面向相似App推薦的列表式多核相似性學習算法①

卜 寧, 牛樹梓, 馬文靜, 龍國平

?

面向相似App推薦的列表式多核相似性學習算法①

卜 寧, 牛樹梓, 馬文靜, 龍國平

(中國科學院軟件研究所, 北京 100190)

相似App推薦可以有效幫助用戶發現其所感興趣的App. 與以往的相似性學習不同, 相似App推薦場景主要面向的是排序問題. 本文主要研究在排序場景下如何學習相似性函數. 已有的工作僅關注絕對相似性或基于三元組的相似性. 本文建模了列表式的相似性, 并將三元組相似性與列表式相似性用統一的面向排序場景的相對相似性學習框架來描述, 提出了基于列表的多核相似性學習算法SimListMKL. 實驗證明, 該算法在真實的相似App推薦場景下性能優于已有的基于三元組相似性學習算法.

相似App推薦; 多核學習; 相對相似性; 相似性學習; 列表式學習

智能手機和移動互聯網的廣泛普及, 帶動了移動應用(Mobile Application, 簡稱App)的飛速發展, 越來越多的用戶每天都要使用移動App, 但是用戶發現找到自己感興趣的App越來越困難. 相似App推薦可以有效緩解這個問題. 例如, Google Play應用商店在每個App的詳情頁面提供與該App相似的App列表. 然而, 如何定義兩個App之間的相似程度成為相似App推薦中的關鍵問題.

移動App本質是一個應用程序, 但實際上公開可獲得的只是其基本情況描述信息, 本文中稱為App的元信息. 這些元信息通常存在于移動App商店中, 包括名稱, 功能描述, 屏幕截圖, 用戶評論, 開發商, 用戶評分, 大小等信息. 因此本文所關注的移動App的本質是一個異質信息的聚合體. App相似性學習可以轉換為多元異質信息間的相似性學習.

已有的相似性學習算法可以分為基于特征的學習算法與基于核函數的學習算法. 前者側重于多元異質信息的表示學習, 后者更側重于如何融合多個異質的核函數. 本文采用主流的基于多元核函數的方法來學習App相似性, 優勢在于便于針對不同的信息采用合適的核函數, 有效的規避了信息間的異質性問題. 在面向排序的的相似性學習場景中, 給定目標對象a, 我們需要一個按與a相似程度, 從由高到低排序的列表, 而非與其中某個對象相似程度的一個具體值, 例如相似App推薦. 相似App列表整體質量的好壞是核心. 已有一些工作[1,2]關注于三元組形式的相對相似性, 如(a,b,c)描述了對于對象a來說, b比c更相似. 基于三元組的相似性學習算法將相似性學習的問題歸約為對于對象a, 對象b是否比c更相似的分類問題, 試圖優化分類錯誤. 這樣做只考慮了局部序的損失, 與我們所關心的排序列表的整體質量不一致, 因此本文提出直接建模排序列表(Listwise)質量, 將其作為優化目標, 來學習App相似性, 稱為SimListMKL. 在真實數據集上的實驗結果表明, 本文提出的SimListMKL算法要優于主流的基于三元組的相對相似性學習算法.

1 相關工作

相似性學習是一種有監督的學習方式, 它從已有的相似關系的對象中學習相似性函數, 度量兩個對象的相似程度[1]. 相似性學習所面向的任務有回歸, 分類與排序等. 本文主要關注面向排序場景的相似性學習. 基于特征的方法在于學習一個特征映射函數, 然后根據該映射定義相似性函數. 基于核函數的方法包括單核函數的方法與多核函數方法, 其中單核函數方法與基于特征的方法類似, 多核函數方法一般要優于單核方法, 但計算代價高. 因此本文主要從基于特征的方法(單核方法)與基于多核函數的方法兩方面闡述.

