決策智能技術浪潮襲來，數智商業領域如何變革？來聽聽三位專家怎么說（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 篇論文，并與北京大學、上海交大、中科院、浙江大學等多所高校及研究機構展開合作，相關成果得到了工業界和學術界的廣泛關注和跟進，在這個領域實現從跟隨到逐步引領行業的技術發展。

相對于深度學習，決策智能在業界和學術界受到關注并沒有那么多，所以借這個機會讓大家更多了解這個領域，這個領域是非常有趣且有前景的。以上是阿里媽媽在決策智能方面的思考和工作，希望跟業界和學術界朋友一起分享，未來能更多地討論，爭取在決策智能的理論研究和業界實際應用上能夠形成一些突破性的發展。