准备知识
training error/empirical risk/empirical error:
给定训练集 $S = \{(x^i, y^i)\} \quad i = 1, \ldots, m$, $(x^i, y^i)$服从独立同分布 $D$中,对于假设(hypothesis)h,我们定义训练误差/经验风险/经验误差为:
generalization error:
表示从分布D中随机抽取样本(x,y),h讲其分类错误的概率
empirical risk minimization
经验误差最小化是
其中H是hypothesis class
The union bound:
令 $A_1, \ldots, A_k$ 是k个事件，那么
Hoeffding inequality/Chernoff bound:
令 $Z_1, \ldots , Z_m$ 是m个服从 $Bernoulli(\phi)$ 的独立同分布变量，其均值 $\hat\phi = \frac{1}{m}\sum_{i=1}^m Z_i$，那么对于任意给的的 $\gamma \gt 0$，有
tradeoff between “Bias” and “Variance”
有限假设空间
$H = \{h_1, \ldots, h_k\}$ 包含k个hypotheses, $h_i : X \rightarrow \{0, 1\}$
对于固定的 $h_j$,我们定义 $Z_i = 1\{h_j(x^i) \neq y^i\}$, 由于 $(x^i, y^i)$是服从概率分布D的IID,那么 $Z_i$ 也是IID,那么
由Hoeffding不等式得
设事件 $A_j = \lvert \varepsilon(h_j) - \hat\varepsilon(h_j) \rvert \gt \gamma$,那么 $P(A_j) \le 2e^{-2\gamma^2 m}$
$\forall h_j \in H, \lvert \varepsilon(h_j) - \hat\varepsilon(h_j) \rvert \le \gamma$称为uniform convergence
推论:
至少 $1-\delta$正确的概率,我们可以说 $\forall h_j \in H, \lvert \varepsilon(h_j) - \hat\varepsilon(h_j) \rvert \le \gamma$ ,当 $m \ge \frac{1}{2\gamma ^2}\log{\frac{2k}{\delta}}$ 这也叫做”sample complexity”
至少 $1-\delta$正确的概率,我们有 $\forall h_j \in H, \lvert \varepsilon(h_j) - \hat\varepsilon(h_j) \rvert \le \sqrt {\frac{1}{2m}\log{\frac{2k}{\delta}}}$
假设uniform convergence成立,那么
推得定理如下
Theorem:
令 $\lvert H \rvert = k$, 给定任意的 $m, \delta$, 那么至少 $1 - \delta$正确的概率,我们有
Sample complexity bound:
令 $\lvert H \rvert = k$, 给定任意的 $\gamma, \delta$, 那么为了至少 $1 - \delta$正确的概率, $\varepsilon(\hat h) \le (\underset{h \in H}{min}\;\varepsilon(h)) + 2\gamma$ 成立,m需要满足:
无限假设空间
给定集合 $S = \{x^1, \ldots, x^d\}$，我们说H shatters S当且仅当对于S标签的任意赋值 ${y^1, \ldots, y^d}$ , $\exists h \in H s.t. h(x^i) = y^i \; for \; all \; x^i$
给定假设类H，定义H的 VC(Vapnik-Chervonenkis) dimension, VC(H)是能被H shatters的最大集合的大小。
Theorem:
给定H, 令 $d = VC(H)$ ,那么有至少 $1 - \delta$的概率，我们有 $\forall h \in H$,
那么有至少 $1- \delta$的概率，我们有
Corollary:
为了，$\lvert \varepsilon(h) - \hat \varepsilon(h) \rvert \le \gamma \; \forall h \in H$ (因此 $\varepsilon(\hat h) \le \varepsilon(h^* ) + 2\gamma$)有至少 $1- \delta$正确的概率,那么需要 $m = O_{\gamma, \delta}(d)$
Model Selection
cross validation
- hold-out/simple cross validation
- k-fold cross validation
- leave-one-out cross validation
Feature Selection
- wrapper model feature selection
foward selection
backward selection - filter feature selection
计算互信息 $MI(x_i, y) = \underset{x_i \in \{0,1\}}{\sum}\underset{y \in \{0,1\}}{\sum}\; p(x_i, y)\log{\frac{p(x_i, y)}{p(x_i)p(y)}}$ or $KL(p(x_i,y)\lVert p(x_i)p(y))$ 选取top K个
MLE & MAP
maximum likelihood
看成固定的未知参数
maximum a posteriori
看成随机变量
当预测时
取
但是 $p(\theta \mid S)$ 难以计算