已有的基于特征的相似性學習的方法直接從成對的相似關系約束中學習相似性函數. 這些工作假設相似性度量的應用場景為回歸或分類, 因此大多將相似性學習的問題歸約為分類問題. 文獻[3]將臉部識別問題歸約為差分空間中的相似性判別二分類問題, 并采用SVM求解. 相似性神經網絡[5](Similarity Neural Network)提出采用前向多層感知機來學習一個非負且對稱的相似性度量, 其中非負性由輸出層的sigmoid激活函數保證, 對稱性由網絡結構的權重共享機制決定. 文獻[6]將相似性度量學習的問題轉化為對象的特征權重的學習問題, 優化目標是經過特征權重的線性變換使得相似的兩個對象距離盡可能小, 并約束不相似的兩個對象間的距離盡量大. 成對相似性關系大多是一種絕對的表示, 但是相對的相似性關系的比較是表達領域知識的更為自然的方式, 因為相似性的知識通常是模糊的, 只有相對意義上的表示. 對象a與對象b相似度比對象c與對象d之間的更高, 這一點很容易確定. 對于對象a與對象b之間是否相似給一個絕對的值要困難一些. 有些基于特征的相似性學習方法關注從這種相對的相似性關系中學習相似性函數. 文獻[7]考慮了將相對相似性約束應用到聚類問題中所面臨的可行性, 完備性以及信息量. 文獻[8]建模了這種相對相似性的領域知識, 將關于相對相似性的約束的均方殘差作為優化目標, 有效改善了聚類準確率.

基于多核函數的方法是目前解決該問題的主流方法. 基于多核函數的相似性學習通過對多個核函數進行綜合獲得最優的描述相似性的核函數[9,10]. 文獻[11]將學習多個核函數的組合權重的問題簡化為分類問題, 采用類似于AdaBoost的方法求解. 考慮到相似度量的非負性, 文獻[12]將成對對象作為訓練實例, 這樣每一個訓練實例都用若干核函數來描述, 采用epsilon不敏感回歸函數作為優化目標, 找到核函數的最優組合. 面向排序場景的多核函數方法大將相對相似性的比較作為監督信息來學習多個核函數的權重[1,2]. 考慮多核方法的計算代價高, SimApp[1]與OASIS[2]均建模hinge損失函數, 前者采用在線梯度下降的優化算法得到核函數權重稱為在線核函數權重學習(OKWL)方法, 后者采用在線的Passive-Aggressive算法求解.

2 面向排序的相似性學習框架

本文首先給出App相似性問題的形式化定義, 接下來基于多核學習思想, 提出了面向排序的相似性學習框架, 最后給出了具體實例.

2.1 App相似性學習問題形式化

描述App的元信息包括多種類型, 如名稱, 功能描述等為文本信息, 屏幕截圖為圖像信息, 用戶評分為數值信息等. App間的語義相似性直接由描述App的文本間, 圖像間以及文本與圖像間的語義相似性等決定. 因此本文將App相似性形式化為問題1.

2.2 面向排序的相似性學習框架

傳統的相似性學習問題認為相似性是絕對的, 例如a與b相似記為1, 不相似記為0, 因此采用分類或回歸算法求解相似性學習的問題. 在排序場景下, 相對相似性比絕對相似性要重要. 例如, 相似App推薦只需關心前個App比個之后的App相比, 與當前App更相似即可, 而不需要確定具體的相似性分值是1還是0.

無論是絕對相似性標注, 還是相對相似性標注, 采用相對相似性的形式進行組織訓練實例, 由此定義損失函數如公式(2)所示, 來學習App相似性函數中的核函數權重. 這就是面向排序的相似性學習框架. 以下是兩個具體的實例來說明相對相似性在損失函數中的建模.

2.3 基于三元組的相似性學習算法

本文以排序學習[13]中最常見的三類建模成對實例的方式來定義損失函數. 以一個查詢App的損失函數的定義為例來說明. 將代表與關系的D維核函數特征記為, 因此損失函數表示為.

①基于交叉熵的損失函數SimTripletNet

②基于指數函數的損失函數SimTripletBoost

③基于Hinge損失函數SimTripletSVM

(5)

已有的工作大多是采用的Hinge損失來從三元組中學習相對相似性[1,2], 根據采用不同的優化算法得到不同的算法. 本文中將他們統一稱為SimTripletSVM. 為了完備起見, 本文引入了其他可能的基于三元組的損失函數定義方式作為對比.

