stop-the-world

takuya-a のブログ

Information Retrieval and Web Search まとめ(25): パーソナライズ

前回は、質問応答とその手法（テキストベース、ナレッジベースを使った方法、それらのハイブリッド）について説明した。今回はパーソナライズについてまとめる。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の25日目の記事です。

adventar.org

パーソナライズ

クエリの曖昧性とパーソナライズ

  • 短いクエリではユーザの情報ニーズを明確に表現できない
  • たとえば chi は以下のような意味をもつ
    • Calamos Convertible Opportunities & Income Fund quote
    • The city of Chicago
    • Balancing one’s natural energy (or ch’i)
    • Computer-human interactions
  • つまり、1つのランキングでは、すべてのユーザに最適なものにはできない
    • パーソナライズドランキング (personalized ranking) がそのギャップを埋めるただ1つの方法
  • パーソナライズに以下のような情報を使うことができる：
    • ユーザの長期的な振る舞い（ユーザの長期的な興味を判定するため）
    • 短期的なセッション情報（ユーザの現在のタスクを判定するため）
    • ユーザの位置情報
    • SNS (social network)
    • ...

パーソナライズのポテンシャル

  • [Teevan, Dumais, Horvitz 2010]
  • RQ
    • パーソナライズすることによってどのくらいランキングを改善できるか？
    • そして、それをどのように計測するか？
  • 評価者 (rater) に明示的に検索結果のレーティングを付けてもらう
    • ただし、評価者にユーザの情報ニーズが何であったか予想してもらうのではなく、個人的な考えで適合しているかどうかの観点で評価
  • 各クエリ q に対して
    • 各検索結果の平均レーティングを計算
    • 平均レーティングを使って最適ランキング R_q を決定
    • 各評価者 i に対して、ランキング R_q をもとにした NDCG を計算
    • そうして計算された各評価者の NDCG の平均 Avg_q を計算
  • すべてのクエリでの Avg_q の平均を Avg とする
  • パーソナライズのポテンシャルを (1 - Avg) とする

f:id:takuya-a:20201225215923p:plain
([Teevan+ 2010] Figure 4) 最適なパーソナライズによるスコア（平均 NDCG）を 1 (Individual) としたときの、パーソナライズしなかった場合の NDCG (Group)

パーソナライズド検索の概要

  • [Pitkow et al. 2002]
  • パーソナライズド検索 (personalizing search) の2つの一般的な方法
    • クエリ拡張 (query expansion)
      • ユーザのクエリを、ユーザの意図 (intent) に応じて修正 (modify) もしくは拡張 (augment) する
      • 例： IR --> "information retrieval", "Ingersoll-Rand"
    • リランキング (reranking)
      • 同じようにクエリを発行し、検索結果を取得したあと、それを並べ替える
      • パーソナライズされた結果を得ることも、全体的に適合する (globally relevant) 結果を得ることもできる

ユーザ意図

  • ユーザによって与えられたもの
    • ときには役立つ（とくに新しいユーザの場合）
  • ユーザの振る舞いやユーザのデータから推論されたもの
    • 過去に発行されたクエリ
    • 過去に訪れた Web ページ
    • 個人の文書データ
    • Email
  • プライバシーを守ることが非常に重要

適合性フィードバックによるパーソナライズ

f:id:takuya-a:20201225220047p:plain
([Teevan+ 2005] Figure 1) 古典的な適合性フィードバック（左）と、ユーザプロファイルを使った適合性フィードバック（右）

  • 古典的な適合性フィードバック (traditional relevance feedback)
    • N: コーパスの文書数
    • n_i: ターム i を含む文書数
    • R: 適合する文書数
    • r_i: ターム i を含み、かつ適合する文書
  • 個人プロファイル適合性フィードバック (personal profile relevance feedback)
    • 適合する文書 (R) として、コーパス外のユーザデータを使う
    • R: 適合する文書数
    • r_i: ターム i を含み、かつ適合する文書
    • N' = (N+R): コーパスの文書数 + ユーザデータの文書数
    • n_i' = (n_i + r_i): ターム i を含む文書数

リランキング

  • スコア関数として、BM25 を変えたものを使う
  • スコア関数は以下の形のものを使う:
 \displaystyle\sum w_i \cdot tf_i
  • tf_i はタームが文書中に出現した頻度 (term frequency)
  • w_i はそのタームの重み (term weight)
  • 古典的な適合性フィードバック ([Teevan+ 2005] Figure 1a) では、タームの重み w_i は以下のようになる
 w_i = \log \dfrac{(r_i + 0.5) (N - n_i - R + r_i + 0.5)}{(n_i - r_i + 0.5)(R - r_i + 0.5)}
  • N' = (N+R) と n_i' = (n_i + r_i) を使って、ユーザデータを使った適合性フィードバック ([Teevan+ 2005] Figure 1b) でのターム重み w_i は以下のようになる
 w_i = \log \dfrac{(r_i + 0.5) (N - n_i + 0.5)}{(n_i + 0.5)(R - r_i + 0.5)} \approx \log \dfrac{(r_i + 0.5)}{(R - r_i + 0.5)} + IDF_i

コーパスの表現

  • N と n_i を推定する
    • コーパスは Web の文書すべて
    • クライアント側でパーソナライズを行う場合、コーパスの統計情報に直接アクセスすることはできない
    • Web 検索を実行して返ってきた検索結果を使って推定する
  • N の推定: 英語でもっとも頻度の高い単語である "the" のヒット数を使う
  • n_i の推定: その単語 i の1単語だけで検索したヒット数を使う

ユーザの表現

  • R と r_i をローカルの検索インデックスから推定する
    • ユーザが閲覧したページ
    • ユーザが閲覧したり送信した Email
    • カレンダーの予定
    • クライアントマシン上の文書
  • R の推定: ローカルのインデックス上の文書数を使う
  • r_i の推定: ローカルのインデックスで単語 i を検索したときのヒット数を使う

文書とクエリの表現

  • 文書はタイトルとスニペットで表現される
  • クエリは、クエリ文字列の近くに出現した単語で拡張される
    • もとのクエリが cancer だったとき、以下の下線の単語がクエリになる

The American Cancer Society is dedicated to eliminating cancer as a major health problem by preventing cancer, saving lives, and diminishing suffering through...

Personalized PageRank

  • [Haveliwala 2002]
  • [Jeh and Widom 2003]
  • 通常の PageRank では、すべてのページにおいてテレポート確率ベクトル (teleportation probability vector) p は一様 (uniform) だった
  • ユーザの嗜好 (preference) をその p によって表現する
    • ユーザがどのページにテレポートするかが、ユーザによって変わる
    • p はユーザのブックマークにあるページのなかで一様とする
    • もしくは、ユーザが興味をもっているトピックのページについてはテレポート確率が存在することにする
  • しかし、 Personalized PageRank を計算するのは高コスト

