机器学习基础概念

记录一些常见的机器学习基础概念。

常见的距离算法

欧几里得距离（Euclidean Distance）

[sqrt{sum_{i=1}^N{(x_i-y_i)}^2} ]

标准欧氏距离的思路：现将各个维度的数据进行标准化：标准化后的值 = ( 标准化前的值－分量的均值 ) /分量的标准差，然后计算欧式距离

马哈拉诺比斯距离（Mahalanobis Distance）
若协方差矩阵是对角矩阵，公式变成了标准化欧氏距离；如果去掉马氏距离中的协方差矩阵，就退化为欧氏距离。欧式距离就好比一个参照值，它表征的是当所有类别等概率出现的情况下，类别之间的距离；当类别先验概率并不相等时，马氏距离中引入的协方差参数（表征的是点的稀密程度）来平衡两个类别的概率。
曼哈顿距离（Manhattan Distance）

[sum_{k=1}^n{|x_{1k}-x_{2k}|} ]

海明距离（Hamming distance）
定义：在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。场景：在海量物品的相似度计算中可用simHash对物品压缩成字符串，然后使用海明距离计算物品间的距离

协方差与相关系数

协方差表示的是两个变量的总体的误差，范围负无穷到正无穷。

[cov(X,Y)=E[(X-μ_x)(Y-μ_y)] ]

它反映了两个变量远离均值的过程是同方向变化还是反方向变化，是正相关还是负相关。协方差数值越大，相关程度越高。如果两个变量的变化趋势一致，也就是说如果其中一个大于自身的期望值，另外一个也大于自身的期望值，那么两个变量之间的协方差就是正值。如果两个变量的变化趋势相反，即其中一个大于自身的期望值，另外一个却小于自身的期望值，那么两个变量之间的协方差就是负值。

相关系数用来度量两个变量间的线性关系。范围-1到+1。

[ρ=frac{cov{(X,Y)}}{σ_X σ_Y} ]

用X、Y的协方差除以X的标准差和Y的标准差。可以将相关系数看成一种特殊的协方差，是一种剔除了两个变量量纲影响、标准化后的特殊协方差，它消除了两个变量变化幅度的影响，而只是单纯反应变量间变化的相似程度。
（即，标准化后的两个数据的相关系数等于其协方差）

卡方检验

用在某个变量(或特征)值是不是和应变量有显著关系。
根本思想在于比较理论频数和实际频数的吻合程度或者拟合优度问题。

[chi^2=sumfrac{(A-T)^2}{T} ]

其中:A是实际值，T为理论值
我们需要查询卡方分布的临界值表，将计算的值与临界值比较。
查询临界值就需要知道自由度
自由度V=（行数-1）*（列数-1）；对四格表，自由度V = 1
当P小于等于0.05（置信度95%），认为变量不相关
若各理论数与相应实际数相差越小，卡方值越小；如两者相同，则卡方值必为零。

熵总结

自信息又称信息量。信息量的度量就等于不确定性的多少。
对于已发生的事件(i)，其所提供的信息量为：

[I(p_i)=-log(p_i) ]

信息熵

信息熵代表一个分布的信息量,或者编码的平均长度。
信息熵用来度量一个事件可能具有多个状态下的信息量，也可以认为是信息量关于事件概率分布的期望值：

[H(X)=-sum_{i=1}^n p(x_i)log{p(x_i)} ]

随机变量的取值个数越多，状态数也就越多，信息熵就越大，混乱程度就越大。当随机分布为均匀分布时，熵最大。
将一维随机变量分布推广到多维随机变量分布，则其 联合熵 (Joint entropy) 为：

[H(X,Y)=-sum_{i=1}^nsum_{j=1}^m{p(x_i,y_j)log{p(x_i,y_j)}} ]

条件熵

条件熵 (H(Y|X))表示在已知随机变量(X)的条件下随机变量(Y)的不确定性。条件熵 (H(Y|X))定义为X给定条件下(Y)的条件概率分布的熵对X的数学期望：

[H(Y|X)=sum_xp(x)H(Y|X=x)=-sum_{x,y}p(x,y)log⁡{p(y|x)} ]

条件熵(H(Y|X))相当于联合熵减去单独的熵(H(X))。

相对熵 (Relative entropy)

也称 KL散度 (Kullback–Leibler divergence) 。相对熵可以用来衡量两个概率分布之间的差异。
设 p(x)、q(x) 是离散随机变量 X 中取值的两个概率分布，则 p 对q的相对熵是：

