Machine Learning

Published: by Creative Commons Licence

  • Tags:

简介

机器学习是指给定目标，程序通过从经验中学习，最后提高它的性能指标。

根据目标的取值范围，我们可以将问题分类为：

  • 回归问题：连续的值，比如所有的实数
  • 分类问题：输出离散的值，比如0,1,2

根据我们是否对样本进行标记，机器学习分为：

  • 监督学习：对样本进行标记，比如图像识别
  • 无监督学习：没有对样本进行标记，比如聚类问题。

监督学习

监督学习的基本流程为：

给定训练集合$x, y$，其中$x$是输入，$y$是正确的输出，记$x^{(i)},y^{(i)}$表示第$i$个样本的输入和输出，记$m$为样本数量，$n$为特征数量。

之后我们需要通过训练集合训练出一个假说函数$h$，这个假说函数拥有最小的惩罚，其中惩罚为$J(h)$。这里我们认为$h$由参数向量$\theta$确定。

最后我们利用$h$预测新数据的输出。

多元线性回归

线性回归算法的假说函数为$h(x)=\theta_1^Tx+\theta_0$，其中$\theta_1$是一个长度为$n$的向量，$\theta_0$为常数。或者我们可以为每个$x$后面补充一个$1$，这时候可以简化为$h(x)=\theta^T x$。

我们的目标是最小化下面的惩罚函数$J$：

\[J(\theta)=\frac{1}{2m}\sum_{i=1}^m(\theta^Tx^{(i)}-y^{(i)})^2\]

计算导数如下：

\[\begin{aligned} \frac{\partial}{\partial \theta_j}J(\theta)&=\frac{1}{m}\sum_{i=1}^m(\theta^Tx^{(i)}-y^{(i)})x^{(i)}_j \end{aligned}\]

线性回归模型的性质：

  • 只有唯一的极值点，同时这个点也是全局极小值点。（因此很适合使用梯度下降算法）

逻辑回归

逻辑回归用于解决分类问题，其假说函数为：

\[h(x)=\mathrm{sigmoid}(\theta^Tx)=\frac{1}{1+e^{-\theta^T x}}\]

这里顺带一提，$\mathrm{sigmoid}$函数的导数特别简单，$\mathrm{sigmoid}'(z)=\mathrm{sigmoid}(z)(1-\mathrm{sigmoid}(z))$。

其中$h(x)$可以理解为对于输入$x$，其输出为$1$的概率，即$h(x)=P(y=1\mid x;\theta)$。

考虑到$h$产生的是$[0,1]$之间的连续值，但是分类问题需要的是离散值，因此我们可以在$h(x)\geq 0.5$的时候输出$1$，否则输出$0$（输出较大可能的项）。考虑到$\mathrm{sigmoid}$函数的特性，可以发现输出$1$当且仅当$\theta^Tx\geq 0$。再考虑到线性函数的模型，其等高线$\theta^Tx=0$对应一个非规则轮廓，如果$x$落在非规则轮廓内部输出$0$，外部输出$1$，这条等高线称为决策边界。

我们不能简单的使用$J(\theta)=\frac{1}{2m}|h(x)-y|^2$作为惩罚函数，因为此时函数可能有多个局部极值点，不是凸函数。

考虑到$y\in\left\{0,1\right\}$，因此我们可以得出

\[P(y|x;\theta)=h(x)^y(1-h(x))^{1-y}\]

根据最大似然估计，得出：

\[\begin{aligned} l(\theta)&=P(y|x;\theta)\\ &=\prod_{i=1}^mP(y^{(i)}|x^{(i)};\theta)\\ &=\prod_{i=1}^mh(x^{(i)})^{y^{(i)}}(1-h(x^{(i)}))^{1-y^{(i)}} \end{aligned}\]

其对数形式为：

\[\begin{aligned} \ln l(\theta) &= \ln \prod_{i=1}^mh(x^{(i)})^{y^{(i)}}(1-h(x^{(i)}))^{1-y^{(i)}}\\ &= \sum_{i=1}^m y^{(i)}\ln h(x^{(i)})+(1-y^{(i)})\ln(1-h(x^{(i)})) \end{aligned}\]

