2017-阿里技术精选下册

1 .

2 . 扫一扫二维码图案，关注我吧 「阿里技术」微信公众号 「阿里技术」官方微博 

3 .

4 . 序 你好，我是阿里妹，第一次这么正式地写序，有点紧张。 2017 年， 在 技 术 发 展 的 历 史 上， 一 定 是 个 特 别 的 一 年： 柯 洁 与 AlphaGo 的惊世大战，无人咖啡店开放体验，AI 设计师“鲁班”横空出 世、三年投入千亿的达摩院正式成立…… 技术前进的脚步，比我们想象中更快。同样在今年，阿里技术公众号，正 式迎来了第 35 万位关注者，也有幸发布过数篇 10w+ 乃至百万阅读的文章。 PS：本想借此搞个联谊活动，瞅瞅后台性别比例 9:1，又默默放弃了。 有读者留言告诉我们，每天早上坐公交车上班，看阿里技术推送的文 章，已经成为了一种习惯。这让我们倍感不胜荣幸，又更觉肩上责任之重。 我们始终相信，每天一篇干货，效果虽不能立竿见影，但聚沙成塔、 滴水成川，你看过的东西，会成为你的一部分，潜移默化影响更多的人。 阿里技术公众号，看似只有阿里妹一个人运营。但在它身后，其实有 超过 25000 名阿里工程师的力量。这群可爱的作者里，有刚走出校门的 新人，有团队中的中流砥柱资深工程师，有带领数百、上千人的技术管理 者。他们在工作之余，抽出宝贵的休息时间，梳理自己对业务、技术、人 生的思考和理解。 没有华丽的词藻、繁复的修辞，只有朴质的代码、反复推敲的算法。 一篇文章看似只有几千字，但在背后，往往是数十人乃至数百人的团队， 长达数月、数年的摸索、跌倒，终于探得的成果。他们把这一路的所得， 迫不及待地分享给业界同仁，希望帮助大家少踩坑，少加班。 这次，在全年发布的近 300 篇文章中，我们选出 65 篇，集结成这套 《2017 阿里技术年度精选》，分为上、下两册，总计 600 余页。 

5 . 序　<　iii 这套精选集覆盖多个热门技术领域：算法、机器学习、大数据、数据 库、中间件、运维、安全、移动开发等，文章内容涉及技术架构、核心算 法、解决方案等干货。无论你是计算机相关专业的在校学生、科研机构的 研究人员，还是步入社会的 IT 从业人员，相信都能从中受益。 这套书同时收录了十多位阿里技术人的访谈：从工程师到合伙人的多 隆，6 年时间影响数亿用户的靖世，入选 MIT2017 年度 TR35 的王刚 & 吴翰清，免试晋升为研究员的钱磊等，将为你展现不一样的技术人生。 它不是一本系统讲述某个领域的书，更像是一本技术杂文选集，内容 五花八门。翻开书来，一眼望去，皆是散落在各个技术领域的结晶。你可以 把它当作床头书，或是在旅行的路上随手翻翻，充充电。希望这本书，能为 你打开一扇窗，去看更大的世界；成为一个小支点，帮你撬动更大的进步。 因为相信，所以看见。这世界依然浮躁，但庆幸始终有人相信，技术 让生活更美好。 感谢坚持分享、笔耕不辍的阿里工程师， 感谢所有关注阿里技术的小伙伴， 感谢所有的相遇与陪伴。 希望这套书，能陪你一起回味即将逝去的 2017。 2018，我们一起遇见更好的自己。 最后，阿里妹也期待你的回信，聊聊你的感想与建议：lunalin.lpp@ alibaba-inc.com 阿里妹 2017 年 12 月 

6 .目录 AI/ 算法 1 60 年后的你长什么样？人脸老化三大技术探秘 1 世界级难题：把不同物品装进箱子，如何使箱子表面积最小？ 7 号称史上最晦涩的算法 Paxos，如何变得平易近人？ 20 在线视频衣物精确检索技术 35 如何送货最省钱？菜鸟自研核心引擎架构解析 41 人类与机器人，如何能像朋友一样愉快聊天？ 52 阿里史上首款 AI 硬件设备，为何如此“听话”？ 66 史上最全！阿里智能人机交互的核心技术解析 75 深度学习要多深，才能读懂人话？｜阿里小蜜前沿探索 94 阿里妈妈首次公开自研 CTR 预估核心算法 MLR 109 阿里翻译一年 2500 亿次调用，节省 25 亿美元 117 战胜柯洁后，AI 在悄悄潜入人类下一个智慧堡垒 131 学术前沿 149 KDD 论文解读 | 想要双 11 抢单快？靠这个技术提速 9MS 149 KDD 论文核心算法独家解读 156 阿里 AI 技术取得重大突破：连破中、英语言处理两项世界纪录 163 如何让电脑成为看图说话的高手？计算机视觉顶会 ICCV 论文解读 168 揭秘支付宝中的深度学习引擎：xNN 175 

