proceeding slide: slideshare

まとめ

CIKM 2013でBest paperを取った、著者が全員女性(参考)という、自分が今まで読んだ中でおそらく一番華やかな論文で、Yahoo Answersを知識源として、セレンディピティ (思ってもみなかったけど、クエリと関連していること) を感じる検索を提供する話。 何か新たな手法を提案した、というよりは、Yahoo Answersという知識源を使うことで、何か思ってもみなかったけど、面白い検索結果を提供できるんじゃないかな〜というアイディアを実際に試してみた、という感じだろうか。

以下、メモ。

Why/when do penguins wear sweaters?

  • タスマニアで起きた原油漏れで体に油がついてしまったペンギンが、再び元の生活に戻れるようにするためのチャリティーソング (James GordonのSweaters for Penguins)
    • 羽毛に原油がつくことで断熱性が落ち、ペンギンが凍えてしまう
    • くちばしで羽毛に付いた原油を落とそうとすることで体を傷つけてしまう

Serendipity

役に立つんだけど、特に探していたわけではないもの。

この論文ではWikipediaとYahoo! Answersから抽出した、メタデータで情報を豊富にしたentityネットワークを基にentity-driven serendipitous search systemを作成する。

この論文の焦点

WHAT

ウェブコミュニティの知識源はどのようなentity間の関係を提供するのか？

WHY

そのような知識源がどのように面白く、セレンディピティなブラウジング経験に寄与するのか？

データ

Yahoo! Answers

  • ごくわずかにまとめられた意見、ゴシップ、個人情報
  • 観点が多様

Wikipedia

  • 高品質の情報が整理されている
  • ニッチなトピックが豊富

Entity & Relation Extraction

Entity: Wikipediaに記述されている概念

1 テキストから表層形を識別し、 2 Wikipediaのentityと紐付けして、

  • 文脈依存
  • 文脈非依存な素性
    • click log

3 Wikipediaのentityを、テキストとの関連度順に基いてランキングする (aboutnessスコア(34)を使ってランキングする)

Reationship: tf/idfベクトルのコサイン類似度

entityが現れるドキュメントを結合したものがベクトルで表される

Dataset Features (Metadata)

Sentiment

  • SentiStrengthを用いてpositive & negativeのスコアを計算する
    • インフォーマルな英語の極性判定でstate-of-the-art
    • このままだと文書レベルでの極性判定
      • 文単位でpositive、negativeのスコアを割り当てて、それぞれの平均が文書単位の極性のスコアになる
    • 文書は複数のentityを含むことが多いのでentity単位での極性はうまく測れない
    • まずentityのそれぞれ前後10単語のウィンドウに対して極性のスコアを計算する
  • attitudeとsentimentalityをウィンドウに対して計算する[Kucuktunc’12]
    • attitude: positiveもしくはnegativeに対する傾向
    • sentimentality: 極性の大きさ
  • entityが現れるウィンドウのattitude, sentimentalityの平均値がentity単位の素性とする

Quality

  • 可読性
  • Flesch Reading Ease score[14]
    • スコアが高いほど理解するのが難しい
    • スコアが低いほど理解するのが易しい
  • Fig1は二つのデータセットにおけるエンティティの可読性の分布

Topical Category

  • Yahoo Content Taxonomy
    • Table 2
    • 二つのデータ・セット中の概念体型は使わない
      • 整合性をとるため
      • 二つのデータセットにおける実験結果を比較するため
  • US-Englishのニュース記事を使って訓練した分類器で文書分類する
  • entityレベルの素性にするため、そのentityが現れた文書に割り当てられたカテゴリのうち、頻度が高い上位3つのカテゴリを素性にする

Retrieval

Algorithm: Lazy Randomwalk with restart

  • self-loop probability: beta 他のノードへの伝搬を遅らせて、random walkの開始ノードの重要性をより高める
    • 先行研究にしたがって、beta = 0.9 [6, 12]
  • follow one of the out-links with probability: 1 - beta エッジの重みに比例してrandom walkする
  • random jumpの確率は0 (alpha = 0)
    • random jumpすると結果が悪くなるため
  • 反復の終了条件
    • 前回とのノルムの差が10^-6以下、もしくは30回反復した

scoring method

  • popularなentityはどこにでも上位にランクされるのでこれらをフィルタリング

Testbed

  • 2010~2011にGoogle Zeitgeistで最も検索されたクエリの中から、Wikipedia、Yahoo! Answersの文書中に共に現れる上位50件のクエリ

Precision @5, MAP

  • Precision: 66.8% on WP, 72.4% on YA
  • MAP: 0.716 on WP, 0.762 on YA ふたつのデータセットでの性能は同等であるものの、ランキングされるentityにはあまり重複がないため、二つのランキング結果を結合すると性能が上がる
    • Fagin et al. [13]のrank aggregationを使う

Annotator agreement

  • 1つのクエリにつき、annotatorは3人
    • クラウドソーシングしてるので、信頼出来ないannotatorは排除
  • (overlap): 0.85%
    • 馴染みのないクエリはagreementが低い (Secosteroid, Sally Kern, …)

