机器学习算法总结

本文将总结机器学习基本算法的目的，输入和输出，训练的参数，训练方法（误差函数的选择，调参方法）等等

1. 线性回归

函数形式（训练目标）：多元线性回归试图学得
$f(x_i)=w^Tx+b\:\:st.\:\:f(x_i) = y_i$
函数的好坏度量：
$L(w,b) = (\mathbf{y-X\hat{w}})^T(\mathbf{y-X\hat{w}})$
对w_hat求导可得：
$\frac{\partial E_{\hat{w}}}{\partial \hat{w}} = 2\mathbf{X^T(X\hat{w}-y)}$
上式得0可得w_hat最优解的闭式解（但是有可能参数过多，无法求出）

或者使用梯度下降对参数进行调整，得：
$w_i = w_i - \eta\sum_{n}-(\hat{y}^n-f_{w,b}(x^n))x_i^n$

2. logistic回归

函数形式（训练目标）：逻辑回归处理分类问题，如果结果大于0.5结果为类别1，否则为类别2
$f_{w,b}(x) = \sigma(\sum_{i}w_ix_i+b)$
函数的好坏度量：
$L(w,b) = f_{w,b}(x^1)f_{w,b}(x^2)(1-f_{w,b}(x^3))...f_{w,b}(x^N)$

找出最大化上述函数的w,b, 即得到最好的函数。最终化简结果为交叉熵, 即求下列函数右侧的最小值
$-lnL(w,b) = \sum_{n}-[\hat{y}^{n}lnf_{w,b}(x^n)+(1-\hat{y}^n)ln(1-f_{w,b}(x^n))]$
计算这个式子对w偏微分，得到
$\frac{-lnL(w,b)}{\partial w_{i}} = \sum_{n}-(\hat{y}^n-f_{w,b}(x^n))x_i^n$
使用梯度下降法进行优化，直观就是观察预测值和实际值的差距，差距越大就更新越多
$w_i = w_i - \eta\sum_{n}-(\hat{y}^n-f_{w,b}(x^n))x_i^n$
这个式子和线性回归得到的式子一样的，区别是预测值和实际值的范围不同，逻辑回归是0到1，线性回归是实数范围

Tips

梯度下降法需要函数是可微分的
回归任务的损失函数：最小二乘误差
最大似然和最小误差的关系：目的相同，都是找到最佳的函数
MLE: Maximum likelihood Estimate, 极大似然估计
$Bayes : P(h|D) \frac{P(D|h)*P(h)}{P(D)}$
上式中，h为假设，即最终的函数形态，D为数据，左侧后验概率代表已知数据，假设为h的概率。右侧分子第一项代表已知假设，求得数据集是已知数据集的概率，即似然概率，p(h)则是先验概率。在线性回归中，可以通过高斯假设得出最大可能假设是最小化平方损失函数的假设。详细过程见证明最小二乘假设的合理性。

3.信息论基本概念

熵, $X$ 是离散型随机变量，取值空间为R。熵又称为自信息，可以视为描述一个变量的不确定性的值
$H(X) = -\sum_{x\epsilon R}p(x)log_2p(x)$
联合熵，X,Y是一对离散型随机变量，遵守 $p(x,y)$ 分布，联合熵定义为：
$H(X,Y) = -\sum_{x\epsilon X}\sum_{y\epsilon Y}p(x,y)logp(x,y)$
给定随机变量X的情况下，Y的条件熵定义为：
$H(Y|X) = \sum_{x\epsilon X}p(x)H(Y|X=x)$
展开可得：
$H(Y|X) =- \sum_{x\epsilon X}\sum_{y\epsilon Y}p(x,y)logp(y|x)$
连锁法则

将联合概率展开，可得熵的连锁法则
$H(X,Y) = H(X) + H(Y|X)$
互信息 $I(X,Y)$ 反映的是知道了Y的值以后X的不确定性的减少量
$I(X,Y) = H(X) - H(X|Y) = \sum_{x,y}p(x,y)log\frac{p(x,y)}{p(x)p(y)}$
互信息体现了两变量之间的依赖程度，如果互信息得0，两变量相互独立
相对熵，是衡量相同事件空间里两个概率分布相对差距的测度，两个概率分布p(x)和q(x)的相对熵定义为：
$D(p||q) = \sum_{x\epsilon X}p(x)log\frac{p(x)}{q(x)}$
交叉熵用来衡量估计模型与真实概率分布之间的差异情况。
$H(X,q) = H(X) + D(p||q) = -\sum_xp(x)logq(x)$

4. 支持向量机

函数形式（训练目标）：

