凸性

为什么要优化

对于一个机器学习问题，我们通常定义一个损失函数，用来衡量模型的表现和实际情况的区别。一旦我们有了损失函数，我们就可以使用优化算法来尝试最小化损失。在优化中，损失函数通常被称为优化问题的目标函数。

由于优化算法的目标函数通常是基于训练数据集的损失函数，因此优化的目标是减少训练误差。但是，深度学习等领域的目标是为了减少泛化误差，以实现模型的泛用性。为了实现后者，除了使用优化算法来减少训练误差之外，我们还需要注意过拟合的问题。

在深度学习中，大多数目标函数都很复杂并且无解析解。因此，我们必须使用数值优化算法。而这个过程中，深度学习优化存在许多挑战，其中最令人烦恼的是局部最小值、鞍点和梯度消失。

局部最小值问题：当优化问题的数值解接近局部最优值时，随着目标函数解的梯度接近或变为零，通过最终迭代获得的数值解可能仅使目标函数局部最优，而不是全局最优
鞍点问题：鞍点是指函数的所有梯度都消失但既不是全局最小值也不是局部最小值的任何位置，优化算法可能会在此停止或收敛
梯度消失问题：神经网络模型层数过深可能导致梯度过小

高等数学知识告诉我们，对于一个多元函数梯度为 $\boldsymbol{0}$ 的点，其 Hessian 矩阵的正定性决定了该点是极值点还是鞍点，这为某些情况下的鞍点判断提供了解决方案。然而，深度学习领域的优化问题通常是没有那么容易解决的。

凸集

凸性(Convexity)在优化算法的设计中起到至关重要的作用，这主要是由于在这种情况下对算法进行分析和测试要容易。换言之，如果算法在凸性条件设定下的效果很差，那通常我们很难在其他条件下看到好的结果。

凸集(Convex Set)是研究凸性的基础。简单地说，如果对于任何 $a,b\in\mathcal{X}$ ，连接 $a,b$ 的线段也位于 $\mathcal{X}$ 中，则向量空间中的一个集 $\mathcal{X}$ 是凸的。用数学语言表述为

$\lambda a+(1-\lambda)b\in\mathcal{X},\quad\forall \lambda\in[0,1];a,b\in\mathcal{X}$

[{"url":"/img/Pytorch/p6f1.png","alt":"凸集的直观定义","title":""}]

设 $\mathcal{X},\mathcal{Y}$ 是凸集，那么显然有 $\mathcal{X}\cap\mathcal{Y}$ 也是凸集，且 $\mathcal{X}\cup\mathcal{Y}$ 不一定是凸集。

通常，深度学习中的问题是在凸集上定义的（例如 $\mathbb{R}^n$ ），这为后续讨论提供了基础。

凸函数

给定一个凸集 $\mathcal{X}$ ，若函数 $f:\mathcal{X}\to\mathbb{R}$ 满足

$\lambda f(x_1)+(1-\lambda)f(x_2)\geqslant f\big(\lambda x_1+(1-\lambda)x_2\big),\quad\forall \lambda\in[0,1];x_1,x_2\in\mathcal{X}$

则称函数 $f$ 是该凸集上的一个凸函数。凸函数在优化算法设计中具有基础性作用，其凸性条件可保证极值唯一性。下面使用反证法证明这个重要性质。

已知 $x^*\in\mathcal{X}$ 是定义在凸集 $\mathcal{X}$ 上凸函数 $f$ 的一个局部最小值，即存在一个较小的正数 $\delta$ 。当 $x\in\mathcal{X}$ 满足 $0<\|x-x^*\|<\delta$ 时都有 $f(x^*)<f(x)$ 。

假设存在 $y\in\mathcal{X}$ 使得 $f(y)<f(x^*)$ 。根据凸函数的定义，对于任意 $\lambda\in(0,1)$ 有

$f\big(\lambda y+(1-\lambda)x^*\big)\leqslant \lambda f(y)+(1-\lambda)f(x^*)<f(x^*)$

由于 $\lambda\to 0$ 的过程中， $\lambda y+(1-\lambda)x^*$ 越来越接近 $x^*$ ，而上述不等式始终成立。这与 $x^*$ 是局部最小值的假设矛盾，因此 $f$ 的任意一个局部最小值都是全局最小值。换言之，函数 $f$ 的全局最小值一定可以通过寻找局部最小值的方法找到。

约束优化

等式约束

凸优化的一个很好的特性是能够让我们有效地处理约束优化(Constraints Optimization)问题。在高数课程的多元函数有约束极值部分，教材编者一般都会介绍拉格朗日乘数法，即对于等式约束问题

$\begin{aligned}\min_{\boldsymbol{x}}\quad & f(\boldsymbol{x})\\s.t.\quad &g_i(\boldsymbol{x})=0,\quad i=1,2,\cdots,n \end{aligned}$

我们引入拉格朗日因子 $\lambda_i(i=1,2\cdots,n)$ 和拉格朗日函数

$L(\boldsymbol{x};\lambda_1,\lambda_2,\cdots,\lambda_n)=f(\boldsymbol{x})+\sum_{i=1}^n \lambda_ig_i(\boldsymbol{x})$

可以证明，原约束问题等价于

