Logistic回归模型
二项Logistic回归模型（binomial logistic regression model）是一种分类模型，由条件概率分布$$P(Y|X)$$表示，形式为参数化的logistic分布。
一、模型定义
模型是如下的条件概率分布：
$$ P(Y=1|X)=\dfrac{e{w\cdot x+b}}{1+e{w\cdot x+b}} $$
$$ P(Y=0|X)=1-P(Y=1|X)=\dfrac{1}{1+e^{w\cdot x+b}} $$
这里$$x\in Rn$$，$$Y\in {0, 1}$$，$$w \in Rn$$和$$b\in R$$是参数，$$w$$称为权值，$$b$$称为偏置。
给定输入实例$$x$$计算得到$$P(Y=1|x)$$和$$P(Y=0|x)$$，然后比较两个条件概率的大小，将实例$$x$$分到概率值较大的那一类。
为了方便，将权值向量和输入向量加以扩展，即令$$w_0=b$$，$$x_0=1$$，扩展为
$$ w=(w_0,w_1, w_2, ..., w_n)^T $$
$$ x=(x_0, x_1, x_2, ..., x_n)^T $$
这样，上面的模型变成：
$$ P(Y=1|X)=\dfrac{e{w\cdot x}}{1+e{w\cdot x}} $$
$$ P(Y=0|X)=1-P(Y=1|X)=\dfrac{1}{1+e^{w\cdot x}} $$
二、发生比
在统计和概率理论中，一个事件或者一个陈述的发生比（英语：Odds）是该事件发生和不发生的比率，公式为：
$$ odds(p)=\dfrac{p}{1-p} $$
其中$$p$$是该事件发生的概率，$$odds(p)$$是关于$$p$$的递增函数。
例如，如果一个人随机选择一星期7天中的一天，选择星期日的发生比是： $$\dfrac{1/7}{1-1/7}=1/6$$。不选择星期日的发生比是 $$6/1$$。
对odds取对数(成为log of odds)，也就是$$log\dfrac{p}{1-p}$$，称为对数几率，这个在正式的数学文献中会记为$$logit(p)$$，即：
$$ logit(p)=log\dfrac{p}{1-p} $$
该函数还是关于$$p$$的递增函数。
在Logistic回归中，对于某个实例$$x$$：
$$ log\dfrac{p}{1-p}=log\dfrac{P(Y=1|x)}{1-P(Y=1|x)}=w\cdot x $$
也就是实例$$x $$输出$$Y=1$$的对数几率是$$x $$的线性函数。
三、极大似然估计
给定训练数据集$$T={(x{(1)},y{(1)}),(x{(2)},y{(2)}),...,(x{(m)},y{(m)})}$$，其中，$$x{(i)}=(1, x_1, x_2, ..., x_n)T\in X= R{n+1}$$，$$y{(i)}\in Y={0, 1}$$，应用极大似然估计发估计模型参数，从而得到Logistic回归模型。
设：$$P(Y=1|x)=\pi(x)=\dfrac{e{w\cdot x}}{1+e{w\cdot x}}$$，$$P(Y=0|x)=1-\pi(x)=\dfrac{1}{1+e^{w\cdot x}}$$
则似然函数为：
$$ \displaystyle\prod_{i=1}m[\pi(x^{(i)})]{y{(i)}}[1-\pi(x^{(i)})]{1-y^{(i)}} $$
对数似然函数为：
$$ L(w)=\displaystyle\sum_{i=1}^m[y{(i)}ln\pi(x{(i)})+(1-y{(i)})ln(1-\pi(x{(i)}))] $$
$$ =\displaystyle\sum_{i=1}^m[y{(i)}ln\dfrac{\pi(x{(i)})}{1-\pi(x{(i)})}+ln(1-\pi(x{(i)}))] $$
$$ =\displaystyle\sum_{i=1}^m[y{(i)}(w\cdot x{(i)})-ln(1+e{w\cdot x{(i)}})] $$
该函数是高阶可导函数，对$$L(w)$$求极大值，即令每个样本的概率越大越好，得到$$w$$的估计值。
变换成求极小值：
$$ \min_{w} L(w)=-\displaystyle\sum_{i=1}^m[y{(i)}(w\cdot x{(i)})-ln(1+e{w\cdot x{(i)}})] $$
这样问题就变成了以对数似然函数为目标函数的最小值优化问题，Logistic回归学习中通常采用的方法是梯度下降和拟牛顿法。
计算梯度：
$$ \dfrac{\partial L(w)}{\partial w_j}=-\dfrac{\partial \displaystyle\sum_{i=1}^m[y{(i)}(w\cdot x{(i)})-ln(1+e{w\cdot x{(i)}})]}{\partial w_j} $$
$$ = \displaystyle-\sum_{i=1}m(y{(i)}x{(i)}j)+\displaystyle\sum{i=1}m\dfrac{\partial ln(1+e{w\cdot x{(i)}})}{\partial w_j} $$
$$ = \displaystyle-\sum_{i=1}m(y{(i)}x{(i)}j)+\displaystyle\sum{i=1}m\dfrac{1}{1+e{w\cdot x{(i)}}}\dfrac{\partial e{w\cdot x{(i)}}}{\partial w_j} $$
$$ = \displaystyle-\sum_{i=1}my{(i)}x{(i)}j+\displaystyle\sum{i=1}m\dfrac{e{w\cdot x{(i)}}}{1+e{w\cdot x{(i)}}}x^{(i)}_j $$
$$ = \displaystyle\sum_{i=1}m\big(\dfrac{e{w\cdot x{(i)}}}{1+e{w\cdot x{(i)}}}-y{(i)}\big)x^{(i)}_j $$
$$ = \displaystyle\sum_{i=1}m\big(\theta(w\cdot x{(i)})-y{(i)}\big)x{(i)}_j $$
其中$$\theta(x)=\dfrac{e{x}}{1+e{x}}=\dfrac{1}{1+e^{-x}}$$，也称为$$sigmoid$$函数，然后得到：
$$ \nabla L(w)= \displaystyle\sum_{i=1}m\big(\theta(w\cdot x{(i)})-y{(i)}\big)x{(i)} $$
假定：
$$X= \begin{bmatrix} (x{(1)})T \ (x{(2)})T \ (x{(3)})T \ ... \ ( x{(m)} )T \end{bmatrix} = \begin{bmatrix} 1 & x{(1)}_1 & x{(1)}_2 & ... & x{(1)}_n \ 1 & x{(2)}_1 & x{(2)}_2 & ... & x{(2)}_n \ 1 & x{(3)}_1 & x{(3)}_2 & ... & x{(3)}_n \ ... \ 1 & x{(m)}_1 & x{(m)}_2 & ... & x{(m)}_n \end{bmatrix}$$，$$Y=\begin{bmatrix} y{(1)} \ y{(2)} \ y{(3)} \ ... \ y{(m)} \end{bmatrix}$$，$$w=\begin{bmatrix} w_0 \ w_1 \ w_2 \ ... \ w_n \end{bmatrix}$$
则：
$$ X\cdot w= \begin{bmatrix} 1 & x{(1)}_1 & x{(1)}_2 & ... & x{(1)}_n \ 1 & x{(2)}_1 & x{(2)}_2 & ... & x{(2)}_n \ 1 & x{(3)}_1 & x{(3)}_2 & ... & x{(3)}_n \ ... \ 1 & x{(m)}_1 & x{(m)}_2 & ... & x{(m)}_n \end{bmatrix}\cdot \begin{bmatrix} w_0 \ w_1 \ w_2 \ ... \ w_n \end{bmatrix}=\begin{bmatrix} (x{(1)})T\cdot w \ (x{(2)})T\cdot w \ (x{(3)})T\cdot w \ ... \ (x{(m)})T\cdot w \end{bmatrix}=\begin{bmatrix} wT \cdot x{(1)} \ wT \cdot x{(2)} \ wT \cdot x{(3)} \ ... \ wT \cdot x{(m)} \end{bmatrix} $$
$$ \theta(X\cdot w)-Y=\begin{bmatrix} {\theta}(wT \cdot x{(1)})-y{(1)} \ {\theta}(wT \cdot x{(2)})-y{(2)} \ {\theta}(wT \cdot x{(3)})-y{(3)} \ ... \ {\theta}(wT \cdot x{(m)})-y{(m)} \end{bmatrix} $$
$$ XT= \begin{bmatrix} x{(1)} & x{(2)} & x{(3)} & ... & x^{(m)} \end{bmatrix} $$
$$ XT\cdot \big(\theta(X\cdot w)-Y\big) = \displaystyle\sum_{i=1}m\big(\theta(w\cdot x{(i)})-y{(i)}\big)x^{(i)} $$
最终得到：
$$ \nabla L(w)= X^T\cdot \big(\theta(X\cdot w)-Y\big) $$
同时也可以得到：
$$ L(w)=-\displaystyle\sum_{i=1}m[y{(i)}(w\cdot x{(i)})-ln(1+e{w\cdot x{(i)}})]=-(X\cdot w)T\cdot Y+ln(1+e^{X\cdot w })\cdot I $$
其中$$I$$为全$$1$$向量。
四、梯度下降法
1.批量梯度下降（Batch Gradient Descent）
输入：训练数据集$$T={(x{(1)},y{(1)}),(x{(2)},y{(2)}),...,(x{(m)},y{(m)})}$$，其中$$x{(i)}\in X= Rn$$，$$y^{(i)}\in Y=\lbrace0,1\rbrace$$，$$i=1,2,...,m$$，学习率$$\eta(0<\eta\leqslant1)$$；
输出：$$w$$，$$b$$，其中$$w=(w_1, w_2, ..., w_n)^T$$，模型$$P(y=1|x)=sigmoid ( w\cdot x+b)$$
**1）**将输入的每个$$x$$转换成$$x=(1, x_1, x_2,...x_n)$$，令$$w_0 =b$$，输出为$$w=(w_0, w_1, w_2, ..., w_n)^T$$
**2）**选取初始$$w{(0)}=(w_0, w_1, w_2, ..., w_n)T$$
**3）**计算梯度$$XT\cdot \big(\theta(X\cdot w{(j)})-Y\big)$$，其中$$w^{(j)}$$为第$$j$$次迭代的结果，则第$$j+1$$次为：
$$ w{(j+1)} \gets w{(j)} - \eta XT\cdot \big(\theta(X\cdot w{(j)})-Y\big) $$
**4）**转到步骤（3），一直到$$ L(w)$$满足一定条件，或者迭代到足够的次数。
在批量梯度下降算法中，每一步的迭代都需要计算所有样本，当样本数较大时，计算量会很大。
时间复杂度：
每次迭代更新$$X\cdot w{(j)}=Y{'}$$的计算次数为$$m\times n$$，$$\theta(Y{'})-Y = Z$$的计算次数为$$n$$次，$$XT \cdot Z$$的计算次数为$$m\times n$$，则每次迭代的时间复杂度为$$O(m\times n)$$，假定迭代次数为$$k$$次，则总时间复杂度为$$O(k\times m\times n)$$.
2.随机梯度下降（Stochastic Gradient Descent）
将上面的步骤（3）改为：
**3）**随机选取某个样本$$x^{(i)}$$，则：
$$ w{(j+1)} \gets w{(j)}-\eta \big(\theta(w{(j)}\cdot x{(i)})-y{(i)}\big)x{(i)} $$
一直到迭代到足够的次数。
时间复杂度：
每次迭代更新$$w{(j)}\cdot x{(i)}=y{'}$$的计算次数为$$n$$，$$\theta(y{'})-y{(i)}=z$$的计算次数为$$1$$，$$zx{(i)}$$的计算次数为$$n$$，则每次迭代的时间复杂度为$$O(n)$$，假设迭代次数为$$k$$，则总时间复杂度为$$O(k\times n)$$.
参考：
https://zh.wikipedia.org/wiki/发生比
http://vividfree.github.io/机器学习/2015/12/13/understanding-logistic-regression-using-odds
