一種基于因子圖的搜索廣告轉化預測模型

顧智宇，秦 濤，王 斌

(1. 中國科學院 計算技術研究所，北京 100190；2. 微軟亞洲研究院，北京 100080)

?

一種基于因子圖的搜索廣告轉化預測模型

顧智宇1，秦 濤2，王 斌1

(1. 中國科學院 計算技術研究所，北京 100190；2. 微軟亞洲研究院，北京 100080)

基于轉化的廣告方式在應用和研究中逐漸得到重視，采用該方式的搜索廣告在廣告排序時需要對候選廣告的轉化概率進行預測，以提高廣告的轉化率，優化搜索引擎的廣告收益。該文在對搜索廣告中影響轉化的各特征進行提取與分析的基礎上，提出了描述廣告、查詢、用戶三個因素與轉化事件關系的概率因子圖模型，并基于該模型對廣告轉化進行預測。最后我們使用從某商業搜索引擎采集的實際數據對預測模型進行評價并與樸素貝葉斯方法進行對比，實驗結果表明，三類因素對轉化具有不同程度的影響，我們提出的因子圖模型可以較好地預測廣告的轉化。

搜索廣告；概率預測模型；CPA廣告

1 引言

互聯網廣告的形式主要有搜索廣告(Sponsored Search)、上下文廣告(Contextual Advertising)、展示廣告(Display Advertising)等。其中搜索廣告約占互聯網廣告總份額的46%，是互聯網廣告中最為重要的部分。并且，廣告收入尤其是搜索廣告收入是大部分搜索引擎公司的主要收入來源。例如Google在2010年的總營收中廣告收入所占比例在96%以上，在廣告收入中66%為搜索廣告收入。搜索廣告模式從早期的基于展示次數收費(Cost-per-mille，CPM)發展到當前主流的基于點擊收費(Cost-per-click，CPC)后，近年來提出了基于轉化收費的廣告模式(Cost-per-Action，CPA)。基于轉化的搜索廣告的流程如圖1所示。當用戶使用搜索引擎進行查詢時，搜索引擎將相關廣告展示于搜索結果頁面上，典型地在搜索結果的右側或上方。若用戶點擊感興趣的廣告，則將被帶到廣告的著陸頁。當用戶進一步在著陸頁上進行特定的動作，例如點擊著陸頁中的“下載”按鈕時，將觸發搜索引擎植入在著陸頁中的一段腳本，該腳本把用戶的本次動作反饋到搜索引擎，記錄為一次轉化，搜索引擎據此進行收費。被稱為轉化(Conversion or Action)的上述用戶特定動作由廣告商定義，常見的有購買商品、注冊信息、下載軟件等。對于廣告商， 由于CPA廣告在廣告產生效果后才支付廣告費用，減少了廣告的風險；而對于搜索引擎，CPA廣告能夠避免CPC廣告中可能出現的點擊欺詐現象[1]，因而近年來CPA廣告逐漸得到重視和發展。

圖1 基于轉化的搜索廣告的流程

(1)

在本文的余下部分中，首先在第2節介紹相關的研究工作，然后在第3節對影響轉化率的各因素進行分析，從中提取特征，第4節用描述因子圖用于轉化預測的概率模型，并在第5節給出相關實驗結果和分析，最后在第6節進行總結。

2 相關工作

目前為止針對廣告轉化預測的研究為數不多，而且尚未有面向搜索廣告的轉化預測研究。文獻[2]對展示廣告的點擊后轉化事件進行了分析，從廣告商、發布商、用戶等信息中提取特征，在進行特征選擇后建立最大熵模型對轉化事件進行預測。而文獻[3]則著重考慮了廣告的點擊/轉化預測中的數據稀疏性問題，針對性地提出了利用廣告商和發布商信息的層次樹結構對數據在不同層次上進行聚合的方法。但上述工作都是針對展示廣告進行，而搜索廣告與展示廣告有較大的差異，首先搜索廣告發布的形式不同，由于搜索廣告是在同一搜索引擎上發布，并不具備展示廣告在各種不同網頁上發布時的不同發布商信息，更重要的是，搜索廣告由于是被用戶搜索時所輸入的查詢所觸發，而用戶查詢是用戶意圖的重要指示，對廣告的轉化有較強影響，因此在進行搜索廣告的轉化預測時，必須對用戶查詢進行分析和利用。

