近年来，随着广告主需求的变化和相关技术的发展，计算经济学理论、博弈论和人工智能技术越来越多地应用于广告竞价机制，放置策略。商业场景中决策智能的意义逐渐凸显。用户看到的每一个产品展示，商家的每一次广告竞价，平台上的每一次流量分配，都有庞大复杂的决策智能支撑。这些动作的目标是优化用户的购物体验，让广告的决策过程更加智能化，同时让广告商和媒体在平台上实现长期繁荣。广告主希望以有限的资源投入实现营销效果最大化，平台希望构建更好的生态。然而，流量环境的复杂性、其他竞争广告形成的竞争环境，以及广告投放策略中的出价、目标人群、资源位置、投放时间等变量的巨大组合复杂性，使得广告投放策略的计算和执行成为可能。充满挑战的最佳广告投放策略。挑战。如何解决这些问题？如何分解利益最大化的目标？这些与决策智能相关的重要问题也是该领域的研究人员和从业者最关心的问题。为深入探讨“数字智能商业场景中的决策智能”这一话题，近日，阿里妈妈博简社、机器之心邀请了北京大学邓小铁教授、中科院蔡绍伟研究员、阿里妈妈CTO郑波老师。课题组资深学者专家开展了系列主题分享。以下是邓小铁教授、蔡绍伟研究员、郑波老师的主题分享内容。机器之心在不改变初衷的情况下组织了它。邓小铁教授：计算经济学近期的几项研究进展。今天我就粗略介绍一下计算经济学。这是一个历史悠久的研究领域，可以追溯到1930年。后来的计算经济学从另一个角度出发，把经济学变成了计算。以前的计算经济学就是通过计算来做经济研究。这次我会谈谈这个想法。我们从计算的角度考虑经济学，有几个关键问题：第一，优化。机器学习就是优化，从中我们可以看到很多优化系统。优化之后，还有一个问题叫做均衡。过去我们是根据计划经济的思想来做计算经济学的。优化输入和输出的思想得到了扩展。从计算的角度计算均衡将是一个非常困难的问题，因此出现了一个叫做可计算一般均衡（Computablegeneralequilibrium）的概念。最近，我们可以看到越来越多的动力系统，因为这个世界上很多东西都不是处于均衡状态，而看到均衡的特别突出的场景是在数字经济活动中，包括经济学，比如定价。在数字经济中，每一秒都可以看到交易数据和价格波动。我们可以清楚地看到数据的变化，而不是一年过去了才去统计经济数据。计算经济学的整体框架还有很多。每个经济主体都必须是最优化的，它们共同博弈的不动点就是均衡点。该平台还将平衡游戏，尤其是互联网广告平台。广告商来到平台，通过平台和媒体投放广告。对于媒体来说，需要提供广告空间，利用其对某一特定人群的吸引力。对于平台来说，我们要思考的是如何更好的匹配大家的兴趣。作为国内最大的广告平台，阿里妈妈同样面临着游戏平衡的问题。需要安排各方利益，使社会效益最大化，机制设计效益最大化。我们可以从三个角度来谈优化。首先是经济主体特征的问题。机器学习中的很多东西都写成优化问题，比如如何用机器学习的方法来计算约束，包括一些环境下的约束。在不完全信息下，很多情况是未知的。原来的经济学不能考虑这么复杂的东西，比如博弈对手的利益函数是什么，博弈对手的策略空间是多少，博弈对手是谁？不完整信息描述经济活动也很重要。许多假设可以描述不完全信息，例如经济人知道对手的利益函数、约束条件等信息。关于彼此的利益函数有一个共同的知识：我们知道分布。但这种分布是如何产生的呢？这就进入了机器学习的领域：为什么玩家要告诉对方和我们它知道什么？针对这些，从计算的角度来看，有一些非常合理的问题。博弈动力学，这是计算经济学的第三步。从实体经济的经济学角度来看，很多活动经过6000年的演进和发展，大家慢慢地玩游戏，直到达到平衡。在数字经济中，一下子达到均衡是一个很大的挑战。广告平台优化是阿里妈妈在做的事情。讲了那么多难的计算任务，什么时候才能做好呢？在单参数的情况下，现有的理论可以支持，但是对于多参数如何做，并没有理论定义。很重要的一点是，整个经济学体系已经建立起来了，但是经济学应用到互联网上会有一个很大的缺陷——它是静态的。想必大家都知道，行业里的东西不是一成不变的。例如，“双十一”促销会带来很多挑战。如何设计红包的价格，如何根据市场上已知的模型来建立这些东西，已经成为当今计算经济学的重要问题。挑战：一是近似解优化，二是均衡规划，三是平台竞争动态。近似计算非常困难。我们知道的平衡解最多只能计算到三分之一，错误率最多33%，与最优相差33%，所以平衡计算真的很难。自动设计方法和隐藏对手模型学习是这方面的框架，它们都与信息容量有关。另一种是在市场上与不知名的对手进行博弈。我们至少要考虑两家公司，并建立一个模型来设计他们之间的博弈。这里很单调，我们不知道所有的信息。基于已知信息看到市场波动和价格设计变化，我们设计了一个基于此的隐函数优化模型，并使用机器学习方法进行分析。多方的认知顺序为我们带来了游戏的认知层次。近年来，一些研究讨论了单价拍卖优于双价拍卖的许多原因。迈尔森假设所有人都知道所有人的价值分配，但我们实际上并不知道公众的知识，从而发展了最优拍卖理论。我们自己的研究是从另一个角度考虑的。出发点是没有先验共同知识，放弃了最初使用概率方法建立迈尔森最优拍卖理论的假设。如果没有这个拍卖均衡的基本假设，最优解怎么可能达到均衡呢？可以发现，广义单价拍卖收益率等于迈尔森的收益率。这里，针对买方以效率最优为目标公布的价值分配，卖方设计的Myerson最优收益与其广义一价拍卖的预期拍卖收益相当。最后的结论是Myerson和GFP是等价的，比VCG好，但是在IID情况下相等，SymmetricBNE和GSP也是等价的。计算经济学中使用的另一个概念是马尔可夫博弈，一种动态环境中的博弈，特别是解决无限轮博弈的问题。我们从三个方向来处理这个问题：一是合理简化计算，将目标限制在一个近似解；二是利用时间贴现率保证无限轮收益收敛；三是利用数学分析阶段求和，将不同轮次的策略变化限制在一轮的变化中。这样就可以克服无限求和的困难。我们进一步简化了马尔可夫博弈应用中的计算难度。对于共识机制的设计，有明确的马尔可夫奖励分析，讲的很好。按照机制的设计，大多数人都支持是对的。但后来证明，大多数支持并不能保证经济安全。对于数字经济设计中的问题，我们最新的工作是可以使用InsightfulminingEquilibrium来克服它们，使用远见策略来达到最优，最后使用马尔可夫博弈的结构形成马尔可夫奖励过程并添加一个认知层面，从诚实矿池，自私矿池，再跨越一个层面，到达远见矿池的结果。同样，很多互联网公司要处理动态的东西，而不是静态的东西。今天的世界经济学已经不是以前的经济学了。此外，机器学习方法论和博弈论通过数学紧密结合。因此，我们已经从只能处理静态经济学转变为能够处理动态经济学。蔡绍伟研究员：一种求解大规模稀疏组合优化问题的高效方法大家好，今天分享的题目是一种高效的求解大规模稀疏组合优化问题的方法。许多决策问题的核心涉及组合优化问题，人们关注的是如何选择合适的组合方案来实现目标优化。求解组合优化的方法主要有两种：一种是启发式方法，包括启发式搜索和启发式构造。比如大家经常使用的贪心算法，就可以看成是一种启发式构造。);另一种是以brand-and-bound为代表的精确算法。启发式方法的优点是对尺度不敏感，因此可以对大规模问题使用近似解。缺点是你往往不知道游离的最优解有多远，你可能已经找到了最优解，但你没有头绪。分支定界完成。如果你给它足够的时间停下来，你就可以找到最优解，并证明它是最优解。但是这种方法是有代价的，它对规模比较敏感，因为这类算法呈指数级爆炸，往往不适合大规模问题。无论是搜索还是构建，大多数启发式算法框架都非常简单，主要取决于启发式如何设计以及遵循哪些准则。分支定界法主要在于如何做“边界”。你会发现很多BranchAndBound论文都在做bounding技术。如何使这个界限更紧可以更好地修剪解决方案空间。然后我想，你能把两者结合起来吗？也就是说，它既可以保持对尺度的不敏感，又可以加入bounding技术。大家很容易想到可以用预处理的方式，或者先做Heuristics再做BranchAndBound，用Heuristics的结果作为初始解等等。我们在这方面提出了一种新方法——启发式和分支定界中的嵌套迭代。简单来说，这种方法是先做一个粗略的启发式求解，求出一个初步的结果。一般来说，bounding需要上下界，Heuristics会粗略的得到一个下界，然后再设计上界的函数。假设这个问题的规模比较大，包含的元素很多，我们可以剔除其中的一些元素，让问题变小。然后再细化，继续做Heuristicsolving，可能会提高下界。在此基础上，算法可以多做一些绑定，继续嵌套。所以这个算法就变成了一个半精确算法，并且可以证明这是最优解，因为在某一步发现问题空间足够小，不用Heuristic就可以直接精确求解解决。另外，如果没有得到最优解，也可以知道最优解区间在哪里。下面给出两个例子来解释这个方法。第一个是“最大集团问题”。Clique是图论中一个非常经典的概念。在图中，点与点之间由边连接的子图称为团。最大团问题是找到最大的团。如果给它一个权重，给每个顶点分配一个权重，这样一个最大权重的clique问题就是找到总权重最大的clique。在下图的例子中，分别有四组和三组，第三组的权重更高，是这张图中权重最大的组。按照这个框架来做，我们需要两个子算法，一个是启发式求解，组里叫FindClique，另一个是简化算法，叫ReduceGraph。我们可以使用FindClique找到一个比前一个更好的团。当这个更好的组来到ReduceGraph时，我们知道最大的组至少有这么大。这一步也进行了简化。如果化简后图变空，说明找到的团是最优解；如果没有变空，那么可以减少一些点，然后回去调整找团的算法。这里的算法不一定是固定的算法，可以动态变化。我们的一个作品选择了“constructandcut”的方式，可以理解为多次贪心算法。multiplegreedy的作用是每次贪心构建可以非常快，可以从不同的起点开始，而且如果在某个构建过程中计算的话，无论当前组扩大多少，都不可能超过之前找到的组，我们将可以停止。最终目标是找到比以前更大的群体。heuristic是否应该更细化以及如何调整顺序取决于图的尺度，就像剥洋葱一样，剥到某一层再细化，从而有更大的Focus找到更好的组。当图无法再简化时，我们可以采用精确的算法，比如BranchAndBound。找到团后，根据我们的方法，我们需要做边界来丢掉一些点。方法是从一个点估计能发展出多大的派系，有不同的解法来解决。这两种边界估计技术是示例，您可以使用不同的技术来完成。实验方面，可以参考下表比较FastWClq、LSCC+BMS、MaxWClq的方法。解决相同精度的时间相差十几倍甚至几百倍。接下来看第二题：“GraphColoringProblem”。所谓着色就是给图形的每个点涂上一种颜色。两个相邻的点不能是相同的颜色。图着色问题讨论了有多少种颜色可以用来给图着色。最小的颜色数称为图形的色数。图着色问题有很多应用，尤其是在无冲突地分配资源方面。这个问题的大体思路是一样的——启发式解法加上一些边界技术。不同之处在于图形着色问题不需要子集。由于需要对整个图进行着色，因此不存在“永远扔掉”的概念。最后必须返回每个点，并且这个点必须有颜色。这里的reduce是把graph分解成Kernel和Margin：有个很简单的规则，还是和独立集有关。如果我知道这个图至少需要使用多少种颜色，也就是颜色下界（记为?），那么我就可以找到?-独立的度界集。这个独立集合中点的度都小于?，所以称为?-度界。如果你找到这样一个独立的集合，你可以放心地将它移到Margin中。找出kernel的解后，我们就可以很容易的将Margin纳入其中。如果核是最优解，那么组合也一定是最优解。该规则可以反复使用。我们看一个例子，这个例子中的四个灰色点就是内核，我们可以看到至少需要4种颜色。旁边的三个点放在边上，因为这三个点的度数都小于4，我们可以放心的把这三个点移到一边，不管它。然后发现剩下的子图没有分解，已经很硬核了，可以直接求解。稀疏图的硬核一般都不大，可以考虑用精确的算法来求解。如果找到核心，就知道核心至少使用了四种颜色。对于边上的点，每个点的度数都小于4，不管你怎么给它留一个颜色，都可以走一遍，线性时间就够了。向上。一直到最后，每一个剥离的Margin都要保留，而且要明确标明是哪一层，这点和第一题略有不同。我们需要使用额外的数据结构来保存这些边图。在最后一个untouchableKernel被准确求解后，我们可以使用倒序的方法先合并最后一个Margin，按照刚才的规则保留最优。如果Kernel是最优的，合并一条边仍然是最优的，一路往回走，原图的解也一定是最优的。当这个问题被框定后，剩下的就是考虑如何找到下界和上界了。算法的总体思路是：一开始kernel是原始图像，需要用最大clique算法寻找下界；剥离边缘后，可以使用贪心图着色算法找到上界。这里实际上使用了三种算法。在实践中，组合打孔法更为普遍。说到kernelcoloring，当图比较大的时候，我们可能会用greedy或者faster的方法来做，最后可能会变成一个精确的算法来做。整个过程中，下界和上界是全局的，如果这两个相等，就可以停止。上图是实验结果。可以看出在稀疏大图上效果更好，144个中的97个可以在一分钟内证明最优解。与同类算法相比，我们算法的比较时间也更快，而且在相对稀疏的大图像上有特殊的方法可以快速求解。以前大家都认为百万顶点的NP-hard问题一定要花很长时间。其实如果这些图很大但是有一定的特征，我们还是可以秒分分钟解决的。阿里妈妈CTO郑博：阿里妈妈不断升级的决策智能技术体系大家好，作为阿里妈妈的技术负责人，我将从行业的角度分享这几年阿里妈妈决策智能技术的进展。阿里妈妈成立于2007年，是阿里巴巴集团的核心商业化部门，也就是网络广告部门。经过十余年的发展，阿里妈妈打造了“搜索广告淘宝速递”这样具有影响力的产品。2009年有展示广告和AdExchange广告交易平台。2014年，数据管理平台Dharma出现，2016年开始全球营销。从技术上看，2015、2016年前后，阿里妈妈全面拥抱深度学习。从智能营销引擎OCPX，到自主研发的CTR预估核心算法MLR模型，都伴随着深度学习的方法进化而来。2018年，深度学习框架X-DeepLearning开源。2019年，欧拉图学习框架开源，信息流产品超级推荐也上线。“人找货”演变为“货找人”。2020年开始，阿里妈妈将投放直播广告，同时开始投放互动激励广告，比如大家玩的互动游戏“双十一”。曲率空间学习框架也在今年开源。2022年，阿里妈妈将对整个广告引擎进行重大升级。广告引擎平台EADS和多媒体制作理解平台MDL均已上线；在消费者隐私保护方面，阿里妈妈隐私计算技术已通过中国信息通信研究院认证。回顾阿里妈妈十五年的发展历程，我们是一家以“根正秒红”做算力广告的公司。阿里妈妈有什么优势？在非常专业的电商领域，我们对用户和电商的理解非常强，业务场景也非常丰富。除了传统的搜索和推荐，还有直播推广、互动、新形态等数字智能业务场景。玩水。此外，我们的客户规模位居全球前列，数百万商户在阿里妈妈平台投放广告。这些客户有很多需求。除了业务运营的业务需求，还涉及到各种生态角色，比如主播、专家，或者代理、服务商等。他们以不同的角色活跃在这个平台上。我们对人工智能也有很多研究。下面就介绍一下广告场景算法技术的特点。如上图，左边的倒漏斗结构，很多做搜索或者推荐的同学都非常熟悉。广告这部分与搜索推荐非常相似，包括广告召回、粗排序、细排序、机制策略打分，涉及信息检索等大量AI。技术，尤其是匹配上的TDM等召回模型，都采用了深度学习技术。这包括决策情报。由于平台包含多个角色，每个角色都有自己的游戏关系，决策智能在多方关系和最佳平衡之间派上用场。用户体验、流量成本、预期收益、预算控制、跨域融合都需要在游戏中进行平衡。这里我说说三个典型的游戏玩家。平台上的游戏玩家众多，主要分为媒体、广告商、广告平台三大类。这三部分的核心技术可以归纳为：从媒体的角度，关注发布哪些媒体资源最能平衡用户体验和商业收入；站在广告主的角度，优化什么，如何用最少的成本达到营销目标。那么，广告平台最大的目标是什么？从长远来看，广告平台的底层目标是让整个平台更加繁荣。赚钱只是短期的事情，让平台长期繁荣才是最终目标。因此，平台必须平衡好各方的关系，让各方玩家在平台上都能玩好。广告平台要优化的目标涉及到很多机制设计。今天简单说一下智能拍卖机制设计、智能竞价策略、智能商业化策略这三个方向。我主要以科普的方式讲讲阿里妈妈这几年的工作，供大家讨论。智能拍卖机制设计。先说智能拍卖机制的设计。这是一个非常有趣的话题。许多前辈和大腕获得了诺贝尔经济学奖。我们所说的经典拍卖机制，就时间而言，出现在1970年代之前。那时候网络广告还没有出现，大家研究了很多关于单次竞价或者静态竞价的优化。这些机制通常是单一目标且用于单一拍卖。无论是广告平台还是媒体，都需要平衡用户体验和广告收入。一个典型的行业问题是多目标优化。如果平台上涉及的业务很多，不同业务之间可能会有平台策略和意愿。这也是多目标的。优化。从一开始，经典的拍卖理论，如GSP或UGSP，被用于流量分配和定价，行业逐渐演变为深度学习来解决这个问题。这些经典算法使用公式来计算平台为某个目标优化的一些参数。有了深度学习工具，拍卖机制的设计本身也是一个决策问题。它是解决决策问题的算法，但生产决策算法也是决策问题。三年前，我们设计了一个基于深度学习的DeepGSP拍卖机制，在满足机制优良性的前提下进行了改进；饿了么平台的效果，所谓好的机制就是激励相容，广告主不需要通过牛角或者黑灰产品。盈利的方式，真正表达自己的意愿，就能得到符合出价的流量。保持激励相容性的DeepGSP，用可学习的深度网络代替了原来的静态公式。这是第一阶段的工作。在第二阶段，我们通过训练和优化来计算拍卖机制网络中的许多参数。但其实在整个过程中，除了参数计算和排序，还有广告分配的过程，它是整个系统不可或缺的一部分。有些模块实际上是不可微的，比如排序模块，所以深度学习网络很难模拟它。为了设计端到端的拍卖机制，我们将拍卖过程中可微分的部分建模到神经网络中，这样就有了反向梯度的传导，让模型训练更加方便。智能出价策略。接下来说说智能出价策略，这是广告主调整效果或者游戏的最重要的工具。集中分发无法表达诉求，但在广告场景中有表达诉求的方式。招标产品分为三个发展阶段：最初的经典方案也是最老的招标，希望预算花得更顺畅，效果更有保障。起初，业界采用类似PID的控制算法，是一种非常简单的算法，效果比较有限。等到2014年、2015年，AlphaGo战胜人类之后，我们才看到了强化学习的强大力量。智能出价是一个非常典型的顺序决策问题。在预算周期中，前期的支出好不好会影响后面的投标决策，这就是强化学习的强项，所以我们在第二阶段使用了强化学习的投标，通过MDP建模，直接用强化学习。第三阶段演变为SORL平台，其特点是强化学习中离线模拟环境与在线环境不一致。我们直接在在线环境中进行交互式学习，这是联合工程设计和算法设计的一个例子。SORL上线后，很大程度上解决了强化学习对仿真平台依赖性强的问题。其他技术特征包括工程基础设施，包括智能投标模型的训练框架、流批集成控制系统和多渠道交付地图在线引擎。工程系统和算法同样重要。离交易中心越近，越实时，您能得到的反馈就越好。对于智能竞价来说，工程基础设施越先进，越能帮助广告主获得更好的效果。智能商业化战略。最后说一下与媒体相关的智能化商业化策略。在商业化策略优化方面，最初的尝试是将广告结果与自然结果进行加权组合，然后混合在一起，根据不同情况进行选择。不合理的商业化机制对用户体验是非常有害的，大家也开始意识到这个问题。近一两年，动态展示的策略逐渐流行起来。随着深度学习等技术的发展，我们可以通过优化决策算法来平衡用户体验和商业收入，在全球流量的背景下平衡用户体验。总的来说，阿里妈妈在这三个方面形成了一张决策智能系统图谱，分为三个层次。智能拍卖机制是中间的桥梁。智能商业化策略解决的问题是拍卖什么样的资源最有效率，最能平衡用户体验和商业收益。智能竞价策略是一种精细化的面向流量的竞价决策过程，通过竞价参数优化、基于真实环境的强化学习参数优化，或者TargetCPX、MaxReturn等建模范式进行优化。面对当前的多轮拍卖和高频拍卖，许多基础理论有待进一步突破。说到基础机制的理论突破，邓先生是这方面的专家，我们期待与邓先生一起做这方面的前沿研究。从实际工程问题的挑战来看，实际环境要求在200毫秒内返回结果，所以需要在效率和效果上做一些平衡。我在这个行业工作了很长时间，我深有体会。广告生态的优化相对独立。平台的最终目标是希望生态蓬勃发展，和平发展。如果这些事情做好了，生态能达到预期吗？我认为两者之间没有直接的等号。对于生态优化，还有很多理论和实践上的问题有待解决，希望业内朋友今后能够共同探讨解决。近三年，阿里妈妈在决策智能方向国际顶级会议（NeurIPS、ICML、KDD、WWW等）发表论文近20篇，并与北京大学等多所高校和研究机构开展合作、上海交通大学、中国科学院和浙江大学。合作、相关成果得到了产学界的广泛关注和跟进，实现了该领域从跟随到逐步引领行业的技术发展。与深度学习相比，决策智能在工业界和学术界并没有受到如此多的关注，所以借此机会让大家更多地了解这个领域，这是非常有趣和有前途的。以上就是阿里妈妈在决策智能方面的思考和工作。希望与工业界和学术界的朋友分享。今后可以多多探讨，力争在决策智能的理论研究和实际应用上形成一些突破。
