高精度な類似検索システム
【課題】高精度な類似検索を実現する。
【解決手段】
ｐｉｖｏｔ決定部によって登録用データからｐｉｖｏｔを決定し、生データを取得し、前記生データから特徴量を抽出し、前記特徴量同士の距離或いは類似度としてスコアを計算し、前記ｐｉｖｏｔに対する前記スコアを用いて索引用ベクトルを生成し、前記索引用ベクトル同士の距離或いは類似度としてΔスコアを計算し、学習用データを用いて、回帰係数を含むｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習し、検索用データと前記ｎｏｎ−ｐｉｖｏｔとの前記Δスコアと前記回帰係数を用いて、ロジスティック回帰により事後確率の大きい順に前記ｎｏｎ−ｐｉｖｏｔの選択順序を決定し、前記検索用データと前記登録用データとの前記スコアを基に、検索結果を出力する。
【解決手段】
ｐｉｖｏｔ決定部によって登録用データからｐｉｖｏｔを決定し、生データを取得し、前記生データから特徴量を抽出し、前記特徴量同士の距離或いは類似度としてスコアを計算し、前記ｐｉｖｏｔに対する前記スコアを用いて索引用ベクトルを生成し、前記索引用ベクトル同士の距離或いは類似度としてΔスコアを計算し、学習用データを用いて、回帰係数を含むｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習し、検索用データと前記ｎｏｎ−ｐｉｖｏｔとの前記Δスコアと前記回帰係数を用いて、ロジスティック回帰により事後確率の大きい順に前記ｎｏｎ−ｐｉｖｏｔの選択順序を決定し、前記検索用データと前記登録用データとの前記スコアを基に、検索結果を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力された非構造化データに類似するものを検索する方法およびシステムに関する。
【背景技術】
【０００２】
入力された画像、動画、音楽、文書、バイナリデータ、生体情報などの非構造化データに対して、それに類似する非構造化データを検索することを類似検索と呼ぶ。類似検索は、一般には、生の非構造化データ（以後、生データと呼ぶ）から、距離計算（或いは類似度計算）のために用いられる特徴量と呼ばれる情報を抽出し、特徴量同士の不一致度合いを示す距離が小さいもの（或いは、特徴量同士の一致度合いを示す類似度が大きいもの）ほど類似していると見なすことで行なわれる。特徴量同士の距離（或いは類似度）をスコアと呼ぶ。
【０００３】
例えば、検索時に入力された生データ（以後、検索用データと呼ぶ）とデータベースに登録されている生データ（以後、登録用データと呼ぶ）との距離（或いは類似度）を計算し、距離が小さい順（或いは類似度が大きい順）にｋ個登録用データを選択し、それらに関する情報を検索結果として出力する方法（ｋ−Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ Ｓｅａｒｃｈ）や、距離（或いは類似度）が閾値ｒより小さい（或いは大きい）登録用データに関する情報を検索結果として出力する方法（Ｒａｎｇｅ Ｓｅａｒｃｈ）がある。
【０００４】
このとき、登録用データの総数をＮとすると、全ての登録用データに対してスコアを計算する場合、Ｎ回のスコア計算が必要となる。一般に、スコア計算には大きな時間が必要とされるので、登録用データ数Ｎが増加すれば、それにほぼ比例して検索時間がかかるようになる。これに対して、あらかじめ登録用データ同士のスコアを計算しておき、これを用いてスコアを計算する登録用データの選択順序を決定し、途中で登録用データとのスコアの計算を止めることで、スコアを計算する回数を削減する距離索引（Ｄｉｓｔａｎｃｅ−ｂａｓｅｄ Ｉｎｄｅｘｉｎｇ）が提案されている。
【０００５】
例えば、E．CHAVEZ，K．FIGUEROA and G．NAVARRO，“Effective Proximity Retrieval by Ordering Permutations，”IEEE Trans． on Pattern Analysis and Machine Intelligence，Vol．30，No．9，pp．1647−1658（2008）（非特許文献１）では、検索前にＮ個の登録用データから、例えばランダムに、Ｍ個（Ｍ＜Ｎ）の登録用データ（以後、ｐｉｖｏｔと呼ぶ）を選択し、各登録用データと各ｐｉｖｏｔとの距離を計算し、これを用いて検索時に用いるベクトル（以後、第１の索引用ベクトルと呼ぶ）を登録用データ毎に求めておき、検索時には入力された検索用データと各ｐｉｖｏｔとの距離を計算して検索用データの第２の索引用ベクトルを求めた後、第１と第２の索引用ベクトル同士の距離の小さい順となるように残りの登録用データ（以後、ｎｏｎ−ｐｉｖｏｔと呼ぶ）の選択順序を決定している。索引用ベクトルとして、非特許文献１では距離の小さい順にｐｉｖｏｔのＩＤを並べたベクトルを求めている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】E．CHAVEZ，K．FIGUEROA and G．NAVARRO，“Effective Proximity Retrieval by Ordering Permutations，”IEEE Trans． on Pattern Analysis and Machine Intelligence，Vol．30，No．9，pp．1647−1658（2008）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１では、第１と第２の索引用ベクトル同士の距離の小さい順となるようにｎｏｎ−ｐｉｖｏｔとの選択順序を決定している。しかしながら、この方法では、途中でｎｏｎ−ｐｉｖｏｔとのスコアの計算を止めたときに、検索用データからのスコアが閾値ｒより小さいにも関わらず、スコアが計算されずに終わる（即ち、検索漏れとなる）ｎｏｎ−ｐｉｖｏｔの個数の期待値を減らすという観点、即ち、検索の精度という観点で改良の余地があった。
【０００８】
本発明の目的は、スコアが計算されずに検索漏れとなるｎｏｎ−ｐｉｖｏｔの個数の期待値を理論的に最小化することにある。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、登録用データからｐｉｖｏｔを決定するｐｉｖｏｔ決定部と、生データを取得する生データ取得部と、前記生データから特徴量を抽出する特徴量抽出部と、前記特徴量同士の距離或いは類似度としてスコアを計算するスコア計算部と、前記ｐｉｖｏｔに対する前記スコアを用いて索引用ベクトルを生成する索引用ベクトル生成部と、前記索引用ベクトル同士の距離或いは類似度としてΔスコアを計算するΔスコア計算部と、学習用データを用いて、回帰係数を含むｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習するｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部と、入力された検索用データと前記ｎｏｎ−ｐｉｖｏｔとの前記Δスコアと前記回帰係数を用いて、ロジスティック回帰により事後確率の大きい順に前記ｎｏｎ−ｐｉｖｏｔの選択順序を決定するｎｏｎ−ｐｉｖｏｔ選択順序決定部と、前記検索用データと前記登録用データとの前記スコアを基に、検索結果を出力する検索結果出力部と、前記登録用データの前記特徴量と、前記登録用データのうちどれが前記ｐｉｖｏｔであるかが記されたｐｉｖｏｔ情報と、前記ｎｏｎ−ｐｉｖｏｔ毎の前記索引用ベクトルから構成されるインデックスと、前記ｎｏｎ−ｐｉｖｏｔ毎のパラメータを保持するデータベースを持つことを特徴とする。
【発明の効果】
【００１０】
本発明によれば、ｎｏｎ−ｐｉｖｏｔ毎の回帰係数を用いて、ロジスティック回帰により、事後確率の大きい順にｎｏｎ−ｐｉｖｏｔの選択順序を決定する。このようにすることで、検索用データからのスコアが閾値ｒより小さいにも関わらず、スコアが計算されずに検索漏れとなるｎｏｎ−ｐｉｖｏｔの個数の期待値を理論的に最小化することが可能となる。その結果、精度が大幅に向上するという効果が得られる。
【図面の簡単な説明】
【００１１】
【図１】本発明の第一の実施形態の機能構成を示すブロック図である。
【図２】本発明の第一、第二の実施形態のハードウェア構成を示すブロック図である。
【図３】本発明の第一の実施形態の登録処理を示すフロー図である。
【図４】本発明の第一、第二の実施形態の補助情報生成処理を示すフロー図である。
【図５】本発明の第一の実施形態の検索処理を示すフロー図である。
【図６】特徴量空間とインデックスを示す概略図である。
【図７】本発明の第二の実施形態の機能構成を示すブロック図である。
【図８】本発明の第二の実施形態の登録処理を示すフロー図である。
【図９】本発明の第二の実施形態の検索処理を示すフロー図である。
【発明を実施するための形態】
【実施例１】
【００１２】
以下、図面を参照して、１つ目の実施形態について説明する。
【００１３】
本実施形態の類似検索システムは、ユーザが画像を入力し、システムがサーバ端末内のデータベースから類似する画像を検索する類似画像検索システムである。画像の代わりに動画、音楽、文書、バイナリデータなどの非構造化データを用いるようにしても良い。本実施形態の類似検索システムでは、画像の特徴量としてカラーヒストグラムを用い、スコアとして特徴量同士のユークリッド距離を用いる。
【００１４】
本実施形態の類似検索システムでは、あらかじめＮ個の登録データからＭ個をｐｉｖｏｔとして選択する。ｐｉｖｏｔの選択方法としては、例えばランダムに選ぶ方法がある。次に、残りの各登録データ（各ｎｏｎ−ｐｉｖｏｔ）と各ｐｉｖｏｔとのスコアを計算し、これを基に検索時に用いる第１の索引用ベクトルをｎｏｎ−ｐｉｖｏｔ毎に求める。検索時には、入力された検索用データと各ｐｉｖｏｔとのスコアを計算し、これを基に検索用データの第２の索引用ベクトルを求める。索引用ベクトルは、各ｎｏｎ−ｐｉｖｏｔと検索用データの位置関係を、直接スコアを求めることなく知る手がかりとなるベクトルである。一般に、検索用データと各登録用データとのスコア計算には大きな時間が必要とされるが、索引用ベクトル同士の距離（或いは類似度）（以後、Δスコアと呼ぶ）を用いてｎｏｎ−ｐｉｖｏｔの選択順序を決定し、ｎｏｎ−ｐｉｖｏｔとのスコア計算をＴ（＜Ｎ−Ｍ）回行った後（Ｔは、あらかじめシステム管理者などが定めた上限値）、ｎｏｎ−ｐｉｖｏｔとのスコア計算を途中で止めることで、スコアを計算する回数を削減する（即ち高速に検索を行う）ことが可能となる。
索引用ベクトルとしては、各ｐｉｖｏｔとのスコアで構成されるベクトル（以後、スコアベクトルと呼ぶ）であっても良いし、距離（或いは類似度）の小さい順（或いは大きい順）にｐｉｖｏｔのＩＤを並べたベクトル（以後、順列ベクトルと呼ぶ）であっても良い。各ｎｏｎ−ｐｉｖｏｔの第１の索引用ベクトルをまとめたものを、インデックスと呼ぶ。
【００１５】
図６に、特徴量空間における検索用データＱと各登録用データＸ１、Ｘ２、・・・、ＸＮの例を示す。但し、Ｘ１、Ｘ２、・・・、ＸＭはｐｉｖｏｔ、ＸＭ＋１、ＸＭ＋２、・・・、ＸＮはｎｏｎ−ｐｉｖｏｔを表す。ここでは２つのクラスタが形成されており、お互いのクラスタは大きく離れている。また、特徴量の次元数は非常に高く、特徴量同士のスコアを計算するのに大きな時間がかかる。
【００１６】
図６（ａ１）（ａ２）に、索引用ベクトルとしてそれぞれスコアベクトル、順列ベクトルを用いた場合における検索用データの第２の索引用ベクトルと、インデックスの例を示す。但し、スコアとしては特徴量同士のユークリッド距離を用いている。
【００１７】
例えば、図６（ａ１）では、ＸＭ＋１とＸ１とのスコアは７０となっており、ＸＭ＋１のスコアベクトルＳＭ＋１は、ＳＭ＋１＝（７０，２８，１０５３，・・・，４３）Ｔとなっている。また、図６（ａ２）では、ＸＭ＋１と各ｐｉｖｏｔとのスコアの中で、最も小さいスコアを実現したｐｉｖｏｔがＸ２となっており、ＸＭ＋１のは、ＴＭ＋１＝（Ｘ２，ＸＭ−１，・・・，Ｘ３）Ｔとなっている。
【００１８】
また、Δスコア（索引用ベクトル同士の距離或いは類似度）としては、索引用ベクトルとしてスコアベクトルを用いた場合では、例えば市街地距離、ユークリッド距離などが考えられ、順列ベクトルを用いた場合では、例えばＳｐｅａｒｍａｎ Ｒｈｏなどが考えられる。また、上述した距離を距離としてとり得る値の最大値から差し引いたものなどを、類似度として用いるようにしても良い。
【００１９】
例えば、索引用ベクトルとしてスコアベクトルを用い、Δスコアとしてユークリッド距離を用いた場合、検索用データのスコアベクトルＳｑ、登録用データＸｉのスコアベクトルＳｉとのユークリッド距離をＤｅ（Ｓｑ，Ｓｉ）とすると、
【００２０】
【数１】
【００２１】
で表される。ここで、Ｓｉ（ｚ）はスコアベクトルＳｉにおけるｚ番目の要素を表す。図６（ａ１）の場合では、Ｄｅ（Ｓｑ，ＳＭ＋１）＝（７８−７０）２＋（９５−２８）２＋・・・＋（３９−４３）２と計算できる。
【００２２】
また、索引用ベクトルとして順列ベクトルを用い、ΔスコアとしてＳｐｅａｒｍａｎ Ｒｈｏを用いた場合、検索用データの順列ベクトルＴｑ、登録用データＸｉの順列ベクトルＴｉとのＳｐｅａｒｍａｎ ＲｈｏをＤρ（Ｔｑ，Ｔｉ）とすると、
【００２３】
【数２】
【００２４】
で表される。ここで、Ｔｉ（ｚ）は順列ベクトルＴｉにおけるｚ番目の要素の添え字の数字を表す。例えば、Ｔｉ＝（Ｘ２，ＸＭ，Ｘ１，・・・，Ｘ３）Ｔであれば、Ｔｉ（１）＝２、Ｔｉ（２）＝Ｍ、Ｔｉ（３）＝１、・・・、Ｔｉ（Ｍ）＝３である。また、Ｔｑ−１（ｉ）は要素Ｘｉが順列ベクトルＴｑの中で何番目の要素であるかを表す。例えば、Ｔｑ＝（ＸＭ，Ｘ１，Ｘ２，・・・，Ｘ３）Ｔであれば、Ｔｑ−１（１）＝２、Ｔｑ−１（２）＝３、Ｔｑ−１（３）＝Ｍ、・・・、Ｔｑ−１（Ｍ）＝１である。図６（ａ２）の場合では、Ｄρ（Ｔｑ，ＴＭ＋１）＝（１−３）２＋（２−１）２＋・・・＋（Ｍ−Ｍ）２と計算できる。
【００２５】
本実施形態の類似検索システムの第１の特徴は、各ｎｏｎ−ｐｉｖｏｔの索引用ベクトルサイズ（索引用ベクトルの次元数）を、あらかじめ用意しておいたデータ（学習用データ）を用いて、検索前に一意に決定（学習）する点にある。但し、索引用ベクトルサイズを学習する方法の詳細については、後述する。
【００２６】
図６（ｂ１）（ｂ２）に、索引用ベクトルとしてそれぞれスコアベクトル、順列ベクトルを用いた場合において、学習したｎｏｎ−ｐｉｖｏｔ毎の索引用ベクトルサイズの分だけ、索引用ベクトルを持つようにしたときのインデックスの例を示す。このとき、索引用ベクトルとしてスコアベクトルを用いる場合は、スコアベクトルとしてはスコアの小さい順、或いは大きい順にスコアベクトルサイズ分の要素を持つように配列し直し、該当するスコアがどのｐｉｖｏｔに対するものかが分かるように、同じ長さの順列ベクトルも保持するようにしておく。
【００２７】
例えば、図６（ｂ１）では、ＸＭ＋１のスコアベクトルサイズは３と学習されており、スコアベクトルＳＭ＋１＝（２８，４３，７０）Ｔを順列ベクトルＴＭ＋１＝（Ｘ２，ＸＭ，Ｘ１）Ｔと合わせて保持しておく。図６（ｂ２）では、ＸＭ＋１の順列ベクトルサイズは２と学習されており、順列ベクトルＴＭ＋１は、ＴＭ＋１＝（Ｘ２，ＸＭ）Ｔとなっている。図６（ｂ１）（ｂ２）において、塗り潰されている箇所はデータベースに保存しない。
【００２８】
このように、本実施例では、学習用データを用いて、ｎｏｎ−ｐｉｖｏｔ毎に索引用ベクトルサイズを学習し、各ｎｏｎ−ｐｉｖｏｔの索引用ベクトルは、当該ｎｏｎ−ｐｉｖｏｔの索引用ベクトルサイズの分だけ保存する。このようにすることで、ｎｏｎ−ｐｉｖｏｔ毎に索引用ベクトルサイズを減らすことが可能となる。その結果、データベースに保存するインデックスのサイズを減らすことができるため、システムの軽量化が実現できるという効果が得られる。但し、索引用ベクトルサイズを学習する方法の詳細については、後述する。
【００２９】
尚、この場合におけるΔスコアは、索引用ベクトルとしてスコアベクトルを用い、Δスコアとしてユークリッド距離を用いた場合、検索用データのスコアベクトルＳｑ、登録用データＸｉのスコアベクトルＳｉ（順列ベクトルはＴｉ、スコアベクトルサイズはＺｉ）とのユークリッド距離をＤｅ（Ｓｑ，Ｓｉ，Ｔｉ，Ｚｉ）とすると、
【００３０】
【数３】
【００３１】
で表される。図６（ｂ１）の場合では、Ｄｅ（Ｓｑ，ＳＭ＋１，Ｔｉ，Ｚｉ）＝（９５−２８）２＋（３９−４３）２＋・・・＋（７８−７０）２と計算できる。
【００３２】
また、索引用ベクトルとして順列ベクトルを用い、ΔスコアとしてＳｐｅａｒｍａｎ Ｒｈｏを用いた場合、検索用データの順列ベクトルＴｑ、登録用データＸｉの順列ベクトルＴｉ（順列ベクトルサイズはＺｉ）とのＳｐｅａｒｍａｎ ＲｈｏをＤρ（Ｔｑ，Ｔｉ，Ｚｉ）とすると、
【００３３】
【数４】
【００３４】
で表される。図６（ａ２）の場合では、Ｄρ（Ｔｑ，ＴＭ＋１，Ｚｉ）＝（１−３）２＋（２−１）２と計算できる。
【００３５】
このように、本実施例では検索用データとｎｏｎ−ｐｉｖｏｔとの、索引用ベクトルサイズ分のΔスコア（即ち、Ｚｉ次元ベクトル同士の距離）を計算する。このようにすることで、ｐｉｖｏｔの数（Ｍ個）分のΔスコア（即ち、Ｍ次元ベクトル同士の距離）を計算する場合と比べて、Δスコアの計算時間が短くて済む。その結果、速度が向上するという効果が得られる。
【００３６】
本実施形態の類似検索システムの第２の特徴は、このようにして各ｎｏｎ−ｐｉｖｏｔに対するΔスコアΔＳｑ，Ｍ＋１、・・・、ΔＳｑ，Ｎが得られた後、ロジスティック回帰を用いて、検索用データからのスコアｓｑ，ｉが閾値ｒより小さいという事後確率Ｐ（ｓｑ，ｉ＜ｒ｜ΔＳｑ，ｉ）（Ｍ＋１≦ｉ≦Ｎ）の大きい順にｎｏｎ−ｐｉｖｏｔの選択順序を決定する点にある。事後確率Ｐ（ｓｑ，ｉ＜ｒ｜ΔＳｑ，ｉ）は、ベイズの定理を用いて以下のように変形できる。
【００３７】
【数５】
但し、σ（ ）はロジスティックシグモイド関数であり、ａｉは、
【００３８】
【数６】
【００３９】
である。ロジスティックシグモイド関数σ（ ）は単調増加の関数であるため、ａｉの大きい順にｎｏｎ−ｐｉｖｏｔの選択順序を決定すれば、事後確率Ｐ（ｓｑ，ｉ＜ｒ｜ΔＳｑ，ｉ）の大きい順にｎｏｎ−ｐｉｖｏｔの選択順序を決定できることになる。ａｉは、ロジスティック回帰を用いて求めることができる。ロジスティック回帰では、ａｉを、
【００４０】
【数７】
【００４１】
と近似的に求める。ｗｉ，１とｗｉ，０は、ｎｏｎ−ｐｉｖｏｔ毎のロジスティック回帰の回帰係数である（Ｍ＋１≦ｉ≦Ｎ）。回帰係数としては、ｎｏｎ−ｐｉｖｏｔ共通の値を用いる方法も考えられるが、回帰係数は厳密にはｎｏｎ−ｐｉｖｏｔ毎に異なる値をとるため、ｎｏｎ−ｐｉｖｏｔ毎の回帰係数を用いた方が、ａｉをより厳密に求めることが可能となる。また、数７より、ａｉはΔスコアΔＳｑ，ｉに対して１回の掛け算と１回の足し算を行うことで近似的に求めることができるので、ａｉの計算にはほとんど時間がかからない。回帰係数は、索引用ベクトルサイズと同様、あらかじめ用意しておいたデータ（学習用データ）を用いて、検索前に一意に決定（学習）しておく。但し、回帰係数を学習する方法の詳細については、後述する。
【００４２】
ここで、各ｎｏｎ−ｐｉｖｏｔに対するΔスコアΔＳｑ，Ｍ＋１、・・・、ΔＳｑ，Ｎの集合をΔＳｑとし、その後、選択順序がｅ（１≦ｅ≦Ｎ−Ｍ）番目と決定されたｎｏｎ−ｐｉｖｏｔをＸｍ（ｅ）（Ｍ＋１≦ｍ（ｅ）≦Ｎ）とすると、ｎｏｎ−ｐｉｖｏｔとのスコアをＴ（＜Ｎ−Ｍ）回計算した後、検索用データからのスコアが閾値ｒより小さいにも関わらず、スコアが計算されずに終わる（即ち、検索漏れとなる）ｎｏｎ−ｐｉｖｏｔの個数の期待値は、
【００４３】
【数８】
【００４４】
と表せる。但し、２行目から３行目の近似は、ｎｏｎ−ｐｉｖｏｔＸｍ（ｅ）の事後確率に最も大きな影響を与えるのは、Ｘｍ（ｅ）に対するΔスコアΔＳｑ，ｍ（ｅ）であることを用いている。数８は、まだスコアの計算を行っていないｎｏｎ−ｐｉｖｏｔＸｍ（ｅ）の事後確率Ｐ（ｓｑ，ｍ（ｅ）＜ｒ｜ΔＳｑ，ｍ（ｅ））の総和で近似できているが、この総和は事後確率Ｐ（ｓｑ，ｍ（ｅ）＜ｒ｜ΔＳｑ，ｍ（ｅ））の大きい順にｎｏｎ−ｐｉｖｏｔとのスコアをＴ回計算したときに最小化することができる。
【００４５】
従って、本実施例では、ｎｏｎ−ｐｉｖｏｔ毎の回帰係数を用いて、ロジスティック回帰により、事後確率の大きい順にｎｏｎ−ｐｉｖｏｔの選択順序を決定するが、このようにすることで、検索用データからのスコアが閾値ｒより小さいにも関わらず、スコアが計算されずに検索漏れとなるｎｏｎ−ｐｉｖｏｔの個数の期待値を理論的に最小化することが可能となる。その結果、精度が大幅に向上するという効果が得られる。但し、回帰係数を学習する方法の詳細については、後述する。
【００４６】
図１に本実施形態の類似検索システムの構成例を示す。本実施形態では、生データは画像である。
【００４７】
このシステムは、ユーザから取得した登録情報をサーバ端末へ送信する登録端末１００と、登録情報を保存し、登録情報から補助情報を生成し、登録情報と補助情報を用いて検索用の生データに対する類似検索を行なうサーバ端末２００と、ユーザが入力した検索用の生データをサーバ端末２００に送信するクライアント端末３００と、ネットワーク４００から構成される。
【００４８】
登録端末１００とサーバ端末２００とクライアント端末３００は、それぞれ１台でも良いし、複数台存在しても良い。また、登録端末１００はサーバ端末２００と同一の端末であっても良いし、クライアント端末３００と同一の端末であっても良い。また、登録端末１００は無くても良い。また、サーバ端末２００はクライアント端末３００と同一の端末であっても良い。ネットワーク４００は、ＷＡＮやＬＡＮなどのネットワーク、ＵＳＢやＩＥＥＥ１３９４などを用いた機器間の通信、或いは携帯電話網やＢｌｕｅＴｏｏｔｈなどの無線通信を用いても良い。
【００４９】
例えば、登録端末１００は企業内の複数のＰＣ、サーバ端末２００は企業が運用するデータセンタ内の１台のサーバ、クライアント端末３００は複数のユーザの個人ＰＣ、ネットワーク４００はインターネットとする構成にし、企業内の従業員が画像の登録を行うようにする運用が考えられる。このとき、登録端末１００をデータセンタ内のサーバにして、サーバ管理者が画像の登録を行うようにしても良い。または、登録端末１００をユーザの個人ＰＣにして、ユーザが画像の登録を行うようにしても良い。または、登録端末１００を持たずに、サーバ端末２００がインターネットから自動的に収集するようにしても良い。または、登録端末１００とサーバ端末２００とクライアント端末３００をユーザの個人ＰＣにして、個人ＰＣ内で画像の登録、補助情報生成、検索を行うようにしても良い。
【００５０】
登録端末１００は、生データを取得する生データ取得部１０１と、通信Ｉ／Ｆ１０２とから構成される。
【００５１】
サーバ端末２００は、Ｎ個の登録用データの中からＭ個のｐｉｖｏｔを決定するｐｉｖｏｔ決定部２０１と、生データから特徴量を抽出する特徴量抽出部２０２と、特徴量同士の距離（或いは類似度）としてスコアを計算するスコア計算部２０３と、ｎｏｎ−ｐｉｖｏｔまたは検索用データのｐｉｖｏｔに対するスコアを用いて索引用ベクトルを生成する索引用ベクトル生成部２０４と、索引用ベクトル同士の距離（或いは類似度）（以後、Δスコアと呼ぶ）を計算するΔスコア計算部２０５と、学習用データを用いて、ｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習するｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部２０６と、入力された検索用データとｎｏｎ−ｐｉｖｏｔとのΔスコアを用いて前記ｎｏｎ−ｐｉｖｏｔの選択順序を決定するｎｏｎ−ｐｉｖｏｔ選択順序決定部２０７と、検索用データと登録用データとのスコアを基に、検索結果を出力する検索結果出力部２０８と、通信Ｉ／Ｆ２０９と、データベース２１０とから構成される。
【００５２】
データベース２１０は、マスタデータ２２０を保持する。マスタデータ２２０は、各登録ユーザの登録情報２３０と、補助情報２４０を保持する。登録情報２３０は、登録用データ毎に、登録用データＩＤ２３１と、生データ２３２と、特徴量２３３を保持する。補助情報２４０は、登録用データのうちどれがｐｉｖｏｔであるかが記されたｐｉｖｏｔ情報２４１と、インデックス２４２と、ｎｏｎ−ｐｉｖｏｔ毎のパラメータ２５０を保持する。インデックス２４２は、ｎｏｎ−ｐｉｖｏｔ毎に、索引用ベクトル２４３を保持する。ｎｏｎ−ｐｉｖｏｔ毎のパラメータ２５０は、ｎｏｎ−ｐｉｖｏｔ毎に、索引用ベクトルサイズ２５１と、ロジスティック回帰で用いる回帰係数２５２を保持する。
【００５３】
クライアント端末３００は、生データを取得する生データ取得部３０１と、通信Ｉ／Ｆ３０２とから構成される。
【００５４】
図２に、本実施形態における登録端末１００、サーバ端末２００、クライアント端末３００のハードウェア構成を示す。これらの端末は、図のようにＣＰＵ５００と、メモリ５０１と、ＨＤＤ５０２と、入力装置５０３と、出力装置５０４と、通信装置５０５とから構成することができる。
【００５５】
図３に、本実施形態における登録の処理手順およびデータの流れを示す。
【００５６】
登録端末１００は、ユーザから登録用の生データを取得する（ステップＳ１０１）。
【００５７】
登録端末１００は、登録用の生データをサーバ端末２００に送信する（ステップＳ１０２）。
【００５８】
サーバ端末２００は、登録用の生データから登録用の特徴量を抽出する（ステップＳ１０３）。
【００５９】
サーバ端末２００は、登録用データに固有の登録用データＩＤ２３１と、登録用の生データ２３２と、登録用の特徴量２３３とから構成される登録情報２３０を、データベース２１０に保存する（ステップＳ１０４）。
【００６０】
図４に、本実施形態における補助情報生成の処理手順およびデータの流れを示す。本処理は、登録処理を行なってから検索処理を行なうまでの間に行なう。例えば、登録直後、或いは登録を行なった日の夜間に行なうなどの方法が考えられる。また、本処理は補助情報を新規生成する場合と、前回の補助情報生成時以来、追加された登録用データの分について補助情報を更新する場合の２通りの場合がある。
【００６１】
サーバ端末２００は、補助情報を新規生成する場合は各登録用ユーザの登録情報２３０を、補助情報を更新する場合は追加された登録情報２３０をデータベース２１０から取得する（ステップＳ２０１）。
【００６２】
サーバ端末２００は、補助情報を新規生成する場合、Ｎ個の登録情報２３０の生データ２３２の中からＭ個のｐｉｖｏｔを新たに決定する（ステップＳ２０２）。補助情報を更新する場合は、このステップを省略し、追加された登録情報２３０の生データ２３２をｎｏｎ−ｐｉｖｏｔとする。ｐｉｖｏｔの決定方法は、ランダムに選択する方法や、ｐｉｖｏｔを選択するたびに、それまでに決定したｐｉｖｏｔとのスコア或いはΔスコアの総和が最小（或いは最大）となるものをｐｉｖｏｔとする、などの方法がある。
【００６３】
サーバ端末２００は、補助情報を新規生成する場合はＮ−Ｍ個の各ｎｏｎ−ｐｉｖｏｔに対して、補助情報を更新する場合は追加された各ｎｏｎ−ｐｉｖｏｔに対して、各ｐｉｖｏｔとのスコアを求めて索引用ベクトル２４３を生成する。（ステップＳ２０３）。
【００６４】
サーバ端末２００は、補助情報を新規生成する場合はＮ−Ｍ個の各ｎｏｎ−ｐｉｖｏｔに対して、補助情報を更新する場合は追加された各ｎｏｎ−ｐｉｖｏｔに対して、索引用ベクトルサイズ２５１とロジスティック回帰で用いる回帰係数２５２で構成されるパラメータ２５０を、あらかじめ用意しておいたデータ（学習用データ）を用いて一意に決定（学習）する（ステップＳ２０４）。索引用ベクトルサイズ２５１と回帰係数２５２で構成されるパラメータ２５０の学習方法の詳細は後述する。
【００６５】
サーバ端末２００は、補助情報を新規生成する場合は登録用データのうちどれがｐｉｖｏｔであるかが記されたｐｉｖｏｔ情報２４１と、Ｎ−Ｍ個の各ｎｏｎ−ｐｉｖｏｔの索引用ベクトル２４３から構成されるインデックス２４２と、学習したｎｏｎ−ｐｉｖｏｔ毎の索引用ベクトルサイズ２５１と回帰係数２５２で構成されるパラメータ２５０とを補助情報２４０として、データベース２１０に保存する。補助情報を更新する場合は生成された索引用ベクトル２４３をデータベース２１０のインデックス２４２に追加し、学習したｎｏｎ−ｐｉｖｏｔ毎の索引用ベクトルサイズ２５１と回帰係数２５２をパラメータ２５０に追加する。このとき、各ｎｏｎ−ｐｉｖｏｔの索引用ベクトル２４３は、当該ｎｏｎ−ｐｉｖｏｔの索引用ベクトルサイズ２５１の分を保存、或いは追加する（ステップＳ２０５）。
【００６６】
図５に、本実施形態における検索の処理手順およびデータの流れを示す。
【００６７】
サーバ端末２００は、データベース２１０からマスタデータ２２０を取得する（ステップＳ３０１）。
【００６８】
クライアント端末３００は、ユーザから検索用の生データを取得する（ステップＳ３０２）。
【００６９】
クライアント端末３００は、検索用の生データをサーバ端末２００に送信する（ステップＳ３０３）。
【００７０】
サーバ端末２００は、検索用の生データから検索用の特徴量を抽出する（ステップＳ３０４）。
【００７１】
サーバ端末２００は、検索用データと各ｐｉｖｏｔとのスコアを計算する（ステップＳ３０５）。
【００７２】
サーバ端末２００は、検索用データと各ｐｉｖｏｔとのスコアを基に、検索用データの索引用ベクトルを生成する（ステップＳ３０６）。
【００７３】
サーバ端末２００は、検索用データの索引用ベクトルと、ｎｏｎ−ｐｉｖｏｔ毎の索引用ベクトルから構成されるインデックス２４２と、ｎｏｎ−ｐｉｖｏｔ毎の索引用ベクトルサイズ２５１を用いて、検索用データとｎｏｎ−ｐｉｖｏｔとのΔスコアを、各ｎｏｎ−ｐｉｖｏｔに対して計算する（ステップＳ３０７）。
【００７４】
サーバ端末２００は、各ｎｏｎ−ｐｉｖｏｔに対するΔスコアΔＳｑ，Ｍ＋１、・・・、ΔＳｑ，Ｎを基に、ｎｏｎ−ｐｉｖｏｔ毎のロジスティック回帰の回帰係数ｗｉ，１とｗｉ，０を用いて、検索用データからのスコアｓｑ，ｉが閾値ｒより小さい事後確率Ｐ（ｓｑ，ｉ＜ｒ｜ΔＳｑ，ｉ）（Ｍ＋１≦ｉ≦Ｎ）と単調増加の関係にある値ａｉを数７によって求め、ａｉの大きい順にｎｏｎ−ｐｉｖｏｔの選択順序を決定する。（ステップＳ３０８）。
【００７５】
サーバ端末２００は、検索用データとｎｏｎ−ｐｉｖｏｔとのスコア計算回数ｔを０に初期化する（ステップＳ３０９）。
【００７６】
サーバ端末２００は、検索用データとステップＳ３０８で決定したｎｏｎ−ｐｉｖｏｔの選択順序に従って選択したｎｏｎ−ｐｉｖｏｔとのスコアを計算する（ステップＳ３１０）。
【００７７】
サーバ端末２００は、検索用データとｎｏｎ−ｐｉｖｏｔとのスコア計算回数ｔを１増やす（ステップＳ３１１）。
【００７８】
サーバ端末２００は、検索用データとｎｏｎ−ｐｉｖｏｔとのスコア計算回数ｔが上限値Ｔ以下であればステップＳ３１０に、上限値Ｔより大きければステップＳ３１３に進む（ステップＳ３１２）。
【００７９】
サーバ端末２００は、クライアント端末３００に検索結果の生データ２３２を送信する（ステップＳ３１３）。このとき、スコアの小さい順（或いは大きい順）にｋ個登録用データを選択し、それらを検索結果とする方法（ｋ−Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ Ｓｅａｒｃｈ）を採用しても良いし、スコアが閾値ｒより小さい（或いは大きい）登録用データを検索結果とする方法（Ｒａｎｇｅ Ｓｅａｒｃｈ）を採用しても良い。
【００８０】
クライアント端末３００は、検索結果の生データ２３２を表示する（ステップＳ３１４）。
【００８１】
以下、ステップＳ２０４において、各ｎｏｎ−ｐｉｖｏｔに対して索引用ベクトルサイズ２５１と回帰係数２５２で構成されるパラメータ２５０を学習データを用いて学習する方法について、その詳細を述べる。学習用データとしては、パラメータを学習する当該ｎｏｎ−ｐｉｖｏｔ以外のＮ−１個のｎｏｎ−ｐｉｖｏｔを用いても良いし、或いは登録用データとは別にあらかじめ用意しておいたデータを用いても良い。
【００８２】
まず、索引用ベクトルサイズＺｉをある値に固定したときの回帰係数ｗｉ，１、ｗｉ，０の学習方法を述べる。学習用データをＱ１、Ｑ２、・・・、ＱＮ’とする（Ｎ’は学習用データの個数）。また、学習用データＱｊ（１≦ｊ≦Ｎ’）とｎｏｎ−ｐｉｖｏｔＸｉ（Ｍ＋１≦ｉ≦Ｎ）とのΔスコアをΔＳｊ，ｉとし、各学習用データＱｊ（１≦ｊ≦Ｎ’）のｎｏｎ−ｐｉｖｏｔＸｉに対するΔスコアの集合を、
【００８３】
【数９】
【００８４】
とする。
【００８５】
例えば、索引用ベクトルとしてスコアベクトルを用い、Δスコアとしてユークリッド距離を用いた場合は、ΔＳｊ，ｉはＤｅ（Ｓｑｊ，Ｓｉ，Ｔｉ，Ｚｉ）と表すことができ（Ｓｑｊは学習用データＱｊのスコアベクトル）、数３によって計算できる。索引用ベクトルとして順列ベクトルを用い、ΔスコアとしてＳｐｅａｒｍａｎ Ｒｈｏを用いた場合、ΔＳｊ，ｉはＤρ（Ｔｑｊ，Ｔｉ，Ｚｉ）であり（Ｔｑｊは学習用データＱｊの順列ベクトル）、数４によって計算できる。
【００８６】
さらに、学習用データＱｊ（１≦ｊ≦Ｎ’）とｎｏｎ−ｐｉｖｏｔＸｉ（Ｍ＋１≦ｉ≦Ｎ）とのスコアｓｊ，ｉが閾値ｒより小さい場合に１、それ以外の場合に０をとるラベルをＬｊｉとし、各学習用データＱｊ（１≦ｊ≦Ｎ’）のｎｏｎ−ｐｉｖｏｔＸｉに対するラベルの集合を、
【００８７】
【数１０】
【００８８】
とする。
【００８９】
またさらに、ｎｏｎ−ｐｉｖｏｔＸｉの回帰係数を、ｗｉ，１、ｗｉ，０を並べて、
【００９０】
【数１１】
【００９１】
とベクトルの形で表すことにする。本実施例では、ｎｏｎ−ｐｉｖｏｔＸｉに対するΔスコアの集合ΔＳｉとラベルの集合Ｌｉを回帰係数ｗｉの学習に用いる。
【００９２】
回帰係数の学習方法としては、最大事後確率（Ｍａｘｉｍｕｍ Ａ Ｐｏｓｔｅｒｉｏｒ）推定、最尤（Ｍａｘｉｍｕｍ Ｌｉｋｅｌｉｈｏｏｄ）推定を用いる方法がある。ｎｏｎ−ｐｉｖｏｔＸｉに対するΔスコアの集合ΔＳｉとラベルの集合Ｌｉを用いて、最大事後確率推定により回帰係数ｗｉを学習する場合、
【００９３】
【数１２】
【００９４】
とパラメータｗｉＭＡＰを求め、これを学習結果とする。但し、２行目から４行目の変形にかけてはベイズの定理を用いており、４行目から５行目の変形にかけてはΔＳｉとｗｉが互いに独立である（即ち、Ｐ（ΔＳｉ｜ｗｉ）＝Ｐ（ΔＳｉ））と仮定している。５行目から６行目の変形にかけてはＰ（ΔＳｉ）がｗｉによらず一定であることを用いている。また、argmax f（x）はf（x）を最大にするｘを示す。最尤推定により回帰係数ｗｉを学習する場合、
【００９５】
【数１３】
【００９６】
とパラメータｗｉＭＬを求め、これを学習結果とする。
【００９７】
数１２と数１３に示されているように、最大事後確率推定では、回帰係数ｗｉの事前確率Ｐ（ｗｉ）も考慮して回帰係数を学習する点が最尤推定と異なる。このように、最大事後確率推定では回帰係数の事前確率を考慮することで、学習用データの数が少ない場合においても、最尤推定より頑健に回帰係数を学習できるという特長を持っている。特に、本実施例では、１をとるラベルＬｊｉの数（即ち、ｎｏｎ−ｐｉｖｏｔＸｉと類似している学習用データＱｊの数）が一般には非常に少ないため、最尤推定では回帰係数を適切に学習できない可能性がある。このような場合でも、最大事後確率推定であれば回帰係数をより適切に学習できる。
【００９８】
Ｐ（Ｌｉ｜ΔＳｉ，ｗｉ）は、
【００９９】
【数１４】
【０１００】
と求めることができる。但し、１行目から２行目にかけてはラベルＬｊｉが、学習用データＱｊとｎｏｎ−ｐｉｖｏｔＸｉとのスコアｓｊ，ｉが閾値ｒより小さい場合に１、それ以外の場合に０をとり、ΔスコアΔＳｊ，ｉに依存することを用いている。また、ａｊ，ｉは、
【０１０１】
【数１５】
【０１０２】
であり、前述のロジスティック回帰を用いることで、
【０１０３】
【数１６】
【０１０４】
と求めることができる。
【０１０５】
Ｐ（ｗｉ）は、例えば平均ベクトル０、分散共分散行列Σ０の正規分布を仮定し、
【０１０６】
【数１７】
【０１０７】
と求める方法がある。Σ０は適当な値をあらかじめ設定する方法や、学習用データを基に経験ベイズ法を用いて自動的に決定する方法などがある。また、０以外の平均ベクトルを用いても良いし、分布モデルとして指数分布やガンマ分布など、正規分布以外のものを用いても良い。
【０１０８】
このとき、最大事後確率推定或いは最尤推定によって求める（即ち、数１６或いは数１７を最大化する）回帰係数ｗｉＭＡＰ或いはｗｉＭＬは、例えばニュートン−ラフソン法を用いて算出できる。これは、回帰係数ｗｉの最大事後確率推定値ｗｉＭＡＰ或いは最尤推定値ｗｉＭＬを、以下の手順で逐次的に求める手法である。
１．ｗｉの初期値ｗｉ（０）を適当に設定する。例えば、ｗｉ（０）＝０とする。τ←０とする。
２．以下のようにｗｉ（τ＋１）を求める。τは逐次計算の回数である。
【０１０９】
【数１８】
【０１１０】
但し、Ｅ（ｗｉ（τ））は事後確率、或いは尤度の負の対数をとったものである。∇は微分演算子ベクトルである。これを誤差関数と呼ぶ。最大事後確率推定の場合は、
【０１１１】
【数１９】
【０１１２】
であり、最尤推定の場合は、
【０１１３】
【数２０】
【０１１４】
である。また、∇Ｅ（ｗｉ（τ））、∇∇Ｅ（ｗｉ（τ））はそれぞれＥ（ｗｉ（τ））の１階微分の列ベクトル、２階微分の行列である。例えば、最大事後確率推定の場合において、数１４、数１６、数１７を用いた場合、
【０１１５】
【数２１】
【０１１６】
【数２２】
【０１１７】
のように求めることができる。但し、
【０１１８】
【数２３】
【０１１９】
【数２４】
【０１２０】
である。
３．ｗｉ（τ＋１）と（ｗｉ（τ））との差が十分小さい、或いはτがある一定値を超えたらｗｉ（τ＋１）をｗｉＭＡＰ或いはｗｉＭＬとして終了する。そうでなければ、τ←τ＋１として、２．に戻る。
【０１２１】
次に、索引用ベクトルサイズＺｉの学習方法を述べる。これは、索引用ベクトルサイズＺｉを様々な値（例えば、１からＭまでの値）に変えて上記の操作を行い、その中で誤差関数がなるべく小さくなるｗｉＭＡＰ或いはｗｉＭＬとそれを実現したＺｉを、学習結果とすれば良い。このようにすれば、精度の観点で最も優れたパラメータを求めることが可能となる。
【０１２２】
或いは、インデックスのサイズがある一定値以下となるうち、誤差関数のｎｏｎ−ｐｉｖｏｔに対する総和がなるべく小さくなるように、ｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習するようにしても良い。これは、インデックスのサイズがある一定値以下となる範囲内で、各ｎｏｎ−ｐｉｖｏｔのＺｉを様々な値に変えてみて、誤差関数のｎｏｎ−ｐｉｖｏｔに対する総和が最も大きくなるときのｗｉＭＡＰとそれを実現したＺｉを学習結果とすれば良い（Ｍ＋１≦ｉ≦Ｎ）。このようにすることで、補助情報のサイズに要求値を設けたとき、それを満たす範囲内で精度の観点で最も優れた性能を実現することが可能となる。
【０１２３】
また、本実施例では、ラベルＬｊｉ（１≦ｊ≦Ｎ’，Ｍ＋１≦ｉ≦Ｎ）を求めるために計（Ｎ−Ｍ）×Ｎ’個のスコアを計算する必要があり、一般にはこれに大きな時間がかかる。そこで、ｎｏｎ−ｐｉｖｏｔ毎に、各学習用データ（Ｎ’個）とのΔスコアを求め、その小さい順にν’（＜Ｎ’）個の学習用データを選択し（ν’は、あらかじめシステム管理者などが定めた値）、それらを学習に用いるようにしても良い。Δスコアが小さい学習用データはｎｏｎ−ｐｉｖｏｔと類似している可能性が高いため、このようにすることでラベルＬｊｉの数が１をとる（即ち、ｎｏｎ−ｐｉｖｏｔＸｉと類似している）学習用データＱｊがなるべく減らないようにしつつ、学習に必要なスコアの計算回数を計（Ｎ−Ｍ）×ν’個まで減らすことが可能となる。その結果、学習が高速に行えるようになる、という効果が得られる。
【０１２４】
また、例えば図６のように登録用データが特徴量空間上で幾つかのクラスタを形成している場合、索引用ベクトルサイズなどのパラメータは各クラスタで似た、或いは同じ値をとる可能性がある。
【０１２５】
従って、本実施例では、ｎｏｎ−ｐｉｖｏｔに対してクラスタリングを行い、得られたクラスタ毎にパラメータの一部或いは全部が共通となるように、ｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習するようにしても良い。クラスタリングの手法としては、最短距離法、最長距離法、群平均法、ウォード法などの階層的手法を用いても良いし、Ｋ平均法などの非階層的手法を用いても良い。このようにクラスタ毎に共通のパラメータを学習することで、パラメータのサイズを減らすことが可能となる。その結果、システムのさらなる軽量化が実現できるという効果が得られる。
【０１２６】
また、本実施例において登録用データを学習用データとして用いる場合、登録用データが追加されたとき、学習用データの索引用ベクトルサイズが小さいためにパラメータの学習がうまく行えなくなる可能性がある。しかしながら、上記のようにクラスタ毎に共通のパラメータを学習すれば、登録用データが追加されたときにおいても、当該登録用データが属するクラスタに共通のパラメータを用いることで、容易にパラメータの学習を行うことが可能となる。
【実施例２】
【０１２７】
以下、図面を参照して、２つ目の実施形態について説明する。本実施形態の類似検索システムは、認証を試みるユーザ（以後、認証ユーザ）が生体情報を入力し、システムがクライアント端末内のデータベースから類似する生体情報を検索することで、認証ユーザがデータベースに登録されているユーザ（以後、登録ユーザ）のうち誰か（或いは誰でもないか）を識別し、その結果に基づいて認証を行なう生体識別システムである。
【０１２８】
図７に本実施形態の生体識別システムの構成例を示す。ここでは、図１と異なる点について述べる。本実施形態では、生データは生体情報である。
【０１２９】
このシステムは、ユーザから取得した生体情報の特徴量をサーバ端末へ送信する登録端末１００と、登録情報を保存し、登録情報から補助情報を生成し、登録情報と補助情報を用いて認証用の特徴量に対する生体識別を行なうサーバ端末２００と、グループＩＤとユーザが入力した認証用の特徴量をサーバ端末２００に送信するクライアント端末３００と、ネットワーク４００から構成される。
【０１３０】
例えば、企業内の情報アクセス制御システム、或いは勤怠管理システムであれば、登録端末１００は企業内の複数のＰＣ、サーバ端末２００は企業が運用するデータセンタ内の１台のサーバ、クライアント端末３００は複数の従業員のＰＣ、ネットワーク４００はインターネットとする構成にする方法が考えられる。また、企業内の入退室管理システムであれば、登録端末１００とサーバ端末２００とクライアント端末３００を同一の入退室管理装置とする構成にする方法が考えられる。グループＩＤ２２１は、ユーザの所属する事業所に固有の値となるようにしても良いし、クライアント端末３００毎、或いは拠点毎に固有の値となるように設定しても良い。前者の場合、ユーザが認証時にグループＩＤを入力する運用が考えられる。後者の場合、ユーザは認証時にグループＩＤを入力しなくても良い。
【０１３１】
登録端末１００は、グループＩＤとユーザ名を取得するグループＩＤ・ユーザ名取得部１０３と、生データから特徴量を抽出する特徴量抽出部１０４をさらに持つ。
【０１３２】
サーバ端末２００は、特徴量抽出部２０２を持たず、グループ絞込み部２０９ａを持ち、グループＩＤ毎にマスタデータ２２０を持つ。マスタデータ２２０は、グループＩＤ２２１を持つ。登録情報２３０は、生データ２３２を持たず、登録用データ毎にユーザ名２３４を持つ。
【０１３３】
生体情報の特徴量としては、例えば指紋であればマニューシャ、虹彩であれば虹彩コード、声紋であればケプストラムなどが考えられる。また、２つの生体情報同士のスコアとしては、指紋であれば対応するマニューシャの数や割合、虹彩であればハミング距離、声紋であればマハラノビス距離などが考えられる。
【０１３４】
クライアント端末３００は、グループＩＤを取得するグループＩＤ取得部３０３と、生データから特徴量を抽出する特徴量抽出部３０４をさらに持つ。
【０１３５】
本実施形態における登録端末１００、サーバ端末２００、クライアント端末３００のハードウェア構成は図２と同じである。
【０１３６】
図８に、本実施形態における登録処理の処理手順およびデータの流れを示す。図８のステップＳ１０１は、図３のステップＳ１０１と同じである。
【０１３７】
登録端末１００は、ユーザからグループＩＤとユーザ名を取得する（ステップＳ１０１ａ）。
【０１３８】
登録端末１００は、登録用の生データから登録用の特徴量を抽出する（ステップＳ１０２ａ）。
【０１３９】
登録端末１００は、グループＩＤとユーザ名と登録用の特徴量をサーバ端末２００に送信する（ステップＳ１０３ａ）。
【０１４０】
サーバ端末２００は、当該グループＩＤに対応するマスタデータ２２０がデータベース２１０にあれば、登録用データに固有の登録用データＩＤ２３１と、ユーザ名２３４と、登録用の特徴量２３３とから構成される登録情報２３０を、そのマスタデータ２２０に追加する。マスタデータ２２０がなければ、当該グループＩＤ２２１と、登録用データに固有の登録用データＩＤ２３１と、ユーザ名２３４と、登録用の特徴量２３３とから構成される登録情報２３０を新しく作成する（ステップＳ１０４ａ）。
【０１４１】
本実施形態における補助情報生成処理の処理手順およびデータの流れは図４と同じである。但し、グループＩＤ毎に本処理を行う。登録情報２３０の数Ｎと、ｐｉｖｏｔの数ＭはグループＩＤ毎に異なっていても良い。
【０１４２】
図９に、本実施形態における検索処理の処理手順およびデータの流れを示す。図９のステップＳ３０２、Ｓ３０５〜Ｓ３１２、Ｓ３１４は、図３のステップＳ３０２、Ｓ３０５〜Ｓ３１２、Ｓ３１４と同じである。
【０１４３】
サーバ端末２００は、データベース２１０からグループＩＤ毎にマスタデータ２２０を取得する（ステップＳ３０１ａ）。
【０１４４】
クライアント端末３００は、ユーザからグループＩＤを取得する（ステップＳ３０２ａ）。グループＩＤは、クライアント端末３００毎、或いは拠点毎に固有の値になるようにしても良く、この場合はユーザから取得しなくても良い。
【０１４５】
クライアント端末３００は、検索用の生データから検索用の特徴量を抽出する（ステップＳ３０３ａ）。
【０１４６】
クライアント端末３００は、グループＩＤと検索用の特徴量をサーバ端末２００に送信する（ステップＳ３０４ａ）。
【０１４７】
サーバ端末２００は、取得したグループＩＤに対応するマスタデータを検索対象とする。以後のステップでは検索対象としたマスタデータについて行う（ステップＳ３０５ａ）。
【０１４８】
このように、本実施例ではグループＩＤを用いた登録用データの絞込みを行う。これによって、スコアを計算する登録用データの数を大幅に減らすことが可能となる。その結果、速度が一層向上するという効果が得られる。
【０１４９】
サーバ端末２００は、クライアント端末３００に検索結果の登録用データに対応するユーザ名２３４を送信する（ステップＳ３１３ａ）。
【０１５０】
クライアント端末３００は、検索結果の登録用データに対応するユーザ名２３４を表示する（ステップＳ３１４ａ）。
【産業上の利用可能性】
【０１５１】
本発明は、画像、動画、音楽、文書、バイナリデータ、生体情報などの非構造化データの類似検索を行なう任意のアプリケーションに対して適用可能である。例えば、類似画像検索システム、類似動画検索システム、類似音楽検索システム、類似文書検索システム、ファジーハッシュを用いた類似ファイル検索システム、情報アクセス制御システム、勤怠管理システム、入退室管理システムなどへの適用が可能である。
【符号の説明】
【０１５２】
１００ 登録端末
１０１ 生データ取得部
１０２ 通信Ｉ／Ｆ
１０３ グループＩＤ・ユーザ名取得部
１０４ 特徴量抽出部
２００ サーバ端末
２０１ ｐｉｖｏｔ決定部
２０２ 特徴量抽出部
２０３ スコア計算部
２０４ 索引用ベクトル生成部
２０５ Δスコア計算部
２０６ ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部
２０７ ｎｏｎ−ｐｉｖｏｔ選択順序決定部
２０８ 検索結果出力部
２０９ 通信Ｉ／Ｆ
２０９ａ グループ絞込み部
２１０ データベース
２２０ マスタデータ
２２１ グループＩＤ
２３０ 登録情報
２３１ 登録用データＩＤ
２３２ 生データ
２３３ 特徴量
２３４ ユーザ名
２４０ 補助情報
２４１ ｐｉｖｏｔ情報
２４２ インデックス
２５０ ｎｏｎ−ｐｉｖｏｔ毎のパラメータ
２５１ 索引用ベクトルサイズ
２５２ 回帰係数
３００ クライアント端末
３０１ 生データ取得部
３０２ 通信Ｉ／Ｆ
３０３ グループＩＤ取得部
３０４ 特徴量抽出部
４００ ネットワーク
５００ ＣＰＵ
５０１ メモリ
５０２ ＨＤＤ
５０３ 入力装置
５０４ 出力装置
５０５ 通信装置
【技術分野】
【０００１】
本発明は、入力された非構造化データに類似するものを検索する方法およびシステムに関する。
【背景技術】
【０００２】
入力された画像、動画、音楽、文書、バイナリデータ、生体情報などの非構造化データに対して、それに類似する非構造化データを検索することを類似検索と呼ぶ。類似検索は、一般には、生の非構造化データ（以後、生データと呼ぶ）から、距離計算（或いは類似度計算）のために用いられる特徴量と呼ばれる情報を抽出し、特徴量同士の不一致度合いを示す距離が小さいもの（或いは、特徴量同士の一致度合いを示す類似度が大きいもの）ほど類似していると見なすことで行なわれる。特徴量同士の距離（或いは類似度）をスコアと呼ぶ。
【０００３】
例えば、検索時に入力された生データ（以後、検索用データと呼ぶ）とデータベースに登録されている生データ（以後、登録用データと呼ぶ）との距離（或いは類似度）を計算し、距離が小さい順（或いは類似度が大きい順）にｋ個登録用データを選択し、それらに関する情報を検索結果として出力する方法（ｋ−Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ Ｓｅａｒｃｈ）や、距離（或いは類似度）が閾値ｒより小さい（或いは大きい）登録用データに関する情報を検索結果として出力する方法（Ｒａｎｇｅ Ｓｅａｒｃｈ）がある。
【０００４】
このとき、登録用データの総数をＮとすると、全ての登録用データに対してスコアを計算する場合、Ｎ回のスコア計算が必要となる。一般に、スコア計算には大きな時間が必要とされるので、登録用データ数Ｎが増加すれば、それにほぼ比例して検索時間がかかるようになる。これに対して、あらかじめ登録用データ同士のスコアを計算しておき、これを用いてスコアを計算する登録用データの選択順序を決定し、途中で登録用データとのスコアの計算を止めることで、スコアを計算する回数を削減する距離索引（Ｄｉｓｔａｎｃｅ−ｂａｓｅｄ Ｉｎｄｅｘｉｎｇ）が提案されている。
【０００５】
例えば、E．CHAVEZ，K．FIGUEROA and G．NAVARRO，“Effective Proximity Retrieval by Ordering Permutations，”IEEE Trans． on Pattern Analysis and Machine Intelligence，Vol．30，No．9，pp．1647−1658（2008）（非特許文献１）では、検索前にＮ個の登録用データから、例えばランダムに、Ｍ個（Ｍ＜Ｎ）の登録用データ（以後、ｐｉｖｏｔと呼ぶ）を選択し、各登録用データと各ｐｉｖｏｔとの距離を計算し、これを用いて検索時に用いるベクトル（以後、第１の索引用ベクトルと呼ぶ）を登録用データ毎に求めておき、検索時には入力された検索用データと各ｐｉｖｏｔとの距離を計算して検索用データの第２の索引用ベクトルを求めた後、第１と第２の索引用ベクトル同士の距離の小さい順となるように残りの登録用データ（以後、ｎｏｎ−ｐｉｖｏｔと呼ぶ）の選択順序を決定している。索引用ベクトルとして、非特許文献１では距離の小さい順にｐｉｖｏｔのＩＤを並べたベクトルを求めている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】E．CHAVEZ，K．FIGUEROA and G．NAVARRO，“Effective Proximity Retrieval by Ordering Permutations，”IEEE Trans． on Pattern Analysis and Machine Intelligence，Vol．30，No．9，pp．1647−1658（2008）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１では、第１と第２の索引用ベクトル同士の距離の小さい順となるようにｎｏｎ−ｐｉｖｏｔとの選択順序を決定している。しかしながら、この方法では、途中でｎｏｎ−ｐｉｖｏｔとのスコアの計算を止めたときに、検索用データからのスコアが閾値ｒより小さいにも関わらず、スコアが計算されずに終わる（即ち、検索漏れとなる）ｎｏｎ−ｐｉｖｏｔの個数の期待値を減らすという観点、即ち、検索の精度という観点で改良の余地があった。
【０００８】
本発明の目的は、スコアが計算されずに検索漏れとなるｎｏｎ−ｐｉｖｏｔの個数の期待値を理論的に最小化することにある。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、登録用データからｐｉｖｏｔを決定するｐｉｖｏｔ決定部と、生データを取得する生データ取得部と、前記生データから特徴量を抽出する特徴量抽出部と、前記特徴量同士の距離或いは類似度としてスコアを計算するスコア計算部と、前記ｐｉｖｏｔに対する前記スコアを用いて索引用ベクトルを生成する索引用ベクトル生成部と、前記索引用ベクトル同士の距離或いは類似度としてΔスコアを計算するΔスコア計算部と、学習用データを用いて、回帰係数を含むｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習するｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部と、入力された検索用データと前記ｎｏｎ−ｐｉｖｏｔとの前記Δスコアと前記回帰係数を用いて、ロジスティック回帰により事後確率の大きい順に前記ｎｏｎ−ｐｉｖｏｔの選択順序を決定するｎｏｎ−ｐｉｖｏｔ選択順序決定部と、前記検索用データと前記登録用データとの前記スコアを基に、検索結果を出力する検索結果出力部と、前記登録用データの前記特徴量と、前記登録用データのうちどれが前記ｐｉｖｏｔであるかが記されたｐｉｖｏｔ情報と、前記ｎｏｎ−ｐｉｖｏｔ毎の前記索引用ベクトルから構成されるインデックスと、前記ｎｏｎ−ｐｉｖｏｔ毎のパラメータを保持するデータベースを持つことを特徴とする。
【発明の効果】
【００１０】
本発明によれば、ｎｏｎ−ｐｉｖｏｔ毎の回帰係数を用いて、ロジスティック回帰により、事後確率の大きい順にｎｏｎ−ｐｉｖｏｔの選択順序を決定する。このようにすることで、検索用データからのスコアが閾値ｒより小さいにも関わらず、スコアが計算されずに検索漏れとなるｎｏｎ−ｐｉｖｏｔの個数の期待値を理論的に最小化することが可能となる。その結果、精度が大幅に向上するという効果が得られる。
【図面の簡単な説明】
【００１１】
【図１】本発明の第一の実施形態の機能構成を示すブロック図である。
【図２】本発明の第一、第二の実施形態のハードウェア構成を示すブロック図である。
【図３】本発明の第一の実施形態の登録処理を示すフロー図である。
【図４】本発明の第一、第二の実施形態の補助情報生成処理を示すフロー図である。
【図５】本発明の第一の実施形態の検索処理を示すフロー図である。
【図６】特徴量空間とインデックスを示す概略図である。
【図７】本発明の第二の実施形態の機能構成を示すブロック図である。
【図８】本発明の第二の実施形態の登録処理を示すフロー図である。
【図９】本発明の第二の実施形態の検索処理を示すフロー図である。
【発明を実施するための形態】
【実施例１】
【００１２】
以下、図面を参照して、１つ目の実施形態について説明する。
【００１３】
本実施形態の類似検索システムは、ユーザが画像を入力し、システムがサーバ端末内のデータベースから類似する画像を検索する類似画像検索システムである。画像の代わりに動画、音楽、文書、バイナリデータなどの非構造化データを用いるようにしても良い。本実施形態の類似検索システムでは、画像の特徴量としてカラーヒストグラムを用い、スコアとして特徴量同士のユークリッド距離を用いる。
【００１４】
本実施形態の類似検索システムでは、あらかじめＮ個の登録データからＭ個をｐｉｖｏｔとして選択する。ｐｉｖｏｔの選択方法としては、例えばランダムに選ぶ方法がある。次に、残りの各登録データ（各ｎｏｎ−ｐｉｖｏｔ）と各ｐｉｖｏｔとのスコアを計算し、これを基に検索時に用いる第１の索引用ベクトルをｎｏｎ−ｐｉｖｏｔ毎に求める。検索時には、入力された検索用データと各ｐｉｖｏｔとのスコアを計算し、これを基に検索用データの第２の索引用ベクトルを求める。索引用ベクトルは、各ｎｏｎ−ｐｉｖｏｔと検索用データの位置関係を、直接スコアを求めることなく知る手がかりとなるベクトルである。一般に、検索用データと各登録用データとのスコア計算には大きな時間が必要とされるが、索引用ベクトル同士の距離（或いは類似度）（以後、Δスコアと呼ぶ）を用いてｎｏｎ−ｐｉｖｏｔの選択順序を決定し、ｎｏｎ−ｐｉｖｏｔとのスコア計算をＴ（＜Ｎ−Ｍ）回行った後（Ｔは、あらかじめシステム管理者などが定めた上限値）、ｎｏｎ−ｐｉｖｏｔとのスコア計算を途中で止めることで、スコアを計算する回数を削減する（即ち高速に検索を行う）ことが可能となる。
索引用ベクトルとしては、各ｐｉｖｏｔとのスコアで構成されるベクトル（以後、スコアベクトルと呼ぶ）であっても良いし、距離（或いは類似度）の小さい順（或いは大きい順）にｐｉｖｏｔのＩＤを並べたベクトル（以後、順列ベクトルと呼ぶ）であっても良い。各ｎｏｎ−ｐｉｖｏｔの第１の索引用ベクトルをまとめたものを、インデックスと呼ぶ。
【００１５】
図６に、特徴量空間における検索用データＱと各登録用データＸ１、Ｘ２、・・・、ＸＮの例を示す。但し、Ｘ１、Ｘ２、・・・、ＸＭはｐｉｖｏｔ、ＸＭ＋１、ＸＭ＋２、・・・、ＸＮはｎｏｎ−ｐｉｖｏｔを表す。ここでは２つのクラスタが形成されており、お互いのクラスタは大きく離れている。また、特徴量の次元数は非常に高く、特徴量同士のスコアを計算するのに大きな時間がかかる。
【００１６】
図６（ａ１）（ａ２）に、索引用ベクトルとしてそれぞれスコアベクトル、順列ベクトルを用いた場合における検索用データの第２の索引用ベクトルと、インデックスの例を示す。但し、スコアとしては特徴量同士のユークリッド距離を用いている。
【００１７】
例えば、図６（ａ１）では、ＸＭ＋１とＸ１とのスコアは７０となっており、ＸＭ＋１のスコアベクトルＳＭ＋１は、ＳＭ＋１＝（７０，２８，１０５３，・・・，４３）Ｔとなっている。また、図６（ａ２）では、ＸＭ＋１と各ｐｉｖｏｔとのスコアの中で、最も小さいスコアを実現したｐｉｖｏｔがＸ２となっており、ＸＭ＋１のは、ＴＭ＋１＝（Ｘ２，ＸＭ−１，・・・，Ｘ３）Ｔとなっている。
【００１８】
また、Δスコア（索引用ベクトル同士の距離或いは類似度）としては、索引用ベクトルとしてスコアベクトルを用いた場合では、例えば市街地距離、ユークリッド距離などが考えられ、順列ベクトルを用いた場合では、例えばＳｐｅａｒｍａｎ Ｒｈｏなどが考えられる。また、上述した距離を距離としてとり得る値の最大値から差し引いたものなどを、類似度として用いるようにしても良い。
【００１９】
例えば、索引用ベクトルとしてスコアベクトルを用い、Δスコアとしてユークリッド距離を用いた場合、検索用データのスコアベクトルＳｑ、登録用データＸｉのスコアベクトルＳｉとのユークリッド距離をＤｅ（Ｓｑ，Ｓｉ）とすると、
【００２０】
【数１】
【００２１】
で表される。ここで、Ｓｉ（ｚ）はスコアベクトルＳｉにおけるｚ番目の要素を表す。図６（ａ１）の場合では、Ｄｅ（Ｓｑ，ＳＭ＋１）＝（７８−７０）２＋（９５−２８）２＋・・・＋（３９−４３）２と計算できる。
【００２２】
また、索引用ベクトルとして順列ベクトルを用い、ΔスコアとしてＳｐｅａｒｍａｎ Ｒｈｏを用いた場合、検索用データの順列ベクトルＴｑ、登録用データＸｉの順列ベクトルＴｉとのＳｐｅａｒｍａｎ ＲｈｏをＤρ（Ｔｑ，Ｔｉ）とすると、
【００２３】
【数２】
【００２４】
で表される。ここで、Ｔｉ（ｚ）は順列ベクトルＴｉにおけるｚ番目の要素の添え字の数字を表す。例えば、Ｔｉ＝（Ｘ２，ＸＭ，Ｘ１，・・・，Ｘ３）Ｔであれば、Ｔｉ（１）＝２、Ｔｉ（２）＝Ｍ、Ｔｉ（３）＝１、・・・、Ｔｉ（Ｍ）＝３である。また、Ｔｑ−１（ｉ）は要素Ｘｉが順列ベクトルＴｑの中で何番目の要素であるかを表す。例えば、Ｔｑ＝（ＸＭ，Ｘ１，Ｘ２，・・・，Ｘ３）Ｔであれば、Ｔｑ−１（１）＝２、Ｔｑ−１（２）＝３、Ｔｑ−１（３）＝Ｍ、・・・、Ｔｑ−１（Ｍ）＝１である。図６（ａ２）の場合では、Ｄρ（Ｔｑ，ＴＭ＋１）＝（１−３）２＋（２−１）２＋・・・＋（Ｍ−Ｍ）２と計算できる。
【００２５】
本実施形態の類似検索システムの第１の特徴は、各ｎｏｎ−ｐｉｖｏｔの索引用ベクトルサイズ（索引用ベクトルの次元数）を、あらかじめ用意しておいたデータ（学習用データ）を用いて、検索前に一意に決定（学習）する点にある。但し、索引用ベクトルサイズを学習する方法の詳細については、後述する。
【００２６】
図６（ｂ１）（ｂ２）に、索引用ベクトルとしてそれぞれスコアベクトル、順列ベクトルを用いた場合において、学習したｎｏｎ−ｐｉｖｏｔ毎の索引用ベクトルサイズの分だけ、索引用ベクトルを持つようにしたときのインデックスの例を示す。このとき、索引用ベクトルとしてスコアベクトルを用いる場合は、スコアベクトルとしてはスコアの小さい順、或いは大きい順にスコアベクトルサイズ分の要素を持つように配列し直し、該当するスコアがどのｐｉｖｏｔに対するものかが分かるように、同じ長さの順列ベクトルも保持するようにしておく。
【００２７】
例えば、図６（ｂ１）では、ＸＭ＋１のスコアベクトルサイズは３と学習されており、スコアベクトルＳＭ＋１＝（２８，４３，７０）Ｔを順列ベクトルＴＭ＋１＝（Ｘ２，ＸＭ，Ｘ１）Ｔと合わせて保持しておく。図６（ｂ２）では、ＸＭ＋１の順列ベクトルサイズは２と学習されており、順列ベクトルＴＭ＋１は、ＴＭ＋１＝（Ｘ２，ＸＭ）Ｔとなっている。図６（ｂ１）（ｂ２）において、塗り潰されている箇所はデータベースに保存しない。
【００２８】
このように、本実施例では、学習用データを用いて、ｎｏｎ−ｐｉｖｏｔ毎に索引用ベクトルサイズを学習し、各ｎｏｎ−ｐｉｖｏｔの索引用ベクトルは、当該ｎｏｎ−ｐｉｖｏｔの索引用ベクトルサイズの分だけ保存する。このようにすることで、ｎｏｎ−ｐｉｖｏｔ毎に索引用ベクトルサイズを減らすことが可能となる。その結果、データベースに保存するインデックスのサイズを減らすことができるため、システムの軽量化が実現できるという効果が得られる。但し、索引用ベクトルサイズを学習する方法の詳細については、後述する。
【００２９】
尚、この場合におけるΔスコアは、索引用ベクトルとしてスコアベクトルを用い、Δスコアとしてユークリッド距離を用いた場合、検索用データのスコアベクトルＳｑ、登録用データＸｉのスコアベクトルＳｉ（順列ベクトルはＴｉ、スコアベクトルサイズはＺｉ）とのユークリッド距離をＤｅ（Ｓｑ，Ｓｉ，Ｔｉ，Ｚｉ）とすると、
【００３０】
【数３】
【００３１】
で表される。図６（ｂ１）の場合では、Ｄｅ（Ｓｑ，ＳＭ＋１，Ｔｉ，Ｚｉ）＝（９５−２８）２＋（３９−４３）２＋・・・＋（７８−７０）２と計算できる。
【００３２】
また、索引用ベクトルとして順列ベクトルを用い、ΔスコアとしてＳｐｅａｒｍａｎ Ｒｈｏを用いた場合、検索用データの順列ベクトルＴｑ、登録用データＸｉの順列ベクトルＴｉ（順列ベクトルサイズはＺｉ）とのＳｐｅａｒｍａｎ ＲｈｏをＤρ（Ｔｑ，Ｔｉ，Ｚｉ）とすると、
【００３３】
【数４】
【００３４】
で表される。図６（ａ２）の場合では、Ｄρ（Ｔｑ，ＴＭ＋１，Ｚｉ）＝（１−３）２＋（２−１）２と計算できる。
【００３５】
このように、本実施例では検索用データとｎｏｎ−ｐｉｖｏｔとの、索引用ベクトルサイズ分のΔスコア（即ち、Ｚｉ次元ベクトル同士の距離）を計算する。このようにすることで、ｐｉｖｏｔの数（Ｍ個）分のΔスコア（即ち、Ｍ次元ベクトル同士の距離）を計算する場合と比べて、Δスコアの計算時間が短くて済む。その結果、速度が向上するという効果が得られる。
【００３６】
本実施形態の類似検索システムの第２の特徴は、このようにして各ｎｏｎ−ｐｉｖｏｔに対するΔスコアΔＳｑ，Ｍ＋１、・・・、ΔＳｑ，Ｎが得られた後、ロジスティック回帰を用いて、検索用データからのスコアｓｑ，ｉが閾値ｒより小さいという事後確率Ｐ（ｓｑ，ｉ＜ｒ｜ΔＳｑ，ｉ）（Ｍ＋１≦ｉ≦Ｎ）の大きい順にｎｏｎ−ｐｉｖｏｔの選択順序を決定する点にある。事後確率Ｐ（ｓｑ，ｉ＜ｒ｜ΔＳｑ，ｉ）は、ベイズの定理を用いて以下のように変形できる。
【００３７】
【数５】
但し、σ（ ）はロジスティックシグモイド関数であり、ａｉは、
【００３８】
【数６】
【００３９】
である。ロジスティックシグモイド関数σ（ ）は単調増加の関数であるため、ａｉの大きい順にｎｏｎ−ｐｉｖｏｔの選択順序を決定すれば、事後確率Ｐ（ｓｑ，ｉ＜ｒ｜ΔＳｑ，ｉ）の大きい順にｎｏｎ−ｐｉｖｏｔの選択順序を決定できることになる。ａｉは、ロジスティック回帰を用いて求めることができる。ロジスティック回帰では、ａｉを、
【００４０】
【数７】
【００４１】
と近似的に求める。ｗｉ，１とｗｉ，０は、ｎｏｎ−ｐｉｖｏｔ毎のロジスティック回帰の回帰係数である（Ｍ＋１≦ｉ≦Ｎ）。回帰係数としては、ｎｏｎ−ｐｉｖｏｔ共通の値を用いる方法も考えられるが、回帰係数は厳密にはｎｏｎ−ｐｉｖｏｔ毎に異なる値をとるため、ｎｏｎ−ｐｉｖｏｔ毎の回帰係数を用いた方が、ａｉをより厳密に求めることが可能となる。また、数７より、ａｉはΔスコアΔＳｑ，ｉに対して１回の掛け算と１回の足し算を行うことで近似的に求めることができるので、ａｉの計算にはほとんど時間がかからない。回帰係数は、索引用ベクトルサイズと同様、あらかじめ用意しておいたデータ（学習用データ）を用いて、検索前に一意に決定（学習）しておく。但し、回帰係数を学習する方法の詳細については、後述する。
【００４２】
ここで、各ｎｏｎ−ｐｉｖｏｔに対するΔスコアΔＳｑ，Ｍ＋１、・・・、ΔＳｑ，Ｎの集合をΔＳｑとし、その後、選択順序がｅ（１≦ｅ≦Ｎ−Ｍ）番目と決定されたｎｏｎ−ｐｉｖｏｔをＸｍ（ｅ）（Ｍ＋１≦ｍ（ｅ）≦Ｎ）とすると、ｎｏｎ−ｐｉｖｏｔとのスコアをＴ（＜Ｎ−Ｍ）回計算した後、検索用データからのスコアが閾値ｒより小さいにも関わらず、スコアが計算されずに終わる（即ち、検索漏れとなる）ｎｏｎ−ｐｉｖｏｔの個数の期待値は、
【００４３】
【数８】
【００４４】
と表せる。但し、２行目から３行目の近似は、ｎｏｎ−ｐｉｖｏｔＸｍ（ｅ）の事後確率に最も大きな影響を与えるのは、Ｘｍ（ｅ）に対するΔスコアΔＳｑ，ｍ（ｅ）であることを用いている。数８は、まだスコアの計算を行っていないｎｏｎ−ｐｉｖｏｔＸｍ（ｅ）の事後確率Ｐ（ｓｑ，ｍ（ｅ）＜ｒ｜ΔＳｑ，ｍ（ｅ））の総和で近似できているが、この総和は事後確率Ｐ（ｓｑ，ｍ（ｅ）＜ｒ｜ΔＳｑ，ｍ（ｅ））の大きい順にｎｏｎ−ｐｉｖｏｔとのスコアをＴ回計算したときに最小化することができる。
【００４５】
従って、本実施例では、ｎｏｎ−ｐｉｖｏｔ毎の回帰係数を用いて、ロジスティック回帰により、事後確率の大きい順にｎｏｎ−ｐｉｖｏｔの選択順序を決定するが、このようにすることで、検索用データからのスコアが閾値ｒより小さいにも関わらず、スコアが計算されずに検索漏れとなるｎｏｎ−ｐｉｖｏｔの個数の期待値を理論的に最小化することが可能となる。その結果、精度が大幅に向上するという効果が得られる。但し、回帰係数を学習する方法の詳細については、後述する。
【００４６】
図１に本実施形態の類似検索システムの構成例を示す。本実施形態では、生データは画像である。
【００４７】
このシステムは、ユーザから取得した登録情報をサーバ端末へ送信する登録端末１００と、登録情報を保存し、登録情報から補助情報を生成し、登録情報と補助情報を用いて検索用の生データに対する類似検索を行なうサーバ端末２００と、ユーザが入力した検索用の生データをサーバ端末２００に送信するクライアント端末３００と、ネットワーク４００から構成される。
【００４８】
登録端末１００とサーバ端末２００とクライアント端末３００は、それぞれ１台でも良いし、複数台存在しても良い。また、登録端末１００はサーバ端末２００と同一の端末であっても良いし、クライアント端末３００と同一の端末であっても良い。また、登録端末１００は無くても良い。また、サーバ端末２００はクライアント端末３００と同一の端末であっても良い。ネットワーク４００は、ＷＡＮやＬＡＮなどのネットワーク、ＵＳＢやＩＥＥＥ１３９４などを用いた機器間の通信、或いは携帯電話網やＢｌｕｅＴｏｏｔｈなどの無線通信を用いても良い。
【００４９】
例えば、登録端末１００は企業内の複数のＰＣ、サーバ端末２００は企業が運用するデータセンタ内の１台のサーバ、クライアント端末３００は複数のユーザの個人ＰＣ、ネットワーク４００はインターネットとする構成にし、企業内の従業員が画像の登録を行うようにする運用が考えられる。このとき、登録端末１００をデータセンタ内のサーバにして、サーバ管理者が画像の登録を行うようにしても良い。または、登録端末１００をユーザの個人ＰＣにして、ユーザが画像の登録を行うようにしても良い。または、登録端末１００を持たずに、サーバ端末２００がインターネットから自動的に収集するようにしても良い。または、登録端末１００とサーバ端末２００とクライアント端末３００をユーザの個人ＰＣにして、個人ＰＣ内で画像の登録、補助情報生成、検索を行うようにしても良い。
【００５０】
登録端末１００は、生データを取得する生データ取得部１０１と、通信Ｉ／Ｆ１０２とから構成される。
【００５１】
サーバ端末２００は、Ｎ個の登録用データの中からＭ個のｐｉｖｏｔを決定するｐｉｖｏｔ決定部２０１と、生データから特徴量を抽出する特徴量抽出部２０２と、特徴量同士の距離（或いは類似度）としてスコアを計算するスコア計算部２０３と、ｎｏｎ−ｐｉｖｏｔまたは検索用データのｐｉｖｏｔに対するスコアを用いて索引用ベクトルを生成する索引用ベクトル生成部２０４と、索引用ベクトル同士の距離（或いは類似度）（以後、Δスコアと呼ぶ）を計算するΔスコア計算部２０５と、学習用データを用いて、ｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習するｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部２０６と、入力された検索用データとｎｏｎ−ｐｉｖｏｔとのΔスコアを用いて前記ｎｏｎ−ｐｉｖｏｔの選択順序を決定するｎｏｎ−ｐｉｖｏｔ選択順序決定部２０７と、検索用データと登録用データとのスコアを基に、検索結果を出力する検索結果出力部２０８と、通信Ｉ／Ｆ２０９と、データベース２１０とから構成される。
【００５２】
データベース２１０は、マスタデータ２２０を保持する。マスタデータ２２０は、各登録ユーザの登録情報２３０と、補助情報２４０を保持する。登録情報２３０は、登録用データ毎に、登録用データＩＤ２３１と、生データ２３２と、特徴量２３３を保持する。補助情報２４０は、登録用データのうちどれがｐｉｖｏｔであるかが記されたｐｉｖｏｔ情報２４１と、インデックス２４２と、ｎｏｎ−ｐｉｖｏｔ毎のパラメータ２５０を保持する。インデックス２４２は、ｎｏｎ−ｐｉｖｏｔ毎に、索引用ベクトル２４３を保持する。ｎｏｎ−ｐｉｖｏｔ毎のパラメータ２５０は、ｎｏｎ−ｐｉｖｏｔ毎に、索引用ベクトルサイズ２５１と、ロジスティック回帰で用いる回帰係数２５２を保持する。
【００５３】
クライアント端末３００は、生データを取得する生データ取得部３０１と、通信Ｉ／Ｆ３０２とから構成される。
【００５４】
図２に、本実施形態における登録端末１００、サーバ端末２００、クライアント端末３００のハードウェア構成を示す。これらの端末は、図のようにＣＰＵ５００と、メモリ５０１と、ＨＤＤ５０２と、入力装置５０３と、出力装置５０４と、通信装置５０５とから構成することができる。
【００５５】
図３に、本実施形態における登録の処理手順およびデータの流れを示す。
【００５６】
登録端末１００は、ユーザから登録用の生データを取得する（ステップＳ１０１）。
【００５７】
登録端末１００は、登録用の生データをサーバ端末２００に送信する（ステップＳ１０２）。
【００５８】
サーバ端末２００は、登録用の生データから登録用の特徴量を抽出する（ステップＳ１０３）。
【００５９】
サーバ端末２００は、登録用データに固有の登録用データＩＤ２３１と、登録用の生データ２３２と、登録用の特徴量２３３とから構成される登録情報２３０を、データベース２１０に保存する（ステップＳ１０４）。
【００６０】
図４に、本実施形態における補助情報生成の処理手順およびデータの流れを示す。本処理は、登録処理を行なってから検索処理を行なうまでの間に行なう。例えば、登録直後、或いは登録を行なった日の夜間に行なうなどの方法が考えられる。また、本処理は補助情報を新規生成する場合と、前回の補助情報生成時以来、追加された登録用データの分について補助情報を更新する場合の２通りの場合がある。
【００６１】
サーバ端末２００は、補助情報を新規生成する場合は各登録用ユーザの登録情報２３０を、補助情報を更新する場合は追加された登録情報２３０をデータベース２１０から取得する（ステップＳ２０１）。
【００６２】
サーバ端末２００は、補助情報を新規生成する場合、Ｎ個の登録情報２３０の生データ２３２の中からＭ個のｐｉｖｏｔを新たに決定する（ステップＳ２０２）。補助情報を更新する場合は、このステップを省略し、追加された登録情報２３０の生データ２３２をｎｏｎ−ｐｉｖｏｔとする。ｐｉｖｏｔの決定方法は、ランダムに選択する方法や、ｐｉｖｏｔを選択するたびに、それまでに決定したｐｉｖｏｔとのスコア或いはΔスコアの総和が最小（或いは最大）となるものをｐｉｖｏｔとする、などの方法がある。
【００６３】
サーバ端末２００は、補助情報を新規生成する場合はＮ−Ｍ個の各ｎｏｎ−ｐｉｖｏｔに対して、補助情報を更新する場合は追加された各ｎｏｎ−ｐｉｖｏｔに対して、各ｐｉｖｏｔとのスコアを求めて索引用ベクトル２４３を生成する。（ステップＳ２０３）。
【００６４】
サーバ端末２００は、補助情報を新規生成する場合はＮ−Ｍ個の各ｎｏｎ−ｐｉｖｏｔに対して、補助情報を更新する場合は追加された各ｎｏｎ−ｐｉｖｏｔに対して、索引用ベクトルサイズ２５１とロジスティック回帰で用いる回帰係数２５２で構成されるパラメータ２５０を、あらかじめ用意しておいたデータ（学習用データ）を用いて一意に決定（学習）する（ステップＳ２０４）。索引用ベクトルサイズ２５１と回帰係数２５２で構成されるパラメータ２５０の学習方法の詳細は後述する。
【００６５】
サーバ端末２００は、補助情報を新規生成する場合は登録用データのうちどれがｐｉｖｏｔであるかが記されたｐｉｖｏｔ情報２４１と、Ｎ−Ｍ個の各ｎｏｎ−ｐｉｖｏｔの索引用ベクトル２４３から構成されるインデックス２４２と、学習したｎｏｎ−ｐｉｖｏｔ毎の索引用ベクトルサイズ２５１と回帰係数２５２で構成されるパラメータ２５０とを補助情報２４０として、データベース２１０に保存する。補助情報を更新する場合は生成された索引用ベクトル２４３をデータベース２１０のインデックス２４２に追加し、学習したｎｏｎ−ｐｉｖｏｔ毎の索引用ベクトルサイズ２５１と回帰係数２５２をパラメータ２５０に追加する。このとき、各ｎｏｎ−ｐｉｖｏｔの索引用ベクトル２４３は、当該ｎｏｎ−ｐｉｖｏｔの索引用ベクトルサイズ２５１の分を保存、或いは追加する（ステップＳ２０５）。
【００６６】
図５に、本実施形態における検索の処理手順およびデータの流れを示す。
【００６７】
サーバ端末２００は、データベース２１０からマスタデータ２２０を取得する（ステップＳ３０１）。
【００６８】
クライアント端末３００は、ユーザから検索用の生データを取得する（ステップＳ３０２）。
【００６９】
クライアント端末３００は、検索用の生データをサーバ端末２００に送信する（ステップＳ３０３）。
【００７０】
サーバ端末２００は、検索用の生データから検索用の特徴量を抽出する（ステップＳ３０４）。
【００７１】
サーバ端末２００は、検索用データと各ｐｉｖｏｔとのスコアを計算する（ステップＳ３０５）。
【００７２】
サーバ端末２００は、検索用データと各ｐｉｖｏｔとのスコアを基に、検索用データの索引用ベクトルを生成する（ステップＳ３０６）。
【００７３】
サーバ端末２００は、検索用データの索引用ベクトルと、ｎｏｎ−ｐｉｖｏｔ毎の索引用ベクトルから構成されるインデックス２４２と、ｎｏｎ−ｐｉｖｏｔ毎の索引用ベクトルサイズ２５１を用いて、検索用データとｎｏｎ−ｐｉｖｏｔとのΔスコアを、各ｎｏｎ−ｐｉｖｏｔに対して計算する（ステップＳ３０７）。
【００７４】
サーバ端末２００は、各ｎｏｎ−ｐｉｖｏｔに対するΔスコアΔＳｑ，Ｍ＋１、・・・、ΔＳｑ，Ｎを基に、ｎｏｎ−ｐｉｖｏｔ毎のロジスティック回帰の回帰係数ｗｉ，１とｗｉ，０を用いて、検索用データからのスコアｓｑ，ｉが閾値ｒより小さい事後確率Ｐ（ｓｑ，ｉ＜ｒ｜ΔＳｑ，ｉ）（Ｍ＋１≦ｉ≦Ｎ）と単調増加の関係にある値ａｉを数７によって求め、ａｉの大きい順にｎｏｎ−ｐｉｖｏｔの選択順序を決定する。（ステップＳ３０８）。
【００７５】
サーバ端末２００は、検索用データとｎｏｎ−ｐｉｖｏｔとのスコア計算回数ｔを０に初期化する（ステップＳ３０９）。
【００７６】
サーバ端末２００は、検索用データとステップＳ３０８で決定したｎｏｎ−ｐｉｖｏｔの選択順序に従って選択したｎｏｎ−ｐｉｖｏｔとのスコアを計算する（ステップＳ３１０）。
【００７７】
サーバ端末２００は、検索用データとｎｏｎ−ｐｉｖｏｔとのスコア計算回数ｔを１増やす（ステップＳ３１１）。
【００７８】
サーバ端末２００は、検索用データとｎｏｎ−ｐｉｖｏｔとのスコア計算回数ｔが上限値Ｔ以下であればステップＳ３１０に、上限値Ｔより大きければステップＳ３１３に進む（ステップＳ３１２）。
【００７９】
サーバ端末２００は、クライアント端末３００に検索結果の生データ２３２を送信する（ステップＳ３１３）。このとき、スコアの小さい順（或いは大きい順）にｋ個登録用データを選択し、それらを検索結果とする方法（ｋ−Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ Ｓｅａｒｃｈ）を採用しても良いし、スコアが閾値ｒより小さい（或いは大きい）登録用データを検索結果とする方法（Ｒａｎｇｅ Ｓｅａｒｃｈ）を採用しても良い。
【００８０】
クライアント端末３００は、検索結果の生データ２３２を表示する（ステップＳ３１４）。
【００８１】
以下、ステップＳ２０４において、各ｎｏｎ−ｐｉｖｏｔに対して索引用ベクトルサイズ２５１と回帰係数２５２で構成されるパラメータ２５０を学習データを用いて学習する方法について、その詳細を述べる。学習用データとしては、パラメータを学習する当該ｎｏｎ−ｐｉｖｏｔ以外のＮ−１個のｎｏｎ−ｐｉｖｏｔを用いても良いし、或いは登録用データとは別にあらかじめ用意しておいたデータを用いても良い。
【００８２】
まず、索引用ベクトルサイズＺｉをある値に固定したときの回帰係数ｗｉ，１、ｗｉ，０の学習方法を述べる。学習用データをＱ１、Ｑ２、・・・、ＱＮ’とする（Ｎ’は学習用データの個数）。また、学習用データＱｊ（１≦ｊ≦Ｎ’）とｎｏｎ−ｐｉｖｏｔＸｉ（Ｍ＋１≦ｉ≦Ｎ）とのΔスコアをΔＳｊ，ｉとし、各学習用データＱｊ（１≦ｊ≦Ｎ’）のｎｏｎ−ｐｉｖｏｔＸｉに対するΔスコアの集合を、
【００８３】
【数９】
【００８４】
とする。
【００８５】
例えば、索引用ベクトルとしてスコアベクトルを用い、Δスコアとしてユークリッド距離を用いた場合は、ΔＳｊ，ｉはＤｅ（Ｓｑｊ，Ｓｉ，Ｔｉ，Ｚｉ）と表すことができ（Ｓｑｊは学習用データＱｊのスコアベクトル）、数３によって計算できる。索引用ベクトルとして順列ベクトルを用い、ΔスコアとしてＳｐｅａｒｍａｎ Ｒｈｏを用いた場合、ΔＳｊ，ｉはＤρ（Ｔｑｊ，Ｔｉ，Ｚｉ）であり（Ｔｑｊは学習用データＱｊの順列ベクトル）、数４によって計算できる。
【００８６】
さらに、学習用データＱｊ（１≦ｊ≦Ｎ’）とｎｏｎ−ｐｉｖｏｔＸｉ（Ｍ＋１≦ｉ≦Ｎ）とのスコアｓｊ，ｉが閾値ｒより小さい場合に１、それ以外の場合に０をとるラベルをＬｊｉとし、各学習用データＱｊ（１≦ｊ≦Ｎ’）のｎｏｎ−ｐｉｖｏｔＸｉに対するラベルの集合を、
【００８７】
【数１０】
【００８８】
とする。
【００８９】
またさらに、ｎｏｎ−ｐｉｖｏｔＸｉの回帰係数を、ｗｉ，１、ｗｉ，０を並べて、
【００９０】
【数１１】
【００９１】
とベクトルの形で表すことにする。本実施例では、ｎｏｎ−ｐｉｖｏｔＸｉに対するΔスコアの集合ΔＳｉとラベルの集合Ｌｉを回帰係数ｗｉの学習に用いる。
【００９２】
回帰係数の学習方法としては、最大事後確率（Ｍａｘｉｍｕｍ Ａ Ｐｏｓｔｅｒｉｏｒ）推定、最尤（Ｍａｘｉｍｕｍ Ｌｉｋｅｌｉｈｏｏｄ）推定を用いる方法がある。ｎｏｎ−ｐｉｖｏｔＸｉに対するΔスコアの集合ΔＳｉとラベルの集合Ｌｉを用いて、最大事後確率推定により回帰係数ｗｉを学習する場合、
【００９３】
【数１２】
【００９４】
とパラメータｗｉＭＡＰを求め、これを学習結果とする。但し、２行目から４行目の変形にかけてはベイズの定理を用いており、４行目から５行目の変形にかけてはΔＳｉとｗｉが互いに独立である（即ち、Ｐ（ΔＳｉ｜ｗｉ）＝Ｐ（ΔＳｉ））と仮定している。５行目から６行目の変形にかけてはＰ（ΔＳｉ）がｗｉによらず一定であることを用いている。また、argmax f（x）はf（x）を最大にするｘを示す。最尤推定により回帰係数ｗｉを学習する場合、
【００９５】
【数１３】
【００９６】
とパラメータｗｉＭＬを求め、これを学習結果とする。
【００９７】
数１２と数１３に示されているように、最大事後確率推定では、回帰係数ｗｉの事前確率Ｐ（ｗｉ）も考慮して回帰係数を学習する点が最尤推定と異なる。このように、最大事後確率推定では回帰係数の事前確率を考慮することで、学習用データの数が少ない場合においても、最尤推定より頑健に回帰係数を学習できるという特長を持っている。特に、本実施例では、１をとるラベルＬｊｉの数（即ち、ｎｏｎ−ｐｉｖｏｔＸｉと類似している学習用データＱｊの数）が一般には非常に少ないため、最尤推定では回帰係数を適切に学習できない可能性がある。このような場合でも、最大事後確率推定であれば回帰係数をより適切に学習できる。
【００９８】
Ｐ（Ｌｉ｜ΔＳｉ，ｗｉ）は、
【００９９】
【数１４】
【０１００】
と求めることができる。但し、１行目から２行目にかけてはラベルＬｊｉが、学習用データＱｊとｎｏｎ−ｐｉｖｏｔＸｉとのスコアｓｊ，ｉが閾値ｒより小さい場合に１、それ以外の場合に０をとり、ΔスコアΔＳｊ，ｉに依存することを用いている。また、ａｊ，ｉは、
【０１０１】
【数１５】
【０１０２】
であり、前述のロジスティック回帰を用いることで、
【０１０３】
【数１６】
【０１０４】
と求めることができる。
【０１０５】
Ｐ（ｗｉ）は、例えば平均ベクトル０、分散共分散行列Σ０の正規分布を仮定し、
【０１０６】
【数１７】
【０１０７】
と求める方法がある。Σ０は適当な値をあらかじめ設定する方法や、学習用データを基に経験ベイズ法を用いて自動的に決定する方法などがある。また、０以外の平均ベクトルを用いても良いし、分布モデルとして指数分布やガンマ分布など、正規分布以外のものを用いても良い。
【０１０８】
このとき、最大事後確率推定或いは最尤推定によって求める（即ち、数１６或いは数１７を最大化する）回帰係数ｗｉＭＡＰ或いはｗｉＭＬは、例えばニュートン−ラフソン法を用いて算出できる。これは、回帰係数ｗｉの最大事後確率推定値ｗｉＭＡＰ或いは最尤推定値ｗｉＭＬを、以下の手順で逐次的に求める手法である。
１．ｗｉの初期値ｗｉ（０）を適当に設定する。例えば、ｗｉ（０）＝０とする。τ←０とする。
２．以下のようにｗｉ（τ＋１）を求める。τは逐次計算の回数である。
【０１０９】
【数１８】
【０１１０】
但し、Ｅ（ｗｉ（τ））は事後確率、或いは尤度の負の対数をとったものである。∇は微分演算子ベクトルである。これを誤差関数と呼ぶ。最大事後確率推定の場合は、
【０１１１】
【数１９】
【０１１２】
であり、最尤推定の場合は、
【０１１３】
【数２０】
【０１１４】
である。また、∇Ｅ（ｗｉ（τ））、∇∇Ｅ（ｗｉ（τ））はそれぞれＥ（ｗｉ（τ））の１階微分の列ベクトル、２階微分の行列である。例えば、最大事後確率推定の場合において、数１４、数１６、数１７を用いた場合、
【０１１５】
【数２１】
【０１１６】
【数２２】
【０１１７】
のように求めることができる。但し、
【０１１８】
【数２３】
【０１１９】
【数２４】
【０１２０】
である。
３．ｗｉ（τ＋１）と（ｗｉ（τ））との差が十分小さい、或いはτがある一定値を超えたらｗｉ（τ＋１）をｗｉＭＡＰ或いはｗｉＭＬとして終了する。そうでなければ、τ←τ＋１として、２．に戻る。
【０１２１】
次に、索引用ベクトルサイズＺｉの学習方法を述べる。これは、索引用ベクトルサイズＺｉを様々な値（例えば、１からＭまでの値）に変えて上記の操作を行い、その中で誤差関数がなるべく小さくなるｗｉＭＡＰ或いはｗｉＭＬとそれを実現したＺｉを、学習結果とすれば良い。このようにすれば、精度の観点で最も優れたパラメータを求めることが可能となる。
【０１２２】
或いは、インデックスのサイズがある一定値以下となるうち、誤差関数のｎｏｎ−ｐｉｖｏｔに対する総和がなるべく小さくなるように、ｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習するようにしても良い。これは、インデックスのサイズがある一定値以下となる範囲内で、各ｎｏｎ−ｐｉｖｏｔのＺｉを様々な値に変えてみて、誤差関数のｎｏｎ−ｐｉｖｏｔに対する総和が最も大きくなるときのｗｉＭＡＰとそれを実現したＺｉを学習結果とすれば良い（Ｍ＋１≦ｉ≦Ｎ）。このようにすることで、補助情報のサイズに要求値を設けたとき、それを満たす範囲内で精度の観点で最も優れた性能を実現することが可能となる。
【０１２３】
また、本実施例では、ラベルＬｊｉ（１≦ｊ≦Ｎ’，Ｍ＋１≦ｉ≦Ｎ）を求めるために計（Ｎ−Ｍ）×Ｎ’個のスコアを計算する必要があり、一般にはこれに大きな時間がかかる。そこで、ｎｏｎ−ｐｉｖｏｔ毎に、各学習用データ（Ｎ’個）とのΔスコアを求め、その小さい順にν’（＜Ｎ’）個の学習用データを選択し（ν’は、あらかじめシステム管理者などが定めた値）、それらを学習に用いるようにしても良い。Δスコアが小さい学習用データはｎｏｎ−ｐｉｖｏｔと類似している可能性が高いため、このようにすることでラベルＬｊｉの数が１をとる（即ち、ｎｏｎ−ｐｉｖｏｔＸｉと類似している）学習用データＱｊがなるべく減らないようにしつつ、学習に必要なスコアの計算回数を計（Ｎ−Ｍ）×ν’個まで減らすことが可能となる。その結果、学習が高速に行えるようになる、という効果が得られる。
【０１２４】
また、例えば図６のように登録用データが特徴量空間上で幾つかのクラスタを形成している場合、索引用ベクトルサイズなどのパラメータは各クラスタで似た、或いは同じ値をとる可能性がある。
【０１２５】
従って、本実施例では、ｎｏｎ−ｐｉｖｏｔに対してクラスタリングを行い、得られたクラスタ毎にパラメータの一部或いは全部が共通となるように、ｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習するようにしても良い。クラスタリングの手法としては、最短距離法、最長距離法、群平均法、ウォード法などの階層的手法を用いても良いし、Ｋ平均法などの非階層的手法を用いても良い。このようにクラスタ毎に共通のパラメータを学習することで、パラメータのサイズを減らすことが可能となる。その結果、システムのさらなる軽量化が実現できるという効果が得られる。
【０１２６】
また、本実施例において登録用データを学習用データとして用いる場合、登録用データが追加されたとき、学習用データの索引用ベクトルサイズが小さいためにパラメータの学習がうまく行えなくなる可能性がある。しかしながら、上記のようにクラスタ毎に共通のパラメータを学習すれば、登録用データが追加されたときにおいても、当該登録用データが属するクラスタに共通のパラメータを用いることで、容易にパラメータの学習を行うことが可能となる。
【実施例２】
【０１２７】
以下、図面を参照して、２つ目の実施形態について説明する。本実施形態の類似検索システムは、認証を試みるユーザ（以後、認証ユーザ）が生体情報を入力し、システムがクライアント端末内のデータベースから類似する生体情報を検索することで、認証ユーザがデータベースに登録されているユーザ（以後、登録ユーザ）のうち誰か（或いは誰でもないか）を識別し、その結果に基づいて認証を行なう生体識別システムである。
【０１２８】
図７に本実施形態の生体識別システムの構成例を示す。ここでは、図１と異なる点について述べる。本実施形態では、生データは生体情報である。
【０１２９】
このシステムは、ユーザから取得した生体情報の特徴量をサーバ端末へ送信する登録端末１００と、登録情報を保存し、登録情報から補助情報を生成し、登録情報と補助情報を用いて認証用の特徴量に対する生体識別を行なうサーバ端末２００と、グループＩＤとユーザが入力した認証用の特徴量をサーバ端末２００に送信するクライアント端末３００と、ネットワーク４００から構成される。
【０１３０】
例えば、企業内の情報アクセス制御システム、或いは勤怠管理システムであれば、登録端末１００は企業内の複数のＰＣ、サーバ端末２００は企業が運用するデータセンタ内の１台のサーバ、クライアント端末３００は複数の従業員のＰＣ、ネットワーク４００はインターネットとする構成にする方法が考えられる。また、企業内の入退室管理システムであれば、登録端末１００とサーバ端末２００とクライアント端末３００を同一の入退室管理装置とする構成にする方法が考えられる。グループＩＤ２２１は、ユーザの所属する事業所に固有の値となるようにしても良いし、クライアント端末３００毎、或いは拠点毎に固有の値となるように設定しても良い。前者の場合、ユーザが認証時にグループＩＤを入力する運用が考えられる。後者の場合、ユーザは認証時にグループＩＤを入力しなくても良い。
【０１３１】
登録端末１００は、グループＩＤとユーザ名を取得するグループＩＤ・ユーザ名取得部１０３と、生データから特徴量を抽出する特徴量抽出部１０４をさらに持つ。
【０１３２】
サーバ端末２００は、特徴量抽出部２０２を持たず、グループ絞込み部２０９ａを持ち、グループＩＤ毎にマスタデータ２２０を持つ。マスタデータ２２０は、グループＩＤ２２１を持つ。登録情報２３０は、生データ２３２を持たず、登録用データ毎にユーザ名２３４を持つ。
【０１３３】
生体情報の特徴量としては、例えば指紋であればマニューシャ、虹彩であれば虹彩コード、声紋であればケプストラムなどが考えられる。また、２つの生体情報同士のスコアとしては、指紋であれば対応するマニューシャの数や割合、虹彩であればハミング距離、声紋であればマハラノビス距離などが考えられる。
【０１３４】
クライアント端末３００は、グループＩＤを取得するグループＩＤ取得部３０３と、生データから特徴量を抽出する特徴量抽出部３０４をさらに持つ。
【０１３５】
本実施形態における登録端末１００、サーバ端末２００、クライアント端末３００のハードウェア構成は図２と同じである。
【０１３６】
図８に、本実施形態における登録処理の処理手順およびデータの流れを示す。図８のステップＳ１０１は、図３のステップＳ１０１と同じである。
【０１３７】
登録端末１００は、ユーザからグループＩＤとユーザ名を取得する（ステップＳ１０１ａ）。
【０１３８】
登録端末１００は、登録用の生データから登録用の特徴量を抽出する（ステップＳ１０２ａ）。
【０１３９】
登録端末１００は、グループＩＤとユーザ名と登録用の特徴量をサーバ端末２００に送信する（ステップＳ１０３ａ）。
【０１４０】
サーバ端末２００は、当該グループＩＤに対応するマスタデータ２２０がデータベース２１０にあれば、登録用データに固有の登録用データＩＤ２３１と、ユーザ名２３４と、登録用の特徴量２３３とから構成される登録情報２３０を、そのマスタデータ２２０に追加する。マスタデータ２２０がなければ、当該グループＩＤ２２１と、登録用データに固有の登録用データＩＤ２３１と、ユーザ名２３４と、登録用の特徴量２３３とから構成される登録情報２３０を新しく作成する（ステップＳ１０４ａ）。
【０１４１】
本実施形態における補助情報生成処理の処理手順およびデータの流れは図４と同じである。但し、グループＩＤ毎に本処理を行う。登録情報２３０の数Ｎと、ｐｉｖｏｔの数ＭはグループＩＤ毎に異なっていても良い。
【０１４２】
図９に、本実施形態における検索処理の処理手順およびデータの流れを示す。図９のステップＳ３０２、Ｓ３０５〜Ｓ３１２、Ｓ３１４は、図３のステップＳ３０２、Ｓ３０５〜Ｓ３１２、Ｓ３１４と同じである。
【０１４３】
サーバ端末２００は、データベース２１０からグループＩＤ毎にマスタデータ２２０を取得する（ステップＳ３０１ａ）。
【０１４４】
クライアント端末３００は、ユーザからグループＩＤを取得する（ステップＳ３０２ａ）。グループＩＤは、クライアント端末３００毎、或いは拠点毎に固有の値になるようにしても良く、この場合はユーザから取得しなくても良い。
【０１４５】
クライアント端末３００は、検索用の生データから検索用の特徴量を抽出する（ステップＳ３０３ａ）。
【０１４６】
クライアント端末３００は、グループＩＤと検索用の特徴量をサーバ端末２００に送信する（ステップＳ３０４ａ）。
【０１４７】
サーバ端末２００は、取得したグループＩＤに対応するマスタデータを検索対象とする。以後のステップでは検索対象としたマスタデータについて行う（ステップＳ３０５ａ）。
【０１４８】
このように、本実施例ではグループＩＤを用いた登録用データの絞込みを行う。これによって、スコアを計算する登録用データの数を大幅に減らすことが可能となる。その結果、速度が一層向上するという効果が得られる。
【０１４９】
サーバ端末２００は、クライアント端末３００に検索結果の登録用データに対応するユーザ名２３４を送信する（ステップＳ３１３ａ）。
【０１５０】
クライアント端末３００は、検索結果の登録用データに対応するユーザ名２３４を表示する（ステップＳ３１４ａ）。
【産業上の利用可能性】
【０１５１】
本発明は、画像、動画、音楽、文書、バイナリデータ、生体情報などの非構造化データの類似検索を行なう任意のアプリケーションに対して適用可能である。例えば、類似画像検索システム、類似動画検索システム、類似音楽検索システム、類似文書検索システム、ファジーハッシュを用いた類似ファイル検索システム、情報アクセス制御システム、勤怠管理システム、入退室管理システムなどへの適用が可能である。
【符号の説明】
【０１５２】
１００ 登録端末
１０１ 生データ取得部
１０２ 通信Ｉ／Ｆ
１０３ グループＩＤ・ユーザ名取得部
１０４ 特徴量抽出部
２００ サーバ端末
２０１ ｐｉｖｏｔ決定部
２０２ 特徴量抽出部
２０３ スコア計算部
２０４ 索引用ベクトル生成部
２０５ Δスコア計算部
２０６ ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部
２０７ ｎｏｎ−ｐｉｖｏｔ選択順序決定部
２０８ 検索結果出力部
２０９ 通信Ｉ／Ｆ
２０９ａ グループ絞込み部
２１０ データベース
２２０ マスタデータ
２２１ グループＩＤ
２３０ 登録情報
２３１ 登録用データＩＤ
２３２ 生データ
２３３ 特徴量
２３４ ユーザ名
２４０ 補助情報
２４１ ｐｉｖｏｔ情報
２４２ インデックス
２５０ ｎｏｎ−ｐｉｖｏｔ毎のパラメータ
２５１ 索引用ベクトルサイズ
２５２ 回帰係数
３００ クライアント端末
３０１ 生データ取得部
３０２ 通信Ｉ／Ｆ
３０３ グループＩＤ取得部
３０４ 特徴量抽出部
４００ ネットワーク
５００ ＣＰＵ
５０１ メモリ
５０２ ＨＤＤ
５０３ 入力装置
５０４ 出力装置
５０５ 通信装置
【特許請求の範囲】
【請求項１】
登録用データからｐｉｖｏｔを決定するｐｉｖｏｔ決定部と、
生データを取得する生データ取得部と、
前記生データから特徴量を抽出する特徴量抽出部と、
前記特徴量同士の距離或いは類似度としてスコアを計算するスコア計算部と、
前記ｐｉｖｏｔに対する前記スコアを用いて索引用ベクトルを生成する索引用ベクトル生成部と、
前記索引用ベクトル同士の距離或いは類似度としてΔスコアを計算するΔスコア計算部と、
学習用データを用いて、回帰係数を含むｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習するｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部と、
検索用データと前記ｎｏｎ−ｐｉｖｏｔとの前記Δスコアと前記回帰係数を用いて、ロジスティック回帰により事後確率の大きい順に前記ｎｏｎ−ｐｉｖｏｔの選択順序を決定するｎｏｎ−ｐｉｖｏｔ選択順序決定部と、
前記検索用データと前記登録用データとの前記スコアを基に、検索結果を出力する検索結果出力部と、
前記登録用データの前記特徴量と、前記登録用データのうちどれが前記ｐｉｖｏｔであるかが記されたｐｉｖｏｔ情報と、前記ｎｏｎ−ｐｉｖｏｔ毎の前記索引用ベクトルから構成されるインデックスと、前記ｎｏｎ−ｐｉｖｏｔ毎のパラメータを保持するデータベースを持つ
ことを特徴とする類似検索システム。
【請求項２】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
索引用ベクトルサイズを含むｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習する
ことを特徴とする請求項１に記載の類似検索システム。
【請求項３】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
誤差関数がなるべく小さくなるように、前記索引用ベクトルサイズを含むｎｏｎ−ｐｉｖｏｔ毎の前記パラメータを学習する
ことを特徴とする請求項２に記載の類似検索システム。
【請求項４】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
前記インデックスのサイズがある一定値以下となるうち、誤差関数の前記ｎｏｎ−ｐｉｖｏｔに対する総和がなるべく小さくなるように、前記索引用ベクトルサイズを含むｎｏｎ−ｐｉｖｏｔ毎の前記パラメータを学習する
ことを特徴とする請求項２に記載の類似検索システム。
【請求項５】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
最大事後確率推定により前記ｎｏｎ−ｐｉｖｏｔ毎の前記パラメータを学習する
ことを特徴とする請求項１ないし４に記載の類似検索システム。
【請求項６】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
最尤推定により前記ｎｏｎ−ｐｉｖｏｔ毎の前記パラメータを学習する
ことを特徴とする請求項１ないし５に記載の類似検索システム。
【請求項７】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
前記ｎｏｎ−ｐｉｖｏｔ毎に、前記学習用データとのΔスコアを計算し、前記Δスコアを用いて学習に用いる前記学習用データを選択する
ことを特徴とする請求項１ないし６に記載の類似検索システム。
【請求項８】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
前記学習用データとして前記登録用データを用いる
ことを特徴とする請求項１ないし７に記載の類似検索システム。
【請求項９】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
前記学習用データとして前記登録用データとは別にあらかじめ用意しておいたデータを用いる
ことを特徴とする請求項１ないし７に記載の類似検索システム。
【請求項１０】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
前記ｎｏｎ−ｐｉｖｏｔに対してクラスタリングを行い、得られたクラスタ毎に前記パラメータの一部或いは全部が共通となるように、前記ｎｏｎ−ｐｉｖｏｔ毎の前記パラメータを学習する
ことを特徴とする請求項１ないし９に記載の類似検索システム。
【請求項１１】
前記索引用ベクトル生成部は、
前記索引用ベクトルとして順列ベクトルを生成する
ことを特徴とする請求項１ないし１０に記載の類似検索システム。
【請求項１２】
前記索引用ベクトル生成部は、
前記索引用ベクトルとしてスコアベクトルを生成する
ことを特徴とする請求項１ないし１０に記載の類似検索システム。
【請求項１３】
グループＩＤを用いて前記登録用データの絞込みを行うグループ絞込み部を持ち、
前記データベースは、
前記グループＩＤを保持する
ことを特徴とする請求項１ないし１２に記載の類似検索システム。
【請求項１４】
登録端末によって、クライアント端末から送信された生データに対して類似検索を行うサーバ端末における高精度な類似検索方法において、
前記生データから抽出した特徴量で構成される登録用データを生成し、
前記登録用データからｐｉｖｏｔを選択し、
前記特徴量同士の距離或いは類似度として定義したスコアを計算し、
前記ｐｉｖｏｔに対する前記スコアを用いて索引用ベクトルを生成し、
前記索引用ベクトル同士の距離或いは類似度として定義したΔスコアを計算し、
予め用意された学習用データを用いて、前記登録用データから前記ｐｉｖｏｔとして選択されなかったｎｏｎ−ｐｉｖｏｔ毎の回帰係数を含むパラメータを学習し、
入力された検索用データと前記ｎｏｎ−ｐｉｖｏｔとの前記Δスコアと前記回帰係数を用いて、ロジスティック回帰により事後確率の大きい順に前記ｎｏｎ−ｐｉｖｏｔの選択順序を決定し、
前記検索用データと前記登録用データとの前記スコアを基に、検索結果を出力し、
前記登録用データの前記特徴量と、前記登録用データのうちどれが前記ｐｉｖｏｔであるかが記されたｐｉｖｏｔ情報と、前記ｎｏｎ−ｐｉｖｏｔ毎の前記索引用ベクトルから構成されるインデックスと、前記ｎｏｎ−ｐｉｖｏｔ毎のパラメータをデータベースに保持することを特徴とする高精度な類似検索方法。
【請求項１５】
前記選択順序の決定の際に、前記学習用データを用いて、前記回帰係数を含むｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習し、前記検索用データと前記ｎｏｎ−ｐｉｖｏｔとの前記Δスコアと前記回帰係数を用いて、ロジスティック回帰により事後確率の大きい順に前記ｎｏｎ−ｐｉｖｏｔの選択順序を決定することを特徴とする請求項１４に記載の高精度な類似検索方法。
【請求項１】
登録用データからｐｉｖｏｔを決定するｐｉｖｏｔ決定部と、
生データを取得する生データ取得部と、
前記生データから特徴量を抽出する特徴量抽出部と、
前記特徴量同士の距離或いは類似度としてスコアを計算するスコア計算部と、
前記ｐｉｖｏｔに対する前記スコアを用いて索引用ベクトルを生成する索引用ベクトル生成部と、
前記索引用ベクトル同士の距離或いは類似度としてΔスコアを計算するΔスコア計算部と、
学習用データを用いて、回帰係数を含むｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習するｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部と、
検索用データと前記ｎｏｎ−ｐｉｖｏｔとの前記Δスコアと前記回帰係数を用いて、ロジスティック回帰により事後確率の大きい順に前記ｎｏｎ−ｐｉｖｏｔの選択順序を決定するｎｏｎ−ｐｉｖｏｔ選択順序決定部と、
前記検索用データと前記登録用データとの前記スコアを基に、検索結果を出力する検索結果出力部と、
前記登録用データの前記特徴量と、前記登録用データのうちどれが前記ｐｉｖｏｔであるかが記されたｐｉｖｏｔ情報と、前記ｎｏｎ−ｐｉｖｏｔ毎の前記索引用ベクトルから構成されるインデックスと、前記ｎｏｎ−ｐｉｖｏｔ毎のパラメータを保持するデータベースを持つ
ことを特徴とする類似検索システム。
【請求項２】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
索引用ベクトルサイズを含むｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習する
ことを特徴とする請求項１に記載の類似検索システム。
【請求項３】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
誤差関数がなるべく小さくなるように、前記索引用ベクトルサイズを含むｎｏｎ−ｐｉｖｏｔ毎の前記パラメータを学習する
ことを特徴とする請求項２に記載の類似検索システム。
【請求項４】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
前記インデックスのサイズがある一定値以下となるうち、誤差関数の前記ｎｏｎ−ｐｉｖｏｔに対する総和がなるべく小さくなるように、前記索引用ベクトルサイズを含むｎｏｎ−ｐｉｖｏｔ毎の前記パラメータを学習する
ことを特徴とする請求項２に記載の類似検索システム。
【請求項５】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
最大事後確率推定により前記ｎｏｎ−ｐｉｖｏｔ毎の前記パラメータを学習する
ことを特徴とする請求項１ないし４に記載の類似検索システム。
【請求項６】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
最尤推定により前記ｎｏｎ−ｐｉｖｏｔ毎の前記パラメータを学習する
ことを特徴とする請求項１ないし５に記載の類似検索システム。
【請求項７】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
前記ｎｏｎ−ｐｉｖｏｔ毎に、前記学習用データとのΔスコアを計算し、前記Δスコアを用いて学習に用いる前記学習用データを選択する
ことを特徴とする請求項１ないし６に記載の類似検索システム。
【請求項８】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
前記学習用データとして前記登録用データを用いる
ことを特徴とする請求項１ないし７に記載の類似検索システム。
【請求項９】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
前記学習用データとして前記登録用データとは別にあらかじめ用意しておいたデータを用いる
ことを特徴とする請求項１ないし７に記載の類似検索システム。
【請求項１０】
前記ｎｏｎ−ｐｉｖｏｔ毎パラメータ学習部は、
前記ｎｏｎ−ｐｉｖｏｔに対してクラスタリングを行い、得られたクラスタ毎に前記パラメータの一部或いは全部が共通となるように、前記ｎｏｎ−ｐｉｖｏｔ毎の前記パラメータを学習する
ことを特徴とする請求項１ないし９に記載の類似検索システム。
【請求項１１】
前記索引用ベクトル生成部は、
前記索引用ベクトルとして順列ベクトルを生成する
ことを特徴とする請求項１ないし１０に記載の類似検索システム。
【請求項１２】
前記索引用ベクトル生成部は、
前記索引用ベクトルとしてスコアベクトルを生成する
ことを特徴とする請求項１ないし１０に記載の類似検索システム。
【請求項１３】
グループＩＤを用いて前記登録用データの絞込みを行うグループ絞込み部を持ち、
前記データベースは、
前記グループＩＤを保持する
ことを特徴とする請求項１ないし１２に記載の類似検索システム。
【請求項１４】
登録端末によって、クライアント端末から送信された生データに対して類似検索を行うサーバ端末における高精度な類似検索方法において、
前記生データから抽出した特徴量で構成される登録用データを生成し、
前記登録用データからｐｉｖｏｔを選択し、
前記特徴量同士の距離或いは類似度として定義したスコアを計算し、
前記ｐｉｖｏｔに対する前記スコアを用いて索引用ベクトルを生成し、
前記索引用ベクトル同士の距離或いは類似度として定義したΔスコアを計算し、
予め用意された学習用データを用いて、前記登録用データから前記ｐｉｖｏｔとして選択されなかったｎｏｎ−ｐｉｖｏｔ毎の回帰係数を含むパラメータを学習し、
入力された検索用データと前記ｎｏｎ−ｐｉｖｏｔとの前記Δスコアと前記回帰係数を用いて、ロジスティック回帰により事後確率の大きい順に前記ｎｏｎ−ｐｉｖｏｔの選択順序を決定し、
前記検索用データと前記登録用データとの前記スコアを基に、検索結果を出力し、
前記登録用データの前記特徴量と、前記登録用データのうちどれが前記ｐｉｖｏｔであるかが記されたｐｉｖｏｔ情報と、前記ｎｏｎ−ｐｉｖｏｔ毎の前記索引用ベクトルから構成されるインデックスと、前記ｎｏｎ−ｐｉｖｏｔ毎のパラメータをデータベースに保持することを特徴とする高精度な類似検索方法。
【請求項１５】
前記選択順序の決定の際に、前記学習用データを用いて、前記回帰係数を含むｎｏｎ−ｐｉｖｏｔ毎のパラメータを学習し、前記検索用データと前記ｎｏｎ−ｐｉｖｏｔとの前記Δスコアと前記回帰係数を用いて、ロジスティック回帰により事後確率の大きい順に前記ｎｏｎ−ｐｉｖｏｔの選択順序を決定することを特徴とする請求項１４に記載の高精度な類似検索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１２−１７８０９５（Ｐ２０１２−１７８０９５Ａ）
【公開日】平成２４年９月１３日（２０１２．９．１３）
【国際特許分類】
【出願番号】特願２０１１−４１２６８（Ｐ２０１１−４１２６８）
【出願日】平成２３年２月２８日（２０１１．２．２８）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｂｌｕｅｔｏｏｔｈ
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２４年９月１３日（２０１２．９．１３）
【国際特許分類】
【出願日】平成２３年２月２８日（２０１１．２．２８）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｂｌｕｅｔｏｏｔｈ
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]