基于支撐向量機(jī)的收斂問(wèn)題研究

摘要:在文章中提出了一種基于支持向量機(jī)思想的對(duì)任意距離空間求解最大分類間隔的方法，其優(yōu)化問(wèn)題可以用輸入空間的距離來(lái)表示。首先將輸入空間等距嵌入到Hilbert空間，在線性的Hilbert空間對(duì)優(yōu)化問(wèn)題進(jìn)行線性處理，但是這種方法只適用于特定的距離空間。在原方案的基礎(chǔ)上擴(kuò)展研究了對(duì)任意距離空間求解最大分類間隔的方法。

關(guān)鍵詞:距離空間;分類間隔;凸集;核函數(shù)

Study on Metric Spaces Based on Support Vector Machine

XIE Shu-xin

(Hunan Railway Professional Technology College， Zhuzhou 412001， China)

Abstract: This paper proposed a maximal margin classification method based on support vector machine(SVM) for arbitrary metric spaces. The optimization problem can be written in terms of the metric of the input space. Firstly we isometrically embedded the input space into a Hilbert space where we can solve the problem with linear method. However， this method is limited to special metric spaces. According to the scheme developed for SVM we provide a generalization of maximum margin principle to arbitrary metric space.

Key words: metric space; margin; convex hull; kernel

距離空間(度量空間)是一種拓樸空間。對(duì)于距離空間(?字，ρ)，X是一個(gè)非空集，ρ叫做?字上的一個(gè)距離。通常SVM問(wèn)題都是以核函數(shù)k作為研究對(duì)象，其分類結(jié)果與k的選擇有關(guān)。由于分類間隔在幾何上等于兩個(gè)互不相交凸集間的距離，在此將距離作為研究對(duì)象。但并非任何情況都線性可分，這時(shí)可考慮將原空間等距嵌入線性空間。一方面，使得輸入空間的距離大小在嵌入后保持不變;另一方面，可以對(duì)問(wèn)題進(jìn)行線性處理。首先在Hilbert空間上用ρ表示該優(yōu)化問(wèn)題，但這必須在-ρ2條件正定的條件下進(jìn)行。因此我們研究了能夠適用于任意距離空間的距離分析方法，就是將任意距離空間等距嵌入到Banach空間，在線性的Banach空間用計(jì)算兩凸集間距離的方法求最大分類間隔。

1 分類超平面與分類間隔

考慮線性可分的情況，分類超平面在泛函分析中的解釋是:Hahn-Banach凸集分離定理。設(shè)E1和E2是Banach空間中兩個(gè)互不相交的非空凸集，E1有內(nèi)點(diǎn)，那么?堝S∈R及非零線性連續(xù)泛函g，使得超平面Hfs分離E1和E2，即存在一個(gè)非零線性泛函g，使得

g(x)≤s(?坌x∈E1) (1)

g(x)≥s(?坌x∈E2)(2)

根據(jù)(1)、(2)定義嚴(yán)格的分類函數(shù)為符號(hào)函數(shù):f(x)=sgn[g(x)-s]

對(duì)應(yīng)SVM問(wèn)題[1]的分類函數(shù): ■ (3)

規(guī)范形式的超平面分類間隔大小為■，即在約束條件yi(w·x+b) ≥1下求‖w‖2的最小值。在此不是如何求分類函數(shù)中參數(shù)的具體值，而是采用距離空間的研究方法，用ρ來(lái)表示該優(yōu)化問(wèn)題。接下來(lái)根據(jù)RKHS理論來(lái)說(shuō)明通常的SVM方法。

2 在Hilbert空間求解最大分類間隔

2.1 基于RKHS理論的SVM方法

根據(jù)正定函數(shù)與條件正定函數(shù)的概念可知正定函數(shù)一定是條件正定的。通過(guò)正定核函數(shù)來(lái)建立基于RKHS理論的希爾伯特空間H，其方法如下:

1) 定義特征映射?準(zhǔn):

?字→R，x→?準(zhǔn)x=k(x，·);

2) 在特征空間定義有界線性算子f，f為?準(zhǔn)x的線性組合，即■;

3) 定義內(nèi)積為=k(x，y);

范數(shù)■;

4) 建立完備的內(nèi)積空間即Hilbert空間H。

