Công nghệ tri thức và ứng dụng (GS.TSKH. Hoàng Kiếm) - Chương 6.Khám phá tri thức

Ph n III: Khai m d li u và khám phá tri th c ứ ỏ ữ ệ ầ

Ch

ng 6

ươ

Máy h c và khám phá tri th c ứ

ọ

Tham kh o thêm: ả

ơ ở ế ả ọ ọ

[1] GS.TSKH Hoàng Ki m. Bài gi ng cao h c môn h c c s tri th c và ng d ng. ĐHKHTN-TPHCM. ứ ứ ụ

[2] Krzysztof J. Cios, Witold Pedrycz, Roman W. Swiniarski. Data Mining Methods for Knowledge Discovery. Kluwer Academic Publishers, 1998

I. Khái ni m máy h c ọ ệ

Th nào là máy h c (Learning Machine) ? ọ ế

ng trình máy tính có kh năng t hoàn thi n ươ ả ự ệ

 Máy tính hay ch t “kinh nghi m”. ừ ệ

ọ ườ

ạ

 Máy h c còn có nghĩa là vi c mô hình hóa môi tr ng xung ệ quanh hay kh năng m t ch ng trình máy tính sinh ra m t c u ộ ấ ươ ộ ả trúc d li u m i khác v i c u trúc hi n có. Ch ng h n vi c tìm ệ ẳ ớ ấ ớ ệ t p d li u đ u vào. ra nh ng lu t ừ ậ ữ ệ ầ ậ If…then… t ữ ệ ữ

(Krzysztof J. Cios, Witold Pedrycz, Roman W. Swiniarski. Data Mining Methods for Knowledge Discovery. Kluwer Academic Publishers, 1998)

II. Khám phá tri th cứ

Th nào là khám phá tri th c (knowledge discovery) ? ứ ế

ứ ề ẩ ữ

 Khám phá tri th c là tìm ra nh ng tri th c ti m n, nh ng tri th c m i (không ph i là nh ng tri th c kinh đi n, kinh nghi m, …) ữ ệ ứ ả ữ ứ ứ ớ ể

Th a d li u, thông tin nh ng thi u tri th c. ừ ữ ệ ư ứ ế

Tri th cứ Thông tin

t

M c đ ứ ộ tr u ừ ngượ

D li u ữ ệ

S l

ng

ố ượ

III. Phân lo i máy h c ọ ạ

Phân lo i thô: ạ

 H c giám sát (supervised learning) ọ

 H c không giám sát (unsupervised learning) ọ

Phân lo i theo 2 tiêu chu n cùng lúc: “c p đ h c” & “cách ti p c n” ấ ộ ọ ế ậ ạ ẩ

ấ ộ ọ C p đ h c:

 H c v t (Rote learning) ọ ẹ

 H c theo gi i thích (by explanation) ọ ả

 H c theo ví d , tr ng h p (by examples, cases) ụ ườ ọ ợ

 H c khám phá (by discovering) ọ

III. Phân lo i máy h c (tt) ạ ọ

Cách ti p c n: ế ậ

 Ti p c n th ng kê ế ậ ố

 Ti p c n toán t logic ế ậ ử

ọ

 Ti p c n hình h c (phân ho ch không gian, xây d ng cây đ nh danh, …) ế ậ ạ ự ị

 Ti p c n m ng Neural ế ậ ạ

 Ti p c n khai m d li u ỏ ữ ệ ế ậ

…

III.1 Ti p c n th ng kê ế ậ ố

ng trình đoán ý nghĩ con ng ườ

i ch i s ph i tr l ươ ố ườ ầ ơ ẽ i. Máy s đoán ng ẽ ả ờ ả

i ườ i cho đó máy tính s h c ế ẽ ọ ể ừ

Ví d :ụ Ch ch i nghĩ s 0 hay 1 trong đ u, ng ơ máy bi qui lu t suy nghĩa c a ng ậ t là máy đã đoán đúng hay sai. Đ t ườ i ch i. ơ ủ

1

Máy đoán sai

Máy đoán là 0

III.1 Ti p c n th ng kê (tt) ế ậ ố

Ý t ng cài đ t: h t s c đ n gi n ưở ế ứ ơ ặ ả

i ch i đã nghĩ ra. - L u tr toàn b dãy s 0, 1 mà ng ộ ư ữ ố ườ ơ

ấ ố ướ ơ ư ườ ấ

