“机器学习”在工作流模型设定中的应用

《“机器学习”在工作流模型设定中的应用》由会员分享，可在线阅读，更多相关《“机器学习”在工作流模型设定中的应用（3页珍藏版）》请在金锄头文库上搜索。

1、第 23 卷第 l 期 计算机应用与软件 VoI. 23， No. l2006 年 l 月 Computer AppIications and Software Jan. 2006收稿日期： 2004 -05 - l7。孟祥山，讲师，主研领域： CSCW 与信息工程“机器学习”在工作流模型设定中的应用孟祥山 罗 宇（国防科技大学计算机学院 湖南 长沙 4l0073）摘 要 针对目前工作流建模方法的局限性，以及工作流自适应的需求，采用“机器学习”的思想，基于工作流实例信息，提出了动态设定工作流模型的方法。采用隐马尔卡夫模型（ HMM）对工作流模型的结构进行了表示，并定义了相应的合并与分离操作符，

2、为进一步转换成正确、合适的工作流模型提供了支持。关键词 工作流模型 工作流实例 机器学习 HMM 自适应APPLICATION OF“ MACHINE LEARNING” IN THE OR FLO MODEL ENACTMENTMeng Xiangshan Luo Yu（ College of Computer Science & Technology， national Uniuersity of Defense Technology， Changsha Hunan 410073， China）Abstract According to the idea of the“ machine I

3、earning”， a dynamic method of the workfIow modeI enactment based on the informationof the workfIow instances is presented for improving the way of workfIow modeIing and satisfying the reguirement of the workfIow adaptation.The structure of the workfIow modeI is showed with HMM（ hidden markov modeIs）

4、 . Furthermore， the corresponding operators of merging andspIitting are defined for acguiring appropriate HMM. It wiII aIso supports transforming the HMM into the correct workfIow modeI Iater.eywords WorkfIow modeI WorkfIow instance Machine Iearning HMM Adaptation1 引 言目前所实现的工作流管理系统（ WfMS），大都是为了支持严格结

5、构化的业务过程的建模、分析以及设定，即以业务过程的形式化模型为基础（下面称之为工作流模型）。然而，工作流模型的获取是应用中的一个瓶颈，大约需要花费 60% 的开发时间来获得对过程的认识 l。而且所获取的模型中，都难以支持非预测的，或者实际工作中的发展变化情形，即不能对异常，或者过程模型的偏差提供充分的支持。基本上有两种方式来处理这种偏差 2： 工作流模型层次 这意味着需要保存过程知识，使专家在系统之外能够修改相应的工作流模型，这是非常费时的。 工作流实例层次 要么在可补偿的情形下，修改工作流模型的拷贝；要么通过提供高层的命令，让活动者根据上下文来控制特定的工作流实例。而全面、准确的异常预测几乎

6、是不可能的 3。因而，在 WfMS 中集成“机器学习”部件，通过处理人工设定的工作流实例，来提取工作流模型，进一步获取工作流的自适应性是有意义的。2 工作流中的“机器学习”定义 机器学习：给定某类任务 T，与 T 相关的性能 P 和经验 E。计算机程序可以从经验 E 中学习，改善性能 P，从而实现自我完善，则称该程序具有学习能力 4。通常，为了很好地定义一个学习问题，必须要明确这样三个特征：任务的种类，衡量任务提高的标准，经验的来源。对应于工作流模型设定中的学习问题，可描述如下： 任务 T：归纳生成一个更具有适应性的模型。 性能标准 P：工作流的正确执行率。 训练经验 E：已执行的（或者模拟的

7、）工作流实例数据。因而，引入“学习部件”的工作流自适应过程如图 l 所示。图 l 工作流自适应过程当然，它不可能是完全自动化的自适应过程。学习部件可能只观察工作流实例，并将它们概括为一种工作流模型。但它不可能推理一种异常的重要性，或者决定是否某个工作流实例的偏差，对于目标来说是正确的。因而，需要集成人工自适应步骤，其中需要活动者（活动参与者与建模专家）的参与执行。这样，工作流的自适应过程就划分为两个阶段：执行阶段和学习阶段。在执行阶段，如果是一个初始工作，则只定义活动的目标而不考虑控制流，设定是通过活动参与者创建并传送工作条目来 46 计算机应用与软件 2006 年完成的。这意味着此时无需工作

8、流引擎的执行，工作流系统只是作为工作流实例踪迹的提供者来进行服务，否则解释执行由活动者所选择的工作流模型。如果执行过程中出现了偏差（或者称之为异常），则需要活动者的参与，根据上下文进行人工自适应调整，工作流系统保存相应的变化踪迹。在学习阶段又分为两个步骤。首先，根据工作流实例的踪迹，由学习部件进行归纳推导工作流模型。然后，通过相应的过程以及建模专家的参与执行，形成可用于执行的更具有适应性的工作流模型。下面将集中于归纳学习功能的描述，它使工作流的自适应成为可能。3 基于工作流实例的归纳学习工作流实例可表示为三元组 e =（ Ne， fe（）， =e），其中 Ne为结点集合 nl， ni， fe：

9、 NeA 为活动分配函数，它分配一个活动到每个结点， =e为 Ne上的偏序 2。工作流实例表示了一种已结束的业务情形，结点所描述的活动被执行来完成业务，并且偏序描述了它们执行的临时次序。因而，基于实例的归纳学习特征为：假定对于工作流实例的集合 E，找到工作流模型 MO和一个非常近似的表示 M，它可以生成 E。当然 MO不需要存在，它仅是一个模型的假设。对于模型的推导可进一步分解为两个子任务： 工作流结构的归纳 从所观察的实例中概括出一种工作流模型结构，它至少应该涵盖所有观察到的工作流实例。 转换条件的归纳 推导出在可选路由之后结点所需要的可能本地条件，或者一个确定的结点。下面将详细地解释工作流

