Machine Learning Thoughts

Can the study of human learning help?

The question is whether, in order to make progress toward building learning machines, it is necessary to study the only available examples of such machines we have so far: animal brains (and more specifically human ones).
People who would answer no to this question often cite the example of planes: the first successes for building flying machines were obtained when people stopped trying to imitate birds. So it seems that understanding how Nature solved the problem may not always help. One reason is that animal brains were not designed only to solve the learning problem, just as birds were not designed to solve the flying problem. It is only a byproduct of an evolution that was mainly geared towards survival and adaptation to certain environmental conditions.

Despite these considerations, there has been many attempts to make bridges between the study of natural and artificial learning. For example, people working on artificial neural networks, or on genetic algorithms were never ashamed of using biological findings as a source of inspiration.

My feeling is that it is fine to be interested both in artificial and natural learning provided the following is accepted:

• First of all it is not necessary to start from natural learning to develop a theory of artificial learning, and there is no need for this theory to explain the specifics of natural learning.
• Second, it is important to abstract away from natural learning in order to formulate precisely what learning means.
• However, any source of inspiration is good, especially when one gets stuck, so why not looking for inspiration in natural learning.

I used to think that the work being done in cognitive psychology was too specifically human to be of any interest for people working on learning theory. Also I was very suspicious about  whatever was said to be "biologically inspired" or "cognitively inspired". However, the remarkable efforts for abstracting concepts that has been done by some cognitive psychologists suggest that might have been too critical.

In a recent interview, Tom Mitchell, a famous ML researcher expressed similar views:

[The interviewer] - Learning the brain’s algorithms for doing things is very difficult, and is not very well understood as yet. Do you ever find it frustrating trying to get computers to learn things that we ourselves don’t know the inner workings of?
[Tom Mitchell] - That’s actually a very interesting observation—I actually don’t get frustrated by that—why? I don’t know!
Maybe it’s odd, but it’s true that much of the work in machine learning—how to get computers to learn—has been kind of unguided by anything we know about human learning. It just grew up on its own—“ok, how would we engineer this system to look at a lot of data and discover regularities?”—so people engineered those instead of looking at how humans do it and then trying to duplicate it. But recently, because I’ve been looking at the brain, I’ve been starting to learn more about what people know about human learning—and it’s very different. For example, when we humans learn, a big part of what determines whether we succeed or not is all about motivation. And there’s nothing in machine learning algorithms that even remotely corresponds to motivation. So it’s just a very different phenomenon…maybe in 10 years we’ll understand it better, but right now, the two are very different.

Also, I recently heard about the work of Alison Gopnik who studied the way children learn causes and she draws some interesting connections between the causal structure that is inferred by them and graphical models such as Bayesian networks. Also she explains that the way children learn is very "multivariate" in the sense that they try many things at a time and extract causal relationships easily from multidimensional observations. In other words, it is not necessary for them to act on one knob at a time to understand how a machine works.

Why do we do Science?

I have been asked several questions revolving about the usefulness of research: why do you do research in mathematics, computers can do the calculations? or why do you do research in computer science, is it to build faster computers? or what is the use of doing all these complicated calculations, is there any application you can make money of?
At some point I used to answer that there is nothing more useful than something that seems useless like a new mathematical theory. My argument was that things that are immediately useful are only useful immediately, while things for which we do not see any immediate application may very well turn out to lead to entirely new technologies in the long run. As an example, take the complex numbers. When they were invented, they were considered as a nice creation of the mind, as something only some mathematicians understood, but as something that would never have any application in the real world. Centuries later they are at the basis of many fields of technology we could hardly live without such as signal processing or electronics.
Unfortunately, it is not easy to predict which of the many mathematical works that are done today will be most useful in a few centuries. There is thus potentially a lot of wasted effort.
Another thing I used to say is the following: it is more fruitful to build a theory that explains several phenomena than to solve a specific problem (this is the difference between science and engineering).
A quote which I like is : "There is nothing so practical as a good theory". It is originally from Kurt Lewin (although some ML people think it is due to Vapnik because it is often used by him).

Anyway, instead of trying to justify scientific research, it is probably more interesting to think about how this research should be conducted and in particular what should be the motivations of someone doing so.
I recently found some interesting answers in the following quotes from Albert Einstein (taken from "The Einstein-Besso Manuscript", Scriptura, Aristophil 2005):

