机器学习与数据挖掘(上)——期末复习
机器学习与数据挖掘(下)——期末复习
预备概念
过拟合与欠拟合
过拟合
过拟合定义 当学习器把训练样本学的“太好”了的时候，很可能已经把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，这样就会导致泛化性能下降，这种现象称为过拟合。 过拟合原因
训练数据中噪音干扰过大，使得学习器认为部分噪音是特征从而扰乱学习规则。建模样本选取有误，例如训练数据太少，抽样方法错误，样本label错误等，导致样本不能代表整体。模型不合理，或假设成立的条件与实际不符。特征维度/参数太多，导致模型复杂度太高。 过拟合解决办法
数据角度 从数据源头获取更多数据 数据增强（Data Augmentation）:通过一定规则扩充数据。如物体在图像中的位置、姿态、尺度、整体图片明暗度等都不会影响分类结果。 获取额外数据进行交叉验证 模型角度
降低模型复杂度： 对于神经网络：减少网络的层数、神经元个数等均可以限制网络的拟合能力。dropout，在向前传播的时候，让某个神经元的激活值以一定的概率p停止工作，这样可以使模型的泛化性更强，因为它不会太依赖某些局部的特征。 对于决策树：限制树深，剪枝，限制叶节点数量。 特征选择、特征降维 正则化：将权值的大小作为惩罚项加入到损失函数里。 增加噪声 欠拟合
欠拟合定义 欠拟合是指对训练样本的一般性质尚未学好。在训练集及测试集上的表现都不好。 欠拟合原因 模型复杂度过低，特征量过少 欠拟合解决办法
增加特征数；当特征不足或者现有特征与样本标签的相关性不强时，模型易出现欠拟合。 可以通过挖掘上下文特征，ID类特征，组合特征等新的特征，可以取得较好的效果增加模型复杂度； 模型简单时其表达能力较差，容易导致欠拟合，因此可以适当地增加模型复杂度，使模型拥有更强的拟合能力。 如线性模型中添加高次项，神经网络中增加网络层数或神经元个数。尝试非线性模型，比如核SVM 、决策树、DNN等模型减小正则化系数。 正则化是用于防止过拟合的，但是当出现欠拟合时，就有必要针对性地减小正则化系数。
正则化
简单来说，在使用神经网络时，为了增加模型的泛化能力，防止模型只在训练集上有效、在测试集上不够有效，我们使用正则化。
L
0
L_0
L0范数
L
0
L_0
L0范数是指向量中非零元素的个数:
∥
X
∥
0
=
∑
i
=
0
n
x
i
0
\Vert X\Vert_0=\sum^{n}_{i=0}x_i^0
∥X∥0=i=0∑nxi0 若用
L
0
L_0
L0范数来规则化参数矩阵，就是希望参数矩阵大部分元素都为0，使特征矩阵稀疏。但是很难优化求解。
L
1
L_1
L1范数
L
1
L_1
L1范数是指向量中各个绝对值元素之和：
∥
X
∥
1
=
∑
i
=
0
n
∣
x
i
∣
\Vert X\Vert_1=\sum^{n}_{i=0}\vert x_i\vert
∥X∥1=i=0∑n∣xi∣ 因为参数的大小与模型的复杂度成正比，所以模型越复杂，范数就越大。使用范数也可以实现特征稀疏。正则化是正则化的最优凸近似，相对范数的优点是容易求解，因此通常都是用范数进行正则化，而不是范数。
L
2
L_2
L2范数
L
2
L_2
L2范数是各参数的平方和再求平方根:
∥
X
∥
2
=
∑
i
=
0
n
∣
x
i
∣
2
\Vert X\Vert_2=\sqrt{\sum^{n}_{i=0}\vert x_i\vert^2}
∥X∥2=i=0∑n∣xi∣2
让
L
2
L_2
L2范数的正则化项
∥
W
∥
2
\Vert W\Vert_2
∥W∥2最小，可以使W的每个元素都很小，都接近于零。但是与范数
L
1
L_1
L1不同，它不使每个元素都为0，而是接近于零。越小的参数模型越简单，越简单的模型越不容易产生过拟合现象。
L
2
L_2
L2范数不仅可以防止过拟合，而且还使优化求解变得稳定与迅速。 L_2范数解决在用正规方程进行最小化代价函数时矩阵可能会不可逆的问题：
∂
∂
θ
j
J
(
θ
)
⟼
s
e
t
0
:
θ
=
(
X
T
X
)
−
1
X
T
y
\frac{\partial}{\partial\theta_j}J(\theta)\overset{set}{\longmapsto}0:\theta=(X^TX)^{-1}X^Ty
∂θj∂J(θ)⟼set0:θ=(XTX)−1XTy 但是如果样本的数目
m
m
m比特征参数
n
n
n要小的时候，也就是方程组的个数小于未知数的个数，那么
X
T
X
X^T X
XTX将会是不满秩的，也就是
X
T
X
X^T X
XTX不可逆，那么就无法求出最优解。在加上正则项后：
θ
=
(
X
T
X
+
λ
I
)
−
1
X
T
y
\theta=(X^TX+\lambda I)^{-1}X^Ty
θ=(XTX+λI)−1XTy 就会保证
(
X
T
X
+
λ
I
)
(X^TX+\lambda I)
(XTX+λI)是可逆的。 Dropout正则化
L
1
、
L
2
L_1、L_2
L1、L2正则化是通过修改损失函数来实现的，而Dropout则是通过修改神经网络本身来实现的，它是在训练网络时用的一种技巧(trick)。每一次训练神经网络时，随机丢弃一部分神经元，下一次训练时，再随机丢掉一部分神经元，那么这样我们也可以有效降低过拟合效应。
机器学习中的目标函数
几乎所有的机器学习算法最后都归结为求解最优化问题，以达到我们想让算法达到的目标。为了完成某一目标，需要构造出一个“目标函数”来，然后让该函数取极大值或极小值，从而得到机器学习算法的模型参数。
感知器算法的是最简单的线性分类器，它的目标是让所有样本尽可能分类。对于二分类问题，线性分类器的判别函数为：
s
g
n
(
w
T
x
+
b
)
sgn(w^Tx+b)
sgn(wTx+b) 样本的标签值为+1或-1，分别对应正样本和负样本。如果线性函数预测出来的值和样本的真实标签值不同号，则预测错误；如果同号，则预测正确。要将预测错误最小化，只需求解如下最优化问题即可：
min
∑
i
=
1
l
−
y
i
(
w
T
x
i
+
b
)
\min\sum^l_{i=1}-y_i(w^Tx_i+b)
mini=1∑l−yi(wTxi+b) 对于二分类或多分类问题，都可以用欧氏距离作为分类的损失函数。对于多分类问题，一般不直接用类别编号作为预测值，而是为类别进行向量化编码，如one-hot编码。此时损失函数定义为：
min
1
2
l
∑
i
=
1
l
∥
h
(
x
i
)
−
y
i
∥
2
2
\min\frac1{2l}\sum^l_{i=1}\Vert h(x_i)-y_i\Vert _{2}^2
min2l1i=1∑l∥h(xi)−yi∥22 线性判别分析（LDA）是一种有监督的数据降维算法，它的目标是最大化类间差异，最小化类内差异。数据经过投影之后，在低维空间里，同类样本聚集在一起，不同类的样本相距尽可能远。类内差异用每个类的方差来衡量，类间差异用各个类的类中心之间的距离来衡量，二者的比值为我们要优化的目标。由此构造出如下损失函数：
max
L
(
W
)
=
t
r
(
W
T
S
B
W
)
t
r
(
W
T
S
W
W
)
\max L(W)=\frac{tr(W^TS_BW)}{tr(W^TS_WW)}
maxL(W)=tr(WTSWW)tr(WTSBW) 支持向量机不仅要让所有训练样本尽可能被正确分类，还要让分类间隔最大化，根据解析几何中点到超平面的距离公式，我们构造出了它的优化目标：
min
1
2
w
T
w
+
C
∑
i
=
1
l
ξ
i
y
i
(
w
T
x
i
+
b
)
≥
1
−
ξ
i
ξ
i
≥
0
,
i
=
1
,
…
,
l
\begin{aligned} &\min \frac12 w^Tw+C\sum_{i=1}^{l}\xi_i\\ &y_i(w^Tx_i+b)\ge1-\xi_i\\ &\xi_i\ge0,i=1,\ldots,l \end{aligned}
min21wTw+Ci=1∑lξiyi(wTxi+b)≥1−ξiξi≥0,i=1,…,l 逻辑回归是输出概率值的模型，可以采用最大似然估计来估计模型的参数。对于二分类问题，如果样本的类别标签值为1和0，则对数似然函数为：
max
L
(
w
)
=
∑
i
=
1
l
(
y
i
log
h
(
x
i
)
+
(
1
−
y
i
)
log
(
1
−
h
(
x
i
)
)
)
\max L(w)=\sum_{i=1}^{l}(y_i\log h(x_i)+(1-y_i)\log (1-h(x_i)))
maxL(w)=i=1∑l(yilogh(xi)+(1−yi)log(1−h(xi))) 将逻辑回归推广到多分类问题，即softmax回归，它输出一个样本属于每个类的概率值。因此，训练样本的标签值为一个向量，如果样本属于某一类，该分量为1，其他分量为0。损失函数根据标签向量与预测出的概率向量构造，使用的是softmax交叉熵，定义为：
min
L
(
θ
)
=
−
1
m
(
∑
i
=
1
m
∑
j
=
1
k
1
{
y
i
=
j
}
log
e
θ
j
T
x
i
∑
l
=
1
k
e
θ
l
T
x
i
)
\min L(\theta)=-\frac1m(\sum_{i=1}^{m}\sum_{j=1}^k1\{y_i=j\}\log\frac{e^{\theta^T_jx_i}}{\sum^k_{l=1}e^{\theta_l^Tx_i}})
minL(θ)=−m1(i=1∑mj=1∑k1{yi=j}log∑l=1keθlTxieθjTxi) 其中，
1
{
⋅
}
1\{·\}
1{⋅}是示性函数，即1{值为真的表达式}=1，1{值为假的表达式}=0。 线性回归，这是最简单的回归算法，其损失函数为：
L
(
w
,
b
)
=
1
2
l
∑
i
=
1
l
(
w
T
x
i
+
b
−
y
i
)
2
L(w,b)=\frac1{2l}\sum^l_{i=1}(w^Tx_i+b-y_i)^2
L(w,b)=2l1i=1∑l(wTxi+b−yi)2 如果加上L1和L2正则化项，则分别得到LASSO回归和岭回归。 生成对抗网络由一个生成模型与一个判别模型构成，前者先用样本进行学习，然后可以生成和真实样本服从相同分布的样本数据。后者对生成模型生成的样本以及真实样本进行判定，确定一个样本是生成的，还是真实的。 训练的目标是，生成模型要尽可能的欺骗判别模型，即让判别模型把自己生成的样本判定为真实样本；判别模型的目标是准确的区分出真实样本和生成的样本，尽可能的把生成模型产生的模型鉴别处理，即判定为假。由此构造出如下的目标函数
V
(
D
,
G
)
V(D,G)
V(D,G)：
min
G
max
D
V
(
D
,
G
)
=
E
x
∽
p
d
a
t
a
(
x
)
[
log
D
(
x
)
]
+
E
z
∽
p
n
o
i
s
e
(
z
)
[
log
(
1
−
D
(
G
(
z
)
)
)
]
\underset{G}{\min}\underset{D}{\max}V(D,G)=E_{x\backsim p_{data}(x)}[\log D(x)]+E_{z\backsim p_{noise}(z)}[\log(1-D(G(z)))]
GminDmaxV(D,G)=Ex∽pdata(x)[logD(x)]+Ez∽pnoise(z)[log(1−D(G(z)))] 其中，
E
(
∗
)
E(*)
E(∗)表示分布函数的期望值，
P
d
a
t
a
(
x
)
P_{data}(x)
Pdata(x)代表着真实样本的分布，
P
n
o
i
s
e
(
z
)
P_{noise}(z)
Pnoise(z)是 定义在低维的噪声分布。 主成分分析的优化目标是最小化重构误差，即用投影到低维空间中的向量近似重构原始向量，二者之间的误差要尽可能的小。最小化重构误差的目标为：
min
∑
i
=
1
n
∥
m
+
∑
j
=
1
d
a
i
j
e
j
−
x
i
∥
2
\min \sum^n_{i=1}\Vert m+\sum_{j=1}^{d}a_{ij}e_j-x_i\Vert^2
mini=1∑n∥m+j=1∑daijej−xi∥2 自动编码器是一种特殊的神经网络，由编码器和解码器两部分构成。前者对输入数据进行映射，得到编码后的向量；后者对编码后的向量进行重构，恢复出原始向量。解码器只在训练时使用，训练完成之后，只需要编码器这一部分，用于对输入数据进行降维或特征提取。其训练时的目标函数为：
min
1
2
l
∑
i
=
1
l
∥
x
i
−
g
θ
(
h
θ
(
x
i
)
)
∥
2
2
\min \frac{1}{2l}\sum_{i=1}^{l}\Vert x_i -g_{\theta}(h_{\theta}(x_i))\Vert_2^2
min2l1i=1∑l∥xi−gθ(hθ(xi))∥22
梯度下降法
梯度下降法又称最速下降法，是求解无约束最优化问题的一种最常用的方法，在对损失函数最小化时经常使用。梯度下降法是一种迭代算法。选取适当的初值x(0)，不断迭代，更新x的值，进行目标函数的极小化，直到收敛。由于负梯度方向时使函数值下降最快的方向，在迭代的每一步，以负梯度方向更新x的值，从而达到减少函数值的目的。
使用微积分里导数，通过求出函数导数的值，从而找到函数下降的方向或者是最低点（极值点）。从几何意义来讲，梯度的方向表示的是函数增加最快的方向，这正是我们下山要找的“最陡峭的方向”的反方向！ 梯度下降法的一般求解框架:
给定待优化连续可微函数
J
(
θ
)
J(\theta)
J(θ)、学习率
α
\alpha
α以及一组初始值
θ
(
0
)
=
(
θ
0
,
θ
1
,
⋯
,
θ
l
)
\theta^{(0)}=(\theta_0,\theta_1,\cdots,\theta_l)
θ(0)=(θ0,θ1,⋯,θl)计算待优化函数的梯度
∇
J
(
θ
(
0
)
)
\nabla J(\theta^{(0)})
∇J(θ(0))更新迭代公式:
θ
(
t
+
1
)
=
θ
(
t
)
−
α
∇
J
(
θ
(
t
)
)
\theta^{(t+1)}=\theta^{(t)}-\alpha \nabla J(\theta^{(t)})
θ(t+1)=θ(t)−α∇J(θ(t))计算
θ
(
t
+
1
)
\theta^{(t+1)}
θ(t+1)处的函数梯度
∇
J
(
θ
(
t
+
1
)
)
\nabla J(\theta^{(t+1)})
∇J(θ(t+1))计算梯度向量的模来判断算法是否收敛:
∥
∇
J
(
θ
(
t
+
1
)
)
∥
≤
ϵ
\Vert \nabla J(\theta^{(t+1)})\Vert\le \epsilon
∥∇J(θ(t+1))∥≤ϵ若收敛，算法停止，否则根据迭代公式继续迭代
学习率
α
\alpha
α：
常见的梯度下降算法
批量梯度下降法（Batch Gradient Descent） 在迭代每一次梯度下降的过程中，都对所有样本数据的梯度进行计算。虽然最终得到的梯度下降的方向较为准确，但是运算会耗费过长的时间。 小批量样本梯度下降（Mini Batch GD) 这个算法在每次梯度下降的过程中，只选取一部分的样本数据进行计算梯度，比如整体样本1/100的数据。在数据量较大的项目中，可以明显地减少梯度计算的时间。 随机梯度下降（Stochastic GD) 随机梯度下降算法只随机抽取一个样本进行梯度计算，由于每次梯度下降迭代只计算一个样本的梯度，因此运算时间比小批量样本梯度下降算法还要少很多，但由于训练的数据量太小（只有一个），因此下降路径很容易受到训练数据自身噪音的影响。
三种方法优缺点对比：
BGDSGDMBGD优点非凸函数可保证收敛至全局最优解计算速度快计算速度快，收敛稳定缺点计算速度缓慢，不允许新样本中途进入计算结果不易收敛，可能会陷入局部最优解中——
熵、条件熵、联合熵
熵是一个随机变量不确定性的度量，对于一个离散型随机变量
X
∼
p
(
x
)
X\sim p(x)
X∼p(x) ，其离散熵可以定义为：
H
(
X
)
=
−
∑
x
∈
χ
p
(
x
)
log
2
p
(
x
)
H(X)=-\sum_{x\in \chi}p(x)\log_2p(x)
H(X)=−x∈χ∑p(x)log2p(x) 一个随机变量的熵越大，意味着不确定性越大，那么也就是说，该随机变量包含的信息量越大。
联合熵
随机变量
X
X
X和
Y
Y
Y的联合熵定义为：
H
(
X
,
Y
)
=
−
∑
x
,
y
p
(
x
,
y
)
log
2
p
(
x
,
y
)
H(X,Y)=-\sum_{x,y}p(x,y) \log_2 p(x,y)
H(X,Y)=−x,y∑p(x,y)log2p(x,y) 联合熵
H
(
X
,
Y
)
H(X,Y)
H(X,Y)表示随机变量
X
X
X和
Y
Y
Y一起发生时的信息熵，即
X
X
X和
Y
Y
Y一起发生时的确定度。
条件熵
H
(
Y
∣
X
)
H(Y|X)
H(Y∣X)由
H
(
Y
∣
X
)
=
−
∑
x
∈
χ
p
(
x
)
log
2
p
(
Y
∣
X
=
x
)
H(Y|X)=-\sum_{x\in \chi}p(x)\log_2 p(Y|X=x)
H(Y∣X)=−x∈χ∑p(x)log2p(Y∣X=x) 定义，其物理意义就是，已知随机变量
X
X
X的情况下，随机变量
Y
Y
Y的信息熵，即在
X
X
X发生的前提下，
Y
Y
Y发生后新带来的不确定度。
条件熵与联合熵的关系为：
H
(
Y
∣
X
)
=
H
(
X
,
Y
)
−
H
(
X
)
H
(
X
∣
Y
)
=
H
(
X
,
Y
)
−
H
(
Y
)
H(Y∣X)=H(X,Y)−H(X)\\ H(X∣Y)=H(X,Y)−H(Y)
H(Y∣X)=H(X,Y)−H(X)H(X∣Y)=H(X,Y)−H(Y)
距离度量
闵可夫斯基距离
d
P
(
x
,
y
)
=
(
∑
i
=
1
n
∣
x
i
−
y
i
∣
P
)
1
P
d_P(x,y)=\left(\sum^n_{i=1}\vert x_i-y_i\vert^P\right)^{\frac1P}
dP(x,y)=(i=1∑n∣xi−yi∣P)P1 当P=1时，可以得到曼哈顿街区距离（简称“曼哈顿距离”）
当P=2时，即可得到欧几里得距离，该公式常用于度量两点之间的直线距离
d
(
x
,
y
)
=
∑
i
=
1
n
(
x
i
−
y
i
)
2
d(x,y)=\sqrt{\sum^n_{i=1}(x_i-y_i)^2}
d(x,y)=i=1∑n(xi−yi)2
训练方法
一般需要将样本分成独立的三部分训练集(train set)，验证集(validation set)和测试集(test set)。一个典型的划分是训练集占总样本的50％，而其它各占25％，三部分都是从样本中随机抽取。
其中训练集用来估计模型验证集用来确定网络结构或者控制模型复杂程度的参数测试集则检验最终选择最优的模型的性能如何。
训练集-验证集-测试集
训练集 训练数据。拟合模型，用这部分数据来建立模型。是一些我们已经知道输入和输出的数据集训练机器去学习，通过拟合去寻找模型的初始参数。 验证集 验证数据。train建了一个模型，但是模型的效果仅体现了训练数据，但不一定适合同类的其他数据，所以建模前数据分成两部分，一部分为训练数据，一部分为验证数据。 是一些我们已经知道输入和输出的数据集，通过让机器学习去优化调整模型的参数，在神经网络中， 我们用验证数据集去寻找最优的网络深度（number of hidden layers)，或者决定反向传播算法的停止点；在普通的机器学习中常用的交叉验证（Cross Validation) 就是把训练数据集本身再细分成不同的验证数据集去训练模型。 测试集 测试数据。跟前两者的最大区别在于：train和validation数据均是同一对象的数据，但是测试，我们就需要用跨对象的数据来验证模型的稳定性。 用户测试模型表现的数据集，根据误差（一般为预测输出与实际输出的不同）来判断一个模型的好坏。
为什么验证数据集和测试数据集两者都需要？
因为验证数据集（Validation Set)用来调整模型参数从而选择最优模型，模型本身已经同时知道了输入和输出，所以从验证数据集上得出的误差（Error)会有偏差（Bias)。但是我们只用测试数据集(Test Set) 去评估模型的表现，并不会去调整优化模型。
留出法
直接将数据集
D
D
D划分为两个互斥的集合，其中一个集合作为训练集
S
S
S，另一个作为测试集
T
T
T。在
S
S
S上训练出模型后，用
T
T
T来评估其测试误差，作为对泛化误差的估计。
留一法 对于整个数据集而言,每次选取一个样本作为验证集,其余样本作为训练集
留P法 对于整个数据集而言，每次选取
P
P
P个样本作为验证集，其余样本作为训练集。
交叉验证
就是进行多次train_test_split划分；每次划分时，在不同的数据集上进行训练、测试评估，从而得出一个评价结果；如果是5折交叉验证，意思就是在原始数据集上，进行5次划分，每次划分进行一次训练、评估，最后得到5次划分后的评估结果，一般在这几次评估结果上取平均得到最后的 评分。k-fold cross-validation ，其中，k一般取5或10。
优点： ①交叉验证通过多次划分，大大降低了这种由一次随机划分带来的偶然性，同时通过多次划分，多次训练，模型也能遇到各种各样的数据，从而提高其泛化能力； ②对数据的使用效率更高，数据量越大，模型准确率越高！缺点： 从上面的图片可以看出来，每次划分时对数据进行均分。设想一下，会不会存在一种情况：数据集有5类，抽取出来的也正好是按照类别划分的5类，也就是说第一折全是0类，第二折全是1类，等等；这样的结果就会导致，模型训练时，没有学习到测试集中数据的特点，从而导致模型得分很低，甚至为0！为了避免这种情况，又出现了其他的各种交叉验证方式。
监督学习
线性回归
线性回归分析（Linear Regression Analysis)是确定两种或两种以上变量间相互依赖的定量关系的一种统计分析方法。
一般用向量形式写成
y
=
w
1
x
1
+
w
2
x
2
+
⋯
+
w
n
x
n
+
b
y
=
∑
i
=
1
n
w
i
x
i
+
b
=
w
T
x
+
b
y=w_1x_1+w_2x_2+\cdots+w_nx_n + b\\ y=\sum_{i=1}^{n}w_ix_i+b=\bold{w}^T\bold{x}+b
y=w1x1+w2x2+⋯+wnxn+by=i=1∑nwixi+b=wTx+b 线性回归模型假设变量相互独立、变量的作用可以叠加。
损失函数的公式（假设数据集有
m
m
m个训练样本，
n
n
n个特征，则平方损失函数公式）
L
(
w
)
=
1
2
∑
j
=
1
m
[
y
(
j
)
−
∑
i
=
1
n
w
i
x
i
(
j
)
−
b
]
2
L(\bold{w})=\frac12\sum^m_{j=1}\left[y^{(j)}-\sum^n_{i=1}w_ix_i^{(j)}-b\right]^2
L(w)=21j=1∑m[y(j)−i=1∑nwixi(j)−b]2 线性回归模型的梯度下降训练如下：
∂
ℓ
(
w
)
∂
(
w
i
)
=
−
∑
j
=
1
m
[
y
(
j
)
−
∑
i
=
1
n
w
i
x
i
(
j
)
−
b
]
∗
x
i
(
j
)
w
i
+
1
=
w
i
−
α
∂
ℓ
(
w
)
∂
(
w
i
)
\frac{\partial \ell(w)}{\partial(w_i)}=-\sum^m_{j=1}\left[y^{(j)}-\sum^n_{i=1}w_ix_i^{(j)}-b\right]*x_i^{(j)}\\ w_{i+1}=w_i-\alpha\frac{\partial \ell(w)}{\partial(w_i)}
∂(wi)∂ℓ(w)=−j=1∑m[y(j)−i=1∑nwixi(j)−b]∗xi(j)wi+1=wi−α∂(wi)∂ℓ(w)
α
\alpha
α：学习率
x
i
(
j
)
x_i^{(j)}
xi(j)：第
j
j
j个样本的第
i
i
i特征
学习率的设置
学习率对模型的影响学习率大学习率小学习速度快慢使用时间点刚开始训练时一定轮数过后副作用易出现损失值爆炸，易振荡易过拟合，收敛速度慢
最理想的学习率不是固定值，而是一个随着训练次数衰减的变化的值，也就是在训练初期，学习率比较大，随着训练的进行，学习率不断减小，直到模型收敛。常用的衰减机制有：
轮数减缓指数减缓分数减缓英文step decayexponential decay
1
/
t
1/t
1/t decay方法每N轮学习率减半学习率按训练轮数增长指数插值递减
l
r
t
=
l
r
0
/
(
1
+
k
t
)
lr_t=lr_0/(1+kt)
lrt=lr0/(1+kt)，
k
k
k控制减缓幅度，
t
t
t为训练轮数
线性回归的优缺点
优点
建模速度快，不需要很复杂的计算，在数据量大的情况下依然运行速度很快；可以根据系给出每个变量的理解和解释。 缺点 不能很好地拟合非线性数据。所以需要先判断变量之间是否是线性关系。
逻辑回归
逻辑回归的原理
用逻辑函数把线性回归的结果从
(
−
∞
,
+
∞
)
(-\infty,+\infty)
(−∞,+∞)映射到
[
0
,
1
]
[0,1]
[0,1]，所以需要知道线性回归。
线性回归函数的数学表达式：
y
=
θ
0
+
θ
1
x
1
+
⋯
+
θ
n
x
n
=
θ
T
x
y=\theta_0 + \theta_1x_1+\cdots + \theta_nx_n=\theta^Tx
y=θ0+θ1x1+⋯+θnxn=θTx。然而线性回归的鲁棒性很差，一个离得比较远的噪声很可能对线性回归模型产生较大的影响，从而影响整个整个训练集的表现。逻辑回归通过减小预测范围，将将预测值限定为[0，1]间。
逻辑函数（Sigmoid/Logistic）：
g
(
z
)
=
1
1
+
e
−
z
\begin{aligned}g(z)=\frac1{1+e^{-z}}\qquad\end{aligned}
g(z)=1+e−z1
函数图像为：
将线性回归函数的结果代入Logistic函数中，得到
h
θ
(
x
)
=
g
(
θ
T
x
)
=
1
1
+
e
−
θ
T
x
\begin{aligned}h_{\theta}(x)=g(\theta^Tx)=\frac 1{1+e^{-\theta^Tx}}\end{aligned}
hθ(x)=g(θTx)=1+e−θTx1
对于二分类任务，结果只有
{
0
,
1
}
\{0,1\}
{0,1}
所以，设
P
(
y
=
1
∣
x
;
θ
)
=
h
θ
(
x
)
P
(
y
=
0
∣
x
;
θ
)
=
1
−
h
θ
(
x
)
P(y=1|x;\theta)=h_{\theta}(x)\qquad P(y=0|x;\theta)=1-h_{\theta}(x)
P(y=1∣x;θ)=hθ(x)P(y=0∣x;θ)=1−hθ(x)，整合到一个公式里，表示为
P
(
y
∣
x
;
θ
)
=
(
h
θ
(
x
)
)
y
(
1
−
h
θ
(
x
)
)
1
−
y
\begin{aligned}P(y|x;\theta)=(h_{\theta}(x))^y(1-h_{\theta}(x))^{1-y}\end{aligned}
P(y∣x;θ)=(hθ(x))y(1−hθ(x))1−y。
这是对于某一个样本而言，事件发生的概率。假设有
m
m
m个样本，那我们就要把这
m
m
m个样本的概率相乘，就是这个合成在一起得到的合事件发生的总概率。即为似然函数：
L
(
θ
)
=
∏
i
=
1
m
P
(
y
i
∣
x
;
θ
)
=
∏
i
=
1
m
(
h
θ
(
x
i
)
)
y
i
(
1
−
h
θ
(
x
i
)
)
1
−
y
i
\begin{aligned}L(\theta)=\prod^m_{i=1}P(y_i|x;\theta)=\prod^m_{i=1}(h_{\theta}(x_i))^{y_i}(1-h_{\theta}(x_i))^{1-y_i}\end{aligned}
L(θ)=i=1∏mP(yi∣x;θ)=i=1∏m(hθ(xi))yi(1−hθ(xi))1−yi，其中
θ
\theta
θ为待求参数。
为了使出现结果的可能性最大，就需要得到极大化似然函数对应的
θ
\theta
θ。为了便于求解，并且不改变单调性，等式两边同时取对数，得到对数似然函数:
l
(
θ
)
=
l
n
(
L
(
θ
)
)
=
∑
i
=
1
m
y
i
l
n
(
h
θ
(
x
i
)
)
+
(
1
−
y
i
)
l
n
(
1
−
h
θ
(
x
i
)
)
\begin{aligned} l(\theta)=ln(L(\theta))=\sum^m_{i=1}y_iln(h_{\theta}(x_i)) + (1-y_i)ln(1-h_{\theta}(x_i)) \end{aligned}
l(θ)=ln(L(θ))=i=1∑myiln(hθ(xi))+(1−yi)ln(1−hθ(xi))
损失函数
如果再对
l
(
θ
)
l(\theta)
l(θ)取负取均值，将
−
1
m
l
(
θ
)
\begin{aligned}- \frac 1ml(\theta)\end{aligned}
−m1l(θ)作为逻辑回归模型的平均损失函数，并使用批量梯度下降法对损失函数进行优化。
根据前文，构造损失函数
J
(
θ
)
=
−
1
m
l
(
θ
)
\begin{aligned}J(\theta) = -\frac 1m l(\theta)\end{aligned}
J(θ)=−m1l(θ)，即在逻辑回归模型中，最大化似然函数和最小化损失函数实际上是等价的。
J
(
θ
)
=
−
1
m
l
n
(
L
(
θ
)
)
=
−
1
m
∑
i
=
1
m
y
i
l
n
(
h
θ
(
x
i
)
)
+
(
1
−
y
i
)
l
n
(
1
−
h
θ
(
x
i
)
)
\begin{aligned} J(\theta)=-\frac1mln(L(\theta))=-\frac1m\sum^m_{i=1}y_iln(h_{\theta}(x_i)) + (1-y_i)ln(1-h_{\theta}(x_i)) \end{aligned}
J(θ)=−m1ln(L(θ))=−m1i=1∑myiln(hθ(xi))+(1−yi)ln(1−hθ(xi))
下降梯度
对损失函数求偏导：(
x
i
j
x_i^j
xij表示第i个样本的第j个特征)
δ
J
(
θ
)
δ
θ
j
=
−
1
m
∑
i
=
1
m
(
y
i
1
h
θ
(
x
i
)
δ
h
θ
(
x
i
)
δ
θ
j
+
(
1
−
y
i
)
1
1
−
h
θ
(
x
i
)
)
δ
h
θ
(
x
i
)
δ
θ
j
=
−
1
m
∑
i
=
1
m
(
y
i
1
g
(
θ
T
x
i
)
−
(
1
−
y
i
)
1
1
−
g
(
θ
T
x
i
)
)
δ
g
(
θ
T
x
i
)
δ
θ
j
=
−
1
m
∑
i
=
1
m
(
y
i
1
g
(
θ
T
x
i
)
−
(
1
−
y
i
)
1
1
−
g
(
θ
T
x
i
)
)
g
(
θ
T
x
i
)
(
1
−
g
(
θ
T
x
i
)
)
δ
θ
T
x
i
δ
θ
j
=
−
1
m
∑
i
=
1
m
(
y
i
(
1
−
g
(
θ
T
x
i
)
)
−
(
1
−
y
i
)
g
(
θ
T
x
i
)
)
x
i
j
=
−
1
m
∑
i
=
1
m
(
y
i
−
g
(
θ
T
x
i
)
)
x
i
j
=
1
m
∑
i
=
1
m
(
h
θ
(
x
i
)
−
y
i
)
x
i
j
\begin{aligned} \frac{\delta J(\theta)}{\delta \theta_j}&=-\frac 1m\sum^m_{i=1}(y_i \frac{1}{h_{\theta}(x_i)}\frac{\delta h_{\theta}(x_i)}{\delta_{\theta_j}}+(1-y_i)\frac{1}{1-h_{\theta}(x_i)})\frac{\delta h_{\theta}(x_i)}{\delta_{\theta_j}} \\ &=-\frac 1m\sum^m_{i=1}(y_i \frac{1}{g(\theta^Tx_i)}-(1-y_i)\frac{1}{1-g(\theta^Tx_i)})\frac{\delta g(\theta^Tx_i)}{\delta_{\theta_j}}\\&=-\frac 1m\sum^m_{i=1}(y_i \frac{1}{g(\theta^Tx_i)}-(1-y_i)\frac{1}{1-g(\theta^Tx_i)})g(\theta^Tx_i)(1-g(\theta^Tx_i))\frac{\delta \theta^Tx_i}{\delta_{\theta_j}}\\&=-\frac 1m\sum^m_{i=1}(y_i (1-g(\theta^Tx_i))-(1-y_i)g(\theta^Tx_i))x_i^j\\ &= -\frac 1m\sum^m_{i=1}(y_i-g(\theta^Tx_i))x_i^j \\&=\frac 1m\sum^m_{i=1}(h_{\theta}(x_i)-y_i)x_i^j\end{aligned}
δθjδJ(θ)=−m1i=1∑m(yihθ(xi)1δθjδhθ(xi)+(1−yi)1−hθ(xi)1)δθjδhθ(xi)=−m1i=1∑m(yig(θTxi)1−(1−yi)1−g(θTxi)1)δθjδg(θTxi)=−m1i=1∑m(yig(θTxi)1−(1−yi)1−g(θTxi)1)g(θTxi)(1−g(θTxi))δθjδθTxi=−m1i=1∑m(yi(1−g(θTxi))−(1−yi)g(θTxi))xij=−m1i=1∑m(yi−g(θTxi))xij=m1i=1∑m(hθ(xi)−yi)xij
然后就可以根据损失函数进行参数更新：
θ
j
←
θ
j
−
α
1
m
∑
i
=
1
m
(
h
θ
(
x
i
)
−
y
i
)
x
i
j
\begin{aligned}\theta_j \leftarrow \theta_j -\alpha\frac 1m\sum^m_{i=1}(h_{\theta}(x_i)-y_i)x_i^j \end{aligned}
θj←θj−αm1i=1∑m(hθ(xi)−yi)xij
(
α
\alpha
α为步长，后面那一部分为方向)，所以更新参数可以分为三步：（1）找方向；（2）走一步，步长不能过大；（3）按照方向和步长更新参数。
算法步骤
最终的算法步骤可以归纳为：
（1）初始化
θ
\theta
θ，其中
θ
\theta
θ是一个n+1维的向量（n为特征数）
（2）设置步长
α
\alpha
α
（3）计算当前梯度值，并更新参数，
θ
j
←
θ
j
−
α
1
m
∑
i
=
1
m
(
h
θ
(
x
i
)
−
y
i
)
x
i
j
\begin{aligned}\theta_j \leftarrow \theta_j -\alpha\frac 1m\sum^m_{i=1}(h_{\theta}(x_i)-y_i)x_i^j \end{aligned}
θj←θj−αm1i=1∑m(hθ(xi)−yi)xij
（4）重复（3），直到满足一定的条件退出。（比如相邻两次迭代的损失函数差小于
1
0
−
5
10^{-5}
10−5、设置最大迭代次数）。
线性回归 VS 逻辑回归
线性回归只能用于回归问题，逻辑回归虽然名字叫回归，但是更多用于分类问题；线性回归要求因变量是连续性数值变量，而逻辑回归要求因变量是离散的变量；线性回归要求自变量和因变量呈线性关系，而逻辑回归不要求自变量和因变量呈线性关系；线性回归可以直观的表达自变量和因变量之间的关系，逻辑回归则无法表达变量之间的关系；
决策树
分类决策树是一种基于特征对实例进行划分的树形结构。该树包括内部节点和叶子节点，叶子节点表示分类的结果，内部节点表示基于特征的划分，边表示属性值。
熵作为决策树中度量随机变量X的不确定性。
当随机变量只有两个值的时候，例如1，0时，即X的分布为
P
(
X
=
1
)
=
p
,
P
(
X
=
0
)
=
1
−
p
,
0
≤
p
≤
1
P(X=1)=p,\quad P(X=0)=1-p,\quad 0\leq p\leq 1
P(X=1)=p,P(X=0)=1−p,0≤p≤1
熵为：
H
(
p
)
=
−
p
log
2
p
−
(
1
−
p
)
log
2
(
1
−
p
)
H(p)=-p\log_2p-(1-p)\log_2(1-p)
H(p)=−plog2p−(1−p)log2(1−p)
更一般的条件下，
P
(
X
=
x
i
)
=
p
i
，
i
=
1
,
2
…
…
n
P(X=x_i)=p_i， i=1, 2……n
P(X=xi)=pi，i=1,2……n。 计算数据集D的熵的公式为：
H
(
D
)
=
−
∑
i
=
1
n
p
i
×
l
o
g
2
(
p
i
)
H(D)=-\sum_{i=1}^np_i\times log_2(p_i)
H(D)=−i=1∑npi×log2(pi) 条件熵
H
(
Y
∣
X
)
H(Y|X)
H(Y∣X)表示在已知随机变量
X
X
X的条件下随机变量
Y
Y
Y的不确定性。
H
(
Y
∣
X
)
=
∑
i
=
1
n
p
i
×
H
(
Y
∣
X
=
x
i
)
H(Y|X)=\sum_{i=1}^np_i \times H(Y|X=xi)
H(Y∣X)=i=1∑npi×H(Y∣X=xi) 当熵和条件熵中涉及的概率是由我们的已有训练数据集得到的时候，就称之为“经验”，即为经验熵和经验条件熵。
信息增益，特征
A
A
A对训练数据集
D
D
D的信息增益
g
(
D
,
A
)
g(D,A)
g(D,A)定义为集合
D
D
D的经验熵
H
(
D
)
H(D)
H(D)与在特征
A
A
A给定的条件下
D
D
D的经验条件熵
H
(
D
∣
A
)
H(D|A)
H(D∣A)的差，公式为：
g
(
D
,
A
)
=
H
(
D
)
−
H
(
D
∣
A
)
g(D,A)=H(D)-H(D|A)
g(D,A)=H(D)−H(D∣A) 信息增益比，
g
R
(
D
,
A
)
g_R(D,A)
gR(D,A)就是信息增益
g
(
D
,
A
)
g(D,A)
g(D,A)与基于特征
A
A
A的训练数据集
D
D
D的经验熵
H
A
(
D
)
H_A(D)
HA(D)之比：
g
R
(
D
,
A
)
=
g
(
D
,
A
)
÷
H
A
(
D
)
g_R(D,A)=g(D,A)\div H_A(D)
gR(D,A)=g(D,A)÷HA(D)
Gini指数，Gini 指数表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。
对于一个数据集T，将某一个特征作为分支标准，其第i个取值的Gini指数计算方式为:
g
i
n
i
(
T
i
)
=
∑
j
=
1
n
p
j
(
1
−
p
j
)
=
1
−
∑
j
=
1
n
p
j
2
gini(T_i)=\sum_{j=1}^np_j(1-p_j)=1-\sum_{j=1}^np_j^2
gini(Ti)=∑j=1npj(1−pj)=1−∑j=1npj2，其中
n
n
n表示数据的类别数，
p
j
p_j
pj表样本属于第j个类别的概率。
计算出某个样本特征所有取值的
G
i
n
i
Gini
Gini指数后就可以得到
G
i
n
i
_
S
p
l
i
t
_
I
n
f
o
Gini\_Split\_Info
Gini_Split_Info:
G
i
n
i
s
p
l
i
t
(
T
)
=
∣
N
1
∣
∣
N
∣
G
i
n
i
(
T
1
)
+
∣
N
2
∣
∣
N
∣
G
i
n
i
(
T
2
)
Gini_{split}(T)=\frac{|N_1|}{|N|}Gini(T_1) +\frac{|N_2|}{|N|}Gini(T_2)
Ginisplit(T)=∣N∣∣N1∣Gini(T1)+∣N∣∣N2∣Gini(T2)，其中
N
N
N表示样本总数，
N
i
N_i
Ni表示属于特征第
i
i
i个属性值的样本数。
ID3算法 在选择特征的时候，使用信息增益最大的特征作为决策点 基于信息增益，一般而言，某信息增益越大，则意味着使用该属性来进行划分所获得的“纯度提升”越大。因此，我们可用信息增益来进行决策树的划分属性选择。 C4.5算法 在选择特征的时候，使用信息增益比最大的特征作为决策点 基于信息增益率，信息增益率越大，该属性的纯度提升越大。 CART算法
使用基尼系数作为特征选择的依据。特征双化:如果某个属性可取的值超过两个，CART算法会考虑将目标合并成两个超类别（双化），因为CART树是二叉树，所以只能由两个分支具有最小
G
i
n
i
s
p
l
i
t
=
A
(
T
)
Gini_{split=A}(T)
Ginisplit=A(T)的属性被选为分裂节点的属性，A作为二分的属性值
决策树停止划分的情况：
划分后该数据集的属性值为空当前所有样本的类别相同数据集为空
决策树生成：
判断是否满足停止划分的条件寻找最佳属性作为当前节点保存从当前属性集中删除该属性遍历该属性的每一个属性值，递归调用函数
支持向量机SVM
支持向量
在二维空间上，两类点被一条直线完全分开叫做线性可分。从二维扩展到多维空间中时，将
D
0
D_0
D0和
D
1
D_1
D1完全正确地划分开的
w
T
x
+
b
=
0
\bold{w}^T\bold{x}+b=0
wTx+b=0就成了一个超平面。为了使这个超平面更具鲁棒性，我们会去找最佳超平面，以最大间隔把两类样本分开的超平面，也称之为最大间隔超平面。
样本空间中任意点
x
\bold{x}
x到超平面的距离可写为：
r
=
∣
w
T
x
+
b
∣
∥
w
∥
r=\frac{\vert\bold{w}^T\bold{x}+b\vert}{\Vert\bold{w}\Vert}
r=∥w∥∣wTx+b∣ 假设超平面能将训练样本正确分类，即对于
(
(
x
i
)
,
y
i
)
∈
D
((\bold{x}_i),y_i)\in D
((xi),yi)∈D，若
y
i
=
+
1
y_i=+1
yi=+1，则有
w
T
x
+
b
≥
0
\bold{w}^T\bold{x}+b\ge0
wTx+b≥0 ；若
y
i
=
−
1
y_i=-1
yi=−1，则有
w
T
x
+
b
≤
0
\bold{w}^T\bold{x}+b\le0
wTx+b≤0:
{
w
T
x
+
b
≥
+
1
,
y
i
=
+
1
w
T
x
+
b
≤
−
1
y
i
=
−
1
\begin{cases} \bold{w}^T\bold{x}+b\ge+1,&y_i=+1\\ \bold{w}^T\bold{x}+b\le -1 &y_i=-1 \end{cases}
{wTx+b≥+1,wTx+b≤−1yi=+1yi=−1 如下图，距离超平面最近的这几个训练样本使上式中的等号成立，被称为支持向量，两个异类支持向量到超平面的距离之和为
γ
=
2
∥
w
∥
\gamma=\frac2{\Vert\bold{w}\Vert}
γ=∥w∥2
欲找到具有“最大间隔”的划分超平面，也就是要找到满足约束条件的参数
w
w
w和
b
b
b，使得
γ
\gamma
γ最大，即
m
a
x
w
,
b
2
∥
w
∥
s
.
t
.
y
i
(
w
T
x
i
+
b
)
≥
1
,
i
=
1
,
2
,
⋯
,
m
\begin{aligned} &\underset{w,b}{max}\quad \frac2{\Vert w\Vert}\\ &s.t.\quad y_i(\bold{w}^Tx_i+b)\ge1,\quad i=1,2,\cdots,m \end{aligned}
w,bmax∥w∥2s.t.yi(wTxi+b)≥1,i=1,2,⋯,m 而最大化
∥
w
∥
−
1
\Vert w\Vert^{-1}
∥w∥−1<等价于最小化
∥
w
∥
2
\Vert w\Vert^2
∥w∥2，上式可重写为
m
i
n
w
,
b
1
2
∥
w
∥
2
s
.
t
.
y
i
(
w
T
x
i
+
b
)
≥
1
,
i
=
1
,
2
,
⋯
,
m
\begin{aligned} &\underset{w,b}{min}\quad \frac12{\Vert w\Vert^2}\\ &s.t.\quad y_i(\bold{w}^Tx_i+b)\ge1,\quad i=1,2,\cdots,m \end{aligned}
w,bmin21∥w∥2s.t.yi(wTxi+b)≥1,i=1,2,⋯,m
对偶问题
对上式使用拉格朗日乘子法可得到其“对偶问题”。每条约束添加拉格朗日乘子
λ
i
≥
0
\lambda_i\ge0
λi≥0，该问题的拉格朗日函数可写为：
L
(
w
,
b
,
λ
)
=
1
2
∥
w
∥
2
+
∑
i
=
1
m
λ
i
(
1
−
y
i
(
w
T
x
i
+
b
)
)
L(w,b,\bold{\lambda})=\frac12\Vert \bold{w}\Vert^2+\sum^m_{i=1}\lambda_i(1-y_i(\bold{w}^Tx_i+b))
L(w,b,λ)=21∥w∥2+i=1∑mλi(1−yi(wTxi+b)) 令
L
(
w
,
b
,
λ
)
L(w,b,\bold{\lambda})
L(w,b,λ)对
w
w
w和
b
b
b的偏导为0可得
w
=
∑
i
=
1
m
λ
i
y
i
x
i
0
=
∑
i
=
1
m
λ
i
y
i
\begin{aligned} w&=\sum^{m}_{i=1}\lambda_iy_ix_i\\ 0&=\sum^{m}_{i=1}\lambda_iy_i \end{aligned}
w0=i=1∑mλiyixi=i=1∑mλiyi 带入上式，对偶问题转化为
m
a
x
λ
∑
i
=
1
m
λ
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
λ
i
λ
j
y
i
y
j
x
i
T
x
j
s
.
t
.
∑
i
=
1
m
λ
i
y
i
=
0
,
λ
i
≥
0
,
i
=
1
,
2
,
…
,
m
\begin{aligned} \underset{\lambda}{max}\quad &\sum^m_{i=1}\lambda_i-\frac12\sum^m_{i=1}\sum^m_{j=1}\lambda_i\lambda_jy_iy_jx_i^Tx_j\\ &s.t.\quad\sum^m_{i=1}\lambda_iy_i=0,\\ &\qquad \lambda_i\ge0,\quad i=1,2,\ldots,m \end{aligned}
λmaxi=1∑mλi−21i=1∑mj=1∑mλiλjyiyjxiTxjs.t.i=1∑mλiyi=0,λi≥0,i=1,2,…,m 上述过程需满足KTT(Karush-Kuhn-Tucker)条件，即
{
λ
i
≥
0
y
i
f
(
x
i
)
−
1
≥
0
λ
i
(
y
i
f
(
x
i
)
−
1
)
=
0
\begin{cases} \lambda_i\ge 0\\ y_if(x_i)-1\ge0\\ \lambda_i(y_if(x_i)-1)=0 \end{cases}
⎩⎪⎨⎪⎧λi≥0yif(xi)−1≥0λi(yif(xi)−1)=0 直观来讲就是，支持向量
y
i
f
(
x
i
)
−
1
=
0
y_if(x_i)-1=0
yif(xi)−1=0，所以
λ
i
>
0
\lambda_i>0
λi>0即可，而其他向量
λ
i
=
0
\lambda_i=0
λi=0
强对偶性
对偶问题其实就是将：
min
w
max
λ
L
(
w
,
λ
)
s
.
t
.
λ
i
≥
0
\underset{w}{\min}\underset{\lambda}{\max}L(w,\lambda)\qquad s.t.\quad\lambda_i\ge0
wminλmaxL(w,λ)s.t.λi≥0 变成了
max
λ
min
w
L
(
w
,
λ
)
s
.
t
.
λ
i
≥
0
\underset{\lambda}{\max}\underset{w}{\min}L(w,\lambda)\qquad s.t.\quad\lambda_i\ge0
λmaxwminL(w,λ)s.t.λi≥0 假设有个函数
f
f
f 我们有
min
max
f
≥
max
min
f
\min\max f\ge\max\min f
minmaxf≥maxminf
也就是说，最大的里面挑出来的最小的也要比最小的里面挑出来的最大的要大。这关系实际上就是弱对偶关系，而强对偶关系是当等号成立时，即：
min
max
f
=
max
min
f
\min\max f= \max\min f
minmaxf=maxminf
SVM优化
上述对偶问题是一个二次规划问题，问题规模正比于训练样本数，我们常用 SMO(Sequential Minimal Optimization) 算法求解。
SMO(Sequential Minimal Optimization)，序列最小优化算法，其核心思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这个优化参数的极值。
但我们的优化目标有约束条件：
∑
i
=
1
m
λ
i
y
i
=
0
\sum^m_{i=1}\lambda_iy_i=0
∑i=1mλiyi=0，所以一次选择两个参数。选择两个需要更新的参数
λ
i
\lambda_i
λi和
λ
j
\lambda_j
λj，固定其他参数，于是有一下约束：
λ
i
y
i
+
λ
j
y
j
=
c
λ
i
≥
0
,
λ
j
≥
0
c
=
−
∑
k
≠
i
,
j
λ
k
y
k
\lambda_iy_i+\lambda_jy_j=c\quad\lambda_i\ge0,\lambda_j\ge0\\ c=-\sum_{k\neq i,j}\lambda_ky_k
λiyi+λjyj=cλi≥0,λj≥0c=−k=i,j∑λkyk 由此可得
λ
j
=
c
−
λ
i
y
i
y
j
\lambda_j=\frac{c-\lambda_iy_i}{y_j}
λj=yjc−λiyi 用
λ
i
\lambda_i
λi的表达式代替
λ
j
\lambda_j
λj，问题转化为仅有一个约束条件的最优化问题。然后可以在
λ
i
\lambda_i
λi上对优化目标求偏导，令导数为0，从而求出
λ
i
n
e
w
\lambda_{inew}
λinew，多次迭代直至收敛。
根据公式
w
=
∑
i
=
1
m
λ
i
y
i
x
i
w=\sum^{m}_{i=1}\lambda_iy_ix_i
w=i=1∑mλiyixi 可求得
w
w
w。
我们知道所有
λ
i
≥
0
\lambda_i\ge0
λi≥0对应的点都是支持向量，随便找一个支持向量带入
y
s
(
w
x
s
+
b
)
=
1
y_s(wx_s+b)=1
ys(wxs+b)=1，两边同乘以
y
s
y_s
ys，因为
y
s
2
=
1
y_s^2=1
ys2=1，所以
b
=
y
s
−
w
x
s
b=y_s-wx_s
b=ys−wxs
为了更具鲁棒性，我们可以求得支持向量的均值：
b
=
1
∣
S
∣
∑
s
∈
S
(
y
s
−
w
x
s
)
b=\frac1{\vert S\vert}\sum_{s\in S}(y_s-wx_s)
b=∣S∣1s∈S∑(ys−wxs) $w $和
b
b
b都求出来了，我们就能构造出最大分割超平面:
w
T
x
+
b
=
0
w^Tx+b=0
wTx+b=0 分类决策函数
f
(
x
)
=
s
i
g
n
(
w
T
x
+
b
)
f(x)=sign(w^Tx+b)
f(x)=sign(wTx+b)，其中
s
i
g
n
(
∗
)
sign(*)
sign(∗)为阶跃函数。
软间隔
在实际应用中，完全线性可分的样本是很少的，如果遇到了不能够完全线性可分的样本，需要使用软间隔，相比于硬间隔的苛刻条件，我们允许个别样本点出现在间隔带里面，为了度量这个间隔软到何种程度，我们为每个样本引入一个松弛变量
ξ
i
\xi_i
ξi，令
ξ
i
≥
0
\xi_i\ge 0
ξi≥0且
1
−
y
i
(
w
T
x
i
+
b
)
−
ξ
i
≤
0
1-y_i(w^Tx_i+b)-\xi_i\le0
1−yi(wTxi+b)−ξi≤0
引入软间隔后我们的优化目标变成了：
m
i
n
w
,
b
1
2
∥
w
∥
2
+
C
∑
i
=
1
m
ξ
i
s
.
t
.
g
i
(
w
,
b
)
=
1
−
y
i
(
w
T
x
i
+
b
)
−
ξ
i
≤
0
,
ξ
i
≥
0
,
i
=
1
,
2
,
⋯
,
m
\begin{aligned} &\underset{w,b}{min}\quad \frac12{\Vert w\Vert^2}+C\sum^m_{i=1}\xi_i\\ &s.t.\quad g_i(w,b)=1-y_i(\bold{w}^Tx_i+b)-\xi_i\le0,\quad\xi_i\ge0,\quad i=1,2,\cdots,m \end{aligned}
w,bmin21∥w∥2+Ci=1∑mξis.t.gi(w,b)=1−yi(wTxi+b)−ξi≤0,ξi≥0,i=1,2,⋯,m 其中 C 是一个大于 0 的常数，可以理解为错误样本的惩罚程度，若 C 为无穷大，
ξ
i
\xi_i
ξi必然无穷小，如此一来线性 SVM 就又变成了线性可分 SVM；当 C 为有限值的时候，才会允许部分样本不遵循约束条件。
然后通过拉格朗日乘子法构造拉格朗日函数
L
(
w
,
b
,
λ
,
ξ
,
μ
)
=
1
2
∥
w
∥
2
+
C
∑
i
=
1
m
ξ
i
+
∑
i
=
1
m
λ
i
(
1
−
ξ
i
−
y
i
(
w
T
x
i
+
b
)
)
−
∑
i
=
1
n
μ
i
ξ
i
s
.
t
.
λ
i
≥
0
,
μ
i
≥
0
\begin{aligned} L(w,b,\lambda,\xi,\mu)=&\frac12\Vert \bold{w}\Vert^2+C\sum^m_{i=1}\xi_i\\&+\sum^m_{i=1}\lambda_i(1-\xi_i-y_i(\bold{w}^Tx_i+b))-\sum^n_{i=1}\mu_i\xi_i\\ &\qquad s.t.\lambda_i\ge0,\mu_i\ge0 \end{aligned}
L(w,b,λ,ξ,μ)=21∥w∥2+Ci=1∑mξi+i=1∑mλi(1−ξi−yi(wTxi+b))−i=1∑nμiξis.t.λi≥0,μi≥0 其中
λ
i
，
μ
i
\lambda_i，\mu_i
λi，μi是拉格朗日乘子，
w
,
b
,
ξ
i
w,b,\xi_i
w,b,ξi是主问题参数。根据强对偶性，将问题转换为：
m
a
x
λ
,
u
m
i
n
w
,
b
,
ξ
L
(
w
,
b
,
λ
,
ξ
,
μ
)
s
.
t
.
λ
i
≥
0
,
μ
i
≥
0
\underset{\lambda,\,u}{max}\quad\underset{w,b,\xi}{min}L(w,b,\lambda,\xi,\mu)\qquad s.t.\lambda_i\ge0,\mu_i\ge0
λ,umaxw,b,ξminL(w,b,λ,ξ,μ)s.t.λi≥0,μi≥0 分别对主问题参数
w
,
b
,
ξ
i
w,b,\xi_i
w,b,ξi求偏导，令偏导数为0，得出如下关系：
w
=
∑
i
=
1
m
λ
i
y
i
x
i
0
=
∑
i
=
1
m
λ
i
y
i
C
=
λ
i
+
μ
i
\begin{aligned} w=&\sum^m_{i=1}\lambda_iy_ix_i\\ 0=&\sum^m_{i=1}\lambda_iy_i\\ C=&\lambda_i+\mu_i \end{aligned}
w=0=C=i=1∑mλiyixii=1∑mλiyiλi+μi 回代入拉格朗日函数中，得到
m
i
n
w
,
b
,
ξ
L
(
w
,
b
,
λ
,
ξ
,
μ
)
=
∑
i
=
1
m
λ
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
λ
i
λ
j
y
i
y
j
x
i
T
x
j
\underset{w,b,\xi}{min}L(w,b,\lambda,\xi,\mu)=\sum^m_{i=1}\lambda_i-\frac12\sum^m_{i=1}\sum^m_{j=1}\lambda_i\lambda_jy_iy_jx_i^Tx_j
w,b,ξminL(w,b,λ,ξ,μ)=i=1∑mλi−21i=1∑mj=1∑mλiλjyiyjxiTxj 最小化结果只有
λ
\lambda
λ没有
μ
\mu
μ，只需要最大化
λ
\lambda
λ。
m
a
x
λ
∑
i
=
1
m
λ
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
λ
i
λ
j
y
i
y
j
x
i
T
x
j
s
.
t
.
∑
i
=
1
m
λ
i
y
i
=
0
,
λ
i
≥
0
,
C
−
λ
i
−
μ
i
=
0
i
=
1
,
2
,
…
,
m
\begin{aligned} \underset{\lambda}{max}\quad &\sum^m_{i=1}\lambda_i-\frac12\sum^m_{i=1}\sum^m_{j=1}\lambda_i\lambda_jy_iy_jx_i^Tx_j\\ &s.t.\quad\sum^m_{i=1}\lambda_iy_i=0,\\ &\qquad \lambda_i\ge0,C-\lambda_i-\mu_i=0\quad i=1,2,\ldots,m \end{aligned}
λmaxi=1∑mλi−21i=1∑mj=1∑mλiλjyiyjxiTxjs.t.i=1∑mλiyi=0,λi≥0,C−λi−μi=0i=1,2,…,m 这个和硬间隔的一样，只是多了个约束条件。然后我们利用 SMO 算法求解得到拉格朗日乘子。
核函数
对于在有限维度向量空间中线性不可分的样本，我们将其映射到更高维度的向量空间里，再通过间隔最大化的方式，学习得到支持向量机，就是非线性 SVM。
我们用
x
x
x 表示原来的样本点，用
ϕ
(
x
)
\phi(x)
ϕ(x)表示
x
x
x映射到特征新的特征空间后到新向量。那么分割超平面可以表示为：
f
(
x
)
=
w
ϕ
(
x
)
+
b
f(x)=w\phi(x)+b
f(x)=wϕ(x)+b
对于非线性 SVM 的对偶问题就变成了：
m
a
x
λ
∑
i
=
1
m
λ
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
λ
i
λ
j
y
i
y
j
ϕ
(
x
i
)
T
ϕ
(
x
j
)
s
.
t
.
∑
i
=
1
m
λ
i
y
i
=
0
,
λ
i
≥
0
,
C
−
λ
i
−
μ
i
=
0
i
=
1
,
2
,
…
,
m
\begin{aligned} \underset{\lambda}{max}\quad &\sum^m_{i=1}\lambda_i-\frac12\sum^m_{i=1}\sum^m_{j=1}\lambda_i\lambda_jy_iy_j\phi(x_i)^T\phi(x_j)\\ &s.t.\quad\sum^m_{i=1}\lambda_iy_i=0,\\ &\qquad \lambda_i\ge0,C-\lambda_i-\mu_i=0\quad i=1,2,\ldots,m \end{aligned}
λmaxi=1∑mλi−21i=1∑mj=1∑mλiλjyiyjϕ(xi)Tϕ(xj)s.t.i=1∑mλiyi=0,λi≥0,C−λi−μi=0i=1,2,…,m 可以看到与线性 SVM 唯一的不同就是：之前的
x
i
T
x
j
x_i^Tx_j
xiTxj变成了
ϕ
(
x
i
)
T
ϕ
(
x
j
)
\phi(x_i)^T\phi(x_j)
ϕ(xi)Tϕ(xj)
常见核函数
优缺点
优点
有严格的数学理论支持，可解释性强，不依靠统计方法，从而简化了通常的分类和回归问题；能找出对任务至关重要的关键样本（即：支持向量）；采用核技巧之后，可以处理非线性分类/回归任务；最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。 缺点
训练时间长。当采用 SMO 算法时，由于每次都需要挑选一对参数，因此时间复杂度为
O
(
N
2
)
O(N^2)
O(N2)，其中N为训练样本的数量；当采用核技巧时，如果需要存储核矩阵，则空间复杂度为
O
(
N
2
)
O(N^2)
O(N2)；模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。因此支持向量机目前只适合小批量样本的任务，无法适应百万甚至上亿样本的任务。
简单的神经网络模型
卷积神经网络(CNN)
卷积神经网络（CNN）主要是用于图像识别领域，它指的是一类网络，而不是某一种，其包含很多不同种结构的网络。不同的网络结构通常表现会不一样。所有CNN最终都是把一张图片转化为特征向量，特征向量就相当于这张图片的DNA。
典型的 CNN 由3个部分构成：
卷积层池化层全连接层
一个卷积块为连续M 个卷积层和b个汇聚层（M通常设置为2 ∼ 5， b为0或1） 一个卷积网络中可以堆叠N 个连续的卷积块， 然后再接着K 个全连接层（N 的取值区间比较大，比如1 ∼ 100或者更大； K一般为0 ∼ 2）
卷积——提取特征
在图像处理中，图像是以二维矩阵的形式输入到神经网络中，因此我们需要二维卷积。
y
i
,
j
=
∑
u
=
1
U
∑
v
=
1
V
w
u
,
v
x
i
−
u
+
1
,
j
−
v
+
1
y_{i,j}=\sum^U_{u=1}\sum^V_{v=1}w_{u,v}x_{i-u+1,j-v+1}
yi,j=u=1∑Uv=1∑Vwu,vxi−u+1,j−v+1 计算卷积需要进行卷积核翻转 ,除非特别声明，卷积一般指“互相关” 。机器学习中不用翻转，数学中需要翻转。
这个过程我们可以理解为我们使用一个过滤器（卷积核）来过滤图像的各个小区域，从而得到这些小区域的特征值。选择了过滤器的尺寸以后，我们还需要选择步幅（stride）和填充（padding）
在具体应用中，往往有多个卷积核，可以认为，每个卷积核代表了一种图像模式，如果某个图像块与此卷积核卷积出的值大，则认为此图像块十分接近于此卷积核。
在卷积层中每个神经元连接数据窗的权重是固定的，每个神经元只关注一个特性。
池化层（下采样）——数据降维，避免过拟合 由于不同尺寸的卷积核得到的
f
e
a
t
u
r
e
_
m
a
p
feature\_map
feature_map的大小也不一样，因此需要对每个
f
e
a
t
u
r
e
_
m
a
p
feature\_map
feature_map使用池化函数，最常用的是Max-Pooling。提取出每个
f
e
a
t
u
r
e
_
m
a
p
feature\_map
feature_map的最大值，然后连接所有的最大值。也有Average_Polling（取每个维度的均值）和K-Max_Pooling（取每个维度的前K个最大值，并在连接的时候保留原始的先后顺序）。
之所以这么做的原因，是因为即使做完了卷积，图像仍然很大（因为卷积核比较小），所以为了降低数据维度，就进行下采样。
Max Pooling保留了每一小块内的最大值，也就是相当于保留了这一块最佳的匹配结果（因为值越接近1表示匹配越好）。也就是说，它不会具体关注窗口内到底是哪一个地方匹配了，而只关注是不是有某个地方匹配上了。
采用Max Pooling 的好处是能够减少模型参数的数量同时也能提取出强特征，有利于减少模型的过拟合；可以把变长的输入整理成固定长度的结果。
全连接层——输出结果
经过卷积层和池化层降维过的数据，全连接层才能”跑得动”，不然数据量太大，计算成本高，效率低下。这一层的目的主要是为了分类，可以使用dropout随机使一部分神经元失活，防止发生过拟合。使用SoftMax函数输出概率分布。
典型的 CNN 并非只是上面提到的3层结构，而是多层结构。卷积网络是由卷积层、池化层、全连接层交叉堆叠而成 。
激活函数
常用的激活函数有sigmoid、tanh、relu等等，前两者sigmoid/tanh比较常见于全连接层，后者ReLU常见于卷积层。
在卷积神经网络中，激活函数一般使用ReLU(The Rectified Linear Unit，修正线性单元)，它的特点是收敛快，求梯度简单。计算公式也很简单，max(0,T)，即对于输入的负值，输出全为0，对于正值，则原样输出。例如输入图像中包含了特定的模式，此时输入为正，当那个区域没有展现出这些模式时，输入为0或者为负，ReLU层将所有负值都置为0，这意味着只有对那个特定区域拥有这些模式的图像才会被激活。
优缺点
优点 共享卷积核，对高维数据处理无压力 无需手动选取特征，训练好权重，即得特征分类效果好 缺点 需要调参，需要大样本量，训练最好要 GPU 可解释性差
循环神经网络(RNN)
某些任务需要能够更好的处理序列的信息，即前面的输入和后面的输入是有关系的。
式1是输出层的计算公式，V是输出层的权重矩阵，g是激活函数。
式2是隐藏层的计算公式，它是循环层。
U
U
U是输入
x
x
x的权重矩阵，
W
W
W是上一次隐藏层值
S
t
−
1
S_{t−1}
St−1作为这一次的输入的权重矩阵，
f
f
f是激活函数。
如果我们把上面的图展开，循环神经网络也可以画成下面这个样子：
x
x
x是输入向量，
o
o
o是输出向量，
s
s
s表示隐藏层的值；
U
U
U是输入层到隐藏层的权重矩阵，
V
V
V是隐藏层到输出层的权重矩阵。循环神经网络的隐藏层的值
s
s
s不仅仅取决于当前这次的输入
x
x
x，还取决于上一次隐藏层的值
s
s
s。权重矩阵
W
W
W就是隐藏层上一次的值作为这一次的输入的权重。
这个网络在
t
t
t时刻接收到输入
x
t
x_t
xt之后，隐藏层的值是
s
t
s_t
st，输出值是
o
t
o_t
ot。关键一点是，
s
t
s_t
st的值不仅仅取决于
x
t
x_t
xt，还取决于
s
t
−
1
s_{t-1}
st−1。
梯度爆炸和消失问题
实践中前面介绍的几种RNNs并不能很好的处理较长的序列，RNN在训练中很容易发生梯度爆炸和梯度消失，这导致梯度不能在较长序列中一直传递下去，从而使RNN无法捕捉到长距离的影响。
通常来说，梯度爆炸更容易处理一些。因为梯度爆炸的时候，我们的程序会收到NaN错误。我们也可以设置一个梯度阈值，当梯度超过这个阈值的时候可以直接截取。
梯度消失更难检测，而且也更难处理一些。总的来说，我们有三种方法应对梯度消失问题：
合理的初始化权重值。初始化权重，使每个神经元尽可能不要取极大或极小值，以躲开梯度消失的区域。使用relu代替sigmoid和tanh作为激活函数。使用其他结构的RNNs，比如长短时记忆网络（LTSM）和Gated Recurrent Unit（GRU），这是最流行的做法。
生成对抗网络(GAN)
生成对抗网络（GAN）由2个重要的部分构成：
生成器(Generator)：通过机器生成数据（大部分情况下是图像），目的是“骗过”判别器判别器(Discriminator)：判断这张图像是真实的还是机器生成的，目的是找出生成器做的“假数据”
原始 GAN 理论中，并不要求 G 和 D 都是神经网络，只需要是能拟合相应生成和判别的函数即可。但实用中一般均使用深度神经网络作为 G 和 D 。
过程
第一阶段：固定「判别器D」，训练「生成器G」 我们使用一个还 OK 判别器，让一个生成器G不断生成“假数据”，然后给这个判别器D去判断。一开始，生成器G还很弱，所以很容易被揪出来。 但是随着不断的训练，生成器G技能不断提升，最终骗过了判别器D。到了这个时候，判别器D基本属于瞎猜的状态，判断是否为假数据的概率为50%。 第二阶段：固定「生成器G」，训练「判别器D当通过了第一阶段，继续训练生成器G就没有意义了。这个时候我们固定生成器G，然后开始训练判别器D。 判别器D通过不断训练，提高了自己的鉴别能力，最终他可以准确的判断出所有的假图片。到了这个时候，生成器G已经无法骗过判别器D 循环阶段一和阶段二 通过不断的循环，生成器G和判别器D的能力都越来越强。
训练
在噪声数据分布中随机采样，输入生成模型，得到一组假数据，记为D(z)在真实数据分布中随机采样，作为真实数据，记做x； 将前两步中某一步产生的数据作为判别网络的输入（因此判别模型的输入为两类数据，真/假），判别网络的输出值为该输入属于真实数据的概率，real为1，fake为0.然后根据得到的概率值计算损失函数；根据判别模型和生成模型的损失函数，可以利用反向传播算法，更新模型的参数。（先更新判别模型的参数，然后通过再采样得到的噪声数据更新生成器的参数）
优缺点
优点
能更好建模数据分布（图像更锐利、清晰）理论上，GANs 能训练任何一种生成器网络。其他的框架需要生成器网络有一些特定的函数形式，比如输出层是高斯的。无需利用马尔科夫链反复采样，无需在学习过程中进行推断，没有复杂的变分下界，避开近似计算棘手的概率的难题。 缺点
难训练，不稳定。生成器和判别器之间需要很好的同步，但是在实际训练中很容易D收敛，G发散。D/G 的训练需要精心的设计。模式缺失（Mode Collapse）问题。GANs的学习过程可能出现模式缺失，生成器开始退化，总是生成同样的样本点，无法继续学习。可解释性差,生成模型的分布 Pg(G)没有显式的表达
【参考博文】
感谢以下博文，如有需要，请移步原文档学习。
Cmd Markdown 公式指导手册
过拟合与欠拟合
信息熵、联合熵、条件熵、互信息
机器学习中的目标函数总结
正则化总结
正则化
如何通俗理解线性回归？
梯度下降算法（Gradient Descent)的原理和实现步骤
机器学习算法：梯度下降法——原理篇
AI—训练集(train set) 验证集(validation set) 测试集(test set) - 曾先森在努力 - 博客园 (cnblogs.com)
决策树分类算法三种方式_技多不压身的博客-CSDN博客_决策树分类
【机器学习】支持向量机 SVM（非常详细）
《机器学习》 周志华
一文搞懂RNN（循环神经网络）基础篇
循环神经网络(RNN)及衍生LSTM、GRU详解
生成对抗网络 – Generative Adversarial Networks | GAN
图解 生成对抗网络GAN 原理 超详解
数据集划分方法(留出法、交叉验证)_若只如初見~~的博客-CSDN博客_留出法
相关文章
您阅读本篇文章共花了：
发表评论