机器学习知识点汇总

一、支持向量机，support vector machine，SVM

找到一个超平面将不同的数据分隔开，并且该使得该超平面到支持向量间的间隔最大化。

1. 函数间隔：在超平面wx+b=0确定的情况下，|y||wx+b|能够表示点x到距离超平面的远近，y*(w*x+b)的正负性表示分类的正确性。
2. 几何间隔：即点到超平面的距离，$\frac{|y||w\ast x+b|}{||w||}$，如果成比例的改变超平面的w和b时几何间隔不变。
3. 最终目标函数为：
   
   （1）其中取y的值为1和-1，是为了计算方便和几何意义明确。实际取任何值都可以，只要不同的类的点函数值有不同的符号即可。（2）支持向量刚好在虚线间隔边界上，即y*(wx+b)=1。对于所有不是支持向量的点，则显然有y(w*x+b)>1。
4. 目标函数最大化问题转为最小化问题：
   
   （1）目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。（2）可以用现有的Quadratic programming(二次规划)包求解。（3）或者手动求解。
5. 通过拉格朗日乘子法，目标函数变成了：
   
   
6. 再得到与原问题等价的对偶问题：
   
   （1）为了容易求解，将minmax原始问题转化为maxmin对偶问题，即先求L 对w、b的极小，再求L 对的极大。（2）原问题是满足 KKT 条件的，所以原问题能有最优化解法，所以可以转化成了对偶问题。
7. $\alpha$固定，分别对w，b求偏导数，再令 ∂L/∂w 和 ∂L/∂b 等于零。求得的结果代入$L(w,b,\alpha )$，此时拉格朗日函数只包含了$\alpha$变量，目标函数为：
8. 可以利用SMO算法求解对$\alpha$的极大，得出最终的w和b。
   所以分类超平面为：
   
   （1）对于新点 x的预测，只需要计算它与训练数据点的内积即可（2）同时发现：非Supporting Vector 所对应的系数都是等于零的，因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据（3）直观上来理解的话，“支持向量”后方的点对超平面是没有影响的，超平面只与“支持向量”有关。
