一種面向計(jì)數(shù)問(wèn)題的公式發(fā)現(xiàn)方法

蔡?hào)|風(fēng),朱耀輝,白 宇

(沈陽(yáng)航空航天大學(xué) 知識(shí)工程研究中心，沈陽(yáng) 110136)

?

一種面向計(jì)數(shù)問(wèn)題的公式發(fā)現(xiàn)方法

蔡?hào)|風(fēng),朱耀輝,白 宇

(沈陽(yáng)航空航天大學(xué) 知識(shí)工程研究中心，沈陽(yáng) 110136)

在分析計(jì)數(shù)問(wèn)題特點(diǎn)的基礎(chǔ)之上，提出了一種面向計(jì)數(shù)問(wèn)題的公式發(fā)現(xiàn)方法。該方法能根據(jù)給定的計(jì)數(shù)數(shù)列，自動(dòng)發(fā)現(xiàn)其計(jì)數(shù)遞推公式。將計(jì)數(shù)遞推公式按公式的系數(shù)不同分為10種不同的公式類(lèi)型(也稱(chēng)公式模式)，對(duì)給定的計(jì)數(shù)數(shù)列，采用SVM方法進(jìn)行公式模式的分類(lèi)，采用求解線性方程組方法對(duì)識(shí)別的公式模式參數(shù)進(jìn)行求解，并為了防止過(guò)擬合得到錯(cuò)誤的公式，利用專(zhuān)用的驗(yàn)證數(shù)據(jù)對(duì)求解后得到的具體計(jì)數(shù)遞推公式進(jìn)行公式驗(yàn)證。最后，采用國(guó)際公開(kāi)的整數(shù)數(shù)列集OEIS中的645個(gè)計(jì)數(shù)問(wèn)題進(jìn)行十折交叉驗(yàn)證實(shí)驗(yàn)，求解正確率達(dá)92.56%。在新公式發(fā)現(xiàn)實(shí)驗(yàn)中，發(fā)現(xiàn)了目前OEIS數(shù)據(jù)集中尚未包含的10個(gè)新公式。

公式發(fā)現(xiàn)；機(jī)器發(fā)現(xiàn)；計(jì)數(shù)問(wèn)題；模式分類(lèi)；遞推公式

由于人工求解計(jì)數(shù)問(wèn)題，特別是對(duì)比較復(fù)雜的計(jì)數(shù)問(wèn)題相當(dāng)困難，本文嘗試?yán)脵C(jī)器學(xué)習(xí)的方法自動(dòng)發(fā)現(xiàn)計(jì)數(shù)公式，提出了一種利用SVM進(jìn)行公式模式的分類(lèi)和利用線性方程組對(duì)公式模式的參數(shù)進(jìn)行求解的計(jì)數(shù)公式發(fā)現(xiàn)方法，簡(jiǎn)稱(chēng)基于模式(模式分類(lèi)+模式求解)的公式發(fā)現(xiàn)方法。

迄今為止，已有多種公式發(fā)現(xiàn)[1]方法被提出。其中，Pat Langly等人1977年提出的BACON系統(tǒng)[2-4]是公式發(fā)現(xiàn)的先驅(qū),成功地重新發(fā)現(xiàn)了開(kāi)普勒行星運(yùn)動(dòng)第三定律、理想氣體定律、萬(wàn)有引力定律等物理和化學(xué)公式。Zembowitz[5]等人在搜索公式時(shí)考慮數(shù)據(jù)的誤差進(jìn)而研發(fā)了FAHRENHEI系統(tǒng)。Dzeroski[6-7]等人采用多元線性回歸同時(shí)考慮多個(gè)變量，并添加微分項(xiàng)拓展公式發(fā)現(xiàn)的范圍。隨后，公式發(fā)現(xiàn)系統(tǒng)被用于科學(xué)模型的修正[8-9]，針對(duì)特定領(lǐng)域公式發(fā)現(xiàn)[10-11]。此外，國(guó)內(nèi)陳文偉[12-15]等人基于原型函數(shù)庫(kù)，利用啟發(fā)式搜索不斷尋找具有最佳線性逼近關(guān)系的原型函數(shù)，并結(jié)合曲線擬合技術(shù)來(lái)求得數(shù)據(jù)間的規(guī)律。

