部分可观察设置中的反馈驱动的决策支持

摘要

本公开涉及部分可观察设置中的反馈驱动的决策支持。描述了一种被称为带有观察的上下文注意游戏机(CABO)的新颖表述，其中仅有限数量的特征可由学习者访问。本发明适用于许多问题，包括在不可能揭示整个特征集的临床环境和对话系统中出现的问题。本发明使用新颖的算法来调整被称为汤普森采样的标准上下文游戏机算法，我们称为带有观察的上下文注意汤普森采样(CATSO)。包括实验结果以证明其有效性，包括证明所公开的新颖方法在多个现实生活数据集上的优势的遗憾分析和实证评估。

说明书

技术领域

本申请总体上涉及改进的数据处理装置和方法，并且更具体地涉及使用强化学习的机器学习系统。

背景技术

上下文游戏机(bandit)问题是广泛研究的多臂游戏机问题的一种变体，其中，在每次迭代中，在选择手臂之前，代理观察N维上下文或特征向量，并使用它预测进行游戏的下一个最佳手臂。代理使用此上下文以及过去进行游戏的手臂的奖励来选择要在当前迭代中进行游戏的手臂。随着时间的推移，代理的目标是收集关于上下文向量和奖励之间的关系的足够信息，以便它可以通过查看对应的上下文来预测进行游戏的下一个最佳手臂。

发明内容

本发明是一种被称为带有观察的上下文注意游戏机(CABO)的新颖表述，其中仅有限数量的特征可由学习者访问。本发明适用于许多问题，包括在不可能揭示整个特征集的临床环境和对话系统中出现的问题。本发明使用一种新颖的算法来调整被称为汤普森采样的标准上下文游戏机算法，我们称为带有观察的上下文注意汤普森采样(CATSO)。包括实验结果以证明其有效性，包括证明所公开的新颖方法在多个现实生活数据集上的优势的遗憾分析和实证评估。本申请参考了在与之一起提交的信息公开声明中列出的非专利文献的若干教导。每个非专利文献的教导在此以引用的方式整体并入本文。

本发明公开了一种反馈驱动的方法，其可以利用已知特征的小的固定子集来选择共同最好地影响(inform)决策过程的附加未知特征。本发明包括以下特征：利用可观察特征值和特征预算大小来决定使用强化学习(RL)策略揭示哪些最初不可观察特征，以及利用所有观察到的特征来使用RL策略做出决策并使用对建议的动作/决策的反馈来更新RL策略。

更具体地，本发明是用于使用强化学习系统中的有限特征进行决策的系统、计算机程序产品和方法。从获得与最初可观察特征列表、最初不可观察特征列表以及与由强化学习代理与之交互的计算机系统有关的可观察特征的最大数量相对应的最初可观察特征值开始。最初可观察特征值是数字特征值、结构特征值、字符串值和图形值中的一个或多个。在一个示例中，最初可观察特征表示患者病史，并且最初不可观察特征是可用的患者测试。在另一示例中，最初可观察特征是语音对话话语和用户历史中的一个或多个，并且最初不可观察特征是可用响应。在又一示例中，最初可观察特征是用户信息历史中的一个或多个，并且最初不可观察特征是可用响应。

强化学习代理从动作集合中选择动作，以使计算机系统从一个状态转移到另一状态，由此将动作的选择建模为强化学习策略。接下来执行已被选择的动作以使计算机系统从一种状态转移到另一种状态。使用最初可观察特征值和可观察特征的最大数量来选择使用用于特征选择的第一强化学习策略揭示哪些最初不可观察特征。接下来，使用最初可观察特征以及已被揭示的最初不可观察特征，使用用于决策选择的第二强化学习策略从动作集合中选择下一动作。基于已被选择的下一动作，使用反馈来更新第一强化学习策略和第二强化学习策略。在可设置的迭代次数上重复上面的步骤。一个示例中将这些步骤应用于上下文游戏机算法，但是在其他示例中，可以考虑其他算法。

在另一个示例中，本发明被应用于单阶段或多阶段示例。在平稳数据的情况下，要求保护的发明还提供获得特征的总数、要在可设置数量的阶段上观察的期望特征的总数。上面的步骤包括使用上下文组合游戏机方法接着使用上下文游戏机方法来选择特征的子集的另一个步骤。可以重复此附加步骤以进行一次以上的迭代或可设置次数的迭代。

在非平稳数据的情况下，要求保护的发明还提供获得特征的总数、要在可设置数量的阶段上观察的期望特征的总数。上面的步骤包括另外两个步骤：使用上下文组合游戏机方法接着使用上下文游戏机方法来选择特征的子集，以及使用由GP-UCB算法计算的衰减参数来更新第一强化学习策略和第二强化学习策略中的至少一个。像平稳情况一样，可以重复这些附加步骤以进行一次以上的迭代或可设置次数的迭代。