$\min_{\boldsymbol{x},\lambda_1,\lambda_2,\cdots,\lambda_n} L(\boldsymbol{x};\lambda_1,\lambda_2,\cdots,\lambda_n)$

而这可以通过求出函数 $L$ 所有梯度为 $\boldsymbol{0}$ 的点，然后分别比较得出，即最优解满足

$\begin{cases}\nabla_{x}L=\nabla f+\displaystyle\sum_{i=1}^n\lambda_i \nabla g_i=\boldsymbol{0} & \\\nabla_{\lambda_i}L=0,& i=1,2,\cdots,n \end{cases}$

必须注意，拉格朗日乘数法提供的是极值点的必要条件，而非充分条件。

KTT条件

当约束条件为不等式形式时，上面的讨论不再适用。对于一个简单的不等式约束问题

$\begin{aligned}\min_{\boldsymbol{x}}\quad & f(\boldsymbol{x})\\s.t.\quad &g(\boldsymbol{x})\leqslant 0\end{aligned}$

称约束不等式 $g(\boldsymbol{x})\leqslant 0$ 为原始可行性，那么约束问题的可行域定义为

$K=\{\boldsymbol{x}\in\mathbb{R}^n|g(\boldsymbol{x})\leqslant 0\}$

假设最优解为 $\boldsymbol{x}^*$ ，其必然在可行域内，且分类讨论

当 $g(\boldsymbol{x}^*)<0$ 时： $\boldsymbol{x}^*$ 位于可行域 $K$ 的内部，称为内部解
当 $g(\boldsymbol{x}^*)=0$ 时： $\boldsymbol{x}^*$ 位于可行域 $K$ 的边界，称为边界解

这两种情况的最优解判定具有不同的必要条件，我们尝试同样应用拉格朗日乘数法

$L(\boldsymbol{x},\lambda)=f(\boldsymbol{x})+\lambda g(\boldsymbol{x})$

对于内部解：由于这个解在可行域 $K$ 内具有相当宽的变化范围，因此可以认为该约束优化问题退化为无约束优化问题。由于 $g(\boldsymbol{x}^*)\neq 0$ ，要想使得 $\nabla f=\boldsymbol{0}$ 且 $\nabla_{x}L=\boldsymbol{0}$ ，那么必须有 $\lambda=0$
对于边界解：此时，原问题视为等式约束条件 $g(\boldsymbol{x})=0$ $g (x) = 0$ 的约束优化问题。根据前面的讨论，我们知道一定存在一个拉格朗日因子 $\lambda$ $λ$ 使得 $\nabla f=-\lambda \nabla g$ $\nabla f = - λ \nabla g$ ，根据梯度的性质可知
- $\nabla f$ 表示 $f$ 在该点最陡峭的上升方向，由于最优解在边界取得，因此 $\nabla f$ 必然指向可行域 $K$ 的内部，即 $g(\boldsymbol{x})\leqslant 0$ 的方向
- $\nabla g$ 表示 $g$ 在该点最陡峭的上升方向，其必然指向可行域 $K$ 的外部，即 $g(\boldsymbol{x})>0$ 的方向
- $\nabla f$ 与 $\nabla g$ 是不可能同向的，因此必然有 $\lambda\geqslant 0$

从上面的讨论看出，不论是内部解或边界解，其必然满足条件 $\lambda g(\boldsymbol{x})=0$ ，称为互补松弛性。我们综合上述讨论内容，可以写出原优化问题在拉格朗日乘数法下的所有约束条件

$\begin{aligned}\nabla_{x}L&=\nabla f+\lambda\nabla g=\boldsymbol{0}\\g(\boldsymbol{x})&\leqslant0\\\lambda&\geqslant0\\\lambda g(\boldsymbol{x})&=0\end{aligned}$

这些条件合称为 Karush-Kuhn-Tucker(KKT)条件，即优化问题最优解一定满足KKT条件。

如果要最大化优化，需要修改因子的条件 $\lambda\leqslant 0$

一般的，考虑一个非线性优化问题

$\begin{aligned}\min_{\boldsymbol{x}}\quad & f(\boldsymbol{x})\\s.t.\quad &g_i(\boldsymbol{x})=0,\quad i=1,2,\cdots,m\\&h_j(\boldsymbol{x})\leqslant0,\quad j=1,2,\cdots,n \end{aligned}$

其对应的拉格朗日函数为

$L(\boldsymbol{x};\{\lambda_i\};\{\mu_{j}\})=f(\boldsymbol{x})+\sum_{i=1}^m \lambda_i g_i(\boldsymbol{x})+\sum_{j=1}^n \mu_j h_j(\boldsymbol{x})$

其对应的KKT条件为

$\begin{aligned}\nabla_{x}L&=\boldsymbol{0}\\g_i(\boldsymbol{x})&=0,\quad i=1,2\cdots,m\\h_j(\boldsymbol{x})&\leqslant 0,\quad j=1,2\cdots,n\\\mu_j&\geqslant 0,\quad j=1,2\cdots,n\\\mu_j h_j(\boldsymbol{x})&=0,\quad j=1,2\cdots,n\end{aligned}$

这里提供一道简单的题目，以帮助加深理解。

求解约束问题

