线性分类函数

• 分类问题的两种决策方法：

  • 概率方法：通过计算后验概率进行分类。优点是在概率分布已知的情况下可以得到最优解，缺点是实际中概率密度通常未知，需要通过大量数据估计。
  • 判别方法：假设判别函数的形式已知，通过训练样本估计判别函数的参数。优点是实现简单，缺点是需要假设函数的形式，可能不适合复杂数据。

• 线性判别函数定义为：
  $$g_i(\mathbf{x})={\mathbf{w}}_i^T\mathbf{x}+w_{i0}$$

  • 易于计算，分析，学习
  • 通过最小化损失函数来学习
  • 需要数据线性可分
  • 训练误差小不能保证测试误差小

• 线性判别函数的决策面推导：

  • 决策面定义：$ g(\mathbf{x}) = 0 $，即： ${\mathbf{w}}^T\mathbf{x}+w_0=0$

    推导： $g(\mathbf{x})={\mathbf{w}}^T\mathbf{x}+\frac{{\mathbf{w}}^T\mathbf{w}}{\Vert \mathbf{w}{\Vert }^2}{w}_0=0$

    ${\mathbf{w}}^T\left(\mathbf{x}+\frac{w_0}{\Vert \mathbf{w}{\Vert }^2}\mathbf{w}\right)=0$

    • w 是超平面的法向量，决定其方向。
    • $\frac{w_0}{\Vert \mathbf{w}{\Vert }^2}\mathbf{w}$表示超平面相对于原点的偏移。

• 增广向量

  我们希望把这个线性函数写成没有显式偏置项的形式：
  $$g(\mathbf{x})={\mathbf{w}}^T\mathbf{x}+w_0\Rightarrow {\mathbf{a}}^T\mathbf{y}$$
  为此，引入两个新的概念：

  1. 增广样本向量（augmented vector）：
     $$\mathbf{y}=\left[\begin{array}{c}\mathbf{x}\\ 1\end{array}\right]\in {\mathbb{R}}^{d+1}$$
     —— 就是在原向量 $\mathbf{x}$ 后面补一个 1。

  2. 增广权重向量：
     $$\mathbf{a}=\left[\begin{array}{c}\mathbf{w}\\ w_0\end{array}\right]\in {\mathbb{R}}^{d+1}$$

  于是有：
  $$g(\mathbf{x})={\mathbf{w}}^T\mathbf{x}+w_0={\mathbf{a}}^T\mathbf{y}$$
  这样就把原来有偏置项的表达式转换成了一个 统一的向量内积形式。

• 线性可分的形式化定义

  • 给定样本集合 $y_1,y_2,\dots ,y_n$，部分标记为 ${\omega }_1$，部分为 ${\omega }_2$。

    如果存在一个向量 $a$，使得：

    • $a^T{y}_i>0$，当 $y_i$ 属于 ${\omega }_1$
    • $a^T{y}_i<0$，当 $y_i$ 属于 ${\omega }_2$

• 权重空间的解区域

  • 若将类别 ${\omega }_2$ 的样本统一变号，即：
    $$y_i\leftarrow -y_i,\text{当 }{y}_i\in {\omega }_2$$
    则线性可分性的问题就变成了：
    $$\forall i,a^T{y}_i>0$$
    即，所有样本点在向量 $a$ 的方向上都有正投影。

  • 如果所有样本 $y_i^{T}a>0$，那么这些 $a$ 向量就构成了解空间。

  • PPT 上给出了缩小解空间的一种方式：引入“边界”（margin），要求 $y_i^{T}a>b_i$，而不是只是大于0。这里 $b_i>0$，常用形式是 $b_i=\frac{1}{\Vert a\Vert }$，即边界和法向量成反比。

• 准则函数

  • 衡量错误或者代价

  • 目标是最小化它的值

  • 转化为函数优化问题

  • 感知机的准则函数举例：

    • $J(\mathbf{w},b)=-{\sum }_{i=1}^n\text{sign}[{\omega }_i\cdot g({\mathbf{x}}_i)]$
    • $J(\mathbf{w},b)=-{\sum }_{i=1}^n{\omega }_i\cdot g({\mathbf{x}}_i)$
    • $J(\mathbf{w},b)={\sum }_{i=1}^n(g({\mathbf{x}}_i)-{\omega }_i{)}^2$

    ${\omega }_i\in -1,+1$ 是样本 $x_i$ 的真实标签。

梯度下降算法

想象需要优化的函数是一座山，沿着下山方向下山

