可参考资料：https://easyai.tech/ai-definition/discriminative-model/

数据

回归算法

判断模型和生成模型

• 判别模型(discriminative model)通过求解条件概率分布P(y|x)或者直接计算y的值来预测y。线性回归（Linear Regression）,逻辑回归（Logistic Regression）,支持向量机（SVM）, 传统神经网络（Traditional Neural Networks）,线性判别分析（Linear Discriminative Analysis），条件随机场（Conditional Random Field）

  通常来说常见的分类、回归模型都是判别模型，直接对数据进行建模，不需要获得真实样本的分布情况

• 生成模型（generative model）通过对观测值和标注数据计算联合概率分布P(x,y)来达到判定估算y的目的。朴素贝叶斯（Naive Bayes）, 隐马尔科夫模型（HMM）,贝叶斯网络（Bayesian Networks）和隐含狄利克雷分布（Latent Dirichlet Allocation）、混合高斯模型

  在概率统计理论中， 生成模型是指能够随机生成观测数据的模型，尤其是在给定某些隐含参数的条件下。它给观测值和标注数据序列指定一个联合概率分布。在机器学习中，生成模型可以用来直接对数据建模（例如根据某个变量的概率密度函数进行数据采样），也可以用来建立变量间的条件概率分布。条件概率分布可以由生成模型根据贝叶斯定理形成。

最小二乘法

题目：给定 n+1 维空间中的 m 个点对 ，若已知 y 和 x 大致成线性关系，试估计线性方程表达式。

设：，其中 W 为 n +1 维横向量，x 为 n + 1 维列向量。由此带入样本点：

写为矩阵形式：，其中 ， ，

目标：使得拟合的残差最小化
目标函数：

最小化目标函数即可，对 分别求偏导得到：

矩阵求导公式： 上面求导：通常向量都是写成列向量，但是上面求导时 等是横向量（通常先转置一下！）

当偏导为 0 时，取得最小值：

直接采用公式求解

迭代求解最小二乘法

import numpy as np
import matplotlib.pyplot as plt
from utils.utils import generate_linear_noisy_points
"""
input:
    X: (sample_num, sample_dim)
    Y: (sample_num, 1)
"""
def iter_solve(X, Y, iter=100, lr=0.005):
    # W: (sample_dim, 1)
    N, D = X.shape
    W = np.zeros((D, 1))
    Y1 = np.matmul(X, W)
    plt.scatter(X[:, 1:], Y)
    plt.plot(X[:, 1:], Y1)
    for idx in range(iter):
        plt.clf()
        mat2 = np.matmul(X, W) - Y
        mat1 = np.transpose(mat2)
        loss = np.matmul(mat1, mat2)
        print("Now Loss", loss)
        # 求偏导：\partial loss / \partial W = 2 * X^T(XW-Y)
        partial = np.matmul(np.transpose(X), mat2)
        W = W - partial * lr
        Y1 = np.matmul(X, W)
        plt.scatter(X[:, 1:], Y)
        plt.plot(X[:, 1:], Y1, 'r')
        plt.pause(0.4)
    return W
if __name__ == "__main__":
    W, X, Y = generate_linear_noisy_points(100, 2)
    W = iter_solve(X, Y)
    plt.show()

最小二乘法是线性回归算法，如果引入变换如：，其中 可微，则得到广义线性模型。

Logistic 回归

https://zhuanlan.zhihu.com/p/95132284

线性回归往往用于连续值的预测，对于标签 非连续的情况，则无法采用线性模型。为了解决这个问题，可以通过阶跃函数将连续空间的 映射到离散空间：

阶跃函数非连续，可以利用平滑的 Logistic 函数替代阶跃函数：，然后根据 与 0.5 进行比较来得到二分类结果。除此之外，由于模型输出在 我们能将 看做是样本预测为正例的概率。模型输出可以表示概率 。

线性模型外面套了个 sigmoid 函数

