林軒田機器學習基石筆記 - 第三講、第四講

發表於 更新於 分類於 ， 閱讀次數： Disqus：

機器學習基石第三講 : Types of Learning
機器學習基石第四講 : Feasibility of Learning**

  • 本篇所有圖片部分由筆者製作，其它均為機器學習基石課程內容講義

Types of Learning

在前文中，我們介紹了一種最簡單的機器學習模式 : 簡單二元分類 (Perceptron) ，但機器學習的型態非常多，以下我們從輸出空間Output Space、目標標籤Data Lable、處理資料的方式Protocol以及輸入空間Input Space這幾個面向來討論

Output Space

  • Binary classification : $\mathbb{y}\in\left{+1,-1\right}$
    許多的ML理論推導均由 binary classification 出發

  • Multiclass classification : $\mathbb{y}\in\left{1,2,3,4,…,k\right}$
    $1,2,3,4,…,k$ 為多種目標的「編號」，並非目標就是 $1,2,3,4,…,k$

    以 Classify US coin by size & mass 為例
    $\mathbb{y}\in\left{1c,5c,10c,25c\right}$ or $\left{1,2,3,4\right}$

    binary classification 為 k=2 時的特例

  • Regression : $\mathbb{y}\in\mathbb{R}$

  • Structure Learning : $\mathbb{y}\in\left{Structural\ Sequence\right}$

    $\mathbb{X}:\left{詞\right}\rightarrow\mathbb{Y} :\left{詞性\right}$ Multiclass classification
    $\mathbb{X}:\left{句子\right}\rightarrow\mathbb{Y} :\left{結構\right}$ Structure Learning

Data Label

  • Supervised Learning ( 監督式學習 ) :
    其實就是 Multiclass classification $\mathbb{y}\in\left{1,2,3,4,…,k\right}$

  • Unsupervised Learning ( 非監督式學習 ) : $unknown\ \mathbb{y}$

    在 Classify US coin by size & mass 例子中，若不告知電腦目標值為多少，而讓其自行進行分類判斷，即為 Unsupervised Learning

    像 Clustering (分群)、Density estimation (密度估計)、Outlier detection ( 異常偵測 )均為 Unsupervised Learning範圍

  • Semi-supervised Learning ( 半監督式學習 ) :

    在 Classify US coin by size & mass 例子中，若僅告知某幾個資料的分類為何，其餘讓電腦自行判斷，便為Semi-supervised Learning

  • Reinforcement Learning ( 增強式學習 ) :
    $\mathbb{y}$ 仍不明確，但每一筆輸出都給予電腦回饋，讓系統逐漸學習者稱之。
    增強式的學習是序列性、逐筆的學習，而前面的其它學習法幾乎都是整個資料集一次餵進去給電腦。

Protocol

  • Batch Data
    將資料成批的餵給電腦進行學習，學習出一個固定的 $g$
  • Online Data
    類似 PLA / Pocket 概念，資料不斷進來，電腦也不斷地調整 $g$
  • Active Learning
    系統會主動向使用者進行提問而來進行優化 $g$

Input Space

  • Concrete Feature
    $\mathbb{X}$ 中帶有具體的描述 / 特徵稱為 concrete feature $x_i$，通常由 domain knowledge 決定

  • Raw Feature

    EX: 手寫辨識
    將每一個手寫字分為256個畫素 ，依程度賦予其數值 $\mathbb{X}\in\mathbb{R^{256}}$

  • Abstract Feature
    特徵不具體 – 像是USER_ID , Rating 或 item_ID - 因為沒有「物理」上的意義，因此這樣的問題在ML中相對困難。

Feasibility of Learning

討論機器學習的可行性，我們就從講義的這一個例子開頭吧!

這樣的例子在一般的智力測驗中算是非常常見的題型之一，但是，好像都不會有人質疑這樣的題目是不是真的唯一解 ?[^註1]

若從上面的例子來看，$g(x)=+1 或是 -1$都是很合理的推測。

這下糟糕了!

那我們怎麼確保機器學習出來的模型可以被侷限住達到有效的預測 ? 而不會預測出來有無限多種可能性 ?

Probability & error

課程走到這，其實會覺得突然引進機率概念會覺得有點突兀、難理解。但是其實並不然，現實生活任何事件都是充滿機率概念，機器學習也不例外。

我們手中有的 dataset 的取得以及分布、雜訊的生成、Model對未來資料的擬合精確度…等也都跟機率有關，所以在機器學習的研究進程中會將機率引入相對來說算是合情而且合理的。有了機率的概念，這表示不會百分之百精準，這時error的概念也會隨之而生。

OK，既然可以理解了這兩個概念在機器學習理論上的定位後，就可以來討論上面的問題 :「機器學習的可行性在理論上的保證」

Hoeffding’s Inequality

