二分类问题

问题介绍

我们在实际生活中会遇到很多的分类问题。对于输入数据 $x$ ，我们需要判断其属于哪一个已知类别 $y$ 。一般来说，对于最简单的一种分类问题，我们可以将类型的取值看做 $0,1$ 。

$y=0$ ：负类(Negative Class)
$y=1$ ：正类(Positive Class)

一般来说，这种分类问题称作二分类问题(Binary Classification)。

对于二分类问题，我们可以试着应用线性回归模型。假设函数为

$h_{\theta}(\boldsymbol{x})=\boldsymbol{\theta}^{T}\boldsymbol{x}$

由于输出值 $y\in\{0,1\}$ ，我们可以规定

$h_{\theta}(x)\geqslant 0.5$ 时：预测结果为 $y=1$
$h_{\theta}(x)<0.5$ 时：预测结果为 $y=0$

然而，当训练集数据中存在一些“不合群”的数据点时，线性回归函数通常会受此影响，从而大幅降低预测准确度。下图的蓝色线就是被右侧的那个孤立数据点所影响，从而影响了预测准确度。

[{"url":"/img/mlearning/m4f1.png","alt":"分类问题中应用线性回归模型","title":""}]

此外， $h_{\theta}(x)$ 可能会超出 $[0,1]$ 的范围，这说明线性回归模型一般不适用于分类问题。

Logistic 回归

在刚刚我们提到，使用线性回归模型可能会使得输出变量超出 $[0,1]$ 的范围。此时我们可以考虑一个函数，把超出 $[0,1]$ 的部分映射到 $[0,1]$ 之内，具体可以定义为

$g:\mathbb{R}\rightarrow (0,1),\quad g(x)=\frac{1}{1+e^{-x}}$

其中，函数 $g(x)$ 也被称作Sigmoid函数或Logistic函数。应用到 $h_{\theta}(\boldsymbol{x})$ 上有

$h(\boldsymbol{x})=g(\boldsymbol{\theta}^T\boldsymbol{x})=\frac{1}{1+e^{-\boldsymbol{\theta}^T\boldsymbol{x}}}$

使用了Logistic函数的回归算法也被称作Logistic回归，其函数的图像大致如下。

[{"url":"/img/mlearning/m4f2.png","alt":"Logistic函数","title":""}]

对于输入 $\boldsymbol{x}$ ，Logistic回归的输出 $h(\boldsymbol{x})$ 被解释为 对于输入 $\boldsymbol{x}$ ，分类结果 $y=1$ 的概率估计 。使用数学语言表示为

$h(\boldsymbol{x})=P(y=1\mid\text{given }\boldsymbol{x} \text{ parameterized by } \boldsymbol{\theta})$

例如， $h(\boldsymbol{x})=0.7$ 表示以 $\boldsymbol{x}$ 为特征的数据，其分类结果 $y=1$ 的概率为0.7或70%；相反的，其分类结果 $y=0$ 的概率为0.3或30%。

决策边界

第一小节中我们提到：对于一个输入 $x$ ，其输出 $y$ 规定为

$h_{\theta}(x)\geqslant 0.5$ 时：预测结果为 $y=1$
$h_{\theta}(x)< 0.5$ 时：预测结果为 $y=0$

对于Logistic函数，对其求导有

$g'(x)=\frac{e^{-x}}{(1+e^{-x})^2}=g(x)[1-g(x)]>0$

这说明 $g(x)$ 在定义域上单调递增。不难发现 $g(0)=0.5$ ，因此上述条件可以改写为

$\boldsymbol{\theta}^T\boldsymbol{x}\geqslant 0$ 时：预测结果为 $y=1$
$\boldsymbol{\theta}^T\boldsymbol{x}<0$ 时：预测结果为 $y=0$

假设有给定的训练集数据(下图)和假设函数

$h(\boldsymbol{x})=g(\boldsymbol{\theta}^T\boldsymbol{x})=g(\theta_0+\theta_1x_1+\theta_2x_2)$

[{"url":"/img/mlearning/m4f3.png","alt":"线性决策边界的例子","title":""}]

不妨假设我们已经通过(后续要学习的)某种方法得到了拟合参数 $\boldsymbol{\theta}=(-3,1,1)^T$ 。根据判断条件，我们可以把应用了Logistic模型的算法解释为

