文章目录
任务详解：
1.矩阵的奇异值分解（SVD分解）
奇异值的定义
证明
例子


本课程来自深度之眼，部分截图来自课程视频。

【第一章 线性代数】1.8SVD分解的证明

在线LaTeX公式编辑器

任务详解：
这节课主要介绍了矩阵的奇异值分解(SVD分解)，SVD分解的应用，多元线性回归等知识点。

掌握目标：

了解svd分解证明过程，以及svd分解的算法流程
之前的课程描述的是方阵，对称阵的处理，对于一般矩阵是怎么化简的呢，就是下面的SVD分解的内容。

PS：用H或者T都是表示矩阵的转置，一个是复矩阵，一个实矩阵的写法，下面讨论的都是实矩阵，但参考书上针对复矩阵，所以用的H ，这里我们认为两个木有区别。

奇异值分解的证明过程有点复杂，虽然编程序的时候可以做调包侠，但是理解其来龙去脉是很有必要的。
1.矩阵的奇异值分解（SVD分解）
为了论述矩阵的奇异值与奇异值分解，需要下面的结论：

（1）设$A\in C_r^{m\times n}(r>0)$，（这里m和n代表矩阵的行列，r是矩阵的秩）则$A^HA$是Hermite矩阵，（如果矩阵A不包含复数，那么$A^H=A^T$）且其特征值均是非负实数；
这里小小证明一下（本来是上节证明的内容，偷懒没写，现在补上）：

$A^TA$写为：$x^TA^TAx=(Ax)^TAx$

这里x是向量，A是矩阵，那么Ax就是一个向量，令$z=Ax$，上面就$=z^Tz=||z||^2≥0$

因此可以断定$A^TA$是半正定的，他的特征值$\lambda_i≥0$
（2）$rank(A^HA)=rank(A)$；

证明：这里只要证明两者的解空间是一样的即可，因为上节讲解空间的时候有下面的结论

$R(A)+N(A)=n$

解空间N(A)一样，那么秩R(A)也就一样了，也就是要证明

$A^TAx=0$和$Ax=0$的解一样，就是x是前者的解也是后者的解。

分两种情况看：

第一种：x=0的时候，肯定是两个方程的解

第二种：对于$\forall x\neq0$，有：

$A^TAx=0$，要把$A^T$去掉，不能两边同时乘$A^T$的逆矩阵，因为$A^T$不一定有逆矩阵。所以我们方程两边同时乘$x^T$，得：$x^TA^TAx=0$，即$(Ax)^TAx=0$，这里，由于x是向量，A是矩阵，Ax是一个向量$x^TA^TAx$相当于求Ax的模长，模长等于0就意味着向量Ax中的每一项都是0，也就是$A^TAx=0$与$Ax=0$解是一样的（解空间一样），因此秩也就一样。

（3）设$A\in C_r^{m\times n}$，则$A=0$的充要条件是$A^HA=0$.
奇异值的定义
定义4.11：$A\in C_r^{m\times n}(r>0)$，$A^HA$的特征值为$\lambda_1≥\lambda_2≥…≥\lambda_r>\lambda_{r+1}=…=\lambda_n=0$则称$\sigma_i=\sqrt{\lambda_i}(i=1,2,…,n)$为A的奇异值；当A为零矩阵时，它的奇异值都是0。

说人话：根据定义可以得到$A^HA$的特征值有r个是大于0的，其他都是等于0的。于是有下面定理：
---------------------------------------------------------割你没商量------------------------------------------------------

定理4.16：设$A\in C_r^{m\times n}(r>0)$，则存在m阶正交矩阵U和n阶正交矩阵V，使得

$U^HAV=\begin{bmatrix}
\Sigma &0 \\ 
0 & 0
\end{bmatrix}$

其中$\Sigma=diag(\sigma_1,\sigma_2,…,\sigma_r)$，而。$\sigma_i(i=1,2,…,r)$为矩阵A的全部非零奇异值。注意这里的矩阵shape，$U^H$是n×m的，A是m×n，V是n×n，$U^HAV$是m×n的。
证明
证明：$A^HA$(写成$A^TA$是一样的，原因之前有讲，不啰嗦了)是对称阵（ $(A^TA)^T=A^T(A^T)^T=A^TA$，就是满足 $A^T=A$），所以可以满足对角化的操作（一个对称阵A，可以找到正交方阵P，使得 $P^TAP=对角阵$，当然由于P是正交方阵，所以有$P^T=P^{-1}$，故 $P^{-1}AP=对角阵$也成立），所以可以有下面的等式（为了和前面的不一样，这里就不用P，用V来表示咯，为什么，因为定理里面用的是V撒，V当然是正交矩阵了，复矩阵就叫酉矩阵）：

$V^H(A^HA)V=\begin{bmatrix}
\lambda_1 && \\ 
 &\ddots&\\
 &&&\lambda_n
\end{bmatrix}=\begin{bmatrix}
\Sigma^2 &0 \\ 
0 & 0
\end{bmatrix} \tag{1}$

根据奇异值的定理可知，从$\lambda_1,...,\lambda_n$这些个特征值中，有一些个是大于0，一些个是等于0的，即：$\lambda_1≥\lambda_2≥…≥\lambda_r>\lambda_{r+1}=…=\lambda_n=0$，上式中的$\Sigma^2=\begin{bmatrix}
\sigma_1^2 && \\ 
 &\ddots&\\
 &&&\sigma_r^2
\end{bmatrix}=\begin{bmatrix}
\lambda_1 && \\ 
 &\ddots&\\
 &&&\lambda_r
\end{bmatrix}$

$\Sigma$的shape是r*r的。

接下来将n×n的方阵V分两块：$V=[V_1\vdots V_2]$，其中$V_1\in C_r^{n\times r},V_2\in C_r^{n\times (n-r)}$

等式（1）两边同时乘上V，由于V是正交$VV^H=E$，改写为：

$A^HAV=V\begin{bmatrix}
\Sigma^2 &0 \\ 
0 & 0
\end{bmatrix} \tag{2}$

由于$V=[V_1\vdots V_2]$，等式2可以写为：

$A^HA[V_1\vdots V_2]=[V_1\vdots V_2]\begin{bmatrix}
\Sigma^2 &0 \\ 
0 & 0
\end{bmatrix}$

两边展开：

$[A^HAV_1\vdots A^HAV_2]=[V_1\Sigma^2\vdots 0]\tag{3}$

等式（3）中$\vdots$两边的东西都应该对应相等，所以有：

$A^HAV_1=V_1\Sigma^2\tag{4}$

$A^HAV_2=0\tag{5}$

等式（4）左右两边分别乘上$V_1^H$得：

$V_1^HA^HAV_1=\Sigma^2\tag{6}$

等式（6）左右两边的左右两边同时乘上$\Sigma^{-1}$

$\Sigma^{-1}V_1^HA^HAV_1\Sigma^{-1}=\Sigma^{-1}\Sigma^2\Sigma^{-1}\tag{7}$

这里$\Sigma=\begin{bmatrix}
\sigma_1 && \\ 
 &\ddots&\\
 &&&\sigma_r
\end{bmatrix}$是对角阵，所以$\Sigma^{-1}=\begin{bmatrix}
\sigma_1^{-1} && \\ 
 &\ddots&\\
 &&&\sigma_r^{-1}
\end{bmatrix}$也是是对角阵，对角阵的转置和它本身一样（$A^T=A$），所以:

$\Sigma^{-1}=(\Sigma^{-1})^T=(\Sigma^{-1})^H\tag{8}$

根据公式（8），等式（7）可以写为：

$(\Sigma^{-1})^TV_1^HA^HAV_1\Sigma^{-1}=\Sigma^{-1}\Sigma^2\Sigma^{-1}$

把前面几个的转置提取到括号外（位置要变化），$\Sigma^{-1}\Sigma^2\Sigma^{-1}=E$,这里写为$I_r$（r是维度），得：

$(AV_1\Sigma^{-1})^T(AV_1\Sigma^{-1})=I_r\tag{9}$

等式（5）左右两边分别乘上$V_2^H$得：

$V_2^HA^HAV_2=0$

$(AV_2)^HAV_2=0\tag{10}$

