決策智能技術(shù)浪潮襲來，數(shù)智商業(yè)領(lǐng)域如何變革？來聽聽三位專家怎么說（2）

蔡少偉研究員：一種求解大規(guī)模稀疏組合優(yōu)化問題的高效方法

大家好，今天我分享的題目是大規(guī)模稀疏組合優(yōu)化的高效方法。很多決策問題的核心都涉及組合優(yōu)化問題，人們很關(guān)注如何選擇合適的組合方案來達到目標最優(yōu)化。

求解組合優(yōu)化主要有兩類方法：一類是啟發(fā)式方法，包括啟發(fā)式搜索和啟發(fā)式構(gòu)造，比如大家經(jīng)常用的貪心算法就可以看作啟發(fā)式構(gòu)造的一種，貪心準則就是啟發(fā)式（heuristics）；另外一種是分支限界（brand-and-bound）為代表的精確算法。

啟發(fā)式方法的好處是對規(guī)模不敏感，所以可以用近似求解大規(guī)模的問題，缺點是往往不知道求出的解離最優(yōu)解有多大的差距，也可能已經(jīng)找到最優(yōu)解了，但是你不知道。Branch And Bound 是完備性的，如果你給它充足時間算到停下來，可以求出最優(yōu)解并且證明這是最優(yōu)解。但這個方法是有代價的，會對規(guī)模比較敏感，因為這類算法是指數(shù)爆炸的，往往不適用于大規(guī)模問題。

不管是做搜索還是做構(gòu)造，啟發(fā)式算法框架大多很簡單，主要是依賴于啟發(fā)式怎么設(shè)計，要根據(jù)哪個準則去做。分支限界方法主要在于怎么做「界」，大家看論文也會發(fā)現(xiàn)，很多 Branch And Bound 的論文在做 bounding 技術(shù)，怎么把這個界做得更緊，可以更好對解空間進行剪枝。

后來我想，可不可以把這兩個結(jié)合一下？也就是說，既能夠保持對規(guī)模不敏感，又能把 bounding 技術(shù)加進去。大家很容易想到，可以用預處理的方法，或者先做 Heuristics 再做 Branch And Bound，把 Heuristics 結(jié)果作為初始解等等。我們在這方面提出了一個新的方法 —— 嵌套地在 Heuristics 和 Branch And Bound 中去迭代。

簡單來說，這個方法先粗糙地做一個 Heuristic solving，求一個初步結(jié)果。一般來說，做 bounding 需要上下界，Heuristics 會粗糙得到一個下界，接下來通過設(shè)計上界的函數(shù)。假設(shè)這個問題規(guī)模比較大，包括很多元素，我們可以淘汰一些，使得問題縮小一圈。之后再精致一點，繼續(xù)做 Heuristic solving，這樣可能改進下界。在這個基礎(chǔ)上，算法可以再做一些 bounding，一直嵌套地做下去。于是這個算法就變成半精確算法，有可能可以證明這是最優(yōu)解的，因為在某一步發(fā)現(xiàn)問題空間足夠小，不需要 Heuristic solving 而是可以直接精確求解。另外，如果沒有求出最優(yōu)解，也可以知道最優(yōu)解的區(qū)間在哪里。

接下來舉兩個例子解釋這個方法。

第一個是「最大團問題」。團是圖論里很經(jīng)典的概念，在一個圖里，點和點之間都有邊相連的子圖，就稱為團，最大團問題是找到最大規(guī)模的團。如果給它一個加權(quán)，對每個頂點賦予一個權(quán)重，這樣的最大加權(quán)團問題是要找到總權(quán)重最大的團。下圖這個例子中，分別是四團、三團，三團的權(quán)重更大一些，也就是這個圖的最大加權(quán)團。

按照該框架來做這個事情，我們需要兩個子算法，一個做啟發(fā)式求解，在團里稱為 FindClique，另外一個是化簡算法，稱為 ReduceGraph。我們可以用 FindClique 找到一個團，這個團會比之前找到的要好。當這個更好的團走到 Reduce Graph，我們知道的是：最大團至少有這么大。也是在這一步做化簡，如果圖經(jīng)過化簡變?yōu)榭?，那么說明找到的團就是最優(yōu)解；如果沒有變?yōu)榭?，那么可以減少一些點，再回去調(diào)整找團的算法。這里的算法不一定是固定的算法，可以動態(tài)地變化。

