¿Por qué el L2 norma heurística de trabajo en la medición de la homogeneidad de las distribuciones de probabilidad?

Question

Para empezar, por favor vaya a través de esta pregunta con respecto a la medición de la falta de uniformidad en las distribuciones de probabilidad.

Entre varias buenas respuestas, user495285 ha sugerido una heurística de simplemente tomar la L2 norma de un vector cuyos valores agregar a 1. Yo me he encontrado en mis experimentos que realmente funciona muy bien para la mayoría de las aplicaciones prácticas y, generalmente, es performante.

Ahora estoy en el proceso de escribir un artículo acerca de un algoritmo de aprendizaje de máquina, que hace uso de este heurístico. Sin embargo, tengo que dar al menos algunos antecedentes que explican por qué esta heurística funciona razonablemente bien.

Dado que la toma de L2 normas para este propósito, es probablemente sólo una heurística, entiendo que no hay una base teórica sólida, pero que sin embargo necesitan una intuición sobre lo que podría estar pasando, así que por lo menos puedo explicar en el papel y soy claro con respecto a lo que está pasando. Idealmente, si hay una explicación adecuada disponible que puedo citar directamente, la amabilidad de compartirlo aquí.

Miré la web y podría encontrar algunos documentos que hablan sobre el uso de la L2 normas en el contexto de la medición de la uniformidad, pero no estoy seguro de si dan una explicación intuitiva de por qué funciona y si son citables. Aquí están los documentos:

1. Examen de la Homogeneidad de las Distribuciones
2. Relación y Diferencia de la l1 y la l2 Normas y Dispersas Representación Coherente con los Diccionarios
3. Sublinear algoritmos en tiempo

Además, si usted tiene otras ideas acerca de cómo medir la no uniformidad en la distribución o usted podría decir por qué cierta medida es mejor que los demás, por favor hágamelo saber.

Answer 1

Creo que la intención de la aplicación es que

• frecuencias $f_i$ $n$ elementos $i=1,2,\ldots, n$ han sido observados; y

• usted se está preguntando si estas frecuencias son consistentes con un subyacente distribución uniforme en el que todas las observaciones son (a) independiente y (b) igualmente probables.

El "vector" en cuestión es la normalizado tupla de la relación de frecuencias,

$$p = (p_1, p_2, \ldots, p_n) = \left(\frac{f_1}{f}, \frac{f_2}{f}, \ldots, \frac{f_n}{f}\right)$$

con $f = f_1 + f_2 + \cdots + f_n$ siendo el número total de observaciones. El $L_2$ norma de $p$ es, por definición, la raíz cuadrada de

$$||p||_2^2 = p_1^2 + p_2^2 + \cdots + p_n^2.$$

Usando esto como una medida de la homogeneidad de la $p_i$ cuenta con una intuitiva justificación matemática--no se hacen más grandes como el $p_i$ variar más, pero carece de justificación estadística. Vamos a ver si podemos ponerlo sobre una base sólida.

Para ello, observe que el valor promedio de la $p_i$ $\bar p = 1/n$ (debido a que se suma a la unidad y no se $n$ de ellos). La uniformidad en realidad no se refieren a los valores reales de la $p_i$: se refiere a cómo varían alrededor de su valor esperado. Acerquémonos, pues, calcular la variación y tratar de relacionarlo con los $L_2$ norma. Un conocido algebraicas resultado (fácil de probar) es

$$||p||_2^2 = \sum_i \left(p_i - \frac{1}{n}\right)^2 + \frac{1}{n}.$$

Ahora el número de observaciones $f$ debe jugar un papel fundamental, ya que sin esa información no tenemos una buena idea de cómo la variable de las frecuencias observadas deben ser. Es natural introducir un factor de $f^2$ con el fin de eliminar los denominadores en la $p_i = f_i/f$:

$$f^2||p||_2^2 = \sum_i \left(f p_i - \frac{f}{n}\right)^2 + \frac{f^2}{n} = \sum_i \left(f_i - \frac{f}{n}\right)^2 + \frac{f^2}{n}.\tag{1}$$

Este es inmediatamente reconocible como casi igual a la de la chi-cuadrado de la estadística para la prueba de homogeneidad: las frecuencias esperadas ( $E_i$ )$f/n$, mientras que las frecuencias observadas ( $O_i$ )$f_i$. Esta estadística, por definición, es la suma de las diferencias estandarizadas,

$$\chi^2 = \sum_i \frac{(O_i - E_i)^2}{E_i} = \sum_i \frac{(f_i - f/n)^2}{f/n}.$$

Así pues, nos dividen $(1)$ $f/n$ a introducir $\chi^2$:

$$n f ||p||_2^2 = \sum_i \frac{(f_i - f/n)^2}{f/n} + f = \chi^2 + f.$$

Finalmente podemos aislar una diferencia estadísticamente significativa expresión:

$$f\left(n||p||_2^2 - 1\right) = \chi^2.$$

Esto muestra que hasta una transformación afín determinado por el número de categorías de $n$ y el número total de observaciones $f$, la plaza de la $L_2$ norma de la frecuencia relativa del vector es un estándar de la estadística utilizada para medir la uniformidad de la distribución de frecuencia. Esa es la razón por la $L_2$ norma puede ser de valor.

Pero, ¿por qué no usar simplemente el $\chi^2$ estadística en el primer lugar?

Answer 2

¿Por qué este método funciona ? Digamos $x+y = 1$; $(x+y)^2 = 1$; $\texttt{norm}^2 + 2xy = 1$; $xy$ es máxima cuando el $x=y$ (uniforme) y por lo tanto la norma debe ser menor. Por lo tanto, menor la norma significa uniformidad. Usted puede extender la misma a los vectores de longitud de más de 2.

Sin embargo, la idea de cambiar la escala con $d$ es simplemente un método heurístico. Usted puede ser que desee omitir.

A su siguiente pregunta. Se pueden utilizar varios métodos para resolver este problema. Algunas de las medidas son:

1. KL divergencia a partir de una distribución uniforme.
2. Producto escalar del vector convertir un vector unitario con un distribuida uniformemente en la unidad de vector de la misma longitud.
3. Varianza

Answer 3

@whuber la respuesta es la más generalizada y elaborados, como de costumbre. Al mismo tiempo, @Aveek del matemático simple observación también hace cosas bastante intuitivo. Me gustaría extender su observación un poco.

Como se señaló, $$norm^2 + 2xy = 1$$ Por lo tanto, $$norm^2 = 1 - 2xy$$ $$norm^2 = 1 - 2x(1-x) $$ $$norm^2 = 1 - 2x + 2x^2 $$ Por lo tanto podemos indicar el $norm^2$ función de: $$f = 2x^2 - 2x + 1$$ Nos encontramos con el mínimo de $f$ tomando sus derivados e igualando a $0$, es decir,$$4x - 2 = 0$$which gives us: $$x = 0.5$$ que es$1/n$$n = 2$, es decir, la distribución uniforme. Por lo tanto observamos que el mínimo de la $(L_2)^2$ función (en $R^2$ en este caso) es $0.5$.