基本概念



统计学习

统计学习是基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科。 也称为统计机器学习。



统计学习的主要特点


统计学习以计算机及网络为平台， 是建立在计算机及网络之上的； 
统计学习以数据为研究对象， 是数据驱动的学科； 
统计学习的目的是对数据进行预测与分析； 
统计学习以方法为中心， 统计学习方法构建模型并应用模型进行预测与分析； 
统计学习是概率论、 统计学、 信息论、计算理论、 最优化理论及计算机科学等多个领域的交叉学科， 并且在发展中逐步形成独自的理论体系与方法论




统计学习的对象

统计学习的对象是数据（data）。 它从数据出发， 提取数据的特征， 抽象出数据的模型， 发现数据中的知识， 又回到对数据的分析与预测中去。 



统计学习关于数据的基本假设

统计学习关于数据的基本假设是同类数据具有一定的统计规律性， 这是统计学习的前提。这里的同类数据是指具有某种共同性质的数据， 例如英文文章、 互联网网页、 数据库中的数据等。由于它们具有统计规律性， 所以可以用概率统计方法来加以处理。 比如， 可以用随机变量描述数据中的特征， 用概率分布描述数据的统计规律。



数据的类型

数据分为连续型变量和离散型变量。



统计学习的目的

统计学习用于对数据进行预测与分析， 特别是对未知新数据进行预测与分析。


对数据的预测可以使计算机更加智能化， 或者说使计算机的某些性能得到提高； 
对数据的分析可以让人们获取新的知识， 给人们带来新的发现。
对数据的预测与分析是通过构建概率统计模型实现的。 


统计学习总的目标就是考虑学习什么样的模型和如何学习模型， 以使模型能对 

数据进行准确的预测与分析， 同时也要考虑尽可能地提高学习效率。



统计学习的方法

统计学习的方法是基于数据构建统计模型从而对数据进行预测与分析。 分为：


监督学习（supervised learning）  
非监督学习（unsupervised learning）
半监督学习（semi-supervised learning）
强化学习（reinforcement learning） 


对于监督学习，统计学习的方法可以概括如下：  

1. 从给定的、 有限的、 用于学习的训练数据（training data） 集合出发； 

2. 假设数据是独立同分布产生的；  

3. 并且假设要学习的模型属于某个函数的集合， 称为假设空间（hypothesis space）； 

4. 应用某个评价准则 ， 从假设空间中选取一个最优的模型， 使它对已知训练数据及未知测试数据（test data） 在给定的评价准则下有最优的预测； 

这样， 统计学习方法包括模型的假设空间、 模型选择的准则以及模型学习的算法， 称其为统计学习方法的三要素。简称为模型（model） 、 策略（strategy） 和算法（algorithm） 。



实现统计学习方法的步骤


得到一个有限的训练数据集合；
确定包含所有可能的模型的假设空间， 即学习模型的集合；
确定模型选择的准则， 即学习的策略；
实现求解最优模型的算法， 即学习的算法；
通过学习方法选择最优模型；
利用学习的最优模型对新数据进行预测或分析。




统计学习的研究

统计学习研究一般包括统计学习方法、 统计学习理论及统计学习应用三个方面：


统计学习方法的研究旨在开发新的学习方法；
统计学习理论的研究在于探求统计学习方法的有效性与效率， 以及统计学习的基本理论问题； 
统计学习应用的研究主要考虑将统计学习方法应用到实际问题中去， 解决实际问题。




统计学习的重要性


统计学习是处理海量数据的有效方法
统计学习是计算机智能化的有效手段
统计学习是计算机科学发展的一个重要组成部分。 可以认为计算机科学由三维组成： 系统、 计算、 信息。 统计学习主要属于信息这一维， 并在其中起着核心作用。

此篇为 李航老师著的《统计学习方法》的学习笔记汇总，准备学习并敲一敲代码，还请大家不吝赐教！updated on 2020.4.26
一些相关的实践：请查阅机器学习
1. 统计学习及监督学习概论
2. 感知机（Perceptron）
3. K 近邻法（K-Nearest Neighbor, K-NN）
4. 朴素贝叶斯法（Naive Bayes，NB）
5. 决策树（Decision Tree，DT）
6. 逻辑斯谛回归模型（ Logistic Regression，LR）& 最大熵模型（Max Entropy，ME）
7. 支持向量机（Support Vector Machines，SVM）
8. 提升方法（Boosting）
9. EM（期望极大化）算法及其推广
10. 隐马尔科夫模型（Hidden Markov Model，HMM）
11. 条件随机场（Conditional Random Field，CRF）
12. 监督学习方法总结

13. 无监督学习概论
14. 聚类方法（Clustering）
15. 奇异值分解（Singular Value Decomposition，SVD）
16. 主成分分析（Principal Component Analysis，PCA）
17. 潜在语义分析（Latent Semantic Analysis，LSA）
18. 概率潜在语义分析（Probabilistic Latent Semantic Analysis，PLSA）
19. 马尔可夫链蒙特卡罗法（Markov Chain Monte Carlo，MCMC）
20. 潜在狄利克雷分配（Latent Dirichlet Allocation，LDA）
21. PageRank 算法
22. 无监督学习方法总结

统计学习的方法：

