[機器學習]VC維(未完)

作者: RJ阿杰 | 来源:发表于2018-11-02 17:36 被阅读0次

[機器學習]VC維(未完)
【機器學習特訓營】第一週-簡介、KNN算法 | 貪心學院
機器學習&應用
機器學習學習心得--Lecture 1
你說學習吧
機器學習學習心得--Lecture 2
忍住
一課機器學習
continuous learner
《精进》如何成为一个很厉害的人

機器學習類型

預測已知資料

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

預測未知資料

學習架構

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

前言
假設若還有一個未知資料(藍圈)，我們並不能保證能夠完全預測，此時若要預測未知資料，我們需要作些假設。
Hoeffding’s Inequality
假設有一個罐子，裡面有橘球跟綠球，抽到橘球可能性為 $\mu$ ，抽到綠球可能性為 $1-\mu$ ，從罐子中抽 $N$ 個，橘球的比例為 $\nu$ ，綠球比例為 $1-\nu$ ， $\epsilon$ 為 $\nu 跟\mu$ 的差距(誤差) $。$
Hoeffding’s:
$P[|\nu - \mu| > \epsilon] \le 2e^{-2 \epsilon^{2}N}$
在N非常大時， $\nu \approx \mu$ $。$
套用到學習架構
我們假設罐子裡有很多球，每個球為一個樣本( $x$ )，若將 $x$ (球)輸入給 $h$ ，得到 $h(x)$ 預測結果，若將 $x$ (球)輸入給 $f$ ，得到 $f(x)$ 真實結果 $。$
如果 $h(x) \neq f(x)$ 將球漆成橘色，如果 $h(x) = f(x)$ 將球漆成綠色，我們取 $n$ 個球出來作為資料 $D=\{(x_n,y_n)\}$ ， $y_n$ 又等於 $f(x_n)$ ，第一筆資料就是 $(x_1,f(x_1) )$ $。$
我們能否從 $h(x_n)$ 是否等於 $y_n$ 推論出 $h(x)$ 是否等於 $f(x)$ ?
得到(橘球可能性 $\mu$ 以及橘球比例 $\nu$ )
我們假設 $x$ 樣本的機率分怖是由一個機率 $P$ 產生的 $。$
$E_{in}:h(x)在樣本的錯誤率$
$E_{out}:h(x)在實際群體的錯誤率$

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

由Hoeffding 我們可以知道，我們只需要知道 $N$ 跟 $\epsilon$ ，就可以知道 $\mu(E_{out})$ 跟 $\nu(E_{in})$ 大於誤差的機率，不需要知道 $E_{out}$ 以及 $f$ 與 $P$ $。$
例如:
$E_{in}:h(x)在樣本的錯誤率$ =0.01=1%， $E_{out}:h(x)在實際群體的錯誤率$ =0.02=2%
$\epsilon$ = 0.01， $N$ = 20000， $\mu(E_{out})$ 跟 $\nu(E_{in})$ 大於誤差的機率 = 0.0366 = 3.6%
當 $\epsilon$ 誤差越大，發生的機率越小，所以 $\mu(E_{out})$ 會接近於 $\nu(E_{in})$ ，此時如果 $\nu(E_{in})$ 很小， $h \approx f$ $。$

選擇 $h$

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

