[HITML]哈工大2020秋机器学习复习笔记
1 基础
查准率 = 预测正确的正例 / 预测出的所有正例
查全率 = 预测正确的正例 / 真实的所有正例
1.1 机器学习中的概率
机器学习任务涉及不确定性下的推理，不确定性的来源/随机性:
-
噪声——传感器测量的变异性，部分可观测性，不正确的标签
-
有限样本大小——训练和测试数据是随机抽取的实例
概率量化不确定性!
分布：二项分布、beta分布、狄利克雷分布
1.2 最大似然估计、最大后验概率
-
频率论的MLE方法：θ为未知常数，由资料估计
Maximum Likelihood Estimate (MLE): choose θ \theta θ that maximizes probability of observed data D \mathcal{D} D
θ ^ = arg max θ P ( D ∣ θ ) \displaystyle \widehat{\theta}=\arg \max _{\theta} P(\mathcal{D} \mid \theta) θ =argθmaxP(D∣θ) -
贝叶斯的MAP方法：θ为随机变量，假设为概率分布
Maximum a Posteriori (MAP) estimate: choose θ \theta θ that is most probable given prior probability and the data
θ ^ = arg max θ P ( θ ∣ D ) = arg max θ = P ( D ∣ θ ) P ( θ ) P ( D ) \begin{aligned} \hat{\theta} &=\arg \max _{\theta} \quad P(\theta \mid \mathcal{D}) \\ &=\arg \max _{\theta}=\frac{P(\mathcal{D} \mid \theta) P(\theta)}{P(\mathcal{D})} \end{aligned} θ^=argθmaxP(θ∣D)=argθmax=P(D)P(D∣θ)P(θ)
缺点：
-
MLE：如果数据集太小就会过拟合
-
MAP：两个有着不同先验的人将会得到不同的估计
详见 https://blog.****.net/weixin_44940258/article/details/109731281
1.3 最小二乘法、梯度下降法、共轭梯度法
最小二乘指的是预测值与样本值距离的平方和最小，在高斯分布的条件下，最下二乘和最大似然可以得到相同的结果。
2 决策树
同样一个训练数据集，可以有多棵树与其一致
决策树的归纳：贪心策略——基于一个可以最优化某项准则的属性来切分示例集合
确定最好的切分：一个好的属性切分是将示例集合分成若干子集，最理想情况是每个子集为“皆为正例”或“皆为反例”，那么需要对结点混杂度（impurity）进行测量。测量由于切分带来的熵减少量，选择具有最大减少量的切分（最大增益）
停止切分准则
(1) 当前结点包含的样本全属于同一类别，无需划分;
(2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分;
(3) 当前结点包含的样本集合为空，不能划分.
当获得最小可接受的决策树时则停止
Occam’s 剃刀：选择适合训练集合数据的最简单假设
解决过拟合问题
- 预剪枝(早期停止规则)：
- 在算法变成一棵完全成熟的树之前停止它，节点的典型停止情况:
- 如果所有实例都属于同一个类，则停止
- 如果所有属性值都相同，则停止
- 更多的限制条件:
- 如果实例数量少于用户指定的阈值，则停止
- 如果实例的类分布与可用的特征无关，停止(例如，使用χ2检验)
- 如果扩展当前节点不能改善杂质度量(例如，基尼系数或信息增益)，停止。
- 后剪枝：使决策树完整生长，以自底向上的方式修剪决策树的节点，如果修剪后泛化误差有所改善，则用叶节点替换子树，叶节点的类标签由子树中的大多数实例类确定，可以使用MDL (Minimum Description Length)进行后剪枝。
缺失属性值的处理
- 在属性值缺失的情况下进行划分属性选择：去除所有缺失的样本，但是计算无缺失值样本所占的比例，在计算信息增益时只看在无缺失样本上的值，但结果需要乘以无缺失值样本所占的比例。
- 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分：让同一个样本以不同的概率划入到不同的子结点中去。让同一个样本划到所有的子结点中，同时设置样本的权值为无缺失值样本中在该属性上取结点值的样本所占的比例
2.1 熵
信息量：当一个不可能发生的事件发生了，我们就说这个信息的信息量大；而当一个一定会发生的事件发生了，我们说这个信息几乎没有信息量。这符合我们的直觉。可以使用函数 − ln p ( x ) -\ln p(x) −lnp(x) 来描述信息量的大小。
因此，我们用熵这个概念来描述一个事件能够带给我们的信息量的期望，即
H
(
X
)
=
−
∑
i
=
1
n
p
(
x
i
)
ln
p
(
x
i
)
H(X)=-\sum_{i=1}^n p(x_i)\ln p(x_i)
H(X)=−i=1∑np(xi)lnp(xi)
2.2 条件熵
条件熵 H ( Y ∣ X ) H(Y|X) H(Y∣X) 表示在已知随机变量 X X X 的条件下随机变量 Y Y Y 的不确定性。条件熵 H ( Y ∣ X ) H(Y|X) H(Y∣X) 定义为 X X X 给定条件下 Y Y Y 的条件概率分布的熵对 X X X 的数学期望：
条件熵 H ( Y ∣ X ) H(Y|X) H(Y∣X) 相当于联合熵 H ( X , Y ) H(X,Y) H(X,Y) 减去单独的熵 H ( X ) H(X) H(X)，即 H ( Y ∣ X ) = H ( X , Y ) − H ( X ) H(Y|X)=H(X,Y)-H(X) H(Y∣X)=H(X,Y)−H(X)
互信息
信息增益：目标类变量与属性A变量在S（样本集）上的互信息
2.3 相对熵（KL散度）
相对熵用于描述两个分布之间的差异，假设
P
P
P 代表真实分布，
Q
Q
Q 代表预测分布，那么这两个分布之间就有一个“相似度”，那么就可以描述它们之间的差异的大小，这就是相对熵。计算公式：
D
K
L
(
p
∥
q
)
=
∑
i
=
1
n
p
(
x
i
)
ln
(
p
(
x
i
)
q
(
x
i
)
)
D_{K L}(p \| q)=\sum_{i=1}^{n} p\left(x_{i}\right) \ln \left(\frac{p\left(x_{i}\right)}{q\left(x_{i}\right)}\right)
DKL(p∥q)=i=1∑np(xi)ln(q(xi)p(xi))
显然，
D
K
L
(
p
∣
∣
q
)
≠
D
K
L
(
q
∣
∣
p
)
D_{KL}(p||q)\ne D_{KL}(q||p)
DKL(p∣∣q)=DKL(q∣∣p)
2.4 交叉熵
在机器学习中，评估一个模型的好坏，只需要计算KL散度即可，而对KL散度公式做一下变形，我们发现，只需要关注交叉熵即可：
D
K
L
(
p
∥
q
)
=
∑
i
=
1
n
p
(
x
i
)
ln
(
p
(
x
i
)
)
−
∑
i
=
1
n
p
(
x
i
)
ln
(
q
(
x
i
)
)
=
−
H
(
p
(
x
)
)
+
[
−
∑
i
=
1
n
p
(
x
i
)
ln
(
q
(
x
i
)
)
]
\begin{aligned} D_{K L}(p \| q) &=\sum_{i=1}^{n} p\left(x_{i}\right) \ln \left(p\left(x_{i}\right)\right)-\sum_{i=1}^{n} p\left(x_{i}\right) \ln \left(q\left(x_{i}\right)\right) \\ &=-H(p(x))+\left[-\sum_{i=1}^{n} p\left(x_{i}\right) \ln \left(q\left(x_{i}\right)\right)\right] \end{aligned}
DKL(p∥q)=i=1∑np(xi)ln(p(xi))−i=1∑np(xi)ln(q(xi))=−H(p(x))+[−i=1∑np(xi)ln(q(xi))]
等式的前一部分恰巧就是p的熵，这一部分是不会变化的，而等式的后一部分，就是交叉熵：
H
(
p
,
q
)
=
−
∑
i
=
1
n
p
(
x
i
)
ln
(
q
(
x
i
)
)
H(p,q) = -\sum_{i=1}^{n} p\left(x_{i}\right) \ln \left(q\left(x_{i}\right)\right)
H(p,q)=−i=1∑np(xi)ln(q(xi))
关于条件熵、相对熵、交叉熵参考 https://www.cnblogs.com/kyrieng/p/8694705.html
交叉熵参考 https://blog.****.net/tsyccnh/article/details/79163834
3 贝叶斯判别
3.1 最优分类器
贝叶斯决策论，在分类任务中是在所有相关概率都已知的理想情形下，考虑如何基于这些概率和误判损失来选择最优的类别标记。
假设类别标记
Y
=
{
c
1
,
c
2
,
.
.
.
,
c
N
}
Y=\{c_1,c_2,...,c_N\}
Y={c1,c2,...,cN}，记
λ
i
j
\lambda_{ij}
λij 为真实类别为
c
j
c_j
cj 的样本点被错误的标记为类别
c
i
c_i
ci 所造成的损失，因此，对于已知后验概率的点
x
x
x，我们有以下的期望损失 (风险)：
R
(
c
i
∣
x
)
=
∑
j
=
1
N
λ
i
j
P
(
c
j
∣
x
)
R\left(c_{i} \mid x\right)=\sum_{j=1}^{N} \lambda_{i j} P\left(c_{j} \mid x\right)
R(ci∣x)=j=1∑NλijP(cj∣x)
我们的目的就是要找一个判定准则
h
:
X
→
Y
h:X\rightarrow Y
h:X→Y，使得总体风险最小，即
R
(
h
)
=
E
x
[
R
(
h
(
x
)
∣
x
)
]
R(h)=E_{x}[R(h(x) \mid x)]
R(h)=Ex[R(h(x)∣x)] 最小，显然，对每个样本
x
x
x，若
h
h
h 能最小化条件风险
R
(
h
(
x
)
∣
x
)
R(h(x) \mid x)
R(h(x)∣x)，则总体风险
R
(
h
)
R(h)
R(h) 也将被最小化。这就产生了贝叶斯判定准则 (Bayes decision rule)：为最小化总体风险，只需在每个样本上选择那个能使条件风险R(c|x)最小的类别标记。此时我们有一个最优分类器
h
∗
(
x
)
=
arg
min
c
∈
Y
R
(
c
∣
x
)
h^*(x)=\arg \min_{c\in Y} R(c|x)
h∗(x)=argc∈YminR(c∣x)
这就是贝叶斯最优分类器。
若目标是最小化分类错误率，则误判损失 λ i j \lambda_{ij} λij 可写为 λ i j = { 0 , if i = j 1 , otherwise \lambda_{i j}=\left\{\begin{array}{ll} 0, & \text { if } i=j \\ 1, & \text { otherwise } \end{array}\right. λij={0,1, if i=j otherwise
于是真实类别为 c j c_j cj 的点 x x x 的期望损失是 R ( c i ∣ x ) = 1 − P ( c i ∣ x ) R(c_i|x)=1-P(c_i|x) R(ci∣x)=1−P(ci∣x)
我们的目的仍是使每个点的损失最小，所以相当于使 P ( c i ∣ x ) P(c_i|x) P(ci∣x) 最大，即 arg max c i P ( c i ∣ x ) \displaystyle\arg \max_{c_i} P(c_i|x) argcimaxP(ci∣x)
故得到的最优分类器为 ∀ x ∈ X , h ∗ ( x ) = arg max c ∈ Y P ( c ∣ x ) \displaystyle \forall x\in X,\quad h^*(x)= \arg\max_{c\in Y} P(c|x) ∀x∈X,h∗(x)=argc∈YmaxP(c∣x)
3.2 线性判别
线性判别分析 (LDA)，原理同PCA，相当于PCA在二维向一维投影降维的特殊情况。
3.3 生成式模型与判别式模型
-
判别式模型：给定 x x x，可通过直接建模 P ( c ∣ x ) P(c|x) P(c∣x) 来预测 c c c
决策树、SVM、线性回归、逻辑回归、kNN
-
生成式模型：先对联合概率分布 P ( x ∣ c ) P(x|c) P(x∣c) 建模，然后再由此获得 P ( c ∣ x ) P(c | x) P(c∣x)
生成式模型：朴素贝叶斯、GMM
3.4 KNN
kNN的意思是取k个最近的邻居的信息来做预测，对于分类任务来说，最近的k个邻居中，哪个类的邻居最多就把它也标为这个类，而对于回归任务来说，可以将这k个邻居的的平均值作为结果输出。总之，就是用最近的k的邻居的特征来描述测试点的特征。
关于距离的度量：
- 欧式距离
- 1范数
- 无穷范数
- 马氏距离： D ( x , x ′ ) = ∑ i σ i 2 ( x i − x i ′ ) 2 ⇔ D ( x , x ′ ) = ( x − x ′ ) T Σ − 1 ( x − x ′ ) D(x, x')=\sqrt{\sum_i\sigma^2_i(x_i-x_i')^2} \Leftrightarrow D(x, x')=\sqrt{(x-x')^T\Sigma^{-1}(x-x')} D(x,x′)=∑iσi2(xi−xi′)2 ⇔D(x,x′)=(x−x′)TΣ−1(x−x′)
- 相关系数
- 马氏距离
- 曼哈顿距离
- 汉明距离
4 线性回归、朴素贝叶斯与逻辑回归
4.1 线性回归
目的是构造一个线性函数，使得输入一个观测值x，能够输出其对应的预测值y，由于y的取值是连续的，所以称其为回归问题，这就是线性回归。
为了判断我们得到的函数中哪个是最好的，我们需要一个指标，这就是损失函数。
在多项式拟合的实验中，我们使用了一个关于x的高阶多项式来拟合正弦函数，虽然在二维空间中，我们得到的不是一个线性函数，但在高位空间看，我们得到的实际上是一个关于 X = ( x , x 2 , . . . , x n ) X=(x, x^2, ... ,x^n) X=(x,x2,...,xn) 的线性函数。在求解过程中，我们使用的损失函数是预测值与样本值的欧氏距离之和，当损失函数最小时，我们取到最优的函数，即回归直线。
4.2 过拟合
过拟合，指的是模型在训练集上表现的很好，但是在交叉验证集合测试集上表现一般，也就是说模型对未知样本的预测表现一般，泛化（generalization）能力较差。
对于过拟合的处理有以下几种常见的方式：
- 增加训练数据集
- 正则化，增加正则项
- 设置提前停止的条件：Early stopping便是一种迭代次数截断的方法来防止过拟合的方法，即在模型对训练数据集迭代收敛之前停止迭代来防止过拟合。
4.3 偏置与方差
4.4 特征变换
从一组已有的特征通过一定的数学运算得到一组新特征
用于数据降维
-
LDA (线性判别分析)：有监督的。设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、 异类样例的投影点尽可能远离；在对新样
本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定新样本的类别。 -
PCA (主成分分析)：无监督的。主要用于对数据的降维压缩，不属于类别判别。
4.5 朴素贝叶斯
在贝叶斯中，有
P
(
Y
∣
X
)
=
P
(
X
∣
Y
)
P
(
Y
)
P
(
X
)
P(Y|X)=\frac{P(X|Y)P(Y)}{P(X)}
P(Y∣X)=P(X)P(X∣Y)P(Y)，即对
∀
i
,
j
\forall\ i,j
∀ i,j，有
P
(
Y
=
y
i
∣
X
=
x
j
)
=
P
(
X
=
x
j
∣
Y
=
y
i
)
P
(
Y
=
y
j
)
P
(
X
=
x
j
)
=
P
(
X
=
x
j
∣
Y
=
y
i
)
P
(
Y
=
y
i
)
∑
k
P
(
X
=
x
j
∣
Y
=
y
k
)
P
(
Y
=
y
k
)
P(Y=y_i|X=x_j)=\frac{P(X=x_j|Y=y_i)P(Y=y_j)}{P(X=x_j)}=\frac{P(X=x_j|Y=y_i)P(Y=y_i)} {\sum_k P(X=x_j|Y=y_k)P(Y=y_k)}
P(Y=yi∣X=xj)=P(X=xj)P(X=xj∣Y=yi)P(Y=yj)=∑kP(X=xj∣Y=yk)P(Y=yk)P(X=xj∣Y=yi)P(Y=yi)
在朴素贝叶斯中，给定观测值
Y
Y
Y，假设
X
=
<
X
1
,
X
2
,
.
.
.
,
X
n
>
X=<X_1, X_2, ..., X_n>
X=<X1,X2,...,Xn>，对于
∀
1
≤
i
<
j
≤
n
\forall\ 1\le i<j\le n
∀ 1≤i<j≤n，
X
i
X_i
Xi 和
X
j
X_j
Xj 满足条件独立，即
P
(
X
1
,
X
2
,
.
.
.
,
X
n
∣
Y
)
=
∏
i
P
(
X
i
∣
Y
)
P(X_1, X_2, ..., X_n|Y)=\prod_i{P(X_i|Y)}
P(X1,X2,...,Xn∣Y)=i∏P(Xi∣Y)
条件独立：X和Y条件独立，即 P ( X ∣ Y , Z ) = P ( X ∣ Z ) P(X|Y,Z)=P(X|Z) P(X∣Y,Z)=P(X∣Z)
所以，在朴素贝叶斯条件独立的假设下给定
X
n
e
w
=
<
X
1
,
X
2
,
.
.
.
,
X
n
>
X^{new}=<X_1, X_2, ..., X_n>
Xnew=<X1,X2,...,Xn> 估计该点的类别
Y
n
e
w
Y^{new}
Ynew，有
P
(
Y
=
y
k
∣
X
1
,
X
2
,
.
.
.
,
X
n
)
=
P
(
X
1
,
X
2
,
.
.
.
,
X
n
∣
Y
=
y
k
)
P
(
Y
=
y
k
)
∑
j
P
(
X
1
,
X
2
,
.
.
.
,
X
n
∣
Y
=
y
j
)
P
(
Y
=
y
j
)
=
P
(
Y
=
y
k
)
∏
i
P
(
X
i
∣
Y
=
y
k
)
∑
j
P
(
Y
=
y
k
)
∏
i
P
(
X
i
∣
Y
=
y
j
)
P
(
Y
=
y
j
)
P(Y=y_k|X_1, X_2, ..., X_n)=\frac{P(X_1, X_2, ..., X_n|Y=y_k)P(Y=y_k)} {\sum_j P(X_1, X_2, ..., X_n|Y=y_j)P(Y=y_j)} =\displaystyle\frac{P(Y=y_k)\displaystyle \prod_i P(X_i|Y=y_k)} {\displaystyle\sum_j P(Y=y_k) \prod_i P(X_i|Y=y_j)P(Y=y_j)}
P(Y=yk∣X1,X2,...,Xn)=∑jP(X1,X2,...,Xn∣Y=yj)P(Y=yj)P(X1,X2,...,Xn∣Y=yk)P(Y=yk)=j∑P(Y=yk)i∏P(Xi∣Y=yj)P(Y=yj)P(Y=yk)i∏P(Xi∣Y=yk)
因此原问题
Y
n
e
w
=
arg
max
y
k
P
(
Y
=
y
k
∣
X
1
,
X
2
,
.
.
.
,
X
n
)
\displaystyle Y^{new}=\arg \max_{y_k} P(Y=y_k|X_1, X_2, ..., X_n)
Ynew=argykmaxP(Y=yk∣X1,X2,...,Xn) 就转化为
Y n e w = arg max y k P ( Y = y k ) ∏ i P ( X i ∣ Y = y k ) (4.5.1) \displaystyle Y^{new}=\arg \max_{y_k} P(Y=y_k) \prod_i P(X_i|Y=y_k)\tag{4.5.1} Ynew=argykmaxP(Y=yk)i∏P(Xi∣Y=yk)(4.5.1)
也就是说，当各个属性之间条件独立时，考虑最大化各个属性取值时的类别，而为了能够从整体上看最大化的情况，取了各个属性值上的概率积。
在朴素贝叶斯中，我们需要对两类参数进行估计
-
先验概率： π k = P ( Y = y k ) \pi_k = P(Y=y_k) πk=P(Y=yk)
-
条件概率： θ i j k = P ( X i = x i j ∣ Y = y k ) \theta_{ijk} = P(X_i=x_{ij}|Y=y_k) θijk=P(Xi=xij∣Y=yk)
因此，分别采用MLE和MAP来看效果
# D { A } \#D\{A\} #D{A} 表示数据集D中满足条件A的样本数量
-
MLE： π ^ k = P ^ ( Y = y k ) = # D { Y = y k } ∣ D ∣ , θ ^ i j k = P ^ ( X i = x i j ∣ Y = y k ) = # D { X i = x i j ∧ Y = y k } # D { Y = y k } \displaystyle\hat\pi_k = \hat P(Y=y_k)=\frac{\#D\{Y=y_k\}}{|D|},\quad \hat\theta_{ijk} = \hat P(X_i=x_{ij}|Y=y_k)=\frac{\#D\{X_i=x_{ij} \wedge Y=y_k\}}{\#D\{Y=y_k\}} π^k=P^(Y=yk)=∣D∣#D{Y=yk},θ^ijk=P^(Xi=xij∣Y=yk)=#D{Y=yk}#D{Xi=xij∧Y=yk}
但是有个问题，若某个属性值在训练集中没有与某个类同时出现过，则直接基于上式进行概率估计，再根据式 ( 4.5.1 ) (4.5.1) (4.5.1)进行判别将出现问题。假设对于类别 y 0 y_0 y0 来说，这个类别中的所有数据都没有出现 X 2 = x 23 X_2=x_{23} X2=x23 的取值，因此有 P ( X 2 = x 23 ∣ Y = y 0 ) = 0 P(X_2=x_{23}|Y=y_0)=0 P(X2=x23∣Y=y0)=0，而由于式 ( 4.5.1 ) (4.5.1) (4.5.1)中的连乘，最终会得到一个拥有 X 2 = x 23 X_2=x_{23} X2=x23 属性值的点被判断为属于 y 0 y_0 y0 类的可能性为0，而其他属性无法起到相应的作用，显然这是不合理的。因此，在各个估计中加入平滑项来消除这个问题，于是可以得到与MAP中的式子相同的结论。
-
MAP： π ^ k = P ^ ( Y = y k ) = # D { Y = y k } + α k ∣ D ∣ + ∑ m α m , θ ^ i j k = P ^ ( X i = x i j ∣ Y = y k ) = # D { X i = x i j ∧ Y = y k } + α k ′ # D { Y = y k } + ∑ m α m ′ \displaystyle\hat\pi_k = \hat P(Y=y_k)=\frac{\#D\{Y=y_k\}+\alpha_k}{|D|+\sum_m \alpha_m},\quad \hat\theta_{ijk} = \hat P(X_i=x_{ij}|Y=y_k)=\frac{\#D\{X_i=x_{ij} \wedge Y=y_k\}+\alpha_k'}{\#D\{Y=y_k\}+\sum_m \alpha_m'} π^k=P^(Y=yk)=∣D∣+∑mαm#D{Y=yk}+αk,θ^ijk=P^(Xi=xij∣Y=yk)=#D{Y=yk}+∑mαm′#D{Xi=xij∧Y=yk}+αk′
α i \alpha_i αi 是一些虚样本点。假的，人为加入的，当 α i = 0 \alpha_i=0 αi=0 时为MLE；当 α i = 1 \alpha_i=1 αi=1 时为拉普拉斯平滑，这是常用的方法。
朴素贝叶斯在不满足假设（各属性之间不条件独立）下的分类效果仍然很好
当第 i i i 个属性 X i X_i Xi 取值是连续的时：高斯朴素贝叶斯
4.6 逻辑回归
分类器做分类问题的实质是预测一个已知样本的位置标签，即 P ( Y = 1 ∣ X = < X 1 , . . . , X n > ) P(Y=1|X=< X_1,...,X_n>) P(Y=1∣X=<X1,...,Xn>)。按照朴素贝叶斯的方法，可以用贝叶斯概率公式将其转化为类条件概率(似然)和类概率的乘积。但通过以下的推导可以直接求该概率。
假设分类问题是一个0/1二分类问题：
P
(
Y
=
1
∣
X
)
=
P
(
Y
=
1
)
P
(
X
∣
Y
=
1
)
P
(
X
)
=
P
(
Y
=
1
)
P
(
X
∣
Y
=
1
)
P
(
Y
=
1
)
P
(
X
∣
Y
=
1
)
+
P
(
Y
=
0
)
P
(
X
∣
Y
=
0
)
=
1
1
+
P
(
Y
=
0
)
P
(
X
∣
Y
=
0
)
P
(
Y
=
1
)
P
(
X
∣
Y
=
1
)
=
1
1
+
exp
(
ln
P
(
Y
=
0
)
P
(
X
∣
Y
=
0
)
P
(
Y
=
1
)
P
(
X
∣
Y
=
1
)
)
\begin{aligned} P(Y=1|X)&=\frac {P(Y=1)P(X|Y=1)} {P(X)}\\ &=\frac{P(Y=1)P(X|Y=1)} {P(Y=1)P(X|Y=1)+P(Y=0)P(X|Y=0)}\\ &=\frac {1}{1+\frac{P(Y=0)P(X|Y=0)}{P(Y=1)P(X|Y=1)}}\\ &=\frac {1}{1+\exp (\ln\frac{P(Y=0)P(X|Y=0)}{P(Y=1)P(X|Y=1)})} \end{aligned}
P(Y=1∣X)=P(X)P(Y=1)P(X∣Y=1)=P(Y=1)P(X∣Y=1)+P(Y=0)P(X∣Y=0)P(Y=1)P(X∣Y=1)=1+P(Y=1)P(X∣Y=1)P(Y=0)P(X∣Y=0)1=1+exp(lnP(Y=1)P(X∣Y=1)P(Y=0)P(X∣Y=0))1
令
π
=
P
(
Y
=
1
)
\pi = P(Y=1)
π=P(Y=1)，
1
−
π
=
P
(
Y
=
0
)
1-\pi = P(Y=0)
1−π=P(Y=0)
P
(
Y
=
1
∣
X
)
=
1
1
+
exp
(
ln
1
−
π
π
+
∑
i
ln
P
(
X
i
∣
Y
=
0
)
P
(
X
i
∣
Y
=
1
)
)
P(Y=1|X)=\frac{1}{1+\exp(\ln \frac{1-\pi}{\pi}+\sum_i \ln \frac {P(X_i|Y=0)}{P(X_i|Y=1)})}\\
P(Y=1∣X)=1+exp(lnπ1−π+∑ilnP(Xi∣Y=1)P(Xi∣Y=0))1
假设类条件分布服从正态分布且方差不依赖于 k k k。 P ( x ∣ y k ) = 1 σ i 2 π e − ( x − μ k ) 2 2 σ i 2 P(x|y_k)=\frac {1}{\sigma_i\sqrt{2\pi}}e^{\frac{-(x-\mu_k)^2}{2\sigma_i^2}} P(x∣yk)=σi2π 1e2σi2−(x−μk)2
令
w
0
=
ln
1
−
π
π
+
∑
i
μ
i
1
2
−
μ
i
0
2
2
σ
i
2
w_0=\ln \frac{1-\pi}{\pi} + \sum_i\frac{\mu_{i1}^2-\mu_{i0}^2}{2\sigma_i^2}
w0=lnπ1−π+∑i2σi2μi12−μi02，
w
i
=
μ
i
0
−
μ
i
1
σ
i
2
w_i=\frac{\mu_{i0}-\mu_{i1}}{\sigma_i^2}
wi=σi2μi0−μi1，则有：
P
(
Y
=
1
∣
X
)
=
1
1
+
exp
(
w
0
+
∑
i
=
1
n
w
i
X
i
)
P(Y=1|X)=\frac{1}{1+\exp{(w_0+\sum_{i=1}^n w_iX_i)}}
P(Y=1∣X)=1+exp(w0+∑i=1nwiXi)1
使用极大条件似然估计来计算损失函数
l
(
w
)
l(w)
l(w)，此时有
P
(
Y
=
0
∣
X
,
W
)
=
1
1
+
exp
(
w
0
+
∑
i
=
1
n
w
i
X
i
)
P(Y=0|X,W)=\frac{1}{1+\exp{(w_0+\sum_{i=1}^n w_iX_i)}}
P(Y=0∣X,W)=1+exp(w0+∑i=1nwiXi)1
所以损失函数
l
(
W
)
=
∑
l
Y
l
ln
P
(
Y
l
=
1
∣
X
l
,
W
)
+
(
1
−
Y
l
)
ln
P
(
Y
l
=
0
∣
X
l
,
W
)
=
∑
l
Y
l
ln
P
(
Y
l
=
1
∣
X
l
,
W
)
P
(
Y
l
=
0
∣
X
l
,
W
)
−
ln
P
(
Y
l
=
0
∣
X
l
,
W
)
=
∑
l
Y
l
(
w
0
+
∑
i
=
1
n
w
i
X
i
)
−
ln
(
1
+
e
x
p
(
w
0
+
∑
i
=
1
n
w
i
X
i
)
(4.6.1)
\begin{aligned} l(W)&=\sum_lY^l\ln\,P(Y^l=1|X^l,W) + (1-Y^l)\ln\,P(Y^l=0|X^l,W)\\ &=\sum_l Y^l\ln\,\frac{P(Y^l=1|X^l,W)}{P(Y^l=0|X^l,W)} - \ln\,P(Y^l=0|X^l,W)\\ &=\sum_l Y^l(w_0+\sum_{i=1}^n w_iX_i) - \ln (1+exp(w_0+\sum_{i=1}^n w_iX_i) \end{aligned} \tag{4.6.1}
l(W)=l∑YllnP(Yl=1∣Xl,W)+(1−Yl)lnP(Yl=0∣Xl,W)=l∑YllnP(Yl=0∣Xl,W)P(Yl=1∣Xl,W)−lnP(Yl=0∣Xl,W)=l∑Yl(w0+i=1∑nwiXi)−ln(1+exp(w0+i=1∑nwiXi)(4.6.1)
我们要求
arg
max
w
l
(
w
)
\arg \max_w\;l(w)
argmaxwl(w)，也就是求
arg
min
w
−
l
(
w
)
\arg \min_w -l(w)
argminw−l(w)，用梯度下降法求解
∂
l
(
W
)
∂
w
i
=
∑
l
X
i
l
(
Y
l
−
1
1
+
exp
(
w
0
+
∑
i
=
1
n
w
i
X
i
l
)
)
w
i
=
w
i
−
η
∑
l
X
i
l
(
Y
l
−
1
1
+
exp
(
w
0
+
∑
i
=
1
n
w
i
X
i
l
)
)
(4.6.2)
\frac {\partial\,l(W)} {\partial\, w_i} = \sum_l\,X_i^l(Y^l-\frac{1}{1+\exp{(w_0+\sum_{i=1}^n w_iX_i^l)}}) \tag{4.6.2}\\ w_i = w_i - \eta\sum_l\,X_i^l(Y^l-\frac{1}{1+\exp{(w_0+\sum_{i=1}^n w_iX_i^l)}})
∂wi∂l(W)=l∑Xil(Yl−1+exp(w0+∑i=1nwiXil)1)wi=wi−ηl∑Xil(Yl−1+exp(w0+∑i=1nwiXil)1)(4.6.2)
向量形式
W
=
W
−
η
∑
l
X
l
(
Y
l
−
1
1
+
exp
(
W
X
l
)
)
\pmb W=\pmb W-\eta \sum_l \pmb X^l(\pmb Y^l-\frac{1}{1+\exp(\pmb {WX^l})})
WWW=WWW−ηl∑XXXl(YYYl−1+exp(WXlWXlWXl)1)
为了控制过拟合问题增加正则项
w
i
=
w
i
−
η
λ
w
i
−
η
∑
l
X
i
l
(
Y
l
−
1
1
+
exp
(
w
0
+
∑
i
=
1
n
w
i
X
i
l
)
)
w_i = w_i - \eta\lambda w_i - \eta\sum_l\,X_i^l(Y^l-\frac{1}{1+\exp{(w_0+\sum_{i=1}^n w_iX_i^l)}})
wi=wi−ηλwi−ηl∑Xil(Yl−1+exp(w0+∑i=1nwiXil)1)
向量形式
W
=
W
−
η
λ
W
−
η
∑
l
X
l
(
Y
l
−
1
1
+
exp
(
W
X
l
)
)
\pmb W=\pmb W - \eta\lambda \pmb W - \eta \sum_l \pmb X^l(\pmb Y^l-\frac{1}{1+\exp(\pmb {WX^l})})
WWW=WWW−ηλWWW−ηl∑XXXl(YYYl−1+exp(WXlWXlWXl)1)
这种直接将式
(
4.6.1
)
(4.6.1)
(4.6.1)求导得到式
(
4.6.2
)
(4.6.2)
(4.6.2)进行迭代的方式，在数据特别多，即
l
(
w
)
l(w)
l(w) 特别大的情况下，有可能导致上溢出发生，基于此，我们将式
(
4.6.1
)
(4.6.1)
(4.6.1)归一化，防止其溢出，得到下式
l
(
W
)
=
1
l
∑
l
Y
l
(
w
0
+
∑
i
=
1
n
w
i
X
i
)
−
ln
(
1
+
e
x
p
(
w
0
+
∑
i
=
1
n
w
i
X
i
)
∂
l
(
W
)
∂
w
i
=
1
l
∑
l
X
i
l
(
Y
l
−
1
1
+
exp
(
w
0
+
∑
i
=
1
n
w
i
X
i
l
)
)
w
i
=
w
i
−
η
l
∑
l
X
i
l
(
Y
l
−
1
1
+
exp
(
w
0
+
∑
i
=
1
n
w
i
X
i
l
)
)
W
=
W
−
η
l
∑
l
X
l
(
Y
l
−
1
1
+
exp
(
W
X
l
)
)
l(W)=\frac{1}{l}\sum_l Y^l(w_0+\sum_{i=1}^n w_iX_i) - \ln (1+exp(w_0+\sum_{i=1}^n w_iX_i)\\ \frac {\partial\,l(W)} {\partial\, w_i} = \frac{1}{l}\sum_l\,X_i^l(Y^l-\frac{1}{1+\exp{(w_0+\sum_{i=1}^n w_iX_i^l)}})\\ w_i = w_i - \frac{\eta}{l}\sum_l\,X_i^l(Y^l-\frac{1}{1+\exp{(w_0+\sum_{i=1}^n w_iX_i^l)}})\\ \pmb W=\pmb W-\frac{\eta}{l} \sum_l \pmb X^l(\pmb Y^l-\frac{1}{1+\exp(\pmb {WX^l})})
l(W)=l1l∑Yl(w0+i=1∑nwiXi)−ln(1+exp(w0+i=1∑nwiXi)∂wi∂l(W)=l1l∑Xil(Yl−1+exp(w0+∑i=1nwiXil)1)wi=wi−lηl∑Xil(Yl−1+exp(w0+∑i=1nwiXil)1)WWW=WWW−lηl∑XXXl(YYYl−1+exp(WXlWXlWXl)1)
加入正则项后
w
i
=
w
i
−
η
λ
w
i
−
η
l
∑
l
X
i
l
(
Y
l
−
1
1
+
exp
(
w
0
+
∑
i
=
1
n
w
i
X
i
l
)
)
W
=
W
−
η
λ
W
−
η
l
∑
l
X
l
(
Y
l
−
1
1
+
exp
(
W
X
l
)
)
w_i = w_i - \eta\lambda w_i - \frac\eta l\sum_l\,X_i^l(Y^l-\frac{1}{1+\exp{(w_0+\sum_{i=1}^n w_iX_i^l)}})\\ \pmb W=\pmb W - \eta\lambda \pmb W - \frac\eta l \sum_l \pmb X^l(\pmb Y^l-\frac{1}{1+\exp(\pmb {WX^l})})
wi=wi−ηλwi−lηl∑Xil(Yl−1+exp(w0+∑i=1nwiXil)1)WWW=WWW−ηλWWW−lηl∑XXXl(YYYl−1+exp(WXlWXlWXl)1)
5 SVM
关于SVM https://blog.****.net/v_july_v/article/details/7624837
5.1 基本问题
记将两个类别分开的超平面为 w T x + b = 0 \pmb {w^Tx}+b=0 wTxwTxwTx+b=0，其中 w = ( w 1 ; w 2 ; . . . ; w n ) \pmb w=(w_1;w_2;...;w_n) www=(w1;w2;...;wn) 为法向量
w \pmb w www 中的分号表示是一个列向量
所以样本空间 D D D 中任意点 x \pmb x xxx 到超平面的距离可写为： r = ∣ w T x + b ∣ ∣ ∣ w ∣ ∣ \displaystyle r=\frac {|\pmb{w^Tx}+b|}{||\pmb w||} r=∣∣www∣∣∣wTxwTxwTx+b∣
假设该超平面能够对训练样本正确分类，则有 { w T x i + b > 0 , y i = + 1 w T x i + b < 0 , y i = − 1 , ( x i , y i ) ∈ D \begin{cases} \pmb {w^Tx_i}+b>0, & y_i=+1\\ \pmb {w^Tx_i}+b<0, & y_i=-1 \end{cases},\; (\pmb x_i, y_i)\in D {wTxiwTxiwTxi+b>0,wTxiwTxiwTxi+b<0,yi=+1yi=−1,(xxxi,yi)∈D
对系数 w , b \pmb w, b www,b 进行适当的放缩有 { w T x i + b ≥ + 1 , y i = + 1 w T x i + b ≤ − 1 , y i = − 1 , ( x i , y i ) ∈ D ⇒ y i ( w T x i + b ) ≥ 1 \begin{cases} \pmb {w^Tx_i}+b\ge +1, & y_i=+1\\ \pmb {w^Tx_i}+b\le -1, & y_i=-1 \end{cases},\; (\pmb x_i, y_i)\in D \Rightarrow y_i(\pmb {w^Tx_i}+b)\ge 1 {wTxiwTxiwTxi+b≥+1,wTxiwTxiwTxi+b≤−1,yi=+1yi=−1,(xxxi,yi)∈D⇒yi(wTxiwTxiwTxi+b)≥1 （这就是超平面需要满足的条件，即约束条件）
于是距离超平面最近的这几个训练样本点使上式等号成立，这些点被称为支持向量，而当等号成立时我们说限制被** (active)，而对于其他点我们说限制未** (inactive)。
显然，此时这两个不同类到超平面的距离和为 γ = 2 ∣ ∣ w ∣ ∣ \displaystyle \gamma=\frac 2 {||\pmb w||} γ=∣∣www∣∣2，它被称为margin（间隔、边缘）
所以我们要找到的就是具有最大间隔的划分超平面 (Maximum Margin Classification)，即 max w , b 2 ∣ ∣ w ∣ ∣ s.t. y i ( w T x i + b ) ≥ 1 , i = 1 , 2 , . . . , m \displaystyle \max_{\pmb w,b} \frac 2 {||\pmb w||}\quad \text{s.t.}\ y_i(\pmb {w^Tx_i}+b)\ge 1,\ i=1,2,...,m www,bmax∣∣www∣∣2s.t. yi(wTxiwTxiwTxi+b)≥1, i=1,2,...,m
显然，为了最大化间隔仅需最大化 ∣ ∣ w ∣ ∣ − 1 ||\pmb w||^{-1} ∣∣www∣∣−1，这等价于最小化 ∣ ∣ w 2 ∣ ∣ ||\pmb w^2|| ∣∣www2∣∣ 于是，上式重写为 min w , b 1 2 ∣ ∣ w ∣ ∣ 2 s.t. y i ( w T x i + b ) ≥ 1 , i = 1 , 2 , . . . , m \displaystyle \min_{\pmb w,b} \frac 1 2 ||\pmb w||^2 \quad \text{s.t.}\ y_i(\pmb {w^Tx_i}+b)\ge 1,\ i=1,2,...,m www,bmin21∣∣www∣∣2s.t. yi(wTxiwTxiwTxi+b)≥1, i=1,2,...,m
这就是SVM的基本形式。因为现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。这个问题可以用现成的QP (Quadratic Programming)优化包进行求解。一言以蔽之：在一定的约束条件下，目标最优，损失最小。
5.2 对偶问题
由于这个问题的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量 (dual variable) 的优化问题，即通过求解与原问题等价的对偶问题（dual problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法。
将5.1中最后得到的问题使用拉格朗日乘子法变成无约束的问题，如下，其中
α
i
\alpha_i
αi 为每个约束条件对应的拉格朗日乘子：
L
(
w
,
b
,
α
)
=
1
2
∥
w
∥
2
−
∑
i
=
1
m
α
i
(
y
i
(
w
T
x
i
+
b
)
−
1
)
(5.2.1)
\mathcal{L}(w, b, \alpha)=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{m} \alpha_{i}\left(y_{i}\left(w^{T} x_{i}+b\right)-1\right) \tag{5.2.1}
L(w,b,α)=21∥w∥2−i=1∑mαi(yi(wTxi+b)−1)(5.2.1)
所以我们有
min
w
,
b
max
α
i
≥
0
L
(
w
,
b
,
α
)
\displaystyle\min _{w, b} \max _{\alpha_{i} \geq 0} \mathcal{L}(w, b, \alpha)
w,bminαi≥0maxL(w,b,α)，这个问题和原问题是等价的，而直接求解此问题又不好求解，所以取它的对偶问题变成：
max
α
i
≥
0
min
w
,
b
L
(
w
,
b
,
α
)
\max _{\alpha_{i} \geq 0} \min _{w, b} \mathcal{L}(w, b, \alpha)
αi≥0maxw,bminL(w,b,α)
所以首先固定
α
\alpha
α，要让
L
L
L 关于
w
w
w 和
b
b
b 最小化，我们分别对
w
,
b
w,\ b
w, b 求偏导：
∇
w
L
(
w
,
b
,
α
)
=
w
−
∑
i
=
1
m
α
i
y
i
x
i
=
0
⇒
w
=
∑
i
=
1
m
α
i
y
i
x
i
∇
b
L
(
w
,
b
,
α
)
=
∑
i
=
1
m
α
i
y
i
=
0
\nabla_{w} \mathcal{L}(w, b, \alpha)=w-\sum_{i=1}^{m} \alpha_{i} y_{i} x_{i}=0 \Rightarrow w=\sum_{i=1}^{m} \alpha_{i} y_{i} x_{i}\\ \nabla_{b} \mathcal{L}(w, b, \alpha)=\sum_{i=1}^{m} \alpha_{i} y_{i}=0
∇wL(w,b,α)=w−i=1∑mαiyixi=0⇒w=i=1∑mαiyixi∇bL(w,b,α)=i=1∑mαiyi=0
将这两个式子代回
L
\mathcal L
L，得到
L
(
w
,
b
,
α
)
=
∑
i
=
1
m
α
i
−
1
2
∑
i
,
j
=
1
m
α
i
α
j
y
i
y
j
(
x
i
T
x
j
)
\displaystyle\mathcal{L}(w, b, \alpha)=\sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(\mathbf{x}_{i}^{T} \mathbf{x}_{j}\right)
L(w,b,α)=i=1∑mαi−21i,j=1∑mαiαjyiyj(xiTxj)，所以我们得到如下的对偶问题：
max
α
∑
i
=
1
m
α
i
−
1
2
∑
i
,
j
=
1
m
α
i
α
j
y
i
y
j
(
x
i
T
x
j
)
s.t.
α
i
≥
0
,
i
=
1
,
…
,
k
∑
i
=
1
m
α
i
y
i
=
0
\max _{\alpha} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j}(\pmb {x_i^T x_j}) \\ \text { s.t. } \quad \alpha_{i} \geq 0, \quad i=1, \ldots, k \\ \quad \sum_{i=1}^{m} \alpha_{i} y_{i}=0
αmaxi=1∑mαi−21i,j=1∑mαiαjyiyj(xiTxjxiTxjxiTxj) s.t. αi≥0,i=1,…,ki=1∑mαiyi=0
这又是一个二次规划问题，总能求出
α
i
\alpha_i
αi 的全局最大值，然后就能计算出
w
,
b
w,\ b
w, b，而从对偶问题解出的
α
i
\alpha_i
αi 是式
(
5.2.1
)
(5.2.1)
(5.2.1) 中的拉格朗日乘子，对应训练样本
(
x
i
,
y
i
)
(\pmb x_i, y_i)
(xxxi,yi)。注意到5.1中最后的式中有不等式约束。因此上述过程需满足 KKT (Karush-Kuhn-Tucker) 条件，即要求
{
α
i
≥
0
y
i
f
(
x
i
)
−
1
≥
0
α
i
(
y
i
f
(
x
i
)
−
1
)
=
0
\left\{\begin{array}{l} \alpha_{i} \ge 0 \\ y_{i} f\left(x_{i}\right)-1 \ge 0 \\ \alpha_{i}\left(y_{i} f\left(x_{i}\right)-1\right)=0 \end{array}\right.
⎩⎨⎧αi≥0yif(xi)−1≥0αi(yif(xi)−1)=0
关于KKT条件，参考 https://zhuanlan.zhihu.com/p/38163970
观察KKT条件，发现只有少数 α i \alpha_i αi 非0，因为KKT条件的第三个条件要满足，而对于非支持向量来说 y i f ( x i ) > 1 y_{i} f(x_{i})> 1 yif(xi)>1 是一定成立的，所以对于这些点必须有 α i = 0 \alpha_i=0 αi=0
因此，在计算
w
w
w 时，只需要关心支持向量对应的
α
i
\alpha_i
αi 即可，即：
w
=
∑
i
∈
S
V
α
i
y
i
x
i
\displaystyle w= \sum_{i\in SV} \alpha_i y_i \pmb x_i
w=i∈SV∑αiyixxxi，SV指support vector，所以我们得到的超平面方程为 (
x
\pmb x
xxx 是一个新数据)：
f
(
x
)
=
w
T
x
+
b
=
∑
i
∈
S
V
α
i
y
i
x
i
T
x
+
b
f(\pmb x)=w^T\pmb x+b= \sum_{i\in SV} \alpha_i y_i \pmb {x_i^Tx}+b
f(xxx)=wTxxx+b=i∈SV∑αiyixiTxxiTxxiTx+b
通过上式可以看到，并不需要显式的计算出
w
w
w，最终是通过新样例与支持向量比较来决策类别的。
5.3 软间隔 Soft Margin Hyperplane
在实际的应用中，我们的数据可能实际上是线性可分的，但是由于噪声的存在，使得两类的个别数据点之间的距离较近，导致类别之间的距离较近，而如果在这个条件下仍然按照上面的办法求解，显然求得的结果是不合理的，甚至有可能出现一类的某个数据点出现在了对侧中，导致不存在分类超平面。因此，我们需要一种手段来使得分类超平面能够容忍这些“错误”的数据点 (outlier) 的存在，即有些点可以不满足约束条件。
原约束条件为
y
i
(
w
T
x
i
+
b
)
≥
1
,
i
=
1
,
2
,
.
.
.
,
m
y_i(\pmb {w^Tx_i}+b)\ge 1,\ i=1,2,...,m
yi(wTxiwTxiwTxi+b)≥1, i=1,2,...,m，现在考虑outlier的存在变成了
y
i
(
w
T
x
i
+
b
)
≥
1
−
ξ
i
,
i
=
1
,
2
,
.
.
.
,
m
y_i(\pmb {w^Tx_i}+b)\ge 1-\xi_i,\ i=1,2,...,m
yi(wTxiwTxiwTxi+b)≥1−ξi, i=1,2,...,m，其中
ξ
i
≥
0
\xi_i\ge 0
ξi≥0 称为松弛变量 (slack variable) ，对应数据点
x
i
\pmb x_i
xxxi 允许偏离的量。当
ξ
i
=
0
\xi_i=0
ξi=0 时说明对应的点
x
i
\pmb x_i
xxxi 无错误，显然，如果将
ξ
i
\xi_i
ξi 设为任意大的话，那任意的超平面都符合条件。所以，在原来的目标函数后面加上一项，使得松弛变量的总和也要最小，于是新的原问题变成了：
min
w
,
b
1
2
∥
w
∥
2
+
C
∑
i
=
1
m
ξ
i
s.t.
y
i
(
w
T
x
i
+
b
)
≥
1
−
ξ
i
,
i
=
1
,
…
,
m
ξ
i
≥
0
,
i
=
1
,
…
,
m
\min_{w,b} \frac{1}{2}\|w\|^{2}+C \sum_{i=1}^{m} \xi_{i} \\ \text { s.t.}\quad y_{i}\left(w^{T} x_{i}+b\right) \geq 1-\xi_{i}, i=1, \ldots, m \\ \quad \xi_{i} \geq 0, i=1, \ldots, m
w,bmin21∥w∥2+Ci=1∑mξi s.t.yi(wTxi+b)≥1−ξi,i=1,…,mξi≥0,i=1,…,m
其中，引入了一个常量 C C C，它是在“寻找 margin 最大的超平面”和“保证数据点偏差量最小”之间权衡参数，它在事先已经被约定好了。
同样构造拉格朗日函数 L ( w , b , ξ , α , r ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 n ξ i − ∑ i = 1 n α i ( y i ( w T x i + b ) − 1 + ξ i ) − ∑ i = 1 n r i ξ i \displaystyle \mathcal{L}(w, b, \xi, \alpha, r)=\frac{1}{2}\|w\|^{2}+C \sum_{i=1}^{n} \xi_{i}-\sum_{i=1}^{n} \alpha_{i}\left(y_{i}\left(w^{T} x_{i}+b\right)-1+\xi_{i}\right)-\sum_{i=1}^{n} r_{i} \xi_{i} L(w,b,ξ,α,r)=21∥w∥2+Ci=1∑nξi−i=1∑nαi(yi(wTxi+b)−1+ξi)−i=1∑nriξi
分别对 w , b . ξ i w,b.\xi_i w,b.ξi 求偏导，其中，对 ξ i \xi_i ξi 求偏导得到 ∂ L ∂ ξ i = 0 ⇒ C − α i − r i = 0 , i = 1 , … , m \frac{\partial \mathcal{L}}{\partial \xi_{i}}=0 \Rightarrow C-\alpha_{i}-r_{i}=0, \quad i=1, \ldots, m ∂ξi∂L=0⇒C−αi−ri=0,i=1,…,m
又由于拉格朗日乘子应该满足
r
i
≥
0
r_i\ge 0
ri≥0，因此得到
0
≤
α
i
≤
C
0\le \alpha_i\le C
0≤αi≤C，于是得到对偶问题，与之前的对偶问题唯一的区别在于
α
i
\alpha_i
αi 多了一个上限
C
C
C：
max
α
∑
i
=
1
m
α
i
−
1
2
∑
i
,
j
=
1
m
α
i
α
j
y
i
y
j
(
x
i
T
x
j
)
s.t.
0
≤
α
i
≤
C
,
i
=
1
,
…
,
k
∑
i
=
1
m
α
i
y
i
=
0
\max _{\alpha} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j}(\pmb {x_i^T x_j}) \\ \text { s.t. } \quad 0\le \alpha_{i} \le C, \quad i=1, \ldots, k \\ \quad \sum_{i=1}^{m} \alpha_{i} y_{i}=0
αmaxi=1∑mαi−21i,j=1∑mαiαjyiyj(xiTxjxiTxjxiTxj) s.t. 0≤αi≤C,i=1,…,ki=1∑mαiyi=0
5.4 核方法
以上的求解都是在线性可分的条件下进行的，而事实上大部分时候数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在。对这样的问题可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。幸运的是，如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。
假设一个映射
ϕ
(
x
)
\phi(x)
ϕ(x) 表示将
x
x
x 映射后的特征向量，在特征空间中划分超平面所对应的模型可表示为
f
(
x
)
=
w
T
ϕ
(
x
)
+
b
f(\pmb x) = w^T \phi(\pmb x) + b
f(xxx)=wTϕ(xxx)+b，类似之前的推导，有
min
w
,
b
1
2
∣
∣
w
∣
∣
2
s.t.
y
i
(
w
T
ϕ
(
x
i
)
+
b
)
≥
1
−
ξ
i
,
ξ
i
≥
0
,
i
=
1
,
2
,
.
.
.
,
m
\displaystyle \min_{\pmb w,b} \frac 1 2 ||\pmb w||^2 \quad \text{s.t.}\ y_i(\pmb w^T\phi (\pmb x_i)+b)\ge 1-\xi_i,\quad \xi_i\ge 0,\quad i=1,2,...,m
www,bmin21∣∣www∣∣2s.t. yi(wwwTϕ(xxxi)+b)≥1−ξi,ξi≥0,i=1,2,...,m
对偶问题
max
α
∑
i
=
1
m
α
i
−
1
2
∑
i
,
j
=
1
m
α
i
α
j
y
i
y
j
(
ϕ
(
x
i
)
T
ϕ
(
x
j
)
)
s.t.
0
≤
α
i
≤
C
,
i
=
1
,
…
,
k
∑
i
=
1
m
α
i
y
i
=
0
\max _{\alpha} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j}(\phi(\pmb x_i)^T \phi(\pmb x_j)) \\ \text { s.t. } \quad 0\le \alpha_{i} \le C, \quad i=1, \ldots, k \\ \quad \sum_{i=1}^{m} \alpha_{i} y_{i}=0
αmaxi=1∑mαi−21i,j=1∑mαiαjyiyj(ϕ(xxxi)Tϕ(xxxj)) s.t. 0≤αi≤C,i=1,…,ki=1∑mαiyi=0
可以看到，我们有在高维空间中的内积运算
(
ϕ
(
x
i
)
T
ϕ
(
x
j
)
(\phi(\pmb x_i)^T \phi(\pmb x_j)
(ϕ(xxxi)Tϕ(xxxj)，这在维度较低的时候计算量还行，然而一旦出现很高的维度甚至无穷维，显然我们受不了，于是核函数出现了：
κ
(
x
i
,
x
j
)
=
⟨
ϕ
(
x
i
)
,
ϕ
(
x
j
)
⟩
=
ϕ
(
x
i
)
T
ϕ
(
x
j
)
\kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left\langle\phi\left(\boldsymbol{x}_{i}\right), \phi\left(\boldsymbol{x}_{j}\right)\right\rangle=\phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right)
κ(xi,xj)=⟨ϕ(xi),ϕ(xj)⟩=ϕ(xi)Tϕ(xj)
通过这个函数，我们把原来的高维空间中的内积运算转换成了在原空间中的内积运算。于是，使用这个方法，就将对偶文艺重写为：
max
α
∑
i
=
1
m
α
i
−
1
2
∑
i
,
j
=
1
m
α
i
α
j
y
i
y
j
⋅
κ
(
x
i
,
x
j
)
s.t.
0
≤
α
i
≤
C
,
i
=
1
,
…
,
k
∑
i
=
1
m
α
i
y
i
=
0
\max _{\alpha} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j}\cdot\kappa(\pmb{x_i, x_j}) \\ \text { s.t. } \quad 0\le \alpha_{i} \le C, \quad i=1, \ldots, k \\ \quad \sum_{i=1}^{m} \alpha_{i} y_{i}=0
αmaxi=1∑mαi−21i,j=1∑mαiαjyiyj⋅κ(xi,xjxi,xjxi,xj) s.t. 0≤αi≤C,i=1,…,ki=1∑mαiyi=0
求解后得到的超平面为
f
(
x
)
=
w
T
ϕ
(
x
)
+
b
=
∑
i
∈
S
V
α
i
y
i
ϕ
(
x
i
)
T
ϕ
(
x
)
+
b
=
∑
i
∈
S
V
α
i
y
i
⋅
κ
(
x
i
,
x
)
+
b
\displaystyle f(\pmb x)=w^T\phi(\pmb x)+b= \sum_{i\in SV} \alpha_i y_i \phi(\pmb x_i)^T \phi(\pmb x)+b=\sum_{i\in SV} \alpha_i y_i\cdot \kappa(\pmb{x_i, x})+b
f(xxx)=wTϕ(xxx)+b=i∈SV∑αiyiϕ(xxxi)Tϕ(xxx)+b=i∈SV∑αiyi⋅κ(xi,xxi,xxi,x)+b
6 无监督学习
6.1 层次聚类与距离度量、相似度函数
层次聚类有两种实现方式，一是自底向上的聚合策略 (Bottom-up, agglomerative)，二是自顶向下的分拆策略 (Top-down, divisive)。
- 自底向上聚合：输入样本集后，先将每个点看作一个单独的簇，然后初始化一个距离矩阵，然后每次合并最近的两个簇，一直合并到剩余要求的k个簇，输出结果。合并的历史形成了一个二叉树或层次结构。
- 自顶向下分拆：从数据集中的所有数据开始，考虑将其分成两部分的所有可能方法，选择最好的分法，然后在两边递归操作。
时间复杂度分析：先计算所有点对之间的距离， O ( n 2 ) O(n^2) O(n2)；在每次迭代中，对所有的距离排序，找到最大的距离 O ( n 2 log n ) O(n^2\log n) O(n2logn)，更新合并后的簇和其他簇之间的相似度；为了保持整体 O ( n 2 ) O(n^2) O(n2) 的性能，类之间的相似度计算必须在常数时间内完成；最终，我们得到 O ( n 2 log n ) O(n^2\log n) O(n2logn) 或 O ( n 3 ) O(n^3) O(n3)。
距离度量应该满足的性质
- 对称性：D(A,B) = D(B,A)
- 自反性：D(A,A) =0
- 距离是正数：D(A,B) = 0 IIf A= B
- 三角不等式：D(A,B) < D(A,C) + D(B,C)
层次聚类中关于两个簇的距离 (相似度) 的度量，不同的度量方式有可能导致不同的聚类结果：
- Single-link：两个簇之间最近的两个点的距离
- Complete-link：两个簇之间最远的两个点的距离
- Centroid：两个簇中心的距离
- Average-link：所有跨簇对的平均值
相似度函数：
-
闵可夫斯基度量 Minkowski Metric：r阶 d ( x , y ) = ∑ i = 1 p ∣ x i − y i ∣ r r \quad \displaystyle d(x, y)=\sqrt[^r]{\sum_{i=1}^{p}\left|x_{i}-y_{i}\right|^{r}} d(x,y)=ri=1∑p∣xi−yi∣r
- r = 2 r=2 r=2 欧式距离(Euclidean distance) d ( x , y ) = ∑ i = 1 p ∣ x i − y i ∣ 2 2 \quad\displaystyle d(x, y)=\sqrt[^2]{\sum_{i=1}^{p}\left|x_{i}-y_{i}\right|^{2}} d(x,y)=2i=1∑p∣xi−yi∣2
- r = 1 r=1 r=1 曼哈顿距离 (Manhattan distance) d ( x , y ) = ∑ i = 1 p ∣ x i − y i ∣ \quad \displaystyle d(x, y)=\sum_{i=1}^{p}|x_{i}-y_{i}| d(x,y)=i=1∑p∣xi−yi∣
- r = + ∞ r=+\infty r=+∞ “sup” distance d ( x , y ) = max 1 ≤ i ≤ p ∣ x i − y i ∣ \quad \displaystyle d(x, y)=\max_{1\le i\le p}|x_{i}-y_{i}| d(x,y)=1≤i≤pmax∣xi−yi∣
-
汉明距离：当所有特征均为二进制时，称曼哈顿距离为汉明距离。其意义是两个等长字符串对应位置的不同字符的个数。
-
相关系数 (Pearson correlation coefficient)：
s ( x , y ) = ∑ i = 1 p ( x i − x ˉ ) ( y i − y ˉ ) ∑ i = 1 p ( x i − x ˉ ) 2 × ∑ i = 1 p ( y i − y ˉ ) 2 ∣ s ( x , y ) ∣ ≤ 1 where x ˉ = 1 p ∑ i = 1 p x i and y ˉ = 1 p ∑ i = 1 p y i \displaystyle s(x, y)=\frac{\sum_{i=1}^{p}\left(x_{i}-\bar{x}\right)\left(y_{i}-\bar{y}\right)}{\sqrt{\sum_{i=1}^{p}\left(x_{i}-\bar{x}\right)^{2} \times \sum_{i=1}^{p}\left(y_{i}-\bar{y}\right)^{2}}} \quad|s(x, y)| \leq 1 \qquad \text{where}\quad \bar{x}=\frac{1}{p} \sum_{i=1}^{p} x_{i} \quad\text{and}\quad \bar{y}=\frac{1}{p} \sum_{i=1}^{p} y_{i} s(x,y)=∑i=1p(xi−xˉ)2×∑i=1p(yi−yˉ)2 ∑i=1p(xi−xˉ)(yi−yˉ)∣s(x,y)∣≤1wherexˉ=p1i=1∑pxiandyˉ=p1i=1∑pyi
-
编辑距离：指两个字串之间，由一个转成另一个所需的最少编辑操作 (包括将一个字符替换成另一个字符，插入一个字符，删除一个字符) 次数
6.2 EM算法
在使用极大似然估计参数时，有可能得到的样本的属性值并不全面，可能存在一些未观测到的属性，这些属性称为隐变量
一般使用对数似然来估计参数，而又由于含有隐变量，所以我们需要先对隐变量做边缘化，于是有如下的表达：
{
L
L
(
Θ
∣
X
)
=
ln
P
(
X
∣
Θ
)
L
L
(
Θ
∣
X
,
Z
)
=
ln
P
(
X
,
Z
∣
Θ
)
⟹
L
L
(
Θ
∣
X
)
=
ln
P
(
X
∣
Θ
)
=
ln
∑
Z
P
(
X
,
Z
∣
Θ
)
\begin{cases} LL(\Theta|X)=\ln P(X|\Theta)\\ LL(\Theta|X, Z)=\ln P(X, Z|\Theta) \end{cases} \Longrightarrow LL(\Theta|X)=\ln P(X|\Theta)=\ln \sum_Z P(X, Z|\Theta)
{LL(Θ∣X)=lnP(X∣Θ)LL(Θ∣X,Z)=lnP(X,Z∣Θ)⟹LL(Θ∣X)=lnP(X∣Θ)=lnZ∑P(X,Z∣Θ)
所以我们有一个直观的想法，先用指定的
Θ
\Theta
Θ 估计一次
Z
Z
Z，然后把估计得到的
Z
Z
Z 带回上式计算
Θ
\Theta
Θ，如此迭代直到收敛，得到的应该是一个较好的解，这就是EM算法：
- 给定一个初始值 Θ ( 0 ) \Theta^{(0)} Θ(0)
- E步：根据 Θ ( t ) \Theta^{(t)} Θ(t) 推断出隐变量 Z Z Z 的期望 Z ( t ) Z^{(t)} Z(t)
- M步：基于已观测的数据 X X X 和 Z ( t ) Z^{(t)} Z(t) 对参数 Θ \Theta Θ 做极大似然估计得到 Θ ( t + 1 ) \Theta^{(t+1)} Θ(t+1)
6.3 K-means
K-means的目的是为了将一组无标签的样本数据分为k个类，称为簇，记为 C = { C 1 , C 2 , . . . , C k } C=\{C_1, C_2,...,C_k \} C={C1,C2,...,Ck}，满足 ∀ i < j ≤ k , C i ∩ C j = ∅ \forall i<j\le k,\ C_i\cap C_j = \empty ∀i<j≤k, Ci∩Cj=∅
K-means的思想是通过随机选择一组（k个）初始的聚类中心，然后计算样本点距离哪个中心最近，然后就把这个样本点标记为这个中心代表的这一类，全部标记结束后，就可以得到k个簇，于是可以通过求平均值的方式得到每个簇的新的中心，如此往复，直到中心点不再变化就说明划分完成了。
所以K-means基于以下两个公式：每次最小化
E
E
E 然后重新求均值
E
=
∑
i
=
1
k
∑
x
∈
C
i
∣
∣
x
−
μ
i
∣
∣
2
2
μ
i
=
1
∣
C
i
∣
∑
x
∈
C
i
x
i
E=\sum^k_{i=1}\sum_{x\in C_i}||x-\mu_i||^2_2\\ \mu_i=\frac 1 {|C_i|}\sum_{x\in C_i}x_i
E=i=1∑kx∈Ci∑∣∣x−μi∣∣22μi=∣Ci∣1x∈Ci∑xi
时间复杂度：在每一次迭代，计算n个物体与K个聚类中心之间的距离为 O ( K n ) O(Kn) O(Kn)；计算质心，每个对象添加一次到某个质心为 O ( n ) O(n) O(n)；假设这两个步骤在 l l l 次迭代中各执行一次， O ( l K n ) O(lKn) O(lKn)。
在K-means中，种子的选取非常重要，随机选择种子的结果会有所不同，有些种子会导致收敛速度较差，或收敛到次优聚类。
6.4 GMM
GMM是混合高斯分布模型，它基于这样一个思想：如果我们要将一组数据分为k个类(簇)，那么这组数据有可能是由k个多元高斯分布生成的，所以每个点都以一定的概率由其中的某个高斯分布生成，所以我们只需要取生成概率最大的哪个高斯分布即可。
基于以上的思想，我们可以用 k 个 d 元高斯分布的线性叠加来表达一个点
x
i
x_i
xi：
p
(
x
i
)
=
∑
j
=
1
k
π
j
p
(
x
i
∣
,
u
j
,
Σ
j
)
(6.4.1)
p(x_i)=\sum^k_{j=1}\pi_jp(x_i|,u_j, \Sigma_j)\\ \tag{6.4.1}
p(xi)=j=1∑kπjp(xi∣,uj,Σj)(6.4.1)
p ( x i ∣ μ j , Σ j ) = 1 ( 2 π ) d 2 ∣ Σ j ∣ 1 2 exp ( − 1 2 ( x i − μ j ) T Σ j − 1 ( x i − μ j ) ) (6.4.2) p(x_i|\mu_j, \Sigma_j)=\frac 1 {(2\pi)^\frac d 2 |\Sigma_j|^\frac 1 2}\exp(-\frac 1 2(x_i-\mu_j)^T\Sigma^{-1}_j(x_i-\mu_j)) \tag{6.4.2} p(xi∣μj,Σj)=(2π)2d∣Σj∣211exp(−21(xi−μj)TΣj−1(xi−μj))(6.4.2)
其中 μ j \mu_j μj 和 Σ j \Sigma_j Σj 是第 j j j 个高斯分布的均值和协方差矩阵， π j \pi_j πj 为相应的混合系数，而由于该数据必定由 k k k 个高斯分布中的某个生成，所以满足 ∑ j = 1 k π j = 1 \displaystyle\sum^k_{j=1}\pi_j=1 j=1∑kπj=1，因此实际上可以认为 π j \pi_j πj 就是它属于各个高斯分布的先验概率。
同样由于该数据必定由
k
k
k 个高斯分布中的某个生成，所以我们可以定义一个隐变量
z
i
z_i
zi，它表示的是
x
i
x_i
xi 由哪一个高斯分布生成，所以可以使用 0/1 来表示，一个点显然只能属于一个高斯分布，所以
z
i
z_i
zi 中只有一位是1，其余为0。上文说
π
j
\pi_j
πj 是
x
i
x_i
xi 属于各个高斯分布的先验概率，所以就可以用下式来表达
z
i
z_i
zi 的先验概率分布：
p
(
z
i
)
=
∏
j
=
1
k
π
j
z
i
j
⟺
p
(
z
i
j
=
1
)
=
π
j
(6.4.3)
p(z_i)=\prod^k_{j=1} \pi^{z_{ij}}_j \quad\Longleftrightarrow\quad p(z_{ij}=1)=\pi_j \tag {6.4.3}
p(zi)=j=1∏kπjzij⟺p(zij=1)=πj(6.4.3)
E步
在已知
x
i
x_i
xi 后确定
z
i
z_i
zi 的后验概率分布为：
p
(
z
i
j
=
1
∣
x
i
)
=
p
(
z
i
j
=
1
)
p
(
x
i
∣
z
i
j
=
1
)
p
(
x
i
)
=
π
j
⋅
p
(
x
i
∣
μ
j
,
Σ
j
)
∑
l
=
1
k
π
l
p
(
x
i
∣
μ
l
,
Σ
l
)
p(z_{ij}=1|x_i) = \frac {p(z_{ij}=1)p(x_i|z_{ij}=1)}{p(x_i)} = \frac{\pi_j\cdot p(x_i|\mu_j, \Sigma_j)}{\sum\limits_{l=1}^k\pi_lp({x_i}|{\mu_l}, \Sigma_l)}
p(zij=1∣xi)=p(xi)p(zij=1)p(xi∣zij=1)=l=1∑kπlp(xi∣μl,Σl)πj⋅p(xi∣μj,Σj)
其中， p ( z i j = 1 ) p(z_{ij}=1) p(zij=1) 由式 ( 6.4.3 ) (6.4.3) (6.4.3) 定义， p ( x i ∣ z i j = 1 ) p(x_i|z_{ij}=1) p(xi∣zij=1) 由式 ( 6.4.2 ) (6.4.2) (6.4.2) 定义， p ( x i ) p(x_i) p(xi) 由式 ( 6.4.1 ) (6.4.1) (6.4.1) 定义。
得到后验概率之后，我们就可以从中挑选一个最大的后验概率，用它的高斯分布类别标识点 x i x_i xi，即求 j = arg max j p ( z i j = 1 ∣ x i ) j=\arg\displaystyle\max_j p(z_{ij}=1|x_i) j=argjmaxp(zij=1∣xi)
M步
而对于每一个高斯分布涉及到的所有的参数：
π
j
,
μ
j
,
Σ
j
\pi_j,\; \mu_j,\; \Sigma_j
πj,μj,Σj，就可以使用 (对数) 极大似然估计来求解，所以有下式：
ln
p
(
X
∣
π
,
μ
,
Σ
)
=
ln
∏
i
=
1
n
p
(
x
i
)
=
∑
i
=
1
n
ln
p
(
x
i
)
=
∑
i
=
1
n
ln
∑
j
=
1
k
π
j
p
(
x
i
∣
,
u
j
,
Σ
j
)
\ln p(X|\pi, \mu, \Sigma) = \ln \prod_{i=1}^n p(x_i)=\sum_{i=1}^n \ln p(x_i) = \sum_{i=1}^n \ln \sum^k_{j=1}\pi_jp(x_i|,u_j, \Sigma_j)
lnp(X∣π,μ,Σ)=lni=1∏np(xi)=i=1∑nlnp(xi)=i=1∑nlnj=1∑kπjp(xi∣,uj,Σj)
对
μ
j
,
Σ
j
\mu_j, \Sigma_j
μj,Σj 分别求偏导，并令导数等于0，得：
∂
ln
p
(
X
∣
π
,
μ
,
Σ
)
∂
μ
j
=
∑
i
=
1
n
π
j
p
(
x
i
∣
μ
j
,
Σ
j
)
∑
l
=
1
k
π
l
p
(
x
i
∣
μ
l
,
Σ
l
)
Σ
j
−
1
(
x
i
−
μ
j
)
=
0
∂
ln
p
(
X
∣
π
,
μ
,
Σ
)
∂
Σ
j
=
∑
i
=
1
n
π
j
p
(
x
i
∣
μ
j
,
Σ
j
)
∑
l
=
1
k
π
l
p
(
x
i
∣
μ
l
,
Σ
l
)
(
Σ
j
−
1
−
Σ
j
−
1
(
x
i
−
μ
j
)
(
x
i
−
μ
j
)
T
Σ
j
−
1
)
=
0
\frac {\partial \ln p(X|\pi, \mu, \Sigma)} {\partial \mu_j} = \sum_{i=1}^n \frac{\pi_j p(x_i| \mu_j, \Sigma_j)}{\displaystyle\sum_{l=1}^k \pi_l p(x_i| \mu_l, \Sigma_l)} \Sigma_j^{-1}(x_i - \mu_j) = 0\\ \frac {\partial \ln p(X|\pi, \mu, \Sigma)} {\partial \Sigma_j} = \sum_{i=1}^n \frac{\pi_j p(x_i| \mu_j, \Sigma_j)}{\displaystyle\sum_{l=1}^k \pi_l p(x_i| \mu_l, \Sigma_l)} (\Sigma_j^{-1} - \Sigma_j^{-1}(x_i -\mu_j)(x_i -\mu_j)^T\Sigma_j^{-1}) = 0
∂μj∂lnp(X∣π,μ,Σ)=i=1∑nl=1∑kπlp(xi∣μl,Σl)πjp(xi∣μj,Σj)Σj−1(xi−μj)=0∂Σj∂lnp(X∣π,μ,Σ)=i=1∑nl=1∑kπlp(xi∣μl,Σl)πjp(xi∣μj,Σj)(Σj−1−Σj−1(xi−μj)(xi−μj)TΣj−1)=0
记
γ
(
z
i
j
)
=
p
(
z
j
=
1
∣
x
i
)
∑
j
=
1
k
p
(
z
j
=
1
∣
x
i
)
=
π
j
p
(
x
i
∣
μ
j
,
Σ
j
)
∑
l
=
1
k
π
l
p
(
x
i
∣
μ
l
,
Σ
l
)
n
j
=
∑
i
=
1
n
γ
(
z
i
j
)
\gamma(z_{ij}) =\frac {p(z_j = 1|x_i)}{\displaystyle\sum_{j=1}^k p(z_j = 1|x_i)}=\frac{\pi_j p(x_i| \mu_j, \Sigma_j)}{\displaystyle\sum_{l=1}^k \pi_l p(x_i| \mu_l, \Sigma_l)}\\ n_j = \sum_{i=1}^n \gamma(z_{ij})
γ(zij)=j=1∑kp(zj=1∣xi)p(zj=1∣xi)=l=1∑kπlp(xi∣μl,Σl)πjp(xi∣μj,Σj)nj=i=1∑nγ(zij)
则上两式解得
μ
j
=
1
n
j
∑
i
=
1
n
γ
(
z
i
j
)
x
i
(6.4.4)
\mu_j = \frac 1 {n_j}\sum_{i=1}^n\gamma(z_{ij})x_i \tag{6.4.4}
μj=nj1i=1∑nγ(zij)xi(6.4.4)
Σ j = 1 n j ∑ i = 1 n γ ( z i j ) ( x i − μ j ) ( x i − μ j ) T (6.4.5) \Sigma_j = \frac 1 {n_j}\displaystyle\sum_{i=1}^n\gamma(z_{ij})(x_i -\mu_j)(x_i -\mu_j)^T \tag{6.4.5} Σj=nj1i=1∑nγ(zij)(xi−μj)(xi−μj)T(6.4.5)
显然，这两个式子都是递推式，需要迭代求解。
对于混合系数 π j \pi_j πj，还需要满足约束条件 ∑ j = 1 k π j = 1 \displaystyle\sum^k_{j=1}\pi_j=1 j=1∑kπj=1，所以构造拉格朗日多项式，对 π j \pi_j πj 求导，令导数为0：
L ( π j ) = ln p ( X ∣ π , μ , Σ ) + λ ( ∑ j = 1 k π j − 1 ) ∂ ln p ( X ∣ π , μ , Σ ) + λ ( ∑ j = 1 k π j − 1 ) ∂ π j = ∑ i = 1 n p ( x i ∣ μ j , Σ j ) ∑ l = 1 k π l p ( x i ∣ μ l , Σ l ) + λ = 0 L(\pi_j)=\ln p(X|\pi, \mu, \Sigma) + \lambda(\sum_{j=1}^k \pi_j - 1)\\ \frac {\partial \ln p(X|\pi, \mu, \Sigma) + \lambda(\displaystyle\sum_{j=1}^k \pi_j - 1)} {\partial \pi_j} =\sum_{i=1}^n \frac{p(x_i| \mu_j, \Sigma_j)}{\displaystyle\sum_{l=1}^k \pi_l p(x_i| \mu_l, \Sigma_l)} + \lambda = 0 L(πj)=lnp(X∣π,μ,Σ)+λ(j=1∑kπj−1)∂πj∂lnp(X∣π,μ,Σ)+λ(j=1∑kπj−1)=i=1∑nl=1∑kπlp(xi∣μl,Σl)p(xi∣μj,Σj)+λ=0
同乘 π j \pi_j πj 并将 j ∈ 1 , 2 , . . . , k j \in {1,2,...,k} j∈1,2,...,k 代入相加得：
∑ j = 1 k π j ∑ i = 1 n p ( x i ∣ μ j , Σ j ) ∑ l = 1 k π l p ( x i ∣ μ l , Σ l ) + λ ∑ j = 1 k π j = 0 \sum_{j=1}^k \pi_j\sum_{i=1}^n \frac{p(x_i| \mu_j, \Sigma_j)}{\displaystyle\sum_{l=1}^k \pi_l p(x_i| \mu_l, \Sigma_l)} + \lambda\sum_{j=1}^k \pi_j = 0 j=1∑kπji=1∑nl=1∑kπlp(xi∣μl,Σl)p(xi∣μj,Σj)+λj=1∑kπj=0
将约束条件代入：
∑ i = 1 n ( ∑ j = 1 k π j p ( x i ∣ μ j , Σ j ) ∑ l = 1 k π l p ( x i ∣ μ l , Σ l ) ) + λ ∑ j = 1 k π j = n + λ = 0 \sum_{i=1}^n (\frac{\displaystyle\sum_{j=1}^k \pi_j p(x_i| \mu_j, \Sigma_j)}{\displaystyle\sum_{l=1}^k \pi_l p(x_i| \mu_l, \Sigma_l)}) + \lambda\sum_{j=1}^k \pi_j = n + \lambda = 0 i=1∑n(l=1∑kπlp(xi∣μl,Σl)j=1∑kπjp(xi∣μj,Σj))+λj=1∑kπj=n+λ=0
即 λ = − n \lambda = -n λ=−n，代入 ∑ i = 1 n p ( x i ∣ μ j , Σ j ) ∑ l = 1 k π l p ( x i ∣ μ l , Σ l ) + λ = 0 \displaystyle\sum_{i=1}^n \frac{p(x_i| \mu_j, \Sigma_j)}{\displaystyle\sum_{l=1}^k \pi_l p(x_i| \mu_l, \Sigma_l)} + \lambda = 0 i=1∑nl=1∑kπlp(xi∣μl,Σl)p(xi∣μj,Σj)+λ=0 中，得
π j = n j n (6.4.6) \pi_j = \frac {n_j}{n} \tag{6.4.6} πj=nnj(6.4.6)
显然，这个参数与上一轮的迭代结果无关，它是每一轮的平均后验概率。
所以，M步主要依靠 ( 6.4.4 ) ( 6.4.5 ) ( 6.4.6 ) (6.4.4)(6.4.5)(6.4.6) (6.4.4)(6.4.5)(6.4.6) 这三个式子来更新参数，以使下一轮求得的后验概率最大化。
6.5 PCA
PCA(主成分分析，Principal Component Analysis)是最常用的一种降维方法。PCA的主要思想是将D维特征通过一组投影向量映射到K维上，这K维是全新的正交特征，称之为主成分，采用主成分作为数据的代表，有效地降低了数据维度，且保留了最多的信息。关于PCA的推导有两种方式：
- 最大投影方差：样本点在这个超平面上的投影尽可能分开
- 最小投影距离：样本点到这个超平面的距离都足够近
6.5.1 中心化
在开始PCA之前需要对数据进行预处理，即对数据中心化。设数据集 X = { x 1 , x 2 , . . . , x n } X=\{x_1, x_2, ..., x_n\} X={x1,x2,...,xn}，其中 x i = { x i 1 , x i 2 , . . . , x i d } x_i = \{x_{i1}, x_{i2}, ..., x_{id}\} xi={xi1,xi2,...,xid}，即 X X X 是一个 n × d n \times d n×d 的矩阵。则此数据集的中心向量（均值向量）为：
μ
=
1
n
∑
i
=
1
n
x
i
\mu = \frac 1 n \sum_{i=1}^n x_i
μ=n1i=1∑nxi
对数据集每个样本均进行操作：
x
i
=
x
i
−
μ
x_i = x_i - \mu
xi=xi−μ，就得到了中心化后的数据，此时有
∑
i
=
1
n
x
i
=
0
\displaystyle\sum_{i=1}^n x_i=0
i=1∑nxi=0。
中心化可以给后面的计算带来极大的便利，因为中心化之后的常规线性变换就是绕原点的旋转变化，也就是坐标变换。此时，协方差为 S = 1 n ∑ i = 1 n x i x i T = 1 n X T X S=\displaystyle\frac 1 n\sum_{i=1}^n x_i x_i^T=\frac 1 n X^T X S=n1i=1∑nxixiT=n1XTX
设使用的投影坐标系的一组标准正交基为 U k × d = { u 1 , u 2 , . . . , u k } , k < d , u i = { u i 1 , u i 2 , . . . , u i d } U_{k\times d}=\{u_1, u_2, ..., u_k\},\ k<d, u_i = \{u_{i1}, u_{i2}, ..., u_{id}\} Uk×d={u1,u2,...,uk}, k<d,ui={ui1,ui2,...,uid}，故有 U U T = 1 UU^T=1 UUT=1，使用这组基变换中心化矩阵 X X X，得降维压缩后的矩阵 Y n × k = X U T Y_{n \times k}=XU^T Yn×k=XUT，重建得到 X ^ = Y U = X U T U \hat X=YU=XU^TU X^=YU=XUTU。
6.5.2 最大投影方差
对于任意一个样本
x
i
x_i
xi，在新的坐标系中的投影为
y
i
=
x
i
U
T
y_i=x_iU^T
yi=xiUT，在新坐标系中的投影方差为
y
i
T
y
i
=
U
x
i
T
x
i
U
T
y_i^Ty_i=Ux_i^T x_iU^T
yiTyi=UxiTxiUT。要使所有的样本的投影方差和最大，也就是求
arg
max
U
∑
i
=
1
n
U
x
i
T
x
i
U
T
\displaystyle\arg\max_U \sum^n_{i=1} Ux_i^T x_iU^T
argUmaxi=1∑nUxiTxiUT，即
arg
max
U
t
r
(
U
X
T
X
U
T
)
s
.
t
.
U
U
T
=
1
\arg \max_U\ tr(UX^TXU^T)\qquad s.t.\ UU^T=1
argUmax tr(UXTXUT)s.t. UUT=1
求解：在 u 1 u_1 u1 方向投影后的方差
1
n
∑
i
=
1
n
{
u
1
T
x
i
−
u
1
T
μ
}
2
=
1
n
(
X
u
1
T
)
T
(
X
u
1
T
)
=
1
n
u
1
X
T
X
u
1
T
=
u
1
S
u
1
T
\frac 1 n \sum_{i=1}^n\{u_1^Tx_i - u_1^T\mu\}^2 = \frac 1 n (Xu_1^T)^T(Xu_1^T)=\frac 1 n u_1X^TXu_1^T=u_1Su_1^T
n1i=1∑n{u1Txi−u1Tμ}2=n1(Xu1T)T(Xu1T)=n1u1XTXu1T=u1Su1T
因为
u
1
u_1
u1 是投影方向，且已经假设它是单位向量，即
u
1
T
u
1
=
1
u_1^Tu_1=1
u1Tu1=1，用拉格朗日乘子法最大化目标函数：
L
(
u
1
)
=
u
1
T
S
u
1
+
λ
1
(
1
−
u
1
T
u
1
)
L(u_1) = u_1^TSu_1 + \lambda_1(1-u_1^Tu_1)
L(u1)=u1TSu1+λ1(1−u1Tu1)
对
u
1
u_1
u1 求导，令导数等于0，解得
S
u
1
=
λ
1
u
1
Su_1 = \lambda_1 u_1
Su1=λ1u1，显然，
u
1
u_1
u1 和
λ
1
\lambda_1
λ1 是一组对应的
S
S
S 的特征向量和特征值，所以有
u
1
T
S
u
1
=
λ
1
u_1^TSu_1 = \lambda_1
u1TSu1=λ1，结合在
u
1
u_1
u1 方向投影后的方差式，可得求得最大化方差，等价于求最大的特征值。
要将 d d d 维的数据降维到 k k k 维，只需计算前 k k k 个最大的特征值，将其对应的特征向量（ d × 1 d\times 1 d×1 的）转为行向量（ 1 × d 1\times d 1×d 的）组合成特征向量矩阵 U k × d U_{k\times d} Uk×d，则降维压缩后的矩阵为 Y = X U T Y=XU^T Y=XUT 。
6.5.3 最小投影距离
现在考虑整个样本集，希望所有的样本到这个超平面的距离足够近，也就是得到
Y
Y
Y 后，与
X
X
X 的距离最小。即求：
arg
min
U
∑
i
=
1
n
∣
∣
x
^
i
−
x
i
∣
∣
2
2
=
arg
min
U
∑
i
=
1
n
∣
∣
x
i
U
T
U
−
x
i
∣
∣
2
2
=
arg
min
U
∑
i
=
1
n
(
(
x
i
U
T
U
)
(
x
i
U
T
U
)
T
−
2
(
x
i
U
T
U
)
x
i
T
+
x
i
x
i
T
)
=
arg
min
U
∑
i
=
1
n
(
x
i
U
T
U
U
T
U
x
i
T
−
2
x
i
U
T
U
x
i
T
+
x
i
x
i
T
)
=
arg
min
U
∑
i
=
1
n
(
−
x
i
U
T
U
x
i
T
+
x
i
x
i
T
)
=
arg
min
U
−
∑
i
=
1
n
x
i
U
T
U
x
i
T
+
∑
i
=
1
n
x
i
x
i
T
⇔
arg
min
U
−
∑
i
=
1
n
x
i
U
T
U
x
i
T
⇔
arg
max
U
∑
i
=
1
n
x
i
U
T
U
x
i
T
=
arg
max
U
t
r
(
U
(
∑
i
=
1
n
x
i
T
x
i
)
U
T
)
=
arg
max
U
t
r
(
U
X
T
X
U
T
)
s
.
t
.
U
U
T
=
1
\begin{aligned} \arg \min_U\sum^n_{i=1} || \hat x_i - x_i ||^2_2 &= \arg \min_U\sum\limits_{i=1}^n||x_iU^TU - x_i||_2^2\\ & =\arg \min_U\sum\limits_{i=1}^n ((x_iU^TU)(x_iU^TU)^T - 2(x_iU^TU)x_i^T + x_ix_i^T) \\ & =\arg \min_U\sum\limits_{i=1}^n (x_iU^TUU^TUx_i^T - 2x_iU^TUx_i^T + x_ix_i^T) \\ & =\arg \min_U \sum\limits_{i=1}^n (-x_iU^TUx_i^T + x_ix_i^T) \\ & =\arg \min_U -\sum\limits_{i=1}^n x_iU^TUx_i^T + \sum\limits_{i=1}^n x_ix_i^T \\ & \Leftrightarrow \arg \min_U -\sum\limits_{i=1}^n x_iU^TUx_i^T \\ & \Leftrightarrow \arg \max_U \sum\limits_{i=1}^n x_iU^TUx_i^T\\ & = \arg \max_U\ tr(U(\sum\limits_{i=1}^n x_i^Tx_i)U^T) \\ & =\arg \max_U\ tr(UX^TXU^T)\qquad s.t.\ UU^T=1 \end{aligned}
argUmini=1∑n∣∣x^i−xi∣∣22=argUmini=1∑n∣∣xiUTU−xi∣∣22=argUmini=1∑n((xiUTU)(xiUTU)T−2(xiUTU)xiT+xixiT)=argUmini=1∑n(xiUTUUTUxiT−2xiUTUxiT+xixiT)=argUmini=1∑n(−xiUTUxiT+xixiT)=argUmin−i=1∑nxiUTUxiT+i=1∑nxixiT⇔argUmin−i=1∑nxiUTUxiT⇔argUmaxi=1∑nxiUTUxiT=argUmax tr(U(i=1∑nxiTxi)UT)=argUmax tr(UXTXUT)s.t. UUT=1
可以看到，这个式子与我们在最大投影方差中得到的式子是一致的，这就说明了这两种方式求得的结果是相同的。