Density Estimation

這個(gè)章節(jié)主要講述了非監(jiān)督機(jī)器學(xué)習(xí)中的異常檢測(cè)算法(anomaly algorithm)，其原理實(shí)際是利用了在工程、產(chǎn)品的檢測(cè)中，大部分正常產(chǎn)品的各個(gè)feature是服從正態(tài)分布(高斯分布)的，所以給定一個(gè)樣本，我們可以計(jì)算其各個(gè)feature為正常值的概率，并設(shè)定一個(gè)閾值?，當(dāng)樣本為正常值的概率P大于?時(shí)，我們就認(rèn)為是正常的，當(dāng)這個(gè)P小于?時(shí)我們就認(rèn)為其是異常的。

關(guān)于density estimation的解釋可以參考wiki - density estimation

Problem Motivation

作者在這一小節(jié)主要講了一些實(shí)際應(yīng)用的例子。

• 飛機(jī)引擎檢測(cè)
• 欺詐用戶
• 數(shù)據(jù)中心的異常檢測(cè)

Gaussian Distribution

這一小節(jié)主要講高斯分布，重點(diǎn)就是下圖中的公式和高斯分布圖：

1.1-Gaussian Distribution

高斯密度函數(shù)中有兩個(gè)需要計(jì)算的值，一個(gè)是均值μ，另一個(gè)是平方差??²，其計(jì)算公式如下：

1.2-Gaussian compution

Algorithm

前面我們已經(jīng)說了，重點(diǎn)是計(jì)算樣本為正常值的概率P，其計(jì)算就需要如下公式：

1.3-probability compution

• 針對(duì)每一個(gè)feature的維度都需要進(jìn)行高斯計(jì)算，從而算出μ和??²，然后針對(duì)不同的樣本x來計(jì)算出P
• 這里引入了一個(gè)新的數(shù)學(xué)符號(hào)Π，這是意味著相乘的關(guān)系

那么，整個(gè)異常檢測(cè)算法的流程如下：

1.4- anomaly detection algorithm

Building an Anomaly Detection System

這個(gè)章節(jié)重點(diǎn)講了工程實(shí)踐中具體是怎么訓(xùn)練我們的模型。

Developing and evaluating an anomaly detection system

首先，作者將了如何將我們的樣本分為training set, cross validation set和testing set，舉例如下：

2.1-sample sets

• 要將異常樣本放到CV和test集中

那么最終這個(gè)?如何選擇呢？重點(diǎn)就是要根據(jù)我們的precision/recall rate, F-score來選擇這個(gè)?值，而不能使用error rate，這是由于我們的樣本集是數(shù)據(jù)傾斜的(skewed)，即負(fù)樣本數(shù)遠(yuǎn)大于正樣本數(shù)，所以需要使用precision/recall rate, F-score, 如下圖：

2.2-choosing ?

Anomaly Detection vs. Supervised Learning

本小節(jié)重點(diǎn)講了在哪些情況下使用anomaly detection，哪些情況下使用supervised learning。其主要區(qū)別如下：

2.3-anomaly detection vs. supervised learning

• 當(dāng)y=1(即異常樣本)的樣本非常少的時(shí)候我們很難通過訓(xùn)練讓supervised learning算法“學(xué)習(xí)”到什么時(shí)候?yàn)?；相比較而言如果有大量y=0的樣本我們就可以計(jì)算其高斯分布情況，從而識(shí)別其為正常值的概率，通過閾值?我們就可以知道何為異常，何為正常
• 當(dāng)異常有很多種類的時(shí)候，甚至于有些異?？赡苤岸紱]有發(fā)生過，這種情況下很難通過supervised learning來“學(xué)習(xí)”到這種異常情況，所以這種情況更適合anomaly detection

Choosing Features

此小節(jié)主要講了如何針對(duì)anomaly detection來選擇feature。我個(gè)人的理解如下：