我们希望最大化$l(\theta)$，等价于最大化$\ln l(\theta)$。

令$J(\theta)=-\frac{1}{m}\ln l(\theta)$，此时的惩罚函数为凸函数，可以利用梯度下降算法进行求解，其偏导数为：

\[\begin{aligned} \frac{\partial}{\partial \theta_j}J(\theta)&=\frac{1}{m}\sum_{i=1}^m (h(x^{(i)})-y^{(i)})x^{(i)}_j \end{aligned}\]

多元逻辑回归

我们已经知道逻辑回归可以处理$y$的值仅两种可能的情况，下面我们设计一个算法，可以将输入分类到$k$个类别中。具体做法就是，我们通过逻辑回归得到$k$个模型，其中$h^{(i)}(x)$表示输入为第$i$个类别元素的概率。之后我们选择$\mathrm{argmax}_i h^{(i)}(x)$作为输出，即最可能的类型。

梯度下降算法

我们可以把惩罚函数$J$绘制成图形。

https://raw.githubusercontent.com/taodaling/taodaling.github.io/master/assets/images/machine-learning/gradient-descending.png

梯度下降算法实际上是选择一条下坡的道路（沿梯度的逆向）。当不存在这样的道路的时候，就意味着我们到了一个局部极小值点。

梯度下降分为多次迭代，每次迭代我们都通过下面方式修正参数$\theta$。

\[\theta := \theta-\alpha \frac{\mathrm{d}}{\mathrm{d} \theta}J(\theta)\]

其中$\alpha$是一个称为学习率的参数。

梯度下降法的性质：

  • 如果迭代点抵达某个极值点，那么迭代点不会再发生变化。
  • $\theta$越是接近极值点，梯度下降的步长就会越小，因此不必特意不断减少$\alpha$。

变种

上面的方法称为批量梯度下降(batch gradient descent)。在训练集非常大的情况下，由于批量梯度下降每一轮迭代都需要遍历整个训练集，因此会非常慢。

还有一种方法叫做随机梯度下降(stochastic gradient descent)。具体做法就是遍历整个训练集，但是对于每个单独的训练集元素都执行一轮迭代(即可以认为每次迭代的时候$m=1$)。其最后还是会停止在全局最小值处。

随机梯度下降也不是完美的，较少的错误数据或噪音可能对结果造成很大的影响。我们可以在随机梯度下降的过程中加入优化，比如每次一次性取$100$条记录来训练(每次迭代的时候$m=100$)，这样就能避免噪音带来的影响，同时训练的速度也非常快。这种方法叫做微批量梯度下降(Mini-batch gradient descent)。

特征缩放

如果某个特征的范围特别大，那么等高线会变得很狭长，这样会导致梯度下降算法需要更多的迭代次数。

特征缩放是指将第$i$个特征归约为$x_i:=\frac{x_i-\mu_i}{s_i}$，其中$\mu_i$为第$i$个特征的平均值，而$s_i$是第$i$个特征的范围（最大值减去最小值）。可以发现这样归约后有$-2\leq x_i\leq 2$。

学习率的选择

只要学习率足够小，就能保证每一步的迭代都会减少$J(\theta)$。但是过小的学习率会导致收敛变慢。

正规方程

对于多元线性回归模型，可以使用正规方程一步计算到位结果。

我们可以假设所有特征之间线性无关（否则可以不断删除冗余的列，直到所有列线性无关），那么可以直接用投影矩阵找到参数$\theta$。以样本向量作为行向量构成$m\times n$的矩阵$X$，可以直接得到：

\[\theta=(X^TX)^{-1}X^Ty\]

正规方程的解法时间复杂度为$O((m+n)n^2)$，因此在特征数$n$很大的时候会运行的很缓慢。同时如果样本集很大，也很难将所有的样本同时加载到内存中做矩阵运算。

这里特殊提一下，如果$X$的列向量线性相关，我们也可以利用伪逆进行求解。记$X^+$为$X$的伪逆，我们可以令$\theta=X^+y$。

