按照一定的精简形式整理机器学习相关算法,为了能够快速回忆,也帮助自己再一次梳理一遍算法。

1. 天下没有免费的午餐

  在机器学习领域,一个基本的定理就是“没有免费的午餐”。换言之,就是没有算法能完美地解决所有问题,尤其是对监督学习而言(例如预测建模)。当然,所选的算法必须要适用于你自己的问题,这就要求选择正确的机器学习任务。作为类比,如果你需要打扫房子,你可能会用到吸尘器、扫帚或是拖把,但你绝对不该掏出铲子来挖地。

2. 偏差和方差

  偏差描述的是预测值(估计值)的期望与真实值之间的差距。偏差越大,说明越偏离真实数值。

\[\text{Bias}[\hat{f}(x)]=E[\hat{f}(x)]-f(x)\]

  方差描述的是预测值的变化范围和离散程度,即离其期望值的距离。

\[\text{Var}[\hat{f}(x)]=E\left[(\hat{f}(x)-E[\hat{f}(x)])^{2}\right]\]

  模型的真实误差则是偏差和方差的和:

\[E\left[(y-\hat{f}(x))^{2}\right]=\text{Bias}[\hat{f}(x)]^{2}+\text{Var}[\hat{f}(x)]+\sigma^{2}\]

线性回归(Linear Regression)

  • 决策函数
    • 线性计算:\(h(x) = x^T \hat{w}\)
  • 损失函数
    • 平方损失:\(\hat{w}=\text{argmin}_{w} \sum_{x, y}\left(y-x^{T} w\right)^{2}\)
  • 优化算法
    • 解析解直接计算:$\hat { w } = \left( \gamma \mathbf { I } + X ^ { T } X \right) ^ { - 1 } X ^ { T } y$
    • 逆不存在可以用梯度下降:
      1. 输入 $X$, $y$, 初始化权重 $w_0$
      2. 计算损失函数对参数 $w$ 的偏导并迭代更新
      3. 达到最大迭代次数,或者损失降低到一定程度退出
  • 优点
    • 实现简单,计算简单。
  • 缺点
    • 不能拟合非线性数据。
    • 对异常值非常敏感。

逻辑斯特回归(Logistic Regression)

  • 决策函数
    • $h(x) = {1\over{1+e^{-x^T w}}} = p$
  • 损失函数
    • 交叉熵损失:\(\begin{aligned} \hat{w} &= \text{argmin}_{w} ~J(w)\\ &= \text{argmin}_{w} ~ -{1\over{m}}\sum_{i=1}^m\left( y \ln p + \left(1 - y \right)\ln \left(1 - p \right) \right) \end{aligned}\)
  • 优化算法
    • 梯度提升算法:${\partial J \over \partial w} = -{1\over{m}} \sum_{i=1}^m\left( y_i - h(x_i)\right) x_i$
  • 优点
  • 缺点

支持向量机 (Support Vector Machines)

-w618

\[r=\frac{\left|\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\right|}{\|\boldsymbol{w}\|}\] \[\left\{\begin{array}{ll}{\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \geqslant+1,} & {y_{i}=+1} \\ {\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \leqslant-1,} & {y_{i}=-1}\end{array}\right.\] \[\gamma=\frac{2}{\|\boldsymbol{w}\|}\]

-w366

\[\begin{array}{l}{\max _{\boldsymbol{w}, b} \frac{2}{\|\boldsymbol{w}\|}} \\ {\text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m}\end{array}\] \[\begin{array}{l}{\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}} \\ {\text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m}\end{array}\] \[L(\boldsymbol{w}, b, \boldsymbol{\alpha})=\frac{1}{2}\|\boldsymbol{w}\|^{2}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right)\] \[\begin{aligned} \boldsymbol{w} &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i} \\ 0 &=\sum_{i=1}^{m} \alpha_{i} y_{i} \end{aligned}\] \[\begin{array}{ll}{\max _{\boldsymbol{\alpha}}} & {\sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}} \\ {\text { s.t. }} & {\sum_{i=1}^{m} \alpha_{i} y_{i}=0} \\ {} & {\alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m}\end{array}\] \[\begin{aligned} f(\boldsymbol{x}) &=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b \\ &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}+b \end{aligned}\] \[\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \max \left(0,1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right)\] \[\begin{array}{ll}{\min _{\boldsymbol{w}, b, \xi_{i}}} & {\frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \xi_{i}} \\ {\text { s.t. }} & {y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1-\xi_{i}} \\ {} & {\xi_{i} \geqslant 0, i=1,2, \ldots, m}\end{array}\] \[\begin{aligned} L(\boldsymbol{w}, b, \boldsymbol{\alpha}, \boldsymbol{\xi}, \boldsymbol{\mu})=& \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \xi_{i} \\ &+\sum_{i=1}^{m} \alpha_{i}\left(1-\xi_{i}-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right)-\sum_{i=1}^{m} \mu_{i} \xi_{i} \end{aligned}\] \[\begin{aligned} \boldsymbol{w} &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i} \\ 0 &=\sum_{i=1}^{m} \alpha_{i} y_{i} \\ C &=\alpha_{i}+\mu_{i} \end{aligned}\] \[\begin{aligned} \max _{\boldsymbol{\alpha}} & \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j} \\ \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ & 0 \leqslant \alpha_{i} \leqslant C, \quad i=1,2, \ldots, m \end{aligned}\]

技巧性问题

如何解决过拟合问题?

  • 正则化

如何应对类别不平衡的问题?

算法表格汇总

算法 类型 是否支持多分类 决策函数 优化目标 求解算法
Adaboost 有监督
判别模型
非线性
不直接支持 $\begin{array}{l}{F(\mathrm{x})=\sum_{t=1}^{T} \alpha_{t} f_{t}(\mathrm{x})} \ {\operatorname{sgn}(F(\mathrm{x}))}\end{array}$ $\min _{F} \mathrm{E}(\exp (-y F(\mathrm{x})))$ 分阶段优化
公式解
           

References

  1. 机器学习算法优缺点对比及选择(汇总篇)
  2. 机器学习面试
  3. 贝叶斯思想以及与最大似然估计、最大后验估计的区别
  4. 我几乎面了所有知名公司的算法岗位