以上發(fā)現(xiàn)系統(tǒng)在面向物理、化學(xué)方面的公式發(fā)現(xiàn)上表現(xiàn)出較好的效果,但是在面向計(jì)數(shù)問(wèn)題的公式發(fā)現(xiàn)上存在困難。這主要是因?yàn)橛?jì)數(shù)公式與物理、化學(xué)公式存在明顯的不同。首先，計(jì)數(shù)公式的數(shù)據(jù)是整數(shù)，而物理、化學(xué)公式的數(shù)據(jù)是實(shí)數(shù)，一般求解同樣的整數(shù)域問(wèn)題要比實(shí)數(shù)域困難；其次，用于學(xué)習(xí)計(jì)數(shù)公式的數(shù)據(jù)要求是精準(zhǔn)無(wú)噪聲的，而用于學(xué)習(xí)物理、化學(xué)公式的經(jīng)驗(yàn)數(shù)據(jù)可能含有誤差或噪聲，要求學(xué)到的計(jì)數(shù)公式必須精準(zhǔn)地滿足所有已給數(shù)據(jù)；最后，計(jì)數(shù)公式的數(shù)據(jù)通常在整數(shù)域內(nèi)無(wú)限延伸，而物理、化學(xué)公式的數(shù)據(jù)通常在一個(gè)相對(duì)固定的實(shí)數(shù)域內(nèi)變化。這些差別說(shuō)明對(duì)于計(jì)數(shù)公式的發(fā)現(xiàn)需要采用新的方法。

因此，本文在分析計(jì)數(shù)問(wèn)題和計(jì)數(shù)公式的特點(diǎn)基礎(chǔ)之上，提出了一種新的計(jì)數(shù)公式發(fā)現(xiàn)方法，能自動(dòng)地發(fā)現(xiàn)計(jì)數(shù)遞推公式。按公式的系數(shù)不同分為10種不同的公式類(lèi)型(也稱(chēng)公式模式)，采用“模式分類(lèi)+模式求解”的方法進(jìn)行公式發(fā)現(xiàn)。最后，在國(guó)際公開(kāi)的整數(shù)數(shù)列集OEIS(On-Line Encyclopedia of Integer Sequence)上進(jìn)行發(fā)現(xiàn)實(shí)驗(yàn)，求解正確率達(dá)92.56%，并發(fā)現(xiàn)了一些目前OEIS數(shù)據(jù)集中沒(méi)有的新公式。

1 計(jì)數(shù)問(wèn)題及計(jì)數(shù)公式

從以上實(shí)例可見(jiàn)，無(wú)論是復(fù)雜的求和、還是含有組合數(shù)以及階乘等常見(jiàn)的計(jì)數(shù)公式表達(dá)，往往可以化為遞推公式形式。在實(shí)際計(jì)數(shù)問(wèn)題中，復(fù)雜的通式公式若能轉(zhuǎn)化為遞推表達(dá)，通常會(huì)比較簡(jiǎn)單且易于理解[16-17]。例如，著名的“斐波那契數(shù)列”的通式表示包含無(wú)理數(shù)，而遞推公式卻非常簡(jiǎn)單(Dn=Dn-1+Dn-2)。遞推公式作為公式，特別是計(jì)數(shù)公式的一種表示形式，具有非常強(qiáng)的表達(dá)能力，有些復(fù)雜的遞推表達(dá)很難找到或根本不存在非遞推表達(dá)。因此，本研究采用計(jì)數(shù)公式的遞推表示形式。

2 基于模式的計(jì)數(shù)公式發(fā)現(xiàn)方法

提出一種基于模式的計(jì)數(shù)公式發(fā)現(xiàn)方法。該方法能根據(jù)給定的計(jì)數(shù)數(shù)列，自動(dòng)地發(fā)現(xiàn)其計(jì)數(shù)遞推公式。將遞推公式分為不同模式，采用SVM[18]方法進(jìn)行公式模式的分類(lèi)，采用求解線性方程組方法對(duì)識(shí)別的公式模式的參數(shù)進(jìn)行求解，并為了防止過(guò)擬合得到錯(cuò)誤的公式，利用預(yù)留的驗(yàn)證數(shù)據(jù)對(duì)求解后得到的具體計(jì)數(shù)遞推公式進(jìn)行公式驗(yàn)證。

2.1 公式模式

遞推公式也稱(chēng)差分方程，其一般形式如公式(1)所示，稱(chēng)為k階遞推公式。h為遞推函數(shù)，ui表示當(dāng)n=i時(shí)的計(jì)數(shù)值，稱(chēng)為遞推變量或差分變量，un和un-k分別稱(chēng)為首項(xiàng)和尾項(xiàng)；f(n)為齊次項(xiàng)，當(dāng)f(n)=0時(shí)，稱(chēng)為齊次遞推公式；當(dāng)f(n)≠0時(shí)，稱(chēng)為非齊次遞推公式。

h(un,un-1,…,un-k,n)=f(n)(n≥k≥1)

(1)

