何文斌　劉群鋒　熊金志

(東莞理工學(xué)院計(jì)算機(jī)學(xué)院　廣東東莞　523808)

?

支持向量機(jī)多項(xiàng)式光滑函數(shù)的誤差理論研究

何文斌劉群鋒熊金志

(東莞理工學(xué)院計(jì)算機(jī)學(xué)院廣東東莞523808)

(hewb@dgut.edu.cn)

摘要光滑函數(shù)在光滑支持向量機(jī)的理論中起著重要作用.1996年Chen等人提出一個支持向量機(jī)的光滑函數(shù)——Sigmoid函數(shù)的積分函數(shù)，并解決了該光滑函數(shù)的誤差問題.2005～2009年，袁玉波、熊金志和劉葉青等人相繼提出支持向量機(jī)的無窮多個多項(xiàng)式光滑函數(shù)和多項(xiàng)式光滑的支持向量機(jī)模型，但都未解決這類多項(xiàng)式光滑函數(shù)的誤差函數(shù)問題.為此，用 Newton-Hermite 插值方法研究該問題.研究結(jié)果表明：1)用 Newton-Hermite 插值方法可計(jì)算這類光滑函數(shù)的誤差函數(shù)，并給出了具體算法；2)這類誤差函數(shù)有無窮多個，可用一個一般形式表示，并得到了這個一般形式；3)這類誤差函數(shù)具有許多重要性質(zhì)，并給出了嚴(yán)格證明.解決了支持向量機(jī)無窮多個多項(xiàng)式光滑函數(shù)的誤差函數(shù)及其性質(zhì)問題，建立了這類多項(xiàng)式光滑函數(shù)的誤差理論，為研究支持向量機(jī)的光滑理論提供了基本的理論支持.

關(guān)鍵詞支持向量機(jī)；Newton-Hermite插值；光滑函數(shù)；誤差函數(shù)；多項(xiàng)式

支持向量機(jī)是在統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)上發(fā)展起來的一種機(jī)器學(xué)習(xí)方法、是數(shù)據(jù)挖掘的一種新方法，廣泛用于分類問題和回歸問題，特別在文本分類、圖像檢索、人臉識別、語音識別、手寫數(shù)字識別等領(lǐng)域有大量應(yīng)用[1-4].但隨著信息技術(shù)的迅猛發(fā)展，數(shù)據(jù)規(guī)模越來越大，其分類速度慢的問題日益突出.為此，在支持向量機(jī)理論的研究上，近年來出現(xiàn)了一個新的研究方向——光滑的支持向量機(jī).這種光滑的支持向量機(jī)采用快速的求解算法，因而可以降低支持向量機(jī)的計(jì)算復(fù)雜性.該研究方向可分為光滑支持向量機(jī)模型和光滑函數(shù)2個方面.

在光滑支持向量機(jī)模型的研究方面，2001年，Lee等人[5]用Sigmoid函數(shù)的積分函數(shù)作為光滑函數(shù)，提出光滑的支持向量機(jī)模型；2005年，袁玉波、嚴(yán)杰和徐成賢[6]用多項(xiàng)式函數(shù)作為光滑函數(shù)，提出一個多項(xiàng)式光滑的支持向量機(jī)模型；同年Lee等人[7]用Sigmoid函數(shù)的積分函數(shù)的復(fù)合函數(shù)作為光滑函數(shù)，提出一個光滑的支持向量回歸機(jī)模型；2008年，我們用一類多項(xiàng)式光滑函數(shù)，提出多項(xiàng)式光滑的支持向量機(jī)在分類問題中的一般模型[8]，還提出多項(xiàng)式光滑的支持向量回歸機(jī)模型[9]；2009年，劉葉青等人[10]也提出多項(xiàng)式光滑的支持向量機(jī).上述這些光滑模型因?yàn)榭梢圆捎每焖俚腘ewton-Armijo算法進(jìn)行求解，所以可以提高分類速度或回歸速度.但這種光滑模型都必須用適當(dāng)?shù)墓饣瘮?shù)對原支持向量機(jī)模型進(jìn)行光滑處理才能得到.可見光滑函數(shù)是研究光滑支持向量機(jī)的前提和基礎(chǔ)，研究光滑函數(shù)具有重要的理論意義.光滑支持向量機(jī)以往的研究主要是針對光滑函數(shù)的應(yīng)用，例如對光滑支持向量機(jī)的模型及其性能、效率的研究，而對光滑函數(shù)自身性質(zhì)的研究卻很少見到.

