Caltech Learning from Data 1 - The learning problem

特別幫Caltech做一個筆記，為何？

因為這是Caltech校內正式課程，跟edX平行提供的，caltechㄟ.....頂級名校（話說為何CMU都不提供MOOCs?)

syllabus號稱：上完這個edX課程，你將擁有跟頂級名校學生一樣對ML的認知與能力，吸引人，不學嗎？

這門課把課堂內的錄影直接放到edX，所以一堂課的時間是....1hr!!!!

好吧，好有挑戰性。筆記應該會很難寫。

Learning Model

Learning的過程如下：

Hypothesis set就是妳挑選的（不挑選就是所有符合Input/output的functions)某些function set，或者說models，例如一個hypothesis set可能有包括SVM, Bayes classifier, Logistic regression三種model，而相對應的learning algorithm則不一樣。

一個hypothesis（例如Neural Network) 搭配一個learning algorithm (例如back propagation)，就形成一個所謂“learning model"。

一個信用卡判斷是否會fraud的hypothesis model如下，採用perceptron model，

wi 和 threshold就是這個model的參數，這決定了decision boundary。
xi是某個顧客的input feature vector，經過weighted sum之後，去和一個threshold做比較，最後再取其sign，大於零代表不是fraud，反之則為fraud。

threshold as w0

這個threshold可以重寫成w0 symbol:

這是為了notation方便起見：

所以以後就直接把hypothesis寫成這樣，只要在input vector加上x0 = 1的item 即可。
可以更簡化寫成vector form:

Perceptron Learning Algorithm (PLA)

hypothesis function需要藉由learning algorithm來找出最逼近理想target function的參數w。

對perceptron來說，misclassified的意義是：

也就是如果yn > 0，則vector w和vector xn的夾角應該會 > 90度，內積才會是負的：

同理 yn < 0 兩者夾角應該要 < 90度，才會misclassified。

所以perceptron learning algorithm (PLA) 事實上就是要調整w vector，使得最後w 和 Xn的夾角處於正確角度（>90度或是小於90度）：

所以PLA演算法如下：
每個iteration，選擇某個misclassified point，然後進行w vector的調整，使之correctly classified。
如果兩個classes是linear separable，則PLA終究會找出正確的decision boundary (final target function g)來劃分出兩個classes。