teoría del aprendizaje distribuido

La teoría del aprendizaje distribucional o aprendizaje de la distribución de probabilidad es un marco teórico en la teoría del aprendizaje computacional . Fue propuesta por Michael Kearns , Yishay Mansour , Dana Ron , Ronitt Rubinfeld , Robert Schapire y Linda Sellie en 1994 ^{[ 1 ]} y se inspiró en el marco PAC introducido por Leslie Valiant ^{[ 2 ]} .

En este marco, la entrada consiste en una serie de muestras extraídas de una distribución perteneciente a una clase específica de distribuciones. El objetivo es encontrar un algoritmo eficiente que, a partir de estas muestras, determine con alta probabilidad la distribución de la que se han extraído. Debido a su generalidad, este marco se ha utilizado en una gran variedad de campos, como el aprendizaje automático , los algoritmos de aproximación , la probabilidad aplicada y la estadística .

Este artículo explica las definiciones básicas, las herramientas y los resultados de este marco desde el punto de vista de la teoría de la computación.

Dejar${\displaystyle \textstyle X}$sea ​​el soporte de las distribuciones de interés. Como en el trabajo original de Kearns et al. ^{[ 1 ]} si${\displaystyle \textstyle X}$es finito se puede asumir sin pérdida de generalidad que${\displaystyle \textstyle X=\{0,1\}^{n}}$dónde${\displaystyle \textstyle n}$es el número de bits que deben usarse para representar cualquier${\displaystyle \textstyle y\en X}$Nos centramos en las distribuciones de probabilidad sobre${\displaystyle \textstyle X}$.

Existen dos posibles representaciones de una distribución de probabilidad.${\displaystyle \textstyle D}$encima${\displaystyle \textstyle X}$.

• función de distribución de probabilidad (o evaluador) un evaluador${\displaystyle \textstyle E_ {D}}$para${\displaystyle \textstyle D}$toma como entrada cualquier${\displaystyle \textstyle y\en X}$y produce un número real${\displaystyle \textstyle E_{D}[y]}$que denota la probabilidad de que${\displaystyle \textstyle y}$de acuerdo a${\displaystyle \textstyle D}$, es decir${\displaystyle \textstyle E_{D}[y]=\Pr[Y=y]}$si${\displaystyle \textstyle Y\sim D}$.
• generador un generador${\displaystyle \textstyle G_ {D}}$para${\displaystyle \textstyle D}$toma como entrada una cadena de bits verdaderamente aleatorios.${\displaystyle \textstyle y}$y resultados${\displaystyle \textstyle G_{D}[y]\en X}$según la distribución${\displaystyle \textstyle D}$El generador puede interpretarse como una rutina que simula el muestreo de la distribución.${\displaystyle \textstyle D}$dada una secuencia de lanzamientos de moneda justos .

Una distribución${\displaystyle \textstyle D}$Se dice que tiene un generador polinomial (respectivamente, un evaluador) si su generador (respectivamente, su evaluador) existe y puede calcularse en tiempo polinomial.

Dejar${\displaystyle \textstyle C_ {X}}$una clase de distribución sobre X, es decir${\displaystyle \textstyle C_ {X}}$es un conjunto tal que cada${\displaystyle \textstyle D\en C_ {X}}$es una distribución de probabilidad con soporte${\displaystyle \textstyle X}$. El${\displaystyle \textstyle C_ {X}}$también se puede escribir como${\displaystyle \textstyle C}$por simplicidad.

