聚类是无监督机器学习方法的一种。

K均值聚类

K均值聚类的算法流程：

1. 给各个簇中心$\mu_1,\dots,\mu_c$以适当的初值

2. 更新样本$x_1,\dots,x_n$对应的簇标签$y_1,\dots,y_n$

   $$y_i \leftarrow \mathop{argmin}_{y\in \lbrace 1,\dots,c \rbrace}||x_i - \mu_y||^2,i=1,\dots,n$$

3. 更新各个簇中心$\mu_1,\dots,\mu_c$

   $$\mu_y \leftarrow \frac{1}{n_y}\sum_{i:y_i=y}x_i,y=1,\dots,c$$

   上式中，$n_y$为属于簇$y$的样本总数

4. 直到簇标签达到收敛精度为止，重复上述2、3步的计算。

高维数据的处理是相当困难的，一般称为维数灾难。为了使机器学习算法从维数灾难中解放出来，一般采取的有效方法是尽量保持输入数据中包含的所有信息，并对其维数进行削减。

线性降维的原理

无监督降维的目的，是把高维的训练输入样本$\lbrace x_i \rbrace_{i=1}^n$变换为低维的训练样本$\lbrace z_i \rbrace_{i=1}^n$，并在降维后还能尽可能地保持其原本包含的所有信息。

通过$x_i$的线性变换求解$z_i$的时候，即使用维数为$m \times d$的投影矩阵$T$根据下式

$$z_i = Tx_i$$

来求解$z_i$的时候，称为线性降维。

中心化：

$x_i \leftarrow x_i \frac{1}{n} \sum_{i’=1}^n x_{i’}$

灵活应用输入数据的流形构造

半监督学习会首先假定输入概率密度$p(x)$和条件概率密度$p(y|x)$之间具有某种关联，利用对输入概率密度$p(x)$的估计来辅助对条件概率密度$p(y|x)$的估计，进而使得最终的学习精度得以提升。

流形是一数学用于，一般指局部具有欧几里得空间性质的图形，在半监督学习里指的是输入空间的局部范围。半监督学习中流形的假设，即输入数据只出现在某个流形上，输出则在该流形上平滑的变化。

高斯核函数实际上是灵活运用了流行的假设后形成的模型

$$f_{\theta}(x)=\sum_{j=1}^n \theta_j K(x,x_j), K(x,c)=exp(-\frac{||x-c||^2}{2h^2})$$

即通过在训练输入样本$\lbrace x_i \rbrace_{i=1}^n$上设置平滑的高斯核函数，进而使得输入数据在流形上学习得到平滑的输入输出函数。

半监督学习在核函数的构成中，也应用了只有输入数据的训练样本$\lbrace x_i \rbrace_{i=n+1}^{n+n’}$

$$f_{\theta}(x)=\sum_{j=1}^{n+n'} \theta_j K(x,x_j)$$

另外，为了使训练输入样本的输出$\lbrace f_{\theta}(x_i) \rbrace_{i=n+1}^{n+n’}$拥有局部相似值，还需要添加约束条件。对于$l_2$正则化最小二乘学习的情况，有以下学习规则

$$\mathop{min}_{\theta}[\frac{1}{2}\sum_{i=1}^n(f_{\theta}(x_i)-y_i)^2 + \frac{\lambda}{2}||\theta||^2+ \frac{v}{4}\sum_{i,i'=1}^{n+n'}W_{i,i'}(f_{\theta}(x_i) - f_{\theta}(x_i'))^2]$$

其中第一项和第二项与$l_2$正则化最小二乘学习相对应。第三项是进行半监督学习所需的正则化项，称为拉普拉斯正则化。$v \ge 0$是调整流形的平滑性的半监督学习的正则化参数。$W_{i,i’} \ge0$是$x_i$和$x_{i’}$的相似度，当$x_i$和$x_{i’}$相似的时候，$W_{i,i’}$具有较大的值；当$x_i$和$x_{i’}$不相似的时候，$W_{i,i’}$具有较小的值。$W_{i,i’}$是对称的，即假定满足$W_{i,i’}=W_{i’,i}$。

