浅谈贪心的启发式算法

作者：章放来源：AMiner官网

我们已经证明了这个问题是NP-hard 的，因此我们很难在多项式时间内找到原来问题的最优解。⽽这在⼤多数时候也意味着为了能在可接受的时间内⽐较好地求解原来的问题，我们需要构思⼀种近似解决来近似解决原来的问题。

对于提取给定领域内的最重要的k 个话题这一问题，我们已把问题形式化为求解下⾯这样⼀个问题的最优解：

我们已经证明了这个问题是NP-hard 的，因此我们很难在多项式时间内找到原来问题的最优解。⽽这在⼤多数时候也意味着为了能在可接受的时间内⽐较好地求解原来的问题，我们需要构思⼀种近似解决来近似解决原来的问题，接下来我们将提出⼀种贪⼼的启发式算法。

算法1展⽰了我们的贪⼼算法的主要步骤，接下来我们将进⾏详细地解释说明。对于⼀个贪⼼算法⽽⾔，我们的主要思路是如何⼀步⼀步增量式地构造出⼀个⽐较好的解。⽽对于我们这个问题⽽⾔，我们主要想要做的就是如何通过⼀步⼀步地挑选话题，使得在第i 步⾥，我们能够挑选出话题t*_ j 使得：

其中Ti 表⽰在第i 步之前选出来的话题。为了计算D(Ti ꓵ{t j } ,C, r)，我们引⼊ “近似权重”的概念：近似权重w^r_i 表⽰话题ti ∈ C 对于给定领域r 的近似重要性。我们将这个权重称作 “近似权重” 是因为这个值代表的是话题的重要性，并且我们可以通过使⽤⼀些领域知识来估计出来它的⼤⼩，由于这种重要性的表⽰并不是⾮常精确的（如果我们能够得到精确的表⽰的话，那么我们的原始的问题其实也就得到解决了），它只能被⽤来粗略地对某个话题对于给定领域的重要性的进⾏估计。很快我们就会阐述如何来计算出这个近似权重w^r_i 。假设我们已经有了这个近似权重w^r_i ，那么我们可以定义D(Ti ꓵ{t j } ,C, r)为：

其中S(th, tl) 表⽰话题th 和tl 之间的相关性。我们在之前已经得到了每个话题的向量表⽰，这样我们就可以通过计算不同向量之间的cosine 距离来衡量不同向量之间的相关性S(th, tl):

近似权重的计算

为了计算话题ti C 在给定的领域r 上的近似权重w^r_i，我们将⼤型外部知识库维基百科⾥⾯的领域信息（Domain Knowledge）给结合进了我们的模型⾥。这个做法跟Mintz 等⼈[1] 提到的 “远程监督” 这个概念是类似的。具体⽽⾔，我们使⽤了维基百科⾥⾯的给定领域r 下⾯的⽬录结构信息作为我们的领域信息来帮助计算w^r_i 。其主要思想是这样的：在给定领域r 对应的⽬录下的所有层次的⼦⽬录⾥⾯，越浅层的⼦⽬录所对应的话题相⽐于越深层的⼦⽬录所对应的话题⽽⾔在领域r 内可能更重要也更跟r 相关。我们将计算w^r_i的具体步骤总结如下：

• ⾸先找到r 在维基百科⾥⾯所对应的⽬录，我们也把这个⽬录记为r。

• 然后对于维基百科中的⽬录r，我们通过递归的⽅式⼀层层地从维基百科上提取出来它下⾯的所有的⼦⽬录：SC = {{t0}， {t11, t12, …}, {t21, t22, …}, …}，其中t0 表⽰根⽬录r，tmn 表⽰在第m 层（或者说深度为m）的第n 个⼦⽬录。

• 按照如下公式计算话题ti ∈ C 在给定领域r 中所对应的近似权重：w^r-_i = g(n)，其中n 表⽰话题ti 在r 的⼦⽬录⾥⾯的深度（在ti ∈ SC 的情况下）；不然我们就令：w^r_i = 0，或者等价地，如果我们想把所有候选话题都放⼊SC 的话，就令n = 1。G(n) 是⼀个随着n 的增⼤单调递减的函数，之后我们将通过经验的⽅式选择这个函数的具体形式。

到此为⽌我们就得到了近似权重w^r_i 的具体的计算⽅式，在计算出近似权重之后，我们就能够计算出之前我们想要计算的D(Ti ꓵ{t j } ,C, r)，这样⼀来我们的算法1就能进⾏下去了。

贪心的启发式算法的改进

从算法1我们可以看出，它的时间复杂度为：O(k |C| ^2)，其中k 表⽰我们需要抽取的话题的个数，|C| 表⽰C 中的元素的个数。在实际的使⽤中，k ⼀般是⽐较⼩（不超过100），然⽽C 中元素的个数却可能很多，⽐如上千万甚⾄上亿个。在我们的⼯作中，C中的元素多达9,355,550 个，因此算法1的运⾏时间可能会⾮常

长以⾄于难以让⽤户接受（事实上我们在实验室中发现确实是如此）。然⽽，我们通过对于数据的观察和分析发现了下⾯两个事实：

• 在整个集合C 中的⼤多数的候选话题都跟给定的单独的⼀个领域r 不是很相关。

• 当⼀个话题在给定领域⾥⾯的近似权重⾜够⼩的时候，那么这个话题对于算法1中的和s的贡献也会变得⾜够⼩以⾄于可以被忽略。

基于这两个事实，我们提出了下⾯两种对应的策略，这两种策略能够⼤⼤提升我们的算法的运⾏速度：

• 我们选定⼀个深度d1，然后对于给定的领域r，我们只保留给定领域r 在维基百科上对应的⽬录下⾯的最多d1 层⼦⽬录下的所有话题作为我们的⾼质量的候选话题。

• 因为⼀个话题的近似权重函数g(n) 是随着话题在⼦⽬录⾥⾯的深度n 单调递减的，所以我们可以选择⼀个深度d2（在定义⼀个合适的g(n) 的基础上）来使得⽐深度d2 还要深的那些⼦⽬录⾥⾯的话题所带来的贡献⾜够⼩以⾄于我们可以在计算中去掉这些话题来加速计算同时保证准确率。

这样的两个策略将会使得我们的算法⽐原来的算法1快得多，并且时间复杂度变为

其中

分别表⽰⾼质量的候选话题集合和贡献⽐较⼤的候选话题集合。在实际使⽤中我们有

这使得我们的算法运⾏速度将⼤⼤提升。我们将这个改进后的算法总结在算法2中。

参考：

[1] Mintz M, Bills S, Snow R, et al. Distant supervision for relation extraction without labeled data [C]//Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 2-Volume 2. [S.l.]: Association for Computational Linguistics, 2009: 1003–1011.