Linearity theorem

  • 任意の preference vector \boldsymbol{u_1} と \boldsymbol{u_2} に対して、 \boldsymbol{v_1} と \boldsymbol{v_2} がそれぞれに対応する personalized PageRank vector だとする
  • このとき、 a_1 + a_2 = 1 となる任意の非負の定数 a_1, a_2 に対して以下が成り立つ
 a_1 \boldsymbol{v_1} + a_2 \boldsymbol{v_2} = (1 - \alpha) \textbf{A} (a_1 \boldsymbol{v_1} + a_2 \boldsymbol{v_2}) + \alpha (a_1 \boldsymbol{u_1} + a_2 \boldsymbol{u_2})

Topic-sensitive PageRank

  • トピックごとに personalized PageRank vector を計算する
    • Open Dictionary Project にある 16 のトップレベルのトピックを使用
    • ページに対してトピックが手で分類されている
    • トピックに対する preference vector は、トピック内では一様分布とする
    • トピック外では 0 とする
  • Note: [Jeh and Widom 2003] によりさらに一般化されている

クエリタイミングでの計算

  • クエリのトピックに対する分布を構築する
    • ユーザプロファイルからトピックの分布を計算
    • 他のコンテキスト情報も使える
  • トピックの preference を使って、topic PageRank vector の重み付き線形和を計算し、それを通常の PageRank の代わりに使う

ソーシャルネットワークでのパーソナライズド検索

  • [Curtiss et al. 2013]
  • Unicorn: Facebook Graph Search のバックエンド
  • Facebook Graph Search
    • ノード (node) は人やもの（エンティティ）を表す
    • エンティティ (entity) はユニークな 64 ビットの id
    • エッジ (edge) はノード間の関係 (relationship) を表す
      • エッジの種類は数千タイプある： friend likes likers ...

Unicorn のデータモデル

  • ノード数は数億だが、グラフは疎 (sparse)
    • グラフを隣接リストを使って表現する
    • ポスティングは sort-key （重要度）でソートされ、次に id でソートされる
    • インデックスは id でシャーディングされる
    • オプショナルで HitData というバイト配列を保存できる
      f:id:takuya-a:20201226055853p:plain
      ([Curtiss+ 2013] Figure 2) Unicorn のデータモデル。ノードのエッジを転置インデックスのポスティングリストとして表現する

Unicorn の基本的な集合演算

  • クエリ言語は基本的な集合演算をサポートしている
    • and or difference
  • 例1: id 5 か id 6 どちらかの友達
    • (or(friend:5 friend:6))
  • 例2: id 5 の女性の友達で、 id 6 の友達ではない人
    • (difference (and friend:5 gender:1) friend:6)

サジェスト (Typehead)

  • 最初の数文字を入力するだけでユーザを見つける
  • インデックスサーバは、ある一定の文字数までのすべての名前の接頭辞 (prefix) に対してポスティングリストを持っている
  • 他の演算子と組み合わせられる
    • 例： (and mel* friend:3)

weak-and 演算子

  • Unicorn は weak-and という特殊な演算子をサポートしている
  • optional-hits optional-weight というオプションをもつ
    • その条件が満たされていなくてもよいという意味

f:id:takuya-a:20201226055823p:plain
([Curtiss+ 2013] Figure 4) weak-and のクエリ実行時のインデックス構造

  • (weak-and (term friend:3 :optional-hits 2) (term malanie) (term mars*)) の検索
    • :optional-hits 2 は、2件まで、この条件（1つめの term）が満たされていなくても結果に含める、という意味
    • 検索結果は 20 7 88 64 となる
    • 62 は返されない
    • 3 つの term 条件の全てを満たしているのは 7 と 64 だけ
    • 左から順番に見ていって、 20 と 88 は条件を 2 つしか満たしていないが、この2つまでは検索結果に含まれる
    • 62 に達したときにはすでに optional-hits の 2 を使い果たしているので、これは含まれない

講義資料

参考資料

Information Retrieval and Web Search まとめ(24): 質問応答

前回は、shingle とスケッチを利用した重複検知について説明した。今回は、Web における質問応答を扱う。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の24日目の記事です。

adventar.org

情報検索と質問応答

  • 情報検索 (information retrieval) という名前は標準になっているが、実際に行われているのは文書検索 (document retrieval) であることが多い
    • それ以上のことはユーザが自身に任されている
  • 2025 年のウェブ検索はどうなっているだろう？
    • 検索ボックスにキーワードを入力している？
    • セマンティックウェブを使っている？
    • 自然言語でコンピュータに質問している？
    • ソーシャル検索、もしくは人力の (human powered) 検索を使っている？

Google 検索の歴史

  • Pigeon アップデート (July 2014)
    • ランキングシグナルとして距離や位置情報をより重視するようになった
  • Mobilegeddon (Apr 21, 2015)
    • モバイル親和性 (mobile friendliness) が主要なランキングシグナルに組みこまれた
  • App Indexing (Android, iOS support May 2015)
    • 検索結果からアプリに遷移できるようになった
  • Mobile-friendly 2 (May 12, 2016)
    • 約半数の検索がモバイル由来になった
  • Fred (1Q 2017)
    • スパムサイト (spammy, clickbaity, fake) を下げるような様々な変更が入った
  • 検索結果ページのスニペットがより長くなった (Nov 2017)
  • Mobile-first Index (Mar 2018)
    • デスクトップ版ではなくモバイル版のページをインデックスするようになった
  • 検索結果ページのスニペットの長さが元に戻った (May 2018)
  • Medic アップデート
    • ページの専門性、権威性、信頼性をより重視するようになった
    • ダイエットや栄養、医療品に関するサイトでランキングに大きな変化があった
  • コアアルゴリズムアップデート (Mar 2019)
    • "Medic 2" 的なアップデートがされた

ナレッジベースを使った検索

  • 古典的なテキスト検索ではなく、構造化されているナレッジベース (knowledge base) を使ってグラフ検索を行う
  • Web ページに埋め込まれている半構造化データを使ったアプリケーションも増えている

Web 検索における最近の課題

  • モバイル検索の増加
    • モバイルでの検索が増えたことにより、音声検索、自然言語による検索が増えつつある
    • モバイルでは自然言語理解 (natural language understanding) や質問応答 (question answering) が重要になることがわかってきた
  • 情報の質
    • 情報源 (information provenance) や情報の信頼性 (information reliability) は Web においてずっと懸念されてきたが、近年、「フェイクの (fake)」情報が拡散されるようになっている

知的エージェントに向けて

  • 2つのゴール
    • 文字列を使わない (things, not string)
    • 検索ではなく推論 (inference)

質問応答

