[發明專利]付費搜索中的投標和預算分配的聯合優化

有效

• 申請號: 201110416422.3
• 申請日: 2011-12-05
• 公開（公告）號: CN103136311B
• 公開（公告）日: 2017-12-19
• 發明（設計）人: 高斌;劉鐵巖
• 申請（專利權）人: 微軟技術許可有限責任公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06Q10/06;G06Q30/02
• 代理公司: 上海專利商標事務所有限公司31100
• 代理人: 黃嵩泉

技術領域

本發明涉及計算機領域，尤其涉及在線的付費搜索。

背景技術

付費搜索是在線廣告的一種常用形式，也是搜索引擎公司的主要收入來源。在付費搜索中，響應于給定的查詢，在搜索結果頁面中顯示一列廣告，以及有組織的十個藍色鏈接。盡管付費搜索結果是同時顯示的并且具有非常類似的外觀，但通過和有組織搜索不同的機制來產生付費搜索結果。一般而言，有組織的搜索結果主要基于每個網頁和查詢的相關度來生成，而付費搜索結果基于競拍來生成。

在付費搜索中，廣告客戶可以創建多個活動計劃并且為每個活動計劃設置一個預算。在每個活動計劃中，他/她可以進一步創建帶有投標關鍵詞和投標價格的幾個廣告組。數據分析顯示出，許多廣告客戶正在同時管理具有非常大量的關鍵詞和投標價格的大量活動計劃和廣告組。這些繁忙廣告客戶對搜索引擎貢獻了很大比例的收入，然而，也很可能并且很需要進一步改進他們的性能和貢獻。這主要是因為，當這一廣告客戶的活動計劃和廣告組的數量變得很大時，該廣告客戶手工地優化活動計劃預算分配并且為每個價格。

圖1示出付費搜索中的典型的廣告客戶帳戶結構。廣告客戶可以創建多個活動計劃。在每個活動計劃中，他/她設置一個活動計劃預算，構建幾組廣告副本，并且對每個廣告組的某些關鍵詞進行投標。每個關鍵詞是假定通過某些用戶查詢來觸發的一個競拍條目。給定一查詢，搜索引擎將首先根據投標關鍵詞和查詢之間的匹配函數，檢索最相關的廣告作為候選。然后，這些候選廣告將參與競拍，一些廣告(例如，具有最大預期收入的廣告)將獲勝并且被顯示在搜索結果頁面上。如果用戶點擊了一個廣告，則搜索引擎會向相應的廣告客戶收費。通常，收費數額由通用第二價格(GSP)競拍機制來確定，這意味著廣告客戶的一次點擊成本取決于競拍排序列表中的第二個廣告的投標價格。當一個活動計劃預算用完時，則在提高預算或者下一次預算周期啟動之前，將不允許該活動計劃參與任何競拍。例如，如果按月設置活動計劃預算，則活動計劃將在下個月重新參與競拍。

由此可見，除了創建廣告組并選擇投標關鍵詞以外，廣告客戶也應當謹慎地考慮以下兩個重要問題：

(1)投標價格設置。由于不同的關鍵詞對應于不同的機會(例如，搜索量)和不同程度的競爭，因此應當為這些關鍵詞設置不同的投標價格。然而，最優投標價格設置對于每個單獨的廣告客戶而言是最不可能的，因為他不能訪問相關信息且他的競爭者也在動態調整他們的投標價格。

(2)活動計劃預算分配。假定對于某一活動計劃，有許多高效用的關鍵詞(換言之，這些關鍵詞包含許多廣告機會)。為了實現關于這些關鍵詞的顯著性能，必須對它們付出許多錢。然而，如果不能提高這一活動計劃的預算，則會失去許多這樣的機會。于是，類似于關鍵詞的情況，不同的活動計劃也有不同的機會和競爭。結果，在一個帳戶下，一些活動計劃可能很快地用完預算，一些活動計劃很慢地消耗他們的預算，而其他活動計劃的預算可能根本不被使用。這顯然會限制廣告客戶使用他/她的預算的總體有效性。

以上兩個問題對于廣告客戶是關鍵的，然而，據數據統計，許多廣告客戶并未在這兩個方面做得很好。這是因為許多廣告客戶管理著上百種活動計劃和上萬個關鍵詞，使他們難以手工地調整活動計劃預算分配和關鍵詞投標價格。也曾嘗試在研究團體內自動地執行任務。然而，這些工作仍不足以滿足實際要求。例如，關于關鍵詞投標價格優化的許多工作僅在對廣告進行排序時考慮投標價格，而不將相關度和位置考慮在內。再例如，盡管人們研究了關鍵詞投標優化，然而盡我們所知，尚未有關于活動計劃預算分配的文獻。

發明內容

為了至少解決上述現有技術中的缺陷，本發明提出了一種新穎的方法來解決上述問題。特別是提出了聯合地優化活動計劃預算分配和投標價格設置。因此本發明將問題形成為一種受約束的優化，將活動計劃預算和關鍵詞投標價格作為變量，在帳戶級預算的約束下，對于具有多個活動計劃的給定廣告客戶帳戶以及帳戶級的預算，嘗試找到帳戶級預算向每個活動計劃的最優分配，并且同時為活動計劃中的每個投標關鍵詞設置最優價格，最終使廣告客戶的收入最大化。

為了更好的說明這一概念，首先定義了一些符號，包括成功價格區間，這是以下討論的基礎。然后采用一概率模型來計算給定投標價格的條件下贏得特定廣告位置的概率。此后，基于概率模型定義了優化問題，并將該問題轉換成有序二元編程問題。通過解決該問題，可以得到對活動計劃預算分配和投標價格設置的最后解決方案，即通過對預算分配和關鍵詞投標設置的聯合優化而最終使廣告客戶收入最大化。