本文分析了OEIS中大量已知計(jì)數(shù)問(wèn)題的計(jì)數(shù)公式，發(fā)現(xiàn)絕大多數(shù)情況下，遞推函數(shù)h都是遞推變量ui的線性組合，即式(2)的形式。其中g(shù)i(n)是n的多項(xiàng)式函數(shù)，一般為常數(shù)或n的3階以下的多項(xiàng)式，g0(n)的次數(shù)越低且gi(n)(i>0)的次數(shù)越高表示計(jì)數(shù)數(shù)列增長(zhǎng)越快。

(2)

因此，按遞推公式的首項(xiàng)系數(shù)g0(n)以及其它變量系數(shù)gi(n)，將式(2)分為如表1所示的7種公式模式(M1-M7)，再加入最常見(jiàn)的多項(xiàng)式模式(M9)，齊次項(xiàng)為多項(xiàng)式型和遞推函數(shù)h為常系數(shù)2次或更高次多項(xiàng)式模式(M8)以及其他模式(M10)，總共分為10種公式模型。另外，式(2)中齊次項(xiàng)函數(shù)f(n)也可分為以下4種類(lèi)型，其中多項(xiàng)式類(lèi)型最為常見(jiàn)。

(P+E型)：f3(n)=f1(n)+f2(n)

表1 遞推公式模式(g0-k的次數(shù)為0表示常數(shù)，- 表示不存在)

模式g0次數(shù)g1-k次數(shù)簡(jiǎn)稱(chēng)縮寫(xiě)公式實(shí)例M100常常型CCun-un-1-un-2+un-13=0M201常一次型C1Pun+(n-2)un-1+2(n-1)un-2=0M311一次一次型1P1P(n+1)un-(4n-2)un-1=0M402常二次型C2Pun=(2n-1)un-1-(n-1)2un-2M512一次二次型1P2P(n-1)un=n2un-1-1M622二次二次型2P2P(4n2+6n+2)un=(27n2-27n+6)un-1M7>=0>2二次以上型G2Pun=n2un-1-1/2n(n-1)2un-2M8h為常系數(shù)2次或更高次多項(xiàng)式HPun+1=u2n-un+1M9--多項(xiàng)式型Pun=(n2+3n)/2M10其他Ou2n=6n-3-un，u2n+1=un+1+2n

2.2 基于模式的公式發(fā)現(xiàn)方法

圖1是本文提出的基于模式的計(jì)數(shù)公式發(fā)現(xiàn)方法或系統(tǒng)的流程圖。該系統(tǒng)由數(shù)列輸入、特征抽取、模式分類(lèi)、模式求解、公式驗(yàn)證、公式輸出以及模式庫(kù)等組成。在模式庫(kù)中，記錄每種模式的ID、類(lèi)型、模式描述、模式求解方法等。算法流程如下：

(1) 模型訓(xùn)練。利用已給數(shù)據(jù)訓(xùn)練不同模式的SVM模型。由于是多模式分類(lèi)問(wèn)題，采用分類(lèi)精度相對(duì)高的OVO方法；

(2) 實(shí)例輸入。輸入計(jì)數(shù)問(wèn)題的計(jì)數(shù)數(shù)列I的前m個(gè)計(jì)數(shù)值，記為Im。并將其前m1個(gè)作為學(xué)習(xí)數(shù)據(jù)Ie和后m2=m-m1個(gè)作為驗(yàn)證數(shù)據(jù)It；

(3) 特征抽取。對(duì)Ie進(jìn)行特征抽取和縮放處理，生成輸入實(shí)例的特征向量Vi；

(4) 模式分類(lèi)。利用SVM模型，對(duì)Vi進(jìn)行公式模式的分類(lèi)，保留前nbest分類(lèi)結(jié)果到nbest模式列表中；

(5) nbest控制。如果nbest模式列表為空，則失敗停止，否則從列表中取出當(dāng)前最好模式m；

(6) 模式求解。利用模式庫(kù)和學(xué)習(xí)數(shù)據(jù)Ie，對(duì)模式進(jìn)行求解，即確定模式的具體參數(shù)。如求解成功，表示發(fā)現(xiàn)了滿足Ie的公式F，否則轉(zhuǎn)(5)；

(7) 公式驗(yàn)證。驗(yàn)證F是否滿足驗(yàn)證數(shù)據(jù)It。如果成功，輸出公式F，停止，否則轉(zhuǎn)(5)。

圖1 公式發(fā)現(xiàn)系統(tǒng)流程圖

本方法的最終目標(biāo)是發(fā)現(xiàn)計(jì)數(shù)公式，不是公式模式的分類(lèi)。不同于一般分類(lèi)問(wèn)題，SVM模式分類(lèi)的主要作用是可將更有希望的模式放在前面求解，可顯著提高系統(tǒng)的效率。對(duì)于無(wú)法求解的計(jì)數(shù)數(shù)列，給出的分類(lèi)模式也可以作為研究人員的參考。下面對(duì)模式分類(lèi)(包括特征抽取)、模式求解以及公式驗(yàn)證進(jìn)行具體介紹。

