¿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 un truco general para probar / probar que una función de modelo u objetivo es convexa?
Respuestas
¿Demasiados anuncios?
Patrick
Puntos
183
En primer lugar, la convexidad no es sólo una característica de una función, sino más bien, una función y el dominio sobre el que está definida.
A la dirección de su pregunta más directamente, otro truco (en lugar de otra formulación) es calcular la matriz Hessiana de la función de probabilidad. Por wiki continua y dos veces diferenciable función de varias variables es convexa en un conjunto convexo si y sólo si su matriz Hessiana es positivo semidefinite en el interior del conjunto convexo.
Desde el estado de Hesse es real simétrica, es suficiente con tener la diagonal de dominio, para que sea PSD (esto es obvio para mostrar para el modelo logístico).
Oak
Puntos
1366
Un truco es reescribir las funciones objetivo en términos de las funciones que se sabe que son convexos.
La función objetivo de ML capacitados log-lineal de la modelo es una suma de registro negativo-de las probabilidades, por lo que es suficiente para mostrar que la negativa de la log-verosimilitud para cada punto de datos es convexa.
Considerando datapoint fijo, podemos escribir negativo de la log-verosimilitud plazo como
$$-\langle \theta,\phi(y)\rangle+\log \sum_y \exp(\langle \theta,\phi(y)\rangle)$$
Primer término es lineal por lo que es suficiente para mostrar que el segundo término, conocido como el registro-normalizador, es convexa.
Escribo como $f(\mathbf{g}(\mathbf{\theta}))$ donde$f(\mathbf{y})=\log \sum_y \exp y$$g_y(\theta)=\langle \mathbf{\theta},\phi(y)\rangle$. Aquí $g$ es una función lineal, y $f$ es un conocido convexa de la función de llamada registro de suma-exp. Consulte la página 72 de Boyd Convexo Optimización del libro. La composición de una función convexa y una función lineal es convexa, véase la sección 3.2.2
Otro enfoque es utilizar el hecho de que el registro-normalizador es el cumulant de generación de función. Por ejemplo ver ejemplo 3.41 en Boyd del libro, o la Proposición 3.1 en Wainwright la "Gráfica de modelos, exponencial familias, y variacional de inferencia" manuscrito. Esto significa que la derivada segunda es la matriz de covarianza de estadística suficiente $\phi$ que por definición es positiva semi-definida, lo que significa que la Arpillera de la log-normalizador es positiva semi-definida. Positiva semi-definida de Hess garantiza la función es convexa, véase la sección 3.1.4 de Boyd del libro.
Técnicamente, el log-normalizador no es el tradicional cumulant de generación de función. El CGF es $g(\phi)=\log(Z(\theta+\phi))-\log(Z(\theta))$. Sin embargo, derivado de registro-normalizador evaluados en $\theta$ es la misma que la derivada de la CGF evaluados en $\mathbf{0}$, por lo que se produce cumulants como CGF.
No pude encontrar la plena prueba de la equivalencia, por lo general la gente omite porque es sólo varios pasos de aburrida álgebra. Una muy breve derivación de salida continua de espacio en la página 5 de Xinhua Zhang de la "Gráfica de los Modelos de" tesis. Creo que una sierra llena de derivación en Lawrence D. Brown "Fundamentos de estadística exponencial de las familias"
