еуые. Лекция 2. 2. лекция. Модельные методы

• Название: 2. лекция. Модельные методы
• Дата: 09.12.2021
• Размер: 0.5 Mb.
• Имя файла: Лекция 2.pdf
• Тип: Лекция; #297880

1
2. ЛЕКЦИЯ. Модельные методы
Несмотря на легкость понимания и реализации анамнестических методов, у них есть ряд недостатков. Во-первых, возникают трудности при прогнозе предпочтений для новых пользователей или при появлении новых элементов, т.к. для них еще нет оценок («холодный старт»). Во-вторых, для расчета предпочтений необходимо хранить всю матрицу данных. В-третьих, ограничивается возможность методов при обработке больших объемов данных, т.к. выполнение большого количества операций для вычисления степени похожести затрудняет выдачу рекомендаций в реальном времени. Большой объем матрицы предпочтений затрагивает также проблему избыточности данных. Как правило, пользователи и элементы делятся на группы с аналогичными профилями предпочтений.
Вследствие этого, возникает задача в понижении размерности матрицы оценок. Такие задачи решают методы второй группы модельные методы
(Model-based). Эти методы направлены на поиск закономерностей на основе обучающих данных. Такой подход является комплексным и даёт более точные прогнозы, так как помогает раскрыть скрытые факторы, объясняющие наблюдаемые оценки
В этом случае возможен вариант объединения пользователей (элементов) в кластеры (профили) с помощью некоторого индекса сходства. Элементы и оценки, выставленные пользователями из одного кластера, будут использоваться для вычисления рекомендаций. Кластерные модели лучше масштабируются, т.к. сверяют профиль пользователя с относительно небольшим количеством сегментов, а не с целой пользовательской базой.
Эта задача может быть выполнена на основе разных математических подходов.
Сингулярное разложение
Для уменьшения сложности вычисления степени схожести векторов объектов используется подход понижения размерности матрицы, который основан на разложении матрицы по сингулярным значениям. Это один из методов матричной факторизации.
Суть метода сингулярного разложения матрицы (Singular Value
Decomposition, SVD)
𝐴 ∈ 𝑀(𝑛, 𝑚) с рангом 𝑑 = 𝑟𝑎𝑛𝑘(𝑀) ≤ 𝑚𝑖𝑛(𝑛, 𝑚) в произведение матриц меньшего ранга:
𝐴 = 𝑈𝐷𝑉
𝑇
(2.1) где матрицы
𝑈 ∈ 𝑀(𝑛, 𝑛) и 𝑉 ∈ 𝑀(𝑚, 𝑚) состоят из ортонормальных столбцов, являющихся собственными векторами при ненулевых собственных

2 значениях матрицы
𝐴𝐴
𝑇
и
𝐴
𝑇
𝐴.
Напомним:
Ортогональная матрица – квадратная матрица
𝐴 с вещественными элементами, результат умножения которой на транспонированную матрицу
𝐴
𝑇
равен единичной матрице:
𝐴𝐴
𝑇
= 𝐴
𝑇
𝐴 = 𝐼
или, что эквивалентно, её обратная матрица (которая обязательно существует) равна транспонированной матрице:
𝐴
−1
= 𝐴
𝑇
Формулу сингулярного разложения
𝐴 = 𝑈𝐷𝑉
𝑇
можно переформулировать в геометрических терминах (рис.2.1). Линейный оператор, отображающий элементы пространства
ℝ
𝑚
в элементы пространства
ℝ
𝑛
представим в виде последовательно выполняемых линейных операций вращения, масштабирования (растяжения) и вращения. Число ненулевых элементов на диагонали матрицы
𝐷 есть фактическая размерность матрицы 𝐴.
Рис. 2.1. Геометрический смысл сингулярного разложения
Вверху слева (рис. 2.1) видно, единичный диск (синий цвет) с двумя каноническими единичными векторами. Действие
𝑉
𝑇
(внизу слева) на единичном диске - это просто вращение (против часовой стрелки) на угол
𝛼.
Действие
𝐷 (справа внизу) масштабирует единичный круг по вертикали и горизонтали (вдоль осей координат). Действие U приводит к окончательному повороту с указанными сингулярными значениями
𝜎
1
и
𝜎
2
. Длины
𝜎
1
и
𝜎
2
из полуосей эллипса являются сингулярные значения из
𝐴.
Соответственно:
𝑈 × 𝑈
𝑇
= 𝐼
𝑛
и
𝑉 × 𝑉
𝑇
= 𝐼
𝑚
(2.2)
Столбцы матрицы
𝑈 представляют собой, ортонормальный базис

