Learning Program
A formal definition of learning program, as given by Tom Mitchell in his book, is stated below.
Definition: 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.
To formulate a well-defined learning problem, we must identify
The class of tasks
The measure of performance
The source of experience
For example, if we wish to formulate a ML problem of recognizing handwritten text, we define
The class of tasks : recognizing hand written words within images
Performance measure : percentage of words/ numbers correctly recognized.
Training Experience : A database of images containing hand-written words along with
the words in those images
Machine Learning Approaches
Machine learning problem can be broadly classified in to
1 Supervised learning
In supervised learning, the goal is to learn to predict the value of an outcome based on a
number of input values for which correct output values are available. Such data is called
the labeled data. Here, supervision is available in terms of known output (label) values.
Supervised learning is like using data to build predictive models
2 Unsupervised learning
In unsupervised learning, the objective is not to predict any outcome. We, therefore, do
not need labeled data. That is, there is no supervisor as in case of supervised learning.
We only have input data, and the goal is to find and describe regularities in the input.
We want to see ‘what generally happens, and what does not’.
Unsupervised learning is like identifying probability distributions or its characteristics
from data
3 Reinforcement learning
Reinforcement learning is learning what to do so as to maximize some notion of a
numerical reward. The learner is not told which actions to take, but instead must
discover which actions yield the most reward by trying them. In this approach the
learner takes a sequence of decisions so as to maximize cumulative reward.
Reinforcement learning is learning from mistakes (experience)
4 Semi-supervised learning
This is an approach that falls between unsupervised learning (with no labeled data) and
supervised learning (with only labeled data). Typically, semi-supervised learning attempt
to improve performance in one of these two tasks by utilizing information that is
generally associated with the other. For example, performance of a
supervised learning algorithm can be improved by utilizing the
information available in unlabeled data.
Overview of Supervised Learning
The goal of supervised learning is to predict the values of output using the values of input. In
statistical terminology, inputs are called predictors. Similarly, the outputs are called responses
or dependent variables. The term feature is more commonly used for a (transformed) input in
the pattern recognition literature.
Output can be a quantitative measure or a qualitative measure (also called categorical).
A prediction task is called regression when the output is a quantitative measure, and for
categorical output, the prediction task is called classification.
Similarly, inputs can also very in measurement types. Different types of prediction methods are
developed for different input-output combinations.
The supervised learning task can be loosely stated as follows:
Given the value of an input X, make a good prediction of the output Y, denoted by Y^ . If Y takes
values in R then Y^ should also take values in R. Similarly, for categorical outputs.
(xi, yi), i = 1, 2, …, N is called the training data, that is used to construct prediction rules.
Supervised Learning Process
To understand the concepts involved in supervised learning process, consider the problem of
predicting a binary output. We also assume that the inputs are binary.
If there are k input variables X1, X2, …, Xk, we need to build a model
Y^ =f ( X 1 , X 2 , … , X k )
Here, in the example problem, the function f should also take binary values.
Several possible functions to choose from
The function f is not known, and we need to identify it. The possible set of functions to
choose from is very large in general. If there are k binary features, as in the given
example problem, there are at most 2k distinct input examples. Since each one of these
k
can be either labelled 0 or 1, total number of possible binary functions are 22 .
To clarify the ideas, suppose there are only two binary features X1 and X2. The possible
distinct input examples are
Feature x1 x2 x3 x4
X1 0 0 1 1
X2 0 1 0 1
There are 16 possible functions to consider
f1 f2 f3
Feature x x2 x3 x4 Feature x x2 x3 x4 Feature x x2 x3 x4
1 1 1
X1 0 0 1 1 X1 0 0 1 1 X1 0 0 1 1
X2 0 1 0 1 X2 0 1 0 1 X2 0 1 0 1
f1(x) 0 0 0 0 f2(x) 0 0 0 1 f3(x) 0 0 1 0
… … ...
f14 f15 f16
Feature x1 x2 x3 x4 Feature x1 x2 x3 x4 Feature x1 x2 x3 x4
X1 0 0 1 1 X1 0 0 1 1 X1 0 0 1 1
X2 0 1 0 1 X2 0 1 0 1 X2 0 1 0 1
f14(x) 1 1 0 1 f15(x) 1 1 1 0 f16(x) 1 1 1 1
The training process
Now suppose we have received a training example, for which x1 = 1, x2 = 0, and Y = 1.
Now, out of 16 possible functions, 8 functions are consistent (shaded green above) with
this observation and 8 are not (shaded red). Thus, the inconsistent 8 functions are
discarded from further consideration.
In this example, every new example removes half of the functions from consideration
that are inconsistent with the new example.
In general. Every new example from training data reduces the class of functions from
which we need to identify the function f .
ill-posed problem
In the ideal scenario, if we have enough training examples, we will be ultimately left
with only one function, clearly that function would perfectly predict the output for new
examples.
However, in most cases, the number of possible functions is prohibitively large (in fact,
infinite) to be able to identify only one correct function from any reasonable amount of
experience.
Yet another possibility is that none of the possible functions are found consistent with
the available training examples. This can happen if the available Features cannot
uniquely determine the output, and we need to enlarge the feature space.
Thus, in practice, data by itself is not sufficient to find unique solution function f. Such a
learning problem is said to be an ill-posed problem.
Inductive bias
Because real world learning problem is generally ill-posed, we need to make some extra
assumptions to obtain a unique solution using the training data we have. The set of
assumptions we make, to make learning possible, introduces a bias in the learning
process. This bias is called the inductive bias in the learning algorithm. One way to
introduce inductive bias is to assume a class F to which f belongs (that is, using a model).
In general, learning is not possible without introducing inductive bias.
Model Selection
Since inductive bias is unavoidable, our objective would be to select a model that
minimizes the amount of inductive bias. The problem of selecting such as model is called
the model selection problem. That is, choosing the best class F from the possible classes.
While doing this, it is important to understand that the goal of learning is to achieve
best generalization (predicting the output for new instances) rather than best
explanation of training data.
To ensure good generalization, we need to
- Avoid underfitting and overfitting.
- Achieve the triple trade-off
o Complexity of the class F
o Amount of training data needed
o Generalization error
✔ Cross validation to choose the best class F.
• Validation data is effectively a part of training data.
✔ Choosing specific member f from F that minimizes the training error.
• In case of parametric approach, this amounts to estimating model parameters
(estimation problem)
Reference:
Tom Mitchell (1997): Machine Learning, McGraw Hill.
Ethem Alpaydin (2014): Introduction to Machine Learning, MIT Press