Despre invatare automata：despre invatare自动机

Despre invatare automata：despre invatare自动机 Capitolul 9 INVATAREA AUTOMATA 9.1 Principii de baza In dezvoltarea programelor de invatare automata se pot distinge trei etape: (1) etapa optimista in care se considera posibila realizarea sistemelor cu autoreglare care s-ar putea modifica si adapta mediului (1960-1965) dar care a fost abandonata datorita limitarilor teoretice si a capacitatii de calcul limitate, pina de curind cind cercetarile legate de retelele neuronal au reluat aceaasta directie; (2) etapa deschisa de teza lui P. Winston (1970) in care invatarea este vazuta ca un proces complex si dificil; aceasta perspectiva a dus la studiul unor forme de invatare mai simple si, pe de alta parte, la ideea ca un sistem de invatare automata trebuie sa contina o cantitate semnificativa de cunostinte apriorice pentru a aajunge la performante; (3) etapa a treia determinata de necesitatea de achizitie a cunostintelor in sisteme expert. Spre deosebire de etapele (1) si (2) care s-au concentrat numai pe invatarea prin memorare si invatarea din exemple, etapa (3) se ocupa si de invatarea prin instruire directa si invatarea prin analogie. Se pot identifica patru perspective asupra invatarii: , Invatarea este procesul prin care un sistem isi imbunatateste performantele (Herbert Simon). , Invatarea este achizitia cunostintelor explicite; aceasta perspectiva porneste de la necesitatea exprimarii explicite a cunostintelor invatate pentru a facilita verificarea, modificarea si explicarea lor in sistem. , Invatarea este achizitiaa deprinderilor de rezolvare a problemelor (desi oamenii inteleg ce trebuie sa faca cind li se explica cum trebuie sa faca ceva, nu ajung imediat la operatii eficiente). , Invatarea este formare teoriilor, formarea ipotezelor si inferenta inductiva; deci procesul de invatare este privit din punct de vedere al stiintei. 9.2 Un model al invatarii Plecind de la definitia lui Simon, se pote construi un model simplificat al procesului de invaatare care permite si clasificareaa diverselor tipuri de invatare automata. Mediul ofera stimuli sau informatie elementului de invatare (EI), elementul de invatare foloseste aceasta informatie pentru a imbunatati cunostintele (explicite) din baza de cunostinte si elementul de prelucrare (EP) foloseste baza de cunostinte pentru a rezolva problema. In final, infomatia obtinuta in incercarea de a rezolva problema poate servi caa "feedback" pentru elementul de invatare. Mediul, baza de cunostinte si elementul de prelucrare determina natura problemei particulare de invatare si deci functiile particulare pe care elementul de invatare trebuie sa le realizeze. StimuliFeedbackElement de Mediu invatare(informatie) (profesor) Baza deEvaluator al cunostinteprelucrarilor informatieElementul de prelucrare (actiune)prelucrare Figura 9.1 Un model simplificat al procesului de invatare 9.2.1 Mediul Mediul influenteaza procesul de invatare prin nivelul si calitatea informatiei oferite. Nivelul informtiei se refera la gradul de generalitate al acesteia (abstract,detaliat). Elementul de invatare are rolul de a reduce diferenta dintre nivelul la care informatia este transmisa de mediu si nivelul la care elementul de prelucrare o poate utiliza pentru a rezolva problema. Daca elementul de invatare primeste sfaturi generale (abstracte) trebuie sa completeze detaliile astfel incit elementul de prelucrare sa poata interpreta informatia intr-o situatie data, iar daca elementul de invatare primeste informatii specifice despre o situatie particulara, elementul de invatare trebuie sa generalizeze aceasta informatie (prin ignorarea detaliilor nesemnificative) pentru a ghida elementul de prelucrare intr-o clasa mai larga de situatii. Elementul de invatare trebuie sa faca presupuneri (deoarece cunostintele lui sint imperfecte), adica sa formeze ipoteze despre cum sa reduca diferenta. Dupa aceasta, sistemul trebuie sa primeasca un "feedback" pe baza caruia sa evalueze ipotezele formate. In acest fel, un sistem de invatare invata prin incercare si eroare. Se pot identifica patru tipuri de invatare: 2 (1) Invatare prin memorare. Mediul ofera informatii exact la nivelul elementul de prelucrare (al problemei de rezolvat), deci nu trebuie sa se formeze ipoteze. (2) Invatare prin instruire. Informatia din mediu este abstracta sau generala si elementul de instruire trebuie sa presupuna (sa genereze ipoteze pentru) detaliile care lipsesc. (3) Invatarea din exemple. Informatia din mediu este specifica si detaliata, iar elementul de invatare trebuie sa formeze ipoteze despre reguli generale. (4) Invatarea prin analogie. Informatia din mediu este relevanta numai pentru probleme similare si elmentul de invatare trebuie sa descopere analogia si sa formeze ipoteze despre reguli similare pentru problema curenta. Din punct de vedere al calitatii informatiei oferite de mediu, aceasta poate fi aleatorie sau nu, cu zgomot sau nu, selectata cu grija de profesor sau nu. 9.2.2 Baza de cunostinte Procesul de invatare este influentat de forma si continutul cunostintelor din baza de cunostinte. Din punct de vedere al formei conteaza metoda de reprezentare a cunostintelor si capacitatea de extensibilitate a reprezentarii. Pentru ca programul de invatare sa poata utiliza explicit cunostintele dobindite, trebuie sa existe o meta-descriere care sa arate cum sint structurate cunostintele. Uneori meta-cunostintele sint introduse explicit ca parte a baza de cunostinte, alteori sint codificate implicit. Scopul acestora este de a permite elementului de prelucrare sa-si modifice propriile reprezentari prin adaugarea de noi termeni in vocabular si noi structuri de reprezentare. Continutul bazei de cunostinte trebuie sa specifice initial cunostinte despre problema, care sa ajute la formarea, testsrea si rafinarea ipotezelor. 9.2.3 Elementul de prelucrare Elementul de prelucrare depinde de complexitatea tipului de problema de rezolvat: clasificare sau predictie pe baza unui singur concept, sinteza conceptelor multiple, probleme de planificare, deci sinteza unor secvecte de executie a actiunilor. O componenta importanta care influenteaza elementul de prelucrare este evaluatorul actiunilor deoarece elementul de prelucrare trebuie sa aiba o posibilitate de a-si valida sau corecta ipotezele facute. Anumite sisteme de invatare au cunostinte separate pentru evaluare (de exemplu sistemul AM are reguli euristice care determina interesul descoperirii de noi concepte). Alte sisteme asteapta de la mediu sau profesor un standard de evaluare pentru a compara ipoteza curenta (de exemplu in sistemele de invatare din exemple standardul de evaluare extern este clasificarea corecta a fiecarui exemplu). 9.2.4 Exemple de tipuri de invatare Invatarea prin memorare. Sistemul de invatare nu prelucreaza informatia pentru a o intelege deoarece aceasta este data chiar sub forma in care poate fi utilizata de EP. EI doar memoreaza informatia pentru o utilizare ulterioara.. Un exemplu este sistemul de invatare a lui Samuel ce isi imbunatateste performantele in jocul de sah prin memorarea fiecarei pozitii de pe tabla de sah ce a 3 fost evaluata; pozitiile anterior memorate sint utilizate pentru cresterea vitezei si pentru cresterea numarului de mutari investigate in avans. Invatarea prin instruire directa. Informatia primita din mediu este abstracta sau generala. Elementul de invatare trebuie sa o transforme intr-o forma utilizabila de elementul de prelucrare. Aceasta transformare se numeste operationalizare. Sistemul trebuie sa inteleaga si sa interpreteze cunostintele de nivel ridicat, apoi sa le coreleze cu ceea ce stie deja (TERESIAS, FOO). Sistemul FOO ce invata reguli de jucat carti, trebuie sa operationalizeze indicatii strategice de tipul "Evita sa iei puncte" in strategii specifice de tipul "Pune o carte mai mica decit orice carte jucata pina in acest moment". Invatarea din exemple. Sistemul trebuie sa generalizeze exemplele in reguli de nivel mai ridicat ce pot fi aplicate in ghidarea elementului de prelucrare. Un program care invata conceptul de pereche intr-un joc de carti, trebuie sa sintetizeze din doua exemple de tipul: 4 pica 4 trefla 5 caro 7 cupa 7 pica 6 trefla 6 caro 9 cupa conceptul de descriere a unei perechi: doua carti de acelasi rang, indiferent de culoare si de valoarea celorlalte carti. Invatarea prin analogie. Acest tip de invatare, putin studiat pina in prezent, ridica probleme ca: ce este analogia, cum sint recunoscute analogiile, cum se transfera cunostintele relevante. Un sistem cu o baza de cunostinte continind cunostinte despre diagnosticarea bolilor umane poate invata prin analogi diagnosticarea defectelor din calculatoare, prin corelarea simptomelor pacientilor cu disfunctiuni ale calculatorului, a tratamentului unei boli cu o metoda de depanare, etc. 9.3 Invatarea prin memorare Invatarea prin memorare consta in salvarea cunostintelor noi a.i. in momentul in care acestea sint din nou necesare singuara problema sa fie regasirea lor si nu calculul sau inferarea acestora. Elementul de prelucrare rezolva problema iar elementul de invatare tine minte problema si solutia acesteia. Elementul de prelucrare poate fi vazut ca o functie f care considera un element de intrare (X,...,X) si calculeaza un sablon de iesire (Y,...,Y) iar invatarea consta in memorarea 1n1p perechii asociate [(X,...,X)(Y,...,Y)]. In timpul unor calcule ulterioare care necesita 1n1p f(X,...,X) elementul de prelucrare poate regasi (Y,...,Y) din memorie in loc sa-l calculeze. 1n1p fdepune(X,...,X)(Y,...,Y)[(X,...,X)(Y,...,Y)],,,,,,,,1n1p1n1p Sablon deFunctii deSabloane dePereche asociata intrareprelucrareiesire Asa cum calculele pot fi reduse la tabele de corespondente de valori, tot asa acest tip de invatare poate fi privit ca reducerea deductiilor la asocieri de valori. Problemele care apar in acest tip de invatare sint: 4 (1) Organizarea memoriei in asa fel incit regasirea sa fie mai rapida decit calculul sau deductia. (2) Stabilitatea mediului (informatia memorata sa fie valabila si ulterior) realizata fie prin monitorizarea schimbarilor mediului si actualizarea cunostintelor memorate, fie prin verificarea valabilitatii cunostintelor la fiecare regasire. (3) Evaluarea informatiei inaintea fiecarei memorari sau memorarea tuturor informatiilor si eliminarea ulterioara a acelora ce se dovesesc a nu mai fi utile. Se prezinta in continuare ca exemplu programul de jucat sah a lui Samuel. Programul contine regulile de jucat sah corect si trebuie sa invete sa joace sah bine prin memorarea si regasirea pozitiilor pe tabla de sah intilnite in jocuri anterioare. Strategia de rezolvare a problemei este cautarea intr-un arbore de joc minmax in care se inspecteaza toate urmatoarele trei miscari posibile si se foloseste o functie de evaluare statica pentru a estima miscrea cea mai buna de executat. Programul memoreaza fiecare miscare selectata impreuna cu valoarea functiei de evaluare. AB CD La reluarea jocului, in momentul intilnirii unei aceleiasi pozitii (A), aceasta nu se mai evalueaza ci se utilizeaza valoarea deja memorata. Avantajul principal al acestei abordari consta insa in faptul ca valoarea memorata pentru pozitia A este o mai buna estimare a sanselor de cistig prin alegerea acestei mutari decit daca s-ar aplica din nou functia de evaluare pentru A; daca valoarea memorata pentru A intervine in calculul estimarii unei mutari X, estimarea lui X se va face pe baza inspectarii a 6, 9, ... mutari in avans. Aceasta abordare imbunatateste adincimea efectiva de cautare pentru mutarea X. EA D 5 Programul a memorat un numar de aproximativ 53.000 de pozitii in urma mai multor partide succesive iar performantele lui au ajuns la nivelul unui jucator mediu de sah. S-a estimat ca programul ar trebui sa ajunga sa memoreze un numar de aproximativ 1 milion de pozitii pentru a atinge nivelul de competenta a unui campion de sah. 9.4 Invatarea prin instruire directa Cercetarile in domeniul invatarii prin instruire s-au ocupat de dezvoltarea unor sisteme ce accepta sfaturi la nivel abstract si le transforma in reguli ce pot ghida efectiv elementul de prelucrare, incercind astfel automatizarea completa a procesului de instruire (4.1). Pe de alta parte, tot in acest tip de invatare pot fi incluse si cercetarile in domeniul dezvoltarii de instrumente de ingineria cunostintelor cum ar fi editoare de baze de cunostinte, depanatoare simbolice ale procesului de deductie, verificatoare ale consistentei bazei de cunostinte, etc. (4.2). In aceste abordari expertul este o parte integranta a sistemului de instruire; succesul comercial al actualelor medii de dezvoltare a sistemelor expert a dovedit viabilitatea acestor directii de cercetare. 9.4.1 Automatizarea instruirii directe Etapele necesare in automatizarea instruirii directe sint: (1) Cerere de sfaturi de la expert. (2) Interpretarea sfaturilor si transformarea lor in reprezentare interna. (3) Operationalizare, i.e. transformarea sfaturilor intr-o forma direct utilizabila de elementulde prelucrare. (4) Integrarea cunostintelor in baza de cunostinte. (5) Evaluarea actiunilor efectuate de elementul de prelucrare. Sistemul FOO Sistmul FOO (J. Mostow) invata reguli din domeniul jocurilor de carti pe baza sfaturilor date de un expert. Activitatea sistemului poate fi vazuta ca o activitate de planificare in care un sfat de tipul "Evita sa iei puncte" este interpretat ca un scop iar programul trebuie sa dezvolte un plan executabil pentru a realiza acest scop. Dificultatea consta in faptul ca scopul poate fi prost definit sau imposibil de realizat deci programul trebuie sa dezvolte strategii aproximative. Sistemul FOO nu realizeaza pasul (2) care ar consta in traducerea sfaturilor din limbaj natural in forma interna, ci este necesar ca utilizatorul sa prezinte sfaturile direct in forma de reprezentare folosita de sistem. Desi contine o baza de cunostinte cu reguli de transformare a sfaturilor generale in reguli specifice si un interpretor de aplicare a acestor reguli, utilizatorul trebuie sa indice ce reguli sa se aplice si ce parte a expresiei (sfatului) sa se transforme; practic strategia de control a sistemului este indicata de utilizator. Cu toate aceste limitari drastice, programul a permis o analiza detaliata a tehnicilor necesare operationalizarii. 6 Baza de cunostinte a sistemului contine: concepte ale domeniului cum ar fi carte, culoare, rang, levata, jucator, preia; sfaturi sub forma de restrictii cum ar fi fiecare jucator pune o carte la culoare, jucatorul cu cartea de rang cel mai mare cistiga levata; sfaturi sub forma de euristici cum ar fi preia toate punctele dintr-un joc, daca nu se pot prelua toate punctele dintr-un joc atunci preia cit mai putine puncte. Un exemplu de operationalizare a sfatului "Evita sa iei puncte" este: (a) pentru a evita sa iei puncte in general, trebuie sa eviti sa iei puncte in levata curenta (b) daca o levata contine puncte, trebuie sa incerc sa nu o preiau (c) pot sa fac (b) prin evitarea cartii cistigatoare (d) pot sa realizez (c) jucind o carte mai mica decit cele jucate pina in prezent. Se aplica deci o strategie de reducere a problemelor pina cind sfatul se poate aplica direct la situatia data. Prin operationalizare sfatul initial (evita (ia_puncte eu) (levata)) se transforma in (scop (not (or [in_timpul (fiecare j (jucatori) (joaca_carte j)) (ia_puncte eu)] [in_timpul (ia_levata (cistigator_levata)) (ia_puncte eu)]))) iar prin alte operationalizari succesive, forma finala este (scop (implicatie (and (carte_mare_culoare (carte eu)) [posibil (levata_are_puncte)]) [carte_mica (carte eu)])) 9.5 Invatarea prin inductie (din exemple) 9.5.1 Principii de baza Procesul inductiv poaate fi descris simbolic prin urmatorul model. Fie P si Q doua predicate; daca P(a),P(a),...,P(a)(x) P(x),se constata ca se poate generaliza prin inductie . Mai general, 12k P(a)Q(b),P(a)Q(b),...,P(a)Q(b),,,daca se observa implicatiile se poate 1122kk (x,y) P(x)Q(y),,generaliza prin inductie . La formarea unei ipoteze generalizate despre o clasa completa (posibil infinita) prin observarea numai a unei parti a membrilor ei, se deduce o concluzie incerta, aceasta fiind forma esentiala a invatarii inductive. Fiind date: (1) observatii (exemple) (2) cunostintele de baza ale domeniului (3) scopuri sau criterii de evaluare 7 elementul de invatare trebuie sa gaseasca o asertiune inductiva sau un concept care implica toate exemplele observate si este consistent atit cu (2) cit si cu (3). Se definesc o serie de notiuni cu care se opereaza frecvent in invatarea inductiva. , Obiect - O entitate ce poate fi descrisa printr-o serie de atribute si relatiile intre acestea. , Clasa - Fiind dat un univers de obiecte U, o clasa este un subset al lui U. , Concept - O descriere a unei clase sau o regula care partitioneaza universul de obiecte U in doua multimi, una care satisface descrierea sau regula si alta ce nu satisface. , Ipoteza - o asertiune despre anumite obiecte din universul U; este un concept tentativ care imparte universul de obiecte. , Concept tinta - Un concept care clasifica corect toate obiectele din univers. , Exemple (instabte) pozitive - exemple de obiecte care apartin conceptului tinta. , Exemple (instante) negative - exemple de obiecte care nu apartin conceptului tinta. , Regula de clasificare consistenta - o regula care este adevarata pentru toate exemplele pozitive si falsa pentru toate exemplele negative. , Inductie - procesul de formare a claselor. Localizarea unui singur concept intr-un univers care contine n obiecte este o problema de cautare exponentiala deoarece universul tuturor multimilor dihotomice (C si U-C) continind n nobiecte poate fi reprezentat ca o structura de latice cu n noduri, deci 2 posibilitati. Cautarea regulilor de descriere a unui concept este ghidata de multimea exemplelor. Se pot deci identifica doua spatii de cautare intr-o problema de invatare inductiva: spatiul instantelor (al exemplelor) si spatiul conceptelor (al regulilor). Un sistem de invatare din exemple poate fi vazut ca un sistem de cautare simultana si cooperativa in aceste doua spatii. Doua aspecte principale sint legate de spatiul conceptelor: modalitate de reprezentare a acestuia si strategia de cautare. Metoda de reprezentare a spatiului conceptelor este importanta deoarece aceasta trebuie sa permita realizarea usoara a diferitelor prelucrari din sistem. In timpul procesului de invatare pot apare doua procese executate alternativ: generalizare si specializare. Generalizarea reprezinta formarea descrierii sau regulii pentru o clasa mai larga decit aceea care este consistenta cu exemplele, iar specializarea reprezinta formarea unei descrieri sau reguli mai restrictive dar consistenta cu exemplele. Specializarea poate fi necesara daca elementul de invatare supra-generalizeaza; o ipoteza supra-generalizata este inconsistenta deoarece include si exemple negative pe linga cele pozitive. Exemple de metode de specializare: , schimbarea variabilelor (dintr-un concept) in constante , adaugarea unei conjunctii , eliminarea unei disjunctii 8 Exemple de metode de generalizare: , schimbarea constantelor in varibile , eliminarea conditiilor din descriere (eliminarea conjunctiilor) , adaugarea unei alternative (adaugarea disjunctiilor) , parcurgerea in sus a arborelui de concepte, in cazul in care universul de obiecte este structurat taxonomic , inchiderea intervalului; daca doua sau mai multe exemple au valori numerice se (d,d)ij ordoneaza aceste valori si se considera ca valoare in concept intervalul [min(d,d),max(d,d)]ijij , generalizarea constructiva; o serie de predicate EstePe(f,f)EstePe(f,f)EstePe(f,f),, 213243 se poate generaliza la EstePrimul(f)EsteUltimul(f), 41 Metodele de cautare in spatiul conceptelor pot fi clasificate in functie de modul in care rafineaza multimea I de ipoteze curente: metode conduse de date, in care exemplele de invatare ghideaza cautarea, si metode conduse de modele, in care un model apriori ghideaza cautarea. In continuare se vor prezenta citiva algoritmi de invatare care folosesc metoda de cautare condusa de date. 9.5.2 Sistemul de invatare W Acest sistem invata un singur concept din exemple pozitive si negative, notate cu ex+ si respectiv ex-, utilizind o reprezentare unica a acestuia. In general invatarea conceptelor simple are ca scop rezolvarea problemelor de clasificare si predictie. Odata sintetizat conceptul, acesta poate fi utilizat pentru a clasifica (sau a prezice iesirea asociata pentru) noi instante ca exemple pozitive sau negative. Multimea I de ipoteze curente este initializata astfel incit sa contina toate ipotezele consistente cu primul exemplu pozitiv (ipotezele se refera la un singur concept tentativ). Exemplele pozitive si cele negative urmatoare sint examinate pe rind si identificate cu multimea de ipoteze pentru a determina generalizarile si specializarile necesare. Algoritmul folosit face parte din categoria algoritmilor cu "decizii intirziate", deoarece setul de ipoteze I nu se modifica decit in cazul in care sistemul este fortat sa faca aceasta modificare pe baza unui exemplu particular. Exemplele pozitive forteaza algoritmul sa generalizeze, iar exemplele negative forteaza algoritmul sa specializeze. Spatiul conceptelor se restringe gradual in acest mod pina cind include un singur concept. Algoritmul W, creat de P. Winston, foloseste metoda de cautare condusa de date, strategia de control fiind cautarea in adincime. 9 Scopul sistemului este de a invata concepte din lumea blocurilor. Forma unui obiect din lumea blocurilor este prezentata initial sub forma de desen, care este apoi interpretat intr-o descriere a obiectului sub forma de retea semantica. Winston foloseste retelele semantice pentru a reprezenta atit exemplele, cit si conceptele si o parte a cunostintelor initiale despre problema. Conceptele initiale (predefinite) sint organizate intr-o ierarhie taxonomica. Se considera in continuare functionarea sistemului pentru invatarea conceptului de Arc din lumea blocurilor. Algoritmul incepe intotdeauna cu un exemplu pozitiv tipic. Arc acoperisa sustine a sustine parte stingab b c la dreapta la stinga parte dreaptac Fie apoi urmatorul exemplu un exemplu negativ limita, adica un exemplu care nu face parte din clasa datorita unor diferente minime. Ex- 1 acoperisa b c parte stinga ab la dreapta la stinga parte dreaptac Din compararea celor doua structuri se deduce ca relatia sustine este esentiala pentru concept deci se modifica in model in trebuie sa sustina (euristica legaturii obligatorii). Urmatorul exemplu este tot un exemplu negativ limita. 10 Ex- 2 acoperisa trebuie sa sustina a trebuie sa sustina parte stingab b c alaturi la dreapta la stinga parte dreaptac Din comparare cu modelul se deduce ca relatia alaturi intre parte singa si parte dreapta este interzisa, deci relatia devine nu alaturi (euristica legaturii interzise). Din arborele taxonomic de concepte stie ca a ISA paralelipiped. Urmatorul exemplu este un exemplu pozitiv care generalizeaza. Ex+ 3 acoperisISAapiramida trebuie sa sustina a trebuie sa sustina parte stingab b c nu alaturi la dreapta la stinga parte dreaptac Deoarece exista relatiile paralelipiped ISA bloc si piramida ISA bloc, se poate aplica euristica parcurgerii in sus a arborelui de concepte si se ajunge la concluzia ca a AKO bloc. Daca paralelipiped si piramida ar fi singurele clase de obiecte existente, fara ca acestea sa fie organizate ierarhic, s-ar putea aplica euristica largirii domeniului prin introducerea unei noi clase care sa le insumeze pe acestea doua. Modelul final este urmatorul: 11 Arc acoperisAKOabloc trebuie sa sustina trebuie sa sustina parte stingaISAbparalelipiped nu alaturi la dreapta la stinga parte dreaptaISAcparalelipiped Algoritm: Algoritmul de invatare W Specializare 1. daca exista o singura diferenta importanta intre concept si exemplu atunci 1.1. daca conceptul are o legatura care nu este in ex- atunci foloseste euristica legaturii obligatorii 1.2. daca ex- are o legatura ce nu este in concept atunci foloseste euristica legaturii interzise 2. altfel ignora exemplul sfirsit. Generalizare 1. daca diferenta este legatura indica o clasa C1 in concept , clasa C2 din ex+ atunci 1.1. daca C1 si C2 sint clase intr-un arbore taxonomic atunci foloseste euristica parcurgerii in sus a arborelui de concepte 1.2. altfel 1.2.1. daca C1 si C2 formeaza o multime exhaustiva atunci foloseste euristica eliminarii legaturii 1.2.2. altfel foloseste euristica largirii domeniului de valori 2. daca diferenta este legatura lipseste fie in concept fie in ex+ atunci foloseste euristica eliminarii legaturii 3. daca diferenta este valori numerice diferite sau o valoare numerica si un interval atunci foloseste euristica inchiderii intervalului 4. daca alta diferenta 12 atunci ignora exemplul sfirsit. Invatare 1. Initializeaza descrierea conceptului curent I cu reteaua semantica corespunzatoare primului exemplu 2. repeta 2.1. Considera urmatorul exemplu si converteste-l intr-o retea semantica 2.2 Identifica exemplul cu I pentru a obtine subgraful maximal comun /* foloseste pentru aceasta un algoritm de identificare a doua grafuri */ 2.3. Foloseste subgraful comun pentru a stabili cum se modifica I 2.4. daca exemplul este pozitiv atunci 2.4.1. Generalizare 2.4.2. daca exista mai multe posibilitati de generalizare atunci alege una si depune restul intr-o lista de backtrack 2.5. daca exemplul este negativ atunci Specializare pina nu mai sint exemple sfirsit. Caracteristicile algoritmului W: , Odata ce a invatat ceva, nu mai uita , Daca exista incertitudini asupra a ceea ce trebuie sa invete, nu se mai invata nimic P(x)Q(y),, Algoritmul nu poate invata concepte disjunctive () datorita strategiei deciziilor intirziate pe baza careia algoritmul generalizeaza numai in cazul in care este fortat de un exemplu pozitiv; un exemplu disjunctiv ofera posibilitatea evitarii generalizarii, astfel incit algoritmul nu este fortat niciodata sa generalizeze. 9.5.3 Sistem de invatare a conceptelor disjunctive Unele concepte nu pot fi descrise decit disjunctiv, de exemplu: unchiul este fie fratele mamei fie fratele tatalui unui copil. Algoritmul descris in continuare, implementat la MIT, invata descrieri de concepte in forma normal disjunctiva. Metoda de reprezentare a cunostintelor este aceea a cadrelor, cu urmatoarea structura: nume_concept: ( descriere in limbaj natural ) parte_pozitiva: cluster: descriere: 13 exemple: cluster: descriere: exemple: ... parte_negativa: exemple: Numele conceptului tinta este dat, iar descrierea este construita pe baza unor exemple pozitive si negative. Toate exemplele sint memorate in structura, deoarece vor fi refolosite pe parcursul algoritmului. Se prezinta in continuare functionarea algoritmului pe un caz concret. Fie setul de exemple: 1. (galben piramida lucios mare +) 2. (bleu sfera lucios mic +) 3. (galben piramida mat mic +) 4. (verde sfera mat mare +) 5. (galben cub lucios mare +) 6. (bleu cub lucios mic -) 7. (bleu piramida lucios mare -) Dupa primul exemplu pozitiv se creaza ipoteza nume_concept: (galben sau sfera) parte_pozitiva: cluster: descriere: (galben, piramida, lucios, mare) exemple: 1 parte_negativa: exemple: Se considera al doilea exemplu. Acesta fiind un exemplu pozitiv, se realizeaza o descriere care combina cele doua exemple pozitive: nume_concept: (galben sau sfera) parte_pozitiva: cluster: descriere: (lucios) exemple: 1, 2 parte_negativa: exemple: Dupa considerarea exemplului 3, descrierea devine nume_concept: (galben sau sfera) parte_pozitiva: cluster: descriere: ( ) exemple: 1, 2, 3 14 parte_negativa: exemple: Urmatoarele doua exemple pozitive nu mai adauga nimic la descriere (se observa o suprageneralizare a algoritmului de invatare) ci doar se completeaza slotul exemple al primului cluster cu exemplele pozitive 4 si 5. Exemplul 6 este un exemplu negativ si este inconsistent cu ipoteza curenta, ipoteza care include orice descriere. In consecinta, elementul de invatare trebuie sa-si revizuiasca ipoteza pentru a exclude acest exemplu negativ din descrierea partii pozitive. Aceasta se realizeaza prin impartirea primului cluster in doua noi clustere care sint fiecare in parte compatibile cu exemplul negativ 6. Fiecare nou cluster corespunde unui termen disjunctiv din descriere. Pentru a construi noi clustere, algoritmul utilizeaza exemplele memorate (prelucrate pina in acest moment) in primul cluster. Aceste exemple sint impartite si combinate in asa fel incit cele doua noi clustere obtinute sa fie compatibile cu exemplul negativ. La reconstruirea clusterelor se incepe prelucrarea exemplelor in ordine inversa a prezentarii lor. Dupa prelucrarea exemplelor 5 si 4 se obtine: nume_concept: (galben sau sfera) parte_pozitiva: cluster: descriere: (mare) exemple: 5, 4 parte_negativa: exemple: Cind se incearca cuprinderea exemplului pozitiv 3, apare o inconsistenta cu exemplul negativ, deci acesta trebuie pus intr-un nou cluster. Acelasi lucru se intimpla daca se incearca adaugarea exemplului pozitiv 2 la primul cluster (descrierea devine ( ) deci inconsistenta cu exemplul negativ), iar daca se adauga exemplul pozitiv 2 la al doilea cluster, descrierea devine (mic), deci inconsistenta cu exemplul negativ. Aceasta forteaza crearea unui nou cluster; in final se considera si exemplul pozitiv 1 si acesta se poate adauga consistent la primul cluster si la al doilea cluster. Dupa reorganizarea clusterelor, structura este: nume_concept: (galben sau sfera) parte_pozitiva: cluster: descriere: (mare) exemple: 5, 4, 1 cluster: descriere: (galben, piramida) exemple: 3, 1 cluster: descriere: (bleu, sfera, lucios, mic) exemple: 2 parte_negativa: exemple: 6 15 La prelucrarea exemplului negativ 7 se observa ca primul cluster este inconsistent cu acesta, deci primul cluster trebuie la rindul lui impartit. Structura rezultata este: nume_concept: (galben sau sfera) parte_pozitiva: cluster: descriere: (galben, lucios, mare) exemple: 5, 1 cluster: descriere: (verde, sfera, mat, mare) exemple: 4 cluster: descriere: (galben, piramida) exemple: 3, 1 cluster: descriere: (bleu, sfera, lucios, mic) exemple: 2 parte_negativa: exemple: 6, 7 Toate noile clustere sint acum consistente cu cele doua exemple negative. Dar clusterele nu sint maximale deoarece exista posibilitatea reunirii unor clustere fara a crea inconsistente cu exemplele negative. Aceasta maximalitate se obtine prin retinerea primului cluster si reunirea sau copierea clusterelor succesive. Reunirea se face numai in cazul in care nu apar inconsistente cu exemplele negative. Structura finala a conceptului este nume_concept: (galben sau sfera) parte_pozitiva: cluster: descriere: (galben) exemple: 5, 3, 1 cluster: descriere: (sfera) exemple: 4, 2 parte_negativa: exemple: 6, 7 Se pot crea clustere si pentru partea negativa. acestea ar permite invatarea unor concepte de tipul "nici galben nici sferic" folosind pentru partea negativa aceeasi structura de clustere si aceeasi metoda ca si pentru partea pozitiva. 9.5.4 Invatarea conceptelor folosind arbori de decizie. Sistemul ID3. Sistemul ID3 a fost dezvoltat de R. Quinlan pentru a invata clasificarea obiectelor din exemple pozitive si negative. Sistemul ID3 s-a bazat pe versiunea initiala a acestui algoritm de invatare, algoritmul CLS a lui E. Hunt. O={o,..,o}Algoritmul porneste de la o multime de obiecte dintr-un univers U in care 1n fiecare obiect este descris de un set de m atribute cu valorile lor. Un atribut A are un numar finit j de valori posibile a,...,a. Se selecteaza un atribut A si se creaza un nod intr-un arbore pentru jj1jk a-l reprezenta; nodul are k succesori, fiecare succesor corespunzind uneia din valorile a. Setul de jji 16 subseturi pe baza valorilor de atribute. Aceeasi obiecte O este apoi partitionat in cel mult kj procedura este apoi repetata recursiv pentru fiecare din aceste subseturi, folosind celelalte m-1 atribute pentru a forma alte noduri in arbore. Procesul se opreste in momentul in care toate obiectele au fost partitionate in clase omogene, i.e. fiecare clasa contine numai exemple pozitive sau numai exemple negative ale aceluiasi concept, care eticheteaza si ultimele noduri (frunze) generate in arbore. Arborele de decizie rezultat poate fi apoi utilizat pentru a clasifica noi obiecte necunoscute pe baza unei descrieri a acestora cu valorile celor m atribute. Algoritmul de invatare poate fi utilizat si pentru invatarea conceptelor disjunctive, fiecare cale in arbore putind reprezenta o disjunctie. In algoritmul prezentat in continuare se considera cazul general al existentei mai multor clase in care se incadreaza exemplele de invatare, C1,..., Cn. Algoritmul intoarce arborele de decizie construit pe baza multimii de exemple de invatare Exemple, fiecare exemplu fiind caracterizat de valori ale multimii de atribute Atribute. Algoritm: Invatare folosind arbori de decizie Constructie(Exemple,Atribute) 1. daca toate exemplele din Exemple sint in aceeasi clasa Ci atunci intoarce un nod frunza etichetat cu clasa Ci 2. daca Atribute=, atunci intoarce un nod frunza etchetat cu disjunctia dintre clasele carora apartin exemplele (Ci1 , Ci2 , ...) 3. Selecteaza un atribut A din Atribute si stabileste A ca radacina a arborelui curent 4. Atribute , Atribute - A 5. pentru fiecare valoare Vj a atributului A executa 5.1 Creaza o ramura succesoare a radacinii etichetata cu Vj 5.2 Fie EXj exemplele din Exemple care au valoarea Vj pentru atributul A 5.3 Ataseaza rezultatul intors de Constructie(EXj, Atribute) ramurii curente 6. Intoare arborele curent astfel obtinut sfirsit. Acest algoritm de baza a fost modificat de Quinlan in urmatorul fel: , un numar relativ mic de exemple este selectat din multimea de exemple , se construieste un arbore de decizie preliminar , arborele este testat cu toate exemplele pentru a vedea daca exista exceptii (neconcordante cu arborele format) , se formeaza un nou set de exemple care contine setul de exemple selectat initial si o parte din exemplele ce sint exceptii (inconsistente) 17 , pe baza acestui nou set se reconstruieste arborele de decizie , procesul se repeta pina cind nu mai exista inconsistente Alta diferenta importanata in ID3 fata de CLS consta in modul in care atributele sint ordonate in procesul de clasificare. Se selecteaza intii atributul care realizeaza o discriminare optima. Se calculeaza o estimare a cistigului de informatie a unui atribut, pe baza tuturor atributelor disponibile, apoi se selecteaza atributul cu merit maxim. Acest atribut este considerat radacina a arborelui de decizie. In continuare atributele se selecteaza in ordine descrescatoare a meritului. Acest algoritm poate fi vazut drept o cautare a conceptului tinta in spatiul de cautare al tuturor conceptelor posibile. Multimea tuturor arborilor de decizie poate defini acest spatiu de cautare. O operatie de avans in cautare in acest spetiu corespunde adaugarii unui test (ramura) arborelui de decizie. ID3 implementeaza o forma de "hill-climbing" in spatiul tuturor arborilor posibili: adauga un subarbore arborelui curent si continua cautarea. Nu face cautare cu reveniri. Acest lucru face ca algoritmul sa fie extrem de eficient; il face de asemenea puternic dependent de criteriul utilizat in selectarea atributelor in vederea testului. Arborele optim (de inaltime minima) se obtine daca atributele sunt selectate in ordine descrescatoare a acastigului informational. Calculul cistigului informational al unui atribut se face in urmatorul mod. Fie , n este numarul de obiecte din U (numarul de exemple) , h reprezinta numarul de obiecte din exemple care apartin lui C; h este o estimare a probabilitatii ca un obiect din U sa apartina lui C , c este numarul de obiecte care apartin lui C si au valoarea a pentru atributul A jkjkj , d este numarul de obiecte care nu apartin lui C si au valoarea a pentru atributul A jkjkj , reprezinta probabilitatea ca un obiect sa aiba valoarea a pentru p=(c+d)/njkjkjkjk p=1atributul A (se presupune ca obiectele au valori pentru toate atributele, deci ) ,jjk j , reprezinta probabilitatea ca obiectele din C sa aiba valoarea a f=c/(c+d)jkjkjkjkjk pentru atributul A j , reprezinta probabilitatea ca obiectele din C sa nu aiba valoarea a pentru g=1f,jkjkjk atributul A j Se defineste: , continutul informational al clasei C H(h)=hlogh(1h)log(1h),,,,,, c22 H(0)=0 c , continutul informational al valorii de atribut a ij H=flogfglogg,,,,jkjk2jkjk2jk 18 , continutul informational al atributului A j , E(H)=H=pH ,jkj medjkjk k , cistigul informational dat de atributul A j G=HH,jcj med Fiecare G este calculat si atributele sint ordonate in functie de aceste valori. Arborele j rezultat prin selectia atributelor in aceasta ordine va fi minimal din punct de vedere al numarului de noduri. Cantitatea calculata ca H=plogp,, cu p=1 ,,i2ii ii reprezinta entropia informationala, unde p este probabilitatea de aparitie a unui eveniment i. H i ofera o masura a dispersiei de aparitie a unui numar de evenimente. Exemplu. Fie urmatorul set de exemple Nr.DimensiuneFormaCuloareClasificare 1miccercrosu， 2marecercrosu， 3mictriunghigalben, 4miccercgalben, 5maretriunghirosu, 6marecercgalben, Cazul (a). Selectarea atributelor se face in ordinea Forma, Culoare, Dimensiune. Se aplica algoritmul pe multimea initiala E Forma cerctriunghi C1=(1+,2+,4-,6-)C2=(3-,5-) Se aplica algoritmul pentru atributele Culoare, Dimensiune pe submultimea C1. Forma cerctriunghi C2=(3-,5-)rosu galben C11=(1+,2+)C12=(4-,6-) Se aplica algoritmul pentru C11; cum toate exemplele din C11 sint exemplele pozitive, nodul se eticheteaza cu + (sau DA). Se aplica algoritmul pentru C12; cum toate exemplele din 19 C12 sint exemplele negative, nodul se eticheteaza cu - (sau NU); la fel pentru C2. Arborele rezultat va avea 5 noduri si va fi: Forma cerctriunghi Culoare NU rosugalben DANU Cazul (b). Se selecteaza atributele in ordinea Dimensiune, Forma, Culoare. Constructia arborelui va parcurge urmatoarele etape: Dimensiune maremic C1=(2+,5-,6-)C2=(1+,3-,4-) (2) Dimensiune maremic C2=(1+,3-,4-)cerctriunghi C11=(2+,6-)C12=(5-) (3) Dimensiune maremic C2=(1+,3-,4-)cerctriunghi C12=(5-)rosu galben C111=(2+)C112=(6-) (4) 20 Dimensiune maremic cerctriunghicerctriunghi C12=(5-)C21=(1+,4-)C22=(3-)rosu galben C111=(2+)C112=(6-) (5) Dimensiune maremic cerctriunghicerctriunghi C12=(5-)C22=(3-)rosurosu galbengalben C111=(2+)C112=(6-)C211=(1+)C212=(4-) Arborele rezultat pentru aceasta ordine de alegere a atributelor are 11 noduri. Dimensiune maremic FormaForma cerccerc triunghitriunghi CuloareCuloareNUNU rosugalbenrosugalben DADANUNU Calculul cistigului informational n=6h=2 H=2log24log4,,,, c22 a=mica=marecu valorile Atributul A si 11121 c=1d=2p=3/6f=1/(1+2)g=1f, 111111111111H(mic)=0.333log0.3330.666log0.666,,,, 1122 21 Atribut/kcdpfglogfHHGjkjk jk jkjk2jkjk jjvaloare k=1 (mic)123/60.3330.667A (Dimensiune)1k=2 (mare)123/60.3330.667 k=1 (cerc)2246/05..05A (Forma)2k=2 (triunghi)0226/01 k=1 (rosu)2136/0667..0333A (Culoare)3k=2 (galben)0336/01 22