Thursday, April 21, 2016

The Master Algorithm

We see so few popular science books on computer science, particularly outside of crypto and theory. Pedro Domingos' The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake the World, despite the hyped title and prologue, does a nice job giving the landscape of machine learning algorithms and putting them in a common text from their philosophical underpinnings to the models that they build on, all in a mostly non-technical way. I love the diagram he creates:

Working out from the inner ring are the representations of the models, how we measure goodness, the main tool to optimize the model and the philosophies that drove that model. The book hits on other major ML topics including unsupervised and reinforcement learning.

In the bullseye you can see the "Master Equation" or the Master Algorithm, one learning algorithm to rule them all. The quest for such an algorithm drives the book, and Domingos describes his own, admittedly limited attempts, towards reaching that goal.

I diverge from Domingos in whether we can truly have a single Master Algorithm. What model captures all the inner-ring models above: circuits. A Master Algorithm would find a minimum-sized circuit relative to some measure of goodness. You can do that if P = NP and while we don't think circuit-minimization is NP-hard, it would break cryptography and factor numbers. One of Domingos' arguments states "If we invent an algorithm that can learn to solve satisfiability, it would have a good claim to being the Master Algorithm". Good luck with that.

5 comments:

  1. It suffices if it works for inputs from real data, it doesn't need to be worst case or even average case. If you ask a machine learning researcher they would tell you that computational learning theory is disconnected from the practical machine learning research.

    ReplyDelete
  2. What he calls Master Algorithm is what machine learning researchers call Artificial General Intelligence. It doesn't need to solve computationally hard problems, it just need to solve problems that humans can solve.

    https://en.wikipedia.org/wiki/Artificial_general_intelligence

    ReplyDelete
  3. There a whole trend of Cortical Learning algorithms that are disregarded here, basically emulating nature. I don't think HTM could be regarded as NN..

    ReplyDelete
  4. Cortical Learning algorithms are misrepresented..

    ReplyDelete
  5. Dear Professor,

    I would like to share you a serious proof of UP = NP. I hope my work can be useful for you.

    Here is the link

    https://hal.archives-ouvertes.fr/hal-01304025v2/document

    In addition, I would like to share you another link if you feel interested on this:

    http://pentian.com/book/fund/2384

    I invite you to share these works to other people if you wish,

    Best Regards...

    ReplyDelete