财新传媒

比你更了解你:算法已经无可匹敌了吗?

2017年08月22日 13:11 来源于 财新网
可以听文章啦!
21世纪的计算机算法早已像空气般浸染你的生活

  撰文 | 叶伟民

  我常去硅谷孵化器YCombinator的黑客留言板,尽管从不发言。那里的人实在太聪明了,教会我很多道理。例如如何用“高斯绝妙定理”[1]正确拿一块比萨。

  这实在太好了。我再也不用为耷拉下来的比萨发愁了(馅儿会掉),学会卷着拿,精准地送到嘴里。这种感觉很棒,就像一个外国人学会了拿筷子夹花生。

  除了高斯,黑客们的超级明星还有乔治·布尔,他们的理论(高斯函数[2]、布尔逻辑[3])和更多数学分支,成就了今天的算法世界。

  黑客笔下的算法看似神秘莫测,实则相当广泛和寻常。只要我们有待解决的问题,又存在行之有效的方案,这个方案就是算法。例如,麦当劳的烹饪流程就是一个算法,它能保证北京国贸的薯条和纽约曼哈顿的口味一致。

  21世纪的计算机算法早已像空气般浸染你的生活:你出门,它为你精准调度地铁;你登录购物网站,弹窗推送你搜索过的商品;你是球迷,资讯软件又很懂事地将联赛排名放在首页。当你迫不及待地要回家抱刚打完架的儿子,算法又在打车软件里又为你安排车辆和规划路线。

  即使你没有任何麻烦,只是莫名沮丧,算法也有办法抚慰你。你可以打开一本叫《阳光失去了玻璃窗》的诗集,作者是微软小冰。这个少女形象的智能机器人,已入侵人类引以为傲的精神领地——文学。它深度学习了1920年以来519位诗人的现代诗,笔触充满人类的温度。粉丝们都喜欢它,还寄去了晚礼服。

  我想领教小冰的聪明,在其社交账号提问:“你怎么看待算法?”小冰回答:“lz(楼主)应该用数学的概率来看待问题。”

  算法的基础之一的确是数学,而且走得相当艰难。以数学演算为形式的传统算法进化了2000多年,到18世纪才有所飞跃——二进制出现了,发明者是德国数学家莱布尼茨。他运气不好,在微积分发明权的争夺中上输给牛顿,但脑洞却大得多——他萌生了制造智能机器的想法,还设计出第一台能做加减乘除的机械计算器。

  此后200多年,随着高斯函数、概率论[4]、图论[5]、布尔逻辑及更多数学分支的发展,1930年代,现代算法呼之欲出——二进制电子电路问世了。一个叫克劳德·香农的麻省理工研究生试着把二进制和布尔逻辑结合写进电子电路,发现能解决数学难题,存储数据,编辑图像和文字。

  1946年,世界上第一台计算机“埃尼阿克”在美国问世。它重30吨,却一点也不笨——能用20秒计算出炮弹的轨道。从此,算法走出古典数学家的演算纸,进入计算机时代。科学家们发现,算法与计算机太匹配了。

  “计算机有难以置信的运算速度,对执行重复性任务非常合适。”英国格拉斯哥大学计算机科学家帕特里克·普罗瑟说,“这些任务被明确定义,并可用有限的时间来完成。”

  “非常优美,我很欣赏”

  虽然高斯的定理教会了我吃比萨,但我的问题仍不少,例如体重。如果我继续放任,体脂率就会超过23%。这是一个测量软件告诉我的,而我太太喜爱的影星彭于晏的体脂率号称曾低至3%。

  数字量化了沮丧感。听说我要立志减肥,一个朋友露出数据主义者的严苛。他指挥我买手环、智能体重计及下载一些运动健身的应用。

  这些终端告诉我很多身体的秘密——例如我坐地铁上下班一天要走6300步,打车的话就只能走3500步了;我的心率有时候每分钟72次,有时候又96次;我的睡眠不太好,每天深睡时间只有2小时;我决定去跑步,又遭到了计步器的嘲笑,我20分钟跑不到3000米,和大长腿走快点差不多……

  要知道,我17年前可是学院的800米冠军,这些数字着实让我不知所措。但算法知道。它们分析我的身体状况,计算我消耗的卡路里,推荐食谱和运动任务。

  算法研究了我,那我的数据会去哪里呢?我的朋友Eric是波士顿一家可穿戴设备公司的首席工程师,他向我解释:被测量者的数据会变成数字或模拟信号,传输回各个设备供应商的数据库中。各种开源算法日夜辛劳,像矿工从砂岩中淘洗黄金一样——某个地区肥胖人数上升或失眠症爆发,无论对商业公司还是卫生系统都是非常宝贵的情报。 

  工程师们告诉我,数据处理的算法有很多,排序是最基础也是最重要的一环。

  如果把算法比作一个拳师,排序问题就是他打出的第一拳。计算机算法史上最具标志性的排序算法——冒泡算法诞生于1963年。两名加州的计算机科学家发明了它,并赋予简单优美的运行逻辑——把待排序数列从头开始依次两两对比,按大小调至正确顺序,然后不断重复上述流程直至没有数字交换为止。

  “非常优美,我很欣赏。”帕特里克·普罗瑟说。然而,冒泡排序本质上是一种暴力求解,当数据量大时就吃力了。科学家们继续发明新的排序算法。“博弈论之父”约翰·冯·诺依曼也来小试牛刀,他发明了归并排序。

  与冒泡算法相比,归并法多了“分治”思维,先让不同子序列有序,再将子序列合并排序,最终得到完全有序,极大提高了运算效率。

  “研究算法的美妙之处,是追求最大限度的优雅和高效。”英国格拉斯哥大学计算机高级讲师大卫·曼罗夫说。如今,仅排序算法领域,已经衍生出20多种算法。

  求婚算法

  还是说回我的体重吧。我变成这样咎由自取,手机里的美食搜索软件和外卖应用都被我置顶。有两类基础算法在忠诚地为我服务:排序算法和路径选择算法。

  正常的人机配合过程应该是这样的:我发出指令——搜索离我最近的咖啡厅。排序算法先把城市所有咖啡厅找出来,按距离排序,给出推荐结果。我接受后,路径选择算法就会计算出最优交通方案,最后我跟着箭头走就是了。

  如果这件事发生在北京这样的特大城市,计算过程就会变得异常漫长,因为数据量太大了。人类不会愚蠢到让自己饿死在搜索过程中,科学家们又创造“预处理”来优化算法——把城市分成若干“格子”,根据用户的位置落在哪个格子内,只对其范围内的咖啡厅按距离排序即可。

  上述的“预处理”就是人脑对算法的优化。在算法的发展问题上,存在两种认知:一种认为应优先发展硬件;一种则倾向优化算法。前Google全球副总裁李开复更支持后者。在一篇文章中,他写到:“(相比计算能力)需要处理的信息量更是呈指数级的增长……越来越多的挑战需要靠卓越的算法来解决。”

  2012年诺贝尔经济学奖就是因为一个卓越的算法——“盖尔-沙普利算法”[6],授予一位数学家。当时,两位发明者中,盖尔已故,沙普利也89岁了。他和中国有缘,年轻时参加美军到中国抗日。

  “我自认为是个数学家,却拿了个经济学的奖。”获奖后,沙普利这样说。

  这个收获最高殊荣的算法,本质是解决匹配问题,但起源有些喜感。1960年,两位发明者就婚姻问题有了一次争论——择偶意愿存在交叠的几对男女,能否最后匹配成稳定的婚姻?

  他们聊到最后,觉得可行,而且还可以有更多应用。1962年,他们合写了一篇论文《高校招生与婚姻稳定性》,“盖尔-沙普利算法”问世。

  该算法的关键在于“延迟接受”——学生对合意的学校要约不要立即接受(不合意的则拒绝),而是“抓住”。等要约被拒绝后,学校才可以向另一名学生发出新的要约。整个程序一直持续到没有学校再希望发出新的要约为止。学生们从各自“抓住”的要约中选择,保证最终结果的相对最优。

  “盖尔-沙普利算法”也成为博弈论早期的重要分支,但人们更愿意叫它为“求婚算法”。 

  算法的局限

  算法已经走了多远?这个问题没有人比Google更合适回答了。

  19年前,斯坦福计算机研究生拉里·佩奇和谢尔盖·布林住进加州一个车库。他们打算设计一个搜索引擎,帮助人们更有效地搜寻万维网信息。他们一无所有,只有在宿舍发明的PageRank(网页排名算法)。

  当时市面上已有的搜索引擎非常简单粗暴,仅以网页点击数排名。两位创始人把他们对搜索的理解写进PageRank,主要基于两个假设:一是数量假设,一个页面接收到其他网页指向的入链数量越多,这个页面就越重要;再是质量假设,指向页面的其他网页的入链质量越高,页面越重要。

  PageRank开创性地提出“链接价值”概念,让搜索引擎从单纯的“计数”飞跃到对网页重要性的评价。PageRank成为Google创业期最核心的算法,不断优化沿用至今。

  如今,Google帝国的技术已无比强大。GFS、MapReduce、BigTable、Caffeine、Pregel、Dremel[7]等技术,已成为全球云计算及大数据技术的基石。

  值得一提的是MapReduce算法。Google每天能经受住55亿次搜索的冲击,它劳苦功高。

  MapReduce算法原理既精妙又质朴,通过把计算量分配给不同的计算机群,并行分布式自动执行。简单地说,就是将复杂任务分解“外包”给全球大大小小的计算机,各自运算,最后汇总解决。“借助该算法,Google几乎能无限地增加计算量。”李开复评价。

  如今,算法已抵达机器学习和人工智能的前沿。Google的人工智能程序“AlphaGo”横扫中韩围棋高手。中国的柯洁也在其中,承认对方是“围棋上帝”。

  那算法已经无可匹敌了吗?

  “我认为人们并不真正了解算法的局限。”牛津大学计算机教授莱斯利·安·高柏说,“有的问题根本无法通过有效算法解决。”

  最著名的莫过于“旅行推销员问题”了。即一个推销员要拜访N个城市,每个城市只经过一次,最终回到出发地,要用算法快速选出最短路线。

  这个问题难住了全球科学家。计算量太大了,当城市达到10个时,可能路线就已超过180万条,每增加1个城市,可能路线还会几何级数增长。暴力穷举的话,时间会长得不可接受。

  2000年,美国克雷数学研究所悬赏100万美元征求算法[8]。如今,这笔奖金已经躺了17年了。

  在沿着算法进化的河流回览之后,下一篇文章我将带你们看看算法更近在眼前的影响——“过滤泡泡”。无处不在的推荐算法让我们更高效获取信息的同时,也让我们变得更狭隘。我将与大家一起探寻:是什么让开放和封闭成为同一个硬币的两面?

  关于作者

  叶伟民,媒体人。毕业于兰州大学核物理专业。曾任ZAKER总编辑,南方周末特稿编辑、记者。现从事互联网,同时是多家平台的签约作者和写作导师。

  注释:

  [1] 高斯绝妙定理:表达高斯曲率的一个定理,是高斯方程的直接推论。它的发现是微分几何学发展史上的一个里程碑。

  [2] 高斯函数:被广泛运用于统计学以描述正态分布,应用范围涵盖自然科学、社会科学、数学以及工程学等领域。

  [3] 布尔逻辑:19世纪中叶乔治·布尔首次定义了逻辑的代数系统。布尔逻辑在电子学、计算机硬件和软件中有广泛应用。

  [4] 概率论:研究随机现象数量规律的数学分支,广泛应用于自然科学、经济学、医学、金融保险甚至人文科学中。

  [5] 图论:通过图形来描述某些事物之间的某种特定关系,是“拓扑学”的先声。

  [6] 盖尔-沙普利算法:也被称为“延迟接受算法”,是盖尔和沙普利为了寻找一个稳定匹配而设计出的市场机制。两位发明者都是数学家和经济学家,戴维·盖尔是加州大学伯克利分校教授,罗伊德·沙普利是加州大学洛杉矶分校教授。

  [7] GFS:Google文件系统,MapReduce:超大集群的简单数据处理,BigTable:结构化数据的分布式存储系统,Caffeine:新索引系统,Pregel:图算法引擎,Dremel:“交互式”数据分析系统。

  [8] 克雷数学研究所在2000年宣布,为世界七大数学难题各悬赏100万美元奖金。它们是:NP完全问题、霍奇猜想、庞加莱猜想、黎曼假设、杨-米尔斯存在性和质量缺口、纳卫尔-斯托可方程、BSD猜想。“旅行推销员问题”是最经典的“NP完全问题”之一。

  《知识分子》是由饶毅、鲁白、谢宇三位学者创办的移动新媒体平台,致力于关注科学、人文、思想