监督学习
非监督学习
半监督学习
强化学习



第一章 统计学习方法概论
1.2监督学习

监督学习的任务是学习一个模型，使模型能够对任意给定的输入，对其相应的输出做出一个好的预测。
监督学习的目的在于学习一个由输入到输出的映射，这一映射由模型来表示

1.2.2问题的形式化

监督学习分为学习和预测两个过程

1.3统计学习三要素

方法=模型+策略+算法

1.3.1模型

模型就是要学习的条件概率分布或者决策分布

1.3.2策略

用一个损失函数或者代价函数来度量预测错误的程度
损失函数

0-1损失函数
平方损失函数
绝对损失函数
对数损失函数


模型f（X）关于训练数据集的平均损失称为经验风险或经验损失
期望风险是模型关于联合分布的期望损失，经验风险是模型关于训练样本集的平均损失
监督学习的两个基本策略：经验风险最小化与结构风险最小化
经验风险最小化的策略认为经验风险最小的模型就是最优模型
结构风险最小化（SRM）是为了防止过拟合的策略，等价于正则化

结构风险在经验风险上加上表示模型复杂度的正则化项或罚项



1.3.3算法

算法是指学习模型的具体计算方法

1.4模型评估与模型选择
1.4.1训练误差与测试误差

损失函数给定时，基于损失函数的模型的训练误差和模型的测试误差就是学习方法评估的标准
训练误差是模型关于训练数据集的平均损失
测试误差是模型关于测试数据集的平均损失
通常将学习方法对未知数据的预测能力称为泛化能力

1.4.2过拟合与模型选择

当模型的复杂度增大时，训练误差会逐渐减小并趋向于0；而测试误差会先减小，达到最小值后又增大

1.5正则化与交叉验证
1.5.1正则化

正则化是结构风险最小化策略的实现， 是在经验风险上加一个正则化项或罚项

正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大


范数就是衡量向量的大小
正则化符合奥卡姆剃刀（Occam’s razor）原理。应用于模型选择：在所有可能选择的模型中，能够很好地解释已知数据并且十分简单才是最好的模型。

从贝叶斯估计的角度来看，正则化项对应于模型的先验概率。可以假设复杂的模型有较大的先验概率，简单的模型有较小的先验概率。



1.5.2交叉验证

将数据集分为三部分;

训练集：训练模型
验证集：模型的选择
测试集：对学习方法的评估


简单交叉验证

数据集分为两部分：

训练集  70%
测试集  30%


选出测试误差最小的模型


S折交叉验证

首先随机地将已给数据切分为S个互不相交的大小相同的子集；然后利用S-1个子集的数据训练模型，利用余下的子集测试模型；将这一过程对可能的S种选择重复进行；最后选出S次评测中平均测试误差最小的模型


留一交叉验证

S折交叉验证的特殊情形是S=N，称为留一交叉验证，往往在数据缺乏的情况下使用（N是给定数据集的容量）



1.6泛化能力
1.6.1发话误差

模型对未知数据预测的误差即为泛化误差。泛化误差越小，这种方法就越有效

1.6.2泛化误差上界

训练误差小的模型，泛化误差也会小

1.7

监督学习的任务就是学习一个模型，应用这一模型，对给定的输入预测相应的输出
监督学习方法又可分为判别方法和生成方法

生成方法由数据学习联合概率分布P(X, Y)，然后求出条件概率模型P(Y | X)作为预测的模型，即生成模型：

$P(Y | X) = \frac{P(X, Y)} {P(X)}$

典型的生成模型有：

朴素贝叶斯法
隐马尔可夫模型
等


特点：

生成方法可以还原出联合概率分布P(X, Y),而判别方法则不能
生成方法的学习速度更快，即当样本容量增加的时候，学到的模型可以更快地收敛于真实模型
当存在隐变量时，仍可以用生成方法学习，此时判别方法就不能用




判别方法有数据直接学习决策函数f(X)或者条件概率分布P(Y | X)作为预测模型，即判别模型

典型的判别模型方法：

k临近法
感知机
决策树
逻辑斯谛回归模型
最大熵模型
支持向量机
提升方法
条件随机场
等


特点：

判别方法直接学习的是条件概率P(Y | X)或决策函数f(X)，直接面对预测，往往学习的准确率更高
由于直接学习P(Y | X)或f(X)，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题







1.8分类问题

监督学习从数据中学习一个分类模型或分类决策函数，称为分类器。分类器对新的输入进行输出预测，称为分类
分类问题分为学习和分类
分类器的性能指标一般是分类准确率：

对于给定的测试数据集，分类器正确分类的样本数与总样本数之比。也就是损失函数0-1损失时测试数据集上的准确率


二分类评价指标值精准率和召回率





类别
解释




TP
将正类预测为正类数


FN
将正类预测为负类数


FP
将负类预测为正类数


TN
将负类预测为负类数



精确率：

$P = \frac{TP} {TP + FP}$

召回率：

$R = \frac{TP}{TP + FN}$

F1值：

$\frac{2} {F1} = \frac{1} {P} + \frac{1} {R}$
$F1 = \frac {2 * TP} {2 * TP + FP + FN}$
1.9标注问题

输入是一个观测序列，输出是一个标记序列或状态序列
常用统计学习方法有：

