机器学习简介

机器学习是让机器从数据中学习规律并预测。

组成上包括：输入、输出、目标函数、数据、假设空间、样本、训练集、测试集、验证集

三类误差：

  • 逼近误差：假设空间与目标函数的误差
  • 估计误差：数据集支持的函数集与假设空间的误差
  • 优化误差：特定训练算法优化的函数与数据集支持的函数集的误差

机器学习的分类：

  • 分类问题：有监督、离散数据
  • 回归问题：有监督、连续数据
  • 聚类问题：无监督、离散数据
  • 嵌入问题：无监督、连续数据

机器学习的表现：欠拟合、拟合、过拟合

机器学习的相关问题：

  • 奥卡姆剃刀
  • 没有免费的午餐：没有一个通用的模型、且是最好的模型。
  • All models are wrong, but some are useful
  • 没有免费的午餐：没有一个通用的模型、且是最好的模型。

分类算法 KNN

模型

超参数K

训练

无

预测

对于一个样本，找到距离最近的K个样本，然后统计这K个样本的类别，返回出现次数最多的那个类别作为预测结果

分类算法 决策树

模型

一颗决策树，边为决策特征，叶子为决策结果

训练

即构建决策树

ID3

考虑信息熵$H(D) = -\sum_{i=1}^n p_i \log_2 p_i$，对每个特征计算条件熵$H(D|f_i) = -\sum_{j=1}^n p_{ij} \log_2 p_{ij}$，贪心选取决策特征，使得信息增益$IG(D|f_i) = H(D) - H(D|f_i)$最大。

C4.5

对于连续数据，选取离散点作为分割点，计算信息增益比$IG(D|f_i) = \frac{H(D) - H(D|f_i)}{H(D)}$，贪心选取决策特征，使得信息增益比最大。

具有缺失值的样本在进行数据分裂时，分配给哪个子数据集？

  • 忽略该类样本
  • 选择常用值或均值填充
  • 根据其他非缺失属性的比例，分配到子数据集中
  • 为缺失值建立单独分支
  • 确定最可能的取值，按比例仅分配给一个子数据集

优化

预剪枝：选取决策特征时如果使得对测试集的错误率下降，则保留。 后剪枝：对决策节点如果不决策反而使得测试集的错误率下降，则剪掉。

alt text

预测

沿决策树下降，到叶子节点返回结果

分类算法 朴素贝叶斯

模型

假定特征独立

训练

无

预测

计算预测样本的值类别相对于给定训练集的后验概率。其中训练集样本特征值关于给定类别的先验概率和类别概率已知，通过贝叶斯公式和假设即求。

二分类算法 Logistic回归

模型

对激活函数Sigmoid$\sigma(x) = \frac{1}{1 + e^{-x}}$，计算属于1类概率为$f(x) = \sigma (\mathbf{\theta} * \mathbf{x} ^ T)$

Sigmoid将函数的输入范围$(-∞,∞)$映射到了输出的$(0,1)$之间且具有概率意义。

训练

对似然函数$L(\theta) = \Pi f(x_i)^{y_i} (1-f(x_i))^{1-y_i}$，通过极大似然估计优化参数$\theta$。采用梯度下降法，迭代更新$\theta$。

改进

随机梯度上升法：每个回归系数初始化为1。对数据集中每个样本，使用该样本梯度更新回归系数值。

预测

计算$f(x)$的值，大于0.5则为1类，否则为0类。

二分类算法 支持向量机

模型

寻找超平面$\mathbf{w} * \mathbf{x} ^ T + \mathbf{b} = 0$，使得$\mathbf{w} * \mathbf{x_{+}} ^ T + \mathbf{b} \ge 1, \mathbf{w} * \mathbf{x_{-}} ^ T + \mathbf{b} \le -1$。

转化为要求$min \|\|\mathbf{w}\|\|$的带约束的二次规划模型。

软间隔

去掉一些样本仍线性可分时，加入松弛变量及其惩罚：

松弛变量的不同取值含义：

  • $\xi = 0$时，样本正确分类；
  • $\xi \in (0, 1)$时，样本在两个夹板间隔之间；
  • $\xi \ge 1$时，样本点异常。

非线性

使用核函数$\phi(\mathbf{x}) = \sum_{i = 1}^k \alpha_i K(\mathbf{x}, \mathbf{x_i})$等将样本映射到高维空间。

训练

对误差函数$E(\mathbf{w}, \mathbf{b}) = \frac{1}{2} \sum_{i = 1}^m \xi_i$，通过梯度下降法，迭代更新$\mathbf{w}$和$\mathbf{b}$。