2.2.1 模式分類(lèi)

模式分類(lèi)的關(guān)鍵是根據(jù)問(wèn)題和樣本的特點(diǎn)選擇合適的特征。針對(duì)計(jì)數(shù)問(wèn)題，輸入樣本是計(jì)數(shù)數(shù)列，記為U=u1,u2,…，un,其主要特點(diǎn)是隨n的增大通項(xiàng)un趨向正無(wú)窮大，數(shù)值的變化范圍很大，沒(méi)有固定范圍，數(shù)據(jù)間關(guān)系密切不獨(dú)立。結(jié)合分類(lèi)模式的特點(diǎn)，本文在分類(lèi)特征的選擇上著重對(duì)數(shù)列的變化趨勢(shì)進(jìn)行度量，并假設(shè)變化趨勢(shì)相似的數(shù)列其對(duì)應(yīng)的公式模式相同。通過(guò)實(shí)驗(yàn)，最后確定了如下定義的增長(zhǎng)量和增長(zhǎng)率兩類(lèi)特征。

增長(zhǎng)量(I)：相鄰數(shù)據(jù)項(xiàng)的差分，Inci=ui+1-ui

例如：給定數(shù)列U=1，3，8，15，24，35，48，……。取前n=7個(gè)數(shù)據(jù)作為學(xué)習(xí)數(shù)據(jù)進(jìn)行特征化處理。對(duì)應(yīng)的1階特征數(shù)列為：

增長(zhǎng)量數(shù)列I=2，5，7，9，11，13

增長(zhǎng)率數(shù)列R=2，5/3，7/8，9/15，11/24，13/35

對(duì)于生成的不同特征數(shù)列，還可以進(jìn)一步特征化處理，生成高階特征數(shù)列。如對(duì)應(yīng)上述增長(zhǎng)量數(shù)列I，可再進(jìn)行特征化處理，稱(chēng)為2階特征數(shù)列(II，IR)。

I的增長(zhǎng)量數(shù)列 II=3，2，2，2，2

I的增長(zhǎng)量數(shù)列 IR=3/2，2/5，2/7，2/9，2/11

一般高階特征能提供更深層的信息，但相對(duì)低階特征，獲取高階特征需要的數(shù)據(jù)更多且計(jì)算量更大。通常特征化處理后的特征值的變化范圍還很大，不適合直接用于模式分類(lèi)，本文在模式分類(lèi)前采用反正切函數(shù)將其映射在(-π/2，π/2)之間，即對(duì)某一特征值x，映射后的值為y=atan(x)，其中atan為反正切函數(shù)。

計(jì)數(shù)問(wèn)題要求計(jì)數(shù)公式必須能完全精確匹配給定的數(shù)據(jù)(包括學(xué)習(xí)數(shù)據(jù)和驗(yàn)證數(shù)據(jù))，即使這樣，學(xué)習(xí)到的計(jì)數(shù)公式也不一定是正確的，有可能出現(xiàn)過(guò)擬合現(xiàn)象，這是歸納學(xué)習(xí)的特點(diǎn)和無(wú)奈。但是，相對(duì)學(xué)習(xí)到的計(jì)數(shù)公式的參數(shù)個(gè)數(shù)，給定數(shù)據(jù)比較多時(shí)，學(xué)習(xí)效果一般會(huì)比較好。另外，計(jì)數(shù)數(shù)列一定是非負(fù)整數(shù)數(shù)列，通常是遞增非負(fù)整數(shù)數(shù)列，隨著n的增大通項(xiàng)將趨向正無(wú)窮大，這點(diǎn)對(duì)機(jī)器學(xué)習(xí)的特征選擇影響較大。

基于以上特征抽取和映射，采用SVM[19]方法進(jìn)行公式模式分類(lèi)。SVM在多分類(lèi)問(wèn)題上，常用的方法有“一對(duì)余(One-VS-Rest)OVR”和“一對(duì)一(One-VS-One)OVO”方法，OVR需要二分類(lèi)器的個(gè)數(shù)少，但是分類(lèi)結(jié)果通常比OVO差，所以本文采用OVO方法。

另外，由于一個(gè)數(shù)列的遞推表示有時(shí)可能對(duì)應(yīng)多種模式，即數(shù)列與公式模式是多對(duì)多的關(guān)系。因此，算法中采用nbest的求解方式，如果僅在nbest模式列表為空時(shí)停止，可發(fā)現(xiàn)更多的公式模式或新的公式。