隐马尔科夫模型
条件随机场



1.10回归问题

回归用于预测输入变量（自变量）和输出变量（因变量）之间的关系，特别是当输出变量的值发生变化时，输出变量的值随之发生变化。
按照输入变量的个数，分为一元回归和多元回归
按照输入变量和输出变量之间关系类型，分为线性回归和非线性回归
回归学习最常用的损失函数是平方损失函数，由最小二乘法求解

第二章 感知机

感知机是二分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别
属于判别模型

2.1感知机模型

感知机定义：

输入空间（特征空间）是$X \subseteq R^n$
输出空间是$y = \begin{Bmatrix}+1， -1\end{Bmatrix}$
输入空间到输出空间的函数（称为感知机）$f(x) = sign(w * x + b)$

w和b为感知机模型参数
w叫做权值或权值向量
b叫做偏置
w * x表示w和x的内积
sign是符号函数





2.2感知机学习策略

数据集的线性可分性

如果存在某个超平面S能够将数据集的正实例和负实例点完全正确地划分到超平面的两侧，即对所有$y_i = +1$ 的实例 i，有$w * x_i + b > 0$,对所有$y_i = -1$的实例 i，有$w * x_i + b < 0$,则称数据集T为线性可分数据集。


感知机学习策略

感知机sign(w * x + b)学习的损失函数定义为$L(w, b) = - \sum_{x_i \in M} y_i(w * x_i + b)$
M为误分点的集合，感知机学习的经验风险函数
损失函数L（w， b）是w， b的连续可导函数



2.3感知机学习算法

损失函数极小化问题的损失函数$\min_{w, b}L(w, b) = - \sum_{x_i \in M} y_i * (w * x_i + b)$

损失函数对应于误分类点到分离超平面的总距离

第三章 k近邻法

k近邻法（k-NN）是一张基本分类回归方法
基本要素：

k值的选择
距离度量
分类决策规则



3.1k近邻算法

定义：

给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k和实例，这k个实例的多数属于某个类，就把该输入实例分为这个类


没有显式的学习过程

3.2.2距离度量

欧式距离：以空间为基准的两点之间最短距离
曼哈顿距离：两点在南北方向上的距离加上在东西方向上的距离，即$d（i，j）=|xi-xj|+|yi-yj|$

3.2.3k值的选择

k值的减小就意味着整体模型变得复杂，容易发生过拟合
k值的增大就相当于用较大邻域中的训练实例进行预测，可以减少学习的估计误差，学习的近似误差增大，模型变得简单
应用中，k值一般取一个较小的数值，通常采用交叉验证法来选取最优的k值

3.3k近邻法的实现：kd树

k近邻法最简单的实现就是线性扫描，当训练集很大时，计算非常耗时

3.3.1构造kd树

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构
kd树是二叉树，表示对k维空间的划分
构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超巨型区域。kd树的每个节点对应于一个k维超巨型区域

3.3.2 搜索kd树

kd树的最邻近搜索

输入：已构造的kd树；目标点x
输出：x的最邻近
解答：

在kd树中找出包含目标点x的叶节点：从根节点出发，递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子节点，否则移到右子节点。直到子节点为叶节点为止
以此叶节点为“当前最近点”
递归地向上回退，在每个节点进行以下操作：

如果该节点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”
当前最近点一定存在于该节点一个子节点对应的区域。检查该子节点的父节点的另一子节点的区域是否有更近的点。具体地，检查另一子节点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超平面球体相交。如果相交，可能在另一个子节点对应的区域内存在距目标点更近的点，移动到另一个子节点。接着，递归地进行最近邻搜索。


当回退到根节点时，搜索结束，最后的“当前最近点”即为x的最近邻点。





第四章 朴素贝叶斯法


朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。


对于给定的训练数据集，首先基于特征条件独立假设学习输入\输出的联合概率分布；然后基于此模型，对给定的输入x，利用贝叶斯定理求出后验概率最大的输出y


先验概率：$P(原因)$


后验概率：$P(原因|结果)$


条件概率：$P(Y|X)$ 表示在条件X成立时，Y存在成立的概率


4.1朴素贝叶斯法的学习与分类

朴素贝叶斯法通过训练数据集学习联合概率分布$P(X, Y)$

学习先验概率分布：$P(Y=c_k), k=1, 2, ……, k$

学习条件概率分布：$P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)}, ……, X^{(n)}=x^{(n)}), k=1, 2, ……, k$

于是学习到联合概率分布$P(X, Y)$
属于生成模型
朴素贝叶斯法分类时，对给定的输入x，通过学习到的模型计算后验概率分布$P(Y=c_k|X=x)$，将后验概率最大类作为x的类输出。后验概率公式：

$P(Y=c_k|X=x)=\frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_kP(X=x|Y=c_k)P(Y=c_k)}$

4.1.2后验概率最大化的含义

朴素贝叶斯法将实例分到后验概率最大的类中，等价于期望风险最小化
后验概率最大化准则：$f(x)=\mathop{\arg\max}_{c_k}P(c_k|X=x)$

4.2.1极大似然估计

