前几个月，由于要处理大批量数据，我专门重温了逻辑回归（Logistic Regression，LR）。虽然LR没有取得比较好的效果，我仍然觉得它的潜力巨大且应用前景广泛。作为广义线性分类器的一种，LR一直是实际应用中的“明星”。下面开始介绍LR原理和其实现过程。

LR原理

经典的线性回归分类器是
\[ y=\mathbf{w}^T \mathbf{x} + w_0 \]
对于数据集\( \{\mathbf{x}_i, t_i\}_{i=1}^N \)，其中类别\( t_i \in \{0, 1\} \)，那么LR分类器可以表示为
\[ y = f(\mathbf{x}) = g(\mathbf{w}^T\mathbf{x} + w_0) = \frac{1}{1 + \exp\{-(\mathbf{w}^T\mathbf{x} + w_0)\}} \]
其中\( g(\mathbf{z})=\frac{1}{1 + e^{-\mathbf{z}}} \)是sigmoid函数。则\( N \)对个样本，其似然函数（likelihood function）为
\[ L(\mathbf{w}) = \prod_{i=1}^N y_i^{t_i} (1 - y_i)^{1 - t_i} \]
其中\( y_i = f(\mathbf{x}_i) \)。那么我们得到的代价函数（cost function）为似然函数的负对数，再加上对系数的惩罚项，以避免过拟合
\[ J(\mathbf{w}) = -\frac{1}{N}\log L(\mathbf{w}) + \frac{\gamma}{2}\Vert\mathbf{w}\Vert^2 \]

\[ J(\mathbf{w}) = -\frac{1}{N}\sum_{i=1}^N \lbrack t_i \log f(\mathbf{x}_i) + (1 - t_i) \log (1 - f(\mathbf{x}_i)) \rbrack + \frac{\gamma}{2}\sum_{j=1}^k w_j^2 \]
上式\( k \)为样本\( \mathbf{x} \)的维度。

梯度下降法

当目标是最小化代价函数时，可采用梯度下降法（Gradient Descent algorithm）求取最优解。
（注：当目标是最小化目标函数（如代价函数）时，才可以采用梯度下降法；若目标是最大化目标函数（如似然函数）时，应采用梯度上升法。为了论述统一，推荐采用最小化的目标函数。）
对\( w_j \)求导数，得到代价函数的梯度（descent）为
\[ \frac{\partial J(\mathbf{w})}{\partial \mathbf{w}} = \frac{1}{N}\sum_{i=1}^N \lbrack f(\mathbf{x}_i) - y_i \rbrack \mathbf{x}_i + \gamma \mathbf{w}, \qquad j = 1,2,\dots,k \]

\[ \frac{\partial J(\mathbf{w})}{\partial w_0} = \frac{1}{N}\sum_{i=1}^N \lbrack f(\mathbf{x}_i) - y_i \rbrack \]
梯度下降法的迭代公式为
\[ \beta^{\prime} = \beta - \alpha\frac{\partial}{\partial \beta} J(\beta) \]
将\( \mathbf{w} \)的梯度代入，可以得到梯度下降法求解LR的迭代公式
\[ \mathbf{w}^{\prime} = \mathbf{w} - \alpha\left\lbrace \frac{1}{N}\sum_{i=1}^N \lbrack f(\mathbf{x}_i) - y_i \rbrack \mathbf{x}_i + \gamma\mathbf{w} \right\rbrace, \qquad j=1,2,\dots,k \]

\[ w_0^{\prime} = w_0 - \alpha\frac{1}{N}\sum_{i=1}^N \lbrack f(\mathbf{x}_i) - y_i \rbrack \]
根据上述迭代公式，可以求得LR分类器的参数。

关于迭代公式向量化的过程，请参考洞庭之子-Bing的博客（从编写代码的角度来说，我觉得向量化很没必要；当然对于数学Geek，向量化表示的确要漂亮很多）。
除去不太主流的梯度下降法，求解LR分类器的方法包括随机梯度下降法（Stochastic Gradient Descent）、拟牛顿法（包括DFP、BFGS算法 ）等。BFGS算法是当前使用最广泛的最优化求解方法，其原理和实现过程比较复杂。我自己曾试图实现BFGS算法，最终没能成功。直到现在，我还是不明白如何寻找最合适的步长。

