面向相似App推薦的列表式多核相似性學(xué)習(xí)算法①

卜 寧, 牛樹(shù)梓, 馬文靜, 龍國(guó)平

?

面向相似App推薦的列表式多核相似性學(xué)習(xí)算法①

卜 寧, 牛樹(shù)梓, 馬文靜, 龍國(guó)平

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

相似App推薦可以有效幫助用戶發(fā)現(xiàn)其所感興趣的App. 與以往的相似性學(xué)習(xí)不同, 相似App推薦場(chǎng)景主要面向的是排序問(wèn)題. 本文主要研究在排序場(chǎng)景下如何學(xué)習(xí)相似性函數(shù). 已有的工作僅關(guān)注絕對(duì)相似性或基于三元組的相似性. 本文建模了列表式的相似性, 并將三元組相似性與列表式相似性用統(tǒng)一的面向排序場(chǎng)景的相對(duì)相似性學(xué)習(xí)框架來(lái)描述, 提出了基于列表的多核相似性學(xué)習(xí)算法SimListMKL. 實(shí)驗(yàn)證明, 該算法在真實(shí)的相似App推薦場(chǎng)景下性能優(yōu)于已有的基于三元組相似性學(xué)習(xí)算法.

相似App推薦; 多核學(xué)習(xí); 相對(duì)相似性; 相似性學(xué)習(xí); 列表式學(xué)習(xí)

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

移動(dòng)App本質(zhì)是一個(gè)應(yīng)用程序, 但實(shí)際上公開(kāi)可獲得的只是其基本情況描述信息, 本文中稱為App的元信息. 這些元信息通常存在于移動(dòng)App商店中, 包括名稱, 功能描述, 屏幕截圖, 用戶評(píng)論, 開(kāi)發(fā)商, 用戶評(píng)分, 大小等信息. 因此本文所關(guān)注的移動(dòng)App的本質(zhì)是一個(gè)異質(zhì)信息的聚合體. App相似性學(xué)習(xí)可以轉(zhuǎn)換為多元異質(zhì)信息間的相似性學(xué)習(xí).

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

1 相關(guān)工作

相似性學(xué)習(xí)是一種有監(jiān)督的學(xué)習(xí)方式, 它從已有的相似關(guān)系的對(duì)象中學(xué)習(xí)相似性函數(shù), 度量?jī)蓚€(gè)對(duì)象的相似程度[1]. 相似性學(xué)習(xí)所面向的任務(wù)有回歸, 分類與排序等. 本文主要關(guān)注面向排序場(chǎng)景的相似性學(xué)習(xí). 基于特征的方法在于學(xué)習(xí)一個(gè)特征映射函數(shù), 然后根據(jù)該映射定義相似性函數(shù). 基于核函數(shù)的方法包括單核函數(shù)的方法與多核函數(shù)方法, 其中單核函數(shù)方法與基于特征的方法類似, 多核函數(shù)方法一般要優(yōu)于單核方法, 但計(jì)算代價(jià)高. 因此本文主要從基于特征的方法(單核方法)與基于多核函數(shù)的方法兩方面闡述.

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

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

2 面向排序的相似性學(xué)習(xí)框架

本文首先給出App相似性問(wèn)題的形式化定義, 接下來(lái)基于多核學(xué)習(xí)思想, 提出了面向排序的相似性學(xué)習(xí)框架, 最后給出了具體實(shí)例.

2.1 App相似性學(xué)習(xí)問(wèn)題形式化

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

2.2 面向排序的相似性學(xué)習(xí)框架

傳統(tǒng)的相似性學(xué)習(xí)問(wèn)題認(rèn)為相似性是絕對(duì)的, 例如a與b相似記為1, 不相似記為0, 因此采用分類或回歸算法求解相似性學(xué)習(xí)的問(wèn)題. 在排序場(chǎng)景下, 相對(duì)相似性比絕對(duì)相似性要重要. 例如, 相似App推薦只需關(guān)心前個(gè)App比個(gè)之后的App相比, 與當(dāng)前App更相似即可, 而不需要確定具體的相似性分值是1還是0.

