algorithm - # 特征较大时改进的迭代缩放方法

Question

在对数线性模型中，我们可以使用 IIS 找到最大熵解。我们通过找到一个参数来更新参数，该参数使模型对特征的期望和经验期望匹配。但是，等式中有一个 exp（所有特征的总和）。我的问题是，当特征的数量很大（比如 10000）时，所有特征的总和会很容易爆炸。我们如何用数值方法解决这个问题？对我来说这似乎是不可能的，因为即使计算 exp(50) 也会失败。

Answer 1

在对数空间中进行计算，并使用一个logsumexp操作（借用自scikit-learn）：

// Pseudocode for 1-d version of logsumexp:
// computes log(sum(exp(x) for x in a)) in a numerically stable way.
def logsumexp(a : array of float):
    amax = maximum(a)
    sum = 0.
    for x in a:
        sum += exp(x - amax)
    return log(sum) + amax

这个求和可以在主循环开始之前完成一次，因为在优化时特征值不会改变。

旁注：IIS 相当老式。大约 10 年来，几乎每个人都在使用 L-BFGS-B、OWL-QN 或 (A)SGD 来拟合对数线性模型。