7 . 目录　<　v 机器学习 175 如何用机器学习方法，提升另一半的满意指数？ 183 如何搭建大规模机器学习平台？以阿里和蚂蚁的多个实际场景为例 194 深度 | 两个案例，掌握 AI 在大数据领域的前沿应用 203 大数据 203 近 300 位数据挖掘专家云集阿里，最精彩的发言都在这儿 213 权威详解 | 阿里新一代实时计算引擎 Blink，每秒支持数十亿次计算 220 如何扛住 1.8 亿 / 秒的双 11 数据洪峰？阿里流计算技术全揭秘 233 阿里知识图谱首次曝光：每天千万级拦截量，亿级别全量智能审核 239 基础架构 244 直击阿里双 11 神秘技术：PB 级大规模文件分发系统“蜻蜓” 244 阿里人打车不给钱？内部自研神器“欢行”首次曝光 261 企业内部 IT 应用 261 淘宝天猫背后，有一个你不知道的神秘组织 270 阿里怎么发工资？自研薪酬管理系统首次曝光 278 如何像阿里工程师一样高效办公？ 285 没想到，阿里工程师每天必刷的网站是…… 296 

8 .

9 .AI/ 算法 60 年后的你长什么样？人脸老化三大技术探秘 塞远 通过计算机视觉技术模拟出人老了的样子，这样的应用实际上并不新奇。这些 年，类似的场景可谓层出不穷，有的 App 可以通过夫妻的样貌预测出孩子的模样， 有的 App 可以通过用户上传的照片还原你小时候的样子和老了之后的样子，甚至还 有一些 App 可以通过一两张照片生成出一段短视频，展示用户一生的样貌变化，让 使用的人颇有沧海桑田之感。 而我们这次的“当你老了”项目的着眼点略有不同，强调的是公益和技术的结 合，因此我们需要将用户上传的面部照片变成 20 年，40 年和 60 年后，让用户看到 自己满脸皱纹，白发苍苍的样子，进而产生关爱身边老年人的感慨，人人每年公益 3 小时，共同为公益做出贡献。 

10 .2　>　2017 阿里技术年度精选（下） 经过将近 4 周左右的努力，我们初步完成了人脸老化项目的开发，赶在 9 月 5 日央视慈善之夜晚会前及时上线。央视公益晚会期间，用户通过扫描电视屏幕上的二 维码，进入我们手淘的互动页面（详见图 1），选择自己喜欢的照片进行老化。一场晚 会下来，许多的用户体验到了自己脸部变老之后的特效。 图 1　手淘“当你老了”项目页面示意图 整个项目中我们遇到了很多的挑战，比如老化模版的选择，脸型的变化趋势问 题，肤色的融合问题等等，下面我会把整个人脸老化技术分成几个关键的部分，进行 简短的剖析。 1. 脸型的老化算法 我们借鉴了一篇 2017 年最新的利用深度学习进行人脸老化的文章 [1]，该文章提 出了一种叫做 conditional adversarial autoencoder (CAAE) 的深度网络结构， 该结构能够学习出面部的 manifold，从而预测出任何一张输入面部图像的全年龄面 部图像。该网络的结构示意图如图 2 所示，该网络学习之后的预测结果示意图如 图 3 所示。 

11 . AI/ 算法　<　3 图 2　S tructure of the proposed CAAE network for age progression/regression. The encoder E maps the input face to a vector z (personality). Concatenating the label l (age) to z, the new latent vector [z, l] is fed to the generator G. Both the encoder and the generator are updated based on the L2 loss between the input and output faces. The discriminator Dz imposes the uniform distribution on z, and the discriminator Dimg forces the output face to be photo-realistic and plausible for a given age label. 图 3　Comparison to prior works of face aging. The first column shows input faces, and second column are the best aged faces cited from prior works. The rest columns are our results from both age progression and regression. The red boxes indicate the comparable results to the prior works. 

12 .4　>　2017 阿里技术年度精选（下） 尽管该深度学习网络能够很好的获得全年龄段的输出，但是它存在两个弊端，其 一是它训练预测出来的图片和输入人脸差异比较大，不像原始输入；其二是处理速度 上该网络速度比较慢，很难适应项目的要求。针对这两点缺点，我们决定只保留该网 络的老化脸型的能力，而脸上的纹理，即皱纹部分我们通过传统方法来贴。图 4 显示 了我们通过该网络获得的脸型变老的能力示意图。 图 4　面部脸型变老的示意图，从左到右分别是原图，20 年后，40 年后，60 年后 用手淘扫描上方二维码，遇见 60 年后的你 2. 脸部纹理的老化算法 在贴脸部皱纹或者说纹理的过程中，我们采用的是分而治之的办法 [2]。即把面部 分成许许多多的小三角形，然后将老人模版上对应的三角形贴到相应的输入人脸的三 角形上。这样做的好处是每个三角形足够小，利用 OpenCV 的 WarpAffine 进行形 变贴图时不会出现不自然的现象。当然这样做的前提是，我们已经获得了输入人脸以 及模版人脸的所有关键点，同时利用 Delaunay Triangulation 将所有关键点划分成若 