附图说明

当结合附图阅读时，通过参考对说明性实施例的以下详细描述将最好地理解本发明以及优选的使用模式及其进一步的目的和优点，其中：

图1是其中可以实现本发明的各方面的分布式数据处理系统的示例图；

图2是其中可以实现本发明的各方面的计算设备的示例框图；

图3描绘了本发明的带有观察的上下文关注汤普森采样(CATSO)的示例功能框图；

图4是使用CATSO方法和平稳数据集的实验结果的表；

图5是使用CATSO方法和非平稳数据集的实验结果的表；

图6是针对平稳Covertype数据集与加权TRSC(WTRSC)方法进行比较的实验结果图；以及

图7是针对非平稳Covertype数据集与WTRSC方法进行比较的实验结果图。

具体实施方式

上下文注意游戏机是基于部分可观察上下文来预测哪个手臂进行游戏的上下文游戏机。上下文注意游戏机的挑战是不可能观察到完整的上下文，并且一开始仅允许代理观察信息的小的子集。例如，在临床环境中，医生在医学检查期间对患者信息进行第一阶段的探索，使用此信息来利用医学测试探索更多特征，然后决定治疗计划。在此临床环境下，在检查期间观察到特征的小的子集，并且未观察到所有可能的测试的结果。永远不可能知道真正的标签或最佳可能的治疗计划，只可能知道对选择的治疗计划的奖励或反馈。进行所有可能的测试即使不是完全不可能的，至少也是不切实际且昂贵的，需要智能地选择未观察到的上下文特征以最大化奖励。注意，当有两个以上的治疗计划或潜在的响应时，基本事实(ground truth)是不可用的。医生永远不可能知道“最佳治疗”或“最佳响应”，只可能知道患者或用户对所选择的动作的反馈。

人工智能(AI)代理的多技能编排中可能会出现类似的问题。在对话编排中，用户的查询通常被指引到多个域特定的代理，并且返回最佳响应。在此情况下，可以立即观察到查询，但是无法观察到特征集或来自域特定的代理的响应。对于多用途对话系统(比如个人家庭助理)，检索特征或来自每个域特定的代理的响应在计算上是昂贵的或棘手的，有可能导致不良的用户体验，从而再次强调了有效特征选择的必要性。使用查询来最后挑选出潜在的响应是必要的。

确定如何利用已知特征的小的固定子集来选择共同最好地影响决策过程的附加未知特征是常见的问题。一个挑战是当基本事实不可用时使此决策过程自动化。

上下文注意游戏机是基于部分可观察上下文来预测哪个手臂进行游戏的上下文游戏机。公开了一种上下文注意游戏机的特殊情况，被称为“带有观察的上下文注意游戏机”(CABO)，其中不可能在每次迭代中观察到完整的上下文向量，但是可以观察到上下文特征的小的子集，并且可以揭示固定数量的未观察到的特征。对于所有迭代，可以揭示的未知上下文特征的数量是固定的，并且代理可以探索此给定大小的未观察到的上下文的任何子集。此问题的目标是在每次迭代中选择最佳特征子集，以最大化总体奖励，在此设置下，这涉及探索特征空间和手臂空间两者。

公开了一种上下文注意游戏机问题CABO的新变体，它是由信息访问受限的实际应用启发的。还公开了用于CABO问题的平稳和非平稳设置两者的两种新算法，以及证明我们提出的方法在一系列数据集和参数设置上的优势的实证评估。

因此，可以在许多不同类型的数据处理环境中利用说明性实施例。为了提供用于描述说明性实施例的具体元件和功能的上下文，下面提供图1和图2作为示例环境，其中可以实现说明性实施例的各方面。应当理解，图1和图2仅是示例，并不旨在断言或暗示对于其中可以实现本发明的各方面或实施例的环境的任何限制。在不脱离本发明的精神和范围的情况下，可以对所描绘的环境进行许多修改。

图1描绘了示例分布式数据处理系统的图示，其中可以实现说明性实施例的各方面。分布式数据处理系统100可以包括其中可以实现说明性实施例的各方面的计算机网络。分布式数据处理系统100包含至少一个网络102，该至少一个网络是用于在分布式数据处理系统100内连接在一起的各种设备和计算机之间提供通信链接的介质。网络102可以包括连接，诸如有线、无线通信链接或光缆。

在所描绘的示例中，服务器104和服务器106与存储单元108一起连接到网络102。此外，客户端110、112和114也连接到网络102。这些客户端110、112和114可以是例如个人计算机、网络计算机等。在所描绘的示例中，服务器104向客户端110、112和114提供诸如引导文件、操作系统映像和应用程序之类的数据。在所描绘的示例中，客户端110、112和114是服务器104的客户端。分布式数据处理系统100可以包括附加的服务器、客户端和其他未显示的设备。

