重新整理出来的推荐系统相关的资料，曾经在赵鹏飞老师指导下进行的学习，与青梅煮茶同学合作完成。

1. MLE & MAP

MLE

背景：极大似然估计方法（Maximum Likelihood Estimate，MLE）也称为最大概似估计或最大似然估计，是求估计的另一种方法，最大概似是1821年首先由德国数学家高斯（C. F. Gauss）提出，但是这个方法通常被归功于英国的统计学家罗纳德·费希尔（R. A. Fisher），他在1922年的论文《On the mathematical foundations of theoretical statistics, reprinted in Contributions to Mathematical Statistics》 $^{[1]}$ 中再次提出了这个思想，并且首先探讨了这种方法的一些性质.极大似然估计这一名称也是费希尔给的。这是一种目前仍然得到广泛应用的方法。

原理：极大似然估计是建立在极大似然原理的基础上的一个统计方法，极大似然原理的直观想法是，一个随机试验如有若干个可能的结果A，B，C，… ，若在一次试验中，结果A出现了，那么可以认为实验条件对A的出现有利，也即出现的概率 $P(A)$ 较大。若概率由系数 $\theta$ 影响，我们便取能使 $P(A)$ 达到最大的 $\theta$ 的值。以下举例：

假设总体X为离散型，其概率分

$P(X=x)=P(x:\theta)$

其中 $\theta$ 为未知参数，设 $(X_{1},X_{2}…X_{n})$ 是取自总体的样本容量为n的样本，则它的联合分布律为 $\prod\limits_{i=1}^{n}P(x_{i}:\theta)$ 。又设一组观测值为 $(x_{1},x_{2}…x_{n})$ ，易知样本 $(X_{1},X_{2}…X_{n})$ 取到观测值 $(x_{1},x_{2}…x_{n})$ 的概率为：

$L(\theta)=L(x_{1},x_{2}...x_{n}:\theta)=\prod\limits_{i=1}^{n}P(x_{i}:\theta)$

这一概率随 $\theta$ 的取值而变化，它是 $\theta$ 的函数，称 $L(\theta)$ 为样本的似然函数。

极大似然估计法原理就是固定样本观测值 $(x_{1},x_{2}…x_{n})$ ，挑选参数 $\theta$ 使

$L(x_{1},x_{2}...x_{n}:\hat{\theta})=maxL(x_{1},x_{2}...x_{n}:\theta)$

这样得到的 $\hat{\theta}$ 与样本值有关， $\hat{\theta}(x_{1},x_{2}…x_{n})$ 称为参数 $\theta$ 的极大似然估计值。

MAP

背景：在贝叶斯统计学中，最大后验估计(Maximum A Posteriori，MAP)可以利用经验数据获得对未观测量的点态估计。它与Fisher的最大似然估计(Maximum Likelihood，ML)方法相近，不同的是它扩充了优化的目标函数，其中融合了预估计量的先验分布信息，所以最大后验估计可以看作是正则化(regularized)的最大似然估计。

原理：最大后验概率是在极大似然估计的基础上根据贝叶斯方法，引入参数的先验概率，结合似然度选择最佳参数或模型的方法。

首先，假设 $\theta$ 的先验分布为 $g(\theta)$ 。通过贝叶斯理论，对于 $\theta$ 的后验分布如下式所示：

$f( \theta| x )=\frac{f(x|\theta)g(\theta)}{\int_{-\infty}^{+\infty}f(x|\theta^{\prime})g(\theta^{\prime})d\theta^{\prime}}$

最后验分布的目标为：

$L(\theta)=arg\max_{\theta} \frac{f(x|\theta)g(\theta)}{\int_{-\infty}^{+\infty}f(x|\theta^{\prime})g(\theta^{\prime})d\theta^{\prime}}=arg\max_{\theta} f( \theta| x )$

其中我们称 $g(\theta)$ 为 prior（先验概率）， $f( \theta| x )$ 为 posterior（后验概率），当先验概率与后验概率有共同形式的分布时，我们称 $g(\theta)$ 为 conjugate prior（共轭先验）。

