OnePUNCHMan——交替最小二乘推荐算法

注意&＃xff1a;由于k的值很小&＃xff0c;所以这种分解算法只能是一种近似值&＃xff0c;并不是绝对的上述说的等式。

原始的矩阵是低秩的&＃xff0c;也就是稀疏的&＃xff0c;但UV的乘积是却稠密的&＃xff0c;即该矩阵存在较少的非0元素。因此&＃xff0c;该约等式只是一种近似&＃xff0c;原始矩阵大量元素是缺失的&＃xff08;因为缺失&＃xff0c;默认为0&＃xff0c;但可能实际上不为0&＃xff09;&＃xff0c;而算法为原始矩阵补全了大部分缺失值。从这个角度来看&＃xff0c;矩阵分解的算法有时候称为矩阵补全算法。

第三次强调了&＃xff0c;UV的乘积只是尽可能的逼近A&＃xff0c;用数学的话来讲就是无限趋近于A。怎么求解呢&＃xff1f;ALS算法呼之欲出&＃xff01;
首先我们简写前面的公式为下&＃xff1a;
A&＃61;XTYA&＃61;X^{T}YA&＃61;XTY

不幸的是&＃xff0c;上述的A&＃61;XTYA&＃61;X^{T}YA&＃61;XTY 通常没有解&＃xff0c;因为XTYX^{T}YXTY 通常不够大&＃xff01;也就是说&＃xff0c;我们找到的分解矩阵X和Y的阶太小了&＃xff0c;无法完美的表示A。其实这不完全是坏事&＃xff0c;因为A归根到底只是现实中的一个微小样本&＃xff0c;它只是一次观察&＃xff0c;而且是很稀疏的观察。就比如拼图里&＃xff0c;很多拼板都掉了&＃xff0c;虽然拼图最后的图样是一只猫&＃xff0c;但是手上的拼板太少的时候&＃xff0c;就很难看到正确的图案。

所以&＃xff0c;另一个由上述公式推导化为&＃xff1a;
AiY(YTY)−1&＃61;XiA_{i}Y(Y^{T}Y)^{-1}&＃61;X_{i}Ai​Y(YTY)−1&＃61;Xi​
这个公式如何理解呢&＃xff1f;
首先A是已知的&＃xff0c;要求解矩阵$X$和矩阵$Y$。那么根据上述公式&＃xff0c;只需要知道一个另一个通过公式推导也是能够知道的。
比如知道矩阵$Y$&＃xff0c;那么&＃xff0c;因为$X$的第$i$行是根据$A$的第$i$行和$Y$的函数得到的&＃xff0c;所以只需要根据上述公式&＃xff0c;一行一行求出$X$即可。
要想两边精确相等是不可能的&＃xff0c;因此&＃xff0c;实际的目的是最小化的∣AiY(YTY)−1−Xi∣|A_{i}Y(Y^{T}Y)^{-1}-X_{i}|∣Ai​Y(YTY)−1−Xi​∣ &＃xff0c;或者是最小的矩阵平方误差&＃xff0c;这也是“最小二乘”的由来。

实际上&＃xff0c;在编码中&＃xff0c;虽然公式中说明了行向量的计算方法&＃xff0c;但是实践中从来不会对矩阵求逆。我们一般会借助QR分解之类的方法&＃xff0c;更快更直接的计算。
QR分解是将矩阵分解为一个正交矩阵与上三角矩阵的乘积。用一张图可以形象地表示QR分解&＃xff1a;

这其中&＃xff0c; 为正交矩阵&＃xff0c;&＃xff0c;R为上三角矩阵。

详见 https://www.cnblogs.com/AndyJee/p/3846455.html

回归正题&＃xff1a;
只要知道一个$Y$&＃xff0c;那么我们就能逐行求出$X$。求出的这个$X$又可以通过这个公式求出新的$Y$&＃xff0c;新的$Y$又可以求出新的$X$…子子孙孙无穷匮也。这时候&＃xff0c;智叟说了一句&＃xff0c;愚公你有老婆么&＃xff1f;愚公老婆都没有&＃xff0c;怎么会有子孙呢&＃xff1f;
那么愚公的老婆哪里来呢&＃xff1f;即这个$Y$怎么来呢&＃xff1f;有小朋友说&＃xff0c;我们可以给它new个对象。
嗯&＃xff0c;没错&＃xff0c;这个$Y$就是人为“瞎编”出来的&＃xff0c;并且是随机的。而$X$是最优化计算出来的&＃xff0c;这个$Y$是假的无所谓&＃xff0c;我们又可以用计算出来的$X$计算出新的$Y$。这个过程一直继续&＃xff0c;$X$和$Y$都会收敛到一个合适的结果&＃xff0c;也就是“交替”一词的来历。

ALS算法页可以利用输入数据是稀疏的这一点&＃xff0c;可以用简单的线性代数运算最优解&＃xff0c;以及数据本身可并行化&＃xff0c;这三点解释了Mlib为什么要使用ALS算法&＃xff0c; 并且也只有ALS算法作为唯一的一种推荐算法。