神經(jīng)網(wǎng)絡(luò)算法在矩陣積和式估值問(wèn)題上的應(yīng)用

1、神經(jīng)網(wǎng)絡(luò)算法在矩陣積和式估值問(wèn)題上的應(yīng)用（申請(qǐng)清華大學(xué)理學(xué)碩士學(xué)位論文）培養(yǎng)單位 學(xué) 科 申請(qǐng)人 指導(dǎo)教師數(shù)學(xué)科學(xué)系數(shù)學(xué)張碩平梁恒教授二。一七年五月The Application of Neural Network onPermanent EstimationThesis Submitted toTsinghua Universityin partial fulfillment of the requirementfor the professional degree ofMaster of ScienceinMathematicsbyZhang ShuopingThesis Supervis

2、or:Professor Liang HengMay, 2017摘要摘要本文主要研究了神經(jīng)網(wǎng)絡(luò)算法在矩陣積和式估值問(wèn)題上應(yīng)用，分析了卷積神 經(jīng)網(wǎng)絡(luò)和人工神經(jīng)網(wǎng)絡(luò)在預(yù)測(cè)矩陣積和式對(duì)數(shù)值問(wèn)題中各自的優(yōu)劣。深入探討了 在不同網(wǎng)絡(luò)結(jié)構(gòu)，不同的訓(xùn)練數(shù)據(jù)集等因素下，神經(jīng)網(wǎng)絡(luò)算法預(yù)測(cè)效果和時(shí)間復(fù) 雜度。通過(guò)實(shí)驗(yàn)，我們證明了，對(duì)于8-18階矩陣，HF-CNN結(jié)構(gòu)的卷積神經(jīng)網(wǎng)絡(luò) 和特征-ANN結(jié)構(gòu)的人工神經(jīng)網(wǎng)絡(luò)可以在保證較低的時(shí)間復(fù)雜度的情況下，對(duì)矩陣 積和式的對(duì)數(shù)值做出有效的估計(jì)。在此基礎(chǔ)上，我們通過(guò)結(jié)合其他算法，進(jìn)一步 提高了神經(jīng)網(wǎng)絡(luò)對(duì)矩陣積和式對(duì)數(shù)值的估值準(zhǔn)確度。關(guān)鍵詞：神經(jīng)網(wǎng)絡(luò)；積和式；HF-CNN；特

3、征-ANNAbstractAbstractWe mainly study the application of neural network algorithm on permanent estimation problem. We analyze the advantages and disadvantages of convolution neural network and artificial neural network in the estimation problem. The influence of different network structure, different

4、 training data sets and other factors on the prediction accuracy and the time complexity is well discussed. Through experiments, we show that for the 8 order to 18 order matrix, the HF-CNN structure of the ANN based on characteristics can make effective estimation on the logarithm of permanent in th

5、e case of low time complexity.We further improve the estimation accuracy of permanent by combining other algorithms.Keywords: neural network ; permanent; HF-CNN; ANN based on characteristics目錄 TOC o 1-5 h z 第一章弓I言1 HYPERLINK l bookmark26 o Current Document 第二章研究問(wèn)題與方法4 HYPERLINK l bookmark29 o Curren

6、t Document 2.1積和式的定義及其相關(guān)的矩陣結(jié)構(gòu)特征4 HYPERLINK l bookmark32 o Current Document 積和式的定義4 HYPERLINK l bookmark35 o Current Document 矩陣的結(jié)構(gòu)特征4 HYPERLINK l bookmark38 o Current Document 神經(jīng)網(wǎng)絡(luò)52.2. 1人工神經(jīng)網(wǎng)絡(luò)6卷積神經(jīng)網(wǎng)絡(luò)73CNN,全局 ANN與特征 ANN8 HYPERLINK l bookmark42 o Current Document 2.2.4神經(jīng)網(wǎng)絡(luò)算法與已有算法的比較9 HYPERLINK l book

7、mark45 o Current Document 第三章實(shí)驗(yàn)與分析11 HYPERLINK l bookmark48 o Current Document 3.1訓(xùn)練集的生成與初步分析11 HYPERLINK l bookmark51 o Current Document 3.2卷積神經(jīng)網(wǎng)絡(luò)估值效果分析20 HYPERLINK l bookmark54 o Current Document 1卷積神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)的研究20 HYPERLINK l bookmark57 o Current Document 3. 2. 2 HF-CNN在各階矩陣上的預(yù)測(cè)效果的比較23 HYPERLINK l

8、bookmark60 o Current Document 3. 2. 3 HF-CNN在不同結(jié)構(gòu)訓(xùn)練集上預(yù)測(cè)效果的比較24 HYPERLINK l bookmark67 o Current Document 3. 2. 4 HF-CNN在不同估值精度要求下預(yù)測(cè)效果的比較27 HYPERLINK l bookmark70 o Current Document 人工神經(jīng)網(wǎng)絡(luò)估值效果分析28 HYPERLINK l bookmark73 o Current Document 3. 3. 1全局ANN與特征ANN在不同階數(shù)矩陣上的預(yù)測(cè)效果28 HYPERLINK l bookmark76 o Cur

9、rent Document 3. 3. 2不同隱藏層數(shù)全局ANN和特征ANN預(yù)測(cè)效果的比較30 HYPERLINK l bookmark79 o Current Document 3. 3. 3特征ANN在不同結(jié)構(gòu)訓(xùn)練集上預(yù)測(cè)效果的比較32 HYPERLINK l bookmark84 o Current Document 3.4關(guān)于0值積和式矩陣的研究35 HYPERLINK l bookmark87 o Current Document 3.4. 1矩陣積和式值的非0判定問(wèn)題35 HYPERLINK l bookmark90 o Current Document 3.4.1 “非0矩陣”的

10、積和式估值問(wèn)題373.5小結(jié)38 HYPERLINK l bookmark93 o Current Document 第四章結(jié)論40 HYPERLINK l bookmark96 o Current Document 參考文獻(xiàn)42 HYPERLINK l bookmark110 o Current Document 致謝43 HYPERLINK l bookmark113 o Current Document 聲明44個(gè)人簡(jiǎn)歷、在學(xué)期間發(fā)表的學(xué)術(shù)論文與研究成果45第一章引言2016年谷歌AlphaGoi在圍棋領(lǐng)域戰(zhàn)勝世界頂級(jí)高手李世石，宣告了人工智 能在處理大規(guī)模復(fù)雜局面時(shí)，也可以有相當(dāng)準(zhǔn)確的

11、“判斷能力”，甚至有類似人 類的“直覺(jué)”。AlphaG。的AI系統(tǒng)中使用的卷積神經(jīng)網(wǎng)絡(luò)算法再次成為人們關(guān)注 的焦點(diǎn)。卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Networks-簡(jiǎn)稱CNN)是一種前饋式神經(jīng) 網(wǎng)絡(luò)，在圖像識(shí)別，自然語(yǔ)言處理等領(lǐng)域有非常好的應(yīng)用效果。在某種意義上，圍棋的每一個(gè)局面可以被看作是一幅圖像，19*19的棋盤對(duì)應(yīng) 19*19個(gè)像素點(diǎn)，每個(gè)像素點(diǎn)有黑子、白子、無(wú)子三種狀態(tài)。我們可以像輸入圖片 一樣輸入每一個(gè)圍棋的局面，把每個(gè)局面下最優(yōu)的應(yīng)對(duì)落子點(diǎn)作為輸出，預(yù)存充 分?jǐn)?shù)量的局面和對(duì)應(yīng)落子點(diǎn)構(gòu)成訓(xùn)練樣本集，訓(xùn)練神經(jīng)網(wǎng)絡(luò)，最終讓神經(jīng)網(wǎng)絡(luò)通 過(guò)學(xué)習(xí)“學(xué)會(huì)下棋。值得注意的

