Zenn
AppBrewPublicationへの投稿
📍

「情報検索 検索エンジンの実装と評価」Advent Calendar Day3「Tokens and Terms」

Pin（spinute）
2020/12/03に公開
#
検索
tech

これは何

https://adventar.org/calendars/4968

「情報検索 検索エンジンの実装と評価」Advent Calendarの3日目の記事です。
3章の「Tokens and Terms」[1]の内容をざっくり紹介[2]します。

あなた誰

株式会社 AppBrew という会社でエンジニアをしているものです📍 LIPS の検索周りを担当していた時期もありましたが、最近は検索に限らずソフトウェアエンジニア半分、開発チームのマネージャ半分くらいの仕事をやっています📌

https://twitter.com/spinute

情報検索関係で一番好きな言葉はこちらです。

検索エンジンの実力って、「エロじゃないけどエロと関連の強いキーワードで検索したときにどれだけエロくない結果を返せるか」に出ると思っています。
https://takeda25.hatenablog.jp/entry/20131107/1383837561

前振り

Day 2に出てきた、情報検索における重要なデータ構造である転置インデックスは、term を格納するデータ構造でした。

文書検索で扱うクエリ・文書はいずれも文字列[3]で、これらをどのように term の列に変換するのかについて2章では説明を省いていました。3章では、文字列である文書やクエリを term の列に変換する際の処理を、より詳しく説明しています。

英語の話題が一番手厚く説明されているのですが、ヨーロッパやアジアの言語にも軽く触れられています。日本の検索エンジニア的には日本語関係の説明が物足りなく感じたので、そのへん補いながら説明していきます。

なお、日本語で tokenization というと形態素解析を思い浮かべる方もいるかと思います。term と形態素（や単語）は、似ていることも多いのですが、形態素は言語学の概念で、今ここで考えているのは term という別の概念です。

良い term の作り方とは IR システムがいい感じに動くものです。単語や形態素は、意味を持つ文字列の単位であり、その結果良い term の作り方はしばしば単語や形態素に近いものになります。一方で、言語学的な正しさに拘る必要はないので、term はしばしば"汚い形"をしています。

3.1 英語の話

英語の term 列の作り方は（例えば日本語と比べて）比較的簡単です。例えば数字・アルファベットの並びを term とみなし、それ以外の文字をセパレータとみなせば、雑ながらそれなりの品質の term の列を得られます。

とはいえ自然言語を扱う上では当然、様々な例外的な用例が襲いかかってくるので、term の作り方に関する様々な工夫があります。この節ではそれらを紹介しています。

キモは正規化だと思います。正規化とは、特定の形式（正規形と呼ぶ）に文字列を変換する処理のことです。この際に、別の文字列が同じ正規形になることがあります（例：カバンとかばんを、ひらがな表記に統一）。

正規化によって：

  • 重要でない違いを同一視することで、同じ概念を表す別の文字列を同一視できます
  • 一方で、本当は違う概念を表す別の文字列を、同じ正規形に変換してしまうミスも起こりえます

このトレードオフをいい感じにする正規化処理の設計が主な課題です。

Punctuation

句読点や記号についての小節です。例えば以下のような用法の扱い方を考慮する（= 必要に応じて特別な処理をする）必要があります。

  • I'll, it's は縮約形である
  • o'clock は1単語である
  • Bill's は文脈によって扱いが違う[4]
  • ピリオド、アクロニム（I.B.M, U.S.等）、小数点、IP アドレス等に同じ文字 . を使う
  • C++, C# から記号を外すと C。ググるときに混同されるとエンジニア的にはつらい...
  • 日本語だと「、」とか「。」とか。基本外してよいことが多いが、たまにまずいことがある（例：「君の名は。」）

Capitalization

大文字と小文字の違いを区別したいこともあれば、区別したくないこともあります。

  • 例えば、ユーザが検索窓にクエリをぶちこむときには、大文字をわざわざ入力してくれないことが多いはずです
  • 一方、us と US、the と THE は区別したいことが多いハズ
  • 日本語だと、カタカナをひらがなに揃えるとか、漢数字を算用数字に揃えるとかに相当する処理でしょうか

