证明 CRF 模型和逻辑模型是凸函数

机器算法验证 物流 优化
2022-03-29 21:06:29

我在哪里可以找到证明基于 CRF 的模型和基于逻辑回归的模型是凸的?是否有一个通用技巧来测试/证明模型或目标函数是凸的?

2个回答

一个技巧是根据已知的凸函数重写目标函数。

ML 训练的对数线性模型的目标函数是负对数似然的总和,因此足以表明每个数据点的负对数似然是凸的。

考虑到数据点是固定的,我们可以将其负对数似然项写为

θ,ϕ(y)+logyexp(θ,ϕ(y))

第一项是线性的,因此足以证明第二项(称为对数归一化器)是凸的。

把它写成其中 and这里是一个线性函数,是一个已知的凸函数,称为log-sum-exp。请参阅 Boyd 的凸优化一书的第 72 页。凸函数和线性函数的组合是凸的,见第 3.2.2 节f(g(θ))f(y)=logyexpygy(θ)=θ,ϕ(y)gf

另一种方法是使用对数归一化器是累积量生成函数的事实。例如,参见 Boyd 书中的示例 3.41,或 Wainwright 的“图形模型、指数族和变分推理”手稿中的命题 3.1 。这意味着二阶导数是充分统计量的协方差矩阵,根据定义,它是半正定的,这意味着对数归一化器的 Hessian 矩阵是半正定的。正半定 Hessian 保证函数是凸的,参见 Boyd 书中的第 3.1.4 节。ϕ

从技术上讲,对数归一化器不是传统的累积量生成函数。CGF 是然而,在处评估的 CGF 的导数相同,因此它会像 CGF 一样产生累积量。g(ϕ)=log(Z(θ+ϕ))log(Z(θ))θ0

我找不到完整的等价证明,通常人们会忽略它,因为它只是平淡无奇的代数的几个步骤。连续输出空间的一个非常简洁的推导在张新华的“图形模型”论文的第 5 页。我相信在 Lawrence D. Brown 的“统计指数族的基础”中看到了完整的推导

首先,凸性不仅是函数的特征,而且是函数定义它的域。

为了更直接地解决您的问题,另一个技巧(而不是另一种公式)是计算似然函数的 Hessian 矩阵。每个wiki 一个连续的、由多个变量组成的二次可微函数在凸集上是凸的当且仅当它的 Hessian 矩阵在凸集的内部是半正定的

由于 Hessian 是实对称的,因此具有对角线优势就足够了,因为它是 PSD(这对于逻辑模型很明显)。