Autômato de aprendizagem

Um autômato de aprendizagem é um tipo de algoritmo de aprendizagem de máquina estudado desde a década de 1970. Os autômatos de aprendizagem selecionam sua ação atual com base em experiências anteriores do ambiente. Ele cairá na faixa de aprendizado por reforço se o ambiente for estocástico e for usado um processo de decisão de Markov (MDP).

História

A pesquisa em autômatos de aprendizagem pode ser rastreada até o trabalho de Michael Lvovitch Tsetlin no início dos anos 1960, na União Soviética. Junto com alguns colegas, ele publicou uma coleção de artigos sobre como usar matrizes para descrever funções de autômatos. Além disso, Tsetlin trabalhou no comportamento de autômatos razoável e coletivo e em jogos de autômatos. Autômatos de aprendizagem também foram investigados por pesquisas nos Estados Unidos na década de 1960. No entanto, o termo autômato de aprendizagem não foi usado até que Narendra e Thathachar o introduziram em um trabalho de levantamento em 1974.

Definição

Um autômato de aprendizado é uma unidade de tomada de decisão adaptativa situada em um ambiente aleatório que aprende a ação ótima por meio de interações repetidas com seu ambiente. As ações são escolhidas de acordo com uma distribuição de probabilidade específica que é atualizada com base na resposta do ambiente que o autômato obtém ao realizar uma determinada ação.

Com relação ao campo de aprendizado por reforço, os autômatos de aprendizado são caracterizados como iteradores de políticas. Em contraste com outros aprendizes de reforço, os iteradores de política manipulam diretamente a política π. Outro exemplo de iteradores de políticas são os algoritmos evolucionários.

• um conjunto X de entradas possíveis,
• um conjunto Φ = { Φ₁, ..., Φ_s } de estados internos possíveis,
• um conjunto α = { α₁, ..., α_r } de possíveis saídas, ou ações, com r ≤ s,
• um vetor de probabilidade de estado inicial p(0) = ≪ p₁(0), ..., p_s(0) ≫,
• uma função computável A que após cada passo de tempo t gera p(t+1) a partir de p(t), a entrada atual e o estado atual, e
• uma função G: Φ → α que gera a saída em cada passo de tempo.

Em seu artigo, eles investigam apenas autômatos estocásticos com r = s e G sendo bijetiva, permitindo-lhes confundir ações e estados. Os estados de um tal autômato correspondem aos estados de um "processo de Markov de parâmetros discretos e estados discretos". A cada passo de tempo t=0,1,2,3,..., o autômato lê uma entrada de seu ambiente, atualiza p(t) para p(t+1) por A, escolhe aleatoriamente um estado sucessor de acordo com as probabilidades p(t+1) e produz a ação correspondente. O ambiente do autômato, por sua vez, lê a ação e envia a próxima entrada para o autômato. Frequentemente, o conjunto de entrada X = { 0,1 } é usado, com 0 e 1 correspondendo a uma resposta de não penalidade e de penalidade do ambiente, respectivamente; neste caso, o autômato deve aprender a minimizar o número de respostas de penalidade, e o ciclo de feedback do autômato e do ambiente é chamado de "modelo P". Mais geralmente, um "modelo Q" permite um conjunto de entradas finitas arbitrárias X, e um "modelo S" usa o intervalo [0,1] de números reais como X.

Uma demonstração visualizada/Obra de Arte de um único Autômato de Aprendizagem foi desenvolvida pelo Grupo de Pesquisa µSystems (microSystems) da Universidade de Newcastle.

Autômatos de aprendizado com conjunto de ações finito

Autômatos de aprendizado com conjuntos de ações finitos (FALA) são uma classe de autômatos de aprendizado para os quais o número de ações possíveis é finito ou, em termos mais matemáticos, para os quais o tamanho do conjunto de ações é finito.

Ver também

• Aprendizado por reforço
• Teoria dos jogos
• Teoria dos autômatos

Literatura

• Philip Aranzulla and John Mellor (Home page):
  • Mellor J and Aranzulla P (2000): "Using an S-Model Response Environment with Learnng [sic] Automata Based Routing Schemes for IP Networks ", Proc. Eighth IFIP Workshop on Performance Modelling and Evaluation of ATM and IP Networks, pp 56/1-56/12, Ilkley, UK.
  • Aranzulla P and Mellor J (1997): "Comparing two routing algorithms requiring reduced signalling when applied to ATM networks", Proc. Fourteenth UK Teletraffic Symposium on Performance Engineering in Information Systems, pp 20/1-20/4, UMIST, Manchester, UK.
• Narendra K., Thathachar M.A.L. (julho de 1974). «Learning automata – a survey» (PDF). IEEE Transactions on Systems, Man, and Cybernetics. SMC-4 (4): 323–334. CiteSeerX 10.1.1.295.2280. doi:10.1109/tsmc.1974.5408453  !CS1 manut: Usa parâmetro autores (link)
• Tsetlin M.L. Automation theory and modeling of biological systems. Academic Press; 1973.^{[ligação inativa]}