引用本文

姜秉序, 宿翀, 刘存志, 陈捷. 融合混合知识与MCTS的针灸排序方案设定方法. 自动化学报, 2020, 46(6): 1240−1254 doi: 10.16383/j.aas.c180120

Jiang Bing-Xu, Su Chong, Liu Cun-Zhi, Chen Jie. Acupuncture sequential scheming method with hybrid knowledge and MCTS. Acta Automatica Sinica, 2020, 46(6): 1240−1254 doi: 10.16383/j.aas.c180120

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180120

关键词

混合知识，蒙特卡洛树搜索算法，序列决策，针灸穴位 

摘要

传统的序列决策方法旨在对决策过程与决策步骤进行建模, 以求解得到最优的决策序列. 然而, 序列决策建模过程对目标函数的确定性要求高, 且序列搜索的算法多以深度优先或广度优先等遍历搜索为主, 鲜有考虑搜索过程的随机性. 蒙特卡洛树搜索算法(Monte Carlo tree search, MCTS)虽然适合求解随机序列搜索问题, 但目前仅应用于博弈型搜索过程, 鲜有探讨需要专家参与的知识约束序列决策的搜索策略, 另外, 传统MCTS算法往往存在搜索范围过大、收敛不及时等问题. 为此, 提出一种融合群决策经验型知识和部分确定型决策序列片段的混合知识约束的MCTS 序列决策方法, 并给出了详细的求解流程. 最后, 将所提方法应用于一类中风后吞咽功能障碍针灸穴位排序方案制订问题, 给出了融合混合知识与MCTS的针灸排序方案设定方法, 并与其他方法进行对比, 验证了所提方法的可行性和有效性, 为年轻医师的针灸方案制订技能的标准化培训工作奠定了方法基础.

文章导读

传统的序列决策大多解决对时间序列问题的预测和对工艺工序的顺序决策问题. 在各类装配序列生产中, 序列决策问题主要存在于工件加工工序[1-3]、 投资节点的投资决策等[4-5]问题中. 然而, 传统的序列决策方法往往需要明确的决策节点与决策目标, 常见的搜索算法(如: 深度优先、广度优先等)缺乏对序列决策问题中的随机性的考虑. 特别地, 针对专家知识为约束的序列决策问题, 尤其是决策步骤排序问题, 尽管目前有强化排序学习等方法[6-7], 但此类方法都需要大量完整标签样本、 辅助序列决策的学习过程. 因此, 传统序列决策方法在可参考完整样本不足的情况下, 对于基于部分先验知识的决策序列能力, 还有待提升.

针对序列决策问题的搜索算法, 一直是该领域的研究热点. 目前解决序列决策问题的搜索方法中, 大致可以分为启发式搜索[8-9]和盲目搜索[10]两种. 其中, 启发式搜索是利用问题拥有的启发信息来引导搜索, 达到减少搜索范围, 降低问题复杂度的目的; 而盲目搜索则是按照固定的规则对目标进行搜索, 具有遍历的特性.

此外, 当需要搜索的数据非常大的时候, 传统启发式和盲目搜索方法得到的搜索树结构异常复杂, 算法用时过长, 收敛很慢, 且易陷入局部极值.

然而, 蒙特卡洛树搜索算法(Monte Carto tree search，MCTS)的诞生, 提供了一种在决策空间中选取随机样本、然后根据阶段性决策结果构建搜索树, 并在给定域中寻求最佳决策序列的方法. 由于其在计算机围棋中取得了巨大的成功, 对人工智能领域产生了深远的影响. 目前, MCTS更多地应用在多阶段交互甚至多角色的博弈型决策中[11-14], 尤其在计算机围棋领域[15-17], 取得了很优异的成绩. 此外, 在众多形式的MCTS中, 尤其以上限置信区间算法(Upper confidence bound apply to tree, UCT) 为内核框架的MCTS算法性能最为常用, 它对反向传播阶段的胜率进行平均, 并基于胜率的上限来选择搜索的方向[18]. 此外, Lin[19]针对基于正常UCT算法往往难以给出较好的搜索结果这一问题, 提出了Lin-UCT算法, 并从多个角度进行算法改进前后的比较. 此算法主旨并不是寻求“全局最优解”, 而是“当前决策阶段的可行搜索最优解”.此外, 当空间复杂度很大时, 运用MCTS算法搜索深度或终止条件任意性的特点[20-21], 来得到可接受的决策解. 因此, MCTS方法以其搜索过程的随机性和终止时间的任意性, 为构建先验知识不完全情况下的序列搜索奠定了坚实的理论基础.