2. MAP运用于正则化的理解

原始的Linear Regression

假设有若干数据 $(x_{1},y_{1}),(x_{2},y_{2}),…,(x_{m},y_{m})$ ，我们要对其进行线性回归。也就是得到一个方程 :

$y=\omega^{T}x+\epsilon$

$\epsilon$ 可以认为是，我们拟合的值和真实值之间的误差 ( $y - \hat{y}$ ) 。
我们将 $\epsilon$ 看成是一个随机变量，其服从高斯分布，即 $p(\epsilon)=N(0,\sigma^{2})p(\epsilon)=N(0,\sigma^{2})$ ，即：

$p(\epsilon_{i})=\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{\epsilon_{i}^{2}}{2\sigma^{2}})$

则对于每一个数据点 $(x_{i},y_{i})$ ，我们用 $x_{i}$ 得到 $y_{i}$ 的概率为 :

$p(y_{i}|x_{i}:\omega)=\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y_{i}-\omega^{T}x_{i})^{2}}{2\sigma^{2}})$

如果我们想要让这个概率最大，就得到了最大似然 :

$\begin{align} L(\omega)&=\prod\limits_{i=1}^{m} p(y_{i}|x_{i}:\omega) \\&=\prod\limits_{i=1}^{m} \frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y_{i}-\omega^{T}x_{i})^{2}}{2\sigma^{2}}) \end{align}$

取对数 :

$\begin{align} logL(\omega)&=log\prod\limits_{i=1}^{m} \frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y_{i}-\omega^{T}x_{i})^{2}}{2\sigma^{2}}) \\&=\sum\limits_{i=1}^{m}log\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y_{i}-\omega^{T}x_{i})^{2}}{2\sigma^{2}}) \\&=mlog\frac{1}{\sqrt{2\pi}\sigma}-\frac{1}{2\sigma^{2}}\sum\limits_{i=1}^{m}(y_{i}-\omega^{T}x_{i})^{2} \end{align}$

由上式可以看出，最大化对数似然，也就是最小化均方误差。即 :

$\omega^{*}=arg\min_{\omega}\sum\limits_{i=1}^{m}(y_{i}-\omega^{T}x_{i})^{2}$

这样，就从最大似然的角度解释了均方误差。

对 $\omega$ 引入高斯先验分布

如果我们对 $\omega$ 引入高斯先验分布，也就是说 :

$p(\omega_{j})=\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{\omega_{j}^{2}}{2\sigma^{2}})$

这样, $L(\omega)$ 的式子就变为：

$\begin{align} L(\omega)&=p(\omega)\prod\limits_{i=1}^{m} p(y_{i}|x_{i}:\omega) \\&=\prod\limits_{j=1}^{n}\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{\omega_{j}^{2}}{2\sigma^{2}})\prod\limits_{i=1}^{m} \frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y_{i}-\omega^{T}x_{i})^{2}}{2\sigma^{2}}) \\&=(\frac{1}{\sqrt{2\pi}\sigma})^{n}exp(-\frac{\sum_{j=1}^{n}\omega_{j}^{2}}{2\sigma^{2}})\prod\limits_{i=1}^{m} \frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y_{i}-\omega^{T}x_{i})^{2}}{2\sigma^{2}}) \\&=(\frac{1}{\sqrt{2\pi}\sigma})^{n}exp(-\frac{\omega^{T}\omega}{2\sigma^{2}})\prod\limits_{i=1}^{m} \frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y_{i}-\omega^{T}x_{i})^{2}}{2\sigma^{2}}) \end{align}$

取对数:

$\begin{align} logL(\omega)&=log[(\frac{1}{\sqrt{2\pi}\sigma})^{n}exp(-\frac{\omega^{T}\omega}{2\sigma^{2}})\prod\limits_{i=1}^{m} \frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y_{i}-\omega^{T}x_{i})^{2}}{2\sigma^{2}})] \\&=mlog\frac{1}{\sqrt{2\pi}\sigma}+nlog\frac{1}{\sqrt{2\pi}\sigma}-\frac{1}{2\sigma^{2}}\sum\limits_{i=1}^{m}(y_{i}-\omega^{T}x_{i})^{2}-\frac{\omega^{T}\omega}{2\sigma^{2}} \end{align}$

最大化对数似然函数，就等价于：

$\omega^{*}=argmin_{\omega}\sum\limits_{i=1}^{m}(y_{i}-\omega^{T}x_{i})^{2}+\lambda \parallel \omega^{T}\omega \parallel$

也就是说，为参数 $\omega$ 引入高斯先验分布的最大似然，相当于给均方误差函数加上正则项。

小结

之所以推导这些，是向给解释正则化找个理由。有了贝叶斯的这种方式，我们可以说，引入先验分布是降低了模型的复杂度，或者说是拉普拉斯分布进行了一定的特征选择，而高斯分布式对不重要的特征进行了抑制。另外，还可以说是，在 $\omega$ 的空间搜索时，先验分布缩小了解空间，这样对求解速度也有好处。

3. 多元高斯分布回顾

如果一个n维随机变量 $X=[X_{1}…X_{n}]^{T}$ 服从多元正态分布，均值为 $\mu \in \Re^{n}$ , 协方差矩阵为 $\Sigma$ ,它的概率密度公式为:

$p(x:\mu,\Sigma)=\frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}}exp(-\frac{1}{2}(x-\mu)^{T}\Sigma^{-1}(x-\mu))$

我们把这个写作 $X \sim N(\mu,\Sigma)$ ，其中 $\Sigma$ 为:

$\Sigma=E[(X-\mu)(X-\mu)^{T}]=E[XX^{T}]-\mu\mu^{T}$

4. 新知识应用于pmf的推算

传统的协同过滤方法既不能处理大数据量的推荐，也不能处理只有很少评分的用户。而 Salakhutdinov 的论文《Probabilistic matrix factorization》 $^{[5]}$ 提出了著名的概率矩阵分解的方法来解决这个问题。具体如下：

假设有 $M$ 个电影和 $N$ 个用户。 $R_{ij}$ 表示第 $i$ 个用户对电影 $j$ 的评分。假设隐变量的维度是 $D$ ，那么我们希望将评分矩阵 $R$ 分解成两个矩阵，即用户隐矩阵 $U\in R^{D\times N}$ ，和电影隐矩阵 $V\in R^{D\times M}$ 。其中， $U_{i}$ 表示第 $i$ 个用户的隐向量， $V_{j}$ 表示第 $j$ 个电影的隐向量。假设评分是一个有高斯噪音的正态分布。那么我们的评分应当有如下公式：

$p(R|U,V,\sigma^{2})=\prod\limits_{i=1}^{N}\prod\limits_{j=1}^{N}[N(R_{ij}|U_{i}^{T}V_{j},\sigma^{2})]^{I_{ij}}$

这里的 $N(R_{ij}|U_{i}^{T}V_{j},\sigma^{2})$ 是指高斯分布的概率密度函数。 $I_{ij}$ 是指示函数，表明如果用户 $i$ 评论了电影 $j$ ，那么其结果等与1，否则就是0。因此，上面的结果就是所有已经被评论的电影得分的乘积，也就是似然函数了。

我们给每个用户和电影的隐向量（特征向量）一个均值为0的高斯先验。有：

$p(U|\sigma^{2}_{U})=\prod\limits_{i=1}^{N}N(U_{i}|0,\sigma_{U}^{2}I)$ $p(V|\sigma^{2}_{V})=\prod\limits_{j=1}^{M}N(V_{j}|0,\sigma_{V}^{2}I)$

这里的I是一个D维单位对角矩阵。那么，用户和电影特征的后验分布计算如下：