2.4 基于列表的相似性學習算法

中國汽車維修行業協會原會長康文仲，交通運輸部科學院原黨委書記、中國汽車保修設備行業協會原副會長王曉曼，中國汽車維修行業協會原會長孫守仁，中國汽車保修設備行業協會原副會長羅大柱 ，中國汽車保修設備行業協會原副會長張熙倫，中國汽車保修設備行業協會原副會長兼秘書長田國華，中國汽車維修行業協會常務副秘書長王逢鈴， 中國汽車保修設備行業協會原常務副秘書長劉蘊，中國汽車保修設備行業協會秘書長劉建農，中國汽車維修行業協會連鎖工委秘書長嚴雪月，廣東省道協機動車維修檢測分會會長羅少澤，北京汽車維修行業協會副秘書長侯金鳳及數十位國內知名汽保企業負責人作為嘉賓出席此次茶話。

基于三元組的相似性學習算法建模了三元組這樣的局部序, 所帶來的損失, 沒有考慮排序列表整體的質量. 基于三元組的算法將整個相似性列表拆分為三元組的形式, 將每個三元組作為一個訓練實例, 強制性的認為這些三元組服從獨立同分布假設. 本文將整個排序列表視為一個訓練實例, 采用基于位置的評價指標作為排序列表質量的度量, 將其作為優化目標, 采用LambdaMART定義損失函數的方式, 如公式(6)所示.

3 SimListMKL算法

本文采用SimListMKL算法來優化公式(6)所示的優化目標, 評價指標采用MAP, 為基于所有查詢App的AP(Average Precision)的平均. 因此這里的MAP的變化應該對應到AP的變化. 公式(7)給出了對于一個查詢App在已知其二值標注Y的情況下, 計算模型f產生的預測序的AP值.

(8)

SimListMKL算法采用MART來優化目標函數公式(6). MART是一類Boosting算法, 可以視為泛函空間的梯度下降算法.

SimListMKL算法 Input: the number of trees N; The number of leaves per tree L; Learning rate ; training samples Output: 1For do 2 For do 3 4 end 5end 6For t = 1 to N do 7 For q = 1 to Q do 8 For do 9 10 11 end 12 end 13 Obtain a L leaf tree from 14 Denoted as , where each leaf value 15 is 16 17end

如算法SimListMKL所示, 第1~5行描述了模型的初始化過程, 第6~17行描述了每一個迭代步生成一個用來公式(6)中損失函數的梯度的回歸樹, 該樹具有L個葉子節點, 葉子節點的值由Newton-Raphon更新步確定. 算法最終得到的即為本文要求解的App相似性函數.

4 實驗結果

為了驗證SimListMKL算法的有效性, 本文首先介紹了實驗設置. 接下來介紹了基于三元組相似性的多核學習算法與本文提出的基于列表相似性的多核學習算法, 在相似App推薦場景下的性能對比. 最后對比了各類算法性能受不同類型數據集的影響以及各類算法的運行時間.

4.1 實驗設置

實驗數據集采用的是SimApp[1]中所用的訓練數據集. 該數據集來源于Google Play的真實數據, 包括約13,000個查詢App, 每個查詢App下約20個App, 其中相似App的比例分布如圖1所示. 橫軸表示相似App的比例范圍, 如0.1對應的是相似App比例在0~0.1之間的查詢App的比例. App之間的相似性由10個核函數來刻畫, 包括名稱, 類別, 描述, 開發商, 屏幕截圖, 大小, 用戶評分, 用戶評論, 更新信息, 許可.

圖1 相似App比例分布

本文的主要基準算法是基于三元組的相似性學習算法, 包括SimTripletNet, SimTripletBoost, SimTripletSVM.盡管采用了相同的優化目標, 可是由于優化算法不同也有許多不同的變種, 如SimTripletSVM對應的OKWL算法與OASIS算法, 這里將它們統一從優化目標的角度命名. 基于交叉熵損失函數的SimTripletNet采用梯度下降優化算法求解, 基于指數函數損失的SimTripletBoost采用boosting優化算法求解, 基于hinge損失函數的SimTripletSVM采用切平面優化算法求解.

