关于周志华老师的《机器学习》这本书的学习笔记
记录学习过程
本博客记录Chapter1 to Chapter3

1 绪论

1.1 引言

机器学习是关于“学习算法”的学问。

1.2 基本术语

• 特征向量（feature vector）：xi={xi1,xi2,…,xid}x_i = \{x_{i1},x_{i2},…,x_{id}\}xi​={xi1​,xi2​,…,xid​}

• 维数（dimensionality）：属性总数$d$

• 预测：预测值离散—分类；预测值连续—回归；还有聚类

• 根据训练数据是否有标记信息：监督学习（supervised learning）和无监督学习（unsupervised learning）。分类和回归是前者；聚类是后者。

• 训练模型适用于新样本的能力称为“泛化”。

1.3 假设空间

归纳学习：induction，从特殊到一般的泛化过程。

学习过程是在所有假设（hypothesis）组成的空间中搜索的过程，搜索目标是找到与训练集匹配的假设。

1.4 归纳偏好

机器学习算法在学习过程中对某种类型假设的偏好，称为归纳偏好（inductive bias）

• 奥卡姆剃刀（Occam’s razor）：若有多个假设与观察一致，则选择最简单的那个。例如认为“更平滑”意味着“更简单”。

  假设样本空间$\chi$和假设空间$H$都是离散的。

  令$P(h|x,{\zeta }_a)$是代表算法${\zeta }_a$在训练数据$X$产生假设$h$的概率。令$f$代表真是目标函数。训练集外误差：

$$E_{ote}({\zeta }_a|X,f)=\sum _h\sum _{x\in \chi -X}P(x)Ⅱ(h(x)\ne f(x))P(h|X,{\zeta }_a)$$
​ 其中，$Ⅱ$表示指示函数，为真取1为假取0。

• NFL定理（没有免费午餐）：当所有问题出现的机会相同，即所有问题同等重要的情况下，所有学习算法的期望性能相同。（$E_{ote}$相同）。其重要意义在于让我们认识到脱离具体问题，空谈算法好坏毫无意义。

1.5 发展历程

推理—>知识—>学习

归纳逻辑程序设计（Inductive Logic Program，ILP）：决策树，不适用于问题规模极大的情况

基于神经网络的连接主义：BP神经网络，黑箱模型，调参困难

统计学习（statistical learning）：支持向量机，核方法。

深度学习：连接主义，多层神经网络。拥有大量参数，样本数据少容易过拟合。

2 模型估计与选择

2.1 经验误差与过拟合

1. 经验误差：$m$个样本中$a$个分类错误，则错误率$E=\frac{a}{m}$。精度为$1-E$。学习器在训练集上的误差称为经验误差或训练误差。在新样本上的误差称为泛化误差。我们希望得到泛化误差小的学习器。

2. 过拟合：学习器把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，导致泛化能力下降。

   欠拟合：训练样本的一般性质尚未学好。
   

2.2 评估方法

• 用测试误差作为泛化误差的近似。

• 划分测试集和训练集的方法：

  • 留出法：直接将数据集划分为两个互斥的集合。$D=S\cup T,S\cap T=\varnothing$

    • 结果：多次随机划分结果的平均值
    • 一般将$2/3,4/5$的数据用于训练集，剩余数据作为测试集

  • 交叉验证法：将数据集划分为$k$个大小相似的互斥子集。

    • $k=10$：十折交叉验证
    • $k=m(样本数)$：留一法，结果可靠但是运算复杂，计算开销大

    

  • 自助法（bootstrapping）：以自助采样法（bootstrap sampling）为基础，给定包含$m$个样本的数据集$D$，对他采样产生数据集$D^{\prime }$：每次随机从$D$中挑选一个样本加入到$D^{\prime }$并放回，重复该过程$m$次。

    • 简单估计，样本在$m$次采样中均不被采样的概率$p=(1-\frac{1}{m}{)}^m\approx e^{-1}\approx 0.368$
    • 适用于数据集较小、难以有效划分训练集和测试集的情况。

• 调参和最终模型：

  • 参数分为算法的参数（超参数，数量一般在10以内）和模型的参数（很多）

2.3 性能度量

1. 回归：均方误差（mean squard error）
   $$MSE=E(f;D)=\frac{1}{m}\sum _{i=1}^m(f(x_i)-y_i{)}^2$$

