华人学者解开计算机领域30年难题 布尔函数敏感度猜想

近日,美国艾默里大学计算机与数学科学系教授黄皓(Hao Huang)用一篇短短 6 页的论文「轻松」证明了困扰理论计算机领域数十年的布尔函数敏感度猜想,引发了计算机和数学领域社区的广泛关注。布尔函数敏感度猜想是理论计算机科学中近三十年来最重要,最令人困惑的开放性问题之一。

论文长度仅有 6 页,其核心证明内容只有两页,不过黄皓为了解决这个问题花费了 7 年时间的思考。

本月初,一篇仅有 6 页的论文悄悄登上了 arXiv,随之而来的是学界的轰动。这篇由华人学者黄皓所著的研究解决了困扰计算机科学领域的难题:布尔函数的敏感度猜想(sensitivity conjecture),而这篇论文中实际的证明部分只有两页纸。

完成这一壮举的数学家黄皓来自广东汕头,他 2007 年本科毕业于北京大学,博士就读于加州大学洛杉矶分校(UCLA),师从著名数学家 Benny Sudakov 教授。黄皓于 2012 年获得博士学位,2012-2014 年受邀访问普林斯顿高等研究院,现担任美国艾默里大学数学系助理教授。其主要研究领域包括极值组合、图论及理论计算机。已经在 JCTB、JCTA、Combinatorica、SIAM J. Discrete Math 等国际著名期刊上发表及接受发表论文 20 余篇。

布尔函数的敏感度猜想主要涉及计算机电路的基础构造块结构,迄今已快 30 年。在这二十余年中,该猜想难倒了许多优秀的计算机科学家,而黄皓提出的证明方法简单到可以用一篇推文总结:

七年思考,两页证明,华人学者解开计算机领域30年难题:布尔函数敏感度猜想


