支持向量机二-拉格朗日对偶问题5篇

第一篇：支持向量机二-拉格朗日对偶问题

支持向量机SVM---拉格朗日乘子 一

参考文档

周志华《机器学习》 郑洁的 《机器学习》 李航 《统计学习方法》

一

前言

通过上一章，我们得到SVM求解的问题

那如何根据输入的训练参数 获得w, b 呢，这里通过拉格朗日对偶问题求解这个问题，并给出算法推导过程

二

拉格朗日对偶问题

上面的问题，可以通过拉格朗日对偶变换，找到更有效的求解方案

式1

L对w, b分别求偏导数

式2 把 式2带入式一可得到

四

求解问题简化

上面当a = 0 的时候，f(x)为无效，a>0 的时候，yif(Xi)-1 =0 必定是一个支持向量机

五 分类器函数

六

例子

如图上，A,B, C三点通过拉格朗日对偶问题求出答案 Step 1 KKT 条件

第二篇：SVM拉格朗日对偶问题——最优间隔分类器

最优间隔分类器（optimal margin classifier）

重新回到SVM的优化问题：

我们将约束条件改写为：

从KKT条件得知只有函数间隔是1（离超平面最近的点）的线性约束式前面的系数，也就是说这些约束式，对于其他的不在线上的点（），极值不会在他们所在的范围内取得，因此前面的系数本。

看下面的图：

.注意每一个约束式实际就是一个训练样

实线是最大间隔超平面，假设×号的是正例，圆圈的是负例。在虚线上的点就是函数间隔是1的点，那么他们前面的系数造拉格朗日函数如下：，其他点都是

。这三个点称作支持向量。构 注意到这里只有没有是因为原问题中没有等式约束，只有不等式约束。

下面我们按照对偶问题的求解步骤来一步步进行，首先求解的最小值，对于固定的，的最小值只与w和b有关。对w和b分别求偏导数。

并得到

将上式带回到拉格朗日函数中得到，此时得到的是该函数的最小值（目标函数是凸函数）

代入后，化简过程如下：

最后得到

由于最后一项是0，因此简化为

这里我们将向量内积

表示为

此时的拉格朗日函数只包含了变量。然而我们求出了才能得到w和b。

接着是极大化的过程，前面提到过对偶问题和原问题满足的几个条件，首先由于目标函数和线性约束都是凸函数，而且这里不存在等式约束h。存在w使得对于所有的i，使得是原问题的解，是对偶问题的解。在这里，求就是求

。因此，一定存在了。

如果求出了，根据即可求出w（也是，原问题的解）。然后

即可求出b。即离超平面最近的正的函数间隔要等于离超平面最近的负的函数间隔。

关于上面的对偶问题如何求解，将留给下一篇中的SMO算法来阐明。

这里考虑另外一个问题，由于前面求解中得到

我们通篇考虑问题的出发点是，根据求解得到的，我们代入前式得到

也就是说，以前新来的要分类的样本首先根据w和b做一次线性运算，然后看求的结果是大于0还是小于0,来判断正例还是负例。现在有了，我们不需要求出w，只需将新来的样本和训练数据中的所有样本做内积和即可。那有人会说，与前面所有的样本都做运算是不是太耗时了？其实不然，我们从KKT条件中得到，只有支持向量的，其他情况。因此，我们只需求新来的样本和支持向量的内积，然后运算即可。这种写法为下面要提到的核函数（kernel）做了很好的铺垫。这是上篇，先写这么多了。

第三篇：拉格朗日插值多项式与泰勒多项式的误差分析详全文

i.拉格朗日插值多項

ii.式與泰勒多項式的誤差分析 iii.朱亮儒 曾政清 陳昭地 iv.國立臺灣師範大學數學系教授 v.臺北市立建國高級中學數學教師 vi.vii.摘要：本文旨於提供拉格朗日插值多項式與泰勒多項式誤差項估計值的初等簡易證明，並探討其應用價值。

viii.關鍵字：拉格朗日插值多項式、泰勒多項式、誤差項 ix.一 引言

