2010年1月6日水曜日

Flickr Tag Recommendation based on Collective Knowledge

Abstract
本論文では我々は人々がどのようにタグを付けるのか、あるいはどのような情報がタグに含まれるのかを調査・分析して人々にタグを推薦するシステムを構築し評価を行う。

１．はじめに
　近年Web上の様々なリソース（画像や動画、Webページなど）にタグを付ける事が一般的になってきた。タグは意味のある記述をオブジェクトに与え、ユーザがコンテンツを整理することができる。特に大規模なリッチメディア（例えば動画や画像）の検索システムには不可欠なものと言えるだろう。
　この論文での貢献は２つある。
１つ目：どのようにユーザは写真にタグを付けるのか？(１つの写真にどれくらいのタグがあるのか？あるいはあるタグがフリッカー中でどれくらいの頻度でつかわれているのかなど）またどのような種類（例えば位置や建物名）のタグをユーザは付けるのかを５２００万枚の代表的なスナップショットに基づいて分析する。
２つ目：４つの異なるタグの推薦システムを提案する。また実験により評価を行う。
　推薦するタグはタグの共起関係に着目する事で決定する。また本研究の状況設定であるが、最初に写真のオーナーがタグを付け、そのタグを元に更に追加でタグを付けるという状況の元行う。（写真のオーナーが最初にタグを付け、次に他の人がタグを追加していく場合とオーナーが追加でつける場合が考えられるが、おそらくオーナーが追加でつける場合を想定していると思われる、というのはyoutube,flickerなどにはタグを他の人が追加で付けるという機能がないからである。youtubeに至っては現在タグはキーワード検索用でしかなく、動画ページにタグへのリンクがないためタグを辿って目的の動画にたどり着くという事ができない。ニコニコ動画ではタグの編集を他の人が自由にする事ができる、また動画投稿を行ったユーザのタグを消して新しいタグに変える事もできるが、動画投稿を行ったユーザがタグを消されないように設定することもできる。）
　評価については200の写真セットをランダムで選び行った。１つのタグしか付いていないものもあれば６つ以上のタグが付いているものもあった。パフォーマンスを詳細に評価するため４つの評価指標と４つのレコメンデーション戦略で評価を行った。（５、６章に詳細）
　以後２章で関連研究、３章でフリッカーのタグの分析、４章でフリッカーで写真のアノテーションを拡張するための４つのタグ推薦戦略を提案５章で評価実験の概要、６章で実験の結果を提示、７章で結論と今後の方向性を述べる。

２．関連研究
タグのシステムについて詳細に説明したもの(タグの目的、意義など）[13][16]
タグを時間軸、あるいは空間で整理するとアクセスを改善できたという研究（時間軸整理[9],空間整理[3]）
タグ付けのモチベーションを調査した研究[4]→ほとんどのユーザが一般大衆に向けて写真にタグ付けをするモチベーションがあるとわかった
(他明らかでないタグはユーザを混乱させる、またユーザはあまり関連性がなくてもsuggested tag（タグの推薦機能もあるということか？）を加えたがる）

自動的にタグを付与する研究群
画像解析により写真にタグを自動で付与する研究[5,15]
画像を見て連想する単語を挙げ、同じ単語を連想するゲームにより、人々にタグをつけさせる研究[23]
ZoneTagというサービス（フリッカーに簡単に写真をアップロードできるアプリケーション）では個人の履歴、写真の地理的位置、時間を利用してタグの推薦を行っている[24]
これらそれぞれは相互補完的に作用しえるものである。（それぞれの手法が独立であり組み合わせることで精度を高めることができる）我々の研究はphotoのアップロード者が付けたタグという他と異なるデータを入力データとして利用するためこれらと相互補完的に使える。

我々の共起解析は、情報検索やセマンティックWebの領域で研究が盛んな単語ヒエラルキーやオントロジーと関係がある[20,17,21](20はテキストから単語ヒエラルキーを構築するもの、２１はフリッカータグからオントロジーを構築しようとするもの）しかしフリッカーは用いられる語彙が限定的であり、またグラフのノード間の関係が制御できない性質を持っているため、我々はこれら2つの側面にも関わらずタグ関係を分析するのに、これらとよく似た概念を用いる。（意味不明、Despiteの訳し方に疑問？おそらく２つの側面を持っているためこの欠点を補うべく共起解析を行ったという意味ではあるが）

フリッカータグにセマンティックラベルを付加する先行研究として、フリッカーのジオタグと時間を利用して、タグがイベントなのか地名なのかを分ける研究がある。[18]我々の研究はこれをより豊かにできる。よりリッチなセマンティックタグを加えるためにWorldNet（英語の概念辞書）を用いる方法でこの手法を補う。

３．フリッカーでのタグのふるまい
タグの振る舞いにおいて我々が特に知りたい事は２つあり、「どのようにタグを付ける?（タグを付ける個数）」と「何をタグとする?（場所や建物名など）」である。「なぜタグを付ける?」についても疑問はあるが、これに関する研究はなされており[23,16,14,4]、社会的な動機によると結論付けられている。

３．１　使用データ（フリッカーの写真集合）
２００４年２月から２００７年６月までのユーザが定義したタグが少なくとも１つついている５２００万枚の写真。タグの種類は凡そ３７０万であり、タグ総数は１億８８００万である。１つの写真につき凡そ３つか４つのタグがついているものが平均的である。

３．２　一般的なタグの特徴
　どのようにユーザはタグを付けるのか？
図１はあるタグについて、登場したタグの回数を縦軸にとり、登場回数が多い（写真によく登場する）タグから順に並べたグラフである。これを見るとあるタグの登場回数はべき則に従う事がわかる。なお最も多いタグは上から順に2006,2005,wedding,party,2004であり、タグとして一般的過ぎるものであった。また少ないものは誤字や複雑なフレーズのものであり１５７０万以上のタグが一度だけしかフリッカー内で使われないものであった。（ここ良くわからない、uniqueタグの数が３７０万と言っているのにグラフでｘ軸は３７０万の所にない、また１５７０万以上のタグが一度しか使われていないと書いてあるがuniqueタグが３７０万であり、個の数を超えているのはおかしい。とりあえずベキ即に従っていることだけはわかる。）図２は１つの写真に付くタグの数を縦軸とし、数が大きい写真順に並べたものである。これもべき則に従うことがわかる。(ただしこれも図の表記方法は不明、図１では重複を許さない３７０万のタグがあり、それを横軸としているにもかかわらず、５０００位のタグしかないみたいにみえる？？）

３．３　タグのカテゴライズ
どんなタグをつけるの？ 
場所→２８％、人工物・芸術品→１６％、人々・グループ→１３％、行動・イベント→９％、時間→７％、他２７％
ユーザは写真の見えている部分にのみタグを付けるのではなくより広いコンテクスト（場所、時間、行動など）に対してタグ付けを行う。

4.　タグ推薦戦略
　本章ではタグレコメンデーションシステムの詳細について述べる。

４．１　タグレコメンデーションシステム概要
図４はタグレコメンデーションの全体図である。ユーザが定義したタグが与えられるとm個のタグ候補が与えられる。タグ候補は共起関係に基づいている。候補タグのリストはランキングされて、順位が高いn個のタグが最終的に推薦される。

４．２　タグの共起
２つのタグの共起を、両方のタグが使われている写真の数であると定義する。タグの共起係数を求める式は、式（１）、式（２）のようになる。
J(t_{i},t_{j}) := \frac{|t_{i}\cap t_{j}|}{|t_{i}\cup t_{j}|}  　・・・(1)   P(t_{j}|t_{i}) := \frac{|t_{i}\cap t_{j}|}{|t_{i}|}  　・・・（２） 
式（１）は共起したタグの回数を、少なくともどちらか一方のタグが出現した回数で割った式であり、２つのタグの類似度を計測するために広く用いられる。式（２）は非対称な指標であり、タグt_{i} が出現したときにどれくらいの確率でタグt_{j} が登場するかを示している。非対称な共起では文献[20,17,21]が詳しい。例えばエッフェル塔(Eiffel Tower)で共起係数の高い順にランキングしたところ、対称な指標である式（１）を用いた場合はTour Eiffel,Eiffel,Seine,La Tour Eiffel,Parisとなったのに対し、非対称の指標である式（２）を用いた場合はParis,France,Tour Eiffel,Eiffel,Europeであった。結論として非対称なタグの共起が、対称なタグの共起と比べてより適した共起タグの多様性を与えてくれると言える。

4.3 タグ集合と促進
ユーザ定義タグ（User-defined tags）を U
候補タグ（Candidate tags）を C_{u}
推薦タグ（Recommended tags）を Rとおく
推薦タグは候補タグの中から絞る事で得られる。
候補タグから推薦タグを決定するときに２つの戦略を用意した。
一つ目：投票戦略⇒共起の時に用いた係数を用いない戦略
二つ目：summing戦略⇒共起の時に用いた係数を用いる戦略
なお各候補タグごとにスコアを算出し高いものから推薦タグに選ばれる。
投票戦略はユーザ定義タグからの共起関係によって得られる候補タグで、同じ単語の個数を足したものである。スコア算出式は式(3),(4)で表される。
vote(u,c)=\begin{cases}<br />1 & if \:\: c\in C_{u} \\<br />0 & otherwise<br />\end{cases} 　・・・（３）　　　score(c) := \sum_{u\in U}{vote(u,c)}   ・・・（４）
例えば図４ではSpain,Gaudi,Catalunyaという単語がユーザ定義タグのSagrada FamiliaとBarcelonaのそれぞれの共起語として挙げられているためスコアは２であり、他の単語はどちらか一方の共起語として挙げられているためスコアは１である。
summing戦略は式（５）のようになる。
score(c) := \sum_{u\in U}{P(c|u)} \:\:\:\:\:\:\:\; ,if\;c \in C_{u} 　・・・（５）
これは４．２で求めたタグの共起係数を利用して、スコアに重みを与えたものである。我々はこれら２つをベースラインとして評価する。

Promotion
さらに推薦精度を上げるためにヒューリスティックな関数をもちいる
・Stability-promotion
ユーザ定義タグで登場回数が少ないものは多いものと比べて信頼性が低い、そこで式（６）の関数
stability(u):=\frac{k_{s} }{k_{s}+abs(k_{s}-log|u|) }  ・・・（６）
を用いて信頼性の高いタグに重みをつける。ここでuはあるユーザ定義タグの登場回数でありk_{s} はこの関数のパラメータであり学習を行う事で決定される。
・Descriptiveness-promotion(描写性促進？）
使用される頻度がとても高いタグは一般的になりすぎる傾向がある。よってこのようなタグの効果を次の式(7)により抑える
descriptive(c) := \frac{k_{d} }{k_{d}+abs(k_{d}-log(|c|)} ・・・（７）
|c|は候補タグとして登場した回数であり、登場した回数が多すぎると重みが小さくなるようになっている。（記述はないが逆に少なすぎても重みが小さくなる）

・Rank-promotion
タグの共起の値はユーザ定義タグと候補タグの関係性の良い推測を提供する。原理上はsumming戦略で既に使われている。しかしこの値は非常に速く減衰する。ランク関数は共起の値に注目せずユーザ定義タグが与えられた時の位置rに注目し次の式（８）で表す。
rank(u,c)=\frac{k_{r}}{k_{r}+(r-1)} ・・・（８）
ここでk_{r}は減衰係数である。（ここでrについての記述がposition rとしかないためあまり定かではないが、おそらく共起の値が大きい順に１，２，３，４と値をつけていくのだと思われる、これによりゆるやかなsumming戦略で使われている急激な値の減衰からゆるやかな値の減衰に変わりパフォーマンスが向上する）
この３つを組み合わせてプロモーション関数は次の式（９）のように定義される
promotion(u,c) := rank(u,c)\cdot stability(u)\cdot descriptive(c)・・・（９）
この関数を投票戦略、あるいはsumming戦略の関数に適用する。投票戦略の場合は次の式（１０）のようにスコア関数がアップデートされる。
score(c):=\sum_{u\in U}{vote(u,c)\cdot promotion(u,c)} ・・・（１０）
（なおsumming戦略についてのアップデートした後の関数の記述がない、しかし今後ほとんど議論に入ってこないのでここは紙面の都合上かわからないが省かれたのだろう。）ここで設定しなければならないパラメータとして(m,k_{r},k_{s},k_{d})がある。これらは次のセクションにて適切な設定を行う。そして下の図のようにプロモーション関数を用いた場合、用いない場合、投票戦略を用いた場合、summing戦略を用いた場合

votesum
no-promotionvotesum
promotionvote+sum+
の４パターンの戦略に対して推薦されるタグが適切であるかの評価を行う。

５．実験
５．１　タスク
システムがタグを推薦して、使用者がリストからユーザ定義タグと関連するタグを選んでアノテーションを増やす事ができるか？

５．２　写真集合
推薦されたタグと写真との関連性が妥当であると査定人が判断できるようににてbasketball,Iceland,sailingなどの高レベルな（カテゴリ階層が上位の）トピックの写真をフリッカーＡＰＩで抽出した。３３１の写真を抽出し、１３１枚を訓練用に用い、２００枚を評価用に用いた。（個人的な意見だが若干抽出方法にはランダムに写真を抽出できているか疑問は残る、できていないのだろうが推薦されたタグが妥当かどうか判定する査定人は本来ならば写真を投稿したユーザだが実験上写真を投稿したユーザに査定を行ってもらう事は不可能なので分かりやすいトピックにせざるを得なかったという実験者の苦悩が伺える）

５．３　査定
タグの妥当性の評価はblind review pooling methodによって手動で行われる。
１．プールを構成するために、４つの戦略それぞれに対してトップ１０の推薦が取り出される。
２．査定人は推薦されたタグのそれぞれの詳細度を査定するように頼まれる。
３．仕事を助けるために、査定人は写真、タイトル、タグ、オーナーの名前、description(記述、写真説明？）が与えられる。
４．査定人はフリッカーの写真を見て、必要に応じて追加のコンテクストを発見する。
　査定人は非常に良い、良い、あまりよくない、わからないの４段階（とても良い、良い、あまり良くない、わからない）でタグの妥当性を判断するように求められる。その結果９７２がとても良いで９８４が良いであり、２８１１があまりよくないで、２８９が分からないであった。

５．４ Evaluation Metrics(評価指標）
異なる側面からパフォーマンスを評価するために我々は３つの評価指標を採用した。

Mean Reciprocal Rank(MRR)
ランキング中のどこでシステムによって最も関連性のあるタグが返されるのかについて指標、全写真での平均を取る。これによりタグの中で最も関連しているタグを返せるかの能力がわかる。（具体的にどのようにこの値を評価しているかは不明）
Success at rank k(S＠k)
上位k個の中で良いタグが見つけられる確率で評価
Precision at rank k(P@k)
上位k個のタグのうち良いタグである割合。全ての写真の平均を取って求める。

５．５　システムのチューニング
１３１枚のトレーニングセットを用いて(m,k_{r},k_{s},k_{d})の最適なパラメータを決定した。その結果をテーブル３に示す。次のセクションではこのパラメータを用いてテストセットを評価する。

６．評価結果
評価は４つのセクションがある。最初に我々は２つの集合戦略の結果を報告する、そしてセクション６．２ではプロモーション関数のパフォーマンスを調べる
６．３では異なるタグクラス（クラス１はユーザ定義タグが１つ、クラス２は２～３、クラス３は４～６、クラス４は６より多い）での結果を報告する
６．４では推薦され、更にユーザに受け入れられるタグのタイプを分析する

６．１　集合戦略
個のセクションでは集合戦略であるsumming戦略とvote戦略のパフォーマンスを評価する。その結果は図４のようになった。ベースラインではsum戦略の方がvote戦略よりも勝っている。これはvote戦略が候補リストのランキングの異なったポジションで起こるタグ間を区別しないからである。（例えば１０番目の共起タグも１番目の共起タグも同等と見なされてしまう。）

６．２　プロモーション
もう一度プロモーション関数のパフォーマンスに注意をむける。テーブル４の中間がプロモーション関数を導入した場合のsum,vote戦略の結果である。全体的にパフォーマンスが向上しているのがわかる。またvote+のP@5(トップ５のタグが正確である割合）の精度がかなり向上した。

６．３　タグクラス
我々のプロモーション関数はユーザ定義タグが大きい場合（Class IV,すなわちユーザ定義タグが６より大きい場合）パフォーマンスがかなり上昇したがそれ以外ではそれほど変わらなかった。（図５参照）

６．４　意味解析
どのようなタグが推薦され、また受け入れられたのか？図５はタグ推薦プロセスに参加した全てのタグのWordNetカテゴリーを表している。各グループの最初の列はフリッカーの写真オーナーによって与えられたタグであり、２番目の列が推薦された上位５個のタグであり、最後の列が受け入れられたタグである。図６はWordNetのカテゴリーの違いによる享受率である。すなわち推薦されたタグのうち各カテゴリーごとにどれだけ受け入れられたかを示す確率である。これから我々のタグ推薦はLocation,Artifact or Objectで良い結果を挙げていることが分かる。

６．５　まとめ
 結果を要約すると次のような事が言える。最初に、我々が提案した戦略は効果的であり、推薦されたタグは有用なものを多く含んでいるといえる。７割に近い写真についてランキングトップのタグに関しては良い推薦であるという評価を受け、９４％の写真についてトップ５の推薦されたタグのうち１つは有用なタグを含んでいることがわかった。５つのタグが推薦された場合その半分以上は有効であるとわかった。次にプロモーション関数が一般的に正の効果を与える事が証明された。取り分け５番目のタグの正確さP@5に関しては効果が大きい事がわかった。最もパフォーマンスが良かったvote+はあらゆるクラスの写真について安定したパフォーマンスを発揮した。推薦されるタグの種類としてはLocation,Artifact or Objectがボリューム、享受率の両方で他と比べて良いパフォーマンスを発揮した。

７今後の課題
本研究ではフリッカーのタグを推薦するシステムを提案し、評価を行った。今後は他のタグを推薦する研究（例えば画像処理からタグを推薦するもの）と組み合わせてより精度を上げていきたい。









投稿者 時刻:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)