在上一週的課程中，我們使用了one-hot結合詞庫來將句子作量化處理。但是使用one-hot的缺點是每個詞被視為獨立的，也就是無法衡量出兩個詞之間的相似或與重要性(兩個one-hot vector內積都會為0)。所以當你想知道apple和orange之間的關係比起apple和king還接近，就無法單純的使用one-hot來作文字的量化。其中一個方法是可以用不同的特性來作量化，比如說使用性別、是否為食物等等的特性，這個時候便可以辯識出具有相同性質的詞。

這種量化文字的方法又可以被稱為Word Embedding，像是每個詞會嵌在高維度的特徵向量中，即每個詞都可以在高維度的特徵找到一個能表示它的位置，而如果要將多個維度的特徵壓縮到兩維來表示，可以使用t-SNE演算法來找到相同的詞會彼此較相近。

使用Word Embedding的好處除了可以判斷出兩個詞之間的相關係，也對Transfer learning有很大的幫助，即使用已經訓練好的word embeddig來用在新的任務。在使用word embedding於transfer learning有幾種方法。1. 從大量的詞庫(1-3B)中進行訓練(或是下載已被訓練過的) 2. 使用原本已建立的embedding並transfer到新的而且訓練資料集較小(1-3k)的任務 3. 持續的使用新的資料來對embeddings進行finetune。

Word Embeddings也可以作到比擬(analogy)，比如說Man之於Woman等同於King之於Queen，這可以透過向量相減來找到相似的結果。

實際上要基於Man與Woman的關係來找到King和某個詞，可以透過向量相似度的計算來找到，只要找到King和哪一個詞的相似度與Man和Woman的相似度最接近即可。這裡的相似度計算是從原始的高維度(~300D)來的，雖然可以透過t-SNE來將高維度使用非線性的轉換到2維空間作視覺化，但如果使用了轉換的2維來計算反而會失真，所以在實際上的相似度計算會使用原始的高維度向量空間。

一個常用的相似度計算是Cosine similarity，即計算兩個向量的角度來判斷兩個相向之間的相似度。Cosine similarity也經常被用在文本分析中，透過計算代表兩筆資料的高維度向量，來評估兩筆資料的相似度。

Word Embedding的學習最終會得到一個Embedding Matrix，凡是把這個矩陣乘上某一個詞的one-hot向量，所得到的即是代表這個詞的embedding。因為one-hot是高維度而且幾乎都是0的稀疏矩陣，所以在實務上並不會真的相乘，而且透過特別的方法來找到詞的embeddings。

在word embeddings的學習演算法中，過去往往會使用很多很複雜的演算法來學習，但後來卻發現很多簡單的方法就可以達到很好的效果。在複雜的方法中，比如說要預測一句話的下一個詞，可以把每個詞的word embeddings輸入到一個類神經網路學習，最後訓練出我們要的embedding matrix(E)。如果有300維度，那麼要輸入到網路裡面的維度就會多達300乘6共1800維，也可以選擇只看前4個詞來學習，那麼維度就會降到300乘4共1200維。

不過事實上用簡單一點的模型也可以訓練出好的效果，比如說只用預測詞的前一個字，或是最接近預測詞前一個詞的詞(又稱為skip gram)來訓練word embeddings matrix。

這裡介紹Word2Vec的Skip-grams模型，Skip-grams在選擇Context與Target組合時，針對Target可透過隨機挑選的方式選出不同的組合，比如說Context詞的+-5~10個詞來選出Target詞。

再來將這些對應的組合透過matrix E轉成word embeddings後丟入神經路網學習，接著經過softmax後計算loss function來訓練出matrix E。

但這個方法的主要缺點在於需要大量的計算，因為在計算softmax時，分別需要加總所有詞，如果詞的數量越多，那麼速度就會越慢，因此很難擴充到大型的訓練詞集。一個解法是使用hierarchical softmax，先拆出詞位於哪個部份(前或是後五千詞)，接著再接續往下作二元拆解。在tree的結構可以把常出現的通用詞放在上半部，這樣就可以較快的被找到。

因為skip-grams在計算softmax需要花費大量運算，使用Negative Sampling則可以避免這個問題。Negative Sampling首先會先建立postive pair和negaive pair，比如說orange和juice會一起出現，就給予label 1，然後再隨機選出其他K個詞和orange組成negative pair給予label 0(即便某些時候negative pair組合真的有一起出現也沒關係)。最後將這些組合透過監督式學習訓練模型。

接著可以使用logistic regression來計算在給定label為1時，postive pair組合的機率，並使用K+1組資料進行訓練，然後再將這個分類器應用在10000個詞作二元分類。因此比起原本作skip-grams要一次訓練10000組資料，使用negatiev sampling的方法只需要用少量的資料訓練，再一次用在多組詞的分類。

但是該如何去選擇negative sampling呢？一個方法可以從詞出現的頻率選起，但是很容易選到停用詞(stop word)；或是假定他是均勻分配，使用1/|V|來選擇，而在這篇論文裡面是用了每個詞在訓練詞庫中出現的3/4次方來計算機率作選擇。

另一個學習方法為GloVe，首先會計算context和target一起出現在訓練資料的次數，Xij會等於Xji如果是用target的正負距離來選擇context，但是如果只看target出現在context後面，就會不相等。

GloVe的模型中為了避免Xij為0，因此會乘上一個權重f(Xij)，如果Xij為0則f(Xij)為0，當然這個函式也可以用來給予不同詞頻的詞有不同的權重處理。

情感分析(Sentiment Analysis/Classification)是NLP其中一種應用，主要用在判斷文本中是表達喜歡或是不喜歡(正或負)。比如說，輸入的X為評論的內容，輸出Y為評論的情感等級，像是從網路評論中判斷對於餐廳或是旅館的正負評論。其最大的困難在於情感分析缺乏大量的標記資料來學習，如果使用word embedding可以幫助在少量訓練資料的情況下學習。

在建立情感分析模型時，一樣使將每個詞透過embedding matrix選出該詞的embeddings向量，接著透過加總或是取平均值後，再使用softmax函式得到輸出Yhat。不過因為這樣的方法是沒有前後順序的，所以如果遇到明明有否定詞在前面，但是後面出現很多的正向詞good，這可能就會造成誤判斷把明明是一星的評論判成五星，因為出現很多次的good會把結果導到正向，這個時候就需要使用RNN來建立模型。

使用RNN一開始也是將每個詞透過embeddings matrix找到該詞的embeddings向量，接著將每個詞輸入進RNN，最後再接softmax判斷結果，這個就一開始提到的Many to One的RNN類型。因為RNN是會有順序性的，所以對於出現否定詞的句子能夠處理的比較好。因為word embedding可以從較大的訓練資料訓練出來，所以即使在情感分析的訓練集裡面缺少了某些詞，但這些詞有被word embedding訓練過，這樣在作情感分析時也可以得到較好的結果。

在word embeddings的訓練過程中，可能會造成帶有偏見的學習結果，比如說本來是希望學出Man之於Woman等於King之於Queen，但可能會學習出Man之於Programer對於Woman之於Home_keeper這種帶偏見，或是Father之於Doctor對於Mother之於Nurse這種錯誤的結果。因為機器學習現在已經越來越普及的被應用在許多不同的領域上，所以這種帶偏見的錯誤結果應該要被避免的。