x.有鑑於教育部99普通高級中學數學課綱在第一冊多項式的運算為迴避解三元一次方程組，首次出現插值多項式及其應用(以不超過三次插值多項式為限)（[1][2][3]），99數學課綱包含插值多項式部分如下： xi.求

xii.f(x)2x5x6x3

xiii.ab(x1)c(x1)(x2)d(x1)(x2)(x3)xiv.中的a, b, c, d.32☆★

★

☆

★xv.f(x)除以(xa)(xb)的餘式為通過a,f(a),b,f(b)的插值多項式。

xvi.若f有a,b兩實根，則f可寫成f(x)q(x)(xa)(xb)的型式。xvii.透過因式定理證明插值多項式的唯一性。xviii.設通過(1,1),(2,3),(3,7)的多項式為

1f(x)ab(x1)c(x1)(x2)，求a,b,c及f.2xix.插值多項式：通過(11,3),(12,5),(13,8)的多項式可表示為 xx.f(x)3，(x12)(x13)(x11)(x13)(x11)(x12)58(1112)(1113)(1211)(1213)(1311)(1312)xxi.求f(11.5)的值。

xxii.此處暫不處理下面的題型：「設通過(1, 1),(2, 3),(3, 7)的多項式為f(x)abxcx2,求a,b,c。」此類題型將在數學的IV的聯立方程組章節中處理。

xxiii.此處自然而然讓人想到拉格朗日(Lagrange, J.L., 1736-1816)其人奇事，羅列如下：

xxiv.他出生於義大利西北部的杜林(Turin)，從小就極有數學天分，於18歲開始撰寫數學論文，在數論上曾提出一個著名的定理：「任意正整數都可以表成四個平方數的和」。

xxv.他是第一位證明均值定理(The Mean Value Theorem)的大數學家。(均值定理在高三選修甲微分的單元中會學到（[4]），它是僅次於微積分基本定理的極重要的存在定理)xxvi.他在30歲時，應腓特烈二世的邀請到柏林作為其宮廷數學大師長達20年之久。xxvii.之後接受法國的邀請，到巴黎擔任法國科學院院士，拿破崙（1769-1821, 1804-1815擔任法皇）讚譽他為「數學科學的巍峨金字塔」

xxviii.泰勒定理有拉格朗日誤差的公式（存在性）。xxix.拉格朗日恆等式：

2nn2n21nxxx.aibiaibiajbkakbj，i1i1i12j,k12xxxi.ab2a222bab，xxxii.abcdacbdadbc.xxxiii.具有附加條件的多變數實函數極值拉格朗日乘子定理。xxxiv.最得意的巨著《分析力學》。

xxxv.拉格朗日差值誤差公式（[5]）：若x1,x2,,xn,xn1為[a,b]區間中相異實數，且fCn1[a,b],則對每一個x[a,b]，存在c(x)(a,b),使得

xxxvi.f(x)P(x)Rn(x), xxxvii.其中P(x)為函數f(x)在x1, x2, , xn, xn1的n階拉格朗日插值多項

f(n1)c(x)xxxviii.式，而Rn(x)(xx1)(xx2)(xxn1)為其插值誤差式。

(n1)!3 xxxix.美國早期數學家泰勒(Taylor, B, 1685-1731)在1715年出版的研究報告中，曾對多項式近似超越函數有精準的描述。當時他提出的泰勒級數展開式雖然符合時代的需求，但並未涉及收斂性的問題，有關餘式則是之後由拉格朗日所提供(稱為：拉格朗日餘式型)；而柯西(Cauchy, A.L., 1789-1857)在此之後又提供了兩個餘式型，分別稱為：柯西餘式型與柯西積分餘式型([6],[7],[8],[9])。本文即欲介紹這些餘式型誤差項的初等證明及一些相關應用。

xl.二 拉格朗日插值多項式誤差項估計 xli.首先，重述一遍定理：

xlii.定理1.〔拉格朗日插值多項式誤差估計〕([5])

