归纳&总结

2019-01-28 本文已影响0人 yi_cloud

机器学习技能树整理

按问题类型划分

分类问题

Logistic Regression

总结：特征的线性组合+非线性映射。推导时从单个样本开始，单个样本经过sigmoid函数后划分为正类的概率为：

$P(\hat{y} _i=1|\mathbf x_i)=\frac {1}{1+e^{-\theta^T\mathbf x_i}}$ ，由于sigmoid函数值域为[0,1]，负类概率为 $P(\hat y_i=0|\mathbf x_i)=1-P(\hat y_i=1|\mathbf x_i)=1-\frac {1}{1+e^{-\theta^T\mathbf x_i}}=\frac {e^{-\theta^T\mathbf x_i}}{1+e^{-\theta^T\mathbf x_i}}$

将上述两个式子整理成一个式子：

$h(\mathbf x_i)=P(\hat{y} _i=1|\mathbf x_i)^{y_i}\cdot P(\hat{y} _i=0|\mathbf x_i)^{1-y_i}$

结合样本间独立同分布(i.i.d)假设，所有样本的联合概率分布为：

$H(\mathbf X)=\prod_{i=1}^n P(\hat{y} _i=1|\mathbf x_i)^{y_i}\cdot P(\hat{y} _i=0|\mathbf x_i)^{1-y_i}$

等式两边取对数，得到对数分布：

$log H(\mathbf X)=\sum_{i=1}^n y_i logP(\hat{y} _i=1|\mathbf x_i) +(1-y_i)logP(\hat{y} _i=0|\mathbf x_i)$

接下来的求解使用极大似然估计的思想即可。

Factorization Machine

总结：FM在线性模型的基础上引入了特征间的二次组合项。 $f(\mathbf x,\mathbf w)=\omega_0+\sum_{i=1}^{n}w_i x_i+\sum_{i=1}^{n-1}\sum_{j=i}^{n}w_{i,j}x_ix_j$

FM的提出是为了解决特征高度系数的问题，太多的零项交叉导致二阶w矩阵无法求解，因此引入隐向量的概念，每一维特征都对应一个k维向量v。

FM的求解过程巧妙的消解了交叉项，这也是FM的精髓所在。

AdaBoost(也可以做回归，但一般不用)

总结：AdaBoost最绝妙的地方在于借用：

①指数损失函数 $e^{a+b}=e^a\cdot e^b$ 的性质，将加法模型中 $f_{m-1}(\mathbf x)+\beta_m b(\mathbf x,\gamma_m )$ 迭代项分裂开；

②逻辑回归中预测值和实际值结乘积 $xf(x)$ ，该式只和分类是否正确有关而和具体分类结果无关。

具体推导过程可以参考https://www.cnblogs.com/gasongjian/p/7648633.html

Naive Bayes

朴素贝叶斯的关键点在于如何将求解步骤三中各项后验概率的值，也就是给定x的情况下该样本属于某类的概率。

根据贝叶斯公式 $P(Y|X)=\frac {P(X|Y)P(Y)}{P(X)}$

那么对于某个样本i来说 $argmax_{c} p(y=c_j|\mathbf x)=\frac {p(\mathbf x|y={c_j})p(y={c_j})}{p(\mathbf x)}$

将分母展开 $p(\mathbf x)=\sum_{j=1}^{C}p(\mathbf x|y=c_j)p(y=c_j)$

因此只需要求 $argmax_{c} p(y=c_j|\mathbf x)\propto \prod _{i=1}^{F}{p( x_i=a_i|y={c_j})p(y={c_j})}$

Decision Tree/Random Forest

总结：决策树分为ID3和C4.5，两者最大的不同在于如何选择分裂属性，因此首先要知道熵的几种计算方式：

熵：表示随机变量X概率分布的不确定性， $H(X)=-\sum_{i=1}^{n}p_ilog(p_i)$

