Me parece que los expertos en aprendizaje automático / minería de datos están familiarizados con P y NP, pero rara vez hablan de algunas de las clases de complejidad más sutiles (por ejemplo, NC, BPP o IP) y sus implicaciones para analizar los datos de manera efectiva. ¿Hay alguna encuesta de trabajo haciendo esto?
cc.complexity-theory
reference-request
machine-learning
Mike Izbicki
fuente
fuente
Respuestas:
Existe alguna diferencia inherente o disparidad de enfoques entre los dos campos del aprendizaje automático aplicado y la teoría de TCS / complejidad.
Aquí hay un taller reciente sobre el tema en el Centro de Intractabilidad Computacional, Princeton, con muchos videos.
En TCS, un área principal de estudio del "aprendizaje", a veces de forma confusa, incluso también llamada "aprendizaje automático", se llama teoría PAC, que significa Probablemente Aproximadamente Correcta. su origen a principios de la década de 1980 es anterior a una investigación mucho más moderna sobre el "aprendizaje automático". Wikipedia lo llama parte de la teoría de aprendizaje computacional de campo . PAC a menudo se refiere a los resultados del aprendizaje de fórmulas booleanas con muestras estadísticas de las distribuciones, etc., y la precisión alcanzable del aprendizaje con varios algoritmos o muestras limitadas. Esto se estudia de una manera teórica rigurosa con vínculos a clases de complejidad. Pero no es tanto una página de estudio aplicado y wikipedias sobre aprendizaje automático que ni siquiera lo enumera.
La complejidad computacional de la tesis doctoral de Machine Learning por Kearns
Xing se desliza sobre el aprendizaje automático (PAC)
fuente