盒子
盒子
文章目录
  1. 机器学习
    1. 1. 逻辑回归（LR）
      1. 1.1 基本原理
      2. 1.2 为什么 LR 要使用 sigmoid 函数？
      3. 1.3 LR 可以用核函数么？
      4. 1.4 为什么 LR 用交叉熵损失而不是平方损失？
      5. 1.5 LR 能否解决非线性分类问题？
      6. 1.6 LR为什么要离散特征？
      7. 1.7 逻辑回归是处理线性问题还是非线性问题的？
    2. 2. 线性回归
      1. 2.1 线性回归与逻辑回归（LR）的区别
    3. 3. 支持向量机（SVM）
      1. 3.1 基本原理
      2. 3.2 支持向量中的向量是指什么？
      3. 3.3 SVM为什么会对缺失值敏感？实际应用时候你是如何处理？
      4. 3.4 SVM为什么可以分类非线性问题？
      5. 3.5 手推SVM
      6. 3.6 LR 与 SVM的区别和联系
      7. SVM 中有哪些核函数？
      8. SVM 的对偶问题
      9. SMO 算法原理
      10. SVM 中的优化技术有哪些？
      11. SVM 的惩罚系数如何确定？
      12. 正则化参数对支持向量数的影响
      13. 如何解决线性不可分问题？
      14. 软间隔和硬间隔
      15. Hinge Loss
    4. 梯度提升树（GBDT）
      1. 基本原理
    5. AdaBoost
      1. 基本原理
      2. GBDT 和 AdaBoost 区别
    6. XGBoost
      1. 基本原理
      2. XGBoost里处理缺失值的方法
      3. XGBoost 和 GBDT 的区别
      4. XGBoost 如何做到自定义损失函数？
      5. XGBoost 如何防止过拟合？
      6. XGBoost 为什么不用后剪枝？
      7. XGBoost 是如何实现并行的？
      8. XGBoost 有哪些参数，取指范围，各代表什么意思？
      9. XGBoost 如何进行并行加速的？
      10. 每次分裂叶子节点是怎么决定特征和分裂点的？
      11. Adaboost、GBDT与XGBoost的区别
    7. LightGBM
      1. 基本原理
      2. LightGBM 与 XGBoost 的区别
      3. GBDT、LightGBM 和 XGBoost 区别
      4. 基本原理
    8. K-Means
      1. 基本原理
      2. 手撕 K-Means
      3. K-Means 与 KNN 的区别
      4. K-Means 中的 K 怎么确定？
      5. K-Means 的迭代循环停止条件
      6. 评判聚类效果准则
    9. Bagging
      1. 基本原理
    10. Boosting
      1. 基本原理
      2. Bagging 和 Boosting 的区别
    11. 朴素贝叶斯
      1. 基本原理
      2. 为什么朴素贝叶斯被称为“朴素”？
    12. EM 算法
      1. 基本原理
      2. E 步和 M 步的具体步骤
      3. E 中的期望是什么？
    13. 决策树
      1. 基本原理
      2. 决策树如何剪枝？
      3. 决策树先剪枝还是后剪枝好？
      4. 决策树能否有非数值型变量？
      5. 决策树如何防止过拟合？
      6. 决策树的ID3和C4.5介绍一下
    14. 随机森林（RF）
      1. 基本原理
      2. 随机森林中的“随机”指什么？
      3. 随机森林处理缺失值的方法
      4. 随机森林和 GBDT 的区别
      5. 随机森林与决策树关系
    15. CART回归树是怎么实现的？
    16. CART分类树和ID3以及C4.5有什么区别？
    17. 机器学习中的分类、回归和聚类模型有哪些？
    18. 高斯混合模型（GMM）
    19. 马尔科夫随机场（MRF）
      1. 基本原理
    20. 隐马尔科夫模型（HMM）
      1. 基本原理
      2. 发射概率和状态转移概率
      3. 每层要记住所有路径吗？
    21. 条件随机场（CRF）
      1. 基本原理
      2. CRF 的损失函数是什么？
      3. HMM、MEMM vs CRF 对比？
    22. 主成分分析（PCA）
      1. 基本原理
    23. 线性判别分析（LDA）
    24. 奇异值分解（SVD）
      1. 基本原理
      2. 手撕 SVD
      3. 特征值和SVD的区别
    25. 凸优化
      1. 基本原理
    26. 神经网络
    27. Accuracy、Precision、Recall和 F1 Score
    28. 正则化方法
      1. L1和L2正则化
      2. L1 和 L2 正则化的区别
      3. 机器学习中常常提到的正则化到底是什么意思？
      4. 为什么 L2 正则化可以防止过拟合？
    29. 过拟合和欠拟合
      1. 基本原理
      2. 如何防止过拟合？
      3. 如何防止欠拟合？
    30. 精确率（Precision）和召回率（Recall）
    31. AUC 和 ROC
      1. 基本原理
      2. 如何绘制ROC曲线？
      3. ROC曲线下面积表示什么？
      4. 手撕 AUC 曲面面积代码
    32. 梯度弥散和梯度爆炸
    33. 什么是参数范数惩罚？
    34. 为什么要进行归一化？优点？
    35. CCA和PCA的区别
    36. Softmax
      1. 基本原理
      2. Softmax是和什么loss function配合使用？
      3. Softmax代码实现
    37. 交叉熵损失函数
    38. 通俗解释一下信息熵
    39. 如何加快梯度下降收敛速度？
    40. 如何解决正负样本数量不均衡？
    41. 如何解决异常值问题？
    42. 机器学习中使用正则化来防止过拟合是什么原理？
    43. 机器学习中常常提到的正则化到底是什么意思？
    44. 梯度下降陷入局部最优有什么解决办法
    45. 聚类算法中的距离度量有哪些？
    46. KL 散度和交叉熵的区别
    47. 降维的方法都有哪些？
    48. TODO

面试

2021.03.16 Lixin  热度 ℃

[TOC]

机器学习

1. 逻辑回归（LR）

1.1 基本原理

逻辑回归（Logistic Regression，LR）也称为”对数几率回归”，又称为”逻辑斯谛”回归。

1.1.1 知识点提炼

  • 分类，经典的二分类算法！
  • 逻辑回归就是这样的一个过程：面对一个回归或者分类问题，建立代价函数，然后通过优化方法迭代求解出最优的模型参数，然后测试验证我们这个求解的模型的好坏。
  • Logistic 回归虽然名字里带“回归”，但是它实际上是一种分类方法，主要用于两分类问题（即输出只有两种，分别代表两个类别）
  • 回归模型中，y 是一个定性变量，比如 y = 0 或 1，logistic 方法主要应用于研究某些事件发生的概率。
  • 逻辑回归的本质：极大似然估计
  • 逻辑回归的激活函数：Sigmoid
  • 逻辑回归的代价函数：交叉熵

逻辑回归的优缺点

优点：

1）速度快，适合二分类问题

2）简单易于理解，直接看到各个特征的权重

3）能容易地更新模型吸收新的数据

缺点：

对数据和场景的适应能力有局限性，不如决策树算法适应性那么强

逻辑回归中最核心的概念是 Sigmoid 函数，Sigmoid函数可以看成逻辑回归的激活函数。

下图是逻辑回归网络：

Logistic Regression.png

对数几率函数（Sigmoid）：$y = \sigma (z) = \frac{1}{1+e^{-z}}$

通过对数几率函数的作用，我们可以将输出的值限制在区间[0，1]上，$p(x)$ 则可以用来表示概率 p(y=1|x)，即当一个x发生时，y被分到1那一组的概率。可是，等等，我们上面说 y 只有两种取值，但是这里却出现了一个区间[0, 1]，这是什么鬼？？其实在真实情况下，我们最终得到的y的值是在 [0, 1] 这个区间上的一个数，然后我们可以选择一个阈值，通常是 0.5，当 y > 0.5 时，就将这个 x 归到 1 这一类，如果 y< 0.5 就将 x 归到 0 这一类。但是阈值是可以调整的，比如说一个比较保守的人，可能将阈值设为 0.9，也就是说有超过90%的把握，才相信这个x属于 1这一类。了解一个算法，最好的办法就是自己从头实现一次。下面是逻辑回归的具体实现。