如何确定模型参数呢？

由于 ，所以完全可以采用最小二乘法进行参数的估计？但是值得注意的一个问题是给定的训练标签是离散的，所以直接按照最小二乘法显然不可行。

事实上可以采用极大似然估计即（概率累乘取对数，变累加）：，其含义即：使得模型对每个样本输出真实标签的概率最大化。由于模型输出表示的是为正例的概率，而标签，所以

上面变换挺巧妙的

然后采用迭代的方式，求解即可！
除了采用极大似然估计之外，也可以利用交叉熵损失函数，交叉熵本身就是用来训练分类模型的。它最大化模型输出分布和真实标签分布尽可能接近。

如何变为多分类：

1. 采用 softmax （，可以实现多分类；
2. 多个二分类组合成为多分类；

分类算法

单一的分类方法主要包括：LR逻辑回归，SVM支持向量机，DT决策树、NB朴素贝叶斯、NN人工神经网络、K-近邻；
集成学习算法：基于 Bagging 和 Boosting 算法思想，RF随机森林, GBDT, Adaboost, XGboost。

KNN

思想非常简单：假设有训练集 X，对于新样本，则计算样本与训练集所有样本的相似性，选取 K 个最相似的样本的综合结果作为最终的结果。

SVM

svm 在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。

小样本：是相对概念，svm 需要的样本较少； 高维模式识别：从计算量而言的，svm 只需要‘支持向量’，并非所有样本，降低了计算量

此处以二分类为例，就是希望在空间中找到一个超平面能够最大限度地将两种样本分隔开来。

满足条件的超平面很多，但是我们需要得到一个更加稳定的分界面，能够对噪声点不那么敏感。
为了简化计算过程，我们可以对 和 进行缩放之后有 则：

满足上述等式的即是距离超平面最近的一系列点，如果我们能使得这些点距离超平面的距离尽量大，那么我们最终得到的模型就更加稳定。满足上述等式的向量叫做支持向量。支持向量到超平面距离为：

点到直线距离公式：

那么，我们最终的目标是：

稍微转换一下：

如果直接采用 hinge loss 不断最小化即可

上面的称为硬间隔，他要求所以样本都要满足约束；但是这在某些情况下是不能实现的，可以适当降低约束，使得某些样本不满足约束，这就引入松弛变量，但是我们还是希望不满足约束的样本越少越好 -> 软间隔

这是一个凸优化问题，可以通过拉格朗日乘子法进行求解。

拉格朗日不等式约束和等式约束可以直接统一起来

两边对 和 进行求导（ 是向量， 是标量，向量标量符号未进行区分）：

原线性函数为：
根据 KKT 条件：

知道，非支持向量对原线性函数无影响。

核函数

核函数的本质可以概括为如下三点：

• 实际应用中，常常遇到线性不可分的情况。针对这种情况，常用做法是把样例特征映射到高维空间中，转化为线性可分问题。
• 将样例特征映射到高维空间，可能会遇到维度过高的问题。
• 针对可能的维灾难，可以利用核函数。核函数也是将特征从低维到高维的转换，但避免了直接进行高维空间中的复杂计算，可以在低维上进行计算，却能在实质上将分类效果表现在高维上。

  高维映射与核方法

为了解决线性不可分问题，引入核函数。首先将输入特征 进行一定的变换：，那么此时原超平面表示为
其中 就是核函数

对于线性不可分的数据，我们一定能够通过将其变到高维之后线性可分。所有 事实上需要是一个合理的升维函数。升维的弊端是增加了计算量！所以才采用核函数。

线性核函数

参数少

多项式核函数

参数很多

高斯核

参数相对多项式要少，解决线性不可分问题（根据泰勒展开，可以表示为无穷维多项式）

这些核函数都隐含了一个将样本升维的过程

核的选择