解決這種錯誤的學習有不同的方法，以解決性別偏見為例來說明，第一先將girl-boy和mother-father來找到屬於性別的分界向量，這時把任一個詞和這個分界向量作內積，就可以找到這個詞會偏向哪個性別，並找出bias direction，要讓不能帶有性別偏差的詞向量去除bias。透過Neutralize將一些對於性別來說屬於中性的詞，將其投影到non bias的方向軸，最後為確保像是doctor這種應該屬於中性的詞，與帶不同性別的詞(像Girl或是Boy)距離要是相同的，會使用Equalize pairs的手法將帶性別的詞移動到以軸為中性對稱的位置，這樣就會讓兩者與doctor的距離或是相似度是相同的。在選擇哪些詞需要進行Neutralize，可以透過練一個分類器來分辨；在選擇要equalize的部份因為較少量，所以可以簡單透過人工挑選的方式完成。

參考資料:
Deep Learning Course 5 - Sequece Models

有序列性質的資料(sequence data)可以泛指輸入資料(X)是有序列的，或是輸出資料(Y)是有序列的。比如說在翻譯問題上，輸入和輸出都是有序列性的句子；但在情感分析問題上，輸入會是一個有序列性質的評論句子，但是輸出為情感的等級或是分數。

量化句子的方法可以使用詞庫加上one-hot encoding，可以透過自己建立或是使用已存在的詞庫，並將詞庫使用one-hot encoding作編碼來將文字資料作量化產生可以用來學習的輸入資料X。

如果使用一般標準的類神經網路會有什麼問題呢？1. 每一個訓練資料的輸入和輸出的長度不同，不好處理。2. 在不同文字中的不同位置無法學習出共同的特徵。如果要像CNN一樣能夠在不同的訓練資料的不同位置中學習到共同的特徵，就必須要透過RNN來達成。

Recurrent Neural Network(RNN)在每個訓練樣本會共同相同的weight和activation function。RNN會將每一個字詞X< i >經過激活函式後的結果，再傳給下一個字詞X< i+1 >，所以每個字詞會拿到由前面傳遞過來的資訊。但是只拿到前面字詞的資訊是不夠的，例如在判斷Teddy時，就需要使用字詞後面的句子內容，才能夠有效的區分Teddy究竟是指總統還是玩具。這時會使用到雙向的RNN(BRNN)才能夠解決這個問題。

前面有提到RNN的輸入和輸出長度可能會不一樣長，針對不同輸入輸出長度可分為不同類型的RNN。在翻釋問題上，不同的語言可能翻譯後的長度都不同，這是一個Many to Many問題；如果是情感分析會將一則評論輸出成正反或是1到5星等級，屬於Many to One問題；One to Many會適用在像是音樂生成，給定一種音樂類型來產生一首音樂；One to One這種類型就是一般的神經網路了。

RNN可以被應用在建立語言模型(Language Model)，例如在語音辨識中，透過語言模型可以透過計算不同輸出句子的機率，來辨識出哪一個句子是最符合的輸出。

把每個句字斷詞並量化後，就可以丟進RNN來建立模型。舉例來說，在訓練時，將第一層RNN輸入空向量，再將本來的實際詞Y< i >從第兩次RNN依序丟進去訓練，就可以建立模型來預測某段句子後會接什麼樣的詞。即輸入Cats average，判斷下個接每個詞的機率。所以可以透過將每個詞依序輸入來計算出在給定某個句子下，輸出某個詞的機率。在這裡可以透過外部詞典，並使用softmax來算出每個詞的機率

進一步我們就可以使用這個模型來隨機的產生句子，首先先隨機選出一個詞，接著將每個詞依序丟進下個結點來產生新的詞，直到取出字尾EOS或是設定一個固定的句子長度終止。

除了使用詞(Word-level)來組成句子，也可以使用字元(Character-level)來建且模型組成句子。如果使用字元來組成句子，那麼每一個輸出就是一個字元而非一個詞，好處在於不用怕取到辭典裡面沒有的詞，壞處則會產生更長的句子，也會降低訓練速度，所以目前經常是使用詞來建立模型。

梯度消失(Gradient Vanishing)

如果句子太長的話，使得神經網路過於深，會讓梯度在作back propagation時很難影響到前面的layer，產生梯度消失現象。對於RNN來說，實際上的影響在於如果太前面的神經元，將會無法去記住前面的詞(例如區分單數詞或是複數詞)。因此，傳統的RNN的輸出結果主要會受到接近神經元的影響，較遠的神經元不容易影響到最終的輸出。比起梯度爆炸容易被發現與處理，梯度消失反而不容易被處理，而且更容易影響到RNN的訓練結果。

Gate Recurrent Unit(GRU)是一個改善RNN長期記憶問題的方法，他引入了memory cell(C)的概念，在這裡的C就等同於activation function的輸出a，這個memory cell會將長期的記憶儲存下來，並用一個帶使用sigmoid轉換後的Γu值來判斷要不要選擇忘記之前的記憶並更新，還是要保留之前的記憶，直到不需時再忘記。實際上為什麼應用GRU會改善梯度消失的現象，主是要在Γu值透過sigmoid轉換後如數數值很小那麼就可能會非常的接近0，在這個情況下，C< t >就會非常接近C< t-1 >並很容易的保存較遠的記憶來大幅改善梯度消失的現象。

另一個常用的方法為Long Short Term Memory(LSTM)，在LSTM裡面C不再等同於a，LSTM會用到3種gate，分別為update gate, forget gate和output gate。

透過update gate和forget gate來決定是否保存較長遠的記憶，並透過output gate來輸出a到下一個神經元。

如果要同時合併前後神經元的資訊，就得使用Bidrectional RNN(BRNN)。BRNN除了從左到右作forward propagation外，也會從右到左作forward propagation。在輸出資料時，會同時輸入兩個方向進入activation function。而其中每個神經元也可以是GRU或是LSTM，所以實務上也會使用LSTM結合BRNN來建立模型。

RNN可以疊多層起來變成深度的RNN模型，本來RNN每一個順序都只有連接一個神經元，但也可以在每一個序順接處多個神經元來建立深度的RNN模型，甚至結合GRU和LSTM與BRNN來建立複雜的RNN模型。不過因為深度的RNN在訓練是非常耗資源的，所以不太常見到超過3層的RNN模型。

參考資料:
Deep Learning Course 5 - Sequece Models

最近正在學習Andrea在Coursera上開的Deep Learning課程，之前工作關係有接觸到keras，而且使用起來還滿容易上手的，所以就嘗試拿了MNIST資料集來試玩看看

首先載入手寫辨識資料集mnist，這個資料集還滿廣泛被拿來使用的，而且在keras也可以直接載入，另外也會用到最基本的keras Sequential model。

1
2
3
4

from keras.datasets 
import mnistfrom keras.models 
import Sequentialfrom keras.layers 
import Denseimport numpy as np

1
2