1. "My scientific work is motivated by an irresistible longing to understand the secrets of Nature and by no other feelings. My love for justice and the striving to contribute toward the improvement of human conditions are quite independent from my scientific interests."
2. "The important thing is not to stop questioning. Curiosity has its own reason for existing. One cannot help but be in awe when he contemplates the mysteries of eternity, of life, of the marvelous structure of reality. It is enough if one tries merely to comprehend a little of this mystery every day. Never lose a holy curiosity.
3. "To be sure, it is not the fruits of scientific research that elevate a man an enrich his nature, but the urge to understand, the intellectual work, creative or receptive."
4. "Where the world ceases to be the scene of our personal hopes and wishes, where we face it as free beings admiring, asking and observing, there we enter the realm of Art and Science."
5. "The most beautiful thing we can experience is the mysterious. It is the source of all true art and science, who can no longer pause to wonder and stand rapt in awe is as good as dead: his eyes are closed."
6. "After a certain high level of technical skill is achieved, science and art tend to coalesce in aesthetics, plasticity, and form. The greatest scientists are always artists as well.
7. "It is my inner conviction that the development of science seeks in the main to satisfy the longing for pure knowledge."

So as a conclusion, the main motivation is the curiosity or the desire to understand, there should be no other. This is probably a bit idealistic, but what is life without a bit of idealism?

Learning theory and Physics

Learning theory is about the process of induction, that is the process of building theories or models from observations.
Most of what physicits do is actually induction about natural phenomena. So one may wonder whether there can be some relationship between Physics and Learning Theory.
One could argue that Physics is using induction in a particular setting, while Learning Theory is studying induction in general, so they cannot really be compared.
But here are some surprising connections:

1. In quantum physics Bell's inequality provides a test for the existence of "hidden variables" that explain entanglement. This inequality is based on a statistical reasoning.
2. Some physicists study the connection between Bayes formula for updating probabilities and the collapse of the wave function when measurements of a quantum system are made (see e.g. the work of Christopher Fuchs). There are even "Bayesian" and "non-Bayesian" physicists, just like the Machine Learning people !
3. Even further, Lucien Hardy tries to rethink the way physics theories are built up. His starting point is that the work of any physicist is to accumulate and correlate data. He thus develops physics theories as theories for how data should be handled ! (see e.g. http://arxiv.org/PS_cache/gr-qc/pdf/0509/0509120.pdf)

French teams getting together

There are many people working on Machine Learning in France, but unfortunately, they have little influence/presence on the international scene. Hence they have decided to get together and to start being "pro-active". The idea is to foster research activities in this area by organizing seminars, applying for funding, running projects...
The homepage for this initiative is http://proml.lri.fr (in french of course).

Building models: what for?

A large amount of the effort in Machine Learning research is devoted to building predictive models. This means trying to infer, from labeled examples, a model that can, later on, be used for making predictions on new instances. This problem of making models for prediction is relatively well understood, although very partially solved today. But, there are plenty of other reasons for building models, and this may drive a large part of the future research in this field.

For example, my current work is to investigate how one can build models for understanding, monitoring and controlling complex systems or processes. Of course, this is not new as such, but I want to emphasize here that this is an area people in Machine Learning have seldom studied, although ML techniques could very well be adapted to yield better solutions than existing approaches.

Let us leave understanding aside (as this is a very debatable issue and should be discussed separately) and focus on monitoring and control. There are plenty of methods for monitoring and controlling systems or processes. Many rely on models that are built from knowledge, some rely on statistical models (built from observations). The problem is that models built from knowledge are usually very sophisticated and specialized, while statistical models are very simple and generic. There thus seems to be a gap in between.
Machine Learning is very advanced in terms of automatically building sophisticated models from observations, while incorporating previous knowledge. The issues of trading-off the complexity of the models with their statistical properties (e.g. overfitting) has been thoroughly investigated in this field.
As a result, ML is particularly suited for providing new ways of building sophisticated, yet reliable models.

However, ML researchers have focused their effort on prediction error, while when you need to control a process, this prediction error is not what matters.
To make my point more precise, let me give an example. Assume you are trying to cook up some nice steak. Depending on the thickness of the piece of meat, you might have to heat it up longer or shorter. Your goal is to have a steak that tastes good (tender, not cold, not burnt...) and for that, you cannot modify the thickness of the meat but only act on the time you leave it on the grill.
Of course if you never have done it before, it is likely that you will fail to get a good steak the first  few times, but after a while, you will have a good model of what is the right cooking time for a given thickness.

To translate this into ML terms, you have as input variables the steak thickness (S), the grill time (G) and your output is the taste (T).
If you try to purely optimize the classification error, you would look for a function f(S,G) that approximates T in the sense that |f(S,G)-T|should be small on average over the distribution of (S,G).
Hence you need to be able to accurately predict the taste for all values (within the observation range) of the pair (S,G).

However, in order to solve your problem, it is sufficient to find, for each value of S, a value of G that guarantees that T is good. This means that you do not need to build a full model (for all pairs (S,G)) but you only need a model which allows you to determine one good grill time and can be wrong otherwise.

This shows that by rephrasing the objective from prediction to control, you get a different problem so that finding the most predictive model might not the best thing to do.
In recent years, ML researchers have started looking at slightly different loss functions (than the simple prediction error) and settings. My feeling is that this will continue and possibly drift towards loss functions that correspond to control (since many real-life problems are control problems rather than prediction ones).

Learning to solve complex problems

I would like to come back to the tight relationship between optimization and learning.
Of course, there is much to say about this, but let us focus on one specific example: randomization.
Randomization is an old and well-known method for solving difficult (e.g. combinatorial) problems. Indeed, when one is faced with a complex problem where there are many combinations to try out, and very little structure in the search space, it is often convenient to introduce some randomness in the search.
As it turns out, you can often prove that a "stupid" random method will perform as well as a sophisticated one in terms of how close you can get to the optimal solution as a function of the computation time spent.

Let me give you some simple example: consider the d-dimensional unit cube and assume you are given a set of k d-dimensional hyperrectangles defined by the coordinates of their borders (2d such borders, hence 2d numbers characterize each hyperrectangle) that lie inside the unit cube  (the numbers are all between 0 and 1).
The problem is to determine the volume left out by these hyperrectangles.

Put in simple words, you have a cubic space from which you cut out (possibly overlapping) rectangular pieces and you want to determine the volume left out after you cut k such pieces out.

This seems like a simple problem but solving it exactly requires heavy computations: you essentially need to determine all intersections between hyperrectangles and the intersections between these intersections and so on... Of course this can be done, but will require exponential time in d.
This means that it is practically impossible as soon as the dimension gets bigger than say 20.

So, instead of trying to solve it exactly, one can try to approximate the solution with the following simple randomized method:
you imagine throwing a stone in the cubic space repeatedly and counting how many times it hits a hyperrectangle. The fraction of such hits will very quickly converge to the solution of the problem.

More precisely, imagine you can sample points in the d-dimensional unit cube independently and uniformly. For each such point it is easy to determine whether it is inside a hyperrectangle (it takes 2dk comparisons at most) and thus if one samples n such points, with a computation time 2dkn, one gets an estimate of the volume v which is (with large probability) at least within epsilon of v.
The size of this epsilon is roughly n^{-1/2} so that with 10000 draws you get 1% precision in your estimation, and this is independent of the dimension.

So you can have, in high dimensional spaces, a very cheap solution for solving the problem (which takes time linear in the dimension and not exponential, at the expense of yielding an approximate solution).
This is actually a very common phenomenon which has been largely exploited in solving many high dimensional problems.

Now the connection to learning: the randomized method proposed above is a learning algorithm. Indeed, you are trying to "learn" the fact that a point in the unit cube is covered or not by one of the hyperrectangles. It is a very simple learning problem since one is only interested in the volume of the empty space and not in a full description of this empty space, but the techniques that are required are basically similar. More precisely, the estimation of the error in the approximation involves computations of the same type as those used in learning theory for deriving bounds on the generalization error of learning algorithms.

Of course this was a very simple use of learning and there are plenty of ways to make more sophisticated uses of learning in solving complex problems. The message is that statistical learning theory can be useful for analyzing algorithms for solving complex problems (and not only for analyzing learning algorithms as such).