為了便于調參, 本文將該數據劃分為5份, 采用5折交叉驗證, 選取最優超參數, 即最后表中與圖中所展示的結果. 所有方法的最大迭代次數均設置為100次. SimTripletNet與SimListMKL中需要設置的學習步長從10-1, 10-2, 10-3, 10-4, 10-5中選取. SimTripletSVM中的C從103, 102, 10, 1, 10-1到10-5中選取. 本文提出的算法SimListMKL中的葉子數從2到20中選取. 實驗采用的基于位置的評價指標是Precision@1~10, 簡記為P@1~10以及MAP.

4.2 性能分析

本文將五折交叉驗證的結果分別展示在表1和圖2中. 表1描述了基于P@1~10的性能對比, 圖2描述了MAP作為評價指標的性能對比. 基于t-test的假設檢驗證明以下表和圖中的對比差異是顯著的.

表 1 Precision性能對比

圖2 MAP性能對比

表1的結果表明, 本文提出的SimListMKL方法普遍好于基于三元組的相似性學習方法. 以P@5為例, SimListMKL算法優于最好的SimTripletSVM算法約0.1%, 比最差的SimTripletNet算法約0.7%. 因此, 從Precision的度量角度來看, 基于列表建模損失函數在面向排序的相似性學習場景中是較好的選擇.

圖2展示的結果可以直觀的表明SimListMKL算法的優勢. 該算法高出SimTripletBoost約0.3%, 高出SimTripletNet約1%, 高出SimTripletSVM約0.3%. 因此, 從MAP的度量角度來看, 基于列表建模損失函數在面向排序的相似性學習場景中是較好的選擇.

4.3 敏感分析

性能分析的結果顯示, 算法在實驗數據集上的性能普遍較好. 根據已有的排序學習算法性能受數據集影響的研究[14]表明, 這主要歸因于訓練數據中正負例的比例均衡.

換句話說, 即每個查詢App對應的訓練實例集合中, 相似App的數量占一半左右.

本實驗試圖打破這種均衡, 研究在不理想的數據集上算法性能的變化. ratio表示每個查詢App對應的待比較App集合中相似App的數量比例. 按這個比例抽取查詢App, 分別構建ratio小于0.1, 0.2, 0.3, 0.4, 0.5的數據集, 對比各算法在這些數據集上的性能表現, 如圖3所示.

圖3展示了不同算法在ratio不同的數據集上MAP的變化曲線. SimListMKL算法對數據集是最不敏感的, 其從0.1到0.5, 僅變化了4.4%. 而變化最大的SimTripletNet變化幅度為18.6%. SimTripletBoost與SimTripletSVM居中, 變化約為6.2%. 由此可以看出, SimListMKL是一個穩定的算法, 不容易受數據集好壞的影響.

4.4 運行時間分析

本部分實驗對比了三元組的相似性學習算法與基于列表的相似性學習算法的訓練時間. 圖4展示了在Win7-64位操作系統, 4GB內存, i7-2600 CPU, 主頻3.4GHZ的環境下, 兩組算法分別采用五折交叉驗證時, 平均每折的運行時間(單位: 秒).

由圖4可得, SimTripletSVM運行時間最短約為2.8秒, 這一時間要遠遠好于同屬于基于三元組的相似性學習算法的SimTripletBoost(約14.2秒)與SimTripletNet(約28秒)算法. SimTripletSVM算法的高效一部分原因在于采用的是C實現, 而其他所有算法都采用的是Java實現.

本文提出的算法SimListMKL運行時間約為14.2秒, 與基于三元組的相似性學習算法SimTripletBoost相當, 遠遠好于SimTripletNet. SimListMKL與SimTripletBoost均采用了Boosting的優化算法, 而SimTripletNet采用了梯度下降算法. 可見, 影響運行時間的因素主要取決于優化算法的具體實現. 本文提出的SimListMKL優化目標雖然復雜, 并沒有給優化算法帶來太多額外的時間開銷.