根據(jù)以上定義，將SVM方法描述如下:輸入空間?字通過(guò)函數(shù)?準(zhǔn)映射到Hilbert空間H，在H空間確定最優(yōu)分類面。Riesz定理指出，任意一個(gè)線性連續(xù)函數(shù)都對(duì)應(yīng)Hilbert空間的一個(gè)向量。最優(yōu)分類面則對(duì)應(yīng)Hilbert空間上的線性連續(xù)函數(shù)。而分類間隔大小等于與分類超平面最近且平行的樣本點(diǎn)到分類面距離的2倍。

給定訓(xùn)練樣本集(xi，yi)，i=1，2…n x∈?字，yi∈{+1，-1}，最大分類間隔的優(yōu)化問(wèn)題可寫成如下形式:

■

約束條件:

■， ai≥0，i=1，2…n

其中分類面法向量■

2.2 用距離空間(?字，ρ)做輸入空間

通常我們對(duì)SVM問(wèn)題的求解按以下步驟進(jìn)行:■

即都是通過(guò)核函數(shù)k將原空間轉(zhuǎn)換到Hilbert空間。這一部分在集合?字上定義ρ，將距離空間(?字，ρ)作為輸入空間等距嵌入Hilbert空間: ■

根據(jù)RKHS理論，可以寫出在集合?字上距離的定義:ρ(x，y)=||?準(zhǔn)x-?準(zhǔn)y||(4)

下面的命題給出了用核函數(shù)k構(gòu)造ρ的一種方法，也可以有不同的形式[3]。

命題1:設(shè)集合?字非空，k是?字 × ?字→R上的一個(gè)條件正定核函數(shù)，定義函數(shù)

■ (5)

則ρ是X上的一個(gè)距離且-ρ2是條件正定的。存在?字→R上的函數(shù)h，使得

■ (6)

證明:若k條件正定，由(6)得

■

上式中■，因此-ρ2條件正定。

令■(x，y)-k(x，x0)-k(x0，y)+k(x0，x0) (7)

■正定當(dāng)且僅當(dāng)k條件正定[3]。

由于 ■(x，x)+■(y，y)-2■(x，y)= k(x，x)+ k(y，y)-2k(x，y)

因此對(duì)公式(5)，■和k定義了相同的ρ且

K(x，y)=■(x，y)+1/2[k(x，x) -■(x，x)+(k(y，y)-■(y，y)) ]，?字→R上的函數(shù)h可定義為

h(·)=1/2 [k(·，·)-■(·，·)]

下面將生成的距離空間等距嵌入到Hilbert空間。

命題2:設(shè)(?字，ρ)是命題1定義的距離空間

1) (?字，ρ)能夠等距嵌入到Hilbert空間H;

2) 若核函數(shù)k有界，則H能連續(xù)嵌入到空間(Cb(?字)，||·||∞)。Cb(?字)，代表集合?字上有界連續(xù)函數(shù)的全體。

證明:由命題1證明中的(7)式，可以通過(guò)條件正定核函數(shù)k得到正定核函數(shù)■，由于兩者定義了相同的距離，故可用正定核函數(shù)■來(lái)建立基于RKHS理論的Hilbert空間H，其特征映射為?準(zhǔn)x=■(x，·)。若k有界，則■有界。其連續(xù)性與ρ相關(guān)，由施瓦茲不等式

■

對(duì)任意的f∈H，■

所以f有界;又

|f(x)-f(y)|≤||f||H||?準(zhǔn)x-?準(zhǔn)y||=||f||Hρ(x，y)所以f連續(xù)。因此H能連續(xù)嵌入到空間 (Cb(?字)，||·||∞)。

Schoenberg已于1938年提出了正定函數(shù)與條件正定函數(shù)的概念并證明了以上結(jié)論[4]。可以得到以下定理:

定理1:距離空間(?字， ρ)等距嵌入到Hilbert空間的充分必要條件是-ρ2條件正定。

實(shí)際上該定理與命題1和命題2等價(jià)，可以描述為:在集合?字上定義一個(gè)條件正定核函數(shù)就相當(dāng)于通過(guò)(5)式在?字上定義了唯一的ρ;另一方面，對(duì)于?字上的一個(gè)ρ，如果-ρ2條件正定，通過(guò)(6)和(7)式則定義了非唯一的正定核函數(shù)。因此可以將(?字，ρ)等距嵌入到基于RKHS理論的Hilbert空間。

2.3 用距離ρ表示SVM優(yōu)化問(wèn)題

