SUBIECTE TIA

1. Motorul de inferene al unui sistem expert: definiie, mod de funcionare i ciclul de baz.

DEFINITIE: Motorul de inferen (MI) este un program general care implementeaz mecanismul prin care se construiesc raionamentele.MOD DE FUNCTIONARE: Exist diverse procedee sau mecanisme de inferen care traverseazacest arbore n sensuri diferite, conceptul de CUTARE fiind unul esenial n programele de IA. Cele mai cunoscute metode de inferen sunt: inducia sau nlnuirea nainte - este un proces de inferen condus de date; inducia sau nlnuirea npoi - este un proces de inferen condus de scop inducia sau nlnuirea hibrid - este un proces de inferen care combin inducia nainte i inducia napoi.CICLUL DE BAZA: MI este inima unui SE pentru c, folosind baza de cunotine, construiete dinamic raionamentele alegnd regulile ce urmeaz a fi declanate/aplicate i ordinea de nlnuire a acestora.Indiferent de modul de raionament utilizat, ciclul de baz al unui motor de inferene comport urmtoarele patru etape:

SELECIA: n aceast etap se extrag din baza de reguli i din baza de fapte elementele care caracterizeaz subdomeniul de rezolvare a problemei. Aceast etap este necesar atunci cnd baza de cunotine este mare, ncercnd s acopere mai multe domenii ale cunoaterii. FILTRAJUL (pattern matching) const n compararea premiselor regulilor selecionate anterior cu faptele ce caracterizeaz problema de rezolvat, pentru a determina submulimea regulilor declanabile.n urma acestei etape pot rezulta una, mai multe sau nicio regul declanabil. Dac nu rezult nicio regul aplicabil, atunci suntem ntr-o stare de eec pe care SE o semnaleaz, iar utilizatorul trebuie srspund la o serie de ntrebri n scopul completrii datelor. REZOLVAREA CONFLICTELOR este necesar atunci cnd din etapa de filtraj au rezultat mai multe reguli declanabile i trebuie aleas una pentru a fi executat. Dintre criteriile utilizabile n aceast etap se amintesc: prima regul din list; regula cu cel mai mare numr de fapte n premis; regula cea mai des utilizat. De aceast alegere depind performanele MI. Totui este dificil de indicat unul sau altul dintre criterii, deoarece aceast alegere depinde de contextul n care se gsete baza de cunotine n momentul respectiv. EXECUIA REGULI SELECTATE const n adugarea uneia sau mai multor fapte n baza de fapte ca o consecin a aplicrii regulii respective. Este posibil, de asemenea, ca n aceast etap s se fac apel la proceduri externe (acces la baze de date sau la procesoare de tabele) sau la ntrebri puse utilizatorului.

2. Structura unei reele neuronale artificiale cu un strat ascuns. Regula delta generalizat: modificarea ponderilor neuronilor de pe stratul de ieire.

RNA cu un singur strat. n acest caz stratul unic joac rol dublu intrare-ieire. Totodat, absena altor straturi impune ca aceste RNA s aib o topologie buclat. n aceast categorie se nscriu reelele Hopfield, precum i variante ale acestora, care se deosebesc n funcie de modul de conectare a neuronilor. Reele cu un singur strat sunt folosite pentru completarea modelelor, filtrarea unor semnale sau rezolvarea unor probleme de optimizare;Regula delta generalizat Perceptronii multistrat cu mai multe ieiri i funcii de transfer sigmoidale sau liniare se mai numesc i reele backpropagation.Denumirea provine de la algoritmul de nvare utilizat de aceste structuri i anume algoritmul backpropagation BP sau algoritmul de propagare napoi a erorii, respectiv algoritmul retropropagrii introdus de Rumelhart i membrii grupului Parallel Distributed Processing PDP n 1986. El este primul algoritm propus pentru antrenarea unei configuraii de tip MLP i a fost considerat un mare succes care a contribuit la relansarea calculului neuronal n IA.Algoritmul BP urmrete minimizarea funciei de performan (eroarea ptratic parial sau total) printr-o metod de gradient. Din acest motiv funciile de activare sau transfer ale neuronilor trebuie s fie continue i derivabile pe tot domeniul de definiie, cerine satisfcute de funciile sigmoidale i funcia liniar.La fel ca i n cazul perceptronilor, generarea unei reele MLP cuprinde dou etape: etapa de nvare n care, pe baza mulimii de antrenare, se sintetizeaz ponderile i valorile pragurilor de activare ale neuronilor; etapa de testare, n care reeaua este utilizat pentru a clasifica mulimi de forme necunoscute, dar similare celor din mulimea de antrenare.Corecia ponderilor neuronilor de pe stratul de ieiren metoda gradientului descendent, respectiv n algoritmul BP, procesul de cutare a punctului de minim al funciei de performan a reelei MLP const n deplasarea dup direcia antigradientului peo lungime proporional cu rata de nvare a crei valoare este selectat n mod arbitrar de ctre utilizator.Adaptarea metodei Newton la antrenarea reelelor MLP conducela urmtoarele relaii de recuren pentru modificarea ponderilor:

