隨筆檔案

大致內(nèi)容：
本文要解決的主要問題是社交網(wǎng)絡(luò)中的標(biāo)簽推薦（本文主要為音樂、視頻等多媒體對象推薦合適的標(biāo)簽）。較之以前的推薦策略——a.根據(jù)已有標(biāo)簽進(jìn)行詞語共現(xiàn)的推薦; b.根據(jù)文本特征（如標(biāo)題、描述）來推薦; c.利用標(biāo)簽相關(guān)性度量來推薦。大部分僅僅至多使用了上述的兩種策略，然而本文將3種特征全部結(jié)合，并提出一些啟發(fā)式的度量和兩種排序?qū)W習(xí)（L2R）的方法，使得標(biāo)簽推薦的效果（p@5)有了顯著的提高。

問題陳述：
作者將數(shù)據(jù)集分為三類：train, validation, test。對于訓(xùn)練集D，包含<L_d,F_d>。L_d指對象d的所有標(biāo)簽集；F_d指d的文本特征集（即L_d=L¹_d∪L²_d∪L³_d...Lⁿ_d，F_d=F¹_d∪ F²_d∪ F³_d....Fⁿ_d）。對于驗證集和測試集，由三部分組成<L_o,F_o,y_o>。L_o為已知標(biāo)簽，y_o為答案標(biāo)簽，實驗中作者將一部分標(biāo)簽劃分L_o，一部分為y_o，這樣做可以方便系統(tǒng)自動評價推薦性能。

Metrics說明：
（1）Tag Co-occurrence：基于共現(xiàn)方法的標(biāo)簽推薦主要是利用了關(guān)聯(lián)規(guī)則（association rules），如X→y，X為前導(dǎo)標(biāo)簽集，y為根據(jù)X（經(jīng)過統(tǒng)計）得到的標(biāo)簽。還要提到兩個參數(shù)：support(σ),意為X,y在訓(xùn)練集中共現(xiàn)的次數(shù)，confidence（θ）=p(y與object o相關(guān)聯(lián)|X與object o相關(guān)聯(lián))。由于從訓(xùn)練集中得到的規(guī)則很多，因此要設(shè)定σ 、θ 的最小閾值，只選取最為頻繁發(fā)生、最可靠的共現(xiàn)信息。
    Sum(c,o,l)=Σ_X⊆L0 θ(X→c)， （X→c）∈R， |X|≤l

（2）Discriminative Power: 指區(qū)分度，對于一個頻繁出現(xiàn)的標(biāo)簽特征，區(qū)分度會很低。作者提出一個IFF度量（類似于IR中的IDF），定義如下：
    IFF（c）=log[(|D|+1)/（f_c^tag+1）]
其中f_c^tag為訓(xùn)練集D中，以c作為標(biāo)簽者的對象數(shù)。
盡管這個度量可能偏重于一些并未在訓(xùn)練集中出現(xiàn)作為標(biāo)簽的詞語，然而在排序函數(shù)中，它的權(quán)重會被合理安排。
    另外，過于頻繁的標(biāo)簽和過于稀少的標(biāo)簽都不會是合理的推薦，而那些頻率中等的term則最受青睞。有一種Stability(Stab)度量傾向于頻率適中的詞語：
    Stab(c,k_s)=k_s/[k_s+|k_s-log(f_c^tag)|] ， 其中k_s表示term的理想頻率，要根據(jù)數(shù)據(jù)集來調(diào)整。

（3）Descriptive Power
指對于一個侯選c的描述能力，主要有如下4種度量：
①TF： TF(c,o)=Σ_Foⁱ∈Fo tf(c,F_oⁱ)
②TS： TS(c,o)=Σ_Foⁱ∈Fo j,  where j=1 (if c∈F_oⁱ ), otherwise j=0
③wTS：wTS(c,o)=Σ_Foⁱ∈Fo j,  where j=AFS（F_i） (if c∈F_oⁱ ), otherwise j=0 
④wTF：wTS(c,o)=Σ_Foⁱ∈Fo tf(c,F_oⁱ),  where j=AFS（F_i） (if c∈F_oⁱ ), otherwise j=0 
這里要引入兩個概念：
FIS：Feature Instance spread. FIS(F_oⁱ) 為F_oⁱ中所有的term的平無數(shù)TS值。
AFS：Average Feature Spread：AFS（Fⁱ）為訓(xùn)練集中所有對象的平均FIS(F_oⁱ)，即
AFS（Fⁱ）=Σ_oj∈D FIS(F_ojⁱ)/|D|

