【浅谈系列】统计学习常见算法(一)

8 minute read

Published:

对统计学习部分的相关算法的简单总结。

由于人工智能的火热,近年密码学在现实中的应用往往也涉及机器学习、深度学习等领域的算法,因此最近抽空简单入了个门。

这篇文章是对传统机器学习,也就是统计学习部分的相关算法,进行科普性的、简单的总结,如有错误欢迎指正。

0. 参考资料

1. 基本概念

(1) 统计学习、机器学习、深度学习

统计学习和机器学习类似,都是从数据中进行学习。只不过统计学习更侧重于数学理论,而机器学习更侧重于数据和模型预测,可以说,机器学习是在统计学习的理论基础上发展起来的。

深度学习则一般被认为是机器学习领域的一个分支。相比传统机器学习,深度学习最直观区别是在加深了隐含层由模型自动抽取特征,参数量大,训练时间长,弱化了解释性,趋向于黑盒子,对数据依赖性更强,更擅长处理高维度大数据。

由于本文只是入门级的,因此只简单介绍传统机器学习,也就是统计学习领域的相关算法。

在蒲公英书的开篇,作者根据自己的理解给出了相关知识的梳理,可以参考一下。

(2) 机器学习

  • 对象:具有一定统计规律的数据。

  • 根据任务分类:

    • 监督学习:从已标记的训练数据来训练模型。 包括:分类任务、回归任务、序列标注任务。

    • 无监督学习:从未标记的训练数据来训练模型。包括:聚类任务、降维任务。

    • 半监督学习:用大量的未标记训练数据和少量的已标记数据来训练模型。

    • 强化学习:从系统与环境的大量交互知识中训练模型。

  • 根据算法分类:

    • 统计学习:基于数学模型的机器学习方法。包括 SVM、逻辑回归、决策树等。这一类算法基于严格的数学推理,具有可解释性强、运行速度快、可应用于小规模数据集的特点。

    • 深度学习:基于神经网络的机器学习方法。包括前馈神经网络、卷积神经网络、递归神经网络等。这一类算法基于神经网络,可解释性较差,强烈依赖于数据集规模。但是这类算法在语音、视觉、自然语言等领域非常成功。

(3) 常见术语

  • 数据:数据集、样本、属性、属性值、属性空间、特征向量、维数

  • 学习:训练、训练数据、训练样本、训练集、假设、模型(学习器)

  • 输出:标记(结果信息)、样例、标记空间(输出空间)

  • 测试:测试样本、预测标记

  • 监督学习:离散值 –> 分类、连续值 –> 回归、概率模型与非概率模型、生成模型与判别模型

  • NFL 定理:天下没有免费的午餐,没有一个模型能适应所有场景。

  • 启发式算法: 启发式算法 - 范叶亮的博客

(4) 三要素

  • 模型:根据模型,解空间为决策函数或条件概率的集合

  • 策略:策略指按照什么样的准则学习,从而定义优化目标;一般参考这几个准则:损失函数、风险函数、经验风险、极大似然估计、最大后验估计

  • 算法:训练模型所用的方法,一般用数值计算相关知识求解

2. 数学基础

(1) 线性代数

包括但不限于 Frobenius 范数、迹、向量内积外积、线性空间、Hadamard 积Kronnecker 积、各种类型偏导数。

(2) 特殊函数

包括但不限于 sigmoid 函数softplus 函数Gamma 函数Beta 函数

(3) 概率论

包括但不限于 条件概率、联合概率分布、期望与方差、协方差与相关系数、大数定律与中心极限定理、常见概率分布、先验分布与后验分布、信息论相关知识。

(4) 数值计算

包括但不限于 近似与误差、条件数、梯度下降、Hesse 矩阵、牛顿法、约束优化问题。

(5) MC 方法

包括但不限于 Monte Carlo 方法、马尔可夫链、MCMC 采样

3. 统计学习(0):模型评估

(1) 基本概念:经验误差与过拟合

  • 错误率与精度、训练/经验误差(训练集上)与泛化误差(新样本上)

  • 欠拟合与过拟合:过拟合,指把训练样本的一些自身特点当成了所有样本的一般性质,从而导致泛化性能下降;欠拟合容易克服,过拟合则是主要障碍

(2) 评估准备工作:产生测试集