$\begin{aligned}\min_{x_1,x_2}\quad & x_1^2+x_2^2\\s.t.\quad &x_1+x_2=1\\&x_2\leqslant \alpha\in\mathbb{R} \end{aligned}$

这是一个凸优化问题，改写成标准形式，写出拉格朗日函数

$L(x_1,x_2,\lambda,\mu)=x_1^2+x_2^2+\lambda(1-x_1-x_2)+\mu(x_2-\alpha)$

写出KKT方程组如下

$\begin{aligned}\frac{\partial L}{\partial x_i}&=0,\quad i=1,2\\x_1+x_2-1&=0\\x_2-\alpha&\leqslant0\\\mu&\geqslant 0\\\mu(x_2-\alpha)&=0\end{aligned}$

根据梯度条件解得

$x_1=\frac12\lambda,\quad x_2=\frac12\lambda-\frac12\mu$

代入 $x_1+x_2-1=0$ ，可以得到 $\lambda$ 和 $\mu$ 的关系式

$\lambda=\frac12\mu+1$

回代入 $x_1,x_2$ 有

$x_1=\frac14\mu+\frac12,\quad x_2=-\frac14\mu+\frac12$

再结合约束条件 $x_2-\alpha\leqslant 0$ ，解得 $\mu\geqslant 2-4\alpha$ ，分类讨论

当 $0=\mu\geqslant 2-4\alpha$ 时，即 $\alpha\geqslant\dfrac12$ 时约束条件无效，此时有内部解 $x_1^*=x_2^*=\dfrac12$
当 $0<\mu=2-4\alpha$ 时，即 $\alpha<\dfrac12$ 时约束有效，得到的是边界解。此时有等式约束 $x_2=\alpha$ ，代入 $x_1+x_2-1=0$ 可以得到 $x_1^*=1-\alpha,x_2^*=\alpha$

凸优化

对于一般的非线性约束优化问题

$\begin{aligned}\min_{\boldsymbol{x}}\quad & f(\boldsymbol{x})\\s.t.\quad &g_i(\boldsymbol{x})=0,\quad i=1,2,\cdots,m\\&h_j(\boldsymbol{x})\leqslant0,\quad j=1,2,\cdots,n \end{aligned}$

如果下述条件满足，则称该问题是一个凸优化问题

$f$ 是一个定义在凸集上的凸函数
$g_i$ 是仿射函数，可以简单理解为 $g_i(\boldsymbol{x})=\boldsymbol{Ax}+\boldsymbol{b}$
$h_j$ 是定义在凸集上的凸函数

前面提到：对于一个凸函数，任意位置的局部最优解同时也是全局最优解，因此不难证明凸优化问题的局部最优解和全局最优解也是等价的。如果能够把某个问题转化为凸优化问题，其求解难度一般是容易的。

拉格朗日对偶

对偶函数

我们首先对一个凸优化问题做如下假定

称该约束优化问题为原问题(Prime Problem)
不再限制 $f$ 的凸性
问题的定义域 $D$ 是所有出现函数定义域的交集，且非空
最优解记为 $p^*=f(\boldsymbol{x}^*)$

对于一个原问题，我们通常用拉格朗日对偶的方式来求解。对偶就是实质相同但从不同角度提出不同提法的一对问题。有时候原问题不太好解，但是其对偶问题(Dual Problem)却很好解，我们就可以通过求解对偶问题来迂回地解答原问题。

原问题的拉格朗日函数表示为

$L(\boldsymbol{x};\{\lambda_i\};\{\mu_{j}\})=f(\boldsymbol{x})+\sum_{i=1}^m \lambda_i g_i(\boldsymbol{x})+\sum_{j=1}^n \mu_j h_j(\boldsymbol{x})$

现在考虑 $L$ 的拉格朗日对偶函数 $\mathcal{L}$ ，其变元记为 $\boldsymbol{\lambda}\in\mathbb{R}^m,\boldsymbol{\mu}\in\mathbb{R}^n$ ，定义为

$\mathcal{L}(\boldsymbol{\lambda},\boldsymbol{\mu})=\inf_{\boldsymbol{x}\in D} L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\mu})$

接下来我们证明，这个对偶函数一定是一个凹函数。这里需要注意：凹函数和凸函数具有类似的定义形式和性质。记 $\boldsymbol{x}$ 在定义域 $D$ 内所有的离散取值为 $\{\boldsymbol{x}_1,\boldsymbol{x}_2,\cdots,\boldsymbol{x}_n,\cdots\}$ ，那么对偶函数 $\mathcal{L}$ 可以看做对离散集合求下确界的形式

$\mathcal{L}(\boldsymbol{\lambda},\boldsymbol{\mu})=\inf \{L(\boldsymbol{x}_1,\boldsymbol{\lambda},\boldsymbol{\mu}),L(\boldsymbol{x}_2,\boldsymbol{\lambda},\boldsymbol{\mu}),\cdots,L(\boldsymbol{x}_n,\boldsymbol{\lambda},\boldsymbol{\mu}),\cdots\}$

为了进一步简化符号，令 $\boldsymbol{\gamma}=(\boldsymbol{\lambda,\mu})$ ，因此我们想证明的是