想象一下我們自己如何去識(shí)別這個(gè)異常，可以使用哪些“指標(biāo)”來發(fā)現(xiàn)異常，那么這些“指標(biāo)”就可以作為feature。

另外，在我們異常檢測(cè)時(shí)，如果發(fā)現(xiàn)某個(gè)異常的樣本在我們的模型中P值很高(即檢測(cè)為正常)，那么很有可能是其某個(gè)檢測(cè)指標(biāo)沒有在我們的檢測(cè)模型當(dāng)中，我們可以看看這個(gè)異常值究竟哪里異常，用什么指標(biāo)可以檢測(cè)到這個(gè)異常，這樣我們就可以為我們的異常檢測(cè)系統(tǒng)發(fā)現(xiàn)新的feature，如下圖所示：

2.4-discover new features

另外, 我們還可以通過一些原始“指標(biāo)”的組合來形成新的feature，如下圖所示：

2.5-compose new features

最后，我們需要看下我們這些feature的數(shù)值分布是否符合高斯分布，如果不符合，就需要將這些數(shù)據(jù)進(jìn)行轉(zhuǎn)換，讓“新的feature”的數(shù)值分布符合高斯分布。如下圖所示：

2.6-feature transform

總結(jié)選擇feature的過程如下：

• 根據(jù)我們?nèi)祟惤?jīng)驗(yàn)，選擇可能檢測(cè)到異常的指標(biāo)作為feature
• 通過CV和測(cè)試集發(fā)現(xiàn)模型中存在異常的樣本但是P值卻很高，分析可能遺漏的feature
• 還可通過原始指標(biāo)的組合形成新的feature
• 將不符合高斯分布的指標(biāo)進(jìn)行轉(zhuǎn)換

Multivariate Gaussian Distribution

本章主要講了多元高斯分布模型(multivariate gaussian distribution)

multivariate gaussian distribution

在現(xiàn)實(shí)使用高斯分布的時(shí)候，我們會(huì)發(fā)現(xiàn)有些情況下兩個(gè)feature是有相關(guān)性的，Andrew舉了一個(gè)數(shù)據(jù)中心異常檢測(cè)的例子，我們會(huì)發(fā)現(xiàn)計(jì)算機(jī)的cpu使用率和memory使用率是有一定相關(guān)性的，通常cpu使用率越高，memory使用率也就越高，如果一臺(tái)機(jī)器CPU使用率很低，但是memory很高，那么異常的可能性就較大，這種情況下用我們之前的高斯分布模型就無法檢測(cè)到，如下圖所示：

3.1-data center example

• 圖中可以看出雖然在同一個(gè)等高線上(紅色圓圈）概率P是相同的，但是實(shí)際上在橢圓圈(藍(lán)色橢圓)中的概率P顯然應(yīng)該更加高一些(由于cpu和memory的正相關(guān))
• 這就是為什么我們需要引入多元高斯模型，從而可以讓我們的高斯模型有更多調(diào)整和控制

多元高斯分布的計(jì)算公式如下圖所示：

3.2-multivariate gaussian distribution formula

• 這里涉及到協(xié)方差矩陣和行列式的概念，具體可以參考wiki-協(xié)方差矩陣 和wiki - 行列式
• 行列式計(jì)算可以直接使用octave中的函數(shù)det來進(jìn)行計(jì)算

接下來，我們看下協(xié)方差矩陣∑和均值μ是如何影響我們的分布模型的。
首先，協(xié)方差矩陣對(duì)角線上的數(shù)值會(huì)影響不同維度的高斯分布的寬度，如下圖所示：

3.3-example1

• 這里可以看到協(xié)方差矩陣對(duì)角線上的值會(huì)影響高斯分布的寬窄，而且對(duì)角線的第一個(gè)值(位置[1, 1])影響的是x1，其越大那么x1維度上高斯分布越寬，下降也越慢；對(duì)角線上第二個(gè)值([2,2])影響x2方向上的高斯分布。

再看第二個(gè)例子

3.4-example2

• 這里看到另一個(gè)方向上的對(duì)角線的值影響的是x1, x2的相關(guān)性，值越大，x1和x2越相關(guān)
• 相關(guān)性的含義就是，當(dāng)x1越大，正常情況下x2也越大（cpu和memory的例子), 這種情況下我們用這個(gè)模型就可以很好的契合本章剛開始的例子（高斯分布圖已經(jīng)變成了橢圓形）

