ＳＶＭ在距離空間中的研究

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

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

1 引言

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

2 分類超平面與分類間隔

考慮線性可分的情況，分類超平面在泛函分析中的解釋如下：

Hahn-Banach凸集分離定理。設(shè)E 和E 是Banach空間中兩個互不相交的非空凸集，E 有內(nèi)點，那么?堝S∈R及非零線性連續(xù)泛函g，使得超平面H分離E 和E ，換句話說，存在一個非零線性泛函g，使得

規(guī)范形式的超平面分類間隔大小為 ，即在約束條件y (w·x+b)≥1下求‖w‖ 的最小值。在這里我們討論的不是如何求出分類函數(shù)中參數(shù)的具體值，而是采用距離空間的研究方法，用距離ρ來表示該優(yōu)化問題。接下來根據(jù)Reproducing Kernel Hilbert Space（RKHS）理論來說明通常的SVM方法。

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

3.1 基于RKHS理論的SVM方法

首先給出正定函數(shù)與條件正定函數(shù)的概念：

定義1：集合?掊×?掊上的實值函數(shù)k正定當(dāng)且僅當(dāng)k對稱且

顯然正定函數(shù)一定是條件正定的。通過正定核函數(shù)來建立基于RKHS理論的希爾伯特空間H，其方法如下：

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

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

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

根據(jù)以上定義，將SVM方法描述如下：輸入空間?掊通過函數(shù)?準(zhǔn)映射到Hilbert空間H，在H空間確定最優(yōu)分類面。Riesz定理指出，任意一個線性連續(xù)函數(shù)都對應(yīng)Hilbert空間的一個向量。最優(yōu)分類面則對應(yīng)著Hilbert空間上的線性連續(xù)函數(shù)。

3.2 用距離空間(?掊，ρ)做輸入空間

通常我們對SVM問題的求解按以下步驟進(jìn)行：

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

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

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

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

證明：若k條件正定，由(7)得

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

命題2：設(shè)（?掊，ρ）是命題1中定義的距離空間，

(1)（?掊，ρ）能夠等距嵌入到Hilbert空間H；

(2)若核函數(shù)k有界，則H能連續(xù)嵌入到空間（C (?掊)，‖·‖ ），C (?掊)代表集合?掊上有界連續(xù)函數(shù)的全體。

證明：由命題1證明中的(8)式，可以通過條件正定核函數(shù)k得到正定核函數(shù) ，由于兩者定義了相同的距離，所以可用正定核函數(shù) 來建立基于RKHS理論的Hilbert空間H，其特征映射為?準(zhǔn) = (x，·)。

對任意的f∈H，

Schoenberg已于1938年提出了正定函數(shù)與條件正定函數(shù)的概念并證明了以上結(jié)論［５］。我們不難得到以下定理：

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

3.3用距離ρ表示SVM優(yōu)化問題

根據(jù)前面的結(jié)論，我們可以嘗試將距離ρ作為研究對象代入原問題。由(8)式定義了正定核函數(shù) ，通過映射?準(zhǔn) = (x，·)將其代入基于RKHS理論的Hilbert空間。因為存在約束條件，所以化簡后將(8)式中其余項略去，只留下條件正定核函數(shù)k，再將由k構(gòu)造的距離ρ代入，優(yōu)化問題最后表示為距離ρ的函數(shù)。

定理2：SVM問題可以通過距離空間（?掊，ρ）來求解，其中-ρ 條件正定。通過正定核函數(shù)將（?掊，ρ）等距嵌入到Hilbert空間。問題結(jié)果只與輸入空間的距離ρ有關(guān)。

我們可以直接構(gòu)造這樣的距離ρ，使得-ρ 條件正定。雖然問題結(jié)果的表示只與距離ρ有關(guān)，但是通過條件正定核函數(shù)k來構(gòu)造ρ可能更容易些。

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

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

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

4.1將任意距離空間等距嵌入到Banach空間

建立兩個Banach空間。將距離空間（?掊，ρ）等距嵌入到第一個Banach空間，第二個Banach空間用來定義線性連續(xù)函數(shù)。設(shè)（?掊，ρ）是緊空間，任取x ∈?掊，定義映射：

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

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

在Banach空間兩個互不相交凸集間的距離大小等于最大分類間隔［３］。定義凸集如下：

為了便于計算，我們將問題放在T的有限維子空間研究。設(shè)有限集Z?奐?掊且Z的維數(shù)為m，根據(jù)定理4的平移不變性，任取一點x ，令x =z ，z ∈Z。得到|β |，約束條件：

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

根據(jù)定理4，我們寫出原問題的對偶形式：

由于a 于β 之間的關(guān)系沒有確定的公式，所以還不能直接通過a 來計算分類函數(shù)。原問題可以在有限集Z上得到近似結(jié)果，同樣我們在對偶問題中也可以在Z上計算上確界。

結(jié)論與討論

在這篇文章里我們給出了如何通過距離空間求解最大分類間隔的方法。將距離空間等距嵌入到Hilbert空間這只限于特定的距離空間。對于距離ρ的構(gòu)造可以有多種形式，在解決一個實際問題時，如何根據(jù)具體的數(shù)據(jù)構(gòu)造一個適當(dāng)?shù)木嚯xρ還沒有固定的準(zhǔn)則。更一般的，將任意距離空間等距嵌入到Banach空間的方法好于文獻(xiàn)中的距離分類方法，但它與前一種方法的數(shù)學(xué)結(jié)構(gòu)之間的聯(lián)系，以及兩種方法的推廣能力如何仍有待研究。

參考文獻(xiàn)：

［1］張恭慶，林源渠.泛函分析講義.北京：北京大學(xué)出版社，2001.

［2］邊肇祺，張學(xué)工等.模式識別（第2版）.北京：清華大學(xué)出版社，2000.

［3］K.P.Bennett，E.J.Bredensteiner，Dualityand Geometry in SVM classifiers， Proceedings of the Seventeenth International Conference on Machine Learning，2000，57-64.

［4］C.Berg，J.P.R.Cristensen，P.Ressel，Harmonic Analysis on Semigroups，Springer Verlag，New York，1984.

［5］B.Scholkopf，The Kernel Trick for Distanances，Neural Information Processing Systems(NIPS)，2000，13.

［6］W.Rudin，F(xiàn)unctional Analysis，McGraw Hill，1991.

［7］T.Graepel，R.Herbrich，B.Scholkopf，A.Smola，P.Bartlett，K.R.Muller，K.Obermayer and R.Williamson，Classification on proximity Data with LP-machines，Internation Conference on Artificial Neural Networks，1999，304-309.

［8］E.Pekalska，P.Paclik，R.P.W.Duin，A Generalized Kernel Approach to Dissimilarity based Classification，Journal of Machine Learning Research，2001，2，175-211.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文?！?/p>