$\boldsymbol{\theta}^T\boldsymbol{x}=-3x_0+x_1+x_2\geqslant 0$ 时：预测结果为 $y=1$
$\boldsymbol{\theta}^T\boldsymbol{x}=-3x_0+x_1+x_2<0$ 时：预测结果为 $y=0$

因此，平面直线 $x_1+x_2=3$ 将整个平面划分为了两个部分，称之为决策边界(Decision Boundary)。由于每一个数据的分类要么是0，要么是1，因此其一定存在于直线 $x_1+x_2=3$ 的某一侧(或直线上)。

决策边界不一定是线性的，满足条件的平面曲线也可以作为决策边界。决策边界不依赖于训练集，而只与假设本身和输入参数的性质有关。

Logistic 回归的参数拟合

损失函数

为了拟合出Logitsic回归模型的参数 $\boldsymbol{\theta}$ ，我们需要再次定义回归模型的代价函数

$\begin{aligned}J(\boldsymbol{\theta})&=\frac{1}{m}\sum_{i=1}^{m} \frac{1}{2}\Big(h(\boldsymbol{x^{(i)}})-y^{(i)}\Big)^2\\&=\frac{1}{m}\sum_{i=1}^{m} \text{Cost}(h(\boldsymbol{x^{(i)}}),y^{(i)})\end{aligned}$

在上式中，我们替换并定义了一个损失函数，又言之单训练样本代价函数 $\text{Cost}(h(\boldsymbol{x}),y)=\dfrac{1}{2}\Big(h(\boldsymbol{x})-y\Big)^2$ 。损失函数是针对单个样本而言的，但我们以后同样称其为代价函数。当 $h$ 是Logistic函数等非线性函数时，代价函数 $J(\boldsymbol{\theta})$ 很可能不再是一个凸函数。换言之，此时使用梯度下降法很容易收敛到一个局部最小值点，而非全局最小值点。

为此，我们需要针对Logistic回归模型重新定义代价函数 $\text{Cost}(h(\boldsymbol{x}),y)$ 如下

$\text{Cost}(h(\boldsymbol{x}),y)= \begin{cases} -\log h(\boldsymbol{x})& \text{if }y=1 \\ -\log (1-h(\boldsymbol{x}))& \text{if }y=0 \end{cases}$

在上述代价函数中， $y$ 是训练集中针对输入 $\boldsymbol{x}$ 的已知分类结果。代价函数的图像如下

[{"url":"/img/mlearning/m4f4.png","alt":"Logitsic回归模型的代价函数","title":""}]

这个代价函数之所以有效，可以作如下解释。

当 $y=1$ $y = 1$ 时：
- 预测值 $h(\boldsymbol{x})\to 1$ 时， $\text{Cost}\to 0$ ，这表示预测是准确的
- 预测值 $h(\boldsymbol{x})\to 0$ 时， $\text{Cost}\to \infty$ ，这表示预测是不准确的
当 $y=0$ $y = 0$ 时：
- 预测值 $h(\boldsymbol{x})\to 0$ 时， $\text{Cost}\to 0$ ，这表示预测是准确的
- 预测值 $h(\boldsymbol{x})\to 1$ 时， $\text{Cost}\to \infty$ ，这表示预测是不准确的
可以证明：该函数的形式可以把问题转化为一个凸优化问题(Convex Optimization)，整体的代价函数 $J(\boldsymbol{\theta})$ 也是一个凸函数，可以通过梯度下降算法找到最小值点。

当预测不准确时，代价函数 $\text{Cost}$ 的对数性质会产生大量代价，导致 $J(\boldsymbol{\theta})$ 增大。我们可以把代价理解成惩罚，此时就可以告诉计算机：这种参数选择带来的 $h(\boldsymbol{x})$ 不是一个好的假设函数。

代价函数的简化

上文中定义的单训练样本代价函数 $\text{Cost}(h(\boldsymbol{x}),y)$ 是一个分段函数，为了简便，我们可以将其改写为

$\text{Cost}(h(\boldsymbol{x}),y)=-y\log h(\boldsymbol{x})-(1-y)\log(1-h(\boldsymbol{x}))$

证明二者等价是显然的，分别带入 $y=0,1$ 并对比函数形式即可。

将这个简化版的函数代入 $J(\boldsymbol{\theta})$ 可以得到

