本文是一篇计算机论文，本文从速度和性能的角度出发，提出了分布式的 top-k 特征选择方法。虽然封装式的特征选择方法性能较好，但是时间开销较高，并且又由于强化学习算法的在线交互特性，导致时间花销更大。
第一章 绪论
1.1课题背景
1956 年的达特茅斯会议被大多数研究者认为是人工智能领域确立的源头。会议发起人之一的约翰·麦卡锡提出了人工智能的概念并将其定义为“研制智能机器的一门科学与艺术”。会上讨论的一些如机器学习、神经网络、自然语言处理议题，如今依旧是人工智能领域研究的重要部分。如今，人工智能的研究成果已经在各行各业得到了广泛的应用，如机器翻译、语音识别、自动驾驶、推荐系统。我国在 2021 年最新的十四五规划纲要中明确指出将新一代人工智能作为科技攻关的第一大点，人工智能的发展势必进入新的阶段。
最初，各领域的学者以自己方式理解和实现人工智能，在这一过程中产生了三大学派，分别是符号主义、联结主义和行为主义。符号主义来源于对人脑抽象逻辑的模拟，通过数学逻辑的符号操作模仿人的思考过程。联结主义认为可借鉴人脑复杂联结的神经元结构，通过大量的神经元来模拟智能，其中以神经网络的方法最为著名。行为主义来源控制论的相关研究，通过模拟人的感知——行动过程完成对人类智能的模拟。而机器学习也同样是实现人工智能的一种方法，它基于概率和统计的相关知识，研究从数据中进行学习，并对新的事物做出预测。在这一思想下，研究者开发出一系列经典的算法。
机器学习是一门研究如何让计算机系统根据以往的经验来改善系统自身性能的学问[1]。机器学习方法可以分为有监督学习（Supervised Learning）、无监督学习（Unsupervised Learning）和强化学习（Reinforcement Learning）。有监督学习使用的数据是带有标签的，一般用来进行预测的任务。无监督学习使用的数据是没有标签的，一般是用来寻找数据本身的关系特点。强化学习不依靠现有的样本，而是通过与环境的交互来进行学习的。因此，强化学习适用于那些难以获取正常样本，或是难以对样本进行标记的场景，如棋类或电动游戏，自动驾驶等领域。
1.2主要研究内容
本文的主要研究内容是强化学习的特征选择问题。本文从特征子集选择方法、强化学习的增量和非平稳特性、加速学习三个角度，研究强化学习的特征选择问题。本文的主要工作如图 1.1 所示。
1、基于封装式的特征选择方法
(1) 提出分段值函数的贪心特征选择方法
在特征选择中，特征的数目随着状态的提高而指数级增长，因而本章使用贪心的方法生成待选的特征子集。特征选择的标准是通过比较不同特征子集在强化学习中的效果。但是在实验中发现特征选择的结果不稳定，表现为多次实验的特征子集选择差别较大，因而又通过分段的值函数器来提高特征选择的稳定性。
(2) 分布式的 top-k 贪心特征选择方法
在上述实验中发现特征选择的速度较慢，究其原因是使用强化学习的训练效果来评估子集是很耗时的，并且这一过程本身是不能精简的，为此本文通过分布式的方法同时评估多个子集。分段的方法虽然能提高一定的稳定性，但因为强化学习算法的特点导致一定的波动性，表现为相同子集的评估效果也不一样，这会导致特征选择的不同，并且特征选择也需探索更多的可能性。因此结合上面两个方面，本文提出了分布式的 top-k 贪心特征选择方法。
第二章 相关背景知识介绍
2.1强化学习基础知识
2.1.1 马尔可夫决策过程
在强化学习中，马尔可夫决策过程是一个最基本的理论模型，大多数的问题都可以被看作或转化为马尔可夫决策过程。在此刻的状态转换概率与之前的历史状态信息如 𝑆1, 𝑆2, . . . , 𝑆𝑡−1 都无关。在这一框架中，实践的主体被称为智能体，它能进行相关学习以及做出策略决定，而除智能体本身外与智能体进行相互作用的都在环境的范畴之内。智能体和环境不断地进行互动，智能体通过自身的行动改变环境的状态，之后环境会给到智能体一个及时的响应。这个响应用不同的值体现对环境影响，我们的目标就是在交互过程结束后使得累计奖赏之和达到最大。
马尔可夫决策过程是一个由< 𝑆, 𝐴, 𝑃, 𝑅 > 表示的四元组。其中𝑆表示为所有可能状态的集合空间，并且这里的状态指的是所有能够对智能体策略改进有所帮助的元素。𝐴表示为智能体在所有状态下可能进行的动作的集合。𝑃 ∶ 𝑆 × 𝐴 × 𝑆 → [0,1] 表示状态转移函数，𝑃(𝑠, 𝑎, 𝑠′) 表示在状态 𝑠 下采取 𝑎 动作转移到 𝑠′ 的概率，𝑅 是奖赏函数空间，𝑅 ∶ 𝑆 × 𝐴 × 𝑆 → 𝑅表示采取动作 𝑎 后状态由 𝑠 转为 𝑠’ 后从环境中得到的奖赏值。
在定义好马尔可夫决策过程后，智能体和环境的交互过程可描述如下：在 𝑡 时刻，智能体处于状态空间 𝑆 中的𝑠𝑡下，随后从动作空间 𝐴 中选择行为动作 𝑎，之后智能体从环境中获得一个奖赏𝑟𝑡+1，同时环境转移到一个新的状态𝑠𝑡+1∈ 𝑆，然后在新的状态下智能体继续重复上述过程，直至结束。
2.2常用的强化学习算法
根据学习和决策是否使用相同的值函数，可将算法分成同策 (on policy) 和异策 (off policy)学习；根据学习过程中是否需要环境的模型，分为有模型学习和无模型学习；根据在不同时间的更新方式还分为回合更新和时序差分学习。另外，近年来强化学习和深度学习相结合的深度强化学习类算法逐渐成为热点。
2.2.1 蒙特卡洛方法
解决强化学习问题的一个难点是智能体对于所处环境的了解是不完备的，我们很难知道状态转移概率的模型，因而就不能使用有模型的方法，而是需要采用其他的无模型的方法，如蒙特卡洛方法。
2.2.2 时序差分方法
Sutton 提出了时序差分算法，其综合了蒙特卡洛和动态规划的方法，是强化学习中具有重要影响力的学习算法。该方法可以通过在部分的连续状态下进行学习，它能够预估某一状态在完整的状态序列下的收获，然后不断地获得和改进状态的价值。
(1) 标准的时序差分方法
它是一种无模型的算法，是直接利用经验进行学习，不同于蒙特卡洛方法每次对样本进行完成采样，时序差分算法在行动一步或者多步后，来估算当前的状态值。最基本的一步更新的为 TD(0) 算法，通过当前和未来一步的状态的估计差值来更新状态值函数。
第三章 基于分段值函数的封装式特征选择方法 .............. 20
3.1动机 ........................ 20
3.2背景知识 ............... 21
第四章 分布式的 top-k 贪心特征选择方法 ....................... 33
4.1动机 ............................... 33
4.2背景知识 ...................................... 33
第五章 基于经验回放的过滤式特征选择方法 .................... 41
5.1动机 ...................................... 41
5.2背景知识 ........................................ 41
第五章 基于经验回放的过滤式特征选择方法
5.1动机
在强化学习的封装式特征选择过程中，对于任意特征子集的评价都需进行强化学习的训练，接着将测试的效果作为子集的评价标准。为了选择一个足够好的特征集合，势必会尝试很多不同的候选特征子集，从而也会进行很多次的强化学习的训练过程。即使我们可以通过分布式的方法减少了特征选择的时间，但由于强化学习的本身训练时间较长，使用频率也太高，导致最终花费的时间过长。因而改进的地方是在特征选择的过程中减少同强化学习的交互，从而减少特征选择的时间开销。所以本章使用过滤式的特征选择方法，首先通过智能体和环境的交互生成数据，然后在数据集上利用过滤式的方法直接完成特征选择工作，得到最终的特征子集。最后只需进行一次强化学习的训练和测试，来检验特征选择的好坏。
不同于封装式方法将特征子集在后续算法中的效果作为子集评估的根据，过滤式方法不需要后续算法的参与，一般是直接在数据集上进行特征选择。通过对于数据集的分析，设定特征的评价标准，然后进行特征的选择。过滤式方法在速度上相比封装式有着更大的优势。过滤式的方法的基本过程如图 5.1 所示。
第六章 总结与展望
6.1总结
强化学习仍受限于高维状态和动作引发的维度灾难，解决的方法是使用远小于状态、动作个数的特征对值函数进行估计。但是估计的值函数跟真正的值函数会有误差。因而本文围绕着强化学习的特征选择，通过为值函数构造好的特征集合的方式来减小误差。本文的主要研究内容总结如下：
1. 使用封装式的特征选择方法，将后续值函数估计的效果作为特征选择的根据，但是选择的特征集合不稳定。因而对值函数进行改进，使用分段值函数的方法提高了特征选择的稳定性。实验表明了该方法的有效性，并且使用了少于其他方法的特征数目。
2. 本文从速度和性能的角度出发，提出了分布式的 top-k 特征选择方法。虽然封装式的特征选择方法性能较好，但是时间开销较高，并且又由于强化学习算法的在线交互特性，导致时间花销更大。因而，本文使用分布式的特征选择方法在不影响性能的同时提高了特征选择的速度。接着使用 top-k 的贪心方法，来探索可能存在的更好的特征子集。实验证明，相比原先的特征子集，能够探索到更好的特征。同时，更多的探索势必会花费更加多的时间，因而可以和分布式的方法相结合，使用分布式的 top-k 贪心方法在获得更好的性能的同时，减少了额外的时间消耗。而且可以根据对性能和时间开销的不同权衡，选择效果更好的 top-k 贪心方法或是花费更少时间的分布式方法。
3. 针对封装式方法的耗时过长的问题，使用过滤式的特征选择方法，将特征选择的过程和值函数估计的算法分开。不同于监督学习中的特征选择方法，强化学习没有确定的数据集。因而学习 DQN 中的经验回放机制，生成相应的数据集用于特征子集的生成。然后利用生成的特征子集作为值函数中的属性，仅需一次强化学习的训练过程就能验证特征子集的效果。在实验中，过滤式的方法特征选择的速度要远快于封装式的方法。
参考文献（略）