12、是，圍棋的每個(gè)局面可以類比于圖像，但與圖像還 是有很大的差別。對(duì)于圍棋而言，局部的一個(gè)微小的差別意味著局部死活的巨大 差異，甚至直接影響全局的勝負(fù)；這與大多數(shù)圖像變化一兩個(gè)像素點(diǎn)不會(huì)影響整 體表達(dá)的內(nèi)容有很大的不同。因此，卷積神經(jīng)網(wǎng)絡(luò)在圍棋人工智能上的成功應(yīng)用 是人工智能領(lǐng)域一個(gè)很大的突破，這意味著，卷積神經(jīng)網(wǎng)絡(luò)可能不僅僅在圖像識(shí) 別和自然語(yǔ)言處理領(lǐng)域十分有效，在處理類圖像問(wèn)題時(shí)，也可以有很大的發(fā)揮空 間。矩陣積和式的計(jì)算，尤其是0-1矩陣的積和式計(jì)算，也是一個(gè)類圖像問(wèn)題。它 可以被看作圖像，但相比與圖像，局部性更弱，全局的關(guān)聯(lián)更復(fù)雜，并且有一些 自身獨(dú)特的數(shù)學(xué)性質(zhì)。卷積神經(jīng)網(wǎng)絡(luò)在圍棋上的成功

13、應(yīng)用讓我想要嘗試把人工智 能算法引入矩陣積和式問(wèn)題，利用卷積神經(jīng)網(wǎng)絡(luò)或者其他的神經(jīng)網(wǎng)絡(luò)算法對(duì)矩陣 積和式值進(jìn)行估算。計(jì)算矩陣積和式的準(zhǔn)確值已被證明是一個(gè)NP-hard問(wèn)題。由于0-1矩陣的積和 式與圖論的密切關(guān)聯(lián)，人們尤其關(guān)注0-1矩陣積和式值的計(jì)算。找到一個(gè)有效的算 法計(jì)算0-1積和式對(duì)于組合數(shù)學(xué)有著重要的意義，其值的計(jì)算直接對(duì)應(yīng)了二分圖的 完美匹配計(jì)數(shù)、以及圖的圈覆蓋計(jì)數(shù)問(wèn)題。本論文中提到的矩陣積和式值的計(jì)算, 如沒(méi)有特殊說(shuō)明，都特指0-1矩陣積和式值的計(jì)算。1993年N.Karmarkar與R. Karp使用蒙特卡洛方法給出了積和式問(wèn)題一個(gè)有 效的估值算法，并對(duì)其計(jì)算精度給出了一個(gè)用概率

14、表示的估計(jì)。1998年，Isabel Beichl和Francis Sullivan通過(guò)將積和式求值轉(zhuǎn)換為圖論中的覆蓋問(wèn)題囹，對(duì)積和式 的值進(jìn)行估計(jì)。2003年，Liang H和Bai F給出了 0-1矩陣積和式上界的一類新的 估計(jì)方法t5o 2004年，Liang H和Bai F對(duì)富勒烯鄰接矩陣的積和式給出了一個(gè)快 速計(jì)算方法。2012年，Wang L, Liang H, Bai F和Huo Y給出了一個(gè)針對(duì)大規(guī)模 稀疏矩陣的積和式的快速計(jì)算方法。人們對(duì)于計(jì)算矩陣積和式值的研究主要有以下幾個(gè)方向：尋找矩陣積和式準(zhǔn) 確值的計(jì)算方法，這些精確算法的時(shí)間復(fù)雜度都是矩陣規(guī)模的指數(shù)量級(jí)；針對(duì)一 些特殊

15、的積和式尋找有針對(duì)性的算法，這類通常都要求矩陣是稀疏的；將積和式 問(wèn)題轉(zhuǎn)化為組合計(jì)數(shù)問(wèn)題求解；對(duì)積和式值的上下界進(jìn)行估計(jì)；使用蒙特卡洛方 法對(duì)積和式進(jìn)行估值，估值精度通常用概率表示。我們可以看到，想要計(jì)算積和式的準(zhǔn)確值，要么付出巨大的計(jì)算代價(jià)（指數(shù) 級(jí)的時(shí)間復(fù)雜度），要么具有較大的局限性（只能計(jì)算某一類特殊矩陣的積和式）； 如果想要快速的計(jì)算積和式的值，我們就必須以某種方式犧牲精度一一估界或者 允許誤差。使用神經(jīng)網(wǎng)絡(luò)計(jì)算積和式，就是一種估值計(jì)算方法。算法需要在一定程度上 犧牲精度，以換取在短時(shí)間內(nèi)快速對(duì)矩陣進(jìn)行估值。在有限的計(jì)算資源下，神經(jīng) 網(wǎng)絡(luò)算法可以給出在精度上不差于蒙塔卡羅方法的結(jié)果。也

