infosearch

06: クエリとインタフェース

情報検索の課題

ユーザが入力したキーワード/クエリはユーザが持つ情報要求に比べると貧弱
- ユーザがインタフェースを介して行う入出力や，ユーザの利用状況（文脈）が重要

クエリの質を向上させる技術

クエリ拡張
クエリ推薦
ランキングの質を向上させる適合性フィードバック

クエリ拡張

クエリの関連語の照合をシソーラスを用いて行うことで検索効果を向上させる手法
自動クエリ拡張
半自動クエリ拡張法
- ユーザが拡張する単語を選択

シソーラス利用

クエリ拡張に特に有用
- クエリの語を検索に好まれる語(統制語彙など)でもって置換/追加する
- シソーラスから同義語やより専門的な語を加えてクエリを拡張

共起語の利用

単語の共起語（一緒に出現する単語）に基づく拡張
- すべての文書集合
- 大規模なクエリの集合
- 3.検索結果の上位ランクの文書

共起語の相関係数

ダイス係数
- 2つの単語の類似度を測る
- {2･n(a ∧ b) / (n(a)+n(b))}
- n(w)はwの出現する文書頻度
- 1に近ければ共起, 0に近ければ独立
相互情報量
- log{P(a,b)/P(a)･P(b)}
- logN ･ (n(ab)/n(a)･n(b))
- 低頻度語に有効
期待相互情報量
- P(a, b)･log(P(a, b)/P(a)P(b))
- 相互情報量にP(a,b)をかけたもの
- 頻度の高い単語の組を重視
ピアソンのカイ二乗(Χ^2)
- C=2単語が独立に出現した場合の共起頻度
- Χ^2=(2単語の共起頻度 - C)^2/C

共起語の相関係数に基づくクエリ拡張

個々の単語の関連語は，クエリtropical fishの拡張に有効でない
- 熱帯魚でなく熱帯雨林やトロピカルフルーツ等関係の無い文脈で拡張してしまう
クエリ（単語の組）tropical fishとの関連語をダイス係数で推定
- いい感じに関連してそうな関連語を判定できそう
すべてのクエリについて相関係数を計算するのは組合せが多すぎて計算不可
- クエリログがいいかんじ

クエリログ

クエリとクリックしたページの記録データ
- tropical fish->[stores, pictures, live, sale, types, clipart, blue, freshwater, aquarium, supplies]
あるページをクリックした際のクエリを持っておき、そのクエリ群に類似したクエリにもページを推薦

適合性フィードバック

検索結果から人力で適合文書と不適合文書を判定
- 大変なので擬似適合性フィードバックでユーザの入力を必要としない判定も
  - 検索上位文書を適合文書とみなす
その判定結果からシステムがクエリ修正して検索結果を再ランク付け
クリックした文書に似た文書を集めるのに応用されている
問題点として:
- 最初のクエリの検索上位文書が不適合文書ばかりの場合クエリ拡張に失敗する…

地域情報の利用

地域情報を利用して検索結果のランクを修正
- クエリ内(履歴も含む)の地理情報
  - 筑波大->つくば市, 茨城, 関東, 日本など
- APのIPアドレス
  - whoisからサーバ所在地はだいたいわかる
テキスト中の地域情報メタデータや，出現する地域情報名と照合
包含関係や，距離といった尺度でクエリとテキストの類似度を計算

モバイル環境におけるアプリ利用

携帯デバイスにおけるクエリは長くなりがち
- Baeza-Yates et al., WWW 2007
携帯デバイスの入力の不便さからクエリ補完機能(サジェスト)がよく使われる
- Kamvar et al, WWW 2009
検索ログ履歴で補完
- real->real estate
インストールされた（最近開いた）アプリで補完
- real->real madrid
- Zhang et al., WWW 2016

クエリ生成時のステミング(語幹よせによる正規化)

ステミング処理の決定は索引付け時でなくクエリ生成時に行う
- 柔軟性や効果の向上
クエリを単語の異表記グループで拡張しステミングはしない
- ステミングを適用すると同じステムになるグループ(ステムのクラス)

ステムのクラス