等式（9）可以看做是一个矩阵($AV_2$)的转置乘以矩阵本身等于0的形式。根据开篇的结论三（设$A\in C_r^{m\times n}$，则$A=0$的充要条件是$A^HA=0$.）可知：

$AV_2=0\tag{11}$

到这个地方，我们分别得到了两个等式（9）（11）。

对于等式（9），令$U_1=AV_1\Sigma^{-1}$，则有：

$U_1^HU_1=I_r\tag{12}$

再次看shape，A是m×n，$V_1$是n×r，$\Sigma^{-1}$是r×r的，所以$U_1$是m×r的。如果记$U_1$是由r个向量$u_1,u_2,...,u_r$构成，上式（12）可以写成：

$U_1^HU_1=\begin{bmatrix}
u_1^T  \\ 
 \vdots\\
u_r^T \end{bmatrix}\begin{bmatrix}
u_1&\cdots&u_r  \\ 
 \end{bmatrix}=I_r\tag{13}$

等式（13）中的左边展开后的每一项$u_i^Tu_j$满足：

$\left\{\begin{matrix}u_i^Tu_j=1\quad i=j,\\u_i^Tu_j=0\quad i\neq j\end{matrix}\right.$

因此说构成的$U_1$的r个向量是两两正交的单位向量。由于$U_1$的shape是m×r，这r个向量$u_i\in\real^m$（说人话：r是m维的列向量），这里可以根据定理，直接把r维向量扩充到m维上。

---------------------------------------------------------割你没商量------------------------------------------------------

定理可视化实例补充：

二维向量$\begin{bmatrix}1  \\ 0\\0 \end{bmatrix}\begin{bmatrix}0 \\ 1\\0 \end{bmatrix}$可以扩充为三维向量：$\begin{bmatrix}1  \\ 0\\0 \end{bmatrix}\begin{bmatrix}0 \\ 1\\0 \end{bmatrix}\begin{bmatrix}0 \\ 0\\1 \end{bmatrix}$

---------------------------------------------------------割你没商量------------------------------------------------------

$U_1$扩充为$C^m$（说人话：m维）的标准正交基，把后来扩展的向量记为：$u_{r+1},...,u_m$，并构造成矩阵：$U_2=(u_{r+1},...,u_m)$，则：

$U=[U_1\vdots U_2]=(u_1,u_2,\cdots,u_r,u_{r+1},\cdots,u_m)$

U是m阶酉（正交）矩阵，且有：

$U_1^HU_1=I_r,U_2^HU_1=0\tag{15}$
下面U构造好后，就可以开始验证要证明的定理$U^HAV$啦，因为$V=[V_1\vdots V_2]$：

$U^HAV=U^H[AV_1\vdots AV_2]\tag{14}$

由$U=[U_1\vdots U_2]$可以知道：$U^H=\begin{bmatrix}U_1^H  \\ U_2^H \end{bmatrix}$；

由$U_1$的设定$U_1=AV_1\Sigma^{-1}$，两边的右边同时乘以$\Sigma$，得$U_1\Sigma=AV_1$；

由等式（11）；

以上三个东西带入等式（14）

$U^HAV=\begin{bmatrix}U_1^H  \\ U_2^H \end{bmatrix}[U_1\Sigma\vdots 0]=\begin{bmatrix}U_1^HU_1\Sigma&0  \\ U_2^HU_1\Sigma&0 \end{bmatrix}$

把等式（15）带入

$U^HAV=\begin{bmatrix}
\Sigma &0 \\ 
0 & 0
\end{bmatrix}$

到这里证明就好了，但是上面的等式还可以在等式的两边左右分别乘以$U,V^H$。

$UU^HAVV^H=U\begin{bmatrix}
\Sigma &0 \\ 
0 & 0
\end{bmatrix}V^H$

单位阵退散后变成：

$A=U\begin{bmatrix}
\Sigma &0 \\ 
0 & 0
\end{bmatrix}V^H$
例子
求矩阵$A=\begin{bmatrix}
1&0&1 \\ 
0 & 1& 1 \\
0 & 0& 0
\end{bmatrix}$的奇异值分解。

解：$B=A^TA=\begin{bmatrix}
1&0&1 \\ 
0 & 1& 1 \\
1 & 1& 2
\end{bmatrix}$的特征值是$\lambda_1=3,\lambda_2=1,\lambda_3=0$，对应的特征向量依次为：

$\xi_1=\begin{bmatrix}1\\  1 \\ 2\end{bmatrix},\xi_2=\begin{bmatrix}1\\  -1 \\ 0\end{bmatrix},\xi_1=\begin{bmatrix}1\\  1 \\ -1\end{bmatrix}$

$\Sigma=\begin{bmatrix}
\sqrt{3} &0 \\ 
0 &1
\end{bmatrix}$

$A^TA$是对称矩阵，因此其特征向量是两两正交的，把上面的三个$\xi$除以模长，得到

$V=\begin{bmatrix}
\frac{1}{\sqrt{6}}&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{3}} \\ 
\frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{3}}\\
\frac{2}{\sqrt{6}} & 0& -\frac{1}{\sqrt{3}}
\end{bmatrix}$

根据公式$U_1=AV_1\Sigma^{-1}$计算$U_1$，其中A在题目已经给了，$V=[V_1\vdots V_2]$，其中$V_1\in C_r^{n\times r},V_2\in C_r^{n\times (n-r)}$，由于R(A)=2，所以r=2，取V的前面两列，$V_1=\begin{bmatrix}
\frac{1}{\sqrt{6}}&\frac{1}{\sqrt{2}} \\ 
\frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{2}}\\
\frac{2}{\sqrt{6}} & 0
\end{bmatrix}$，$\Sigma^{-1}=\begin{bmatrix}
\frac{1}{\sqrt{3}} &0 \\ 
0 &1
\end{bmatrix}$，最后算出来：

$U_1=AV_1\Sigma^{-1}=\begin{bmatrix}
\frac{1}{\sqrt{2}} &\frac{1}{\sqrt{2}} \\ 
\frac{1}{\sqrt{2}} &-\frac{1}{\sqrt{2}}\\
0&0
\end{bmatrix}$

这里只构造出$U_1$，还要弄$U_2$，使得$U=[U_1\vdots U_2]$

取$U_2=\begin{bmatrix}0\\  0 \\ 1\end{bmatrix}$

$U=[U_1\vdots U_2]=\begin{bmatrix}
\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}&0 \\ 
\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}&0\\
0& 0& 1
\end{bmatrix}$

则A的奇异值分解为：

$A=U\begin{bmatrix}
\sqrt{3}&0&0 \\ 
0 & 1&0\\
0& 0& 0
\end{bmatrix}V^T$

推荐系统之矩阵分解和FM
一、矩阵分解
1. 隐语义模型与矩阵分解
2. 隐语义模型
3. 矩阵分解算法的原理
4. 矩阵分解算法的求解
5. Basic SVD
6. 编程实现
7. 课后思考
8. 参考资料
9. 源码链接
二、FM
1. FM模型的引入
1.1 逻辑回归模型及其缺点
1.2 二阶交叉项的考虑及改进
2. FM公式的理解
3. FM模型的应用
4. 代码实践
4.1 调包实现
**电影评分数据集实战**
分类任务实战
4.2 从零实现
5. 课后思考
6. 参考资料
7. 源码链接

一、矩阵分解
1. 隐语义模型与矩阵分解
协同过滤算法的特点就是完全没有利用到物品本身或者是用户自身的属性， 仅仅利用了用户与物品的交互信息就可以实现推荐，是一个可解释性很强， 非常直观的模型， 但是也存在一些问题， 第一个就是处理稀疏矩阵的能力比较弱， 所以为了使得协同过滤更好处理稀疏矩阵问题， 增强泛化能力， 从协同过滤中衍生出矩阵分解模型(Matrix Factorization,MF)或者叫隐语义模型,  两者差不多说的一个意思， 就是在协同过滤共现矩阵的基础上， 使用更稠密的隐向量表示用户和物品， 挖掘用户和物品的隐含兴趣和隐含特征， 在一定程度上弥补协同过滤模型处理稀疏矩阵能力不足的问题。


