はじめに
こんにちは、最近分散システムに興味を持ち始めてきている、むっそです。
今回は 「検索システム ― 実務者のための開発改善ガイドブック」 の感想文を書いていこうかと思います。
ソフトウェアエンジニアとして働いていて、全文検索エンジンElasticsearchを使用している開発チームにいることが多いので全文検索などの検索システムについてちゃんと理解しておきたいという思いで、この本を購入いたしました。
良い本は今後もっと紹介していきたいですし、技術書が売れる→もっと良い技術書が増えるというサイクルを少しでも促せたら良いなと思ったので、この感想文を読むことで「この本、すぐほしい！」って思わせられたら幸いです。
ブログで感想文を書いたりするのは初めてですが、この本に最大級の敬意をもって感想文を書かせていただきたいと思います。
全体的な感想
この本を読んで、良い検索システムとは 1.検索における技術的な課題を解決していて 2.ユーザーが使いたくなるシステムであるということに気付かされました。(めちゃくちゃ普通の感想だが)
1.検索における技術的な課題を解決するためには、転置インデックスなどの検索を効率化するためのデータ構造とアルゴリズムの理解、検索に適したユーザーインターフェースの作成、検索システムプロジェクトを成功に導くチームマネジメント、検索クエリに応じたランキング作成などが重要になりますね。
2.ユーザーが使いたくなるシステムにするためには、検索意図があいまいなユーザーに対して検索クエリを提案してあげたり、検索を通じてユーザー自身の学習を促していくような使いやすさ、人間心理への理解、ユーザーからのフィードバックを反映した改善活動が重要となります。
「検索に関するユーザーエクスペリエンスを高める」 ためには人間の理解とシステムの理解を必要とするので、検索機能は総合格闘技だなぁと感じさせてくれます。
そしてなんといっても、図やグラフ、文章が分かりやすい！！
めちゃくちゃ内容チェックしたんだろうな感がある。そして明確な章立てと、参考論文に裏付けられた信頼性、知的好奇心を掻き立てるひと息コラムなど読むのが楽しくなる工夫が盛り込まれています。
どんなひとにオススメしたいか
- 全文検索エンジンの仕組みや推薦アルゴリズムを理解したいエンジニアやデータサイエンティスト
⇒図やグラフが非常にわかりやすいため、検索や推薦に携わるエンジニアにオススメ。数式が出てきても日本語で数式の意味を書いてくれたりしていて、優しさにあふれている。そして鬼のような参考文献(笑)
- 事業のマーケティングをうまくやりたい経営者やマーケター
⇒もはやどのサービスにおいても、検索機能や推薦機能というのは重要な位置づけになっていますね。twitterやNetflixなどの検索/推薦機能で満足度が上がっている人も多くいるでしょう。事業のマーケティングをうまくやりたい経営者やマーケターにも気づきをくれるかもしれません。
- バズる記事を書きたいライター、ユーザーフレンドリーなウェブページを作りたいデザイナー
⇒どういう検索意図を持ったユーザーに対して自分の記事を読んでほしいのか、そのためにはどんな記事を書けば良いのかという観点だったり、ユーザーが検索/推薦機能を効果的に使えるためのウェブデザインはどうあるべきなのかという観点で有用と思いました。
いろいろ書いたけれど、要は検索に携わる人に読んでほしい本です！
では読書感想文、たらたら書いていきます。参照したページ番号はP11(11ページ)など書いておきます。
第1章 イントロダクション
いきなり若手システムエンジニアのクラン君の全文検索エンジンに関する奮闘物語が始まります(P1)。この奮闘物語を読んだ読者は 「この本、対話形式で先生が生徒に教えるタイプの本じゃね？」 と錯覚するのですが、この物語は1章だけであります。今後、本の改訂版が出るのであれば物語の続編を書いてほしいですね。
これはお前が始めた物語だろ(唐突のエレン・クルーガー)
おもに第1章では、情報検索の歴史を紐解き、コンピューターが発達する以前は 図書館などの本をどうやって管理/分類していくのかということで目録法やらデューイ十進分類法などの話が出てきます(P11)。おおまかな歴史を表にまとめているのも良いです(P15)。
その学問の歴史を1章で書くというのは、構成としてはベタではありますがこの本に深みを生み出してくれるので非常に重要な章ですね。
第一部 検索エンジンの基礎
第2章 検索エンジンのしくみ
全文検索エンジンのしくみについて、転置インデックスのデータ登録(インデキシング)とデータ検索の仕組みについて書いてくれています。
実用的な転置インデックスはターム辞書(web, 検索、ランキングのような単語辞書) と ポスティング辞書(この単語はドキュメントIDの何文字目に含まれているかを指し示す辞書) に分けられている。
ターム辞書はハッシュテーブルベースの実装と、辞書順による実装があって、
- 転置インデックス構築時はハッシュテーブルベースの実装を利用して計算を高速化
- 検索時には接頭辞検索できるように辞書順による実装をしたリストを使う
と使い分けられることがある(P30)というところが特に面白い！と思いました。
P33には転置インデックスを利用した検索の図が書いてありますが、ここらへんで 「この本、めちゃくちゃグラフとか図を多用してくれてるやん、助かる～」 ということに気づくのです。
さらにこの章で気づくのですが、いくつか参考文献を引用しているので本の最後らへんに載っている参考文献を見に行くと、ものすごい量の参考文献です！参考文献の量は信頼の証です！
参考文献、こんなんなんぼあっても良いですからね(唐突のミルクボーイ)
第3章 テキスト解析
検索で使われるクエリやドキュメントを登録(インデキシング)するときに、テキスト解析が必要になるということが書かれています。
たとえば 「ウェブ検索エンジンの仕組み」という単語で検索をかけたときに、テキスト解析をして 「ウェブ」「検索」「エンジン」「の」「仕組み」 といった具合に認識できる単語で分けたり、日本語には活用があるので「検索し」ではなく「検索する」みたいな原型や終止形にしてあげたりする必要があるってやつですね。
ここらへんの前処理的な話は、自然言語処理らへんで良く出てくる話ですね。
また類義語の展開は検索クエリのテキスト解析でのみ実行したほうが良い(P51)という部分は、個人的に類義語検索をElasticsearchで実行するタスクを持ったことがあって、分かりみが深かったです。
概して、検索時に同義語フィルターを使用することのメリットは、インデックス時に同義語フィルターを使用することでわずかにパフォーマンスが向上することのメリットを上回ります。
第4章 ポスティングリストの走査とランキングのアルゴリズム
転置インデックスの構成要素である、ポスティングリストを走査していかに検索クエリに適したランキングをユーザーに出してあげれるか、という章になります。
ポスティングリストはメモリにのりきれないほど膨大になることが多く、少しずつ読み込む必要がある(P54)。またAND検索とOR検索では、AND検索のほうが各単語のポスティングリストの走査を最後までする必要がないため、OR検索より処理が速いことが一般的(P57) というところが図で示されていてものすっごくわかりやすかったです。
P58から検索クエリと登録しているドキュメントの類似度計算の話で、コサイン類似度や、TF-IDFによるランキングを考慮したポスティングリスト走査の説明が書かれています。
「あーこうやって検索エンジンはドキュメントに対してランキングをつけているのか」 というのが非常に直感的に書かれています。
P65から検索エンジンのパフォーマンスとスケーラビリティの話に入りますが、 「めちゃくちゃ重要な情報書いてあるし別章で作ってあげてもいいんじゃね！？」 と思ったくらいにパフォーマンスチューニングの面白い要素が書かれているので、パフォーマンスチューニングしたい人に読んでほしいですね。
たとえばOR検索のときにポスティングリストをすべて走査しなければならないという弱点を克服したMaxScoreというアルゴリズムの話が出てきます。Apache Luceneでのblock-max WAND有効/無効化時のパフォーマンス比較のコラム(P73)では、返却件数が10件の場合、block-max WAND有効のほうが4.5倍速くなっている という結果が書かれていて、ほぇー－っとなりました。(低語彙力)
第5章 検索エンジンへのデータ登録
ネット上などのいろんなデータソースからデータを持ってきて、処理して、データ登録することになりますが、そのときは色々気をつけてね！ってことが書かれています。
ここらへんのETL処理系の話はいかに不要な情報を抜くか、いかにインデックスへ登録するかという点が重要かと思いました。
個人的にためになる話は、P91のNOTEに書いてあった、 転置インデックスの利点を最大限活用するためには非正規化したデータを作成して転置インデックスに登録すべきってところです。
以下の英語の記事などでも書いてありますが、Elasticsearchはリレーショナルデータベースじゃありませんね(N回目)。 なのでElasticsearchでインデックスを登録するときにはリレーショナルデータベースのお作法をいったん忘れる必要があるわけですね。世の中、難しいです
第6章 検索インターフェースと検索クエリの処理
いままでの章とは変わって、検索するためのユーザーインターフェース設計やデザインの話が中心の章となっています。
ためになったのはP102のコラム 「インタラクションの原則」 の部分です。ユーザーが検索行為をするためにはアフォーダンス、シグニファイア、制約、対応付け、フィードバックという５つの心理学的な概念があるとのこと。
たしかになにかのウェブサイトの画面で検索したいなぁってときに、 テキストボックスと虫眼鏡マークがあれば「これ、検索できるやつー」 って無意識に認識しますよね。そこでの検索操作が直感的でなかったり、詳細検索がよくできてなかったりするとそのサービスに対するがっかり体験が生じてしまうわけですね。
また検索するにしても検索結果が0件とかだと激萎えなので、検索ボックスに文字を入力するごとに検索を実行してくれるインクリメンタルサーチ機能(P131)だったり、検索文字の一部を書いたときに候補をリストで表示してくれるオートコンプリート機能(P123)みたいなものが実装されていると、検索ユーザー体験としては良さそうですな。
第二部 より高度な検索システムにむけて
第7章 良い検索とは
どういうユーザーをターゲットとして、彼らにとって良い検索システムとはなんだろうか、という感じで視点を検索システムからユーザー/利害関係者(人間)へと転換している章となります。
この本ではユーザーの情報要求のレベルを4つに分けた指標を取り上げています。(P142)
1.自分がなにを探したいのか認識できていない
2.探したいものは認識しているが明確化したり言語化できない
3.探したいものが言語化できる
4.検索機能に検索クエリなどの検索条件を入力できる
この話は、要件定義あるあるで有名な 「顧客が本当に必要だったもの」 に近いですね。
検索システムの開発者やプロダクトマネージャーは 「検索意図が明確なユーザーが検索システムを使ってくれる」 と信じがちですが、実際のユーザーは 「レストランでメニューを選んでるくらいの軽いノリでほしいものを検索している」 みたいなことが起きがちです。(この微妙な意識の違いがユーザー離脱につながったりしたことがあります笑)
また、ほしい情報だけに絞って検索結果で見たいユーザー(適合率を高く評価)や、多少興味から外してても良いからほしい情報を取りこぼさずに全部見たいユーザー(再現率を高く評価)がいたりします。(P145)
どちらのタイプのユーザーも大事にできるのが理想ですが、一般的に適合率と再現率(偽陰性と偽陽性)はトレードオフだと言われてます。
たとえば病院のがん検査で本当にがんの人を見つけたい(再現率を高く評価)からとりあえず疑わしいひとには 「あなたは陽性です！再検査します！」 ってやると、偽陰性(本当はがんだが、検査では陰性の人)は低くなるが、偽陽性(本当はがんではないのに、検査では陽性の人)が増えてしまうやつですね。
検索システムでも適合率と再現率のうち、どれを評価するのかというのは考えておく必要がありそうですね。全然考えてない視点だったので、勉強になります...
第8章 検索システムプロジェクトの始め方
検索プロジェクトをはじめるときにどうやってマネジメントしていくかという章ですね。ちょっとアジャイル開発というよりかはウォーターフォール感強めな章でした。
個人的にためになった部分は、検索システムの運用の話です(P168)。
とくにインデクサの更新については、プロジェクトを進めていくにしたがって、 このインデックス変更したいなぁ っていう事象がやはり起きます。
運用していく中で学習すれば良いとは思いますが、不測の事態が起きるのはいやだと思うので、下記のようなインデックス更新手順などは準備しておくと良いかと思いました。
第9章 検索システムの評価と課題の発見
良い検索システムかどうかを評価する方法は大きく分けて、オフライン評価とオンライン評価の2つがあって、その評価指標と課題発見を説明している章となります。
オフライン評価では、検索クエリに関連するドキュメントが検索システムのロジックによってちゃんと検索結果の上位に提示されるかを評価する方法で、再現率や適合率、Cumulative Gainなどの評価指標があるらしい(P179)。
オンライン評価では、実際の検索システムをユーザーに利用してもらい、検索結果のクリックなどのユーザーの行動を調べることで、検索システムを評価する方法。リクエストあたりクリック数のユーザー平均だったり0件マッチ、再検索、離脱といった指標を調べることができる(P187)。
個人的に知れて良かったのは、インターリービングという手法です。
A/Bテストとは違って、インタリービングでは以前のアルゴリズムと改善後のアルゴリズムのランキングリストを混ぜることで新たなランキングを作成し、同一のユーザー群にそのランキングを提示し性能を評価します。同一のユーザー群で評価することで、極端な振る舞いをする少数のヘビーユーザーの行動に結果が左右されなくなるメリットがあるようです。
第10章 クエリ提案とドメイン理解の支援
この章では、検索システムというのは 検索者がクエリを投げて、そのクエリに応じた結果を返すだけのシステムではないんじゃね？ というところから始まります(P203)。
つまり検索者が検索システムと複数回対話を繰り返す過程で、ドメイン知識などを学習して、学習とともに検索クエリもまた改善されていくようなシステムが理想的ですよねっていうことです。考えてみれば、我々はもうGoogle大先生に育てられてここまでやってきたといっても過言ではないですもんね。
検索システムはラブい
検索システム フォーエヴァー
まぁ誰しも検索を活用する始まりは赤ちゃん同然なので、検索システムが赤ちゃん検索者を成長させていくためには、オートコンプリート機能(P209)やスペル修正(P210)、関連単語の提案(P212) といった機能を実装してあげることで、検索体験を学習させて成長へとつなげられます。
またGoogleなどの雑多なドメインが検索結果に登場する検索システムにおいては、不必要なドメインの検索結果を表示させないために、検索結果をドメインごとなどでクラスタリングする必要が出てきます。検索結果のクラスタリングの手法として、 クラスタ中心アプローチ(P229)や、クラスタラベル中心アプローチ(P231) などがあるらしいです。
正直1つのドメインの検索システムを開発することが多いので、雑多なドメインについて検索システムを提供しなければいけないとなったら、検索結果のクラスタリングなど含めて、めっちゃ大変やろなぁと遠い目をしながら思いました。
第11章 検索を成功させるための支援
検索者というのは時に突拍子もない検索クエリを投げたりします。そんなクエリに検索エンジンが敗北しないためには、下記のような検索戦略を立てる必要があるようです(P236)。
あらかじめ検索内容をカテゴリ化しておいて、入力されたごくわずかな1.検索クエリをカテゴリ分類して2.入力されたクエリから検索のパフォーマンスを予測して、ものすごくパフォーマンスが悪そうだったら3.検索クエリの書き換えなどにより積極介入したりすることで、どうにかして検索体験を成功へ導く。
1.検索クエリをカテゴリ分類する手法として、検索クエリqがカテゴリvに含まれるかどうかをClarity(q, v)を計算して検索クエリのカテゴリ分類をしたりできる(P242)らしい。
2.入力されたクエリから検索のパフォーマンスを予測する手法として、検索結果の上位には局所的にまとまった単語が出現していることを利用してClarityを計算したりできる(P248)らしい。
3.検索クエリの書き換えをする手法として、検索結果の適合率を高めるならばクエリセグメンテーション、クエリスコーピングが使える(P252)。再現率を高めるならばクエリ拡張とクエリ緩和が使える(P253)らしい。
これはただのたとえ話ですが、
検索者：Googleで「阪神」という検索ワードを入力
Google：うむ、検索者は野球の阪神タイガースの試合結果の情報が知りたいんやな！(エスパー)
Google：「阪神タイガース」って検索クエリに書き換えたろ！
みたいなことを裏でしてるんですかねぇ。エスパー並みに一を聞いて十を知ったうえで、お父さんのような優しさで検索クエリに書き換えてるんだとしたら、Googleエグいっすね。
正直この章はちょっと内容が難しいですが、すごく面白くて勉強になりました。
もっと詳しく知りたい方はこの本買ってください笑
第12章 検索結果のランキング
検索システムにおいて、ユーザーの関心が高いと考えられる結果を上位に提示する必要があります。この章では、検索結果のランキングをいかにチューニングしていくかという話がメインになります。
私が特に面白いと思ったのが、P289の機械学習によるランキングです。
MicrosoftのMSLR-WEB10Kのデータセットを用いたLightGBMを使ってLambdaMARTによるランキング学習の実行スクリプトが記載されています(P296)。
ちゃんとスクリプトも用意してくださって、機械学習によるランキング出力ができるのはうれしいですね。そして出来上がったモデルを検索エンジンに組み込む方法も書かれています(P298)。
Elasticsearchであれば下記のようなリンクを参照して組み込めそうです。また組み込む場合はちゃんとレイテンシを意識して組み合わせましょうという話もあります(P304)。
なんだかデータベースに機械学習を組み込んでいくの楽しそうと思って読んでおりました。
ワクワクをありがとうございます。
あとがき
ちょっと長い読書感想文になってしまいましたが、読んでいただきありがとうございます。
書き終わって思ったことは 「読書感想文記事、めちゃくちゃ大変でした」 ということですね。あんま的外れなことも書けないし、本を書いた人に失礼がないように...みたいなことを考えると時間が溶けますね。笑
今後も良い本があれば紹介していきたいと思います。
あとなんかQiitaのキャンペーンが開催されてるっぽいので、ノリで参加してみました。
(このキャンペーンがやってることも知らずに記事を書いていたので、ちょうどいいタイミングでした。)
皆さんもこの機会にぜひ記事を投稿してみてください。