Hei.

Algoritmer

Ord og uttrykk

Beste først

Bruker i grunnen “bredde først”-søk der det foregår kvalitativ seleksjon av hvilken node som skal besøkes neste. Den prøver å “gjette” seg fram til den beste mulige veien fram til målnoden.

Heuristisk

Det er en algoritme som verken beviser at den er optimal, som i at den har ikke bevist at den har optimal kjøretid eller optimal løsning. En heuristisk algoritme vil (vanligvis) gi et godt resultat.

A*

• “Beste først”-algoritme
• Oppdaget i 1968 av Peter Hart, Nils Nilsson og Bertram Raphael
• Bredde først og dybde først er 2 spesialtilfeller av A*
• Dijkstras algoritme er det spesialtilfellet av A* der
• Dybde først søk med A*
  • Global counter som er initialisert med int
  • Startnoden får verdien . Deretter får alle de nye naboene verdien . ().
• A* gjetter seg fram til hvilken node som er den beste veien å gå. Deretter den nest beste og så videre. . er kostnaden fram til noden, er et heuristisk estimat av minimumskostnaden som må til for å nå målet. blir lagret i en priority-queue, der den veien med minst mulig er den veien som har best sannsynlighet for at den er den rette veien.
• A* er “komplett” i den forstand at den vil alltid finne en løsning så lenge løsningen finnes.

Back-tracking

Prøver å finne fram til mål ved å “prøve seg fram”. Den starter med “et valg” av neste vei å gå. Deretter hvis det valget var galt, så “backtracker” den seg til noden der den gjorde valget, og prøver et annet valg. Hvis det ikke er flere alternativer/valg så feiler den.

Backward chaining

Brukes i blant annet i ekspertsystemer. “Backward chaining” brukes når en vet hva målene skal være, men er usikker på om det er nok datagrunnlag for å støtte opp om målene. Kan også brukes om hypoteser.

Forward chaining

Brukes når en har et datagrunnlag, men lurer på hva målene/resultatene blir. På grunnlag av dataene kan en lage nye konklusjoner og dermed definere et optimalt mål.

Depth-first

“Dybde først”-søk søker i alle barn-barnebarn og så videre.

Breadth-first

Søker først i alle nodene som er naboer, deretter naboenes naboer, naboene til naboenes naboer osv.

Beam search

Beam search, however, only unfolds the first m most promising nodes at each depth, where m is a fixed number, the “beam width.” So while best-first search for example, will always expand one path with the least net path cost, beam search with m=2 will expand the best two paths with the least net path cost instead of just one.

An optimisation of the best first search graph search algorithm where only a predetermined number of paths are kept as candidates. The number of paths is the “width of the beam”. If more paths than this are generated, the worst paths are discarded. This reduces the space requirements of best first search.

Hill climbing

Fjellklatring finner en (ikke nødvendigvis optimal) løsning på et problem i et lokalt område.

non-deterministic search

Iterative deepening

Formalismer for representasjoner

Ikke-analoge

• Egenskapsvektor (feature vector)
  • Egenskaper som definerer et mønster representeres i en vektor – ofte på binær form
• Kromoson
  • Nevrale nett – avanserte mønstergjenkjennere

Analoge

• Produksjonsregler
  • Logisk formell, avledet fra propopositional calculus
  • Godt egnet for representasjon av ekspertbasert heuristikk
• Semantiske nett
  • Egnet for representasjon av hverdagskunnskap
  • Plattform for ontologisk kunnskap
• Predikatlogikk
  • Strengt logisk, nært knyttet til propopositional calculus og boolsk algebra.
  • Godt egnet for representasjon av ekspertbasert heuristikk
• Rammer og scripts
  • Ligner objekter og beslektet med semantiske nettverk
  • Godt egnet for representasjon
• Cases
  • Bygger på vanlig databasekonsept
  • Omfatter og et enkelt læringsformat

Fuzzy

Dersom temperaturen måles til 210 grader hvor ”Passende varme på grillen” er det?

Gitt at det aktuelle fuzzy settet i deloppgave e. inngår i en regel som konkluderer med at det skal være ”Passende varme på grillen” med tilhørighet 0,75. Hva vil anbefalt temperatur med utgangspunkt i dette fuzzy settet være (Tips: Defuzzification).

passende varme på grillen. Støtteverdi = 220.

Uten skalering:

Med skalering:

Semantisk nettverk

Under er gjengitt en illustrasjon av et øye. Øyets deler er benevnt med sitt engelske/latinske navn. Det er 15 nummererte deler av øyet som er benevnt.

Konstruer et semantisk nett med disse entitetene. Benevn relasjonene mellom dem slik du oppfatter disse fra illustrasjonen over.