2. 隐语义模型
隐语义模型最早在文本领域被提出，用于找到文本的隐含语义。在2006年， 被用于推荐中， 它的核心思想是通过隐含特征（latent  factor）联系用户兴趣和物品（item）， 基于用户的行为找出潜在的主题和分类， 然后对item进行自动聚类，划分到不同类别/主题(用户的兴趣)。
这么说可能有点抽象，所以下面拿项亮老师《推荐系统实践》里面的那个例子看一下：

如果我们知道了用户A和用户B两个用户在豆瓣的读书列表， 从他们的阅读列表可以看出，用户A的兴趣涉及侦探小说、科普图书以及一些计算机技术书， 而用户B的兴趣比较集中在数学和机器学习方面。 那么如何给A和B推荐图书呢？

 先说说协同过滤算法， 这样好对比不同：

对于UserCF，首先需要找到和他们看了同样书的其他用户（兴趣相似的用户），然后给他们推荐那些用户喜欢的其他书。
对于ItemCF，需要给他们推荐和他们已经看的书相似的书，比如作者B看了很多关于数据挖掘的书，可以给他推荐机器学习或者模式识别方面的书。


而如果是隐语义模型的话，  它会先通过一些角度把用户兴趣和这些书归一下类， 当来了用户之后， 首先得到他的兴趣分类， 然后从这个分类中挑选他可能喜欢的书籍。



这里就看到了隐语义模型和协同过滤的不同， 这里说的角度其实就是这个隐含特征， 比如书籍的话它的内容， 作者， 年份， 主题等都可以算隐含特征，如果这个例子还不是很清晰的话， 那么下面再举个更为具体的例子， 看看是如何通过隐含特征来划分开用户兴趣和物品的。但是在这之前， 相信通过上面这个例子， 我们已经隐隐约约感受到了协同过滤和隐语义模型的区别了， 下面放上王喆老师《深度学习推荐系统》的一个原理图作为对比， 区别简直一目了然：



我们下面拿一个音乐评分的例子来具体看一下隐特征矩阵的含义。
假设每个用户都有自己的听歌偏好， 比如A喜欢带有小清新的， 吉他伴奏的， 王菲的歌曲，如果一首歌正好是王菲唱的， 并且是吉他伴奏的小清新， 那么就可以将这首歌推荐给这个用户。 也就是说是小清新， 吉他伴奏， 王菲这些元素连接起了用户和歌曲。 当然每个用户对不同的元素偏好不同， 每首歌包含的元素也不一样， 所以我们就希望找到下面的两个矩阵：

潜在因子—— 用户矩阵Q

这个矩阵表示不同用户对于不同元素的偏好程度， 1代表很喜欢， 0代表不喜欢， 比如下面这样：





潜在因子——音乐矩阵P

表示每种音乐含有各种元素的成分， 比如下表中， 音乐A是一个偏小清新的音乐， 含有小清新的Latent Factor的成分是0.9， 重口味的成分是0.1， 优雅成分0.2…




利用上面的这两个矩阵， 我们就能得出张三对音乐A的喜欢程度：

张三对小清新的偏好 * 音乐A含有小清新的成分 + 张三对重口味的偏好 * 音乐A含有重口味的成分 + 张三对优雅的偏好 * 音乐A含有优雅的成分…,

下面是对应的两个隐向量：

根据隐向量其实就可以得到张三对音乐A的打分，即：  $0.6 * 0.9 + 0.8 * 0.1 + 0.1 * 0.2 + 0.1 * 0.4 + 0.7 * 0 = 0.69$

按照这个计算方式， 每个用户对每首歌其实都可以得到这样的分数， 最后就得到了我们的评分矩阵：

这里的红色表示用户没有打分，我们通过隐向量计算得到的。
上面例子中的小清晰， 重口味， 优雅这些就可以看做是隐含特征， 而通过这个隐含特征就可以把用户的兴趣和音乐的进行一个分类， 其实就是找到了每个用户每个音乐的一个隐向量表达形式（embedding的原理其实也是这样， 那里是找到每个词的隐向量表达）， 这个隐向量就可以反映出用户的兴趣和物品的风格，并能将相似的物品推荐给相似的用户等。 有没有感觉到是把协同过滤算法进行了一种延伸， 把用户的相似性和物品的相似性通过了一个叫做隐向量的方式进行表达
但是， 真实的情况下我们其实是没有上面那两个矩阵的， 音乐那么多， 用户那么多， 我们没有办法去找一些隐特征去表示出这些东西， 另外一个问题就是即使能表示也不一定准， 对于每个用户或者每个物品的风格，我们每个人都有不同的看法。 所以事实上， 我们有的只有用户的评分矩阵， 也就是最后的结果， 并且一般这种矩阵长这样：

这种矩阵非常的稀疏，如果直接基于用户相似性或者物品相似性去填充这个矩阵是不太容易的， 并且很容易出现长尾问题， 所以矩阵分解就可以比较容易的解决这个问题。


矩阵分解模型其实就是在想办法基于这个评分矩阵去找到上面例子中的那两个矩阵， 也就是用户兴趣和物品的隐向量表达， 然后就把这个评分矩阵分解成Q和P两个矩阵乘积的形式， 这时候就可以基于这两个矩阵去预测某个用户对某个物品的评分了。 然后基于这个评分去进行推荐。这就是矩阵分解算法的原理。


3. 矩阵分解算法的原理
在矩阵分解的算法框架下， 我们就可以通过分解协同过滤的共现矩阵来得到用户和物品的隐向量， 就是上面的用户矩阵Q和物品矩阵P， 这也是“矩阵分解”名字的由来。

矩阵分解算法将 $m\times n$ 维的共享矩阵 $R$ 分解成 $m \times k$ 维的用户矩阵 $U$ 和 $k \times n$ 维的物品矩阵 $V$ 相乘的形式。 其中 $m$ 是用户数量，  $n$ 是物品数量，  $k$ 是隐向量维度， 也就是隐含特征个数， 只不过这里的隐含特征变得不可解释了， 即我们不知道具体含义了， 要模型自己去学。 $k$ 的大小决定了隐向量表达能力的强弱，  $k$ 越大， 表达信息就越强， 理解起来就是把用户的兴趣和物品的分类划分的越具体。
那么如果有了用户矩阵和物品矩阵的话， 我们就知道了如果想计算用户 $u$ 对物品 $i$ 的评分， 只需要

$\operatorname{Preference}(u, i)=r_{u i}=p_{u}^{T} q_{i}=\sum_{f=1}^{F} p_{u, k} q_{k,i}$

这里的 $p_u$ 就是用户 $u$ 的隐向量， 就类似与上面的张三向量， 注意这是列向量，  $q_i$ 是物品 $i$ 的隐向量， 就类似于上面的音乐A向量， 这个也是列向量， 所以才用了 $p_{u}^{T} q_{i}$ 得到了一个数， 也就是用户的最终评分， 计算过程其实和上面例子中一样。  这里的 $p_{u,k}$ 和 $q_{i,k}$ 是模型的参数， 也正是我们想办法要计算的，  $p_{u,k}$ 度量的是用户 $u$ 的兴趣和第 $k$ 个隐类的关系， 而 $q_{i,k}$ 度量了第 $k$ 个隐类和物品 $i$ 之间的关系。