目前對于搜索廣告的轉化主要集中在經驗性分析上，其中，文獻[4]分析了廣告的關鍵字對轉化率的影響，以幫助廣告商優化廣告。文獻[5]則分析了廣告的著陸頁與轉化率的關系，他們發現大部分著陸頁可劃分為廣告商主頁、搜索轉移(SearchTransfer)、分類瀏覽這三種類型，對Yahoo搜索廣告數據進行的統計表明不同類型的著陸頁的平均轉化率有明顯的差異。而文獻[6]則主要針對用戶查詢與轉化的關系進行了分析，通過回歸分析計算了查詢長度、查詢中是否包含特定關鍵字等特征與廣告轉化率的相關性。其結果表明某些特定關鍵字對轉化率有較大影響。但是上述工作都沒有建立理論模型來對搜索廣告的轉化進行直接預測。

圖2 廣告點擊率與轉化率的分布

針對CPC廣告的點擊預測已有較多的研究工作，如文獻[7-8]等提出了基于概率的點擊預測方法。然而廣告的點擊與轉化是兩個不同的事件，具有不同的性質和影響因素。通過利用某商業搜索引擎所記錄的兩個星期內的廣告展示、點擊與轉化數據，我們計算了廣告點擊率與轉化率分布，其中點擊率定義為廣告該時間段內點擊次數與展示次數之比，轉化率定義為廣告一定時間段內轉化次數與點擊次數之比，并在圖2中進行了對比。從圖中可見雖然大部分廣告都分布于轉化率/點擊率較低的區間，但轉化率的分布更為不均勻，曲線更陡。并且，廣告的點擊率與轉化率的關聯性很弱，具有高點擊率的廣告并不一定具有高轉化率，反之亦然。經計算，上述數據集的廣告點擊率與轉化率的相關系數僅為0.023。此外，影響廣告的點擊與轉化的因素并不完全相同。例如，如圖3所示，在上述廣告數據中可發現廣告的顯示位置對廣告的點擊率有大的影響，廣告在展示于搜索結果上方時點擊率明顯高于廣告顯示在結果右側，而對轉化率的影響卻很微小。因此，對于廣告的轉化預測，有必要對特征重新分析并建立不同的模型。

圖3 廣告顯示于搜索結果上方或右側對點擊率與轉化率的不同影響

3 影響轉化的特征分析

為了研究影響轉化的因素，我們對某商業搜索引擎的廣告日志進行采樣，分析各因素與轉化率的關系，從中提取用于預測廣告轉化的特征。廣告的轉化首先受廣告自身影響，例如廣告的內容和向用戶展示的廣告文本，尤其是著陸頁的類型和內容。其次是觸發廣告的查詢，包括查詢的意圖、查詢與廣告的相關程度以及查詢進行的時間等。由于轉化實際是用戶的行為，所以用戶因素也是影響轉化的原因，包括用戶的性別、年齡等個人信息，以及用戶的搜索歷史、廣告點擊歷史、廣告轉化歷史數據等。在文獻[7-8]等點擊率預測等工作中也曾使用了與廣告、查詢或者用戶相關的特征，但考慮到轉化率預測問題與點擊率預測問題的上述差異，本工作不僅增加了歷史轉化率、著陸頁文本、查詢時間及用戶轉化歷史等對轉化影響密切的新特征，并對特征重新分析，建立不同的模型，即利用因子圖進行預測。以下首先對這三組特征逐一分析。