13 . AI/ 算法　<　5 干三角形了。关键点和三角形 Mesh 示意图如图 5 所示。 3. 肤色的融合算法 在完成了人脸的老化脸型 变化和贴皱纹的步骤后，我们 还缺最后一步，即将老化后的 脸完美无瑕地贴回到原始输入 图 5　面部关键点示意图，面部三角形化示意图 图像上去，否则会显得老化很 不自然。这里我们采用了一个非常经典地融合算法，即 Poisson Image Editing[3]， 它是通过保留剃度的方式使贴过来的图像能够无缝地融入背景图像。这里我们利用了 OpenCV3.2 里面提供的 SeamlessClone 这样一个函数，可以比较方便地实现前后 景融合。肤色和纹理的融合示意图如图 6 所示。 图 6　从左到右依次为原始图像，老人模版贴入相应三角形，SeamlessClone 之后的融合结果 4. 项目小结 在脸型，皱纹，肤色的老化之外，我们还尝试了头发的变白等算法，篇幅有限， 就不在此赘述了。最后贴几张我们认为效果还是不错的人脸老化结果作为结尾。 

14 .6　>　2017 阿里技术年度精选（下） 图 7　效果示意图 Reference [1] Zhifei Zhang, Yang Song, and Hairong Qi. "Age Progression/Regression by Conditional Adversarial Autoencoder." IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , 2017. [2] Face Morph Using OpenCV — C++ / Python,  http://www.learnopencv.com/face- morph-using-opencv-cpp-python/ [3] Poisson Image Editing, http://www.ctralie.com/Teaching/PoissonImageEditing/. 

15 . AI/ 算法　<　7 世界级难题：把不同物品装进箱子， 如何使箱子表面积最小？ 菜鸟人工智能部 阿里妹导读：三维装箱问题是一类经典的组合优化问题，具有巨大的学习研究和 实际应用价值。传统的三维装箱问题都是给定了箱子的尺寸并以最小化箱子的使用数 量为优化目标，但是在某些实际业务场景中并没有固定尺寸的箱子。 基于此类场景，本文提出了一类新型的三维装箱问题。在本问题中，需要将若干 个长方体物体逐个放入一个箱子中（物品的摆放位置不能倾斜），优化目标为最小化能 够容纳所有物品的箱子的表面积，因为箱子的表面积与其成本直接正相关。本文证明 了此类新问题为 NP-hard 问题。对于装箱问题，箱子的表面积取决于物品的放入顺 序、摆放的空间位置和摆放朝向。在这些因素中，物品的放入顺序有着非常重要的影 响。所以本文基于近些年被提出的、能够有效解决某些组合优化问题的深度强化学习 方法—Pointer Network 方法来优化物品的放入顺序。 本文基于大量实际业务数据对网络模型进行了训练和检验。结果表明，相对于已 有的启发式算法，深度强化学习方法能够获得大约 5% 的效果提升。 

16 .8　>　2017 阿里技术年度精选（下） 论文地址：https://arxiv.org/abs/1708.05930 1. 引言 装箱问题是一类非常经典且重要的优化问题，常被应用于物流系统和生产系统 中。装箱问题有很多变型问题，其中最重要且最难求解的是三维装箱问题，在此问题 中，需要将若干个不同大小的长方体物品放入箱子中，物品之间不能重叠且不能倾斜， 箱子的尺寸和成本已知，优化目标为最小化箱子的使用数量，即最小化总成本。装箱 问题一直是学术界非常流行的研究方向之一。除此之外，装箱问题在实际中也有很多 应用。有效的装箱算法往往意味着计算时间、装箱成本的大量节省和资源使用效率的 大幅提升。 在某些实际业务场景中，我们发现装箱时并不是使用固定尺寸的箱子（例如在跨 境电商业务中，大部分是使用柔性的塑料材料，而不是箱子来包装货物） ，而且由于装 箱的成本大部分都由装箱材料成本构成，而装箱材料成本又主要取决于材料的表面积。 所以在本研究中，我们提出了一类新型的装箱问题。与传统三维装箱问题不同的是，本 问题的优化目标为确定一个能够容纳所有物品的箱子，并最小化此箱子的表面积。 由于寻找装箱问题的最优解非常难，所以相关研究者们提出了不同的近似算法和 启发式算法来求解此类问题。但是启发式算法往往有着较强的问题依赖性，一类启发 式算法可能只适用于求解某种或某些业务场景中的装箱问题。近些年来，人工智能技 术，尤其是深度强化学习 (Deep reinforcement learning, DRL) 技术有着非常快速 的发展，并且在某些问题上取得了令人瞩目的成果。而且深度强化学习技术已经被发 现在求解组合优化问题方面具有较大的潜力，所以本研究使用了一种基于深度强化学 习的方法来求解新型三维装箱问题。本文基于大量实际业务数据训练了深度强化学习 模型，并验证了模型的效果。 2. 相关研究介绍 2.1　三维装箱问题相关研究 装箱问题是一类非常经典和流行的优化问题。自从其在 20 世纪 70 年代被提出 