質問応答のパラダイム

  • テキストベースのアプローチ
    • TREC QA, IBM Watson, DrQA
  • 構造化されたナレッジベースを使ったアプローチ
  • 上記のハイブリッド

"Things, not strings"

From To Requires
ターム (term) 概念 (concept) パース (parsing)、曖昧性解消 (disambiguation)、共参照解析 (coreference)
タームの同一性 (term identity) 含意 (entailment) 概念の関係性 (concept relations)
共起 (co-occurrence) 構文的関係 (syntactic relation) 文書構造、パース (parsing)
タームインデックス (term index) 意味インデックス (semantic index) 概念の曖昧性解消 (concept disambiguation)、推論 (inference)

行動と意図

f:id:takuya-a:20201224234143p:plain
ユーザの検索意図と行動

エンティティの曖昧性解消とリンキング

Siri のアプローチ

  • クエリの意味表現 (semantic representation) を構築
    • 時刻、日付、場所、エンティティ、数量
  • このセマンティクスで構造化データベースにクエリ

テキストベース質問応答

  • 質問処理 (question processing)
  • パッセージ検索 (passage retrieval)
  • 回答処理 (answer processing)

IBM Watson

  • ハイブリッドアプローチ
    • クエリの浅い (shallow) 意味表現を構築
    • 情報検索の手法で回答候補を生成
    • よりリッチな知識情報を使って、各候補をスコア付けする
      • 地理空間データベース
      • 時間の推論 (temporal reasoning)
      • タクソノミー (taxonomical classification)

言語から知識へ

単語アラインメント

f:id:takuya-a:20201224234244p:plain
([Wen-tau+ 2013] Figure 1) 単語アラインメント

LCC の質問応答システム

f:id:takuya-a:20201224234337p:plain
([Harabagiu+ 2003] Figure 1) 質問応答システム LCC のアーキテクチャ

Open-domain Question Answering

f:id:takuya-a:20201224234413p:plain
([Chen+ 2017] Figure 1) 質問応答システム DrQA の概要

  • 古典的な TF-IDF とバイグラムのハッシュを組み合わせると document retriever の性能が上がった

f:id:takuya-a:20201224234503p:plain
([Chen+ 2017] Table 3) 文書検索の精度

講義資料

Information Retrieval and Web Search まとめ(23): 重複検知

前回は Web クローラの要件やそのアーキテクチャについて解説した。今回は、重複した文書の検知について扱う。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の23日目の記事です。

adventar.org

重複ページの検知

  • Web には重複コンテンツがたくさんある
  • 厳密な重複検知（= 完全一致 (exact match)）は一般的ではない
  • だが、準重複 (near duplicate) 検知の例は非常に多い
    • 例：ページ内容は同じだが更新日だけが違う

重複・準重複検知

  • 重複 (duplication): 完全一致はフィンガープリント (fingerprint) によって検知できる
  • 準重複 (near-duplication): 近似マッチ (approximate match)
    • 構文的な類似度を編集距離によって計算する
    • その類似度の閾値で準重複コンテンツを検知する
    • これは推移的にはならないが、推移的として扱うこともある
      • A と B、B と C がそれぞれ準重複だったとして、A と C は準重複とは限らない

類似度の計算

  • 特徴量
    • 文書のセグメント
      • 自然な、もしくは人工的な場所で分割
    • shingles
      • 単語 n-gram　などを使う
  • 類似度の指標
    • それぞれの文書の shingles に対して定義される
    • ジャッカード係数 (Jaccard coefficient)
      • 共通集合の要素数 / 和集合の要素数
  • 文書 d_j のshingleを S(d_j) で表すとすると、文書 d_1 と d_2 のジャッカード係数は
 J(S(d_1), S(d_2)) = \dfrac{|S(d_1) \cap S(d_2)|}{|S(d_1) \cup S(d_2)|}

スケッチ

  • shingles どうしの正確な共通集合 (intersection) S(d_i) \cap S(d_j) を計算するのは高コスト
  • それぞれの shingles から、部分集合を賢く選んで近似する
    • 近似した shingles の部分集合をスケッチ (sketch) と呼ぶ
  • 共通集合の要素数 / 和集合の要素数 （ J(S(d_1), S(d_2))）を、スケッチから推定する

スケッチベクトルの計算とジャッカード係数の推定

  • 各文書に対してスケッチベクトル (sketch vector) を作成する
    • スケッチベクトルの次元数 m は ~200 次元
    • スケッチベクトルの要素が t 以上（80% 以上など）かぶっている文書は準重複 (near duplicate) であるとみなせる
  • 準備
    • 文書の shingles を 1 .. 2^{m} のいずれかの値に写像する、以下のような集合関数 H() を用意する
      • H(d_j) は、文書 d_j の shingles S(d_j) の各要素のハッシュ値からなる集合
      • m = 64 のとき、 H(d_j) の要素は 64 ビット非負整数のいずれかの値をとる
    • 1 .. 2^{m} のランダムな置換 (permutation) \pi() を用意する
      • 1 .. 2^{m} を 1 .. 2^{m} のいずれかの値にランダムに入れ替える写像
      • 置換は全単射なので異なる値が同じ値に写像されることはない
    • H(d_j) の各要素を \pi によって置換したものを \Pi(d_j) とする
      • H(d_j) の各要素 h \in H(d_j) に対して、対応する値 \pi(h) \in \Pi(d_j) が存在する
  • 文書 d_j の \pi によるスケッチ x_j^{\pi} は \text{min}(\Pi(d_j)) （ \Pi(d_j) のうち最小の整数）で計算される

f:id:takuya-a:20201223235614p:plain
(IIR p.439 Figure 19.8) スケッチ計算の例

  • このスケッチの計算を 200 個のランダム置換 \pi_1, \pi_2, ..., \pi_{200} に対して行う
    • 200 次元のスケッチベクトルを計算する場合
  • このようにして得られた 200 個のスケッチ x_j^{\pi_1}, x_j^{\pi_2}, ..., x_j^{\pi_{200}} を並べたものを、文書 j のスケッチベクトル \phi_j とする
  • 文書 i と文書 j のペアに対するジャッカード係数 J(S(d_i), S(d_j)) を |\phi_i \cap \phi_j| \, / \, 200 で推定する

置換の効率化

  • ランダムな置換は計算コストが高い
  • 線形の置換でも実用上はうまくいく
    • 大きな素数 p に対して、以下のような {0, ..., p-1} 上の置換の集合を考える
 \mathcal{F}_p = \{ \pi_{a,b}: 1 \leq a \leq p-1, 0 \leq b \leq p-1 \} \; \text{where} \; \pi_{a,b}(x) = ax + b \, \text{mod} \, p