9. 通过引入核函数，将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。从而解决了非线性分类问题，此时的分类超平面为：
   （1）核函数为ϕ，该非线性映射函数能将数据数据变换到另一个特征空间。（2）核函数方法：在特征空间中直接计算内积〈φ(xi · φ(x)〉，避开了直接在高维空间中进行计算。（3）手工构造出对应的核函数比较困难，通常直接用一些常用的核函数，如多项式核、高斯核、线性核。

二、核函数

三、从线性回归到逻辑回归，Logistic Regression，LR

1. 线性回归可以建模为（回归问题）：
   y = β0 + β1x1 + β2x2 + … + βn*xn + ε
   （1）其中，β0, β1, β2, …, βn 是模型的参数，ε是误差项。
   （2）求解模型参数：
   • 使用最小二乘法来求解参数，使得模型的预测值 ŷ 与真实值 y 的残差平方和最小化
   • 损失函数的角度：最小化均方差损失函数，用梯度下降法。
2. 逻辑回归可以建模为（分类问题）：
   p(y=1|x) = sigmoid(β0 + β1x1 + β2x2 + … + βn*xn)
   （1）其中，β0, β1, β2, …, βn 是模型的参数，sigmoid函数为：sigmoid(z) = 1 / (1 + exp(-z))，可以将线性回归模型的输出值映射到[0,1]的概率值。
   （2）求解模型参数：
   • 使用最大似然法来求解参数，使得模型对训练数据的似然值最大化
     
   • 损失函数的角度：最小化对数损失函数，即
     
     这时发现，最小化对数损失函数=最小化二分类交叉熵损失函数=最大化对数似然函数，再用梯度下降法求解。

四、防止过拟合的方法

正则化：经验风险加正则化项来使得结构风险最小化，L1范数会趋向于产生少量的特征，而其他的特征的参数都是0，而 L2会选择更多的特征，这些特征的参数都会接近于0。

1. L1范数（Lasso正则化、曼哈顿距离、稀疏规则算子）：是指向量中各个元素绝对值之和。$||w|{|}_{p=1}={\sum }_{i=1}^n|w_i|$越小，参数越稀疏，去掉了没有信息的特征，也就是把这些特征对应的权重置为0，实现特征的自动选择。
2. L2范数（Ridge正则化、欧氏距离、权值衰减）：$||w|{|}_{p=1}=\sqrt{{\sum }_{i=1}^n{w}_i^2}$越小，参数越小越接近于0，能够缓解过拟合问题。

Dropout：在训练过程中，随机丢弃一部分神经元，从而使模型对某些特定的输入不敏感，减少了模型的依赖性，避免过拟合。当用训练好的模型进行预测时，设置dropout概率为0或者移除dropout层，此时Dropout是不起作用的。

Batch Normalization（批归一化）：在每一层的激活函数之前，对每个Batch的数据进行标准化处理，使得每个特征的均值为0、方差为1，所以是在 channel维度上对每个Batch的数据进行标准化。最后，通过缩放和平移操作，将标准化后的特征映射到一个新的范围来增强模型的表达能力。

Layer Normalization（层归一化）：在每个样本上，即在 C、H 和 W 这 3 个维度上进行标准化处理，即对每个样本的多个特征进行标准化处理，并且针对每个样本的所有特征分别进行缩放和平移（区别：BN针对的是单个特征）。

Early Stopping：根据交叉叉验证提前终止: 若每次训练前, 将训练数据划分为若干份, 取一份为测试集, 其他为训练集, 每次训练完立即拿此次选中的测试集自测. 因为每份都有一次机会当测试集, 所以此方法称之为交叉验证.。交叉验证的错误率最小时可以认为泛化性能最好, 这时候训练错误率虽然还在继续下降, 但也得终止继续训练了。

五、实对称矩阵

六、决策树

ID3 算法中，我们使用信息增益来选择最优分裂特征。信息增益是在当前节点选择某个特征进行分裂后，信息熵减少的程度。

C4.5 算法在 ID3 算法的基础上进行了改进，它使用信息增益比来选择最优分裂，以避免属性取值数目较多时出现偏向的情况。

CART 决策树使用基尼指数来计算最优分裂。基尼指数表示随机抽取两个样本，其类别标记不一致的概率，它越小表示样本集的纯度越高。最终，选择基尼指数最小的特征作为当前节点的划分特征。

七、Boost

Bagging方法有放回地采样同数量样本训练每个学习器, 然后再一起集成(简单投票);
Boosting方法使用全部样本(可调权重)依次训练每个学习器, 迭代集成(平滑加权)；

• Adaboost, Adaptive Boosting, 采用指数损失函数替代原本分类任务的0/1损失函数
  

• GBDT, Gradient Boosting Decision Tree，对函数残差近似值进行梯度下降

• XGboost类似于GBDT的优化版, 对函数残差近似值进行梯度下降, 迭代时利用了二阶梯度信息，是用泰勒展式二项逼近，而不是像gbdt里的就是一阶导数，对树的结构进行了正则化约束，防止模型过度复杂，降低了过拟合的可能性

八、判别式模型和生成式模型

判别方法：由数据直接学习决策函数 Y = f（X），或者由条件分布概率 P（Y|X）作为预测模型，即判别模型。

• K近邻、SVM、决策树、感知机、线性判别分析（LDA）、线性回归、传统的神经网络

生成方法：由数据学习联合概率密度分布函数 P（X,Y）,然后求出条件概率分布P(Y|X)作为预测的模型，即生成模型。

• 朴素贝叶斯、隐马尔可夫模型

九、主成分分析

 -> 输入原始数据矩阵 X
 -> 对 X 进行标准化处理
 -> 计算样本协方差矩阵 S
 -> 对 S 进行特征值分解，得到特征值和特征向量
 -> 将特征向量按照特征值从大到小排序
 -> 选择前 k 个特征向量作为主成分，其中 k 表示保留的主成分数目
 -> 输出主成分方差贡献率和主成分权重向量
1
2
3
4
5
6
7

PCA降维的目的，就是为了在尽量保证“信息量不丢失”的情况下，对原始特征进行降维，也就是尽可能将原始特征往具有最大信息量的维度上进行投影。将原特征投影到这些维度上，使降维后信息量损失最小。

由于协方差矩阵对称，因此k个特征向量之间两两正交，也就是各主成分之间正交，正交就肯定线性不相关，可消除原始数据成分间的相互影响