先验概率$P(Y=c_k)$的极大似然估计是$P(Y=c_k)=\frac{\sum_{i=1}^NI(y_i=c_k)}{N}, k=1, 2, ……, K$
条件概率$P(X^{(f)}=a_{jl}|Y=c_k)$的极大似然估计是$P(X^{(f)}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^NI(x_i^{(f)}=a_{jl}, y_i=c_k)}{\sum_{i=1}{N}I(y_i=c_k)}$

$j=1, 2, ……, n; l=1, 2, ……, S_j; k=1, 2, ……, K$

式中，$x_i^{(f)}$是第i个样本的第j个特征；$a_{jl}$是第j个特征可能取的第l个值；I为指示函数

4.2.3贝叶斯估计


用极大似然估计可能会出现所要估计的概率值为0的情况。条件概率的贝叶斯估计是$P_\lambda(X^{j}=a_{jl}|Y=c_k)=\frac{\sum^N_{i=1}I(x_i^{(j)}=a_{jl}, y_i=c_k)+\lambda}{\sum_{i=1}^NI(y_i=c_k)+S_j\lambda}$


式中$\lambda>=0$等价于在随机变量各个取值的频数上赋予一个正数$\lambda>0$。当$\lambda=0$时就是极大似然估计。常取$\lambda=1$，这时称为拉普拉斯平滑。显然对于任何$l=1, 2, ……, S_j, k=1, 2, ……, K$有$P_\lambda(X^{(f)=a_{jl}}|Y=c_k)>0$$\sum_{l=1}^{S_j}P(X^{j}=a_{jl}|Y=c_k)=1$先验概率的贝叶斯估计是$P_\lambda(Y=c_k)=\frac{\sum_{i=1}^NI(y_i=c_k)+\lambda}{N+K\lambda}$


本章概要

生成方法由训练数据学习联合概率分布$P(X, Y)$，然后求得到后验概率分布$P(Y|X)$。利用训练数据学习$P(X|Y)$和$P(Y)$的估计，得到联合概率分布：$P(X, Y)=P(Y)P(X|Y)$
朴素贝叶斯法的基本假设是条件概率独立性，$P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)}, ……, X^{(n)}=X^{(n)}|Y=c_k)$$=\prod^n_{j=1}P(X^{(j)}=x^{(j)}|Y=c_k)$这是一个较强的假设，因此条件概率的数量大为减小，朴素贝叶斯法的学习与预测大为简化。因而朴素贝叶斯法高效，且易于实现，缺点是分类的性能不一定很高。
朴素贝叶斯法利用贝叶斯定理与学到的联合概率模型进行预测。$P(Y|X)=\frac{P(X, Y)}{P(X)}=\frac{P(Y)P(X|Y)}{\sum_YP(Y)P(X|Y)}$将输入x分到后验概率最大的类y。

$y=\mathop{\arg\max}_{c_k}$\
$P(Y=c_k)\prod^n_{j=1}P(X_j=x^{(j)}|Y=c_k)$


后验概率最大等价于0-1损失函数时的期望风险最小化

注解：

$P(A|B)=P(B|A)*\frac{P(A)}{P(B)}$

贝叶斯三要素



第五章 决策树

决策树的学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪

5.1.1决策树模型

定义：分类决策树模型是一种描述对实例进行分类的树形结构

5.2.1特征选择
5.2.2信息增益

熵是表示随机变量不确定性的度量
信息增益：定义：

特征A对训练集D的信息增益g(D, A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D | A)之差，及：$g(D, A) = H(D) - H(D | A)$
一般地，熵H(Y)与条件熵H(Y | X)之差称为互斥信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。



5.3决策树的生成
第六章 逻辑斯谛回归与最大熵模型

都属于对数线性模型

逻辑斯谛回归模型
6.1.1逻辑斯谛分布

定义：

设X是连续随机变量，X服从逻辑斯谛分布是指X具有下列分布函数和密度函数：$F(x)=P(X \le x0)=\frac{1}{1+e^{-(x-\mu)/\gamma}}$