2.2.2 模式求解

模式求解是指給定輸入的計(jì)數(shù)數(shù)列和分類(lèi)的公式模式的條件下，確定模式參數(shù)的過(guò)程，即發(fā)現(xiàn)滿足已給學(xué)習(xí)數(shù)據(jù)的計(jì)數(shù)公式。不同模式可以采用不同的方法求解，一般可轉(zhuǎn)化為代數(shù)方程組，特別是線性方程組求解。但是，許多計(jì)數(shù)問(wèn)題的計(jì)數(shù)值很大，有時(shí)很難獲得較多的輸入數(shù)據(jù)。例如，n皇后問(wèn)題的不同解的計(jì)數(shù)問(wèn)題，當(dāng)n=26時(shí)，解數(shù)為22 317 699 616 364 044,這是目前已知解數(shù)的最大n值。因此，公式模式中的參數(shù)個(gè)數(shù)不可設(shè)定過(guò)多，要依據(jù)輸入數(shù)據(jù)的多少確定，有時(shí)需要對(duì)遞推公式的階數(shù)和遞推函數(shù)系數(shù)的次數(shù)進(jìn)行權(quán)衡和限制。另外，即使求解成功，得到候選公式，還需要進(jìn)一步通過(guò)驗(yàn)證數(shù)據(jù)的驗(yàn)證才能作為輸出，以防由于過(guò)擬合生成錯(cuò)誤公式。

對(duì)于參數(shù)較多的高階或高次的遞推公式模式，往往由于可用數(shù)據(jù)的不足或沒(méi)有好的求解方法，有些暫時(shí)還不能求解，如后面實(shí)驗(yàn)中G2P模式的實(shí)例。

2.2.3 公式驗(yàn)證

公式驗(yàn)證是指利用驗(yàn)證數(shù)據(jù)對(duì)由前面模式分類(lèi)和模式求解得到的候選計(jì)數(shù)公式進(jìn)行驗(yàn)證的過(guò)程，是防止由于數(shù)據(jù)過(guò)擬合造成發(fā)現(xiàn)錯(cuò)誤公式的必要步驟。

驗(yàn)證數(shù)據(jù)是輸入數(shù)據(jù)的一部分，但要獨(dú)立于學(xué)習(xí)數(shù)據(jù)，即輸入數(shù)據(jù)=學(xué)習(xí)數(shù)據(jù)+驗(yàn)證數(shù)據(jù)。實(shí)際應(yīng)用中，可根據(jù)輸入數(shù)據(jù)的多少確定學(xué)習(xí)數(shù)據(jù)和驗(yàn)證數(shù)據(jù)的比例分配，學(xué)習(xí)數(shù)據(jù)越多，可以學(xué)習(xí)到參數(shù)更多的復(fù)雜模型，而驗(yàn)證數(shù)據(jù)越多，會(huì)使我們對(duì)學(xué)習(xí)到并通過(guò)驗(yàn)證的公式的正確性更有信心。在本文實(shí)驗(yàn)中，采取了盡量增加學(xué)習(xí)數(shù)據(jù)和保證至少一個(gè)驗(yàn)證數(shù)據(jù)的原則，取得了很好的效果。但是，無(wú)論如何，自動(dòng)公式發(fā)現(xiàn)是基于數(shù)據(jù)的歸納學(xué)習(xí)，通過(guò)有限的采樣數(shù)據(jù)歸納學(xué)習(xí)得到的公式即使通過(guò)驗(yàn)證數(shù)據(jù)的驗(yàn)證，也不一定就能滿足其它的新數(shù)據(jù)。因此，嚴(yán)格意義上說(shuō)，自動(dòng)發(fā)現(xiàn)的計(jì)數(shù)公式應(yīng)該被認(rèn)識(shí)是通過(guò)了有限數(shù)據(jù)驗(yàn)證的原計(jì)數(shù)問(wèn)題計(jì)數(shù)公式的一個(gè)假說(shuō)或一個(gè)還需要證明的定理。對(duì)于相關(guān)研究人員可能是一個(gè)很有意義的提示和輔助，或是一個(gè)一直期待的結(jié)果。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與算法設(shè)置

