Logistic Regression笔记

Logistic function

Logistic function是指满足这样的函数关系的一条曲线

$$ y = \frac{1}{1+e^{-x}} , x \in R $$

函数图像

它又常被称为S型曲线。它有一个很好的特性是: \( y' = y(1-y) , max(y)=1 \)

因为y的最大值是1,所以我们可以把1-y称作y的不饱和度。所以,y的增长速度和y成正比,和y的不饱和度成反比。

举个例子,社会学上经常用Logistic function来估算人口增长。假设y是当前人口基数/环境所能容纳的上限。环境所能容纳的人数上限是固定值。显然人口基数越大,出生的孩子也就越多,人口增长也就越快。但是另一方面,人口越接近饱和,增长速度也就越慢。

Logistic Regression

Logistic Regression本质上来讲就是利用极大似然法进行参数估计。

Logistic Regression是假设某件事情发生的概率满足Logistic function的形式:

$$ P(x) = \frac{1}{1+e^{-w \cdot x}} \quad w,x \in R^n $$

其中x是特征向量(比如性别、年龄),在回归分析中被称为自变量。w是这些特征所对应的权重,是待估计参数。

Logistic Regression的核心是给出Loss函数以及Loss函数的一阶导数的计算方式。即:对每一行训练数据x,都能计算出一个L(x)和L'(x)。前者是一个标量(实数),后者是一个向量。然后把这两个东西交给SGD、BFGS或CG等最优化方向去求解。LR模型本身是极为简单的,难点在后面如何求最优化的部分。

Loss函数及其导数的推导过程

如果我们引入随机变量y。用y=1代表该事件发生,y=0代表该事件不发生,那么

$$ P(Y=y|x) = P(x)^y(1-P(x))^{1-y} = (\frac{1}{1+e^{-w \cdot x}})^y (1-\frac{1}{1+e^{-w \cdot x}})^{1-y} $$

如果用\(x_i,y_i\)代表训练集中的第i行数据,把那么这些样本的联合分布概率为

$$ \prod_{i=1}^{n}{P(Y=y_i|x_i)} = \prod_{i=1}{P_i^{y_i}(1-P_i)^{1-y_i}} $$

\(P_i\)是\(P(Y=y_i|x_i)\)的简写

我们的目标的是希望联合分布概率越大越好

对联合分布概率取对数后再取反,得到Loss函数为

$$ L(w) = -\sum_{i=1}^n{\ln{P_i^{y_i}(1-P_i)^{1-y_i}}} = \sum_{i=1}^n{(-y_i\ln{P_i}-(1-y_i)\ln{(1-P_i)})} $$

接下来就是根据样本求L(w)的最小值。这是一个无约束最优化问题。典型的解法有:最速下降法、拟牛顿法(如DFP、BFGS)、随机梯度下降等。 这些方法都需要对L(w)进行求导。所以下面把L(w)的导数也给出来:

$$ L'(w) = \sum_{i=1}^n{(P_i-y_i)x_i}$$

推导过程如下:

由于\(P_i\)是Logistic function的形式,所以它的导数很好求,\( P_i' = xP_i(1-P_i) \)

所以\(\ln{P_i}' = P_i'/P_i=xP_i(1-P_i)/P_i=x(1-P_i) \)

类似可得\(\ln{(1-P_i)}' = -P_i'/(1-P_i) =-xP_i(1-P_i)/(1-P_i)=-xP_i \)

所以 $$ L'(w) = \sum_{i=1}^n{(-y_i x_i(1-P_i)+(1-y_i)x_iP_i)} = \sum_{i=1}^n{(P_ix_i-y_ix_i)}$$

推导完毕。

L'(w)有个很好的特性是:如果x在某一列为0,则L'(w)在这一列也为0。于是它所对应的权重(weight)在迭代中不会变。直观的解释是:如果一个feature在训练集中从未出现过,那么最终它所对应的weight等于初始weight。后面会讲到,一旦加入L2正则化后,这个特性就没了。

y=1或-1的情况

有些地方假设y=1或-1,所以从P(Y=y|x)开始的公式就和上面的完全不一样。但其实只是公式长的不一样,计算的结果是一样的。更进一步,梯度也是。However,我还是把它们对比着列出来。(我试图做成一张表格,但是我在table中嵌不进去latex的公式)

y=1或0

对于每一行记录,有

$$ P(Y=y|x)= P^y (1-P)^{1-y} $$

$$L(w) =-y\ln{P}-(1-y)\ln{(1-P)}$$

$$L'(w) = (\frac{1}{1+e^{-w \cdot x}}-y)x$$

y=1或-1

对于每一行记录,有 $$ P(Y=y|x)= \frac{1}{1+e^{-yw \cdot x}} $$

$$ L(w) = \ln{(1+e^{-yw \cdot x})} $$

$$ L'(w) = (\frac{1}{1+e^{-yw \cdot x}} -1)* y * x $$

正则化

正则化又是一个比较大的topic了。改天单独开一篇写吧。对模型最大的影响就是Loss函数略微变了,变完之后有可能是非光滑的或丧失稀疏性。

带L1正则化的LR的目标函数为:

$$ \min \frac{1}{n}\sum^n_{i=1}{ \ln{(1+e^{-y_i w \cdot x_i})}} + \lambda \Vert w \Vert _1 $$

带L2正则化的LR的目标函数为: $$ \min \frac{1}{n}\sum^n_{i=1}{ \ln{(1+e^{-y_i w \cdot x_i})}} + \frac{\lambda}{2} \Vert w \Vert ^2 $$

对偶

一段用于计算对偶函数的代码

syms alpha u y  
f1 = symfun(log(1+exp(-y*u)), [u y])  
f2 = symfun(alpha*u - f1,[alpha u y])  
x = diff(f2,u)  
t = solve(x,u,'IgnoreAnalyticConstraints', true)  
simplify(f2(alpha,t,y))  

把f1的函数改成(u-y)*(u-y)得到的就是squared loss的对偶。

在“An Interior-Point Method for Large-Scale l1-Regularized Logistic Regression” by K. Koh, S.-J. Kim, and S. Boyd 中有对L1 LR的对偶函数的推导

首先把原问题转换成约束最优化问题,令\( z_i = w \cdot x_i \) ,则原问题可转换为

$$ \min {\frac{1}{n}\sum^n_{i=1}{ \ln{(1+e^{-y_i w \cdot x_i})}} + \lambda \Vert w \Vert _1 } $$ $$ s.t. z_i - w \cdot x_i =0 $$

于是它的Lagrange扩展函数为:

$$ L(w,z,θ) = \frac{1}{n}\sum^n_{i=1}{ \ln{(1+e^{-y_i w \cdot x_i})}} + \lambda \Vert w \Vert _1 + θ^T(Aw-z)$$

对偶函数为

$$ D(θ) = \inf_{w,z} L(w,z,θ) = \frac{1}{n}\inf_z \sum^n_{i=1}{ (\ln{(1+e^{-y_i w \cdot x_i})} - n θ_i z_i) } + \inf_w (\lambda \Vert w \Vert _1 + θ^T A w ) $$

当\( \Vert A^T θ \Vert _ ∞ \leq \lambda \) 时,\( D(θ) = \frac{1}{n} \sum^n_{i=1}H(nθ_i) \) 其中H(x)是Binary entropy function.

即L1 LR的对偶问题为:

$$ \max \frac{1}{n} \sum^n_{i=1}H(nθ_i) $$ $$ s.t. \Vert A^T θ \Vert _ ∞ \leq \lambda $$

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