3 пространства столбцов матрицы
𝐴, а столбцы матрицы 𝑉 – ортонормальный базис пространства строк матрицы
𝐴. 𝐼
𝑛
и
𝐼
𝑚
– единичные вектора.
𝐷 ∈ 𝑀(𝑛, 𝑚)
– диагональная матрица с положительными диагональными элементами
𝜎
1
≥
𝜎
2
… ≥ 𝜎
𝑑
≥ 0, отсортированного в порядке убывания (рис. 2.2).
𝐷 = (
𝜎
1 0
0 0
…
0 0
0 𝜎
𝑑
)
(2.3)
Рис. 2.2. SVD – сингулярное разложение
С использованием свойств (2), можно получить следующие соотношения:
𝐴𝐴
𝑇
𝑈
𝑖
= 𝜎
𝑖
2
𝑈
𝑖
; 𝑖 = 1, … , 𝑚
(2.4) где
𝑈
𝑖
– столбцы матрицы
𝑈, 𝜎
𝑖
2
– квадраты соответствующих значений на диагонали матрицы
𝐷.
Векторно-матричное выражение (2.3) представляет собой решение задачи нахождения собственных чисел
𝜎
𝑖
2
и собственных векторов
𝑈
𝑖
матрицы
𝐴𝐴
𝑇
. В результате получаем, что сингулярные числа
𝜎
𝑖
2
(𝑖 = 1, … , 𝑚) представляют собой решения характеристического уравнения
𝑑𝑒𝑡(𝜎
𝑖
2
𝐼 − 𝐴𝐴
𝑇
) = 0
(2.5)
Также можно получить зеркальные соотношения:
𝐴
𝑇
𝐴𝑉
𝑖
= 𝜎
𝑖
2
𝑉
𝑖
; 𝑖 = 1, … , 𝑚
(2.6) где
𝑉
𝑖
– столбцы матрицы
𝑉, 𝜎
𝑖
2
– квадраты соответствующих значений на диагонали матрицы D.
В свою очередь, по аналогии с (4), векторно-матричное выражение (2.6) представляет собой полное решение задачи нахождения собственных чисел
𝜎
𝑖
2
и собственных векторов
𝑉
𝑖
матрицы
𝐴
𝑇
𝐴. В результате получаем, что 𝜎
𝑖
2
(𝑖 =
1, … , 𝑚) представляют собой решения характеристического уравнения
𝑑𝑒𝑡(𝜎
𝑖
2
𝐼 − 𝐴
𝑇
𝐴) = 0
(2.7)
При конструировании сингулярного разложения произвольной
(𝑛, 𝑚) - матрицы
𝐴 ранга 𝑑 следует придерживаться следующего порядка действий.
1.
Составить матрицу
𝐴
𝑇
𝐴 и характеристический полином этой матрицы. Найти сингулярные числа матрицы
𝐴 и составить (𝑛, 𝑚)-матрицу 𝐷.
Рассмотрим следующий пример:

4
Пусть имеется таблица 2.1 с тестом мужчин о предпочтении к музыкальным направлениям. Индексы строк – это имена меломанов, а индексы столбцов – виды направлений в музыке.
Таблица 2.1
классика джаз регги рок
Рома
1 1
0 1
Витя
0 1
1 1
Вова
0 0
0 1
Задача состоит в том, чтобы аппроксимировать значения ячеек, где стоят нули. Иными словами необходимо получить новые знания о данных по предложенному тесту.
Составим сингулярное разложение для матрицы:
𝐴 = (
1 0 0 1 0 1 0 1 0 0 1 1
)
Решение. Для матрицы
𝐴 имеем:
𝐴
𝑇
𝐴 = (
1 0 0 0 1 0 0 0 1 1 1 1
) × (
1 0 0 1 0 1 0 1 0 0 1 1
) = (
1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 3
)
Составим характеристическое уравнение. Записываем определитель матрицы, вычитая при этом «
𝜆» из чисел главной диагонали:
|
1 − 𝜆 0 0 1 0 1 − 𝜆 0 1 0 0 1 − 𝜆 1 1 1 1 3 − 𝜆
| = 0
Определитель представляет собой характеристический многочлен. В раскрытом виде он записывается так:
𝜆
4
− 6𝜆
3
+ 9𝜆
2
− 4𝜆 = 0
Представим альтернативную запись уравнения, разбив на множители.
𝜆(𝜆 − 4)(𝜆 − 1)
2
= 0
Тогда корни уравнения:
𝜆
1
= 4; 𝜆
2
= 𝜆
3
= 1; 𝜆
4
= 0
Исходя из уравнения 2.7
𝜎
1
= √𝜆
1
= 2; 𝜎
2
= 𝜎
3
= √𝜆
2
= √𝜆
3
= 1; 𝜎
4
= 0 .
Тогда
𝐷 = (
2 0 0 0 0 1 0 0 0 0 1 0
)