17 . AI/ 算法　<　9 以来，大量研究者对此类问题进行了研究并获得了许多有价值的成果。[Coffman et al ., 1980] 证明了二维装箱问题是 NP-hard 问题，所以作为二维装箱问题的一般化 问题，三维装箱问题也是 NP-hard 问题。由于此原因，很多之前的研究都集中于近 似算法和启发式算法。[Scheithauer, 1991] 首先提出了针对三维装箱问题的近似算 法并分析了其近似比。 此外，研究者们还提出了很多不同类型的启发式算法，例如禁忌搜索 ([Lodi et al .,2002], [Crainic et al ., 2009]), 引导式局部搜索 ([Faroe et al ., 2003]), 基于极点 的启发式算法 ([Crainic et al ., 2008])，混合遗传算法 ([Kang et al .,2012]) 等。在精 确解算法方面，[Chen et al ., 1995] 考虑了一种有多种尺寸箱子的三维装箱问题，并 建立一个混合整数规划模型来求解最优解。[Martello et al .,2000] 提出了一种分支定 界算法来求解三维装箱问题，并通过数值实验表明 90 个物品以内的问题都可以在合 理的时间内获得最优解。 另外，还有一些从实际业务中提出的装箱问题的变型问题，例如 [Kang and Park, 2003] 提 出 了 一 种 可 变 尺 寸 的 装 箱 问 题，[Khanafer et al .,2010], [Gen- dreau et al ., 2004] 研究了一种考虑物品冲突的装箱问题，[Clautiaux et al .,2014] 对一种考虑易碎物品的装箱问题进行了研究。 另一类装箱问题—条带装箱问题 (Strippacking problem) 与本文提出的新问题 

18 .10　>　2017 阿里技术年度精选（下） 比较接近。在一般的条带装箱问题中，若干个长方体物品需要被逐个放入一个给定的 条带中，条带的长度和宽度是已知且固定的，长度为无穷大（在二维条带装箱问题中， 条带的宽度固定，但是长度为无穷大），优化目标为最小化使用的条带的高度。此类 问题在钢铁工业和纺织工业中有很多应用，研究者们也提出了不同类型的求解算法， 例如精确解算法 ([Martello et al ., 2003]，[Kenmochi et al ., 2009])，近似解算法 ([Steinberg, 1997])，启发式算法 ([Bortfeldt and Mack, 2007], [Bortfeldt, 2006], [Hopper andTurton, 2001]) 等。 2.2　DRL 方法在组合优化问题中的应用研究 虽然机器学习和组合优化问题已经分别被研究了数十年，但是关于机器学习方法 在求解组合优化问题方面的研究却比较少。其中的一个研究方向是使用强化学习的思 想来设计超启发式算法。[Burke et al ., 2013] 在一篇关于超启发式算法的综述论文中 对于一些基于学习机制的超启发式算法进行了讨论。[Nareyek, 2003] 使用了一种基 于非平稳强化学习的方法来更新启发式算法被选择的概率。除此之外，强化学习思想 在超启发式算法中的应用研究还包括二元指数补偿 ([Remde et al .,2009])、禁忌搜 索 ([Burke et al .,2003]) 和选择函数等 ([Cowling et al ., 2000])。 近 些 年 来， 序 列 到 序 列 模 型 (sequence-to-sequence) 的 一 系 列 研 究 突 破 激 发 了 研 究 者 们 对 于 神 经 组 合 优 化 (neural combinatorial optimization) 方 向 的 兴趣。其中注意机制 (attention mechanism) 对于加强神经网络模型在机器翻译 ([Bahdanau et al .,2014]) 和 算 法 学 习 ([Graves et al .,2014]) 方 面 的 效 果 中 扮 演 了重要决策。 [Vinyals et al ., 2015] 提出了一种带有特殊注意机制的网络模型— Pointer Net，并使用有监督学习的方法来通过此模型求解旅行商问题 (Travelling Salesman Problem)。[Bello et al ., 2016] 提出了一种基于强化学习思想的神经组 合优化 (neural combinatorial optimization) 框架，并使用此种框架求解了旅行商问 题和背包问题 (Knapsack Problem)。因为此种框架的有效性和普适性，本研究在求 解新型装箱问题中主要使用了此种框架和方法。 

19 . AI/ 算法　<　11 3. 针对三维装箱问题的 DRL 方法 3.1　问题定义 在经典的三维装箱问题中，需要将若干个物品放入固定尺寸的箱子中，并最小 化箱子的使用数量。与经典问题不同的是，本文提出的新型装箱问题的目标在于设计 能够容纳一个订单中所有物品的箱子，并使箱子的表面积最小。在一些实际业务场景 中，例如跨境电商中，包装物品时使用的是柔性的塑料材料，而且由于包装材料的成 本与其表面积直接正相关，所以最小化箱子的表面积即意味着最小化包装成本。 本文提出的新型装箱问题的数学表达形式如下所示。给定一系列物品的集合，每 个物品 i 都有各自的长 (l i )、宽 (w i ) 和高 (h i )。优化目标为寻找一个表面积最小且能够 容纳所有物品的箱子。我们规定 (x i  , y i  , z i ) 表示每一个物品的左下后 (left-bottom- back) 角的坐标，而且 (0, 0, 0) 表示箱子的左下后角的坐标。决策变量的符号及其含 义如表 1 所示。基于以上问题描述和符号定义，新问题的数学表达形式为： 其中， sij = 1 表示第 i 个物品在第 j 个物品的左边， uij = 1 表示第 i 个物品在第 j 个 物品的下边， bij = 1 表示第 i 个物品在第 j 个物品的后边。 δ i1 = 1 表示物品 i 的摆放朝向 为正面朝上， δ i 2 = 1 表示物品 i 正面朝下， δ i 3 = 1 表示物品 i 侧面朝上， δ i 4 = 1 表示物 