CMU 计算机科学系教授 Ryan O’Donnell 发推概括了这篇证明。(图源:https://twitter.com/BooleanAnalysis/status/1145837576487612416)

使用有 200 年历史的方法解决了 30 年历史的重量级猜想,有关布尔函数敏感度的证明让我们感受到了数学之美。人们对于黄皓的论证纷纷表示感叹:「这是我们看到过最美丽的两页证明。」

七年思考,两页证明,华人学者解开计算机领域30年难题:布尔函数敏感度猜想

敏感度猜想涉及布尔函数,布尔函数描述如何基于对布尔输入的某种逻辑计算确定布尔值输出,在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。

七年思考,两页证明,华人学者解开计算机领域30年难题:布尔函数敏感度猜想


图源:http://jandan.net/2019/07/13/sensitivity-conjecture.html

这一猜想可以简单表述为:存在一个多项式 P,对所有的布尔函数 f,都成立 bs(f)≤P[s(f)]!

敏感度猜想

法国国家科学研究中心 Claire Mathieu 用生动的例子介绍了布尔函数及其敏感度。

当你在银行贷款申请书上填写一系列 yes/no 问题的时候,填写完之后,银行工作人员将对你的填写结果进行评分,然后告知你是否符合贷款条件。这一过程就是一个布尔函数:你的答案是输入 bit,银行工作人员的决策是输出 bit。

如果你的申请被拒,你可能会觉得如果在回答某一个问题时撒谎是否就可以改变最后的结果,比如在你实际上挣钱数量不超过 5 万美元时却表示超过这一数目。如果该谎言能够改变最终决策结果,那么这一布尔函数就对特定 bit 的值「敏感」。假如有七个不同的谎言每一个都可以导致最终决策结果反转,那么这一布尔函数的敏感度就为 7。

计算机科学家将该布尔函数的敏感度定义为:当查看所有不同贷款资料时所得到的最大敏感度值。某种程度上,它可以计算在模棱两可的情况下多少问题是真正重要的,这些情况包括只要稍微改变即可情况反转的申请。


七年思考,两页证明,华人学者解开计算机领域30年难题:布尔函数敏感度猜想

敏感度通常是最容易计算的复杂度度量指标,但是它并非唯一富有启发性的指标。例如,银行工作人员不让你填写纸质申请,而是进行面谈,先问简单的问题,再根据你的回答进行后续的提问。这时候银行职员在进行决策前需要提问的最大问题数量就是布尔函数的查询复杂度(query complexity)。

这一度量指标在很多场景下都会出现,例如医生在得出诊断结果之前想让病人尽可能少地进行检查,或者机器学习专家想让算法在进行物体分类之前尽可能少地查看物体的特征。「在大量场景中,如诊断场景或学习场景,底层规则的 query 复杂度低是非常值得庆幸的。」O’Donnell 表示。

其他度量包括寻找将布尔函数写为数学表达式的最简单方法,或者说计算银行职员应向上司展示多少个答案,才能证明他们做了正确的贷款决定。这里甚至还有量子物理版本的查询复杂度,即银行职员可以在同一时间询问多个问题的「叠加」。找到这种度量与其他复杂度的关系,可以帮助研究人员了解量子算法的局限性。

除了敏感度之外,计算机科学家已经证明了所有这些度量都是紧密关联的。具体而言,它们之间存在多项式关系——例如一个度量可能大致是另一个度量的平方或立方或平方根。

只有敏感度固执地拒绝适应这种简洁的表示。很多研究人员怀疑敏感度与其他度量之间也存在多项式关系,但人们一直无法证明确实不存在奇特的布尔函数,其敏感度与其他度量具有指数而非多项式关系。这意味着敏感度度量远小于其他度量。

「这一问题已经困扰了人们三十年。」德克萨斯大学奥斯汀分校计算机科学教授 Scott Aaronson 说道。

寻找解法

黄皓在 2012 年末与普林斯顿高等研究院数学家 Michael Saks 共进午餐的时候听闻了敏感度猜想,彼时前者还是一名博士后。他立即被这一猜想的简洁和优雅所吸引了。「从那一刻起,我就开始沉迷于思考这个问题了。」黄皓说道。

黄皓将敏感度猜想加入了他感兴趣问题的「秘密清单」中,每当他学习新的数学工具时,他都会思考这些方法是否会对解决敏感度猜想有所帮助。「每次我发表新的论文之后,我总会回过头来看看这个问题,」黄皓表示。「当然,我也经常在研究一番之后选择放弃,然后回到更为现实的问题上来。」

七年思考,两页证明,华人学者解开计算机领域30年难题:布尔函数敏感度猜想


数学家黄皓在里斯本。

黄皓明白,正如研究社区普遍认为的一样,如果数学家可以证明一个有关不同维度立方体上点集合的猜想,那么敏感度猜想就可以得到解决。从一个 n 个 0 和 1 组成的序列到 n 维立方体上的点有一种自然的方法:只需使用 n 个 bit 作为点的坐标。

例如,有四个两位字符串 00、01、10 和 11,分别对应二维平面中正方形的四个角:(0,0)、(0,1)、(1,0) 和 (1,1)。同样,八个三位字符串分别对应三维立方体的八个角……以此类推。布尔函数可以被认为,用两种不同颜色为这些角进行着色的规则(比如为 0 涂红色,1 涂上蓝色)。

1992 年,现任新泽西理工计算机学院院长 Craig Gotsman 和希伯来大学计算机科学教授 Nati Linial 找出了证明敏感度猜想的思路:通过回答一个有关不同维度立方体的问题将敏感度猜想大大简化,如果你选择将超过一半的立方体尖角同时涂为红色,是否总是有一些红色点是与其他红色点相连接?(在这里,「连接」表示通过立方体的边相连,而不是通过任何对角线。)

如果你选择刚好一半的立方体尖角,则很可能红色点并不会相连接。例如,在三维立方体的八个角中,(0,0,0), (1,1,0), (1,0,1) 和 (0,1,1) 这四个点只是通过对角线相连。但是只要立方体中超过一半的点被涂成红色,那么肯定会出现相连接的红色点。问题在于:这些连接是如何分布的?是否存在一个高度连接的点?

2013 年,黄皓认为理解这一问题的最佳路径是,使用矩阵表示网络(矩阵可以追踪相连的点),并检测矩阵特征值。之后五年,他一直试验这个思路,但都没有成功。

2018 年,黄皓决定使用柯西交错定理(Cauchy interlace theorem),该定理将矩阵特征值和子矩阵特征值关联起来,因此成为研究立方体及其尖角子集的完美工具。黄皓决定向美国国家科学基金会提交申请,以进一步探索这一思路。

随后在上个月,当他坐在马德里的一家旅馆中撰写申请报告时,他突然意识到自己可以通过简单地改变矩阵中一些数字的符号来直接解决问题。通过这种方式,他可以证明在 n 维立方体中超过一半点的任何集合中,会有一些点和其他点有至少√n 个连接,敏感度猜想问题的证明就从这里开始。

当黄皓的论文进入 Claire Mathieu 的收件箱时,她的第一反应是「哦——哇」,她说道:「当一个问题已经存在了 30 年,而每个人都已经听闻过的时候,我们自然认为证明它的方法会看起来冗长而复杂,或者非常高深。」她打开论文并期待看到无法理解的内容。

但是,对于 Mathieu 和其他很多研究者来说,这一证明非常简单,可以一次消化。「我希望在今年的秋天在每个硕士级别的组合数学课程中讲授这一内容——一堂课就够了。」Mathieu 表示。

黄皓的研究结果甚至超过了证明敏感度猜想所需的必要程度,其推理应该可以形成有关复杂度度量的新见解。「它充实了我们的工具库,让我们可以试图回答布尔函数分析中的其他问题。」哥伦比亚大学计算机科学教授 Rocco Servedio 说道。

当然,更重要的是黄皓的结果让那些担忧敏感度可能是复杂度度量世界中的异类的人放心了,Servedio 表示。「我认为在这一证明推出以后,很多人终于能睡得着觉了。」

最后,这里是黄皓对布尔函数敏感度猜想的两页纸证明:

七年思考,两页证明,华人学者解开计算机领域30年难题:布尔函数敏感度猜想

七年思考,两页证明,华人学者解开计算机领域30年难题:布尔函数敏感度猜想

更多详情参见论文《Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture》(https://arxiv.org/pdf/1907.00847.pdf)

mysql索引相关 – 阿里面试经验

相信很多人对于MySQL的索引都不陌生,索引(Index)是帮助MySQL高效获取数据的数据结构。

因为索引是MySQL中比较重点的知识,相信很多人都有一定的了解,尤其是在面试中出现的频率特别高。楼主自认为自己对MySQL的索引相关知识有很多了解,而且因为最近在找工作面试,所以单独复习了很多关于索引的知识。

但是,我还是图样图森破,直到我被阿里的面试官虐过之后我才知道,自己在索引方面的知识,只是个小学生水平。

以下,是我总结的一次阿里面试中关于索引有关的问题以及知识点。

索引概念、索引模型
我们是怎么聊到索引的呢,是因为我提到我们的业务量比较大,每天大概有几百万的新数据生成,于是有了以下对话:

面试官:你们每天这么大的数据量,都是保存在关系型数据库中吗?

我:是的,我们线上使用的是MySQL数据库

面试官:每天几百万数据,一个月就是几千万了,那你们有没有对于查询做一些优化呢?

我:我们在数据库中创建了一些索引(我现在非常后悔我当时说了这句话)。

这里可以看到,阿里的面试官并不会像有一些公司一样拿着题库一道一道的问,而是会根据面试者做过的事情以及面试过程中的一些内容进行展开。

面试官:那你能说说什么是索引吗?

我:(这道题肯定难不住我啊)索引其实是一种数据结构,能够帮助我们快速的检索数据库中的数据。

面试官:那么索引具体采用的哪种数据结构呢?

我:(这道题我也背过)常见的MySQL主要有两种结构:Hash索引和B+ Tree索引,我们使用的是InnoDB引擎,默认的是B+树。

这里我耍了一个小心机,特意说了一下索引和存储引擎有关。希望面试官可以问我一些关于存储引擎的问题。

面试官:既然你提到InnoDB使用的B+ Tree的索引模型,那么你知道为什么采用B+ 树吗?这和Hash索引比较起来有什么优缺点吗?

我:(突然觉得这道题有点难,但是我还是凭借着自己的知识储备简单的回答上一些)因为Hash索引底层是哈希表,哈希表是一种以key-value存储数据的结构,所以多个数据在存储关系上是完全没有任何顺序关系的,所以,对于区间查询是无法直接通过索引查询的,就需要全表扫描。所以,哈希索引只适用于等值查询的场景。而B+ Tree是一种多路平衡查询树,所以他的节点是天然有序的(左子节点小于父节点、父节点小于右子节点),所以对于范围查询的时候不需要做全表扫描。

面试官:除了上面这个范围查询的,你还能说出其他的一些区别吗?

我:(这个题我回答的不好,事后百度了一下)

科普时间:B+ Tree索引和Hash索引区别 哈希索引适合等值查询,但是不无法进行范围查询 哈希索引没办法利用索引完成排序 哈希索引不支持多列联合索引的最左匹配规则 如果有大量重复键值得情况下,哈希索引的效率会很低,因为存在哈希碰撞问题

聚簇索引、覆盖索引
面试官:刚刚我们聊到B+ Tree ,那你知道B+ Tree的叶子节点都可以存哪些东西吗?

我:InnoDB的B+ Tree可能存储的是整行数据,也有可能是主键的值。

面试官:那这两者有什么区别吗? 我:(当他问我叶子节点的时候,其实我就猜到他可能要问我聚簇索引和非聚簇索引了)在 InnoDB 里,索引B+ Tree的叶子节点存储了整行数据的是主键索引,也被称之为聚簇索引。而索引B+ Tree的叶子节点存储了主键的值的是非主键索引,也被称之为非聚簇索引。
面试官:那么,聚簇索引和非聚簇索引,在查询数据的时候有区别吗?

我:聚簇索引查询会更快?

面试官:为什么呢?

我:因为主键索引树的叶子节点直接就是我们要查询的整行数据了。而非主键索引的叶子节点是主键的值,查到主键的值以后,还需要再通过主键的值再进行一次查询。

面试官:刚刚你提到主键索引查询只会查一次,而非主键索引需要回表查询多次。(后来我才知道,原来这个过程叫做回表)是所有情况都是这样的吗?非主键索引一定会查询多次吗?

我:(额、这个问题我回答的不好,后来我自己查资料才知道,通过覆盖索引也可以只查询一次)

科普时间——覆盖索引 覆盖索引(covering index)指一个查询语句的执行只用从索引中就能够取得,不必从数据表中读取。也可以称之为实现了索引覆盖。 当一条查询语句符合覆盖索引条件时,MySQL只需要通过索引就可以返回查询所需要的数据,这样避免了查到索引后再返回表操作,减少I/O提高效率。 如,表covering_index_sample中有一个普通索引 idx_key1_key2(key1,key2)。当我们通过SQL语句:select key2 from covering_index_sample where key1 = ‘keytest’;的时候,就可以通过覆盖索引查询,无需回表。

联合索引、最左前缀匹配
面试官:不知道的话没关系,想问一下,你们在创建索引的时候都会考虑哪些因素呢?

我:我们一般对于查询概率比较高,经常作为where条件的字段设置索引

面试官:那你们有用过联合索引吗?

我:用过呀,我们有对一些表中创建过联合索引。

面试官:那你们在创建联合索引的时候,需要做联合索引多个字段之间顺序你们是如何选择的呢?

我:我们把识别度最高的字段放到最前面。

面试官:为什么这么做呢?

我:(这个问题有点把我问蒙了,稍微有些慌乱)这样的话可能命中率会高一点吧。。。

面试官:那你知道最左前缀匹配吗?

我:(我突然想起来原来面试官是想问这个,怪自己刚刚为什么就没想到这个呢。)哦哦哦。您刚刚问的是这个意思啊,在创建多列索引时,我们根据业务需求,where子句中使用最频繁的一列放在最左边,因为MySQL索引查询会遵循最左前缀匹配的原则,即最左优先,在检索数据时从联合索引的最左边开始匹配。所以当我们创建一个联合索引的时候,如(key1,key2,key3),相当于创建了(key1)、(key1,key2)和(key1,key2,key3)三个索引,这就是最左匹配原则。

虽然我一开始有点懵,没有联想到最左前缀匹配,但是面试官还是引导了我。很友善。

索引下推、查询优化
面试官:你们线上用的MySQL是哪个版本啊呢?

我:我们MySQL是5.7

面试官:那你知道在MySQL 5.6中,对索引做了哪些优化吗?

我:不好意思,这个我没有去了解过。(事后我查了一下,有一个比较重要的 :Index Condition Pushdown Optimization)

科普时间—— Index Condition Pushdown(索引下推) MySQL 5.6引入了索引下推优化,默认开启,使用SET optimizer_switch = ‘index_condition_pushdown=off’;可以将其关闭。官方文档中给的例子和解释如下: people表中(zipcode,lastname,firstname)构成一个索引

SELECT * FROM people WHERE zipcode=‘95054’ AND lastname LIKE ‘%etrunia%’ AND address LIKE ‘%Main Street%’;

如果没有使用索引下推技术,则MySQL会通过zipcode=’95054’从存储引擎中查询对应的数据,返回到MySQL服务端,然后MySQL服务端基于lastname LIKE ‘%etrunia%’和address LIKE ‘%Main Street%’来判断数据是否符合条件。 如果使用了索引下推技术,则MYSQL首先会返回符合zipcode=’95054’的索引,然后根据lastname LIKE ‘%etrunia%’和address LIKE ‘%Main Street%’来判断索引是否符合条件。如果符合条件,则根据该索引来定位对应的数据,如果不符合,则直接reject掉。 有了索引下推优化,可以在有like条件查询的情况下,减少回表次数。

面试官:你们创建的那么多索引,到底有没有生效,或者说你们的SQL语句有没有使用索引查询你们有统计过吗?

我:这个还没有统计过,除非遇到慢SQL的时候我们才会去排查

面试官:那排查的时候,有什么手段可以知道有没有走索引查询呢?

我:可以通过explain查看sql语句的执行计划,通过执行计划来分析索引使用情况

面试官:那什么情况下会发生明明创建了索引,但是执行的时候并没有通过索引呢?

我:(依稀记得和优化器有关,但是这个问题并没有回答好)

科普时间——查询优化器 一条SQL语句的查询,可以有不同的执行方案,至于最终选择哪种方案,需要通过优化器进行选择,选择执行成本最低的方案。 在一条单表查询语句真正执行之前,MySQL的查询优化器会找出执行该语句所有可能使用的方案,对比之后找出成本最低的方案。这个成本最低的方案就是所谓的执行计划。 优化过程大致如下: 1、根据搜索条件,找出所有可能使用的索引 2、计算全表扫描的代价 3、计算使用不同索引执行查询的代价 4、对比各种执行方案的代价,找出成本最低的那一个

面试官:哦,索引有关的知识我们暂时就问这么多吧。你们线上数据的事务隔离级别是什么呀?

我:(后面关于事务隔离级别的问题了,就不展开了)

感觉是因为我回答的不够好,如果这几个索引问题我都会的话,他还会追问更多,恐怕会被虐的更惨

总结&感悟
以上,就是一次面试中关于索引部分知识的问题以及我整理的答案。感觉这次面试过程中关于索引的知识,自己大概能够回答的内容占70%左右,但是自信完全答对的内容只占50%左右,看来自己索引有关的知识了解的还是不够多。

通过这次面试,发现像阿里这种大厂对于底层知识还是比较看重的,我以前以为关于索引最多也就问一下Hash和B+有什么区别,没想到最后都能问到查询优化器上面。

最后,不管本次面试能不能通过,都非常感谢有这样一次机会,可以让自己看到自己的不足。通过这次面试,我也收获了很多东西。加油!

蜘蛛采集频率过高怎么办

网站开发者,站长都很喜欢蜘蛛,有蜘蛛爬取才会有收录。如果不想被收录或者被大量爬取而毫无收录,直接robots里屏蔽掉该蜘蛛,或者用web服务器写几条禁用的规则就好了。

还有一种情况是正常抓取,但是抓取频率实在太高。而一般的开发者买的服务器,应该都是比较廉价的。超高的抓取频率,影响了网站的正常访问,甚至有可能因为CPU占用过高被服务商suspend里主机。开了缓存更是灾难,说不定一两天就inode用完导致服务器无法正常运行。

那么我们怎么去限制抓取频率呢。搜索引擎提供了限制功能,谷歌最近又取消了该功能,但是写的是蜘蛛会自动调节抓取频率。实际没有那么智能。而国内的搜索引擎实名绑定各种繁琐,最后设置了还不一定有效。最简单的办法当然还是自己用代码解决。

nginx和apache有插件可以直接根据IP限制访问频率。

自己用网页后台语言实现也很简单。不同语言实现不一样,但是原理很简单

判断条件 同一个蜘蛛,或者IP,或者不判断蜘蛛和IP,直接判断网站被访问的频率,甚至时间段什么的
满足条件 直接返回500,或者503的网页状态即可。