The Learning Problem: When Machine Learning Is the Right Tool | NTU Hsuan-Tien Lin Machine Learning Foundations Lecture 1

🌏 中文版

Video status: Videos included. This article is written from the official MOOC handout 01_handout.pdf and transcripts of this lecture's five official videos, with the content following the handout. The transcripts are machine transcripts made for this article (Whisper), not official captions, and no human has proofread them. The videos are taught in Mandarin; the slides are in English. Each section opens with its official video and the approximate time ranges. Page numbers refer to the number at the lower right of each slide (0/27 to 27/27), and wherever the text says "in the lecture" it is paraphrasing what is said in the video.

This is Foundations Lecture 1 in Reading NTU Hsuan-Tien Lin Machine Learning Foundations & Techniques, and the starting point of the whole series. The Roadmap on page 5 of the handout divides Foundations into four questions, and this lecture opens the first one, "When Can Machines Learn?". It has no algorithm yet. It does two pieces of groundwork: it makes clear what problem machine learning solves, and it writes that problem down in a set of symbols that every later lecture uses.

The only prerequisites are being able to program and being able to read notation like $f: \mathcal{X} \to \mathcal{Y}$. After reading, you should be able to take any problem and use three conditions to judge whether it suits machine learning; break an application into input, output, target function, data, hypothesis set, algorithm, and final hypothesis; and say what machine learning, data mining, artificial intelligence, and statistics each care about.

How the course is taught: foundation oriented, told as a four-part story

(Video 00:25–01:09 covers the course logo, 01:09–03:06 the drawbacks of two common ways of teaching, 03:06–04:27 what "foundations" means, 04:27–06:31 the four questions, 06:31–09:03 the history of the course, and Fun Time follows.)

Two ways of teaching, each with an obvious drawback

Page 1 of the handout says machine learning is a mixture of theoretical and practical tools, so courses usually land at one of two ends:

• Theory oriented: derive everything deeply for solid understanding, but it is less interesting to a general audience.
• Techniques oriented: flash over the sexiest techniques broadly for shiny coverage, but there are too many techniques, and they are hard to choose and hard to use properly.

In the lecture, Lin adds a passage on each end. At the theory end, you come away thinking the mathematics of earlier researchers is beautiful, but people who want to apply machine learning in their own field find it not practical enough. At the techniques end, each class teaches two or three methods, and after a few weeks you have learned dozens, yet when you actually need one you do not know how to choose or how to use it properly. The comparison Lin uses is a character in a martial arts novel who has learned too many moves and does not know which one to use on the battlefield.

This course takes a third route, which the handout calls foundation oriented.

What "foundations" refers to

Page 2 of the handout lists what goes into the course: philosophical illustrations, key theory, core techniques, usage in practice, and "hopefully" jokes, which together make up what every machine learning user should know. In the lecture, Lin specifically explains the word "foundations" in the course title: it refers to groundwork, the part you must have before you can put a building on top, and it does not mean the content is easy. Once you have learned it, machine learning is your tool, and you do not become its slave.

The opening of the lecture also mentions that the logo is made of four figures. The two smaller ones are explained in the next lecture, and the two larger ones only late in the course; the hint is that red stands for dangerous and blue for not dangerous, which corresponds to "when is it dangerous to use machine learning". This article just notes the foreshadowing for now.

Four questions

The handout tells the whole course as a story in four parts. The parentheses after each part give the aspects it involves:

Order	Question	Aspects marked in the handout
1	When Can Machines Learn?	illustrative + technical
2	Why Can Machines Learn?	theoretical + illustrative
3	How Can Machines Learn?	technical + practical
4	How Can Machines Learn Better?	practical + theoretical

In the lecture, Lin strings them together like this: first ask when machine learning can be used; in those situations, why does it work; once you have the "why", it is easy to understand how the basic methods let a machine learn something; and once you understand the methods, ask how to do better. Lin also stresses that no part is about a single aspect: the most theoretical second part weaves in the philosophical meaning behind the theory, and the most applied fourth part also explains the theory behind the applications.

The handout's comment on this design is that it allows students to learn "future/untaught" techniques or study deeper theory easily.

The history of the course

Page 3 of the handout compares two versions:

	NTU version	Coursera version
Length	15 to 17 weeks, 2+ hours each week	8 weeks of "foundation" (this course) plus 7 weeks of "techniques" (the coming course)
Language	Taught in English	Taught in Mandarin, to reach more audience in need
Format	Blackboard	Slides, improved with Coursera's quiz and homework mechanisms

Details added in the lecture: the course has been taught at NTU since 2008, five years by the time of recording; the difference between 15 and 17 weeks depends on whether holidays fall in that semester; most of the students are from computer science, with others from electrical engineering, other engineering departments, and even finance and biology backgrounds. Fifteen weeks is too long for people taking a course online, so it was cut into two courses, and the last 7 weeks became a separate course, Machine Learning Techniques. Lin says the content of the two courses taken together is almost exactly the same as the original NTU course.

At the bottom of this page the handout states the goal: try making the Coursera version even better than the NTU version. The wording in the lecture is more conservative: the hope is that the online course keeps the same quality as the NTU course.

Fun Time: which description of this course is true

Question (page 4 of the handout): Which of the following description of this course is true?

1. the course will be taught in Taiwanese
2. the course will tell me the techniques that create the android Lieutenant Commander Data in Star Trek
3. the course will be 15 weeks long
4. the course will be story-like

Answer: 4. The handout gives one sentence for each choice. (1) No: the course is taught in Mandarin, and the lecturer's own Taiwanese is, in the handout's words, not good enough for teaching "yet". (2) No, although what the course teaches may serve as foundations of those future techniques; in the lecture, Lin adds that building that kind of robot is still an area of ongoing research. (3) No, unless you choose to join the next course; the lecture puts it more plainly: this course is 8 weeks, and it is 15 weeks only if you take both. (4) Yes. The purpose of this question is to have you confirm two practical things: the course is 8 weeks long, and it does not promise to teach you to build what you see in science fiction films.

