Machine Learning Thoughts

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).

The Meaning of Probability

The formalization of the concept of probability has a long history. Probability Theory is now a well-founded and very mature part of Mathematics, mainly due to its axiomatization by Kolmogorov who grounded the concept of probability in measure theory.
It may thus seem that defining and combining probabilities can be done in a unique way, without any questions.
However, there is still a lot of disagreement on the crucial issue: the interpretation of probability. The problem here is that interpretation means connection to the real world. In that respect, the issue is not just a technical one but also a philosophical one, which explains why there can be many different points of view.

First of all, it is possible to distinguish between the objective and the subjective points of view:

• Objective probability: the objective point of view consists in postulating that probabilities do not depend on the person observing events or performing experiments. This means that there exists some absolute notion of probability for every possible event and this probability originates from Nature itself. Once this is assumed, the question becomes : how to "measure" these pre-existing probabilities, or how to confirm that the probability of a given event has a given value?
• Subjective probability: in the subjective point of view, probabilities are not something that can be measured, but something one assumes. The idea is that events either occur or do not occur and the probability is not a property of Nature but rather a convenient way of representing someone's uncertainty prior to the event actually occurring.

There are two classical (and opposed) ways of interpreting probabilities: the frequency and Bayesian interpretations.

• Probability as frequency: in this approach, the probability of an event is defined as the ratio of how  many times the event occurs to the number of times a similar experiment is performed. For example, if you repeatedly flip a coin, the probability of this coin landing on "heads" will be defined as the percentage of trials where it does land on "heads". Of course, this will highly depend on the number of such trials and may vary from one sequence to another. However, this issue is solved by the theorem called "the law of large numbers" which essentially states that the frequency of an event in successive independent trials will converge to a fixed value (its probability). In other words, if you flip your coin again and again, the frequency will (slowly but surely) converge to a definite value. There are some issues about the definition of independent trials and about the fact that one can really perform successive experiments in exactly the same way, but we will not worry about this now.
• Bayesian probability: it is obvious that not all notions of probability (as they are used in every day life) can be properly captured by the frequency definition given above. For example, when one speaks about the probability of an event that may occur only once (hence it is not possible to perform repeated experiments) such as the probability of a politician being elected at a given election, it is clear that frequency does not make practical sense and cannot be tested. Another issue with frequency is that it makes sense in the limit only: say we start flipping a coin and it keeps landing heads up; how many times does it need to land heads up before we decide that this is not happening with probability 1/2?  Five?  Ten?  A thousand?  A million? There is no reasonable answer to this question. Hence (subjective) Bayesians do not attempt to measure probabilities, rather they consider that a probability is a "degree of belief" that someone may have in the fact that a given event will occur. The whole point is that how you obtain your "prior" probability or initial degree of belief (before observing anything) does not matter. What matters is how these values are combined and updated when events are observed.

There is of course a lot to be said about the above two interpretations and there are many refinements or deviations from these. I hope to be able to explore this in more details in later posts.

Scientific Names and Their Relationship

This is a followup of this post and of the comments made about my previous post.

I have use the idea of Rudi Cilibrasi and Paul Vitanyi (see their preprint here) of extracting from Google page counts a "semantic" distance between terms.
So I ran the following experiment: I did Google searches for the terms Statistics, Statistical, Data Analysis, Data Mining and Machine Learning.
The individual page counts came as follows:

Statistics	573000000
Statistical	158000000
Data Analysis	38600000
Data Mining	17500000
Machine Learning	5250000

Of course Statistics is the most common. One reason is that it is not exclusively associated to a scientific discipline.
Then, I used the so-called "Normalized Google Distance" (NGD) to assess the relationship between these terms. Here is the result:

	St.tics	St.cal	DA	DM	ML
Statistics	0.00	0.53	0.73	0.93	0.82
Statistical	0.53	0.00	0.49	0.72	0.65
Data Analysis	0.73	0.49	0.00	0.54	0.61
Data Mining	0.93	0.72	0.54	0.00	0.39
Machine Learning	0.82	0.65	0.61	0.39	0.00