ステミングを適用すると同じステムになるグループ
単語の異表記グループ
- ステムのクラスは，そのままでは大きすぎて不正確
- 単語の共起関係の分析により修正
  - 文書内で共起しやすいという仮定に基づく

ステムのクラスの修正アルゴリズム

ステムのクラス中のすべての単語のペアについて，ある窓幅内での共起数を数える
- W=50~100
それぞれのペアについて共起尺度を計算
- ダイス係数2･n(a ∧ b)/(n(a)|n(b)), n(x)は単語xを含む窓(または文書)の数
単語を表現する頂点間で共起尺度が閾値Tを超える辺を持つグラフを形成
- 2頂点間にパス（連結辺）があれば，単語クラスタを形成
結合されたグループを見つけて，新しいステムのクラスとする
- 大幅にクラスは縮む

スペルチェック

クエリ処理における重要な処理
- Webのクエリの10-15% はスペルミス
辞書に含まれない単語を対象として修正したい
修正候補を辞書中の単語との類似度を比較して提示
よく使われる類似尺度: 編集距離(levenshtein distanceなど)
- AからBにかきかえるための{挿入, 削除, 置換, 入替}回数

(defun ld(a b)
  (cond
    ((= (length a) 0)(length a))
    ((= (length b) 0)(length b))
    ((char= (char a 0)(char b 0))
      (ld (subseq a 1)(subseq b 1)))
    (t (1+ (min
      (ld a (subseq b 1))
      (ld (subseq a 1) b)
      (ld (subseq a 1) (subseq b 1)))))))
(ld "heool wrodl" "hello world") ;=> 5

高速化するには単語に特定の制約を与える
- 同一文字で始まる単語
- 同じまたは類似した長さを持つ単語
- 類似した音韻を持つ単語
単語をグループ化するための音韻コードを使う
- Soundex
  - 英語の発音の類似性を評価する4文字コード

Soundex

#!/usr/bin/sed -rf
s/^./\U\0/
s/[aeiouyhw]/-/g
s/[aeiouyhw]/-/g;s/[bfpv]/1/g;s/[cgjkqsxz]/2/g;y/dt/33/;y/l/4/;y/mn/55/;y/r/6/
s/([1-6])\1+/\1/g
s/-//g
s/^[A-Z][1-6]$/&00/;s/^[A-Z][1-6]{2}$/&0/;s/^([A-Z][1-6]{3})[1-6]+$/\1/

スペル修正のための問題点

ランキングの正確さ
- 検索処理中に「…が正しいスペル..？」といった提示を行うためには正確なランキングが必要
文脈
- 文脈に応じて多くの候補から正しい候補を推薦
  - lawers->[lowers, lawyers, layers, lasers, lagers]
  - trial lawers->trial lawyers
複数の単語の走り書きによる誤り
- mainscourcebank
  - スペースが欠けている
  - 複数語を対象としたスペース一文字の編集距離を考える必要が出てくる
  - 最近の論文(Li et al., SIGIR2012)では，確率モデルとして，統一的に扱っている

雑音のある通信路モデルでのスペルチェック

雑音のある通信路モデル

noisy channel model
文字が乱されている単語から意図した単語を推測したい
ユーザが単語wを選択する
- 「選択はコーパス中の確率分布P(w)に基づく」という言語モデル
単語wを書く際雑音のある通信路により単語eを誤って書いてしまった場合を考える
- 「誤った選択は確率P(e|w)に基づく」という誤りモデル
スペル誤りの頻度についての情報を表現できる
- P(w|e)を求め、高いwを修正候補としたい
- ベイズ規則によって推定できる
  - P(e|w)は何かしらで求められるものとする
  - P(w|e) = P(e|w)P(w)
  - 言語モデル確率P(w)の推定は:
    - 文脈による推定だとλP(w) + (1-λ)P(w|直前の単語w(p))
    - コーパスやクエリログによる推定が可能
  - 誤りモデル確率P(e|w)は:
    - 同じ編集距離を持つすべての単語の組は同じ確率を持つものとし，編集距離1と2のものだけを対象
    - 典型的な誤り（aとeは間違えやすいなど）に基づき推定
      - 間違いクエリログなどのデータを用いる