条件熵：已知随机变量X时，随机变量Y的不确定性， $H(Y|X)=\sum P(X=x_i)H(Y|X=x_i)$

信息增益（ID3）：特征A对数据集D的信息增益 $g(D,A)=H(D)-H(D|A)$ 表示使用A对数据集D分类能够减少的不确定性程度。

信息增益比(C4.5)：信息增益与数据集D关于A的取值概率分布的熵 $g_R(D,A)=\frac {g(D,A)}{H_A(D)}$

注意区别条件熵 $H(D|A)$ 和 $H_A(D)$

基尼不纯度(CART)：表示一个随机选中的样本在子集中被分错的可能性， $Gini(x)=\sum_{k=1}^Kp_k(1-p_k)=\sum_{k=1}^Kp_k-\sum_{k=1}^Kp_k^2=1-\sum_{k=1}^Kp_k^2$

决策树算法框架：

回归问题

Linear Regression

总结：线性回归是一切回归问题的基础，不管数据是否是明确的线性可分，都可以尝试，非线性数据的用核函数映射到高维后，再做线性回归即可。

线性回归用最小二乘法（最小平方损失）求解，具体参考https://www.cnblogs.com/futurehau/p/6105011.html

Ridge/Lasso Regression

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

带约束最优化问题：

$argmin_w\sum_{i=1}^N(h(\mathbf x_i,w)-y_i)^2 \\ s.t.\sum_{j=1}^M|w_j|^q\leq \eta$

转化为无约束最优化问题：

$argmin_w\sum_{i=1}^N(h(\mathbf x_i,w)-y_i)^2+\lambda|\omega_i|^q$

式子q表示范数，q=1是L1范数，q=2则是L2范数。通常带约束的形式是最原始的优化模型，但是不好求解，因此转化为无约束形式。两种形式等价的条件是带约束最优化是凸优化。

用一个直观的例子解释L1的作用：

下面两个图可以很直观的感受到，L1正则项在做的事情就是让原本较小的 $\omega$ 为0（可以理解成舍弃不太重要的特征维度，因此L1也有降维和特征选择的作用），让原本很大的 $\omega$ 为 $\eta$ （即强度不超过 $\eta$ ）

不同维度权重差距较小，无法得到稀疏解

不同维度权重差距很

Regression Tree

分类&回归

SVM

CART

当CART树用作回归时也叫做最小二乘回归树。自然地，选择误差平方和作为损失函数。某个特征上的最有切分点能够使划分后左右子树分别对应的损失函数和最小，表示成公式就是：

$min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2$

当CART树用作分类时又叫做基尼指数最小化分类树。确定特征A上划分点的公式为：

$argmin_aGini(D,A=a)=\frac {|D_1|}{|D|}Gini(D_1)+\frac {|D_2|}{|D|}Gini(D_2)$

不管分类树还是回归树最优切分点和最优特征的搜索过程都是一样的，唯一的区别就是确定最优切分点的方式。

GBDT/XGBoost(CART Based)

GBDT和XGBoost的弱分类器都是CART，自然也能同时解决分类和回归问题，并且也不要求输入都是离散或连续变量，对特征工程要求较低。

聚类问题

KNN

K-means

层次聚类

其他无监督方法

Manifold Learning(Dimension Deduction): PCA /LDA/ AutoEncoder

Matrix Decomposition: SVD/SVD++/NMF/LFM

总结：

SVD矩阵奇异值分解是推荐系统工程中常用的一种算法，理解的关键点

① 为什么(m,n)维矩阵M能够分解成 $M=U\Sigma V^T$ 的形式？

以二维空间中的任意矩阵M为例，总能找到一组标准正交基 $\vec{v}_1,\vec{v}_2$ ，使得 $M\vec{v}_1,M\vec{v}_2$ 是正交的，设 $\sigma_1=||M\vec{v}_1||,\sigma_2=||M\vec{v}_2||$ ，那么存在另一组正交基 $\vec u_1,\vec u_2$ ，使得：