泛化误差上界
- 机器学习最终目的不是最小的训练误差，而需要看泛化误差；
- 泛化误差：
即从训练集泛化至训练集外的过程中的误差，或者直接用
来表示泛化误差也行；
Hoeffding 不等式
由大数定理得到：
可以看出，当N足够大时，泛化误差和训练误差会非常接近；但这是单一假设函数的情况，实际上，机器学习的假设函数是从很大的集合中选出来的：
一般来说，机器学习中的M的值很大。因此，右边不等式值也比很大；
有效假设函数与VC维
当多个假设函数在数据集上得到的分类结果相同时 (比如, 对三个数据点, 分类结果都是”正正负”), 有效数量为 1.
就二分类问题而言:假设函数”有效”数量的上限是 , 达到这个上限时, 意味着假设函数集合 H 能够穷尽 N 个数据点分类的所有可能性 (这时可以说 H shatter 了数据点).
- VC 维 (VC dimension), 即: 一个假设函数集合 H 最多能 shatter 多少数据点.假设函数集合可以理解为同一函数模型的不同参数组合组成的集合；
- 以二维平面的感知机为例: 对三个不共线的点, 它总是能给出所有的分类可能, 但对四个点就办不到了. 因此二维感知机的 VC 维是 3. 更一般地, d 维感知机的 VC 维等于 d+1. VC 维可以看做对模型有效参数数量或自由度的一种度量.
- 可以看出影响泛化误差的两个因素: 数据量和模型复杂度. 数据量不必多说, 自然多多益善. 模型复杂度的影响更微妙一些: 当复杂度增加时, 一般
会减小, 而泛化误差 Ω 项会增大; 为了得到最优的
https://sunoonlee.github.io/2017/07/generalization-error-bound/
生成模型与判别模型
- 生成模型：学习x,y的联合概率分布p(x,y),从而来得到p(y|x).，收敛速度快，存在隐变量时仍能使用；
- 判别模型：直接学习决策函数f(x)或者p(y|x),可以对数据进行抽象和使用特征；
期望风险与经验风险：
- 期望风险：模型关于联合分布的期望损失；
- 经验风险：模型关于训练样本集的平均损失；
感知机（线性二分类模型）
- 输出为{+1，-1}二值，f(x) = sign(wx+b)
- 损失函数的一个自然选择是误分类点的总数，但是，这样的损失函数不是参数w,b的连续可导函数，不易优化，在这里采用误分类点到超平面S的总距离。
- 感知机的经验风险函数：
- 上式很容易求导，采用随机梯度下降法优化；
感知机的对偶形式
优点：输入特征比较高时，能够利用Gram矩阵可以简化运算。
在更新感知机的参数时有(只有分错时，即时才跟新):
可见，w和b可以写成所有的和
加上不同的权重组合的形式；
这里的实际上是i实例由于分错更新的次数，
越大，说明其离超平面越近，越难以分对;
- 更新条件：
Gram矩阵可以提前计算出来，原来的w*x_i的形式如果x_i的维度高，则该内积计算耗时;
更新，实际上只更新就行。
从二分类问题来看为什么要使用sigmoid函数
实际上，可以将二分类模型未经过sigmoid函数的输出理解为一个事件发生的几率：,，为了让其更平滑，取个对数有：
即模型的输出
是关于该事件的几率，即概率P的函数
，更确切的说，是长成
这个样子的函数；取反函数，可得
,可得
SVM
SVM的解释可以有两个角度：
- 可以从带约束的最大化间隔理解，以拉格朗日算法来求解；
- 从合页损失函数来理解，直接使用梯度下降求解；
Hinge损失函数
解释教程[svm 比较好的]https://wizardforcel.gitbooks.io/dm-algo-top10/content/svm-1.html
关于模型的误差来源
简单的模型B大，V小，复杂的模型b小，V大；
-
Bias和Variance
image.png
ID3,C4.5,CART决策树，
https://blog.csdn.net/u010089444/article/details/53241218
CART进行回归
https://www.ibm.com/developerworks/cn/analytics/library/machine-learning-hands-on5-cart-tree/index.html