model = Sequential()
(x_train, y_train), (x_test, y_test) = mnist.load_data()

再來直接宣告一個sequential模型，並載入訓練和測試資料集

1
2
3
4
5

x_train = np.reshape(x_train, (x_train.shape[0], -1))/255
x_test = np.reshape(x_test, (x_test.shape[0], -1))/255

y_train = np.eye(10)[y_train.reshape(-1)]
y_test = np.eye(10)[y_test.reshape(-1)]

接著要先處理一下載入的資料，在x資料的部份要先將原本28×28的維度轉成1×784輸入，這裡可以使用numpy的reshape來處理，再來再將資料除上255作正規化。另外在label y資料集的部份則要作one-hot encoding，將每個標籤轉成長度為10的向量，並用0和1來表示屬於哪一個類別。

1
2
3
4
5
6
7
8

>>> x_train.shape
(60000, 784)
>>> x_test.shape
(60000, 10)
>>> y_train.shape
(10000, 784)
>>> y_test.shape
(10000, 10)

可以看到處理完後的資料維度

1
2

model.add(Dense(units=256, activation='relu', input_dim=28*28))
model.add(Dense(units=10, activation='softmax'))

再來加入兩個layer，即只使用一個hidden layer和一個output layer，其中hidden layer有256顆神經元，output layer有10顆，並透過softmax輸出結果

1
2
3

model.compile(loss='categorical_crossentropy',
              optimizer='Adam',              
              metrics=['accuracy'])

接著開始設定使用什麼loss function與最佳化的方法，還有要評估模型的指標

1

model.fit(x_train, y_train, epochs=10, batch_size=32)

接著就開始訓練，其中會設定訓練的週期與每一次的批數

1
2
3
4
5
6

>>> loss_and_metrics = model.evaluate(x_train, y_train, batch_size=128)
>>> print(loss_and_metrics)
loss=0.007, acc=0.998
>>> loss_and_metrics = model.evaluate(x_test, y_test, batch_size=128)
>>> print(loss_and_metrics)
loss=0.08, acc=0.979

中間可以看到訓練的過程，在訓練完畢說可以透過evaluate來評估model在訓練資料集，還有測試資料集的正確率。

keras在建立模型非常方便使用，可以很容易的加入需要的hidden layer數，而且針對常使用的activation function, loss function和最佳化的方法都有支援，如果需要快速的建出模型來作應用非常的推薦。另外keras也有支援CNN還有RNN，下次會用別的資料來試試看囉！

參考資料:
Keras Getting Start

上一堂提到validation的手法，透過留下用來驗證的資料模擬測試過程，並透過validation結果來選擇該使用什麼樣的模型。這一堂會提到三個在作機器學習時的小技巧。

Occam’s Razor在機器學習裡面意議是指不要對資料有過多的解釋，就是越簡單的解釋越好。以上面兩張圖的資料來看，左邊的模型符合直覺判斷，是一種比較容易而且 簡單的解釋，那到底什麼樣的模型才叫簡單的模型，而為什麼簡單的模型就比較好呢？

簡單的hypothesis是指沒有過多的參數就是個簡單的hypothesis，而簡單的模型則是指模型包含了較少的hypothesis就是個簡單的模型，所以簡單在這裡就是指比較小的hypothesis和模型複雜度。而要得到簡單的解釋，除了一開始就使用簡單的模型之外，也可以在之前透過regularization來達成。

那為什麼簡單的模型就比較好呢？如果今天使用簡單的模型就可以將資料分類正確，那某種程度上也就代表著資料背後的關聯性或是規律性是簡單的；相反的如果使用很複雜的模型，可能就無法知道資料背後的關聯性，因為不管是有關聯性的資料，或是雜訊很多的資料，都可以被複雜的模型分的開。所以如果使用簡單的模型來解釋資料，可以很直覺的看到資料間的顯著性，但是如果使用複雜的模型就辨別不出來，所以建議一開始推薦先使用線性模型。

第二個技巧會談到樣本的抽樣誤差，這裡用一個美國總統選舉的例子，來說明如果抽樣和要學習的結果不一致，並帶出抽樣誤差問題。如果在抽樣時就發生抽樣誤差，那麼在學習時就會產生偏差的結果，這就是為什麼前面課堂有說到訓練和測試的樣本資料要抽樣自相同的分配，訓練和測試的資料抽自相同的分配，才會得到預期中的學習效果，這就是我們VC中的重要假設。

這裡舉了一個實際上發生過的問題，如果訓練資料和驗證資料有有時間前後依序性(即一個人看過的電影順序)，而非隨機取樣的話，如果透過隨機取樣來建立訓練資料和驗證資料，那麼在學習和驗證中就會有問題。這時候為了讓測試和驗證可以盡可能的接近，例如訓練時可以把時間依序性較後面的權重調高，或是抽比較多時間依序較後面的資料來作驗證。

再來第三個技巧則是談到之前說到偷看資料的問題，前面有說到如果偷看了資料，可能會把人腦學習到的，或是自己的偏差帶進機器學習裡面。

偷看資料其實比想像中更容易發生，不是只有用眼睛視覺化的偷看才叫偷看，而是你在處理資料的整個過程中，都算是間接的偷看了資料。如果使用這樣偷看過的資料，都會受到自己的主觀影響。假設今天有一組八年的交易資料，使用前六年當訓練，後兩年當測試。其中在將資料作放縮(Data Scaling)的資料處理過程中，如果不是將前六年作縮放，預測完再還原，而是直接將八年的資料都作放縮的話，就會得到紅色這條上升趨線。這樣將會得到一個太過於樂觀的學習結果，如果將這個結果用來實際投資可能會大大的失準。

除了直接的視覺化偷看，或是使用統計分析間接的偷看，其實作在研究上也會發生。例如針對相同問題，不同的論文會都使用更好的模型來作的比以前好，這樣的過程就有點像你的論文間接的偷看了前面論文的結果，這樣就有點像某種程度的overfit了。正是所謂的如果你拷問資料過久了，他就會招拱一個好的hypothesis，但是這個hypothesis應該用測試資料可能效果不保證會好。

但是完全不偷看其實很不容易，只能盡量的降低這中間的干擾，比如說小心的使用validation，或是把測試資料好好的先收好。所以要時時注意的是，記得要用專業知識來建立模型，而不是先偷看了資料來作決策。另外要時時存著懷疑每次作出來的結果，並懷疑這樣的分析結果是不是有受過汙染。

這堂課教到很多和三有關的東西，第一個是三個和機器學習相關的領域，Data Mining是希望在大量資料中找到找到有用或是重要的關聯，人工智慧是要讓機器作出有智慧的事情(像是自動駕駛)，機器學習可以說是實現人工智慧的方法，統計則是為了去對母體作出推論，所以統計方法也被大量的使用在機器學習上。

在機器學習背後理論的保證，如果只有一個hypothesis的情況下，Hoeffding可以情供測試驗證的保證，當有多個hypothesis的情況下，Multi-Bin Hoeffding可以提供在有限多個選擇下的保證，如果是無限多個選擇下，VC則是可以提供在無限多個hypothesis是供理論上的保證。

