INFO283 Kunstig Intelligens k.7 og 10

  1. nye Komponenter i læring
    • gjøremål (to-do/task) - framferd agenten skal gjøre bedre
    • data - kan bruke erfaringer til å lære yte(perform) bedre
    • mål for forbedring - nye ferdigheter, bedre posisjon i prediksjon, raskere avgjerder (decisions)
    • induksjon - prosess som gir en kompakt representasjon av kunnskap lært fra eksempeldata. (utfordring: balansere effektiv representasjon og god presisjon)
  2. rettledet (supervised) maskinlæring innebærer
    å bruke data-instanser med attributt og klassifiseringer til å lære en funksjon som klassifiserer nye instanser

    • treningseksempler har en klassifisering
    • klassifikator-læring, regresjons-læring: input features og target features
    • test eksempler: kun input features

    forutsi target features for test examples
  3. læring ved forsterking
    agent får belønning og straff
  4. Ikke rettledet læring
    oppdage mønster og kategorier i data
  5. Hva er et beslutningstre? (decision tree)
    • effektive strukturer som er lett å forstå
    • for at et system skal kunne lære, bruker det beslutningstreet for å tolke informasjonen ved å utføre tester på hvert trinn og opprette nye grenser på treet for å komme frem til et resultat.

    tar i mot objekter/situasjonser som beskrives av et sett av egenskaper/attributer og skal si noe om hvordan tilstanden er (vær - att: sol, regn, overskyet). returnerer en handling
  6. Hva representerer nodene og kantene i beslutningstreet?
    • internal (ikke-blad) node = verdi/egenskap/attribut (f.eks boolean, sol)
    • beslutningsnoder - rektangler
    • blad noder - triangel
  7. Skriv en rekursiv algoritme for konstruksjon av et beslutningstre der kriteriet for valg av variabel å splitte på er uspesifisert
    • procedure DecisionTreeLearner(X,Y,E)
    • inputs
    • X: set of input features
    • Y: target feature
    • E: set of training examples
    • output
    • decision tree
    • if stopping criterion is true then
    • return pointEstimate(Y,E)
    • else
    • select feature Xi E X, domain {v1,v2}
    • let E1 = {e E E: val(e,Xi) = v1}
    • let T1 = DecisionTreeLearner({Xi},Y,E1)
    • let E2 = {e E E: val(e,Xi = v2}
    • let T2 = DecisionTreeLearner({Xi},Y,E2}
    • return <Xi = v1, T1, T2>
  8. forklar hva som menes med at man i læringsalgoritmen for beslutningstre velger den noden å splitte på som gir mest informasjonsvinst (information gain)
    • kriterier i algoritmen:
    • Hvis stopping kriterium/kjennetegn er ikke sant, lærer plukker ut et vilkår (beslutningsnode, rektangler) å splitte på. 
    • velg basert på hvor godt en lokal splitt deler opp data
    • mål på hvor gode en oppdeling er: kvadratsum-feil, informasjons-vinst

    • Informasjonsvinst - myopically optimal split is the one that gives max info gain. decrease in entropy.
    • ........
    • Man finner den attributten som gir klarest forskjell mellom valgene og det man vil fram til.

    La oss si at man har et datasett med 4 attributter:

    • W X Y Z
    • w1 x1 y1 z1
    • w2 x2 y2 z2
    • w1 x2 y1 z2
    • wn xn yn zn



    Det kommer nye data inn, men disse mangler verdi for attributten Z. Da velger man den attributten som gir klare skiller på om z1 eller z2 ble valgt, en såkalt unær gren. Om det ikke er mulig å få et klart svar, velg heller fra sannsynlighetsfordeling. I vårt eksempel ser vi at når x2 er tilfellet er Z alltid z2. Ved å velge å splitte på X vil vi få mest informasjon om Z.
  9. lineær regresjon
    numeriske input, lineær likning(comparison) beslutter/bestemmer prediksjon
  10. avgjer
    beslutning
  11. optimering
    • gradient-nedstigning: grådig-søk, følg bratteste(steep) nedstigning
    • endre hver vekt
  12. inkrementell gradient-nedstiging
    • juster W etter hvert eksempel istedenfor å summere opp feil
    • gjentas mange ganger over eksempelsettet til stoppkriterium
    • raskere og mer presis enn å regne ut summer av feil for alle eksempel om gangen
  13. hypotese
    • mulig sammenheng mellom data og fenomen
    • funksjon som tar eksempeldata og gir en klassifisering, læring er å finne en best mulig hypotese, må være effektiv
  14. feil - prediction error
    • E = set of examples
    • absolutt feil- on E is the sum of the absolute differences btw the actual and predicted values on each example. is minimized by median

    kvadratsum-feil- same as absolute, but squared, treats large errors as much worse than small errors. minimized by mean

    verste-tilfelle-feil- maximum absolute difference. minimized by (max+min)/2
  15. lineær regresjon for klassifikasjon
    • target features are discrete.
    • domain of the target variable is {0,1}
  16. overfitting / tilpassinger
    • variable med flere mulige verdier
    • dele domene i 2 deler: reelle tall, ordne mengder
    • overtilpassing (pga for få data, kanskje med feil)
    • treningssettet viser sammenhenger som ikke er reelle, la være å splitte når det ikke er nyttig (lite informasjonsvinst) men velg heller en sannsynsfordeling
    • kjør fullstendig algoritme: nedskjæring, vurder forbedring i hver gren i forhold til å velge en sannsynsfordeling, mer vanlig enn den over
  17. multiagent-system
    • flere agenter som kan handle selvstendig(autonomt), har egen informasjon om verden og andre agenter
    • mekanismer som spesifiserer utfall av agentenes handlinger
    • nytte(utiliy) for hver utfall for hver agent

    naturen: kan ses på som agent uten strategi, handler stokastisk (tilfeldig)
  18. multiagent-system strategi
    • hvordan handler du i en bestemt situasjon
    • velg av handlinger basert på mål/nytte
    • kooperative agenter: agenter som har lik nyttefunksjon, har samarbeidende strategi
    • konkurrerende agenter: agenter som har motsett nyttefunksjon, har strategier som prøver å balansere mulighet for vinst (gain) mot det å hindre motstander, null-sum-spill
  19. null-sum-spill med perfekt informasjon
    • sjakk, go
    • etter du har brukt en strategi i spillet, så vet man hva skal skje, vet intensjon
  20. null-sum-spill med delvis
    • med delvis observerbare og/eller stokastisk forutsigbare omgivelser (random predictable environment)
    • -- mye info/forståing: poker, backgammon
    • -- lite informasjon og forståing: robotfotball

    terningskast - vet hva det betyr, men vet ikke hva du skal få
  21. spillteori
    • strategisk spill
    • endelig mengde agenter 1,2,...,n
    • bestemt mengde med handlinger
    • utfall: faktisk nytte for hver agent over en handlingsprofil
    • nyttefunksjon Ui: gir forventet berdi for en handlingsprofil for agent i
    • alle agenter vil maksimere egen nytte

    • handlingsprofil -> utført
    • (A1,...,An) -> (U1,...Un)
  22. spilltre
    • endelig tre
    • noder er tilstander
    • kanter representerer handlinger

    • hver node er merket med en agent/naturen, agenten kontrollerer noden
    • kant fra node for agent i er en handling for agent i
    • naturen har en sanssynsfordeling for sine barn
    • blader representer endelige utfall og er merket med nytte for hver agent

    • strategi for agent: funksjon fra hver node som agenten kontrollerer til handlinger
    • strategiprofil: representerer strategien til alle agentene
  23. utfall fra spilltre
    • nytte for hver agent - blad
    • nytten for agent j ved en node kontrollert av agent i er nytten ved det bladet som er resultatet av agent i sin strategi
    • nytten ved en natur-node n er forventet verdi for agent i blant n sine barn
  24. utfall fra delespill
    andy og barbara skal dele 2 kroner
    andy-> keep -> barb -> yes(2,0) no(0,0)
    andy -> share -> barb yes(1,1) no(0,0)
    andy -> give -> barb -> yes(0,2) no (0,0)

    strategi?
    • andy fordeler: (2,0), (1,1), (0,2)
    • andy sin strategi er keep
    • barbara sin strategi er (no, yes, yes)
  25. delvis observerbare spill
    • spiller vet ikke tilstand til spill: stein, saks, papir
    • agenten kan være i flere noder med samme mulige valg, men vet ikke hva for en node - informasjonssett
    • strategi må utformes for hvert informasjonssett - slik at den er uavhengig av noder i settet
  26. minimax
    • nullsum-spill med to spillere og perfekt informasjon
    • bruker baklengs induksjon for hvert valg i spillet: gå til bladnoder, finn nytte for hver agent, gå ett nivå opp, genta for alle noder opp til rooten
    • hver spiller har valg etter tur frem til spillet er ferdig

    MAX: alltid velge vei som gir maks score, MIN: minimal score

    eks. tripp trapp tresko - rekursivalgoritme
  27. effektivisering av søk
    minimax som dybde-først, med maksimering og minimering på annen hvert nivå
  28. alphabeta
    • bruke info fra tidligere verdier til å trimme søketreet (spilltre)
    • derom en har funnet en foreløpig høyest verdi (a) på MAX-nivånode n, ikke vits å søke videre på MIN-noder under n som garantert gir lavere verdi enn a
    • a -> så dårlig kan spillet bli for max

    • ""lavest verdi B på en MIN-nivånode n, ingen vits å søke MAX under n som garantert gir høyere verdi enn B
    • b -> så bra
  29. alphabeta algoritmen
    • procedure MinimaxAlphaBeta(N,a,b)
    • inputs
    • N: node in game tree
    • a,b: real numbers
    • output
    • value for node N
    • if (N is leaf node) then
    • return value of N
    • else if (N is a MAX node) then
    • for each child C og N do
    •    Set a<-
    •    max(a,MinimaxAlphaBeta(C,a,b))
    •    if (a >or== b) then
    •    return b
    • return a
    • else
    • for each child C of N do
    •    Set b <-
    •    min(b,MinimaxAlphaBeta(C,a,b))
    •    if(b <or== a) then
    •    return a
    • return b
  30. evalueringsfunksjoner
    alphabeta fungerer best hvis du trekker fra venstetreet. undersøker et tall på noder som tilsvarer halvparten av tredybde i forhold til ren minimax


    bruker heuristikker for å vurdere bladnoder, avgjør hvor gode programmene er
Author
burntoutmatch
ID
336623
Card Set
INFO283 Kunstig Intelligens k.7 og 10
Description
Eksamensforberedelse til Info283 UiB høst 2017
Updated