在光滑函數(shù)的研究方面，1996年，Chen等人[11-12]針對數(shù)學(xué)規(guī)劃問題中正號函數(shù)x+=max(0,x)不光滑的問題，用概率密度的方法提出一個光滑函數(shù)，即Sigmoid函數(shù)的積分函數(shù)，并解決了該光滑函數(shù)的誤差問題.此后將近10年沒有新的研究成果出現(xiàn)，直到2005年，袁玉波等人[6]提出一個多項(xiàng)式光滑函數(shù)；2007年，熊金志等人[13]用積分等方法導(dǎo)出一個重要的遞推公式，得到一類支持向量機(jī)的多項(xiàng)式光滑函數(shù)，并指出這類多項(xiàng)式光滑函數(shù)有無窮多個；2008年，王斌等人[14]用遞推等方法也得到這類多項(xiàng)式光滑函數(shù)；2009年，劉葉青等人[10]用級數(shù)方法提出這類多項(xiàng)式光滑函數(shù)的級數(shù)形式.然而，這些方法都沒能給出這類多項(xiàng)式光滑函數(shù)的誤差函數(shù)及其性質(zhì).到目前為止，有關(guān)利用正號函數(shù)光滑化的文獻(xiàn)也均未給出這種誤差函數(shù).因此，支持向量機(jī)的多項(xiàng)式光滑函數(shù)還存在3個問題：1)用何種方法尋找這類光滑函數(shù)的誤差函數(shù)？2)這類誤差函數(shù)有多少個？可否用一個一般形式表示？3)這類誤差函數(shù)的性質(zhì)如何？為此，本文用Newton-Hermite插值方法，研究支持向量機(jī)無窮多個多項(xiàng)式光滑函數(shù)的誤差函數(shù)及其性質(zhì)，試圖解決上述3個長期困擾人們的問題，為光滑函數(shù)和支持向量機(jī)的研究提供基本的理論支持.

1多項(xiàng)式光滑函數(shù)及其Newton-Hermite插值問題

1.1多項(xiàng)式光滑函數(shù)

為便于敘述和理解，我們先給出支持向量機(jī)多項(xiàng)式光滑函數(shù)的定義：

定義1. 多項(xiàng)式光滑函數(shù).在一個包含原點(diǎn)的對稱區(qū)間[-a,a]，a>0，用一個具有d階光滑(d為任意正整數(shù))的多項(xiàng)式函數(shù)pd(x,a)代替x+=max(0,x)，在該區(qū)間以外仍取x+的值.而在端點(diǎn)x=±a上，使pd(x,a)具有d階光滑，從而使這個函數(shù)在整個x軸上皆具有d階光滑，稱這種函數(shù)為支持向量機(jī)的多項(xiàng)式光滑函數(shù)[13],如圖1所示的虛線為多項(xiàng)式光滑函數(shù)曲線.

Fig.1　The image of polynomial smoothing functions approximating x+.圖1　多項(xiàng)式光滑函數(shù)逼近x+的圖像

1.2Newton-Hermite插值方法

Hermite插值是處理插值節(jié)點(diǎn)處的導(dǎo)數(shù)信息已知的一類插值方法.其基本原理是：設(shè)被插值函數(shù)為f(x)，φ(x)為Hermite插值多項(xiàng)式.給定f(x)在n+1個插值節(jié)點(diǎn)x0,x1,…,xn處的函數(shù)值及導(dǎo)數(shù)值，這些插值條件通常表示為φ(k)(xi)=f(k)(xi),i=0,1,…,n且k=0,1,…,d，其中φ(0)(x)表示函數(shù)值φ(x).Newton差商經(jīng)常被用來求Hermite插值多項(xiàng)式，兩者的結(jié)合稱為Newton-Hermite插值方法.當(dāng)利用到高階導(dǎo)數(shù)的信息即插值條件中d>1時，Newton-Hermite插值方法具有計(jì)算簡便、容易得到誤差估計(jì)等優(yōu)點(diǎn)[15].

由定義1知，支持向量機(jī)的多項(xiàng)式光滑函數(shù)只涉及到2個節(jié)點(diǎn)，因此下面我們簡要給出只有2個插值節(jié)點(diǎn)的Newton-Hermite插值的相關(guān)定義：

定義2. Newton-Hermite插值多項(xiàng)式函數(shù).給定被插值函數(shù)f(x)在2個插值節(jié)點(diǎn)x1,x2處的信息f(k)(x1),f(k)(x2)，k=0,1,…,d，若多項(xiàng)式函數(shù)φ(x)滿足插值條件φ(k)(x1)=f(k)(x1)，φ(k)(x2)=f(k)(x2)，k=0,1,…,d，則稱φ(x)為f(x)的Newton-Hermite插值多項(xiàng)式函數(shù).

根據(jù)Newton-Hermite插值原理[15]，該多項(xiàng)式函數(shù)可表示為

φ(x)=f[x1]+f[x1,x1](x-x1)+…+

f[x1,…,x1](x-x1)d+f[x1,…,x1,x2]×

(x-x1)d+1+f[x1,…,x1,x2,x2]×

(x-x1)d+1(x-x2)+…+f[x1,…,x1,

x2,…,x2](x-x1)d+1(x-x2)d,

其中，插值多項(xiàng)式函數(shù)的系數(shù)稱為Newton差商，其定義如下：

定義3[15]. Newton差商.記

定義4. 誤差函數(shù).對插值區(qū)間內(nèi)的任意點(diǎn)x，令R(x)=f(x)-φ(x)，則稱R(x)為Newton-Hermite插值多項(xiàng)式函數(shù)的誤差函數(shù).

根據(jù)Newton-Hermite插值原理[15]，該誤差函數(shù)可表示為

(x-x1)d+1(x-x2)d+1.

(1)

1.3多項(xiàng)式光滑函數(shù)的Newton-Hermite插值問題

在支持向量機(jī)的光滑理論中，正號函數(shù)具有很重要的作用.為表述方便，我們把正號函數(shù)記為f(x)，即

因?yàn)檎柡瘮?shù)不光滑，所以如何選擇光滑函數(shù)對正號函數(shù)進(jìn)行光滑逼近是一個重要課題.