SMO算法

每次循环中选择2个α 进行优化处理

预测

计算超平面$\mathbf{w} * \mathbf{x} ^ T + \mathbf{b}$的值，大于0则为1类，否则为0类。

分类增强 AdaBoost

模型

对于给定的若干弱训练器，希望通过线性组合$f(x) = \sum_{i = 1}^n \alpha_i f_i(x)$，通过经过符号函数变为强训练器。

训练

  1. 计算弱训练器误差率$e_i = P(y \neq f_i(x))$
  2. 选取最小误差率的弱训练器并更新样本权重$w_i^\prime = \begin{cases} \frac{w_i}{2e_i} & 正确分类 \\ \frac{w_i}{2(1-e_i)} & 错误分类 \end{cases}$
  3. 计算该弱训练器的权重$\alpha_i = \frac{1}{2} \log \frac{1 - e_i}{e_i}$

预测

直接计算

回归算法 线性回归

即利用最小二乘法

局部加权线性回归

采用核函数来度量样本间的距离。如高斯核$W(x, x') = exp(-\frac{|x - x'|^2}{2\sigma^2})$

岭回归

额外加一个单位矩阵作为惩罚性，减少不必要的参数

前向逐步回归 lasso法

使用L1范数度量误差。

回归算法 树回归

模型

一颗必为二叉树的回归树，边为特征分界值，叶子为决策结果。

训练

即构建回归树。通过最小化方差的分界值来构建树。

预测

直接计算

聚类算法 k-means

模型

超参数k，预先指定k个质心

训练

通过距离度量将样本分配到最近的质心，然后重新计算质心。若干次迭代或直至质心不再发生变化。度量通常取L2范数。

预测

计算属于哪个质心。

2分K-means

将所有的点作为一个簇，然后选择可以使得误差最大程度降低的簇一分为二。不断循环到满足簇数目为止。

Apriori关联分析

频繁项集：如果某个项集是频繁的，那么它的所有子集也是频繁的。可以通过前k-2个项相同的k-1项项集来构建k项项集。

支持度：某个项集出现的次数和样本数的比值。

关联规则：频繁项集二分得到，写作$A \rightarrow B$。其可信度为$\frac{频繁项集支持度}{A的支持度}$

降维算法 主成分分析(PCA)

模型

选取样本方差最大的维度，将其他维度映射到该维度上。

训练

无

计算

  1. 去平均值，即每一位特征减去各自的平均值
  2. 计算协方差矩阵，并得到其特征值与特征向量。
  3. 对特征值从大到小排序，选择其中最大的k个。然后将其对应的k个特征向量分别作为行向量组成特征向量矩阵P。
  4. 将数据通过乘积转换到k个特征向量构建的新空间中。

反向传播神经网络

模型

每个节点模拟神经元，其值为$f(x) = t(\mathbf{w}^T * \mathbf{x} + b)$，x为输入或上一层的输出，其中$t(x)$为激活函数，常见有：

  • Sigmoid$t(x) = \frac{1}{1 + e^{-x}}$，特点是连续可导，但输出恒大于0，导致梯度下降的收敛速度变慢，且梯度消失
  • tanh$t(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}}$，特点是连续可导，改进了Sigmoid，输出为$(-1, 1)$，但梯度消失
  • ReLU$t(x) = \max(0, x)$，特点是简单，模拟神经元一半激活，但非零中心，设置不当不能被激活
  • LReLU$t(x) = \max(\alpha x, x)$
  • PReLU$t(x) = \max(0, x) + \min(0, \alpha x)$

最后的节点就是输出/预测，通过损失函数计算误差，常见的有：

  • 0-1损失函数$L(y, \hat{y}) = \begin{cases} 0 & y = \hat{y} \\ 1 & y \neq \hat{y} \end{cases}$，问题是非凸函数，不太适用，且相等这个条件太过严格
  • 平方损失函数$L(y, \hat{y}) = (y - \hat{y})^2$，经常应用于回归问题
  • 绝对损失函数$L(y, \hat{y}) = \|y - \hat{y}\|$
  • 绝对损失函数$L(Y, P(Y\mid X)) = -log(P(Y\mid X))$，能非常好的表征概率分布，适合置信度

计算

沿着前向传播，计算每个节点的值。

训练

梯度下降

同前

反向传播

$\Delta w = -\eta \frac{\partial L}{\partial w}$

后者满足链式法则。