Lærende automaton

Lærende automaton [singular: automaton, plural: automata] 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 automaton en gren av adaptiv kontrollteori, som ble undersøkt av Narendra og Thathachar (1974), og som opprinnelig ble beskrevet som finite state automaton. Lærende automaton velger nåværende handling basert på tidligere erfaring, gitt observerte treningsdata. Metoden er basert på forsterkende læring, gitt et stokastisk miljø og en Markov beslutningsprosess (MDP).

Historie

Forskning på lærende automata kan spores tilbake til arbeider gjort av Mikahel 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 automata. I tillegg arbeidet Tsetlin med fornuftig atferd og kollektive atferd i automata, og på automata brukt i spill. Lærende automata ble også undersøkt av forskere i USA på 1960-tallet. Begrepet lærende automaton (learning automaton) 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 automata karakterisert som policy iterators. I motsetning til andre automata for forsterket læring så manipulerer policy iterators direkte regelen ${\textstyle \pi }$ (policyen ${\textstyle \pi }$ ). Et annet eksempel på policy iterators er evolusjonære algoritmer.

Formelt så definerte Narendra og Thathachar en stokastisk prosess som:

et sett ${\textstyle x}$ av mulige påtrykk (innsignal),
et sett ${\textstyle \mathbf {\Phi } =\left\{\Phi _{1},{\mbox{…}},\Phi _{s}\right\}}$ av mulige interne tilstander,
et sett ${\textstyle \mathbf {\alpha } =\left\{\alpha _{1},{\mbox{…}},\alpha _{s}\right\}}$ av mulige respons (utsignal), eller handlinger, med ${\textstyle r\leqslant s}$ ,
en initiell tilstandsvektor ${\textstyle p\left(0\right)=\left\langle p_{1}\left(0\right),{\mbox{…}},p_{s}\left(0\right)\right\rangle }$ ,
en beregnbar funksjon ${\textstyle A}$ som etter hvert tidssteg ${\textstyle t}$ beregner ${\textstyle p\left(t+1\right)}$ fra ${\textstyle p\left(t\right)}$ , det nåværende påtrykket (innsignalet), og den nåværende tilstanden, og
en funksjon ${\textstyle G:\Phi \to \alpha }$ som beregner responsen (utsignal) for hvert tidssteg.

I den publiserte artikkelen så undersøkte de kun stokastiske automata med $r=s$ og hvor ${\textstyle G}$ 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).^[1] Ved hvert tidssteg ${\textstyle t=0,1,2,3,{\mbox{…}}}$ så vil automaten lese et påtrykk (innsignal) fra miljøet, oppdatere ${\textstyle p\left(t\right)}$ til ${\textstyle p\left(t+1\right)}$ med funksjonen ${\textstyle A}$ , velge tilfeldig en etterfølgende tilstand i henhold til sannsynligheten gitt av ${\textstyle p\left(t+1\right)}$ , og gi tilhørende handling som respons (utsignal). Automatens miljø leser handlingen og sender det neste påtrykket til automaten. Ofte brukes settet ${\textstyle x=\left\{0,1\right\}}$ 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 ${\textstyle x}$ , og en «S-modell» bruker et reelle nummer i et intervall ${\textstyle \left[0,1\right]}$ som ${\textstyle x}$ .^[1]

Lærende automata for endelige handlinger

En klasse av lærende automata for endelige handlinger (Finite action-set learning automata – FALA) er en klasse av lærende automata hvor antall mulige handlinger er begrenset eller, i mer matematiske termer, hvor størrelsen på handlingsrommet er begrenset.

Referanser

^ ^a ^b Narendra, Kumpati S.; Thathachar, M. A. L. (Juli 1974). «Learning Automata - A Survey». IEEE Transactions on Systems, Man, and Cybernetics. 4 (på engelsk). SMC-4: 323–334. ISSN 0018-9472. doi:10.1109/tsmc.1974.5408453. Besøkt 3. mai 2018.

Litteratur

Philip Aranzulla og John Mellor (arkivert hjemmeside):
- Mellor, J.; Aranzulla, P. (2000). «Using an S-Model Response Environment with Learnng Automata Based Routing Schemes for IP Networks». Proc. Eighth IFIP Workshop on Performance Modelling and Evaluation of ATM and IP Networks. Ilkley,UK: 56/1–56/12.
- Mellor, J.; Aranzulla, P. (1997). «Comparing two routing algorithms requiring reduced signalling when applied to ATM networks». Proc. Fourteenth UK Teletraffic Symposium on Performance Engineering in Information Systems. UMIST, Manchester, UK: 20/1–20/4.
Narendra, K.; Thathachar, M.A.L. (Juli 1974). «Learning automata – a survey» (PDF). IEEE Transactions on Systems, Man, and Cybernetics. SMC-4 (4): 323–334. doi:10.1109/tsmc.1974.5408453.
Mikhail L. Tsetlin (1973). Automaton theory and modeling of biological systems. Mathematics in science and engineering. vol. 102. New York: Academic Press. ISBN 0127016503.

Se også

Autoritetsdata

[:0-1] Narendra, Kumpati S.; Thathachar, M. A. L. (Juli 1974). «Learning Automata - A Survey». IEEE Transactions on Systems, Man, and Cybernetics. 4 (på engelsk). SMC-4: 323–334. ISSN 0018-9472. doi:10.1109/tsmc.1974.5408453. Besøkt 3. mai 2018.

[1]