Svar:

Genetisk algoritme

Du skal lage en kodeknekker ved hjelp av en genetisk algoritme. Koden består av 4 tegn som må stå i riktig sekvens. Hvert tegn kan være et tall mellom 0 og 9. Det finnes en innretning som gjør det mulig å teste om noen tall i en sifferserie inneholder en eller flere tegn som inngår i koden. Denne innretningen kan angi hvor mange tegn som er identifisert, og hvilke av disse som står på riktig plass i en sekvens. (Tips: Dette er analogt med måten man knekker koder i et spill som Master Mind).

Lag et eksempel på et kromoson. Hvilke krav bør vi stille til populasjonen i første generasjon?

#(3 4 2 0) //eksempel på kromoson
Vi bør ha en populasjon med alle siffere godt representert

Hvordan vil du konstruere de tre operatorene som typisk inngår i en genetisk algoritme? I svaret må du angi operator, forklare hva du vil den skal gjøre og gi et eksempel på hvordan dette vil fungere i kodeknekkeren.

Krysning, seleksjon, mutasjon – hver og en beskrives kort.

Hvordan vil du gjennomføre seleksjon for at algoritmen skal fungere effektivt?

#(n1, n2, n3, n4) = K
#(j1, j2, j3, j4) Fasit = J

For hvert kromoson K

For hver ni i K
Hvis ni er et element i J da er PK = PK+1 //finnes siffer ni i løsningen
Hvis ni = ji da er PK = PK+1 //riktig plassering gir høyere score

Et riktig tall på riktig plass gir 3 poeng. Kan riktig tall (på gal plass) gir kun 1 poeng.
De beste kromosonene får parre seg og etablere neste generasjon som så testes igjen.

Nevrale nett

Beskriv kort et perseptron.

Et perceptron består av en inputvektor () og en vektvektor (). Disse vil da gi en sum og hvis
. Hvis ikke blir .

Hvordan trenes et perseptron? Beskriv trinnvis hovedstegene i perseptronets kovergensprosedyre.

1. Etabler et treningssett med gode data
2. Lag en feature vektor for alle data i settet, hvert element i settet tilordnes I for hver treningssekvens.
3. Initialiser vektvektoren .
4. Multipliser og sjekk om resultatet er større enn 0.
5. Dersom dette ikke er tilfelle, etabler avvik og juster vekter
6. Gjenta treningen for hele treningssettet inntil systemet konvergerer for alle data i treningssettet.

Forklar de arktitektoniske forskjellene mellom et perseptron og et backpropagation nett.

Backpropagation “skylder” på feil i estimatene til “forrige node” og retter opp vektene “tidligere” i køen.

1. Initialize the weights in the network (often randomly)
2. repeat

3. * foreach example e in the training set do

   1. O = neural-net-output(network, e) ; forward pass
   2. T = teacher output for e
   3. Calculate error (T – O) at the output units
   4. Compute delta_wi for all weights from hidden layer to output layer ; backward pass
   5. Compute delta_wi for all weights from input layer to hidden layer ; backward pass continued
   6. Update the weights in the network

   * end

4. until all examples classified correctly or stopping criterion satisfied
5. return(network)

Backpropagation brukes i problemer der en ikke vet om input er korrekt eller ikke korrekt før lengre “inn” i systemet.
Hvordan hvordan backpropagation-metoden fungerer i en trelags BP-arkitektur. Del forklaringen opp i:

• Deteksjon og håndtering av avvik mellom ønsket og virkelige verdi
• Porpagering av avviket til mellomnivået
• Endring av vektene mellom resultatnivået (output layer) og mellomnivået (middle layer).

Ting som en burde kunne

APKA-prinsippet

• Awareness
  • oppmerksomhet (fokusering og orienteringsevne)
• Perception
  • Oppfattelsesevne (absorbsjon og reaksjon)
• Knowledge
  • mobilisering og utnyttelse av kunnskap og evne til å beslutte og lære
• Action
  • handlingsevne

Et problem

Et problem er erkjennelsen av en utilfredstilt tilstand, et mål er ikke oppfylt.

Kunnskapsrepresentasjon

Kunnskapsrepresentasjon er viktig fordi lagring av kunnskap krever struktur og syntax. Ingen universell representasjon.

• Tilnærming til modeller som omfatter virkelige mentale prosesser knyttet til langtidshukommelsen
• Kan vi tenke oss en virkelighet som benytter en langtidshukommelse basert på en ikke-intern representasjon?
• Eksempler på “kunstige” representasjoner:
  • Semantiske nett,
  • frames (rammer),
  • produksjonsregler,
  • predikatlogikk,
  • naturlig språk,
  • artimetikk,
  • hieroglyfer

