# CS156_Machine Learning Course Lecture 01 - The Learning Problem
###### tags: `CS156` `Machine Learning`
[撥放清單](https://www.youtube.com/watch?v=mbyG85GZ0PI&list=PLD63A284B7615313A)
[課程連結](https://www.youtube.com/watch?v=mbyG85GZ0PI)
## Outline of the Course
- [ ] 0.36

上面是這個課程七大綱，不同的顏色代表著它是偏應用還是偏數學的課程。

機器學習包含的非常廣泛，除了抽象的理論，也函蓋著經驗法則的實踐。每一個課程的主題都取決於與機器學習的相關性來說明。

- [ ] 2.56

不管你信不信，Learning from data這本書的右下的這個圖形並不是一個藝術品，而是一個工程圖形，後面還會再出現。

這有點像屁屁偵探，後面會有四個紅色屁屁，大家要注意。

## Example: Predicting how a viewer will rate a moive
- [ ] 7.25

課程給出的第一個範例是，觀眾如何幫一部電影打分數?以Netflix為例，在登入系統的時候Netflix就會提供給你他們覺得你會喜歡的電影，這樣你就會滿意他們的服務。因此Netflix希望可以提高現有的系統10%的效能。

提升Netflix10%效能值多少?答案是100萬美金，這是當初舉辦競賽第一名的獎金，看起來似乎很大的金額，但是如果這個提升是有效的，那可以為Netflix帶來大筆的收入。即使是金融系統中的微小改變都可以賺來大筆金財。因此，利用機器學習來改善系統在各種應用中都非常有吸引力。

想要利用機器學習來改善一件事要有三個要素：
1. 一個既存的模式，如果不存在任何模式那就無跡可尋。以上面的推薦系統為例，一個人評價一部電影會跟他怎麼評價其它部電影有關，也跟其他人怎麼評價那部電影有關，這就是模式
2. 沒有辦法將模式數學化寫出來，因此我們需要機器學習，Learning from Data，利用資料來找出這個模式
3. 我們需要資料，從資料中學習，Learning from Data

## Movie rating - a solution
- [ ] 8.15

這邊給出剛才所說的電影推薦。我們將一位看電影的觀察(viewer)以向量來表示(記錄這元素的向量或許可以很長)，或者你可以把這個viewer當做自己來記錄。舉例來說，第一維是記錄這個觀眾是否喜歡喜劇片，第二維記錄是否喜歡動作片...等等，甚至記錄是否喜歡Tom Cruise演的片子。

- [ ] 8.46

接下來我們轉換角度，從電影的角度出發，找相對應的元素，這電影是否存在喜劇的元素，是否存在動作片的元素，或者是否為阿湯哥所主演。

這時候你會發現，如果從用戶與電影的角度能夠互相匹配這些相對應的元素，那就可以知道用戶是否喜歡這部電影。舉例來說，也許用戶喜歡動作成份多一點，喜劇成份少一點，但某部片可能喜劇成份很多，但沒有動作特技，那用戶可能就不喜歡這部電影。

但這並不是機器學習，因為你為了要有這些資料你要去看電影，然後要去問每一個觀眾他們對電影的喜好，然後合併得到的資料再來試著得到你想要的預測。我們希望的是機器自己學習。

## The learning approach
- [ ] 12.19

我們剛才已經說過了，我們有viewer的向量，也movie的向量資訊，整合之後得到一個評分，再利用機器學習來做逆向工程。也就是利用評分的結果回頭找出與評分結果有相關性的因素。

讓viewer跟movie的向量值都是隨機初始化，然後做內積，想當然這跟實際的評分一定會有很大的落差，然後我們利用機器學習讓這些隨機因素內積之後的結果接近實際評分的結果。這其中的關鍵就是就是你需要的不是一個評分，而是很多的評分資料。然後在這些評分資料裡面不斷的迭代循環計算，最後你會發現一開始隨機初始化的這些向量內的元素結果會變的有意義。這就是機器學習做的事情。

## Components of learning
- [ ] 14.01

從剛才的範例我們進入學習的要素，從遇到的學習問題中歸納出構成學習問題的數學組成部份有那些。

我們利用另一個案例來說明，銀行發行信用卡。銀行發卡要的就是可以賺錢，但銀行並不認識申請卡的人，銀行唯一有的就是過往申請的歷史資料，利用這些資料弄出一個系統，再以此系統的結果應用於新的用戶身上。

因此，組件的部份可以看到，可能會有申請信用卡的人員的個人信息，年齡、性別、收入…等等。即使這並不是一個絕對相關的資料，也是一個相對相關的資料。用這些資料做為input，以此決定是否發卡。

- [ ] 17.56

形式上來看，我們會有：
1. input：$x$，也就是剛才的客戶信息，向量資訊
2. output：$y$，判斷是否發卡或是否提供貸款
3. target function：$f: \mathcal{X} \to y$，從$\mathcal{X}$映射到$y$的函數，這個$\mathcal{X}$所指是該domain內的所有$x$，是一個$d$維向量的集合。而$y$則是co-domain，目前範例來看是$\pm 1$，而這個target function就是那個決定是否發卡或借款的函數
4. data：$(x_1, y_1), (x_N,y_N)$，data pair，以上面的範例來看就是申請者的信息以及最後是否發卡或撥款的資料組
5. hypothesis：$g:\mathcal{X} \to y$，用來近似target function，$f$是未知，而$g$是差不多已知，我們希望它可以接近$f$

要注意的是，在機器學習中，target function對我們來說都是未知的，因為如果是已知的，那也沒有必要學習。正因為是未知才會需要學習。而當你有足夠的資料量的時候，你就抓的住這個target function。而抓住target function的方式就是用hypothesis-$g$來近似target function-$f$。這就是學習的目標。

- [ ] 19.22

上面以圖表來看，有一個我們很想得到卻又未知的target function，但我們唯一能看到它的方式是透過資料集，也是唯一能用來觀察target function的方式。我們希望得到的就是最終的hypothesis，也就是銀行用來決定要不要發卡的$g$，而連結這兩個function的就是learning algorithm，$\mathcal{A}$。學習演算法利用資料集得到最終的hypothesis。

另外有一個部份是指向學習演算法的，學習演算法會依據預設的一組候選模型來建立公式，我們稱之為hypothesis set，$\mathcal{H}$，$\mathcal{H}$裡面有著許許多多的hypothesis $h$，而其中一個被選中的就成了最終的hypothesis，也就是$g$。

這邊我們可能會疑問，為什麼需要一個hypothesis set?為什麼不讓演算法隨意挑選就行，隨便一個公式就可以隨便來一個$g$，而一定要從這個$\mathcal{H}$中選一個?

這麼做沒有壞處的原因在於，當你提到你要用線性函數、神經網路或是SVM等演算法的時候，這已經是一種hypothesis，這就是我們現在在做的事。當你沒有任何的假設的時候，那你的hypothesis set就是所有可能的hypothesis。因此我們說加入這個hypothesis set沒有任何的壞處。

而好處在於，hypothesis set在學習理論中有著關鍵的作用，它可以告訴我們是否可以學習以及學習效果如何，可以讓理論更加完善，愈後面的課程會愈有感覺。

## Solution components
- [ ] 23.08

這邊說明兩個solution components：
1. hypothesis set，以$\mathcal{H}$來表示，每一個hypothesis都以$h$來表示，而最終的hypothesis以$g$來表示，而$g\in\mathcal{H}$，也就是我們從這個hypothesis set裡面眾多的$h$找一個來當最終的hypothesis
2. learning algorithm

當你將hypothesis set與learning algorithm放在一起的時候，它們就被稱為learning model，也就是學習模型。也就是任一個模型都會有對應的hypothesis set，然後會有一個演算法從這個hypothesis set找出一個結果。

## A simple hypothesis - the 'perceptron'
- [ ] 26.23

這邊給出一個perceptron的範例，假設有一個輸入，$x=(x_1, \cdots, x_d)$，$d$維的資料且皆為實數(real number)，這是一筆關於客戶記錄的feature，可能有著客戶的收入、性別等等資訊。

perceptron做的計算很簡單，就是$\sum^d_{i=1} w_ix_i > \text{threshold}$，其中$x_i$為一筆輸入內的其中一個維度，也就是其中的一個feature，而$w_i$則是相對應feature的權重(weight)。重要的feature，其相對應的weight就會比較大，反之則較小。

就這樣，將每一個feature與相對應的weight相乘之後加總，就組成perceptron，事實上就可以拿這個結果來計算像是信用評分之類的應用，只要加總之後的值大於閥值，那就可以發信用卡，反之則拒發。

目前為止雖然還不知道如何求解，但已經有一個目標函式，接下來套入稍早所提過的流程，這個linear formula $h \in \mathcal{H}$可以寫成：
* $h(x) = \text{sign}\left(\left(\sum^d_{i=1}w_ix_i \right) - \text{threshold}\right)$

這跟上面提的沒不一樣，只是寫的看起來比較正式一點，只要加總之後的值大於閥值，那就是正數，那信用卡或貸款申請就通過，那[sign function](https://zh.wikipedia.org/zh-tw/%E7%AC%A6%E5%8F%B7%E5%87%BD%E6%95%B0)的輸出就會是$1$，反之則輸出$-1$。

從上面的計算不難看出，這個hypothesis的輸出是取決於$w_i$與閥值，因為你的$x_i$是固定的，而是否放款或核發信用卡是你的資料集內也已經確定的結果，因此會異動的就只有$w_i$與閥值，不同的搭配就是不同的hypothesis。

- [ ] 29.13

用圖形來觀察這個hypothesis，假設這個資料集是線性可分的，圖上可以看到9個資料點，我們希望新的客戶不管好壞都可以正確的辨別。

一開始的權重是隨機初始的，所以效果可能不是那麼好。因此可以看到圖上的紫線其實就是與權重還有閥值相關的，不同的權重與閥值就產出不同的線，演算法做的事情就是找一條好的線來最最佳化資料集的分割。

現在我們要調整剛才的數學式，將減去threshold以加上$w_0$來替代，然後加入一個常數$x_0=1$，這並不是原本feature內的一個維度，這麼做的好處在於可以減化數學式變成：
* $h(x) = \text{sign}\left(\sum^d_{i=0}w_ix_i \right)$

減化之後的求解就可以變成只是一個簡單的內計計算：
* $h(x) = \text{sign}(w^Tx)$

這個$h(x)$就是hypothesis set，因為不同的weight就會有不同的hypothesis。有了這個hypothesis set就可以找相對應的演算法來從中選出一個最終使用的hypothesis。

## A simple learning algorithm - PLA
- [ ] 32.30

上面所說明的就是整個perceptron的作法：
1. 有著一個hypothesis set $h(x) = \text{sign}(w^Tx)$
2. 給定訓練集

演算法會試著去取得正確的$w$，因此當有一個資料點分類錯誤的時候就意謂著找到的$w$可能不是那麼好，也就是$\text{sign}(w^Tx_n) \neq y_n$。

所以當有資料分類錯誤的時候，演算法就會試著調整權重$w$，剛才說過，只要$w$不一樣，那就是一個新的hypothesis，也就是$w \leftarrow w + y_nx_n$。

當兩個向量($w, x$)組成是一個銳角的時候，sign function的output就會是$1$，反與當兩個向量組成一個鈍角的時候，那sign function的output就會是$-1$。所以有資料分類錯誤的時候就意謂著該筆資料在銳角的時候sign function的output是$-1$，鈍角的時候output是$1$

| Sign function | 正確 | 錯誤 |
| :--------: | :--------: | :--------: |
| 銳角 | $1$ | $-1$ |
| 鈍角 | $-1$ | $1$ |

可以看右上角的$y=+1$的圖，為什麼更新參數的時候會是$+y_nx_n$，當它$y=1$的時候應該是一個銳角，但分類錯誤，因此它是一個鈍角，加上$y_nx_n$之後(事實上就是加上$x_n$，因為$y_n=1$)會把它拉回，變成銳角。右上角的$y=-1$也是類似的概念可以說明。這是一個比較直觀的說明。

## Iterations of PLA
- [ ] 34.26

這邊說明的是perceptron learning algorithm的迭代過程。上圖可以看的到，有一個藍色點被分類錯誤，所以接下來演算法就會調整權重，讓線可以正確的分類該點，不過這麼做之後可能上面的紅色資料點就會變成錯誤被階郋至藍色區域。

整個迭代過程就是從$n$筆資料集中取出一筆標記錯誤的資料，然後更新權重，也因此在更新一筆資料的時候並沒有去考慮到其它的資料是否也會受影響。只要資料要是線性可分，那你只需要耐心的執行這個演算法，最終是確實可以收斂的。

現在已經有一個模型可以用來分類，只是目前為止並不確定這樣做是否可以應用在新的客戶上，因為這是利用現有資料所建構而成的模型。

## Basic premise of learning
- [ ] 38.42

在進行下一步之前要先有一個觀念，那就是"using a set of observations to uncover an underlying process"，也就是我們用著一組稱為資料的觀察集來揭露出一個潛在的過程，也就是我們所說的目標函數(target function)。

如果是在統計學的角度，這個潛在的過程就是一個機率分佈，而觀察集就是從這個分佈中所生成的樣本，利用這個樣本來預測它們的機率分佈。

學習的方式主要三種型態：
1. Supervised Learning，也是課程中主要會說明的
2. Unsupervised Learning，課程中會討論到一個著名的演算法
3. Reinforcement Learning，會簡單的介紹到

## Supervised learning
- [ ] 40.39

監督式學習(Supervised Learning)，你的資料有著明確的輸出，像是這個客戶是否能不能放款，這個電影的評價如何之類的，能不能放款跟電影的評價就像是有一個監督者(supervisor)在幫忙你區分這資料。

上面給出一個硬幣辨識的案例，以重量與大小做為特徵，分佈就如上圖，以不同的顏色標記，給出重量與大小，告訴你這是什麼樣的硬幣，因此是一個監督式學習。

當你使用線性可分的演算法來演算法來訓練模型的時候，可以得到三條線，然後你就不再需要這些資料了，當有人投幣，只需要判斷它是屬於那一個區域就可以知道這個硬幣是屬於那一種幣值。

## Unsupervised learning
- [ ] 42.41
- [ ] 42.28

非監督式學習的資料本身並不會有結果，就單純的資料分佈，所以你不會知道那一個資料點是屬於那一種的幣別，意思就是只會有單純的input，不會有correct output。

但這沒有關係，從分佈圖中還是可以看的出資料點聚集在一起的趨勢，我們可以利用這一點來做聚類，一樣可以得到分界線，這樣就夠了。但要注意的是，左下的部份其實並沒有很明顯的可以分成兩群，因此在非監督式學習中，聚類的數量是比較不好定義的。

## Reinforcement learning
- [ ] 49.10

強化學習，不會有完整的輸入、輸出，只會有輸入跟某些的輸出，而這個輸出並不是正確的輸出，只是一個輸出，然後再對這個輸出做評分。這好比一個小孩正在學爬，手去摸一個裝熱茶的杯子，一碰就熱，這小孩會記得這個熱，然後下次就可能不會直接碰，而是開始依著幾次被燙手的經驗學到要看一下杯子是不是有冒煙來決定要不要碰。一個強化學習很重要的應用領域就是玩遊戲。

## A Learning puzzle
這邊給出一個學習的範例，給出六個資料，看看下面的那一個輸入應該是-1或是+1。個人猜+1，但這個分類是一個不可能的任務，因為目標函數是一個未知的函數，它可以是任意函數。

我們可以看左上角的點，如果輸出是-1，每一個點都是黑的，如果輸出是+1，每個點都是白的。所以如果用這個點來觀察，那輸出就會是-1，如果你看對稱性，那輸出就會是+1。因為下圖的輸入一次符合這兩個特性。像這樣子的問題比比皆是，但這並不意味著學習是不可行的。

我們知道，目標函數是一個未知函數，我們只擁有著有限的樣本，然後利用這個有限樣本去瞭解樣本外的資訊。這是學習的本質，如果只是為了單純的記住給出的例子，那叫做記憶而不是學習，學習是為了找出一個一般性的模式。

## QA
Q1：如何確定一個資料集是否為線性可分，如果是線性不可分的話應該怎麼做?
A1：線性可分的假設是一個簡化的假設，現實生活中很少符合，課程上是為了可以說明perceptron learning algorithm而做的假設。處理線性不可分有兩種方法，下週會說明將線性不可分的資料映射成線性可分。至於如何判斷是否為線性可分，現實中的處理方法就是在接收到資料集之後，我們先假設它們不是線性可分，實際上也幾乎都是線性不可分，然後再以處理線性不可分的技術來實作。perceptron learning algorithm的一個變形，pocket algorithm，就可以處理線性不可分。只要資料是線性可分，那perceptron learning algorithm就保證沒問題，但只要是線性不可分，perceptron learning algorithm就永遠不會收斂，而且效果還非常的不好。

Q2：perceptron learning algorithm的收斂速度如何隨著資料維度變化?
A2：變化很大。再次的說明到，第一節課談到perceptron learning algorithm就只是因為它最簡單，最好說明，後面還會有很多不同的演算法可以讓你淡忘這個演算法。

Q3：課程中提到，學習演算法一定會有一個模式(pattern)，怎麼知道一定會有這個模式的存在?
A3：我不知道。但這部份在後面談到學習是否可行的時候會有更深的說明。

Q4：機器學習是如何跟其它的統計學關聯起來的?
A4：統計學的目標是一個機率分佈，而機器學習的目標是一個函數。統計是一個數學領域，為了得到一個嚴謹的證明，我們需要提供很多的假設。而機器學習則是試著以最少的假設來覆蓋最多的領域。

Q5：機器學習是否可以得到一個全域最佳解，或是只能得到局部最佳解?
A5：最佳化是機器學習的一個工具，因此我們會需要一個非常具體的最佳化方式，像SVM就會需要用到二次規劃，這個二次規劃就是SVE的工具。其它相關會在相關課程中說明。

Q6：在拓撲意義上，hypothesis set是否為連續的?
A6：原則上hypothesis set可以是任何的東西，可以是連續的也可以是離散的。實際上，幾乎所有的hypothesis set都是連續而且無限(infinite)的，而且非常複雜，但即使如此還是可以成功的學習。

Q7：關於課程提到的信用貸款問題，我們應該如何收集資料?我們應該給每一個人信用評分，或是讓資料集有偏差。因為我們並不知道是否應該給那些我們已經拒絕的人貸款。
A7：這是一種抽樣偏差(sampling bias)，舉例來說，當銀行使用歷史記錄，看被被批准的申請人，銀行可以很輕易的推測出申請者的信貸行為，因為銀行掌握這些人的信用交易記錄。但對於那些被拒絕的人我們沒有辦法知道。但如果你用你所擁有的用戶資料，然後用這資料來做決定，那這個決策邊界會得出一個好的結果。有些時候資料並不具完全的代表性，學習中我們要遵循特定的原則，也就是我們談的抽樣偏差。(這邊不是很明白意思)

Q8：我們需要多少的資料才能得到一個魯棒性佳的結果?
A8：理論答案是課程中我們將會得到這部份，實際答案是我們無法控制。能做多好取決於你有多少資料，但你幾乎無法控制你能夠擁有多少的資料。

Q9：hypothesis set愈大，處理資料的效果愈好，但這也會對新進資料造成反效果(overfitting)，我們該如何定義hypothesis set的大小?
A9：如課程中所提，學習是一種關於進行預測的能力，所以我們要做的是應用這些資料找出一個模式，而不是記憶它們。當我們找出一個適用所有資料的模式，那就是一個合理的模式。舉例來說，你只有50個點，但用了7000階的多項式來訓練，這只是記憶，並不是學習。後續課程會提到，hypothesis set會有一個度量來衡量它的複雜度，然後告訴你在這個複雜度下你需要多少資料才夠。

Q10：我們學到模型之後是否有反饋的方式可以讓我們知道模型是否有錯?
A10：這後續會說明到。

Q11：實際應用中，以perceptron問題來看，怎麼依維度來看待它是簡單的或是難的?
A11：這比較難說明。在瞭解機器學習之前可能會用計算時間較長來做為是否複雜的判斷。但機器學習的瓶頸從來都不是計算時間，即使是非常大的資料集。它的瓶頸是如何應用到其它的資料集上。因此這個問題可以說，perceptron的計算效能很差，但泛化性很高，因為它夠簡單。

Q12：課程中提到一個binary function的範例，這個function是否可以是real function或multi-valued function?
A12：y可以是任意函數。

Q13：在perceptron範例中，輸出為+1、-1，那如果輸出剛好是0的話怎麼判定?
A13：開玩笑的回答就是取決於當天審理信貸人員的心情。正確的說是，如果真的遇到了，就給它輸出為0就好，不要讓它是+1或-1。

Q14：是否存在即使擁有大數據還是無法正確學習的問題?
A14：當然，如果我隨機產生一批資料，那很明顯是無法學習的。這回到課程，記住機器要成功學習的三個要點。1，存在一個模式。2，無法以數學的方式來處理。3，你必需擁有資料。

這邊沒有全數記錄QA，有些課程後面還會提的我就沒有記錄了。