Prueba de que los modelos CRF y los modelos logísticos son funciones convexas

¿Dónde puedo encontrar una buena prueba de que los modelos basados ​​en CRF y los modelos basados ​​en regresión logística son convexos? ¿Hay algún truco general para probar / probar que un modelo o función objetivo es convexo?

Un truco es reescribir funciones objetivas en términos de funciones que se sabe que son convexas.

La función objetiva del modelo logarítmico lineal entrenado en ML es una suma de probabilidades logarítmicas negativas, por lo que es suficiente para mostrar que la probabilidad logarítmica negativa para cada punto de datos es convexa.

Considerando el punto de datos fijo, podemos escribir su término negativo de log-verosimilitud como

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

El primer término es lineal, por lo que es suficiente mostrar que el segundo término, conocido como log-normalizer, es convexo.

Escríbalo como donde y . Aquí es una función lineal, es una función convexa conocida llamada log-sum-exp. Consulte la página 72 del libro de optimización convexa de Boyd . La composición de una función convexa y una función lineal es convexa, ver sección 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$

Otro enfoque es utilizar el hecho de que log-normalizer es la función de generación acumulativa. Por ejemplo, vea el ejemplo 3.41 en el libro de Boyd, o la Proposición 3.1 en el manuscrito "Modelos gráficos, familias exponenciales e inferencia variacional" de Wainwright . Esto significa que la segunda derivada es la matriz de covarianza de suficiente estadística que, por definición, es semi-definida positiva, lo que significa que Hessian del log-normalizador es semi-definida positiva. La arpillera semi-definida positiva garantiza que la función es convexa, consulte la sección 3.1.4 del libro de Boyd.$\phi$

Técnicamente, el log-normalizador no es la función de generación acumulativa tradicional. CGF es . Sin embargo, la derivada del log-normalizador evaluada en es la misma que la derivada del CGF evaluado en , por lo que produce acumulantes como CGF.$g(\phi)=\log(Z(\theta+\phi))-\log(Z(\theta))$$\theta$$\mathbf{0}$

No pude encontrar una prueba completa de equivalencia, por lo general la gente la omite porque son solo varios pasos de álgebra poco inspiradora. Una derivación muy concisa para el espacio de salida continua se encuentra en la página 5 de la tesis de "Modelos gráficos" de Xinhua Zhang . Creo que se vio una derivación completa en "Fundamentos de las familias exponenciales estadísticas" de Lawrence D. Brown

Primero, la convexidad no es solo una característica de una función, sino más bien una función y el dominio sobre el que se define.

Para abordar su pregunta más directamente, otro truco (más bien otra formulación) es calcular la matriz de Hesse de su función de probabilidad. A por wiki, una función continua, dos veces diferenciable de varias variables es convexa en un conjunto convexo si y solo si su matriz de Hesse es positiva semidefinida en el interior del conjunto convexo .

Dado que el Hessian es realmente simétrico, es suficiente tener un dominio diagonal para que sea PSD (esto es obvio para el modelo logístico).