Рекомендательные системы: SVD на perl

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


Итак, SVD на Perl. Готовый скрипт, который можно запускать в виде

./svd.pl число_признаков dataset.csv

можно скачать отсюда. Я сейчас просто приведу его часть, которая делает собственно обучение.

# обучение SVD: обучаем, пока не сойдётся
while (abs($old_rmse - $rmse) > 0.00001 ) {
	$old_rmse = $rmse;
	$rmse = 0;
	foreach my $u ( keys %l ) {
		foreach my $v ( keys %{$l{$u}} ) {
			# считаем ошибку
			$err = $l{$u}{$v} - ($mu + $b_u[$u] + $b_v[$v] + dot($u_f[$u], $v_f[$v]) );
			# возводим в квадрат
			$rmse += $err * $err;
			# применяем правила апдейта для базовых предикторов...
			$mu += $eta * $err;
			$b_u[$u] += $eta * ($err - $lambda2 * $b_u[$u]);
			$b_v[$v] += $eta * ($err - $lambda2 * $b_v[$v]);
			# ...и для векторов признаков
			for (my $f=0; $f < $features; ++$f) {
				$u_f[$u][$f] += $eta * ($err * $v_f[$v][$f] - $lambda2 * $u_f[$u][$f]);
				$v_f[$v][$f] += $eta * ($err * $u_f[$u][$f] - $lambda2 * $v_f[$v][$f]);
			}
		}
	}
	++$iter_no;
	# нормируем суммарную ошибку, чтобы получить RMSE
	$rmse = sqrt($rmse / $total);
	print "Iteration $iter_no:\tRMSE=" . $rmse . "\n";
	# если RMSE меняется мало, нужно уменьшить скорость обучения
	if ($rmse > $old_rmse - $threshold) {
		$eta = $eta * 0.66;
		$threshold = $threshold * 0.5;
	}
}

Как видите, совершенно ничего страшного – нужно просто запустить процесс апдейта весов и продолжать его до сходимости. Сходимость определяется по RMSE (root mean squared error) – среднеквадратической ошибке, т.е. корню из сумме квадратов ошибок, поделённой на число тестовых примеров. Мы реализуем стохастический градиентный спуск: после каждого тестового примера мы сразу меняем параметры, а не собираем статистику об ошибке по всей базе.

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

Теперь применим то, что у нас получилось, к матрице рейтингов, которую мы рассматривали в одном из первых текстов.

В подходящем формате его можно скачать здесь (порядок сохранён). После запуска нашего скрипта на этом датасете мы получим примерно следующее.

Read 5 users and 5 urls.
Iteration 1:    RMSE=1.92845291697284
Iteration 2:    RMSE=1.28481736445124
Iteration 3:    RMSE=1.14159530044051
...
Iteration 808:	RMSE=0.0580161117835789
Iteration 809:	RMSE=0.0580061123741253
       mu:	2.54559533638261
User base:	0.7271	0.1626	0.7139	1.9097	-0.9677	
Item base:	0.8450	0.6593	0.2731	0.7328	0.0354	
User features
  user 0:	-0.5087	-0.8326	
  user 1:	1.0220	1.2826	
  user 2:	-0.9509	0.2792	
  user 3:	0.1031	-0.4814	
  user 4:	0.6095	0.0557	
Item features:
  item 0:	-0.8368	0.2511	
  item 1:	1.1101	0.4120	
  item 2:	-0.4159	-0.4073	
  item 3:	-0.3130	-0.9115	
  item 4:	0.6408	1.2205

Что получилось у нас в результате? Примерно то, чего мы и ожидали. Пользователи получили базовые предикторы в соответствии со своей добротой: Петрович оказался злобным зрителем, а остальные, наоборот, добрыми, особенно Жанночка. Фильмы получили базовые предикторы в соответствии с «общим качеством» (выраженным, естественно, через оценки).

Но самое интересное – мы получили разумное разложение оставшихся пользовательских предпочтений на два фактора. Пример, конечно, игрушечный, и в датасете изначально было заложено, что фильмы делятся на фильмы «про поросят» и «про тракторы»; некоторые пользователи больше любят мощную технику, а некоторые – свиной хрящик.

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

Кстати, датасет я специально не подгонял, и в данном случае произошёл забавный случай со знаками: SVD обучил отрицательные значения факторов «про тракторы» для двух пользователей, которым тракторы нравятся, Васи и Валерика. Но вместе с этим SVD обучил отрицательные значения для факторов «про тракторы» у фильмов, которые действительно про тракторы – минус на минус даст плюс. А 1.0220 Петра как раз, наоборот, означает, что тракторы его по сравнению с поросятами совершенно не интересуют…

Мы теперь можем предсказать значение рейтинга Васи для «Трактористов» как

2.5456 + 0.7271 + 0.8450 + (-0.5087)*(-0.8368) + (-0.8326)*0.2511 = 4.3343143.

Что ж, действительно можно было предположить, что «Трактористы» Васе понравятся.

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