由上可知，可將ρ作為研究對(duì)象代入原問(wèn)題。由(7)式定義了正定核函數(shù)■，通過(guò)映射?準(zhǔn)x=■(x，·)將其代入基于RKHS理論的Hilbert空間。因?yàn)榇嬖诩s束條件，所以化簡(jiǎn)后將(7)式中其余項(xiàng)略去，只留下條件正定核函數(shù)k，再將由k構(gòu)造的距離ρ代入，優(yōu)化問(wèn)題最后表示為ρ的函數(shù)。

定理2:SVM問(wèn)題可以通過(guò)距離空間(?字，ρ)來(lái)求解，其中-ρ2條件正定。通過(guò)正定核函數(shù)將(?字，ρ)等距嵌入到Hilbert空間。在線性Hilbert空間中兩類集合能夠線性分開(kāi)且使兩類間隔最大，間隔大小等于兩凸集間的距離，結(jié)果只與輸入ρ有關(guān)。

■

約束條件:■

分類函數(shù):■

證明:■

■

上式中■，j遍歷所有的aj>0

可以直接構(gòu)造這樣的ρ，使-ρ2條件正定。雖然結(jié)果的表示只與ρ有關(guān)，但通過(guò)條件正定核函數(shù)k來(lái)構(gòu)造ρ更容易。

3 在Banach空間求解最大分類間隔

由于只有在-ρ2條件正定時(shí)才能將輸入空間(?字，ρ)等距嵌入到Hilbert空間，故上面的方法只適用于距離空間的一個(gè)子集。下面討論如何對(duì)任意距離空間求解。基本想法是將任意距離空間等距嵌入到Banach空間，再根據(jù)分類間隔大小等于兩凸集間的距離求解。即

■

上式中S是?字上的一個(gè)Banach空間，它是有界連續(xù)函數(shù)全體的一個(gè)子集。

3.1 將任意距離空間等距嵌入Banach空間

建立兩個(gè)Banach空間.將距離空間(?字，ρ)等距嵌入到第一個(gè)Banach空間，第二個(gè)Banach空間用來(lái)定義線性連續(xù)函數(shù).設(shè)(?字，ρ)是緊空間(此處為便于分析使用緊空間，在有限集上研究時(shí)緊集與非緊集效果近似，所以下面的討論可忽略該假設(shè))，任取x0∈?字，定義映射:

?準(zhǔn):?字→R，x→?準(zhǔn)x=ρ(x，·)- ρ(x0，·)

ψ:?字→R，x→ψx=ρ(·，x)- ρ(x0，x)

令S=span{?準(zhǔn)x:x∈?字}，即S為?字上關(guān)于映射?準(zhǔn)的線性包;T=span{ψx:x∈?字}，即T為τ上關(guān)于映射ψ的線性包。集合S的閉包S是一個(gè)Banach空間，在S中定義范數(shù)■。距離空間(?字，ρ)通過(guò)映射?準(zhǔn)等距嵌入到空間S，S的對(duì)偶空間S'與集合T的閉包T等距同構(gòu)，因此可認(rèn)為S'與T等價(jià)。又定義范數(shù):

■

對(duì)以上內(nèi)容做一總結(jié):

引理1 ?準(zhǔn)是距離空間(?字，ρ)到Banach空間(S，||·||∞)?奐(Cb(?字)，||·||∞)的等距映射。

證明:根據(jù)在S中范數(shù)的定義

■

?準(zhǔn)x有界，并且

|?準(zhǔn)x(y)- ?準(zhǔn)x(y')|≤|ρ(x，y)-ρ(x，y')|+|ρ(x0，y)-ρ(x0，y')| ≤2ρ(y，y')

?準(zhǔn)x連續(xù)，因此?準(zhǔn)x∈Cb(?字)

又||?準(zhǔn)x-?準(zhǔn)y||=||ρ(x，·)- ρ(y，·)|| ≤ρ(x，y)

所以?準(zhǔn)是(?字，ρ)到(S，||·||∞)連續(xù)的等距映射，其中x0映射到S空間的原點(diǎn)。(S，||·||∞)是空間(Cb(?字)，||·||∞)的一個(gè)子集且S完備。

引理2 ||·||T是定義在T上的一個(gè)范數(shù)

證明:顯然||·||T滿足三角不等式和齊次性，且||t||T≥0。下來(lái)驗(yàn)證||t||T =0?圳t=0，充分性是顯然的;必要性:取t∈T，且||t||T=0則存在序列In、βi，n、xi，n使得■且當(dāng)n→∞，有■，因此對(duì)任意的x∈?字，

