隨筆檔案

1.馬爾可夫
2.GBDT，隨機(jī)森林
3.SVD，LDA等理論
4.上述理論的工具使用
5.網(wǎng)絡(luò)可視化工具的調(diào)研

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

問(wèn)題陳述：
作者將數(shù)據(jù)集分為三類(lèi)：train, validation, test。對(duì)于訓(xùn)練集D，包含<L_d,F_d>。L_d指對(duì)象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）。對(duì)于驗(yàn)證集和測(cè)試集，由三部分組成<L_o,F_o,y_o>。L_o為已知標(biāo)簽，y_o為答案標(biāo)簽，實(shí)驗(yàn)中作者將一部分標(biāo)簽劃分L_o，一部分為y_o，這樣做可以方便系統(tǒng)自動(dòng)評(píng)價(jià)推薦性能。

Metrics說(shuō)明：
（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)過(guò)統(tǒng)計(jì)）得到的標(biāo)簽。還要提到兩個(gè)參數(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ū)分度，對(duì)于一個(gè)頻繁出現(xiàn)的標(biāo)簽特征，區(qū)分度會(huì)很低。作者提出一個(gè)IFF度量（類(lèi)似于IR中的IDF），定義如下：
    IFF（c）=log[(|D|+1)/（f_c^tag+1）]
其中f_c^tag為訓(xùn)練集D中，以c作為標(biāo)簽者的對(duì)象數(shù)。
盡管這個(gè)度量可能偏重于一些并未在訓(xùn)練集中出現(xiàn)作為標(biāo)簽的詞語(yǔ)，然而在排序函數(shù)中，它的權(quán)重會(huì)被合理安排。
    另外，過(guò)于頻繁的標(biāo)簽和過(guò)于稀少的標(biāo)簽都不會(huì)是合理的推薦，而那些頻率中等的term則最受青睞。有一種Stability(Stab)度量?jī)A向于頻率適中的詞語(yǔ)：
    Stab(c,k_s)=k_s/[k_s+|k_s-log(f_c^tag)|] ， 其中k_s表示term的理想頻率，要根據(jù)數(shù)據(jù)集來(lái)調(diào)整。

（3）Descriptive Power
指對(duì)于一個(gè)侯選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 
這里要引入兩個(gè)概念：
FIS：Feature Instance spread. FIS(F_oⁱ) 為F_oⁱ中所有的term的平無(wú)數(shù)TS值。
AFS：Average Feature Spread：AFS（Fⁱ）為訓(xùn)練集中所有對(duì)象的平均FIS(F_oⁱ)，即
AFS（Fⁱ）=Σ_oj∈D FIS(F_ojⁱ)/|D|

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

標(biāo)簽推薦策略：
（1）幾個(gè)先進(jìn)的baseline：
① Sum^+：擴(kuò)展了Sum度量，通過(guò)相應(yīng)關(guān)聯(lián)規(guī)則的前導(dǎo)和后繼中的詞項(xiàng)的Stablity為Confidence賦予權(quán)重。給定一個(gè)對(duì)象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在這個(gè)關(guān)聯(lián)規(guī)則中confidence排名的位置，這個(gè)值可以使Confidence值更為平滑地衰減。Sum⁺限制了前導(dǎo)中的標(biāo)簽數(shù)為1。
② LATRE（Lazy Associative Tag Recommendation）：與Sum⁺不同，LATRE可以在立即請(qǐng)求的方式快速生成更大的關(guān)聯(lián)規(guī)則，這與其它策略不同（因?yàn)樗鼈兌际鞘孪仍谟?xùn)練集中計(jì)算好所有的規(guī)則），但也可能包含一些在測(cè)試集中并不是很有用的規(guī)則。 LATRE排序每個(gè)侯選c，通過(guò)相加所有包含c的規(guī)則的confidence值。
③ CTTR（Co-occurrence and Text based Tag Recommender）：利用了從文本域特征中抽取出的詞項(xiàng)和一個(gè)相關(guān)性度量，但所有考慮事先已經(jīng)賦給對(duì)象o的標(biāo)簽。作者對(duì)比CTTR與作者的方法，評(píng)價(jià)了作者自創(chuàng)幾個(gè)度量和應(yīng)用事先預(yù)有標(biāo)簽的有效性，篇幅有限，不再對(duì)此詳述。

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

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

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

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

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


（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í)，將值設(shè)定為與σ_min和θ_min=0相比，結(jié)果下降小于3%的值
③ RankSVM中，選定線性核，cost j=100
④ 歸一化特征向量結(jié)果不明顯，因此本文并沒(méi)有采取特征向量歸一化。

（4）實(shí)驗(yàn)結(jié)果：
a. LastFM上提升較小，原因有二：① 有LastFM上標(biāo)簽、標(biāo)題、描述內(nèi)容重疊少，使TS，wTS集中在小值上，使得難以區(qū)別good,bad；② LastFM上對(duì)象標(biāo)簽較少，使TS,wTS難以發(fā)揮較好作用。
b. LATRE在大部分情況，好于Sum⁺，而CTTR在一些情況好于LATRE。尤其是在Youtube。
c. 對(duì)比每個(gè)方案和數(shù)據(jù)集，作者的heuristics都有較大提升，因此引入描述性度量(descriptive power)會(huì)顯著提高推薦效果，尤其是標(biāo)簽數(shù)較少的情況（因?yàn)楣铂F(xiàn)效果差）
d. 比較Sum+, LATRE, CTTR。作者的8種啟發(fā)式護(hù)展都有不小的提升（LastFM最小），證實(shí)了利用預(yù)先已知標(biāo)簽和描述度量的作用。
e. 新啟發(fā)思想中，LATRE+wTS在大多數(shù)情況最好。在DP確定下，LATRE通常好于Sum+；DP變時(shí)，wTS最好，其實(shí)是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問(wèn)題，如個(gè)性化）
h.對(duì)于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