4. Neuronul clasificator (perceptronul): structura, ecuaiile de evoluie i regulile de modificare a ponderilor

Pornind de la modelul MCP, psihologul Rosenblatt a introdus, n anul 1958, noiunea de perceptron sau neuron clasificator.Perceptronul este asemntor neuronului MCP (fig. 2.5) i a fost dezvoltat din dorina de a modela funcia de percepie vizual a retinei.

Ecuaiile de funcionare ale perceptronului sunt ecuaiile modelului MCP. Deosebirea provine din faptul c de aceast data intrrile sunt valori reale i nu valori binare de tipul 1 sau 0, funcia de activare fiind tot de tipul treapt.Prin urmare evoluia perceptronului este descris de: Problema care se pune const n gsirea unui algoritm de nvare care s determine vectorul ponderilor W astfel nct frontiera s ajung s separe corect elementele. Cu alte cuvinte, ieirea neuronului s fie y =1 sau y =0, dup cum intrarea aparine clasei A sau clasei B.Rspunsul la aceast problem a fost dat, ntr-o prim etap, de ctre Rosenblatt. Algoritmul propus de acesta, cunoscut sub denumirea de algoritmul standard de antrenare a perceptronuli, modific valorile ponderilor ori de cte ori la intrarea reelei este prezentat o configuraie (form sau pattern) incorect clasificat.

5. Cutri neinformate n spaiul strilor: caracterizare i algoritmul cutrii pe nivel.

Se consider: un graf definit implicit prin mulimea operatorilor asociai arcelor; nodul sau mulimea de noduri ce definesc starea iniial Si , adic condiiile iniiale ale problemei de rezolvat; nodul sau mulimea de noduri ce definesc starea final S f , adic obiectivele sau cerinele problemei.Pentru rezolvarea este necesar s se gseasc o cale ntre starea initial i starea final. Principiul care se afl la baza algoritmului generic de cutare const n explorarea incremental a cilor ce pornesc din nodurile aferente strii iniiale i folosete noiunea de frontier pentru a delimita nodurile explorate de cele care nu au fost nc explorate.n parcurgerea spaiului de cutare un nod poate fi: necunoscut - nodul aparine prii neexplorate a spaiului de cutare, evaluat - nodul este cunoscut dar fie nu se cunoate nici un succesor al lui, fie se cunosc numai o parte dintre acetia; expandat - nodul este cunoscut si, in plus, se cunosc toi succesorii luin procesul de cutare se vor folosi doua liste: LF lista frontier care conine nodurile evaluate; LT lista teritoriu care conine nodurilor expandate.Deci LF reprezint frontiera spaiului de cutare parcurs (explicitat) spre partea necunoscut a acestuia, iar LT partea cunoscut a spaiului de cutare.Cutarea pe nivel, numit i cutarea n lime, este o strategie care expandeaz strile urmtoare n ordinea apropierii fa de nodul stare iniial Si. Aceast strategie trateaz lista frontier LF folosind o strategie de tipul FIFO. Nodul din frontier care se elimin este primul din list, iar succesorii si sunt adugai la sfritul listei.Algoritm: Strategia cutrii pe nivel in spaiul strilor1. Creeaz listele LF{Si} si LT{ }2. DAC LF={ }ATUNCI ntoarce INSUCCES /* nu exist soluie */3. Elimin primul nod Sc din LF si-l insereaz n LT4. Expandeaz nodul Sc4.1 Genereaz toi succesorii direci S j ai nodului Sc 4.2 pentru fiecare succesor Sj (1 j m) al lui Sc executa4.2.1 Stabilete legtura Sj S4.2.2 daca Sj este stare finalatuncii) Soluia este (Sj,S,...,Si )ii) ntoarce SUCCES /* s-a gsit soluie */4.2.3 Insereaza S j in LF, la sfrit5. repeta de la 2sfrit.7. Clasificarea strategiilor de cutare dup cantitatea de informaie. Costul computaional.

capacitatea mecanismului de rezolvare de a reveni ntr-o stare intermediar anterioar; dup cantitatea de informaie folosit la gsirea soluiei.n funcie de cel de-al doilea criteriu, strategiile de cutare se mpart n: Strategii de cutare neinformate.Considerarea strilor urmtoare de inspectat se face dup o ordine arbitrar, anterior stabilit. Strategiile de cutare neinformat inspecteaz sistematic toate strile spaiului de cutare pn n momentul gsirii strii finale. Cele mai importante strategii de acest fel sunt cutarea pe nivel sau cutarea n lime si cutarea in adncime. Strategii de cutare informate.Considerarea strilor urmtoare de inspectat se face dup criteria euristice. Strategia folosete o funcie de evaluare a situaiei globale sau locale care indic starea urmtoare cea mai promitoare din punct de vedere al avansului spre soluie.Costul computaional total al unui program de rezolvare a problemelor de IA depinde de locul unde se situeaz strategia de control n spectrul neinformat/informat i are dou componente: costul aplicrii operatorilor, sau costul parcurgerii spaiului de cutare ntre starea iniial si starea final; costul controlului, sau costul evalurii si seleciei celei mai promitoare stri urmtoare.

