Learning Theory

Andrew Ng在NIPS 2016上的观点数据划分不是以前简单的training和test了。

吴恩达NIPS 2016演讲现场直击：如何使用深度学习开发人工智能应用

Machine Learning Yearning book draft - 读记（更新至Chapters 14）

损失函数，经验风险最小，结构风险最小

Bias Error Variance

首先 Error = Bias + Variance Error反映的是整个模型的准确度 Bias反映的是模型在样本上的输出与真实值之间的误差，即模型本身的精准度 Variance反映的是模型每一次输出结果与模型输出期望之间的误差，即模型的稳定性

Bias: a learner’s tendency to consistently learn the same wrong thing，即度量了某种学习算法的平均估计结果所能逼近学习目标(目标输出)的程度。 Variance：the tendency to learn random things irrespective of the real signal，即度量了在面对同样规模的不同训练集时，学习算法的估计结果发生变动的程度。比如在同一现象所产生的不同训练数据上学习的决策树往往差异巨大，而实际上它们应当是相同的。

MSE(mean squared error)

\begin{align} MSE & = E[(f(x)-Y)^2] \quad \text{其中Y为x对应的真实类标，f(x)为预测标号}\\ & = [Ef(x)-Y]^2 + E[f(x)-Ef(x)]^2 \\ & ={Bias}^2 + Variance \end{align}

所以bias表示预测值的均值与实际值的差值；而variance表示预测结果作为一个随机变量时的方差。

换一种描述：

偏差 $\delta^2$ :不同次采样时学习器预测的均值和 真实值 的差距
方差 $\sigma^2$ :不同次采样时学习器预测值间的差异

实际值y（未知），模型预测值 $f(x)$ ，

\tilde{f}(x) = E(f(x)) \quad f(x) \mbox{的均值}\\ \begin{align} E[(y-f(x))^2] & = E[(y- \tilde{f}(x) + \tilde{f}(x) - f(x))^2] \\ & = E[(y- \tilde{f}(x))^2] + 2(y- \tilde{f}(x)) {\color{Blue} {E[\tilde{f}(x) - f(x)] }} + E[(\tilde{f}(x) - f(x))^2] \\ & = E[(y- \tilde{f}(x))^2] + E[(\tilde{f}(x) - f(x))^2] \\ & ={Bias}^2 + Variance \end{align}

蓝色字体部分等于0

在一个实际系统中，Bias与Variance往往是不能兼得的。如果要降低模型的Bias，就一定程度上会提高模型的Variance，反之亦然。造成这种现象的根本原因是，我们总是希望试图用有限训练样本去估计无限的真实数据。当我们更加相信这些数据的真实性，而忽视对模型的先验知识，就会尽量保证模型在训练样本上的准确度，这样可以减少模型的Bias。但是，这样学习到的模型，很可能会失去一定的泛化能力，从而造成过拟合，降低模型在真实数据上的表现，增加模型的不确定性。相反，如果更加相信我们对于模型的先验知识，在学习模型的过程中对模型增加更多的限制，就可以降低模型的variance，提高模型的稳定性，但也会使模型的Bias增大。Bias与Variance两者之间的trade-off是机器学习的基本主题之一，可以在各种机器模型中发现它的影子。

模型泛化误差 generalization err 包含了在样本上的期望误差和训练集上的误差。

如何在Bias和Variance之间tradeoff

机器学习中使用「正则化来防止过拟合」到底是一个什么原理？为什么正则化项就可以防止过拟合？

模型选择

一般而言模型选择准则有如下几种：

重复抽样与预测稳定性角度：CV、GCV、Boostrap
似然与模型复杂度角度：AIC、AICc、BIC、EBIC
VC维与风险上界控制角度：SRM

模型评价 众多模型中选择最佳，或模型融合后再评价

分类：ROC、AUC、TPR、FPR、F1 score；
排序：DCG、NDCG；
回归：RMSE、MAE、Deviance。

结构化风险 = 经验风险 + 置信风险经验风险 = 分类器在给定样本上的误差置信风险 = 分类器在未知文本上分类的结果的误差

置信风险因素：

样本数量，给定的样本数量越大，学习结果越有可能正确，此时置信风险越小；
分类函数的VC维，显然VC维越大，推广能力越差，置信风险会变大。

提高样本数量，降低VC维，降低置信风险。

结构风险控制

L0，L1，L2，核范数等机器学习中的规则化范数(L0, L1, L2, 核范数) 最优化之Robust PCA 为什么核范数能凸近似矩阵的秩？

VC维（Vapnik-Chervonenkis Dimension）

一致限(the union bound)

令 $A_1,A_2,\ldots,A_k$ 为k个不同的事件（不一定相互独立），那么有：

p(A_1 \cup A_2 \cup \ldots \cup A_k) \le p(A_1) + p(A_2) + \ldots + p(A_k)

一致限说明：k个事件中任一个事件发生的概率小于等于这k个事件发生的概率和（等号成立的条件为这k个事件相两两互斥）。

Hoeffding 不等式（Hoeffding inequality）

Hoeffding不等式是关于一组随机变量均值的概率不等式。如果X1,X2,⋯,Xn为一组独立同分布的参数为p的伯努利分布随机变量，n为随机变量的个数。定义这组随机变量的均值为：

\overline X = \frac {X_1 + X_2 +\cdots+ X_n}{n} \\ \text{则Hoeffding不等式：} P(|\overline X - E(\overline X)| \ge \delta) \le exp(-2\delta^2n) \\ \delta \gt 0 , \overline X \text{是样本的期望} , E(\overline X) \text{总体真实的期望} \\ \text{当n逐渐变大时，不等式的UpperBound越接近0，所以样本期望越来越接近总体期望}

要先介绍分散(shatter)的概念：对于一个给定集合S={x1, ... ,xd}，如果一个假设类H能够实现集合S中所有元素的任意一种标记方式，则称H能够分散S。这样之后才有VC维的定义：H的VC维表示为VC(H) ，指能够被H分散的最大集合的大小。若H能分散任意大小的集合，那么VC(H)为无穷大。在《神经网络原理》中有另一种记号：对于二分总体F，其VC维写作VCdim(F)。

如果某函数的VC维无穷大，也就意味着，任意多个点无论怎样标注都能将其打散。例如sin(ax)。它可以将任意多样本的任意标注情况精确分开，即在训练集上达到100%的分类正确率。

注意，在假设空间H中，往往有多个假设函数(甚至于无穷多个)，这里我们先假定H中有k个假设函数。