$\mathcal{L}\big(k\boldsymbol{\gamma}_1+(1-k)\boldsymbol{\gamma}_2\big)\geqslant k\mathcal{L}\big(\boldsymbol{\gamma}_1)+(1-k)\mathcal{L}(\boldsymbol{\gamma}_2)$

对于一个确定的 $\boldsymbol{x}_n$ ，函数 $f,g_i,h_j$ 都是一个常数，因此有

$L(\boldsymbol{x}_n,\boldsymbol{\gamma})=f+\sum_{i=1}^m \lambda_ig_i+\sum_{j=1}^n \mu_j h_j$

这是一个线性函数，而线性函数既是凸函数也是凹函数，因此有

$L\big(\boldsymbol{x}_n,k\boldsymbol{\gamma}_1+(1-k)\boldsymbol{\gamma}_2\big)=kL(\boldsymbol{x}_n,\boldsymbol{\gamma}_1)+(1-k)L(\boldsymbol{x}_n,\boldsymbol{\gamma}_2)$

根据这个性质有

$\begin{aligned}\mathcal{L}\big(k\boldsymbol{\gamma}_1+(1-k)\boldsymbol{\gamma}_2\big)=\inf \{&kL(\boldsymbol{x}_1,\boldsymbol{\gamma}_1)+(1-k)L(\boldsymbol{x}_1,\boldsymbol{\gamma}_2),\\&kL(\boldsymbol{x}_2,\boldsymbol{\gamma}_1)+(1-k)L(\boldsymbol{x}_2,\boldsymbol{\gamma}_2),\\&\cdots,\\&kL(\boldsymbol{x}_n,\boldsymbol{\gamma}_1)+(1-k)L(\boldsymbol{x}_n,\boldsymbol{\gamma}_2),\cdots\}\end{aligned}$

由于 $\min \{a_i+b_i\}\geqslant\min\{a_i\}+\min\{b_i\}$ ，于是有

$\begin{aligned}\mathcal{L}\big(k\boldsymbol{\gamma}_1+(1-k)\boldsymbol{\gamma}_2\big)&\geqslant k\inf_{i=1,2,\cdots,n,\cdots}\{L(\boldsymbol{x}_i,\boldsymbol{\gamma}_1)\}+(1-k)\inf_{i=1,2,\cdots,n,\cdots}\{L(\boldsymbol{x}_i,\boldsymbol{\gamma}_2)\}\\&=k\mathcal{L}\big(\boldsymbol{\gamma}_1)+(1-k)\mathcal{L}(\boldsymbol{\gamma}_2)\end{aligned}$

对偶问题

假设 $\hat{\boldsymbol{x}}\in D$ 是原问题的一个可行解，那么对于所有的 $i,j$ 有

$g_{i}(\hat{\boldsymbol{x}})=0,\quad h_{j}(\hat{\boldsymbol{x}})\leqslant 0$

当 $\mu_j \geqslant 0$ 时，可以得出拉格朗日函数的取值范围

$L(\hat{\boldsymbol{x}},\boldsymbol{\lambda},\boldsymbol{\mu})=f+\sum_{i=1}^m \lambda_ig_i+\sum_{j=1}^n \mu_j h_j\leqslant f$

又因为 $p^*=\min f$ ， $\mathcal{L}=\inf L$ ，那么有如下不等式

$\mathcal{L}(\boldsymbol{\lambda},\boldsymbol{\mu})\leqslant L\leqslant p^*$

因此，这个对偶函数 $\mathcal{L}$ 一定不大于原问题的最优解，即有

$p^*\geqslant\max_{\boldsymbol{\lambda},\boldsymbol{\mu}}\mathcal{L}(\boldsymbol{\lambda},\boldsymbol{\mu})$

这表明，即使我们无法求出原问题的最优解 $p^*$ ，但是可以通过求解凹函数 $\mathcal{L}$ 的最大值或局部最大值来估计 $p^*$ 的下界，此时只需要满足 $\mu_i\geqslant 0$ 即可。事实上，这一定是一个凸优化问题，并且其和原问题紧密相关，我们称其为对偶问题(Dual Problem)。回顾一下原问题的形式为

$\begin{aligned}\min_{\boldsymbol{x}\in D}\quad & f(\boldsymbol{x})\\s.t.\quad &g_i(\boldsymbol{x})=0,\quad i=1,2,\cdots,m\\&h_j(\boldsymbol{x})\leqslant0,\quad j=1,2,\cdots,n \end{aligned}$

那么，其对偶问题可以记作

$\begin{aligned}\max_{\boldsymbol{\lambda},\boldsymbol{\mu}}\quad & \mathcal{L}(\boldsymbol{\lambda},\boldsymbol{\mu})=\max_{\boldsymbol{\lambda},\boldsymbol{\mu}}\inf_{\boldsymbol{x}\in D} L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\mu})\\s.t.\quad &\mu_j\geqslant0,\quad j=1,2,\cdots,n \end{aligned}$

这个对偶问题是一个凸优化问题，使用KKT条件等求出一个局部最大值后，就确定了其最优解 $d^*$ 。而我们前面的讨论中提到 $d^*\leqslant p^*$ ，并且在某些时候 $d^*=p^*$ ，这就大大简化了约束优化的难度。

弱对偶与强对偶