• 特征维数高选择线性核
• 样本数量可观、特征少选择高斯核（非线性核）
• 样本数量非常多选择线性核（避免造成庞大的计算量）

下面是吴恩达的见解：
1. 如果Feature的数量很大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM
2. 如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel
3. 如果Feature的数量比较小，而样本数量很多，需要手工添加一些feature变成第一种情况

SVM 和 LR 对比

相同处

1、LR和SVM都可以处理分类问题，且一般都用于处理线性二分类问题（在改进的情况下可以处理多分类问题）
2、两个方法都可以增加不同的正则化项，如 l1、l2 等等。所以在很多实验中，两种算法的结果是很接近的
3、LR和SVM都可以用来做非线性分类，只要加核函数就好
4、都属于判别模型

区别

1、LR是参数模型，SVM是非参数模型

参数模型需要对数据分布做假设；非参数模型不要求数据分布，直接分析样本

2、从目标函数来看，区别在于逻辑回归采用的是logistical loss，SVM采用的是hinge loss，这两个损失函数的目的都是增加对分类影响较大的数据点的权重，减少与分类关系较小的数据点的权重

logistical loss: hinge loss: 适用于 max margin 任务，当预测 大于等于 1 或者小于等于 -1 则认为分类明确，当分类正确时则 loss 为 0；当 在 -1 到 1 之间时则认为分类不确定，loss 一定不为 0

3、逻辑回归相对来说模型更简单，好理解，特别是大规模线性分类时比较方便。而SVM的理解和优化相对来说复杂一些，SVM转化为对偶问题后,分类只需要计算与少数几个支持向量的距离,这个在进行复杂核函数计算时优势很明显,能够大大简化模型和计算。
4、SVM不直接依赖数据分布，而LR则依赖，因为SVM只与支持向量那几个点有关系，而LR和所有点都有关系。
5、SVM依赖penalty系数，实验中需要做CV
6、SVM本身是结构风险最小化模型，而LR是经验风险最小化模型

概率图模型

概率图模型是用图来表示变量概率依赖关系的理论，结合概率论与图论的知识，利用图来表示与模型有关的变量的联合概率分布。由图灵奖获得者Pearl开发出来。概率图中的节点分为隐含节点和观测节点，边分为有向边和无向边。从概率论的角度，节点对应于随机变量，边对应于随机变量的依赖或相关关系，其中有向边表示单向的依赖，无向边表示相互依赖关系。
概率图模型分为贝叶斯网络（Bayesian Network）和马尔可夫网络（Markov Network）两大类。贝叶斯网络可以用一个有向图结构表示，马尔可夫网络可以表示成一个无向图的网络结构。更详细地说，概率图模型包括了朴素贝叶斯模型、最大熵模型、隐马尔可夫模型、条件随机场、主题模型等，在机器学习的诸多场景中都有着广泛的应用。

Bayes

https://www.cnblogs.com/mantch/p/11179933.html

结构形式

• head to head

  在 c 未知的条件下，a, b 被 block，是独立的

• tail to tail

  a 未知时，不能推出 b, c 独立；在 a 已知的条件下 b, c 在 a 的条件下独立

• head to tail

  在 b 未知条件下，不能得到 a, c 独立；在 b 已知时，a, c 在 b 的条件下独立（增加级数就是马尔科夫链）

因子图

将一个具有多变量的全局函数因子分解，得到几个局部函数的乘积，以此为基础得到的一个双向图叫做因子图（Factor Graph）。图中一般内含两种节点：变量节点和函数节点。

朴素贝叶斯

前提条件

• 特征关于类别条件独立（简化模型）
• 特征均等重要性

根据 bayes 公式给定特征 的条件下，类别为 的概率为：

先验概率 似然概率，根据历史信息推断的概率 调整因子，标准似然度

, 以及 可以通过在样本中统计得到，所以上述概率值也就求出来了。