まとめ

  • shingling は乱択アルゴリズム (randomized algorithm) である
    • なんの確率モデルも仮定していない
    • ある確率で正しい答えを返す
  • 文書のペアに対して準重複検知を行う方法を示した

講義資料

参考資料

Information Retrieval and Web Search まとめ(22): Webクローリング

前回は PageRank などのリンク解析手法について説明した。今回は、Web のクローリングを扱う。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の22日目の記事です。

adventar.org

クローリングの概要

  • クローラ (crawler) （もしくはスパイダー (spider)、ロボット (robot)、ボット (bot) とも）は、Web ページのリンクを辿り、検索エンジンにページをインデックスするためのコンポーネント
  • これらの一連の処理をクローリング (crawling) という

f:id:takuya-a:20201223044038p:plain
(IIR p.434 Figure 19.7) Web 検索エンジンのコンポーネント

クローラの動作

  • 「シード (seed)」となる既知の URL から開始する
  • Web ページをフェッチしたあとパースする
    • ページに含まれる URL を抽出する
    • 抽出した URL をキューに入れる
  • キューにある URL をフェッチし、繰り返す

f:id:takuya-a:20201223043937p:plain
Web クローリングの概念図

クローリングの難しさ

  • Web のクローリングは1台のマシンでは実現不可能
    • 上記のすべてのステップは分散化される必要がある
  • 悪質なページへの対応
    • スパムページ
    • スパイダートラップ (spider trap)
      • 動的に生成されるページを含む
  • リモートサーバへの礼儀正しさ (politeness)
    • サーバを高頻度で叩かない
  • その他の課題
    • リモートサーバのレイテンシや帯域は様々
    • ウェブマスターの規定 (webmasters' stipulation)
      • サイトの URL の階層をどこまで辿るか
    • ミラーサイトや重複ページ

クローラの要件

クローラの MUST 要件

  • 頑健 (robust) である
    • スパイダートラップや悪質なページから影響を受けないこと
  • 礼儀正しい (polite)
    • 暗黙的・明示的な礼儀正しさを考慮していること
    • 明示的な礼儀正しさ
      • クロールするサイトのウェブマスターからの仕様を守る
    • 暗黙的な礼儀正しさ
      • （仕様になくても）サーバを高頻度で叩かない

robots.txt

  • スパイダー（= ロボット）によるアクセスを制限するためのプロトコル (1994-)
  • どのページがクロールされるべきで、どのページはされるべきではないのかをアナウンスする
    • サーバ側で /robots.txt ファイルを作成する

robots.txt の例

  • searchengine という名前のロボット以外は /yoursite/temp/ から始まる URL を訪問してはいけない
User-agent: *
Disallow: /yoursite/temp/

User-agent: searchengine
Disallow:

クローラの SHOULD 要件

  • 分散化されていること
    • 複数台のマシンで実行されるように設計されていること
  • スケーラブルであること
    • マシンを追加することでクロール速度を上げることができるように設計されていること
  • 効率的であること
    • CPU/ネットワークリソースを使い切れること
  • 質の高いページから先にフェッチすること
  • 前にフェッチしたページの新しいコピーもフェッチし続けること
  • 拡張可能であること
    • 新しいデータフォーマットやプロトコルに適応できること

f:id:takuya-a:20201223044120p:plain
クローラの要件を踏まえてアップデートした Web クローリングの概念図

  • URL frontier
    • 同じホストのページを複数含んでいてもよい
      • ただし、同じタイミングでフェッチすることは避けなければならない
    • すべてのクローラのスレッドはビジー状態をキープしなければならない

クローラのアーキテクチャ

クローラの処理ステップ

  • URL frontier から URL を1つ選択する
  • その URL をフェッチする
  • URL をパースする
    • 他の URL を抽出する
  • URL がすでに見ているかどうかチェックする
    • 見ていなければインデックスに追加する
  • 抽出された URL に対して
    • フィルタ条件に引っかかっていないか確かめる
    • URL frontier にすでにあるかどうかチェックする
      • 重複 URL の排除

クローラの基本アーキテクチャ

f:id:takuya-a:20201223044220p:plain
(IIR p.446 Figure 20.1) 基本的なクローラアーキテクチャ

  • DNS のルックアップは処理をブロック (blocking) する
    • DNS キャッシュ、バッチ DNS リゾルバなどを利用する
  • URL 正規化
    • URL のパース時に、リンクが相対 URL になっていることがあるので、正規化（展開）する
  • 重複ページの判定
    • すでに見たページは処理しないようにする
    • 文書の fingerprint もしくは shingle を使う
      • 次回扱う
  • robots.txt
    • 1度 robots.txt をフェッチしたら、繰り返しフェッチしないようにする（キャッシュする）

分散型クローラ

f:id:takuya-a:20201223044312p:plain
(IIR p.449 Figure 20.2) 分散化したクローラアーキテクチャ

  • 複数のクロールスレッドを、異なるプロセス、異なるノードの上で動かす
    • 地理的に分散されたノード
  • リモートホストをノードに割り当てる

URL frontier

  • 2つの主な目標
    • Politeness: 頻繁に Web サーバを叩きすぎない
    • Freshness: いくつかのページは優先的にクロールする
      • ニュースサイトのように、頻繁に更新されるページ
  • この2つの目標はコンフリクトする
    • たとえば、シンプルな優先度付きキューでは不可能
    • 多くのリンクが自身のサイトへのリンクなので、アクセスがバーストする
  • 一般的なヒューリスティック：前回のリクエストから時間をおいてアクセスする

Mercator URL frontier

  • Mercator クローラ [Heydon et al. 1999]
    • 多くの研究や商用のクローラの基礎となったクローラの実装 (Java)
  • Mercator のスキームは、2つの FIFO キューを使う
    • Front queue: 優先度を管理する
    • Back queue: Politeness を強制する

f:id:takuya-a:20201223044401p:plain
(IIR p.452 Figure 20.3) URL frontier

Front queue

  • Prioritizer が URL に 1 から F までの優先度を割り当てる
    • その URL を、各優先度に対応するキューに append する
    • 優先度割当てのヒューリスティック
      • 前回のクロール時にリフレッシュレートをサンプルしておく
      • アプリケーション依存の方法：サイトの種類（ニュースサイトなど）によって優先度を決める

Biased front queue selector

  • Biased front queue selector は、Back queue が URL をリクエストしたとき、その URL を pull するために Front queue を1つ選ぶ
    • pull 型なので Back queue がリクエストする
  • この選択は優先度でバイアスがかけられたラウンドロビンで行うことができる
    • 他のもっと sophisticated な方法を使っても良い
    • ランダマイズしてもよい

Back queue

  • Back queue はクローリングしているあいだは休まないようにする
    • Back queue の数 B で調整（すべてのスレッドがビジーになるように）
    • Mercator の推奨設定：クローラスレッド数の3倍
  • それぞれの Back queue は1つのホストからの URL のみを含む
    • ホスト名から Back queue への対応（マッピング）はテーブルで管理

Back queue heap

  • Back queue heap は、1つの Back queue ごとに1つのエントリをもつ
  • エントリには、 Back queue に対応するホストが次に叩かれる最も速い時刻を保存
  • この時刻は、以下から決定される

Back queue の処理

  • クローラスレッドはクロールすべき URL を探す
  • Back queue heap のルートを取得
  • テーブルをひき、対応する Back queue q の先頭から URL をフェッチ
  • Back queue q が空になったかどうかチェックし、もし空なら Front queue から URL v を pull する
    • もし URL v のホストに対応する Back queue がすでにあったら、URL v をそれに append し、別の URL を Front queue から pull し、繰り返す
    • そうでなければ、 v を q に入れる
  • q が空でなければ、Back queue heap にそのための新しいエントリを作成する

講義資料

参考資料

Information Retrieval and Web Search まとめ(21): リンク解析

前回はランク学習手法について説明した。今回は、リンク解析について扱う。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の21日目の記事です。

adventar.org

リンク解析の概要

ハイパーテキストとリンク

  • 文書のコンテンツ以外のものもスコアリングに取り入れる
  • リンクは権威 (authority) をページに与えることを意味するのか？ランキングに役立てることはできるか？
    • CERN のホームページからリンクされたページは高エネルギー物理に関するページ？
  • 応用範囲
    • Web
    • Email
    • SNS

リンク解析と情報検索

  • スコアリングとランキング
  • リンクベースでのクラスタリング
    • トピックによる文書分類
  • リンクを分類の特徴量として使う
    • 同じ文書を指している文書たちは同じようなテーマである可能性が高い
  • クローリング
    • 次回扱う

有向グラフとしての Web

  • Web はページ内にアンカー (anchor) をもつ
  • Web はページを頂点、ハイパーリンクを辺とする有向グラフとみなせる

f:id:takuya-a:20201222234147p:plain
Web のグラフ構造

  • 仮説1
  • 仮説2
    • ページAのハイパーリンクのアンカーテキストには、リンク先のページBの内容が書かれている

PageRank

引用解析

  • 論文などの学術文献の引用関係を解析
  • 同じ文献を引用している文献同士は関連している
  • PageRank の基礎となった

学術文献と Web との違い

  • Web は数百万の書き手がいて、それぞれが違う興味を持っている
  • スパムが多い
  • 検索エンジンがリンクをランキングに使い始めると、リンクスパムが増える
    • お互いにリンクを張り合うリンクファーム (link farm) も存在する

PageRank スコアの基本的な考え方

  • ユーザはページ間をランダムウォークすると仮定する
    • ランダムなページから開始
    • 各ステップで、ユーザはページから出ているリンクの中から等確率で1つ選んで遷移する
  • 長い時間のあと、各ページはある一定の訪問率 (vist rate) に落ち着く
    • これをそのページのスコアとする

f:id:takuya-a:20201222234252p:plain
(IIR p.464 Figure 21.1) ランダムウォークするユーザのページ遷移

テレポート

  • しかし、この方法には問題がある
    • dead-end （リンクを持たない Web ページ）がたくさんある
    • ランダムウォークを継続できない（スタック (stuck) する）
    • 訪問率が意味を持たなくなる
  • dead-end に行き当たったら、次はランダムなページに遷移する
    • スタックしなくなる
  • また、dead-end でないページでも、ある確率（たとえば 10%）の確率でランダムなページに遷移する
    • この確率は PageRank のパラメータであり、テレポート確率 (teleportation probability) と呼ぶ
    • Web のユーザがどこか他のページに行く挙動をシミュレートしている
  • すべてのページに訪問率が存在するようになる
    • この訪問率をどうやって計算するか？

マルコフ連鎖

  • マルコフ連鎖 (Markov chain) は n 個の状態 (state) と、 n×n の遷移確率行列 (transition probability matrix) P からなる
  • 各ステップで、状態のうちのどれか1つの中にいる
  • P_{ij} は、状態 i から状態 j へ遷移する確率を表す
    • P_{ii} > 0 も認められる
  • すべての i に対して
 \displaystyle\sum_{j=1}^{n} P_{ij} = 1

マルコフ連鎖の例

f:id:takuya-a:20201222234405p:plain
(IIR p.466 Figure 21.2) マルコフ連鎖の例


P = \left(
  \begin{array}{ccc}
    0 & 0.5 & 0.5 \\
    1 & 0   & 0   \\
    1 & 0   & 0
  \end{array}
\right)

エルゴード的マルコフ連鎖

  • エルゴード的マルコフ連鎖 (ergodic Markov chain) は、各状態での長期的な訪問率がユニーク（一意）である
    • エルゴード的：周期的なパターンがない
    • テレポートによりエルゴード性が満たされる
  • 長期的には、この訪問率に比例して各状態に遷移する
  • どこから開始するかには依存しない

確率ベクトル

  • 確率（行）ベクトル x = (x_1, ..., x_n) は、どの状態にいるかを示す
    • (0, 0, ..., 0, 1, 0, ..., 0) （i 番目の要素だけ 1）のとき、状態 i にいる
    • より一般には、確率ベクトル x = (x_1, ..., x_n) は、状態 i にいる確率 x_i を意味する
 \displaystyle\sum_{i=1}^n x_i = 1
  • このステップでの確率ベクトルが x = (x_1, ..., x_n) だったとき、次のステップはどうなるか？
  • 行列 P が、状態 i からの遷移確率を示していることを思い出すと、次の状態は xP と表せる
    • その次は xP^{2} 、更にその次は xP^{3}...
    • これは収束するか？
    • これを計算して調べるのがべき乗法 (power method, power iteration)
      • 初歩的な方法
      • 訪問頻度が一定の閾値以下に「落ち着く」までシミュレートを繰り返す
  • 確率行ベクトルの定常状態を a = (a_1, ..., a_n) と書くことにする
    • これは定常状態なので、 a = aP
  • この方程式を解くと a を求めることができる

Web グラフの例

f:id:takuya-a:20201223005928p:plain
6つのページ（状態）をもつ小さい Web のグラフと、その遷移確率行列

  • dead-end (sink) となるページ（状態 2）からは、ランダムなページに遷移するように修正する

f:id:takuya-a:20201223010257p:plain
dead-end を修正した遷移確率行列

  • テレポートの効果を入れる

f:id:takuya-a:20201223010043p:plain
テレポートによるランダムな遷移を追加した遷移確率行列

f:id:takuya-a:20201223010122p:plain
べき乗法で計算した確率ベクトル。収束していく様子が見える

HITS

講義資料

参考資料

Information Retrieval and Web Search まとめ(20): ランク学習

前回は Word2vec, BERT などの単語埋め込み手法と、それらの情報検索への応用について説明した。今回は、ランク学習について紹介する。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の20日目の記事です。

adventar.org

情報検索のための機械学習

  • これまでに検索における文書のランキング手法をいくつか見てきた
    • コサイン類似度、BM25...
  • また、教師ありの機械学習を使った文書分類（クラス分類）の方法も見てきた
    • ロッキオの方法、kNN、決定木...
  • 文書のランク付けにも機械学習を使えないか？
    • "machine-learned releance", "learning to rank" として知られている

歴史

  • 検索ランキングのための機械学習はアクティブに研究されてきた
  • 過去の研究
    • Wong, S.K. et al. 1988. Linear structure in information retrieval. SIGIR 1988.
    • Fuhr, N. 1992. Probabilistic methods in information retrieval. Computer Journal.
    • Gey, F. C. 1994. Inferring probability of relevance using the method of logistic regression. SIGIR 1994.
    • Herbrich, R. et al. 2000. Large Margin Rank Boundaries for Ordinal Regression. Advances in Large Margin Classifiers.
  • 初期の研究はそれほどうまくいっていなかった
    • 訓練データが少なかった
      • 特に実世界のデータ
      • クエリログ、適合性判定のデータを集めるのは大変
    • 機械学習手法もまだ発展していなかった
    • 情報検索の問題への適用が不十分だった
    • 特徴量が十分ではなかった

機械学習の必要性

  • 現代的な（Web の）システムは大量の特徴量を扱う
    • ターム頻度などの古典的な特徴量だけではなく、ページ中の画像の数、リンクの数、PageRank、URL、更新日時、ページの表示速度...
  • Google は 2008 年には 200 以上の特徴量（シグナル）を使っており、今日では 500 以上になっているだろう

ランク学習

  • クラス分類はアドホック検索への適切なアプローチではない
    • クラス分類 (classification)：順序がないクラスへのマッピングを行う
    • 回帰 (regression)：実数へのマッピングを行う
    • 順序付き回帰 (ordinal regression)、あるいはランキング (ranking)：順序付きのクラスへのマッピングを行う
  • ランキング問題では、文書が他の文書に対してよいかどうかを議論する
    • よさの絶対的な尺度は必要ない
  • ランク学習 (learning to rank)
    • 以下のような適合性のカテゴリの集合 C が存在すると仮定する
      • C のすべてのカテゴリ c_i には全順序がついている (totally ordered)
        • c_1 \gt c_2 \gt ... \gt c_J
      • （これは順序付き回帰の問題設定と同じ）
    • 以下のような文書とクエリのペア (d, q) からなる訓練データを仮定する
      • (d, q) は特徴量ベクトル x_i で表され、それに適合ランキング c_i がついている

検索ランキングのためのアルゴリズム

  • SVM (Vapnik 1995) のランキングへの適用：Ranking SVM (Joachims 2002)
  • ニューラルネット：RankNet (Burges et al. 2006)
  • Tree Ensemble
    • ランダムフォレスト (Breiman and Schapire 2001)
    • Boosted Decision Tree
      • Multiple Additive Regression Trees (Friedman, 1999)
      • Gradient-boosted decision trees: LambdaMART (Burges, 2010)
      • AltaVista, Yahoo!, Bing, Yandex などの検索エンジンで採用事例あり
    • 2010 年の Yahoo! Learning to Rank Challenge ではすべてのトップチームが Tree Ensemle の手法の組み合わせを使った

Yahoo! Learning to Rank Challenge

回帰木

  • 回帰木 (regression tree) は、実数を予測できる決定木
  • 葉ノードには、その葉ノードに含まれるすべてのサンプルの平均値 (mean) を保持する
    • \gamma_{k} = f(x_i) = \overline{x_i}
  • 分割規準：標準偏差 (standard deviation; SD) の最小化
    • 値の分散（標準偏差 SD）を最小化するように分割 A を選択する
    • 標準偏差、サンプル数、もしくは木の深さのいずれかが閾値を下回ったら分割を止める
  • 学習時には、分割する変数 x_1 と、その変数上での分割点 v_1 を探索する
    • それらは予測誤差 \displaystyle\sum_{i} \left( y_i - f(x_i) \right) ^2 を最小化するように選ぶ

f:id:takuya-a:20201222053301p:plain
回帰木の分割の例(1)。予測誤差を最小化する分割を選択

f:id:takuya-a:20201222053337p:plain
回帰木の分割の例(2)。予測誤差が0になるまで分割を進めた

勾配ブースティング

ブースティングのモチベーション

  • Q:「独立な弱い (weak) 分類器を組み合わせて、高い精度の分類器を構築できるか？」
  • 古典的なアプローチ: AdaBoost
  • すべての木の重み付きの投票で分類する

ブースティングによる関数の推定

  • ほしいもの：損失関数 L(y, F(x)) の期待値を最小化する、以下のような関数 F^*(x)
 F^*(x) = \text{argmin}_{F(x)} \mathbb{E}_{y,x} L(y, F(x))
  • ブースティングでは、 F^*(x) を以下のような形で近似する
    • h(x; a) は a = { a_1, a_2, ..., a_n } でパラメータ化された関数
    • \beta は重み係数
 F(x) = \displaystyle\sum_{m=1}^M \beta_m h(x; a_m)

勾配ブースティングの学習

  • 勾配ブースティング (gradient boosting) は、任意の微分可能な損失関数に対して関数 F(x) を推定できる
  • 関数 h(x; a) を最小二乗法でフィッティングする
 a_m = \text{argmin}_a \sum_i [ \tilde{y_{im}} - h(x_i, a) ]^2
  • ただし \tilde{y_{im}} は「疑似残差 (pseudo-residual)」であり
 \tilde{y_{im}} = - \left[ \dfrac{\partial L(y_i, F(x_i))}{\partial F(x_i)} \right]_{F(x) = F_{m-1}(x)}
  • 勾配ブースティングは、どんな損失関数であっても最小二乗法に単純化する

Gradient Boosted Regression Tree (GBRT)

  • Gradient Boosted Regression Tree (GBRT) は、この勾配ブースティングのアプローチを回帰木 (regression tree) に適用する
    • それぞれの回帰木は通常 1-8 の分割しか持たない
  • GBRT の学習
    • 最初に、すべての x_i に対して定数をとる、最もシンプルな予測器を学習する（[tex: F_0(x)）
      • 訓練データの誤差を最小化する定数
    • 木のルートノードの値 \gamma_{km} を探索する
    • 最小二乗法によりルートノードを分割する
    • さらに誤差を最小化する木を追加する

MART

f:id:takuya-a:20201222063819p:plain
MART の学習アルゴリズム

RankNet

  • RankNet [Burges et al. 2005] はニューラルネットによる ranker
  • モデルパラメータ w に対して微分可能な関数 f(x; w) をスコア関数とする
    • f(x_i; w) = s_i が x_i のスコア
  • クエリ q に対して、各文書の組 (d_i, d_j) に対するランキングのクラスの確率 P_{ij} を学習する
    • P_{ij} は、文書 d_i が d_j よりランキングが上である確率
    • \sigma はシグモイド関数の傾きを決めるパラメータ
 P_{ij} = P \left( d_i \succ d_j \right) = \dfrac{1}{1 + e^{-\sigma (s_i - s_j)}}
  • 損失関数 C はクロスエントロピー損失
    • P_{ij} はモデルの確率
    • \overline{P_ij} は実際の確率（各カテゴリに対して0/1で与えられる適合性の判定）
\begin{eqnarray}
C &=& - \overline{P_{ij}} \log P_{ij} - (1 - \overline{P_ij}) \log (1 - P_ij) \\
  &=& \frac{1}{2} (1 - S_{ij}) \sigma (s_i - s_j) + \log (1 + e^{-\sigma (s_i - s_j)})
\end{eqnarray}
  • ただし、 S_{ij} \in { 0, +1, -1 }
    • d_i が d_j よりも適合しているとき S_{ij} = 1
    • d_j が d_i よりも適合しているとき S_{ij} = -1
    • d_i と d_j が同じラベルのとき S_{ij} = 0

RankNet の Lambda

 \dfrac{\partial C}{\partial s_i} = \sigma \left( \dfrac{1}{2} (1 - S_{ij}) - \dfrac{1}{1 + e^{\sigma (s_i - s_j)}} \right) = - \dfrac{\partial C}{\partial s_j}
  • これを使って損失関数の w_k に対する微分は以下のようにできる
\begin{eqnarray}
\dfrac{\partial C}{\partial w_k} &=& \dfrac{\partial C}{\partial s_i} \dfrac{\partial s_i}{\partial w_k} + \dfrac{\partial C}{\partial s_j} \dfrac{\partial s_j}{\partial w_k} \\
&=& \sigma \left( \dfrac{1}{2} (1 - S_{ij}) - \dfrac{1}{1 + e^{\sigma (s_i - s_j)}} \right) \left( \dfrac{\partial s_i}{\partial w_k} - \dfrac{\partial s_j}{\partial w_k} \right) \\
&=& \lambda_{ij} \left( \dfrac{\partial s_i}{\partial w_k} - \dfrac{\partial s_j}{\partial w_k} \right)
\end{eqnarray}
  • この式を使って重み w_k を更新できる
  • \lambda_{ij} は、文書 d_i と d_j の組に対しての、変更したいスコアを表している
  • クエリ-文書ベクトル x_i の \lambda_{ij} と
    • \lambda_{ji} の総和 \lambda_i を定義する
 \lambda_i = \displaystyle\sum_{j:\{i,j\} \in I} \lambda_{ij} - \displaystyle\sum_{k:\{k,i\} \in I} \lambda_{ki}
  • この \lambda_i は、クエリ-文書ベクトル x_i のペアワイズ損失の勾配を表している
    • (a) は最適なランキング
    • (b) は 10 のペアワイズ誤差をもつランキング
    • (c) は 8 のペアワイズ誤差をもつ
    • 青の矢印は最後の文書の勾配 \lambda_i

f:id:takuya-a:20201222153814p:plain
ランキングの損失とそれらの λi の例(1)

  • 青の矢印でペアワイズ誤差は減り、2値の適合性評価指標は改善する
  • しかし、NDCG や ERR のような、上位により大きい重みをつける指標では、以下の赤の矢印のような勾配のほうが望ましい

f:id:takuya-a:20201222153851p:plain
ランキングの損失とそれらの λi の例(2)

LambdaRank

  • LambdaRank [Burges et al. 2006]
  • RankNet のようなペアワイズ誤差ではなく、NDCG の効果を入れる
  • アイデア： lambda を | \Delta Z| 倍する
    • |\Delta Z| は、文書 d_i と d_j を交換したときの差分
  • |\Delta Z| として |\Delta NDCG| （NDCG の変化）を使って \lambda を以下のようにする
 \lambda_{ij} = \dfrac{\partial C (s_i - s_j)}{\partial s_i} = \dfrac{- \sigma}{1 + e^{\sigma (s_i - s_j)}} |\Delta NDCG|
  • Burges et al. は、この変更によって NDCG に対して十分に最適化できることを示した

LambdaMART

  • LambdaRank は勾配をモデル化している
  • MART は勾配（勾配ブースティング）によって学習できる
  • この2つを組み合わせたのが LambdaMART [Burges 2010]
    • MART に LambdaRank の勾配を入れた

f:id:takuya-a:20201221041428p:plain
([Burges 2010] Algorithm: LambdaMART) LambdaMART のアルゴリズム

  • 前述の通り、Yahoo! Learning to Rank Challenge で LambdaMART （と他のモデルとの線形結合）を使ったチームが優勝 [Burges et al. 2011]
  • 結合されたモデルと、それぞれの単体でのスコアは以下の通り

f:id:takuya-a:20201222164100p:plain
([Burges et al. 2011 Table 2]) 使用されたモデルと単体でのスコア

  • 多くのモデルを組み合わせなくても十分に高い性能を示す

f:id:takuya-a:20201222164143p:plain
([Burges et al. 2011 Table 3]) モデルの組み合わせとそれぞれのスコア

  • 他のチームも僅差
    • ペアワイズの Logistic Rank もいい結果を残している

f:id:takuya-a:20201222164220p:plain
([Burges et al. 2011 Table 4]) Yahoo! Learning to Rank Challenge の最終スコア。1位のチームが LambdaMART

  • だが、決定木ベースの手法は検索エンジンの会社では必要不可欠になっているようだ

講義資料

参考資料

Information Retrieval and Web Search まとめ(19): 分散表現

前回は決定木によるテキスト分類について説明した。今回は、情報検索での分散表現の利用について解説する。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の19日目の記事です。

adventar.org

単語の表現

  • ユーザの検索意図をどうやって頑健にマッチするか？
    • クエリを（字面通りではなく）理解 (understand) したい
      • クエリが Dell notebook battery size だったとき、 Dell laptop battery capacity に言及している文書にマッチさせたい
      • クエリが Seattle motel だったとき、 Seattle hotel を含む文書にもマッチさせたい
    • キーワードベースの情報検索システムでは難しい
      • スペル訂正、ステミング、小文字への正規化 (case folding) 役立つときもあるが限定的
  • クエリ拡張 (query expansion)
    • 単語の類似度を使うことができる
      • 手で構築されたシソーラス（類語辞書）
      • 単語類似度の尺度
        • 大規模なコレクションから計算されたもの
        • Web などのクエリログから計算されたもの
  • 文書拡張 (document expansion)
    • Web ページにおけるアンカーテキスト (anchor text) でシノニムを解決できるかもしれない
      • Web ページによっては使えないこともあるし、ハイパーリンクのないコレクションでは不可能

検索ログによるクエリ拡張

  • 文脈のないクエリ拡張は失敗する
    • wet ground ~ wet earth なので、ground --> earth と拡張すると...
    • ground coffee（挽いたコーヒー豆） != earth coffee
  • 同じユーザの context-specific なクエリ書き換えのログから学習することはできる
    • Hinton word vector
    • Hinton word embedding
    • この文脈では vector ~ embedding

シソーラスの自動生成

  • 文書のコレクションを解析することでシソーラスを自動生成することができる
  • シンプルなものだと、タームの共起行列から計算する方法がある

f:id:takuya-a:20201220172432p:plain
自動生成されたシソーラスの例

タームの関係性の表現

  • 標準的な符号化方法だと、各タームはそれぞれ1つの次元に対応する
    • 異なるタームは関係がないものとして扱われる
    • たとえば、 hotel を 3 つ含む文書と、 motel を 1 つ含む文書があったとして、それらの文書ベクトルは直交するので内積をとっても 0 になってしまう
  • Query translation model [Berger and Lafferty (1999)]
    • 基本的な情報検索のスコアリングは q^{T} d
    • スコアリングを q^{T} W d と修正して、W のパラメータを学習する
    • しかし、その行列 W が疎であるという問題は解決しない（W の次元は 10^{10} 以上）
  • 解決策：低次元密ベクトル
    • アイデア：固定長の低次元密ベクトルに、最も重要な情報を詰め込む
    • 通常、 25 - 1000 次元
    • 高次元の疎なカウントベクトルから、低次元の「単語埋め込み (word embedding)」へと変換する
  • 古典的な方法：潜在意味インデキシング/潜在意味解析 (latent semantic indexing/analysis)
    • 特異値分解 (singular value decomposition; SVD) を使う
    • 1990 年代では一般的だった
    • 情報検索システムでは効率的な実装は難しい（密行列なので）

ニューラル埋め込み

  • 単語を密ベクトルで表現する
    • そのベクトルは、その文脈で登場する他の単語を予測できるようなものが選ばれる
    • 他の単語もベクトルで表現されている
 banking = \left(
  \begin{array}{c}
    0.286 \\
    0.792 \\
    -0.177 \\
    -0.107 \\
    0.109 \\
    -0.542 \\
    0.349 \\
    0.271
  \end{array}
\right)

ニューラルネットワークと単語埋め込み

基本的なアイデア

  • 中央の単語 (center word) w_t から、周辺の単語 (context word) を予測するモデルを定義する
    • p(context \mid w_t)
  • この上に損失関数を定義し、大規模なコーパスからモデルを学習する
    • t の位置をずらしながら学習していく
    • この損失関数を最小化するような単語のベクトル表現が学習される

低次元の単語ベクトルの学習

  • 逆伝搬誤差 (back-propagating error) によってベクトル表現を学習 [Rumelhart et al., 1986]
    • 古い方法
  • ニューラル確率言語モデル [Bengio et al., 2003]
  • NLP from Scratch [Collobert & Weston, 2008]
  • Word2vec（よりシンプルで速いモデル） [Mikolov et al. 2013]
    • バイリニア (bilinear) で速い
  • GloVe（matrix factorization と接続） [Pennington, Socher, and Manning 2014]
    • バイリニア (bilinear) で速い
  • ELMo、ULMfit、BERT（トークンごとのベクトル表現、Deep contextual word representation）
    • 現在の stage of the art

Word2vec

  • Word2vec は、ある単語 (center word) とその周辺の単語 (context words) を予測するモデル
  • 2つのアルゴリズムがある
    • Skip-gram (SG)
      • （ポジションに対して独立な）ターゲットの単語から周辺の単語を予測する
    • Continuous Bag of Words (CBOW)
      • bag-of-words の文脈から、ターゲットの単語を予測する
  • 訓練方法
    • 階層的ソフトマックス (hierarchical softmax)
    • ネガティブサンプリング
    • ナイーブソフトマックス (naive softmax)

Skip-gram

  • Skip-gram で P(w_{t+j} \mid w_t) を計算する例
    • banking が center word w_t
    • ウィンドウサイズは 2

f:id:takuya-a:20201220164632p:plain
Skip-gram の例

  • 2つのパラメータ行列
    • W_{in} は center word の埋め込みとなる（行が単語を表す）
    • W_{out} は context word の埋め込みとなる（列が単語を表す）

f:id:takuya-a:20201220164713p:plain
Word2vec が学習する2つのパラメータ行列

Word2vec の線形性

  • Word2vec による単語のベクトル表現は、類似度と類似度の次元を、とてもうまくエンコードする

構文的な関係性

 x_{apple} - x_{apples} \approx x_{car} - x_{cars} \approx x_{family} - x_{families}

意味的な関係性 [Semeval 2012 task 2]

 x_{shirt} - x_{clothing} \approx x_{chair} - x_{furniture}
 x_{king} - x_{man} \approx x_{queen} - x_{woman}

情報検索への応用

ニューラルネットによるリランキング

Dual Embedding Space Model (DESM)

f:id:takuya-a:20201220164836p:plain
([Mitra et al. 2016] Figure 2) 1つの context word を考慮した Word2vec (CBOW) モデルのアーキテクチャ。W_IN と W_OUT は訓練によって学習される重み行列で、それぞれ IN と OUT の単語埋め込み空間に対応する

f:id:takuya-a:20201220164953p:plain
([Nalisnick et al. 2016] Figure 1) "Albuquerque"（アメリカの都市）を含む文書。緑の単語は "Albuquerque" との IN-OUT 類似度スコアが閾値より高かったもの。(a) は Albuquerque に関する文書で、 (b) はその都市についてただ言及しただけの記事

f:id:takuya-a:20201220165040p:plain
([Nalisnick et al. 2016] Table 1) "yale", "seahawks", "eminem" に対する、コサイン類似度で最近傍の単語

BERT

  • BERT: Devlin, Chang, Lee, Toutanova (2018)
  • Transformer ベースの DNN
  • トークンごとの表現を（コンテキストありで）出力する
  • クエリや文書の表現も同様に作れる
    • もしくはクエリと文書を同時に埋め込み、適合スコアを求める
  • 非常に効果的

f:id:takuya-a:20201220165115p:plain
([Devlin et al. 2018] Figure 3 (left)) BERT の事前学習モデルのアーキテクチャ

講義資料

参考資料