$f(x)=F^{'}(x)=\frac{e^{-(x-\mu)/\gamma}}{\gamma(1+e^{-(x-\mu)/\gamma})^2}$式中，$\mu$为位置参数，$\gamma>0$为形状参数



6.1.2二项逻辑斯谛回归模型

定义：二项逻辑斯谛回归模型是如下的条件概率分布：$P(Y=1|x)=\frac{exp(w*x+b)}{1+ exp(w * x+b)}这里，x\in R^n是输入，Y\in \\{0, 1\\}是输出，$

$w\in R^n 和 b\in R是参数，w称为权值向量，b称为偏置，w*x为w和x的内积$
6.1.3模型参数估计
$假设w的极大似然估计值是\hat{w}，那么学到的逻辑斯谛回归模型为$
$P(Y=1|X)=\frac{exp(\hat{w}*x)}{1+exp(\hat{w}*x)}$
$P(Y=0|X)=\frac{1}{1+exp(\hat{w}*x)}$
6.2最大熵模型
6.2.1最大熵原理
$假设离散随机变量X的概率分布是P(X)，其熵是$
$H(P)=-\sum_xP(x)logP(x)$
$熵满足下列不等式：0\le H(P)\le log|X|$
式中，|X|是X的取值个数，当且仅当X的分布是均匀分布时右边的等号成立。就是，当X服从均匀分布时，熵最大。
最大熵模型：假设满足所有约束条件的模型集合为$C\equiv \\{ P\in p | E_p(f_i)=E_{\bar{p}}(f_i)，i=1, 2, ……, n \\}$
$定义在条件概率分布P(Y|X)上的条件熵为H(P)=-\sum_{x,y}\bar{P}(x)P(y|x)logP(y|x)$
$则模型集合C中条件熵H(P)最大的模型称为最大熵模型。式中的对数为自然对数$
P99

文章作者：Tyan

博客：noahsnail.com  |  CSDN  |  简书
1. 统计学习方法概论
本文是统计学习方法（李航）第一章的学习总结。
1.1 统计学习
1.统计学习的特点
统计学习（statistical learning）是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测和分析的一门学科。统计学习也称为统计机器学习（statistical machine learning）。现在人们提到的机器学习往往是指统计机器学习。
统计学习的特点：(1)以计算机和网络为平台；(2)以数据为研究对象，是数据驱动的学科；(3)目的是对数据进行分析和预测；(4)以方法为中心，构建模型并应用模型进行分析和预测；(5)是概率论、统计学、信息论、优化理论和计算机科学等多个领域的交叉学科。
2.统计学习的对象
统计学习的对象是数据（data）。它从数据出发，提取数据特征，抽象出数据模型，根据模型对数据进行分析和预测。统计学习的前提是假设同类数据（具有某种共同性质）具有一定的统计规律性。统计学习过程中，以变量或变量组表示数据，数据分为连续变量和离散变量表示的类型。
3.统计学习的目的
统计学习总的目标就是考虑学习什么的模型和如何学习模型，以使模型能够对数据进行准确的预测和分析，同时也要考虑学习效率。
4.统计学习的方法
统计学习分为监督学习（supervised learning）、非监督学习（unsupervised learning）、半监督学习(semi-supervised learning)和强化学习(reinforcement learning)等。统计学习方法包括模型的假设空间、模型选择的准则及模型选择的算法，称为统计学习方法的三要素，简称模型（model）、策略（strategy）和算法（algorithm）。
5.统计学习的研究
统计学习的研究包括统计学习方法（算法创新）、统计学习理论（算法效率及有效性）及统计学习应用（解决问题）三个方面。
6.统计学习的重要性
统计学习的重要性体现在三个方面：（1）统计学习是处理海量数据的有效方法。（2）统计学习是计算机智能化的有效手段。（3）统计学习是计算机发展的重要组成部分。
1.2 监督学习
监督学习的任务是学习一个模型，使模型能够对任意给定的输入，对其相应的输出做出一个好的预测。
1.2.1 基本概念
1.输入空间、特征空间与输出空间
在监督学习中，输入与输出的所有可能的取值集合分别称为输入空间（input space）和输出空间（output space）。通常输出空间远远小于输入空间。
每个具体的输入是一个实例（instance），通常由特征向量（feature vector）表示。所有特征向量存在的空间称为特征空间（feature space）。特征空间的每一维对应一个特征。当输入空间与特征空间不同时，需要将实例从输入空间映射到特征空间，模型实际上都是定义在特征空间上的。
监督学习过程中，将输入和输出看作是定义在输入空间和输出空间上的随机变量的取值。习惯上输入变量写作X，其取值写作x，输出变量写作Y，其取值写作y。输入实例的x的特征向量记作
$x = (x^{(1)}, x^{(2)},..., x^{(i)} ,...,x^{(n)})^T$
$x^{(i)}$表示向量x的第i个特征，而$x_i$表示第i个输入变量。
$x_i = (x_i^{(1)}, x_i^{(2)},..., x_i^{(i)} ,...,x_i^{(n)})^T$
监督学习从训练数据中学习模型，对测试数据进行预测。训练集通常表示为
$T = {(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$
$(x_i,y_i)$表示样本或样本点。
输入变量和输出变量可以是离散型的，也可以是连续型的。输入变量和输出变量都是连续型变量的预测问题称为回归问题；输出变量为有限个离散型变量的预测问题称为分类问题；输入变量和输出变量均为变量序列的预测问题称为标注问题。
2.联合概率分布
监督学习假设输入与输出的随机变量X和Y遵循联合概率分布P(X,Y)，P(X,Y)表示分布函数或分布密度函数。训练数据和测试数据被看作是依联合概率分布P(X,Y)独立同分布产生的。统计学习假设数据存在一定的统计规律。
3.假设空间
监督学习的目的在于学习一个由输入到输出的映射，映射关系用模型表示。输入到输出的映射集合就是假设空间（hypothesis space）。简单学习的模型可以是概率模型或非概率模型。由条件概率分布P(Y|X)或决策函数Y=f(X)表示。对具体的输入进行输出预测时，写作P(y|x)或y=f(x)。
1.2.2 问题的形式化
监督学习利用训练数据学习模型，再用模型对测试数据进行预测。学习过程中的训练数据往往是人工给出的，因此称为监督学习。监督学习分为学习和预测两个过程，如下图：

首先给定数据集$T={(x_1,y_1),(x_3,y_2),...,(x_N,y_N)}$，其中$(x_i,y_i)，i=1,2,...,N$，称为样本或样本点，$x_i \in X \subseteq R^n$是输入的观测值，称为输入或实例，$y_i \in Y$是输出的观测值，也称为输出。通过学习得到的模型表示为条件概率分布$P(Y|X)$和决策函数$Y=f(X)$，模型表示的是输入与输出之间的映射关系。
预测过程中，对于测试数据中的输入$x\_{N+1}$,由模型$y\_{N+1}=argmax P(y\_{N+1}|x\_{N+1})$或$y\_{N+1}=f(x\_{N+1})$给出对应的输出$y\_{N+1}$。
1.3 统计学习三要素
统计学习方法的三要素为模型、策略和算法，它们关系为：统计学习方法 = 模型 + 策略 + 算法。
1.3.1 模型
在监督学习过程中，模型是要学习的条件概率分布或决策函数。模型的假设空间包含所有可能的条件概率分布或决策函数。假设空间用F表示：

$F=\lbrace f|Y=f(X)\rbrace$

X和Y是定义在输入输出空间上的变量，F通常是由一个参数向量决定的函数族：

$F=\lbrace f|Y=f_\theta (X),\theta \in R^n \rbrace$

参数向量$\theta$取值于n维欧式空间$R^n$，称为参数空间（parameter space）。假设空间也可以定义为条件概率的集合：
$F=\lbrace P|P(Y|X)\rbrace$

X和Y是定义在输入输出空间上的随机变量，F通常是一个由参数向量决定的条件概率分布族：
$F=\lbrace P|P_\theta (Y|X)，\theta \in R^n \rbrace$

参数向量$\theta$取值于n维欧式空间$R^n$，也称为参数空间。
1.3.2 策略
有了模型的假设空间，统计学习接着考虑的是按照什么样的准则学习或选择最优的模型，统计学习的目标在于从假设空间中选取最优的模型。损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。
1.损失函数和风险函数
监督学习问题是在假设空间F中选取f作为决策函数，对于给定的输入X，f(X)给出对应的输出Y，输出预测值f(X)与真实值Y可能一致也可能不一致，用一个损失函数（loss function）或代价函数（cost function）。损失函数是f(X)和Y的非负实值函数，记作$L(Y,f(X))$。统计学习常用的损失函数有以下几种：


0-1损失函数（0-1 loss function）

$L(Y,f(X))=
\begin{cases}  
1, Y \neq f(X) \\\\
0, Y=f(X) 
\end{cases}$


平方损失函数（quadratic loss function）

$L(Y,f(X))=(Y-f(X))^2$


绝对损失函数（absolute loss function）

$L(Y,f(X))=|(Y-f(X))|$


对数损失函数（logarithmic loss function）或对数似然损失函数(log-likelihood loss function)

$L(Y,f(X))=-\log P(Y|X)$


损失函数越小，模型越好。由于模型输入、输出(X,Y)是随机变量，遵循联合分布P(X,Y)，所以损失函数的期望是
$R\_{exp}(f)=E\_p[L(Y,f(X))]=\int_{x*y}L(y,f(x))P(x,y)dxdy$
这是理论上模型f(X)关于联合分布P(x,y)的平均意义下的损失，称为风险函数（risk function）或期望损失（expected loss）。学习的目标就是选择期望风险最小的模型。由于联合分布P(X,Y)是未知的，$R_{exp}(f)$不能直接计算。如果知道联合分布P(X,Y)，从联合分布可以直接求出条件概率分布P(Y|X)，也就不需要学习了。一方面根据期望风险最小学习模型需要用到联合分布，一方面联合分布又是未知的，因此监督学习就称为一个病态问题（ill-formed problem）。
给定一个训练数据集
$T = {(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$
模型f(X)关于训练数据集的平均损失称为经验风险（empirical risk）或经验损失（empirical loss），记作$R_{emp}$：
$R\_{emp}(f)=\frac {1} {N} \sum_{i=1}^N L(y_i,f(x_i))$
期望风险$R\_{exp}(f)$是模型关于联合分布的期望损失，经验风险$R\_{emp}(f)$是模型关于训练样本集的平均损失。根据大数定律，当样本容量N趋于无穷时，经验风险$R\_{emp}(f)$趋于期望风险$R\_{exp}(f)$。因此很自然的一个想法就是用经验风险估计期望风险，但由于训练数据是有限的，因此要对经验风险进行一定的矫正。这关系到监督学习的两个基本策略：经验风险最小化和结构风险最小化。
2.经验风险最小化和结构风险最小化
在假设空间、损失函数以及训练数据集确定的情况下，经验风险函数就可以确定。经验风险最小化（empirical risk minimization，ERM）策略认为，经验风险最小的模型就是最优的模型。求解经验最小化最优模型就是求解最优化问题：
$^{min} \_{f \in F} \frac {1} {N}  \sum\_{i=1}^N L(y\_i, f(x\_i))$
当样本容量足够大时，经验风险最小化能保证有很好的学习效果，在现实中被广泛采用。极大似然估计（maximum likelihood estimation）就是经验风险最小化的一个例子。当模型是条件概率分布时，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计。但是，当样本容量很小时，经验风险最小化未必会很好，有可能产生“过拟合”现象。
结构风险最小化（structural risk minimization，SRM）是为了防止过拟合而提出来的策略，结构化风险最小化等价于正则化（regularization）。结构风险在经验风险的基础上加上了表示模型复杂度的正则项（regularizer）或惩罚项（penalty term）。在假设空间、损失函数和训练数据集确定的情况下，结构风险定义为：
$R\_{srm}(f)=\frac {1} {N} \sum_{i=1}^N L(y_i,f(x_i)) + \lambda J(f)$
$J(f)$为模型的复杂度，模型f越复杂，J(f)越大。$\lambda>=0$是权衡经验风险和模型复杂度的系数。
结构风险最小化策略认为，结构风险最小的模型就是最优的模型。求解最优模型就是求解最优化问题：
$^{min} \_{f \in F} \frac {1} {N}  \sum\_{i=1}^N L(y\_i, f(x\_i)) + \lambda J(f)$
这样，监督学习问题变成了经验风险或结构风险的最优化问题。
1.3.3算法
算法是指学习模型的具体计算方法。统计学习基于训练数据集，根据学习策略，从假设空间中选取最优模型，然后考虑用什么计算方法求解最有模型。统计学习问题变为了最优化问题，统计学习的算法变味求解最优化问题的算法。如何保证找到全局最优解，并使求解过程非常高效，就称为一个重要问题。
1.4 模型评估与模型选择
1.4.1 训练误差与测试误差
当损失函数给定时，基于损失函数的模型的训练误差和模型的测试误差就自然称为学习方法评估的标准。假设学习到的模型为$ Y=f\hat (X)$，训练误差是模型关于训练数据集的平均损失：
$R\_{emp}(f \hat)=\frac {1} {N} \sum\_{i=1}^N L(y\_i,f \hat(x\_i))$
测试误差是关于测试数据集的平均损失：
$e\_{test}(f \hat)=\frac {1} {N \prime} \sum\_{i=1}^{N\prime} L(y\_i,f \hat(x\_i))$
N和$N\prime$分别为训练数据集和测试数据集的样本容量。
通常将学习方法对未知数据的预测能力称为泛化能力（generalization ability）。
1.4.2 过拟合和模型选择
过拟合是指学习时选择的模型包含参数过多，以至于模型对已知数据预测很好，而对未知数据预测很差的现象。模型选择旨在避免过拟合并提供模型的预测能力。模型选择时，不仅要考虑对已知数据的预测能力，而且还要考虑对未知数据的预测能力。下图展示了训练误差、测试误差与模型复杂度之间的关系。当模型复杂度增大时，训练误差会逐渐减少并趋向于0；而测试误差会先减少，达到最小值后又增大。当选择的模型复杂度过大时，过拟合现象就会发生。学习时要防止过拟合，进行最优的模型选择，即选择模型复杂度适当的模型，以使测试误差达到最小。

1.5 正则化与交叉验证
1.5.1 正则化
模型选择的方法是正则化（regularization）。正则化是结构风险最小化策略的实现，是在经验风险上加上一个正则化项（regularizer）或惩罚项（penalty term）。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大。正则化一般具有以下形式：
$^{min}\_{f \in F } \frac {1} {N} \sum\_{i=1}^{N} L(y\_i,f(x\_i)) + \lambda J(f)$
其中，第一项是经验风险，第二项是正则化项，$\lambda >= 0$为调整两者之间关系的系数。
正则化项可以取不同的形式，回归问题中，损失函数是平方损失，正则化项可以是参数向量的$L\_2$范数：
$L(w)=\frac {1} {N} \sum\_{i=1}^{N} (f(x\_i;w) - y\_i)^2 + \frac {\lambda} {2} ||w||^2$
$||w||$表示参数向量w的$L\_2$范数。正则化项也可以是参数向量的$L\_1$范数：
$L(w)=\frac {1} {N} \sum\_{i=1}^{N} (f(x\_i;w) - y\_i)^2 + \frac {\lambda} {2} ||w||\_1$
$||w|\_1$表示参数向量w的$L\_1$范数。
正则化的作用是选择经验风险和模型复杂度同时较小的模型。正则化符合奥卡姆剃刀原理：在所有可能选择的模型中，应该选择能够很好的解释已知数据并且十分简单的模型。从贝叶斯估计的角度来看，正则化项对应模型的先验概率，可以假设复杂的模型具有较小的先验概率，简单的模型具有较大的先验概率。
1.5.2 交叉验证
另一种常用的模型选择方法是交叉验证（cross validation）。如果给定的样本数据充足，进行模型选择的一种简单方法是随机的将数据分为训练集（training set）、测试集（test set）和验证集（validation set）。训练集用来训练模型，测试集用于模型的评估，验证集用于模型的选择。在学习到的模型中，选择对验证集有最小预测误差的模型。当数据集不充足时，可以采用交叉验证的方法。交叉验证的基本思想是重复的使用数据；吧核定的数据分为训练集和测试集，在此基础上进行反复的训练、测试和模型选择。
1.简单交叉验证
简单交叉验证方法是：首先随机地将数据分为两部分——训练集(70%)和测试集(30%)；然后用训练集在各种条件下训练得到不同的模型，在测试集上评价各个模型的测试误差，选择测试误差最小的模型。
2.S折交叉验证
应用最多的是S折交叉验证（S-fold cross validation），首先随机地将数据分为S个互不相交的大小相同的子集，然后利用$S-1$个子集的数据进行训练，用剩下的子集进行测试；重复上述过程，最后选出S次测试中平均测试误差最小的模型。
3.留一交叉验证
S折交叉验证特殊情况是$S=N$，称为留一交叉验证（leave-one cross validation），往往在数据缺乏的情况下使用。
1.6 泛化能力
1.6.1 泛化误差
学习方法的泛化能力（generalization ability）是指由该方法学习到的模型对未知数据的预测能力，是学习方法本质上最重要的性质。通常采用测试误差来评价学习方法的泛化能力，但这种方法依赖于测试数据，但数据较少时评价结果有可能不可靠。统计学试图从理论上对学习方法的泛化能力进行分析。
首先给出泛化误差的定义，如果学到的模型是$\hat f$，那么用这个模型对未知数据预测的误差即为泛化误差（generalization error）
$R\_{exp}(\hat f)=E\_p[L(Y,\hat f(X))] = \int_{x*y}L(y,\hat f(x))P(x,y)dxdy$
泛化误差反映了学习方法的泛化能力，泛化误差就是所学习到的模型的期望风险。
1.6.2 泛化误差上界
学习方法的泛化能力分析往往是通过研究误差的概率上界进行的，简称为泛化误差上界（generalization error bound）。泛化误差上界通常具有以下性质：它是样本容量的函数，当样本容量增加时，泛化上界趋向于0；它是假设空间容量的函数，假设空间容量越大，模型就越难学，泛化误差上界就越大。
1.7 生成模型和判别模型
监督学习方法可分为生成方法（generative approach）和判别方法（discriminative approach）。所学到的模型分别称为生成模型（generative model）和判别模型（discriminative model）。生成方法由数据学习联合概率分布P(X,Y)，然后求出条件概率分布P(Y|X)作为预测的模型，即生成模型：
$P(Y|X)=\frac {P(X,Y)} {P(X)}$
之所以称为生成方法，是因为模型表示了给定输入X产生输出Y的生成关系。典型的生成模型有：朴素贝叶斯法和隐马尔可夫模型。
判别方法由数据直接学习决策函数f(X)或者条件概率分布P(Y|X)作为预测的模型，即判别模型。判别方法关心的是对给定的输入X，应该预测什么样的输出Y。典型的判别模型包括：k近邻法、感知机、决策树、逻辑回归模型、最大熵模型、支持向量机、提升方法和条件随机场。
在监督学习中，生成方法和判别方法各有优缺点，适合于不同条件下的学习问题。生成方法的特点：生成方法可以还原出联合概率分布P(X,Y)，而判别方法则不能；生成方法的收敛速度更快，当存在隐变量时，仍可以使用生成方法，此时判别方法不可用。判别方法的特点：判别方法直接学习的是条件概率P(Y|X)或决策函数f(X)，直接面对预测，往往学习的准确率更高；由于直接学习P(Y|X)或f(X)，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。
1.8 分类问题
分类是监督学习的一个核心问题。在监督学习中，当输出变量Y取有限个离散值时，预测问题便称为分类问题。监督学习从数据中学习一个分类模型或分类决策函数，称为分类器（classifier）。分类器对新的输入进行输出的预测（prediction），称为分类（classification）。分类的类别为多个时，称为多分类问题。分类问题包括学习和分类两个过程。学习过程中，根据已知的训练数据集学习一个分类器，分类过程中，根据学习的分类器对新实例进行分类。分类问题如图所示：

精确率的定义为$P=\frac {TP} {TP+FP}$，召回率的定义为$R=\frac {TP} {TP+FN}$，F1值是精确率和召回率的调和均值，公式为$F1=\frac {2PR} {P+R}$。精确率和召回率都高时，F1值也会高。
1.9 标注问题
标注（tagging）也是一个监督学习问题，可以认为标注问题是分类问题的一个推广，标注问题的输入是一个观测序列，输出是一个标记序列或状态序列。标注问题的目标在于学习一个模型，使它能够对观测序列给出标记序列作为预测。标注问题分为学习和标记过程。学习系统基于训练数据集构建一个模型，表示为条件概率，标注系统按照学习到的条件概率分布模型，对新的输入观测序列找到相应的输出标记序列。标注问题如下图所示：

评价标注模型的指标与评价分类模型的指标一样，常用的有标注准确率、精确率和召回率。标注常用的统计学习方法有：隐马尔可夫模型、条件随机场。标注问题在信息抽取、自然语言处理等领域被广泛应用，是这些领域的基本问题。
1.10 回归问题
回归（regression）是监督学习的另一个重要问题。回归用于预测输入变量（自变量）和输出变量（因变量）之间的关系，特别是当输入变量的值发生变化时，输出变量的值随之发生变化。回归模型正是表示从输入变量到输出变量之间的映射的函数。回归问题等价于函数拟合，选择一条函数曲线使其很好地拟合已知数据且很好的预测未知数据。
回归问题分为学习和预测两个过程。学习系统基于训练数据构建一个模型，预测系统根据学习的模型确定相应的输出。回归问题如下图所示：

回归问题按照变量的个数分为一元回归和多元回归；按照输入变量和输出变量之间关系的类型即模型的类型，分为线性回归和非线性回归。回归学习最常用的损失函数是平方损失函数，此情况下回归问题可以用最小二乘法求解。