异常检测，是指找出给定的输入样本$\lbrace x_i \rbrace_{i=1}^n$中包含的异常值的问题。

局部异常因子

局部异常因子，是指对偏离大部分数据的异常数据进行检测的方法。

从$x$到$x’$的可达距离

$$RD_k(x,x')=max(||x-x^{(k)}||,||x-x'||)$$

$x^{(k)}$表示的是训练样本$\lbrace x_i \rbrace_{i=1}^n$中距离$x$第$k$近的样本。

$x$的局部可达密度可由下式加以定义

$$LRD-k(x) = (\frac{1}{k} \sum_{i=1}^k RD_k(x^{(i)},x))^{-1}$$

$x$的局部可达密度，是从$x^{(i)}$到$x$的可达距离的平均值的倒数。

$x$的局部异常因子

$$LOF_k(x) = \frac{ \frac{1}{k} \sum_{i=1}^k LRD_k(x^{(i)})}{LRD_k(x)}$$

$LOF_k(x)$的值越大，$x$的异常度就越大。$LOF_k(x)$是$x^{(i)}$的局部可达密度的平均值和$x$的局部可达密度的比。当$x^{(i)}$的周围的密度比较高而$x$周围的密度比较低的时候，局部异常因子就比较大，$x$就会被看作是异常值。

局部异常因子，是遵循事先制定的规则(偏离大部分正常值的数据被认为是异常值)，寻找异常值的无监督的异常检测算法。

最小二乘学习法

 最小二乘学习法是对模型的输出$f_{\theta}(x_i)$和训练集输出$\lbrace y_i \rbrace_{i=1}^n$的平方误差

$$J_{LS}(\theta)=\frac{1}{2}\sum_{i=1}^n(f_{\theta}(x_i) - y_i)^2$$

为最小时的参数$\theta$进行学习

$$\hat{\theta}_{LS}=\mathop{argmin}_{\theta} J_{LS}(\theta)$$

平方误差$(f_{\theta}(x_i)-y_i)^2$是残差$f_{\theta}(x_i) - y_i$的$\mathcal{l}_2$范数，因此最小二乘学习法有时也称为$\mathcal{l}_2$损失最小化学习法。

 如果使用线性模型

$$f_{\theta}(x_i)=\sum_{j=1}^b \theta_i \phi_i (x)=\theta^{\intercal}\phi(x)$$

训练样本的平方差

$$J_{LS}(\theta)=\frac{1}{2}||\Phi \theta - y||^2$$

其中，$y=(y_1,\dots,y_n)^{\intercal}$是训练输出的$n$维向量，$\Phi$是下式中定义的$n\times b$阶矩阵，也称为设计矩阵

$$\Phi=\left[ \begin{matrix} \phi_1(x_1) & \cdots & \phi_b(x_1) \\ \vdots & \ddots & \vdots \\ \phi_1(x_n) & \cdots & \phi_b(x_n) \\ \end{matrix} \right]$$

训练样本的平方差$J_{LS}$的参数向量$\theta$的偏微分

$$\nabla_{\theta}J_{LS}=(\frac{\partial J_{LS}}{\partial \theta_1},\dots,\frac{\partial J_{LS}}{\partial \theta_b})^{\intercal} = \Phi^{\intercal}\Phi \theta - \Phi^{\intercal}y$$

将其微分设置为0，则

$$\hat{\theta}_{LS} = (\Phi^{\intercal}\Phi)^{-1}\Phi^{\intercal}y$$

对顺序为$i$的训练样本的平方差通过权重$\omega_i \ge 0$进行加权，然后采用最小二乘学习，这称为加权最小二乘学习法

$$\mathop{min}_{\theta} \frac{1}{2}\sum_{i=1}^n \omega_i (f_{\theta}(x_i)-y_i)^2$$

