← 返回刚才阅读的位置

知识卡片

结构图卡 · 9829.d · 生成模型:DeepSeek-V4.1-Flash

对偶解法让内积露出来

理解等级:高级

原始问题是”带 M 个不等式约束的凸二次规划”,直接解也可以,但对参数 w 的维度不友好:w 的维度等于特征维度,高维时变量极多。转成对偶问题后,待求量换成了 M 个拉格朗日乘子 α_i,规模只与样本数有关,还额外得到两个好处——更好解、能自然接上核函数。

推导路径(四步,不需要背):

  1. 写拉格朗日函数 L(w,b,α)=½‖w‖²−Σα_i[y_i(w·x_i+b)−1],α_i≥0。
  2. 对 w、b 求偏导并置零,得到两个关系:w=Σα_i y_i x_i,以及 Σα_i y_i=0。第一个式子说明最优 w 是样本的线性组合,第二个是后面必须保留的等式约束。
  3. 把这两个关系代回 L,w、b 消失,只剩 α。此时 L 的值变成 −½ΣΣα_iα_j y_i y_j(x_i·x_j)+Σα_i。
  4. 对 α 求极大,再改写成习惯的极小形式:

 min_α ½ΣΣα_iα_j y_i y_j(x_i·x_j) − Σα_i s.t. Σα_i y_i=0, α_i≥0

原问题凸且约束线性,对偶间隙为零,解出 α* 就等价于解出原问题;再由 w=Σα_i y_i x_i 回代得到 w*。

第二点最值得注意:整个对偶问题里,样本只以 x_i·x_j 的内积形式出现。这意味着模型不关心样本长什么样,只关心两两之间的相似度——于是把内积换成一个更一般的相似度函数(核函数)不会破坏任何推导结构。这是 [[核函数不用真的映射到高维]] 的全部前提。

求解 α 的那一步,原文点明”一般采用的是 SMO 算法”,细节见 [[SMO每次只调两个乘子]]。

结构图:

flowchart TD
    A[原始问题 min ½‖w‖²] --> B[构造拉格朗日函数 L]
    B --> C[对 w、b 求偏导置零]
    C --> D[w = Σαiyixi<br/>Σαiyi = 0]
    D --> E[回代 消去 w、b]
    E --> F[对偶问题 只含内积 xi·xj]
    F --> G[SMO 解出 α*]
    G --> H[回代得 w*、b*]
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《机器学习基础:从入门到求职》第8章《第8章 支持向量机》(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00011.html) - 结论依据:原文按"拉格朗日函数—求偏导—回代—对偶极大极小"的顺序推导,并明确指出对偶问题更易求解、结果为内积点乘从而为核函数提供基础。 - 原始内容:利用拉格朗日对偶性,通过求解对偶问题得到原始问题的最优解(对偶问题:更容易求解,且后面可自然引入核函数)……从上式可以发现,L(w,b,α)的结果居然只取决于(xi ∙xj ) ,即两向量的点乘结果(这为后面核函数的引入提供了基础)。