Машинное обучение: рекомендательные системы​

Продолжаем нашу постоянную рубрику #чтопочитать. Специалисты компании Sociaro подготовили перевод очередной статьи, которая поможет лучше разобраться в том, что такое машинное обучение. Как и просили — статья для продвинутых пользователей.

Оригинальная статья.

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

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

Сперва я просто хочу обратить внимание на самое главное. В данной статье мы рассмотрим основные понятия. Но, пожалуйста, имейте в виду, что настоящие продукционные системы трудоемки из-за своего множества ансамблевых методов, выполняемых в несколько этапов.

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

Фильтрация по содержимому (content-based filtering) выдает рекомендации на основе сходства признаков предмета (item features) и предпочтений пользователя. То есть мы можем извлечь значимые признаки из описания фильма и сопоставить их с предпочтениями пользователя.

Например, фильм «Шпион» может быть показан как фильм Маккарти и будет предлагаться пользователям, которые регулярно смотрят фильмы Маккарти. Информация о фильме может быть извлечена из названия фильма, его описания и информации, предоставленной студией.

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

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

Существует много методов извлечения признаков. Мы можем создать мешок слов из описания фильма или из слов, собранных в соответствии с предпочтениями пользователя.

Затем мы используем метод TF-IDF для пересчета значений в этом векторе. Это снижает значение слов, которые часто встречается в описаниях фильмов.

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

Другие методы измерения, включая коэффициент корреляции Пирсона, норма L1, норма L2 или коэффициент сходства, могут быть использованы в зависимости от того, как рассчитывается вектор. Если у Вас возникали трудности, связанные с пониманием использованных терминов машинного обучения, предлагаю сначала прочитать данную статью.

Как и во многих методах машинного обучения, предварительная обработка данных очень важна. Мы просматриваем словарь, используемый при подготовке мешка слов, и ограничиваем его размер. Стоп-слова должны быть удалены.

Слова в топе рассматриваем вручную и удаляем те, которые не связаны с решением поставленной задачи. Мы также можем подбирать фразы и относиться к ним как к одному слову в словаре. Кроме того, существуют варианты слов, которые должны совпадать с одним и тем же словом. Например, все множественные числа можно рассматривать как единственные.

Тем не менее, даже TF-IDF часто упоминается в рекомендательных системах. Этот метод уменьшает значение таких распространенных категорий, как «комедия», что важно при составлении рекомендаций. TF-IDF играет важную роль в поиске по запросам. Однако в некоторых случаях он может привести к появлению слишком узконаправленных рекомендаций, что негативно скажется на разнообразии рекомендаций.

Поэтому в некоторых системах могут быть исключены некоторые как распространенные, так и редкие слова, которые оказывают незначительное влияние на рекомендации. Затем в них просто используется частота встречающихся слов вместо TF-IDF. Точный выбор зависит от контекста приложения.

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

Фильтрация по содержимому имеет ограничение по качеству описания, предоставляемого контент-провайдером. Технически, существует ограничение на то, какие признаки могут быть извлечены из ограниченного объема контентной информации.

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

При совместной (коллаборативной) фильтрации мы концентрируемся на составлении прогнозов на основе поведения пользователей, а не на извлечении признаков. Обилие поведенческой информации может сделать совместную фильтрацию более привлекательной и подходящей.

При совместной фильтрации нам предоставляются метки (labels), но не контентные признаки. Совместная фильтрация собирает информацию о том, как вы взаимодействуете с предметами — что вы оцениваете, как вы оцениваете, что вы просматриваете и/или что вы покупаете.

Один из типичных подходов заключается в создании матрицы рейтингов пользователя, содержащей оценки, которые пользователь дал разным фильмам. Благодаря ей, мы находим сходства и даем рекомендации.

Например, вы дали оценки нескольким фильмам. Мы находим людей, которые дали примерно такие же оценки тем же самым фильмам, и предлагаем вам те фильмы, которые вы не смотрели, но которые получили высокие оценки от этих людей (пользователь-пользователь).

С другой стороны, вместо того чтобы находить сходства в людях, мы можем находить сходства в фильмах (предмет-предмет) и делать предложения на основе того, что вы уже смотрите. Что касается проблемы холодного старта, предложения вида предмет-предмет могут быть проще, когда информация о новом пользователе ограничена.

Одно из возможных применений совместной фильтрации — это нахождение k-ближайших соседей и использование их среднего значения в качестве нашего прогноза. Или же мы можем вычислить сходства (u) между вами и всеми другими пользователями и использовать их для вычисления средневзвешенного значения ваших возможных оценок. Конечно, для масштабирования второго подхода необходимо использование приближенных или упрощенных значений.

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

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

