胡笳、陈同学、钱天培编译

机器学习单挑数学界:最新算法仲裁数列之美(附论文)

e + 1 = 0 ,这是数学史上最美妙的公式之一 —— 欧拉公式。

它揭示了表面看似无关的数学领域之间的深层联系,是数学界的伟大奇观之一。而这也指出了数学之美的另一个组成部分:数学模式必须在某种角度上是有趣的。

自古以来,发现这些有趣的模式一直是人类独有的能力。而现在,机器也具备了这样的能力!

近几年来,机器已经成为强有力的模式识别工具。人脸识别、目标检测、甚至水军评论过滤,不一而足。

这不由引发了我们的思考:机器学习算法是否也可以识别出有趣优雅的数学模式呢?

来自IBM研究中心的 Chai Wah Wu 的最新研究结果告诉我们:这完全是可能的!

Wu实现了一种机器学习算法,该算法已经能够学习并识别出数学结构中的某些优美之处,并被用于从完全随机的序列中,过滤出那些有趣的数列。

该研究的主要目的在于探究机器学习是否可以用于定义科学知识的本质属性,即是否能够辨别其是否具有优雅,简洁或有趣性质。并通过对数列进行研究来探索这个问题。

之所以采用数列进行研究,一方面是因为数列结构本身包含了很多基本的数学思维,另一方面是因为现有已被编辑和整理超过50年的庞大数列数据库可用于分析。

该算法使用了一种名为整数序列在线大全的特殊数据库,这个数据库最初由数学家尼尔斯隆(Neil Sloane)于20世纪60年代创建,并于1996年挂到网上。

整数序列在线大全数据库

http://oeis.org/

The Online Encyclopedia of Integer Sequences (OEIS) 整数序列在线大全由尼尔斯隆(Neil Sloane)于1964年创建,目前已经包含超过300,000个数列,并由数千名OEIS社区的志愿者不断地编辑和添加这些序列的元数据和引用信息。数据库中每个数列都被社区成员指定了关联的关键字。例如‘nice’,‘core’,‘base’,‘hard’等关键字。

40000个OEIS中的随机序列

图示为斜率 s与相关系数r的关系,采用RANSAC随机抽样一致算法作为回归求导函数,并且其slope值约为2。样本中的正常数据(大约占序列集的一半)符合Slope=2.001, intercept=0.003 ,相关系数r=0.999的回归曲线.

整数数列是指由根据某一规则排序后的一列数字。其中比较著名的数列包括素数——只能被自身和1整除的数;斐波那契数列,数列中的每项是前两项的和;甚至还包括一些较为普通的数列,例如奇数序列或者以7开头的素数序列。

实际上OEIS网站背后的数学家们撒开大网来寻找“有趣的”数列,由此网站中也收录了很多具有纯粹文化意义的数列。例如包含666序列的素数,其中666被称之为恶魔数字。

这个数据库甚至还录入了包含数字667的素数序列。667这个数字被认为很重要,因为在传真机普遍的时代,传真机号码通常就是人们的电话号码加1。也就是说,如果他们的电话号码是 123-4567,那他们的传真号码就是123-4568。按这种方式计算,667就是恶魔数字(666)的传真号码,因此这个数字具有一定的文化意义。

包含数字667的素数序列

http://oeis.org/A138563

如今,这个整数序列数据库包含约30万个序列,并且每天都有业余爱好者和专业人士提交新的序列,其中很多序列暗含着新的有趣的数学问题。

Wu的任务就是找到一种方式来从随机生成的序列中区分出这些“有趣的”序列。他的想法是通过找到作用于定义“有趣”序列的经验规则,来将其从其他序列中区分开来。

为了实现对这些数列分类计算,我们希望能够找出一些固定的数列特征,并将这些特征应用到有限个数序列上进行分类计算。本文研究中采用了两个经验规则来进行计算。

Wu说:“经验规则本身并不是数学定理,而是经由经验观察结果得出的规律。这些规律可能可以应用于很多自然或人造数据集”。例如电气工程的摩尔定律和经济学中的80/20帕累托原则。尽管这些“定律”的原因不得而知,他们却真实存在。

本福德定律(Benford’s Law)也是一个广泛适用很多数据集的经验规则。本福德定律是1881年由加拿大数学家和天文学家西蒙·纽康伯(Simon Newcomb)发现的。纽康伯注意到对数表书籍中的前几页较后面的页翻阅破损更严重,这表明以数字1开头的对数更加常见。

这使他得出一个原理,即在任意一组数字中,更多的情况是以数字1为首出现,而不是以其他数字为首。20世纪30年代,富兰克本福德(Frank Benford)也发现这一现象并推广了这个原理。

本福德定律(Benford’s Law)指出:在一组数字中,较小数字排在首位的概率更高。更准确的定义是,以b为底,数字d出现在首位的概率为logb( (d+1)/ d )。在本文研究中采用以10为底的公式版本。

本福德定律适用性广泛,例如电费数字,街道地址,股票价格数字等。这个定律的预测力很强,以至于它被用于识别财务账户中的欺诈行为。但它不适用于随机序列,这点究竟为什么至今还没有弄清。

的确,本福德定律支配一些整数序列这一现象是十分神奇的。那么它能多广泛地应用于这些OEIS数据库中的数列中呢?

为了弄清这一点,Wu计算了利用本福德定律预测从OEIS数据库中随机选择的40,000个序列的首位数字分布的结果。

事实证明本福德定律比预期的适用性更广。Wu说:“结果表明,大部分但不是全部的序列,从某种程度上满足本福德定律。”

他还发现,另一个经验规则泰勒定理(Taylor’s Law)也普遍存在。

