"検索クエリに基づき文書の集合を検索した検索結果をランキングするためのランキング関数に関するパラメータを学習する装置であって、検索クエリに対する検索結果の各文書について求められた特徴値及び前記検索クエリに対する適合度を含む訓練データの集合を記憶した訓練データ記憶手段と、前記ランキング関数に関するパラメータを学習するN個Nは2以上の自然数であるの計算ノードと、前記訓練データ記憶手段に記憶された前記訓練データの集合を、N個の部分集合に分割して前記N個の計算ノードに割り当てる分割手段と、を含み、前記N個の計算ノードの各々は、前記分割手段によって割り当てられた前記訓練データの部分集合に基づいて、前記ランキング関数に関するパラメータであって、かつ、局所的なパラメータを更新する局所更新手段と、前記局所更新手段によって更新された前記局所的なパラメータを、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記局所的なパラメータを取得する同期手段と、前記同期手段によって取得した前記他の計算ノードの前記局所的なパラメータ及び前記局所更新手段によって更新された前記局所的なパラメータに基づいて、前記ランキング関数に関するパラメータであって、かつ、各計算ノードの前記局所的なパラメータを一致させるための大域的なパラメータを更新する大域更新手段と、前記大域的なパラメータの値が収束したか否かを判定し、前記大域的なパラメータの値が収束したと判定するまで、前記局所更新手段による更新、前記同期手段による通知及び取得、並びに前記大域更新手段による更新を繰り返す収束判定手段とを含むランキング関数学習装置。前記局所更新手段は、前記分割手段によって割り当てられた前記訓練データの部分集合と、前回更新されたラグランジュ未定乗数、前記局所的なパラメータ、及び前記大域的なパラメータとを用いて、予め定められた目的関数の値を最適化するように、前記ラグランジュ未定乗数及び前記局所的なパラメータを更新し、前記同期手段は、前記局所更新手段によって更新された前記ラグランジュ未定乗数及び前記局所的なパラメータを、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記ラグランジュ未定乗数及び前記局所的なパラメータを取得し、前記大域更新手段は、前記同期手段によって取得した前記他の計算ノードの前記ラグランジュ未定乗数及び前記局所的なパラメータ、並びに前記局所更新手段によって更新された前記ラグランジュ未定乗数及び前記局所的なパラメータに基づいて、前記目的関数の値を最適化するように、前記大域的なパラメータを更新する請求項1記載のランキング関数学習装置。前記訓練データ記憶手段に前記訓練データの集合が追加された場合に、前記ランキング関数に関するパラメータを学習する追加の計算ノードを更に含み、前記追加の計算ノードは、前記追加された前記訓練データの集合に基づいて、前記局所的なパラメータを更新する局所更新手段と、前記局所更新手段によって更新された前記局所的なパラメータを、他の計算ノードに通知すると共に、前記他の計算ノードから前記局所的なパラメータを取得する同期手段と、前記同期手段によって取得した前記他の計算ノードの前記局所的なパラメータに基づいて、前記大域的なパラメータを更新する大域更新手段と、前記大域的なパラメータの値が収束したか否かを判定し、前記大域的なパラメータの値が収束したと判定するまで、前記局所更新手段による更新、前記同期手段による通知及び取得、並びに前記大域更新手段による更新を繰り返す収束判定手段とを含み、前記計算ノードの各々の同期手段は、前記局所更新手段によって更新された前記局所的なパラメータを、他の計算ノード及び前記追加の計算ノードに通知すると共に、前記他の計算ノード及び前記追加の計算ノードから通知された前記局所的なパラメータを取得する請求項1又は2記載のランキング関数学習装置。検索クエリに基づき文書の集合を検索した検索結果をランキングするためのランキング関数に関するパラメータを学習する装置であって、検索クエリに対する検索結果の各文書について求められた特徴値及び前記検索クエリに対する適合度を含む訓練データの集合を記憶した訓練データ記憶手段と、前記ランキング関数に関するパラメータを学習するN個Nは2以上の自然数であるの計算ノードと、前記訓練データ記憶手段に記憶された前記訓練データの集合を、N個の部分集合に分割して前記N個の計算ノードに割り当てる分割手段と、大域更新手段と、収束判定手段とを含み、前記N個の計算ノードの各々は、前記分割手段によって割り当てられた前記訓練データの部分集合に基づいて、前記ランキング関数に関するパラメータであって、かつ、局所的なパラメータを更新する局所更新手段を含み、前記大域更新手段は、前記全ての計算ノードの前記局所更新手段によって更新された前記局所的なパラメータに基づいて、前記ランキング関数に関するパラメータであって、かつ、各計算ノードの前記局所的なパラメータを一致させるための大域的なパラメータを更新する手段であり、前記収束判定手段は、前記大域的なパラメータの値が収束したか否かを判定し、前記大域的なパラメータの値が収束したと判定するまで、各計算ノードの前記局所更新手段による更新及び前記大域更新手段による更新を繰り返す手段であることを特徴とするランキング関数学習装置。検索クエリに対する検索結果の各文書について求められた特徴値及び前記検索クエリに対する適合度を含む訓練データの集合を記憶した訓練データ記憶手段と、N個Nは2以上の自然数であるの計算ノードと、分割手段とを含む、検索クエリに基づき文書の集合を検索した検索結果をランキングするためのランキング関数に関するパラメータを学習する装置におけるランキング関数学習方法であって、前記分割手段によって、前記訓練データ記憶手段に記憶された前記訓練データの集合を、N個の部分集合に分割して前記N個の計算ノードに割り当てるステップと、前記N個の計算ノードの各々によって、前記ランキング関数に関するパラメータを学習するステップとを含み、前記計算ノードによって学習するステップは、局所更新手段によって、前記分割手段によって割り当てられた前記訓練データの部分集合に基づいて、前記ランキング関数に関するパラメータであって、かつ、局所的なパラメータを更新するステップと、同期手段によって、前記局所更新手段によって更新された前記局所的なパラメータを、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記局所的なパラメータを取得するステップと、大域更新手段によって、前記同期手段によって取得した前記他の計算ノードの前記局所的なパラメータ及び前記局所更新手段によって更新された前記局所的なパラメータに基づいて、前記ランキング関数に関するパラメータであって、かつ、各計算ノードの前記局所的なパラメータを一致させるための大域的なパラメータを更新するステップと、収束判定手段によって、前記大域的なパラメータの値が収束したか否かを判定し、前記大域的なパラメータの値が収束したと判定するまで、前記局所更新手段による更新、前記同期手段による通知及び取得、並びに前記大域更新手段による更新を繰り返すステップとを含むランキング関数学習方法。前記局所更新手段によって更新するステップは、前記分割手段によって割り当てられた前記訓練データの部分集合と、前回更新されたラグランジュ未定乗数、前記局所的なパラメータ、及び前記大域的なパラメータとを用いて、予め定められた目的関数の値を最適化するように、前記ラグランジュ未定乗数及び前記局所的なパラメータを更新し、前記同期手段によって通知及び取得するステップは、前記局所更新手段によって更新された前記ラグランジュ未定乗数及び前記局所的なパラメータを、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記ラグランジュ未定乗数及び前記局所的なパラメータを取得し、前記大域更新手段によって更新するステップは、前記同期手段によって取得した前記他の計算ノードの前記ラグランジュ未定乗数及び前記局所的なパラメータ、並びに前記局所更新手段によって更新された前記ラグランジュ未定乗数及び前記局所的なパラメータに基づいて、前記目的関数の値を最適化するように、前記大域的なパラメータを更新する請求項5記載のランキング関数学習方法。追加の計算ノードによって、前記訓練データ記憶手段に前記訓練データの集合が追加された場合に、前記ランキング関数に関するパラメータを学習するステップを更に含み、前記追加の計算ノードによって学習するステップは、局所更新手段によって、前記追加された前記訓練データの集合に基づいて、前記局所的なパラメータを更新するステップと、同期手段によって、前記局所更新手段によって更新された前記局所的なパラメータを、他の計算ノードに通知すると共に、前記他の計算ノードから前記局所的なパラメータを取得するステップと、大域更新手段によって、前記同期手段によって取得した前記他の計算ノードの前記局所的なパラメータに基づいて、前記大域的なパラメータを更新するステップと、収束判定手段によって、前記大域的なパラメータの値が収束したか否かを判定し、前記大域的なパラメータの値が収束したと判定するまで、前記局所更新手段による更新、前記同期手段による通知及び取得、並びに前記大域更新手段による更新を繰り返すステップとを含み、前記計算ノードの各々の同期手段によって通知及び取得するステップは、前記局所更新手段によって更新された前記局所的なパラメータを、他の計算ノード及び前記追加の計算ノードに通知すると共に、前記他の計算ノード及び前記追加の計算ノードから通知された前記局所的なパラメータを取得する請求項5又は6記載のランキング関数学習方法。検索クエリに対する検索結果の各文書について求められた特徴値及び前記検索クエリに対する適合度を含む訓練データの集合を記憶した訓練データ記憶手段と、N個Nは2以上の自然数であるの計算ノードと、分割手段と、大域更新手段と、収束判定手段とを含む、検索クエリに基づき文書の集合を検索した検索結果をランキングするためのランキング関数に関するパラメータを学習する装置におけるランキング関数学習方法であって、前記分割手段によって、前記訓練データ記憶手段に記憶された前記訓練データの集合を、N個の部分集合に分割して前記N個の計算ノードに割り当てるステップと、前記N個の計算ノードの各々によって、前記ランキング関数に関するパラメータを学習するステップと、前記大域更新手段によって更新するステップと、前記収束判定手段によって判定するステップと、を含み、前記計算ノードによって学習するステップは、局所更新手段によって、前記分割手段によって割り当てられた前記訓練データの部分集合に基づいて、前記ランキング関数に関するパラメータであって、かつ、局所的なパラメータを更新するステップを含み、前記大域更新手段によって更新するステップは、前記全ての計算ノードの前記局所更新手段によって更新された前記局所的なパラメータに基づいて、前記ランキング関数に関するパラメータであって、かつ、各計算ノードの前記局所的なパラメータを一致させるための大域的なパラメータを更新するステップであり、前記収束判定手段によって判定するステップは、前記大域的なパラメータの値が収束したか否かを判定し、前記大域的なパラメータの値が収束したと判定するまで、各計算ノードの前記局所更新手段による更新及び前記大域更新手段による更新を繰り返すステップであることを特徴とするランキング関数学習方法。コンピュータを、請求項1~請求項4の何れか1項記載のランキング関数学習装置の各手段として機能させるためのプログラム。しかしながら、上記の非特許文献2~4で使われている方法は、単純な結合方法であるため、訓練データ全体を用いて構築したランキング関数より精度が落ちることがほとんどである。つまり、分散処理により高速化はできているが、精度を犠牲にしている面がある。本発明は、上記の事情を鑑みてなされたもので、ランキング精度の低下を抑制して、高速にランキング関数を学習することができるランキング関数学習装置、方法、及びプログラムを提供することを目的とする。上記の目的を達成するために第1の発明に係るランキング関数学習装置は、検索クエリに基づき文書の集合を検索した検索結果をランキングするためのランキング関数に関するパラメータを学習する装置であって、検索クエリに対する検索結果の各文書について求められた特徴値及び前記検索クエリに対する適合度を含む訓練データの集合を記憶した訓練データ記憶手段と、前記ランキング関数に関するパラメータを学習するN個Nは2以上の自然数であるの計算ノードと、前記訓練データ記憶手段に記憶された前記訓練データの集合を、N個の部分集合に分割して前記N個の計算ノードに割り当てる分割手段と、を含み、前記N個の計算ノードの各々は、前記分割手段によって割り当てられた前記訓練データの部分集合に基づいて、前記ランキング関数に関するパラメータであって、かつ、局所的なパラメータを更新する局所更新手段と、前記局所更新手段によって更新された前記局所的なパラメータを、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記局所的なパラメータを取得する同期手段と、前記同期手段によって取得した前記他の計算ノードの前記局所的なパラメータ及び前記局所更新手段によって更新された前記局所的なパラメータに基づいて、前記ランキング関数に関するパラメータであって、かつ、各計算ノードの前記局所的なパラメータを一致させるための大域的なパラメータを更新する大域更新手段と、前記大域的なパラメータの値が収束したか否かを判定し、前記大域的なパラメータの値が収束したと判定するまで、前記局所更新手段による更新、前記同期手段による通知及び取得、並びに前記大域更新手段による更新を繰り返す収束判定手段とを含んで構成されている。第2の発明に係るランキング関数学習方法は、検索クエリに対する検索結果の各文書について求められた特徴値及び前記検索クエリに対する適合度を含む訓練データの集合を記憶した訓練データ記憶手段と、N個Nは2以上の自然数であるの計算ノードと、分割手段とを含む、検索クエリに基づき文書の集合を検索した検索結果をランキングするためのランキング関数に関するパラメータを学習する装置におけるランキング関数学習方法であって、前記分割手段によって、前記訓練データ記憶手段に記憶された前記訓練データの集合を、N個の部分集合に分割して前記N個の計算ノードに割り当てるステップと、前記N個の計算ノードの各々によって、前記ランキング関数に関するパラメータを学習するステップとを含み、前記計算ノードによって学習するステップは、局所更新手段によって、前記分割手段によって割り当てられた前記訓練データの部分集合に基づいて、前記ランキング関数に関するパラメータであって、かつ、局所的なパラメータを更新するステップと、同期手段によって、前記局所更新手段によって更新された前記局所的なパラメータを、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記局所的なパラメータを取得するステップと、大域更新手段によって、前記同期手段によって取得した前記他の計算ノードの前記局所的なパラメータ及び前記局所更新手段によって更新された前記局所的なパラメータに基づいて、前記ランキング関数に関するパラメータであって、かつ、各計算ノードの前記局所的なパラメータを一致させるための大域的なパラメータを更新するステップと、収束判定手段によって、前記大域的なパラメータの値が収束したか否かを判定し、前記大域的なパラメータの値が収束したと判定するまで、前記局所更新手段による更新、前記同期手段による通知及び取得、並びに前記大域更新手段による更新を繰り返すステップとを含む。第1の発明及び第2の発明によれば、前記分割手段によって、前記訓練データ記憶手段に記憶された前記訓練データの集合を、N個の部分集合に分割して前記N個の計算ノードに割り当てる。前記N個の計算ノードの各々によって、前記ランキング関数に関するパラメータを学習する。このとき、各計算ノードでは、局所更新手段によって、前記分割手段によって割り当てられた前記訓練データの部分集合に基づいて、前記ランキング関数に関するパラメータであって、かつ、局所的なパラメータを更新する。同期手段によって、前記局所更新手段によって更新された前記局所的なパラメータを、他の計算ノードに通知すると共に、前記他の計算ノードから通知された前記局所的なパラメータを取得する。大域更新手段によって、前記同期手段によって取得した前記他の計算ノードの前記局所的なパラメータ及び前記局所更新手段によって更新された前記局所的なパラメータに基づいて、前記ランキング関数に関するパラメータであって、かつ、各計算ノードの前記局所的なパラメータを一致させるための大域的なパラメータを更新する。収束判定手段によって、前記大域的なパラメータの値が収束したか否かを判定し、前記大域的なパラメータの値が収束したと判定するまで、前記局所更新手段による更新、前記同期手段による通知及び取得、並びに前記大域更新手段による更新を繰り返す。このように、各計算ノードにおいて、割り当てられた訓練データの部分集合に基づいて局所的なパラメータを更新し、他の計算ノードから取得した局所的なパラメータを用いて、大域的なパラメータを更新することを収束するまで繰り返すことにより、ランキング精度の低下を抑制して、高速にランキング関数を学習することができる。第3の発明に係るランキング関数学習装置は、検索クエリに基づき文書の集合を検索した検索結果をランキングするためのランキング関数に関するパラメータを学習する装置であって、検索クエリに対する検索結果の各文書について求められた特徴値及び前記検索クエリに対する適合度を含む訓練データの集合を記憶した訓練データ記憶手段と、前記ランキング関数に関するパラメータを学習するN個Nは2以上の自然数であるの計算ノードと、前記訓練データ記憶手段に記憶された前記訓練データの集合を、N個の部分集合に分割して前記N個の計算ノードに割り当てる分割手段と、大域更新手段と、収束判定手段とを含み、前記N個の計算ノードの各々は、前記分割手段によって割り当てられた前記訓練データの部分集合に基づいて、前記ランキング関数に関するパラメータであって、かつ、局所的なパラメータを更新する局所更新手段を含み、前記大域更新手段は、前記全ての計算ノードの前記局所更新手段によって更新された前記局所的なパラメータに基づいて、前記ランキング関数に関するパラメータであって、かつ、各計算ノードの前記局所的なパラメータを一致させるための大域的なパラメータを更新する手段であり、前記収束判定手段は、前記大域的なパラメータの値が収束したか否かを判定し、前記大域的なパラメータの値が収束したと判定するまで、各計算ノードの前記局所更新手段による更新及び前記大域更新手段による更新を繰り返す手段であることを特徴とする。第4の発明に係るランキング関数学習方法は、検索クエリに対する検索結果の各文書について求められた特徴値及び前記検索クエリに対する適合度を含む訓練データの集合を記憶した訓練データ記憶手段と、N個Nは2以上の自然数であるの計算ノードと、分割手段と、大域更新手段と、収束判定手段とを含む、検索クエリに基づき文書の集合を検索した検索結果をランキングするためのランキング関数に関するパラメータを学習する装置におけるランキング関数学習方法であって、前記分割手段によって、前記訓練データ記憶手段に記憶された前記訓練データの集合を、N個の部分集合に分割して前記N個の計算ノードに割り当てるステップと、前記N個の計算ノードの各々によって、前記ランキング関数に関するパラメータを学習するステップと、前記大域更新手段によって更新するステップと、前記収束判定手段によって判定するステップと、を含み、前記計算ノードによって学習するステップは、局所更新手段によって、前記分割手段によって割り当てられた前記訓練データの部分集合に基づいて、前記ランキング関数に関するパラメータであって、かつ、局所的なパラメータを更新するステップを含み、前記大域更新手段によって更新するステップは、前記全ての計算ノードの前記局所更新手段によって更新された前記局所的なパラメータに基づいて、前記ランキング関数に関するパラメータであって、かつ、各計算ノードの前記局所的なパラメータを一致させるための大域的なパラメータを更新するステップであり、前記収束判定手段によって判定するステップは、前記大域的なパラメータの値が収束したか否かを判定し、前記大域的なパラメータの値が収束したと判定するまで、各計算ノードの前記局所更新手段による更新及び前記大域更新手段による更新を繰り返すステップであることを特徴とする。第5の発明に係るプログラムは、コンピュータを、上記のランキング関数学習装置の各手段として機能させるためのプログラムである。以上説明したように、本発明のランキング関数学習装置、方法、及びプログラムによれば、各計算ノードにおいて、割り当てられた訓練データの部分集合に基づいて局所的なパラメータを更新し、他の計算ノードから取得した局所的なパラメータを用いて、大域的なパラメータを更新することを収束するまで繰り返すことにより、ランキング精度の低下を抑制して、高速にランキング関数を学習することができる、という効果が得られる。以下、図面を参照して本発明の実施の形態を詳細に説明する。第1の実施の形態<発明の概要>本発明の処理の枠組は、基本的に分散計算環境を想定する。ここでは、図1に示すように、N個の計算ノードがあるとする。つぎに、M個の訓練データをN個に分割する。この時、分割した訓練データのn番目の部分集合をMnと書く。また、各部分集合は重複するデータを持たないと仮定する。つまり、∪nMn,∩nMn空集合である。訓練データの集合を分割し、各計算ノードに割り当てた後、各計算ノードは、自分自身に割り当てられた訓練データのみを用い、上記1式に示した従来法等を用いてランキング関数を学習する。このとき、n番目の計算ノードで得られるランキング関数で用いられるパラメータをvnとする。このvnは上記1式中のwに相当する。本発明の枠組では、各計算ノードは独立にランキング関数で用いるパラメータを学習することができるため、単純計算で学習時間を1Nに縮減できるという計算量的な利点がある。ただし、vnは部分的な訓練データのみから生成されるため、部分的な情報しか用いることができないという観点で、基本的に訓練データ全体を使って学習したwを用いたランキング関数よりランキング精度は一般的に低くなる、という問題がある。また、独立に得られたvnから最良のvnを選択する方法、或いは、効果的にvnを結合する方法などはこれまで知られていない。本発明では、各計算ノードで得られたvnは一致しなくてはいけないという制約パラメータwを導入する。この制約を入れることで、部分的なデータのみから生成されるvnは全体で一致しなくてはいけなくなるため、間接的に訓練データ全体の情報を包含した関数を学習することが可能となる。つまり、訓練データ集合を分割することで、ランキング関数の学習時間を短縮する性質を保持したまま、従来と同様に全体の訓練データを使って学習したランキング関数と同じようにランキング精度の高い関数を学習することが可能となる。また、分散計算環境を用いれば訓練データが増えても容易に扱えることから、従来では利用できなかった量の訓練データを用いてランキング関数を構築することができるようになるため、より高精度なランキング関数を学習することが可能となる。本発明の枠組では、ランキング関数に用いるパラメータwは、以下の3式で示す最適化式を解くことで得られる。本発明では、参考文献1DanielGabayandBertrandMercierAdualalgorithmforthesolutionofnonlinearvariationalproblemsviafiniteelementapproximationComputersandMathematicswithApplications217401976及び参考文献2StephenBoydNealParikhEricChuBorjaPeleatoandJonathanEcksteinDistributedoptimizationandstatisticallearningviathealternatingdirectionmethodofmultipliersFoundationsandTrendsinMachineLearning2011に記載されたalternatingdirectionmethodofmultipliersと呼ばれる最適化の枠組を用いて上記最適化問題を解く。まず、ADMMの枠組に則って上記3式の最適化式を変形し、以下の4式に示す目的関数Lρを得る。ここで、μnは、上記4式の制約をラグランジュ未定乗数法で表現した際のラグランジュ乗数に相当し、ρ2vn-w2は最適化の解を効率的に求めるための追加の項である。ρは人手により決定するパラメータでρ0とする。上記参考文献2に従って、unμnρで上式を置き換える。その結果、上記4式は、以下の5式に変形される。上記5式を用いることで、実際の最適化問題は、vn,w,unを順番に繰り返し求めることで最適解が得られることが保証されている。また、後述する第2の実施の形態のように、訓練データが逐次的に増加しても、つまり、計算ノードの個数が増加しても、最終的な最適解wが得られることが参考文献3PedroForeroAlfonsoCanoandGeorgiosGiannakisConsensusbaseddistributedsupportvectormachinesJMLR2010により保証される。これらの性質を利用することで、分散処理かつデータの逐次投入によるランキング関数学習処理を行うことが可能となる。<システム構成>本発明の第1の実施の形態に係るランキング関数学習装置100は、学習用として与えられた訓練データを入力として受け取り、ランキング関数に関するパラメータを出力する。このランキング関数学習装置100は、CPUと、RAMと、後述するランキング関数学習処理ルーチンを実行するためのプログラムを記憶したROMとを備えたコンピュータで構成され、機能的には次に示すように構成されている。図2に示すように、ランキング関数学習装置100は、入力部10と、演算部20と、出力部30とを備えている。入力部10は、入力された訓練データとして、上記図14で示した文書のペアによる訓練データを複数受け付ける。各訓練データは、ある検索クエリに対する検索結果文書ペアの複数の特徴値の各々の差分からなる差分ベクトルと、当該検索クエリに対する適合度の大小関係を示す変数とを含む。また、入力される訓練データには、様々な検索クエリに基づく訓練データが含まれる。また、入力部10は、人手により入力された計算ノード数Nとパラメータρを受け付ける。演算部20は、訓練データ記憶部21、分割部22、及びN個の計算ノード231~23Nを備えている。なお、計算ノード231~23Nのうちの任意の計算ノードを示す場合には、計算ノード23と称することとする。訓練データ記憶部21は、入力部10により受け付けた大量の訓練データからなる訓練データ集合を記憶する。訓練データ記憶部21のデータ構造は、上記図14に示す。上記図14に示すように、それぞれの行が、ある検索クエリに対する検索結果文書のペアの文書IDと、ペアにした文書で便宜上左側の文書の適合度が高いときに1、右の文書が高いときに-1となる変数ymと、各文書を各特徴ベクトル表現にしたものの差分ベクトルxmとを表している。分割部22は、訓練データ記憶部21に記憶された訓練データ集合を、N個の部分集合に分割し、N個の計算ノード231~23Nに割り当てる。また、分割部22は、入力されたパラメータρを、N個の計算ノード231~23Nの各々に通知する。N個の計算ノード231~23Nの各々は、分割データ記憶部31、局所更新部32、同期部33、大域更新部34、及び収束判定部35を備えている。各N個の分割データ記憶部31、局所更新部32、同期部33、大域更新部34、及び収束判定部35が存在することになるが、同様の機能を有す処理部は同じ番号で表わしている。分割データ記憶部31には、計算ノード23に割り当てられた訓練データ集合の部分集合を記憶する。局所更新部32は、分割データ記憶部31に記憶された訓練データ集合の部分集合を用いて、以下に説明するように、ラグランジュ未定乗数un及び局所的なパラメータvnを更新する。ラグランジュ未定乗数unの更新最初の処理として、局所更新部32は、当該計算ノード23nにおけるラグランジュ未定乗数unを更新する。wとvnを固定したときunの最適値の方向は、以下の6式に示すように、上記5式に示す目的関数Lρのunに関する勾配方向である。上記6式の関係から、以下の7式に示す更新式を得る。局所更新部32は、上記7式に従って、ラグランジュ未定乗数unを更新する。上記7式の更新式は、各計算ノード23で独立に計算できるため、他の計算ノード23と通信などを行う必要がない。局所的なパラメータvnの更新次に、局所更新部32は、当該計算ノード23nにおける局所的なパラメータvnを更新する。反復計算kkは繰り返し回数を管理する変数の時点で、unとwを固定したとき各vnの最適解は、以下の8式に示すように、上記5式に示す目的関数Lρを最小にするvnを見つける問題である。定義に従って、局所的なパラメータvnに関係する項のみを取り出すと、以下の9式が得られる。上記9式は、従来法で示したRankSVMにバイアス項を追加したモデルとみなせる。また、バイアス項は、ここでは定数となるので、従来法のRankSVMと同じ方法で解くことができる。また、もし0なら、RankSVMの式と一致する。つまり、ここの計算ノードでは、あたえられた訓練データの部分集合を使って独立に従来法のRankSVMを用いてパラメータvnを生成することと等価である。局所更新部32は、上記9式に従って、局所的なパラメータvnを更新する。また、パラメータvnも、unと同様に、各計算ノード23で独立に更新することができる。同期部33は、当該計算ノード23で今回更新されたunとvnを、自分以外の全ての計算ノード23iへ通知する。また、同期部33は、他の計算ノード23i全てから通知された、今回更新されたuiとviを受け取る。この処理によって、個々の計算ノード23は全ての計算ノード23nの持つunとvnの値を取得することができる。大域更新部34は、他の計算ノード23n全てから受け取ったunとvnを使って、以下のように、大域的制約パラメータwを更新する。unとvnを固定したときwの最適解は、上記5式に示す目的関数Lρのwに関する勾配が零ベクトルになる点である。その関係から以下の10式~13式に示す関係式が得られる。ただし、 ̄vΣNn1vnN, ̄uΣNn1unNである。上記13式に示す関係式から、反復計算kの時点でのwは以下の14式で求められる。大域的制約パラメータwの更新には、全てのvnとunが必要である。そこで,大域更新部34は、取得した全ての計算ノード23nの持つunとvnの値を用いて、上記14式に従って、大域的制約パラメータwを更新する。個々の計算ノード23で独立にwを求める。ここでの注意点として、個々の計算ノード23は独立でwを求めるが、得られるwは全ての計算ノード23で一致する。処理方法としては、任意のひとつの計算ノード23でwを計算し、その後に各計算ノード23に通知するといった処理を行うようにしてもよい。ただし、その場合には、選択された計算ノード23の計算が終了し、結果が通知されるまで、それ以外の計算ノードは待機する必要がある。本実施の形態では、個々の計算ノード23で同じ計算を行う方式をとった場合を例に説明する。収束判定部35は、得られた大域的制約パラメータwが収束して最適値になっているか判定する。二つの小さな正の実数ε1、ε2をあたえ、以下の15式、16式を満たした際に収束したと判定する参考文献2を参照。収束判定で、収束していなかった場合は、kk1として、局所更新部32による処理に戻る。収束していると判定された場合は、繰り返し処理を終了する。この収束判定の処理もwと同様に任意のひとつの計算ノード23で行い、その結果を全体に通知するようにしてもよい。しかし、同期処理が必要となるため、本実施の形態では、収束判定も全ての計算ノード23で個別に行い、収束と判定されれば処理を終了する場合を例に説明する。この収束判定も、全ての計算ノードで結果が必ず一致するため、個々に判定をおこなっても結果は同じになる。収束判定部35は、収束したと判定されたときに得られた大域的制約パラメータwを、ランキング関数を構成するパラメータとして出力部30により出力する。なお、本実施の形態では、任意の一つの計算ノード23から、大域的制約パラメータwが出力される場合を例に説明したが、全ての計算ノード23から、大域的制約パラメータwが出力されてもよい。また、実際のランキングを生成する際には、従来法と同様に上記2式を用いて検索スコアを計算する。<ランキング関数学習装置の作用>次に、本実施の形態に係るランキング関数学習装置100の作用について説明する。まず、大量の訓練データからなる訓練データ集合がランキング関数学習装置100に入力されると、ランキング関数学習装置100によって、入力された訓練データ集合が、訓練データ記憶部21へ格納される。そして、ランキング関数学習装置100において、分割部22によって、訓練データ記憶部21の訓練データ集合を、N個の部分集合に分割し、N個の計算ノード231~23Nに割り当てる。訓練データ集合の各部分集合が、計算ノード231~23Nの各々の分割データ記憶部31に格納される。そして、ランキング関数学習装置100の各計算ノード23によって、図3に示すランキング関数学習処理ルーチンが実行される。なお、以下では、計算ノード23nによって実行した場合について説明する。まず、ステップS101において、ラグランジュ未定乗数un、局所的なパラメータvn、及び大域的制約パラメータwの各々に、適当な値例えば、0を与えて初期化する。そして、ステップS102において、局所更新部32によって、上記ステップS101で初期化されたラグランジュ未定乗数un、局所的なパラメータvn、及び大域的制約パラメータw、又は前回更新されたラグランジュ未定乗数un、局所的なパラメータvn、及び大域的制約パラメータwに基づいて、上記7式に従って、ラグランジュ未定乗数unを更新する。次のステップS103では、局所更新部32によって、上記ステップ102で更新されたラグランジュ未定乗数unと、上記ステップS101で初期化された大域的制約パラメータw、又は前回更新された大域的制約パラメータwと、分割データ記憶部31に記憶された訓練データ集合の部分集合とに基づいて、上記9式に従って、局所的なパラメータvnを更新する。そして、ステップS104では、同期部33によって、上記ステップS102で更新されたラグランジュ未定乗数un及び上記ステップ103で更新された局所的なパラメータvnを他の計算ノード23に通知すると共に、他の計算ノード23i全てから、更新されたラグランジュ未定乗数ui及び上記ステップ103で更新された局所的なパラメータviを取得するi=1n-1,n1,N。ステップS105では、大域更新部34によって、上記ステップS102で更新されたラグランジュ未定乗数un及び上記ステップ103で更新された局所的なパラメータvnと、上記ステップS104で他の計算ノード23i全てから取得したラグランジュ未定乗数uiび局所的なパラメータviとに基づいて、上記14式に従って、大域的制約パラメータwを更新する。次のステップS106では、上記ステップ103で更新された局所的なパラメータvnと、上記ステップ105で更新された大域的制約パラメータwと、前回更新された大域的制約パラメータwとに基づいて、上記15式、式に従って、大域的制約パラメータwが収束したか否かを判定する。上記15式および式を満たさない場合には、収束していないと判断し、上記ステップS102へ戻る。一方、上記15式及びの計算ノード223N1、223N2を備える。なお、計算ノード223N1、223N2のうちの任意の計算ノードを示す場合には、計算ノード223と称することとする。データ追加部222は、ある時点までで訓練データ集合が追加された場合に、訓練データ集合の追加分を、計算ノード223N1に割り当てる。また、次の時点までで訓練データ集合が更に追加された場合には、データ追加部222は、訓練データ集合の更なる追加分を、計算ノード223N2に割り当てる。計算ノード223N1~223N2の各々は、追加データ記憶部231、局所更新部32、同期部33、大域更新部34、及び収束判定部35を備えている。追加データ記憶部231には、計算ノード223に割り当てられた、追加分の訓練データ集合を記憶する。計算ノード223の局所更新部32及び収束判定部35は、計算ノード23と同様である。計算ノード223の同期部33は、当該計算ノード223nで今回更新されたunとvnを、自分以外の全ての計算ノード23、223へ通知する。また、計算ノード23の同期部33も、当該計算ノード23iで今回更新されたuiとviを、自分以外の全ての計算ノード23、223へ通知する。計算ノード23、223の各々の同期部33は、他の計算ノード23、223全てから通知された、今回更新されたunとvnを受け取る。この処理によって、個々の計算ノード23、223は全ての計算ノード23、223の持つunとvnの値を取得することができる。計算ノード23、223の各々の大域更新部34は、他の計算ノード23、223全てから受け取ったunとvnを使って、上記14式に従って、大域的制約パラメータwを更新する。<ランキング関数学習装置の作用>次に、本実施の形態に係るランキング関数学習装置200の作用について説明する。まず、大量の訓練データからなる訓練データ集合がランキング関数学習装置200に入力されると、ランキング関数学習装置200によって、入力された訓練データ集合が、訓練データ記憶部21へ格納される。そして、ランキング関数学習装置200において、分割部22によって、訓練データ記憶部21の訓練データ集合を、N個の部分集合に分割し、N個の計算ノード231~23Nに割り当てる。そして、ランキング関数学習装置200の各計算ノード23によって、上記図3に示すランキング関数学習処理ルーチンが実行される。各計算ノード23によるランキング関数学習処理ルーチンの実行中に、訓練データ集合がランキング関数学習装置200に追加入力されると、ランキング関数学習装置200によって、追加入力された訓練データ集合が、訓練データ記憶部21へ格納される。そして、ランキング関数学習装置200において、データ追加部222によって、訓練データ記憶部21の訓練データ集合の追加分を、計算ノード223N1に割り当てる。ランキング関数学習装置200の計算ノード223N1によって、各計算ノード23と同様に、ランキング関数学習処理ルーチンが実行される。このとき、各計算ノード23、223で実行されるランキング関数学習処理ルーチンのステップS104では、更新されたラグランジュ未定乗数ui及び局所的なパラメータviを他の計算ノード23、223に通知すると共に、他の計算ノード23、223全てから、更新されたラグランジュ未定乗数ui及び上記ステップ103で更新された局所的なパラメータviを取得する。また、各計算ノード23、223N1によるランキング関数学習処理ルーチンの実行中に、訓練データ集合がランキング関数学習装置200に追加入力されると、ランキング関数学習装置200によって、追加入力された訓練データ集合が、訓練データ記憶部21へ格納される。データ追加部222によって、訓練データ記憶部21の訓練データ集合の更なる追加分を、計算ノード223N2に割り当てる。ランキング関数学習装置200の計算ノード223N2によって、各計算ノード23と同様に、ランキング関数学習処理ルーチンが実行される。また、訓練データ集合が追加入力される毎に、計算ノード223N3223N4と計算ノード223を追加し、訓練データ集合の更なる追加分を割り当て、ランキング関数学習処理ルーチンを同様に実行させる。以上説明したように、第2の実施の形態に係るランキング関数学習装置によれば、ランキング処理装置で利用するランキング関数を学習する際に、訓練データの大規模化と逐次投入化を同時に可能とする。これにより、従来扱えなかった大量の訓練データを用いて従来より高精度なランキング関数を構築することが可能となる。また、逐次的に訓練データを増加させながら、ランキング関数の構築が可能となるため、時々刻々と変化するデータに対応してランキング関数を適応させることが容易となる。また、検索のランキング関数学習処理においては、実際にユーザが入力した検索クエリとユーザがクリックしたWebページが、擬似的な訓練データとして利用可能である。これらのいわゆるユーザフィードバックを逐次的に取り入れてランキング関数の性能を向上させることが可能となる。なお、上記の実施の形態では、訓練データの追加前から実行されているランキング関数学習処理ルーチンを、計算ノードが実行している間に、訓練データが追加される場合を例に説明したが、これに限定されるものではない。N個の計算ノードによって、ランキング関数学習処理ルーチンの実行が終了した後に、訓練データが追加された場合であってもよい。この場合には、訓練データの追加前に実行完了したランキング関数学習処理ルーチンで最終的に得られた各種変数u,v,wの値を保持しておき、保持した値を、各種変数の初期値として設定して、追加された計算ノードを含む複数の計算ノードの各々によって、ランキング関数学習処理ルーチンを実行するようにすればよい。これによって、訓練データが追加される前に学習した結果を有効利用することができる。第3の実施の形態次に、第3の実施の形態について説明する。なお、第1の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。第3の実施の形態では、ネットワークで接続された複数の学習装置を備えた分散並列計算環境において、複数の学習装置による分散並列計算で、パラメータ更新を行っている点が、第1の実施の形態と異なっている。<システム構成>図7に示すように、第3の実施の形態に係るランキング関数学習システム300は、学習制御装置301、及びN個の学習装置3021~302Nを備えている。学習制御装置301及びN個の学習装置3021~302Nは、ネットワーク303を介して接続されている。なお、学習装置3021~302Nのうちの任意の学習装置を示す場合には、学習装置302と称することとする。図8に示すように、学習制御装置301は、入力部10、演算部320、及び出力部330を備えている。演算部320は、訓練データ記憶部21及び分割部22を備えている。分割部22は、訓練データ記憶部21に記憶された訓練データ集合を、N個の部分集合に分割し、ネットワーク303を介してN個の学習装置3021~302Nに送信する。また、分割部22は、入力されたパラメータρを、ネットワーク303を介してN個の学習装置3021~302Nの各々に送信する。N個の学習装置3021~302Nの各々は、図9に示すように、入力部340、演算部350、及び出力部360を備えている。入力部340は、学習制御装置301から送信された訓練データ集合の部分集合を受け付ける。また、入力部340は、他の学習装置302からネットワーク303を介して送信された情報を受け付ける。演算部350は、分割データ記憶部31、局所更新部32、同期部33、大域更新部34、及び収束判定部35を備えている。分割データ記憶部31には、学習装置302に送信された訓練データ集合の部分集合を記憶する。同期部33は、当該学習装置302nで今回更新されたunとvnを、自分以外の全ての学習装置302へネットワーク303を介して送信する。また、同期部33は、他の学習装置302i全てから送信された、今回更新されたuiとviを受け取る。この処理によって、個々の学習装置302は全ての学習装置302nの持つunとvnの値を取得することができる。大域更新部34は、他の学習装置302i全てから受け取ったuiとviを使って、上記14式に従って、大域的制約パラメータwを更新する。収束判定部35は、得られた大域的制約パラメータwが収束して最適値になっているか判定し、収束したと判定されたときに得られた大域的制約パラメータwを、ランキング関数を構成するパラメータとして、出力部360により学習制御装置301へ送信する。<ランキング関数学習システムの作用>次に、本実施の形態に係るランキング関数学習システム300の作用について説明する。まず、大量の訓練データからなる訓練データ集合が学習制御装置301に入力されると、学習制御装置301によって、入力された訓練データ集合が、訓練データ記憶部21へ格納される。そして、学習制御装置301において、分割部22によって、訓練データ記憶部21の訓練データ集合を、N個の部分集合に分割し、ネットワーク303を介してN個の学習装置302へ送信して、N個の学習装置302に割り当てる。訓練データ集合の部分集合が、学習装置3021~302Nの分割データ記憶部31に格納される。そして、各学習装置302によって、上記図3に示すランキング関数学習処理ルーチンが実行される。少なくとも1つの学習装置302によって、最終的に更新された大域的制約パラメータwが、ネットワーク303を介して学習制御装置301へ送信される。学習制御装置301は、学習装置302により受信した大域的制約パラメータwを出力部330により出力する。以上説明したように、第3の実施の形態に係るランキング関数学習システムによれば、ネットワークを介して接続された複数の学習装置によって、分散並列処理によるランキング関数学習処理を行うため、処理を高速化でき、訓練データの更なる大規模化に対応することができる。なお、上記の実施の形態において、上述した第2の実施の形態における訓練データの逐次追加に対応する技術を適用してもよい。この場合には、訓練データが追加される毎に、ランキング学習処理を行う学習装置を増やして対応すればよい。<実験例>次に、本発明の実施の形態で提案するランキング関数学習方法を用いた実験の結果について説明する。訓練データ集合が静的な場合と、逐次的に訓練データが追加される場合とについて、それぞれ実験を行った。また、比較手法として、参考文献3RyanMcDonaldKeithHallandGideonMannDistributedtrainingstrategiesforthestructuredperceptronInNAACLHLT2010に記載の方法を用いた。図10に実験結果を示す。図10のグラフの縦軸は精度であり、横軸は学習処理中の繰り返し回数である。また、Batchとは、全訓練データをはじめから利用した場合の実験結果を表わし、Streamとは、逐次的に訓練データを投入した場青の実験結果を表わす。また、BatchADMM及びStreamADMMが、本発明の実施の形態で提案するランキング関数学習方法提案手法の実験結果を表わし、BatchIterParamMix及びStreamIterParamMixが、比較手法を用いた場合の実験結果を表わす。本発明の実施の形態で提案するランキング関数学習方法を用いた場合には、従来方法より、精度が高くなることがわかった。また、逐次的に投入しても、全訓練データをはじめから使っているときとほぼ同じ解が得られることがわかった。また、分散並列処理を行う方法を用いた実験を行った。学習処理を行う計算機の数を、1個、12個、36個、72個とした場合それぞれについて実験を行った。図11に実験結果を示す。図11のグラフの縦軸はエラー率であり、横軸は学習処理中の繰り返し回数である。分散並列処理を行う計算機の数を増やすほどエラーを少なくできることがわかった。なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。例えば、上述のランキング関数学習装置、学習制御装置、学習装置は、内部にコンピュータシステムを有しているが、コンピュータシステムは、WWWシステムを利用している場合であれば、ホームページ提供環境あるいは表示環境も含むものとする。また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。"