學習的種類：依輸出、標籤、資料取得方式與輸入來分

TL;DR這堂課把第 1 堂的學習流程圖沿四個方向各換一次：輸出空間 Y（二元分類、多類別分類、迴歸、結構化學習）、標籤 yₙ（監督式、非監督式、半監督式、強化學習）、資料交給演算法的方式（batch、online、active）、輸入空間 X（具體、原始、抽象特徵）。四個方向各有一個核心選項，合起來是基石之後的主場：批次、監督式、具體特徵的二元分類與迴歸。

🌏 English version

影片狀態：已附影片。 這篇依官方 MOOC 講義 03_handout.pdf 與這堂四支官方影片的機器轉錄逐字稿寫成，術語與記號以講義為準；逐字稿未經人工校對。每一節開頭附該節的官方影片與大致的時間區段。文中的頁碼指投影片右下角的編號（0/29 到 29/29），寫「課堂上」的地方是轉述影片裡的說法。

這是台大林軒田機器學習基石與技法導讀裡的基石第 3 堂。講義第 1 頁的 Roadmap 把基石分成四個問題，這堂還在第一個「When Can Machines Learn?」底下。上一堂基石第 2 堂：感知器與 PLA在 Roadmap 上只留一行：PLA 拿線性可分的資料 $\mathcal{D}$ 與感知器 $\mathcal{H}$ ，得到假說 $g$ 。那是一種很特定的學習問題：輸出只有是與否、每筆資料都附答案、資料一次給完、輸入是整理好的幾個數字。這堂把這四件事一件一件鬆開，看流程圖的每個位置還能換成什麼。

Roadmap 上列的四節，就是四個可以換的位置：

節	換掉的是流程圖的哪裡	講義的寫法
Learning with Different Output Space	輸出的集合	$\mathcal{Y}$
Learning with Different Data Label	每筆資料附的答案	$y_n$
Learning with Different Protocol	目標函數的資訊怎麼變成資料、交到演算法手上	$f \Rightarrow (\mathbf{x}_n, y_n)$
Learning with Different Input Space	輸入的集合	$\mathcal{X}$

這堂幾乎沒有公式，內容是一張分類表與每一格的例子。這種課容易聽完覺得都懂、遇到真的問題卻標不出來，所以本文在每一節各擬一組小資料，把那一節的差別算出來。先備是基石第 1 堂：機器學習是什麼的五個符號（ $f$ 、 $\mathcal{D}$ 、 $\mathcal{A}$ 、 $\mathcal{H}$ 、 $g$ ）與上一堂的 PLA。讀完之後，你應該能把一個學習問題在四個軸上各標一次、說出標的理由，並且指出它離這門課主要處理的那一格有多遠。

輸出空間不同：是非題之外還有哪些題型

YouTube：Types of Learning :: Learning with Different Output Space @ Machine Learning Foundations (機器學習基石)

（影片 00:00–04:19 回顧上一堂與二元分類，04:19–08:21 多類別分類，08:24–11:02 迴歸，11:05–15:28 結構化學習，15:28–16:35 小結，之後是 Fun Time。）

二元分類：已經會做的是非題

講義第 2 頁把信用卡核卡的流程圖再放一次，只在申請人資料表底下多加一列：credit? $\{\text{no}(-1), \text{yes}(+1)\}$ 。頁尾寫：

\mathcal{Y} = \{-1, +1\}: \text{binary classification}

輸出只有兩種可能，叫二元分類，課堂上的白話說法是是非題。第 3 頁放了三張圖，都是平面上的藍色圈圈與紅色叉叉，被一條邊界分成藍、紅兩塊：左圖的邊界是一條直線，分得乾乾淨淨；中圖也是直線，但有幾個點落在錯的那一側；右圖的邊界是一個圓，圈圈在圓裡面。課堂上說，之後會學到用直線以外的曲線來分這兩塊。

同一頁列了五個二元分類的例子：核卡或不核卡、垃圾信或正常信、病人有沒有生病、廣告會不會賺錢、答案對或錯。最後一個標著 KDDCup 2010，課堂上說這就是之前提過、他們在 KDD Cup 比賽裡要解的問題：預測學生在答題系統裡下一題會不會答對。

講義對二元分類的評語是 core and important problem with many tools as building block of other tools。課堂上的說法是：機器學習裡很多理論推導與實際的演算法都從二元分類出發，有點像要先會答是非題，才會答更複雜的題目。

多類別分類：販賣機怎麼認硬幣

第 4 頁的例子是辨識美國硬幣。課堂上說大家可能都用過這個應用：販賣機要判斷你投進去的是哪一種銅板。美國常見的硬幣有四種，1 分、5 分、10 分、25 分（講義寫 1c、5c、10c、25c）。講義的圖是一張散佈圖，橫軸是大小（Size），縱軸是重量（Mass），四種硬幣各自聚成一團，用四種顏色標出來：

位置	硬幣	說明
左下	10c	最小也最輕
緊鄰 10c 的右上方	1c	和 10c 靠得很近
中間偏右上	5c
右上	25c	最大也最重

課堂上特別提醒，美國硬幣不照面額排大小：10 分的那一顆是所有硬幣裡最小、最輕的。這個細節在標籤那一節會再用到。

這時輸出有四種。講義寫 $\mathcal{Y} = \{1c, 5c, 10c, 25c\}$ ，抽象一點寫成

\mathcal{Y} = \{1, 2, \cdots, K\}

這裡 $K = 4$ 。二元分類是 $K = 2$ 的特例。課堂上的白話說法是單選題：是非題只有圈和叉兩個選項，現在有四個、五個選項，要從裡面選一個對的。

本文補充一點，後面分辨多類別分類和迴歸時用得到： $\{1, 2, \cdots, K\}$ 裡的數字只是類別的名字。把 10c 編成 1、1c 編成 2、5c 編成 3，並不表示 1c「介於」10c 與 5c 之間，更不能把兩個類別的編號拿來平均。

講義列的其他例子：手寫數字辨識成 0 到 9（課堂上說郵遞區號的辨識就用到）、一張圖片裡是蘋果、橘子還是草莓、把電子郵件分成垃圾信、重要、社交、促銷、更新（講義標 Google；課堂上說 Google 的信箱當時正在推這種自動分類）。頁尾的評語是 many applications in practice, especially for 'recognition'，課堂上說就是視覺或聽覺的辨識。

迴歸：輸出是一個實數

第 5 頁用醫院裡的三個問題，把三種輸出放在一起比：

二元分類：病人的資料 ⇒ 有沒有生病
多類別分類：病人的資料 ⇒ 哪一種癌症
迴歸（regression）：病人的資料 ⇒ 還要幾天才會康復

課堂上把第三個問題講得更具體：病人剛開完刀，要多久才能出院，想知道的是幾天，或者幾天幾小時幾秒這樣的數字。輸出空間於是變成整條實數線，或者實數線上的一段：

\mathcal{Y} = \mathbb{R} \qquad \text{或} \qquad \mathcal{Y} = [\text{lower}, \text{upper}] \subset \mathbb{R}

後者講義稱為 bounded regression。課堂上舉的有範圍的例子是打分數：分數在 0 到 100 之間，不能打超過 100 分，也不能扣到 0 分以下。

講義在這裡加了一句 deeply studied in statistics。課堂上說，這個問題在統計裡已經被研究了好幾十年，學過線性迴歸的人看過的就是一個典型的迴歸問題，這門課之後會用機器學習的觀點再講一次。其他例子：公司的資料 ⇒ 股價、氣候的資料 ⇒ 氣溫。頁尾的評語和二元分類幾乎一樣：also core and important with many 'statistical' tools as building block of other tools。

迴歸和多類別分類的差別就在輸出的數字有沒有大小的意義。康復天數是 6 還是 7，兩個答案差一天，猜 6.5 也說得通。硬幣的類別 2 與 3 沒有「差一」這回事。

結構化學習：輸出是一整個結構

第 6 頁的例子來自自然語言處理：給一句話，標出每個字的詞性。講義畫的句子是 I love ML，三個字底下分別標 pronoun（代名詞）、verb（動詞）、noun（名詞）。

這個問題有兩種看法，講義並排寫出來：

多類別分類：word ⇒ word class。一次看一個字，輸出它的詞性。
結構化學習（structured learning）：sentence ⇒ structure (class of each word)。一次看整句，輸出整串詞性。

為什麼要整句一起看？課堂上的解釋是，句子裡有結構。love 這個字可能是動詞，也可能是名詞，單看這個字不容易判斷；整句送進去，就可以利用它在句子裡的位置，例如它接在一個名詞後面的話，比較可能是動詞。

整句一起看的時候，輸出空間是「所有合乎文法的詞性串」。講義用 P、V、N 代表代名詞、動詞、名詞：

\mathcal{Y} = \{PVN, PVP, NVN, PV, \cdots\}, \quad \text{not including } VVVVV

