大規模ソーシャルサーチエンジンの構造

はじめに

Googleのように，どのドキュメントが適切なのかを選ぶのではなく，質問を誰にするのが適切かを選ぶ検索エンジンをAardvarkという会社が作り，その構造を論文で公開しました．この会社はもともとGoogleの社員だった人達が作った物で，最近Googleが買い上げました．今日はその論文の要旨をまとめてみました．

タイトルと著者

タイトルはGoogle創始者のLarry PageさんとSergey Brinさんが1988年に発表した"Anatomy of a Large-Scale Hypertextual Search Engine"と韻を踏んでいます．論文を発表したのは，Aardvark社のDamon HorowitzさんとStanford Univ.のSepandar D. Kamvarさんです．以下小見出しが章，少々見出しが節という形式で進めます．

ABSTRACT

Aardvarkは会社名であると供に，この会社が作ったSocial Search Engineの名前でもあります．ユーザはIM，email，web入力，text messageや音声で質問をします．Aardvarkは，質問をした人のextended social network中で，その質問に最も適切に答えられると考えた人にその質問を廻します．

INTRODUCTION

The Library and the Village

従来，情報を取得するためにはどうlibraryを使いこなせばいいか，という事が検索の理論的枠組みの基礎となっていました．Google自体"Stanford Digital Library project"から生まれました．一方で人々は，Aardvarkがvillage paradigmと呼んでいる情報取得方法を古くから使ってきました．情報は，村の中では薄く，かつ，人から人へ伝わりながら存在します．質問の答えを見つけるためには，正しい文章を見つけるのではなく，情報を持っている人を見つけなければなりません．

Aardvark

Aardvarkはvillage paradigmに基づいたsocial search engineです．

OVERVIEW

Main Components
  • Crawler and Indexer：情報源を見つけてラベル付けします．ここでいう情報源とは，文章ではなくて人のことです．
  • Query Analyzer：ユーザが必要としている情報を理解します．
  • Ranking Function：適切な情報源を選択します．
  • UI：人々に受け入れやすい，対話的な情報提供方法です
The Initiation of a User

ユーザが初めてAardvarkにアクセスすると，Aardvarkはどんな質問をそのユーザに廻すのが適切かを判断するindexing stepsを実施します．どんな質問を廻すかはそのユーザのextended social networkに依存するので，Aardvarkはユーザの友人をindexesすることと，ユーザとその友人との関係を調べます．その狙いは単にsocial networkを作る事にあるのではありません．ユーザから彼らのextended social networksを利用させてもらうことにあります．Aardvarkでは，ユーザは実社会における人間関係を反映したいくつかのgroupsで結びつきます．これらのgroupsはsocial networksから自動的に取り込むこともありますし，ユーザが編集することもできます．

さらにAardvarkは，ユーザのtopicにおける知識や経験がどのレベルにあるのかを複数の観点から判定しForward Indexにindexesします．Forward IndexにはuserIdに対するtopicごとのレベルのリスト，そのユーザが解答した質問内容と解答の質が格納されています．AardvarkはForward IndexからInverted Indexを作成し，そこでは任意のtopicIdに対して専門性があると判断したユーザのリストとそれらのユーザごとのレベル，回答の質と回答に要した時間を格納しています．

The Life of a Query

Aardvarkはユーザの質問をMessage data structureに正規化しConversation Managerに送ります．Conversation Managerがそのmessageを質問だと判断すると，その質問がどんなtopicsに属しているのかを調べる為Question Analyzerに問合せます．Conversation Managerは，Question Analyzerから得たtopics種別がユーザの考えと一致しているかどうかをユーザに確認し，違っていれば訂正してもらいます．それと同時にConversation ManagerはRouting Engineに対してRouting Suggestion Requestを発行します．Routing EngineはInverted IndexとSocial Graphを使って回答してくれそうな候補者リストを作成し，候補者の回答の質と質問者の希望にどれくらい合致するかを基にランク付けします．Routing Engineはランク付けしたRouting SuggestionsをConversation Mangerに返却します．Conversation ManagerはRouting Policyに従い，回答候補者に質問に返事できるかを問い合わせ続けます．最終的にConversation Managerは回答を質問者に返し，質問者と回答者が追加情報のやりとりを必要とする際には情報を中継します．

ANATOMY

The Model

Aardvarkのcoreは潜在的な回答者へ質問をroutingするための統計モデルにあります．このモデルは，aspect modelと呼ばれている物をネットワーク用にしたものを使っています．このモデルには2つの特徴があります．

    • ユーザu_iがtopic t(t \in T = t_1, ... tn)に属する質問qに答える確率p(u_i|q) = \sum _{t \in T} p(u_i|t)p(t|q)
    • どのような質問であるかに係らずユーザu_iがユーザu_jの質問に答える確率p(u_i|u_j)

これらふたつの確率を掛け合わせた物がscoring function s(u_i,u_j,q)です．

s(u_i,u_j,q) = p(u_i|u_j) \cdot p(u_i|q) = p(u_i|u_j) \sum _{t \in T} p(u_j|t)p(t|q)

ranking problemとしての目標は，ユーザu_jから質問qを与えられた時，s(u_i,u_j,q)を最大にするユーザu_i \in Uのリストを作成することにあります．

Social Crawling

Aardvarkにとっての情報源は人なので，active userを維持し増やして行くことが必要です．そのためには使ってよかったという体験をユーザに与える必要があります．

Indexing People

Aardvarkはユーザu_iについて以下の2点知る必要があります．

    • ユーザu_iがp_{smoothed} (t|u_i)で答える事ができるtopic t
    • ユーザu_iとユーザu_jとのconnections p(u_i|u_j)