5 結語

針對排序場景中的相似性學習問題, 本文總結出了一個基于相對序的相似性學習框架, 并提出了基于列表的多核相似性學習算法SimListMKL. 與已有的基于三元組相對相似性學習的算法相比, SimListMKL算法采用了一個更為概括的形式, 即列表的相對相似性, 并基于此建模了損失函數, 并采用MART算法優化. 實驗結果表明, SimListMKL是一種更好的建模相對相似性的方式, 提升了相似App推薦的性能, 同時保證較高的時間效率. 多核相似性學習方法的顯著問題是計算復雜度高, 下一步的研究工作主要是在線SimListMKL算法.

1 Chen N, Hoi S C H, Li S, et al. SimApp: A framework for detecting similar mobile applications by online kernel learning. Proc. of the 8th ACM International Conference on Web Search and Data Mining. ACM. 2015. 305–314.

2 Chechik G, Sharma V, Shalit U. Large scale online learning of image similarity through ranking. Journal of Machine Learning Research, 2010: 1109–1135.

3 https://en.wikipedia.org/wiki/Similarity_learning#cite_note-4.

4 Guo G, Li S, Chan K. Support vector machines for face recognition. Image and Vision Computing, 2001, 19(9): 631–638.

5 Melacci S, Sarti L, Maggini M, et al. A neural network approach to similarity learning. IAPR Workshop on Artificial Neural Networks in Pattern Recognition. Springer Berlin Heidelberg. 2008. 133–136.

6Xing EP, Ng AY, Jordan MI, et al. Distance metric learning with application to clustering with side-information. Advances in Neural Information Processing Systems, 2003, 15: 505–512.

7 Liu E Y, Zhang Z, Wang W. Clustering with relative constraints. Proc. of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM. 2011. 947–955.

8 Liu E Y, Guo Z, Zhang X, et al. Metric learning from relative comparisons by minimizing squared residual. 2012 IEEE 12th International Conference on Data Mining. IEEE. 2012. 978–983.

9 Lanckriet GRG, Cristianini N, Bartlett P, et al. Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research, 2004, 5(Jan): 27–72.

10 Ying Y, Zhou DX. Learnability of Gaussians with flexible variances. Journal of Machine Learning Research, 2007, 8(Feb): 249–276.

11 Tang Y, Li L, Li X. Learning similarity with multikernel method. IEEE Trans. on Systems, Man, and Cybernetics, 2011, 41(1): 131–138.

12 Chen LB, Wang YN, Hu BG. Kernel-based similarity learning. Proc. 2002 International Conference on Machine Learning and Cybernetics. IEEE. 2002, 4. 2152–2156.

13 Liu TY. Learning to rank for information retrieval. Foundations and Trends in Information Retrieval, 2009, 3(3): 225–331.

14 Niu S, Lan Y, Guo J. Which noise affects algorithm robustness for learning to rank. Information Retrieval Journal, 2015, 18(3): 215–245.

Listwise Multi-Kernel Similarity Learning Algorithm for Similar Mobile App Recommendation

BU Ning, NIU Shu-Zi, MA Wen-Jing, LONG Guo-Ping

(Institute of Software, Chinese Academy of Sciences, Beijing 100190, China)

Similar App recommendation is useful for helping users to discover their interested Apps. Different from existing similarity learning algorithms, the similar App recommendation focuses on presenting a ranking list of similar Apps for each App. In this paper, we put emphasis on how to learn a similarity function in a ranking scenario. Previous studies model the relative similarity in the form of triplets. Instead of triplets, we model the ranking list as a whole in the loss function, and propose a listwise multi-kernel similarity learning method, referred as SimListMKL. Experimental results on real world data set show that our proposed method SimListMKL outperforms the baselines approaches based on triplets.

similar App recommendation; multi-kernel learning; relative similarity; similarity learning; listwise learning

2016-04-14;收到修改稿時間:2016-05-12

[10.15888/j.cnki.csa.005502]