[發明專利]通過劃分網絡空間計算單隱層ReLU神經網絡全局最優解的圖像分類方法

在審

• 申請號: 202110184449.8
• 申請日: 2021-02-10
• 公開（公告）號: CN112819086A
• 公開（公告）日: 2021-05-18
• 發明（設計）人: 劉波;包文強
• 申請（專利權）人: 北京工業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N3/04;G06N3/08
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 劉萍

1.通過劃分網絡空間計算單隱層ReLU神經網絡全局最優解的圖像分類方法，其特征在于，包含以下幾個步驟：

(1)挑選數據集；使用原始的MNIST數據集和經過線性判別分析將原始的MNIST數據集降至2維后的數據，分別用于對高維和低維兩種情況下的實驗；

(2)使用局部敏感哈希原理對讀取的MNIST數據集進一步的篩選；由于局部敏感哈希原理可以在一個相對比較高的概率下篩選出一些更具有代表性的樣本，用一系列的哈希函數，將原始MNIST數據集映射至1維后，再定義新的哈希函數對數據進行“哈希分桶”；收集經過一系列哈希函數映射后均落入同一個桶中的數據，將這些數據作為最終的神經網絡的輸入數據，其余數據舍棄；

(3)搭建神經網絡；使用具有d個輸入神經元、K個ReLU單隱層神經元和1個輸出神經元的神經網絡；

(4)神經網絡權值空間的劃分；令x表示輸入樣本向量，w表示輸入層到隱藏層的權值向量，根據ReLU函數的性質，如果輸入樣本的向量與隱藏層神經元的權重向量在同一個方向，有w·x＞0成立，可以通過ReLU函數被激活；反之，輸入樣本向量與隱藏層神經元權重向量方向相反，則w·x≤0，不會被ReLU函數激活；

激活部分與不激活部分將整個神經網絡的權值空間劃分為兩個不同的區域，樣本向量x則可以抽象地理解為神經元權值空間的超平面；那么，若干個輸入樣本向量x就將權值空間劃分為若干個不用的區域，簡稱“單元格”；

(5)神經網絡全局最優解的計算；假定單元格是凸的，損失函數是均方誤差損失，則求解出來的參數空間中該單元格中的損失函數局部極小值就是該單元格中的損失函數全局最小值；求解出網絡空間中所有單元格中損失函數的局部極小值，返回其中的最小值計算出整個神經網絡的全局最優解。

2.根據權利要求1所述的方法，其特征在于：

步驟1：數據集的準備

使用的是經過線性判別分析將原始的MNIST手寫數字數據集降至2維后的數據集和原始784維度的MNIST手寫數字數據集，分別用于對低維和高維這兩種情況下的深度神經網絡全局最優解的計算；

先將MNSIT數據集按照0-9標簽的順序存到一個新的文件中；因為MNIST數據集的訓練樣本是10類數據并不是等分的，所以每個不同標簽的數據均等量挑選；

步驟2：使用局部敏感哈希原理對數據進行預處理；

使用局部敏感哈希會使得相鄰的數據落入到同一個“哈希桶”中，收集通過一系列的哈希函數映射后均落入到同一個哈希桶中的數據作為最終的樣本數據；

將步驟1中的MNIST數據集按照標簽0-9的順序重新存儲到一個新的列表中并保證不同標簽的數據集個數相等；

采用如下公式，將MNIST數據集中的降至1維，公式如下：

h(v)＝v·x

其中，矩陣v代表的是一個(N，784)的MNIST數據集向量，N為挑選的MNIST數據集的個數，x代表的是一個(784，1)用作降維的向量；將N個相同標簽的數據數據集通過上述公式運算后映射為1維的點，即映射結果為(N，1)的向量；

下面將降維好的樣本進行哈希分桶挑選數據集，采用下述哈希函數：

其中v是(N，784)的原始MNIST數據集向量，x代表的是一個(784，1)用作降維的向量，w是哈希分桶的寬度，b是0到w間的一個均勻分布；采用了m個哈希函數同時進行分桶，同時掉進m哈希函數的同一個桶中的若干個點，其相似度最大；

步驟3：單隱層ReLU神經網絡的參數搭建；

使用具有d個輸入神經元、K個ReLU激活的單隱層神經元和1個輸出神經元的深度神經網絡；定義[N]來表示{1，2，3…，N}的縮寫，即神經網絡的輸入樣本個數是N；定義[K]來表示{1，2，3…，K}的縮寫，表示神經網絡隱藏神經元的個數為K；其中輸入樣本用(x_i，y_i)來表示，x_i是第i個輸入樣本的向量，i∈[N]，y_i∈±1是x_i的標簽，連接輸入神經元和隱藏神經元之間的權向量記為w_j，連接隱藏神經元與輸出神經元之間的權重向量記為z_j，j∈[K]，則單隱層ReLU神經網絡的損失函數公式如下述：

其中z＝{z_k，k∈[K]}，w＝{w_k，k∈[K]}，[w_j·x_i]₊＝max(0，w_j·x_i)為ReLU函數，y_i為第i個樣本的標簽，表示第i個樣本的損失函數值，表示對N個樣本的損失函數做平均處理，L(z，w)為整個神經網絡的損失函數；損失函數具體化為均方誤差損失；