情報要求

ユーザがサーチエンジンに入力したクエリの背景にある要因
- いくつかの基準で分類
  - 何を探したい？
    - 旅行プラン？ニュース？事典？レビュー？
  - 検索対象
    - 判例？ブログ？学術論文？Twitter?
  - 検索する適合文書数
    - 多く見つかる？少しだけ見つかれば良い？

クエリと情報要求

同一クエリ
- 異なる情報要求を表現
  - 筑波大->筑波大学の沿革？アクセス方法？
- きちんと検索するには情報要求に応じた異なる検索技術とランキングアルゴリズムが必要
  - むずかしい
クエリ
- 情報要求の表現としては貧弱
- ユーザ自身が上手く情報要求を表現できないこともある
- ユーザは短いクエリを入れがち
  - 長いと上手くヒットしないという常識

ユーザとサーチエンジンとのインタラクション

クエリの形成，修正
検索結果のブラウジング

ASK仮説

Belkin ら(1982)
- Anomalous State of Knowledge
- 情報要求で必要とされる情報は知識のギャップ（空白部分）であるため，人々は正確に表現することが難しい
- ギャップを埋めるために情報探索を行うのだ

キーワードによるクエリ表現

60s~70sごろ: クエリは，専門家である検索仲介者により表現
クエリのうまい表現を学ぶことで検索性能が向上

スニペットの生成

検索ページの概要をクエリに応じて自動要約し表示したい
- 重要な文をスニペットとして選択する
- メタデータから: meta name="description"のcontent属性
- Webディレクトリのルートから: https://example.com/index.html
- Wikipediaから

スニペット生成のガイドライン

クエリ中の単語をすべてスニペットに含むことで単語間の関係がわかるようにする
クエリ中の単語がページタイトルに現れている場合は，スニペット中で繰り返す必要なし
クエリ中の単語は強調（ハイライト）処理#:~:text=<text>
スニペットは，キーワードの集合よりも，読めるテキストであったほうが良い
- 辞書の意味説明のような感じの文だと好ましい

広告推薦

検索結果と一緒に（スポンサーサーチ）
ウェブページをブラウズしているときに
Adデータベースから広告を探索しランク付け
- クエリとテキストの類似性
- 広告費
- 広告の人気(クリック数)
広告中テキストは文字が少ないのでクエリ拡張が有効な手段！

擬似適合性フィードバック

広告テキストやクエリを利用してクエリを拡張
入力クエリに対し:
- 1)完全照合
- 2)ステミング
- 3)拡張したクエリの順で広告テキストを照合しランキング
探索履歴中の共起語を用いてクエリを修正

検索結果のクラスタリング

ブラウジングを楽にするため関連ページをグループでまとめ(クラスタリング)推薦したい
- 熱帯魚の{写真, 水槽, 飼育, ショップ,…}ページ
効率よくクラスタリングしたい
- スニペットでのクラスタリングが効率よい
- クエリの上位適合文書中でのクラスタリング
理解しやすい分類
- 一元的分類 vs. 多元分類（要素クラスが複数の性質を共有）

クラスタのラベル

単純: スニペット中の単語をラベルとして使う
複雑:
- フレーズをラベルとして使う
- ラベルの判定基準/アルゴリズムを追加する
  - フレーズがタイトルやスニペットに出現？
  - フレーズ長
  - フレーズの集合中での頻度

ファセット

階層化されたカテゴリに，関連した重要な性質を記述するもの
- 価格帯, お急ぎor通常, 新品or中古など
- 人手で定義するやり方はECサイトで採用されがち
  - Amazon.com や楽天などで用いられるカテゴリ階層と直交する価格や割引率

言語横断検索

ある言語でクエリを入力し，別の（複数の）言語の文書を検索
クエリの翻訳，検索文書の翻訳が必要
- 統計的機械翻訳

統計的機械翻訳

対訳コーパスを訓練データとして，翻訳をモデル化
人名や固有名は言語によって表記が揺れる
- 音韻規則などに着目した，通常と異なる翻訳ルールが必要
- Wikipediaの活用が有効