課堂上逐一說明：代名詞、動詞、名詞是一個正確的英文句子；代名詞、動詞、代名詞也是；動詞是不及物動詞的話，代名詞加動詞也成立。連續五個動詞就一定不合文法，所以 $VVVVV$ 不在 $\mathcal{Y}$ 裡。

講義把這種問題描述成 huge multiclass classification problem (structure ≡ hyperclass) without 'explicit' class definition：把每一種結構當成一個類別，它就是一個類別非常多、而且沒辦法把類別一一列出來的多類別分類問題。課堂上說，類別藏在底下，彼此之間有結構上的關係；所有正確的句子很難窮舉，因為還跟句子的長度有關。

數值例子：詞性串有多少種

以下是本文自擬的計算，不在講義上，用來說明 huge 有多大。假設詞性只有講義用的 P、V、N 三種。長度是 $L$ 個字的句子，每個字有 3 種標法，候選的詞性串有 $3^L$ 種：

句子長度 $L$	候選詞性串 $3^L$	講義提到的
1	3
2	9	$PV$
3	27	$PVN$ 、 $PVP$ 、 $NVN$
4	81
5	243	$VVVVV$ （不合文法，被排除）

長度 1 到 5 加起來是 $3 + 9 + 27 + 81 + 243 = 363$ 種候選， $\mathcal{Y}$ 是其中合乎文法的那一部分。這還只是三種詞性、最多五個字。詞性分成 $K$ 種、句子有 $L$ 個字時，候選數是 $K^L$ ；取 $K = 10$ 、 $L = 20$ 就是 $10^{20}$ 。

這個結果代表什麼。 硬幣辨識可以每一類收集幾十顆樣本。 $10^{20}$ 個「類別」不可能每一類都有樣本，連把類別寫下來都做不到，這就是講義說的 without 'explicit' class definition。反過來，拆成一個字一個字的多類別分類，三個字的句子只是 3 個各有 3 類的小問題，類別數完全不是問題，但每個字獨立判斷， $VVV$ 這種整體看就不合理的答案沒有機制可以排除。結構化學習要的是兩邊的好處：輸出整個結構，同時利用結構本身的規律把候選縮小。

講義列的其他例子：蛋白質的資料 ⇒ 蛋白質的摺疊方式、語音資料 ⇒ 剖析樹（parse tree）。課堂上說，蛋白質立體的形狀哪裡彎、哪裡折，會影響它在生物體裡怎麼作用。頁尾的評語是 a fancy but complicated learning problem。課堂上交代了這門課和它的關係：它的解法多半從多類別分類延伸出來，這門課不會教具體的方法；提它是要讓大家知道機器學習不只有是非題和選擇題，真的碰到的時候，會曉得它和其他問題的關聯。

這一節的小結：核心是二元分類與迴歸

第 7 頁把四種輸出空間列在流程圖旁邊：

問題	輸出空間 $\mathcal{Y}$
binary classification	$\{-1, +1\}$
multiclass classification	$\{1, 2, \cdots, K\}$
regression	$\mathbb{R}$
structured learning	structures

清單最後一行是 . . . and a lot more!!，四種只是比較重要的幾種。頁尾寫 core tools: binary classification and regression。課堂上說，之後的課會花比較多時間在這兩種問題的工具上，這些工具可以拿來建構更複雜的工具，解決其他種類的問題。

Fun Time：體育館的門禁系統

題目（第 8 頁）： 學校體育館的門禁系統用機器學習做自動人臉辨識，目的是對四種不同身分的使用者收不同的費用：Staff、Student、Professor、Other。哪一種學習問題最符合這個系統的需要？

binary classification
multiclass classification
regression
structured learning

答案：2。 講義的解釋只有一句：There is an 'explicit' $\mathcal{Y}$ that contains four classes。輸出是四個寫得出來的類別， $K = 4$ 。課堂上補充，這四類真的能寫下來，裡面沒有隱藏的結構。

其他選項（以下是本文的推理）：選項 1 只有兩個類別，四種身分裝不下。選項 3 容易讓人猶豫，因為系統最後要「收不同的錢」，錢是數字。但系統要從人臉判斷的是身分，費用只是查表的結果；四種身分沒有大小順序，「介於 Student 與 Professor 之間」沒有意義，這正是前面說的類別編號不能當實數用。選項 4 需要輸出一個內部有關聯的結構，這裡每次只輸出一個身分。

標籤給多少：每筆資料都有答案嗎

YouTube：Types of Learning :: Learning with Different Data Label @ Machine Learning Foundations (機器學習基石)

（影片 00:00–01:21 監督式，01:21–04:34 分群，04:34–07:35 其他非監督式問題，07:38–10:32 半監督式，10:35–16:04 強化學習，16:04–17:24 小結，之後是 Fun Time。）

這一節固定用硬幣辨識當例子，只改一件事：訓練資料裡的 $y_n$ 給了多少。

監督式：每個 xₙ 都附上 yₙ

第 9 頁把硬幣的彩色散佈圖放回流程圖裡，頁尾寫 supervised learning: every $\mathbf{x}_n$ comes with corresponding $y_n$ 。每顆硬幣除了大小與重量，還附上它是哪一種。前兩堂的信用卡問題與 PLA 都是這種設定，只是當時沒有給它名字。

課堂上解釋「監督」這個詞：監督的意思就像老師。老師把銅板交給學生，同時告訴他這一顆是 10 分、那一顆是 1 分，每一顆都講。這是一種完整的教學。

一組貫穿這一節的硬幣資料

以下的資料是本文自擬的，不在講義上。八顆硬幣，每種兩顆；大小與重量各自換算成 1 到 11 的刻度，數字是為了好算而編的，不是真實硬幣的規格。四種硬幣的相對位置照講義的圖：10c 在左下，1c 緊鄰著它，25c 在右上。

硬幣	$\mathbf{x}_n$ =（大小, 重量）	$y_n$
1	$(1, 1)$	10c
2	$(2, 2)$	10c
3	$(4, 2)$	1c
4	$(4, 3)$	1c
5	$(7, 5)$	5c
6	$(8, 6)$	5c
7	$(10, 9)$	25c
8	$(11, 9)$	25c

監督式的做法。 講義這裡沒有指定演算法，本文挑一個最容易手算的：每一類算出中心（同類各點的平均），新的硬幣離哪個中心最近就判成哪一類。四個中心是

\text{10c}: (1.5, 1.5), \quad \text{1c}: (4, 2.5), \quad \text{5c}: (7.5, 5.5), \quad \text{25c}: (10.5, 9)

販賣機裡投進一顆 $(3, 2)$ 的硬幣。它到四個中心的距離平方分別是

\begin{aligned} \text{10c}: \ & (3 - 1.5)^2 + (2 - 1.5)^2 = 2.5 \\ \text{1c}: \ & (3 - 4)^2 + (2 - 2.5)^2 = 1.25 \\ \text{5c}: \ & (3 - 7.5)^2 + (2 - 5.5)^2 = 32.5 \\ \text{25c}: \ & (3 - 10.5)^2 + (2 - 9)^2 = 105.25 \end{aligned}

最近的是 1c，所以 $g((3, 2)) = \text{1c}$ 。這個做法用到了全部八個 $y_n$ ：沒有標籤，就不知道哪幾顆該放在一起算中心。

非監督式：把 yₙ 全部拿掉

第 10 頁問：不告訴機器每顆硬幣是什麼，還學得到東西嗎？講義把同一張散佈圖畫兩次。左邊是彩色的，標 supervised multiclass classification。右邊所有的點都塗成同一種藍色，機器看到的只剩位置。這一頁有兩個版本，第二個版本在右圖上多畫了三個圈，把點圈成三群。講義的標示是

\text{unsupervised multiclass classification} \iff \text{'clustering'}

沒有標籤的多類別分類，做的事就是分群（clustering）。課堂上的比喻是把一堆銅板丟給小朋友，讓他自己玩、自己決定怎麼分堆，沒有人告訴他哪顆是幾分。就算不給答案，點在平面上也不是零零落落的：左邊有一些比較小比較輕的，右邊有一些比較大比較重的。

接著課堂上指出分群難在哪裡，講義的圖只畫了三個圈，沒有寫出原因：

大家心裡知道硬幣有四種，但只看右邊那張圖，很可能覺得只有三群，因為 10 分和 1 分長得沒差多少。
做分類時至少知道有四類，分群時連有幾群都不知道。
有人說全部算一群，也沒有什麼不對。所以分群的好壞比分類更難衡量。

用上面的八顆硬幣看這三點（以下是本文自擬的觀察，不在講義上）。把 $y_n$ 那一欄遮住，只留八個點，量一量硬幣之間隔多遠：

比較的兩顆	距離
同一種硬幣的兩顆（四種都算）	$1$ 到 $\sqrt{2} \approx 1.41$
硬幣 2 與硬幣 3（10c 與 1c 之間最近的一對）	$2$
硬幣 4 與硬幣 5（1c 與 5c 之間最近的一對）	$\sqrt{13} \approx 3.61$
硬幣 6 與硬幣 7（5c 與 25c 之間最近的一對）	$\sqrt{13} \approx 3.61$

