Supervised Machine Learning

Learning Objectives

  • Understand supervised learning and the distinction from unsupervised learning

  • Understand how supervised learning may be used

  • Distinguish classification and regression problems

Distinguish Supervised and Unsupervised Learning

Another type of learning is called supervised learning. Unsupervised learning means discovering patterns from data, just data. Supervised learning means associating data with labels. When a father holds a baby saying “Daddy”, this is supervised learning: The baby learns to associate the father’s face (data) with the sound of “Daddy” (label). When a user identifies an email as spam and clicks the “spam” button in a mail reader, this is supervised learning: The mail reader learns to associate the email: the data, may include the subject or the content or the sender, or all of them with the spam label.

Supervised learning can be further divided into two types of problems: classification and regression. For classification problems, the labels are discrete values. They can be words, numbers, a finite set of options, etc. The labels are discrete because it makes no sense to have a label “between” two labels. For example, the input is the voice of a person and the output is the gender, either female or male.

Minimization Problem

Supervised learning is essentially a “minimization problem”. Suppose there is a collection of \(n\) images and each image can be represented by a word. Consider the following examples from the COCO dataset.

../_images/coco000000006040.jpg

Figure 55 Tram

../_images/coco000000007108.jpg

Figure 56 Elephant

../_images/coco000000042070.jpg

Figure 57 Bus

../_images/coco000000124975.jpg

Figure 58 Zebra

The \(n\) images are the sequence of inputs \({\bf x} = <x_1, x_2, ..., x_n>\). Each element \(x_i\) \((1 \le i \le n)\) can be a high-dimensional vector, such as an image. If an image has \(w \times h\) pixels, then \(x_i\) is a vector of \(w \times h\) dimensions, each pixel represents one dimension. For \(x_i\), there is a correct word \(y_i\) for describing the image. \({\bf y} = <y_1, y_2, ..., y_n>\) is the sequence of outputs. For the examples of images, \({\bf x}\) are the four images and \({\bf y}\) are \(<\text{Tram}, \text{Elephant}, \text{Bus}, \text{Zebra}>\) Please notice that \({\bf x}\) and \({\bf y}\) are sequences because \(y_i\) is the correct output for \(x_i\). If \({\bf x}\) and \({\bf y}\) were sets (the order in a set does not matter), then we would have problems.

Consider a machine model \(f\) that intends to learn the relationships between the inputs and outputs. Ideally, \(f(x_i)\) should be \(y_i\), meaning that \(f\) maps each input \(x_i\) to the correct output \(y_i\). In reality, \(f\) may make mistakes. Because \(f\)’s output may be wrong, we define its actual output for \(x_i\) as \(\tilde{y_i}\). The mistake is defined as the difference between \(\tilde{y_i}\) (the actual output of \(f\)) and \(y_i\) (the desired output of \(f\)). The differences between \(y_i\) and \(\tilde{y_i}\) are the mistakes.

Usually, the quality of \(f\) is measured by how many and how much mistakes \(f\) makes. One way to mesure is

\(\underset{i}{\overset{n}{\sum}} |y_i - \tilde{y_i}|\)

or

\(\underset{i}{\overset{n}{\sum}} (y_i - \tilde{y_i})^2\)

The goal is supervised learning is to find \(f\) so that the cumulative errors are as small as possible. Thus, this is a minimization problem.

Classification and Regression Problems

“Wait”, you will probably ask, these are classification questions: classifying the images into different categories: Tram, Elephant, Bus, and Zebra. Does it make sense to write the distance between these categories? The answer depends on how you define \(y_i - \tilde{y_i}\). It is possible to define it as \(y_i - \tilde{y_i}\) as 0 when they are the same and as 1 when they are different. Using this definition, learning is still a minimization problem: The goal is to find \(f\) to minimize the number of pairs when \(\tilde{y_i}\) and \(y_i\) are different.

Supervised learning can be generally divided into two types of problems:

  • Classification Problems: The answers are “discrete”, such as nationalities, genders, brands of cars. There is no “ordering” among these values and it makes no sense to “interpolate” between the values. It makes no sense to say \(\frac{\text{USA} +\text{France}}{2}\) (nobody can get a passport that is printed by USA and France). That’s why the labels are discrete.

  • Regression Problems: The answers are numeric values, such as temperatures, speed of a car, the price of a house.

