《模式识别与机器学习》

机器学习 读书笔记 DOING

---

1 绪论

模式识别领域关注的是利用计算机算法自动发现数据中的规律，以及使用这些规律采取将数据分类等行动。正确分类与训练集不同的新样本的能力叫做泛化（generalization）。
原始数据通常需要预处理（pre-processed），变换到新的变量空间。预处理阶段有时候也叫做特征提取（feature extration）。
分类（classification）：目标是给每个向量分配到有限数量离散标签中的一个；
回归（regression）：要求输出由一个或者多个连续变量组成；
聚类（clustering）：目标是发现数据中相似样本的分组；
密度估计（density estimation）：目标是决定输入空间中数据的分布；
数据可视化（visualization）：数据从高维空间投影到二维或者三维空间；

1.1 多项式曲线拟合

$$y(x,w)=w_0+w_1x+...+w_Mx^M=\sum_{j=0}^Mw_jx^j$$
最小化： $$E(w)={{1\over2}{\sum_{n=1}^N(y(x_n,w)-t_n)^2}}$$
当M值设置过小时，欠拟合，设置过大时，容易过拟合（over fitting）。过拟合的原因是因为数据本身有噪声，而拟合的时候使得多项式被调节成了与目标值的随机噪声相符。当数据集的规模增加时，过拟合的问题就变得不那么严重。
控制过拟合现象的一种技术是正则化（regularization）。给误差函数增加一个惩罚项，使得系数不会达到很大的值。最简单的形式就是采用所有系数的平方和的形式。$\lambda$项控制正则化相对于平方和误差项的重要性。
$$\bar E(w)={1\over2}\sum_{n=1}^N(y(x_n,w)-t_n)^2)+{\lambda \over 2}||w||^2$$ $$||w||^2 = w^Tw=w_0^2+w_1^2+...+w_n^2$$
通常$w_0$从正则项中省略，包含会使得结果依赖于目标变量原点的选择。

1.2 概率论

不确定性，可以由测量的误差引起，也可能由数据集的有限大小引起。

加和规则

$p(X=x_i)=\sum_{j=1}^Lp(X=x_i,Y=y_j) -> p(X)=\sum_Y p(X,Y)$

乘积规则

$p(X=x_i,Y=y_j) = p(Y=y_j|X=x_i)p(X=x_i) -> p(X,Y)=p(Y|X)p(X)$

贝叶斯定理

$p(Y|X)={p(X|Y)p(Y)\over p(X)}$

$p(X)=\sum_Yp(X|Y)p(Y)$

名词解释

先验概率，对应于取盒子的概率
后验概率，根据选出来的东西而计算出来的选择某个盒子的概率

如果两个变量的联合分布可以分解成两个边缘分布的乘积，即$p(X,Y)=p(X)p(Y)$则称X和Y相互独立。

1.2.1 概率密度

连续环境下，x位于区间(a,b)之间的概率由下式给出

$$p(x\in (a,b))=\int_a^bp(x)dx$$
则有 $$p(x)\ge 0$$ $$\int _{-\infty}^\infty p(x)dx = 1$$

考虑变量变换 $x=g(y)$，则有

$$p_y(y)=p_x(x)|{dx\over dy}|=p_x(g(y))|g'(y)|$$ 概率密度最大值的概念取决于变量的选择。

累积分布函数

位于区间$(-\infty, z)$的x的概率，$P(z)=\int_{-\infty}^z p(x)dx$

联合概率密度

几个连续变量，整体记住向量x，则可以有$p(x)=p(x_1,...x_D)$，使得x落在包含点x的无穷小体积$\delta x$的概率由$p(x)\delta x$给出。

法则

概率的加和规则、乘积规则、贝叶斯同样满足
$p(x)=\int p(x,y)dy$
$p(x,y)=p(y|x)p(x)$

1.2.2 期望和协方差

期望 expectation

在概率分布p(x)下，函数f(x)的平均值
$E[f]=\sum_x p(x)f(x)$
$E[f]=\int p(x)f(x)dx$
抽样情况下： $E[f]\simeq{1\over N}\sum_{n=1}^N f(x_n)$
$E_x[f(x,y)]$表示函数f(x,y)关于x的分布的平均，是y的一个函数
$E_x[f|y]=\sum_x p(x|y)f(x)$为条件期望

方差 variance

定义为$var[f]=E[(f(x)-E[f(x)])^2]$，度量了f在均值附近变化性的大小。
也可以写成$var[f]=E[f(x)^2]-E[f(x)]^2$
自变量x的方差为$var[x]=E[x^2]-E[x]^2$

协方差 covariance

