随笔档案

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