Algoritmos de modelo de consulta estadística?

Hice esta pregunta en preguntas y respuestas validadas cruzadas, pero parece que está relacionada con CS mucho más que las estadísticas.

¿Me puede dar ejemplos de algoritmos de aprendizaje automático que aprendan de las propiedades estadísticas del conjunto de datos, no de las observaciones individuales, es decir, empleen el modelo de consulta estadística ?

Casi todos los algoritmos que funcionan en el modelo PAC (con la excepción de los algoritmos de aprendizaje de paridad) pueden funcionar en el modelo SQ. Ver, por ejemplo, este artículo de Blum et al. en el que varios algoritmos populares se traducen en sus equivalentes SQ ( Privacidad práctica: el marco de trabajo SuLQ ). El documento se refiere en principio a la "privacidad", pero puede ignorarlo: en realidad solo se trata de implementar algoritmos con consultas SQ.

El aprendizaje agnóstico, por otro lado, es mucho más difícil en el modelo SQ: aparte de los problemas computacionales (aunque estos son importantes), la complejidad de la muestra requerida para el aprendizaje agnóstico es aproximadamente la misma que la requerida para el aprendizaje exacto, si realmente tiene acceso a Los puntos de datos. Por otro lado, el aprendizaje agnóstico se vuelve mucho más difícil en el modelo SQ: por lo general, deberá realizar muchas consultas superpolinomialmente, incluso para clases tan simples como disyunciones monótonas. Consulte este documento de Feldman ( Una caracterización completa del aprendizaje de consultas estadísticas con aplicaciones a la capacidad de evolución ) o este documento reciente de Gupta et al. ( Conjunciones de publicación privada y la barrera de consulta estadística )

El modelo SQ se realizó para analizar el aprendizaje tolerante al ruido, es decir, un algoritmo que funciona realizando consultas estadísticas funcionará bajo el ruido de clasificación. Como dijo Aaron, la mayoría de los algoritmos PAC que tenemos tienen equivalentes en el modelo SQ. La única excepción es la eliminación gaussiana, que se usa para aprender paridades (incluso se puede usar una aplicación inteligente de la misma).para aprender las paridades de tamaño log (n) loglog (n) en el modelo de clasificación de ruido). También sabemos que las paridades no se pueden aprender con consultas estadísticas, y resulta que las clases más interesantes, como los árboles de decisión, pueden simular funciones de paridad. Entonces, en nuestra búsqueda para obtener algoritmos de aprendizaje PAC para muchas clases interesantes (como árboles de decisión, DNF, etc.), sabemos que necesitamos algoritmos de aprendizaje fundamentalmente nuevos que no funcionan en el modelo de consulta estadística.

Me gustaría aclarar un poco la respuesta de Aaron. Casi todos los algoritmos agnósticos (una vez más, excepto cualquier cosa que use la eliminación gaussiana) pueden funcionar en el modelo SQ. Naturalmente, el aprendizaje agnóstico es más difícil que el aprendizaje no agnóstico, pero esta es una pregunta independiente.