2. 分类任务：

   • 精度：$acc(f;D)=\frac{1}{m}{\sum }_{i=1}^mⅡ(f(x_i)\ne y_i)$

   • 错误率：$E(f;D)=1-acc(f;D)$

   • 混淆矩阵

     

   • 查准率：$precision=\frac{TP}{TP+FP}$

   • 查全率：$recall=\frac{TP}{TP+FN}$

     • 查全率和查准率是一堆矛盾的较量

   • $BEP$平衡点（$precision=recall$），平衡点越大，可以认为学习器更好

   • $F1$度量：$F1=\frac{2\times Precision\times Recall}{Precision+Recall}$

     • 本质是调和平均

   • $F_{\beta }$度量：$F1=\frac{(1+{\beta }^2))\times Precision\times Recall}{({\beta }^2\times Precision)+Recall}$

     • 本质是加权调和平均
     • $\beta$表示查全率对查准率的影响；$\beta >1$说明查全率影响

   • 宏F1：先计算各混淆矩阵的查全率和查准率，在平均调和

   • 微F1：先计算TP FP TN FN的平均，再计算查全率、查准率和F1

   • ROC和AUC：

     • ROC（受试者工作特征曲线）：

       • 纵轴（真正例率）：$TPR=\frac{TP}{TP+FN}$
       • 横轴（假正例率）：$FPR=\frac{FP}{TN+FP}$

     • AUC：ROC曲线下的面积。$AUC=\frac{1}{2}{\sum }_{i=1}^{m-1}(x_{i+1}-x_i)(y_i+y_{i+1})$

     • 非均等代价：不同类型错误造成不同损失。

       

     • $D^{+}$代表数据集$D$的正例子集，$D^{-}$代表数据集$D$中的反例子集，代价敏感错误率为：
       $$E(f;D;cost)=\frac{1}{m}(\sum _{x_i\in D^{+}}Ⅱ(f(x_i)\ne y_i)\times cos{t}_{01}+\sum _{x_i\in D^{-}}Ⅱ(f(x_i)\ne y_i)\times cos{t}_{10})$$

2.4 比较检验

• 统计假设检验：若在测试集上观察到学习器A比学习器B好，则A的泛化性能是否在统计意义上优于B，以及这个结论的把握有多大。

• 假设检验

  • 思想：根据测试错误率推估出泛化错误率的分布。

  • 泛化错误率$ϵ$，测试错误率$\widehat{ϵ}$。将$\widehat{ϵ}\times m$个样本误分类的概率：$P(\widehat{ϵ};ϵ)=\left(\begin{array}{c}m\\ m\times \widehat{ϵ}\end{array}\right){ϵ}^{\widehat{ϵ}\times m}(1-ϵ{)}^{m-\widehat{ϵ}\times m}$，求解导数，令一阶导数为0得到**$\widehat{ϵ}=ϵ$**,满足二项分布。可使用二项检验，计算$\overline{ϵ}$（误判样本数量不少于$\epsilon_0\times m $个样本的概率小于$\alpha$，其中最小的$\epsilon$）：
    $$\overline{ϵ}=minϵs.t.\sum _{i={ϵ}_0\times m+1}^m\left(\begin{array}{c}m\\ i\end{array}\right){ϵ}^i(1-ϵ{)}^{m-i}<\alpha$$
    若测试错误率$\widehat{ϵ}<\overline{ϵ}$，根据二项检验，得出结论再$\alpha$的显著度下，假设$ϵ\le {ϵ}_0$不能被拒绝。

  

  • t检验：得到了$k$个测试错误率，$\widehat{{ϵ}_1}、\widehat{{ϵ}_2}、\dots 、\widehat{{ϵ}_k}$，则平均错误率和方差为：

    • $\mu =\frac{1}{k}{\sum }_{i=1}^k\widehat{{ϵ}_i}$
    • $\sigma =\frac{1}{k-1}{\sum }_{i-1}^k(\widehat{{ϵ}_i}-\mu {)}^2$
    • $t=\frac{\sqrt{k}(\mu -{ϵ}_0)}{ϵ}$服从自由度为$k-1$的$t$分布。若$t$位于$[t_{-\frac{\alpha }{2}},t_{\frac{\alpha }{2}}]$，则无法拒绝原假设。

• 交叉验证$t$检验

  • 两个学习器A和B，使用$k$折交叉验证法得到测试错误率分别为${ϵ}_1^A,\dots ,{ϵ}_k^A$和${ϵ}_1^B,\dots ,{ϵ}_k^B$。计算差值$△i={ϵ}_i^A-{ϵ}_i^B$(均值应该为0)。根据$\triangle i $做$t$检验：$t=|\frac{\sqrt k\mu}{\sigma}|$

