Existe-t-il un travail combinant l'apprentissage automatique et les formes plus exotiques de la théorie de la complexité?

13

Il me semble que les experts en apprentissage automatique / exploration de données connaissent bien P et NP, mais parlent rarement de certaines des classes de complexité les plus subtiles (par exemple NC, BPP ou IP) et de leurs implications pour une analyse efficace des données. Y a-t-il une enquête sur le travail qui le fait?

cc.complexity-theory reference-request machine-learning Mike Izbicki
la source
2
Aucune enquête à ma connaissance, mais consultez ce pointeur sur «l'apprentissage quantique» (# 5) de ce post: blog.computationalcomplexity.org/2012/10/quantum-workshop.html
Suresh Venkat
l'apprentissage automatique attaque régulièrement des problèmes très difficiles qui sont prob en dehors de NP pour une optimisation "globale" mais à l'intérieur de NP ou moins dur que celui pour une optimisation "locale". donc tout le concept de classe de complexité devient flou quand on optimise pour des résultats "assez bons" qui sont mesurés davantage par des mesures de qualité dépendantes de l'application et dans un sens ne sont pas vraiment connus apriori pour exécuter le ou les algorithmes ....
vzn
@vzn Pour moi, cette subtilité semble être une raison de plus de prêter attention à la complexité! Cela pourrait fournir des informations très intéressantes.
Mike Izbicki
il existe certainement des liens entre la théorie de l'apprentissage, la complexité des circuits et la cryptographie. mais c'est le coin de la théorie de l'apprentissage qui est un peu éloigné de la pratique de l'apprentissage automatique. si vous êtes intéressé, je peux trouver quelques conseils
Sasho Nikolov
oui, un autre exemple, les BDD (diagrammes de décision binaires) ont été utilisés dans les algorithmes de base de données / exploration de données et ont des liens solides avec la complexité du circuit. mais il me semble que la question dans son ensemble peut être un peu une prémisse délicate car une grande partie de l'apprentissage automatique est pragmatique et la complexité du ML appliqué est souvent étudiée indirectement / empiriquement en analysant des implémentations réelles d'algorithmes plutôt qu'en tentant de l'anticiper théoriquement ou de le classer strictement.
vzn

Réponses:

3

Il existe une différence inhérente ou une dissimilarité des approches entre les deux domaines de l'apprentissage automatique appliqué et de la théorie TCS / complexité.

Voici un récent atelier sur le sujet au Center for Computational Intractability, Princeton avec beaucoup de vidéos.

Description: De nombreuses approches actuelles de l'apprentissage automatique sont heuristiques: nous ne pouvons prouver de bonnes limites ni sur leurs performances ni sur leur durée d'exécution. Ce petit atelier se concentrera sur le projet de conception d'algorithmes et d'approches dont les performances peuvent être analysées rigoureusement. Le but est de regarder au-delà des paramètres où des limites prouvables existent déjà.

Dans le TCS, un domaine d'étude principal de l '«apprentissage», parfois aussi appelé «apprentissage machine», est parfois appelé théorie PAC, ce qui signifie probablement approximativement correct. son origine au début des années 80 est antérieure à la recherche beaucoup plus moderne sur «l'apprentissage automatique». wikipedia l'appelle partie de la théorie de l'apprentissage computationnel sur le terrain . Le PAC concerne souvent les résultats de l'apprentissage des formules booléennes à partir d'échantillons statistiques des distributions, etc. et la précision réalisable de l'apprentissage à l'aide de divers algorithmes ou d'échantillons limités. Ceci est étudié de manière théorique rigoureuse avec des liens avec les classes de complexité. Mais ce n'est pas tellement une page d'étude appliquée et de wikipédias sur l'apprentissage automatique qui ne la répertorie même pas.

vzn
la source
5
"appels wikipedia" ... savez-vous réellement quelque chose sur le sujet? 1) le wiki pour l'apprentissage automatique a une section Théorie qui relie à la théorie de l'apprentissage informatique page 2) le travail de la théorie de l'apprentissage de Valiant, Vapnik, Schapire, entre autres, a eu un impact énorme sur la pratique de l'apprentissage automatique.
Sasho Nikolov