В декабре я успешно сдал курс Математика больших данных. Нужно было либо решить всякие стохастические задачки, либо сделать проект. Я выбрал второе, и сейчас я про это расскажу.

Проект заключался в реализации алгоритма малорангового восстановления матрицы. Вообще, это довольно полезная штука: например, чтобы Кинопоиск мог предложить вам какой-то фильм, ему нужно знать, как вы оценивали другие, уже просмотренные фильмы. Из оценок можно сформировать матрицу (пользователи, фильмы), где на пересечении строки с пользователем A и фильмом B будет стоять оценка, которую пользователь A выставил фильму B. Это будет очень большая и жутко разреженная матрица, ведь каждый пользователь мог просмотреть лишь малое число от всех фильмов, которые есть у Кинопоиска.
Ну вот, если вдруг мы хотим предлагать пользователю какие-то фильмы, которые ему наверное понравятся, нам бы хотелось заранее знать, какую оценку он мог бы поставить фильму, который он еще не смотрел. Но как это сделать?

Хорошая новость заключается в том, что, хоть матрица (пользователи, фильмы) и большая, но скорее всего она малоранговая: вероятно, существует какой-то небольшой набор фильмов, оценки которых будут давать оценки всем другим фильмам. Как это понимать?
Об этом можно думать так: все фильмы можно разбить по жанрам: детективы, комедии, хорроры. Если пользователю A нравятся детективы (например, всем просмотренным детективам он выставил высокую оценку), но не нравятся хорроры (аналогично, всем просмотренным хоррорам он выставил низкую оценку), то вполне вероятно, что какому-то другому детективу он также выставит высокую оценку, а значит и предлагать ему надо какой-то детектив. В этом и заключается малоранговость матрицы (пользователи, фильмы): можно найти небольшое число фильмов (скажем, по одному ключевому фильму в каждом жанре), пользовательские оценки которых будут определять оценки других фильмов.

Допустим, это так. Выходит, чтобы приблизить нашу исходную матрицу (пользователи, фильмы), нам нужно искать среди матриц такого же размера, но у которых маленький ранг (например, ранг k). Это как-то облегчает нашу участь? О да: множество матриц фиксированного размера и фиксированного ранга, на самом деле, являются гладким многообразием! Более того, оно погружено в Евклидово пространство, а значит можно наследовать риманову метрику с объемлющего пространства на наше многообразие. А тогда мы можем заниматься всякой гладкой оптимизацией, ведь у нас теперь есть возможность посчитать градиент.

Рассмотрим такую функцию f(index; A) = A[index], которая по заданным индексам и матрице возвращает значения матрицы в этих индексах. Пусть index будет теперь означать индексы исходной матрицы (пользователи, фильмы), в которых стоят оценки. Тогда, можно рассмотреть квадратичную функцию ошибки на многообразии матриц фиксированного ранга:

(f(index; (пользователи, фильмы)) - f(index; A))**2

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

Вообщем, просмотреть все детали и код можно в этой тетрадке.