Quantify Errors in Classification

For classification problems, the answers are discrete and there is not definition of distance, other than whether \(\tilde{y_i}\) is the same as or different from \(y_i\). It does not make sense saying anything like \(|\text{Tram} - \text{Elephant}| < |\text{Bus} - \text{Zebra}|\). For regression problems, the answers are numeric and distance can be defined. If \(y_i\) is 1, then the answer 3 is worse than the answer 1.5.

What are good ways to evaluate the quality of \(f\) for clssification problems?

Precision and Recall

One common method is to calculate precision and recall.

Consider the four images above (bus, zebra, tram, elephant).

Suppose \(x\) is an input image and a classification function \(f\) gives output \(\tilde{y}\) (i.e., \(f(x) = \tilde{y}\)). Consider the class “bus”, there are four possibilities:

  • The image is a bus and \(\tilde{y}\) is “bus”. This is called true positive (TP).

  • The image is not bus and \(\tilde{y}\) is “bus”. This is called false positive (FP).

  • The image is a bus and \(\tilde{y}\) is not “bus”. This is called false negative (FN).

  • The image is not bus and \(\tilde{y}\) is not “bus”. This is called true negative (TN).

These four scenarios can be expressed by the table:

\(\tilde{y} = f(x)\)

bus

not bus

\(x\)

bus

true positive

false negative

not bus

false positive

true negative

../_images/positivenegative.png

Figure 59 Four possible outcomes of classification

In this figure, the left side (blue) means the object exists in the image. The right side means the object doest not exist in the image.

A commonly used method to quantify a classification is called presision. It is defined as

\(\frac{TP}{TP + FP}\)

It means “among the reported positive cases, how many are actually positive?”

Another commonly used method is called recall. It is defined as

\(\frac{TP}{TP + FN}\)

It means “among all positive cases, how many are actually found?”

F1 Score

Precision or recall individually does not provide enough information to evaluate \(f\). F1 score uses both precision and recall:

\(2 \times \frac{\text{precision} \times \text{recall}}{\text{precision} + \text{recall}}\)

Confusion Matrix

Let’s add four more images:

../_images/coco000000001584.jpg

Figure 60 Bus

../_images/coco000000002006.jpg

Figure 61 Bus

../_images/coco000000005037.jpg

Figure 62 Bus

../_images/coco000000545129.jpg

Figure 63 Zebra

Among the eight images, four are buses; two are zebra; one is a tram; the last is elephant. The following table shows the situation if \(f\) is always correct. The rows represent the inputs \(x\). The columns represent the outputs \(\tilde{y}\). The table shows that there are four bus images (\(x\)) and all of them are classified as bus. No input bus image is classified as zebra, tram, or elephant. Similiarly, the two zebra images are classified as zebra correctly. The correct results should have non-zero values only along the diagonal.

input

Output

bus

zebra

tram

elephant

bus

4

0

0

0

zebra

0

2

0

0

tram

0

0

1

0

elephant

0

0

0

1

Next, consider another function \(f\) that is not so good. The result is also expressed in a table:

input

Output

bus

zebra

tram

elephant

bus

2

0

1

1

zebra

0

1

1

0

tram

0

0

1

0

elephant

0

1

0

0

The four bus images are classified as 2 bus, 1 tram, and 1 elephant. Please notice that the numbers in the row add to four. The two zebra images are classified as 1 zebra and 1 tram. The tram image is classified correctly. The elephant image is classified as tram. This is called a confusion matrix: it measures how many inputs are incorrectlly classified.

The difference of these two matrices (the sum of absolute values or sum of squres) can measure how good \(f\) is.

Regression Problems

Regression problems the values are continuous. Consider the following example. We have some values of \((x,y)\). What we want to do is to find the best estimate of \(y\) given a value of \(x\).

x

y

-5.15729202513464

-18.340290586929

5.67238162670287

6.22643565856931

6.40374670885682

21.7357321986057

5.65689483769905

5.13168505805081

-7.47512108623663

