It seems to me that machine learning/data mining experts are familiar with P and NP, but rarely talk about some of the more subtle complexity classes (e.g. NC, BPP, or IP) and their implications for effectively analyzing data. Is there any survey of work doing this?
$\begingroup$
$\endgroup$
5
-
2$\begingroup$ No survey that I know of, but check out this pointer to "quantum learning" (#5) from this post: blog.computationalcomplexity.org/2012/10/quantum-workshop.html $\endgroup$– Suresh VenkatOct 3, 2012 at 18:57
-
$\begingroup$ machine learning regularly attacks very hard problems that are prob outside of NP for "global" optimization but inside NP or less hard than that for "local" optimization. so the whole concept of complexity class gets blurry when one is optimizing for "good enough" results which are measured more by application-dependent quality measurements & in a sense arent really known apriori to running the algorithm(s).... $\endgroup$– vznOct 4, 2012 at 15:05
-
$\begingroup$ @vzn To me, that subtlety seems like all the more reason to pay attention to complexity! It might provide some very interesting insights. $\endgroup$– Mike IzbickiOct 4, 2012 at 15:28
-
$\begingroup$ there certainly are connections between learning theory, circuit complexity, cryptography. but this is the corner of learning theory that's a bit removed from machine learning practice. if you are interested, i can come up with some pointers $\endgroup$– Sasho NikolovOct 4, 2012 at 16:35
-
$\begingroup$ yes, another example, BDDs (binary decision diagrams) have been used in database algorithms/data mining & have strong connections to circuit complexity. but it seems to me the whole question may be a bit of a tricky premise because much machine learning is pragmatic & complexity of applied ML is often studied indirectly/empirically through analyzing real implementations of algorithms rather than attempting to theoretically anticipate or strictly classify it. $\endgroup$– vznOct 4, 2012 at 17:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
There is some inherent difference or dissimilarity of approaches between the two fields of applied machine learning and TCS/complexity theory.
Here is a recent workshop on the subject at the Center for Computational Intractability, Princeton with lots of videos.
Description: Many current approaches in machine learning are heuristic: we cannot prove good bounds on either their performance or their running time. This small workshop will focus on the project of designing algorithms and approaches whose performance can be analyzed rigorously. The goal is to look beyond settings where provable bounds already exist.
In TCS a main area of study of "learning" sometimes maybe confusingly even also called "machine learning" is called PAC theory which stands for Probably Approximately Correct. its early 1980s origin predates much more modern research into "machine learning." wikipedia calls it part of the field computational learning theory. PAC often concerns results of learning boolean formulas given statistical samples of the distributions etc and the achievable accuracy of learning given various algorithms or limited samples. This is studied in a rigorous theoretical way with tie-ins to complexity classes. But it is not so much an applied study & wikipedias page on machine learning does not even list it.
The Computational Complexity of Machine Learning PhD thesis by Kearns
-
5$\begingroup$ "wikipedia calls"... do you actually know anything about the subject? 1) the wiki for machine learning has a section Theory which links to the computational learning theory page 2) the learning theory work of Valiant, Vapnik, Schapire, among others, has had a huge impact on the practice of machine learning. $\endgroup$ Oct 5, 2012 at 19:09