Before ML101 | Why and How We Learn from Examples?

So from our last post, we saw that computation is essentially fixing a routine to get some output from some input, for practical purposes.

Traditional wisdom is that the routine is set by humans. Programmers design an algorithm to operate on the input to generate an output. A branch of theoretical computer science concerns itself with the analysis of such algorithms like complexity analysis, which asks how much time and space an algorithm consumes.

In certain scenarios, however, algorithms with clean and clear routines are sometimes hard to find. And this is when machine learning kicks in: it tries to unearth the algorithm out of given examples.

We restrict machine learning to supervised learning in this post.

The Perplexity of Human Mind

One canonical problem in machine learning is handwritten digit recognition: given the image of a handwritten digit, output the actual digit it shows. The task is trivial for a human brain, but when you try to design an algorithm to do the work, you find it surprisingly hard to say how you did it.

You might start by detecting closed loops, to separate 1, 2, 3, 5, 7 from 4, 6, 8, 9, 0. But how do you write a rule that tells 6 from 9? We think of orientation, but how do you make the rule to distinguish orientation for an image made up of pixels? When you try to be machine-level precise about your own decision process, you find the features are not always obvious.

This is an instance of Moravec's paradox — things humans sometimes find hard (chess, symbolic integration, long division) turned out to be comparatively easy to program, and things that are seemingly easy for the human brain (recognizing a scrawled 7) turned out to be hard to program. Sometimes, we cannot explain how our brain works.

And such perplexity shows up everywhere.

Define courage.

How would you define courage?

This is the same question Socrates put to Laches in Plato's dialogue Laches. The discussion felt like nitpicking to me when I first read the book. Let's take a closer look:

Laches first defines courage as standing your ground in battle. Socrates counters with Spartans who won by deliberately retreating — and points out the definition doesn't even cover courage at sea. Laches tries again: courage is endurance of the soul. Socrates negates that too — foolish endurance is just harmful, and a man who fights knowing he's outnumbered seems more courageous than one who fights with the advantage. A third speaker, Nicias, proposes that courage is a kind of knowledge — knowing what's truly to be feared and hoped for. This fails as well: knowledge is broad, and knowing something doesn't make you act on it.

When I got impatient with such stuff, I found the following quote at the end of the conversation:

SOCRATES: Then, Nicias, we have not discovered what courage is.

NICIAS: We have not.

Okay, fair enough.

Machine Learning

The story demonstrates how hard it can be to incrementally add rules to define courage, and yet they all somehow know how to distinguish a courageous deed. So instead of handcrafting rules by hand, we provide abundant examples and design an algorithm to extract the rules underneath. And that's the spirit of machine learning.

Traditional computation:

human: designs [algorithm]
input + [algorithm] -> output

Machine learning:

human: designs [sample set] and [learning method]
[sample set] + [learning method] -> [inference rules]
real input  + [inference rules] -> real output

Now, instead of designing an algorithm, the programmer needs to design examples as well as a learning algorithm. But in a lot of cases, it is worth the trade.

The canonical task in machine learning is handwritten digit recognition we mentioned earlier. It is also referred to as MNIST, since MNIST is the go-to dataset for this task. MNIST is a dataset of 70,000 labeled images of handwritten digits. Each image is 28 by 28 in pixels, with each pixel an integer between 0 and 255 representing the greyscale at that pixel. Specifically, 0 stands for background and higher values stand for ink.

A simplified example with spaces representing 0s is shown below:

[[ , ,3,4,3, , ],
 [ ,2,3, ,3,4, ],
 [1, , , , ,2,5],
 [ , , , ,4,5, ],	->	2
 [ , , ,5,5, , ],
 [ ,3,4, , , , ],
 [5,5,6,5,4,3,3]]

So the input is a 28 by 28 matrix. The output is an integer from 0 to 9. And the task is to come up with a fixed procedure that operates on the input to tell which number it represents.

It may take you days to craft a process sequence to complete the task. But providing examples, which is labeling images with their corresponding digits in this case, is generally cheaper. With 70,000 labeled examples in MNIST, and a carefully designed learning algorithm, the learned inference can perform at 99% accuracy.

In machine learning, constructing good samples is sometimes more important than the learning algorithm.

Learning from Examples

The remaining question is how to uncover the underlying rules from given examples. There are multiple approaches. But before diving into them, let's define the problem with more precision.

Using the MNIST setting: our goal is to find a process that takes in an image and outputs the number it represents with high accuracy. And it should work well on all valid inputs. Now we try to model this mathematically.

We have an input in the form of a 28 by 28 matrix. We want an output that is an integer from 0 to 9. Every input gets exactly one output, so what we are after is a function. Each of the 784 pixels takes one of 256 values, so there are $256^{784}$ possible input images. Each one of those images can be sent to any of the 10 digits, independently of all the others. So the number of possible functions is