無(wú)論是絕對(duì)相似性標(biāo)注, 還是相對(duì)相似性標(biāo)注, 采用相對(duì)相似性的形式進(jìn)行組織訓(xùn)練實(shí)例, 由此定義損失函數(shù)如公式(2)所示, 來(lái)學(xué)習(xí)App相似性函數(shù)中的核函數(shù)權(quán)重. 這就是面向排序的相似性學(xué)習(xí)框架. 以下是兩個(gè)具體的實(shí)例來(lái)說(shuō)明相對(duì)相似性在損失函數(shù)中的建模.

2.3 基于三元組的相似性學(xué)習(xí)算法

本文以排序?qū)W習(xí)[13]中最常見(jiàn)的三類建模成對(duì)實(shí)例的方式來(lái)定義損失函數(shù). 以一個(gè)查詢App的損失函數(shù)的定義為例來(lái)說(shuō)明. 將代表與關(guān)系的D維核函數(shù)特征記為, 因此損失函數(shù)表示為.

①基于交叉熵的損失函數(shù)SimTripletNet

②基于指數(shù)函數(shù)的損失函數(shù)SimTripletBoost

③基于Hinge損失函數(shù)SimTripletSVM

(5)

已有的工作大多是采用的Hinge損失來(lái)從三元組中學(xué)習(xí)相對(duì)相似性[1,2], 根據(jù)采用不同的優(yōu)化算法得到不同的算法. 本文中將他們統(tǒng)一稱為SimTripletSVM. 為了完備起見(jiàn), 本文引入了其他可能的基于三元組的損失函數(shù)定義方式作為對(duì)比.

2.4 基于列表的相似性學(xué)習(xí)算法

中國(guó)汽車維修行業(yè)協(xié)會(huì)原會(huì)長(zhǎng)康文仲，交通運(yùn)輸部科學(xué)院原黨委書記、中國(guó)汽車保修設(shè)備行業(yè)協(xié)會(huì)原副會(huì)長(zhǎng)王曉曼，中國(guó)汽車維修行業(yè)協(xié)會(huì)原會(huì)長(zhǎng)孫守仁，中國(guó)汽車保修設(shè)備行業(yè)協(xié)會(huì)原副會(huì)長(zhǎng)羅大柱 ，中國(guó)汽車保修設(shè)備行業(yè)協(xié)會(huì)原副會(huì)長(zhǎng)張熙倫，中國(guó)汽車保修設(shè)備行業(yè)協(xié)會(huì)原副會(huì)長(zhǎng)兼秘書長(zhǎng)田國(guó)華，中國(guó)汽車維修行業(yè)協(xié)會(huì)常務(wù)副秘書長(zhǎng)王逢鈴， 中國(guó)汽車保修設(shè)備行業(yè)協(xié)會(huì)原常務(wù)副秘書長(zhǎng)劉蘊(yùn)，中國(guó)汽車保修設(shè)備行業(yè)協(xié)會(huì)秘書長(zhǎng)劉建農(nóng)，中國(guó)汽車維修行業(yè)協(xié)會(huì)連鎖工委秘書長(zhǎng)嚴(yán)雪月，廣東省道協(xié)機(jī)動(dòng)車維修檢測(cè)分會(huì)會(huì)長(zhǎng)羅少澤，北京汽車維修行業(yè)協(xié)會(huì)副秘書長(zhǎng)侯金鳳及數(shù)十位國(guó)內(nèi)知名汽保企業(yè)負(fù)責(zé)人作為嘉賓出席此次茶話。

