REPLICATOR NEURAL NETWORKS

01-31

本文將會從 Replicator Neural Networks 出發，介紹這個神經網路的使用場景以及神經網路的後向傳播演算法（back propagation）。之前的文章的鏈接是《異常點檢測演算法（三）》。

異常值檢測演算法在數據挖掘的諸多領域有著應用場景，例如金融領域，信息傳輸領域，圖像領域等。在研究過程中，有學者給出了異常點的一個定義：

An outlier is an observation that deviates so much from other observations as as to arouse suspicion that it was generated by a different mechanism.

RNN 演算法的主要思想

在這篇文章中，我們將會介紹一個多層的前饋神經網路，該神經網路可以用來進行異常值的檢測。這個神經網路模擬的是一個恆等映射，輸入層的神經元個數和輸出層的神經元個數是一樣的。這類的神經網路被稱為 Replicator Neural Networks (RNNs)，請注意這裡的 RNN 演算法指的並不是 Recurrent Neural Networks（RNNs），而是 Replicator Neural Networks，儘管它們擁有著同樣的縮寫名字 RNNs。具體來說， Replicator Neural Networks (RNNs)，或者說自編碼器，是一個多層前饋的神經網路 (multi-layer feed-forward neural networks)。在 Replicator Neural Networks 中，輸入的變數也是輸出的變數，模型中間層節點的個數少於輸入層和輸出層節點的個數。這樣的話，模型就起到了壓縮數據和恢複數據的作用。

如圖所示，這裡的 RNNs 有三個隱藏層，輸入層和輸出層的節點個數都是6，第一個隱藏層和第三個隱藏層的節點個數（圖中是4個節點）少於輸入層，第二個隱藏層的節點個數是最少的（圖中是2個節點）。在神經網路傳輸的時候，中間使用了 tanh 函數和 sigmoid 函數。這個神經網路是訓練一個從輸入層到輸出層的恆等函數（identity mapping），傳輸的時候從輸入層開始壓縮數據，然後到了第二個隱藏層的時候開始解壓數據。訓練的目標就是使得整體的輸出誤差足夠小，整體的誤差是由所有的樣本誤差之和除以樣本的個數得到的。由於圖中只畫出了6個特徵，因此第 $i$ 個樣本的誤差是 $e_i=sum_{j=1}^{6}frac{(x_{ij}-r_{ij})^{2}}{6}.$

如果使用已經訓練好的 RNN 模型，異常值的分數就可以定義為重構誤差（reconstruction error）。

下面簡要介紹一下 RNN 模型是如何構建的：

根據上圖所示，左邊的是輸入層，右邊的輸出層。假設第 $k$ 層中第 $i$ 個神經元的輸出是 $S_{k}(I_{ki})$ ，其中 $I_{ki}$ 表示第 $k$ 層中第 $i$ 個神經元的輸入， $S_{k}$ 表示第 $k$ 層使用的激活函數。那麼 $theta=I_{ki}=sum_{j=0}^{L_{k-1}}w_{kij}Z_{(k-1)j},$ 其中 $Z_{kj}$ 是第 $k$ 層中第 $j$ 個神經元的輸出， $L_{k}$ 是第 $k$ 層神經元的個數。對於第二層和第四層而言 ( $k=2,4$ )，激活函數選擇為

$S_{k}(theta)=tanh(a_{k}theta) text{ for } k=2 text{ or } 4,$

這裡的 $a_{k}$ 是一個參數，通常假設為 $1$ 。對於中間層 ( $k=3$ ) 而言，激活函數是一個類階梯 (step-like) 函數。有兩個參數 $N$ 和 $a_{3},$ $N$ 表示階梯的個數， $a_{3}$ 表示從這一層到下一層的提升率 (transition rate)：

$S_{3}(theta)=frac{1}{2} + frac{1}{4}sum_{j=1}^{N-1}tanh(a_{3}(theta-frac{j}{N})).$