对于某些问题，其原问题的最优解和对偶问题的最优解是相同的，此时称其具有强对偶性；相反的，当 $p^*>d^*$ 时，称其具有弱对偶性。根据已有讨论，我们可以得出如下结论

对于任意一个强对偶性问题，其最优解 $p^*$ 满足 KKT 条件
对于一个可微的凸优化问题，其具有强对偶性

一个约束优化问题的凸性是比较容易看出来的，但是其对偶性具有较大的讨论空间。这里，我们主要讨论一个凸优化问题什么时候是强对偶的（不考虑可微性），我们称之为 Slater判定条件。

Slater 判定条件要求，对于原问题而言，存在点 $\boldsymbol{x}_0\in D$ 满足

$g_i(\boldsymbol{x}_0)=0,\quad h_j(\boldsymbol{x}_0)<0,\quad \forall i,j$

对于大多数凸函数而言，Slater条件都是成立的，因此可直接求解对应的KTT方程组。

损失函数的凸性

线性回归MSE

在线性回归模型中，我们通常定义均方误差函数(MSE)来衡量模型的训练结果。假设有 $m$ 个样本和 $n$ 个特征量，并考虑把偏置项 $b$ 融入参数向量或矩阵，那么特征矩阵 $\boldsymbol{X}\in \mathbb{R}^{m\times (n+1)}$ ，标签向量 $\boldsymbol{y}\in\mathbb{R}^m$ ，待训练参数为 $\boldsymbol{w}\in\mathbb{R}^{n+1}$ 。均方误差函数记作

$MSE=\frac{1}{2m}\|\boldsymbol{Xw}-\boldsymbol{y}\|^2$

我们因此考虑无约束优化问题

$\min_{\boldsymbol{w}} MSE$

现在我们来说明 $MSE$ 是一个凸函数。一个函数是凸函数，当且仅当其Hessian矩阵半正定。Hessian矩阵就是要求函数的所有二阶偏导数，因此我们考虑均方误差函数 $MSE$ 的二阶导。由于常数因子不影响函数的凸性，因此考虑函数

$f(\boldsymbol{w})=\|\boldsymbol{Xw}-\boldsymbol{y}\|^2$

根据之前有关正规方程的推导，函数 $f$ 的梯度为

$\nabla f=2\boldsymbol{X}^T\boldsymbol{Xw}-2\boldsymbol{X}^T\boldsymbol{y}$

Hessian矩阵就是梯度的梯度，因此

$\boldsymbol{H}=\nabla^2f=2\boldsymbol{X}^T\boldsymbol{X}\in\mathbb{R}^{(n+1)\times(n+1)}$

矩阵 $\boldsymbol{H}$ 是半正定的，当且仅当对于任意非零向量 $\boldsymbol{v}\in\mathbb{R}^{(n+1)}$ 都有

$\boldsymbol{v}^T\boldsymbol{Hv}\geqslant 0$

代入化简得到

$\boldsymbol{x}^T\boldsymbol{Hx}=2\|\boldsymbol{Xv}\|^2\geqslant 0$

这就证明了均方误差函数是一个凸函数，整个问题就是一个凸优化问题。

当 $\boldsymbol{X}$ 列满秩时，此时没有冗余特征。根据线性代数知识可知 $\boldsymbol{Xv}=\boldsymbol{0}$ 当且仅当 $\boldsymbol{v}=\boldsymbol{0}$ ，因此对于所有非零向量 $\boldsymbol{v}$ 都有 $\boldsymbol{v}^T\boldsymbol{Hv}>0$ ，此时Hessian矩阵正定。由于函数严格凸，只有一个全局最优解，于是这个解可以通过求解正规方程得到。
当 $\boldsymbol{X}$ 不满秩时，此时 $MSE$ 仍然是一个凸函数，但是有无穷个全局最优解，解不具有的唯一性。为了解决这个问题，我们通过 L2 正则化引入 $\lambda\boldsymbol{I}$ ，此时 $\boldsymbol{H}=2\boldsymbol{X}^T\boldsymbol{X}+\lambda\boldsymbol{I}$ 。此时不难证明 $\boldsymbol{H}$ 一定正定，于是重新保证了解的唯一性。

当引入 L2 正则项时，整个损失函数可以改写为

$L=MSE+\lambda\|\boldsymbol{w}\|^2$

我们不希望参数的范数过大，因此有等价的对偶优化问题

$\begin{aligned}\min_{\boldsymbol{x}}\quad & L=\frac{1}{2m}\|\boldsymbol{Xw}-\boldsymbol{y}\|^2+\lambda\|\boldsymbol{w}\|^2\\s.t.\quad &\|\boldsymbol{w}\|^2\leqslant r\in\mathbb{R}^{+}\end{aligned}$

分类CE Loss

交叉熵损失函数(CE Loss)常用于分类问题中，这是因为在分类问题中，均方误差函数往往是非凸的（证明略）。我们以二分类 Logistic 回归为例子，证明交叉熵损失函数可以把训练过程转化为一个凸优化问题。

假设有 $m$ 个样本和 $n$ 个特征量，第 $i$ 个样本的特征向量为 $\boldsymbol{x}^{(i)}$ ，标签为 $y^{(i)}\in\{0,1\}$ ，待求参数为权重 $\boldsymbol{w}\in\mathbb{R}^n$ 。此处假设偏置项 $b$ 已经通过齐次化融入 $\boldsymbol{x}^{(i)},\boldsymbol{w}$ ，则模型预测输出为

