2004 年、Microsoft Research と Microsoft の Web Search チームは、Web 検索結果の関連性を向上させるための共同作業を開始しました。 その後、数年にわたる持続的な取り組みにより、3 世代の Web 検索ランキング アルゴリズムを出荷し、Bing が今日使用しているブースト ツリー アンサンブルに至ります。 私たちは、これらのランキングアルゴリズムの最初のものをRankNetと呼んでいます。 このRankNetの論文は2005年にICML（International Conference on Machine Learning）で発表され、ICMLの「Test of Time」賞を受賞しました。これは、10年前の会議で発表された論文のうち、その間に最も学術的に大きな影響を与えたと判断された1編に毎年授与される賞で、今回の受賞はこの賞の受賞となります。 これは大変名誉なことであると同時に、この10年の歩みを振り返って評価する機会でもあります。 この記事では、この話をしたいと思います。
Web検索は、基本的にユーザーのクエリを受け取り、それに対するインデックスされたすべてのドキュメントの関連性を評価することで機能します。 すべての Web ページがインデックスにあるわけではありませんが、それでもインデックスには何千億もの文書があり、検索を高速にするために特別なデータ構造に格納されています。 このため、非常に効率的なフィルタリングとランキング処理が必要となる。 ここで紹介するランカーは、この高速な初期フィルタリング処理によって選ばれた、（まだ大きな）文書のサブセットに対して動作する。 基本的に、ランカーはある特定のクエリとドキュメントのマッチングの質を測定する数値のリストを受け取ることで動作します（例えば、クエリがドキュメントのタイトルに単語を含んでいるかどうかを表す2進数）。 そして、ランカーはこの数字のリストをひとつの関連性の指標にマッピングし、この指標を使って、そのクエリに対するすべての文書をランク付けします。 3681>
したがって、実行時に使用する場合、与えられたクエリに対して、ランカーは各クエリ/ドキュメント ペアの特徴ベクトルを取り、それをクエリに対するそのドキュメントの関連性を表す数値にマッピングします。 RankNet はフィードフォワードのニューラルネットワークモデルです。 このモデルを使用する前に、トレーニングセットと呼ばれるラベル付けされた大量のデータを使用して、そのパラメータを学習する必要があります。 トレーニングセットは多数のクエリとドキュメントのペアからなり、それぞれのペアに対して、人間の専門家がそのクエリに対するドキュメントの関連性の質を評価する数値が割り当てられる。 データのラベル付けには時間がかかり、人間の労力が必要とされるが、ラベル付けされたデータがあれば、ネットの学習は完全に自動化され、非常に高速に行える。 2004年にMicrosoft社がランカーの学習に用いたシステムは、The Flying Dutchmanと呼ばれるものであった。 その結果、The Flying Dutchmanが数日とクラスタを使って学習済みモデルを作成したのに対し、RankNetはたった1台のマシンを使って、わずか数時間でランキングモデルを作成することができたのです。 また RankNet は、以前使用されていたランカーよりも関連性が大幅に改善されました。ニューラルネットは非常に幅広いマッピングをモデル化できますが、以前のシステムは線形マッピングだけに限られていたからです。
スポットライト Webinar series
Microsoft research webinars
Microsoft 研究者による講義をライブ Q&A およびオンデマンド視聴で提供します。
ここまでは良かったのですが、もっと良い方法があったのではないでしょうか？ 答えはYesですが、その理由を知るためには、RankNetがどのように学習されるのかについて少し説明する必要があります。 学習セットの各クエリについて、そのクエリに対してランク付けされるドキュメントの各ペアについて、RankNetは2つの特徴ベクトルを見せられ、SGD（Stochastic Gradient Descent）という方法を使ってパラメータを少し調整し、2つの特徴に対する調整後の出力スコアが正しい方向へ動くようにします（つまり、より関連性の高いドキュメントに対するスコアを増加、低いものに対するスコアを減少させるのです。 しかし、これはRankNetが、非常に低い順位にある関連性の高い文書を引き上げ、また、スコアは高いが関連性の低い文書を下げるように努力することを意味します。 このようにリソースを使うことで、ユーザーに表示される上位数点のリンクだけには、必要以上に注意を払わないのです。 実は当時、私たちの評価指標はNDCGと呼ばれるスコアで、ユーザーに表示される上位数件の結果をより重視した上で、ランキング全体の品質を評価する1つの数値を与えていました。 そのため、NDCGはウェブ検索において、ペアワイズエラーよりも自然な評価指標と言えます。 SGDは連続空間の探索に帰着しますが、NDCGは基本的に離散的な尺度であり、少なくとも2つの文書がランク付けされたリストの位置を変えたときにのみ値が変化します。 モデルのスコアが十分に小さく変化してもNDCGは変化せず、SGDはスコアの小さな変化を探索することで機能するので、SGDを使用してNDCGを最適化する方法を見出すのは困難です。 そのコツは、ニューラルネットの学習手順全体が、コスト関数そのものではなく、コスト関数の勾配だけを必要としていることに気づくことでした。 この勾配は、ランク付けされたリストの各文書に付けられた小さな矢印と考えることができ、これらの文書がどの方向に移動して欲しいかを示しています。 LambdaRankは、RankNetの勾配を単純に取り、それを各文書のペアを交換したときのNDCGの変化でスケーリングして、うまく機能することが分かっていました。 この学習により、NDCGで測定した関連性が大幅に改善されたモデルが生成され、さらに、RankNetとLambdaRankの両方で、学習速度が向上するトリックが発見されました。 さらに、驚くべきことに、この方法は直感的で賢明ではあるものの、そのような保証はないにもかかわらず、学習手順が実際に NDCG を最適化するという経験的証拠（この論文も参照）を発見しました。 答えはまたしても「Yes」でした。 私たちは、非常に強力な多クラス分類器を作ることが知られているブーストツリー・アンサンブルと呼ばれるモデルのクラスを知っていました。 そこで、ランキング問題を、学習セットで特定された5つの関連性のレベルごとに1つのクラスを持つ多クラス分類問題として扱ったらどうなるか？ 私たちは、この方法がLambdaRank（特に序数型多クラス分類と呼ばれるもの）よりも良い結果をもたらすことを発見しました。 さらにブーストツリーは、ニューラルネットには不向きなカテゴリなどの離散的な特徴を簡単に扱えるという利点もあります。 この結果は、このクラスのモデルが我々のデータにより適しているためだと考えています。そこで、ブーストされた木モデルとラムダランクを組み合わせて、両者の長所を引き出すことはできないか、というのが自然な疑問でした。 ブーストツリーモデルの学習はSGDの一種とみなすことができるので、答えは「Yes」で、我々がLambdaMARTと呼ぶモデルの形で実現しました。 LambdaMARTには、ニューラルネットに比べ、木構造モデルの学習を大幅に高速化できるという利点もありました（O. Dekel氏によるこの研究は、まだ発表されていません）。 これにより、より大きなデータセットで学習することができ、ランキングの精度が再び向上しました。
私たちのランカーは、業界の他の人と比べてどうなのでしょうか？ 2010年、Yahoo! はLearning to Rank Challengeを開催し、その中の1トラックで、誰が最も優れたウェブ検索ランキングアルゴリズムを持っているかを見るために設計されました。 1,055チームがこのチャレンジに登録しました。 3681>
過去10年間を振り返って、おそらく最も顕著な技術的教訓は、学習速度の重要性です。 より速いトレーニングは、より多くの実験とより大きなデータセットの使用の両方を可能にします。 この2つの要因は、最終的には、使用される基本的なアルゴリズムよりも、後者が目下の課題に対して十分に表現力のあるモデルである限り、より重要であると私は考えています。 この経験から得たもうひとつの「人生の教訓」は、粘り強くあることの重要性、そして何よりも、製品グループ、Microsoft Research、学界の素晴らしい同僚と一緒に仕事ができることの重要性です。 それ以前は、1986年に入社したAT&T Bell Labsに勤務していました。 それ以前は、MITの理論物理学部の博士研究員であり、オックスフォード大学で物理学と数学の第一級優等学位を取得後、ブランダイス大学で物理学の博士号を取得し、同大学に入学した。 彼の関心は、大規模通信ネットワークのシステム工学（AT&Tは、いくつかの重要なネットワークのルーティングに彼のアルゴリズムを使っている）、手書き文字および機械活字認識のためのニューラルネットワーク（彼は、現在毎日数百万の小切手を読むのに使われているシステムに取り組んでおり、実際、彼の機械学習への長い下りは、90年代初頭に手書き数字を認識するニューラルネットの特に素晴らしいデモをきっかけに始まった）、に広がっていた。 サポートベクターマシン（幸運にも、SVMの共同開発者であるVladimir Vapnikと初期の頃に仕事をすることができ、一部の人々が好むチュートリアルを書いた）、オーディオフィンガープリント（彼の作品は現在XboxとWindows Media Playerで音楽の識別に使われている）、話者検証、情報検索、ランキング（彼のランキングアルゴリズムは現在Bingでウェブ検索に使われている）。 現在、クリスは、スケーラブルで実用的なテキストの機械理解への新しいアプローチを開発することに情熱を注いでいます。これは、確かに野心的ですが、我々が挑戦をやめない限り、まだ何かを教えてくれる可能性があります。 クリスは、2012年のNeural Information Processing Systemsのプログラム共同議長、NIPS 2013の一般共同議長を務めました。
コンピュータサイエンスの研究ニュースについては、ResearchNews.comを参照してください。