このような場合に使える汎用テクとして、正規化処理を挟むインデックスと、正規化処理を挟まないインデックスを両方作っておくやり方が紹介されていました。[5]

Stemming

  • Stemming は言語学における lemmatization に似た処理です。これは単語を辞書の見出し語（lemma）に変換する手続きのことです
    • 日本語だと例えば MeCab が原形を出してくれるやつのこと。中身はよく知らないが、多分辞書に入っているものを出している（？）
  • ただ、stemming は IR のための手続きであり、変換後の term は英語辞典には載っていない文字列かもしれません
  • 一番有名な英語 stemmer は Porter Stemmer です
    • ルールの集まり（例：複数形を単数系にする。英語の教科書に載ってるやつ）で、ソースコードを見るとわかるけど、辞書的なものは載っていない
    • やりすぎちゃうこともある。例えば、orienteers も orienteering も（orienteer ならいいのに）orient に変換しちゃって、oriental と区別がつかなくなる
  • TREC での評価結果が載っています。英語において stemming の効果が比較的大きいようです

Stopping

  • 非機能語（the や of など、たくさん出てくるわりに情報が少ない term）を除く処理のこと
    • Web 文書だと http や www なども外すことがある
    • "To be, or not to be" 等、除くべきではないケースもある
    • 日本語だと品詞で切ったり単語リスト[6]作って切ったりするイメージ
  • ノイズが減って検索結果の質が改善することがあるだけでなく、インデックスの容量削減や検索速度の改善に効くこともあります
  • ただ、気軽に index から stop word を全部抜くのはオススメしないそうです
    • 主流の仕組みでは stop word の影響は少ない[7]し、フレーズ検索等ができなくなってしまうデメリットがあるため

3.2 文字について

  • 英語の文字はだいたい ASCII（7-bit で表現できる文字種）で済みます
    • というか、そのように設計された文字セット・ 文字コードが ASCII である（たぶん）
  • 歴史的には色々な文字がありましたが、今は Unicode がデファクトになりつつあります
  • Unicode では文字に対して番号 codepoint を割り当てるもので、それを計算機上でどう表現するかは定めていません
  • 計算機上での表現方法は、最近だと UTF-8 が主流と言ってよい気がします[8]
    • Rob Pike の Wikipedia に「ソフトウェア作家」と書いてあってカッコいい
    • UTF-8 は ASCII 互換なのが巧い（ASCII 文字列を UTF-8 文字列として解釈できる）
    • UTF-8 は可変長文字コードである（固定長の文字コードとは違い、バイト列の長さから文字列の長さを単純には決められない）
  • この本では Unicode や UTF-8 の説明をかなりサマっているので、詳しく知りたい人は別の文献にあたるのが良さそうです

3.3 N-gram

3.1 の話は言語依存性が強いもので、言語ごとに処理を設計する必要がありました。言語に依存性が低い term 列の作り方として、文字 N-gram があります。

N-gram 自体の説明は https://en.wikipedia.org/wiki/N-gram 読めばわかるので省略します。

  • 最適な N はケースバイケースです
  • N-gram は英語ではあまり良くないようです
    • subword が意味を持つ言語や、辞書とか tokenizer とかが潤沢でない言語だと有効なイメージ
  • term 数が増え、インデックスのサイズが大きくなるデメリットがあります
  • term に分けた後で n-gram にすることもあれば、term に分けずにそのまま n-gram にしちゃうテクもあります（英語では有効ではないらしい）
    • 日本語だと、例えば入力補完機能作るときにこのテクを使うことが多いハズ[9]

