機器學習類型

預測已知資料

如下圖已知資料中，我們使用PLA可以預測6個已知資料

預測未知資料

• 學習架構
  

為群體參數，為一個函數(就是我們想由機器學習得到的那個真實的x)，輸入得到
(資料)為由群體取出的樣本參數加上雜訊，為一個函數，輸入得到
為推測可能為函數的集合

• 前言
  假設若還有一個未知資料(藍圈)，我們並不能保證能夠完全預測，此時若要預測未知資料，我們需要作些假設。
  

• Hoeffding’s Inequality
  假設有一個罐子，裡面有橘球跟綠球，抽到橘球可能性為，抽到綠球可能性為，從罐子中抽個，橘球的比例為，綠球比例為，為的差距(誤差)
  Hoeffding’s:
  
  在N非常大時，
  

• 套用到學習架構
  我們假設罐子裡有很多球，每個球為一個樣本()，若將(球)輸入給，得到預測結果，若將(球)輸入給，得到真實結果
  如果將球漆成橘色，如果將球漆成綠色，我們取個球出來作為資料，又等於，第一筆資料就是
  我們能否從是否等於推論出是否等於?
  

• 得到(橘球可能性以及橘球比例)
  我們假設樣本的機率分怖是由一個機率產生的
  
  
  

  所有樣本機率總和除以樣本數(平均)

• 帶入Hoeffding

1. 由Hoeffding 我們可以知道，我們只需要知道跟，就可以知道跟大於誤差的機率，不需要知道以及與
2. 例如:
   =0.01=1%，=0.02=2%
   = 0.01， = 20000，跟大於誤差的機率 = 0.0366 = 3.6%
3. 當誤差越大，發生的機率越小，所以會接近於，此時如果很小，

• 選擇

1. 目前我們只有選擇一個固定的，我們還無法找出，我們每個選擇的h都代表一個罐子，而我們抽出N個樣本，當h很多時，我們看見樣本中有一個全為綠色()的球，那麼它是最佳的h嗎?
   其實並不一定，因為當h越大，表示我們從很多罐子中抽取同樣的那幾顆的球，有可能在某個中剛好這些都是綠色，而並非罐子全為綠色
   

• 壞的資料
  假設我們有個要選擇，我們有很多筆資料，如果同一資料中對應的有其中一個是我們就說這是一個不好的資料
  由下圖推導我們可以知道，越大會導致的機率上升，如果我們夠大，在有限個中，我們可以說小的時候，
  我們使就像在驗證(validation)數據(test)，而使就像在訓練(train)數據
  

• M的大小
  如果很小，我們說機率大，但小我們可以選的h太少，可能可以選的裏頭並沒有一個是接近的，但大我們抽中壞資料的機率又會增加，所以我們必須選擇一個大小剛好的
  

• 代換M
  對於一個假設空間中，可能是無窮大的。要能夠繼續推導下去，那麼有一個直觀的思路，能否找到一個有限的因子來替代不等式約束中的，雖然假設空間(hypotheses set)很大，多個之間並不是完全獨立的，他們是有很大的重疊的，也就是在中號個假設中，可能有一些假設可以歸為同一類
  

• h分類

1. 如果我們的算法要在平面上（二維空間）挑選一條直線方程作為g，用來劃分一個點，假設空間是所有的直線，它的尺寸是無限多的
   2.dichotomies是指被分為二元類別
2. 但是實際上可以將這些直線分為兩類，一類是把判斷為，另一類是把判斷為，(dichotomies = 2)
   那如果在平面上有兩個數據點，，可以分為類(dichotomies = 4)
   3個數據點，中最多有8類直線(dichotomies = 8)
   4個數據點，中最多有14類直線(dichotomies = 14)，有2種情況無法線性分類
   前面3種狀況dichotomies都等於數據的排列組合數，只有時，才發生
   

• effective(N)
  effective(N)為作用於資料中，最多能產生多少個dichotomies，這個又稱為“成長函數”（growth function），例如：在2D perceptrons中， ， ，，
  

• 不同情況的Growth Function
  

• Break Point(k)
  Break Point 就是 開始小於"數據的排列組合數"時的N值
  例如：在2D perceptrons中，時，才發生，，所以Break Point = 4
  例如：在positive rays中，時，才發生，，所以Break Point = 2
  

• Shatter

1. 在還沒到達Break Point(k)時，我們稱"這個被給Shatter，如果說Break Point = 2就表示，任兩點不能被Shatter

• Bounding Function
  若給我們N以及k，我們如何求得Bounding Function，在個中，給幾個dichotomies之後，才能使其中任意個都不能被dichotomies給shatter

例:求

1. 首先我們給一個任意dichotomies，也可以是，N個的二元排列組合，但不能重複
2. 檢查我們取任2個(k個)能不能由dichotomies產生全部的排列組合
3. 不行再加入新任意的dichotomies(不跟之前重複)，重新檢查取任2個(k個)能不能由dichotomies產生全部的排列組合
4. 直到加入某個任意的dichotomies(不跟之前重複)，不管如何改變dichotomies(不跟之前重複)，取任2個都不能由dichotomies產生(oo,ox,xo,xx)全部的排列組合，此時的上一個dichotomies數目就是

• = 4
  

參考:

1. 林軒田老師機器學習基石課程(想詳讀的可以找coursera)
2. 參考李宏毅老師ML課程