在機器學習模型部份，PLA/pocket可以提供在線性可分下處理二元分類問題，在衡量上為讓0/1 err最小化，linear regression則是可以處理數值預測問題，在衡量上使用squared err最小化，logistic regression則可以處理軟性二元分類問題，在衡量上使用cross entropy最小化。

另外還有學到三個重要的技巧，Feature Transform可以將簡單的線性模型轉成高維度的複雜模型，會得到較好的Ein但是也會付出較高的VC代價，Regularization則是相反，透過加上regularizer來讓VC代價變小，但是也會讓Ein變大，Validation則是在沒辦法拿到測試資料的情況下，留下一部份的資料當作驗證資料。

最後則是這堂課學到的三個注意的地方，要注意簡單模型是好的，而且要注意抽樣的偏差，最後要記得不能提看資料。

再來後面的課程還會上到如何使用不同的轉換方法，以即不同的規則化方法，或是在缺少label的情況下該如何進行訓練。

總結這堂課程學到了很多機器學習背後的論理依據，而許多不同的機器學習方法將在另一堂機器學習技法課程教授！

參考資料:
Machine Learning Foundation 16

上一堂課講到為了避免overfitting，可以使用regularization的技巧，把一個regularizer加在Ein上面，轉而求Augmented Error反而可以有效的解決模型複雜度太高的問題。這一堂課會講到該如何使用Validation的手法幫助選擇機器學習裡面不同的參數。

在訓練一個機器學習模型，其中會遇到很多的選擇，包含使用哪些演算法、使用多少資料、要使用什麼非線性轉換方法，甚至是要使用哪一種regularizer。

Machine Learning裡面最實務的問題，就是如何作出好的選擇讓最後Eout可以作到最好，如果用視覺化的方法來作選擇，反而會受到自己的主觀影響，那到底該怎麼作選擇呢？

如果使用Ein來作模型選擇的話，就會受到overfitting的影響，越複雜的模型就越容易作好更好的Ein，但是會付出模型複雜度的代價，因為overfitting造成泛化能力變差，Eout反而也作不好。

那如果我們可以拿到實際的測試資料，就拿實際的測試資料衡量模型表現就好了，但是實務上可能不會有這樣的實際測試資料。

如果使用Ein來選模型不可行，而實務上又拿不到實際的資料該怎麼取平衡呢？我們可以使用手上的樣本資料，把一部份切出來當作看不到的測試資料，再拿剩下的資料作學習，並使用切出來的資料衡量模型的效果。

原本的樣本資料D要負擔兩種角色，一個是透過D來求出最好的Ein，然後再把D丟進演算法得到一個Hypothesis G，前面有講到如果這樣的話很可能會造成overfitting問題，所以我們把資料分成train和validation，先使用train總共N-K筆資料練習出好的Ein，並得到Hypothesis G，最後再透過K筆validation資料來驗證G到底好還不好。

從前面講到的learning curve可以知道，如果使用較多的資料來訓練會得到比較好的結果，所以實務上雖然會使用D(train)來訓練出不同的Hypothesis，然後使用D(val)作評估並選出最好的模型，但是最後在選好模型之後，會再把全部的資料D丟進模型裡作訓練，因為使用全部的資料會比較用部份訓練資料所訓練出來的模型還要好。

從驗證資料量和Eout來分析可以看到黑線的Eout會很大，因為在使用複雜的模型之下可能因為overfitting的關係造成Eout作不好；而虛線是用Etest資料，但是這個最佳的測試資料常常是不存在的；紅色是只使用訓練資料建立模型得到的Eout，他會比藍色使用全部資料來訓練所得到的Eout還要來的高。至於為什麼使用訓練資料會比使用Ein還要來的差的原因，是因為當驗證資料量K越大，代表訓練資料就越小，可能產生underfitting使得模型怎麼樣都練習不好。

所以我們會遇到不知道該怎麼選擇驗證資料量K的情況，因為如果用了比較大的K，雖然可以確保validation和Eout可以比較接近，但卻會造成訓練資料的Eout和全部資料的Eout差很多；但如果使用小的K雖然可以確保訓練資料的Eout和全部資料的Eout很接近，但是就無法確保validation和Eout到底接不接近。實務上的K常使用N/5。

假設今天設定K=1，並且重複抽出一筆當驗證算出error，再來把error作平均，就可以透過計算這個平均的error來推估Eout。而這種只抽一筆當驗證的方法就稱為leave-one-out的cross validation，因為每次都用N-K筆計算一個g，所以稱為交叉驗證。

在使用leave-one-out cross validation可以有兩種方法，第一種是拿掉一個點，用剩下的點作迴歸，再計算驗證的點到迴歸的距離當作error；第二種是拿掉一個貫，用剩下的點中間取一個常數，再計算驗證的點到常數的距離當作error，透過比較這兩種方法得到的較小的error，就可以選出比較好的模型，也許使用計算迴歸不一定會得到比較小的error，反而使用常數來計算還得到較好的結果。

而且leave-one-out cross validation的期望值，確實也可以證明和Eout是相近的，這個部份證明這裡就不多作說明了。

在實務上，如果使用Ein來選擇模型，使用越多的特徵雖然可以得到較小的Ein，但卻也可以造成overfitting，反而和Eout相差很大。但是如果使用leave-one-out cross validation的方法來選模型，確實可以找到一個比較接近Eout的結果，而且絕對對比Ein要來的好很多。

使用leave-one-out的最大問題，就是他會花很多的時間在作訓練，如果樣本資料有1000筆，每次都要拿999筆來訓練並重複作一千次才能取到平均的Error，所以在實務上leave-one-out要用來選擇模型可能比較不可行。第二個問題是leave-one-out因為每次只取一個點，所以他的變動程度很高，雖然有取平均，但是他本質上還是一個變動程度比較高的評估方法。

所以實務上，第一個希望可以降低訓練的次數，比起之前的1000次訓練，可以切成10份的方式，每次取9份作訓練1份作驗證後作平均，這樣就只需要作10次而不需要作到1000次。而且這個方法也可以作到交叉驗證的效果，leave-one-out其實也就是這種方法的極端例子。實務上比較常用的方法是切成十份，又可以稱為10-fold cross validation

使用cross validation在實務上會比只作一次validation當果會比較好也比較穩定，但是前提是在計算上是充許的，因為作k次的交叉驗證作平均需要額外的運算資源；而validation切5份或是10份就可以得到比較好的結果，不需要真的使用到leave-one-out。我們透過validation是可以讓我們選到一個比較好的模型，但是要注意的是，這個validation還是比最終使用測試資料的結果應該還是要樂觀的，只要真正應用在測試資料，你才會知道真的的效果如何。

總結來說，這堂課學到使用Ein來選擇模型是很危險的，並談到leave-one-out cross validaion與實務上會使用到的k-fold corss validation可以用來作模型選擇。

參考資料:
Machine Learning Foundation 15

上一堂課講到overfitting現象，他會在使用過高的模型複雜度、雜訊過多或是資料太少時發生。上次有提到可以使用Data Clean/Purning和Data Hinting從資料面下手解決，這堂課會提到regularized手法來避免overfitting。

