情報考学　Passion For The Future

無敵会議第10回　検索会議　満員御礼に感謝　報告第3弾

さて、第3部はヤフー、リスティング事業部の宮崎氏によるYahooSearchTechnology概要説明から始まりました。YSTとは何か、どのような仕組みで検索結果の表示順位が決まるのか、が話の中心でした。

Yahoo!は2004年5月31日まではGoogleのエンジンを使っていましたが、この日を境に独自開発したYSTに乗り換えました。当時の経緯はCNETで私がスクープ記事を対談形式で書いていますのでご参考まで。

・対談：日本における検索の未来 - データセクション 橋本大也 vs ヤフー 志立正嗣 - CNET Japan
http://japan.cnet.com/column/search/story/0,2000050605,20068928-2,00.htm

さて、なぜ宮崎氏に検索アルゴリズムをお話いただいたのかというと、今回の会議の発想テーマが、新しい検索アルゴリズムだったからです。問題は以下の通りでした。

「
理想の検索アルゴリズムを探せ！

アンカーテキストの活用やリンク分析により、検索エンジンの精度は飛躍的に高まりました。しかし、しかし、しかし!!!まだまだ情報を見つけるのが難しい状態です。
より便利な検索結果を出すためにどんな情報が使えるでしょうか。
その情報を使った理想の検索アルゴリズムを考えてみてください。

新アルゴリズムの概要：

いままで誰も目をつけなかった
（ 　　　　　　　 　　　　 　　　 ）の情報を活用することにより、
（　 　　　　　　　　　　　 ）が可能に！
名づけて（　　　　　　　　　　　　　　　　　　　　　　　　　）アルゴリズム。

以下にその検索アルゴリズムを具体的に図解してください：
」

さて、注目の受賞結果は？

「検索」をテーマに全員で会議する「無敵会議」第10弾〜検索をより便利に、これまで不可能だった検索を可能に〜
http://bb.watch.impress.co.jp/cda/news/7238.html

がうまくまとまっていたので、引用させていただきます。

「
参加者には問題用紙が配布され、それぞれが15分間で個人ごとのアイディアを回答。その後に6人程度のグループを作成し、20分間で議論した内容をグループごとに提出するといった流れで会議は進行した。個人アイディア、グループアイディアはそれぞれ2つが運営者側から賞として選出され、その内容紹介と合わせて賞品が贈られた。

　グループ賞には、関氏が紹介した「やってはいけない検索方法」を活用し、検索方法の採点や適切な検索方法の紹介によってユーザーの検索技術を教育する「関裕二養成アルゴリズム」、検索結果を見た時の汗や声、心拍数といった情報を利用して、多くの人を興奮させた情報のランク付けを行なう「テンション検索アルゴリズム」の2つが入賞。参加者の投票によって、「テンション検索アルゴリズム」が1位に選ばれた。

　個人賞では、日々のひとりごとを収集して悩み解決の糸口を探る「ひとりカウンセリングアルゴリズム」、検索した文章のパターンと既存の文章との類似性をファイル形式ではなく「解読型」「批判型」「推薦型」といった文書の形式で分類するアルゴリズムの2つが紹介。ヤフーの宮崎氏は「自ら検索しようとは思っていないひとりごとを、勝手に検索してしまうのは面白い。文書形式の分類はすぐにでも使いたいくらいのアイディア」との賛辞を贈った。
」

優秀者にはヤフーからお食事券などの豪華プレゼントが渡されました。そして最後にはなんと全員に豪華なヤフーグッズ満載の袋が渡され拍手喝さいになりました。中身は

・たつをの ChangeLog / 2004-10-27
http://nais.to/~yto/clog/2004-10-27.html#2004-10-27-6

に写真で紹介されています。すごすぎです。なお、このブログには検索会議の報告系ブログ一覧があってさらに詳細が楽しめます。

さて、ちょっと真面目に捕捉。

