机器学习笔记

基本概念

• 泛化能力：模型对未知数据的预测能力

• 过拟合：在样本上准确率很高，但是在预测上准确率低，那这个模型就是过拟合模型

• 先验概率: 事件发生前的预判概率。可以是基于历史数据的统计，可以由背景常识得出，也可以是人的主观观点给出。一般都是单独事件概率，如P(x),P(y)。

• 后验概率: 事件发生后求的反向条件概率

• 条件概率: 一个事件发生后另一个事件发生的概率

• 最大似然理论: P(类别1 | w) > P(类别2 | w)，则认为w条件下，应该属于类别1

• 贝叶斯估计: 用最大似然估计，会出现某些概率值为0的情况，为了解决这个问题，可以在随机变量各个取值的频数上加一个正数$\lambda$, 当$\lambda$为0时，为最大似然估计，当$\lambda$为1时，为拉普拉斯修正

• 拉普拉斯修正: 训练集上，很多样本的取值可能并不在其中，但是这不并代表这种情况发生的概率为0，因为未被观测到，并不代表出现的概率为0, 所以我们给所有条件个数加1，总个数加上分类数，由$$P(c) = \dfrac{D_c}{D}$$ 修正为$$P(c) = \dfrac{D_c + 1}{D + N}$$ , 其中D为个数，N为分类数

• 方差与偏差的trade-off

• 欧拉距离 $$d(X, y) = \dfrac{1}{1 + \Sigma_{i=1}^n(X_i - Y_i)^2}$$ 分母加1，是为了防止分母为0，出现除0的错误

• 皮尔逊相关系数 等于协方差除了标准差的乘积 $$\rho(X, Y) = \dfrac{cov(X, Y)}{\sigma_X\sigma_Y} = \dfrac{ \Sigma_{i=1}^n(X_i - \bar{X})(Y_i - \bar{Y}) }{ {\sqrt{\Sigma_{i=1}^n(X_i - \bar{X})^2}} {\sqrt{\Sigma_{i=1}^n(Y_i - \bar{Y})^2}} }$$

• 在数据标准化之后，欧拉距离，皮尔逊相似度是等价的

• 余弦距离 $$sim(X, Y) = cos\theta = \dfrac{\vec{x}\vec{y}}{\Vert x \Vert\Vert y \Vert}$$ 余弦距离更注重两个向量的方向，而欧拉距离会关注位置。

• 杰卡德系数：两个集合A和B交集元素的个数在A、B并集中所占的比例，称为这两个集合的杰卡德系数 $$J(A, B) = \dfrac{\vert A \bigcap B \vert}{\vert A \bigcup B \vert}$$ 也叫Tanimoto系数

• 曼哈顿距离：所有维度之差的绝对值之和 $$d(X, Y) = \Sigma_{i=1}^n \vert X_i - Y_i \vert$$

• 闵可夫斯基距离 $$d(X, Y) = (\Sigma_{i=1}^n \vert X_i - Y_i \vert ^p)^{1/p}$$ 当p等于1时，为曼哈顿距离，当p等于2时，为欧拉距离 当p趋向无穷大时，为切比雪夫距离: $$\lim_{p\to\infty}(\Sigma_{i=1}^n \vert X_i - Y_i \vert ^p)^{1/p} = max_{i=1}^n\vert X_i - Y_i \vert$$

朴素贝叶斯分类

条件概率： $$P(A|B) = \dfrac{P(A \cap B)}{P(B)}$$ 贝叶斯定理 因为：$$P(A|B) = \dfrac{P(A \cap B)}{P(B)}$$ 所以： $$P(A \cap B) = P(A|B)P(B)$$ 所以：$$P(B|A) = \dfrac{P(A \cap B)}{P(A)} = \dfrac{P(A|B)P(B)}{P(A)}$$ $P(B|A)$ 是后验概率，$P(A)$, $P(B)$是先验概率，$P(A|B)$是条件概率 假定有一个很大的训练集，和一个结果集。训练集里面每一条记录，有很多特征，比如 性别：{男，女}，学历：{博士，硕士，本科，大专} 结果类别为: {好股，差股} 可以直接计算得到概率P(男|好股) 根据贝叶斯定理，P(好股|男) = P(男|好股)*P(好股)/P(男) 现在，给定一条记录，如果性别是男，学历是博士，用来预测是好股还是差股，即分类。 相当于求P(好股|男)*P(好股|博士)的概率，再求P(坏股|男)*P(坏股|博士)的概率，哪个大则分到哪个类里面 优点：容易实现, 能反映真正的数据 缺点：性能不高