在這裡可以假設 $a_{3}=100,$ $N=4.$ . 那麼 $S_{3}(theta)$ 就如下圖所示。

第三層的激活函數的輸出就變成了 $N$ 個離散的變數： $0,frac{1}{N-1},frac{2}{N-2},cdots,1$ 。這個階梯型的激活函數是把第三層的連續輸入值變成了一批離散的值。也就意味著把樣本映射到了 $N$ 個簇，那麼 RNN 就可以計算出單個的異常點和一小簇的異常點。

備註：

根據上面的分析，可以看出如果按照以上演算法，則不能使用反向傳播演算法來訓練模型，原因是 $S_{3}(theta)$ 的導數不能夠通過它的取值來表示。這一點與 $tanh$ 函數和 $sigma$ 函數是不一致的，因為 $tanh^{}(x) = 1-tanh^{2}(x)$ 和 $sigma^{}(x)=sigma(x)(1-sigma(x)).$

因此有學者指出 [1]，使用三個隱藏層是沒有必要的，使用1個或者2個隱藏層的神經網路也能夠得到類似的結果；同樣，沒有必要使用 $S_{3}(theta)$ 這樣類型的階梯函數，使用傳統的 $sigma$ 激活函數也能夠得到類似的結果。並且 $S_{3}(theta)$ 是一個 step-like 函數，很多地方的導數取值都是接近於零的。

後向傳播演算法：

一般來說，為了訓練神經網路模型，需要使用後向傳播演算法（back propagation），也簡稱為 BP 演算法，或者誤差逆傳播演算法（error back propagation）。在本文中，僅針對最簡單的 RNN 模型介紹如何使用 BP 演算法進行模型訓練，至於多層的神經網路模型或者其他的神經網路模型，方法則是完全類似的。

給定訓練集合 $D={(bold{x}_{1},bold{y}_{1}),...,(bold{x}_{m},bold{y}_{m})},$ 其中有 $m$ 個樣本，並且輸入和輸出是一樣的值。換句話說，也就是 $n$ 維向量 $bold{x}_{i}=bold{y}_{i}inmathbb{R}^{n} text{ for all } 1leq ileq m.$

換句話說，輸入樣例是由 $n$ 個屬性描述，輸出的結果也是 $n$ 個屬性。隱藏層只有一個，隱藏層的神經元個數是 $q=[(n+1)/2],$ 這裡的 $[]$ 表示 Gauss 取整函數。輸出層第 $j$ 個神經元的閾值使用 $theta_{j}.$ 表示，隱藏層第 $h$ 個神經元的閾值使用 $gamma_{h}$ 表示。輸入層第 $i$ 個神經元與隱藏層第 $h$ 個神經元之間的連接權重是 $v_{i h}$ , 隱藏層第 $h$ 個神經元與輸出層第 $j$ 個神經元之間的連接權重是 $w_{h j},$ 其中 $1leq i leq n, 1leq h leq q, 1leq j leq n.$

記隱藏層第 $h$ 個神經元接收到的輸入為 $alpha_{h} = sum_{i=1}^{n}v_{i h}x_{i} text{ for all } 1leq h leq q.$

寫成矩陣形式就是： $(alpha_{1},cdotcdotcdot,alpha_{q})=(x_{1},cdotcdotcdot,x_{n})begin{bmatrix} v_{11} & ... & v_{1q} ... & ... & ... v_{n1} & ... & v_{nq} end{bmatrix}.$

記輸出層第 $j$ 個神經元接收到的輸入為 $beta_{j}=sum_{h=1}^{q}w_{h j}b_{h} text{ for all } 1leq jleq n,$ 其中 $b_{h}$ 是隱藏層第 $h$ 個神經元的輸出， $b_{h} = f(alpha_{h}-gamma_{h}) text{ for all } 1leq h leq q,$ 其中 $f$ 是激活函數。寫成矩陣形式就是： $(beta_{1},cdotcdotcdot,beta_{n})=(b_{1},cdotcdotcdot,b_{q})begin{bmatrix} w_{11} & ... & w_{1n} ... & ... & ... w_{q1} & ... & w_{qn} end{bmatrix}.$ 輸出層第 $j$ 個神經元的輸出是 $f(beta_{j}-theta_{j}),$ 其中 $1leq jleq n.$

