统计机器学习01：机器学习中的基本概念.md

# 统计机器学习01：机器学习中的基本概念
> 统计机器学习公式推导Revisiting
什么是Machine Learning？
------------------------
机器学习(Machine Learning)实际上就是计算机系统的自我学习，通过输入的数据集来学习出一个"函数(或者说映射)"，机器学习的三大问题是：
- 监督学习Supervised
Learning：学习已经存在的结构和规则，也就是学习一个映射，即对于有标注数据的学习，常见的有分类和回归
- 非监督学习Unsupervised
Learning：学习过程中由计算机自己发现新的规则和结构，即对于无标注数据的学习，常见的有聚类和降维
- 强化学习：有反馈的学习，但是只会反馈对和错，在机器人中比较常见
监督学习的数据都是有标注的，而非监督学习的数据是没有标注的，需要在学习过程中自己发现数据中存在的一些结构和特征。
机器学习问题中**最重要并需要花最多时间的事情就是定义模型**，机器学习的三个要素是模型的表示、度量和优化。
几个机器学习中的基本概念
------------------------
- Sample，example，pattern 问题案例，样本
- Features，predictor，independent variable将需要处理的数据用高维向量来表示，一般用$x_i$表示
- State of the nature，lables，pattern class数据的类型，一般用$\omega_i$表示
- Training data：用若干组$(x_i, \omega_i)$表示训练数据集
- Test data 测试数据
- Training error & Test error 训练误差和测试误差
机器学习问题的分类
------------------
事实上1.1中介绍的三大机器学习问题只是机器学习的一种分类方法，常见的对于机器学习的分类方法还有如下几种：
### 按模型分类
根据模型的类型，机器学习还存在如下几种分类方式：按照是否为概率模型分类、按照是否为线性模型分类、按照是否为参数化模型分类，每种分类方式的特点如下：
- 概率模型和非概率模型：非概率模型也叫做确定性模型，区别在于概率模型在学习时使用条件概率分布形式，二非概率模型使用函数形式
- 线性模型和非线性模型：主要区别在于模型是否为线性函数，神经网络就是复杂的非线性模型
- 参数化模型和非参数化模型：区别在于参数化模型用确定个参数刻画模型，而非参数化模型的参数维度不固定
### 按算法分类
可以分为在线学习和批量学习，在线学习是每次接受一个样本进行预测，然后进行学习，并不断重复的过程，而批量学习则是一次性把数据集训练完之后再
进行结果的预测
模型的复杂度 Complexity
-----------------------
随着模型的复杂度提高，其训练误差会不断下降，但是测试误差会先下降再提高。因此模型存在一个最优的复杂度。
模型训练的过程中可能会出现过拟合(overfitting)的情况.
按照我个人的表达方式，过拟合其实就是对测试数据拟合得太好而对训练数据拟合效果不好。
泛化(Generalization)能力：表示一个模型对未出现过的数据样本的预测能力，我们一般希望泛化能力越大越好。
模型的评估
----------
### 样本数据集的表示
我们用$D = \lbrace(x_1,y_1),(x_2,y_2),\dots,(x_m,y_m)\rbrace$表示样本数据集 其中 $y_i$表示 $x_i$的真实标记，要评估学习的性能，需要将预测结果和真实标记进行比较。
### 指示函数
指示函数 $\mathbb I(e)$在表达式e的值为真的时候值为1，在表达式e为假的时候值为0
### 错误率和准确率
模型训练的错误率定义为
$$
E(f; D)=\frac{1}{m}\sum_{i=1}^{m}\mathbb I(f(x_i)\not=y_i)
$$
精确度的定义为：
$$
acc(f;D)=\frac{1}{m}\sum_{i=1}^{m}\mathbb I(f(x_i)=y_i)=1-E(f;D)
$$
### 查准率和查全率
真实情况 结果为正例 结果为反例
---------- ------------ ------------
正例 TP FN
反例 FP TN
- 查准率 $P=\frac{TP}{TP+FP}$ 表示预测结果为正例中预测正确的比例
- 查全率 $R=\frac{TP}{TP+FN}$ 表示所有正例中被预测对的比例
No Free Lunch
-------------
我们总希望我们的机器学习算法在所有情况下都表现得非常优秀，因为这样可以帮我们省很多事，然而事实上这是不可能的，因为对于同一个问题的两种解决算法A和B，如果A在某些情况下表现比B要好，那么A就一定会在另一些情况里表现得比B要差，这是因为对于一个问题，其所有情况的总误差和算法是没有关系的，也就是说，**一个特定问题的所有可能情况的总误差也是一定的**。
下面我们可以来简单地证明这一个结论，我们用X表示样本空间，H表示假设空间，并且假设它们都是离散的，令$P(h|D,\lambda_a)$表示算法a在训练集D下产生假设h的概率，再用f代表我们希望学习的真实目标函数，则可以用$C=X-D$来表示训练集之外的所有样本，则其产生的误差可以表示为：
$$
E(\lambda_a|D,f)=\sum_h\sum_{X\in C} P(x)\mathbb{I}(h(x)\not= f(x))P(h|D,\lambda_a)
$$
考虑最简单的二分类问题，并且真实目标函数可以是任何映射到0和1上的函数，因此可能的函数有$2^{|X|}$,对所有可能的f按照均匀分布求和，有
$$
\begin{aligned}
\sum_f E(\lambda_a|D,f) & =\sum_f\sum_h\sum_{X\in C} P(x)\mathbb{I}(h(x)\not= f(x))P(h|D,\lambda_a)\\
& = \sum_{x\in C} P(x)\sum_h P(h|D,\lambda_a) \sum_f\mathbb{I}(h(x)\not= f(x)) \\
& = \sum_{x\int C} P(x) \sum_h P(h|D,\lambda_a) \frac 12 2^{|X|}\\
& = 2^{|X|-1}\sum_{x\in C}P(x)\sum_h P(h|D,\lambda_a)\\
& = 2^{|X|-1}\sum_{x\in C}P(x)
\end{aligned}
$$
我们发现这其实是一个常数，也就是说不管选择了什么算法，其在特定问题和特定数据集下的总误差是一定的，因此两个算法一定会在一些问题上的表现互有胜负，这也就是There is no free lunch定理。
误差，偏差和方差
----------------
在机器学习中我们非常关注学习的效果，这可以通过误差的指标来衡量，常见的一种误差就是均方误差，比如在回归问题中，均方误差可以表示为：
$$
E(f; \mathcal D)=\frac{1}{m}\sum_{i=1}^{m}(f(x_i)-y_i)^2
$$
如果采用概率密度函数，就可以计算连续状态下的均方误差：
$$
E(f; \mathcal D)=\int_{x\thicksim D}(f(x_i)-y_i)^2p(x)dx
$$
而均方误差又可以进一步的分解。
### 方差variance和偏差bias
对于数据集D和学习模型f，学习算法期望预测为：
$$
\overline f(x)=\mathbb E_{D}(f(x;\mathcal D))
$$
则根据方差的定义，可以得到方差的表达式：
$$
var(x)=\mathbb E_{D}[(f(x;\mathcal D)-\overline f(x))^2]
$$
我们又可以定义**模型的期望预测值和真实标记之间的误差为偏差**(bias)，即
$$
bias^2(x)=(\overline f(x)-y)^2
$$
则在回归问题的均方误差中，我们可以将均方误差分解为：
$$
E(f;\mathcal D)=var(x)+bias^2(x)+\epsilon^2
$$
其中$\epsilon^2=\mathbb E_{D}[(y_D-y)^2]$表示样本产生的噪声(noise)
连续形式的bias和variance
------------------------
变量取值连续的情况下，引入概率密度函数，bias和variance的表达式可以写为：
$$
bias^2=\int (E_D(f(x,D))-E(y|x))^2 p(x)dx
$$
$$
var=\int E_D[(f(x,D)-E_D(f(x,D)))^2]p(x)dx
$$