1
一牡直、課程大綱
1.1課程內(nèi)容介紹
1.1.1 Supervised Learning
關于監(jiān)督型學習方法捐腿，本課程涉及到的有Linear Regression缕减，Logistic Regression笼痛，Neural Network士八，SVMs容燕。
1.1.2 UnSupervised Learning
非監(jiān)督型方法中，本課程教授了K-means Clustering 曹铃，Principal Component Analysis和Anomaly Detection缰趋。
1.1.3 Special Application /Topic
在本課程中，除基本課程中的應用外陕见，還提及了幾種應用：
- Recommender System（推薦系統(tǒng)）
- Photo OCR（圖片中的文字識別）
另外提到的主題有： - Large Scale Machine Learning（在大數(shù)據(jù)量下的機器學習）
- Advice on building a machine learning system（一些機器學習系統(tǒng)設計的建議）
- Bias/Variance（應對overfit與underfit的方法秘血，Learning Curves學習曲線等）
- Regularization（一種處理overfit和underfit的具體辦法）
- Evalution of Learning Algorithm（如何評判算法效率：F1 Score與Cross Validation）
- Ceiling analysis（找到機器學習系統(tǒng)的瓶頸的方法）
1.2 課程脈絡描述
縱觀整個課程，Andrew Ng教授對機器學習的表述是非常統(tǒng)一的评甜，所以在課程的學習上灰粮，雖然是不同的方法，卻有很多類似的地方忍坷。下面大致描述一下課程對機器學習算法的描述方法：
- 所有的課程中提到的機器學習算法或工具粘舟，無論監(jiān)督方法和非監(jiān)督方法，都可以表述為一種對于模型參數(shù)進行優(yōu)化求解的過程（Optimization）佩研，也就是說柑肴，把所有的方法過程都看成是優(yōu)化問題。（無論是SVM旬薯，Neural Network晰骑，Linear Regression， K-mean Clustering等等绊序。）
- 這種表示方法有三個要素（也是Optimization的要素）硕舆，分別是：
a) h(params,x)函數(shù)：hypothesis，對于所有的監(jiān)督方法骤公，對于給定輸入樣本x抚官，計算出輸出y的方法。
b) J(params,x,y)函數(shù)：cost function阶捆，由優(yōu)化算法所使用凌节，給出對于樣本x，計算cost值的方法洒试。
c) grad(params,x,y)函數(shù)：由優(yōu)化算法所使用刊咳，給出參數(shù)修正值的計算方法，為了簡便起見儡司，在本課程中娱挨，一直使用Gradient Descent（也就是對每個參數(shù)進行求偏導，然后使用偏導值進行參數(shù)修改的方法）捕犬。
其中上述表示方式中的參數(shù)params即是我們的模型所需要的參數(shù)跷坝，也就是我們所要優(yōu)化求解的對象酵镜。（模型參數(shù)params像是Linear Regression的Theta， Neural Network的Weighted Matrix） - 課程對提到的所有算法進行闡述的時候柴钻，都采用上述的三要素進行表示淮韭，但是雖然這些模型都有這些要素，每個模型的三要素與其他模型的差別還是非常大的贴届。
另外靠粪，為了描述計算方便，本課程的所有代碼均為Matlab或Octave毫蚓，所有的練習也都由Matlab或Octave完成占键。
下面開始對課程進行總結。
二元潘、課程內(nèi)容總結
2.1 線性回歸：Linear Regression
線性回歸Linear Regression是Regression最簡單的一種畔乙，為什么叫線性呢，因為在上面提到的三要素中翩概，它的h(x)函數(shù)是線性的（說白了牲距，最簡單的情況就是在一個2D的圖上有一些點，線性回歸就是找到一條直線可以對這些點進行擬合钥庇，使總體的距離誤差最少）牍鞠。它的典型應用是根據(jù)房屋的大小和臥室數(shù)目對房價進行預測。
它的輸入為X评姨，y兩個矩陣皮服，其中
X是mn的矩陣，為m個樣本参咙，n個特征，每行代表一個樣本房屋的所有特征硫眯。
Y是m1的向量蕴侧，每行代表一個樣本房屋的實際售價。
2.1.1 Linear Regression的模型要素
Cost Function J****和Hypothesis H****：
本例中只有一個特征x1两入，所以在計算H的時候公式只有兩項净宵，當特征向量X為n1時，H就有n+1項裹纳。（為了加強模型準確度择葡，需要加入一個常數(shù)項，這樣就需要在在特征X中加入一個x0=1剃氧，并且Theta中加入一個Theta(0)才能完成敏储，所以在實際進行計算的時候X為n+11向量，比特征數(shù)多1朋鞍，而參數(shù)Theta也比特征數(shù)多1）
Gradient Descent****：
上面就是進行模型參數(shù)修改的公式已添，需要注意的是妥箕，在一次迭代中，必須在所有的Theta(j)都已經(jīng)完成計算了之后更舞，在能一次性修改所有的Theta畦幢，不可以一個一個對Theta(j)進行修改。上面式中：Theta(j)減去的部分就是我們要計算的Gradient Descent缆蝉。
另外我們需要注意的是在計算Grad的時候宇葱，有一個參數(shù)alpha，此參數(shù)可以進行手動設定如0.01刊头，但實際使用的時候我們一般不進行手動書寫優(yōu)化算法的循環(huán)黍瞧，而是使用Matlab的fminunc函數(shù)，此參數(shù)alpha則不用我們進行設置芽偏，算法會自動選取雷逆。
2.1.2 Feature Normalization
由于我們選取的特征的值域很可能是不同的，比如房子的面積可以是100-200平方米污尉，而房子的臥室數(shù)也就在2-5之間膀哲，這些值域不同的特征在依據(jù)上面公式計算Hypothesis的時候，不同的特征的權重是不一樣的被碗，房子的面積這個特征就對Hypothesis的影響很大某宪，有可能臥室數(shù)的變化根本對Hypothesis的影響不大，這樣是不對的锐朴，為了防止這種情況的發(fā)生兴喂，我們要使用一種叫Feature Normalization的計算，對特征值進行二次計算焚志，將其值域調(diào)整為比較小的固定區(qū)間衣迷。
具體的做法為：對于輸入矩陣X，mn（m個樣本酱酬，n個特征）壶谒，計算每個Feature（X(:,j)是個列向量哦）的平均值mean()，然后計算每個Feature的標準差std()膳沽，最后對此列特征的所有值執(zhí)行操作：
X(:,j)=(X(:,j)-mean())/std();
即得到了新的特征值汗菜。得到特征值之后，我們就可以帶入之前的公式計算J挑社、H和Grad陨界，調(diào)用優(yōu)化算法對Theta進行求解了。不過要注意的是痛阻，在進行預測的時候菌瘪，也需要對輸入數(shù)據(jù)進行如上的變換，之后才可以帶入H中進行輸出值Hypothesis計算阱当。
2.1.3 Normal Equations：正規(guī)方程組
上面說了那么多麻车，其實這個Linear Regression不用優(yōu)化算法也可以直接進行求解缀皱，經(jīng)過數(shù)學推導之后，Linear Regression的Theta可以直接表示為：
我們可以直接根據(jù)輸入矩陣X和y進行Theta的計算动猬，直接就得到了我們Linear Regression的模型參數(shù)啤斗，就直接可以執(zhí)行預測了。（PS：這種算法還不用對Feature進行縮放處理赁咙，很強大钮莲，不過此方法只在線性回歸中有效，有一定局限性）
2.2 Logistic Regression
Logistic Regression是對Linear Regression的一種改進彼水，主要的做法是將線性的Linear Regression中的Hypothesis函數(shù)使用一個sigmoid函數(shù)g進行作用崔拥，將Hypothesis函數(shù)轉換為非線性的。
Logistic Regression將線性的Linear Regression改進為可以處理非線性Decision Boundary的算法凤覆，并且用Logistic Regression實現(xiàn)了一個分類器链瓦。另外課程中分類器是做Binary分類的，類別只有兩個{0盯桦，1}慈俯。（也可以擴展到多個類分類的情況，這樣需要對每個類建立一個模型拥峦，計算Theta贴膘，輸入樣本是自己類的為1，否則為0略号，對于預測結果來說刑峡，哪個Hypothesis*的輸出大，就識別為某個類玄柠，這樣就可以解決多類分類的問題了）
2.2.1 Logistic Regression模型要素
Hypothesis****函數(shù)：
其中函數(shù)g是一個S型函數(shù)突梦，形狀大致是：
在x趨近負無窮的時候，g值趨近0羽利，在x趨近正無窮的時候宫患，g值趨近1。
Cost Function ****函數(shù)J****和Gradient****：
同樣要注意的是铐伴，計算Grad的時候，需要用上一次迭代的Theta進行計算俏讹，全都計算完畢后当宴，才可以用Grad對Theta進行統(tǒng)一的修改。
2.2.2 使用Matlab的優(yōu)化函數(shù)對參數(shù)進行求解
在課程中我們可以使用Matlab函數(shù)fminunc來進行優(yōu)化算法的計算泽疆，而不用自己書寫Iterator loop 户矢，僅需要給出計算Cost 和Grad的函數(shù)即可。
使用Matlab的計算代碼如下：其中costFunction函數(shù)返回每次循環(huán)的Cost和Grad值殉疼。
上述代碼就完成了對Cost Function的優(yōu)化計算梯浪，求得了模型參數(shù)Theta捌年，我們可以使用Theta直接對未知數(shù)據(jù)進行分類預測
2.2.3 預測分類
在求到了Theta后，我們通過使用Hypothesis函數(shù)進行計算挂洛，來進行對未知數(shù)據(jù)的分類礼预。當H值大于某個值a---可以是0.5，我們就預測分類為1虏劲，否則就分類為0托酸。
這個值a，可以我們手動給出柒巫，可以使用Cross Validation的方式進行自動選取励堡，具體方式在后面會進行說明。（大致為給出a的一系列可能值堡掏，比如從0.1到1应结，然后分別計算Cross Validation， 選擇Error最小的作為實際使用a）
2.3 Regularization
在我們使用了機器學習算法對分類器進行實現(xiàn)之后（任何算法泉唁，可以是Logistic Regression或者Neural Network等）鹅龄，都可能出現(xiàn)overfitting（過擬合）或者underfitting（未擬合）的問題。為了解決overfitting（主要）和underfitting的問題游两，我們可以采用一種叫做Regularization的方法砾层。
在應對Overfitting的時候，我們可以選擇減少特征個數(shù)或者是使用Regularization贱案。其中使用Regularization的優(yōu)點是不用減少特征個數(shù)肛炮，且在特征數(shù)比較多的時候很使用。其思想就是在計算Cost和Grad的時候宝踪，使用模型參數(shù)Theta來對其進行修正侨糟。修改后的Cost和Grad公式如下。
2.3.1 Logistic Regression with Regularization
Regularization方法適用在很多模型上瘩燥，但是在不同的模型上的公式修改不同秕重。在Logistic Regression上，使用了Regularization的Cost和Grad計算公式修改為如下：
Cost Function****：
要注意的是厉膀，在計算Regularization部分的時候溶耘，不要計算用于修正模型的Theta(1)（Matlab中索引從1開始），計算Theta(2:n+1)即可服鹅。
另外凳兵，在計算Regularization部分的時候，有一個參數(shù)lambda企软，是Regularization的參數(shù)庐扫，lambda很大的時候，會出現(xiàn)underfitting的情況，lambda很小的時候形庭，會出現(xiàn)overfitting的情況铅辞，關于lambda的選取，可以使用手動設定或者是自動選擇的方法萨醒，在下面介紹斟珊。
Gradient Decent****：
通樣，在計算Grad的時候验靡，也不要對Theta(1)進行計算倍宾，在Matlab中可以通過獲取一個臨時ThetaTemp，并將其ThetaTemp(1)=0胜嗓，來進行計算高职，簡化邏輯。
2.3.2 自動選擇Regularization參數(shù)lambda
lambda的自動選擇算法可以描述為如下幾步： - 給出可能的lambda選值（每個建議為*3的關系）辞州，如[0.001 ; 0.003 ; 0.01 ; 0.03 ; 0.1 ;0.3 ; 1 ; 3 ;10 ;30 ;100]
- 分別使用上述可選的lambda對模型進行計算怔锌，求得Theta
- 使用Theta在Test集上進行計算，求得誤差和Error
- 比較Error变过，選擇使得Error最小的lambda的實際使用的lambda
（其他模型中參數(shù)的選擇也類似的方法）埃元。
2.4 Neural Network
Neural Network可以算得上是機器學習或是人工智能領域最常用，也比較經(jīng)典的算法了媚狰，在這里不在贅述Neural Network的實現(xiàn)方式岛杀，僅僅給出模型描述和具體的實現(xiàn)方式。在課程中崭孤，Andrew Ng教授給處了一種用Neural Network模擬邏輯操作（與或門）等的方式类嗤，并且實現(xiàn)了一個使用3層的Neural Network進行手寫數(shù)字識別的工具。
和其他提到的模型一樣辨宠，如Logistic Regression遗锣，Neural Network一樣有自己的模型元素和模型參數(shù)，不同的是它的參數(shù)是權重矩陣Weighted Matrix嗤形。
2.4.1 Neural Network模型要素
對于一個3層的Neural Network分類器來講精偿，Input layer的節(jié)點數(shù)應該就是Feature的個數(shù)feature_num，hidden layer的節(jié)點數(shù)可以隨意指定赋兵，假設為hidder_layer_size笔咽，output layer的節(jié)點數(shù)則是具體的分類的個數(shù)classes_num。圖示如下：
我們注意到在實際的Neural Network中霹期，Input Layer和Hidden Layer都多了一個只輸出1的節(jié)點叶组，用于對模型進行調(diào)整，所以在實際的使用中经伙，Input Layer和Hidden Layer個數(shù)各子加1扶叉。
圖中的Theta1和Theta2即為Neural Network的模型參數(shù)Weighted Matrix，它們的維度隨著Input Layer和Hidden Layer加1也要修改帕膜。
Hypothesis****函數(shù)：
在上圖中枣氧，其中output layer的輸出a3，即為我們的Hypothesis垮刹，它的計算方法是一次forward propagation的過程达吞，注意每層的輸入到輸出過程中使用了sigmoid函數(shù)g，它的定義和Logistic Regression中一致荒典。
使用Regularization****的Cost Function****函數(shù)：
需要注意的是酪劫，在計算Regularization部分的時候，要忽略Input Layer和Hidden Layer中只輸出1的調(diào)整節(jié)點的參數(shù)Theta
Grad****函數(shù)計算：Neural Network的Grad計算方式很特別寺董，在下面給出具體步驟覆糟。
2.4.2 Neural Network Back propagation
注意到在上面的模型元素中，我們沒有提到Grad的計算方法遮咖，這是因為Neural Network的Grad計算方法比較特別滩字，需要用到back propagation技術，在這里單獨描述御吞。
Back propagation的具體想法大致為：從Output Layer的輸出開始與實際輸出y進行Error計算麦箍，將此Error沿著Neural Network反向計算，一直到Input Layer輸出陶珠，計算對Weighted Matrix Theta1 和Theta2的Grad修正值挟裂。
對于一個3層Neural Network，Back propagation大致算法如下：
在實現(xiàn)上述算法的時候揍诽，我們需要寫一個for i=1: size(X,1)的循環(huán)诀蓉，對每個樣本循環(huán)計算，
在循環(huán)中進行一次forward propagation寝姿，得出每層的輸出交排，然后根據(jù)步驟2-4進行delta_1和delta_2的統(tǒng)計。循環(huán)外部計算Grad_1和Grad_2饵筑。大致代碼如下：
以上算法是計算不帶Regularization的Gradient Decent埃篓，帶Regularization的需要將上述求得的Theta1_grad和Theta2_grad加上Regularization部分。
Grad使用Regularization的公式如下：
需要注意的是根资，在計算Regularization的時候架专，我們對調(diào)整節(jié)點（Bias Node）的相關Theta值不能處理。
2.4.3 Gradient Checking---驗證Gradient Descent計算是否正確的方式
有時候我們需要確定我們的Gradient Descent是否計算的正確（尤其像Neural Network這種需要很大計算玄帕，并且很容易出錯的算法）部脚，Gradient Checking就是一種計算Gradient Descent的輔助驗證手法。
因為Gradient Descent是一種計算Cost Function對于每個模型參數(shù)的偏導的方式裤纹，那我們就可以用簡單的數(shù)學上知識對此進行驗證委刘，Gradient Checking就是這個想法丧没。具體步驟如下：
上面的計算公司給出了我們一種模擬計算偏導的好方法，通過對小數(shù)據(jù)量上的數(shù)據(jù)進行Gradient Checking锡移，我們就可以驗證Gradient Descent的正確性呕童。（由Gradient Checking和Gradient Descent對于Gradient的計算結果進行比較，他們的誤差應該非常小淆珊。）這種方法不僅適合Neural Network夺饲，也適合很多其他的算法施符，當你對你計算Gradient Descent的代碼不夠自信（自信其實算一下也沒錯）的時候往声，就是用它來Checking吧。
2.5 Cross Validation & Bias/Variance
2.5.1 Cross Validation
Cross Validation戳吝，中文稱作交叉驗證浩销，是一種很好的對算法進行驗證的方法，它可以適用于任何監(jiān)督類學習算法听哭。
Cross Validation的思想很簡單撼嗓，大致為以下幾步： - 訓練集Training set劃分為兩個部分Cross-Validation set和Training set_use。
- 使用Training set_use來進行算法的訓練欢唾，計算得到的模型在Training set_use上的誤差數(shù)據(jù)J_train且警。
- 使用訓練的結果對Cross-Validation set上的數(shù)據(jù)進行計算Hypothesis，計算模型在Cross-Validation set上的誤差數(shù)據(jù)J_cv
- 根據(jù)Cross-Validation set上的模型表現(xiàn)J_cv判定算法效率礁遣。
2.5.2 Learning Curves, Bias & Variance
我們計算通過調(diào)整訓練集的大邪呶摺（從1到m）來計算J_train和J_cv兩個數(shù)據(jù)，這樣祟霍，我們就得到了一個關于訓練集大小和J_train/J_cv的學習曲線（Learning Curves）杏头。它可以幫助我們更好的確定數(shù)據(jù)集的大小，以及確定當前算法的表現(xiàn)情況沸呐。
High Bias：underfitting醇王，Learning Curves中的J_train和J_cv數(shù)據(jù)都很高，兩者曲線最后距離變很靠近崭添。
解決辦法：獲取更多的特征寓娩；使用多項式特征（Feature Mapping，引入特征的冪作為新特征）呼渣；如果是Logistic Regression的話減少lambda棘伴。
High Variance：overfitting，Learning Curves中的J_train值很低屁置，J_cv數(shù)據(jù)很高焊夸，二者有明顯的差距。
解決辦法：選擇更多的訓練集蓝角；選擇更少的特征阱穗；如果是Logistic Regression則增加lambda饭冬。
2.6 Error Metrics ---如何度量Skewed Classes的錯誤
使用機器學習的時候，我們需要一個評價得到的模型效率的的方式揪阶，使用準確率來講伍伤，一般的情況就可以了，不過應對一些特殊問題的時候遣钳，比如說小概率事件的預測上，癌癥預測：平均發(fā)送比例非常新笃颉（5/1000）蕴茴，這種情況叫做Skewed Classes。
在Skewed Classes問題中就算我們的算法一直預測0（正常）姐直，對于現(xiàn)實的樣本也可能得到非常高的準確率倦淀，但是這明顯是不對的，所以我們需要其他的評價方式声畏。
下面介紹一些新的概念撞叽。
2.6.1 Precision & Recall
如上圖，左邊是一個22的矩陣插龄，其中每個元素為實際模型在Test集上的表現(xiàn)數(shù)據(jù)愿棋，其中
True Positive為預測為1，實際也是1的次數(shù)
False Positive為預測為1均牢，實際為0的次數(shù)
False Negative為預測為0糠雨，實際為1的次數(shù)
True Negative為預測為0，實際也為0的次數(shù)
我們又引入兩個概念Precision和Recall徘跪，其中Precision=tp/(tp+fp)甘邀，Recall=tp/(tp+fn)。
它們的具體計算方法如下：
2.6.2 F1 Score
為了計算Error Metrics for Skewed Classes垮庐，最終我們需要計算的值稱為F1 Score松邪，它的計算公式為：
我們最終使用F1 Score來評價不同的算法效率，對于F1 Score的值最高的算法哨查，效率最高逗抑。（根據(jù)公式可見，F(xiàn)1 Score高的算法的Precision和Recall的值都比較高才行）
另外寒亥，F(xiàn)1 Score的評價方法不僅局限于Skewed Classes锋八，還可以應用于任何其他類型的算法比較。
2.7 SVM
Support Vector Machine护盈，支持向量機挟纱，現(xiàn)在應用很廣的非常好用的機器學習算法，關于此算法已有了比較成型的工具支持腐宋，如LIBSVM紊服，使用也非常好用檀轨，在這里僅僅簡單介紹SVM的一些概念。本課程中給出了一個利用SVM進行垃圾郵件分類的工具欺嗤。（關于SVM的具體理論很復雜参萄，不進行討論，只要知道如何使用就好*）
2.7.1 SVM模型要素
Cost Function ****和Hypothesis****：
由上公式可見煎饼，SVM模型中有一個參數(shù)C讹挎，這個參數(shù)的大小是很重要的，它和1/lambda的概念差不多吆玖，如果C取得比較大筒溃，則SVM 訓練到的Decision Boundary對于訓練集數(shù)據(jù)敏感，如果C取得比較小沾乘，則Decision Boundary對訓練集的噪聲比較不重視怜奖。
2.7.2 Kernels核函數(shù)
在處理非線性的Decision boundary的時候，SVM通常要將特征空間擴展到高維空間上翅阵，而Kernel函數(shù)的主要工作是用于代替高維向量的點積運算歪玲，這樣甚至我們就不用真的執(zhí)行高維空間映射就可以完成高維空間的效果。有幾種常用的Kernel函數(shù)掷匠，課程中使用的Kernel函數(shù)是Gaussian Kernel滥崩。它的定義如下：
其中xi和xj為兩個特征空間的向量。
2.7.3 SVM的使用
SVM的使用是比較簡單的讹语，一般我們只要給出樣本集X夭委，y，要使用的kernel 函數(shù)募强，以及參數(shù)C株灸，即可。關于更多的使用擎值，課程建議我們使用已有的SVM工具集LIBSVM慌烧。
另外，關于多類分類的SVM使用鸠儿，假設有K個分類屹蚊，則我們可以訓練K個SVMs，對每一組輸入數(shù)據(jù)进每，進行K個SVM的Hypothesis計算汹粤，取其中比較大的為最后的分類。
2.8 Supervised Learning 算法的比較
目前我們學到的Supervised Learning算法有Logistic Regression 田晚，Neural Network和SVM嘱兼。
假設輸入樣本集為m個，特征為n個贤徒，我們來分情況討論上述算法的適用情況芹壕。 - n比m大很多：使用Logistic Regression或者Linear Kernel的SVM比較好汇四。
- n比較小，m數(shù)量級適中：使用Gaussian Kernel的SVM比較好
- n比較小踢涌，m很大的情況：嘗試提取更多的特征通孽，使用Logistic Regression或者使用Linear Kernel的SVM比較好。
- 在上述所有情況睁壁，Neural Network都可以有很好的表現(xiàn)还惠，但是訓練的時間要很長糠馆。
2.9 Clustering：K-means
Clustering聚類歹颓，課程涉及到的第一個非監(jiān)督算法埠况。用來找到結構或者模式蹬刷，可以用于社交網(wǎng)絡分析性含、市場分析豁状、優(yōu)化計算集群知态、天文數(shù)據(jù)分析等個個方面巢价。
經(jīng)典Clustering 算法：K-means牲阁。在Programming exercises中，給出了一個圖片壓縮的應用壤躲。（圖片中保存的顏色為RGB城菊，每個8位，我們實際可以使用16個顏色來代替其他所有的顏色碉克，針對所有像素點的RGB值凌唬，作為一個3D的特征，使用K=16的K-means方法漏麦，將所有的RGB值聚類為16類客税，然后用這每個RGB值的從屬類RGB值代替原RGB，即完成了圖像壓縮撕贞，每個像素只用4位（2^4=16））
和監(jiān)督算法不同更耻，非監(jiān)督算法中沒有Hypothesis函數(shù)，只有Cost Function捏膨，也有Grad的形式秧均。
2.9.1 K-means算法
K-means****算法的Cost Function****如下：
由上公式我們可以看到，K-means算法的模型參數(shù)有兩組号涯，一組是m個樣本的所屬分類情況C目胡，另一組是K個聚類的中心點左邊U。通過優(yōu)化Cost Function J链快，我們想得到這兩組值誉己。
K-means****算法的過程如下：
如上所示，算法循環(huán)中對C和U的修正域蜗，即為minimize Cost Function J的過程巫延。
2.9.2 K-means的初始值U和C
K-means算法的Cost Function J可能有局部最小值效五，這樣就無法避免K-means算法可能會得到一個局部最小值而無法得到全局最小值。
解決的辦法大致有二：
- 隨機賦值初始值U和C炉峰，并執(zhí)行K-means算法畏妖，記錄最后的Cost值，循環(huán)上述過程N次疼阔，取其中Cost最小的U和C作為最后的全局最小值戒劫。
- 使用模擬退火法，修改K-means算法循環(huán)過程婆廊，加入模擬退火迅细，防止進入局部最小值（詳見《集體智慧編程》）。
2.10 Principal Component Analysis
PCA算法在機器學習的主要作用即為：對數(shù)據(jù)的降維淘邻。Programming exercises中給出的例子是對人臉圖片進行壓縮茵典。它可以用于我們在機器學習訓練時對訓練集降維，進而加快我們的訓練速度等等宾舅，也可以完成數(shù)據(jù)的可視化统阿。（n維數(shù)據(jù)降維成3維）
PCA算法解決的主要問題是：如何在盡量保持數(shù)據(jù)完整性情況下將n維數(shù)據(jù)降到k維（n>k）。它的想法大概是這樣：找到一個K維的超平面筹我，它可以擬合大部分的數(shù)據(jù)集中的n維點扶平，然后將數(shù)據(jù)集中的n維點都投影（projection）到這個K維的超平面上，即完成了數(shù)據(jù)的壓縮蔬蕊。
需要注意的是對于PCA算法结澄，所有的輸入數(shù)據(jù)必須進行Normalization，否則會出錯岸夯。
PCA算法的步驟和過程是固定的麻献，下面簡單進行描述。
2.10.1 PCA Algorithm
PCA算法主要需要計算兩個值：一是數(shù)據(jù)的covariance matrix猜扮，二是計算principal components赎瑰。
- 計算covariance matrix ：對于數(shù)據(jù)集X，計算covariance matrix的公式如下：
- 計算principal components：使用matlab的svd函數(shù)計算如下：
其中Sigma即為上面計算出的covariance matrix破镰。 - 對數(shù)據(jù)X進行降維到K得到數(shù)據(jù)集Z：（X為mn餐曼，Z為mk）
U_reduce=U(:,1:K);
Z=X*U_reduce; - 對數(shù)據(jù)Z進行還原得到X_approx
X_approx=ZU_reduce’;
2.10.2 PCA的Cost Function
上式的左邊即為PCA算法的Cost Function，代表經(jīng)壓縮的數(shù)據(jù)相對于原數(shù)據(jù)的信息丟失程度鲜漩。上式在我們進行K的選擇的時候比較有用（比如要將數(shù)據(jù)降維源譬，但又要保持數(shù)據(jù)完整性）可以自動選擇一個滿足上式的還比較小的K，滿足上式代表著經(jīng)過PCA算法的處理后孕似，數(shù)據(jù)的信息量丟失不超過1%踩娘。
2.11 Anomaly Detection
異常檢測，用于檢測異常的情況，如檢測用戶異常動作或者系統(tǒng)行為等等养渴。在Programming Exercises中雷绢，課程給出了一個根據(jù)吞吐量和延時檢測服務器異常的用例。
在異常檢測中理卑，所有的輸入訓練集都是正常的訓練集翘紊，沒有異常情況的樣例。
課程使用了Gaussian Model的Anomaly Detection藐唠，它的思想比較簡單帆疟，把所有的特征Feature都假定其滿足Gaussian的分布。
Gaussian Distribution如下：
我們看到Gaussian Distribution有兩個參數(shù)宇立，我們需要將樣本中的每個特征看為一組訓練數(shù)據(jù)踪宠，來求得每個特征的Gaussian分布參數(shù)。計算公式：
2.11.1 Anomaly Detection Algorithm
由上可見妈嘹，算法在計算玩每個Feature的Gaussian分布后柳琢，對每個后來的新數(shù)據(jù)X，都要計算p(x)润脸，公式如上柬脸，如果p(x)小于特定值則判定為異常。此值可以用自動選擇的方式進行計算（上面討論過：使用CV和F1對不同值的算法進行評價津函，取最好的）肖粮。
2.11.2 More about Anomaly Detection
Anomaly Detection與Supervised算法是不同的孤页，anomaly的種類有非常多尔苦，它不能像Supervised算法一樣根據(jù)之前的anomaly學習，對后來的數(shù)據(jù)進行預測行施，因為后來的anomaly可能和之前的是完全沒有相似性的允坚。
另外，在例子中我們使用的是Gaussian Model蛾号，那么在實際的使用中很可能Feature是不滿足Gaussian分布的稠项，在這種情況下我們可以對特征進行某種變換（某種數(shù)學計算），來使它滿足Gaussian分布即可鲜结，可自己嘗試對特征進行變換的方法展运。
2.12 Recommender System
Recommender System推薦系統(tǒng)，課程以一個對電影進行評分的應用展示了推薦系統(tǒng)的設計方法精刷。
2.12.1 Content-based recommendation
輸入共有nm個電影拗胜，nu個用戶。輸入矩陣X怒允，nmnu埂软，其中每行是一個電影的所有用戶的評分，（從1到5纫事，沒填即為勘畔？）所灸，而R矩陣也是nmnu的，R(i,j)=1代表用戶j對電影i進行了評分炫七。
假設每個電影都有n個特征爬立，特征值由我們自行給每個電影填上（如romantic,action）。
對于每個用戶j诉字，計算他相對與特征的Thetaj懦尝，計算采用優(yōu)化算法，其中要素如下：
Cost Function****和Gradient Descent****：
在優(yōu)化求得了Theta_1到Theta_nu之后壤圃，我們就可以使用Hypothesis函數(shù)來對用戶j對未評價的電影i進行評分陵霉。Hypothesis如下：
2.12.2 Collaborative filtering learning algorithm
協(xié)同過濾算法，和基于內(nèi)容的推薦不同伍绳，對于Collaborative filtering算法踊挠，電影的特征值是不知道的，對于模型來說冲杀，參數(shù)就換成了：X_1到X_nm效床，Theta_1到Theta_nu。它的Cost Function如下：
而它的Grad修改為：
我們要計算兩個Grad矩陣：X_grad：nmn和Theta_grad：nun权谁。
而Collaborative filtering的Hypothesis函數(shù)還是一樣剩檀，對于h(i,j)=Theta_j’X(i,:)。
這樣旺芽，Cost Function和Gradient Descent以及Hypothesis都有了沪猴，我們就可以使用優(yōu)化算法對Theta_1到Theta_nu和X_1到X_nm進行計算。得到這些值之后采章，我們就可以這些值使用Hypothesis(i,j)進行對于用戶j對于電影i的評分進行預測了运嗜。
2.13 Large Scale Machine Learning
在這個議題里，我們主要討論了對于數(shù)據(jù)量比較大的情況下悯舟，如何有效地使用機器學習算法担租。
2.13.1 對于Logistic Regression算法
Logistic Regression算法中的Grad中每個元素的計算每次都要遍歷所有的輸入，這樣在數(shù)據(jù)樣本比較大時是非常耗時的抵怎，這時我們就可以使用隨機梯度下降算法（Stochastic Gradient Descent）或者Mini-batch Gradient Descent算法奋救。
Stochastic Gradient Descent算法如下：
由上圖可見，在每次循環(huán)計算Theta(j)的時候反惕，算法不再像原始的Batch Gradient Descent一樣需要計算所有的數(shù)據(jù)尝艘，只有了一條數(shù)據(jù)。減少了計算量承璃。（當然這樣求得的Gradient Descent就不是真正意義上的偏導數(shù)了利耍，其Cost Function可能會有上升的情況，不過沒問題，經(jīng)過迭代是可以收斂的）
Mini-batch Gradient Descent算法和Batch Gradient Descent算法（一次計算需要所有值的計算）與Stochastic Gradient Descent算法（一次計算只用一個值的計算）都不同隘梨，它每次計算使用b=mini-batch size個元素進行計算程癌，是上述兩種的中間算法，Gradient Descent的計算方式修改為：
2.13.2 Online Learning
在線學習轴猎，主要的思想是根據(jù)用戶的新輸入實時的對模型參數(shù)進行持續(xù)的在線修改嵌莉，完成持續(xù)性的學習。另外的一種方式是將之前訓練的結果加以保存捻脖，這樣可以在下次運行時繼續(xù)持續(xù)的學習锐峭。增加了允許學習的時間。
2.13.3 Map Reduce and Data parallelism
使用如Map Reduce等分布式計算的工具也是一種加速我們學習的算法可婶，可以通過將學習中的計算任務分布到不同的機器或節(jié)點上的方式來進行并行化沿癞。
2.14 Ceiling analysis
上限分析，一種可以讓我們找到我們機器學習系統(tǒng)瓶頸的工具矛渴。一個完整的機器學習系統(tǒng)由很多部分組成椎扬，在整體系統(tǒng)的表現(xiàn)不好的時候，我們需要確定到底是那個子系統(tǒng)出了問題具温，我們需要集中經(jīng)歷解決哪個系統(tǒng)的問題蚕涤。這時就可以使用Ceiling analysis。
Ceiling analysis的思想也很簡單铣猩，它通過用人工替換的方式揖铜，記錄在系統(tǒng)各部分依次換成人工執(zhí)行的時候，整個系統(tǒng)的表現(xiàn)达皿，在某個部分換成人工之后天吓，系統(tǒng)性能有很明顯的提升，這就說明這個部分的表現(xiàn)決定了我們系統(tǒng)的表現(xiàn)鳞绕，目前是系統(tǒng)的瓶頸失仁，是我們應該集中精力改善的部分尸曼。
課程以OCR（圖片文字識別）為例給出了進行Ceiling analysis的方法们何。
如圖為OCR系統(tǒng)進行Ceiling analysis的一個例子：
根據(jù)圖片所示系統(tǒng)目前的瓶頸在于Text detection部分。