线性向量机：
$f(x) = \sum_iw_ix_i + b = \begin{bmatrix} w \\ b \end{bmatrix}dot \begin{bmatrix} x \\ 1 \end{bmatrix}$
损失函数：这里面的loss都是一个训练样例的loss, 累加之后才得到系统的所有loss
$hinge\;loss :l(f(x^n),\hat{y}^n) = max(0,1-\hat{y}^n(f(x^n)*(f(x^n))(0)$

${12} Square\;loss + Sigmoid :l(f(x^n),\hat{y}^n)=(\sigma(\hat{y}^nf(x))-1)^2\;(1)$ {12}

$Sigmoid + cross\;entropy\;\;l(f(x^n),\hat{y}^n) = ln(1+exp(-\hat{y}^nf(x))) \; (2)$
由（0）可推导出损失函数（cost_1为label为1的损失函数）：
$\left\{\begin{matrix} max(0,-x+1) (y^{i}=1) \\ max(0,x-1) (y^{i}=0) \end{matrix}\right.$

$J(\theta) = C\sum_{i=1}^{m}[y^{(i)}cost \;t_1(\theta^Tx^{(i)})+(1-y^{(i)})cost\;t_0(\theta^Tx^{(i)})]+\frac{1}{2}\sum_{j=1}^{n}\theta_j^2$
这里的 $C = \frac{m}{\lambda}$ , C越大，SVM的决策边界margin也越大

当C越大时，margin也越大，我们的目标是最小化代价函数 $J(\theta)$ , 所以C的乘积项
$\sum_{i=1}^{m}[y^{(i)}cost \;t_i(\theta^Tx^{(i)})+(1-y^{(i)})cost\;t_0(\theta^Tx^{(i)})]$
要很小。最终近似为：
$J(\theta) = C*0+\frac{1}{2}\sum_{j=1}^{n}\theta_j^2 = \frac{1}{2}(\theta_1^2+\theta_2^2)$
我们的目标是求使代价最小的 $\theta$

几何论证：对于任意一个点，根据分类条件得出以下限制：
$\left\{\begin{matrix} \theta^Tx^{(i)}\geqslant1 (y^{i}=1) \\ \theta^Tx^{(i)}\leqslant-1 (y^{i}=0) \end{matrix}\right.$
将上述看为x和各个系数的点积，化为几何概念，可以得到：
$\left\{\begin{matrix} p^{(i)}||\theta||\geqslant1 (y^{i}=1) \\ p^{(i)}||\theta||\leqslant-1 (y^{i}=0) \end{matrix}\right.$

到 $\theta$ 上的投影为p,则 $p||\theta||>=1$ 或者 $p||\theta||<=-1$ , 如果因为要求 $\theta$ 很小，所以p要求很大，最终求得的就是点在 $\theta$ 方向投影最小，即在与 $\theta$ 垂直的决策边界上投影最大。

RBF Kernel核函数

RBF核函数，即高斯核函数，公式为：
$f(x) =e^{-\frac{||x-u||^2}{2\sigma^2}}$
Sigmoid Kernel核函数
$K(x,z) = tanh(x .dot \;z)$

支持向量机(解释二)(其实二者的区别在于label为0和1还是-1和1)

如果是后者，则可以把代价函数合并，如下：

函数形式（训练目标）：
$f(x) = \sum_iw_ix_i + b = \begin{bmatrix} w \\ b \end{bmatrix}dot \begin{bmatrix} x \\ 1 \end{bmatrix}$
损失函数(C的值为无穷大时，为硬间隔向量机，不允许有数据分类错误，否则成为软间隔向量机)：
$L(f) = C\sum_{n}\epsilon^n+\lambda||w||_2$

$\epsilon^n = max(0,1-\hat{y}^nf(x))$

由上式
$\epsilon^n \geq 0\\ \epsilon^n \geq1-\hat{y}^nf(x) \rightarrow\hat{y}^nf(x)\geq1-\epsilon^n$
优化方式：
$w \leftarrow w-\eta\sum_{n}c^n(w)x^n$
w初始化为0，解出的结果是w是x的线性组合， $c^n(w)$ 是f对loss function的偏微分
$w = \sum_{n}\alpha_nx^n = X\mathbf{\alpha}$
w是nx1维， $w^T$ 是1xn维，x是nx1，X是n*N，所以
$f(x) = w^T*x \rightarrow f(x) = \alpha^TX^Tx \rightarrow \sum_{n}\alpha_n(x^n\;dot\;x)$
$(x^n\;dot\;x)$ 可以记为 $K(x^n,x)$
重写损失函数：
$L(f) = \sum_{n}l(f(x^n),\hat{y}^n) = \sum_{n}l(\sum_{n'}\alpha_{n'}K(x^{n'},x^n),\hat{y}^n)$
利用拉格朗日乘子法证明w是x的线性组合的合理性：

对硬间隔向量机的损失函数进行转换：
$L(w,b,\alpha) = \frac{1}{2}||w||^2+\sum_{i=1}^{m}\alpha_i(1-y_i(w^Tx_i+b))$

$w = \sum_{i=1}^{m}\alpha_iy_ix_i \\ 0=\sum_{i=1}^{m}\alpha_iy_i$

核函数Tips
1. 核函数其实就是用来描述相似度的（向量的点积）
2. 通过mercer's 定理来检测所定核函数能否拆分成点积
3. kernel(x1,x2)函数代表x1、x2先做特征转换之后再做内积的结果，特征转换代表的是将低维提升到高维的转换

5. 集束搜索

集束搜索(beam search)：

集束搜索可以认为是维特比算法的贪心形式，在维特比所有中由于利用动态规划导致当字典较大时效率低，而集束搜索使用beam size参数来限制在每一步保留下来的可能性词的数量。集束搜索是在测试阶段为了获得更好准确性而采取的一种策略，在训练阶段无需使用。

假设字典为[a,b,c]，beam size选择2，则如下图有：

1：在生成第1个词的时候，选择概率最大的2个词，那么当前序列就是a或b

2：生成第2个词的时候，我们将当前序列a或b，分别与字典中的所有词进行组合，得到新的6个序列aa ab ac ba bb bc,然后从其中选择2个概率最高的，作为当前序列，即ab或bb

3：不断重复这个过程，直到遇到结束符为止。最终输出2个概率最高的序列。

6.条件随机场链接

$f_j$ 为特征函数， $\lambda_j$ 为特征函数的权重。给定一个句子s，则可以通过以下公式计算得到给定l下s的评分。
$socre(l\mid s)= \sum_{j=1}^m\sum_{i=1}^n\lambda_jf_j(s,i,l_i,l_{i-1})$
然后通过softmax可以将上述离散值转换成概率形式：
$p(l\mid s)= \frac{exp[score(l\mid s)]}{\sum_{l'}exp[score(l'\mid s)]}$

和马尔可夫模型对比

马尔可夫模型公式：
$p(l,s)=p(l_1)\prod_{i}p(l_i\mid l_{i-1})p(w_i\mid l_i)$
CRF模型更加强大，它可以建立包含HMM的所有模型

7.机器学习算法分类总结

其中一些学习的类别其实是很多种学习算法的总结，比如监督学习，其他则是表述一些你可以在项目中使用的有力的技术，比如"迁移学习"

总共有14种学习方法，根据分类的不同标准可以划分为：

1.监督学习方法

主要描述一类问题，即建立从输入实例到输入的目标值的映射。

2.无监督学习方法

主要描述一类问题，即使用一个模型来描述或者提取数据中的关系。

聚类：学习数据的集群
密度估计：总结数据的分布，核密度估计：使用小规模的紧密联系的数据集群去估测问题空间中新的点的分布情况。

当我们需要学习数据中蕴含的模式时，聚类和密度估计是不错的选择。

3.强化学习

学习要做什么：agent要学习如何将当前的场景映射到动作中，以此来最大化一个数值的奖励信息。

4.半监督学习（semi-supervised Learning）

半监督学习是当训练数据只有一小部分是有标签数据，更多的是无标签数据时的监督学习。

要想有效地使用未标注数据，我们需要从无监督学习方法中获得灵感，例如聚类和密度估计。

5.自监督学习

自监督学习是一种无监督学习，他被构造为监督学习问题的框架，从而使用有监督学习算法来解决。

自编码器就是一种自监督学习算法，训练过程是将模型的输入放到输入和输出两个地方，要求模型先将输入编码为一个压缩的表示，然后重新构造出输入。训练好之后，扔掉解码器，然后编码器被用于为输入编码。

尽管自编码器训练时是一种监督学习方法，但是它解决了一个无监督学习问题，即一个投影方法，将输入降维或者学习一些特征。

GAN是自监督学习的另一个例子。

6.多事例学习

7.Inductive Learning

8.Deductive Learning

9.Transduction Learning

image

10.多任务学习

多任务学习是一种有监督的学习，涉及在一个数据集上拟合模型以解决多个相关问题。

一个例子是词向量在一个任务中被训练出来，然后可以用于不同的自然语言处理任务。

11.Active Learning积极学习

是一种监督学习，学习算法可以选择从哪些数据中学习，一个积极的学习算法可以向oracle提出查询。积极学习通常被用于当标签的获取开销很大时，比如计算生物学的应用。

12.在线学习

当数据被不断提供，而且数据的分布不断变化时，适用于在线学习。

在线学习就是在预测被提出之前直接基于现有的数据更新数据。

13.迁移学习

14.集成学习

8.PCA和SVD

pca

svd

Micro和Macro测度的区别

[图片上传失败...(image-f30fbf-1578886312596)]

9.Perceptron

算法描述：

是一种机器学习算法，目标是二分类任务的无监督学习。是一种线性分类器，