OEIS(On-Line Encyclopedia of Integer Sequences)是一個(gè)在線整數(shù)數(shù)列百科全書(shū)。它由Neil J. A. Sloane在1964年創(chuàng)建，截至到2011年11月已容納超過(guò)二十萬(wàn)個(gè)數(shù)列，其解釋涉及超過(guò)3千篇相關(guān)圖書(shū)和文章。 OEIS對(duì)每一個(gè)數(shù)列都有詳細(xì)表述，包括：數(shù)列的來(lái)源，數(shù)列的相關(guān)文獻(xiàn)，已發(fā)現(xiàn)的數(shù)列公式，生成數(shù)列的程序，求解數(shù)列的難易程度等。整數(shù)數(shù)列包括由計(jì)數(shù)問(wèn)題產(chǎn)生的計(jì)數(shù)數(shù)列，計(jì)數(shù)數(shù)列是整數(shù)數(shù)列的主要組成部分。OEIS是公認(rèn)的研究計(jì)數(shù)問(wèn)題的重要公開(kāi)資源。

本實(shí)驗(yàn)包括已有公式的再發(fā)現(xiàn)實(shí)驗(yàn)(實(shí)驗(yàn)一)和新公式的發(fā)現(xiàn)實(shí)驗(yàn)(實(shí)驗(yàn)二)。實(shí)驗(yàn)一中的實(shí)驗(yàn)數(shù)據(jù)取自O(shè)EIS公開(kāi)數(shù)據(jù)集標(biāo)號(hào)為A000001～A003000中的遞推公式和多項(xiàng)式公式，共計(jì)645個(gè)計(jì)數(shù)問(wèn)題或計(jì)數(shù)數(shù)列；實(shí)驗(yàn)二將實(shí)驗(yàn)一的全部數(shù)據(jù)作為模型訓(xùn)練數(shù)據(jù)，對(duì)A000001～A000300的計(jì)數(shù)問(wèn)題進(jìn)行新公式的發(fā)現(xiàn)實(shí)驗(yàn)。

算法設(shè)置是指以下實(shí)驗(yàn)中的一些參數(shù)的確定。主要包括：SVM模型訓(xùn)練數(shù)據(jù)取為u6～u15，特征階數(shù)為3，學(xué)習(xí)數(shù)據(jù)范圍因問(wèn)題而異，公式驗(yàn)證數(shù)據(jù)1個(gè)以上。以上設(shè)置都是通過(guò)實(shí)驗(yàn)選取的經(jīng)驗(yàn)值。例如，計(jì)數(shù)數(shù)列開(kāi)始時(shí)的數(shù)據(jù)一般并不能很好地顯示出數(shù)據(jù)的變化趨勢(shì)，通過(guò)實(shí)驗(yàn)選擇訓(xùn)練數(shù)據(jù)從u6開(kāi)始。

3.2 公式再發(fā)現(xiàn)實(shí)驗(yàn)

本實(shí)驗(yàn)采用2.2節(jié)提出的基于模式的計(jì)數(shù)公式發(fā)現(xiàn)方法，對(duì)上述OEIS實(shí)驗(yàn)數(shù)據(jù)集的645個(gè)問(wèn)題進(jìn)行十折交叉驗(yàn)證實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2和表2所示。其中，“分類(lèi)”表示能正確分類(lèi)的公式模式，“求解”表示能正確求解的計(jì)數(shù)公式。圖2和表2給出了在不同nbest取值的情況下，能夠正確分類(lèi)和求解的問(wèn)題的比率曲線和具體數(shù)值?？梢?jiàn)，top1-top3的模式分類(lèi)正確率分別為：75.97%，89.46%，95.35%，已達(dá)到相當(dāng)高的水平，而top8達(dá)到100%，平均每個(gè)模式分類(lèi)僅需要循環(huán)1.42次。top1-top3的模式求解正確率分別為：73.02%、83.72%、89.15%，而top8達(dá)92.56%?？傊?，通過(guò)本實(shí)驗(yàn)驗(yàn)證了基于模式的遞推公式發(fā)現(xiàn)方法是有效的，OEIS中的645個(gè)問(wèn)題中，共求解597個(gè)，求解率達(dá)90%以上。

另外，表2進(jìn)一步給出了按不同模式(共9類(lèi)模式，不包括其它類(lèi))的分類(lèi)和求解的具體問(wèn)題個(gè)數(shù)及比率。可見(jiàn)，不同模式的公式分布非常不均勻，常系數(shù)遞推公式模式(CC)和多項(xiàng)式公式模式(P)共記418個(gè)，占整個(gè)數(shù)據(jù)集的64.8%。P、CC、C1P、HP四類(lèi)公式模式分類(lèi)效果較好，而1P2P、2P2P模式的訓(xùn)練實(shí)例很少導(dǎo)致分類(lèi)效果相對(duì)較差；HP模式的訓(xùn)練實(shí)例雖也不多，

但其分類(lèi)與求解效果都較好，說(shuō)明高次的特征明顯；另外，對(duì)于參數(shù)較多的高次系數(shù)公式模式G2P，實(shí)驗(yàn)中由于可用數(shù)據(jù)相對(duì)較少，還需要尋找更有效的求解方法。

