二分类问题的评分值与损失函数
二分类问题是监督学习中最基本的问题之一，本文旨在从评分值、损失函数的角度，对解决二分类问题的诸多机器学习算法做一个梳理。相关算法的详细介绍可以参考相关教材12。
给定一个数据集$D={(\mathbf x_1, y_1), (\mathbf x_2, y_2), …, (\mathbf x_m, y_m)}$ ，其中$y_i\in {-1, 1} $，$\mathbf x_i=(x_{i1}, x_{i2}, …x_{id})$为d维向量 。注意有些资料中二分类比较喜欢用${0, 1}$表示，使用什么数字表示二分类从原理上讲没有区别，但在数学表达上会有一些细微差异。
评分值不是一个机器学习算法中的一个正式名词，但是我们不妨建立这样一个认识角度。我们希望建立关于样本$\mathbf x$的一个评分函数$s(\mathbf x)$，它的基本性质很简单，就是要求和目标值$y$同号，即正样本评分为正数，负样本评分为负数，这样最终的二分类函数为$sign(s(\mathbf x))$。
那么我们要如何建立评分函数呢？直观的想法是，对样本的$d$个属性进行加权求和，这样能体现每个属性在评分中的重要性，如此建立的评分不一定在0值处有区分作用，因此再加上一个偏置项，所以评分函数为$s(\mathbf x)=w^T\mathbf x+b$，这个基本的评分函数可以衍生出很多算法。
评价二分类问题的基本标准是分类错误率，针对每一个样本，如果去计算它的损失函数，就是分类正确损失为0，分类错误损失为1，这种损失函数一般叫做0-1损失函数，可记为$l_{0-1}=\mathbb{I}[sign(s(\mathbf x))\neq y]$。
如果我们统一考虑正、负样本，令$z=s(\mathbf x)*y$ ，那么分类正确时，$z$必然始终为正值，不妨称其为绝对评分值,$z$是对分类是否正确的一个度量。则$l_{0-1}=\mathbb{I}[sign(z)= -1]$，故$l_{0-1}$是关于$z$的分段函数。从最优化理论的角度来看，这个函数无法求梯度或次梯度，因此需要找它的近似来优化。这个近似$\widetilde l$的基本标准是：始终为非负值；当它很小时，$l_{0-1}$很小。
评分值是属性$X$的线性组合，从另一个角度看，评分值也是关于权值$w$的线性组合。一般的，我们将$X$变换到新的特征空间得到$\phi (\mathbf x)$。则评分值为$z=(w^T\mathbf \phi (\mathbf x)+b)y$。上述分析基本不变，只是模型的复杂度更高了。以下分析如无特别说明仍在原空间进行。
1 线性回归
要求评分值与目标值同号，如果目标定得更加狭隘一些，可以令评分值直接为${-1, 1}$,这是线性回归问题，损失函数使用误差平方（可以做直观的理解，也可以认为样本的误差符合正态分布，从极大似然的角度推导出，这不是本文的重点。）。注意到$l_{sqr}=(s(\mathbf x)-y)^2=(s(\mathbf x) * y-y^2)^2=(z-1)^2$，故误差函数是关于绝对评分值$z$的二次函数。从图中可以看出$l_{sqr}$是始终大于$l_{0-1}$的，而且当$l_{sqr}$比较小时，$l_{0-1}$也比较小，所以可以作为$l_{0-1}$的近似。
线性回归有封闭解$w=(X^TX)^{-1}X^Ty$，所以使用线性回归做二分类非常简单，但是效果一般不太好，为什么呢？从$l_{sqr}$的曲线可以看出，当绝对评分值很大时，$l_{0-1}$应该为0，直观来说，绝对评分值很大应该是区分度高的一件好事情，但是$l_{sqr}$却给与了更高的惩罚，这是不合理的。线性回归可以给出一个还不错的$w$值，可以用作其他算法的初始值。
2 感知机学习
感知机学习可以用如下的直观想法来理解：针对绝对评分值，当它为正数时，分类正确，我们认为误差为0，当它为负数时，我们认为离0值越远，误差越大，即$l_p=max(0, -z)$，从$l_p$的曲线来看，也是$l_{0-1}$的一个近似，虽然它也是一个分段函数，但是是可以求次梯度的,$z\geqslant 0$时，认为梯度为0，当$z<0$时，$\frac{dl_p}{dw}=\frac {dl_p}{dz}\frac{dz}{dw}=-1*y\mathbf x=-y\mathbf x$，使用随机梯度下降法，$w\leftarrow w+\eta y\mathbf x$也就是说，只在出现评分错误时进行优化，这恰好就是感知机学习算法所做的工作。
3 支持向量机
对感知机学习的误差函数，我们可以进一步优化，我们希望绝对评分值要充分大，这样认为样本是正样本我们才更加放心，考虑到$z$是关于$w,b$可缩放的，不妨定义充分大为大于1。于是有$l_{hinge}=max(0, 1-z)$,这个损失函数被称为hinge损失函数。考虑结构风险，我们的优化目标为
\[\underset{w,b}{min}=\frac{1}{2}\left \|w \right \|^2+C\sum_{i=1}^{m}max(0, 1-z)\]通过松弛变量法，就可以变为软间隔支持向量机，通过二次规划来求出模型。
从评分值的角度来理解，评分值充分大使得模型针对新的样本有较好的鲁棒性，这正是支持向量机比较优秀的地方。如果引入特征空间，则在支持向量机的求解过程中要大量计算内积，将特征空间的内积简化为原空间的核函数可以引入核方法。
4 Logistic回归
在$z$值的基础上，我们希望它能算出一个概率，衡量分类正确的概率或者说程度。即将$z$的值域从$(-\infty , +\infty )$映射到$(0,1)$ ,那么sigmoid函数是个好的选择，它可求梯度而且在0处概率恰好为0.5。即
\[sigmoid(z)=\frac {1}{1+exp(-z)}\]然后，我们再根据这个sigmoid函数，再来模拟损失函数$l_{0-1}(z)$，我们要求损失函数关于$z$递减，而且始终为正数，考虑概率求对数后再取负号，故
\[l_{log}(z)=-log(sigmoid(z))=log(1+exp(-z))\]由图可以看出，它也是$l_{0-1}(z)$的一种近似。以对数损失函数为优化目标。
\[\underset{w,b}{min}=\sum_{i=1}^{m}log(1+exp(-z))+ \lambda\left \|w \right \|^2\]这是带正则化的Logistic回归，由于$l_{log}(z)$处处可微，因此可以使用梯度下降法等最优化方法求解。
5 AdaBoost
指数函数同样可以满足近似$l_{0-1}$的基本条件，即损失函数定义为$l_{exp}(z)=exp(-z)$。
指数损失函数结合加性模型，可以推导出AdaBoost算法。
所谓加性模型，可以这样来理解：假设我们得到的特征空间中的d维向量$\phi(\mathbf x)$对应的就是d个弱分类器，就是说比随机猜测50%的正确率高一点的分类器。所谓的Boost方法就是有效的组合这些弱分类器来构建强分类器。加性模型本质上依然是一个线性模型。依然有评分函数为$s(\mathbf x)=w^T\mathbf \phi (\mathbf x)$。（考虑到弱分类器本身可以有偏置，因此取$b=0$。）只不过这里的$\phi(\mathbf x)$代表一个弱分类器，而不是一个简单的属性变换（本质上看，也是一种属性变换）。
AdaBoost是一个逐步迭代的过程，假设经过$m-1$轮迭代已经得到评分函数$s_{m-1}(\mathbf x)=\sum_{i=1}^{m-1}w_i\phi_i(\mathbf x)$,在第$m$轮迭代后得到$w_m, \phi_m(\mathbf x), s_m(\mathbf X)$,则$s_m(\mathbf X)=s_{m-1}(\mathbf X)+w_m\phi_m(\mathbf x)$，AdaBoost的优化目标是使得每一步得到的评分函数关于指数损失函数最小，即
\[w_m, \phi_m = arg\underset{w,\phi}{min}\sum_{i=1}^Nexp(-z_{mi}) \quad z_{mi}=y_is_m(\mathbf X_i)\]该式的进一步推导此处不再详述。
小结
以上介绍了6种损失函数，他们都是关于评分值的单调非增函数，其中后面5种是关于0-1损失函数的近似替代，通过求解替代函数能否得到原问题的解，有深入的研究，称为替代损失的“一致性”问题3。
此外，如果我们要找出所有样本种的正例并排序，那么评分值应该在参与优化的时候就具备排序的特性，对数损失和指数损失是单调递减的，以它们为优化目标的模型计算出的评分值可以参与排序，其他几种损失函数不是单调递减的，因此相应的评分值不适合排序。