一、 技術背景
ctr（click-through-rate）即點選通過率，是網際網路廣告常用的術語，指網絡廣告（圖檔廣告/文字廣告/關鍵詞廣告/排名廣告/視訊廣告等）的點選到達率，即該廣告的實際點選次數除以廣告的展現量。點選率預估（click-through rate prediction）是網際網路主流應用(廣告、推薦、搜尋等)的核心算法問題，包括google、facebook等業界巨頭對這個問題一直進行着持續投入和研究。
ctr預估是網際網路計算廣告中的關鍵技術環節，預估準确性直接影響公司廣告收入。廣告領域的ctr預估問題，面臨的是超高維離散特征空間中模式發現的挑戰——如何拟合現有資料的規律，同時又具備推廣性。
二、 ctr預估算法現狀及進展
2.1 傳統ctr預估算法及不足
業界傳統的ctr預估解法是廣義線性模型lr(logistic regression，邏輯斯特回歸)+人工特征工程。lr使用了logit變換将函數值映射到0~1區間，映射後的函數值就是ctr的預估值。lr這種線性模型很容易并行化，處理上億條訓練樣本不是問題。但這種解法的不足是，因為線性模型的學習能力有限，需要引入大量的領域知識來人工設計特征以及特征之間的交叉組合來間接補充算法的非線性學習能力，非常消耗人力和機器資源，遷移性不夠友好。
另外，目前業界也有一些效果不錯的非線性模型不斷被提出來，并被工程實踐且取得不錯效果，但這些模型都或多或少存在一些不足。比如kernel方法，因為複雜度太高而不易實作；比如tree based方法，這個是由facebook團隊在2014年首先提出，有效地解決了lr模型的特征組合問題，但缺點就是仍然是對曆史行為的記憶，缺乏推廣性；還有fm（factorization machine）模型，能自動學習高階屬性的權值，不用通過人工的方式選取特征來做交叉，但fm模型隻能拟合特定的非線性模式，如最常用的2階fm隻能拟合特征之間的線性關系和二次關系。深度神經網絡非線性拟合能力足夠強，但面對廣告這樣的大規模工業級稀疏資料，适合資料規律的、具備推廣性的網絡結構業界依然在探索中，尤其是要做到端到端規模化上線，這裡面的技術挑戰依然很大。
那麼挑戰來了，如何設計算法從大規模資料中挖掘出具有推廣性的非線性模式？
2.2 阿裡媽媽自主研發mlr算法
2011-2012年期間，阿裡媽媽資深專家蓋坤（花名靖世）突破了主流大規模線性模型的思路，創新性地提出了mlr(mixed logistic regression, 混合邏輯斯特回歸)算法，引領了廣告領域ctr預估算法的全新更新。mlr算法創新地提出并實作了直接在原始空間學習特征之間的非線性關系，基于資料自動發掘可推廣的模式，相比于人工來說效率和精度均有了大幅提升。
mlr可以看做是對lr的一個自然推廣，它采用分而治之的思路，用分片線性的模式來拟合高維空間的非線性分類面，其形式化表達如下：
這裡面超參數分片數m可以較好地平衡模型的拟合與推廣能力。當m=1時mlr就退化為普通的lr，m越大模型的拟合能力越強，但是模型參數規模随m線性增長，相應所需的訓練樣本也随之增長。是以實際應用中m需要根據實際情況進行選擇。例如，在我們的場景中，m一般選擇為12。下圖中mlr模型用4個分片可以完美地拟合出資料中的菱形分類面。
mlr算法适合于工業級的大規模稀疏資料場景問題，如廣告ctr預估。背後的優勢展現在兩個方面：
1）端到端的非線性學習：從模型端自動挖掘資料中蘊藏的非線性模式，省去了大量的人工特征設計，這 使得mlr算法可以端到端地完成訓練，在不同場景中的遷移和應用非常輕松。
2）稀疏性：mlr在模組化時引入了l1和l2,1範數正則，可以使得最終訓練出來的模型具有較高的稀疏度， 模型的學習和線上預測性能更好。當然，這也對算法的優化求解帶來了巨大的挑戰，具體細節參見我們的論文（見文章尾部）。
2.3 mlr算法進階特性
在具體的實踐應用中，阿裡媽媽精準定向團隊進一步發展了mlr算法的多種進階特性，主要包括：
1）結構先驗。基于領域知識先驗，靈活地設定空間劃分與線性拟合使用的不同特征結構。例如精準定向 廣告中驗證有效的先驗為：以user特征空間劃分、以ad特征為線性拟合。直覺來講這是符合人們的認知的：不同人群具有聚類特性，同一類人群對廣告有類似的偏好，例如高消費人群喜歡點選高客單價的廣告。結構先驗有助于幫助模型縮小解空間的探索範圍，收斂更容易。
2）線性偏置。這個特性提供了一個較好的方法解決ctr預估問題中的bias特征，如位置、資源位等。實際應用中我們對位置bias資訊的模組化，獲得了4%的rpm提升效果。
3）模型級聯。mlr支援與lr模型的級聯式聯合訓練，這有點類似于wide&deep learning。在我們的實踐經驗中，一些強feature配置成級聯模式有助于提高模型的收斂性。例如典型的應用方法是：以統計回報類特征建構第一層模型，它的輸出(如下圖中的fbctr)級聯到第二級大規模稀疏id特征體系中去，這樣能夠有助于獲得更好的提升效果。
4）增量訓練。實踐證明，mlr通過結構先驗進行pretrain，然後再增量進行全空間參數尋優訓練，會獲得進一步的效果提升。同時增量訓練模式下模型達到收斂的步數更小，收斂更為穩定。在我們的實際應用中，增量訓練帶來的rpm增益達到了3%。
2.4 大規模分布式實作
mlr算法面向的是工業級的資料，例如億級特征，百億級參數，千億級樣本。是以我們設計了一套分布式架構，以支援模型的高效并行訓練。下圖是架構示意圖，它跟傳統的parameter server架構略有差別，主要不同點在于我們在每一個分布式節點上同時部署了worker和server兩種角色，而不是将server單獨剝離出去部署。這背後的考慮是充分利用每個節點的cpu和記憶體，進而保證最大化機器的資源使用率。
此外，針對個性化廣告場景中資料的結構化特性，我們提出并實作了common feature的trick，可以大幅度壓縮樣本存儲、加速模型訓練。例如下圖示意，在展示廣告中，一般來說一個使用者在一天之内會看到多條廣告展現，而一天之内這個使用者的大量的靜态特征（如年齡、性别、昨天以前的曆史行為）是相同的，通過common feature壓縮，我們對這些樣本隻需要存儲一次使用者的靜态特征，其餘樣本通過索引與其關聯；在訓練過程中這部分特征也隻需要計算一次。在實踐中應用common feature trick使得我們用近1/3的資源消耗獲得了12倍的加速。
三、 mlr在阿裡媽媽業務應用現狀
從2013年起，mlr算法在阿裡媽媽及阿裡集團多個bu的主要場景(包括阿裡媽媽精準定向廣告、淘寶客、神馬商業廣告、淘寶主搜等等）被大規模地應用和嘗試，尤其是在阿裡媽媽的精準定向廣告場景，算法模型創新帶來了業務上的重大突破，主要場景下的ctr和rpm均獲得20%以上的提升。典型應用如下：
3.1 基于mlr的定向廣告ctr預估算法
基于mlr算法的非線性學習能力，阿裡媽媽的定向廣告ctr預估采用了大規模原始id特征+mlr算法的架構。具體地，我們刻畫一次廣告展現為特征向量，它由三部分獨立構成：使用者部分特征（包括userid、profile資訊、使用者在淘寶平台上的曆史行為特征（浏覽/購買過的寶貝/店鋪/類目上的id和頻次等）、廣告部分特征（包括adid、campainid、廣告對應的賣家店鋪id、類目id等）、場景部分特征（包括時間、位置、資源位等）。這些特征之間無傳統的交叉組合，次元在2億左右。然後我們将資料直接喂給mlr算法，并且應用了結構化先驗、pretrain+增量訓練、線性偏置等進階技巧，讓模型從資料中自動去總結和拟合規律。實踐證明，相比于傳統的lr+特征工程思路，這種解法更為高效和優雅，模型精度更高，在實際生産中的可疊代更強。
3.2 基于mlr的定向廣告learning to match算法
match算法是定向廣告中的一個重要環節，它的核心使命是基于使用者的人口屬性、曆史行為等資訊來猜測使用者可能感興趣的廣告集合。傳統的match算法更多采用的是規則比對、協同過濾等方法，方法的擴充性不強。在阿裡媽媽定向廣告系統中，我們研發了基于mlr的learning to match算法架構。簡單來說，用模型的方法基于使用者的行為曆史來學習使用者個性化的興趣，進而召回高相關性的候選廣告集。同樣地，基于mlr算法的非線性能力，我們可以很容易地将不同的特征源、标簽體系融合到架構中，不需要過多地關注和設計特征的交叉組合，使得架構的靈活性大大增強。
四、 總結和挑戰
總的來說，阿裡媽媽算法技術團隊自主創新的mlr模型和算法，在阿裡媽媽業務中大範圍推廣和應用帶來了非常好的效果，另外在大資料智能方面，因為省去特征工程，具備了從資料接入到應用的全自動功能。
雖然目前取得了非常不錯的成績，但是未來的挑戰也不小：比如初值問題、非凸問題的局部極值、雖然mlr比lr好，但不知道和全局最優相比還有多遠；第二，在初值的pre-train方面需要改進和優化模型函數等等；第三，目前規模化能力方面也需要能夠吞吐更多特征和資料，比如采用更快的收斂算法等等；最後，整體的mlr算法的抽象能力也需進一步得到強化。
<a href="https://mp.weixin.qq.com/s/mtnhympvodaid9snhnlzuw">原文連結</a>