基于三元組的相似性學(xué)習(xí)算法建模了三元組這樣的局部序, 所帶來(lái)的損失, 沒(méi)有考慮排序列表整體的質(zhì)量. 基于三元組的算法將整個(gè)相似性列表拆分為三元組的形式, 將每個(gè)三元組作為一個(gè)訓(xùn)練實(shí)例, 強(qiáng)制性的認(rèn)為這些三元組服從獨(dú)立同分布假設(shè). 本文將整個(gè)排序列表視為一個(gè)訓(xùn)練實(shí)例, 采用基于位置的評(píng)價(jià)指標(biāo)作為排序列表質(zhì)量的度量, 將其作為優(yōu)化目標(biāo), 采用LambdaMART定義損失函數(shù)的方式, 如公式(6)所示.

3 SimListMKL算法

本文采用SimListMKL算法來(lái)優(yōu)化公式(6)所示的優(yōu)化目標(biāo), 評(píng)價(jià)指標(biāo)采用MAP, 為基于所有查詢App的AP(Average Precision)的平均. 因此這里的MAP的變化應(yīng)該對(duì)應(yīng)到AP的變化. 公式(7)給出了對(duì)于一個(gè)查詢App在已知其二值標(biāo)注Y的情況下, 計(jì)算模型f產(chǎn)生的預(yù)測(cè)序的AP值.

(8)

SimListMKL算法采用MART來(lái)優(yōu)化目標(biāo)函數(shù)公式(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行描述了模型的初始化過(guò)程, 第6~17行描述了每一個(gè)迭代步生成一個(gè)用來(lái)公式(6)中損失函數(shù)的梯度的回歸樹(shù), 該樹(shù)具有L個(gè)葉子節(jié)點(diǎn), 葉子節(jié)點(diǎn)的值由Newton-Raphon更新步確定. 算法最終得到的即為本文要求解的App相似性函數(shù).

4 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證SimListMKL算法的有效性, 本文首先介紹了實(shí)驗(yàn)設(shè)置. 接下來(lái)介紹了基于三元組相似性的多核學(xué)習(xí)算法與本文提出的基于列表相似性的多核學(xué)習(xí)算法, 在相似App推薦場(chǎng)景下的性能對(duì)比. 最后對(duì)比了各類算法性能受不同類型數(shù)據(jù)集的影響以及各類算法的運(yùn)行時(shí)間.

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)數(shù)據(jù)集采用的是SimApp[1]中所用的訓(xùn)練數(shù)據(jù)集. 該數(shù)據(jù)集來(lái)源于Google Play的真實(shí)數(shù)據(jù), 包括約13,000個(gè)查詢App, 每個(gè)查詢App下約20個(gè)App, 其中相似App的比例分布如圖1所示. 橫軸表示相似App的比例范圍, 如0.1對(duì)應(yīng)的是相似App比例在0~0.1之間的查詢App的比例. App之間的相似性由10個(gè)核函數(shù)來(lái)刻畫, 包括名稱, 類別, 描述, 開(kāi)發(fā)商, 屏幕截圖, 大小, 用戶評(píng)分, 用戶評(píng)論, 更新信息, 許可.

圖1 相似App比例分布

本文的主要基準(zhǔn)算法是基于三元組的相似性學(xué)習(xí)算法, 包括SimTripletNet, SimTripletBoost, SimTripletSVM.盡管采用了相同的優(yōu)化目標(biāo), 可是由于優(yōu)化算法不同也有許多不同的變種, 如SimTripletSVM對(duì)應(yīng)的OKWL算法與OASIS算法, 這里將它們統(tǒng)一從優(yōu)化目標(biāo)的角度命名. 基于交叉熵?fù)p失函數(shù)的SimTripletNet采用梯度下降優(yōu)化算法求解, 基于指數(shù)函數(shù)損失的SimTripletBoost采用boosting優(yōu)化算法求解, 基于hinge損失函數(shù)的SimTripletSVM采用切平面優(yōu)化算法求解.

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

