0. 符号假设

1. When Can Machine Learn?

1.1

1.2 Learning to Answer Yes-­No

本节主要介绍了感知机算法，它在一定条件下可以使得 $\textbf{E}_{in} \approx 0$ (在数据集上的误差近似为0)。

感知机学习算法 $\mathcal{A}$ 通过线性可分的数据 $\mathcal{D}$ 以及感知机 $\mathcal{H}$ 获得假设 $g$

• 感知机的假设空间：定义在 $\mathbb{R}^d$ 上的一条直线或超平面
• 感知机算法可以不断纠正错误并改进
• 感知机的分类正确性保证：数据是线性可分的
• 无法分类的数据：存储效果最好的直线

1.3 Types of Learning

本节主要介绍机器学习的分类

• 按输出空间 $\mathcal{Y}$ 分类：分类、回归、结构化学习
• 按数据标签 $y_n$ 分类：监督学习、半监督学习、无监督学习、强化学习
• 按不同的学习方式分类：批量学习、在线学习、主动学习
• 按输入空间 $\mathcal{X}$ 分类：具体意义的数据、原始数据、抽象数据

1.4 Feasibility of Learning

本节主要介绍机器学习的可能性

• NFL定理：面对所有的问题，没有一种算法能说比另一种算法更好

• 验证一个固定假设 $h$ 的 $E_{in}$ 和 $E_{out}$ 是否PAC

  • 机器能够学习的必要条件：样本满足独立同分布假设 (每次抽样之间相互独立，样本服从同一分布)

  • $E_{in}$ 为抽样样本（数据集）内所有数据中 $h(\vec{x}) = f(\vec{x})$ 的概率，
    $E_{out}$ 为抽样样本外所有数据中 $h(\vec{x}) = f(\vec{x})$ 的概率

    ($E_{in}(h) = \frac{1}{N} \sum\limits_{n=1}^{N} \mathbb{I}[h(\vec{x}) \neq y_n]$、
    $E_{out} = \mathop{\varepsilon}\limits_{\vec{x} \sim{P}} \mathbb{I}[h(\vec{x}) \neq f(\vec{x})]$)

  • Hoeffding 不等式：$P[\lvert E_{in} - E_{out} \rvert > \epsilon] \leq 2exp(-2 \epsilon^2 N)$

    (说明了只要样本数 $N$ 够大，$E_{in}$ 和 $E_{out}$ 相差的很大概率会很小，也就可以用 $E_{in}$ 来估计 $E_{out}$)

  • 上述 Hoeffding 不等式说明了 $E_{in}$ 和 $E_{out}$ 是 PAC(概率近似相等) 的

• 在 $E_{in}(h)$ 足够小且 $\lvert \mathcal{H} \rvert$ 有限的情况下，学习有可能能实现了

  • 坏数据集 (BAD $\mathcal{D}$)：使得假设 $h$ 的 $E_{in}$ 和 $E_{out}$ 相差很大的数据集

  • $P_{\mathcal{D}}(BAD \; \mathcal{D}) \leq P(BAD \; \mathcal{D} \; for \; h_1) + … + P(BAD \; \mathcal{D} \; for \; h_M)$

    $P_{\mathcal{D}}(BAD \; \mathcal{D}) \leq 2exp(-2 \epsilon^2 N) + … + 2exp(-2 \epsilon^2 N)$

    $P_{\mathcal{D}}(BAD \; \mathcal{D}) \leq 2Mexp(-2 \epsilon^2 N)$

    也就是说只要 $N$ 足够大，$\lvert \mathcal{H} \rvert$ 有限的情况下。
    不管使用什么算法 $\mathcal{A}$ 都能够使得 $E_{in}$ 和 $E_{out}$ PAC，

    如果 $\mathcal{A}$ 可以找到 $g$ 使 $E_{in}(g) \approx 0$ 那么PAC可以保证 $E_{out}(g) \approx 0$

2. Why Can Machines Learn?

2.1 Training VS Testing

本节主要介绍假设数量 $M = \infty$ 时，机器学习是否有可能性

• $M$ 过小 $E_{in}(g) \approx 0$ 难以实现(选择过少)，$M$ 过大出现坏样本的概率又显著增加，
  导致 $E_{in}(g)$ 和 $E_{out}(g)$ 无法PAC