• 根据泰勒公式展开：
  $$f(x+\Delta x)\approx f(x)+\nabla f(x{)}^{\top }\Delta x+\underset{\text{高阶小量}}{\underbrace{o(\Vert \Delta x\Vert )}}$$
  如果我们取：
  $$\Delta x=-\eta \nabla f(x)$$
  代入得：
  $$f(x+\Delta x)\approx f(x)-\eta \nabla f(x{)}^{\top }\nabla f(x)=f(x)-\eta \Vert \nabla f(x){\Vert }^2$$
  由于 $\eta >0$，且 $\Vert \nabla f(x){\Vert }^2\ge 0$，所以有：
  $$f(x+\Delta x)\le f(x)$$

• 梯度下降的迭代流程：

  1. 初始化 $x_0$；

  2. 设置学习率 $\eta >0$ 和收敛阈值 $ϵ$；

  3. 重复执行：
     $$x_{k+1}=x_k-\eta \nabla f(x_k)$$
     直到梯度的模很小（即差不多到最低点）。

  学习率太大→跳跃，太小→收敛慢。

牛顿法

• 先从一维开始（找方程的根）

  目标：解一个方程：$f(x)=0$。我们想找一个 $x$，使得函数在该点为 0。

  • 基本思路

    1. 从一个初始点 $x_0$ 出发；
    2. 用函数的切线来逼近根；
    3. 一步步更新 $x_1,x_2,x_3,\dots$，越来越接近真解。

  • 数学推导（重点）

    • 给定当前点 $x_k$，在该点做一个切线（用一阶泰勒展开）：

    $$f(x)\approx f(x_k)+f^{\prime }(x_k)(x-x_k)$$

    • 我们希望 $f(x)=0$，代入这个近似式：

    $$f(x_k)+f^{\prime }(x_k)(x-x_k)=0$$

    解得：
    $$x=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$$
    这就是 牛顿法的一维更新公式：
    $$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$$
    

• 多维扩展（用于优化）

  当我们不再是解方程，而是要 最小化一个函数 $f(\mathbf{x})$：
  目标：$\min f(\mathbf{x})$
  我们要找一个点 ${\mathbf{x}}^{\ast }$，使得 $f(\mathbf{x})$ 最小，也就是 $\nabla f(\mathbf{x})=0$。

  • 思路

    在高维情况下，我们可以使用 泰勒二阶展开式 来近似 $f(\mathbf{x}+\Delta \mathbf{x})$：
    $$f(\mathbf{x}+\Delta \mathbf{x})\approx f(\mathbf{x})+\nabla f(\mathbf{x}{)}^T\Delta \mathbf{x}+\frac{1}{2}\Delta {\mathbf{x}}^{T}H(\mathbf{x})\Delta \mathbf{x}$$
    其中：

    • $\nabla f(\mathbf{x})$：一阶导数（梯度向量）
    • $H(\mathbf{x})$：二阶导数矩阵（Hessian矩阵）

  • 目标：让这个函数值最小！

    我们对上面的展开式求导，令导数为 0（为什么？一个函数在某点取得极小值（或极大值），该点的导数为零（如果导数存在）），有：
    $$\nabla f(\mathbf{x})+H(\mathbf{x})\Delta \mathbf{x}=0\Rightarrow \Delta \mathbf{x}=-H(\mathbf{x}{)}^{-1}\nabla f(\mathbf{x})$$
    于是就得到 牛顿法的多维更新公式：
    $${\mathbf{x}}_{k+1}={\mathbf{x}}_k-H^{-1}({\mathbf{x}}_k)\nabla f({\mathbf{x}}_k)$$

• 为什么一维只展开一阶项，多维要展开到二阶项？多维可以只展开一项吗？或者展开更多项？

  因为在做什么问题！

  • 一维时：

    我们只是想找根（即 $f(x)=0$）
    所以我们只需要一阶导数的切线逼近：
    $$f(x)\approx f(x_k)+f^{\prime }(x_k)(x-x_k)$$
    设这个近似函数等于0即可。

  • 多维优化时：

    我们要找极小值，不只是找根。

    这时一阶导数并不能判断拐点类型（极大？极小？拐点？），必须引入二阶信息（曲率）：
    $$f(\mathbf{x}+\Delta \mathbf{x})\approx f(\mathbf{x})+\nabla f(\mathbf{x}{)}^T\Delta \mathbf{x}+\frac{1}{2}\Delta {\mathbf{x}}^{T}H\Delta \mathbf{x}$$

    • 第一项：函数值
    • 第二项：梯度，方向信息
    • 第三项：Hessian，曲率信息

  • 为什么需要二阶项？

    • 如果你只看一阶项，相当于只看斜率，不知道是山顶还是山谷；
    • 二阶项（Hessian）告诉你，函数在这一点的“凹凸”：
      • Hessian 正定 → 函数局部向上开口 → 极小值 ✅
      • Hessian 负定 → 极大值 ❌
      • Hessian 不定 → 鞍点 ❗️

  • 多维可以只展开一项：这就是梯度下降法！

    • 它忽略了二阶信息，只用了：

    $$f(\mathbf{x}+\Delta \mathbf{x})\approx f(\mathbf{x})+\nabla f(\mathbf{x}{)}^T\Delta \mathbf{x}$$

    然后让 $\Delta \mathbf{x}=-\eta \nabla f(\mathbf{x})$，即反方向下降。

    但这会导致收敛慢、不稳定。

  • 也可以展开更多项，但通常没必要。

    • 泰勒展开可以无限展开高阶项：

    $$f(x)=f(x_0)+f^{\prime }(x_0)(x-x_0)+\frac{1}{2}{f}^{\prime \prime }(x_0)(x-x_0{)}^2+\frac{1}{6}{f}^{\prime \prime \prime }(x_0)(x-x_0{)}^3+\dots$$

    • 但高阶导数计算极其复杂；
    • 通常二阶展开就能在极小值附近拟合得很好（函数形状如碗口）；
    • 这就是牛顿法停止在二阶的原因。