Para evaluar la capacidad de aprendizaje, es necesario tener una forma de medir qué tan bien se aproxima una distribución.${\displaystyle \textstyle D'}$se ajusta a la distribución muestreada${\displaystyle \textstyle D}$Existen varias formas de medir la divergencia entre dos distribuciones. Tres posibilidades comunes son:

• Divergencia de Kullback-Leibler
• Distancia de variación total de medidas de probabilidad
• distancia de Kolmogorov

La variación total y la distancia de Kolmogorov son métricas válidas , mientras que la divergencia KL no lo es (carece de simetría). Estas medidas se ordenan según su fuerza de convergencia : la proximidad en la divergencia KL implica proximidad en la variación total (mediante la desigualdad de Pinsker ), lo que a su vez implica proximidad en la distancia de Kolmogorov. Por lo tanto, un resultado de capacidad de aprendizaje demostrado con la divergencia KL se cumple automáticamente con las medidas más débiles, pero no a la inversa.

Dado que ciertas medidas pueden ser más apropiadas en aplicaciones específicas, utilizaremos${\displaystyle \textstyle d(D,D')}$para denotar una divergencia seleccionada entre la distribución${\displaystyle \textstyle D}$y la distribución${\displaystyle \textstyle D'}$.

La entrada básica que utilizamos para aprender una distribución es un número de muestras extraídas de esta distribución. Desde el punto de vista computacional, se supone que dicha muestra se proporciona en una cantidad de tiempo constante. Por lo tanto, es como tener acceso a un oráculo.${\displaystyle \textstyle GEN(D)}$que devuelve una muestra de la distribución${\displaystyle \textstyle D}$A veces, el interés radica, además de medir la complejidad temporal, en medir el número de muestras que deben utilizarse para aprender una distribución específica.${\displaystyle \textstyle D}$en clase de distribuciones${\displaystyle \textstyle C}$Esta cantidad se denomina complejidad de muestreo del algoritmo de aprendizaje.

Para que el problema del aprendizaje de la distribución sea más claro, considérese el problema del aprendizaje supervisado tal como se define en ^{[ 3 ]} . En este marco de la teoría del aprendizaje estadístico, un conjunto de entrenamiento${\displaystyle \textstyle S=\{(x_{1},y_{1}),\dots,(x_{n},y_{n})\}}$y el objetivo es encontrar una función objetivo${\displaystyle \textstyle f:X\rightarrow Y}$que minimiza alguna función de pérdida , por ejemplo, la función de pérdida cuadrática. Más formalmente${\displaystyle f=\arg \min _{g}\int V(y,g(x))d\rho (x,y)}$, dónde${\displaystyle V(\cdot ,\cdot )}$es la función de pérdida, por ejemplo${\displaystyle V(y,z)=(yz)^{2}}$y${\displaystyle \rho (x,y)}$la distribución de probabilidad según la cual se muestrean los elementos del conjunto de entrenamiento. Si la distribución de probabilidad condicional${\displaystyle \rho _{x}(y)}$Si se sabe entonces que la función objetivo tiene una forma cerrada${\displaystyle f(x)=\int _{y}yd\rho _{x}(y)}$. Entonces el conjunto${\displaystyle S}$es un conjunto de muestras de la distribución de probabilidad${\displaystyle \rho (x,y)}$Ahora bien, el objetivo de la teoría del aprendizaje distribucional es encontrar${\displaystyle \rho }$dado${\displaystyle S}$que se puede utilizar para encontrar la función objetivo${\displaystyle f}$.

Definición de capacidad de aprendizaje

Una clase de distribuciones${\displaystyle \textstyle C}$se denomina eficientemente aprendible si para cada${\displaystyle \textstyle \epsilon >0}$y${\displaystyle \textstyle 0<\delta \leq 1}$se le dio acceso a${\displaystyle \textstyle GEN(D)}$para una distribución desconocida${\displaystyle \textstyle D\en C}$Existe un algoritmo de tiempo polinomial.${\displaystyle \textstyle A}$, llamado algoritmo de aprendizaje de${\displaystyle \textstyle C}$, que produce un generador o un evaluador de una distribución${\displaystyle \textstyle D'}$de tal manera que

${\displaystyle \Pr[d(D,D')\leq \epsilon ]\geq 1-\delta }$

Si sabemos que${\displaystyle \textstyle D'\en C}$entonces${\displaystyle \textstyle A}$se denomina algoritmo de aprendizaje adecuado , de lo contrario se denomina algoritmo de aprendizaje inadecuado .

En algunos entornos la clase de distribuciones${\displaystyle \textstyle C}$es una clase con distribuciones bien conocidas que se pueden describir mediante un conjunto de parámetros. Por ejemplo${\displaystyle \textstyle C}$podría ser la clase de todas las distribuciones gaussianas${\displaystyle \textstyle N(\mu ,\sigma ^{2})}$En este caso, el algoritmo${\displaystyle \textstyle A}$debería poder estimar los parámetros${\displaystyle \textstyle \mu,\sigma}$. En este caso${\displaystyle \textstyle A}$se denomina algoritmo de aprendizaje de parámetros .

Obviamente, el aprendizaje de parámetros para distribuciones simples es un campo muy estudiado, conocido como estimación estadística, y existe una extensa bibliografía sobre diferentes estimadores para distintos tipos de distribuciones simples conocidas. Sin embargo, la teoría del aprendizaje de distribuciones se ocupa del aprendizaje de clases de distribuciones con descripciones más complejas.

En su obra fundamental, Kearns et al. abordan el caso en el que${\displaystyle \textstyle A}$se describe en términos de un circuito de tamaño polinomial finito y demostraron lo siguiente para algunas clases específicas de distribución. ^{[ 1 ]}

• ${\displaystyle \textstyle O}$distribuciones de compuertas para este tipo de distribuciones no hay un evaluador de tamaño polinomial, a menos que${\displaystyle \textstyle \#P\subseteq P/{\text{poly}}}$Por otro lado, esta clase se puede aprender de manera eficiente con un generador.
• Las distribuciones de puertas de paridad de esta clase se pueden aprender de manera eficiente tanto con el generador como con el evaluador.
• Mezclas de bolas de Hamming: esta clase se puede aprender de manera eficiente tanto con el generador como con el evaluador.
• Autómatas finitos probabilísticos: esta clase no se puede aprender de manera eficiente con un evaluador bajo la suposición de paridad ruidosa, que es una suposición de imposibilidad en el marco de aprendizaje PAC.

Una técnica muy común para encontrar un algoritmo de aprendizaje para una clase de distribuciones${\displaystyle \textstyle C}$es primero encontrar un pequeño${\displaystyle \textstyle \epsilon -}$portada de${\displaystyle \textstyle C}$.

Definición

Un conjunto${\displaystyle \textstyle C_{\epsilon }}$se llama${\displaystyle \textstyle \epsilon }$-portada de${\displaystyle \textstyle C}$si por cada${\displaystyle \textstyle D\en C}$hay un${\displaystyle \textstyle D'\in C_{\epsilon }}$de tal manera que${\displaystyle \textstyle d(D,D')\leq \epsilon }$. Un${\displaystyle \textstyle \epsilon -}$La cobertura es pequeña si tiene un tamaño polinomial con respecto a los parámetros que la describen.${\displaystyle \textstyle D}$.

Una vez que exista un procedimiento eficiente que para cada${\displaystyle \textstyle \epsilon >0}$encuentra un pequeño${\displaystyle \textstyle \epsilon -}$cubrir${\displaystyle \textstyle C_{\epsilon }}$de C entonces la única tarea restante es seleccionar de${\displaystyle \textstyle C_{\epsilon }}$la distribución${\displaystyle \textstyle D'\in C_{\epsilon }}$que se acerca más a la distribución${\displaystyle \textstyle D\en C}$Eso hay que aprenderlo.

El problema es que dado${\displaystyle \textstyle D',D''\in C_{\epsilon }}$No es trivial cómo podemos comparar${\displaystyle \textstyle d(D,D')}$y${\displaystyle \textstyle d(D,D'')}$para decidir cuál es el más cercano a${\displaystyle \textstyle D}$, porque${\displaystyle \textstyle D}$es desconocido. Por lo tanto, las muestras de${\displaystyle \textstyle D}$deben usarse para realizar estas comparaciones. Obviamente, el resultado de la comparación siempre tiene una probabilidad de error. Por lo tanto, la tarea es similar a encontrar el mínimo en un conjunto de elementos usando comparaciones ruidosas. Hay muchos algoritmos clásicos para lograr este objetivo. El más reciente que logra las mejores garantías fue propuesto por Daskalakis y Kamath ^{[ 4 ].} Este algoritmo establece un torneo rápido entre los elementos de${\displaystyle \textstyle C_{\epsilon }}$donde el ganador${\displaystyle \textstyle D^{*}}$de este torneo es el elemento que es${\displaystyle \textstyle \epsilon -}$cerca de${\displaystyle \textstyle D}$(es decir${\displaystyle \textstyle d(D^{*},D)\leq \epsilon }$) con probabilidad al menos${\displaystyle \textstyle 1-\delta }$Para ello, su algoritmo utiliza${\displaystyle \textstyle O(\log N/\epsilon ^{2})}$muestras de${\displaystyle \textstyle D}$y se ejecuta en${\displaystyle \textstyle O(N\log N/\epsilon ^{2})}$tiempo, donde${\displaystyle \textstyle N=|C_{\epsilon }|}$.

El aprendizaje de distribuciones simples y conocidas es un campo ampliamente estudiado, y existen numerosos estimadores que pueden utilizarse. Una clase de distribuciones más compleja es la de la suma de variables que siguen distribuciones simples. Estos procedimientos de aprendizaje guardan una estrecha relación con teoremas límite como el teorema del límite central, ya que tienden a analizar el mismo objeto cuando la suma tiende a infinito. Recientemente, se han publicado dos resultados que se describen aquí: el aprendizaje de distribuciones binomiales de Poisson y el aprendizaje de sumas de variables aleatorias enteras independientes. Todos los resultados que se presentan a continuación son válidos utilizando la distancia de variación total como medida de distancia.

Sean las variables aleatorias${\displaystyle \textstyle X\sim N(\mu _{1},\Sigma _{1})}$y${\displaystyle \textstyle Y\sim N(\mu _{2},\Sigma _{2})}$Definir la variable aleatoria${\displaystyle \textstyle Z}$que toma el mismo valor que${\displaystyle \textstyle X}$con probabilidad${\displaystyle \textstyle w_{1}}$y el mismo valor que${\displaystyle \textstyle Y}$con probabilidad${\displaystyle \textstyle w_{2}=1-w_{1}}$. Entonces si${\displaystyle \textstyle F_{1}}$es la densidad de${\displaystyle \textstyle X}$y${\displaystyle \textstyle F_{2}}$es la densidad de${\displaystyle \textstyle Y}$la densidad de${\displaystyle \textstyle Z}$es${\displaystyle \textstyle F=w_{1}F_{1}+w_{2}F_{2}}$. En este caso${\displaystyle \textstyle Z}$Se dice que sigue una mezcla de gaussianas. Pearson ^{[ 8 ]} fue el primero en introducir la noción de mezclas de gaussianas en su intento de explicar la distribución de probabilidad de la que obtuvo los mismos datos que quería analizar. Así, después de realizar muchos cálculos a mano, finalmente ajustó sus datos a una mezcla de gaussianas. La tarea de aprendizaje en este caso es determinar los parámetros de la mezcla.${\displaystyle \textstyle w_{1},w_{2},\mu _{1},\mu _{2},\Sigma _{1},\Sigma _{2}}$.

El primer intento de resolver este problema fue de Dasgupta . ^{[ 9 ]} En este trabajo, Dasgupta supone que las dos medias de las gaussianas están lo suficientemente alejadas entre sí. Esto significa que existe un límite inferior en la distancia.${\displaystyle \textstyle ||\mu _{1}-\mu _{2}||}$Utilizando esta suposición, Dasgupta y muchos científicos después de él pudieron aprender los parámetros de la mezcla. El procedimiento de aprendizaje comienza con la agrupación de las muestras en dos grupos diferentes minimizando alguna métrica. Utilizando la suposición de que las medias de las gaussianas están muy alejadas entre sí con alta probabilidad, las muestras en el primer grupo corresponden a muestras de la primera gaussiana y las muestras en el segundo grupo a muestras de la segunda. Ahora que las muestras están particionadas${\displaystyle \textstyle \mu _{i},\Sigma _{i}}$se puede calcular a partir de estimadores estadísticos simples y${\displaystyle \textstyle w_{i}}$comparando la magnitud de los grupos.

Si${\displaystyle \textstyle GM}$es el conjunto de todas las mezclas de dos gaussianas, utilizando el procedimiento anterior se pueden demostrar teoremas como el siguiente.

Teorema ^{[ 9 ]}

Dejar${\displaystyle \textstyle D\in GM}$con${\displaystyle \textstyle ||\mu _{1}-\mu _{2}||\geq c{\sqrt {n\max(\lambda _{max}(\Sigma _{1}),\lambda _{max}(\Sigma _{2}))}}}$, dónde${\displaystyle \textstyle c>1/2}$y${\displaystyle \textstyle \lambda _{max}(A)}$el mayor valor propio de${\displaystyle \textstyle A}$, entonces hay un algoritmo que dado${\displaystyle \textstyle \epsilon >0}$,${\displaystyle \textstyle 0<\delta \leq 1}$y acceso a${\displaystyle \textstyle GEN(D)}$encuentra una aproximación${\displaystyle \textstyle w'_{i},\mu '_{i},\Sigma '_{i}}$de los parámetros tales que${\displaystyle \textstyle \Pr[||w_{i}-w'_{i}||\leq \epsilon ]\geq 1-\delta }$(respectivamente para${\displaystyle \textstyle \mu _{i}}$y${\displaystyle \textstyle \Sigma _{i}}$La complejidad de muestreo de este algoritmo es${\displaystyle \textstyle M=2^{O(\log ^{2}(1/(\epsilon \delta )))}}$y el tiempo de ejecución es${\displaystyle \textstyle O(M^{2}d+Mdn)}$.

El resultado anterior también podría generalizarse en${\displaystyle \textstyle k-}$mezcla de gaussianas. ^{[ 9 ]}

Para el caso de una mezcla de dos gaussianas, existen resultados de aprendizaje sin asumir la distancia entre sus medias, como el siguiente, que utiliza la distancia de variación total como medida de distancia.

Teorema ^{[ 10 ]}

Dejar${\displaystyle \textstyle F\in GM}$entonces hay un algoritmo que dado${\displaystyle \textstyle \epsilon >0}$,${\displaystyle \textstyle 0<\delta \leq 1}$y acceso a${\displaystyle \textstyle GEN(D)}$hallazgos${\displaystyle \textstyle w'_{i},\mu '_{i},\Sigma '_{i}}$de tal manera que si${\displaystyle \textstyle F'=w'_{1}F'_{1}+w'_{2}F'_{2}}$, dónde${\displaystyle \textstyle F'_{i}=N(\mu '_{i},\Sigma '_{i})}$entonces${\displaystyle \textstyle \Pr[d(F,F')\leq \epsilon ]\geq 1-\delta }$La complejidad de la muestra y el tiempo de ejecución de este algoritmo son:${\displaystyle \textstyle {\text{poly}}(n,1/\epsilon ,1/\delta ,1/w_{1},1/w_{2},1/d(F_{1},F_{2}))}$.

La distancia entre${\displaystyle \textstyle F_{1}}$y${\displaystyle \textstyle F_{2}}$no afecta la calidad del resultado del algoritmo sino solo la complejidad de la muestra y el tiempo de ejecución. ^{[ 9 ] [ 10 ]}