轉轉商業化OCPC產品護航之路
一、廣告業務介紹
1.1 廣告的業務邏輯
廣告系統中的業務邏輯用一句話來表示：廣告主通過付費在媒體對目標用戶進行營銷信息傳達，達成營銷目的的過程。抽取出三個主體，廣告主、媒體和用戶，他們的關系如下：
其中，廣告主和媒體之間是買賣付費關系。媒體有很多流量，可以按點擊售賣也可以按曝光售賣，媒體根據自有流量制定了售賣機制。廣告主則通過售賣機制提供的投放方式，建立廣告投放計劃，并付費給媒體。媒體和用戶之間是有訪問展示關系的，媒體在什么時間什么場景以什么樣的方式的讓用戶看到什么樣的廣告，這是投放策略決定的。本次主要介紹的是轉轉商業廣告OCPC產品實現的一種投放策略。
1.2 廣告的系統架構
轉轉搜索廣告系統架構圖如下，平臺的投放策略由ZZADECPM模塊（紅框圈定）來承載。本文介紹的投放策略也在這個模塊實現。
1.3 業務背景
隨著轉轉廣告業務的發展，商家的營銷需求也不斷豐富起來。既要有托管的流量包產品去平衡平臺收益和實現小微商家利益最大化[1]，也要有滿足中大型廣告主對成本、收益、流量的有更多把控的優店通產品。為了不影響大盤推廣的效果，團隊業務同學聚焦二手平臺藍海品類，圍繞流量充足，物料不夠的現象，綜合產研、運營和銷售的能力和經驗，積極探索和制定了OCPC的拉新投放策略，為業務發展打開新局面，給予商家表達需求的機會，助力商家進行合理的成本控制，讓商家參與進來，盤活更多新商家。
1.4 目標及計劃
OCPC產品策略的目標有兩個，通過AB實驗的方式驗證目標是否達成。
- 1、大盤收入不降的情況下提升ROI；
- 2、提升有效填充（100%相關性）的ASN、收入和ROI；
各團隊合作完成該項目，具體動作：
1、產品同學負責設計產品方案、運營模式及后期迭代維護邏輯；
2、銷售和運營同學針對新產品進行售賣及運營話術設計和人員培訓；
3、技術同學負責調研合適的算法模型，設計合理可實現的優化目標，選擇匹配的策略方案：多重約束下的pid線性擬合控制方案[2]，也是本文要介紹的重點。
二、OCPC產品項目面臨的挑戰
下圖是廣告業務迭代的歷史脈絡。從2018年開始，在售賣機制/投放方式上，從最樸素的CPM/CPC類的廣告到衍生出來的基于流量預估價值去調整廣告的競價策略，即OCPM/OCPC這樣的平臺能力。為了滿足廣告主進一步對成本和預算控制的需求，本次是BCB（Budget Constrained Bidding）的又一次升級，MCB（Multi-Constrained Bidding）多約束下的競價策略。
本次項目環環相扣，需要打通產品、研發、運行和銷售各個環節，各方合力才能保障項目的正常運行。在具體實時過程中面臨的挑戰主要有以下幾個方面：
1）滿足廣告主成本需求及預算需求的同時需要考慮冷啟動期間要給予廣告主的優惠扶持策略；
2）配合產品同學，設計合理的算法邏輯，助力產品實現；
3）理解銷售和運營同學的話術，能夠用算法策略去進行保障；
4）算法策略要優先考慮大盤商家ROI，同時能嚴格把控平臺讓利規模；
5）優化目標中指標多約束多，算法策略設計及參數調整都有挑戰。
三、OCPC產品策略的實現方案
3.1 問題建模
OCPC項目目標抽象出來就是一個帶約束的線性規劃求最優解的問題。廣告主訴求：預算不超過B，cpc的成本不超過C的情況下，最大化GMV。原始問題 LP1建模如下：
寫出對偶問題 LP2（大同小異，互顛倒）如下：
根據互補松弛定理，得到兩個等式
然后，論文作者精心設計了出價公式，
帶入公式 8 轉化公式 10：
根據等式(10)，如果競價贏得了展示機會，則
并且
推導得到
如果競價輸掉了這次展示機會，結合公式 9 和公式 7，推導得到
說明最優解的公式設計巧妙且合理。至此，線性規劃問題 LP1 最優解的形式就求解出來了。
3.2 如何求解后驗數據的最優解及最優參數
這里會用到GNU Linear Programming Kit (GLPK)工具包，專門用來解線性規劃問題的。一開始使用的是開源工具包 pyomo+python[3]，對于小規模的問題，可以做到分鐘級別解出。簡單驗算完成后確認求解最優。但是當問題規模變大時，解答時間接近指數級增長。如下圖所示：
小規模問題編碼較為簡單，求解時間也可以接受。下圖是具體實現的偽代碼，索引集合、決策變量、參數、目標及約束條件，最后只需要調用 Objective 函數，輸入目標即可。
但是當問題規模變大時，耗時問題會嚴重影響進度，因此嘗試使用商業級軟件 GUROBI[4]。無論是原問題還是對偶問題，即使問題規模在10w以上，依然能夠在分鐘級解決問題。不由得感嘆，GUROBI 背后的算法優化的真是強大。具體安裝過程：
配置好環境后，就可以使用了。注意?。?！這里我使用的是商業版的，只有2個月的試用期。如果有持續性需求建議購買正版商業化產品。
下面是部分具體實現，求解對偶問題的代碼。跟PYOMO的編程語言風格較為類似。廣告主不同訴求對應的約束不同：
其中alpha和beta分別對應 p* 和 q*。通過后驗數據獲得的最優參數，后面會作為我們最優解公式的初始化參數。
3.3 最優出價參數分析
接下來，我們繼續講最優解的使用。
式中p和q對應的最優參數，可以根據后驗數據計算得到（3.2.3 節介紹），但是此時是對過去歷史數據的一個最優參數組合。對于未來的最優參數，需要我們自己去探索如何獲得；下面我們來分析最優出價公式中的 p 和 q 兩個參數對預算和點擊成本的影響。
當固定 q 時，從圖中可以看到，減小 p 時，cpc 出價整體提升，反之出價下降；p=0 時，表示沒有了 budget 這個約束。
當固定 p 時，從圖中可以看到，減小 q 時，cpc 出價隨之變化，cvr>C * p 時，高價值流量出價進一步提升，反之出價下降；增加 q 時，則正好相反，用高出價獲得了更多低 cvr 的流量，丟失了高 cvr 的流量。p=0 時，表示沒有了點擊成本這個約束。
分析以后，發現p 和 q 參數本身之間無法做到完全獨立。例如：當出價升高時，預算也會相應提高；如何調控 p 和 q 去優化我們的算法，目前主要有兩種解法：
- 強化學習的思路，通過設計狀態、動作及合理 reward 函數，進行參數控制，例如[5]；
- 反饋控制方法，也就是本文所采用多pid線性擬合控制方法。更有效的控制耦合效應的方法是MPC[6]方法，由于系統耗時等因素，未選該方案，本次介紹不涉及。
3.4 參數控制-pid 反饋控制系統
下圖介紹了兩種 pid 控制系統，對于獨立控制變量可以選用圖 6，本次主要介紹圖 7 的實現。
下面公式是標準 pid 的控制邏輯，公式 13、14、15 依次表示誤差，控制變量及系統輸入；
下圖是對 p 和 q 進行線性擬合的公式：
3.5 離線流程及線上部署
總結一下，3.1介紹了問題建模，3.2介紹了如何用工具求解最優解，3.3分析最優參數的意義，選擇合適的參數控制方法-pid反饋控制，3.4 pid控制系統介紹及使用
離線關鍵動作：
1、利用訓練數據及商用線性規劃優化器gurobi對原問題和對偶問題求解，得到對偶問題最優解p和q。
2、利用訓練數據進行最優參數尋找，模擬實時競價過程，p i d參數和擬合系數alpha、beta通過grid-search 進行找尋。
線上參數部署：
3、用1中參數初始化線上q和p，2中參數固定為線上參數；4、按小時級收集競價日志，計算預算和點擊/成交成本誤差，通過pid調控參數p和q；
整個流程基本就是這樣，具體細節不再這里展開。
四、總結
期間調研了拼多多 ocpc 的業務模式，優秀案例，總結理解他們的目標設計思路。為了保障項目成功，還與相關領域的專家技術進行了深入探討和交流，系統地整理了業界發展進程和最新研究，深入地了解了其他家 ocpc 項目的思路方法。為團隊技術賦能打下堅實的基礎。
OCPC 模式在二手商業廣告領域不斷擴展著自己的應用領域。本此項目是產品、研發、運營和銷售團隊通力配合的一個項目，算法策略肩負了核心邏輯實現的重任，是整個項目中順暢運行的潤滑劑。
最終結果，產品順利上線全量，并拿到預期的收益：針對有效填充部分的收益，收入、ASN 和 ROI 都有符合預期的提升: COST +4.61% CASH +4.58% ASN +8.64% TRUE_SHOW +12.16% GMV +23.73% ROI +17.86%；針對大盤的收益，收入持平，GMV 和 ROI 增長：收入持平，TRUE_SHOW +2.41% GMV +10.79% ROI +10.24%；
五、參考資料
[1] Zhu H. et al. 2017. Optimized Cost per Click in Taobao Display Advertising Proceedings of the 23rd International Conference on Knowledge Discovery and Data Mining. ACM, 2191--2200.
[2] Xun Yang, Yasong Li, Hao Wang, Di Wu, Qing Tan, Jian Xu, and Kun Gai. 2019. Bid optimization by multivariable control in display advertising. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1966–1974.
[3] Hart W E, Laird C D, Watson J P, et al. Pyomo-optimization modeling in python[M]. Berlin: Springer, 2017.
[4] https://www.gurobi.com/documentation/9.5/refman/py_python_api_details.html
[5] Di Wu, Xiujun Chen, Xun Yang, Hao Wang, Qing Tan, Xiaoxun Zhang, Jian Xu, and Kun Gai. 2018. Budget constrained bidding by model-free reinforcement learning in display advertising. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management. 1443–1451.
[6] James B Rawlings and David Q Mayne. 2009. Model predictive control: Theory and design. (2009).
