4 ms·

I can chime in for the theoretical computer scientists. Deep learning (in its simplest form) corresponds to the class of circuits whose gates are linear thresho

by j2kun 11y ago

I can chime in for the theoretical computer scientists. Deep learning (in its simplest form) corresponds to the class of circuits whose gates are linear threshold functions. Our primary goal with such functions is not to show what problems can be solved by small circuits using linear threshold gates, but what problems cannot be solved with such circuits. Until last week [1], it was an open problem whether every function with n inputs that is computable in nondeterministic time 2^O(n) could also be computed with a two-layer circuit using only O(n) gates (that is, a deep net with just one hidden layer with a linear number of gates). This is an embarrassing state of knowledge. Now we know the following slightly less embarrassing thing: there is an explicit function, computable in linear time, that needs at least n^3/2 gates in a two-layer deep net (modulo some log(n) factors), and another function that needs n^3/2 gates in a three-layer deep net (with the additional restriction that the output gate is a majority vote of the previous layer). This is still a long way away from truly understanding the representational power of deep nets, but it's the first general progress that has been made since the early 90's. [1]: http://eccc.hpi-web.de/report/2015/188/ http://eccc.hpi-web.de/report/2015/188/

algomanic 11y ago
Related: "On the Expressive Power of Deep Learning: A Tensor Analysis". http://arxiv.org/abs/1509.05009 http://arxiv.org/abs/1509.05009
eli_gottlieb 11y ago
Actually, there's been a few papers showing solid theoretical progress on understanding what structure in data deep networks are learning to represent. https://github.com/gregversteeg/CorEx https://github.com/gregversteeg/CorEx http://arxiv.org/abs/1406.1222 http://arxiv.org/abs/1406.1222 http://arxiv.org/abs/1410.7404 http://arxiv.org/abs/1410.7404 Disclaimer: I reinvented the idea about a month or two ago, and ran into the existing papers when googling for joint entropy estimators after making some interesting graphs with hierarchical probabilistic programs. I only wish I could've been the first!
- disgruntledphd2 11y ago
  That's really interesting, especially with respect to the personality trait recovery. I'm particularly amazed given that I've never been able to replicate the Big5 model in its entirety against particular datasets. Only commenting on that portion, as it's what I know. The author doesn't appear to give any indication of which test was used, and where the sample was taken from. This makes me a little suspicious, but its probably just a disciplinary thing. Additionally, many tests reduce the pool of available questions for a scale after testing it against against other scales + theory. This means that what the author is recovering, is the scale imposed on the items by the original authors. Nonetheless, this has forced me to reinvestigate the Big5 model, so it's not all bad :). Massive appreciation for the links.
- nl 11y ago
  Possibly also of interest: Recursive Neural Networks Can Learn Logical Semantics[1] Probably not as theoretical as the work you referenced, but interesting to me because of the deeply practical outcomes in NLP. [1] http://www.aclweb.org/anthology/W/W15/W15-40.pdf#page=22 http://www.aclweb.org/anthology/W/W15/W15-40.pdf#page=22
- j2kun 11y ago
  I meant "deep nets" in terms of boolean circuits, which seems like a different beast from these papers.
- Xcelerate 11y ago
  Those papers are very interesting. I was particularly surprised that the method exactly recovers the Big-5 components of personality from the results of the survey questions. The whole idea of "simplest model that explains most of the data" has always been very appealing to me. The concept is closely tied to reproducing kernel Hilbert spaces, which have recently experienced a revival in interest due to the representer theorem.
  - eli_gottlieb 11y ago
    >I was particularly surprised that the method exactly recovers the Big-5 components of personality from the results of the survey questions. Why? Is that a standard dataset? They could have just cherrypicked tasks. I also noticed that they seem to only have the actual computation working for discrete random variables (integer features) right now, which limits its applicability. They also seem to use mass-function estimators, which again can work well for discrete data while becoming statistically intractable when dealing with continuous random variables. >The whole idea of "simplest model that explains most of the data" has always been very appealing to me. In this case it's a bit more like, "The set of latent variables that best screen off the observables from each-other."
