読者です 読者をやめる 読者になる 読者になる

でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

Semantic Stability in Social Tagging Streams (WWW'14) を読んだ

paper

WWW14から。次のWWW15はイタリアフローレンス!参加したい!

概要

Social tagging systems(FlickrとかDeliciousとか)においてリソース(Flickrなら写真、DeliciousならWebページ)に付けられたタグがどのように "Stable" になっていくかを分析。

Social tagging systemsではいろんな人が何のルールもなしに好き勝手タグ付けをするので、結果として意味を成さないめちゃくちゃなタグ付けになってしまいそうだけど、(多くの人が経験上分かるように)そうはならない。時間を追ってどんどんタグ付けされていくわけだけど、一定時間経つとあるリソースに付けられたタグの "割合" は変化しなくなる。こういう状況を "Stable" であるという。

例えば、Deliciousでgoogle.comは多分"search engine"とかそういうタグを付けられてるんだけど、Stableな状態になるとその後みんながタグ付けを続けてもgoogle.comに付けられたタグの割合は変わらない。

この論文ではStableであるという状態を表す新しい指標を提案し、それを使って三つの異なるSocial tagging systemsの違いや、Stableになる原因について論じている。

貢献

  1. Social tagging systemsがStableであるかどうかを示す指標を提案。既存の指標のいくつかの問題点を解決している。
  2. 提案指標を使って三つのSocial tagging systems (Delicious, Librarything, Twitter lists) がStableであるかどうかを分析。
  3. 三つのシステムの違いや、Social tagging systemsがStableになる原因について議論。

提案指標

直感的には、付けられたタグの割合が変化しなくなったリソースが多いほどそのSocial tagging systemはStableであると言える。

実際には提案指標では付けられたタグの割合じゃなくて、付けられたタグの順位(google.comに付けられたタグで一番多いのは"search engine"とかそういうランキング)が変化しなくなるかどうかを見る。

Rank Biased Overlap

これはこの論文の提案した指標じゃないけど、これを使ってる。

あるリソース1に付けられたタグの頻度によるランキングを{ \sigma 1 }とし、2つのランキングの類似度を以下で測る。

{
RBO(\sigma 1, \sigma 2, p) = (1-p) \sum_{d=1}^{\infty} \frac{\sigma 1_{1:d} \cap \sigma 2_{1:d}}{d} p^{d-1}
}

{ \sigma 1_{1:d} }はランキングの1からd位までという意味。RBOは[0,1]の範囲の値を取り、0は2つのランキングが全く異なることを意味し、1は完全で同じであることを意味する。

{0 \leq p \lt 1}はパラメータで、0にするとランキングの1位だけしか考慮されなくなり(互いの1位が同じならRBO=1、そうでないならRBO=0)、1に近づけるほど下位まで考慮することになる。

Rank-based Stability Method

同じリソースの時刻tでのランキングと時刻t+t'でのランキングについて上のRBOを計算する。で、その値が閾値kより大きいリソースの割合f(t,k)を計算する。それが大きいほどStableであると言える。これだけ。

この値はSocial tagging systemについて決まる値なので、それを各Social tagging systemについて計算して比較する。またランダムなタグ付けをシミュレートして、それについてもこの値を計算して比較する。

提案指標の特徴三つ

  1. あるリソースに付けられたタグの割合そのもの(google.comに付けられた全てのタグの内"search engine"は割合0.7とか)を使うんじゃなくてランキングを使う。
  2. いくつかの既存指標ではランダムなタグ付けもStableである事になってしまうが、この指標ではランダムなタグ付けはStableであると判定されない(後述)。
  3. 既存指標はいままで出現したことのなかったタグを扱えなかったがこの指標は扱える。

結果

(論文中 Fig.7)

f:id:yamaguchiyuto:20141224073615p:plain

なんかすごい見づらい図なんだけど、縦軸がパラメータkで、横軸が時刻t。線の色が各Social tagging systemsに対応してて、各線はf(t,k)の値の等高線になってる。

まぁ図を読む必要も特に無いので結果だけまとめると、

  • Social tagging systemsは三つともランダムなタグ付けよりもStableだった
  • Twitterは他の2つのSocial tagging systemsよりfの値が小さかったんだけど、これはTwitterでリストを作る時に「このユーザにはこういうタグ(リスト名)をつけたほうがいいですよ」っていう推薦がないから(と思われる)
  • この図から読み取れることではないけど、Stableになる原因としてはシステムからのタグの推薦と、ユーザ達が持ってるBackground knowledge(どういうタグを付けるべきか)が挙げられる。これはシミュレーションから得られた結果 (Fig. 8) で示している。

感想

サーベイが本気。論文中で何かを主張する時は大抵文献が参照されてるか実験結果があるかだった気がする。論文書く時はホントはそれくらいしないといけないね。すごい。結果はまぁ驚くもんでもなくて、直感に反しないんだけど。どこかで「当たり前の結果を出すことが大事」みたいなのを見たことがあるし最近そう思うので、この手の分析しました論文ではしっかりとした手順を踏んで直感的なことを "示す" ってのが重要なんだと思う。