A second review of "The Master Algorithm" - Pedro Domingos

Amazon link

This is a guest review from Dr Roy Simpson.

---

Review of The Master Algorithm (by Pedro Domingos) 

By Dr. R. Simpson

This book provides both a history and a visionary project in machine learning by a leading professor in the field. The author writes fluently and well providing an informative book, which can be worth re-reading if one is interested in the details of machine learning techniques, as well as in (re-)evaluating his ideas about the future of the subject.

I was brought to this book after reading two other recent books on the subject of Algorithms: Weapons of Math Destruction, by Cathy O'Neil and the recent Hello World by Hannah Fry. Both of these books discuss the ongoing issues associated with the application of Algorithms, Big Data and Machine Learning to contemporary society – the latter book being newer and most relevant for UK audiences. These books recommended The Master Algorithm (2015) as a book for a deeper understanding of machine learning.

Much of this book is eminently quotable, and its text provides good introductions, for example here is from the first page of the Prologue:

“You may not know it, but machine learning is all around you. When you type a query into a search engine, it's how the engine figures out which results to show you (and which ads as well). When you read your email, you don't see most of the spam, because machine learning filtered it out. Go to Amazon.com to buy a book or Netflix to watch a video, and a machine-learning system helpfully recommends some you might like...

Traditionally, the only way to get a computer to do something – from adding two numbers to flying an airplane - was to write down and algorithm explaining how, in painstaking detail. But machinelearning algorithms, also known as learners, are different: they figure it out on their own, by making inferences from data. And the more data they have, the better they get. Now we don't have to program computers; they program themselves.

It's not just in cyberspace, either: your whole day, from the moment you wake up to the moment you fall asleep, is suffused with machine learning.”

The introductory chapters continue with more aspects of machine learning making some interesting points. For example the above passage indicates a “culture shift” within the programming world. In a later section it is noted that Microsoft has some difficulties with the new world, because its programmers are just that and its main products are produced in the traditional way, whereas Google is more of a machine learning organisation, with its main products produced the machine learning way.

He introduces the metaphor that whereas traditional programming is more like a manual (at best industrial) process, machine learning is more like farming – prepare the ground, then sit back and watch the systems (i.e. commercial products) grow themselves.

The author is aware that this field is not “General AI” - a topic often discussed in this blog to which I shall return at the end of this review. However we read that within this subfield of AI the traditional opponents are “Knowledge Engineers”. Knowledge Engineers hold (or at least once held) the view that systems which contain “knowledge” need to have that knowledge typed into them, and more generally be programmed in the traditional way.

The classic example was Cyc - a massive common sense knowledge based system over which programmers have been typing in “common sense rules” for several decades now.

The main counter to this view presented in this book is the matter of scale: knowledge engineers could work with thousands of rules; whereas machine learning will generate many millions of rules. (The argument against this knowledge engineering viewpoint held by the Agent Theory/AGI community has been different, and concerns its narrowness of scope. Agent Theorists might have used a “narrowness of scope” argument against early machine learning too, but the scalability of these techniques has won the commercial argument  - at least for now - though not necessarily the conceptual argument, as discussed later in this review.)

The primary content of the book is a review and overall analysis, from a modern machine learning perspective, of the five main strands of machine learning during the history of AI: Symbolism, Connectionism, Evolutionary Programming, Bayesian Networks, and Analogical Reasoning.

His purpose in all of this is to identify the principles involved and describe the essence of the technique and identify the best algorithm that the given technique has provided to the machine learning community. From there he moves to the main objective of the book: the development of a “Master (Learning) Algorithm” which incorporates all the best of the previous techniques and which is the subject of his own research group. This Master Algorithm would then be able to optimally learn anything .. .

A brief summary of each (with quotes from the book):

Symbolism

The symbolist's core belief is that all intelligence can be reduced to manipulating symbols. Whereas deductive reasoning is about going from axioms to conclusions, the learning aspect requires inductive reasoning: going from conclusions to axioms. Thus Hume's problem is discussed and the master algorithm here becomes “inverse deduction”.

Inverse deduction is like a super-scientist systematically looking at the evidence, considering possible inductions, collating the strongest, and using those along with other evidence to construct yet further hypotheses – all at the speed of computers. Yet this inverse deduction has limitations and issues, so we move to Connectionism.

