Кино – неотъемлемая часть нашей жизни. Вы когда-нибудь задумывались, как киносайты, такие как IMDb или Netflix, определяют список фильмов с самым высоким рейтингом на своих веб-сайтах? Напомним, что после завершения просмотра любого фильма на потоковой платформе система обычно предлагает вам оценить этот фильм по шкале от 1 до 5.

В этой серии сообщений в блоге я сформулирую задачу «нахождения глобального рейтинга фильмов с учетом оценок пользователей» как задачу обучения с полуучителем, а затем решу ее, решив систему линейных уравнений. Алгоритм называется HodgeRank¹ и представляет собой общий метод решения статистического ранжирования на основе данных, включающих количественные оценки, разработанный Jiang et al. из Стэнфордского университета.

Чтобы сформулировать задачу, приведем сначала пример данных, которые у нас есть. Набор данных MovieLens² содержит более 20 миллионов оценок для 27 278 фильмов. Эти данные были созданы 138 493 пользователями в период с 09 января 1995 г. по 31 марта 2015 г. Ниже представлено подмножество набора данных, которое содержит лишь небольшую часть голосов пользователя №1.

Для простоты предположим, что у нас есть только два пользователя, ⍺ и β, и четыре фильма: A,B, С, Г. И их данные голосования выглядят следующим образом:

Теперь нам нужно создать график для каждого голосующего, где вершины — это фильмы, за которые проголосовал этот пользователь, а ребра — это разница в баллах между соответствующими двумя вершинами.

Более того, для вычитания разницы в баллах важен порядок: если мы решим выполнить оценка(A)−оценка(B), мы убедимся, что разница между A и B указывает из B в A. Кроме того, несложно заметить, что в этой формулировке все графики будут полными графиками.

Таким образом, мы можем построить два графика для наших двух избирателей следующим образом:

Учитывая два «локальных» графика для наших отдельных пользователей, теперь мы хотим сформировать «глобальный» график, который содержит информацию обо всем нашем наборе данных; в нашем игрушечном примере он будет содержать данные о голосовании двух избирателей и четырех фильмов.

«Глобальный» график — это результат усреднения всех графиков, созданных всеми избирателями. Например, 0,5 между A и B говорит нам о том, что консенсус среди всех пользователей заключается в том, что B лучше, чем A на 0,5 балла.

Из этого игрушечного примера мы можем легко обобщить таким же образом огромный набор данных MovieLens. Надеюсь, вы уже заметили пару важных особенностей наших локальных и глобальных графов:

  1. Для каждого избирателя локальный граф будет содержать только небольшое количество вершин: это связано с тем, что, каждый избиратель, скорее всего, посмотрел и оценил лишь небольшую часть от общего числа 27 000 фильмов. Так что, если я оценил только 50 фильмов, мой локальный граф будет иметь только 50 вершин, в отличие от глобального графа, который имеет 27 тысяч вершин.
  2. Из-за приведенного выше наблюдения глобальный граф будет чрезвычайно плотным (имеющим много ребер): это потому, что для любой пары фильмов A и B, пока один пользователь смотрел их оба, на глобальном графе будет создано ребро! Подумайте обо всех менее известных инди-фильмах, о которых мало кто слышал.

Поскольку у каждого ребра есть направление, обратите внимание на циклы на графике: что, если на глобальном графике у нас есть A›B›C›A (› означает «имеет более высокий рейтинг, чем»)? Учитывая такие несоответствия в наших данных, как мы узнаем, какой фильм является лучшим?

Алгоритм HodgeRank прекрасно решает вышеуказанные проблемы. Первоначальные авторы разработали алгоритм, используя концепцию алгебраической геометрии, называемую теория Ходжа, которая не очень дружелюбна для тех, кто не знаком с геометрией для выпускников. Вместо этого я представлю более простой для понимания способ, используя тот же игрушечный набор данных, что и выше. Затем я покажу, что этого можно добиться, решая систему линейных уравнений по алгоритму HodgeRank.

Напомним, что наша цель — ранжировать все фильмы. Теперь представьте, что мы уже знали ответ: у нас была глобальная оценка для каждого фильма, поэтому все, что нам нужно было сделать дальше, это просто отсортировать оценку от самой высокой до самой низкой.

Теперь предположим, что для нашего глобального графа число вершин равно |V| а число ребер равно |E|. Кроме того, для любого ребра на графе мы называем вершину, которая указывает на узел-приемник, а другую вершину узел-источник. Тогда мы можем определить матрицу 𝛛1 размера |V|×|E| например следующее:

В 𝛛1 каждый столбец определяет ребро. Мы можем взять значения ребер соответственно в том же порядке и сформировать вектор fдлины |E|:

В настоящее время,

Кроме того, обратите внимание, что

Вспоминая, как мы получили вектор f, мы видим, что эти два вектора представляют одну и ту же идею: разницу в баллах между каждой парой фильмов.

Таким образом, мы пришли к важному наблюдению: если наши глобальные рейтинги точны, эти два вектора выше должны быть максимально близки друг к другу по элементам! Далее мы можем легко сформулировать нашу целевую функцию, задачу оптимизации линейного метода наименьших квадратов:

Как мы узнали на уроке линейной алгебры, один из способов решения линейной задачи наименьших квадратов — решить ее нормальное уравнение:

В области спектральной теории графовособенно, матрица Лапласа графов является хорошо изученным матричным представлением графов . У него много интересных числовых свойств, тесно связанных с графом, который он представляет.

На данный момент наша цель состоит в том, чтобы решить Lr = b, а затем отсортировать записи r, чтобы узнать нашу рейтинг фильмов.

Конечно, в нашем случае L — это огромная плотная квадратная матрица размера |V|×|V|, было бы катастрофическим с вычислительной точки зрения пытаться решить Lr = bиспользуя сокращение строк, чему мы научились в течение первой недели линейной алгебры.

Таким образом, в следующем посте я обобщу основные итерационные и традиционные методы, используемые для решения этого уравнения, и обсужу, какие из них более подходят.

Я надеюсь, что этот пост был полезным и понятным. Если я что-то пропустил или у вас есть вопросы, пожалуйста, дайте мне знать. Спасибо!!!

[1]: Сяой Цзян, Лек-Хэн Лим, Юань Яо, Иньюй Е. Статистическое ранжирование и комбинаторная теория Ходжаhttps://web.stanford.edu/~yyye/hodgeRank2011.pdf

[2]: Группы. Набор данных MovieLens 20M https://grouplens.org/datasets/movielens/20m/