Sobre la dureza de datos para aprender

Question

Casi en todos los textos que se están discutiendo los teoremas de aprendizaje estadístico, se supone que el análisis de arbitrario desconocido de distribución (el peor caso). Pero en la práctica los diferentes problemas (datos diferentes) tienen diferentes niveles de dureza, por ejemplo lineal separables de datos es más fácil de aprender que los datos que son menos (o no) separables por hyperplanes. Hay obras en la formalización de la dureza de datos (similar a lo hecho en la teoría de la complejidad)

Nota: no estoy seguro de si mismo como el análisis de VC-dimensión o no, pero creo que no lo es.

Answer 1

La noción de instancia de la dureza de mayo de la dirección de lo que usted está buscando. Ejemplo de la dureza de la postula que cada instancia del conjunto de datos tiene una dureza de la propiedad que indica la probabilidad de que va a ser clasificados erróneamente por un algoritmo de aprendizaje supervisado. En un sentido, el ejemplo de la dureza se ve en la dureza de cada individuo en lugar de la dureza de los datos. Sin embargo, el ejemplo de la dureza puede ser agregada a la esencia de caracterizar la dureza del conjunto de datos. Como con todos los métodos de agregación, sin embargo, se pierde algo de información cuando los datos agregados. Esperemos que esto puede dar alguna dirección.

Answer 2

Estadísticos de la teoría del aprendizaje generalmente se ocupa de la complejidad de la muestra, es decir, cuántas muestras necesito para producir una hipótesis de tener un error con una probabilidad alta. Más concretamente, si $S$ es un conjunto de muestras y $h_S$ es la hipótesis devueltas por algún algoritmo de aprendizaje cuando se administra $S$ como entrada, normalmente uno ve a producir declaraciones de la forma $$ P(\text{err}(h_S)\le \epsilon) \ge 1 - \delta $$ si $|S| \ge m$ algunos $m = \text{poly}(1/\epsilon, 1/\delta)$.

En el anterior hemos ignorado completamente cómo $h_S$ fue generado. Computacional Teoría de Aprendizaje es el campo que se ocupa de estos tipos de problemas computacionales. Uno puede, por ejemplo, requieren que el algoritmo que produce $h_S$ a ejecutar en el tiempo $\text{poly}(1/\epsilon, 1/\delta)$, observe que la anterior es una condición necesaria para que esto sea posible. Otras cosas comunes estudiados son ¿qué pasa si el algoritmo tiene acceso a información diferente (miembros de las consultas de permitir que el algoritmo de aprendizaje para la consulta de oracle para la etiqueta de los puntos que se elige), cuántos errores hace un alumno en un aprendizaje en línea, ¿qué sucede si la retroalimentación es limitado como en el aprendizaje por refuerzo, etc.

Hay mucho más y es un campo fascinante, pero en lugar de una lista de ellos, voy a señalar que el libro Una Introducción a la Teoría del Aprendizaje Computacional por Kearns y Vazirani, que es una gran introducción al tema.