我們的一項工作選了「construct and cut」的方法，可以理解為多次貪心的算法。

多次貪心的作用在于，每一次貪心構(gòu)造可以很快，可以從不同的起點出發(fā)，而且如果在某次構(gòu)造過程中算出來，當前的團再怎么擴展都不可能超過之前找到的團，我們就可以停止。最終目的是希望找到比以前大一些的團，啟發(fā)式要不要做得更精致以及順序如何調(diào)整，依賴于圖的規(guī)模，就像剝洋蔥一樣，剝到某一層再精化，以便有更大精力把更好的團找出來。當圖不能再化簡的時候，我們可以采取精確的算法，比如 Branch And Bound。找到一個團之后，根據(jù)我們的方法，我們要做 bounding 把一些點扔掉，方法在于估計點所能發(fā)展出來的團有多大，可以有不同方案去解決。

這兩個估界技術(shù)是作為例子，大家可以利用不同的技術(shù)去做。在實驗方面，可以參考下表，對比 FastWClq、LSCC+BMS、MaxWClq 這些方法，求解到相同精度的時間相差十幾倍甚至上百倍。

接下來看第二個問題：「圖著色問題」。所謂著色是給圖的每個點涂一個顏色，相鄰兩個點不能為同一個顏色，圖著色問題討論的是一個圖最少可以用多少種顏色來著色，最少顏色數(shù)叫做圖的色數(shù)。圖著色問題有很多應用，特別是在沒有沖突情況下分配資源。

這個問題大思路是一樣的 —— 啟發(fā)式求解加一些 bounding 的技術(shù)。不同的是，圖著色問題并不要求子集合，由于要對整張圖進行著色，所以沒有「永遠扔掉」這個概念，每個點最后都要返回去，這個點一定要有一個顏色。這里的 reduce 是把圖分解為 Kernel 和 Margin：

有一個很簡單的規(guī)則，還是與獨立集有關(guān)，我如果知道這個圖至少需要用多少種顏色，就是顏色下界（記為?），則可以找到?-degree bound 的獨立集。這個獨立集的點的度數(shù)都比?小，所以叫做?-degree bound。如果找到這樣的獨立集，可以放心移到 Margin 里面。如果把 kernel 的 solution 找出來之后，我們可以很方便把 Margin 合并進來，如果 kernel 是最優(yōu)解，合起來一定也是最優(yōu)解，這個規(guī)則可以迭代地去使用。

我們看一個例子，這個例子里面灰色的四個點是 kernel，可以看到至少需要 4 種顏色。旁邊的三個點放到邊緣上，因為三個點的度數(shù)都比 4 小，我們放心把這三個點挪到旁邊先不管。然后發(fā)現(xiàn)剩下這個子圖分解不動，已經(jīng)很硬核了，可以直接求解出來。稀疏圖的硬核一般都不大，所以可以考慮精確算法求解。如果把核心找出來，因為已知核心至少用四個顏色，對于邊緣中的點，每個點的度數(shù)小于 4，怎么樣都留有一個顏色給它，走一遍就可以了，線性的時間就可以了。

直到最后，每一次剝離的 Margin 都要保留下來，而且要標記清楚是第幾層，這是與第一個問題稍微不同的地方。我們要用額外數(shù)據(jù)結(jié)構(gòu)把這些邊緣圖保留下來，最后一個剝不動的 Kernel 精確化解決之后，就可以用倒序的方法，先把最后一個 Margin 給合并進來，根據(jù)剛才的規(guī)則保留最優(yōu)性，Kernel 是最優(yōu)的話，合并一個邊緣還會是最優(yōu)，一路回溯上去，那原圖的解也一定是最優(yōu)的。