i ch i đ a ra), tính xác su t xu t ấ hi n c a s 1 và s 0 sau dãy 7 con s này. Máy s đoán s ố c đó (ng ố ố ẽ

- L y 7 con s tr ệ ủ ố có xác su t xu t hi n cao h n. ệ ấ ấ ơ

Gi s l n đoán th i, dãy s mà ng i dùng đã đoán nh sau: ả ử ở ầ ứ ố ườ ư

… 1 1 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 ?

c, gi ữ ở ữ nh ng l n đoán tr ầ ả ử ố ầ

0 0 0 0 1 0 0 là 28 và s l n xu t hi n c a s 0 là ừ ữ ệ ư ệ ủ ướ ố ầ s s l n xu t ấ ệ ủ ố ấ

T d li u l u tr hi n c a 1 sau dãy 90

Xác su t xu t hi n c a s 1 sau dãy này là: 28/(28+90) = 23.7% ệ ủ ố ấ ấ

Xác su t xu t hi n c a s 0 sau dãy này là: 90/(28+90) = 76.3% ệ ủ ố ấ ấ

(cid:222) Máy s đoán s 0 ố ẽ

III.1 Ti p c n th ng kê (tt) ế ậ ố

Nh n xét ví d : ụ ậ

ộ ọ ẹ ử ụ ộ ấ ư ế

 Ví d đã đ a ra là thu c c p đ h c v t s d ng cách ti p ụ c n th ng kê. ố ậ

ượ ư ề

ộ ở ạ ầ

 Máy không th đoán đúng ngay đ c, nh ng càng v sau (vài ể trăm l n đoán) máy càng tr nên chính xác m t cách kinh ng c (trung bình có th lên đ n 90%). ể ế

ự ế ậ ừ khi cài đ t ch ặ dãy s c a ng ố ủ ươ ườ không ch ng trình này tác gi ỉ i ch i, máy còn s d ng c dãy ả ả ử ụ ơ

 Trên th c t đoán qui lu t t s mà máy đã đoán ố

III.2 Ti p c n hình h c ọ ế ậ

ữ ậ ớ ướ

Xét bài toán: cho t p các hình ch nh t v i kích th ậ và màu s c khác nhau (hình v ). Cho bi c (ngang & r ng) ộ t hình bên ph i có màu gì? ả ẽ ế ắ

Ñoû

Vaøng

Cam

Tía

?

Ñoû

Xanh döông

Xanh laù caây

Tím

III.2 Ti p c n hình h c (tt) ế ậ ọ

Gi i quy t bài toán: ả ế

ự

Vaøng

Ñoû

ủ ẵ

6

Tía

Cam

ế

 Ph n ng t nhiên c a ả ứ con ng i: tìm kh i có s n ườ ố g n gi ng đ đoán màu ể ố ầ t. Nh cho kh i ch a bi ư ư ố th nào là g n gi ng ? ố ế ầ

U

4

ễ ể

ộ ề

Xanh döông

Ñoû

2

Xanh laù caây

Tím

 Bi u di n 2 thu c tính chi u r ng & chi u cao ộ i d ng 1 đi m trên d ạ ể m t ph ng 2 chi u. ề ẳ ề ướ ặ

0 2 4 6

ạ

ườ ầ ấ

 Tính kho ng cách t ừ ả kh i c n tìm đ n t t c ố ầ ấ ả ế i. (bài toán các kh i còn l ố ng i láng gi ng g n nh t ề v i đ ph c t p O(n)). ớ ộ ứ ạ

III.2 Ti p c n hình h c (tt) ế ậ ọ

ệ ả ơ

ẫ ệ ự ể ấ

[1.2]

Vaøng

Ñoû

t ệ ứ 6 [1.2.1] [1.2.2]

Tía

Cam

 Cách làm hi u qu h n là tìm cách chia không gian các hình ch ữ t theo ki u phân c p không nh t m u thành các khu v c riêng bi ậ gian.  8 không gian riêng bi ng v i 8 hình ch ữ ớ nh t đã cho ban ậ đ u.ầ

U 4 y = 3.5 [1]

[1.1]

Xanh döông

ườ 2 [1.1.1]

ế

Tím

Xanh laù caây

Ño û [1.1.2]

ữ ậ

0 2 4 6

 L n l t xác ầ ượ ng đ nh v trí t ươ ị ị đ i c a U so v i ớ ố ủ ng chia. các đ Cu i cùng U x p ố cùng không gian v i hình ch nh t ớ có màu cam (cid:222) U có màu cam

III.2 Ti p c n hình h c (tt) ế ậ ọ

Nh n xét bài toán: ậ

ề ặ ậ

 V m t thu t toán, phân chia không gian theo cách làm trên là phân chia theo cây k-d.

 Cây quy t đ nh (cây k-2) c a bài toán có th bi u di n nh sau: ể ể ế ị ủ ư ễ

[1]

treân

döôùi

[1.1]

[1.2]

phaûi

traùi

traùi

phaûi

[1.1.1]

[1.1.2]

[1.2.2]

[1.2.1]

treân

treân döôù i

döôù i

Ñoû

treân döôù i Tím Vaøng Tía Ñoû

Cam

Xanh döông

treân döôù i Xanh laù caây

III.3 Ti p c n logic ế ậ

Ví d 1:ụ Baïn haõy thöû tìm ñaëc tính ñeå phaân bieät hai nhoùm hình aûnh A vaø B döôùi ñaây.

III.3 Ti p c n logic (tt) ế ậ

Nh n xét ví d 1: ụ ậ

ế ạ ẽ ể ắ ậ

 N u tinh ý b n s nh n th y các đi m tr ng trong nhóm A ấ luôn th ng hàng. ẳ

ậ

ng hình h c.  Th t khó đ phát hi n ra đ c tính v a nêu trên (ngay c đ i ả ố ặ v i con ng ớ ệ ể i) nh t là đ i v i các đ i t ố ớ ừ ố ượ ườ ọ ấ

ươ ộ ọ ố ị

 Nhà bác h c Bongard đã đ ra m t ph ề liên h b ng cách xây d ng các m nh đ logic. (xem ví d 2) ng án xác đ nh m i ụ ệ ằ ự ệ ề

III.3 Ti p c n logic (tt) ế ậ

Ví d 2:ụ Xác đ nh đ c đi m c a các nhóm hình A, B ể ủ ặ ị

Nhoùm A

Nhoùm B

III.3 Ti p c n logic (tt) ế ậ

Nh n xét ví d 2:

ụ

ậ

 Nhoùm A : Toång soá ñænh tröø toång soá ñoái töôïng = 7. (Chaúng haïn nhö hình 2 trong nhoùm A coù 3 hình goàm 2 tam giaùc vaø moät hình chöõ nhaät, toång coäng coù 10 ñænh).

 Nhoùm B : Toång soá ñænh tröø toång soá ñoái töôïng = 6.

 Hình ellipse vaø hình troøn ñöôïc xem laø khoâng coù ñænh naøo

 Khoâng ñöôïc gôïi yù thì quan h treân laø moät loaïi quan heä raát ệ khoù ñöôïc phaùt hieän.

 Vôùi phöông aùn cuûa Bongard, ta vaãn coù theå tìm ra ñöôïc moái lieân heä ñuû ñeå phaân bieät hai nhoùm hình naøy.

III.3 Ti p c n logic (tt) ế ậ

Ñònh ra moät soá caùc meänh ñeà logic ñôn giaûn nhö:

 P1 : “toàn taïi tam giaùc”

 P2 : “toàn taïi voøng troøn”

 P3 : “toàn taïi hình oval”

 P4 : “toàn taïi hình chöõ nhaät”

 P5 : “toàn taïi hình ña giaùc nhieàu hôn 4 caïnh”.

III.3 Ti p c n logic (tt) ế ậ

Hình

Nhoù m

Tam giaùc P1 1

Voøng troøn P2 1

Oval P3 1

Chöõ nhaät P4 1

Ña giaùc P5 0

1

A

2

1

0

0

1

A

0

3

0

1

0

0

A

1

4

1

0

0

0

A

1

5

0

1

0

1

A

0

6

1

1

0

1

A

0

7

1

1

0

0

B

0

8

1

1

0

1

B

0

9

0

0

0

1

B

0

10

1

0

1

0

B

0

11

1

1

0

0

B

0

12

1

0

0

0

B

0

III.3 Ti p c n logic (tt) ế ậ

(cid:222) Söû duïng caùc meänh ñeà logic khaù ñôn giaûn, ta ñaõ xaây döïng ñöôïc

j ø ø ø ø ø

moät lieân heä “ñaëc tröng” cho nhoùm hình A nhö sau: (cid:218)

(cid:218) ø P1P2

P4 P5

P3 P4

ø P5

P3

ø ø ø ø ø ø

= P1 P2 P3 P4 ø P1P2

P3

P4

P5

(cid:218) P1 P2 (cid:218) ø P1P2

P3 P4 P5

P3 P4

P5

P5 (cid:218) P1P2

(cid:222)

Baèng caùc pheùp bieán ñoåi logic toaùn hoïc, ta coù theå thu goïn meänh

ñeà treân thaønh :

j ø

= ø

P1P2 (cid:218) P1 (P2P3 (cid:218) ø

P2

P3)

Nhö vaäy 1 hình x naøo ñoù ñeå ñöôïc xeáp vaøo nhoùm hình A thì giaù trò caùc meänh ñeà P1 ñeán P6 cuûa hình x phaûi thoûa meänh ñeà j ôû treân.

III.3 Ti p c n logic (tt) ế ậ

Nh n xét: ậ

 Trong tröôøng hôïp toång quaùt, phaûi choïn caùc meänh ñeà cô sôû (nhö caùc meänh ñeà P1, P2, …P6 trong ví duï treân) nhö theá naøo ñeå meänh ñeà ñaëc tröng cuûa taát caû caùc hình trong taäp maãu laø khaùc nhau vaø meänh ñeà ñaëc tröng cuûa nhoùm hình cuõng phaûi khaùc nhau.

 Laøm sao xaây döïng thuû tuïc ñeå kieåm tra giaù trò caùc meänh ñeà cô sôû. Maét ngöôøi coù theå deã daøng nhaän bieát söï toàn taïi moät hình troøn, hình tam giaùc, … trong moät hình aûnh coù nhieàu ñoái töôïng khaùc nhau nhöng laøm ñieàu baèng chöông trình maùy tính hoaøn toaøn khoâng ñôn giaûn.

 Chính vì lyù do ñoù, phöông phaùp hoïc naøy raát caàn ñeán söï hoã trôï cuûa con ngöôøi trong vieäc ñöa ra quyeát ñònh tính ñuùng ñaén cuûa caùc meänh ñeà thaønh vieân trong meänh ñeà ñaëc tröng.

III.4 H c d a trên cây đ nh danh ọ ự ị

 Xây d ng cây đ nh danh b ng cách tìm các qui lu t c a d li u.

 Döïa treân yù töôûng cuûa tieáp caän hình hoïc laø phaân chia khoâng gian baøi toaùn taïo thaønh moät caây quyeát ñònh, ngöôøi ta ñaõ xaây döïng caùc phöông phaùp hoïc döïa treân vieäc xaây döïng caây ñònh danh.

ậ ủ ữ ệ

ự

ằ

ị

Ví d :ụ Xaây döïng caùc quy luaät ñeå keát luaän moät ngöôøi nhö theá naøo khi ñi taém bieån thì bò chaùy naéng. Ta goïi tính chaát chaùy naéng hay khoâng chaùy naéng laø thuoäc tính quan taâm (thuoäc tính muïc tieâu).

R = {“chaùy naéng”, “bình thöôøng”}

P = taäp hôïp 8 ngöôøi quan saùt ñöôïc

4 thuoäc tính : chieàu cao (cao, trung bình, thaáp), maøu toùc (vaøng,

naâu, ñoû) caân naëng (nheï, TB, naëng), duøng kem (coù, khoâng)

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

Teân

Toùc

Ch.Cao

Keát quaû

Sarah

Vaøng

T.Bình

Caân Naëng Nheï

Duøng kem? Khoâng

Chaùy

T.Bình

Dana

Vaøng

Cao

Coù

Khoâng

T.Bình

Alex

Naâu

Thaáp

Coù

Khoâng

T.Bình

Annie

Vaøng

Thaáp

Khoâng

Chaùy

Emilie

Ñoû

T.Bình

Khoâng

Chaùy

Peter

Naâu

Cao

Khoâng

Khoâng

John

Naâu

T.Bình

Khoâng

Khoâng

Kartie

Vaøng

Thaáp

Naën g Naën g Naën g Nheï

Coù

Khoâng

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

˛

R).

 Tìm caùch phaân hoaïch taäp P ban ñaàu thaønh caùc taäp Pi sao cho taát caû caùc phaàn töû trong taát caû caùc taäp Pi ñeàu coù chung thuoäc tính muïc tieâu ri (ri

¨

(i,j) i„

) vaø

