Skip to content
Gonge

机器学习初步

· 12 min

机器学习初步(Introduction to Machine Learning)#

LDA (Linear Discriminant Analysis)#

LDA的基本原理就是寻找一个线或面、超面W\mathbf{W}，使得不同维度的数据点投影到W\mathbf{W}上时，其各个类之间的均值距离最为远，而类内的距离最为近。它就是一个根据已有数据求取这个W\mathbf{W}的问题。以鸢尾花数据集X为例，有三个类别i=Setosa, Versicolor, Virginicai=Setosa,\ Versicolor,\ Virginica，对于其间的每个维度：萼片长、萼片宽、花瓣长、花瓣宽，将每个维度的每个样本点到样本均值的距离计算出来，即用于评估一个类别内的离散程度：

Sw=∑i=13∑x∈Xi(x−μi)(x−μi)T\mathbf{S}_w=\sum_{i=1}^{3}\sum_{x\in X_i}{(\mathbf{x}-\boldsymbol{\mu}_i)(\mathbf{x}-\boldsymbol{\mu}_i)^T}

若有一个投影目标W\mathbf{W}，则WTSwW\mathbf{W}^T\mathbf{S}_w\mathbf{W}为Sw\mathbf{S}_w到W\mathbf{W}的投影，它评估了在这个投影上，每个投影点到投影中心的距离：

WTSwW\mathbf{W}^T\mathbf{S}_w\mathbf{W}

同样的，要使得各个类别中心距离尽量远，计算出各个类的均值距离，

Sb=∑i=13ni(μi−μ)(μi−μ)T\mathbf{S}_b=\sum_{i=1}^{3}{\mathbf{n}_i(\boldsymbol{\mu}_i-\boldsymbol{\mu})(\boldsymbol{\mu}_i-\boldsymbol{\mu})^T}

那么，WTSbW\mathbf{W}^T\mathbf{S}_b\mathbf{W}则为各个类的均值距离到W\mathbf{W}的投影，它评估了在这个投影上，每个类均值中心的距离。

据此，我们要最小化WTSwW\mathbf{W}^T\mathbf{S}_w\mathbf{W}，最大化WTSbW\mathbf{W}^T\mathbf{S}_b\mathbf{W}，有向量值函数：

J(W)=WTSbWWTSwW\mathbf{J}(\mathbf{W})=\frac{\mathbf{W}^T\mathbf{S}_b\mathbf{W}}{\mathbf{W}^T\mathbf{S}_w\mathbf{W}}

则LDA问题为求解J(W)\mathbf{J}(\mathbf{W})的最大值及其对应的W\mathbf{W}。我们只需要W\mathbf{W}的方向，则令WTSwW=1\mathbf{W}^T\mathbf{S}_w\mathbf{W}=1，则上述问题转化为一个优化求解问题：

max⁡ J(W)=WTSbW\max\ \mathbf{J}(\mathbf{W})=\mathbf{W}^T\mathbf{S}_b\mathbf{W} s.t. WTSwW=1s.t.\ \mathbf{W}^T\mathbf{S}_w\mathbf{W}=1

由拉格朗日乘数法，构造：

F(W)=WTSbW+λ(WTSwW−1=0)\mathbf{F}(\mathbf{W})=\mathbf{W}^T\mathbf{S}_b\mathbf{W}+\lambda(\mathbf{W}^T\mathbf{S}_w\mathbf{W}-1=0)

当F′(W)=0\mathbf{F}'(\mathbf{W})=0时，有：

SbW=λSwW\mathbf{S}_b\mathbf{W}=\lambda\mathbf{S}_w\mathbf{W}

随后对W\mathbf{W}进行数值求解。

Naive Bayes#

我们已经有了现成的样本x=(x1,x2,…,xn)x=\left(x_1,x_2,\ldots,x_n\right)，其已知的类别为yy。根据贝叶斯定理，有后验概率：

P(y∣x)=P(x∣y)P(y)P(x)P\left(y\mid x\right)=\frac{P\left(x\mid y\right)P\left(y\right)}{P\left(x\right)}

其中：P(y∣x)P\left(y\mid x\right)是给定样本xx的类别为yy的后验概率，P(x∣y)P\left(x\mid y\right)是给定类别yy的情况下样本xx的似然概率，P(y)P\left(y\right)是类别yy的先验概率，P(x)P\left(x\right)是样本xx的边缘概率。

