(57)【要約】【課題】特徴量ベクトルを用いた類似検索を精度よく実行すること。【解決手段】射影部１１１は、ｍ次元の特徴量空間Ｖに対して逆立体射影を行うことで、ｍ次元よりもｐ次元高い空間Ｗに埋め込まれた（ｍ＋ｐ−１）次元の超球Ｓと特徴量空間Ｖとを対応付ける。設定部１１２は、超平面が共有する共通交点を超球Ｓの内部に設定する。作成部１１３は、（ｍ＋ｐ−１）次元の超球Ｓを横切る超平面をｎ個、超球Ｓに配置し、配置した結果を基にして変換規則を生成する。生成部１１４は、超球Ｓ上の座標を変換規則に従って、ビット列に変換する。【選択図】図１
2015121899.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
【非特許文献２】Jae-Pil  Heo,  Youngwoon  Lee,  Junfeng  He,  Shih-Fu  Chang,  and  Sung-Eui  Yoon.  “Spherical  hashing”,  In  CVPR,  pp.  2957-2964,  2012
【非特許文献３】Kengo  Terasawa  and  Yuzuru  Tanaka.  “Spherical  lsh  for  approximate  nearest  neighbor  search  on  unit  hyper-sphere”,  In  Frank  K.  H.  A.  Dehne,  Jorg-Rudiger  Sack,  and  Norbert  Zeh,  editors,  WADS,  Vol.  4619  of  Lecture  Notes  in  Computer  Sciene,  pp.  27-38.  Springer,  2007.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来技術では、特徴量ベクトルを用いた類似検索を精度良く実行できないという問題がある。
【０００８】
例えば、超球を用いて特徴量ベクトルをハッシュベクトルに変換すると、ワームホールの影響により、大きく異なる特徴量ベクトル同士であっても、ハッシュベクトル変換後のハミング距離が小さくなる場合がある。このため、異なる特徴量ベクトル同士を、類似する特徴量ベクトルとして誤判定する場合がある。
【０００９】
ここで、ワームホールについて説明する。図１６〜図１８は、ワームホールを説明するための図である。例えば、ｍ次元の特徴量空間Ｖを超球を用いて分割し、分割された領域が超球の内部か外部かに応じてビット列を割り振ることを考える。超球の配置によっては、図１６に示すように、領域Ａと、領域Ｂとが同一のビット列（０，０，０）を持つが、領域Ａと領域Ｂとは連結していない。
【００１０】
図１６に示す現象が起こる場合には、特徴量ベクトルに割り振られたビット列間のハミング距離により、特徴量ベクトルの類似性を評価する際に、特徴量ベクトルが大きく離れていてもハミング距離が小さくなる。この非連結性を理解するためには、図１７に示すように、領域Ａと領域Ｂとを結ぶチューブ１０が存在していると考えるのがよい。このチューブを一般相対論の特殊解になぞらえてワームホールと呼ぶ。
【００１１】
図１８に、一次元の特徴量空間の超球Ｓ４による領域分割を行った時の非連結領域の発生とその間を結ぶワームホールを示す。超球Ｓ４は、超平面Ｆ５およびＦ６によって分割されている。例えば、超平面Ｆ５よりも左の領域は、１ビット目に１が割り振られ、超平面Ｆ５よりも右の領域は、１ビット目に０が割り振られる。また、超平面Ｆ６よりも右の領域には、２ビット目に１が割り振られ、超平面Ｆ６よりも左の領域には、２ビット目に０が割り振られる。そうすると、図１８の南極付近と北極付近は連結していないが、同じビット列（０，０）が割り振られてしまう。これは、超球Ｓの南極付近と北極付近とを結ぶワームホールが発生したためである。
【００１２】
一つの側面では、特徴量ベクトルを用いた類似検索を精度よく実行できる空間分割方法、空間分割装置および空間分割プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
第１の案では、コンピュータが下記の処理を実行する。コンピュータは、特徴量空間の次元よりも１次元以上大きい次元の空間に存在する球の内側に含まれるような超平面の交点の位置を特定し、特定された位置の交点を、各超平面が共有するように超平面を配置する処理を実行する。
【発明の効果】
【００１４】
本発明の一の実施態様によれば、特徴量ベクトルを用いた類似検索を精度よく実行できるという効果を奏する。
【図面の簡単な説明】
【００１５】
【図１】図１は、実施例１に係る空間分割装置に係るシステム構成を示す図である。
【図２】図２は、超球Ｓへの逆立体射影を説明するための図である。
【図３】図３は、超球Ｓの特徴量空間Ｖへの射影による像の円の半径の一例を示す図である。
【図４】図４は、超球Ｓへ逆立体射影される領域及び逆立体射影された領域の一例を示す図である。
【図５】図５は、近似直線の一例を示す図である。
【図６】図６は、超球Ｓ内に設定された共通交点の一例を示す図である。
【図７】図７は、全体処理を説明するための図である。
【図８】図８は、共通交点を設定する処理フローの第一の例を示す図である。
【図９】図９は、共通交点を設定する処理フローの第二の例を示す図である。
【図１０】図１０は、共通交点を設定する処理フローの第三の例を示す図である。
【図１１】図１１は、実施例２に係る空間分割装置に係るシステム構成を示す図である。
【図１２】図１２は、共通交点を設定する処理フローの第四の例を示す図である。
【図１３】図１３は、共通交点を設定する処理フローの第五の例を示す図である。
【図１４】図１４は、共通交点を設定する処理フローの第六の例を示す図である。
【図１５】図１５は、目的関数の処理フローの一例を示す図である。
【図１６】図１６は、ワームホールの発生を説明するための第一の例を示す図である。
【図１７】図１７は、ワームホールの発生を説明するための第二の例を示す図である。
【図１８】図１８は、ワームホールの発生を説明するための第三の例を示す図である。
【図１９】図１９は、空間分割装置のハードウェア構成を示す図である。
【発明を実施するための形態】
【００１６】
以下に、本願の開示する空間分割方法、空間分割装置および空間分割プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの権利範囲が限定されるものではない。各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００１７】
（空間分割装置のシステム構成）
図１を用いて、空間分割装置１００のシステム構成について説明する。図１は、実施例１に係る空間分割装置に係るシステム構成を示す図である。図１の例に示すように、空間分割装置１００は、制御部１１０、記憶部１２０および特徴量空間のデータ１３０を有する。記憶部１２０は、超平面数１２１と、ビット列１２２ａとを含む。また、空間分割装置１００は、ビット列１２２ｂと、クエリデータ１３１とを含む。記憶部１２０は例えば、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）、フラッシュメモリ（Flash  Memory）などの半導体メモリ素子、ハードディスクや光ディスクなどの記憶装置に対応する。なお、特徴量空間のデータ１３０は、記憶部１２０に含まれていてもよい。
【００１８】
また、制御部１１０は、射影部１１１ａ、設定部１１２、作成部１１３および生成部１１４ａを有する。また、空間分割装置１００は、射影部１１１ｂと、生成部１１４ｂと、ハミング距離計算部１１６とを含む。制御部１１０の機能は例えば、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路により実現することができる。また、制御部１１０の機能は例えば、ＣＰＵ（Central  Processing  Unit）が所定のプログラムを実行することで実現することができる。なお、設定部１１２は、特定部の一例である。作成部１１３は、配置部の一例である。
【００１９】
特徴量空間のデータ１３０は、複数の特徴量ベクトルを記憶する記憶部である。特徴量ベクトルは、例えば、ユーザの生体情報から得られるｍ次元の特徴量のデータである。生体情報から特徴量ベクトルを求める手法は、如何なる従来技術を用いても良い。例えば、ｍは１以上の整数である。超平面数１２１は、ｍ次元よりもｐ次元高い空間Ｗに設定する超平面の数である。ビット列１２２ａおよびビット列１２２ｂは、特徴量ベクトルを基にして生成されるビット列である。
【００２０】
射影部１１１ａおよび射影部１１１ｂは、ｍ次元の特徴量空間Ｖに対して逆立体射影を行うことで、ｍ次元よりもｐ次元高い空間Ｗに埋め込まれた（ｍ＋ｐ−１）次元の超球Ｓと特徴量空間Ｖとを対応付ける処理部である。ｐは、１以上の整数である。以下の説明では、射影部１１１ａ，１１１ｂをまとめて適宜、射影部１１１と表記する。
【００２１】
図２は、超球Ｓへの逆立体射影を説明するための図である。図２に示すように、逆立体射影を行うと、特徴量空間Ｖ上の点と、超球Ｓ上の点とが対応付けられる。図２に示す例では、特徴量空間Ｖ上の点Ｘ１と、超球Ｓ上の点ｒ１とが対応付けられる。超球Ｓの北極Ｙと南極Ｚを結ぶ直線と、特徴量空間Ｖとの交点をＸ０と定義する。例えば、北極Ｙの座標は、（ｘＳ１，ｘＳ２，・・・，ｘＳｍ，１）となり、南極Ｚの座標は、（ｘN１，ｘN２，・・・，ｘNｍ，−１）となる。
【００２２】
特徴量空間Ｖから超球Ｓの北極Ｙまでの高さをｄと定義する。北極Ｙと、点Ｘ１とを通る直線と、超球Ｓの表面との交点が、ｒ１に対応する。図３は、超球Ｓの特徴量空間Ｖへの射影による像の円の半径の一例を示す図である。図３に示すように、超球Ｓの断面ＳＡは、特徴量空間Ｖの領域ＶＡに対応する。
【００２３】
ここで、逆立体射影は、立体射影の逆射影である。立体射影は、図２のように超球Ｓと特徴量空間Ｖとを配置し、北極Ｙから超球Ｓと交わる直線を引いたとき、超球Ｓと直線との交点ｒ１から直線と特徴量空間Ｖとの交点Ｘ１への写像と定義される。なお、図２に示す例は、ｐの値が１である場合を示す。
【００２４】
特徴量空間Ｖの特徴量ベクトル（座標）を（ｘ１，ｘ２，・・・、ｘｍ）とするとき、逆立体射影「ｆ−１：Ｖ→Ｗ」を、式（１）とする。ただし、式（１）のｒ２は、式（２）で定義される。
【００２５】
【数１】
2015121899.tif 000003
【００２６】
【数２】
2015121899.tif 000004
【００２７】
式（１）および式（２）において、ｘ０およびｄはパラメータである。パラメータｘ０およびｄは、図２に示すｘ０およびｄに対応するものである。パラメータｘ０は、超球Ｓの南極Ｚに写像される特徴量空間Ｖの点の座標である。パラメータｄは、立体射影のスケールを調整するパラメータであり、超球Ｓの赤道が特徴量空間Ｖに写像された時の超球Ｓの半径に相当するものである。なお、超球Ｓの赤道の座標は、（ｘＳ１，ｘＳ２，・・・，ｘＳｍ，０）となる。
【００２８】
図４は、超球Ｓへ逆立体射影される領域及び逆立体射影された領域の一例を示す図である。図４のように特徴量空間Ｖの領域Ｖａｒｅａは、射影点が超球Ｓの北極Ｙである場合に超球Ｓ上の領域ｒａｒｅａに逆立体射影される。
【００２９】
射影部１１１ａは、指定されたパラメータｘ０およびパラメータｄと式（１）とを基にして、特徴量ベクトルの逆立体射影を行う。なお、射影部１１１ａは、パラメータｘ０およびパラメータｄの情報を予め保持しておいても良い。
【００３０】
射影部１１１ｂは、クエリデータ１３１に記憶された特徴量ベクトルと式（１）とを基にして、逆立体射影を行い、特徴量ベクトルに対応する超球Ｓ上の座標を算出する。射影部１１１ａは、算出した座標を、生成部１１４ａに出力する。
【００３１】
射影部１１１ｂは、特徴量空間のデータ１３０に記憶された各特徴量ベクトルと式（１）とを基にして、逆立体射影を行い、各特徴量ベクトルに対応する超球Ｓ上の複数の座標を算出する。射影部１１１ｂは、算出した各座標を、生成部１１４ｂに出力する。
【００３２】
生成部１１４ａ，１１４ｂは、超球Ｓ上の座標を変換規則に従って、ビット列に変換する処理部である。このビット列は、ハッシュベクトルに対応する。以下の説明では、生成部１１４ａ，１１４ｂをまとめて適宜、生成部１１４と表記する。
【００３３】
式（３）において、ｎ×（ｍ＋１）行列の情報「Ｗ１１，Ｗ１２,・・・，Ｗｎ（ｍ＋１）」およびｎ×１の情報「ｃ１，ｃ２，・・・，ｃｎ」は、変換規則である。生成部１１４は、変換規則を、作成部１１３から変換規則を取得する。式（３）において、「ｘ１，ｘ２，・・・，ｘｍ＋１」の情報は、超球Ｓ上の座標である。
【００３４】
【数３】
2015121899.tif 000005
【００３５】
生成部１１４は、式（３）を計算することで、「ｂ１，ｂ２，ｂ３，・・・、ｂｎ」を算出する。
【００３６】
生成部１１４は、「ｂ１，ｂ２，ｂ３，・・・、ｂｎ」を算出した後に、ｂＮの値が正であれば、ｂＮを「１」に変換し、ｂＮの値が正でない場合には、ｂＮを「０」に変換することで、ビット列を算出する。例えば、「ｂ１，ｂ２，ｂ３，・・・，ｂｎ」の値がそれぞれ正、負、正、・・・、正の場合には、生成部１１４は、ビット列「１，０，１，・・・，１」を生成する。
【００３７】
生成部１１４ａは、射影部１１１ａから取得した座標を基にして、ビット列を生成し、生成したビット列をハミング距離計算部１１６に出力する。
【００３８】
生成部１１４ｂは、射影部１１１ｂから取得する各座標を基にして、複数のビット列を生成し、生成した複数のビット列１２２ｂをハミング距離計算部１１６に出力する。なお、生成部１１４ｂは、ビット列１２２ｂをＲＡＭ等の記憶領域に格納してもよい。
【００３９】
ハミング距離計算部１１６は、生成部１１４ａにより生成された各ビット列１２２ａと、生成部１１４ｂにより生成されたビット列１２２ｂとのハミング距離を算出する。ハミング距離とは、桁数の同じ２つの２進数を比較した場合の、異なる桁の個数である。ハミング距離計算部１１６は、ハミング距離の算出結果に基づいて、クエリビット列とのハミング距離が近い順に、各ビット列に対して順位付けを行う。ハミング距離計算部１１６は、順位付けした各ビット列のうち、上位のビット列を、クエリビット列に対応するビット列として出力しても良いし、順位付けの結果を出力しても良い。
【００４０】
設定部１１２は、超平面が共有する共通交点を超球Ｓの内部に設定する。共通交点とは、超平面が共有する点である。空間分割装置１００によって設定された各超平面は、それぞれ共通交点を共有する。設定部１１２は、例えば、超球Ｓの北極と南極を結ぶ線上に共通交点を設定する。なお、設定部１１２は、設定した共通交点をＲＡＭ等のメモリに記憶してもよい。
【００４１】
作成部１１３は、（ｍ＋ｐ−１）次元の超球Ｓを横切る超平面をｎ個、超球Ｓに配置する処理部である。また、作成部１１３は、配置した結果を基にして変換規則を生成する。
【００４２】
設定部１１２が、各超平面の初期配置を特定する処理について３つの具体例を挙げて説明する。各超平面の初期配置を特定する処理について第一の例を説明する。設定部１１２は、特徴量空間のデータ１３０から各特徴量ベクトルを取得し、各特徴量ベクトルの分散共分散行列の固有値の平方根を算出する。設定部１１２は、各固有値のうち、最大のものをδとして特定する。また、設定部１１２は、超球Ｓの特徴量空間Ｖへの射影による像の円の半径Ｒを特定する。
【００４３】
設定部１１２は、式（４）を基にしてｃを算出する。設定部１１２は、共通交点の位置を超球Ｓの中心からｍ＋１次元方向にｃずらしたところに設定する。なお、超球Ｓの特徴量空間Ｖへの射影による像の円の半径Ｒは、例えば、図３に示される。
【００４４】
【数４】
2015121899.tif 000006
【００４５】
すなわち、法線ベクトルが第ｍ＋１軸方向に向いた超平面とそれが作る超球の半径を考えたとき、共通交点の位置が北極に近いほど大きな半径となり、南極に近いほど小さな半径になる。設定部１１２は、データの分布している領域のおおよその半径と赤道に写像される球の半径の比を基に共通交点の位置を調整する。
【００４６】
各超平面の初期配置を特定する処理について第二の例を説明する。設定部１１２は、特徴量ベクトルを主成分分析し、累積寄与率を算出する。例えば、設定部１１２は、主成分分析を行い、第１主成分から第Ｎ主成分の広がりを求める。設定部１１２は、各主成分の広がりを降順に並べ、広がりの大きいものから順に、δ１、δ２、・・・δＮとする。設定部１１２は、累積寄与率λｍを算出する。なお、ｍは主成分の成分数を示す。
【００４７】
設定部１１２は、横軸に成分の数「ｉ」、縦軸に対数累積寄与率「ｌｏｇλｍ」とするグラフに、ｉとｌｏｇλｍとの関係をプロットし、プロットした結果から近似直線を特定する。例えば、設定部１１２は、最小二乗法などを用いて近似直線を特定する。
【００４８】
図５は、近似直線の一例を示す図である。設定部１１２は、近似直線の傾きｂ／ａを「γ＋１」として算出する。設定部１１２は、式（５）を基にしてｃを算出する。設定部１１２は、共通交点の位置を超球Ｓの中心からｍ＋１次元方向にｃずらしたところに設定する。
【００４９】
【数５】
2015121899.tif 000007
【００５０】
すなわち、データの分布を楕円と捉え、楕円のつぶれ度合いは累積寄与率曲線から読み取ることができる。このつぶれた楕円を円で近似し、その半径をつぶれ度合いに依存するようにとっている。
【００５１】
各超平面の初期配置を特定する処理について第三の例を説明する。設定部１１２は、ｖｅｃＮ方向の三次モーメントを計算し、計算結果をνとする。例えば設定部１１２は、式（６）を基にして三次モーメントを計算する。式（６）において、ｘｉは、特徴量ベクトルのｉビット目に対応する。また、ｕは、特徴量ベクトルの１ビット目からｍビット目までの値の平均値に対応する。
【００５２】
【数６】
2015121899.tif 000008
【００５３】
設定部１１２は、式（４）を基にしてｃ、式（７）を基にしてｃ２を算出する。設定部１１２は、共通交点の位置をｍ＋１次元方向にｃ移動させ、さらに、ｖｅｃＮ方向にｃ２移動させたところに設定する。
【００５４】
【数７】
2015121899.tif 000009
【００５５】
すなわち、データの偏りがデータの平均値に関して非対称なときは、出来上がる超球の位置や半径の出現確率は、データの平均値に関して対称である必要はない。データの偏りは３次のモーメントで測ることができる。データの偏り度合いに応じ共通交点の位置を北極と南極を結ぶ線分からずらす。
【００５６】
図６を用いて、先述した第一〜第三の例によって、超球Ｓ内に設定される共通交点および超平面について説明する。図６は、超球Ｓ内に設定された共通交点の一例を示す図である。Ｆ１〜Ｆ４は、作成部１１３によって設定された超平面である。図６のように、超球Ｓを横断する超平面は、それぞれ超球Ｓ内部に存在する共通交点を通る。超球によりハッシングを行う際に、ワームホールが現れないようにするにはＷ中の超平面Ｆ１〜Ｆ４が作る交点が超球Ｓの内部にあることが必要である。そのために超平面Ｆ１〜Ｆ４の共通の交点を設けるようパラメータを設定する。
【００５７】
図７は、全体処理を説明するための図である。図７のように特徴量空間Ｖに各特徴量データＸｐが入力される（ステップＳ１０）。射影部１１１は、ｍ次元よりもｐ次元上位の空間Ｗに超球Ｓを設定する（ステップＳ１１）。射影部１１１は、各特徴量データＸｐを超球Ｓに逆立体射影する（ステップＳ１２）。設定部１１２は、超平面が共有する共通交点を超球Ｓの内部に設定する（ステップＳ１３）。
【００５８】
作成部１１３は、（ｍ＋ｐ−１）次元の超球Ｓを横切る超平面をｎ個、超球Ｓに設定する（ステップＳ１４）。生成部１１４は、射影部１１１ａから取得した座標を基にして、ビット列を生成する（ステップＳ１５）。ハミング距離計算部１１６は、生成部１１４ａにより生成された各ビット列１２２ａと、生成部１１４ｂにより生成されたビット列１２２ｂとのハミング距離を算出する（ステップＳ１６）。以下、共通交点を設定する処理フローについて説明する。
【００５９】
図８は、共通交点を設定する処理フローの第一の例を示す図である。設定部１１２は、特徴量の共分散行列Ｘmmの固有値のうち、最大の固有値の平方根δを算出する（ステップ２０）。設定部１１２は、式（４）を基に移動距離ｃを算出する（ステップＳ２１）。式（４）のＲは、超球Ｓの赤道の立体射影による像の円の半径である。設定部１１２は、共通交点の位置Ａを超球Ｓの中心から（ｍ＋１）次元方向にｃ移動させたところに設定する（ステップＳ２２）。
【００６０】
図９は、共通交点を設定する処理フローの第二の例を示す図である。設定部１１２は、特徴量の共分散行列Ｘmmの固有値のうち、最大の固有値の平方根δを算出する（ステップ３０）。設定部１１２は、特徴量データ群に対して主成分分析し、主成分の各成分の累積寄与率を算出する（ステップＳ３１）。
【００６１】
設定部１１２は、横軸に主成分の各成分、縦軸に対数累積寄与率をプロットした時の傾きγを算出する（ステップＳ３２）。設定部１１２は、式（５）を基に移動距離ｃを算出する（ステップＳ３３）。設定部１１２は、共通交点の位置Ａを超球Ｓの中心からｍ＋１次元方向にｃ移動させたところに設定する（ステップＳ３４）。
【００６２】
図１０は、共通交点を設定する処理フローの第三の例を示す図である。設定部１１２は、特徴量の共分散行列Ｘmmの固有値のうち、最大の固有値の平方根δを算出する（ステップＳ４０）。設定部１１２は、最大の固有値に対応する固有ベクトル方向のｖｅｃＮ方向の３次モーメントνを算出する（ステップＳ４１）。
【００６３】
設定部１１２は、式（３）を基に移動距離ｃを算出する（ステップＳ４２）。設定部１１２は、式（７）を基に移動距離ｃ２を算出する（ステップＳ４３）。設定部１１２は、共通交点の位置Ａを超球Ｓの中心からｍ＋１次元方向にｃ移動させ、さらに、ｖｅｃＮ方向にｃ２移動させたところに設定する（ステップＳ４４）。
【実施例２】
【００６４】
図１１を用いて、実施例２に係る空間分割装置２００のシステム構成について説明する。図１１は、実施例２に係る空間分割装置に係るシステム構成を示す図である。図１１の例に示すように、空間分割装置２００は、制御部２１０、記憶部２２０および特徴量空間のデータ２３０を有する。記憶部２２０には、超平面数２２１と、ビット列２２２ａとが含まれる。また、空間分割装置２００は、ビット列２２２ｂと、クエリデータ２３１とを有する。記憶部２２０は例えば、ＲＡＭ、ＲＯＭ、フラッシュメモリなどの半導体メモリ素子、ハードディスクや光ディスクなどの記憶装置に対応する。なお、特徴量空間のデータ２３０は、記憶部２２０に含まれてもよい。
【００６５】
また、制御部２１０は、射影部２１１ａ、設定部２１２、作成部２１３、生成部２１４ａおよび算出部２１５を有する。また、空間分割装置２００は、射影部２１１ｂと、生成部２１４ｂと、ハミング距離計算部２１６を含む。制御部２１０の機能は、例えば、ＡＳＩＣやＦＰＧＡなどの集積回路により実現することができる。また、制御部２１０の機能は例えば、ＣＰＵが所定のプログラムを実行することで実現することができる。なお、設定部２１２は、特定部の一例である。作成部２１３は、配置部の一例である。以下、制御部２１０の各処理部について説明する。
【００６６】
射影部１１１ｂは、クエリデータ１３１に記憶された特徴量ベクトルと式（１）とを基にして、逆立体射影を行い、特徴量ベクトルに対応する超球Ｓ上の座標を算出する。
【００６７】
設定部２１２が、近似精度が高い共通交点を設定する処理について３つの具体例を挙げて説明する。設定部２１２が「山登り探索」を用いて、近似精度が高い共通交点を設定する第一の例について説明する。設定部２１２は、共通交点の位置の初期値として位置Ａを特定する。算出部２１５は、この初期値によって算出される各特徴量ベクトルのビット列を、生成部２１４ａから取得する。算出部２１５は、各特徴量ベクトルとビット列とを基に近似精度を計算する。例えば、近似精度は、式（８）または式（９）によって算出される。
【００６８】
【数８】
2015121899.tif 000010
【００６９】
【数９】
2015121899.tif 000011
【００７０】
ここで、近似精度を算出する処理の一例について説明する。算出部２１５は、特徴量空間のデータ２３０から、ある特徴量ベクトルｖａを選出し、特徴量ベクトルｖａとの距離が、特徴量空間上で最も近い特徴量ベクトルを、第１位から第Ｍ位まで特定する。特徴量ベクトルｖａとの距離が、特徴量空間上で最も近い特徴量ベクトルを特徴量ベクトルｖａ１〜ｖａＭとする。例えば、式（８）において、特徴量ベクトルの数Ｍが、｜Ｒｋ｜に対応する。
【００７１】
算出部２１５は、生成部２１４ａから特徴量ベクトルｖａに対応するビット列との距離が、最も近いビット列を、第１位から第Ｍ位まで特定し、特定したビット列に対応する特徴量ベクトルｖｂ１〜ｖｂＭを特定する。算出部２１５は、特徴量ベクトルｖｂ１〜ｖｂＭのうち、何個の特徴量ベクトルが、特徴量ベクトルｖａ１〜ｖａＭと同一のものであるかを計数する。この計数した数が、式（８）の｜Ｒｋ∩Ｑｋ｜に対応する。
【００７２】
設定部２１２は、共通交点の位置Ａに近傍する位置ＢｉをＩ個設定する。算出部２１５は、各共通交点の位置Ｂｉに対する近似精度を算出する。設定部２１２は、近似精度の最も高い共通交点の位置を、位置Ａに設定する。設定部２１２は、上記処理を繰り返し実行し、近似精度の最も高い共通交点を特定する。
【００７３】
設定部２１２が上記処理を所定回数繰り返した後に得られる最終的な共通交点の位置Ａを用いて、ハミング距離計算部２１６は、ハミング距離を計算する。
【００７４】
設定部２１２が「マルコフ連鎖モンテカルロ法」を用いて、近似精度が高い共通交点を設定する第二の例について説明する。設定部２１２は、実施例１に係る手順に基づいて共通交点の位置Ａを特定する。算出部２１５は、共通交点の位置Ａを基に生成される各特徴量ベクトルのビット列を、生成部２１４ａから取得する。
【００７５】
算出部２１５は、各特徴量ベクトルとビット列とを基にして、近似類似検索を実行し、共通交点の位置をＡとした場合の近似精度Ｘ１を計算する。例えば、近似精度は、山登り探索と同様にして、式（８）によって算出される。
【００７６】
設定部２１２は、共通交点の位置Ａに近傍する位置Ｂを設定する。算出部２１５は、各特徴量ベクトルとビット列とを基にして、近似類似検索を実行し、共通交点の位置をＢとした場合の近似精度Ｘ２を計算する。
【００７７】
設定部２１２は、乱数を振り、乱数の値がＸ２／Ｘ１よりも小さい場合に、共通交点の位置Ｂを位置Ａに設定する。一方、パラメータ設定部３１０は、乱数を振り、乱数の値がＸ２／Ｘ１よりも小さくない場合に、共通交点の位置をそのままにする。また、設定部２１２は、所定回数上記処理を実行する。
【００７８】
設定部２１２が「群知能」を用いて、近似精度が高い共通交点を設定する第三の例について説明する。設定部２１２は、複数の共通交点の位置を特定する。例えば、設定部２１２は、実施例１と同様の手法により、共通交点の位置を求め、更に、この共通交点の位置に近傍する位置を複数求めることで、複数の共通交点の位置を特定する。
【００７９】
設定部２１２は、複数の共通交点の位置を基に算出される各特徴量ベクトルのビット列を、生成部２１４ａから取得する。設定部２１２は、各共通交点の位置を、荷電粒子の位置と見なし、目的関数を使用して、荷電系探索を実行することで、近似精度の最も高い共通交点の位置を特定する。
【００８０】
各共通交点の位置を荷電粒子の位置とみなすことで、各共通交点の位置を移動させる場合に、各共通交点の位置が、相互に近づかないような制約を設けることが出来る。そして、所定距離離れた位置で、近似精度が最も大きくなる共通交点の位置を、特定することができる。係る共通交点の位置を使用して、ハミング距離計算部２１６は、ハミング距離を計算する。
【００８１】
なお、荷電系探索の目的関数は、共通交点の位置が与えられた場合に、近似精度を算出する関数であり、近似精度を算出する処理の内容は、上述した山登り検索およびマルコフ連鎖モンテカルロ法と同様である。
【００８２】
次に、実施例２に係る空間分割装置２００の処理手順について説明する。以下では、共通交点の位置を特定する処理を、山登り探索を用いたパラメータ特定処理、マルコフ連鎖モンテカルロ法を用いたパラメータ特定処理、群知能を用いたパラメータ特定処理について順に説明する。
【００８３】
まず、山登り探索を用いたパラメータ特定処理の処理手順の一例について説明する。図１２は、共通交点を設定する処理フローの第四の例を示す図である。図１２に示すように、空間分割装置２００の設定部２１２は、共通交点の位置Ａを特定する（ステップＳ５０）。設定部２１２は、試行回数ｔを１に設定する（ステップＳ５１）。設定部２１２は、試行回数ｔが所定回数より大きい場合は（ステップＳ５２YES）、処理を終了する。一方、設定部２１２は、試行回数ｔが所定回数以下の場合は（ステップＳ５２NO）、ステップＳ５３に移行する。
【００８４】
作成部２１３は、設定された共通交点の位置Ａを基にして変換規則を生成する（ステップＳ５３）。生成部２１４ａは、変換規則を基に近似類似検索の近似精度αを計算する（ステップＳ５４）。
【００８５】
設定部２１２は、共通交点の位置Ａに近傍する位置Ｂｉを複数生成する（ステップＳ５５）。作成部２１３は、各共通交点の位置Ｂｉを基にして各々の変換規則を生成する（ステップＳ５６）。算出部２１５は、各変換規則を基に各々の近似精度βｉを計算する（ステップＳ５７）。設定部２１２は、近似精度α、近似精度βｉのうち、最も近似精度のよいものに対応する共通交点の位置を位置Ａに設定する（ステップＳ５８）。設定部２１２は、試行回数ｔに１を加算する（ステップＳ５９）。
【００８６】
次に、マルコフ連鎖モンテカルロ法を用いたパラメータ特定処理の処理手順の一例について説明する。図１３は、共通交点を設定する処理フローの第五の例を示す図である。図１３に示すように、空間分割装置２００の設定部２１２は、共通交点の位置Ａを特定する（ステップＳ６０）。設定部２１２は、試行回数ｔを１に設定する（ステップＳ６１）。設定部２１２は、試行回数ｔが所定回数より大きい場合は（ステップＳ６２YES）、処理を終了する。一方、設定部２１２は、試行回数ｔが所定回数以下の場合は（ステップＳ６２NO）、ステップＳ６３に移行する。
【００８７】
作成部２１３は、設定された共通交点の位置Ａを基にして変換規則を生成する（ステップＳ６３）。算出部２１５は、変換規則を基に近似類似検索の近似精度Ｘを計算する（ステップＳ６４）。設定部２１２は、共通交点の位置Ａに近傍する位置Ｂを生成する（ステップＳ６５）。作成部２１３は、共通交点の位置Ｂを基にして変換規則を生成する（ステップＳ６６）。算出部２１５は、変換規則を基に近似精度Ｘ２を計算する（ステップＳ６７）。
【００８８】
設定部２１２は、［０、１］の乱数を割り振り、乱数がＸ２／Ｘ１よりも小さい場合には（ステップＳ６８YES）、近傍位置Ｂを共通交点の位置Ａに設定し（ステップＳ６９）、そうでなければ（ステップＳ６８No）、共通交点の位置をそのままにし、ステップＳ７０に移行する。設定部２１２は、試行回数ｔに１を加算する（ステップＳ７０）。
【００８９】
次に、群知能を用いたパラメータ特定処理の処理手順の一例について説明する。図１４は、共通交点を設定する処理フローの第六の例を示す図である。設置部２１２は、例えば、実施例１に係る手順で共通交点の位置を複数設定する（ステップＳ８０）。
【００９０】
設定部２１２は、試行回数ｔを１に設定する（ステップＳ８１）。設定部２１２は、試行回数ｔが所定回数より大きい場合は（ステップＳ８２YES）、処理を終了する。一方、設定部２１２は、試行回数ｔが所定回数以下の場合は（ステップＳ８２NO）、ステップＳ８３に移行する。
【００９１】
設定部２１２は、各々の共通交点の位置を荷電粒子の位置とみなし目的関数を使用して荷電系探索を行う（ステップＳ８３）。設定部２１２は、試行回数ｔに１を加算する（ステップＳ８４）。
【００９２】
図１４の処理フローで使用される目的関数について説明する。図１５は、目的関数の処理フローの一例を示す図である。図１５のように、空間分割装置２００の作成部２１３は、目的関数を開始させ（ステップＳ９０）、共通交点の位置を基に変換規則の生成をおこなう（ステップＳ９１）。算出部２１５は、生成された変換規則を基に近似類似検索の近似精度Ｘ１を計算し（ステップＳ９２）、近似精度Ｘ１を出力して（ステップＳ９３）、目的関数を終了する（ステップＳ９４）。
【００９３】
（空間分割装置のハードウェア構成）
図１９は、空間分割装置のハードウェア構成を示す図である。図１９が示すように、コンピュータ３００は、各種演算処理を実行するＣＰＵ３０１と、ユーザからのデータ入力を受け付ける入力装置３０２と、モニタ３０３とを有する。また、コンピュータ３００は、記憶媒体からプログラム等を読み取る媒体読取装置３０４と、他の装置と接続するためのインターフェース装置３０５と、他の装置と無線により接続するための無線通信装置３０６とを有する。また、コンピュータ３００は、各種情報を一時記憶するＲＡＭ（Random  Access  Memory）３０７と、ハードディスク装置３０８とを有する。また、各装置３０１〜３０８は、バス３０９に接続される。
【００９４】
ハードディスク装置３０８には、例えば、図１に示した制御部１１０の各処理部と同様の機能を有する情報処理プログラムが記憶される。もしくは、ハードディスク装置３０８には、図１１に示した制御部２１０の各処理部と同様の機能を有する情報処理プログラムが記憶される。また、ハードディスク装置３０８には、情報処理プログラムを実現するための各種データが記憶される。
【００９５】
ＣＰＵ３０１は、ハードディスク装置３０８に記憶された各プログラムを読み出して、ＲＡＭ３０７に展開して実行することで、各種の処理を行う。これらのプログラムは、コンピュータ３００を図１に示した制御部１１０として機能させることができる。
【００９６】
なお、上記の情報処理プログラムは、必ずしもハードディスク装置３０８に記憶されている必要はない。例えば、コンピュータ３００が読み取り可能な記憶媒体に記憶されたプログラムを、コンピュータ３００が読み出して実行するようにしてもよい。コンピュータ３００が読み取り可能な記憶媒体は、例えば、ＣＤ−ＲＯＭやＤＶＤディスク、ＵＳＢ（Universal  Serial  Bus）メモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリ、ハードディスクドライブ等が対応する。また、公衆回線、インターネット、ＬＡＮ（Local  Area  Network）等に接続された装置にこのプログラムを記憶させておき、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。
【００９７】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００９８】
（付記１）コンピュータが実行する空間分割方法であって、
特徴量空間の次元よりも１次元以上大きい次元の空間に存在する球の内側に含まれるような超平面の交点の位置を特定し、
特定された位置の交点を、前記各超平面が共有するように前記超平面を共有させて配置する
処理を実行することを特徴とする空間分割方法。
【００９９】
（付記２）前記特定する処理は、前記球の北極と南極とを結ぶ線上に、前記共有される交点を設定することを特徴とする付記１に記載の空間分割方法。
【０１００】
（付記３）前記特定する処理は、前記特徴量ベクトルから算出される分散共分散行列の固有値のうち、最大の固有値に基づいて前記共有される交点を設定することを特徴とする付記１または２に記載の空間分割方法。
【０１０１】
（付記４）前記特定する処理は、前記特徴量ベクトルから算出される分散共分散行列の固有ベクトル方向のモーメントに基づいて前記交点を設定することを特徴とする付記１〜３のいずれか一に記載の空間分割方法。
【０１０２】
（付記５）前記特定する処理は、特徴量データの群に対して主成分分析した際に算出された主成分の各成分に対応する累積寄与率に基づいて前記交点を設定することを特徴とする付記２〜４のいずれか一に記載の空間分割方法。
【０１０３】
（付記６）前記特定する処理は、前記球内に設定された第１の交点と、前記第１の交点に近傍する１以上の第２の交点とのうち、近似精度が高い交点を第１の交点に設定する処理を１回以上おこなうことにより、第１の交点を設定することを特徴とする付記２〜５のいずれか一に記載の空間分割方法。
【０１０４】
（付記７）前記特定する処理は、前記球内に設定された第１の交点に近傍する第２の交点の近似精度を、前記第１の交点の近似精度で除算した数値が乱数よりも大きい場合に、前記第２の交点を前記第１の交点に設定する処理を１回以上おこなうことにより、第１の交点を設定することを特徴とする付記２〜５のいずれか一に記載の空間分割方法。
【０１０５】
（付記８）前記特定する処理は、前記球内に荷電粒子とみなして配置された複数の交点のうち、最も近似精度の高い交点を設定することを特徴とする付記１に記載の空間分割方法。
【０１０６】
（付記９）特徴量空間の次元よりも１次元以上大きい次元の空間に存在する球の内側に含まれるような超平面の交点の位置を特定する特定部と、
特定された位置の交点を、前記各超平面が共有するように前記超平面を共有させて配置する配置部と
を有することを特徴とする空間分割装置。
【０１０７】
（付記１０）コンピュータに、
特徴量空間の次元よりも１次元以上大きい次元の空間に存在する球の内側に含まれるような超平面の交点の位置を特定し、
特定された位置の交点を、前記各超平面が共有するように前記超平面を共有させて配置する処理を実行させることを特徴とする空間分割プログラム。
【符号の説明】
【０１０８】
１００            空間分割装置
１１０            制御部
１１１ａ，ｂ      射影部
１１２            設定部
１１３            作成部
１１４ａ，ｂ      生成部
１１６            ハミング距離計算部
１２０            記憶部
１２１            超平面数
１２２ａ，ｂ      ビット列
１３０            特徴量空間のデータ
１３１            クエリデータ
【図１】
2015121899.tif 000012
【図２】
2015121899.tif 000013
【図３】
2015121899.tif 000014
【図４】
2015121899.tif 000015
【図５】
2015121899.tif 000016
【図６】
2015121899.tif 000017
【図７】
2015121899.tif 000018
【図８】
2015121899.tif 000019
【図９】
2015121899.tif 000020
【図１０】
2015121899.tif 000021
【図１１】
2015121899.tif 000022
【図１２】
2015121899.tif 000023
【図１３】
2015121899.tif 000024
【図１４】
2015121899.tif 000025
【図１５】
2015121899.tif 000026
【図１６】
2015121899.tif 000027
【図１７】
2015121899.tif 000028
【図１８】
2015121899.tif 000029
【図１９】
2015121899.tif 000030
【手続補正書】
【提出日】平成26年10月30日(2014.10.30)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
しかしながら、従来技術では、ハッシュベクトルを用いた類似検索を精度良く実行できないという問題がある。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
一つの側面では、ハッシュベクトルを用いた類似検索を精度よく実行できる空間分割方法、空間分割装置および空間分割プログラムを提供することを目的とする。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
本発明の一の実施態様によれば、ハッシュベクトルを用いた類似検索を精度よく実行できるという効果を奏する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
特徴量空間のデータ１３０は、複数の特徴量ベクトルを記憶する記憶部である。特徴量ベクトルは、例えば、ユーザの生体情報から得られるｍ次元の特徴量のデータである。生体情報から特徴量ベクトルを求める手法は、如何なる従来技術を用いても良い。例えば、ｍは１以上の整数である。超平面数１２１は、ｍ次元よりもｐ次元高い空間Ｕに設定する超平面の数である。ビット列１２２ａおよびビット列１２２ｂは、特徴量ベクトルを基にして生成されるビット列である。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
射影部１１１ａおよび射影部１１１ｂは、ｍ次元の特徴量空間Ｖに対して逆立体射影を行うことで、ｍ次元よりもｐ次元高い空間Ｕに埋め込まれた（ｍ＋ｐ−１）次元の超球Ｓと特徴量空間Ｖとを対応付ける処理部である。ｐは、１以上の整数である。以下の説明では、射影部１１１ａ，１１１ｂをまとめて適宜、射影部１１１と表記する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００２４
【補正方法】変更
【補正の内容】
【００２４】
特徴量空間Ｖの特徴量ベクトル（座標）を（ｘ１，ｘ２，・・・、ｘｍ）とするとき、逆立体射影「ｆ−１：Ｖ→Ｕ」を、式（１）とする。ただし、式（１）のｒ２は、式（２）で定義される。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
【数１】
2015121899.tif 000031
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００４７
【補正方法】変更
【補正の内容】
【００４７】
設定部１１２は、横軸に成分の数「ｍ」、縦軸に対数累積寄与率「ｌｏｇλｍ」とするグラフに、ｍとｌｏｇλｍとの関係をプロットし、プロットした結果から近似直線を特定する。例えば、設定部１１２は、最小二乗法などを用いて近似直線を特定する。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００４９
【補正方法】変更
【補正の内容】
【００４９】
【数５】
2015121899.tif 000032
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
各超平面の初期配置を特定する処理について第三の例を説明する。設定部１１２は、第一主成分方向の三次モーメントνを計算する。例えば設定部１１２は、式（６）を基にして三次モーメントを計算する。式（６）では、ｘｉ(k)はｋ番目の特徴量ベクトルの第ｉ成分であり、ｕは特徴量ベクトル達の平均ベクトルであり、Ｋは特徴量ベクトル達の数である。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００５２
【補正方法】変更
【補正の内容】
【００５２】
【数６】
2015121899.tif 000033
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
図６を用いて、先述した第一〜第三の例によって、超球Ｓ内に設定される共通交点および超平面について説明する。図６は、超球Ｓ内に設定された共通交点の一例を示す図である。Ｆ１〜Ｆ４は、作成部１１３によって設定された超平面である。図６のように、超球Ｓを横断する超平面は、それぞれ超球Ｓ内部に存在する共通交点を通る。超球によりハッシングを行う際に、ワームホールが現れないようにするにはＵ中の超平面Ｆ１〜Ｆ４が作る交点が超球Ｓの内部にあることが必要である。そのために超平面Ｆ１〜Ｆ４の共通の交点を設けるようパラメータを設定する。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００５７
【補正方法】変更
【補正の内容】
【００５７】
図７は、全体処理を説明するための図である。図７のように特徴量空間Ｖに各特徴量データＸｐが入力される（ステップＳ１０）。射影部１１１は、ｍ次元よりもｐ次元上位の空間Ｕに超球Ｓを設定する（ステップＳ１１）。射影部１１１は、各特徴量データＸｐを超球Ｓに逆立体射影する（ステップＳ１２）。設定部１１２は、超平面が共有する共通交点を超球Ｓの内部に設定する（ステップＳ１３）。
【手続補正１４】
【補正対象書類名】図面
【補正対象項目名】図９
【補正方法】変更
【補正の内容】
【図９】
2015121899.tif 000034