Overfit現象就是Target和Fit兩者相差太多，雖然可以將樣本學習的很好使Ein很小，但是卻造成泛化能力很差Eout過高，就如同右邊這張圖。regularized目標則是希望可以把Fit曲線能夠更接近Target，所以regularized可以視成一個從高次方項走向底次方項的手法，有很多的解都可以通過樣本點，但是究竟哪一組是最好的，就是regularized要作的。那該怎麼從高次多項走回低次多項式呢？

要從高次多項式走回低次多項式，其實就可以視成低次多項式是高次多項式加上constrain，即如果把十次多項式中超過三次的項權重都設成0，那麼就可以降回二次多項式了。在求最佳化的過程也是，如果今天要求二次多項式的最小值Ein，就可以使用加上constrain的十次多項式來求最小值。

進一步的可以再延伸出，如果我並不是把超過三次項的權重設成0，而是只要其中有8項設權重設成0，就可以放寬這個constrain，讓regression可以更加的有彈性。這個放寬限制條件的二項式會比本來的二項式可以變化的項次更多，但也不像十次多項式這麼複雜。所以成求Ein時，只要確保權重為0的項次小於3個就可以了，但是這種離散的限制就像PLA一樣不容易求解，是NP-hard問題。

原本的條件是算權重不是0的項次要小於3，我們可以把他轉換成將每個項次權重平均相加要小於上限制C，這樣就可以轉成比較好解的問題，而且權重越接近0的取平均會越小。C如果設定的越大，就會越接近十次多項式結果，且所有比較小的C的項次組合都會被比較大的C的項次組合包含。這個H(C)又可以被稱為regularized hypothesis，即加上限制條件的hypothesis，而透過規則化的hypothesis set裡所找到的最佳hypothesis又稱為W(REG)

再來可以和之前一樣把式子轉換成矩陣的表示方法來解最佳化問題。原本我們可以透過走梯度反方向到W(lin)這個最佳解，但是現在加上了限制式，這個限制在幾何上是一個圓圈，找到前面所提到的規則化hpothesis最佳解W(REG)的話，就得同時往梯度反方向走而且不離開圓邊。又因為往圓的法向量(紅色向量)走就會離開圓邊，所以只能往垂直於法向量的分量走(綠色向量)，當持續走到梯度反方向要是和圓的法向量平行的話，就代表不能走了，即為找到最佳解。我們可以把兩個平行向量的比值設成2λ/N。

再來可以把求梯度等於0轉換回求最小值的式子，即為Ein加上一組regularizer又可稱為augmented error Eaug(w)，如果預先先指定λ值就可以很容易的解這個式子。

所以只要加上一點regularizer就可以對模型結果作出適當調整，今天如果λ設成0的話就等同沒有regularized即為overfitting，λ設的太大則會造成underfitting，加上regularizer就會有類似懲罰的效果。這種的規則化方法又稱為weight-decay regularization，即把權重最小的規則化方法。而且這個規則化方法可以應用到linear regresion、logistic regression甚至是其他不同的transform。

但究竟這個augmented error和之前學到的VC有什麼相關性呢？用求augmented error的方法來解本來不好解的constrain Ein，這裡對應到的VC保證為Eout會小於En加上一個constrain H(C)，所以作好Eaug就能把Eout間接的也作好。

Augmented error和VC bound其實相同的地方在於都是在求複雜度，augmented error求的是單一個hypothesis的複雜度，而VC則是在求整個hypothesis集合的複雜度。這個augmented error如果可以表現更好，那麼Eaug可能是一個比Ein更好的代理人可以幫我們作到好的Eout。

其實使用regulization付出的VC dimension會比原本還要小，因為在實際上有N個特徵維度下，最終透過regulization將不會使用到那麼多的維度。這裡相比原本的d(VC)，可以稱為d(EFF)，其付出的維度會比本來的d(VC)還小。

那到底該使用什麼樣的regularizer呢？今天如果在知道target特性的情況下，可以針對target特性來設計regularizer，比如說如果想要一個比較接近偶函數的函數話，就針對奇數次方讓他變小。又或者在選出一個比較能夠說服我們的regularizer，像是比較平滑或是簡單的regularizer，因為overfitting是noise造成的，noise就會造成不平滑，像是使用L1 regularizer。或者也可以找一個好使用好最佳化的regularizer，像是前面說到的weight-decay regularizer，又被稱為L2 regularizer。如果找到不好的regularizer，那就把λ設定成0就等同於拿掉regularizer的效果。

L2 Regularizer最大的好處就是他很好微分求最佳值，而L1在微分求最佳值的部份比較困難，且L1在求最佳值時很常發生在頂點上，意義就是某一些的權重w會是0，所以L1 Regularizer又被稱為sparse regularizer。透過L1就可以在高維度空間下(例如1000維)，找到一些w非0的項次(可能只有5維)，所以在最後的預測只要算非0項速度會比較快。

那λ該怎麼選擇呢？很明顯的可以看到不管是stochastic noise或是deterministic noise，只要noise越大λ就要越大。下一講將會開始說明在使用規則化手法時，該如何有效的使用最佳的λ。

總結來看，這堂課說明規則化就是在原本的hypothesis加上一個條件，並轉成一個Augmented Error，因為作了規則化所以有些維度就不會被使用到，因此VC維度就會下降成d(EFF)，而使用regularizer的使用方法可以針對target特性，或是使用容易說服自己的regularizer，還有也可以使用好最佳化的regularizer。

參考資料:
Machine Learning Foundation 14

上一講提到可以使用非線性轉換的方法，將線性的模型轉換成非線性，雖然可以解決更複雜的問題，但也伴隨著模型複雜度提高的代價。這一講將提到過度適合(Overfitting)現象所造成的泛化能力缺陷。

假設今天有一個目標的函式是二次函式，但我們使用的四次函式來找到通過所有點的答案使得Ein為0，但這個四次函式卻和目標的二次函式差距很大造成Eout很大。這樣就會讓這個四次函式只認得樣本資料，而這種VC維度很高所付出的代價就是模型會失去舉一反三的能力，也就是泛化能力很差。

這裡帶出學習會出現的兩個問題，一個是過度適合(Overfitting)，即Ein的fitting作的很好，但是作過度了造成Eout效果不好；一個是低度適合(Underfitting)，即Ein的fitting作的不夠好。Underfitting可以透過增加樣本資料或是使用較複雜的模型就可以解決，但是Overfitting反而是一個比較難解決的問題。

發生Overfitting會有幾種原因，第一種是使用了過多的VC維，也就是使用了過於複雜的機器學習模型，像是對二次函式問題使用了四次函式來解；第二種可能性是雜訊太多，造成錯誤的學習；第三種是資料量不足，如果資料量不足可能沒有辦法學習出接近目標函式的結果。尤其當資料量不夠且雜訊又多，就很容易造成Overfitting讓模型最終失去泛化能力

假設現在有兩個目標函式，一個是十次多項式加上雜訊，一個是五十次多項式但是沒有雜訊。今天分別使用二次多項式和十次多項式來比較兩個問題的學習結果，會發現十次多項式都發生Overfitting，在Ein都作的比較好，但是Eout都作不好。甚至是當我們已經知道目標函式是十次多項式的情況，使用十次多項式的結果也不一定會贏過二次多項式。

