學習自動機

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

歷史

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

定義

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

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

形式上，Narendra和Thathachar用以下的方式定義隨機自動機

• x為可能輸入的集合
• Φ = { Φ₁, ..., Φ_s } 是可能內部狀態的集合
• a set α = { α₁, ..., α_r } 是可能輸出或是動作的集合，r≤s,
• 初始的狀態機率向量p(0) = ≪ p₁(0), ..., p_s(0) ≫,
• 可计算函数 A ，在每一個時間t，根據從p(t)、當時輸入及狀態來產生p(t+1) * 函數G: Φ → α，在每一個時間產生輸出

在其論文中，只探討r=s，也就是G是双射的學習自動機，因此可能會混淆內部狀態及動作。

自動機的狀態是對應離散狀態離散參數马尔可夫链的狀態^[1]。在每一個時間點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]中的实数為^[2]。

有限動作集學習自動機

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

相關條目

• 强化学习
• 博弈论
• 自動機理論

文獻

• Philip Aranzulla and John Mellor ():
  • 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.
• Narendra K., Thathachar M.A.L. Learning automata – a survey (PDF). IEEE Transactions on Systems, Man, and Cybernetics. July 1974, SMC–4 (4): 323–334 [2018-09-24]. doi:10.1109/tsmc.1974.5408453. （原始内容 (PDF)于2018-07-21）. 
• Mikhail L’vovich TSetlin., Automaton Theory and the Modelling of Biological Systems, New York and London, Academic Press, 1973. (Find in a library（页面存档备份，存于互联网档案馆）)

参考资料

1. (Narendra, Thathachar, 1974) p.325 left
2. (Narendra, Thathachar, 1974) p.325 right
3. Thathachar, M.A.L.; Sastry, P.S. Varieties of learning automata: an overview. IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics). December 2002, 32 (6): 711–722. doi:10.1109/TSMCB.2002.1049606.