（4）詞項預(yù)測度
Heymann et al.[11]通過詞項的熵來度量這個特征。
詞項c在標(biāo)簽特征的熵值H^tags(c)=-Σ_(c→_i)∈_R    θ(c→i)logθ(c→i) ，其中R為訓(xùn)練集中的規(guī)則集。

標(biāo)簽推薦策略：
（1）幾個先進(jìn)的baseline：
① Sum^+：擴(kuò)展了Sum度量，通過相應(yīng)關(guān)聯(lián)規(guī)則的前導(dǎo)和后繼中的詞項的Stablity為Confidence賦予權(quán)重。給定一個對象o的侯選標(biāo)簽c，Sum⁺定義如下：
    Sum⁺(c,o,k_x,k_c,k_r)=Σx∈L₀ θ(x→c)*Stab(x,k_x)*Stab(c,k_c)*Rank(c,o,k_r)
    其中：k_x,k_c,k_r為調(diào)節(jié)參數(shù)，Rank(c,o,k_r)=k_r/[k_r+p(c,o), p(c,o)為c在這個關(guān)聯(lián)規(guī)則中confidence排名的位置，這個值可以使Confidence值更為平滑地衰減。Sum⁺限制了前導(dǎo)中的標(biāo)簽數(shù)為1。
② LATRE（Lazy Associative Tag Recommendation）：與Sum⁺不同，LATRE可以在立即請求的方式快速生成更大的關(guān)聯(lián)規(guī)則，這與其它策略不同（因為它們都是事先在訓(xùn)練集中計算好所有的規(guī)則），但也可能包含一些在測試集中并不是很有用的規(guī)則。 LATRE排序每個侯選c，通過相加所有包含c的規(guī)則的confidence值。
③ CTTR（Co-occurrence and Text based Tag Recommender）：利用了從文本域特征中抽取出的詞項和一個相關(guān)性度量，但所有考慮事先已經(jīng)賦給對象o的標(biāo)簽。作者對比CTTR與作者的方法，評價了作者自創(chuàng)幾個度量和應(yīng)用事先預(yù)有標(biāo)簽的有效性，篇幅有限，不再對此詳述。

（2） New Heuristics
8種，作者擴(kuò)展了Sum⁺和LATRE baseline加入了描述性度量（TS,TF,wTS,wTF），共合成了8種方案。
    Sum⁺DP(c,o,k_x,k_c,k_r,α)=αSum⁺(c,o,k_x,k_c,k_r)+(1-α)DP(c,o)
    LATRE⁺DP(c,o,l,α)=αSum(c,o,l)+(1-α)DP(c,o)

（3）排序?qū)W習(xí)策略：
對一個Metric矩陣（對于侯選c）M_c∈R^m，m是考慮的metric數(shù)，即矩陣的維數(shù)。然后驗證集V的對象v賦一個Y_c，若c為v的合理推薦，Y_c=1，否則Y_c=0。因為訓(xùn)練集用來抽取關(guān)聯(lián)規(guī)則和計算metrics，驗證集用來學(xué)習(xí)solutions，因此只對驗證集賦Y_c。學(xué)習(xí)模型，即排序函數(shù)f(M_c)將被用于測試集：
① RankSVM：作者使用SVM-rank tool學(xué)習(xí)一個函數(shù)f(M_c)=f(W,M_c)，其中W=<w₁,w₂,....,w_m>是一個對metrics賦權(quán)值的向量。其中，RankSVM有兩個參數(shù)，kernel function和cost j。

② 遺傳算法：
    這里將個體（即標(biāo)簽排序函數(shù)）看成一個樹表示，葉子結(jié)點為變量或常數(shù)。樹內(nèi)結(jié)點為基本運算符（+,-,*,/,ln）。若域超出運算范圍，結(jié)果默認(rèn)為0。例如，一個樹表示函數(shù)：Sum+0.7*TS，如下圖：

    個體的健壯度（Fitness）表示相應(yīng)排序函數(shù)的推薦質(zhì)量，本文以P@k為衡量標(biāo)準(zhǔn)給定f(M_c)，y_o是o的相關(guān)標(biāo)簽，R_o^f是通過f(M_c)排序后的o的推薦結(jié)果，R_k,o^f的R_o^f中前k個結(jié)果，推薦質(zhì)量定義如下：