這張表代表什麼。 10c 與 1c 之間的空隙是 2，只比同一種硬幣內部的間隔大一點，另外兩個空隙則有 3.61。只看位置的人把硬幣 1 到 4 圈成一團、畫出三群，是很自然的結果，這就是課堂上說的 10 分和 1 分長得沒差多少。畫成四群也說得通，全部圈成一群也沒有人能說錯，因為手上沒有答案可以對。監督式的問題可以數判錯幾顆；非監督式的問題沒有這種現成的標準，要比較兩種分法，得先另外訂出「怎樣算分得好」，而這個準則本身就有很多種訂法。

講義列的分群應用有兩個：文章 ⇒ 主題、顧客資料 ⇒ 顧客群。課堂上說後者可以針對不同的群做不同的促銷。頁尾的評語是 clustering: a challenging but useful problem。

第 11 頁說明分群只是非監督式學習的一種，並把三種問題各自對到一種監督式的問題：

非監督式問題	輸入 ⇒ 輸出	講義的類比	講義的例子
clustering（分群）	$\{\mathbf{x}_n\} \Rightarrow \text{cluster}(\mathbf{x})$	≈ unsupervised multiclass classification	文章 ⇒ 主題
density estimation（密度估計）	$\{\mathbf{x}_n\} \Rightarrow \text{density}(\mathbf{x})$	≈ unsupervised bounded regression	附地點的交通事故報告 ⇒ 危險的區域
outlier detection（離群值偵測）	$\{\mathbf{x}_n\} \Rightarrow \text{unusual}(\mathbf{x})$	≈ extreme unsupervised binary classification	網路的紀錄 ⇒ 入侵警示

課堂上對後兩種的說明：密度估計是給機器一堆點，問哪裡比較稠密、哪裡比較稀疏，例如把各個路口的事故紀錄交給機器，問哪裡比較常出事；它像有範圍的迴歸，因為想知道的是底下那個類似密度或機率的函數長什麼樣子。離群值偵測是資料大部分正常、小部分怪怪的，例如網路流量裡的怪資料可能代表入侵者，或者某台機器運作不正常；它像一個很極端的是非題，因為「是」的情形非常少，也正因為少，很難取得有標籤的資料。

頁尾的評語是 unsupervised learning: diverse, with possibly very different performance goals。課堂上說，監督式因為有標籤在那裡，目標大致是清楚的；非監督式的目標比較分散，演算法的好壞通常也比較難衡量。

半監督式：只有少數幾個 yₙ

第 12 頁把三種情形排成一列：左圖全部彩色（supervised），右圖全部藍色（unsupervised, clustering），中間那張大部分是藍點、只有少數幾個點有顏色，標 semi-supervised。課堂上說這是介於兩者之間的情形：少數的點告訴機器答案，大多數的點不告訴它。

講義的兩個例子：

少數有標註的人臉照片 ⇒ 人臉辨識器（講義標 Facebook）
少數有標註的藥物資料 ⇒ 藥效預測器

課堂上說明這兩個例子的共同點是標籤很貴。照片的例子，要人坐下來一張一張標這張臉是誰，標十張就不想做了；某個人的照片可能只標了兩張，其他很多張沒標的，希望機器自己認出來。藥物的例子，動物實驗或人體實驗都很貴，只有少部分的藥能做測試、知道有效還是沒效。頁尾的總結是 semi-supervised learning: leverage unlabeled data to avoid 'expensive' labeling。課堂上的說法是，它有點像監督式，但要用大量還沒標的資料讓表現再提升。

回到八顆硬幣（以下是本文自擬的示範；講義沒有指定半監督式的做法，這裡用的「先分群、再命名」只是其中最容易手算的一種）。假設請人看硬幣要花錢，只標了四顆：

有標籤：硬幣 1 是 10c、硬幣 4 是 1c、硬幣 5 是 5c、硬幣 8 是 25c。
沒標籤：硬幣 2、3、6、7，只知道大小與重量。

做法分三步：

先不管標籤，把八個點分成四群：每顆硬幣和離它最近的那一顆圈在一起，得到 $\{1, 2\}$ 、 $\{3, 4\}$ 、 $\{5, 6\}$ 、 $\{7, 8\}$ 。這裡是直接告訴演算法要分四群；前面說過，群數本身就是分群最難決定的地方。這一步用到了全部八個 $\mathbf{x}_n$ ，沒標籤的四顆也有貢獻。
每一群裡剛好有一顆有標籤的硬幣，用它替整群命名： $\{1, 2\}$ 是 10c、 $\{3, 4\}$ 是 1c、 $\{5, 6\}$ 是 5c、 $\{7, 8\}$ 是 25c。
八顆硬幣現在都有類別，照監督式的做法算中心，得到的四個中心和前面一模一樣， $(3, 2)$ 同樣判成 1c。

這個結果代表什麼。 只付了四個標籤的成本，得到和八個標籤相同的 $g$ 。沒標籤的資料提供的是「哪些點聚在一起」，少數的標籤提供的是「這一團叫什麼」。本文補充它成立的條件：資料自己形成的群必須和真正的類別對得上。同一批硬幣只分三群的話，硬幣 1 與硬幣 4 會落在同一群裡，一個說 10c、一個說 1c，這一群就沒辦法命名；某一群裡一顆有標籤的都沒有，也沒辦法命名。

強化學習：不給答案，只說剛才那樣好不好

第 13 頁的副標是 a 'very different' but natural way of learning。講義用訓練小狗當例子，標題是 Teach Your Dog: Say 'Sit Down'，同一頁有兩個版本。

版本一。 你說「坐下」，狗在地上尿尿（The dog pees on the ground）。你罵牠：BAD DOG. THAT'S A VERY WRONG ACTION。講義底下兩行是：

cannot easily show the dog that $y_n$ = sit when $\mathbf{x}_n$ = 'sit down'
but can 'punish' to say $\tilde{y}_n$ = pee is wrong

版本二。 你說「坐下」，狗真的坐下了。你說 Good Dog，給牠餅乾。

still cannot show $y_n$ = sit when $\mathbf{x}_n$ = 'sit down'
but can 'reward' to say $\tilde{y}_n$ = sit is good

這裡有兩個要分清楚的符號。 $y_n$ 是你心裡要的那個正確輸出。 $\tilde{y}_n$ 是對方實際做出來的輸出。監督式學習直接把 $(\mathbf{x}_n, y_n)$ 交給機器；訓練狗的時候，你沒辦法直接把「坐下才是對的」這件事交給牠，你能給的只有對 $\tilde{y}_n$ 的評價，是好還是不好。講義把這種資料寫成三個一組：

(\mathbf{x}, \tilde{y}, \text{goodness})

課堂上強調，被獎勵也不代表做到了最正確的事。你說坐下，狗卻跟你握手，你可能還是很高興、還是給牠餅乾；獎勵只說了這個動作好，沒有說它就是你最期待的那一個。

講義的兩個應用：

（顧客, 選了哪個廣告, 廣告點擊的收入）⇒ 廣告系統
（手上的牌, 策略, 贏了多少）⇒ 21 點的玩家程式

課堂上的說明：廣告系統像是顧客在訓練它，輸入是顧客的資料，系統選了一個廣告放上去，這是 $\tilde{y}$ ，顧客有沒有點、有沒有讓你賺到錢，就是這個選擇好不好。玩 21 點時，拿著某一手牌決定不補牌，結果輸了或贏了；這只說明這一次不補牌好不好，沒有說補牌或不補牌哪一個才是最好的。

以下是本文自擬的小例子，把「只知道做過的那個選擇好不好」寫成資料。一個廣告系統有 A、B、C 三支廣告，記錄了六次曝光：

第幾次	$\mathbf{x}$ （顧客）	$\tilde{y}$ （放了哪支）	goodness（收入）
1	學生	A	0
2	學生	B	5
3	上班族	A	8
4	學生	B	3
5	上班族	C	0
6	上班族	A	6

把同一種顧客、同一支廣告的收入平均：學生看 A 平均 0（1 次）、看 B 平均 4（2 次）；上班族看 A 平均 7（2 次）、看 C 平均 0（1 次）。學生看 C、上班族看 B 這兩格一次都沒試過。六次曝光各有三支廣告可以放，總共 18 個「這位顧客看這支廣告會怎樣」的問題，資料只回答了其中 6 個。

這個結果代表什麼。 換成監督式的資料，每一列會直接寫「這位顧客該放哪一支」，也就是 $y_n$ 。這裡沒有任何一列這樣寫。對學生放 B 的收入是正的，但沒有人知道 C 會不會更好，因為 C 從來沒對學生放過。這就是講義頁尾說的 learn with 'partial/implicit information'；後面括號裡的 often sequentially，課堂上說留到談 protocol 的時候解釋。

