15. BI - 推荐系统之 ALS 原理

本文为 「茶桁的 AI 秘籍 - BI 篇 第 15 篇」

[TOC]

Hi，你好。我是茶桁。

上一节课咱们介绍了推荐系统中使用的矩阵分解的原理，讲到最终我们设定了模型目标。

有了机器学习去解这个目标，要用到一些优化的方法。常见的优化方法有两种，一个叫 ALS，交替最小二乘法。还有一个就是 SGD，随机梯度下降。

ALS 求解方法

我们来看看，ALS 是怎样一个原理。交替最小二乘法有点像我们拧螺丝的一个过程，就是固定一边求解另一边。

上一节课中我们有了 user 矩阵和 item 矩阵，12*3的 user 和3*9的 item 这两个矩阵都是未知，都是模型要去求的。一个方程有两个未知，R 是已知。

一个方程有两个未知能依次求解出来吗？如果 item 已经知道了，R 也知道了，把 user 求出来这个很有可能。但是如果 R 知道，user 和 item 都不确定的话一次是不能求解出来的。

那怎么办？我们就要固定一个求解另一个，这叫做交替最小二乘法。

• step1: 固定 Y 优化 X
• step2: 固定 X 优化 Y

重复 step1 和 2，每一次求解过程都是一个收敛的，去拟合参数的过程。

最小二乘法的应用

最小二乘实际上我们都不陌生，在中学期间做过一些物理实验，物理老师就会说我们的实验报告要多次求解。

举个场景，比如要测量一把尺子，这个尺子到底有多长咱们做了 5 次实验，分别是 9.8、9.9、9.8、10.2 和 10.3，那你在写实验报告结论的时候一般就是相加再除上 5，这个叫平均值。

最小乘法是由道尔顿提出来

\[ \begin{align*} E = \sum_{i=1}^n e_i^2 = \sum_{i=1}^n(y_i - \hat y)^2 \end{align*} \]

不采用中位数和几何平均数背后的原理就是因为要求一个导数为 0 的函数。对其进行求导之后，导数为 0 的时候为最小值，因此：

\[ \begin{align*} \frac{d}{dy}\sum_{i=1}^n(y_i-y)^2 = 2\sum_{i=1}^n(y_i - y) = 0 \end{align*} \]

那么继续往下计算就可以得到

\[ \begin{align*} (y_1 - y) + (y_2 - y) + (y_3 - y) + (y_4 - y) + (y_5 - y) = 0 \end{align*} \]

所以，当它最小拟合的过程中就是

\[ \begin{align*} y = \frac{1}{n}\sum_{i=1}^n y_i \end{align*} \]

也就等于 \[ \begin{align*} \frac{y_1+y_2+y_3+y_4+y_5}{5} \end{align*} \]

现在我们知道，物理上做实验，取多次结果最后求平均值其原理就是我们要去求一个导数为 0 的函数极值，也是因为我们的评价标准是最小二乘。

做了五次实验，得到五个数，就是 y1、y2 一直到 y5，是以这个例子为例。n 次实验其实应该是从 y1 一直到 yn。做物理实验做 n 次应该就是这 n 次的 n 分之一。

那现在也是一样的，用的一个叫做交替最小二乘，最小二乘是一种拟合技术，它可以让我们更好的去求这种参数估计。

最小二乘法在计算机产生之前已经变成了一个通用的数学工具，我们来看一下：

在 1889 年，那阵还没有计算机，道尔顿和他的朋友皮尔森收集了上千个家庭的身高、臂长和腿长的记录，企图寻找出儿子们身高与父亲们身高之间关系的具体表现形式。

看到皮尔森大家想到是什么样的内容？皮尔森也是一个统计学家，有个「皮尔森系数」。

那个时候他们也没有一个数据建模机器学习什么的，那他怎么去建模呢？他就认为儿子和父亲之间的关系用一个方程，拟合它就求解这个方程，把这个系数求出来就行了，就是最小二乘。

\[ \begin{align*} y & = a + bx + u \\ \hat y & = 84.33 + 0.516x \end{align*} \]

所以最小二乘就是规定出来了一个标准，然后把这个参数拟合出来，通过导数为 0 的情况下极值来求解出来。这项乘法现在已经是一个重要的拟合技术，不仅仅用于我们刚才看到的线性回归，还在非线性的回归里面去使用。

所以非线性过程中也可以采用最小二乘法来做一个拟合，最小二乘法可以帮你来去拟合这样一个参数。

ALS 求解方法

到底是怎样一个使用过程呢？回到今天使用的 ALS 方法，对矩阵分解来求解一下。

• Step1, 固定 y 优化 x

我们想要去求解这个过程，\(r = x \times y\)，一个方程里面有两个未知数，能一次求解出来吗？求不出来。所以要固定一个求解另一个，如果把 y 固定了，也就是随机的初始一个 y，这个时候 y 是确定值，那么要求解的过程就变成了

\[ \begin{align*} min_{X_u} \sum_{r_{ui} \ne 0}(r_{ui} - x_u^T y_i)^2 + \lambda \sum||x_u||_2^2 \end{align*} \]

原来后面是加了一个 \(y^2\), 因为 y 的平方是个固定的常量，任何的值 y 其实对它都没有影响。所以就把后面这项给它去掉了。那要拟合的话就变成了这个式子，所以要拟合它目标函数就是：

\[ \begin{align*} J(x_u) = (R_u - Y_u^T x_u)^T(R_u - Y_u^T x_u) + \lambda x_u^T x_u \end{align*} \]

转化为矩阵表达形式

$$ \begin{align*} R_u & = [r_