泰勒定理(Taylor’s Law)由莱昂纳尔·泰勒(Lionel Taylor ) 于1961年提出。他指出在社会生态学中,均值µ和方差v似乎满足幂律公式:v = TaµTb,其中Ta和Tb为正常数。泰勒定理被观察出现在很多自然观察的数据集和数列中,如素数序列,和二项式系数序列。

接下来就是更进一步的问题了:本福德定律和泰勒定理能否将随机序列从OEIS的序列中区分出来?

为了弄清楚这个问题,Wu生成了40,000个随机整数序列,并将这些随机整数序列添加到从OEIS中选出的40,000个序列中去。然后他训练机器学习算法,利用本福德定律和泰勒定理来识别OEIS序列,并将OEIS序列从随机序列中区分出来。

在Wu从OEIS中随机选择的40,000条数列集中,每一个序列中至少包含990个数字。之所以采用990这个数字是因为,OEIS数据库对大部分数列的个数限制为1000个,有些数列中的数字个数稍少于1000个,如“包含至少n个连续相同数字的最小序列”。

为了验证上述问题,Wu从2000个随机整数中生成了大约40,000个序列,并计算得到这些随机序列的14个特征。然后将这些随机序列添加到上述OEIS序列中,组成80,000个随机序列,并随机抽取其中的70,000个作为训练集,10,000个作为测试集。他采用随机森林分类器,使用665作为树的个数,以及其他通过超参优化得到的参数

通过主成分分析处理后,得到从随机序列中区分OEIS序列计算模型的性能指标如下:准确度(accuracy):0.999,精确度(precision):0.9984,召回率(recall):0.9996,F1值:0.9990。

这样的结果令人非常欣喜。这表明了,通过自动化程序识别“有趣”数列是完全可行的。

通过机器学习来识别序列有一个显而易见用途。OEIS背后运营的数学家们目前每年都需要处理大约10,000份序列的提交。所以这种自动化识别有趣序列的方法可能会很有帮助。

但是,这种方法有一些很明显的局限性。数学家们已经定义了很多有趣且重要的无穷大序列,并且这些序列难以计算。因此,OEIS数据库中只涵盖了数列中的一小部分数字。这些只有小部分的序列显然不适合这种基于机器的分析。

更普遍的一个问题是,是否通过这种方式能够定义数学之美?正如Wu所问的:“机器学习能否识别科学知识的定性属性;换句话说,机器是否能够辨别出一项科学结果是否是优雅的,简洁的,或是有趣的?”

这一愿景可能并不完全是没有希望。如果像上问题到的类似福德定律和泰勒定理这样的经验规则可以作为“有趣性”的指标,那么或许这种算法至少在某种程度上,可以被认为是数学之美的仲裁者。

倘若机器学习真能到达这一境界,想必欧拉公式的命名者、也是历史上最伟大的数学家之一——欧拉也会在棺材板里惊讶地坐起来吧~

入门机器学习
相关数据
人脸识别技术
Facial recognition

广义的人脸识别实际包括构建人脸识别系统的一系列相关技术,包括人脸图像采集、人脸定位、人脸识别预处理、身份确认以及身份查找等;而狭义的人脸识别特指通过人脸进行身份确认或者身份查找的技术或系统。 人脸识别是一项热门的计算机技术研究领域,它属于生物特征识别技术,是对生物体(一般特指人)本身的生物特征来区分生物体个体。

机器学习技术
Machine Learning

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

摩尔定律技术
Moore's law

摩尔定律是由英特尔创始人之一戈登·摩尔提出来的。其内容为:积体电路上可容纳的电晶体数目,约每隔两年便会增加一倍;经常被引用的“18个月”,是由英特尔首席执行官大卫·豪斯所说:预计18个月会将芯片的性能提高一倍。

参数技术
parameter

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

主成分分析技术
Principal component analysis

在多元统计分析中,主成分分析(Principal components analysis,PCA)是一种分析、简化数据集的技术。主成分分析经常用于减少数据集的维数,同时保持数据集中的对方差贡献最大的特征。这是通过保留低阶主成分,忽略高阶主成分做到的。这样低阶成分往往能够保留住数据的最重要方面。但是,这也不是一定的,要视具体应用而定。由于主成分分析依赖所给数据,所以数据的准确性对分析结果影响很大。

随机森林技术
Random Forest

在机器学习中,随机森林是一个包含多个决策树的分类器,并且其输出的类别是由个别树输出的类别的众数而定。 Leo Breiman和Adele Cutler发展出推论出随机森林的算法。而"Random Forests"是他们的商标。这个术语是1995年由贝尔实验室的Tin Kam Ho所提出的随机决策森林(random decision forests)而来的。这个方法则是结合Breimans的"Bootstrap aggregating"想法和Ho的"random subspace method" 以建造决策树的集合。

模式识别技术
Pattern Recognition

模式识别(英语:Pattern recognition),就是通过计算机用数学技术方法来研究模式的自动处理和判读。 我们把环境与客体统称为“模式”。 随着计算机技术的发展,人类有可能研究复杂的信息处理过程。 信息处理过程的一个重要形式是生命体对环境及客体的识别。其概念与数据挖掘、机器学习类似。

大数据文摘
大数据文摘

秉承“普及数据思维,传播数据文化,助⼒产业发展”的企业⽂化,我们专注于数据领域的资讯、案例、技术,形成了“媒体+教育+⼈才服务”的良性⽣态,致⼒于打造精准数据科学社区。

大数据文摘
大数据文摘

秉承“普及数据思维,传播数据文化,助⼒产业发展”的企业⽂化,我们专注于数据领域的资讯、案例、技术,形成了“媒体+教育+⼈才服务”的良性⽣态,致⼒于打造精准数据科学社区。

返回顶部