Inteligenta Artificiala

download Inteligenta Artificiala

of 55

  • date post

    14-Jan-2016
  • Category

    Documents

  • view

    39
  • download

    1

Embed Size (px)

description

Inteligenta Artificiala. Universitatea Politehnica Bucuresti Anul universitar 2010-2011 Adina Magda Florea http://turing.cs.pub.ro/ia_10 si curs.cs.pub.ro. Curs nr. 11. Invatare automata Tipuri de invatare Invatarea prin arbori de decizie Invatarea conceptelor disjunctive din exemple - PowerPoint PPT Presentation

Transcript of Inteligenta Artificiala

  • Inteligenta ArtificialaUniversitatea Politehnica Bucuresti Anul universitar 2010-2011

    Adina Magda Floreahttp://turing.cs.pub.ro/ia_10 si curs.cs.pub.ro

  • Curs nr. 11Invatare automataTipuri de invatareInvatarea prin arbori de decizieInvatarea conceptelor disjunctive din exempleInvatarea prin cautare in spatiul versiunilor

    *

  • 1. Tipuri de invatareUna dintre caracteristicile esentiale ale inteligentei umane este capacitatea de a nvtanvatarea automat este domeniul cel mai provocator al inteligentei artificiale si, n acelasi timp, cel mai rezistent ncercrilor de automatizare complet*

  • Reguli de inferenta utilizate in invatareLa baza procesului de nvtare stau o serie de forme inferentiale nevalide: inductia, abductia si analogiaO metod de nvtare poate folosi una sau mai multe astfel de forme de inferent, cat si forme de inferent valide, cum este deductia*

  • Inferenta inductivaO proprietate adevrat pentru o submultime de obiecte dintr-o clas este adevrat pentru toate obiectele din acea clas

    *

  • Inferenta inductivaSe poate generaliza la sintetizarea unei ntregi reguli de deductie pe baza exemplelor*

  • Inferenta abductivaSe utilizeaza cunostinte cauzale pentru a explica sau a justifica o concluzie, posibil invalid*

  • Inferenta abductivaExemplul 1Ud(iarba)(x) (PlouaPeste(x) Ud(x))Se poate infera abductiv c a plouatCu toate acestea, abductia nu poate fi aplicat consistent n oricare caz*

  • Inferenta analogicaSituatii sau entitti care tind s fie asemntoare sub anumite aspecte sunt asemntoare n generalEste o combinatie a celorlalte forme de inferent: abductive, deductive si inductive*

    _1146385778.unknown

  • Modelul conceptual al unui sistem de invatare automata*Invatare mono-agentProcesInvatare Rezolvare probleme Cunostinte Inferente Strategii Evaluare performanteRezultate invatareRezultate MediuFeed-backFeed-backDate

  • Modelul conceptual al unui sistem de invatare automatan functie de diferenta ntre nivelul informatiei oferite de mediu si cel al informatiei din baza de cunostinte, se pot identifica patru tipuri de nvtareinvatarea prin memorareinvatarea prin instruireinvatarea prin inductie (din exemple)invatarea prin analogie*

  • 2. Arbori de decizie. Algoritmul ID3Invatare inductivaAlgoritmul ID3 nvat inductiv concepte din exempleConceptele se reprezint ca un arbore de decizie, ceea ce permite clasificarea unui obiect prin teste asupra valorii anumitor proprietti (atribute) ale sale Arbore de decizie - arbore care contine n noduri cte un test pentru o anumit proprietate, fiecare arc fiind etichetat cu o valoare a propriettii testate n nodul din care pleac arcul respectiv, iar n fiecare frunz o clas*

  • Prezentarea algoritmului ID3Algoritmul ID3 urmeaz principiul conform cruia explicatia cea mai simpl (arborele de decizie cel mai simplu) este si cea adevrat Ockhams razorOrdinea testelor este important, punndu-se accent pe criteriul alegerii testului din rdcina arborelui de decizie

    *

  • Construirea arborelui de decizieMai intai, se construieste arborele de decizie Dupa aceea, se foloseste arborele de decizie pentru a clasifica exemple necunoscuteExemplele necunoscute pot fi clasificate astfel:apartin unei clase (YES sau Ci)nu apartin unei clase (NO)*

  • Exemplu simplu de clasificare*

    No.

    Forma

    Culoare

    Dim

    Clasa

    1

    cerc

    rosu

    mic

    +

    2

    cerc

    rosu

    mare

    +

    3

    triunghi

    galben

    mic

    -

    4

    cerc

    galben

    mic

    -

    5

    triunghi

    rosu

    mare

    -

    6

    cerc

    galben

    mare

    -

  • Problema acordarii unui creditProblema estimrii riscului acordrii unui credit unei anumite persoane, bazat pe anumite proprietti: comportamentul anterior al persoanei atunci cnd i-au fost acordate credite (istoria creditului), datoria curent, garantii si venit*

  • No.Risk (Classification)Credit HistoryDebtCollateralIncome

    1HighBadHighNone$0 to $15k2HighUnknownHighNone$15 to $35k3ModerateUnknownLowNone$15 to $35k4HighUnknownLowNone$0k to $15k5LowUnknownLowNoneOver $35k6LowUnknownLowAdequateOver $35k7HighBadLowNone$0 to $15k8ModerateBadLowAdequateOver $35k9LowGoodLowNoneOver $35k10LowGoodHighAdequateOver $35k11HighGoodHighNone$0 to $15k12ModerateGoodHighNone$15 to $35k13LowGoodHighNoneOver $35k14HighBadHighNone$15 to $35k

    *

  • *

    Given a set of training

    Good

    Bad

    Unknown

    $Over 35K

    $15K-$35K

    $0K-$15K

    Good

    Unknown

    Bad

    High

    Low

    High risk

    Credit history?

    Credit history?

    Moderate risk

    High risk

    Debt?

    High risk

    Moderate risk

    Low risk

    Low risk

    Moderate risk

    Income?

  • Algoritm pentru construirea arborelui de decizie

    functie ind-arbore (set-exemple, atribute, default) 1. daca set-exemple = vid atunci intoarce frunza etichetata cu default 2. dac toate exemplele din set-exemple sunt n aceeasi clas atunci ntoarce o frunz etichetat cu acea clas 3. dac atribute este vid atunci ntoarce o frunz etichetat cu disjunctia tuturor claselor din set-exemple

    *

  • 4.- selecteaz un atribut A, creaza nod pt A si eticheteaza nodul cu A- sterge A din atribute > atribute1- m = majoritate (set-exemple)-pentru fiecare valoare V a lui A repeta - fie partitieV multimea exemplelor dinset-exemple, cu valorea V pentru A- creaza nodV = ind-arbore (partitieV, atribute1,m)- creeaz legatura nod A - nodVetichetat cu V sfarsit*

  • ObservatiiSe pot construi mai multi arbori de decizie, ponind de la multimea data de exempleAdancimea arborelui de decizie necesar pentru a clasifica o multime de exemple variaza in functie de ordinea in care atributele sunt testatePentru problema acordarii unui credit, se obtine arborele de decizie cu adancimea cea mai mica in cazul cand in radacina se testeaza atributul incomeAlgoritmul ID3 alege cel mai simplu arbore de decizie care acopera toate exemplele din multimea initiala *

  • Selectarea atributelor pentru construirea arborelui de decizieConsideram fiecare atribut al unui exemplu ca avnd o anumit contributie de informatie la clasificarea respectivului exempluEuristica algoritmului ID3 msoar cstigul informational pe care l aduce fiecare atribut si alege ca test acel atribut care maximizeaz acest cstig*

  • Notiuni despre teoria informatieiTeoria informatiei furnizeaz fundamentul matematic pentru msurarea continutului de informatie dintr-un mesajUn mesaj este privit ca o instant dintr-un univers al tuturor mesajelor posibileTransmiterea mesajului este echivalent cu selectia unui anumit mesaj din acest univers*

  • Notiuni despre teoria informatieiContinutul informational al unui mesaj depinde de mrimea universului si de frecventa fiecrui mesajContinutul informational al unui mesaj se defineste ca fiind probabilitatea de aparitie a oricrui mesaj posibil

    *

  • Notiuni despre teoria informatieiAvnd un univers de mesaje M = {m1, m2, ..., mn } si o probabilitate p(mi) de aparitie a fiecrui mesaj, continutul informational al unui mesaj din M se defineste astfel:*

    _957505600.unknown

    log2(p(mi))

  • Notiuni despre teoria informatieiInformatia dintr-un mesaj se msoar in bitiAlgoritmul ID3 foloseste teoria informatiei pentru a selecta atributul care ofera cel mai mare cstig informational n clasificarea exemplelor de nvtareConsideram un arbore de decizie ca avnd informatie despre clasificarea exemplelor din multimea de nvtareContinutul informational al arborelui este calculat cu ajutorul probabilittilor diferitelor clasificri*

  • Continutul de informatie I(T)p(risk is high) = 6/14p(risk is moderate) = 3/14p(risk is low) = 5/14

    Continutul de informatie al arborelui de decizie este:

    I(Arb) = 6/14log(6/14)+3/14log(3/14)+5/14log(5/14)*

    _1209447839.unknown

  • Castigul informational G(A)Pentru un anumit atribut A, cstigul informational produs de selectarea acestuia ca rdcin a arborelui de decizie este egal cu continutul total de infomatie din arbore minus continutul de informatie necesar pentru a termina clasificarea (construirea arborelui), dupa selectarea atributului A ca radacina G(A) = I(Arb) - E(A)*

  • Cum calculam E(A)Cantitatea de informatie necesar pentru a termina constructia arborelui este media ponderat a continutului de informatie din toti subarboriiPresupunem c avem o multime de exemple de nvtare CDac punem atributul A cu n valori n rdcina arborelui de decizie, acesta va determina partitionarea multimii C n submultimile {C1, C2, ..., Cn}

    *

  • Cum calculam E(A)Estimarea cantittii de informatie necesar pentru a construi arborele de decizie, dup ce atributul A a fost ales ca rdcin, este:*

    _1146475699.unknown

  • Problema acordarii unui creditDaca atributul Income este ales ca radacina a arborelui de decizie, aceasta determina impartirea multimii de exemple in submultimile:C1 = {1, 4, 7, 11}C2 = {2, 3, 12, 14}C3 = {5, 6, 8, 9, 10, 13}G(income) = I(Arb) - E(Income) =1,531 - 0,564 = 0,967 bitsG(credit history) = 0,266 bitsG(debt) = 0,581 bitsG(collateral) = 0,756 bits*

  • Performanta invatariiFie S mult de exImparte S in set de invatare si set de testAplica ID3 la set de invatareMasoare proc ex clasificate corect din set de testRepeta pasii de mai sus pt diferite dimensiuni ale set invatare si set test, alese aleatorRezulta o predictie a performantei invatariiGrafic X- dim set invatare, Y- procent set testHappy graphs

    *

  • ObservatiiDate lipsaAtribute cu valor