用學習曲線來看會發現，當樣本數量不夠的時候，十次多項式Ein和Eout差距會非常大，所以如果資料量不足就不應該免強使用較複雜的方法，反而使用二次多項式還能夠學習出比較好的結果。

那如果都沒有雜訊的情況下也會是二次多項式的效果比較好，因為當目標函式很複雜時，也會造成類似雜訊的效果，如果二次多項式和十次多項式都作不好，使用二次多項式的泛化效果可能會比較好。

什麼時候要注意overfitting會發生呢？可以分成模型複雜程度Qf和雜訊程度σ^2來探討，再來會討論兩者和資料量N之間的關係。延續之前的二次和十次多項式的例子，再來會使用Eout(g10) - Eout(g2)來衡量overfit的程度，即使用十次和二次多項式的Eout差來衡量。

在固定模型複雜度之下，只要資料量不夠而且雜訊程度越高，就越容易造成overfit；但在固定雜訊程度看模型複雜度的影響，大部份也是發生在資料量少且目標複雜度高會造成overfit。

兩者最主要的差異在於，雜訊是stochastic noise，即隨機產生的，但是目標函式的複雜度是deterministic noice，是固定可以計算出來的。總結來說在四種情況下會發生overfit，第一個是資料的量過小，第二個是stochastic noise太高的時候，第三個是deterministic noise太高的時候，第四個則是VC維度太高的時候。所以overfit是很容易發生的。

所以到底為什麼今天的目標函式太過複雜的情況下和隨機雜訊是類似的呢？假設今天目標函式太過複雜，以至於無法使用任何的hypothesis描述，這中間的差距就是我們說的deterministic noise，這並不是一個隨機發生的雜訊。所以deterministic noise會取決於hypothesis，而且在給定相同x之下會有相同的deterministic noise。

如果有這麼多的原因會造成overfit，那該怎麼解決呢？在模型部份，可以先使用比較簡單的模型開始，避免一開始就用過複雜的模型；在資料部份，可以將雜訊資料作data cleaning/pruning處理，或是收集更多的資料與使用data hinting產生虛擬資料來提供更多額外的資料；另外還可以透過regularization對模型產生懲罰效果，或是透過validation來隨時看學習的狀況。

在Data Cleaning/Pruning的部份，Data Clean是指把已經確定是錯誤標記的資料，標記到正確的類別。Data Pruning則是直接將錯誤的雜訊資料直接從資料集去除掉。兩個資料的處理方法都不難，難度反而會在於該如何判斷資料是有問題的雜訊資料。

在Data Hinging部份，以圖像的數字辨識來說，就是把每個字作簡單的旋轉來當作新的虛擬資料並加進來學習。這個方法很常用在現今在作圖象辨識時，對圖像作扭曲或是轉換來增加學習樣本數量。

總結來說，這堂課教到了把Ein作好但是Eout作不好是overfitting現象，而且overfitting是非常容易發生的。不只是雜訊會造成overfitting，當目標函式過於複雜時，也是另一種雜訊。在處理overfitting的部份，這堂課簡單提到了data cleaning/pruning和data hinting，下一堂會再進一步教到如何使用regularization來避免overfitting現象。

參考資料:
Machine Learning Foundation 13

上一堂講到三種不同的線性模型都可以用在二元分類，並且還可以透過二元分類來達成多類別分類，這一堂課會教到該如何將線性模型延伸轉換成非線性模型。

前面都講到線性模型，線性模型可以很容易的計算出線性分數，再結合不同的轉換作輸出，線性模型好處在於VC維度是可以很容易的受到控制的，所以確保作好Ein，Eout就可以表現的好。但是如果遇到像右邊比較複雜的資料，可能就沒辦法使用線性模型達成，勢必需要結合其它手法來突破限制。

再重新看一次這組比較複雜的資料，可以發現他雖然沒辦法線性分割，但似乎是「圓圈」可分的問題，也就是在圓圈內和圓圈外是不同的類別。那該如何把本來線性可分的問題轉成圓圈可分，再透過前面教到的演算法來解決呢？

接著我們先把原本的圓圈作符號的替換，可以整理成像之前一樣的向量內積式。他的意義在於，如果本來可以這個問題在X維度上用圓圈分出兩種類別，那麼在Z維度上將可以用直接用直線來分出兩種類別，即線性可分問題，這樣的轉換又稱為特徵轉換。所以我們知道問題在X維是圓圈可分，轉成在Z維是線性可分，但是相反來說的是不是在Z維是線性可分，在X維就是圓圈可分呢？

在Z維是線性可分，但是在X維其實不一定會是圓圈。因為在二次曲線可能性不止是圓圈，還有可能是橢圓或是雙曲線，甚至就算是圓圈還可能分成圓內和圓外，那該如何找到所有二次曲線的可能性呢？

我們可以列出所有能表式二次曲線的項都列出來(包含常數、一次項和二次項)，所以在Z維的perceptron就會對應到在X維的某個二次曲線可能的分類方式，當然也有可能會退化成一次方程式。

所以到現在可以發現，如果能夠在Z維找到一個好的perceptron，就可以在X維找到一個可分割類別的二次曲線。之前學習的內容都是在X維裡面使用x和y來找到好的perceptron，現在要在Z維找到好的perceptron，自然就需要使用在Z維上的資料，再使用學習到的二元分類方法來處理。

首先可以透過一個函式Φ來將X維資料轉成Z維，再使用演算法來找出一個線性分割的perceptron。於是我們就可以把X維的資料，把它丟到Z維看看轉換到Z維的這筆資料究竟是什麼類別，就可以知道這筆資料該分成什麼類別。所以當我們把原本學到的方法透過特徵轉換到二次式甚至是多項式，可大大延伸演算法的應用範圍！

比如說本來維度很高的手寫辨識資料，可以應用特徵轉換建立intensity和symmetry組成的兩維問題。

這樣的特徵轉換好看起很多好處，但是究竟會有什麼壞處呢？前面只講到兩次項而已，如果今天要把特徵轉成Q次項的話，他的複雜度將會是O(Q^d)，其中d是除常數項以外的項次，Q是要作的Q次項轉換。所以可以發現，透過這個轉換會讓計算還有儲存都多花費額外的力氣，可能是很困難的。

除了計算和儲存的困難，在VC維也會因為Q變大而變大，造成模型的複雜度變高。

上面給出了一組資料且有兩種分類結果，雖然右邊的Ein為0(即所有資料都可以分對)，但是相比起左邊的分類結果反而讓人比較喜歡。雖然左邊的分類結果有些點是分錯的Ein不是0，但是線性的模型的泛化能力會比較好，雖然特徵轉換的維度比較低，Ein比較大，但是確有可能得到一個比較好的Eout；右邊的模型其特徵轉換的維度比較高，雖然讓Ein可以作的很好，但有可能得到較差的Eout，這就是機器學習上特徵還有模型選擇的trade-off！