模型泛化能力评估需要测试集。那如何从数据集中产生训练集和测试集?

  • hold-out 留出法:简单的拆分为互斥的训练集和测试集。注意,使用这种方法时尽量保持数据分布一致性,两个集合样本类别比例差别不能很大。

  • cross validation 交叉验证法:划为为 $k$ 个互斥子集,每次用任意 $k-1$ 个的并来训练,剩下一个来测试。

  • bootstrapping 自助法:$m$ 次采样获取训练集,剩下数据作为测试集,取极限可知大约 $\frac{1}{3}$ 的数据作为测试集。

除了训练集和测试集,有的模型中还包含验证集。

  • 超参数与验证集:大多数机器学习算法具有超参数,超参数的值无法通过学习算法拟合出来(比如正则化项的系数、控制模型容量的参数)。为了解决这个问题,可以引入验证集。具体的例子和细节可以看 机器之心 - 超参数

(3) 模型泛化能力评估:性能度量

  • 分类问题性能度量
    • 准确率、错误率
    • 查准率、查全率
    • P-R 曲线
    • ROC 曲线
    • F1 值
    • 代价矩阵
  • 回归问题性能度量
    • 均方误差
    • 均方根误差
    • 均方根对数误差
    • 平均绝对误差

(4) 知其然也要知其所以然:偏差方差分解

除了通过实验评估泛化性能,我们还需要了解为什么某个算法具有这样的性能。偏差方差分解是解释学习算法泛化性能的重要工具。 偏差方差分解推导如下:

\[\begin{align} E(f;D) & = \mathbb{E}_D[((f(x;D)-y_D)^2] \\ & = \mathbb{E}_D[(f(x;D)-\overline{f}(x)+\overline{f}(x)-y_D)^2] \\ & = \mathbb{E}_D[(f(x;D)-\overline{f}(x))^2] + \mathbb{E}_D[(\overline{f}(x)-y_D)^2]+\mathbb{E}_D[2(f(x;D)-\overline{f}(x))(\overline{f}(x)-y_D)] \\ & = \mathbb{E}_D[(f(x;D)-\overline{f}(x))^2]+\mathbb{E}_D[(\overline{f}(x)-y_D)^2] \\ & = \mathbb{E}_D[(f(x;D)-\overline{f}(x))^2] +\mathbb{E}_D[(\overline{f}(x)-y+y-y_D)^2] \\ & = \mathbb{E}_D[(f(x;D)-\overline{f}(x))^2]+\mathbb{E}_D[(\overline{f}(x)-y)^2]+\mathbb{E}_D[(y-y_D)^2]+2\mathbb{E}_D[(\overline{f}(x)-y)(y-y_D)] \\ & = \mathbb{E}_D[(f(x;D)-\overline{f}(x))^2] +(\overline{f}(x)-y)^2+\mathbb{E}_D[(y_D-y)^2] \\ & = var(x)+bias^2(x)+\varepsilon^2 \end{align}\]

也就是说,泛化误差可以分解为偏差、方差和噪声之和。通过偏差方差分解,误差诊断可以从具体的偏差或是方差某个方面来入手,对具体的情况给出具体的策略,详细细节可以参考 偏差方差分解

(5) 传统机器学习的挑战

  • 维数灾难:当数据的维数很高时,很多机器学习问题变得相当困难。因为许多传统机器学习算法简单地假设:一个新样本的输出应该大致与最接近的训练样本的输出相同 。

  • 选择性偏好:要学习的函数不会在一个小区域内发生较大的变化。很多简单算法完全依赖此先验知识来达到良好的泛化。

4. 统计学习(1):线性模型

(1) 线性回归

  • 英文名: Linear Regression

  • 原理: 用线性函数来表示数据集中的点,并预测新的点

  • 模型: $f(\vec{\bf{x}}) = \vec{\bf{w}} \cdot \vec{\bf{x}} + b$

  • 策略: 损失函数最小化

  • 算法: 最小二乘法 或 梯度下降法

  • 应用场景: 回归、分类

  • 输入: $\vec{\bf{x}}$ 和 $\vec{\bf{y}}$

  • 输出: 满足策略的权重值 $\vec{\bf{w}}$

  • 要算什么: 一般常用梯度下降,梯度下降通过不断迭代,求得使损失函数最小的权重值;因此每次迭代要算的式子就是:

    \[\theta_i {'} = \theta_i - \alpha \cdot \frac{\partial J}{\partial \theta_i}\]

    其中,

    \[\frac{\partial J(\theta)}{\partial \theta_i} = \frac{1}{m} \sum_{j=1}^{m}(\sum_{i=0}^n \theta_i x_{i,j} - y_j)x_{i,j}\]

(2) 广义线性模型

  • 英文名: Generalized Linear Model

  • 原理: 和线性回归本质上是一样的原理。从函数定义来说,只是将原来的 $f(\vec{\bf{x}}) = \vec{\bf{w}} \cdot \vec{\bf{x}} + b$ 左式变为了单调可微函数 $g(y)$,$g(y)$ 称为联系函数;从概率定义来说,如果给定 $\vec{\bf{x}}$ 和 $\vec{\bf{w}}$,$y$ 的条件概率分布 $p(y \mid \vec{\bf{x}}; \vec{\bf{w}})$ 服从指数分布族,则该模型称为广义线性模型。

  • 指数分布族: $p(y;\eta) = b(y) \cdot e^{\eta T(y)-a(\eta)}$,其中 $\eta$ 是 $\vec{\bf{x}}$ 的线性函数。

  • 常见分布: 高斯分布、伯努利分布、多元伯努利分布。

(3) 对数几率回归

  • 英文名: Logistic Regression

  • 原理: 又称逻辑回归,属于广义线性模型中伯努利分布形式中的一种。原理是如果用来做分类,最理想的单位阶跃函数并不单调可微,所以需要用一个单调可微且满足广义线性模型的函数来近似单位阶跃函数。而 sigmoid 函数 正是一个不错的方案。因此我们可以让 $p(y=1 \mid \vec{\bf{x}}) = \frac{1}{1+e^{-z}}$,$z = \vec{\bf{w}} \cdot \vec{\bf{x}}+b$。其他步骤和线性回归一样。

(4) 线性判别分析

  • 英文名: Linear Discriminant Analysis

  • 原理: 给定训练样本集,设法将样例投影到某一条直线上,使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离。要学习的就是这样的一条直线;对新样本进行分类时,将其投影到学到的直线上,在根据投影点的位置来确定新样本的类别

  • 模型: $y = \vec{\bf{w}}^{T} \cdot \vec{\bf{x}}$

  • 策略: 让不同类别的数据的类别中心之间的距离尽可能的大,同一种类别数据的投影点尽可能的接近,也就是方差尽可能小;前者作为分子,后者作为分母,使这个函数最大即可 \(\underbrace{arg\;max}_w\;\;J(w) = \frac{||w^T\mu_0-w^T\mu_1||_2^2}{w^T\Sigma_0w+w^T\Sigma_1w} = \frac{w^T(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw}{w^T(\Sigma_0+\Sigma_1)w}\)

  • 算法: 借助类内散度矩阵和类间散度矩阵,可以将上面的函数化为瑞利商形式,而瑞利商的最大值等于分母上的那个矩阵最大特征值,对应的 $w$ 是该矩阵取最大值时的特征向量。怎么求解?用拉格朗日乘数法。

    类内散度矩阵和类间散度矩阵:

    \[S_w = \Sigma_0 + \Sigma_1 = \sum\limits_{x \in X_0}(x-\mu_0)(x-\mu_0)^T + \sum\limits_{x \in X_1}(x-\mu_1)(x-\mu_1)^T \\ S_b = (\mu_0-\mu_1)(\mu_0-\mu_1)^T\]

    化为瑞利商:

    \[\underbrace{arg\;max}_w\;\;J(w) = \frac{w^TS_bw}{w^TS_ww}\]

    拉格朗日乘数法:

    \[L(w, \lambda) = -w^TS_{b}w + \lambda (w^TS_ww-1)\]

    求导并令其为 $0$,得到:

    \[S_{w}^{-1}S_{b}w = \lambda w\]

    对于这个式子,可以通过奇异值分解求特征向量 $w$。

  • 应用场景: 监督学习中的降维
  • 输入: $D={(x_1,y_1), (x_2,y_2), …,((x_m,y_m))}$
  • 输出: 设降维后维度为 $d$,则为 $(w_1,w_2,…w_d)$
  • 要算什么: 根据上面的公式,算类内散度矩阵和类间散度矩阵,然后奇异值分解,奇异值分解里主要用了特征分解,也就是求特征值和特征向量

(5) 感知机

  • 英文名: Perceptron

  • 原理: 对于高维空间中的数据集,感知机尝试找到一个超平面,将数据分为两类;在平面中就是找到一条直线,将数据集一分为二;使用感知机的前提条件是数据集线性可分

  • 模型: $f(\vec{\bf{x}}) = sign(\vec{\bf{w}} \cdot \vec{\bf{x}} + b)$

  • 策略: 以误分类的点到超平面距离之和作为损失函数,损失函数最小化

  • 算法: 拟牛顿法 或 梯度下降法

  • 应用场景: 分类

  • 输入: $(x_1^{(0)}, x_2^{(0)}, …,x_n^{(0)}, y_0), (x_1^{(1)}, x_2^{(1)}, …,x_n^{(1)},y_1), …, (x_1^{(m)}, x_2^{(m)}, …, x_n^{(m)}, y_m)$

  • 输出: 超平面 $\vec{\bf{w}} \cdot \vec{\bf{x}} + b = 0$

  • 要算什么: 一般常用梯度下降,梯度下降通过不断迭代,求得使损失函数最小的权重值;因此每次迭代要算的式子就是:

    \[w_i {'} = w_i - \alpha \cdot \frac{\partial J}{\partial w_i}\]

    其中,

    \[\frac{\partial J(w)}{\partial w_i} = - \sum\limits_{x_i \in M}y_i x_i\]

5. 统计学习(2):支持向量机

(1) 线性可分支持向量机

  • 英文名: SVM: support vector machines

  • 原理: 在感知机的基础上,如果所有点不仅和超平面分开,还保持一定距离,那么是比感知机找到的超平面更优;和超平面平行的保持一定的函数距离的这两个超平面对应的向量,称之为支持向量;支持向量到超平面的距离为 $\frac{1}{\lVert w \rVert_2}$,数学上可以证明这样的超平面只有一个

  • 模型:

    \[f(\vec{\bf{x}}) = sign(\vec{\bf{w}} \cdot \vec{\bf{x}} + b), \quad sign(x)= \begin{cases} -1& {x<0}\\ 1& {x\geq 0} \end{cases} \\ max \;\; \frac{1}{||w||_2} \;\; s.t \;\; y_i(w^Tx_i + b) \geq 1 (i =1,2,...m)\]
  • 策略: 构造并求解约束最优化问题

    \[min \;\; \frac{1}{2}||w||_2^2 \;\; s.t \;\; y_i(w^Tx_i + b) \geq 1 (i =1,2,...m)\]

    根据凸优化理论,这里用拉格朗日乘数法将原始问题变为对偶问题

    \[L(w,b,\alpha) = \frac{1}{2}||w||_2^2 - \sum\limits_{i=1}^{m}\alpha_i[y_i(w^Tx_i + b) - 1] \quad (\alpha_i \geq 0)\]

    优化目标变为

    \[\underbrace{min}_{w,b}\; \underbrace{max}_{\alpha_i \geq 0} L(w,b,\alpha)\]

    先求优化函数对于 $w$ 和 $b$ 的极小值,再求拉格朗日乘子 $\alpha$ 的极大值。

    前者求偏导即可

    \[\frac{\partial L}{\partial w} = 0 \;\Rightarrow w = \sum\limits_{i=1}^{m}\alpha_iy_ix_i \\ \frac{\partial L}{\partial b} = 0 \;\Rightarrow \sum\limits_{i=1}^{m}\alpha_iy_i = 0\]

    后者经过变形得到

    \[\underbrace{min}_{\alpha} \frac{1}{2}\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j) - \sum\limits_{i=1}^{m} \alpha_i \\ s.t. \; \sum\limits_{i=1}^{m}\alpha_iy_i = 0 \\ \alpha_i \geq 0 \; i=1,2,...m\]

    使用 SMO 算法 可以求出 $\alpha$,代入之前求偏导得到的那个式子,就可以得到 $w$。

    SMO 算法 相关细节建议参考 SMO 算法原理,这里不展开介绍。

  • 算法: SMO 算法

  • 应用场景: 分类

  • 输入: $(x_1^{(0)}, x_2^{(0)}, …,x_n^{(0)}, y_0), (x_1^{(1)}, x_2^{(1)}, …,x_n^{(1)},y_1), …, (x_1^{(m)}, x_2^{(m)}, …, x_n^{(m)}, y_m)$

  • 输出: 超平面 $\vec{\bf{w}} \cdot \vec{\bf{x}} + b = 0$

  • 要算什么: 主要就是 SMO 算法,算法步骤如下图,原理可参考 参考资料

(2) 更多

更多支持向量机相关模型,可以自行查阅相关资料:

  • 线性支持向量机:

    与线性可分支持向量机不同的地方在于,前者仅限于线性可分的数据,而线性支持向量机则是在前者的基础之上,增加了对线性不可分数据中异常点的处理

  • 非线性支持向量机:

    原始样本空间内也许并不存在一个能正确划分两类样本的超平面,但可将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分

  • 支持向量回归:

    将支持向量机用于回归

  • 支持向量数据描述:

    将数据从原始空间映射到特征空间,然后在特征空间中寻找一个体积最小的超球体

6. 统计学习(3):贝叶斯

(1) 朴素贝叶斯

  • 英文名: Naive Bayes

  • 原理: 前提条件是特征之间相互独立,这样就可以用贝叶斯公式 $P(Y_k \mid X) = \frac{P(X \mid Y_k)P(Y_k)}{\sum\limits_{k}P(X \mid Y =Y_k)P(Y_k)}$ 来求出 $P(category \mid characteristics)$,比如 $P(apple \mid red, fruit, sweet)$;当给出一组样本的特征时,我们可以求出在这组特征下属于每个分类的概率,然后取最大概率的分类作为结果

  • 模型: 根据贝叶斯公式有:

    \[C_{result} = \underbrace{argmax}_{C_k}P(X=X^{(test)}|Y=C_k)P(Y=C_k) \Bigg{/}P(X=X^{(test)})\]

    而分母显然和类别并没有关系,所有计算时为了简化可以忽略分母:

    \[C_{result} = \underbrace{argmax}_{C_k}P(Y=C_k)\prod_{j=1}^{n}P(X_j=X_j^{(test)}|Y=C_k)\]
  • 策略: 后验概率最大化

  • 算法: 极大似然估计(算先验概率)

  • 应用场景: 分类

  • 输入: $(x_1^{(0)}, x_2^{(0)}, …,x_n^{(0)}, y_0), (x_1^{(1)}, x_2^{(1)}, …,x_n^{(1)},y_1), …, (x_1^{(m)}, x_2^{(m)}, …, x_n^{(m)}, y_m)$

  • 输出:

    \[C_{result} = \underbrace{argmax}_{C_k}{P(Y=C_k) \cdot \prod_{j=1}^{n}{P(X_j=X_j^{(test)}} \mid {Y=C_k})}\]
  • 要算什么: 首先用极大似然估计算先验概率,然后用贝叶斯公式算后验概率

(2) 半朴素贝叶斯分类器

  • 原理: 朴素贝叶斯要求特征相互独立,而现实中有时候很难满足;对特征独立性假设进行一定程度上的放松,这就是半朴素贝叶斯分类器。主要方法是用了独依赖估计,但要算的和贝叶斯差不多,都是算概率,然后四则运算。

7. 统计学习(4):决策树

(1) 概述

  • 英文名: Decision Trees

  • 原理: 决策树模型是描述对样本进行分类的树形结构,树由结点和有向边组成,内部结点表示一个特征,叶子结点表示一个分类,有向边表示一个划分规则,且决策树的路径是互斥并且是完备的。决策树的分类过程就是对一个样本递归的测试,直到将其分配到某个叶子结点。决策树学习一般分三步:特征选择、决策树生成、剪枝。

  • 模型: 一棵树

  • 策略: 损失函数最小化

  • 算法: 三个步骤的算法,见下面的详细介绍

  • 应用场景: 分类 或 回归

  • 输入: $(x_1^{(0)}, x_2^{(0)}, …,x_n^{(0)}, y_0), (x_1^{(1)}, x_2^{(1)}, …,x_n^{(1)},y_1), …, (x_1^{(m)}, x_2^{(m)}, …, x_n^{(m)}, y_m)$

  • 输出: 生成并剪枝后的决策树

  • 要算什么: 生成部分,根据你用的生成算法,要算熵或是基尼系数;剪枝部分,要算生成算法对应的损失函数;整个流程中操作的数据结构是一棵树

(2) 特征选择

特征选择,也就是生成决策树之前,选择最优的划分属性。目前最常见的三种算法是 ID3 算法C4.5 算法CART 算法

ID3 算法 采用信息增益作为不确定度的度量,选取信息增益最大的特征进行分裂。信息增益的定义是信息熵减去条件熵,也就是 $I(X,Y) = H(X) - H(X \mid Y)$,其中 $H(X) = -\sum\limits_{i=1}^{n}p_i logp_i$。具体理论细节可以自行搜索信息熵相关内容。

C4.5 算法 则是针对 ID3 算法 的不足来提出的。前者的不足包括:无法处理连续特征,如长度密度等;相同条件下,取值比较多的特征比取值少的特征信息增益大;没有考虑缺失值;没有考虑过拟合问题。

针对第一个问题,后者将连续的特征离散化处理;对第二个,引入信息增益比代替信息增益;对第三个,分了两种情况讨论;对第四个,引入了正则化系数进行初步的剪枝。具体的细节可以看这篇文章 决策树算法原理 - 刘建平的博客

CART 算法 则是用基尼指数来度量数据的不确定度,相比于前两者,它的好处在于避免了大量的对数运算,算起来更简单,但熵所具备的优点它也没有丢失。它反映的是从数据集中随机抽取两个样本,其类别标记不一致的概率。因此,其值越小,数据集纯度越高。表达式如下:$Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2$。

(3) 决策树生成

生成算法的核心,就是递归的调用上面讲的两种特征选择算法,选择特征作为子结点,从而建立整个树。

(4) 剪枝

  • 为什么要剪枝?

    决策树生成算法生成的树往往对于训练数据拟合很准确,但是对于未知的测试数据分类却没有那么准确。即出现过拟合现象。过拟合产生得原因是决策树太复杂。解决的办法是:对决策树剪枝,即对生成的决策树进行简化。

  • 剪枝的策略?

    极小化决策树的整体损失函数。生成算法仅考虑局部最优,而剪枝算法考虑全局最优。

  • 怎么剪枝?

    两种方法,预剪枝和后剪枝。

    • 预剪枝:在构造决策树的过程中,先对每个结点在划分前进行估计,若果当前结点的划分不能带来决策树模型泛化性能的提升,则不对当前结点进行划分并且将当前结点标记为叶结点。

    • 后剪枝:后剪枝就是先把整颗决策树构造完毕,然后自底向上的对非叶结点进行考察,若将该结点对应的子树换为叶结点能够带来泛化性能的提升,则把该子树替换为叶结点。

  • 数学表示?

    这里作为入门,仅给出熵模型的剪枝依赖的损失函数,基尼系数的剪枝类似,可自行查阅相关资料,建议参考 决策树算法原理 - 刘建平的博客

    设树 $T$ 的叶子结点个数为 $\lvert T_f \rvert$,设 $T_t \quad (t = 1,2,…,\lvert T_f \rvert)$ 为树的叶子结点,每个叶结点有 $N_t$ 个样本点,其中属于 $c_k$ 类的样本点有 $N_{t,k}$ 个,$k=1,2,…,K$。

    令 $H(t)$ 为叶子结点 $T_t$ 上的经验熵,令 $\alpha \geq 0$ 为参数,则决策树 $T$ 的损失函数定义为:$C_{\alpha}(T) = \sum_{t=1}^{\lvert T_f \rvert}{N_t H(t)}+{\alpha}\lvert T_f \rvert$,其中 $H(t) = -\sum_{k=1}^{K}{\frac{N_{t,k}}{N_t}\log \frac{N_{t,k}}{N_t}}$

8. 统计学习(5):k 近邻

(1) 概述

  • 英文名: K - Nearest Neighbors

  • 原理: 顾名思义,就是从训练集里找 $k$ 个距离最近的邻居,用这些邻居的样本标签值进行多数表决(分类)或是求均值(回归),来表示测试样本的值。距离的度量可以采用欧氏距离、曼哈顿距离、闵可夫斯基距离等等。显然,对于大量样本,暴力是不现实的,一般会采用 KD 树 或是 球树KNN 的三要素为:$k$ 值选择、距离度量、决策规则。注意,这里的 $k$ 不是参数,而是 超参数

  • 模型: KD 树球树

  • 策略: 损失函数最小化

  • 算法: 实现方式两种树的算法

  • 应用场景: 分类 或 回归

  • 输入: $(x_1^{(0)}, x_2^{(0)}, …,x_n^{(0)}, y_0), (x_1^{(1)}, x_2^{(1)}, …,x_n^{(1)},y_1), …, (x_1^{(m)}, x_2^{(m)}, …, x_n^{(m)}, y_m)$

  • 输出: KD 树球树

  • 要算什么: 三要素并不需要怎么计算,需要计算的是实现两种树的算法

(2) 关于三要素

  • $k$ 的选择:

    对于 $k$ 的选择,没有一个固定的经验,一般根据样本的分布,选择一个较小的值,或者通过交叉验证选择一个合适的 $k$ 值。

    • $k$ 太小:减小学习的偏差,增大学习的方差。只有与输入样本较近的训练样本才会对预测起作用,预测结果会对近邻的样本点非常敏感;若近邻的训练样本点刚好是噪声,则预测会出错。模型整体变复杂,易发生过拟合。

    • $k$ 太大:减小学习的方差,增大学习的偏差。相当于用较大的邻域中的训练样本进行预测,输入样本较远的训练样本也会对预测起作用,使预测偏离预期的结果。

  • 距离度量:

    可以是一般的 $L_p$ 距离 $L_p(x_i,x_j)=(\sum_{l=1}^n{|x_i^{(l)}-x_j^{(l)}|^p})^{\frac{1}{p}}   (p\geq1)$,不同的距离度量所确定的最近邻点是不同的。

    • $p=1$:称为曼哈顿距离,$L_1(x_i,x_j)=\sum_{l=1}^n{\lvert x_i^{(l)}-x_j^{(l)} \rvert}$;

    • $p=2$:称为欧式距离,$L_2(x_i,x_j)=(\sum_{l=1}^n{\lvert x_i^{(l)}-x_j^{(l)} \rvert^2})^{\frac{1}{2}}$;

    • $p= \infty$:为各维度距离中最大值,$L_p(x_i, x_j) = max \lvert x_i^{(l)} - x_j^{(l)} \rvert$。

  • 决策规则:

    为了使损失函数最小,回归采用均值回归,分类采用多数表决,详细推导参考 AI 算法工程师手册 - KNN

(3) KD 树球树

  • KD 树

    在数据结构这门课中,我们学过 KD 树。它的原理大致可以理解为,通过不同维度对数据集进行切分,然后构造出一棵树;当我们需要找某个点最近的点时,只需要从该点所在叶子结点出发,不断往上,只要父结点对应的切分线和该点距离小于目前的最短距离,那就对该父结点的其他子结点进行搜索,若有更近的就更新最短距离,最后一只搜索到根结点。显然,这个算法用在 KNN 里要比暴力快多了。

    理解 KD 树 的一个经典例子是纹身兔子,建议参考这篇文章:知乎文章 - 没想到你是这样的兔子

  • 球树

    类似 KD 树,只不过每个分割块是超球体。此处不展开,建议参考 KNN 原理小结

9. 统计学习(6):集成学习

(1) 概述

  • 英文名: Ensemble Learning

  • 原理: 集成学习的思想是训练若干的个体学习器,通过一定的策略将其结合,得到一个博采众长的强学习器。显而易见,集成学习的两个要点就是如何得到若干个体学习器,以及这些学习器以何种策略结合。

(2) 获取若干个体学习器

  • 分类:

    • 同质:所有个体学习器同种类,目前集成学习一般指同质的。如 CART 决策树神经网络

      • 存在强依赖关系:因此必须串行生成,代表算法为 Boosting 系列算法

      • 不存在强依赖关系:因此可以并行生成,代表算法为 随机森林Bagging 系列算法

    • 异质:所有个体学习器不是同种类,目前较少见。

(3) 结合策略

  • 记 $T$ 个弱学习器为 ${h_1,h_2,…h_T}$。

  • 平均法

    原理:对于数值类的回归预测问题,通常对输出进行平均得到最终的预测输出,或者自定义合适的权重。 表示:若权重为 $w_i$,则 $H(x) = \sum\limits_{i=1}^{T}w_ih_i(x)$。

  • 投票法

    原理:对于分类问题,一般用投票法,也就是少数服从多数。更严格一点,需要票过半数。更复杂一点就是给投票加权重

  • 学习法

    原理:以上两种方法可能误差比较大。另一种误差相对较小的方法是学习法。我们将训练集弱学习器的学习结果作为输入,将训练集的输出作为输出,重新训练一个学习器来得到最终结果。弱学习器称为初级学习器,用于结合的学习器称为次级学习器。

(4) Boosting

  • 原理: 它的基本思想是对于一个复杂任务来说,将多个专家的判断进行适当的综合所得出的判断,要比其中任何一个专家单独的判断要好。它的理论基础是强可学习与弱可学习是等价的,即若在学习中发现了弱学习算法,则可以通过某些办法将它提升为强学习算法。它主要关注降低偏差,因此在 SVMKNN 等不容易受到样本扰动的学习器上效果更为明显。

  • 策略: 先从初始训练集训练出一个基学习器;再根据基学习器的表现对训练样本分布进行调整,使得先前基学习器做错的训练样本在后续受到更多关注;然后基于调整后的样本分布来训练下一个基学习器;如此重复,直到基学习器数量达到事先指定的值 $M$;最终将这 $M$ 个基学习器进行加权组合。

  • 相关算法: Adaboost 算法

  • 应用场景: 分类 或 回归

  • 输入: 训练数据集、弱学习算法

  • 输出: 集成模型

  • 要算什么: Adaboost 算法 每个步骤如下图所示,要算基本分类器的分类误差率,基本分类器的系数,基本分类器的线性组合,并每一次迭代要更新训练数据集的权值分布

(5) Bagging

  • 原理: 基于 自助采样法,生成训练集与测试集,训练出基学习器,再组合为集成模型。它主要关注降低方差,它能平滑强学习器的方差,因此它在非剪枝决策树、神经网络等容易受到样本扰动的学习器上效果更为明显。

  • 策略: 经过 $M$ 轮 自助采样,可以得到 $M$ 个包含 $N$ 个训练样本的采样集;然后基于每个采样集训练出一个基学习器;最后将这 $M$ 个基学习器进行组合,得到集成模型。分类任务采取简单投票法,取每个基学习器的预测类别的众数;回归任务使用简单平均法,取每个基学习器的预测值的平均。

  • 相关算法: 随机森林(它是 bagging 的一个特别升级版;升级在于随机森林中的基学习器的多样性不仅来自样本扰动,还来自属性扰动,使得最终集成的泛化性能可以通过个体学习器之间差异度的增加而进一步提升;特别在于随机森林中的弱学习器都是决策树)

  • 应用场景: 分类 或 回归

  • 输入: 训练数据集、弱学习算法

  • 输出: 集成模型

  • 要算什么: 和 boosting 不同,bagging 并不需要串行,而是并行的,因此它并不需要每次更新权重等等操作,它要算的很简单,就是每个基学习器要算的东西

10. 统计学习(7):梯度提升树

(1) 概述

  • 英文名: Gradient Boosting Decison Tree

  • 原理: 梯度提升树,顾名思义,可以拆成梯度提升和提升树两个概念的合成来理解。应该属于集成学习中 boosting 的一种。

    • 提升树:

      • 概述:

        boosting 算法的一种,以决策树为基本学习器。对分类问题,提升树中的决策树是二叉决策树;对回归问题,提升树中的决策树是二叉回归树。

      • 数学表示:

        $f(\vec{\bf{x}}) = \sum_{m=1}^{M}{h_m(\vec{\bf{x}};\Theta_m)}$。

      • 采用前向分布算法:

      • 损失函数:

        回归问题采用平方误差损失函数 $L(\tilde{y}, \hat{y}) = (\tilde{y}-\hat{y})^2$,分类问题采用指数损失函数 $L(\tilde{y}, \hat{y}) = e^{-\tilde{y} \hat{y}}$,其中 $\tilde{y}$ 和 $\hat{y}$ 分别指真实值和预测值。

      • 算法:

        以回归提升树为例:

      • 怎么理解:

        这里我觉得刚入门比较难理解的是为什么这里要学习一个回归树来拟合残差。我的理解是,我们要找一个 $f(x)$ 使得损失函数 $L(y,f(x))$ 最小,那么 $f(x)$ 应该在使损失函数减小的方向变化,也就是沿着负梯度方向,$f(x_1) = f(x) - \frac{\partial{L(y,f(x))}}{\partial{f(x)}}$。而对于提升树,最新的学习器是由当前学习器加上一个回归树,为 $f(x_1) = f(x) + T$,那么自然 $T = - \frac{\partial{L(y,f(x))}}{\partial{f(x)}}$,也就是要用损失函数对 $f(x)$ 的负梯度来拟合回归树。而这里之所以是残差,是因为这里损失函数恰好是平方损失函数,残差恰好等于负梯度。

    • 梯度提升:

      • 概述:

        提升树中,当损失函数是平方损失函数和指数损失函数时,每一步优化都很简单,因为平方损失函数和指数损失函数的求导非常简单。当损失函数是一般函数时,往往每一步优化不是很容易。针对这个问题,Freidman 提出了梯度提升算法。梯度提升树是利用梯度下降法的近似方法,其关键是利用损失函数的负梯度在当前模型的值作为残差的近似值,从而拟合一个回归树。在每一轮迭代中,首先计算出当前模型在所有样本上的负梯度,然后以该值为目标训练一个新的弱分类器进行拟合并计算出该弱分类器的权重,最终实现对模型的更新。我个人的理解是,这里的梯度提升树,和梯度下降法,核心思想是一样的,至于名字为什么看上去相反,应该是断句的问题,“梯度下降、法” 和 “梯度、提升树”,这样断句就能理解了。

  • 策略: 让损失函数 $L(y, f_{t}(x)) =L(y, f_{t-1}(x)+ h_t(x))$ 最小

  • 算法:

  • 应用场景: 回归 或 分类

  • 输入: 训练数据集 和 弱学习算法(决策树)

  • 输出: 集成模型

  • 要算什么: 决策树相关算法,以及这里用负梯度拟合回归树,需要算偏导数

(2) XGBoost

(3) LightBGM


声明:本文采用 CC BY-NC-SA 4.0 授权。

This work is licensed under a CC BY-NC-SA 4.0.

Tags: