stop-the-world

takuya-a のブログ

情報検索とその周辺

これは、情報検索・検索エンジン Advent Calendar 2019 の 1 日目の記事です。

情報検索・検索エンジン Advent Calendar を作った経緯

という流れで @johtani さんから「つくってよ!」と言われて作ったのが、このアドベントカレンダーです。

そういうわけなので、このアドベントカレンダーには、これといったルールや、こういうテーマで書いてほしい、といった要望はありません。そもそも情報検索は非常に学際的な分野ですし。

ただ、なにかしらのガイドラインなりテーマの例はあったほうが参加しやすいだろうと考え、説明文は以下のようにしました。

検索 (IR) に関わることならなんでも OK!

情報検索・検索エンジンという名前のアドベントカレンダーですが、「検索に関わること」として、情報推薦や自然言語処理、地理検索、さらには画像検索まで含めています。

その意図を説明するためにも、情報検索を取り巻く現状について、ざっとまとめてみました。いちソフトウェアエンジニアの自分から見たものですので、偏りや見識不足があることをご容赦ください。

情報検索の概要と近年の動向

情報検索の原語は Information retrieval です(しばしば IR と略されます)。そのまま解釈すると、情報の取得・取り出し、情報を取ってくること、といった意味合いです。

古典的な情報検索のモデルでは、

  • ユーザはなんらかの情報ニーズ (information need) をもつ
  • 検索システムはあらかじめ静的に構築された文書集合を内部にもつ

という条件のもと、

  1. ユーザは、情報ニーズに従い、検索システムに対してクエリ (query) を入力する
  2. 検索システムは、内部に保持する文書集合から、ユーザの情報ニーズに適合すると思われる文書集合を計算し、 UI 上に検索結果ページ (SERP; search engine result page) として表示する

というユーザと検索システムとのインタラクションを対象にします*1。 たとえば、図書館の蔵書検索システムで、ある特定の書籍を検索する、といったシチュエーションです。

古典的な情報検索モデルでは、静的な文書集合のなかから、ユーザがもともと持っている固定的な「情報ニーズ」にマッチする文書を探すことに焦点が当てられていました。 しかし近年では、情報システムの高度化・複雑化に伴い、既存の情報検索モデルには当てはまらないアプリケーションが増えてきました。

みなさんが Google などの Web 検索エンジンで検索しているときのことを想像してみてください。 検索結果のリストを見たり、その中の Web ページにアクセスしたりする中で、なんらかの知識を得て、そのトピックをさらに深堀りしてみたり、関連する別のことを探してみたりする経験があると思います。 クエリを入力している最中にもクエリ補完の候補が表示したり、検索結果ページに別のクエリ候補を提示したりして、ユーザをサポートしてくれます。

また、多くのアプリケーションにおいて、検索システムに保存されている文書集合は静的ではなく、動的に増え続けるものになっています。 Web の登場などの背景から、世界全体の情報量は爆発的に増加しており、増え続ける大規模な文書集合から、適合する文書を効率的に検索する必要性が出てきました。

さらに、アプリケーションによって検索対象の種類も多様になり、テキスト情報だけではなく、いまや画像や音楽、動画までが検索の対象になりました。

情報検索分野の大家である Zobel は、近年の情報検索を取り巻く状況を鑑み、 "What We Talk About When We Talk About Information Retrieval" の中で、以下のように述べています。

Information retrieval is the study of techniques for supporting human cognition with documents, using material that is sourced from large document collections. (情報検索は、大規模な文書集合からなる材料を用いて、文書による人間の認識をサポートするための手法の研究である)

情報検索の関連分野・関連技術

以上のように、情報検索は高度化・複雑化する実アプリケーションにも追従しつつ、進化・発展してきました。

情報検索は非常に学際的な分野であり、とくに情報推薦や自然言語処理機械学習ユーザインタフェース、といった分野とは深い関係があります。 また、産業界 (industry) への応用という意味では、検索システム全体としての評価や運用も重要になってきます。

情報推薦(レコメンド)

ACM SIGIR は言わずとしれた情報検索のトップカンファレンスですが、今年の SIGIR推薦に関する論文が多く採択されていたことからも、情報推薦・レコメンドシステムが情報検索の分野からも重要な関心事になっていることがわかります。

推薦システム (recommender system) は、ユーザにとって価値があるものを特定するのを助けるためのシステムです。 具体的には、ユーザの行動や属性情報などから、様々なアイテム(本、音楽、動画、記事など)から、ユーザの好みそうなものをランク付けして提示するようなシステムです。

ユーザが積極的に検索要求・クエリをシステムに入力するか(情報検索)、システム側からユーザが好みそうなものを提示するか(情報推薦)、といった違いはありますが、ユーザの認識をサポートする、という意味では非常に近いモチベーションをもった分野だと思います。 実際、レコメンドシステムで要素技術として検索エンジンを使う例もありますし、その境界は年々曖昧になっているように感じます。

自然言語処理機械学習

自然言語処理機械学習も広大な分野ですが、以下に情報検索に関連するトピックを挙げておきます。

  • 文書とクエリの言語処理
    • 分かち書きトークナイズ) (tokenize)ストップワード (stop word) 除去、見出し語化 (lemmatization)語幹化 (stemming)類義語 (synonym) 展開など。索引付け(インデキシング)やクエリ処理で使う
  • 文書要約 (text summarization)
    • 検索結果 (SERP) に表示する文書のサマリに文書要約したテキストを使用するなど
  • 情報抽出 (information extraction)
    • 文書のなかに含まれる固有表現などを予め抽出し、クエリ時にそれらの属性でフィルタするなどの応用がある
  • 言語横断情報検索 (CLIR; cross lingual information retrieval)
    • クエリとは別の言語で検索してもヒットさせたい場面で使われる。機械翻訳が使われることも
  • ランク学習 (LTR; learning to rank)
    • ユーザの行動ログなどから、文書のランキングを最適化する。近年、ニューラル検索 (nerural information retrieval) が急速に発展している

