隨筆檔案

1.馬爾可夫
2.GBDT，隨機森林
3.SVD，LDA等理論
4.上述理論的工具使用
5.網絡可視化工具的調研

暫時就想到這些，到時候再補充~ 大致內容：
本文要解決的主要問題是社交網絡中的標簽推薦（本文主要為音樂、視頻等多媒體對象推薦合適的標簽）。較之以前的推薦策略——a.根據已有標簽進行詞語共現的推薦; b.根據文本特征（如標題、描述）來推薦; c.利用標簽相關性度量來推薦。大部分僅僅至多使用了上述的兩種策略，然而本文將3種特征全部結合，并提出一些啟發式的度量和兩種排序學習（L2R）的方法，使得標簽推薦的效果（p@5)有了顯著的提高。

問題陳述：
作者將數據集分為三類：train, validation, test。對于訓練集D，包含<L_d,F_d>。L_d指對象d的所有標簽集；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為已知標簽，y_o為答案標簽，實驗中作者將一部分標簽劃分L_o，一部分為y_o，這樣做可以方便系統自動評價推薦性能。

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

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

（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的平無數TS值。
AFS：Average Feature Spread：AFS（Fⁱ）為訓練集中所有對象的平均FIS(F_oⁱ)，即
AFS（Fⁱ）=Σ_oj∈D FIS(F_ojⁱ)/|D|

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

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

（2） New Heuristics
8種，作者擴展了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）排序學習策略：
對一個Metric矩陣（對于侯選c）M_c∈R^m，m是考慮的metric數，即矩陣的維數。然后驗證集V的對象v賦一個Y_c，若c為v的合理推薦，Y_c=1，否則Y_c=0。因為訓練集用來抽取關聯規則和計算metrics，驗證集用來學習solutions，因此只對驗證集賦Y_c。學習模型，即排序函數f(M_c)將被用于測試集：
① RankSVM：作者使用SVM-rank tool學習一個函數f(M_c)=f(W,M_c)，其中W=<w₁,w₂,....,w_m>是一個對metrics賦權值的向量。其中，RankSVM有兩個參數，kernel function和cost j。

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

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

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

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


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

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

論文：
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