10^{\left(256^{784}\right)} \approx 10^{1.15 \times 10^{1888}}

Thus we have a function space $\mathcal{H}$ containing all functions from a 28 by 28 matrix to a digit, and we want to find a target function $f \in \mathcal{H}$ that maps each image to the digit it shows. The 70,000 examples are what we have to find it with.

To design a machine learning algorithm is just to design ways of utilizing these examples in search of our target function. But notice that our input space is extremely large and that the number of examples is comparatively small. And in most cases it is not possible to iterate over the whole function space.

We can mitigate this by making some assumptions, like an assumption that the target function can be nicely approximated with polynomials of n degrees. Or such function can also be approximated by a combination of decision rules of maximum number. Or one can approximate the function using a neural network which is the most widely used option these days.

This is an important assumption we impose in order to move on, which is called inductive bias in machine learning. It should not be taken for granted when trying to apply machine learning.

Estimation Viewpoint

Suppose we narrow our search to functions that can be described by a finite list of numbers — call that list $\theta$ , the parameters. A candidate function is then written as $f_\theta$ , and choosing a function reduces to choosing $\theta$ . This turns our problem into one you may already have met in a statistics course: parametric estimation. We have data, we have a family of candidate models indexed by $\theta$ , and we want to pick a $\theta$ .

To do that we need to treat the examples as data in the statistical sense. We assume they are drawn independently from a fixed underlying distribution: each example does not depend on the ones before it, and they all come from the same source. This is the i.i.d. assumption (independent and identically distributed). This assumption is not always met and there are methods regarding those situations, but we focus on i.i.d. assumption here.

There are many options to get the $\theta$ . The standard first answer in statistics is maximum likelihood.

To frame the problem in a statistical sense, we now think of our function as not outputting a digit number, but instead outputting a distribution, which is probabilities over the ten digits and sums up to 1. Thus, for an image $x$ , the output $f_\theta(x)$ is a vector of probabilities of length 10.

In this setting, $f_\theta$ tells how probable an image is to be categorized into each category. This is called likelihood. And with such a $f_\theta$ , we can then compute how likely our example dataset is labelled the way it is. The principle of maximum likelihood is to choose the $\theta$ that makes current labeling most likely to happen. Also since the examples are independent, the probability of observing all of them together is the product of the individual probabilities. Picking the $\theta$ that makes this product largest is maximum likelihood estimation:

\hat\theta_{\text{MLE}} = \arg\max_{\theta} \prod_{i=1}^{n} p(y_i \mid x_i; \theta)

We will not dig into how to actually find that $\theta$ . It is an optimization question, and it is where most of the technical machinery of the field lives. But we have now assembled a nearly complete machine learning pipeline:

Goal: get a mapping from an input image to the corresponding digit.

Method:

Assume the mapping can be approximated by $f_\theta$

Collect 70,000 examples under i.i.d assumption.

Estimate $\theta$ by maximum likelihood principle.

But Why Likelihood?

One should notice that the parameter $\hat\theta_{\text{MLE}}$ is, by construction, the one that best explains the examples we collected. Is it the golden rule?

This principle is well-motivated and actually does behave well, and proved to be "good" under conditions I won't dig deeper into. But I'd like to ask the question: what would make an estimate "good"?

In fact, we can be quite limited to evaluate whether an estimation is a good one. Or even further, it seems hard for us to define "good" in this sense. One answer is that a good estimate should be "close" to the true function. But then, what does "close" mean for two functions? And also, we never really have the true function, and thus the distance can never be measured.

In light of this, we don't have a golden rule. And we can only set our own objectives. In the MLE case, I want my estimation to have maximized likelihood. I can have other objectives, though, like I want to make the cost of prediction errors as low as possible, if my errors have different penalties on different categories. And thus we can coin a loss function $L(\hat y, y)$ , which scores how bad it is to predict $\hat y$ when the truth is $y$ . The expected loss over all inputs is called the risk.

But still, we cannot compute that average: it ranges over inputs we do not have. So, second, we approximate it by averaging over the inputs we do have. This is the empirical risk:

\hat R(\theta) = \frac{1}{n}\sum_{i=1}^{n} L\big(f_\theta(x_i),\, y_i\big)

And choosing the $\theta$ that makes this number smallest is empirical risk minimization, or ERM.

This is another principle to get $\theta$ .

Machine Learning Recipe

Actually, it can be proved that MLE is an instance of ERM when you set the loss in ERM as $L = -\log p(y \mid x; \theta)$ .

And this reveals that there is no golden rule to decide which $\theta$ is actually better. It all comes down to what your objective is.

