线性网络
对于推荐系统（recommender system）数据集，用户对第$m$部电影的评分表示为 \[ \mathcal D_m= \left\{\left( \tilde x_n=(n), y_n=r_{nm} \right) \mbox{ user }n\mbox{ rated movie }m \right\}， \] $\tilde x_n=(n)$表示抽象的（abstract）特征，代表用户编号（ID），不代表任何数值上的意义，这类的特征称为类别特征（categorical feature）。
常见的类别特征有ID、血型、程序语言……然而，许多机器学习算法都对数值特征友好，比如线性模型、扩展的（extended）线性模型（神经网络等）……决策树可以处理类别特征。若要将类别特征用于对数值特征友好的模型，需要将类别特征转换或编码（transform/encode）为数值特征。二值编码（binary vector encoding）是比较简单的征编码方式，对于血型有 \[ A=[1\;0\;0\;0]^\top,\quad B=[0\;1\;0\;0]^\top,\quad AB=[0\;0\;1\;0]^\top,\quad O=[0\;0\;0\;1]^\top。 \] 编码之后第$m$部电影的的数据记为 \[ \mathcal D_m= \left\{\left( \tilde x_n=\mbox{BinaryVectorEncoding}(n), y_n=r_{nm} \right) \mbox{ user }n\mbox{ rated movie }m \right\}， \] 所有用户的数据可以统一记为 \[ \mathcal D= \left\{\left( \tilde x_n=\mbox{BinaryVectorEncoding}(n), y_n=\left[r_{n1}\;?\;?\;r_{n4}\;r_{n5}\;\ldots\;r_{nM}\right]^\top \right) \right\}， \] “$?$”表示用户没有对电影做出评价。若要学到每个用户的爱好，需要先学到每个用户的特征（年龄、电影类型的偏好等）。
利用不含$x_0^{(\ell)}$神经元1的$N-\tilde d-M$神经网络（自编码器）提取特征，如上图所示，$\mathbf x$是只有一个非0元的二值向量。中间的$\tanh$转换必要么？
对于$\mathbf x$，只会有一个非0分量进入$\tanh$层的神经元，即使不进行$\tanh$转换（采用线性模型，如上图所示）也能找到特征的恰当描述方式，这样的神经网络称为线性网络（linear network）。第一层用$N\times\tilde d$的矩阵$\mathbf V^\top$表示，第二层用$\tilde d\times M$的矩阵$\mathbf W$表示，线性网络可以表示为 \begin{equation} h(\mathbf x)=\mathbf W^\top\mathbf V\mathbf x。 \end{equation} 对每个用户而言，由于$\mathbf x_n$只有一个元素为1，相当于抽取矩阵的一列 \begin{equation*} h(\mathbf x_n)=\mathbf W^\top\mathbf v_n， \end{equation*} $\mathbf v_n$表示$\mathbf V$的第$n$列，相当于对第$n$个用户进行了特征转换。
对于推荐系统，线性网络学习$\mathbf V$和$\mathbf W$。
矩阵分解
令$\Phi(\mathbf x)=\mathbf V\mathbf x$，第$m$部电影的评分只是线性模型$h_m(\mathbf x)=\mathbf w_m^\top\Phi(\mathbf x)$。对于$\mathcal D_m$，期望有 \[ r_{nm}=y_n\approx\mathbf w_m^\top\mathbf v_n， \] 需要最小化目标函数 \begin{equation} E_{in}\left(\left\{\mathbf w_m\right\},\left\{\mathbf v_n\right\}\right) ={1\over \sum_{m=1}^M\lvert\mathcal D_m\rvert}\sum_{\mbox{user }n\mbox{ rated movie }m} \left(r_{nm}-\mathbf w_m^\top\mathbf v_n\right)^2， \end{equation} 同时学到转换方式$\left\{\mathbf v_n\right\}$和线性模型$\left\{\mathbf w_m\right\}$。
当$r_{nm}=\mathbf w_m^\top\mathbf v_n=\mathbf v_n^\top\mathbf w_m$时，所有评价可记为矩阵形式$\mathbf R\approx\mathbf V^\top\mathbf W$，将含有缺失值的$\mathbf R$矩阵分解为两个矩阵的乘积，如上图所示，就得到了用户的特征以及特征的线性组合方式。
通过用户的评分$\mathbf R$，学到了$\mathbf v_n$表示用户的特征（喜好），也学到了$\mathbf w_m$表电影具备哪些元素，如上图所示。当有新用户$N+1$时，$\mathbf v_{N+1}$初始化为$\mathbf v_{N+1}={1\over N}\sum_{n=1}^N\mathbf v_n$，新用户$N+1$的评分$r_{(N+1)m}$最高的电影是有最高平均评分的电影。
类似的矩阵分解模型可以用于提取其它抽象特征。线性自编码器可看作一种特殊的矩阵分解方法：
| 线性自编码器 $\mathbf X\approx\mathbf W\left(\mathbf W^\top\mathbf X\right)$ | 矩阵分解 $\mathbf R\approx \mathbf V^\top\mathbf W$ | |
|---|---|---|
| motivation | 特殊的$d-\tilde d-d$的线性神经网络 | $N-\tilde d-M$的线性神经网络 |
| 误差度量 | 所有数据$x_{ni}$上的平方误差 | 已知数据$r_{nm}$上的平方误差 |
| 求解方法 | $\mathbf X^\top\mathbf X$特征向量上的全局最优解 | 交替最小二乘法求取的局部最优解 |
| 功能 | 获取数据低维特征表示 | 提取隐含特征 |
交替最小二乘法
通过最优化 \[ \min_{\mathbf W,\mathbf V}E_{in}\left(\left\{\mathbf w_m\right\},\left\{\mathbf v_n\right\}\right) \propto\sum_{m=1}^M\left( \sum_{(\mathbf x_n,r_{nm})\in\mathcal D_m} \left(r_{nm}-\mathbf w_m^\top\mathbf v_n\right)^2 \right)， \] 学到参数矩阵$\mathbf W,\mathbf V$。同时学习两组变量很困难，可以采取类似k均值算法的交替最小二乘法（alternating least squares algorithm）：
- 当固定$\mathbf v_n$时，相当于在第$m$部电影的数据$\mathcal D_m$上最小化$E_{in}$得到$\mathbf w_m$，通过对每部电影的线性回归（不含$w_0$）实现；
- 由于用户特征向量和电影特征向量的对称性（二者地位一样），当固定$\mathbf w_m$时，相当于对每个用户的线性回归（不含$v_0$）。
####交替最小二乘法
随机初始化$\tilde d$维向量$\{\mathbf w_m\}，\{\mathbf v_n\}$；
交替最小化$E_{in}$直到收敛：
- 最优化$\mathbf w_1,\mathbf w_2,\ldots,\mathbf w_M$：对电影$m$在数据集$\{(\mathbf v_n,r_{nm})\}$做线性回归；
- 最优化$\mathbf v_1,\mathbf v_2,\ldots,\mathbf v_N$：对用户$n$在数据集$\{(\mathbf w_m,r_{nm})\}$做线性回归。
每次交替最小化都会使$E_{in}$减小，收敛是有保障的。采用交替最小二乘法，类似于用户和电影之间的“探戈”（tango）。
随机梯度下降法
随机梯度下降法（SGD，stochastic gradient descent）容易实现，每轮迭代高效，容易扩展到平方误差之外的其它误差度量方式。
单个数据产生的误差为 \[ err(\mbox{user }n, \mbox{movie }m, \mbox{rating }r_{nm}) =\left(r_{nm}-\mathbf w_m^\top\mathbf v_n\right)^2， \] 那么可得偏微分 \[ \begin{aligned} \nabla_{\mathbf v_n} &err(\mbox{user }n, \mbox{movie }m, \mbox{rating }r_{nm}) =-2\left(r_{nm}-\mathbf w_m^\top\mathbf v_n\right)\mathbf w_m\\ \nabla_{\mathbf w_m} &err(\mbox{user }n, \mbox{movie }m, \mbox{rating }r_{nm}) =-2\left(r_{nm}-\mathbf w_m^\top\mathbf v_n\right)\mathbf v_n。 \end{aligned} \] 每次跟新量$\propto -(\mbox{residual})(\mbox{the other feature vector})$，余数（residual）为$r_{nm}-\mathbf w_m^T\mathbf v_n$，也就是用余数倍另一个量更新当前量。
####基于随机梯度下降法的矩阵分解
随机初始化$\tilde d$维向量$\{\mathbf w_m\}，\{\mathbf v_n\}$2；
对$t=0,1,\ldots,T$迭代：
- 对所有已知的$r_{nm}$，随机抽取$(n,m)$；
- 计算余数$\tilde r_{nm}=r_{nm}-\mathbf w_m^T\mathbf v_n$；
- 随机梯度更新： \[ \begin{aligned} \mathbf v_n^{new}&\leftarrow\mathbf v_n^{old}+\eta\tilde r_{nm}\mathbf w_m^{old}\\ \mathbf w_m^{new}&\leftarrow\mathbf w_m^{old}+\eta\tilde r_{nm}\mathbf v_n^{old}。 \end{aligned} \]
随机梯度下降法在大规模矩阵分解中很常用。
####KDDCup 2011 Track 1: World Champion Solution by NTU
问题：训练数据时间上要早于测试数据。也就是训练和测试数据分布不同，有偏采样（sampling bias）。
对策：强化时间晚的数据。SGD在最后$T’$轮迭代只选用感兴趣的$T’$个数据。
结果：consistent improvements of test performance。