3．1 廣告特征

不同內容的廣告的轉化概率有明顯不同，例如軟件下載廣告的轉化概率可能比銷售電器的廣告的轉化概率高很多。從搜索引擎的角度看，一個廣告包括三部分： 向用戶顯示的內容、用戶點擊后顯示的著陸頁、廣告數據庫中的元信息。廣告顯示的內容包括廣告的標題、正文和顯示URL。廣告數據庫中元信息包括廣告競價關鍵字、廣告商對廣告的出價、廣告所屬的廣告活動(Campaign)、廣告商ID等。從各部分中可提取下列與廣告轉化率相關聯的特征。

(2)

廣告標題與文本： 廣告的標題與文本同樣表示了廣告的內容，我們從廣告的標題和文本中提取有用詞項，同樣地使用上述方法計算相關系數并選擇前100個詞項作為二元特征。

著陸頁文本： 由于著陸頁對轉化有較大影響，因此我們抓取了每個廣告的著陸頁并提取其中的文本，同樣地用上述方法選擇前100個詞項作為特征。不同的是，由于在上面廣告標題與文本為短文本，我們僅將詞項出現與否作為二元特征，而在此著陸頁文本為較長的文本，因此使用詞項的TF-IDF值作為連續值特征。

廣告歷史轉化率： 大部分廣告的轉化率在時間上都比較平穩，這意味著可以使用廣告的歷史轉化率預測當前廣告的轉化。我們將廣告在過去一星期的轉化率的平均值作為廣告的歷史轉化率特征。

廣告出價： 圖4表示了廣告出價與轉化率的關系，其中橫軸表示廣告出價，正規化到(0, 1)區間，縱軸為轉化率。圖中轉化率與報價顯示出相關性。在(0,0.8)區間內，隨著廣告出價的提高，廣告的轉化率有上升的趨勢。這是因為轉化率高的廣告可以給廣告商帶來更多的收益，因此廣告商傾向于提高其報價。而在0.8以上的出價可認為是廣告商的競爭性出價而非合理出價，所以該區間的轉化率反而有所下降。由此，我們將正規化后的廣告出價作為轉化預測的一個特征。

圖4 廣告出價與轉化率的關系

3．2 查詢特征

如上所述，搜索廣告與網頁廣告的最大區別是搜索廣告由用戶的查詢所觸發，而查詢揭示了用戶當前的意圖，與轉化緊密關聯，例如具有購買意圖的用戶往往有更高的轉化率。查詢中所包含的影響轉化率的特征包括查詢本身的特征以及查詢與廣告的相關特征，如下所示。

查詢類別： 我們按照ODP目錄將查詢分類為12個類別，作為查詢的類別特征。圖5展示了每種類別所對應的廣告平均轉化率。可見各類別的平均轉化率有較大的差別，其中Business(商業)、Recreation(娛樂)、Shopping(購物)等具有商業意圖的類別的轉化率明顯高于Science(科技)等類別。

圖5 不同查詢類別的轉化率

查詢的歷史轉化率： 與廣告類似，查詢的歷史信息同樣可作為預測轉化的特征。除了查詢串本身的歷史轉化率之外，我們還對每個查詢中各詞項分別統計包含該詞項的查詢的歷史轉化率，將上述各詞項歷史轉化率的平均值和最大值作為特征。使用的歷史數據的時間窗口長度為一個星期。

查詢時間： 圖6表示一天中的查詢時間與轉化率的關系，在不同時間的查詢轉化率有明顯差別，10點左右的查詢轉化率最低，而晚上的轉化率則較高，這可以理解為人們在工作時間和休息時間對待購物的區別。因此我們將查詢在一天中的時間作為特征。

圖6 查詢時間與轉化率的關系