本文用多項(xiàng)式函數(shù)對正號函數(shù)在一個對稱區(qū)間[-a,a]進(jìn)行光滑處理，根據(jù)定義1，即用d階光滑多項(xiàng)式函數(shù)pd(x,a)來光滑逼近正號函數(shù)f(x)，使其滿足如下的d階光滑條件[13]：

其中a>0，d為任意正整數(shù).根據(jù)定義2，顯然該問題是一個Hermite插值問題.根據(jù)Newton-Hermite插值原理，該d階多項(xiàng)式光滑函數(shù)可表示為

pd(x,a)=f[-a]+f[-a,-a](x+a)+…+

f[-a,…,-a](x+a)d+f[-a,…,-a,a]×

(x+a)d+1+f[-a,…,-a,a,a](x+a)d+1×

(x-a)+…+f[-a,…,-a,a,…,a]×

(x+a)d+1(x-a)d,

(2)

其中,各項(xiàng)系數(shù)為Newton差商.

為書寫方便，我們結(jié)合定義3，記Newton差商為

i,j=0,1,…,d+1.

(3)

則由式(2)可直接得d階多項(xiàng)式光滑函數(shù):

(4)

顯然，只要求出各項(xiàng)Newton差商N(yùn)(i,j)，就可得到多項(xiàng)式光滑函數(shù)pd(x,a).因此我們就把求多項(xiàng)式光滑函數(shù)的問題轉(zhuǎn)換成了求Newton差商的問題.

2Newton差商與多項(xiàng)式光滑函數(shù)的Newton-Hermite插值形式

2.1Hermite插值中的Newton差商

下面的引理表明，在本文的Hermite插值問題中，Newton差商具有許多良好性質(zhì).

引理1.Newton差商N(yùn)(i,j)定義如式(3)，則：

1) N(i,0)=0, i=1,2,…,d+1,

2) 當(dāng)i≠0，j≠0時，

4) 當(dāng)i≠0，j≠0時，Newton差商為

(5)

其中,h(i,j)滿足:

h(i,j)=h(i-1,j)-h(i,j-1)；

(6)

5) 當(dāng)i=1或j=1時，有:

h(i,1)=1，i=1,2,…,d+1,

h(1,j)=(-1)j，j=2,3,…,d+1;

6) 當(dāng)i,j=2,3,…,d+1時，h(i,j)滿足下列遞推公式：

證明. 1) 由式(3)得:

N(1,0)=f[-a]=f(-a)=0，

N(0，1)=f[a]=f(a)=a,

i,j=2,3,…,d+1.

故有N(0,2)=1,N(0,j)=0，j=3,4,…,d+1.

2) 根據(jù)式(3)有:

4) 用數(shù)學(xué)歸納法.

當(dāng)i+j=2時，有:

假設(shè)當(dāng)i+j=n時，式(5)成立，即:

下面證明當(dāng)i+j=n+1時，式(5)也成立.因?yàn)?/p>

5) 結(jié)合3)和式(6)直接可得.

6) 由式(6)分別可得:

h(i,j)-h(i-1,j)=-h(i,j-1)，

h(i-1,j)-h(i-2,j)=-h(i-1,j-1)，

h(2,j)-h(1,j)=-h(2,j-1)，

以上等式相加得到:

證畢.

說明：

1) 引理1的結(jié)論5)，6)表明：系數(shù)h(i,j)與插值區(qū)間的a無關(guān)，只與i和j有關(guān).任意給定i和j，h(i,j)是常量，由引理1的結(jié)論5)，6)可將h(i,j)遞推出來.為表述方便，我們稱h(i,j)為Newton差商因子.

2) 引理1的結(jié)論4)把Newton差商表示成式(5)，從而把與a有關(guān)的Newton差商N(yùn)(i,j)與Newton差商因子h(i,j)一一對應(yīng)了起來，也就是說，把求Newton差商N(yùn)(i,j)的問題轉(zhuǎn)換成了求Newton差商因子h(i,j)的問題了.

3) 借助Newton差商因子h(i,j)來發(fā)現(xiàn)Newton差商的內(nèi)部規(guī)律和性質(zhì)，仍用Newton差商N(yùn)(i,j)來更簡潔地表示相應(yīng)的結(jié)果.

引理2. 當(dāng)i，j≠0且i+j>2時，Newton差商因子h(i,j)和Newton差商N(yùn)(i,j)具有3點(diǎn)性質(zhì)：

1) 若i+j是偶數(shù)，則h(i,j)=-h(j,i)，從而N(i,j)=-N(j,i)；

2) 若i+j是奇數(shù)，則h(i,j)=h(j,i)，從而N(i,j)=N(j,i)；

3) N(i,j)=(-1)i+j-1N(j,i).

證明. 用數(shù)學(xué)歸納法.

1) 當(dāng)i+j=4時，根據(jù)引理1的結(jié)論1)～3)，可得：

假設(shè)當(dāng)i+j=2n(n>2)時h(i,j)+h(j,i)=0成立.下面證明當(dāng)i+j=2(n+1)時(n>2)命題也成立.

多次利用式(6)：h(i,j)=h(i-1,j)-h(i,j-1)，可得：

h(i,j)+h(j,i)=h(i-1,j)-h(i,j-1)+

h(j-1,i)-h(j,i-1)=h(i-2,j)-