那么，对于已知特征x=(x1,x2,…,xn)x=\left(x_1,x_2,\ldots,x_n\right)但是未知其类别yy的样本，我们期望得到y^\hat{y}作为其真实类别的估计值，那么上述式子给出了一个数值上的概率判断，对于每一类yy，将其P(y∣x)P\left(y\mid x\right)估计出来，选择具有最高后验概率的类别y^\hat{y}作为估计值。

朴素贝叶斯假设：对于任意类别yy，样本xx的特征是在条件yy下独立的。因此：

P(x∣y)=∏i=1nP(xi∣y)P\left(x\mid y\right)=\prod_{i=1}^{n}{P\left(x_i\mid y\right)}

P(y)P\left(y\right)为先验概率，由训练集可得，P(x)P\left(x\right)是该样本特征出现的概率，对于任意一个样本，我们求得的是，最大的后验概率，那么P(x)P\left(x\right)不影响我们对于相对大小值的比较。因此，简化为：

P(y∣x)∝∏i=1nP(xi∣y)P(y)P\left(y\mid x\right)\propto\prod_{i=1}^{n}{P\left(x_i\mid y\right)P\left(y\right)}

选择具有最高后验概率的类别：

y^=arg⁡max⁡yP(y∣x)=arg⁡max⁡y∏i=1nP(xi∣y)P(y)\hat{y}=\arg\max_y P\left(y\mid x\right)=\arg\max_y \prod_{i=1}^{n}{P\left(x_i\mid y\right)P\left(y\right)}

在高斯朴素贝叶斯中：假设每个特征在给定类别的条件下遵循正态分布，那么有：

计算条件类的特征均值：

μi,y=1Ny∑j:yj=yxi,j\mu_{i,y}=\frac{1}{N_y}\sum_{j:y_j=y} x_{i,j}

条件类的特征方差：

σi,y2=1Ny−1∑j:yj=y(xi,j−μi,y)2\sigma_{i,y}^2=\frac{1}{N_y-1}\sum_{j:y_j=y}\left(x_{i,j}-\mu_{i,y}\right)^2

最终：

xi∣y∼N(μi,y,σi,y2)x_i|y \sim N(\mu_{i,y},\sigma_{i,y}^2)

则有概率密度函数可得：

f(xi∣y)=12πσi,y2e−(xi−μi,y)22σi,y2f\left(x_i\mid y\right)=\frac{1}{\sqrt{2\pi\sigma_{i,y}^2}}e^{-\frac{\left(x_i-\mu_{i,y}\right)^2}{2\sigma_{i,y}^2}}

使用最概似然估计，则P(xi∣y)=f(xi∣y)P\left(x_i\mid y\right)=f\left(x_i\mid y\right)，用做概率估计。

为了避免数值计算过程中，P(xi∣y)P(y)P\left(x_i\mid y\right)P\left(y\right)不断累乘造成的数值过小以及其带来的浮点运算的数值下溢、精度折损严重，对其取对数，即：

y^=arg⁡max⁡yln⁡P(y)+∑i=1nln⁡P(xi∣y)\hat{y}=\arg\max_y \ln P\left(y\right)+\sum_{i=1}^{n}{\ln P\left(x_i\mid y\right)}

计算得出即为最终估计值。

SVM (Support Vector Machine)#

对于线性可分的数据集，其有n个特征维度，为X\mathbf{X}，分为2类y=1,−1\mathbf{y}=1,-1。SVM要找到一个线性超平面wTx+b=0\mathbf{w}^T\mathbf{x}+b=0可以将不同类别的数据点完全分开，同时也需要使得找到的平面是”最优”的，b为常数。即不同类别的点到这个超平面wTx+b=0\mathbf{w}^T\mathbf{x}+b=0的距离最远，在直观上就是wTx+b=0\mathbf{w}^T\mathbf{x}+b=0能最大程度地区分不同的类。

对于任意的样本点xi∈X\mathbf{x}_i\in\mathbf{X}到超平面wTx+b\mathbf{w}^T\mathbf{x}+b的距离did_i为：

di=∣wTxi+b∣∣∣w∣∣d_i = \frac{|\mathbf{w}^T\mathbf{x}_i + b|}{||\mathbf{w}||}

