學習自動機

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

歷史

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

定義

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

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

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

  • x為可能輸入的集合
  • Φ = { Φ1, ..., Φs } 是可能內部狀態的集合
  • a set α = { α1, ..., αr } 是可能輸出或是動作的集合,rs,
  • 初始的狀態機率向量p(0) = ≪ p1(0), ..., ps(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 (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.
  • 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.