h(i-1,j-1)-h(i-1,j-1)+h(i,j-2)+

h(j-2,i)-h(j-1,i-1)-h(j-1,i-1)+

h(j,i-2)=[h(i-2,j)+h(j,i-2)]-

2[h(i-1,j-1)+h(j-1,i-1)]+

[h(i,j-2)+h(j-2,i)]，

因?yàn)閕+j-2=2n,n>2，所以以上每個中括號項(xiàng)都等于0.故h(i,j)+h(j,i)=0成立.

故當(dāng)i，j≠0且i+j為大于2的偶數(shù)時，h(i,j)=-h(j,i)總成立，從而N(i,j)=-N(j,i).

2) 與結(jié)論1)類似，可證當(dāng)i，j≠0且i+j為大于2的奇數(shù)時，h(i,j)=h(j,i)總成立，從而N(i,j)=N(j,i).

3) 根據(jù)證明1)和2)可直接得到性質(zhì)3).

證畢.

推論1. 對任意正整數(shù)2≤r≤d+1，有h(r,r)=0，N(r,r)=0.

證畢.

推論2. 對任意正整數(shù)d，i=1,2,…,d，有(-1)d+1h(i,d+1)>0，(-1)d+1N(i,d+1)>0.

證明. 根據(jù)式(5)只需要證明(-1)d+1h(i,d+1)>0成立即可.用數(shù)學(xué)歸納法.

當(dāng)d=1時，根據(jù)引理1的結(jié)論5)知h(1,2)=1，故命題成立.

假設(shè)當(dāng)d=n時命題也成立，即對任意i=1,2,…,n，有(-1)n+1h(i,n+1)>0.

下面證明d=n+1時命題成立.因?yàn)椋?/p>

所以，對任意i=1,2,…,n+1，有：

故對任意正整數(shù)d，i=1,2,…,d，(-1)d+1h(i,d+1)>0總成立.

證畢.

推論3. 對任意正整數(shù)d，i=1,2,…,d，有(-1)i+1h(d+1,i)>0，(-1)i+1N(d+1,i)>0.

證明. 根據(jù)式(5)，只需證明(-1)i+1h(d+1,i)>0成立即可.由引理2，當(dāng)d+i+1為奇數(shù)時，h(d+1,i)=h(i,d+1).所以由推論2，對任意i=1,2,…,d，有：

0<(-1)d+1h(i,d+1)=(-1)d+1h(d+1,i)=

(-1)d+1+2ih(d+1,i)=(-1)i+1h(d+1,i)，

即(-1)i+1h(d+1,i)>0.類似地，當(dāng)d+i+1為偶數(shù)時，h(d+1,i)=-h(i,d+1).所以由推論2，對任意i=1,2,…,d，有：

0<(-1)d+1h(i,d+1)=(-1)dh(d+1,i)=

(-1)d+2i+2h(d+1,i)=(-1)i+1h(d+1,i)，

即(-1)i+1h(d+1,i)>0.

證畢.

2.2多項(xiàng)式光滑函數(shù)的Newton-Hermite插值形式

引理3. 支持向量機(jī)d階多項(xiàng)式光滑函數(shù)可表示為

(7)

證明. 由引理1的結(jié)論1)知N(i,0)=0，i=1,2,…,d+1，代入式(4)可得：

由推論1知N(d+1,d+1)=0.故有式(7)成立.

證畢.

由引理3知，對稱區(qū)間(-a,a)上的多項(xiàng)式光滑函數(shù)pd(x,a)是2d階的，于是就推出：

推論4. 文獻(xiàn)[6]關(guān)于光滑支持向量機(jī)在對稱區(qū)間用“奇數(shù)階多項(xiàng)式可能是做不到的”的猜想是正確的.

結(jié)合式(5)和式(7)直接可得：

定理1. 支持向量機(jī)d階多項(xiàng)式光滑函數(shù)pd(x,a)可表示為

(8)

定理1表明：

1) 支持向量機(jī)的多項(xiàng)式光滑函數(shù)存在一種Newton-Hermite插值形式.

2) 只要求出式(8)中的Newton差商因子h(d+1,j)和h(d,j+1)，即可得到這種Newton-Hermite插值形式.

3) 任意給定一個d(d=1,2,…)，式(8)就有一個多項(xiàng)式光滑函數(shù)與之對應(yīng)，顯然該Newton-Hermite插值形式含有無窮多個光滑函數(shù)，即{pd(x,a),d=1,2,…}.

因此由定理1知，只要求出h(d+1,j)，就可得到支持向量機(jī)多項(xiàng)式光滑函數(shù)的Newton-Hermite插值形式.于是，我們就把求多項(xiàng)式光滑函數(shù)的問題最終轉(zhuǎn)換成了求Newton差商因子h(d+1,j)的問題.

將定理1和引理1結(jié)合起來，便可得到如下計(jì)算d階多項(xiàng)式光滑函數(shù)的算法：

算法1. 計(jì)算支持向量機(jī)的任意d階多項(xiàng)式光滑函數(shù).

Step1. 給定光滑階數(shù)d；

Step2. 根據(jù)引理1的結(jié)論5)，6)計(jì)算Newton差商因子h(d+1,j)，j=1,2,…,d；

Step3. 代入式(8)，計(jì)算出d階多項(xiàng)式光滑函數(shù)pd(x,a).

