(57)【要約】【課題】リランキングの精度を高めて、検索の精度を高めることができるようにする。【解決手段】類似度計算部１３０が、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とするデータ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算し、ランクスコア計算部１４０が、検索対象となる複数のデータの各々について、類似度計算部１３０により求められた類似度に基づいて、当該データが第１クエリに関連する度合いを示すランクスコアを計算する。【選択図】図１
2019125316.tif 000002
【特許請求の範囲】
【請求項１】
入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とするデータ集合に含まれるデータの各々について、前記データを第２クエリとして前記データ集合に対する検索を行った場合における、前記データ集合に含まれるデータの各々の、前記第２クエリに関連する順位であるランクを付与する検索部と、
前記データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する類似度計算部と、
前記検索対象となる複数のデータの各々について、前記類似度計算部により求められた類似度に基づいて、前記データが前記第１クエリに関連する度合いを示すランクスコアを計算するランクスコア計算部と、
を含む検索装置。
【請求項２】
前記類似度計算部は、
前記データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が前記所定のランクよりも低いランクである場合に小さい値を取るように計算する
請求項１記載の検索装置。
【請求項３】
入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とする第１データ集合に含まれるデータの各々について、前記データを第２クエリとして前記第１データ集合に対する検索を行った場合における、前記第１データ集合に含まれるデータの各々の、前記第２クエリに関連する順位であるランクを付与する検索部と、
前記第１クエリであるデータと、前記ランクが上位Ｎ個の前記検索対象となるデータを要素とする第２データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する第１類似度計算部と、
前記第２データ集合の各データについて、前記第１類似度計算部により求められた類似度に基づいて、前記データが前記第１クエリに関連する度合いを示す第１ランクスコアを計算する第１ランクスコア計算部と、
前記検索対象となる複数のデータに含まれるデータの各々と、前記第２データ集合に含まれるデータの各々とを組み合わせたペアの各々について、一方の前記データと他方の前記データとの類似度である第２類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する第２類似度計算部と、
前記検索対象となる複数のデータの各々について、前記データの第１ランクスコアと、前記第２類似度とに基づいて、前記データが前記第１クエリに関連する度合いを示す第２ランクスコアを計算する第２ランクスコア計算部と、
を含む検索装置。
【請求項４】
前記第１類似度計算部は、
前記第２データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に所定のランクよりも高いランクである場合に高いランクであるほど大きい値を取るように計算し、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が前記所定のランクよりも低いランクである場合に小さい値を取るように計算し、
前記第２類似度計算部は、
前記検索対象となる複数のデータに含まれるデータの各々と、前記第２データ集合に含まれるデータの各々とを組み合わせたペアの各々について、一方の前記データと他方の前記データとの類似度である第２類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が前記所定のランクよりも低いランクである場合に小さい値を取るように計算する
請求項３記載の検索装置。
【請求項５】
検索部が、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とするデータ集合に含まれるデータの各々について、前記データを第２クエリとして前記データ集合に対する検索を行った場合における、前記データ集合に含まれるデータの各々の、前記第２クエリに関連する順位であるランクを付与する検索ステップと、
類似度計算部が、前記データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する類似度計算ステップと、
ランクスコア計算部が、前記検索対象となる複数のデータの各々について、前記類似度計算部により求められた類似度に基づいて、前記データが前記第１クエリに関連する度合いを示すランクスコアを計算するランクスコア計算ステップと、
を含む検索方法。
【請求項６】
前記類似度計算ステップは、
前記データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が前記所定のランクよりも低いランクである場合に小さい値を取るように計算する
請求項５記載の検索方法。
【請求項７】
検索部が、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とする第１データ集合に含まれるデータの各々について、前記データを第２クエリとして前記第１データ集合に対する検索を行った場合における、前記第１データ集合に含まれるデータの各々の、前記第２クエリに関連する順位であるランクを付与する検索ステップと、
第１類似度計算部が、前記第１クエリであるデータと、前記ランクが上位Ｎ個の前記検索対象となるデータを要素とする第２データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する第１類似度計算ステップと、
第１ランクスコア計算部が、前記第２データ集合の各データについて、前記第１類似度計算部により求められた類似度に基づいて、前記データが前記第１クエリに関連する度合いを示す第１ランクスコアを計算する第１ランクスコア計算ステップと、
第２類似度計算部が、前記検索対象となる複数のデータに含まれるデータの各々と、前記第２データ集合に含まれるデータの各々とを組み合わせたペアの各々について、一方の前記データと他方の前記データとの類似度である第２類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する第２類似度計算ステップと、
第２ランクスコア計算部が、前記検索対象となる複数のデータの各々について、前記データの第１ランクスコアと、前記第２類似度とに基づいて、前記データが前記第１クエリに関連する度合いを示す第２ランクスコアを計算する第２ランクスコア計算ステップと、
を含む検索方法。
【請求項８】
コンピュータを、請求項１乃至４の何れか１項記載の検索装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置、検索方法、およびプログラムに関し、特に、リランキングの精度を高めるための検索装置、検索方法、およびプログラムに関する。
【背景技術】
【０００２】
検索とは、検索の利用者がクエリを入力し、検索アルゴリズムがクエリとデータベースに格納されている検索対象のデータとの関係性の測度を計算し、関係性の測度が最も高い検索対象のデータや関係性の測度が所定の閾値より高い検索対象のデータ、検索対象のデータを関係性の測度の高い順に並べ替えたランキングリストなどを利用者に返答することである。
【０００３】
検索対象は、例えば、文書や画像、音声、映像、その他様々なメディアやその組み合わせとして記録されたデータ等がある。以下、検索対象のデータを単に検索対象と記す。また、関係性の測度を類似度と記し、クエリと検索対象との類似度を当該クエリにおける当該検索対象のランクスコアとも記す。
【０００４】
利用者にとってクエリと関係性のある検索対象を関係のある検索対象と記し、そうでない検索対象を無関係な検索対象と記す。
【０００５】
ランキングリストの中における検索対象の順位を当該検索対象のランクという。ランクの値は正の整数であり、ランクスコアとは異なる概念である。ランクが高いとはランクの値が小さいことを指し、例えば、ランクの最も高い検索対象はランクの値が１である。
【０００６】
しかし、クエリから得られる情報量が少ない場合、クエリと関係のある検索対象との類似度が低く、関係のある検索対象に低いランクが与えられる可能性が高い。
【０００７】
このような問題に対処するために、１回目の検索によってランクを与えられた検索対象に対して、新たなランクを付与するための検索対象リランキング方法が各種提案されている。
【０００８】
以下、１回目の検索によってランクを与えられた検索対象で、ランクのより高いものを上位結果と記す。上位結果の中に含まれている検索対象で、関係のあるものを真陽性の上位結果と記し、そうでないものを偽陽性の上位結果と記す。
【０００９】
例えば、非特許文献１記載の検索対象リランキング装置は、入力となる第１クエリを用いて、全検索対象を対象に１回目の検索をし、検索対象の中から上位結果を複数取得する。
【００１０】
次に、検索対象の各々について、当該検索対象を第２クエリとし、第１クエリと全検索対象とを組み合わせたデータの集合を対象に２回目の検索をし、第１クエリと全検索対象にランクを付与する。
【００１１】
そして、検索対象の各々について、第１クエリと全上位結果とに付与されたランクに基づいて、当該検索対象のランクスコアを計算する。検索対象の全てについてランクスコアの計算が完了後、ランクスコアの高い順に全検索対象を並べ替える。
【００１２】
また、例えば、非特許文献２記載の検索対象リランキング装置は、入力となる第１クエリを用いて、全検索対象を対象に１回目の検索をし、全検索対象に第１ランクを付与し、検索対象の中から上位結果を複数取得する。
【００１３】
次に、上位結果の各々について、当該上位結果を第２クエリとし、第１クエリと全検索対象とを組み合わせたデータの集合を対象に２回目の検索をし、第１クエリと全検索対象に第２ランクを付与する。
【００１４】
そして、検索対象の各々について、全上位結果の第１ランクの行列と、第１クエリの第２ランクの行列と、当該検索対象の第２ランクの行列と、に基づいて、当該検索対象のランクスコアを計算する。
【００１５】
検索対象の全てについてランクスコアの計算が完了後、ランクスコアの高い順に全検索対象を並べ替える。
【００１６】
また、例えば、非特許文献３記載の検索装置は、クエリと全検索対象とを組み合わせたデータの集合において、データのペアの各々について、当該ペアを構成した２個のデータ間の距離に基づく類似度を計算し、ランクスコアの初期値を定める。
【００１７】
次に、データのペアの全てについて類似度の計算が完了後、データの各々について、当該データと全データとの類似度と全データのランクスコアに基づいて、当該データのランクスコアを更新する。
【００１８】
そして、データの全てについてランクスコアの更新をし、当該更新処理を複数回繰り返し、最終回の更新で得られたランクスコアの高い順に全検索対象を並べ替える。
【先行技術文献】
【非特許文献】
【００１９】
【非特許文献１】Danfeng Qin, Stephan Gammeter, Lukas Bossard, Till Quack, and Luc J. Van Gool. Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors. In CVPR, 2011, pp. 777-784.
【非特許文献２】Xiaohui Shen, Zhe Lin, Jonathan Brandt, and Ying Wu. Spatially-constrained similarity measure for large-scale object retrieval. IEEE Trans. Pattern Anal. Mach. Intell., Vol. 36, No. 6, 2014, pp. 1229-1241.
【非特許文献３】Dengyong Zhou, Jason Weston, Arthur Gretton, Olivier Bousquet, and Bernhard Scholkopf. Ranking on data manifolds. In NIPS, 2003, pp. 169-176.
【発明の概要】
【発明が解決しようとする課題】
【００２０】
検索対象リランキング方法の精度は、上位結果のリランキングに対する貢献度の正確性に強く依存する。
【００２１】
偽陽性の上位結果のリランキングに対する貢献度が高く計算された場合、当該上位結果との類似度が高い無関係な検索対象は、ランクスコアが高く計算され、リランキングの精度に悪影響を与える。
【００２２】
例えば、非特許文献１記載の方法は、全上位結果のリランキングに対する貢献度を一様に扱う。また、非特許文献２記載の方法は、各上位結果の第１ランクに反比例する加重値を当該上位結果のリランキングに対する貢献度として計算する。
【００２３】
しかし、第１ランクの正確性は１回目の検索の精度に強く依存し、１回目の検索の精度が低い場合、偽陽性の上位結果については第１ランクが高く、高い加重値が付与される可能性が高い。
【００２４】
こうした第１ランクの高い偽陽性の上位結果は、依然としてリランキングに対する貢献度が高く、リランキングの精度に悪影響を与える場合が多い。
【００２５】
このため、偽陽性の上位結果のリランキングに対する貢献度と、真陽性の上位結果と無関係な検索対象との類似度が低い場合であっても、当該類似度が高いと判断されてしまうことにより、リランキングの精度が劣化する、という問題があった。
【００２６】
本発明は上記の点に鑑みてなされたものであり、リランキングの精度を高めて、検索の精度を高めることができる検索装置、検索方法、およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２７】
本発明に係る検索装置は、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とするデータ集合に含まれるデータの各々について、前記データを第２クエリとして前記データ集合に対する検索を行った場合における、前記データ集合に含まれるデータの各々の、前記第２クエリに関連する順位であるランクを付与する検索部と、前記データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する類似度計算部と、前記検索対象となる複数のデータの各々について、前記類似度計算部により求められた類似度に基づいて、前記データが前記第１クエリに関連する度合いを示すランクスコアを計算するランクスコア計算部と、を備えて構成される。
【００２８】
また、本発明に係る検索方法は、検索部が、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とするデータ集合に含まれるデータの各々について、前記データを第２クエリとして前記データ集合に対する検索を行った場合における、前記データ集合に含まれるデータの各々の、前記第２クエリに関連する順位であるランクを付与する検索ステップと、類似度計算部が、前記データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する類似度計算ステップと、ランクスコア計算部が、前記検索対象となる複数のデータの各々について、前記類似度計算部により求められた類似度に基づいて、前記データが前記第１クエリに関連する度合いを示すランクスコアを計算するランクスコア計算ステップと、を含む。
【００２９】
本発明に係る検索装置及び検索方法によれば、検索部が、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とするデータ集合に含まれるデータの各々について、当該データを第２クエリとしてデータ集合に対する検索を行った場合における、データ集合に含まれるデータの各々の、第２クエリに関連する順位であるランクを付与し、類似度計算部が、データ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する。
【００３０】
そして、ランクスコア計算部が、検索対象となる複数のデータの各々について、類似度計算部により求められた類似度に基づいて、当該データが第１クエリに関連する度合いを示すランクスコアを計算する。
【００３１】
このように、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とするデータ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算することにより、関係のある検索対象と無関係な検索対象との類似度を低く抑制し、無関係な検索対象のランクスコアをより正確に計算し、リランキングの精度を高めて、検索の精度を高めることができる。
【００３２】
また、本発明に係る検索装置の類似度計算部は、前記データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が前記所定のランクよりも低いランクである場合に小さい値を取るように計算することができる。
【００３３】
また、本発明に係る検索方法の前記類似度計算ステップは、前記データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が前記所定のランクよりも低いランクである場合に小さい値を取るように計算することができる。
【００３４】
また、本発明に係る検索装置は、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とする第１データ集合に含まれるデータの各々について、前記データを第２クエリとして前記第１データ集合に対する検索を行った場合における、前記第１データ集合に含まれるデータの各々の、前記第２クエリに関連する順位であるランクを付与する検索部と、前記第１クエリであるデータと、前記ランクが上位Ｎ個の前記検索対象となるデータを要素とする第２データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する第１類似度計算部と、前記第２データ集合の各データについて、前記第１類似度計算部により求められた類似度に基づいて、前記データが前記第１クエリに関連する度合いを示す第１ランクスコアを計算する第１ランクスコア計算部と、前記検索対象となる複数のデータに含まれるデータの各々と、前記第２データ集合に含まれるデータの各々とを組み合わせたペアの各々について、一方の前記データと他方の前記データとの類似度である第２類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する第２類似度計算部と、前記検索対象となる複数のデータの各々について、前記データの第１ランクスコアと、前記第２類似度とに基づいて、前記データが前記第１クエリに関連する度合いを示す第２ランクスコアを計算する第２ランクスコア計算部と、を備えて構成される。
【００３５】
また、本発明に係る検索方法は、検索部が、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とする第１データ集合に含まれるデータの各々について、前記データを第２クエリとして前記第１データ集合に対する検索を行った場合における、前記第１データ集合に含まれるデータの各々の、前記第２クエリに関連する順位であるランクを付与する検索ステップと、第１類似度計算部が、前記第１クエリであるデータと、前記ランクが上位Ｎ個の前記検索対象となるデータを要素とする第２データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する第１類似度計算ステップと、第１ランクスコア計算部が、前記第２データ集合の各データについて、前記第１類似度計算部により求められた類似度に基づいて、前記データが前記第１クエリに関連する度合いを示す第１ランクスコアを計算する第１ランクスコア計算ステップと、第２類似度計算部が、前記検索対象となる複数のデータに含まれるデータの各々と、前記第２データ集合に含まれるデータの各々とを組み合わせたペアの各々について、一方の前記データと他方の前記データとの類似度である第２類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する第２類似度計算ステップと、第２ランクスコア計算部が、前記検索対象となる複数のデータの各々について、前記データの第１ランクスコアと、前記第２類似度とに基づいて、前記データが前記第１クエリに関連する度合いを示す第２ランクスコアを計算する第２ランクスコア計算ステップと、を含む。
【００３６】
本発明に係る検索装置及び検索方法によれば、検索部が、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とする第１データ集合に含まれるデータの各々について、当該データを第２クエリとして第１データ集合に対する検索を行った場合における、第１データ集合に含まれるデータの各々の、当該第２クエリに関連する順位であるランクを付与し、第１類似度計算部が、第１クエリであるデータと、ランクが上位Ｎ個の検索対象となるデータを要素とする第２データ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算し、第１ランクスコア計算部が、第２データ集合の各データについて、第１類似度計算部により求められた類似度に基づいて、当該データが第１クエリに関連する度合いを示す第１ランクスコアを計算する。
【００３７】
そして、第２類似度計算部が、検索対象となる複数のデータに含まれるデータの各々と、第２データ集合に含まれるデータの各々とを組み合わせたペアの各々について、一方の当該データと他方の当該データとの類似度である第２類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算し、第２ランクスコア計算部が、検索対象となる複数のデータの各々について、当該データの第１ランクスコアと、第２類似度とに基づいて、当該データが第１クエリに関連する度合いを示す第２ランクスコアを計算する。
【００３８】
このように、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とする第１データ集合に含まれるデータの各々について、当該データを第２クエリとして第１データ集合に対する検索を行った場合における、第１データ集合に含まれるデータの各々の、当該第２クエリに関連する順位であるランクを付与し、第１類似度計算部が、第１クエリであるデータと、ランクが上位Ｎ個の検索対象となるデータを要素とする第２データ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算し、第２データ集合の各データについて、類似度に基づいて、当該データが第１クエリに関連する度合いを示す第１ランクスコアを計算し、検索対象となる複数のデータに含まれるデータの各々と、第２データ集合に含まれるデータの各々とを組み合わせたペアの各々について、一方の当該データと他方の当該データとの類似度である第２類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算し、検索対象となる複数のデータの各々について、当該データの第１ランクスコアと、第２類似度とに基づいて、当該データが第１クエリに関連する度合いを示す第２ランクスコアを計算することにより、偽陽性の上位結果のリランキングに対する貢献度と、真陽性の上位結果と無関係な検索対象との類似度とを低く抑制し、リランキングの精度を高めて、検索の精度を高めることができる。
【００３９】
また、本発明に係る検索装置の第１類似度計算部は、前記第２データ集合に含まれるデータのペアの各々について、一方の前記データと他方の前記データとの類似度を、一方の前記データを第２クエリとした場合における他方の前記データに付与されたランクと、他方の前記データを第２クエリとした場合における一方の前記データに付与されたランクとが、共に所定のランクよりも高いランクである場合に高いランクであるほど大きい値を取るように計算し、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が前記所定のランクよりも低いランクである場合に小さい値を取るように計算し、第２類似度計算部は、検索対象となる複数のデータに含まれるデータの各々と、第２データ集合に含まれるデータの各々とを組み合わせたペアの各々について、一方の当該データと他方の当該データとの類似度である第２類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が前記所定のランクよりも低いランクである場合に小さい値を取るように計算することができる。
【００４０】
本発明に係るプログラムは、上記の検索装置の各部として機能させるためのプログラムである。
【発明の効果】
【００４１】
本発明の検索装置、検索方法、およびプログラムによれば、リランキングの精度を高めて、検索の精度を高めることができる。
【図面の簡単な説明】
【００４２】
【図１】本発明の第１実施の形態に係る検索装置の構成を示す概略図である。
【図２】本発明の第１実施の形態に係る検索装置の検索処理ルーチンを示すフローチャートである。
【図３】本発明の第２実施の形態に係る検索装置の構成を示す概略図である。
【図４】本発明の第２実施の形態に係る検索装置の検索処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００４３】
以下、本発明の実施の形態について図面を用いて説明する。
【００４４】
＜本発明の第１実施の形態に係る検索装置の概要＞
まず、本発明の第１実施形態の概要について説明する。
【００４５】
非特許文献３記載の方法では、検索の精度は、ランクスコアの更新に必要な全データ間の類似度の正確性に強く依存する。当該方法は、データ間の距離に基づく類似度を用いているが、距離計算の正確性が低い場合、関係のある検索対象と無関係な検索対象との類似度が高く計算される可能性が高い。
【００４６】
このため、無関係な検索対象は、ランクスコアが過度に高く計算され、検索の精度に悪影響を与える場合が多い、という問題があった。
【００４７】
本実施形態では、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とするデータ集合に含まれるデータの各々について、当該データを第２クエリとして、データ集合に対して検索をし、全データにランクを付与する。
【００４８】
そして、データのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する。
【００４９】
そして、データのペアの全てについて類似度の計算が完了後、計算した全データ間の類似度に基づいて、全データのランクスコアを計算する。
【００５０】
このような構成により、関係のある検索対象と無関係な検索対象との類似度を低く抑制し、無関係な検索対象のランクスコアをより正確に計算し、検索の精度を高めることが可能となる。
【００５１】
また、当該類似度を、データのペアの各々について、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が前記所定のランクよりも低いランクである場合に小さい値を取るように計算してもよい。
【００５２】
このような構成により、関係のある検索対象と無関係な検索対象との類似度をより低く抑制することができ、検索の精度をより高めることが可能となる。
【００５３】
＜本発明の第１実施の形態に係る検索装置の構成＞
図１を参照して、本発明の第１実施の形態に係る検索装置の構成について説明する。図１は、本実施形態に係る検索装置の構成を示すブロック図である。
【００５４】
検索装置１０は、ＣＰＵと、ＲＡＭと、後述する検索処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。
【００５５】
図１に示すように、本実施形態に係る検索装置１０は、入力部１００と、データベース１１０と、検索部１２０と、類似度計算部１３０と、ランクスコア計算部１４０と、出力部１５０とを備えて構成される。
【００５６】
入力部１００は、検索クエリである、第１クエリｑの入力を受け付ける。そして、入力部１００は、受け付けた第１クエリを、検索部１２０に渡す。
【００５７】
データベース１１０は、検索対象となる複数のデータを記憶している。
【００５８】
具体的には、データベース１１０は、検索対象のデータ
2019125316.tif 000003
をｎ個記憶している。データベース１１０は、検索部１２０の要求に応じて、検索対象のデータ
2019125316.tif 000004
を検索部１２０に渡す。
【００５９】
検索部１２０は、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とするデータ集合に含まれるデータの各々について、当該データを第２クエリとしてデータ集合に対する検索を行った場合における、データ集合に含まれるデータの各々の、第２クエリに関連する順位であるランクを付与する。
【００６０】
具体的には、検索部１２０は、まず、入力部１００から第１クエリｑを受け取ると、データベース１１０から、検索対象となる複数のデータ
2019125316.tif 000005
を取得し、これらを１つの集合としたデータ集合
2019125316.tif 000006
を作成する。ここで、
2019125316.tif 000007
とする。
【００６１】
次に、検索部１２０は、データ集合
2019125316.tif 000008
に含まれるデータの各々について、当該データを第２クエリとして当該データ集合に含まれるデータの各々を対象として検索した場合における、当該第２クエリと当該対象としたデータとの組に対して、当該第２クエリに関連する順位であるランクを付与する。
【００６２】
より具体的には、まずｘ０を第２クエリとして、データ集合
2019125316.tif 000009
に含まれるデータ全てを対象として検索し、全データに対してランクを付与する。ここで、データｘｉを第２クエリとした時の対象としたデータｘｊに付与されたランクをｒ（ｘｉ｜ｘｊ）と表す。
【００６３】
例えば、検索した第２クエリｘ０と対象としたデータｘ２とのランクが３であった場合、ｒ（ｘ０｜ｘ２）＝３となる。
【００６４】
検索部１２０は、第２クエリをｘ０と対象としたデータとの組｛ｘ０，ｘ０｝，｛ｘ０，ｘ１｝，…，｛ｘ０，ｘｎ｝の各々に対して、ｒ（ｘ０｜ｘ０）、ｒ（ｘ０｜ｘ１）、…、ｒ（ｘ０，ｘｎ）等のようにランクを付与する。
【００６５】
そして、検索部１２０は、第２クエリをｘ１とした場合、ｘ２とした場合と、データ集合の全てのデータを第２クエリとした場合も同様にデータ集合
2019125316.tif 000010
に含まれるデータ全てを対象としたランクを付与する。
【００６６】
ここで、検索方法としては、例えば検索対象が文書の場合に、ｂａｇ−ｏｆ−ｗｏｒｄｓ法等、検索対象が画像の場合に、ｂａｇ−ｏｆ−ｖｉｓｕａｌ−ｗｏｒｄｓ法等、検索対象の性質に応じた種々の検索方法を用いることができる。
【００６７】
次に、検索部１２０は、全てのデータのペアに対してランクを付与すると、得られた全ランクの値を格納するランク行列を生成し、当該ランク行列と、生成したデータ集合
2019125316.tif 000011
とを類似度計算部１３０に渡す。
【００６８】
類似度計算部１３０は、データ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する。
【００６９】
具体的には、類似度計算部１３０は、ランク行列に基づいて、データ集合
2019125316.tif 000012
に含まれるデータのペアの各々について、当該データのペア｛ｘｉ，ｘｊ｝について、類似度ｓ（ｘｉ，ｘｊ）を求める。
【００７０】
ここで、類似度計算部１３０は、類似度ｓ（ｘｉ，ｘｊ）を、一方のデータｘｉを第２クエリとした場合における他方のデータｘｊに付与されたランクｒ（ｘｉ｜ｘｊ）と、他方のデータｘｊを第２クエリとした場合における一方のデータｘｉに付与されたランクｒ（ｘｊ｜ｘｉ）とが共に高いランクであるほど大きい値を取るように計算する。例えば、下記式（１）を用いて計算することができる。
【００７１】
【数１】
2019125316.tif 000013
【００７２】
ここで、
2019125316.tif 000014
は、パラメータである。
【００７３】
また、類似度ｓ（ｘｉ，ｘｊ）を、ｒ（ｘｉ｜ｘｊ）とｒ（ｘｊ｜ｘｉ）とにおける相乗平均の逆数、相加平均の逆数、最大値の逆数等としてもよい。
【００７４】
そして、類似度計算部１３０は、全てのデータのペアについて類似度を求めると、得られた全ての類似度を格納する類似度行列を求め、当該類似度行列と、データ集合
2019125316.tif 000015
とを、ランクスコア計算部１４０に渡す。
【００７５】
ランクスコア計算部１４０は、検索対象となる複数のデータの各々について、類似度計算部１３０により求められた類似度に基づいて、当該データが第１クエリに関連する度合いを示すランクスコアを計算する。
【００７６】
具体的には、ランクスコア計算部１４０は、類似度計算部１３０より取得した類似度行列に基づいて、第１クエリｑに関して、データ集合
2019125316.tif 000016
に含まれる全データのランクスコアを計算する。
【００７７】
ランクスコアの計算は、例えば非特許文献３記載の方法を用いて計算することができる。ここで、類似度行列を
2019125316.tif 000017
とし、
2019125316.tif 000018
とする。
【００７８】
また、上記式（７）を用いて類似度を求めた場合、類似度行列の要素は、
2019125316.tif 000019
とする。
【００７９】
まず、ランクスコア計算部１４０は、Ａの対角成分を０にする。
【００８０】
次に、ランクスコア計算部１４０は、下記式（２）を用いて、対角行列Ｄを計算する。
【００８１】
【数２】
2019125316.tif 000020
【００８２】
ここで、ｄｊは、下記式（３）のように、ｘｊを検索の対象とした場合の、全ての第２クエリとの類似度の総和である。
【００８３】
【数３】
2019125316.tif 000021
【００８４】
ランクスコア計算部１４０は、下記式（４）にしたがって、
2019125316.tif 000022
を計算する。
【００８５】
【数４】
2019125316.tif 000023
【００８６】
次に下記式（５）にしたがって、ランクスコアを格納する行列ｗを計算する。ここで、行列ｗを
2019125316.tif 000024
とする。
【００８７】
【数５】
2019125316.tif 000025
【００８８】
ここで、Ｉは単位行列あり、
2019125316.tif 000026
はパラメータであり、例えばα＝０．９９を採用することができる。また、
2019125316.tif 000027
も、パラメータである。
【００８９】
また、ランクスコアは、非特許文献３記載の反復法を用いても計算することができる。例えば、下記式（６）による計算を繰り返すことにより、行列ｗを計算する。
【００９０】
【数６】
2019125316.tif 000028
【００９１】
ここで、
2019125316.tif 000029
である。また、ｔ番目の反復をしたときに計算されるｗをｗｔとし、ｗ０＝ｙとする。また、例えば反復回数を３０回とし、最終回の反復で計算された行列ｗをランクスコア計算部１４０による計算結果とすることができる。
【００９２】
また、ランクスコアは、共役勾配法を用いて、上記式（５）を解く方法によっても計算することができる。
【００９３】
そして、ランクスコア計算部１４０は、計算された行列ｗに基づいて、ランクスコアの高い順に検索対象のデータ
2019125316.tif 000030
を並べ替え、並べ替え結果を出力部１５０に渡す。
【００９４】
出力部１５０は、ランクスコア計算部１４０による並び替え結果を出力する。
【００９５】
＜本発明の第１実施の形態に係る検索装置の作用＞
図２は、本発明の第１実施の形態に係る検索処理ルーチンを示すフローチャートである。
【００９６】
入力部１００に第１クエリが入力されると、検索装置１０において、図２に示す検索処理ルーチンが実行される。
【００９７】
まず、ステップＳ１００において、入力部１００が、第１クエリの入力を受け付ける。
【００９８】
ステップＳ１１０において、検索部１２０が、データベース１１０から検索対象となる複数のデータを取得する。
【００９９】
ステップＳ１２０において、検索部１２０は、上記ステップＳ１００により受け付けた第１クエリであるデータと、上記ステップ１００により取得した検索対象となる複数のデータとを要素とするデータ集合に含まれるデータの各々について、当該データを第２クエリとしてデータ集合に対する検索を行った場合における、データ集合に含まれるデータの各々の、第２クエリに関連する順位であるランクを付与する。
【０１００】
ステップＳ１３０において、類似度計算部１３０は、データ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する。
【０１０１】
ステップＳ１４０において、ランクスコア計算部１４０は、検索対象となる複数のデータの各々について、類似度計算部１３０により求められた類似度に基づいて、当該データが第１クエリに関連する度合いを示すランクスコアを計算する。
【０１０２】
ステップＳ１５０において、ランクスコア計算部１４０は、上記ステップＳ１４０により得られたランクスコアに基づいて、ランクスコアの高い順に検索対象のデータを並べ替える。
【０１０３】
ステップＳ１６０において、出力部１５０は、上記ステップＳ１５０により得られた並び替え結果を出力する。
【０１０４】
以上説明したように、本実施形態に係る検索装置によれば、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とするデータ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算することにより、関係のある検索対象と無関係な検索対象との類似度を低く抑制し、無関係な検索対象のランクスコアをより正確に計算し、リランキングの精度を高めて、検索の精度を高めることができる。
【０１０５】
なお、本実施形態において、類似度計算部１３０は、データ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が所定のランクよりも低いランクである場合に小さい値を取るように計算してもよい。
【０１０６】
具体的には、類似度計算部１３０は、類似度ｓ（ｘｉ，ｘｊ）を、一方のデータｘｉを第２クエリとした場合における他方のデータｘｊに付与されたランクｒ（ｘｉ｜ｘｊ）と、他方のデータｘｊを第２クエリとした場合における一方のデータｘｉに付与されたランクｒ（ｘｊ｜ｘｉ）とが共に所定のランクよりも高いランクである場合に高いランクであるほど大きい値を取るように計算し、共に所定のランクよりも高いランクでない場合に小さい値を取るように計算する。例えば、下記式（７）を用いて計算することができる。
【０１０７】
【数７】
2019125316.tif 000031
【０１０８】
ここで、ｋは所定のランクである正の整数の閾値であり、例えばｋ＝３０とすることができ、ｓｋ（ｘｉ，ｘｊ）は、式（７）を用いた場合の類似度を示す。
【０１０９】
式（７）を用いる場合、ｒ（ｘｉ｜ｘｊ）とｒ（ｘｊ｜ｘｉ）とが共に所定のランクよりも高いランクでない場合には、類似度を小さい値を取るように計算することで、関係のある検索対象のデータと無関係な検索対象のデータとの類似度をより低く抑制することができ、より精度の高い類似度を求めることができる。
【０１１０】
＜本発明の第２実施の形態に係る検索装置の概要＞
本発明の第２実施形態の概要について説明する。
【０１１１】
検索対象リランキング方法の精度は、上位結果のリランキングに対する貢献度の正確性に強く依存する。偽陽性の上位結果のリランキングに対する貢献度が高く計算された場合、当該上位結果との類似度が高い無関係な検索対象は、ランクスコアが高く計算され、リランキングの精度に悪影響を与える。例えば、非特許文献１記載の方法は、全上位結果のリランキングに対する貢献度を一様に扱う。非特許文献２記載の方法は、各上位結果の第１ランクに反比例する加重値を当該上位結果のリランキングに対する貢献度として計算する。しかし、第１ランクの正確性は１回目の検索の精度に強く依存し、１回目の検索の精度が低い場合、偽陽性の上位結果については第１ランクが高く、高い加重値が付与される可能性が高い。こうした第１ランクの高い偽陽性の上位結果は、依然としてリランキングに対する貢献度が高く、リランキングの精度に悪影響を与える場合が多い。
【０１１２】
また、検索対象リランキング方法の精度は、上位結果と検索対象との類似度の正確性にも強く依存する。真陽性の上位結果と無関係な検索対象との類似度が高く計算された場合、当該検索対象のランクスコアが高く計算され、リランキングの精度が低下する。例えば、非特許文献１、２記載の方法は、２回目の検索で上位結果や検索対象などに付与されたランクに基づいて、前記類似度を計算している。
【０１１３】
しかし、２回目の検索の精度が低い場合、無関係な検索対象でも、真陽性の上位結果との類似度が高く計算され、リランキングの精度に悪影響を与える可能性が高い、という問題があった。
【０１１４】
本実施形態では、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とするデータ集合に含まれるデータの各々について、当該データを第２クエリとして、データ集合に対して検索をし、全データにランクを付与する。
【０１１５】
次に、検索対象の中から第１クエリにおける上位結果を取得し、第１クエリと全上位結果とを組み合わせた第２データ集合において、第１実施形態と同様の方法を用いて、全データのランクスコア（第１ランクスコア）を計算する。
【０１１６】
検索対象となる複数のデータに含まれるデータと、第２データ集合に含まれるデータとを組み合わせたペアの各々について、ランクに基づいて、第１実施形態と同様の方法を用いて、類似度を計算し、検索対象の各々について、第２データ集合の全データの第１ランクスコアに基づいて、当該検索対象と全データとの類似度の加重和を計算し、第２ランクスコアとする。
【０１１７】
このような構成により、偽陽性の上位結果のリランキングに対する貢献度と、真陽性の上位結果と無関係な検索対象との類似度とを低く抑制し、リランキングの精度を高めることが可能となる。
【０１１８】
また、第１実施形態の構成、従来技術の方法（例えば非特許文献３の方法）と比べて、計算量の大きい第１ランクスコアの計算を検索対象のデータの数より数少ない上位結果のみに限定するため、計算量を小さく抑制することができ、検索の速度を高めることが可能となる。
【０１１９】
＜本発明の第２実施の形態に係る検索装置の構成＞
本発明の第２実施の形態に係る検索装置２０の構成について説明する。なお、第１実施の形態に係る検索装置１０と同様の構成については、同一の符号を付して詳細な説明は省略する。
【０１２０】
検索装置２０は、ＣＰＵと、ＲＡＭと、後述する検索処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。
【０１２１】
図３に示すように、本実施形態に係る検索装置２０は、入力部１００と、データベース１１０と、検索部１２０と、第１類似度計算部２３０と、第１ランクスコア計算部２４０と、第２類似度計算部２５０と、第２ランクスコア計算部２６０と、出力部１５０とを備えて構成される。
【０１２２】
検索部１２０は、更に、生成したランク行列と、生成したデータ集合
2019125316.tif 000032
を第２類似度計算部２５０に渡す。ここで、本実施形態では、データ集合
2019125316.tif 000033
を第１データ集合と呼ぶ。
【０１２３】
第１類似度計算部２３０は、第１クエリであるデータと、ランクが上位Ｎ個の検索対象となるデータを要素とする第２データ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する。
【０１２４】
具体的には、第１類似度計算部２３０は、まず、検索部１２０によって計算されたランク行列に含まれている、第１クエリｑ（ｘ０）を用いた時に検索対象のデータ
2019125316.tif 000034
に付与されたランクｒ（ｘ１｜ｘ０），ｒ（ｘ２｜ｘ０），…，ｒ（ｘｎ｜ｘ０）に基づいて、検索対象のデータのうち第１クエリにおける上位ｍ個のデータを取得する。例えば、上位１００個（ｍ＝１００）個のデータを取得する場合、ｒ（ｘｉ｜ｘ０）≦１００となるｘｉを取得する。ここで、取得した上位結果を、
2019125316.tif 000035
とする。
【０１２５】
そして、第１類似度計算部２３０は、第１クエリｑと、取得した上位結果
2019125316.tif 000036
とを１つの集合とした第２データ集合
2019125316.tif 000037
を作成する。
【０１２６】
次に、第１類似度計算部２３０は、第２データ集合
2019125316.tif 000038
に含まれるデータのペアの各々について、当該データのペア｛ｚｉ，ｚｊ｝について、類似度ｓ（ｚｉ，ｚｊ）を、一方のデータｚｉを第２クエリとした場合における他方のデータｚｊに付与されたランクｒ（ｚｉ｜ｚｊ）と、他方のデータｚｊを第２クエリとした場合における一方のデータｚｉに付与されたランクｒ（ｚｊ｜ｚｉ）とが共に高いランクであるほど大きい値を取るように計算する。
【０１２７】
例えば、上記式（１）を用いて計算し、また、類似度ｓ（ｚｉ，ｚｊ）を、相乗平均の逆数、相加平均の逆数、最大値の逆数等としてもよい。
【０１２８】
また、第１類似度計算部２３０は、第１クエリであるデータと、ランクが上位Ｎ個の検索対象となるデータとを要素とする第２データ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に所定のランクよりも高いランクである場合に高いランクであるほど大きい値を取るように計算し、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が所定のランクよりも低いランクである場合に小さい値を取るように計算してもよい。
【０１２９】
具体的には、第１類似度計算部２３０は、第２データ集合
2019125316.tif 000039
に含まれるデータのペアの各々について、当該データのペア｛ｚｉ，ｚｊ｝について、類似度ｓ（ｚｉ，ｚｊ）を、一方のデータｚｉを第２クエリとした場合における他方のデータｚｊに付与されたランクｒ（ｚｉ｜ｚｊ）と、他方のデータｚｊを第２クエリとした場合における一方のデータｚｉに付与されたランクｒ（ｚｊ｜ｚｉ）とが、共に所定のランクよりも高いランクである場合に高いランクであるほど大きい値を取るように計算し、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が所定のランクよりも低いランクである場合に小さい値を取るように計算する。
【０１３０】
例えば、上記式（７）の方法を用いて、類似度ｓｋ（ｚｉ，ｚｊ）を求めることができる。
【０１３１】
そして、第１類似度計算部２３０は、得られた全ての類似度を格納する第１類似度行列を求め、第１類似度行列と、第２データ集合
2019125316.tif 000040
とを、第２ランクスコア計算部２６０に渡す。
【０１３２】
また、第１類似度計算部２３０は、第２データ集合
2019125316.tif 000041
を、第２類似度計算部２５０に渡す。
【０１３３】
第１ランクスコア計算部２４０は、第２データ集合の各データについて、第１類似度計算部２３０により求められた類似度に基づいて、当該データが第１クエリに関連する度合いを示す第１ランクスコアを計算する。
【０１３４】
具体的には、第１ランクスコア計算部２４０は、第１実施形態に係るランクスコア計算部１４０と同様の手法により、第１類似度計算部２３０より取得した第１類似度行列に基づいて、第１クエリｑに関して、第２データ集合
2019125316.tif 000042
に含まれるデータの各々についてのランクスコアである第１ランクスコアを計算する。
【０１３５】
そして、第１ランクスコア計算部２４０は、第１ランクスコアを格納する第１ランクスコア行列を、第２ランクスコア計算部２６０に渡す。
【０１３６】
第２類似度計算部２５０は、検索対象となる複数のデータに含まれるデータの各々と、第２データ集合に含まれるデータの各々とを組み合わせたペアの各々について、一方の当該データと他方の当該データとの類似度である第２類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する。
【０１３７】
具体的には、第２類似度計算部２５０は、検索対象となる複数のデータ
2019125316.tif 000043
に含まれるデータｘｉと、第２データ集合
2019125316.tif 000044
に含まれるデータｚｊとを組み合わせたペアの各々について、当該データのペア｛ｚｉ，ｘｊ｝について、第２類似度ｓ（ｘｉ，ｚｊ）を、一方のデータｘｉを第２クエリとした場合における他方のデータｚｊに付与されたランクｒ（ｚｉ｜ｘｉ）と、他方のデータｚｊを第２クエリとした場合における一方のデータｘｉに付与されたランクｒ（ｘｉ｜ｚｊ）とが、共に高いランクであるほど大きい値を取るように計算する。
【０１３８】
例えば、上記式（１）を用いて計算し、また、第２類似度ｓ（ｘｉ，ｚｊ）を、相乗平均の逆数、相加平均の逆数、最大値の逆数等としてもよい。
【０１３９】
そして、第２類似度計算部２５０は、得られた全ての第２類似度を格納する第２類似度行列を求め、第２類似度行列を、第２ランクスコア計算部２６０に渡す。
【０１４０】
第２ランクスコア計算部２６０は、検索対象となる複数のデータの各々について、当該データの第１ランクスコアと、第２類似度とに基づいて、当該データが第１クエリに関連する度合いを示す第２ランクスコアを計算する。
【０１４１】
具体的には、第２ランクスコア計算部２６０は、検索対象のデータの各々について、第２データ集合
2019125316.tif 000045
に含まれるデータの各々についての第１ランクスコアに基づいて、当該検索対象のデータと当該第２データ集合に含まれるデータのペアとの第２類似度の加重和を計算し、第２ランクスコアとする。
【０１４２】
ここで、第１ランクスコア行列を
2019125316.tif 000046
と、検索対象のデータｘｉの第２ランクスコアをｐ（ｘｉ）と表す。
【０１４３】
例えば、第２ランクスコアは、下記式（８）や式（９）などを用いて計算する。
【０１４４】
【数８】
2019125316.tif 000047
【０１４５】
【数９】
2019125316.tif 000048
【０１４６】
そして、第２ランクスコア計算部２６０は、第２ランクスコアの高い順に検索対象のデータ
2019125316.tif 000049
を並べ替え、並べ替え結果を出力部１５０に渡す。
【０１４７】
＜本発明の第２実施の形態に係る検索装置の作用＞
図４は、本発明の第２実施の形態に係る検索処理ルーチンを示すフローチャートである。なお、第１実施の形態に係る検索処理ルーチンと同様の処理については、同一の符号を付して詳細な説明は省略する。
【０１４８】
ステップＳ２３０において、第１類似度計算部２３０は、第１クエリであるデータと、ランクが上位Ｎ個の検索対象となるデータを要素とする第２データ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する。
【０１４９】
また、ステップＳ２３０において、第１類似度計算部２３０は、第１クエリであるデータと、ランクが上位Ｎ個の検索対象となるデータとを要素とする第２データ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に所定のランクよりも高いランクである場合に高いランクであるほど大きい値を取るように計算し、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が所定のランクよりも低いランクである場合に小さい値を取るように計算してもよい。
【０１５０】
ステップＳ２４０において、第１ランクスコア計算部２４０は、第２データ集合の各データについて、上記ステップＳ２３０により求められた類似度に基づいて、当該データが第１クエリに関連する度合いを示す第１ランクスコアを計算する。
【０１５１】
ステップＳ２４２において、第２類似度計算部２５０は、検索対象となる複数のデータに含まれるデータの各々と、第２データ集合に含まれるデータの各々とを組み合わせたペアの各々について、一方の当該データと他方の当該データとの類似度である第２類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算する。
【０１５２】
ステップＳ２４４において、第２ランクスコア計算部２６０は、検索対象となる複数のデータの各々について、当該データの第１ランクスコアと、上記ステップＳ２４２により求められた第２類似度とに基づいて、当該データが第１クエリに関連する度合いを示す第２ランクスコアを計算する。
【０１５３】
ステップＳ２５０において、第２ランクスコア計算部２６０は、上記ステップＳ２４４により得られた第２ランクスコアの高い順に検索対象のデータを並べ替える。
【０１５４】
以上説明したように、本実施形態に係る検索装置によれば、入力された第１クエリであるデータと、検索対象となる複数のデータとを要素とする第１データ集合に含まれるデータの各々について、当該データを第２クエリとして第１データ集合に対する検索を行った場合における、第１データ集合に含まれるデータの各々の、当該第２クエリに関連する順位であるランクを付与し、第１類似度計算部が、第１クエリであるデータと、ランクが上位Ｎ個の検索対象となるデータを要素とする第２データ集合に含まれるデータのペアの各々について、一方の当該データと他方の当該データとの類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算し、第１ランクスコア計算部が、第２データ集合の各データについて、第１類似度計算部により求められた類似度に基づいて、当該データが第１クエリに関連する度合いを示す第１ランクスコアを計算し、検索対象となる複数のデータに含まれるデータの各々と、第２データ集合に含まれるデータの各々とを組み合わせたペアの各々について、一方の当該データと他方の当該データとの類似度である第２類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に高いランクであるほど大きい値を取るように計算し、検索対象となる複数のデータの各々について、当該データの第１ランクスコアと、第２類似度とに基づいて、当該データが第１クエリに関連する度合いを示す第２ランクスコアを計算することにより、偽陽性の上位結果のリランキングに対する貢献度と、真陽性の上位結果と無関係な検索対象との類似度とを低く抑制し、リランキングの精度を高めて、検索の精度を高めることができる。
【０１５５】
また、計算量の大きい第１ランクスコアの計算を、検索対象のデータ数より少ない上位結果のみに限定するため、計算量を小さく抑制することができ、検索の速度を高めることが可能となる。
【０１５６】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１５７】
例えば、第２の実施形態において、第２類似度計算部２５０は、検索対象となる複数のデータに含まれるデータの各々と、第２データ集合に含まれるデータの各々とを組み合わせたペアの各々について、一方の当該データと他方の当該データとの類似度である第２類似度を、一方の当該データを第２クエリとした場合における他方の当該データに付与されたランクと、他方の当該データを第２クエリとした場合における一方の当該データに付与されたランクとが、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が前記所定のランクよりも低いランクである場合に小さい値を取るように計算するようにしてもよい。
【０１５８】
具体的には、第２類似度計算部２５０は、検索対象となる複数のデータ
2019125316.tif 000050
に含まれるデータｘｉと、第２データ集合
2019125316.tif 000051
に含まれるデータｚｊとを組み合わせたペアの各々について、当該データのペア｛ｚｉ，ｘｊ｝について、第２類似度ｓ（ｘｉ，ｚｊ）を、一方のデータｘｉを第２クエリとした場合における他方のデータｚｊに付与されたランクｒ（ｚｊ｜ｘｉ）と、他方のデータｚｊを第２クエリとした場合における一方のデータｘｉに付与されたランクｒ（ｘｉ｜ｚｊ）とが、共に所定のランクよりも高いランクである場合に高いランクであるほど大きい値を取るように計算し、共に所定のランクよりも高いランクである場合に共に高いランクであるほど大きい値を取るように計算し、少なくとも一方が所定のランクよりも低いランクである場合に小さい値を取るように計算する。
【０１５９】
例えば、上記式（７）の方法を用いて、第２類似度ｓｋ（ｘｉ，ｚｊ）を求めることができる。
【０１６０】
また、第２実施形態において、第１類似度計算部２３０が、上位検索
2019125316.tif 000052
と、第２データ集合
2019125316.tif 000053
とを作成したが、検索部１２０が生成し、第１類似度計算部２３０と、第２類似度計算部２５０とにそれぞれ渡す構成としてもよい。
【０１６１】
また、第２類似度計算部２５０においても、上位検索
2019125316.tif 000054
と、第２データ集合
2019125316.tif 000055
とを作成する構成としてもよい。
【０１６２】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【０１６３】
１０   検索装置
２０   検索装置
１００ 入力部
１１０ データベース
１２０ 検索部
１３０ 類似度計算部
１４０ ランクスコア計算部
１５０ 出力部
２３０ 第１類似度計算部
２４０ 第１ランクスコア計算部
２５０ 第２類似度計算部
２６０ 第２ランクスコア計算部
【図１】
2019125316.tif 000056
【図２】
2019125316.tif 000057
【図３】
2019125316.tif 000058
【図４】
2019125316.tif 000059