526
優化介紹及應用實踐
雲棲TechDay第33期，阿裏巴巴iDST Staff Engineer楊森帶來題為“優化介紹及應用實踐”的演講。本文主要從用戶需求開始談起，對婚姻配對算法進行了介紹，重點談及了分配問題、路徑規劃和組合優化等問題，最後總結了優化的重要性。
以上是精彩內容整理：
用戶需求
說起阿裏巴巴，第一個標簽肯定是電商平台。電商平台的核心問題就是如何關聯用戶、商品和賣家，是否成功的關鍵就是如何去高效率的匹配。如何高效率的匹配用戶和商品，這直接影射出兩個非常直觀的問題：
首先我們要知道用戶想要什麼，我們才能去高效的匹配用戶和商品。在大數據、沒有機器學習等技術沒有廣泛應用之前，最簡單的方法做一個簡單的統計，把一些非常受歡迎的商品列在頁麵的上麵，而這個在商業分析中可以稱之為一個描述性的分析，相當於去利用一個曆史數據來分析曆史上用戶的喜好。 最近幾年大數據機器學習廣泛的運用，使得我們可以精確的預測用戶的需求，可以做到“千人千麵”。
這就是一個比較常用的流程，首先我們有一些行為數據，包括交易信息、行為數據，甚至還有一些位置的信息，然後我們通過這些信息，用機器學習的方法就可以把用戶的畫像構建出來。 然後我們再通過一些實時的數據，一些上下文信息，比如說一個用戶前一個點擊和下一個點擊，這些上下文的信息再通過一些機器學習的技術，可以得到一個很好的預測。其實抽象起來無非就是一個輸入，然後去學習一個決策的函數，產生一個輸出。無論是Deep learning還是GBDT，都是可以抽象成這類的。 機器學習就是一個從數據中總結的重要的模式， 通過用戶的一些特征或者行為的交易數據、曆史數據，可以去預測用戶在將來需要什麼，而這個階段在商業分析中稱之為預測分析，就是如何通過曆史數據試圖去預測將來會發生什麼，比方說預測用戶的需求。
當我們知道了用戶的需求之後，下一步問題就是如何去匹配用戶的需求。我們知道用戶想要哪些商品，問題的關鍵是如何把這堆商品很好的提供給用戶，從而實現交易最大化。 其實有一個很簡單的場景，假如供是遠遠大於需的，作為平台我們為了實現交易最大化，貪心算法其實可以達到最優。 因為用戶過來的時候，我們可以把最好的、最希望買的東西展現給他，因為我們庫存是沒有限製的。 但很多現實的場景中，往往是供小於需的，就是說每個商店是有一些庫存量的限製，這樣就需要去決策，這個商品到底是給這個用戶還是給另一個用戶，從而達到一個全局上的最優，這就是一個優化的問題。 如何發現最優解，這個階段其實在商業分析中可以認為是第三個階段，規範式分析，或者稱為指導式分析，本質上如何通過仿真或者一些數學建模，希望能進行合理的智能決策，從而知道將來為什麼要發生、達到什麼目的、通過什麼形式達到這個目的，這是一個決策的過程。
優化算法：婚姻配對
說起優化算法， 婚姻配對是一個很好的例子。 其實準確來說，以上的圖片並不能囊括所有的關係。 我們把男女關係進行簡化，認為每個男的對每個女的都有一個排序，都有一個喜好程度，比方說，Bob最喜歡heiki大於geeta大於irina，女方也對男方有一個喜好排序。 如果我們要進行婚姻配對的時候，真實情況下我們不可能滿足每個人的需求，比方說屌絲比較喜歡女神，但女神並不一定喜歡屌絲，所以說我們不可能讓每個人都很happy。在這個例子中geeta是非常受歡迎的，男生Bob可能是比較受女生歡迎的，但這個配對隻能One to one，這是一個非常經典的問題，穩定婚姻的一個stable marriage，這個問題其實應用了很多的場景，比方說在美國醫科生如何配對醫院是通過這個模型去解的，還有高中生怎麼去選高中也是通過穩定婚姻模型去做的。我們得到一個穩定的婚姻配對，這樣可以盡量減少出軌這種不安定性的因素，假設Carl遇到了irina，irina會覺得Carl其實比David要好，David會覺得heiki比irina要好，這是一個非常不穩定的婚姻配對，通過這個問題說明我們優化問題：
第一，我們想讓多數人能happy，這其實就是一個優化目標；
第二，我們想讓婚姻配對盡量穩定，這其實就有一個約束條件。 優化很大程度上是如何去做一個tradeoff，在這個有限的空間裏麵去盡量找到一個最優解，就是優化目標。
婚姻配對問題有個經典的算法叫DA算法。 它的流程是，如果男生還沒有訂婚的話，讓男去向女求婚，第一次嚐試肯定是最喜歡的那個女生。 在男生求完婚之後，每個女生都會接受被求婚（也有可能這個女的沒有被求婚），女生會在自己的可選集中挑一個最好的，把其他拒絕掉。 如果男生被拒掉，那個男生可以下一輪繼續求婚，選擇下一個最喜歡的女生，候選人繼續求，但假設這個女生碰到的男生是比之前更好，她會把之前那個人踹掉，然後把最好的這個留住，通過這種流程，得出結果就是stable marriage。 怎麼說呢？這個算法如果是男的求婚，其實也被稱為Man optimal olgorithm，就是男生最優算法，即如果男生去求婚，得到好處最多。 這也就是說，幸福其實應該主動爭取的。 這個模型感覺很簡單，因為它隻需要一個排序，不需要一個量化的數字，但是假設我們知道Bob對每個人的喜歡程度或者幸福度可以量化，我們都可以知道一個數值的話，很明顯這個算法得出的結果並不是一個最優的，因為如果可以量化，可以通過一些建模的方式去解，廣告問題就是類似的，我們在在線展示廣告展示裏麵，它的核心就是如何去用有限的資源，達到整體最大化效益，因為每個廣告都有預算的。
每個用戶對於廣告都可以算出來一個喜好程度，或者稱之為回報，比方說我們能算出點擊的概率是多少。 CTR作為廣告的根本，預測已經可以做的很準。 假設我們的目標是想優化最大的點擊量，因為在有一些模式下， 廣告主需要為點擊付錢給平台。 如果整體的點擊數最大，相當於平台收益最多。 但這個問題我們有一個投放量的約束，就是說其實每一個廣告主的廣告都有一個預算，每天每個廣告主對廣告的投放量其實都有限製。
圖中為隻有兩個流量和兩個廣告的一個例子，比方說男生對兩個廣告的一個喜好程度CTR的預估，第一個廣告是0.8，第二個廣告是0.6；女生對兩個廣告喜好程度是0.7和0.2，如果沒有一個預算的約束，我想最大化整體的點擊數無非就是把這個最好的、最有可能被點擊的廣告分給兩個用戶，0.8和0.7，從而達到最優。 但是現實中我們是有一些約束的，假設約束是每個廣告隻能展現一次，這個廣告雖然喜好是0.8，但為了最大化點擊率依然不能分給他。
我們在線上的應用，其實就是供需關係的一個投放量，假設我們不考慮投放量約束的時候，比方說長棒是一個供，我的預算很多，廣告主其實想推廣我的產品，但產品有可能是一個新品，很多人不知道， CTR可能就很小。 我其實想推廣，但是可能沒有那麼多人去點，如果用貪心算法，就會造成供需不匹配。 如果要考慮投放量的約束，進行優化算法的優化之後，可以看到供需還是比較匹配的，我們在線上使用最優化算法之後，我們的收入是有15%的提升，這其實就是把流量和廣告進行一個調整。
分配問題：抽象
分配問題抽象也是比較經典的問題，給定一個二分圖，二分圖就是說一邊是用戶，一邊是廣告，可以稱為左邊有M個agents，右邊有N個Tasks，每個agent-task pair都有一個reward，其實最優化的任務分配其實就是一個最大化的總獎勵，但是它是有一些約束，這個task隻能分配給有限一個agents，在這個廣告例子上，就是說廣告隻能展現多少次，是有限製的，這個問題其實可以描述成一個整數規劃的問題。
Pij就相當於是一個Reward，假設A用戶和task配對，xij就是一個decision variable，一個決策的變量，它其實被限製為0和1. 如果是0就不展現，如果是1就應該展現，就是說不能超過預算， Customer來說明其實隻能分配一個，這是一個靜態的建模方式。如果問題比較小， 常用的solver也是可以直接求解。 但在如阿裏巴巴這種大數據情況下，廣告PV數其實是幾十億的，廣告數也是幾百萬，這些常用的solver並不很好的求解這樣大數據問題。 其實還有另外一個問題就是現實中很多應用是它不能事先獲得所有的數據，因此這種靜態的建模方式並不適用。 在我們很多實際的應用中，其實是動態的建模，比方說廣告這種情況用戶可能是隨時出現的，那麼，如何根據用戶的一些分數做一個實時的決策，去分配廣告呢？打車平台的用戶和司機是同時出現的，那怎麼去實時做一個分配匹對？
這是我們現實中的一些常用場景，是一個動態的在線分配問題，那這個模型T表示時間，表示按照每個時間點來進行的流量，這個問題的解可以有多種方式去解，比方說可以先積攢一部分數據，求解一個小的問題的對偶變量（或者稱為控製變量），然後通過控製變量去進行決策，即求解xij。 例如一小時數據的控製變量再去影射回原來那個問題，來進行算Xij。 通過這樣的情況，一旦得到控製變量之後，其實後麵的23個小時的決策都可以通過控製變量去進行實時決策。 我們算法可以證明這種在線的優化方式，長期優化一定是最優的 ： 假設問題夠大（預算夠大）， 在線最優解和理想靜態建模的最優解的誤差可以夠小。
其他應用
除了廣告，這種分配算法還有很多的應用場景。 其實準確來說，就是如何在有限的資源進行合理的分配。 這些例子包括消息推送，因為每個用戶每天push的個數是受限的，如何去最大化打開數？還有在線流量分配，購物券分發，購物券分發是有一些額度，我有一些cost，然後分給哪些人能給我們引流，給平台帶來的GMV最多，還有問大家的消息分發，其實說的是一個有約束的優化問題，如何在有限的資源進行合理的分配資源，進而達到一個最優的收益，這是電商場景中比較常見的優化算法。
路徑規劃
另一種優化方法就是路徑規劃，路徑規劃其實是一個非常傳統的圖優化問題，比方說我們從GPS去做一個導航，就是一個最短路徑的問題。 另外一個比較廣泛應用的路徑優化問題是車輛路徑規劃的問題， 就是我們有一個倉庫，每個用戶有很多的需求，盡量去用最少的車輛從倉庫出發，用最少的行車距離來滿足用戶的快遞需求。 車輛路徑規劃其實有很多應用場景，最直觀的就是訂單攬收，比方說上圖紅色點是一個深圳的訂單分布，然後我們做了一個調度分單，不同顏色每個是Driver去負責不同顏色的訂單攬收，然後進行路徑規劃之後，通過這種優化，整體的行車路徑接近節省50%。 這個問題其實也可以包括兩個部分，一是分配算法，一是最短路徑算法。
一個經典的路徑規劃問題，其實不僅僅是一個比較直觀的訂單攬收可以抽象成路徑規劃問題，比方說這個問題是一個訂單的波次，菜鳥每天在我們用戶購買發生交易之後，這個訂單會到倉庫的管理係統，可以抽象成就有一個訂單池子，訂單池子如何去進行波次，生成一個揀選單，讓它行走的距離最短。 如果路徑不是很好優化的話，揀選的效率會受到影響，所以這其實也可以轉化成路徑規劃的問題。 不過在整個鏈路中，其實這個問題可以模擬成三個問題：我們怎麼去分配，把這個訂單分配到每個揀選單裏麵，進而讓每個揀選單路徑最短。 這個問題也可以轉化成一個VRP的車徑路徑規劃問題的一種擴展，我們現在和菜鳥一起合作，開發了一個VRP Solver，可以支持多種VRP路徑規劃需求，包括經典的VRP，包括有時間窗口的VRP，有各種VIP的求解器，基準數據集評測優於開源Jsprit。
裝箱算法
再說一個組合優化的例子，叫裝箱算法，這也是一個非常經典的算法， 就是說我們怎麼把商品用最少的箱子去裝。 這在天貓超市有很大的應用場景，因為天貓超過一定限額是包郵的，為了超過限額，很多人都買很多東西，對於我們其實想用最少的箱子去郵寄，這樣就可以節省成本。 其實裝箱是物流成本非常核心的問題，而且Bin packing並不僅僅是物流上麵的問題，可以擴展到計算資源調度。 裝箱算法的目標是減少箱子個數、提高空間利用率和優化揀貨路徑，這些問題雖然看起來很基本，但這是非常難的問題，它解的好壞直接與商品個數和運行時間是成比例的，我們裝箱算法可以達到每單節省2毛到3毛，可以降低到耗材的15%，如果要把這個算法用到去年整量的數據，可以節省幾千萬。
我們剛才講三大類的優化問題：一種是分配問題，如何通過有限的資源合理分配，達到我們收益最大化，在阿裏有很多的應用場景；另一種是像bin packing這種組合優化問題，除了裝箱算法，還有一種類似於任務調度的組合優化問題；還有一種非常廣泛應用的路徑規劃，比方說O2O的送貨路徑怎麼規劃，其實也可以推動路徑規劃算法進行優化。
優化引擎
我們針對三類問題開發出了一個優化引擎來支持這三大類的問題，我們這種優化引擎現在已經有一部分的應用部署到雲端，如果有需求的可以進行試用。 我們在集團內部支持很多優化的需求，優化問題真的是無處不在的，阿裏每天有很多應用程序需要運行，像機器學習或者各種model、各種query都要去運行，那如何把這些應用程序分配計算資源，盡量用最少的計算資源去滿足計算需求，本質上就是最優化問題。
還有計算平台。比方說ODPS、Hadoop、Spark、flink其實都有一個資源調度的模塊，如何合理去調度資源，進而把效率提升，如果在計算平台上麵，還要用算法，基本可以認為機器學習和深度學習本身是有一個優化問題，優化就是機器學習的基礎。
在業務層麵也有很多的場景，像廣告消息的push message，還有物流，就是比較傳統的裝箱算法，去調度甚至路徑規劃；阿裏雲的智慧城市，比方說交通如何調度，紅綠燈如何調度等等，說明優化問題是無處不在的。
優化的重要性，第一是數據增值，我們可以充分的使用大數據來進行，比方說廣告投放，其實就是機器學習+優化的一個完美結合，通過預測用戶的一個點擊精確預測用戶的點擊，然後再通過優化算法進行優化，可以讓整體的平台收益達到最高。
另一個例子就是雲平台的增值服務，比方說計算資源如何管理，這本身就是一個很好的優化問題，hadoop等都有一個標配的調度模塊，我們可以針對業務場景做的更好，優化的另一個重要性是提升效率和降低成本，AWS從2014年開始每年都在降價，但是它的運營利潤率每年在上漲，從12.5%提升到23.5%，其實內部進行了大量的優化工作，還有數據中心的PUE每年都在持續的下降，因為對這種雲平台，成本的控製真正是一個核心的競爭力。
優化另一個重要作用是係統地平衡多目標間的tradeoff，比方說廣告收益和用戶體驗，一味的去追求收益，可能會影響用戶體驗，還有物流效率和費用等。
楊森：阿裏巴巴iDST Staff Engineer，美國亞利桑那州州立大學計算機博士學位，致力於優化和機器學習研究。2015年在加入阿裏巴巴後，參與並負責多個推薦項目的核心算法開發。從2016年開始，致力於開發和應用前沿的優化技術去更有效的使用和分配公共和私有資源，並負責開發和沉澱優化引擎。
最後更新：2017-05-17 09:31:12