基于機(jī)器學(xué)習(xí)思想的非線性方程組求解

徐 林

(陽泉師范高等?？茖W(xué)校，山西 陽泉 045200)

基于機(jī)器學(xué)習(xí)思想的非線性方程組求解

徐 林

(陽泉師范高等專科學(xué)校，山西 陽泉 045200)

為解決非線性方程組求解過程中計算繁瑣、計算耗時長、計算結(jié)果不精確的問題，選用機(jī)器學(xué)習(xí)方法，利用Bayes rules實現(xiàn)機(jī)器學(xué)習(xí)的決策操作和學(xué)習(xí)過程，融合半解析法的思想，開發(fā)非線性方程組實數(shù)/復(fù)數(shù)求解程序“GuessKey”，實現(xiàn)對非線性方程組所有的實數(shù)解和復(fù)數(shù)解進(jìn)行搜索。同現(xiàn)在常用的非線性方程組求解算法進(jìn)行比較，結(jié)果顯示：該算法在全局搜索能力、計算精度、計算速度方面都優(yōu)于其他算法。

Bayes rules；決策函數(shù)；半解析解；計算精度

1 研究背景

非線性方程組適合描述更為復(fù)雜的工程、自然現(xiàn)象，對于一些瞬變過程具有很好的適用性，是數(shù)學(xué)領(lǐng)域以及工程領(lǐng)域長期關(guān)注的問題[1]。但是，非線性方程組的求解過程比較繁瑣，且沒有解析解，一直為研究的難點[2-3]。

鑒于此，國內(nèi)外學(xué)者針對擬牛頓算法進(jìn)行了大量研究。Eisen等人[4]利用并行計算來提升計算速度，在計算時，可以同時利用不同的內(nèi)核，從而使復(fù)雜非線性方程組求解問題成為可能，但Eisen等人并沒有針對算法層面進(jìn)行改進(jìn)，依照的是計算機(jī)硬件的優(yōu)勢。Lorenzo Stella等人[5]利用粒子群算法-擬牛頓法求解非線性方程組，在一定程度上提升了算法的全局搜索能力，但僅限于實數(shù)解，對復(fù)數(shù)域沒有涉及。Yousefian和Im ekli U等人[6-7]利用遺傳算法-擬牛頓法求解非線性方程組，同樣意在提升算法的全局搜索能力，但僅限于實數(shù)解，對復(fù)數(shù)域沒有涉及。Farzad Rahpeymaii、Jun Kitagawa等人[8-9]通過對比不同的算法，發(fā)現(xiàn)機(jī)器學(xué)習(xí)在解答非線性方程組的時候，全局搜索能力頗佳，認(rèn)為機(jī)器學(xué)習(xí)可以在復(fù)數(shù)域和實數(shù)域都有較好的全局搜索能力。

本文基于機(jī)器學(xué)習(xí)的思想，通過Bayes Rule實現(xiàn)機(jī)器學(xué)習(xí)的決策操作和主動學(xué)習(xí)過程，并融合半解析解的相關(guān)思想[10]，開發(fā)非線性方程組實數(shù)/復(fù)數(shù)求解程序“GuessKey”。利用機(jī)器學(xué)習(xí)對非線性方程進(jìn)行學(xué)習(xí)，并運用學(xué)習(xí)后的數(shù)值空間對非線性方程進(jìn)行求解，在得到一個非線性方程的半解析表達(dá)式之后，代入其他非線性方程，進(jìn)而得到非線性方程組的解。最后，同常用的非線性方程組進(jìn)行求解算法比較，在全局搜索能力、計算精度、計算速度3個層面揭示算法的適用性。

2 機(jī)器學(xué)習(xí)的基本思想

對于機(jī)器學(xué)習(xí)，將感興趣的數(shù)據(jù)集合命名為D，集合D也被稱為訓(xùn)練數(shù)據(jù)，機(jī)器學(xué)習(xí)的目標(biāo)便是確定假設(shè)空間(命名為H)中的最佳假設(shè)。令P(h)表示未訓(xùn)練數(shù)據(jù)集合D之間假設(shè)h所擁有的初始概率，將其命名為prior probability。prior probability表示在當(dāng)前知識背景之下，假設(shè)h為正確假設(shè)的概率。同理，令P(D)表示欲觀察訓(xùn)練數(shù)據(jù)集合D的prior probability。P(D)反映在訓(xùn)練數(shù)據(jù)D之后假設(shè)h成立的置信度。

根據(jù)Bayes Rule：

(1)

在機(jī)器學(xué)習(xí)的過程中，考慮候選假設(shè)集合H，并從中尋找上述給定的數(shù)據(jù)集合D。在此，可能性最大的假設(shè)被命名為h(h∈H)，這樣，具有最大可能性的假設(shè)被稱為極大后檢假設(shè)：

(2)

其中，hMAP被稱為極大后檢假設(shè)。聯(lián)立式(1)和式(2)，得到

(3)

因為，P(D)并不是依賴于h的變量，而是一個常量，故而，式(3)可以寫作