n1xliii.設x1, x2, , xn1為區間[a,b]上的(n1)相異實數，fC[a,b](即f(n1)在[a,b]上連續)，則對每一x[a,b]，存在c(x)(a,b)使得

xliv.f(x)P(x)Rn(x)

xlv.其中P(x)為函數f在點x1,x2,,xn1的n階拉格朗日多項式，而

f(n1)c(x)xlvi.Rn(x)(xx1)(xx2)(xxn1)為插值多項式的誤差

(n1)!式。

xlvii.證明：當xxk時，f(xk)P(xk)，此時可任取c(x)(a,b)都成立。

xlviii.當xxk,k1, 2, , n, n1時，設g:[a, b]定義成

xlix.g(t)f(t)P(t)f(x)P(x)4

(tx1)(tx2)(txn1)

(xx1)(xx2)(xxn1)則gCl.n1[a, b]，且g(x)g(xk)0,k1, 2, , n, n1，逐次利用Rolle定理知存在c(x)(a, b)使得g(n1)c(x)0。又對任意t(a, b)，g(n1)(t)f(n1)(t)P(n1)(t)f(x)P(x)

li.且P(n1)c(x)0，於是可得

(n1)!(xx1)(xx2)(xxn1)f(n1)c(x)lii.f(x)P(x)(xx1)(xx2)(xxn1)

(n1)!f(n1)c(x)liii.即Rn(x)(xx1)(xx2)(xxn1)。

(n1)!liv.由定理1可以得到下面的推論： lv.推論1-1：

lvi.(1)當fCn1[a, b]時，f(n1)(t)在[a, b]上連續，故有一Mn1使

(n1)lvii.Mn1maxfatb(t)，故Rn(x)Mn1(xx1)(xx2)(xxn1)。

(n1)!lviii.(2)當f(x)一開始就是k次的多項式函數時，則對[a,b]內任一大於或等於 lix.k階以上的拉格朗日多項式就是函數f(x)本身。

lx.在數值分析中，拉格朗日插值多項式誤差公式具有關鍵性的角色。lxi.三 泰勒定理 lxii.利用完全平行於定理1的證明方法，我們可用來證明拉格朗日餘式型的泰勒定理，其定理與證法如下：

lxiii.定理2.〔泰勒定理(拉格朗日餘式型)〕：

lxiv.設x0(a, b)，fC得

n1[a, b]，則對每一x[a, b]存在c(x)(a,b)使lxv.f(x)Pn(x)Rn(x)，nlxvi.其中，Pn(x)k0f(k)(x0)(xx0)k為f(x)在x0點的n階泰勒多項式，k!f(n1)c(x)lxvii.Rn(x)(xx0)n1為f(x)用Pn(x)表示的誤差項。

(n1)!lxviii.證法(一)(完全平行於定理1)如下： 當xx時，可任取c(x)為(a,b)內的任一數都成立。lxix.○02 當xx時，設g(t):[a,b]定義成 lxx.○0(tx0)n1lxxi.g(t)f(t)P, n(t)f(x)Pn(x)n1(xx0)lxxii.則gCn1[a,b]且g(x)g(x0)g(x0)g(n)(x0)，lxxiii.逐次用Rolle定理知存在c(x)(a,b)使得g(n1)c(x)0。

lxxiv.又對任意t(a,b)，lxxv.g(n1)(t)f(n1)(t)Pn(n1)(t)f(x)Pn(x)6

(n1)!

(xx0)n1(n1)lxxvi.且Pc(x)0，於是可得 nf(n1)c(x)lxxvii.f(x)P(xx0)n1Rn(x)。n(x)(n1)!lxxviii.證法(二)([6][8])： lxxix.設實數Q滿足

lxxx.(xx0)n1f(x0)f(n)(x0)Qf(x)f(x0)(xx0)(xx0)n(n1)!1!n!

lxxxi.並設函數:[a,b]定義成

f(t)f(n)(t)Qlxxxii.(t)f(x)f(t)(xt)(xt)n(xt)n11!n!(n1)!