• 按照对数据集中样本点的分类结果可以将无穷种假设分成 $effective(N)$ 种，
  如果 $effective(N) << 2^N$ ，机器学习是有可能的
• 成长函数 $m_{\mathcal{H}}(N)$ 是含N个数据点的数据集最多的假设种类数
  ($m_{\mathcal{H}}(N) = \mathop{max}\limits_{\vec{x_1},…,\vec{x_N} \in \mathcal{X}} \lvert \mathcal{H}(x_1,…,x_N) \rvert$)
• $m_{\mathcal{H}}(N) = O(N^{k-1})$ ($k$ 是break point，也就是 $k$ 个样本点类别的 $2^k$ 种情况
  都能被 $\mathcal{H}$ 中其中一个假设全部正确分类)

2.2 Theory of Generalization

• $N > k$ 时，$m_{\mathcal{H}}(N)$ 会比 $2^N$ 小的多

• Bounding Function $B(N,k)$ 是 $m_{\mathcal{H}}(N)$ 的上限，以下是它的一些性质:

  • $k = 1$ 时，$B(N,1) = 1$

  • $N < k$ 时，$B(N,k) = 2^N$ (相当于没有限制)

  • $N = k$ 时，$B(N,k) = 2^k - 1$ (刚出现不能被覆盖的分类情况)

• 通过递推得到 $B(N,k)$ 其他情况下的一些性质:

  • 把 $N$ 个样本可以被覆盖的二分情况再分为两类：第一类每两种情况的 $x_1$ 到 $x_{k-1}$ 的类别完全相同，$x_k$ 的类别不同且成对，其他为第二类

  • 第一类情况个数记为 $\alpha$，第二类为 $\beta$，存在以下关系：$B(N,k) = 2\alpha + \beta$、
    $\alpha + \beta \leq B(N-1,k)$、$\alpha \leq B(N-1,k-1)$

  • 因此可以得到 $B(N,k) = B(N-1,k) + B(N-1,k-1)$ (取等证明略)

  • 因此 $B(N,k) = \sum\limits_{i=0}^{k-1} C_i^N$，最高次项为 $N^{k-1}$，所以成长函数 $m_{\mathcal{H}}(N)$ 是 $poly(N)$ 的

• 用成长函数 $m_{\mathcal{H}}(N)$ 替代 $M$ 证明 $E_{in}$ 和 $E_{out}$ 是PAC的

  • 证明略

  • VC bound：$P_{\mathcal{D}}(\lvert E_{in} - E_{out} \rvert > \epsilon) \leq 4m_{\mathcal{H}}(N)exp(-\frac{1}{8} \epsilon^2 N)$

2.3 The VC Dimension

本节介绍VC维的意义及其与泛化能力的关系

• VC维的定义：使得 $m_{\mathcal{H}}(N) = 2^N$ 成立的最大N，记为 $d_{VC}$

  • 机器学习的条件：1、$m_{\mathcal{H}}(N)$ 有间断点k；2、样本数N足够大(这两点保证 $E_{out}$ 和 $E_{in}$ PAC)；
    3、合适的算法 $\mathcal{A}$ (保证 $E_{in} \approx 0$)

  • $d_{VC}$ 有限时，$E_{out}$ 和 $E_{in}$ 是PAC的

• $d_{VC} = d+1$

  • 先证明 $d_{VC} \geq d+1$，由于 $X\vec{w}_{d+1} = \vec{y}_{d+1}$ 可得 $\vec{w} = X^{-1}\vec{y}$
    (X有 $d+1$ 个维度和 $d+1$ 个样本).

    因此对每一种 $\vec{y}$，$\vec{w}$ 唯一确定. $\vec{w}$ 的所有情况也就可以覆盖 $\vec{y}$ 的所有情况

  • 再证明 $d_{VC} \leq d+1$，也就是对 $d+2$ 个样本 $\vec{w}$ 的所有情况不可以覆盖 $\vec{y}$ 的所有情况

    由于 $\vec{x}_{d+2}$ (第 $d+2$ 个样本) 能被表示成前 $d+1$ 个样本的线性组合.

    也就是：$\vec{x}_{d+2} = a_1\vec{x}_{1} + … + a_{d+1}\vec{x}_{d+1}$

    因此存在 $\vec{w}$ 使得 $\vec{x}_{d+2}\vec{w} = a_1\vec{x}_{1}\vec{w} + … + a_{d+1}\vec{x}_{d+1}*\vec{w}>0$

    这种情况下 $\vec{x}_{d+2}$ 一定是正类. $\vec{w}$ 的所有情况不能覆盖 $\vec{y}$ 的所有情况