[D_{KL}(p||q)=sum_x p(x) log{⁡frac{p(x)}{q(x)}} ]

性质：

如果 p(x)和 q(x)两个分布相同，那么相对熵等于0
相对熵具有不对称性
≥0 (利用Jensen不等式)

交叉熵 (Cross entropy)

交叉熵可以来衡量在给定的真实分布下，使用非真实分布所指定的策略消除系统的不确定性所需要付出的努力的大小。
交叉熵本质上可以看成,用一个猜测的分布的编码方式去编码其真实的分布,得到的平均编码长度或者信息量。

[H(p,q)=sum_x p(x) log{⁡frac{1}{q(x)}}=-sum_x p(x) log{⁡{q(x)}} ]

所以有：

[D_{KL}(p||q)=H(p,q)-H(p) ]

当用非真实分布q(x)得到的平均码长比真实分布p(x)得到的平均码长多出的比特数就是相对熵。
当H(p)为常量时（在机器学习中，训练数据分布是固定的），最小化相对熵等价于最小化交叉熵；H(p,q)也等价于最大化似然估计.

交叉熵是指用分布q来表示本来分布p的平均编码长度。可以用来计算学习模型分布与训练分布之间的差异。

Note:
在机器学习中，我们需要评估label和predicts之间的差距，使用KL散度刚刚好，即(DKL(y||hat{y}))，由于KL散度中的一部分(−H(y))不变，故在优化过程中，只需要关注交叉熵就可以了。 所以一般在机器学习中直接用用交叉熵做loss，评估模型。

互信息（信息增益）

互信息就是一个联合分布中的两个信息的纠缠程度/或者叫相互影响那部分的信息量.其衡量的是两个随机变量之间的相关性，即一个随机变量中包含的关于另一个随机变量的信息量。

[I(X,Y)=H(X)+H(Y)-H(X,Y) \ I(X,Y)=H(Y)-H(Y|X) ]

决策树中的信息增益就是互信息，决策树是采用的上面第二种计算方法，即把分类的不同结果看成不同随机事件Y，然后把当前选择的特征看成X，则信息增益就是当前Y的信息熵减去已知X情况下的信息熵。

置信区间

置信区间不能用贝叶斯学派的概率来描述，它属于频率学派的范畴。真值要么在，要么不在。由于在频率学派当中，真值是一个常数，而非随机变量（后者是贝叶斯学派），所以我们不对真值做概率描述。比如，95%置信区间，并不是真值在这个区间内的概率是95%，而应该为100次随机抽样中构造的100个区间如果95次包含了参数真值，那么置信度为95%。

最大似然估计、最大后验估计与贝叶斯估计

贝叶斯公式可如下表示：

[p( heta|X) = frac{p(X| heta) p( heta)}{p(X)} ]

其中：
(p( heta|X)) : 后验概率(posterior),通过样本X得到参数( heta)的概率
(p(X| heta)) : 似然函数(likehood),通过参数( heta)得到样本X的概率，通常就是我们的数据集的表现。
(p( heta)) : 参数( heta)的先验概率(prior)，一般是根据人的先验知识来得出的。比如人们倾向于认为抛硬币实验会符合先验分布：beta分布。当我们选择beta分布的参数(alpha=eta=0.5)时，代表人们认为抛硬币得到正反面的概率都是0.5。

最大似然估计（MLE）

　最大似然估计的核心思想是：认为当前发生的事件是概率最大的事件。因此就可以给定的数据集，使得该数据集发生的概率最大来求得模型中的参数。

[p(X| heta) = prod p(x_i| heta) ]

最大似然估计只关注当前的样本，也就是只关注当前发生的事情，不考虑事情的先验情况。由于计算简单，而且不需要关注先验知识，因此在机器学习中的应用非常广，最常见的就是逻辑回归。

最大后验估计（MAP）

和最大似然估计不同的是，最大后验估计中引入了先验概率 。最大似然估计是求参数(θ), 使似然函数(P(x_i|θ))最大。最大后验概率估计则是想求(θ)使(P(x_i|θ)P(θ))最大。求得的(θ)不单单让似然函数大，(θ)自己出现的先验概率也得大。

最大后验估计和最大似然估计的区别：最大后验估计允许我们把先验知识加入到估计模型中，这在样本很少的时候是很有用的（因此朴素贝叶斯在较少的样本下就能有很好的表现），因为样本很少的时候我们的观测结果很可能出现偏差，此时先验知识会把估计的结果“拉”向先验，实际的预估结果将会在先验结果的两侧形成一个顶峰。