3.4 European languages

  • ヨーロッパの言語は IR 的には同じグループとして扱うことが多いそうです
  • 英語と似たテクが使えることが多いそうです
  • Snowball という多言語向けの stemmer があります
  • 対応する英字がある文字（ギリシャ文字とかウムラウト付いた文字とか）は、英字に正規化して割と上手くいくそうです。先述した正規化・非正規化インデックスをテクも使えます
  • 手法・言語の組み合わせごとの評価が本に載っていますが、ドイツ語やフィンランド語で n-gram 成績良いのがちょっと面白いです
    • ドイツ語もフィンランド語も長い単語が多く、subword が意味を持つことが多そうで、n-gram がそれを拾えている？

3.5 CJK languages

  • 簡潔に書かれています（日本語ユーザ的には日本語の話もっと読みたい...）
  • 大変
    • 文字が多くて大変（特に漢字）
    • 日本語と中国語は分かち書きされない[10]
    • 日本語では、Syllable に対応する文字を含む2つの文字集合と、中国語の文字の、合計3種類の文字集合をごちゃまぜに使うらしい。なにその言語メチャむずそう
    • 中国語には簡体字と繁体字、2つの字体がある
      • 両方読める人も多いが、片方で検索された場合に他方のドキュメントを返すのは不適切かもしれない
    • 漢字は表意文字である。実際は文字の構成要素である部首にまで意味ある気がするけど、部首を subword 的に暑かったりすることもあるんだろうか（知らない）
    • 中国語には2字熟語が多く、2-gram[11]がかなり効果的

まとめ

「情報検索 検索エンジンの実装と評価」Advent Calendarの3日目の記事でした。

3章は、数式もコードもほとんど出てこない、お話ベースの章でした📍

Buttcher 本 advent calendar 2020、明日は空いていますが、12/5 には Ryo Kato さんが5章を、12/10 には @po3rin さんが4章を書いてくださる予定です。

また空席やアサインが決まっていない章もあるため、興味を持っていただけた方はぜひご参加ください📍📍

脚注

  1. 実は「情報検索 検索エンジンの実装と評価」持っていません👶 学生の頃に講義で原著を読んだことがあり、専門用語の訳語選定等、翻訳書に沿っていないかもですがご容赦ください ↩︎

  2. 単に本の説明なぞるとただの劣化版になってしまうので、ラフにまとめつつ、本に書いていないこともわりと書きます。変なことが書いてるところは、本に書いてあるわけじゃなくて僕が書いてる可能性が高いです ↩︎

  3. 文字列でないケースを考えることもできるのですが、この本は文字列からなるクエリ・文書についての説明を扱った本です ↩︎

  4. 日本でいうと「クレアおばさんのシチュー」 ↩︎

  5. どう使うかは、具体的には書いていない。両方検索してスコアを混ぜたり、正規化すると形が変わるクエリ文字列では非正規化インデックスの優先度を上げたり、自由度はあってケースバイケースそう ↩︎

  6. 既存のものだと例えば http://svn.sourceforge.jp/svnroot/slothlib/CSharp/Version1/SlothLib/NLP/Filter/StopWord/word/Japanese.txt を使ったことがある。今ググってたら http://stopwords.quanteda.io/ も見つけた ↩︎

  7. たぶん tf-idf 的なものを想定している。この本の中盤で出てくるはず ↩︎

  8. UTF-16 とかも普通に使われてはいますが。検索文脈だと Elasticsearch の低レベルな機能触ってると出てくることがある。Java なので ↩︎

  9. 例えば最近 Elasticsearch の blog に書いてあった https://www.elastic.co/jp/blog/implementing-japanese-autocomplete-suggestions-in-elasticsearch ↩︎

  10. じゃあどうやって term にするんじゃいと思った人には形態素解析の理論と実装がおすすめです。使うだけでいい人は mecab とか kuromoji とか使えば良さそう ↩︎

  11. 読み方はバイグラムのはず。3-gram はトライグラムのはず。ニグラム、サングラムと読む人もみたことある。日本語むずぃ ↩︎

AppBrew
AppBrewPublication

国内最大級美容コスメプラットフォーム 「LIPS」を運営するAppBrewです。

Discussion