-20.8106624661057

-0.711593755459095

-2.54910987787733

-6.95917493967064

-28.2506351240132

0.594903088106715

1.93288808859777

-2.13227865685453

-11.5116804440814

0.092071535500583

2.97502762479007

1.41908176266247

-1.61369639836753

5.93255235081788

12.6030743771715

3.0231412917473

2.54359754526641

-0.817471009793984

-15.0948200499757

-6.83628619785253

-19.3228061431844

4.26187912325374

13.3248920273636

5.645502603752

5.38510507733904

5.41713539454346

10.7935811954502

0.546454811623898

-6.86445487862335

-7.61321344126601

-24.6346836202365

9.06168077872272

29.0798518348037

-9.03699956534284

-28.5123544071629

-6.54329007709694

-28.8177837612506

0.852020463402736

4.67263051840162

-3.7286914781359

-9.12184292513442

-5.15737565352333

-17.2276338083982

-1.3996170643474

-8.99958774263143

2.38724883946816

-2.31967888256527

-8.0563844593181

-29.4361617277288

-4.10526781323183

-14.0127370704183

-2.67167911783576

-5.6033246889177

-3.56273630648561

-11.8145232865756

The pairs are plotted below:

../_images/xy11.png

Next chapter (Gradient Descent) will explain how to find a line that has the least sum of error square.

Overfitting

Have you ever had the following experience: You studied extremely hard for an exam and could answer every practice question perfectly. However, you performed in the actual exam. How can this be possible? This is called the overfitting problem in machine learning (seems to be applicable to human learning also).

Consider the following figure (this figure has fewer data point.).

../_images/xy21.png

This is the data:

x

y

13.25288

40.89277

-14.8602

-45.3906

-5.68594

-22.806

18.02815

50.83212

-10.9294

-30.8796

-19.5857

-60.713

-6.93697

-32.6769

-1.07072

-3.18677

7.796119

16.73295

-11.9286

-43.9226

13.36518

28.79474

If this trend is consistent, by interpolation, when \(x\) is 6, the value of \(y\) is around 13. By observation, a straight line seems to be a pretty good way to express the relations between the values of \(x\) and \(y\), as shown below.

../_images/xy3.png

The straight line, however, is not a “perfect” solution: it does not pass most points. Would it be better if we can find a polynomial that passes every data point? Given a list of \(n\) pairs of \((x, y)\), it is always possible finding a polynomial of degree \(n-1\) passing every pair of point, as long as the \(x\) values are distinct.

Using the polyfit function in MATLAB, it is possible to find a polynomial of the 10th degree passing all elevent points. The coefficients are

Degree

Coefficient

\(x^{10}\)

-0.000000005588280

\(x^{9}\)

-0.000000016933579

\(x^{8}\)

0.000004911667751

\(x^{7}\)

0.000019301830733

\(x^{6}\)

-0.001461105562290

\(x^{5}\)

-0.007306583900806

\(x^{4}\)

0.166442447665419

\(x^{3}\)

0.999911252411206

\(x^{2}\)

-5.336314308798566

\(x^{1}\)

-34.670075611821026

\(x^{0}\)

-33.190351515165069

The following shows the polynomial when \(x\) is between -20 and 20.

../_images/xy5.png

Zoom in the vertical axix, we can very clearly that this polynomail passes every data point

../_images/xy4.png

Is this polynomial a good representation of the data? Based on this polynomial, when \(x\) is -18, the \(y\) value is 329.303. When \(x\) is 6, the \(y\) value is -113.469. Are these expected? From the original data, we would expect that when \(x\) is -18, \(y\)’s value is around -50. The problem is overfitting: the polynomial intends to match the data, including the noise. A better solution is to use a lower-degree (such as linear) and allow some errors. Allowing some errors can be better generalizing the seen data to unseen data (such as when \(x\) is -18 or 6).

How can this concept be applicable to human learning? Some people study “too much” and memorize the details, instead of fully understanding the concepts. These people try to match problems with what they have already seen and answer based on these seen problems. If the new problems are different, these people may be unable to solve the new problems. They can solve the seen problems perfectly (like the 10-th degree polynomial) but these people cannot handle new problems.