圖2 模式分類(lèi)和模式求解的nbest變化曲線

公式模式公式數(shù)量top1分類(lèi)求解top2分類(lèi)求解top3分類(lèi)求解top8分類(lèi)求解P116113113116116116116116116CC302272272297297299299302302C1P5852525454555558581P1P3266272730303232C2P33221313323233331P2P100000001092P2P2666131323232626G2P43150330360430HP252420242024202521總數(shù)645490471577540615575645597百分比1007597730289468372953589151009256

3.3 新公式發(fā)現(xiàn)實(shí)驗(yàn)

采用本文提出方法對(duì)OEIS集A000001～A000300共300個(gè)數(shù)列進(jìn)行新公式發(fā)現(xiàn)實(shí)驗(yàn)，共發(fā)現(xiàn)新公式10個(gè)。發(fā)現(xiàn)的新公式如表3所示。表中“原公式”表示OEIS中已存在的公式，“新公式”表示本實(shí)驗(yàn)發(fā)現(xiàn)的新公式?！霸健币粰趦H列出與對(duì)應(yīng)的“新公式”模式較相近的公式，并不是全部原公式。實(shí)驗(yàn)結(jié)果可知，A000115的原公式是非連續(xù)函數(shù)，但也能得到遞推公式表達(dá)；A000202沒(méi)有原公式，發(fā)現(xiàn)了較簡(jiǎn)潔的常系數(shù)遞推公式；A000130和A000222也沒(méi)有原公式，分別發(fā)現(xiàn)了較高次的遞推公式；A000128、A000150、A000180、A000266、A000245、A000256存在原公式，但又發(fā)現(xiàn)了不同模式的新公式。

另外，為了保證發(fā)現(xiàn)公式的正確性，本文對(duì)以上發(fā)現(xiàn)的新公式使用OEIS提供的對(duì)應(yīng)問(wèn)題的全部數(shù)據(jù)進(jìn)行了公式驗(yàn)證，結(jié)果全部順利通過(guò)驗(yàn)證。

表3 新公式發(fā)現(xiàn)實(shí)驗(yàn)結(jié)果(序號(hào)上的數(shù)字表示n開(kāi)始計(jì)數(shù)的數(shù)字)

OEIS問(wèn)題序號(hào)原公式新發(fā)現(xiàn)公式A0001150un=[(n+4)2/20]un-un-2-un-5+un-7=1(n>6)]A0001281非遞推un-un-1-un-2=12n2-52n+4(n>2)A0001300無(wú)(n-3)un-(n2-2n-3)un-1+(n2-4n+5)un-2+(n2-6n+5)un-3-(n2-3n+2)un-4=0(n>3)A0001500非遞推(n2+n)un-(6n2-6n)un-1+(8n2-40n+36)un-2+(8n2+8n-72)un-3-(48n2-336n+576)un-4+(64n2-608n+1440)un-5=0(n>4)A0001842非遞推(n-1)un=(12n-14)un-1-(48n-64)un-2+(64n-96)(un-3)(n>4)A0002021無(wú)un-un-1-nn-8+un-9=0(n>9)A0002220無(wú)un-(n-5/2)un-1-(5/2n-6)un-2-(3n-21/2)un-3-(5/2n-23/2)un-4-(n-9/2)un-5-un-6(n>5)A00024502P2P型(n+2)un=(5n+2)un-1-(4n-6)un-2(n>1)A0002563G2P型(n2-11/2n+15/2)un-(13/2n2-423/8n+845/8)un-1-(27/16n2-189/16n+165/8)(un-2=0)(n>5)A0002660非遞推un=nun-1-(n-1)un-2+(n2-3n+2)un-3(n>2)

4 結(jié)論

本文首次提出了基于模式(模式分類(lèi)+模式求解)的計(jì)數(shù)公式發(fā)現(xiàn)方法。在OEIS數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，該方法能以較高的正確率再現(xiàn)已有公式，并能發(fā)現(xiàn)一些新的計(jì)數(shù)公式。需要強(qiáng)調(diào)的是，通過(guò)擴(kuò)充更多的不同類(lèi)型的公式模式，該方法能發(fā)現(xiàn)不限于遞推公式形式的更為復(fù)雜多樣的計(jì)數(shù)公式，也能用于其它問(wèn)題類(lèi)型的數(shù)學(xué)公式的發(fā)現(xiàn)或輔助發(fā)現(xiàn)。

[1]TODOROVSKI L.Equation Discovery[M].Springer US,2011.

[2]LANGLEY P,BRADSHAW G L,SIMON H A.BACON.5:The discovery of conservation laws[C]//IJCAI.1981,81:121-126.

