Preuve que les modèles CRF et les modèles logistiques sont des fonctions convexes

8

Où puis-je trouver une bonne preuve que les modèles basés sur CRF et les modèles basés sur la régression logistique sont convexes? Existe-t-il une astuce générale pour tester / prouver qu'un modèle ou une fonction objective est convexe?

euphoria83
la source

Réponses:

7

Une astuce consiste à réécrire les fonctions objectives en termes de fonctions connues pour être convexes.

La fonction objective du modèle log-linéaire formé par ML est une somme de log-vraisemblances négatives, il suffit donc de montrer que la log-vraisemblance négative pour chaque point de données est convexe.

En considérant le point de donnée comme fixe, nous pouvons écrire son terme de log-vraisemblance négatif comme

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

Le premier terme est linéaire, il suffit donc de montrer que le second terme, connu sous le nom de normalisateur de log, est convexe.

Écrivez-le comme où et . Ici, est une fonction linéaire et est une fonction convexe connue appelée log-sum-exp. Voir page 72 du livre Boyd's Convex Optimization . La composition d'une fonction convexe et d'une fonction linéaire est convexe, voir section 3.2.2f(g(θ))f(y)=logyexpygy(θ)=θ,ϕ(y)gf

Une autre approche consiste à utiliser le fait que le normalisateur de journal est la fonction de génération de cumul. Par exemple, voir l'exemple 3.41 du livre de Boyd ou la proposition 3.1 du manuscrit "Modèles graphiques, familles exponentielles et inférence variationnelle" de Wainwright . Cela signifie que la dérivée seconde est la matrice de covariance d'une statistique suffisante qui, par définition, est semi-définie positive, ce qui signifie que la Hesse du log-normalisateur est semi-définie positive. Une Hesse semi-définie positive garantit que la fonction est convexe, voir la section 3.1.4 du livre de Boyd.ϕ

Techniquement, le normalisateur de journal n'est pas la fonction de génération de cumulante traditionnelle. CGF est . Cependant, le dérivé du normalisateur de log évalué à est le même que le dérivé du CGF évalué à , il produit donc des cumulants tout comme CGF.g(ϕ)=log(Z(θ+ϕ))log(Z(θ))θ0

Je n'ai pas pu trouver une preuve complète de l'équivalence, généralement les gens l'omettent parce que ce n'est que plusieurs étapes d'une algèbre sans intérêt. Une dérivation très concise pour l'espace de sortie continu est à la page 5 de la thèse de "Modèles graphiques" de Xinhua Zhang . Je crois que l'on a vu une dérivation complète dans "Fondamentaux des familles exponentielles statistiques" de Lawrence D. Brown

Yaroslav Bulatov
la source
2

Premièrement, la convexité n'est pas seulement une caractéristique d'une fonction, mais plutôt une fonction et le domaine sur lequel elle est définie.

Pour répondre plus directement à votre question, une autre astuce (plutôt une autre formulation) consiste à calculer la matrice de Hesse de votre fonction de vraisemblance. Une fonction par wiki d' une fonction continue, deux fois différenciable de plusieurs variables est convexe sur un ensemble convexe si et seulement si sa matrice de Hesse est semi-définie positive à l'intérieur de l'ensemble convexe .

Le Hessian étant vraiment symétrique, il suffit d'avoir une dominance diagonale pour qu'il soit PSD (c'est évident à montrer pour le modèle logistique).

user603
la source