9. Cutri neinformate n spaiul strilor: caracterizare i algoritmul cutrii n adncime.

Algoritmul cutrii n adncimeCutarea n adncime este strategia cea mai frecvent utilizat n aplicaiile practice. Ea expandeaz strile cel mai recent generate, adic nodurile din lista LF cu adncimea cea mai mare. Prin urmare, aceast strategie parcurge o cale de la starea iniial pn la o stare ce poate fi starea final sau care nu mai are nici un succesor. n acest ultim caz se aplic mecanismul backtracking revenindu-se pe nivelurile anterioare i se ncearc explorarea altor ci posibile. n cadrul acestei strategii lista frontier LF este tratat ca o stiv folosind o tehnic de tipul LIFO (Last In First Out).Strategia cutrii n adncime nu garanteaz obinerea unei soluii a problemei, chiar n cazul n care aceasta exist.Algoritm: Strategia cutrii in adncime n spaiul strilor1. Creeaz listele LF {Si} si LT { }2. DAC LF={ }ATUNCI ntoarce INSUCCES /* nu exist soluie sau soluia nu poate fi gsit pn la nivelul AdMax */3. Elimin primul nod Sc din LF si-l insereaz n LT3'. DAC Ad(Sc ) = AdMaxATUNCI repet de la 24. Expandeaz nodul Sc4.1 Genereaz toi succesorii direci S j ai nodului Sc4.2 Pentru fiecare succesor S j (1 j m) al lui Sc execut4.2.1 Stabilete legtura S j Sc4.2.2 DAC S j este stare finalATUNCIi) Soluia este (S j , Sc ,..., Si )ii) ntoarce SUCCES /* s-a gsit soluie */4.2.3 Insereaz S j n LF, la nceput5. repet de la 2 sfrit.

13. Structura general a unei proceduri de calcul evolutiv.

Tehnicile de calcul evolutiv TCE , numite i inteligen computaional IC sau calcul uor - CU , sunt metode stocastice de cutare multi-dimensional care simuleaz evoluia biologic. n conformitate cu legile evoluiei naturale, ele modeleaz adaptarea unei populaii de indivizi, fiecare individ n parte reprezentnd o soluie posibil a problemei de rezolvat, n sensul creterii performanelor n raport cu funcia obiectiv.Interesul pentru aceste tehnici a crescut foarte repede, deoarece ele ofer un mecanism foarte robust de cutare a soluiei optime. Cele mai cunoscute tehnici de calcul evolutiv sunt: algoritmii genetici AG; strategiile evolutive SE; programarea evolutiv PE; programarea genetic PG; sistemele de clasificare SE.P1. Iniializeaz t = 0 ;P2 Genereaz populaia iniial P(t) P(0)P3 Evaluaeaz P(t) ;P4 Repet atta timp ct (not COND_OPRIRE)Stabilete t t +1;Selecia : selecteaz populaia intermediar P1(t) din populaia anterioar P(t 1) Recombinarea: aplic procesul de recombinarea asupra lui P1(t) i rezult o nou populaie intermediar P2 (t) ;Mutaia: aplic procesul de mutaie asupra lui P2 (t) i rezult noua populaie P(t) ;Evaluare: evalueaz P(t) ;Sfrit ciclu iterativ.

15. Algoritme genetice: operatorul de selecie.

Algoritmii genetici (AG) sunt procedee de cutare i optimizare bazate pe mecanismele geneticii i seleciei naturale. Ei combin supravieuirea artificial a celui mai bun individ cu operatorii genetici care sunt abstractizri ale celor din natur, n scopul formrii unui mecanism robust, aplicabil unei largi game de probleme.Selecia este cel mai important operator al algoritmilor genetici i are rol hotrtor n dirijarea procesului de cutare din spatial soluiilor. Scopul operatorului de selecie este de a asigura mai multe anse de reproducere celor mai performani indivizi din cadrul unei populaii date. Prin urmare, pentru a implementa acest operator este necesar definirea unei msuri a performanei indivizilor, adic definirea unei funcii de evaluarea a performanei sau adecvrii fiecrui individ, numit n continuare funcie de performan. Dac, pentru o problem i o codificare date, este mulimea tuturor indivizilor/cromozomilor posibili, atunci funcia de performan este o funcie f : R care satisface cerinele: f trebuie s fie pozitiv, adic f (X) 0 X f trebuie s reflecte calitatea cromozomilor n sensul optimizrii funciei obiectiv.Prin urmare, performana unui individ Xi al populaiei curenteP(t) = {X1,...Xi ,..., Xn}este:Pi = f (Xi )Deoarece prin selecie se urmrete maximizarea performanei indivizilor, cutarea se concentreaz n regiunile spaiului soluiilor ce corespund adecvrii maxime, realizndu-se astfel exploatarea celor mai bune soluii.