(57)【要約】【課題】より正確な検索対象リランキングができる。【解決手段】検索部２４が、入力されたクエリを用いた検索によって検索対象にランクを付与し、検索対象の中から上位結果を複数取得する。加重値計算部２６が、上位結果の各々に対して加重値を設定する。上位結果検索対象間類似度計算部２８が、上位結果の各々と全検索対象の各々との間の類似度を各々計算する。リランキング部３０が、各検索対象について、上位結果との類似度が高ければ高いほど前記上位結果の加重値と前記検索対象のランクスコアとの差分が小さくなることを表す目的関数を最適化するように、各検索対象のランクスコアを計算する。【選択図】図１
2018041281.tif 000002
【特許請求の範囲】
【請求項１】
入力されたクエリを用いた検索によって検索対象にランクを付与し、前記検索対象の中から上位結果を複数取得する検索部と、
前記検索部によって取得された前記上位結果の各々に対して加重値を設定する加重値計算部と、
前記上位結果の各々と全検索対象の各々との間の類似度を各々計算する上位結果検索対象間類似度計算部と、
前記上位結果検索対象間類似度計算部によって計算された前記類似度に基づいて、各検索対象について、上位結果との類似度が高ければ高いほど前記上位結果の加重値と前記検索対象のランクスコアとの差分が小さくなることを表す目的関数を最適化するよう    に、各検索対象のランクスコアを計算するリランキング部と、
を含む検索装置。
【請求項２】
前記検索部は、前記上位結果を複数取得すると共に、前記クエリと前記上位結果の各々との間の類似度を取得し、
前記加重値計算部は、前記クエリと前記上位結果の各々との間の類似度を、前記上位結果の各々に対する加重値として設定する請求項１記載の検索装置。
【請求項３】
前記検索部は、前記上位結果を複数取得すると共に、前記クエリと前記上位結果の各々との間の類似度を取得し、
前記加重値計算部は、前記上位結果間の類似度を各々計算し、前記上位結果間の類似度の各々に基づいて、二つの上位結果間の類似度が高ければ高いほど前記二つの上位結果の加重値の差分が小さくなることを表す目的関数を最適化するように、前記上位結果の各々の加重値を計算する請求項１記載の検索装置。
【請求項４】
前記加重値計算部は、正規化された前記上位結果間の類似度の各々と、前記クエリと前記上位結果の各々との間の類似度とに基づいて、前記目的関数を最適化するように前記上位結果の各々の加重値を更新することを繰り返すことにより、前記上位結果の各々の加重値を計算する請求項３記載の検索装置。
【請求項５】
検索部が、入力されたクエリを用いた検索によって検索対象にランクを付与し、前記検索対象の中から上位結果を複数取得し、
加重値計算部が、前記検索部によって取得された前記上位結果の各々に対して加重値を設定し、
上位結果検索対象間類似度計算部が、前記上位結果の各々と全検索対象の各々との間の類似度を各々計算し、
リランキング部が、前記上位結果検索対象間類似度計算部によって計算された前記類似度に基づいて、各検索対象について、上位結果との類似度が高ければ高いほど前記上位結果の加重値と前記検索対象のランクスコアとの差分が小さくなることを表す目的関数を最適化するように、各検索対象のランクスコアを計算する
検索方法。
【請求項６】
前記検索部によって取得することでは、前記上位結果を複数取得すると共に、前記クエリと前記上位結果の各々との間の類似度を取得し、
前記加重値計算部によって設定することでは、前記クエリと前記上位結果の各々との間の類似度を、前記上位結果の各々に対する加重値として設定する請求項５記載の検索方法。
【請求項７】
前記検索部によって取得することでは、前記上位結果を複数取得すると共に、前記クエリと前記上位結果の各々との間の類似度を取得し、
前記加重値計算部によって設定することでは、前記上位結果間の類似度を各々計算し、前記上位結果間の類似度の各々に基づいて、二つの上位結果間の類似度が高ければ高いほど前記二つの上位結果の加重値の差分が小さくなることを表す目的関数を最適化するように、前記上位結果の各々の加重値を計算する請求項５記載の検索方法。
【請求項８】
コンピュータを、請求項１〜請求項４の何れか１項記載の検索装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置、方法、及びプログラムに係り、特に、クエリを用いた検索による各検索対象のランクを付与する検索装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
検索とは、検索の利用者がクエリを入力し、検索アルゴリズムがクエリとの類似性の高いデータをデータベースに格納されている検索対象のデータから選択し、選択された検索対象のデータを利用者に返答することである。以下、検索対象のデータを検索対象と記す。検索対象は、例えば、文書や画像、音声、映像、その他様々なメディアやその組み合わせとして記録されたデータ等がある。適切な検索結果は、データを検索する条件によって複数存在することがある。検索の利用者が検索対象の中から適切な検索結果を判断しやすくするために、検索アルゴリズムによって計算された検索対象とクエリとの類似性の測度の高い順に検索対象を並べ替え、検索対象に優先順位をつける必要がある。以下、類似性の測度を類似度と記し、優先順位をランクと記す。
【０００３】
しかし、クエリから得られる情報量が少ない場合、適切な検索結果とクエリとの類似度が低く、適切な検索結果に低いランクが与えられる可能性が高い。前記問題に対処するために、１回目の検索によってランクを与えられた検索対象に対して、新たなランクを付与するための検索対象リランキング方法が各種提案されている。
【０００４】
例えば、非特許文献１記載の検索対象リランキング装置は、入力となる第１のクエリを用いて１回目の検索をし、検索対象に第１のランクを付与した後に、検索対象の中から第１のランクが最高な検索対象を複数割り出す。以下、前記第１のランクが最高な検索対象を上位結果と記す。次に、各検索対象を第２のクエリとして用いて２回目の検索をし、全検索対象に第２のランクをつける。次に、前記各検索対象について、上位結果の第２のランクに基づいて、新たなランクスコアを計算する。最後に、新たなランクスコアの高い順に前記各検索対象を並べ替え、前記各検索対象に第３のランクをつける。
【０００５】
また、非特許文献２記載の検索対象リランキング装置は、非特許文献１記載の検索対象リランキング装置と同様に検索対象の中から上位結果を割り出す。次に、入力となる第１のクエリをデータベースに追加し、各上位結果を第２のクエリとして用いて２回目の検索をし、第１のクエリと全検索対象に第２のランクをつける。次に、各検索対象について、上位結果の第１のランクと第１のクエリの第２のランク、前記各検索対象の第２のランクに基づいて、新たなランクスコアを計算する。最後に、新たなランクスコアの高い順に前記各検索対象を並べ替え、前記各検索対象に第３のランクをつける。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Danfeng Qin, Stephan Gammeter, Lukas Bossard, Till Quack, Luc J. Van Gool: Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors. CVPR 2011: 777-784.
【非特許文献２】Xiaohui Shen, Zhe Lin, Jonathan Brandt, Ying Wu: Spatially-Constrained Similarity Measurefor Large-Scale Object Retrieval. IEEE Trans. Pattern Anal. Mach. Intell. 36(6): 1229-1241 (2014).
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１、２記載の検索対象リランキング装置は、ランクに基づいて検索対象の新たなランクスコアを計算する。しかし、ランクは、データを並べ替えた優先順位に過ぎず、データ間の類似性と相関しない場合が存在する。例えば、類似性の低い二つのデータについて、片方のデータをクエリとして用いて検索をした場合、もう片方のデータに高いランクが与えられる場合が存在する。こうしたデータ間の類似性と相関しないランクに基づいて検索対象の新たなランクスコアを計算する場合、計算されたランクスコアに誤差が生じやすく、検索対象リランキングの精度に悪影響を与える場合が存在する。
【０００８】
また、非特許文献１記載の検索対象リランキング装置は、全上位結果の検索対象リランキングに対する貢献度を一様に扱う。しかし、上位結果に無関係な検索対象が偽陽性の上位結果として含まれる場合が多く存在する。この場合、偽陽性の上位結果との類似性が高い他の無関係な検索対象について、新たなランクスコアが高く計算される可能性が高く、検索対象リランキングの精度に悪影響を与える場合が存在する。
【０００９】
非特許文献２記載の検索対象リランキング装置は、上位結果の第１のランクに反比例する加重値を前記上位結果に付与することによって、前記偽陽性の上位結果の貢献度を抑える。しかし、第１のランクの正確性は１回目の検索の精度に強く依存し、１回目の検索の精度が低い場合、偽陽性の上位結果について、第１のランクが高く、高い加重値が付与される場合が存在する。こうした第１のランクの高い偽陽性の上位結果は依然として貢献度が高く、検索対象リランキングの精度に悪影響を与える場合が存在する。
【００１０】
本発明は、上記課題を解決するために成されたものであり、より正確な検索対象リランキングができる検索装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、本発明に係る検索装置は、入力されたクエリを用いた検索によって検索対象にランクを付与し、前記検索対象の中から上位結果を複数取得する検索部と、前記検索部によって取得された前記上位結果の各々に対して加重値を設定する加重値計算部と、前記上位結果の各々と全検索対象の各々との間の類似度を各々計算する上位結果検索対象間類似度計算部と、前記上位結果検索対象間類似度計算部によって計算された前記類似度に基づいて、各検索対象について、上位結果との類似度が高ければ高いほど前記上位結果の加重値と前記検索対象のランクスコアとの差分が小さくなることを表す目的関数を最適化するように、各検索対象のランクスコアを計算するリランキング部と、を含んで構成されている。
【００１２】
本発明に係る検索方法は、検索部が、入力されたクエリを用いた検索によって検索対象にランクを付与し、前記検索対象の中から上位結果を複数取得し、加重値計算部が、前記検索部によって取得された前記上位結果の各々に対して加重値を設定し、上位結果検索対象間類似度計算部が、前記上位結果の各々と全検索対象の各々との間の類似度を各々計算し、リランキング部が、前記上位結果検索対象間類似度計算部によって計算された前記類似度に基づいて、各検索対象について、上位結果との類似度が高ければ高いほど前記上位結果の加重値と前記検索対象のランクスコアとの差分が小さくなることを表す目的関数を最適化するように、各検索対象のランクスコアを計算する。
【００１３】
本発明に係るプログラムは、コンピュータを、上記の検索装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１４】
本発明の検索装置、方法、及びプログラムによれば、上位結果の各々と全検索対象の各々との間の類似度に基づいて、各検索対象について、上位結果との類似度が高ければ高いほど前記上位結果の加重値と前記検索対象のランクスコアとの差分が小さくなることを表す目的関数を最適化するように、各検索対象のランクスコアを計算し、検索対象にランクを付与することにより、より正確な検索対象リランキングができる、という効果が得られる。
【図面の簡単な説明】
【００１５】
【図１】本発明の第１の実施の形態に係る検索装置の構成を示すブロック図である。
【図２】本発明の第１の実施の形態に係る検索装置のリランキング部の構成を示すブロック図である。
【図３】本発明の第１の実施の形態に係る検索装置における検索処理ルーチンを示すフローチャートである。
【図４】本発明の第３の実施の形態に係る検索装置の加重値計算部の構成を示すブロック図である。
【図５】本発明の第３の実施の形態に係る検索装置における加重値を計算する処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１７】
＜第１の実施の形態に係る検索装置の構成＞
次に、本発明の第１の実施の形態に係る検索装置の構成について説明する。図１に示すように、本発明の第１の実施の形態に係る検索装置１００は、ＣＰＵと、ＲＡＭと、後述する検索処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この検索装置１００は、機能的には図１に示すように、入力部１０、演算部２０と、出力部５０とを備えている。
【００１８】
入力部１０は、クエリの入力を受け付ける。
【００１９】
演算部２０は、検索対象を蓄積・管理しているデータベース２２に対してクエリを用いた検索を行って上位結果を複数取得する検索部２４と、上位結果の各々の加重値を計算する加重値計算部２６と、上位結果の各々と全検索対象の各々との間の類似度を計算する上位結果検索対象間類似度計算部２８と、検索対象のランクスコアを計算してランクを付与するリランキング部３０とを含んで構成されている。
【００２０】
検索部２４は、クエリとデータベース２２を入力とし、クエリと全検索対象との類似度を計算し、類似度に応じて検索対象にランクを付与し、複数の上位結果と、複数の上位結果の各々とクエリとの類似度を記録した第１の類似度行列とを出力する。類似度の計算方法は、例えば、検索対象が文書の場合は、ベクトル空間モデル等が挙げられる。検索対象が画像の場合は、bag-of-visual-words法や非特許文献３のような空間検証法等が挙げられる。
【００２１】
[非特許文献３]：Xiaomeng Wu, Kunio Kashino: Robust Spatial Matching as Ensemble of Weak Geometric Relations. BMVC 2015: 25.1-25.12
【００２２】
加重値計算部２６は、検索部２４によって出力された上位結果を入力とし、上位結果の各々の加重値を設定し、加重値を記録した加重値行列を出力する。本実施の形態では、全上位結果の加重値を１に設定する。
【００２３】
上位結果検索対象間類似度計算部２８は、複数の上位結果とデータベース２２を入力とし、複数の上位結果の各々と全検索対象の各々との間の類似度を各々計算し、類似度の各々を記録した第２の類似度行列を出力する。類似度の計算方法は、検索部２４が用いた方法と同様の方法でも良く、前記方法と異なる方法でも良い。
【００２４】
リランキング部３０は、図２に示すように、検索対象のランクスコアを最適化するための目的関数を作成する第１の目的関数作成部３２と、目的関数を最適化するランクスコアを計算する第１の目的関数最小化部３４とを含んで構成されている。リランキング部３０は、上位結果検索対象間類似度計算部２８によって出力された第２の類似度行列と加重値計算部２６によって出力された加重値行列を入力とし、検索対象のランクスコアを記録したランクスコア行列を出力する。
【００２５】
第１の目的関数作成部３２は、第２の類似度行列と加重値行列を入力とし、各検索対象について、上位結果との類似度が高ければ高いほど当該上位結果の加重値と当該検索対象のランクスコアとの差分が小さくなることを表す目的関数を作成し、出力する。
【００２６】
本実施形態では、以下のように目的関数を作成する。ここで、上位結果の数をｍと記し、ｊ番目の上位結果の加重値をｓjと記し、全上位結果の加重値行列を
【００２７】
【数１】
2018041281.tif 000003
【００２８】
と記す。また、検索対象の数をｎと記し、ｉ番目の検索対象のランクスコアをｒiと記し、全検索対象のランクスコア行列を
【００２９】
【数２】
2018041281.tif 000004
【００３０】
と記す。また、ｉ番目の検索対象とｊ番目の上位結果との類似度をｕijと記し、前記第２の類似度行列を
2018041281.tif 000005
と記す。
【００３１】
次に、
2018041281.tif 000006
の入次数行列を
【００３２】
【数３】
2018041281.tif 000007
に定義し、
2018041281.tif 000008
に定義する。同様に、
2018041281.tif 000009
の出次数行列を
【００３３】
【数４】
2018041281.tif 000010
に定義し、
2018041281.tif 000011
に定義する。次に、
2018041281.tif 000012
を
【００３４】
【数５】
2018041281.tif 000013
に正規化する。次に、ｉ番目の検索対象のランクスコアｒiの費用関数を
【００３５】
【数６】
2018041281.tif 000014
【００３６】
に定義する。最後に、全検索対象のランクスコア行列
2018041281.tif 000015
を最適化するための大域的な目的関数を
【００３７】
【数７】
2018041281.tif 000016
に定義する。
【００３８】
第１の目的関数最小化部３４は、上記式（７）に示す目的関数を入力とし、当該目的関数を最小化する時の全検索対象のランクスコアを計算し、ランクスコアを記録したランクスコア行列を出力する。
【００３９】
本実施形態では、式（７）に示す目的関数について、全検索対象のランクスコア行列
2018041281.tif 000017
における式（７）の微分係数が0になる時の
2018041281.tif 000018
を求める。具体的に、以下の式（９）に従って計算する。
【００４０】
【数８】
2018041281.tif 000019
【００４１】
ここで、最適化された
2018041281.tif 000020
を
2018041281.tif 000021
と記す。
【００４２】
出力部５０は、ランクスコアの高い順に検索対象を並べ替え、検索対象にランクを付与して出力する。
【００４３】
＜本発明の第１の実施の形態に係る検索装置の作用＞
次に、本発明の第１の実施の形態に係る検索装置１００の作用について説明する。入力部１０によって、クエリを受け付けると、検索装置１００は、図３に示す検索処理ルーチンを実行する。
【００４４】
まず、ステップＳ１００では、入力されたクエリを用いてデータベース２２に対して検索を行い、上位結果を複数取得し、第１の類似度行列を出力する。
【００４５】
ステップＳ１０２では、上記ステップＳ１００で取得した上位結果の各々と、データベース２２に蓄積されている検索対象の各々との間の類似度を計算し、第２の類似度行列を出力する。
【００４６】
ステップＳ１０４では、上記ステップＳ１００で取得した上位結果の各々に対して加重値を設定し、加重値行列を出力する。
【００４７】
そして、ステップＳ１０６では、上記ステップＳ１０２で出力された第２の類似度行列と上記ステップＳ１０４で出力された加重値行列を入力とし、上記式（７）に示す目的関数を作成する。
【００４８】
ステップＳ１０８では、上記ステップＳ１０６で作成された目的関数を入力とし、上記式（９）に従って、目的関数を最小化する時の全検索対象のランクスコアを計算し、ランクスコアの高い順に検索対象を並べ替え、検索対象にランクを付与して出力し、検索処理ルーチンを終了する。
【００４９】
以上説明したように、本発明の第１の実施の形態に係る検索装置によれば、上位結果の各々と全検索対象の各々との間の類似度に基づいて、各検索対象について、上位結果との類似度が高ければ高いほど当該上位結果の加重値と当該検索対象のランクスコアとの差分が小さくなることを表す目的関数を最適化するように、各検索対象のランクスコアを計算し、１回目の検索によってランクを与えられた検索対象に対して、新たなランクを付与することにより、より正確な検索対象リランキングができる。
【００５０】
また、上位結果の各々と全検索対象の各々との間の類似度に基づいて検索対象のランクスコアを計算することによって、ランクがデータ間の類似性と相関しない場合でも、より正確な検索対象リランキングができる。
【００５１】
＜第２の実施の形態に係る検索装置の構成＞
次に、本発明の第２の実施の形態に係る検索装置の構成について説明する。なお、第２の実施の形態に係る検索装置は、第１の実施の形態と同様であるため、同一符号を付して説明を省略する。
【００５２】
第２の実施の形態では、検索部２４によって出力された第１の類似度行列を用いて、上位結果の加重値行列を設定している点が、第１の実施の形態と異なっている。
【００５３】
上記図１に示すように、第２の実施の形態に係る検索装置１００の加重値計算部２６は、検索部２４によって出力された上位結果、及び第１の類似度行列を入力とし、第１の類似度行列を、上位結果の各々の加重値を記録した加重値行列として設定し、出力する。
【００５４】
なお、第２の実施の形態に係る検索装置の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【００５５】
このように、クエリと上位結果との間の類似度を用いて、上位結果の各々の加重値を設定し、目的関数を最適化するように、検索対象のランクスコアを計算することによって、ランクがデータ間の類似性と相関しない場合でも、より正確な検索対象リランキングができる。
【００５６】
＜第３の実施の形態に係る検索装置の構成＞
次に、本発明の第３の実施の形態に係る検索装置の構成について説明する。なお、第３の実施の形態に係る検索装置は、第１の実施の形態と同様であるため、同一符号を付して説明を省略する。
【００５７】
第３の実施の形態では、目的関数を作成し、目的関数を最適化するように、上位結果の加重値を計算している点が、第２の実施の形態と異なっている。
【００５８】
第３の実施の形態に係る検索装置１００の加重値計算部２６は、図４に示すように、全上位結果間の類似度を計算する上位結果間類似度計算部６０と、上位結果の加重値を最適化するための目的関数を作成する第２の目的関数作成部６２と、加重値を計算する第２の目的関数最小化部６４とを含んで構成されている。加重値計算部２６は、検索部２４によって出力された複数の上位結果と第１の類似度行列を入力とし、上位結果の加重値を記録した加重値行列を出力する。
【００５９】
上位結果間類似度計算部６０は、複数の上位結果を入力とし、全上位結果間の類似度を計算し、類似度を記録した第３の類似度行列を出力する。類似度の計算方法は、検索部２４と上位結果検索対象間類似度計算部２８が用いた方法と同様の方法でも良く、前記方法と異なる方法でも良い。
【００６０】
第２の目的関数作成部６２は、第３の類似度行列と第１の類似度行列を入力とし、二つの上位結果間の類似度が高ければ高いほど前記二つの上位結果の加重値の差分が小さくなることを表す目的関数を作成し、出力する。
【００６１】
本実施の形態では、以下のように目的関数を作成する。ここで、ｊ番目の上位結果とクエリとの類似度をｙjと記し、第１の類似度行列を
【００６２】
【数９】
2018041281.tif 000022
【００６３】
と記す。また、ｉ番目の上位結果とｊ番目の上位結果との類似度をｖijと記し、前記第３の類似度行列を
2018041281.tif 000023
と記す。
【００６４】
次に、
2018041281.tif 000024
の入次数行列を
【００６５】
【数１０】
2018041281.tif 000025
【００６６】
に定義し、
2018041281.tif 000026
に定義する。同様に、
2018041281.tif 000027
の出次数行列を
【００６７】
【数１１】
2018041281.tif 000028
【００６８】
に定義し、
2018041281.tif 000029
に定義する。次に、
2018041281.tif 000030
を
【００６９】
【数１２】
2018041281.tif 000031
【００７０】
に正規化する。次に、ｉ番目の上位結果の加重値ｓiの費用関数を
【００７１】
【数１３】
2018041281.tif 000032
【００７２】
に定義する。最後に、全上位結果の加重値行列
2018041281.tif 000033
を最適化するための大域的な目的関数を
【００７３】
【数１４】
2018041281.tif 000034
【００７４】
に定義する。ここで、μ＞０は外部パラメータであり、
2018041281.tif 000035
はｍ×ｍの単位行列である。
【００７５】
第２の目的関数最小化部６４は、上記式（１５）に示す目的関数を入力とし、当該目的関数を最小化する時の全上位結果の加重値を計算し、加重値を記録した加重値行列を出力する。
【００７６】
本実施の形態では、上記式（１５）の目的関数について、全上位結果の加重値行列
2018041281.tif 000036
における式（１５）の微分係数が0になる時の
2018041281.tif 000037
を求める。具体的には、以下の式（１７）に従って計算する。
【００７７】
【数１５】
2018041281.tif 000038
【００７８】
ここで、
2018041281.tif 000039
である。
【００７９】
最適化された
2018041281.tif 000040
を
2018041281.tif 000041
と記す。
【００８０】
式（１７）を用いて
2018041281.tif 000042
を求めても良いが、本実施の形態では、より効率的な解法として、以下の反復法を用いる。ここで、ｔ番目の反復をした時の
2018041281.tif 000043
を
2018041281.tif 000044
と記し、
2018041281.tif 000045
を
2018041281.tif 000046
に初期化する。次に、
【００８１】
【数１６】
2018041281.tif 000047
【００８２】
により
2018041281.tif 000048
を更新し、外部パラメータＴ番目の反復が終わった時の加重値行列
2018041281.tif 000049
を
2018041281.tif 000050
として出力する。
【００８３】
＜本発明の第３の実施の形態に係る検索装置の作用＞
次に、本発明の第３の実施の形態に係る検索装置１００の作用について説明する。入力部１０によって、クエリを受け付けると、検索装置１００は、上記図３に示す検索処理ルーチンと同様の処理ルーチンを実行する。
【００８４】
このとき、上記ステップＳ１０４は、図５に示す処理ルーチンによって実現される。
【００８５】
ステップＳ３００では、上記ステップＳ１００で取得した複数の上位結果を入力とし、全上位結果間の類似度を計算し、類似度を記録した第３の類似度行列を出力する。
【００８６】
ステップＳ３０２では、上記ステップＳ３００で出力された第３の類似度行列と上記ステップＳ１００で出力された第１の類似度行列を入力とし、上記式（１５）に示す目的関数を作成し、出力する。
【００８７】
そして、ステップＳ３０４では、上記ステップＳ３００で出力された第３の類似度行列を正規化した行列と、上記ステップＳ１００で出力された第１の類似度行列とに基づいて、上記式（１８）に従って、上記式（１５）に示す目的関数を最適化するように上位結果の各々の加重値を更新することを繰り返すことにより、上位結果の各々の加重値を計算し、加重値行列を出力する。
【００８８】
なお、第３の実施の形態に係る検索装置の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【００８９】
このように、上位結果間の類似度を用いて、各上位結果について、他の上位結果との類似度が低ければ低いほどより低い加重値を付与することによって、１回目の検索の精度が低い場合や上位結果に無関係な検索対象が含まれる場合でも、偽陽性の上位結果に、より低い加重値を付与することが可能になり、偽陽性の上位結果の検索対象リランキングに対する貢献度を抑制し、より正確な検索対象リランキングができる。
【００９０】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００９１】
例えば、上述した実施の形態では、データベース２２が、検索装置１００に設けられている場合を例に説明したが、これに限定されるものではなく、データベース２２が、検索装置１００の外部に設けられていてもよい。
【符号の説明】
【００９２】
１０   入力部
２０   演算部
２２   データベース
２４   検索部
２６   加重値計算部
２８   上位結果検索対象間類似度計算部
３０   リランキング部
３２   第１の目的関数作成部
３４   第１の目的関数最小化部
５０   出力部
６０   上位結果間類似度計算部
６２   第２の目的関数作成部
６４   第２の目的関数最小化部
１００ 検索装置
【図１】
2018041281.tif 000051
【図２】
2018041281.tif 000052
【図３】
2018041281.tif 000053
【図４】
2018041281.tif 000054
【図５】
2018041281.tif 000055