(57)【要約】【課題】データ検索を高速かつ精度よくおこなう。【解決手段】検索装置１００は、Manifold  Rankingでスコアを計算し、スコアが高い順にｋ個のノードを検索結果として出力する。検索装置１００は、事前計算部１０、検索部２０を有する。事前計算部１０は、グラフデータＧ＝｛Ｖ，Ｅ｝（Ｖはノード集合、Ｅはエッジ集合）を外部入力とし、三角行列を出力する。検索部２０は、問い合わせノードｕｑおよび検索数ｋを外部入力とし、事前計算部１０からの三角行列を内部入力とし、検索結果としてｋ個のノードを出力する。【選択図】図１３
2015232782.tif 000002
【特許請求の範囲】
【請求項１】
記憶部と協働して処理を実行する制御部を有する検索装置であって、
前記制御部は、
複数のノードならびに前記ノード間を接続するエッジを含む入力グラフの隣接行列に基づく、各前記ノードのスコアを算出する行列に対して、疎行列を含む行列積へ行列分解をおこない、
問い合わせノードならびに検索数の入力に応じて、前記行列分解をおこなった行列から求まる前記問い合わせノードに対する前記スコアが、上位から前記検索数以内の解ノードを、前記複数のノードから選択して出力する
ことを特徴とする検索装置。
【請求項２】
さらに、
前記制御部は、
前記入力グラフを複数のクラスタへ分割し、
前記クラスタごとに、クラスタ内の全ノードに対する前記スコアの上限値を推定し、
前記問い合わせノードに対する前記スコアが上位から前記検索数だけの解ノードを、前記複数のノードから選択する際に、前記クラスタごとに推定した前記スコアの上限値が、前記解ノードの集合に既に含まれる要素に対応する前記スコアの最小値（ただし、前記解ノードの集合が空集合の場合には、０）未満であるクラスタを、前記解ノードを選択する対象クラスタから除外する
ことを特徴とする請求項１に記載の検索装置。
【請求項３】
さらに、
前記制御部は、
前記入力グラフを複数のクラスタへ分割し、
各前記クラスタにおいて、接続されるエッジ数が少ない順序でノードを並び替え、
前記ノードの並び替えに応じて求まる行列に基づいて前記スコアを算出する行列を変換した行列に対して前記行列分解をおこなう
ことを特徴とする請求項１に記載の検索装置。
【請求項４】
前記行列分解は、不完全コレスキー分解である
ことを特徴とする請求項１、２または３に記載の検索装置。
【請求項５】
検索装置が実行する検索方法であって、
前記検索装置が、
複数のノードならびに前記ノード間を接続するエッジを含む入力グラフの隣接行列に基づく、各前記ノードのスコアを算出する行列に対して、疎行列を含む行列積へ行列分解をおこない、
問い合わせノードならびに検索数の入力に応じて、前記行列分解をおこなった行列から求まる前記問い合わせノードに対する前記スコアが、上位から前記検索数以内の解ノードを、前記複数のノードから選択して出力する
処理を含むことを特徴とする検索方法。
【請求項６】
さらに、
前記検索装置が、
前記入力グラフを複数のクラスタへ分割し、
前記クラスタごとに、クラスタ内の全ノードに対する前記スコアの上限値を推定し、
前記問い合わせノードに対する前記スコアが上位から前記検索数だけの解ノードを、前記複数のノードから選択する際に、前記クラスタごとに推定した前記スコアの上限値が、前記解ノードの集合に既に含まれる要素に対応する前記スコアの最小値（ただし、前記解ノードの集合が空集合の場合には、０）未満であるクラスタを、前記解ノードを選択する対象クラスタから除外する
処理を含むことを特徴とする請求項５に記載の検索方法。
【請求項７】
さらに、
前記検索装置が、
前記入力グラフを複数のクラスタへ分割し、
各前記クラスタにおいて、接続されるエッジ数が少ない順序でノードを並び替え、
前記ノードの並び替えに応じて求まる行列に基づいて前記スコアを算出する行列を変換した行列に対して前記行列分解をおこなう
処理を含むことを特徴とする請求項５に記載の検索方法。
【請求項８】
請求項１〜４のいずれか１つに記載の検索装置としてコンピュータを機能させるための検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置などに関する。
【背景技術】
【０００２】
近年、Flickr（登録商標）などのウェブサービスが発達してきているように、画像検索が普及しつつある。そのなか、画像検索の手法についての研究が盛んにおこなわれている。画像検索の目的は、問い合わせ画像と意味が同じ画像を見いだすことである。
【０００３】
そこで、画像検索においては、ユーザの意図に基づき、どのように画像をランキングするかが重要な問題となる。１９７０年代に提案された初期の画像検索の手法は、キーワードに基づくものである。キーワードに基づく画像検索の手法は、現在でも多くのウェブサービスで用いられている。しかし、テキストと、画像との間には、意味的なギャップがあるという問題がある。
【０００４】
この意味的なギャップを克服するために、問い合わせ画像と最も視覚的に似た画像を検索する検索手法が、１９９０年代に提案された。この検索手法は、データベースに格納された画像を、形や色などの低次元の特徴量を用いた類似度に基づいてランキングをおこない、類似度がより高い画像を検索結果とする。この検索手法は、キーワードに基づく検索手法と比較して、画像の特徴量を自動抽出できるというメリットがある。しかし、この検索手法は、低次元の特徴量ではユーザが望む意図を十分に反映し切れず、画像の特徴量とユーザの意図との間にギャップがあり、適切な検索結果が必ずしも得られないという問題がある。
【０００５】
このギャップの問題を解決する手法として、Manifold  Rankingを画像検索に用いることが提案されている。Manifold  Rankingとは、データポイントによって構成されるクラスタ（典型的にManifoldとよばれる）に基づいて、データポイントのランキングを計算する手法である。また、同じクラスタに属するデータポイントは同じ意味を持つことを前提とし、画像検索における上記のギャップの問題を解決する手法も提案されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】J.He，M.Li，H.Zhang，H.Tong，and  C.Zhang，“Manifold-Ranking  Based  Image  Retrieval”，In  ACM  Multimedia,2004.
【非特許文献２】D.Zhou，J.Weston，A.Gretton，O.Bousquet，and  B.Schoelkopf，“Ranking  on  Data  Manifolds”，In  NIPS，2003.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、Manifold  Rankingを用いる画像検索の手法は、高い計算量が問題となる。理論的には、Manifold  Rankingにおけるランキングスコアは、後述するコスト関数を最小化するものとして定義される。コスト関数を最小化する最適解は、データポイントの数をｎとしたとき、サイズがｎ×ｎである行列の逆行列を計算することで求めることができる。ｎ×ｎ行列の逆行列を求める計算量はＯ（ｎ３）であるため、Manifold  Rankingにおける計算量はＯ（ｎ３）となる。さらに、Manifold  Rankingを用いる画像検索の手法は、逆行列を保持することから、Ｏ（ｎ２）のメモリ量が必要となる。このような課題は、画像検索に限らず、一般的なデータ検索にもあてはまる。
【０００８】
本願が開示する実施形態の一例は、上記に鑑みてなされたものであって、データ検索を高速かつ精度よくおこなうことを目的とする。
【課題を解決するための手段】
【０００９】
本願が開示する実施形態の一例は、複数のノードならびにノード間を接続するエッジを含む入力グラフの隣接行列に基づく、各ノードのスコアを算出する行列に対して、疎行列を含む行列積へ行列分解をおこなう。そして、実施形態の一例は、問い合わせノードならびに検索数の入力に応じて、行列分解をおこなった行列から求まる問い合わせノードに対するスコアが、上位から検索数以内の解ノードを、複数のノードから選択して出力する。
【発明の効果】
【００１０】
本願が開示する実施形態の一例によれば、例えば、データ検索を高速かつ精度よくおこなうことができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、補助定理１を示す図である。
【図２】図２は、定理１を示す図である。
【図３】図３は、補助定理２を示す図である。
【図４】図４は、補助定理３を示す図である。
【図５】図５は、補助定理４を示す図である。
【図６】図６は、定義１を示す図である。
【図７】図７は、補助定理５を示す図である。
【図８】図８は、定義２を示す図である。
【図９】図９は、補助定理６を示す図である。
【図１０】図１０は、補助定理７を示す図である。
【図１１】図１１は、定理２を示す図である。
【図１２】図１２は、定理３を示す図である。
【図１３】図１３は、検索装置の構成の一例を示すブロック図である。
【図１４】図１４は、事前計算部の構成の一例を示すブロック図である。
【図１５】図１５は、検索部の構成の一例を示すブロック図である。
【図１６】図１６は、事前計算処理を示すフローチャートの一例を示す図である。
【図１７】図１７は、検索処理を示すフローチャートの一例を示す図である。
【図１８】図１８は、ノードの並び替えによる最適化処理のアルゴリズムの一例を示す図である。
【図１９】図１９は、ｔｏｐ−ｋ検索処理のアルゴリズムの一例を示す図である。
【図２０】図２０は、検索プログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１２】
実施形態の説明に先立ち、以下の説明で用いる主な記号の定義、従来手法の数理的背景の説明、実施形態の数理的背景の説明をおこなう。その後、実施形態を説明する。
【００１３】
［主な記号の定義］
実施形態で用いる主な記号を下表に示す。以下、従来手法の数理的背景、実施形態の数理的背景、実施形態の各説明において、同一の記号を用いる。
【００１４】
【表１】
2015232782.tif 000003
【００１５】
［従来手法の数理的背景］
以下、従来手法の数理的背景を説明する。Manifold  Rankingでは、ｋ−ＮＮグラフを用いてデータを表現することが一般的である。グラフのノードは、データポイントに対応する。２つのデータポイントがｋ近傍であれば、２つのデータポイント間は、無向グラフで接続される。ｋ−ＮＮグラフを用いたランキングとは、ノードの集合をＵ＝｛ｕ１，ｕ２，・・・，ｕｎ｝⊂Ｒｍ（Ｒｍ：ｍ次実空間）とし、問い合わせノードをｕｑ∈Ｕとしたときに、Ｕに含まれるノードをｕｑに対するスコアでランキングすることである。
【００１６】
Ａ∈Ｒｎ×ｎ（Ｒｎ×ｎ：ｎ×ｎ行列集合）をｋ−ＮＮグラフにおける隣接行列としたときに、行列Ａは、対称行列であり、エッジ数がＯ（ｎ）である。２つのノードｕｉ，ｕｊを接続するエッジの重みは、Ａｉｊ＝ｅｘｐ｛−ｄ２（ｕｉ，ｕｊ）／２σ２｝と計算される。ここで、ｄ（ｕｉ，ｕｊ）は、ノードｕｉ，ｕｊの距離関数であり、一般的にはユーグリッド距離が用いられる。σは、一般的には距離関数の関数値の標準偏差が用いられる。ｑは、大きさがｎ×１のベクトルであり、問い合わせノードｕｑに対応する要素ｑｑは１であり、その他の要素は０である。
【００１７】
Manifold  Rankingにおいて、各ノードのスコアは、下記の式（１）で定義されるコスト関数を最小化する最適解として定義される。なお、下記の式（１）における||＊||２は、Ｌ２ノルムである。
【００１８】
【数１】
2015232782.tif 000004
【００１９】
コスト関数ｆ（ｘ）の右辺第１項は、グラフ内で近接するノードは類似するスコアを持つという条件に対応し、右辺第２項は、問い合わせノードｕｑに近いノードほどより高いスコアを持つという条件に対応する。最適なランキングスコアｘ＊は、コスト関数ｆ（ｘ）を最小化するものであり、下記の式（２）に示すコスト関数の微分を０とおいた下記の式（３）から、下記の式（４）のように求まる。
【００２０】
【数２】
2015232782.tif 000005
【００２１】
【数３】
2015232782.tif 000006
【００２２】
【数４】
2015232782.tif 000007
【００２３】
式（４）において、（Ｉ−αＣ−１／２ＡＣ−１／２）−１は、（Ｉ−αＣ−１／２ＡＣ−１／２）の逆行列である。式（４）から、Manifold  Rankingにおけるスコアを計算するには、逆行列の計算が必要であることが分かる。しかし、逆行列の計算は、ｎ×ｎ行列の場合、Ｏ（ｎ３）の計算量を要する。よって、検索の際の計算量が問題となる。
【００２４】
また、この従来手法では、スコアが小さいノードに対しても、式（２）〜（４）の計算を行う必要があるという問題がある。また、この従来手法では、逆行列を保持するために、Ｏ（ｎ２）の記憶領域が必要となるという問題がある。結果として、大規模なデータに対して検索をおこなう際には、膨大な計算量と記憶領域を要することとなる。
【００２５】
［実施形態の数理的背景］
次に、実施形態の数理的背景を説明する。Manifold  Rankingによる検索速度を向上させるために、（ｉ）不完全コレスキー分解から得られた疎行列を用いてスコアの近似を計算し、（ii）不要なスコアの計算を枝刈り（除外）するために、スコアの上限値を計算する。（ｉ）および（ii）の手法は、不完全コレスキー分解から得られた疎行列における非零要素の数はＯ（ｎ）であるため、Ｏ（ｎ３）の計算コストを要する逆行列を用いる場合と比べ大幅に高速に検索できる。
【００２６】
なお、疎行列とは、三角行列、対角行列などのように、大部分の要素が０である行列をいう。
【００２７】
以下、問い合わせノードに対してスコアを近似的に計算する方法について述べる。実施形態では、不完全コレスキー分解を用いてスコアを計算する。先ず、Manifold  Rankingのスコアの定義が、不完全コレスキー分解を用いて書き直せることを示す。
【００２８】
実施形態では、近似の精度を上げるために、ノードを並び変える。ノードの並び変えを行う行列をＰとする。行列Ｐを求める手法は、後述する。また、ノードが並び変えられた行列をＡ´とする。ｋ−ＮＮグラフにおけるｎ×ｎの隣接行列Ａは、行列Ｐを用いて行列Ａ´へ、Ａ＝ＰＡ´ＰＴと変換される。なお、行列ＰＴは、行列Ｐの転置である。
【００２９】
同様に、対角行列Ｃは、Ｃ´＝ＰＣＰＴと変換される。ｕ´ｉを、ノードを並び替えた後の第ｉ番目のノードとする。ｎ×ｎの行列Ｐは、直交行列である。行列Ｐの各行と各列は、それぞれ１つずつ非零の要素を持ち、その他の要素は０である。Ｐｉｊ＝１は、第ｊ番目の行が第ｉ番目の行と入れ替えできることを表す。
【００３０】
この行列Ｐを用いることにより、上記の式（４）で定義されるスコアの計算式は、Ｉ＝ＰＩＰＴであり、ＰＴ＝Ｐ−１であることから、下記の式（５）のように書き換えることができる。
【００３１】
【数５】
2015232782.tif 000008
【００３２】
ここで、行列Ｉ、行列Ｃ´、行列Ａ´は、いずれも対称行列であるので、行列｛Ｉ−α（Ｃ´）−１／２Ａ´（Ｃ´）−１／２｝もまた対称行列である。そのため、実施形態は、行列｛Ｉ−α（Ｃ´）−１／２Ａ´（Ｃ´）−１／２｝を不完全コレスキー分解して、ある近似行列を求める。なお、不完全コレスキー分解とは、対称行列を下三角行列Ｌ、対角行列Ｄ、上三角行列Ｕ（Ｌは実対称行列のため、Ｕ＝ＬＴ）の行列積へ近似分解する手法である。
【００３３】
不完全コレスキー分解により、｛Ｉ−α（Ｃ´）−１／２Ａ´（Ｃ´）−１／２｝＝ＬＤＵ＋Ｎ≒ＬＤＵ＝ＬＤＬＴと計算できる。この式から、近似のスコアは、前進身代入と後進代入を用いて計算できる。ここで、Ｌ´＝ＬＤ、ｑ´＝（１−α）Ｐｑとする。また、ベクトルｘを、近似スコアによるベクトルとし、ｘ´＝Ｐｘとする。すると、式（５）から、Ｕｘ´＝ｙ、Ｌ´ｙ＝ｑ´となる。行列Ｌ´は、下三角行列であるため、大きさがｎ×１であるベクトルｙの要素をＬ´ｙ＝ｑ´に対する前進代入を用いて、下記の式（６）に示すように求めることができる。
【００３４】
【数６】
2015232782.tif 000009
【００３５】
同様に、大きさがｎ×１であるベクトルｘ´の要素は、行列Ｕｘ´＝ｙに対する後進代入を用いて、下記の式（７）に示すように求めることができる。
【００３６】
【数７】
2015232782.tif 000010
【００３７】
前進代入では、先ず、最初の要素ｙ１を求め、ｙ１を用いてｙ２を求めるように、前の要素の値を求め、式（６）に逐次的に代入をおこなっていくことで、最後の要素ｙｎまでの各要素の値を求める。後進代入では、先ず、最後の要素ｘ´ｎを求め、ｘ´ｎを用いてｘ´ｎ−１を求めるように、後の要素の値を求め、式（７）に逐次的に代入をおこなっていくことで、最初の要素ｘ´１までの各要素の値を求める。
【００３８】
行列式Ｐｘ（＝ｘ´）は、ベクトルｘの行が並び替えられたベクトルなので、ノードｕｉの近似スコアｘｉは、ベクトルｘ´の要素から、下記の式（８）のように求められる。
【００３９】
【数８】
2015232782.tif 000011
【００４０】
式（８）は、ベクトルｘ´が、近似のスコアに対応することを示す。すなわち、要素ｘ´ｊは、並び替えをおこなった後のノードｕ´ｊのスコアに対応する。
【００４１】
行列｛Ｉ−α（Ｃ´）−１／２Ａ´（Ｃ´）−１／２｝の不完全コレスキー分解をおこなえば、式（６）〜（８）から、近似のスコアを計算できることが分かる。実施形態における近似のスコアの計算量を示す補助定理１を、図１に示す。補助定理１によれば、近似のスコアを計算するには、Ｏ（ｎ）の計算量が必要である。
【００４２】
実施形態では、不完全コレスキー分解を用いて、｛Ｉ−α（Ｃ´）−１／２Ａ´（Ｃ´）−１／２｝≒ＬＤＵを計算することにより、近似のスコアを求める。以下、近似の精度を向上させるために、グラフのノードを並び替える手法について述べる。実施形態では、不完全コレスキー分解を適用する前にノードの並び替えをおこなう。先ず、ノードの並び替えにより近似の精度を向上させる問題は、ＮＰ完全問題と等価であることを、図２の定理１で示す。
【００４３】
ここで、不完全コレスキー分解が「不完全」である所以を説明する。行列ＷをＷ＝｛Ｉ−α（Ｃ´）−１／２Ａ´（Ｃ´）−１／２｝とすると、行列Ｌ（＝ＵＴ）と、Ｄは、それぞれ下記の式（９）、（１０）のようになる。
【００４４】
【数９】
2015232782.tif 000012
【００４５】
ここで、式（９）から、もし行列Ｗにおける要素が０であれば、対応する行列Ｌにおける要素も０になることが分かる。この「行列Ｌが行列Ｗと同じ疎なパターンを有する」性質が、「不完全」の所以である。“疎なパターン”とは、三角行列、対角行列などを含む、大部分の要素が０である行列の要素配置パターンをいう。
【００４６】
もし「行列Ｌが行列Ｗと同じ疎なパターンを有する」性質がなければ、式（９）、（１０）から正確にスコアの値を計算することは不可能である。この「行列Ｌが行列Ｗと同じ疎なパターンを有する」性質から、不完全コレスキー分解においては、強制的に値が０にされる要素の数が少ないほど、近似の精度の向上が期待できることが分かる。
【００４７】
式（９）、（１０）から、行列Ｌと行列Ｄは、左側の要素から計算されることが分かる。このため、行列Ｗにおける左側の要素が疎であるほど強制的に値が０にされる要素の数が減り、近似の精度の向上が期待できることが分かる。すなわち、ノードを並び替えることにより行列の左側の要素を疎にし、近似の精度を向上させることができる。
【００４８】
ノードを並び替えるＡｌｇｏｒｉｔｈｍ１では、ｋ−ＮＮグラフのデータがクラスタを形成する、すなわちクラスタリング可能であるという性質を用いる。グラフのクラスタリング手法として、例えば一例として「H.Shiokawa，Y.Fujiwara，and  M.Onizuka，”Fast  Algorithm  for  Modularity-based  Graph  Clustering“，AAAI，2013.」を用いることができるが、その他の手法であってもよい。Ａｌｇｏｒｉｔｈｍ１および対応するフローチャートの説明は、図１６および図１８を参照して後述する。
【００４９】
ノードの並び替えをおこなう手法は、近似の精度を上げるためにおこなう以外にも、不要なノードのスコアの計算を枝刈りするというメリットがある。先に述べたとおり、近似のスコアは前進代入と後退代入を用いて計算できるが、前進代入と後退代入のみの手法では、選択したノードのみのスコアを計算することは難しい。これは前進代入と後退代入において先に計算したスコアを代入することで新たにスコアを逐次的に計算するからである。以下、不要なノードのスコアの計算を枝刈りするアプローチについて述べる。
【００５０】
ノードを並び変えた後における問い合わせノードをｕ´ｑとし、ノードｕ´ｑが含まれるクラスタをＣＱ（ノードｕ´ｑがクラスタＣＮに含まれる場合はＣＱ＝ＣＮ）としたときに、実施形態では、図３の補助定理２に示す行列Ｌの性質を用いて枝刈りをおこなう。
【００５１】
図３の補助定理２に示す行列Ｌの性質から、ベクトルｙについて、図４の補助定理３に示す性質が成り立つ。
【００５２】
図４の補助定理３から、ベクトルｙにおける非零要素は、クラスタＣＱとクラスタＣＮに対応する要素のみに限定されることがわかる。この性質を用いてベクトルｙにおける要素を高速に計算することができる。同様に、この性質から近似のスコアに対応するベクトルｘ´について、図５の補助定理４に示す性質が成り立つ。図５の補助定理４から、クラスタＣＮに対応するベクトルｘ´の要素が存在すれば、任意に選択したノードのスコアを計算できることがわかる。
【００５３】
実施形態では、補助定理２〜４を用いて、ベクトルｙにおいて、まずクラスタＣＱとクラスタＣＮに対応する要素を計算し、ベクトルｘ´におけるクラスタＣＮに対応する要素を計算する。クラスタＣＮに対応する要素を用いることにより、任意に選択したクラスタにおける近似のスコアを計算することができる。
【００５４】
実施形態では、高速に検索をおこなうために、解の候補となるノードを、スコアの上限値の推定により求める。スコアの上限値で解の候補となると判定されたときにのみ、近似のスコアを計算することで、高速に検索をおこなうことができる。以下、スコアの上限値の推定方法について述べる。
【００５５】
先に述べたとおり、実施形態は、先ず、クラスタＣＱと、クラスタＣＮに含まれる近似のスコアを計算するため、クラスタＣＱおよびクラスタＣＮ以外のクラスタに含まれるノードに対して、スコアの上限値の推定値を計算する。ノードｕ´ｉに対する、下記の（Ａ）で表される推定値は、図６の定義１のように定義される。
【００５６】
【数１０】
2015232782.tif 000013
【００５７】
なお、下記の（Ｂ）で表される、図６の定義１で定義される２つの上限値は、検索をおこなう前に事前に計算しておくことが可能である。推定値についての性質を述べるための補助定理を示す。
【００５８】
【数１１】
2015232782.tif 000014
【００５９】
図７の補助定理５は、推定値が近似のスコアの上限値になっていることを示す。実施形態は、高速に検索をおこなうため、定義１により各ノードに対してスコアの上限値を推定するのではなく、各クラスタに対してスコアの上限値を推定する。クラスタＣＱおよびクラスタＣＮのいずれのクラスタでもないクラスタＣｉにおける、下記の式（Ｃ）で表されるスコアの上限値の推定値は、図８の定義２のように定義される。
【００６０】
【数１２】
2015232782.tif 000015
【００６１】
そして、上記（Ｃ）で表される、クラスタＣｉにおけるスコアの上限値の推定値は、図９の補助定理６に示す性質を持つ。そして、図９の補助定理６を用いて、検索において不必要なノードを枝刈りする。その結果、検索におけるスコアの上限値の推定値の計算量は、図１０の補助定理７に示すとおりである。
【００６２】
以上の数理的考察から、実施形態における検索の計算量およびメモリ量について、図１１の定理２および図１２の定理３が成り立つ。なお、実施形態は、疎行列を用い、不要なスコア計算を枝刈りするが、図１１の定理２によれば、不要なスコア計算を枝刈りする必要がない場合でも、計算量を削減でき、検索を高速化できることが分かる。
【００６３】
すなわち、実施形態は、ＮＰ完全問題に基づき、従来手法より高い精度の検索結果を得ながら、計算量およびメモリ使用量がＯ（ｎ）と、従来手法より大幅に低減される。また、実施形態は、事前に内部パラメータの設定を要しないパラメータフリーとなり、ユーザがManifold  Rankingによる検索を簡易におこなうことができる。
【００６４】
［実施形態］
上記の数理的議論を踏まえ、以下、本願が開示する検索装置などの実施形態を、図面に基づいて説明する。以下の実施形態は、Manifold  Rankingを用いた、画像をノードとする画像検索において、ｋ−ＮＮグラフ、問い合わせノードｕｑ、解ノードの数ｋを入力とし、Manifold  Rankingによるスコアが上位ｋ個のノードを出力する。なお、以下の実施形態は、一例を示すに過ぎず、本願が開示する技術を限定するものではない。
【００６５】
（検索装置の構成）
図１３は、検索装置の構成の一例を示すブロック図である。実施形態の検索装置１００は、Manifold  Rankingでスコアを計算し、スコアが高い順にｋ個のノードを検索結果として出力する検索装置である。図１３に示すように、検索装置１００は、事前計算部１０、検索部２０を有する。事前計算部１０は、グラフデータＧ＝｛Ｖ，Ｅ｝（Ｖはノード集合、Ｅはエッジ集合）を外部入力とし、三角行列を出力する。検索部２０は、問い合わせノードｕｑおよび検索数ｋを外部入力とし、事前計算部１０からの三角行列を内部入力とし、検索結果としてｋ個のノードを出力する。
【００６６】
（事前計算部の構成）
図１４は、事前計算部の構成の一例を示すブロック図である。事前計算部１０は、ノード並び替え部１１、行列計算部１２を有する。ノード並び替え部１１は、グラフデータＧ＝｛Ｖ，Ｅ｝を外部入力とし、ノード集合Ｖを並び替えるノードの並び替え行列Ｐを計算し、並び替え行列Ｐおよび並び替え行列Ｐにより並び替えられたノード集合Ｖ´を出力する。行列計算部１２は、ノードが並び替えられたグラフデータＧ＝｛Ｖ´，Ｅ｝を内部入力とし、上述の式（９）、（１０）に基づき計算した下三角行列Ｌ、対角行列Ｄ、上三角行列Ｕを出力する。ただし、Ｌ＝ＵＴである。
【００６７】
（検索部の構成）
図１５は、検索部の構成の一例を示すブロック図である。検索部２０は、スコア計算部２１、スコア推定部２２、検索結果保存部２３を有する。スコア計算部２１は、三角行列を事前計算部１０からの入力とし、検索対象のノードＶを検索結果保存部２３からの入力として計算したノードＶのスコアをスコア推定部２２および検索結果保存部２３へ出力する。
【００６８】
スコア推定部２２は、問い合わせノードｕｑおよび検索個数ｋを外部入力とし、スコア計算部２１により計算されたスコアを入力とし、検索結果保存部２３からの検索対象のノードＶを入力として、推定したノードのスコアを検索結果保存部２３へ出力する。
【００６９】
検索結果保存部２３は、スコア推定部２２により推定されたスコアを入力とし、スコア計算部２１により計算されたスコアを入力とし、検索対象のノードを決定し、決定したノードをスコア計算部２１およびスコア推定部２２へ出力し、検索結果を外部へ出力する。
【００７０】
（事前計算処理）
図１６は、事前計算処理を示すフローチャートの一例を示す図である。事前計算処理は、ｋ−ＮＮのグラフデータＧ＝｛Ｖ，Ｅ｝を入力として、ノードＶの並び替え行列Ｐを出力する処理である。
【００７１】
先ず、検索装置１００の事前計算部１０は、外部からの入力として、ｋ−ＮＮグラフの隣接行列Ａの入力を受け付ける（ステップＳ１１）。次に、事前計算部１０は、並び替え行列ＰをＰ＝０と初期化する（ステップＳ１２）。次に、事前計算部１０は、所定のクラスタリング手法により、グラフＧをＮ−１個のクラスタに分割する（ステップＳ１３）。次に、事前計算部１０は、Ｎ個目の空のクラスタＣＮを作成する（ステップＳ１４）。
【００７２】
次に、事前計算部１０は、ｉ＝１，２，・・・，Ｎ−１について、ステップＳ１５〜Ｓ１８のループ処理を実行する。ステップＳ１６では、事前計算部１０は、ｉ番目のクラスタから、他のクラスタへまたがるエッジを持つノードを削除する。次に、ステップＳ１７では、事前計算部１０は、ステップＳ１６で削除したノードを、Ｎ番目のクラスタＣＮへ追加する。事前計算部１０は、ｉ＝１，２，・・・，Ｎ−１についてのステップＳ１５〜Ｓ１８のループ処理が終了すると、ステップＳ１９へ処理を移す。
【００７３】
次に、事前計算部１０は、行インデックスｋをｋ＝１と初期化する（ステップＳ１９）。次に、事前計算部１０は、ｉ＝１，２，・・・，Ｎ（Ｎはクラスタの数）について、ステップＳ２０〜Ｓ２９のループ処理を実行する。ステップＳ２１では、事前計算部１０は、グラフデータＧ＝｛Ｖ，Ｅ｝のノード集合Ｖを並べ代えたノード集合Ｖ´を空集合に初期化する。
【００７４】
次に、事前計算部１０は、ｊ＝１，２，・・・，Ｎｉ（Ｎｉは第ｉ番目のクラスタＣｉにおけるノードの個数）について、ステップＳ２２〜Ｓ２７のループ処理を実行する。ステップＳ２３では、事前計算部１０は、ｕｌ＝ａｒｇ  ｍｉｎ（ｅ（ｕ）｜ｕ∈Ｃｉ＼Ｖ´）により、エッジ数ｅ（ｕ）が最小となるＣｉのノードｕｌを求める。次に、ステップＳ２４では、事前計算部１０は、並び替え行列Ｐのｋｌ成分ＰｋｌをＰｋｌ＝１とする。ただし、ｌは、ステップＳＳ２３で求めたノードｕｌに対応するｌである。
【００７５】
次に、ステップＳ２５では、事前計算部１０は、ステップＳ２３で求めたノードｕｌを、ノード集合Ｖ´に追加する。次に、ステップＳ２６では、事前計算部１０は、行インデックスｋをｋ＝ｋ＋１と１インクリメントする。
【００７６】
事前計算部１０は、ｊ＝１，２，・・・，ＮｉについてのステップＳ２２〜Ｓ２７のループ処理が終了し、ｉ＝１，２，・・・，ＮについてのステップＳ２０〜Ｓ２８のループ処理が終了すると、ステップＳ２９へ処理を移す。ステップＳ２９では、事前計算部１０は、ステップＳ２０〜Ｓ２８のループ処理により求まった並び替え行列ＰおよびグラフデータＧ＝｛Ｖ，Ｅ｝のノード集合Ｖを並べ代えたノード集合Ｖ´を出力する。
【００７７】
（検索処理）
図１７は、検索処理を示すフローチャートの一例を示す図である。先ず、検索部２０は、問い合わせノードｕｑの入力を受け付ける（ステップＳ３１）。次に、検索部２０は、パラメータθ、ｔｏｐ−ｋノード集合Ｋを、それぞれθ＝０、Ｋ＝φと初期化する（ステップＳ３２）。次に、検索部２０は、ｔｏｐ−ｋノード集合Ｋにダミーノードを追加する（ステップＳ３３）。
【００７８】
次に、検索部２０は、問い合わせノードｕｑから、並び替え後のノードｕ´ｑを求める（ステップＳ３４）。次に、検索部２０は、全てのｕ´ｉ∈ＣＱ∪ＣＮについて、ステップＳ３５〜Ｓ３７のループ処理を実行する。ステップＳ３６では、検索部２０は、補助定理３に基づき、ノードｕ´ｉに対応する要素ｙ´ｉを計算する。検索部２０は、全てのｕ´ｉ∈ＣＱ∪ＣＮについてのステップＳ３５〜Ｓ３７のループ処理が終了すると、ステップＳ３８へ処理を移す。
【００７９】
次に、検索部２０は、全てのｕ´ｉ∈ＣＱ∪ＣＮについて、ステップＳ３８〜Ｓ４４のループ処理を実行する。ステップＳ３９では、検索部２０は、補助定理４に基づき、ノードｕ´ｉに対応する要素ｘ´ｉを計算する。次に、ステップＳ４０では、検索部２０は、ステップＳ３９で計算した要素ｘ´ｉがパラメータθ以上であるか否かを判定する。検索部２０は、要素ｘ´ｉがパラメータθ以上である場合にステップＳ４１へ処理を移し、要素ｘ´ｉがパラメータθ未満である場合にステップＳ４３へ処理を移す。
【００８０】
次に、ステップＳ４１では、検索部２０は、ｖ´＝ａｒｇ  ｍｉｎ（ｘ´ｋ｜ｕ´ｋ∈Ｋ）に基づき、ｖ´を計算する。次に、ステップＳ４２では、検索部２０は、ｔｏｐ−ｋノード集合Ｋからｖ´を削除し、ｕ´ｉをｔｏｐ−ｋノード集合Ｋへ追加する。次に、ステップＳ４３では、検索部２０は、θ＝ｍｉｎ（ｘ´ｋ｜ｘ´ｋ∈Ｋ）なる計算式によりθを更新する。検索部２０は、全てのｕ´ｉ∈ＣＱ∪ＣＮについてのステップＳ３８〜Ｓ４４のループ処理が終了すると、ステップＳ４５へ処理を移す。
【００８１】
次に、検索部２０は、全てのＣｉ≠ＣＱ，ＣＮについて、ステップＳ４５〜Ｓ５５のループ処理を実行する。ステップＳ４６では、検索部２０は、図８の定義２で定義される、上述した（Ｃ）で表されるスコアの上限値の推定値を計算する。次に、ステップＳ４７では、検索部２０は、上述した（Ｃ）で表されるスコアの上限値の推定値がパラメータθ以上であるか否かを判定する。検索部２０は、スコアの上限値の推定値がパラメータθ以上である場合にステップＳ４８へ処理を移し、スコアの上限値の推定値がパラメータθ未満である場合にステップＳ５３へ処理を移す。
【００８２】
次に、検索部２０は、全てのｕｊ∈Ｃｉについて、ステップＳ４８〜Ｓ５４のループ処理を実行する。ステップＳ４９では、検索部２０は、補助定理４に基づき、ノードｕ´ｊに対応する要素ｘ´ｊを計算する。次に、ステップＳ５０では、検索部２０は、ステップＳ４９で計算した要素ｘ´ｊがパラメータθ以上であるか否かを判定する。検索部２０は、要素ｘ´ｊがパラメータθ以上である場合にステップＳ５１へ処理を移し、要素ｘ´ｊがパラメータθ未満である場合にステップＳ５３へ処理を移す。
【００８３】
次に、ステップＳ５１では、検索部２０は、ｖ´＝ａｒｇ  ｍｉｎ（ｘ´ｋ｜ｕ´ｋ∈Ｋ）に基づき、ｖ´を計算する。次に、ステップＳ５２では、検索部２０は、ｔｏｐ−ｋノード集合Ｋからｖ´を削除し、ｕ´ｉをｔｏｐ−ｋノード集合Ｋへ追加する。次に、ステップＳ５３では、検索部２０は、θ＝ｍｉｎ（ｘ´ｋ｜ｘ´ｋ∈Ｋ）なる計算式によりθを更新する。検索部２０は、全てのｕ´ｊ∈ＣｉについてのステップＳ４８〜Ｓ５４のループ処理が終了し、全てのＣｉ≠ＣＱ，ＣＮについてのステップＳ４５〜Ｓ５５のループ処理が終了すると、ステップＳ５６へ処理を移す。
【００８４】
次に、検索部２０は、全てのｕ´ｉ∈Ｋについて、ステップＳ５６〜Ｓ５８のループ処理を実行する。ステップＳ５７では、検索部２０は、事前計算部１０のノード並び替え部１１が計算した並び替え行列Ｐを用いて、ノードｕ´ｉを並び替える。検索部２０は、全てのｕ´ｉ∈ＫについてのステップＳ５６〜Ｓ５８のループ処理が終了すると、ステップＳ５９へ処理を移す。ステップＳ５９では、検索部２０は、ｔｏｐ−ｋノード集合Ｋを出力する。
【００８５】
（ノードの並び替えによる最適化処理）
図１８は、ノードの並び替えによる最適化処理のアルゴリズムの一例を示す図である。図１８に示すＡｌｇｏｒｉｔｈｍ１は、図１６に示す事前計算処理を示すフローチャートに対応する。Ａｌｇｏｒｉｔｈｍ１は、ノードを並び替えることにより行列の左側の要素を疎にし、近似の精度を向上させる。ここで、Ｎをクラスタの数とし，Ｎｉを第ｉ番目のクラスタＣｉにおけるノードの個数とし、ｅ（ｕ）をクラスタＣｉ内のノードｕに接続されるエッジの数とする。
【００８６】
Ａｌｇｏｒｉｔｈｍ１では、先ず、行列Ｐを零行列に設定する（１行目）。次に、グラフのクラスタリング手法により、グラフにおけるＮ−１個のクラスタを計算する（第２行目）。このクラスタリング手法では、クラスタ間にまたがるエッジを持つノードは削除し、削除したノードをＮ番目のクラスタＣＮに追加する（３〜７行目）。その結果、クラスタＣＮに含まれるノードは、全てクラスタにまたがるエッジを持つこととなる。すなわち、ｉ＝１，２，・・・，Ｎ−１であるクラスタＣｉに含まれるノードは、クラスタ内のエッジのみしか持たないこととなる。最後に、各クラスタにおいて、エッジが少ない順でノードを選択し、ノードの並び替えを行う（８〜１７行目）。
【００８７】
（ｔｏｐ−ｋ検索処理）
図１９は、ｔｏｐ−ｋ検索処理のアルゴリズムの一例を示す図である。図１９に示すＡｌｇｏｒｉｔｈｍ２は、図１７に示す検索処理を示すフローチャートに対応する。Ａｌｇｏｒｉｔｈｍ２において、パラメータθはｔｏｐ−ｋノード集合Ｋにおいて最も低い近似のスコア、Ｋはｔｏｐ−ｋノード集合とする。Ａｌｇｏｒｉｔｈｍ２において、先ず、θを０に設定し（１行目）、ｔｏｐ−ｋノード集合Ｋに近似のスコアが０であるダミーのノードを追加する（２〜３行目）。次に、問い合わせノードｕｑからノードｕ´ｑを求める（４行目）。ベクトルｙにおいては、クラスタＣＱと、ＣＮに属するノードに対応する要素のみが非零要素になるため（補助定理３）、前進代入を用いてベクトルｙにおける非零要素を計算する（５〜７行目）。
【００８８】
クラスタＣＱに属するノードは解ノードであることが期待され、また、クラスタＣＮに含まれるノードの近似のスコアは、選択されたノードの近似のスコアを計算するために必要であるため（補助定理４）、クラスタＣＱと、クラスタＣＮに属するノードに対して近似のスコアを計算し、解ノードの集合を更新する（８〜１６行目）。そして、各クラスタにおける推定値を計算する（１８行目）。
【００８９】
もし、推定値がθより小さければ、補助定理６から、そのクラスタに含まれる全てのノードの近似のスコアはθより小さくなる。そのため、そのクラスタに含まれるノードに対しては近似のスコアを計算しない。もし、推定値がθ以上であれば、そのクラスタには解ノードが含まれる可能性があるため、そのクラスタに含まれるノードの近似のスコアを計算する（１９〜２９行目）。最後に、解ノードに対して並び替え行列Ｐを用いて並び替えをおこなう前のノード番号を求める（３１〜３３行目）。
【００９０】
（変例）
実施形態は、複数のノードならびにノード間を接続するエッジを含む入力グラフの隣接行列に基づく、各ノードのスコアを算出する行列を、不完全コレスキー分解する。しかし、行列分解は、不完全コレスキー分解に限らず、コレスキー分解、ＬＤＭ分解、ＬＵ分解など、疎行列を含む行列積へ行列を分解する他の分解方法を用いてもよい。
【００９１】
（実施形態の効果）
実施形態は、複数のノードならびにノード間を接続するエッジを含む入力グラフの隣接行列に基づく、各ノードのスコアを算出する行列に対して不完全コレスキー分解をおこなう。そして、実施形態は、問い合わせノードならびに検索数の入力に応じて、行列分解をおこなった行列から求まる問い合わせノードに対するスコアが、上位から検索数以内の解ノードを、複数のノードから選択して出力する。
【００９２】
また、実施形態は、入力グラフを複数のクラスタへ分割し、クラスタごとに、クラスタ内の全ノードに対するスコアの上限値を推定する。そして、実施形態は、問い合わせノードに対するスコアが上位から検索数だけの解ノードを、複数のノードから選択する際に、クラスタごとに推定したスコアの上限値が、解ノードの集合に既に含まれる要素に対応するスコアの最小値（ただし、解ノードの集合が空集合の場合には、０）未満であるクラスタを、解ノードを選択する対象クラスタから除外する。
【００９３】
また、実施形態は、入力グラフを複数のクラスタへ分割し、各クラスタにおいて、接続されるエッジ数が少ない順序でノードを並び替え、ノードの並び替えに応じて求まる行列に基づいてスコアを算出する行列を変換した行列に対して不完全コレスキー分解をおこなう。
【００９４】
よって、実施形態は、Ｏ（ｎ３）の計算量を要する従来手法と比較し、Ｏ（ｎ）の計算量へと計算量を削減できるので、高速に検索処理をおこなうことができる。また、実施形態は、ノードの並び替えをおこなった後に不完全コレスキー分解をおこなった結果に基づくスコアにより検索結果を出力するので、計算量の削減と計算精度のトレードオフの問題を克服し、高精度で上位ｋ個のノードを検索結果として出力できる。また、実施形態は、Ｏ（ｎ２）のメモリ量を要する従来手法と比較し、Ｏ（ｎ）のメモリ量で計算できるので、計算資源の省資源化を図ることができる。また、実施形態は、事前設定を要する内部パラメータを必要としないので、ユーザは、Manifold  Rankingによる検索を簡易に行うことができる。
【００９５】
（実施形態のシステム構成について）
図１３〜１５に示した検索装置１００の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、検索装置１００の機能の分散および統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散または統合して構成することができる。
【００９６】
また、検索装置１００においておこなわれる各処理は、全部または任意の一部が、ＣＰＵ（Central  Processing  Unit）およびＣＰＵにより解析実行されるプログラムにて実現されてもよい。また、検索装置１００においておこなわれる各処理は、ワイヤードロジックによるハードウェアとして実現されてもよい。
【００９７】
また、実施形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともできる。もしくは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上述および図示の処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて適宜変更することができる。
【００９８】
（プログラムについて）
また、実施形態において説明した検索装置１００のＣＰＵなどの制御装置が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。例えば、制御装置が実行する処理をコンピュータが実行可能な言語で記述した検索プログラムを作成することもできる。この場合、コンピュータが検索プログラムを実行することにより、実施形態と同様の効果を得ることができる。さらに、検索プログラムをコンピュータ読み取り可能な記録媒体に記録して、記録媒体に記録された検索プログラムをコンピュータに読み込ませて実行することにより実施形態と同様の処理を実現できる。以下に、図１３〜１５に示した検索装置１００と同様の機能を実現するプログラムを実行するコンピュータの一例を説明する。
【００９９】
図２０は、検索プログラムを実行するコンピュータを示す図である。コンピュータ１０００は、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらは、バス１０８０によって接続される。
【０１００】
図２０に示すように、メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。また、ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０３１に接続される。また、ディスクドライブインタフェース１０４０は、ディスクドライブ１０４１に接続される。ディスクドライブ１０４１には、磁気ディスクや光ディスクなどの着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０は、例えばマウス１０５１、キーボード１０５２に接続される。また、ビデオアダプタ１０６０は、例えばディスプレイ１０６１に接続される。
【０１０１】
ここで、図２０に例示するように、ハードディスクドライブ１０３１は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、検索プログラムは、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、例えばハードディスクドライブ１０３１に記憶される。
【０１０２】
また、実施形態で説明した各種データは、プログラムデータとして、例えばメモリ１０１０やハードディスクドライブ１０３１に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０３１に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出す。そして、ＣＰＵ１０２０が、検索プログラムの各手順を実行する。
【０１０３】
なお、検索プログラムにかかるプログラムモジュール１０９３およびプログラムデータ１０９４は、ハードディスクドライブ１０３１に記憶される場合に限られない。すなわち、プログラムモジュール１０９３およびプログラムデータ１０９４は、着脱可能な記憶媒体に記憶され、ディスクドライブなどを介してＣＰＵ１０２０によって読み出されてもよい。
【０１０４】
検索プログラムにかかるプログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）など）を介して接続された他のコンピュータに記憶されていてもよい。そして、プログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出され、実行されてもよい。
【０１０５】
また、検索プログラムのモジュール分割は、例えば図１３〜１５に示す事前計算部１０、ノード並び替え部１１、行列計算部１２、検索部２０、スコア計算部２１、スコア推定部２２、検索結果保存部２３およびその他の処理を実行する機能部それぞれが実行する処理単位でおこなってもよい。しかし、モジュールの分割および統合は、これに限らず、処理効率や保守性などを考慮し、適宜なされてもよい。
【０１０６】
以上の実施形態ならびにその変形は、本願が開示する技術に含まれると同様に、特許請求の範囲に記載された発明とその均等の範囲に含まれるものである。
【符号の説明】
【０１０７】
１０  事前計算部      
１１  ノード並び替え部
１２  行列計算部    
２０  検索部        
２１  スコア計算部    
２２  スコア推定部    
２３  検索結果保存部
１００  検索装置          
１０００  コンピュータ    
１０１０  メモリ          
１０２０  ＣＰＵ  
【図１】
2015232782.tif 000016
【図２】
2015232782.tif 000017
【図３】
2015232782.tif 000018
【図４】
2015232782.tif 000019
【図５】
2015232782.tif 000020
【図６】
2015232782.tif 000021
【図７】
2015232782.tif 000022
【図８】
2015232782.tif 000023
【図９】
2015232782.tif 000024
【図１０】
2015232782.tif 000025
【図１１】
2015232782.tif 000026
【図１２】
2015232782.tif 000027
【図１３】
2015232782.tif 000028
【図１４】
2015232782.tif 000029
【図１５】
2015232782.tif 000030
【図１６】
2015232782.tif 000031
【図１７】
2015232782.tif 000032
【図１８】
2015232782.tif 000033
【図１９】
2015232782.tif 000034
【図２０】
2015232782.tif 000035