(4)

式(4)可以做進(jìn)一步的簡化，如果假定H中每個假設(shè)有相同的prior probability，就可以使用極大似然假設(shè)：

(5)

其中，hML被稱為極大后檢假設(shè)。對于H中的任意h，有

(6)

通過不斷學(xué)習(xí)和訓(xùn)練，機(jī)器便擁有了對某一特定問題的處理能力。

3 非線性方程組求解

設(shè)非線性方程組

(7)

其中，(x1,x2,…,xn)為變量，(y1,y2,…,yn)為常數(shù)，為了便于書寫，將式(7)記作

fi(X)=yi，i=1,2,…,n.

(8)

式中：

X=(x1,x2,…,xn)T.

(9)

令空間Ri表示第i個方程fi的自變量X的所有可能取值。假設(shè)X在空間Ri中的第k次抽樣為

(10)

(11)

(12)

(13)

其中，δi被認(rèn)為是Kmeans算法誤差[11-12]。至此，便完成了對第i個方程fi的機(jī)器學(xué)習(xí)操作。

(14)

(15)

如此重復(fù)n次，得到

(16)

(17)

將式(16)代入式(7)，得到

(18)

如此共重復(fù)n次，可得X。

4 數(shù)值驗算

通過上述理論，開發(fā)非線性方程組實數(shù)/復(fù)數(shù)求解程序“GuessKey”，為了驗證本文算法A1的優(yōu)越性，利用傳統(tǒng)擬牛頓法A2、擬牛頓混合遺傳算法A3、粒子群算法A4、NGEA算法A5進(jìn)行比較。

4.1 全局搜索能力

(19)

利用數(shù)學(xué)知識可知，式(19)共6組解。利用5種算法分別進(jìn)行計算，結(jié)果見圖1。

根據(jù)圖2，本文提出算法的搜索能力最強(qiáng)為A1，其次是NGEA算法A5、粒子群算法A4和擬牛頓混合遺傳算法A3、傳統(tǒng)擬牛頓法A2。傳統(tǒng)擬牛頓法A2只能找到方程組的一個實數(shù)根，說明其搜

教師敘事探究確實承擔(dān)“集智”的重要價值，“集智”對于教師的專業(yè)成長意義顯然。展示性的敘事分享對于“集智”確實有重要貢獻(xiàn)，但是對于參與者的實質(zhì)成長卻存在阻隔。靜聽者傾向于對外歸因，覺得自己沒有遇上生命中的重要貴人，學(xué)生和家長又不配合，平時已經(jīng)竭盡全力了，哪有時間讀書和嘗試改變，等等。因此，許多教師培訓(xùn)會知行分離，聽者往往當(dāng)場深受震撼，做起來卻可能一籌莫展。

圖1 5種算法的搜索能力

索能力極差。粒子群算法A4和擬牛頓混合遺傳算法A3能夠搜索方程組的兩個實數(shù)根(該方程組只有

兩個實數(shù)根)，說明粒子群算法A4和擬牛頓混合遺傳算法A3在實數(shù)域的搜索能力尚可，但無法識別復(fù)數(shù)根。NGEA算法A5可以搜索到兩個實數(shù)根和兩個復(fù)數(shù)根，說明NGEA算法A5在實數(shù)域的搜算能力頗佳，對于復(fù)數(shù)域的搜索亦具有一定能力。綜上所述，算法A1的搜索能力最強(qiáng)。

4.2 計算精度

(20)

利用數(shù)學(xué)知識可知，式(20)共2組實數(shù)解。利用5種算法分別進(jìn)行計算，結(jié)果見表1。

表1 5種算法的計算精度

根據(jù)表1可以看出，算法A1、擬牛頓混合遺傳算法A3、粒子群算法A4、NGEA算法A5可以搜索到所有解，但傳統(tǒng)擬牛頓法A2只能搜索到一個解。

定義誤差

(21)

為了更好地觀察誤差，將誤差的單位設(shè)置成10-4(見圖2)。

根據(jù)圖2，本文提出的算法A1的精度最高，最高誤差不超過3×10-7，最小誤差為7×10-9，平均誤差為6×10-8；傳統(tǒng)擬牛頓法A2的精度相對較低，最高誤差不超過83×10-4，最小誤差為57×10-4，平均誤差為6×10-3；粒子群算法A4和擬牛頓混合遺傳算法A3的收斂精度相當(dāng)，最高誤差不超過98×10-4，最小誤差為13×10-4，平均誤差為21×10-4；NGEA算法A5精度也相對較低，最高誤差不超過58×10-4，最小誤差為11×10-4，平均誤差為16×10-4?？傮w而言，本文提出的算法A1的精度是傳統(tǒng)擬牛頓法A2的10 594.602 99倍，是擬牛頓混合遺傳算法A3的22 183.721 19倍，是粒子

群算法A4的73 129.744 86倍，是NGEA算法A5的26 268.005 51倍。

圖2 5種算法的搜索能力

4.3 計算速度

