# Is deduction, genetic programming, PCA, or clustering machine learning according to Tom Mitchells definition?

Tom M. Mitchell defines machine learning as

A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P if its performance at tasks in T, as measured by P, improves with experience E.

For some algorithms that are usually counted towards the field of machine learning, I heavily doubt that they are learning algorithms according to the definition. Interestingly, all of them are part of Tom Mitchell's book "Machine Learning".

## Deduction

The "symbolist tribe" uses inverse deduction according to Pedro Domingos (see The 5 tribes of ML). While I'm not too sure what inverse deduction is, the idea of having a set of true statements and inference rules like Modus Ponens to create more/other true statements is clear.

Comming to the definition: What is experience here? How is performance measured? What does a typical task look like?

## Genetic programming

From Wikipedia:

Genetic programming (GP) is a technique whereby computer programs are encoded as a set of genes that are then modified (evolved) using an evolutionary algorithm (often a genetic algorithm, "GA").

What is experience in this case? Maybe "iterations" / "epochs"? (I'm not sure about the terminology)

## PCA

PCA and some other dimensionality reduction algorithms are in some way "fixed". The algorithm does not change with more data. It does not have parameters. Thinking about it, one might argue that it estimates the projection in a better way with more data.

But then: What is better? What is the performance measure P here?

## Clustering

I don't see a clear performance measure for Clustering (e.g. k-means). Also, the only kind of experience I can see is the number of samples.

• K-means has a very clear performance measure: SSE aka inertia. Aug 7, 2018 at 23:28
• SSE I guess is "sum of squared errors"?... hm, ok. The reason why I'm not super happy with that is that it doesn't really tell you a lot about the quality of the found clusters / a good number of clusters. But if SSE is your quality measure, what is experience then? It cannot be more examples, as more examples will always lead to higher SSE. Aug 8, 2018 at 5:23
• More experience in this logic is not more data, but more passes over the data. But as mentioned in my answer, I don't like this logic. Then any iterative optimization, say the Hungarian algorithm, suddenly is "learning". Aug 8, 2018 at 6:41

A while back, when presenting ML basics to experts of other domains, I also looked into the formal definitions; Mitchell's seems to be the most official/prominent is usage. However, I found that the interpretation can be also somewhat subjective. In addition, the lines between Machine Learning, Deep Learning, Artificial Intelligence and Statistics in general, do sometimes become a little hazy in various fields of application - the terms are also often abused and used as buzz-words (just like Big Data). I think the biggest guinine struggle is perhaps the interpretation of each of the terms that Mitchell introduces: Experience (E), Tasks (T) and Performance (P).

Perhaps it would be worth keeping another definition of machine learning in mind (my current favourite); that of Kevin Murphy from his book Machine Learning: a Probabilistic Approach (page 1):

... we define machine learning as a set of methods that can automatically detect patterns in data, and then use the uncovered patterns to predict future data, or to perform other kinds of decision making under uncertainty (such as planning how to collect more data!).

This is certainly a lot broader, and may help accept the greater everyday toolbox as machine learning, instead of tight constraints.

For these reasons, I would say my answer below is more of a discussion than a factual answer.

I'd happily be corrected by readers possessing better informed opinions or facts! :-)

## Inverted Deduction

Of the examples you list, I am least familiar with inverted deduction. It is described by Mitchell himself (in Section 10.6 of his book) and this helpful Quora post, as logically equivalent to induction! The latter link includes one paragraph describing this symbolist method, which makes the idea quite accessible to someone more similar to modern connectionist approaches:

The most successful form of symbolic AI is expert systems, which use a network of production rules. Production rules connect symbols in a relationship similar to an If-Then statement. The expert system processes the rules to make deductions and to determine what additional information it needs, i.e. what questions to ask, using human-readable symbols.

At this point, it helped me distinguish between mathematical induction and mathematical deduction. The quote above sounds a bit like a expert designed recommender system. Given that deduction implies to refer a universal hypothesis from axioms or known facts (I imagine Sherlock Holmes!), we start with some rules that come from experience (instead of starting with just data). The idea with inverted deduction is that we have some observations and can induce relationships/rules that support the data/observations, and from that we can improve our system. We accept this to be weaker than pure mathematical deduction, and the starting point differs to Mitchell's own definition of machine learning, but if machine learning is an iterative cycle, is our starting point in that cycle critical to the definition?

Putting inverted deduction in the framework of a machine learning problem (as per our definition with T, E and P), we have the following definition from Mitchell to help:

... assume as usual that the training data D is a set of training examples, each of the form $\langle x_i, f(x_i) \rangle$. Here $x_i$ denotes the $i^{th}$ training instance and $f(x_i)$ denotes its target value. Then learning is the problem of discovering a hypothesis $h$, such that the classification $f(x_i)$ of each training instance $x_i$ follows deductively from the hypothesis $h$, the description of $x_i$ and any other background knowledge B known to the system.

He explicitly writes that the Task is to extract the hypothesis (the target function) rules that explain the system as a whole. Experience is the observations plus background knowledge (including the experience of the experts who create/define the rules). Performance remains as the accuracy or strength of the final set of rules. It is especially the interpretation of experience as data as well as expert/background knowledge, which differs slightly from simple observations.

As a facit: induction allows us to make statements about relationships, mapping input to outputs on the known range of our observations, but it is not as watertight as deduction, which by definition must be a universal truth (and therefore becomes a theorem). This makes induction sound a lot like machine learning (and therefore inverted deduction!)- just as neural networks learn relationships very well, but only over their input domain i.e. not universally.

## Genetic Programming

Straight off the bat, I would say this does fall into machine learning by the given definition. Models are iteratively assessed on their ability to perform a predefined task, then further training data is used to improve the performance on that task.

Given the usual approach of allowing many models to train, then selecting the best models and allowing them to somehow be fused (equivalent to genetic cross-pollination in biological reproduction). The resulting child-model would thereafter (hopefully) contain the best traits of the two best parent-models. Just as can be the case in biology, or within Reinforcement Learning and exploration step (as opposed to exploitation), the resulting child-model also is sprinkled with a bit of luck/randomness in the form of a mutation. Here is a summary article. The resulting child-model may well be degenerate i.e. less performant than the parents.

OP: What is experience in this case? Maybe "iterations" / "epochs"?

Given the above rough description, I would call a training case as all the work done between the consolidatory steps (breeding and mutation: producing the child-model). This is also similar to the paradigm used within meta-learning (a great lecture from Ilya Sutskever), whereby a task is defined as the sample dataset, plus information about the task itself. This is inspired by the idea of allowing algorithms to "learn to learn". For me, this is very close to the idea of genetic algorithms and evolutionary models.

## PCA

I'm not convinced PCA falls into a machine learning algorithm; however, it is such a commonly used pre-processing method, I would be surprised if it didn't get a mention in any machine learning book.

If I had to force PCA into Mitchell's definition, this would be my best shot: The Task, T, would be simply that of PCA; to reduce the dimensionality of the dataset. The Performance metric, P; I would interpret as the percentage of the variance that is contained with the first $k$ principal components - e.g. just fix $k = 3$, and run the algorithm with more and more data. More data would allow this to be performed more accuractely, i.e. with higher levels of confidence and the variance should be described more densely be the denser set of input points. So, let's say P is given by:

$$P = \sum_{i=1}^{k} C_i$$

where $k = 3$, for example and $C_i$ is the $i^{th}$ principal component's normalised coefficient. This sum therefore integrates to 1 over all $k$.

If the value of P actually decreases after adding more data, I would perhaps argue that we have actually learned more about the sample distribution with the extra data, even though our performance metric technically indicates worse results.

Despite this attempt to shoehorn PCA into the definition - I am still uneasy about calling this machine learning (see the second paragraph in my conclusion).

## Clustering

I agree with you that the only real experience is the number of samples. To add to any doubts, clustering (like PCA), is an unsupervised method - there are typically no labels on the data.

If experience, E, is then the number of data points, the metric, P, would be the inherent error measured used to iteratively improve the clustering result. For example, in the case if KNN, it could be the sum of squared distances between points one cluster and those of a different clusters. Allowing the model to train with additional data points (assuming the ability to overfit), it would not produce a worse value for P: either the same or better.

In my opinion, clustering is included in many machine learning books, not because it falls nicely into Mitchell's definition, but because it is a widely used and extremely useful tool. That being said, it can also be used in the a non-parametric setting, e.g. using a Dirichlet process as a prior and allowing the number of clusters to grow as more data is provided. I find that idea to be easier to merge into Mitchell's notion of a model improving a metric given more experience!

The fact that clustering is indeed defined as un-supervised learning, i.e. without any sample labels, just makes the idea here more interesting to me.

## Conclusion

I agree with @Anony-Mousse, in that PCA and clustering really don't give the impression of a learning algorithm. I think it is because I conflate statistical learning with human learning. General discussion around machine learning and AI tends to use anthropomorphism: e.g. "AlphaZero learned from scratch how to play a wide range of Atari games"... If we replace AlphaZero with Alice or Bob, it is clear we are talking about a human. This way of describing algorithms leaks into methods like PCA and clustering - people say how PCA learns representations of the variance in the data, even though we struggle to align Mitchell's definition of machine learning to PCA. After the explosion of machine and deep learning since ca. 2012, we see there are still many undisputed terminologies floating around - something that is unavoidable for a rapidly devloping area.

To address the discssion in the comments to Anony-Mousse's answer: Arthur Samuel coined the term machine learning, as a computer being able to learn without being explicitly programmed. Here, in its original context, I believe it meant to learn as a human does, i.e. to exhibit the use of intelligence (paraphrased from quotes in this nice article). Humans learn a great deal from observations, even without knowing the correct answer (the case without labels). Given this, and drawing the direct comparison to unserupervised learning, one could argue that any process by which a machine is able to improve some metric is indeed a learning machine. So clustering as an example, is learning, as it improves a metric and derives new insights into data (without labels). In the case of PCA, the metric is unclear - it must be derived from the usefulness of the results for the task at hand: beauty is the eye of the beholder.

In the end, it doesn't matter too much to me, as long as we know what we are talking about and can make progress in research and applications thereof. My only concern is that this confusion makes teaching the subject more difficult and raises the barrier to entry for newcomers, who have to deal with sometimes contradictory terminology.

Some people like calling anything that uses data "learning".

And in the hype cycle world of today, anything that is AI, ML, data science, or deep learning just sells much better than "mathematical optimization" which seems so 1970s or 1980s.

I am not a big fan of this. It just adds more terms that cannot be distinguished well.

I recommend to use the term "learning" only when you have an "input" and a "desired output" (e.g. class label). Methods like PCA and k-means then are not "learning".

• I know I am perhaps nitpicking here, but does that mean you would never use the term unsupervised learning, as there are not labels? Aug 8, 2018 at 5:19
• Yes. "Unsupervised learning" is a stupid term that is all but well defined. It's usually used in a book about supervised learning, as blanket term for all the stuff not well covered by the book. Aug 8, 2018 at 6:37