• McNemar检验

  

  • $e_{01}$和$e_{10}$应该相等。$|e_{01}-e_{10}|$应服从正态分布。用卡方检验：${\chi }^2=\frac{(|e_{01-e_{10}}|-1{)}^2}{e_{01}+e_{10}}$服从自由度为1的卡方分布。（$e_{01}+e_{10}$通常很小，需考虑连续性校正，因此分子中有-1项）。

• Friedman检验和Nemenyi后续检验

  • 对比多组算法的性能。在多个数据集对算法进行排序，求取排序的平均值。采用F检验判断算法是否性能相同。若拒绝原假设，则采用后续检验。

2.5 偏差和方差

• 泛化误差可以分为偏差、方差和噪声之和（假定噪声期望为0）。

  • 期望输出：$\bar{f}(x)=E_D[f(x;D)]$
  • 偏差：期望输出与真实标记的差别（bias），刻画了算法本身的拟合能力。$bia{s}^2(x)=(\bar{f}(x)-y{)}^2$
  • 使用样本数相同的不同训练集产生的方差，描述数据扰动所造成的影响。$var(x)=E_D[(f(x;D)-\bar{f}(x){)}^2]$
  • 噪声，描述了学习问题本身的难度。${\epsilon }^2=E_D[(y_D-y{)}^2]$。（$y_D$是数据集中的标记，$y$是真实标记，即数据集中可能存在标错的情况）
  • 泛化误差：$E(f;D)=E_D[(f(x;D)-y_D{)}^2]$

• 偏差-方差窘境：

  • 假定能控制学习算法的训练程度。训练不足：学习器拟合能力不够强，训练数据的扰动不足以使得学习器发生显著变化，偏差主导了泛化错误率；训练程度加深，拟合能力增强，训练数据发生的扰动渐渐能被学习器学到，方差主导了泛化错误率。若训练数据自身的、非全局的特性被学习到，则将发生过拟合。

3 线性模型

3.1 基本形式

$$f(x)=w_1{x}_1+w_2{x}_2+\dots +w_d{x}_d+b={\mathbf{w}}^T\mathbf{x}+b$$

3.2 线性回归

最小二乘法：基于均方误差最小化。

• 针对一元回归$f(x_i)=w{x}_i+b$

  • 原理：找到一条直线，使得所有样本到直线上的欧氏距离之和最小
    $$\begin{gathered} (w^{\ast },b^{\ast })={\mathrm{argmin}}_{(w,b)}\sum _{i=1}^m(f(x_i)-y_i{)}^2 \\ ={\mathrm{argmin}}_{(w,b)}\sum _{i=1}^m(y_i-w{x}_i-b{)}^2 \end{gathered}$$

  • 参数估计：

    • 求解w：
      $$\begin{gathered} \frac{\partial E_{(w,b)}}{\partial w}=2(w\sum _{i=1}^m{x}_i^2-\sum _{i=1}^m(y_i-b)x_i)=0 \\ w=\frac{\sum _{i=1}^m{y}_i(x_i-\bar{x})}{\sum _{i=1}^m{x}_i^2-\frac{1}{m}(\sum _{i=1}^m{x}_i{)}^2} \end{gathered}$$

    • 求解b：
      $$\begin{gathered} \frac{\partial E_{(w,b)}}{\partial b}=2(mb-\sum _{i=1}^m(y_i-w{x}_i))=0 \\ b=\frac{1}{m}\sum _{i=1}^m(y_i-w{x}_i) \end{gathered}$$

• 针对多元回归$f(x)=wx;x=(x;1);w=(w;1)$

  • 原理：
    $${\hat{w}}^{\ast }={\mathrm{argmin}}_{\hat{w}}(\mathbf{y}-\mathbf{X}\hat{\mathbf{w}}{)}^T(\mathbf{y}-\mathbf{X}\hat{\mathbf{w}})$$

  • 参数估计：

    • 求解$w$：
      $$\frac{\partial E_{\hat{w}}}{\partial \hat{w}}=2{\mathbf{X}}^{\mathbf{T}}(\mathbf{X}\hat{\mathbf{w}}-\mathbf{y})$$

      • 当$X^{T}X$满秩矩阵，直接令上式为0，得${\hat{w}}^{\ast }=({\mathbf{X}}^{\mathbf{T}}\mathbf{X}{)}^{-1}{\mathbf{X}}^{\mathbf{T}}\mathbf{y}$
      • 当$X^{T}X$不是满秩矩阵，可以解出多个$\hat{w}$，都能使得均方误差最小化。引入正则化项（regularization）选择解。

