机器学习知识梳理

没有深度学习的内容

泛化能力相关理论
——机器学习的理论根基
- 泛化误差与经验误差的关系
  首先介绍 Hoeffding 不等式: 对服从同一伯努利分布 $\text{Bernoulli}(\phi)$ 的 $m$ 个独立变量 $Z_i, \ldots, Z_m$ 有 $P(|\phi-\hat{\phi}|>\gamma)\le 2\exp(-2\gamma^2m)$ ，其中 $\hat{\phi} = \frac{1}{m}\sum_{i=1}^mZ_i, \gamma>0$ 。
  也就是说对于投篮命中率号称 $\phi$ 的选手，我们只要让他多投几次，就知道他到底几斤几两。
  下面考虑机器学习的一般情景，也就是有监督学习：
  即有服从某种神秘分布 $D$ 的输入输出对，或者说特征和目标值，也就是 $(x,y) \sim D$ 。
  我们想要拥有这种能力：在给某输入 $x$ 时准确预测对应的输出 $y$ 。
  我们手边有这么一个观察到的集合 $S = \{(x^{i},y^{i});i=1, \ldots, m\}$ ，也就是训练集，这里不妨假设观察到的各实例间是相互独立的。
  也许是经验，也许是调参，也许是有人不放弃，我们会选择一种模型 $h_{\theta}$ ，其中 $\theta$ 是模型的可训练参数。这时输入 $x$ , 输出 $h_\theta(x)$ 。
  注意不同的参数对应着不同的模型实例，所有这些模型实例构成一个集合：模型空间 $H = \{h_\theta; \forall \theta\}$ 。
  本小节主角登场：
  经验误差 也称训练误差 $\hat{\varepsilon}(h_\theta) = \frac{1}{m} \sum_{i=1}^m \mathbf{1}\{h_\theta(x^i)\ne y^i\}$ , 它描述了模型对训练集的拟合程度。
  泛化误差 $\varepsilon(h_\theta) = P_{(x,y)\sim D}(h_\theta(x)\ne y)$ ,它描述了对真实分布 $D$ 的拟合程度。
  很显然我们的目标是最小化泛化误差，可是并没有办法。( $D$ 是未知的）
  实际上我们通常采用经验风险最小化 的策略，也就是说选择 $\hat\theta = \arg\min_\theta \hat\varepsilon(h_\theta)$ 。而不是 $\theta^* = \arg \min_\theta \varepsilon(h_\theta)$ 。
  换句话说，虽然是 $\varepsilon(h_{\theta^*})$ 是我们能力的上限，但是 $\varepsilon(h_\hat\theta)$ 才是我们实际的表现。
  由此引出两个重要的概念：
  偏差： $\varepsilon(h_{\theta^*})$ ，那个神秘的最强王者。我们唯一可以确定的是他来自 $H$ 。由此可以得到推论：模型空间越大（更准确的说是表达能力越强），偏差越小（与中国最强射手不会比上海最强射手弱一个道理）。
  方差： $\theta^*$ 虽强，可我们用的是 $\hat\theta$ , 很自然地，我们转而关心 $\varepsilon(h_{\theta^*})$ 和 $\varepsilon(h_\hat\theta)$ 的关系：我们离我们能力的上限有多远？
  下面来回答这个问题。
  令 $Z = \mathbf{1}\{h_\theta(x)\ne y\}$ ，代入 Hoeffding 不等式中得到：
  $P(|\varepsilon(h_\theta)-\hat{\varepsilon}(h_\theta) >\gamma)\le 2\exp(-2\gamma^2m)$
  由下面的推导
  $\begin{split} P(\forall h\in H, |\varepsilon(h)-\hat\varepsilon(h)|\le \gamma) &= 1 -P(\exists h\in H, |\varepsilon(h)-\hat\varepsilon(h)|>\gamma) \\ &\ge 1- \sum_{i=1}^{|H|} P(|\varepsilon(h_i)-\hat\varepsilon(h_i)|>\gamma) \\ &\ge 1-2|H|\exp(-2\gamma^2 m) \end{split}$
  稍加变化，得到结论
  $P\left(\forall h \in H, |\varepsilon(h)-\hat\varepsilon(h)|\le \sqrt{\frac{1}{2m}\log\frac{2|H|}{\delta}}\right) \ge 1- \delta$
  
  故存在至少 $1-\delta$ 的概率有
  即
  $\varepsilon(h_{\hat\theta}) -\varepsilon(h_{\theta^*})\le2\sqrt{\frac{1}{2m}\log\frac{2|H|}{\delta}}$
  
  $2\sqrt{\frac{1}{2m}\log\frac{2|H|}{\delta}}$ 就是方差，这个公式揭示了方差和偏差的矛盾关系。
  有关泛化误差的许多结论都可以从这个公式中看出来，就不多说了。
- 偏差和方差的另一种解释
  上面的推导能有效地对单一模型（在确定的模型空间 $H$ 进行一次搜索得到 $h_\hat\theta$ ）的泛化能力进行解释。
  我们还可以从另一个角度定义偏差和方差，对模型的泛化能力作出解释。
  假设存在某未知函数 $f$ ，观测到训练集 $S = \{(x^{i},y^{i});i=1, \ldots, m\}$ ，现要寻找拟合 $f$ 的一个函数 $h$ 。
  我们用均方差来衡量 $h$ 的拟合程度： $E[(f-h)^2]$
  有如下推导
  其中的 noise 是函数 f 本身的性质，可以看作一个常量；variance 和 bias 即方差和偏差，可以看出： $h$ 越复杂，方差越大，同时由于可以对训练数据的刻画更细致，偏差减小。
一些理论坚实的模型
- Bagging and Boosting
- 决策树
- 逻辑斯蒂回归
- 最大熵模型
- 支持向量机
- EM算法
- 主元成分分析