... ¨

P = P1 ¨

Pn vaø "

j : thì (Pi ˙

Pj = ˘

"

P2 i, " k,l : pk ˛

Pi vaø pl ˛

Pj thì f(pk) = f(pl)

ri

 ÖÙùng vôùi moãi phaân hoaïch Pi ta xaây döïng luaät Li : GTi fi ( GT-i laø keát hôïp caùc thuoäc tính daãn xuaát )

 Coù hai caùch phaân hoaïch hieån nhieân: Caùch ñaàu tieân laø cho moãi ngöôøi vaøo moät phaân hoaïch rieâng (P1 = {Sarah}, P2 = {Dana}, …. Caùch thöù hai laø phaân hoaïch thaønh hai taäp, moät taäp goàm taát caû nhöõng ngöôøi chaùy naéng vaø taäp coøn laïi bao goàm taát caû nhöõng ngöôøi khoâng chaùy naéng. Tuy ñôn giaûn nhöng phaân hoaïch theo kieåu

naøy thì chuùng ta chaúng giaûi quyeát ñöôïc gì !!

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

(cid:222) ng pháp gi Đ xu t ph ề ấ ươ ả i quy t ế

a. Đâm ch iồ

Ma ø u t o ù c

Pvaøng = { S a ra h , Dana, An n ie , Kartie }

Pnaâu = { Alex, Peter, John } Em m il e

Pñoû = { Em m ile }

Alex Pete r John  Caùc ngöôøi bò chaùy naéng ñöôïc gaïch döôùi vaø in ñaäm.

S a ra h Dana An n ie Kartie

 Pvaøng laø coøn laãn loän ngöôøi chaùy naêng vaø khoâng chaùy naéng.

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

 Quan saùt thuoäc tính chieàu cao. Thuoäc tính naøy giuùp phaân hoaïch taäp Pvaøng thaønh 3 taäp con :

PVaøng, Thaáp = {Annie, Kartie}

PVaøng, T.Bình= {Sarah}

Ma ø u t o ù c

PVaøng,Cao= { Dana }

S a ra h

Em m il e

Ch ie à u c a o

Dana An n i e

Thaáp T.Bình

Cao

Kartie

Alex Peter John

S a ra h

Dana An n ie Kartie

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

Nh n xét:

ậ

 Quaù trình naøy cöù theá tieáp tuïc cho ñeán khi taát caû caùc nuùt laù cuûa caây khoâng coøn laãn loän giöõa chaùy naéng vaø khoâng chaùy naéng nöõa.

 Qua moãi böôùc phaân hoaïch caây phaân hoaïch ngaøy caøng “phình” ra. Ca â y m a ø c h u ù n g t a ñ a n g x a â y d ö ïn g ñ ö ô ïc g o ïi la ø c a â y ñ ò n h d a n h .

V n đ : ấ ề

 Neáu nhö ban ñaàu ta khoâng choïn thuoäc tính maøu toùc ñeå phaân hoaïch maø choïn thuoäc tính khaùc nhö chieàu cao chaúng haïn ñeå phaân hoaïch thì sao? Cuoái cuøng thì caùch phaân hoaïch naøo seõ toát hôn?

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

b. Ch n thu c tính phân ho ch ộ ọ ạ

Quinlan: Vôùi moãi thuoäc tính daãn xuaát A coøn coù theå söû duïng ñeå phaân hoaïch, tính :

VA(j) = ( T(j , r1), T(j , r2) , …, T(j , rn) )

T(j, ri) = (toång soá phaàn töû trong phaân hoaïch coù giaù trò thuoäc tính daãn xuaát A laø j vaø coù giaù trò thuoäc tính muïc tieâu laø ri ) / ( toång soá phaàn töû trong phaân hoaïch coù giaù trò thuoäc tính daãn xuaát A laø j )

=

1)rT(j, •t ro n g ñ o ù r1, r2, … , rn laø caùc giaù trò cuûa thuoäc tính muïc tieâu i

i

(cid:229)

Nh ö v a ä y n e á u m o ä t t h u o ä c t ín h A c o ù t h e å n h a ä n m o ä t t ro n g 5 g ia ù t rò kh a ù c n h a u t h ì n o ù s e õ c o ù 5 v e c t o r ñ a ë c t rö n g .

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

 Moät vector V(Aj ) ñöôïc goïi laø vector ñôn vò neáu noù chæ coù duy nhaát moät thaønh phaàn coù giaù trò 1 vaø nhöõng thaønh phaàn khaùc coù giaù trò 0.

 Thuoäc tính ñöôïc choïn ñeå phaân hoaïch laø thuoäc tính coù nhieàu vector ñôn vò nhaát.

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

 Trôû laïi ví duï cuûa chuùng ta, luùc ban ñaàu (chöa phaân hoaïch)

VToùc (vaøng) = ( T(vaøng, chaùy naéng), T(vaøng, khoâng chaùy naéng) )

Soá ngöôøi toùc vaøng laø : 4

Soá ngöôøi toùc vaøng vaø chaùy naéng laø : 2

Soá ngöôøi toùc vaøng vaø khoâng chaùy naéng laø : 2

Do ñoù: VToùc(vaøng) = (2/4 , 2/4) = (0.5, 0.5)

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

Töông töï

VToùc(naâu) = (0/3, 3/3) = (0,1) (vector ñôn vò)

Soá ngöôøi toùc naâu laø : 3

Soá ngöôøi toùc naâu vaø chaùy naéng laø : 0

Soá ngöôøi toùc naâu vaø khoâng chaùy naéng laø : 3

VToùc(ñoû) = (1/1, 0/1) = (1,0) (vector ñôn vò)

Toång soá vector ñôn vò cuûa thuoäc tính toùc vaøng laø 2

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

 Caùc thuoäc tính khaùc ñöôïc tính töông töï, keát quaû nhö sau :

VC.Cao(Cao) = (0/2,2/2) = (0,1)

VC.Cao(T.B) = (2/3,1/3)

VC.Cao(Thaáp) = (1/3,2/3)

VC.Naëng (Nheï) = (1/2,1/2)

VC.Naëng (T.B) = (1/3,2/3)

VC.Naëng (Naëng) = (1/3,2/3)

VKem (Coù) = (3/3,0/3) = (1,0)

VKem (Khoâng) = (3/5,2/5)

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

 Nh ö v a ä y t h u o ä c t ín h m a ø u t o ù c c o ù s o á v e c t o r ñ ô n v ò n h ie à u n h a á t n e â n s e õ ñ ö ô ïc c h o ïn ñ e å p h a â n h o a ïc h .

 P h a â n h o a ïc h t h e o t o ù c v a ø n g ( P vaøng) laø coøn chöùa nhöõng ngöôøi chaùy naéng vaø khoâng chaùy naéng. Tieáp tuïc phaân hoaïch taäp naøy. Tính vector ñaëc tröng töông töï ñoái vôùi caùc thuoäc tính coøn laïi (chieàu cao, caân naëng, duøng kem). Trong phaân hoaïch Pvaøng, taäp döõ lieäu cuûa chuùng ta coøn laïi laø :

Te â n

Ch . Ca o

Ke á t q u a û

Ca â n N a ë n Nheï g T.Bình

Sarah Dana T.Bình Cao

D u ø n g k e m ? Khoâng Coù

T.Bình

Chaùy Khoâng

Nheï

Annie Thaáp Khoâng Chaùy

Kartie Thaáp Coù Khoâng

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

VC.Cao(Cao) = (0/1,1/1) = ( 0 , 1 )

VC.Cao(T.B) = (1/1,0/1) = ( 1 , 0 )

VC.Cao(Thaáp) = (1/2,1/2)

VC.Naëng (Nheï) = (1/2,1/2)

VC.Naëng (T.B) = (1/2,1/2)

VC.Naëng (Naëng) = (0,0)

VKem (Coù) = (0/2,2/2) = ( 0 , 1 )

VKem (Khoâng) = (2/2,0/2) = ( 1 , 0 )

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

 2 t h u o ä c t ín h d u ø n g ke m v a ø c h ie à u c a o ñ e à u c o ù 2 v e c t o r ñ ô n v ò . Tu y n h ie â n , s o á p h a â n h o a ïc h c u û a t h u o ä c t ín h d u ø n g ke m la ø ít h ô n n e â n t a c h o ïn p h a â n h o a ïc h t h e o t h u o ä c t ín h d u ø n g ke m . Ca â y ñ ò n h d a n h c u o á i c u ø n g :

Ma ø u t o ù c

S a ra h

Em m ile

Dana An n ie

Kartie

Du ø n g ke m

Coù Alex Peter John

Dana

Kartie

Khoân g

S a ra h An n ie

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

ộ

ạ Th a y v ì p h a û i x a â y d ö ïn g c a ù c v e c t o r Đ đ o h n lo n : ỗ ñ a ë c t rö n g n h ö p h ö ô n g p h a ù p c u û a Qu in la n , ö ù n g v ô ù i m o ã i t h u o ä c t ín h d a ã n x u a á t t a c h æ c a à n t ín h ra ñ o ä ñ o h o ã n lo a ïn v a ø lö ïa c h o ïn t h u o ä c t ín h n a ø o c o ù ñ o ä ñ o h o ã n lo a ïi la ø t h a á p n h a á t . Co â n g t h ö ù c t ín h n h ö s a u :

b

j

log

2

b

b ir b

b ir b

j

i

t

j

j

(cid:246) (cid:230) (cid:246) (cid:230) (cid:246) (cid:230) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) - · - · (cid:229) (cid:229) TA = (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231)

ł Ł ł Ł ł Ł

b t laø toång soá phaàn töû coù trong phaân hoaïch

bj laø toång soá phaàn töû coù thuoäc tính daãn xuaát A coù giaù trò j.

bri : toång soá phaàn töû coù thuoäc tính daãn xuaát A coù giaù trò j vaø thuoäc tính muïc tieâu coù giaù trò i.

III.4 H c d a trên cây đ nh danh (tt) ọ ự ị

ậ

c. Phát sinh t p lu t ậ

(Maøu toùc vaøng) vaø (coù duøng kem) fi

khoâng chaùy naéng

(Maøu toùc vaøng) vaø (khoâng duøng kem) fi

chaùy naéng

(Maøu toùc naâu) fi

khoâng chaùy naéng

(Maøu toùc ñoû) fi

chaùy naéng

i u t p lu t (tham kh o ph n t i u hóa ấ ề ế ố ư ậ ầ ố ư ả ậ

V n đ ti p theo là t CSTT)

III.6 Ti p c n m ng Neural ế ậ ạ

 Maïng neural laø thuaät ngöõ noùi ñeán moät phöông phaùp giaûi quyeát vaán ñeà – baøi toaùn treân maùy tính moâ phoûng theo hoaït ñoäng cuûa caùc teá baøo thaàn kinh trong naõo boä.

 Maïng neural nhaân taïo laø söï moâ phoûng caáu truùc cuûa maïng neural sinh hoïc. Maïng neural nhaân taïo ñöôïc taïo thaønh bôûi söï noái keát giöõa raát nhieàu ñôn vò thaàn kinh goïi laø perceptron.

Khôùp

Nhaùnh

Truïc

Thaân

Caáu truùc cuûa moät teá baøo thaàn kinh sinh hoïc

III.6 Ti p c n m ng Neural ế ậ ạ

 C u t o moät ñôn vò thaàn kinh nhaân taïo (nhö hình v ) ẽ ấ ạ

Giaù trò ñaàu ra y cuûa moät perceptron ñöôïc tính baèng coâng thöùc sau:

y = f((xnwn+ xn-1wn-1 + … + w2n2 + w1n1 + w0) - f ) ( f

ñöôïc goïi laø ngöôõng kích hoaït cuûa neural ) x1

w1

x2 w2

y Haøm f ñöôïc goïi laø haøm haøm truyeàn. Moät truyeàn caàn phaûi coù tính chaát sau : f (cid:229) xiwi

… wn-1 - bò chaën

xn-1 wn

- ñôn ñieäu taêng

xn

- haøm lieân tuïc taêng

=

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

)(f x

1 -+ xe

1

Caùc haøm truyeàn thöôøng ñöôïc söû duïng: Haøm logistic (hay coøn goïi laø haøm Sigma)

x

=

- -

)(h x

x

+

1 1

e e

Haøm hyperbol -

x

x

tanh

=)( x

- -

x

x

+

e e

e e

Haøm tang-hyperbol -

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

Mô hình minh h a m ng neural 1 l p ọ ớ ạ

ọ Cung liên k t ế ố j) (tr ng s W

Units Input

Unit output

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

Mô hình minh h a m ng neural t ng quát ạ ọ ổ

Các unit input Ik Wk,j Các unit nẩ aj Wj, i Các unit output Oi

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

1. M ng lan truy n (Feed Forward) ề ạ

W13 W35 I1 H3

O5

W14 W23

H4 W45 I2

W24

Nguyên t c xác đ nh giá tr Output c a node 5: ủ ắ ị ị

a5 = f (W3,5a3 + W4,5a4)

= f (W3,5 f(W1,3a1 + W2,3a2) + W4,5 f(W1,4a1 + W2,4a2))

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

2. M ng Hopfield ạ

-1 -1

+1 -1 +3 +1 -1 +3

-1 -1

+1 +1 +3 +3 -2 -2 +2 +2

-1 +1

ng t ho t đ ng m t b nh k t h p -1 ạ ộ +1 ự ạ ộ ươ ộ ộ ớ ế ợ

M ng Hopfield ho t đ ng t ạ có:

Wi,j = Wj,i

III.5 Ti p c n m ng Neural (tt) ế ậ ạ

3. M ng Perceptron ạ

Các unit output Các unit output

Các unit input Ij Các unit input Ij

Oi Oi

Wj,i Wj,i

Perceptron đ n lơ ẻ

III.5 Ti p c n m ng Neural (tt) ế ậ ạ

M ng Perceptron ạ

input output

Wi = Wi + a *Xi Wi = Wi - a *Xi

Xi a : h s h c ệ ố ọ

Wi,j

Oj

O

T - O

T : đ u ra mong mu n ố ầ

O: đ u ra c a m ng ủ ạ ầ

Perceptron đ n ơ lẻ

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

Kh năng phân chia tuy n tính trong m ng Perceptron ế ả ạ

I1 I1 I1

1 1 1

?

0 0 0

0 I2 I2 0 I2 0 1

(b) I1 or I2 (c) I1 xor I2 (a) I1 and I2

1 n u Wế

1I1 + W2I2 > q

Y(I1, I2) =

0 ng i c l ượ ạ

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

H n ch c a m ng Perceptron ạ ế ủ ạ

ự ấ ứ

- Năm 1969, Minsky và Papert đã phân tích và ch ng minh s th t b i c a m ng Perceptron v i bài toán XOR. ạ ủ ớ ạ

I1 1 I2 1 y(I1, I2) = I1 XOR I2 0

1 0 1

0 1 1

0 0 0

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

Xét t ng tr ừ ườ

> 0 (cid:222) q N u [Iế

q £ q (cid:222) N u [Iế W1

q (cid:222) q £ N u [Iế W2

(cid:222) q N u [Iế ng h p: ợ 1, I2]=[0,0] thì y(I1, I2)=0 (cid:222) 1, I2]=[0,1] thì y(I1, I2)=1 (cid:222) 1, I2]=[1,0] thì y(I1, I2)=1 (cid:222) 1, I2]=[1,1] thì y(I1, I2)=0 (cid:222) W1*0 + W2*0 < q W1*0 + W2*1 ‡ W1*1 + W2*0 ‡ W1*1 + W2*1 < q > W1 + W2

c W th a mãn 4 b t đ ng th c ể ượ ấ ẳ ứ ỏ

1, W2, q

(cid:222) Rõ ràng không th tìm đ trên.

(cid:222) i trong tr ng h p này vì ườ ợ

ể hàm XOR không ph i là hàm ng ưỡ Mô hình Perceptron không th tìm ra l ả i gi ờ ả ng tuy n tính. ế

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

Ví d minh h a vi c h c c a m ng Perceptron: ệ ọ ủ ụ ọ ạ

Loài

Đ dài ộ đài hoa Đ r ng ộ ộ đài hoa Đ dài ộ cánh hoa Đ r ng ộ ộ cánh hoa

C t ộ thêm vào

1 Cây Iris A 4.7 3.2 1.3 0.2 -1

1 Cây Iris B 6.1 2.8 4.7 1.2 1

1 Cây Iris C 5.6 3.0 4.1 1.3 1

1 Cây Iris D 5.8 2.7 5.1 1.9 -1

1 Cây Iris E 6.5 3.2 5.1 2.0 -1

1 Cây Iris Q 5.8 2.7 3.9 1.2 ???

Kh i t o tr ng s : w ở ạ ọ ố 1=1; w2=0; w3=0; w4=0; w5=1

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

5

=

+

+

=

+

+ 2.12.0*13.1*02.3*07.4*01*1

 D đoán l n th nh t đ i v i m u “Cây Iris A” ứ ấ ố ớ ẫ ự ầ

i xw i

=i 1

(cid:229)

Perceptron d đoán “Loài” có k t qu là 1 so v i k t qu đúng là -1 ớ ế ự ế ả ả

 C p nh t tr ng s m ng ậ ọ ố ạ ậ

*a

w i

w i

x i

- ‹ ớ ế ả

N u k t qu “Loài” là 1 so v i k t qu ả ế ế đúng là -1

( a : T l h c nên ch n nh , = 0.05) ỉ ệ ọ ỏ ở ọ ọ a đây ta ch n

-=

=

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

*05.0

95.01*05.01 -= -=

- ‹

*05.0

x 1 x

7.4*05.00

24.0

w 1 w 2

2

-=

-=

- ‹

*05.0

2.3*05.00

16.0

-=

-=

- ‹

*05.0

x 3 x

3.1*05.00

07.0

w 3 w 4

4

-=

=

- ‹

*05.0

99.02.0*05.01

w 1 w 2 w 3 w 4 w 5

w 5

x 5

- ‹

Các tr ng s này dùng đ luy n cho nh ng m u k ti p ẫ ế ế ữ ố ọ ệ ể

 Đi u ki n d ng: ệ ừ ề

T t c các m u đã đ c d đoán đúng. ấ ả ẫ ượ ự

D ng sau m t s b c l p do ng i dùng quy t đ nh. ộ ố ướ ặ ừ ườ ế ị

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

a

C p nh t tr ng s sao cho t i ti u sai l ch. ố ậ ố ể ệ

w i

- ‹ ớ ế ả Nh n xét: ậ ( ) 1 w i ậ ọ * x i

(

)

a+

N u k t qu “Loài” là 1 so v i k t qu ả ế ế đúng là -1

2

*

w i

w i

x i

‹ ế ế ớ ế ả

n

N u k t qu “Loài” là -1 so v i k t qu ả đúng 1

= 1

i

(cid:229) ầ

c k ti p cho cùng ố ớ ế ướ ế ế

• Tr ng s m i là ọ m u d li u ta đ ẫ ữ ệ

2 < wixi

n

(cid:229)

i xw (1) wixi góp ph n làm cho > 0. i wi - a *xi. Vì th b wi ‹ ượ wi - a *xi )*xi = wixi – r*xi c ( i xw i

i

= 1

• Nh v y sau khi thay đ i tr ng s nh h n ố ỏ ơ ổ ọ ư ậ

tr c đó. ướ

• Vì v y k t qu d đoán s g n v k t qu đúng là –1. ẽ ầ ề ế ậ ế ả ự ả

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

Nguyên lý ho t đ ng c a m ng Perceptron ạ ộ ủ ạ

B c 1ướ : Xác đ nh giá tr c a ị ị ủ Err

Err = T – O (T : đ u ra mong mu n) ầ ố

if Err > 0 then tăng O

else gi m ả O

B c 2: ướ C p nh t giá tr ma tr n tr ng s ị ọ ậ ố ậ

là h s h c) ệ ố ọ ậ Wj = Wj + a * xj*Err. (a

B c 3: L p l i b c 1 và 2 cho đ n khi Err < e ướ ặ ạ ướ ế thì d ng.ừ

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

4. M ng lan truy n ng c (back propagation) ề ạ ượ

Các unit input xk Wk,j Các unit nẩ aj Wj, i Các unit output Oi

III.5 Ti p c n m ng Neural (tt) ế ậ ạ

M ng lan truy n ng c (back propagation) ề ạ ượ

output input Hidden

Oj Xi

Wih Whj O h

OT – O

. . .

. . .

. . .

d

oj*oj

o = o(1-o)(T-o) Whj = Whj + a *d * d Wih = Wih + a

o* Wh*oh*(1-oh)*xi

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

T p m u cho quá trình h c ọ ẫ ậ

Đ u ra mong mu n ố ầ

M uẫ 1

1)