lxxxiii.依f,f,,f(n)之假設知:[a,b]為連續且在(a,b)內可微分，顯然(x)0且由實數Q之定義知(x0)0；於是由Rolle定理知x,x0之間有一c(x)使得c(x)0。但

f(t)f(n)(t)f(n)(t)n1lxxxiv.(t)f(t)f(t)(xt)(xt)(xt)n11!(n1)!(n1)!

f(n1)(t)QQf(n1)(t)nn(xt)(xt)(xt)n，lxxxv.n!n!n!7 lxxxvi.於是，由c(x)0得Qf(n1)c(x)，故知

f(n1)c(x)Rn(x)(xx0)n1，得證。

(n1)!lxxxvii.同樣地，由定理2我們可以得到如下的推論。lxxxviii.推論1-2：

lxxxix.(1)當fCn1[a,b]時，f(n1)(t)在[a,b]上連續，故有一Mn1使

Mn1n1xx0。

(n1)!xc.Mn1maxfatb(n1)(t)，故Rn(x)(n1)xci.(2)當f(x)是k次的多項式時，由f(x)0,x(a,b)，故知f(x)的

xcii.任一大於或等於k階的泰勒多項式就是函數f(x)本身。xciii.定理2.可用來證明下列的冪級數表示超越函數的漂亮結果：

xnxciv.(1)e,x

n0n!x(1)n2n1xcv.(2)sinxx,x

(2n1)!n0(1)n2nxcvi.(3)cosx1x,x

(2n)!n1xcvii.定理3〔泰勒定理（柯西餘式型）〕：

xcviii.設x0(a,b),fCn1[a,b]，則對每一x[a,b]存在01使得

xcix.f(x)Pn(x)Rn(x)，c.其中，Pn(x)k0nf(k)(x0)(xx0)k為f(x)在x0點的n階泰勒多項式，k!f(n1)(1)x0x(xx0)n1為誤差項 ci.Rn(x)(1)n!ncii.證明：（底下的證明完全平行於定理2的證法(二)）ciii.設實數q滿足

(xx0)f(x0)f(n)(x0)civ.qf(x)f(x0)(xx0)(xx0)nn!1!n!，cv.並設函數:[a,b]定義成

f(t)f(n)(t)qcvi.(t)f(x)f(t)(xt)(xt)n(xt)，1!n!n!cvii.則:[a,b]為連續且在(a,b)內可微分。

cviii.顯然(x)0，且由實數q之定義知(x0)0，於是由Rolle定理知

cix.x,x0之間有一c(x)(1)x0x(01)使得c(x)0。

f(t)f(n)(t)cx.但(t)f(t)f(t)(xt)(xt)n1

1!(n1)!cxi.f(n)(t)f(n1)(t)qqf(n1)(t)(xt)nn1n(xt)(xt).(n1)!n!n!n!cxii.於是，由c(x)0得

cxiii.qf(n1)c(x)xc(x)nnf(n1)1x0x1xx0，nnf(n1)(1)x0x(xx0)n1，得證。cxiv.故知Rn(x)(1)n!cxv.定理4〔泰勒定理(柯西積分餘式型)〕

cxvi.設x0(a,b),fCn1[a,b]，則對每一x[a,b]

cxvii.f(x)Pn(x)Rn(x)

………(＊)

cxviii.其中，Rn(x)1x(n1)nf(t)(xt)dt x0n!cxix.證明：利用微積分基本定理，xcxx.f(x)f(x0)f(t)dtx0

cxxi.再由分部積分法，得

xxcxxii.x0f(t)dtf(t)x0d(xt)dtdt

xcxxiii.f(t)(xt)x0xx0f(t)(xt)dt

cxxiv.f(x0)(xx0)xx0f(t)(xt)dt.cxxv.故知n1時，公式(＊)成立。

cxxvi.利用數學歸納法，設1kn1,(＊)在nk成立，而

1x(k1)kf(t)(xt)dtx0cxxvii.k!

1x(k1)dt