$J(\boldsymbol{\theta})=-\frac{1}{m}\sum_{i=1}^m\Big[y^{(i)}\log h(\boldsymbol{x^{(i)}})+(1-y^{(i)})\log(1-h(\boldsymbol{x^{(i)}}))\Big]$

这个函数的形式也可以通过数理统计中的极大似然估计法得出。

梯度下降

在前面的讨论之后，我们就可以使用梯度下降法寻找合适的参数 $\boldsymbol{\theta}$ 了。

$\theta_{j}:=\theta_j-\alpha\frac{\partial}{\partial \theta_j}J(\boldsymbol{\theta}),\quad(j=0,1,\cdots,n)$

这里，我觉得有必要留存一下求偏导的推导过程。

以 $\log=\ln$ 为例，则有

$\begin{aligned} \frac{\partial}{\partial \theta_j}J(\boldsymbol{\theta})&=-\frac1m\sum_{i=1}^m\left[\frac{y^{(i)}}{h(x^{(i)})}\frac{\partial h(x^{(i)})}{\partial\theta_j}-\frac{1-y^{(i)}}{1-h(x^{(i)})}\frac{\partial h(x^{(i)})}{\partial\theta_j}\right]\\&=-\frac{1}{m}\sum_{i=1}^{m}\left[\frac{y^{(i)}}{g(\theta^{T}x^{(i)})}\frac{\partial g(\theta^{T}x^{(i)})}{\partial\theta_{j}}-\frac{1-y^{(i)}}{1-g(\theta^{T}x^{(i)})}\frac{\partial g(\theta^{T}x^{(i)})}{\partial\theta_{j}}\right]\\ &=-\frac1m\sum_{i=1}^m\left[\frac{y^{(i)}}{g(\theta^Tx^{(i)})}\cdot g(\theta^Tx^{(i)})[1-g(\theta^Tx^{(i)})]x^{(i)}_j-\frac{1-y^{(i)}}{1-g(\theta^Tx^{(i)})}\cdot g(\theta^Tx^{(i)})[1-g(\theta^Tx^{(i)})]x_j^{(i)}\right]\\&=-\frac1m\sum_{i=1}^m\left[y^{(i)}(1-g(\theta^Tx^{(i)}))x_j^{(i)}-(1-y^{(i)})g(\theta^Tx^{(i)})x_j^{(i)}\right]\\&=\frac1m\sum_{i=1}^m\Big(g(\theta^Tx^{(i)})-y^{(i)}\Big)x_j^{(i)}\\&=\frac1m\sum_{i=1}^m\Big(h(x^{(i)})-y^{(i)}\Big)x_j^{(i)},\quad(j=0,1,\cdots,n) \end{aligned}$

这和线性回归模型得出的结论一致，唯一的不同是 $h(x)$ 的表述不同。因此，我们完全可以把线性回归模型中，梯度下降法的技巧应用到Logistic回归的梯度下降法中。

代码实现

我们在 Python定义两个关键函数，以实现 Logistic 回归模型的梯度下降参数训练。

# Sigmoid 函数
def sigmoid(z):
    return 1 / (1 + np.exp(-1*z))

# 梯度下降
def gradient_descent(X, y, learning_rate=0.01, iterations=1000, tol=1e-5):
    theta = np.random.randn(X.shape[1])
    for _ in range(iterations):
        p = sigmoid(np.dot(X, theta))
        gradient = np.dot(X.T, (p - y))
        theta_update = learning_rate * gradient
        theta -= theta_update
        if np.linalg.norm(theta_update, ord=1) < tol:
            print(f"迭代终止在第{_}次循环")
            break
    return theta

多分类问题

一对多分类

对于存在多个类别的分类问题，我们可以将分类结果按照 $y=1,2,3,\cdots$ 进行表示。在二分类问题中，我们可以使用线性回归、Logistic 回归等方法进行分类预测。当我们把二分类问题的策略搬到多分类问题中时，可以参考下面的例子。

假设训练集中包含三种类别

三角形： $y=1$
正方形： $y=2$
红色X： $y=3$

我们先假设三角形 $y=1$ 为正类，其他数据为负类，以此构造一个二分类模型 $h^{(1)}(\boldsymbol{x})$ ；接着选择正方形 $y=2$ 为正类，其他数据为负类，依次再构造一个二分类模型 $h^{(2)}(\boldsymbol{x})$ ；同理有 $h^{(3)}(\boldsymbol{x})$ 。