需要指出的是，我們在文獻(xiàn)[13]已證明：任意給定一個d(d=1,2,…)，支持向量機(jī)的多項(xiàng)式光滑函數(shù)是唯一的.因此，由算法1求得的支持向量機(jī)多項(xiàng)式光滑函數(shù)形式上是用Newton-Hermite插值表示，實(shí)際上與文獻(xiàn)[10,13-14]的多項(xiàng)式光滑函數(shù)是完全相同的，只是求法和形式不同.我們還注意到文獻(xiàn)[6,8,10]已做了3個工作：1)列出了這類多項(xiàng)式光滑函數(shù)的前3個函數(shù)；2)用這類多項(xiàng)式光滑函數(shù)提出了多項(xiàng)式光滑的支持向量機(jī)及其一般模型；3)做了數(shù)值實(shí)驗(yàn).因此本文就不重復(fù)這些工作了.

本節(jié)得到了Newton差商的性質(zhì)和多項(xiàng)式光滑函數(shù)的Newton-Hermite插值形式，下面我們利用這些結(jié)果重點(diǎn)研究多項(xiàng)式光滑函數(shù)的誤差函數(shù)及其性質(zhì).

3多項(xiàng)式光滑函數(shù)的誤差函數(shù)及其性質(zhì)

3.1誤差函數(shù)及其一般形式

正號函數(shù)不是多項(xiàng)式且在原點(diǎn)處不可導(dǎo)，故用插值多項(xiàng)式函數(shù)逼近正號函數(shù)，必然會產(chǎn)生誤差.據(jù)我們所知，到目前為止，利用正號函數(shù)的光滑化的文獻(xiàn)均未解決這類誤差問題.下面我們研究多項(xiàng)式光滑函數(shù)pd(x,a)逼近正號函數(shù)的誤差函數(shù).顯然誤差函數(shù)有無窮多個，根據(jù)定義4，該類誤差函數(shù)可記為

Rd(x,a)=f(x)-pd(x,a),

(9)

其中，d=1,2,….

由定義1易知，在區(qū)間(-a,a)以外，Rd(x,a)=0,d=1,2,….因此我們只需研究誤差函數(shù)Rd(x,a)在區(qū)間(-a,a)內(nèi)的情形.

引理4. 對任意點(diǎn)x∈(-a,a)，d階多項(xiàng)式光滑函數(shù)pd(x,a)在x處的誤差函數(shù)可表示為

(10)

或

(11)

其中,N(d+1,j)和N(j,d+1)由式(5)給出.

證明. 把式(7)代入式(9)直接可得式(10).下面證明式(11)成立.

根據(jù)式(1)，正號函數(shù)的插值多項(xiàng)式的誤差函數(shù)也可表示為

(x+a)d+1(x-a)d+1.

若記：

i,j=0,1,…,d+1，

(12)

則誤差函數(shù)可表示為

Rd(x,a)=l(d+1,d+1)(x+a)d+1(x-a)d+1.

根據(jù)定義3，由式(12)可得Newton差商

從而：

(13)

根據(jù)定義3和式(12)可得：

所以：

代入式(13)得到：

故：

Rd(x,a)=l(d+1,d+1)(x+a)d+1(x-a)d+1=

即式(11)成立.

證畢.

定理2. 支持向量機(jī)d階多項(xiàng)式光滑函數(shù)的誤差函數(shù)的一般形式可表示為

Rd(x,a)=

(14)

其中，N(d+1,j)和N(j,d+1)由式(5)給出.

證明. 當(dāng)x∈(-a,0]時，f(x)=0，代入引理4的式(10)得到：

當(dāng)x∈[0,a)時，f(x)=x，代入式(11)得到：

故(14)式成立.

證畢.

式(14)中含有2類Newton差商N(yùn)(d+1,j)和N(j,d+1)，通過式(5)可以轉(zhuǎn)化為Newton差商因子h(d+1,j)和h(j,d+1).h(d+1,j)可根據(jù)引理1的結(jié)論5)，6)得到，而h(j,d+1)可通過引理2間接得到.

定理2表明3個性質(zhì)：

1) 這類光滑函數(shù)的誤差函數(shù)可由Newton-Hermite插值方法給出.式(14)是這類光滑函數(shù)的誤差函數(shù)的一般形式，也是一個計(jì)算誤差函數(shù)的方便公式，顯然只需計(jì)算Newton差商因子h(d+1,j)，然后利用引理2計(jì)算h(j,d+1)，即可算出N(d+1,j)和N(j,d+1)，j=1,2,…,d，從而由式(14)得到誤差函數(shù).

2) 由式(14)知，誤差函數(shù)與被插值函數(shù)的函數(shù)值無關(guān)，只與Newton差商N(yùn)有關(guān)，或者說只與Newton差商因子h有關(guān)(通過式(5)可知).因此我們就把求多項(xiàng)式光滑函數(shù)的誤差函數(shù)問題轉(zhuǎn)換成了求Newton差商的問題，然后又轉(zhuǎn)換成了求Newton差商因子的問題.

3) 任意給定一個d(d=1,2,…)，就有一個誤差函數(shù)與之對應(yīng)，顯然該誤差函數(shù)包含了無窮多個多項(xiàng)式光滑函數(shù)的誤差函數(shù).

以上分析可綜合成下面的算法：

算法2. 計(jì)算支持向量機(jī)d階多項(xiàng)式光滑函數(shù)的誤差函數(shù).