贝叶斯估计

最大似然估计和贝叶斯估计都属于参数化估计。最大似然估计和贝叶斯估计最大区别便在于估计的参数不同，最大似然估计要估计的参数(θ)被当作是固定形式的一个未知变量，然后我们结合真实数据通过最大化似然函数来求解这个固定形式的未知变量！
贝叶斯估计则是将参数视为是有某种已知先验分布的随机变量，意思便是这个参数他不是一个固定的未知数，而是符合一定先验分布如：随机变量(θ)符合正态分布等！那么在贝叶斯估计中除了类条件概率密度(p(x|w))符合一定的先验分布，参数(θ)也符合一定的先验分布。我们通过贝叶斯规则将参数的先验分布转化成后验分布进行求解。
贝叶斯估计和极大后验估计有点相似，都是以最大化后验概率为目的。区别在于：极大后验估计在计算后验概率的时候，把分母(p(X))给忽略了，在进行贝叶斯估计的时候则不能忽略,并且贝叶斯估计要计算整个后验概率的概率分布。
贝叶斯估计的应用有LDA主题模型。LDA主题模型通过共轭分布的特性来求出主题分布和词分布。

梯度下降

梯度下降法是一种迭代算法。选取适当的初值，不断迭代，更新的值，进行目标函数的极小化，直到收敛。因为负梯度方向是使函数值下降最快的方向，在迭代的每一步，以负梯度方向更新的值，从而达到减少函数值的目的。由于具有一阶连续偏导数，若第k次迭代值为，则可将在附近进行一阶泰勒展开。

优点：
求解无约束优化问题简单
缺点：
靠近极小值时收敛速度减慢。
直线搜索时可能会产生一些问题。
可能会“之字形”地下降。

牛顿法

牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数(f(x))的泰勒级数的前面几项来寻找方程(f(x) = 0)的根。牛顿法最大的特点就在于它的收敛速度很快。
首先把函数(f(x))在点(x_k)处一阶泰勒展开有