在所描绘的示例中，分布式数据处理系统100是因特网，其中网络102表示使用传输控制协议/因特网协议(TCP/IP)协议套件彼此通信的网络和网关的全球集合。因特网的核心是主要节点或主机计算机之间的高速数据通信线路的骨干，其由路由数据和消息的数千个商业、政府、教育和其他计算机系统组成。当然，分布式数据处理系统100也可以被实现为包括许多不同类型的网络，诸如例如内联网、局域网(LAN)、广域网(WAN)等。如上所述，图1旨在作为示例，而非作为对本发明的不同实施例的体系结构限制，并且因此，图1中所示的特定元件不应该被认为是对于其中可以实现本发明的说明性实施例的环境的限制。

图2是其中可以实现说明性实施例的各方面的示例数据处理系统的框图。数据处理系统200是计算机的示例，诸如图1中的客户端110，实现本发明的说明性实施例的过程的计算机可用代码或指令可以位于该计算机中。

在所描绘的示例中，数据处理系统200采用包括北桥和存储器控制器集线器(NB/MCH)202以及南桥和输入/输出(I/O)控制器集线器(SB/ICH)204的集线器体系结构。处理单元206、主存储器208和图形处理器210连接到NB/MCH 202。图形处理器210可以通过加速图形端口(AGP)连接到NB/MCH 202。

在所描绘的示例中，局域网(LAN)适配器212连接到SB/ICH 204。音频适配器216、键盘和鼠标适配器220、调制解调器222、只读存储器(ROM)224、硬盘驱动器(HDD)226、CD-ROM驱动器230、通用串行总线(USB)端口和其他通信端口232以及PCI/PCIe设备234通过总线238和总线240连接到SB/ICH 204。PCI/PCIe设备可以包括，例如，以太网适配器、附加卡和用于笔记本计算机的PC卡。PCI使用卡总线控制器，而PCIe不使用。ROM 224可以是例如闪存基本输入/输出系统(BIOS)。

HDD 226和CD-ROM驱动器230通过总线240连接到SB/ICH 204。HDD 226和CD-ROM驱动器230可以使用例如集成驱动电子设备(IDE)或串行高级技术附件(SATA)接口。超级I/O(SIO)设备236可以连接到SB/ICH 204。

操作系统在处理单元206上运行。该操作系统协调并提供对图2中的数据处理系统200内的各种组件的控制。作为客户端，操作系统可以是商业上可获得的操作系统，诸如

作为服务器，数据处理系统200可以是例如运行高级交互执行

用于操作系统、面向对象的编程系统以及应用程序或程序的指令位于诸如HDD226之类的存储设备上，并且可以被加载到主存储器208中以由处理单元206执行。处理单元206可以使用计算机可用程序代码来执行本发明的说明性实施例的过程，该计算机可用程序代码可以位于诸如例如主存储器208、ROM 224之类的存储器中，或者例如位于一个或多个外围设备226和230中。

诸如图2所示的总线238或总线240之类的总线系统可以包括一个或多个总线。当然，可以使用任何类型的通信结构或体系结构来实现总线系统，该通信结构或体系结构提供在附接到该结构或体系结构的不同组件或设备之间的数据传输。通信单元(诸如图2的调制解调器222或网络适配器212)可以包括用于发送和接收数据的一个或多个设备。存储器可以是例如主存储器208、ROM 224或诸如在图2的NB/MCH 202中找到的高速缓存。

本领域普通技术人员将理解，图1和图2中的硬件可以根据实现而变化。除了图1和图2中所示的硬件之外或代替图1和图2中所示的硬件，可以使用其他内部硬件或外围设备，诸如闪存、等效的非易失性存储器或光盘驱动器等。在不脱离本发明的精神和范围的情况下，除了前面提到的SMP系统以外，说明性实施例中的过程也可以应用于多处理器数据处理系统。

此外，数据处理系统200可以采取包括客户端计算设备、服务器计算设备、平板计算机、膝上型计算机、电话或其他通信设备、个人数字助理(PDA)等的许多不同数据处理系统中的任何一种的形式。在一些说明性示例中，例如，数据处理系统200可以是便携式计算设备，该便携式计算设备配置有闪存以提供用于存储例如操作系统文件和/或用户生成的数据的非易失性存储器。本质上，数据处理系统200可以是任何已知的或以后开发的数据处理系统，而没有体系结构上的限制。

本部分介绍了本发明所建立于其上的一些背景概念，诸如上下文游戏机和上下文组合游戏机。

上下文游戏机问题。接下来，此问题定义如下。在每个时间点(迭代)，t∈{1，...T}，在选择手臂k∈A＝{1，...K}之前，向代理呈现上下文(特征向量)c(t)∈R