朴素 bayes 的缺点：
朴素贝叶斯模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，在属性个数比较多或者属性之间相关性较大时，分类效果不好。

解释朴素贝叶斯算法里面的先验概率、似然估计和边际似然估计？

• 先验概率：就是因变量（二分法）在数据集中的比例。这是在你没有任何进一步的信息的时候，是对分类能做出的最接近的猜测。
• 似然估计：似然估计是在其他一些变量的给定的情况下，一个观测值被分类为1的概率。例如，“FREE”这个词在以前的垃圾邮件使用的概率就是似然估计。
• 边际似然估计：边际似然估计就是，“FREE”这个词在任何消息中使用的概率。

  决策树

  https://easyai.tech/ai-definition/decision-tree/

决策树采用树形结构，其中节点分为以下三种：

• 根节点：起始点
• 内部节点：对应特征属性测试
• 叶子节点：决策结果

决策树学习三个步骤：

1. 特征选择：选择和分类结果最相关的特征
2. 决策树生成：选择好特征后，就从根节点出发，对节点计算所有特征的信息增益，选择信息增益最大的特征作为节点特征，根据该特征的不同取值建立子节点；对每个子节点使用相同的方式生成新的子节点，直到信息增益很小或者没有特征可以选择为止
3. 树的剪枝：剪枝的主要目的是对抗「过拟合」，通过主动去掉部分分支来降低过拟合的风险

   ID3 算法

   建树举例

最早提出的决策树算法，它利用信息增益来选择特征的

特征增益

以信息熵（信息量的期望）表示信息量的多少，
以某特征划分数据集前后的熵的差值公式定义为信息增益：，其中
优点：

1. 决策树易于理解和解释，可以可视化分析。
2. 决策树分类器的构造不需要任何领域知识或参数设置，
3. 适合高维数据
4. 可以同时处理标称型和数值型数据
5. 计算复杂度不高

缺点：

1. 容易出现过拟合
2. 对缺失数据处理比较困难
3. 忽略数据集中属性的相关性
4. ID3算法计算信息增益时偏向数值较多的特征
5. 不支持增量学习

   C4.5 算法

   引入“信息增益比”指标作为特征的选择依据

   CART 算法

   CART 算法使用了基尼系数取代了信息熵模型

   集成树方法

   RandonForest

   基于 Bagging 的方法，采用四步构造随机森林：

• 随机抽样训练决策树
• 随机选取属性做节点分类属性
• 重复上一步直到节点无法继续分裂
• 建立大量决策树进行后续任务

优点：

• 可以出来很高维度（特征很多）的数据，并且不用降维，无需做特征选择
• 它可以判断特征的重要程度
• 可以判断出不同特征之间的相互影响
• 不容易过拟合
• 训练速度比较快，容易做成并行方法
• 实现起来比较简单
• 对于不平衡的数据集来说，它可以平衡误差
• 如果有很大一部分的特征遗失，仍可以维持准确度

Adaboost

AdaBoost 用于短决策树。在创建第一个树之后，每个训练实例上的树的性能用于加权创建的下一个树应该关注每个训练实例的注意力。难以预测的训练数据被赋予更多权重，而易于预测的实例被赋予更少的权重。模型一个接一个地顺序创建，每个模型更新训练实例上的权重，这些权重影响序列中下一个树所执行的学习。构建完所有树之后，将对新数据进行预测，并根据训练数据的准确性对每棵树的性能进行加权。

优点：

• 很好的利用了弱分类器进行级联；
• 可以将不同的分类算法作为弱分类器；
• AdaBoost 具有很高的精度；
• 相对于 bagging 算法和 Random Forest 算法，AdaBoost 充分考虑的每个分类器的权重；

缺点：

• AdaBoost 迭代次数也就是弱分类器数目不太好设定，可以使用交叉验证来进行确定；
• 数据不平衡导致分类精度下降；
• 训练比较耗时，每次重新选择当前分类器最好切分点；