P@k(R_o^f,y_o,f)=|R_k,o^f∩y_o|/min(k,|y_o|)

實驗評價：
（1）數(shù)據(jù)收集：LastFM, Youtube, YahooVideo。 然后去停用詞，詞干化處理（Poster Stemmer）
（2）評價方法：
a.將object預(yù)先的一些標(biāo)簽一部分作為已經(jīng)，一部分作為答案，方便評價，某些生成的答案，并不能在答案集中，但并不意味不相關(guān)，因此可作為lower bound。
b.在實際實驗中，作者將驗證集和測試集的對象標(biāo)簽平均分為L_o,y_o,使用title和description作為文本特征F_o。
c.在評價指標(biāo)上，主要使用P@5，并用了Recall和MAP值
d.以兩種方案來對各種推薦方法評價：
① 把每個數(shù)據(jù)集分為3份，對應(yīng)小規(guī)模，中規(guī)模，大規(guī)模，以便針對每種情況，調(diào)整參數(shù)，評價不同規(guī)模下各方法的效果
② 利用整個數(shù)據(jù)集，統(tǒng)一的評價

這兩種方案，①更加有針對性，②則代價較低
對于第一個方案，作者隨機(jī)從每個子集（大、中、小規(guī)模）中選取50000個樣本，對于第二種方案，作者使用第一個方案選取出的3個樣本集組合的樣本。這兩種方案都把每個樣本集分為5份來做5折交叉驗證。3/5做訓(xùn)練，1/5做驗證，1/5做測試。之所以在驗證集上做L2R是為了避免過擬合。


（3）參數(shù)設(shè)定
① Sum⁺DP中，k_r=k_x=k_c=5, α=[0.7,1.0]
② LATRE⁺DP和L2R中，l=3, k_s=5。在確定σ_min和θ_min時，將值設(shè)定為與σ_min和θ_min=0相比，結(jié)果下降小于3%的值
③ RankSVM中，選定線性核，cost j=100
④ 歸一化特征向量結(jié)果不明顯，因此本文并沒有采取特征向量歸一化。

（4）實驗結(jié)果：
a. LastFM上提升較小，原因有二：① 有LastFM上標(biāo)簽、標(biāo)題、描述內(nèi)容重疊少，使TS，wTS集中在小值上，使得難以區(qū)別good,bad；② LastFM上對象標(biāo)簽較少，使TS,wTS難以發(fā)揮較好作用。
b. LATRE在大部分情況，好于Sum⁺，而CTTR在一些情況好于LATRE。尤其是在Youtube。
c. 對比每個方案和數(shù)據(jù)集，作者的heuristics都有較大提升，因此引入描述性度量(descriptive power)會顯著提高推薦效果，尤其是標(biāo)簽數(shù)較少的情況（因為共現(xiàn)效果差）
d. 比較Sum+, LATRE, CTTR。作者的8種啟發(fā)式護(hù)展都有不小的提升（LastFM最小），證實了利用預(yù)先已知標(biāo)簽和描述度量的作用。
e. 新啟發(fā)思想中，LATRE+wTS在大多數(shù)情況最好。在DP確定下，LATRE通常好于Sum+；DP變時，wTS最好，其實是wTF,TS。
f. L2R中，兩種方法都有提升，但提升幅度有限，觀察發(fā)現(xiàn)，GP和SVMRank主要利用的還是LATRE+wTS的metrics，GP中最常用的是Sum(c,o,3)，然后是wTS，再是IFF，其它少于這些函數(shù)的25%。RankSVM中，最高權(quán)重主要還是集中于Sum,wTS。
g.盡管L2R效果提升不明顯，但框架靈活，易于擴(kuò)展（加入新度量和tag recommender問題，如個性化）
h.對于SVMRank和GP的比較，效果好壞主要取決于數(shù)據(jù)集。

論文：
Fabiano Belem,  Eder Martins,  Tatiana Pontes,  Jussara Almeida,  Marcos Goncalves.  Associative Tag Recommendation Exploiting Multiple Textual Features. Proceedings of the 34th international ACM SIGIR conference on Research and development in Information, Jul. 2011.
 
論文鏈接：
SIGIR2011_Associative_Tag_Recommendation_Exploiting_Multiple_Textual_Features.pdf