机器学习(零)

绪论

基本术语

基本概念

  • $\mathcal{X}$, 样本空间(sample space)
  • $\mathcal{Y}$, 标记空间(label space)
  • $\vec{x_i}=(x_{i1}; x_{i2}; \dots; x_{id}) \in \mathcal{X}$, 样本(sample)
  • $y_i \in \mathcal{Y}$, 标记(label)
  • $(\vec{x_i},y_i)$, 样例(example)
  • $f:\mathcal{X} \mapsto \mathcal{Y}$, 预测函数(predicting function)
  • $\hat{y}=f(\vec{x})$, 预测标记(predicted label)

假设空间

  • $\mathcal{H}$, 假设空间(hypothesis space)
  • $\mathcal{H}_v$, 版本空间(version hypothesis)
  • $h$, 假设(hypothesis)

搜索目标: 找到$h \in \mathcal{H}_v$

归纳偏好: 有偏好地选择$h$

没有免费的午餐定理(NFL Theorem):
$$\sum_fE_{ote}(\mathfrak{L_a}|X, f) = \sum_fE_{ote}(\mathfrak{L_b}|X, f)$$

模型评估

基本概念

  • 训练误差(training error), 学习器在训练集上的误差
  • 泛化误差(generalization error), 学习器在新样本上的误差
  • 过拟合(overfitting), 对训练集过配
  • 欠拟合(underfitting), 对训练集欠配

评估方法

  • 留出法(hold-out), 直接将数据集$D$划分为训练集$S$和测试集$T$, 一般用$2/3 \sim 4/5$的样本用于训练, 剩余样本用于测试
  • 交叉验证法(cross validation), 将数据集$D$划分为$k$个大小相似的集合, 训练集为其中$k-1$个子集的并集, 测试集为剩余的子集, 取$k$次训练和测试结果的平均
  • 留一法(leave-one-out), 交叉验证法的特例, 取$k = \left| D \right|$, 在数据集比较大时, 计算开销非常大
  • 自助法(bootstrapping), 自助采样亦称“有放回采样”, 从数据集$D$中通过自助采样产生相同规模的数据集$D’$, $D$作为训练集, $D \setminus D’$作为测试集, 优点是同规模, 缺点是不同分布

性能度量

  • 回归任务
    • 均方误差, $$E(f;D)=\frac{1}{m}\sum f(\vec{x_i}-y_i)^2$$
  • 分类任务
    • 错误率, $$E(f;D)=\frac{1}{m}\sum \mathbb{I}(f(\vec{x_i} \neq y_i)$$
    • 查准率, $$P=\frac{TP}{TP+FP}$$
    • 查全率, $$R=\frac{TP}{TP+FN}$$
    • 代价敏感错误率, $$E(f;D;cost)=\frac{1}{m}\sum \mathbb{I}(f(\vec{x_i} = y_j)\times cost_{ij}$$

假设检验

  • 二项检验(binomial test),
    $$\bar{\epsilon} = \max \epsilon\text{ s.t. }
    \sum_{i=\epsilon_0 \times m + 1}^{m}
    \begin{pmatrix}
    m \
    a \
    \end{pmatrix} \epsilon^{i} (1-\epsilon)^{m-i} < \alpha$$
  • $t$检验(t-test),
    $$\tau_t = \frac{\sqrt{k}(\mu-\epsilon_0)}{\sigma}$$

参考资料

周志华, 机器学习, 清华大学出版社, 2016年版