What machine learning does, and when to use it

(Video 00:00–03:41 goes from learning to machine learning, 03:41–05:51 makes skill concrete, 05:51–08:42 gives the tree recognition example, 08:42–12:51 the four use scenarios, 12:51–13:36 the fishing metaphor, 13:36–15:53 the three conditions, and Fun Time follows.)

From learning to machine learning

Page 6 of the handout defines the terms with two parallel lines:

• Learning: acquiring skill with experience accumulated from observations.
• Machine learning: acquiring skill with experience accumulated or computed from data.

The only differences are that the starting point changes from "observations" to "data", and the process in between changes from a human brain to a computer's computation. In the lecture, Lin gives three kinds of human learning: attending a class, a child learning to speak by listening to the people around (Lin uses a daughter who had just started talking as the example), and reading a book. What the three share is that they start from observations. Hearing, sight, and even smell and touch all count as observations, and the brain turns them into skill. Machine learning is a big name, and Lin says that at bottom it is using a computer to simulate this process: the computer's "observations" are whatever we feed it or whatever it can get for itself, collectively called data.

Making "skill" concrete

The word "skill" is too vague. Page 7 of the handout replaces it with something measurable: skill means improving some performance measure, for example prediction accuracy. The definition then becomes:

machine learning: improving some performance measure with experience computed from data

Written as a flow, that is "data → ML → improved performance measure". The analogy in the lecture is that after learning mathematics you prove things more correctly, and after learning English you speak it better; for a computer, if its performance on some task gets better, we say it has learned something.

The first application the handout gives is computational finance: stock data goes in, and more investment gain comes out. In the lecture, Lin describes it as feeding the computer the past ten years of stock data, having it analyze the data and tell you how to invest from tomorrow on; only if following its advice really earns more does the machine count as having learned something.

This definition has one advantage: it turns "has it learned anything" into something you can check. Once a performance measure is specified, you can compare before learning with after.

Why not just write a program: recognizing a tree

Page 8 of the handout shows a photo of a tree and asks: to make a computer recognize whether a photo contains a tree, there are two routes.

1. "Define" trees first, then hand-program the definition. The handout's comment is "difficult". In the lecture, Lin asks you to try: you would have to write the way you recognize trees in your own head as a hundred rules, and most people have no idea what those hundred rules would even say.
2. Learn from data (observations) and then recognize. The handout says a 3-year-old can do so. In the lecture, Lin says no child learned to recognize trees from a hundred rules given by their parents; parents do point and say this is a tree and that is not, but the larger part is what children internalize on their own after seeing many trees and many things that are not trees.

The conclusion is that an "ML-based tree recognition system" can be easier to build than a hand-programmed system. The handout condenses this into the most important positioning statement of the section:

ML: an alternative route to build complicated systems

Machine learning is another route to building complicated systems. Note that it is an "alternative" (an addition in this article): for a system whose rules you can write down directly, writing the rules is still the more direct approach, and this point comes up again in the three conditions below.

Four scenarios where it is useful

Page 9 of the handout lists four scenarios for taking this route, each with an example. The explanations from the lecture are in the right-hand column:

Scenario (handout)	Example (handout)	Explanation in the lecture
when human cannot program the system manually	navigating on Mars	Humans know little about Mars, so nobody can write, back on Earth, one or two thousand rules of the form "in this situation do that"; the robot has to observe for itself on site, for example seeing a pit and going around it
when human cannot "define the solution" easily	speech/visual recognition	People recognize sounds and images easily, but looking at a pile of audio signals and writing rules for "what each pronunciation looks like" cannot be done in practice
when needing rapid decisions that humans cannot do	high-frequency trading	Lin describes it as extremely short-term trading: the decision to buy or sell has to be made within ten or twenty seconds, people do not decide that fast, and it is also a field people had not thought about before, so there are no ready-made rules to write
when needing to be user-oriented in a massive scale	consumer-targeted marketing	A service has a huge number of users, and nobody can work out in advance what one user's personality is or how another should be served; the only option is to let the machine learn from their usage records

The bottom of the same page rewrites a proverb: give a computer a fish, you feed it for a day; teach it how to fish, you feed it for a lifetime. Lin's explanation is that writing three hundred lines of rules yourself and having the computer run them is giving it a fish directly, which solves only that one task; teaching it a way to learn is hoping it can later use the same method to solve all kinds of problems.

Three conditions: deciding whether a problem should use machine learning

Page 10 of the handout is titled Key Essence of Machine Learning. It pulls three conditions out of the definition, each matching one phrase in the definition:

1. There exists some underlying pattern to be learned. With a pattern, the performance measure has room to improve.
2. The pattern has no programmable (easy) definition. If you can write it, just write it, and machine learning is not needed.
3. Somehow there is data about the pattern. Machine learning needs inputs to learn from.

The handout states the purpose of these three at the bottom of the page: they help decide whether to use ML. Lin's additions in the lecture for each: on a problem with no pattern at all, no matter how much data you feed in or how long the machine runs, it learns nothing in the end; on a problem whose rules you know how to write, just write them down and be done; and a problem without data is not suitable, because everything in machine learning starts from data. Lin also reminds you that machine learning cannot necessarily be used everywhere, so check a new problem against these three conditions first.

The order of the three checks can be treated as a small procedure (organized by this article; the handout only lists the three conditions):

1. First ask whether there is a pattern. If not, stop: there is nothing to learn.
2. Then ask whether the rules can be written directly as a program. If so, stop: writing the program is cheaper and more reliable.
3. Finally ask whether there is data. If there is none or too little, go collect data first, or admit it cannot be done now.

Only a problem that passes all three is worth discussing which method to use.

Fun Time: which problem is best suited for machine learning

Question (page 11 of the handout): Which of the following is best suited for machine learning?

1. predicting whether the next cry of the baby girl happens at an even-numbered minute or not
2. determining whether a given graph contains a cycle
3. deciding whether to approve credit card to some customer
4. guessing whether the earth will be destroyed by the misuse of nuclear power in the next ten years