20 .12　>　2017 阿里技术年度精选（下） 品 i 侧面朝下， δ i 5 = 1 表示物品底面朝上， δ i 6 = 1 表示物品底面朝下。 约束条件中的 (9), (10), (11) 表示物品在不同的朝向情况下占用的空间的长宽 高；约束条件 (1), (3), (4), (5) 表示物品之间没有重叠，约束条件 (6), (7), (8) 保证了 箱子容纳了所有物品。 基于以上的数学模型，我们使用了优化引擎，例如 IBM Cplex 等来直接求解此 问题。但是对于一般规模的问题（例如物品数量大于等于 6），很难在合理的时间内获 得最优解。而且我们还证明了此类问题是 NP-hard 问题。证明过程请见附录。 表1　决策变量符号及含义 变量名 类型 含义 L 连续型变量 箱子的长度 W 连续型变量 箱子的宽度 H 连续型变量 箱子的高度 xi 连续型变量 物品的左下后角的 x 坐标 yi 连续型变量 物品的左下后角的 y 坐标 zi 连续型变量 物品的左下后角的 z 坐标 sij 0-1 二元变量 第 i 个物品是否在第 j 个物品的左边 uij 0-1 二元变量 第 i 个物品是否在第 j 个物品的下边 bij 0-1 二元变量 第 i 个物品是否在第 j 个物品的后边 δ i1 0-1 二元变量 第 i 个物品是否是正面朝上 δi2 0-1 二元变量 第 i 个物品是否是正面朝下 δi3 0-1 二元变量 第 i 个物品是否是侧面朝上 δi4 0-1 二元变量 第 i 个物品是否是侧面朝下 δi5 0-1 二元变量 第 i 个物品是否是底面朝上 δi6 0-1 二元变量 第 i 个物品是否是底面朝下 3.2　DRL 方法 在本部分中，我们将介绍用于求解新型三维装箱问题的 DRL 方法。在求解三维 装箱问题时，决策变量主要分为三类： （1）物品放入箱子的顺序； （2）物品在箱子中的摆放位置； 

21 . AI/ 算法　<　13 （3）物品在箱子的摆放朝向。 我们首先设计了一种启发式算法来求解此类新型三维装箱问题。此种算法的基 本思想为：在放入一个物品时，遍历所有可用的空余空间和物品朝向，并选择能够最 小化表面积的组合。然后再遍历所有物品，确定一个能够最小化浪费空间体积（least waste space）的物品。算法的详细步骤请见附录。在本文中，我们使用 DRL 方法 来优化物品的放入顺序，在确定了物品的放入顺序之后，选择物品的摆放位置和朝向 时使用和以上启发式算法相同的方法。所以本研究的重点在于使用 DRL 方法来优化 物品的放入顺序。在未来的研究中，我们将会把物品的放入顺序、摆放位置和朝向统 一纳入深度强化学习方法框架中。 3.2.1　网络结构 本研究主要使用了 [Vinyals et al .,2015] 和 [Bello et al .,2016] 提出的神经网络 结构。在 Vinyals 和 Bello 等人的研究中提出了一种名为 Pointer Net (Ptr-Net) 的 神经网络来求解组合优化问题。例如，在求解旅行商问题时，二维平面中每个点的坐 标被输入到网络模型中，经过计算之后，模型的输出为每个点被访问的顺序。这种网 络结构与 [Sutskever et al .,2014] 提出的序列到序列模型非常相似，但是有两点不 同：第一，在序列到序列模型中，每一步的预测目标的种类是固定的，但是在 Ptr- Net 中是可变的；第二，在序列到序列模型中，在解码阶段通过注意机制将编码阶段 的隐层单元组合成为一个上下文向量信息，而在 Ptr-Net 中，通过注意机制来选择 （指向）输入序列中的一个来作为输出。 本研究中使用的神经网络模型的结构如图 1 所示。网络的输入为需要装箱的 物品的长宽高数据，输出为物品装箱的顺序。网络中包含了两个 RNN 模型：编码 网络和解码网络。在编码网络的每一步中，首先对物品的长宽高数据进行嵌入表达 （embedded），然后再输入到 LSTM 单元中，并获得对应的输出。在编码阶段的最 后一步，将 LSTM 单元的状态和输出传递到解码网络。在解码网络的每一步中，在 编码网络的输出中选择一个作为下一步的输入。如图 1 所示，在解码网络中的第 3 步 的输出为 4，则选择（指向）编码网络的第 4 步的输出，将其作为解码网络下一步（第 4 步）的输入。此外，在每一步的预测过程中还使用了 [Bello et al ., 2016] 提出的 