Сингулярное разложение представленное выше является одним из методов разложения матрицы. Оно разбивает данные на независимые главные компоненты, как показано ниже.

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

Мы позволяем компьютеру изучать их на основе данных, как и в других методах машинного обучения. Разложение матрицы — это большая тема, и мы не будем подробно останавливаться на ней. Обсуждение данной темы можно найти здесь или более подробное здесь.

Но количество скрытых факторов может быть огромным, и многие из них могут не иметь большого значения. В методе главных компонент (PCA) мы просто усекаем те, которые не являются важными (имеют очень маленькое значение σᵢ по сравнению с другими).

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

С помощью метода главных компонентов любая матрица рейтингов пользователя может быть разложена на матрицу P, содержащую скрытый фактор пользователя, и матрицу Q, содержащую скрытый фактор предмета. Рейтинг фильма от пользователя может быть восстановлен путем умножения соответствующего скрытого фактора пользователя и скрытого фактора фильма.

Но как найти матрицы, если в матрице рейтингов пользователя отсутствуют некоторые записи? Пользователи оценивают или взаимодействуют только с горсткой фильмов. Для решения этой проблемы мы применяем стохастический градиентный спуск (SGD) для изучения разложенной матрицы Z и W.

Но мы включаем ошибки для корректных записей только в матрицу рейтингов R. Мы не будем вносить ошибку в функцию потерь для записей с отсутствующими оценками.

Кроме того, будут иметь место предвзятые смещения рейтингов у отдельных пользователей и какой-нибудь культовый фильм может быть оценен намного выше среднего. Мы учтём эти предвзятости при составлении прогноза и добавим условия регуляризации для них в функцию потерь.

Многие цепи Маркова могут быть решены с помощью случайных блужданий. Допустим, мы высаживаем 100 покупателей случайным образом по центру Сан-Франциско и предоставляем стохастическую матрицу, чтобы показать вероятность того, куда покупатели могут направиться дальше с текущей позиции.

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

Мы можем представить каждый фильм в виде вершины (узла) на графе. Основываясь на многих факторах, в том числе на том, какие товары пользователи могут выбрать далее, какие товары могут быть просмотрены или куплены вместе, какие товары пользователь высоко оценил вместе, или на других моделях поведения пользователей, мы можем сформулировать переходную вероятность от одного товара к другому.

Эти вероятности могут быть представлены в виде стохастической матрицы ниже. Мы хотим знать распределение вероятностей того, куда мы можем приземлиться по мере того, как время приближается к бесконечности. Эти вероятности служат ранжированием при составлении рекомендаций.

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

К счастью, обычно такое решение можно найти в ограниченное количество шагов. Если мы продолжим умножать приведенную выше стохастическую матрицу, то она будет упрощаться и во многих случаях очень быстро (нам не нужно выполнять бесконечные шаги). Вектор в правой части уравнения демонстрирует вероятность каждого состояния, в котором мы можем находиться.

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

Google PageRank использует входящие и исходящие ссылки на страницу в ранжировании их поиска. (Подробнее о PageRank обсуждается в контексте собственного вектора здесь).

Найдя стабильное состояние такого случайного блуждания, можно использовать соответствующую вероятность каждого состояния для финального ранжирования. Задача заключается в нахождение собственных векторов в разложении матрицы.

На практике мы продолжаем умножать матрицу R и надеемся, что она быстро станет проще. PageRank показала, что при 322 миллионах ссылок на страницу решение сходится до допустимого предела за 52 операции. Поэтому решение неожиданно хорошо масштабируется (детали).

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

Переходная вероятность обновляется следующими уравнениями. Если команда A выиграет у команды B, переходная вероятность увеличится в сторону A. Она увеличится еще больше, если игра будет сыграна всухую.

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

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

На Pinterest пользователи могут прикрепить посты (пины, pins) других пользователей на свой доску (board). Таким образом, Pinterest может построить гигантский граф с 3 миллиардами вершин и 17 миллиардами рёбер, связывающих посты и доски вместе для всего сайта.

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

Мы можем повторить процесс со стартового поста много раз, чтобы сформировать аппроксимацию по частоте посещений постов для цепи Маркова. Ниже приведен алгоритм:

Другая возможность — использование веса (biased weight) при выборе вершин. Например, доски с меньшим количеством постов могут быть специально показаны большему количеству людей, «прорекламированы», чтобы показать, что посты в них могут быть более целенаправленными и важными, чем доски с большим количеством постов.

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

