0:00
好，那我們來看看，我們剛才說到說，One Versus All裡面
一個最麻煩的問題就是，如果我今天Class的數量一多，K一大的時候。
我很有可能，面對的會是一個Unbalance的問題。也就是 說，我今天，哎，可能我的圈圈很少，然後叉叉非常的多。
我為什麼我的圈圈會很少，叉叉非常多？因為我的一個Class的這些Example要去- 打什麼？要去
打所有不是這個Class的人。所以，想象成這個好像是在打架的話，就是一個要打很多個- ，一個要打很多個的話，
就會產生這個Unbalance的問題，造成說，哎，我們的表現可能沒有很好。
我們要怎麼樣解決這個Unbalance的問題呢？好吧，既然如果今天是一個人打五個人- ，這個會有不平均的狀況
發生的話。那我們今天想辦法用一對一的來對打可以吧？什麼叫一對一來對打？ 也就是說，我今天在做Binary
Classification的時候，我 不再是，比如說方塊跟其他所有三個不同的Class。
來看看哪個是圈圈，哪個是叉叉。而是我直接從所有的Class裡面
選兩個出來，先看看這兩個裡面，哪個比較像是我要的答案。
什麼意思呢？好，例如說，我可以先做一個比較是這樣，說，哎，今天在我所有的資料里
面，到底，OK，哪一邊比較像是方塊，哪一邊比較像是菱形。也就是我把方塊當圈圈， 菱形當叉叉，我一樣，我可以做一個Binary
Classification，做一個分類的動作之後， 哎，我得到說，啊，右邊這邊比較像方塊，左邊那邊比較像菱形。
好，所以這是方塊跟菱形，只有方塊跟菱形對打而已，沒有把其他的
這個Class來放進來。好，於是這樣子，好，如果我的資料的分佈，每個Class是
大概平均的話，那麼我相對應的這個二元分類的問題，就也會是比較平均的。
好，所以不止這兩個Class可以這樣做，那我還可以做什麼？我還可以做方塊跟三角
形。好，也就是中間那邊切一刀，右上角是方塊，左下角是三角形。
好，或者我可以做方塊跟星號，上面是圈圈下面是叉叉，好，這樣子一刀切開。
好，所以呢，大家可以想象，我如果有四個Class的話，我總共有幾種切法？好，
也就是說，四個裡面我要選兩個，總共，好，我就會有六種切法。所以這是第四種、
第五種、第六種，好，這些不同的分類問題。那我們現在已經很會解分類問題了，
反正哎，我就咚咚咚咚咚，把這些分類問題產生出來把它解開。
解開以後怎麼樣？那我們就來想啊，我最後要怎麼樣決定，
到底哪一邊要當做這個方塊的，哪一邊要當做菱形的，哪一邊要當做三角形的？
好，我們就來看，跟方塊有關的分類器是哪些？
好，這個是一個跟方塊有關的分類器，這個是一個跟方塊有關的分類器，這個是一個跟方塊有- 關的分類器。
對吧？所以跟它有關，就是說，我們在訓練過程中，有把方塊使用進去的。
好,那現在我們又再看到甚麼呢?這三個分類器, 在很接近
方塊的地方，通通都給了藍色，通通都給了支持方塊的這邊。所以，例如說， 我們的這個區域上，這一個區域上，這一個區域上，
哎，通通都得到了這個，支持方塊的這個訊息。
好，其他三個分類器，其實跟方塊沒有什麼關係，我們也不太管了。不過呢，我光從這三- 個分類器
的結果我就可以知道說，哎，在我圈起來的這一個區域裡面，
大概是一個方塊，或者我們可以把這六個分類器的輸出，有一點像是什麼？
有一點點像是，今天有四個隊伍，想像四個棒球隊好了，四個棒球隊的比賽。
要比什麼？要比說，哎，到底哪一隊是總冠軍。
那我們這六場比賽是什麼？六場比賽實際上就是這四個隊伍的一個循環賽。
好，第一個分類器說，哎，到底哪一個隊伍比較好，第二個分類器說，哪一個隊伍比較好。
好，六個分類器的結果出來，例如說，我今天假設有一個測試的點在這邊，
好，我就看看了，這六個分類器各說什麼。第一個分類器說，它是一個方塊。
第二個分類器也說，它是一個方塊， 第三個分類器也說，它是一個方塊。
第四個分類器呢，雖然它
不是用方塊訓練出來，但是它可以說它比較像什麼，它會說，它在靠上面，它是比較像菱形的。
好，所以，我這邊可以列出來，這個說方塊，這個說方塊， 這個說方塊，這個說比較像菱形。
好，那另外這邊呢，好，這個我的點，如果點在這邊的話， 這個分類器說什麼？這個分類器說比較像一個星星。
然後呢，這個分類器說什麼呢？這個分類器說，比較像一個星星。
所以總的來看是什麼呢？如果我們要決定這一場比賽，這六場比賽，從這六場比賽
決定說，這四種類別裡面，到底哪一個類別是最適合預測的類別，對我剛才點的這個點來- 說的話。
我們可以看到說，方塊贏了三場，星星贏了兩場， 菱形只贏了一場，然後這個，三角形是全輸的。
所以這個時候，對這個點最好的預測是什麼？對這個點最好的預測就是方塊。
好，我點每一個點，我都可以用這六個分類器去做同樣的預測， 然後我們把每個分類器，這些預測的結果畫出來，我們最後得到一個圖，就長
這個樣子。好，這個樣子說什麼呢？它說，哎，在右上角那個地方，大概都是
方塊，哎，左上角的那個地方大概都是菱形，然後，哎，左下角那個地方大概都是三角形。
也就是我做的事情，實際上有一點像，讓這六個分類器做投票的動作。它要投方塊還是要投
三角形，還是要投什麼東西，或者是把這六場，想成在打一場比賽
的話，哎，就看看啊，這個比賽的冠軍到底是誰，對每一個點 都像打了六場比賽，然後看看冠軍的選項到底是哪一個。
好，所以這是我們介紹給大家另外一個方法，OK，一般叫做，One-versus-on- e，OVO，跟剛才的OVA
只差一個字，那因為它最後這個比較，我拿一個Class出來，跟它比較是另外一個Cla- ss，而不是其他數的Class。
它做的事情一樣，很簡單，跟OVA一樣。OK，做的事情是，我原來資料拿來之後，
我先把原來的資料轉成，我要選哪一個Binary Classification，它對應的資料是什麼？
那每一個轉換的動作，牽扯到兩個Class，其中一個Class當做正1，另外一個Cl- ass當做負1。
好，那所以，今天如果是，原來是四個Class的話，我就產生六個分類器，產生這六個分- 類器之後，最後我怎麼
做預測？我讓這六個分類器去投票，或者去，哎，像在打比賽一樣。看看到底哪一個
類別獲得最高的支持，或者，哎，它是得，得到冠軍的類別。
好，那這樣的方法有什麼特點呢？首先它很有效率，很有效率的其中一個原因，並不是
哎，我們看說，哎，它要做，我今天有四個類別，它，它要做六個Classificati- on，這樣怎麼會有效率呢？
可是注意到，它每一個Classify，要用做訓練的時候，用的資料量是比原來的資料要- 少的。因為
它就是切拿的兩個類別，例如說，我今天要看方塊跟三角形的，我就只有拿方塊跟三角形的資- 料出來，切掉的資料有點像是丟掉了一樣。
所以因為它每一輪是解一個比較小的問題，所以整體來說，它可能會是比較有效率的。
那另外呢，它可以跟任何的Binary Classification的方法搭配，我想
這個大家應該很容易想象，就跟剛才我們講OVA一樣，非常的General。
好，那壞處是什麼呢？壞處是，哎，我們剛才講了K平方，或者嚴格來說是K取2這件事情，
會導致首先，我們有這麼多的W，我有，例如說我有六個W向量。
好，所以呢，我就要花六倍的力氣，我要花六的力氣去儲存這些W。好，或者是去，這個
如果在預測的時候，我要把六個W都算出來，分數都算出來，然後最後再看看，哪一個是比賽- 的贏家。
所以預測的時間會拉長，儲存的空間會變大，然後，那實際上呢，
Training，當然我還是，例如說我如果這邊要平均化做，我還是要多花幾台機器等- 等等等。
好，那不過呢，這跟OVA一樣，是一個簡單的方法，很好用。常常用至少特別是你的K，- 如果沒有
非常非常多的時候，實際上OVO是一個很好用的方法，而且它相對來說， 還蠻穩定的，這是因為，哎，中間這個打比賽的過程，
確保了說，哎，我有一些不同的分類方式，然後我想辦法 用投票的方式，好像民主的機制一樣，去找出那個最好的結果。
好，那我們就來算一算，OK，所以說我們用OVO這樣的方式的話，好，那，我
到底要花的時間的力氣是多少，那我們這邊給大家一個假想的問題，說如果我一個Binary Classification的演算法，
它要花的力氣跟資料量來說，大概就是三次方的關係。然後呢，再來，我有OVO這樣的問題，
然後我拿到的資料大概是平均的，也就是例如說，我有十個類別，每個類別就大概是1/10- 的資料化。
好，那我總共要花多少的力氣。好，那大家想一想之後，我希望大家會算出正確的答案
是2。OK，因為我們有K取2那麼多個，這個Classify，所以例如說我10個的話- ，我是有45個分類器。
但是每個分類器只用1/5的資料去做訓練，好，所以如果我這樣算下去的話，我就
會得到2的答案。注意到你如果用OVA的話，你要花的就是10倍N三方的力氣。
好，這是跑不掉的，然後所以OVO在這個時候可能會比OVA省力氣一些。
好，那我們今天呢，更豐富了大家對Classification上面，可以用的方法的一- 些想象，我們
首先先講到說，我們之前講的三個Linear Model，實際上 都可以看成要用來做Binary Classification。
然後呢，我們又把Logistic Regression延伸到，哎，我可以用SGT的方式來做，然後
做這樣之後，我發現Logistic Regression跟PLA其實非常地有關係。
那麼最後，我跟大家講了兩種不一樣的做多類別分類的方法。一種是用一個類別跟其他
類別比，然後來看看哪一個的可能性最高。然後另外一種，則是類別之間兩兩比較，然後最後- ，打一場比賽，看誰
是冠軍。好，那這是我們今天跟大家介紹的Classification的方法。
到今天以前，我們跟大家介紹的方法，都集中在線性，也就是我腦袋裡都有一個W在那邊。
然後這個W跟我原來的這些x算出分數以后，再拿那些分數來做事情。
那在下一次的課程，我們會開始從線性移到非線性的。也就是說，我們
會想要做更複雜的，例如說，不是直線，也許是二次曲線，也許是三次曲線
的分類方式出來。那希望大家下一次回來，跟我們一起學習這個有趣的課題，謝謝。感謝 (台語).
[音樂]
[音樂]
[音樂]
[音樂]
Hsuan-Tien Lin, 林軒田教授 (Professor)
