Reading Hsuan-Tien Lin's ML Foundations: The Learning Problem, PLA, and Types of Learning

🌏 中文版

This is post 1 in the Reading NTU Hsuan-Tien Lin Machine Learning Foundations & Techniques series. It covers Lectures 1–3 of Machine Learning Foundations, the first three lectures under the first big question, "When Can Machines Learn?"

These three lectures answer two things: what components make up a machine learning problem, and what the simplest learning algorithm looks like. By the end you should be able to write PLA yourself and say which type of learning a problem belongs to. Whether PLA's line is also right on data it has never seen is left for post 2.

Sources: MOOC handouts 01, 02, and 03; the W2–W3 watch lists on the Fall 2026 course page and extended slides 01e, 02e, and 03e; Fall 2024 HW1 and Fall 2026 hw1. All checked on 2026-09-30.

Materials for this post

That is 13 videos. Fall 2026 assigns L1, L2, and the first L3 video before W2, and the last three L3 videos before W3.

Lecture 1: What machine learning is

From learning to machine learning

L1's definition is plain. Learning means acquiring a skill from experience accumulated through observation. Machine learning computes that experience from data, and "skill" means improving some performance measure, such as prediction accuracy. The slide puts it this way:

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

It then lists when ML makes sense: when humans cannot program the system by hand (navigating on Mars), when the solution is hard to define (speech and image recognition), when decisions must be faster than humans can make them (high-frequency trading), and when a system must serve many users individually (targeted marketing).

When to use ML: three conditions

The slide titled "Key Essence of Machine Learning" is meant to help you decide whether a problem calls for ML:

1. Some underlying pattern exists, so the performance measure can improve.
2. The pattern has no easy programmable definition, so ML is needed.
3. There is data about the pattern, so ML has something to learn from.

The Fun Time right after it makes a good self-check. Is the baby's next cry on an even minute? (No pattern.) Does a graph contain a cycle? (Programmable.) Should a customer get a credit card? (All three conditions hold.) Will Earth be destroyed by nuclear misuse in the next ten years? (Not enough data.) The answer is the credit card.

Five components: f, D, A, H, g

The most important figure in L1 is the learning flow for credit card approval:

Two points. First, f is unknown, so g can only hope to be close to f; being identical is not something anyone can guarantee. Second, the slides call A and H together the learning model ("learning model = A and H"). Nearly all of the next 16 lectures either swap H, swap A, or ask whether learning still works after the swap.

L1's practical definition fits in one line: use data to compute a hypothesis g that approximates the target f.

ML and other fields

The last section compares ML with data mining, AI, and statistics. Data mining "uses (huge) data to find interesting properties," and in practice it is hard to tell apart from ML. ML is one route to AI. Statistics "uses data to make inference" and gives ML many tools, though traditional statistics cares more about provable mathematical results.

Fall 2026 addition (01e): the extended slides swap in newer applications: dialogue-based medical diagnosis, 4G LTE configuration, PCB defect detection, face recognition, and tropical cyclone intensity estimation (the TCIR dataset). ML is compared to the cooking tools that turn (big) data, the ingredient, into AI, the dish. The deck closes with AlphaGo to show that good AI needs both ML (deep learning) and non-ML techniques (Monte Carlo tree search).

Lecture 2: The perceptron and PLA

Hypothesis set: the perceptron

L2 goes back to credit cards and picks the simplest possible H. Each applicant's features x = (x₁,…,x_d) produce a weighted score, and the card is approved if the score clears a threshold:

• h(x) = sign(Σᵢ wᵢxᵢ − threshold)
• Treat the threshold as dimension 0: set x₀ = +1 and w₀ = −threshold, and it becomes h(x) = sign(wᵀx)

This h is historically called the perceptron. In two dimensions each w is a line, +1 on one side and −1 on the other. Hence the slide's conclusion: perceptrons are linear binary classifiers.

The algorithm: PLA

H contains infinitely many lines. How do you choose one? The slides' idea: start from any line and fix it whenever it is wrong.

Start from w₀ (e.g. 0). For t = 0, 1, …
  1. Find an example (x_n(t), y_n(t)) that w_t gets wrong: sign(w_tᵀ x_n(t)) ≠ y_n(t)
  2. Correct it: w_{t+1} ← w_t + y_n(t) · x_n(t)
Stop when there are no mistakes; return the last w (called w_PLA) as g

Why does this count as a correction? Multiply the update by y_n x_n and you get y_n w_{t+1}ᵀx_n ≥ y_n w_tᵀx_n: the score moves toward the right side. In practice people often use cyclic PLA, sweeping the data in a fixed or pre-shuffled order and stopping after a full pass with no mistakes. The slides then show a "Seeing is Believing" sequence where PLA corrects itself 9 times on 2D data before halting.

The guarantee: on separable data, PLA halts

When PLA halts it has no mistakes on D. So halting requires some w that classifies everything correctly; such data is called linearly separable. Conversely, if the data is linearly separable, does PLA always halt?

The slides prove it with two facts. Let w_f be a perfect line:

1. w_t becomes more aligned with w_f: every update increases w_fᵀw_t by at least min_n y_n w_fᵀx_n > 0.
2. w_t does not grow too fast: updates only happen on mistakes, and a mistake means y_n w_tᵀx_n ≤ 0, so ‖w_t‖² grows by at most R² = max_n ‖x_n‖² per update.

The slides list two limits of this guarantee. It assumes linear separability in order to halt. And ρ depends on the unknown w_f, so in practice you don't know how long PLA will run.

Non-separable data: pocket