Connectionism

How does your brain learn? Hebb's rule (from 1949) has become the cornerstone of connectionism, and is about neuron firing: “neurons that fire together wire together”. This history in AI begins with the Perceptron (from the 1950s). This was an electromechanical learning machine, based on a model of neurons, which had some basic classification skills (e.g is this a picture of a door or not?).

In the late 1960s it was proven that its classification skills were too limited to be of much generality and this approach to AI learning suffered a near total set-back (to the delight of the knowledge engineers of the time, due to funding competition).

It was not until the 1980s that physics inspired alternatives were introduced, such as the Boltzmann machine, which introduced probabilities into the field, and brought in techniques from statistical physics (ie thermodynamics) – so for a period the notion of “temperature” was important for a neural network learning system!

Although the introduction of probabilities has lasted, it is not clear what has happened to "temperature" in machine learning. It later transpired also that none of this physics theory was necessary to overcome the original Perceptron limitations. Nevertheless more mathematical techniques emerge from this era such as calculations in hyperspace, with associated weighted functions, convergence metrics, etc.

The main algorithm eventually identified from Connectionism is backpropagation, whose refinements are at the core of today's learning systems. However, the author raises an intriguing question: Is everything we “know” actually learned by our neurons? Has not evolution played a part too?

Evolutionary Learning

As an introduction to this chapter the author tells the following fantasy story:

Robotic Park is a massive robot factory surrounded by ten thousand square miles of jungle, urban and otherwise. Ringing that jungle is the tallest, thickest wall ever built, bristling with sentry posts, searchlights, and gun turrets. The wall has two purposes: to keep trespassers out and the park's inhabitants – millions of robots battling for survival and control of the factory – within.

The winning robots get to spawn, their reproduction accomplished by programming the banks of 3D printers inside. Step-by-step, the robots become smarter, faster – and deadlier. Robotic Park is run by the US Army, and its purpose is to evolve the ultimate soldier.

Needless to say this story brings out a large number of issues and concerns. The author seems to be sanguine about the dangers here, although modern “AI Ethics” movements (which included the late Stephen Hawking and Elon Musk) are concerned about this type of development. Towards the end of the book, the author actually suggests that working on “AI Ethics” could itself be a growth industry for displaced humans in the new era – robots and AI will have a lot of (human) ethics to learn!

The author is using this story here to dramatically introduce the AI Learning techniques inspired by Darwinian evolution: genetic algorithms and genetic programming. These techniques are overviewed, and some issues identified. However this reviewer is intrigued by the wider point that is being made here, and has an alternative way of expressing a related idea. The overall point that the author is making can be summarised by this formula:

   Learning == Agent Learning + Environment Learning + (Environment → Agent transfer)

