學習自動機

學習自動機（learning automaton）是一種1970年代就開始研究的机器学习演算法。學習自動機是由對以往對環境的經驗來選擇目前的動作。若環境是随机性的，且使用了馬可夫決策過程，則這種學習自動機屬於强化学习的演算法。

 歷史 
學習自動機的研究可以追溯到蘇聯的在1960年代所做的研究。他和同事們發表了數篇論文，說明如何用矩陣來描述自動機功能。此外，Tsetlin也在研究合理及集体性的自动机行为，以及自动机游戏的。美國學者在1960年代也有探討學習自動機。不過一直到1974年Narendra及Thathachar在一调查报告中才開始使用「learning automaton」此一名詞。

 定義 
學習自動機是在一隨機環境下的適應性決策產生單元，可以根據和環境重複的互動來學習最佳的動作。動作是依照特定的機率分佈來決定，而系統會依採取特定行動後的環境反應來更新機率分佈。

在强化学习的領域中，學習自動機的特徵是馬可夫決策過程。政策迭代者會直接處理π，這點其他强化学习的演算法不同。另一個政策迭代者的例子是演化演算法。

形式上，Narendra和Thathachar用以下的方式定義隨機自動機
 x為可能輸入的集合
 Φ = { Φ1, ..., Φs } 是可能內部狀態的集合
 a set α = { α1, ..., αr } 是可能輸出或是動作的集合，r≤s,
 初始的狀態機率向量p(0) = ≪ p1(0), ..., ps(0) ≫,
 可计算函数 A ，在每一個時間t，根據從p(t)、當時輸入及狀態來產生p(t+1) * 函數G: Φ → α，在每一個時間產生輸出
在其論文中，只探討r=s，也就是G是双射的學習自動機，因此可能會混淆內部狀態及動作。

自動機的狀態是對應離散狀態離散參數马尔可夫链的狀態(Narendra, Thathachar, 1974) p.325 left。在每一個時間點t=0,1,2,3,...，自動機會從環境讀取輸入，用A來將p(t)更新為p(t+1)，根據機率分布p(t+1)選擇後續狀態，並輸出其動作，而環境會讀取其動作，其結果就是下一個時間的環境輸入。常常會選用輸入集合x = { 0,1 }，其中的0和1對應環境「不懲罰」及「懲罰」的反應。因此學習自動機的目的是使「懲罰」的反應的數量降到最低，這種自動機和環境之間的回授迴路稱為P-模型。而Q-模型允許x是有限集合中的任意值，S-模型是允許x為區間 [0,1]中的实数為(Narendra, Thathachar, 1974) p.325 right。

有限動作集學習自動機 
有限動作集學習自動機（Finite action-set learning automata、FALA）是可能動作數量有限的學習自動機，若用較數學的說法來表示，是動作集合大小為有限值的學習自動機。

相關條目
强化学习
博弈论
自動機理論

 文獻 
 Philip Aranzulla and John Mellor (Home page):
 Mellor J and 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, 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.

 Mikhail L’vovich TSetlin., Automaton Theory and the Modelling of Biological Systems, New York and London, Academic Press, 1973. (Find in a library)

参考资料

Category:机器学习
Category:控制理论