22 .14　>　2017 阿里技术年度精选（下） Glimpse 机制来整合编码阶段和解码阶段的输出信息。 图 1　神经网络模型的结构 3.2.2　基于策略的强化学习方法 本研究中使用了强化学习方法来训练网络模型。网络模型的输入可以表示为 s = {( li , wi , hi )}i =1 ，其中 l i , w i , h i 分别表示第 i 个物品的长宽高。网络模型的输出为物品 n 放入箱子的顺序，用 o 来表示。我们使用表面积（Surface area，SA）来评价模型 的输出结果，使用 SA (o|s ) 表示在模型输入为 o ，输出为 s 的情况下对应的表面积。 模型的随机策略可以表示为 p (o |s )，即在模型输入为 s 的情况下，输出为 o 的概率。 模型训练的目标为尽可能的使对应表面积较小的输出 (o ) 以较大的概率被选中。我们 使用 θ 表示网络模型的参数，则训练目标可以表示为： J (θ | s ) = Eo~ pθ ( ⋅|s ) SA(o | s ) [Williams, 1992] 提出了一种具有普适性的强化学习方法，此种方法能够在训练 过程中使模型参数在期望的强化方向上不断地调整。基于此种方法，本研究在训练的 每一步中，在获得了奖励值（reward）、基准值（baseline value）和预测的概率分布 之后，模型参数的更新公式为： ∇θ J (θ | s ) Eo~ pθ(⋅|s ) [( SA(o | s ) – b ( s )) ∇θ log pθ (o | s )] = 其中 b (s ) 表示表面积的基准值，可以用来有效降低训练过程中梯度的方差。在 训练过程中，如果我们随机选取 M 个独立同分布的样本 s1 , s2 ,…, sM , 则以上更新公式 

23 . AI/ 算法　<　15 可以近似为： 1 M ∇θ J (θ | s ) ≈ M ∑[(SA(o | s ) – b ( s ))∇ log pθ (o | s )] i =1 i i i θ i i 3.2.3　基准值的更新 在本研究中，我们使用了一种基于记忆重放的方法来不断地更新基准值。首先， 对于每一个样本点 si ，通过启发式算法获取一个装箱方案，并计算其表面积，作为 b (si ) 的初始值。之后在每一步的训练过程中，通过以下公式来更新基准值： b ' ( si ) = b ( si ) + α ( SA(oi | si ) − b ( si )) 其中 SA(oi | si ) 为训练过程中获得表面积的值。 3.2.4　随机采样与集束搜索（Beam Search） 在模型的训练阶段，我们从模型预测的概率分布中进行随机选取作为输出。但是 在验证阶段，我们采用贪婪策略来进行选择，即在每一步中，我们选取概率分布中概 率最大的备选项作为输出。除此之外，我们还在验证阶段使用来集束搜索的方法来提 高模型的效果，即在每一步中不是选择对应概率最高的备选项，而是选择概率最高的 前 k 个备选项作为输出。 通过以上描述，模型的整个训练步骤总结为： 算法1：网络模型的训练步骤 1: 使用 S 表示训练样本集合，T 表示训练步数，B 表示训练过程中每批样本的样本量 2: 初始化 Pointer Net 的参数 θ 3: for t = 1 to T do 4: 选择一批训练数据 s i ，其中 i ∈ {1, 2, , B} 5: 对于 s i ，基于 pθ (⋅ | si ) 选择模型的输出 oi 1 B 6: 计算 gθ = ∑[(SA(oi | si ) − b ( si ))∇θ logpθ (oi | si )] B i =1 7: 更新 θ ← ADAM (θ , gθ ) 8 对于 i ∈ {1, 2, , B} ，更新基准值 b ' ( si ) = b ( si ) + α ( SA(oi | si ) − b ( si )) 9: end for 10: 返回模型参数 θ 

24 .16　>　2017 阿里技术年度精选（下） 4. 数值实验 为了验证模型的效果，我们基于大量实际业务数据完成了数值实验。根据实验过 程中每个订单中物品数量的不同（8，10 和 12），实验分为了三个部分，但是每次实 验过程中的超参数均相同。在每次实验中，我们采用了 15 万条训练样本和 15 万条 测试样本。在实验过程中，每批训练的样本量为 128，LSTM 的隐层单元的数量为 128，Adam 的初始学习速率为 0.001，并且每 5000 步以 0.96 的比例衰减。网络 模型的参数的初始值均从 [-0.08, 0.08] 中随机选取。为了防止梯度爆炸现象的出现， 我们在训练过程中使用 L2 正则方法对梯度进行修剪。在更新基准值的过程中，的取 值为 0.7。在每次训练中，我们在 Tesla M40 GPU 上训练 100 万步，每次的训练 时间大约为 12 小时。在验证阶段，使用集束搜索方法时，集束搜索的宽度为 3。模 型主要通过 TensorFlow 来实现。 数 值 实 验 的 结 果 请 见 表 2。 主 要 评 价 指 标 为 平 均 表 面 积（Average surface area, ASA）. 从表中可以看出，在使用集束搜索的情况下，本文提出的基于 DRL 的 方法在三类测试集上分别可以获得大约 4.89%, 4.88%, 5.33% 的效果提升。此外， 我们还通过穷举的方法获得了对于 8 个物品测试数据中 5000 个样本数据的最优物品 放入顺序，并计算得到了启发式算法的结果与最优解的平均差距为 10% 左右，这说 明基于 DRL 的方法的结果已经与最优解比较接近。 表2　不同方法下获得的ASA 深度强化学习方法 深度强化学习方法 物品数量 随机方法 启发式算法 （随机选取） （集束搜索） 8 44.70 43.97 41.82 41.82 10 48.38 47.33 45.03 45.02 12 50.78 49.34 46.71 46.71 5. 结论 本文提出了一类新型三维装箱问题。不同于传统的三维装箱问题，本文提出的 问题的优化目标为最小化能够容纳所有物品的箱子的表面积。由于问题的复杂性和求 解难度，此类问题非常难以获得最优解，而大部分启发式算法又缺乏普适性。所以本 