查詢與關鍵字的匹配類型： 搜索引擎在利用廣告的競價關鍵字與查詢匹配時，有多種匹配方式，包括查詢與關鍵字完全一致的精確匹配、關鍵字為查詢的一個子串的部分匹配、關鍵字為查詢的一個子集的寬泛匹配等。不同的匹配方式所返回的廣告與查詢的相關程度不同，導致轉化率有所不同，因此我們將匹配類型作為一個特征。

查詢與廣告文本的相似度： 除了使用競價關鍵字的匹配類型外，我們還考慮使用廣告的文本信息作為廣告與查詢的相關度的衡量。在此使用向量空間模型計算廣告文本與查詢的相似度作為特征，見式(3)。

(3)

其中wiq、wia分別是查詢Q和廣告A的文本的各詞項的TF-IDF值。

3．3 用戶特征

用戶特征包括兩類，一類為用戶年齡、性別、位置等用戶的個人信息，另一類為用戶的歷史記錄如用戶的搜索歷史和廣告點擊歷史。

愛德華·薩義德在《東方學》一書中，提出東方主義是與西方殖民主義和帝國主義緊密聯系在一起的西方關于東方的話語形式，通過使東方成為西方屬下的“他者”，使東方主義臣服于西方對東方的霸權統治。在東方主義話語中，東方國家被標以五花八門的消極特征：無聲、淫逸、陰弱、專制、落后、非理性。相反，西方則總是被賦予積極的特征：陽剛、民主、理性、道德、強悍、進步。在薩義德的后殖民理論中，西方人往往被稱為具有主體性的“自我”，殖民地人民則被稱為“他者”（薩義德 2007：1-36）。薩義德認為，在西方文學家或者學者眼里的“東方并非現實存在的東方，而是被東方化了的東方”（同上：136），是被西方控制的對象。

用戶性別、年齡： 我們將用戶以10歲為間隔劃分為八個年齡段，圖7中表示了不同年齡段用戶的轉化率。 從圖中可見，除了0-10歲區間，年齡較大的用戶具有較高的轉化率，這可能是因為該部分用戶經濟條件較好而具有較高的購買力。而對于0-10歲區間用戶，考慮到其使用搜索引擎、點擊廣告并發生消費的可能性，我們認為該年齡段的異常是由于用戶注冊搜索引擎帳戶時未正確填寫真實年齡所致，故不考慮該年齡段，將其余年齡段作為用戶的年齡特征。此外用戶的性別也作為特征之一。

圖7 年齡與轉化率的關系

用戶地理位置： 由于使用的廣告數據為英文廣告，受眾主要分布在英語國家，因此將用戶的地理位置劃分為美國、加拿大、英國、其他地區等四個范圍，將其作為地理位置特征。

用戶搜索歷史： 用戶的搜索提示了該用戶的興趣與關注點，把用戶最近一個星期內的查詢的集合視為表示用戶興趣的一個文檔，來計算其和廣告文本在向量空間模型中的相似度，計算公式仍為與3.2節中文本相似度計算公式(3)類似，其中wiq換成查詢集合文檔中詞項的權值。

用戶廣告轉化歷史： 為了表示用戶是否有在網上購物的習慣，我們對每個用戶統計了最近60天內的轉化次數作為用戶轉化特征。

4 轉化預測模型

基于上述特征，我們提出用于預測廣告轉化的概率模型，下面首先利用因子圖(FactorGraph)對模型的各層次進行描述，然后給出模型的學習和推斷的方法。因子圖[9]是概率圖模型的一種，它通過二分圖的形式表示函數與變量的依賴關系，二分圖中的一類頂點表示函數，另一類頂點表示變量，下面用實心框和空心圓區分這兩類頂點。頂點之間的連線表示依賴關系。借助因子圖我們可以將概率函數分解為各因子，用子圖清晰地表示各因子的關系，并能夠在其上利用消息傳播算法有效地進行概率推斷。

4．1 轉化預測模型描述

? 廣告得分：sa

? 用戶得分：su

? 總得分：s

其中，總得分由各因素得分決定：