为加速序列决策的求解过程, 建立混合先验知识约束的搜索方法是一个有效的途径. 目前众多的复杂序列决策问题(例如: 复杂医学治疗方案生成过程), 往往存在决策机理难以全面掌握, 且序列决策中的每个决策节点与最终决策解呈非线性关系, 阶段性决策结果难以量化评价等难点. 因此, 面向需要多人专家参与的序列决策问题, 多属性群决策方法以其专注于群体专家经验的提取与集结[22-24]的优势, 显然是构建部分先验知识的有效途径. 该方法尤其适用于为含专家参与的序列决策求解问题提供先验知识, 并为决策序列的搜索方向进行引导, 有效减少搜索时间和搜索空间.

特别地, 常见的中医针灸诊疗方案制订过程是一类典型的序列决策问题. 在众多中医针灸古籍和当代文献中, 针对针灸机理的研究主要集中在单个穴位对疗效[25-26]的改善中, 只是对穴位, 针灸方法进行了简单的数据统计. 针对同一病症的多个穴位的针刺排序方案, 目前主要是专家经验, 并没有对专家经验知识进行梳理和数字化描述, 且未针对特定病症提出相关的穴位排序确定的方法, 科学性有待提升. 然而, 关于医学中的序列决策问题, 大多集中在资源调度方面, 例如, 关于医疗资源的调度[27]、关于医护人员的调度[28], 鲜有关于针灸排序对治疗效果的量化论述. 目前的中医针灸方案, 虽然治疗效果稳定, 但是主要依赖专家经验, 缺乏灵活性和量化数学的基础, 使得年轻医生难以学习和继承针灸方案制订的精髓.

所谓针灸“治疗序列”的决策问题, 从数学角度可以归结为“治疗序列上的划分优化问题”, 这与传统集合上的划分及评价有所不同. 面向传统集合划分优化方面的研究, 文献[29-31]针对寻找最优联盟系统问题, 分别提出了SCS (Search of coalition structure)算法、EOCS (Effective optimal coalition structure)算法和ODP-IP (Optimal dynamic programming-IP)算法, 提高了搜索速度; 文献[32]描述了关于图形联盟游戏中连续决策问题, 利用价值加强定义优劣势; 文献[33] 尝试解决组合拍卖中的NP完全问题. 本文所涉及的“治疗序列的划分优化”, 相对传统的“集合划分优化”而言, 面临几个难点: 1)治疗序列生成的规则不明确, 不能完全已知. 且由于针灸学的特殊性, “口口相传”的专家经验占主导作用. 这种影响“治疗序列”生成的约束, 往往是非结构化的. 2)治疗序列有效性的评价, 目前也未能形成统一标准, 未能明确结构化描述, 往往依赖专家经验和患者的主观感受进行评价. 在中医界对针灸的作用机制未能完全阐明的情况下, 这也是制约针灸医学发展的一大瓶颈. 3)传统的联盟结构缺乏对子节点优先度位置的论述. 针对上述问题, 本文尝试结合确定性专业知识和专家经验作为判断规则, 构建出一种混合智能, 以确定治疗序列的生成.

受上述讨论的启发, 在获取搜索过程所需量化先验知识的前提下, 本文提出了一种基于混合知识的蒙特卡洛树搜索的序列决策方法, 旨在展示目标函数不明确且需要专家参与的序列决策问题中可行决策解的生成过程. 最后以一类面向中风后吞咽障碍的针灸穴位排序方案生成过程为例, 讨论了本文所提方法的应用. 本文结构安排如下: 第1节介绍基于混合知识的决策序列评价方法; 第2节给出基于混合知识的蒙特卡洛树搜索序列决策方法; 第3节以面向吞咽功能障碍针灸排序方案生成过程为实例, 验证所提序列决策方法的正确性, 并与传统搜索方法进行对比, 验证所提方法的优势; 第4节给出结论与工作展望.