25 . AI/ 算法　<　17 文尝试将 Pointer Net 框架和基于深度强化学习的方法应用到了对此类问题的优化求 解中。本文基于大量实际数据对网络模型进行了训练和验证，数值实验的结果表明基 于深度强化学习方法获得的结果显著好于已有的启发式算法。本项研究的主要贡献包 括：第一，提出了一类新型的三维装箱问题；第二，将深度强化学习技术应用到了此 类新问题的求解中。在之后的研究中将会深入探索更有效的网络模型和训练算法，并 且会尝试将物品的摆放位置和朝向的选择整合到模型中。 附录： A：三维装箱问题的启发式算法 用于求解本文的新型三维装箱问题的启发式算法包括最小表面积（least surface area）算法和最小浪费空间（least wastespace）算法。算法的详细步骤如下所示： 算法2：针对三维装箱问题的启发式算法 1: 使用 I 表示物品集合，每一个物品的长宽高分别为 li 、wi 和 hi 2: 初始化一个足够大的箱子 B，其长宽高分别为 L, W, H ( 可以设置为 n L = W= H= ∑max ( l , h , w ) ) i =1 i i i 3: 初始化剩余物品集合 Iˆ = I ，初始化可用空间集合 ES = ∅ 4: for t = 1 to n do 5: 如果 t =1： 6: 选择一个表面积最大的物品 7: 将物品放入箱子中，然后将由此产生的 3 个可用空间加入到 ES 中 8: 否则： 9: 使用最小浪费空间算法从物品集合 S 中选择一个物品 i , 更新 Iˆ ← Iˆ \ i 10: 使用最小表面积算法选择物品的放入空间位置和朝向 11: 在放入物品之后，会产生新的可用空间 (ES 1)，而之前的部分可用空间会被占用 (ES 2)， 更新可用空间集合 ES ← ES ∪ ES1\ ES 2 12: 结束判断 13: end for 14: 返回能够容纳所有物品的箱子的表面积 

26 .18　>　2017 阿里技术年度精选（下） 算法3：最小表面积算法 1: 使用 ES 表示可用空间集合，O 表示物品的朝向集合 3 ⋅ ( max ( li , wi , hi ) ⋅ n ) 2 2: 初始化物品 i 对应的最小化表面积 LSAi = 3: 初始化对于物品 i 的最佳可用空间 sˆi = null , 最佳朝向 oˆi = null 4: for 任意 s ∈ ES do 5: for 任意 o ∈ O do 6: 计算物品 i 以朝向 o 放入 s 之后的表面积 SAi ,s ,o 7: 如果 SAi ,s ,o < LSAi : 8: sˆi s= 更新= , oˆi o, LSA =i SAi ,s ,o 9: 否则，如果 SAi ,s ,o = LSAi ： 10: 如果 min ( length ( s ) − o ( li ) , width ( s ) − o ( wi ) , height ( s ) − o ( hi ) ) 小于 min ( length ( si ) − o ( li ) , width ( si ) − o ( wi ) , height ( si ) − o ( hi ) ) , 则使用 s, o 更新 si , oi . 11: 结束判断 12: end for 13: end for 14: 返回对于物品 i 的 sˆi , oˆi 算法 4：最小浪费空间算法 1: 使用 I 表示剩余物品集合，使用 Vi 表示物品的体积 2: 初始化最佳物品 ˆi = null ( max ( l , w , h ) ⋅ n ) 3 3: = 初始化最小体积 LV i i i 4: for 任意 i ∈ I do 5: 计算物品 i 按照朝向 oˆi 放入可用空间 sˆi 之后（ sˆi , oˆi 通过最小表面积算法获得）的体积 V , 使用 LWV=i V − Vi 表示最小浪费体积 6: 如果 LWVi < LV : ˆ i = LV LWV = i,i 7: 更新 8: 结束判断 9: end for 10: 返回物品 i B：关于新型三维装箱问题为 NP-hard 问题的证明 引理 B.1: 本文提出的新型三维装箱问题为 NP-hard 问题。 证明： 首先，我们证明新型的二维装箱问题为 NP-hard 问题。为了完成此证明，我们 将新型的二维装箱问题归约为一维的普通装箱问题。 

