【十分钟 机器学习 系列课程】讲义（三十四）：最大熵模型：原始问题和对偶问题

欢迎回来。上期我们给大家解读了最大熵模型【十分钟 机器学习 系列课程】讲义（三十三）：最大熵模型的含义，详细梳理了集合和条件熵中的概念，这期带着大家继续说说最大熵模型中的「原始问题和对偶问题」。

壹 最大熵模型的原始问题

1.最大熵模型

首先让我们还是用1分钟回顾一下最大熵模型的含义吧。

❝

假设满足所有约束条件的「模型集合」为

定义在条件概率分布 上的「条件熵」为

则模型集合 中条件熵 最大的模型称为「最大熵模型」。

❞

没错，这其实是个「优化问题」，目的就是要找到使条件熵最大的那个「概率分布」，而这个分布是要从「待选模型集合」中选出。

因为它的特点是概率分布，找到的所有集合就必须满足：

2.拉格朗日对偶性

那么如何找到满足最大条件熵的概率分布呢？在介绍之前，咱们先不妨说说用来求解约束最优化问题的方法-「拉格朗日对偶性」。

这个方法的「精髓实质」上：

❝

是将一个求解有约束最优化的「原始问题(不等式)」 用 「拉格朗日乘子法」转为无约束「等式」问题，并接着将这个无约束的原始问题转为「对偶问题」来进行求解，目的就是更便捷地求出有约束最优化的解。

❞

当然啦，相信你一定想为什么要这么计算呢，别着急，在此之前，我们先仔细说一下什么是原始问题。

3.原始问题

❝

若 是定义在 上的连续可微函数。考虑如下有约束的最优化问题：

❞

❝

这就是该有约束最优化问题的原始形式。

❞

这样一个优化问题其实计算起来非常的复杂，因为有 个约束条件。

那么这个原始问题怎么和最大熵模型联系起来呢？

很简单，这里的原始问题用来求「最小值」，那么我们可以将最大熵模型求最大值问题「取反后求最小值」，也是同样的含义。

好啦，接着该怎么将不等式换成等式呢？

没错，正是要用到拉格朗日乘子法，那么我们就可以引进「广义拉格朗日函数」：

对于每个约束条件前面都来加一个拉格朗日乘子，那么对应的 有 维，对应的 有 维，而原始的 有 维。

我们「考虑关于 的函数」，这就意味着代入已知的若干组 找到可以使 最大的值，接着把这个函数记为：

这里的角标 意味着 「Primal」（原始）的含义哦。咱们可以看出：

❝

• 在有约束的情况下，
• 在无约束的情况下，

❞

为什么这么说呢？

因为「在有约束的情况下」，如果求 ，回归到原始问题的约束条件中，意味着将 和 都取最大值，这里对应的都是 ，只剩下了 ，因此 「 」。

而「在无约束的情况下」，意味着没有了 和 的约束，那么可以将 取无穷大，这样就得到了 。

接着对这个原始问题的最优值就可以写成：

这样就转为了极小极大值的问题，记为 。

贰 最大熵模型的对偶问题

介绍完了原始问题，咱们接下来继续看看什么是对偶问题。

1.对偶问题

还是回到广义拉格朗日函数问题上。

如果这次我们是对 求最小值，那么未知的就是 和 函数。

记为：

注意哦，这里的 代表了 「Dual」，意味着对偶问题。

那么对偶问题的最优值就可以写成：

这就写成了极大极小问题。

2.原始问题和对偶问题的关系

那么这两个问题有什么关系呢？接着就手把手带你推导一下。

Step 1 广义拉格朗日函数的区间范围

可以看出：

Step 2 用 函数表示原始对偶关系

接着我们用刚刚设置的 函数代入表示：

那么什么时候能满足等号相同呢？

Step 3 令等号相等需满足的条件

❝

若函数 和 是凸函数， 是仿射函数；并且假设不等式约束 是严格可行的，即存在 ，对所有的 有 ，则存在 使 是原始问题的解， 是对偶问题的解，并且

❞

而将满足等号对应的最优解记为 。

利用这个等式，我们就可以用「对偶问题」来求解「有约束的最优化原始问题」，实现了极大极小值之间的转换，便于计算出最优解。

叁 如何理解拉格朗日对偶性

现在，咱们一起总结一下如何理解拉格朗日对偶性，当然有两个函数的含义你必须了解。

1.凸函数和仿射函数

还记得在讲条件熵时【十分钟 机器学习 系列课程】 讲义（二十）：选择最优特征-信息增益，我们说过了凸函数的概念，举个简单的例子。

「凸函数」是指 在任意两个向量 的函数满足:

它的特点是「局部最小值即全局最小值」。

意味着：

❝

可以通过偏微分函数为零求出最小值。

❞

那么「仿射函数」又是什么呢？仿射函数就是最高次数为1的多项式函数，一般形式为 。

2.KKT条件

若函数 和 是凸函数， 是仿射函数；并且假设不等式约束 是严格可行的，则 是原始问题的解， 是对偶问题的解的「充分必要条件」，简称KKT条件。

注意哦，第一条正是「可微求偏导求极值」，通过这个条件就可以通过对偶问题求出原始问题的解。之后的学习中，我们就是根据这个思路来进行计算的。

好啦，关于最大熵模型「原始问题和对偶问题的解读」就到这里，下期我们将继续说说为什么要用对偶问题来计算有约束的最优解，在最大熵模型的学习中又是如何应用这个方法的，喜欢我们的小伙伴请「点赞+转发+在看」。下期不见不散~