$\hat{y}^{(i)}=\mathrm{sigmoid}(\boldsymbol{w}^T\boldsymbol{x}^{(i)})=\frac{1}{1+\exp(-\boldsymbol{w}^T\boldsymbol{x}^{(i)})}$

定义二分类问题的交叉熵损失函数为

$CE=-\frac{1}{m}\sum_{i=1}^m\left[y^{(i)}\log\hat{y}^{(i)}+(1-y^{(i)})\log(1-\hat{y}^{(i)})\right]$

我们需要证明上述函数的Hessian矩阵半正定。设 $\sigma(\cdot)=\mathrm{sigmoid}(\cdot)$ ，其满足

$\dfrac{\partial \sigma}{\partial x}=\sigma(1-\sigma)$

省略常数项的新函数设为 $f$ ，在机器学习日志（四）中，我们曾推导出其梯度为

$\nabla f=\sum_{i=1}^m \big(\sigma(\boldsymbol{w}^T\boldsymbol{x}^{(i)})-y^{(i)}\big)\boldsymbol{x}^{(i)}$

对梯度再次求导，可以得到 Hessian 矩阵

$\begin{aligned} \boldsymbol{H}=\nabla^2 f&=\frac{\partial}{\partial \boldsymbol{w}}\left[\sum_{i=1}^m \big(\sigma(\boldsymbol{w}^T\boldsymbol{x}^{(i)})-y^{(i)}\big)\boldsymbol{x}^{(i)}\right]\\&=\sum_{i=1}^m \boldsymbol{x}^{(i)}\left[\nabla\sigma(\boldsymbol{w}^T\boldsymbol{x}^{(i)})\right]^T\\&=\sum_{i=1}^m \boldsymbol{x}^{(i)}\left[\sigma(\boldsymbol{w}^T\boldsymbol{x}^{(i)})\big(1-\sigma(\boldsymbol{w}^T\boldsymbol{x}^{(i)})\big)(\boldsymbol{x}^{(i)})^T\right]\\&=\sum_{i=1}^m \left[\sigma(\boldsymbol{w}^T\boldsymbol{x}^{(i)})\big(1-\sigma(\boldsymbol{w}^T\boldsymbol{x}^{(i)})\big)\right]\cdot\left[\boldsymbol{x}^{(i)}(\boldsymbol{x}^{(i)})^T\right]\\&=\sum_{i=1}^m k_i\cdot\left[\boldsymbol{x}^{(i)}(\boldsymbol{x}^{(i)})^T\right] \end{aligned}$

其中 $k_i=\sigma(\boldsymbol{w}^T\boldsymbol{x}^{(i)})\big(1-\sigma(\boldsymbol{w}^T\boldsymbol{x}^{(i)})\big)>0$ 是一个标量。对于任意非零向量 $\boldsymbol{v}\in\mathbb{R}^n$ 有

$\boldsymbol{v}^T\boldsymbol{Hv}=\sum_{i=1}^mk_i\cdot\boldsymbol{v}^T\boldsymbol{x^{(i)}}(\boldsymbol{x}^{(i)})^T\boldsymbol{v}=\sum_{i=1}^m k_i\cdot\|(\boldsymbol{x}^{(i)})^T\boldsymbol{v}\|\geqslant 0$

于是证明了交叉熵损失函数是一个凸函数。

在神经网络模型中，交叉熵损失函数不一定是凸函数。

SVM优化问题

模型表述

支持向量机SVM与感知机一样，可以用于解决二分类问题。在一个线性可分的问题中，有无数个可行的超平面。SVM在这无数个超平面中选择的是能最大化间隔的，而感知机算法的最后结果与初始值选择有关。

假设一共有 $m$ 个样本和 $n$ 个特征量，第 $i$ 个样本表示为 $(\boldsymbol{x}^{(i)},y^{(i)})$ ，并且 $y^{(i)}\in\{1,-1\}$ 分别表示正类和负类。在样本的特征空间中，我们可以找到一个 $n$ 维超平面

$f(\boldsymbol{w},b)=\boldsymbol{w}^T\boldsymbol{x}+b$

我们规定 $f(\boldsymbol{w},b)>0$ 时表示类别 $y=1$ ，反之表示 $y=-1$ 。构造表征量

$\gamma_i=y^{(i)}(\boldsymbol{w}^T\boldsymbol{x}^{(i)}+b)$

显然看出， $\gamma_i>0$ 当且仅当模型对第 $i$ 个样本分类正确。解析几何知识告诉我们，对于一个确定的超平面 $f=\boldsymbol{w}^T\boldsymbol{x}+b$ ，样本 $\boldsymbol{x}^{(i)}$ 到其的距离可以表示为

$d_i=\frac{|\boldsymbol{w}^T\boldsymbol{x}^{(i)}+b|}{\|\boldsymbol{w}\|}$

硬间隔SVM

当数据集是线性可分的时候，我们可以得到如下优化目标

