ѧ
JOURNAL OF SOFTWARE
1999 10 7ڡNo.7 Vol.10 1999



ǰĽ渲㷨
š塡šࡡ󺣷
ժҪ¸ݶǰȨֵԭ,ƹ̷ֳ:þٵеĸָ,ȻĽ渲㷨.¸дԵģ,һƽߵķ,һǡѧϰ.ģ֤˴˷Ч.
ؼʡ,ԭ,渲㷨.
ͼšTP18
An Alternative Covering Design Algorithm of Multi-layer Neural Networks
ZHANG Ling1,3ZHANG Bo2,3YIN Hai-feng1
1(Institute of Artificial Intelligence Anhui University Hefei 230039)
2(Department of Computer Science and Technology Tsinghua University Beijing 100084)
3(Laboratory of Intelligent Technology and Systems Tsinghua University Beijing 100084)
AbstractIn this paper, the authors present a new principle for designing a sort of multi-layer weight-sum-and -threshold neural networks. The design process consists of two steps. First, each class of the given training samples is covered by using neighbor coverings as less as possible. Then a neural network is specifically designed by an approach called alternative covering algorithm. The simulation results of two representative hard classification problems are shown. One is so called two spirals separation problem, the other is the learning problem of infinitetraining samples. These simulation results are given to illustrate the effectiveness of the new method.
Key wordsMulti-layer neural network, principle for design, alternative covering algorithm.
ף1,M-PԪģ͵ļ,һ(Ϊ)ԭ򷽷,ΪFP㷨.Ľף1иĹFP㷨ԭ,ؽ,һֳõĸ㷨,ҳ֮Ϊ渲㷨.㷨һϽ˶һֱδ(Ϊ)ǰ.ģ,ָ㷨ѧϰ⡱(ѧϰѧϰ㷨޷),˵㷨Ч.ΪĶ,򵥽ף1õһЩ(ϸף1).
M-PԪģ͵ļ.
޶ĳ,޶n+1άռĳSn(ԭ,뾶ΪR),ôʱ(W*x-)>0(WȨ,ֵ),ͱʾɳƽP(䷽Ϊ:(W*x-)0)ָռĲ,ǡϵĳ.ȡWxȳ,򡱵ǡW,뾶Ϊr()(r()R(cos-1(/R2)),ͼ1ʾ.


aƽP볬ཻγɡ򡱵ʾͼbDSn任ʾͼ
ͼ1


,ȡԪļΪҡ(W*x-),һԪļϡ򡱵,,ǾͽԪϵӦ.Ԫּ,Ǿܷǳֱ۵ؽĸо.
Ԫļ֪,һ,ʹԸܽзҪķ,ȼһ,ԸKеĵ,ܰҪ򸲸ǽǷָ.,ǾͽתĳŸǵ.
ĳȲʱ,ķ,任ɳȵ.
ĶΪnάռен缯D,Snn+1άռеnάĳ,任

dmax{xxD}.
任ɴӼֱ۵Ϊ:Dλn+1άռйԭһnάƽ,DλSnڲ,任TǽDϵĵ㴹ֱͶ䵽Snϰ.ֱ任ȻһһӦ.,ʱÿһԪ(W,)ڳSn,WΪ,r()Ϊ뾶һ򡱵(r()r(cos-1(/R2))).
1ǰĽ渲㷨
1.1 
һ뼯K{x1,x2,...,xk}(KnάŷϿռĵ㼯),KΪsӼK1{x1,x2,...,xm(1)},...,Ks{xm(s-1)+1,xm(s-1)+2,...,xk}.һN,:ͨ,KiĵΪyi,yi(0,...,1,0,...,0)(iΪ1,Ϊ0).i1,2,...,s.
,Ϊ۷,s2,y11,y2-1.
1.2 渲㷨
ף1֪,繹,ȼһ,ܽͬĵָ.,ǸһΪ渲Ƿ㷨.Ҫ˼·:һC1,ֻK1еĵ,K2еĵ,Ȼ󽫱C1ǵĵɾȥ.µĵһC2,ֻK2ĵ,K1ĵ,Ȼ󽫱C2ǵĵɾȥ,...,˽и,ֱK1(K2)ĵȫɾΪֹ.
Ciʱ,ȻϣǵĵԽԽ,Ϊýٵɸǵ,Ҳ,˵õԪԽ.һCiķ(˷δŵCi,һɵõŵ).󷨵Ҫ:áģ򡱺͡ƽƣ򡱽,ýϺõCi.
㷨1. 󽻲渲ǵĲ
ȽK1,K2ĵӳ䵽Sn(Snn+1άռ,ԭ,뾶Rnά,ȡ뾶Rmax|xi|)ԼΪK1,K2.
1:һC(i)(ʼʱi1),ֻסK1ĵ,C(i)ǵK1еӼΪK1i,
K2K1/K1i,K1K2,K1K2Ϊռ,ֹͣ.,ii+1,ص1.
㷨1һǼ,ΪC{C1,C2,...,Cp}.
:
1Ԫ,ȡpԪA1,A2,...,Ap,AiΪӦCiԪ,i1,2,...,p.书ܺΪ.
2ȡһpԪB,ȨֵΪ(u,a),uiaķ(K1Ϊռ,K2Ϊռ,ԼK1ӦΪ1,K2ӦΪ-1):
-a0(ʣµK2Ӧķ),
up-a0(pиķ),
up-1+up-a0
 up-1 ...-a0(p-1еĸķ),
u1+b2u2+b3u3+...+bpup-a0(1еĸķ),
biȡ10,ɸľ.biȡֵ,ʽһн.ȡa1,up2,up-1-2,up-24,һ
͹ɷ,KΪK1K2(ӦK1(K2)еĵ,1(-1)).
ע:󵽵ԪȨϵ,,ָ.Ϊ,ǿһ,ʹȨϵֻ.
㷨2. 󸲸C(i)Ĳ
1:K1K2һǿռ,ֹͣ;(K1)ȡai(ʼʱ,j1,i1)K1.
2:aiΪĵC(ai).C(ai)K1Di,i1,2,...,D0,
C(ai)ӦȨֵ(Wi(wij),ȣ(i)),ɰĹʽ:


id(i),
W(ai),ȣ(i).
3():Di-1DiӼ,Dia-,ai+1 a-,ii+1,ص2.,4.
4(ƽ):aiƽƵa, ai+1a(a󷨼㷨3),ӦC(ai+1)(Cʱ,轫ai-1Ͷ䵽),Di+1.
DiDi+1Ӽ,Di+1a-,ai+1a-,ii+1,ص2.
,CjC(ai),ǾһCj.
Ȼ,Cjǵĵɾȥ, K1jCjK1,K2K1/K1j,K1K2,jj+1,ص㷨1ĵ1,һ.õһ{C1,C2,...,Cp}.
㷨3. ƽ㷨(aƽƵa)
aK1,,d(a,x)ʾaxľ.
1:|B|kn,ȡa䣽a.ɹ,ֹͣ.
,aP(B)(P(B)Bɵ)Ĵb,P(k)P(B),ٶÿxK2/P(k),d(x):

cP(k)еһ.
x:a,c-x0,xck+1,ȡa䣽a,P(k+1)P(k){ck+1}.2.
,
(1)

RSnİ뾶.(a-db)ͶӰSn.ȡck+1x*.
2:P(k+1)P(k){ck+1}(,Ϊ,P(k){ck+1}ʾP(k)ck+1ɵ).
k+1n,aΪ.ɹ,ֹͣ.
,a䵽P(k+1)(ʼʱ,k|B|)ͶӰbk+1,bbk+1,aa,kk+1,ص1.
ͶӰ㷨.
P(k){c1,c2,...,ck}(P(k)㷨3P(k)),aP(k)ɵ(ԼΪP(k)),aP(k)ͶӰ.
ǿһ,ȻͶӰķͶӰ.
P(k)һķΪ
P(k){c1,c2,...,ck},dici-c1, i2,...,k,

,aP(k)ͶӰΪ

,P(k-1),P(k)һʱ,ֻҪek,ͬe1,...,ek-1,͹P(k)һĻ.
Ҫ֤,㷨3,aƽƺõa,aΪ,ֻK1,İ뾶aΪ,ֻK1İ뾶.֤,ͨƽ,п󵽸ǸK1.
1. a,P(k)㷨3жӦķ,aP(k)иľ.
֤:k|B|ʱ,BĶ֪,۳,ùɷ֤.
x:a,c-x0,ɡa,ca,x,ֱӵd(a,c)d(a,x);x*,ȡck+1x*,d(x*),áa-d(x*)b,ca-d(x*)b,x*,d(a,c)>d(a,x*)d(a,ck+1).
2. aa㷨3󵽵ƽƵ,C(a)C(a),C(a)ֻK1ĵ.
֤:C(a)(C(a))a(a)Ϊ,a(a)c(cP(k)еһ)ľΪ뾶,ǪC(a)(C(a))ķΪa,x-c0(a,x-c0).֤,x㡴a,x-c0,xһҲ㡴a,x-c0.
ڵxC(a)ʱ,d(x),ǡa,x-ca-d(x*)b,x-ca,c-x-d(x*)b,c-x,ɡa,c-x0d(x)0,b,c-x0,Сa,c-x0,xҲC(a),C(a)C(a).
,d(x*)Ķ׵,C(a)(C(a))ֻK1ĵ.
12֪,㷨3ƽƵõĶӦ,K1ķΧԽԽ,ҪﵽĿ.
ע:ֻ󸲸ķ֮һ.˷δܱ֤ÿ󵽵C(a)K1ĵﵽ,㷨иĽ.
2ģ
ڸдԵ,ЩӾͿɿķǱ.
1:ƽ˫ߵʶ(ͼ2ʾ).

Ϊ˫ߣ𼰡ʾѵ
ͼ2ƽ˫
K1ڼϵrϵӼ,K2ڼϵrϵӼ,/2ܦȡ6.
K1(K2)ϸ77,ֵΪȣi/2,i1,...,12,Լ/2,ȡȷֵ,е3/2ȡȷֵ,һi/2(i+1)/2ȡi+1ȷֵ.
һǰ,K1,K2ֿ.ѧϰѧϰ֮һ.
ף2,RaumBP㷨˫,ʧ.ף3,Chen-,˫ѧϰ,3 000εĵ,õһ,˽ʶȷֻ89.6%.ף4,Fahlmanáʽṹǿ˫ѧϰ,õҪüʮԪ.ɼѶ.ý渲㷨,õ˷ǳĽ.
:ý渲㷨,1㹲10Ԫ(ͼ3ʾ,ԲǸڶάƽϵͶӰ).2һԪ,繲11Ԫ.ķȷΪ100%.


(a)ѵΪ˫156㡡(b)ѵΪ20 000ݵ
ͼкɫʾֵĵ1ĸ,ɫʾ2ĸ,𼰡ʾѵ
ͼ3θǷƽ˫


Ȼr(r)ȡ1Ϊ,õʶ,ȷʴﵽ98.245%.,K1,K2ϸȡ1Ϊ,Ȼѧϰ,Եõ10Ԫ(ڶάϵͶӰͼ3(b)ʾ),ʱȷΪ100%,иȡ1ʶ,ʶȷҲﵽ99.995%.
,ǻƽߺάռߵѧϰ,õ˷ǳĽ,1.
1ý渲㷨ѧϰ

ѵ
()ѧϰʱ串
()ʶ(%)
ƽ˫1 (156)
2(20 000)1ms
5.16s10
10(20 000)
(20 000)98.245
99.995
ƽ1 (234)
2(30 000)0.06s
14.61s24
26(30 000)
(30 000)91.11
99.067
ռ1 (183)
2(30 000)0.07s
19.34s28
37(30 000)
(30 000)96.293
99.653


2:άռߵʶ.
ϵ,K1{(,r,z)|z,r1,0ܦȡ4},K2{(,r,z)|zȣ,r1,0ܦȡ4},һǰ罫K1,K2ֿ.
ע:2һʶ,(BP㷨)޷.ñṩķ,ԱȽԲؽѧϰ.
:ý渲Ʒ(Ҫ󸲸סK1,K2ϵе)õ,110Ԫ,21Ԫ.
K1K2Ϲȡ30 000,õʶ,ȫʶȷ.
ӿԳ˵ƷЧ.㷨(ָĽBP㷨)ƽ൱ѵ. 
3
M-PԪģ͵ļóһ򸲸ǵ㷨.㷨һϿǵĽṹŻ(ָĹģС),ҷʵ,Ӷ˶һֱδܺܺõصõĶǰ.ĸļģҲ˵˱Ǳ.
,ĸ㷨ֻ򸲸㷨еһ,κһС(С)㷨뱾ԭ,ɵóһµ㷨.͸о⿪һ;.
л廪ѧͬѧΪĵı1ṩģ,ڴ˱ʾл.
оõȻѧ͹863߿ƼĿ.,1937,,ҪоΪ˹,˹.,1935,,ʿʦ,йѧԺԺʿ,ҪоΪ˹ۼӦ,Ӧü.󺣷,1970,˶ʿ,ҪоΪ˹ۼӦ.
ͨѶϵ:,Ϸ230039,մѧ˹о
ߵλ[š壨廪ѧܼϵͳصʵҡ100084󺣷(մѧ˹оϷʡ230039)]š(廪ѧѧ뼼ϵ100084廪ѧܼϵͳصʵҡ100084)
E-mail: zling@mars.ahu.edu.cn
ο
1,.M-PԪģ͵ļ弰Ӧ.ѧ,1998,9(5):334338
(Zhang Ling, Zhang Bo. A geometrical representation of M-P neural model and its applications. Journal of Software, 1998,9(5):334338)
2Baum E B, Lang K J. Constracting hidden units using examples and queries.In: Lippman R P et al eds. Neural Information Processing. San Mateo, CA: Morgan Kaufmann Publishers, Inc., 1991. 904910
3Chen Q C et al. Generating-shrinking algorithm for learning arbitrary classification. Neural Networks, 1994,5(7):14771489
4Fahlman S E, Lebiere C. The cascade-correlation learning archtecture. In: Tourdtzhy D S ed. Advances in Neural Information-processing System. San Mateo, CA: Morgan Kaufmann Publishers, Inc., 1990. 524532
1998-01-16յԭ 
1998-08-24յ޸ĸ
