"複数の学習用特徴ベクトルを入力し、その中から複数のペアを選択する学習ペア選択部と、変換行列を用いて前記学習用特徴ベクトルを変換した上で、当該変換された学習用ベクトルをビットコードに変換するビットコード変換部と、前記複数のペアについての、前記学習ペア選択部に入力された前記学習用特徴ベクトルの距離と前記ビットコード変換部で変換された前記ビットコードの距離との相違の、全ての前記ペアについての和を示すコスト関数を計算するコスト関数計算部と、前記ビットコード変換部にて用いる前記変換行列の要素を選択して、選択した要素を置換候補で置換することで、前記変換行列を更新する変換行列更新部と、を備え、前記ビットコード変換部は、変換行列更新部で更新された変換行列を用いて、前記学習用特徴ベクトルを変換した上で、当該変換された学習用ベクトルをビットコードに変換し、前記コスト関数計算部は、前記変換行列更新部によって前記変換行列の要素が前記置換候補で置換されたときに、前記コスト関数に基づいて、前記置換候補及びもとの前記要素の中から、ひとつを選択することで、前記要素を確定し、前記変換行列更新部が前記要素を順に変えて選択し、そのつど前記コスト関数計算部が選択された前記要素を確定することで、前記最終的に最適な前記変換行列を確定し、前記置換候補は、前記ビットコード変換部による前記変換行列を用いた変換処理が高速になるように特定されることを特徴とする特徴変換装置。前記コスト関数計算部は、前記要素を前記置換候補の各々で置換したときの前記コスト関数の変化量を計算し、前記変化量に応じて採用確率を決定し、前記採用確率に応じて、前記置換候補及びもとの前記要素の中からひとつを選択することを特徴とする請求項1に記載の特徴変換装置。前記ペアについての、前記学習ペア選択部に入力された前記学習用特徴ベクトルの距離は、L1ノルム、L2ノルム、又はベクトル間角度のいずれかに基づく距離であることを特徴とする請求項1又は2に記載の特徴変換装置。前記ペアについての、前記ビットコード変換部で変換された前記ビットコードの距離は、ハミング距離に基づく距離であることを特徴とする請求項1ないし3のいずれか一項に記載の特徴変換装置。前記変換行列の要素は整数に限定されており、前記置換候補も整数に限定されていることを特徴とする請求項1ないし4のいずれか一項に記載の特徴変換装置。前記変換行列の要素は、-1、0、1のいずれかに限定されており、前記置換候補も-1、0、1のいずれかに限定されていることを特徴とする請求項5に記載の特徴変換装置。前記変換行列は、非0の要素の数が所定の範囲内に限定されており、前記置換候補は、前記変換行列の非0の要素の数を前記所定の範囲内に保つよう特定されていることを特徴とする請求項1ないし6のいずれか一項に記載の特徴変換装置。前記変換行列の要素は、2のべき乗に限定されており、前記置換候補も2のべき乗に限定されていることを特徴とする請求項5に記載の特徴変換装置。前記学習ペア選択部は、入力された前記複数の学習用特徴ベクトルの中から任意にペアを選択することを特徴とする請求項1ないし8のいずれか一項に記載の特徴変換装置。前記学習ペア選択部は、前記学習用特徴ベクトルの距離に基づいて、入力された前記複数の学習用特徴ベクトルの中からペアを選択することを特徴とする請求項1ないし8のいずれか一項に記載の特徴変換装置。前記学習ペア選択部は、所定の距離以下のペアと前記所定の距離以上のペアの組数が所定の割合になるように、入力された前記複数の学習用特徴ベクトルの中からペアを選択することを特徴とする請求項10に記載の特徴変換装置。前記学習ペア選択部は、距離の頻度が一様又は特定の分布になるように、入力された前記複数の学習用特徴ベクトルの中からペアを選択することを特徴とする請求項10に記載の特徴変換装置。前記学習ペア選択部は、最も遠い距離関係にあるペアと最も近い距離関係にあるペアの組数が所定の割合になるように、入力された前記複数の学習用特徴ベクトルの中からペアを選択することを特徴とする請求項10に記載の特徴変換装置。前記コスト関数計算部は、前記変換行列更新部によって前記変換行列の要素が置換候補で置換される前の変換行列を用いてされた前記コスト関数の計算の結果を、前記変換行列更新部によって前記変換行列の要素が置換候補で置換された後の変換行列のコスト関数の計算に流用することを特徴とする請求項1ないし13のいずれか一項に記載の特徴変換装置。請求項1ないし14のいずれか一項に記載の特徴変換装置と、類似ベクトル検索部とを備えた類似情報探索装置であって、前記ビットコード変換部は、前記確定された最適な変換行列を用いて前記複数の学習用特徴ベクトルを複数のビットコードに変換し、前記ビットコード変換部は、入力特徴ベクトルが与えられたときに、前記確定された最適な変換行列を用いて当該入力特徴ベクトルをビットコードに変換し、前記類似ベクトル検索部は、前記ビットコード変換部にて前記複数の学習ベクトルから変換された前記複数のビットコードを保管するビットコード保管部と、前記ビットコード変換部にて前記入力特徴ベクトルから変換された前記ビットコードを入力して、近傍探索によって、前記ビットコード保管部に保管された前記複数のビットコードの中から、前記入力特徴ベクトルから変換されたビットコードに類似するビットコードを探索する近傍探索部と、を備えたことを特徴とする類似情報探索装置。特徴ベクトルをビットコードに変換するためのコード化パラメータとして変換行列を出力するコード化パラメータ生成方法であって、複数の学習用特徴ベクトルの中から複数のペアを選択する第1ステップと、所定の拘束条件の下で、変換行列を初期化する第2ステップと、前記複数のペアについての、前記学習用特徴ベクトルの距離と前記学習用特徴ベクトルから前記初期化された変換行列を用いて変換されたビットコードの距離との相違の和を示すコスト関数を計算する第3ステップと、前記変換行列の要素の中から置換対象とする要素を選択する第4ステップと、前記第4ステップで選択された要素を特定の置換候補で置換する第5ステップと、前記第5ステップで前記選択された要素が前記置換候補で置換された前記変換行列を用いて、前記コスト関数を計算する第6ステップと、前記選択された要素をそれに対応する前記置換候補のすべてで置換したか否かを判断して、前記選択された要素をそれに対応する前記置換候補のすべてで置換していない場合には前記第5ステップに戻る第7ステップと、前記第7ステップにおいて、前記選択された要素をそれに対応する前記置換候補のすべてで置換したと判断された場合に、前記置換候補のうち、計算されたコスト関数が最も小さかった置換候補で、選択されている要素を確定することで、最適変換行列を暫定的に確定する第8ステップと、前記第8ステップにて暫定的に確定された前記最適変換行列が収束しているか否かを判断し、収束していないと判断した場合には前記第4ステップに戻る第9ステップと、前記第8ステップにて暫定的に確定された前記最適変換行列が収束していると判断した場合に、暫定的に確定された前記最適変換行列を最終的に確定された最適変換行列として出力する第10ステップと、を含むことを特徴とするコード化パラメータ生成方法。請求項16に記載のコード化パラメータ生成方法をコンピュータに実行させるためのコンピュータプログラム。しかしながら、上記の従来のバイナリビットコード化手法には、以下の問題がある。第一の問題は、従来手法はビットコード化が遅いという問題である。即ち、D次元のベクトルをdビットのコードに変換する場合には、式4のWTxの計算にはD×d回の乗算と、D×d-1回の加算が必要である。従って、従来手法では距離計算を高速化することはできるものの、その前段の処理であるビットコード化がボトルネックとなってしまう。これは、特徴ベクトルの次元数Dが増えるほど深刻となる。特に、リアルタイムにビットコード化が必要な場合、例えばリアルタイム画像検索やリアルタイム音声認識に適用する場合には非常に不便である。第二の問題は、ビットコードが長くなるという問題である。即ち、乱数に基づいてWを構成する場合、特徴ベクトルの分布を考慮していないため、十分な性能を得るためには長いビットコードが必要になる。上記の従来のバイナリビットコード化手法のうち、ランダムプロジェクションには第一及び第二の問題があり、ベリースパースランダムプロジェクションには第二の問題があり、スペクトラルハッシングには、第一の問題がある。本発明は、上記の問題点に鑑みてなされたものであり、特徴ベクトルのビットコード化が高速で、かつ短いビットコードを生成できる特徴変換装置を提供することを目的とする。上記従来の課題を解決するために、本発明の特徴変換装置は、複数の学習用特徴ベクトルを入力し、その中から複数のペアを選択する学習ペア選択部と、変換行列を用いて前記学習用特徴ベクトルを変換した上で、当該変換された学習用ベクトルをビットコードに変換するビットコード変換部と、前記複数のペアについての、前記学習ペア選択部に入力された前記学習用特徴ベクトルの距離と前記ビットコード変換部で変換された前記ビットコードの距離との相違の、全ての前記ペアについての和を示すコスト関数を計算するコスト関数計算部と、前記ビットコード変換部にて用いる前記変換行列の要素を選択して、選択した要素を置換候補で置換することで、前記変換行列を更新する変換行列更新部とを備えた構成を有している。そして、前記ビットコード変換部は、変換行列更新部で更新された変換行列を用いて、前記学習用特徴ベクトルを変換した上で、当該変換された学習用ベクトルをビットコードに変換し、前記コスト関数計算部は、前記変換行列更新部によって前記変換行列の要素が前記置換候補で置換されたときに、前記置換候補及びもとの前記要素の中から、所定の方法に基づいてひとつを選択することで、前記要素を確定する。前記変換行列更新部が前記要素を順に変えて選択し、そのつど前記コスト関数計算部が選択された前記要素を確定することで、前記最終的に最適な前記変換行列が確定される。前記置換候補は、前記ビットコード変換部による前記変換行列を用いた変換処理が高速になるように特定される。この構成により、変換行列が学習に基づいて最適化されるため、生成されるビットコードは短くなる。更に、最終的に確定される最適変換行列の要素は、ビットコード変換部によるビットコード変換処理が高速になるように確定されているので、この最適変換行列を用いることで高速にビットコード変換を行うことができる。また、変換行列更新部が要素を順に変えて選択し、そのつどコスト関数計算部が当該選択された要素を確定するという手法により最適変換行列を求めるので、コスト関数が非線形であって微分不可能であっても、効果的にコスト関数を減少させることができる。これにより、ビットコード変換部で変換されたビットコードの距離によって、学習ペア選択部に入力された学習用特徴ベクトルの距離を十分な精度で近似できるようになる。よって、短いビットコードでも、最近傍探索において十分な性能を発揮できるようになる。上記の特徴変換装置において、前記コスト関数計算部は、前記要素を前記置換候補の各々で置換したときの前記コスト関数の変化量を計算し、前記変化量に応じて採用確率を決定し、前記採用確率に応じて、前記置換候補及びもとの前記要素の中からひとつを選択してよい。この構成により、コスト関数の変化量に基づいて要素が確定されるので、好適に要素を確定することができる。例えば、コスト関数計算部は、コスト関数を最小にする置換候補でもって要素を確定してよい。なお、コスト関数の変化量とは、選択された要素をある置換候補で置換する前のコスト関数と置換した後のコスト関数との差分値である。上記の特徴変換装置において、前記ペアについての、前記学習ペア選択部に入力された前記学習用特徴ベクトルの距離は、L1ノルム、L2ノルム、又はベクトル間角度のいずれかに基づく距離であってよい。また、上記の特徴変換装置において、前記ペアについての、前記ビットコード変換部で変換された前記ビットコードの距離は、ハミング距離に基づく距離であってよい。また、上記の特徴変換装置において、前記変換行列の要素は整数に限定されており、前記置換候補も整数に限定されていてよい。この構成により、ビットコード変換部によるビットコード変換処理をより高速化できる。また、上記の特徴変換装置において、前記変換行列の要素は、-1、0、1のいずれかに限定されており、前記置換候補も-1、0、1のいずれかに限定されていてよい。この構成により、ビットコード変換部での変換行列を用いた変換において掛け算が不要となるので、ビットコード変換処理をより高速化できる。また、上記の特徴変換装置において、前記変換行列は、非0の要素の数が所定の範囲内に限定されており、前記置換候補は、前記変換行列の非0の要素の数を前記所定の範囲内に保つよう特定されていてよい。この構成により、変換行列を疎スパースにできるので、ビットコード変換部での変換行列を用いた処理をさらに高速化できる。なお、上記の所定の範囲の大きさは、幅1の範囲であってもよい。即ち、非0の要素の数が具体的な数に固定されていてもよい。また、上記の特徴変換装置において、前記変換行列の要素は、2のべき乗に限定されており、前記置換候補も2のべき乗に限定されていてよい。この構成により、ビットコード変換部での変換行列を用いた変換においてビットシフトの手法を用いることが可能になり、ビットコード変換処理をより高速化できる。また、上記の特徴量変換装置において、前記学習ペア選択部は、入力された前記複数の学習用特徴ベクトルの中から任意にペアを選択してよい。この構成により、高い精度で近似が可能なビットコードに変換するための変換行列を好適に求めることができる。また、上記の特徴変換装置において、前記学習ペア選択部は、前記学習用特徴ベクトルの距離に基づいて、入力された前記複数の学習用特徴ベクトルの中からペアを選択してよい。この構成により、ビットコード変換部で変換されたビットコードの距離によって、学習ペア選択部に入力された学習用特徴ベクトルの距離をより十分な精度で近似できるようになる。よって、より短いビットコードでも、最近傍探索において十分な性能を発揮できるようになる。また、上記の特徴変換装置において、前記学習ペア選択部は、所定の距離以下のペアと前記所定の距離以上のペアの組数が所定の割合になるように、入力された前記複数の学習用特徴ベクトルの中からペアを選択してよい。また、上記の特徴変換装置において、前記学習ペア選択部は、距離の頻度が一様又は特定の分布になるように、入力された前記複数の学習用特徴ベクトルの中からペアを選択してよい。また、上記の特徴変換装置において、前記学習ペア選択部は、最も遠い距離関係にあるペアと最も近い距離関係にあるペアの組数が所定の割合になるように、入力された前記複数の学習用特徴ベクトルの中からペアを選択してよい。また、上記の特徴変換装置において、前記コスト関数計算部は、前記変換行列更新部によって前記変換行列の要素が置換候補で置換される前の変換行列を用いてされた前記コスト関数の計算の結果を、前記変換行列更新部によって前記変換行列の要素が置換候補で置換された後の変換行列のコスト関数の計算に流用してよい。この構成により、最適変換行列を求める演算を高速化できる。本発明の類似情報探索装置は、上記のいずれかの特徴変換装置と、類似ベクトル検索部とを備えた類似情報探索装置であって、前記ビットコード変換部は、前記確定された最適な変換行列を用いて前記複数の学習用特徴ベクトルを複数のビットコードに変換し、前記ビットコード変換部は、入力特徴ベクトルが与えられたときに、前記確定された最適な変換行列を用いて当該入力特徴ベクトルをビットコードに変換し、前記類似ベクトル検索部は、前記ビットコード変換部にて前記複数の学習ベクトルから変換された前記複数のビットコードを保管するビットコード保管部と、前記ビットコード変換部にて前記入力特徴ベクトルから変換された前記ビットコードを入力して、近傍探索によって、前記ビットコード保管部に保管された前記複数のビットコードの中から、前記入力特徴ベクトルから変換されたビットコードに類似するビットコードを探索する近傍探索部とを備えた構成を有している。本発明のコード化パラメータ生成方法は、特徴ベクトルをビットコードに変換するためのコード化パラメータとして変換行列を出力するコード化パラメータ生成方法であって、複数の学習用特徴ベクトルの中から複数のペアを選択する第1ステップと、所定の拘束条件の下で、変換行列を初期化する第2ステップと、前記複数のペアについての、前記学習用特徴ベクトルの距離と前記学習用特徴ベクトルから前記初期化された変換行列を用いて変換されたビットコードの距離との相違の和を示すコスト関数を計算する第3ステップと、前記変換行列の要素の中から置換対象とする要素を選択する第4ステップと、前記第4ステップで選択された要素を特定の置換候補で置換する第5ステップと、前記第5ステップで前記選択された要素が前記置換候補で置換された前記変換行列を用いて、前記コスト関数を計算する第6ステップと、前記選択された要素をそれに対応する前記置換候補のすべてで置換したか否かを判断して、前記選択された要素をそれに対応する前記置換候補のすべてで置換していない場合には前記第5ステップに戻る第7ステップと、前記第7ステップにおいて、前記選択された要素をそれに対応する前記置換候補のすべてで置換したと判断された場合に、前記置換候補のうち、計算されたコスト関数が最も小さかった置換候補で、選択されている要素を確定することで、最適変換行列を暫定的に確定する第8ステップと、前記第8ステップにて暫定的に確定された前記最適変換行列が収束しているか否かを判断し、収束していないと判断した場合には前記第4ステップに戻る第9ステップと、前記第8ステップにて暫定的に確定された前記最適変換行列が収束していると判断した場合に、暫定的に確定された前記最適変換行列を最終的に確定された最適変換行列として出力する第10ステップとを含んでいる。本発明のコンピュータプログラムは、上記のコード化パラメータ生成方法をコンピュータに実行させるためのコンピュータプログラムである。本発明によれば、ビットコード変換を高速化でき、かつ短いビットコードを生成できる変換行列を生成することができる。以下、本発明を実施するための形態について説明する。なお、本明細書において、ビットコード化とビットコード変換とは同じ意味として用いる。図2は、本発明の実施の形態の類似情報探索装置の構成を示すブロック図である。図2に示すように、類似情報探索装置100は、エンコーダ部101と類似特徴ベクトル検索部102とを備えている。エンコーダ部101は、単精度実数の特徴ベクトルをビットコードに変換する。エンコーダ部101は、本発明の特徴変換装置に相当する。類似特徴ベクトル検索部102は、k-最近傍探索によって、入力特徴ベクトルに対するk個の類似ベクトルを探索する。図1は、エンコーダ部101の構成を示すブロック図である。エンコーダ部101は、コード化パラメータ生成部10と、ビットコード変換部20を備えている。コード化パラメータ生成部10は、学習用の特徴ベクトルtを用いて、単精度実数の特徴ベクトルをビットコードに変換する際に必要なパラメータを生成して、ビットコード変換部20に出力する。具体的には、コード化パラメータ生成部10は、コード化パラメータとして、ビットコード変換に用いる変換行列Wを求める。ビットコード変換部20は、コード化パラメータ生成部10で生成されたパラメータを用いて、特徴ベクトルをビットコード化する。類似特徴ベクトル検索部102は、ビットコード保管部30と、k-最近傍検索部40と、距離計算部50とを備えている。ビットコード保管部30には、ビットコード化された複数の特徴ベクトル以下、ビットコード化された特徴ベクトルを単にビットコードという。が保存されている。類似特徴ベクトル検索部102は、入力情報と類似する情報を探す際には、入力情報の特徴ベクトルから変換されたビットコードと類似するビットコードをビットコード保管部30に保管された複数のビットコードの中から検索する。このビットコード保管部30には、エンコーダ部101のビットコード変換部20で変換されたビットコードが保管される。また、入力情報の特徴ベクトルもビットコード変換部20でビットコードに変換される。入力情報のビットコードは、k-最近傍探索部40に入力される。k-最近傍探索部40は、この入力情報のビットコードと類似するビットコードをビットコード保管部30に保管されている複数のビットコードの中から探索して、類似ベクトルとして出力する。距離計算部50は、k-最近傍探索部40において類似するビットコードを探索する際のビットコード同士の距離を計算して、k-最近傍探索部40に提供する。本発明は、エンコーダ部101に特徴を有し、特に、ビットコード変換部20にて特徴ベクトルをビットコードに変換する際に用いるコード化パラメータ変換行列Wを生成するコード化パラメータ生成部10に特徴を有する。コード化パラメータ生成部10について説明をする前に、以下の定義をする。まず、変換前の特徴ベクトルを次式5のように定義する。式5において、Dは特徴ベクトルの次元数である。変換後のビットコードを次式6のように定義する。式6において、dはビットコードのビット長である。これは、yがd次元のベクトルであり、yの各要素は0もしくは1の値のみを取るという意味である。すなわち、yはビットコードであると解釈できる。変換行列を次式7のように定義する。ビットコード化を次式8のように定義する。変換前の特徴空間における類似度正規化コサイン距離を次式9のように定義する。なお、変換前の特徴空間における類似度の尺度として、L1ノルムやL2ノルムなど、他の尺度を用いてもよい。例えば、上式3の角度θを円周率πで正規化したものを用いてもよい。変換後の特徴空間における類似度正規化ハミング距離を次式10のように定義する。なお、式10において、hはハミング距離を求める関数である。式9及び式10から明らかなように、正規化コサイン距離及び正規化ハミング距離は、0から1の範囲の値を取るように正規化されている。距離の値が小さいほど特徴が類似しており、大きいほど特徴が類似していないことを表している。以下、エンコーダ部101、特にコード化パラメータ生成部10の構成について説明する。コード化パラメータ生成部10は、学習ペア選択部11と、学習ペア保持部12と、変換行列初期化部13と、拘束条件格納部14と、置換候補特定部15と、変換行列更新部16と、コスト関数計算部17と、判定収束部18とを備えている。学習ペア選択部11には、複数の学習用の特徴ベクトル以下、単に学習ベクトルという。が入力される。学習ベクトルは、次式11のように定義される。式11においてN、即ち学習ベクトルの数は、例えば1万とすることができる。学習用ペア選択部11は、入力された複数の学習ベクトルの中から、ペアを選択する。図3は、学習ベクトルとそのペアを概念的に示す図である。学習用ペア選択部11で選択するペアの数は多いほうがよい。学習用ペア選択部11は、例えば次の選び方でペアを選択する。まず、学習用ペア選択部11は、入力された複数の学習ベクトルの全ての組合せをペアとして選択することができる。また、学習用ペア選択部11は、入力された複数の学習ベクトルの中から所定数のペアをランダムに選択することもできる。さらに、学習用ペア選択部11は、距離に依存するようにペアを選択することもできる。例えば、学習用ペア選択部11は、距離が最も遠いペアと距離が最も近いペアを均等に選ぶことができる。また、学習用ペア選択部11は、距離の頻度が一様になるようにペアを選んでもよい。さらに、学習用ペア選択部11は、一定の距離d_th以下のペアと、d_th以上のペアの数が均等になるように選んでもよい。学習ペア選択部11にて選択された学習ベクトルのペアは学習ペア保持部12に保持される。学習ペア保持部12に保持されている学習ベクトルの各ペアは、コスト関数計算部17に出力され、コスト関数計算部17でコスト関数を計算するのに用いられる。コスト関数計算部17で計算されるコスト関数は、次式12のように定義される。ここで、集合Pは学習ペア保持部12から入力された学習ベクトルのペアの集合である。コスト関数計算部17は、fWを最小化するようなWを求める。即ち、コスト関数計算部17は、変換前の空間におけるコサイン距離と、変換後の空間におけるハミング距離がなるべく一致するようなWを求める。このときに必要なビットコード変換は、ビットコード変換部20が行う。一般的には、関数yxを最小にするxを求める場合には、関数yxを微分することで変曲点のxを求める等の手法が用いられるが、式12に示すように、本実施の形態のコスト関数fWは微分不可能であり、従って、一般的な最適化手法を適用することができない。そこで、本実施の形態のコード化パラメータ生成部10は、後述する方法でfWを最小化し、そのときの変換行列Wを最適変換行列として、ビットコード変換部20に出力する。最適変換行列を求めるための構成を説明する。変換行列初期化部13は、拘束条件格納部14に格納されている拘束条件の下で、変換行列Wを初期化して、変換行列更新部16に出力する。拘束条件格納部14には、変換行列初期化部13にて変換行列を初期化する際、及び置換候補特定部15にて変換行列の要素を置換するための置換候補を特定する際の、変換行列の要素に課される拘束条件を格納している。置換候補特定部15は、変換行列中の選択された要素に対する置換候補を特定して、変換行列更新部16に出力する。変換行列更新部16は、変換行列初期化部14から入力された初期化された変換行列をコスト関数計算部17に出力する。変換行列更新部16は、また、初期化された変換行列Wの要素の中から置換対象とする要素を選択して、選択した要素を置換候補特定部15で特定された置換候補で置換して、コスト関数計算部17に出力する。変換行列更新部16は、さらに、収束判定部18から未収束である旨の報告を受けると、その暫定的に確定された変換行列Wについて、新たな置換対象要素を選択して、置換候補特定部15で特定された置換候補で置換する。コスト関数計算部17は、変換行列更新部16から入力された変換行列を用いて、式12によってコストを計算する。また、コスト関数計算分17は、選択された要素が複数の置換候補でそれぞれ置換されてなる複数の変換行列によってそれぞれ計算されたコストを比較して、最も低いコストが計算された際に用いた変換行列を、暫定的に最適変換行列として確定し、これを変換行列更新部16に戻す。収束判定部18は、暫定的に確定された最適変換行列で計算されたコストに基づいて、最適変換行列が収束しているか否かを判断する。収束判定部18は、例えば暫定的に確定された最適変換行列で計算されたコストが所定の閾値を下回っている場合に、収束していると判断してもよいし、暫定的に確定された最適変換行列で計算されたコストの変化量が所定の閾値を下回った場合に、収束していると判断してもよい。収束判定部18は、最適変換行列が収束していると判断する場合には、暫定的に確定された最適変換行列を最終的に確定された最適変換行列として、ビットコード変換部20に出力する。収束判定部18は、最適変換行列が収束していないと判断する場合には、変換行列行進部16に対して、暫定的に確定された最適変換行列に対して、再度、そのうちの要素を選択して、選択した要素を置換候補に従って置換するよう指示する。図4は、最適変換行列の決定方法の概要を示すフロー図である。図4を参照して、最適変換行列の決定方法の概要を説明する。まず、変換行列初期化部13が、拘束条件格納部14に格納されている拘束条件の下で、変換行列Wを初期化して、変換行列更新部16に出力するステップS41。変換行列更新部16は、まず、変換行列初期化部14から入力された初期化された変換行列をコスト関数計算部17に出力し、コスト関数計算部17は、この初期化された変換行列を用いて、式12によってコストを計算するステップS42。次に、変換行列更新部16は、変換行列Wの要素の中から置換対象とする要素を選択するステップS43。変換行列更新部16は、選択した要素を置換候補特定部15で特定された置換候補で置換して、コスト関数計算部17に出力するステップS44。コスト関数計算部17は、選択された要素が置換された変換行列Wを用いて、コストを計算するステップS45。次に、置換候補行列更新部16は、置換候補特定部15で特定された置換候補のうち、まだコスト計算を行っていない置換候補があるか否かを判断するステップS46。まだコスト計算を行っていない置換候補がある場合にはステップS46でYES、ステップS44に戻って、選択されている要素を他の置換候補で置換して、ステップS45にてコスト計算を行なう。こうして置換候補特定部15にて特定されたすべての置換候補についてコスト計算をするとステップS46でNO、コスト関数計算部17は、それらの置換候補のうち計算されたコストが最も小さかった置換候補で、選択されている要素を確定するステップS47。これによって最適変換行列が暫定的に確定される。収束判定部18は、変換行列が暫定的に確定された後に、その確定された変換行列で計算されたコストの値に基づいて、変換行列が収束したか否かを判断するステップS48。収束していない場合にはステップS48でNO、収束判定部18は、暫定的に確定された変換行列を変換行列更新部16に出力するとともに、変換行列更新部16に再度の置換対象候補の選択をするよう指示する。即ち、このとき処理はステップS43に戻って、ステップS43からステップS48の処理を繰り返す。ステップS43からステップS48の処理を繰り返して、ステップS48で収束したと判断されたときは、収束判定部18は、最後にステップS47で確定された変換行列Wを最終的に確定された最適変換行列として出力するステップS49。以下、上記で概要を説明した最適変換行列の決定方法の具体例を説明する。以下では、図4を引用して、具体例の処理が対応する図4中のステップを明示する。最適変換行列の決定方法の具体例1具体例1のコード化パラメータ生成部10では、拘束条件格納部14には、拘束条件として、次式13が格納されている。ここで、wi,jは、変換行列Wのi行j列の要素である。変換行列初期化部13は、変換行列Wをランダムに初期化するステップS41。変換行列更新部16は、変換行列Wの要素wi,jをランダムに1つ選択し、この選んだ要素をwu,vとするステップS43。図5は、具体例1において置換候補特定部15で特定される置換候補を示す図である。図5に示すように、wu,vが1である場合には、置換候補は-1及び0となり、wu,vが0である場合には、置換候補は1及び-1となり、wu,vが-1である場合には、置換候補は0及び1となる。変換行列更新部16は、選択された要素をこれらの各置換候補で置換して、選択された要素が変換された変換行列をコスト関数計算部17に出力するステップS44。コスト関数計算部17は、それぞれの変換行列についてコストを計算するステップS45。コスト関数計算部17は、もともとのコストと選択された要素が置換候補によってそれぞれ置換された変換行列で計算されたコストとを比較して、最もコストが低かった変換行列を暫定的に最適変換行列として確定するステップS47。そして、コストが十分に小さくなるまで、上記の処理を繰り返す。具体例1によれば、式13の条件を維持しつつ、コストを効率的に最小化できる。そして、変換行列Wの要素wi,jが-1,0,1しか持たないため、ビットコード変換部20が式8によってビットコード変換をする際のWTxの計算において、掛け算が不要になり、高速にビットコード化を行なうことができる。最適変換行列の決定方法の具体例2具体例2は、上記の具体例1において、拘束条件に次式14を追加したものである。ここで、式14は、変換行列Wの要素のうち、非0の要素の数がC個であるという条件である。Cはユーザが任意に指定できる定数である。即ち、具体例2では、要素数がC個になるという条件下の下で、fWを最小化する。変換行列初期化部13は、変換行列Wの要素を-1と1でランダムに埋めて、変換行列Wの要素からランダムにC個を選択し、それら以外をすべて0で埋めることにより、変換行列Wを初期化するステップS41。変換行列更新部16は、変換行列Wの要素wi,jをランダムに1つ選択するステップS43この選んだ要素をwu,vとする。図6は、具体例2において置換候補特定部15で特定される置換候補を示す図である。図6に示すように、置換候補特定部15では、式14の条件を満たすように置換候補が特定される。即ち、式14の拘束条件によって、非0の数を変動させるような変換はできないので、非0の数が変動しないような置換候補のみが特定されている。具体的には、図6に示すように、wu,v=1である場合は、1は非0であるので、非0である-1にしか変換できない。また、wu,v=0である場合は、これを1又は-1、即ち非0に変換すると、非0の数が変動してしまうので、0には置換候補はないことになる。wu,v=-1である場合は、-1は非0であるので、非0である1にしか変換できない。変換行列更新部16は、選択された要素をこれらの各置換候補で置換して、選択された要素が置換された変換行列をコスト関数計算部17に出力するステップS44。その他の処理は具体例1と同様である。具体例2によれば、式13及び式14の条件を維持しつつ、コストを効率的に最小化できる。そして、変換行列Wの要素wi,jが-1と1しか持たないため、ビットコード変換部20が式8によってビットコード変換をする際のWTxの計算において、掛け算が不要になり、高速にビットコード化を行なうことができる。具体例2ではさらに、Cの値を小さくすることで、変換行列Wを非常に疎スパースな行列にすることができる。変換行列Wを疎にすることで、WTxの計算を更に高速化できる。最適変換行列の決定方法の具体例3具体例3のコード化パラメータ生成部10では、具体例2と同様に、拘束条件格納部14には、拘束条件として、式13及び次式14が格納されている。変換行列初期化部13は、具体例2と同様にして変換行列Wを初期化するステップS41。具体例3では、変換行列更新部16は、変換行列Wの要素wi,jをランダムに2つ選択するステップS43この選んだ要素をwu,v、wp,qとする。図7は、具体例3において置換候補特定部15で特定される置換候補を示す図である。図7に示すように、置換候補特定部15は、式14の条件を満たすように、置換候補を特定する。即ち、式14の拘束条件によって、非0の数を変動させるような変換はできないので、非0の数が変動しないような置換候補のみが特定されている。例えば、wu,v,wp,q=1,1である場合は、非0の数は2個であるので、置換候補は、非0が2個になる条件を保って、-1,-1、1,-1、-1,1となる。他も同様であり、wu,v,wp,qに非0が1個ある場合には、非0が1個という条件を保って置換候補が特定される。なお、wu,v,wp,q=0,0である場合は、式14によって、非0が0個である状態を維持する必要があるので、置換候補はないことになる。この場合は、wu,v、wp,qを新たに選択し直す。変換行列更新部16は、選択された要素をこれらの各置換候補で置換して、選択された要素が変換された変換行列をコスト関数計算部17に出力するステップS44。その他の処理は具体例1と同様である。具体例3によれば、具体例2と同様に変換行列Wを疎にすることで、WTxの計算を更に高速化できる。さらに、具体例2では、初期化された変換行列Wにおいて0の要素は固定されていたが、具体例3では、0の要素の数を固定したままその場所が最適化されるので、変換行列Wをより好適に最適化できる。以上説明したとおり、最適変換行列を求める過程では、wu,vを更新するたびに、ビットコード変換部20がビットコード変換を行い、コスト関数計算部17がコスト関数fWを計算する。以下では、その計算を大幅に簡略化して、効率的にコスト関数を計算する方法を説明する。図8は、特徴ベクトルをビットコードに変換する処理を示す図である。図8は、式8を図式化したものである。なお、図8において、行列Xの各列は、1つの特徴ベクトルxであり、行列Zの各列は、WTxであり、行列Yの各列は、式8で表されるyである。図9は、ビットコードに変換する前の特徴ベクトルXAと特徴ベクトルXBの間の距離を求める処理を示す図である。なお、図9及び以下の図10、図11、図14において、説明の便宜上、特徴ベクトルもしくはビットコード間の距離演算を模式化する記号としてマイナスを用いた。図9におけるDoの各列は、特徴ベクトルXA及びXBの対応する列同士の正規化された距離を表している。図10は、図9の特徴ベクトルXA及びXBをビットコードに変換して、ビットコードYA及びYBとした上で、それらのハミング距離を求める処理を示す図である。図10においても、Dhの各列は、ビットコードYA及びYBの対応する列同士の正規化された距離を表している。図11は、変換行列において選択された要素とコスト関数との関係を示す図である。図11に示すように、いま、選択された要素がWTの第1行にあるとすると、この選択された要素w1,∞右下添え字の1,∞は、第1行の任意の列を表しているが置換候補によって置換されることで、ビットコードYA及びYBにおいて影響を受けるのは、その第1行の要素のみである。よって、要素w1,∞を各置換候補で置換しながらビットコードYA及びYBのハミング距離を求めると、その各ハミング距離の各列の値は、実際には、ビットコードYA及びYBにて第1行の要素のみが変更されて求められた値である。即ち、図11のビットコードYA及びYBにおいて、斜線で示した第1行以外の部分については、要素w1,∞を各置換候補で置換するたびに、重複して計算していることになる。従って、この重複計算を回避することで、計算速度を早くすることができる。図12は、変換行列W中の選択された要素を第n番目の置換候補に置換したときの、ビットコードYを求める処理を示す図である。図12において、ビットコードY及び変換行列の転地行列WTの右上添え字のnは、選択された要素が第n番目の置換候補で置換されていることを示している。図12の例では、WTの1行1列の要素w1,1が選択されている。図13は、図12の状態から、選択された要素w1,1が第n1番目の置換候補で置換されたときのビットコードYを求める処理を示す図である。図13のビットコードYn1において、図12のビットコードYnから変更されているのは、斜線で示した第1行のみである。ここで、下式15、16のように定義をする。ここで、wの右下添え字1,∞は、上述のように、選択された要素wが第1行列は任意であることを表しており、Yの右下添え字1,∞は、ビットコードYの第1行を表している。上記のように定義すると、X、及び変換行列Wのうちの選択された要素w以外の要素は、選択された要素wが置換候補で置換されたとしても不変であるので、次式17が成り立つ。式17から、次式18が成り立つ。図14は、選択された要素w1,1が第n1番目の置換候補で置換されたときの、ハミング距離を求める処理を示す図である。ハミング距離Dhの右上添え字のn1は、選択された要素w1,1が第n1番目の置換候補で置換されていることを示している。ハミング距離Dhn1はハミング距離Dhnとは異なるものになるが、この相違は、実際には、ビットコードYAとビットコードYBのそれぞれの第1行の相違のみに起因するものである。従って、選択された要素w1,1が第n1番目の置換候補で置換されたときのハミング距離Dhn1は、次式19によって求めることができる。ここで、ΔY1,∞は、次式20で定義される。このように、選択された要素w1,1が第n1番目の置換候補で置換されたときのビットコードYn1の第1行は、式15から式19で示したように、選択された要素w1,1が第n番目の置換候補にであったときの計算結果を利用して求めることができ、更に、選択された要素w1,1が第n1番目の置換候補で置換されたときのハミング距離Dhn1は、選択された要素w1,1が第n番目の置換候補であったときのハミング距離DhnとビットコードYAn及びYBnの第1行を用いて求めることができる。上記の説明は、選択された要素wが第1行第1列のw1,1であったが、上記の式18及び19を一般化すると、それぞれ次式21及び22となる。なお、ΔYj,∞は、次式23で定義される。コスト関数計算部17は、選択された要素が置換候補で置換されると、上記式21及び式22を用いてコスト関数fWを計算する。以上、本発明の実施の形態を説明したが、本発明は上記の実施の形態に限らず、種々の形態で実施される。例えば、拘束条件格納部14に格納される拘束条件は、変換行列の要素がすべて整数であるという条件であってもよく、変換行列の要素がすべて2のべき乗であるという条件であってもよい。"