下面可以假定激活函數都使用 $f(x)=1/(1+exp(-x)),$ 那麼直接通過導數計算可以得到 $f^{}(x)=f(x)(1-f(x)).$

對於訓練集 $(bold{x}_{k},bold{y}_{k}),$ 通過神經網路得到的輸出是 $hat{bold{y}}_{k}=(hat{y}_{k1},...,hat{y}_{kn}),$ 並且 $hat{y}_{kj} = f(beta_{j}-theta_{j}).$

對於 $1leq j leq n$ 都成立。那麼神經網路在訓練集 $(bold{x}_{k},bold{y}_{k})$ 的均方誤差是

$E_{k} =frac{1}{2}sum_{j=1}^{n}(hat{y}_{kj}-y_{kj})^{2},$

其中 $bold{y}_{k}=(y_{k1},...,y_{kn}).$

整體的誤差是

$E = frac{1}{m}sum_{k=1}^{m}E_{k} = frac{1}{2m}sum_{k=1}^{m}sum_{j=1}^{n}(hat{y}_{kj}-y_{kj})^{2}.$

標準 BP 演算法：

網路中有 $2nq+n+q$ 個參數需要確定：輸入層到隱藏層的 $nq$ 個權重值，隱藏層到輸出層的 $nq$ 個權重值， $q$ 個隱層神經元的閾值， $n$ 個輸出層神經元的閾值。BP 演算法是一個迭代學習演算法，在迭代的每一輪採用了梯度下降法來進行參數的更新。任意參數的更新規則是

$v leftarrow v + Delta v.$

標準 BP 演算法是根據每一個 $E_{k}$ 來獲得更新規則，下面來推導每一個參數的更新規則。對於 $1leq h leq q, 1leq j leq n,$

計算梯度 $Delta w_{hj} = -eta frac{partial E_{k}}{partial w_{hj}},$

注意到 $w_{hj}$ 先影響到第 $j$ 個輸出層神經元的輸入值 $beta_{j},$ 再影響到第 $j$ 個輸出層神經元的輸出值 $hat{y}_{kj},$ 最後影響到 $E_{k},$ 根據高等數學的鏈式法則可以得到

$frac{partial E_{k}}{partial w_{hj}} = frac{partial E_{k}}{partial hat{y}_{kj}} cdot frac{partial hat{y}_{kj}}{partial beta_{j}} cdot frac{partial beta_{j}}{partial w_{hj}}.$

根據定義 $beta_{j}=sum_{h=1}^{q}w_{hj}b_{h}$ 可以得到 $frac{partial beta_{j}}{partial w_{hj}}=b_{h}$ 對於 $1leq j leq n$ 都成立。

根據定義 $E_{k}=frac{1}{2}sum_{j=1}^{n}(hat{y}_{kj}-y_{kj})^{2}$ 可以得到 $frac{partial E_{k}}{partial hat{y}_{kj}}=(hat{y}_{kj}-y_{kj}).$

根據定義 $hat{y}_{kj}=f(beta_{j}-theta_{j})$ 和 $f^{}(x)=f(x)cdot(1-f(x))$

可以得到 $frac{partial hat{y}_{kj}}{partial beta_{j}}=f^{}(beta_{j}-theta_{j})=f(beta_{j}-theta_{j})cdot(1-f(beta_{j}-theta_{j}))=hat{y}_{kj}cdot (1-hat{y}_{kj}).$

所以可以計算出對於 $1leq h leq q, 1leq j leq n,$