5 2.
Построить ортонормированную систему собственных векторов
𝑒
1
, 𝑒
2
, … , 𝑒
𝑛
оператора с матрицей
𝐴
𝑇
𝐴 , принадлежащих соответственно собственным значениям
𝜆
1
, 𝜆
2
, 𝜆
3
, 𝜆
4
. Из столбцов координат этих векторов составить матрицу
𝑉.
Составим систему уравнений из строк характеристического уравнения.
(𝐴
𝑇
𝐴 − 𝜆𝐼)𝑥
𝑛
= 0
Тогда
{
(1 − 𝜆)𝑥
1
+ 𝑥
4
= 0
(1 − 𝜆)𝑥
2
+ 𝑥
4
= 0
(1 − 𝜆)𝑥
3
+ 𝑥
4
= 0
𝑥
1
+ 𝑥
2
+ 𝑥
3
+ (3 − 𝜆)𝑥
4
= 0
При
𝜆
1
= 4 получаем
{
−3𝑥
1
+ 𝑥
4
= 0
−3𝑥
2
+ 𝑥
4
= 0
−3𝑥
3
+ 𝑥
4
= 0
𝑥
1
+ 𝑥
2
+ 𝑥
3
− 𝑥
4
= 0
Придавая переменным «
𝑥
𝑛
» произвольные значения, получаем бесконечно много собственных векторов. Все они будут коллинеарны друг другу, и поэтому нам достаточно указать один из них.
𝑢̅ = (𝑥
1
, 𝑥
2
, … , 𝑥
𝑛
)
𝑇
Пусть
𝑥
1
= 1 , 𝑥
2
= 1 , 𝑥
3
= 1 , тогда 𝑥
4
= 3 . Таким образом, находим первый собственный вектор:
𝑢̅
1
= (1,1,1,3)
𝑇
При
𝜆
2
= 𝜆
3
= 1 получаем
{
𝑥
4
= 0
𝑥
4
= 0
𝑥
4
= 0
𝑥
1
+ 𝑥
2
+ 𝑥
3
+ 2𝑥
4
= 0
Здесь
𝑥
4
= 0 . Тогда возможны следующие варианты собственных векторов:
𝑢̅
2
= (1, −1,0,0)
𝑇
; 𝑢̅
3
= (1,1, −2,0)
𝑇
При
𝜆
4
= 0 получаем
{
𝑥
1
+ 𝑥
4
= 0
𝑥
2
+ 𝑥
4
= 0
𝑥
3
+ 𝑥
4
= 0
𝑥
1
+ 𝑥
2
+ 𝑥
3
+ 3𝑥
4
= 0
Пусть
𝑥
1
= 1, 𝑥
2
= 1, 𝑥
3
= 1, тогда 𝑥
4
= −1. Таким образом, находим последний собственный вектор:

6
𝑢̅
4
= (1,1,1, −1)
𝑇
Нормируем все полученные вектора, согласно формуле:
𝑒
𝑛
=
𝑢
𝑛
‖𝑢
𝑛
‖
Тогда используя норма Фробениуса (норма Фробениуса, или евклидова норма представляет собой частный случай нормы для
𝑝 = 2):
𝑒
1
=
1
√1 2
+ 1 2
+ 1 2
+ 3 2
(1,1,1,3)
𝑇
=
1 2√3
(1,1,1,3)
𝑇
𝑒
2
=
1
√1 2
+ (−1)
2
+ 0 2
+ 0 2
(1, −1,0,0)
𝑇
=
1
√2
(1, −1,0,0)
𝑇
𝑒
3
=
1
√1 2
+ 1 2
+ (−2)
2
+ 0 2
(1,1, −2,0)
𝑇
=
1
√6
(1,1, −2,0)
𝑇
𝑒
4
=
1
√1 2
+ 1 2
+ 1 2
+ (−1)
2
(1,1,1, −1)
𝑇
=
1 2
(1,1,1, −1)
𝑇
Из столбцов координат векторов
𝑒 составим матрицу
𝑉 =
(
1 2√3 1
√2 1
√6 1
2 1
2√3
−
1
√2 1
√6 1
2 1
2√3 0 −
2
√6 1
2 3
2√3 0 0 −
1 2 )
3.
Построить ортонормированную систему векторов
𝑓
1
=
𝐴𝑒
1
𝜎
1
, … , 𝑓
𝑟
=
𝐴𝑒
𝑟
𝜎
𝑟
и дополнить ее любыми векторами до ортонормированного базиса пространства. Из столбцов координат векторов составить матрицу
𝑈.
Далее строим векторы
𝑓
1
=
𝐴𝑒
1
𝜎
1
=
1 2
(
1 0 0 1 0 1 0 1 0 0 1 1
)
1 2√3
(
1 1
1 3
) =
1
√3
(
1 1
1
)
𝑓
2
=
𝐴𝑒
2
𝜎
2
= (
1 0 0 1 0 1 0 1 0 0 1 1
)
1
√2
(
1
−1 0
0
) =
1
√2
(
1
−1 0
)

7
𝑓
3
=
𝐴𝑒
3
𝜎
3
= (
1 0 0 1 0 1 0 1 0 0 1 1
)
1
√6
(
1 1
−2 0
) =
1
√6
(
1 1
−2
)
Из столбцов координат векторов
𝑓
1
, 𝑓
2
, 𝑓
3
, составим матрицу.
𝑈 =
(
1
√3 1
√2 1
√6 1
√3
−
1
√2 1
√6 1
√3 0 −
2
√6 )
4.
Записать искомое сингулярное разложение .
𝐴 = 𝑈𝐷𝑉
𝑇
𝐴 =
(
1
√3 1
√2 1
√6 1
√3
−
1
√2 1
√6 1
√3 0 −
2
√6 )
(
2 0 0 0 0 1 0 0 0 0 1 0
)
(
1 2√3 1
2√3 1
2√3 3
2√3 1
√2
−
1
√2 0 0 1
√6 1
√6
−
2
√6 0
1 2
1 2
1 2
−
1 2
)
Важным свойством SVD-разложения является тот факт, что если для
𝑘 <
𝑑 преобразовать матрицу 𝐷 в матрицу
𝐷
𝑘
= (
𝜎
1 0
0 0
…
0 0
0 𝜎
𝑘
) ∈ 𝑀(𝑘, 𝑘) состоящую только из
𝑘 наибольших диагональных элементов, а также оставить в матрице
𝑈 и 𝑉 только 𝑘 первых столбцов, т.е. преобразовать их в 𝑈
𝑘
∈
𝑀(𝑛, 𝑘) и 𝑉
𝑘
∈ 𝑀(𝑚, 𝑘), то матрица (рис. 2.3)
𝐴
𝑘
= 𝑈
𝑘
𝐷
𝑘
𝑉
𝑘
𝑇
Рис. 2.3. Аппроксимация сингулярного разложения будет являться лучшей аппроксимации матрицы
𝐴 относительно нормы
Фробениуса среди всех матриц с рангом
𝑘 , т.е. ‖𝐴 − 𝐴
𝑘
‖ ≤ ‖𝐴 − 𝐴
′
‖ ∀ 𝐴
′
∈
𝑀(𝑛, 𝑚) rank (𝐴
′
) = 𝑘

8
Данные факторы являются как раз характеристикой вкусов и предпочтений пользователя – для матрицы
𝑈 и характеристикой самих объектов – для матрицы
𝑉.
Это усечение одновременно достигает двух целей. Во-первых, оно уменьшает размерность векторного пространства, снижает требования хранения и вычислительные требования к модели. Во-вторых, отбрасывая малые сингулярные числа, малые искажения в результате шума в данных удаляются, оставляя только самые сильные эффекты и тенденции в этой модели. Снижение воздействия шума улучшает способность предоставлять высококачественные рекомендации.
Тогда зафиксируем некоторое число скрытых факторов
𝑘 = 2 (для нашего примера), которое, так или иначе, описывает каждый элемент и предпочтения каждого меломана относительно этих факторов. Можно подбирать
𝑘, исходя из размера сингулярных значений матрицы, т.е. тех самых диагональных элементов матрицы
𝐷
𝑘
: желательно отбрасывать как можно более маленькие значения элементов.
𝐷
2
= (2 0 0 1
)
Сингулярные значения показывают значимость факторов (табл. 2.1)
𝑓
1
𝑓
2
𝑓
1 2 0
𝑓
2 0 1
Теперь рассмотрим матрицу
𝑉
2
𝑇
𝑉
3
𝑇
=
(
1 2√3 1
2√3 1
2√3 3
2√3 1
√2
−
1
√2 0 0
)
≈ (
0,288 0,288 0,288 0,866 0,707 −0,707 0 0
)
Так как определено 2 фактора – это будут индексы строк, а индексы столбцов относятся к направлениям в музыке (табл.).
Таблица 2.2 классика джаз регги рок
𝑓
1 0,288 0,288 0,288 𝟎, 𝟖𝟔𝟔
𝑓
2
𝟎, 𝟕𝟎𝟕−0,707 0
0
Каждый фактор (строка) состоит из 2 значений, каждое из которых определено принадлежностью (весом) к каждой из 4 музыкальных направлений. Логично будет судить фактор за максимальный вес по направлениям. Таким образом,
𝑓
1
имеет максимальное значение
0,866 в секторе

9
«рок»,
𝑓
2
–
0,707 в секторе «классика».
Тогда для понимания можно факторам дать название, которое будет обусловлено психологий музыкальных предпочтений. Многие психологи утверждают, что предпочтения в направлении музыкальных композиций определяют характер человека. Тогда исходя из данной информации можно охарактеризовать человека с иных позиций:
𝑓
1
– склонность к творчеству (Любители рока вопреки бытующему мнению, они обладают чрезвычайно мягким и даже утонченным характером.
Это творческие люди, но, как правило, с довольно низкой самооценкой);
𝑓
2
–целеустремленность (Люди, которые предпочитают слушать классическую музыку постоянно стремятся вырваться вперёд, любят работать над собой в различных сферах жизни);
Таким образом, помимо рекомендаций мы «бонусом» получили выполненную задачу классификации без учителя.
Теперь рассмотрим матрицу
𝑈
2
:
𝑈
3
=
(
1
√3 1
√2 1
√3
−
1
√2 1
√3 0
)
≈ (
0,577 0,707 0,577 −0,707 0,577 0
)
На основании матрицы составим таблицу 2.3
Таблица 2.3
𝑓
1
𝑓
2
Рома
0,577 0,707
Витя
0,577
−0,707
Вова
0,577 0
В общем случае рекомендательных систем получается, что мы представляем каждого пользователя вектором из
𝑓 факторов 𝑈
𝑖
, а каждый продукт – вектором из
𝑓 факторов 𝑉
𝑗
. Представляем каждого пользователя вектором из
𝑘 факторов 𝑟
𝑢
и каждый продукт вектором из
𝑘 факторов 𝑟
𝑖
, чтобы предсказать рейтинг пользователя
𝑢 товару 𝑖 , вычисляем их скалярное произведение:
𝑟̇
𝑢,𝑖
= 𝑟
𝑖
× 𝑟
𝑢
= 𝑟
𝑖
𝑇
× 𝑟
𝑢
Вектор факторов пользователя показывает, насколько пользователю нравится или не нравится тот или иной фактор, а вектор факторов продукта показывает, насколько тот или иной фактор в продукте выражен.

10
Тогда в нашей задаче рассмотрим, как каждый исследуемый относится к классической музыке. Узнаем, насколько выражена целеустремленность в каждом рассматриваемом человеке:
Рассчитаем скалярное произведение векторов Классика/Рома
𝑟̇
1,1
= (0,288 0,707)
𝑇
(0,577 0,707)
= 0,288 × 0,577 + 0,707 × 0,707 = 0,166 + 0,5 = 0,666
𝑟̇
2,1
= (0,288 −0,707)
𝑇
(0,577 0,707)
= 0,288 × 0,577 − 0,707 × 0,707 = 0,166 − 0,5 = −0,334
𝑟̇
3,1
= (0,288 0)
𝑇
(0,577 0,707) = 0,288 × 0,577 = 0,166
𝑟̇
4,1
= (0,866 0)
𝑇
(0,577 0,707) = 0,866 × 0,577 = 0,511
Роман явно является приверженцем к классической музыке и определен фактором
𝑓
2
–целеустремленность, но ему, возможно, нравится направление рок –
𝑓
1
(склонность к творчеству).
Аналогично, рассматриваются остальные скалярные произведения векторов. При этом некоторые факторы легко будет понять человеческим разумом, которые будут показывать, насколько соответствующие характеристики объекта по вкусу пользователям. Но может и не выделиться ничего содержательного – гарантий нет, формально просто используется линейная алгебра.
Составим матрицу:
𝐴
2
≈ (
0,666
−0,334 0,166 0,511
−0,334 0,666 0,166 0,511 0,166 0,166 0,166 0,511
)
Тогда составим табл.2.4
Таблица 2.4 классика джаз регги рок
Рома
0,666
−0,334 0,166 0,511
Витя
−0,334 0,666 0,166 0,511
Вова
0,166 0,166 0,166 0,511
Таким образом, классическая музыка может быть предложена Роману с долей успеха
0,666 и Владимиру джаз с долей успеха 0,666 . Аналогичные рассуждения можно привести по другим направлениям музыки.
Однако, в реальной системе подобная матрица будет иметь относительно небольшое число ненулевых элементов (сильноразреженная) – это значит, что далеко не все пользователи оценили объекты, и, соответственно, не все объекты будут оценены, т.е. большая часть оценок заранее неизвестна. Кроме того,

11 алгоритм SVD-разложения является довольно трудоёмким, поэтому невозможно производить такие вычисления набольших объёмах.
Измерение качества рекомендаций
Существует достаточное количество метрик (оценка качества) для тестирования рекомендательных систем. На данный момент не существует единой метрики. Каждый тестировщик подбирает метрику под свои цели.
Для тестирования качества прогнозирования оценок в рекомендательных системах используются метрики:
MAE – Mean Absolute Error – средняя абсолютная ошибка (2.8)
𝑴𝑨𝑬 =
𝟏
|𝑫|
∑ |𝒓̂
𝒖𝒊
− 𝒓
𝒖𝒊
|
(𝒖,𝒊)∈𝑫
(2.8)
MSE – Mean Squared Error – среднеквадратичная ошибка (2.9)
𝑴𝑺𝑬 =
𝟏
|𝑫|
∑ (𝒓̂
𝒖𝒊
− 𝒓
𝒖𝒊
)
𝟐
(𝒖,𝒊)∈𝑫
(2.9)
RMSE – Root Mean Squared Error – корень среднеквадратичной ошибки
(2.10)
𝑹𝑴𝑺𝑬 = √
𝟏
|𝑫|
∑ (𝒓̂
𝒖𝒊
− 𝒓
𝒖𝒊
)
𝟐
(𝒖,𝒊)∈𝑫
(2.10) где для всех формул:
|D| – размер набора данных;
𝑟̂
𝑢𝑖
–предсказанная оценка пользователя u фильму i;
𝑟
𝑢𝑖
– действительная оценка, поставленная пользователем u фильму i.
Эти метрики показывают на сколько ошибается модель при прогнозировании оценок.
Алгоритм Funk SVD
Множество записей в матрице предпочтений могут отсутствовать, и обычный SVD имеет следующие проблемы: a) пропущенные значения могут оказать нежелательное влияние на результат. b) вычислительная сложность для обучения может быть высокой со всеми рассмотренными записями.
Поскольку SVD может достичь очень хорошего результата только на не разрежённых данных (имеются в виду данные без пропущенных значений).
Фактически, реальный набор данных для механизма рекомендаций может быть очень разреженным, можно найти матрицы пользовательских элементов со

12 значениями NaN (англ. Not-a-Number, «не число» — одно из особых состояний
числа с плавающей запятой) более 95%.
Для этих задач Саймон Фанк придумал регуляризированный SVD алгоритм, который на конкурсе Netflix Prize занял одно из призовых мест. В алгоритме Funk SVD (Funk MF – Matrix Factorization, Факторизация матрицы) не применяется разложение по сингулярным значениям, это подобие SVD- модели машинного обучения. Прогнозируемые рейтинги могут быть вычислены как
𝑅̃ = 𝐻𝑊 𝑅̃ ∈ ℝ
𝑢𝑠𝑒𝑟𝑠×𝑖𝑡𝑒𝑚𝑠
где
𝐻 ∈ ℝ
𝑢𝑠𝑒𝑟𝑠×𝑙𝑎𝑡𝑒𝑛𝑡 𝑓𝑎𝑐𝑡𝑜𝑟𝑠
– матрица рейтингов пользовательских элементов, содержащая скрытые факторы пользователя и
𝑊 ∈ ℝ
𝑙𝑎𝑡𝑒𝑛𝑡 𝑓𝑎𝑐𝑡𝑜𝑟𝑠×𝑖𝑡𝑒𝑚𝑠
– скрытые факторы элемента.
Прогнозируемая оценка, которую пользователь
𝑢 поставит элементу 𝑖 , вычисляется как:
𝑟̃
𝑢𝑖
=
∑
𝐻
𝑢,𝑓
𝑛 𝑓𝑎𝑐𝑡𝑜𝑟𝑠
𝑓=0
𝑊
𝑓,𝑖
Необходимо учитывать, что увеличение количества скрытых факторов улучшит персонализацию, следовательно, качество рекомендаций, до тех пор, пока количество факторов не станет слишком большим, после чего модель начнет переобучаться, и качество рекомендаций снизится. Распространенной стратегией, позволяющей избежать переобучения, является добавление членов регуляризации к целевой функции. Алгоритм Саймона Фанка был разработан как задача прогнозирования рейтингов, поэтому он использует явные числовые рейтинги в качестве взаимодействий между пользователем и элементом.
Учитывая все обстоятельства, алгоритм минимизирует следующую целевую функцию:
𝑎𝑟𝑔 𝑚𝑖𝑛
𝐻,𝑊
‖𝑅 − 𝑅̃‖
𝐹
+ 𝛼‖𝐻‖ + 𝛽‖𝑊‖ где
‖𝑅 − 𝑅̃‖
𝐹
определяется как норма Фробениуса (евклидова норма представляет собой частный случай нормы для
𝑝 = 2 ). Но могут использоваться другие нормы в зависимости от конкретной рекомендующей задачи.
Рассмотрим пример реализации алгоритма Саймона Фанка, который должен проигнорировать пропущенные значения и найти способ вычисления скрытых факторов только с использованием известных нам значений.
Пусть имеется матрица User-Item (Пользователь-Объект) табл. 2.5.

13
Таблица 2.5
О1
О2
О3
О4
П1
NaN
NaN
9 1
П2 3
NaN
7
NaN
П3 5
NaN
NaN
10
П4
NaN
2
NaN
NaN
Чтобы достичь результата в подходе матричной факторизации с Funk
SVD, необходимо выполнить следующие шаги:
1.
Построить матрицы
𝑈 и 𝑉
𝑇
, соответственно матрицу пользователей по количеству выбранных скрытых факторов (
𝐹) и матрицу этих же скрытых факторов по объекту. Заполните эти матрицы случайными числами.
Таблица 2.6. Матрица
𝑈
(Пользователь по скрытым факторам, заполненный случайными значениями)
F1
F2
F3
П1 0,8 1,2
-0,2
П2 2
1,8 0,4
П3 0,8 3
0,1
П4 1
0,8 2,4
Таблица 2.7. Матрица
𝑉
𝑇
(Скрытые факторы по объектам, заполненным случайными значениями)
О1
О2
О3
О4
F1
-1,8 1
-0,2 1
F2 0,5 1,2 0,1 5
F3 1,4 4
0,14 2
2.
Найти в матрице «Пользователь-Объект» существующую ставку для одной пары «пользователь-объект».
Таблица 2.8
О1
О2
О3
О4
П1
NaN
NaN
9 1
П2 3
NaN
7
NaN
П3 5
NaN
NaN
10
П4
NaN
2
NaN
NaN
Первая найденная оценка – 9, присвоенная пользователем 1 пункту 3.
Итак, 9 – это наше фактическое значение, истинное значение.
3.
В матрице
𝑈 берутся все случайные значения, связанные с

14 пользователем П1 (первая строка, табл. 2.9). У нас есть для этого пользователя
[0.8, 1.2, -0.2]
Таблица 2.9
F1
F2
F3
П1 0,8 1,2
-0,2
П2 2
1,8 0,4
П3 0,8 3
0,1
П4 1
0,8 2,4
Помните, что 9 было присвоено пользователем 1 элементу 3. В матрице
𝑉
𝑇
берутся все случайные значения, связанные с элементом 3. У нас есть для этого элемента
[−0,2, 0,1, 0,14]
𝑇
(табл. 2.10).
Таблица 2.10
О1
О2
О3
О4
F1
-1,8 1
-0,2 1
F2 0,5 1,2 0,1 5
F3 1,4 4
0,14 2
4.
Вычисляется скалярное произведение между найденной строкой и столбцом, чтобы сделать наш прогноз.
𝑟
13
= 𝑢
1
𝑣
3
= (0,8 × −0,2) + (1,2 × 0,1) + (−0,2 × 0,14) = −0,07
Имеем: Фактическое
𝑟̂
13
= 9; Прогнозируемый 𝑟
13
= −0,07
Таким образом, среднеквадратичная ошибка составляет:
𝑒
13
= (𝑟̂
13
− 𝑟
13
)
2
= 0,5 × (9 − (−0,07))
2
= 41,13 5.
Необходимо минимизировать ошибку, используя градиентный спуск.
Для пользователя:
𝑈
𝑖
∗
= 𝑈
𝑖
+ 𝛼∇𝑒
𝑖
𝑉
𝑖
= 𝑈
𝑖
+ 𝛼∇(𝑟̂
𝑖
− 𝑟
𝑖
)
2
𝑉
𝑖
= 𝑈
𝑖
+ 𝛼2(𝑟̂
𝑖
− 𝑟
𝑖
)𝑉
𝑖
где
𝑈
𝑖
∗
– обновленное значение пользователя по скрытым факторам;
𝑈
𝑖
– случайное значение пользователя по скрытым факторам;
∇𝑒
𝑖
– градиент функции ошибки;
𝑉
𝑖
– случайное значение скрытых факторов по объектам.
Для объектов:
𝑉
𝑖
∗
= 𝑉
𝑖
+ 𝛼2(𝑟̂
𝑖
− 𝑟
𝑖
)𝑈
𝑖
где
𝑉
𝑖
∗
– обновленное значение скрытых факторов по объектам;
𝑉
𝑖
– случайное значение скрытых факторов по объектам;

15
∇𝑒
𝑖
– градиент функции ошибки;
𝑈
𝑖
– случайное значение пользователя по скрытым факторам/
Составим таблицу 2.11 для каких значений необходимо сделать обновления.
Таблица 2.11
F1
F2
F3 для U
0,8 1,2
-0,2 для V
-0,2 0,1 0,14
Обновим значение пользователя по скрытым факторам при
𝛼 = 0,1:
𝑈
1
∗
= 𝑈
1
+ 𝛼2(𝑟̂
13
− 𝑟
13
)𝑉
1
= 0,8 + 0,1 × 2 (9 + 0,07) × −0,2 = 0,44
𝑈
2
∗
= 𝑈
2
+ 𝛼2(𝑟̂
13
− 𝑟
13
)𝑉
2
= 1,2 + 0,1 × 2 (9 + 0,07) × 0,1 = 1,38
𝑈
3
∗
= 𝑈
3
+ 𝛼2(𝑟̂
13
− 𝑟
13
)𝑉
3
= −0,2 + 0,1 × 2 (9 + 0,07) × 0,14 = 0,053
Обновим значение скрытых факторов по объектам
𝑉
1
∗
= 𝑉
1
+ 𝛼2(𝑟̂
13
− 𝑟
13
)𝑈
1
= −0,2 + 0,1 × 2 (9 + 0,07) × 0,8 = 1,25
𝑉
2
∗
= 𝑉
2
+ 𝛼2(𝑟̂
13
− 𝑟
13
)𝑈
2
= 0,1 + 0,1 × 2 (9 + 0,07) × 1,2 = 2,28
𝑉
3
∗
= 𝑉
3
+ 𝛼2(𝑟̂
13
− 𝑟
13
)𝑈
3
= 0,14 + 0,1 × 2 (9 + 0,07) × −0,2 = −0,22
Обновляются все значения из
𝑈 и 𝑉 таблицы 2.11.
Таблица 2.12
F1
F2
F3 для U
0,44 1,38 0,053 для V
1,25 2,28
– 0,22
Соответственно, исправляются значения для матрицы пользователя
𝑈 табл. 2.13.
Таблица 2.13
F1
F2
F3
П1 0,44 1,38 0,053
П2 2
1,8 0,4
П3 0,8 3
0,1
П4 1
0,8 2,4
И заменяются значения для матрицы объектов
𝑉
𝑇
табл. 2.14.
Таблица 2.14
О1
О2
О3
О4
F1
-1,8 1
1,25 1
F2 0,5 1,2 2,28 5
F3 1,4 4
– 0,22 2
6.
Снова вычисляем скалярное произведение между новой строкой и

16 столбцом, чтобы сделать обновленный прогноз.
𝑟
13
′
= 𝑢
1
′
𝑣
3
′
= (0,44 × 1,25) + (1,38 × 2,28) + (0,053 × −0,22)
= 3,58
Тогда имеем: Фактическое
𝑟̂
13
= 9; Прогнозируемое 𝑟
13
′
= 3,58
Таким образом, среднеквадратичная ошибка составляет:
𝑒
13
= (𝑟̂
13
− 𝑟
13
)
2
= 0,5 × (9 − 3,58)
2
=
14,68
Таким образом, за одну итерацию величина ошибки уменьшилась на
41,13 −
14,68 = 26,45.
Таким образом, алгоритм Funk SVD легко позволяет найти способ оценить механизм рекомендаций и создать хорошие матрицы
𝑈 и 𝑉
𝑇
, чтобы давать рекомендации, даже если у нас очень разреженная матрица. Но алгоритм
Funk SVD не следует использовать в одиночку, потому что можно столкнуться с общей проблемой в системе рекомендаций, которая называется «Проблема холодного запуска». Эта проблема означает, что нельзя давать рекомендации новым пользователям или новым объектам.
Алгоритм SVD++
Funk SVD может обеспечить очень хорошее качество рекомендаций, его способность использовать только явные числовые рейтинги в качестве взаимодействий между пользователями и элементами представляет собой ограничение. Современные рекомендательные системы должны использовать все доступные взаимодействия, как явные (например, числовые рейтинги), так и неявные (например, лайки, покупки, пропущенные, добавленные в закладки).
С этой целью SVD ++ также был разработан с учетом неявных взаимодействий, учитывает предвзятость пользователя и элемента.
Пусть стоит задача: по известным оценкам известных продуктов предсказать, насколько хорошо будет оценен новым пользователем каждый продукт.
Введем так называемые базовые предикторы
𝑏
i,a
, которые складываются из базовых предикторов отдельных пользователей
𝑏
i
, и отдельных продуктов
𝑏
𝑎
, а также просто общего среднего рейтинга по базе
𝜇:
𝑏
𝑖,𝑎
= 𝜇 + 𝑏
i
+ 𝑏
𝑎
, где
𝜇 – средний рейтинг по базе; 𝑏
i
– средний рейтинг каждого
𝑖 пользователя;
𝑏
𝑎
– средний рейтинг каждого
𝑎 продукта.
Для определения только базовых предикторов необходимо найти такие
𝜇,
𝑏
i
,
𝑏
𝑎
, для которых
𝑏
𝑖,𝑎
лучше всего приближают имеющиеся рейтинги. Затем можно будет добавить собственно факторы. Поскольку теперь, когда сделана

17 поправка на базовые предикторы, остатки будут сравнимы между собой, вполне возможно будет получить разумные значения для факторов:
𝑟̇
𝑢𝑖
= 𝜇 + 𝑏
i
+ 𝑏
𝑎
+ 𝑣
𝑎
𝑇
𝑢
𝑖
(2.11) где
𝑣
𝑎
– вектор факторов, представляющий продукт
𝑎; 𝑢
𝑖
– вектор факторов, представляющий пользователя
𝑖.
Теперь можно вернуться к исходной задаче и сформулировать ее точно: нужно найти наилучшие предикторы, которые приближают величину
𝑟̇
𝑢𝑖
Лучшими будут те предикторы, которые дают минимальную среднеквадратичную ошибку, определяемую следующим образом:
𝐿(𝜇, 𝑏
i
, 𝑏
𝑎
, 𝑣
𝑎
, 𝑢
𝑖
) = ∑
(𝑟
𝑖,𝑎
− 𝑟̇
𝑖,𝑎
)
2
(𝑖,𝑎)∈𝐷
= ∑
(𝑟
𝑖,𝑎
− 𝜇 − 𝑏
i
− 𝑏
𝑎
− 𝑣
𝑎
𝑇
𝑢
𝑖
)
2
(𝑖,𝑎)∈𝐷
Функцию
𝐿(𝜇, 𝑏
i
, 𝑏
𝑎
, 𝑣
𝑎
, 𝑢
𝑖
) минимизируем градиентным спуском: берем частные производные по каждому аргументу и двигаемся в сторону, обратную направлению этих частных производных.
Для компенсирования эффекта переобучения добавляется параметр регуляризации. Иными словами, накладывается штраф за слишком большие значения обучаемых переменных. Например, можно просто добавить в функцию ошибки сумму квадратов всех факторов и предикторов. В результате функция ошибки выглядит как
𝑏
∗
, 𝑣
∗
, 𝑢
∗
= 𝑎𝑟𝑔 𝑚𝑖𝑛
𝑏,𝑝,𝑔
∑
(𝑟
𝑖,𝑎
− 𝜇 − 𝑏
i
− 𝑏
𝑎
− 𝑣
𝑎
𝑇
𝑢
𝑖
)
2
(𝑖,𝑎)
+ 𝜆(∑ 𝑏
𝑖
2
𝑖
+
∑ 𝑏
𝑎
2
𝑎
+ ‖𝑣
𝑎
‖
2
+ ‖𝑢
𝑖
‖
2
),
(2.12)
Если взять у функции ошибки в формуле (2) частные производные по каждой из оптимизируемых переменных, получим простые правила для градиентного (стохастического) спуска:
𝑏
𝑖
= 𝑏
𝑖
+ 𝛾(𝑒
𝑖,𝑎
− 𝜆𝑏
𝑖
),
𝑏
𝑎
= 𝑏
𝑎
+ 𝛾(𝑒
𝑖,𝑎
− 𝜆𝑏
𝑎
),
𝑣
𝑎,𝑗
= 𝑣
𝑎,𝑗
+ 𝛾(𝑒
𝑖,𝑎
𝑢
𝑖,𝑗
− 𝜆𝑣
𝑎,𝑗
),
𝑢
𝑖,𝑗
= 𝑢
𝑖,𝑗
+ 𝛾(𝑒
𝑖,𝑎
𝑣
𝑎,𝑗
− 𝜆𝑢
𝑖,𝑗
) для всех
𝑗, где 𝑒
𝑖,𝑎
= 𝑟
𝑖,𝑎
− 𝑟̇
𝑖,𝑎
,
𝑎 — ошибка на данном тестовом примере, а
𝛾 — скорость обучения.