機器學習可行性
在銀行評估貸款申請人的授信請求前，會進行風險評估朽砰。符合申請則通過尖滚，反之駁回。長時間的數(shù)據(jù)和申請使得銀行從中找到了一些規(guī)律并開始learning瞧柔，所以風險評估就是一個learning的過程漆弄，流程圖如下：
首先target function我們是未知的，需要求解的造锅。D就是我們的訓練數(shù)據(jù)撼唾，hypothesis set就是我們的假設(shè)集合，也就是說我們的最佳函數(shù)g就是要從里面選擇备绽，learing algorithm我們稱為演算法券坞，使用這個演算法來選擇最好的g，最后達到g ≈ f的結(jié)果肺素。
先介紹一個Perceptron Algorithm---感知機
為每一個特征向量設(shè)置一個w，所以的wx相加如果大于某一個閾值宇驾，我們就設(shè)置為正例倍靡，approve credit；否則就deny了课舍。
但其實我們一般會把閾值加進來一起預測塌西，因為如果分開的話求導計算或者其實算法計算要分兩部分。
如下變換：
設(shè)置一個X0筝尾，我們稱為是1捡需。
對于這個perceptron，對于不同的權(quán)值集合筹淫，我們就有多少種不同的線段站辉，而這些不同的線段，其實就是假設(shè)集合损姜，剛剛所說的hypothesis set饰剥。
perceptron的學習
一開始我們的權(quán)值肯定是一個隨機值，那么學習的過程就是一個轉(zhuǎn)變方向的過程了摧阅。我們通過第一個錯誤進行逐步的修正：
當發(fā)現(xiàn)了一個錯誤汰蓉，那么這個錯誤肯定和我們預知的范圍是相反的，比如一個mistake棒卷，wx < 0 顾孽，意味著是在圖像的下方祝钢，而w是法向量，那么就會出現(xiàn)w和mistake的夾角就是大于90度的了若厚，所以需要小于90度拦英，則只需要加上yx即可，y代表要旋轉(zhuǎn)的方向盹沈。
但是每一次的改變有可能使得correct的點變成mistake龄章，但是沒有關(guān)系，迭代下去總可以找到最好的一個g乞封。
perceptron的停止條件
對于一個集合D做裙，如果是線性可分的，自然就分開了肃晚，但如果是線性不可分的锚贱，你們感知機就不會停止，一直迭代下去关串，因為只要有錯誤就一直進行迭代而不會找到最佳的g ≈ f拧廊。
當然對于非線性的情況我們不考慮，對于線性可分的情況晋修，我們可以用公式表明W在變化的過程中確實是越來越接近Wf的恩沛。
當一個向量越接近一個向量的時候甘晤，如果這兩個向量是單位向量，那么越接近自然越大，所以如果W*Wf變大娜汁，就可以證明percetron確實是可以學習的际长。
YnWfXn>0餐屎。因為y就是根據(jù)WX來分類的场靴，這兩的正負號肯定是一樣的。
但是增大的可能性其實還有可能是這逼長度變化了忠怖，導致增大呢堰，所以我們要證明
是不斷增大的。
推導流程如下：
所以可以證明W是隨著時間的增長不斷的靠近Wf的凡泣，perceptron的學習就被證明是有效的了枉疼。
回到我們要講的機器學習可行性
舉一個例子，現(xiàn)在有一個九宮格要我們來找規(guī)律推測出第三個九宮格里面的內(nèi)容：
不同的學習方法找到的規(guī)律是不一樣的问麸，得到的g(x)也不一樣往衷。給出的這個例子里面的六個九宮格其實就是機器學習里面的數(shù)據(jù)D，我們可以找到并且看見的严卖，而那個我們需要預測的就是我們看不見并且要預測的大數(shù)據(jù)席舍。比如剛剛的credit card，我們要預測的其實就是所有人哮笆，而不是僅僅的只是數(shù)據(jù)集里面的来颤。
在機器學習基石里面老師用了一個bin的例子：
在訓練集D以外的樣本上汰扭，機器學習的模型是很難，似乎做不到正確預測或分類的福铅。那是否有一些工具或者方法能夠?qū)ξ粗哪繕撕瘮?shù)f做一些推論萝毛，讓我們的機器學習模型能夠變得有用呢？
比如裝有一個很多球的罐子：
其實這個罐子就是hypothesis set里面的一個h(x) 滑黔。罐子里面的球其實本來是沒有顏色的笆包，我們依照h(x) 的分布，把這里面的求都用油漆涂成orange and green略荡。orange代表錯誤庵佣，而green代表正確。抽樣抽出來的小球其實就是我們的數(shù)據(jù)集set汛兜，就是已經(jīng)拿到并且是帶了label那種巴粪。
我們現(xiàn)在就是要確定能否用抽樣的比例來確定罐子里面的比例呢？
u是罐子里面orange的比例粥谬，而v則是抽樣抽到的orange的比例肛根。那么根據(jù)霍夫丁不等式有：
P[|v?u|>?]≤2exp(?2?2N)
當N很大的時候其實兩個都是差不多的。
我們把u ≈ v稱為probably approximately correct(PLA)漏策，近似相等派哲。
聯(lián)系到機器學習上面
我們將罐子的內(nèi)容對應到機器學習的概念上來。機器學習中hypothesis與目標函數(shù)相等的可能性掺喻，類比于罐子中橙色球的概率問題狮辽；罐子里的一顆顆彈珠類比于機器學習樣本空間的x；橙色的彈珠類比于h(x)與f不相等巢寡；綠色的彈珠類比于h(x)與f相等；從罐子中抽取的N個球類比于機器學習的訓練樣本D椰苟，且這兩種抽樣的樣本與總體樣本之間都是獨立同分布的抑月。所以呢，如果樣本N夠大舆蝴，且是獨立同分布的谦絮，那么，從樣本中h(x)≠f(x)的概率就能推導在抽樣樣本外的所有樣本中h(x)≠f(x)的概率是多少洁仗。
理解的關(guān)鍵是我們需要通過抽樣來知道h(x)的錯誤概率是多少层皱，通過局部推廣到全局。
這里要引入兩個值：Ein值的是抽樣的錯誤率赠潦，Eout指的是全局的錯誤率叫胖，這里就是指h的錯誤率了。
使用霍夫丁不等式：
P[|Ein(h)?Eout(h)|>?]≤2exp(?2?2N)
inequalty表明：在h確定了她奥，N很打的情況下瓮增，Ein ≈ Eout怎棱，但這并不代表g≈f，因為我們后面還要知道Ein ≈ 0才行绷跑。
類比到機器學習上面
hypothesis set里面有多少個h就有多少個罐子拳恋。
但是在抽樣過程中還有可能抽到壞的數(shù)據(jù)，bad sample砸捏。比如你丟一個硬幣谬运，三次向上一次向下，這并不能說明這個硬幣正反面不均勻垦藏。
所以抽樣也有可能抽到壞樣本梆暖。
這么多個數(shù)據(jù)集，根據(jù)霍夫丁不等式膝藕，在大多數(shù)情況下式廷，抽樣得到的數(shù)據(jù)其實都是好數(shù)據(jù)，Ein ≈ Eout的芭挽，但是會有極小的情況下會出現(xiàn)Ein 和 Eout相差很大的情況滑废。也就是說，不同的數(shù)據(jù)集Dn袜爪，對于不同的hypothesis蠕趁，有可能成為Bad Data。只要Dn在某個hypothesis上是Bad Data辛馆，那么Dn就是Bad Data俺陋。只有當Dn在所有的hypothesis上都是好的數(shù)據(jù)，才說明Dn不是Bad Data昙篙，可以自由選擇演算法A進行建模腊状。那么，根據(jù)Hoeffding’s inequality苔可，Bad Data的上界可以表示為連級（union bound）的形式：
意味著缴挖，如果M是有限的，N很大焚辅，那么我們出現(xiàn)bad sample的概率會很小映屋，Ein ≈ Eout就可以成立，再選取一個合理的演算法同蜻，就可以得到g ≈ f棚点，機器學習就有效了。這樣就有了不錯的泛化能力湾蔓。
要解決的問題已經(jīng)M的處理
上面的講解過后機器學習的流程：
于是就回歸到了兩個問題：
①Ein ≈ Eout
②Ein ≈ 0
M就是代表hypothesis set里面h的數(shù)量瘫析，M小，可以達到bad sample概率小但是選擇就少了，而大的話就有可能變成大概率了颁股。所以M需要不大不小的么库。
但事實上很多機器學習的hypothesis set都是M無限大的诉儒，比如SVM忱反，linear regression滤愕，logitic regression他們的M都是無限大的间影，但他們的學習都是有效的魂贬，所以付燥，很明顯這里的M是可以被替換掉的键科。替換成一個有限的mH勋颖。
對M的處理
hypothesis set是無限的，但他的種類肯定是有限的酸钦，比如2D-perceptron要分類一個數(shù)據(jù)點：
在這個分類里面，hypothesis set是無限多個的蚕断，因為不同的w集合就不同的直線亿乳，但他的分類種數(shù)卻只有兩種葛假，要不X要不O聊训，就兩種带斑，所以可見勋磕，很多的H是有重疊的。
如果有兩個點：
就四種情況。
到了三個點的時候幔虏，情況有所不一樣：
這樣是8種情況所计。
我們自然是要找最多的了踪栋，所以3個點2分類就是8種情況夷都。
四個點就是14種情況囤官。
所以我們的M其實可以被有限個替代的党饮。如果可以保證是小于2^n次方刑顺，也就算是無限大的蹲堂，他的種類也是有限的柒竞。
成長函數(shù)
成長函數(shù)的定義是：對于由N個點組成的不同集合中能犯，某集合對應的dichotomy最大执泰，那么這個dichotomy值就是mH(H)术吝，它的上界是2N：
而我們剛剛的例子：
我們現(xiàn)在要做的就是要討論如何限制成長函數(shù)，得到表達式或者是找到上界淘衙。
成長函數(shù)的討論
對于一維的positive rays（正射線）：
當N = 1
mH(1) = 2
當N = 2
mH(2) = 3
所以他的mH(N) = N + 1
對于一維的positive intervals：
下面推導可以得到：
而對于一個凸集合：
他的成長函數(shù)就是2^n次方了。
所以可以看到在某些情況下具垫，成長函數(shù)增長到一定情況下，會被限制铺坞，也就是在那個地方會小于2^n济榨。
而這個點腿短，我們就稱為break point橘忱。在這個點和這個點以后钝诚，任何兩點都不能被shatter凝颇。
shatter的意思：比如你有一把散彈槍拧略，要求你每一關(guān)都要一槍打死所有人垫蛆，第一關(guān)的時候袱饭，你一槍可以打死所有人虑乖，第二關(guān)也可以疹味，第三關(guān)不行了佛猛，那么3就是break point了继找。
positive rays：N = 1的時候幻锁，shatter的情況就是 這個點等于x,o哄尔，而很明顯可以達到岭接。N = 2的時候鸣戴，shatter的情況就是xx ,oo,xo ,ox，而ox是達不到的窄锅，所以2就是break point了，而N = 3的時候入偷，就更加不能被shatter了。如果是三分類疏之，那就要求任何三個點都不能被shatter。
其他的情況也是一樣：
能不能shatter体捏，就是看他能不能有2n種分類河泳，三分類就是3n種了某抓。
mH(N)的限制
現(xiàn)在我們確定了汉矿，break point絕逼是mH(N)的一個限制曲尸，因為在那個點開始就不再是2^n的規(guī)律了另患。
我們現(xiàn)在要證明的就是，上界是plot(N)。
對于mH(N)夕吻，因為不同的模型對應的mH(N)不一樣的归园，所以直接討論mH(N)是很困難的晤揣，我們可以找一個上界钠四，要討論mH(N)就直接討論上界就好了甸祭。上界我們設(shè)為B(N , K)。
第一列肯定是1了斟湃。
當N < K的時候注暗，肯定是2^n次方
當N = k的時候，這個時候是第一次不能被shatter的情況，小于2n，那就設(shè)為2n-1吧。其實就是算在N個點K個點不能被shatter的情況下，有多少種mH(N)。
填上三角其實很簡單，現(xiàn)在填下三角了。
先寫出B(4,3)的所以情況：
把他劃分下：
上面橙色的作為a漆羔，下面紫色的作為b鸟顺，有：
所以我們可以得到：
進一步推廣：
所以整個就是：
最后根據(jù)遞推公式，可以得到：
所以B(N ,K)的上界滿足多項式曲楚。
最后我們就得到M的上界是一個多項式。
正常的想法是帶回原式：
但這樣是不行的粗截，因為一個M就對應這一個Ein婿屹，但是Eout是無限個的，而替換了M成mH(N)之后扩所，這個Ein就是有限的了，兩個級數(shù)不同是不可以進行計算的。所以正確的公式：
怎么證明就不說了儒鹿。最后的結(jié)果我們叫做VC bound：
總結(jié)一下流程：首先，我們的M是無限的众雷，現(xiàn)在想要替換成有限個编兄，于是我們找上界碰煌，找到了break point，發(fā)現(xiàn)這個點可以打破指數(shù)增長的規(guī)律壳澳；而對于不同的維度模型mH(N)是不同的锉屈，于是儡炼，準備一個上界函數(shù)B(N , K)唬党，這樣就不用再考慮維度問題了蓝纲，直接找上界函數(shù)即可慕嚷；之后又找到B(N , K)的上界函數(shù)是一個多項式。于是就保證了這個M是可控制的。
VC dimension
順便說一下邊界喝检。
這樣嗅辣，不等式就只和K，N有關(guān)系了挠说。根據(jù)VCbound理論：如果空間H有break point k澡谭，且N足夠大，則根據(jù)VC bound理論纺涤，算法有良好的泛化能力译暂；如果在H空間中有一個g可以使得Ein ≈ 0，則全集數(shù)據(jù)集的錯誤率會偏低撩炊。
下面介紹一個新名詞：VC dimension
VC Dimension就是某假設(shè)集H能夠shatter的最多inputs的個數(shù)外永，即最大完全正確的分類能力。其實就break point - 1拧咳。因為break point是最小任何兩個點都不可被shatter的點伯顶。
來看一下之前的幾個例子，他們的VC dimension是多少：
現(xiàn)在我們用VC dimension來代替K祭衩，那么VC bound的問題就轉(zhuǎn)換成了VC dimension和N的問題，自然就解決了第一個問題——Eout ≈ Ein阅签。
VC dimension of perceptron
已知Perceptrons的k=4掐暮，即dvc=3。根據(jù)VC Bound理論政钟，當N足夠大的時候路克，Eout(g) ≈ Ein(g)。如果找到一個g养交，使Ein(g)≈0精算，那么就能證明PLA是可以學習的。
這是在2D的情況的情況下碎连，如果是多維的呢付材？
1D perceptron 综苔， dvc = 2苦锨；2D perceptron 矗烛， dvc = 3，我們假設(shè)倒戏，和維度有關(guān)前鹅，d維，那就是d+1峭梳。
要證明只要分兩步：
dvc >= d+1
dvc <= d+1
證明dvc >= d+1
在d維里面舰绘，我們只要找到某一類的d+1個輸入可以被shatter就可以了蹂喻。因為找到一個符合的，其他就可以得到dvc >= d+1捂寿。
我們構(gòu)造一個可逆的X矩陣：
shatter的本質(zhì)是假設(shè)空間H對X的所有情況的判斷都是對的口四，意味著可以找到權(quán)值W滿足W*X = Y，而W = X^-1 * Y秦陋，所以可以得到對于d+1個輸入是可以被shatter的蔓彩。
證明dvc <= d+1
在d維里，如果對于任何的d+2個inputs驳概，一定不能被shatter赤嚼，則不等式成立。
我們構(gòu)造一個任意的矩陣X顺又，其包含d+2個inputs更卒，該矩陣有d+1列，d+2行稚照。這d+2個向量的某一列一定可以被另外d+1個向量線性表示蹂空，例如對于向量Xd+2，可表示為： Xd+2=a1?X1+a2?X2+?+ad+1?Xd+1果录。所以他的自由度只有d+1,因為確定了d+1個上枕，d+2個就知道了。
所以綜上所述dvc = d+1
VC dimension的理解
在perceptron中的W弱恒，被稱為是features辨萍。W就像按鈕一樣可以隨意調(diào)節(jié)，所以也叫自由度返弹。VC Dimension代表了假設(shè)空間的分類能力锈玉，即反映了H的自由度，產(chǎn)生dichotomy的數(shù)量琉苇，也就等于features的個數(shù)。
比如悦施，2D的perceptron并扇，VC dimension是3,而W就是{W0,W1,W2}。
回到VC bound
上面的VC維告一段落了抡诞，回到VC bound穷蛹。
這是我們之前推導得到的VC bound。
根據(jù)之前的霍夫丁不等式昼汗，如果|Ein?Eout|>?肴熏，那么他發(fā)生的概率就不會超過δ；反過來顷窒，發(fā)生好的概率就是1-δ蛙吏。
我們重新推導一下：
于是我們可以得到：
事實上前面的那個我們并不會太關(guān)注他源哩，所以有：
Ω我們稱為是模型的復雜度，其模型復雜度與樣本數(shù)量N鸦做、假設(shè)空間H(dvc)励烦、?有關(guān)。下面是他們的圖像：
該圖可以得到如下結(jié)論：
dvc越大泼诱，Ein越小坛掠，Ω越大（復雜）。
dvc越小治筒，Ein越大屉栓，Ω越小（簡單）耸袜。
隨著dvc增大友多，Eout會先減小再增大。
所以并不是越復雜的模型越好句灌，這其實就是過擬合的理論基礎(chǔ)夷陋，在訓練集上表現(xiàn)的很好，但是在測試集上就很糟糕胰锌∑疲看到這我就知道差不多理解了，舒服资昧！
理解實際問題linear regression to linear lassification
線性回歸是用來做回歸擬合的酬土，能不能做分類呢？學習過程也就是找到g ≈ f的過程可以不用擔心格带，因為regression已經(jīng)證明是可行的了撤缴，現(xiàn)在要解決的就是第一個問題---Eout ≈ Ein。
回歸模型的錯誤是err = (y - y)2叽唱，而分類模型的錯誤無非就是0和1屈呕。
當y = 1：
當y = -1
很明顯，回歸錯誤大于分類錯誤棺亭。
原來的有：
自然根據(jù)VC bound原理了虎眨。
當然上界更加寬松一點了，效果可以沒有之前的好镶摘，但是保證了Eout ≈ Ein的概率嗽桩。