• $d_{VC}$ 的物理意义：假设空间的自由度。所以 $M$ 和 $d_{VC}$ 是成正比的

• $d_{VC}$ 和泛化能力、样本复杂度以及模型复杂度的关系

  • $E_{out}(g) \leq E_{in}(g) + \sqrt{\dfrac{8}{N} \ln{\dfrac{4(2N)^{d_{VC}}}{\delta}}}$

  • $\Omega(N,\mathcal{H},\delta) = \sqrt{\dfrac{8}{N} \ln{\dfrac{4(2N)^{d_{VC}}}{\delta}}}$ 称为模型复杂度的惩罚项

  • 随着 $d_{VC}$ 增加，$E_{in}$ 下降，但是 $\Omega$ 上升。所以 $E_{out}$ 随 $d_{VC}$ 先下降后上升

  • 样本复杂度：$d_{VC}$ 固定的情况下，$N$ 的合理取值(理论上 $N \approx 10000d_{VC}$ 实际上只需要 $N \approx 10d_{VC}$)

2.4 Noise and Error

本节主要说了在数据集有噪声的情况下，VC维依然是成立的，机器学习依然是可能的

• 样本由 $P(y|\vec{x})$ (也就是 $f(\vec{x}) + noise$ ) 产生
  • 只要 $\vec{x} \stackrel{\text{i.i.d}}{\sim}{P(\vec{x})}$ 和 $y \stackrel{\text{i.i.d}}{\sim}{P(y)}$，VC维理论依然成立

• 误差的度量方式

  • 误差度量的特点：1、只考虑样本外的未知数据，2、分别考虑每个数据点的误差(不一定满足，但本课程只考虑这个)

  • 常用误差有：0-1误差和平均平方误差(MSE)，前者用于分类，后者用于回归

  • 0-1误差下的 $f(\vec{x}) = \mathop{\arg\max}\limits_{y \in \mathcal{Y}} P(y|\vec{x})$，使得翻转噪声最小

  • MSE下的 $f(\vec{x}) = \sum\limits_{y \in \mathcal{Y}} yP(y|\vec{x})$，使得高斯噪声最小

• 错误衡量设计的两种方式：有意义的或者易于设计算法
• 通过”虚拟复制”某类错误对应的标签的样本w次的方法，可以计算 $E_{in}^w$ (w为某类错误的权重)

3. How Can Machines Learn?

3.1 Linear Regression

• 线性回归使用超平面 $h(\vec{x}) = \vec{w}^T\vec{x}$ 估计真实值

• 线性回归存在用伪逆表示的解析解 $\vec{w}_{LIN} = X^{\dagger}\vec{y}$

  • MSE误差最小等价于：$\min\limits_{\vec{w}} E_{in}(\vec{w}) = \frac{1}{N} \Vert X\vec{w} - \vec{y} \Vert^2$

  • 因为MSE损失函数为凸函数，所以 $\nabla E_{in}(\vec{w}) = 0$ 处即为最小值点

• 线性回归相当于使 $\vec{y}$ 投影到由 $X$ 的特征张成的平面内，其中 $y - \hat{y}$ 是误差

  • $trace(I - H) = N-(d+1)$ 表示$\vec{y}$ 投影到由 $X$ 的特征张成的平面内损失的自由度

  • 如果有真实值来自于$f(X) \in span{X}$，那么对 noise 进行投影即 $I-H$ 操作可得：

    $\overline{E_{in}} = \frac{1}{N}\Vert y - \hat{y} \Vert^2 = \frac{1}{N}\Vert (I-H)\textbf{noise} \Vert^2 =
    \textbf{noise} (1-\frac{d+1}{N})$

  • $\overline{E_{out}} = \textbf{noise} (1+\frac{d+1}{N})$，随着 $N$ 逐渐增大 $\overline{E_{in}} \approx \overline{E_{out}}$