まずはtopicについて．
p(t|u_i)の値は，過去そのユーザが行った発言から推測します．特定のtopicに関してある確率で回答するコンテンツジェネレータとしてユーザを見るわけです．すべてのtopicに対してスコアを作成しユーザプロファイルに登録します．加えて，

  • ユーザが無視したtopic
  • 機会があったのに回答を拒否したtopic
  • 回答に対して別のユーザから否定的なコメントがついたtopic

を調べ，ユーザに対して送るべきではないtopicを学習します．
さらに，定期的にtopic strengthening algorithmを実行します．このアルゴリズムの基本的な考え方は，あるユーザが特定のtopicの専門家で，そのユーザのほとんどの友人がやはりそのtopicの専門家であれば，そのユーザが自分の友達グループの中でただ一人の専門家である場合よりも高い信頼を置く，というものです．
あるユーザをu_i，そのユーザの友達グループをU，特定のtopicをtとしたとき

if p(t|u_i) \neq 0 then s(t|u_i) = p(t|u_i) + \gamma \sum _{u \in U} p(t|u)

となります．ここで \gammaは小さな定数です．

加えて，ふたつのsmoothing algorithmsを実行します．これは明示的に回答していないtopicに対して確率を割り当てる手段で，ひとつは，basic collaborating filtering techniquesで，似たようなtopicに対しては似たような値にします．もうひとつはsemantic similarityです．

これらの作業を経て，あるユーザに対するすべてのtopicに対するスコアを得ることができるので，\sum _{t \in T}p(t|u_i) = 1となるように正規化しておきます．Bayesの定理から，あるtopicとユーザに対して

p(u_i|t) = \frac{p(t|u_i)(p(u_i)}{p(t)}

が得られます．ここで，p(u_i)は一様分布，p(t)はtopicを観測した割合です．Aardvarkは算出したp(u_i|t)をtopicをキーにした転地インデックスに格納し，質問が来た時に備えます．

次にConnectionsについて．
Aardvarkは任意のユーザ間のconnectionp(u_i|u_j)をさまざまな方法で算出します．ソーシャルネットワーク上での距離も重要ですが，demographics（人口統計学）や振る舞いの類似性も重要です．考慮している項目には以下のようなものがあります

  • Social connection (common friends and affiliations)
  • Demographic similarity
  • Profile similarity (e.g. common favorite movies)
  • Vocabulary match (e.g. IM shortcuts)
  • Chattiness match (freequency of follow-up messages)
  • Verbosity match (the average length of messages)
  • Politeness match (e.g. the use of "Thanks")
  • Speed match (responsiveness to other users)

ユーザ間のconnectionの強さはweighted cosine similarityを使って計算し， \sum _{u_i \in U}p(u_i|u_j) =1となるよう正規化します．
topicとconnectionは常時更新します．

Analyzing Questions

質問を解析する目的は質問qからtopicに対するスコアのリストp(t|q)を導きだすことにあります．まず，以下のClassifierを適用し，回答すべき質問を選別します．

  • NonQuwestionClassifier: 質問かどうか
  • InappropriateQuestionClassifier: Q&Aとして適切な文章かどうか
  • TrivialQuestionClassifier: 人に聞かないと答えられない質問かどうか
  • LocationSensitiveClassifier: 特定の地域に関する知識が必要かどうか

次に以下のTopicMapper algorithmsで得られた結果を統合して，質問に対するtopicのリストを得る事ができます．

  • A KeywordMatchTopicMapper: user profileのtopicに記載された文字列と一致するか
  • A TaxonomyTopicMapper: SVMを用いて約3,000種類に分類
  • A SalientTermTopicMapper: 質問からの特徴語の抽出
  • A UserTagTopicMapper: 質問者によって付けられたタグ
The Aardvark Ranking Algorithm

ランキングはRoutingEngineが行い，質問者と，Question Analyzerから受け取った情報を元に，よい回答をしてくれそうな人の順序リストを作成します．ユーザのランキングを決定するために必要な要素は，Topic Expertise p(u_i|t)，Connectednessp(u_i|u_j),Availabilityです．

  • Topic Expertise: まず，Routing Engineは質問とsemantic matchesするユーザ群を探します．location-sensitiveな質問に関しては，ユーザプロフィールがその場所と一致するユーザのみ考慮します．
  • Connectedness: 次にRouting Engineは回答者のtopicに関する専門性とは無関係に，質問者とどれぐらいの親和性があるかを見極めます．
  • Availability: 3つ目にRouting Engineは質問に今回答してくれそうな人の優先度付けををします．これはIMでオンラインになっているかどうかなどを参考にします．

回答してくれそうな人のリストができるとAardvarkはガイドラインに基づいてコンタクトしてはならない人を除外します．残ったリストをConversation Managerに渡します．Conversation Managerはリストのそれぞれの人にアクセスして，回答が得られるまで，質問に答えてくれるかどうか訪ねて廻ります．

この後の論文は…

と続きます．UIは面白いと思うのですが，アーキテクチャではないと思うのでここでは取り上げません．（疲れたともいう）詳しくは元論文をごらん頂くか，The Anatomy of Large-Scale Social Search Engine: ソーシャル検索エンジンAardvark論文の輪講用資料 - シリコンの谷のゾンビに載っている資料をごらんください．

おわりに

いくつかアルゴリズムの名前が出てくるんですが，それがなんだかわかってません．勉強しないと．最近ソーシャルアプリ流行だし，答えを知ってる人を推薦してくれるアプリというのは面白いと思うんですが，いつになったら自分で作れることやら… とりあえず，睡眠不足の日々が解消できてうれしいです．