Regression 常规步骤

  1. 寻找h函数（即预测函数）
  2. 构造J函数（损失函数）
  3. 想办法（迭代）使得J函数最小并求得回归参数（θ）

函数h(x)的值有特殊的含义，它表示结果取1的概率，于是可以看成类1的后验估计。因此对于输入x分类结果为类别1和类别0的概率分别为：

$P(y=1│x;θ)=hθ (x) $

$P(y=0│x;θ)=1-hθ (x)$

代价函数

逻辑回归一般使用交叉熵作为代价函数。关于代价函数的具体细节，请参考代价函数。

交叉熵是对「出乎意料]的度量。神经元的目标是去计算函数 $y$, 且 $y = y(x)$。但是我们让它取而代之计算函数 a, 且 a = a(x) 。假设我们把 a 当作 y 等于 1 的概率，1−a 是 y 等于 0 的概率。那么，交叉熵衡量的是我们在知道 y 的真实值时的平均「出乎意料」程度。当输出是我们期望的值，我们的「出乎意料」程度比较低；当输出不是我们期望的，我们的「出乎意料」程度就比较高。

交叉熵代价函数如下所示：

注：为什么要使用交叉熵函数作为代价函数，而不是平方误差函数？请参考：逻辑回归算法之交叉熵函数理解

逻辑回归伪代码

1
2
3
4
5
6
7
8
初始化线性函数参数为1
构造sigmoid函数
重复循环I次
	计算数据集梯度
	更新线性函数参数
确定最终的sigmoid函数
输入训练（测试）数据集
运用最终sigmoid函数求解分类

