✏️
LiHang-TongJiXueXiFangFa
  • Introduction
  • 第2章 感知机 - 原始形式
    • 学习策略的推导
    • 梯度下降法的算法过程
    • 梯度下降法的推导过程
    • 梯度下降法的收敛证明
  • 第2章 感知机 - 对偶形式
    • 学习模型的推导
    • 梯度下降法的算法过程
    • 梯度下降法的推导过程
  • 第3章 k近邻算法
    • 模型三要素
    • 构造平衡kd树
    • 用kd树的k近邻搜索
    • kd树的原理与改进
  • 第4章 朴素贝叶斯
    • 模型公式的推导
    • 策略公式的推导
    • 最大似然估计算法过程
    • 贝叶斯估计算法过程
  • 第5章 决策树
    • 决策树的模型
    • 信息增益的算法
    • ID3决策树的生成算法
    • C4.5决策树的生成算法
    • 决策树的剪枝算法
  • 第5章 CART决策树
    • CART树的生成
    • CART树的剪枝
  • 第6章 逻辑回归
    • 二分类逻辑回归模型
    • 多分类逻辑回归模型
  • 第6章 最大熵模型
    • 最大熵的原理
    • 最大熵模型的定义
    • 最大熵的学习过程
    • 根据最大熵的学习过程推导最大熵模型
    • 证明:对偶函数的极大化=模型的极大似然估计
  • 第6章 目标函数最优化问题
    • 改进的迭代尺度法(IIS)
    • IIS算法公式(1)推导
    • A和B的推导
    • 拟牛顿法
  • 第7章 支持向量机
    • 函数间隔与几何间隔
  • 第7章 线性可分SVM
    • 凸二次规划问题推导
    • 支持向量
    • 凸二次规划问题求解
    • 原始问题转换为对偶最优化问题
  • 第7章 线性SVM
    • 原始问题转换为对偶最优化问题
    • 根据 a 求 w 和 b*
    • 支持向量
  • 第7章 非线性SVM
    • 核函数与核技巧
    • 核技巧在SVM中的应用
    • 7.3.2 正定核
    • 常用的核函数
  • 第7章 序列最小最优化算法
    • 选择变量
    • 推导1
    • 推导2
    • 推导3
    • 推导4
    • 推导5:update b
  • 第8章 adaboost
    • 算法过程
    • 训练误差分析
    • 加法模型
    • 前向分步算法
    • adaboost一种特殊的加法模型
  • 第8章 提升树
    • 回归问题提升树的推导
    • 回归问题提升树前向分步算法
    • 一般决策问题梯度提升算法
  • 第9章 EM算法
    • 算法过程
    • Q函数的推导
    • 关于算法的收敛性
    • 高斯混合模型参数估计的EM算法
    • Q函数推导
    • 推导2
  • 第10章 隐马尔可夫模型
    • 定义
    • 概率计算问题 - 直接计算法
    • 概率计算问题 - 前向算法
    • 概率计算问题 - 后向算法
    • 学习问题 - 监督学习
    • 学习问题 - 非监督学习
    • Baum - Welch算法推导
    • 推导1
    • 预测问题 - 近似算法
    • 预测问题 - 维特比算法
    • 维特比算法推导过程
  • 第11章 条件随机场
    • 概率无向图模型
  • 遗留问题
Powered by GitBook
On this page

Was this helpful?

  1. 第7章 序列最小最优化算法

推导1

Previous选择变量Next推导2

Last updated 5 years ago

Was this helpful?

L(a1,a2)=∑i=1N∑j=1NaiajyiyjK(xi,xj)−∑i=1Nai1\begin{aligned} L(a_1, a_2) = \sum_{i=1}^N\sum_{j=1}^Na_ia_jy_iy_jK(x_i, x_j) - \sum_{i=1}^Na_i && {1} \end{aligned}L(a1​,a2​)=i=1∑N​j=1∑N​ai​aj​yi​yj​K(xi​,xj​)−i=1∑N​ai​​​1​

