(57)【要約】【課題】順位付けの対象となる対象データを適切に順位付けすることのできる評価関数を推定する。推定した評価関数を用いて適切に順位付けを行う。【解決手段】順位が付けられた順位付きデータを入力して、対象データを順位付けするための基準となる評価関数を推定する。推定に際しては、順位付きデータの各順位についての上位／下位をカテゴリとして付与したカテゴリ付きデータを作成する。そして、カテゴリ付きデータから順位付けの基準となる評価関数を推定する。推定した評価関数（そのパラメータ）に基づいて対象データを順位付けする。【選択図】　　　図３
2004062737.tif 000002
【特許請求の範囲】
【請求項１】
順位付けの対象となる対象データを順位付けするために、順位が付けられた順位付きデータから、前記対象データを順位付けする際の基準となる評価関数を推定する評価関数推定方法であって、
前記順位付きデータを入力し、当該順位付きデータの各順位についての上位／下位をカテゴリとして付与したカテゴリ付きデータを作成し、このようにカテゴリを付与したカテゴリ付きデータから順位付けの基準となる評価関数を推定すること、
を特徴とする順位付けのための評価関数推定方法。
【請求項２】
前記順位についての上位／下位をカテゴリとして付与した前記カテゴリ付きデータに対して、前記評価関数の値が下位より上位の方が大きくなるように当該評価関数のパラメータを設定すること、
を特徴とする請求項１に記載の順位付けのための評価関数推定方法。
【請求項３】
次の式（２）〜（４）の条件を満たし、かつ式（１）の値を最小化するように前記評価関数のパラメータを設定すること、
を特徴とする請求項１又は請求項２に記載の順位付けのための評価関数推定方法。
【数１】
2004062737.tif 000004
【請求項４】
二次計画法であるＳＭＯを用いて前記パラメータを設定すること、を特徴とする請求項３に記載の順位付けのための評価関数推定方法。
【請求項５】
請求項１ないし請求項４のいずれか１項に記載の順位付けのための評価関数推定方法により推定された評価関数を用いて順位付けの対象となる対象データを順位付けする順位付け方法であって、
前記評価関数と前記対象データを入力し、当該評価関数と前記対象データから各対象データのスコアを計算し、このスコアの順に前記対象データに順位を付けること、
を特徴とする順位付け方法。
【請求項６】
順位が付けられた順位付きデータを入力する順位付きデータ入力手段と、
前記順位付きデータの順位についての上位／下位をカテゴリとして付与してカテゴリ付きデータを作成するカテゴリ付きデータ作成手段と、
前記カテゴリ付きデータから順位付けの対象となる対象データを順位付けするための評価関数を推定する評価関数推定手段と、
を備えることを特徴とする順位付けのための評価関数推定装置。
【請求項７】
前記評価関数推定手段は、前記順位についての上位／下位をカテゴリとして付与した前記カテゴリ付きデータに対して、前記評価関数の値が下位より上位の方が大きくなるように前記評価関数のパラメータを設定する構成を有すること、
を特徴とする請求項６に記載の順位付けのための評価関数推定装置。
【請求項８】
請求項１ないし請求項４のいずれか１項に記載の順位付けのための評価関数推定方法により推定された評価関数を用いて順位付けの対象となる対象データを順位付けする順位付け装置であって、
前記評価関数と前記対象データを入力するデータ入力手段と、
前記評価関数と前記対象データから前記各対象データのスコアを計算するスコア計算手段と、
前記スコアの順に前記対象データに順位を付ける手段と、
を備えることを特徴とする順位付け装置。
【請求項９】
順位付けの対象となる対象データを順位付けするために、順位が付けられた順位付きデータから、前記対象データを順位付けする際の基準となる評価関数を推定するため、コンピュータに、
前記順位付きデータを入力する順位付きデータ入力ステップ、
前記順位付きデータの順位についての上位／下位をカテゴリとして付与してカテゴリ付きデータを作成するカテゴリ付きデータ作成ステップ、
前記カテゴリ付きデータから順位付けの対象となる対象データを順位付けするための評価関数を推定する評価関数推定ステップ、
を実行させることを特徴とする順位付けのための評価関数推定プログラム。
【請求項１０】
前記評価関数推定ステップは、前記順位についての上位／下位をカテゴリとして付与した前記カテゴリ付きデータに対して、前記評価関数の値が下位より上位の方が大きくなるように当該評価関数のパラメータを設定すること、
を特徴とする請求項９に記載の順位付けのための評価関数推定プログラム。
【請求項１１】
請求項１ないし請求項４のいずれか１項に記載の順位付けのための評価関数推定方法により推定された評価関数を用いて順位付けの対象となる対象データを順位付けするため、コンピュータに、
前記評価関数と前記対象データを入力するデータ入力ステップ、
前記評価関数と前記対象データから各対象データのスコアを計算するスコア計算ステップ、
前記スコアの順に前記対象データに順位を付ける順位付けステップ、
を実行させることを特徴とする順位付けプログラム。
【請求項１２】
請求項９又は請求項１０に記載の順位付けのための評価関数推定プログラムを記憶したこと、を特徴とするプログラム記憶媒体。
【請求項１３】
請求項１１に記載の順位付けプログラムを記憶したこと、を特徴とするプログラム記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば情報検索システム等で、ユーザに提示する情報を自動的に順位付けする際に用いられる、順位付けのための評価関数推定方法、装置、プログラム及び記憶媒体、並びに、順位付け方法、装置、プログラム及び記憶媒体に関する。
【０００２】
【従来の技術】
コンピュータやインターネットの普及により、大量の情報の中から適切な情報を探しだす情報検索システムの重要性が増している。このようなシステムにおいては、探しだした情報も大量になるため、何らかの基準に基づいて情報を順位付けしてから提示することが多い。通常、この順位付けは、ある評価関数に基づいて各情報にスコアを付け、そのスコア順に並べて出力する、という形で行われることが多い。このような順位付けに用いられる評価関数としては、例えば、ユーザが入力した検索要求（キーワード）に一致する語の数をスコアとするもの等がある。
【０００３】
従来、情報検索システムにおけるこのような評価関数は、システム設計者の経験や直観に頼って設計されることがほとんどであった。しかし、近年、情報のサンプルに対し理想的な順位付けを行ったデータから、自動的に評価関数を推定する技術が幾つか提案されている。例えば、平尾勉、前田英作、松本祐治、「Ｓｕｐｐｏｒｔ　Ｖｅｃｔｏｒ　Ｍａｃｈｉｎｅによる重要文抽出」、情報処理学会、第６３回情報学基礎研究予稿集（２００１年７月）等がある。
【０００４】
ここで、今までに提案された評価関数の推定方法を説明する。
まず、サンプルとして与えられた順位付きデータを適当な順位を境に、それより上位のものと下位のものに分ける。次に、それぞれのサンプルを別々のカテゴリと見なし、上位のサンプルについては正の値、下位のサンプルについては負の値をとるような評価関数を推定する。この推定にあたっては、既存の２カテゴリの分類器（例えば、ニューラルネットワークやサポートベクトルマシン等）の推定方法を用いる。最後に、こうしてできた評価関数をそのままシステムの評価関数として用いる。
【０００５】
このように評価関数を自動的に推定する方法では、順位付きのサンプルさえ用意すれば、ユーザに適応した評価関数（評価関数のパラメータ）が自動的に設定（推定）される、という利点がある。
【０００６】
【発明が解決しようとする課題】
しかしながら、従来のこのような評価関数の推定方法には次のような問題点がある。まず、サンプルを２つのカテゴリに分けるためには、閾となる順位を予め決める必要がある。しかし、一般にどの順位を閾とすればよいかは、実際に推定された評価関数の精度を調べなければ決定することができない。そのため、最良の評価関数を探すためには、分類器の推定を繰り返す必要があり、例えばサポートベクトルマシン等のように一回一回の推定に時間がかかる分類器を用いる場合には、大きな問題となる。
【０００７】
次に、ある順位でカテゴリを分けると、その順位近辺に現われにくいデータに関しては、評価関数の推定精度が悪くなる傾向がある。これは、一般に分類器による評価関数の推定にあたっては、カテゴリの境界から遠いところでは評価関数の推定精度が低くなるためである。したがって、従来の評価関数の推定方法では、閾とした順位から離れた順位に関しては、評価関数に基づく順位付けがうまくいかないことが多い。
【０００８】
そこで、本発明の主たる目的は、順位付けの対象となる対象データを適切に順位付けすることのできる評価関数を推定することができる順位付けのための評価関数推定方法、装置、プログラム及び記憶媒体、並びに、推定した評価関数を用いて適切に順位付けを行うこができる、順位付け方法、装置、プログラム及び記憶媒体を提供すること等にある。
【０００９】
【課題を解決するための手段】
前記課題に鑑み、本発明者らは鋭意研究を行い、順位付きデータの各順位についての上位／下位をカテゴリとして付与してカテゴリ付きデータを作成し、このカテゴリ付きデータから順位付けの基準となる評価関数を推定し、この推定した評価関数を用いることで、順位付けの対象となる対象データを適切に順位付けできることを見出し、本発明を完成するに至った。
【００１０】
即ち、前記課題を解決した本発明（請求項１）は、順位付けの対象となる対象データを順位付けするために、順位が付けられた順位付きデータから、前記対象データを順位付けする際の基準となる評価関数を推定する順位付けのための評価関数推定方法であって、前記順位付きデータを入力し、当該順位付きデータの各順位についての上位／下位をカテゴリとして付与したカテゴリ付きデータを作成し、このようにカテゴリを付与したカテゴリ付きデータから順位付けの基準となる評価関数を推定することを特徴とする。
【００１１】
この構成においては、順位付きデータには順位が付けられており、この順位付きデータの各順位についての上位／下位をカテゴリとして付与する。カテゴリの付与は、例えば後述する実施形態のように、サンプル中の各順位付きデータについて、１位より上位／下位、２位より上位／下位、…、ｎ−１位より上位／下位（ｎは順位付きデータに現われる最も下位な順位）、を表すカテゴリラベル（ｙ［ｊ／ｉ，ｓ］）を付与することにより行われる。
【００１２】
また、順位付けのための評価関数推定方法は、後述する実施形態のように、順位についての上位／下位をカテゴリとして付与した前記カテゴリ付きデータに対して、評価関数の値が下位より上位の方が大きくなるように当該評価関数のパラメータを設定することが好ましい。また、後述する実施形態のように、式（１２）〜（１４）の条件を満たし、かつ式（１１）の値を最小化するように前記評価関数のパラメータを設定することが好ましい。なお、請求項での式（１）は実施形態での式（１１）に相当する。一方、式（２）と式（１２）、式（３）と式（１３）、式（４）と式（１４）は同じ式である。また、本発明は、後述する実施形態のように、二次計画法であるＳＭＯを用いて前記パラメータを設定することが好ましい。
【００１３】
また、前記課題を解決した本発明（請求項５）は、請求項１ないし請求項４のいずれか１項に記載の順位付けのための評価関数推定方法により推定された評価関数を用いて順位付けの対象となる対象データを順位付けする順位付け方法であって、前記評価関数と前記対象データを入力し、当該評価関数と前記対象データから各対象データのスコアを計算し、このスコアの順に前記対象データに順位を付けることを特徴とする。
【００１４】
この構成によれば、順位付けのための評価関数推定方法により推定された評価関数を活用して、順位付けの対象となる対象データを適切に順位付けすることができる。
【００１５】
また、前記課題を解決した本発明（請求項６）の順位付けのための評価関数推定装置は、順位が付けられた順位付きデータを入力する順位付きデータ入力手段と、前記順位付きデータの順位についての上位／下位をカテゴリとして付与してカテゴリ付きデータを作成するカテゴリ付きデータ作成手段と、前記カテゴリ付きデータから順位付けの対象となる対象データを順位付けするための評価関数を推定する評価関数推定手段とを備えることを特徴とする。
【００１６】
この構成においても、順位付きデータには順位が付けられており、この順位付きデータの各順位についての上位／下位をカテゴリとして付与する。カテゴリの付与は、例えば後述する実施形態のように、サンプル中の各順位付きデータについて、１位より上位／下位、２位より上位／下位、…、ｎ−１位より上位／下位（ｎは順位付きデータに現われる最も下位な順位）、を表すカテゴリラベル（ｙ［ｊ／ｉ，ｓ］）を付与することにより行われる。
【００１７】
また、順位付けのための評価関数推定装置は、後述する実施形態のように、前記評価関数推定手段が、前記順位についての上位／下位をカテゴリとして付与した前記カテゴリ付きデータに対して、前記評価関数の値が下位より上位の方が大きくなるように前記評価関数のパラメータを設定する構成を有することを特徴とする。
【００１８】
また、前記課題を解決した本発明（請求項８）は、請求項１ないし請求項４のいずれか１項に記載の順位付けのための評価関数推定方法により推定された評価関数を用いて順位付けの対象となる対象データを順位付けする順位付け装置であって、前記評価関数と前記対象データを入力するデータ入力手段と、前記評価関数と前記対象データから前記各対象データのスコアを計算するスコア計算手段と、前記スコアの順に前記対象データに順位を付ける手段と、を備えることを特徴とする。
【００１９】
この構成によれば、順位付けのための評価関数推定方法により推定された評価関数を活用して、順位付けの対象となる対象データを適切に順位付けすることができる。
【００２０】
また、前記課題を解決した本発明（請求項９〜請求項１３）は、順位付けのための評価関数推定プログラム、順位付けプログラム、及びこれらを記憶した記憶媒体であり、コンピュータにプログラムの各ステップを実行させて、順位付けのための評価関数を推定させたり、評価関数を用いて順位付けの対象となる対象データを順位付けさせたりする。
【００２１】
【発明の実施の形態】
以下、本発明の実施形態を、図面を参照して詳細に説明する。
本実施形態で参照する図１の、（ａ）は実施形態に係る順位付け装置を機能展開したブロック図であり、（ｂ）は（ａ）の順位付け装置のハードウェア構成を示すブロック図である。図２は、実施形態に係る順位付けのための評価関数推定方法及び順位付け方法を示すフローチャートである。
【００２２】
〔順位付け装置〕
図１（ａ）に示すように、順位付けのための評価関数推定方法及び順位付け方法を実行する順位付け装置Ａは、順位付きデータを読み込む順位付きデータ入力手段１１と、全ての順位についての上位／下位をカテゴリとして付与したカテゴリ付きデータを作成するカテゴリ付きデータ作成手段１２と、カテゴリ付きデータから評価関数のパラメータを推定する評価関数推定手段１３と、評価関数のパラメータを再利用できるように格納するパラメータ格納手段１４を有すると共に、順位付けの対象となる対象データを読み込む対象データ入力手段２１と、評価関数のパラメータと対象データから全ての対象データのスコアを計算するスコア計算手段２２と、スコア順に対象データを整列するデータ整列手段２３と、整列した対象データを順位付けして出力するデータ出力手段２４を有する。この順位付け装置Ａの各手段（各ブロック）は、プログラムモジュールとして構成されているが、各手段の詳細な機能については、後でフローチャート等を参照して明らかにする。
【００２３】
なお、図１（ｂ）に示すように、本実施形態の順位付け装置Ａは、主制御装置１、記憶装置２、通信制御装置３、入出力装置４がシステムバスに接続された構成を有している。このうち、主制御装置１は、ＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）、ＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）等を含んで構成され、対象データを順位付けするための評価関数（そのパラメータ）を推定する機能、推定した評価関数を用いて対象データを順位付けする機能、順位付け装置Ａを統括制御する機能等を有する。また、記憶装置２は、ハードディスク装置等を含んで構成され、評価関数のパラメータを格納する機能、各種プログラムやデータを記憶する機能等を有する。また、通信制御装置３は、例えばネットワークインタフェイスカード（ＮＩＣ；Ｎｅｔｗｏｒｋ　Ｉｎｔｅｒｆａｃｅ　Ｃａｒｄ）等を含んで構成され、所定の通信プロトコールによりネットワークを介した通信（データの入出力）を実現する機能等を有する。また、入出力装置４は、キーボード、マウス等が接続された構成を有している。
【００２４】
〔順位付け装置の処理フロー〕
上記構成からなる本実施形態の順位付け装置Ａの処理フローを、図１（ｂ）を参照しつつ図２のフローチャートに沿って説明する。なお、このフローチャートは、順位付きのサンプルから、予め閾となる順位を設定する必要がなく、かつ、全順位にわたって精度の劣化しない評価関数を推定する処理フローと、推定した評価関数に基づいて精度の良い順位付けを行う処理フローを含んで構成されている。
【００２５】
ちなみに、情報検索の一分野である情報フィルタリングでは、膨大な文書集合から取り出したサンプル文書（通常文書集合全体に比べると非常に少ない）に対して、ユーザが有用度順に別途順位付けした後に、その順位付けを参考にして文書集合全体の順位を付ける、ということが行われる。本実施形態は、この情報フィルタリングを念頭に置いたもので、順位付きデータはユーザが別途順位付けしたサンプル文書に相当し、対象データは文書集合に相当し、出力データは順位付けられた文書集合に相当する。
【００２６】
まず、順位付きデータ入力手段１１がサンプルとなる順位付きデータを読み込み（Ｓ１１；順位付きデータ入力ステップ）、カテゴリ付きデータ作成手段１２ヘ渡す。カテゴリ付きデータ作成手段１２では、順位付きデータの全ての順位についての上位／下位をカテゴリとして付与して（Ｓ１２；カテゴリ付きデータ作成ステップ）、評価関数推定手段１３ヘ渡す。評価関数推定手段１３では、カテゴリ付きデータから、各順位についての上位／下位の判別を一度に行うことができるような評価関数のパラメータを推定して（Ｓ１３評価関数推定ステップ）、パラメータ格納手段１４ヘ渡す。パラメータ格納手段１４では、評価関数のパラメータを再利用できるように格納する（Ｓ１４；パラメータ格納ステップ）。これにより、読み込んだ（入力した）順位付きデータから、評価関数のパラメータが推定され、再利用可能に記憶される。
【００２７】
なお、本実施形態では、「上位」というときには同位を含むが、「下位」を含まないものとする。
【００２８】
次に、対象データ入力手段２１が順位付けの対象となる対象データを読み込み（Ｓ２１；対象データ入力ステップ）、スコア計算手段２２ヘ渡す。スコア計算手段２２では、評価関数のパラメータをパラメータ格納手段１４から読み込み、それに基づいて各対象データのスコアを計算して（Ｓ２２；スコア計算ステップ）、対象データとともにデータ整列手段２３ヘ渡す。データ整列手段２３では、スコア順に対象データを整列して（Ｓ２３；データ整列ステップ）、その結果をデータ出力手段２４ヘ渡す。最後に、データ出力手段２４では、整列した対象データを出力する（Ｓ２４；データ出力ステップ）。
【００２９】
〔具体的動作〕
次に、本実施形態の具体的動作について、図３等を参照してより詳細に説明する。なお、以下の記載は、説明を容易にするため、図３のフローチャートに示すように、図２のフローチャートにおける全てのステップ（Ｓ１１〜Ｓ２４）を連続して動作する場合を述べる。
【００３０】
なお、図３は図２のフローチャートを直列に配置したフローチャートであり、図２と同じステップ番号が付してある。また、図４は順位付きデータの例を示す表であり、図５は対象データの例を示す表であり、図６は出力データの例を示す表である。また、図７はデータの理解を容易にするために、順位付きデータ（図４）と対象データ（図５）を平面にプロットしてグラフ化した図である。図８は、カテゴリ付きデータの例を示す表である。
【００３１】
ちなみに、図４〜図８において、χ［ｊ／ｉ］はサンプル文書としての順位付きデータである（ｉ＝イ，ロ，ハ、ｊ＝１位，２位，３位）。また、Ａ，Ｂ，Ｃは順位付けの対象となる文書集合としての対象データである。また、χ［ｊ／ｉ］の添字ｉは順位付きデータの組を区別するためのものであり、添字ｊは各組内での順位を表すためのものである。また、（０．９，０．８），（０．４，０．５）等のカッコ内の数字は、サンプル文書（順位付けデータ）や順位付けの対象となる文書（対象データ）の、検索要求（例えばキーワード）に一致する語の数に関連したスコアである。ちなみに、図４の順位付きデータの順位は、このスコアに基づいて予め決められている。また、図７では、χ［ｊ／イ］は○、χ［ｊ／ロ］は△、χ［ｊ／ハ］は×で表している。また、図７では、図４、図５のカッコ内の最初の数値が横軸に、カッコ内の後の数値が縦軸に割り振られる（後述する図１３、図１４も同じ）。
【００３２】
ところで、ユーザによる順位付けが複数回行われる場合もある。図４の順位付きデータは、例えば、文書集合の中から３文書を取り出して順位付けすることを、３回試行するというような場合に相当する。ちなみに、図４の添字ｉの、イの組は１位〜３位までのデータが一組をなしている。同様に本実施形態では、ロの組もハの組も、１位〜３位までのデータが一組をなしている。
【００３３】
以下、図３のフローチャートに沿って、図４に示す順位付きデータから評価関数（そのパラメータ）を推定し、図５に示す対象データについて順位付けを行い、図６に示す出力データを得る例について、具体的動作を説明する。なお、この具体的動作及び図２のフローチャートを参照して説明した処理フローは、特許請求の範囲の、「順位付けのための評価関数推定方法」、「順位付け方法」、「順位付けのための評価関数推定プログラム」、「順位付けプログラム」に相当するものである。
【００３４】
まず、評価関数を推定するために、順位付きデータ入力ステップ（Ｓ１１）では、順位付きデータ入力手段１１が、図４の順位付きデータを読み込み、カテゴリ付きデータ作成手段１２ヘ渡す。
【００３５】
カテゴリ付きデータ作成ステップ（Ｓ１２）では、カテゴリ付きデータ作成手段１２が、図４の順位付きデータについて、１位より上位（下位）、２位より上位（下位）を表すカテゴリラベルを付与してカテゴリ付きデータを作成する。つまり、順位付きデータの全ての順位についての上位／下位をカテゴリとして付与したカテゴリ付きデータを作成する。本実施形態では、カテゴリラベルをｙ［ｊ／ｉ，ｓ］で表し、順位付きデータχ［ｊ／ｉ］がｓ位より上位（同位）のとき「ｙ［ｊ／ｉ，ｓ］＝＋１」、下位のとき「ｙ［ｊ／ｉ，ｓ］＝−１」と決める（ｉ＝イ，ロ，ハ，ｊ＝１位，２位，３位，ｓ＝１，２）。
【００３６】
この決め方に従うと、ｙ［ｊ／ｉ，ｓ］は次のようになり（図８参照）、これらの結果は、評価関数推定手段１３ヘと渡される。
【００３７】
χ［１位／イ］は１位より上位なのでｙ［１位／イ，１］＝＋１、
χ［１位／イ］は２位より上位なのでｙ［１位／イ，２］＝＋１、
χ［２位／イ］は１位より下位なのでｙ［２位／イ，１］＝−１、
χ［２位／イ］は２位より上位なのでｙ［２位／イ，２］＝＋１、
χ［３位／ロ］は１位より下位なのでｙ［３位／イ，１］＝−１、
χ［３位／ロ］は２位より下位なのでｙ［３位／イ，２］＝−１
【００３８】
χ［１位／ロ］は１位より上位なのでｙ［１位／ロ，１］＝＋１、
χ［１位／ロ］は２位より上位なのでｙ［１位／ロ，２］＝＋１、
χ［２位／ロ］は１位より下位なのでｙ［２位／ロ，１］＝−１、
χ［２位／ロ］は２位より上位なのでｙ［２位／ロ，２］＝＋１、
χ［３位／ロ］は１位より下位なのでｙ［３位／ロ，１］＝−１、
χ［３位／ロ］は２位より下位なのでｙ［３位／ロ，２］＝−１
【００３９】
χ［１位／ハ］は１位より上位なのでｙ［１位／ハ，１］＝＋１、
χ［１位／ハ］は２位より上位なのでｙ［１位／ハ，２］＝＋１、
χ［２位／ハ］は１位より下位なのでｙ［２位／ハ，１］＝−１、
χ［２位／ハ］は２位より上位なのでｙ［２位／ハ，２］＝＋１、
χ［３位／ハ］は１位より下位なのでｙ［３位／ハ，１］＝−１、
χ［３位／ハ］は２位より下位なのでｙ［３位／ハ，２］＝−１
【００４０】
評価関数推定ステップ（Ｓ１３）では、評価関数推定手段１３が、図８のカテゴリラベルが付与された各データ、つまりカテゴリ付きデータに対して、評価関数ｆ（χ）の値が、１位より上位のデータの方が１位より下位のデータよりも大きく、かつ、２位より上位のデータの方が２位より下位のデータよりも大きくなるように、評価関数の種類及びパラメータを推定（設定）する。
【００４１】
ここで、評価関数の種類及びパラメータの推定（設定）法については様々なものが考えられるが、本実施形態では評価関数の種類として入力χの線形関数ｆ（χ）＝ｗ・χを予め採用し（ｗは二次元ベクトル）、そして、この予め採用した線形関数ｆ（χ）に対するパラメータの推定法として次の条件式（１２）〜（１４）を満たし、目的関数Ｒ（つまり次の式（１１））の値が最小となるパラメータｗ，ｂＳ，ξ［ｊ／ｉ，ｓ］を求める方法を採用する（但しｉ＝イ，ロ，ハ，ｊ＝１位，２位，３位，ｓ＝１，２）。
【００４２】
【数２】
2004062737.tif 000003
【００４３】
式（１２），（１３）のｂＳは、ｓ位の上位／下位を分ける閾値である。具体的には、ｂ１は１位の上位／下位を分ける閾値であり、ｂ２は２位の上位／下位を分ける閾値である。また、式（１２）は、ｙ［ｊ／ｉ，ｓ］＝＋１のとき、即ちχ［ｊ／ｉ］がｓ位より上位であるときに、評価関数の値ｆ（χ［ｊ／ｉ］）がｂＳより（１−ξ［ｊ／ｉ，ｓ］だけ余裕を持って）大きいことを要請する条件である。また、式（１３）は、ｙ［ｊ／ｉ，ｓ］＝−１のとき、即ちχ［ｉ／ｊ］がｓ位より下位であるときに、ｆ（χ［ｊ／ｉ］）がｂＳより（１−ξ［ｊ／ｉ，ｓ］だけ余裕を持って）小さいことを要請する条件である。
【００４４】
ちなみに本実施形態では、順位付きのサンプルデータは図４に示されるとおり３件であることから必要とする閾値はｂ１，ｂ２の２つであるが、仮に１０件の順位付きデータ（サンプル文書）を与える場合、閾値は、１位より上位／下位、２位より上位／下位、…９位より上位／下位に対応するｂ１〜ｂ９の９つが必要になる。なお、この閾値ｂＳを人間が設定する必要は特にない。
【００４５】
ここで、各式の意味を説明するために、仮に全てのξ［ｊ／ｉ，ｓ］を０とした式（１１）〜（１４）を満たすパラメータが見つかったとする。すると、式（１２）及び式（１３）から明らかなように、そのパラメータを用いることで、各ｓについて、ｓ位の上位のデータが下位よりもｆ（χ）の値で２以上大きくなる。このことより、そのようなｆ（χ）を用いれば、全てのχ［ｊ／ｉ］について各順位の上位／下位を正しく分類（判別）できることになるのが理解される。
【００４６】
ところで、一般的に、全てのξ［ｊ／ｉ，ｓ］を０とした最小化問題には解がないこともある。そこで、式（１２）及び式（１３）では、条件をξ［ｊ／ｉ，ｓ］だけ緩めることで、近似的に上位／下位を分類できる評価関数のパラメータを求めている。ただし、条件を緩める程度は出来るだけ小さい方が望ましいと考えられるので、目的関数Ｒ（つまり式（１１））にξ［ｊ／ｉ，ｓ］の和を含めて、ξ［ｊ／ｉ，ｓ］ができるだけ小さくなるような評価関数のパラメータを求めるようにしている。
【００４７】
また、式（１１）には、サンプルだけをよく分類する評価関数を推定しないように（いわゆる過学習を避けるために）、目的関数Ｒにパラメータｗの大きさを制限する項（１／２｜ｗ｜２）を含めている。なお、このような項が過学習を防ぐ効果を持つことについては、例えば、Ｖｌａｄｉｍｉｒ　Ｎ．　Ｖａｐｎｉｋ，　“Ｔｈｅ　Ｎａｔｕｒｅ　ｏｆ　Ｓｔａｔｉｓｔｉｃａｌ　Ｌｅａｒｎｉｎｇ　Ｔｈｅｏｒｙ，　Ｓｅｃｏｎｄ　Ｅｄｉｔｉｏｎ”，　Ｓｐｒｉｎｇｅｒ　１９９９　に記載されている。
【００４８】
なお、式（１２）〜（１４）を満たし、式（１１）を最少化するパラメータｗを求める問題は、二次計画法の一種であり様々な解法が知られている。本実施形態では、そのような解法の一つＳｅｑｕｅｎｔｉａｌ　Ｍｉｎｉｍａｌ　Ｏｐｔｉｍｉｚａｔｉｏｎ（ＳＭＯ）を用いて、上記最小化問題を解くこととする。ちなみに、ＳＭＯは式（１１）〜（１４）を双対問題と呼ばれる別の形式に変換した後、目的関数が小さくなる方向に２変数の組を徐々に変化させていくことで最小化を行う。ここで、このような最小化は、Ｂｅｒｎｈａｒｄ　Ｓｃｈｏｌｋｐｆ，　Ａｌｅｘａｎｄｅｒ　Ｊ　Ｓｍａｏｌａ　”Ｌｅａｒｎｉｎｇ　ｗｉｔｈ　Ｋｅｒｎｅｌｓ”　Ｔｈｅ　ＭＩＴ　Ｐｒｅｓｓ　２００２　の第１０章に詳しく記載されている。
【００４９】
本実施形態では、評価関数推定手段１３が、図８のカテゴリ付きデータを式（１１）〜（１４）にあてはめて、ＳＭＯで式（１１）が最小となるパラメータ（評価関数のパラメータ）の値を求める。その結果、パラメータとして図９に示すｗ＝（１．２，１．３）を得たとする。このパラメータをパラメータ格納手段１４ヘ渡す。なお、ＳＭＯを用いることにより、コンピュータで容易に処理して評価関数のパラメータを推定することができるようになる。
【００５０】
パラメータ格納ステップ（Ｓ１４）では、図９のパラメータを、再利用可能な形でパラメータ格納手段１４に格納する。ここで再利用可能な形とは、例えば磁気装置・メモリ等に記憶するものであるが、後に自動的に読み込める形態であれば何を用いても構わない。なお、閾値ｂＳも求まるので、これを格納するようにしてもよい。
【００５１】
対象データ入力ステップ（Ｓ２１）では、順位付けを行う対象となるデータ（文書集合）を対象データ入力手段２１から読み込む。本実施形態では、図５のデータ（Ａ，Ｂ，Ｃ）を読み込み、それを対象データのスコアを計算するスコア計算手段２２に渡す。
【００５２】
スコア計算ステップ（Ｓ２２）では、スコア計算手段２２が、パラメータ格納手段１４に格納された評価関数のパラメータ（図９）を読み込み、そのパラメータを代入した評価関数ｆ（χ）＝ｗ・χを用いて、対象データ入力手段２１から渡された対象データ（図５）の各々についてスコアを計算する。
【００５３】
図５、図９から、スコア計算ステップ（Ｓ２２）における、データＡのスコアはｆ（Ａ）＝１．２×０．９＋１．３×０．６＝１．８６となり、データＢのスコアはｆ（Ｂ）＝１．２×０．６＋１．３×０．２＝０．９８となり、データＣのスコアはｆ（Ｃ）＝１．２×０．３＋１．３×０．８＝１．４０となる（図１０参照）。このように、このスコア計算ステップ（Ｓ２２）では、図５の対象データのスコアに、図９の評価関数のパラメータを乗じることで、スコアを計算する。計算されたスコアは、データ整列手段２３ヘ渡される。
【００５４】
なお、図９は、評価関数のパラメータの例を示す図である。図１０は、スコア計算ステップで計算したスコアの例を示す図である。図１１は、対象データを順位付けした出力データの例を示す図である。
【００５５】
データ整列ステップ（Ｓ２３）では、データ整列手段２３が、渡されたスコアの大きいものから順に対象データを並べ替える。本例では、図１０に示すように、Ａ，Ｃ，Ｂの順にスコアが小さくなっていくので、その順に対象データを並べ替え、データ出力手段２４へと渡す（図１１）。
【００５６】
データ出力ステップ（Ｓ２４）では、データ出力手段２４が、並べ替えられたデータを順位とともに出力する。本実施形態では、図１１より、１位Ａ、２位Ｃ、３位Ｂとして出力する。
【００５７】
以上の実施形態では、順位付きデータ・対象データともに３個１組のものを例として説明したが、１組あたりデータ数は３以外でも構わない。また、全ての組についてデータ数が同一でなくても構わない。その場合には、順位付きデータ中の最も大きな順位より１だけ小さい値に、式（１１）〜（１４）におけるｓの値を置き、かつ、ｓ位より上位のデータに対してｙ［ｊ／ｉ，ｓ］＝＋１、下位のデータに対してｙ［ｊ／ｉ，ｓ］＝−１として、本実施形態と同様の手順を行うことが可能である。
【００５８】
〔結果の考察〕
以上の実施形態（実施形態例）で、順位付きデータ（サンプル）から評価関数（そのパラメータ）を推定する際、予め閾となる順位を設定する必要がなく、かつ、全順位にわたって精度の劣化しない評価関数を推定し、順位付けを行ったことを次に説明する。ここで、図１２は、従来方法の評価関数の推定に用いられるカテゴリ付きデータを示す表であり、２位を閾に示してある。図１３は、実施形態例の順位付け方法により得られた出力データの例を示す図である。図１４は、従来方法による順位付けにより得られた出力データの例を示す図である。
【００５９】
まず、カテゴリ付きデータ作成ステップ（Ｓ１２）では、特定の順位についての上位／下位ではなく、全ての順位についての上位／下位をカテゴリとしてラベルを付与しており、特定の順位を閾として決める必要はない。なお、本実施形態例では、閾値ｂＳは自ずと求まり、閾値ｂＳを決める必要は特にない。
【００６０】
次に、全順位にわたって精度の劣化しない評価関数（そのパラメータ）が推定できていることを、以下の従来方法と比較することで説明する。
【００６１】
まず、従来方法として平尾らの提案にしたがい、本実施形態例の順位付きデータに対して、２位の上位／下位を分類（カテゴライズ）する評価関数をサポートベクトルマシン（ＳＶＭ）により推定する。即ち、図１２にあるようなカテゴリ付きデータを用意し、ｙ［ｊ／ｉ］＝＋１なるデータを正例、ｙ［ｊ／ｉ］＝−１なるデータを負例として、ＳＶＭを適用する。ただし、カテゴリ付きデータは、２位が閾になっている。また、推定に使用する評価関数の形は、本実施形態例と同じく入力の線形関数ｗ’・χとする。
【００６２】
すると、ＳＶＭによる計算結果はｗ’＝（１．１，０．３）となる。なお、平尾らの提案は、「Ｓｕｐｐｏｒｔ　Ｖｅｃｔｏｒ　Ｍａｃｈｉｎｅ　による重要文抽出」、情報処理学会、第６３回情報処理学会基礎研究会予稿集（２００１年７月）に記載されている。
【００６３】
このパラメータ（ｗ’＝（１．１，０．３））を用いて本実施形態例の対象データ（図５参照）についてスコアを計算すると、Ａのスコアは１．１×０．９＋０．３×０．６＝１．１７、Ｂのスコアは１．１×０．６＋０．３×０．２＝０．７２、Ｃのスコアは１．１×０．３＋０．３×０．８＝０．５７になる。したがって、従来方法による順位付けの結果は、１位Ａ、２位Ｂ、３位Ｃ（Ａ→Ｂ→Ｃ）になり、本発明の順位付け結果、１位Ａ、２位Ｃ、３位Ｂ（Ａ→Ｃ→Ｂ）とは、２・３位の順番が異なる。
【００６４】
ここで順位付けした対象データ（出力データ）をプロットした図７を見ると、全体的に見て右上から左下にかけて順位が大きく（下位に）なっていることがわかる。したがって、対象データに対する本発明の順位付けＡ，Ｃ，Ｂの方が、従来方法による順位付けＡ，Ｂ，Ｃよりも、もっともらしいと言える。これは、本発明においては全体の順位付けを見て、全体的にもっともらしい評価関数を推定することができたのに対し（図１３）、従来方法では、２位の上位／下位という分類だけに基づいて推定を行ったために、それ以外の順位である１位の上位／下位の分類では間違いの大きい評価関数しか推定できなかったためである（図１４）。ちなみに、対象データの数がさらに多くなると、閾となる順位を用いる従来方法では、閾の順位から離れるほど順位付けの精度が大きく劣化することになる。
【００６５】
なおＳＶＭを用いない方法でも、ある特定の順位の上位／下位の分類のみに基づいて評価関数を推定する限り、同様の問題が発生する。
【００６６】
本実施形態例では、カテゴリ付きデータ作成ステップ（図３のＳ１２）で、一つの順位ではなく各順位、つまりサンプル中（順位付きデータ中）に現われる全ての順位の上位／下位についてカテゴリ分けを行い、評価関数推定ステップ（図３のＳ１３）で、全ての順位に対して上位／下位の分類を行うことができる評価関数のパラメータを決定した。これにより、予め閾となる順位を設定する必要がなく、かつ、全順位にわたって良い精度を達成する評価関数を推定することが可能となった。
【００６７】
また、従来方法では、どの順位を閾とすればよいかは、実際に推定された評価関数の精度を調べなければ決定することができないという問題があったが、以上説明したような評価関数の推定方法では、このような問題はない。このため、評価関数を迅速に推定することが可能である。
【００６８】
以上説明した本発明は、前記した実施形態に限定されることなく幅広く変形実施することができる。例えば、図３の順位付きデータ入力ステップＳ１１からパラメータ格納ステップＳ１４までと、対象データ入力ステップＳ２１からデータ出力ステップＳ２４までは、独立に動作させても構わない。また、順位付きデータ入力ステップＳ１１からパラメータ格納ステップＳ１４までは一度だけ動作させ、その後、対象データ入力ステップＳ２１からデータ出力ステップＳ２４までを繰り返し動作させることで、異なる対象データに対して順位付けを行うこともできる。また、実施形態では各データの表現に表形式を使用するが、表形式に限定されず、論理的に同等な形式表現を使用しても構わない。また、各プログラムは、ネットワーク上を送受信されたり、ＣＤ−ＲＯＭ等の記憶媒体に記憶されたりする。
【００６９】
また、実施形態では、上位／下位のカテゴリ付与を、出現する全ての順位について行ったが、必ずしも出現する全ての順位について行う必要はなく、間引くこともできる。つまり、請求項におけるところの「各順位についての上位／下位をカテゴリとして付与…」の一例が、実施形態におけるところの「全ての順位についての上位／下位をカテゴリとして付与…」に相当する。
【００７０】
また、実施形態では、サンプルとしての順位付けデータを１組３件（ｊ＝１位，２位，３位）で、３組（ｉ＝イ，ロ，ハ）のデータとしたが、例えば１組５〜２０件で、５〜５０組程度のデータとしてもよい。この場合は、式（１）〜（４）について、ｉに関する和は、順位付きデータの全ての組について求める。同様に、ｊに関する和は、１位から順位付きデータ中に現われる最も大きな順位まで求める。同様に、ｓに関する和は、１から順位付きデータ中に現われる最も大きな順位から１だけ小さい値まで求める。
【００７１】
また、図４等におけるカッコ内の数値（０．９，０．８），（０．４，０．５）…は、検索要求に一致する語の数に関連したスコアとしたが、順位付けを行うための何らかの尺度であればよい。
【００７２】
【発明の効果】
以上説明したように、本発明では、各順位の上位／下位を分類できるような評価関数を推定することで、予め閾となる順位を設定する必要がなく、かつ、各順位にわたって精度の劣化しない評価関数を求めることができる。また、この評価関数を用いて、各順位について、精度の劣化しない順位付けを行うことができる。また、このような順位付けのための評価関数を推定する評価関数推定装置や評価関数を用いて順位付けを行う順位付け装置、順位付けのための評価関数推定プログラム、プログラムを記憶した記憶媒体を提供することができる。つまり、以上説明した本発明によれば、順位付けの対象となる対象データを適切に順位付けすることのできる評価関数を推定することができ、また、推定した評価関数を用いて適切に順位付けを行うことができる。
【図面の簡単な説明】
【図１】（ａ）は本発明の実施形態に係る順位付け装置を機能展開したブロック図であり、（ｂ）は（ａ）の順位付け装置のハードウェア構成を示すブロック図である。
【図２】本発明の実施形態に係る順位付けのための評価関数推定方法及び順位付け方法を示すフローチャートである。
【図３】図２のフローチャートを直列に配置したフローチャートである。
【図４】評価関数を推定するための順位付きデータの例を示す表である。
【図５】順位付けの対象となる対象データの例を示す表である。
【図６】順位付けデータを順位付けした出力データの例を示す表である。
【図７】データの理解を容易にするために、順位付きデータ（図４）と対象データ（図５）を平面にプロットしてグラフ化した図である。
【図８】カテゴリ付きデータの例を示す表である。
【図９】評価関数のパラメータの例を示す図である。
【図１０】スコア計算ステップで計算したスコアの例を示す図である。
【図１１】対象データを順位付けした出力データの例を示す図である。
【図１２】従来方法の評価関数の推定に用いられるカテゴリ付きデータを示す表であり、２位を閾に示してある。
【図１３】本発明の実施形態に係る順位付け方法により得られた出力データの例を示す図である。
【図１４】従来方法による順位付けにより得られた出力データの例を示す図である。
【符号の説明】
Ａ　…　順位付け装置
１１…順位付きデータ入力手段、１２…カテゴリ付きデータ作成手段、１３…評価関数推定手段、１４…パラメータ格納手段、２１…データ入力手段、２２…スコア計算手段、２３…データ整列手段、２４…データ出力手段
【図１】
2004062737.tif 000005
【図２】
2004062737.tif 000006
【図３】
2004062737.tif 000007
【図４】
2004062737.tif 000008
【図５】
2004062737.tif 000009
【図６】
2004062737.tif 000010
【図７】
2004062737.tif 000011
【図８】
2004062737.tif 000012
【図９】
2004062737.tif 000013
【図１０】
2004062737.tif 000014
【図１１】
2004062737.tif 000015
【図１２】
2004062737.tif 000016
【図１３】
2004062737.tif 000017
【図１４】
2004062737.tif 000018