ML Данные и машинное обучение Алгоритм
Рекомендации через разложение матрицы
Также: Matrix factorization · рекомендательная система · recommender system · коллаборативная фильтрация · collaborative filtering · ALS · alternating least squares · латентные факторы · latent factors · Netflix Prize
Таблица «читатель × книга» почти пуста: каждый оценил десятки книг из тысяч. Если описать каждого читателя и каждую книгу несколькими числами — «вкусом», — оценку можно предсказать их скалярным произведением, а числа найти по известным оценкам, попеременно решая обычные наименьшие квадраты. На 277 тысячах настоящих оценок тысячи книг — рекомендации для вас и карта книг, где жанры собираются сами.
Четыре тысячи читателей поставили тысяче популярных книг 277 181 оценку от одной до пяти. Если записать их в таблицу «читатель × книга», заполнено меньше семи процентов клеток: каждый читатель знает несколько десятков книг из тысячи. Рекомендация — это догадка, что стоит в пустой клетке. Разложение матрицы угадывает так: каждому читателю и каждой книге ставит в соответствие десять чисел, и оценка — их скалярное произведение. Числа никто не задаёт заранее, они получаются из оценок. И у книг, которые любят одни и те же люди, они оказываются похожими: рядом с «Хоббитом» — «Властелин колец», рядом с «Гордостью и предубеждением» — другие романы Остин.
Отметьте несколько книг — модель найдёт ваш вектор и предложит книги, на которые он указывает. Точки на карте — все тысяча книг по двум главным направлениям их векторов (как в методе главных компонент); стрелка — ваш вкус в тех же осях. Жанров модель не знает: книги оказываются рядом только потому, что их любят и не любят одни и те же читатели. На карте видны лишь два направления из десяти, поэтому соседство на ней приблизительное; «похожие книги» модель ищет по всем десяти числам — так у «Хоббита» и находятся три тома «Властелина колец».
Идея
Предсказание складывается из четырёх частей:
r̂ui = μ + bu + bi + pu · qi.
μ — средняя оценка всех, bu — насколько читатель щедрее среднего, bi — насколько книгу любят больше средней, а pu · qi — совпадение вкусов: векторы из k чисел. Если считать, что всё это верно для каждой известной оценки, получится таблица ранга k с поправками — отсюда «разложение матрицы»: таблица оценок ≈ P · QT.
Числа подбирают так, чтобы на известных оценках сумма квадратов ошибок плюс штраф λ·(|p|² + |q|² + b²) была наименьшей. Целиком эта задача не выпуклая, но если векторы книг заморожены, то для каждого читателя она — обычная линейная регрессия с k + 1 неизвестными, и решается точно. Поэтому решают попеременно: при известных книгах — всех читателей, при известных читателях — все книги. Это ALS, чередующиеся наименьшие квадраты.
Пусть F(P, Q) — сумма квадратов ошибок на известных оценках плюс штраф λ > 0. Если заменить каждый вектор читателя решением его задачи наименьших квадратов при текущих Q, значение F не увеличится; то же для книг. Значения F по раундам не возрастают и сходятся.
При фиксированных Q функция F распадается в сумму слагаемых, каждое из которых зависит только от одного читателя: его ошибки и его штраф. Слагаемое читателя u — квадратичная функция от (pu, bu) с матрицей Σ xxT + λE, где x = (qi, 1) по его книгам. Эта матрица положительно определена: Σ xxT неотрицательно определена, а λE добавляет λ|v|² > 0 к любому ненулевому v. Значит, у слагаемого единственный минимум — решение системы, и замена старого вектора этим минимумом не увеличивает слагаемое, а с ним и всю сумму. Последовательность значений F не возрастает и ограничена снизу нулём, поэтому сходится.
Сходится значение, но не обязательно к лучшему возможному: задача не выпуклая, и ALS может остановиться в точке, где знаки векторов «не договорились». На практике запускают несколько раз с разных случайных векторов. А новому читателю, который появился после обучения, переобучать модель не нужно: его вектор — решение той же системы по векторам книг, которые он оценил. Так работает сцена выше.
Код
Листинг берёт 200 книг, которые оценивали чаще всего, и 2890 читателей с 25 оценками из них; каждая десятая оценка отложена для проверки. Ошибка — корень из среднего квадрата промаха на отложенных оценках. Если всем ставить среднюю, 3,95, промах 1,024 звезды. Средняя книги — 0,977. Поправки на читателя и книгу — 0,902: поправка на щедрость читателя сняла с ошибки больше, чем средняя книги до неё. Векторы из пяти чисел — 0,865. Выигрыш последней ступени кажется скромным, но именно он отличает «популярное» от «вашего»: самые близкие к «Хоббиту» — три книги «Властелина колец», к «Сумеркам» — продолжения, а читателю Остин, Бронте и Фицджеральда, которому не нравится Дэн Браун, модель советует «Грозовой перевал», «Гроздья гнева» и «Ромео и Джульетту».
Рекомендации упорядочены по совпадению вкуса p · q, без поправки книги. С поправкой наверх выходят книги, которые любят все, — сборники комиксов и любимые циклы фэнтези, — и рекомендации у разных читателей становятся одинаковыми.
Сколько чисел и какой штраф
Модель сцены обучена на всей выборке, и на графике — её ошибка на отложенных оценках для векторов от 0 до 40 чисел. С заметным штрафом, λ = 15, длинные векторы немного помогают: от 0,887 без векторов до 0,851 при сорока числах. Со слабым штрафом, λ = 1, всё наоборот: при 40 числах ошибка 1,130 — хуже, чем если всем ставить среднюю, 1,006. Сорок чисел на читателя, у которого в среднем 69 оценок, — почти столько же неизвестных, сколько уравнений, и модель запоминает шум. Штраф не даёт числам расти там, где данные их не подтверждают.
Сколько это стоит
Раунд ALS собирает для каждого читателя и каждой книги систему (k + 1) × (k + 1) — по оценке O(k²) на сборку — и решает её методом Гаусса за O(k³). Всего O(N·k² + (u + i)·k³) на раунд, и раундов обычно немного. Все системы одного полураунда независимы, поэтому ALS хорошо делится между машинами — за это его и выбирают для больших данных. Новый читатель — одна система, микросекунды.
Другой путь — градиентный спуск по одной оценке за раз (Саймон Фанк, 2006): шаг дешевле, памяти меньше, но нужно подбирать шаг обучения и число проходов. На неявных данных — «смотрел», «слушал», где пустая клетка тоже что-то значит, — ALS выгоднее: пустые клетки входят в систему одной общей матрицей.
Где легко ошибиться
- Пустые клетки как нули. Если вписать в пропуски нули и разложить всю таблицу (например, сингулярным разложением), модель будет предсказывать нули — ведь их большинство. Ошибка считается только по известным оценкам.
- Без штрафа. У читателя с тремя оценками десять неизвестных: без λ система вырождена, а с маленьким λ векторы подгоняются под каждую оценку и предсказывают остальное наугад.
- Проверка на тех же оценках. На оценках, по которым учились, ошибка падает с каждым числом в векторе; честная ошибка — только на отложенных.
- Популярность вместо вкуса. Поправка книги bi честно предсказывает оценку, но в рекомендациях вытягивает наверх одно и то же для всех. Для «вам может понравиться» её ослабляют или убирают.
- Холодный старт. У новой книги нет оценок и нет вектора; у нового читателя — пока не отметит хоть что-нибудь. Здесь выручают признаки самой книги — жанр, автор, текст.
Где работает
Рекомендации. Фильмы, книги, музыка, товары: «вам может понравиться» и «с этим смотрят» строятся на векторах вкуса или их потомках — моделях, которые добавляют время, контекст и признаки.
Большие и неявные данные. В Spark MLlib — ALS для явных и неявных оценок, в библиотеке implicit — ALS по работе Ифань Ху, Иегуды Корена и Криса Волински (2008) для кликов и прослушиваний, где «оценки» — это сколько раз человек что-то открыл.
Похожие объекты. Близкие векторы книг — книги, которые любят одни и те же люди; это основа «похожих товаров», даже когда описания у них совсем разные.
Пропуски в измерениях. Таблица датчиков по времени, где часть измерений потеряна, или таблица расстояний в сети, измеренных не для всех пар, — то же восстановление матрицы малого ранга по части клеток.
История
В октябре 2006 года Netflix выложил сто миллионов оценок фильмов и объявил конкурс: улучшить свою систему рекомендаций на десять процентов. Через два месяца Брэндин Уэбб под псевдонимом Саймон Фанк описал в блоге разложение оценок градиентным спуском по одной оценке за раз, и оно стало основой почти всех сильных решений. В 2008 году Юньхун Чжоу и соавторы предложили для того же конкурса ALS со штрафом, который хорошо делится между машинами. Иегуда Корен, Роберт Белл и Крис Волински добавили поправки читателя и фильма, время и неявные данные; их команда вместе с соавторами выиграла конкурс в сентябре 2009 года, улучшив исходную систему на 10,06 %. Обзор Корена, Белла и Волински 2009 года «Методы разложения матриц для рекомендательных систем» стал стандартным введением в тему. А сама идея лучшего приближения матрицы малым рангом восходит к теореме Карла Эккарта и Гейла Янга 1936 года — для полностью известной матрицы.
Задачи
Подобрать векторы по известным клеткам так, чтобы ошибка со штрафом была как можно меньше.
Векторы вкусаДанные: Оценки книг: goodbooks-10k (Зыгмунт Заёнц), CC BY-SA 4.0