推荐系统
例子：不同用户对不同电影有着不同偏好，以5分制进行评分
| Movie | Alice(1) | Bob(2) | Carol(3) | Dave(4) |
|---|---|---|---|---|
| Love at last | 5 | 5 | 0 | 0 |
| Romance forever | 5 | ? | ? | 0 |
| Cute puppies of love | ? | 4 | 0 | ? |
| Nonstop Car chases | 0 | 0 | 5 | 4 |
| Swords vs. karate | 0 | 0 | 5 | ? |
基于内容的推荐系统
对内容进行不同维度的评分，形成内容的特征向量（看具体场景是否加偏置项1），学习用户的偏好对内容特征向量的假设函数，则可推测各用户对不同电影的评分。
| Movie | $x_1$(romance) | $x_2$(action) |
|---|---|---|
| Love at last | 0.9 | 0 |
| Romance forever | 1.0 | 0.01 |
| Cute puppies of love | 0.99 | 0 |
| Nonstop Car chases | 0.1 | 1.0 |
| Swords vs. karate | 0 | 0.9 |
加上偏置项，则可得到每一个不同的电影内容的特征向量，如电影1的内容特征向量为
$$
x^{(1)}=[1 \quad 0.9 \quad 0]^T
$$
对任意一个用户j，学习一个参数$\theta^{(j)}\in \mathbb{R^3}$。以此预测用户j对电影i的评分：
$$
y^{(i,j)}={(\theta^{(j)})}^Tx^{(i)}
$$
本例中Alice对$x_1$和$x_2$的偏好程度为5和0，所以最终对第三部电影打分为$[0 \quad 5 \quad 0]*[1\quad 0.99\quad 0]^T=4.95$
问题描述
记$n_u$为用户数目，$n_m$为电影数目，如果用户j对电影i有评分则记$r(i,j)=1$，$y^{(i,j)}$为用户j对电影i的评分，$\theta^{(j)}\in\mathbb{R^{n+1}}$为用户的偏好向量，$x^{(i)}$为电影的特征向量，$m^{(j)}$为用户j评分过的电影数目。
则问题的目标为
$$
\min_{\theta^{(j)}}\frac{1}{2m^{(j)}}\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})+\frac{\lambda}{2m^{(j)}}\sum_{k=1}^{n}(\theta_k^{(j)})^2
$$
问题优化
对于单个用户，因为$m^{(j)}$是固定值，可以去掉$m^{(j)}$，简化问题。
$$
\min_{\theta^{(j)}}\frac{1}{2}\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum_{k=1}^{n}(\theta_k^{(j)})^2
$$
对所有用户偏好求解，则可以拆分进行优化。
$$
\min_{\theta^{(j)},\cdots,\theta^{(n_u)}}\frac{1}{2}\sum_{j=1}^{n_u}\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^{n}(\theta_k^{(j)})^2
$$
优化过程
对式(5)，利用梯度下降算法：
$$\theta_k^{(j)}:=\theta_k^{(j)}-\alpha\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x^{(i)}k\quad(k=0)\
\theta_k^{(j)}:=\theta_k^{(j)}-\alpha(\sum{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x^{(i)}_k+\lambda\theta_k^{(j)})\quad(k\neq0)$$
协同过滤算法
不知道每部电影的评分，只知道部分用户对部分电影的打分情况或者各用户对不同类别的电影的偏好。
例如：
- 求取对单部电影的评分，即给定$\theta^{(1)},\cdots,\theta^{(n_u)}$，求取$x^{(i)}$，目标函数为
$$
\min_{x^{(i)}}\frac{1}{2}\sum_{j:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum_{k=1}^{n}(x_k^{(i)})^2
$$
- 求取对多部电影的评分，即给定$\theta^{(1)},\cdots,\theta^{(n_u)}$，求取$x^{(1)},\cdots,x^{(n_m)}$，目标函数为
$$
\min_{x^{(1)},\cdots,x^{(n_m)}}\frac{1}{2}\sum_{i=1}^{n_m}\sum_{j:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^{n}(x^{(i)})^2
$$
- 给定$x^{(1)},\cdots,x^{(n_m)}$，求取$\theta^{(1)},\cdots,\theta^{(n_u)}$
例1为例2的简化版，这里不予考虑。例3可以通过初始化$\theta$，转化为求取x的问题，即转化为例2，例2也可转化为例3。初步求解的想法是，两者不断迭代，由此得到合理的评分和偏好特征。
协同过滤算法的优化函数是整合式(5)和式(6)，得到新的目标函数，此举不需要迭代运算，可以同时进行优化求解。
损失函数为
$$
J(x^{(1)},\cdots,x^{(n_m)},\theta^{(1)},\cdots,\theta^{(n_u)})=\frac{1}{2}\sum_{i=1}^{n_m}\sum_{j:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2\
+\frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^{n}(x^{(i)})^2\
+\frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^{n}(\theta_k^{(j)})^2
$$
优化目标为
$$
\min_{x^{(1)},\cdots,x^{(n_m)},\theta^{(1)},\cdots,\theta^{(n_u)}} J(x^{(1)},\cdots,x^{(n_m)},\theta^{(1)},\cdots,\theta^{(n_u)})
$$
算法流程
- 用小值随机初始化$x^{(1)},\cdots,x^{(n_m)},\theta^{(1)},\cdots,\theta^{(n_u)}$
- 梯度下降算法或其他优化算法min J，对于所有$j=1,\cdots,n_u;i=1,\cdots,n_m$：
- $\theta_k^{(j)}:=\theta_k^{(j)}-\alpha(\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x^{(i)}_k+\lambda\theta_k^{(j)})$
- $x_k^{(i)}:=x_k^{(i)}-\alpha(\sum_{j:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})\theta^{(j)}_k+\lambda x_k^{(i)})$
- 利用$\theta^{(i)}$和$x^{(i)}$预测其打分。
注：通过矢量化的方法可以加速运算过程。
矢量化：低秩矩阵分解
相关概念
- 秩（Rank）：矩阵的秩度量的就是矩阵的行列之间的相关性，即矩阵的行/列向量的极大无关组，且行秩等于列秩。为了求矩阵A的秩，我们是通过矩阵初等变换把A化为阶梯型矩阵，若该阶梯型矩阵有r个非零行，那A的秩rank(A)就等于r。 如果矩阵的各行或列是线性无关的，矩阵就是满秩的，也就是秩等于行数。
- 低秩（Low-Rank）：如果X是一个m行n列的数值矩阵，rank(X)是X的秩，假如rank (X)远小于m和n，则我们称X是低秩矩阵。低秩矩阵每行或每列都可以用其他的行或列线性表出，可见它包含大量的冗余信息。利用这种冗余信息，可以对缺失数据进行恢复，也可以对数据进行特征提取。
- 低秩分解（Low Rank Filters）
- 目的：去除冗余，减少权值参数
- 方法：采用K*1和1*K的卷积核替换掉一个K*K的卷积核
- 矩阵补全（Matrix Completion）：是为了顾及矩阵中确实的部分（不可观察的部分），可以看做是用矩阵Y’近似矩阵Y，然后用X中的元素作为矩阵M中不可观察部分的元素的估计。
- 矩阵分解（Matrix Factorization）：用矩阵A*B来近似矩阵M，那么A*B的元素就可以用于估计M中对应不可见位置的元素值，而A*B可以看成M的分解。
与协同过滤的关系
因为协同过滤本质上是考虑大量用户的偏好信息（协同），来对某一用户的偏好做出预测（过滤），那么当我们把这样的偏好用评分矩阵M表达后，这即等价于用M其他行的已知值（每一行包含一个用户对所有商品的已知评分），来估计并填充某一行的缺失值。若要对所有用户进行预测，便是填充整个矩阵，这是所谓“协同过滤本质是矩阵填充”。
矩阵填充如何来做呢？矩阵分解是一种主流方法。这是因为，协同过滤有一个隐含的重要假设，可简单表述为：如果用户A和用户B同时偏好商品X，那么用户A和用户B对其他商品的偏好性有更大的几率相似。个假设反映在矩阵M上即是矩阵的低秩。极端情况之一是若所有用户对不同商品的偏好保持一致，那么填充完的M每行应两两相等，即秩为1。
所以这时我们可以对矩阵M进行低秩矩阵分解，用U*V来逼近M，以用于填充——对于用户数为m，商品数为n的情况，M是m*n的矩阵，U是m*r，V是r*n，其中r是人工指定的参数。这里利用M的低秩性，以秩为r的矩阵M’=U*V来近似M，用M’上的元素值来填充M上的缺失值，达到预测效果。
根据维度的不同，矩阵特征的不同，分解手段也很多样：
- 矩阵（2维）：特征值分解、奇异值分解
- 张量（3维以上）：Canonical Polyadic Decomposition (CPD)、 Tucker Decomposition、Block Term Decomposition
具体介绍可见低秩分解。
例子
例如实际的各用户给分矩阵如下：
$$
Y=\left[
\begin{matrix}
5&5&0&0\
5&?&?&0\
?&4&0&?\
0&0&5&4\
0&0&5&0
\end{matrix}
\right]
$$
而预测得分的公式为
$$
Y’=X\Theta^T=\left[
\begin{matrix}
(\theta^{(1)})^T(x^{(1)})&(\theta^{(2)})^T(x^{(1)})&…&(\theta^{(n_u)})^T(x^{(1)})\
(\theta^{(1)})^T(x^{(2)})&(\theta^{(2)})^T(x^{(2)})&…&(\theta^{(n_u)})^T(x^{(2)})\
\vdots&\vdots&\vdots&\vdots\
(\theta^{(1)})^T(x^{(n_m)})&(\theta^{(2)})^T(x^{(n_m)})&…&(\theta^{(n_u)})^T(x^{(n_m)})\
\end{matrix}
\right]
$$
其中
$$
X=\left[
\begin{matrix}
–&(x^{(1)})^T&–\
–&(x^{(2)})^T&–\
&\vdots&\
–&(x^{(n_m)})^T&–\
\end{matrix}
\right]
$$
$$
\Theta=\left[
\begin{matrix}
–&(\theta^{(1)})^T&–\
–&(\theta^{(2)})^T&–\
&\vdots&\
–&(\theta^{(n_u)})^T&–\
\end{matrix}
\right]
$$
以上过程即为矩阵分解过程，且因为用户量巨大，会有趋同性，所以Y是低秩矩阵，可通过矩阵分解手段加快学习。
内容推荐
如何通过某用户已知的打分数据，为其推荐电影？以内容特征向量间的距离度量两电影的相似度。
确定电影i的特征为$x^{(i)}\in \mathbb{R}^n$，例如$x_1=romance,x_2=action,x_3=comedy,x_4=…$
选择离电影i最近的电影j作为下一个推荐，即$\min ||x^{(i)}-x^{(j)}||$。
如果需要选多个相似的电影，则对$\min ||x^{(i)}-x^{(j)}||$从低到高择选即可。
均值归一化
若是某用户初始没有评分数据，则由目标函数迭代得出的最终结果，用户未打分的电影评分均会接近零分，这显然不是正常的结果。通过均值归一化，先求各部电影的得分均值$\mu_i$，然后各用户对电影i的评分减去$\mu_i$，得到新的打分矩阵，通过该打分矩阵学习$\theta^{(j)},x^{(i)}$。然后通过假设函数求取得分后再加上均值$\mu_i$，最终分数即为用户对电影i的打分。
注：相当于用均值填补缺失值。