■

上式兩邊取極限n→∞，得t=0

定理3:空間(T， ||·||T)與空間(S'， ||·||S')等距同構(gòu)。

其中S'是S的對(duì)偶空間，證明參見(jiàn)文獻(xiàn)[5]的定理3.9.

3.2 在Banach空間求解兩凸集間的距離

在Banach空間兩個(gè)互不相交凸集間的距離大小等于最大分類間隔[2]。定義凸集如下:

■

定理4:設(shè)E1和E2是Banach空間B中兩個(gè)有限集合，若co(E1)∩co(E2)= ?準(zhǔn)，則

■

將上式取倒數(shù)轉(zhuǎn)換上確界為下確界來(lái)求解:

■，約束條件:

■;

令■

得到標(biāo)準(zhǔn)形式:■，(8)

約束條件:yi(w'(xi)+b)≥1， ?坌xi∈E

3.3 將距離ρ代入優(yōu)化問(wèn)題

根據(jù)(8)式，在任意距離空間求解最大分類間隔的優(yōu)化問(wèn)題表示為:■

約束條件:yj(w'(?準(zhǔn)xj)+b) ≥1，?坌xj∈E

由于S'與T等距同構(gòu)，因此可以把兩者視為等價(jià)集合。又T在T中稠密且范數(shù)連續(xù)，將上式做一變換，用T上的下確界來(lái)表示T的最小值:■，

約束條件:■

為便于計(jì)算，將問(wèn)題放在T的有限維子空間研究。設(shè)有限集Z?奐?字且Z的維數(shù)為m，根據(jù)定理4的平移不變性，任取一點(diǎn)x0，令x0=z1，z1∈Z。得到:

■，約束條件:■

通常取Z=E，由于■與j無(wú)關(guān)，將該項(xiàng)與常數(shù)項(xiàng)b合并為c:

■，約束條件:■

分類函數(shù):■

以上優(yōu)化問(wèn)題可用線性方法解決，如果我們令Z=E，將得到和文獻(xiàn)[7]相同的結(jié)論。

根據(jù)定理4，寫出原問(wèn)題的對(duì)偶形式:■

約束條件:■

由于αi與βi之間的關(guān)系無(wú)確定公式，故還不能直接通過(guò)αi來(lái)計(jì)算分類函數(shù)。原問(wèn)題可以在有限集Z上得到近似結(jié)果，同樣在對(duì)偶問(wèn)題中也可以在Z上計(jì)算上確界。

4 結(jié)論與討論

在文章中給出了通過(guò)距離空間求解最大分類間隔的方法。將距離空間等距嵌入到Hilbert空間只限于特定的距離空間。ρ的構(gòu)造有多種形式，如何根據(jù)具體數(shù)據(jù)構(gòu)造一個(gè)適當(dāng)?shù)摩焉袩o(wú)通用準(zhǔn)則。更一般的，將任意距離空間等距嵌入到Banach空間的方法好于文獻(xiàn)[7]中的距離分類方法，但它與前一種方法的數(shù)學(xué)結(jié)構(gòu)之間的聯(lián)系，以及兩種方法的推廣能力如何還有待研究，另外，由于受篇幅的限制，該算法的源代碼在此沒(méi)有給出。

參考文獻(xiàn):

[1] 邊肇祺，張學(xué)工.模式識(shí)別[M].2版.北京:清華大學(xué)出版社，2000.

[2] Bennett K P，Bredensteiner E J.Dualityand Geometry in SVM classifiers[C].Proceedings of the Seventeenth International Conference on Machine Learning，2000:57-64.

[3] Berg C，Cristensen J P R，Ressel P.Harmonic Analysis on Semigroups[M].New York:Springer Verlag，1984.

[4] Scholkopf B.The Kernel Trick for Distanances[C].Neural Information Processing Systems(NIPS)，13，2000.

[5] Rudin W.Functional Analysis[M].McGraw Hill，1991.

[6] Graepel T，Herbrich R，Scholkopf B，et al.Classification on proximity Data with LP-machines[C].Internation Conference on Artificial Neural networks，1999:304-309.

[7] Pekalska E，Paclik P，Duin R P W.A Generalized Kernel Approach to Dissimilarity based Classification[J].Journal of Machine Learning Research，2001(2):175-211.