集成学习，是指把性能较低的多种弱学习器，通过适当组合而形成高性能的强学习器的方法。本章有介绍两种集成学习法，一种是对多个弱学习器独立进行学习的Bagging学习法，一种是对多个弱学习器依次进行学习的Boosting学习法。

剪枝分类

剪枝分类是属于弱学习器的一种单纯分类器。是指对于$d$次维的输入变量$x=(x^{(1)},\dots,x^{(d)})^{\intercal}$，任意选定其中的一维，通过将其值与给定的阈值相比较来进行分类的线性分类器。即以输入空间内的坐标轴与超平面进行正交的方式对模式进行分类。

剪枝分类器的自由度很低，但是具有计算成本低的优点。

线性模型

 在对函数$f$进行近似时，最简单的模型就是线性模型$\theta \times x$。$\theta$表示模型的参数，通过对参数进行学习，完成函数的近似计算。在实际应用中，经常会对线性模型进行扩展，使其变成基于参数的线性模型：

$$f_{\theta}(x)=\sum_{j=1}^b \theta_j \phi_j(x)=\theta^{\intercal}\phi(x)$$

 乘法模型是指，把一维基函数作为因子，通过使其相乘而获得多维基函数的方法：

$$f_{\theta}(x)=\sum_{j_1=1}^{b'} \dots \sum_{j_d=1}^{b'} \theta_{j1,\dots,j_d}\phi_{j1}(x^{(1)} \dots\phi_{jd}(x^{(d)}))$$

由于乘法模型随着维数的增加，计算量呈指数级增长的现象，称为维数灾难。

 加法模型是指，把一维的基函数作为因子，通过使其相加而获得多维基函数的方法：

$$f_{\theta}(x)=\sum_{k=1}^d \sum_{j=1}^{b'} \theta_{k,j} \phi_j(x^{(k)})$$

加法模型只会随着输入维数线性增长，但是，由于加法模型只考虑了一维基函数相加的情况，因此表现力要比乘法模型逊色许多。

在对多个相似的学习任务进行学习的时候，共享各学习任务的信息并同时对其进行求解的方法，往往比对各个学习任务单独进行求解有更高的学习精度。

多任务学习是在多个学习任务之间实现信息的共享、转移的一种学习方法

使用最小二乘回归的多任务学习

对于序号为$t$的回归任务，使用与参数$\theta_t = (\theta_{t,1},\dots,\theta_{t,b})^{\intercal}$相关的线性模型

$$\sum_{j=1}^b \theta_{t,j}\phi_j(x) = \theta_t^{\intercal} \phi(x)$$

基函数$\phi(x)$对所有的学习任务都相同。在多任务学习里，添加约束条件使各个任务的参数$\theta_1,\dots,\theta_T$具有相似的值，在此基础上对所有的参数$\theta=(\theta_1^{\intercal}, \dots, \theta_T^{\intercal})^{\intercal}$同时进行学习。

使用$l_2$正则化的最小二乘法对下式$J(\theta)$为最小时所对应的参数$\theta$进行学习

$$J(\theta) = \frac{1}{2}\sum_{i=1}^n (\theta_{t_i}^{\intercal} \phi(x_i) - y_i)^2+\frac{1}{2}\sum_{t=1}^T \lambda_t||\theta_t||^2 + \frac{1}{4}\sum_{t,t'=1}^T \gamma_{t,t'}||\theta_t - \theta_{t'}||^2$$

在这里，$\lambda_t \ge 0$是与序号为$t$的学习任务对应的$l_2$正则化参数0，$\gamma_{t,t’} \ge 0$是序号为$t$的学习任务和序号为$t’$的学习任务的相似度。对于所有的$t,t’=1,\dots,T$，当$\gamma_{t,t’} = 0$时，$J(\theta)$的第三项就没有了，这就对应于$T$个学习任务分别进行$l_2$正则化最小二乘学习。另一方面，如果$\gamma_{t,t’} > 0$的话，$\theta_t$和$\theta_{t’}$向着$l_2$范数的方向进行学习，即可实现多个学习任务间的信息共享。