В плейлисте могут соседствовать Кино, Земфира, Noize MC, Linkin Park и Gorillaz. Но что включить дальше? Любимый жанр не решает вопрос: две рок-группы могут нравиться вам совершенно по-разному. Друг, который знает ваши вкусы, предложит что-то конкретное. Попробуем дать такую же задачу программе.
Найдите в каталоге хотя бы трёх знакомых исполнителей. Поставьте каждому оценку от 1 до 5: единица — совсем не нравится, пятёрка — очень нравится. Незнакомых оставьте без оценки. Посмотрите, кого программа предложит, затем измените одну оценку. Как изменится список?
Похож ли результат на совет друга? Пока это впечатление. Чтобы понять, чему доверять, разберём, откуда берётся список и как устроить проверку.
Вход нашей модели — ваши оценки знакомых исполнителей и сведения об их общей аудитории. Ответ — предположение о том, какую оценку вы поставите другому исполнителю. Отсортировав такие прогнозы, получим рекомендации.
В основе опыта — открытый исследовательский набор Last.fm, выпущенный в мае 2011 года: 1 892 слушателя, 17 632 исполнителя и 92 834 записи о прослушиваниях. Для опыта выбраны 200 самых представленных исполнителей и ещё 19 русскоязычных из того же набора — например, Кино, Земфира и Сплин. Это старый срез: многих современных артистов в нём нет. У добавленных исполнителей здесь всего от 4 до 21 слушателя, поэтому данных для рекомендаций мало.
В исходной записи указано, сколько раз человек слушал исполнителя. Звёздных оценок там нет — оценки в нашем опыте ставите вы.
Представьте большую таблицу: строки — слушатели, столбцы — исполнители, отметки — известные прослушивания. Программа ищет повторяющиеся сочетания и сжимает эту таблицу: каждому исполнителю достаётся всего 12 чисел. По вашим оценкам она подбирает ещё 12 чисел — ваш личный профиль. Сопоставляя его с профилями исполнителей, можно получить новые прогнозы. Такой способ сжатия называют матричной факторизацией; вычисления разберём в Профи.
Это простой вариант рекомендательной системы. Она использует закономерности в чужих прослушиваниях и ваши примеры. Здесь нет понимания музыки: программа не слышит мелодию, не читает тексты и не знает, что вы хотите включить именно сегодня.
Можно спросить: «Какую оценку я поставлю этому исполнителю?» Программа отвечает числом, например 3,9 из 5. Предсказание числовой величины называют регрессией. Тем же способом ставят задачи о времени доставки, температуре или цене подержанного велосипеда.
Для проверки нужна ваша настоящая оценка. Если вы поставили 4, прогноз 3,9 ошибся на 0,1, а прогноз 2 — на 2. Чем меньше такой промах, тем точнее числовой ответ. Но одна угаданная оценка ещё не делает модель надёжной: нужно проверить несколько примеров.
В нашей модели 3 — отправная точка. Программа настраивает личный профиль так, чтобы приблизиться к вашим оценкам, но не делать слишком резких выводов из нескольких примеров. Затем использует тот же профиль для незнакомых исполнителей. Если расчёт выходит за пределы 1–5, ограничиваем его этой шкалой. Это предполагаемая оценка, а не измеренная вероятность вашей реакции.
Теперь спросим иначе: «Поставлю ли я не ниже четырёх?» Возможны два ответа: «да» или «нет». Выбор из заранее известных категорий называют классификацией. Для нашего опыта договоримся: прогноз от 4 означает «да», ниже 4 — «нет».
Пусть ваша настоящая оценка — 4. Прогноз А равен 3,9, прогноз Б — 4,7. А ближе по числу, но только Б правильно отвечает на вопрос «не ниже четырёх?». Мы не поменяли ваш вкус — поменяли требуемый ответ и способ проверки.
Рекомендация задаёт ещё один вопрос: «Кого показать первым?» Расположение кандидатов по предполагаемому интересу называется ранжированием. Программа может правильно упорядочить исполнителей, хотя и неточно предскажет каждую оценку. Поэтому качество списка и точность чисел не одно и то же.
Вы уже оценили нескольких исполнителей, значит правильные ответы у нас есть. Спрячем одну оценку, построим прогноз только по оставшимся и лишь затем раскроем спрятанное число. Иначе программа получила бы ответ вместе с условием.
Примеры, по которым модель настраивается, называют обучающей выборкой, или train. Отложенные для проверки — тестовой выборкой, или test. В нашем маленьком опыте оставшиеся оценки задают личный прогноз, а спрятанная служит тестом. Числа, описывающие исполнителей, мы при этом не переучиваем: они получены до ваших оценок.
Повторим опыт, по очереди пряча каждую оценку. Сложим величины промахов и разделим на число проверок — получим среднюю ошибку. Рядом посчитаем ошибку простого соперника: он всегда предсказывает 3. Сложная модель должна доказывать свою пользу сравнением, а не названием.
Три личные оценки — маленькая проверка, а не доказательство качества для всех слушателей. Если после каждого результата менять правило, вы начнёте подгонять его под тест. Для окончательного сравнения понадобится ещё один набор ответов, который не участвовал в выборе правила.
Подбор исполнителя использует готовый каталог. А просьба «сочини песню для нашего класса» требует создать новый материал. Это генерация. У неё может быть много подходящих ответов; проверять нужно выполнение просьбы, факты и качество результата, а не совпадение с одной заранее записанной песней.
Другой пример — афиша школьного концерта. Чтобы вырезать человека из фотографии, недостаточно ответа «на снимке человек». Нужна маска: для каждого пикселя, маленькой клетки изображения, метка «человек» или «фон». Такую разметку изображения называют сегментацией. Если рука ошибочно отмечена как фон, редактор удалит её вместе с ним.
Так карта задач расширяется: число, категория, упорядоченный список, разметка изображения, новый текст или звук. Название приложения не определяет задачу. В одном музыкальном сервисе могут работать сразу несколько моделей с разными ответами.
В учебном каталоге можно пересчитать все варианты после каждого клика. В огромном сначала стоит быстро отобрать кандидатов, затем точнее оценить короткий список. Короткие числовые профили исполнителей уже вычислены заранее: для нового прогноза не нужно снова читать всю историю прослушиваний. Подробно к скорости вернёмся после знакомства с алгоритмами поиска.
Для рабочего сервиса придётся уточнить цель. Хотим, чтобы человек нажал на исполнителя, дослушал трек или нашёл новую любимую музыку? Это разные признаки успеха. Много прослушиваний может означать привычку; высокий интерес к обложке ещё не доказывает, что музыка понравилась.
Формула прогноза и цена вычислений
Начнём с исторической таблицы P: P_{ui}=1, если слушатель u встречается у исполнителя i, иначе 0. Здесь 1 830 строк и 219 столбцов. Ноль — отсутствие записи, не оценка «не нравится».
Подберём для слушателей векторы a_u, для исполнителей — q_i, по 12 координат в каждом. Их скалярное произведение должно приближать таблицу:
Для браузера все векторы исполнителей поделены на общий коэффициент: средний квадрат их длины стал равен 1. Обратное масштабирование векторов слушателей сохраняет произведение матриц. Координаты не имеют заданных названий вроде «рок» или «поп».
Теперь учим новый личный профиль p по вашим оценкам r_j исполнителей из множества R. Это отдельная задача: в исходном Last.fm звёздных оценок нет.
Для проверки оценки r_i сначала исключаем её из R и заново находим p. Иначе личный профиль уже знал бы проверяемый ответ. Ошибка по тем же оценкам, на которых он учился, не заменяет эту проверку.
При N исполнителях и d=12 координатах хранение профилей и полный пересчёт их числовых прогнозов требуют порядка Nd чисел и операций. Обучение личного профиля по m оценкам требует порядка md^2+d^3 операций. Для большого каталога можно ускорить поиск кандидатов, но точность такого отбора надо проверять отдельно.
Условимся обозначать настоящий ответ через y, прогноз — \hat y. Для регрессии считаем |\hat y-y|, для обычной классификации — совпадение категории. Эти две проверки не взаимозаменяемы.
В генерации текста ответ собирается последовательно. Вероятность последовательности раскладывается по правилу цепочки:
Цель: Сделайте три шага генерации, выбирая на каждом самый вероятный токен, и получите фразу «буду через десять минут»
Распределение зависит от того, что уже набрано, поэтому берите его заново на каждом шаге; и выбирайте не любой вариант, а тот, у которого вероятность в dist наибольшая
Точнее оценки — лучше рекомендации?
У трёх исполнителей настоящие оценки слушателя равны 5, 4 и 1. Модель А предсказывает 4, 5 и 1; модель Б — 3, 2 и 1. Какая модель лучше по средней абсолютной ошибке? Какая верно выбирает любимого исполнителя? Докажите на этом примере, что улучшение числовой ошибки не гарантирует улучшения первой рекомендации.
Решение
У А средняя ошибка равна (1+1+0)/3=2/3, у Б — (2+2+0)/3=4/3: по числам А точнее. Но А ставит второго исполнителя выше первого, а Б правильно выбирает первого. Числовая ошибка учитывает расстояния до оценок, первая рекомендация — победителя по порядку. Оба показателя полезны, но отвечают на разные вопросы.Рекомендации используют известные предпочтения; чужие прослушивания и ваши оценки — разные сведения.
Регрессия предсказывает число, классификация выбирает категорию, ранжирование упорядочивает кандидатов.
Тестовый ответ скрывают до прогноза; качество сравнивают с простым правилом.
Маска отмечает части изображения, генерация создаёт новый материал; каждому ответу нужна своя проверка.
Домашняя работа
Источники
- Matrix factorization, Google — представление слушателей и объектов короткими векторами, взвешенная функция ошибки и ALS.
- HetRec 2011, GroupLens — Last.fm и набор Universidad Autónoma de Madrid: Cantador, Brusilovsky, Kuflik, HetRec 2011. Записи о прослушиваниях, не звёздные оценки. Условия набора предусматривают некоммерческое использование.
- README набора Last.fm — состав файлов, статистика, значение listening count и условия использования.
- Google: Collaborative filtering — рекомендации по взаимодействиям пользователей, явная и косвенная обратная связь.
- Google: Recommendation systems overview — отбор кандидатов, оценка и окончательное упорядочивание.
- Google: What is Machine Learning? — обучение по примерам, классификация и регрессия.
- Vaswani et al.: Attention Is All You Need — архитектура трансформера; дополнительное чтение о генерации.
- Bike Sharing, UCI — источник отдельного упражнения тренажёра о выдачах велосипедов; Hadi Fanaee-T, CC BY 4.0.