GBDT

梯度提升决策树（Gradient Boosting Decision Tree）

集成模型分类

XGboost

极值梯度提升（eXtreme Gradient Boosting）

聚类算法

k-means

k-means 算法是找到 k 个质心，使得
其中 表示样本， 表示簇， 表示 所属的簇， 表示对应簇的质心

步骤：

1. 数据预处理
2. 随机选择 k 个质心：
3. 计算损失
4. 迭代优化
   1. 对每个样本 , 将其分配到其最近的质心所对应的簇
   2. 分配完之后，重新计算质心坐标
   3. 重复 a, b
5. 当所有质心趋于稳定或者定义的损失函数函数值足够小时，停止迭代

优点：

• 容易理解，聚类效果不错，虽然是局部最优， 但往往局部最优就够了
• 处理大数据集的时候，该算法可以保证较好的伸缩性
• 当簇近似高斯分布的时候，效果非常不错
• 算法复杂度低

缺点：

• K 值需要人为设定，不同 K 值得到的结果不一样
• 对初始的簇中心敏感，不同选取方式会得到不同结果

• 对异常值敏感

  离群点检测，去除离群点

• 样本只能归为一类，不适合多分类任务

• 只能处理球形（欧式距离）簇，不是球形距离效果差
• 不适合太离散的分类、样本类别不平衡的分类、非凸形状的分类

  DBSCAN

  详解 DBSCAN

基于密度的噪声应用空间聚类(Density-Based Spatial Clustering of Applications with Noise)
该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。

三种点：

• 核心点：若样本 的 邻域内有大于 MinPts 的点
• 边界点：若样本 的在某一个核心点的 邻域内，但其自身的 邻域内没有大于 MinPts 的点
• 噪声：若样本 不在核心点的 邻域内

算法步骤：

• 首先选取任意一点，找到其 邻域内的所有点。如果点数多于 MinPts, 则此点为核心点，并被分配一个簇标签；如果点数少于 MinPts，则可能是噪声或者边界点，需要重新选取点

• 访问上一个核心点邻域内的所有节点，如果节点还没有被分配簇，那么就将他们分配到上一个核心点对应的簇；如果节点经过判断是核心点，那么就在他的基础上继续“扩张”，直到在簇的 邻域内没有更多的核心样本为止

  很像图的遍历

• 选取另一个尚未被访问过的点，并重复相同的过程

DBSCAN 的优点：

• 不需要像KMeans那样预先确定集群的数量
• 对异常值不敏感
• 能将高密度数据分离成小集群
• 可以聚类非线性关系(聚类为任意形状)

缺点：

• 很难在不同密度的数据中识别集群
• 难以聚类高维数据
• 对极小点的参数非常敏感

  和 MinPts 需要手动设置

Mean Shift

https://blog.csdn.net/google19890102/article/details/51030884

Mean Shift 算法，是一个迭代的步骤，即先算出当前点的偏移均值，将该点移动到此偏移均值，然后以此为新的起始点，继续移动，直到满足最终的条件。

步骤如下：

1. 定义区域大小
2. 初始化 位置
3. 计算 内部点均值
4. 移动 使其中心坐标为
5. 重复 3, 4 直到满足条件

这样就找到了一个簇的中心

kernel density estimation

采用核函数 来估计位置的概率密度函数
核函数满足：

• 偶对称：
• 归一化：

• 单调递减： when

  差异越大，那么所占权重就越小

• 期望为 0：

其中 h 为一个平滑参数，称作带宽

降维算法

PCA

主要思想是将 n 维特征映射到 k 维上，这 k 维是全新的正交特征也被称为主成分，是在原有n维特征的基础上重新构造出来的k维特征。

