機器學習公開課筆記(9)：異常檢測和推薦系統

異常檢測(Anomaly Detection)

基本假設：多數情況下數據點落入正常的取值范圍，但是當異常行為發生時，數據點的取值落入正常取值范圍之外（如圖1所示）。所以可以利用高斯分布，計算行為發生的概率，如果是概率小于給定閾值，則認為發生了異常行為。基本過程是利用訓練數據點建立模型$p(x)$，對于新的數據點$x_{new}$, 如果$p(x_{new})<\epsilon$則發生異常；否則正常。異常檢測的應用包括：

• 欺詐檢測(Fraud detection)
• 制造業(Manufacturing)
• 數據中心監視電腦(Monitering computers in data center)

圖1 異常行為（Outlier Point）發生示例

高斯分布

對于一元高斯分布$x \sim N(\mu, \sigma^2)$，表達式如下，其中$\mu$表示均值，對應于分布的對稱軸；$\sigma$表示數據點的離散程度，$\sigma$越大函數圖像的下端張口越大峰值越低；反之$\sigma$越小，圖像下端張口越小，峰值越高，如圖2所示。

$$p(x;\mu, \sigma^2)=\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(x-\mu)^2}{2\sigma^2})$$

圖2 不同參數($\mu, \sigma$)取值下的一元高斯分布

參數估計

高斯分布的總體參數$\mu$和$\sigma$可以使用樣本數據點進行估計，如下

異常檢測算法

對于訓練數據集$\{x^{(1)}, x^{(2)}, \ldots, x^{(m)}\}$，其中數據點$x^{(i)}\in R^n$并假設每個特征均服從高斯分布，即$x^{(i)}_j \sim N(\mu, \sigma^2)$，可如下建立模型$p(x)$

\begin{align*}p(x)&=p(x_1; \mu_1, \sigma_1^2)p(x_2; \mu_2, \sigma_2^2)\ldots p(x_n; \mu_n, \sigma_n^2) \\ &= \prod\limits_{j=1}^n p(x_j; \mu_j, \sigma_j^2)\end{align*}

算法步驟：

1. 特征選擇：選擇能夠指示異常行為的特征

2. 參數估計：用訓練數據集估計每個特征的整體均值$\mu_j$和方差$\sigma_j^2$，即$\mu_j = \frac{1}{m}\sum\limits_{i=1}^{m}x^{(i)}_j$, $\sigma^2_j=\frac{1}{m}\sum\limits_{i=1}^{m}(x^{(i)}_j-\mu_j)^2$

3. 用估計得到的參數$\mu_1, \mu_2, \ldots, \mu_n$,  $\sigma^2_1, \sigma^2_2, \ldots, \sigma^2_n$建立模型$p(x)$；

4. 對于給定新的數據點$x_{new}$, 計算$p(x_{new})$；如果$p(x_{new})<\epsilon$則發生異常，否則正常。

算法評估:

給定訓練數據集(去掉標簽建立模型)中$\{x^{(1)}, x^{(2)}, \ldots, x^{(m)}\}$，訓練模型$p(x)$。在交叉驗證集(帶標簽)中，如果$p(x_{cv})<\epsilon$，則預測$y=1$；否則預測$y=0$。最后計算指標Precison/Recall/F1Score等來評估算法性能。注意：也可以用驗證集來選擇閾值$\epsilon$.

異常檢測與監督式學習對比：

特征選擇：

選擇的特征需要近似服從于高斯分布，如果明顯不服從高斯分布，可以做適當的轉換，例如$log(x), log(x+c), \sqrt{x}, x^{1/3}$等

多元高斯分布

之前的模型假設各個特征之間是相互獨立的，因此模型$p(x)$將個特征取值的概率相乘【$P(AB)=P(B)P(A|B)=P(A)P(B|A)$，當且僅當事件AB相互獨立時才有$P(AB)=P(A)P(B)$】；然而當各個特征之間存在依賴關系時，一元的高斯模型將不能很好的刻畫$p(x)$，需要多元高斯模型。模型$p(x)$的建立不再是各個概率相乘，而直接用多元高斯分布進行刻畫$$p(x;\mu, \Sigma)=\frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}}\exp\left(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)\right)$$ 其中$\mu$是$n$維行向量，$\mu=\frac{1}{m}\sum\limits_{i=1}^{m}x^{(i)}$； $\Sigma$是$n\times n$協方差矩陣，$\Sigma=\frac{1}{m}\sum\limits_{i=1}^{m}(x^{(i)}-\mu)(x^{(i)}-\mu)^T$，圖3給出了在不同參數取值下的二維高斯模型及其對應的等高線圖。

圖3 二維高斯分布及其對應的等高線圖

多元高斯模型和一元高斯模型的關系：當協方差矩陣$\Sigma$是對角陣且對角線元為一元高斯分布的估計參數$\sigma_j^2$時，兩個模型是等價的。區別在于前者能夠自動獲取特征之間的依賴關系而后者不能(后者假設特征之間是獨立的)。當特征數$n$很大時，前者計算代價高昂而后者計算速度快。前者適用于$m>n$(一般要求$m>10n$)的情況，而后者當$m$很小時依然適用。

推薦系統