有 $frac{partial E_{k}}{partial w_{hj}} = (hat{y}_{kj}-y_{kj})cdothat{y}_{kj}cdot(1-hat{y}_{kj})cdot b_{h}$

如果假設 $g_{j}=-frac{partial E_{k}}{partial beta_{j}}=-frac{partial E_{k}}{partial hat{y}_{kj}}cdot frac{hat{y}_{kj}}{partial beta_{j}},$

那麼可以得到 $g_{j}=hat{y}_{kj}cdot(1-hat{y}_{kj})cdot(y_{kj}-hat{y}_{kj})$

因此對於 $1leq h leq q, 1leq j leq n,$

可以得到 $Delta w_{hj}=eta g_{j}b_{h}.$

根據類似的想法，有

$Delta theta_{j}=-etacdotfrac{partial E_{k}}{partial theta_{j}},$ $Delta v_{ih}=-etacdotfrac{partial E_{k}}{partial v_{ih}},$ $Delta gamma_{h}=-etacdotfrac{partial E_{k}}{partial gamma_{h}}.$

逐個計算： $frac{partial E_{k}}{partial theta_{j}}=frac{partial E_{k}}{partial hat{y}_{kj}}cdotfrac{partialhat{y}_{kj}}{partialtheta_{j}}=(hat{y}_{kj}-y_{kj})cdot(-1)cdot f^{}(beta_{j}-theta_{j})$

$=(y_{kj}-hat{y}_{kj})cdothat{y}_{kj}cdot(1-hat{y}_{kj})=g_{j},$

$frac{partial E_{k}}{partial v_{ih}}=frac{partial E_{k}}{partialalpha_{h}}cdotfrac{partialalpha_{h}}{partial v_{ih}}=frac{partial E_{k}}{partial b_{h}}cdotfrac{partial b_{h}}{partial alpha_{h}}cdotfrac{partialalpha_{h}}{partial v_{ih}}.$

由於 $frac{partial alpha_{h}}{partial v_{ih}}=x_{ki},$

$frac{partial b_{h}}{partialalpha_{h}}=f^{}(alpha_{h}-gamma_{h})=f(alpha_{h}-gamma_{h})cdot(1-f(alpha_{h}-gamma_{h}))=b_{h}cdot(1-b_{h}),$

$frac{partial E_{k}}{partial b_{h}}=sum_{j=1}^{n}frac{partial E_{k}}{partial beta_{j}}cdotfrac{partial beta_{j}}{partial b_{h}}=sum_{j=1}^{n}(-g_{j})cdot w_{hj},$

所以，

$Delta v_{ih}=eta(sum_{j=1}^{n}g_{j}w_{hj})cdot b_{h}cdot (1-b_{h})x_{ki} = eta e_{h}x_{ki},$

其中 $e_{h}=-partial E_{k}/partialalpha_{h}=(sum_{j=1}^{n}g_{j}w_{hj})cdot b_{h}cdot(1-b_{h}).$

$Delta gamma_{h}=(-eta)cdotfrac{partial E_{k}}{partialgamma_{h}}=(-eta)cdotfrac{partial E_{k}}{partial b_{h}}cdotfrac{partial b_{h}}{partialgamma_{h}}$

$=etacdot(sum_{j=1}^{n}g_{j}w_{hj})cdot(-1)cdot f^{}(alpha_{h}-gamma_{h})$

$=(-eta)cdot(sum_{j=1}^{n}g_{j}w_{hj})cdot b_{h}cdot(1-b_{h})=(-eta)cdot e_{h}.$

整理之後，任意參數 $v$ 的更新式子是 $vleftarrow v + Delta v,$ 並且更新的規則如下： $Delta w_{hj}=eta g_{j}b_{h} text{ for all } 1leq jleq n, 1leq h leq q,$

$Delta theta_{j}=-eta g_{j} text{ for all } 1leq jleq n,$

$Delta v_{ih}=eta e_{h}x_{ki} text{ for all } 1leq ileq n, 1leq hleq q,$

