PAC学习框架

几个重要不等式
1. 马尔科夫不等式：设X为非负随机变量，满足\(E[X]< \infty\), 则\[P(X\ge t\cdot E[X])\le\frac 1 t,\forall t > 0.\]
2. 切比雪夫不等式：设 \(Var[X]<\infty\)，标准差 \(\sigma_X=\sqrt{Var[X]}\)，则\[P(|X-E[X]|\ge t\sigma_X)\le\frac{1}{t^2},\forall t > 0.\]
3. Chernoff界：对任意 \( t>0, \epsilon>0,\)\[P(X\ge\epsilon) \le e^{-t\epsilon}E[e^{tX}]\]
证明：因为\(P(X\ge \epsilon) = P(e^{tX}\ge e^{t\epsilon})\)，由马尔可夫不等式知\(P(e^{tX}\ge e^{t\epsilon})\le \frac{1}{e^{t\epsilon}}E[e^{tX}]\)，代入即得。

4. Hoeffding引理：设\(E[X]=0, a\le X\le b\). 则\[E[e^{tX}]\le \exp \{\frac{t^2(b-a)^2}{8}\}\]

5. Hoeffding不等式：设\(X_1,\cdots, X_m\)为一组独立随机变量，满足\(a_i\le X_i\le b_i\).
令\(S=\sum\limits_{1}^m X_i\)，则对任意\(\epsilon > 0\)，有
(1) \[P(S-E[S]\ge\epsilon)\le \exp\{-\frac{2\epsilon^2}{\sum\limits_{i=1}^m (b_i-a_i)^2}\}.\](2)\[P(S-E[S]\le - \epsilon)\le \exp\{-\frac{2\epsilon^2}{\sum\limits_{i=1}^m (b_i-a_i)^2}\}.\]推论(1) \[P(|S-E[S]|\ge\epsilon)\le 2\exp\{-\frac{2\epsilon^2}{\sum\limits_{i=1}^m (b_i-a_i)^2}\}.\](2) 如果\(b_i-a_i=1\)，则\[P(\frac{|S-E[S]|}{m}\ge\epsilon)\le 2\exp\{-{2m\epsilon^2}\}.\]
证明：由Chernoff界，\(P(S-E[S]\ge\epsilon)\le e^{-t\epsilon} E[e^{t(S-E[S])}]\)。
利用独立性展开\(E[e^{t(S-E[S])}]=\prod\limits_{i=1}^m E[e^{t(X_i-E[X_i])}]\)。
由Hoeffding引理得\(E[e^{t(X_i-E[X_i])}]\le \exp\{\frac{t^2(b_i-a_i)^2}{8}\}\)。
最后得到一关于\(t\)的二次函数。选择\(t=\frac{4\epsilon}{\sum(b_i-a_i)}\)即得。

PAC学习模型
设有输入空间\(\mathcal X\)有隐含分布\(\mathcal D\)，标签集合\(\mathcal Y = \{0,1\}\)。设概念\(c:\mathcal X\to \mathcal Y\)是我们希望学习的目标，所有可能学习的概念集合为一假设空间\(H\)，对\(H\)中每个假设\(h:\mathcal X\to\mathcal Y\)，其泛化误差定义为\[R(h) = P_{x\sim\mathcal D}(h(x)\ne c(x))=E_{x\sim\mathcal D}\mathbb I (h(x)\ne c(x)).\]
对于样本集\(S=\{x_i\}_{i=1}^m\)，\(h\)的经验误差（经验风险）定义为\[\hat R(h) = \frac{1}{m}\sum\limits_{i=1}^m \mathbb I (h(x)\ne c(x)).\]
PAC(Probably Approximately Correct)可学习：称目标概念类\(C\)是PAC可学习的，如果存在一个学习算法\(\mathcal A\)和一个多项式函数\(p(\cdot,\cdot,\cdot,\cdot)\)，满足：对任意的\(\epsilon<1, \delta >0,\mathcal X\)上任一分布\(\mathcal D\)，任一目标概念\(c\in C\)，任一样本容量\(m\ge p(\frac 1 \epsilon,\frac 1 \delta, size(x) ,size(c))\)成立：\[P_{S\sim\mathcal D^m}(R(h_S)\le \epsilon )\ge 1-\delta\]

    所属分类：机器学习     发表于2022-06-07