reinforcement learning 的中文，課堂上說有人譯成增強式學習，意思是一步一步讓電腦愈變愈強；本文用另一個同樣常見的譯名「強化學習」。

這一節的小結：核心是監督式

第 14 頁的清單：

種類	標籤的狀況
supervised	all $y_n$
unsupervised	no $y_n$
semi-supervised	some $y_n$
reinforcement	implicit $y_n$ by goodness( $\tilde{y}_n$ )

最後一行同樣是 . . . and more!!。頁尾寫 core tool: supervised learning。課堂上說，其他很多方法都是從監督式的方法發展出來的，所以監督式是這門課的重點。

Fun Time：樹的辨識系統

題目（第 15 頁）： 一家公司想做樹的辨識系統，從網路上收集了一百萬張圖片，然後請公司的 10 位成員每人看 100 張，記錄每張圖裡有沒有樹。這些圖片與紀錄接著交給學習演算法來建立系統。演算法要解的是哪一種學習問題？

supervised
unsupervised
semi-supervised
reinforcement

答案：3。 講義的解釋：The 1,000 records are the labeled $(\mathbf{x}_n, y_n)$ ; the other 999,000 pictures are the unlabeled $\mathbf{x}_n$ 。算一下： $10 \times 100 = 1{,}000$ 張有標籤， $1{,}000{,}000 - 1{,}000 = 999{,}000$ 張沒有，有標籤的只占 $0.1\%$ 。課堂上說這是典型的半監督式問題，把有標的和沒標的通通交給機器，希望能做得更好。

其他選項（本文的推理）：選項 1 要每一張都有標籤，這裡絕大多數沒有。選項 2 要完全沒有標籤，這裡有 1,000 個，而且目標很明確，就是有樹或沒有樹。選項 4 的資料應該長成「系統做了一個判斷、有人說這個判斷好不好」，題目裡的紀錄是人直接寫下正確答案。關鍵在題目寫的是圖片與紀錄都交給演算法；公司只拿那 1,000 張有標籤的去訓練、把其餘的丟掉的話，同一批資料就變成監督式的問題。順帶把輸出空間那個軸也標一次：輸出是有樹或沒有樹，是二元分類。

資料怎麼交給演算法：一次給完、一筆一筆來，或者讓機器發問

YouTube：Types of Learning :: Learning with Different Protocol @ Machine Learning Foundations (機器學習基石)

（影片 00:00–01:55 batch，01:55–05:58 online，05:58–09:11 active，09:13–09:54 小結，之後是 Fun Time。）

這一節的英文名稱是 Learning with Different Protocol，Roadmap 上寫成 $f \Rightarrow (\mathbf{x}_n, y_n)$ ：目標函數 $f$ 的資訊怎麼變成一筆一筆的資料，到達演算法手上。課堂上把 protocol 說成人跟機器溝通的方式，也就是怎麼把資料餵給機器。

Batch：整批一次給完

第 16 頁再放一次硬幣的流程圖，頁尾寫 batch supervised multiclass classification: learn from all known data。這一行同時標了三個軸：protocol 是 batch，標籤是 supervised，輸出是 multiclass classification。

課堂上描述前兩堂一直沒有明說的做法：先收集一堆硬幣，例如 200 顆，量好大小與重量、標好是哪一種，然後把這 200 筆資料整批交給演算法，得到一個 $g$ ；這個 $g$ 裝進販賣機，之後每一顆投進來的硬幣都用同一個 $g$ 判斷。他的比喻是丟一本書給機器，讓它自己翻、自己學。

第 17 頁再放一次彩色與全藍的兩張散佈圖，列出三個 batch 的例子：

一批（信件, 是不是垃圾信）⇒ 垃圾信過濾器
一批（病人, 有沒有癌症）⇒ 癌症分類器
一批病人資料 ⇒ 病人的分群

第三個例子沒有標籤，是非監督式的，照樣可以是 batch。protocol 和標籤是兩個獨立的軸。頁尾的評語是 batch learning: a very common protocol。

Online：資料一筆一筆來，假說跟著改

第 18 頁的標題是 Online: Spam Filter that 'Improves'。課堂上從一個問題開始：垃圾信過濾器真的是餵一批資料、學好 $g$ 之後就不動了嗎？日常用到的不太像這樣。信一封一封進來，過濾器先判斷，判錯了你就告訴它。講義把兩種過濾器並排：

batch 的過濾器：用已知的（信件, 是不是垃圾信）學習，之後用固定的 $g$ 預測。
online 的過濾器，依序重複三件事：
1. 看到一封信 $\mathbf{x}_t$
2. 用目前的 $g_t$ 預測它是不是垃圾信，也就是算 $g_t(\mathbf{x}_t)$
3. 從使用者那裡收到「想要的標籤」 $y_t$ ，用 $(\mathbf{x}_t, y_t)$ 更新 $g_t$

下標從 $n$ 換成 $t$ ，因為資料現在有先後順序。課堂上點出它和 batch 的兩個差別：假說一直在變，每一輪各有一個， $g_1, g_2, g_3, \dots$ ；資料是一筆一筆告訴機器的，沒有先收集好一千封再整批給。追求的目標也跟著換：batch 希望最後出來的那一個 $g$ 是好的，online 希望每一輪的 $g$ 愈變愈好。頁尾的說法是 online: hypothesis 'improves' through receiving data instances sequentially。

同一頁有一個小框 Connection to What We Have Learned，裡面是兩個問句。

PLA can be easily adapted to online protocol (how?) 課堂上的回答：PLA 每一輪做的事本來就是挑一筆出來看對不對，對就不動，錯就修正。換到 online，每來一封新的信就做預測，預測對了沒事，預測錯了就做和 PLA 一樣的修正。他還說，可以證明這個 PLA 的變形在 online 的 protocol 上也是有用的。

reinforcement learning is often done online (why?) 課堂上的回答：強化學習每次只得到部分的資訊。我們不可能一次告訴狗三件事，坐下對不對、上廁所對不對、握手對不對；一次只能知道牠在這個情況下做的這一個動作好不好。所以強化學習的資料通常是一筆一筆進來的，比較接近 online。標籤那一節留下的 often sequentially，答案就在這裡。

本文補充：online 版 PLA 會判錯幾次

講義在這裡只留下 (how?) 這個問句，課堂上只說可以證明，兩邊都沒有寫出證明。這一小節從頭到尾是本文補充的推導與自擬的數值例子，不是講義或課堂的內容；用的全是基石第 2 堂：感知器與 PLA的結果。

先把 online 版的 PLA 寫清楚。從 $\mathbf{w}_1 = \mathbf{0}$ 開始（上一堂從 $\mathbf{w}_0$ 起算；這裡為了讓第 $t$ 輪的權重對上第 $t$ 封信，改從 1 起算，其餘不變），第 $t$ 輪：

收到 $\mathbf{x}_t$ （已補上 $x_0 = 1$ ），算分數 $\mathbf{w}_t^\top\mathbf{x}_t$ ，預測 $\text{sign}(\mathbf{w}_t^\top\mathbf{x}_t)$ 。
收到 $y_t$ 。預測錯了，也就是 $y_t\mathbf{w}_t^\top\mathbf{x}_t \le 0$ （和上一堂一樣，分數剛好是 0 也算錯），就修正 $\mathbf{w}_{t+1} = \mathbf{w}_t + y_t\mathbf{x}_t$ ；預測對了， $\mathbf{w}_{t+1} = \mathbf{w}_t$ 。

batch 版問的是「會不會停」。online 的信一直來，沒有停不停的問題，該問的是：總共會判錯幾次？

假設整串資料是線性可分的，存在某個 $\mathbf{w}_f$ ，讓每一輪都有 $y_t\mathbf{w}_f^\top\mathbf{x}_t > 0$ 。照上一堂的記號定義

R^2 = \max_{t}\lVert\mathbf{x}_t\rVert^2, \qquad \rho = \min_{t} y_t\frac{\mathbf{w}_f^\top}{\lVert\mathbf{w}_f\rVert}\mathbf{x}_t

線性可分時 $\rho > 0$ 。上一堂證明的兩個事實，各自只描述「一次修正」前後發生的事：

\mathbf{w}_f^\top\mathbf{w}_{t+1} \ \ge\ \mathbf{w}_f^\top\mathbf{w}_t + \rho\lVert\mathbf{w}_f\rVert, \qquad \lVert\mathbf{w}_{t+1}\rVert^2 \ \le\ \lVert\mathbf{w}_t\rVert^2 + R^2

第一條用到修正式與 $\rho$ 的定義；第二條用到「只在 $y_t\mathbf{w}_t^\top\mathbf{x}_t \le 0$ 時修正」。兩條都沒有用到那筆資料是從一批舊資料裡挑的，還是剛到的新資料，所以在 online 的修正上照樣成立。沒判錯的那幾輪， $\mathbf{w}$ 不變，兩個量都不動。

