Inequality

信息熵不等式

K-L距离$D(P||Q)$; 联合熵$H(X,Y)$, 互信息$I(X,Y)$, 条件熵$H(X|Y)$; Han不等式.

基本不等式

Markov不等式: 给定$\epsilon>0$, X是一个非负随机变量, 有:
$$Pr[X\geq\epsilon]\leq\frac{E[X]}{\epsilon}$$. 另由该不等式可以直接导出Chebyshev不等式.

Jensen不等式: 对凸函数$f$, 有:
$$E[f(X)]\geq f(E[X])$$

Chernoff不等式: $X_1,…,X_n$是n独立同分布随机变量且满足$X_i\in[\alpha,\beta]$, 令$\bar X=\sum_{i=1}^nX_i/n$, 有:
$$Pr[\bar X-\mu\geq\epsilon]\leq exp(\frac{-2n\epsilon^2}{(\beta-\alpha)^2})$$, 该不等式可以从Markov不等式出发, 并利用Moment-Generating-Function证明.

McDiarmid不等式: $X_1,…,X_m$是空间$\cal X$的m个独立随机变量, 令$f:\cal X^m\rightarrow\mathbb R$是一个关于$X_1,…,X_m$的实值函数, 并满足对任意的$X_1,…,X_m, X_i^{‘}\in\cal X$, 都有:
$$|f(X_1,…,X_i,…,X_m)-f(X_1,…,X_i{‘},…,X_m)|\leq c_i$$, 那么对任意$\epsilon>0$, 有:
$$Pr[f(X_1,…,X_m)-E[f(X_1,…,X_m)]\geq\epsilon]\leq exp(-2\epsilon^2/\sum_{i=1}^mc_i^2)$$.

AdaBoost

集成学习是一类著名机器学习方法, 通过使用一系列学习器进行学习, 并使用某种规则将各个学习器进行整合从而获得比单个学习器显著优越的泛化性能, 常用方法包括Boosting, Bagging, random forest等, 其中, Boosting族算法最著名的代表是AdaBoost. 从基学习器的线性组合去优化指数损失函数出发, 可以直接得到AdaBoost算法中的权重更新公式.

若从VC维角度去分析AdaBoost的泛化性, 只会得到, 随着迭代轮数的增加, AdaBoost所产生的学习器函数空间复杂度将增加, 从而导致AdaBoost学习方法过拟合风险. 事实并非如此, 即使训练轮数增加, 仍不易陷入过拟合, 甚至当训练错误率为零时还可以降低泛化错误率, 为解释这一现象, 需要新的理论: 著名的间隔理论. 事实上, AdaBoost优化的是间隔分布, 当轮数增加, 泛化错误率越小.

Consistency

贝叶斯(最优)分类器和贝叶斯风险分别为:
$$g^(x)=\mathbb I[\eta(x)>1/2]\qquad R^=E_{x\sim\cal D_{\cal X}}[min{\eta(x),1-\eta(x)}]$$

称学习方法F满足一致性(贝叶斯一致性, 弱一致性), 如果有:
$$E_{S_n}[R(F_{S_n})]\rightarrow R^*$$, 当$n\rightarrow\infty$. 一致性反映了学习函数的错误率随样本的增加而趋于贝叶斯错误率.

替代损失函数一致性

对于常见的二分类问题, 由于0-1损失函数是非凸与不连续的, 直接优化是一个NP-hard问题, 从而导致计算上不可行. 在实际的算法设计过程中, 一般会对分类错误率损失函数进行凸放松, 即对$\mathbb I[\cdot]$的上界进行凸放松. e.g. AdaBoost算法优化指数损失函数$l(g(x),y)=exp(-yg(x))$, SVM采用hinge损失函数等等. 为此引入新的函数$\phi:\cal R\rightarrow\cal R$, 使得$l(g(x),y)=\phi(yg(x))$. 这里称函数$\phi$为替代损失函数, 一般是连续的凸函数.

对于给定数据集和替代损失函数, 我们可以优化替代损失函数在数据集上的平均损失, 由于$\phi$一般情况下是连续的凸函数, 因此各种优化技术可用于上述替代损失函数. 从本质上看, 这种方法可被看作随机近似最小化替代损失函数期望风险:
$$R_\phi(g)=E_{(X,Y)\sim\cal D}[\phi(Yg(X))]$$

常见的替代损失函数如下几种:

最小二乘损失函数(最小二乘SVMs方法) $\phi(t)=(1-t)^2$
Hinge损失函数(SVMs方法) $\phi(t)=max(0, 1-t)$
平方Hinge损失函数(平滑SVMs方法) $\phi(t)=(max(0,1-t))^2$
指数损失函数(Boosting方法) $\phi(t)=exp(-t)$
对数损失函数(LogisticRegression方法) $\phi(t)=log(1+exp(-t))$

替代损失函数一致性问题: 通过优化替代损失函数所学得的学习器$\hat g_1,\hat g_2,…,\hat g_n,…$, 如果$R_\phi(\hat g_n)\rightarrow R_\phi^\quad(n\rightarrow\infty)$, 则有$R(\hat g_n)\rightarrow R^$, 称该替代损失函数与0-1分类损失函数具有一致性.
注意: 这里一致性不仅仅包含在最优时是一致的, 还包括一种趋近的性质. 可以证明, 上述几种损失函数都具有这样的一致性.

优化AUC替代函数一致性

类似于0-1损失最优函数和错误率, 可以定义AUC最优函数和错误率以及相应的一致性定义. 下面直接给出结论: 若函数$\phi:\mathbb R\rightarrow\mathbb R$是可导的, 非单调递减的凸函数, 并且满足$\phi{‘}(0)<0$, 那么替代损失函数$\Phi(g,X,X^{‘})=\phi(g(X)-g(X^{‘}))$与AUC具有一致性.

由此可以得到, 指数替代函数, 对数替代函数, 平方Hinge替代函数与AUC具有一致性, 而Hinge替代函数在t=1不可导, 不能得到结论.