gone35 11y ago
This is still a long way away from truly understanding the representational power of deep nets, but it's the first general progress that has been made since the early 90's. Exactly. Someone should tell Yann LeCun this --see e.g. Section 3.2 in [1], or pretty much every time he brings up circuit complexity theory to automagically imply that "most functions representable compactly with a deep architecture would require a very large number of components if represented with a shallow one." [ibid, p.14] [1] http://yann.lecun.com/exdb/publis/pdf/bengio-lecun-07.pdf http://yann.lecun.com/exdb/publis/pdf/bengio-lecun-07.pdf

by j2kun 11y ago

algomanic 11y ago

Related: "On the Expressive Power of Deep Learning: A Tensor Analysis". http://arxiv.org/abs/1509.05009 http://arxiv.org/abs/1509.05009

eli_gottlieb 11y ago

Actually, there's been a few papers showing solid theoretical progress on understanding what structure in data deep networks are learning to represent. https://github.com/gregversteeg/CorEx https://github.com/gregversteeg/CorEx http://arxiv.org/abs/1406.1222 http://arxiv.org/abs/1406.1222 http://arxiv.org/abs/1410.7404 http://arxiv.org/abs/1410.7404 Disclaimer: I reinvented the idea about a month or two ago, and ran into the existing papers when googling for joint entropy estimators after making some interesting graphs with hierarchical probabilistic programs. I only wish I could've been the first!

disgruntledphd2 11y ago
That's really interesting, especially with respect to the personality trait recovery. I'm particularly amazed given that I've never been able to replicate the Big5 model in its entirety against particular datasets. Only commenting on that portion, as it's what I know. The author doesn't appear to give any indication of which test was used, and where the sample was taken from. This makes me a little suspicious, but its probably just a disciplinary thing. Additionally, many tests reduce the pool of available questions for a scale after testing it against against other scales + theory. This means that what the author is recovering, is the scale imposed on the items by the original authors. Nonetheless, this has forced me to reinvestigate the Big5 model, so it's not all bad :). Massive appreciation for the links.
nl 11y ago
Possibly also of interest: Recursive Neural Networks Can Learn Logical Semantics[1] Probably not as theoretical as the work you referenced, but interesting to me because of the deeply practical outcomes in NLP. [1] http://www.aclweb.org/anthology/W/W15/W15-40.pdf#page=22 http://www.aclweb.org/anthology/W/W15/W15-40.pdf#page=22
j2kun 11y ago
I meant "deep nets" in terms of boolean circuits, which seems like a different beast from these papers.
Xcelerate 11y ago
Those papers are very interesting. I was particularly surprised that the method exactly recovers the Big-5 components of personality from the results of the survey questions. The whole idea of "simplest model that explains most of the data" has always been very appealing to me. The concept is closely tied to reproducing kernel Hilbert spaces, which have recently experienced a revival in interest due to the representer theorem.
- eli_gottlieb 11y ago
  >I was particularly surprised that the method exactly recovers the Big-5 components of personality from the results of the survey questions. Why? Is that a standard dataset? They could have just cherrypicked tasks. I also noticed that they seem to only have the actual computation working for discrete random variables (integer features) right now, which limits its applicability. They also seem to use mass-function estimators, which again can work well for discrete data while becoming statistically intractable when dealing with continuous random variables. >The whole idea of "simplest model that explains most of the data" has always been very appealing to me. In this case it's a bit more like, "The set of latent variables that best screen off the observables from each-other."

gone35 11y ago

This is still a long way away from truly understanding the representational power of deep nets, but it's the first general progress that has been made since the early 90's. Exactly. Someone should tell Yann LeCun this --see e.g. Section 3.2 in [1], or pretty much every time he brings up circuit complexity theory to automagically imply that "most functions representable compactly with a deep architecture would require a very large number of components if represented with a shallow one." [ibid, p.14] [1] http://yann.lecun.com/exdb/publis/pdf/bengio-lecun-07.pdf http://yann.lecun.com/exdb/publis/pdf/bengio-lecun-07.pdf