Вот общий алгоритм, используемый в Pixie на Pinterest.

Здесь применяется ранняя остановка, а также использование нескольких постов Q для генерации случайного блуждания. Pixie позволяет использовать несколько постов с разным весом. Например, вес более высок для постов, с которыми взаимодействие произошло недавно.

Дополнительные посты улавливают контекст предыдущего поведения пользователя. Например, они могут уловить последовательность постов, с которыми пользователь взаимодействовал во время поиска. Как показано выше, V[p] не суммируется линейно. Вместо этого, значение V будет увеличено, если несколько начальных постов (Q) приземлятся на один и тот же пост (в результате квадратичной функции).

Как уже упоминалось, некоторые доски менее целенаправленны. Разумно очистить те, которые переборщили с темами. Как цитируется в исследовательской работе:

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

Благодаря обрезке графа, граф для всего сайта может поместиться в память одного сервера. Без межсерверной связи он может выполнять запросы, соблюдая требования к задержке.

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

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

Таким образом, может существовать граф пост-доска и граф пользователь-пост. Затем Pixie объединяет кандидатов и ранжирует их. Наконец, чтобы избежать скопления похожих постов рядом друг с другом, применяется алгоритм blender для создания небольшой случайности отображения всех постов в ленте пользователя.

Давайте остановимся на ранжирующей модели (ranking model). По мере того, как глубокое обучение развивается, система может построить глубокую сеть для прогнозирования вероятности взаимодействия с постом. Во-первых, Pixie извлекает признаки кандидатов и использует полносвязную сеть для составления прогнозов.

Чтобы обобщить решение, Pixie обучается предсказывать несколько задач, включая репост, клик, долгий клик и крупный план (close-up). Это позволяет избежать чрезмерной оптимизации сети под конкретную задачу и делает выученную модель более универсальной. Ниже приведена взвешенная функция потерь, объединяющая все четыре задачи.

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

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

Давайте сперва определим несколько терминов. Поддержка (support) S — это вероятность событий. Например, какова вероятность покупки S₁, S₂, …Sk ∈ S.

Достоверность (confidence) — это то, как часто случается T, когда случается S. Например, как часто покупка одного товара происходит вместе с покупкой другого товара.

Для ассоциации, мы ищем высокую поддержку и высокую достоверность.

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

Сначала мы начнем с данных о транзакциях клиентов. Первым шагом мы вычисляем соответствующую поддержку для каждого отдельного товара. (Для простоты в наших примерах мы используем количество вместо вероятности). Но, чтобы избежать экспоненциального роста комбинаций, товары с количеством меньше или равным порогу будут исключены.

Далее мы создаем комбинации по два товара из тех, которые остались после предыдущего шага. Это останавливает экспоненциальный рост.

Затем мы продолжаем строить 3-х, 4-х и 5-и товарные комбинации, до тех пор, пока не закончатся предметы, которые можно включить в комбинации. После этого мы создаем частые наборы товаров (A, P, K, M, AP, AM, PM, KM и APM).

Наша следующая задача — создать ассоциативные правила. Для комбинации APM, существуют следующие варианты:

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

Тем не менее, одна лишь достоверность может ввести в заблуждение. Достоверность P(Y|X) может быть высокой просто потому, что набор Y популярен. Мы хотим узнать дополнительную достоверность Y при данном X. Лифт (lift) заново откалибрует достоверность.

Если лифт больше 1, это означает, что покупатели чаще покупают оба набора вместе, чем по отдельности, или наоборот, если он меньше 1. Убедительность (conviction) — это частота случаев, когда X был куплен, а Y — нет, и наоборот. Значение 1,3 означает, что наш прогноз того, что эти товары будут приобретены вместе, на 30% более верен, чем если бы эти товары были приобретены вместе по чистой случайности.

Рассмотрим пример применения алгоритма Apriori при формировании ассоциативных правил. В приведенном ниже примере предпринимается попытка найти ассоциации для ответов на 14 вопросов опроса. Для вопросов с категоричными (categorical) ответами (такими, которые используют не числа, а ответы «да», «нет», «женат», «разведен») каждый возможный ответ рассматривается как отдельный предмет.

Однако, численные (ordinal) ответы этот пример рассматривает как либо меньше среднего значения, либо больше или равно среднему значению. Таким образом, возможными варианты могут быть: мужчина, не женат, разведен; доход < $40,000, доход ≥ $40,000 и т.д.

#машинноеобучение