[3]LANGLEY P,BRADSHAW G L,SIMON H A.Rediscovering chemistry with the BACON system[M]//Machine learning.Springer Berlin Heidelberg,1983:307-329.

[4]LANGLEY P,ZYTKOW J M.Data-driven approaches to empirical discovery[J].Artificial Intelligence,1989,40(1-3):283-312.

[5]ZEMBOWICZ R,YTKOW J M.Discovery of equations:experimental evaluation of convergence[C]//AAAI.San Jose,Ca,July.1992:70-75.

[6]DZEROSKI S,TODOROVSKI L.Discovering dynamics:from inductive logic programming to machine discovery[J].Journal of Intelligent Information Systems,1995,4(1):89-108.

[7]TODOROVSKI L,DZEROSKI S.Declarative bias in equation discovery[C]//ICML.1997:376-384.

[8]SAITO K,LANGLEY P,GRENAGER T,et al.Computational revision of quantitative scientific models[C]//International Conference on Discovery Science.Springer Berlin Heidelberg,2001:336-349.

[9]TODOROVSKI L,SAO D06EROSKI,LANGLEY P,et al.Using equation discovery to revise an earth ecosystem model of the carbon net production[J].Ecological Modelling,2003,170(170):141-154.

[10]TODOROVSKI L,D?EROSKI S.Integrating domain knowledge in equation discovery[M]//Computational Discovery of Scientific Knowledge.Springer Berlin Heidelberg,2007:69-97.

[11]D?EROSKI S，TODOROVSKI L.Equation discovery for systems biology:finding the structure and dynamics of biological networks from time course data.[J].Current Opinion in Biotechnology,2008,19(4):360-368.

[12]陳文偉,張帥.經(jīng)驗(yàn)公式發(fā)現(xiàn)系統(tǒng) FDD[J].小型微型計(jì)算機(jī)系統(tǒng),1999,20(6):410-413.

[13]馮金花,陳燕雷,關(guān)永.經(jīng)驗(yàn)公式發(fā)現(xiàn)系統(tǒng)(FDD)中對(duì)誤差的改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(20):5287 -5289.

[14]陳燕雷,孟俊仙,關(guān)永.經(jīng)驗(yàn)公式發(fā)現(xiàn)系統(tǒng)FDD函數(shù)庫(kù)的擴(kuò)充與改進(jìn)[J].微計(jì)算機(jī)信息,2010,26(27):232-234.

[15]陳燕雷,孟俊仙,關(guān)永.經(jīng)驗(yàn)公式發(fā)現(xiàn)FDD搜索方向判斷標(biāo)準(zhǔn)的改進(jìn)[J].微計(jì)算機(jī)信息,2011,27(4):238-239.

[16]韓林.巧用遞推公式求解四類(lèi)計(jì)數(shù)問(wèn)題[J].數(shù)學(xué)教學(xué)通訊：教師閱讀,2011(24):49-50.

[17]唐保祥,任韓.幾類(lèi)特殊圖完美匹配數(shù)目的遞推求法[J].西南師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2014(2):9-13.

[18]CHANG C C,LIN C J.LIBSVM:a library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology(TIST),2011,2(3):27.

[19]郎宇寧.基于支持向量機(jī)的多分類(lèi)方法研究及應(yīng)用[D].成都:西南交通大學(xué),2010.

(責(zé)任編輯：劉劃 英文審校：趙亮)

Formula discovery method for counting problem

CAI Dong-feng，ZHU Yao-hui， BAI Yu

(Knowledge Engineering Research Center,Shenyang Aerospace University,Shenyang 110136,China)

Inspired by the property of counting problems,we proposed a formula discovery method for counting problem.The method could automatically derive the recursion formula corresponding to some given counting sequence.Specifically,we first grouped the recursion formulas into different types,i.e.pattern,and then used SVM to do pattern classification on the input counting sequence.When the pattern was determined,we obtained the specific recursion formula by calculating the parameters(in the pattern),which could be translated into solving system of linear equations.Finally,we checked the correctness of the discovered recursion formula on unused part of the input data.By using the ten-fold cross validation test,we achieved 92.56% accuracy on 645 counting problems from the On-line Encyclopedia of Integer Sequence(OEIS).In the meanwhile,we discovered 10 new formulas are not included in OEIS.

formula discovery;machine discovery;counting problem;pattern classification;recursion formula

2015-10-28

蔡?hào)|風(fēng)(1958-)，男，遼寧沈陽(yáng)人，教授，主要研究方向：人工智能、自然語(yǔ)言處理，E-mail:caidf@vip.163.com。

2095-1248(2016)05-0061-07

TP391.1

A

10.3969/j.issn.2095-1248.2016.05.012