本发明中的特征子集选择方法建立在如下所指定的上下文组合游戏机(CCB)问题上。每个手臂k∈A＝{1，...K}与对应的变量x

在本节中，我们介绍一种新型的上下文游戏机问题，被称为“带有观察的上下文注意游戏机”(CABO)，提出解决此问题的算法，并得出该算法的理论结果(遗憾界限)。

如上所述，c(t)∈R

现在我们将介绍算法1中概述的以下问题设置。我们假设环境在每个时间点t都生成代理无法完全观察到的特征向量c(t)∈R

算法1CABO问题设置

我们将考虑所有复合函数策略的集合П，其首先在给定观察结果c

等式1：

其中

上下文游戏机算法的目标是在T个迭代或时间点上找到最佳策略π∈H，以便总奖励被最大化。假设随机设置，其中上下文和奖励都是分别从概率分布P

定义1(累积遗憾)。令П是等式1中的一组策略。然后，将解决CABO问题(即优化其策略π∈П)的算法的T次迭代上的累积遗憾定义为

等式2：

在T次迭代中学习假设π∈П的上下文游戏机算法的目标是最小化累积遗憾R(T)。

在介绍解决上述CABO问题的算法之前，我们将得出用于解决此问题的任何算法的预期遗憾的下界。

定理1。对于由特定算法计算的用于解决CABO问题的任何策略π∈П，在给定初始特征子集C

第一项来自具有(U+V)个最佳分量的线性游戏机的下界，并且第二项来自具有V个最佳分量的线性游戏机的下界。N和T的条件来自引理7。证明的细节可以在补充材料中找到。参见在线URL＜＜http：//tinyurl.com/y37r9chm＞＞，其教导在此以引用的方式整体并入本文。注意，由于算法需要同时探索特征空间和手臂空间，因此该下界比传统的上下文游戏机更糟。

算法带有观察的上下文注意汤普森采样2

现在，我们提出一种用于解决CABO问题的方法，被称为带有观察的上下文注意汤普森采样(CATSO)，并在算法2中对它进行了总结(对于汤普森采样的背景，参见第3节)。分别地将选择最佳特征子集的组合任务视为上下文组合游戏机(CCB)问题，并且将随后的决策(动作选择)任务视为由汤普森采样解决的上下文游戏机问题。

该算法将特征总数N、最初观察到的特征数V和要观察的附加特征数U作为其输入。我们还提供了上下文汤普森采样(CTS)中使用的分布参数作为输入。

我们迭代T个步骤，在每次迭代t中，首先观察原始观察到的子集C

一旦使用上下文组合游戏机方法选择了特征子集，我们将在步骤17-26中切换到上下文游戏机设置，以基于现在由特征子集组成的上下文选择手臂。

我们将假设预期奖励是受限上下文的线性函数，

除了此差异以外，我们将遵循上下文汤普森采样(CTS)的方法。我们假设在时间t选择手臂k的奖励r

在每个时间点t，并且对于每个手臂，我们从

现在，我们得出了由我们刚刚提出的CATSO算法计算出的策略的遗憾上界。然而，为了使分析更加方便，我们假设算法必须在独立的特征子集C

定义2(CABO的最佳策略)。解决CABO的最佳策略是在时间t选择手臂：

我们还需要以下假设：

等式3：

注意，此情况意味着噪声的均值为零，并且取决于C

使用上述遗憾的定义，现在我们可以得出以下结果。

定理2。假设测量噪声n

定理2指出，所提出算法的遗憾取决于以下两个部分：使用最佳特征向量引起的误差(上界为CTS的遗憾)和选择次优特征子集导致的误差(上界为具有关于奖励的异方差噪声的上下文游戏机中的CTS的遗憾)。

在三种可公开获得的数据集Covertype1、CNAE-91和Warfarin上执行对所提出方法的实证评估。表1总结了这些数据集中的每个数据集的细节。

我们将针对上下文注意游戏机的最新技术(带有受限上下文的汤普森采样(TSRC))，评估带有观察的上下文注意汤普森采样(CATSO)。TSRC解决了先前讨论的具有受限上下文问题的上下文游戏机(CRBC)，其在每个事件中选择一组未知特征，同时假设不存在可观察特征。对于特征总数N和总特征预算D，我们将O个观察到的特征称为已知上下文，将N-O个未观察到的上下文特征称为未知上下文。在我们对TSRC算法的使用中，在每次迭代中，观察已知上下文，TSRC决策机制独立地选择要揭示的U＝D-O个未知上下文特征，并调用上下文汤普森采样(CTS)。

