跳转至

1. logistic回归&最大熵模型#

引子: 经典回归分析中目标Y一般是服从正态分布的连续变量，取值范围可以是(-∞, + ∞) ，那么能否利用回归的方式来解决二分类问题呢？

logistic分布#

分布函数如下

分布函数特点：

  • 分布函数以(u, ½)为中心对称，在中心附近增长速度较快，在两端增长速度较慢。
  • 也称为sigmoid函数

logistic回归模型#

利用sigmoid函数进行映射，将传统的回归(-∞, + ∞) 数值映射到 (0, 1)。或者反过来说，是通过回归方式直接对odds进行建模

  • 二分类

二项logistic回归模型是如下的条件概率分布，其中Y={0,1}

P(Y=1|x) = \frac{e^{wx+b}}{1+e^{wx+b}}
P(Y=0|x) = \frac{1}{1+e^{wx+b}}

模型的物理意义：

事件的几率odds#

一个事件发生的概率与不发生的概率的比值

\frac{p}{1-p}

对数几率#

log(odds) = log\frac{p}{1-p}=wx+b
  • 多分类

多分类的逻辑回归是二分类的推广形式，假设离散型随机变量Y的取值范围是{1,2, ..., K}， 则多项logstic回归模型的形式是

模型参数估计#

极大似然估计

以常用的二分类为例， 我们假设P(Y=1|x)=\pi(x), P(Y=0|x)=1-\pi(x), 则

对应的似然函数是: \prod \pi(x_i)^{y_i}(1-\pi(x_i))^{1-y_i}

对数似然函数为： L(w) =\sum y_i log \pi(x_i) + (1-y_i)log(1-\pi(x_i))

通过对L(w)求极大值，得到w的估计值。

似然函数：是统计模型中参数的函数，表示的是给定参数后样本取值的概率

2 最大熵模型#

最大熵原理#

最大熵原理是**概率模型**学习的一个准则。学习概率模型时，在所有可能的概率模型分布中，熵最大的模型是最好的模型。

通常用约束条件来确定概率模型的候选集合，因此最大熵原理也可以表述为：在满足约束条件的模型集合中选取熵最大的模型。

H(p) = -\sum_{i=1}^{n}p_i\log{p_i} \\ 0 \le H(p) \le \log{n}\\

熵的上界是log(n), 并且仅当pi全部相等即X服从均匀分布的时候熵最大

=> 体现了一种思想，不要把鸡蛋都放在同一个篮子里。在我们对分布本身的信息不足的时候，最安全的选择就是保留各种可能性。

例如: 假设随机变量X有5个取值{A, B, C,D,E}, 并且已知P(A) + P(B) = 3/10, P(A) + P(B) + P(C) + P(D) + P(E) = 1，求X取各个值的概率？

Answer：满足已经信息条件的概率部分有无穷多个。如果没有任何其他信息，仍要对概率分布进行估计，一个办法就行认为在限制条件下各个分布取值是一样的。即 P(A) = P(B) = 3/20, P(C) = P(D) =P(E) = 7/30

条件熵

H(Y|X) = -\sum p(x_i)H(Y|X=x_i)=-\sum_{x,y}p(x)P(y|x)logP(y|x)

最大熵模型#

将最大熵原理应用在分类问题中得到的模型就是最大熵模型。

例如：一般的一个分类模型可以表述成P(Y|X), 给定一个训练数据集合T=\{(x_1, y_1), (x_2, y_2)...(x_N, y_N)\},学习的目标是用最大熵原理选择最好的分类模型

最大熵模型求解：

min_{P \in C} -H(Y|X) = \sum_{x,y}p(x)P(y|x)logP(y|x)
st. E_P(f_i) - E_{\hat P}(f_i) =0, i =1,2,...n \\ \sum_y P(y|x) = 1

通过拉格朗日乘子将限制条件转为优化目标： min_{P \in C}Max_w L(P, w) \\ L(P, w)= -H(Y|X) + w_0(1-\sum P(y|x)) +w_1\sum (E_P(f_i) - E_{\hat P}(f_i))

等价的对偶问题是

Max_w min_{P \in C}L(P, w)

step1： $$min_{P \in C}L(P, w) $$最终求解得到

step2: 求解对偶问题外部的极大化问题

=> 可以证明：对偶函数的极大化等价于最大熵模型的极大似然估计

3.模型学习的最优化算法#

logstic回归模型、最大熵模型最终都可以归结为以似然函数为目标函数的最优化问题，通常通过迭代算法求解。

改进的迭代尺度法IIS

IIS是一种最大熵模型学习的最优化算法。对极大似然函数求最值。

基本想法：假设最大熵模型当前的参数向量是w=(w_1, w_2,...w_n)T，希望找到一个新的参数向量w+\delta使得模型的对数似然函数值增大，然后一直沿用这种参数更新的方法，直至找到对数似然函数的最大值。

当模型参数改变时，对数似然函数的改变量是:

L(w+\delta) -L(w) \ge B(\delta | w)

其中B(\delta|w)是改变量的下界，寻找适当的\delta使得下界提高，那么似然函数也会提高。

梯度下降法-一阶

假设f(x) 具有一阶连续偏导数的函数

目标函数 min_{x\in R^n} f(x)

泰勒展开f(x) ≈ f(x_k) + ▽f(x_k)(x-x_k)

沿着负梯度方向进行迭代

x' = x_k- \eta▽f(x_k)

牛顿法-二阶

泰勒展开到二阶 f(x) ≈ f(x_0) + ▽f(x_0)(x-x_0)+\frac{1}{2}(x-x_k)^T H(x_k)(x-x_k)

拟牛顿法

在牛顿法中需要计算黑塞矩阵H的逆矩阵，拟牛顿法主要是对该逆矩阵的计算进行优化。即考虑用一个n阶矩阵来近似替代H的逆矩阵。

  • BFGS

不支持在 Docs 外粘贴 block

参考资料

机器学习中的最优化算法总结