Estimación computacionalmente eficiente del modo multivariante

Question

La versión corta: ¿Cuál es el método más eficiente desde el punto de vista computacional para estimar la moda de un conjunto de datos multidimensionales, muestreados a partir de una distribución continua?

La versión larga: Tengo un conjunto de datos del que necesito estimar la moda. La moda no coincide con la media o la mediana. Un ejemplo se muestra a continuación, este es un ejemplo 2D, pero una solución N-D sería mejor:

Actualmente, mi método es

1. Calcular la estimación de la densidad del núcleo en una cuadrícula igual a la resolución del modo
2. Busca el mayor punto calculado

Obviamente, esto calcula la KDE en muchos puntos no plausibles, lo que es especialmente malo si hay muchos puntos de datos de altas dimensiones o espero una buena resolución en el modo.

Una alternativa sería utilizar un recocido simulado, un algoritmo genético, etc. para encontrar el pico global en la KDE.

La pregunta es si existe un método más inteligente para realizar este cálculo.

Answer 1

Si su interés principal son los problemas bidimensionales, yo diría que la estimación de la densidad del núcleo es una buena opción porque tiene buenas propiedades asintóticas (tenga en cuenta que no estoy diciendo que sea la mejor). Ver por ejemplo

Parzen, E. (1962). Sobre la estimación de una función de densidad de probabilidad y modo . Anales de Estadística Matemática 33: 1065-1076.

de Valpine, P. (2004). Verosimilitudes del espacio de estado de Monte Carlo mediante la estimación de la densidad del núcleo posterior ponderada . Revista de la Asociación Americana de Estadística 99: 523-536.

Para dimensiones superiores (4+) este método es realmente lento debido a la conocida dificultad de estimar la matriz de ancho de banda óptima, véase .

Ahora, el problema con el comando ks en el paquete KDE es, como has mencionado, que evalúa la densidad en una malla específica que puede ser muy limitante. Este problema se puede resolver si se utiliza el paquete KDE para estimar la matriz de ancho de banda, utilizando por ejemplo Hscv implementa el estimador de densidad Kernel y luego optimiza esta función utilizando el comando optim . Esto se muestra a continuación utilizando datos simulados y un núcleo gaussiano en R .

rm(list=ls())

# Required packages
library(mvtnorm)
library(ks)

# simulated data
set.seed(1)
dat = rmvnorm(1000,c(0,0),diag(2))

# Bandwidth matrix
H.scv=Hlscv(dat)

# [Implementation of the KDE](http://en.wikipedia.org/wiki/Kernel_density_estimation)
H.eig = eigen(H.scv)
H.sqrt = H.eig$vectors %*% diag(sqrt(H.eig$values)) %*% solve(H.eig$vectors)
H = solve(H.sqrt)
dH = det(H.scv)

Gkde = function(par){
return( -log(mean(dmvnorm(t(H%*%t(par-dat)),rep(0,2),diag(2),log=FALSE)/sqrt(dH))))
}

# Optimisation
Max = optim(c(0,0),Gkde)$par
Max

Los estimadores de forma restringida suelen ser más rápidos, por ejemplo

Cule, M. L., Samworth, R. J. y Stewart, M. I. (2010). Estimación por máxima verosimilitud de una densidad logarítmica multidimensional . Revista Royal Statistical Society B 72: 545-600.

Pero son demasiado pico para este fin.

El problema en las altas dimensiones es difícil de atacar independientemente del método utilizado debido a la naturaleza de la propia pregunta. Por ejemplo, el método propuesto en otra respuesta (desplazamiento de la media) está bien, pero se sabe que la estimación de la derivada de una densidad es aún más difícil que la estimación de la propia densidad en términos de errores (no estoy criticando esto, sólo señalando lo difícil que es este problema). Entonces, es probable que se necesiten miles de observaciones para estimar con exactitud el modo en dimensiones superiores a $4$ en problemas no relacionados con los juguetes.

Otros métodos que puede considerar utilizar son: ajustar una mezcla finita multivariada de normales (u otras distribuciones flexibles) o

Abraham, C., Biau, G. y Cadre, B. (2003). Estimación simple de la moda de una densidad multivariante . La Revista Canadiense de Estadística 31: 23-34.

Espero que esto ayude.

Answer 2

El método que se ajustaría a lo que quieres hacer es el desplazamiento medio algoritmo. Esencialmente, el desplazamiento de la media se basa en moverse a lo largo de la dirección del gradiente, que se estima de forma no paramétrica con la "sombra", $K'$ de un núcleo determinado $K$ . A saber, si la densidad $f(x)$ se estima mediante $K$ entonces $\nabla f(x)$ se estima mediante $K'$ . Los detalles de la estimación del gradiente de una densidad de núcleo se describen en Fukunaga y Hostetler (1975), que también introdujeron el algoritmo de desplazamiento de la media.

También se ofrece una exposición muy detallada del algoritmo en este entrada de blog .

REFERENCIAS:

• K. Fukunaga y L. Hostetler, "The estimation of the gradient of a density function, with applications in pattern recognition, " IEEE Transactions on Information Theory 21(1), enero de 1975.

Answer 3

Recientemente hemos publicado un artículo que sugiere un estimador de modo rápido y consistente.

P.S. Ruzankin y A.V. Logachov (2019). Un estimador rápido de modos en el espacio multidimensional. Cartas de Estadística y Probabilidad

Nuestro estimador tiene una complejidad de tiempo $O(dn)$ , donde $d$ es la dimensionalidad y $n$ es el número de puntos observados. Aunque nuestro método puede no ser tan preciso como los otros ya mencionados aquí, escribimos pruebas completas para la consistencia y la consistencia fuerte.

También sugeriría los nuevos estimadores de modo de varianza mínima de mi reciente artículo

P.S. Ruzankin (2020). Una clase de estimadores de modo no paramétricos. Comunicaciones en estadística - Simulación y cálculo

Estos estimadores tienen una complejidad temporal $O(dn^2)$ para $n$ puntos en ${\mathbb R}^d$ . Véase allí la sección 2.3. Los estimadores tienen una precisión similar a la de los algoritmos conocidos.