这样，我们就得到了三个分类器

$h^{(i)}(\boldsymbol{x})=P(y=1\mid \boldsymbol{x},\boldsymbol{\theta}),\quad (i=1,2,3)$

[{"url":"/img/mlearning/m4f5.png","alt":"一对多分类的例子","title":""}]

对于每一个分类器 $h^{(i)}(\boldsymbol{x})$ ，其输出结果表示了 $y=i$ 的概率，此时选取输出值最大的，其最可能的分类结果就可以断定为 $y=i$ 。这种策略也称作一对多分类(One v.s. All)，是一种简单且有效的分类方式。

KNN算法

$K$ 近邻算法(K-Nearest Neighbors) 是一种简单且常用的分类和回归算法。由于其过于简单和实用，我们这里只列出其算法流程

计算待分类样本与训练集中每个样本的距离。常用的距离度量方法有欧氏距离、曼哈顿距离等。
选择 $K$ 个最近邻：根据计算出的距离，选择距离最近的 $K$ 个样本。
投票或平均

对于分类问题， $K$ 个最近邻中出现次数最多的类别即为待分类样本的类别
对于回归问题， $K$ 个最近邻的值的平均值即为待分类样本的值。

$K$ 值的选择对模型的性能有重要影响。通常可以通过交叉验证或可视化方法选择最佳的 $K$ 值。具体原理可以参考后续日志内容。

正则化

过拟合问题

在上一篇日志中，我们谈到了多项式回归的过拟合(Overfitting)问题。

线性回归：可能导致欠拟合(Underfitting)，即模型具有高偏差(High Bias)
高次数多项式回归：可能导致过拟合，即模型具有高方差(High Variance)

[{"url":"/img/mlearning/m4f6.png","alt":"欠拟合和过拟合","title":""}]

过拟合模型的问题在于：其能够很好的拟合训练集数据，但是对于新数据的预测能力较差。这在直观上表示为多项式函数图像的陡峭性，导致其在实际问题上表现出反常的变化趋势。这种表现也称为较差的泛化能力(Generalization)。

对于过拟合模型，一般有两种处理方式

减少特征量
使用正则化(Regularization)方法

正则化和代价函数

如果模型的特征量都比较关键，不容易舍去时，可以采用正则化的方法。

举例而言，如果我们想使用一个四次多项式作为假设函数

$h(x)=\theta_0+\theta_1x+\theta_2x^2+\theta_3x^3+\theta_4x^4$

假设函数的过拟合主要是由高次数项 $x^3,x^4$ 导致的，为此我们想要使得其系数项 $\theta_3,\theta_4$ 尽可能的小。为此，我们可以在原代价函数 $J(\boldsymbol{\theta})$ 后面添加两项惩罚项(Penalty)。

$J(\boldsymbol{\theta})=\frac{1}{2m}\sum_{i=1}^{m}\Big(h_{\theta}(\boldsymbol{x^{(i)}})-y^{(i)}\Big)^2+M\theta_3^2+N\theta_4^2$

其中 $M,N$ 是两个大数。此时，我们想要使得上述代价函数尽可能小，那么 $\theta_3,\theta_4$ 就必须尽可能的接近于0，此时的函数图像就贴近于一个良好拟合的二次函数了。这种增加惩罚项以避免过拟合的方法便是正则化。

正则化实际上就是在原先的代价函数后面添加了一项惩罚项，即表示为

$J_{new}=J_{original}+\text{Penalty}$

如果我们有 $n$ 个特征量，采用正则化就可以改写代价函数为

$J(\boldsymbol{\theta})=\frac{1}{2m}\left[\sum_{i=1}^{m}\Big(h_{\theta}(\boldsymbol{x^{(i)}})-y^{(i)}\Big)^2+\lambda\sum_{j=1}^{n}\theta_j^2\right]$

其中，惩罚项 $\lambda\displaystyle\sum_{j=1}^n \theta_j^2$ 被称作L2正则项，且参数 $\lambda$ 称作正则化参数。使用了L2正则项的回归模型称作岭回归模型(Ridge Regression)。

在后一项求和中，一般规定不对 $\theta_0$ 求和。当正则项形式为 $\lambda\displaystyle\sum_{j=1}^n |\theta_j|$ 时，称之为L1正则项，使用了L1正则项的回归模型称作Lasso回归。在今后的讨论中默认使用L2正则项。

