<div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Oct 1, 2014 at 2:28 AM, Anders Sandberg <span dir="ltr"><<a href="mailto:anders@aleph.se" target="_blank">anders@aleph.se</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>Combinatorial explosion. When you discover spatial coherence and the existence of objects a lot of things like video become learnable that otherwise would need exponentially large training sets. So the real issue is how to get the hierarchies and structures from the data; I assume you know about the work in the Josh Tannenbaum empire?</div><div><br></div><div>Apparently the video game playing reinforcement agent of Deep Mind somehow figured out object constancy for the aliens in the first wave of Space Invaders and could learn to play well, but got confused by the second wave since the aliens looked different - it didn't generalize the first aliens, and had to re-learn the game completely for that stage. </div></blockquote></div><br><br><br></div><div class="gmail_extra">Contemporary learning algorithms are even O(1) wrt number of variables. An example that jumps to my mind is PEGASOS SVM. It is a shallow learner, though. I don't recall an example for deep learning right now, but even I have developed some deep learning neural networks, some even fully connected, with training time of O(n) per iteration wrt number of connections, and optimization convergence rate of O(n^-2) wrt number of iterations. Of course, all learnable wrt PAC Learning theory. Yann Le'Cunn, which I mentioned earlier, also demonstrated extraordinary results with deep neural networks.<br><br></div></div>