画像検索・地理検索

スマートフォンの普及などの背景から、写真や動画をオンラインサービスに簡単に上げられるようになり、画像などを含むマルチモーダル検索 (multimodal information retrieval) の重要性も増してきています。 地理情報を考慮した検索も同様の理由ですっかり一般的になりました。

それ以外にも、検索システムとして見た場合、キーワード以外にも何らかの属性(文書の更新日時など)によってフィルタしたり、ソートしたりすることは非常に一般的です。

検索のためのアルゴリズム・データ構造

情報検索はこれまで、全文検索 (fulltext search) を中心に発展してきました。

全文検索エンジンの実装方式にはいくつかありますが、現状、最も利用されている検索エンジン転置インデックス (inverted index) 型のものでしょう(文字列検索アルゴリズムについては以前、文字列アルゴリズムの学び方という記事を書きました)。 このタイプの検索エンジンは非常に古典的でありながら、クエリ処理の手法などはいまだに発展しており、さらに効率的になっています。

一方で、数値をインデックスするためには B+-tree や LSM-tree が、多次元の数値(地理情報や IP アドレスなどのベクトルデータ)をインデックスするためには kd-tree などのデータ構造が利用されます。実際、 Apache Lucene では、 kd-tree の発展型である Bkd-tree による範囲検索を実装しています。地理検索では、これらのインデックスが役立ちます。

さらに、画像検索や、ニューラル検索などのベクトル表現を使った検索システムでは、さらに高次元のベクトルを検索する必要があり、上記のようなインデックスではパフォーマンス要件などを満たせないことがあります。この場合、近似近傍探索 (ANN; approximate nearest neighbor) と呼ばれる方法で、近似的な解を返すことで、高速にベクトルを検索することを可能にします(参考: Billion-scale similarity search with GPUs - Speaker Deck)。 画像検索では ANN を使った検索が一般的になってきています。

検索エンジンライブラリ・検索ミドルウェア

実応用で検索システムをつくるときには、現状、ElasticsearchApache Solr をベースに考えるケースが多いようです。

インデックスを保存するストレージとして安定しており、レプリケーションやスナップショット(バックアップ)といったミドルウェアとしての機能が一通り揃っています。 分散検索にも対応しており、大規模な文書集合にも対応できます。

テキストだけでなく数値や日時、ベクトルなど、さまざまなデータタイプに対してインデックスを張れ、それらを横断した柔軟なクエリを書けるため、非常に応用範囲が広いため、システム要件の変化に対しても柔軟です。

また、REST API を提供しており、メジャーな言語ではクライアントライブラリが提供されていて開発しやすいのも人気の理由でしょう。

検索システムの設計・構築・運用・評価

検索は、研究だけでなく、実務においても、まだ答えが出ていない問題がたくさん残っています。

日本語の検索においては、トークナイズ(分かち書き)が必要ですが、そのアプリケーションにとって最適なトークナイズとはなにか?というのは実は難しい問題です。

さらに、構築した検索システムの精度評価も非常に重要な問題です。 対象となるコーパス、アプリケーションによって適切な評価方法を選ばなければなりません。

また、高いパフォーマンスを発揮させつつ、安定して運用していくためには、設計段階からインフラの知識が要求されます。 最近はクラウド技術が急速に発達しており、それらを使いこなすことでシステムの運用負荷を下げていくのも重要な課題になってきています。

  • 検索システム全体のアーキテクチャ設計
  • 検索システムの運用
  • 検索精度のチューニング
    • 類義語(シノニム)辞書の構築・運用、トークナイザの選定・チューニング
  • 精度評価・精度を上げるための方法論・システム
    • オフライン評価方法、オンライン評価方法(A/B テストなど)

UI/UX

検索システム全体としての良し悪しを評価する際には、UI/UX の観点は欠かせません。 ユーザからみたとき、検索エンジンに直接クエリを叩くことはなく、必ずフロントエンドを通して検索システムを利用します。

すなわち、ユーザはフロントエンドで検索クエリを入力し、フロントエンドから検索結果を得ることになります。 この基本は音声検索であっても画像検索であっても変わりません。

おわりに

以上のように、ひとくちに検索といっても、様々な分野や技術が相互に絡んでいて、状況は単純ではないことがおわかりいただけたかと思います。 検索システムをつくる上でも、以上のようなトピックがあるということだけでも知っておくと、役に立つことがあるのではないでしょうか。

情報検索という分野は、ある意味で古典的と思われがちかもしれませんが、このように、検索は様々な分野と密接に関係しながら、学術界・産業界の両方面からともに、いまなお発展しています。

ここでは紹介しきれなかったトピックもまだまだたくさんあると思います。 すでにたくさんの多様なエントリーをこのアドベントカレンダーに登録していただいており、とても楽しみです。

情報検索・検索エンジン Advent Calendar 2019、明日は rejasupotaro さんです。よろしくお願いします!

参考文献

*1:検索結果が情報ニーズに適合しないような場合、ユーザは(ときには情報ニーズを変化させながら)クエリ修正 (query reformulation) し、検索行動を繰り返すことがあります。一般には、このような、ユーザと検索システムとの一連のインタラクションの系列(これを検索セッション (search session) と呼びます)を考慮するモデルもあります