那到底該選擇哪個維度的轉換才是最好的呢？也許就先把資料作視覺化看看資料長什麼樣子就能決定了，像是正圓圈只要作二次曲線轉換就可以了。看似好像一下子就可以找到特徵轉換的維度來達到好的學習效果，但是這樣的過程其實包含了過多的人為介入，而這樣的介入也許可以得到不錯的學習結果與好的Ein，但是背後隱含了機器會受到你的主觀想法和偏見影響，也容易讓你對學習的結果有過度的樂觀。所以在機器學習中要非常的小心，也許我們可以先偷看資料，然後用腦袋解析一次來找到最好的維度轉換與好的Ein，但是這個學習的結果在拿來應用時卻可能會得到不好的效果。

在多維度的轉換過程中，當轉換成Q維時，其中也包含了Q-1維的項次，Q-1維能作到的事Q維也能作到，Q-1維就等同於在Q維中某些項次為0，這其實是一個巢狀的涵蓋蓋念。

維度越高，可調整的自由變數就越多，所以VC維也就越多；又因為可調整的自由變數越多，所以也就越有可能找到更好的結果來產生更好的Ein。再來就可以畫出之前也看過的圖，Ein會隨著VC維而下降，而模型複雜度則會隨著VC維而上升，其中我們最在乎的Eout會先下降再上升。所以如果一開始就使用很高維度的特徵轉換是會得到好的Ein，但也會付出模型複雜度的代價，造成Eout效果不好。

安全的作法是先從低維轉換開始，再持續往右邊移動，直接找到好的Ein與好的Eout。雖然線性分類也許可以作到的是有限的，但是線性的泛化能力比較好，反而最後可以作到的事情是比較多的。

這一堂課教的是把原本線性的模型作特徵轉換變成非線性，並說明其中轉換的流程該如何作，但要特別注意的是維度的轉換是會付出計算、儲存和模型複雜度代價的，在選擇維度轉換記得要從簡單的開始，慢慢的往高維度找到最好的模型。

參考資料:
Machine Learning Foundation 12

上一講談到logistic regression，這一講會講到到底該如何使用線性的模型來作二元或是多元分類。

複習一下三種線性模型，共同點就是三種都會透過計算分數來作分類，差別在於PLA的線性分類會將分數取正負號來達到0/1分類，線性迴歸則是直接輸出分數，並使用squared error評估找到最佳解；logistic regression則是會透過logistic function將分數轉換成0到1的機率值。

為了將線性模型作二元分類(y=-1/+1)，可以把error function稍微整理算出yx項，這個yx項的實際意義為分類的正確性，也就是yx項得到的分數要是正的(即兩者同號)，而且越大越好。

再來將三種模型的error畫出來，可以發現三種error的特性都不同，唯一相同地方在於如果squared和scaled cross-entropy很低時，通常0/1也會很低。

究竟linear regression和logistic regression是否是好的分類方法呢？先從VC的角度來看scaled cross-entropy他會是0/1 error的upper bound，所以如果把logistic regression的cross-entropy error作到最小的話，也就可以說我們能把0/1 error也作的好。當然sqr err也是一樣，所以linear regression和logistic regression確實是可以作到二元分類的。

在logistic/linear regression分類問題上，linear regression的好處是他最容易作到最佳化，但是其error衡量比較寬鬆；logistic regression因為他也是convex所以最佳化也是容易的，而error衡量在ys負向很小時會很寬鬆，但也比linear regression還好；PLA則是如果在線性可分的問題上可以作到很好，不過缺點就是如果在非性線可分的問題上，雖然可以使用pocket演算法，但是效果就沒那麼好。

以前有有學過，雖然linear regression太過寬鬆，但是卻可以很快的先拿在找到一個初始的權重值，後續再交給PLA或是logistic regression作後續的最佳化。在實務上大部份的人會較常使用logistic regression來作二元分類，因為可以兼顧效果還有最佳化的容易程度。

雖然PLA和logistic regression都是iterative optimization方法，但是PLA是每看一點就作調整，而logistic regression卻要看完所有的資料點才會一次調整權重，他的速度和pocket一樣，每作一輪都要花比較長的時間，到底能不能讓logistic regression和PLA一樣快呢？

那不就學PLA每看一個點就調整一次權重就好了啊，這種每看一點作偏微分求梯度來調整權重的方法就稱為Stochastic Gradient Desent(SGD)，即用隨機的梯度作梯度下降來接近真實梯度的期望值。好處就是每次算一個點比較簡單而且容易計算，由其是在大量資料的情況下原本的批次梯度下降法速度會很慢，但是壞就就是一次看一個點所以每次調整的結果可能很不穩定，但是最終應該都會很接近要求的目標值。這種隨機梯度下降也適合online learning，即每次接到一筆新資料後即作學習調整權重。其實還有另外折衷的方法稱為mini-batch gradient desent，當我們沒辦法看完所有資料再調整權重時，那就一次看N筆資料作調整就好囉！

那PLA和logistic regression到底相差在哪裡呢？PLA是一次調整到位，而logistic是看差多少就調多少，所以SGD的logistic可以說他像soft的PLA，而PLA又很像η設成1的logistic。在執行logistic時有兩個可以調整討論的地方，第一個是停止條件，通常我們會執行夠多的次數，因為我們相信執行夠多次就會逐步接近目標執；另外是η的設定上，老師個人習慣會使用0.1126，也許之後需要調整學習速度時可以參考一下。

再來談到多類別分類的問題，實務上常會有很多多類別的問題，像是要辨識圖像上不同的東西就是多類別的問題，再來會介紹該怎麼使用二元分類來達成多類別分類。

當我們想分類其中一種類別時，可以把其他三種當成同一種類別，這樣就可以建立四種二元分類器，把多類別問題轉成二元分類問題。但是這樣的方法會有某些地方有分類重疊的問題，像是四個角落都有兩種分類器範圍重疊，甚至也會有某些地方所有分類器都分不出來，像是中間區塊所有分類器都會認為不是自己要分類出來的區域。那該怎麼辦呢？

我們可以應用logistic regression來達成softly classfication，用顏色深淺來代表機率的大小，顏色越藍分到O機率越大，反之顏色越紅分到X的機率大。

再來組合出四個分類器，就可以知道在給定一組資料X，他究竟有分到不同類別的的機率有多少，所以可以透過選出機率最大的類別來判斷要分成哪個類別。

當我們有K種類別要作分類時，透過logistic regression建立K個分類器，接著選出機率最高的類別，這種方法來作多類別分類稱為One-Versus-All(OVA)。好處是方法很有效率，而且只要和logistic regression能算出機率值的方法，都可以應用OVA作多類別分類，壞處是如果成兩元分類的資料不平衡的話，可能造成每個分類器都叫你猜大宗類別，造成最終分類效果不好。

前面有講到OVA會遇到Unbalance問題，可能造成分類表現不好，那該怎麼解決這個問題呢？

前面是一對其他所有類別作兩元分類，我們其實可以直接使用其中兩種類別的資料作二元分類就好了，如果兩種類別的資料接近的話，那麼資料量就會比較平均避免Unbalance問題。

