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.
