机器学习总结
0 前言
机器学习是人工智能的核心，从历史数据中学习信息，总结规律。
学会概率论与数理统计，矩阵分析以及凸优化，机器学习就掌握了大部分。
其中贝叶斯，梯度下降，svd分解在机器学习中较为常用。
1理论部分
1.1 优化问题
机器学习可以抽象为优化问题
未知函数
f
:
x
→
y
f :x\to y
f:x→y
数据集
D
(
x
i
,
y
i
)
\mathcal{D} (x_i,y_i)
D(xi,yi)
假设函数类
H
,
h
∈
H
\mathcal{H},h\in \mathcal{H}
H,h∈H看成约束
损失函数
l
o
s
s
(
h
(
x
i
)
,
y
i
)
loss(h(x_i),y_i)
loss(h(xi),yi)
m
i
n
h
E
D
(
l
o
s
s
(
h
(
x
i
)
,
y
i
)
s
.
t
h
∈
H
min_h \quad \mathbb{E}^D(loss(h(x_i),y_i)\\ s.t \quad h\in \mathcal{H}
minhED(loss(h(xi),yi)s.th∈H
上述问题称为期望风险极小化，但是实际情况，我们不知道所有数据集，只有样本，上述问题转为
m
i
n
h
1
n
∑
i
n
(
l
o
s
s
(
h
(
x
i
)
,
y
i
)
s
.
t
h
∈
H
.
min_h \quad \frac{1}{n}\sum_i^n(loss(h(x_i),y_i)\\ s.t \quad h\in \mathcal{H}.
minhn1i∑n(loss(h(xi),yi)s.th∈H.
称为经验风险极小化。
从概率角度解释
存在一个未知分布
(
x
,
y
)
∼
P
(
X
,
Y
)
(x,y)\sim P(X,Y)
(x,y)∼P(X,Y)，
极大似然估计：极大化后验概率
p
(
y
∣
x
)
p(y|x)
p(y∣x)
1.2 泛化
用样本得到的模型再样本之外的数据集性能表现称为泛化。
E
i
n
\mathbb{E}_{in}
Ein：样本期望误差
E
o
u
t
\mathbb{E}_{out}
Eout：样本之外数据点的期望误差
大数定理，Hoeffding’s inequality
P
[
(
∣
E
i
n
(
h
)
−
E
o
u
t
(
h
)
∣
)
>
ϵ
]
≤
2
e
−
2
ϵ
2
m
P[(|\mathbb{E}_{in}(h)-\mathbb{E}_{out}(h)|)>\epsilon]\leq 2e^{-2\epsilon^2m}
P[(∣Ein(h)−Eout(h)∣)>ϵ]≤2e−2ϵ2m
m为样本个数。
g
g
g为最优
h
h
h
对于有限的
H
\mathcal{H}
H
P
[
(
∣
E
i
n
(
g
)
−
E
o
u
t
(
g
)
∣
)
>
ϵ
]
≤
P
[
(
∣
E
i
n
(
h
1
)
−
E
o
u
t
(
h
1
)
∣
)
>
ϵ
]
+
P
[
(
∣
E
i
n
(
h
2
)
−
E
o
u
t
(
h
2
)
∣
)
>
ϵ
]
+
.
.
.
≤
2
∣
H
∣
e
−
2
ϵ
2
m
P[(|\mathbb{E}_{in}(g)-\mathbb{E}_{out}(g)|)>\epsilon]\\\leq P[(|\mathbb{E}_{in}(h_1)-\mathbb{E}_{out}(h_1)|)>\epsilon]+P[(|\mathbb{E}_{in}(h_2)-\mathbb{E}_{out}(h_2)|)>\epsilon]+...\\ \leq 2|\mathcal{H}|e^{-2\epsilon^2m}
P[(∣Ein(g)−Eout(g)∣)>ϵ]≤P[(∣Ein(h1)−Eout(h1)∣)>ϵ]+P[(∣Ein(h2)−Eout(h2)∣)>ϵ]+...≤2∣H∣e−2ϵ2m
对于无限的
H
\mathcal{H}
H
P
[
(
∣
E
i
n
(
g
)
−
E
o
u
t
(
g
)
∣
)
>
ϵ
]
≤
4
m
H
(
2
N
)
e
−
1
8
ϵ
2
N
P[(|\mathbb{E}_{in}(g)-\mathbb{E}_{out}(g)|)>\epsilon]\leq 4 m_{\mathcal{H}}(2N)e^{-\frac{1}{8}\epsilon^2N}
P[(∣Ein(g)−Eout(g)∣)>ϵ]≤4mH(2N)e−81ϵ2N
m
H
(
N
)
m_{\mathcal{H}}(N)
mH(N)为增长函数，表示对于
N
N
N个数据点可以将数据分为几类。
k
k
k为断点，当
N
<
k
N<k
N<k时可以被完全粉碎，即分为
2
N
2^N
2N类。
d
v
c
=
k
−
1
d_{vc}=k-1
dvc=k−1
二分类问题最多显然为
2
N
2^N
2N类，不同的假设函数类分类能力不同，如下例子。
m
H
(
N
)
≤
∑
i
=
0
k
−
1
C
N
i
m_{\mathcal{H}}(N)\leq \sum_{i=0}^{k-1}C_N^i
mH(N)≤∑i=0k−1CNi
给定误差限
δ
\delta
δ
E
o
u
t
≤
E
i
n
+
8
N
l
n
(
4
(
(
2
N
)
d
v
c
+
1
)
δ
)
\mathbb{E}_{out}\leq \mathbb{E}_{in}+\sqrt{\frac{8}{N}ln(\frac{4((2N)^{d_{vc}}+1)}{\delta})}
Eout≤Ein+N8ln(δ4((2N)dvc+1))
降低置信度，增大训练集，慎选假设函数集来提升泛化。
1.3 过拟合
正则化
1.4 优化算法
一阶算法，二阶算法，牛顿，拟牛顿
2 应用
2.1 SVM
到直线距离最大
2.2 decision tree
未完待续