當這個問題變成有框架的之后，就只剩下考慮如何找 lower bound 和 upper bound。算法的大致思路是：一開始 kernel 是原圖，需要用到最大團算法找一個 lower bound；剝掉邊緣之后，可以采取貪心圖著色算法，找一個 upper bound。

這里其實用到了三種算法。實踐中比較常見組合拳打法，具體到做 kernel 著色，當這個圖比較大的時候，我們可能通過某種貪心或者比較快的方法去做，最后有可能變成精確算法去做。整個流程中，lower bound 和 upper bound 都是全局的，如果這兩個相等，就可以停下了。

上圖是實驗結(jié)果，可以看出在稀疏大圖上面的效果更好，144 個中里有 97 個可以在一分鐘內(nèi)證明最優(yōu)解。跟同類算法相比，我們的算法對比時間也比較快，在比較稀疏大圖上面有特殊方法可以很快求解。大家以前認為，幾百萬頂點的 NP 難問題肯定要算很久，其實，如果這些圖很大但有一定特點的話，我們還是可以在秒級和分鐘級的時間內(nèi)解決的。

阿里媽媽 CTO 鄭波：阿里媽媽持續(xù)升級的決策智能技術(shù)體系

大家好，作為阿里媽媽技術(shù)負責人，我將從業(yè)界視角分享一下過去幾年阿里媽媽在決策智能技術(shù)上的進展。

阿里媽媽創(chuàng)立于 2007 年，是阿里巴巴集團的核心商業(yè)化部門，也就是在線廣告部門。經(jīng)過了十幾年的發(fā)展，阿里媽媽打造過「搜索廣告淘寶直通車」這樣有影響力的產(chǎn)品，2009 年有了展示廣告、Ad Exchange 廣告交易平臺，2014 年又出現(xiàn)了數(shù)據(jù)管理平臺達摩盤，2016 年開始做全域營銷。

從技術(shù)上看的話，在 2015 年、2016 年前后，阿里媽媽全面擁抱深度學習，從智能營銷引擎 OCPX 到自研 CTR 預估核心算法 MLR 模型，都是隨著深度學習的方法不斷演進的。2018 年，深度學習框架 X-Deep Learning 開源。2019 年，Euler 圖學習框架開源，信息流產(chǎn)品超級推薦也上線了，「人找貨」進化到了「貨找人」。2020 年開始，阿里媽媽針對直播類型的廣告上線，同時開始推出互動激勵廣告，比如大家玩得比較多的互動游戲「雙十一」疊貓貓。曲率空間學習框架也在這一年開源。

2022 年，阿里媽媽將整個廣告引擎做了重大升級。廣告引擎平臺 EADS 和多媒體生產(chǎn)與理解平臺 MDL 都上線了；在消費者隱私保護上，阿里媽媽的隱私計算技術(shù)能力獲得了中國信通院認證。回顧阿里媽媽過去十五年的發(fā)展，可以看出，我們是一家「根正苗紅」做計算廣告的公司。

阿里媽媽有什么優(yōu)勢呢？在非常專業(yè)的電商場域，我們對用戶和電商理解是非常強的，業(yè)務場景也非常豐富，除了傳統(tǒng)的搜索推薦是傳統(tǒng)，在直播推廣、互動、新形態(tài)等數(shù)智業(yè)務場景上都有涉獵。此外我們的客戶規(guī)模屬于全球領(lǐng)先，幾百萬的商家都是阿里媽媽平臺的廣告客戶。這些客戶有非常多的需求，除了商家對經(jīng)營的需求，還有各種各樣的生態(tài)角色涉及其中，比如主播、達人或者代理商、服務商，他們以不同角色在這個平臺里活躍。

我們在 AI 方面也有比較多的研究。這里介紹一下廣告場景算法技術(shù)的特色。如上圖，左邊的倒漏斗型結(jié)構(gòu)，很多做搜索或者推薦同學非常熟悉，這一部分廣告和搜索推薦非常相似，包括廣告召回、粗排序、精排序到機制策略的打分，涉及到信息檢索等大量 AI 技術(shù)，特別是匹配上的 TDM 等召回模型都用了深度學習的技術(shù)。

