决策智能技术浪潮袭来，数智商业领域如何变革？来听听三位专家怎么说（2）

蔡少伟研究员：一种求解大规模稀疏组合优化问题的高效方法

大家好，今天我分享的题目是大规模稀疏组合优化的高效方法。很多决策问题的核心都涉及组合优化问题，人们很关注如何选择合适的组合方案来达到目标最优化。

求解组合优化主要有两类方法：一类是启发式方法，包括启发式搜索和启发式构造，比如大家经常用的贪心算法就可以看作启发式构造的一种，贪心准则就是启发式（heuristics）；另外一种是分支限界（brand-and-bound）为代表的精确算法。

启发式方法的好处是对规模不敏感，所以可以用近似求解大规模的问题，缺点是往往不知道求出的解离最优解有多大的差距，也可能已经找到最优解了，但是你不知道。Branch And Bound 是完备性的，如果你给它充足时间算到停下来，可以求出最优解并且证明这是最优解。但这个方法是有代价的，会对规模比较敏感，因为这类算法是指数爆炸的，往往不适用于大规模问题。

不管是做搜索还是做构造，启发式算法框架大多很简单，主要是依赖于启发式怎么设计，要根据哪个准则去做。分支限界方法主要在于怎么做「界」，大家看论文也会发现，很多 Branch And Bound 的论文在做 bounding 技术，怎么把这个界做得更紧，可以更好对解空间进行剪枝。

后来我想，可不可以把这两个结合一下？也就是说，既能够保持对规模不敏感，又能把 bounding 技术加进去。大家很容易想到，可以用预处理的方法，或者先做 Heuristics 再做 Branch And Bound，把 Heuristics 结果作为初始解等等。我们在这方面提出了一个新的方法 —— 嵌套地在 Heuristics 和 Branch And Bound 中去迭代。

简单来说，这个方法先粗糙地做一个 Heuristic solving，求一个初步结果。一般来说，做 bounding 需要上下界，Heuristics 会粗糙得到一个下界，接下来通过设计上界的函数。假设这个问题规模比较大，包括很多元素，我们可以淘汰一些，使得问题缩小一圈。之后再精致一点，继续做 Heuristic solving，这样可能改进下界。在这个基础上，算法可以再做一些 bounding，一直嵌套地做下去。于是这个算法就变成半精确算法，有可能可以证明这是最优解的，因为在某一步发现问题空间足够小，不需要 Heuristic solving 而是可以直接精确求解。另外，如果没有求出最优解，也可以知道最优解的区间在哪里。

接下来举两个例子解释这个方法。

第一个是「最大团问题」。团是图论里很经典的概念，在一个图里，点和点之间都有边相连的子图，就称为团，最大团问题是找到最大规模的团。如果给它一个加权，对每个顶点赋予一个权重，这样的最大加权团问题是要找到总权重最大的团。下图这个例子中，分别是四团、三团，三团的权重更大一些，也就是这个图的最大加权团。

按照该框架来做这个事情，我们需要两个子算法，一个做启发式求解，在团里称为 FindClique，另外一个是化简算法，称为 ReduceGraph。我们可以用 FindClique 找到一个团，这个团会比之前找到的要好。当这个更好的团走到 Reduce Graph，我们知道的是：最大团至少有这么大。也是在这一步做化简，如果图经过化简变为空，那么说明找到的团就是最优解；如果没有变为空，那么可以减少一些点，再回去调整找团的算法。这里的算法不一定是固定的算法，可以动态地变化。

我们的一项工作选了「construct and cut」的方法，可以理解为多次贪心的算法。

多次贪心的作用在于，每一次贪心构造可以很快，可以从不同的起点出发，而且如果在某次构造过程中算出来，当前的团再怎么扩展都不可能超过之前找到的团，我们就可以停止。最终目的是希望找到比以前大一些的团，启发式要不要做得更精致以及顺序如何调整，依赖于图的规模，就像剥洋葱一样，剥到某一层再精化，以便有更大精力把更好的团找出来。当图不能再化简的时候，我们可以采取精确的算法，比如 Branch And Bound。找到一个团之后，根据我们的方法，我们要做 bounding 把一些点扔掉，方法在于估计点所能发展出来的团有多大，可以有不同方案去解决。