Step1. 給定光滑階數(shù)d；

Step2. 根據(jù)引理1的結(jié)論5)，6)計(jì)算Newton差商因子h(d+1,j)；然后根據(jù)引理2計(jì)算Newton差商因子h(j,d+1)，j=1,2,…,d；

Step3. 將Newton差商因子h(d+1,j)和h(j,d+1)代入式(5),得到N(d+1,j),N(j,d+1)，j=1,2,…,d；

Step4. 將N(d+1,j),N(j,d+1),j=1,2,…,d，代入式(14)計(jì)算出d階多項(xiàng)式光滑函數(shù)的誤差函數(shù)Rd(x,a).

3.2誤差函數(shù)的性質(zhì)

定理3. 任意給定正整數(shù)d和正數(shù)a，支持向量機(jī)d階多項(xiàng)式光滑函數(shù)的誤差函數(shù)Rd(x,a)具有4個性質(zhì)：

1) Rd(x,a)是非正函數(shù)，即Rd(x,a)≤0；

2) Rd(x,a)是偶函數(shù)，即Rd(-x,a)=Rd(x,a)；

3) Rd(x,a)在(-a,0]上是減函數(shù)，在[0,a)上是增函數(shù)；

4) Rd(x,a)在x=0時絕對值最大，即在x=0處誤差最大，且最大誤差為

證明. 1)當(dāng)x≤-a或x≥a時，顯然有Rd(x,a)=0.下面考慮x∈(-a,a)的情形，此時有x+a>0，x-a<0.

根據(jù)推論3可得對任意j=1,2,…,d，有(-1)i+1N(d+1,i)>0.所以當(dāng)x∈(-a,0]時，

又根據(jù)推論2可得：對任意i=1,2,…,d，(-1)d+1N(i,d+1)>0.所以當(dāng)x∈(0,a)時，

綜合以上分析可得：Rd(x,a)≤0.

2) 因?yàn)椋?/p>

Rd(-x,a)=

所以Rd(-x,a)=Rd(x,a)，即Rd(x,a)為偶函數(shù)、關(guān)于y軸對稱.

3) 當(dāng)x∈(-a,0]時，可求得Rd(x,a)關(guān)于x的導(dǎo)數(shù)：

當(dāng)x∈[0,a)時，可求得Rd(x,a)關(guān)于x的導(dǎo)數(shù)

4) 根據(jù)性質(zhì)3)的結(jié)論，Rd(x,a)在x=0時取最小值.由性質(zhì)1)知Rd(x,a)≤0，故Rd(x,a)在x=0時絕對值最大，即在x=0處誤差最大.在式(14)中取x=0得到最大誤差為

證畢.

定理3表明誤差函數(shù)Rd(x,a)具有若干共同的重要性質(zhì)，特別是定理3的性質(zhì)4)給出了誤差函數(shù)一般形式Rd(x,a)的誤差最大值點(diǎn)以及最大誤差值，這是誤差理論的一個重要內(nèi)容.

定理4. 任意給定x和正數(shù)a，支持向量機(jī)d階多項(xiàng)式光滑函數(shù)的誤差函數(shù)Rd(x,a)關(guān)于光滑階數(shù)d是增函數(shù).

證明. 我們在文獻(xiàn)[8]中已證明：d階多項(xiàng)式光滑函數(shù)pd(x,a)關(guān)于光滑階數(shù)d是減函數(shù)，即

pd(x,a)≤pd-1(x,a)，d=2,3,…,

結(jié)合式(9)，易得：

f(x)-pd(x,a)≥f(x)-pd-1(x,a)，

d=2,3,…,

即：

Rd(x,a)≥Rd-1(x,a)，d=2,3,…，

所以，Rd(x,a)關(guān)于光滑階數(shù)d是增函數(shù).

證畢.

定理3的性質(zhì)1)表明Rd(x,a)是非正函數(shù)，結(jié)合定理4知，光滑階數(shù)d越大，Rd(x,a)越接近0.換言之，光滑階數(shù)d越大，多項(xiàng)式光滑函數(shù)pd(x,a)越接近正號函數(shù).

證明. 根據(jù)定理3的性質(zhì)1)，4)有：

故：

證畢.

3.3誤差函數(shù)的若干算例

由第3節(jié)的證明知：這類多項(xiàng)式光滑函數(shù)的誤差函數(shù)有無窮多個.下面我們以d=1,2,3時為例，即以1階、2階和3階多項(xiàng)式光滑函數(shù)為例，用Matlab演算這類多項(xiàng)式光滑函數(shù)的前3個誤差函數(shù)的表達(dá)式，以及驗(yàn)證它們的重要性質(zhì).

根據(jù)算法2，得到表1中關(guān)于Newton差商因子h(d+1,j)及h(j,d+1)的數(shù)據(jù).

Table1Whendis1, 2and3,theDifferenceQuotientFactorofNewtonh(d+1,j)andh(j,d+1)

表1d值取1,2,3時的Newton差商因子h(d+1,j)及h(j,d+1)

dh(d+1,j)h(j,d+1)11121,-1-1,-131,-2,21,2,2

Note: j=1,2,…,d

當(dāng)d=1時，1階多項(xiàng)式光滑函數(shù)的誤差函數(shù)為

當(dāng)d=2時，2階多項(xiàng)式光滑函數(shù)的誤差函數(shù)為