壞的資料
假設我們有 $M$ 個 $h$ 要選擇，我們有很多筆資料，如果同一資料中對應的 $h$ 有其中一個是 $BAD$ 我們就說這是一個不好的資料 $。$
由下圖推導我們可以知道， $M$ 越大會導致 $h \neq f$ 的機率上升，如果我們 $N$ 夠大，在有限個 $M$ 中，我們可以說 $E_{in}$ 小的時候， $h \approx f$ $。$
我們使 $(E_{out}) \approx (E_{in})$ 就像在驗證(validation)數據(test)，而使 $(E_{in} \approx 0$ 就像在訓練(train)數據 $。$
M的大小
$M$ 如果很小，我們說 $h \approx f$ 機率大，但 $h$ 小我們可以選的h太少，可能可以選的 $h$ 裏頭並沒有一個 $h$ 是接近 $f$ 的，但 $h$ 大我們抽中壞資料的機率又會增加，所以我們必須選擇一個大小剛好的 $M$ $。$
代換M
對於一個假設空間中， $M$ 可能是無窮大的。要能夠繼續推導下去，那麼有一個直觀的思路，能否找到一個有限的因子 $m_H$ 來替代不等式約束中的 $M$ ，雖然假設空間(hypotheses set)很大，多個 $h$ 之間並不是完全獨立的，他們是有很大的重疊的，也就是在中號個假設中，可能有一些假設可以歸為同一類 $。$
h分類

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

effective(N)
effective(N)為 $H$ 作用於資料中，最多能產生多少個dichotomies，這個又稱為“成長函數”（growth function） $= m_H(N)$ ，例如：在2D perceptrons中， $m_H(1)=2$ ， $m_H(2)=4$ ， $m_H(3)=8$ ， $m_H(4)=14$ $。$
不同情況的Growth Function
Break Point(k)
Break Point 就是 $m_H(N)$ 開始小於"數據 $x$ 的排列組合數"時的N值 $。$
例如：在2D perceptrons中， $N \ge 4$ 時， $m_H(N) < 2^N$ 才發生， $(14 < 16)$ ，所以Break Point = 4 $。$
例如：在positive rays中， $N \ge 2$ 時， $m_H(N) < 2^N$ 才發生， $(3 < 4)$ ，所以Break Point = 2 $。$
Shatter

在 $m_H(N)$ 還沒到達Break Point(k)時，我們稱"這 $N$ 個 $x$ 被 $h$ 給Shatter，如果說Break Point = 2就表示，任兩點 $x_1,x_2$ 不能被Shatter $。$

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

例:求 $(N=3，K=2)的Bounding Function$

首先我們給一個任意dichotomies $(OOO,XXX)$ ，也可以是 $(OXO,XXX)、(OOX,XOX).....$ ，N個 $x$ 的二元排列組合，但不能重複 $。$

檢查我們取任2個(k個) $x$ 能不能由dichotomies產生 $(OO,OX,XO,XX)$ 全部的排列組合

不行再加入新任意的dichotomies(不跟之前重複)，重新檢查取任2個(k個) $x$ 能不能由dichotomies產生 $(OO,OX,XO,XX)$ 全部的排列組合

直到加入某個任意的dichotomies(不跟之前重複)，不管如何改變dichotomies $(OXO、XOX...)$ (不跟之前重複)，取任2個 $x$ 都不能由dichotomies產生(oo,ox,xo,xx)全部的排列組合，此時的上一個dichotomies數目就是 $Bounding Function$

$(N=3，K=2)的Bounding Function$ = 4

參考:

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

[機器學習]VC維(未完)
機器學習類型預測已知資料如下圖已知資料中，我們使用PLA可以預測6個已知資料預測未知資料學習架構為群體參...
【機器學習特訓營】第一週-簡介、KNN算法 | 貪心學院
機器學習的概念：大數據、數據挖掘、機器學習，這三者是不同但有重合的領域而人工智能、機器學習、深度學習的關係是這...
機器學習&應用
1/什麼是機器學習：什麼是學習？利用經驗來提升自己，從而獲得理解以及解決問題的能力什麼是機器學習？讓計算機...
機器學習學習心得--Lecture 1
什麽是學習？學習是一種觀察。觀察->學習->技能。 _ 機器學習即是人類通過電腦來模擬學習的一種過程_ 在電腦的...
你說學習吧
你說我這學習和不學習有什麼區別呢無非是點進去退出來昨天看了寫視頻跟著學霸做題其實跟他的思維比聽機構的課好一...
機器學習學習心得--Lecture 2
什麽樣的機器學習演算法可以做是非題？流程回顧：模型：上圖公式中 w 是這個維度的重要性。h 表示的是所有可能...
忍住
學習時不要看手機。
一課機器學習
说是一课机器学习，其实只讨论神经网络。神经网络首先被看作是一种「学习算法」。因此，我们有必要先对「学习」做一番探讨...
continuous learner
只有學習和知識能創造思維和自信。不斷的提升自己只有通過學習學習專業知識，溝通能力，情商，抗壓能力。
《精进》如何成为一个很厉害的人
不是想著要如何成為一個很厲害的人，而是想學習他們的思維方式。本書從七個側面：時間、選擇、行動、學習、思維、才能和成...