INFO283 Kunstig Intelligens k.7 og 10

• 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)

å 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

agent får belønning og straff

oppdage mønster og kategorier i data

• 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

• internal (ikke-blad) node = verdi/egenskap/attribut (f.eks boolean, sol)
• beslutningsnoder - rektangler
• blad noder - triangel

• 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>

• 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.

numeriske input, lineær likning(comparison) beslutter/bestemmer prediksjon

beslutning

• gradient-nedstigning: grådig-søk, følg bratteste(steep) nedstigning
• endre hver vekt

• 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

• 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

• 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

• target features are discrete.
• domain of the target variable is {0,1}

• 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

• 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)

• 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

• sjakk, go
• etter du har brukt en strategi i spillet, så vet man hva skal skje, vet intensjon

• 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å

• 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)

• 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

• 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

• andy fordeler: (2,0), (1,1), (0,2)
• andy sin strategi er keep
• barbara sin strategi er (no, yes, yes)

• 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

• 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

minimax som dybde-først, med maksimering og minimering på annen hvert nivå

• 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

• 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

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