$\begin{aligned}\max_{\boldsymbol{w},b}\min_{i}\quad & d_i=\frac{|\boldsymbol{w}^T\boldsymbol{x}^{(i)}+b|}{\|\boldsymbol{w}\|}\\s.t.\quad & \gamma_i>0,\quad i=1,2\cdots,m\end{aligned}$

我们可以这样理解原问题

内层的 $\min\limits_{i}$ 表示对所有 $d_i$ 遍历，找到距离平面 $f=\boldsymbol{w}^T\boldsymbol{x}+b$ 最小的距离
外层的 $\max\limits_{\boldsymbol{w},b}$ 表示对所有参数 $\boldsymbol{w},b$ 遍历，使得 $\min\limits_{i}d_i$ 最大

为了简化约束条件，我们考虑如下等价转换

$\begin{aligned} &\exist \boldsymbol{w},b,&\quad s.t.\quad \forall i,\gamma_i>0\\\Leftrightarrow&\exist \boldsymbol{w},b,c&\quad s.t.\quad \forall i,\gamma_i\geqslant c,c>0\\\Leftrightarrow&\exist \boldsymbol{w},b,c,d&\quad s.t.\quad \forall i,d\gamma_i\geqslant cd=1\\\Leftrightarrow&\exist \boldsymbol{w},b,d&\quad s.t.\quad \forall i,y^{(i)}\big((d\boldsymbol{w})^T\boldsymbol{x}^{(i)}+(db)\big)\geqslant 1\\\Leftrightarrow&\exist \boldsymbol{w},b,&\quad s.t.\quad \forall i,\gamma_i\geqslant 1\\ \end{aligned}$

最后一步使用了超平面的参数放缩性。

同样利用超平面的参数放缩性，令 $\min\limits_{i} y^{(i)}(\boldsymbol{w}^T\boldsymbol{x}^{(i)}+b)=1$ 。这表示此时找到的平面处于一个平衡的位置，到两个类别的最近距离都为 $r=\dfrac{|\boldsymbol{w}^T\boldsymbol{x}^{(i)}+b|}{\|\boldsymbol{w}\|}=\dfrac{1}{\|\boldsymbol{w}\|}$ ，因此有 $\min\limits_{i} d_i=\dfrac{1}{\|\boldsymbol{w}\|}$ ，即等价优化问题

$\begin{aligned}\max_{\boldsymbol{w},b}\quad&\frac{2}{\|\boldsymbol{w}\|}\\s.t.\quad & \gamma_i\geqslant 1,\quad i=1,2\cdots,m\end{aligned}$

因为优化目标参数在分母，等价的有

$\begin{aligned}\min_{\boldsymbol{w},b}\quad& \frac12\boldsymbol{w}^T\boldsymbol{w}\\s.t.\quad & 1-\gamma_i\leqslant 0,\quad i=1,2\cdots,m\end{aligned}$

定义拉格朗日函数

$L(\boldsymbol{w},b;\{\boldsymbol{\lambda}\})=\frac{1}{2}\boldsymbol{w}^T\boldsymbol{w}+\sum_{i=1}^m \lambda_i(1-\gamma_i)$

因此原问题的对偶问题为

$\begin{aligned}\max_{\boldsymbol{\lambda}}\inf_{\boldsymbol{w},b}\quad& L(\boldsymbol{w},b;\{\boldsymbol{\lambda}\})\\s.t.\quad & \lambda_i\geqslant 0,\quad i=1,2\cdots,m\end{aligned}$

可以证明这个问题具有强对偶性，因此考虑求解对偶问题。列出 KKT 条件为

$\begin{aligned}\nabla_{\lambda}L&=\boldsymbol{0}\\\frac{\partial L}{\partial b}&=0\\1-\gamma_i&\leqslant 0,\quad i=1,2\cdots,m\\\lambda_j&\geqslant 0,\quad j=1,2\cdots,m\\\lambda_i(1-\gamma_i)&=0,\quad j=1,2\cdots,m\end{aligned}$

解梯度条件，可知最优解 $\boldsymbol{w}^*,b^*,\boldsymbol{\lambda}^*$ 满足

$\begin{cases} \boldsymbol{w}^*=\displaystyle\sum_{i=1}^m \lambda_i^{*}\boldsymbol{x}^{(i)}y^{(i)}\\ \displaystyle\sum_{i=1}^m \lambda_i^{*}y^{(i)}=0 \end{cases}$

代入原问题，有

$\begin{aligned}\inf_{\boldsymbol{w},b} L&=\frac{1}{2}\left(\sum_{i=1}^m \lambda_i^{*}\boldsymbol{x}^{(i)}y^{(i)}\right)^T\left(\sum_{j=1}^m \lambda_j^{*}\boldsymbol{x}^{(j)}y^{(j)}\right)+\sum_{i=1}^m \lambda_i^*\\&-\sum_{i=1}^m\left(\lambda_i^*y^{(i)}\left[\sum_{j=1}^m \lambda_j^{*}\boldsymbol{x}^{(j)}y^{(j)}\right]\boldsymbol{x}^{(i)}\right)-b\sum_{i=1}^m \lambda_i^*y^{(i)}\\&=-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \lambda_i^*\lambda_j^*y^{(i)}y^{(j)}(\boldsymbol{x}^{(i)})^T\boldsymbol{x}^{(j)}+\sum_{i=1}^m \lambda_i^*\end{aligned}$

