蔡东风,朱耀辉,白 宇

(沈阳航空航天大学 知识工程研究中心，沈阳 110136)



一种面向计数问题的公式发现方法

蔡东风,朱耀辉,白 宇

(沈阳航空航天大学 知识工程研究中心，沈阳 110136)

在分析计数问题特点的基础之上，提出了一种面向计数问题的公式发现方法。该方法能根据给定的计数数列，自动发现其计数递推公式。将计数递推公式按公式的系数不同分为10种不同的公式类型(也称公式模式)，对给定的计数数列，采用SVM方法进行公式模式的分类，采用求解线性方程组方法对识别的公式模式参数进行求解，并为了防止过拟合得到错误的公式，利用专用的验证数据对求解后得到的具体计数递推公式进行公式验证。最后，采用国际公开的整数数列集OEIS中的645个计数问题进行十折交叉验证实验，求解正确率达92.56%。在新公式发现实验中，发现了目前OEIS数据集中尚未包含的10个新公式。

公式发现；机器发现；计数问题；模式分类；递推公式

由于人工求解计数问题，特别是对比较复杂的计数问题相当困难，本文尝试利用机器学习的方法自动发现计数公式，提出了一种利用SVM进行公式模式的分类和利用线性方程组对公式模式的参数进行求解的计数公式发现方法，简称基于模式(模式分类+模式求解)的公式发现方法。

迄今为止，已有多种公式发现[1]方法被提出。其中，Pat Langly等人1977年提出的BACON系统[2-4]是公式发现的先驱,成功地重新发现了开普勒行星运动第三定律、理想气体定律、万有引力定律等物理和化学公式。……