f(t)(xt)k1cxxviii.(k1)!x010 cxxix.x11(k2)k1f(k1)(x0)(xx0)k1f(t)(xt)dt x0(k1)!(k1)!cxxx.於是(＊)在nk1時亦成立，得證。cxxxi.事實上，由定理4之

1x(n1)Rn(x)f(t)(xt)ndtn!x0cxxxii.cxxxiii.利用連續函數f(n1)(t)(xt)n之積分均值定理知有一(0,1)使得

cxxxiv. xx0f(n1)(t)(xt)dtfn(n1)(1)x0xx(1)x0xn(xx)0f(n1)(1)x0xxx0cxxxv.n11n。

(1)nf(n1)(1)x0xcxxxvi.即Rn(x)(xx0)n1，故知定理3的「柯

n!西餘式型的泰勒定理」為「柯西積分餘式型」的直接結果。甚至，再利用下面的引理(一般化的積分均值定理)：

cxxxvii.引理：

cxxxviii.設g,h:[a,b]都是連續，且h(x)0對每一x[a, b]，則存在一點c(a,b)使得

bbcxxxix.ah(x)g(x)dxg(c)h(x)dx.acxl.可推得拉格朗日餘式型的泰勒氏定理(不妨設xx0)：

1x(n1)(t)(xt)ndt cxli.Rn(x)fn!x011

x1(n1)fcxlii.c(x)x0(xt)ndt(x0c(x)x)n!cxliii.1(n1)fc(x)n!(xt)n1n1xx0

f(n1)c(x)cxliv.(xx0)n1.(n1)!cxlv.四 結論

cxlvi.本文最後主要的結論如下：

cxlvii.一、拉格朗日不但提供了他本身的插值多項式誤差項的初等令人深刻印象的證法，也同時解決了拉格朗日餘式型的泰勒多項式誤差項的公式，手法值得讚賞，並可輕易以多項式函數逼近超越函數。

cxlviii.二、拉格朗日餘式型的泰勒定理，可以推廣到多變數實函數的泰勒定理([7])。

cxlix.三、拉格朗日餘式型的泰勒定理有三種證法，而柯西餘式型的泰勒定理也有兩種

cl.證法，都是在寫這篇文章的意外收穫。

cli.四、柯西餘式型和柯西積分餘式型的泰勒定理，形式證明也都很初等，它對於牛頓的二項級數(1x)kx,1x1(為任意實數)的正確k0k性提供了拉格朗日餘式型無法單獨承擔的完整證明([6],[7],[8])。clii.在拉格朗日插值多項式被引入高中數學課綱([3])，加之以拉格朗日的均值定理([4])，甚至一般化的超廣義均值定理~拉格朗日餘式型泰勒定理也將是選修 cliii.微積分([2])必然會接觸到的問題。它提供了e,sinx,cosx等初等超越函數的泰勒級數表示，大大拓展了多項式微積分的應用範疇，值得學習。cliv.五 參考資料

clv.1.教育部(民98)。普通高級中學必修科目「數學」課程綱要。clvi.2.教育部(民98)。普通高級中學選修科目「數學」課程綱要。

clvii.3.李虎雄、陳昭地、朱亮儒等(民99)。普通高級中學數學第一冊，康熹文化事業股份有限公司出版。

clviii.4.李虎雄、陳昭地、朱亮儒等(民99)。高中選修數學(II)，康熹文化事業股份有限公司出版。

clix.5.朱亮儒、陳材河(民99年7月9日)，「99課程中的Lagrange插值多項式」電子報專刊，高中數學電子報第47期。

clx.6.陳昭地、顏啟麟(民67)。數學分析，汝旭圖書公司印行。

clxi.7.張幼賢、陳火炎、陳昭地(民100年4月)。二項級數之教學研究，教育部高中數學學科中心電子報54期，http://mathcenter.ck.tp.edu.tw clxii.8.Bartle, R.G.(1978).The elements of real analysis(2nd.Ed.)，中央圖書出版社代印行。

clxiii.9.Fitzpatrick, P.M.(1995), Advanced Calculus, PWS Publishing Company.clxiv.x13