With noisy data, a perfect line may not exist. Asking for the line with the fewest mistakes sounds reasonable, but the slides point out that this problem is NP-hard.

The compromise is the pocket algorithm. Run PLA as usual, but keep the weights with the fewest mistakes so far, ŵ, in your pocket. After each update, if the new w_{t+1} makes fewer mistakes than ŵ, swap it in. After enough iterations, return ŵ. The cost is counting mistakes on all of D every round, so on separable data pocket is slower than PLA; both return the same weights, with no mistakes.

Fall 2026 addition (02e): the extended slides add four things. First, what to do with sign(0): starting from w₀ = 0 the first step always hits sign(0), and the slides list four conventions (−1, +1, 0, random), noting the choice matters little as long as w₁ usually becomes nonzero. Second, the role of x₀: every update changes w_{t,0} by y_n(t). Third, the full "Magic Chain" derivation above. Fourth, the pocket pattern of "generate candidates, keep the better one" is compared to how modern generative AI is aligned, citing a paper by Lu, Lin, and Wang at the ICML 2026 Workshop on Generative and Agentic AI for Biology.

Lecture 3: Types of learning

L3 classifies learning problems along four axes. Each axis has a "core" option, which is what Foundations mainly handles (bold below):

The slides boil the core tools down to three lines: binary classification and regression on the output axis, supervised on the label axis, batch on the protocol axis. The next 13 lectures of Foundations focus on "batch, supervised binary classification or regression on concrete features." Raw and abstract features need feature transforms, by humans or machines; that thread returns in Foundations L12 and the second half of Techniques.

Fall 2026 addition (03e): the extended slides add recent examples on every axis. The output axis gains multilabel classification (which fruits are in this picture), binary relevance, which splits it into several yes/no questions, and image generation (style transfer, denoising, super-resolution). The label axis gains self-supervised learning (jigsaw puzzles) and weakly supervised learning with complementary labels, which say which class an example is not. The reinforcement learning examples become AlphaGo and GPT-3. The protocol axis adds the practical pattern of online learning plus daily batch retraining, and NTU CLLab's active learning tool libact.

Practice: Fall 2024 HW1 and Fall 2026 hw1

Both sets are public on the hw1/ subpage of each course page. There are no official solutions, and grading (Gradescope) is for enrolled students only.

Fall 2024 HW1 (released 09/09, due 10/07, 200 points plus 20 bonus):

• Q1: which task is best suited for ML, a direct drill of L1's three conditions.
• Q3–4, Q7–8: how rescaling the data or changing x₀ affects PLA's bound and behavior (the problems cite the convergence-bound page of Lecture 2).
• Q5–6: ask a ChatGPT-like agent "what is a possible application of active learning?" and "can machine learning be used to predict earthquakes?", then argue in 10–20 English sentences, as the agent's "boss," whether you agree.
• Q9: a derivation about using a perceptron to detect hateful articles.
• Q10–12: run randomized PLA 1000 times on the first 200 lines of LIBSVM's rcv1_train.binary, plot a histogram of update counts and how ‖w_t‖ evolves, then compare a variant that keeps correcting the same example until it is right. Q13 is the bonus.

Fall 2026 hw1 (released 09/23, red-corrected 09/25, due 10/21, 16 problems, 240 points):

• Q1: which task is best suited for ML.
• Q2–4: the minimum number of extra updates that guarantees a mistake is fixed, how normalizing inputs changes the bound, and how multiclass PLA with K = 2 relates to binary PLA.
• Q5: what kind of learning problem predicting Taiwan's rain map is, drilling L3's four axes.
• Q6–10 are L4 feasibility problems, covered in post 2.
• Q11–16 (programming): run randomized PLA 1000 times on hw1_train.dat (N = 256, x ∈ ℝ¹²), measure the share of runs with E_in = 0 and the medians of update counts and ‖w_PLA‖, then see how update counts change when x is halved or x₀ is set to 0.5 or 0.

Without official solutions, you can check programming problems yourself. Run scikit-learn's Perceptron on the same data and see whether its E_in also reaches 0. Or generate a small dataset you know is linearly separable and check that your update count never exceeds R²/ρ².

What to do tonight

1. Watch the Perceptron Learning Algorithm video, then write PLA in under 20 lines of Python without looking at the slides.
2. Generate 50 linearly separable points in 2D, run your PLA, plot the line after each update, and compare with the slides' "Seeing is Believing" pages.
3. Take three problems from your own work, label each along L3's four axes, and use L1's three conditions to decide whether ML fits.

Further reading

• Stanford CS229 guide: another take on perceptrons and linear classification.
• Caltech Learning from Data: Abu-Mostafa's English course on the same textbook; its Lecture 1, "The Learning Problem," matches the start of this post.

Series navigation: Overview | Next: Is Learning Feasible? Hoeffding and "Outside the Data"

References

• Hsuan-Tien Lin > MOOCs — section titles and slides for Lectures 1–3
• Lecture 1: The Learning Problem (01_handout.pdf)
• Lecture 2: Learning to Answer Yes/No (02_handout.pdf)
• Lecture 3: Types of Learning (03_handout.pdf)
• Machine Learning Foundations YouTube playlist (in Mandarin)
• Machine Learning, Fall 2026 course page — W2–W3 watch lists and LFD sections
• Lecture 1 extended slides (01e), Lecture 2 (02e), Lecture 3 (03e)
• Fall 2026 Homework 1 (hw1.pdf), hw1_train.dat
• Fall 2024 Homework 1 (hw1_red.pdf)
• LIBSVM Data: rcv1.binary
• libact: Pool-based Active Learning in Python
• Learning from Data textbook site