陆品燕 上海财经大学理论计算机科学研究中心 主任

淘宝排名的算法有什么问题?理论计算机牛人告诉你真相

造就 TALK · 2018-04-17 · 19:18:52

造就第284位讲者 陆品燕

上海财经大学理论计算机科学研究中心主任

屏幕快照 2018-04-13 下午3.48.26.png

我的研究方向是理论计算机。每次我跟别人说自己的专业时,大家都会问我一个问题:你是做硬件还是软件?

我每次都非常尴尬。因为我既不是做硬件的,也不是做软件的。大学毕业后十几年,我就没有写过程序。我们日常的工作,只要一张纸、一只笔就可以了。

理论计算机的关键词不在计算机,而在计算。我们关注的是计算的理论。

大家可能前两年看过一个电影,叫《模仿游戏》。电影就是以计算理论的祖师爷——图灵的生平作为原型。

图灵在1936年的一篇论文中精确地定义了什么叫计算。这样的精确定义有什么意义呢?

屏幕快照 2018-04-13 下午3.52.02.png

一方面,从他原始的初衷来说,有了这样精确的定义,就可以证明什么东西是不能计算的。

另外一方面的意义可能对我们的影响更大。现代计算机就是在图灵机这样的数学模型基础上造出来的。虽然计算机已经被发明出来了,但计算的理论还是沿着自身的逻辑发展,继续研究计算的真相。

什么是计算的真相呢?

简单来说,就是我们计算的能力到了什么程度?计算的极限又在哪里?什么是可以计算的?什么是不能计算的?什么是容易计算的?什么是不容易计算的?

计算的普适性

计算其实是无处不在的。从最深刻最基础的数学到最酷最炫的信息科技应用;从最客观的自然科学,到我们日常生活中的社会、经济行为。计算与它们都有着非常广泛而本质的联系。

非常幸运,我本人的研究方向恰好与数学、科学、技术、经济学这四个纬度都有交叉。所以,我的朋友和合作者中既有数学家、物理学家、经济学家、也有计算机应用科学的学者以及一线的程序员和工程师们。

其实这四类人是非常不一样的,他们之间使用的语言和关注的东西都很不一样,彼此很难对话。但是,他们跟我都对话得很好,合作得很好。我觉得这也从一个角度论证了计算思维的普适性。

_HAN5722.JPG

在计算与数学、科学、技术、经济学这四个方向的联系中,大家对计算与科学、技术的联系相对好理解一些。

比如它与科学方面的联系。现在最火的技术叫量子信息与量子计算,就是计算与物理学的结合。现在这个领域特别火。不仅各国政府投入了很多资金,很多高科技企业也加入了。就在最近这短短的一年左右,BAT先后成立了量子计算与量子信息的实验室。

计算与技术的结合就更不用说了。现在的高科技都是以计算机科学的技术为基本支撑的。包括大家说得特别多的人工智能技术、区块链技术等等。

不过我今天最想讲的,是计算与数学、经济学的联系。

你能证明一个问题是无解的吗?

让我们从数学开始。德国伟大的数学家希尔伯特有一个很重要的贡献。他在1900年巴黎国际数学家大会上,提出了23个数学问题。这23个问题涉及数学非常多不同的方向,很大程度上引导了整个21世纪数学的发展。

屏幕快照 2018-04-13 下午3.59.52.png

后来很多人试图解答他的这23个问题,从而发展出了很多新的数学理论和工具。其中有一些到现在还没有解出来。

我们今天要讲的是他的第10个问题。第10个问题,大家非常好理解,尤其对小时候学过奥数或者有孩子在学奥数的人来说,很好理解。

就是随便给你一个方程,让你回答这个方程有没有整数解?(编者按:即不定方程可解性)

前段时间,有个特殊的方程在我的朋友圈里刷屏了。

屏幕快照 2018-04-13 下午4.01.57.png

这个方程看起来非常简洁,也没有什么特殊的。问题是存不存在三个正整数ABC使得这个方程成立。

这题为什么很有趣呢?

因为这样的正整数确实是存在的,但如果你去算一下的话,我相信你不会很快算出来。因为它最小的一个正整数解是长这个样子的。具体多少位我也没数过。

从这个例子,大家可以看出。不是所有的问题都可以通过输入方程,就能把解给找出来。

就像希尔伯特第10问题,虽然已经有了答案,但结果却不是希尔伯特所希望的。希尔伯特希望找出一个通用的方法。但我们通过计算理论证明了通用方法是不存在的。不存在一个算法,可以给你一个方程,就能确定地找到一个解。

这样一种否定性的回答,有时候在数学中反而具有更加深刻的意义。

计算的理论现在已经发展得很成熟了。我们大家已经知道,哪些问题是可以算的,哪些问题是不能算的。

现在,计算理论关注的焦点已经从能不能算发展到了难不难算。也就是计算的复杂性问题。

屏幕快照 2018-04-13 下午4.05.39.png

计算复杂性怎么理解?意思是我们要用多长时间来把这个问题给算出来。

我们再举一个奥赛题。这是一张纸,上面有一张图。你沿着图上的线画,但是同一条线不能画两次,你能不能把这个图一笔画出来?

如果尝试所有的画法,需要很久;如果这个图再大一点,就更麻烦了。有没有一个简便的方法呢?

我想很多人会知道这个简便的方法。那就是你看每一个点连接的线是奇数条还是偶数条。偶数条我们就叫偶点,奇数条叫奇点。如果一个图的奇点数不超过2的话,这个图就是可以一笔画的。

有了这样一个简单的辨别方法,即使这个图里有几百个点,你也能很快判断出能不能一笔画完。