对于平稳设置，我们随机将每个数据集的上下文特征空间的10％固定为一开始就已知，并探索U个未知特征的子集。请注意，当U＝0时，两种方法都简化到(reduce to)仅具有固定的已知上下文的CTS，而当U等于N(上下文特征总数)的90％时，每种方法都简化为具有完整上下文的CTS。对于CATSO，我们固定λ(t)＝1以反映固定设置，然后选择S＝1。对于CATSO和TSRC，我们固定v＝0.25。在图4中的表2中，我们针对每种算法报告了跨对应于N的各种百分比的U的范围的总平均奖励。表2中的结果是令人鼓舞的，在大多数情况下，CATSO的性能优于TSRC基线。在CNAE-9数据集上，CATSO有时表现优于TSRC，而其他时候则几乎与TSRC的性能相当。这一结果在某种程度上说是意料之中的，因为在TSRC的原始工作中，TSRC的平均误差率仅比随机固定未知特征的子集来揭示在CNAE-9上的每个事件要低0∶03％。这表明，TSRC的操作前提(一些特征比其他特征更能预测奖励)并不适用于此数据集。在此假设之上，CATSO还假设已知上下文特征与未知上下文特征之间存在关系，这可能会导致少量误差复合。CATSO在Warfarin和Covertype上均优于TSRC。

接下来，我们检验未知特征空间非平稳的情况。为了模拟未知特征空间中的非平稳性，我们复制每个数据集，以与上述相同的方式随机固定已知上下文，然后对未知特征集-标签对进行混洗。然后，我们随机将原始数据集中的事件替换为它们的经过混洗的对应事件，替换的概率随每个附加事件的增加而一致增加。对于我们称为NCATSO的此非平稳设置，我们固定S＝1并使用GP-UCB算法定义的λ(t)。我们将NCATSO与加权TSRC(WTSRC)进行比较，其中TSRC是具有受限上下文的汤普森采样，TSRC的非平稳版本也在引用的Bouneffouf等人的2017年参考文献中得到了开发。WTSRC仅基于最近的事件来进行对其特征选择模型的更新，其中最近的事件是由时间段或“窗口”w定义的。我们为WTSRC选择w＝100，为两种算法固定v＝0∶25，随机固定10％上下文为已知的并对比图5中的表3中的方法总平均奖励。在这里，我们观察到NCATSO在大多数情况下再次优于现有技术(在此情况下为WTSRC)，并注意到相对于基线(在此情况下为WTSRC)的改进增益甚至比在平稳情况下更大。关于当揭示100％的上下文时奖励的下降，这是两种方法都简化为CTS的情况。在没有任何自适应的情况下，CTS处理非平稳数据与处理平稳数据没有任何不同，这有时可能导致非最佳性能。图1：平稳Covertype，10％的上下文已知

我们通过对Covertype数据集进行更深入的分析并检验S＝U的情况来结束实验。当S＝1时，已知上下文用于一次选择所有U个附加上下文特征，而当S＝U时，已知上下文被更新并用于每次一个地选择U个附加上下文特征中的每一个。维持v＝1和λ(t)＝1，对于平稳情况，我们将CATSO算法的这两种情况分别表示为CATSO-1和CATSO-U，并在10％的上下文被随机固定时在图6中跨各个U报告它们的性能。跨所有测试的U，CATSO-1始终优于CATSO-U。CATSO-U可能会受到影响，这是因为增量特征选择给已知上下文增加了不平稳性-CATSO-1正在学习已知特征和未知特征之间的关系，而CATSO-U正在学习已知上下文增长时它们之间的关系。尽管如此，这两种方法都优于TSRC。对于非平稳情况，我们对λ(t)使用GP-UCB算法，将S＝1和S＝U的情况称为NCATSO-1和NCATSOU，并在图7中说明其性能。在这里，我们观察到NCATSO-1和NCATSO-U具有可比的性能，相对于基线(在该情况中为WTSRC)的改进增益甚至比在平稳情况下更大。

本专利描述了CABO，它是上下文注意游戏机的新变体，其关注上下文不是完全可观察的上下文游戏机问题。我们示出图2：非平稳Covertype，10％的上下文已知，通过了解部分上下文，代理可以对选择下一组要揭示的特征做出更好的决定。这样做的动机来自其中部分上下文特征更容易且更便宜地变得可用而其他特征可能需要时间和/或带来成本的问题场景。

在我们的实验中，我们使用了对于每个数据集预先可用的随机固定的上下文。然而，重要的是注意在此问题设置的实际应用中，已知的上下文特征空间可能是非随机的。相反，它是手边最容易获得的信息，获得成本很低，甚至没有成本，而且信息量可能很高。在我们临床环境的启发性示例中，患者信息的已知上下文很可能对需要执行哪些医学测试具有很高的信息量，并且在AI代理编排的情况下，查询的已知上下文和用户可能能够高度预测需要在对话编排中揭示哪些潜在的代理响应。作为我们未来的紧接的下一步，我们希望在存在已知和未知上下文特征之间的这样的自然划分的数据集上评估我们的算法，并期望我们的方法在这些场景中具有更大的优势。未来工作的另一个方向可能是探索已知上下文的集合随时间变化的已知上下文空间中的非平稳性。