設前 $T$ 輪裡總共判錯 $M$ 次。從 $\mathbf{0}$ 出發，把兩條不等式各累加 $M$ 次：

\mathbf{w}_f^\top\mathbf{w}_{T+1} \ \ge\ M\rho\lVert\mathbf{w}_f\rVert, \qquad \lVert\mathbf{w}_{T+1}\rVert \ \le\ \sqrt{M}R

兩個向量夾角的 cos 不超過 1，分子用下界、分母用上界：

1 \ \ge\ \frac{\mathbf{w}_f^\top\mathbf{w}_{T+1}}{\lVert\mathbf{w}_f\rVert\lVert\mathbf{w}_{T+1}\rVert} \ \ge\ \frac{M\rho\lVert\mathbf{w}_f\rVert}{\lVert\mathbf{w}_f\rVert\cdot\sqrt{M}R} = \sqrt{M}\cdot\frac{\rho}{R} \quad\Longrightarrow\quad M \le \frac{R^2}{\rho^2}

右邊和 $T$ 無關。信來了一千封還是一百萬封，只要整串資料分得開、 $R$ 與 $\rho$ 不變，判錯的總次數就不會超過 $R^2/\rho^2$ 。上一堂的「修正次數有上限」，在 online 讀成「判錯次數有上限」。

數值例子（本文自擬，不在講義上）。 垃圾信過濾器只看兩個特徵：兩個關鍵字每一百字各出現幾次，記成 $(x_1, x_2)$ 。使用者心裡的規則是 $x_1 + x_2 > 2$ 就算垃圾信（ $y = +1$ ），過濾器不知道這條規則。十封信依序進來：

$t$	來信 $(x_1, x_2)$	這一輪的 $\mathbf{w}_t$	分數	預測	$y_t$	判錯？	$\mathbf{w}_{t+1}$
1	$(3, 0)$	$(0, 0, 0)$	$0$	無法判斷	$+1$	是	$(1, 3, 0)$
2	$(1, 0)$	$(1, 3, 0)$	$4$	$+1$	$-1$	是	$(0, 2, 0)$
3	$(0, 3)$	$(0, 2, 0)$	$0$	無法判斷	$+1$	是	$(1, 2, 3)$
4	$(0, 1)$	$(1, 2, 3)$	$4$	$+1$	$-1$	是	$(0, 2, 2)$
5	$(2, 2)$	$(0, 2, 2)$	$8$	$+1$	$+1$	否	不變
6	$(1, 0.5)$	$(0, 2, 2)$	$3$	$+1$	$-1$	是	$(-1, 1, 1.5)$
7	$(0.5, 0.5)$	$(-1, 1, 1.5)$	$0.25$	$+1$	$-1$	是	$(-2, 0.5, 1)$
8	$(4, 1)$	$(-2, 0.5, 1)$	$1$	$+1$	$+1$	否	不變
9	$(0, 2.5)$	$(-2, 0.5, 1)$	$0.5$	$+1$	$+1$	否	不變
10	$(1.5, 0)$	$(-2, 0.5, 1)$	$-1.25$	$-1$	$-1$	否	不變

拿第 6 封示範一列怎麼算： $\mathbf{x}_6 = (1, 1, 0.5)$ ，分數是 $0 \cdot 1 + 2 \cdot 1 + 2 \cdot 0.5 = 3$ ，預測是垃圾信；使用者說不是（ $y_6 = -1$ ），判錯， $\mathbf{w}_7 = (0, 2, 2) - (1, 1, 0.5) = (-1, 1, 1.5)$ 。

十封信判錯 6 次，全部發生在前 7 封，最後 3 封都判對。對照上限：最長的是第 8 封， $\lVert\mathbf{x}_8\rVert^2 = 1 + 16 + 1 = 18$ ，所以 $R^2 = 18$ 。取 $\mathbf{w}_f = (-2, 1, 1)$ （就是 $x_1 + x_2 = 2$ 那條線），十封信的 $y_t\mathbf{w}_f^\top\mathbf{x}_t$ 最小是 $0.5$ ， $\lVert\mathbf{w}_f\rVert = \sqrt{6}$ ，所以 $\rho^2 = 0.25/6 = 1/24$ ，上限是 $18 \times 24 = 432$ 。實際的 6 次遠低於它。

這個例子代表什麼。 把每一輪結束時的 $\mathbf{w}$ 拿回去對全部十封信打分數，判錯的封數依序是 5、7、5、5、5、5、1、1、1、1（還沒開始時是 10）。整體趨勢是變好，中間有一輪從 5 封退到 7 封：修正一封信可能弄壞別的信，這和上一堂看到的現象相同。最後的 $\mathbf{w} = (-2, 0.5, 1)$ 還判錯 1 封，就是最早來的第 1 封： $-2 + 0.5 \times 3 = -0.5$ ，和 $y_1 = +1$ 不同號。online 不回頭檢查舊信，所以上限保證的是「一路上判錯的總次數」，沒有保證最後那個 $g$ 對看過的每一封都對。這封信再來一次，過濾器會再錯一次、再修正一次，這一次同樣算在 432 次的額度裡。batch 版的 PLA 會反覆繞同一批資料，直到全部分對才停，兩種 protocol 的差別在這裡看得最清楚。

Active：讓機器自己挑問題問

第 19 頁的標題是 Active Learning: Learning by 'Asking'。講義在流程圖上加了一條橘色的箭頭，從演算法 $\mathcal{A}$ 指回目標函數 $f$ ：資料不再只是從 $f$ 單向流到 $\mathcal{A}$ ， $\mathcal{A}$ 可以回頭向 $f$ 提問。旁邊的框把三種 protocol 對到三種學習的方式（Protocol ⇔ Learning Philosophy）：

protocol	講義的說法	課堂上的比喻
batch	'duck feeding'	填鴨式教育：丟一本參考答案都寫好的書，叫你自己讀
online	'passive sequential'	老師教書：舉一個例子、告訴你答案，再舉下一個
active	'question asking' (sequentially)，query the $y_n$ of the chosen $\mathbf{x}_n$	學生發問

課堂上指出前兩種的共同點：從機器的角度看都是被動的，人家餵什麼資料就做什麼事。active learning 給演算法一個新的能力：它可以提出一個 $\mathbf{x}$ ，問這個輸入的 $y$ 是多少。課堂上舉手寫辨識當例子，機器可以自己寫出一個字，或者挑一個它還不會認的字，問你這到底是 9 還是 7。林軒田說這在當時是機器學習裡比較新、也被廣泛研究的設定。

這樣做的理由寫在頁尾：active: improve hypothesis with fewer labels (hopefully) by asking questions strategically。課堂上說，問問題是有技巧的，有技巧地問，也許用很少的問題就能很快學到東西；它用在標籤很貴的場合，和半監督式學習的出發點類似。括號裡的 hopefully 是講義自己加的，表示這是期望，不是保證。

數值例子：問 4 次，還是標 16 次

以下是本文自擬的例子，不在講義上，用來說明 strategically 能省多少。桌上有 16 顆硬幣，只有 1c 和 5c 兩種，已經照重量從輕到重排成一列，編號 1 到 16。假設 1c 一定比 5c 輕，所以這一列的前面一段全是 1c、後面一段全是 5c，只是不知道從第幾顆開始換。請人辨認一顆硬幣算一個標籤。真實的情況是前 11 顆是 1c（演算法不知道）。

batch 的做法是 16 顆全部請人標，花 16 個標籤。active 的做法是每次挑「還不確定的那一段」正中間的那一顆去問：

第幾次問	問之前還不確定的範圍	挑哪一顆	得到的答案	問完之後確定的事
1	1 到 16	8	1c	1 到 8 都是 1c
2	9 到 16	12	5c	12 到 16 都是 5c
3	9 到 11	10	1c	9、10 是 1c
4	11	11	1c	11 是 1c，全部確定

問了 4 次，16 顆硬幣的類別全部知道。其餘 12 顆沒有人看過，是從「重量排序」加上「已經問到的答案」推出來的。

換點落在別的位置時次數會略有不同：16 顆硬幣有 17 種可能的換點（包含全部是 1c、全部是 5c），這個問法最少問 4 次、最多問 5 次。每問一次，還不確定的範圍大約減半，所以 $N$ 顆硬幣大約要問 $\log_2 N$ 次；一百萬顆大約是 20 次（ $\log_2 10^6 \approx 19.9$ ），全部標則要一百萬次。

這個例子代表什麼。 省下來的標籤來自「挑」：每一次都問當下最沒把握的那一顆，已經有把握的不問。挑得不好就沒有這個效果，從第 1 顆開始照順序問的話，要問到第 12 顆才看到第一顆 5c。本文也要提醒這個例子刻意做得很乾淨：資料只有一個維度，而且完全沒有雜訊。真實的問題很少這麼理想，所以講義才寫 hopefully。

這一節的小結：核心是 batch

第 20 頁的清單：