也可以是負(fù)相關(guān)，即x1越大，相應(yīng)的x2應(yīng)當(dāng)越小，可以通過設(shè)為負(fù)值讓其負(fù)相關(guān)，如下圖：

3.5-example3

最后，均值會(huì)影響到高斯分布的中心點(diǎn)位置，如下圖所示：

3.6-example4

本節(jié)疑問是，中心點(diǎn)的概率應(yīng)當(dāng)是接近于1的，但是看到課程的示例其高點(diǎn)都沒有到1，甚至遠(yuǎn)低于1，這個(gè)不明白為什么是這種情況？

Anomaly Detection Using Multivariate Gaussian Distribution

本小節(jié)主要講如何使用多元高斯分布，首先我們要計(jì)算均值μ和協(xié)方差矩陣∑，如下圖：

3.7-multivariate gaussian distribution

• 通過上圖的公式計(jì)算好μ和∑之后，我們就可以將新的樣本x一起代入公式當(dāng)中，從而計(jì)算出概率P

實(shí)際上，原來的高斯模型是多元高斯模型的一個(gè)特殊形式而已，如下圖所示：

3.8-relation between original gaussian distribution and multivariate gaussian distributon

這兩種高斯模型各有利弊，反而original高斯模型使用更加頻繁一些。其利弊比較如下圖所示：

3.9-original vs. multivariate

• 針對(duì)相關(guān)性問題，我們可以生成一個(gè)新的feature（如圖x3）,從而讓original model也可以檢測(cè)到這種相關(guān)性。相比較而言多元高斯模型是自動(dòng)捕獲這種相關(guān)性的。
• original模型計(jì)算相對(duì)簡(jiǎn)單，因此當(dāng)n非常大的時(shí)候，就非常適合這i種模型。相較而言，多元高斯模型的計(jì)算量相當(dāng)大。
• 最后由于數(shù)學(xué)上限制，當(dāng)m<n時(shí)我們是無法使用多元高斯模型的。

Recommendation System

Rating Movie

此小節(jié)主要講了我們是如何在推薦系統(tǒng)中給電影進(jìn)行預(yù)測(cè)打分的，重點(diǎn)是講了一些notation，如下圖：

4.1-movie rating system notations

Content Based Recommendations

此小節(jié)主要講了如何基于內(nèi)容進(jìn)行推薦，本質(zhì)上是將電影的一些特征組成一個(gè)特征向量，然后根據(jù)每個(gè)用戶已經(jīng)評(píng)分的電影樣本進(jìn)行訓(xùn)練（Linear Regression），從而為每一個(gè)用戶都訓(xùn)練出一個(gè)單獨(dú)的模型（即每個(gè)用戶都會(huì)有一個(gè)不同的θ）這樣的話，就可以針對(duì)沒有評(píng)分的電影進(jìn)行預(yù)測(cè)。過程如下圖所示：

4.2-movie rating model

所以，我們的優(yōu)化目標(biāo)跟Linear Regression類似，只是我們需要針對(duì)每個(gè)用戶都要計(jì)算其cost function的最小值，所以最終的公式如下圖所示：

4.3-optimization objective

• 圖4.3上邊的公式是計(jì)算當(dāng)個(gè)用戶的優(yōu)化目標(biāo)，注意這里省略了m，因?yàn)椴挥绊懽詈蟮摩戎?/li>