若wTxi+b>0\mathbf{w}^T\mathbf{x}_i + b>0，将样本点归为正类，yi=1y_i=1，若wTxi+b<0\mathbf{w}^T\mathbf{x}_i + b<0，将样本点归为负类，yi=−1y_i=-1。我们希望简化dd，同时统一归类的约束条件。由于w,b\mathbf{w},b为待估参数，我们总能够找到w′,b′\mathbf{w}',b'使得：

w′Txi+b′≥1,yi=1\mathbf{w}'^T\mathbf{x}_i + b' \geq 1, \quad y_i = 1 w′Txi+b′≤−1,yi=−1\mathbf{w}'^T\mathbf{x}_i + b' \leq -1, \quad y_i = -1

成立的同时令前面所述的约束条件成立，通过yi(w′Txi+b′)y_i(\mathbf{w}'^T\mathbf{x}_i + b')统一约束条件为：

yi(w′Txi+b′)≥1y_i(\mathbf{w}'^T\mathbf{x}_i + b') \geq 1

同时，通过yi(wTxi+b)≥1y_i(\mathbf{w}^T\mathbf{x}_i + b) \geq 1可知，我们总可以找到离缩放的超平面w′\mathbf{w}'最近的两个不同类别的样本点d+d_+与d−d_-，其对应的样本点x+\mathbf{x}_+与x−\mathbf{x}_-作为支持向量，有：