正则化

当我们的特征数过多，容易得到一个误差接近$0$的模型，但是这时候样本数不足以约束模型，因此这时候模型无法泛化到新的样本中。这时候我们称模型过拟合。

当我们的特征数不足，这时候会得到一个误差很大的模型。这时候称模型欠拟合。

对于惩罚函数$J(h)$，我们实际上是加上一段与模型相关的乘法，此时修正后的惩罚函数为$J(h)+\lambda\mathrm{Reg}(h)$。其中$\lambda$表示正则化的强度，$\lambda$越大，则对模型约束越大，防止过拟合效果越好，但是对应的也会导致模型在训练数据上效果的变差，即可能导致欠拟合。

对于线性模型，$h$由向量$\theta$所决定，我们可以定义$\mathrm{Reg}(\theta)=\frac{1}{2m}\theta^T\theta$，这样可以保证训练出来的模型参数比较小，从而保证模型比较简单，不容易出现过拟合。这里特殊提一下，一般我们在计算$\mathrm{Reg}(\theta)$的时候是不会考虑之前插入的全$1$的特征的。

在梯度下降的时候，正则化的作用可以理解为将梯度向远离原点的方向延长，由于梯度下降是按照梯度的逆向移动，因此每次迭代后会更加接近原点。

神经网络

在逻辑回归的时候，当特征数量很大的时候，我们很难选择特征，并且生成新的特征。这时候就需要用到神经网络了。

神经网络分成多个层次，每个层次都包含多个神经元，第一层称为输入层，最后一层称为输出层，中间的其余层称为隐藏层。可以将神经元理解为一个sigmod函数$g$，接受输入，并提供输出（每一层增加一个隐藏的神经元，始终输出常数$1$），而神经元之间的线路对应一个常数，这个常数对这个神经元的输出进行缩放。在神经网络中，输入经过输入层、隐藏层、输出层的变换，最后输出实数的这个过程称为前向传播。

https://upload.wikimedia.org/wikipedia/commons/9/97/Ncell.png

记录$L$为神经网络层数，记录$s_i$表示第$i$层神经元个数，记录$a_i^{(j)}$表示第$j$层的第$i$个神经元的输出，$\Theta^{(i)}$是一个$s_{i+1}\times s_{i}$的矩阵，矩阵的第$k$列对应第$i$层输出到$a_{k}^{(i+1)}$的模型参数，$\Theta^{(i)}$称为权重矩阵，表示从第$i$层向第$i+1$层的转换。经过$\Theta^{(i)}$转换后，第$i+1$层得到的输入为$z^{(i+1)}=\Theta^{(i)}a^{(i)}$，满足$g(z^{(i)})=a^{(i)}$。记录$K$为输出层的神经元数目（即$s_L$）。记录$\delta^{(l)}_i$表示第$l$层第$i$个神经元的误差。

如果希望神经网络做多分类，可以在输出层设置多个神经元，这样神经网络的输出就是一个向量了，向量的第$i$个元素表示输入是否属于类别$i$。

神经网络的惩罚函数定义为:

\[\begin{aligned} J(\Theta)=&-\frac{1}{m}\left[\sum_{i=1}^m\sum_{k=1}^K y_k^{(i)}\ln h(x^{(i)})_k+(1-y_k^{(i)})\ln(1-h(x^{(i)})_k)\right]\\&+\frac{\lambda}{2m}\sum_{l=1}^{L-1}\sum_{i=1}^{s_l}\sum_{j=1}^{s_{l+1}}(\Theta^{(l)}_{j,i})^2 \end{aligned}\]

在做正则化的时候我们同样不考虑那些增加的常数$1$神经元的输出的参数。

偏导数可以通过链式求导的方式计算：

下面的计算我们仅考虑一个测试用例，多个测试用例只需要计算出单个测试用例的部分，之后加总即可。同时我们忽略系数$\frac{1}{m}$和正则化项的影响。定义$\delta^{(l)}$表示$\frac{\mathrm{d}J}{\mathrm{d}a^{(l)}}$，可以发现有$\delta^{(l)}=a^{(L)}-y$。对于其余项：

