« 2010年9月 | トップページ | 2010年11月 »

2010年10月

国際会議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つは手法としては完全に独立とは言えない.また,これらとは異なる手法も,まだありそうな気がする.

|

クラスタリング アルゴリズムの評価

クラスタリングの研究をしていると,その評価にはいつも悩まされます.人手で行った正解クラスタリングとの類似性を評価指標とすることも考えられますが,実際の利用では特定のクラスタに入って,その使い勝手を見ることも多いでしょう.もし,特定のクラスタに注目して評価するならば,そのクラスタが何の集まりなのかを決めないといけません.支配的な集まりを仮の正解とすることも考えられますが,これで完全であるとは言えません.
人手で行った正解クラスタリングとの類似性を評価指標に,以下のようなものが見つかったので紹介します.

・Folwkes-Mallows index
E. Fowlkes and C. Mallows: A method for comparing two hierarchical clusterings. Journal of the American Statistical Association, Vol.78, No. 383, pp.553-569, 1983.
2つのクラスタリングC1とC2.C1は計算機によるクラスタリング結果.C2は人手による正解のクラスタリング.
N11:サンプルがC1,C2の両方において同じクラスタにある.
N00:サンプルがC1,C2の両方において異なるクラスタにある.
N10:サンプルがC1においては同じクラスタにあり,C2においては異なるクラスタにある.
N01:サンプルがC1においては異なるクラスタにあり,C2においては同じクラスタにある.

WI(C1,C2)=N11/(N11+N01)
WII(C1,C2)=N11/(N11+N10)
Folwkes-Mallows index=sqrt(WI(C1,C2)*WII(C1,C2))

・variation of information
M. Meila: Comparing clusterings: An information based distance, Journal of Multivariate Analysis, Vol.98, No.5, pp.873-895, 2007.
クラスタk,クラスタ内のサンプル数nk,全体のサンプル数n,C(C1とC2)はクラスタリング結果,KはクラスタリングC内のクラスタ個数

サンプルがクラスタkに属する確率
P(k)=nk/n
サンプルがどのクラスタに属しているかという不確実性H(C)は,
H(C)=-sigma{k=1, K}(P(k)*logP(k))
サンプルがクラスタリングC1中のkとC2中のk'に含まれている確率
P(k,k')=|C1k∧C2k'|/n
相互情報量はあらゆるクラスタの組を考慮に入れて
I(C1,C2)=Sigma{k=1,K}Sigma{k'=1,K'}P(k,k')log(P(k,k')/P(K)P(k')
ランダムなサンプルに対して,それが所属するC1のクラスタについての不確実性はH(C1).あるサンプルがC1においてどのクラスタに属するか与えられたときは,C2における不確実性をI(C1,C2)だけ減少させられる.
すなわち,
variation of information = H(C1,C2)+H(C2,C1)
=[H(C1)-I(C1,C2)]+[H(C2)-I(C1,C2)]

|

« 2010年9月 | トップページ | 2010年11月 »