• 用回归器进行分类的代价是更松的上界，因为 $err_{0/1} \leq err_{sqr}$，所以 $E_{out} \leq 分类E_{in} + 复杂度 \leq 回归E_{in} + 复杂度$

3.2 Logistic Regression

• Logistic 回归的目标函数是 $P(+1|x)$，其假设为 $h(x) = \theta(\vec{w}^T x)$(其中 $\theta = \dfrac{1}{1+e^{-s}}$)
• Logistic 回归的损失函数是交叉熵函数(似然函数的负对数 $L(\vec{w}) = \frac{1}{N}\sum\limits_{n=1}^{N} -\ln \theta(y_n \vec{w}^T \vec{x}_n)$)
• Logistic 回归的损失函数是凸函数，因此其最小值在
  $\nabla E_{in}(\vec{w}) = \frac{1}{N} \sum\limits_{n=1}^{N} \theta(-y_n \vec{w}^T \vec{x}_n) (-y_n \vec{x}_n) = 0$ 处取得
• Logistic 回归可以用梯度下降法求得 $L(\vec{w})$ 最小值
  • $\vec{w}$ 更新方式：$\vec{w}_{t+1} = \vec{w}_{t} + \eta \vec{v}$
  • $\eta$ 很小的时候可以泰勒展开近似，$E_{in}(\vec{w}_{t+1}) \approx E_{in}(\vec{w}_{t} + \eta \vec{v}^T \nabla E_{in}(\vec{w}_t))$
  • 当 $\vec{v}$ 与 $\nabla E_{in}(\vec{w}_t)$ 方向相反时(即 $\vec{v} = -\dfrac{\nabla E_{in}(\vec{w}_t)}{\Vert \nabla E_{in}(\vec{w}_t) \Vert}$)
    $E_{in}$ 下降最快
  • 我们希望 $\eta$ 与 $\Vert \nabla E_{in}(\vec{w}_t) \Vert$ 正相关，因此更新的式子可以改为:
    $\vec{w}_{t+1} = \vec{w}_{t} - \eta \nabla E_{in}(\vec{w}_t)$

3.3 Linear Models for Classification

• 线性回归和Logistic 回归都可以解决线性分类问题
• 随机梯度下降(SGD)可以简化更新操作到 $\mathcal{O}(1)$ 复杂度
  简化后的更新操作：$\vec{w}_{t+1} = \vec{w}_{t} - \eta \theta(-y_n \vec{w}_t^T \vec{x}_n) (-y_n \vec{x}_n)$
• 多分类问题
  • OVA：对每一类和所有其他类别数据做二分类，分别计算 $P(k|\vec{x})$
    • 优点：高效，可以和所有类似Logistic 回归的算法结合
    • 缺点：K较大时容易类别不平衡
  • OVO：对每一类和每种其他类别数据做二分类
    • 优点：可以和所有二分类算法结合
    • 缺点：时空复杂度高，预测速度慢

3.4 Nonlinear Transformation

• 可以用一非线性函数 $\Phi$ 将非线性函数映射到线性空间中，实现x域到z域特征转换
• z域特征维度 $\tilde{d} = C_{Q+d}^{Q} = C_{Q+d}^{d} = \mathcal{O}(Q^d)$ 较大，
  会导致模型泛化能力差，时空复杂度高
• 优先选择 $Q$ 较小的假设，如果 $E_{in}$ 太高在考虑复杂假设

4. How Can Machines Learn Better?

4.1 Hazard of Overfitting

• 过拟合：$E_{in}$ 变小但是 $E_{out}$ 变大的过程。以下是过拟合常见原因：
  • VC Dimension太大
  • 随机噪声或系统性噪声过强
  • 训练样本数 $N$ 不够
• 避免过拟合的措施:
  • 从简单的模型开始
  • 数据清理(修正明显错误的label或者删除错误样本点)
  • 数据增强(注意新增的数据可能和原来数据不是 $i.i.d.$ 的，尽量保证新数据内的样本是 $i.i.d.$ 的)
  • 正则化
  • 验证

4.2 Regularization