16、就是說(shuō)，卷積神經(jīng)網(wǎng) 絡(luò)是蒙塔卡羅方法外，另一種估算積和式值的有效方法。必須要指出的是，積和式的精確值計(jì)算方法，以及一些矩陣積和式值上下界 的估計(jì)方法，都是確定性的算法，算法的原理和過(guò)程一般都很簡(jiǎn)明。即使是引入 隨機(jī)模擬的蒙塔卡羅方法，我們也能夠?qū)ζ湔`差值給出一個(gè)理論上的估界。相比 于這些算法，神經(jīng)網(wǎng)絡(luò)算法具有“黑箱子”的特點(diǎn)，也就是說(shuō)其內(nèi)部的計(jì)算機(jī)制 不透明，對(duì)其計(jì)算誤差的估計(jì)也主要源于實(shí)驗(yàn)數(shù)據(jù)而非理論分析。神經(jīng)網(wǎng)絡(luò)“黑 箱子”的特點(diǎn)，在我們嘗試?yán)斫馍窠?jīng)網(wǎng)絡(luò)在矩陣積和式計(jì)算上的優(yōu)勢(shì)和不足時(shí)造 成了較大的困難。我們只能更多的從實(shí)驗(yàn)和對(duì)比中理解神經(jīng)網(wǎng)絡(luò)是如何去對(duì)矩陣 的積和式進(jìn)行估值。類似于圍棋，

17、我們也可以把積和式問(wèn)題看作圖像，每一個(gè)矩陣中的每一個(gè)元 素看作為一個(gè)像素點(diǎn)，元素的值對(duì)應(yīng)像素點(diǎn)的RGB值，特別的，對(duì)于0-1矩陣， 每個(gè)元素只有0和1兩個(gè)狀態(tài)。我們知道積和式值的大小不僅與積和式中的1的 數(shù)量有關(guān)，更與1的排布方式有關(guān)（以下稱其為積和式的結(jié)構(gòu)），而卷積神經(jīng)網(wǎng) 絡(luò)己在多個(gè)領(lǐng)域被證明，它在模式識(shí)別，挖掘圖像或類圖像的內(nèi)在結(jié)構(gòu)上有著突 出的優(yōu)勢(shì)。我們有理由相信，卷積神經(jīng)網(wǎng)絡(luò)在處理矩陣積和式估值問(wèn)題時(shí)也能給 我們帶來(lái)一些啟發(fā)。在具體的處理過(guò)程中，我們可以模仿AlphaGo,把矩陣看作圖像進(jìn)行處理。同 時(shí)也要注意到，矩陣中一個(gè)局部上的細(xì)微差別同樣可能導(dǎo)致計(jì)算結(jié)果的巨大變化。 此外，積和式

18、還具有更多自身的結(jié)構(gòu)特征。例如，任意交換矩陣的兩行或兩列， 其積和式的值不變。如何處理好這些異同點(diǎn)，對(duì)相似之處融會(huì)貫通加以推廣借鑒, 對(duì)不同之處進(jìn)行有效的預(yù)處理，并且在神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)中對(duì)這些特點(diǎn)加以考 慮，將會(huì)是能否使用好神經(jīng)網(wǎng)絡(luò)解決矩陣積和式估值問(wèn)題的難點(diǎn)和重點(diǎn)。論文各章的安如下，第二章主要給出論文中常用到的名詞的定義和解釋，并 介紹人工神經(jīng)網(wǎng)絡(luò)和卷積神經(jīng)網(wǎng)絡(luò)的實(shí)現(xiàn)原理。第三章包含測(cè)試集樣本的初步分 析以及神經(jīng)網(wǎng)絡(luò)的具體實(shí)現(xiàn)、實(shí)驗(yàn)以及分析，并在章節(jié)最后對(duì)諸多實(shí)驗(yàn)的結(jié)果做 一個(gè)小結(jié)。第四章簡(jiǎn)要闡述結(jié)論，并對(duì)未來(lái)后續(xù)更深入的研究做一些展望。第二章研究問(wèn)題與方法2.1積和式的定義及其相關(guān)的矩陣

19、結(jié)構(gòu)特征2. 1. 1積和式的定義給定一個(gè)n階矩陣A = (tz,)；!.=1 ,定義矩陣A的積和式為 perm(A) = 勺% ，其中求和號(hào)、 表示對(duì)(區(qū),、)遍取1到n所(1，,，,?)v ,，2，”)有排列的乘積務(wù)*2&a,以求和。我們稱perm(A)值的大小為矩陣的積和式值。我們對(duì)“積和式”與“積和式值”不作嚴(yán)格的區(qū)分，當(dāng)我們稱“積和式”時(shí) 更強(qiáng)調(diào)表達(dá)式 Z %向2。叫；當(dāng)我們稱“積和式值”時(shí)更強(qiáng)調(diào)Perm(A)的數(shù)(4 無(wú)，”)值。對(duì)于階數(shù)較高的矩陣，其積和式值可能很大，因此我們?cè)趯?duì)其估值時(shí)，需要 對(duì)其進(jìn)行對(duì)數(shù)預(yù)處理：即對(duì)積和式值取以10為底的對(duì)數(shù)。我們稱log(perm(A)為 矩

20、陣A的“積和式對(duì)數(shù)值”。論文中，我們主要使用神經(jīng)網(wǎng)絡(luò)對(duì)矩陣得積和式對(duì) 數(shù)值進(jìn)行估計(jì)。矩陣中，每個(gè)元素都為1或0的矩陣稱為0-1矩陣。論文中，主要研究對(duì)0-1 矩陣的積和式進(jìn)行估值。若沒(méi)有特殊說(shuō)明，論文中提及的矩陣都特指0-1矩陣。利用矩陣積和式的展開式，容易證明，任意交換矩陣的兩行或兩列，矩陣的 積和式值保持不變。2. 1.2矩陣的結(jié)構(gòu)特征我們通常稱多數(shù)元素為0的矩陣為稀疏矩陣，但對(duì)于其稀疏程度，即具體0 元素占到多少比例才稱為稀疏矩陣并沒(méi)有明確的定義。對(duì)于0-1矩陣的積和式，容 易知道當(dāng)矩陣中0元素很多而1元素很少時(shí)，矩陣的積和式值大概率為0;而矩陣 中1元素很多時(shí)，矩陣的積和式值則通常很大

21、。對(duì)于給定階數(shù)的矩陣，矩陣中1 元素的比例對(duì)于矩陣積和式值的大小有很大的影響。因此在構(gòu)造算例時(shí)，我們必 須要包含各種不同稀疏度的矩陣算例。我們把矩陣中1元素的比例稱為矩陣的稀 疏度。對(duì)于不同階數(shù)的矩陣，即使它們的稀疏度，即1元素的占比相同，其表現(xiàn) 出的稀疏程度也可能有很大的區(qū)別。例如對(duì)于一個(gè)稀疏度為10%的10階矩陣，其 值大概率為0,至多為1;而對(duì)于一個(gè)稀疏度為10%的1000階矩陣，其實(shí)已經(jīng)相 當(dāng)?shù)谩俺砻堋?了。論文中，我們的研究對(duì)象主要為8-18階矩陣，矩陣階數(shù)相差不大，因此我們 簡(jiǎn)單定義1元素的比例為矩陣的稀疏度，并用它來(lái)衡量矩陣的稀疏程度相互間具 有可比性。如果在后續(xù)研究中將算法推廣

22、應(yīng)用到更高階的矩陣算例上，需要對(duì)矩 陣稀疏度重新定義。為討論方便，我們將矩陣不嚴(yán)格的分為“稀疏矩陣”，“中間狀態(tài)矩陣”和 “稠密矩陣”，區(qū)分標(biāo)準(zhǔn)綜合考慮矩陣稀疏度，以及該稀疏度下的隨機(jī)矩陣其積 和式值為0的概率?！跋∈杈仃嚒币缶仃囍?元素的個(gè)數(shù)很少，并且矩陣的積 和式值幾乎全部為0; “稠密矩陣”要求矩陣中1元素的個(gè)數(shù)很多，并且矩陣的積 和式值幾乎全部非0; “中間狀態(tài)矩陣”指矩陣中1元素個(gè)數(shù)介于稀疏與稠密之間, 并且其積和式值為0和非0的概率都不低的矩陣?！爸虚g狀態(tài)矩陣”的定義不嚴(yán) 格，主要為表述方便，這一概念在論文第三章的實(shí)驗(yàn)部分還會(huì)再次闡述。給定一個(gè)0-1矩陣K =（2.況,/=1，我

23、們定義.=an + ai2 + - + 為第i行 行和，并稱向量（a，%，兄）為矩陣A的行和向量；類似地，我們定義 Cj = *. + a2J + +粉為第j列列和，并稱向量G，6）為矩陣A的列和 向量。我們把矩陣行和向量與列和向量拼合得到的向量（化匕,R, C2, Cn） 稱為矩陣的行列和向量。給定一個(gè)0-1矩陣刃=（達(dá)若兩個(gè)不同行不同列的元素粉與也均為1， 那么我們稱元素弓,.與也構(gòu)成一個(gè)“2元組”。矩陣A中所有“2元組”的個(gè)數(shù)稱 為矩陣A的“2元組數(shù)”。類似地，我們還可以定義矩陣A的“3元組”與“3元 組數(shù)”在討論矩陣稀疏度時(shí)，我們巳經(jīng)提到，對(duì)于給定階數(shù)的矩陣，矩陣中1元素 的比例是影響

24、矩陣積和式值大小的一個(gè)重要因素。在閱讀相關(guān)文獻(xiàn)，了解前人工 作的過(guò)程中，我們發(fā)現(xiàn)矩陣的行列和向量，以及矩陣中2元組或3元組的個(gè)數(shù)也 可以幫助給出矩陣積和式值或其上下界一些更好的估計(jì)。2. 2神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)是模擬人腦或生物神經(jīng)網(wǎng)絡(luò)進(jìn)行抽象和建模，因而具有非程序的、 適應(yīng)性的、人腦風(fēng)格的信息處理的本質(zhì)和能力。神經(jīng)網(wǎng)絡(luò)以腦科學(xué)和認(rèn)知神經(jīng)科 學(xué)的研究成果為基礎(chǔ)，依托分布式并行計(jì)算強(qiáng)大的計(jì)算能力，拓展智能信息處理 的方法，為解決復(fù)雜問(wèn)題和智能控制問(wèn)題提供了新的有效途徑。2. 1人工神經(jīng)網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò)(Artificial Neural Networks,簡(jiǎn)寫為ANN)也簡(jiǎn)稱為神經(jīng)網(wǎng)絡(luò) (NN)或稱作

25、連接模型(Connection Model),它是一種模仿動(dòng)物神經(jīng)網(wǎng)絡(luò)行為特 征，進(jìn)行分布式并行信息處理的算法數(shù)學(xué)模型。Neural Network圖2.1人工神經(jīng)網(wǎng)絡(luò)示意圖(截取自MATLAB)人工神經(jīng)網(wǎng)絡(luò)兇包括輸入層，隱藏層，輸出層3個(gè)主要部分。在示意圖中，輸 入層對(duì)應(yīng)Input；隱藏層對(duì)應(yīng)Hidden Layer；輸出層對(duì)應(yīng)Output Layer以及Output。輸入層即為輸入數(shù)據(jù)，以矩陣積和式問(wèn)題為例，我們可以選擇輸入n階矩陣 的完整信息(n*n個(gè)元素值),也可以選擇輸入預(yù)處理過(guò)后的矩陣信息(例如2*n 維的矩陣行列和向量)。人工神經(jīng)網(wǎng)路把所有輸入的數(shù)據(jù)看作是若干個(gè)相互獨(dú)立 的初始信

26、息。通常，輸入層越大，ANN的網(wǎng)絡(luò)規(guī)模就越大，訓(xùn)練網(wǎng)絡(luò)需要的訓(xùn)練 樣本量就越大，訓(xùn)練時(shí)間也越長(zhǎng)。同時(shí)，輸入層越大也意味著輸入的信息越多， 如果選取的網(wǎng)絡(luò)結(jié)構(gòu)得當(dāng)，通常會(huì)得到預(yù)測(cè)能力更好的模型。隱藏層即為人工神經(jīng)網(wǎng)絡(luò)的中間層的總稱，一個(gè)人工神經(jīng)網(wǎng)絡(luò)可以有多層中 間層，每個(gè)中間層上的元素我們稱為神經(jīng)元。每一個(gè)中間層的規(guī)模都可以自己設(shè) 定，可能大于、等于或小于輸入層的規(guī)模。每一個(gè)中間層與上一中間層進(jìn)行連接, 第一個(gè)中間層與輸入層進(jìn)行連接，連接的方式都是一組權(quán)值向量W和一個(gè)激發(fā)函 數(shù)F。我們對(duì)上一層的全部神經(jīng)元做一個(gè)權(quán)值為W1的線性加權(quán)求和，然后用激發(fā) 函數(shù)F作用，得到一個(gè)輸出信號(hào)存入下一層的一個(gè)神經(jīng)

27、元內(nèi)；再選擇另一個(gè)不同 的權(quán)值W2對(duì)上一層的全部神經(jīng)元進(jìn)行線性加權(quán)求和，然后用同一個(gè)激發(fā)函數(shù)F 作用，得到的輸出信號(hào)存入下一層的下一個(gè)神經(jīng)元內(nèi)，如此重復(fù)，把上一層的信 號(hào)經(jīng)過(guò)權(quán)值為Wl, W2,Ws和同一激發(fā)函數(shù)F的作用后存入下一層的神經(jīng)元 內(nèi)。激發(fā)函數(shù)F可選為階段函數(shù)，線性函數(shù)或Sigmoid函數(shù)f(x) = 1/(1 + #x) 等。人工神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)在進(jìn)行網(wǎng)絡(luò)的訓(xùn)練前就已完全確定，我們輸入訓(xùn)練 集中的樣本對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，實(shí)際上就是去確定網(wǎng)絡(luò)中每一隱藏層的權(quán)值參 數(shù)W。訓(xùn)練機(jī)制是誤差反向傳播算法（以下簡(jiǎn)稱BP過(guò)程）。算法先對(duì)W隨機(jī)初 始化，輸入一組訓(xùn)練樣本（可以是單一樣本，全體樣本

28、，或部分抽樣樣本），輸 出在當(dāng)前權(quán)值參數(shù)W下，網(wǎng)絡(luò)的預(yù)測(cè)結(jié)果，將預(yù)測(cè)結(jié)果與真值相比較，并將誤差 從輸出層起，逐層反向傳導(dǎo)修改各個(gè)隱藏層的權(quán)值參數(shù)W,如此多次循環(huán)重復(fù)， 直到循環(huán)次數(shù)達(dá)到初始設(shè)定次數(shù)或者輸出的預(yù)測(cè)值與真值之間誤差滿足算法的收 斂停止條件。通常來(lái)說(shuō)，人工神經(jīng)網(wǎng)絡(luò)單層的規(guī)模越大，層數(shù)越多，循環(huán)次數(shù)要求或收斂 停止條件越高，網(wǎng)絡(luò)的訓(xùn)練時(shí)間就越長(zhǎng)。2. 2. 2卷積神經(jīng)網(wǎng)絡(luò)卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Networks,簡(jiǎn)寫為CNN）,它是人工神 經(jīng)網(wǎng)絡(luò)的一種變型，在圖像處理，人臉識(shí)別，語(yǔ)音識(shí)別問(wèn)題上十分有效。卷積神經(jīng)網(wǎng)絡(luò)1。與人工神經(jīng)網(wǎng)絡(luò)的在整體框架上相同，也

29、包含輸入層，隱藏 層，輸出層3個(gè)主要部分。在示意圖中，輸入層對(duì)應(yīng)Input；隱藏層包含Cl、S2、 C3、S4、以及NN；輸出層即為NN的最終輸出結(jié)果。輸入層仍為輸入數(shù)據(jù)。不同于ANN中將輸入數(shù)據(jù)看作是相互獨(dú)立信息，CNN 把輸入數(shù)據(jù)看作是一幅圖像，輸入數(shù)據(jù)之間存在相互位置關(guān)系。在矩陣積和式對(duì) 數(shù)值問(wèn)題中，輸入數(shù)據(jù)就為整個(gè)矩陣。隱藏層包含卷積層，池化層和單層神經(jīng)網(wǎng)絡(luò)。它們按示意圖中所示排列，卷 積層C1,池化層S2,卷積層C3,池化層S4, ,單層神經(jīng)網(wǎng)絡(luò)NN。隱藏層 中可以包含多組卷積層+池化層。卷積層，也稱為特征提取層，通常用C表示。特征提取層上的每個(gè)神經(jīng)元的 輸入與前一層的局部感受野相連

30、，并提取該局部的特征，即我們會(huì)選定一個(gè)面積 小于前一層總面積的特征提取框，對(duì)框中前一層的信息做一個(gè)權(quán)值為W的線性加 權(quán)，然后用激發(fā)函數(shù)F作用，得到一個(gè)輸出信號(hào)存入C層的一個(gè)神經(jīng)元內(nèi)。我們 用特征提取框依次掃過(guò)前一層的所有神經(jīng)元，并將經(jīng)過(guò)W和F作用后的結(jié)果依次 對(duì)應(yīng)存入C層。不同于ANN中，每一次作用可以選取不同的W, CNN要求同一 層使用同一權(quán)值W。池化層，通常用S表示。卷積神經(jīng)網(wǎng)絡(luò)中的每一個(gè)特征提取層（C-層）都緊 跟著一個(gè)用來(lái)求局部平均與二次提取的計(jì)算層（S-層），這種特有的兩次特征提取 結(jié)構(gòu)使網(wǎng)絡(luò)在識(shí)別時(shí)對(duì)輸入樣本有較高的畸變?nèi)萑棠芰?。單層神?jīng)網(wǎng)絡(luò)，通常用NN或BP表示。輸入信號(hào)在經(jīng)過(guò)

31、若干卷積層和池化層 處理后，得到一組規(guī)模遠(yuǎn)小于初始輸入規(guī)模的輸出，我們對(duì)這組輸出信號(hào)構(gòu)建一 個(gè)單層的神經(jīng)網(wǎng)絡(luò)，即選取一組權(quán)值參數(shù)W進(jìn)行加權(quán)求和，再用激發(fā)函數(shù)F作用， 得到最終的輸出結(jié)果。卷積神經(jīng)網(wǎng)絡(luò)具有參數(shù)共享的特點(diǎn)。一個(gè)映射面上的神經(jīng)元共享權(quán)值，因而 減少了網(wǎng)絡(luò)自由參數(shù)的個(gè)數(shù)，降低了網(wǎng)絡(luò)參數(shù)選擇的復(fù)雜度。卷積神經(jīng)網(wǎng)絡(luò)的網(wǎng) 絡(luò)結(jié)構(gòu)也在進(jìn)行網(wǎng)絡(luò)的訓(xùn)練前就巳完全確定，我們同樣通過(guò)BP過(guò)程訓(xùn)練網(wǎng)絡(luò)中的 權(quán)值參數(shù)Wo2. 2. 3 CNN,全局ANN與特征ANN在使用ANN時(shí)，我們可以選擇輸入層輸入的數(shù)據(jù)，隱藏層的層數(shù)，以及隱藏 層每一層的規(guī)模。通常，隱藏層數(shù)的多少與輸入層的規(guī)模有關(guān)，隱藏層每一層的

32、規(guī)模逐層遞減，具體的選取依賴于實(shí)驗(yàn)和經(jīng)驗(yàn)。對(duì)于輸入數(shù)據(jù)的選擇，則更多的 可以基于我們對(duì)于矩陣積和式對(duì)數(shù)值問(wèn)題的一些先驗(yàn)的理解。如果選取輸入數(shù)據(jù)為n階矩陣的完整信息，那么輸入數(shù)據(jù)就完全不包含先驗(yàn) 知識(shí)，我們希望這一不包含先驗(yàn)知識(shí)的ANN通過(guò)對(duì)訓(xùn)練樣本的學(xué)習(xí)能夠自己發(fā)現(xiàn) 矩陣特征與矩陣積和式對(duì)數(shù)值之間的內(nèi)在聯(lián)系，并最終在測(cè)試集上對(duì)矩陣積和式 對(duì)數(shù)值做出正確的預(yù)測(cè)。如果選取預(yù)處理后的數(shù)據(jù)，例如矩陣的行列和向量，作為輸入數(shù)據(jù)，那么輸 入數(shù)據(jù)中就包含了我們的先驗(yàn)知識(shí)。這一方法在損失一定量的信息的同時(shí)，簡(jiǎn)化 了網(wǎng)絡(luò)結(jié)構(gòu)。如果預(yù)處理的方式得當(dāng)，那么就有可能在減少訓(xùn)練的時(shí)間的情況下 得到不差于完整信息輸入，甚

33、至更優(yōu)于完整信息輸入得到的結(jié)果；反之，如果我 們的預(yù)處理是不合理的，損失了重要信息，那么就會(huì)導(dǎo)致神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)失效。對(duì)于矩陣積和式估值問(wèn)題，如果我們把人工神經(jīng)網(wǎng)絡(luò)ANN的輸入數(shù)據(jù)選為全 矩陣（n*n個(gè)數(shù)據(jù)），則我們稱其為“全局ANN” ；如果把ANN的輸入數(shù)據(jù)選為 矩陣的行列和向量（n*2個(gè)數(shù)據(jù)）,則我們稱其為“特征ANN” o在使用CNN時(shí)，我們有更大的空間去選擇網(wǎng)絡(luò)結(jié)構(gòu)：包括網(wǎng)絡(luò)的層數(shù)，每一 層提取面積的大小，提取特征的數(shù)量，以及是否引入池化處理等。從訓(xùn)練時(shí)間的 角度來(lái)看，網(wǎng)絡(luò)層數(shù)的增加，每一層提取面積的增大，提取特征數(shù)量的增加會(huì)增 大訓(xùn)練網(wǎng)絡(luò)的時(shí)間復(fù)雜度；而引入池化處理則會(huì)減少訓(xùn)練所需的時(shí)

34、間。從網(wǎng)絡(luò)的 預(yù)測(cè)能力上看，對(duì)于圖像識(shí)別問(wèn)題，較高（但不能過(guò)高）的網(wǎng)絡(luò)層數(shù)，適合的提 取面積大小，足夠的提取特征數(shù)量通常能得到具有較好識(shí)別能力的CNNo但對(duì)于 矩陣積和式對(duì)數(shù)值問(wèn)題，不完全如此，具體的差異在論文的實(shí)驗(yàn)部分會(huì)有比較分 析。特征ANN在一定程度上可以被看作是CNN的另一種形式。在矩陣積和式對(duì) 數(shù)值問(wèn)題中，CNN將矩陣看作是圖像，對(duì)一個(gè)n*n的矩陣，以矩形的特征提取框 的方式提取矩陣局部特征進(jìn)行學(xué)習(xí)；而特征ANN則是分行分列地看待矩陣，對(duì)一 個(gè)n*n矩陣，先按行按列提取特征（提取方式為簡(jiǎn)單的加和），再對(duì)初步提取特 征后的行列和向量做進(jìn)一步的學(xué)習(xí)。相比于全局ANN,特征ANN和CNN都

35、引入 了對(duì)初始數(shù)據(jù)的預(yù)處理，加入了對(duì)于矩陣積和式對(duì)數(shù)值問(wèn)題的一些先驗(yàn)的理解。CNN,全局ANN與特征ANN三類網(wǎng)絡(luò)結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)算法在處理同一矩陣 階數(shù)的矩陣積和式對(duì)數(shù)值問(wèn)題時(shí)，由于其各自適合的網(wǎng)絡(luò)層數(shù)等設(shè)置不盡相同， 時(shí)間復(fù)雜度不能直接比較。但可以肯定的是，全局ANN的計(jì)算代價(jià)一定最大，且 明顯高于特征ANN和CNN,其時(shí)間復(fù)雜度隨矩陣階數(shù)的增加快速增長(zhǎng)，難以處 理較高階矩陣的積和式估值問(wèn)題。在論文中，我們主要把全局ANN用作特征ANN 和CNN在預(yù)測(cè)能力上的一個(gè)對(duì)比。2.2.4神經(jīng)網(wǎng)絡(luò)算法與已有算法的比較積和式的精確值計(jì)算方法，以及一些積和式值上下界的估計(jì)方法，都是確定 性的算法，是基于矩

36、陣一些數(shù)學(xué)性質(zhì)，推演優(yōu)化后形成的算法；引入隨機(jī)模擬的 蒙塔卡羅方法，是基于對(duì)矩陣行列式值與積和式值在期望意義下的等量關(guān)系，優(yōu) 化后隨機(jī)方法后得到的估值算法。這兩類算法都有明確的矩陣積和式數(shù)學(xué)性質(zhì)作 為支撐，以及對(duì)誤差大小或計(jì)算的時(shí)間復(fù)雜度有明確的估計(jì)。神經(jīng)網(wǎng)絡(luò)算法與這些精確值算法或者隨機(jī)模擬算法有很大的不同。我們?cè)谑?用神經(jīng)網(wǎng)絡(luò)對(duì)矩陣積和式對(duì)數(shù)值進(jìn)行估計(jì)時(shí)，是在嘗試選取一個(gè)比較合理的網(wǎng)絡(luò) 結(jié)構(gòu)，以及給出具有代表性的算例樣本，希望神經(jīng)網(wǎng)絡(luò)能夠通過(guò)自己對(duì)于算例樣 本的學(xué)習(xí)，得到一組參數(shù)，最終在測(cè)試算例上對(duì)矩陣積和式對(duì)數(shù)值給出較為準(zhǔn)確 的預(yù)測(cè)?？梢哉f(shuō)，精確算法和隨機(jī)模擬算法都是基于已有的對(duì)于矩陣積和

37、式性質(zhì)的結(jié) 論提出的算法；而神經(jīng)網(wǎng)絡(luò)算法則是不以已知的矩陣積和式性質(zhì)或相關(guān)定理為基 礎(chǔ)，相反，是通過(guò)學(xué)習(xí)過(guò)程本身去發(fā)現(xiàn)矩陣的特征與其積和式對(duì)數(shù)值之間的關(guān)聯(lián)。我們對(duì)于矩陣積和式的一些先驗(yàn)的知識(shí)不能直接影響于最終的神經(jīng)網(wǎng)絡(luò)，但 可以幫助我們更好地選擇更適合矩陣積和式問(wèn)題的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，以及選取更具 有代表性的矩陣算例作為輸入樣本。第三章實(shí)驗(yàn)與分析3. 1訓(xùn)練集的生成與初步分析論文中，我們選擇使用有積和式精確值計(jì)算結(jié)果的矩陣作為神經(jīng)網(wǎng)絡(luò)的訓(xùn)練 和測(cè)試樣本。實(shí)驗(yàn)中使用的樣本均用矩陣積和式值的一個(gè)精確算法Npermii在 MATLAB 計(jì)算生成。Nperm是一個(gè)關(guān)于矩陣階數(shù)n的指數(shù)時(shí)間復(fù)雜度算法，因 此

38、我們只能用其計(jì)算20階以下矩陣的積和式值。受限于生成樣本在時(shí)間復(fù)雜度上 的困難，論文中對(duì)于用神經(jīng)網(wǎng)絡(luò)給矩陣積和式估值的研究主要針對(duì)8-18階矩陣。矩陣的積和式具有交換任意兩行或兩列，其值保持不變的特點(diǎn)，而對(duì)于神經(jīng) 網(wǎng)絡(luò)而言，不論是把矩陣作為圖像處理的CNN,是把矩陣每個(gè)位置元素獨(dú)立看待 的全局ANN,還是取用矩陣行列和向量來(lái)進(jìn)行學(xué)習(xí)的特征ANN,都是不具有任意 交換兩行或兩列，預(yù)測(cè)值保持不變這一性質(zhì)的。因此，在將矩陣放入神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練學(xué)習(xí)之前，我們需要對(duì)矩陣進(jìn)行“去 可交換性”的預(yù)處理。對(duì)矩陣的“去可交換性”預(yù)處理方法有3種，左上角方法，居中方法和旋轉(zhuǎn) 翻倍方法三種。左上角法。先對(duì)矩陣進(jìn)行列

39、的交換，使得1較多的列靠左；再對(duì)矩陣進(jìn)行行 的交換，使得1較多的行靠上。最終得到的矩陣，其行和向量和列和向量的分量 的值都為從大到小順序排列。矩陣中的1元素相對(duì)集中在矩陣的左上角。居中方法。與左上角法類似，先對(duì)矩陣進(jìn)行列的交換，使得1較多的居中； 再對(duì)矩陣進(jìn)行行的交換，使得1較多的也居中。最終矩陣中的1元素相對(duì)集中在 矩陣中央。旋轉(zhuǎn)翻倍方法。先將矩陣按左上角法變換，然后將矩陣依次逆時(shí)針旋轉(zhuǎn)90度 得到4個(gè)等價(jià)矩陣，最后按旋轉(zhuǎn)時(shí)的相對(duì)位置拼合成一個(gè)4倍于初始矩陣規(guī)模的 大矩陣。大矩陣與原始矩陣在積和式值上并沒(méi)有直接的關(guān)聯(lián)，但在矩陣的結(jié)構(gòu)上 有很強(qiáng)的聯(lián)系。在的神經(jīng)網(wǎng)絡(luò)訓(xùn)練中，我們將變換后的大矩陣作

40、為輸入，變換前 的原始矩陣的積和式對(duì)數(shù)值作為輸出，進(jìn)行訓(xùn)練。三種預(yù)處理方法都有一個(gè)共同點(diǎn)，即使得本質(zhì)上相同（即可以通過(guò)交換行或 列變?yōu)橄嗤┑木仃?，在預(yù)處理后能得到同樣的矩陣表示。這一點(diǎn)對(duì)于不具備行 列可交換性的神經(jīng)網(wǎng)絡(luò)是十分重要的。對(duì)于全局ANN （輸入數(shù)據(jù)為全矩陣）和特征ANN （輸入數(shù)據(jù)為矩陣的行列和 向量）而言，三種預(yù)處理方法是基本等價(jià)的。其中，旋轉(zhuǎn)翻倍法擴(kuò)大了輸入的規(guī) 模，在不提高預(yù)測(cè)效果的情況下，額外增加了訓(xùn)練網(wǎng)絡(luò)的時(shí)間復(fù)雜度，因此不可 取。對(duì)于ANN有關(guān)的實(shí)驗(yàn)，我們統(tǒng)一選用左上角預(yù)處理法。對(duì)于CNN而言，三種預(yù)處理方法是有區(qū)別的。我們知道，CNN是一個(gè)在處 理圖像識(shí)別問(wèn)題上十分有

41、效的算法。因此，我們?cè)陬A(yù)處理的過(guò)程中，一方面要考 慮將等價(jià)矩陣唯一確定；另一方面也要考慮對(duì)矩陣進(jìn)行“圖像化”，即增加矩陣 的“圖像性”。CNN的網(wǎng)絡(luò)結(jié)構(gòu)決定了它在處理圖像的過(guò)程中會(huì)更重視中間部分, 給予中央部分的信息以更大的權(quán)重。也就是說(shuō)，CNN在處理矩陣數(shù)據(jù)時(shí)，會(huì)對(duì)中 間部分的數(shù)據(jù)和邊緣部分的數(shù)據(jù)區(qū)別對(duì)待，而不會(huì)對(duì)左上還是右下的數(shù)據(jù)有所區(qū) 別。因此，將1集中到矩陣中間的居中方法就優(yōu)于將1集中到左上角的左上角法。 旋轉(zhuǎn)翻倍方法在“圖像性”方面與居中方法有些類似，但旋轉(zhuǎn)翻倍法更有利于放 大矩陣行列之間的聯(lián)系，也是一個(gè)可以在CNN上嘗試的預(yù)處理方法。對(duì)于CNN 有關(guān)的實(shí)驗(yàn)，我們統(tǒng)一選用居中方法（旋

42、轉(zhuǎn)翻倍法留待后續(xù)研究）。在生成樣本時(shí)，還要考慮樣本包含各種稀疏度的矩陣，從而有足夠的代表性。 試驗(yàn)中我們隨機(jī)生成稀疏度為10%, 20%, ,90%的矩陣各10000個(gè)，共90000 個(gè)矩陣作為訓(xùn)練樣本（以下也稱其為訓(xùn)練集）；隨機(jī)生成稀疏度為10%, 20%, , 90%的矩陣各1000個(gè)，共9000個(gè)矩陣作為測(cè)試樣本（以下也稱其為測(cè)試集）。表3. 1矩陣樣本的基本數(shù)據(jù)矩陣階數(shù)訓(xùn)練集規(guī)模測(cè)試集規(guī)模矩陣稀疏度最大積和式值0值矩陣數(shù)生成時(shí)間810000*91000*910%-90%4. 0320e+430072. 3365e+21010000*91000*910%-90%3. 2659e+6258

43、95. 4272e+21210000*91000*910%-90%3. 6977e+822902. 1407e+31410000*91000*910%-90%5. 5915e+1020208. 4455e+31610000*91000*910%-90%1.2417e+1317573. 3553e+41810000*91000*910%-90%2. 7057e+1516271. 3093e+5*矩陣中“0值矩陣數(shù)”特指測(cè)試集中積和式值為0的矩陣占比。*矩陣中“最大積和式值”為訓(xùn)練集和測(cè)試集中所有矩陣積和式值的最大值。* “生成時(shí)間”為生成訓(xùn)練集與測(cè)試集矩陣樣本的總時(shí)間，由MATLAB的 tic+

44、toc指令得到。首先觀察測(cè)試集中矩陣樣本的積和式對(duì)數(shù)值分布情況。以下是各階矩陣積和 式對(duì)數(shù)值分布圖。圖中，橫坐標(biāo)為測(cè)試集樣本編號(hào)，縱坐標(biāo)為矩陣積和式對(duì)數(shù)值。 由于樣本按稀疏度由小到大排序，每1000個(gè)樣本增大10%,因此隨樣本編號(hào)增大,矩陣中1的比例增大，并且每1000個(gè)樣本之間1的比例相近。8階矩陣測(cè)試集積和式對(duì)數(shù)值分布圖圖3.18階矩陣測(cè)試集積和式對(duì)數(shù)值分布圖5 6 4 5 3 4.3.52.51.5O2 LO-10階指降測(cè)試集積和式對(duì)數(shù)值分布圖1000 20003000 40005000 6000 7000 80009000樣本編號(hào)7 6 54 3 2 S新校牝曷?lián)魣D3.2 10階矩陣測(cè)

45、試集積和式對(duì)數(shù)值分布圖12階矩陣測(cè)試集積和式對(duì)數(shù)值分布圖樣本福號(hào)圖3.3 12階矩陣測(cè)試集積和式對(duì)數(shù)值分布圖14階矩陣測(cè)試集積和式對(duì)數(shù)值分布圖1000 20003000 400050006000700080009000樣本編號(hào)0 8 6 42圖3.4 14階矩陣測(cè)試集積和式對(duì)數(shù)值分布圖皿二痂校施必S5圖3.516階矩陣測(cè)試集積和式對(duì)數(shù)值分布圖圖3.618階矩陣測(cè)試集積和式對(duì)數(shù)值分布圖恭長(zhǎng)協(xié)忠曉64 2 086420可以看到，稀疏矩陣的積和式對(duì)數(shù)值基本為0。對(duì)于稠密矩陣的積和式對(duì)數(shù)值 與矩陣稠密程度（1的比例）有較大的相關(guān)性。對(duì)于8-18階矩陣，其積和式對(duì)數(shù)值的分布圖大體相似，但仍有區(qū)別。我們可

46、 以看到，對(duì)于8階矩陣，0值矩陣數(shù)有3007個(gè)，而隨著矩陣階數(shù)的上升，。值矩 陣數(shù)逐漸減少，18階矩陣的0值矩陣數(shù)只有1627個(gè)。并且在。值矩陣的分布上， 對(duì)于8階矩陣，70%稀疏度的矩陣中，仍有矩陣的積和式值為0,；而對(duì)于18階矩 陣，40%以上稀疏度矩陣的積和式己經(jīng)基本非0。另一方面，對(duì)于8階矩陣，20% 以下稀疏度的矩陣大多積和式值為0;而對(duì)于18階矩陣，直到10%以下稀疏度的 矩陣，其積和式值才基本為0。這一觀察與我們?cè)诰仃囅∈瓒戎兴懻摰南嘁恢拢?矩陣稀疏程度對(duì)于不同階數(shù)的矩陣而言，即使是同一百分比，其表現(xiàn)出的稀疏程 度也有區(qū)別。在本論文中，對(duì)某一給定的矩陣階數(shù)，我們把積和式值基本為

47、0的稀疏度的 矩陣稱為“稀疏矩陣”，把積和式值基本不為0的稀疏度的矩陣稱為“稠密矩陣”， 把積和式的值為。和非。的都占一定比例的稀疏度的矩陣稱為“中間狀態(tài)矩陣”。我們約定：對(duì)于8階矩陣而言，10%-20%為稀疏，30%-60%為中間狀態(tài)，70%-90%為稠 密。對(duì)于12階矩陣而言，10%為稀疏，20%-40%為中間狀態(tài)，50%-90%為稠密。對(duì)于18階矩陣而言，10%為稀疏，20%-30%為中間狀態(tài)，40%-90%為稠密。在對(duì)樣本的初步分析中，我們發(fā)現(xiàn)，矩陣積和式對(duì)數(shù)值的大小與矩陣稀疏度 具有相關(guān)性。因此我們可以考慮將矩陣稀疏度作為一個(gè)估計(jì)量對(duì)積和式的對(duì)數(shù)值 做估計(jì)。這是一個(gè)十分粗檢的估計(jì)方法

48、，我們可以將這一估計(jì)方法的預(yù)測(cè)結(jié)果作 為論文中后續(xù)的CNN或ANN估計(jì)方法的比對(duì)基礎(chǔ)。使用矩陣稀疏度（即矩陣中1的個(gè)數(shù)）單變量的預(yù)測(cè)效果（以18階矩陣為例）:表3. 2元回歸模型預(yù)測(cè)情況簡(jiǎn)表矩陣階數(shù)估值方法準(zhǔn)確預(yù)測(cè)正確預(yù)測(cè)整體偏差值訓(xùn)練時(shí)間/s18稀疏度單變量回歸293975133686 4 2 0 8 6圖3.7測(cè)試集矩陣積和式對(duì)數(shù)值真值圖18階拒陣測(cè)試集積和式對(duì)數(shù)值一元回歸預(yù)測(cè)值1000 20004000樣本編號(hào)測(cè)試集矩陣積和式對(duì)數(shù)值預(yù)測(cè)值2108 6 42 O圖3.8k rr.弟二早圖3.8眥琳型菰技KS變18階拒陣測(cè)試集積和式一元回歸預(yù)測(cè)誤差1000 20003000 40005000

49、6000700080009000樣本編號(hào)測(cè)試集矩陣積和式對(duì)數(shù)值預(yù)測(cè)誤差圖從實(shí)驗(yàn)結(jié)果中可以看到，對(duì)矩陣稀疏度因子（即矩陣中1的個(gè)數(shù)）做線性回 歸，可以對(duì)矩陣積和式的對(duì)數(shù)值有一個(gè)比較模糊的預(yù)測(cè)效力，預(yù)測(cè)結(jié)果在矩陣稀 疏度介于稀疏與稠密之間，也即在該稀疏度下，矩陣的積和式值部分為0、部分非 0時(shí)（以下簡(jiǎn)稱為“中間狀態(tài)”），單元回歸方法的預(yù)測(cè)效力尤為糟糕。此外，單 元回歸方法在各個(gè)稀疏度的樣本上會(huì)表現(xiàn)出對(duì)該類樣本估值整體有偏。我們考慮在矩陣稀疏度的基礎(chǔ)上再引入一個(gè)能夠在一定程度上刻畫矩陣內(nèi)在 結(jié)構(gòu)的因子，建立一個(gè)二元回歸模型，希望模型在預(yù)測(cè)準(zhǔn)確度有所提高，并能在 一定程度上改進(jìn)一元模型對(duì)不同稀疏度矩陣

50、的估值整體有偏這一缺陷。以下我們引入矩陣積和式對(duì)數(shù)值對(duì)“矩陣稀疏度+2元組數(shù)”的二元回歸模型 （以18階矩陣為例）。表3. 3二元回歸模型預(yù)測(cè)情況簡(jiǎn)表矩陣階數(shù)估值方法準(zhǔn)確預(yù)測(cè)正確預(yù)測(cè)整體偏差值訓(xùn)練時(shí)間/s18稀疏度+2元組數(shù)雙 變量回歸19779800.8453218階矩陣測(cè)試集積和式對(duì)數(shù)值分布圓1000 2000 3000 4000 5000 6000 7000 8000 9000樣本編號(hào)圖3.9測(cè)試集矩陣積和式對(duì)數(shù)值真值圖18階布陣測(cè)試集積和式對(duì)數(shù)值一元回歸項(xiàng)測(cè)值40005000樣本編號(hào)測(cè)試集矩陣積和式對(duì)數(shù)值預(yù)測(cè)值利唯地蒸灰蒞是壬18階矩陣測(cè)試集積和式一元回歸預(yù)測(cè)誤差40005000樣本編

51、號(hào)圖3.11測(cè)試集矩陣積和式對(duì)數(shù)值預(yù)測(cè)誤差圖從實(shí)驗(yàn)結(jié)果中可以看到，在回歸方程中添加“2元組”因子，即將矩陣積和式 對(duì)數(shù)值對(duì)矩陣稀疏度和2元組個(gè)數(shù)做二元線性回歸，得到的回歸模型對(duì)于矩陣積 和式對(duì)數(shù)值的預(yù)測(cè)效力有明顯的提升。不僅正確率有很大的提高，預(yù)測(cè)值在各個(gè) 稀疏度的樣本上的有偏現(xiàn)象也得到了較大的改善。但回歸模型在預(yù)測(cè)處于“中間 狀態(tài)”矩陣的積和式對(duì)數(shù)值時(shí)，預(yù)測(cè)效力仍然不好。3.2卷積神經(jīng)網(wǎng)絡(luò)估值效果分析我們首先討論卷積神經(jīng)網(wǎng)絡(luò)在矩陣積和式值估計(jì)問(wèn)題上的表現(xiàn)。卷積神經(jīng)網(wǎng)絡(luò)的基本網(wǎng)絡(luò)結(jié)構(gòu)和原理在第二章中已經(jīng)說(shuō)明。我們?cè)贛ATLAB 上實(shí)現(xiàn)算法，并進(jìn)行相關(guān)的實(shí)驗(yàn)和分析研究。我們用“ 3c-2s-5c

52、-3s-5c-ls-BP ”的形式來(lái)表述卷積網(wǎng)絡(luò)的結(jié)構(gòu)?！?c-2s-5c-3s-5c-ls-BP”即表示我們對(duì)輸入層數(shù)據(jù)先做一個(gè)特征提取框?yàn)?*3 的卷積層，再做一個(gè)池化面積為2*2的池化層；接著做一個(gè)特征提取框?yàn)?*5的 卷積層，再做一個(gè)池化面積為3*3的池化層；然后做一個(gè)特征提取框?yàn)?*5的卷 積層，再做一個(gè)池化面積為1*1的池化層（相當(dāng)于不進(jìn)行池化處理）；最后將處 理到這一步的數(shù)據(jù)展開，做一個(gè)單層的人工神經(jīng)網(wǎng)絡(luò)NN,輸出最終結(jié)果。3. 2. 1卷積神經(jīng)網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)的研究在實(shí)驗(yàn)過(guò)程中，我們先主要對(duì)8階、12階和18階矩陣進(jìn)行研究。對(duì)于同一階數(shù)的矩陣，用來(lái)估計(jì)其積和式值的量級(jí)的可選CNN結(jié)

53、構(gòu)有很多， 區(qū)別主要在3個(gè)方面：每一卷積層卷積面積的選擇、每一池化層是否池化層以及 如何池化、卷積神經(jīng)網(wǎng)絡(luò)的層數(shù)。我們?cè)?階、12階和18階矩陣的樣本集上做了大量嘗試。部分網(wǎng)絡(luò)結(jié)構(gòu)在8、 12、18階矩陣上的實(shí)驗(yàn)數(shù)據(jù)如下：表3. 4 8階矩陣上不同網(wǎng)絡(luò)結(jié)構(gòu)CNN的表現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)準(zhǔn)確預(yù)測(cè)偏大一量級(jí)偏小一量級(jí)預(yù)測(cè)錯(cuò)誤訓(xùn)練時(shí)間/SHF-CNN(4c-is-BP)7948410504138245.433c-ls-BP7964496375165586.745c-ls-BP79293795441481163.306c-ls-BP7997520311172829.625c-2s-BP7767416613204

54、313.933c-2s-BP7783544456217326.283c-ls-3c-ls-BP80033465481033169.794c-ls-3c-ls-BP8074420396110602.05* “準(zhǔn)確預(yù)測(cè)”表示預(yù)測(cè)結(jié)果與真實(shí)值在同一數(shù)量級(jí)。* “偏大一量級(jí)”表示預(yù)測(cè)結(jié)果相比于真實(shí)值偏大1個(gè)數(shù)量級(jí)。* “偏小一量級(jí)”表示預(yù)測(cè)結(jié)果相比與真實(shí)值偏小1個(gè)數(shù)量級(jí)。* “預(yù)測(cè)錯(cuò)誤”表示預(yù)測(cè)結(jié)果相比于真實(shí)值偏差超過(guò)1個(gè)數(shù)量級(jí)。* “訓(xùn)練時(shí)間”由MATLAB中tic+toc指令得到，可能存在一定的偏差。表3. 5 12階矩陣上不同網(wǎng)絡(luò)結(jié)構(gòu)CNN的表現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)準(zhǔn)確預(yù)測(cè)偏大一量級(jí)偏小一量級(jí)預(yù)測(cè)錯(cuò)誤訓(xùn)練時(shí)

55、間/SHF-CNN(6c-ls-BP)7582540571307423.103c-ls-BP7369732580319613.395c-ls-BP7720571392317660.337c-ls-BP7510475734281490.268c-ls-BP7704600427269428.913c-2s-BP7414832357397527.185c-2s-BP7465646558331345.797c-2s-BP7345834430391341.186c-ls-3c-ls-BP7673548505274973.516c-ls-4c-ls-BP7564378809249960.65表3. 6 1

56、8階矩陣上不同網(wǎng)絡(luò)結(jié)構(gòu)CNN的表現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)準(zhǔn)確預(yù)測(cè)偏大一量級(jí)偏小一量級(jí)預(yù)測(cè)錯(cuò)誤訓(xùn)練時(shí)間/SHF-CNN(9c-ls-BP)6915994610481691.567c-ls-BP493580428629751012.878c-ls-BP52006718772252985.23lOc-ls-BP682511786103872915.61llc-ls-BP6926943778353797.9112c-ls-BP70188567853412704.047c-2s-BP68956979204881420.919c-2s-BP682810226385121558.11llc-2s-BP6876626999

57、499565.8713c-2s-BP65141242755489567.899c-ls-5c-ls-BP663556912835132177.969c-ls-6c-ls-BP672012415305092392.0910c-ls-5c-ls-BP646315595704081416.929c-1 s-5c-1 s-3c-1 s-BP664970711494955901.83我們首先比較不引入池化處理的單卷積層CNN,即“Nc-ls-BP”型網(wǎng)絡(luò)?？梢?看出，面積過(guò)小的特征提取框會(huì)導(dǎo)致神經(jīng)網(wǎng)絡(luò)對(duì)矩陣積和式對(duì)數(shù)值的預(yù)測(cè)能力較 差。實(shí)驗(yàn)表明，設(shè)置首個(gè)卷積層的特征提取邊長(zhǎng)不小于矩陣階數(shù)的一半是一個(gè)比

58、較好的選擇。再分析引入池化處理的單卷積層CNN,即“Nc-2s-BP”型網(wǎng)絡(luò)。對(duì)比不引入池 化處理的CNN,引入池化處理通常降低了網(wǎng)絡(luò)訓(xùn)練所需的時(shí)間，但對(duì)于網(wǎng)絡(luò)的預(yù) 測(cè)能力基本沒(méi)有太大的影響，在部分結(jié)構(gòu)上有所提升，在部分結(jié)構(gòu)上有所下降。最后分析多卷積層的CNN,即“Nc-ls-Mc-ls-BP”型網(wǎng)絡(luò)。可以看到，網(wǎng)絡(luò) 層數(shù)的增加，對(duì)于CNN的預(yù)測(cè)能力沒(méi)有明顯的改變，但會(huì)在一定程度上增加網(wǎng)絡(luò) 訓(xùn)練所需的時(shí)間。預(yù)測(cè)準(zhǔn)確度上，單層的卷積神經(jīng)網(wǎng)絡(luò)己經(jīng)對(duì)矩陣積和式對(duì)數(shù)值有比較好的預(yù) 測(cè)效果，增加網(wǎng)絡(luò)層數(shù)并不能使預(yù)測(cè)效果有明顯的提高。需要注意的是，特征提 取框的規(guī)模不能設(shè)置過(guò)小，通常需要超過(guò)原矩陣面積的1

59、/4。對(duì)于部分結(jié)構(gòu)的CNN, 池化處理可以提高預(yù)測(cè)準(zhǔn)確度；但對(duì)另一部分結(jié)構(gòu)的CNN,池化處理會(huì)使預(yù)測(cè)準(zhǔn) 確度降低。時(shí)間復(fù)雜度上，增加卷積神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)層數(shù)，增大單卷積層的特征提取框 面積，都會(huì)增加網(wǎng)絡(luò)訓(xùn)練時(shí)間；而引入池化處理則通常會(huì)降低網(wǎng)絡(luò)訓(xùn)練時(shí)間。我們把不引入池化處理的單卷積層，并且卷積層的特征提取框邊長(zhǎng)為1/2原矩 陣階數(shù)的CNN稱為HF-CNNo對(duì)10階矩陣，HF-CNN即指“5c-ls-BP”結(jié)構(gòu)。HF-CNN是其中較為“扁平”的一種。HF-CNN只有一個(gè)卷積層，卷積面積 為矩陣總“面積”的1/4,并且沒(méi)有進(jìn)行池化處理。這一網(wǎng)絡(luò)結(jié)構(gòu)在預(yù)測(cè)積和式量 級(jí)上表現(xiàn)最好。3. 2. 2 HF-C

60、NN在各階矩陣上的預(yù)測(cè)效果的比較通過(guò)實(shí)驗(yàn)3.2.1,我們發(fā)現(xiàn)，HF-CNN是多種不同結(jié)構(gòu)CNN中，預(yù)測(cè)效果比較 好，在各階矩陣上的表現(xiàn)比較穩(wěn)定的一個(gè)。下表中給出這一類結(jié)構(gòu)的CNN網(wǎng)絡(luò)在 8-18階矩陣上的預(yù)測(cè)準(zhǔn)確度。訓(xùn)練數(shù)據(jù)選取為10%-90%各個(gè)程度的稀疏度矩陣構(gòu)成的完整數(shù)據(jù)（共90000 個(gè)訓(xùn)練樣本），測(cè)試數(shù)據(jù)也選取為10%-90%稀疏度的完整數(shù)據(jù)（共9000個(gè)測(cè)試樣 本）。“準(zhǔn)確預(yù)測(cè)”表示預(yù)測(cè)結(jié)果與真實(shí)值在同一數(shù)量級(jí)（每相差10倍為相差一個(gè) 數(shù)量級(jí)），“偏大一量級(jí)”表示預(yù)測(cè)結(jié)果相比于真實(shí)值偏大1個(gè)數(shù)量級(jí)，“偏小 一量級(jí)”表示預(yù)測(cè)結(jié)果相比與真實(shí)值偏小1個(gè)數(shù)量級(jí)；“預(yù)測(cè)錯(cuò)誤”表示預(yù)測(cè)結(jié) 果相