protocol	資料怎麼來
batch	all known data
online	sequential (passive) data
active	strategically-observed data

最後一行是 . . . and more!!。頁尾寫 core protocol: batch。課堂上說這門課會著重在 batch，理由是 batch 的很多演算法學會之後，要延伸到 online 或其他設定也還蠻容易的，PLA 就是一個例子。

Fun Time：棒球照片的分類

題目（第 21 頁）： 一位攝影師有 100,000 張照片，每張裡有一位棒球選手。他想自動把照片依照裡面的選手分類。他先自己分了 1,000 張，然後寫了一個演算法：對其餘的照片，如果演算法對分到哪一類「有信心」，就自己分；沒有信心，就停下來等人輸入，並且從這個輸入學習。哪一種 protocol 最能描述這個演算法的性質？

batch
online
active
random

答案：3。 講義的解釋：The algorithm takes a active but naïve strategy: ask when 'confused'. You should probably do the same when taking a class :-)。演算法自己決定哪一張要問人，問的時機是它困惑的時候。課堂上說關鍵字就是「問」，並且說這是 active learning 裡一個典型的做法；他也順勢說，對上課內容有困惑的話歡迎提問。

這個策略和前面 16 顆硬幣的例子是同一件事：硬幣的例子裡，「還不確定的範圍」就是演算法沒有信心的那些硬幣，範圍以外的它自己分類，不去問人。

其他選項（本文的推理）：選項 1，如果攝影師用那 1,000 張學出一個固定的 $g$ 、之後不再向人要任何標籤，才是 batch；題目裡演算法會停下來要標籤並繼續學。選項 2 的 online 是被動的，資料照它來的順序出現，每一筆的答案由對方給；這裡是演算法挑出特定的照片去問。選項 4 的 random 不是這堂介紹的 protocol，而且演算法挑照片的依據是有沒有信心，並非隨機。一個小差別：講義的題目有具體的數字（100,000 張裡先標 1,000 張，也就是 1%），課堂上口頭念題時把數字省略了，只說照片很多、沒辦法一一手動標。

輸入長什麼樣：特徵帶著多少意義

YouTube：Types of Learning :: Learning with Different Input Space @ Machine Learning Foundations (機器學習基石)

（影片 00:00–02:43 具體特徵，02:45–07:42 原始特徵，07:45–10:23 抽象特徵，10:26–10:59 小結，10:59–11:59 Fun Time，之後是整堂的總結與下一堂的預告。）

課堂上先定位這一節：前面談的大多和輸出那一側有關，最後回頭看輸入 $\mathbf{x}$ 有哪些變化。他也交代一個之後會一直出現的詞：輸入的每個維度常常叫作 feature，特徵。

具體特徵：每個維度都有講究的意義

第 22 頁再放一次信用卡的流程圖，這次把焦點放在申請人資料表上：年齡 23 歲、性別女、年薪新台幣 1,000,000、居住 1 年、工作 0.5 年、負債 200,000。頁尾寫：

\text{concrete features: each dimension of } \mathcal{X} \subseteq \mathbb{R}^d \text{ represents 'sophisticated physical meaning'}

每個維度都有具體、而且經過整理的意義。課堂上的說法是，這些資料代表一些蠻複雜、已經處理過的資訊，我們相信它們和想要的輸出有關係；正因為這樣，上一堂的線性假說才能直接把這些維度加權、加起來算一個總分。

第 23 頁列了前面用過的例子：硬幣分類的（大小, 重量）、核卡的顧客資料、癌症診斷的病人資料，並加上一行 often including 'human intelligence' on the learning task。課堂上把這件事叫作 domain knowledge，也就是人對這個問題的專業知識：這些特徵是人先在腦袋裡做過一輪預處理，才交給機器的。頁尾的評語是 concrete features: the 'easy' ones for ML。課堂上補了一句，說簡單其實也不簡單，是和接下來的兩種比起來相對簡單。

原始特徵：只有像素

第 24 頁是一格一格的手寫數字影像，6 列 9 行共 54 個字，筆跡各不相同。講義說這是 digit recognition problem: features ⇒ meaning of digit，一個典型的監督式多類別分類問題。課堂上問：要做這個問題，你會把什麼當作 $\mathbf{x}$ 交給機器？

第 25 頁並排兩種答案。

by Concrete Features。 從每張影像算出兩個數字， $\mathbf{x} = (\text{symmetry}, \text{density})$ ，對稱的程度與筆畫的密度。課堂上把問題簡化成只分 1 和 5 來說明這兩個特徵為什麼有用：1 比 5 對稱，1 的密度也比 5 低（筆畫占的黑格子比較少）。講義的圖是一張散佈圖，藍色圈圈聚在左上、紅色叉叉散在右下，旁邊放了幾張實際的數字影像，用線連到它們在圖上的位置。課堂上說明縱軸是對稱、橫軸是密度，所以 1 落在偏高偏左的地方，5 落在偏低偏右的地方；字寫得不好或掃描得不好的，會落在不太對的位置。

by Raw Features。 直接把影像攤開。講義寫：

\text{16 by 16 gray image } \mathbf{x} \equiv (0, 0, 0.9, 0.6, \cdots) \in \mathbb{R}^{256}

16 乘 16 是 256 格，每一格的灰階值是一個維度（課堂上說可以先正規化到 0 與 1 之間），每個數字就是一個 256 維的向量。講義的評語是 'simple physical meaning'; thus more difficult for ML than concrete features。課堂上解釋：每一個維度有物理意義，但意義很單純，就只是那一個點的深淺；我們寫出來的數字靠的不是單獨一個點，是這個點和旁邊的點有沒有寫等等的關係。

講義列的其他原始特徵：image pixels、speech signal。頁尾說 raw features: often need human or machines to convert to concrete ones。課堂上把這兩條路都給了名字。人來做的那一種，常被取一個好聽的名字叫 feature engineering（特徵工程）。機器自己做的那一種，他舉的是當時很紅的 deep learning（深度學習）：非常概略地說，是從大量的資料裡，甚至用非監督式的方式，學出怎麼抽取具體的特徵。他說這些抽取特徵的方法會在下一門課機器學習技法的後期介紹。他也提醒，換成原始特徵之後，機器學習的設定沒有變，輸入照樣是一個向量，只是變成 256 維；變的是機器要學到東西的難度，通常會比較高。

有一個用詞上的小差別。課堂上口頭說 256 維的表示法比（對稱, 密度）「更抽象一些」，愈抽象對機器愈困難；講義的用詞比較嚴格，把這種叫 raw（意義單純），abstract 留給下一種幾乎沒有意義的輸入。

數值例子：同一個字的兩種表示法

以下是本文自擬的例子，不在講義上。把 16 乘 16 縮成 5 乘 5，只有黑（#，記 1）與白（.，記 0）兩種值。三個字：

「1」           「5」           寫歪的「1」
. . # . .       # # # # #       . # # . .
. . # . .       # . . . .       . . # . .
. . # . .       # # # # #       . . # . .
. . # . .       . . . . #       . . # . .
. . # . .       # # # # #       . # # # .

原始特徵。 一列接一列攤開，每個字是一個 25 維、只含 0 與 1 的向量。「1」是 $(0,0,1,0,0,\ 0,0,1,0,0,\ \cdots)$ ，「5」是 $(1,1,1,1,1,\ 1,0,0,0,0,\ \cdots)$ 。

具體特徵。 講義沒有給 symmetry 與 density 的算式，以下兩個定義是本文為了這個例子訂的：

density：黑格子的數目除以 25。
symmetry：把影像左右翻轉，數有幾格和原圖不同，除以 25 再取負號。完全對稱是 0，愈不對稱愈負。

逐一計算。「1」有 5 個黑格，左右翻轉後和原圖一樣。「5」有 17 個黑格；第 2 列 # . . . . 翻轉後是 . . . . #，最左與最右兩格不同，第 4 列同樣有 2 格不同，其他三列是對稱的，共 4 格。寫歪的「1」有 8 個黑格；第 1 列 . # # . . 翻轉後是 . . # # .，第 2 格與第 4 格不同，其他列都對稱，共 2 格。

字	density	symmetry	$\mathbf{x} = (\text{symmetry}, \text{density})$
「1」	$5/25 = 0.20$	$0$	$(0, 0.20)$
「5」	$17/25 = 0.68$	$-4/25 = -0.16$	$(-0.16, 0.68)$
寫歪的「1」	$8/25 = 0.32$	$-2/25 = -0.08$	$(-0.08, 0.32)$

這個結果代表什麼。 在具體特徵的平面上，兩個「1」都在對稱偏高、密度偏低的那一角，「5」在另一角，和講義那張散佈圖的方向一致。上一堂的感知器馬上能用：取 $h(\mathbf{x}) = \text{sign}(0.5 - \text{density})$ ，三個字的 $0.5 - \text{density}$ 分別是 $+0.30$ 、 $-0.18$ 、 $+0.18$ ，取正負號之後，兩個「1」得到 $+1$ ，「5」得到 $-1$ 。寫歪的「1」比標準的「1」更靠近分界，對應課堂上說的字寫不好會落在比較不對的位置。

