总阅读量次

对率回归原理及其编程实现

原理

用线性模型解决分类问题，只需找一个单调可微函数将分类任务的标记y与线性回归模型的预测值联系起来。而对数几率函数正是这样的一个常用替代函数：

$$y = \frac{1}{1+e^{-z}}$$

令$z = \vec{\omega}^T\vec{x}+b$，则可得到：

$$ln\frac{y}{1-y} = \vec{\omega}^T\vec{x} + b$$

令 $p(y = 1 | \vec{x}) = y$，则$p(y=0|\vec{x}) = 1-p(y = 1 | \vec{x})$，这里假定为二分类任务，则有：

$$p(y = 1 | \vec{x}) = \frac{e^{\vec{\omega}^T\vec{x}+b}}{1+e^{\vec{\omega}^T\vec{x}+b}}$$ $$p(y = 0 | \vec{x}) = \frac{1}{1+e^{\vec{\omega}^T\vec{x}+b}}$$

运用“极大似然法”，则对率回归模型最大似然函数如下：

$$\ell(\vec{\omega},b) = \sum_{i=1}^{m}{lnp(y_{i}|\vec{x}_{i};\vec{\omega},b)}$$

令$\beta = ({\vec{w};b})$，令$\dot{x} = (\vec{x};1)$，则$\vec{\omega}^T\vec{x}+b = \beta^T\dot{x}$。再令$p_{1}(\dot{x};\beta) = p(y=1|\dot{x};\beta)$，则$p_{0}(\dot{x};\beta)=p(y=0|\dot{x};\beta)=1-p_{1}(\dot{x};\beta)$，则上式为：

$$p(\vec{y}_i|\vec{x}_i,\vec{\omega},b)=y_{i}p_{1}(\vec{x}_i;\beta) + (1-y_i)(p_{0}(\vec{x}_i;\beta))$$

最大化上式等价于最小化下式，

$$\ell(\beta) = \sum_{i=1}^{m}{(-y_i\beta^T\dot{x}_i+ln(1+e^{\beta^T\dot{x}_i}))}$$

上式是关于$\beta$的高阶可导连续凸函数，根据凸优化理论，可用梯度下降法和牛顿法求得其最优解。
这里给出第$t+1$代牛顿迭代法公式：

$$\beta^{t+1} = \beta^t - (\frac{\partial^2\ell{(\beta)}}{\partial\beta \partial\beta^T})^{-1}\frac{\partial\ell{(\beta)}}{\partial\beta}$$

其中$\ell(\beta)$的一阶，二阶导如下：

$$\frac{\partial\ell{(\beta)}}{\partial\beta} = -\sum_{i=1}^{m}{\dot{x}_i(y_i-p_1(\dot{x}_i;\beta))}$$ $$\frac{\partial^2\ell{(\beta)}}{\partial\beta \partial\beta^T} = \sum_{i=1}^{m}\dot{x}_i\dot{x}_i^Tp_1(\dot{x}_i;\beta)(1-p_1(\dot{x}_i;\beta))$$

代码所用算法与数据结构分析

因为目标函数是凸函数，所以可以直接将数据代入目标函数，用经典最优化算法进行求解。

Python语言实现

可以将格式化后的数据集存入文件（数据集较小），每次运行读取数据放入内存进行迭代最优化求解即可。代码库见我的码云
雨落纷飞