當(dāng)d=3時，3階多項(xiàng)式光滑函數(shù)的誤差函數(shù)為

下面以a=1為例，即在區(qū)間(-1,1)上，畫出1階至3階多項(xiàng)式光滑函數(shù)的誤差函數(shù)，如圖2所示:

Fig. 2　Error function of the polynomial smoothing functions between -1 and 1.圖2　區(qū)間(-1,1)上多項(xiàng)式光滑函數(shù)的誤差函數(shù)

由圖2可以看出，這3個多項(xiàng)式光滑函數(shù)的誤差函數(shù)具有5個共同的重要性質(zhì)：1)非正函數(shù)；2)偶函數(shù)；3)在(-1,0]上是減函數(shù)，在[0,1)上是增函數(shù)；4)在x=0處誤差最大；5)關(guān)于光滑階數(shù)是增函數(shù).

4結(jié)論

光滑函數(shù)是研究光滑支持向量機(jī)的重要基礎(chǔ)，因此其誤差及其性質(zhì)問題是一個重要的理論問題.近年來多位學(xué)者用不同方法對支持向量機(jī)的多項(xiàng)式光滑函數(shù)進(jìn)行了研究，提出了這類多項(xiàng)式光滑函數(shù)的多種不同形式，還提出了多項(xiàng)式光滑的支持向量機(jī)及其一般模型，但都沒能解決這類多項(xiàng)式光滑函數(shù)的誤差函數(shù)及其性質(zhì)問題.為此本文用Newton-Hermite插值方法對該問題進(jìn)行了研究：首先把多項(xiàng)式光滑函數(shù)的誤差函數(shù)問題轉(zhuǎn)換成Newton-Hermite插值問題，繼而轉(zhuǎn)換成求Newton差商的問題，然后轉(zhuǎn)換成求Newton差商因子的問題，最終解決了這個問題,歸納出3個結(jié)論：

1) 用Newton-Hermite插值方法可得到這類光滑函數(shù)的誤差函數(shù).

2) 這類誤差函數(shù)有無窮多個，任意給定一個光滑階數(shù)，就有一個誤差函數(shù)與之對應(yīng).這無窮多個誤差函數(shù)可用一個一般形式表示，并給出了這個一般形式,該一般形式能方便地計(jì)算出任意多項(xiàng)式光滑函數(shù)的誤差函數(shù).還給出了誤差函數(shù)一般形式的誤差最大值點(diǎn)以及最大誤差值.

3) 這類誤差函數(shù)具有6個共同的重要性質(zhì).如：①都是非正函數(shù)；②都是偶函數(shù)；③在區(qū)間(-a,0]上都是減函數(shù)，在區(qū)間(0,a)上都是增函數(shù)；④誤差最大值點(diǎn)都在原點(diǎn)，誤差最大值都可由一個公式給出；⑤關(guān)于光滑階數(shù)都是增函數(shù)；⑥當(dāng)插值區(qū)間趨于一點(diǎn)時，誤差都趨于0.

本文用Newton-Hermite插值方法，得到了支持向量機(jī)多項(xiàng)式光滑函數(shù)的誤差函數(shù)的一般形式及其許多重要性質(zhì)，從而解決了這類多項(xiàng)式光滑函數(shù)以往沒有解決的誤差函數(shù)問題，成功解決了引言中提到的3個問題，填補(bǔ)了多項(xiàng)式光滑函數(shù)在誤差函數(shù)方面的研究空白，建立了這類多項(xiàng)式光滑函數(shù)的誤差理論.本文為研究光滑函數(shù)和光滑支持向量機(jī)提供了基本的理論支持，因而在一定程度上豐富了支持向量機(jī)理論.

參考文獻(xiàn)

[1]DengNaiyang,TianYingjie.NewMethodinDataMining:SupportVectorMachine[M].Beijing:SciencePress, 2004 (inChinese)(鄧乃揚(yáng), 田英杰. 數(shù)據(jù)挖掘的新方法—支持向量機(jī)[M]. 北京: 科學(xué)出版社, 2004)

[2]XuLL,CrammerK,SchuurmansD.Robustsupportvectormachinetrainingviaconvexoutlierablation[C]Procofthe21stIntConfonArtificialIntelligence.MenloPark,CA:AAAIPress, 2006: 536-542

[3]WuYC,LiuYF.Robusttruncatedhingelosssupportvectormachines[J].JournaloftheAmericanStatisticalAssociation, 2007, 102(479): 974-983

[4]YangXiaowei,TanLiangjun,HeLifang.Arobustleastsquaressupportvectormachineforregressionandclassificationwithnoise[J].Neurocomputing, 2014, 140: 41-52

[5]LeeYJ,MangasarianOL.SSVM:Asmoothsupportvectormachineforclassification[J].ComputationalOptimizationandApplications, 2001, 22(1): 5-21

[6]YuanYubo,YanJie,XuChengxian.Polynomialsupportvectormachine[J].ChineseJournalofComputers, 2005, 28(1): 9-17 (inChinese)(袁玉波, 嚴(yán)杰, 徐成賢. 多項(xiàng)式光滑的支撐向量機(jī)[J]. 計(jì)算機(jī)學(xué)報(bào), 2005, 28(1): 9-17)