决策树

基尼不纯度

基尼不纯度（Gini Impurity）是决策树里常用的一种衡量划分优劣的指标$$I_G(p) = \Sigma_{i=1}^n p_i(1 - p_i)$$#### 熵 熵，表示某个随机变量的不确定性 熵越大，不确定性越大，类别越多，如果只有一个类别，则熵为0 条件熵，表示在某个条件下，某个随机变量的不确定性 信息增益 = 熵 - 条件熵 条件熵越小，说明这个条件对于不确定性贡献越小，那信息增益越大，说明这个条件分类越准确 信息增益值是相对于训练数据集而言的，如果总熵太大，则信息增益也会很大，那就没有可比性。所以要用信息增益比: $$g_R(D, A) = \dfrac{g(D, A)}{H(D)}$$ 其中，D是数据集，A是特征，H(D)是总熵，g(D, A)是信息增益

ID3

在决策树各结点上应用信息增益选择的规则，取信息增益最大的那个特征(贪心)。相当于用极大似然法选择概率模型 只能用于分类，不能处理连续型数值，所以不能用于回归。不关心是否最优，很贪心。 假定有一个很大的训练集，和一个结果集。训练集里面每一条记录，有很多特征，比如 投票数：{0100, 1001000, 1000以上}, 分别表示为{low, middle, high} 字数：{020, 2050, 50~200, 200以上}，分别表示为{less, normal, many, lots} 结果类别为: {好答案，差答案}, 分别表示为{good, worse} 假设训练集总数为120条, 好答案为60条，差答案为60条 好答案的概率： $$P(good) = \dfrac{|good|}{|total|} = \dfrac{60}{120} = 0.5$$ 差答案的概率： $$P(worse) = \dfrac{|worse|}{|total|} = \dfrac{60}{120} = 0.5$$ 总熵 $$Entropy = -P(good)log2(P(good)) - P(worse)log2(P(worse))$$ $$= -0.5 * log2(0.5) - 0.5 * log2(0.5) = 0.5 + 0.5 = 1$$ 假设好答案中投票数三种类型的记录的条数为： low: 10 middle: 20 high: 30 差答案中投票数三种类型的记录的条数为： low: 30 middle: 20 high: 10 则： $$P(low) = \dfrac{|low|}{|total|} = (10 + 30) / 100 = 0.4$$ $$P(lowInGood) = \dfrac{|lowInGood|}{|low|} = 10 / 40 = 0.25$$ $$P(lowInWorse) = \dfrac{|lowInWorse|}{|low|} = 30 / 40 = 0.75$$ $$P(middle) = \dfrac{|middle|}{|total|} = (20 + 20) / 100 = 0.4$$ $$P(middleInGood) = \dfrac{|middleInGood|}{|middle|} = 20 / 40 = 0.5$$ $$P(middleInWorse) = \dfrac{|middleInWorse|}{|middle|} = 20 / 40 = 0.5$$ $$P(high) = \dfrac{|high|}{|total|} = (30 + 10) / 100 = 0.4$$ 那么条件熵为： $$Entropy(vote) = [-P(good)log2(P(good) - P(worse)log2(P(worse))$$

C4.5

ID3是用信息增益最大的特征，C4.5是用信息增益比最大的特征 C4.5 可以处理连续型的变量，但是还是只能用于分类

CART

classification and regression tree 采用基尼指数来判断划分的好坏 再剪枝: 从根开始遍历，如果2个叶节点合并之后，减少的熵小于某个给定的值，说明这2个叶节点分开来作用不大，合并这2个叶节点

logistic回归

使用最大似然估计，对数似然后，推导出来的损失函数其实就是softmax

梯度下降

导数

当函数定义域和取值都在实数域中的时候，导数可以表示函数曲线上的切线斜率。 除了切线的斜率，导数还表示函数在该点的变化率 导数的物理意义表示函数在这一点的 (瞬时) 变化率 $$S = vt$$ $$a = \dfrac{\Delta v}{\Delta t}$$ $$\lim_{t\to0}\dfrac{\Delta v}{\Delta t} = \lim_{t\to0}\dfrac{f(v0 + \Delta v) - f(v0)}{\Delta t}$$

偏导数

其实就是多维的情况下，对某一维进行求导，这个好理解

方向导数

设 $z = f(x, y)$ 在一点 $P_0(x_0, y_0)$的一个邻域内有定义，又设 $\vec {l}$ 是给定的一个方向，其方向余弦为$\cos\alpha, \cos\beta$，若极限 $$\lim_{t\to0}\dfrac{f(x_0 + t\cos\alpha, y_0 + t\cos\beta) - f(x_0, y_0)}{t}$$ 存在，则称此极限值为函数$z = f(x, y)$在$P_0$点沿方向 $\vec {l}$ 的方向导数，其中点t是点$P_0(x_0, y_0)$到点$P_t(x_0 + t\cos\alpha, y_0 + t\cos\beta)$的距离 其实，偏导数是方向导数是特殊形式，是方向为坐标轴方向的方向导数，而导数为偏导数的特殊形式，是一元的偏导数。

梯度

梯度是一个有方向的向量。 梯度的方向呢是使得方向导数达到最大值的方向，它的模就是方向导数的最大值 而把所有的偏导数写成一个向量形式，得到的向量（f'(x),f'(y),f'(z)）就是梯度。梯度意味着方向导数变化最大 | 概念|物理意义 | |-------|------| | 导数 | 函数在该点的瞬时变化率| | 偏导数 | 函数在坐标轴方向上的变化率| | 方向导数 | 函数在某点沿某个特定方向的变化率| | 梯度 | 函数在该点沿所有方向变化率最大的那个方向|

• 梯度消失：反向传播时，误差是一个小于1的数，不断减小，最后趋近于0
• 梯度爆炸：反向传播时，误差是一个大于于1的数，不断增大，最后无穷大

支持向量机

• 支持向量(support vector)就是离分隔超平面最近的那些点 使用的损失函数是Hinge loss: $$L(m_i) = max(0, 1 - m_i(w))$$

Apriori

• 置信度体现了一个数据出现后，另一个数据出现的概率，或者说数据的条件概率。如果我们有两个想分析关联性的数据X和Y，X对Y的置信度为 Confidence(X⇐Y)=P(X|Y)=P(XY)/P(Y)

• 提升度表示含有Y的条件下，同时含有X的概率，与X总体发生的概率之比，即: Lift(X⇐Y)=P(X|Y)/P(X)=Confidence(X⇐Y)/P(X)提升度体先了X和Y之间的关联关系, 提升度大于1则X⇐YX⇐Y是有效的强关联规则， 提升度小于等于1则X⇐YX⇐Y是无效的强关联规则 。一个特殊的情况，如果X和Y独立，则有Lift(X⇐Y)=1Lift(X⇐Y)=1，因为此时P(X|Y)=P(X)P(X|Y)=P(X)。

图示

特征处理

NMF

非负矩阵分解，V为原矩阵，W为权重矩阵，H为特征矩阵， $$V \approx WH$$

PCA

• PCA（Principal Component Analysis）, 降维
• 将二维平面的点降为一维，相当于变成一条直线上的点，相当于将这些点投影到一条直线上，要想降维后数据尽可能不丢失，那这条直线上保留的点应该尽可能的多，说明应该让这些点尽可能地离散，那就是让这些点的方差最大
• 考虑到三维降到二维的情况，我们还要找一个方向，使得各个点之间相互独立，即协方差为0，所以协方差矩阵会变成对角线上是方差，而其他地方为0，这叫做协方差矩阵的对角化
• 要想让协方差矩阵对角化，我们要对这个矩阵做变换，让它对角化。而由于协方差矩阵是一个实对称矩阵，所以只要将它进行特征值分解，得到特征向量和特征值，特征值就是对角线上的方差。
• 取最大的k个方差(特征值)对应的特征向量，乘以原始数据，就是降维后的数据

协同过滤

• 找出与该用户相似度较高的用户
• 根据相似用户的评分A，预测用户的评分(A乘以相似度)，然后排序，就可以向用户进行推荐了

机器学习的模型的种类

判别模型与生成模型

常见的判别模型有线性回归、对数回归、线性判别分析、支持向量机、boosting、条件随机场、神经网络等。常见的生产模型有隐马尔科夫模型、朴素贝叶斯模型、高斯混合模型、LDA、Restricted Boltzmann Machine等

• 生成方法可以还原原数据的概率分布，收敛速度更快，并且可以发现隐变量，判别方法则做不到这3点
• 判别方法准确率更高，可以简化学习问题

参数模型与非参数模型

• 参数模型就是假设一个函数的形式，通过不断的学习调整这个函数的参数，以达到最优如: logistic回归，朴素贝叶斯，MLP, LDA
• 非参数模型就是不假设一个特定的函数形式，自由的学习，直到达到最优如: 决策树，SVM, KNN

分类问题/回归问题/标注问题

• 分类：输出为离散数据
• 回归: 输入和输出都为连续数据
• 标注问题: 输入和输出都为序列，分类问题输出为哪一个类别，标注问题输出为一个向量。词性标注为这一类

经验风险最小化与结构风险最小化

• 经验风险最小化(empirical risk minimization, ERM)$$min(\dfrac{1}{N}\Sigma_{i=1}^N L(y_i, f(x_i))$$这是平均损失，当N趋向无穷大时，平均损失趋近期望损失。极大似然估计属于这种
• 结构风险最小化(structural risk minimization, SRM) $$min(\dfrac{1}{N}\Sigma_{i=1}^N L(y_i, f(x_i)) + \lambda J(f)$$$J(f)$是模型复杂度， 属于惩罚项， 最大后验概率估计属于这种。

准确率/精确率/召回率

• TP(true positive): positive的预测对了，将正类预测为正类
• FP(false positive): positive的预测错了，将负类预测为正类
• TN(true negative): negative的预测对了，将负类预测为负类
• FN(false negative): negative的预测错了，将正类预测为负类
• 准确率(accuracy): 预测对的占所有的比例$\dfrac{TP + TN}{TP + FP + TN + FN}$
• 精确率(precision): 对于预测结果的正类而言，计算预测为正类的里面，有哪些是真正预测对的$\dfrac{TP}{TP + FP}$
• 召回率(recall):对于样本中的数据而言，计算原来的正类中，预测为正类的，占所有的预测结果的比率$\dfrac{TP}{TP + FN}$

各种范数

绝对值其实便是一维向量空间中实数或复数的范数范数的一般化定义$$\vert\vert x \vert\vert_p = (\Sigma_{i=1}^n \vert x_i \vert^p)^{1/p}$$

L0范数

L1范数

即曼哈顿距离

L2范数

欧几里得距离，

EM算法

Expectation Maximization

线性回归

Lasso回归和Ridge回归都是用于解决过拟合问题的。回归问题解决过拟合问题有两种方法

• 丢弃某些不重要的特征，如使用PCA来实现
• 保留所有特征，改变损失函数的形式线性回归的损失函数:$$J(\theta) = \dfrac{1}{2m}\Sigma_{i=1}^m(h_\theta(x^i) - y^i)^2$$

L1(Lasso回归)

损失函数:$$J(\theta) = \dfrac{1}{2m}\Sigma_{i=1}^m(h_\theta(x^i) - y^i)^2 + \lambda\Sigma_{j=1}^n | \theta_j |$$L1范数惩罚项

L2(岭回归)

损失函数:$$J(\theta) = \dfrac{1}{2m}\Sigma_{i=1}^m(h_\theta(x^i) - y^i)^2 + \lambda\Sigma_{j=1}^n \theta_j^2$$L2范数惩罚项

Elastic Net(弹性网络)

$$J(\theta) = \dfrac{1}{2m}\Sigma_{i=1}^m(h_\theta(x^i) - y^i)^2 + \lambda\rho\Sigma_{j=1}^n |\theta_j| + \dfrac{\lambda(1 - \rho)}{2}\Sigma_{j=1}^n \theta_j^2$$组合了L1和L2惩罚项

广义线性模型(GLM, General linear model)

一个回归模型输出的是连续值，加上一个连接函数后，可以产生离散值或连续值，这就是广义线性模型。 伯努利分布(0-1分布), 根据GLM模型，可推导出sigmoid函数，用于二分类问题。 多项分布推导出softmax函数，用于多分类问题。

集成学习

Bagging

多个分类器集成

• 随机森林 并行训练，通过降低方差来降低误差

boosting

Boosting 树以迭代方式建立在弱学习器身上。在每次迭代中，都会添加一个新的学习器，而所有现有的学习器都保持不变。所有的学习器根据他们的表现（例如，准确性）进行加权，并且在加入弱学习器之后，对数据进行重新加权：错误分类的样例获得更多的权重，而正确分类的样例减少权重。因此，未来的弱学习器会更多地关注之前的弱学习器错误分类的样例 顺序训练，通过减少偏差来降低误差

stacking

首先将训练集分为两个子集：第一个子集用于训练第一层的学习器接下来，第一层学习器被用于对第二子集进行预测（元特征），并且这些预测被用于在第二层训练另一个模型（以获得不同学习器的权重）

凸优化

改进的迭代尺度法

improved iterative scaling , IIS算法

牛顿法和拟牛顿法

牛顿法和拟牛顿法一般收敛比较快，梯度下降法收敛比较慢

梯度下降法

聚类

DBSCAN

基于密度的聚类算法，不用指定聚多少个类