It is interesting to notice that Machine Learning is more related to Statistics than is Data Mining. Also, Machine Learning and Data Mining are very close to each other, while Data Analysis is closer to Statistics.

I also tried to compute the NGD between these terms and the term "Company" in order to see which one had penetrated the corporate world the most. The results were not very enlightening. However, if you look at the page counts for the phrase "Statistics Company", or replace Statistics by the other terms, you get the following:

Statistics Company	23100
Data Mining Company	10500
Data Analysis Company	623
Statistical Company	163
Machine Learning Company	140

Interestingly, Machine Learning is very seldom associated to company, while Data Mining companies seem to abund.

Another possible measure, is the number of ads you get when you do these searches. I noticed that the search "Data Mining" or "Data Mining Company" are returning an incredible number of ads for data mining software and companies (much more than statistics or machine learning).

So there is still a lot to be done in order to make Machine Learning better recognized...

Data in the Corporate World

Dealing with data is becoming an important part of the job of most large companies. Within this area, tasks such as storing and managing data are now well-mastered, so that the key capability now becomes the analysis or leveraging of this data.
Hence Data Mining is becoming an increasingly important concern of most hi-tech companies. This trend is witnessed by the recent creation of the CDO (Chief Data Officer) title at Yahoo! (see here), which has been given to a former Data Mining researcher.
Another indication of this trend can be found in the educational domain: most computer science departments in the big US universities now offer courses in Data Mining or Machine Learning.
These terms are also now known to people remote from the scientific world.

So it seems that Machine Learning is no longer an obscure research field, and more and more a popular technological domain.

Deduction and Induction

It is enlightening to try and define terms properly when trying to understand foundations of a scientific domain. In the case of the learning phenomenon, the distinction between deduction and induction is a crucial one.

Deductive reaonsoning consists in combining logical statements according to certain agreed upon rules in order to obtain new statements. This is how mathematicians prove theorems from axioms. Proving a theorem is nothing but combining a small set of axioms with certain rules. Of course, this does not mean proving a theorem is a simple task, but it could theoretically be automated.

Inductive reasoning consists in constructing the axioms from the observation of supposed consequences of these axioms. This is what scientists like physicists for example do: observing natural phenomena, they postulate the laws of Nature.

Both deduction and induction have limitations. One limitation of deduction is exemplified by Gödel's theorem which essentially states that for a rich enough set of axioms, one can produce statements that can be neither proved nor disproved.
Induction on the other hand is limited in that it is impossible to prove that an inductive statement is correct. At most can one empirically observe that the deductions that can be made from this statement are not in contradiction with experiments. But one can never be sure that no future observation will contradict the statement.

How to be a Bayesian while pretending you are a Frequentist?

Using the Bayesian modeling approach is very convenient when designing learning algorithms. You just have to encode your prior knowledge and assumptions into a prior distribution and a likelihood function and then you can simply unroll the Bayes rule mechanism. Of course there are usually sophisticated computational problems, but no conceptual ones.
So-called "frequentists" usually try to justify the algorithm they design based on a theoretical analysis in the iid framework. Hence it is common practice (I am not saying here that I like this practice) to use a probabilistic error bound as a justification for a new algorithm.
The problem is that it is usually very hard to obtain such a bound and there is no unique way or guiding principle for doing so.

Fortunately, people have recently obtained bounds that involve a prior over a class of functions. They are called "PAC-Bayesian" bounds and are quite easy to apply to several different algorithms.
In a way this gives rise to a new principled method for producing new algorithms. Here is the recipe:

• You encode your prior assumptions into a prior distributions (just like in the Bayesian case)
• You plug this distribution into a PAC-Bayesian bound
• You use the bound as an objective criterion, so that the algorithm is simply minimizing the bound

This gives something that is similar in spirit to the MAP (maximum a posteriori) method. In my opinion, this is not any better or worse than MAP and there is no reason to believe that this way of designing algorithms is better than the Bayesian way.
Unfortunately, people tend to think that because the algorithm was derived from a bound which is some sort of formal mathematical statement, then it should be a better algorithm that if this were not the case.