可以看出，正则化参数 $\lambda$ 的作用是用来平衡 $J_{original}$ 和正则项的。

正则项的加入可以让所有的参数都倾向于变小，使得假设函数更平滑
正则化参数 $\lambda$ $λ$ 的选取不能随意进行
- 如果 $\lambda$ 过小，可能起不到正则化的效果
- 如果 $\lambda$ 过大，在正则项的影响下可能导致所有的参数都趋于0，使得模型退化为一条几乎水平的直线，从而欠拟合

[{"url":"/img/mlearning/m4f7.png","alt":"正则化参数过大导致欠拟合","title":""}]

线性回归梯度下降正则化

当我们使用了L2正则化时，线性回归的梯度下降法也需要改动。

$\theta_j:=\theta_j-\alpha\cdot\dfrac{1}{m}\displaystyle\sum_{i=1}^{m}\Big(h_{\theta}(\boldsymbol{x}^{(i)})-y^{(i)}\Big)x_j^{(i)},\quad(j=0,1,\cdots,n)$

$\theta_0:=\theta_j-\alpha\cdot\dfrac{1}{m}\displaystyle\sum_{i=1}^{m}\Big(h_{\theta}(\boldsymbol{x}^{(i)})-y^{(i)}\Big)x_0^{(i)}$

$\begin{aligned}\theta_j:&=\theta_j-\alpha\cdot\dfrac{1}{m}\left[\displaystyle\sum_{i=1}^{m}\Big(h_{\theta}(\boldsymbol{x}^{(i)})-y^{(i)}\Big)x_0^{(i)}+\lambda\theta_j\right]\\&=\theta_j\left(1-\alpha\cdot\frac{\lambda}{m}\right)-\alpha\cdot\dfrac{1}{m}\displaystyle\sum_{i=1}^{m}\Big(h_{\theta}(\boldsymbol{x}^{(i)})-y^{(i)}\Big)x_j^{(i)}\\ &\quad(j=1,2,\cdots,n) \end{aligned}$

在使用了正则化的梯度下降迭代式中，参数 $\theta_j(j>0)$ 乘了一个因子

$1-\alpha\cdot\frac{\lambda}{m}<1,\quad \text{where $\alpha\cdot\dfrac{\lambda}{m}$ is usually pretty small}$

这表明，每次迭代都把参数 $\theta_j(j>0)$ 乘以了一个略小于1的数，以达到不断缩小参数值的效果。这也表明了正则化方法的可行性。

线性回归正规方程正则化

上一篇日志也提到正规方程的解如下

$\boldsymbol{\theta}=(\boldsymbol{X}^T\boldsymbol{X})^{-1}\boldsymbol{X}^T\boldsymbol{y}$

有时候，矩阵 $\boldsymbol{X}^T\boldsymbol{X}$ 不一定是可逆的，那么就不能这样求解方程。不放假设引入L2正则项，经过推导后可以得出下面这个新的方程

$\boldsymbol{\theta}=\left(\boldsymbol{X}^T\boldsymbol{X}+\lambda\begin{bmatrix}0&&&&\\&1&&&\\&&1&&\\&&&\ddots&\\&&&&1\end{bmatrix}_{(n+1)\times(n+1)}\right)^{-1}\boldsymbol{X}^T\boldsymbol{y},\quad(\lambda>0)$

此时，括号内的矩阵是一个满秩矩阵(证明略)，因此其一定可逆。

这表明，正规方程法遇到矩阵不可逆的情况时，可引入正则化方法解决。

Logistic 回归正则化

前面提到，Logistic 回归的梯度下降法和线性回归模型几乎一致，因此有

$\begin{aligned}\theta_j:&=\theta_j-\alpha\cdot\dfrac{1}{m}\left[\displaystyle\sum_{i=1}^{m}\Big(h(\boldsymbol{x}^{(i)})-y^{(i)}\Big)x_0^{(i)}+\lambda\theta_j\right]\\&=\theta_j\left(1-\alpha\cdot\frac{\lambda}{m}\right)-\alpha\cdot\dfrac{1}{m}\displaystyle\sum_{i=1}^{m}\Big(h(\boldsymbol{x}^{(i)})-y^{(i)}\Big)x_j^{(i)}\\ &\quad(j=1,2,\cdots,n) \end{aligned}$