在原始特徵那一邊，單獨一個維度幾乎看不出差別。正中央那一格（第 3 列第 3 行）在「1」和「5」裡都是黑的；25 格裡，這兩個字有 9 格的值完全相同。要從 25 個這樣的維度分辨兩個字，得靠很多格合起來的樣子。人看一眼想到「對稱」與「密度」，就是替機器做了這個合起來的動作，這是 including 'human intelligence' 的意思；不這樣做，就得靠機器自己從資料裡學出類似的組合。

抽象特徵：只有編號

第 26 頁的例子是 KDDCup 2011 的評分預測：

給定過去的 (userid, itemid, rating)，預測某個 userid 會給某個 itemid 幾分。
這是一個迴歸問題， $\mathcal{Y} \subseteq \mathbb{R}$ 是評分， $\mathcal{X} \subseteq \mathbb{N} \times \mathbb{N}$ 是 (userid, itemid)。
'no physical meaning'; thus even more difficult for ML。

課堂上說那一年比賽的題目是預測每個使用者會給每首歌幾分，分數如果是 0 到 100，輸出就是典型的有範圍的迴歸。輸入只有兩個編號，例如 257 號使用者給 1126 號歌曲幾分。二維的向量聽起來很好處理，但它和（對稱, 密度）那種二維向量完全不同：這兩個數字只是系統發給使用者與歌曲的編號。

講義列的其他例子：線上教學系統裡的學生 ID（KDDCup 2010）、線上廣告系統裡的廣告 ID。頁尾說 abstract: again need 'feature conversion/extraction/construction'。課堂上描述他們的做法：替每個使用者抽出他真正的特徵，例如一個描述他對歌曲喜好的向量；替每首歌抽出特徵，例如曲風或作曲者；再用這些特徵去學。這些特徵一部分是人想的，一部分是機器自己學到的。他要大家記住的是：輸入愈抽象，機器就要花愈大的力氣去找出能用的具體東西，問題通常也愈難。

數值例子：把使用者重新編號，預測就跟著變

以下是本文自擬的例子，不在講義上，用來說明「編號沒有物理意義」會造成什麼後果。三位使用者甲、乙、丙，兩首歌（歌 1、歌 2），已知五個評分，要預測丙給歌 2 幾分：

	歌 1	歌 2
甲	90	70
乙	50	30
丙	80	？

假裝編號是具體特徵，做一件最簡單的事：只看歌 2 這一欄，已知甲給 70 分、乙給 30 分。把 userid 當橫軸、評分當縱軸，畫一條通過這兩點的直線 $h(\text{userid}) = w_0 + w_1 \cdot \text{userid}$ ，再讀出丙的編號對應的值。使用者該編成幾號？系統先註冊的先編，本來就是任意的。試三種編法：

編號（甲, 乙, 丙）	通過甲、乙兩點的直線	對丙、歌 2 的預測
$(1, 2, 3)$	$110 - 40 \cdot \text{userid}$	$-10$
$(2, 1, 3)$	$-10 + 40 \cdot \text{userid}$	$110$
$(1, 3, 2)$	$90 - 20 \cdot \text{userid}$	$50$

驗算第一列：甲是 1 號、乙是 2 號，編號大 1，評分從 70 掉到 30，斜率是 $-40$ ；直線通過 $(1, 70)$ ，所以 $w_0 = 70 + 40 = 110$ 。丙是 3 號， $110 - 40 \times 3 = -10$ 。

這個結果代表什麼。 三種編法描述的是同一批人、同一批評分，預測卻是 $-10$ 、110、50，其中兩個連 0 到 100 的範圍都超出去了。原因是這個假說對 userid 做了加減乘除： $w_1 \cdot \text{userid}$ 的意思是「編號每大 1，評分就固定變 $w_1$ 」，把乙編成 2 號等於宣稱乙的口味介於甲與丙之間。這些都是編號帶進來的假資訊。具體特徵沒有這個問題，重量 6 確實介於 5 與 7 之間。

換一種表示法（本文補充的最簡單做法）：不用編號的大小，改成讓每位使用者各有一個代表他給分高低的數字、每首歌各有一個代表它受歡迎程度的數字，評分是兩者相加。從甲和乙看，歌 2 都比歌 1 低 20 分，於是丙對歌 2 的預測是 $80 - 20 = 60$ ，而且不管怎麼編號都是 60。「每位使用者一個數字、每首歌一個數字」就是最陽春的 feature extraction；課堂上說替使用者抽出的是一個描述喜好的向量，就是把這裡的一個數字換成一個向量。機器學習技法的後段有一堂專門處理這個問題：技法第 15 堂：矩陣分解的例子是使用者對電影的評分，講義同樣把使用者編號稱為 abstract feature，做法是替每位使用者、每部電影各學一個向量，用兩個向量的內積預測評分。

這一節的小結：容易的輸入是具體特徵

第 27 頁的清單：

特徵	物理意義
concrete	sophisticated (and related) physical meaning
raw	simple physical meaning
abstract	no (or little) physical meaning

最後一行是 . . . and more!!。頁尾寫 'easy' input: concrete。課堂上說，這門比較基礎的課會假設手上已經有具體的特徵；輸入是原始或抽象的資料時，通常需要人或機器想辦法抽出具體的特徵，那部分放在比較進階的地方。

Fun Time：線上圖片廣告系統

題目（第 28 頁）： 考慮建立一個線上的圖片廣告系統，把最相關的圖片顯示給使用者。你可以選用哪些特徵？

concrete
concrete, raw
concrete, abstract
concrete, raw, abstract

答案：4。 講義的解釋：concrete user features, raw image features, and maybe abstract user/image IDs。使用者的資料像顧客資料一樣是具體的；圖片本身有像素，是原始的；使用者與圖片在系統裡的編號是抽象的。

題目問的是「可以」用哪些，前三個選項各自少列了手上其實拿得到的一種，所以都不完整（本文的推理）。講義在 abstract 前面加了 maybe，表示編號用不用要看情況，但它確實可以用。課堂上從這一題延伸出一個觀察：大部分實際的應用裡，三種特徵通常都有；怎麼從這些不同的 $\mathbf{x}$ 裡找出一個好的表現方式，常常是機器學習能不能成功的關鍵。

這堂課的總結：四個軸合起來看

第 29 頁把四節收成一張表，每一個軸裡用方括號標出核心的選項：

軸	講義列的選項（方括號是核心）
Output Space $\mathcal{Y}$	[classification], [regression], structured
Data Label $y_n$	[supervised], un/semi-supervised, reinforcement
Protocol $f \Rightarrow (\mathbf{x}_n, y_n)$	[batch], online, active
Input Space $\mathcal{X}$	[concrete], raw, abstract

四個軸是各自獨立的，一個問題要在每個軸上各選一格。講義自己就這樣標過：第 16 頁把硬幣辨識寫成 batch supervised multiclass classification，第 23 頁再說它的（大小, 重量）是具體特徵，四個軸剛好標滿。把這堂出現過的幾個問題照同樣的方式整理（講義有明寫的照講義，括號裡是本文依題目敘述的判斷）：

問題	輸出	標籤	protocol	輸入
信用卡核卡	二元分類	（監督式）	（batch）	具體
硬幣辨識	多類別分類	監督式	batch	具體
手寫數字辨識	多類別分類	監督式	（batch）	原始，或轉成具體
KDDCup 2011 評分預測	迴歸	（監督式）	（batch）	抽象
會改進的垃圾信過濾器	二元分類	（監督式）	online	講義沒有說
Fun Time 的樹辨識系統	（二元分類）	半監督式	（batch）	（原始）
Fun Time 的棒球照片	（多類別分類）	一部分有標，其餘由演算法挑著問	active	（原始）

本文補充一個數字：光是講義四頁小結列出來的選項就有 $4 \times 4 \times 3 \times 3 = 144$ 種組合，而且每一頁都還寫著 and more。基石接下來主要處理的是其中兩格：批次、監督式、具體特徵的二元分類，以及批次、監督式、具體特徵的迴歸。課堂上的總結是，其他比較複雜的情形多半要先找出更具體的特徵，化回具體特徵的情形再處理；前面各節也分別說過，多類別與結構化的問題建立在二元分類與迴歸的工具上，非監督式與半監督式的方法借用監督式的概念，batch 的演算法容易延伸到 online。先把這兩格學透，是因為其他格子的方法大多從這裡長出去。

講義最後一行預告下一堂：next: learning is impossible?!。課堂上說下一次要先講一個壞消息：機器學習搞不好是做不到的，然後再看有沒有辦法解決。

自我檢查