这两个估界技术是作为例子，大家可以利用不同的技术去做。在实验方面，可以参考下表，对比 FastWClq、LSCC+BMS、MaxWClq 这些方法，求解到相同精度的时间相差十几倍甚至上百倍。

接下来看第二个问题：「图着色问题」。所谓着色是给图的每个点涂一个颜色，相邻两个点不能为同一个颜色，图着色问题讨论的是一个图最少可以用多少种颜色来着色，最少颜色数叫做图的色数。图着色问题有很多应用，特别是在没有冲突情况下分配资源。

这个问题大思路是一样的 —— 启发式求解加一些 bounding 的技术。不同的是，图着色问题并不要求子集合，由于要对整张图进行着色，所以没有「永远扔掉」这个概念，每个点最后都要返回去，这个点一定要有一个颜色。这里的 reduce 是把图分解为 Kernel 和 Margin：

有一个很简单的规则，还是与独立集有关，我如果知道这个图至少需要用多少种颜色，就是颜色下界（记为ℓ），则可以找到ℓ-degree bound 的独立集。这个独立集的点的度数都比ℓ小，所以叫做ℓ-degree bound。如果找到这样的独立集，可以放心移到 Margin 里面。如果把 kernel 的 solution 找出来之后，我们可以很方便把 Margin 合并进来，如果 kernel 是最优解，合起来一定也是最优解，这个规则可以迭代地去使用。

我们看一个例子，这个例子里面灰色的四个点是 kernel，可以看到至少需要 4 种颜色。旁边的三个点放到边缘上，因为三个点的度数都比 4 小，我们放心把这三个点挪到旁边先不管。然后发现剩下这个子图分解不动，已经很硬核了，可以直接求解出来。稀疏图的硬核一般都不大，所以可以考虑精确算法求解。如果把核心找出来，因为已知核心至少用四个颜色，对于边缘中的点，每个点的度数小于 4，怎么样都留有一个颜色给它，走一遍就可以了，线性的时间就可以了。

直到最后，每一次剥离的 Margin 都要保留下来，而且要标记清楚是第几层，这是与第一个问题稍微不同的地方。我们要用额外数据结构把这些边缘图保留下来，最后一个剥不动的 Kernel 精确化解决之后，就可以用倒序的方法，先把最后一个 Margin 给合并进来，根据刚才的规则保留最优性，Kernel 是最优的话，合并一个边缘还会是最优，一路回溯上去，那原图的解也一定是最优的。

当这个问题变成有框架的之后，就只剩下考虑如何找 lower bound 和 upper bound。算法的大致思路是：一开始 kernel 是原图，需要用到最大团算法找一个 lower bound；剥掉边缘之后，可以采取贪心图着色算法，找一个 upper bound。

这里其实用到了三种算法。实践中比较常见组合拳打法，具体到做 kernel 着色，当这个图比较大的时候，我们可能通过某种贪心或者比较快的方法去做，最后有可能变成精确算法去做。整个流程中，lower bound 和 upper bound 都是全局的，如果这两个相等，就可以停下了。

上图是实验结果，可以看出在稀疏大图上面的效果更好，144 个中里有 97 个可以在一分钟内证明最优解。跟同类算法相比，我们的算法对比时间也比较快，在比较稀疏大图上面有特殊方法可以很快求解。大家以前认为，几百万顶点的 NP 难问题肯定要算很久，其实，如果这些图很大但有一定特点的话，我们还是可以在秒级和分钟级的时间内解决的。

阿里妈妈 CTO 郑波：阿里妈妈持续升级的决策智能技术体系

大家好，作为阿里妈妈技术负责人，我将从业界视角分享一下过去几年阿里妈妈在决策智能技术上的进展。

阿里妈妈创立于 2007 年，是阿里巴巴集团的核心商业化部门，也就是在线广告部门。经过了十几年的发展，阿里妈妈打造过「搜索广告淘宝直通车」这样有影响力的产品，2009 年有了展示广告、Ad Exchange 广告交易平台，2014 年又出现了数据管理平台达摩盘，2016 年开始做全域营销。

