Machine Learnng 1.1 -- Perceptron -- 什麼是 machine learning 問題

如果有上過林軒田老師的課，他在課堂的一開始一定會先提到 perceptron learning algorithm (PLA)。這是一個最簡單，最好應用，涵蓋範圍可以很廣，但效果卻不會太差的演算法。我想在真正提到SVM之前，先用PLA來給大家進一步熟悉machine learning的問題。

我在上一個段落有說到machine learning的概念，這樣的概念我們可以用一個比較一般性的描述來表示。

為了找到未知的公式 $f: X \rightarrow Y$ ，我們必須要從資料集(Data set) $ D: (x_1,y_1) (x_2,y_2) ... (x_n,y_n) $ 中，利用演算法 $A$ 產生一個假說集 (Hypothesis set) $H: h_1(x), h_2(x) ...$ ，並想辦法從 $H$ 中挑一個我們心目中最接近 $f(x)$ 的假說，一般而言我們會用$g(x)$來表示那個從$H$雀屏中選的那個。

/* 以下廢話

上面那一段用白話文來說就可以講一大堆了，以前在看大學工數課本的時候，都覺得外國人寫的書廢話好多，我只要看得懂公式就好，不過這幾年下來，我有時候會覺得學數學的重點就是，可以從公式中領會出那些廢話。公式是一個結論，是思想的精華，不過對數學而言，我們需要花很多時間來思考問題，界定問題，這樣才能真正應用在這個世界上。

先來看 $f$ ，什麼叫做未知的公式，其實可以把它看作是一個最終目標，這樣的目標可以是一個判斷，一種預測，甚至是比較抽象的想法。比如說：

這張相片中有沒有人臉? (二元分類問題)
輸入：圖片
輸出：true / false

身高175公分的人走一步的距離大概是多少？ (回歸問題)
輸入：身高
輸出：步長

這位網路商城的使用者可能會喜歡哪種廣告？(比較抽象的問題)。
輸入：歷史紀錄
輸出： 可能喜歡的廣告

這些問題是無法憑空找出答案的，不管是人也好，機器也好，要找出這些問題的答案都必須經過學習過程。學習就是透過資料、教材或範本找到答案，也就是說從一群資料中萃取出我們要的東西，那個萃取出來的公式 一般我們會用 $g$ 來表示。

換句話說，這件事可以拆成兩件事來看 1)要如何利用手上的資料找出 $g$ ，並且 2)確保 $g$ 跟 $f$ 很接近。

1) 如何利用手上的資料找出 $g$: 
這時後 $A$ 就出場了，我們可以用很多種方法來找 $g$，每一種都是 $A$ 的子集，這些方法作用在資料上，就會出現其對應的假說 $h$ ，每一種方法至少會有一種假說(註)，這些假說的集合 就表示為 $H$。

每個 $h$ 的功用就是越來預測資料，資料是由一群這樣的東西 $ D: (x_1,y_1) (x_2,y_2) ... (x_n,y_n) $所組成的，其中的 $x$ 就是所謂的特徵，也就是上面的 "輸入" ，可以是圖片，可以是身高，可以是歷史紀錄或是任何想用來學習的特徵；而 $y$ 就是 "輸出"，也有人把他們叫做 "標籤" ， 他標示著我們想要電腦學習的結果，也就是我們會希望那個好的 $h$ 會出現，並且讓所有的 $h(X)$ 都接近甚至等於 $Y$。

註：一般來說，我們會把同一種方法，但使用不同的參數的結果，定義為不同的 $h$，換句話說，一個 $a$ (俗稱演算法)，可能會產生多個 $h$。

2) 如何確保 $g$ 跟 $f$ 很接近:
在 $H$ 裡面，要知道其中的好壞很簡單，就是把所有在 $D$ 中的 $x_1, x_2, x_3 ...$ 都帶到 $h_i$, ( $i=1,2, ... ,n$ $假設有H中有n個假說$ ) 裡面，然後再將每一個輸出 $h_i(x_1)$, $h_i(x_2)$, $h_i(x_3)$, 與 $y_1, y_2, y_3...$ 比較錯誤率最低的，在小心 overfit(註) 的情況下，我們可以說 $g$ 接近 $f$，只要有類似的資料進來，我們就可以用手上的 $g$ 來完成 $f$ 所描述的問題。

註：overfit 是過度學習的意思，一般而言可以看做是不只有用的資料本身，連雜訊也完全學習。也就是說，雖然可以百分之百呈現當前的資料，但往往這個找到的 $g$ 是沒有應用價值的。

以上廢話  */