1

责任编辑:于达维 | 版面编辑:张柘
文章很值,赞赏激励一下
赞 赏
首席赞赏官虚位以待
赞赏是一种态度
  • 1
  • 3
  • 6
  • 12
  • 50
  • 108
其他金额
金额(元):
赞 赏
财新传媒版权所有。
如需刊登转载请点击右侧按钮,提交相关信息。经确认即可刊登转载。
推广

财新私房课
好课推荐

2017年09月24日    22:37
【“曲线”买卖壳暗涌潜行 监管保持紧盯态势】随着二级市场行情回暖,不少壳主正计划趁着股价处于阶段高位,通过转让股权的手段“曲线”卖壳,围绕控制权变更的壳生意正在暗涌潜行。与此同时,控制权变更带来的卖壳预期传导至整个二级市场,形成了以ST板块为主的壳股炒作行情。值得注意的是,监管层对大比例股权转让一直保持紧盯态势。随着监管层对重组借壳的进一步严格监管,加上退市制度的进一步完善,未来壳资源价值将越来越低,大规模借壳及炒壳热潮难以再现。(中证)
2017年09月24日    22:00
【董明珠回应举牌海立股份:格力产能不够 需要大量采购海立的压缩机】格力电器举牌海立股份引发资本市场关注。针对举牌一事,格力电器董事长董明珠在接受央视采访时表示,格力过去一直是海立的一个大户,一年用它的压缩机有六七百万台,格力自身本身也有几千万产能,格力远远是不够的,所以还要大量采购它的压缩机。在这过程中,格力也发现还有技术的东西,(海立股份)有这个想法,愿意把这个股份出让,那我觉得格力正好可以去接盘。
2017年09月24日    21:07
【科技部:全国技术合同成交额已突破万亿大关】科技部政策法规与监督司副司长张炳清表示,企业是技术创新主体,当前中国正在深入实施创新驱动发展战略,深化供给侧结构性改革,培育壮大新动能,加快新旧动能的转化。在这一过程中必须不断强化企业创新的主体地位。(上证报)
2017年09月24日    20:53
【海伦哲:预计前三季度净利同比增长102.80%-131.36%】预计2017年前三季度实现盈利7100万元–8100万元,同比增长102.80%-131.36%,公司上年同期盈利3501万元。业绩增长主要因公司7月获国家电网4亿余元的订单陆续交付;子公司巨能伟业及深圳连硕自动化并购协同效应体现,业绩持续稳步增长。
2017年09月24日    20:49
【达威股份:股东减持公司股份总数累计达到1%】公司持股5%以上股东吴冬梅女士在09月14日至09月21日期间,共计减持其持有的公司无限售流通股85.72万股。吴冬梅女士通过证券交易系统减持公司股份总数累计达到1%。减持完成后其还持有15.28%股份。
2017年09月24日    20:43
【苏试试验:拟8000万收购台科视讯98%的股权】公司与周晓英、夏红干、薛承财签署《关于台科视讯系统(苏州)有 限公司之股权转让合同》,公司拟收购台科视讯系统(苏州)有限公司98%的股权,标的资产的价格确定为8,036.00万元(含税价)。
2017年09月24日    20:39
【深振业A:停牌事项构成重大资产重组 继续停牌】公司此前停牌筹划重大事项。9月22日,公司收到控股股东深圳市国资委通知,初步确认上述重大事项对公司构成重大资产重组。公司股票自25日开市时起转入重大资产重组事项继续停牌。公司预计在不超过1个月的时间内披露本次重组方案。
2017年09月24日    19:50
【富春股份控股股东质押1316万股】公司控股股东质押1316万股公司股份用于融资。截至公告披露日,富春投资持有公司股份 105,925,406 股,占公司总股本的18.58%,其中累计被质押股份9428万股,占其持有公司股份总数的89.01%,占公司总股本的16.54%。
2017年09月24日    19:47
【恒通科技全资子公司中标新疆7.9亿元PPP项目】全资子公司北京恒通创新整体房屋组装有限公司与裕腾建设集团有限公司组成的联合体,中标“新疆纺织服装产业园基础设施及标准化厂房PPP项目”。项目总投资约7.91亿元。本项目采用BOT模式,合作期不低于(含)10 年(包含建设期及运营期,建设期不超过2年)。
2017年09月24日    19:42
【神华集团名称变更为国家能源集团 获北京市工商局通过】北京市工商行政管理局发布企业名称变更申请核准告知书称,神华集团有限责任公司名称变更为国家能源投资集团有限责任公司申请获得通过。同时,变更以该企业为核心企业组建的企业集团名称为:国家能源投资集团,简称为:国家能源集团。
财新微信

热词推荐
南华早报 纪念日 大庆油田 负利率 东部战区 刘芳 博客 数字 秦晖 黄坤明 昆明火车站暴恐案 火线 谢伏瞻 吴英 王儒林