从技术上看的话，在 2015 年、2016 年前后，阿里妈妈全面拥抱深度学习，从智能营销引擎 OCPX 到自研 CTR 预估核心算法 MLR 模型，都是随着深度学习的方法不断演进的。2018 年，深度学习框架 X-Deep Learning 开源。2019 年，Euler 图学习框架开源，信息流产品超级推荐也上线了，「人找货」进化到了「货找人」。2020 年开始，阿里妈妈针对直播类型的广告上线，同时开始推出互动激励广告，比如大家玩得比较多的互动游戏「双十一」叠猫猫。曲率空间学习框架也在这一年开源。

2022 年，阿里妈妈将整个广告引擎做了重大升级。广告引擎平台 EADS 和多媒体生产与理解平台 MDL 都上线了；在消费者隐私保护上，阿里妈妈的隐私计算技术能力获得了中国信通院认证。回顾阿里妈妈过去十五年的发展，可以看出，我们是一家「根正苗红」做计算广告的公司。

阿里妈妈有什么优势呢？在非常专业的电商场域，我们对用户和电商理解是非常强的，业务场景也非常丰富，除了传统的搜索推荐是传统，在直播推广、互动、新形态等数智业务场景上都有涉猎。此外我们的客户规模属于全球领先，几百万的商家都是阿里妈妈平台的广告客户。这些客户有非常多的需求，除了商家对经营的需求，还有各种各样的生态角色涉及其中，比如主播、达人或者代理商、服务商，他们以不同角色在这个平台里活跃。

我们在 AI 方面也有比较多的研究。这里介绍一下广告场景算法技术的特色。如上图，左边的倒漏斗型结构，很多做搜索或者推荐同学非常熟悉，这一部分广告和搜索推荐非常相似，包括广告召回、粗排序、精排序到机制策略的打分，涉及到信息检索等大量 AI 技术，特别是匹配上的 TDM 等召回模型都用了深度学习的技术。

其中包括决策智能，鉴于平台包含非常多的角色，各有各的博弈的关系，在多方关系和优化平衡之间，决策智能就派上了用场。用户体验、流量成本、预期收益、预算控制、跨域的融合，这些都是需要去博弈平衡的。

在这里我讲讲典型三个博弈 player。平台上博弈方有非常多，主要有三类：媒体、广告主、广告平台。

这三部分的核心技术可以总结为：从媒体角度，关注释放哪些媒体资源能够最好地平衡用户体验和商业化收入；从广告主角度，要优化什么，如何用最小的代价实现营销目标。那么，广告平台的最大目标是什么？长远来说，广告平台更底层的追求目标是让整个平台更加地繁荣，赚钱只是短期的事情，让这个平台长期繁荣才是最终目标，所以平台要平衡各方的关系，让各方的 player 在平台上很好地玩下去。

广告平台所要优化的目标涉及到很多机制设计。我今天会简单讲一下智能拍卖机制设计、智能出价策略、智能商业化策略三个方向，主要以科普的方式讲一讲阿里妈妈在这几年这上面的工作，供大家探讨。

智能拍卖机制设计。

先讲讲智能拍卖机制设计，这是很有趣的课题， 已经好多位前辈、大牛得了诺贝尔经济学奖。我们所谈的经典拍卖机制，从时间来看都是上世纪 70 年代之前出现的，那时候在线广告还没有出现，大家研究了很多关于单次拍卖或者静态拍卖的优化。这些机制通常都是单目标的，而且是针对单次拍卖。

无论是广告平台还是媒体，需要平衡用户体验和广告收入，典型的业界问题都是多目标优化，如果平台上涉及业务比较多，不同业务之间可能有平台策略和意志在里面，这也是多目标的优化。

从最开始用经典拍卖理论，比如用 GSP 或者 UGSP 方式去做流量分发和定价，业界逐渐演进到深度学习去解决这个问题。这些经典算法通过公式去计算平台对某个目标最优化的一些参数，有了深度学习的工具之后，拍卖机制设计本身也是一个可决策问题，其本身是解决决策问题的算法，但生产决策算法也是决策问题。

三年前，我们基于深度学习设计了一个 Deep GSP 拍卖机制，在满足机制良好性质的前提下提升；饿平台的效果，所谓机制性质良好是指激励兼容，广告主不用通过钻牛角尖或者是黑灰产方式获利，真实表达自己的意愿就能够拿到符合出价的流量。保持了激励兼容性质做的 Deep GSP，把原来静态公式换成了可学习的深度网络，这是第一阶段的工作。