電影推薦系統問題：根據用戶對已看過電影的打分，對用戶未看過的電影(下表中以?表示)進行打分估計，以給其推薦合適的電影。

符號說明：

• $n_u$表示用戶數量
• $n_m$表示電影數量
• $r(i, j)$是符號變量，如果用戶$j$已經對電影$i$進行評分則$r(i, j)=1$；反之，如果用戶$j$尚未對電影$i$進行評分則$r(i, j)=0$.
• $y^{(i, j)}$表示用戶$j$對電影$i$的評分（如果用戶$j$對電影$i$已經評分，即$r(i, j)=1$）.

基于內容的推薦

對每一部電影$i$抽出若干特征，然后每個用戶$j$學習一個參數向量$\theta^{(j)}$，然后用$(\theta^{(j)})^Tx^{(i)}$來估計用戶$j$對電影$i$的評分。例如對于上面的表格，我們對每一個電影抽取出2個特征$x_1,x_2$(對應表格最后2列)，然后每個用戶$j$學習一個參數向量$\theta^{(j)}\in R^3$（包含bias項$\theta_0=1$以及$x_1, x_2$的系數$\theta_1, \theta_2$）,然后就可以用$(\theta^{(j)})^Tx^{(i)}$來預測評分。為了學習參數$\theta$，定義代價函數為$$J(\theta^{(1)},\theta^{(2)},\ldots,\theta^{(n_u)})=\frac{1}{2}\sum\limits_{j=1}^{n_u}\sum\limits_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum\limits_{j=1}^{n_u}\sum\limits_{k=1}^n(\theta^{(j)}_k)^2$$

梯度下降法的參數更新：$$\theta_k^{(j)}=\theta_k^{(j)}-\alpha\left(\sum\limits_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_k^{(i)}+\lambda\theta_k^{(j)}\right)\quad k > 0$$ $$\theta_k^{(j)}=\theta_k^{(j)}-\alpha\sum\limits_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_k^{(i)}\quad k = 0$$

協同過濾(Collaborative Filtering)

基于內容的推薦假設電影的特征(如$x_1$, $x_2$)是已知的，僅需要學習參數$\theta$；然而實際中電影的特征是未知的，現在假定已知用戶的參數$\theta$，需要學習電影的特征$x$，與上面的代價函數類似，定義$$J(x^{(1)},x^{(2)},\ldots,x^{(n_m)})=\frac{1}{2}\sum\limits_{i=1}^{n_m}\sum\limits_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum\limits_{i=1}^{n_m}\sum\limits_{k=1}^n(x^{(i)}_k)^2$$這樣我們發現，給定電影特征$x$可以學習到用戶參數$\theta$；反之給定用戶參數$\theta$可以學習到特征$x$。因此可以先隨機猜一個$\theta$，然后學習$x$，再由學習到的$x$學習$\theta$，然后不斷重復即可。然而事實上，兩個參數$x, \theta$可以如下同時更新，從而得到協同過濾的推薦算法$$J(x^{(1)},x^{(2)},\ldots,x^{(n_m)},\theta^{(1)},\theta^{(2)},\ldots,\theta^{(n_u)})=\frac{1}{2}\sum\limits_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum\limits_{j=1}^{n_u}\sum\limits_{k=1}^n(\theta^{(j)}_k)^2+\frac{\lambda}{2}\sum\limits_{i=1}^{n_m}\sum\limits_{k=1}^n(x^{(i)}_k)^2$$

協同過濾算法步驟:

1. 初始化參數$x^{(1)},x^{(2)},\ldots,x^{(n_m)},\theta^{(1)},\theta^{(2)},\ldots,\theta^{(n_u)}$為隨機數，其中$x\in R^n$表示電影特征，$\theta \in R^n$表示用戶參數（注：不包含bias參數$\theta_0$）

2. 使用梯度下降或者其他高級優化算法，進行參數更新

$$x_k^{(i)}=x_k^{(i)}-\alpha\left(\sum\limits_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_k^{(i)}+\lambda x_k^{(i)}\right)$$$$\theta_k^{(j)}=\theta_k^{(j)}-\alpha\left(\sum\limits_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_k^{(i)}+\lambda\theta_k^{(j)}\right)$$

3. 用學習到的參數$\theta$和$x$預測電影評分$\theta^Tx$

低秩矩陣分解(Low rank matrix factorization)

協同過濾與低秩矩陣分解：協同過濾算法要求評分矩陣$Y$中元素$y^{(i,j)}$越接近$(\theta^{(j)})^T x^{(i)}$越好，因此參數$\theta$和$x$的求解，實際上等價于尋找兩個矩陣$X$和$\Theta$使得$Y \approx X\Theta^T$，從而協同過濾問題可以轉化為低秩矩陣分解問題。

均值歸一化：對于尚未評分任何電影的用戶，可以對$Y$矩陣按行求平均值作為該用戶的初始評分；用均值化矩陣$Y-\mu$進行參數學習，然后用$(\theta^{(j)})^T\theta^{(i)}+\mu_i$進行評分預測。

參考文獻

[1] Andrew Ng Coursera 公開課第九周

[2] Recommender Systems: Collaborative Filtering. http://recommender-systems.org/collaborative-filtering/

[3] Wikipedia: Low-rank approximation https://en.wikipedia.org/wiki/Low-rank_approximation