• 圖4.3下方的公式是針對(duì)所有用戶的優(yōu)化目標(biāo)，實(shí)際就是把針對(duì)單個(gè)用戶的優(yōu)化目標(biāo)相加

  
  
  4.4-optimization algorithm
• 根據(jù)我們的優(yōu)化目標(biāo)的公式，我們可以針對(duì)其進(jìn)行梯度下降計(jì)算
• 注意這里是要針對(duì)每一個(gè)用戶(θ^(j))的每一個(gè)θ_k(k 從0到n)都要進(jìn)行梯度計(jì)算。舉個(gè)例子，假設(shè)我們的movie使用了兩個(gè)特征值，那么我們的特征向量就是2+1個(gè)維度，所以我們要為每個(gè)用戶都計(jì)算其相應(yīng)的θ₀，θ₁，θ₂。假設(shè)我們有5個(gè)用戶需要計(jì)算(即j從1到5)，那么總共要計(jì)算3x5=15個(gè)θ。

個(gè)人認(rèn)為，實(shí)際項(xiàng)目中很難使用此種方法，因?yàn)榇蟛糠钟脩艨赡芨揪筒粫?huì)去給電影評(píng)分，也就沒有樣本可以訓(xùn)練，因此也就無法訓(xùn)練出相應(yīng)的模型

Collaborative Filtering

Collaborative Filtering

此章節(jié)重點(diǎn)講協(xié)同過濾算法，為什么要使用協(xié)同過濾呢，主要原因在于如果電影數(shù)量龐大，我們手工去標(biāo)注電影的feature x1， x2會(huì)非常麻煩，因此我們就會(huì)想，如果我們已知各個(gè)用戶的θ值，是否也能推測(cè)出其feature值呢，如下圖所示，顯然是可以的：

5.1-predict feature according to θ

然后，問題就轉(zhuǎn)化為求如下最優(yōu)解的問題：

5.2-optimization algorithm

• 這里的regularization item變成了針對(duì)x，而不是θ
• 當(dāng)針對(duì)所有的movie的時(shí)候，我們要需要將x⁽¹⁾到x^{(no of moview)}的所有誤差項(xiàng)都加總起來，如此就有了下方的公式。最終我們只需要針對(duì)下方的公式來求解最小值，從而得到x的最優(yōu)解

那么，問題來了，我們又如何得到θ，從而去求解x呢？這成了一個(gè)先有雞還是先有蛋的問題。解決此類問題的一種辦法是，先隨機(jī)取一組θ值，然后去優(yōu)化x，用得到的x再去優(yōu)化θ，循環(huán)往復(fù)，如下圖所示：

5.3-optimization both θ and x

下一節(jié)，我們會(huì)看到一種更好的辦法。

Collaborative Filtering Algorithm

首先，我們可以將兩組優(yōu)化公式(一個(gè)是針對(duì)θ，另一個(gè)是針對(duì)x)整合在一起，如下圖所示：

5.4-collaborative filtering optimization objective

• 無論針對(duì)x還是針對(duì)θ，其本質(zhì)都是找尋某個(gè)x和θ使得預(yù)測(cè)值（即某個(gè)用戶針對(duì)某個(gè)電影的評(píng)分）和真實(shí)值(真實(shí)評(píng)分)之間的差值最小。而這個(gè)差值對(duì)于兩個(gè)公式來說，本質(zhì)是一樣的，都是找尋有用戶評(píng)分的電影( 即r(i, j)=1 )，和預(yù)測(cè)值，然后計(jì)算其差值的平方。
• 正則部分，由于我們是同時(shí)針對(duì)θ和x進(jìn)行求解，因此就需要有同時(shí)針對(duì)θ和x的正則項(xiàng)。
• 另外，我們也不需要設(shè)定x0， θ0，這些都會(huì)交給算法自動(dòng)訓(xùn)練出來。

最后，整個(gè)算法的訓(xùn)練和預(yù)測(cè)過程如下：

