Por qué optimizar la probabilidad máxima de registro en lugar de la probabilidad

66

En la mayoría de las tareas de aprendizaje automático en las que puede formular alguna probabilidad que debería maximizarse, en realidad optimizaríamos la probabilidad de lugar de la probabilidad de algunos parámetros . Por ejemplo, en el entrenamiento de máxima verosimilitud, generalmente es el log-verosimilitud. Al hacer esto con algún método de gradiente, esto implica un factor: $p$ $\log p$ $\theta$

\frac{\partial \log p}{\partial θ} = \frac{1}{p} \cdot \frac{\partial p}{\partial θ}

$\frac{\partial \log p}{\partial \theta} = \frac{1}{p} \cdot \frac{\partial p}{\partial \theta}$

Ver aquí o aquí para algunos ejemplos.

Por supuesto, la optimización es equivalente, pero el gradiente será diferente, por lo que cualquier método basado en gradiente se comportará de manera diferente (especialmente los métodos de gradiente estocástico). ¿Hay alguna justificación de que el gradiente funcione mejor que el gradiente ? $\log p$ $p$

probability optimization log-likelihood Albert
fuente

3

necesita notar que usualmente maximizamos la probabilidad usando derivados. Por otro lado, en muchos casos, la condición de independencia se aplica, lo que significa que la probabilidad es el producto de algunas funciones de densidad de probabilidad iid. Además, el producto de muchos valores pequeños (en el intervalo [0,1]) da como resultado un valor muy pequeño. Esto da como resultado una dificultad de cálculo.

TPArrow

@AlejandroRodriguez mira mi respuesta aquí para más detalles.

Paul

65

Los métodos de gradiente generalmente funcionan mejor optimizando que porque el gradiente de generalmente está más bien escalado . Es decir, tiene un tamaño que refleja de manera consistente y útil la geometría de la función objetivo, lo que hace que sea más fácil seleccionar un tamaño de paso apropiado y llegar al óptimo en menos pasos. $\log p(x)$ $p(x)$ $\log p(x)$

Para ver lo que quiero decir, comparar el proceso de optimización de gradiente para y . En cualquier punto , el gradiente de esSi multiplicamos eso por , obtenemos el tamaño de paso exacto necesario para llegar al óptimo global en el origen, sin importar qué $p(x) = \exp(-x^2)$ $f(x) = \log p(x) = -x^2$ $x$ $f(x)$

