(57)【要約】【課題】特徴量ベクトルをバイナリ列に変換した際の検索精度を向上する。【解決手段】情報検索装置１は、ハミング距離を用いた検索処理の対象となるデータの特徴量ベクトルを、バイナリ記号とのハミング距離を０とするワイルドカード記号と前記バイナリ記号とを含む記号列に変換する。そして、情報検索装置１は、クエリデータをバイナリ化し、バイナリ化したクエリデータとのハミング距離が所定の値以下となる記号列を検索することで、クエリデータの近傍データを検索する。【選択図】図１
2013206187.tif 000002
【特許請求の範囲】
【請求項１】
ハミング距離を用いた検索処理の対象となるデータの特徴量ベクトルを、バイナリ記号とのハミング距離を０とするワイルドカード記号と前記バイナリ記号とを含む記号列に変換する変換部を有することを特徴とする情報変換装置。
【請求項２】
前記変換部は、ハミング距離を用いた検索処理の対象となるデータの特徴量ベクトルのある成分が、異なるクラスの特徴量ベクトルとの境界から所定の範囲内に収まる場合には、バイナリ記号とのハミング距離を０とするワイルドカード記号に当該成分を変換し、異なるクラスの特徴量ベクトルとの境界から所定の範囲内に収まらない場合には、当該成分をバイナリ記号に変換することで、前記特徴量ベクトルを記号列に変換することを特徴とする請求項１に記載の情報変換装置。
【請求項３】
前記変換部は、所定の変換行列と前記特徴量ベクトルとの積を算出し、算出した積のある成分が所定の範囲内に含まれる場合は、当該成分を前記ワイルドカード記号に変換し、前記成分が所定の範囲内に含まれない場合には、当該成分の値に応じたバイナリ記号に変換することを特徴とする請求項１または２に記載の情報変換装置。
【請求項４】
前記データから複数のデータを抽出する抽出部と、
前記抽出部が抽出したデータの特徴量ベクトル同士の距離と、当該特徴量ベクトルを所定の変換関数で変換した記号列同士のハミング距離とに基づいて、前記所定の変換関数を評価する評価部と、
前記評価部による評価に基づいて、前記所定の変換関数が有するパラメータを最適化する最適化部と
を有し、
前記変換部は、前記最適化部が最適化したパラメータを有する変換関数を用いて、前記データの特徴量ベクトルを前記記号列に変換することを特徴とする請求項１−３のいずれか１つに記載の情報変換装置。
【請求項５】
前記評価部は、前記抽出部が抽出したデータが同一のクラスに属し、かつ、前記記号列同士のハミング距離が所定の値以下となる場合、または、前記抽出部が抽出したデータが異なるクラスに属し、かつ、前記記号列同士のハミング距離が所定の値以上となる場合は、前記変換関数の評価値を下げ、
前記最適化部は、前記評価値の上限が下がるように前記パラメータを最適化することを特徴とする請求項４に記載の情報変換装置。
【請求項６】
前記データと、当該データの特徴量ベクトルから前記変換部が変換した記号列とを対応付けて記憶する記憶部と、
前記記憶部に記憶されたデータのうち、クエリデータを変換したバイナリ列とのハミング距離が所定の値以下となる記号列と対応付けられたデータを検索する検索部と
を有することを特徴とする請求項１−５のいずれか１つに記載の情報変換装置。
【請求項７】
ハミング距離を用いた検索処理の対象となるデータの特徴量ベクトルを、バイナリ記号とのハミング距離を０とするワイルドカード記号と前記バイナリ記号とを含む記号列に変換する変換部と
前記データのうち、前記変換部が変換した記号列と、クエリデータを変換したバイナリ列とのハミング距離が所定の値以下となるデータを検索する検索部と
を有することを特徴とする情報検索装置。
【請求項８】
ハミング距離を用いた検索処理の対象となるデータを管理する情報変換装置が
前記データの特徴量ベクトルを、バイナリ記号とのハミング距離を０とするワイルドカード記号と前記バイナリ記号とを含む記号列に変換する処理を実行することを特徴とする情報変換方法。
【請求項９】
ハミング距離を用いた検索処理を行う情報検索装置が、
前記検索処理の対象となるデータの特徴量ベクトルを、バイナリ記号とのハミング距離を０とするワイルドカード記号と前記バイナリ記号とを含む記号列に変換し
前記変換した記号列と、クエリデータを変換したバイナリ列とのハミング距離が所定の値以下となるデータを検索する
処理を実行することを特徴とする情報検索方法。
【請求項１０】
ハミング距離を用いた検索処理の対象となるデータを管理するコンピュータに
前記データの特徴量ベクトルを、バイナリ記号とのハミング距離を０とするワイルドカード記号と前記バイナリ記号とを含む記号列に変換する処理を実行させることを特徴とする情報変換プログラム。
【請求項１１】
ハミング距離を用いた検索処理を行うコンピュータに、
前記検索処理の対象となるデータの特徴量ベクトルを、バイナリ記号とのハミング距離を０とするワイルドカード記号と前記バイナリ記号とを含む記号列に変換し
前記変換した記号列と、クエリデータを変換したバイナリ列とのハミング距離が所定の値以下となるデータを検索する
処理を実行させることを特徴とする情報検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報変換装置、情報検索装置、情報変換方法、情報検索方法、情報変換プログラム、情報検索プログラムに関する。
【背景技術】
【０００２】
従来、データベースに登録された複数のデータから、入力されたクエリデータとの類似度や関連の強さが所定の条件を満たすデータを検索する技術が知られている。このような技術の一例として、各データ間の類似度や関連の強さを特徴量ベクトルの多次元空間における距離で示し、クエリデータとの距離が閾値以内となるデータや、クエリデータに近い方から所定の数のデータを選択する近傍検索の技術が知られている。
【０００３】
図１２は、従来の近傍検索を説明するための図である。例えば、近傍検索を実行する情報処理装置は、図１２中の白丸で示すように、検索対象となるデータの特徴量ベクトルを記憶する。そして、情報処理装置は、図１２中（Ａ）で示すクエリデータを取得すると、クエリデータと特徴量ベクトルとの距離を算出し、図１２中（Ｂ）に示すように、クエリデータとの距離が所定の範囲内となるデータをクエリデータの近傍データとする。
【０００４】
ここで、データベースに多数のデータが登録されている際に、データベースに登録された全てのデータとクエリデータとの距離を算出した場合は、近傍検索に要する計算コストが増大する。このため、特徴量ベクトル空間のインデックスをあらかじめ作成したり、特定の特徴量ベクトルからの距離を利用したインデックスを用いて、検索対象とするデータを限定することで、近傍検索を実行するための計算コストを削減する技術が知られている。しかし、これらの方法は、特徴量ベクトルの次元数が増大すると、計算コストを削減することができなくなる。
【０００５】
そこで、検索処理における計算コストを削減するため、検索結果の厳密性を緩和し、クエリデータに対して近似的な類似データの集合を取得することで、検索処理を高速化する方法が知られている。例えば、バイナリ列同士の一致検索やハミング距離の計算は、ベクトル間の距離の計算よりも高速に行える。そこで、特徴量ベクトル間の距離関係を保ちつつ特徴量ベクトルをバイナリ列に変換し、クエリデータを変換したバイナリ列との一致検索やハミング距離を計算することで、計算コストを削減する方法が知られている。
【０００６】
ここで、特徴量ベクトルをバイナリ列に変換する方法としては、ランダムな射影関数を適用してデータベースの特徴量ベクトルをバイナリ化する方法が知られている。また、元の特徴量ベクトル同士の距離関係を保存したまま変換するため、予め得られる登録データを利用して、データの分布を考慮した射影関数を決定し、決定した射影関数で特徴量ベクトルをバイナリ化する方法が知られている。
【０００７】
以下、このような特徴量ベクトルをバイナリ列に変換し、クエリデータに類似するデータを検索する方法の一例について説明する。図１３は、バイナリ化による検索処理を説明するための図である。なお、図１３に示す例では、図１３中の白丸で示す特徴量ベクトルを、２桁のバイナリ列に変換する方法について説明する。
【０００８】
例えば、情報処理装置は、図１３中の白丸で示す特徴量ベクトルを記憶する。ここで、情報処理装置は、射影関数を適用し、図１３中の点線よりも上の範囲に含まれる特徴量ベクトルについては、バイナリ列の１桁目を「１」とし、点線よりも下の範囲に含まれる特徴量ベクトルについては、バイナリ列の１桁目を「０」とする。また、情報処理装置は、図１３中の実線よりも右の範囲に含まれる特徴量ベクトルについては、バイナリ列の２桁目を「１」とし、実線よりも左の範囲に含まれる特徴量ベクトルについては、バイナリ列の２桁目を「０」とする。
【０００９】
この結果、各特徴量ベクトルは、「０１」、「１１」、「００」、「１０」のいずれかに変換される。そして、情報処理装置は、図１３中（Ｃ）に示すように、クエリデータを変換したバイナリ列が「１１」となる場合は、ハミング距離が「０」となるバイナリ列、すなわちバイナリ列が「１１」となる特徴量ベクトルをクエリデータの近傍データとする。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００３−２８９３５号公報
【特許文献２】特許第２８１５０４５号公報
【特許文献３】特開２００６−２７７４０７号公報
【特許文献４】特開２００７−２４９３３９号公報
【非特許文献】
【００１１】
【非特許文献１】M.  Datar,  N.  Immorlica,  P.  Indyk,  V.  S.  Mirrokni:  Locality-Sensitive  Hashing  Scheme  Based  on  p-Stable  Distributions,  Proceedings  of  the  twentieth  annual  symposium  on  Computational  geometry  (SCG)  2004
【非特許文献２】Y.  Weiss,  A.  Torralba,  R.  Fergus:  Spectral  Hashing,  Advances  in  Neural  Information  Processing  Systems  (NIPS)  2008
【非特許文献３】B.  Kulis,  T.  Darrell:  Learning  to  Hash  with  Binary  Reconstructive  Embeddings,  Advances  in  Neural  Information  Processing  Systems  (NIPS)  2009
【非特許文献４】Norouzi,  D.  Fleet:  Minimal  Loss  Hashing  for  Compact  Binary  Codes,  International  Conference  in  Machine  Learning  (ICML)  2011
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかし、上述した特徴量ベクトルをバイナリ列に変換する技術では、１つの特徴量ベクトルを１つのバイナリ列にマッピングするので、類似する特徴量ベクトルについてのバイナリ列の距離が離れてしまい、検索漏れが発生するという問題がある。
【００１３】
図１４は、従来の問題を説明するための図である。例えば、情報処理装置は、図１４中（Ｄ）に示すクエリデータが入力された場合は、図１４中右側の斜線で示すように、バイナリ列が「１１」となる特徴量ベクトルのデータを抽出する。しかし、情報処理装置は、図１４中右側の白丸で示すように、クエリデータの近傍となる特徴量ベクトルであって、バイナリ列が「１１」にならない特徴量ベクトルを抽出しない。この結果、情報処理装置は、検索漏れを生じさせてしまう。
【００１４】
本発明は、１つの側面では、特徴量ベクトルをバイナリ列に変換した際の検索精度を向上させる。
【課題を解決するための手段】
【００１５】
１つの側面では、ハミング距離を用いた検索処理の対象となるデータの特徴量ベクトルを、バイナリ記号とのハミング距離を０とするワイルドカード記号と前記バイナリ記号とを含む記号列に変換する情報変換装置である。
【発明の効果】
【００１６】
１つの側面では、特徴量ベクトルをバイナリ列に変換した際の検索精度を向上させる。
【図面の簡単な説明】
【００１７】
【図１】図１は、実施例１に係る情報検索装置の機能構成を説明するための図である。
【図２】図２は、生体認証の一例を説明するための図である。
【図３】図３は、特徴量ベクトル記憶部が記憶する情報の一例を説明するための図である。
【図４】図４は、記号列データインデックス記憶部が記憶する情報の一例を説明するための図である。
【図５】図５は、変換関数がワイルドカード記号に変換する成分を説明するための図である。
【図６】図６は、記号列間の距離関係が保たれるように変換関数を更新する処理を説明するための図である。
【図７】図７は、変換関数の一例を説明するための図である。
【図８】図８は、クエリデータの近傍候補となる特徴量ベクトルの記号列を抽出する処理を説明するための図である。
【図９】図９は、検索部が記憶するハッシュテーブルの一例を説明するための図である。
【図１０】図１０は、変換関数を生成する処理の流れについて説明するためのフローチャートである。
【図１１】図１１は、情報変換プログラムを実行するコンピュータの一例を説明するための図である。
【図１２】図１２は、従来の近傍検索を説明するための図である。
【図１３】図１３は、バイナリ化による検索処理を説明するための図である。
【図１４】図１４は、従来の問題を説明するための図である。
【発明を実施するための形態】
【００１８】
以下に添付図面を参照して本願に係る情報変換装置、情報検索装置、情報変換方法、情報検索方法、情報変換プログラム、情報検索プログラムについて説明する。
【実施例１】
【００１９】
以下の実施例１では、図１を用いて、バイナリ化した特徴量ベクトルを用いて、クエリデータの近傍データを検索する情報検索装置について説明する。図１は、実施例１に係る情報検索装置の機能構成を説明するための図である。図１に示す例では、情報検索装置１は、特徴量ベクトル記憶部１０、記号列データインデックス記憶部１１、変換関数学習部１２、特徴量変換部１３、検索部１４を有する。
【００２０】
また、情報検索装置１は、クエリデータを入力するクライアント装置２と接続されている。そして、情報検索装置１は、クライアント装置２からクエリデータを受信すると、受信したクエリデータの近傍データを検索し、検索した近傍データをクライアント装置２へ送信する。ここで、情報検索装置１が検索対象とするデータは、例えば、画像や音声などのデータであり、指紋のパターンや静脈のパターンを用いた生体認証における生体データである。
【００２１】
図２は、生体認証の一例を説明するための図である。なお、図２に示す例では、利用者のＩＤ（Identification）等の情報が入力されず、検索対象となる生体データの絞込みを行わないＩＤレスの１：Ｎ認証における処理を示す。図２に示すように、情報検索装置１は、複数の利用者が登録した登録生体データを複数記憶する。
【００２２】
そして、情報検索装置１は、クライアント装置２からクエリデータとして、生体データが入力されると、入力された生体データの特徴量を示す特徴量ベクトルを抽出し、抽出した特徴量ベクトルと類似する特徴量ベクトルを有する登録生体データを検索する。すなわち、情報検索装置１は、クエリデータを入力した利用者の登録生体データが登録されているか否かを判別する。
【００２３】
また、情報検索装置１は、登録生体データの特徴量ベクトルを変換した記号列と、クエリデータとして入力された生体データにおける特徴量ベクトルをバイナリ化した記号列とのハミング距離を算出する。そして、情報検索装置１は、ハミング距離が所定の閾値以下となる登録生体データを検索対象の候補として抽出する。その後、情報検索装置１は、検索した登録生体データとクエリデータとして入力された生体データとの厳密なマッチング処理を実行し、実行結果を出力する。
【００２４】
このように、情報検索装置１は、検索対象となる登録生体データの特徴を示す特徴量ベクトルを記号列に変換し、クエリデータの記号列とのハミング距離を算出することにより、検索対象とするデータの絞込みを行う。そして、情報検索装置１は、絞り込んだデータとクエリデータとのマッチングを行うことで、生体認証におけるマッチングを行う。
【００２５】
なお、入力された生体データや登録生体データが画像である場合には、特徴量ベクトルは、例えば、画像中の特定領域における隆線の方向や長さ、勾配、隆線の終端や分岐などの特徴的な点の密度や座標の数値をベクトル化したものとなる。また、入力された生体データや登録生体データが音声である場合には、特徴量ベクトルは、例えば、周波数成分の分布、強度、ピーク値などの数値をベクトル化したものとなる。
【００２６】
ここで、検索対象となる登録生体データを「０」または「１」からなるバイナリ列に変換した場合には、特徴量ベクトル同士の距離関係が反映されない場合がある。そこで、情報検索装置１は、バイナリ記号とのハミング距離が「０」となるワイルドカード記号とバイナリ記号とを含む記号列に変換する。そして、情報検索装置１は、バイナリ記号とワイルドカード記号とを含む記号列と、クエリデータの特徴量ベクトルを変換した記号列とのハミング距離が、所定の閾値以下となる登録生体データを検索対象の候補として検索することで、検索精度を向上させる。
【００２７】
以下、図１に示す情報検索装置１が実行する処理について具体的に説明する。特徴量ベクトル記憶部１０は、登録生体データの特徴量ベクトルを記憶する。具体的には、特徴量ベクトル記憶部１０は、登録生体データの特徴量ベクトルと、登録生体データを登録した利用者の識別子であるデータＩＤとを対応付けて記憶する。
【００２８】
ここで、図３を用いて、特徴量ベクトル記憶部１０が記憶する情報の一例について説明する。図３は、特徴量ベクトル記憶部が記憶する情報の一例を説明するための図である。例えば、図３に示す例では、特徴量ベクトル記憶部１０は、データＩＤ「１」と複数の特徴量ベクトルとして、太字の「ａ」、「ｂ」、「ｃ」を対応付けて記憶する。なお、図３では省略したが、特徴量ベクトル記憶部１０は、データＩＤ「１」と対応付けて、他の特徴量ベクトルを記憶する。また、特徴量ベクトル記憶部１０は、他のデータＩＤと対応付けた特徴量ベクトルを記憶する。
【００２９】
このように、特徴量ベクトル記憶部１０は、複数の登録生体データの特徴量ベクトルを、データＩＤごと、すなわち、登録生体データを登録した利用者ごとに記憶する。以下の説明では、同一のデータＩＤに対応付けられた特徴量ベクトル、すなわち、同一の利用者が登録した登録生体データの特徴量ベクトルを、同一のクラスに属する特徴量ベクトルと記載する。
【００３０】
図１に戻って、記号列データインデックス記憶部１１は、所定の変換関数を用いて特徴量ベクトルを変換した記号列であって、バイナリ記号とワイルドカード記号とを含む記号列とデータＩＤとを対応付けて記憶する。以下、図４を用いて、記号列データインデックス記憶部１１が記憶する情報の一例について説明する。
【００３１】
図４は、記号列データインデックス記憶部が記憶する情報の一例を説明するための図である。例えば、図４に示す例では、記号列データインデックス記憶部１１は、データＩＤ「１」と対応付けて、記号列「０１＊１０１＊０１１０…」を記憶する。ここで、記号列中の「＊」は、ワイルドカード記号である。
【００３２】
なお、図４では記載を省略したが、記号列データインデックス記憶部１１は、データＩＤ「１」と対応付けて、他にも複数の記号列を記憶する。すなわち、記号列データインデックス記憶部１１は、特徴量ベクトル記憶部１０がデータＩＤと対応付けて記憶する特徴量ベクトルを、ぞれぞれ変換した複数の記号列を、データＩＤごとに記憶する。
【００３３】
図１に戻って、変換関数学習部１２は、特徴量ベクトル記憶部１０が記憶する特徴量ベクトルをバイナリ記号とワイルドカード記号とを含む記号列に変換し、変換後の記号列を記号列データインデックス記憶部１１に格納する。
【００３４】
具体的には、変換関数学習部１２は、あるクラスに属する特徴量ベクトルのある成分が、異なるクラスの特徴量ベクトルとの境界から所定の範囲内に収まる場合は、この成分をワイルドカード記号に変換する変換関数を生成する。また、変換関数学習部１２は、あるクラスに属する特徴量ベクトルのある成分が、異なるクラスの特徴量ベクトルとの境界から所定の範囲内に収まらない場合は、この成分の値に応じたバイナリ記号に変換する変換関数を生成する。
【００３５】
詳細には、変換関数学習部１２は、特徴量ベクトルと所定の変換行列との積を算出し、算出した積のある成分が所定の範囲内に含まれる場合には、この成分をワイルドカード記号に変換する変換関数を生成する。また、変換関数学習部１２は、特徴量ベクトルと所定の変換行列との積を算出し、算出した積のある成分が所定の範囲内に含まれない場合には、この成分の値に応じたバイナリ記号に変換する変換関数を生成する。
【００３６】
そして、変換関数学習部１２は、生成した変換関数を用いて、特徴量ベクトル記憶部１０が記憶する特徴量ベクトルを記号列に変換し、変換後の記号列を記号列データインデックス記憶部１１に格納する。
【００３７】
なお、変換関数学習部１２は、特徴量ベクトル記憶部１０が予め記憶する特徴量ベクトルを用いて、変換関数の生成を行う。具体的には、変換関数学習部１２は、特徴量ベクトル記憶部１０が記憶する特徴量ベクトルを２つ抽出し、一方をクエリデータとみなし、もう一方を検索対象となるデータの特徴量ベクトルとみなす。
【００３８】
そして、変換関数学習部１２は、抽出した２つの特徴量ベクトル同士のユークリッド距離（ノルム）を算出する。また、変換関数学習部１２は、所定の変換関数を用いて、抽出した物理量ベクトルを記号列に変換し、変換後の記号列におけるハミング距離を算出する。そして、変換関数学習部１２は、算出したユークリッド距離とハミング距離とに基づいて、物理量ベクトルを変換した変換関数を評価する。その後、変換関数学習部１２は、変換関数の評価結果に基づいて、変換関数が有するパラメータを変更する。
【００３９】
また、変換関数学習部１２は、再度２つの特徴量ベクトルを抽出し、パラメータを変更した変換関数を用いて、抽出した特徴量ベクトルを記号列に変換する。また、変換関数学習部１２は、再度抽出した物理量ベクトルのユークリッド距離と記号列におけるハミング距離とに基づいて、変換関数を評価し、評価結果に基づいて、変換関数が有するパラメータを変更する。
【００４０】
そして、上述した処理を複数回繰り返すことにより、変換関数学習部１２は、変換関数が有するパラメータを最適化する。その後、変換関数学習部１２は、パラメータを最適化した変換関数を用いて、特徴量ベクトル記憶部１０が記憶する特徴量ベクトルを記号列に変換し、変換後の記号列を記号列データインデックス記憶部１１に格納する。
【００４１】
次に、図５、図６を用いて、変換関数学習部１２が生成する変換関数について説明する。まず、図５を用いて、変換関数がワイルドカード記号に変換する特徴量ベクトルの成分について説明する。
【００４２】
図５は、変換関数がワイルドカード記号に変換する成分を説明するための図である。なお、図５に示す例では、２次元の特徴量ベクトルを記号列に変換する例を記載した。また、図５に示す例では、それぞれ異なるクラスに属する特徴量ベクトルを異なる斜線で示した。また、図５中では、変換行列Ｗと特徴量ベクトルｘとの積が「０」となる境界線を直線で示した。
【００４３】
例えば、従来の方法では、図５中の直線よりも右側の範囲に含まれる特徴量ベクトルを記号列「０」に変換し、図５中の直線よりも左側の範囲に含まれる特徴量ベクトルを記号列「１」に変換する。しかし、このような閾値による画一的な変換を行った場合には、異なるクラスの特徴量ベクトルとの境界に存在する特徴量ベクトル、すなわち境界線の近傍に存在する特徴量ベクトルを、同一クラスの特徴量ベクトルとは異なる記号列に変換してしまう。この結果、従来の方法では、異なるクラスの特徴量ベクトルとの境界に存在する特徴量ベクトルの検索漏れが発生する。
【００４４】
そこで、情報検索装置１は、変換行列Ｗと特徴量ベクトルｘとの積が「０」となる境界線から所定の範囲内に含まれる特徴量ベクトルを、ワイルドカード記号「＊」に変換する。ここで、ワイルドカード記号「＊」は、ハミング距離の算出において、バイナリ記号「１」または「０」との距離が「０」であると判断される。このため、情報検索装置１０は、変換行列Ｗと特徴量ベクトルｘとの積が「０」となる境界線の近傍となる特徴量ベクトルを検索結果に含めるため、検索漏れを防ぐことができる。
【００４５】
例えば、図５中の薄い網掛けで示す特徴量ベクトルをクラスＡの特徴量ベクトルとし、濃い網掛けで示す特徴量ベクトルをクラスＢの特徴量ベクトルとする。すると、クラスＡの特徴量ベクトルの多くは、記号列「０」に変換され、クラスＢの特徴量ベクトルとの境界に近い特徴量ベクトルは、ワイルドカード記号「＊」に変換される。このため、情報検索装置１０は、クエリデータを変換した記号列が「０」である際に、記号列「０」に変換された特徴量ベクトルだけではなく、記号列「＊」に変換した特徴量ベクトルも検索結果に含める。この結果、情報検索装置１０は、クラスＡに属する特徴量ベクトルの検索漏れを防ぐことができる。
【００４６】
次に、図６を用いて、変換関数学習部１２が変換関数を繰り返し評価し、パラメータを変更することによって、変換関数を最適化する処理について説明する。図６は、記号列間の距離関係が保たれるように変換関数を更新する処理を説明するための図である。図６に示す例では、図５と同様に、それぞれ異なるクラスに属する２次元の特徴量ベクトルを異なる斜線で示した。また、図６に示す例では、３つの閾値を用いて、２次元の特徴量ベクトルを３桁の記号列に変換する例について記載した。
【００４７】
図６に示すように、初期状態の変換関数は、各クラスに属する特徴量ベクトルを記号列に変換する境界線が各クラスの特徴量ベクトルを上手く分割することができない。そこで、変換関数学習部１２は、任意の２つの特徴量ベクトルを抽出し、抽出した特徴量ベクトルのユークリッド距離と、特徴量ベクトルを変換した記号列のハミング距離とに応じて、変換関数を評価する。
【００４８】
具体的には、変換関数学習部１２は、特徴量ベクトル同士のユークリッド距離が短い際に、変換後の記号列におけるハミング距離を短くし、特徴量ベクトル同士のユークリッド距離が長い際に、変換後の記号列におけるハミング距離が長くなるように変換関数を更新する。また、抽出した特徴量ベクトルが同一のクラスに属する場合は、特徴量ベクトル同士のユークリッド距離が短くなる。このため、変換関数学習部１２は、特徴量ベクトル同士のユークリッド距離が短い場合に、記号列におけるハミング距離を短くした場合は、同一クラスに属する特徴量ベクトルを変換した記号列におけるハミング距離を短くできる。
【００４９】
この結果、変換関数学習部１２は、図６の右側に示すように、各クラスに属する特徴量ベクトルが境界線によって上手く分割できるように、変換関数を更新する。さらに、変換関数学習部１２は、変換関数を更新する際に、ワイルドカード記号「＊」に変換する範囲の更新も行う。この結果、変換関数学習部１２は、特徴量ベクトルを記号列に変換し、クエリデータを変換した記号列とのハミング距離を算出する際の検索漏れを防ぐことができる。
【００５０】
また、変換関数学習部１２は、特徴量ベクトル記憶部１０が記憶する特徴量ベクトルを用いて、変換関数を更新する。このため、変換関数学習部１２は、検索対象となるデータに対して最適化された変換関数を求めることができる。なお、変換関数学習部１２は、抽出した特徴量ベクトル同士のユークリッド距離や、抽出した特徴量ベクトルを変換した記号列のハミング距離だけではなく、抽出した特徴量ベクトルが属するクラスを考慮して、変換関数の最適化を行ってもよい。
【００５１】
次に、変換関数学習部１２が所定の変換関数を更新し、最適化した変換関数を生成する処理の具体例について説明する。なお、以下の説明では、変換関数学習部１２が生成する変換関数について説明し、その後、変換関数の評価結果に基づいて、変換関数の各パラメータを変更し、変換関数を最適化する処理について説明する。
【００５２】
まず、変換関数隔週部１２が生成する変換関数について説明する。例えば、変換関数学習部１２は、特徴量ベクトルをバイナリ記号とワイルドカード記号とを有する記号列に変換する場合は、変換後の記号列ｃは、以下の式（１）で表せる。なお、式（１）中のｐは、記号列の記号数（次元数）である。
【００５３】
【数１】
2013206187.tif 000003
【００５４】
次に、記号列ｃｉとｃｊの記号列間のハミング距離ｍｉｊを以下の式（２）のように定義する。ここで、式（２）中のｓ（ｃｋｉ，ｃｋｊ）は、以下の式（３）で表される値であり、ｃｋとは、記号列ｃにおけるｋ番目の記号である。また、以下の式においては、記号列ｃを太字で示した。
【００５５】
【数２】
2013206187.tif 000004
【００５６】
【数３】
2013206187.tif 000005
【００５７】
ここで、変換関数には、様々なバリエーションが考えられるが、例えば、変換関数学習部１２は、以下の式（４）に示す変換関数を設定する。ここで、ｕｋは、記号列ｕにおけるｋ番目の値である。なお、以下の式においては、記号列ｕを太字で示した。
【００５８】
【数４】
2013206187.tif 000006
【００５９】
また、記号列ｕは、以下の式（５）で定義される記号列である。なお、式（５）中の太字のｘはｎ次元の特徴量ベクトルであり、太字のＷは行数ｎ、列数ｐで表される変換行列である。また、式（５）中の太字のａ１、ａ２、ｂ１、ｂ２は、ｐ次元のベクトルである。なお、ａ１、ａ２、ｂ１、ｂ２は、ワイルドカード記号に変換する範囲を定める変換関数のパラメータであり、各要素が「０」以上の値を有するものとする。また、太字のｈ＋、ｈ−は、各要素が「０」または「１」となるｐ次元のベクトルであり、太字のｇ＋、ｇ−は、各要素が「０」または「−１」となるｐ次元のベクトルである。
【００６０】
【数５】
2013206187.tif 000007
【００６１】
すなわち、変換関数学習部１２は、式（５）における各項において、変換行列と特徴量ベクトルとの積に各パラメータを考慮した値が最大となるｈ＋、ｈ−、ｇ＋、ｇ−を求め、求めたｈ＋、ｈ−、ｇ＋、ｇ−を用いてベクトルｕを算出する。
【００６２】
ここで、図７は、変換関数の一例を説明するための図である。なお、図７には、式（５）で示される記号列ｕを式（４）で示す変換関数で変換した際に、２次元の特徴量ベクトルが「０」、「１」、「＊」のいずれに変換されるかを示した。詳細には、式（５）中における特徴量ベクトルと変換行列との積が定めるバイナリ記号と、式（５）中における各パラメータａ１、ａ２、ｂ１、ｂ２が定めるワイルドカード記号に変換する範囲について記載した。
【００６３】
例えば、図７に示すように、−Ｗｘ−ａ１＋ｂ１＝０を満たす範囲からＷｘ＋ａ１＋ｂ１＝０を満たす範囲に含まれる特徴量ベクトルは、バイナリ記号「１」に変換される。また、Ｗｘ＋ａ１＋ｂ１＝０を満たす範囲からＷｘ−ａ２−ｂ２＝０を満たす範囲に含まれる特徴量ベクトルは、ワイルドカード記号「＊」に変換される。すなわち、特徴量ベクトルと変換行列との積であるＷｘが０となる境界から所定の範囲に含まれる特徴量ベクトルをワイルドカード記号「＊」に変換する。
【００６４】
また、Ｗｘ−ａ２−ｂ２＝０を満たす範囲から−Ｗｘ＋ａ２−ｂ２＝０を満たす範囲に含まれる特徴量ベクトルは、バイナリ記号「０」に変換される。また、−Ｗｘ−ａ１＋ｂ１が０以下となる範囲や、−Ｗｘ＋ａ２−ｂ２が０以上となる範囲に含まれる特徴量ベクトルは、ワイルドカード記号「＊」に変換される。
【００６５】
次に、変換関数学習部１２が変換関数の評価結果に基づいて、変換関数の各パラメータａ１、ａ２、ｂ１、ｂ２を変更し、変換関数を最適化する処理について説明する。例えば、情報検索装置１が用いる変換関数は、元の特徴量ベクトル空間における距離関係をできるだけ保存したまま、特徴量ベクトルを記号列に変換する変換関数が望ましい。
【００６６】
そこで、例えば、変換関数学習部１２は、以下の式（６）で示す評価関数を用いて、変換関数を評価することができる。ここで、式（６）中のｄｉｊは、特徴量ベクトルｉと特徴量ベクトルｊとのユークリッド距離である。また、式（６）中のＳは、特徴量ベクトル記憶部１０が記憶する特徴量ベクトルのデータ集合である。
【００６７】
【数６】
2013206187.tif 000008
【００６８】
つまり、変換関数学習部１２は、式（６）を用いて、特徴量空間でのユークリッド距離の関係と記号列間の距離の関係とが似ているほどよいと変換関数を評価する。また、他の例として、変換関数学習部１２は、以下の式（７）を用いて、変換関数を評価する。ここで、式（７）中のｌ２（ｍｉｊ，ｔｉｊ）は、以下の式（８）で表される値である。また、式（７）、式（８）中のｔは特徴量ベクトルｉと特徴量ベクトルｊとが同一のクラスに属する特徴量ベクトルである場合は、「１」となり、異なるクラスであれば「０」となる変数である。
【００６９】
【数７】
2013206187.tif 000009
【００７０】
【数８】
2013206187.tif 000010
【００７１】
つまり、変換関数学習部１２は、式（７）および式（８）を用いて、同一クラスの特徴量ベクトルについては記号列間のハミング距離が「ρ」以内となるようにし、異なるクラスの特徴量ベクトルについては、記号列間のハミング距離が「ρ」以上となるようにする。以下の説明では、変換関数学習部１２が式（７）および式（８）を用いて変換関数を評価する例について説明する。
【００７２】
ここで、式（７）および式（８）は、同一クラスの特徴量ベクトルについては記号列間のハミング距離が「ρ」以内となるようにし、異なるクラスの特徴量ベクトルについては、記号列間のハミング距離が「ρ」以上となる変換関数に対して、より低い値となる。このため、変換関数学習部１２は、評価関数である式（７）の値が小さくなるように、変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２を最適化すればよい。
【００７３】
ここで、評価関数である式（７）は、不連続な関数である。このため、式（７）の上限値を最小化する場合について考える。例えば、変換関数学習部１２は、特徴量ベクトルｉを登録データとし、特徴量ベクトルｊをクエリデータと考える。ここで、クエリデータをバイナリ列に変換する変換式を以下の式（９）で定義する。なお、式（９）中のｘｑは、クエリデータとなる特徴量ベクトルである。
【００７４】
【数９】
2013206187.tif 000011
【００７５】
すると、評価関数である式（７）の上限値は、以下の式（１０）で表すことができる。
【００７６】
【数１０】
2013206187.tif 000012
【００７７】
ここで、式（１０）の第１項目について考えると、ｌ２（ｍｉｊ，ｔｉｊ）は、ｈi＋、ｈi−、ｈｊ、ｇi＋、ｇi−とは無関係な値であるので、以下の式（１１）のように書くことができる。
【００７８】
【数１１】
2013206187.tif 000013
【００７９】
ここで、式（１１）に示す演算を満たすｈi＋、ｈi−、ｈｊ、ｇi＋、ｇi−をそれぞれの記号上に波線を付した記号で表すと、式（１０）の右辺は、以下の式（１２）で表すことができる。
【００８０】
【数１２】
2013206187.tif 000014
【００８１】
ただし、ｈi＋、ｈi−、ｈｊ、ｇi＋、ｇi−のｍａｘ演算については、以下の式（１３）〜式（１７）で示す変換を行った。
【００８２】
【数１３】
2013206187.tif 000015
【００８３】
【数１４】
2013206187.tif 000016
【００８４】
【数１５】
2013206187.tif 000017
【００８５】
【数１６】
2013206187.tif 000018
【００８６】
【数１７】
2013206187.tif 000019
【００８７】
続いて、変換関数学習部１２が確率的勾配降下法を用いて、式（１２）の変換行列と各パラメータを最適化する。具体的には、変換関数学習部１２は、以下の式（１８）〜式（２２）を用いて、変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２を順次更新し、式（７）の上限値を最小化する。なお、式（１８）〜式（２２）中のηは、学習率を示すパラメータである。
【００８８】
【数１８】
2013206187.tif 000020
【００８９】
【数１９】
2013206187.tif 000021
【００９０】
【数２０】
2013206187.tif 000022
【００９１】
【数２１】
2013206187.tif 000023
【００９２】
【数２２】
2013206187.tif 000024
【００９３】
上述したように、変換関数学習部１２は、特徴量ベクトル記憶部１０から特徴量ベクトルを抽出し、式（１８）〜式（２２）を計算する処理を所定の回数だけ繰り返す。そして、変換関数学習部１２は、変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２を順次更新することで、式（７）の上限値を最小化する変換行列およびパラメータを算出する。すなわち、変換関数学習部１２は、変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２を最適化する。
【００９４】
その後、変換関数学習部１２は、最適化した変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２を用いて、特徴量ベクトル記憶部１０が記憶する特徴量ベクトルを記号列に変換し、変換した記号列を記号列データインデックス記憶部１１に格納する。また、変換関数学習部１２は、最適化した変換行列Ｗを特徴量変換部１３に通知する。
【００９５】
なお、上述した説明では、確率的勾配降下法を用いて変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２を最適化する例について説明したが、変換関数学習部１２は、他の最適化アルゴリズムを用いて、式（７）の上限値を最小化してもよい。
【００９６】
また、変換関数学習部１２は、上述した処理を所定の回数だけ繰り返すことにより、変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２を最適化した。しかしながら、変換関数学習部１２は、所定の条件を満たした際に、変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２を最適化したと判別してもよい。例えば、変換関数学習部１２は、式（７）で示される評価関数の値が所定の閾値以下となった際に、変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２を最適化したと判別してもよい。
【００９７】
図１に戻って、特徴量変換部１３は、クライアント装置２からクエリデータを受信すると、受信したクエリデータから特徴量ベクトルを生成する。また、特徴量変換部１３は、変換関数学習部１２から受信した変換行列Ｗと、式（９）とを用いて、クエリデータをバイナリ列ｂｑに変換する。そして、特徴量変換部１３は、特徴量ベクトルとバイナリ列ｂｑとを検索部１４に送信する。
【００９８】
検索部１４は、特徴量変換部１３から特徴量ベクトルとバイナリ列ｂｑとを受信した場合には、以下の処理を実行する。まず、検索部１４は、受信したバイナリ列ｂｑと記号列データインデックス記憶部１１が記憶する各記号列とのハミング距離を算出する。例えば、検索部１４は、受信したバイナリ列ｂｑが「１１０１００」であり、記号列が「１１０１１０」である場合には、ハミング距離「１」を算出する。また、検索部１４は、ワイルドカード記号とバイナリ記号とのハミング距離を「０」とするので、受信したバイナリ列ｂｑが「１１０１００」であり、記号列が「１００１＊０」である場合には、ハミング距離「１」を算出する。
【００９９】
そして、検索部１４は、ハミング距離が所定の値以下となる記号列、すなわち、クエリデータの近傍候補となる特徴量ベクトルの記号列を抽出する。また、検索部１４は、抽出した記号列の元となる特徴量ベクトルを特徴量ベクトル記憶部１０から取得し、抽出した特徴量ベクトルと、特徴量ベクトル記憶部１０から取得した特徴量ベクトルとを比較する。
【０１００】
その後、検索部１４は、特徴量ベクトル記憶部１０から取得した特徴量ベクトルに、特徴量変換部１３から取得した特徴量ベクトルと一致する特徴量ベクトルや、ユークリッド距離が所定の閾値以下となる特徴量ベクトルが存在する場合は、以下の処理を実行する。すなわち、検索部１４は、クエリデータが登録生体データに一致する旨をクライアント装置２へ送信する。
【０１０１】
一方、検索部１４は、特徴量ベクトル記憶部１０から取得した特徴量ベクトルに、特徴量変換部１３から取得した特徴量ベクトルと一致する特徴量ベクトルや、ユークリッド距離が所定の閾値以下となる特徴量ベクトルが存在しない場合は、以下の処理を実行する。すなわち、検索部１４は、クエリデータが登録生体データに一致しない旨をクライアント装置２へ送信する。この結果、クライアント装置２は、クエリデータを入力した利用者の生体認証を行うことができる。
【０１０２】
ここで、図８を用いて、検索部１４がクエリデータの近傍候補となる特徴量ベクトルの記号列を抽出する処理について説明する。図８は、クエリデータの近傍候補となる特徴量ベクトルの記号列を抽出する処理を説明するための図である。なお、図８に示す例では、情報検索装置１は、特徴量ベクトルを「１１」、「１０」、「００」、「０１」のいずれかの記号列に変換するとともに、図８中の網掛け部分に位置する特徴量ベクトルについては、ワイルドカード記号を含む記号列に変換する。
【０１０３】
すなわち、情報検索装置１は、記号列に変換する際の閾値の境界から所定の範囲内にある特徴量ベクトルについては、ワイルドカード記号を含む記号列に変換する。例えば、検索部１４は、特徴量変換部１３から、図８中（Ｅ）に示す特徴量ベクトルを受信した場合には、記号列が「１１」に変換される特徴量ベクトルを抽出する。さらに、検索部１４は、ワイルドカード記号とバイナリ記号とのハミング距離を「０」とするので、図８中の網掛けで示す範囲に含まれる特徴量ベクトルを抽出する。
【０１０４】
この結果、検索部１４は、図８の下側に白丸で示す特徴量ベクトルについては、クエリデータの近傍候補から除外し、図８の下方に網掛け入りの丸で示す特徴量ベクトルについては、クエリデータの近傍候補とする。この結果、情報検索装置１は、検索漏れを防ぐことができる。
【０１０５】
また、検索部１４は、クエリデータを変換したバイナリ列と、特徴量ベクトルを変換した記号列とのハミング距離を算出することで、クエリデータの近傍候補となる特徴量ベクトルを抽出する。そして、検索部１４は、抽出した特徴量ベクトルとクエリデータの特徴量ベクトルとのユークリッド距離を算出する。この結果、検索部１４は、検索処理に要する検索コストを削減できる。
【０１０６】
なお、検索部１４は、ハッシュテーブルを用いて検索処理をさらに高速化してもよい。そこで、図９を用いて、検索部１４がハッシュテーブルを用いて検索処理を行う例について説明する。
【０１０７】
図９は、検索部が記憶するハッシュテーブルの一例を説明するための図である。例えば、図９に示す例では、検索部１４は、各記号列と対応付けて、対応付けられた記号列の元となる特徴量ベクトルの近傍に存在する特徴量ベクトルのデータＩＤを記憶する。例えば、検索部１４は、記号列データインデックス記憶部１１に格納された記号列ｃを取得する。また、検索部１４は、記号列ｃに含まれるｒ個のワイルドカード記号「＊」をバイナリ記号「１」または「０」に変換した２ｒ通りのバイナリ列を生成する。
【０１０８】
また、検索部１４は、生成したバイナリ列に対して、元となる記号列の変換元である特徴量ベクトルの近傍に存在する特徴量ベクトルのデータＩＤを対応付けたハッシュテーブルを生成する。そして、検索部１４は、クエリデータの特徴量ベクトルを変換したバイナリ列を受信した場合には、受信したバイナリ列と対応付けられたデータＩＤをハッシュテーブルから取得する。その後、検索部１４は、ハッシュテーブルから取得したデータＩＤと対応付けられた特徴量ベクトルを特徴量ベクトル記憶部１０から取得し、クエリデータの特徴量ベクトルとのユークリッド距離を算出する。
【０１０９】
このように、検索部１４は、記号列と記号列の元となる特徴量ベクトルの近傍に存在する特徴量ベクトルのデータＩＤとを対応付けたハッシュテーブルを記憶する。この結果、検索部１４は、さらに高速に検索処理を実行することができる。
【０１１０】
例えば、変換関数学習部１２、特徴量変換部１３、検索部１４とは、電子回路である。ここで、電子回路の例として、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路、またはＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などを適用する。
【０１１１】
また、特徴量ベクトル記憶部１０、記号列データインデックス記憶部１１とは、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ（flash  memory）などの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。
【０１１２】
次に、図１０を用いて、情報検索装置１が、変換関数を生成する処理の流れについて説明する。図１０は、変換関数を生成する処理の流れについて説明するためのフローチャートである。なお、情報検索装置１は、図１では図示しなかった外部装置から特徴量ベクトル記憶部１０に新たな特徴量ベクトルが登録されたことをトリガとして、処理を開始する。
【０１１３】
まず、情報検索装置１は、特徴量ベクトル記憶部１０から、任意の２つの特徴量ベクトルを学習用データとして抽出する（ステップＳ１０１）。次に、情報検索装置１は、変換関数を初期化する（ステップＳ１０２）。すなわち、情報検索装置１は、変換関数の変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２の値を所定の初期値に設定する。そして、情報検索装置１は、現在の変換関数の評価を行う（ステップＳ１０３）。すなわち、情報検索装置１は、抽出した学習用データを現在の変換関数を用いて記号列に変換し、変換後の記号列同士のハミング距離と、学習用データのユークリッド距離とを用いて、現在の変換関数の評価を行う。
【０１１４】
そして、情報検索装置１は、ステップＳ１０３における評価結果を用いて、現在の変換関数の変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２の値を更新する（ステップＳ１０４）。次に、情報検索装置１は、終了条件を満足しているか否かを判別する（ステップＳ１０５）。例えば、情報検索装置１は、所定の回数だけ、ステップＳ１０３〜ステップＳ１０４の処理を実行したか否か、または、式（７）が示す評価値が所定の閾値以下となったか否かを判別する。
【０１１５】
そして、情報検索装置１は、終了条件を満足している場合は（ステップＳ１０５肯定）、更新後の変換関数を用いて特徴量ベクトルを変換し（ステップＳ１０６）、処理を終了する。一方、情報検索装置１は、終了条件を満足していない場合は（ステップＳ１０５否定）、ステップＳ１０３の処理を実行する。
【０１１６】
［実施例１の効果］
上述したように、情報検索装置１は、ハミング距離を用いた検索処理の対象となるデータの特徴量ベクトルを、ワイルドカード記号とバイナリ記号とを含む記号列に変換する。このため、情報検索装置１は、記号列に変換する際の閾値の近傍に存在する特徴量ベクトルを検索候補に含めるので、検索漏れを防げる。
【０１１７】
また、情報検索装置１は、特徴量ベクトルのある成分が異なるクラスの特徴量ベクトルとの境界から所定の範囲内に収まる場合は、この成分をワイルドカード記号「＊」に変換する。また、情報検索装置１は、特徴量ベクトルのある成分が異なるクラスの特徴量ベクトルとの境界から所定の範囲内に収まらない場合は、この成分をバイナリ記号に変換する。このため、情報検索装置１は、検索漏れが発生しないように、特徴量ベクトルを記号列に変換できる。
【０１１８】
また、情報検索装置１は、変換行列と特徴量ベクトルとの積について、ある成分が所定の範囲内に含まれる場合は、この成分をワイルドカード記号「＊」に変換し、この成分が所定の範囲内に含まれない場合は、この成分の値に応じたバイナリ記号に変換する。このため、情報検索装置１は、特徴量ベクトルの分布に応じた変換行列を選択した際に、検索漏れを防ぎつつ、特徴量ベクトルの位置関係を保持したままで特徴量ベクトルを記号列に変換できる。
【０１１９】
また、情報検索装置１は、特徴量ベクトル記憶部１０から２つの特徴量ベクトルを抽出し、抽出した特徴量ベクトル同士のユークリッド距離と、特徴量ベクトルを所定の変換関数で変換した記号列同士のハミング距離とに基づいて、所定の変換関数を評価する。そして、情報検索装置１は、評価結果に基づいて、所定の変換関数が有する変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２の値を更新する。このため、情報検索装置１は、特徴量ベクトル記憶部１０に記憶された特徴量ベクトルの分布ごとに最適な変換関数を用いて、特徴量ベクトルを記号列に変換できる。
【０１２０】
また、情報検索装置１は、変換関数を評価する際に、特徴量ベクトル記憶部１０から抽出した特徴量ベクトルが同一クラスの特徴量ベクトルであり、かつ、変換後の記号列同士のハミング距離が所定の値以下となる場合は、変換関数の評価値を下げる。また、情報検索装置１は、変換関数を評価する際に、特徴量ベクトル記憶部１０から抽出した特徴量ベクトルが異なるクラスの特徴量ベクトルであり、かつ、変換後の記号列同士のハミング距離が所定の値以上となる場合は、変換関数の評価値を下げる。
【０１２１】
すなわち、情報検索装置１は、同一利用者が登録した特徴量ベクトルを記号列に変換した際に、ハミング距離が所定の値以下となる場合は、変換関数の評価値を下げる。また、情報検索装置１は、異なる利用者が登録した特徴量ベクトルを記号列に変換した際に、ハミング距離が所定の値以上となる場合は、変換関数の評価値を下げる。そして、情報検索装置１は、評価値の上限が下がるように、所定の変換関数が有する変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２の値を更新する。このため、情報検索装置１は、特徴量ベクトル記憶部１０が記憶する特徴量ベクトルの分布に応じて、最適な変換関数を自動で生成することができる。
【０１２２】
また、情報検索装置１は、特徴量ベクトルと変換後の記号列とを対応付けて記憶する。具体的には、情報検索装置１は、特徴量ベクトルと変換後の記号列とに同一のデータＩＤを対応付けて、特徴量ベクトル記憶部１０および記号列データインデックス記憶部１１に格納する。そして、情報検索装置１は、クエリデータを変換したバイナリ列とのハミング距離が所定の値以下となる記号列と対応付けられた特徴量ベクトルを検索する。このため、情報検索装置１は、クエリデータの近傍に位置する特徴量ベクトルを検索する際の計算コストを削減することができる。
【実施例２】
【０１２３】
これまで本発明の実施例について説明したが、実施例は、上述した実施例以外にも様々な異なる形態にて実施されてよいものである。そこで、以下では実施例２として本発明に含まれる他の実施例を説明する。
【０１２４】
（１）数式について
上述した情報検索装置１は、式（１）〜（２２）を用いて、特徴量ベクトルの変換、クエリデータの変換、変換関数の評価、変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２の最適化を行った。しかし、実施例はこれに限定されるものではない。
【０１２５】
すなわち、情報検索装置１は、特徴量ベクトルの変換時において、適切にワイルドカード記号を含む記号列に変換する変換関数を採用してよい。また、情報検索装置１は、最適化した変換行列Ｗを用いてクエリデータの特徴量ベクトルを変換する必要はなく、任意の変換行列を用いて、クエリデータの特徴量ベクトルをバイナリ列に変換してもよい。
【０１２６】
また、情報検索装置１は、確率的勾配降下法を用いて、評価関数の上限値を下げ、変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２の最適化を行った。しかし、実施例はこれに限定されるものではなく、情報検索装置１は、任意の手法を用いて、変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２の最適化を行ってよい。
【０１２７】
例えば、情報検索装置１は、評価関数の上限値を下げるように、変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２の最適化を行う都合上、同一利用者の特徴量ベクトルのハミング距離が所定の値以下となる場合は、変換関数の評価値を下げた。つまり、情報検索装置１は、より適切に特徴量ベクトルを記号列に変換する変換関数については、評価値を下げることで、変換行列Ｗおよび変換関数のパラメータａ１、ａ２、ｂ１、ｂ２の最適化を行った。しかし、例えば、情報検索装置１は、より適切に特徴量ベクトルを記号列に変換する変換関数の評価値を上げ、評価値が所定の閾値を超えた際に、変換関数を採用することとしてもよい。
【０１２８】
（２）変換関数の評価について
上述した情報検索装置１は、変換関数を評価する際に、特徴量ベクトル記憶部１０から特徴量ベクトルを２つ抽出し、抽出した２つの特徴量ベクトルの一方をクエリデータとし、もう一方を登録された特徴量ベクトルとみなして、変換関数を評価した。しかし、実施例はこれに限定されるものではない。例えば、情報検索装置１は、複数の特徴量ベクトルを抽出し、１つをクエリデータとし、残りを登録された特徴量ベクトルとみなして、変換関数を評価してもよい。
【０１２９】
（３）発明の実施形態について
上述した情報検索装置１は、クエリデータの特徴量ベクトルの近傍に位置する特徴量ベクトルの候補をハミング距離で抽出し、抽出した特徴量ベクトルの候補に、クエリデータの特徴用ベクトルと類似するデータが存在するか否かを判別した。しかし、本発明の実施形態はこれに限定されるものではない。
【０１３０】
すなわち、クエリデータと類似するデータが存在するか否かの判別については、従来の情報検索装置も可能である。そこで、登録された特徴量ベクトルをワイルドカード記号「＊」とバイナリ記号とを含む記号列に変換する情報変換プログラム、もしくは、情報変換装置として本発明を実施し、特徴量ベクトルの検索については、従来の情報検索装置が担うこととしてもよい。なお、このような実施を行う場合は、従来の情報検索装置がワイルドカード記号とバイナリ記号とのハミング距離を「０」として扱うようにする。
【０１３１】
また、情報検索装置１は、クエリデータの特徴用ベクトルと類似するデータが存在するか否かをクライアント装置２に送信した。しかし、実施例はこれに限定されるものではない。例えば、情報検索装置１は、ハミング距離を用いて、クエリデータの特徴量ベクトルの近傍に位置する特徴量ベクトルの候補を抽出し、抽出した特徴量ベクトルをクライアント装置２に送信することとしてもよい。また、情報検索装置１は、クエリデータの特徴量ベクトルのバイナリ列とのハミング距離が、所定の閾値以下となる記号列の元となる特徴量ベクトルをクライアント装置２に送信してもよい。また、情報検索装置１は、ハミング距離が小さい順に、特徴量ベクトルをクライアント装置２に送信してもよい。
【０１３２】
（４）特徴量ベクトルについて
上述した情報検索装置１は、生体データの特徴量ベクトルを記憶した。しかし、実施例はこれに限定されるものではなく、情報検索装置１は、任意の情報についての特徴量ベクトルを記憶し、クエリデータの特徴量ベクトルと類似する特徴量ベクトルを記憶しているか否かを判別してもよい。
【０１３３】
（５）プログラム
ところで、実施例１に係る情報検索装置１は、ハードウェアを利用して各種の処理を実現する場合を説明した。しかし、実施例はこれに限定されるものではなく、あらかじめ用意されたプログラムを情報検索装置１が有するコンピュータで実行することによって実現するようにしてもよい。そこで、以下では、図１１を用いて、実施例１に示した情報検索装置１と同様の機能を有するプログラムを実行するコンピュータの一例を説明する。図１１は、情報変換プログラムを実行するコンピュータの一例を説明するための図である。
【０１３４】
図１１に例示されたコンピュータ１００は、ＲＯＭ（Read  Only  Memory）１１０、ＨＤＤ（Hard  Disk  Drive）１２０、ＲＡＭ（Random  Access  Memory）１３０、ＣＰＵ（Central  Processing  Unit）１４０がバス１６０で接続される。また、図１１に例示されたコンピュータ１００は、パケットを送受信するためのＩ／Ｏ（Input  Output）１５０を有する。
【０１３５】
ＨＤＤ１２０は、特徴量ベクトル記憶部１０が記憶する情報と同一の情報が格納された特徴量ベクトルテーブル１２１と、記号列データインデックス記憶部１１が記憶する情報と同一の情報が格納された記号列テーブル１２２とを記憶する。また、ＲＡＭ１３０には、情報変換プログラム１３１があらかじめ保持される。ＣＰＵ１４０が情報変換プログラム１３１をＲＡＭ１３０から読み出して実行することによって、図１１に示す例では、情報変換プログラム１３１は、情報変換プロセス１４１として機能するようになる。なお、情報変換プロセス１４１は、図１に示した変換関数学習部１２、特徴量変換部１３、検索部１４と同様の機能を発揮する。
【０１３６】
なお、本実施例で説明した情報変換プログラムは、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。このプログラムは、インターネットなどのネットワークを介して配布することができる。また、このプログラムは、ハードディスク、フレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ（Compact  Disc  Read  Only  Memory）、ＭＯ（Magneto  Optical  Disc）、ＤＶＤ（Digital  Versatile  Disc）などのコンピュータで読取可能な記録媒体に記録される。また、このプログラムは、コンピュータによって記録媒体から読み出されることによって実行することもできる。
【符号の説明】
【０１３７】
１  情報検索装置
２  クライアント装置
１０  特徴量ベクトル記憶部
１１  記号列データインデックス記憶部
１２  変換関数学習部
１３  特徴量変換部
１４  検索部
【図１】
2013206187.tif 000025
【図２】
2013206187.tif 000026
【図３】
2013206187.tif 000027
【図４】
2013206187.tif 000028
【図５】
2013206187.tif 000029
【図６】
2013206187.tif 000030
【図７】
2013206187.tif 000031
【図８】
2013206187.tif 000032
【図９】
2013206187.tif 000033
【図１０】
2013206187.tif 000034
【図１１】
2013206187.tif 000035
【図１２】
2013206187.tif 000036
【図１３】
2013206187.tif 000037
【図１４】
2013206187.tif 000038