PCA的工作就是从原始的空间中顺序地找一组相互正交的坐标轴，新的坐标轴的选择与数据本身是密切相关的。其中，第一个新坐标轴选择是原始数据中方差最大的方向，第二个新坐标轴选取是与第一个坐标轴正交的平面中使得方差最大的，第三个轴是与第1,2个轴正交的平面中方差最大的。依次类推，可以得到n个这样的坐标轴。通过这种方式获得的新的坐标轴，我们发现，大部分方差都包含在前面k个坐标轴中，后面的坐标轴所含的方差几乎为0。

LDA

LDA 是一种基于有监督学习的降维方式,将数据集在低维度的空间进行投影,要使得投影后的同类别的数据点间的距离尽可能的靠近,而不同类别间的数据点的距离尽可能的远。

模型融合

bagging

Bagging是基于自助采样法采样出 个含 个训练样本的采样集，然后基于每个采样集训练一个基学习器，再将这些基学习器进行结合。

采样时，有放回地进行采样

样本每次采样某个样本不被采集到的概率 ，如果采样 m 次都不被采集到的概率为 ，当 m 趋向于无穷大时该值为

由于Bagging 算法每次都进行采样来训练模型，因此泛化能力很强，对于降低模型的方差很有作用。当然对于训练集的拟合程度就会差一些，也就是模型的偏倚会大一些。

boosting

Boosting 中基模型按次序进行训练,而基模型的训练集按照某种策略每次都进行一定的转化,最后以一定的方式将基分类器组合成一个强分类器。

Bagging 的训练集是在原始集中有放回的选取,而 Boosting 每轮的训练集不变,只是训练集中的每个样本在分类器中的权重都会发生变化,此权值会根据上一轮的结果进行调整。

Bagging 的各个预测函数可以并行生成, Boosting 的各预测函数只能顺序生成。

Bagging 和 Boosting 的区别：
1）样本选择上：Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
2）样例权重：Bagging：使用均匀取样，每个样例的权重相等。Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
3）预测函数：Bagging：所有预测函数的权重相等。Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
4）并行计算：Bagging：各个预测函数可以并行生成。Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。

距离度量

设有两点： 和

欧式距离

两者欧式距离定义为：

曼哈顿距离

两者曼哈顿距离定义为：

余弦距离

空间中的向量可以通过向量长度和角度加以确定；在定义两个向量相似度时完全可以只考虑角度，两个向量夹角越小，那么相似度越大。余弦相似度定义为：，在此基础上定义余弦距离：

• 欧式距离考虑的是距离上的绝对差异，余弦距离考虑的是方向上的相对差异；
• 余弦距离不满足‘三角不等式’，不是严格意义上的距离；
• 如何选择，视情况而定：两个人分别取了蓝球(1,0)与红球(0,1)，这两个向量的欧式距离较小，可是事实是这两个球是不同的,而余弦距离为2表示的是完全不同的意思。所以在这种情况下选择余弦距离更具合理性。再比如两个人对APP的使用次数与使用时长分别表示为(1,10),(10,100),可知余弦相似度较小，说明这两个人的行为时相同的，可是，事实是不同的，两个人的活跃度有着极大的差异，第二个人的活跃度更高。

正则化方法

L1 正则化

L1 更趋向于产生少量的特征,其它特征为0,最优的参数值很大概率出现在坐标轴上

L2 正则化

L2 会选择更多的矩阵,但是这些矩阵趋向于0

dropout

dropout 通常用于线性层; BN 多用于 CNN, BN 在一定程度上替代了 dropout 等。

在神经网络训练时遇到收敛速度很慢，或梯度爆炸等无法训练的状况时可以尝试BN来解决。另外，在一般使用情况下也可以加入BN来加快训练速度，提高模型精度。 深度学习的 tricks：Must Know Tips/Tricks in Deep Neural Networks

dropout 原理：使得激活输出部分失活，从而达到正则化的效果。因为模型越复杂其拟合能力越强，但是其过拟合训练集的概率越大，引入正则化就是希望模型尽可能简化，从而在一定程度上降低过拟合。