4. 矩阵分解算法的求解
谈到矩阵分解， 最常用的方法是特征值分解(EVD)或者奇异值分解(SVD）， 关于这两个的具体原理可以参考下面的链接奇异值分解(SVD)的原理详解及推导，但是这两种方式在这里不适用。
首先是EVD， 它要求分解的矩阵是方阵， 显然用户-物品矩阵不满足这个要求， 而传统的SVD分解， 会要求原始矩阵是稠密的， 而我们这里的这种矩阵一般情况下是非常稀疏的， 如果想用奇异值分解， 就必须对缺失的元素进行填充， 而一旦补全， 空间复杂度就会非常高， 且补的不一定对。  然后就是SVD分解计算复杂度非常高， 而我们的用户-物品矩阵非常大， 所以基本上无法使用。


5. Basic SVD
2006年的Netflix Prize之后， Simon Funk公布了一个矩阵分解算法叫做Funk-SVD,  后来被Netflix Prize的冠军Koren称为Latent Factor Model(LFM)。  Funk-SVD的思想很简单： 把求解上面两个矩阵的参数问题转换成一个最优化问题， 可以通过训练集里面的观察值利用最小化来学习用户矩阵和物品矩阵。
我们上面已经知道了， 如果有了用户矩阵和物品矩阵的话， 我们就知道了如果想计算用户 $u$ 对物品$i$的评分， 只需要

$\operatorname{Preference}(u, i)=r_{u i}=p_{u}^{T} q_{i}=\sum_{f=1}^{F} p_{u, k} q_{k,i}$

而现在， 我们有真实的 $r_{u,i}$ , 但是没有 $p_{u}^{T} q_{i}$ , 那么我们可以初始化一个啊， 随机初始化一个用户矩阵 $U$ 和一个物品矩阵 $V$ ， 然后不就有 $p_{u}^{T} q_{i}$ 了？  当然你说， 随机初始化的肯定不准啊， 但是， 有了 $p_{u}^{T} q_{i}$ 之后， 我们就可以计算一个猜测的 $\hat{r}_{u i}$ , 即

$\hat{r}_{u i}=p_{u}^{T} q_{i}$
这时候， 肯定是不准， 那么这个猜测的和真实值之间就会有一个误差：

$e_{u i}=r_{u i}-\hat{r}_{u i}$
有了误差， 我们就可以计算出总的误差平方和：

$\operatorname{SSE}=\sum_{u, i} e_{u i}^{2}=\sum_{u, i}\left(r_{u i}-\sum_{k=1}^{K} p_{u,k} q_{k, i}\right)^{2}$

有了损失， 我们就可以想办法进行训练， 把SSE降到最小， 那么我们的两个矩阵参数就可以算出来。所以就把这个问题转成了最优化的的问题， 而我们的目标函数就是：
$\min _{\boldsymbol{q}^{*}, \boldsymbol{p}^{*}} \sum_{(u, i) \in K}\left(\boldsymbol{r}_{\mathrm{ui}}-p_{u}^{T} q_{i}\right)^{2}$
这里的 $K$ 表示所有用户评分样本的集合。
有了目标函数， 那么我们就可以使用梯度下降算法来降低损失。  那么我们需要对目标函数求偏导， 得到梯度。  我们的目标函数如果是上面的SSE， 我们下面来推导一下最后的导数：
$\operatorname{SSE}=\sum_{u, i} e_{u i}^{2}=\sum_{u, i}\left(r_{u i}-\sum_{k=1}^{K} p_{u,k} q_{k,i}\right)^{2}$

首先我们求SSE在 $p_{u,k}$ （也就是Q矩阵的第 $u$ 行 $k$ 列）的梯度：

$\frac{\partial}{\partial p_{u,k}} S S E=\frac{\partial}{\partial p_{u,k}}\left(e_{u i}^{2}\right) =2e_{u i} \frac{\partial}{\partial p_{u,k}} e_{u i}=2e_{u i} \frac{\partial}{\partial p_{u,k}}\left(r_{u i}-\sum_{k=1}^{K} p_{u,k} q_{k,i}\right)=-2e_{u i} q_{k,i}$

然后求SSE在 $q_{k,i}$ 处(也就是V矩阵的第 $k$ 行 $i$ 列）的梯度：
$\frac{\partial}{\partial q_{k,i}} S S E=\frac{\partial}{\partial p_{k,i}}\left(e_{u i}^{2}\right) =2e_{u i} \frac{\partial}{\partial p_{k,i}} e_{u i}=2e_{u i} \frac{\partial}{\partial p_{k,i}}\left(r_{u i}-\sum_{k=1}^{K} p_{u,k} q_{k,i}\right)=-2e_{u i} p_{u,k}$

为了让公式更为简单， 把前面的2给他越掉， 即可以令SSE等于：

$\operatorname{SSE}=\frac{1}{2} \sum_{u, i} e_{u i}^{2}=\frac{1}{2} \sum_{u, i}\left(r_{u i}-\sum_{k=1}^{K} p_{u k} q_{k i}\right)^{2}$
这时候， 梯度就没有前面的系数了， 有了梯度， 接下来我们就可以用梯度下降算法更新梯度了：

$p_{u, k}=p_{u,k}-\eta (-e_{ui}q_{k,i})=p_{u,k}+\eta e_{ui}q_{k,i} \\ q_{k, i}=q_{k, i}-\eta (-e_{ui}p_{u,k})=q_{k, i}+\eta e_{ui}p_{u,k}$
这里的 $\eta$ 是学习率， 控制步长用的， 但上面这个有个问题就是当参数很多的时候， 就是两个矩阵很大的时候， 往往容易陷入过拟合的困境， 这时候， 就需要在目标函数上面加上正则化的损失， 就变成了RSVD， 关于RSVD的详细内容， 可以参考下面给出的链接， 由于篇幅原因， 这里不再过多的赘述。
但在实际中， 单纯的 $\hat{r}_{u i}=p_{u}^{T} q_{i}$ 也是不够的， 还要考虑其他的一些因素， 比如一个评分系统， 有些固有的属性和用户物品无关， 而用户也有些属性和物品无关， 物品也有些属性和用户无关。 因此， Netfix Prize中提出了另一种LFM， 在原来的基础上加了偏置项， 来消除用户和物品打分的偏差， 即预测公式如下：

$\hat{r}_{u i}=\mu+b_{u}+b_{i}+p_{u}^{T} \cdot q_{i}$

这个预测公式加入了3项偏置 $\mu,b_u,b_i$ , 作用如下：

$\mu$ : 训练集中所有记录的评分的全局平均数。 在不同网站中， 因为网站定位和销售物品不同， 网站的整体评分分布也会显示差异。 比如有的网站中用户就喜欢打高分， 有的网站中用户就喜欢打低分。 而全局平均数可以表示网站本身对用户评分的影响。
$b_u$ : 用户偏差系数， 可以使用用户 $u$ 给出的所有评分的均值， 也可以当做训练参数。 这一项表示了用户的评分习惯中和物品没有关系的那种因素。 比如有些用户比较苛刻， 对什么东西要求很高， 那么他评分就会偏低， 而有些用户比较宽容， 对什么东西都觉得不错， 那么评分就偏高
$b_i$ : 物品偏差系数， 可以使用物品 $i$ 收到的所有评分的均值， 也可以当做训练参数。 这一项表示了物品接受的评分中和用户没有关系的因素。 比如有些物品本身质量就很高， 因此获得的评分相对比较高， 有的物品本身质量很差， 因此获得的评分相对较低。

加了用户和物品的打分偏差之后， 矩阵分解得到的隐向量更能反映不同用户对不同物品的“真实”态度差异， 也就更容易捕捉评价数据中有价值的信息， 从而避免推荐结果有偏。 注意此时的$SSE$会发生变化：

$\begin{array}{l}
\operatorname{SSE}=\frac{1}{2} \sum_{u, i} e_{u i}^{2}+\frac{1}{2} \lambda \sum_{u}\left|\boldsymbol{p}_{u}\right|^{2}+\frac{1}{2} \lambda \sum_{i}\left|\boldsymbol{q}_{i}\right|^{2}+\frac{1}{2} \lambda \sum_{u} \boldsymbol{b}_{u}^{2}+\frac{1}{2} \lambda \sum_{u} \boldsymbol{b}_{i}^{2} \\
=\frac{1}{2} \sum_{u, i}\left(\boldsymbol{r}_{u i}-\boldsymbol{\mu}-\boldsymbol{b}_{u}-\boldsymbol{b}_{i}-\sum_{k=1}^{K} \boldsymbol{p}_{u k} \boldsymbol{q}_{k i}\right)^{2}+\frac{1}{2} \lambda \sum_{u}\left|\boldsymbol{p}_{u}\right|^{2}+\frac{1}{2} \lambda \sum_{i}\left|\boldsymbol{q}_{i}\right|^{2}+\frac{\mathbf{1}}{2} \lambda \sum_{u} \boldsymbol{b}_{u}^{2}+\frac{1}{2} \lambda \sum_{u} \boldsymbol{b}_{i}^{2}
\end{array}$

此时如果把 $b_u$ 和 $b_i$ 当做训练参数的话， 那么它俩的梯度是：
$\frac{\partial}{\partial b_{u}} S S E=-e_{u i}+\lambda b_{u} \\ \frac{\partial}{\partial b_{i}} S S E=-e_{u i}+\lambda b_{i}$

更新公式为：

$\begin{aligned}
\boldsymbol{b}_{u}&=\boldsymbol{b}_{\boldsymbol{u}}+\boldsymbol{\eta}\left(\boldsymbol{e}_{u i}-\lambda \boldsymbol{b}_{\boldsymbol{u}}\right) \\
\boldsymbol{b}_{\boldsymbol{i}} &=\boldsymbol{b}_{\boldsymbol{i}}+\boldsymbol{\eta}\left(\boldsymbol{e}_{\boldsymbol{u} i}-\lambda \boldsymbol{b}_{\boldsymbol{i}}\right)
\end{aligned}$

而对于 $p_{u,k}$ 和 $p_{k,i}$ ， 导数没有变化， 更新公式也没有变化。


6. 编程实现
我们这里用代码实现一下上面的算法来预测上一篇文章里面的那个预测Alice对物品5的评分， 看看矩阵分解到底是怎么进行预测或者是推荐的。 我把之前的例子拿过来：

任务就是根据这个评分矩阵， 猜测Alice对物品5的打分。
在实现SVD之前， 先来回忆一下ItemCF和UserCF对于这个问题的做法， 首先ItemCF的做法， 根据已有的用户打分计算物品之间的相似度， 得到物品的相似度矩阵， 根据这个相似度矩阵， 选择出前K个与物品5最相似的物品， 然后基于Alice对这K个物品的得分， 猜测Alice对物品5的得分， 有一个加权的计算公式。   UserCF的做法是根据用户对其他物品的打分， 计算用户之间的相似度， 选择出与Alice最相近的K个用户， 然后基于那K个用户对物品5的打分计算出Alice对物品5的打分。   但是， 这两种方式有个问题， 就是如果矩阵非常稀疏的话， 当然这个例子是个特例， 一般矩阵都是非常稀疏的， 那么预测效果就不好， 因为两个相似用户对同一物品打分的概率以及Alice同时对两个相似物品打分的概率可能都比较小。 另外， 这两种方法显然没有考虑到全局的物品或者用户， 只是基于了最相似的例子， 很可能有偏。
那么SVD在解决这个问题上是这么做的：

首先， 它会先初始化用户矩阵P和物品矩阵Q， P的维度是[users_num, F], Q的维度是[item_nums, F]， 这个F是隐向量的维度。 也就是把通过隐向量的方式把用户的兴趣和F的特点关联了起来。  初始化这两个矩阵的方式很多， 但根据经验， 随机数需要和 $1/ \sqrt{F}$ 成正比。 下面代码中会发现。
有了两个矩阵之后， 我就可以根据用户已经打分的数据去更新参数， 这就是训练模型的过程， 方法很简单， 就是遍历用户， 对于每个用户， 遍历它打分的物品， 这样就拿到了该用户和物品的隐向量， 然后两者相乘加上偏置就是预测的评分， 这时候与真实评分有个差距， 根据上面的梯度下降就可以进行参数的更新

这样训练完之后， 我们就可以得到用户Alice和物品5的隐向量， 根据这个就可以预测Alice对物品5的打分。 下面的代码的逻辑就是上面这两步， 这里使用带有偏置项和正则项的那个SVD算法：
class SVD():
    def __init__(self, rating_data, F=5, alpha=0.1, lmbda=0.1, max_iter=100):
        self.F = F           # 这个表示隐向量的维度
        self.P = dict()          #  用户矩阵P  大小是[users_num, F]
        self.Q = dict()     # 物品矩阵Q  大小是[item_nums, F]
        self.bu = dict()   # 用户偏差系数
        self.bi = dict()    # 物品偏差系数
        self.mu = 0.0        # 全局偏差系数
        self.alpha = alpha   # 学习率
        self.lmbda = lmbda    # 正则项系数
        self.max_iter = max_iter    # 最大迭代次数
        self.rating_data = rating_data # 评分矩阵
        
        # 初始化矩阵P和Q, 方法很多， 一般用随机数填充， 但随机数大小有讲究， 根据经验， 随机数需要和1/sqrt(F)成正比
        cnt = 0    # 统计总的打分数， 初始化mu用
        for user, items in self.rating_data.items():
            self.P[user] = [random.random() / math.sqrt(self.F)  for x in range(0, F)]
            self.bu[user] = 0
            cnt += len(items) 
            for item, rating in items.items():
                if item not in self.Q:
                    self.Q[item] = [random.random() / math.sqrt(self.F) for x in range(0, F)]
                    self.bi[item] = 0
        self.mu /= cnt
        
    # 有了矩阵之后， 就可以进行训练, 这里使用随机梯度下降的方式训练参数P和Q
    def train(self):
        for step in range(self.max_iter):
            for user, items in self.rating_data.items():
                for item, rui in items.items():
                    rhat_ui = self.predict(user, item)   # 得到预测评分
                    # 计算误差
                    e_ui = rui - rhat_ui
                    
                    self.bu[user] += self.alpha * (e_ui - self.lmbda * self.bu[user])
                    self.bi[item] += self.alpha * (e_ui - self.lmbda * self.bi[item])
                    # 随机梯度下降更新梯度
                    for k in range(0, self.F):
                        self.P[user][k] += self.alpha * (e_ui*self.Q[item][k] - self.lmbda * self.P[user][k])
                        self.Q[item][k] += self.alpha * (e_ui*self.P[user][k] - self.lmbda * self.Q[item][k])
                    
            self.alpha *= 0.1    # 每次迭代步长要逐步缩小
    
    # 预测user对item的评分， 这里没有使用向量的形式
    def predict(self, user, item):
        return sum(self.P[user][f] * self.Q[item][f] for f in range(0, self.F)) + self.bu[user] + self.bi[item] + self.mu   

下面我建立一个字典来存放数据， 之所以用字典， 是因为很多时候矩阵非常的稀疏， 如果用pandas的话， 会出现很多Nan的值， 反而不好处理。
# 定义数据集， 也就是那个表格， 注意这里我们采用字典存放数据， 因为实际情况中数据是非常稀疏的， 很少有情况是现在这样
def loadData():
    rating_data={1: {'A': 5, 'B': 3, 'C': 4, 'D': 4},
           2: {'A': 3, 'B': 1, 'C': 2, 'D': 3, 'E': 3},
           3: {'A': 4, 'B': 3, 'C': 4, 'D': 3, 'E': 5},
           4: {'A': 3, 'B': 3, 'C': 1, 'D': 5, 'E': 4},
           5: {'A': 1, 'B': 5, 'C': 5, 'D': 2, 'E': 1}
          }
    return rating_data
 
# 接下来就是训练和预测
rating_data = loadData()
basicsvd = SVD(rating_data, F=10)
basicsvd.train()
for item in ['E']:
    print(item, basicsvd.predict(1, item))
 
## 结果：
E 3.252210242858994

通过这个方式， 得到的预测评分是3.25， 这个和隐向量的维度， 训练次数和训练方式有关， 这里只说一下这个东西应该怎么用， 具体结果可以不用纠结。


7. 课后思考


矩阵分解算法后续有哪些改进呢?针对这些改进，是为了解决什么的问题呢？请大家自行探索
RSVD，消除用户和物品打分偏差等。


矩阵分解的优缺点分析

优点：

泛化能力强： 一定程度上解决了稀疏问题
空间复杂度低： 由于用户和物品都用隐向量的形式存放， 少了用户和物品相似度矩阵， 空间复杂度由 $n^2$ 降到了 $(n+m)*f$
更好的扩展性和灵活性：矩阵分解的最终产物是用户和物品隐向量， 这个深度学习的embedding思想不谋而合， 因此矩阵分解的结果非常便于与其他特征进行组合和拼接， 并可以与深度学习无缝结合。



但是， 矩阵分解算法依然是只用到了评分矩阵， 没有考虑到用户特征， 物品特征和上下文特征， 这使得矩阵分解丧失了利用很多有效信息的机会， 同时在缺乏用户历史行为的时候， 无法进行有效的推荐。  所以为了解决这个问题， 逻辑回归模型及后续的因子分解机模型， 凭借其天然的融合不同特征的能力， 逐渐在推荐系统领域得到了更广泛的应用。


8. 参考资料

王喆 - 《深度学习推荐系统》
项亮 - 《推荐系统实战》
奇异值分解(SVD)的原理详解及推导
Matrix factorization techniques for recommender systems论文
隐语义模型(LFM)和矩阵分解(MF)

9. 源码链接
https://github.com/datawhalechina/team-learning-rs/tree/master/RecommendationSystemFundamentals
二、FM
1. FM模型的引入
1.1 逻辑回归模型及其缺点
FM模型其实是一种思路，具体的应用稍少。一般来说做推荐CTR预估时最简单的思路就是将特征做线性组合（逻辑回归LR），传入sigmoid中得到一个概率值，本质上这就是一个线性模型，因为sigmoid是单调增函数不会改变里面的线性模型的CTR预测顺序，因此逻辑回归模型效果会比较差。也就是LR的缺点有：

是一个线性模型
每个特征对最终输出结果独立，需要手动特征交叉（ $x_i*x_j$ ），比较麻烦



1.2 二阶交叉项的考虑及改进
由于LR模型的上述缺陷（主要是手动做特征交叉比较麻烦），干脆就考虑所有的二阶交叉项，也就是将目标函数由原来的
$y = w_0+\sum_{i=1}^nw_ix_i$

变为
$y = w_0+\sum_{i=1}^nw_ix_i+\sum_{i=1}^{n-1}\sum_{i+1}^nw_{ij}x_ix_j$

但这个式子有一个问题，只有当 $x_i$ 与 $x_j$ 均不为0时这个二阶交叉项才会生效，后面这个特征交叉项本质是和多项式核SVM等价的，为了解决这个问题，我们的FM登场了！
FM模型使用了如下的优化函数：
$y = w_0+\sum_{i=1}^nw_ix_i+\sum_{i=1}^{n}\sum_{i+1}^n\lt v_i,v_j\gt x_ix_j$

事实上做的唯一改动就是把 $w_{ij}$ 替换成了 $\lt v_i,v_j\gt$ ，大家应该就看出来了，这实际上就有深度学习的意味在里面了，实质上就是给每个 $x_i$ 计算一个embedding，然后将两个向量之间的embedding做内积得到之前所谓的 $w_{ij}$ 好处就是这个模型泛化能力强 ，即使两个特征之前从未在训练集中同时出现，我们也不至于像之前一样训练不出 $w_{ij}$ ，事实上只需要 $x_i$ 和其他的 $x_k$ 同时出现过就可以计算出 $x_i$ 的embedding！


2. FM公式的理解
从公式来看，模型前半部分就是普通的LR线性组合，后半部分的交叉项：特征组合。首先，单从模型表达能力上来看，FM是要强于LR的，至少它不会比LR弱，当交叉项参数 $w_{ij}$ 全为0的时候，整个模型就退化为普通的LR模型。对于有 $n$ 个特征的模型，特征组合的参数数量共有 $1+2+3+\cdots  + n-1=\frac{n(n-1)}{2}$ 个，并且任意两个参数之间是独立的。所以说特征数量比较多的时候，特征组合之后，维度自然而然就高了。

定理：任意一个实对称矩阵（正定矩阵） $W$ 都存在一个矩阵 $V$ ，使得  $W=V.V^{T}$ 成立。

类似地，所有二次项参数 $\omega_{ij}$ 可以组成一个对称阵 $W$ （为了方便说明FM的由来，对角元素可以设置为正实数），那么这个矩阵就可以分解为 $W=V^TV$ ， $V$  的第 $j$ 列( $v_{j}$ )便是第 $j$ 维特征( $x_{j}$ )的隐向量。
$\hat{y}(X) = \omega_{0}+\sum_{i=1}^{n}{\omega_{i}x_{i}}+\sum_{i=1}^{n-1}{\sum_{j=i+1}^{n} \color{red}{<v_{i},v_{j}>x_{i}x_{j}}}$
需要估计的参数有 $\omega_{0}∈ R$ ， $\omega_{i}∈ R$ ， $V∈ R$ ， $< \cdot, \cdot>$ 是长度为 $k$ 的两个向量的点乘，公式如下：
$<v_{i},v_{j}> = \sum_{f=1}^{k}{v_{i,f}\cdot v_{j,f}}$
上面的公式中：

$\omega_{0}$ 为全局偏置；
$\omega_{i}$ 是模型第 $i$ 个变量的权重;
$\omega_{ij} = < v_{i}, v_{j}>$ 特征 $i$ 和 $j$ 的交叉权重;
$v_{i} $ 是第 $i$ 维特征的隐向量;
$<\cdot, \cdot>$ 代表向量点积;
$k(k<<n)$ 为隐向量的长度，包含  $k$  个描述特征的因子。

FM模型中二次项的参数数量减少为  $kn $ 个，远少于多项式模型的参数数量。另外，参数因子化使得

$x_{h}x_{i}$  的参数和  $x_{i}x_{j}$  的参数不再是相互独立的，因此我们可以在样本稀疏的情况下相对合理地估计FM的二次项参数。具体来说， $x_{h}x_{i}$  和  $x_{i}x_{j}$ 的系数分别为  $\lt v_{h},v_{i}\gt$  和  $\lt v_{i},v_{j}\gt$  ，它们之间有共同项  $v_{i}$  。也就是说，所有包含“  $x_{i}$  的非零组合特征”（存在某个  $j \ne i$  ，使得  $x_{i}x_{j}\neq 0$  ）的样本都可以用来学习隐向量 $v_{i}$ ，这很大程度上避免了数据稀疏性造成的影响。而在多项式模型中, $w_{hi}$  和  $w_{ij}$  是相互独立的。
显而易见，FM的公式是一个通用的拟合方程，可以采用不同的损失函数用于解决regression、classification等问题，比如可以采用MSE（Mean Square Error）loss function来求解回归问题，也可以采用Hinge/Cross-Entropy loss来求解分类问题。当然，在进行二元分类时，FM的输出需要使用sigmoid函数进行变换，该原理与LR是一样的。直观上看，FM的复杂度是 $O(kn^2)$ 。但是FM的二次项可以化简，其复杂度可以优化到 $O(kn)$ 。由此可见，FM可以在线性时间对新样本作出预测。
证明：

KaTeX parse error: No such environment: align at position 8: 
\begin{̲a̲l̲i̲g̲n̲}̲ \sum_{i=1}^{n-…

解释：

$v_{i,f}$  是一个具体的值；
第1个等号：对称矩阵 $W$ 对角线上半部分；
第2个等号：把向量内积 $v_{i}$,$v_{j}$ 展开成累加和的形式；
第3个等号：提出公共部分；
第4个等号： $i$ 和 $j$ 相当于是一样的，表示成平方过程。



3. FM模型的应用
最直接的想法就是直接把FM得到的结果放进sigmoid中输出一个概率值，由此做CTR预估，事实上我们也可以做召回。
由于FM模型是利用两个特征的Embedding做内积得到二阶特征交叉的权重，那么我们可以将训练好的FM特征取出离线存好，之后用来做KNN向量检索。
工业应用的具体操作步骤：

离线训练好FM模型（学习目标可以是CTR）
将训练好的FM模型Embedding取出
将每个uid对应的Embedding做avg pooling（平均）形成该用户最终的Embedding，item也做同样的操作
将所有的Embedding向量放入Faiss等
线上uid发出请求，取出对应的user embedding，进行检索召回



4. 代码实践
4.1 调包实现
调包版
直接看Github官方仓库：https://github.com/coreylynch/pyFM，里面有介绍如何安装以及使用，下面搬运一遍：
安装
方法一：直接pip install
pip install git+https://github.com/coreylynch/pyFM

方法二：手动安装
输入上面这行代码应能下载这个包并安装，如果安装失败可能是网络原因，这时可以考虑手动下载这个包然后手动python setup.py install安装，这时候通常会报错，去掉setup.py文件里面的libraries=[“m”]一行再重新安装即可
具体操作是：

在https://github.com/coreylynch/pyFM中手动下载包
将包解压，更改里面的setup.py文件，去掉setup.py文件里面的libraries=[“m”]一行
cd到当前文件夹下python setup.py install

测试
这部分主要作为简单上手让读者了解如何使用这个包~
第一步：导包
from pyfm import pylibfm
from sklearn.feature_extraction import DictVectorizer
import numpy as np

第二步：创建训练集并转换成one-hot编码的特征形式
train = [
    {"user": "1", "item": "5", "age": 19},
    {"user": "2", "item": "43", "age": 33},
    {"user": "3", "item": "20", "age": 55},
    {"user": "4", "item": "10", "age": 20},
]
v = DictVectorizer()
X = v.fit_transform(train)
print(X.toarray())

看看结果，对比一下维度是否符合预期：
[[19.  0.  0.  0.  1.  1.  0.  0.  0.]
 [33.  0.  0.  1.  0.  0.  1.  0.  0.]
 [55.  0.  1.  0.  0.  0.  0.  1.  0.]
 [20.  1.  0.  0.  0.  0.  0.  0.  1.]]

第三步：创建标签
这里简单创建了一个全1的标签：
y = np.repeat(1.0,X.shape[0])
y

array([1., 1., 1., 1.])

第四步：训练并预测
就和调用sklearn的包是一样的用法：
fm = pylibfm.FM()
fm.fit(X,y)
fm.predict(v.transform({"user": "1", "item": "10", "age": 24}))



电影评分数据集实战
数据集在这里下载，数据集本地具体保存路径读者自行阅读代码找找： http://www.grouplens.org/system/files/ml-100k.zip
导包，并定义一个导入指定格式数据集的函数
import numpy as np
from sklearn.feature_extraction import DictVectorizer
from pyfm import pylibfm

# Read in data
def loadData(filename,path="ml-100k/"):
    data = []
    y = []
    users=set()
    items=set()
    with open(path+filename) as f:
        for line in f:
            (user,movieid,rating,ts)=line.split('\t')
            data.append({ "user_id": str(user), "movie_id": str(movieid)})
            y.append(float(rating))
            users.add(user)
            items.add(movieid)

    return (data, np.array(y), users, items)

导入训练集和测试集，并转换格式
(train_data, y_train, train_users, train_items) = loadData("ua.base")
(test_data, y_test, test_users, test_items) = loadData("ua.test")
v = DictVectorizer()
X_train = v.fit_transform(train_data)
X_test = v.transform(test_data)

训练模型并测试
# Build and train a Factorization Machine
fm = pylibfm.FM(num_factors=10, num_iter=100, verbose=True, task="regression", initial_learning_rate=0.001, learning_rate_schedule="optimal")
fm.fit(X_train,y_train)

预测结果打印误差
preds = fm.predict(X_test)
from sklearn.metrics import mean_squared_error
print("FM MSE: %.4f" % mean_squared_error(y_test,preds))

FM MSE: 0.8873



分类任务实战
搞数据
import numpy as np
from sklearn.feature_extraction import DictVectorizer
from sklearn.cross_validation import train_test_split
from pyfm import pylibfm

from sklearn.datasets import make_classification

X, y = make_classification(n_samples=1000,n_features=100, n_clusters_per_class=1)
data = [ {v: k for k, v in dict(zip(i, range(len(i)))).items()}  for i in X]

X_train, X_test, y_train, y_test = train_test_split(data, y, test_size=0.1, random_state=42)

v = DictVectorizer()
X_train = v.fit_transform(X_train)
X_test = v.transform(X_test)

建模型
我们可以看到主要改变的参数是num_factors和tasks，读者可以想想为什么
fm = pylibfm.FM(num_factors=50, num_iter=10, verbose=True, task="classification", initial_learning_rate=0.0001, learning_rate_schedule="optimal")
fm.fit(X_train,y_train)

由于是分类任务，误差函数肯定不一样
from sklearn.metrics import log_loss
print("Validation log loss: %.4f" % log_loss(y_test,fm.predict(X_test)))

Validation log loss: 1.3678



4.2 从零实现
数据集介绍
criteo：criteo是非常经典的点击率预估数据集，其中连续特征有13个，类别型特征有26个，没有提供特征的具体名称，特征分别如下：
dense_feats：'I1', 'I2', 'I3', 'I4', 'I5', 'I6', 'I7', 'I8', 'I9', 'I10','I11', 'I12', 'I13'

sparse_feats:  'C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9', 'C10', 'C11', 'C12', 'C13', 'C14', 'C15', 'C16', 'C17', 'C18', 'C19', 'C20', 'C21', 'C22', 'C23', 'C24', 'C25', 'C26'



代码参考源代码文档中的FM.py


5. 课后思考
请大家思考一下FM存在的问题， 以及可以从哪些地方再进行改进？
6. 参考资料

FM算法解析
推荐系统遇上深度学习(一)–FM模型理论和实践
FM论文原文
FM算法原理分析与实践
AI上推荐 之 FM和FFM

7. 源码链接
https://github.com/datawhalechina/team-learning-rs/tree/master/RecommendationSystemFundamentals

文章目录
1.FM模型
2.FM公式理解
3.应用
4.代码时间
实战：电影评分数据
实战：分类任务
5.思考
6.参考

1.FM模型

逻辑回归模型及其缺点

做推荐CTR预估时最简单的思路就是将特征做线性组合（逻辑回归LR），传入sigmoid中得到一个概率值，本质上这就是一个线性模型。

sigmoid是单调增函数不会改变里面的线性模型的CTR预测顺序，因此逻辑回归模型效果会比较差。即LR的缺点：

是线性模型
个特征对最终输出结果独立，需要手动特征交叉（$x_i*x_j$），比较麻烦


二阶交叉项的考虑及改进

考虑所有的二阶交叉项，也就是将目标函数由原来的

$y = w_0+\sum_{i=1}^nw_ix_i$

变为

$y=w_0+\sum_{i=1}^nw_ix_i+\sum_{i=1}^{n-1}\sum_{i+1}^nw_{ij}x_ix_j$ 但这个式子有一个问题，只有当$x_i$与$x_j$均不为0时这个二阶交叉项才会生效，后面这个特征交叉项本质是和多项式核SVM等价的，为了解决这个问题，FM上场。

FM模型使用了如下的优化函数：
$y = w_0+\sum_{i=1}^nw_ix_i+\sum_{i=1}^{n}\sum_{i+1}^n\lt v_i,v_j\gt x_ix_j$ 事实上做的唯一改动就是把$w_{ij}$替换成了$\lt v_i,v_j\gt$，大家应该就看出来了，这实际上就有深度学习的意味在里面了，实质上就是给每个$x_i$计算一个embedding，然后将两个向量之间的embedding做内积得到之前所谓的$w_{ij}$。

好处就是这个模型泛化能力强 ，即使两个特征之前从未在训练集中同时出现，我们也不至于像之前一样训练不出$w_{ij}$，事实上只需要$x_i$和其他的$x_k$同时出现过就可以计算出$x_i$的embedding！
2.FM公式理解
从公式来看，模型前半部分就是普通的LR线性组合，后半部分的交叉项：特征组合。首先，单从模型表达能力上来看，FM是要强于LR的，至少它不会比LR弱，当交叉项参数$w_{ij}$全为0的时候，整个模型就退化为普通的LR模型。对于有$n$个特征的模型，特征组合的参数数量共有$1+2+3+\cdots + n-1=\frac{n(n-1)}{2}$个，并且任意两个参数之间是独立的。所以说特征数量比较多的时候，特征组合之后，维度自然而然就高了。

（线性代数）定理：任意一个实对称矩阵（正定矩阵）$W$都存在一个矩阵$V$，使得 $W=V.V^{T}$成立。

所有二次项参数$\omega_{ij}$可以组成一个对称阵$W$（为了方便说明FM的由来，对角元素可以设置为正实数），那么这个矩阵就可以分解为$W=V^TV$，$V$ 的第$j$列($v_{j}$)，即第$j$维特征($x_{j}$)的隐向量。

$\hat{y}(X) = \omega_{0}+\sum_{i=1}^{n}{\omega_{i}x_{i}}+\sum_{i=1}^{n-1}{\sum_{j=i+1}^{n} \color{red}{<v_{i},v_{j}>x_{i}x_{j}}}$
需要估计的参数有$\omega_{0}∈ R$，$\omega_{i}∈ R$，$V∈ R$，$< \cdot, \cdot>$是长度为$k$的两个向量的点乘，公式如下：
$<v_{i},v_{j}> = \sum_{f=1}^{k}{v_{i,f}\cdot v_{j,f}}$
上面的公式中：

$\omega_{0}$为全局偏置；
$\omega_{i}$是模型第$i$个变量的权重;
$\omega_{ij} = < v_{i}, v_{j}>$特征$i$和$j$的交叉权重;
$v_{i}$是第$i$维特征的隐向量;
$<\cdot, \cdot>$代表向量点积;
$k(k<<n)$为隐向量的长度，包含 $k$ 个描述特征的因子。

FM模型中二次项的参数数量减少为 $kn$个，远少于多项式模型的参数数量。另外，参数因子化使得 $x_{h}x_{i}$ 的参数和 $x_{i}x_{j}$ 的参数不再是相互独立的，因此我们可以在样本稀疏的情况下相对合理地估计FM的二次项参数。具体来说，$x_{h}x_{i}$ 和 $x_{i}x_{j}$的系数分别为 $\lt v_{h},v_{i}\gt$ 和 $\lt v_{i},v_{j}\gt$ ，它们之间有共同项 $v_{i}$ 。也就是说，所有包含“ $x_{i}$ 的非零组合特征”（存在某个 $j \ne i$ ，使得 $x_{i}x_{j}\neq 0$ ）的样本都可以用来学习隐向量$v_{i}$，这很大程度上避免了数据稀疏性造成的影响。而在多项式模型中,$w_{hi}$ 和 $w_{ij}$ 是相互独立的。
FM的公式是一个通用的拟合方程，可以采用不同的损失函数用于解决regression、classification等问题，比如可以采用MSE（Mean Square Error）loss function来求解回归问题，也可以采用Hinge/Cross-Entropy loss来求解分类问题。当然，在进行二元分类时，FM的输出需要使用sigmoid函数进行变换，该原理与LR是一样的。直观上看，FM的复杂度是 $O(kn^2)$ 。但是FM的二次项可以化简，其复杂度可以优化到 $O(kn)$ 。由此可见，FM可以在线性时间对新样本作出预测。
证明：


解释：

$v_{i,f}$ 是一个具体的值；
第1个等号：对称矩阵 $W$ 对角线上半部分；
第2个等号：把向量内积 $v_{i}$,$v_{j}$ 展开成累加和的形式；
第3个等号：提出公共部分；
第4个等号： $i$ 和 $j$ 相当于是一样的，表示成平方过程。

3.应用
直接把FM得到的结果放进sigmoid中输出一个概率值，由此做CTR预估，事实上我们也可以做召回。

FM模型是利用两个特征的Embedding做内积得到二阶特征交叉的权重，那么我们可以将训练好的FM特征取出离线存好，之后用来做KNN向量检索。

具体步骤：

离线训练好FM模型（学习目标可以是CTR）
将训练好的FM模型Embedding取出
将每个uid对应的Embedding做avg pooling（平均）形成该用户最终的Embedding，item也做同样的操作
将所有的Embedding向量放入Faiss等
线上uid发出请求，取出对应的user embedding，进行检索召回

4.代码时间
1.调包实现

Github官方仓库：https://github.com/coreylynch/pyFM
安装及使用：

安装

方法一：pip install

pip install git+https://github.com/coreylynch/pyFM

方法二：手动安装

在官方仓库下载这个包
解压包
cd到当前文件夹下python setup.py install安装
若报错，去掉setup.py文件里面的libraries=[“m”]一行，再回到第3步重新安装


安装失败。需要提前安装好Cython，但是我按网上的教程都未成功。后续有待实现

测试

导包

from pyfm import pylibfm
from sklearn.feature_extraction import DictVectorizer
import numpy as np


创建训练集并转换为one-hot编码的特征形式

train = [
    {"user": "1", "item": "5", "age": 19},
    {"user": "2", "item": "43", "age": 33},
    {"user": "3", "item": "20", "age": 55},
    {"user": "4", "item": "10", "age": 20},
]
v = DictVectorizer()
X = v.fit_transform(train)
print(X.toarray())

查看结果

[[19.  0.  0.  0.  1.  1.  0.  0.  0.]

[33.  0.  0.  1.  0.  0.  1.  0.  0.]

[55.  0.  1.  0.  0.  0.  0.  1.  0.]

[20.  1.  0.  0.  0.  0.  0.  0.  1.]]


创建标签

简单创建了一个全1的标签：

y = np.repeat(1.0,X.shape[0])
y


array([1., 1., 1., 1.])


训练并预测

和调用sklearn的包是一样的用法：

fm = pylibfm.FM()
fm.fit(X,y)
fm.predict(v.transform({"user": "1", "item": "10", "age": 24}))

实战：电影评分数据
数据集在这里下载：http://www.grouplens.org/system/files/ml-100k.zip


导包，并定义一个导入指定格式数据集的函数
import numpy as np
from sklearn.feature_extraction import DictVectorizer
from pyfm import pylibfm

# Read in data
def loadData(filename,path="ml-100k/"):
    data = []
    y = []
    users=set()
    items=set()
    with open(path+filename) as f:
        for line in f:
            (user,movieid,rating,ts)=line.split('\t')
            data.append({ "user_id": str(user), "movie_id": str(movieid)})
            y.append(float(rating))
            users.add(user)
            items.add(movieid)

    return (data, np.array(y), users, items)

导入训练集和测试集，并转换格式
(train_data, y_train, train_users, train_items) = loadData("ua.base")
(test_data, y_test, test_users, test_items) = loadData("ua.test")
v = DictVectorizer()
X_train = v.fit_transform(train_data)
X_test = v.transform(test_data)

训练模型并测试
# Build and train a Factorization Machine
fm = pylibfm.FM(num_factors=10, num_iter=100, verbose=True, task="regression", initial_learning_rate=0.001, learning_rate_schedule="optimal")
fm.fit(X_train,y_train)

预测结果打印误差
preds = fm.predict(X_test)
from sklearn.metrics import mean_squared_error
print("FM MSE: %.4f" % mean_squared_error(y_test,preds))


FM MSE: 0.8873

实战：分类任务
处理数据
import numpy as np
from sklearn.feature_extraction import DictVectorizer
from sklearn.cross_validation import train_test_split
from pyfm import pylibfm

from sklearn.datasets import make_classification

X, y = make_classification(n_samples=1000,n_features=100, n_clusters_per_class=1)
data = [ {v: k for k, v in dict(zip(i, range(len(i)))).items()}  for i in X]

X_train, X_test, y_train, y_test = train_test_split(data, y, test_size=0.1, random_state=42)

v = DictVectorizer()
X_train = v.fit_transform(X_train)
X_test = v.transform(X_test)

建模型

注意：这里的参数num_factors和tasks改变了
fm = pylibfm.FM(num_factors=50, num_iter=10, verbose=True, task="classification", initial_learning_rate=0.0001, learning_rate_schedule="optimal")
fm.fit(X_train,y_train)


这是处理分类任务，误差函数也和之前的不同
from sklearn.metrics import log_loss
print("Validation log loss: %.4f" % log_loss(y_test,fm.predict(X_test)))



Validation log loss: 1.3678


从零实现

数据集介绍

criteo：非常经典的点击率预估数据集，其中连续特征有13个，类别型特征有26个，没有提供特征的具体名称，特征分别如下：


dense_feats：‘I1’, ‘I2’, ‘I3’, ‘I4’, ‘I5’, ‘I6’, ‘I7’, ‘I8’, ‘I9’, ‘I10’,‘I11’, ‘I12’, ‘I13’

sparse_feats:  ‘C1’, ‘C2’, ‘C3’, ‘C4’, ‘C5’, ‘C6’, ‘C7’, ‘C8’, ‘C9’, ‘C10’, ‘C11’, ‘C12’, ‘C13’, ‘C14’, ‘C15’, ‘C16’, ‘C17’, ‘C18’, ‘C19’, ‘C20’, ‘C21’, ‘C22’, ‘C23’, ‘C24’, ‘C25’, ‘C26’

5.思考
FM存在的问题，以及哪可以改进
6.参考

FM算法解析
推荐系统遇上深度学习(一)–FM模型理论和实践
FM算法原理分析与实践
AI上推荐 之 FM和FFM
FM论文原文