初始化：为了避免式 5.21 中 P(zi = (p,t)|X,θ(s)) 为全零的情况，模型要求 θ(0) 在所有满足 f(xi,zi) > 0 的 (xi,zi) 上均匀分布。从而得到：

E步骤：这一步骤中，算法枚举所有的 zi，通过式 5.21 计算 P(zi|X,θ(s))。这一步骤的复杂度为 O(m)。

M步骤：这一步骤中，对每一个θ(s+1)Pt，算法计算 ∑m P(Zi= (p,t)|X,θ(s))。直接计算需要消耗 O(m|P||T|) 的时间，因为算法需要枚举全部可能的模板和属性。接下来，通过对每个 i 只枚举常量的模板和属性，算法的复杂度可以被减少为 O(m)。

注意到只有 P(zi = (p,t)|X,θ(s)) > 0 的 Zi 需要考虑。由式 5.19 和 5.21 可知：

由于 P(t|ei,qi) > 0，算法可以减少枚举的模板数。P(t|ei,qi) > 0 意味着算法只枚举从 qi 中的 ei 概念化过程中得到的模板。e 的概念数显然是有上界的，并且可以被看作常量。因此，第 7 行中枚举的模板 t 的总数是 O(m)。由于 P(vi|ei, p) > 0，算法可以减少枚举的属性数。P(vi|ei, p) > 0 意味着只有在知识图谱中连接 ei 和 vi 的属性需要被枚举。这样的属性数也可以被视作常量。因此 M 步骤的复杂度是 O(m) 的。

EM 算法的总体复杂度：假定整个过程重复 EM 算法 k 次，则总体复杂度为 O(km)。

PaperWeekly 将对本论文进行独家连载

　　敬请期待后续精彩内容……