![image](https://habrastorage.org/webt/gq/td/mc/gqtdmc8joactk6gu7xrzcdr0f4i.jpeg)
«Эта книга — живой портрет цифровых преобразований в маркетинге. Она показывает, как наука о данных становится неотъемлемой частью любой маркетинговой деятельности. Подробно описывается, как подходы на основе анализа данных и интеллектуальных алгоритмов способствуют глубокой автоматизации традиционно трудоемких маркетинговых задач. Процесс принятия решений становится не только более совершенным, но и более быстрым, что важно в нашей постоянно ускоряющейся конкурентной среде. Эту книгу обязательно должны прочитать и специалисты по обработке данных, и специалисты по маркетингу, а лучше, если они будут читать ее вместе.» Андрей Себрант, директор по стратегическому маркетингу, Яндекс.
Отрывок. 5.8.3. Модели скрытых факторов
В алгоритмах совместной фильтрации, обсуждавшихся до сих пор, большая часть вычислений выполняется на основе отдельных элементов матрицы рейтингов. Методы на основе близости оценивают отсутствующие рейтинги непосредственно по известным значениям в матрице рейтингов. Методы на основе моделей добавляют слой абстракции поверх матрицы рейтингов, создавая предиктивную модель, которая фиксирует определенные закономерности взаимоотношений между пользователями и элементами, но обучение модели по-прежнему сильно зависит от свойств матрицы рейтингов. Как следствие, эти методы совместной фильтрации обычно сталкиваются со следующими проблемами:
Матрица рейтингов может содержать миллионы пользователей, миллионы элементов и миллиарды известных рейтингов, что создает серьезные проблемы вычислительной сложности и масштабируемости.
Матрица рейтингов, как правило, очень разрежена (на практике может отсутствовать около 99 % рейтингов). Это влияет на вычислительную стабильность алгоритмов рекомендаций и приводит к недостоверным оценкам, когда у пользователя или элемента нет действительно похожих соседей. Эта проблема часто усугубляется тем, что большинство базовых алгоритмов ориентированы либо на пользователей, либо на элементы, что ограничивает их способность фиксировать все типы сходств и взаимоотношений, доступных в матрице рейтингов.
Данные в матрице рейтингов обычно сильно коррелируют из-за сходств пользователей и элементов. Это означает, что сигналы, доступные в матрице рейтингов, не только разрежены, но и избыточны, что способствует обострению проблемы масштабируемости.
Приведенные выше соображения указывают на то, что исходная матрица рейтингов может быть не самым оптимальным представлением сигналов, и следует рассмотреть другие альтернативные представления, более подходящие для целей совместной фильтрации. Чтобы изучить эту идею, вернемся к исходной точке и немного поразмышляем о характере служб рекомендаций. По сути, службу рекомендаций можно рассматривать как алгоритм, предсказывающий рейтинги на основе некоторой меры сходства между пользователем и элементом:
![image](https://habrastorage.org/webt/at/bc/6n/atbc6no-aj2vssp1mrgyctgu_oy.png)
Один из способов определить эту меру сходства — использовать подход скрытых факторов и отобразить пользователей и элементы в точки в некотором k-мерном пространстве, чтобы каждый пользователь и каждый элемент были представлены k-мерным вектором:
![image](https://habrastorage.org/webt/9e/ck/no/9eckno4ntrf2yl0hw1q2tr2irbk.png)
Векторы должны строиться так, чтобы соответствующие размерности p и q были сопоставимы друг с другом. Иначе говоря, каждое измерение можно рассматривать как признак или понятие, то есть puj является мерой близости пользователя u и понятия j, а qij, соответственно, является мерой элемента i и понятия j. На практике эти размерности часто интерпретируются как жанры, стили и прочие атрибуты, применимые одновременно к пользователям и элементам. Сходство между пользователем и элементом и, соответственно, рейтинг можно определить как произведение соответствующих векторов:
![image](https://habrastorage.org/webt/k3/1w/9w/k31w9wqmwas5pfvhr8_mopo7ibg.png)
Поскольку каждый рейтинг можно разложить на произведение двух векторов, принадлежащих пространству понятий, которое не наблюдается непосредственно в исходной матрице рейтингов, p и q называются скрытыми факторами. Успех этого абстрактного подхода, конечно, полностью зависит от того, как именно определяются и конструируются скрытые факторы. Чтобы ответить на этот вопрос, заметим, что выражение 5.92 можно переписать в матричной форме следующим образом:
![image](https://habrastorage.org/webt/2i/bp/j9/2ibpj9pmptpun2amylvxf41okjw.png)
где P — матрица n × k, собранная из векторов p, а Q — матрица m × k, собранная из векторов q, как показано на рис. 5.13. Основной целью системы совместной фильтрации обычно является минимизация ошибки прогнозирования рейтинга, что позволяет прямо определить задачу оптимизации относительно матриц скрытых факторов:
![image](https://habrastorage.org/webt/9h/nm/mx/9hnmmxregnvn9snp9empxqf91qk.png)
![image](https://habrastorage.org/webt/z-/vl/nu/z-vlnuz-v9git5dmm0nj79etl5g.png)
Если предположить, что число скрытых размерностей k фиксировано и k ≤ n и k ≤ m, задача оптимизации 5.94 сводится к задаче низкоранговой аппроксимации, которую мы рассматривали в главе 2. Чтобы продемонстрировать подход к решению, допустим на минутку, что матрица рейтингов полная. В этом случае задача оптимизации имеет аналитическое решение в терминах сингулярного разложения (Singular Value Decomposition, SVD) матрицы рейтингов. В частности, с помощью стандартного алгоритма SVD матрицу можно разложить на произведение трех матриц:
![image](https://habrastorage.org/webt/7z/ic/x0/7zicx0iwp156hctp6t7axd5bzu4.png)
где U — матрица n × n, ортонормированная по столбцам, Σ — диагональная матрица n × m, а V — матрица m × m, ортонормированная по столбцам. Оптимальное решение задачи 5.94 можно получить в терминах этих факторов, усеченных до k наиболее значимых размерностей:
![image](https://habrastorage.org/webt/mw/i-/os/mwi-oskhgcs-ehf_bhepytyo_os.png)
Следовательно, скрытые факторы, оптимальные с точки зрения точности прогнозирования, можно получить сингулярным разложением, как показано ниже:
![image](https://habrastorage.org/webt/uc/ih/yl/ucihyltxuqye29vkocknsbzyguw.png)
Эта модель скрытых факторов, основанная на SVD, помогает решить проблемы совместной фильтрации, описанные в начале раздела. Во-первых, она заменяет большую матрицу рейтингов n × m матрицами факторов n × k и m × k, которые обычно намного меньше, потому что на практике оптимальное количество скрытых размерностей k часто невелико. Например, известен случай, когда матрицу рейтингов с 500 000 пользователей и 17 000 элементов удалось достаточно хорошо аппроксимировать с использованием 40 измерений [Funk, 2016]. Далее, SVD устраняет корреляцию в матрице рейтингов: матрицы скрытых факторов, определяемые выражением 5.97, являются ортонормированными по столбцам, то есть скрытые измерения не коррелированы. Если, что обычно верно на практике, SVD также решает проблему разреженности, потому что сигнал, присутствующий в исходной матрице рейтингов, эффективно концентрируется (напомню, что мы выбираем k размерностей с наибольшей энергией сигнала), а матрицы скрытых факторов не разрежены. Рисунок 5.14 иллюстрирует это свойство. Алгоритм близости на основе пользователей (5.14, a) свертывает разреженные векторы рейтингов для данного элемента и данного пользователя, чтобы получить оценку рейтинга. Модель скрытых факторов (5.14, б), напротив, оценивает рейтинг путем свертки двух векторов уменьшенной размерности и с более высокой плотностью энергии.
![image](https://habrastorage.org/webt/v3/te/fm/v3tefmto-k2yf54og0xn4rpbxlq.png)
Только что описанный подход выглядит как стройное решение задачи скрытых факторов, но на самом деле он имеет серьезный недостаток из-за предположения о полноте матрицы рейтингов. Если матрица рейтингов разрежена, что имеет место почти всегда, стандартный алгоритм SVD нельзя применить напрямую, поскольку он не способен обрабатывать отсутствующие (неопределенные) элементы. Самым простым решением в этом случае является заполнение отсутствующих рейтингов некоторым значением по умолчанию, но это может привести к серьезному смещению прогноза. Кроме того, это неэффективно с вычислительной точки зрения, потому что вычислительная сложность такого решения равна сложности SVD для полной матрицы n × m, тогда как желательно иметь метод со сложностью, пропорциональной числу известных рейтингов. Эти проблемы можно решить с помощью альтернативных методов разложения, описанных в следующих разделах.
5.8.3.1. Разложение без ограничений
Стандартный алгоритм SVD — это аналитическое решение задачи низкоранговой аппроксимации. Однако эту проблему можно рассматривать как задачу оптимизации, и к ней также можно применить универсальные методы оптимизации. Один из самых простых подходов заключается в использовании метода градиентного спуска для итеративного уточнения значений скрытых факторов. Отправной точкой является определение функции стоимости J как остаточной ошибки прогноза:
![image](https://habrastorage.org/webt/g8/d_/gk/g8d_gkpksz8-d3wyg0xs9ca60a8.png)
Обратите внимание, что на этот раз мы не накладываем никаких ограничений, таких как ортогональность, на матрицы скрытых факторов. Вычисляя градиент функции стоимости по отношению к скрытым факторам, получаем следующий результат:
![image](https://habrastorage.org/webt/jn/_l/cu/jn_lcurj48vk0kuluh8mojadgcy.png)
где E — матрица остаточных ошибок:
![image](https://habrastorage.org/webt/6z/wt/at/6zwtat7l4h9qoo0fq7ejzatlobi.png)
Алгоритм градиентного спуска минимизирует функцию стоимости, перемещаясь на каждом шаге в отрицательном направлении градиента. Следовательно, можно найти скрытые факторы, минимизирующие квадрат ошибки прогнозирования рейтинга путем итеративного изменения матриц P и Q до сходимости, в соответствии со следующими выражениями:
![image](https://habrastorage.org/webt/f9/uw/gu/f9uwguspa118fw__nuchwxu1ycy.png)
где α — скорость обучения. Недостатком метода градиентного спуска является необходимость вычисления всей матрицы остаточных ошибок и одновременного изменения всех значений скрытых факторов в каждой итерации. Альтернативным подходом, который, возможно, лучше подходит для больших матриц, является стохастический градиентный спуск [Funk, 2016]. Алгоритм стохастического градиентного спуска использует тот факт, что общая ошибка прогноза J является суммой ошибок для отдельных элементов матрицы рейтингов, поэтому общий градиент J можно аппроксимировать градиентом в одной точке данных и изменять скрытые факторы поэлементно. Полная реализация этой идеи показана в алгоритме 5.1.
![image](https://habrastorage.org/webt/le/c5/ct/lec5ctumggjq0twtb30wnamvj0g.png)
Первый этап алгоритма — инициализация матриц скрытых факторов. Выбор этих начальных значений не очень важен, но в данном случае выбрано равномерное распределение энергии известных рейтингов среди случайно сгенерированных скрытых факторов. Затем алгоритм последовательно оптимизирует размерности понятия. Для каждого измерения он многократно выполняет обход всех рейтингов в обучающем наборе, прогнозирует каждый рейтинг с использованием текущих значений скрытых факторов, оценивает ошибку и корректирует значения факторов в соответствии с выражениями 5.101. Оптимизация измерения завершается по выполнении условия сходимости, после чего алгоритм переходит к следующему измерению.
Алгоритм 5.1 помогает преодолеть ограничения стандартного метода SVD. Он оптимизирует скрытые факторы, циклически перебирая отдельные точки данных, и тем самым избегает проблем с отсутствующими рейтингами и алгебраическими операциями с гигантскими матрицами. Итерационный подход также делает стохастический градиентный спуск более удобным для практических приложений, чем градиентный спуск, который изменяет целые матрицы с помощью выражений 5.101.
ПРИМЕР 5.6
По сути, подход на основе скрытых факторов — это целая группа методов обучения представлениям, способных выявлять закономерности, неявно присутствующие в матрице рейтингов, и представлять их явно в виде понятий. Иногда понятия имеют вполне осмысленную интерпретацию, особенно высокоэнергетические, хотя это не означает, что все понятия всегда имеют осмысленное значение. Например, применение алгоритма разложения матриц к базе данных рейтингов фильмов может создать факторы, приблизительно соответствующие психографическим измерениям, таким как мелодрама, комедия, фильм ужасов и т. д. Проиллюстрируем это явление небольшим числовым примером, который использует матрицу рейтингов из табл. 5.3:
![image](https://habrastorage.org/webt/xw/6a/vu/xw6avuizjd2x8aku8k-0r89ieem.png)
Сначала вычтем глобальное среднее μ = 2,82 из всех элементов, чтобы центрировать матрицу, а затем выполним алгоритм 5.1 с k = 3 скрытыми измерениями и скоростью обучения α = 0,01, чтобы получить следующие две матрицы факторов:
![image](https://habrastorage.org/webt/k-/rr/vd/k-rrvde1sezar3qo0e2vqfb7jh8.png)
Каждая строка в этих матрицах соответствует пользователю или фильму, и все 12 векторов-строк изображены на рис. 5.15. Обратите внимание, что элементы в первом столбце (первый вектор понятий) имеют наибольшие величины, а величины в последующих столбцах постепенно уменьшаются. Это объясняется тем, что первый вектор-понятие захватывает столько энергии сигнала, сколько возможно захватить с помощью одного измерения, второй вектор-понятие захватывает только часть остаточной энергии и т. д. Далее, обратите внимание, что первое понятие можно семантически интерпретировать как ось драма — боевик, где положительное направление соответствует жанру боевика, а отрицательное — жанру драмы. Рейтинги в этом примере имеют высокую корреляцию, поэтому хорошо видно, что первые три пользователя и первые три фильма имеют большие отрицательные значения в первом векторе-понятии (фильмы-драмы и пользователи, которым нравятся такие фильмы), тогда как три последних пользователя и три последних фильма имеют большие положительные значения в одном и том же столбце (боевики и пользователи, которые предпочитают этот жанр). Второе измерение в данном конкретном случае соответствует в основном смещению пользователя или элемента, которое можно интерпретировать как психографический атрибут (критичность суждений пользователя? популярность фильма?). Остальные понятия можно рассматривать как шум.
![image](https://habrastorage.org/webt/z0/s6/t9/z0s6t9vbnwdtgonx0p6rswo_ufe.png)
Полученные матрицы факторов не являются полностью ортогональными по столбцам, но стремятся к ортогональности, потому что это следует из оптимальности решения SVD. Это можно увидеть, рассматривая произведения PTP и QTQ, которые близки к диагональным матрицам:
![image](https://habrastorage.org/webt/pb/zr/sf/pbzrsfbqm0hjvmoqgh1xlurslnm.png)
Матрицы 5.103 по сути являются предиктивной моделью, которую можно использовать для оценки как известных, так и отсутствующих рейтингов. Оценки можно получить путем умножения двух факторов и добавления обратно глобального среднего:
![image](https://habrastorage.org/webt/qg/du/d2/qgdud2i8fqm_ut6doi-8jnpllq8.png)
Результаты достаточно точно воспроизводят известные и предсказывают недостающие рейтинги в соответствии с интуитивными ожиданиями. Точность оценок можно увеличивать или уменьшать, изменяя число измерений, а оптимальное число измерений можно определить на практике путем перекрестной проверки и выбора разумного компромисса между вычислительной сложностью и точностью.
» Более подробно с книгой можно ознакомиться на сайте издательства
» Оглавление
» Отрывок
Для Хаброжителей скидка 25% по купону — Машинное обучение
По факту оплаты бумажной версии книги на e-mail высылается электронная книга.