$\begin{align} p(U,V|R,\sigma^{2},\sigma^{2}_{V},\sigma^{2}_{U})&=\frac{p(R|U,V,\sigma^{2},\sigma^{2}_{V},\sigma^{2}_{U})\times p(U,V)}{p(R,\sigma^{2},\sigma^{2}_{V},\sigma^{2}_{U})} \\&\sim p(R|U,V,\sigma^{2},\sigma^{2}_{V},\sigma^{2}_{U})\times p(U,V) \\&=p(R|U,V,\sigma^{2},\sigma^{2}_{V},\sigma^{2}_{U})\times p(U)\times p(V) \\&=\prod\limits_{i=1}^{N}\prod\limits_{j=1}^{M}[N(R_{ij}|U_{i}^{T}V_{j},\sigma^{2})]^{I_{ij}}\times \prod\limits_{i=1}^{N}N(U_{i}|0,\sigma_{U}^{2}I) \times \prod\limits_{j=1}^{M}N(V_{j}|0,\sigma_{V}^{2}I) \end{align}$

对两边取个ln（这是我们求解中常用的方法，取ln不改变函数凹凸性，极值点位置也不便，所以最优点的解也是一样的，同时，乘积形式变成求和形式，也简单很多）。

$lnp(U,V|R,\sigma^{2},\sigma^{2}_{V},\sigma^{2}_{U})=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}I_{ij}lnN(R_{ij}|U_{i}^{T}V_{j},\sigma^{2})+\sum\limits_{i=1}^{N}lnN(U_{i}|0,\sigma_{U}^{2}I)+\sum\limits_{j=1}^{M}lnN(V_{j}|0,\sigma_{V}^{2}I)$

上面这三项都是形式完全一样，只是系数和均值方差不同，我们以其中一个为例，剩下都一样。即求解:

$lnN(U_{i}|0,\sigma^{2}_{U}I)$

我们给出用户i的概率密度函数：

$N(U_{i}|0,\sigma_{U}^{2}I)=-\frac{1}{(2\pi)^{D/2}|\sigma_{U}^{2}I|^{1/2}}exp(-\frac{1}{2}U_{i}^{T}(\sigma_{u}^{2}I)^{-1}U_{i})$

注意，由于 $I$ 是对角阵，那么 $(\sigma_{u}^{2}I)^{-1}=\frac{1}{\sigma_{u}^{2}}I$ ，所以：

$\begin{align} lnN(U_{i}|0,\sigma_{U}^{2}I)&=ln(-\frac{1}{(2\pi)^{D/2}|\sigma_{U}^{2}I|^{1/2}})-\frac{U_{i}^{T}U_{i}}{2\sigma_{u}^{2}} \\&=-ln(|\sigma_{U}^{2}I|^{1/2})-\frac{U_{i}^{T}U_{i}}{2\sigma_{u}^{2}}+C_{U} \\&=-\frac{1}{2}ln(\sigma_{U}^{2D})-\frac{U_{i}^{T}U_{i}}{2\sigma_{u}^{2}}+C_{U} \\&=-\frac{D}{2}ln(\sigma_{U}^{2})-\frac{U_{i}^{T}U_{i}}{2\sigma_{u}^{2}}+C_{U} \end{align}$

类似地，我们可以得到进而我们可以得到最终的公式。公式如下：

$lnp(U,V|R,\sigma^{2},\sigma^{2}_{V},\sigma^{2}_{U})=-\frac{1}{2\sigma^{2}}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}I_{ij}(R_{ij}-U_{i}^{T}V_{j})^{2}-\frac{1}{2\sigma_{U}^{2}}\sum\limits_{i=1}^{N}U_{i}^{T}U_{i}-\frac{1}{2\sigma_{V}^{2}}\sum\limits_{j=1}^{M}V_{j}^{T}V_{j}-\frac{1}{2}((\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}I_{ij})ln\sigma^{2}+NDln\sigma_{U}^{2}+MDln\sigma_{V}^{2})+C$