$$cov[x,y]=E_{x,y}[\{x-E[x]\}\{y-E[y]\}]=E_{x,y}[xy]-E[x]E[y]$$
表示多大程度上两个变量会共同变化，如果相互独立，则其值为0
$cov[x,y]=E_{x,y}[\{x-E[x]\}\{y^T-E[y^T]\}]=E_{x,y}[xy^T]-E[x]E[y^T]$

1.2.3 贝叶斯概率

$$p(w|D)={p(D|w)p(w)\over p(D)}$$

似然函数

$p(D|w)$似然函数，likelihood function，由观测数据集D来估计，可以看成参数向量w的函数，表达在不同的参数向量w下，观测数据出现的可能性的大小，似然函数不是w的概率分布，并且其关于w的积分并不（一定）等于1.

概率观点认为w是一个固定的参数，它的值由某种形式的估计来确定。估计的误差通过考察可能的数据集D的概率分布来得到。贝叶斯观点看，只有一个数据集D，参数的不确定性通过w的概率分布来表达。批评是先验的选择通常是为了计算的方便而不是为了反映先验的知识。先验选择不好可能会得到错误的结果。

最大似然估计

其中w值是使其似然函数达到最大的w值。似然函数的负对数被叫做误差函数，由于负对数是单调递减的函数，最大化似然函数等价于最小化误差函数。

1.2.4 高斯分布

也称为正态分布

$$\mathcal N(x|u,\sigma^2)={1\over (2\pi\sigma^2)^{1\over 2}}exp\{-{1\over 2\sigma^2}(x-u)^2\}$$
u为均值，$\sigma^2$被称为方差。众数与均值相等。

独立同分布

独立地从相同的数据点中抽取的数据点被称为独立同分布（independent and identically distributed）。
$p(\mathbf x|u,\sigma^2)=\prod_{n=1}^N\mathcal N(x_n|u,\sigma^2)$

最大似然方法

采用似然最大化概率求参数。
$\ln p(\mathbf x|u,\sigma^2)=-{1\over 2\sigma^2}\sum_{n=1}^N(x_n-u)^2-{N\over 2}\ln \sigma^2-{N\over 2}\ln(2\pi)$
最大化可得$u_{ML}={1\over N}\sum_{n=1}^Nx_n$，就是样本均值。方差最大似然解$\sigma^2_{ML}={1\over N}\sum_{n=1}^N(x_n-u_{ML})^2$
均值为实际均值。$E[U_{ML}]=u$
最大似然方法系统化低估了分布的方差。$E[\sigma^2_{ML}]=({N-1\over N})\sigma^2$

1.2.5 重新考察曲线拟合问题

多曲线拟合可以通过误差最小化问题来表示。曲线拟合问题的模目标是能够根据N个输入组成的数据集和他们对应的目标t，再给出输入变量的x的新值的情况下，对目标变量t进行预测。我们假定给定x的值，对应的t值服从高斯分布，分布的均值为y(x, w)，精度为$\beta$，其值有$\beta^{-1}=\sigma^2$，于是有