为了简化公式,令:

f(i,j)=aiajyiyjK(xi,xj)2\begin{aligned} f(i, j) = a_ia_jy_iy_jK(x_i,x_j) && {2} \end{aligned}f(i,j)=ai​aj​yi​yj​K(xi​,xj​)​​2​

公式(1)简化为:

L(a1,a2)=∑i=1N∑j=1Nf(i,j)−∑i=1Nai3\begin{aligned} L(a_1, a_2) = \sum_{i=1}^N\sum_{j=1}^Nf(i,j) - \sum_{i=1}^Na_i && {3} \end{aligned}L(a1​,a2​)=i=1∑N​j=1∑N​f(i,j)−i=1∑N​ai​​​3​

在公式(3)中,将a1a_1a1​、a2a_2a2​是变量,其它参数a是常量,把公式(3)分成包含变量的部分和常量部分:

L(a1,a2)=f(1,1)+f(1,2)+∑j=3Nf(1,j)+f(2,1)+f(2,2)+∑j=3Nf(2,j)+∑i=3Nf(i,1)+∑i=3Nf(i,2)++∑i=3N∑j=3Nf(i,j)−a1−a2−∑i=3Nai4\begin{aligned} L(a_1, a_2) = f(1,1)+f(1,2)+\sum_{j=3}^Nf(1,j) \\ +f(2,1)+f(2,2)+\sum_{j=3}^Nf(2,j) \\ +\sum_{i=3}^Nf(i,1)+\sum_{i=3}^Nf(i,2) + +\sum_{i=3}^N\sum_{j=3}^Nf(i,j) \\ -a_1 - a_2 - \sum_{i=3}^Na_i && {4} \end{aligned}L(a1​,a2​)=f(1,1)+f(1,2)+j=3∑N​f(1,j)+f(2,1)+f(2,2)+j=3∑N​f(2,j)+i=3∑N​f(i,1)+i=3∑N​f(i,2)++i=3∑N​j=3∑N​f(i,j)−a1​−a2​−i=3∑N​ai​​​4​

要L(a_1, a_2)对a_1和a_2求导,公式(4)中的常数部分对求导结果不影响,直接合并为一个不需要关心具体内容的常数项,得:

根据f(i,j)的定义可知,f具有对称性,得:

L(a1,a2)=f(1,1)+f(1,2)+∑j=3Nf(1,j)+f(2,1)+f(2,2)+∑j=3Nf(2,j)+∑i=3Nf(i,1)+∑i=3Nf(i,2)−a1−a2+常数项5\begin{aligned} L(a_1, a_2) = f(1,1)+f(1,2)+\sum_{j=3}^Nf(1,j) \\ +f(2,1)+f(2,2)+\sum_{j=3}^Nf(2,j) \\ +\sum_{i=3}^Nf(i,1)+\sum_{i=3}^Nf(i,2) \\ -a_1 - a_2 + \text{常数项}&& {5} \end{aligned}L(a1​,a2​)=f(1,1)+f(1,2)+j=3∑N​f(1,j)+f(2,1)+f(2,2)+j=3∑N​f(2,j)+i=3∑N​f(i,1)+i=3∑N​f(i,2)−a1​−a2​+常数项​​5​
L(a1,a2)=f(1,1)+2f(1,2)+f(2,2)+2∑j=3Nf(1,j)+2∑j=3Nf(2,j)−a1−a2+常数项6\begin{aligned} L(a_1, a_2) = f(1,1)+2f(1,2)+f(2,2) \\ +2\sum_{j=3}^Nf(1,j) +2\sum_{j=3}^Nf(2,j) \\ -a_1 - a_2 + \text{常数项}&& {6} \end{aligned}L(a1​,a2​)=f(1,1)+2f(1,2)+f(2,2)+2j=3∑N​f(1,j)+2j=3∑N​f(2,j)−a1​−a2​+常数项​​6​