线性分类模型

回归用于分类

线性分类器、线性回归和logistic回归，都采用了同样的线性评分函数 \[ s=\mathbf w^T\mathbf x \] 它们之间的对比如下：

最小化线性分类器的$E_{in}(\mathbf w)$更困难，它是NP-Hard，能否用回归方法解决分类问题？✅

线性分类器、线性回归和logistic回归，它们的误差函数分别可记为 \[ \mbox{err}_{0/1}(s,y)=[[\mbox{sign}(ys)\neq 1]];\quad \mbox{err}_{SQR}(s,y)=(ys-1)^2;\quad \mbox{err}_{CE}(s,y)=\ln(1+\exp(-ys))。 \]

图 1: 误差曲线对比 [PNG]

上图展示了误差曲线的对比，为了比较方便，用$\mbox{err}_{SCE}(s,y)=\log_2(1+\exp(-ys))$代替$\mbox{err}_{CE}$。从图中容易看出 \[ \mbox{err}_{0/1}(s,y)\leq\mbox{err}_{SCE}(s,y)={1\over\ln 2}\mbox{err}_{CE}(s,y)， \] 因此可得 \[ E_{in}^{0/1}(\mathbf w)\leq E_{in}^{SCE}(\mathbf w)={1\over\ln 2}E_{in}^{CE}(\mathbf w)\quad\mbox{and}\quad E_{out}^{0/1}(\mathbf w)\leq E_{out}^{SCE}(\mathbf w)={1\over\ln 2}E_{out}^{CE}(\mathbf w)， \] 从而可得 \[ E_{out}^{0/1}(\mathbf w)\leq{1\over\ln 2}E_{in}^{CE}(\mathbf w)+\Omega^{0/1}\quad\mbox{or}\quad E_{out}^{0/1}(\mathbf w)\leq{1\over\ln 2}E_{in}^{CE}(\mathbf w)+{1\over\ln 2}\Omega^{CE}， \] $E_{out}^{0/1}$和$E_{in}^{SQR}$之间也存在同样的关系。从以上关系可以看出，做到$E_{in}^{CE}(\mathbf w)$很小时也可使$E_{out}^{0/1}(\mathbf w)$很小，那么用线性或logistic回归也可解决线性分类问题， \[ g(\mathbf x)=\mbox{sign}(\mathbf w_{REG}^T\mathbf x)。 \]

PLA在数据线性可分时效率较高否则需要采用pocket算法，线性或logistic回归“容易”优化但采用了比$err_{0/1}$松散的误差上限。

可用线性回归设置PLA、pocket或logistic回归的初始值$\mathbf w_0$，logistic回归的计算复杂度和pocket相当，通常logistic回归的性能优于pocket。

随机梯度下降法

迭代优化时，参数更新可以表示为 \begin{equation*} \mathbf w_{t+1}\leftarrow \mathbf w_{t}+\eta\mathbf v\quad(t=0,1,\ldots)。 \end{equation*} PLA每次采用一个数据更新参数，但logistic的梯度下降法每次采用全部数据更新参数，显然logistic更新过程计算量大很多。logistic回归和pocket效率差不多，能否使logistic回归和PLA一样快呢？✅

logistic回归采用的参数更新方法是 \begin{equation} \mathbf w_{t+1}\leftarrow \mathbf w_{t}+\eta{1\over N}\sum_{n=1}^N\theta\left(-y_n\mathbf w^T\mathbf x_n\right)(y_n\mathbf x_n)， \end{equation} 按梯度负方向$\mathbf v=-\nabla E_{in}(\mathbf w)$更新。通过$n$个点计算可估计梯度，极端情况用1个点计算估计梯度，称为随机梯度。随机梯度可视为真实梯度与零均值噪声之和，经过足够过的迭代次数，平均的真实梯度和平均的随机梯度基本相同，可利用随机梯度更新参数， \begin{equation} \mathbf w_{t+1}\leftarrow \mathbf w_{t}+\eta\theta\left(-y_n\mathbf w_t^T\mathbf x_n\right)(y_n\mathbf x_n)， \end{equation} 这就是随机梯度下降法（SGD，stochastic gradient descent）。

随机梯度法的优点是简单且计算量小，有利于大数据和在线学习；其缺点是稳定性欠佳，尤其是$\eta$很大时。随机梯度法实现时需要处理两个问题：

1. 停止条件：梯度下降法可通过梯度是否接近零作为停止条件，但是随机梯度法没有梯度计算，难以确定停止条件，通常用足够大的迭代次数$t$作为停止条件；
2. 选择合适的$\eta$：通常利用交叉验证选择，经验表明$\eta=0.1$在大多数情况下是不错的选择。

回顾PLA的参数更新过程 \begin{equation} \mathbf w_{t+1}\leftarrow \mathbf w_{t}+1\cdot\left[\left[-y_n\neq\mbox{sign}(\mathbf w_t^T\mathbf x_n)\right]\right](y_n\mathbf x_n)， \end{equation} 随机梯度下降法的logistic回归想当于soft-PLA，用$\theta\left(-y_n\mathbf w_t^T\mathbf x_n\right)$表示更新的力度；当$\eta=1$并且$\mathbf w_t^T\mathbf x$很大时，PLA和随机梯度下降法的logistic回归相似。利用随机梯度下降法的线性回归可以表示为 \begin{equation} \mathbf w_{t+1}\leftarrow \mathbf w_{t}+2\eta\left(y_n-\mathbf w_t^T\mathbf x_n\right)\mathbf x_n， \end{equation} $y_n-\mathbf w_t^T\mathbf x_n$表示错得越多，更新力度越大。

多分类问题

采用one-vs-all的数据分割策略，利用logistic回归进行软性（softly）分类，选择“概率”大的类别 \begin{equation} g(\mathbf x)=\arg\max_{k\in\mathcal Y}\theta\left(\mathbf w_{[k]}^T\mathbf x\right)=\arg\max_{k\in\mathcal Y}\mathbf w_{[k]}^T\mathbf x。 \end{equation} one-vs-all方式的优点是简单易推广，并且很容易并行化训练每个分类器；它的坏处是当类别数$K$很大时，数据集$\mathcal D_{[k]}$的不平衡（unbalance）问题凸显。不平衡数据导致logistic回归通过误差最小化求解参数时，倾向于选择有利于数据量多的类别的假设。事实上，有专门的多分类logistic模型，例如softmax分类器。

one-vs-one的方法有利于克服one-vs-all的数据不平衡问题，采用投票机制判断类别，类似循环赛， \begin{equation} g(\mathbf x)=\mbox{tournament champion}\left\{\mathbf w_{[k,l]}^T\mathbf x\right\}。 \end{equation} one-vs-one方式训练每个分类器数据量较少，因此比较有效率，它克服了数据不平衡，以及利用了循环赛机制，所以更稳定；它的坏处是分类器数目更多，导致空间存储增大，预测时间增加，需要更多的训练¹，并且存在有争议的判别区间。

参考文献

脚注