如果我把这个题稍微换一下,说图中的每个点都不能重复呢?就好比这是一个游览图,每个点代表一个景点,你能不能把所有的景点没有重复地游览一遍?

这个问题在数学上称为哈密尔顿道路问题。当然你可以把所有可能的路线图都走一遍。但如果这个图的点数超过几百的话,即使用现代最先进的电脑,要穷举所有的可能性,也无法在我们的有生之年看到结果。因为所需要的时间实在太长了。

那么有没有一个像一笔画一样的简便方法?这个问题不仅奥数老师没有教过,现在所有的数学家也都不知道。

屏幕快照 2018-04-13 下午4.02.44.png

它是21世纪七大数学难题之一。如果你能够找到这样一个简便方法,你就可以获得一百万美金的奖金。如果你能证明这个方法不存在,同样可以获得这一百万美金。

哈密尔顿问题并不是孤立存在的。这世上,有成千上万个问题,虽然看起来不一样,但在计算复杂性这件事情上却是等价的。等价的意思就是说,如果你找到其中一个问题的简便方法,那么,这成千上万的问题,你都找到了一个简便方法。所以计算复杂性是当今理论计算机科学焦点之一。

我们的目标就是根据计算复杂性把问题进行区分。

像我自己证明了很多二分定理。二分定理的意思就是:所有在一个框里可以描述的问题,我要把它完全地区分出哪些是难的,哪些是不难的。

算法不是无所不能的

讲完计算理论与数学结合,我们再来讲它与经济学的联系。

我们举一个大家比较容易理解的例子——淘宝。

屏幕快照 2018-04-13 下午4.06.16.png

在淘宝中,你输入一个关键词,它会推荐一些商品和商家。

从淘宝的角度来说,它希望为用户提供最好的体验,所以会尽量把它认为优质的商品与商家推荐给你。那如何评价商品与商家呢?淘宝用了一系列参数,比如商家的历史销量、用户评价等等,然后根据这些参数进行排名。

排名对每一个商家来说很重要。如果被排在在前面的话,商品被购买的可能性就会大很多。

所以,很多商家就会用虚假交易的方式来刷销量、刷评价,让自己排名靠前。

如果很多商家都这样做,用户的体验就不好了。从计算的视角来看,淘宝运行一个算法,希望给用户好的体验。但是因为这些数据的生产者是商家,而商家又有各自的利益。它的利益是希望自己的收益最好,而不是希望整体用户的体验最好。

就在这样的过程中,算法有其限制性。也就是说,输入的数据并不是完全可控的。这时候,计算的极限的分界点其实就发生了变化。

为了解释得更具体,举一个我自己科研中的例子。这是一个最优拍卖机制的设计。

大家可能都知道拍卖。大到开发商拍地,小到在淘宝网上拍卖,甚至大家常说的搜索引擎关键词的竞价排名,都是用的拍卖方式。

IMG_5673.JPG

拍卖是经济学中非常重要的一个行为,也有很多关于设置最优拍卖机制的研究。但经济学的研究一般都基于这样的假设:拍卖者知道大家对拍卖品的估价大概是处在什么样的分布水平。

这种情况在互联网时代变得越来越不现实。因为互联网上卖的很多东西,比如竞价排名,你是不可能对每一个网友做市场调查的。

所以原来的经济学理论很难在现实中适用。为了改变这个问题,理论计算机科学家在2001年基于竞争比的概念,提出了新的最优拍卖机制模型。它概念是说,如果竞争比的数值越小,拍卖机制期望的收益就会越好。因此对于卖家来说,竞争比越小越好。

而2001年提出的最优拍卖机制,它的竞争比非常大的,是一个大于100的常数。之后有好多不同的经济学家、数学家、计算机科学家试图设计更好的机制来改进这个竞争比。之前改进到最好的是3.12。

屏幕快照 2018-04-13 下午4.05.13.png

这个改进是不是无止尽的?有没有一个极限呢?2004年,有科学家证明这个数不能变得比2.42还小。但是,从3.12到2.42怎么做到不知道。

于是,我和我的两个合作者一起证明了,存在一个拍卖机制,竞争比就是2.42。那么,这就是一个最优的拍卖机制。

淘宝的排名与拍卖机制的设计催生一个新的学科——计算经济学。

屏幕快照 2018-04-13 下午4.07.11.png

这个学科包含的领域其实非常广,包括像市场价格的预测、市场平衡的计算等等问题。这些问题原来在经济学中也有很多研究,但当市场越来越大的时候,关于计算的复杂性成为新经济学中的一个新的约束。

算法创造更好的未来

我们讲到了计算理论与数学、科学、经济学、技术的关系。可以看到:

计算理论与数学的结合体现了理论的深刻性;

在与科学的结合中,我们发现关于计算的概念真的出现在物理的世界中,并且影响着宇宙运行的规律,所以是真实的;

它与经济学的结合,可以看到它的普适性;

而当我们看到以计算机科学为基础的信息科技,正以前所未有的程度改变着我们整个生活和生产的方式时,再一次证明了这些计算工具的有用性。

屏幕快照 2018-04-13 下午4.07.23.png

深刻、真实、普适、有用,这就是我眼中的计算思维和计算原理,也是我十几年来一直醉心于这个学科的原因。

我相信通过计算的视角,我们可以更好地理解这个世界;通过计算这个工具,我们也可以去更好地改造我们的世界,创造更加美好的未来。

文/汉岚

  • 算法
  • 理论计算机
19:52
陈静 南京大学艺术研究院 副教授

如果每个人都变成了机器,那么还需要分男女么?

2018-04-18
25:01
冯家妹 歌手 演员

凡杀不死你的,终将使你更坚强

2018-06-11

造就评论0

造就  发现创造力