This is the entire estimation viewpoint of machine learning, and it is the foundation of most neural-network-based deep learning frameworks. As Goodfellow, Bengio and Courville put it:

Nearly all deep learning algorithms can be described as particular instances of a fairly simple recipe: combine a specification of a dataset, a cost function, an optimization procedure and a model.

We assumed a parametrized function family, which is the model indexed by the parameter $\theta$ . We designed a cost function, which is the loss in ERM. This is used to define what "good" is for our purposes. And different scenarios might have different understandings of "good". We have also constructed a dataset, which is our examples. The final part is to run an optimization procedure to find the corresponding parameters, which deserves another article and will not be discussed in this post.

And now we can update our pipeline and complete a machine learning recipe:

Choose a family of functions indexed by parameter $\theta$ with inductive bias

Construct sample set under i.i.d. assumption

Decide on your objective, defining what "good" means to you, derive the corresponding loss function

Search for $\hat\theta$ using optimization methods

Other Viewpoints

Actually, regarding examples as samples drawn from i.i.d. underlying distribution is just one way of regarding the examples. And there are multiple other ways to view the examples, and they can lead to machine learning algorithms that are not based on neural networks.

K-nearest-neighbor is one such example. In this setting, we keep all examples, and when given a new image, we find the stored images most similar to it and take a majority vote of their labels. Examples now form a decision border in input space. This time, the model is considered non-parametric. And all examples collectively form a model.

But still, using neural networks is the dominant approach these days. And we should be aware that the use of neural networks comes with the price of many (usually) unstated assumptions mentioned above.

Several Notices

First, on generalization. Our ultimate goal is a function that works on all valid inputs, and yet we only have a restricted number of examples. The ability to work correctly on valid but unseen inputs is called generalization — a somewhat misleading name, I think. We say a model generalizes well when it performs well on data outside the sample set, but that data is still assumed to come from the same underlying distribution. Data from a different distribution — say, digits written by someone with a very different hand, or photographed in poor light — is called out-of-distribution, and generalization in the technical sense promises nothing there.

Second, on choices. You might have noticed that we have made tons of design choices along the way, like the model we choose, the size of parameters, how to define "good", and the choice to represent output as a distribution instead of a digit number. These design choices are actually mostly grounded in proper mathematical assumptions, which is out of the scope of this post.

Third, what has the machine learned, actually?

The question is relevant because you might have noticed that our estimated function maps an input to one of ten digits, but we can't interpret how it does so. What's more, since the estimated function is total, when given a photograph of a cat, it will still return a digit between 0 and 9, with no indication that anything is wrong.

Is this acceptable? Especially after recalling an old quote of Confucius: "true knowledge is to know the extent of one's ignorance".

As we mentioned earlier that constructing good examples matters as much as the algorithm. Here is where it comes due. Our sample space is not uniform within the input space — we only supplied images of digits. We have no images of letters, or random noise, or images of cats. So the learned function was never asked to distinguish digits from non-digits. It was asked to sort digits from each other, and that is all it can do.

The consequence is that models exploit whatever happens to work on the data given, and the mechanism might differ from what a human would think acceptable. An example of this would be the LIME experiment where researchers trained a husky-versus-wolf classifier on images in which wolves appeared on snow and huskies did not. And the model learned to detect snow as a way of telling a husky apart from wolves.

And thus it is known that the result can inevitably make use of shortcuts.

But if you find this situation not ideal, can we add an output representing that the image is a non digit? While this is possible, it might be more tedious than you might think. Our original input space is merely valid images of digits. We can view it as rather constrained, with only ten categories, each projecting to the input space from a higher dimension. And each projection has some kind of distance in between. But with this additional label, we first cannot be sure that our function can be nicely approximated within a finite parametric function, we have also difficulty explaining those "in-between" areas. And making such design decisions sometimes requires examining statistical assumptions from bottom up.

Epilogue

So basically, machine learning is to gain a mapping from input to output.

With a fixed set of training data and a fixed learning algorithm, the parameters can largely be fixed, thus determining a mapping from input to output. So if we want to improve this final mapping, we can curate training data as well as update learning method.

I hope this article has given you an intuitive understanding of the following:

why we use machine learning
what machine learning is, and
how machine learning is constructed

Many details are left out such as the asymptotic quality of MLE, how optimization works, etc. This is because the author wants to provide a principled intuition on the outline of machine learning instead of being precise on key components. I hope the post has done the job. The reader is however encouraged to explore those technical details.

References

The contents of this article come mostly from my understanding of the book Deep Learning by Goodfellow, Bengio and Courville; and CMU 10-716: Advanced Machine Learning.

Chapters 5 and 6 of the deep learning book are highly recommended, which I think is an underrated and systematic review of machine learning and neural networks for anyone who wish to dig deeper into the field.