(57)【要約】【課題】部分順位付きデータから評価関数を推定する際に、適応性の高い評価関数を推定することができる順位付け評価関数推定方法、装置及びプログラム並びに記憶媒体を提供する。【解決手段】順位が付けられていない順位無しデータを順位付けする際の基準となる評価関数を、特定の部分に順位が付けられた部分順位付きデータから推定する順位付け評価関数推定装置１であって、順位無しデータと部分順位付きデータとを入力するデータ入力手段３と、部分順位付きデータに基づいて暫定評価関数を算出する暫定評価関数算出手段５と、順位無しデータと暫定評価関数とを用いて、部分順位付きデータに重み付けを行う部分順位付きデータ重み付け手段７と、重み付け部分順位付きデータから評価関数を推定する評価関数推定手段９と、評価関数を出力する評価関数出力手段１１と、を備えた。【選択図】　　　図１
2004133667.tif 000002
【特許請求の範囲】
【請求項１】
順位が付けられていない順位無しデータを順位付けする際の基準となる評価関数を、特定の部分に順位が付けられた部分順位付きデータから推定する順位付け評価関数推定方法であって、
前記順位無しデータと前記部分順位付きデータとを入力し、前記部分順位付きデータに基づき仮に定められる暫定評価関数を算出し、前記部分順位付きデータおよび前記順位無しデータを前記暫定評価関数に入力して得られた暫定評価関数値に基づいた重み付けを算出し、この重み付けを前記部分順位付きデータに行い、重み付けられた部分順位付きデータから評価関数を推定し、出力すること、
を特徴とする順位付け評価関数推定方法。
【請求項２】
前記暫定評価関数値に基づいた重み付けは、前記部分順位付きデータおよび前記順位無しデータを前記暫定評価関数に入力し得られた結果を混ぜ合わせて並べ替え、この並べ替えの結果得られた順位に基づいて、前記部分順位付きデータの各データが順位付きで出現する確率に反比例する重み付けであることを特徴とする請求項１に記載の評価関数推定方法。
【請求項３】
順位が付けられていない順位無しデータを順位付けする際の基準となる評価関数を、特定の部分に順位が付けられた部分順位付きデータから推定する順位付け評価関数推定装置であって、
前記順位無しデータと前記部分順位付きデータとを入力するデータ入力手段と、
前記部分順位付きデータに基づき仮に定められる暫定評価関数を算出する暫定評価関数算出手段と、
前記部分順位付きデータおよび前記順位無しデータを前記暫定評価関数に入力して得られた暫定評価関数値に基づいた重み付けを算出し、この重み付けを前記部分順位付きデータに行う部分順位付きデータ重み付け手段と、
この部分順位付きデータ重み付け手段で、重み付けられた重み付け部分順位付きデータから評価関数を推定する評価関数推定手段と、
この評価関数推定手段で推定された評価関数を出力する評価関数出力手段と、
を備えることを特徴とする順位付け評価関数推定装置。
【請求項４】
順位が付けられていない順位無しデータを順位付けする際の基準となる評価関数を、特定の部分に順位が付けられた部分順位付きデータから推定する装置を、
前記順位無しデータと前記部分順位付きデータとを入力するデータ入力手段、
前記部分順位付きデータに基づき仮に定められる暫定評価関数を算出する暫定評価関数算出手段、
前記部分順位付きデータおよび前記順位無しデータを前記暫定評価関数に入力して得られた暫定評価関数値に基づいた重み付けを算出し、この重み付けを前記部分順位付きデータに行う部分順位付きデータ重み付け手段、
この部分順位付きデータ重み付け手段で、重み付けられた重み付け部分順位付きデータから評価関数を推定する評価関数推定手段、
この評価関数推定手段で推定された評価関数を出力する評価関数出力手段、
として機能させることを特徴とする順位付け評価関数推定プログラム。
【請求項５】
請求項４に記載の順位付け評価関数推定プログラムを記憶したことを特徴とする順位付け評価関数推定プログラムを記憶した記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば、情報検索システム等で、当該システムのユーザに提示する情報を自動的に順位付ける際に用いられる評価関数に係り、順位付けられたサンプルデータに基づいて、順位付けの基準となる評価関数を推定する順位付け評価関数推定方法、装置及びプログラム並びに記憶媒体に関する。
【０００２】
【従来の技術】
近年、コンピュータやインターネットの普及により、取り扱われる（流通する）情報が膨大な量に達しており、この膨大な量の情報の中から適切な情報（所望情報）を検索する情報検索システムも一般化している。このような情報検索システムでは、通常、所望情報として検索された情報（検索情報）が大量となる場合が多く、何らかの基準に従って検索情報が順位付けられ、当該情報検索システムのユーザに提示されている。
【０００３】
通常、検索情報の順位付けは、ある評価関数に基づいて、各検索情報にスコアを付加し、このスコアの高い順に検索情報を順位付けて出力するといった形式で行われることが多い。この検索情報の順位付けで使用される評価関数は、従来、情報検索システムのシステム設計者の経験や直感を頼りに作成されている場合が多く、例えば、情報検索システムのユーザが、情報検索システムを使用して所望情報を検索する際に入力した検索キーワード（検索要求）と一致する語数等が評価関数を作成する際に参考にされてきた。
【０００４】
ところが、最近、情報のサンプル（検索情報に該当）に対して、理想的な順位付けを行ったデータ（順位付きデータ）から自動的に評価関数を推定する技術が幾つか提案されている（例えば、非特許文献１）。この非特許文献１で提案されている評価関数の推定は、各順位付きデータに対する評価関数の関数値が順位と同じ順番に並ぶ（例えば、関数値の順位が３位ならば、３番目に並ぶ）と共に、それぞれの関数値の間隔が出来るだけ大きくなるような評価関数を、与えられた関数族（評価関数の集合）の中から選択することで行われている。
【０００５】
【非特許文献１】
Ｒ．Ｈｅｒｂｒｉｃｈ　ｅｔ　ａｌ．“Ｌａｒｇｅ　Ｍａｒｇｉｎ　Ｒａｎｋ　Ｂｏｕｎｄａｒｉｅｓ　ｆｏｒ　Ｏｒｄｉｎａｌ　Ｒｅｇｒｅｓｓｉｏｎ”（Ａｄｖａｎｃｅｓ　ｉｎ　Ｌａｒｇｅ　Ｍａｒｇｉｎ　Ｃｌａｓｓｉｆｉｅｒｓ　ｐｐ．１１５−１３２，Ｔｈｅ　ＭＩＴ　Ｐｒｅｓｓ（２０００））
【０００６】
【発明が解決しようとする課題】
ところで、この非特許文献１で提案されている評価関数の推定では、与えられた順位付きデータ全体に順位が付けられていることが前提となっている。しかしながら、与えられた順位付きデータから、実際に評価関数を推定する場合、上位に位置する順位付きデータの順位のみが明確になっており、下位に位置する順位付きデータの順位が不明確な（順序関係がわからない）場合が多々存在する。なお、以下の説明では、上位に位置しており順位が明確になっている（順位付けがなされている）順位付きデータを部分順位付きデータと記載することとする。
【０００７】
例えば、前記した情報検索システムで情報検索を行う場合、出力対象となる検索情報（例えば、文書）の数が膨大となることが多い。従って、従来のシステムでは、全ての検索情報に対して、順位付きデータを用意することは事実上不可能であり、検索キーワード（検索要求）に対して、部分順位付きデータに基づき妥当性の高い上位の検索情報のみ順位付けられるのが一般的である。
【０００８】
このように、部分順位付きデータしか得られていない場合、この部分順位付きデータを従来の情報検索システムに適用すると、順位が明確になっているデータ領域（上位）では、比較的に適応性の高い評価関数を推定できるが、それ以外のデータ領域（中位、下位）では、適応性の低い評価関数を推定してしまうという問題がある。
【０００９】
そこで、本発明の目的は前記した従来の技術が有する課題を解消し、部分順位付きデータから評価関数を推定する際に、適応性の高い評価関数を推定することができる順位付け評価関数推定方法、装置及びプログラム並びに記憶媒体を提供することにある。
【００１０】
【課題を解決するための手段】
本発明は、前記した目的を達成するため、以下に示す構成とした。
請求項１記載の順位付け評価関数推定方法は、順位が付けられていない順位無しデータを順位付けする際の基準となる評価関数を、特定の部分に順位が付けられた部分順位付きデータから推定する順位付け評価関数推定方法であって、前記順位無しデータと前記部分順位付きデータとを入力し、前記部分順位付きデータに基づき仮に定められる暫定評価関数を算出し、前記部分順位付きデータおよび前記順位無しデータを前記暫定評価関数に入力し得られた暫定評価関数値に基づいた重み付けを算出し、この重み付けを前記部分順位付きデータに行い、重み付けられた部分順位付きデータから評価関数を推定し、出力すること、を特徴とする。
【００１１】
この方法によれば、まず、はじめに、順位無しデータと部分順位付きデータとが入力される。部分順位付きデータに基づいて、最終的に求めたい評価関数を暫定的に推定した暫定評価関数が算出される。そして、この暫定評価関数に部分順位付きデータおよび順位無しデータとが入力されて暫定評価関数値に基づいた重み付けが算出されて、部分順位付きデータに重み付けがなされる。この重み付けがなされた部分順位付きデータに基づいて評価関数が推定される。つまり、この方法では、暫定評価関数に部分順位付きデータおよび順位無しデータが入力され暫定評価関数値が算出され、この値に基づいた重み付けが部分順位付きデータになされることで、特定の部分に順位が付けられている部分順位付きデータの順位の付けられていない部分（特に、下位位置の領域にある下位データ）も重視することになり、順位の分かっていない領域でも妥当な（適応性の高い）評価関数を推定することが可能になる。
【００１２】
請求項２記載の順位付け評価関数推定方法は、請求項１に記載の評価関数推定方法において、前記暫定評価関数値に基づいた重み付けは、前記部分順位付きデータおよび前記順位無しデータを前記暫定評価関数に入力し得られた結果を混ぜ合わせて並べ替え、この並べ替えの結果得られた順位に基づいて、前記部分順位付きデータの各データが順位付きで出現する確率に反比例する重み付けであることを特徴とする。
【００１３】
この方法によれば、部分順位付きデータの中で、順位の付いていないデータについて、順付きで出現する確率に反比例する重み付けがなされるので、評価関数を推定する際に、順位の付いていないデータに関しても、妥当な偏りの少ない評価関数を推定することができる。
【００１４】
請求項３記載の順位付け評価関数推定装置は、順位が付けられていない順位無しデータを順位付けする際の基準となる評価関数を、特定の部分に順位が付けられた部分順位付きデータから推定する順位付け評価関数推定装置であって、前記順位無しデータと前記部分順位付きデータとを入力するデータ入力手段と、前記部分順位付きデータに基づき仮に定められる暫定評価関数を算出する暫定評価関数算出手段と、前記部分順位付きデータおよび前記順位無しデータを前記暫定評価関数に入力し得られた暫定評価関数値に基づいた重み付けを算出し、この重み付けを前記部分順位付きデータに行う部分順位付きデータ重み付け手段と、この部分順位付きデータ重み付け手段で、重み付けられた重み付け部分順位付きデータから評価関数を推定する評価関数推定手段と、この評価関数推定手段で推定された評価関数を出力する評価関数出力手段と、を備えることを特徴とする。
【００１５】
かかる構成によれば、データ入力手段で順位付けの対象となる順位無しデータと、特定の部分に順位が付けられている部分順位付きデータとが入力される。暫定評価関数算出手段で、データ入力手段にて入力されたそのままの部分順位付きデータに基づいて暫定評価関数が算出される。そして、部分順位付きデータ重み付け手段で部分順位付きデータおよび順位無しデータが暫定評価関数に入力され得られた暫定評価関数値に基づいた重み付けが算出され、この重み付けが部分順位付きデータになされる。さらに、評価関数推定手段で、重み付け部分順位付きデータに基づいて評価関数が推定される。この評価関数推定手段で推定される評価関数は、重みが大きいデータについて間違いが少なくなるようなものである。その後、評価関数出力手段で評価関数が再利用可能な形式で出力される。
【００１６】
請求項４記載の順位付け評価関数推定プログラムは、順位が付けられていない順位無しデータを順位付けする際の基準となる評価関数を、特定の部分に順位が付けられた部分順位付きデータから推定する装置に関し、当該装置を以下に示す手段として機能させることを特徴とする。当該装置を機能させる手段は、前記順位無しデータと前記部分順位付きデータとを入力するデータ入力手段、前記部分順位付きデータに基づき仮に定められる暫定評価関数を算出する暫定評価関数算出手段、前記部分順位付きデータおよび前記順位無しデータを前記暫定推定評価関数に入力し得られた暫定評価関数値に基づいた重み付けを算出し、この重み付けを前記部分順位付きデータに行う部分順位付きデータ重み付け手段、この部分順位付きデータ重み付け手段で、重み付けられた重み付け部分順位付きデータから評価関数を推定する評価関数推定手段、この評価関数推定手段で推定された評価関数を出力する評価関数出力手段、である。
【００１７】
かかる構成によれば、データ入力手段で順位付けの対象となる順位無しデータと、特定の部分に順位が付けられている部分順位付きデータとが入力される。暫定評価関数算出手段で、データ入力手段にて入力されたそのままの部分順位付きデータに基づいて暫定評価関数が算出される。そして、部分順位付きデータ重み付け手段で部分順位付きデータおよび順位無しデータを暫定評価関数に入力し得られた暫定評価関数値に基づいた重み付けを算出し、この重み付けが部分順位付きデータになされる。さらに、評価関数推定手段で、重み付け部分順位付きデータに基づいて評価関数が推定される。その後、評価関数出力手段で評価関数が再利用可能な形式で出力される。
【００１８】
請求項５記載の順位付け評価関数推定プログラムを記憶した記憶媒体は、請求項４に記載の順位付け評価関数推定プログラムを記憶したことを特徴とする。
【００１９】
かかる構成によれば、順位付け評価関数推定プログラムの作用に加え、記憶媒体を取り扱う（読み取る）ことのできるコンピュータ等の装置を機能させることができ、流通させることができる。
【００２０】
【発明の実施の形態】
以下、本発明の一実施の形態について、図面を参照して詳細に説明する。
（順位付け評価関数推定装置の構成）
図１は、順位付け評価関数推定装置のブロック図である。この図１に示すように、順位付け評価関数推定装置１は、データ入力手段３と、暫定評価関数算出手段５と、部分順位付きデータ重み付け手段７と、評価関数推定手段９と、評価関数出力手段１１とを備えている。
【００２１】
この順位付け評価関数推定装置１は、特定の部分（例えば、上位部分）にのみ順位が付けられている部分順位付きデータと、順位が全く付けられていない順位無しデータとを用いて、順位無しデータを順位付けする際の基準となる評価関数を推定するものである。
【００２２】
ここで、この順位付け評価関数推定装置１の具体的構成について補足しておく。この順位付け評価関数推定装置１は、この実施の形態では、図示を省略した主制御部と、記憶部と、通信制御部と、入出力部とを備え、これらがバスで接続されたコンピュータによって構成されている。主制御部は、ＣＰＵ（ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）とメインメモリ（ＲＡＭ）等を含んで構成され、順位付け評価関数推定装置１を統括制御する機能を有し、入力された部分順位付きデータ、順位無しデータとに基づいて、暫定評価関数、重み付け部分順位付きデータおよび評価関数を算出、推定するものである。
【００２３】
記憶部は、ハードディスク等を含んで構成され、入力された部分順位付きデータや順位無しデータを記憶すると共に、暫定的に求めた暫定評価関数や、出力である評価関数を記憶するものである。また、通信制御部は、例えば、ネットワークインターフェースカード（ＮＩＣ；Ｎｅｔｗｏｒｋ　Ｉｎｔｅｒｆａｃｅ　Ｃａｒｄ）、外部接続端子（ポート部）等を含んで構成され、所定の通信プロトコルによって通信（データの入出力）を実現する機能を有するものである。入出力部は、一般的なキーボード、マウス等を含んで構成され、順位付け評価関数推定装置１のユーザから部分順位付きデータおよび順位無しデータを入力され、これらの推定結果である評価関数を出力するものである。
【００２４】
これより、順付け評価関数推定装置１の各構成を説明する。
データ入力手段３は、部分順位付きデータおよび順位無しデータを入力するものであり、部分順位付きデータ入力手段３ａと、順位無しデータ入力手段３ｂとを備えている。部分順位付きデータ入力手段３ａは、部分順位付きデータを入力するものであり、順位無しデータ入力手段３ｂは、順位無しデータを入力するものである。部分順位付きデータは、評価関数を推定するためのサンプルとなるもので、部分順位付きデータはデータ全体の中で特定の部分（一部分）のみに順位（優先選択順位といえる）が付与されているものである。順位無しデータは、順位付けの対象となる順位が付けられていないもので、部分順位付きデータの重み（重み付け）を計算するのに利用されるものである。
【００２５】
暫定評価関数算出手段５は、部分順位付きデータ中で大小関係が明確になっている（順位が付けられている）データ対だけを使用して、この大小関係に適合する暫定評価関数を推定すると共に、推定した暫定評価関数および部分順位付きデータを部分順位付きデータ重み付け手段に出力するものである。
【００２６】
部分順位付きデータ重み付け手段７は、部分順位付きデータと順位無しデータに基づいて、暫定評価関数を大きい順に整列し、順位無しデータが部分順位付きデータの中に順位付きで出現する確率（以下、出現確率という）を計算し、部分順位付きデータの中で順位が付与されているものについて、出現確率に反比例する重みを付与し（重み付けをし）、重み付け部分順位付きデータとして、評価関数推定手段９に出力するものである。
【００２７】
評価関数推定手段９は、暫定評価関数算出手段５にて推定された暫定評価関数と、部分順位付きデータ重み付け手段７にて重み付けされた重み付け部分順位付きデータとに基づいて、重みの大きな部分順位付きデータを含むデータ対ほど間違いが少なくなるような評価関数を推定し、評価関数出力手段１１に出力するものである。
【００２８】
評価関数出力手段１１は、評価関数推定手段９にて推定された評価関数を再利用可能な形式で出力するものである。再利用可能な形式とは、例えば、汎用的なコンピュータ言語で記述した１個のファイルにまとめた形式である。
【００２９】
（順位付け評価関数推定装置の動作）
次に、図２、図３に示すフローチャートを参照して、順位付け評価関数推定装置１の動作について説明する（適宜、図１参照）。なお、図２に示したフローチャートは、情報（部分順位付きデータ、順位無しデータ等）の流れを主体に図示したもので、図３に示すフローチャートは、各構成の処理を主体に図示したものである。また、Ｓ１はＳ１１に、Ｓ２はＳ１２に、Ｓ３はＳ１３に、Ｓ４はＳ１４に、Ｓ５はＳ１５に対応している。この図２、図３に示した処理フローは、特許請求の範囲の「順位付け評価関数推定方法」、「順位付け評価関数推定プログラム」に相当するものである。
【００３０】
まず、部分順位付きデータおよび順位無しデータがデータ入力手段３に入力される（読み込まれる）（Ｓ１、Ｓ１１）。図２では、データ入力ステップである。暫定評価関数算出手段５で部分順位付きデータから暫定評価関数が推定される（Ｓ２、Ｓ１２）。図２では暫定学習ステップであり、この暫定評価関数算出手段５で暫定評価関数および部分順付きデータが部分順位付きデータ重み付け手段７に出力され、データ入力手段３の順位無しデータ入力手段３ｂから順位無しデータが部分順位付きデータ重み付け手段７に出力される。
【００３１】
すると、部分順位付きデータ重み付け手段７で部分順位付きデータと順位無しデータに基づいて、暫定評価関数の大きい順に整列させて、これらのデータ（部分順位付きデータおよび順位無しデータ）が部分順位付きデータ中に順位付きで出現する出現確率が計算され、部分順位付きデータの中で順位が付けられているについて出現確率に反比例する重みが付与される（重み付けがなされる）（Ｓ３、Ｓ１３）。図２では、重み付けステップである。
【００３２】
そして、この部分順位付きデータ重み付け手段７で重み付けがなされた重み付け部分順位付きデータに基づいて、評価関数推定手段９で評価関数が推定される（Ｓ４、Ｓ１４）。その後、評価関数出力手段１１で評価関数が出力される（Ｓ５、Ｓ１５）。
【００３３】
この順位付け評価関数推定装置１によれば、データ入力手段３で順位付けの対象となる順位無しデータと、特定の部分に順位が付けられている部分順位付きデータとが入力される。暫定評価関数算出手段５で、データ入力手段３にて入力されたそのままの部分順位付きデータに基づいて暫定評価関数が算出される。そして、部分順位付きデータ重み付け手段７で順位無しデータと暫定評価関数に基づいて、部分順位付きデータの重み付けがなされる。さらに、評価関数推定手段９で、重み付け部分順位付きデータに基づいて評価関数が推定される。その後、評価関数出力手段１１で評価関数が再利用可能な形式で出力される。このため、暫定評価関数を使用して、順位が不明な（不明確な）データ領域（中位、下位位置）に位置するデータほど、部分順位付きデータ重み付け手段７で重み付けがなされるので、順位が不明なデータ領域（順位が分かっていない領域）でも、部分順位付きデータから、適応性の高い（妥当な）評価関数を推定することができる。
【００３４】
（順位付け評価関数推定装置の具体的な動作）
次に、図４から図１０を参照して、順位付け評価関数推定装置１の具体的な動作について説明する（適宜、図１参照）。
なお、以下の説明では、部分順位付きデータ、順位無しデータ、重み付け部分順位付きデータの表現形式を用いているが、論理的に同等の表現形式に置き換えてもよい。
【００３５】
図４は部分順位付きデータを示した図であり、図５は順位無しデータを示した図であり、図６は評価関数を示した図であり、図７は暫定評価関数を示した図であり、図８は暫定評価関数値をソートした結果を示した図であり、図９は出現確率を示した図であり、図１０は重み付け部分順位付きデータを示した図である。
【００３６】
図４に示した部分順位付きデータは、５個（名称：Ａ、Ｂ、Ｃ、Ｄ、Ｅ）のデータからなる２次元ベクトルで与えられたもので、５個のデータの内、上位３位までに順位が付けられているものである。図５に示した順位無しデータは、１０個（名称：Ｕ１、Ｕ２、Ｕ３、Ｕ４、Ｕ５、Ｕ６、Ｕ７、Ｕ８、Ｕ９、Ｕ１０）のデータからなる２次元ベクトルで与えられたものである。
【００３７】
まず、データ入力手段３に図４に示した部分順位付きデータおよび図５に示した順位無しデータが入力され（読み込まれ）、暫定評価関数算出手段５では、部分順位付きデータの中で大小関係のわかるデータ対を使用して、この大小関係に適合する暫定評価関数が推定される（暫定される）。この実施の形態では、Ｒ．ｈｅｒｂｒｉｃｈ　ｅｔ　ａｌ．“Ｌａｒｇｅ　Ｍａｒｇｉｎ　Ｒａｎｋ　Ｂｏｕｎｄａｒｉｅｓ　ｆｏｒ　Ｏｒｄｉｎａｌ　Ｒｅｇｒｅｓｓｉｏｎ”（Ａｄｖａｎｃｅｓ　ｉｎ　Ｌａｒｇｅ　Ｍａｒｇｉｎ　Ｃｌａｓｓｉｆｉｅｒｓ　ｐｐ．１１５−１３２，Ｔｈｅ　ＭＩＴ　Ｐｒｅｓｓ（２０００））で提案されている手法であるｌｉｎｅａｒ　ｋｅｒｎｅｌを用いた方法（以下、「Ｈｅｒｂｒｉｃｈの方法」という）によって暫定評価関数を推定する（暫定する）こととする。
【００３８】
このＨｅｒｂｒｉｃｈの方法では、図４に示した部分順位付きデータＡ、Ｂ、Ｃ、Ｄ、Ｅの座標を表すベクトルｘＡ、ｘＢ、ｘＣ、ｘＤ、ｘＥに対して、暫定評価関数ｇ（ｘ）＝ｗ・ｘを次の条件を満たすように求められる。なお、ｗはパラメータであり、詳細は後記する。
【００３９】
【数１】
2004133667.tif 000003
【００４０】
この数式１を条件式の（１）とする。
また、各条件式（２）〜（１０）が以下のようになる。
【００４１】
ｇ（ｘＡ）−ｇ（ｘＢ）≧１−ξＡＢ，ξＡＢ≧０・・・（２）
ｇ（ｘＡ）−ｇ（ｘＣ）≧１−ξＡＣ，ξＡＣ≧０・・・（３）
ｇ（ｘＡ）−ｇ（ｘＤ）≧１−ξＡＤ，ξＡＤ≧０・・・（４）
ｇ（ｘＡ）−ｇ（ｘＥ）≧１−ξＡＥ，ξＡＥ≧０・・・（５）
ｇ（ｘＢ）−ｇ（ｘＣ）≧１−ξＢＣ，ξＢＣ≧０・・・（６）
ｇ（ｘＢ）−ｇ（ｘＤ）≧１−ξＢＤ，ξＢＤ≧０・・・（７）
ｇ（ｘＢ）−ｇ（ｘＥ）≧１−ξＢＥ，ξＢＥ≧０・・・（８）
ｇ（ｘＣ）−ｇ（ｘＤ）≧１−ξＣＤ，ξＣＤ≧０・・・（９）
ｇ（ｘＣ）−ｇ（ｘＥ）≧１−ξＣＥ，ξＣＥ≧０・・・（１０）
【００４２】
ただし、Ｃは部分順位付きデータ（サンプル）に対する暫定評価関数の精度と、後記するパラメータに対する正規化項とのバランスを決める定数（比例係数）であり、この実施の形態では、Ｃ＝１としている。
【００４３】
また、前記した条件式（２）〜（１０）は、
（２）は、Ａ（１位）の暫定評価関数がＢ（２位）より１−ξＡＢだけ大きい、
（３）は、Ａ（１位）の暫定評価関数がＣ（３位）より１−ξＡＣだけ大きい、
（４）は、Ａ（１位）の暫定評価関数がＤ（４位以下）より１−ξＡＤだけ大きい、
（５）は、Ａ（１位）の暫定評価関数がＥ（４位以下）より１−ξＡＥだけ大きい、
（６）は、Ｂ（２位）の暫定評価関数がＣ（３位）より１−ξＢＣだけ大きい、
（７）は、Ｂ（２位）の暫定評価関数がＤ（４位以下）より１−ξＢＤだけ大きい、
（８）は、Ｂ（２位）の暫定評価関数がＥ（４位以下）より１−ξＢＥだけ大きい、
（９）は、Ｃ（３位）の暫定評価関数がＤ（４位以下）より１−ξＣＤだけ大きい、
（１０）は、Ｃ（３位）の暫定評価関数がＥ（４位以下）より１−ξＣＥだけ大きい、
という条件を示しており、仮に十分小さなξｉｊに対してこれらの条件を満たす暫定評価関数ｇ（ｘ）が存在すれば、暫定評価関数ｇ（ｘ）は部分順位付きデータ中で示された順位とよく合う暫定評価関数であるといえる。
【００４４】
（１）の第二項は「ξｉｊができるだけ小さくなるようにする」という条件を示している。この第二項に対し、（１）の第一項は機械学習の分野で正規化項と呼ばれるものの一種であり、パラメータｗの値を小さくすることで、部分順位付きデータだけによく合うような評価関数を推定すること、すなわち、過学習を避ける効果があることが知られている（詳しくはＳｃｈｏｌｋｏｐｆ　ｅｔ　ａｌ．“Ｌｅａｒｎｉｎｇ　ｗｉｔｈ　Ｋｅｒｎｅｌｓ”　Ｔｈｅ　ＭＩＴ　Ｐｒｅｓｓ（２００２）を参照のこと）。
【００４５】
この実施の形態では、（１）〜（１０）を解いた結果、図７に示したｇ（ｘ）＝１．８ｘ１−０．２ｘ２が得られたとする。この暫定評価関数ｇ（ｘ）と、部分順位付きデータと、順位無しデータとが部分順位付きデータ重み付け手段７に入力される。
【００４６】
この部分順位付きデータ重み付け手段７では、暫定評価関数ｇ（ｘ）に部分順位付きデータおよび順位無しデータの座標を入力して得られた値である暫定評価関数値の大きい順にソートされる。このソートした結果を図８に示す。この暫定評価関数値を大きい順にソートしたソート結果によって得られた順位から、部分順位付きデータ中で順位が付いているデータＡ、Ｂ、Ｃについて、出現確率が計算される。この出現確率とは、部分順位付きデータと同じ数のデータ（以下、同数データという、この場合、５個のデータ）を再度サンプリングしたとき（暫定評価関数を求めたとき）に、同数データが再び順位付き（この実施の形態では３位以内）で現れる確率であり、次式、数式２によって与えられる。
【００４７】
【数２】
2004133667.tif 000004
【００４８】
この数式２において、ｍは部分順位付きデータの数（この実施の形態では５個）、ｎはその中で順位付けされている数（この実施の形態では３個）を示すものである。また、Ｆ（ｘ）は部分順位付きデータを得た母集団の中でｘよりも順位が下となるデータの割合を表したもので、次式、数式３によって与えられる。
【００４９】
【数３】
2004133667.tif 000005
【００５０】
ここで、図８に示したソート結果、数式２および数式３に基づいて、部分順位付きデータの中で順位が付いているデータＡ、Ｂ、Ｃについて出現確率が演算（計算）される。この出現確率の演算結果を図９に示す。この図９に示した出現確率と反比例するように、部分順位付きデータの中で順位が付いているデータＡ、Ｂ、Ｃの重みが計算される。この実施の形態では比例係数Ｃ＝１とし、図９に示した出現確率の逆数を、部分順位付きデータの中で順位が付いているデータＡ、Ｂ、Ｃの重みとする。このようにして得られた重み付け部分順位付きデータを図１０に示す。そして、この重み付け部分順位付きデータが評価関数推定手段９に入力される。
【００５１】
この評価関数推定手段９では、図１０に示した重み付け部分順位付きデータから、重みの大きな重み付け部分順位付きデータとの対ほど順位付けに関して、間違いが少なくなるように評価関数が推定される。この評価関数の推定には、部分順位付きデータの重要性について重み付けができるような任意の推定方法が使用できるが、この実施の形態では、Ｈｅｒｂｒｉｃｈの方法を次のように変更した方法で使用することとする。
【００５２】
すなわち、部分順位付きデータＡ、Ｂ、Ｃ、Ｄ、Ｅの座標を表すベクトルｘＡ、ｘＢ、ｘＣ、ｘＤ、ｘＥと、この中で順位が付けられているデータＡ、Ｂ、Ｃに対する重みＣＡ＝１．０、ＣＢ＝１．０、ＣＣ＝１．４とすると、評価関数ｆ（ｘ）＝ｗ´・ｘを次の条件を満たすように求められる。
【００５３】
【数４】
2004133667.tif 000006
【００５４】
この数式４を条件式の（１３）とする。
また、各条件式（１４）〜（２２）が以下のようになる。
【００５５】
ｆ（ｘＡ）−ｆ（ｘＢ）≧１−ξ´ＡＢ，ξ´ＡＢ≧０・・・（１４）
ｆ（ｘＡ）−ｆ（ｘＣ）≧１−ξ´ＡＣ，ξ´ＡＣ≧０・・・（１５）
ｆ（ｘＡ）−ｆ（ｘＤ）≧１−ξ´ＡＤ，ξ´ＡＤ≧０・・・（１６）
ｆ（ｘＡ）−ｆ（ｘＥ）≧１−ξ´ＡＥ，ξ´ＡＥ≧０・・・（１７）
ｆ（ｘＢ）−ｆ（ｘＣ）≧１−ξ´ＢＣ，ξ´ＢＣ≧０・・・（１８）
ｆ（ｘＢ）−ｆ（ｘＤ）≧１−ξ´ＢＤ，ξ´ＢＤ≧０・・・（１９）
ｆ（ｘＢ）−ｆ（ｘＥ）≧１−ξ´ＢＥ，ξ´ＢＥ≧０・・・（２０）
ｆ（ｘＣ）−ｆ（ｘＤ）≧１−ξ´ＣＤ，ξ´ＣＤ≧０・・・（２１）
ｆ（ｘＣ）−ｆ（ｘＥ）≧１−ξ´ＣＥ，ξ´ＣＥ≧０・・・（２２）
ここで、（１４）〜（２２）は、暫定評価関数算出手段５で使用した各条件（２）〜（１０）と同じである。しかしながら、数式４（式（１３））で、ＣＡ、ＣＢ、ＣＣが乗算されていることで、重みの大きい部分順位付きデータほど、よりξｉｊが小さくなるようにパラメータｗ´を求める点が暫定評価関数算出手段５における演算とは異なる。
【００５６】
これらの式（１３）〜（２２）を解くことで、図６に示した評価関数ｆ（ｘ）＝２．０ｘ１が得られ、この評価関数ｆ（ｘ）が評価関数出力手段１１に出力される。そして、この評価関数出力手段１１で評価関数ｆ（ｘ）が再利用可能な形式で出力される。この実施の形態では、評価関数ｆ（ｘ）を直接提示することで出力としている。
【００５７】
（順位付け評価関数推定装置の具体的な動作における結果について）
以上説明した順位付け評価関数推定装置１の具体的な動作において、従来の方法に比べた顕著な効果、すなわち、部分順位付きデータから順位の分かっていない領域（データＤ、Ｅがある下位の領域）でも適応性の高い（妥当な）評価関数が推定できることについて説明する。この説明のために、部分順位付きデータを平面にプロットした図１１を示す。
【００５８】
この図１１から読みとれるように、この実施の形態における部分順位付きデータは、図１１中、右下（ｘ１＝１，ｘ２＝０）に近い領域にあるデータＡ（１位）が最も順位が高く、次に、図１１中、中央上部（ｘ１＝１，ｘ２＝１）の近くにデータＢ（２位）、データＣ（３位）と順位が下がり、さらに、図１１中、左下（ｘ１＝０，ｘ２＝０）に近い領域にあるデータＤ、データＥ（両方とも４位以下）が最も低い順位となっている。
【００５９】
従って、この順位付け評価関数推定装置１の具体的な動作で仮定した線形の評価関数を用いる場合、図１１中、イの矢印で示したように、ｘ１軸と平行な方向に値が増加する関数が用いられることで、部分順位付きデータの順位と最もよく合致する（適合する）評価関数が得られる。実際、この実施の形態では、図６に示した評価関数２．０ｘ１は、ｘ１軸と平行な方向に値が増大する関数となっている。
【００６０】
ところで、従来の評価関数の推定方法（例えば、順序付け学習方法）を部分順位付きデータに適用した例として、この実施の形態における暫定評価関数算出手段５で推定した暫定評価関数を、最終的な評価関数として用いる方法を想定してみる。この場合、評価関数は、図７に示したもの（１．８ｘ１−０．２ｘ２）となる。図１１中、ロの矢印で示したように、この矢印ロの方向は評価関数が増大する方向を示すものである。
【００６１】
すると、この図１１から明らかなように、矢印イの方向に比べ、矢印ロの方向では、データＣ、データＤに対する評価関数の値（評価関数値）の差が小さくなる。一般に、与えられた部分順位付きデータに対して、評価関数の差が小さい場合には、未知のデータ（順位付けの対象となる順位無しデータ）について順位判定の間違いを犯しやすいということが知られている。従って、従来の評価関数の推定方法で得られた評価関数（図７の暫定評価関数に該当）は、この実施の形態で得られた評価関数に比べ、精度の劣ることが想定できる（考えられる）。
【００６２】
このことは、従来の手法では、数式１（１）に示されているように、部分順位付きデータからわかる順位関係を同一の重みをもつものとして評価関数を推定しているため、上位（高位）の領域（図１１中、右下に近い領域）において主に評価関数が正しくなるような偏ったものを推定してしまうためである。これに対して、この順位付け評価関数推定装置１で得られた評価関数では、下位（低位）の領域に近いデータ（この具体的な動作では、データＣ）について、自動的に大きい重み（ＣＣ＝１．４）をつけることで、暫定評価関数ｇ（ｘ）の偏りを是正し、部分順位付きデータに正しい順位付けを行うと共に、従来の手法に比べ、下位（低位）の領域（図１１中、左下に近い領域）において、より適応性の高い（妥当な）評価関数を得ることができる。
【００６３】
また、この評価関数は、同種のデータに対して、評価関数を用いて順位付けを行う方法と組み合わせて使用することが可能である。このような方法の一つとして、特願２００２−２２３０３２「順位付けのための評価関数推定方法、装置、プログラム及び記憶媒体、並びに、順位付け方法、装置、プログラム及び記憶媒体」が挙げられる。
【００６４】
以上、一実施形態に基づいて本発明を説明したが、本発明はこれに限定されるものではない。
この順位付け評価関数推定装置１の各構成の処理を汎用的なコンピュータ言語で記述した順位付け評価関数推定プログラムとみなすこともできる。この場合、順位付け評価関数推定装置１と同様の効果を得ることができ、また、この順位付け評価関数推定プログラムをコンピュータで読み込み可能な記憶媒体に記憶させて流通させることができる。
【００６５】
【発明の効果】
以上説明したように、この発明では、暫定評価関数を使用して、順位が不明な（不明確な）データ領域（中位、下位位置）に位置するデータほど、大きな重み付けがなされるので、順位が不明なデータ領域（順位が分かっていない領域）でも、部分順位付きデータから、適応性の高い（妥当な）評価関数を推定することができる。
【図面の簡単な説明】
【図１】本発明による一実施の形態である順位付け評価関数推定装置のブロック図である。
【図２】図１に示した順位付け評価関数推定装置の動作を説明したフローチャート（データの流れを主に図示）である。
【図３】図１に示した順位付け評価関数推定装置の動作を説明したフローチャート（処理を主に図示）である。
【図４】部分順位付きデータを示した図である。
【図５】順位無しデータを示した図である。
【図６】評価関数を示した図である。
【図７】暫定評価関数を示した図である。
【図８】暫定評価関数値をソートした結果を示した図である。
【図９】出現確率を示した図である。
【図１０】重み付け部分順位付きデータを示した図である。
【図１１】部分順位付きデータを平面にプロットした図である。
【符号の説明】
１　　　　順位付け評価関数推定装置
３　　　　データ入力手段
５　　　　暫定評価関数算出手段
７　　　　部分順位付きデータ重み付け手段
９　　　　評価関数推定手段
１１　　　評価関数出力手段
【図１】
2004133667.tif 000007
【図２】
2004133667.tif 000008
【図３】
2004133667.tif 000009
【図４】
2004133667.tif 000010
【図５】
2004133667.tif 000011
【図６】
2004133667.tif 000012
【図７】
2004133667.tif 000013
【図８】
2004133667.tif 000014
【図９】
2004133667.tif 000015
【図１０】
2004133667.tif 000016
【図１１】
2004133667.tif 000017