En lærende automat er en type algoritme for maskinlæring som er studert siden 1970-tallet. I forhold til andre metoder for læring så er lærende automat en gren av adaptiv kontrollteori, som ble undersøkt av Narendra og Thathachar (1974), og som opprinnelig ble beskrevet som en endelig tilstandsmaskin. En lærende automat velger nåværende handling basert på tidligere erfaring, gitt observerte treningsdata. Dersom automaten anvendes med stokastisk miljø og en Markovsk beslutningsprosess (MDP), faller algoritmen under kategorien av forsterkende læring.
Historie Forskning på lærende automater kan spores tilbake til arbeider gjort av Mikhail Tsetlin i Sovjetunionen tidlig på 1960-tallet. Sammen med kolleger utga han en samling av artikler om hvordan matriser kan brukes for å beskrive funksjoner i automater. I tillegg arbeidet Tsetlin med fornuftig atferd og kollektive atferd i automater, og på automater brukt i spill. Lærende automater ble også undersøkt av forskere i USA på 1960-tallet. Begrepet lærende automat (learning automat) ble ikke brukt før Narendra og Thathachar introdusert det i en artikkel de publiserte i 1974.
Definisjon En lærende automat er en enhet for adaptiv beslutningsprosess i et stokastisk miljø som lærer optimal handling gjennom gjentatt interaksjon med sitt miljø. Handlingene som tas er bestemt av sannsynlighetsfordelingen til tidligere respons fra miljøet, gitt automatens tidligere handlinger (a posteriori respons).
Innenfor feltet forsterket læring så er lærende automater karakterisert som policy iterators. I motsetning til andre automater for forsterket læring så manipulerer policy iterators direkte regelen (policyen ). Et annet eksempel på policy iterators er evolusjonære algoritmer.
Formelt så definerte Narendra og Thathachar en stokastisk prosess som:
et sett av mulige påtrykk (innsignal), et sett av mulige interne tilstander, et sett av mulige respons (utsignal), eller handlinger, med , en initiell tilstandsvektor , en beregnbar funksjon som etter hvert tidssteg beregner fra , det nåværende påtrykket (innsignalet), og den nåværende tilstanden, og en funksjon som beregner responsen (utsignal) for hvert tidssteg.
I den publiserte artikkelen så undersøkte de kun stokastiske automater med og hvor er bijektiv, noe som gjorde at de kunne behandle handlinger og tilstander på samme vis. Tilstandene i en slik automat tilsvarer tilstandene i en Markov-prosess med diskrete tilstander og parametre (discrete-state discrete-parameter Markov process). Ved hvert tidssteg så vil automaten lese et påtrykk (innsignal) fra miljøet, oppdatere til med funksjonen , velge tilfeldig en etterfølgende tilstand i henhold til sannsynligheten gitt av , og gi tilhørende handling som respons (utsignal). Automatens miljø leser handlingen og sender det neste påtrykket til automaten. Ofte brukes settet som påtrykk, med 0 og 1 tilsvarende henholdsvis ikke-straff og straff fra miljøet. I dette tilfellet vil automaten minimere antallet straffepåtrykk, og tilbakekoblingen mellom automaten og miljøet er kalt en «P-modell». Mer generelt så vil en «Q-modell» tillate et tilfeldig påtrykk , og en «S-modell» bruker et reelle nummer i et intervall som .
Lærende automater for endelige handlinger En klasse av lærende automater for endelige handlinger (Finite action-set learning automater – FALA) er en klasse av lærende automater hvor antall mulige handlinger er begrenset eller, i mer matematiske termer, hvor størrelsen på handlingsrommet er begrenset.
Referanser
Litteratur Philip Aranzulla og John Mellor (arkivert hjemmeside):
Se også Forsterkende læring Spillteori Automatteori
Kategori:Reguleringsteori Kategori:Endelig tilstandsmaskin Kategori:Kunstig intelligens