4.2 性能分析

本文將五折交叉驗(yàn)證的結(jié)果分別展示在表1和圖2中. 表1描述了基于P@1~10的性能對(duì)比, 圖2描述了MAP作為評(píng)價(jià)指標(biāo)的性能對(duì)比. 基于t-test的假設(shè)檢驗(yàn)證明以下表和圖中的對(duì)比差異是顯著的.

表 1 Precision性能對(duì)比

圖2 MAP性能對(duì)比

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

圖2展示的結(jié)果可以直觀的表明SimListMKL算法的優(yōu)勢(shì). 該算法高出SimTripletBoost約0.3%, 高出SimTripletNet約1%, 高出SimTripletSVM約0.3%. 因此, 從MAP的度量角度來(lái)看, 基于列表建模損失函數(shù)在面向排序的相似性學(xué)習(xí)場(chǎng)景中是較好的選擇.

4.3 敏感分析

性能分析的結(jié)果顯示, 算法在實(shí)驗(yàn)數(shù)據(jù)集上的性能普遍較好. 根據(jù)已有的排序?qū)W習(xí)算法性能受數(shù)據(jù)集影響的研究[14]表明, 這主要?dú)w因于訓(xùn)練數(shù)據(jù)中正負(fù)例的比例均衡.

換句話說(shuō), 即每個(gè)查詢App對(duì)應(yīng)的訓(xùn)練實(shí)例集合中, 相似App的數(shù)量占一半左右.

本實(shí)驗(yàn)試圖打破這種均衡, 研究在不理想的數(shù)據(jù)集上算法性能的變化. ratio表示每個(gè)查詢App對(duì)應(yīng)的待比較App集合中相似App的數(shù)量比例. 按這個(gè)比例抽取查詢App, 分別構(gòu)建ratio小于0.1, 0.2, 0.3, 0.4, 0.5的數(shù)據(jù)集, 對(duì)比各算法在這些數(shù)據(jù)集上的性能表現(xiàn), 如圖3所示.

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

4.4 運(yùn)行時(shí)間分析

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

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

本文提出的算法SimListMKL運(yùn)行時(shí)間約為14.2秒, 與基于三元組的相似性學(xué)習(xí)算法SimTripletBoost相當(dāng), 遠(yuǎn)遠(yuǎn)好于SimTripletNet. SimListMKL與SimTripletBoost均采用了Boosting的優(yōu)化算法, 而SimTripletNet采用了梯度下降算法. 可見(jiàn), 影響運(yùn)行時(shí)間的因素主要取決于優(yōu)化算法的具體實(shí)現(xiàn). 本文提出的SimListMKL優(yōu)化目標(biāo)雖然復(fù)雜, 并沒(méi)有給優(yōu)化算法帶來(lái)太多額外的時(shí)間開(kāi)銷.

5 結(jié)語(yǔ)

針對(duì)排序場(chǎng)景中的相似性學(xué)習(xí)問(wèn)題, 本文總結(jié)出了一個(gè)基于相對(duì)序的相似性學(xué)習(xí)框架, 并提出了基于列表的多核相似性學(xué)習(xí)算法SimListMKL. 與已有的基于三元組相對(duì)相似性學(xué)習(xí)的算法相比, SimListMKL算法采用了一個(gè)更為概括的形式, 即列表的相對(duì)相似性, 并基于此建模了損失函數(shù), 并采用MART算法優(yōu)化. 實(shí)驗(yàn)結(jié)果表明, SimListMKL是一種更好的建模相對(duì)相似性的方式, 提升了相似App推薦的性能, 同時(shí)保證較高的時(shí)間效率. 多核相似性學(xué)習(xí)方法的顯著問(wèn)題是計(jì)算復(fù)雜度高, 下一步的研究工作主要是在線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;收到修改稿時(shí)間:2016-05-12

[10.15888/j.cnki.csa.005502]