广义线性模型：$y=g^{-1}({\mathbf{w}}^{\mathbf{T}}\mathbf{x}+b)$，函数$g(\cdot )$为联系函数。

3.3 对数几率回归

对数几率函数Sigmoid函数：
$$y=\frac{1}{1+e^{-({\mathbf{w}}^{\mathbf{T}}\mathbf{x}+b)}}$$
式（11）可变换为：
$$ln\frac{y}{1-y}={\mathbf{w}}^{\mathbf{T}}\mathbf{x}+b$$
将$y$看作样本$x$作为正例的可能性，$1-y$为反例的可能性，两者比值称为几率（odds），反应$x$作为正例的相对可能性
$$\frac{y}{1-y}$$

3.4 线性判别分析（LDA）

LDA线性判别分析：也叫Fisher判别分析。是一种监督降维技术。

核心思想： 给定训练样例集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离;在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定新样本的类别

数学表达：极小化同类样例投影点的协方差；极大化异类样例中心之间的距离。
$$\begin{gathered} 广义瑞利商：J=\frac{||{\mathbf{w}}^{\mathbf{T}}{\mathbf{\mu }}_0-{\mathbf{w}}^{\mathbf{T}}{\mathbf{\mu }}_1|{|}_2^2}{{\mathbf{w}}^{\mathbf{T}}{\sum }_0\mathbf{w}+{\mathbf{w}}^{\mathbf{T}}{\sum }_1\mathbf{w}}=\frac{w^T{S}_{b}w}{w^T{S}_{w}w} \\ 类间散度矩阵：S_b=({\mu }_0-{\mu }_1)({\mu }_0-{\mu }_1{)}^T \\ 类内散度矩阵：S_w=\sum _0+\sum _1=\sum _{\mathbf{x}\in X_0}(x-{\mu }_0)(x-{\mu }_0{)}^T+\sum _{\mathbf{x}\in X_1}(x-{\mu }_1)(x-{\mu }_1{)}^T \end{gathered}$$
求解$w$:$J$与$w$的长度无关，只与方向有关。令$w^T{S}_{w}w=1$
$$\begin{gathered} {\min }_w-w^T{S}_{b}w \\ s.t.w^T{S}_{w}w=1 \end{gathered}$$
由拉格朗日乘子法，后进行奇异值分解。

3.5 多分类学习

核心问题：基本思路是“拆解法”，即将多分类任务拆分为若干个二分类任务。关键在于如何对多分类任务进行拆分，以及对多个分类器进行集成。

拆分策略：

• OvO（一对一）：训练$\frac{N(N-1)}{2}$个分类器（两两一个），单个分类器的训练数据量较小

• OvR（一对其余）：训练$N$个分类器，但是单个分类器训练数据较大

  

• MvM（多对多）：采用ECOC（纠错输出码技术）。一般来说，ECOC编码越长，纠错能力越强，开销也越大。

  • 编码：划分M次（下图（a）为5次，五个分类器，$f_2$分类器中，$C_1,C_3$为正例）

  • 解码：测试结果和各类的编码结果之间求解距离。

    (a)中：$2\sqrt{3}=\sqrt{[-1-(-1){]}^2+[1-(-1){]}^2+[-1-1{]}^2+[1-(-1){]}^2+[1-1{]}^2}=\sqrt{12}=2\sqrt{3}$

  

3.6 类别不平衡问题

• 再缩放策略：一般来说阈值设置为0.5($\frac{y}{1-y}=1$)。更改分类器决策规则：若$\frac{y}{1-y}>\frac{m^{+}}{m^{\_}}$，预测为正例。
  • 前提：训练集是真是样本总体的无偏采样。这个假设很难成立，因此我们未必有效地基于训练集观测几率odds来推断真实几率
• 解决方案：
  • 欠采样：去除一些反例使得正反例数目接近。
    • 可能会丢失信息。
    • EasyEnsemble：随机丢弃反例
  • 过采样：增加一些正例使得正反例数目接近。
    • 不能简单的重复样本，不然会导致过拟合。
    • SMOTE：对训练集的正例进行插值得到额外的正例。
  • 阈值移动：再缩放策略。