27 . AI/ 算法　<　19 对于一维的普通装箱问题，我们有 n 个物品，其尺寸分别为 w1 , w2 , , wn ，其中每 一个 wi 为正整数。箱子的容量为正整数W 。优化目标为最小化箱子的使用数量。 为了将新型的二维装箱问题归约为普通的一维装箱问题，我们假设有 n 个物品， 其宽度分别为 w1 , w2 , , wn ，高度为 1/ ( n ⋅ max ( wi ) ) 。而且还有一个物品，其宽度为 W ，高度为 W ⋅ n ⋅ max ( wi ) ，我们称此物品为基准物品。则可以定义一个新型的装箱问 题为：找到一个能够装下所有 n + 1 个物品且表面积最小的箱子。 不失一般性，我们假设基准物品放在箱子的左下角。如果将一个其它物品放到基 准物品的右方，则至少会使表面积增加 (W ⋅ n ⋅ max ( xi ) ) / ( n ⋅ max ( wi ) ) =W 。而如果将 其它物品放到基准物品的上方，则最多使表面积增加 W 。所以所有的物品必须被放到 基准物品的上方。 然后，我们证明物品在放置时没有进行旋转。如果在放置时有任意一个物品进行 了旋转，则表面积至少增加 W ⋅ min ( wi ) 。如果放置时没有物品进行旋转，则表面积至 多增加W ，所以为了最小化表面积，物品放置时是没有进行旋转的。 所以，如果我们能够针对此种包含 n + 1 个物品的新型二维装箱问题找到一个最优 解，则我们就能够同时获得对于普通一维装箱问题的最优解。即如果我们能够在多项 式时间内求解此类新型二维装箱问题，则同样能够在多项式时间内求解以上的普通一 维装箱问题。显然，这种情况不可能出现，除非 P=NP。 对于新型的三维装箱问题，我们可以同样在二维问题的基础上对每个物品增加一 个长度 1/ ( n ⋅ max ( wi ) ) 。证明方法与以上相同。 2 

28 .20　>　2017 阿里技术年度精选（下） 号称史上最晦涩的算法 Paxos，如何变得平易近人？ 阿里技术 阿里妹导读：Paxos（分布式一致性算法）作为分布式系统的基石，一直都是计算 机系统工程领域的热门话题。Paxos 号称是最难理解的算法，其实真的这么困难么？ “X-Paxos”是阿里巴巴数据库团队面向高性能、全球部署以及阿里业务特征等 需求，实现的一个高性能分布式强一致的 Paxos 独立基础库。X-Paxos 具体又有哪 些优势，能给现有的系统带来什么收益呢？ 背景 分布式一致性算法（Consensus Algorithm）是一个分布式计算领域的基础性问 题，其最基本的功能是为了在多个进程之间对某个（某些）值达成一致（强一致）；进 而解决分布式系统的可用性问题（高可用）。Paxos 是最重要的分布式一致性算法， 很多人都把它作为“分布式一致性协议”的代名词（Mike Burrows, inventor of the Chubby service at Google, says that“there is only one consensus protocol, and that’s Paxos” ）。 关于 Paxos 的历史和原理，已经有很多经典的论文可以参考，也有厂内外的文 章有详细的描述，本文就不再重复了。感兴趣的同学可以阅读下这些论文 [1,2,3,4]。 业内 虽然 Paxos 的理论提出已经 17 年了，从第一个 Paxos 的工业实现到现在也已 经 11 年了，但是直到近几年，无论是顶级会议，还是业内，Paxos 相关的文章和项 目还是层出不穷。 转向业内，虽然使用了 Paxos 及各种变种的产品已经层出不穷；但是真正工业 级的，独立的，Paxos 基础库还是相当的少见：Google 并没有开源其任何 Paxos 基础库（连包含 Paxos 的项目都没有开源过）; Facebook 也没有公布过包含 Paxos 

29 . AI/ 算法　<　21 的产品 ; Apache 有 Zookeeper，但是其协议并不能支持一个高吞吐的状态机复制， 且并没有提供独立的第三方库，可供快速接入。 在 Github 上 能 找 到 的 Paxos 的 独 立 库，star 最 高 的 是 腾 讯 于 去 年 开 源 的 phxpaxos（后文会作为竞品进行详细对比）。 因此到目前为止业内还鲜有成熟可靠的，可供快速使用的独立第三方 Paxos 库， 开源的 Paxos 生态也尚未成熟。 X-Paxos 愿景 我们的初衷并不是要做一个 Paxos 的公共库，X-Paxos 诞生于阿里巴巴的分布 式数据库 AliSQL X-Cluster，但 X-Paxos 并不属于 AliSQL X-Cluster。Paxos 是分布式系统的基石，X-Paxos 可用于解决各种各样的分布式系统中的一致性问题。 因此在整个分布式数据库的设计之初，我们就独立设计了分布式一致性协议模 块，并把它独立为 X-Paxos。X-Paxos 为 AliSQL X-Cluster 解决了分布式一致 性问题，同样可以快速赋予其他系统分布式一致性能力。 分布式一致性需求，并不是 AliSQL X-Cluster 所特有的，很多系统都存在这高 可用和强一致的需求，我们把 Paxos 的能力独立成一个基础库，希望能够把这个能 力带给更多的其他系统。 例如：团队内的同学把 X-Paxos 融入到单机 KV 数据库 RocksDB 中，快速实 现了一个分布式 KV 引擎。集团已有业务团队团队把 X-Paxos 融入到业务存储系统 中，构建全新的分布式强一致存储服务。 同时也正是 AliSQL X-Cluster，成就了 X-Paxos。Google 的论文《Paxos made live》中有一段话说的很好，大意是说：Paxos 从理论到现实世界的实现之间 有巨大的鸿沟，在真正实现一个 Paxos 的时候，往往需要对 Paxos 的经典理论做一 些扩展，（尤其是在实现一个高性能的 Paxos 的时候，扩展点就更多了，可以参考后 文的功能增强和性能优化），这往往会导致真正的 Paxos 实现其实都是基于一个未被 完全证明的协议。