Maximum Margin 为了使分类面更合适 为了减少误分次数 最大化几何间隔 max→min‖l‖
Maximum Margin • 为了使分类面更合适 • 为了减少误分次数 • 最大化几何间隔 27
minimize w 是否让W=0,目标函数就最小了呢?=。= ·式子有还有一些限制条件,完整的写下来,应 该是这样的 mins‖ws:,y(wx+b)≥1,=1,…,n 求最小值的问题就是一个优化问题,一个带约束的 次规划( quadratic programming,QP)问题,是一个 凸问题 凸二次规划区别于一般意义上的规划问题,它有解 而且是全局最优的解,而且可以找到
minimize ||w|| • 是否让W=0，目标函数就最小了呢？ =。= • 式子有还有一些限制条件，完整的写下来，应 该是这样的 – 求最小值的问题就是一个优化问题，一个带约束的 二次规划(quadratic programming, QP)问题，是一个 凸问题 – 凸二次规划区别于一般意义上的规划问题，它有解 而且是全局最优的解，而且可以找到 28
如何解二次规划问题 等式约束,是求极值、拉格朗日转化等方法转 化为无约束问题 不等式约束的问题怎么办? 方法一:用现成的QP( Quadratic Programming)优化 包进行求解(效率低) 方法二:求解与原问题等价的对偶问题(dual problem)得到原始问题的最优解(更易求解、可以推 广到核函数 拉格朗日乘子法 拉格朗日对偶性 KT理论支撑
如何解二次规划问题 • 等式约束，是求极值、拉格朗日转化等方法转 化为无约束问题 • 不等式约束的问题怎么办？ – 方法一：用现成的QP (Quadratic Programming) 优化 包进行求解(效率低) – 方法二：求解与原问题等价的对偶问题(dual problem)得到原始问题的最优解(更易求解、可以推 广到核函数) • 拉格朗日乘子法 • 拉格朗日对偶性 • KKT理论支撑 29
求解步骤 转化为对偶问题 对偶转化&KKT条件 求解wb极小化 拉格朗日乘子极值 ·求解α极大化 用SMo算法求解α乘子
求解步骤 • 转化为对偶问题 – 对偶转化 & KKT条件 • 求解wb极小化 – 拉格朗日乘子极值 • 求解α极大化 – 用SMO算法求解α乘子 30
1、对偶问题的转化 m0070 subject to yili)+b-120(i=1, 2, 3,..., 给每一个约束条件加上一个拉格朗日乘子( Lagrange multiplier),定义拉 格朗日函数 C(c)=21o2-((02+)-1) 根据对偶算法与KKT条件约束,这个问题可以从 min (w)=min max C(u, b, a)=p u,bai≥0 转化为 max min L(u, b, a=d' a;≥0t,b 而KT条件就是指上面最优化数学模型的标准形式中的最小点x*必须满足下面的条件: 其中p*和d*等价条件就是KKT条件* 1.b(x)=0.=1…P,g1(x)≤0.k=1-q Vf(x)+∑4V(x)+∑Vg(x)=0 ,≠0,从20,A8(x.)=
• 1、对偶问题的转化 • 给每一个约束条件加上一个拉格朗日乘子（Lagrange multiplier），定义拉 格朗日函数 • 根据对偶算法与KKT条件约束，这个问题可以从 • 转化为 • 其中 p*和d*等价条件就是KKT条件* 31