線性分類函數

• 分類問題的兩種決策方法：

  • 概率方法：通過計算后驗概率進行分類。優點是在概率分布已知的情況下可以得到最優解，缺點是實際中概率密度通常未知，需要通過大量數據估計。
  • 判別方法：假設判別函數的形式已知，通過訓練樣本估計判別函數的參數。優點是實現簡單，缺點是需要假設函數的形式，可能不適合復雜數據。

• 線性判別函數定義為：
  $$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?{\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$$
    則線性可分性的問題就變成了：
    $$?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?g({\mathbf{x}}_i)]$
    • $J(\mathbf{w},b)=?{\sum }_{i=1}^n{\omega }_i?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)+?f(x{)}^{?}\Delta x+\underset{\text{高階小量}}{\underbrace{o(\Vert \Delta x\Vert )}}$$
  如果我們取：
  $$\Delta x=?\eta ?f(x)$$
  代入得：
  $$f(x+\Delta x)\approx f(x)?\eta ?f(x{)}^{?}?f(x)=f(x)?\eta \Vert ?f(x){\Vert }^2$$
  由于 $\eta >0$，且 $\Vert ?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 ?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}}^{?}$，使得 $f(\mathbf{x})$ 最小，也就是 $?f(\mathbf{x})=0$。

  • 思路

    在高維情況下，我們可以使用 泰勒二階展開式 來近似 $f(\mathbf{x}+\Delta \mathbf{x})$：
    $$f(\mathbf{x}+\Delta \mathbf{x})\approx f(\mathbf{x})+?f(\mathbf{x}{)}^T\Delta \mathbf{x}+\frac{1}{2}\Delta {\mathbf{x}}^{T}H(\mathbf{x})\Delta \mathbf{x}$$
    其中：

    • $?f(\mathbf{x})$：一階導數（梯度向量）
    • $H(\mathbf{x})$：二階導數矩陣（Hessian矩陣）

  • 目標：讓這個函數值最小！

    我們對上面的展開式求導，令導數為 0（為什么？一個函數在某點取得極小值（或極大值），該點的導數為零（如果導數存在）），有：
    $$?f(\mathbf{x})+H(\mathbf{x})\Delta \mathbf{x}=0?\Delta \mathbf{x}=?H(\mathbf{x}{)}^{?1}?f(\mathbf{x})$$
    于是就得到 牛頓法的多維更新公式：
    $${\mathbf{x}}_{k+1}={\mathbf{x}}_k?H^{?1}({\mathbf{x}}_k)?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})+?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})+?f(\mathbf{x}{)}^T\Delta \mathbf{x}$$

    然后讓 $\Delta \mathbf{x}=?\eta ?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”經常做不到或不現實，原因如下：

  • 函數可能沒有解析解
    很多現實問題的目標函數形式太復雜，根本找不到 $?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 ?f(x)$$

  只用一階導數，沿著負梯度走，小步慢慢試探。

  • 牛頓法（Newton’s Method）：

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

  不僅看梯度，還用 Hessian（H）矩陣調整方向和步幅。

  數學上，牛頓法是這樣構造的：

  • 近似 $f(x)$ 為一個二次函數（拋物面）：

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

  • 找這個二次函數的極小值點。
  • 解出最佳 $\Delta x$：

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

  所以牛頓法每次直接跳到局部拋物線的最低點方向，而不是慢慢沿斜坡滑。

  

• 比較梯度下降與牛頓法：

  • 牛頓法每一步通常比簡單的梯度下降法帶來更大的改進，即使梯度下降使用了最優步長 ${\eta }_k$。
  • 但是，如果 Hessian 矩陣 $Q$ 是奇異的（singular），那么牛頓法不可用。
  • 即使 Hessian $Q$ 是非奇異的，計算它也是很耗時的，時間復雜度是 $O(d^3)$。
  • 實際上，給梯度下降法設一個常數步長（即使比最優步長小一點），通常總開銷比每次都精確尋找最優 ${\eta }_k$ 更低。