逻辑回归算法之Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import numpy as np
from sklearn import datasets
import os
import sys
sys.path.insert(0, os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
from utils import train_test_split, accuracy_score
from utils import Plot

def sigmoid(x):
    return 1 / (1 + np.exp(-x))


class LogisticRegression():
    def __init__(self, learning_rate=.1, n_iterations=4000):
        self.learning_rate = learning_rate
        self.n_iterations = n_iterations

    def initialize_weights(self, n_features):
        limit = np.sqrt(1 / n_features)
        w = np.random.uniform(-limit, limit, (n_features, 1))
        b = 0
        self.w = np.insert(w, 0, b, axis=0)

    def fit(self, X, y):
        m_samples, n_features = X.shape
        self.initialize_weights(n_features)
        # 为X增加一列特征x1，x1 = 0
        X = np.insert(X, 0, 1, axis=1)
        y = np.reshape(y, (m_samples, 1))

        # 梯度训练n_iterations轮
        for i in range(self.n_iterations):
            h_x = X.dot(self.w)
            y_pred = sigmoid(h_x)
            w_grad = X.T.dot(y_pred - y)
            self.w = self.w - self.learning_rate * w_grad

    def predict(self, X):
        X = np.insert(X, 0, 1, axis=1)
        h_x = X.dot(self.w)
        y_pred = np.round(sigmoid(h_x))
        return y_pred.astype(int)

参考资料

1.2 为什么 LR 要使用 sigmoid 函数？

1.广义模型推导所得
2.满足统计的最大熵模型
3.性质优秀，方便使用（Sigmoid函数是平滑的，而且任意阶可导，一阶二阶导数可以直接由函数值得到不用进行求导，这在实现中很实用）

参考资料

1.3 LR 可以用核函数么？

LR是可以使用核函数，但是通常没有不会这么干。原因如下：

核方法用于分类的时候用的是hinge loss，可以方便的转化为对偶形式求解，也就是SVM。

逻辑回归中交叉熵这个损失函数，对kernel methods来说可能有点伤…转化易求解的形式比较难，而且损失是不是凹函数都不一定。

但，如果分类函数为逻辑函数运用于rkhs方程上，还是可以用剃度方法求解的，但是就没有解析解了。svm的理论保障不知道容不容易适用这种情况。

参考资料

逻辑回归为什么不用核函数呢？

1.4 为什么 LR 用交叉熵损失而不是平方损失？

logistic回归和softmax回归使用交叉熵而不用欧氏距离是因为前者的目标函数是凸函数，可以求得全局极小值点；用欧氏距离则无法保证。

1.5 LR 能否解决非线性分类问题？

逻辑回归本质上是线性回归模型，关于系数是线性函数，分离平面无论是线性还是非线性的，逻辑回归其实都可以进行分类。对于非线性的，需要自己去定义一个非线性映射。

参考资料

1.6 LR为什么要离散特征？

  1. 在工业界很少直接将连续值作为逻辑回归模型的特征输入，而是将连续特征离散化为一系列 0/1 的离散特征。

    其优势有：

    • 离散化之后得到的稀疏向量，内积乘法运算速度更快，计算结果方便存储。

    • 离散化之后的特征对于异常数据具有很强的鲁棒性。

      如：销售额作为特征，当销售额在 [30,100) 之间时，为1，否则为 0。如果未离散化，则一个异常值 10000 会给模型造成很大的干扰。由于其数值较大，它对权重的学习影响较大。

    • 逻辑回归属于广义线性模型，表达能力受限，只能描述线性关系。特征离散化之后，相当于引入了非线性，提升模型的表达能力，增强拟合能力。

      假设某个连续特征 $j$ ，它离散化为 $M$ 个 0/1 特征 $j_{1}, j_{2}, \cdots, j_{M}$ 。则：$w_{j} x_{j} \rightarrow w_{j_{1}} x_{j_{1}}^{\prime}+w_{j_{2}} x_{j_{2}}^{\prime}+\cdots+w_{j_{M}} x_{j_{M}}^{\prime}$ 。其中 $x_{j_{1}}^{\prime}, \cdots, x_{j_{\mu}}^{\prime}$ 是离散化之后的新的特征，它们的取值空间都是 $\{0,1\}$ 。

      上式右侧是一个分段线性映射，其表达能力更强。

    • 离散化之后可以进行特征交叉。假设有连续特征 $j$，离散化为 $M$ 个 0/1 特征；连续特征 $k$，离散化为 $N$ 个 0/1 特征，则分别进行离散化之后引入了 $M+N$ 个特征。

      假设离散化时，并不是独立进行离散化，而是特征 $M+N$ 联合进行离散化，则可以得到 $M\times N$ 个组合特征。这会进一步引入非线性，提高模型表达能力。

    • 离散化之后，模型会更稳定。

      如对销售额进行离散化，[30,100) 作为一个区间。当销售额在40左右浮动时，并不会影响它离散化后的特征的值。

      但是处于区间连接处的值要小心处理，另外如何划分区间也是需要仔细处理。

  2. 特征离散化简化了逻辑回归模型，同时降低模型过拟合的风险。

    能够对抗过拟合的原因：经过特征离散化之后，模型不再拟合特征的具体值，而是拟合特征的某个概念。因此能够对抗数据的扰动，更具有鲁棒性。

    另外它使得模型要拟合的值大幅度降低，也降低了模型的复杂度。

1.7 逻辑回归是处理线性问题还是非线性问题的？

逻辑回归本质上是线性回归模型，关于系数是线性函数，分离平面无论是线性还是非线性的，逻辑回归其实都可以进行分类。对于非线性的，需要自己去定义一个非线性映射。

2. 线性回归

2.1 线性回归与逻辑回归（LR）的区别

不同点：

  • 逻辑回归处理的是分类问题，线性回归处理的是回归问题；
  • 逻辑回归中认为y是因变量，即逻辑回归的因变量是离散的，线性回归的因变量是连续的。

相同点：

  • 二者都使用了极大似然估计来对训练样本进行建模
  • 求解超参数过程中，都可以使用梯度下降的方法

联系：

如果把一个事件的几率（odds）定义为该事件发生的概率与不发生概率的比值 $\frac{p}{1-p}$ ，那么逻辑回归可以看做是对于”y=1|x”这一事件的对数几率的线性回归

参考资料

3. 支持向量机（SVM）

3.1 基本原理

支持向量机（supporr vector machine，SVM）是一种二类分类模型，该模型是定义在特征空间上的间隔最大的线性分类器。间隔最大使它有区别于感知机；支持向量机还包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的最小化问题。

3.1.1 知识点提炼：

  • SVM核函数
    • 多项式核函数
    • 高斯核函数
    • 字符串核函数
  • SMO
  • SVM损失函数

支持向量机的学习算法是求解凸二次规划的最优化算法。

支持向量机学习方法包含构建由简至繁的模型：

  • 线性可分支持向量机
  • 线性支持向量机
  • 非线性支持向量机（使用核函数）

当训练数据线性可分时，通过硬间隔最大化（hard margin maximization）学习一个线性的分类器，即线性可分支持向量机，又成为硬间隔支持向量机；

当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization）也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；

当训练数据不可分时，通过核技巧（kernel trick）及软间隔最大化，学习非线性支持向量机。

注：以上各SVM的数学推导应该熟悉：硬间隔最大化（几何间隔）—-学习的对偶问题—-软间隔最大化（引入松弛变量）—-非线性支持向量机（核技巧）。

3.1.2 SVM的主要特点

（1）非线性映射-理论基础

（2）最大化分类边界-方法核心

（3）支持向量-计算结果

（4）小样本学习方法

（5）最终的决策函数只有少量支持向量决定，避免了“维数灾难”

（6）少数支持向量决定最终结果—->可“剔除”大量冗余样本+算法简单+具有鲁棒性（体现在3个方面）

（7）学习问题可表示为凸优化问题—->全局最小值

（8）可自动通过最大化边界控制模型，但需要用户指定核函数类型和引入松弛变量

（9）适合于小样本，优秀泛化能力（因为结构风险最小）

（10）泛化错误率低，分类速度快，结果易解释

SVM为什么采用间隔最大化？

当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开。

感知机利用误分类最小策略，求得分离超平面，不过此时的解有无穷多个。

线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解是唯一的。另一方面，此时的分隔超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。

然后应该借此阐述，几何间隔，函数间隔，及从函数间隔—>求解最小化1/2 ||w||^2 时的w和b。即线性可分支持向量机学习算法—最大间隔法的由来。

为什么要将求解SVM的原始问题转换为其对偶问题？

  1. 对偶问题往往更易求解（当我们寻找约束存在时的最优点的时候，约束的存在虽然减小了需要搜寻的范围，但是却使问题变得更加复杂。为了使问题变得易于处理，我们的方法是把目标函数和约束全部融入一个新的函数，即拉格朗日函数，再通过这个函数来寻找最优点。）
  2. 自然引入核函数，进而推广到非线性分类问题

为什么SVM要引入核函数？

当样本在原始空间线性不可分时，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。

SVM核函数有哪些？

  • 线性（Linear）核函数：主要用于线性可分的情形。参数少，速度快。
  • 多项式核函数
  • 高斯（RBF）核函数：主要用于线性不可分的情形。参数多，分类结果非常依赖于参数。
  • Sigmoid核函数
  • 拉普拉斯（Laplac）核函数

注：如果feature数量很大，跟样本数量差不多，建议使用LR或者Linear kernel的SVM。如果feature数量较少，样本数量一般，建议使用Gaussian Kernel的SVM。

SVM如何处理多分类问题？

一般有两种做法：

  1. 直接法：直接在目标函数上修改，将多个分类面的参数求解合并到一个最优化问题里面。看似简单但是计算量却非常的大。

  2. 间接法：对训练器进行组合。其中比较典型的有一对一，和一对多。

    • 一对多：对每个类都训练出一个分类器，由svm是二分类，所以将此而分类器的两类设定为目标类为一类，其余类为另外一类。这样针对k个类可以训练出k个分类器，当有一个新的样本来的时候，用这k个分类器来测试，那个分类器的概率高，那么这个样本就属于哪一类。这种方法效果不太好，bias比较高。
    • 一对一：针对任意两个类训练出一个分类器，如果有k类，一共训练出C(2,k) 个分类器，这样当有一个新的样本要来的时候，用这C(2,k) 个分类器来测试，每当被判定属于某一类的时候，该类就加一，最后票数最多的类别被认定为该样本的类。

SVM中硬间隔和软间隔

硬间隔分类即线性可分支持向量机，软间隔分类即线性不可分支持向量机，利用软间隔分类时是因为存在一些训练集样本不满足函数间隔（泛函间隔）大于等于1的条件，于是加入一个非负的参数 ζ （松弛变量），让得出的函数间隔加上 ζ 满足条件。于是软间隔分类法对应的拉格朗日方程对比于硬间隔分类法的方程就多了两个参数（一个ζ ，一个 β），但是当我们求出对偶问题的方程时惊奇的发现这两种情况下的方程是一致的。下面我说下自己对这个问题的理解。

我们可以先考虑软间隔分类法为什么会加入ζ 这个参数呢？硬间隔的分类法其结果容易受少数点的控制，这是很危险的，由于一定要满足函数间隔大于等于1的条件，而存在的少数离群点会让算法无法得到最优解，于是引入松弛变量，从字面就可以看出这个变量是为了缓和判定条件，所以当存在一些离群点时我们只要对应给他一个ζi，就可以在不变更最优分类超平面的情况下让这个离群点满足分类条件。

综上，我们可以看出来软间隔分类法加入ζ 参数，使得最优分类超平面不会受到离群点的影响，不会向离群点靠近或远离，相当于我们去求解排除了离群点之后，样本点已经线性可分的情况下的硬间隔分类问题，所以两者的对偶问题是一致的。

3.2 支持向量中的向量是指什么？

3.3 SVM为什么会对缺失值敏感？实际应用时候你是如何处理？

涉及到距离度量(distance measurement)时，如计算两个点之间的距离，缺失数据就变得比较重要。如果缺失值处理不当就会导致效果很差，如SVM，KNN。

常用的缺失值处理方法：

（1）把数值型变量(numerical variables)中的缺失值用其所对应的类别中(class)的中位数(median)替换。把描述型变量(categorical variables)缺失的部分用所对应类别中出现最多的数值替代(most frequent non-missing value)。【快速简单但效果差】（平均数、中位数、众数、插值等）

（2）将缺失值当成新的数值，NaN

（3）忽略该项数据（当缺失少时）

3.4 SVM为什么可以分类非线性问题？

原输入空间是一个非线性可分问题，能用一个超曲面将正负例正确分开；

通过核技巧的非线性映射，将输入空间的超曲面转化为特征空间的超平面，原空间的非线性可分问题就变成了新空间的的线性可分问题。低维映射到高维。

在核函数 $K(x,z)$ 给定的条件下，可以利用解线性分类问题的方法求解非线性分类问题的支持向量机。学习是隐式地在特征空间进行的，在学习和预测中只定义核函数 $K(x,z)$，而不需要显式地定义特征空间和映射函数$\phi$，这样的技巧成为核技巧。通常直接计算$K(x,z)$比较容易，而通过$\phi(x)$和$\phi(z)$计算$K(x,z)$并不容易。

对于给定核 $K(x,z)$，特征空间和映射函数的取法并不唯一。

3.5 手推SVM

参考资料

3.6 LR 与 SVM的区别和联系

相同点

第一，LR和SVM都是分类算法。

看到这里很多人就不会认同了，因为在很大一部分人眼里，LR是回归算法。我是非常不赞同这一点的，因为我认为判断一个算法是分类还是回归算法的唯一标准就是样本label的类型，如果label是离散的，就是分类算法，如果label是连续的，就是回归算法。很明显，LR的训练数据的label是“0或者1”，当然是分类算法。其实这样不重要啦，暂且迁就我认为它是分类算法吧，再说了，SVM也可以回归用呢。

第二，如果不考虑核函数，LR和SVM都是线性分类算法，也就是说他们的分类决策面都是线性的。

这里要先说明一点，那就是LR也是可以用核函数的，至于为什么通常在SVM中运用核函数而不在LR中运用，后面讲到他们之间区别的时候会重点分析。总之，原始的LR和SVM都是线性分类器，这也是为什么通常没人问你决策树和LR什么区别，决策树和SVM什么区别，你说一个非线性分类器和一个线性分类器有什么区别？

第三，LR和SVM都是监督学习算法。

这个就不赘述什么是监督学习，什么是半监督学习，什么是非监督学习了。

第四，LR和SVM都是判别模型。

判别模型会生成一个表示P(Y|X)的判别函数（或预测模型），而生成模型先计算联合概率p(Y,X)然后通过贝叶斯公式转化为条件概率。简单来说，在计算判别模型时，不会计算联合概率，而在计算生成模型时，必须先计算联合概率。或者这样理解：生成算法尝试去找到底这个数据是怎么生成的（产生的），然后再对一个信号进行分类。基于你的生成假设，那么那个类别最有可能产生这个信号，这个信号就属于那个类别。判别模型不关心数据是怎么生成的，它只关心信号之间的差别，然后用差别来简单对给定的一个信号进行分类。常见的判别模型有：KNN、SVM、LR，常见的生成模型有：朴素贝叶斯，隐马尔可夫模型。当然，这也是为什么很少有人问你朴素贝叶斯和LR以及朴素贝叶斯和SVM有什么区别（哈哈，废话是不是太多）。

不同点

第一，本质上是其损失函数（loss function）不同。

注：lr的损失函数是 cross entropy loss， adaboost的损失函数是 expotional loss ,svm是hinge loss，常见的回归模型通常用 均方误差 loss。

不同的loss function代表了不同的假设前提，也就代表了不同的分类原理，也就代表了一切！！！简单来说，​逻辑回归方法基于概率理论，假设样本为1的概率可以用sigmoid函数来表示，然后通过极大似然估计的方法估计出参数的值，具体细节参考逻辑回归。支持向量机​基于几何间隔最大化原理，认为存在最大几何间隔的分类面为最优分类面，具体细节参考支持向量机通俗导论（理解SVM的三层境界）

第二，支持向量机只考虑局部的边界线附近的点，而逻辑回归考虑全局（远离的点对边界线的确定也起作用）。

当​你读完上面两个网址的内容，深入了解了LR和SVM的原理过后，会发现影响SVM决策面的样本点只有少数的结构支持向量，当在支持向量外添加或减少任何样本点对分类决策面没有任何影响；而在LR中，每个样本点都会影响决策面的结果。用下图进行说明：

支持向量机改变非支持向量样本并不会引起决策面的变化

逻辑回归中改变任何样本都会引起决策面的变化

理解了这一点，有可能你会问，然后呢？有什么用呢？有什么意义吗？对使用两种算法有什么帮助么？一句话回答：

因为上面的原因，得知：线性SVM不直接依赖于数据分布，分类平面不受一类点影响；LR则受所有数据点的影响，如果数据不同类别strongly unbalance，一般需要先对数据做balancing。​（引自http://www.zhihu.com/question/26768865/answer/34078149）

第三，在解决非线性问题时，支持向量机采用核函数的机制，而LR通常不采用核函数的方法。

这个问题理解起来非常简单。分类模型的结果就是计算决策面，模型训练的过程就是决策面的计算过程。通过上面的第二点不同点可以了解，在计算决策面时，SVM算法里只有少数几个代表支持向量的样本参与了计算，也就是只有少数几个样本需要参与核计算（即kernal machine解的系数是稀疏的）。然而，LR算法里，每个样本点都必须参与决策面的计算过程，也就是说，假设我们在LR里也运用核函数的原理，那么每个样本点都必须参与核计算，这带来的计算复杂度是相当高的。所以，在具体应用时，LR很少运用核函数机制。​

第四，​线性SVM依赖数据表达的距离测度，所以需要对数据先做normalization，LR不受其影响。（引自http://www.zhihu.com/question/26768865/answer/34078149）

一个机遇概率，一个机遇距离！​

第五，SVM的损失函数就自带正则！！！（损失函数中的1/2||w||^2项），这就是为什么SVM是结构风险最小化算法的原因！！！而LR必须另外在损失函数上添加正则项！！！

以前一直不理解为什么SVM叫做结构风险最小化算法，所谓结构风险最小化，意思就是在训练误差和模型复杂度之间寻求平衡，防止过拟合，从而达到真实误差的最小化。未达到结构风险最小化的目的，最常用的方法就是添加正则项，后面的博客我会具体分析各种正则因子的不同，这里就不扯远了。但是，你发现没，SVM的目标函数里居然自带正则项！！！再看一下上面提到过的SVM目标函数：

SVM目标函数

有木有，那不就是L2正则项吗？

不用多说了，如果不明白看看L1正则与L2正则吧，参考http://www.mamicode.com/info-detail-517504.html

http://www.zhihu.com/question/26768865/answer/34078149

快速理解LR和SVM的区别

两种方法都是常见的分类算法，从目标函数来看，区别在于逻辑回归采用的是logistical loss，svm采用的是hinge loss。这两个损失函数的目的都是增加对分类影响较大的数据点的权重，减少与分类关系较小的数据点的权重。SVM的处理方法是只考虑support vectors，也就是和分类最相关的少数点，去学习分类器。而逻辑回归通过非线性映射，大大减小了离分类平面较远的点的权重，相对提升了与分类最相关的数据点的权重。两者的根本目的都是一样的。此外，根据需要，两个方法都可以增加不同的正则化项，如l1,l2等等。所以在很多实验中，两种算法的结果是很接近的。但是逻辑回归相对来说模型更简单，好理解，实现起来，特别是大规模线性分类时比较方便。而SVM的理解和优化相对来说复杂一些。但是SVM的理论基础更加牢固，有一套结构化风险最小化的理论基础，虽然一般使用的人不太会去关注。还有很重要的一点，SVM转化为对偶问题后，分类只需要计算与少数几个支持向量的距离，这个在进行复杂核函数计算时优势很明显，能够大大简化模型和计算量。

SVM与LR的区别与联系

联系：（1）分类（二分类） （2）可加入正则化项

区别：（1）LR–参数模型；SVM–非参数模型？（2）目标函数：LR—logistical loss；SVM–hinge loss （3）SVM–support vectors；LR–减少较远点的权重 （4）LR–模型简单，好理解，精度低，可能局部最优；SVM–理解、优化复杂，精度高，全局最优，转化为对偶问题—>简化模型和计算 （5）LR可以做的SVM可以做（线性可分），SVM能做的LR不一定能做（线性不可分）

总结一下

  • Linear SVM和LR都是线性分类器
  • Linear SVM不直接依赖数据分布，分类平面不受一类点影响；LR则受所有数据点的影响，如果数据不同类别strongly unbalance，一般需要对数据先做balancing。
  • Linear SVM依赖数据表打对距离测度，所以需要对数据先做normalization；LR不受影响
  • Linear SVM依赖penalty的系数，实验中需要做validation
  • Linear SVM的LR的performance都会收到outlier的影响，就敏感程度而言，无法给出明确结论。

参考资料

SVM 中有哪些核函数？

核函数定义：设$\mathcal{X}$是输入空间，又设$\mathcal{H}$为特征空间，如果存在一个从$\mathcal{X}$到$\mathcal{H}$的映射

使得对所有$x, z \in \mathcal{X}$，函数$K(x, z)$满足条件

则称$K(x, z)$为核函数，$\phi(x)$为映射函数，式中$\phi(x) \cdot \phi(z)$$为\phi(x)$和$\phi(z)$的内积

线性核函数

主要用于线性可分的情况。可以看到特征空间到输入空间的维度是一样的，其参数少速度快，对于线性可分数据，其分类效果很理想，因此我们通常首先尝试用线性核函数来做分类，看看效果如何，如果不行再换别的。

多项式核函数（polynomial kernel function）

对应的支持向量机是一个p次多项式分类器。分类决策函数为

多项式核函数可以实现将低维的输入空间映射到高维的特征空间，但是多项式核函数的参数多，当多项式的阶数比较高的时候，核矩阵的元素值将趋于无穷大或者无穷小，计算复杂度会大到无法计算。

高斯核函数（Gaussian kernel function）

对应的支持向量机是高斯径向基函数（radial basis function）分类器，分类决策函数为

高斯径向基函数是一种局部性强的核函数，其可以将一个样本映射到一个更高维的空间内，该核函数是应用最广的一个，无论大样本还是小样本都有比较好的性能，而且其相对于多项式核函数参数要少，因此大多数情况下在不知道用什么核函数的时候，优先使用高斯核函数。

Sigmod核函数

总结

  • 如果特征的数量大到和样本数量差不多，则选用LR或者线性核的SVM；
    • （特征维度高，往往线性可分，SVM解决非线性分类问题的思路就是将样本映射到更高维的特征空间中）
  • 如果样本数量很多，由于求解最优化问题的时候，目标函数涉及两两样本计算内积，使用高斯核明显计算量会大于线性核，所以手动添加一些特征，使得线性可分，然后可以用LR或者线性核的SVM
  • 如果特征的数量小，样本的数量正常，则选用SVM+高斯核函数；

参考资料

SVM 的对偶问题

  • [ ] TODO

SMO 算法原理

  • [ ] TODO

SVM 为什么可以处理非线性问题？

  • [ ] TODO

SVM 中的优化技术有哪些？

  • [ ] TODO

SVM 的惩罚系数如何确定？

  • [ ] TODO

正则化参数对支持向量数的影响

  • [ ] TODO

如何解决线性不可分问题？

  • [ ] TODO

软间隔和硬间隔

  • [ ] TODO

Hinge Loss

  • [ ] TODO

梯度提升树（GBDT）

基本原理

下面关于GBDT的理解来自论文greedy function approximation: a gradient boosting machine

  1. 损失函数的数值优化可以看成是在函数空间，而不是在参数空间。
  2. 损失函数L(y,F)包含平方损失(y−F)2，绝对值损失|y−F|用于回归问题，负二项对数似然log(1+e−2yF),y∈{-1,1}用于分类。
  3. 关注点是预测函数的加性扩展。

最关键的点在于损失函数的数值优化可以看成是在函数空间而不是参数空间。

GBDT对分类问题基学习器是二叉分类树，对回归问题基学习器是二叉决策树。

参考资料

AdaBoost

基本原理

Adaboost算法基本原理就是将多个弱分类器（弱分类器一般选用单层决策树）进行合理的结合，使其成为一个强分类器。

Adaboost采用迭代的思想，每次迭代只训练一个弱分类器，训练好的弱分类器将参与下一次迭代的使用。也就是说，在第N次迭代中，一共就有N个弱分类器，其中N-1个是以前训练好的，其各种参数都不再改变，本次训练第N个分类器。其中弱分类器的关系是第N个弱分类器更可能分对前N-1个弱分类器没分对的数据，最终分类输出要看这N个分类器的综合效果。

参考资料

GBDT 和 AdaBoost 区别

  • [ ] TODO

XGBoost

基本原理

XGBoost全名叫（eXtreme Gradient Boosting）极端梯度提升，经常被用在一些比赛中，其效果显著。它是大规模并行boosted tree的工具，它是目前最快最好的开源boosted tree工具包。下面我们将XGBoost的学习分为3步：

① 集成思想

② 损失函数分析

③ 求解

我们知道机器学习三要素：模型、策略、算法。对于集成思想的介绍，XGBoost算法本身就是以集成思想为基础的。所以理解清楚集成学习方法对XGBoost是必要的，它能让我们更好的理解其预测函数模型。在第二部分，我们将详细分析损失函数，这就是我们将要介绍策略。第三部分，对于目标损失函数求解，也就是算法了。

参考资料

XGBoost里处理缺失值的方法

  • [ ] TODO

XGBoost 和 GBDT 的区别

  • 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。

  • 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。

  • xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。

  • Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）

  • 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。

  • 对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。

  • xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

  • 可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

XGBoost 如何做到自定义损失函数？

  • [ ] TODO

XGBoost 如何防止过拟合？

  • [ ] TODO

XGBoost 为什么不用后剪枝？

  • [ ] TODO

XGBoost 是如何实现并行的？

  • [ ] TODO

XGBoost 有哪些参数，取指范围，各代表什么意思？

  • [ ] TODO

参考资料

XGBoost 如何进行并行加速的？

  • [ ] TODO

每次分裂叶子节点是怎么决定特征和分裂点的？

  • [ ] TODO

Adaboost、GBDT与XGBoost的区别

  • [ ] TODO

参考资料

LightGBM

基本原理

  • [ ] TODO

LightGBM 与 XGBoost 的区别

  • [ ] TODO

GBDT、LightGBM 和 XGBoost 区别

  • [ ] TODO

基本原理

1、KNN算法概述

　　kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
　　
2、KNN算法介绍

　　最简单最初级的分类器是将全部的训练数据所对应的类别都记录下来，当测试对象的属性和某个训练对象的属性完全匹配时，便可以对其进行分类。但是怎么可能所有测试对象都会找到与之完全匹配的训练对象呢，其次就是存在一个测试对象同时与多个训练对象匹配，导致一个训练对象被分到了多个类的问题，基于这些问题呢，就产生了KNN。

KNN是通过测量不同特征值之间的距离进行分类。它的的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。K通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

下面通过一个简单的例子说明一下：如下图，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。


　
接下来对KNN算法的思想总结一下：就是在训练集中数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前K个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的描述为：

1）计算测试数据与各个训练数据之间的距离；

2）按照距离的递增关系进行排序；

3）选取距离最小的K个点；

4）确定前K个点所在类别的出现频率；

5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。　

参考资料

K-Means

基本原理

算法思想：

1
2
3
4
5
选择K个点作为初始质心  
repeat  
    将每个点指派到最近的质心，形成K个簇  
    重新计算每个簇的质心  
until 簇不发生变化或达到最大迭代次数

这里的重新计算每个簇的质心，如何计算的是根据目标函数得来的，因此在开始时我们要考虑距离度量和目标函数。

考虑欧几里得距离的数据，使用误差平方和（Sum of the Squared Error,SSE）作为聚类的目标函数，两次运行K均值产生的两个不同的簇集，我们更喜欢SSE最小的那个。

参考资料

手撕 K-Means

  • [ ] TODO

K-Means 与 KNN 的区别

  • [ ] TODO

参考资料

K-Means 中的 K 怎么确定？

  • [ ] TODO

K-Means 的迭代循环停止条件

  • [ ] TODO

评判聚类效果准则

  • [ ] TODO

Bagging

基本原理

  • [ ] TODO

参考资料

Boosting

基本原理

  • [ ] TODO

参考资料

Bagging 和 Boosting 的区别

1）样本选择上：

Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的.

Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化.而权值是根据上一轮的分类结果进行调整.

2）样例权重：

Bagging：使用均匀取样，每个样例的权重相等

Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大.

3）预测函数：

Bagging：所有预测函数的权重相等.

Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重.

4）并行计算：

Bagging：各个预测函数可以并行生成

Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果.

参考资料

朴素贝叶斯

基本原理

  • [ ] TODO

参考资料

为什么朴素贝叶斯被称为“朴素”？

  • [ ] TODO

EM 算法

基本原理

  • [ ] TODO

参考资料

E 步和 M 步的具体步骤

  • [ ] TODO

E 中的期望是什么？

  • [ ] TODO

决策树

基本原理

  • [ ] TODO

决策树如何剪枝？

  • [ ] TODO

决策树先剪枝还是后剪枝好？

  • [ ] TODO

决策树能否有非数值型变量？

  • [ ] TODO

决策树如何防止过拟合？

  • [ ] TODO

参考资料

决策树的ID3和C4.5介绍一下

  • [ ] TODO

随机森林（RF）

基本原理

随机森林属于集成学习（Ensemble Learning）中的bagging算法。在集成学习中，主要分为bagging算法和boosting算法。我们先看看这两种方法的特点和区别。

Bagging（套袋法）

bagging的算法过程如下：

从原始样本集中使用Bootstraping方法随机抽取n个训练样本，共进行k轮抽取，得到k个训练集。（k个训练集之间相互独立，元素可以有重复）
对于k个训练集，我们训练k个模型（这k个模型可以根据具体问题而定，比如决策树，knn等）
对于分类问题：由投票表决产生分类结果；对于回归问题：由k个模型预测结果的均值作为最后预测结果。（所有模型的重要性相同）

Boosting（提升法）

boosting的算法过程如下：

对于训练集中的每个样本建立权值wi，表示对每个样本的关注度。当某个样本被误分类的概率很高时，需要加大对该样本的权值。

进行迭代的过程中，每一步迭代都是一个弱分类器。我们需要用某种策略将其组合，作为最终模型。（例如AdaBoost给每个弱分类器一个权值，将其线性组合最为最终分类器。误差越小的弱分类器，权值越大）
Bagging，Boosting的主要区别

样本选择上：Bagging采用的是Bootstrap随机有放回抽样；而Boosting每一轮的训练集是不变的，改变的只是每一个样本的权重。

样本权重：Bagging使用的是均匀取样，每个样本权重相等；Boosting根据错误率调整样本权重，错误率越大的样本权重越大。

预测函数：Bagging所有的预测函数的权重相等；Boosting中误差越小的预测函数其权重越大。

并行计算：Bagging各个预测函数可以并行生成；Boosting各个预测函数必须按顺序迭代生成。

下面是将决策树与这些算法框架进行结合所得到的新的算法：

1）Bagging + 决策树 = 随机森林

2）AdaBoost + 决策树 = 提升树

3）Gradient Boosting + 决策树 = GBDT

决策树

常用的决策树算法有ID3，C4.5，CART三种。3种算法的模型构建思想都十分类似，只是采用了不同的指标。决策树模型的构建过程大致如下：

ID3，C4.5决策树的生成

输入：训练集D，特征集A，阈值eps 输出：决策树T

若D中所有样本属于同一类Ck，则T为单节点树，将类Ck作为该结点的类标记，返回T

若A为空集，即没有特征作为划分依据，则T为单节点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T
否则，计算A中各特征对D的信息增益(ID3)/信息增益比(C4.5)，选择信息增益最大的特征Ag

若Ag的信息增益（比）小于阈值eps，则置T为单节点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T
否则，依照特征Ag将D划分为若干非空子集Di，将Di中实例数最大的类作为标记，构建子节点，由结点及其子节点构成树T，返回T

对第i个子节点，以Di为训练集，以A-{Ag}为特征集，递归地调用1~5，得到子树Ti，返回Ti

CART决策树的生成

这里只简单介绍下CART与ID3和C4.5的区别。

CART树是二叉树，而ID3和C4.5可以是多叉树
CART在生成子树时，是选择一个特征一个取值作为切分点，生成两个子树
选择特征和切分点的依据是基尼指数，选择基尼指数最小的特征及切分点生成子树

随机森林

随机森林是一种重要的基于Bagging的集成学习方法，可以用来做分类、回归等问题。

随机森林有许多优点：

  • 具有极高的准确率
  • 随机性的引入，使得随机森林不容易过拟合
  • 随机性的引入，使得随机森林有很好的抗噪声能力
  • 能处理很高维度的数据，并且不用做特征选择
  • 既能处理离散型数据，也能处理连续型数据，数据集无需规范化
  • 训练速度快，可以得到变量重要性排序
  • 容易实现并行化

随机森林的缺点：

当随机森林中的决策树个数很多时，训练时需要的空间和时间会较大

随机森林模型还有许多不好解释的地方，有点算个黑盒模型

与上面介绍的Bagging过程相似，随机森林的构建过程大致如下：

从原始训练集中使用Bootstraping方法随机有放回采样选出m个样本，共进行n_tree次采样，生成n_tree个训练集
对于n_tree个训练集，我们分别训练n_tree个决策树模型

对于单个决策树模型，假设训练样本特征的个数为n，那么每次分裂时根据信息增益/信息增益比/基尼指数选择最好的特征进行分裂

每棵树都一直这样分裂下去，直到该节点的所有训练样例都属于同一类。在决策树的分裂过程中不需要剪枝
将生成的多棵决策树组成随机森林。对于分类问题，按多棵树分类器投票决定最终分类结果；对于回归问题，由多棵树预测值的均值决定最终预测结果

参考资料

随机森林中的“随机”指什么？

  • [ ] TODO

随机森林处理缺失值的方法

  • [ ] TODO

随机森林和 GBDT 的区别

  • [ ] TODO

随机森林与决策树关系

  • [ ] TODO

CART回归树是怎么实现的？

  • [ ] TODO

CART分类树和ID3以及C4.5有什么区别？

  • [ ] TODO

机器学习中的分类、回归和聚类模型有哪些？

分类：LR、SVM、KNN、决策树、RandomForest、GBDT

回归：non-Linear regression、SVR（支持向量回归—>可用线性或高斯核（RBF））、随机森林

聚类：Kmeans、层次聚类、GMM（高斯混合模型）、谱聚类

高斯混合模型（GMM）

  • [ ] TODO

参考资料

马尔科夫随机场（MRF）

基本原理

  • [ ] TODO

参考资料

隐马尔科夫模型（HMM）

基本原理

  • [ ] TODO

参考资料

发射概率和状态转移概率

  • [ ] TODO

每层要记住所有路径吗？

  • [ ] TODO

条件随机场（CRF）

基本原理

  • [ ] TODO

CRF 的损失函数是什么？

  • [ ] TODO

参考资料

HMM、MEMM vs CRF 对比？

1）HMM是有向图模型，是生成模型；HMM有两个假设：一阶马尔科夫假设和观测独立性假设；但对于序列标注问题不仅和单个词相关，而且和观察序列的长度，单词的上下文，等等相关。

2）MEMM（最大熵马尔科夫模型）是有向图模型，是判别模型；MEMM打破了HMM的观测独立性假设，MEMM考虑到相邻状态之间依赖关系，且考虑整个观察序列，因此MEMM的表达能力更强；但MEMM会带来标注偏置问题：由于局部归一化问题，MEMM倾向于选择拥有更少转移的状态。这就是标记偏置问题。

img最大熵模型（MEMM）

img

3）CRF模型解决了标注偏置问题，去除了HMM中两个不合理的假设，当然，模型相应得也变复杂了。

HMM、MEMM和CRF的优缺点比较：

a）与HMM比较。CRF没有HMM那样严格的独立性假设条件，因而可以容纳任意的上下文信息。特征设计灵活（与ME一样）

b）与MEMM比较。由于CRF计算全局最优输出节点的条件概率，它还克服了最大熵马尔可夫模型标记偏置（Label-bias）的缺点。

c）与ME比较。CRF是在给定需要标记的观察序列的条件下，计算整个标记序列的联合概率分布，而不是在给定当前状态条件下，定义下一个状态的状态分布.

首先，CRF，HMM(隐马模型)，MEMM(最大熵隐马模型)都常用来做序列标注的建模，像分词、词性标注，以及命名实体标注
隐马模型一个最大的缺点就是由于其输出独立性假设，导致其不能考虑上下文的特征，限制了特征的选择
最大熵隐马模型则解决了隐马的问题，可以任意选择特征，但由于其在每一节点都要进行归一化，所以只能找到局部的最优值，同时也带来了标记偏见的问题，即凡是训练语料中未出现的情况全都忽略掉。
条件随机场则很好的解决了这一问题，他并不在每一个节点进行归一化，而是所有特征进行全局归一化，因此可以求得全局的最优值。

参考资料

主成分分析（PCA）

基本原理

PCA（Principal Component Analysis）是一种常用的数据分析方法。PCA通过线性变换将原始数据变换为一组各维度线性无关的表示，可用于提取数据的主要特征分量，常用于高维数据的降维。网上关于PCA的文章有很多，但是大多数只描述了PCA的分析过程，而没有讲述其中的原理。这篇文章的目的是介绍PCA的基本数学原理，帮助读者了解PCA的工作机制是什么。

当然我并不打算把文章写成纯数学文章，而是希望用直观和易懂的方式叙述PCA的数学原理，所以整个文章不会引入严格的数学推导。希望读者在看完这篇文章后能更好的明白PCA的工作原理。

参考资料

线性判别分析（LDA）

TODO

参考资料

奇异值分解（SVD）

基本原理

  • [ ] TODO

参考资料

手撕 SVD

  • [ ] TODO

特征值和SVD的区别

  • [ ] TODO

参考资料

凸优化

基本原理

  • [ ] TODO

参考资料

神经网络

  • [ ] TODO

注：建议放在深度学习中介绍，这里可以简单介绍

Accuracy、Precision、Recall和 F1 Score

在学习机器学习、深度学习，甚至做自己项目的时候，经过看到上述名词。然而因为名词容易搞混，所以经常会忘记相关的含义。

这里做一次最全最清晰的介绍，若之后再次忘记相关知识点，本文可以帮助快速回顾。

首先，列出一个清单：

  • TP（true positive，真正）: 预测为正，实际为正

  • FP（false positive，假正）: 预测为正，实际为负

  • TN（true negative，真负）：预测为负，实际为负

  • FN（false negative，假负）: 预测为负，实际为正

  • ACC（accuracy，准确率）：ACC = (TP+TN)/(TP+TN+FN+FP)

  • P（precision精确率、精准率、查准率P = TP/ (TP+FP)

  • R（recall，召回率、查全率）： R = TP/ (TP+FN)

  • TPR（true positive rate，，真正类率同召回率、查全率）：TPR = TP/ (TP+FN)

    注：Recall = TPR

  • FPR（false positive rate，假正类率）：FPR =FP/ (FP+TN)

  • F-Score: F-Score = (1+β^2) x (PxR) / (β^2x(P+R)) = 2xTP/(2xTP + FP + FN)

  • 当β=1是，F1-score = 2xPxR/(P+R)

  • P-R曲线（precision-recall，查准率-查全率曲线）

  • ROC曲线（receiver operating characteristic，接收者操作特征曲线）

  • AUC（area under curve）值

中文博大精深，为了不搞混，下面统一用英文全称或简称作为名词标识。

正式介绍一下前四个名词：

True positives（TP，真正） : 预测为正，实际为正

True negatives（TN，真负）：预测为负，实际为负

False positives（FP，假正）: 预测为正，实际为负

False negatives（FN，假负）: 预测为负，实际为正

为了更好的理解，这里二元分类问题的例子：

假设，我们要对某一封邮件做出一个判定，判定这封邮件是垃圾邮件、还是这封邮件不是垃圾邮件？

如果判定是垃圾邮件，那就是做出（Positive）的判定；

如果判定不是垃圾邮件，那就做出（Negative）的判定。

True Positive（TP）意思表示做出Positive的判定，而且判定是正确的。

因此，TP的数值表示正确的Positive判定的个数。

同理，False Positive（TP）数值表示错误的Positive判定的个数。

依此，True Negative（TN）数值表示正确的Negative判定个数。

False Negative（FN）数值表示错误的Negative判定个数。

TPR、FPR和TNR

TPR（true positive rate，真正类率）

TPR = TP/(TP+FN)

真正类率TPR代表分类器预测的正类中实际正实例占所有正实例的比例。

FPR（false positive rate，假正类率）

FPR = FP/(FP+TN)

假正类率FPR代表分类器预测的正类中实际负实例占所有负实例的比例。

TNR（ture negative rate，真负类率）

TNR = TN/(FP+TN)

真负类率TNR代表分类器预测的负类中实际负实例占所有负实例的比例。

Accuracy

准确率（accuracy，ACC）

ACC = (TP+TN)/(TP+TN+FN+FP)

Precision & Recall

Precision精确率：

P = TP/(TP+FP)

表示当前划分到正样本类别中，被正确分类的比例（正确正样本所占比例）。

Recall召回率：

R = TP/(TP+FN)

表示当前划分到正样本类别中，真实正样本占所有正样本的比例。

F-Score

F-Score 是精确率Precision和召回率Recall的加权调和平均值。该值是为了综合衡量Precision和Recall而设定的。

F-Score = (1+β^2) x (PxR) / (β^2x(P+R)) = 2xTP/(2xTP + FP + FN)

当β=1时，F1-score = 2xPxR/(P+R)。这时，Precision和Recall都很重要，权重相同。

当有些情况下，我们认为Precision更重要，那就调整β的值小于1；如果我们认为Recall更加重要，那就调整β的值大于1。

一般来说，当F-Score或F1-score较高

P-R曲线

ROC曲线

横轴：负正类率(false postive rate FPR)

纵轴：真正类率(true postive rate TPR)

ROC Curve

AUC值

上面都是理论，看起来很迷糊，这里举个真实应用的实例，加强理解。

对于那些不熟悉的人，我将解释精确度和召回率，对于那些熟悉的人，我将在比较精确召回曲线时解释文献中的一些混淆。

下面从图像分类的角度举个例子：

假设现在有这样一个测试集，测试集中的图片只由大雁和飞机两种图片组成，如下图所示：

假设你的分类系统最终的目的是：能取出测试集中所有飞机的图片，而不是大雁的图片。

现在做如下的定义：

True positives（TP，真正） : 飞机的图片被正确的识别成了飞机。

True negatives（TN，真负）: 大雁的图片没有被识别出来，系统正确地认为它们是大雁。

False positives（FP，假正）: 大雁的图片被错误地识别成了飞机。

False negatives（FN，假负）: 飞机的图片没有被识别出来，系统错误地认为它们是大雁。

Precision and recall

实战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
'''In binary classification settings'''

######### Create simple data ##########

from sklearn import svm, datasets
from sklearn.model_selection import train_test_split
import numpy as np

iris = datasets.load_iris()
X = iris.data
y = iris.target

# Add noisy features
random_state = np.random.RandomState(0)
n_samples, n_features = X.shape
X = np.c_[X, random_state.randn(n_samples, 200 * n_features)]

# Limit to the two first classes, and split into training and test
X_train, X_test, y_train, y_test = train_test_split(X[y < 2], y[y < 2],
                                                    test_size=.5,
                                                    random_state=random_state)

# Create a simple classifier
classifier = svm.LinearSVC(random_state=random_state)
classifier.fit(X_train, y_train)
y_score = classifier.decision_function(X_test)


######## Compute the average precision score ######## 

from sklearn.metrics import average_precision_score
average_precision = average_precision_score(y_test, y_score)

print('Average precision-recall score: {0:0.2f}'.format(
      average_precision))
	  

######## Plot the Precision-Recall curve   ######
	  
from sklearn.metrics import precision_recall_curve
import matplotlib.pyplot as plt

precision, recall, _ = precision_recall_curve(y_test, y_score)

plt.step(recall, precision, color='b', alpha=0.2,
         where='post')
plt.fill_between(recall, precision, step='post', alpha=0.2,
                 color='b')

plt.xlabel('Recall')
plt.ylabel('Precision')
plt.ylim([0.0, 1.05])
plt.xlim([0.0, 1.0])
plt.title('2-class Precision-Recall curve: AP={0:0.2f}'.format(
          average_precision))
plt.show()

参考资料

正则化方法

  • L1 范数
  • L2 范数

  • 数据集增广

  • Dropout

  • Batch Normaliztion

参考资料

L1和L2正则化

目的：降低损失函数

机器学习中几乎都可以看到损失函数后面会添加一个额外项，常用的额外项一般有两种，一般英文称作ℓ1-norm和ℓ2-norm，中文称作L1正则化和L2正则化，或者L1范数和L2范数。

L1正则化和L2正则化可以看做是损失函数的惩罚项。所谓『惩罚』是指对损失函数中的某些参数做一些限制。对于线性回归模型，使用L1正则化的模型建叫做Lasso回归，使用L2正则化的模型叫做Ridge回归（岭回归）。下图是Python中Lasso回归的损失函数，式中加号后面一项α||w||1即为L1正则化项。

Logistic Regression.png

下图是Python中Ridge回归的损失函数，式中加号后面一项即为L2正则化项。

Logistic Regression.png

一般回归分析中回归w表示特征的系数，从上式可以看到正则化项是对系数做了处理（限制）。L1正则化和L2正则化的说明如下：

  • L1正则化是指权值向量w中各个元素的绝对值之和，通常表示为||w||1
  • L2正则化是指权值向量w中各个元素的平方和然后再求平方根（可以看到Ridge回归的L2正则化项有平方符号），通常表示为||w||2
    一般都会在正则化项之前添加一个系数，Python中用α表示，一些文章也用λ表示。这个系数需要用户指定。

那添加L1和L2正则化有什么用？下面是L1正则化和L2正则化的作用，这些表述可以在很多文章中找到。

  • L1正则化可以产生稀疏权值矩阵，即产生一个稀疏模型，可以用于特征选择
  • L2正则化可以防止模型过拟合（overfitting）；一定程度上，L1也可以防止过拟合

稀疏模型与特征选择

上面提到L1正则化有助于生成一个稀疏权值矩阵，进而可以用于特征选择。为什么要生成一个稀疏矩阵？

稀疏矩阵指的是很多元素为0，只有少数元素是非零值的矩阵，即得到的线性回归模型的大部分系数都是0. 通常机器学习中特征数量很多，例如文本处理时，如果将一个词组（term）作为一个特征，那么特征数量会达到上万个（bigram）。在预测或分类时，那么多特征显然难以选择，但是如果代入这些特征得到的模型是一个稀疏模型，表示只有少数特征对这个模型有贡献，绝大部分特征是没有贡献的，或者贡献微小（因为它们前面的系数是0或者是很小的值，即使去掉对模型也没有什么影响），此时我们就可以只关注系数是非零值的特征。这就是稀疏模型与特征选择的关系。

L1和L2正则化的直观理解

这部分内容将解释为什么L1正则化可以产生稀疏模型（L1是怎么让系数等于零的），以及为什么L2正则化可以防止过拟合。

L1正则化和特征选择
假设有如下带L1正则化的损失函数：

Logistic Regression.png

其中J0是原始的损失函数，加号后面的一项是L1正则化项，α是正则化系数。注意到L1正则化是权值的绝对值之和，J是带有绝对值符号的函数，因此J是不完全可微的。机器学习的任务就是要通过一些方法（比如梯度下降）求出损失函数的最小值。当我们在原始损失函数J0后添加L1正则化项时，相当于对J0做了一个约束。令L=α∑w|w|，则J=J0+L，此时我们的任务变成在L约束下求出J0取最小值的解。考虑二维的情况，即只有两个权值w1和w2，此时L=|w1|+|w2|对于梯度下降法，求解J0的过程可以画出等值线，同时L1正则化的函数L也可以在w1w2的二维平面上画出来。如下图：

Logistic Regression.png
图1 L1正则化

图中等值线是J0的等值线，黑色方形是L函数的图形。在图中，当J0等值线与L图形首次相交的地方就是最优解。上图中J0与L在L的一个顶点处相交，这个顶点就是最优解。注意到这个顶点的值是(w1,w2)=(0,w)。可以直观想象，因为L函数有很多『突出的角』（二维情况下四个，多维情况下更多），J0与这些角接触的机率会远大于与L其它部位接触的机率，而在这些角上，会有很多权值等于0，这就是为什么L1正则化可以产生稀疏模型，进而可以用于特征选择。

而正则化前面的系数α，可以控制L图形的大小。α越小，L的图形越大（上图中的黑色方框）；α越大，L的图形就越小，可以小到黑色方框只超出原点范围一点点，这是最优点的值(w1,w2)=(0,w)中的w可以取到很小的值。

类似，假设有如下带L2正则化的损失函数：

Logistic Regression.png

同样可以画出它们在二维平面上的图形，如下：

Logistic Regression.png
图2 L2正则化

二维平面下L2正则化的函数图形是个圆，与方形相比，被磨去了棱角。因此J0与L相交时使得w1或w2等于零的机率小了许多，这就是为什么L2正则化不具有稀疏性的原因。

注：以二维平面举例，借助可视化L1和L2，可知L1正则化具有稀疏性。

L2正则化和过拟合

拟合过程中通常都倾向于让权值尽可能小，最后构造一个所有参数都比较小的模型。因为一般认为参数值小的模型比较简单，能适应不同的数据集，也在一定程度上避免了过拟合现象。可以设想一下对于一个线性回归方程，若参数很大，那么只要数据偏移一点点，就会对结果造成很大的影响；但如果参数足够小，数据偏移得多一点也不会对结果造成什么影响，专业一点的说法是『抗扰动能力强』。

那为什么L2正则化可以获得值很小的参数？

以线性回归中的梯度下降法为例。假设要求的参数为θ，hθ(x)是我们的假设函数，那么线性回归的代价函数如下：

Logistic Regression.png

那么在梯度下降法中，最终用于迭代计算参数θ的迭代式为：

Logistic Regression.png

其中α是learning rate. 上式是没有添加L2正则化项的迭代公式，如果在原始代价函数之后添加L2正则化，则迭代公式会变成下面的样子：

Logistic Regression.png

其中λ就是正则化参数。从上式可以看到，与未添加L2正则化的迭代公式相比，每一次迭代，θj都要先乘以一个小于1的因子，从而使得θj不断减小，因此总得来看，θ是不断减小的。
最开始也提到L1正则化一定程度上也可以防止过拟合。之前做了解释，当L1的正则化系数很小时，得到的最优解会很小，可以达到和L2正则化类似的效果。

L2正则化参数

从上述公式可以看到，λ越大，θj衰减得越快。另一个理解可以参考图2，λ越大，L2圆的半径越小，最后求得代价函数最值时各参数也会变得很小。

L1 和 L2 正则化的区别

  • [ ] TODO

机器学习中常常提到的正则化到底是什么意思？

  • [ ] TODO

参考资料

为什么 L2 正则化可以防止过拟合？

  • [ ] TODO

过拟合和欠拟合

基本原理

过拟合（Over-Fitting）

高方差

在训练集上误差小，但在测试集上误差大，我们将这种情况称为高方差（high variance），也叫过拟合。

欠拟合（Under-Fitting）

在训练集上训练效果不好（测试集上也不好），准确率不高，我们将这种情况称为高偏差（high bias），也叫欠拟合。

如何防止过拟合？

  • 数据增广（Data Augmentation）
  • 正则化（L0正则、L1正则和L2正则），也叫限制权值Weight-decay
  • Dropout
  • Early Stopping
  • 简化模型
  • 增加噪声
  • Bagging
  • 贝叶斯方法
  • 决策树剪枝
  • 集成方法，随机森林
  • Batch Normalization

如何防止欠拟合？

  • 添加新特征
  • 添加多项式特征
  • 减少正则化参数
  • 增加网络复杂度
  • 使用集成学习方法，如Bagging

精确率（Precision）和召回率（Recall）

对于二分类问题常用的评价指标是精确率和召回率。通常以关注的类为正类，其他类为负类，分类器在数据集上的预测或者正确或者不正确，我们有4中情况，在混淆矩阵中表示如下：

img

  • [ ] 精确率$Precision = \frac{TP}{TP+FP} $, 那么有误拦率为$ \frac{FP}{TP+FP} $
  • [ ] 召回率$ Recall = TP / (TP + FN)$

精确率表示我现在有了这么的预测为正的样本，那么这些样本中有多少是真的为正呢？

召回率表示我现在预测为正的这些值中，占了所有的正的为正的样本的多大比例呢？

参考资料

AUC 和 ROC

基本原理

  • [ ] TODO

如何绘制ROC曲线？

  • [ ] TODO

ROC曲线下面积表示什么？

  • [ ] TODO

手撕 AUC 曲面面积代码

  • [ ] TODO

梯度弥散和梯度爆炸

  • [ ] TODO

什么是参数范数惩罚？

  • [ ] TODO

为什么要进行归一化？优点？

  • [ ] TODO

CCA和PCA的区别

  • [ ] TODO

Softmax

基本原理

  • [ ] TODO

Softmax是和什么loss function配合使用？

  • [ ] TODO

Softmax代码实现

  • [ ] TODO

交叉熵损失函数

  • [ ] TODO

通俗解释一下信息熵

  • [ ] TODO

如何加快梯度下降收敛速度？

  • [ ] TODO

如何解决正负样本数量不均衡？

  • [ ] TODO

如何解决异常值问题？

  • [ ] TODO

机器学习中使用正则化来防止过拟合是什么原理？

  • [ ] TODO

参考资料

机器学习中常常提到的正则化到底是什么意思？

  • [ ] TODO

参考资料

梯度下降陷入局部最优有什么解决办法

  • [ ] TODO

聚类算法中的距离度量有哪些？

  • [ ] TODO

常见的距离度量：欧氏距离、曼哈顿距离、夹角余弦、切比雪夫距离、汉明距离

KL 散度和交叉熵的区别

  • [ ] TODO

降维的方法都有哪些？

  • [ ] TODO

TODO