其中包括決策智能，鑒于平臺包含非常多的角色，各有各的博弈的關(guān)系，在多方關(guān)系和優(yōu)化平衡之間，決策智能就派上了用場。用戶體驗、流量成本、預期收益、預算控制、跨域的融合，這些都是需要去博弈平衡的。

在這里我講講典型三個博弈 player。平臺上博弈方有非常多，主要有三類：媒體、廣告主、廣告平臺。

這三部分的核心技術(shù)可以總結(jié)為：從媒體角度，關(guān)注釋放哪些媒體資源能夠最好地平衡用戶體驗和商業(yè)化收入；從廣告主角度，要優(yōu)化什么，如何用最小的代價實現(xiàn)營銷目標。那么，廣告平臺的最大目標是什么？長遠來說，廣告平臺更底層的追求目標是讓整個平臺更加地繁榮，賺錢只是短期的事情，讓這個平臺長期繁榮才是最終目標，所以平臺要平衡各方的關(guān)系，讓各方的 player 在平臺上很好地玩下去。

廣告平臺所要優(yōu)化的目標涉及到很多機制設(shè)計。我今天會簡單講一下智能拍賣機制設(shè)計、智能出價策略、智能商業(yè)化策略三個方向，主要以科普的方式講一講阿里媽媽在這幾年這上面的工作，供大家探討。

智能拍賣機制設(shè)計。

先講講智能拍賣機制設(shè)計，這是很有趣的課題， 已經(jīng)好多位前輩、大牛得了諾貝爾經(jīng)濟學獎。我們所談的經(jīng)典拍賣機制，從時間來看都是上世紀 70 年代之前出現(xiàn)的，那時候在線廣告還沒有出現(xiàn)，大家研究了很多關(guān)于單次拍賣或者靜態(tài)拍賣的優(yōu)化。這些機制通常都是單目標的，而且是針對單次拍賣。

無論是廣告平臺還是媒體，需要平衡用戶體驗和廣告收入，典型的業(yè)界問題都是多目標優(yōu)化，如果平臺上涉及業(yè)務比較多，不同業(yè)務之間可能有平臺策略和意志在里面，這也是多目標的優(yōu)化。

從最開始用經(jīng)典拍賣理論，比如用 GSP 或者 UGSP 方式去做流量分發(fā)和定價，業(yè)界逐漸演進到深度學習去解決這個問題。這些經(jīng)典算法通過公式去計算平臺對某個目標最優(yōu)化的一些參數(shù)，有了深度學習的工具之后，拍賣機制設(shè)計本身也是一個可決策問題，其本身是解決決策問題的算法，但生產(chǎn)決策算法也是決策問題。

三年前，我們基于深度學習設(shè)計了一個 Deep GSP 拍賣機制，在滿足機制良好性質(zhì)的前提下提升；餓平臺的效果，所謂機制性質(zhì)良好是指激勵兼容，廣告主不用通過鉆牛角尖或者是黑灰產(chǎn)方式獲利，真實表達自己的意愿就能夠拿到符合出價的流量。保持了激勵兼容性質(zhì)做的 Deep GSP，把原來靜態(tài)公式換成了可學習的深度網(wǎng)絡(luò)，這是第一階段的工作。

到了第二階段，拍賣機制網(wǎng)絡(luò)里很多參數(shù)，我們通過訓練優(yōu)化的方式算出來。但實際上在整個過程中，除了參數(shù)計算還有排序，以及廣告分配的過程，是整個系統(tǒng)完整的組成部分。部分模塊其實是不可微的，比如排序模塊，因此深度學習網(wǎng)絡(luò)很難模擬它，為了端到端進行拍賣機制設(shè)計，我們把拍賣流程可微部分建模到神經(jīng)網(wǎng)絡(luò)，這樣可以有梯度的反向傳導，使得模型訓練更加方便。

智能出價策略。

接下來講一下智能出價策略，這是廣告主用來調(diào)節(jié)效果或者博弈最主要的工具。中心化的分發(fā)無法表達訴求，但是在廣告場景中這是有辦法表達的。出價產(chǎn)品分為三個發(fā)展階段：