图 1  完整决策序列的评价流程图

图 2  序列分割示意图

图 3  传统MCTS流程图

为解决以专业知识和专家经验为主的序列决策问题, 本文给出获取确定型知识与经验型知识的统计与群决策算法. 为解决序列的评价问题, 本文给出了子序列片段以及决策序列分割的定义, 进而提出了基于子序列片段优先度的完整序列的评价方法. 之后又在评价模块中添加反馈矩阵, 用以模拟反馈的情况.

此外, 基于上述评价方法, 本文给出了基于群决策经验型知识和部分确定型知识的混合知识约束的MCTS-max序列决策方法, 并详细描述该序列决策的流程. 构建了以混合知识引导搜索方向的序列决策方法, 并使计算机具备对专家参与的目标函数不明确的序列决策问题的自动求解能力, 实现了决策智慧的传播与继承功能, 是一种专家经验和决策算法的混合智能.

为验证本文所提方法的正确性和有效性, 以一类面向卒中后吞咽障碍康复中的针灸穴位排序问题展开讨论. 我们定义了一种“治疗序列”, 不同于传统数学中联盟结构的划分和组合优化, 是一种矢量性, 含有子节点优先度增益, 且其生成受知识约束节点集合, 属于针灸所特有的序列. 之后通过统计和群决策算法对脑卒后中风吞咽障碍的针灸治疗方案的众多穴位进行了量化处理. 最后通过本文所提基于混合知识的MCTS-max序列决策方法获得最终的治疗方案. 并将其与传统MCTS方法、基于混合知识的遗传算法和贪心算法的序列决策方法进行对比, 从算法复杂度、收敛特性等角度说明了所提方法的优缺点.

需要说明的是, 本文的工作仍然是基础性的, 在未来工作中, 有一些问题需要进一步研究, 例如: 1)本文所提序列决策是基于离线的混合知识构建的, 未来将研究一种知识在线更新的动态序列决策方法; 2)在治疗序列生成方面, 本文的反馈矩阵只是简单的单位对角阵, 未来将充分考虑“反馈矩阵”与疗效评价高度相关这一事实, 站在人工智能的角度, 研究基于疗效评价的反馈矩阵计算方法; 3)本文的针灸疗效评价, 仅以医生评价和患者主观感受的简单数学描述为主, 关于疗效评价的科学性有待提升, 未来将尝试引入核磁共振影像在针刺作用下的患者生理反应图像作为参考; 4)传统中华医学博大精深, 由于本文专业视野的局限性, 调研范围有限, “专业知识”及“专家知识”不够完整. 未来, 医学证据的搜索要更广泛, 经验性的知识库要更全面; 5)在研究面向吞咽功能障碍针灸康复治疗的动态序列决策问题中, 我们还要着力解决多专家经验知识的不确定性与序列决策结果之间的量化建模问题, 以及含多操纵量(例如, 除针灸之外的其他治疗手段, 包括物理治疗、按摩、冰刺激等)的复杂治疗序列的搜索与评价等问题.

作者简介

姜秉序

北京化工大学信息学院硕士研究生. 主要研究方向为智能决策. E-mail: yizhoutanjian@126.com

宿翀

北京化工大学信息学院副教授. 主要研究方向为人工智能, 情感计算和智能医疗. 本文通信作者.E-mail: suchong@mail.buct.edu.cn

刘存志

北京中医药大学东方医院副院长. 主要研究方向为针灸的临床疗效评价与作用机理研究.E-mail: lcz623780@126.com

陈捷

北京中关村医院针灸推拿科主治医师. 主要研究方向为中医学, 针灸推拿学及智慧医学. E-mail: chenjie0128@126.com