f^{'} (x) = - 2 x .

$f'(x) = -2x.$

1 / 2

$1/2$

x

$x$ es. Esto significa que no tenemos que trabajar demasiado para obtener un buen tamaño de paso (o "tasa de aprendizaje" en la jerga ML). No importa dónde esté nuestro punto inicial, solo establecemos nuestro paso a la mitad del gradiente y estaremos en el origen en un solo paso. Y si no sabemos el factor exacto que se necesita, podemos elegir un tamaño de paso alrededor de 1, hacer un poco de búsqueda de línea y encontraremos un gran tamaño de paso muy rápidamente, uno que funcione bien sin importar dónde es. Esta propiedad es robusta para la traducción y escala de . Si bien la escala hará que la escala de pasos óptima difiera de 1/2, al menos la escala de pasos será la misma sin importar cuál sea , por lo que solo tenemos que encontrar un parámetro para obtener una optimización eficiente basada en gradientes esquema.

x

$x$

f (x)

$f(x)$

f (x)

$f(x)$

x

$x$

En contraste, el gradiente de tiene propiedades globales muy pobres para la optimización. TenemosEsto multiplica el gradiente perfectamente agradable y de buen comportamiento con un factor que decae (más rápido que) exponencialmente a medida que aumenta. En , ya tenemos , por lo que un paso a lo largo del vector de gradiente es aproximadamente veces demasiado pequeño. Para obtener un tamaño de paso razonable hacia el óptimo, tendríamos que escalar el gradiente por el recíproco de eso, una enorme constante $p(x)$

p^{'} (x) = f^{'} (x) p (x) = - 2 x \exp (- x^{2}) .

$p'(x) = f'(x) p(x)= -2x \exp(-x^2).$

- 2 x

$-2x$

\exp (- x^{2})

$\exp(-x^2)$

x

$x$

x = 5

$x = 5$

\exp (- x^{2}) = 1.4 \cdot 10^{- 11}

$\exp(-x^2) = 1.4 \cdot 10^{-11}$

10^{- 11}

$10^{-11}$

\sim 10^{11}

$\sim 10^{11}$ . Un gradiente tan escalado es peor que inútil para fines de optimización: sería mejor intentar un paso de unidad en la dirección ascendente que establecer nuestro paso escalando contra . (En muchas variables, vuelve un poco más útil, ya que al menos obtenemos información direccional del gradiente, pero el problema de escala persiste).

p^{'} (x)

$p'(x)$

p^{'} (x)

$p'(x)$

En general, no hay garantía de que tenga propiedades de escala de gradiente tan buenas como este ejemplo de juguete, especialmente cuando tenemos más de una variable. Sin embargo, para casi cualquier problema no trivial, va a ser mucho mejor que . Esto se debe a que la probabilidad es un gran producto con un montón de términos, y el registro convierte ese producto en una suma, como se señala en varias otras respuestas. Siempre que los términos en la probabilidad se comporten bien desde el punto de vista de la optimización, su registro generalmente se comporta bien y la suma de las funciones se comporta bien. Por buen comportamiento me refiero a $\log p(x)$ $\log p(x)$ $p(x)$ $f''(x)$ no cambia demasiado o demasiado rápido, lo que lleva a una función casi cuadrática que es fácil de optimizar mediante métodos de gradiente. La suma de una derivada es la derivada de la suma, sin importar el orden de la derivada, lo que ayuda a garantizar que ese gran montón de términos de suma tenga una segunda derivada muy razonable.

Pablo
fuente

44

+1 Esta respuesta presenta y enfatiza puntos que llegan al meollo del asunto.

whuber

47

Underflow

La computadora usa una representación de fracciones de coma flotante de dígitos limitados, multiplicando tantas probabilidades se garantiza que será muy muy cercana a cero.

Con , no tenemos este problema. $log$

Uri Goren
fuente

3

+1 para estabilidad numérica: ¡esta y la respuesta de Yuril deberían ser una!

Alec Teal

1

Puede calcular el producto en el espacio logarítmico, por lo tanto, se convierte en una suma y luego transferirlo nuevamente. O calcula que es igual a . Entonces, la estabilidad numérica no es la cuestión.

\frac{\partial \log p}{\partial θ} \cdot p

$\frac{\partial \log p}{\partial \theta} \cdot p$

\frac{\partial p}{\partial θ}

$\frac{\partial p}{\partial \theta}$

Albert

1

Tenga en cuenta que la que mencionó es la multiplicación de las probabilidades de todos los eventos en la muestra, y es el elemento sujeto a un flujo inferior.

p

$p$

p

$p$

Uri Goren

55

@Filip La terminología en este hilo es poco aconsejable. Estamos discutiendo densidades de probabilidad , no probabilidades. Las densidades son arbitrarias: dependen de las unidades de medida. Además, para tamaños de muestra suficientes, la densidad de probabilidad de cualquier muestra simple de un modelo paramétrico será eventualmente menor que . En problemas grandes (con millones de datos), las densidades de probabilidad son habitualmente o menores. Incluso una muestra de tamaño de la distribución Normal estándar es casi segura de tener una densidad de probabilidad menor que .

2^{- 127}

$2^{-127}$

2^{- 1000000}

$2^{-1000000}$

80

$80$

2^{- 127}

$2^{-127}$

whuber

44

@FilipHaglund: whuber es correcto, sin embargo, el hecho de que sus densidades no es la observación crucial aquí. También podríamos estar discutiendo un proceso discreto y hablando de probabilidades reales (y, de hecho, el OP no dijo nada que excluya este caso). Pero estamos hablando de probabilidades para resultados muy específicos (p. Ej., Un millón de observaciones de alguna manera en particular). Es improbable un único resultado específico, pero en la inferencia bayesiana las razones de probabilidades son importantes, por lo que necesitamos saber cuánto más grande es una pequeña probabilidad de otra.

Meni Rosenfeld

34

El logaritmo de la probabilidad de múltiples probabilidades conjuntas se simplifica a la suma de los logaritmos de las probabilidades individuales (y la regla de la suma es más fácil que la regla del producto para la diferenciación)

$\log \left(\prod_i P(x_i)\right) = \sum_i \log \left( P(x_i)\right)$
El logaritmo de un miembro de la familia de distribuciones de probabilidad exponencial (que incluye la normal ubicua) es polinomial en los parámetros (es decir, la probabilidad máxima se reduce a mínimos cuadrados para las distribuciones normales)

$\log\left(\exp\left(-\frac{1}{2}x^2\right)\right) = -\frac{1}{2}x^2$
La última forma es más estable numéricamente y simbólicamente más fácil de diferenciar que la primera.
Por último, pero no menos importante, el logaritmo es una transformación monotónica que preserva las ubicaciones de los extremos (en particular, los parámetros estimados en máxima probabilidad son idénticos para la formulación original y la transformación transformada logarítmica)

TemplateRex
fuente

55

La razón 2 no se puede enfatizar lo suficiente. Para maximizar la probabilidad logarítmica de un modelo lineal con ruido gaussiano, solo tiene que resolver un problema de mínimos cuadrados, que equivale a resolver un sistema lineal de ecuaciones.

Paul

Las razones 1 y 3 solo describen cómo calcularlo. Puede calcularlo de esa manera y luego convertirlo nuevamente (multiplicar por ) para obtener . En realidad, es bastante común calcular en el espacio logarítmico la estabilidad numérica. Pero eso no explica por qué usas ese gradiente. La razón 4 tampoco es una razón por la cual el gradiente es mejor. También puedes hacerlo con muchas otras transformaciones. La razón 2 es interesante, pero todavía no estoy exactamente seguro de por qué el gradiente de un polinomio es mejor que el gradiente de otra función.

p

$p$

\frac{\partial p}{\partial θ}

$\frac{\partial p}{\partial \theta}$

\log p

$\log p$

Albert

@Albert, la derivada de un polinomio es un polinomio de un grado más bajo (en particular, cuadrático va a lineal), mientras que los exponenciales no se limitan a la diferenciación

TemplateRex

@TemplateRex: Sí, eso está claro. Pero estoy preguntando sobre las propiedades de convergencia en un método de gradiente estocástico.

Albert

25

Es mucho más fácil tomar una derivada de la suma de logaritmos que tomar una derivada del producto, que contiene, por ejemplo, 100 multiplicadores.

Yurii
fuente

10

Además, reduce los posibles problemas numéricos cuando los términos se vuelven muy pequeños o grandes.

Björn

8

Por el contrario, el OP proporciona implícitamente una excelente manera de calcular la derivada de cualquier producto de funciones no negativas: multiplicar la suma de las derivadas de los registros por el producto mismo. (Esta multiplicación se realiza mejor en términos de logaritmos, lo que elimina los problemas numéricos mencionados en el comentario de @ Björn, también.) Por lo tanto, "facilidad" no ofrece un poder explicativo real, ni aborda la pregunta más significativa sobre la comparación de los gradientes .

whuber

10

Como regla general, el problema de optimización más básico y fácil es optimizar una función cuadrática. Puede encontrar fácilmente el óptimo de dicha función sin importar dónde comience. La forma en que esto se manifieste depende del método específico, pero cuanto más se acerque su función a una cuadrática, mejor.

Como lo señaló TemplateRex, en una amplia variedad de problemas, las probabilidades que intervienen en el cálculo de la función de probabilidad provienen de la distribución normal, o son aproximadas por ella. Entonces, si trabajas en el registro, obtienes una buena función cuadrática. Mientras que si trabajas en las probabilidades, tienes una función que

No es convexo (la ruina de los algoritmos de optimización en todas partes)
Cruza múltiples escalas rápidamente y, por lo tanto, tiene un rango muy estrecho donde los valores de la función son indicativos de dónde dirigir su búsqueda.

¿Qué función preferirías optimizar, esto o esto ?

(Esto fue realmente fácil; en aplicaciones prácticas, su búsqueda puede comenzar tan lejos de lo óptimo que los valores y gradientes de la función, incluso si pudiera calcularlos numéricamente, serán indistinguibles de 0 e inútiles para la optimización algoritmo. Pero transformarse en una función cuadrática lo convierte en pan comido).

Tenga en cuenta que esto es completamente coherente con los problemas de estabilidad numérica ya mencionados. La razón por la que se requiere la escala de registro para trabajar con esta función es exactamente la misma razón por la que la probabilidad de registro se comporta mucho mejor (para la optimización y otros fines) que la original.

También podría abordar esto de otra manera. Incluso si no hubiera ninguna ventaja para el registro (que existe), de todos modos usaremos la escala de registro para derivaciones y cálculos, entonces, ¿qué razón hay para aplicar la transformación exp solo para calcular el gradiente? También podríamos ser consistentes con el registro.

Meni Rosenfeld
fuente

@TemplateRex: el registro de una función positiva convexa (hacia abajo) es convexo, pero lo contrario no es cierto. Las probabilidades no son convexas, por lo que no tienen nada que preservar, pero el registro es convexo. Mire las gráficas que vinculé: exp (-10x ^ 2) obviamente no es convexo, pero -10x ^ 2 sí.

Meni Rosenfeld

4

Al usar aumentamos el rango dinámico del algoritmo de optimización. La en las aplicaciones suele ser un producto de funciones. Por ejemplo, en la estimación de máxima verosimilitud, es el producto de la forma , donde Es la función de densidad, que puede ser mayor o menor que 1, por cierto. $\ln p$ $p$ $L(x|\theta)=\Pi_{i=1}^n f(x_i|\theta)$ $f(.)$

Así que, cuando es muy grande, es decir, muestra grande, su función de verosimilitud es por lo general muy lejos de 1: o está muy pequeño o muy grande, porque es una función de potencia . $n$ $L(.)$ $L\sim f(.)^n$

Al tomar un registro, simplemente mejoramos el rango dinámico de cualquier algoritmo de optimización, permitiéndole trabajar con valores extremadamente grandes o pequeños de la misma manera.

Aksakal
fuente

0

Algunas buenas respuestas ya se han dado. Pero recientemente encontré uno nuevo:

A menudo, se le da un gran conjunto de datos de entrenamiento , y define algún modelo probabilístico , y desea maximizar la probabilidad de . Se supone que son independientes, es decir, tiene Ahora, a menudo haces algún tipo de entrenamiento estocástico (mini-lote) basado en gradiente, es decir, en cada paso, para tu pérdida , optimizas para , es decir, $\mathcal{X}$ $p(x|\theta)$ $x \in \mathcal{X}$

p (X | θ) = \prod_{x \in X} p (x | θ) .

$p(\mathcal{X}|\theta) = \prod_{x\in\mathcal{X}} p(x|\theta) .$

L

$L$

L (X^{'} | θ)

$L(\mathcal{X'}|\theta)$

X^{'} \subset X

$\mathcal{X'} \subset \mathcal{X}$

θ^{'} := θ - \frac{\partial \sum_{x \in X^{'}} L (x | θ)}{\partial θ} .

$\theta' := \theta - \frac{\partial \sum_{x\in\mathcal{X'}} L(x|\theta)}{\partial \theta} .$ Ahora, estos pasos estocásticos se acumulan aditivamente. Por eso, desea la propiedad que en general Este es el caso de

L (X | θ) = \sum_{x \in X} L (x | θ) .

$L(\mathcal{X}|\theta) = \sum_{x\in\mathcal{X}} L(x|\theta) .$

L (x | θ) = - \log p (x | θ) .

$L(x|\theta) = -\log p(x|\theta) .$

Albert
fuente

Por qué optimizar la probabilidad máxima de registro en lugar de la probabilidad

Respuestas: