News for hackers. Stuff that matters.
Re:Machine learning works spectacularly well, but mathematic... by j2kun on Friday December 04, 2015 @09:13AM (#10676383)
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/

Re:Machine learning works spectacularly well, but mathematic... by eli_gottlieb on Friday December 04, 2015 @10:47AM (#10676925)
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

http://arxiv.org/abs/1406.1222

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!

Re:Machine learning works spectacularly well, but mathematic... by blennon on Friday December 04, 2015 @01:05PM (#10677913)
An interesting and early (1992) demonstration of deep nets learning latent structure in the visual domain was presented by Usui et al. They presented a deep autoencoder with the spectral values of color chips and show that the hidden layer representation corresponds to the Munsell color space where each dimension corresponds to a psychological/intuitive color attribute. Pretty amazing. Even cooler that they showed this in 1992.

10.1364/JOSAA.9.000516 Shiro Usui, Shigeki Nakauchi, and Masae Nakano, "Reconstruction of Munsell color space by a five-layer neural network," J. Opt. Soc. Am. A 9, 516-520 (1992)

Re:Machine learning works spectacularly well, but mathematic... by Xcelerate on Friday December 04, 2015 @12:33PM (#10677669)
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.

Re:Machine learning works spectacularly well, but mathematic... by eli_gottlieb on Friday December 04, 2015 @01:09PM (#10677943)
>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."

Re:Machine learning works spectacularly well, but mathematic... by emcq on Friday December 04, 2015 @06:13PM (#10679861)
You will probably be interested in Kolmogrov complexity, which studies this using an information theoretic lens. However it is just an abstract concept and not really something you can measure precisely.
Re:Machine learning works spectacularly well, but mathematic... by j2kun on Friday December 04, 2015 @11:32AM (#10677258)
I meant "deep nets" in terms of boolean circuits, which seems like a different beast from these papers.
Re:Machine learning works spectacularly well, but mathematic... by auvrw on Friday December 04, 2015 @02:40PM (#10678570)
> reinvented the idea about a month or two ago, and ran into the existing papers

this happens all the time. i'm thankful that you took the time to post the results, because a discovery that's not communicated is not really a discovery. indeed, i suspect that what's going on in the field is as much a lack of communication as much as a lack of understanding.

i wish the author of the original article had included links to at least a couple of of the "number of tools to probe the geometry of these hidden structures."

Re:Machine learning works spectacularly well, but mathematic... by disgruntledphd2 on Sunday December 06, 2015 @04:56AM (#10684826)
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.

Re:Machine learning works spectacularly well, but mathematic... by nl on Friday December 04, 2015 @10:55AM (#10676984)
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

Re:Machine learning works spectacularly well, but mathematic... by gone35 on Friday December 04, 2015 @02:46PM (#10678612)
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

Re:Machine learning works spectacularly well, but mathematic... by algomanic on Friday December 04, 2015 @10:26AM (#10676778)
Related: "On the Expressive Power of Deep Learning: A Tensor Analysis". http://arxiv.org/abs/1509.05009