通过学习与规划的结合实现数据驱动的可操作性

今天，FCS给大家分享一篇人工智能专栏论文——《Achieving data-driven actionability by combining learning and planning（通过学习与规划的结合实现数据驱动的可操作性）》的读者给我们带来的论文阅读笔记。如果您也同样对这篇论文感兴趣，或者也想把您阅读我们期刊论文的感受分享给更多的小伙伴，欢迎在文后留言或者与我们联系。

原文信息：

Achieving data-driven actionability by combining learning and planning

Frontiers of Computer Science,2018,12(5): 939-949

Qiang LV, Yixin CHEN, Zhaorong LI, Zhicheng CUI, Ling CHEN, Xing ZHANG, Haihua SHEN

01

简介

目前在机器学习领域，对于支持向量机、人工神经网络、随机森林等模型的研究已经极大地提升了模型的准确度与效率。但是在许多问题中，人们需要的不仅仅是一个判别模型，而是需要模型能够规划出出一系列步骤，来达到预期的目标。本文所做的研究，是通过一种结合学习与规划的方法，能够对输入样本进行一系列的变换操作，使样本在学习模型中可以达到预期的输出。

以随机森林（random forest）为例，尽管这种复杂的学习模型可以达到很高的精度，但是其缺乏可操作性（actionability），只能固定地对输入进行判别。

本文提出的方法分为离线预处理（offline phase）与在线规划（online phase）两部分，将一个近似最优解规划（sub-optimal actionable planning， SOAP）问题进行了两次SAS+与WPMax-SAT形式的变换。

02

背景知识

2.1 随机森林

随机森林（Random Forest）是一种常用的分类模型，每一个随机森林模型由多个独立的决策树（Decision Tree）组成。相较其他的常见学习模型，随机森林能够很好地处理缺失值与多类型属性样本，同时鲁棒性也更高，因此应用相当广泛。

对于数据集,随机森林将输入向量映射到标签集合上，写作。对于给定的输入向量，输出结果是标签集合中任意一个标签的概率可表示为：

其中是决策树的权重，时取1否则取0的二值函数。随机森林对于输入样本的分类为：

随机森林的生成方式为：

（1）对训练集进行次有放回采样；

（2）根据采样样本集，训练决策树模型，在训练过程中只采用样本的一部分特征；

重复上述过程D次，生成的全部D个决策树构成随机森林模型。

2.2 SAS+形式

在规划问题中，以往有两种传统的问题描述形式：STRIPS（STanford Research Institute Problem Solver）与PDDL（Planning Domain Definition Language）。SAS+是近年来较为流行的一种新型表述形式，使用一组多值状态变量（state variable）表示。每一个的值域都是有穷的。状态是对全部变量的一组赋值，全部状态的集合用表示。

（1）变换（Transition）

对于一个上述的状态变量，变换可以定义为一个三元组，写作。当且仅当时，变换对于状态才是可用的(applicable)。将变换作用于状态后得到的新状态记作，则有。

对于一个变量，将所有针对的变换记作，例如对于全部。

（2）互斥变换（Transition mutex）

对于两个不同的变换与，若至少其中之一是机械变换（mechanical transition）且，则称这两个变换是兼容的（compatible）；否则即为互斥的（mutually exclusive）。

（3）动作（Action）

一个动作由一系列彼此不互斥的变换组成。如果一个动作中的全部变换对状态是可用的，则对是可用的（applicable）。每个动作都伴随一个代价（cost）。

（4）SAS+规划（SAS+ planning）

一个SAS+规划问题可由一个四元组表示，其中：

ž是一系列状态变量。

ž是一系列动作。

ž是初始状态。

ž是目标状态集合，其中每个目标状态都是对于一部分状态变量赋值。当一个状态的赋值与一个中的赋值均一致时，则是一个目标状态。

（5）互斥动作（Action mutex）

对于两个不同的动作与，当且仅当下列两条件满足至少之一时，称其为互斥的：

ž 存在非普通变换（non-prevailing transition）满足且。

ž 存在彼此互斥的两变换与。

对于一个动作集合，当每个动作对状态是可用的且中动作彼此不互斥，则称对是可用的。将状态应用动作集合中全部动作后的结果称为。

（6）解决方案规划（Solution Plan）

对于一个SAS+问题，一个解决方案指的是一个序列，其中是一系列动作集合，同时有。

在一个解决方案中，多个非互斥动作可以在同一时刻作用。指以任意顺序将中的全部动作作用于状态。本文旨在寻找一个能够最小化总动作代价（total action cost）的解决方案。

03

近似最优解规划问题

对于一个随机森林模型与一个输入向量，近似最优解规划（SOAP）问题指的是通过一系列动作（action），将转换为一个新的输入向量，从而可以通过随机森林模型得到希望的输出。而这些动作均包含一个代价，因此SOAP问题同时需要最小化总动作代价。

上文中提到样本的样本属性由可以更改的软属性（soft attribute）与不可更改的硬属性（hard attribute）组成。

SOAP问题可以用三元组来表示，是随机森林模型，是输入向量，是一个分类标签，是一系列动作。而SOAP问题的目标则是规划一个动作集合，从而满足：