• 既然目标是找极小值点，为什么不能直接对原函数求导，令导数等于0？（解析法）

  如果函数 $f(x)$ 是光滑可导的，我们当然可以直接求导并令导数为0，找到所谓的极值点（极小值或极大值）。但在实际应用中，“直接求导=0”经常做不到或不现实，原因如下：

  • 函数可能没有解析解
    很多现实问题的目标函数形式太复杂，根本找不到 $\nabla f(x)=0$ 的显式解，比如：

    • 函数包含 非线性嵌套结构，如： $f(x)=\log (1+e^{-(Ax+b{)}^2})$
    • 参数是 高维张量（如深度学习模型中的几百万维参数）

    此时我们只能数值优化，从一个起始点出发逐步更新参数靠近最优点。

  • 即使可以求导，也可能解不出来
    举个例子：
    $$f(x)=x^5-3x+1$$
    对它求导是简单的：
    $$f^{\prime }(x)=5x^4-3$$
    你能显式求出解吗？不能。我们只能用牛顿法或者二分法来数值逼近根。

  • 优化法能处理约束问题
    现实中很多问题还有 约束条件：
    $$\min f(x)\text{subject to }Ax\le b$$
    这时候直接对 $f(x)$ 求导=0 是无效的，你还需要引入拉格朗日乘子等技巧，或者干脆使用优化算法如：

    • 投影梯度法
    • 拉格朗日乘子法
    • 对偶法
    • 内点法、罚函数法、SLP 等等

  • 优化方法适合自动化处理
    在现代机器学习和工程中，我们希望：

    • 用程序自动优化复杂函数
    • 不依赖人工推导
    • 能处理几十万参数的模型（如深度学习）

    这时优化方法（如SGD、Adam、LBFGS）显然比“手动解导数方程”更加实用。

• 牛顿下降方向为何更陡？

  牛顿法的下降方向更陡，是因为它不仅利用了梯度的方向，还根据 Hessian（即二阶导数信息）自适应地调整了步长和方向，使下降速度沿着最快变小的路径。

  • 梯度下降（Gradient Descent）：

  $$\Delta x=-\eta \nabla f(x)$$

  只用一阶导数，沿着负梯度走，小步慢慢试探。

  • 牛顿法（Newton’s Method）：

  $$\Delta x=-H^{-1}\nabla f(x)$$

  不仅看梯度，还用 Hessian（H）矩阵调整方向和步幅。

  数学上，牛顿法是这样构造的：

  • 近似 $f(x)$ 为一个二次函数（抛物面）：

  $$f(x+\Delta x)\approx f(x)+\nabla f(x{)}^T\Delta x+\frac{1}{2}\Delta x^{T}H\Delta x$$

  • 找这个二次函数的极小值点。
  • 解出最佳 $\Delta x$：

  $$H\Delta x=-\nabla f(x)\Rightarrow \Delta x=-H^{-1}\nabla f(x)$$

  所以牛顿法每次直接跳到局部抛物线的最低点方向，而不是慢慢沿斜坡滑。

  

• 比较梯度下降与牛顿法：

  • 牛顿法每一步通常比简单的梯度下降法带来更大的改进，即使梯度下降使用了最优步长 ${\eta }_k$。
  • 但是，如果 Hessian 矩阵 $Q$ 是奇异的（singular），那么牛顿法不可用。
  • 即使 Hessian $Q$ 是非奇异的，计算它也是很耗时的，时间复杂度是 $O(d^3)$。
  • 实际上，给梯度下降法设一个常数步长（即使比最优步长小一点），通常总开销比每次都精确寻找最优 ${\eta }_k$ 更低。