Answer: 3. This question removes one of the three conditions from each of the other choices:

Choice	Pattern	No programmable definition	Data	Handout's comment
1 minute of the baby's cry	none	—	—	no pattern
2 cycle in a graph	yes	can be programmed	—	programmable definition
3 approving a credit card	yes: customer behavior	not easily programmable	yes: history of bank operation	all three hold
4 earth destroyed by nuclear power	—	—	none or not enough	arguably no (or not enough) data yet

For choice 1, Lin says in the lecture that, from experience with Lin's own daughter, there is no rule anyone can think of that predicts whether she cries on an odd or an even minute. Choice 2 has a clear rule that is easy to write as a program (an addition in this article: one depth-first search over the graph decides it), so nothing needs to be learned. For choice 4, Lin says the earth has never actually been destroyed and there have not been many nuclear disasters, so people cannot infer it and a machine probably cannot either; the handout's word is "arguably", which leaves this item open to discussion. Choice 3 is a common application of machine learning: the bank has data on past customers and knows whether they went on to use their credit cards well; there should be some formula behind whether to issue a card, but it may be very complicated and we cannot write it down. This example becomes the main example of the whole lecture in the section "Writing the learning problem in symbols".

Where machine learning is already used: six examples, all trading data for skill

(Video 00:00–05:56 covers food, clothing, housing, and transportation, 05:56–10:20 education, 10:20–14:12 the recommender system problem and two competitions, 14:12–17:38 one model for recommender systems, and Fun Time follows.)

Every example in this section follows the same format: what the data is, and what skill is learned. As you read, you can also run each one through the three conditions from the previous section.

Food, clothing, housing, transportation

Page 12 of the handout arranges four examples under "Daily Needs", and the rightmost column of the table is the source the handout cites. In the lecture, Lin says the four items food, clothing, housing, and transportation come from Sun Yat-sen's Principle of People's Livelihood, and the two that follow, education and entertainment, were added by Chiang Kai-shek; together they give the order of the six examples in this section.

Need	Data	Skill	Source cited in the handout
Food	Twitter data (words + location)	tell food poisoning likeliness of restaurant properly	Sadilek et al., 2013
Clothing	sales figures + client surveys	give good fashion recommendations to clients	Abu-Mostafa, 2012
Housing	characteristics of buildings and their energy load	predict energy load of other buildings closely	Tsanas and Xifara, 2012
Transportation	some traffic sign images and meanings	recognize traffic signs accurately	Stallkamp et al., 2012

The lecture adds background for each example:

• Food. People write on Twitter about which restaurant they went to today, whether it was good, and whether they had an upset stomach afterwards. By analyzing these words together with the locations, a machine can tell you how likely you are to get food poisoning at a given restaurant. Before, the only ways to learn about a restaurant's hygiene were to hear it from friends, try it yourself, or look up reviews online.
• Clothing. Abu-Mostafa is a professor at Caltech and Lin's former advisor. Lin says an online fashion company hired Abu-Mostafa as a consultant to build a system that recommends how customers should put outfits together. Lin admits that machine learning people know very little about fashion, but they know how to use the tools of machine learning properly, so they learned from sales figures and client surveys; Lin says the system's ability is already comparable to human fashion experts. One thing can be read out of this example (this article's reading): the people who design the system do not need to be experts in that field.
• Housing. Before building a house you want to know how much energy it will use once built, for example whether the air conditioning or heating will need to run often. Lin says this used to rely on the architect's experience (for example, a west-facing building uses more energy in the afternoon); this study feeds the machine the building characteristics and energy use of houses that already exist, so that it can predict at the design stage, and the architect then revises the design accordingly.
• Transportation. The lecture connects this to driverless cars: the car has to understand signs, watch out for pedestrians, slow down, and stop at red lights. The study the handout cites comes from a competition on using machine learning to raise sign recognition accuracy, and the data is photographed images of signs of all sizes and all meanings.

The handout's closing line on this page is "ML is everywhere".

Education: inferring student strength and question difficulty from answer records

The example on page 13 of the handout is an online math tutoring system.

• Data: students' records on quizzes on the system.
• Skill: predict whether a student can give a correct answer to another quiz question.

The lecture explains why this prediction is useful: the system has to decide which question to give next. One the student is certain to get right is too easy and need not be done again; one the student is certain to get wrong is too hard, and from a teaching-design point of view you do not want to give it now either; so the system needs to know whether the student will answer correctly a question they have not done.

One solution the handout gives starts by assuming a pattern:

$$\text{answer correctly} \approx \llbracket\, \text{recent strength of student} > \text{difficulty of question} \,\rrbracket$$

The double brackets mean "1 if the condition inside holds, 0 if it does not" (how to read this notation is an addition in this article). Lin says the pattern comes from imagining how a human teacher would judge: a question has a difficulty, a student has a level that depends on how well they understand, and the student answers correctly when the level is above the difficulty.

The problem is that nobody tells you the strength or the difficulty. The handout's approach is to give the machine 9 million records from 3,000 students and let it determine automatically (the handout's word is "reverse-engineers") each student's strength at each point in time and each question's difficulty. The lecture compares this to reverse engineering in engineering: you hold only the results and work backwards to the quantities that produced them. This article adds a sense of scale: 9 million records divided by 3,000 students is an average of 3,000 records per student, so there is material to infer each person's strength from.

The handout notes that this is the key part of the world-champion system from National Taiwan University in KDD Cup 2010. Lin says KDD Cup is the most important machine learning and data mining competition in the world, with hundreds of teams from academia and industry each year, competing on whose algorithm improves most on the performance measure the organizers specify, and that Lin was a member of the NTU team that year. "Competing on a specified performance measure" matches the definition from the previous section exactly.

Entertainment: recommender systems

Page 14 of the handout first defines the problem:

• Data: the ratings many users have given to some movies.
• Skill: predict how a user would rate a movie they have not rated yet.

If the predicted rating is high, recommend the movie to that user. The handout lists two competitions to show how hot this problem is:

Competition	Ratings	Users	Items
Netflix, held in 2006	100,480,507	480,189	17,770 movies
Yahoo!, KDD Cup 2011 (movies replaced by songs)	252,800,275	1,000,990	624,961 songs

Netflix's rule was that a 10% improvement over their system earns a prize of 1 million US dollars. The lecture adds that Netflix was at the time the largest online DVD rental company in the United States, and that the 10% is relative to their system at the time; Lin also remarks that, looking back, it was a good deal for the company: besides the publicity, spending 1 million dollars got researchers around the world to help find better methods.

These numbers are worth working out yourself (the two ratios below are additions in this article and are not on the handout). If every user in the Netflix data had rated every movie, there would be $480{,}189 \times 17{,}770 \approx 8.53$ billion ratings; there are actually only about 100 million, which is 1.18%; on average each user rated about 209 movies. The Yahoo! data is even sparser, with the known ratings covering only about 0.04% of all (user, song) combinations. So "predicting the ratings not yet given" means using roughly 1% of the cells, the known ones, to fill in the remaining 99%.

Page 15 of the handout gives one possible model. The figure shows two rows of cells side by side:

• The top row is a string of numbers for the viewer, each cell one preference factor: likes comedy? likes action? prefers blockbusters? ..., likes Tom Cruise?
• The bottom row is a string of numbers for the movie, each cell matching the same factor: comedy content, action content, blockbuster or not, ..., is Tom Cruise in it?
• The two rows are matched cell by cell, and the contributions from each factor are added up to give the predicted rating.

