第1章 统计学习及监督学习概论

1. 统计学习基本分类

监督学习 学习输入到输出的映射的统计规律

1-输入空间、特征空间和输出空间：特征连续预测是回归，离散预测是分类
2-联合概率分布：假设输入与输出服从联合分布（关于数据的基本假设）
3-假设空间：模型属于由输入空间到输出空间的映射的集合，意味着学习范围的确定。模型可以是概率模型（$P(Y|X)$）或非概率模型$Y=f(X)$

无监督学习 学习数据中的统计规律或潜在结构

旨在从假设空间中选出在给定评价标准下的最优模型
模型可以实现对数据的聚类、降维或概率估计

强化学习 学习最优的序贯决策

强化学习的马尔可夫决策过程是状态、奖励、动作序列上的随机过程，$<S,A,P,r,\gamma>$
State、Action、transition Probability ($P(s^\prime|s,a)=P(s_{t+1}=s^\prime|s_t=s,a_t=a)$)、reward function ($r(s,a)=E(r_{t+1}|s_t=s,a_t=a)$)、discount factor ($\gamma\in[0,1]$)
策略$\pi$定义为给定状态下动作的函数$a=f(s)$或$P(a|s)$
状态价值函数定义为策略$\pi$从某一个状态$s$开始的长期累积奖励的数学期望
动作价值函数定义为策略$\pi$从某一个状态$s$和动作$a$开始的长期累积奖励的数学期望

强化学习方法有基于策略的(policy-based)、基于价值的(value-based)无模型(model-free)方法和有模型(model-based)方法。
model-based直接学习马尔科夫决策过程
policy-based model-free求解最优策略$\pi^*$
value-based model-free求解最优价值函数$q^*(s,a)$

半监督学习 利用未标注数据中的信息辅助标注数据进行监督学习

主动学习 找出对学习最有帮助的实例让teacher标注

2. 按模型分类

概率模型与非概率模型

基本概率公式
加法规则：$P(x)=\sum_yP(x,y)$
乘法规则：$P(x,y)=P(x)P(y|x)$

线性模型与非线性模型

参数化模型与非参数化模型

参数化模型假设模型参数的维度固定，模型可以由有限维参数完全刻画；非参数化模型假设模型参数的维度不固定或者说无穷大，随着训练数据量的增加而不断增大。

3. 按算法分类

在线学习与批量学习

在线学习每次接受一个样本，进行预测，之后学习模型，不断重复；批量学习一次接受所有数据，学习模型，之后进行预测。
在线学习可以是监督学习，也可以是无监督学习，强化学习本身就拥有在线学习的特点。

4. 按技巧分类

贝叶斯学习

在概率模型学习和推理中，利用贝叶斯定理计算在给定数据条件下模型的条件概率，即后验概率，并应用这个原理进行模型的估计，以及对数据的预测。

贝叶斯估计和极大似然估计代表着统计学中贝叶斯学派和频率学派对统计的不同认识。
假设先验分布是均匀分布，取后验概率最大，就能从贝叶斯估计得到极大似然估计。
$$
D\rightarrow{极大似然估计}\rightarrow\hat{\theta=\arg\max_{\theta}P(D|\theta)}\ [图像是只在\hat{\theta}有值]\
D\rightarrow{贝叶斯估计}\rightarrow\hat{P}(\theta|D)=\frac{P(\theta)P(D|\theta)}{P(D)}\ [图像是正态分布曲线]
$$
核方法

核方法是使用核函数表示和学习费线性模型的一种机器学习方法。有一些线性模型的学习方法基于相似度计算<向量內积>，核方法可以把他们扩展到非线性模型的学习中，使其应用更广泛。
线性转非线性直接做是显式的定义输入空间到特征空间的映射，在特征空间做內积；核方法不显式的定义这个映射，而是定义核函数<映射之后在特征空间的內积>。
$$
\frac{输入空间}{x_1,x_2}\stackrel{映射函数\psi}{\longrightarrow}\frac{特征空间}{\psi(x_1),\psi(x_2)}\
核函数定义在输入空间\frac{输入空间}{K(x_1,x_2)} \ K(x_1,x_2)=<\psi(x_1),\psi(x_2)>
$$

5. 统计学习方法三要素

模型

在监督学习过程中，模型就是所要学习的条件概率分布或决策函数，模型的假设空间（hypothesis space）包含所有可能的条件概率分布或决策函数。

策略

损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。
损失函数是$f(X)$和$Y$的非负实值函数，记作$L(Y,f(X))$；损失函数的期望是模型$f(X)$关于联合分布$P(x,Y)$的平均意义下的损失，称为风险函数或期望损失$R_{exp}(f)$。
$$
R_{exp}(f)=E_P[L(Y,f(X))]=\int_{\mathcal{X}\times\mathcal{Y}}{L(y,f(x))P(x,y)dxdy}
$$
由于联合分布未知，监督学习就是为了学习联合分布，所以监督学习是一个ill-formed problem。根据大数定律，当样本容量$N$趋于无穷时，经验风险$R_{emp}$趋近于期望风险$R_{exp}$
$$
R_{emp}(f)=\frac{1}{N}\sum_{i=1}^N{L(y_i,f(x_i))}
$$
大数定律：说如果统计数据足够大,那么事物出现的频率就能无限接近它的期望值。

由于现实中训练样本数目有限，甚至很小，所以需要矫正。

经验风险最小化
$\min_{f\in{F}}\frac{1}{N}\sum_{i=1}^N{L(y_i,f(x_i))}$
当模型是条件概率分布、损失函数是对数损失函数时，经验风险最小化等价于极大似然估计
结构风险最小化
$R_{srm}(f)=\frac{1}{N}\sum_{i=1}^N{L(y_i,f(xi))+\lambda J(f)},\ \lambda\ge0$
$J(f)$为模型的复杂度，是定义在假设空间的泛函；$\lambda$用以权衡经验风险和模型复杂度
当模型是条件概率分布、损失函数是对数损失函数时，模型复杂度由模型的先验概率表示时，结构风险最小化等价于最大后验概率估计

算法

6.模型评估与模型选择

通常将学习方法对未知数据的预测能力称为泛化能力

模型选择方法：正则化和交叉验证

正则化符合奥卡姆剃刀（Occam’s razor）原理
如无必要，勿增实体，即简单有效原理

交叉验证：简单交叉（分成两部分）、S折交叉（分成S分）、留一交叉（S=N）

7.泛化误差上界

$$
对二分类问题，泛化误差R(f)：R(f)\le\hat{R}(f)+\epsilon(d,N,\delta),\ \epsilon(d,N,\delta)=\sqrt{\frac{1}{2N}(\log{d}+\log\frac{1}{\delta})}\
Hoeffding不等式：\forall{t\gt0},P(|\overline{X}-E[\overline{X}]|\ge t)\le2exp(-\frac{2n^2t^2}{\sum_{i=1}^{n}(b_i-a_i)^2})
$$

8.监督学习应用

TP（正确（T）预测为正样例（P））——正预测为正
FN（错误（F）预测为负样本（N））——正预测为负
FP（错误（F）预测为正样例（P））——负预测为正
TN（正确（T）预测为负样本（N））——负预测为负
准确率：预测为正的里面真实为正的
召回率：真实为正的里面预测为正的