其中是动作的代价，为一个常数，是2.1节中定义的输出，是将中的动作作用于后的新向量。

下图中的随机森林包含两个决策树以及三类属性，其中是硬属性，其余两种为软属性。对于输入向量，随机森林的输出为0。而目标则是对输入进行一系列变换，使新输入向量在随机森林的输出为1。例如可以将转换为。

04

对近似最优解规划问题的规划方式

SOAP问题也已被证明是NP-hard问题，因此不能通过寻找最优解的算法来解决SOAP问题。本文提出了一种基于规划的解法，该解法分为两阶段。

4.1 离线预处理阶段

在离线预处理阶段，本文通过构建有向图，为每个训练样本构建一个合适的目标状态。

4.1.1样本属性空间划分

对于随机森林，可以通过以下规则对样本的每个属性进行划分：

（1）如果是离散属性且共有类，则将分为类；

（2）如果是连续属性而且在的全部决策树中共有个分支节点，则将分为类。

以第3节中的例子为例，属性被划分为。

在明确了属性的划分后，对于输入，是属性划分出的类别，是取值的对应划 分下标，可以将表示为SAS+状态。

4.1.2 路径规划与启发式搜索

上文提到，本文通过动作图（action graph）来规划问题的解。对于SOAP问题，动作图可以表示为

。其中是一系列转换后的状态。由一系列边组成，其中的每条边代表一个动作，且有，边权为。

因此，SOAP问题可以转换为寻找图中从到目标状态的最短路径。对于训练集，可以通过启发式搜索（heuristic search）寻找一个较优解。

启发式搜索采用估值函数。是到达的总代价，如果，且，那么。当时，启发式函数，否则。

对于任意满足的，估值函数为。因为目标是达到，度量的是与目标之间的距离。是控制参数，在本文的实验中，设置为全部动作代价的均值。

上述函数定义完毕后，即可根据现有的启发式搜索算法进行搜索。本文同时从算法的角度论证了可以在有限时间内结束搜索并返回结果。

在离线预处理阶段结束后，对于每个以及对应的，都规划出了一个合理的较优目标状态。同样以第3节的例子为例，取输入为，对应的初始状态为，一个最优解即为，其中

，

目标状态为。

4.2在线规划阶段

当预处理阶段完成后，本文提出了一种类kNN算法，以训练集中对应的规划方案，来解决输入样本的规划问题。

4.2.1 样本相似度

为了度量输入样本与训练样本之间的相似程度，本文提出了特征相似度（feature similarity）度量方案。状态相似度可定义为：

其中是决策树在随机森林中的权重，是样本在某特征下的相似度。特殊的是，当存在是硬属性时，两状态的相似程度为0，因为无论采取任何变换，都无法修改硬属性使得两状态相同。越大意味着两状态相似程度也越高。

4.2.2 SAS+形式表示法

为了进一步对输入样本进行规划，现在要将SOAP问题转换为SAS+形式（SAS+ formulation）表示。对于SOAP问题，可以定义对应的SAS+问题为：

ž是一系列状态变量，每个变量的值域都是有穷的，是第i个属性的划分数目；

ž是一系列SAS+动作，直接从中变换而来；

ž是变换后得到的状态；

ž 令为与相似度

最高的K个邻居，对应的转换目标状态分别为。SAS+问题的目标即为。其中K为自定义参数；

以先前的例子为例，如果我们预处理阶段得到了三个初始状态，其对应的转换目标为。在在线规划阶段，对于输入样本，对应的状态为。令权重，则可计算出。当时的两个最接近邻居是和，那么SAS+的目标即为。

4.2.3WPMax-SAT问题

至此，我们已经将原问题转化为求解一个如上定义的SAS+问题。由于传统的SAS+问题解法无法同时兼顾最小化代价函数，达到最优效果，文章采用了一种基于SAT的方法。

本文采用的方法基于有约束的SAT解法，将SAS+问题以WPMax-SAT（weighted partial Max-SAT）的形式表示，最终规划出合适的解法同时达到最小化代价函数，或证明条件不可满足。

对于上文的，可以定义WPMax-SAT问题，其中为变量集合，为子句集合。变量集合与子句集合分别由SAS+下的变换、动作等元素以及其间的互斥关系构成。

通过以上转换后，原始问题已经转换为MaxSAT问题，从而可以使用任一种MaxSAT问题解法进行求解。

05

总结

本文提出了一种将随机森林等学习模型与启发式搜索等路径规划算法相结合的方法，对原问题形式进行分别SAS+形式与SAT形式的转换进行求解。克服了传统算法可操作性不强、特化效果较差以及无法很好优化代价函数的缺点。

文章中根据提出的方法，在多数据集上进行了实验，得到了以下结果：

可见本文采用的方法达到了执行速度与准确度的优化，代价函数也显示取得的结果相对更优，展现出本方法在解决SOAP问题上的效率。

注：本文为该读者的阅读笔记，未经原论文作者和FCS期刊审读。仅供广大读者参考。

Frontiers of Computer Science

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社出版、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”。