學習自動機（Learning Automata）是通過與隨機環境不斷的互動來調整自己，也就是說，其通過與環境不斷的交流獲得經驗用來改善自己的行為，從而在可選擇的動作中選擇在該環境下最優的動作，而最優的動作也就是在當前的環境下，能得到環境獎勵的機率最大的動作。
基本介紹
- 中文名：學習自動機
- 外文名：Learning Automata
- 屬於：機器學習
- 優點：良好的噪聲魯棒性，全局最佳化能力
- 提出時間：1961
- 提出者：Tsetlin等
概述,定義,分類,優點,
概述
從心理學上來說，學習就是通過以往的行為以及因此所獲得的經驗來改善當前的行為。為了模擬生物的學習過程，Testlin等最先提出了學習自動機的數學模型。其通過與隨機環境不斷的互動來最佳化自身，從而在備選的動作集合中選擇在當前環境下最優的動作。最優的動作被定義為當前的環境下得到環境獎勵機率最大的動作。
學習自動機的概念從提出以來，經歷了幾十年的發展，其算法的收斂速度已經得到很大的提高。近年來，學習自動機的研究，不僅在於提升學習自動機的算法本身，更大量地涉及如何將學習自動機套用於解決各種實際問題。例如，在分散式計算中，將學習自動機部署於各個節點，各節點所分配的任務由對應的學習自動機依據客觀環境（主要為單節點運算能力和節點間的通信強度）進行最佳化配置，最大限度地提升分散式計算各節點的運算能力。在無線感測器網路中，通過在路由節點中配置學習自動機，能有效地判斷自身和相鄰節點多變的通信環境，選擇最佳鏈路，降低傳輸成本，保證通信質量。在人工智慧方面，學習自動機可用來模擬個體在集體中的行為幫助管理者進行決策。如在老師和學生的教與學中，老師可通過模擬學生的學習過程更加合理地安排教學活動。在教練和籃球隊員的指導與訓練中，教練可根據隊員的訓練與比賽狀態來確定隊員的訓練強度和訓練安排。
定義
學習自動機（LA）是機器學習中的一類算法，運行在機率空間中，通過不斷與未知環境的互動來學習最優值。學習自動機根據環境反饋情況（獎勵或懲罰）來調整每個動作被選中的機率分布，並使機率值最終收斂到最佳動作。一個典型的學習自動機由一個四元組{A, B, P, T}定義，而所處的環境是一個三元組{A, B, D}。其中：
A代表可選動作集合{a1,a2,...,an }，最終學習自動機將收斂到其中一個動作。
B代表環境的反饋值，在S型環境中，B是一個連續值，通常介於0到1之間；在Q型環境中，B是幾個固定值；在P型環境中，B是0或者1；而在連續動作的學習自動機（CALA）中，B值較特殊，其數值跟所需最佳化的函式值大小有關，具體內容將在後續章節詳細介紹。
P代表每個動作被選中的機率{ p1,p2,...,pn}，在每次疊代中，P的分布會改變，受到環境獎勵的動作機率會增加，而沒有受到環境獎勵（或者受到環境懲罰）的動作機率會降低，最終某個動作的機率值會接近1，而其他動作的機率值會接近0，這就是學習自動機的收斂狀態。
T代表學習自動機的機率更新策略，決定了不同自動機模型的性質，有RP（rewarpenalty）、RI（reward-inaction）、IP（inaction-penalty）三種基本模式。
D代表環境對每個動作的獎勵機率，如果D是固定不變的，則稱環境是穩定的隨機環境，如果D隨時間變化，則稱環境是非穩定的隨機環境。
分類
為了模仿生物的學習過程，Tsetlin等在1961年最先提出學習自動機（LearningAutomata）的數學模型，該模型被稱為固定結構學習自動機（FSSA），
固定結構的學習自動機可以有多個動作，而每個動作都會映射到有限個狀態中，學習自動機根據環境的反饋而在不同的狀態之間轉移。以兩個動作的學習自動機為例，每個動作有N個狀態，當學習自動機處於前N個狀態時，輸出動作是α1，處於後N個狀態時，輸出動作α2。
可變結構學習自動機（VSSA）的概念也是在上世紀60年代被提出的。與固定結構的學習自動機每個動作具有有限個狀態不同，可變結構學習自動機能根據環境而改變自己的狀態，也就是說具有無限個狀態，且往往將狀態直接映射成為學習自動機選擇不同動作的機率。VSSA因其更快的收斂速度，成為了研究的熱點，也是目前所泛指的學習自動機。
可變結構學習自動機根據是否具有估計器可以分為兩類，第一類是無估計器的學習自動機算法，第二類是有估計器的算法。
優點
學習自動機是在機率空間中運行，不受樣本的非均衡性影響，再加上其良好的噪聲魯棒性，全局的最佳化能力等等優點，非常適用於各種隨機環境，可以廣泛地套用到博弈論、參數最佳化、通信網路、圖分割等等領域。