[f(x)=f(x_k)+f^{'}(x_k)(x-x_k) ]

假设点(x_{k+1})为该方程的根，则有

[f(x_{k+1})=f(x_k)+f^{'}(x_k)(x_{k+1}-x_k)=0 ]

那么移项就可以得到

[x_{k+1}=x_k-frac{f(x_k)}{f'(x_k)} ]

这样我们就得到了一个递归方程，我们可以通过迭代的方式不断的让(x)趋近于(x^∗)，从而求得方程(f(x)=0)的解。

当无约束最优化问题是 (min_x f(x))时，可以得到迭代公式，(g)和(h)分别是目标在当前(x)上的一阶和二阶导:

[x_{k+1}=x_k-frac{g_k}{h_k} ]

推广到(x)是多维向量的情况，(g_k)仍然是向量，而(H_k)是Hesse矩阵

[H = [frac{partial^2 f}{partial x_i partial x_j}] ]

参数更新方程推广为：

[x_{k+1}=x_k- H_k^{-1} g_k ]

可见，每一次迭代的更新方向都是当前点的牛顿方向，步长固定为1。每一次都需要计算一阶导数(g)以及Hesse矩阵的逆矩阵，对于高维特征而言，求逆矩阵的计算量巨大且耗时。
关于牛顿法和梯度下降法的效率对比：
　　从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好。

优点：
二阶收敛，收敛速度快；
缺点：
牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。

阻尼牛顿法

从上面的推导中看出，牛顿方向 (−H^{−1}g) 能使得更新后函数处于极值点，但是它不一定是极小点，也就是说牛顿方向可能是下降方向，也可能是上升方向，以至于当初始点远离极小点时，牛顿法有可能不收敛。因此提出阻尼牛顿法，在牛顿法的基础上，每次迭代除了计算更新方向（牛顿方向），还要对最优步长做一维搜索。
算法步骤
（1）给定给初始点 (x(0))，允许误差 (ϵ)
（2）计算点 (x^{(t)}) 处梯度(g_t)和Hesse矩阵(H)，若(|g_t|<ϵ)则停止迭代
（3）计算点 (x^{(t)}) 处的牛顿方向作为搜索方向：

[d{(t)}=−H_t^{-1}g_t ]

（4）从点 (x^{(t)}) 出发，沿着牛顿方向 (d^{(t)}) 做一维搜索，获得最优步长：

[λ_t=argmin_λ f(x^{(t)}+λ⋅d^{(t)}) ]

（5）更新参数

[x^{(t+1)}=x^{(t)}+λ_t⋅d^{(t)} ]

拟牛顿法

牛顿法中的Hesse矩阵(H)在稠密时求逆计算量大，也有可能没有逆（Hesse矩阵非正定）。拟牛顿法提出，用不含二阶导数的矩阵 (U_t) 替代牛顿法中的 (H_t^{−1})，然后沿搜索方向 (−U_t g_t) 做一维搜索。根据不同的 (U_t) 构造方法有不同的拟牛顿法。

注意拟牛顿法的关键词：
不用算二阶导数
不用求逆

牛顿法的搜索方向是

[d^{(t)} = - H_t^{−1} g_t ]

为了不算二阶导及其逆矩阵，设法构造一个矩阵 (U)，用它来逼近 (H^{−1})
现在为了方便推导，假设 (f(x)) 是二次函数，于是 Hesse 矩阵 (H) 是常数阵，任意两点$ x^{(t)}$ 和 (x^{(t+1)}) 处的梯度之差是：

[▽f(x^{(t+1)})−▽f(x^{(t)})=H⋅(x^{(t+1)}−x^{(t)}) ]

等价于

[x^{(t+1)}−x^{(t)}= H^{−1}⋅[▽f(x^{(t+1)}−▽f(x^{(t)})] ]

那么对非二次型的情况，也仿照这种形式，要求近似矩阵 UU 满足类似的关系：

[x^{(t+1)}−x^{(t)}= U_{t+1}⋅[▽f(x^{(t+1)}−▽f(x^{(t)})] ]

或者写成

[Δx_t=U_{t+1}⋅Δg_t ]

以上就是拟牛顿条件，不同的拟牛顿法，区别就在于如何确定 (U)。常用的拟牛顿法有DFP算法和BFGS算法。
DFP算法
将U记为D，已知拟牛顿条件

[Δx_t=D_{t+1}⋅Δg_t ]

假设已知(D_t)，希望用叠加的方式求(D_{t+1})，即 (D_{t+1}=D_t+ΔD_t)，代入得到

[ΔD_t Δg_t=Δx_t−D_t Δg_t ]

假设满足这个等式的 (ΔD_t) 是这样的形式：

[ΔD_t=Δx_t⋅q_t^T−D_t Δg_t ⋅ w_t^T ]

首先，对照一下就能发现：

[q_t^T ⋅ Δg_t=w_t^T⋅Δg_t=I_n ]

其次，要保证 (ΔD_t) 是对称的，参照 (ΔD_t) 的表达式，最简单就是令

[q_t=α_t Δx_t \ w_t=β_t D_t Δg_t ]

第二个条件代入第一个得到：

[α_t=frac{1}{Δg_t^T Δx_t} \ β_t=frac{1}{Δg_t^T D_t Δg_t} ]

然后代入回(ΔD_t) 的表达式：

[ΔD_t=frac{Δx_t Δx_t^T} {Δg_t^T Δx_t} − frac{D_t Δg_t Δg_t^T D_t}{Δg_t^T D_t Δg_t} ]

观察一下两项分式，第一项仅涉及向量乘法，时间复杂度是(O(n))，第二项涉及矩阵乘法，时间复杂度是(O(n^2))，综合起来是(O(n^2))。

DFP算法步骤

（1）给定初始点 (x(0))，允许误差 (ϵ)，令 (D_0=I_n)（(n)是(x)的维数），(t=0)
（2）计算搜索方向 (d^{(t)}=−D_t^{−1}⋅g_t)
（3）从点 (x^{(t)}) 出发，沿着 (d^{(t)}) 做一维搜索，获得最优步长并更新参数：

[λ_t=argmin_λ f(x^{(t)}+λ⋅d^{(t)}) \ x^{(t+1)}=x^{(t)}+λ_t⋅d^{(t)} ]

（4）判断精度，若(|g_{t+1}|<ϵ)则停止迭代，否则转（5）
（5）计算(Δg=g_{t+1}−g_t)，(Δx=x^{(t+1)}−x^{(t)})，更新 (H)

[D_{t+1}=D_t+frac{Δx Δx^T}{Δg^T Δx}−frac{D_t Δg Δg^T D_t}{Δg^T D_t Δg} ]

（6）(t=t+1)，转（2）

共轭梯度法（Conjugate Gradient）

共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。