在开始讨论说明性实施例的各个方面之前，应该首先理解，贯穿本说明书中，术语“机构(mechanism)”将用于指代执行各种操作、功能等的本发明的元件。如本文使用的术语“机构”可以是以装置、过程或计算机程序产品形式的说明性实施例的各功能或各方面的实现。在过程的情况下，该过程由一个或多个设备、装置、计算机、数据处理系统等来实现。在计算机程序产品的情况下，由体现在计算机程序产品中或计算机程序产品上的计算机代码或指令表示的逻辑由一个或多个硬件设备执行，以实现功能或执行与具体“机构”相关联的操作。因此，本文描述的机制可以被实现为专用硬件、在通用硬件上执行的软件、存储在介质上使得指令可以由专用或通用硬件容易地执行的软件指令、用于执行功能的过程或方法，或任何上述各项的组合。

关于说明性实施例的特定特征和元素，本说明书和权利要求可以使用术语“一”、“至少一个”和“一个或多个”。应当理解，这些术语和短语旨在声明在特定说明性实施例中存在特定特征或元素中的至少一个，但是也可以存在一个以上。即，这些术语/短语不旨在将说明书或权利要求限制为存在单一特征/元素，或者要求存在多个这样的特征/元素。相反，这些术语/短语仅要求至少一个单一特征/元素，并且多个这样的特征/元素的可能性在说明书和权利要求书的范围内。

因此，可以在许多不同类型的数据处理环境中利用说明性实施例。为了提供用于描述说明性实施例的具体元件和功能的上下文，下面提供图1和图2作为示例环境，其中可以实现说明性实施例的各方面。应当理解，图1和图2仅是示例，并不旨在断言或暗示对于其中可以实现本发明的各方面或实施例的环境的任何限制。在不脱离本发明的精神和范围的情况下，可以对所描绘的环境进行许多修改。

图1描绘了示例分布式数据处理系统的图示，其中可以实现说明性实施例的各方面。分布式数据处理系统100可以包括其中可以实现说明性实施例的各方面的计算机网络。分布式数据处理系统100包含至少一个网络102，该至少一个网络是用于在分布式数据处理系统100内连接在一起的各种设备和计算机之间提供通信链接的介质。网络102可以包括连接，诸如有线、无线通信链接或光缆。

在所描绘的示例中，服务器104和服务器106与存储单元108一起连接到网络102。此外，客户端110、112和114也连接到网络102。这些客户端110、112和114可以是例如个人计算机、网络计算机等。在所描绘的示例中，服务器104向客户端110、112和114提供诸如引导文件、操作系统映像和应用程序之类的数据。在所描绘的示例中，客户端110、112和114是服务器104的客户端。分布式数据处理系统100可以包括附加的服务器、客户端和其他未显示的设备。

在所描绘的示例中，分布式数据处理系统100是因特网，其中网络102表示使用传输控制协议/因特网协议(TCP/IP)协议套件彼此通信的网络和网关的全球集合。因特网的核心是主要节点或主机计算机之间的高速数据通信线路的骨干，其由路由数据和消息的数千个商业、政府、教育和其他计算机系统组成。当然，分布式数据处理系统100也可以被实现为包括许多不同类型的网络，诸如例如内联网、局域网(LAN)、广域网(WAN)等。如上所述，图1旨在作为示例，而非作为对本发明的不同实施例的体系结构限制，并且因此，图1中所示的特定元件不应该被认为是对于其中可以实现本发明的说明性实施例的环境的限制。

图2是其中可以实现说明性实施例的各方面的示例数据处理系统的框图。数据处理系统200是计算机的示例，诸如图1中的客户端110，实现本发明的说明性实施例的过程的计算机可用代码或指令可以位于该计算机中。

在所描绘的示例中，数据处理系统200采用包括北桥和存储器控制器集线器(NB/MCH)202以及南桥和输入/输出(I/O)控制器集线器(SB/ICH)204的集线器体系结构。处理单元206、主存储器208和图形处理器210连接到NB/MCH 202。图形处理器210可以通过加速图形端口(AGP)连接到NB/MCH 202。

在所描绘的示例中，局域网(LAN)适配器212连接到SB/ICH 204。音频适配器216、键盘和鼠标适配器220、调制解调器222、只读存储器(ROM)224、硬盘驱动器(HDD)226、CD-ROM驱动器230、通用串行总线(USB)端口和其他通信端口232以及PCI/PCIe设备234通过总线238和总线240连接到SB/ICH 204。PCI/PCIe设备可以包括，例如，以太网适配器、附加卡和用于笔记本计算机的PC卡。PCI使用卡总线控制器，而PCIe不使用。ROM 224可以是例如闪存基本输入/输出系统(BIOS)。

