Máximo Global de una suma de Gaussianas

Question

Supongamos que tengo la suma ponderada de $n$ Gauss funciones con diferentes medias y desviaciones estándar, $$f(x) = \sum_{i=1}^n a_i\exp\left(-\frac{(x-\mu_i)^2}{2\sigma_i^2}\right).$$ Todos los pesos $a_i$ son positivos. Quiero encontrar la posición de la máxima global de $f$.

Claramente $f$ no es cóncava y puede tener múltiples los máximos locales. Sin embargo, se siente como cada máximo local debe estar cerca de la cima $\mu_i$ de una de las Gaussianas.

Supongamos que realizar gradiente de ascenso $n$ veces a partir de $x = \mu_i$$i = 1, 2,\ldots, n$. Me garantiza que voy a encontrar a todos los locales de maxima, y por lo tanto el máximo global? Existe una mejor estrategia para encontrar el máximo global?

Answer 1

Desde $x$ es unidimensional, usted puede hacer una simple rejilla de la búsqueda con multa suficiente cuadrículas, lo que garantiza a encontrar el óptimo global. No es necesario en el caso de que cada uno de los máximo local está muy cerca de a $\mu_i$. De hecho, los nuevos locales maxima que se puede crear entre dos distante $\mu_i$s si su $\sigma_i$s son lo suficientemente grandes.

EDITAR

Para ver cómo la cuadrícula de búsqueda le dará garantías global de la solución óptima. En primer lugar, calcular la cota de $f'(x)$:

$$|f'(x)| \le \sum_i a_i \left|\frac{x-\mu_i}{\sigma_i^2}\right|\exp\left(-\frac{(x-\mu_i)^2}{2\sigma_i^2}\right)$$

puesto que (tomando derivados)

$$\frac{|x|}{\sigma^2}\exp\left(-\frac{x^2}{2\sigma^2}\right) \le \frac{1}{\sigma}e^{-1/2}$$

tenemos $$|f'(x)| \le e^{-1/2}\sum_i \frac{a_i}{\sigma_i} \equiv M$$

Por otro lado, existe una lo suficientemente grande $K$, de modo que $|f(x)| \le \max_i a_i$ $x \notin [-K,K]$ y no puede ser la solución óptima global. Por lo tanto la brecha $[-K, K]$ a $\lceil 2KM/\epsilon \rceil$ papeleras $[l_j, u_j]$, de modo que $u_j - l_j \le \epsilon/M$. Por lo tanto desde $|f'(x)|\le M$, dentro de cada bin $j$ existe $c_j$, de modo que

$$c_j - \frac{\epsilon}{2}\le f(x) \le c_j + \frac{\epsilon}{2}$$

Deje $j^* = \arg\max_j c_j$. Entonces cualquier $\hat x^* \in [l_{j^*}, u_{j^*}]$ da $f(\hat x^*)$ que es en la mayoría de las $\epsilon$ peor que el verdadero óptimo global.

Tengo que admitir que a partir de este análisis, no es posible proporcionar un tiempo finito algoritmo que encontrar la exacta óptimo global.

Answer 2

He aquí un resultado parcial de decisiones de la intuición en mi pregunta de rigor.

Deje $f(x) = \sum\limits_{i=1}^n g_i(x)$, donde $$g_i(x) = a_i\exp\left(-\frac{(x-\mu_i)^2}{2\sigma_i^2}\right)$$ are the $n$ Gaussianas ser sumados.

Supongamos $x$ es un punto crítico de $f$, $f'(x)=0$. Para ser un máximo local, $f''(x)$ debe ser negativo. Pero $f''(x)=\sum\limits_{i=1}^ng_i''(x)$, y $$g_i''(x)=\frac{(x-\mu_i)^2-\sigma_i^2}{\sigma_i^4}g(x)$$ is negative only when $x\in[\mu_i-\sigma_i,\mu_i+\sigma_i]$. So any local maximum can only occur within $\sigma_i$ of a $\mu_i$.

Esto nos permite buscar sólo dentro de la potencialmente más pequeños de la unión de los intervalos ($\bigcap\limits_{i=1}^n [\mu_i-\sigma_i,\mu_i+\sigma_i]$ más que en el aproximadamente $[\min\mu_i,\max\mu_i]$ como debo interpretar Yuandong la respuesta. Esto es útil si el $\mu_i$ son ampliamente separados. Sin embargo, $f$ no está garantizado a ser cóncava en cualquiera de estos intervalos, por lo que no podemos estar seguros de encontrar un máximo global simplemente por gradiente de ascenso. Uno puede conseguir dentro de $\epsilon$ de la máxima global por una cuadrícula de búsqueda con el tamaño de paso de $\epsilon/M$ donde $M$ como se define en el Yuandong la respuesta, pero sería bueno saber si alguno convergencia más rápida posible.