(4)

上式中N(·)表示正態分布概率。通過f函數建立總得分s與子項得分sa,sq,su的聯系，即總得分s具有以w1·sa+w2·sq+w3·sa為中心，以β為標準差的正態分布。隱變量w1～3分別為各子項得分的權值，具有正態分布的先驗。因此，包含上述兩個函數的因子圖如圖8所示，它表示了總得分與子項得分的關系。

圖8 總得分與各子項得分的概率關系的因子圖

而子項得分將分別由廣告特征、查詢特征、用戶特征決定，即sa,sq,su由xa,xq,xu以及權值wa,wq,wu決定：

(5)

其中作為隱變量的wa,wq,wu也具有正態分布的先驗。上述函數的因子圖可分別用圖9中各圖表示。

圖9 各子項得分與特征的概率關系的因子圖

最后，我們使用logistic函數建立總得分s與轉化事件的概率關系，即給定s下的轉化概率為式(6)。

(6)

(7)

圖10 包含隱變量的聯合概率的因子圖

4．2 模型訓練與預測

5 實驗與分析

5．1 實驗數據與評價標準

實驗使用的數據來自于某商業搜索引擎，該搜索引擎的廣告服務器可獲取的日志信息中每天記錄了數千萬條點擊信息，并且記錄了與點擊相關的查詢信息與用戶信息，我們將從中采樣作為實驗數據，并進一步從中提取特征。我們從搜索引擎2011年12月的前兩周的廣告日志中隨機采樣了200 000條廣告點擊記錄作為實驗數據，每周各100 000條記錄，從中抽取轉化結果與特征。使用了轉化歷史信息的特征則從相應時間段的廣告日志中統計，例如12月5日的記錄所對應廣告的歷史轉化率的值將從11月28日至12月4日一個星期全部的廣告日志中統計。對于特征提取完成的數據，我們把第一周的數據用作訓練數據，第二周的數據作為測試數據。

(8)

(9)

(10)

而AUC值為ROC曲線(ReceiverOperatingCharacteristiccurve)下的面積，ROC曲線是表示測試中假陽率與真陽率關系的曲線，廣泛用于衡量分類器的性能。一般認為若AUC值在0.8以上則可視為較好的結果。

5．2 實驗結果

根據上述評價指標，我們將本文提出的概率預測模型與樸素貝葉斯(Na?veBayesian)方法進行對比。本概率預測模型采用Infer.Net實現[11]，樸素貝葉斯方法則使用weka工具包*http://www.cs.waikato.ac.nz/ml/weka/實現。

表1 模型性能對比

表1列出了概率預測模型與樸素貝葉斯方法下的相對信息增益和AUC值，圖11為兩者的準確率-召回率曲線。概率預測模型其準確率-召回率曲線在樸素貝葉斯的曲線之上，相對信息增益與樸素貝葉斯方法相比有23.3%的提升。概率預測模型的AUC值為0.852，可認為它能夠對轉化事件進行較好的預測。

圖11 準確率-召回率曲線

5．3 各因子對轉化預測的影響

為了分別考察廣告、查詢、用戶在轉化中的重要性，我們分別從模型中移除這三個因子，即從圖10的模型中依次移除圖9中代表廣告因子、查詢因子、用戶因子的三個部分，將移除后的模型與原模型進行對比。圖12表示了原模型與分別移除部分因子后的相對信息增益。從圖中可見， 移除任何一個因子后相對信息增益都有顯著降低，但各因子的影響并非完全相同。其中，移除查詢因子后性能下降最大，說明相對其他兩類因子，查詢在轉化預測中起到更重要的作用，證明了代表用戶當前意圖的查詢在轉化中的重要作用，這正是搜索廣告相對于上下文廣告的不同之處。相對地，移除用戶因子后性能下降相對較小，說明用戶的長期興趣對轉化的作用不如當前意圖的對轉化的作用大。