HDD 226和CD-ROM驱动器230通过总线240连接到SB/ICH 204。HDD 226和CD-ROM驱动器230可以使用例如集成驱动电子设备(IDE)或串行高级技术附件(SATA)接口。超级I/O(SIO)设备236可以连接到SB/ICH 204。

操作系统在处理单元206上运行。该操作系统协调并提供对图2中的数据处理系统200内的各种组件的控制。作为客户端，操作系统可以是商业上可获得的操作系统，诸如

作为服务器，数据处理系统200可以是例如运行高级交互执行

用于操作系统、面向对象的编程系统以及应用程序或程序的指令位于诸如HDD226之类的存储设备上，并且可以被加载到主存储器208中以由处理单元206执行。处理单元206可以使用计算机可用程序代码来执行本发明的说明性实施例的过程，该计算机可用程序代码可以位于诸如例如主存储器208、ROM 224之类的存储器中，或者例如位于一个或多个外围设备226和230中。

诸如图2所示的总线238或总线240之类的总线系统可以包括一个或多个总线。当然，可以使用任何类型的通信结构或体系结构来实现总线系统，该通信结构或体系结构提供在附接到该结构或体系结构的不同组件或设备之间的数据传输。通信单元(诸如图2的调制解调器222或网络适配器212)可以包括用于发送和接收数据的一个或多个设备。存储器可以是例如主存储器208、ROM 224或诸如在图2的NB/MCH 202中找到的高速缓存。

本领域普通技术人员将理解，图1和图2中的硬件可以根据实现而变化。除了图1和图2中所示的硬件之外或代替图1和图2中所示的硬件，可以使用其他内部硬件或外围设备，诸如闪存、等效的非易失性存储器或光盘驱动器等。在不脱离本发明的精神和范围的情况下，除了前面提到的SMP系统以外，说明性实施例中的过程也可以应用于多处理器数据处理系统。

此外，数据处理系统200可以采取包括客户端计算设备、服务器计算设备、平板计算机、膝上型计算机、电话或其他通信设备、个人数字助理(PDA)等的许多不同数据处理系统中的任何一种的形式。在一些说明性示例中，例如，数据处理系统200可以是便携式计算设备，该便携式计算设备配置有闪存以提供用于存储例如操作系统文件和/或用户生成的数据的非易失性存储器。本质上，数据处理系统200可以是任何已知的或以后开发的数据处理系统，而没有体系结构上的限制。

为了基于一组计划中每个计划的质量来确定一组高质量计划的最高子集(k)，并在所识别的前k个计划中，从该组前k个计划中识别一个或多个聚类(m)，说明性实施例提供了一种计划识别和聚类机制，该机制识别具有最低成本的k个不同计划的集合，基于所关联的质量对所识别的前k个计划进行排名，然后使用聚类技术将前k个计划分组，形成一组前m个聚类。图3描绘了使用AI计划的这样的带有不可靠观察结果的计划识别的功能框图。例如，图3的功能框图可以由图1所示的计算设备中的一个或多个计算设备和/或图2的数据处理系统200来实现。在计划识别和聚类机制300的初始化中，计划识别和聚类机制300接收计划问题。

本发明可以是系统、方法和/或计算机程序产品。计算机程序产品可以包括计算机可读存储介质，其上载有用于使处理器实现本发明的各个方面的计算机可读程序指令。

计算机可读存储介质可以是可以保持和存储由指令执行设备使用的指令的有形设备。计算机可读存储介质例如可以是――但不限于――电存储设备、磁存储设备、光存储设备、电磁存储设备、半导体存储设备或者上述的任意合适的组合。计算机可读存储介质的更具体的例子(非穷举的列表)包括：便携式计算机盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、静态随机存取存储器(SRAM)、便携式压缩盘只读存储器(CD-ROM)、数字多功能盘(DVD)、记忆棒、软盘、机械编码设备、例如其上存储有指令的打孔卡或凹槽内凸起结构、以及上述的任意合适的组合。这里所使用的计算机可读存储介质不被解释为瞬时信号本身，诸如无线电波或者其他自由传播的电磁波、通过波导或其他传输媒介传播的电磁波(例如，通过光纤电缆的光脉冲)、或者通过电线传输的电信号。

这里所描述的计算机可读程序指令可以从计算机可读存储介质下载到各个计算/处理设备，或者通过网络、例如因特网、局域网、广域网和/或无线网下载到外部计算机或外部存储设备。网络可以包括铜传输电缆、光纤传输、无线传输、路由器、防火墙、交换机、网关计算机和/或边缘服务器。每个计算/处理设备中的网络适配卡或者网络接口从网络接收计算机可读程序指令，并转发该计算机可读程序指令，以供存储在各个计算/处理设备中的计算机可读存储介质中。