Average overlap in top 5

  • results: 12%
    • = 0.6 entity/top 5 entities

Error analysis

提案手法の有効性はクエリのentityのすぐとなりのentityをあまり上に挙げないことによる

  • 例) Egyptに最も近い二つのentity
    • British Pacific Fleet, FC Groningen (WP)
    • Spring, IGN (YA)
    • Springは"Arab Spring"と間違えて識別された可能性があるが、このSpringは提案手法があまりEgyptの近くをみないので下位にランクされる

とても似通ったentityばかりが上位にランクされてしまうこともある

  • 例) インフルエンザのウィルス名、Mac PowerBookのバージョン名で上位がうまる
    • random walk時に密度が高いサブグラフにトラップされてしまうことで起きる

entityは関連していないentityが近くに来ることがある

  • entity extractionの失敗
  • 文脈類似度を測るときのノイズ
  • 例) 同音異義語が強くつながってしまう
    • 意味的な素性を使わずに類似度を測ってしまう
    • (意味が違うなら文脈も違う気もする…)

制約

二つのデータセットが、serendipitous searchに何をもたらしてくれるのか調べる

  • YAとWPにおける実験結果を比べる
  • どの素性が検索結果に影響するのか調べる
    • このために、データセットからメタデータを抽出する
    • そして、sentimentality, quality, topical categoryの次元に対して、検索に制約をかける

制約をかけたネットワークと、制約をかけていないネットワークでの結果を比べる

Topic

Question: クエリに対してトピック的にコヒーレントなentityは良い結果をもたらすのか？ Constraint 1: entityは少なくとも1つ以上のクエリと同じトピックカテゴリに属さなければならない

High/Low Sentimentalyty

Question: より感情的な(感情的でない)entityは良い結果をもたらすのか？ Constraint 2(3): entityは中央値(0.6 for YP, 0 for WP)よりも高いsentimentalityでなければならない

High/Low Readability

Question: より読みやすい(読みにくい)entityは良い結果をもたらすのか？ Constraint 4(5): entityのreadabilityスコアは中央値(46 for YA, 41 for WP)でなければならない

制約の結果

  • low-sentimentalityとlow-readabilityが負の影響を持っている

Serendipity

  • accuracy以外にも推薦エンジンの性能を測ることが重要である
  • serendipity = unexpectedness + relevance
  • baselineの結果に入っていない結果のrelの平均
    • relはannotatorの判断（？）
  • baseline
    • Top: 2つの商用検索エンジンの検索結果のうち、最も上位5位の検索結果に現れる回数が多いentity
    • Top Nwp: TopからqueryのWikipediaの記事を除いたもの。WPに対するバイアスを避けるため
    • Rel: 2つの商用検索エンジンから提案される関連クエリから得られる結果のうち、頻度が高い上位5件のentity
    • Top+Rel: Top, Relの和集合
  • Table 5: 各baselineに対する、各制約条件で計算されたserendipity
    • topic-constrainedな条件ではすべてのbasline/datasetにおけるserendipityを上回っている
    • YAは常にWPを上回っている
    • COMが一番良いserendipityを出せる
    • 括弧の中の値は各制約条件で提示されたすべての結果に対するunexpectedでrelaventな結果の割合
      • baselineによって弾かれていたentityも含めたときの値
    • これはだいたいserendipityと同じくらいの高さになっている
      • つまり、最も強いbasline Rel+Topと比べた時でさえ、提案手法はすごい数のunexpectedでrelaventな結果を検索している

User-Perceived Quality

  • 主観的な評価になるので、結果に値を入れるのでは無く、色々な条件での実験結果を比較する
  • 順序付きリストの要素のペアワイズで比較する (順番はランダムに決める)
    • 最初のほうが良かった
    • 二つ目のほうが良かった
    • 両方だめだった
  • reference result rankingを各次元に対して構築する
    • ランキング結果の集合の和集合(?)
  • 各ペアは3人のannotatorにより評価される
    • ほとんど重複がない時に評価するのは非常に手間がかかる
    • 適切なランクを推定するために、すべての順序リスト中の要素のペアから比較するペアをサンプリングする

Labeling

  1. どちらの結果がよりクエリと関連しているか？
  2. そのクエリに興味を持つ人がいたら、その人はこの結果に興味を持つと思うか？
  3. あなたがそのクエリに興味がないとしても、この結果はおもしろいか？
  4. そのクエリについてなにか新しいことを学んだか？

Table 6: ランキングの集合とreference ranking間のKendall’s tau-b

  • personal interest (Q3)とrelevance (Q1)の好みの割合の差を計算する時に、おもしろいけど必ずしもクエリと関連している必要のないentityを見つけた
    • Oil Spill -> Sweaters for Penguins
    • Robert Pattinson -> Water for Elephants
    • Egypt -> Ptolematic Kingdom
  • 専門的には似ているけど、面白くない例
    • Egypt -> Cairo Conference
    • Netflix -> Blu-ray Disc
  • YAはreference rankに似た結果を出せている
  • Topical categoryはreferece rankingとの類似度を高めている
  • Sentiment & Readabilityもreferece rankingとの類似度を高めている

関連記事






最近の記事