$$p(t|x,w,\beta)=\mathcal N(t|y(x,w,\beta^{-1})$$
我们现在以训练数据通过最大似然法来确定未知参数的值。有 $$p(t|x,w,\beta)=\prod_{n=1}^N\mathcal N(t_n|y(x_n,w),\beta^{-1})$$
进而有 $$\ln p(t|x,w,\beta)=-{\beta \over 2}\sum_{n=1}^N\{y(x_n,w)-t_n\}^2+{N\over 2}\ln\beta-{N\over 2}\ln(2\pi)$$ 由此可见，再高斯噪声的假设下，平方和误差函数是最大化似然函数的一个自然结果。同样可得 $${1\over \beta_{ML}}={1\over N}\sum_{n=1}^N\{y(x_n,w_{ML})-t_n\}^2$$
现在假设引入在多项式系数w上的先验分布。 $$p(w|\alpha)=\mathcal N(w|0,\alpha^{-1}I)=({\alpha\over 2\pi})^{M+1\over 2}exp\{-{\alpha\over 2}w^tw\}$$
根据贝叶斯定理有 $$p(w|x,t,\alpha,\beta)=p(t|x,w,\beta)p(w|\alpha)$$ 最大化后验概率来确定w。称为最大后验（maximum posterior, MAP）。取负对数，就是要最小化下公式 $${\beta \over 2}\sum_{n=1}^N\{y(x_n,w)-t_n\}^2+{\alpha\over 2}w^Tw$$ 由此有最大化概率等价于最小化正则化的平方和误差函数，正则化参数为$\alpha\over \beta$。

1.2.6 贝叶斯曲线拟合

贝叶斯方法就是使用概率的加和和乘积规则。

$$p(t|x,\mathbf x,\mathbf t)=\int p(t|x,\mathbf w)p(\mathbf w|\mathbf x,\mathbf t)d\mathbf w$$
解答可得 $$p(t|x,\mathbf x,\mathbf t)=\mathcal N(t|m(x),s^2(x))$$
$$m(x)=\beta\phi(x)^TS\sum_{n=1}^NS\phi(x_n)t_m$$
$$s^2(x)=\beta^{-1}+\phi(x)^TS\phi(x)$$
$$S^{-1}=\alpha I+\beta\sum_{n=1}^N\phi(x_n)\phi(x_n)^T$$

1.3 模型选择

存在一个最优的多项式阶数，能够给出最好的结果。多项式的阶数控制了模型的自由参数的个数。因此控制了模型的复杂度。
交差验证，选择数据集的$S-1\over S$进行训练，同时使用所有的数据进行评估表现。缺点是随着S的增加训练很耗时。而且可能单个模型有多个复杂度参数（可能有若干个正则化参数），其组合可能为参数个数的指数函数。

1.4 维度灾难

考虑测试点与近处的训练点之间的关系。简单方式是将输入空间划分成小的单元格。判断其输入哪个输入格，类别就是所属单元格内最多的类。
多项式拟合会随着维度的增加而导致系数数量快速增大。
D维空间的半径为r的球体的体积一定是$r^D$的倍数，有$V_D(r)=K_Dr^D$，因此有半径$1-\epsilon$与1之间的部分占球的总体积百分比

$${V_D(1)-V_D(1-\epsilon)\over V_D(1)}=1-(1-\epsilon)^D$$ 因此可得对于高维空间中，一个球体的大部分体积都聚集在表面附近的薄球壳上。对于大的D值，高斯分布的概率质量也集中再薄球壳上。

1.5 决策论

从训练数据集中确定p(x,t)是一个推断问题，决策论就是在给定的合适的概率的前提下，如何进行最优的决策。

1.5.1 最小化错误分类率

$p(mistake)=p(x\in R_1,C_2)+p(x\in R_2,C_1)=\int_{R_1}p(x,C_2)dx+\int_{R_2}p(x,C_1)dx$
我们将每个x分配到后验概率$p(C_k|x)$中最大的类别中，那么我们分类错误的概率就会最小。
对于K类，最大化正确率会简单一些

$$p(correct)=\sum_{k=1}^Kp(x\in R_k,C_k)=\sum_{k=1}^K \int_{R_k}p(x,C_k)dx$$

1.5.2 最小化期望损失

最优解是使损失函数最小的解。损失函数依赖于真实的类别。

$$E[L]=\sum_k\sum_j\int_{R_j}L_{kj}p(x,C_k)dx$$
使用乘法规则$p(x,C_k)=p(C_k|x)p(x)$消除共同因子p(x)。由此，最小化期望损失的决策规则是对于每个新的x，把它分到能使下式取得最小值的第j类： $$\sum_kL_{kj}p(C_k|x)$$

1.5.3 拒绝选项

在某些分类不很明确的情况下，避免做出决策是更合适的选择。这样会使得模型的分类错误率降低。
引入一个阀值$\theta$，拒绝后验概率$p(C_k|x)$小于等于该值的输入x。值为1，所有值都拒绝，值小于$1\over k$将会确保没有样本被拒绝。

1 连续潜在变量

12.1 主成因分析

又称为PCA，应用领域包括维度降低、有损数据压缩、特征抽取、数据可视化。

12.1.1 最大方差形式

13 顺序数据

13.1 马尔科夫模型

用概率的乘积规则来表示观测序列的联合概率分布。形式为

$$p(x_1,...x_N)=p(x_1)\prod_{n=2}^Np(x_n|x_1,x_2,...x_{n-1})$$
假设右侧的每个条件概率分布只与最近的一次观测有关，而独立于其他所有之前的观测，就为一阶马尔科夫模型链，N次观测的联合概率分布为 $$p(x_1,...x_N)=p(x_1)\sum_{n=1}^Np(x_n|x_{n-1})$$ 于是有 $$p(x_n|x1,...x_{n-1})=p(x_n|x_{n-1})$$
限制了概率分布 $p(x_n|x_{n-1})$ 为相等的。
二阶 $$p(x_1,...x_N)=p(x_1)p(x_2|x_1)\prod_{n=3}^Np(x_n|x_{n-1},x_{n-2})$$ 通过d-划分或者直接计算，可以看到给定 $x_{n-1}$ 和 $x_{n-2}$ 的条件下 $x_n$ 的条件概率分布与所有的 $x_1,...x_{n-3}$ 的观测无关。