Perceptron

20:36:58 <@Blackmore> evening
20:37:39 < o^nd> hoi
20:37:46 <@Blackmore>
20:37:53 <@Blackmore> Klar til i morgen?
20:41:48 < o^nd> næh
20:41:53 < o^nd> bare surr disse algoritmene
20:42:46 <@Blackmore> dybde/bredde først? A-star?
20:43:13 < o^nd> perseptron, backpropagation, nevrale nett etc
20:44:29 <@Blackmore> nevral nett er data struktur….  perseptron er algoritme for å trene opp nevral nett (for å løse linære problemer), backpropagation er tenikk.
20:44:39 <@Blackmore> teknikk
20:45:41 <@Blackmore> både perceptron og backpropagation brukes i forbindelse med nevrale nett.
20:46:46 <@Blackmore> perceptron: ideen er å bygge linje (for 2d problem), flate (for 3d problem)…… som separerer dine klasser (mulige output).
20:46:48 < o^nd> og forskjellen mellom perceptron og backpropagation?
20:48:04 < o^nd> btw, vet du hvordan eksamen vår blir? #:)
20:48:42 <@Blackmore> backpropagation brukes i problmer der du ikke får beskjed på forhånd om dette er riktig input eller feil input
20:49:04 <@Blackmore> o^nd: Nei dessverre (ærlig!)
20:49:11 < o^nd> “ok”
20:49:42 <@Blackmore> OK… følgende eksempel…. tenk lineær algebra
20:50:15 <@Blackmore> Vi vil trene opp et system som skal gjenkjenne om du tegner firkant eller ikke.
20:51:07 <@Blackmore> tenkt deg et gridd 6 x 6
20:51:33 < o^nd> kk
20:51:37 <@Blackmore> hver av de 36 cellene kan være 0 eller 1 (blank eller ikke blank).
20:52:04 <@Blackmore> der du har 1ere har du tegnet noe….
20:52:16 <@Blackmore> ops.. tlf.
20:52:36 < o^nd> heh
20:52:41 <@Blackmore> K.
20:52:42 < o^nd> *ooops i did it again*
20:53:28 <@Blackmore> kluet er å bestemme om d du har tegnet er firkant eller ikke.
20:53:46 <@Blackmore> starter med definisjonene:
20:54:56 <@Blackmore> siden svaret kan være bare ja og nei, snakker vi om binary classification.
20:55:51 <@Blackmore> for hver celle X (starter med øverst til venstre) har du en verdi…. alle de 36 cellene er input.
20:56:26 < o^nd> ok
20:56:41 <@Blackmore> kombinasjonenj av alle X kalles for festure vector.
20:56:58 <@Blackmore> {x1, x2… x36}
20:57:04 <@Blackmore> feature
20:58:17 <@Blackmore> Nå tenker du på en flate…. der alle mulige kombinasjoner av figurer er representert.
20:59:13 <@Blackmore> de kombinasjonene som gir firkant, kaller vi for 1, de andre for 0
20:59:49 <@Blackmore> vårt mål er å finne linje… som deler (klasifiserer) de to gruppene.
21:00:34 <@Blackmore> hvis de finnes en slik linje, sier vi at problemet er lineær (dessverre veldig få slike i virkeligheten).
21:01:11 <@Blackmore> det vi skal finne ut er funksjonen f(x) til denne linjen.
21:02:40 <@Blackmore> formelen er følgende: f(x) = <w . x> + b der x er feature (input) vectoren, w er vekt (weight) vectoren… og b er konstant (bias).
21:03:15 <@Blackmore> w er vector som er like stor (lang) som x (eller får vi ikke utføre gange operasjonen).
21:03:57 <@Blackmore> i stanrten kan vi sette w = {1, 1, …1}
21:05:05 <@Blackmore> OK…. ved å forendre w og b, skal vi finne linjen vi er ute etter.
21:05:28 <@Blackmore> Det er her perceptronen og backpropagation skiller lag.
21:05:39 < o^nd> hmm ok… hadde ei innlevering med perceptron, men forstod ikke så veldig mye…
21:06:16 <@Blackmore> skjønner du nå? bare spør og avbryt hvis det er uklart
21:07:24 < o^nd> jo ja… jeg tror det
21:08:08 <@Blackmore> Perceptron: Hvis du på forhånd vet hva som er rett og galt og vil bare trene opp systemet (supervised learning) så bruker du eksempler: du gir et sett med
input (du tegner noe i gridden) (er det et eller en grid ?)
21:08:24 < o^nd> en grid
21:08:35 <@Blackmore> og til slutt sier du f.eks: dette ER firkant
21:08:51 < o^nd> egentlig et rutenett, men hvatever
21:08:59 < o^nd> okay
21:09:43 <@Blackmore> dermed har du noe som kalls for “training set” et par X med tilsvarende output (i dette tilfellet 1 fordi dette er forkant).
21:11:51 < o^nd> ja… men… hva skal dette brukes til.. disse vektene fungerer jo bare på 1 input, eller har jeg misforstått noe?
21:11:59 <@Blackmore> det vi gjør er å øke alle w der vi har X = 1 med en vis tall.
21:12:26 <@Blackmore> det samme gjentar du for neste treningssett.
21:13:29 <@Blackmore> eksempel med 2×2 grid
21:14:21 <@Blackmore> X = {1, 0, 0, 1}  , w i starter er {1, 1, 1, 1}  svar (output) 1
21:16:09 <@Blackmore> dermed forandrer vi w til f.eks. w {1.1, 1, 1, 1.1} (med learning factor 0.1)
21:16:54 <@Blackmore> hadde svaret vært 0, ville vi minke med learning factor.
21:17:01 <@Blackmore> get the idea.
21:17:26 <@Blackmore> til slutt linjen blir funksjonen: <x . w > + b = 0
21:17:30 <@Blackmore> tadaaaaaaaaaaaaaa
21:18:27 <@Blackmore> darmed når du sender X (en grid) og <x . w > + b < 0 vet du at svaret er nei
21:18:34 <@Blackmore> darmed når du sender X (en grid) og <x . w > + b > 0 vet du at svaret er ja
21:19:07 <@Blackmore> jævli møddafakkings enkelty.
21:19:12 <@Blackmore> enkelt-
21:20:58 < o^nd> men… vektene er jo fremdeles koblet til en og samme input`?
21:21:14 <@Blackmore> hmm.. nei.
21:21:51 <@Blackmore> X kan være: {0, 0, 0, 0}, {0,0, 0, 1} …….
21:22:45 <@Blackmore> {0, 0, 0, 0} og {1, 1, 1, 1} er trivielle input (vil ikke forandre noe).
21:22:53 <@Blackmore> fra alle andre, kan du lære.
21:23:00 <@Blackmore> fra alle andre, kan du lære systemet
21:23:08 < o^nd> i 6×6 eksemplet, så må det da være 2^36 kombinasjoner
21:23:53 <@Blackmore> ja… men du buker 1000 training set og da er systemet forhåpentligvis ferdigtrent.
21:24:30 <@Blackmore> deretter kan systemet bestemme (jobbe for deg og ikke du for henne).
21:24:35 <@Blackmore> deretter kan systemet bestemme (jobbe for deg og ikke du for den).
21:24:49 <@Blackmore> for henne… hehe .. tenker bare på damer.
21:25:01 <@Blackmore> deT
21:25:10 <@Blackmore> anyway….
21:25:57 <@Blackmore> jævlig vanskelig å forklare det i chatten, men det er veldig enkelt (i motsetning til ikke-lineære problemer som jeg jobba med i forbindelse med diplomen).
21:26:47 < o^nd> okay
21:29:43 <@Blackmore> for hvert treningsett med positiv output øker du de elementene i w som tilsvarer 1 i X.
21:30:04 <@Blackmore> for hvert treningsett med negativ output reduserer du de elementene i w som tilsvarer 1 i X.
21:30:26 <@Blackmore> og slik fortsetter du til du lærer opp systemet.
21:32:03 <@Blackmore> startverdier for w er vanligvis {0, 0, …..0} eller {1, 1, 1, 1} samma faen den vil jo konvergere uansett.
21:32:26 <@Blackmore> 0, 0, 0 er mer vanlig tror jeg.
21:32:33 < o^nd> hmm ok
21:32:56 < o^nd> vi hadde i oppgave å implementere OR som perceptron
21:33:11 < o^nd> tror det ble litt for enkelt…
21:33:19 <@Blackmore> ja
21:33:41 < o^nd> vitsen med perceptron faller bort
21:33:42 <@Blackmore> vil konvergere etter max 2 treninger
21:33:55 <@Blackmore> ja i dette tilfellet ja.
21:35:52 < o^nd> og det som er av stoff på nettet om perceptron er svært omfattende og uoversiktlig, eller ubrukelig
21:45:50 <@Blackmore> ja.. det kan nok stemme
21:46:12 <@Blackmore> bare få med deg prinsippet…
21:46:32 <@Blackmore> du får sikkert oppgave om å lage en eller annen onthology

Popularity: 54% [?]