\[\begin{aligned} \delta^{(l)}&=\frac{\mathrm{d}J}{\mathrm{d}a^{(l)}}\\ &=\frac{\mathrm{d}J}{\mathrm{d}a^{(l+1)}}\frac{\mathrm{d}a^{(l+1)}}{\mathrm{d}z^{(l+1)}}\frac{\mathrm{d}z^{(l+1)}}{\mathrm{d}a^{(l)}}\\ &=\delta^{(l+1)}\mathrm{diag}(a^{(l+1)}.*(1-a^{(l+1)}))\Theta^{(l)}\\ &=(\delta^{(l+1)}.*a^{(l+1)}.*(1-a^{(l+1)}))\Theta^{(l)} \end{aligned}\]

其中$\mathrm{diag}(A)$表示把向量$A$作为对角线元素组成一个新的方阵，而$A.*B$表示按位置乘，即$(A.*B)_{i,j}=A_{i,j}B_{i,j}$。

接下来定义$\Delta^{(l)}_{i,j}=\frac{\mathrm{d}J}{\mathrm{d}\Theta^{(l)}_{i,j}}$。可以发现

\[\begin{aligned} \Delta^{(l)}_{i,j}&=\frac{\mathrm{d}J}{\mathrm{d}\Theta^{(l)}_{i,j}}\\ &=\frac{\mathrm{d}J}{\mathrm{d}a^{(l+1)}}\frac{\mathrm{d}a^{(l+1)}}{\mathrm{d}z^{(l+1)}}\frac{\mathrm{d}z^{(l+1)}}{\mathrm{d}\Theta^{(l)}_{i,j}}\\ &=\delta^{(l+1)}\mathrm{diag}(a^{(l+1)}.*(1-a^{(l+1)}))[i:a_j^{(l)}]\\ &=(\delta^{(l+1)}.*a^{(l+1)}.*(1-a^{(l+1)}))_i\cdot a_j^{(l)} \end{aligned}\]

其中$[i:a_j^{(l)}]$是个向量，只有第$i$行一个非零值$a_j^{(l)}$。

最后加入我们久违的系数和正则化项后，得到：

\[\frac{\mathrm{d}J}{\mathrm{d}\Theta^{(l)}_{i,j}}= \left\{ \begin{array}{ll} \frac{1}{m}\Delta^{(l)}_{i,j} &\text{if }j=0\\ \frac{1}{m}\Delta^{(l)}_{i,j}+\frac{\lambda}{m}\Theta^{(l)}_{i,j} &\text{otherwise} \end{array} \right.\]

神经网络的惩罚函数并不是一个凸函数，因此可能存在多个局部极值点。

随机初始化

如果初始化$\Theta$的时候选择$0$矩阵，会导致每一层的神经元的输出都相同，对应的它们的偏导数也会相同。这样无论多少次迭代后，每一层的神经元只有一个输出，十分浪费。

一个较好的方法时，用$(-\epsilon, \epsilon)$之间的随机数填充$\Theta$，注意$\epsilon$不能太大，可以取$1$。

梯度检测

如果写梯度下降算法的时候，偏导数计算错误，可能也会得到一个使得惩罚下降的结果，但是效果会相差十万八千里。

那么该如何发现偏导数计算上的错误呢。

一种简单的方法就是计算两侧偏导。

\[\frac{\partial}{\partial \theta_i}J(\theta)\approx \frac{J(\theta+\epsilon)-J(\theta-\epsilon))}{2\epsilon}\]

求出两侧偏导后，对照计算出来的导数看看结果是否相近，这里可以取$\epsilon=10^{-4}$或者其它较小的数。

训练参数的选择

一般我们将样板按照$6:2:2$划分为训练集，交叉验证集，测试集。训练集用于训练模型，我们通过调整训练参数在训练集上可以得到多个模型，之后让这些模型在交叉验证集上测试，选择惩罚最小的模型。最后利用测试集测试选中模型的泛化能力。并且注意正则化项仅出现在测试集上，因为正则化项仅用于挑选模型。