[7]LeeYJ,HsiehWF,HuangCM. ε-SSVR:Asmoothsupportvectormachineforε-insensitiveregression[J].IEEETransonKnowledgeandDataEngineering, 2005, 17(5): 5-22

[8]XiongJinzhi,YuanHuaqiang,PengHong.Ageneralformulationofpolynomialsmoothsupportvectormachines[J].JournalofComputerResearchandDevelopment, 2008, 45(8): 1346-1373 (inChinese)(熊金志, 袁華強(qiáng), 彭宏. 多項(xiàng)式光滑的支持向量機(jī)一般模型研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2008, 45(8): 1346-1373)

[9]XiongJinzhi,HuJinlian,YuanHuaqiang,etal.Researchonnewsmoothingfunctionsforsupportvectorregressions[J].PatternRecognitionandArtificialIntelligence, 2008, 21(3): 273-279 (inChinese)(熊金志, 胡金蓮, 袁華強(qiáng), 等. 支持向量回歸機(jī)的光滑函數(shù)研究[J]. 模式識別與人工智能, 2008, 21(3): 273-279)

[10]LiuYeqing,LiuSanyang,GuMingtao.Researchonpolynomialfunctionsforsmoothingsupportvectormachines[J].SystemsEngineeringandElectronics, 2009, 31(6): 1450-1453 (inChinese)(劉葉青, 劉三陽, 谷明濤. 光滑支持向量機(jī)多項(xiàng)式函數(shù)的研究[J]. 系統(tǒng)工程與電子技術(shù), 2009, 31(6): 1450-1453)

[11]ChenC,MangasarianOL.Aclassofsmoothingfunctionsfornonlinearandmixedcomplementarityproblems[J].ComputationalOptimizationandApplication, 1996, 5: 97-138

[12]ChenC,MangasarianOL.Smoothingmethodsforconvexinequalitiesandlinearcomplementarityproblems[J].MathematicalProgramming, 1995, 71: 51-69

[13]XiongJinzhi,HuJinlian,YuanHuaqiang,etal.Anewclassofsmoothingfunctionsforsupportvectormachines[J].ActaElectronicaSinica, 2007, 35(2): 366-370 (inChinese)(熊金志, 胡金蓮, 袁華強(qiáng), 等. 一類光滑支持向量機(jī)新函數(shù)的研究[J]. 電子學(xué)報(bào), 2007, 35(2): 366-370)

[14]WangBin,HuJinlian,XiongJinzhi.Newmethodforsolvingsmoothingfunctionsofsupportvectormachines[J],JournalofSystemSimulation, 2008, 20(15): 4018-4020 (inChinese)(王斌, 胡金蓮, 熊金志. 一種求支持向量機(jī)光滑函數(shù)的新方法[J]. 系統(tǒng)仿真學(xué)報(bào), 2008, 20(15): 4018-4020)

[15]KincaidD,CheneyW.NumericalAnalysis:MathematicsofScientificComputing[M]. 3rded.NewYork:ThomsonLearning,Inc, 2002

HeWenbin,bornin1976.PhD,lecturer.Hismainresearchinterestsincluderemotesensingimageprocessing,artificialintelligence.

LiuQunfeng,bornin1978.PhD,associateprofessor.Hismainresearchinterestsincludeglobaloptimization,intelligentcomputing.

XiongJinzhi,bornin1964.Professor.Hismainresearchinterestsincludeartificialintelligenceanddatamining.

收稿日期：2015-01-04；修回日期：2015-08-19

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(60773050)；廣東省科技發(fā)展專項(xiàng)資金(基礎(chǔ)與應(yīng)用基礎(chǔ)研究方向)項(xiàng)目(2016A030313135)；東莞市科技計(jì)劃資助項(xiàng)目(201208102027)

通信作者：熊金志(dgxiongjz@126.com)

中圖法分類號TP18

The Error Theory of Polynomial Smoothing Functions for Support Vector Machines

He Wenbin, Liu Qunfeng, and Xiong Jinzhi

(CollegeofComputer,DongguanUniversityofTechnology,Dongguan,Guangdong523808)

AbstractSmoothing functions play an important role in the theory of smooth support vector machines. In 1996, Chen et al proposed a smoothing function of support vector machines—the integral function of Sigmoid function, and solved the error problem of the smoothing function. From 2005 to 2009, Yuan, Xiong and Liu proposed an infinite number of polynomial smoothing function and the corresponding reformulations for support vector machines. However, they did not touch the error functions for this class of polynomial smoothing functions. To fill up this gap, this paper studies the problem of the error functions with the Newton-Hermite interpolation method. The results show that: 1) the error functions of this class of polynomial smoothing functions can be calculated using the Newton-Hermite interpolation method, and the detailed algorithm is given; 2) there are an infinite number of error functions for this class of polynomial smoothing functions and a general formulation is obtained to describe these error functions; 3) there are several important properties for this class of error functions and the strict proof is given for these properties. By solving the problem of the error functions and their properties, this paper establishes an error theory of this class of polynomial smoothing functions, which is a basic theoretical support for smooth support vector machines.

Key wordssupport vector machine; Newton-Hermite interpolation; smoothing function; error function; polynomial

This work was supported by the National Natural Science Foundation of China (60773050), the Special Fund for Science and Technology Development in Guangdong Province (Basic and Applied Basic Research) (2016A030313135), and the Dongguan Science and Technology Plan (2012108102027).