引入變量I_ij作為ReLU激活函數的取值，表示的是第i個輸入樣本在第j個隱藏神經元上的激活情況，即，如果w_j·x_i＞0，則I_ij＝1，表示第i個輸入樣本第j個隱藏神經元上被激活；否則等于0，表明第i個輸入樣本在第j個隱藏神經元上不被激活；

將輸入層到隱藏層的神經元權重與隱藏層到輸出層的權值w和z進行積分，定義R_j＝z_j·w_j；其中R＝{R_j，j∈[K]}，K表征的是具有K個隱藏神經元，這樣的轉換在很大程度上隱藏了兩層權重的復雜性；則損失函數被重新寫為：

其中，L(R)表示神經網絡的損失函數；表示第i個樣本的損失函數；表示對N個樣本的損失函數做平均處理；中的中I_ij表明第i個輸入樣本在第j個隱藏神經元上的激活情況，即ReLU函數的取值；R_j表明的輸入層到隱藏層的神經元權重與隱藏層到輸出層的權值w和z的積分；x_i是第i個輸入樣本，y_i為第i個樣本的標簽；

對于單隱層ReLU神經網絡，樣本向量x是參數空間w中的超平面；樣本(x_i，i∈[N])將w空間劃分為若干個凸的單元格；因此，每個權值w_j都位于某一單元格內部或單元格邊界上；如果所有的權值(w_j，j∈[K])都位于單元格內，并且在單元格內移動而不跨越邊界，則上述公式中的I_ij(I∈[N])的值是常數，因此損失L在這些單元格內是(R_j，j∈[K])的可微函數；將其中(w_j，j∈[K])的單元稱為定義單元格；當越過兩個單元格的邊界時I_ij在邊界處從1變為0；因此，損失函數L在邊界處是不可微的；

步驟4：根據凸單元格中的所有局部極小值就是全局最小值的定理來計算單元格中局部最小值；

則損失函數的解析解是下述公式：

其中R^*為損失函數的解，表示對N個樣本的損失函數做平均處理，I_ij為第i個樣本在第j個神經元中的ReLU函數的取值，x_i表示第i個樣本，y_i表示第i個樣本的標簽；

通過上式求得神經網絡權值的線性解由下述公式表征：

定義I_ij·x_i＝A，則上式解析解改寫為如下的矩陣形式：

其中表明x_i轉置；并且則上述矩陣中R的解為：

其中表示矩陣A的Moore-Penrose偽逆矩陣，y是樣本的標簽向量，c∈R^Kd代表的是任意向量，其中R為實數集合，K表示的是隱藏神經元的個數，d表示的是輸入神經元的個數，即c是屬于K·d范圍內的實數集向量，I是單位矩陣；

矩陣的最優解R^*表征的就是神經網絡的權值參數{w^*，z^*}的最優解；R^*被如下兩種情況所表征：

(1)R^*有唯一解；即當且僅當rank(A)＝Kd，矩陣A為滿秩矩陣；將矩陣A進行分解，可得矩陣的解可以表示為：

(2)R^*有無限個連續的解；此時，rank(A)≠Kd；首先N＜Kd，此時矩陣有無數個解；其次N≥Kd但rank(A)＜Kd，舉例就是一些隱藏的神經元并不是被所有的樣本激活；

處在單元格中的最優解或者是唯一的或者是連續的，將矩陣的解R^*帶入到損失函數可得最優解：

其中，其中表示矩陣A的Moore-Penrose的偽逆矩陣，y表示樣本的標簽，表示損失函數的L₂范數的平方，表示對N個樣本的損失函數做平均處理；

在上述矩陣的解向量中，涵蓋輸入樣本向量x和ReLU函數的取值I_ij；由于樣本向量x可知，只要求解出ReLU激活函數的取值I_ij即可利用該公式計算出神經網絡的參數解R^*；

步驟5：在2維空間中，利用計算幾何領域里線排列中的雙向鏈接邊表結構體來可視化上述步驟中的可微單元格，神經網絡損失函數最小值就處在某一個雙向鏈接邊表中；

在計算幾何中存在雙向鏈接邊表的結構體，利用每個雙向鏈接邊表來表示每個不同的單元格并且雙向鏈接邊表的每一條邊的里邊和外邊分別代表順時針和逆時針這兩個不同的方向，顯然時針轉向相同的邊必然能夠表征凸的單元格；通過應用該結構體可以將參數空間中的單元格可視化呈現出來；

對于2維的輸入樣本，使用2維空間的點來表示數據樣本，使用2維空間中的直線來表示由ReLU函數將神經網絡參數空間劃分出來的單元格，使用2維空間中的平面表示整個神經網絡的權值空間；因為在整個平面空間的計算過程中，需要一個有限的范圍將樣本劃分出來的單元格包圍起來，可以利用計算幾何中線排列的相關理論來構造整個外圍的包圍框；隨著樣本的不斷增多，使用遞增式算法逐一增加與神經網絡參數空間相對應的雙向鏈接邊表，并通過遍歷雙向鏈接邊表從每一個劃分的區域中的樣本點來計算步驟4中的I_ij(i∈[N]，j∈[K])的所有取值；

計算出來I_ij(i∈[N])的所有取值之后，使用步驟4中的神經網絡參數空間的求解矩陣來求解出每個單元格中的損失函數值，進而比對出所有單元格中的損失函數最小值，此時的神經網絡權值的取值即為整個網絡空間的最優解。