数据归一化

在实际应用中，LR通常采用一种特别的数据预处理方式——数据归一化（data normalization）。这个技巧是Weka中LR模型所采用的，在做主成分分析（PCA，Primary Component Analysis）时经常用到。我利用几个基准数据集进行测试，发现这个技巧能极大地降低代价函数，且能更快达到终止条件（如\( \vert J(\mathbf{w}^{\prime}) - J(\mathbf{w}) \vert \leq \epsilon \)）。

对于\( k \)维空间的样本数据\( \lbrace \mathbf{x}_i, t_i \rbrace_{i=1}^N \)，对每一维特征进行归一化，得到新的样本数据\( \lbrace\mathbf{z}_i, t_i \rbrace_{i=1}^N \)。归一化方式为
\[ z^j = \frac{x^j - \bar{x}^j}{\sigma^j}, \qquad j = 1,2,\dots,k \]
其中\( z^j \)是样本\( \mathbf{z} \)的第\( j \)维特征的值， \( \bar{x}^j \)是所有样本\( \lbrace\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_N \rbrace \)的第\( j \)维特征的均值，\( \sigma^j \)是其标准差。
\[ \bar{x}^j = \frac{1}{N}\sum_{i=1}^N x_i^j \]
\[ \sigma^j = \sqrt{\frac{1}{N-1}\sum_{i=1}^N (x_i^j - \bar{x}^j)^2} \]
若\( \sigma^j = 0 \)，则所有样本第\( j \)维特征的元素相同，第\( j \)维特征对样本分类没有贡献，不用归一化，其系数为零（选择\( \mathbf{w} \)和\( w_0 \)的初始值全为零）。
对样本集\( \lbrace\mathbf{z}_i, t_i \rbrace_{i=1}^N \)，学习LR分类器，假设分类器为
\[ y = f(\mathbf{z}) = g(\mathbf{\theta}^T\mathbf{z} + \theta_0) = \frac{1}{1 + \exp\lbrace -(\mathbf{\theta}^T\mathbf{z} + \theta_0)\rbrace} \]
将上面的\( \mathbf{z} \)与\( \mathbf{x} \)的关系式\( z^j = \frac{x^j - \bar{x}^j}{\sigma^j} \)代入，得到
\[ y = f(\mathbf{x}) = \frac{1}{\displaystyle 1 + \exp\left\lbrace -\left( \sum_{j=1}^k \frac{\theta_j}{\sigma^j} x^j + \theta_0 - \sum_{j=1}^k \frac{\theta_j}{\sigma^j} \bar{x}^j \right) \right\rbrace} \]
那么，可以得到原始样本集的LR分类器系数
\[ w_j = \frac{\theta_j}{\sigma^j}, \qquad j = 1,2,\dots,k \]
\[ w_0 = \theta_0 - \sum_{j=1}^k w_j \bar{x}^j \]

在训练LR分类器时，数据归一化技术有一些特殊的优势。

• 归一化后，样本每一维特征的值基本满足标准正态分布\( N(0, 1) \)，在学习LR分类参数时方便处理。
• 提高标准差较大维度的分类系数的准确度。若\( \sigma^j \)很大，则\( w_j \)较小；（不经过数据归一化）直接求取\( w_j \)时，\( w_j \)的变化受迭代步长\( \alpha \)制约。
• 归一化后，每一维特征的梯度比原始的梯度小很多（梯度下降法迭代步骤中，\( z^j \)的幅值比\( x^j \)的幅值小很多），系数的更新幅度变小，更容易找到精确解。
• 归一化后，系数的初始值全设为零，相对合理；在原始情况下，初始值的选取通常没有统一的准则。

关于LR分类器的总结至此结束，我希望能够与各位同仁探讨交流。