5.5-collaborative filtering algorithm procedure

Low Rank Matrix Factorization

Vectorize: Low Rank Matrix Factorization

此小節(jié)主要是講在計(jì)算預(yù)測(cè)值的時(shí)候，我們不需要一個(gè)用戶一個(gè)電影的計(jì)算，而可以通過vectorization的方式進(jìn)行計(jì)算，如下圖所示：

6.1-vectorization computing

由于這種計(jì)算方式在線性代數(shù)中叫做low rank matrix factorization，因此我們這種協(xié)同過濾算法有時(shí)也被稱為low rank matrix factorization算法
隨后Andrew又提出了一個(gè)問題，就是我們?cè)趺礃涌梢耘袛嘁粋€(gè)電影是相關(guān)的呢？針對(duì)一個(gè)電影，我們可能有很多的features，那么這時(shí)候如何判斷兩個(gè)電影的相關(guān)性呢？本質(zhì)上我們可以用這些feature的vector來表示一部電影，這樣電影就都可以用vector來表示了，那么問題就轉(zhuǎn)化為如何判斷兩個(gè)vector的相關(guān)性了，通過前面的學(xué)習(xí)我們知道，其中一種方法就是看兩個(gè)vector的歐幾里得距離，具體如下圖所示：

6.2-finding related movies

Implementation Detail: Mean Normalization

我們之所學(xué)所思皆來源于問題，那么此小節(jié)所講正是來源于之前我提到的一個(gè)問題，即當(dāng)用戶評(píng)分很少或者干脆沒有評(píng)分的時(shí)候怎么辦？如下當(dāng)用戶沒有任何評(píng)分的時(shí)候，最后我們通過優(yōu)化公式優(yōu)化的結(jié)果就是所有的θ均為0，那么預(yù)測(cè)值也就全是0，這樣就沒有預(yù)測(cè)效果了。

6.3-question: if user has no ratings

那么，我們?cè)撊绾谓鉀Q這個(gè)問題呢？一個(gè)最直觀的辦法就是將每部電影的平均評(píng)分賦給這個(gè)沒有評(píng)分的用戶。那么，我們不可能去找哪個(gè)用戶沒有評(píng)分，哪個(gè)用戶評(píng)分?jǐn)?shù)量不夠，我們可以通過算法來解決這個(gè)問題，如下圖所示：

6.4-mean normalization

• 通過mean normalization（即讓原先的x，記作x_ori減去均值μ從而轉(zhuǎn)化為新的features，記作x_new)，我們可以得到一個(gè)新的feature matrix，然后再通過這個(gè)新的feature matrix來訓(xùn)練θ和x_new
• 最終預(yù)測(cè)的時(shí)候我們需要將均值加回來，因此就有(θ^(j))^T(x⁽ⁱ⁾_new) + μ
• 針對(duì)沒有評(píng)分的用戶Eve，最終由于加了μ，所以其預(yù)測(cè)值就是均值。

其它疑問

1. 視頻中Andrew沒有講針對(duì)一個(gè)item，我們?cè)撊绾芜x擇其features？實(shí)際上，我們可能也無需關(guān)心某個(gè)feature的含義，但是feature的數(shù)量是需要我們?nèi)ミx擇的。那么該如何解決呢？

答案是：做實(shí)驗(yàn)。比如我們可以先選擇兩個(gè)feature，訓(xùn)練之后，讓其在CV集上預(yù)測(cè)，計(jì)算error rate，然后再選擇5個(gè)feature嘗試，再選擇更多的feature嘗試，最終我們可以繪制一個(gè)feature數(shù)量和error rate的關(guān)系圖，從而判斷feature數(shù)量n為幾的時(shí)候，error rate最低。

2. Andrew講的協(xié)同過濾算法和網(wǎng)上搜索查到的協(xié)同過濾算法感覺并不是相同的算法，這是怎么回事？