• 正则化约束条件：$\Vert \vec{w} \Vert^2 \leq C$，$H_n \subset H(C) \subset H_m$ ($n<m$)
• 最优解需要满足 $-\nabla E_{in}(w_{reg})$ 与 $w^Tw = C$ 的法向量平行，
  即 $\nabla E_{in}(w_{reg}) + \frac{2\lambda}{N}w_{reg}=0$
  • 求解 $w_{reg}$ 等价于最小化 $E_{aug} = E_{in} + \frac{\lambda}{N} w_{reg}^Tw_{reg}$
  • 多项式变换除了可以用朴素的 $x^n$，也可以用勒让德多项式
• $E_{aug}$ 可以看成 $E_{out}$ 的代理
  • $E_{aug} = E_{in} + \frac{\lambda}{N} w^Tw$ 中的 $w^Tw$ 是单个假设的复杂度，记为 $\Omega(w)$。
    整个 $H$ 的复杂度为 $\Omega(H)$，$\Omega(w)$ 包含在 $\Omega(H)$ 中
  • 整个 $H$ 的VC维是 $d_{VC} = \tilde{d} + 1$，引入正则化限定条件 $H(C)$ 后的VC维记为 $d_{EFF}(H,A)$.
    则有 $d_{EFF}(H,A) \leq d_{VC}$
• 正则化项选择方法
  • 基于目标特性，比如目标具有对称性则考虑用 $\sum\mathbb{I}(q \% 2==0)w^2_q$ 作为正则化项
  • 接近真实(曲线平滑、简单)，如L1正则化 $\sum \vert w_q \vert$
  • 易于实现，如L2正则化 $\sum w^2_q$
  • 噪音越大，$\lambda$ 也要越大

4.3 Validation

模型选择指的是在 $M$ 个假设空间 $H_m$ 对应 $M$ 种算法 $A_m$ 中选择最优假设空间 $H_{m^*}$

使得 $g_{m^} = A_{m^}(D)$，$E_{out}(g_{m^*})$ 最小

• 用验证集选择模型
  • 用 $E_{in}$ 选择模型是危险的(因为即用 $D$ 训练模型又用它选择模型)
  • 用 $E_{test}$ 选择模型是作弊且无法实现的(难以获得测试数据)
• 验证集模型选择原理：$E_{out}(g) \mathop{\approx}\limits_{small K} E_{out}(g^-) \mathop{\approx}\limits_{large K} E_{val}(g^-)$
  • 验证集大小 $K$ 越大，$g^-$ 越不如 $g$，但是 $E_{val}$ 越接近 $E_{out}$ (学习曲线)
  • 验证集大小 $K$ 越小，$g^-$ 越接近 $g$，但是 $E_{val}$ 越不如 $E_{out}$ (学习曲线)
• 留一法交叉验证(LOOCV) 的期望 $\mathop{\varepsilon}\limits_{D} E_{LOOCV}(H,A) = \overline{E_{out}}(N-1)$
  是对 $\overline{E_{out}}$的近似无偏估计
  • $E_{LOOCV} = \frac{1}{N} \sum\limits_{n=1}^{N} err(g_m^-(\vec{x}_n),y_n)$ ($K = 1$ 的特殊情况)
  • LOOCV的缺点：计算量大、结果不稳定
• V折交叉验证公式：$E_{CV} = \frac{1}{V} \sum\limits_{v=1}^{V} E_{val}^{(v)}(g_v^-)$

4.4 Three Learning Principles

• 奥卡姆剃刀原则：适合数据的最简单的模型是最合适的
• 抽样误差：数据要匹配测试环境
• 偷窥数据：容易造成过拟合。应当避免通过数据进行决策，并且对别人的研究成果保持警惕
• power of three
  • 机器学习相关的三个领域：数据挖掘、机器学习、统计
  • 三个理论保证：霍夫丁不等式、多假设霍夫丁不等式、VC维
  • 三种线性模型：感知机、线性回归、Logistic回归
  • 三种重要的工具：特征转换、正则化、验证
  • 三个锦囊妙计：奥卡姆剃刀、防止抽样误差、谨慎偷窥数据
  • 机器学习未来方向：更多转换、更多正则化、更少标签