-
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)
-
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
-
læring ved forsterking
agent får belønning og straff
-
Ikke rettledet læring
oppdage mønster og kategorier i data
-
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
-
Hva representerer nodene og kantene i beslutningstreet?
- internal (ikke-blad) node = verdi/egenskap/attribut (f.eks boolean, sol)
- beslutningsnoder - rektangler
- blad noder - triangel
-
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>
-
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.
-
lineær regresjon
numeriske input, lineær likning(comparison) beslutter/bestemmer prediksjon
-
-
optimering
- gradient-nedstigning: grådig-søk, følg bratteste(steep) nedstigning
- endre hver vekt
-
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
-
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
-
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
-
lineær regresjon for klassifikasjon
- target features are discrete.
- domain of the target variable is {0,1}
-
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
-
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)
-
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
-
null-sum-spill med perfekt informasjon
- sjakk, go
- etter du har brukt en strategi i spillet, så vet man hva skal skje, vet intensjon
-
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å
-
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)
-
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
-
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
-
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)
-
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
-
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
-
effektivisering av søk
minimax som dybde-først, med maksimering og minimering på annen hvert nivå
-
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
-
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
-
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
|
|