Chương 7 : Việc học máy

ij laø troïng soá keát noái giöõa ñôn vò thöù j vaø ñôn vò thöù i, luaät hoïc caäp nhaät troïng troïng soá taïi thôøi ñieåm t+1 ñöôïc thieát laäp laø Wij(t+1) = Wij(t) + Wij(t) Trong ñoù,  laø haèng soá döông ñoù ñöôïc goïi laø toác ñoä hoïc vaø Wij(t) laø löôïng gia taêng troïng soá taïi thôøi ñieåm t. Coù ba theå loïai hoïc trong caùc maïng neuron nhaân taïo ñoù laø hoïc giaùm saùt, hoïc cuûng coá vaø hoïc khoâng giaùm saùt. Hoïc giaùm saùt : cho taäp döõ lieäu vaøo ra mong muoán, quaù trình hoïc caäp nhaät caùc troïng soá keát noái giöõa caùc phaàn töû xöû lyù trong maïng sao cho ngoõ ra that söï cuûa maïng xaáp xæ vôùi ngoõ ra mong muoán cuûa maïng. Hoïc cuûng coá : cuõng laø theå loïai hoïc giaùm saùt, tuy nhieân, tín hieäu ra mong muoán cuûa maïng laø tín hieäu cuûng coá ñoù laø tín hieäu thöôûng vaø phaït. Quaù trình hoïc, caäp nhaät caùc troïng soá keát noái giöõa caùc ñôn vò xöû lyù sao cho ngoõ ra thaät söï cuûa maïng xaáp xæ vôùi ngoõ ra mong muoán thöôûng vôùi ñoä tin caäy caøng cao caøng toát. Hoïc khoâng giaùm saùt : laø theå loïai hoïc khoâng coù döõ lieäu ra mong muoán, quaù trình hoïc vôùi taäp döõ lieäu vaøo mong muoán, maïng töï caäp nhaät caùc troïng soá keát noái döïa treân cô sôû taäp döõ lieäu vaøo mong muoán sao cho ngoõ ra thöïc söï cuûa maïng thích nghi vôùi ngoõ vaøo mong muoán. 2) Maïng truyeàn thaúng vaø giaûi thuaät hoïc lan truyeàn ngöôïc : Cho maïng truyeàn thaúng ba lôùp nhö ñöôïc moâ taû treân, vaø vôùi haøm chi phí ño tín hieäu sai soá giöõa ngoõ ra thöïc söï yi (k) cuûa maïng vaø ngoõ ra mong muoán di (k) cuûa maïng cho bôûi moãi maãu tín hieäu vaøo mong muoán X(k) laø Giaûi thuaät hoïc lan truyeàn ngöôïc caäp nhaät troïng soá keát noái trong maïng ñöôïc moâ taû goàm caùc böôùc sau : Böôùc 0 : Nhaäp taäp maãu huaán luyeän vaøo ra mong {X(k), d(k), cho k = 1, . . . ,p}, trong ñoù X(k) laø veùctô maãu vaøo vaø d(k) laø veùctô maãu ra. Thieát laäp toác ñoä hoïc , sai soá cho pheùp hoäi tuï Emax , troïng soá khôûi taïo, E = 0 vaø k = 1. Böôùc 1 : Truyeàn tín hieäu chuyeån tieáp töø lôùp vaøo, qua lôùp aån vaø ñeán lôùp ra. Cho q = 1 ñeán l Cho i = 1 ñeán n Böôùc 2 : Tính sai soá chuan 2 giöõa ngoõ ra mong muoán vaø ngoõ ra thöïc söï cuûa maïng. Böôùc 3 : Lan truyeàn ngöôïc caäp nhaät troïng soá keát noái giöõa caùc lôùp. Cho i = 1 ñeán n Cho i = 1 ñeán n Cho q = 1 ñeán l Cho q = 1 ñeán l Cho q = 1 ñeán l Cho j = 1 ñeán m Böôùc 4 : Kieåm tra neáu k < p thì taêng k = k + 1 vaø quay veà böôùc 1; maët khaùc ñeán böôùc 5. Böôùc 5 : Kieåm tra neáu E < Emax thì döøng thuû tuïc huaán luyeän; maët khaùc thieát laäp E = 0 vaø k = 1 vaø quay veà böôùc 1 thöïc hieän moät theá heä huaán luyeän khaùc. 3) Ví Duï ÖÙng duïng : Cho Robot töï haønh di chuyeån treân maët phaúng keû löôùi hai chieàu nhö hình veõ Robot ñöôïc gaén boán caûm bieán ñeå nhìn boán höôùng nhö S1 (North), S2(East), S3(South) vaø S4(West). Neáu oâ naøo baát kyø xung quanh robot chöùa chöôùng ngaïi vaät, caûm bieán traû veà chöõ soá 1; maët khaùc caûm bieán traû veà chöõ soá 0. Vôùi baøi toùan Robot hoïc ñeå traùnh chöôùng ngaïi vaät, moät maïng truyeàn thaúng ba lôùp ñöôïc thieát laäp coù caáu truùc maïng laø Vôùi caùc ngoõ vaøo cuûa maïng laø caùc giaù trò traû veà cuûa caùc caûm bieán vôùi caùc chöõ soá 1 vaø 0 öùng vôùi caùc ngoõ ra mong muoán cuûa maïng ñoù laø neáu höôùng naøo khoâng chöùa chöôùng ngaïi vaät thì ngoõ ra cuûa höôùng ñoù laø chöõ soá 1; maët khaùc ngoõ ra mong muoán cuûa maïng laø chöõ soá 0. Treân cô sôû ñoù, ta coù taäp maãu döõ lieäu vaøo ra mong muoán ñeå huaán luyeän maïng cho robot hoïc traùnh chöôùng ngaïi vôùi caùc chuoåi nhò phaân vaøo ra mong muoán laø 7.4) Giaûi Thuaät Di Truyeàn (Generic Algorithm) : Giaûi thuaät di truyeàn döïa vaøo söï tieán hoùa cuûa luaät di truyeàn sinh hoïc sinh saûn lai gheùp gene giöõa cha vaø meï trong töï nhieân toàn taïi vaø phaùt trieån töø theá heä naøy sang theá heä khaùc vôùi theá heä môùi toàn taïi thích nghi vôùi moâi tröôøng soáng môùi hôn theá heä cha oâng. Quaù trình tieán hoùa sinh saûn trong töï nhieân toàn taïi vaø phaùt trieån töø theá heä naøy sang theá heä khaùc bao goàm choïn loïc töï nhieân (Natural selection), lai gheùp (Cross) vaø ñoät bieán (mutation). Choïn loïc töï nhieân :Moät quaàn theå (population) chöùa nhieàu caù theå (individual), chæ coù nhöõng caù theå thích nghi nhaát vôùi moâi tröôøng soáng môùi, môùi toàn taïi trong cuoäc ñaáu tranh sinh toàn; maët khaùc nhöõng caù theå khoâng thích nghi vôùi moâi tröôøng soáng môùi seõ bò ñaøo thaûi. Lai ghep : Ñôn vò di truyeàn caáp teá baøo laø nhieãm saéc theå (Chromosome) hay coøn ñöôïc goïi laø caù theå trong quaàn theå; trong ñoù, moãi nhieãm saéc theå goàm nhieàu gen. Trong qua trình lai gheùp nhieãm saéc theå cuûa cha meï bò phaân chia vaø taïo neân nhieãn saéc theå cuûa con. Nhö vaäy, nhieãm saéc theå cuûa con bao goàm moät soá gen cuûa cha vaø moät soá gen cuûa meï. Thoâng qua quaù trình lai gheùp (sinh saûn), nhöõng gen toát nhaát cuûa cha vaø meï ñöôïc truyeàn töø ñôøi naøy sang ñôøi khaùc. Ñoät bieán : Moãi caù theå chöùa nhieàu gen vaø caùc gen coù thay ñoåi moät caùch ngaãu nhieân do loãi trong qua trình di truyeàn vôùi xaùc suaát xaûy ra ñoät bieán trong töï nhieân raát thaáp. Quaù trình ñoät bieán laø tìm nhöõng nhieãm saéc con thích nghi nhaát trong moâi tröôøng soáng môùi. Giaûi thuaät di truyeàn cô baûn (GA) ñöôïc moâ taû baèng löu ñoà khoài nhö hình Hoïi tuï Giaûi thuaät di truyeàn cô baûn vôùi caùc caù theå cuûa quaàn theå maõ hoùa baèng chuoåi nhò vôùi mieàn caùc caù theå trong quaàn theå laø [a,b] ñöôïc moâ taû toùm taét trong caùc böôùc nhö sau : Böôùc 0 : Khôûi taïo quaàn theå vôùi caùc caù theå cuûa quaàn theå laø xi, i = 1, . . ,N duøng haøm ngaãu nhieân taïo ra N caù theå trong moät quaàn theå.ø t = 0; for i = 1: N xi,t = random(a,b); end; Böôùc 1 : Choïn loïc ngaãu nhieân, tìm caùc caù theå trong quaàn theå coù ñoä thích nghi toát nhaát thoâng qua haøm thích nghi fitness. Cho f(x) laø haøm muoán tìm cöïc ñaïi hoaëc cöïc tieåu. Neáu f(x) laø haøm cöïc tieåu, haøm thích nghi ñöôïc thieát laäp laø fitness(x) = 1/f(x) Neáu f(x) laø haøm tìm cöïc ñaïi, haøm thích nghi ñöôïc thieát laäp laø fitness(x) = f(x) Giaûi thuaät choïn loïc ngaãu nhieân ñöôïc moâ taû laø for i = 1:N b = random(0,1); k = 1; while k < N & b < k = k + 1; end; xi,t+1 = xk,t; end; Böôùc 2 : Maõ hoùa caùc caù theå trong quaàn theå baèng chuoåi nhò phaân duøng coâng thöùc laø for i = 1:N Si,t+1 = binn (round((2n – 1)(xi,t+1 – a)/(b –a))) end; Trong ñoù binn laø haøm bieán ñoåi soá nguyeân thaäp phaân sang soá nhò phaân, a laø caän döôùi, b laø caän treân cuûa bieán caù theå trong quaàn theå vaø n laø chieàu daøi cuûa chuoåi nhò phaân. Haøm binn bieán ñoåi soá nguyeân döông sang chuoåi nhò nhaân ñöôïc thieát vôùi caùc voøng laëp laø for k = 1: n s[k] = remainder = (num)mode(2); num = round(num/2); end; for k = n : 1 s(k) = S(n – k + 1); end; Böôùc 3 : Choïn hai nhieãm saéc theå vôùi ñoä thích nghi toát nhaát, moät nhieãm saéc theå goïi laø parent1 vaø moät nhieãm saéc theå khaùc goïi laø parent2, lai gheùp caùc gen trong hai nhieãm saéc theå naøy ñeå taïo ra caùc nhieãm saéc theå con môùi child1 vaø child2 baèng phöông phaùp lai gheùp moät ñieåm nhò phaân ngaãu nhieân vôùi giaûi thuaät ñöôïc moâ taû laø for i = 1:2:N-1 if random(0,1) <= PC then pos = random{1,. . .,n-1}; for k = pos + 1:n parent = si,t+1[k]; si,t+1[k] = si+1,t+1[k]; si+1,t+1[k] = parent; end; end; end; Trong ñoù, PC laø xaùc suaát lai gheùp thöôøng laø giaù trò raát lôùn ñieån hình PC = 0.9 Böôùc 4 : Ñoät bieán moät ñieåm, gen naøo trong nhieãn saéc theå coù xaùc suaát ngaãu nhieân laø nhoû hôn xaùc suaát ñoät bieán cho tröôùc PM, thì ñaûo bít gen ñoù. Giaûi thuaät ñoät bieán moät ñieåm ngaãu nhieân nhò phaân laø for i = 1:N for k = 1: n if random(0,1) < PM then invert(Si,t+1[k]); end; end; end; Trong ñoù haøm invert laø haøm ñaûo bit vaø PM laø xaùc suaát ñoät bieán cho tröôùc vôùi giaù trò raát nhoû ñieån hình laø PM = 0.1. Böôùc 5 : Giaûi maõ, giaûi maõ chuoåi nhò phaân ñeå traû veà giaù trò thöïc cuûa caùc caù theå trong quaàn theå duøng coâng thöùc giaûi maõ laø for i = 1 : N xi,t+1 = a + binn-1(si,t+1).((b – a)/(2n – 1)); end; trong ñoù, binn-1(s) laø haøm bieán ñoåi chuoåi nhò phaân veà daïng soá nguyeân döông ñoù laø Böôùc 6 : Kieåm tra neáu giaûi thuaät hoäi tuï thì döøng; maët khaùc, thieát laäp t = t + 1; quay veà böôùc 1. Ví duï : Tìm giaù trò cöïc ñaïi cuûa haøm f(x) = x2,Trong ñoù x thuoán veà mieàn [0,31]. Choïn kích thöôùc cuûa quaàn theå laø N = 4, Xaùc suaát lai gheùp laø PC = 1, xaùc suaát ñoät bieán laø PM = 0.001 vaø chieàu daøi chuoåi nhò phaân laø n = 5. Vôùi giaûi thuaät cho treân cho keát quaû ban ñaàu laø Quaù trình choïn loïc vaø lai gheùp cho theá heä môùi laø