(57)【要約】【課題】ＰＰＲの演算において演算回数を削減することができる。【解決手段】スコア行列作成部２９によって、スコア行列を作成し、ＺＤＤ構築部２２によって、入力された隣接行列に対応する二値行列をＺＤＤに変換すると共に、各ノードの出次数を記憶し、ＰＰＲ計算部３０によって、スコア行列と、入力部１０により入力された複数のパーソナライズドベクトルの集合からなる行列と、ＺＤＤとに基づいて、中間ノードの各々について、スコアベクトルを算出し、行ノードの子ノードのスコアを積演算の結果として、行列を出力し、当該行列を用いてＰＰＲスコアを計算する。【選択図】図１
2014182753.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ個のページ間の関係を表す有向グラフについて求められたＮ行Ｎ列の隣接行列と、Ｋ個のトピックごとに予め用意された各ページの重みを格納したＮ次元のパーソナライズドベクトルを表すＮ行Ｋ列の行列とに基づいて、ＰＰＲ（Personalized PageRank）スコアを表わすＮ行Ｋ列のスコア行列を計算するＰＰＲ演算装置であって、
前記スコア行列の全ての要素を初期化する初期化手段と、
前記隣接行列と、前記初期化手段によって初期化された前記スコア行列、又は前回計算された前記スコア行列との積、及び前記Ｋ個のトピックごとのパーソナライズドベクトルを表す行列の重み付き和を、前記スコア行列として計算するＰＰＲスコア計算手段と、
予め定められた反復終了条件を満たすまで、前記ＰＰＲスコア計算手段による計算を繰り返す反復判定手段と、
を含み、
前記ＰＰＲスコア計算手段は、
前記隣接行列の非ゼロの要素の各々について、前記要素の値を１に置き換えることによって、前記隣接行列に対応する二値行列を作成し、前記作成した二値行列を、値を示す終端ノード、前記二値行列の各行に対応する各行ノード、及び前記二値行列の非ゼロの各要素に対応する各中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）に変換するＺＤＤ構築手段と、
前記ゼロサプレス型二分決定グラフの前記終端ノードから前記行ノードに向かう順序で、前記中間ノードの各々について、Ｋ次元のスコアベクトルを算出するスコア算出手段であって、
算出対象の中間ノードの各々について、前記算出対象の中間ノードの子ノードである各中間ノードに対し既に算出された前記スコアベクトルと、前記算出対象の中間ノードに対応する前記二値行列の要素、乗算すべき前記スコア行列のうちのＫ次元ベクトル、及び前記算出対象の中間ノードに対応する前記隣接行列の要素の積との和を、前記算出対象の中間ノードの前記スコアベクトルとして算出するスコア算出手段を含み、
前記行ノードの各々について、前記行ノードの子ノードである中間ノードに対し前記スコア算出手段により算出された前記スコアベクトルを取得し、前記隣接行列と前記スコア行列との積演算の結果として、Ｎ行Ｋ列の行列を作成し、前記作成された前記Ｎ行Ｋ列の行列、及び前記Ｋ個のトピックごとのパーソナライズドベクトルを表す行列の重み付き和を計算する
ＰＰＲ演算装置。
【請求項２】
前記有向グラフは、前記Ｎ個のページ間のリンク関係を表す有向グラフであって、
前記隣接行列の（ｊ，ｉ）要素は、前記有向グラフのｉ番目のノードを始点、ｊ番目のノードを終点とするエッジが存在する場合に、１／（ｉ番目のノードの出次数）であり、前記有向グラフのｉ番目のノードを始点、ｊ番目のノードを終点とするエッジが存在しない場合に、０である請求項１記載のＰＰＲ演算装置。
【請求項３】
初期化手段と、ＰＰＲスコア計算手段と、反復判定手段と、を含み、Ｎ個のページ間の関係を表すグラフについて求められたＮ行Ｎ列の隣接行列と、Ｋ個のトピックごとに予め用意された各ページの重みを格納したＮ次元のパーソナライズドベクトルを表すＮ行Ｋ列の行列とに基づいて、ＰＰＲ（Personalized PageRank）スコアを表わすＮ行Ｋ列のスコア行列を計算するＰＰＲ演算装置におけるＰＰＲ演算方法であって、
前記初期化手段によって、前記スコア行列の全ての要素を初期化するステップと、
前記ＰＰＲスコア計算手段によって、前記隣接行列と、前記初期化手段によって初期化された前記スコア行列、又は前回計算された前記スコア行列との積、及び前記Ｋ個のトピックごとのパーソナライズドベクトルを表す行列の重み付き和を、前記スコア行列として計算するステップと、
前記反復判定手段によって、予め定められた反復終了条件を満たすまで、前記ＰＰＲスコア計算手段による計算を繰り返すステップと、
を含み、
前記ＰＰＲスコア計算手段によって計算するステップは、
ＺＤＤ構築手段によって、前記隣接行列の非ゼロの要素の各々について、前記要素の値を１に置き換えることによって、前記隣接行列に対応する二値行列を作成し、前記作成した二値行列を、値を示す終端ノード、前記二値行列の各行に対応する各行ノード、及び前記二値行列の非ゼロの各要素に対応する各中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）に変換するステップと、
スコア算出手段によって、前記ゼロサプレス型二分決定グラフの前記終端ノードから前記行ノードに向かう順序で、前記中間ノードの各々について、Ｋ次元のスコアベクトルを算出するステップであって、
前記スコア算出手段によって、算出対象の中間ノードの各々について、前記算出対象の中間ノードの子ノードである各中間ノードに対し既に算出された前記スコアベクトルと、前記算出対象の中間ノードに対応する前記二値行列の要素、乗算すべき前記スコア行列のうちのＫ次元ベクトル、及び前記算出対象の中間ノードに対応する前記隣接行列の要素の積との和を、前記算出対象の中間ノードの前記スコアベクトルとして算出するステップとを含み、
前記行ノードの各々について、前記行ノードの子ノードである中間ノードに対し前記スコア算出手段により算出された前記スコアベクトルを取得し、前記隣接行列と前記スコア行列との積演算の結果として、Ｎ行Ｋ列の行列を作成し、前記作成された前記Ｎ行Ｋ列の行列、及び前記Ｋ個のトピックごとのパーソナライズドベクトルを表す行列の重み付き和を計算する
ＰＰＲ演算方法。
【請求項４】
前記有向グラフは、前記Ｎ個のページ間のリンク関係を表す有向グラフであって、
前記隣接行列の（ｊ，ｉ）要素は、前記有向グラフのｉ番目のノードを始点、ｊ番目のノードを終点とするエッジが存在する場合に、１／（ｉ番目のノードの出次数）であり、前記有向グラフのｉ番目のノードを始点、ｊ番目のノードを終点とするエッジが存在しない場合に、０である請求項３記載のＰＰＲ演算方法。
【請求項５】
コンピュータを、請求項１又は２記載のＰＰＲ演算装置を構成する各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＰＰＲ演算装置、方法、及びプログラムに係り、特に、ＰＰＲ演算を行うＰＰＲ演算装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
Personalized PageRank（以下ＰＰＲ）はグラフの構造をもとに、グラフの各節点の重要さを反映した重み計算するアルゴリズムである。ＰＰＲは、例えばＷｅｂページを対象とした情報検索におけるページの重要度の判定や、推薦システムにおいて推薦するアイテムを決定するためのスコア等に幅広く用いられている。
【０００３】
ＰＰＲを計算するためには、グラフを表現する隣接行列と、スコアを表現する行列との乗算を繰り返す必要がある（非特許文献１）。
【０００４】
また、隣接行列が二値行列の場合には、ゼロサプレス型二分決定グラフ（ＺＤＤ：Zero-suppressed Binary Decision Diagrams）を用いて表現することもできる。ＺＤＤは二分グラフの構造で対象となるデータを表現するデータ構造であり、データを圧縮して表現できることを特徴とする。ある一定の条件の下において、隣接行列をＺＤＤとして表し、ＰＰＲの計算において必要となる乗算をＺＤＤの構造を用いた動的計画法として実行することによって、計算量を減らすことができる（非特許文献２）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Taher H. Haveliwala, “Topic-Sensitive PageRank”, In Proceedings of the 11th World Wide Web conference, 2002.
【非特許文献２】西野正彬，安田宜仁，小林透, “ZDDを用いた効率的な集合拡張の計算”，人工知能学会論文誌 27巻2号p1 − 6, 2011
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、ＰＰＲは大規模なグラフデータを対象として適用されることが多いため、大規模な疎行列である隣接行列とスコアを表現する行列との乗算の繰り返しには、疎行列の非ゼロ要素の数に比例する時間がかかり、大規模なグラフに対しては計算時間が長くなるという問題がある。特に、複数のパーソナライズドベクトルに対してＰＰＲを計算するときには、パーソナライズドベクトルの個数に応じて計算時間がかかるという問題がある。
【０００７】
また、非特許文献２によれば、二値行列のみを対象としているため、ＰＰＲの計算の為に必要となる、列で正規化された隣接行列を、ＺＤＤを用いて表すことが出来ないという問題がある。また、非特許文献２おいては、二値行列とベクトルとの積の計算法は示されているが、行列間の積の計算方法については記載がないことから、直接ＰＰＲの計算に利用することは不可能であるという問題がある。
【０００８】
本発明では、上記問題点を解決するために成されたものであり、ＰＰＲのスコアの演算において必要な演算回数を削減することができるＰＰＲ演算装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、第１の発明に係るＰＰＲ演算装置は、Ｎ個のページ間の関係を表す有向グラフについて求められたＮ行Ｎ列の隣接行列と、Ｋ個のトピックごとに予め用意された各ページの重みを格納したＮ次元のパーソナライズドベクトルを表すＮ行Ｋ列の行列とに基づいて、ＰＰＲ（Personalized PageRank）スコアを表わすＮ行Ｋ列のスコア行列を計算するＰＰＲ演算装置であって、前記スコア行列の全ての要素を初期化する初期化手段と、前記隣接行列と、前記初期化手段によって初期化された前記スコア行列、又は前回計算された前記スコア行列との積、及び前記Ｋ個のトピックごとのパーソナライズドベクトルを表す行列の重み付き和を、前記スコア行列として計算するＰＰＲスコア計算手段と、予め定められた反復終了条件を満たすまで、前記ＰＰＲスコア計算手段による計算を繰り返す反復判定手段と、を含み、前記ＰＰＲスコア計算手段は、前記隣接行列の非ゼロの要素の各々について、前記要素の値を１に置き換えることによって、前記隣接行列に対応する二値行列を作成し、前記作成した二値行列を、値を示す終端ノード、前記二値行列の各行に対応する各行ノード、及び前記二値行列の非ゼロの各要素に対応する各中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）に変換するＺＤＤ構築手段と、前記ゼロサプレス型二分決定グラフの前記終端ノードから前記行ノードに向かう順序で、前記中間ノードの各々について、Ｋ次元のスコアベクトルを算出するスコア算出手段であって、算出対象の中間ノードの各々について、前記算出対象の中間ノードの子ノードである各中間ノードに対し既に算出された前記スコアベクトルと、前記算出対象の中間ノードに対応する前記二値行列の要素、乗算すべき前記スコア行列のうちのＫ次元ベクトル、及び前記算出対象の中間ノードに対応する前記隣接行列の要素の積との和を、前記算出対象の中間ノードの前記スコアベクトルとして算出するスコア算出手段を含み、前記行ノードの各々について、前記行ノードの子ノードである中間ノードに対し前記スコア算出手段により算出された前記スコアベクトルを取得し、前記隣接行列と前記スコア行列との積演算の結果として、Ｎ行Ｋ列の行列を作成し、前記作成された前記Ｎ行Ｋ列の行列、及び前記Ｋ個のトピックごとのパーソナライズドベクトルを表す行列の重み付き和を計算する。
【００１０】
第２の発明に係るＰＰＲ演算方法は、初期化手段と、ＰＰＲスコア計算手段と、反復判定手段と、を含み、Ｎ個のページ間の関係を表すグラフについて求められたＮ行Ｎ列の隣接行列と、Ｋ個のトピックごとに予め用意された各ページの重みを格納したＮ次元のパーソナライズドベクトルを表すＮ行Ｋ列の行列とに基づいて、ＰＰＲ（Personalized PageRank）スコアを表わすＮ行Ｋ列のスコア行列を計算するＰＰＲ演算装置におけるＰＰＲ演算方法であって、前記初期化手段によって、前記スコア行列の全ての要素を初期化するステップと、前記ＰＰＲスコア計算手段によって、前記隣接行列と、前記初期化手段によって初期化された前記スコア行列、又は前回計算された前記スコア行列との積、及び前記Ｋ個のトピックごとのパーソナライズドベクトルを表す行列の重み付き和を、前記スコア行列として計算するステップと、前記反復判定手段によって、予め定められた反復終了条件を満たすまで、前記ＰＰＲスコア計算手段による計算を繰り返すステップと、を含み、前記ＰＰＲスコア計算手段によって計算するステップは、ＺＤＤ構築手段によって、前記隣接行列の非ゼロの要素の各々について、前記要素の値を１に置き換えることによって、前記隣接行列に対応する二値行列を作成し、前記作成した二値行列を、値を示す終端ノード、前記二値行列の各行に対応する各行ノード、及び前記二値行列の非ゼロの各要素に対応する各中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）に変換するステップと、スコア算出手段によって、前記ゼロサプレス型二分決定グラフの前記終端ノードから前記行ノードに向かう順序で、前記中間ノードの各々について、Ｋ次元のスコアベクトルを算出するステップであって、前記スコア算出手段によって、算出対象の中間ノードの各々について、前記算出対象の中間ノードの子ノードである各中間ノードに対し既に算出された前記スコアベクトルと、前記算出対象の中間ノードに対応する前記二値行列の要素、乗算すべき前記スコア行列のうちのＫ次元ベクトル、及び前記算出対象の中間ノードに対応する前記隣接行列の要素の積との和を、前記算出対象の中間ノードの前記スコアベクトルとして算出するステップとを含み、前記行ノードの各々について、前記行ノードの子ノードである中間ノードに対し前記スコア算出手段により算出された前記スコアベクトルを取得し、前記隣接行列と前記スコア行列との積演算の結果として、Ｎ行Ｋ列の行列を作成し、前記作成された前記Ｎ行Ｋ列の行列、及び前記Ｋ個のトピックごとのパーソナライズドベクトルを表す行列の重み付き和を計算する。          
【００１１】
第１の発明及び第２の発明によれば、初期化手段によって、スコア行列の全ての要素を初期化し、ＰＰＲスコア計算手段によって、隣接行列と、初期化されたスコア行列、又は前回計算されたスコア行列との積、及びＫ個のトピックごとのパーソナライズドベクトルを表す行列の重み付き和を、スコア行列として計算し、反復判定手段によって、予め定められた反復終了条件を満たすまで、前記ＰＰＲスコア計算手段による計算を繰り返す。
【００１２】
そして、ＰＰＲスコア計算手段は、ＺＤＤ構築手段によって、隣接行列の非ゼロの要素の各々について、要素の値を１に置き換えることによって、隣接行列に対応する二値行列を作成し、作成した二値行列を、値を示す終端ノード、二値行列の各行に対応する各行ノード、及び二値行列の非ゼロの各要素に対応する各中間ノードを含むゼロサプレス型二分決定グラフに変換し、スコア算出手段によって、ゼロサプレス型二分決定グラフの終端ノードから行ノードに向かう順序で、中間ノードの各々について、Ｋ次元のスコアベクトルを算出するスコア算出手段であって、算出対象の中間ノードの各々について、算出対象の中間ノードの子ノードである各中間ノードに対し既に算出されたスコアベクトルと、算出対象の中間ノードに対応する二値行列の要素、乗算すべきスコア行列のうちのＫ次元ベクトル、及び算出対象の中間ノードに対応する隣接行列の要素の積との和を、算出対象の中間ノードのスコアベクトルとして算出し、行ノードの各々について、行ノードの子ノードである中間ノードに対しスコア算出手段により算出されたスコアベクトルを取得し、隣接行列とスコア行列との積演算の結果として、Ｎ行Ｋ列の行列を作成し、作成されたＮ行Ｋ列の行列、及びＫ個のトピックごとのパーソナライズドベクトルを表す行列の重み付き和を計算する。
【００１３】
このように、本発明によれば、隣接行列と、スコア行列との積の演算において、隣接行列に対応する二値行列をＺＤＤに変換し、隣接行列とスコア行列との積演算を行うことにより、ＰＰＲのスコアの演算において必要な演算回数を削減することができる。
【００１４】
また、本発明において、前記有向グラフは、前記Ｎ個のページ間のリンク関係を表す有向グラフであって、前記隣接行列の（ｊ，ｉ）要素は、前記有向グラフのｉ番目のノードを始点、ｊ番目のノードを終点とするエッジが存在する場合に、１／（ｉ番目のノードの出次数）であり、前記有向グラフのｉ番目のノードを始点、ｊ番目のノードを終点とするエッジが存在しない場合に、０とすることもできる。
【００１５】
また、本発明のプログラムは、コンピュータを、上記のＰＰＲ演算装置を構成する各手段として機能させるためのプログラムである。
【発明の効果】
【００１６】
以上説明したように、本発明のＰＰＲ演算装置、方法、及びプログラムによれば、隣接行列と、スコア行列との積の演算において、隣接行列に対応する二値行列をＺＤＤに変換し、隣接行列とスコア行列との積演算を行うことにより、ＰＰＲのスコアの演算において必要な演算回数を削減することができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施の形態に係るＰＰＲ演算装置の構成を示す概略図である。
【図２】入力される隣接行列の有向グラフの例を示す図である。
【図３】入力された隣接行列の例を示す図である。
【図４】二値行列をＺＤＤへ変換した例を示す図である。
【図５】入力された隣接行列を二値行列に変換した例を示す図である。
【図６】ＺＤＤの簡略表記の例を示す図である。
【図７】ＺＤＤにノードＩＤを割り当てた例を示す図である。
【図８】ＺＤＤの配列表現の例を示す図である。
【図９】ＺＤＤの配列表現と出次数の併記の例を示す図である。
【図１０】中間ノードのスコアベクトルを算出する例を示す図である。
【図１１】本発明の実施の形態に係るＰＰＲ演算装置におけるＰＰＲ演算処理ルーチンを示す図である。
【図１２】本発明の実施の形態に係るＰＰＲ演算装置におけるＰＰＲスコア計算処理ルーチンを示す図である。
【図１３】本発明の実施の形態に係るＰＰＲ演算装置におけるＡＸ（ｔ−１）計算処理ルーチンを示す図である。
【発明を実施するための形態】
【００１８】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１９】
＜ＰＰＲ演算装置の構成＞
本発明の実施の形態に係るＰＰＲ演算装置について説明する。図１に示すように、本発明の実施の形態に係るＰＰＲ演算装置１００は、ＣＰＵと、ＲＡＭと、後述するＰＰＲ演算処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このＰＰＲ演算装置１００は、機能的には図１に示すように入力部１０と、演算部２０と、出力部５０とを備えている。
【００２０】
入力部１０は、キーボードなどの入力装置から、図２に示すようなＰＰＲの計算対象となるＮ個のページ間のリンク関係を示す、ノード数がＮ個の有向グラフを表す図３に示すＮ行Ｎ列の隣接行列Ａと、Ｋ個のトピックごとのパーソナライズドベクトルの集まりで表現されるＮ行Ｋ列の行列Ｕと、を受け付ける。なお、入力部１０は、ネットワーク等を介して外部から入力されたものを受け付けるようにしてもよい。なお、本発明の実施の形態においては、３行３列の隣接行列Ａが入力されたものとして説明する。
【００２１】
ここでパーソナライズドベクトルとは、各ページごとの重みのことをいう。例えば、トピック「news」に関しては、どのようなページが重要であるか、トピック「スポーツ」に関しては、どのようなページが重要であるかをページごとに重みづけした重みからなるベクトルのことをいう。また、パーソナライズドベクトルの各要素の重みづけは、各要素の合計が１となる確率で表わされているものとする。
【００２２】
隣接行列Ａの（ｊ，ｉ）要素Ａｊ，ｉは、対象の有向グラフのｉ番目の節点を始点、ｊ番目の節点を終点とするエッジが存在する場合にＡｊ，ｉ＝１／ｍｉ、存在しない場合にＡｊ，ｉ＝０とする。ここで、ｍｉは節点ｉの出次数とする。
【００２３】
演算部２０は、ＺＤＤ構築部２２と、ＺＤＤ記憶部２４と、スコア配列作成部２６と、配列記憶部２８と、ＰＰＲスコア行列作成部２９と、ＰＰＲ計算部３０と、行列記憶部３２と、を備えている。なお、ＰＰＲスコア行列作成部２９が、初期化手段の一例であり、ＺＤＤ構築部２２及びＰＰＲ計算部３０が、ＰＰＲスコア計算手段、ＺＤＤ構築手段、スコア算出手段、及び反復判定手段の一例である。
【００２４】
ＺＤＤ構築部２２は、入力部１０において受け付けたＮ行Ｎ列の隣接行列Ａを図４に示すようなＺＤＤのデータ構造に変換する。上記の非特許文献２に記載の方法においては、二値行列に対応するＺＤＤの構築方法しか示されていないため、まず、隣接行列Ａの非ゼロの要素の各々について、要素の値を１に置き換えた、隣接行列Ａに対応するＮ行Ｎ列の二値行列Ｄを作成する（図５参照）。当該二値行列をＺＤＤのデータ構造に変換し、有向グラフの各ノードの出次数と併せてＺＤＤ記憶部２４に記憶しておく。ＺＤＤは、０、１の値の各々に対する終端ノード、二値行列Ｄの各行に対応する各行ノード、及び二値行列Ｄの非ゼロの各要素に対応する各中間ノードを含む。図４中のＦは始点ノードへのポインタを示し、ｒで始まるラベルがついた各ノード（行ノード）は二値行列Ｄの各行に対応し、ｅで始まるラベルがついた各ノード（中間ノード）は二値行列Ｄの各列に対応している。中間ノードはすべてＬＯ側のリンクが０終端ノードへつながっているため、これらのＬＯ側のリンクを省略し、図６のように表記する。なお、二値行列ＤをＺＤＤのデータ構造に変換する手法については、上記の非特許文献２に記載の方法を用いればよい。
【００２５】
また、このダイヤグラムを図７のように、終端ノードから始点ノードへ向かって順番にノードＩＤを付し、ノードごとに、ノードＩＤと、ラベルと、ＨＩ側リンクの接続先のノードＩＤと、ＬＯ側リンクの接続先のノードＩＤと、を対応付けた一次元配列で表現し、ＺＤＤ記憶部２４に記憶する。なお、図６及び図７に対応する配列表現を図８左に示し、図８右にＺＤＤの各ノードにノードＩＤを記したものを示す。図８のように、０終端、１終端の２つの終端ノードには、配列番号１、２が割り当てられているとし、配列番号３以降に中間ノードが並び、その後に行ノードが並ぶように構成する。また、図９に示すように、図８の一次元配列に、ＺＤＤのノードに対応する有向グラフのノードの出次数を格納するカラムを設けても良い。
【００２６】
具体的には、入力部１０により受け付けた隣接行列Ａに対応するＮ行Ｎ列の二値行列Ｄを組み合わせ集合として表現し、組み合わせ集合で用いられるシンボルの集合Ｓを、Ｓ＝｛r1,...,rN,e1,...,eN｝とする。ここで、r1,...,rNは、それぞれ各行に対応するシンボルであり、e1,...,eNは、それぞれ各列に対応するシンボルとする。これらのシンボルを用いて、二値行列Ｄに対応する組み合わせ集合Ｚは、下記（１）式として表現し、当該組み合わせ集合をＺＤＤとして構築する。
【００２７】
【数１】
2014182753.tif 000003
【００２８】
ここで、aｇ(l)は、ｇ行目のｆｇのベクトルの成分ｆｇ1,...,ｆｇNのうち、値が１となるl番目の要素の添え字を表す。また、bｇはｆｇ1,...,ｆｇNのうち値が１となる要素の総数である。１≦aｇ（１）＜…＜aｇ（bｇ）≦Ｎを満たす。例えば、図５の二値行列Ｄには、組み合わせ集合{r1e1e3,r2e3,r3e2}が対応する。これをＺＤＤとして表現したものが図４となる。
【００２９】
また、構築されたＺＤＤにはいくつかの特徴がある。まず、ＺＤＤの節点数は、
【００３０】
【数２】
2014182753.tif 000004
【００３１】
以下であり、かつシンボルr1,...,rN対応する節点は、常に高々一つしか出現しないという特徴がある。また、集合中の２つの項について、ある節点の共有による簡約化はe1,...,eNに対応する節点でのみ起きるようになる。各項に含まれるシンボルのうち、順序的に後にくるものがすべて共通な場合にのみ、ＺＤＤにおいて構造の共有が行われるということになる。図４では、図５の二値行列Ｄの１行目に相当する項がr1e1e3、２行目に相当する項がr2e3であり、e3に相当する節点で共有されている。
【００３２】
ＺＤＤ記憶部２４には、ＺＤＤ構築部２２において構築された図９に示すような隣接行列Ａに対応する二値行列ＤのＺＤＤと、ＺＤＤの各ノードに対応する有向グラフの各ノードの出次数とを一次元配列で表現した配列が記憶されている。
【００３３】
スコア配列作成部２６は、計算の途中結果を保持するための一時記憶領域としての、中間ノード各々のスコアを保持するための各要素からなるスコア配列を作成し、配列記憶部２８に記憶する。計算の途中結果を保持するために、中間ノードごとに対応付けられた一時領域が必要であり、各要素がＫ次元ベクトルとすると、中間ノード数分の要素（Ｋ次元ベクトル）からなる１次元配列をスコア配列として作成する。なお、このスコア配列をscoreとする。
【００３４】
ＰＰＲスコア行列作成部２９は、入力されたＫ個のトピックごとのパーソナライズドベクトルの集まりで表現されるＮ行Ｋ列の行列Ｕに対応して、ＰＰＲスコアを格納するためのＮ行Ｋ列のスコア行列Ｘを作成する。スコア行列Ｘは、入力部１０において受け付けたパーソナライズドベクトルを集約した行列Ｕと同様の構成とし、スコア行列Ｘの各要素を１／Ｎの値で初期化し、行列記憶部３２に記憶する。ここで、計算するパーソナライズドベクトルの数をＫとすると、行列Ｕ及び行列Ｘ共にＮ行Ｋ列の実数行列となる。それぞれのｉ列目に対応する列ベクトルをｕｉ、ｘｉとすると、それぞれトピックｉに対するパーソナライズドベクトルと、それに対応するスコアを表している。
【００３５】
ＰＰＲ計算部３０は、入力部１０において受け付けたパーソナライズドベクトルを集約した行列Ｕと、行列記憶部３２に記憶されているスコア行列Ｘと、ＺＤＤ記憶部２４に記憶されている隣接行列Ａを変換した二値行列ＤのＺＤＤと、配列記憶部２８に記憶されているスコア配列と、に基づいて、下記（２）式よりスコア行列Ｘの更新を、予め定めた回数Ｖになるまで、若しくは収束条件を満たすまで繰り返し行い、その結果を出力部５０に出力する。例えば、収束条件として、前回の行列Ｘの各要素との差分の絶対値の総和が一定値以下になった場合に、収束条件を満たすとしてもよい。なお、予め定められた回数の試行の繰り返し、及び収束条件が反復終了条件の一例である。
【００３６】
【数３】
2014182753.tif 000005
【００３７】
ここで、Ｘ（ｔ）はｔ回目のスコア行列Ｘを表す。また、ｃは調整用のパラメータであり、ｃ∈［０，１］を満たす。
【００３８】
行列の積ＡＸ（ｔ−１）の計算は、ＺＤＤ上での動的計画法に基づいて行う。具体的には、ＺＤＤ記憶部２４に記憶されている隣接行列Ａに対応する二値行列ＤのＺＤＤと、行列記憶部３２に記憶されているＰＰＲスコアを格納するスコア行列Ｘとを受け付ける。そして、ＺＤＤ記憶部２４に記憶されている二値行列ＤのＺＤＤの構造を利用して、ノードＩＤが３からの中間ノードの各々について、ノードＩＤの昇順に各中間ノードのスコアベクトルを、隣接行列Ａの対応する要素の値（有向グラフの対応するノードの出次数の逆数）で重みづけを行いながら下記（３）式により算出する。なお、ノードＩＤが１又は２のノードは終端ノードであるので当該ノードのスコアベクトルは、各要素が０のベクトルとする。また、算出したスコアベクトルは、配列記憶部２８に記憶されているスコア配列の当該中間ノードに対応付けられた位置に格納される。図１０に各中間ノードのスコアベクトルの算出例を示す。
【００３９】
【数４】
2014182753.tif 000006
【００４０】
ここで、ｐはノードＩＤの値であり、ｗは、ノードＩＤ＝ｐのノードに対応する有向グラフのノードの出次数の逆数であり、η（ｐ）はノードＩＤ＝ｐのノードのラベルを受け取り、当該ラベルの添え字を返す関数である。例えば、図９を例に示すと、η（３）＝３、η（５）＝１となる。また、Ｘ（ｔ−１）η（ｐ）は、Ｎ行Ｋ列の行列Ｘ（ｔ−１）のη（ｐ）行目の各要素からなるベクトルであり、ノードＩＤ＝ｐのノードに対応する二値行列Ｄの要素と乗算すべき、行列Ｘ（ｔ−１）のうちの各要素からなるベクトルである。また、配列記憶部２８に記憶されているスコア配列から、算出対象の中間ノード（ノードＩＤ＝ｐ）のＨＩ側の子ノードのノードＩＤ＝ＨＩ（ｐ）に対応するスコアベクトルを取得することで、スコアベクトルscore[HI(ｐ)]を取得する。同様に、算出対象の中間ノード（ノードＩＤ＝ｐ）のＬＯ側の子ノードのノードＩＤ＝ＬＯ（ｐ）に対応するスコアベクトルを取得することで、スコアベクトルscore[LO(ｐ)]を取得する。
【００４１】
また、中間ノードの全てのスコアベクトルが算出された場合、下記（４）式によりベクトルＡＸ（１−ｔ）１〜Ｎを求め、ベクトルＡＸ（ｔ−１）１〜Ｎを各行に並べたＮ行Ｋ列の行列ＡＸ（ｔ−１）を作成して、積演算の結果として出力する。
【００４２】
【数５】
2014182753.tif 000007
【００４３】
ここで、上記（４）式は、ラベルｒ１〜ｒＮに対応する行ノードの各々について算出される。そのため、当該行ノードの各々に対応するＡＸ（ｔ−１）η（ｐ）のベクトルは行列ＡＸ（ｔ−１）の各行に該当する。そして、ベクトルＡＸ（ｔ−１）η（ｐ）をメモリ（図示省略）に格納しておき、ラベルｒ１〜ｒＮに対応する全てのノードについてベクトルＡＸ（ｔ−１）η（ｐ）が算出された場合に、ベクトルＡＸ（ｔ−１）η（ｐ）を結合しＮ行Ｋ列の行列ＡＸ（ｔ−１）とする。そして、Ｎ行Ｋ列の行列ＡＸ（ｔ−１）を用いて上記（２）式に従ってスコア行列Ｘ（ｔ）の計算を行う。そしてスコア行列Ｘ（ｔ）の計算が、予め定めた回数Ｖになった場合、若しくは収束条件を満たした場合、その結果を出力部５０に出力する。
【００４４】
＜ＰＰＲ演算装置の作用＞
次に、本発明の実施の形態に係るＰＰＲ演算装置１００の作用について説明する。まず、入力部１０により、隣接行列Ａと、パーソナライズドベクトルの集まりで表現される行列Ｕと、が入力され、ＰＰＲ演算装置１００のＲＯＭに記憶されたプログラムを、ＣＰＵが実行することにより、図１１に示すＰＰＲ演算処理ルーチンが実行される。
【００４５】
まず、ステップＳ１００では、入力部１０により入力された隣接行列Ａ及び行列Ｕを受け付ける。
【００４６】
次に、ステップＳ１０２では、ステップＳ１００において取得した隣接行列Ａを、図５に示すように隣接行列Ａの非ゼロ要素を全て１で置き換えた隣接行列Ａに対応する二値行列Ｄを作成し、二値行列Ｄを０、１の値の各々に対する終端ノード、二値行列Ｄの各行に対応する各行ノード、及び二値行列Ｘの非ゼロの各要素に対応する各中間ノードを含むＺＤＤのデータ構造に変換し、有向グラフの各ノードの出次数と併せてＺＤＤ記憶部２４に記憶する。
【００４７】
次に、ステップＳ１０４では、ステップＳ１０２において構築したＺＤＤと、ステップＳ１００において受け付けた行列Ｕとに基づいて、各要素をＫ次元ベクトルとした、中間ノード数分の要素からなる一次元配列のスコア配列を作成する。
【００４８】
次に、ステップＳ１０５において、ステップＳ１００において受け付けた行列Ｕに基づいて、Ｎ行Ｋ列のＰＰＲスコアを格納するためのスコア行列Ｘを作成し、行列記憶部３２に記憶する。
【００４９】
次に、ステップＳ１０６では、ステップＳ１０２において構築したＺＤＤと、ステップ１００において受け付けた行列Ｕと、行列記憶部３２に記憶されているスコア行列Ｘとに基づいて、ＰＰＲスコアを計算する。
【００５０】
上記ステップＳ１０８は、図１２に示すＰＰＲスコア計算処理ルーチンによって実現される。
【００５１】
まず、ステップＳ２０２では、行列記憶部３２に記憶されているスコア行列Ｘの各要素を１／Ｎで初期化して、スコア行列Ｘ（0）とする。
【００５２】
次に、ステップＳ２０４では、変数ｔに初期値として１を与える。
【００５３】
次に、ステップＳ２０６では、ステップＳ１０２において構築したＺＤＤと、行列記憶部３２に記憶されているスコア行列Ｘとに基づいて、行列ＡＸ（ｔ−１）を計算する。
【００５４】
上記ステップＳ２０６は、図１３に示す行列ＡＸ（ｔ−１）計算処理ルーチンによって実現される。
【００５５】
まず、ステップＳ３００では、変数ｐの初期値として３を与える。
【００５６】
次に、ステップＳ３０２では、ノードＩＤ＝ｐのラベルがＥｏ（ｏ＝１,...,Ｎ）か否かを判定する。ノードＩＤ＝ｐのラベルがＥｏである場合には、ノードＩＤ＝ｐのノードが中間ノードであると判断し、ステップＳ３０４に移行し、ノードＩＤ＝ｐのラベルがＥｏでない場合には、ノードＩＤ＝ｐのノードが行ノードであると判断し、ステップＳ３１０へ移行する。
【００５７】
次に、ステップＳ３０４では、配列記憶部２８に記憶されているスコア配列から、ノードＩＤ＝ｐのノードのＨＩ側の子ノード（中間ノード）のノードＩＤ＝ＨＩ（ｐ）に対応付けられたスコアベクトルscore［ＨＩ（ｐ）］、及びノードＩＤ＝ｐのノードのＬＯ側の子ノード（中間ノード）のノードＩＤ＝ＬＯ（ｐ）に対応付けられたスコアベクトルscore[LO(p)]を取得し、score［ＨＩ（ｐ）］と、score［ＬＯ（ｐ）］と、ＺＤＤ記憶部２４に記憶されている、ノードＩＤ＝ｐのノードに対応する有向グラフのノードの出次数と、ノードＩＤ＝ｐのラベルの添え字η（ｐ）に対応するＸη（ｉ）とに基づいて、上記（３）式に従って、ノードＩＤ＝ｐの中間ノードのスコアベクトルを算出する。
【００５８】
次に、ステップＳ３０６では、変数ｐの値が最大ノード番号Ｙよりも小さいか否かを判定する。変数ｐが最大ノード番号Ｙよりも小さい場合にはステップＳ３０８に移行し、変数ｐの値が最大ノード番号Ｙ未満である場合にはステップＳ３１２に移行する。
【００５９】
次に、ステップＳ３０８では、変数ｐに１を加えた値を変数ｐとする。
【００６０】
次に、ステップＳ３１０では、ノードＩＤ＝ｐの行ノードについて、当該行ノードのＨＩ側の子ノード(中間ノード)のノードＩＤ＝ＨＩ（ｐ）に対応付けてスコア配列に格納されている、当該行ノードのＨＩ側の子ノードのスコアベクトルを取得する。そして、当該行ノードについて、ノードＩＤ＝ｐの当該行ノードのラベルの添え字η（ｐ）を取得し、当該行ノードについて取得したスコアベクトルを、積演算の結果であるＮ行Ｋ列の行列のうちの要素からなるベクトルＡＸ（ｔ−１）η（ｐ）とする。なお、ステップＳ３１０は、全ての行ノードについて繰り返し行われる。
【００６１】
次に、ステップＳ３１２では、ステップＳ３１０において取得したベクトルＡＸ（ｔ−１）１〜Ｎの結果に基づいて、ベクトルＡＸ（ｔ−１）１〜Ｎを各行に並べて生成されるＮ行Ｋ列の行列ＡＸ（ｔ−１）を出力する。
【００６２】
図１２のステップＳ２０８では、ステップＳ３１２において取得した行列ＡＸ（ｔ−１）と、ステップＳ１００において受け付けた行列Ｕとに基づいて、上記（２）式に従って、スコア行列Ｘ（ｔ）を計算する。
【００６３】
次に、ステップＳ２１０では、変数ｔの値が規定繰返し回数Ｖよりも小さいか否かを判定する。変数ｔの値が規定繰返し回数Ｖ未満の場合は、ステップＳ２１２に移行し、変数ｔの値が規定繰返し回数Ｖ以上の場合には、ステップＳ２１４に移行する。
【００６４】
ステップＳ２１２では、変数ｔの値に１を加えた値をｔとする。
【００６５】
次に、ステップＳ２１４では、ステップＳ２１０において取得したＸ（ｔ）をＰＰＲスコアの計算結果として出力部５０に出力し、処理を終了する。
【００６６】
以上説明したように、本発明の実施の形態に係るＰＰＲ演算装置によれば、ＰＰＲスコアの演算のうちの、隣接行列Ａとスコア行列Ｘとの積演算において、隣接行列Ａに対応する二値行列をＺＤＤに変換し、隣接行列Ａとスコア行列Ｘとの積演算を行うことにより、ＰＰＲのスコアの演算において必要な演算回数を削減することができる。
【００６７】
また、Personalized PageRankの計算に必要な演算回数を削減することによって、処理を高速化することができる。
【００６８】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００６９】
例えば、パーソナライズドベクトルが、ある要素だけ１となり他の要素の全てが０となるような単位ベクトルであってもよい。
【符号の説明】
【００７０】
１０   入力部
２０   演算部
２２   ＺＤＤ構築部
２４   ＺＤＤ記憶部
２６   スコア配列作成部
２８   配列記憶部
２９   スコア行列作成部
３０   ＰＰＲ計算部
３２   行列記憶部
３４   配列記憶部
５０   出力部
１００ ＰＰＲ演算装置
【図１】
2014182753.tif 000008
【図２】
2014182753.tif 000009
【図３】
2014182753.tif 000010
【図４】
2014182753.tif 000011
【図５】
2014182753.tif 000012
【図６】
2014182753.tif 000013
【図７】
2014182753.tif 000014
【図８】
2014182753.tif 000015
【図９】
2014182753.tif 000016
【図１０】
2014182753.tif 000017
【図１１】
2014182753.tif 000018
【図１２】
2014182753.tif 000019
【図１３】
2014182753.tif 000020