y1

2

2)

y2 x1 = (x1 x2 = (x1

1, …, xn 2, …, xn

… …

M

m)

ym Đ u vào ầ 1, x2 2, x2 … m, x2 xm = (x1

m, …, xn

ệ ệ ả

ứ  Cho m u xẫ k sai l ch v i k t qu mong k vào luy n -> Cho ra O ớ ế k: mu n yố k. Sai l ch c a m u th k là E ẫ ủ ệ

Ek = ½*(yk - Ok)2 = ½(yk – f(wT x))2

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

m

=

+

E

E

E

++ ...

E

t c các m u: ủ ấ ả ẫ

k

E 1

2

m

= 1

k

 Sai l ch c a t ệ = (cid:229)

a

ng c c ti u hóa sai l ch  C p nh t tr ng s : theo h ậ ọ ố ậ ướ ự ể ệ

-= ww

(' wE ) k

*

a : là h s h c ệ ố ọ

2

k

k

T

T

'

(cid:246) (cid:230)

(

)

)

(

(

=

-=(cid:247)

y

- - (cid:231)

( T xwf

y

)xwfxwf ) ) (

' ( wE ) k

d dw

1 2

ł Ł

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

Ví d minh h a cho ph ng pháp lan truy n ng c ụ ọ ươ ề ượ

Loài

Đ dài ộ đài hoa Đ r ng ộ ộ đài hoa Đ dài ộ cánh hoa Đ r ng ộ ộ cánh hoa

C t ộ thêm vào

1 Cây Iris A 4.7 3.2 1.3 0.2 0

1 Cây Iris B 6.1 2.8 4.7 1.2 1

1 Cây Iris C 5.6 3.0 4.1 1.3 1

1 Cây Iris D 5.8 2.7 5.1 1.9 0

1 Cây Iris E 6.5 3.2 5.1 2.0 0

1 Cây Iris Q 5.8 2.7 3.9 1.2 ???

=

)(f x

1 -+ xe

1

Ch n hàm truy n: ọ ề

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

Các unit input xk Wk,j Các unit nẩ hj Wj, i Các unit output Oi

4

b

3 o

a

2

1

0

0

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

Kh i t o các tr ng s có giá tr ng u nhiên nh ị ẫ ở ạ ọ ố ỏ

Tr ng s c t giá tr -1 trong đ n v n a ị ơ ị ẩ ố ộ ọ W0a = 0.0

Tr ng s trong đ n v n a t ơ ị ẩ ọ ố ừ giá tr nh p th 1 ị ậ ứ W1a = 0.1

Tr ng s trong đ n v n a t ơ ị ẩ ố ọ ừ giá tr nh p th 2 ị ậ ứ W2a = -0.1

Tr ng s trong đ n v n a t ơ ị ẩ ố ọ ừ giá tr nh p th 3 ị ậ ứ W3a = -0.1

Tr ng s trong đ n v n a t ơ ị ẩ ọ ố ừ giá tr nh p th 4 ị ậ ứ W4a = 0.0

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

Tr ng s c t giá tr -1 trong đ n v n b ị ơ ị ẩ ố ộ ọ W0b = 0.0

Tr ng s trong đ n v n b t ơ ị ẩ ọ ố ừ giá tr nh p th 1 ị ậ ứ W1b = -0.1

Tr ng s trong đ n v n b t ơ ị ẩ ố ọ ừ giá tr nh p th 2 ị ậ ứ W2b = 0.2

Tr ng s trong đ n v n b t ơ ị ẩ ọ ố ừ giá tr nh p th 3 ị ậ ứ W3b = 0.1

Tr ng s trong đ n v n b t ơ ị ẩ ố ọ ừ giá tr nh p th 4 ị ậ ứ W4b = -0.1

Tr ng s c t giá tr -1 trong đ n v xu t o ơ ị ấ ố ộ ọ ị W0o = 0.1

Tr ng s c t trong đ n v n b t đ n v n a ơ ị ẩ ố ộ ọ ừ ơ ị ẩ Wao = 0.2

Tr ng s c t trong đ n v n b t đ n v n b ơ ị ẩ ố ộ ọ ừ ơ ị ẩ Wbo = -0.1

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

B ướ c 1: D đoán ự

 Đ i v i “cây Iris A” đ u tiên ta tính giá tr xu t c a nút n a ị ấ ủ ố ớ ẩ ầ

oa = f (w0a + w1ax1 + w2ax2 + w3ax3 + w4ax4)

= f (0.0 + 0.1*4.7 + (-0.1)*3.2 + (-0.1)*1.3 + 0.0*0.2)

= f (0.02) = 1/(1 + e -0.02) = 0.5050

 T ng t v i nút n b ươ ự ớ ẩ

ob = f (w0b + w1bx1 + w2bx2 + w3bx3 + w4bx4)

= f (0.0 + (-0.1)*4.7 + 0.2*3.2 + 0.1*1.3 + (-0.1)*0.2)

= f (0.28) = 1/(1 + e -0.28) = 0.5695

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

 Cu i cùng ta tính giá tr xu t cho nút xu t o ị ấ ố ấ

oo = f (w0o + waooa + wboob)

= f (0.1 + 0.2*0.5050 + (-0.1)*0.5695)

= f (0.1440) = 1/(1 + e –0.1440) = 0.5359

(cid:222) Giá tr d đoán cho “cây Iris A” là 0.5359 ị ự

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

B ướ c 2: Xác đ nh sai l ch ị ệ

c (back propagation)  Dùng k thu t lan truy n ng ậ ề ỹ ượ

: giá tr xu t mong mu n V i ớ ị ấ ố to

: giá tr xu t th t ậ ị ấ oo

d Sai l ch c n tính cho nút xu t o: ệ ầ ấ

o = oo(1 - oo)(to - oo)

d Sai l ch c n tính cho nút n h t o là: o ệ ầ ẩ ừ

h(1-oh)who

o

 Trong ví d đang xét “cây Iris A” có t ụ

0 = 0.

Sai l ch c a nút xu t o: ủ ệ ấ

d

o=o0(1-o0)(t0-o0)=0.5359*(1-0.5359)*(0-0.5359) = -0.1333

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

Sai l ch c a ủ nút n a:ẩ ệ

d d

a

= oa(1-oa)wao

o = 0.5050*(1-0.5050)*0.2*(-0.1333)

= -0.0067

Sai l ch c a ủ nút n b:ẩ ệ

d d

b

= ob(1-ob)wbo

o = 0.5695*(1-0.5695)*(-0.1)*(-0.1333)

= 0.0032

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

c c p nh t tr ng s B c 3: B ướ ậ ậ ọ ố

= 0.1 ướ ọ ỉ ệ ọ a h c

a *1 = 0.0 + 0.1*(-0.0067)*1 = -0.0007

a *x1 = 0.1 + 0.1*(-0.0067)*4.7 = 0.0969

a * x2 = -0.1 + 0.1*(-0.0067)*3.2 = -0.1021

a * x3 = -0.1 + 0.1*(-0.0067)*1.2 = -0.1009

Ch n t l w0a = w0a + a *d w1a = w1a + a *d w2a = w2a + a *d w3a = w3a + a *d w4a = w4a + a *d

a * x4 = 0.0 + 0.1*(-0.0067)*0.2 = -0.0001

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

b *1 = 0.0 + 0.1*(0.0032)*1 = 0.0003

b *x1 = -0.1 + 0.1*(0.0032)*4.7 = -0.0985

b * x2 = 0.2 + 0.1*(0.0032)*3.2 = 0.2010

b * x3 = 0.1 + 0.1*(0.0032)*1.2 = 0.1004

b * x4 = -0.1 + 0.1*(0.0032)*0.2 = -0.0999

o*1 = 0.1 + 0.1*(-0.1333)*1 = 0.0867

o * oa = 0.2 + 0.1*(-0.1333)*0.5050 = 0.1933

w0b = w0b + a *d w1b = w1b + a *d w2b = w2b + a *d w3b = w3b + a *d w4b = w4b + a *d w0o = w0o + a *d wao = wao + a *d wbo = wbo + a *d

o * ob = -0.1 + 0.1*(-0.1333)*0.5695 = -0.1076

T t c các tr ng s này s dùng cho các m u k ti p. ẽ ẫ ế ế ấ ả ọ ố

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

 Th tính cho “cây Iris A” thêm m t b ử ộ ướ ế ế c k ti p, có k t qu : ả ế

Oa = f (-0.0007 + 0.0969*4.7 + (-0.1021)*3.2 +

(-0.1009)*1.3 + (-0.0001)*0.2) = f (-0.0032) = 0.4992

Ob = f (0.0003 + -(0.0985)*4.7 + 0.2010*3.2 +

0.1004*1.3 + (-0.0999)*0.2) = f (0.2911) = 0.5724

Oo= f (0.0867 + 0.1933*0.4992 + (-0.1076)*0.5724)

= f (0.1440) = 0.5304

ế ố ế ả ả

ầ ề c đó là 0.5359.  K t qu , ta th y 0.5304 g n v 0 (k t qu mong mu n) so v i ớ k t qu c a b ế ấ c tr ả ủ ướ ướ

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

Tóm t t gi ắ ả i thu t ậ

1

k

Cho tr c K m u d li u : ướ ẫ ữ ệ

{

(

)

)

}

1 , yx

( ,....

x

k y ,

k) và yk ˛

R, k = 1, …, K. v i xớ k = (x1

k, x2

k, …, xn

B c 1: ướ ch n tr ọ ướ ị a c giá tr > 0 và Emax >0.

c 2: ướ ắ ầ ớ ẫ ứ ấ ở ạ ẫ

B kh i t o ng u nhiên w, b t đ u v i m u th nh t k = 1 và gán sai l ch E = 0. ệ

k , y = yk. Đ u ra c a m ng

ướ ọ ủ ạ ầ

k

=

O

k

+

B ắ ầ neuron tính theo: c 3: b t đ u quá trình h c, gán x = x 1

1

exp(

T oW

)

-

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

=

k o l

+

c tính b i: trong đó ok là giá tr ra c a l p n, đ ị ượ ở

1

)

T xw 1

k

ad+

- ủ ớ ẩ 1 exp(

= WW

o

c 4: c p nh t tr ng s neuron đ u ậ ọ ố ầ ướ

(

OOy

)

1(

O

)

B ra: ậ =d - -

v iớ

=

+

ad

B c 5: c p nh t tr ng s c a neuron n ướ ậ ọ ậ ẩ

w l

w l

oW l

l

) xo l

(cho l = 1, …., L) ố ủ 1( -

III.6 Ti p c n m ng Neural (tt) ế ậ ạ

+=

B c 6: tính sai l ch b ng cách c ng thêm sai l ch hi n t i ướ ệ ạ ộ ệ ệ ằ

EE

(

Oy

2)

1 2

-

c 3. N u không thì i B ở ạ ướ ế

B ướ qua B n u k < K thì k = k + 1 và tr l ế c 8. c 7: ướ

c 8: N u E <= E ế ướ ế

max thì k t thúc quá trình h c. Còn n u E > i ở ạ

ọ ớ ằ ắ ầ ọ ộ

B ế Emax gán E = 0 và b t đ u m t chu kỳ h c m i b ng cách tr l B c 3. ướ