1. 一家連鎖飲料店想預測每家分店明天會賣出幾杯。手上有過去三年每家店每天的銷量、當天的氣溫、是不是假日、有沒有促銷，都存在資料庫裡，一次全部拿來訓練，學出一個公式後固定使用。這個問題在四個軸上各是什麼？如果改成每天打烊後把當天的實際銷量交給系統、讓它調整公式，哪一個軸變了？

答案：輸出是杯數，數字的大小有意義，是迴歸（杯數不會是負的，可以看成有下限的迴歸）。每一筆過去的資料都有實際銷量，是監督式。資料一次給完、學出固定的 $g$ ，是 batch。氣溫、假日、促銷都是人挑過、有明確意義的欄位，是具體特徵。改成每天收到答案就調整，變的只有 protocol，從 batch 變成 online；其他三個軸不變。判準：四個軸要分開回答，並且各說得出一個理由。只答「監督式學習」只標了一個軸。

2. 詞性分成 4 種，句子固定 6 個字。把「整句的詞性串」當成一個類別，候選的類別有幾個？改成一個字一個字各做一次多類別分類，變成幾個問題、每個問題幾類？後者少了什麼？

答案：候選有 $4^6 = 4096$ 個。拆開之後是 6 個問題，每個 4 類。少掉的是字與字之間的關係：每個字獨立判斷時，沒有任何機制排除整體不合文法的組合（例如六個字全部標成動詞）。判準：要能說出結構化學習的輸出空間是「合乎文法的那一部分」，而且這一部分沒辦法逐一列出來。

3. 32 顆硬幣照重量排好，只有 1c 與 5c 兩種，前面一段是 1c、後面一段是 5c。真實情況是前 5 顆是 1c。用「每次問還不確定範圍的正中間」的方式（不確定的範圍記成兩端各多一格的區間，一開始是 0 到 33，每次問兩端相加除以 2、無條件捨去的那一顆），依序會問哪幾顆？共問幾次？

答案：一開始區間是 $(0, 33)$ ，問第 16 顆，答 5c，區間變 $(0, 16)$ 。問第 8 顆，5c，變 $(0, 8)$ 。問第 4 顆，1c，變 $(4, 8)$ 。問第 6 顆，5c，變 $(4, 6)$ 。問第 5 顆，1c，變 $(5, 6)$ ，兩端相鄰，換點確定在第 5 與第 6 顆之間。依序問 16、8、4、6、5，共 5 次，其餘 27 顆不用問。32 顆硬幣在這個問法下最多問 6 次。

4. online 的垃圾信過濾器目前的權重是 (−2, 0.5, 1)（含第 0 維）。接著來了三封信，特徵與使用者之後給的標籤依序是 (3, 0) 標 +1、(0, 3) 標 +1、(1, 0) 標 −1。照 online 版 PLA，每一封的預測是什麼？判錯幾次？最後的權重是多少？

答案：第一封補上 $x_0$ 是 $(1, 3, 0)$ ，分數 $-2 + 1.5 + 0 = -0.5$ ，預測 $-1$ ，標籤是 $+1$ ，判錯；修正成 $(-2, 0.5, 1) + (1, 3, 0) = (-1, 3.5, 1)$ 。第二封 $(1, 0, 3)$ ，分數 $-1 + 0 + 3 = 2$ ，預測 $+1$ ，判對，權重不變。第三封 $(1, 1, 0)$ ，分數 $-1 + 3.5 + 0 = 2.5$ ，預測 $+1$ ，標籤是 $-1$ ，判錯；修正成 $(-1, 3.5, 1) - (1, 1, 0) = (-2, 2.5, 1)$ 。共判錯 2 次，最後的權重是 $(-2, 2.5, 1)$ 。要注意順序：預測是在看到標籤之前做的，不能先看標籤再回頭改預測。

5. 用正文裡本文自訂的 density 與 symmetry 定義，算出下面這個 5 乘 5 的「7」的兩個特徵。把它交給正文裡那個只分 1 和 5 的感知器 h(x) = sign(0.5 − density)，會被判成什麼？這說明了什麼？

# # # # #
. . . . #
. . . # .
. . # . .
. . # . .

答案：黑格子有 $5 + 1 + 1 + 1 + 1 = 9$ 個，density 是 $9/25 = 0.36$ 。左右翻轉後，第 2 列 . . . . # 變成 # . . . .，有 2 格不同；第 3 列 . . . # . 變成 . # . . .，有 2 格不同；其他三列對稱。symmetry 是 $-4/25 = -0.16$ 。感知器算出 $0.5 - 0.36 = +0.14$ ，判成「1」。這說明具體特徵是針對特定任務挑的：密度與對稱夠分 1 和 5，放到十個數字的問題就不夠用，「7」的密度像「1」、對稱程度卻和「5」一樣。人挑的特徵帶著人對那個任務的知識，換了任務要重新挑。

練習與對應閱讀

對應的教科書章節。 Fall 2026 課程頁把這堂標在 Learning from Data（LFD）的 1.2 與 1.3。同一個課程頁把這堂的第一支影片（輸出空間）排在 W2 的課前必看清單，後三支排在 W3。

Fall 2026 extended slides（03e）的補充。 同一個課程頁的 03e_handout.pdf 在 MOOC 講義之外，替每個軸補了比較近期的例子：

輸出空間：multilabel classification（一張圖裡有哪幾種水果）、用 binary relevance 把它拆成多個是非題，以及影像生成（風格轉換、去噪、超解析度）。
標籤：self-supervised（拼圖任務）與 weakly-supervised（只給「不是哪一類」的 complementary label）；強化學習的例子換成 AlphaGo 與 GPT-3。
protocol：online 加上每日批次重新訓練的實務做法，以及台大 CLLab 的 active learning 工具 libact。

作業。 兩個學期的第一份作業各有這堂的題目，沒有官方解答，批改只限修課生。

Fall 2024 HW1 的 Q5–6：先問一個 chatGPT 類的 agent「active learning 可以用在哪裡」「ML 能預測地震嗎」，再用 10 到 20 句英文以「老闆」的立場批判它的回答。前一題直接用到這堂 protocol 那一節。
Fall 2026 hw1 的 Q5：台灣降雨圖預測屬於哪一種學習問題，練的就是這堂的四個軸。自我檢查第 1 題是暖身。

整份作業的導讀在基石作業導讀。

動手做。 挑三個你工作上或生活裡的問題，照這堂的四個軸各標一次，每一格寫一句理由。標不出來的那一格，通常就是那個問題真正難的地方：沒有標籤、標籤很貴，或者輸入只有編號。

這堂提到、之後才教的東西。 課堂上說抽取特徵的方法放在機器學習技法的後期；本文對照系列的堂次，深度學習在技法第 13 堂：深度學習，處理使用者編號這種抽象特徵的矩陣分解在技法第 15 堂：矩陣分解。基石裡最接近的是基石第 12 堂：非線性轉換，它教的是把已經具體的特徵再做轉換，不是從原始或抽象的輸入抽特徵。

延伸閱讀。 Caltech Learning from Data 是 Abu-Mostafa 用同一本教科書開的英文課。

下一堂。 基石第 4 堂：學習可行嗎從這堂最後留下的壞消息開始：只看有限的資料，憑什麼說 $g$ 在沒看過的資料上也接近 $f$ 。

課程影片來源

原始影片：Learning with Different Output Space、Learning with Different Data Label、Learning with Different Protocol、Learning with Different Input Space

查核日期：2026-10-13。影片 ID、標題與長度於當天從官方播放清單取得；YouTube 上沒有字幕軌，本文的課堂說法來自自行轉錄的逐字稿。

更新紀錄

2026-10-13：系列改為一堂一篇，這篇是新拆出的一堂，依講義與影片逐字稿寫成。

參考資料

基石第 3 堂講義 03_handout.pdf：本文的主要底本，四節的分類、每一類的例子、四題 Fun Time 與第 29 頁的總結都出自這份講義。
機器學習基石 YouTube 播放清單：四支影片的 ID 與標題；文中「課堂上」的說法轉述自這四支影片的機器轉錄逐字稿。
Hsuan-Tien Lin > MOOCs：官方講義與錄影入口。
基石第 2 堂導讀：online 版 PLA 的判錯上限沿用那一堂的兩個事實與記號。
Machine Learning, Fall 2026 課程頁：W2、W3 課前必看清單與 LFD 章節。
Lecture 3 extended slides（03e_handout.pdf）：四個軸上的近期例子。
Fall 2024 Homework 1（hw1_red.pdf）：Q5–6 的題目內容。
Fall 2026 Homework 1（hw1.pdf）：Q5 的題目內容。
libact: Pool-based Active Learning in Python：03e 提到的 active learning 工具。
Learning from Data 教科書網站：1.2 與 1.3 的出處。
Caltech Learning from Data：延伸閱讀，同一本教科書的英文課程。
台大林軒田機器學習基石與技法導讀：課程總覽：整門課的位置與閱讀路線。

學習的種類：依輸出、標籤、資料取得方式與輸入來分｜台大林軒田 機器學習基石 第 3 堂