$Delta gamma_{h}=-eta e_{h} text{ for all } 1leq hleq q,$

其中學習率 $etain(0,1)$ 控制著演算法每一輪迭代中的更新步長，若步長太大則容易振蕩，太小則收斂速度過慢，需要人工調整學習率。對每個訓練樣例，BP 演算法執行下面的步驟：先把輸入樣例提供給輸入層神經元，然後逐層將信號往前傳，直到計算出輸出層的結果；然後根據輸出層的誤差，再將誤差逆向傳播至隱藏層的神經元，根據隱藏層的神經元誤差來對連接權和閾值進行迭代（梯度下降法）。該迭代過程循環進行，直到達到某個停止條件為止。

標準 BP 演算法的訓練流程：

輸入：訓練集合 $D=(bold{x}_{k},bold{y}_{k})_{k=1}^{m}$ 和學習率 $eta.$

過程： 1. 在 $(0,1)$ 範圍內隨機神經網路中的所有連接權重和閾值

2. repeat

for all $(bold{x}_{k},bold{y}_{k})$ do

根據當前參數，計算出當前的樣本輸出 $bold{y}_{k}.$

計算輸出層神經元的梯度項 $g_{j}$

計算隱藏層神經元的梯度項 $e_{h}$

更新連接權重 $w_{hj}, v_{ih}$ 與閾值 $theta_{j},gamma_{h}$

end for

3. 達到停止條件

輸出：鏈接權與閾值都確定的神經網路模型

累積 BP 演算法：

BP 演算法的目的是最小化訓練集上的累計誤差 $E=frac{1}{m}sum_{k=1}^{m}E_{k},$ 其中 $m$ 是訓練集合中樣本的個數。不過，標準的 BP 演算法每次僅針對一個訓練樣例更新連接權重和閾值，也就是說，標準 BP 演算法的更新規則是基於單個的 $E_{k}$ 推導而得到的。通過類似的計算方法可以推導出累計誤差的最小化更新規則，那就得到了累計誤差逆傳播（accumulate error backpropagation）演算法。標準 BP 演算法需要進行更多次的迭代，並且參數的更新速度快，累積 BP 演算法必須掃描一次訓練集合才會進行一次參數的更新，而且累計誤差下降到一定的程度以後，進一步下降就會明顯變慢，此時標準 BP 演算法往往會更快的得到較好的解，尤其是訓練集合大的時候。

訓練方法：

（1）把數據集合的每一列都進行歸一化；

（2）選擇 70% 的數據集合作為訓練集合，30% 的數據集合作為驗證集合。或者訓練集合 : 驗證集合 = 8 : 2，這個需要根據情況而定。

（3）隨機生成一個三層的神經網路結構，裡面的權重都是隨機生成，範圍在 [0,1] 內。輸入層的數據和輸出層的數據保持一致，並且神經網路中間層的節點個數是輸入層的一半。

（4）使用後向傳播演算法（back-propagation）來訓練模型。為了防止神經網路的過擬合，通常有兩種策略來防止這個問題。（i）第一種策略是「早停」（early stopping）：當訓練集合的誤差降低，但是驗證集合的誤差增加時，則停止訓練，同時返回具有最小驗證集合誤差的神經網路；（ii）第二種策略是「正則化」（regularization）：基本思想是在誤差目標函數中增加一個用於描述網路複雜度的部分，例如鏈接權和閥值的平方和。

測試效果：

其中藍色的點表示正常點，紅色的點表示被 RNN 演算法標記的異常點。

參考文獻：

Anomaly Detection Using Replicator Neural Networks Trained on Examples of One Class, Hoang Anh Dau, Vic Ciesielski, Andy Song
Replicator Neural Networks for Outlier Modeling in Segmental Speech Recognition, Laszlo Toth and Gabor Gosztolya
Outlier Detection Using Replicator Neural Networks, Simon Hawkins, Honxing He, Graham Williams and Rohan Baxter