(57)【特許請求の範囲】
【請求項１】
各次元の値が０又は１の２値で表されるｄ（ｄは１以上の整数）次元のバイナリ空間に存在し、ｄ個の各成分が前記２値で表される第１ベクトルをＮ（Ｎは２以上の整数）個記憶する記憶部と、
前記バイナリ空間に存在し、前記ｄ個の各成分が前記２値で表される第２ベクトルを取得する取得部と、
前記Ｎ個の第１ベクトルから、前記第２ベクトルとの距離が予め定められた条件を満たす１以上の第１ベクトルを抽出し、前記第２ベクトルに対する前記１以上の第１ベクトルの距離の分布を算出する第１算出部と、
前記第２ベクトルと前記Ｎ個の第１ベクトルとの間で取り得る距離範囲のうちの少なくとも一部の範囲内にある距離毎に、当該距離に応じて得られる第１カーネル関数を取得し、前記分布と複数の前記第１カーネル関数とに基づいて得られる第２カーネル関数を生成する生成部と、
前記第２カーネル関数を用いて、前記Ｎ個の第１ベクトルが与えられたときの前記第２ベクトルが生起する確率を示す生起確率を算出する第２算出部と、
を備える算出装置。
【請求項２】
前記第１カーネル関数は、次元数ｄと前記距離との比をパラメータとする関数である請求項１に記載の算出装置。
【請求項３】
前記第１カーネル関数は、距離に応じた前記第２ベクトルの生起する確率をカーネル平滑化により求めるための関数であって、前記距離が小さいほど平滑化の度合いを弱め、前記距離が大きいほど平滑化の度合いを強める関数である請求項１に記載の算出装置。
【請求項４】
前記第２カーネル関数は、前記距離毎に当該距離に応じて前記分布から定まる重みが付与された当該距離に応じた第１カーネル関数の総和を前記距離毎の重みの総和で除した関数である請求項１に記載の算出装置。
【請求項５】
前記重みは、前記分布における前記距離の頻度である請求項４に記載の算出装置。
【請求項６】
前記予め定められた条件は、値が小さい方からの順位が上位α％に含まれる前記距離であることを示す条件、又は、値が小さい方からの順位がＭ以内（ＭはＭ＜Ｎを満たす整数）の前記距離であることを示す条件である請求項１に記載の算出装置。
【請求項７】
前記範囲は、ｄ以下の距離である請求項１に記載の算出装置。
【請求項８】
前記範囲は、ｄ／２を超えない最大の整数の距離である請求項１に記載の算出装置。
【請求項９】
前記生起確率を出力する出力部を更に備える請求項１に記載の算出装置。
【請求項１０】
前記Ｎ個の第１ベクトルは、それぞれ、複数のカテゴリのいずれかに属し、
前記第２算出部は、前記第２カーネル関数を用いて、前記カテゴリ毎に、当該カテゴリに属する第１ベクトルに対する前記第２ベクトルの生起確率を算出する請求項１に記載の算出装置。
【請求項１１】
前記カテゴリ毎の前記生起確率に基づいて、前記第２ベクトルが属するカテゴリを識別する識別部と、
識別結果を出力する出力部と、
を更に備える請求項１０に記載の算出装置。
【請求項１２】
前記識別結果は、識別されたカテゴリ及び当該カテゴリの前記生起確率の少なくともいずれかを含む請求項１１に記載の算出装置。
【請求項１３】
画像データを入力する入力部を更に備え、
前記取得部は、前記画像データから前記第２ベクトルを取得する請求項１に記載の算出装置。
【請求項１４】
記憶部、取得部、第１算出部、生成部、および、第２算出部を備える算出装置で実行される算出方法であって、
前記記憶部が、各次元の値が０又は１の２値で表されるｄ（ｄは１以上の整数）次元のバイナリ空間に存在し、ｄ個の各成分が前記２値で表される第１ベクトルをＮ（Ｎは２以上の整数）個記憶する記憶ステップと、
前記取得部が、前記バイナリ空間に存在し、前記ｄ個の各成分が前記２値で表される第２ベクトルを取得する取得ステップと、
前記第１算出部が、前記Ｎ個の第１ベクトルから、前記第２ベクトルとの距離が予め定められた条件を満たす１以上の第１ベクトルを抽出し、前記第２ベクトルに対する前記１以上の第１ベクトルの距離の分布を算出する第１算出ステップと、
前記生成部が、前記第２ベクトルと前記Ｎ個の第１ベクトルとの間で取り得る距離範囲のうちの少なくとも一部の範囲内にある距離毎に、当該距離に応じて得られる第１カーネル関数を取得し、前記分布と複数の前記第１カーネル関数とに基づいて得られる第２カーネル関数を生成する生成ステップと、
前記第２算出部が、前記第２カーネル関数を用いて、前記Ｎ個の第１ベクトルが与えられたときの前記第２ベクトルが生起する確率を示す生起確率を算出する第２算出ステップと、
を含む算出方法。
【請求項１５】
各次元の値が０又は１の２値で表されるｄ（ｄは１以上の整数）次元のバイナリ空間に存在し、ｄ個の各成分が前記２値で表される第１ベクトルをＮ（Ｎは２以上の整数）個記憶する記憶部と、
前記バイナリ空間に存在し、前記ｄ個の各成分が前記２値で表される第２ベクトルを取得する取得部と、
前記Ｎ個の第１ベクトルから、前記第２ベクトルとの距離が予め定められた条件を満たす１以上の第１ベクトルを抽出し、前記第２ベクトルに対する前記１以上の第１ベクトルの距離の分布を算出する第１算出部と、
前記第２ベクトルと前記Ｎ個の第１ベクトルとの間で取り得る距離範囲のうちの少なくとも一部の範囲内にある距離毎に、当該距離に応じて得られる第１カーネル関数を取得し、前記分布と複数の前記第１カーネル関数とに基づいて得られる第２ベクトルの生起確率を求める第２カーネル関数を生成する生成部と、
前記第２カーネル関数を用いて、前記Ｎ個の第１ベクトルが与えられたときの前記第２ベクトルが生起する確率を示す生起確率を算出する第２算出部と、
してコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、算出装置、方法及びプログラムに関する。
【背景技術】
【０００２】
ｄ（ｄは１以上の整数）次元のユークリッド空間上に存在する複数のトレーニングベクトルを用いて、当該ユークリッド空間上の任意のベクトルの生起確率を算出（推定）する際に、カーネル平滑化（kernel  Smoothing）という技術を用いる手法が知られている。なお、トレーニングベクトルや任意のベクトルは、ユークリッド空間上の点（ｄ次元の座標）を成分とするベクトルであり、ユークリッド空間上の点に該当する。
【０００３】
上述の手法では、数式（１）に示すように、カーネル関数Ｋを用いて、Ｎ（Ｎは２以上の整数）個のトレーニングベクトルｘｉそれぞれに対する任意のベクトルｘの生起確率Ｋ（ｘ，ｘｉ）を算出し、算出した各生起確率Ｋ（ｘ，ｘｉ）の合計値を算出し、算出した合計値をＮで除すことで、当該Ｎ個のトレーニングベクトルに対する当該任意のベクトルｘの生起確率Ｐ（ｘ）を算出する。
【０００４】
【数１】
0006453618.tif 000002
【０００５】
なお、カーネル関数Ｋは、トレーニングベクトルｘｉと任意のベクトルｘとの距離から当該トレーニングベクトルｘｉに対する当該任意のベクトルｘの生起確率Ｋ（ｘ，ｘｉ）を算出するため、実際には、等分散のガウシアンのように、２つのベクトル間の距離の関数として表せるものが使用される。また、カーネル関数Ｋでは、平滑化の度合いが固定化されているものとする。
【０００６】
但し、一般的に、トレーニングベクトルは、ユークリッド空間上に一様に分布せず、何らかの偏りをもって分布することが多い。このため、例えば非特許文献１には、Ｎ個のトレーニングベクトルｘｉの分布（詳細には、任意のベクトルｘに対するＮ個のトレーニングベクトルｘｉの距離の分布）を用いて、平滑化の度合いを適応的に制御することで、任意のベクトルｘの生起確率Ｐ（ｘ）の算出精度を高める技術が提案されている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｄ．Ｑｉｎ  ａｎｄ  Ｃ．Ｗｅｎｇｅｒｔ  ａｎｄ  Ｌ．ｖ．Ｇｏｏｌ，“Ｑｕｅｒｙ  Ａｄａｐｔｉｖｅ  Ｓｉｍｉｌａｒｉｔｙ  ｆｏｒ  Ｌａｒｇｅ  Ｓｃａｌｅ  Ｏｂｊｅｃｔ  Ｒｅｔｒｉｅｖａｌ，”Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ（ＣＶＰＲ），２０１３
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述した技術は、ユークリッド空間を想定した技術であり、バイナリ空間を想定したものではない。
【０００９】
ユークリッド空間は、各次元の値が連続した値（連続値）で表されるｄ次元の空間であり、空間上の点を示すｄ次元の各成分（座標）の値も連続値で表される。一方、バイナリ空間は、各次元の値が０又は１の２値、即ち、非連続値で表されるｄ次元の空間であり、空間上の点を示すｄ次元の各成分（座標）の値も非連続値である０又は１の２値で表される。
【００１０】
ユークリッド空間とバイナリ空間とでは、このような相違があるため、バイナリ空間上に存在する複数のトレーニングベクトルを用いて、当該バイナリ空間上の任意のベクトルの生起確率を算出する際に、上述したような技術をそのまま採用しても、精度の高い生起確率を算出することはできない。
【００１１】
本発明が解決しようとする課題は、各次元の値が０又は１の２値で表されるバイナリ空間上の任意のベクトルの生起確率の算出精度を高めることができる算出装置、方法及びプログラムを提供することである。
【課題を解決するための手段】
【００１２】
実施形態の算出装置は、記憶部と、取得部と、第１算出部と、生成部と、第２算出部と、を備える。記憶部は、各次元の値が０又は１の２値で表されるｄ（ｄは１以上の整数）次元のバイナリ空間に存在し、ｄ個の各成分が前記２値で表される第１ベクトルをＮ（Ｎは２以上の整数）個記憶する。取得部は、前記バイナリ空間に存在し、前記ｄ個の各成分が前記２値で表される第２ベクトルを取得する。第１算出部は、前記Ｎ個の第１ベクトルから、前記第２ベクトルとの距離が予め定められた条件を満たす１以上の第１ベクトルを抽出し、前記第２ベクトルに対する前記１以上の第１ベクトルの距離の分布を算出する。生成部は、前記第２ベクトルと前記Ｎ個の第１ベクトルとの間で取り得る距離範囲のうちの少なくとも一部の範囲内にある距離毎に、当該距離に応じて得られる第１カーネル関数を取得し、前記分布と前記複数の第１のカーネル関数とに基づいて得られる第２カーネル関数を生成する。第２算出部は、前記第２カーネル関数を用いて、前記Ｎ個の第１ベクトルに対する前記第２ベクトルの生起確率を算出する。
【図面の簡単な説明】
【００１３】
【図１】第１実施形態のカーネル関数の平滑化の度合いの制御例を示す図。
【図２】第１実施形態のカーネル関数の平滑化の度合いの制御例を示す図。
【図３】第１実施形態の算出装置の例を示す構成図。
【図４】第２実施形態の処理例を示すフローチャート。
【図５】第２実施形態の算出装置の例を示す構成図。
【図６】第２実施形態の処理例を示すフローチャート。
【図７】上記各実施形態の算出装置のハードウェア構成例を示すブロック図。
【発明を実施するための形態】
【００１４】
以下、添付図面を参照しながら、実施形態を詳細に説明する。
【００１５】
（第１実施形態）
まず、バイナリ空間上の任意のベクトルの生起確率を算出する際に、非特許文献１に開示されたような技術をそのまま採用しても、精度の高い生起確率を算出することはできない理由について説明する。なお、バイナリ空間は、前述の通り、各次元の値が０又は１の２値、即ち、非連続値で表されるｄ（ｄは１以上の整数）次元の空間であり、空間上の点を示すｄ次元の各成分（座標）の値も非連続値である０又は１の２値で表される。
【００１６】
バイナリ空間上のベクトルは、ｄ次元の各成分の値が０又は１の２値で表されるため、バイナリ空間上のトレーニングベクトルであるベクトルｂ１を基準とした場合のバイナリ空間上の任意のベクトルであるベクトルｂ２の生起確率は、ベクトルｂ２の各成分がベクトルｂ１と異なる確率をｐとおき、確率ｐが成分によらず一定で、互いに独立だとすると、数式（２）で表すことができる。
【００１７】
【数２】
0006453618.tif 000003
【００１８】
ｈは、ベクトルｂ１、ｂ２間のハミング距離を示す。ここで、数式（２）では、確率ｐの値が小さいほど、ｈの値が増加したときに、ベクトルｂ２の生起確率は急激に０に漸近する。つまり、数式（２）をカーネル関数と考えると、確率ｐの値が小さいほど、平滑化の度合いが弱いことになる。
【００１９】
従って、バイナリ空間上の複数のトレーニングベクトルに対するベクトルｂ２の生起確率を算出する場合、図１において、複数のトレーニングベクトルに対するベクトルｂ２の距離のヒストグラム２が示すように、ベクトルｂ２とトレーニングベクトルの距離が近いほど値が小さな確率ｐを用いることで、カーネル関数３の平滑化の度合いを弱めることになる。
【００２０】
一方、図２において、複数のトレーニングベクトルに対するベクトルｂ２の距離のヒストグラム４が示すように、ベクトルｂ２とトレーニングベクトルの距離が遠いほど値が大きな確率ｐを用いることで、カーネル関数５の平滑化の度合いを強めることになる。
【００２１】
但し、図１及び図２に示すように、数式（２）では、確率ｐの値が変化すると、関数の形状も変化する。つまり、数式（２）をカーネル関数と考え、平滑化の度合いを制御すると、カーネル関数も変化してしまう。
【００２２】
このように、平滑化の度合いを制御して、バイナリ空間上の任意のベクトルの生起確率を算出する場合、平滑化の度合いに応じたカーネル関数が必要となるため、平滑化の度合いが変化しても単一のカーネル関数で対応できる非特許文献１に開示されたような技術をそのまま採用しても、精度の高い生起確率を算出することはできない。
【００２３】
そこで、以下では、バイナリ空間上の任意のベクトルの生起確率を高い精度で算出する方法について説明する。
【００２４】
図３は、第１実施形態の算出装置１０の一例を示す構成図である。図３に示すように、算出装置１０は、記憶部１１と、入力部１３と、受付部１５と、取得部１７と、第１算出部１９と、生成部２１と、第２算出部２３と、出力制御部２５と、出力部２７とを、備える。
【００２５】
記憶部１１は、例えば、ＨＤＤ（Hard  Disk  Drive）、ＳＳＤ（Solid  State  Drive）、メモリカード、光ディスク、ＲＡＭ（Random  Access  Memory）、及びＲＯＭ（Read  Only  Memory）などの磁気的、光学的、又は電気的に記憶可能な記憶装置により実現できる。
【００２６】
入力部１３は、処理対象データを入力するものであり、例えば、カメラなどの撮像装置、ネットワークインタフェースなどの通信装置、及びＨＤＤやＳＳＤ等の補助記憶装置などにより実現できる。
【００２７】
受付部１５、取得部１７、第１算出部１９、生成部２１、第２算出部２３、及び出力制御部２５は、例えば、ＣＰＵ（Central  Processing  Unit）などの処理装置にプログラムを実行させること、即ち、ソフトウェアにより実現してもよいし、ＩＣ（Integrated  Circuit）などのハードウェアにより実現してもよいし、ソフトウェア及びハードウェアを併用して実現してもよい。
【００２８】
出力部２７は、例えば、液晶ディスプレイやタッチパネルディスプレイなどの表示装置により実現できる。
【００２９】
記憶部１１は、各次元の値が０又は１の２値で表されるｄ次元のバイナリ空間Ｂに存在し、ｄ個の各成分が０又は１の２値で表されるトレーニングベクトルである第１ベクトルｂｌ（ｂｌ∈Ｂ）をＮ（Ｎは２以上の整数）個記憶する。なお、ｂｌは、ｌ（１≦ｌ≦Ｎ）番目の第１ベクトルを示す。
【００３０】
受付部１５は、入力部１３から処理対象データの入力を受け付ける。第１実施形態では、処理対象データは、画像データであるものとするが、これに限定されず、音声データ、文書データ、又はセンサデータなど種々のデータであってもよいし、後述の第２ベクトルそのものであってもよい。
【００３１】
取得部１７は、前述のｄ次元のバイナリ空間Ｂに存在し、ｄ個の各成分が０又は１の２値で表される任意のベクトルである第２ベクトルｂ（ｂ∈Ｂ）を取得する。第１実施形態では、取得部１７は、受付部１５により受け付けられた画像から第２ベクトルｂを抽出することで、第２ベクトルｂを取得する。
【００３２】
なお、画像データからの第２ベクトルの抽出には、画像データから各成分が０又は１の２値で表されるバイナリベクトルを抽出する公知技術を用いればよい。例えば、任意の２画素の大小関係の結果を０と１で表すビットテストの結果を用いてもよいし、ＢＲＩＥＦ記述子やＯＲＢ記述子などの一般的なバイナリ記述子を用いてもよいし、ＨＯＧ（Histograms  of  Oriented  Gradients，IJCV２００４）などのように連続実数値の特徴量を算出した後、ＬＳＨ（Locality  Sensitive  Hashing）などの手法を用いてバイナリベクトルに変換したものを用いてもよい。
【００３３】
また第１実施形態では、記憶部１１に記憶されているＮ個の第１ベクトルｂｌも取得部１７と同様の手法で予め抽出されたものとするが、これに限定されるものではない。
【００３４】
第１算出部１９は、記憶部１１に記憶されているＮ個の第１ベクトルｂｌから、取得部１７により取得された第２ベクトルｂとの距離が予め定められた条件を満たす１以上の第１ベクトルｂｌを抽出し、第２ベクトルｂに対する１以上の第１ベクトルｂｌの距離の分布を算出する。なお、第１算出部１９は、２以上の第１ベクトルｂｌを抽出でき、第２ベクトルｂに対する２以上の第１ベクトルｂｌの距離の分布を算出できることが好ましい。予め定められた条件は、例えば、距離が、距離の小さい順に予め定められた割合又は数に収まることである。
【００３５】
例えば、第１算出部１９は、第２ベクトルｂとＮ個の第１ベクトルｂｌそれぞれとの距離ｈｌ＝Ｈ（ｂ，ｂｌ）を算出し、距離ｈｌが小さい方から（第２ベクトルｂに近い方から）α％（０＜α＜１００）に含まれる第１ベクトルｂｌについて、距離の分布（ヒストグラム）ｑ（ｈ）を算出する。
【００３６】
また例えば、第１算出部１９は、第２ベクトルｂとＮ個の第１ベクトルｂｌそれぞれとの距離ｈｌ＝Ｈ（ｂ，ｂｌ）を算出し、距離ｈｌが小さい方から（第２ベクトルｂに近い方から）Ｍ（Ｍ＜Ｎ）個の第１ベクトルｂｌについて、距離の分布ｑ（ｈ）を算出してもよい。
【００３７】
なお、Ｈ（ｂ，ｂｌ）は、第２ベクトルｂと第１ベクトルｂｌとのハミング距離を示す。また、第２ベクトルｂ、第１ベクトルｂｌは、いずれもｄ次元のバイナリベクトルであるため、距離ｈｌの値は、０〜ｄまでの整数値のいずれかの値となる。
【００３８】
生成部２１は、取得部１７により取得された第２ベクトルｂと記憶部１１に記憶されているＮ個の第１ベクトルｂｌとの間で取り得る距離範囲のうちの少なくとも一部の範囲内にある距離毎に、当該距離に応じて得られる第１カーネル関数を取得し、第１算出部１９により算出された距離の分布と取得した複数個の第１カーネル関数とに基づいて得られる第２カーネル関数を生成する。第１カーネル関数は、距離に応じた第２ベクトルｂの生起確率を求める関数である。第２カーネル関数は、Ｎ個の第１ベクトルｂｌに対する第２ベクトルｂの生起確率を求める関数である。
【００３９】
例えば、生成部２１は、数式（３）を用いて、第２カーネル関数Ｋ（ｈ）を生成する。
【００４０】
【数３】
0006453618.tif 000004
【００４１】
ここで、ｉは、第２ベクトルｂとＮ個の第１ベクトルｂｌとの間で取り得る距離を示す変数であり、０〜ｄまでの整数値をとる。Ｚは、総和が１となるようにする正規化定数であり、例えば、数式（４）で表される。
【００４２】
【数４】
0006453618.tif 000005
【００４３】
数式（３）に戻り、Ｋｉ（ｈ）は、第１カーネル関数であり、例えば、数式（５）で表される。
【００４４】
【数５】
0006453618.tif 000006
【００４５】
数式（５）は、数式（２）のｐをｐｉとし、Ｚｉで除したものである。なお、ｐｉ＝ｉ／ｄであり、次元数ｄに対する距離の割合をパラメータとしている。また、ｐｉ＝ｉ／ｄであるため、距離ｉが小さいほどｐｉの値が小さくなり、第１カーネル関数Ｋｉ（ｈ）の平滑化の度合いを弱め、距離ｉが大きいほどｐｉの値が大きくなり、第１カーネル関数Ｋｉ（ｈ）の平滑化の度合いを強める。Ｚｉは、総和が１となるようにする正規化定数であり、例えば、数式（６）で表される。
【００４６】
【数６】
0006453618.tif 000007
【００４７】
数式（３）に戻り、ｗ（ｉ）は、第１カーネル関数Ｋｉ（ｈ）の重みであり、第１算出部１９により算出された距離の分布ｑ（ｈ）に基づいて定まる。例えば、ｑ（ｈ）における距離ｉのヒストグラムの値（頻度）をｗ（ｉ）としてもよい。
【００４８】
また例えば、ｑ（ｈ）において代表値となる距離ｉのｗ（ｉ）を１、代表値以外の距離ｉのｗ（ｉ）を０としてもよい。この場合、代表値となる距離ｉの第１カーネル関数Ｋｉ（ｈ）が第２カーネル関数Ｋ（ｈ）となる。代表値となる距離ｉは、例えば、ヒストグラムの値が平均値となる距離ｉ、ヒストグラムの値が中央値となる距離ｉ、ヒストグラムの値が最頻値となる距離ｉ、及び距離０〜距離ｉまでのヒストグラムの値の合計値の割合が下側β％となる距離ｉなどが挙げられる。
【００４９】
また例えば、ｑ（ｈ）において代表値となる距離ｉのｗ（ｉ）を１、ｑ（ｈ）において代表値以外の距離ｉのｗ（ｉ）を、代表値となる距離ｉから離れるほど緩やかに減少する値としてもよい。
【００５０】
以上のように、第２カーネル関数Ｋ（ｈ）は、距離ｉ毎に当該距離ｉに応じて距離の分布ｑ（ｈ）から定まる重みｗ（ｉ）が付与された当該距離ｉに応じた第１カーネル関数Ｋｉ（ｈ）の総和を距離ｉ毎の重みの総和Ｚで除した関数とすることができる。
【００５１】
なお、第２ベクトルｂがランダムに発生した場合、第２ベクトルｂと第１ベクトルｂｌとのハミング距離Ｈ（ｂ，ｂｌ）の期待値はｄ／２であるため、第２ベクトルｂとのハミング距離がｄ／２を超える第１ベクトルｂｌは、第２ベクトルｂの近傍に位置するとは言い難い。このため、数式（３）、（４）を、それぞれ、数式（７）、（８）のように変形してもよい。
【００５２】
【数７】
0006453618.tif 000008
【００５３】
【数８】
0006453618.tif 000009
【００５４】
数式（７）、（８）は、数式（３）、（４）のｄを[ｄ／２]に変形したものであり、［ｄ／２］は、ｄ／２を超えない最大の整数を示す。つまり、数式（３）、（４）では、所定範囲をｄ以下の距離としていたが、数式（７）、（８）に示すように、所定範囲は、ｄ／２を超えない最大の整数の距離としてもよい。数式（３）の場合でも第１カーネル関数の個数は、高々ｄ＋１個であるが、数式（７）の場合、第１カーネル関数の個数は、［ｄ／２］＋１個となる。
【００５５】
また、第１カーネル関数Ｋｉ（ｈ）に数式（５）を用いた場合、次元数ｄが大きくなると、“次元の呪い”の影響を受けやすい。このため、次元数ｄを仮想的に低次元化してもよい。
【００５６】
この場合、生成部２１は、低次元化後の次元数をｍ（ｍ＜ｄ）とし、第２ベクトルｂからｍ個の成分を選択するとともに、第１ベクトルｂｌからｍ個の成分を選択し、ハミング距離を算出する。
【００５７】
ここで、ｄ次元のバイナリ空間でハミング距離がｈのベクトルの組をｍ次元のバイナリ空間で観測した場合に、ハミング距離がｒになる確率は、数式（９）に示すように、超幾何分布ｆ（ｒ；ｄ,ｈ,ｍ）となることが知られている。
【００５８】
【数９】
0006453618.tif 000010
【００５９】
従って、ｄ次元のバイナリ空間でハミング距離がｈのベクトルの組をｍ次元のバイナリ空間で観測し、カーネル平滑化を用いて確率推定した場合の期待値Ｅｉ（ｈ）は、数式（１０）で表される。
【００６０】
【数１０】
0006453618.tif 000011
【００６１】
そして、生成部２１は、数式（１０）を区間［０，ｄ］で積分したら１になるように正規化した数式（１１）に示す関数を、第１カーネル関数に用いればよい。
【００６２】
【数１１】
0006453618.tif 000012
【００６３】
数式（１１）で表される関数を第１カーネル関数に用いると、ｄ次元のバイナリ空間におけるベクトルを仮想的にｍ次元のバイナリ空間で観測してハミング距離を測るという試行を無限回繰り返した場合の確率の期待値が算出できる。
【００６４】
第２算出部２３は、生成部２１により生成された第２カーネル関数を用いて、Ｎ個の第１ベクトルｂｌに対する第２ベクトルｂの生起確率Ｐ（ｂ）を算出する。例えば、第２算出部２３は、数式（１２）を用いて、生起確率Ｐ（ｂ）を算出する。
【００６５】
【数１２】
0006453618.tif 000013
【００６６】
なお、第２ベクトルｂに対するＮ個の第１ベクトルｂｌの距離の分布（ヒストグラム）ｓ（ｈ）が算出してあれば、第２算出部２３は、数式（１３）を用いて、生起確率Ｐ（ｂ）を算出してもよい。
【００６７】
【数１３】
0006453618.tif 000014
【００６８】
第２ベクトルｂ、第１ベクトルｂｌは、いずれもｄ次元のバイナリベクトルであるため、距離ｈｌの値は、０〜ｄまでの整数値のいずれかの値となることが予め分かる。このため、距離ｈｌが取り得る全ての値（０〜ｄまでの整数値のいずれかの値）に対し、予め第２カーネル関数の値を算出しておけば、数式（１３）に示すように、これらの第２カーネル関数の値と距離の分布（ヒストグラム）ｓ（ｈ）との内積を求めることで、生起確率Ｐ（ｂ）を算出してもよい。
【００６９】
第１ベクトルｂｌの数Ｎが次元数ｄよりも大きい場合、数式（１２）を用いて生起確率Ｐ（ｂ）を算出するよりも、数式（１３）を用いて生起確率Ｐ（ｂ）を算出する方が演算を簡略化でき、演算量を抑えることができる。
【００７０】
出力制御部２５は、第２算出部２３により算出された生起確率Ｐ（ｂ）を出力部２７に出力させる。
【００７１】
図４は、第１実施形態の算出装置１０で行われる処理の手順の流れの一例を示すフローチャートである。
【００７２】
まず、受付部１５は、入力部１３から画像データの入力を受け付ける（ステップＳ１０１）。
【００７３】
続いて、取得部１７は、受付部１５により受け付けられた画像から第２ベクトルｂを抽出することで、第２ベクトルｂを取得する（ステップＳ１０３）。
【００７４】
続いて、第１算出部１９は、記憶部１１に記憶されているＮ個の第１ベクトルｂｌから、取得部１７により取得された第２ベクトルｂとの距離が予め定められた条件を満たす１以上の第１ベクトルｂｌを抽出し（ステップＳ１０５）、第２ベクトルｂに対する１以上の第１ベクトルｂｌの距離の分布を算出する（ステップＳ１０７）。
【００７５】
続いて、生成部２１は、取得部１７により取得された第２ベクトルｂと記憶部１１に記憶されているＮ個の第１ベクトルｂｌとの間で取り得る距離範囲のうちの少なくとも一部の範囲内にある距離毎に、当該距離に応じて得られる第１カーネル関数を取得し（ステップＳ１０９）、第１算出部１９により算出された距離の分布と取得した複数個の第１カーネル関数とに基づいて得られる第２カーネル関数を生成する（ステップＳ１１１）。
【００７６】
続いて、第２算出部２３は、生成部２１により生成された第２カーネル関数を用いて、Ｎ個の第１ベクトルｂｌに対する第２ベクトルｂの生起確率Ｐ（ｂ）を算出する（ステップＳ１１３）。
【００７７】
続いて、出力制御部２５は、第２算出部２３により算出された生起確率Ｐ（ｂ）を出力部２７に出力させる（ステップＳ１１５）。
【００７８】
以上のように第１実施形態によれば、第２ベクトルｂとＮ個の第１ベクトルｂｌとの間で取り得る距離毎に、平滑化の度合いが適応的に制御された第１カーネル関数を用いて、Ｎ個の第１ベクトルｂｌに対する第２ベクトルｂの生起確率を求める第２カーネル関数を生成し、当該生起確率を算出するため、バイナリ空間上の第２ベクトルｂの生起確率の算出精度を高めることができる。
【００７９】
（第２実施形態）
第２実施形態では、第１ベクトルｂｌが属するカテゴリ毎に第２ベクトルｂの生起確率を算出し、第２ベクトルｂがいずれのカテゴリに属するかを識別する例について説明する。以下では、第１実施形態との相違点の説明を主に行い、第１実施形態と同様の機能を有する構成要素については、第１実施形態と同様の名称・符号を付し、その説明を省略する。
【００８０】
図５は、第２実施形態の算出装置１１０の一例を示す構成図である。図５に示すように、第２実施形態の算出装置１１０は、第２算出部１２３、識別部１２４、及び出力制御部１２５が、第１実施形態と相違する。
【００８１】
なお、第２実施形態では、記憶部１１に記憶されているＮ個の第１ベクトルｂｌは、それぞれ、Ｃ（Ｃ≧２）個のカテゴリのいずれかに属するものとする。
【００８２】
第２算出部１２３は、生成部２１により生成された第２カーネル関数を用いて、カテゴリｃ（１≦ｃ≦Ｃ）毎に、当該カテゴリｃに属する第１ベクトルｂｌに対する第２ベクトルｂの生起確率Ｐｃ（ｂ）を算出する。
【００８３】
ここで、第１ベクトルｂｌが属するカテゴリをｙｌ（ｙｌ∈｛１，…，Ｃ｝）とすると、第２算出部１２３は、数式（１４）を用いて、カテゴリｃにおける第２ベクトルｂの生起確率Ｐｃ（ｂ）を算出する。
【００８４】
【数１４】
0006453618.tif 000015
【００８５】
ここで、ｎｃは、数式（１５）で表されるＤｃの要素の個数、即ち、カテゴリｃに属する第１ベクトルｂｌの個数を表す。なお、Ｄｃは、カテゴリｃに属する第１ベクトルｂｌを指し示すインデックスの集合を表す。
【００８６】
【数１５】
0006453618.tif 000016
【００８７】
また、数式（１４）についても、数式（１２）から数式（１３）への変形と同様の変形が可能である。つまり、カテゴリｃにおける距離ｈｌの分布（ヒストグラム）ｓｃ（ｈ）が算出してあれば、第２算出部１２３は、数式（１６）を用いて、生起確率Ｐｃ（ｂ）を算出してもよい。
【００８８】
【数１６】
0006453618.tif 000017
【００８９】
識別部１２４は、第２算出部１２３により算出されたカテゴリｃ毎の生起確率Ｐｃ（ｂ）に基づいて、第２ベクトルｂが属するカテゴリｃを識別する。例えば、識別部１２４は、カテゴリｃ毎の生起確率Ｐｃ（ｂ）のうち生起確率Ｐｃ（ｂ）が最も高いカテゴリｃに第２ベクトルｂが属すると識別する。但し、識別部１２４は、最も高い生起確率Ｐｃ（ｂ）が閾値未満の場合には、第２ベクトルｂはいずれのカテゴリｃにも属さないと識別してもよい。
【００９０】
出力制御部１２５は、識別部１２４の識別結果を出力部２７に出力させる。識別結果は、例えば、識別部１２４により識別されたカテゴリｃ及び当該カテゴリｃの生起確率Ｐｃ（ｂ）の少なくともいずれかを含む。また例えば、識別結果は、カテゴリｃ毎の生起確率Ｐｃ（ｂ）を含んでいてもよい。
【００９１】
図６は、第２実施形態の算出装置１１０で行われる処理の手順の流れの一例を示すフローチャートである。
【００９２】
まず、ステップＳ２０１〜Ｓ２１１までの処理は、図４に示すフォローチャートのステップＳ１０１〜Ｓ１１１までの処理と同様である。
【００９３】
続いて、第２算出部１２３は、生成部２１により生成された第２カーネル関数を用いて、カテゴリｃ毎に、当該カテゴリｃに属する第１ベクトルｂｌに対する第２ベクトルｂの生起確率Ｐｃ（ｂ）を算出する（ステップＳ２１３）。
【００９４】
続いて、識別部１２４は、第２算出部１２３により算出されたカテゴリｃ毎の生起確率Ｐｃ（ｂ）に基づいて、第２ベクトルｂが属するカテゴリｃを識別する（ステップＳ２１４）。
【００９５】
続いて、出力制御部１２５は、識別部１２４の識別結果を出力部２７に出力させる（ステップＳ２１５）。
【００９６】
以上のように第２実施形態によれば、第１実施形態同様、バイナリ空間上の第２ベクトルｂの生起確率の算出精度を高めることができ、第２ベクトルｂ近傍の第１ベクトルｂｌの分布の違いによるロバストな識別を行うことができる。
【００９７】
（ハードウェア構成）
図７は、上記各実施形態の算出装置のハードウェア構成の一例を示すブロック図である。図７に示すように、上記各実施形態の算出装置は、ＣＰＵなどの制御装置９０２と、ＲＯＭやＲＡＭなどの内部記憶装置９０４と、ＨＤＤやＳＳＤなどの外部記憶装置９０６と、ディスプレイなどの表示装置９０８と、カメラなどの入力装置９１０と、通信Ｉ／Ｆなどの通信装置９１２とを、備えており、通常のコンピュータを利用したハードウェア構成で実現できる。
【００９８】
上記各実施形態の算出装置で実行されるプログラムは、ＲＯＭ等に予め組み込んで提供される。
【００９９】
また、上記各実施形態の算出装置で実行されるプログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、ＣＤ−Ｒ、メモリカード、ＤＶＤ、フレキシブルディスク（ＦＤ）等のコンピュータで読み取り可能な記憶媒体に記憶されて提供するようにしてもよい。
【０１００】
また、上記各実施形態の算出装置で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するようにしてもよい。また、上記各実施形態の算出装置で実行されるプログラムを、インターネット等のネットワーク経由で提供または配布するようにしてもよい。
【０１０１】
上記各実施形態の算出装置で実行されるプログラムは、上述した各部をコンピュータ上で実現させるためのモジュール構成となっている。実際のハードウェアとしては、例えば、制御装置９０２が外部記憶装置９０６からプログラムを内部記憶装置９０４上に読み出して実行することにより、上記各部がコンピュータ上で実現されるようになっている。
【０１０２】
以上説明したとおり、上記各実施形態によれば、各次元の値が０又は１の２値で表されるバイナリ空間上の任意のベクトルの生起確率の算出精度を高めることができる。
【０１０３】
なお本発明は、上記各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化することができる。また上記各実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成することができる。例えば、実施形態に示される全構成要素からいくつかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせても良い。
【０１０４】
例えば、上記各実施形態のフローチャートにおける各ステップを、その性質に反しない限り、実行順序を変更し、複数同時に実施し、あるいは実施毎に異なった順序で実施してもよい。
【符号の説明】
【０１０５】
１０、１１０  算出装置
１１  記憶部
１３  入力部
１５  受付部
１７  取得部
１９  第１算出部
２１  生成部
２３、１２３  第２算出部
２５、１２５  出力制御部
２７  出力部
１２４  識別部
【図１】
0006453618.tif 000018
【図２】
0006453618.tif 000019
【図３】
0006453618.tif 000020
【図４】
0006453618.tif 000021
【図５】
0006453618.tif 000022
【図６】
0006453618.tif 000023
【図７】
0006453618.tif 000024