泛化误差上界

机器学习最终目的不是最小的训练误差，而需要看泛化误差；
泛化误差： $E_{out}-E_{in}$ 即从训练集泛化至训练集外的过程中的误差，或者直接用 $E_{out}$ 来表示泛化误差也行；

Hoeffding 不等式

由大数定理得到：
$P[|E_{out}-E_{in}|> \epsilon<=2Me^{-2\epsilon^2N}],\forall \epsilon>0$
可以看出，当N足够大时，泛化误差和训练误差会非常接近；但这是单一假设函数的情况，实际上，机器学习的假设函数是从很大的集合中选出来的：

M表示假设函数集合的大小

一般来说，机器学习中的M的值很大。因此，右边不等式值也比很大；

有效假设函数与VC维

当多个假设函数在数据集上得到的分类结果相同时 (比如, 对三个数据点, 分类结果都是”正正负”), 有效数量为 1.
就二分类问题而言:假设函数”有效”数量的上限是 $2^N$ , 达到这个上限时, 意味着假设函数集合 H 能够穷尽 N 个数据点分类的所有可能性 (这时可以说 H shatter 了数据点).

VC 维 (VC dimension), 即: 一个假设函数集合 H 最多能 shatter 多少数据点.假设函数集合可以理解为同一函数模型的不同参数组合组成的集合；
以二维平面的感知机为例: 对三个不共线的点, 它总是能给出所有的分类可能, 但对四个点就办不到了. 因此二维感知机的 VC 维是 3. 更一般地, d 维感知机的 VC 维等于 d+1. VC 维可以看做对模型有效参数数量或自由度的一种度量.
可以看出影响泛化误差的两个因素: 数据量和模型复杂度. 数据量不必多说, 自然多多益善. 模型复杂度的影响更微妙一些: 当复杂度增加时, 一般 $E_{in}$ 会减小, 而泛化误差 Ω 项会增大; 为了得到最优的 $E_{out}$ , 需要两者之间达到一种平衡.

https://sunoonlee.github.io/2017/07/generalization-error-bound/

生成模型与判别模型

生成模型：学习x,y的联合概率分布p(x,y),从而来得到p(y|x).，收敛速度快，存在隐变量时仍能使用；
判别模型：直接学习决策函数f(x)或者p(y|x),可以对数据进行抽象和使用特征；

期望风险与经验风险：

期望风险：模型关于联合分布的期望损失；
$R(f) = E[L(Y,f(x))] = \int_{XY} L(y,f(x))p(x,y)dxdy$
经验风险：模型关于训练样本集的平均损失；
$R(f) = 1/N\sum L(y_i,f(x_i))$

感知机（线性二分类模型）

输出为{+1，-1}二值，f(x) = sign(wx+b)
损失函数的一个自然选择是误分类点的总数，但是，这样的损失函数不是参数w,b的连续可导函数，不易优化，在这里采用误分类点到超平面S的总距离。
$-\frac{1}{||w||}|w*x_0+b|$
感知机的经验风险函数：
$L(w,b) = -\sum_{x_i\in{M}}y_i(w*x_i+b)$
上式很容易求导，采用随机梯度下降法优化；

感知机的对偶形式

优点：输入特征比较高时，能够利用Gram矩阵可以简化运算。
在更新感知机的参数时有(只有分错时，即 $y_i*(w x_i+b)<0$ 时才跟新):
$w \longleftarrow w + \eta y_ix_i$
$b \longleftarrow b + \eta y_i$
可见，w和b可以写成所有的 $x_i$ 和 $y_i$ 加上不同的权重组合的形式；
$w = \sum_{i = 1}^{N}\eta n_ix_iy_i$
$b = \sum_{i = 1}^{N}\eta n_iy_i$
这里的 $n_i$ 实际上是i实例由于分错更新的次数， $n_i$ 越大，说明其离超平面越近，越难以分对;

更新条件：
$y_i(\sum_{j}^{N}\eta n_jy_jx_jx_i+b)<=0$
$G = [x_ix_j]_{nn}$ Gram矩阵可以提前计算出来，原来的w*x_i的形式如果x_i的维度高，则该内积计算耗时;
更新，实际上只更新 $n_i=n_i+1$ 就行。

从二分类问题来看为什么要使用sigmoid函数

实际上，可以将二分类模型未经过sigmoid函数的输出理解为一个事件发生的几率： $\frac{p}{1-p}$ ,，为了让其更平滑，取个对数有： $wx+b = f(p) = log(\frac{p}{1-p})$ 即模型的输出 $wx+b$ 是关于该事件的几率，即概率P的函数 $f(p)$ ，更确切的说，是长成 $log(\frac{p}{1-p})$ 这个样子的函数；取反函数，可得 $e^{(wx+b)} = \frac{p}{1-p}$ ,可得 $p = \frac{1}{1+e^{-(wx+b)}}$