In other words, when we ask “how does that small brain learn all this stuff?” - the answer is that the small brain has not had to do all the learning implicit in its actions. This viewpoint is implied also by the Chomsky view of language acquisition (Chomsky has been another critic of the traditional approach to machine learning – the author hopes that his wider “Master Algorithm” approach meets Chomsky's concerns.)

There are again several limitations to any master algorithm provided by what we could also call the Darwinian algorithm. Chief amongst them is the fact that the Darwinian algorithm (as currently understood) tends to find “suboptimal” solutions, not optimal solutions – so we move on to Bayesian theory.

Bayesian Networks

The path to optimal learning begins with a formula that many people have heard of: Bayes Theorem. But here we'll see it in a whole new light and realize that it's vastly more powerful than you'd guess from its everyday uses.

At heart, Bayes' theorem is just a simple rule for updating your degree of belief in a hypothesis when you receive new evidence: if the evidence is consistent with the hypothesis, the probability of the hypothesis goes up; if not, it goes down.

Bayes Theorem uses conditional probabilities. (P(A|B) is the probability that A happens given that B has happened/is assumed) and there is an associated inference system. Similar to deductive logic (e.g. the Prolog-based resolution systems sometimes discussed in this blog) the inference system allows the deduction of probabilistic conclusions and the management of probabilistic assumptions. This is all wrapped into a network structure amongst assumptions, and apparently it has been discovered that there is an isomorphism between the probabilities and weights often used in Artificial Neural Net models and the probabilities used in Bayesian Networks.

The success of this Bayesian approach arises directly from the quantity of data now available, making the probabilities and conditional probabilities very accurately determinable from millions upon millions of data points (pre-Internet such probabilities would have been input by researchers by hand as guesses, resulting in unconvincing performance and results from such probabilistic systems).

This has motivated much of the idea behind a complete Master Algorithm for learning. This has left open two remaining unification tasks, of which the hardest has been the unification of logic and probability; the other has been to incorporate what to do when there is essentially no data, only analogies to existing data.

Analogy Reasoning

Methane and Methanol have very similar chemical structure; but they are not identical and have some big differences since one is a (room temperature) gas, the other a liquid. So if your system knew much about one, what can it deduce about the other? Much of science and business-services-work operates by analogy: no two customers are exactly the same. We manage to cope, so what are the principles involved?

Various classification ideas have been developed in this strand of AI, and a very powerful technique called a Support Vector Machine was apparently the most powerful AI technique around the turn of the century. Only in recent years has it been superseded by Artificial Neural Nets for the top learning slot (although Artificial Neural Nets don't do analogical reasoning as such).

The Master Algorithm - Alchemy

So putting this all together has been the research project of Prof. Domingos, and he has developed a mathematical framework called Markov Logic Networks and a corresponding (open source) software system called Alchemy. The final chapters discuss the general steps required to produce a Master Algorithm from all the above ingredients. He does not describe the current form of Alchemy (or MLN) as the Master Algorithm, but uses it to suggest that this goal is feasible.

One feature he seems to claim Alchemy is lacking is the ability to explain itself fully, also there may still be optimisation issues. There are also some discussions about the social aspects of all this, suggesting that users should form “trusted data unions” to hold the value of their data (a bit like banks holding their money), rather than the current practice of just handing everything over to the big corporations who then benefit from any commercial consequences (and as UK residents are aware, don't pay appropriate tax either).

Analysis: Agent Theory and Computational Mathematics

I shall end this review with a few remarks about this idea of a “Master Learning Algorithm” from the perspective of Agent theory (which is often discussed in this blog); and some ideas about Computational Mathematics (my own interest).

Agent theory takes a more holistic, biologically realistic and physically realist view of AI than one finds in stand-alone techniques like machine learning. Although these machine learning techniques have become (and will remain for another decade at least) at the centre of a business and social revolution, in aiming for such a high goal as a Master Algorithm which can learn everything – and do so optimally - one has to ask if boundaries will eventually be reached due to insufficient attention to agent theoretic issues.

For example, how and in what way, is a biological cell a learning system? Likewise the mysteries of neurological biochemistry are not resolved in an agreed way. Even aspects of the Darwinian algorithm are not fully understood. So it is quite possible that nature has more to teach us about learning.

On the subject of Computational Mathematics and AI much can also be said. A famous critic of the entire AI project (at least as seen as a branch of Computer Science) has been Professor Penrose with his books (from 1989 and 1994). Since that time more results have appeared in the foundations of logic and mathematics which can be viewed as clarifying Penrose's position.

For example using the results of an ongoing project known as ReverseMathematics, this reviewer suspects that much of Applied Engineering Mathematics is not actually computable in the Turing sense. However it nearly is, so many effects are “subtle” - although the inability to predict weather systems accurately beyond (say) five days; turbulence theory; and mathematical puzzles related to physics models suggest these “weakly non-computable” effects may yet be important.

The author himself recognises that an outstanding and unsolved mathematical problem known as the NP-completeness problem is significant to the subject of AI. I shall leave the last words to the author:

The purpose of AI systems is to solve NP-complete problems, which may take exponential time, but the solutions can always be checked efficiently. We should therefore welcome with open arms computers that are vastly more powerful than our brains, safe in the knowledge that our job is exponentially easier than theirs.

---

My own review was posted back in June 2016 and can be found here.

A second review of "Beyond Weird" by Philip Ball

Amazon link

Roy Simpson has written his own review of the above book which I'm pleased to guest-post here. He previously guest-reviewed "The Order of Time" by Carlo Rovelli.

---

Review of Philip Ball: Beyond Weird (2018)

By Dr. Roy Simpson, October 2018

This review was requested by Nigel Seel and could be read in conjunction with his review of this book.

In reviewing a book such as this it is tempting to first review the style and content of the book, then secondly to add comments concerning one's own view and approach to these matters.

Having been familiar with the basic equations of quantum mechanics for a long time I am not able to say for sure whether the book actually requires the prior familiarity with quantum mechanics suggested in the Seel review. Certainly one has to be interested in physics and its foundations. The book contains a good introduction to the structure and key components of quantum mechanics and eventually leads us towards the questions of interpretation and meaning.

The unusual nature of the formulation of the subject is neatly captured in a chapter comparing the axioms of quantum mechanics with other physics theories. For example we have Newton's Laws:

1. Every moving object keeps moving at the same speed if no force is applied to it. If it is still to begin with, it stays still.

2. If a force is applied to an object it accelerates it in direct proportion to that force .. .

3. For every force that one body exerts on another, the other body exerts an equal force back in the opposite direction.

Special Relativity can be presented with similar physically comprehensible (and experimentally checkable) axioms. By contrast for quantum mechanics we have:

1. For every system, there is a complex Hilbert Space H.

2. States of the system correspond to projection operators onto H.

3. Those things that are observable somehow correspond to eigenprojectors of Hermitian operators.

4. Isolated systems evolve according to the Schrödinger equation.

Now all physics theories have a mathematical content and even Newtonian mechanics can be presented using mathematical structures such as symplectic manifolds, Noetherian moments and differential forms. However Newtonian theory has a basic physical form as stated above. The issue is: what is the Quantum equivalent?

Without an answer to that question it can be difficult to be convinced that the theory has been fully understood, despite the success of the mathematical formulation. So this situation is deemed philosophically unsatisfactory and also impedes progress towards reconciling quantum theory with General Relativity (which also has a physical explanation as well as a successful mathematical form).

The book takes a long look at the most basic interpretation (as these attempts to connect the mathematics with any physical reality are called) of quantum mechanics, called the Copenhagen interpretation.

The book then follows with a more cursory and dismissive view of the Bohm-de Broglie interpretation as an example of a key distinction between such interpretations: are they Ontic (the mathematical entities represent real physical structures in the usual physics sense); or are they Epistemic (the mathematical entities describe the observer's knowledge of the – perhaps unknowable – physical system).

The Copenhagen leans towards the Epistemic, whereas the Bohm is Ontic. Other interpretations are also discussed by the book such as the very Epistemic Qbism interpretation and the Ontic GRW and Penrose-Diosi models. These latter are not just interpretations but are modifications of some of the mathematics (making a physics explanation easier, in the latter case by invoking gravity).

There is also a long and useful discussion of “decoherence”. However this book does not include any mathematics and although that makes the book easier for some audiences, it does detract from some clarity and rigour in the arguments the author wishes to make.

Another interpretation dismissively discussed in the book is the Many Worlds Interpretation. A recent summary of this section is available in an online article by the author here.

There are over one dozen interpretations of quantum mechanics and they are not all discussed in the book. New interpretations appear regularly with an example “The Montevideo Interpretation” (which this reviewer has not yet studied). So the book is not comprehensive in its account of interpretations.

The book gives a long account of the Bell Theorem, which is an experimentally checked theorem implying the non-locality and non-contextuality of quantum mechanics. The discussion here is interesting, but this reviewer has uncovered a recent examination of the Bell Theorem which is more precise about the nature of the “superluminal effects” involved in the statement of the theorem.

Apparently there were two forms of Bell's Theorem: a “coarser” form, and 10 years later a more precise form, which makes clearer what is and is not prohibited by the theorem. However the book does not discuss this level of distinction, and the possible consequences.

The book eventually focuses on the idea of an information-based interpretation of Quantum Mechanics, and recent work related to this. This area of work is largely stimulated by the subject of Quantum Computation, and the intriguing question as to whether all of the “engineering” problems in that area are purely engineering problems and not also some scientific (i.e. quantum interpretational).

Of particular interest is the idea of “quantum reconstruction” and “information causality”. Here the attempt is to address the lack of a physics basis by trying to find one in axioms - often based on “information” based ideas. From the present reviewer's perspective this work is encouraging in the sense that the results may be converging on a class of invariant mathematical objects that are being studied in 21st century mathematics.

So overall the book is a good comprehensive account of quantum interpretation and meaning from an early 21st century perspective, especially as viewed by a physical-chemist who has a “user” view of quantum mechanics.

Transgender? Ask an AI

An image of Aiden Katri uploaded to her Facebook page on Tuesday, March 29, 2016, together with a post explaining her decision to conscientiously object (Aiden Katri/Facebook)

Commenting on yesterday's post, "The 'is' and 'ought' of homosexuality", Roy suggested I should write something on the current hot topic of transgenderism.

As a topic this ranks with dissing the Religion of Peace, suggesting the Saudi ruling clique might have psychopathic tendencies or speaking out in support of Brexit.

Obviously I'm not going to go there .. . But wait! Let's be objective about this. We can ask an AI. Time to invoke SWI Prolog in theorem-proving mode.

---

Let’s start by introducing a convenient acronym: marbiafl:

“Male As Regards Body - Identifies As Female Lesbian”.

The scientific approach would be to axiomatise the properties of the marbiafl and then appeal to Leibniz's law, the identity of indiscernibles. First we list the properties of heterosexual men, then the properties of heterosexual women (for simplicity just the 95% of the population who are straight) and finally, the properties of transgender people who are biologically male but who self-identify as lesbian females.

property(man, often_aggressive).
property(man, male_genitalia).
property(man, over_muscled_or_fat).
property(man, hairy_face).
property(man, wants_sex_with_women).

property(woman, often_agreeable).
property(woman, female_genitalia).
property(woman, often_slim_and_petite).
property(woman, smooth_face).
property(woman, romantically_inclined_to_men).

property(marbiafl, often_aggressive).
property(marbiafl, male_genitalia).
property(marbiafl, over_muscled_or_fat).
property(marbiafl, hairy_face).
property(marbiafl, wants_sex_with_women).

Now we ask: are transgender people (as defined above) men or women?

transgender_is(X, Y) :- findall(P, property(X, P), Plist), findall(P, property(Y, P), Plist).

This says a transgender person X is a Y (man or woman) if all the properties of X (gathered in Plist) are just the same as all the properties of a Y (a man or a woman). This is Leibniz's law.

Here is how findall works on the dataset already defined, using SWI Prolog:

?- findall(P, property(man, P), Plist).
Plist = [often_aggressive, male_genitalia, over_muscled_or_fat, hairy_face, wants_sex_with_women].

?- findall(P, property(woman, P), Plist).
Plist = [often_agreeable, female_genitalia, often_slim_and_petite, smooth_face, romantically_inclined_to_men].

?- findall(P, property(marbiafl, P), Plist).
Plist = [often_aggressive, male_genitalia, over_muscled_or_fat, hairy_face, wants_sex_with_women].

---

We have now trained the AI and it's ready to answer our questions.

?- transgender_is(marbiafl, woman).
 false.

?- transgender_is(marbiafl, man).
 true.

Oh dear! A shock for activists, I wasn't expecting that.

"The Order of Time" by Carlo Rovelli

Amazon link

Roy Simpson, who frequently comments here, sent me a review of the book above to post as a guest blogger. He wrote:

"Here is the review of the Rovelli book. ... I am hoping the Philip Ball book might arrive next week.

A remarkably hot topic right now is the Riemann Hypothesis since there are several (doubtful) claims that it has been solved. Since I haven't really studied this equation much, I am finding papers which make all rather interesting.

For example in 1949 Casimir used "zeta function regularization" in QFT to calculate his effect; then in 1976 Hawking used "zeta function regularization" to do most of his quantum black hole calculations. As I remarked in your blog

zeta (-1) = 1+2+3+4+  ... = -1/12

Also String theory requires 2/(2-D) = zeta(-1) for the number of Dimensions - giving D = 26!

The reason that this curious sum forms is because of (a) complex analytic continuation - taking a function out of its domain of definition in a unique way and (b) p-adic theory which messes up what is meant by "=" (zero distance) via a fractal like metric. So the interconnectedness of mathematics seems to be in evidence here (something the String Theorists are always proud of).."

Here is his review.

---

Review of C. Rovelli : The Order of Time (2018)

By Dr. Roy Simpson, October 2018

The small (214 page) book by Prof. Carlo Rovelli came to my attention as it featured in a “guest interview” in the blog of physicist S. Hossenfelder in August. That interview was conducted by a lawyer with an interest in physics and time and has generated at least 250 comments.

Rovelli has written several very poetic, but informative, popular physics books in recent years and this book continues that theme by discussing his approach to the question of “time” in physics.

In broad terms the book is divided into three parts: first the lessons from General Relativity on time; second the particular ideas about time proposed by Rovelli from his work on Quantum Gravity; third some broader statements about the philosophy of time. None of these parts conveys the details of the theory that a student of physics or a practising physicist would wish (although there are some equations in the notes), but it does all provide a general overview of where Rovelli's thinking is with respect to “Time in Physics” for a general audience. There are links in the end-notes to detailed papers by Rovelli and books by others which can be studied later.

To understand Rovelli's view of physics we should begin by recognising that he is the author of (another) Interpretation of Quantum Mechanics called “The Relational Interpretation”. The underlying idea here was to spread the relational arguments which drove the development of special relativity (time being relative to observers and frames) onto quantum observers and onto physics theories in general. The quantum interpretation that results has some similarity to the original Everett Interpretation, but without the many worlds. He does not believe that “measurement” is a real activity, but only interactions between quantum objects is real. As evident from Part two his relational viewpoint also applies to physics concepts like Entropy – where he emphasises “Relative Entropy” between two subsystems.

To understand why Time is important we also need to understand his research starting point: Quantum Gravity and an associated equation from the 1960s now called the Wheeler-DeWitt equation. Rovelli is also the author of a rival (to String Theory) theory of quantum gravity called “Loop Quantum Gravity” which originated from the Wheeler-DeWitt equation (the latter equation plays no role in String theory, as yet).

The Wheeler-Dewitt equation was derived by making many assumptions in a 1960s attempt at a quantization of General Relativity. This equation was thus a kind of “Schrodinger Equation” for General Relativity, generated by advanced versions of the quantization procedures found in Quantum Mechanics textbooks. Now the Schrodinger equation, in its full dynamic form, is a time dependent equation concerning the wavefunction Ψ(q1,q2,q3;t) where (q1,q2,q3) are position variables and t is the usual Newtonian time parameter. In the Wheeler-DeWitt equation, in which the system quantized is all of general relativity Ψ becomes Ψ(g_ij(p)). Here p is an event in space-time and g_ij is (derived from) the general relativity metric (distance function). The equation becomes a so-called functional equation in the function (of position and time) g_ij(p). Furthermore this derivation requires (perhaps fortunately) that the Schrodinger time parameter t disappears.

In short the Wheeler-DeWitt equation is timeless - Ψ once calculated never changes and this Ψ is meant to describe the entire Universe – for all time! This is known as the “problem of time” in Quantum Gravity, and is especially relevant to the approach taken by Rovelli.

Now time is still present in this model via the metric g_ij(p) and so is introduced the idea of “external variables” and “internal variables” - in particular “internal time”. Thus in the Rovelli approach time is not a fundamental feature of physics but an emergent concept, which he believes can be understood taking a relational approach. The more fundamental concept he calls “change”.

So in Part One of the book Rovelli is reviewing the results of General Relativity (such as the effect of location in a gravitational field on clocks) and presents this as evidence that in standard physics time should be considered as relative, forming part of a network of time. There is no “order of time” amongst the clocks in General Relativity due to lack of simultaneity etc.

In Part Two Rovelli discusses Entropy (also part of the physics discussion of time) and introduces his equation for “thermal time” - which is a time simply derived from the state of a dynamic thermal system, effectively by inverting the usual equation for the dynamical evolution of a thermal system.

Again thermal subsystems have a relative entropy. There is also a quantum version of the same idea. Interestingly an experiment was reported in 2013 that entangled two photons in such a way that photon A used photon B as a local clock, suggesting that hiding inside “quantum entanglement” could be an emergent notion of clock and thus time.

Another consequence of the work on the Wheeler-DeWitt equation is that there can be quantum solutions in which no emergent time forms. Thus time is not even Universal (in the way that “change” might be) as is commonly assumed in physics and “common sense” (naïve intuition). Rovelli makes some remarks about this, but deeper analysis is needed to understand all of this.

Rovelli takes the view that we are on the cusp of more breakthroughs in time research. We shall see.