Luận văn Một số thuật toán học trên bảng quyết định

2 MANG N<1-RON. PERCEPTRON ) ' tu'dngv~nhungmohinhm~ngno-randaulienkhdidautU nhungDam1940.Vaoh1cd6,hainhaloanhQcMcCullochva Pitts(19 3) g<;liY v~mQtno-rollnhu'mQtphdnIlt nguiJnglogic(logical thresholdelement)c6haitr~ngthaikhiidi.MQtphantitngu'cJngnhu'the' c6n kenhchoduli~unh~pva mQtkenhchoduli~uxu!t.Kenhchodu li~unh~pdu'<;lccoiladQngne'udauvaola 1,ho~ccoila tinhne'udauvao la O.Nhu'v~ythongtinnh~pdu'X2,U? Xn.Thongthu'ongdaynhiphannaydu'<;lccoi la nhungthanhphancua vecto x =(Xi> X2, U?xn) Tr~ngthaicuaphantitngu'cJngchobdi t6h<;lptuye'ntinhcuacae tinhi~unh~pXidemsosanhvoi mQtgiatringu'cJngs.Tin hi~uxu!tcua mQtno-rolldinhbdihamoutput: y =o(L/w/x/-s) (1) trongd6agQilahaml!y ngu'cJng:o(x)=1ne'uX>0va o(x)=0ne'uX< 0, va caeh~s6Wi=+1. Qua d6, ngu'oitan6i no-randu'<;lckich ho~tne'ut6 h<;lpI;WiXi trQi hon ngu'cJngs . Con trongtru'ongh<;lpngu'<;lcl~i, no-roll d6 du'<;lcgQi la tinh. Hai ongclingdachiraeachthucmamQtno-rollc6 th€ tht1chi~n cacpheploanlogic.Chiingh~n,ho~tdQngcuacacc6ngAND trong19 thuye'tm~chlogicho~cvoicaebQchuy€nm~ch(inverter)thid~uc6th€ di~ntiidu'oimQthamtheod~ng(1). Mllingno-ranperceptron 11 Tuynhien,c6haikhiac~nhquaDtrQngmamohlOOcuaMcCulloch va Pittsdii khongghliquye'tdu'<;1c.Thanha't,mohlnhtrendiikhonggiiii thichdu'<;1cca hiliacmacacnd-ronlien l~cvoiOOau-tie'cthay-d6 l~ila mQtth1!cte'xiiy ra trongsuo'tquatrloohQccuamQtm~ngnd-ron.Tha hai,nhii'ngm~ngnd-rondohaiongd~rakhongphiinanhdu'<;1ckhiiDang chiu16i,nha'tlakhisosanhvoikhiiDanga'yndiOOii'ngnd-ronsinhhQc. Saunay,nhovao Dang11!cuanhii'ngh~tho'ngtioo loanmoi, nhii'ngnhaphattri€n dii c6 th€ mophongmQtcachchi tie'thdnv~khii DanghQCcuaOOii'ngm~ngnd-ronvadiineudu'<;1cca liinhv1!cangd~ng mamohlnhcuahQc6khiiDanggiiiiquye't. Mo hlOOddngiiinxetdu'oidayla m~ngperceptrondoRosenblatt d~ravaoDam1948. 2.1M~ngPerceptron: M~ngperceptIonmQtlOpla mQtmohlnhddngiiinmachungtase xettrongchu'dngnay.N6 chig6mN ddnvi nd-ron,trongd6m6ind-ron c6chacDangcuatie'pnh~nthongtinquankeOO,dii'li~udiquam6ikenh d~ctru'ngbdiXl .Thu'ongthu'ongdii'li~uquam6ikeOOmangmQtrong haigiatri0 hay1.CungvoichacDanginput,nd-ronilia r trongm~ngc6 hamoutputdinhbdi: Yr=O(LiWriXi- sr) (2) voi {Wri}la t~pcactrQngso'xacdjnhchond-ronilia r vaSrlangu'ong. Khongma'tinht6ngquat,congiliac(2)c6th€ vie'thaOO: Yr = O(LiWriXi) voi Wro= Srva Xo= -1. (3) Ne'um~ngperceptIonchi g6mmQtddnvi nd-ron,ta n6i d6 la m~ngperceptIonddnnd-ron. Kie'ntrUccuamQtm~ngperceptIonhu'motittrenchu'atriiloi cho Callhoi v~cachiliacho~tdQng.Va'nd~d~tra la: voi mQt~p hii'uh~n nhii'ngthongtinnh~px, vavoimQt~pconCrchos[n,ngu'oitamuo'ntlm du'<;1Ct~pnhii'ngtrQngso'{Wri}saochoylx) =1voi mQix 6 Crvaylx) = 0 voix {l!Cr. M~ngno-ranperceptron 12 Quatrinhxacdinhnhii'ngtrQngs6{Wri}du'<;fcgQila quatrinhhQc. Va nhii'ngthu~tloanap dt}ngchoquatrinhhQcgQila thuq,thQc.N6i chung,mQtquatrinhhQCdic3nranhu'san:ngu'CJitakhdit~omQt~ptrQng s6{Wri}bandftunoino-rOllr, sand6chonhii'ngtrQngs6naylacdQngten tUngvectoinputx IDeocongtht1'c(3).DI nhien,sec6nhii'ngvectdx e Cr nhu'ngylx) =0 .Luc d6 ngu'CJita phiH di~uchinh trQngs6 {Wri}bhng s6 gia L1Wri. T~pnhii'ngtrQngs6cu6iclingdu'<;fcchQnkhichungphant1'ng dungvdi mQix eCr . Trongchu'ongnay,chungtakhaosatnhii'ngthu~t hQctrenm~ngperceptrondonno-roll. 2.2Tlnhkhatachcuakhonggiannhungvacta'hQc: B€ c6th€ xacdjnhdu'<;fC~pnhii'ngtrQngs6 {Wri}cu6icling,di~u d6mythuQcvaobancha'tciiabai loanva vaocachmah6amftunh~p. B€ giai thich, chung ta hay xet y nghia hinh hQc ciia qua trinh hQc. Nhii'ngmftuhQcx = (x],X2,"7XL) du'<;fcxemla nhii'ngvectdtrongkhong gianL chi~u,trongd6, t~ph<;fpCr sedu'<;fctachkhoi nhii'ngvectdkhacbdi sieuphiing: WrlX]+Wr2X2+ ". +WrLXL= Wo Ngu'CJitada neudu'<;fCnhii'ngphanvi dt}v~mQtkhonggiannhii'ngvectd hQcmakhongt6nt~iba'tct1'sieuphiingnaod€ tachchung. 2.3Tlnhkhatachtuye'ntinh: B6i vdihait~pmftuthll'C] vaC2 makhongth€ tachdu'<;fCbdimQt si~uphiing,ngu'CJitasemdrQngs6chi~uciiaciiakhonggianvectdthll' va anhx~t~pC] va C2 vaokhonggiannaysaochoc6 th€ tachchung bhngmQtsieuphiing. [JO :> M~ngnd-ronperceptran 13 TinhchathlnhhQCaydu'<JcgQila tinhkhatachtuytntinh.Nhu'v~y, tinhkhatachtuye'ntinhnhhmbaodamluonluonc6th~chQndu'<Jct~p cactrQngs6 {Wri}saochobai loanphanlo~icacvectdthax c6th~giiii du'<Jc. Trudckhitimhi~ucacthu~thQc,chungtahayxetquamQts61Inh vl{capd~ngcoam~ngperceptron. 2.4. MOlso'linhvileapd~ng D Vi dlf-1:Vdi mQtlOpc6giOih~nnhii'ngb~liloanvi ttr,chiingh~nOOu' xetphatbi~u:"Loandiphffntu troindnghayntu troi l{lnhvagi6 thdihuangdong".TagQinhii'ngvi ttr: Xl: "TroinAng" X2:"Troi l~nh" X3:"Gi6th6ihu'dngdong" y: "Loandiph6" va gQichantri cuachungHi1 ho~cO.The'thid~xacdinhh~illh dQng"Loandiphff"la dunghaysaingu'oitac6 nhieueachthl{c hi~n.N6ichung,ngu'oitasehmtrii'bangchantricoay: Bang2.1..Bangchantrj........................................................................... :.1::::::::::::::::::::::::.:::::::::::::::::::::::0::::::::::::::::::~::::::::- 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 va saud6,vdimQtth~hi~nnaod6coavectd (x],Xl,X3) ngu'oitased6i sanhvectdnayvdido8 tru'ongh<Jptrongbangchantrid~rutramQtke't lu~nvey.R6rangcachtie'pc~nnayc6dQphuc~p2£dod6khongthich M\ingno-ranperceptran 14 hQpvoi nhfi'ngtruonghQpmakhonggiannhfi'ngvectdhQcco s6chi~u khaIon. Clingvoim1;1cdichthugQnbangchantri,nguoitathilydingBang 2.1.coth<3'rutgQnthanhBang2.2nhusauday Bang2.2.a:Bangchiintrj dttqcthugQn [::::::i::I::::::::::i:i:i:::::i:::ii:::::::::::::::::::::::5.li:::::i:i::::::::::::::::::I:::::::::I::::1 0 0 * 0 0 1 0 0 0 1 1 1 1 * * 1 (*) Chiintrj ia 1ho(ic0 Tac gia Celko trong[CELKO] d~nghimQtthu~toansa d1;1ng Bang2.2.phatsinhmQtdo(;lnchuangtrinhcod(;lngnhu: IFX1THENY ELSE IFX2THEN IFX3THENY ELSEERROR ENDIF ELSEERROR ENDIF ENDIF Ca che't1;1'dQngphatsinhchuangtrinhIDeogQiy tren, ne'uth1;1'c hi~nduQc,coynghHikhad~cbi~tvi dochinhla cache'phatsinhchuang trinh,C1;1th<3'la no phatsinhdo(;lnchuangtrinhphucV1;1vi~cl~plu~ntie'n trongdonvi maysuydi~ncuabiltcll'h~chuyengianao(Xem Chuang1). va clingdocache'phatsinhchuangtrinhd1;1'av ocdsdtri thll'c,tathilyca che'ily th1;1'cs1;1'dfft(;loduQcs1;1'dQcl~pgifi'adfi'li~uva chuangtrinh.Diiu nay cung co mQtynghiiiquantrQngnhatia trangnhangh? chuyengiama cosa tri thacthtti'lngco nhangbie'ndQngtheothi'ligian,chungtamu6nh~ Ml)ngno-ranperceptron 15 chuyengianayphiiic6 khananghQcnhanhch6ngnhatm6ikhi c6 stf bie'ndQngv~cosdtrithuc.Thu~tloannaymdranhungungdI}ngthuvi chiingh~ntrongvi~ct\f thie'tke'nhungh~CASE la nhungh~trQgiup phftntichthie'tke'h~th6ngho~cl~ptrlnhchonhungthie'thi di~ukhi~nt\f dQng.van d~conl~ila thu~tloanphatsinhchuongtrlnhay phaic6dQ phuct~pchapnh~nduQC. Cu6idIngla cachtie'pc~nno-rOll.Vdi phuongphapnay,ngucsita khonghill tri'i'bangchftntri-haycongQila banghanhdQng-nhungse duy~tquatUngth~hi~ncuavectdx d~cu6icungxftydtfngduQcham output y =a( -1 +2x]+X2+X3) HamoutputnaykhilacdQngtrentUngvectddongcuaBangquye't dinh2.2,tasethayn6phananhdungvi~cphftnlOpnhungvectdnaose chooutputla 1haysechooutputla0nhutrongBang2.2.b. DVf dl!-2: PerceptIonconc6 mQtungdI}ngkhactrongvi~cnh~nd~ng mfiumanhungn6ltfcbandaDthuQcv~Rosenblatt(1962),Minsky va Papert(1969).Vdi mQtmfiuchosan,ngucsita chie'ulen mQt ludig6mnhi~u0 vuongnho,m6i0 vuongduQcgallchobie'nXi . Bie'nXic6giatri i ne'umfiuthitc6baophu0 vuongvac6giatri0 trongtru'csnghQpnguQcl~i.M~ngperceptIonc6 Iihi~mVI} hQc phftnlo~icacmfiuhQcbhngcachduy~tquatUngthitd~cu6icung xftydtfngduQchamnguangy.Lay vi dI}tac6mQtludig6mb6n0 M~ngna-ronperceptron 16 vuongva 16mallhQcphanlo~ithanhhaiph~mtrU:Ph~mtrUfull' nh!tg6mnhiingmallco it nh!thai0 t6ik~nhauva ph~mtrUfull' hai g6mnhiingmauconl~i.C~thc3'k6tquaphanlo~ichatrang Bang2.3.dudiday: Bang2.3:Phanlo{limJug6m40 vuong Dudiday,chungtasexetnhiingthu~thQcd6i vdi mohlobperceptIon donno-roo. 2.5.Mil hinhperceptronilltn nit-ran: Trudc h6t chungta dinh nghHiham y =f(x], X2, ..~ XL) la ham nguongtuy6ndnhobiphanll'ngvdibi6nnhiphanx],X2,. . .,XL n6ut6n ~i mQts6th1;1'cTva day s6th1;1'c{w],W2,. . .,wd saochoy=1 n6u LW/X/ >T vabAng0 trongtru'onghQpnguQcl~i. Trong th1;1'ct6, chungta se coi Wo=-T vab6 sungbi6nXo=1. Khi dohamnguongtuy6ntmhselahamtheocacbi6nXo,X/,. . .,XLvacogia triy =1 n6u.EWjXj>0 vay=0 n6u .EWjXj<-0 (t6nglay theoi =0,1, ...). 2.6.Thu~thOcreinforcementchom~ngperceptronilltnnltron D6i vdi m~ngperceptIondonno-roo,co phuongphaphQcda tra thanhc6dic3'ngQila lu~thQcreinforcement.NQidungcd~phuongphap nhugall: ................................... ......................................................................................................................... ::.:::::.:II:I!I!I:I:I .................................... ................................... 11:ljl:111111111111:IIIIIIIIIIIIIIIIIIIIIII::!lj ................. ............... .................. 11111111111111111111111 ....................................................................... .................. I!IIIIIIIIIII!III!!!!I!IIIIII .................................. .............. .................. !IIIII!IIIII!IIIIIIII ................................. .................. ::!I!!!I!::II!I!I!I!I!! ................. ............................................... :::::!!ii: ::::::::: . ... ... ............... ::::::::::B:::::::::::lil:::::: ::: 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 M~ngno-ranperceptron 17 Gia Saco N m~uhQCHinhungvectd x =(x], X2,...,xn)E Rll va chungthuQcmQttronghailopmachungtakyhi~uIanIu'<;1tIa G+va G-. Mvc dichcuachungta Ia xaydl;l'ngmQtanhX(;lg xacdinhlIen nhung m~uhQcvacomiengiatri Ia t~ph<;1p{a,I} saochokhichoanhX(;lnay lacdQngIenm6ix thlg(x)=1 ne'ux E G+vag(x)=0 ne'ux E G-.AOOX(;l gthu'ongIah0vaa(s)=0ne'us<0 voi mQtanhX(;ltuye'ntinhf xacdinhlIen x: y =lex)=WoXo+WjXj +W2X2 + ...+WnXn g(s)=a(f(x)) trongdoXo= 1 va cacs6thl;l'cWi( i = 0,1,2, ...,n ) du'<;1cgQiIa trQngs6cuaanhX(;lf vavectdw= (wo,WI,W2,...,w,Jdu'<;1cgQiIa vectd trQngs6.Di nhienvoimQtvectdtrQngs6w naodothlcoOOungvectdx trongG+ nhu'nga(f(x))=0vangu'<;1cI(;li iingconhungx trongG- nhu'ng a(f(x))=1.Trongnhungtru'ongh<;1pOOu'the',tanoico sl;l'khacbi~tgiua outputhl;l'cte'va outputIy tu'dng.Nhi~mvv cuathu~thQcIa voi mQt vectdtrQngs6wchQntuyybandati,sankhichohamg lacdQng!entung m~uhQcx vaconhungdieuchinhtrQngs6thichh<;1pmachungtagQila quatrlnhhQc,hamg sephanaOOdungsl;l'tachkhonggiancacm~uhQc theonghHiIag(x)=1voimQix E G+vag(x)=0 voi mQix E G- Vi dl1: Xet nhungm~uhQctrongR2va outputIy tu'dngcuachungcho trongBang2.4sanday Bang2.4:CaemJu thitvaeaeoutputly tLlang ., "'"..,....................................,.........................................................................................-...".'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'...'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'...'.'.'.'.'.'.'.'.'.'.'".".'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.'.''.'.'.'.'.'.'.'.'.'.'.'.'.'.' :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: '""""""$:"""""""""""""""~:""""""""""""""""'V""""""'" ::r:r ¥.trrrrr r:xIi :r::::::::::r:t::::~Jrrr 0 0 0 1 0 0 1 1 0 1 0 1 M~ngno-ranperceptron 18 Voi mQivectdmftuhQcchotren,tab6 sungthemthanhphftnXo= 1.Va ne'unhfi'ngtrQngsachQnd lftndftulien la w(O)=(0.5,1,-1) thioutputhl1cte'cuanhfi'ngvectdmftuhQcchotrongbangsan: Bang2.5:CacmJu thitmarQngXo,outputly tLlangvaputputthl!Cte ,---~H---,~'HH'~-- """" " ,.................................................,..., , , ," ,." , ,..................................." ",., " ,"""""""""","""""""""""""""'" ,.................................. ::1:::;11111:1:::::::11:11111:1::11::1:1::::::::::::::::::::::;:::i~:::::::::::::I:llllliiliiiiil:~::ii:::::::i:::::::::I:iillii:i::ii:i 1 1 0 0 0 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1 Co haivectdduQcphanlOpsai,dolahaivectd(1,0,0)va(1,1,0) . Quyt~chQcthanh3.'tduQcgQila hQcdiaphLlongphatbienla chungtase di€u chinhtrQngsangaykhiphathi~ncosl1phanlopsaiIDeoquyt~c: Va quyt~chQcthahaila hQctoanc¥cduQcphatbienb~ngcong thacdi€u chinhtrQngsa w(k+1)=w(k)+ 8 (LXi -Lxj) voi mQiXi E r w va Xj E T"w Trongcahaiquyt~c,tagQi8 la h~s8tdcdQhQc.Ta gQiquyt~c thahailahQcloancl;lcvi anhx~tuye'ntinhf voivectdtrQngsaw sephai lacdQngtrent3.'tcanhfi'ngvectdX trongtungbuochQc.Bdi cooouthe' thit~ibuochQcthakchungtamoicothexacdinhduQchait~phQpr w vaT-w.Trongvi dl;lchungtadangxet,cacbuocdi€u chinhtrQngsatrong suatquatrlnhhQcloancl;lcduQcphanaOOquaBangsan: w(k) neuphan lcJpdung w(k+1)= w(k) + &Xi neuXi Erw w(k) - &Xi neu Xi E T"w M\lngno-ranperceptron Bang2.6:Cac buochQc * 0 w 0.5 1 -1 N/A (1,0,0)(1,1,0) ~w -2 -1 0 w -1.5 0 -1 ~w 1 1 1 w -0.5 1 0 ~w -1 -1 0 w -1.5 0 0 ~w 1 1 1 w -0.5 1 1 ~w -2 -1 -1 w -2.5 0 0 ~w 1 1 1 6 w -1.5 1 1 tJ : khongc6 1 2 3 4 5 19 (1,1,1) N/A N/A (1,1,0) (1,1,1) N/A N/A (1,1,0)(1,0,1) (1,1,1) N/A N/A N/A QuatrinhhQCcha'mdti't~i badcthti'6VIkhi docact~ph<jpr va T- cact~ph<jpr6ng,mcHikhongconvectOmfiuhQcnaobiphanIdpsai. Theod5iquatrinhhQCcuamQtm~ngperceptronddnnd-ronnha minhhQatren,mQtCallhoid~trala li~ucoxayratru'CJngh<jpsaumQts6 huuh~nbadcdi~uchinhtrQngs6,chungtal~iquaytrdv~dungvdimQt tr~ngthainaodo makhongbaagiCJd~tde'ntinhtr~nghoanchinhv~ trQngs6?Tacodinhly sauday BinhIV 2.1 TrongsudtquatrlnhhQccila mi)tm{lngperceptrondanna-ron, nguiJitakhongbaagiiJ quaytrov~cungmi)ttr{lngthainhi~uhan mi)ttanneubili loanc6liJi giai. M~cdudinhly chobie'tdingtrongquatrinhhQc,m~ngkhongbaa giCJquaytrdv~cungmQtr~ngthai,nhangdi~udokhongconghHilaqua trinhhQcsecha'mdti'tsaumQts6huuh~nbadchQc.Tuynhien,chungta co dinhly saudaykhiingdjnhstfhQitl}.cuaquatrinhhQccuam~ng perceptronddnnd-ron. M~ngno-ranperceptron 20 Blnh IV 2.2 Trong trulJnghf/phQctoimCf:lChayhQcdiq.phuong,cac trQngsd w(k)sf!hQitf:lv~vectow ntu khonggian cac mt1uhQcia khd tach tuytn tinhva ntu cac diiu ki~nsauvi h~sd tdcdQhQcdUf/cthod man: 1. 2. c:(k) >o. limZZk=lc:(k)=co khim ~ co 3. limZZk=iCc:(k)l/(ZZk=lc:(k)l=0 khim~ co [VLENTURF] conchirar~ng5t!hQin,.cuaquatrinhhQcvftncon baodamne'uc:(k)=1 / k hay th~mchi c:(k)=k. Ne'ut~pcacmftuhQc khongkhatachtuye'nHnhthi 5ieuph~ngtachkhonggianmftu5edao dQngquanhmQtvai vi trid:Jcbi~tne'uh~56c:(k)dtt<;jcchQnla hAng56 hayla mQtday56tang. 2.7. PhU'o'ngphapbangch6t Ke'tquachinhcuachttdngnayla vi~cungdl;lngphttdngphapbang chdt,v6ndungchonhllngbai loanquyho~chtuye'ntiOO(Xemtai li~u [SDGWICK]),nhAmtill cactrQng56chohamngtt5ngtuye'nHOOma khongcftnquacacbttdcdi~uchinhtrQng56OOttronghaithu~thQcdi~ phttdnghayloancl;lCn6itrongtie'ttrUdc.Trudche'tchungtadinhnghia the'naolamQtbangch6t. Cho 5[n mQtmatr~nA =(aij)nhttdttdiday aQl aO2 aOL all al2 alL aNI aN2 aNL M~ngno-ranperceptron 21 Khi dobangch6tungvdiph~ntt1'a[p,q]Ia IDatr~nco duQcbhng cachbie'nd6i IDatr~nA theodongsaochothuduQcIDatr~nIDaph~ntt1' t~idongp thlbhng1vatatcacacph~ntt1'khaclIencQtqthlbhngo. £)6rninhhQaphudngphapbangch6t,chungtaxetke'tquaphan ldpcuab6nvectdchotrongbangsau: ttttt:rr:Hft:rrrr:::tttt:I:trrrrr':'t::t::::::::ti ,:::IIiQ::::::::::::::::::::l~-:l:::::::::::::III~~:::l::::::::::::::l::oo::::l:::::: 1 I 0 0 0 I 0 0 1 1 1 1 0 1 0 1 Chungtarnu6nurnrnQtanhx~tuye'ntinhf vdi cactrQngso'{Wi} saochokhif lacdQngIentUngvectdthl: f(1,0,0) =Wo f(1, 0, 1)=Wo+Wz f(1, 1,0) =Wo+WI f(1,1,1)=Wo+WI +Wz Chungtasexacdinhnhfi'ngtrQngso'{wo,Wj, wz}saocho: Wo<0 Wo+Wz<0 Wo+WI <0 (1) Wo+WI +Wz>0 VI tachic~nurnrnQtnghi~rncuah~batphudngtrlnh(1)nentaxeth~ batphudngtrlnhd~cbi~t: M~ngna-ronperceptron 22 Wo< -1 Wo+ W2< -0.5 (2) wo+wI<-0.5 Wo +WI +W2 >0.5 B~ dungphu'dngphapbangeh6t,taphatbi~ubai toan:"TImmQtgia trj cothl!cua Wo+WI +W2 sao cho cac Wi thoabtitdangthac(2)".Be'ndfiy bailoandu'Qegiaiquacaebu'de: Bltoc1:TITh~bfttphu'dngtrlnh(2),tathftyr~ngt6nt~inhfi'ngiatriYo, Yi>Y2,Y3 >0 saoeho: wo+Yo=-1 Wo+W2+YI =-0.5 (3) Wo+WI+Y2= -0.5 Wo+WI+W2- Y3=0.5 Bltoc2: L~pmatr~ntrQngso'g6mtftteanhfi'ngh~so'euah~phu'dng trlnh(3) -1 -1 -1 0 0 0 0 0 1 0 0 1 0 0 0 -1 1 0 1 0 1 0 0 -0.5 1 1 0 0 0 1 0 -0.5 1 1 1 0 0 0 -1 0.5 Mi;lngno-ranperceptron 23 Dongthnnha'tcuamatr~nchinhlacach~s6cuawo,Wj,Wztrongh~thnc Wo+WI+WzduQCIa'ynguQcda'u.Trangcactinhloanti6ptheodongthn nha'tcuamatr~nh~s6chico lacdvngki€m ITak6tqua. Blloc3:L~pbangch6tchonhfi'ngphantii'manga[p,q]voip,qchQnthich hQp. - Bangch6tcuaa[2,1] 0 -1 0 0 1 0 0 -0.5 0 0 -1 1 -1 0 0 -0.5 1 0 1 0 1 0 0 -0.5 0 1 -1 0 -1 1 0 0.0 0 1 0 1 -1 0 -1 1.0 Ti6p theochungta Hmnghim WI trongvectcJcQtthnhai bhng cachlily bangch6tchophantd'a[4,2] 0 0 0 1 0 0 -1 -0.5 0 0 -1 1 -1 0 0 -0.5 1 0 1 0 1 0 0 -0.5 0 0 -1 -1 0 0 1 -1.0 0 1 0 1 -1 0 -1 1.0 Nhutrongbuoctren,d6ivoi nghim thnba,talily bangch6tcho phantd'a[1,3]vathuduQcmatrn sail: 0 0 0 1 0 0 -1 0.5 0 0 -1 1 -1 0 0 -0.5 1 0 0 1 0 0 0 -1.0 0 0 0 -2 1 0 0 -1.5 0 1 0 1 -1 0 -1 1.0 M~ngnO'-ronperceptron 24 Be'ndaytaco th~chQnnghi~mdin tlmHi (wo,Wj,wz)=(-1.0,1.0, 0.5)va nghi~mnay thoaHnhchill Wo+ WI + Wz=0.5. Ghi tri naydu<Jc ki~mtrabhngphftntU'cu6itrongdongdftuliencuamatr~n.SaukhichQn du<JcaetrQngso'Wi thlhamnguongcuall(j-ronsecod~ng: Y = a(-1 +Xl +0.5xz) D~dangki~mchungthilyhamnayphananhdungbangChaDtricuabai loan. Vi~ccaid~tthu~tloand~chQndu<Jcbangch6tcu6iclingkhong khoHim.Viln d~Ia eachchQncaehhngso'd ve'phiiicuah~bittphuong trlnh(2).KhongphaibittcueachchQnnaoclingd~uchoke'tquamong mu6n.Chiingh~ntrongbittdiingthuccu6icuah~bittphuongtrlnh(2),ta chohhngso'd ve'phaibhng1.Cl;lth~chungtacoh~bittphuongtrlnh: Wo<-1 Wo +Wz <-0.5 Wo+WI <-0.5 Wo+WI +Wz>1 vaclingvoigiathuye'tt6nt~inhii'ngiatrikhongamYo,yj,Yz,Y3saocho tacoh~: Wo +Yo=-1 Wo +Wz+ YI =-0.5 Wo+WI +Yz=-0.5 Wo+ WI + Wz- Y3=1 thlchungtasecomatrn h s61a: -1 -1 -1 0 0 0 0 0.0 1 0 0 1 0 0 0 -1.0 1 0 1 0 1 0 0 -0.5 1 1 0 0 0 1 0 -0.5 1 1 1 0 0 0 -1 1.0 M~ngnet-ranperceptran 25 Lftn luQtlily bangch6tchonhfi'ngphftntU'manga[2,l], a[4,2],a[1,3] thi bangch6tcu6icling: Cactn,mgso'chobdibangnayla (-1.0,1.5,0.5)nhunghamnguBngtuye'n tinh y =a( -1.0+1.5xj+0.5x2) thikhongphananhdungbangChaDtrio DI nhien,chungtaphiiidi~uchinhcachchQnve'phaicuah~biltphUelng trinh(2).Biingcachnao?Nh~nxetriingcactrQngso'Wimu6nla nghi~m duQcchQnthiphaithoabiltdiingthuc: -Wo<Wj +W2< -2wo. daDde'nvi~cchQnWoco mQtgia tri IonhelD.Chiingh~nco the'chQnWo< -1.5. 0 0 0 0 0 0 -1 1.0 0 0 1 -1 1 0 0 0.5 1 0 0 1 0 0 0 -1.0 0 0 0 -1 1 1 1 -1.0 0 1 0 0 -1 0 -1 1.5 0 0 0 0 0 0 -1 1.0 0 0 1 -1 1 0 0 1.0 1 0 0 1 0 0 0 -1.5 0 0 0 -1 1 1 1 -0.5 0 1 0 0 -1 0 -1 1.5 M~ngno-ranperceptran 26 Luc nayhamnguongtuye'ntinhchQnduQc: t =a( -1.5+ 1.5x]+X2) chungta co th~ki~mchungd~danghamnguongnayphananhdung bangchantrio 2.8.ChUfnhiQ'C I~pbangch6t: £)~co cainhinmangtinhcachthu~tgiaidO'ivdiphuongphapneu trongvi dl;llIen,chungtadungtrudcva'nd~din philitimmQtchie'nluQc chovi~cxacdinhxemphantit alp, q] naGse duQcchQnd~l~pbang chO't.Trentinhthanapdl;lngphuongphapdonhinhcuanhii'ngbai loan quyho~chtuye'ntinh,chie'nluQcchQnphantitmangalp,q] d~l~pbang chO'tphaichochungtanhii'ngtrQngsO'{Wi}saDchohamml;lclieu LWi tangdande'ngiatri ldnnha't,noicachkhaccacthu~tgiaiphaichoduQc gia tri {Wi}Ia tQadQdinhcuadonhinh.Theo [SDGWICK],co mQtsO' chie'nluQcchQnphantitalp,q] d~l~pbangchO't,machungtasedung mQtphuongphapnhumatadudiday: CQtq duqcchr,mne'udduVaGtfli dong0 ia s6 am.Dongp duqcchQn trongs6 nhangdongco dduVaGtfli cQtq ia s6 duangva ia pht1nt11 chothuangs6 wJi phdnt11cu6itrendAngmQtdongmanggicitrj nho nhdt. Chungtahayxeml~imatr~nh~sO',tatha'ycQt1 co datiVaGt~i dong0 Ia -1. -1 -1 -1 0 0 0 0 0 1 0 0 1 0 0 0 -1 I 0 1 0 1 0 0 -0.5 1 1 0 0 0 1 0 -0.5 1 1 1 0 0 0 -1 0.5 M~ngnd-ronperceptron 27 V~ycQt1dU<;1CchQn.Baygiod~chQnph~nhi'trendong,chungta chQndong2 (tinhtu0)vi ph~ntUa{2][l]chothuongsavaiph~nhi'cuai trenclingdongc6 ghl tri la 0.5la ghi tri nhonha't.Va thlJ'chi~nphep bie'nd6itheodongd~trdthanhmatr~n £)~till bangchatlingvai mQtph~nhi'naod6trencQt2, chungta se chQnIlJ'agiuahai ph~nhi' la a{3,2]haya{4,2]?Ne'uchQnph~nhi' a{3,2]d~l~pbangchatchungtatha'ydng vi ph~ntti'cuaitrendong3 b~ng0 chonenbangchatdU<;1cl~ptuph~nhi'a{3,2]thonglamchogia tri cuaph~ntti'cuaicuadong0 tanglen.Trongkhi phuongphapbang chatla till nhungbangchattheohuanglamchoph~nhi'cuaicuadong0 tangd~nlen de'ngiatri Iannha't.Do d6chungtase till bangchatcho ph~ntti'a{4,2] Va quatrinhchQnph~ntti'trongbangchatd buacthak d~l~p bangchatchobuacthak +1tie'pl\!Cchode'nbangchatcuaila bangc6n cQtd~uliendiidU<;1cchuiinhoa. 0 -1 0 0 1 0 0 -0.5 0 0 -1 1 -1 0 0 -0.5 1 0 1 0 1 0 0 -0.5 0 1 -1 0 -1 1 0 0.0 0 1 0 1 -1 0 -1 1.0 0 0 0 1 0 0 -1 -0.5 0 0 -1 1 -1 0 0 -0.5 1 0 1 0 1 0 0 -0.5 0 0 -1 -1 0 0 1 -1.0 0 1 0 1 -1 0 -1 1.0 M\tngno-ranperceptran 28 2.9. Nh~nlet Trongphuongphapbangch6ttren,buoctimcachhngso'd~di€n tacacrangbuQcnhutrongh~biltphuongtrinh(2)cuatie't2.7.du<;lcthV'c hi~nbellngoaithu~tloanvaxemnhubuocphantichsobQ.H~nche'cua phuongphaptrend ch6nochuachomQtthut1;1cnaogiupcaid~tcach~ so'cuah~biltphuongtrinh(2)mQtcachheuristic,makhi lingd1;1ngcho cacmfiuhQccoso'chi~uIOnthibuocnaydatrdthanhmQthachthlicIOn. Vi d1;1trongtie't2.7tu'ongd6idongianvi ch~ngquabangchantri cuabailoanchinhIa dinhnghiacualoantitlOgicAND, so'chi~ucuacac vectomfiuhQcquanhosovoi cacbai loanthV'cte',chonenvi~cdi~u chinhcacgiatri cuacQtcu6iclingtrongmatr~nkhongt6ncongnhi~u l~m(thu~tgiaimotatrenkhongh~noigi v~chie'nIU'<;lcdi~uchinhcac hhngso'nay).D6ivoibailoansan,voi so'chi~ucuavectomfiuhQcbhng 3 chungtaco 8rangbuQcva truockhi ch~ythachuangtrinh,vi~cchQn hhngso'trongdi~uki~nrangbuQcdoihoinhfi'ngdanhgiate'nhi Vidl1:HaytimmQthamnguongtuye'ntinhth~hi~nbangchantri: 1.11111:1:11;111111111111111111111111111111.111.111111i.IIIII:III.i.III.:li.II..li:.:.:I:.II::~i::.:::I:..: Chungtakhdit~omatr~nd~tll'dotimbangch6tla . 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 M~ngno-ranperceptron 29 Sankhich~ychn'ongtrlnhtrenmatr~nd6,tathudn'<;fcvectotrQng s6w=(-2.5,4.0,1.5,1.5) vahamngn'ongtuy€ntinhc6d~ng: y =0( -2.5+ 4x] + 1.5x2+ 1.5X3) Va cho y lacd(>ngtencacvectomfiuhQcthitathudn'<;fcbangsan d~sosanhvdibangchantrichotrongbailoan: -1 -1 -1 -1 0 0 0 0 0 0 0 0 0.0 1 0 0 0 1 0 0 0 0 0 0 0 -2.5 1 0 0 1 0 1 0 0 0 0 0 0 -1.0 1 0 1 0 0 0 1 0 0 0 0 0 -1.0 1 0 1 1 0 0 0 -1 0 0 0 0 1.5 1 1 0 0 0 0 0 0 -1 0 0 0 1.5 1 1 0 1 0 0 0 0 0 -1 0 0 1.5 1 1 1 0 0 0 0 0 0 0 -1 0 1.5 1 1 1 1 0 0 0 0 0 0 0 -1 1.0 1 0 0 0 -2.5 0 1 0 0 1 -1.0 0 1 0 1 0 -1.0 0 1 0 1 1 0.5 1 1 1 0 0 1.5 1 1 1 0 1 3.0 1 1 1 1 0 3.0 1 1 1 1 1 4.5 1 Mj;lngno-ranperceptron 30 R6ranghamnguongtuye'ntinhthuduQcphananhdungbangchan tricuabailoan. Cuo'iclIngthivande conI~iIa voi nhungbai loanvi ill'naothi bangchantrico th~duQcphananhnhomohinhperceptIondonno-roll con nhungbai loannao thi khong?Voi nhungbai loan ma so'chien khongIon Iitm,thi ve nguyentitc,co th~ITaIoi chocall hoi trenb~ng nhungkhaosattrennhunghamrangbuQccuabai loan.Lay vi d1;lcho tru'onghQpduoiday,ta sechungminhr~ngkhongth~phananhbang chantrib~ngmQthamnguongtuye'ntinh,tlicIa mohinhperceptIondon no-rollkhongapd1;lngduQc. Vidl1:Ta xethamy =I(x],Xz,X3)du'QcxacdinhIa duQcxacdinhIa y=1 ne'utrongcacXico mQtso'Ie cacgia tri 1, va y =0 trongcac truonghQpkhac.Bangchantricuabailoandu'Qcth~hi~nnhu'san: ... ............"""""""""""""""""""""",........................................................................................................................................................................................................................................................................................................................................................................................................."""""""""""""""""""""""""""............................................................................................... :::::::::::~:l::::::::::::::::::::::]{g:::::::::::::::::::::::~a:::::::::::::::::::::::::::M:::::::::::::: Chungtasechungminhrhngkhongth~!lmmQthamngu'ongtuye'ntinh chobangchantritrenne'udungmohinhperceptIondonno-roll. Chung ta them mQt gia tri Xo=1 va gQi {Wi}( i > 0 ) Ia nhung trQngso',the'thiquabangchantritren,taconhungbatdiingthuc: 0 0 0 0 0 0 1 1 0 I 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 M!,mgno-ranperceptron 31 (vii) Wo+Wi+ Wz<0 (viii) Wo+Wi +Wz+W3>0 C(>ngtheov€ hai ba'td!ng thuc(ii) va (iii) taduQC:2wo+ Wz+ W3 >0,k€t hQpvoiba'td!ngthuc(i) thlduQc:Wo+Wz+W3 >O. Mauthuftn voiba'td!ngthuc(iv).Di~udochungtodingkhongth€ dungmohlnh perceptIondonno-ronchobailoandiineu. 2.10.Cuoichuang Trongchuongnay,chungtadiidi€m quahaiphuongphaphQccua m~ngperceptIondonno-ronIDeonguyenly "thii'vasii'a".Chungtadiid~ ram(>tphuongphaphQcmak€t quavi~chQCduQchoanta'tngaysaukhi duy(HquacacmftuhQc.Congcv chinhtrongphuongphapnayHiphep giaim(>th~phuongtrlnhtuy€ntinhvoicach~sO'trong{a,1 },doclingla m(>tcongcvmachungtasesii'dvngkhixetm(>tsO'thu~thQcdO'ivoiki€n trUcm~ngperceptIonhi~ulOpbon. (i) Wo<0 (ii) Wo+W3 >0 (iii) Wo+Wz>0 (iv) Wo+Wz+W3<0 (v) Wo+Wi>0 (vi) Wo+ Wi + W3< 0