如果一个模型在训练集上表现不良，则表示这个模型欠拟合；如果模型在训练集表现良好，但是在验证集上表现不佳，这说明模型过拟合。

支持向量机（SVM）

考虑逻辑回归问题中的每个样本对惩罚函数的贡献：

\[\frac{1}{m}[y^{(i)}(-\ln h(x^{(i)}))+(1-y^{(i)})(-\ln(1-h(x^{(i)})))]\]

这里我们可以定义两个分段函数，其中第一个分段函数$\mathrm{cost}_1(z)$用于拟合$-\ln \mathrm{sigmoid}(z)$，第二个分段函数$\mathrm{cost}_2(z)$用于拟合$-\ln (1-\mathrm{sigmoid}(z))$。

其中$\mathrm{cost}_1(z)$的定义如下：

\[\mathrm{cost}_1(z)= \left\{ \begin{array}{ll} 0&\text{if }z\geq 1\\ c_1(1-x)&\text{if }z<1 \end{array} \right.\]

而$\mathrm{cost}_2(z)$的定义如下：

\[\mathrm{cost}_2(z)= \left\{ \begin{array}{ll} 0&\text{if }z\leq -1\\ c_2(1+x)&\text{if }z>-1 \end{array} \right.\]

其中$c_1$和$c_2$都是正实数。

之后我们的最小化目标可以设置为

\[\frac{1}{m}\sum_{i=1}^m[y^{(i)}\mathrm{cost}_1(\theta^Tx^{(i)})+(1-y^{(i)})\mathrm{cost}_2(\theta^Tx^{(i)})]+\frac{\lambda}{2m}\theta^T\theta\]

之后忽略一些常数系数之后，我们的最小化目标等价于：

\[\frac{1}{\lambda}\sum_{i=1}^m[y^{(i)}\mathrm{cost}_1(\theta^Tx^{(i)})+(1-y^{(i)})\mathrm{cost}_2(\theta^Tx^{(i)})]+\frac{1}{2}\theta^T\theta\]

支持向量机通过最小化上面的目标函数，得到最优的模型参数$\theta$。之后利用模型参数，对于输入的$x$，SVM可以直接报告结果是$1$还是$0$而非逻辑回归的概率。SVM的假说函数定义如下：

\[h_{\theta}(x)= \left\{ \begin{array}{cc} 1&\text{if }\theta^Tx\geq 0\\ 0&\text{otherwise} \end{array} \right.\]

如果我们将$\lambda$设置的足够小，这样训练得到的模型$\theta$，应当满足当$y^{(i)}=1$的时候$\theta^Tx^{(i)}\geq 1$，$y^{(i)}=0$的时候$\theta^Tx^{(i)}\leq -1$。那么此时最小化的目标仅为正则化项。

支持向量机寻找的决策边界是距离样本最远的一条线，其到样本的距离称为支持向量机的间距。这样的决策边界具有更强的鲁棒性。也因此SVM也称为大间距分类器。

如果我们不使用核函数的支持自动机，则一般称为使用线性核函数。当特征数远远多于样本数，线性核函数或者逻辑回归是不错的选择，因为不需要拟合过于复杂的决策边界。如果特征很少，且样本适中，高斯核函数则是个更好的选择，可以自动选择特征，并能训练处复杂度的函数。如果特征很少，但是样本非常多，我们可以手动加入一些新的特征，之后使用逻辑回归或线性核函数。

SVM功能比逻辑回归要强大，但是神经网络的表达能力会更加强大。SVM相较于神经网络，SVM是凸优化问题，只有唯一的极小值点，因此可以很快收敛，但是神经网络则存在多个局部极小值点，因此不能保证收敛到最优。

核函数

基于已有的特征，我们可以创建出无穷的特征，比如$x_1^i,x_2^j,x_1^ix_2^j$。由于特征数越多，计算量就越大，我们必须仅选择其中的部分特征。那么我们应该使用哪些特征，核函数可以用于帮助我们选择特征。

考虑多个$s$个新的$n$维向量$l^{(i)}$，这些向量称为标记点。我们定义它们与$x$的相似度为：

\[f_i=\mathrm{k}(x,l^{(i)})=\exp(-\frac{\|x-l^{(i)}\|_2^2}{2\sigma^2})\]

其中$\mathrm{k}$函数称为高斯核函数，是核函数的一种。

可以发现当$x$与$l^{(i)}$的欧式距离很小的时候，核函数的结果接近$1$，如果距离很大，则核函数的结果接近$0$。

我们将$1,f_1,f_2,\ldots,f_s$作为特征。这时候可以发现只有接近这些标记点的输入才会输出$1$，否则会输出$0$。

至于如何选择标记点，我们可以直接从训练集和中选择部分输入作为标记点即可。

核函数主要被支持向量机所使用，虽然可以用于普通的逻辑回归，但是会运行的很慢。

除了高斯核函数外，也还有很多核函数，但是不是所有函数都可以作为核函数的，核函数必须满足默塞尔定理才行，这时候求解SVM的参数$\theta$时才能使用一些优化技巧，快速求解。下面介绍一些满足默塞尔定理的核函数：

  • 多项式核函数：$k(x,l)=(x^Tl+a)^b$，其中$a$和$b$是可选的参数。
  • 字符串核函数：用于计算两个字符串的相似度
  • chi-square核函数
  • histogram intersection核函数

k-means算法

k-means算法是一种聚类算法，用于无监督机器学习。

要运行这个算法，你首先要指定一个$K$，表示希望得到的集群数。之后随机化$K$个集群中心。之后重复执行下面过程多次：

  • 将所有样本归类到最接近的集群中心所对应的集群中。
  • 将每个集群中心修正为集群中所有点的均值。

当然如果某个迭代中，发现一个集群中没有样本，那么有两种方案：

  • 移除那个集群，这样得到的总集群数可能只有$K-1$个。
  • 用随机点替代新的集群中心。

下面我们用$c^{(i)}$表示第$i$个样本所属的分类。$\mu_k$表示第$k$个分类的中心。

k-means算法的优化目标为：

\[J(c^{(1)},\ldots,c^{(m)},\mu_1,\ldots,\mu_k)=\frac{1}{m}\sum_{i=1}^m\|x^{(i)}-\mu_{c^{(i)}}\|^2\]

可以发现k-means算法的执行第一步显然会优化惩罚函数，而第二步是通过调整$\mu_k$（将$c^{(i)}$视作常数）让其落于极小值点。

这里提到的随机选择中心点，是指从样本中随机挑选，而非在无穷的高维空间中挑选任意点。

上面提到的惩罚函数并不是一个凸函数，因此可能存在多个极值点。这时候我们需要多次k-means算法来获得最优的分类方法。

PCA算法和数据降维

对于$\mathbb{R}^n$上的元素，我们选择$\mathbb{R}^n$的一个$k$维线性子空间$S$，并将所有元素投影到这个子空间。这个过程就叫做降维，降维可以帮助我们压缩数据，以及低维的数据更利于展示。对于机器学习，如果特征数过多，会导致学习速度变慢。可以通过将特征降维，在可控失真内，大幅度降低数据的维度，从而提高学习速度。

PCA（主成分分析，Principal component analysis）算法实际上是要找到一个线性子空间，使得样本中的元素到线性子空间的投影误差平方和最小。

首先我们需要把所有数据进行特征缩放，保证数据的范围和均值。之后计算数据的协方差：

\[\Sigma=\frac{1}{m}\sum_{i=1}^mx^{(i)}(x^{(i)})^T\]

之后计算协方差矩阵的奇异值分解$\Sigma=UDV^T$。之后我们取$U$的前$k$列向量组成线性子空间即可。而线性子空间的投影矩阵为$U^T$的前$k$行$S^T$，记$z^{(i)}=S^Tx^{(i)}$。

这里$k$的选择方案是找到一个最小的$k$，满足：

\[[\sum_{i=1}^m\|x^{(i)}-Sz^{(i)}\|^2]/[\sum_{i=1}^m\|x^{(i)}\|^2]\leq 0.01\]

左边的部分实际上可以通过更简单的方式计算得到：

\[[\sum_{i=1}^m\|x^{(i)}-Sz^{(i)}\|^2]/[\sum_{i=1}^m\|x^{(i)}\|^2]=1-[\sum_{i=1}^kD_{i,i}]/[\sum_{i=1}^nD_{i,i}]\]

异常检测

异常检测可以用于检测一个物体的运行是否正常。此时假说函数$h(x)$类似于逻辑回归中的假说函数，即表示物体运行正常的概率，而$x$可能是物体当前的状态、最近的活动记录等。如果$h(x)\lt \epsilon$，那么我们就认为发生了异常。

这个技术可以用于检测一个用户是否被盗号，一台机器是否运行正常等等。

首先我们要为所有特征都训练一个最大似然高斯分布模型，这样就能得到总共$n$个高斯分布$\mu_1,\mu_2,\ldots,\mu_n,\sigma_1,\ldots,\sigma_n$。之后有

\[h(x)=\prod_{i=1}^np(x_i;\mu_i,\sigma_i)\]

在训练异常检测模型的时候，我们会使用正常物体（即标签值为$1$）的样本训练我们的模型，但是交叉集和测试集需要同时带上异常的物体。

可以发现逻辑回归同样可以解决异常检测的问题，但异常检测模型在异常样本比例非常小但是总样本数量比较大的时候表现很好，并且计算非常高效。

适合选择作为特征的属性，应该拥有类似高斯分布的钟形分布。

还有一种方式就是直接使用多元高斯分布而不是为每个特征建立一个高斯分布，这样的好处是多元高斯分布能检测到不同特征之间的关联关系，而单元高斯分布则不需要手动创建一些代表这类关联关系的特征。但是多元高斯分布的计算成本很高。

高斯分布

高斯分布（即正态分布）用于的概率密度函数为：

\[p(x;\mu,\sigma)=\frac{1}{\sigma \sqrt{2\pi}}\exp(-\frac{(x-\mu)^2}{2\sigma^2})\]

其中$\mu$是高斯分布的期望，而$\sigma$是高斯分布的标准差。

对于给定的实数$x^{(1)},x^{(2)},\ldots,x^{(m)}$，此时似然函数为：

\[L(\mu,\sigma;x^{(1)},x^{(2)},\ldots,x^{(m)})=\prod_{i=1}^mp(x^{(i)};\mu,\sigma)\]

要使似然函数最大，不难推出：

\[\left\{ \begin{array}{rcl} \mu&=&\frac{1}{m}\sum_{i=1}^mx^{(i)}\\ \sigma^2&=&\frac{1}{m}\sum_{i=1}^m(x^{(i)}-\mu)^2 \end{array} \right.\]

多元高斯分布

考虑$n$元高斯分布，此时$\mu\in \mathbb{R}^n$，$\Sigma\in \mathbb{R}^{n\times n}$。多元高斯分布的概率密度函数为：

\[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^{(1)},\ldots,x^{(m)}$。

多元高斯分布的最大似然估计：

\[\left\{ \begin{array}{rcl} \mu&=&\frac{1}{m}\sum_{i=1}^mx^{(i)}\\ \Sigma&=&\frac{1}{m}\sum_{i=1}^m(x^{(i)}-\mu)(x^{(i)}-\mu)^T \end{array} \right.\]

注意这里一定要保证$m\gt n$，否则$\Sigma$不可逆。

推荐系统

推荐系统解决的问题是已知一些用户对一些商品的评价，要求对于给定用户和商品，推测出它的可能评价。

考虑一个商品推荐系统。

记$n_u$表示用户人数，$n_g$表示商品人数，$r(i,j)$表示用户$i$是否对商品$j$做出过平方（$1$表示是$0$表示否）。$y^{(i,j)}$表示用户$i$对商品$j$做出的评分，$m^{(i)}$表示用户$i$实际对多少部电影做出了评价。

基于内容的推荐算法

假设我们有每个商品的各个参数（作为特征），那么我们可以使用基于内容的推荐算法来做推荐。

我们需要为每个用户$u$训练一个参数$\theta_u$（一个向量），而对于电影$x$，用户的预估评分为$h_u(x)=\theta_ux$。即这是一个线性回归问题。

基于内容的推荐算法的惩罚函数为：

\[J(\theta^{(1)}, \ldots, \theta^{(n_u)})=\frac{1}{2}\sum_{i=1}^{n_u}\sum_{j:r(i,j)=1}((\theta^{(i)})^Tx^{(j)}-y^{(j)})^2+\frac{\lambda}{2}\sum_{i=1}^{n_u}\|\theta^{(i)}\|^2\]

协同过滤

基于内容的推荐算法要求我们能正确的计算商品的各个特征。但是这在很多时候是不能被正确评估的。

但是如果我们知道了每个用户的偏好$\theta_1,\ldots,\theta_{n_u}$，那么根据用户对商品的评分，就能反向推导出商品的各个特征了。

当然上面提到的依旧是一个线性回归问题，只不过这时候我们的样本是用户，模型是商品而已。

\[J(x^{(1)}, \ldots, x^{(n_g)})=\frac{1}{2}\sum_{i=1}^{n_g}\sum_{j:r(j,i)=1}((\theta^{(i)})^Tx^{(j)}-y^{(j)})^2+\frac{\lambda}{2}\sum_{i=1}^{n_g}\|x^{(i)}\|^2\]

协同过滤算法

可以发现基于内容的推荐算法可以从商品特征计算用户偏好，而协同过滤可以通过用户偏好计算商品的特征。不断重复这两个过程，我们可以得到不断精确的用户偏好和商品特征。

协同过滤算法（又名低秩矩阵分解）去除了上面辗转的部分，将两个惩罚函数合并为一个，因此可以将商品特征和用户偏好同时求出。

\[J(x^{(1)}, \ldots, x^{(n_g)},\theta^{(1)}, \ldots, \theta^{(n_u)})=\frac{1}{2}\sum_{i,j:r(i,j)=1}((\theta^{(i)})^Tx^{(j)}-y^{(j)})^2+\frac{\lambda}{2}\sum_{i=1}^{n_g}\|x^{(i)}\|^2+\frac{\lambda}{2}\sum_{i=1}^{n_u}\|\theta^{(i)}\|^2\]

我们的算法流程如下：

  1. 均值初始化
  2. 随机初始化$x^{(1)},\ldots,x^{(n_g)},\theta^{(1)}, \ldots, \theta^{(n_u)}$。
  3. 进行梯度下降。

梯度下降所需要的偏导数的计算如下：

\[\left\{ \begin{array}{rcl} \frac{\partial }{\partial \theta^{(u)}_i}J(\ldots)&=&\sum_{j:r(u,j)=1}[(\theta^{(u)})^Tx^{(j)}-y^{(j)}]x^{(j)}_i+\lambda\theta^{(u)}_i\\ \frac{\partial }{\partial x^{(g)}_j}J(\ldots)&=&\sum_{i:r(i,g)=1}[(\theta^{(i)})^Tx^{(g)}-y^{(g)}]\theta^{(i)}_j+\lambda x^{(g)}_j\\ \end{array} \right.\]

注意这个算法中并不需要为输入增加额外的一列$1$。

由于协同过滤算法可以同时分析出商品的重要特征，因此我们可以利用2范数距离来判断两个商品是否相似，从而推荐相似的内容给用户。

均值初始化

考虑对于一个新用户$t$，他尚未对任何商品做出评分，那么该如何推荐呢。实际上用上面的协同过滤算法得到的$\theta^{(t)}=0$（因为正则化的原因），因此预估出来他对所有电影的评分都将是$0$。

一种可行的技术是，将每个人对每件商品的评分减去这件商品的评分的平均分。之后在还原的时候$0$就会被还原为平均分，这意味着平均分最高的商品会被推荐给新用户。

均值初始化只适合对同一件商品执行，对于没有被评价过的商品，其预估评分并不重要。

参考资料

  • 吴恩达机器学习系列课程
  • 《统计学习方法》