增量式支持向量回归机学习

CCML2015主要内容背景介绍修改的n

-SVR形式增量式n-SVR算法实验结论对比n-SVR，n

-SVR相应于增量式学习带来两个难题：盒约束部分与训练样本集的大小相关约束部分多出一个不等式约束对比n

-SVC，n

-SVR相应于增量式学习带来一个难题：在目标函数中引入了一个额外的线性项n-SVR对偶形式(

)()

(

)((

)(

)mina

,a

******1s.t.lli=1i

ij2l

i,

j

=1ji

jK x

,

x

-ia

-ai

)yili=1li=1i

ii

ii0

£

a

(*)

£

C,i

=1,,

la

-aa

-aa

-a=

0,a

+a£

Cnl精确增量式SVM更新过程[Cauwen-berghs

and

Poggio,

2001]H2H1H初始化ac

=

0新增样本精确增量式SVM更新过程[Cauwen-berghs

and

Poggio,

2001]H2H1H1新增样本›

ac

=

ac

+

Dacfl

a1

=

0精确增量式SVM更新过程[Cauwen-berghs

and

Poggio,

2001]H2H1H间隔新增样本›

ac

=

ac

+

Dac1a1

=

0对比标准SVM，n-SVC相应于增量式学习多了两个复杂成分：盒约束部分与训练样本集的大小相关约束部分多出一个不等式约束n-SVC：s.t.0

£

ai

£1

/

l,i

=1,,

llmin

1

a

T

Haai=12

yiai

=

0,lai

‡n,i=1s.t.0

£

ai

£1,i

=1,,

llmin

1

a

T

Qaa2

yiai

=

0,i=1lai

=nl,i=1lj

ijii¶W"

i

˛

S

:

gi

=

=¶aib¢¢a

Q

+

y+

r

=

0‡

0

ai

=

00

<

ai

<1£

0

a

=1j

=1KKT条件：li

ii=1¶W=y

a

=

0b¢¶li=1¶W¶r¢=

ai

=nl聚焦点样本标签不同导致冲突的情形：新增样本（xc,yc）：=n

(l

+1)yiai

+

ycac

=

0li=1li=1i

ca

+a-Da1

--

Dan

+

Dac

=

0Da1

++

Dan

+

Dac

=

0›Dac存在冲突i˛

SSi

i

cc

y

Da

+

y

Da

=

0i

ci˛

SS

Da

+

Da

=

0解决思路：li

=1,,

ls.t.

ai

yi

=

0，

0

£

ai

£nl，i=12min

1

a

T

Qaai

=1,,

ll

ls.t.

ai

yi

=

0，ai

=nl, 0

£

ai

£nl，i=1

i=12a严格的

min

1

a

T

Qa松弛的绝缘增量调整恢复调整恢复等式约束Da

j

Qij

+

yi

Db¢+

Dr¢=

0,i

j˛

SSSDg

=

"

i

˛

S

y

Da

=

0j˛

SS

j

jjDDaa

j

++eDDzr¢=+0Dz

=

0j˛Sj˛

SsS仍然可能存在冲突解决方法：根据KKT条件，新增样本需满足：一种等式形式：n-SVR

min(

)(

)

(

)(

)(

)(

)a

,a

******0

£a

(*)

£

C,l1

2ls.t.i

=1,,lli=1iijji

jii

illi

ii=1iii=1i约简yai,

j=1-a

a-a

K x

,

x

-a

-aa

-a=

0,a

+a=

Cnl2l2l

zia

i

=

0,i

=10

£

ai

£

C

,ai

=

Cnli

=1i

=

1,

,

2l1mina2s.t.-2li

,

j

=1aia

j

Qij2li

=1i

i

iz

y

a形式iji

j

i

jlQ

=

1

z

z K

(x

,

x

)KKT条件：仍然存在冲突'2li'

+e

=

0¶W"i

˛

S

:

gi

=

=¶aia

Q

-

z

y

+

z

b

j

ij

i

i

ij=1‡

0

for

ai

=

0for

0

<ai

<

C£

0

for

a

=

C'2l¶W¶b'2l¶W¶e=

ziai

=

0i=1=

ai

=

Cnli=1Q

‹l

lQ g

‹l

+1

l

+1g

b¢‹l

+1lb¢l

+1l蝌¢‹¢AONSV初始解：'

'ij

ij

ij˛Ss

z

j

Da

j

=

0j˛SS

Da

j

=

0j˛SSi

is=

0,

"

i

˛

SDgDa

Q

+

z

Db

+

De-

Dhz

y=h

:

0

fi

1初始化调整：根据KKT条件，调整zi

yiSSSSsSzTeTSSS

Suz

e

QDh

Db'

De'

=

0

Dh

0

0

0

0

0

Da

S

S

S

S

SS

QMM

ˇˇSSDb¢

=

R

0DhDhbb¢

def

ˇ

ˇb

S

0

Da=

bò¢

S

‚u

S

倐M

S

Dò¢

图1

不同基准数据集上IA、RAIA、SRA迭代次数的均值。(a)

Housing.

(b)

Forest

Fires.

(c)

Auto

MPG.

(d)

Triazines.

(e)ConcreteCompressive

Strength.

(f)

Friedman.图2

不同基准数据集上LibSVM(冷启动)、LibSVM(热启动)、INSVR的运行时间(秒)。(a)

Housing.

(b)

Forest

Fires.

(c)

Auto

MPG.

(d)

Triazines.

(e)Concrete

CompressiveStrength.

(f)

Friedman.结论提出了一种有效的增量式n

-SVR算法（

INSVR

）实验表明，INSVR能在有限的步骤内成功收敛到精确最优解实验表明，INSVR比基于冷启动和热启动的n

-SVR批处理算法更快。19具体请参考：Bin

Gu,

Victor

S.

Sheng,

Zhijie

Wang,

Derek

Ho,

SaidOsman,

and

Shuo

Li.

Incremental

Learning

for

ν-SupportVector

Regression.

Neural

Networks,

67

(2015):

140-150.Bin

Gu,

Jian-Dong

Wang,

Yue-Cheng

Yu,

Guan-Sheng

Zheng,

Yu-Fan

Huang,

and

Tao

Xu.

Accurate

on-line

ν-support

vector

learning.

Neural

Networks,27(0):51–59,

2012.Bin

Gu,

Victor

S.

Sheng,

Keng

Yeow

Tay,

WalterRomano,

and

Shuo

Li.

Incremental

Support

VectorLearning

for

Ordinal

Regression