因此，把对偶问题改写为一个更简单的形式

$\begin{aligned}\max_{\boldsymbol{\lambda}}\quad& -\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \lambda_i\lambda_jy^{(i)}y^{(j)}(\boldsymbol{x}^{(i)})^T\boldsymbol{x}^{(j)}+\sum_{i=1}^m \lambda_i\\s.t.\quad &\sum_{i=1}^m \lambda_iy^{(i)}=0\\ &\lambda_i\geqslant 0,\quad i=1,2\cdots,m\end{aligned}$

这个关于 $\boldsymbol{\lambda}$ 的约束优化问题是比较容易求的，是一个二次型凸优化形式。一般而言，我们采用 SMO 迭代法求最优解 $\boldsymbol{\lambda}^*$ 。SMO 的主要思想是随机固定 $m-2$ 个 $\lambda_k$ 不变，剩下两个变元 $\lambda_i,\lambda_j$ 由于等式约束，可以看做一个单变量二次函数优化问题。重复多次之后理应得到一组解满足所有的 KTT 条件，从而就是我们要找的解。

假设我们求得了 $\boldsymbol{\lambda}^*$ ，代入 $\boldsymbol{w}^*$ 的表达式可以求得 $\boldsymbol{w}^*$ 。由于 KKT 条件中有约束

$\begin{aligned}1-\gamma_i&\leqslant 0,\quad i=1,2\cdots,m\\\lambda_j&\geqslant 0,\quad j=1,2\cdots,m\\\lambda_i(1-\gamma_i)&=0,\quad j=1,2\cdots,m\end{aligned}$

当 $\lambda^*_i=0$ 时必然有 $1-\gamma_i<0$ ，这时候对应的 $\boldsymbol{x}^{(i)}$ 一定不是距离超平面距离最近的点，因为之前假设过 $\min\limits_{i} \gamma_i=1$ 。反之，对于某个 $\lambda^*_j\neq 0$ ，其对应的 $\boldsymbol{x}^{(j)}$ 一定是距离超平面距离最近的点，而这样的点至少有两个，称之为支持向量(Support Vector)，因此有

$\gamma_j=y^{(j)}\big((\boldsymbol{w}^*)^T\boldsymbol{x}^{(j)}+b^*\big)=1$

解得参数

$b^*=\frac{1}{y^{(j)}}-(\boldsymbol{w}^*)^T\boldsymbol{x}^{(j)},\quad s.t.\quad \lambda^*_j=1$

软间隔SVM

当数据集不再线性可分时，我们可以考虑对数据进行升维操作。数学上可以证明，越高维度的数据集一般是越容易线性可分的。而我们把原数据集映射为一个高维度的线性可分集时，就可以使用硬间隔SVM的优化方法了。

注意到，在硬间隔SVM的对偶问题中，有求内积操作 $(\boldsymbol{x}^{(i)})^T\boldsymbol{x}^{(j)}$ ，当升维之后，这个内积计算复杂度会大大增加。因此我们考虑核函数映射以简化运算，其定义如下。

设映射 $K:\mathbb{R}^m\times\mathbb{R}^m\to\mathbb{R}$ ，如果存在一个映射 $\phi:\mathbb{R}^m\to\mathbb{R}^n(m<n)$ ，使得对于任意 $\boldsymbol{x,y}\in\mathbb{R}^m$ 都有 $K(\boldsymbol{x,y})=\big(\phi(\boldsymbol{x})\big)^T\phi(\boldsymbol{y})$ ，则称 $K$ 是一个核函数或者核映射。一般而言，核函数 $K$ 的充要判定条件为

对称性： $K(\boldsymbol{x,y})=K(\boldsymbol{y,x})$
Gram 矩阵的正定性

我们不再详细说明核函数的更多性质。在机器学习篇中，我们接触了一种很常见的核函数，即高斯核。对于若干个给定的点 $\boldsymbol{l}^{(i)}$ ，其对应的高斯核函数为

$f_i=K(\boldsymbol{x},\boldsymbol{l}^{(i)})=\exp\left(-\frac{\|\boldsymbol{x}-\boldsymbol{l}^{(i)}\|}{2\sigma^2}\right),\quad \sigma^2\text{ is a hyperparameter}$

若要把 $n$ 维特征空间升维到 $N$ 维空间时，可以选取 $N$ 个点 $\boldsymbol{l}^{(i)}$

同时考虑到模型的容错空间，我们可以定义松弛变量 $\xi_i\geqslant 0$ ，并改变约束条件为

$\gamma_i=y^{(i)}\big((\boldsymbol{w})^T\boldsymbol{x}^{(i)}+b\big)\geqslant1-\xi_i$

由于这个松弛 $\xi_i$ 不能很大，否则模型就有了很大的误差范围，因此添加惩罚项

$\begin{aligned}\min_{\boldsymbol{w},b}\quad& \frac12\boldsymbol{w}^T\boldsymbol{w}+C\sum_{i=1}^m\xi_i \\s.t.\quad & \gamma_i\geqslant 1-\xi_i,\quad i=1,2\cdots,m\\ &\xi_i\geqslant 0,\quad i=1,2,\cdots,m\end{aligned}$