Beweis, dass CRF-Modelle und Logistikmodelle konvexe Funktionen sind

Wo finde ich einen guten Beweis dafür, dass CRF-basierte Modelle und logistische Regressionsmodelle konvex sind? Gibt es einen allgemeinen Trick, um zu testen / zu beweisen, dass ein Modell oder eine Zielfunktion konvex ist?

Ein Trick besteht darin, objektive Funktionen in Form von Funktionen umzuschreiben, von denen bekannt ist, dass sie konvex sind.

Die Zielfunktion des ML-trainierten logarithmischen linearen Modells ist eine Summe negativer logarithmischer Wahrscheinlichkeiten. Es reicht also aus zu zeigen, dass die negative logarithmische Wahrscheinlichkeit für jeden Datenpunkt konvex ist.

Wenn der Datenpunkt fest ist, können wir seinen negativen Log-Likelihood-Term als schreiben

$$-\langle \theta,\phi(y)\rangle+\log \sum_y \exp(\langle \theta,\phi(y)\rangle)$$

Der erste Term ist linear, daher reicht es aus zu zeigen, dass der zweite Term, der als Log-Normalisierer bezeichnet wird, konvex ist.

Schreiben Sie es als wobei und . Hier ist eine lineare Funktion und ist eine bekannte konvexe Funktion, die als log-sum-exp bezeichnet wird. Siehe Seite 72 von Boyds Buch zur konvexen Optimierung . Die Zusammensetzung einer konvexen Funktion und einer linearen Funktion ist konvex, siehe Abschnitt 3.2.2$f(\mathbf{g}(\mathbf{\theta}))$$f(\mathbf{y})=\log \sum_y \exp y$$g_y(\theta)=\langle \mathbf{\theta},\phi(y)\rangle$$g$$f$

Ein anderer Ansatz besteht darin, die Tatsache zu verwenden, dass der Log-Normalisierer die kumulierende Erzeugungsfunktion ist. Siehe zum Beispiel Beispiel 3.41 in Boyds Buch oder Satz 3.1 in Wainwrights Manuskript "Grafische Modelle, Exponentialfamilien und Variationsinferenz" . Dies bedeutet, dass die zweite Ableitung die Kovarianzmatrix mit ausreichender Statistik die per Definition positiv semidefinit ist, was bedeutet, dass Hessisch des logarithmischen Normalisierers positiv semidefinit ist. Positives halbbestimmtes Hessisches garantiert, dass die Funktion konvex ist, siehe Abschnitt 3.1.4 von Boyds Buch.$\phi$

Technisch gesehen ist der Log-Normalisierer nicht die herkömmliche Funktion zur Erzeugung von Kumulanten. CGF ist . Die Ableitung des bei bewerteten logarithmischen Normalisierers ist jedoch dieselbe wie die Ableitung des bei bewerteten CGF , so dass sie genau wie CGF Kumulanten erzeugt.θ $g(\phi)=\log(Z(\theta+\phi))-\log(Z(\theta))$$\theta$$\mathbf{0}$

Ich konnte keinen vollständigen Beweis für die Äquivalenz finden, normalerweise lassen die Leute ihn weg, weil es nur ein paar Schritte uninspirierender Algebra sind. Eine sehr knappe Ableitung für den kontinuierlichen Ausgaberaum finden Sie auf Seite 5 von Xinhua Zhangs These "Graphical Models" . Ich glaube, dass Lawrence D. Browns "Grundlagen statistischer Exponentialfamilien" eine vollständige Ableitung gesehen hat.

Erstens ist Konvexität nicht nur ein Merkmal einer Funktion, sondern vielmehr eine Funktion und die Domäne, über die sie definiert ist.

Um Ihre Frage direkter zu beantworten, besteht ein weiterer Trick (eher eine andere Formulierung) darin, die hessische Matrix Ihrer Wahrscheinlichkeitsfunktion zu berechnen. Eine pro Wiki kontinuierliche, zweimal differenzierbare Funktion mehrerer Variablen ist auf einer konvexen Menge genau dann konvex, wenn ihre hessische Matrix im Inneren der konvexen Menge positiv semidefinit ist .

Da das Hessische wirklich symmetrisch ist, reicht es aus, eine diagonale Dominanz zu haben , damit es PSD ist (dies ist für das logistische Modell offensichtlich).