検索会議ではヤフーのアルゴリズムのみでしたが、私が知っている有名な検索アルゴリズムをいくつかここでリストにしてみますと以下のような感じです。今回は技術者会議ではなかったのでアイデアベースでユニークなアルゴリズム発想が主体ですが、技術者ばかりで本当の数学的アルゴリズムを発想してみる会もやってみたいですね。

■TF/IDF

全文検索エンジンのほぼすべてに使われている基本アルゴリズム。文書を特徴づけている言葉はどれか、その言葉の重みはどれくらいかを求める数式。検索対象とする文書全部におけるキーワードの発生頻度（ある単語数÷全単語数）と、個別文書における発生頻度の比率を計算することで、文書を特徴づけているキーワードとその重要度を求めることができる。極めてよく使われる一般語は低い値になり、特定のテーマのときに登場する専門語は高い値になる傾向がある。

■PageRank

Googleのアルゴリズムとして有名になった。今は他のエンジンも部分的にはこの考え方を採用している。リンクを人気の指標と考えPageRankという数値で人気ぶりを算出する。まず外部からリンクの数が多ければ高いPageRankを与える。リンクの質も重視し人気ページからリンクされたページのPageRankも高めになる。例えば、YAHOO!はたくさんのページからリンクされているからPageRankが高くなる。PageRankの高いYAHOO!からリンクされたページのPageRankも高く計算される。

・Google の秘密 - PageRank 徹底解説
http://www.kusastro.kyoto-u.ac.jp/~baba/wais/pagerank.html

■Subject-Specific Popularity

Teomaなどが採用している。PageRankの改良。検索キーワードのテーマを重視してPageRankの計算に重みを加算する。例えば検索キーワードが音楽関連であれば、音楽関連をテーマにしたサイト群を抽出し、そのサイト同士のリンク構造からPageRankを算出する。無関係なテーマのサイトからのリンクは重視しないということでもある。例えば2チャンネルからのひやかしリンクがいかに増えても重要とはみなされないのでノイズが低くなるといえそう。

■HITS(Hyperlink-Induced Topic Search)

YSTはこの系統に分類できる。PageRankの改良。PageRankではリンク構造しか見ていないため、人気サイトの出自を問わない。つまり、リンクの人気があれば価値が高いということになってしまう。リンクだけですべてを判断していいのかという問題がある。そこでHITSではオーソリティとハブという二つの考え方を導入する。オーソリティはたくさんのサイトからリンクされた信頼できるコンテンツである。ハブはたくさんのひとをナビゲートしているリンク集である。二つを異なるタイプとして計算することでより精度の高い結果が得られるという考え方。
。
TREC10 - HITS Algorithm
http://csgrad.cs.vt.edu/~lixu1/work/CS5604/hits.htm

■Block-level Link Analysis

MSNのアルゴリズムはこれに分類できる。ここまでのPageRank、Subject-Specific Popularity、HITSではページ単位で重要度を計算していた。この手法ではページの中の意味のあるブロック（パラグラフなど）を分割し、ブロック内のリンク同士の関係をPageRank的に計算する。リンクの前後の文章を分析してリンクの重要度を計算するので、ひとつのページに複数の記事がある場合にも、ノイズの少ないPageRank的計算が可能になる。

・Block-level Link Analysis
http://research.microsoft.com/research/pubs/view.aspx?tr_id=754

■Vision-based Page Segmentation Algorithm

MSが研究している。視覚的な情報を重視したアルゴリズム。人間ならページのどこがナビゲーションで、どこが広告で、どこが著作権表示のフッターかはすぐに理解できる。それらの中のリンクは普通はあまり大切ではない。この手法ではコンピュータがHTMLを解析することで、ブロックの視覚的意味を推察し、リンクの重み計算に利用する。

VIPS: a Vision-based Page Segmentation Algorithm
http://research.microsoft.com/research/pubs/view.aspx?tr_id=690

Posted by daiya at 2004年10月29日 23:59 | TrackBack