那有這麼多的分類器，到底該如何判斷是哪個類別呢？以方塊類別為例，其中可以發現共6個分類器，其中前三個都說分出來的結果是方塊，後面三個則分類分到一個菱形和兩個星型，透過投票可以知道最可能的類別應該會是方塊，因為分出方塊佔大多數。

這樣的方法稱為One-versus-one(OVO)，因為他是一對一類別的分類，而非一對其他所有類別的分類方法，透過一對一類別的分類別，再找出最有可能的的類別。這個方法的優點是在訓練資料時很有效果，因為只使用比較少的資料量來作訓練，而且可以應用在所有的二元分類問題；壞處則是要訓練更多的分類器，所以在預測的時間、訓練的次數還有儲存的空間都會花比較多。

這一講首先學到了前面講的三種線種模型方法其實都是可以用來作二元分類的，而且針對logistic regression可以使用SGD來作隨機梯度下降找最佳解，這樣的方法很像最早學到的PLA。再來針對多類別的問題教了兩種方法，都是應用二元分類來達成多類別分類，第一種OVA是把所有資料分成兩個類別，一個是要分出來的類別，另一個是把其他資料視為同一類別；第二種OAO是單純就看兩種不同類別來作兩兩比較，而這兩種多類別方法都是簡單而且常被拿來使用的分類手法！

參考資料:
Machine Learning Foundation 11

上次介紹了linear regression，這一堂課會說到logistic regression，主要會將linear regression使用sigmoid轉換來算出不同類別的機率。

之前有學過在二元分類中會判斷病人「有」或是「沒有」心臟疾病，並可以使用0/1的分類錯誤來判斷分類的結果好壞

但如果今天並非想要知道病人「有」或是「沒有」心臟疾病，而是想知道未來一段時間後，心臟疾病發生的機率是多少。和二元分類有點不同，我們想要知道的是發生某個狀況的機率，這會是一個介於0到1的數值。當然後續可以對這個數值定義出一個臨界值來達成二元分類，所以又可以稱為soft binary classification。

如果我們可以知道在給定一組x，他的結果y是一個機率值的話那就可以很容易的找到這樣的結果，但是實務上我們只會拿到有抽樣誤差雜訊的結果，只能知道0/1的結果(即有沒有心臟病發)。再來會學到的是，如果只能知道0/1的情況下，要如何求出想要的機率值。

要如何找到這個機率值呢？一樣可以像之前的線性問題，將每個特徵乘上特徵權重，就會找到分數，但是這次想要的不是這個分數，而且要把分數轉換為0到1的機率值，分數越大機率越大，反之分數越小機率就越對，這裡會透過logistic function會把這個分數值轉換成0到1的機率值。

一般會使用sigmoid來把分數轉換成0到1的機率值，當分數越大會越接近1，分數越小會越接近0。再來就可以使用這個logistic hypothesis來達到我們的目標函式f(x)

究竟logistic和之前學到的有什麼差別呢？
在linear classification算完分數會以0為臨界點來區分0/1類別，並使用0/1 err來判斷結果，在linear regression則會直接輸出分數，再使用squared err來評估結果；logistic regression會將算完的分數透過logistic function轉換，但該用什麼err來衡量呢？

首先可以先算出f(x)是怎麼產生一組資料D的，再來因為要使用hypothesis H來逼近f(x)，所以可以把f取代成h，因為最好的狀況下，我們學習到的h和原本的f是會非常接近。而且如果資料D是由f產生的，那麼f算出來的機率值應該是很大的，所以若是可以在多個h裡面找到一個最大機率的h，就能找到一個最適合的hypothesis

在計算likeliood時，重點會放在hypothesis上，因為hypothesis決定了最後的機率，再來因為logistic function具有對稱性，所以最後可以整理成h(YnXn)的連乘

因為這個hypothesis是線性的，在線性裡面我們關注的是其中的權重w，所以再重新整理將h取代成w，把y取代成線性組合yn*w

之前最常處理的就是連加的問題，所以我們取log將連乘取代成連加，再來為了轉成求Ein，所以加上負號來取最小值。最後再將logistic function代進去，就可以得到最後要求的Ein，這裡的Ein又可以稱為cross-entropy error。

在推導出Ein後，再來就要找到一個權重w可以讓Ein最小，因為Ein最小就可以知道Eout也很小。前面的linear regression因為是convex所以可以透過梯度找到最小低，而logistic regression這個函式也是convex，所以也可以透過梯度來找到梯度為0的地方算出最好的權重w。

我們可以使用微分和鏈鎖率來找到梯度，如果今天要讓梯度等於0可以有一個假設，就是假設θ出來的值是0，但要讓θ出來的值是負無限大，就要讓y乘上w乘上x這一項是正的。其中w^T．x這個分數在以前可以被拿來作兩元分類，而乘上y如果大於0的話，代表是同號，即所有資料都可以分對，意義就是線性可分。之前在linear regression可以直接算出一個close-form的答案，但是現在logistic regression並非線性的，困難在於沒辦法直接算出close-form的解，那該怎麼辦呢？

這個時候就可以應用到之前的PLA方法，PLA在每次拜訪到的點如果分錯的話，就會逐步作調整來更新權重。

在整理後可以歸納出兩個部分，如果需要更新權重的話，第一個η是指走多大一步，之前在PLA可以視為1，後面第二部份則是算出要走的方向。像這種逐步循序的調整學習又稱為iterative optimization approach逐步最佳化方法。

那麼再來要如何找到logistic regression的最好權重值w呢？其實就是隨便找一個方向v，然後慢慢透過往下走到谷底就可以了，其中要走的步伐η會決定往下走的速度。

但是要怎麼找這個方向v呢？因為這個問題還是非線性，但是如果我們每次都看一小小段，就是一次只看一個線性問題，就可以比較容易而且轉成接近線性問題。其實這就是常使用的梯度下降法(Gradient Descent)，即每一次走梯度逐步找到最佳，或是近似最佳解。

那麼η該怎麼決定呢？如果η太小的話，雖然遲早可以找到最佳值，但是速度會很慢；如果η太大的話，反而可以會跳過最小值，搞不好會跳來跳去找不到最佳值。有一個最好的方法，就是隨著坡度的大小來決定η要走的大小。

因為η會改變，所以可以採用一個不一樣的η來代表這個會變動的η，即他每一次的學習都是會變化的η乘上梯度，這就稱為fixed learning rate gradient descent。

最後我們可以逐步的作梯度下降，一直到找到最好的谷點，但是實際上可以找到接近谷底的值就可以了，所以最常用的就是設定一個iteration的次數，到達就停止。這個方法其實就很像之前學到的pocket方法，pocket方法是每次抓一個最好的值，得到更好的值就會更新。

因為之前有上過Andrew的Machine Learning課程，其實Andrew在教linear regression找最佳權重w時，就是直接教fixed learning rate的梯度下降法，我覺得在學習線性時用梯度下降還滿好理解的，對於後面到logistic regression很有幫助，建議沒有上過Andrew的Machine Learning課程可以考慮上看看！

參考資料:
Machine Learning Foundation 10
Andrew Ng - Machine Learning