リスト 2. 12 URL の適合度を NaiveBayes 分類器で評価する
2.7 得られた結果は欲しい結果？ 精度と再現率
図
2.12
分散ファイルシステムを用いたHadoop
のMapReduce
実装ウェアプラットフォームを提供する。
Hadoop
は、独自の分散ファイルシステムHDFS
を用いてMapReduce
（Dean
、Ghemawat
の論文を参照[10]
）を実装する。MapReduce
はアプリケーショ ンを多くの小さな処理単位に分割する。HDFS
は信頼性確保のためにデータブロックのコピーを 複数生成し、計算クラスタ中の計算ノードに配置する（図2.12
）。MapReduce
は、データが存在 する場所でデータを処理する。Hadoop
は2,000
ノードのクラスタで動くことが実証され、現在は
10,000
ノードのクラスタで動くことを目標にしている*5。実世界の本番システムでは、大規模データセットを扱う能力が非常に重要となる。我々は、起 こりうる問題について注意を促し、それに対処するための適切なプロジェクトや文献を紹介し た。読者が検索エンジンを設計するとき、スケールする能力と大量のデータを扱う能力のみなら ず、検索結果の品質についても考える必要がある。結局のところ、ユーザは正確な結果が速く出 てくることを望んでいるのだ。そこで、得られた結果が望むものであるかどうかを定量的に測る 方法を、いくつか見てみよう。
2.7 得られた結果は欲しい結果？ 精度と再現率
Yahoo!
は、検索エンジンの品質のために膨大な時間を費やしている。ソフトウェアシステムの品質保証プロセスと同様に、検索エンジンの成功のためには検索品質も極めて重 要だ。検索エンジンにクエリを投げたとき、欲しい結果が得られるかもしれないし、得られな いかもしれない。検索エンジン向けの品質評価指標はたくさんあるが、最もよく使われる精度
（
precision
）と再現率（recall
）が、実装も、品質に対する理解も簡単だ。図
2.13
は典型的なクエリから得られうる結果を示している。ドキュメントの集合があって、*5訳注：原書が発行された2009年時点での話。米Yahoo!が2011年2月に発表したところによると、2011年初頭 時点のHadoop MapReduceフレームワークは1クラスタあたり4,000ノードでスケーラビリティの限界を迎える。
そのうち部分集合の片方がクエリに対して適切なドキュメントであり、もう片方の部分集合が検 索されたドキュメントである。適切なドキュメントを全て検索することが目標であることは明ら かだが、そうなることはめったにない。そこで我々の関心は、図
2.13
のようにこれら2
つの部 分集合の積集合に向く。Retrieved Relevant
All documents
図
2.13
この図は、適切なドキュ メントと検索されたドキュメント を表している。検索の精度と再現 率はこれらの積集合によって定義 される。情報検索では、取得した適合ドキュメントの数（
RR
） を、取得した全ドキュメントの数（Rd
）で割ったものを 精度（precision
）という—
精度= RR / Rd
。図2.13
に おける精度は、目分量でおよそ1 / 5(0.2)
である。正確 ではないが、我々は実務者なのだから。一方、再現率（
recall
）は取得した適合ドキュメントの数（RR
）を、す べての適合ドキュメントの数（Rt
）で割ったものだ—
再現率= RR / Rt
。これら
2
つの指標は、質的に異なる質問に答えてくれ る。精度は「得られたもののうち、欲しかったものはど の程度か？」で、再現率は「得られたもので、欲しかっ たものはすべてか？」という意味である。再現率よりも 精度のほうが得やすいのは明らかだ。なぜかといえば、再現率を求めるには、与えられたクエリに適合するすべ
てのドキュメントをあらかじめ知っている必要があるからだ。現実にはそんなことはまずない。
どの程度の割合で良い結果と悪い結果が混ざっているのか評価するために、この
2
つの指標を算 出する。もし得られた検索結果が正しければ、そう、完全に正しく、一点の曇りもなければ、ク エリに対する精度と再現率は両方とも1
に近づく。図
2.14
検索エンジンの典型的な 精度と再現率のプロットアルゴリズムを評価して検索エンジンをチューニング するときは、ユーザが検索しようとする代表的なクエリ 群に対してこれら
2
つの値をグラフにプロットすべき だ。この2
つの値の典型的なプロットを図2.14
に示す。クエリごとに、そのクエリの精度と再現率に対応する点 をプロットした。たくさんのクエリを実行して点を打て ば、図
2.14
のような線が得られるだろう。クエリの数 が少ないときに値を補完するのは、よい考えではないか もしれない。点は点として残して、線でつながないほう がよいだろう。我々は高い精度と高い再現率を追い求めるのだから、
グラフの右上の角に置かれた点が良い精度
-
再現率を表2.8
まとめ65
すことになる。このグラフを用いると、目的に応じたアルゴリズムの調整や、ある手法と別の 手法との優劣の比較が客観的に可能となる。疑いのまなざしを向ける上層部に対して、本書に 載せたアルゴリズムを使うように説得することもできるだろう。この章で説明した3
つの手法（
Lucene
による検索、Lucene
とPageRank
、Lucene
とPageRank
とユーザクリック）で実践する こともできる。我々が提供したデータセット、あるいは読者が自分で作ったデータセットに適用 して、10
から20
クエリの結果を精度-
再現率グラフにプロットすることもできる。5.5
節では、ある特定のアルゴリズムを評価するための多くの信頼性の視点について、また2
つのアルゴリズムの比較の方法について議論する。さらに、得られた結果に対してより信頼をお けるようにするため、検証実験が欠かせないということを述べる。検索結果の品質を考える上で は、精度と再現率は氷山の一角である。本書で扱う基本的なインテリジェントアルゴリズムをす べて説明し終えてから、より詳細な信頼性解析について説明する。この手法によって、インテリ ジェンスの品質を汎用フレームワークを用いて評価できるようになる。2.8 まとめ
2000
年初頭に、ネット上の多くのニュース記事が「検索こそ支配者だ！（Search is king!
）」と 声高に言っていた。前世期、この種の意見は洞察にあふれるものであったろうし、予言的にも見 えただろう。しかし今、これは全世界で受け入れられている。本当かって？ ググってみたら いい。この章では、地球上に散らばるコンテンツ中心の物事に対するユーザのクエリにインテリ ジェントに答えるには、インデックス化を超える注意と努力が必要なことを示してきた。まず、
Lucene
ライブラリが提供する従来型の情報検索技術の利用から始めるという検索戦略を示した。ウェブからのコンテンツ収集（ウェブクローリング）について述べ、クローラを独自に実装した。
NekoHTML
やtext-mining
ライブラリのような様々なドキュメントパーサを用い、得られたコンテンツを
Lucene
アナライザに渡した。標準のLucene
アナライザは強力かつ柔軟で、多くの目的に適合する。読者の目的に合わないときのために、いくつかの拡張の可能性と変更について議 論した。さらに
Lucene
クエリフレームワークは強力であり、拡張性と柔軟性を持つということ を述べた。それ以上に重要なのが、本章で詳細に述べた、最も成功したリンク解析アルゴリズム
PageRank
である。本章では外部のライブラリに一切依存しない完全な実装を提供し、スパース行列の大規 模実装に強いG(Google)
行列の構築を採用した。さらにこの処理を発展させて完全なものとす るための手がかりを与え、読者自身で大きなことを成し遂げられるようにした。このアルゴリズ ムが持つ数多くの複雑さに触れ、テレポーテーション成分やべき冪乗法などの、中心となる性質を説 明した。さらにユーザクリック解析では、本書に載せた
NaiveBayes
分類器実装などのインテリジェントな確率技法を説明した。ここでは、重要な処理すべてを公開したラッパークラスを導入した が、内部のコードも詳しく見た。この種の技術によって、あるサイトや話題に対してのユーザの 嗜好を学習できるようになる。これはさらに大きく強化、拡張して機能追加することもできる。
すべてに合うような万能の解決策はない。この章では、
DocRank
と名付けたアルゴリズムを 採用することで、読者がウェブページ以外のドキュメントを扱う際にも役立つようにした。この アルゴリズムはある程度有用であるが、より重要な点は、水面下にあるPageRank
の数学理論を 拡張して注意深く変更を加えることで、他の場面でも利用可能だと示したことにある。最後に、大規模ネットワークを扱う際に起こる問題と、検索結果を数値評価するためのシンプルで堅固な 方法と、検索エンジンの信頼性を増す方法について述べた。
「検索こそが支配者だ」という言葉は真実であろう。しかしレコメンデーションエンジンもま た、支配者たりえる。サジェスチョンとレコメンデーションの実現方法について、次の第