到了第二阶段，拍卖机制网络里很多参数，我们通过训练优化的方式算出来。但实际上在整个过程中，除了参数计算还有排序，以及广告分配的过程，是整个系统完整的组成部分。部分模块其实是不可微的，比如排序模块，因此深度学习网络很难模拟它，为了端到端进行拍卖机制设计，我们把拍卖流程可微部分建模到神经网络，这样可以有梯度的反向传导，使得模型训练更加方便。

智能出价策略。

接下来讲一下智能出价策略，这是广告主用来调节效果或者博弈最主要的工具。中心化的分发无法表达诉求，但是在广告场景中这是有办法表达的。出价产品分为三个发展阶段：

最初的经典解法也是最古老的出价，希望预算花得比较平滑，让效果比较有保障，最初的时候业界是通过类似 PID 的控制算法，这是非常简单的算法，效果也比较有限。

等到了 2014、2015 年，再到 AlphaGo 打败人类之后，我们看到了强化学习的强大力量。智能出价是一个非常典型的序列决策问题，在预算周期内，前面花的好不好会影响到后面的出价决策，而这正是强化学习的强项，因此第二阶段我们用了基于强化学习的 bidding，通过 MDP 建模，直接用强化学习做这个事情。

第三个阶段就演进到了 SORL 这个平台，它的特点是针对强化学习中离线仿真环境与在线环境不一致。我们直接在在线环境中进行可交互的学习，这是工程设计和算法设计联合的例子。SORL 上线之后，很大程度上解决了强化学习强依赖于仿真平台的问题。

其他的技术特色还有工程基建部分，包括智能出价模型的训练框架、流批一体调控系统以及多渠道的投放图化在线引擎。工程体系和算法同样重要，离交易中心越近、越实时，越能够得到好的反馈，对于智能出价来说，工程基建部分越先进，越能帮助广告主获得更好的效果。

智能商业化策略。

最后讲讲与媒体相关的智能商业化策略部分。在商业化策略优化上，最初的尝试是把广告结果和自然结果进行加权融合，然后混合起来，根据不同的情况挑选去放。不合理的商业化机制对用户体验伤害很大，大家开始意识到这个问题。最近一两年，动态展现的策略逐渐流行起来了，随着深度学习等技术发展，我们可以通过优化决策算法做到平衡用户体验和商业化收入，在全域流量下去平衡用户的体验。

总体而言，在这三大方面，阿里妈妈形成了一张决策智能体系图，分为三个层面，智能拍卖机制是中间的桥梁，智能商业化策略解决的问题是拿出什么样的资源拍卖最高效，最能平衡好用户体验和商业化收入，智能出价策略是面向流量精细化出价的决策过程，通过出价参数的优化、基于真实环境的强化学习参数寻优，或 Target CPX、Max Return 等建模的范式进行优化。

面对现在的多轮拍卖和高频拍卖，很多基础理论有待进一步突破。说到基础机制理论突破，邓老师是这方面的专家，我们期待与邓老师一起在这方面做出前沿性的研究。从工程实际问题的挑战角度来看，实际环境要求在 200 毫秒返回结果，因此效率和效果上需要通过一些平衡，在工业界做得比较久对这个都有感触。

广告生态的优化是相对独立的，平台的最终目标是希望生态欣欣向荣、和平发展，做好了这几个，生态是否能达到预期呢？我想二者之间未必直接划等号。对于生态优化，仍然有很多理论和实际问题需要解决，这也是希望业界朋友们未来能够一起去探讨和解决的。

过去三年，阿里妈妈决策智能方向在顶级国际会议（NeurIPS、ICML、KDD、WWW 等）共发表近 20 篇论文，并与北京大学、上海交大、中科院、浙江大学等多所高校及研究机构展开合作，相关成果得到了工业界和学术界的广泛关注和跟进，在这个领域实现从跟随到逐步引领行业的技术发展。

相对于深度学习，决策智能在业界和学术界受到关注并没有那么多，所以借这个机会让大家更多了解这个领域，这个领域是非常有趣且有前景的。以上是阿里妈妈在决策智能方面的思考和工作，希望跟业界和学术界朋友一起分享，未来能更多地讨论，争取在决策智能的理论研究和业界实际应用上能够形成一些突破性的发展。