這就是我所知道的machine learning的問題，簡單用一句話來說明就是，如何從資料中找到我們心中想知道的答案。

Machine Learning 0 -- What is SVM?

前面的課程主要是在講SVM(Support Vector Machine)，本來這篇兩個禮拜前就應該發的，不過很多事讓我一拖再拖，我希望以後可以以兩個禮拜一篇的速度完成，有點像是自己對這個領域的小筆記。

SVM 是一種 Machine Learning 的演算法，照字面上的意思來看，就是"利用 support vector 來分類的 machine"。

在了解這句話之前，我們先來看一個簡單的圖

取樣資料

一般來說，machine learning 的目的是從取樣資料(手上有的看得到的資料)中預測一個可以描述全域資料(不知道長怎樣，不過大概跟取樣資料長得很像)的方程式 $f(x)$，換句話說$f(x)$是學習的最終目標；以上圖為例，我們可以用任意直線、圓錐曲線甚至是不規則圖形來分開他們，每一個圖形都是一個假說(hypothesis)，以$h_i(x)$表示，當我們使用不同的 machine learning 演算法 (或者是使用同一種演算法但不同參數)，就是用不同的選妃標準來選擇一個最適合的假說，被挑選出來的妃子假說我們會讓他進化成皇后$g(x)$，$g(x)$就是我們的預測值，我們會希望$g(x)$非常接近世界上最完美的皇后$f(x)$。

圖上的三條線都可以分開兩群資料，所以我們都可以把它們看成假說。

現在我們回到那句話："SVM 是利用 support vector 來分類的 machine"。SVM 挑選假說的方式就是去尋找 support vector，並且以 support vector 為基準來分類。這句話從字面上完全無法了解它的意函，所以有另外一個比較通俗的說法:

找到一條可以分類的線，而且這條線所在的區域擁有兩群資料間最大的邊界。

找到一條可以分類的線，而且這條線所在的區域擁有兩群資料間最大的邊界。

找到一條可以分類的線，而且這條線所在的區域擁有兩群資料間最大的邊界。

因為很重要所以要說三次

如下圖，如果假說都是直線的話，SVM 就是要找到一條線離左右兩群資料間的區域最大。

中間的區域就像是緩衝區一樣，到左右兩邊的緩衝區越大，就有很大的機會容忍取樣上的誤差。

好啦，現在問題就來了，兩群資料可以分就好幹嘛這麼龜毛，還要找最大的邊界？

其實這很直覺！撇開數學（shatter, vc dimension）不談，要確保 machine learning 出來的結果正確，最重要的就是兩件事，1）取樣的資料要好。2）演算法要挑剔。

對我個人來說，好的取樣資料是最重要的，因為我們不可能把世界上所有的資料都拿來用，所以我們只能取其中有代表性的資料出來算，如果取得不好，就算使用世界 上最強的演算法也算不出符合原始資料的結果。就像是要去分析交大學生的習慣，如果全部都在竹軒、女二舍裡面調查的話，就會有交大是女校的錯覺，在這樣的錯覺下，任何對於此資料做出的分析找到的$g(x)$一定會跟$f(x)$相去甚遠。

不過就算是再好的取樣，取出的資料也不能100%代表著母體，而這時候使用演算法就要特別小心。在 machine learning 裡面，演算法決定了$h_i(x)$的產生方式，以及選擇$g(x)$的標準。如果產生$h_i(x)$的方式不挑剔，不管三七二十一，只要能夠把當前這筆資料完美的處理就好，很容易會學過頭了，也就是說好得學壞得也學，連那些誤差都學得淋漓盡致，一般正式的文章裏面都把這個叫做 over fitting。為了避免 over fitting，最簡單的方式就是對演算法設下條件，而SVM的條件就是，要找最大的邊界。

到這邊就是簡單的 machine learning 以及 SVM 的概念。

Machine Learning Course

今天從以前學長的FB發現，台大林軒田老師有一個機器學習的開放式課程「機器學習技法」，我在研究所的時候有修過他的課，是一門充滿著紮實的學問、困難的理論以及寫不完的作業的課。

雖然如此我還是報名了這個開放式課程，所以接下來，我會在這個部落格分享我上課的心得，以及技術面的東西。