給定某事件在母體中機率 $\mu$，現有一抽樣，其樣本數 $N$，此事件在樣本中機率$\nu$
則 $\mu\ 與\ \nu$之誤差大於 $\epsilon$ 的 機率不會超過 $2e^{-2\epsilon^2N}$
$$\mathbb{P}(|\mu-\nu|>\epsilon) \leq 2e^{-2\epsilon^2N}$$

我們把上面這樣的一個概念跟機器學習做一個類比:

抽球 ML
給定一個Bin，裡面裝滿綠球跟橘球 給定一個$h$，及一個Dataset $\mathbb{D}$
Bin內抽中橘球的機率為$\mu$，樣本內抽中橘球的機率為$\nu$ 在$\mathbb{D}$以外的資料中，$h(\mathbb{X})\neq f(\mathbb{X})$ 的機率為$E_{out}(h)$，在$\mathbb{D}$中的資料中，$h(\mathbb{X})\neq f(\mathbb{X})$ 的機率為$E_{in}(h)$
$\mathbb{P}(\mid\mu-\nu\mid>\epsilon) \leq 2e^{-2\epsilon^2N}$ $\mathbb{P}(\mid E_{out}(h)-E_{in}(h)\mid>\epsilon) \leq 2e^{-2\epsilon^2N}$

從 Hoeffding’s Inequality 可知道 :
樣本的數量 $N$ 越大，$2e^{-2\epsilon^2N}$會越小$\implies$$\mu$ 與 $\nu$ 會越接近 ( $E_{out}(h)$ 與 $E_{in}(h)$ 會越接近 )
只要 $E_{out}(h)$足夠小， 我們便可以宣稱 $h$ 與 $f$ 夠接近了。

看起來好像沒問題了?

上述的理論出發點是「給定一個 $h$ 」，然而我們的 Hypothesis Set $\mathbb{H}$裡面可不只裝一個 $h$ (可能 finite ,也可能 infinite) ，如何在這眾多的 $h_k$ 中選擇一個表現最好的來當我們要的 $g$ ?

我們一樣先從單一的 $h$ 來看 Hoeffding’s Inequality的意義是什麼?

$D_k$代表的是母體中採樣樣本數量為 $N$ 的各種採樣組合

Hoeffding告訴我們，只要採樣樣本數為 $N$ ，那麼「不好的採樣」
( 意即$E_{out}(h)-E_{in}(h)\mid>\epsilon$ ) 的機率一定會有一個上界 $2e^{-2\epsilon^2N}$，從上圖來解釋，其實就是BAD的機率會有上界 $2e^{-2\epsilon^2N}$

那麼把所有 hypothesis $h_k$( 假設 $\mathbb{H}$ 為有限集 )攤開來看

在所有的 $h_k$ 之中，真正一個「好的採樣」，應該是不管機器選到哪一個 hypothesis $h_k$ ，都仍然是一個「好的採樣」 ( 意即$E_{out}(h)-E_{in}(h)\mid<\epsilon$ )。上圖的 $D_{1126}$便是一個如此的「好的採樣」。

那我們仍然從 Hoeffiding’s Inequality的角度來看 :

$\mathbb{P} (|E_{out}(\mathbb{H})-E_{in}(\mathbb{H})|>\epsilon)$

$=\mathbb{P} ((|E_{out}(h_1)-E_{in}(h_1)|>\epsilon)\ or\ (|E_{out}(h_2)-E_{in}(h_2)|>\epsilon)\ or\ …or(|E_{out}(h_M)-E_{in}(h_M)|>\epsilon))$

$\leq\mathbb{P} ((|E_{out}(h_1)-E_{in}(h_1)|>\epsilon)\ +\ (|E_{out}(h_2)-E_{in}(h_2)|>\epsilon)\ +\ …+(|E_{out}(h_M)-E_{in}(h_M)|>\epsilon))$

$\leq2Me^{-2\epsilon^2N}$

所以我們可以得到以下結論 :
M 為有限數 , N夠大 ，$E_{out}(h)$ 與 $E_{in}(h)$ 會夠接近
$\implies$ M 為有限數 , N夠大 ， $E_{in}(h)\rightarrow0$，則 $E_{out}(h)\rightarrow0$
$\implies$ 機器學習中，只要 M為有限數，樣本數夠多，我們盡可能的 找出$E_{in}(h)\rightarrow0$，則便可確保$E_{out}(h)\rightarrow0$

註釋

[^註1]:
還有一種很常見的題目「1=2；2=4；3=8，請問4= ?」
大家正常都會非常快速的回答出「16」，而答案通常也是如此。
假設有一個函數 $f$ 滿足上面的條件，$f(1)=2，f(2)=4，f(3)=8$
從座標的角度來看可以看做給定三點$(1,2) , (2,4) ,(3,8)$求過第四點$(4,y)$的曲線，
從這裡不難發現，給定任意四點，我都可以求出一個四次方程式$f(x)=ax^3+bx^2+cx+d$通過這四點，
也就是說，不管我們給定哪一個$y$值，都一定可以找到一個(或以上)的 $f$ 來對應。