跳转到内容

学习自动机

维基百科,自由的百科全书

学习自动机(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.