d++d−=2∣∣w′∣∣d_+ + d_- = \frac{2}{||\mathbf{w}'||}

最终，为了简化优化求解问题，将线性SVM的优化基本形式写为：

min⁡12∣∣w∣∣2\min \frac{1}{2}||\mathbf{w}||^2 s.t.yi(wTxi+b)≥1s.t. \quad y_i(\mathbf{w}^T\mathbf{x}_i + b) \geq 1

通过拉格朗日乘子法，有拉格朗日函数：

L(w,b,λ)=12∣∣w∣∣2+∑i=1nλi(1−yi(wTxi+b))L(\mathbf{w},b,\boldsymbol{\lambda}) = \frac{1}{2}||\mathbf{w}||^2 + \sum_{i=1}^n \lambda_i(1 - y_i(\mathbf{w}^T\mathbf{x}_i + b))

求：

∂L(w,b,λ)∂w=w−∑i=1nλiyixi=0\frac{\partial L(\mathbf{w},b,\boldsymbol{\lambda})}{\partial\mathbf{w}} = \mathbf{w} - \sum_{i=1}^n \lambda_i y_i \mathbf{x}_i = 0 ∂L(w,b,λ)∂b=−∑i=1nλiyi=0\frac{\partial L(\mathbf{w},b,\boldsymbol{\lambda})}{\partial b} = -\sum_{i=1}^n \lambda_i y_i = 0

代回原SVM得到对偶问题：

max⁡∑i=1nλi−12∑i=1n∑j=1nλiλjyiyjxiTxj\max \sum_{i=1}^n \lambda_i - \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n \lambda_i\lambda_j y_i y_j \mathbf{x}_i^T\mathbf{x}_j s.t.∑i=1nλiyi=0,λi≥0s.t. \quad \sum_{i=1}^n \lambda_i y_i = 0, \quad \lambda_i \geq 0

通过二次规划解得λ\boldsymbol{\lambda}，代回得到w,b\mathbf{w},b。

另外需要明白的一点是，由于SVM的特性，上述拉格朗日乘子法中，总满足KKT条件。

PCA (Principal Component Analysis)#

对于任意的数据集X\mathbf{X}，其具有n个样本，每个样本具有p个属性值，则可以将X\mathbf{X}表述为n×pn\times p的矩阵：

X=[x1,1⋯x1,p⋮⋱⋮xn,1⋯xn,p]=(x⋅1,⋯ ,x⋅p)\mathbf{X}=\begin{bmatrix} x_{1,1}&\cdots&x_{1,p}\\ \vdots&\ddots&\vdots\\ x_{n,1}&\cdots&x_{n,p} \end{bmatrix}=(\mathbf{x}_{·1},\cdots,\mathbf{x}_{·p})

PCA希望从这个样本集中抽离出其所有的p个特征，并从中选取最为主要的d个特征作为其最终降维的结果。剩余p−dp-d个维度由于对数据集的贡献不大被舍去，而不参与接下来更复杂的数据计算，这就主成分分析降维的主要目标。

根据线性代数相关理论，矩阵X\mathbf{X}中的xi,jx_{i,j}是在基E\mathbf{E}上的坐标值。其中：

Ep×p=[10⋯001⋯0⋮⋮⋱⋮00⋯1]p×p\mathbf{E}_{p\times p}=\begin{bmatrix} 1&0&\cdots&0\\ 0&1&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&1 \end{bmatrix}_{p\times p}

更直白地说，xi,jx_{i,j}就是各个样本在其各p个特征属性上的取值，这些属性是依靠现实世界的观测得到的，基E\mathbf{E}就是现实世界的观测基。观测的各个特征属性往往在一定程度上存在相关性，也就很难对上述原有的p个属性特征进行贡献的准确评估。我们可以计算样本的各个特征在基E\mathbf{E}上的协方差矩阵Σ\boldsymbol{\Sigma}。

首先，计算样本上各个特征的均值向量：

μp×1=(x⋅1‾,⋯ ,x⋅p‾)T\boldsymbol{\mu}_{p\times 1}=(\overline{\mathbf{x}_{·1}},\cdots,\overline{\mathbf{x}_{·p}})^T

令每一个样本减去均值向量：

X′=[x1,1−x⋅1‾⋯x1,p−x⋅p‾⋮⋱⋮xn,1−x⋅1‾⋯xn,p−x⋅p‾]\mathbf{X}^\prime=\begin{bmatrix} x_{1,1}-\overline{\mathbf{x}_{·1}}&\cdots&x_{1,p}-\overline{\mathbf{x}_{·p}}\\ \vdots&\ddots&\vdots\\ x_{n,1}-\overline{\mathbf{x}_{·1}}&\cdots&x_{n,p}-\overline{\mathbf{x}_{·p}} \end{bmatrix}

根据协方差的计算公式：Cov(xi,xj)=E[(x⋅i−x⋅i‾)(x⋅j−x⋅j‾)]\text{Cov}(x_i,x_j)=E[(\mathbf{x}_{·i}-\overline{\mathbf{x}_{·i}})(\mathbf{x}_{·j}-\overline{\mathbf{x}_{·j}})]，那么各个样本属性特征的协方差为：

Cov(x⋅i,x⋅j)=1n−1∑k=1n(xk,i−x⋅i‾)(xk,j−x⋅j‾)\text{Cov}(\mathbf{x}_{·i},\mathbf{x}_{·j})=\frac{1}{n-1}\sum_{k=1}^{n}(x_{k,i}-\overline{\mathbf{x}_{·i}})(x_{k,j}-\overline{\mathbf{x}_{·j}})

则协方差矩阵为：

Σ=1n−1X′TX′\boldsymbol{\Sigma}=\frac{1}{n-1}{\mathbf{X}^\prime}^T\mathbf{X}^\prime

根据线性空间与基的理论，我们可以试图寻找到另一组正交基B\mathbf{B}，令样本在这一组基的映射点所包含的p个特征相互独立，那么我们就可以对在空间B\mathbf{B}内的特征进行贡献评估，并大胆舍去没有什么贡献的特征，将具象特征转换为抽象特征。设Zp×n\mathbf{Z}_{p\times n}就是相互独立的抽象特征观察点，有：

XE=ZB\mathbf{X}\mathbf{E}=\mathbf{Z}\mathbf{B}

那么我们期待得到组成Z\mathbf{Z}的各个特征彼此独立，若Λ\boldsymbol{\Lambda}为一个对角矩阵，有Z\mathbf{Z}与X\mathbf{X}相同的方法求得的Z\mathbf{Z}对应p个特征的协方差矩阵：

ΣZ=1n−1Z′TZ′=Λ\boldsymbol{\Sigma}_\mathbf{Z}=\frac{1}{n-1}{\mathbf{Z}^\prime}^T\mathbf{Z}^\prime=\boldsymbol{\Lambda}

现在问题来到了两个岔路口，从正交基的角度来说XE=ZB\mathbf{X}\mathbf{E}=\mathbf{Z}\mathbf{B}，若X\mathbf{X}为方阵，我们直接利用这个等式可以得到：

X′E=Z′B\mathbf{X}^\prime\mathbf{E}=\mathbf{Z}^\prime\mathbf{B} Z′=X′BT\mathbf{Z}^\prime=\mathbf{X}^\prime\mathbf{B}^T

代入ΣZ\boldsymbol{\Sigma}_\mathbf{Z}中得到：

ΣZ=B1n−1X′TX′BT=BΣBT\boldsymbol{\Sigma}_\mathbf{Z}=\mathbf{B}\frac{1}{n-1}{\mathbf{X}^\prime}^T\mathbf{X}^\prime\mathbf{B}^T=\mathbf{B}\boldsymbol{\Sigma}\mathbf{B}^T

它演变为一个线性代数中的经典问题，Σ\boldsymbol{\Sigma}为一个实对称矩阵，那么我们要求得的是一个正交矩阵BT\mathbf{B}^T，使得二次型Σ\boldsymbol{\Sigma}标准化。那么我们只需要求出Σ\boldsymbol{\Sigma}的特征值以及特征向量，再对特征向量组成进行施密特正交化法，即可求出B\mathbf{B}以及Λ\boldsymbol{\Lambda}，并得到我们想要的Z\mathbf{Z}。

现实中不可能实现样本X\mathbf{X}总是一个方阵。在另一条路上，从Σ\boldsymbol{\Sigma}出发。由于Σ\boldsymbol{\Sigma}为一个实对称矩阵，它一定可以被正交矩阵Q\mathbf{Q}化为标准二次形：

QTΣQ=Λ\mathbf{Q}^T\boldsymbol{\Sigma}\mathbf{Q}=\boldsymbol{\Lambda} QT1n−1X′TX′Q=Λ\mathbf{Q}^T\frac{1}{n-1}{\mathbf{X}^\prime}^T\mathbf{X}^\prime\mathbf{Q}=\boldsymbol{\Lambda}

只要令Z′=X′Q\mathbf{Z}^\prime=\mathbf{X}^\prime\mathbf{Q}，不去关心另一组基B\mathbf{B}是什么，这样也求出Z\mathbf{Z}与Λ\boldsymbol{\Lambda}，最终有：

1n−1Z′TZ′=1n−1QTX′TX′Q=QT1n−1X′TX′Q=QTΣQ=Λ\frac{1}{n-1}{\mathbf{Z}^\prime}^T\mathbf{Z}^\prime=\frac{1}{n-1}\mathbf{Q}^T{\mathbf{X}^\prime}^T\mathbf{X}^\prime\mathbf{Q}=\mathbf{Q}^T\frac{1}{n-1}{\mathbf{X}^\prime}^T\mathbf{X}^\prime\mathbf{Q}=\mathbf{Q}^T\boldsymbol{\Sigma}\mathbf{Q}=\boldsymbol{\Lambda}

综上所述，已经实现了将现实存在相关性的具象特征转换为抽象的相互独立的特征，接下PCA想要评价这些抽象特征的重要性。根据对角化理论以及二次型标准化法：

Λp×p=[λ1⋯0⋮⋱⋮0⋯λp]\boldsymbol{\Lambda}_{p\times p}=\begin{bmatrix} \lambda_1&\cdots&0\\ \vdots&\ddots&\vdots\\ 0&\cdots&\lambda_p \end{bmatrix}

Λp×p\boldsymbol{\Lambda}_{p\times p}为抽象特征间的协方差矩阵，其中λi\lambda_i为Z′\mathbf{Z}^\prime抽象样本集中抽象特征ii的方差。方差越大说明它在这个样本中的变动情况越大，是在p维空间中张成这个样本对应的p维空间体的重要维度。对λi\lambda_i排序，选取最大的d个特征作为保留，余下的删除。若未设定d，可以设定保留维度的比率t，从大到小遴选d个令其满足：

∑i=1dλi∑i=1pλi≥t\frac{\sum_{i=1}^{d}\lambda_i}{\sum_{i=1}^{p}\lambda_i}\geq t

最后一个问题，如何产生删除p−dp-d个抽象特征后的样本集Fn×d\mathbf{F}_{n\times d}。我们保留了d个特征，它们对应的特征向量分别为ω1,ω2,⋯ ,ωd\boldsymbol{\omega}_1,\boldsymbol{\omega}_2,\cdots,\boldsymbol{\omega}_d，每一个ωi\boldsymbol{\omega}_i为p维列向量，对应λi\lambda_i。令：

Up×d=(ω1,ω2,⋯ ,ωd)\mathbf{U}_{p\times d}=(\boldsymbol{\omega}_1,\boldsymbol{\omega}_2,\cdots,\boldsymbol{\omega}_d)

则：

F=X′U\mathbf{F}=\mathbf{X}^\prime\mathbf{U}

未完待续…#