(22)

利用5種算法分別進(jìn)行計算，記錄其計算耗時，計算設(shè)備的配置參數(shù)為：Pentium (R)Dual-Core CPU，2.2 GHz，2 G內(nèi)存，win7X86系統(tǒng)。

根據(jù)圖3，算法A1的計算速度最高，耗時為3.165 42 h；傳統(tǒng)擬牛頓法A2的計算速度次之，耗時為4.675 62 h；NGEA算法A5計算速度最慢，耗時為14.586 77 h?？傮w而言，算法A1的計算速度是傳統(tǒng)擬牛頓法A2的1.477 09倍，是擬牛頓混合遺傳算法A3的3.403 61倍，是粒子群算法A4的3.052 63倍，是NGEA算法A5的4.608 16倍。

圖3 5種算法的計算耗時

5 結(jié) 論

本文基于機(jī)器學(xué)習(xí)的思想，融合了半解析解的思想求解非線性方程組，得到一個精確度較高的解。與常用算法進(jìn)行對比，結(jié)果發(fā)現(xiàn)：

1)算法A1的搜索能力最強(qiáng)，可以搜索出所有的解。

2)算法A1的精度是傳統(tǒng)擬牛頓法A2的10 594.602 99倍，是擬牛頓混合遺傳算法A3的22 183.721 19倍，是粒子群算法A4的73 129.744 86倍，是NGEA算法A5的26 268.005 51倍。

3)算法A1的計算速度是傳統(tǒng)擬牛頓法A2的1.477 09倍，是擬牛頓混合遺傳算法A3的3.403 61倍，是粒子群算法A4的3.052 63倍，是NGEA算法A5的4.608 16倍。

機(jī)器學(xué)習(xí)的思想是一種新的智能算法，可以對現(xiàn)有問題進(jìn)行自動優(yōu)化，對于提升計算效率、提高計算速度具有重要影響。

[1] EISEN M, MOKHTARI A, RIBEIRO A. A Decentralized Quasi-Newton Method for Dual Formulations of Consensus Optimization[J]. 2016.

[2] BALEEIRO A C, PEREIRA R P, BRIGATTO G A, et al. Multilayer Stratification Earth by Kernel Function and Quasi-Newton Method[J]. IEEE Latin America Transactions, 2016, 14(1):225-234.

[3] NIE Y, CHUNG C Y, XU N Z. System State Estimation Considering EV Penetration With Unknown Behavior Using Quasi-Newton Method[J]. IEEE Transactions on Power Systems, 2016:1-11.

[4] EISEN M, MOKHTARI A, RIBEIRO A. Decentralized Quasi-Newton Methods[J]. 2016.

[5] STELLA L, THEMELIS A, PATRINOS P. Forward-backward quasi-Newton methods for nonsmooth optimization problems[J]. 2016.

[6] YOUSEFIAN F, NEDI A, SHANBHA U V. Stochastic quasi-Newton methods for non-strongly convex problems: convergence and rate analysis[J]. 2016.

[8] RAHPEYMAII F, KIMIAEI M, BAGHERI A. A limited memory quasi-Newton trust-region method for box constrained optimization[J]. Journal of Computational and Applied Mathematics, 2016, 303:105-118.

[9] KITAGAWA J, MéRIGOT Q, THIBERT B. A Newton algorithm for semi-discrete optimal transport[J]. 2016.

[10] 王俊奇, 李闖, 董曄. Bishop法的半解析解及其廣義數(shù)學(xué)模型[J]. 水利與建筑工程學(xué)報, 2015(6):123-128.

[11] DASGUPTA S. Evaluation of the antimicrobial activity of Moringa oleifera seed extract as a sustainable solution for potable water[J]. Rsc Advances, 2016, 6.

[12] DASGUPTA A, POCO J, BERTINI E, et al. Reducing the Analytical Bottleneck for Domain Scientists: Lessons from a Climate Data Visualization Case Study[J]. Computing in Science & Engineering, 2016, 18(1):92-100.

[責(zé)任編輯：郝麗英]

Solutions to nonlinear equations based on machine learning theory

XU Lin

(Yangquan Techers College, Yangquan 045200,China)

In order to solve the problem of computational complexity, long calculation time and inaccurate calculation results in the process of solving nonlinear equations, this paper chooses machine learning method and Bayes rules to realize the decision-making and learning process for machine learning, by compromising the idea of semi-analytical solution, and developing real/complex solution procedure of nonlinear equations-“GuessKey”, in order to realize the search for all real solutions and complex solutions to nonlinear equations. Compared with the algorithm for solving the nonlinear equations which is commonly used in the present, the result shows this algorithm is superior to other algorithms in terms of global search capability, computational accuracy and computational speed.

Bayes rules; decision function; semi-analytical solution; computational accuracy

10.19352/j.cnki.issn1671-4679.2016.06.011

2016-06-30

徐 林(1982-)，女，講師，研究方向：概率統(tǒng)計.

O241.7

A

1671-4679(2016)06-0045-04