本节提出了一种基于模拟退火的算法来解决问题 4.7，并展示了如何利用外部知识来优化俗语模板。本章使用模拟退火算法来计算最好的动词模板分配 f 。算法流程如下。首先选取随机的分配作为初始值（初始温度）。然后，算法生成并评估一个新的分配，如果它是一个更好的分配，用这个分配替换掉之前的分配；否则，算法以一定的概率接受这个分配（温度降低）。重复生成以及替换的步骤直到最后的 β 轮结果没有出现变化（终止条件）。

候选分配生成：显然，候选分配的生成对于算法的效用和效率来说非常关键。接下来首先介绍一个直接生成候选分配的方法。然后对候选动词模板作典型性的改进。

直接生成方法：模板分配 f 的最基本的单元是对一个动词短语的模板分配。直接生成方法会随机选择一个动词短语 p 并将它分配给一个随机的模板 a。产生一个有效的模板。算法需要确保（1）a 是一个 p 的俗语模板，或者（2）a 是一个实体概念化模板并且 ca 是 op 的上位词。然而，因为很难达到最优状态，这个方法效率很低。对于一个动词，假设它有 n 个动词短语并且每一个动词短语都有平均 k 个候选模板。达到最优状态的最小轮数平均是 kn，这在大语料库上是不可接受的。

利用典型性的生成方法：注意到对于每一个确定的动词词组，一些模板会因为它们更高的典型性而比其他模板更有效。例 4.8 介绍了这种情况。这使算法倾向于将动词短语分配给具有更高典型性的动词模板。

例 4.8. 对于 eat breakfast，eat lunch。eat $Cmeal 显然比 eat $Cactivity 更好。因为对于一个真实的人来说，他更容易想到 eat $Cmeal 而不是 eat $Cactivity。换句话说 eat $Cmeal 相比 eat $Cactivity 具有更高的典型性。

更形式化的，对于一个确定的动词短语 p，定义 t(p,a) 衡量模板 a 相对于动词短语 p 的典型性。如果 a 是俗语模板，t(p,a) 被设置成一个常数 γ。如果 a 是实体概念化模板，使用 op 相对于 ca 的典型性定义 t(p,a)，这里 ca 是模板 a 的概念。特别的有：

这里 PT (op|ca) 和 PT (ca|op) 可以从 Probase [103] 通过式 4.15 推导出。在这个计算中，公式同时考虑从 ca 到 op 的概率，和从 op 到 ca 的概率，以获得它们相互之间的影响。

3.3.1. 流程

现在将介绍解决方案的详细流程：

　　1. 通过将每一个 p 分配给它的俗语模板来初始化 f(0)。

2. 随机选择新的动词模板 a。对于每一个动词短语 p，

这里 f (i) 是第 i 轮产生的分配。

3. 以如下概率接受 f(i+1)：

这里 L(f(i+1)) 是 f(i+1) 的描述长度，S 是 SA 算法进行的轮数，A 是控制冷却速度的常数。

4. 重复步骤 2 和步骤 3，直到最后 β 轮结果不发生变化。

步骤 2 和步骤 3 使算法不同于一般的基于 SA 的解决方法。在步骤 2 中，对于每一 个随机选择的动词模板 a，算法计算它的典型性。如果它的典型性大于当前分配的动词模板，则将这个动词短语分配给动词模板 a。在步骤 3 中，当一个新的分配的描述长度比上一轮的分配更小时，算法接受这个新的分配。否则，算法以 (L( f (i)) ?L( f (i+1)))/SA 的概率接受原有的分配。它的合理性是显然的：L( f (i+1)) 相对于 L( f (i)) 的偏离越大，f (i+1) 被接受的概率越小。

复杂性分析假设有 n 动词短语。在每一轮循环中，算法随机选择一个动词模板，然后计算它对于所有 n 个动词短语的典型性，这需要 O(n) 的时间来实现。然后，算法通过加和所有 n 个动词短语的编码长度来计算 f (i+1) 的描述长度。这个步骤同样需要 O(n) 时间。假设算法在 S 轮后终止，则整体的复杂度将是 O(Sn)。