« クラスタリング アルゴリズムの評価 | トップページ | ソーシャルゲーム・ソーシャルアプリケーションの現在と未来 @ WebDB2010 »

国際会議WWW2009論文感想その7

Dong Liu , Xian-Sheng Hua, Linjun Yang, Meng Wang, Hong-Jiang Zhang: Tag ranking, Proc. WWW 2010, pp. 351-360, 2010.
Microsoft Research Asiaの研究

Flickrの特定の画像に付けられたタグをランキングしている.タグをランキングする世界で初めての論文であると主張している.

Flickrの特定の画像に付けられたタグは,時間順で表示されており,タグの重要度や関連度については考慮されていない.この論文の調査によると,Flickrの特定の画像に付けられたタグにおいて,その画像と最も関連しているタグがタグリスト中で,1番目にある割合は10%以下であることを報告している.

この研究では,タグをランキングするのに2種類の方法を提案している.また,この2種類の方法を組み合わせる方法も提案している.

1つ目の方法は,Probabilistic Tag Relevance Estimation (PTR)である.これは,ある画像xにおけるランキングを求める.xに付けられたタグのうちのtiについて,tiとxの関連度s(ti,x)を求める.タグtiを含む画像集合をXiとする.Xi中の全画像とxとの類似度を計算し,その和をs(ti,x)としている.画像の類似度の計算は,画像認識の研究分野で基本的な特徴量を使用している.

2つ目の方法は,Random Walk-Based Refinementである.これは,ある画像xに付けられたタグ集合において,全てタグ間の類似度を求める.全てのタグ間にリンクを張り,グラフ構造とみなす.ノードにもスコアがあるとみなす.最も基本的には,初期値としては全て1とする.このグラフ構造に対し,ランダムウォーク法を適用する.これにより,ノードのスコアを再帰的に計算する.

2つ目の方法をもう少し具体的に説明すると,やりたいことは,例えば猫の画像に,"cat", "animal", "kitten", "Nikon"というタグが付けられていたとする.この中で,"Nikon"は他のタグより説明的でない.したがって,この"Nikon"のスコアを下げることである.

方法としては,2つの方法でタグ間の類似度を計算する.1つは代表画像類似度でもう一つは共起類似度である.代表画像類似度の算出方法は,以下のとおりである.画像xにつけられたタグtについて,タグtを含む画像集合に対し,画像xからのN近傍を収集する.これをFtとする.近傍は,画像の類似性で判定している.画像xに付けられたタグtiとタグtjの類似度を求めるには,FtiとFtjを求める.代表画像類似度は,タグtiが付けられた全画像とタグtjが付けられた全画像のすべての組み合わせに対し,ユークリッド距離を算出する.これを足し合わせたものを距離dとみなし,e^{-d}としたものを類似度としている.

共起類似度は,d(ti,tj)=log(f(ti)/f(ti,tj))/log(ftj)で算出している.f(ti)はタグtiを含む画像の数,f(ti,tj)はタグtiとtjを両方含む画像の数である.直感的に,タグが類似していれば,f(ti,tj)が大きくなり,結果としてd(ti,tj)は小さくなる.e^{-d)により類似度を求める.
タグ間の類似度=λ*代表画像類似度+(1-λ)*共起類似度
としている.

ランダムウォークであるが,ノードiからノードjへの遷移確率pijを計算する.これはタグ間の類似度を用いている.タグjに注目した時,他のすべてのタグとの類似度に,タグjのスコアrjをかけたものの総和を求め,これを次のrjとしている.これを収束するまで行う.タグjの初期スコアは,1.ただし,PTRと組み合わせるときは,PTRで算出したスコアを用いる.

評価は,データセット(独自で収集)から10000画像を選択し,5人の評価者に各タグにスコア(5段階)を付けてもらい,それを正解とみなしている.性能の評価尺度にNDCGを用いている.NDCGは下記の式で算出される
NDCG=Z*Σ_{i=1}^{n}[(2^{ri-1}-1)/log(1+i)]
ランク付けを行ったタグリストt1,...,tn
Zは正規化定数.riはタグtiの関連度(評価者につけてもらったもの).iはランキング順位.

BaselineはFlickrの提供する時間順のリスト.評価結果は,PTRとRWTRは,ほぼ同じ評価値で,Baselineに比べるとはるかによくなっている.PTR*RWTRは,PTRとRWTRのそれぞれよりさらによくなっている.

タグのスコアを用いた画像検索における画像ランキング,タグ推薦,グループ推薦(グループとはFlickrが提供する画像を分類するためのグループ.全ユーザ共通で使える)に応用し,その評価も行っている.画像ランキングは,提案手法と,時間順,interestingness順(Flickrの提供するランキング(詳細は不明)),タグの時間順のランキングを用いた画像のランキング順と比較し,提案手法が最も良いことを示している.
タグ推薦は,グループ推薦も同様に,好評価となっている.

感想であるが,近年画像認識の技術を用いた研究がWWW Conf.に多く投稿されている.これもその一つである.今までタグのランキングを行った研究がなかったことに驚きだが,研究の進め方は非常にうまいと思う.評価指標もはっきりしており,研究の進め方は参考にすべき論文である.2つのランキング手法を提案しているが,この2つは手法としては完全に独立とは言えない.また,これらとは異なる手法も,まだありそうな気がする.

|

« クラスタリング アルゴリズムの評価 | トップページ | ソーシャルゲーム・ソーシャルアプリケーションの現在と未来 @ WebDB2010 »

Web研究」カテゴリの記事