最初的經(jīng)典解法也是最古老的出價，希望預算花得比較平滑，讓效果比較有保障，最初的時候業(yè)界是通過類似 PID 的控制算法，這是非常簡單的算法，效果也比較有限。

等到了 2014、2015 年，再到 AlphaGo 打敗人類之后，我們看到了強化學習的強大力量。智能出價是一個非常典型的序列決策問題，在預算周期內(nèi)，前面花的好不好會影響到后面的出價決策，而這正是強化學習的強項，因此第二階段我們用了基于強化學習的 bidding，通過 MDP 建模，直接用強化學習做這個事情。

第三個階段就演進到了 SORL 這個平臺，它的特點是針對強化學習中離線仿真環(huán)境與在線環(huán)境不一致。我們直接在在線環(huán)境中進行可交互的學習，這是工程設(shè)計和算法設(shè)計聯(lián)合的例子。SORL 上線之后，很大程度上解決了強化學習強依賴于仿真平臺的問題。

其他的技術(shù)特色還有工程基建部分，包括智能出價模型的訓練框架、流批一體調(diào)控系統(tǒng)以及多渠道的投放圖化在線引擎。工程體系和算法同樣重要，離交易中心越近、越實時，越能夠得到好的反饋，對于智能出價來說，工程基建部分越先進，越能幫助廣告主獲得更好的效果。

智能商業(yè)化策略。

最后講講與媒體相關(guān)的智能商業(yè)化策略部分。在商業(yè)化策略優(yōu)化上，最初的嘗試是把廣告結(jié)果和自然結(jié)果進行加權(quán)融合，然后混合起來，根據(jù)不同的情況挑選去放。不合理的商業(yè)化機制對用戶體驗傷害很大，大家開始意識到這個問題。最近一兩年，動態(tài)展現(xiàn)的策略逐漸流行起來了，隨著深度學習等技術(shù)發(fā)展，我們可以通過優(yōu)化決策算法做到平衡用戶體驗和商業(yè)化收入，在全域流量下去平衡用戶的體驗。

總體而言，在這三大方面，阿里媽媽形成了一張決策智能體系圖，分為三個層面，智能拍賣機制是中間的橋梁，智能商業(yè)化策略解決的問題是拿出什么樣的資源拍賣最高效，最能平衡好用戶體驗和商業(yè)化收入，智能出價策略是面向流量精細化出價的決策過程，通過出價參數(shù)的優(yōu)化、基于真實環(huán)境的強化學習參數(shù)尋優(yōu)，或 Target CPX、Max Return 等建模的范式進行優(yōu)化。

面對現(xiàn)在的多輪拍賣和高頻拍賣，很多基礎(chǔ)理論有待進一步突破。說到基礎(chǔ)機制理論突破，鄧老師是這方面的專家，我們期待與鄧老師一起在這方面做出前沿性的研究。從工程實際問題的挑戰(zhàn)角度來看，實際環(huán)境要求在 200 毫秒返回結(jié)果，因此效率和效果上需要通過一些平衡，在工業(yè)界做得比較久對這個都有感觸。

廣告生態(tài)的優(yōu)化是相對獨立的，平臺的最終目標是希望生態(tài)欣欣向榮、和平發(fā)展，做好了這幾個，生態(tài)是否能達到預期呢？我想二者之間未必直接劃等號。對于生態(tài)優(yōu)化，仍然有很多理論和實際問題需要解決，這也是希望業(yè)界朋友們未來能夠一起去探討和解決的。

過去三年，阿里媽媽決策智能方向在頂級國際會議（NeurIPS、ICML、KDD、WWW 等）共發(fā)表近 20 篇論文，并與北京大學、上海交大、中科院、浙江大學等多所高校及研究機構(gòu)展開合作，相關(guān)成果得到了工業(yè)界和學術(shù)界的廣泛關(guān)注和跟進，在這個領(lǐng)域?qū)崿F(xiàn)從跟隨到逐步引領(lǐng)行業(yè)的技術(shù)發(fā)展。

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