Lin says this imitates the way people themselves decide whether they like a movie: the figure uses the size of a circle for the size of a number, so someone who likes action movies has a large number in the "action" cell; the two strings of numbers go through something like an inner product, multiplied cell by cell and summed, and a high sum means a high rating. (The actor used as the example in the lecture is Julia Roberts, while the handout's figure says Tom Cruise; the examples differ, the meaning is the same.)

The handout writes the model in two lines:

• Pattern: rating ← viewer/movie factors
• Learning: known rating → learned factors → unknown rating prediction

The key is the direction of the second line. All the machine has is ratings; it has nobody's preference numbers and no movie's content numbers. It has to work backwards from the ratings to these two sets of factors, which is the same idea as inferring strength and difficulty in the education example.

Numeric example (made up for this article, not from the slides). Suppose the reverse-engineering is already done, and there are only four factors, in the order (comedy, action, blockbuster, Tom Cruise). One viewer's factors are $(0.1,\ 0.9,\ 0.6,\ 0.8)$. Two movies this viewer has not seen:

• Movie A has factors $(0.0,\ 1.0,\ 0.9,\ 1.0)$, an action blockbuster with Tom Cruise.
• Movie B has factors $(0.9,\ 0.1,\ 0.2,\ 0.0)$, a low-budget comedy.

Multiply cell by cell and sum:

$$\text{A}: \ 0.1 \times 0.0 + 0.9 \times 1.0 + 0.6 \times 0.9 + 0.8 \times 1.0 = 0 + 0.9 + 0.54 + 0.8 = 2.24$$ $$\text{B}: \ 0.1 \times 0.9 + 0.9 \times 0.1 + 0.6 \times 0.2 + 0.8 \times 0.0 = 0.09 + 0.09 + 0.12 + 0 = 0.30$$

A scores far higher than B, so recommend A. What this result means: once every person and every movie has a string of numbers, predicting any cell of the rating table is just one inner product. The 2.24 and 0.30 here can only be compared with each other; a real system still has to map them onto the rating scale. The truly hard part is the step this example skips, namely inferring these numbers from 100 million ratings.

The handout notes that this model is the key part of the system with which the National Taiwan University team became world champion again in KDD Cup 2011. Lin says that year's competition had two tracks and NTU took first place in both.

Fun Time: which field cannot use machine learning

Question (page 16 of the handout): Which of the following field cannot use machine learning?

1. Finance
2. Medicine
3. Law
4. none of the above

Answer: 4. The handout gives one use for each of the first three: finance can predict stock price from data, medicine can predict medicine effect from data, and law can summarize legal documents from data. The lecture explains the law item a little further: court documents are long, and automatically generated summaries make them easier to search and read. All three fields have problems with "a pattern, no writable rules, and data", so none of them is unable to use it. The thing to notice is that the question asks about "fields"; a field being able to use machine learning does not mean every problem in the field is suitable, and each individual problem still has to pass the three conditions.

Writing the learning problem in symbols: f, D, H, A, g

(Video 00:00–01:24 sets up the credit card scenario, 01:24–04:35 the basic notations, 04:35–06:45 the learning flow, 06:45–10:06 the hypothesis set and the learning model, 10:06–10:46 the practical definition, and Fun Time follows.)

The "data → ML → skill" of the previous two sections is still a sketch. This section replaces each box with a symbol, and it is the part of the lecture you most need to remember.

Main example: should the bank approve a credit card

Page 17 of the handout gives one applicant's information:

Field	Value
age	23 years
gender	female
annual salary	NTD 1,000,000
year in residence	1 year
year in job	0.5 year
current debt	200,000

The bank wants to decide from this information on the application form whether to issue a card. The handout writes what is to be learned as a question: "approve credit card good for bank?" The way the lecture puts it, the thing to learn is how the bank should issue cards so that its profit or its service is best.

Basic notations

Page 18 of the handout defines five symbols. The last column is what each means in the credit card example:

Symbol	Name	In the credit card example
$\mathbf{x} \in \mathcal{X}$	input	customer application
$y \in \mathcal{Y}$	output	good or bad after approving the credit card
$f: \mathcal{X} \to \mathcal{Y}$	target function, the unknown pattern to be learned	ideal credit approval formula
$\mathcal{D} = \{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \dots, (\mathbf{x}_N, y_N)\}$	data, also called training examples	historical records in the bank
$g: \mathcal{X} \to \mathcal{Y}$	hypothesis, the skill with hopefully good performance	the "learned" formula to be used

A few things that are easy to mix up:

• The lowercase $\mathbf{x}$ is one applicant, and the calligraphic $\mathcal{X}$ is the set of all possible applicants; likewise for $y$ and $\mathcal{Y}$. In this example $\mathcal{Y}$ has only two elements, good and bad.
• $f$ and $g$ have the same type: both are functions from $\mathcal{X}$ to $\mathcal{Y}$. The difference is that $f$ is what we want but do not know, and $g$ is what the machine computes and hands to us. Lin stresses again and again that $f$ is unknown: if we knew it, we would just write it as a program and there would be nothing to learn. This is exactly the symbolic version of the second condition, "no programmable (easy) definition".
• Each entry in $\mathcal{D}$ is a pair: a past customer's application $\mathbf{x}_n$, plus the outcome $y_n$ after the card was issued to them. $N$ is the number of entries, and the number Lin gives in the lecture is that the bank may have collected 1,000 of them.
• Once the bank has $g$, it uses it to judge future customers. So whether $g$ is good depends on how it does on people it has not seen, and that is only handled formally in Lecture 4.

With the symbols, the sketch becomes: $\{(\mathbf{x}_n, y_n)\}$ from $f$ → ML → $g$.

The learning flow

Page 19 of the handout draws it as a flow chart. Following the arrows, the chart contains:

1. At the upper left is the unknown target function $f: \mathcal{X} \to \mathcal{Y}$ (the ideal credit approval formula).
2. $f$ generates the training examples $\mathcal{D}: (\mathbf{x}_1, y_1), \dots, (\mathbf{x}_N, y_N)$ (historical records in the bank).
3. The data goes to the learning algorithm $\mathcal{A}$.
4. $\mathcal{A}$ outputs the final hypothesis $g \approx f$ (the "learned" formula to be used).

Step 2 has a detail that the lecture makes very clear: how $f$ generates the data is a process we do not know; we only assume that things happen this way. What we really have in hand is the second half, which starts from "we have data".

Under the chart the handout lists two reminders:

• The target $f$ is unknown, i.e. there is no programmable definition.
• The hypothesis $g$ is hopefully close to $f$ but possibly different from $f$; perfection is "impossible" when $f$ is unknown.

The lecture turns "better performance" into symbols: the more $g$ resembles $f$, the better. Because $f$ is unknown, $g$ will usually not be identical to it; if it really is identical, that can only be called luck.

The hypothesis set, and what a learning model is

What does $g$ actually look like? Page 20 of the handout gives three possible approval formulas:

• $h_1$: approve if annual salary > NTD 800,000
• $h_2$: approve if debt > NTD 100,000 (the handout marks this "really?")
• $h_3$: approve if year in job ≤ 2 (also marked "really?")

$h_2$ and $h_3$ look absurd at first glance. In the lecture, Lin makes up a reason for each: someone with a lot of debt might use the card to roll the debt over and pay the bank interest; a young person who has only worked a few years spends more freely and may be exactly the customer group the bank wants. Lin also says "I don't know" right away; the point is only that these are all possible formulas, with no claim that the machine will pick them.

Collect all the candidate $h$ together and you have the hypothesis set $\mathcal{H} = \{h_k\}$; the handout assumes $g \in \mathcal{H}$. The handout says two things about $\mathcal{H}$:

• It can contain good or bad hypotheses.
• It is up to $\mathcal{A}$ to pick the "best" one as $g$.

So the flow chart needs one more box: $\mathcal{H}$ also points to $\mathcal{A}$. As Lin puts it, the algorithm really has two inputs, one being the data and the other being the hypotheses you allow it to choose from. Lin also leaves one remark hanging: whether the one the algorithm "thinks" is best really is the best is something to be sorted out later. That remark is the subject of Lectures 4 to 7.

At the bottom of this page the handout gives a definition:

learning model = $\mathcal{A}$ and $\mathcal{H}$

A learning model is the algorithm plus the hypothesis set it uses. Why talk about the two separately? The lecture only says that we will see later that the hypothesis set has a special role in the design and analysis of algorithms, so it is pulled out on its own. From here on, whenever a lecture introduces a new method, you can ask the same two questions: what is its $\mathcal{H}$, and how does its $\mathcal{A}$ pick from it.

Numeric example: walking through the five components

What follows is an example made up for this article. Neither the data nor the algorithm is from the slides; only $h_1$, $h_2$, $h_3$ and the 23-year-old applicant come from the handout. The aim is to tie each symbol to something you can see.

Input and output. Record only three numbers for each customer: $\mathbf{x} = (\text{annual salary}, \text{debt}, \text{year in job})$, with money amounts in units of NTD 10,000. $y = +1$ means the customer turned out good after the card was issued, and $y = -1$ means bad.

Target function. $f$ is "the ideal credit approval formula". We do not know it, and nothing below uses it.

Data. The bank has $N = 8$ historical records:

$n$	Annual salary (NTD 10,000)	Debt (NTD 10,000)	Year in job	$y_n$
1	120	5	6	$+1$
2	95	30	3	$+1$
3	60	0	10	$-1$
4	40	25	1	$-1$
5	150	0	1.5	$+1$
6	85	15	0.5	$-1$
7	70	12	4	$-1$
8	90	0	8	$+1$

Hypothesis set. $\mathcal{H} = \{h_1, h_2, h_3\}$, the three formulas from the handout. Each $h$ outputs $+1$ when it says "approve" and $-1$ otherwise.

Algorithm. Use the most direct kind of $\mathcal{A}$ here: take every hypothesis in $\mathcal{H}$ to $\mathcal{D}$, count the records on which it disagrees with $y_n$, and choose the one with the fewest errors.

Computing them one by one:

Hypothesis	Outputs on the 8 records (for $n = 1$ to 8)	Which records are wrong	Errors
$h_1$: annual salary > 80	$+,+,-,-,+,+,-,+$	record 6 (salary 85 is approved, but the customer is actually bad)	1
$h_2$: debt > 10	$-,+,-,+,-,+,+,-$	records 1, 4, 5, 6, 7, 8	6
$h_3$: year in job ≤ 2	$-,-,-,+,+,+,-,-$	records 1, 2, 4, 6, 8	5

Take record 1 under $h_2$: a debt of 5 does not exceed 10, so $h_2$ outputs $-1$, but $y_1 = +1$, so it is wrong. The other cells are compared the same way.

Final hypothesis. $\mathcal{A}$ picks the one with the fewest errors, so $g = h_1$, which gets 1 of the 8 records in $\mathcal{D}$ wrong.

Putting it to use. The applicant on page 17 of the handout has $\mathbf{x} = (100, 20, 0.5)$. An annual salary of 100 exceeds 80, so $g(\mathbf{x}) = +1$: approve. Incidentally, all three hypotheses happen to say approve for her (a debt of 20 exceeds 10, and 0.5 year in the job does not exceed 2), so this one applicant alone cannot tell the three hypotheses apart; it takes the 8 records in $\mathcal{D}$ to do that.

Three things can be seen from this example:

1. $g$ is not necessarily all correct even on the data. $h_1$ still gets record 6 wrong. $\mathcal{A}$ can only pick from the options $\mathcal{H}$ offers, and when all three options are imperfect, so is the one it picks.
2. Change $\mathcal{H}$, and the same $\mathcal{A}$ gives a different $g$. If $\mathcal{H}$ had one more member, $h_4$: approve if annual salary is above 87, it would make no errors at all on these 8 records (it approves records 1, 2, 5, 8, all of them $+1$; the other four are all $-1$), and $\mathcal{A}$ would choose $h_4$ instead. This gives a feel for why the handout calls $\mathcal{A}$ and $\mathcal{H}$ together the learning model (this is this article's reading; the handout gives no reason): the algorithm alone does not tell you what will be learned in the end.
3. All correct on $\mathcal{D}$ does not mean $g = f$. $h_4$ makes no errors on the 8 records, but we never saw $f$ at any point, so we cannot know whether its decisions for the 9th and 10th customers agree with $f$. This gap is the problem Lecture 4 deals with.

The practical definition of machine learning

Page 21 of the handout condenses the full chart ($f$ generates $\mathcal{D}$, $\mathcal{D}$ and $\mathcal{H}$ go into $\mathcal{A}$, $\mathcal{A}$ outputs $g \approx f$) into one sentence, under the title Practical Definition of Machine Learning:

machine learning: use data to compute hypothesis $g$ that approximates target $f$

Use data to compute a hypothesis $g$ that is close to the target $f$. Compare it with the earlier definition on page 7 of the handout: "experience computed from data" is unchanged, and "improving some performance measure" has become "$g$ approximates $f$". Whenever the rest of the course says machine learning, it means this version.

Fun Time: placing four sets into a song recommendation learning problem

Question (page 22 of the handout): How to use the four sets below to form a learning problem for song recommendation?

• $S_1 = [0, 100]$
• $S_2$ = all possible (userid, songid) pairs
• $S_3$ = all formula that "multiplies" user factors & song factors, indexed by all possible combinations of such factors
• $S_4$ = 1,000,000 pairs of ((userid, songid), rating)

Choices:

1. $S_1 = \mathcal{X},\ S_2 = \mathcal{Y},\ S_3 = \mathcal{H},\ S_4 = \mathcal{D}$
2. $S_1 = \mathcal{Y},\ S_2 = \mathcal{X},\ S_3 = \mathcal{H},\ S_4 = \mathcal{D}$
3. $S_1 = \mathcal{D},\ S_2 = \mathcal{H},\ S_3 = \mathcal{Y},\ S_4 = \mathcal{X}$
4. $S_1 = \mathcal{X},\ S_2 = \mathcal{D},\ S_3 = \mathcal{Y},\ S_4 = \mathcal{H}$

Answer: 2. The handout gives only a one-line diagram: $S_4$ goes through "$\mathcal{A}$ on $S_3$" and yields $g: S_2 \to S_1$. The reasoning can be filled in like this (an addition in this article):

• What is to be predicted is "what rating a user would give a song". The input of the problem is who listens to which song, so $\mathcal{X} = S_2$; the output is a rating, so $\mathcal{Y} = S_1$, an interval from 0 to 100.
• Every entry of $S_4$ is "an input paired with a known output", exactly the shape of $(\mathbf{x}_n, y_n)$, and it has a definite count $N = 1{,}000{,}000$, so it is $\mathcal{D}$.
• $S_3$ is a collection of formulas: each setting of the factors determines one formula, and each formula maps a (user, song) pair to a rating, so it is the set of candidate functions $\mathcal{H}$. The recommender model of the previous section is exactly this; "inferring the factors" amounts to choosing one $h$ in $\mathcal{H}$.

Where the other choices go wrong: choice 1 swaps input and output, which would mean predicting the pair from the rating; choices 3 and 4 match $\mathcal{D}$ or $\mathcal{H}$ to a set of the wrong type. For example, choice 3 says $\mathcal{D} = [0, 100]$, but data must be input-output pairs, and an interval is not. The way to check this kind of question is to look at types: the elements of $\mathcal{D}$ are $(\mathbf{x}, y)$ pairs, and the elements of $\mathcal{H}$ are functions.

How machine learning differs from data mining, artificial intelligence, and statistics

(Video 00:00–03:53 covers data mining, 03:53–05:47 artificial intelligence, 05:47–08:02 statistics, 08:02–08:47 Fun Time, and the summary of the whole lecture follows.)

With the practical definition in hand, it can serve as a ruler for measuring three fields that are often lumped together. Pages 23 to 25 of the handout all use the same layout: the definition of machine learning on the left, and the definition of another field on the right.

Field	One-sentence definition in the handout	Relation to machine learning (handout)
Machine Learning	use data to compute hypothesis $g$ that approximates target $f$	—
Data Mining	use (huge) data to find property that is interesting	difficult to distinguish in reality
Artificial Intelligence	compute something that shows intelligent behavior	ML is one possible route to realize AI
Statistics	use data to make inference about an unknown process	statistics offers many useful tools for ML

Data mining

The example in the lecture is a supermarket operator who has a pile of sales data and wants to know whether customers who buy one thing will also want another, that is, which products are associated. That kind of association is an "interesting property".

The handout distinguishes three cases:

• If the "interesting property" is the same as the "hypothesis that approximates the target", then data mining equals machine learning. The handout notes that this is usually what KDD Cup does. The lecture resolves a question left over from the applications section: KDD Cup is a competition of the data mining community, so why call it the most important machine learning competition? Because its tasks usually ask you to design an algorithm that raises some performance measure, that is, to approximate some ideal $f$.
• If the two are only related, then data mining can help machine learning, and vice versa. The handout adds: often, but not always.
• Traditional data mining also focuses on efficient computation in large databases. Lin says this is because data mining is a field that grew out of the database side.

On the first case Lin says "that is a big if": some problems in data mining do not care about prediction and only want to find things that help people analyze further. Lin also says that Lin's own research field is machine learning, but seen from a certain angle it is data mining too; finding a researcher today who does only one of the two is almost impossible. The handout's conclusion is that it is difficult to distinguish the two in reality.

Artificial intelligence

The intelligent behaviors given as examples in the lecture are a computer that can play chess or drive a car, and "being able to predict" is also a way of appearing smart. The handout's reasoning is that $g \approx f$ is itself something that shows intelligent behavior, so machine learning can realize artificial intelligence, but it is only one of the routes.

The handout contrasts the two routes using chess:

• Traditional AI: game tree. The lecture's explanation is that you expand the pros and cons of every move downwards like a tree diagram, and design an algorithm for the machine to analyze this tree.
• ML for AI: "learning from board data". Lin says you can show the machine how many players play, or let the machine play by itself, record which moves win and which lose, and then work out how to play from this data.

Statistics

The statistics example in the lecture is tossing a coin: you do not know the probability of heads, so you toss it 1,000 times and estimate it. The handout lines machine learning up against this: $g$ is an inference outcome and $f$ is something unknown, so statistics can be used to achieve machine learning.

The difference is in orientation. The handout says traditional statistics also focuses on provable results with math assumptions and cares less about computation. The way Lin puts it, statistics starts from mathematics and is used to writing down assumptions first and then obtaining inferences that can be proved, while machine learning starts from computer science and puts more weight on how to compute the result. Lin also announces that many of the tools used later actually appeared in statistics long ago; this course borrows them and looks at them again from the machine learning point of view. Hoeffding's inequality in Lecture 4 is the first example.

These three relations point in different directions and are worth remembering separately (organized by this article): machine learning is one way to realize artificial intelligence; statistics is one source of tools for achieving machine learning; and data mining and machine learning are two fields that overlap heavily but differ in focus.

Fun Time: which claim is not totally true

Question (page 26 of the handout): Which of the following claim is not totally true?

1. machine learning is a route to realize artificial intelligence
2. machine learning, data mining and statistics all need data
3. data mining is just another name for machine learning
4. statistics can be used for data mining

Answer: 3. The handout's explanation is that data mining and machine learning do share a huge overlap, but they are arguably not equivalent because of the difference of focus. Choice 1 is the conclusion of page 24 of the handout. Choice 2 can be seen from the three definitions, which involve data in each case. Choice 4 is not written directly in the handout, but it can be deduced (an addition in this article): statistics is a set of tools for making inference from data, and data mining finds properties from data, so the tools of the former can naturally be used for the latter. Choice 3 goes wrong at the word "just": the problems in data mining that do not aim at prediction, and its focus on computational efficiency in large databases, are both outside the definition of machine learning.

Summary of this lecture

Page 27 of the handout sums up each of the five subsections in one line:

Subsection	The handout's one line
Course Introduction	foundation oriented and story-like
What is Machine Learning	use data to approximate target
Applications of Machine Learning	almost everywhere
Components of Machine Learning	$\mathcal{A}$ takes $\mathcal{D}$ and $\mathcal{H}$ to get $g$
Machine Learning and Other Fields	related to DM, AI and Stats

The same page announces the next lecture: a simple and yet useful learning model, that is, a concrete $\mathcal{H}$ and $\mathcal{A}$. In this lecture's credit card example, $\mathcal{H}$ has only three casually written rules, and nothing was said about how $\mathcal{A}$ picks; the next lecture replaces both with the real thing.

Self-check

1. Use the three conditions to judge whether each of the following four problems suits machine learning, and for the unsuitable ones say which condition they fail: (a) deciding whether a positive integer is prime; (b) predicting the next roll of a fair die; (c) predicting the sale price of a house from its floor area, age, and location, given one hundred thousand sale records; (d) predicting the first-year sales of a product of a completely new type, with nothing similar on the market.

Answer: (a) There is a pattern, but the definition can be written as a program (trial division is enough), so it fails the second condition. (b) Each roll of a fair die is independent and every face has the same probability, so there is no pattern to learn, and it fails the first condition. (c) All three hold: the price is related to these features, the relation cannot be written as a simple formula, and there are records. (d) There may be a pattern and no formula can be written, but there is no historical data for this kind of product, so it fails the third condition. An answer counts as correct only if it says which condition each one fails.

2. Spam filtering: write out X, Y, f, D, g for this problem, and give two hypotheses that could be placed in H.

Criteria: $\mathcal{X}$ is all possible emails, and $\mathcal{Y}$ is {spam, not spam}; $f$ is "the ideal rule for judging", unknown; $\mathcal{D}$ is a batch of emails that someone has already labeled as spam or not, each entry a pair (email, label); $g$ is the learned rule used to filter new emails. Examples of hypotheses: "call it spam if the body contains 'free'" and "call it spam if the sender is not in the address book". In the answer, $\mathcal{D}$ must be input-output pairs, and the things in $\mathcal{H}$ must be functions that map an email to a label; writing $f$ as some known rule is wrong.

3. Keep the 8 credit approval records from the main text. Change the hypothesis to "approve if annual salary is above 100". How many records in D does it get wrong, and which ones? Would the algorithm pick it or h₁?

Answer: Only record 1 (120) and record 5 (150) have an annual salary above 100, both are $+1$, and both are judged correctly. The other six are all judged $-1$, and among them record 2 (95) and record 8 (90) are actually $+1$, so they are wrong. That is 2 errors in total, more than the 1 error of $h_1$, so the algorithm still picks $h_1$.

4. In the main text, h₄ is correct on all 8 records. Why can we not conclude from this that g = f?

Criteria: the answer must make two points. First, $f$ is a function defined on all of $\mathcal{X}$, and $\mathcal{D}$ covers only 8 of its points; $g$ agreeing with $f$ on these 8 points does not mean they agree elsewhere. Second, $f$ is unknown, so we have no way to compare $g$ with $f$ directly; this is why page 19 of the handout writes only $g \approx f$ and says perfection is "impossible" when $f$ is unknown.

5. Which field is each of the following three tasks typical of, and how does it differ from the definition of machine learning? (a) A chess program that relies only on expanding a game tree; (b) finding combinations of products often bought together from supermarket transaction records, for the store manager's reference; (c) tossing a coin 1,000 times and estimating the probability of heads.

Criteria: (a) is artificial intelligence, but it does not use data to compute $g$, so it is the route that does not go through machine learning. (b) is data mining, and what it looks for is an interesting property; it is not trying to approximate a target function $f$ in order to predict, so it does not directly equal machine learning. (c) is statistical inference, where the unknown thing is a probability; it fits "use data to make inference about something unknown", and when carried over to machine learning, the unknown thing becomes a function $f$ and the inference outcome becomes $g$.

Exercises and corresponding reading

Where this sits in Fall 2026. The Fall 2026 course page puts this lecture's five videos on the must-watch-before-class list for W2, and the matching textbook sections are 1.0, 1.1.1, and 1.2.4 of Learning from Data (LFD). The schedule on the course page was checked on 2026-09-30.

What the Fall 2026 extended slides (01e) add. These slides switch to more recent applications than the MOOC version, including medical dialogue diagnosis, 4G LTE communication configuration, PCB defect inspection, face recognition, and typhoon intensity estimation (the TCIR dataset), and they compare machine learning to "the tool that cooks the ingredient, (big) data, into the dish, AI". They end by using AlphaGo to show that good AI needs both machine learning (deep learning) and non-machine-learning techniques (Monte Carlo tree search), which can be read alongside the last section of this lecture, "ML is one possible route to realize AI".

Homework. The first homework of both semesters is public on the course pages. There are no official solutions, and grading is for enrolled students only.

• Q1 of Fall 2024 HW1 (released 2024-09-09, due 10-07) asks which task is best suited for machine learning. It practices this lecture's three conditions directly, and you can check each choice item by item the way the Fun Time table does: pattern, whether it can be programmed, whether there is data. Q5–6 have you first ask a ChatGPT-like agent "where can active learning be used" and "can ML predict earthquakes", and then, from the standpoint of "the boss", critique its answer in 10 to 20 English sentences; for the earthquake question, the three conditions can serve as the skeleton of the critique (this is this article's suggestion; the problem does not ask for it).
• Q1 of Fall 2026 hw1 (released 2026-09-23, due 10-21) is likewise about which task is best suited for machine learning.

The remaining problems in these two homework sets belong to Lectures 2 to 4; the guide to the full sets is in Foundations Homework.

Practice you can do on your own. Pick three problems from your work or daily life and do two things for each: use the three conditions to judge whether it should use machine learning; and for those that should, write out its $\mathcal{X}$, $\mathcal{Y}$, $\mathcal{D}$, and think of two or three rules that could go into $\mathcal{H}$. When you cannot write $\mathcal{D}$ as input-output pairs, it usually means the problem is not yet clearly defined.

Further reading. Caltech Learning from Data is the course in English that Abu-Mostafa teaches from the same textbook, and its Lecture 1, The Learning Problem, corresponds to this lecture.

Next lecture. Foundations Lecture 2: Perceptrons and PLA returns to the credit card problem and gives the first concrete $\mathcal{H}$ (the perceptron) and $\mathcal{A}$ (PLA).

Course video sources

Original videos: Course Introduction, What is Machine Learning, Applications of Machine Learning, Components of Machine Learning, Machine Learning and Other Fields

• Machine Learning Foundations YouTube playlist (in Mandarin)
• Official course and recordings portal

Checked: 2026-10-13. The video IDs, titles, and lengths were taken from the official playlist that day; there is no caption track on YouTube, and what this article reports from the lecture comes from transcripts made for this article.

Update Log

• 2026-10-10: Marked the video status and checked the recording sources and how they were obtained.
• 2026-10-10: Re-checked the video status. The embedded videos match the lecture numbering of the official playlist.
• 2026-10-13: Previously combined with Lectures 2 and 3 in one article; changed to one lecture per article and rewritten from the handout and the video transcripts.

References

• Foundations Lecture 1 handout, 01_handout.pdf: the main basis of this article; the definitions, examples, flow charts, and five Fun Time questions of the five subsections all come from this handout.
• Machine Learning Foundations YouTube playlist (in Mandarin): the IDs and titles of the five videos; what the text reports as said "in the lecture" is paraphrased from machine transcripts of these five videos.
• Hsuan-Tien Lin > MOOCs: the official portal for handouts and recordings.
• Machine Learning, Fall 2026 course page: the W2 must-watch-before-class list and the LFD sections.
• Lecture 1 extended slides (01e_handout.pdf): the applications added in Fall 2026 and the AlphaGo discussion.
• Fall 2024 Homework 1 (hw1_red.pdf): the content of Q1 and Q5–6.
• Fall 2026 Homework 1 (hw1.pdf): the content of Q1.
• Learning from Data textbook site: the source of the LFD sections.
• Caltech Learning from Data: further reading, the course in English from the same textbook.
• Reading NTU Hsuan-Tien Lin Machine Learning Foundations & Techniques: Course Overview: where this lecture sits in the whole course and the reading routes.