[科普中国]-学习自动机

概述

从心理学上来说，学习就是通过以往的行为以及因此所获得的经验来改善当前的行为。为了模拟生物的学习过程，Testlin等最先提出了学习自动机的数学模型。其通过与随机环境不断的交互来优化自身，从而在备选的动作集合中选择在当前环境下最优的动作。最优的动作被定义为当前的环境下得到环境奖励概率最大的动作。

学习自动机的概念从提出以来，经历了几十年的发展，其算法的收敛速度已经得到很大的提高。近年来，学习自动机的研究，不仅在于提升学习自动机的算法本身，更大量地涉及如何将学习自动机应用于解决各种实际问题。例如，在分布式计算中，将学习自动机部署于各个节点，各节点所分配的任务由对应的学习自动机依据客观环境（主要为单节点运算能力和节点间的通信强度）进行优化配置，最大限度地提升分布式计算各节点的运算能力。在无线传感器网络中，通过在路由节点中配置学习自动机，能有效地判断自身和相邻节点多变的通信环境，选择最佳链路，降低传输成本，保证通信质量。在人工智能方面，学习自动机可用来模拟个体在集体中的行为帮助管理者进行决策。如在老师和学生的教与学中，老师可通过模拟学生的学习过程更加合理地安排教学活动。在教练和篮球队员的指导与训练中，教练可根据队员的训练与比赛状态来确定队员的训练强度和训练安排。

定义学习自动机（LA）是机器学习中的一类算法，运行在概率空间中，通过不断与未知环境的交互来学习最优值。学习自动机根据环境反馈情况（奖励或惩罚）来调整每个动作被选中的概率分布，并使概率值最终收敛到最佳动作。一个典型的学习自动机由一个四元组{A, B, P, T}定义，而所处的环境是一个三元组{A, B, D}。其中1：

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因其更快的收敛速度，成为了研究的热点，也是目前所泛指的学习自动机。

可变结构学习自动机根据是否具有估计器可以分为两类，第一类是无估计器的学习自动机算法，第二类是有估计器的算法2。

优点学习自动机是在概率空间中运行，不受样本的非均衡性影响，再加上其良好的噪声鲁棒性，全局的优化能力等等优点，非常适用于各种随机环境，可以广泛地应用到博弈论、参数优化、通信网络、图分割等等领域。