10、结构的归纳，并限定于顺序的工作流。3.1 隐马尔卡夫模型在更为抽象的观点上，顺序工作流可视为一个事件的序列，因而我们采用对事件建模（识别）的最普通方法：隐马尔卡夫模型（ hidden markov modeIS， HMM）可以基本上被描述为一个有限的自动机，其中的系统状态转换具有一定的概率，并且状态是与一个有一定输出可能性的、符号的有限集合相关联的。表 1 使用 HMM 表示工作流模型工作流模型 HMM活动结点 状态活动 输出符号实例踪迹 输出符号序列集合从实例踪迹中归纳工作流模型 从输出符号序列集合中归纳 HMM表 l 表现了 HMM 如何被用于表达顺序的工作流模型 l。由于工作流实例中的每

11、个活动结点，都已经被明确地（概率为 l）分配有一个活动，所以当应用 HMM 表现工作流模型时，可以得到简化。例如，在公文流转系统中的公文撰写中，所观察到的具体 HMM 集合 E = abcac， abc， abcabc， acabc，其中 a：公文起草， b：审定修改， c：同意批示。则图 2 表示了涵盖它们的HMM 形式。根据工作流实例的定义，应该表示为无环的有向图，而现在一个活动 Ai可能在一个实例 e 中不止一次地出现。因而首先假定允许环的存在，通过增加一个下标，来简单地区别在一个实例中同一活动的发生。那么就可以把同一活动的不同发生作为不同活动来对待，直到已经确定了模型的边为止。然后，属

12、于同一个活动的所有结点被合并成一个结点，它将继承所有被合并结点的边。那么，从所执行的工作流踪迹中归纳出工作流模型的问题，就相应于从大量所观察到的输出符号序列中发现合适的 HMM表示。图 2 涵盖工作流实例的 HMM 形式3.2 模型的合并特定的 HMM 所包含的输出符号观察序列，就是工作流执行的一条路径，它的数目会随着所观察到的工作流实例数目而增长。因而，需要对简单归纳所得到的 HMM 进行合并操作，使其能涵盖更多的实例。下面定义 Merge 操作符。它将所观察到的特定 HMM，具有相同输出符号的状态进行合并；而将具有不同输出符号的状态作为分支加入到模型结构中。设 E = el， e2， en

13、，其中 ei为观察序列 gstartglg2 gmgend的输出符号串。 e 为 Merge 操作所得到的 HMM。则 Merge 的具体操作如下：（ l）若 e 为空，则使 e = el，并进行检查，若有 gk， gh。el，且gk= gh（它们所对应输出的符号相等），则对它们运用 Merge操作。（ 2）若 e 不为空，则取 ei。E， gh。ei， h =l， 2， m。! 若有 gh= gk， gk。e，则对它们运用 Merger 操作； 若 gh一gk， gk。e，则回到 ei合并到 e 中的上一状态，使 gh成为它的新分支。（ 3）取下一符号串，重复步骤（ 2），直到最后一个为止。

14、经过对所观察的特定 HMM 集合反复进行 Merge 操作，就可以得到合适的 HMM 表示。在合并过程中，转换的概率 ! 是通过经验计数来估计的，即如果走过某条路径的工作流实例越多，则该条路径上的状态转换概率就越大，它应该就是正常工作所需要的工作流模型，而小概率的分支路径就可能对应于异常的情形。3.3 模型的分离根据 Merge 操作符的定义以及我们的假定，当在反复进行合并操作时，我们会遇到一个问题：所生成的 HMM 中，会有大量状态是与同一种符号相联系的，特别是有回返的指向而形成环。因而，在 HMM 的空间中，从特定的模型到一个只有少数状态与同一个符号相关联的模型间的距离是很大的（模型之间的

15、距离，是根据在一个模型转换到另一模型中，所需要合并或者分离的操作符数目而定的）。因为归纳出的 HMM 准确地包含了每个所观察到的输出符号的状态，并且结合了所观察到的每种分支转换。虽然所得到的 HMM 涵盖了所有的观察，但它也同时涵盖了很多没有观察到的状态序列，如上例中的 acacac， abcacabc等。如果我们把最一般化的 HMM 作为一种工作流模型，那么 第 1 期 孟祥山等：“机器学习”在工作流模型设定中的应用 47 将意味着，尽管有一个很紧凑的模型，但它同时允许有很多从来没有观察到的活动序列，可能有一些对于实际工作并不是合适的。因而，为了获得一种更为合适的工作流模型，需要进行适当的分

16、离操作。另外，工作流建模语言都要求无环的有向图，在随后的模型转换中也需要进行分离。分离操作符 Split 的定义如下：设 e 为观察序列 gstartg1g2gmgend的输出符号串，且为 Merge 操作所得到的 HMM。 gi为 gj的直接后继，若 i j，则复制 gigi +1 gj，并将它们插入到 gj与gj +1之间而成为一个新分支，删除 gj指向 gi的边，然后调整序列下标。经过反复运用 Spiit 操作符，就可以使所得到的 HMM 成为无环的有向图。图 3 即是对图 2 中的 HMM 运用 Spiit 操作所得到的结果。图 3 Spiit 操作所生成的 HMM3. 4 条件的归纳通过归纳学习，返回了所观察到的工作流实例结构的一种紧凑模型。在该结构中，通过概率描述了所有非确定的转换。对于 WfMS 来说，这当然是不充分的模型。为了下一个转换的选择，当前大多数的 WfMS 都允许建模者基于工作流实例的属性来说明简单的条件