用于执行本发明操作的计算机程序指令可以是汇编指令、指令集架构(ISA)指令、机器指令、机器相关指令、微代码、固件指令、状态设置数据或者以一种或多种编程语言的任意组合编写的源代码或目标代码，所述编程语言包括面向对象的编程语言—诸如Java、Smalltalk、C++等，以及传统过程式编程语言—诸如“C”语言或类似的编程语言。计算机可读程序指令可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络—包括局域网(LAN)或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。在一些实施例中，通过利用计算机可读程序指令的状态信息来个性化定制电子电路，例如可编程逻辑电路、现场可编程门阵列(FPGA)或可编程逻辑阵列(PLA)，该电子电路可以执行计算机可读程序指令，从而实现本发明的各个方面。

这里参照根据本发明实施例的方法、装置(系统)和计算机程序产品的流程图和/或框图描述了本发明的各个方面。应当理解，流程图和/或框图的每个方框以及流程图和/或框图中各方框的组合，都可以由计算机可读程序指令实现。

这些计算机可读程序指令可以提供给通用计算机、专用计算机或其它可编程数据处理装置的处理器，从而生产出一种机器，使得这些指令在通过计算机或其它可编程数据处理装置的处理器执行时，产生了实现流程图和/或框图中的一个或多个方框中规定的功能/动作的装置。也可以把这些计算机可读程序指令存储在计算机可读存储介质中，这些指令使得计算机、可编程数据处理装置和/或其他设备以特定方式工作，从而，存储有指令的计算机可读介质则包括一个制造品，其包括实现流程图和/或框图中的一个或多个方框中规定的功能/动作的各个方面的指令。

也可以把计算机可读程序指令加载到计算机、其它可编程数据处理装置、或其它设备上，使得在计算机、其它可编程数据处理装置或其它设备上执行一系列操作步骤，以产生计算机实现的过程，从而使得在计算机、其它可编程数据处理装置、或其它设备上执行的指令实现流程图和/或框图中的一个或多个方框中规定的功能/动作。

附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或指令的一部分，所述模块、程序段或指令的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

因此，说明性实施例提供了用于基于一组计划中的每个计划的质量来识别一组前k个计划并且在所识别的前k个计划的集合中从该组前k个计划中识别一个或多个聚类(即前m个聚类)的机制。特别地，说明性实施例识别具有最低成本的k个不同计划的集合，其中，k个不同计划包括取决于k的最优计划和接近最优的计划，并且根据定义，对于此集合中的每个计划，所有成本较低的有效计划也必须在该集合中。然后，基于每个计划相关联的质量(即与计划相关联的成本)对前k个计划进行排名，其中最低成本识别最高质量。然后，使用聚类技术将前k个计划分组为前m个聚类，其中每个聚类的代表集合被提供有查看该聚类内的所有计划的选项。

如上所述，应当理解，说明性实施例可以采取完全硬件实施例、完全软件实施例或包含硬件和软件元素两者的实施例的形式。在一个示例实施例中，说明性实施例的机制以软件或程序代码来实现，该软件或程序代码包括但不限于固件、驻留软件、微代码等。

适用于存储和/或执行程序代码的数据处理系统将包括通过系统总线直接或间接耦合到存储器元件的至少一个处理器。存储器元件可以包括在程序代码的实际执行期间使用的本地存储器、大容量存储装置和提供至少一些程序代码的临时存储以便减少在执行期间必须从大容量存储装置中检索代码的次数的高速缓存存储器。

输入/输出或I/O设备(包括但不限于键盘、显示器、定点设备等)可以直接或通过中间I/O控制器耦合到系统。网络适配器也可以耦合到系统，以使数据处理系统能够通过中间的专用或公共网络耦合到其他数据处理系统或远程打印机或存储设备。调制解调器、线缆调制解调器和以太网卡只是当前可用的网络适配器类型中的几种。盘驱动器、DVD、CD和记忆棒只是计算机可读存储设备中的几种。

本发明的描述已经出于说明和描述的目的被给出，并且并不旨在是穷举的或将本发明限于所公开的形式。在不脱离所描述的实施例的范围和精神的情况下，许多修改和变化对于本领域普通技术人员将是明显的。选择和描述实施例是为了最好地解释本发明的原理、实际应用，并使本领域的其他普通技术人员能够理解具有如适合所设想的特定用途的各种修改的各种实施例的本发明。选择这里使用的术语是为了最好地解释实施例的原理、对市场上发现的技术的实际应用或技术上的改进，或者使本领域的其他普通技术人员能够理解本文公开的实施例。