圖12 模型移除不同因子后對性能的影響

6 總結

在本文中，我們通過分析搜索廣告中影響廣告轉化的各因素，包括廣告因素、查詢因素和用戶因素，從中提取特征，并建立概率預測模型用三個因子描述上述因素，用以預測廣告的轉化概率。通過實驗證明了該模型具有較好的性能，有效地解決了基于轉化的搜索廣告的廣告排序問題。

[1] Mitchell D. Click fraud and halli-bloggers[J]. New York Times, 2005, July.

[2] Rosales R, Cheng H, Manavoglu E. Post-click conversion modeling and analysis for non-guaranteed delivery display advertising[C]//Proceedings of the fifth ACM international conference on Web search and data mining. 2012:293-302.

[3] Kota N, Agarwal D. Temporal multi-hierarchy smoothing for estimating rates of rare events[C]//Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining. 2011:1361-1369.

[4] Rutz O, Bucklin R. A model of individual keyword performance in paid search advertising[OL]. 2007. http://dx.doi.org/10.2139/ssrn.

[5] Becker H, Broder A, Gabrilovich E, et al. What happens after an ad click?: quantifying the impact of landing pages in web advertising[C]//Proceeding of the 18th ACM conference on information and knowledge management. 2009:57-66.

[6] Ghose A, Yang S. An empirical analysis of sponsored search performance in search engine advertising[C]//Proceedings of the international conference on Web search and web data mining. 2008:241-250.

[7] Graepel T, Candela J, Borchert T, et al. Web-scale Bayesian click-through rate prediction for sponsored search advertising in Microsoft’s Bing search engine[C]//Proceedings of the Twenty-Seventh International Conference on Machine Learning (ICML-10). 2010:13-20.

[8] Hillard D, Manavoglu E, Raghavan H, et al. The sum of its parts: reducing sparsity in click estimation with query segments[J]. Information Retrieval, 2011:1-22.

[9] Kschischang F, Frey B, Loeliger H. Factor graphs and the sum-product algorithm[J]. Information Theory, IEEE Transactions on, 2001, 47(2):498-519.

[10] Minka T. Expectation Propagation for approximate Bayesian inference[C]//Proceedings of the Seventeenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-01). San Francisco, CA: Morgan Kaufmann, 2001:362-369.

[11] T Minka J G, J Winn, Knowles D. Infer.NET 2.4[OL]. Microsoft Research Cambridge, 2010, http://research.microsoft.com/infernet.

A Factor Graph Based Conversion Prediction Model for Sponsored Search

GU Zhiyu1, QIN Tao2, WANG Bing1

(1.Institue of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China; 2. Microsoft Research Asia, Beijing 100080, China)

The CPA (Cost-per-Action) Advertising is attracting more and more attention in both industry and research. Sponsored search based on CPA requires predicting conversion probability for each candidate ad during ad ranking, in order to raise conversion rate and optimize ad revenue for search engine. After extracting and analyzing features which may influence conversion of ads, we propose a probabilistic factor graph based model for ad conversion prediction which describes the relation between the conversion event and three factors, i.e. ad, query, and user. The model is evaluated and compared with Naive Bayesian method on real-world data gathered from a commercial search engine. The experiment demonstrates a good result in the ad conversion prediction, as well as different influences of the three factors.

sponsored search；probabilistic prediction model；CPA advertising

顧智宇(1981-)，博士研究生，主要研究領域為信息檢索、計算廣告學。E?mail：guzhiyu@ict．ac．cn秦濤(1981-)，博士，研究員，主要研究領域為互聯網經濟、博弈論、機器學習、信息檢索和計算廣告學。E?mail：taoqin@microsoft．com王斌(1972-)，博士，研究員，主要研究領域為信息檢索與自然語言處理。E?mail：wangbin@iie．ac．cn

1003-0077(2015)03-0140-10

2012-04-18 定稿日期： 2012-07-16

TP391

A