(57)【要約】  【課題】  数十万乃至数百万のノードの数に対応可能な、スケーラブルなリンク予測技法を提供すること。  【解決手段】  類似度行列ＷZ，ＷY，ＷXが先ず、不完全コレスキー分解などの技法によって、低ランク近似される。次に、類似度行列ＷZ，ＷY，ＷXの低ランク近似行列の固有値分解を行なう。低ランク近似とは、図式的には、１つの行列を、長方形の２つの行列の積で近似することである。ここで低ランク近似化されていることで、固有値分解の計算が容易になっている。次の段階では、得られたＷZ，ＷY，ＷXの低ランク近似行列の固有値を用いて、正規化ラプラシアンＬが構成される。こうして正規化ラプラシアンＬが得られると、ＷZ，ＷY，ＷXの低ランク近似行列のそれぞれの固有ベクトルを並べた行列であるＶ~Z，Ｖ~Y，Ｖ~XとＬを用いて、(σＬ + Ｉ)の部分の逆行列が有利に計算される。(σＬ + Ｉ)の逆行列が求まると、vec(Ｆ) = (σＬ + Ｉ)-1vec(Ｆ*)であることから、Ｆが計算される。【選択図】  図１４
2010250377.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータの処理により、第１のノードの集合のデータと、第２のノードの集合のデータの間のマルチタイプ・リンクを予測するためのシステムであって、
前記コンピュータによってデータを読み書き可能なメモリと、
前記メモリに記憶された前記第１のノードの集合のデータと、
前記メモリに記憶された前記第２のノードの集合のデータと、
前記第１のノードと前記第２のノードの間のマルチタイプ・リンク情報の集合を前記メモリに格納する手段と、
前記マルチタイプ・リンク情報から、前記第１のノードと、前記第２のノードと、その間の３階テンソル教師データを計算する手段と、
前記第１のノードの集合の第１の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算する手段と、
前記第２のノードの集合の第２の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算する手段と、
前記マルチタイプ・リンク情報の集合の第３の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算する手段と、
前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値分解を計算して、その固有値と、固有ベクトルを並べた固有ベクトル行列のデータを求める手段と、
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算する手段と、
前記固有値の値から、３階テンソル・パラメータを計算する手段と、
前記３階テンソル教師データと、前記固有ベクトル行列のクロネッカー積またはクロネッカー和と、前記３階テンソル・パラメータに基づき、マルチタイプ・リンクの予測を計算する手段とを有する、
マルチタイプ・リンク予測システム。
【請求項２】
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算する手段が、クロネッカー積を計算する場合、前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値をそれぞれλX(i),λY(j),λZ(k)とすると、前記３階テンソル・パラメータのi,j,k成分が、λX(i)λY(j)λZ(k)の値に基づき決定される、請求項１のマルチタイプ・リンク予測システム。
【請求項３】
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算する手段が、クロネッカー和を計算する場合、前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値をそれぞれλX(i),λY(j),λZ(k)とすると、前記３階テンソル・パラメータのi,j,k成分が、λX(i)+λY(j)+λZ(k)の値に基づき決定される、請求項１のマルチタイプ・リンク予測システム。
【請求項４】
コンピュータの処理により、第１のノードの集合のデータと、第２のノードの集合のデータの間のマルチタイプ・リンクを予測するための方法であって、
前記コンピュータのメモリに前記第１のノードの集合のデータをロードするステップと、
前記メモリに前記第２のノードの集合のデータをロードするステップと、
前記第１のノードと前記第２のノードの間のマルチタイプ・リンク情報の集合を前記メモリにロードするステップと、
前記マルチタイプ・リンク情報から、前記第１のノードと、前記第２のノードと、その間の３階テンソル教師データを計算するステップと、
前記第１のノードの集合の第１の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算するステップと、
前記第２のノードの集合の第２の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算するステップと、
前記マルチタイプ・リンク情報の集合の第３の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算するステップと、
前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値分解を計算して、その固有値と、固有ベクトルを並べた固有ベクトル行列のデータを求めるステップと、
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算するステップと、
前記固有値の値から、３階テンソル・パラメータを計算するステップと、
前記３階テンソル教師データと、前記固有ベクトル行列のクロネッカー積またはクロネッカー和と、前記３階テンソル・パラメータに基づき、マルチタイプ・リンクの予測を計算するステップとを有する、
マルチタイプ・リンク予測方法。
【請求項５】
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算するステップが、クロネッカー積を計算する場合、前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値をそれぞれλX(i),λY(j),λZ(k)とすると、前記３階テンソル・パラメータのi,j,k成分が、λX(i)λY(j)λZ(k)の値に基づき決定される、請求項４のマルチタイプ・リンク予測方法。
【請求項６】
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算するステップが、クロネッカー和を計算する場合、前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値をそれぞれλX(i),λY(j),λZ(k)とすると、前記３階テンソル・パラメータのi,j,k成分が、λX(i)+λY(j)+λZ(k)の値に基づき決定される、請求項４のマルチタイプ・リンク予測方法。
【請求項７】
コンピュータの処理により、第１のノードの集合のデータと、第２のノードの集合のデータの間のマルチタイプ・リンクを予測するためのプログラムであって、
前記コンピュータに、
前記コンピュータのメモリに前記第１のノードの集合のデータをロードするステップと、
前記メモリに前記第２のノードの集合のデータをロードするステップと、
前記第１のノードと前記第２のノードの間のマルチタイプ・リンク情報の集合を前記メモリにロードするステップと、
前記マルチタイプ・リンク情報から、前記第１のノードと、前記第２のノードと、その間の３階テンソル教師データを計算するステップと、
前記第１のノードの集合の第１の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算するステップと、
前記第２のノードの集合の第２の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算するステップと、
前記マルチタイプ・リンク情報の集合の第３の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算するステップと、
前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値分解を計算して、その固有値と、固有ベクトルを並べた固有ベクトル行列のデータを求めるステップと、
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算するステップと、
前記固有値の値から、３階テンソル・パラメータを計算するステップと、
前記３階テンソル教師データと、前記固有ベクトル行列のクロネッカー積またはクロネッカー和と、前記３階テンソル・パラメータに基づき、マルチタイプ・リンクの予測を計算するステップとを実行させる、
マルチタイプ・リンク予測プログラム。
【請求項８】
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算するステップが、クロネッカー積を計算する場合、前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値をそれぞれλX(i),λY(j),λZ(k)とすると、前記３階テンソル・パラメータのi,j,k成分が、λX(i)λY(j)λZ(k)の値に基づき決定される、請求項７のマルチタイプ・リンク予測プログラム。
【請求項９】
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算するステップが、クロネッカー和を計算する場合、前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値をそれぞれλX(i),λY(j),λZ(k)とすると、前記３階テンソル・パラメータのi,j,k成分が、λX(i)+λY(j)+λZ(k)の値に基づき決定される、請求項７のマルチタイプ・リンク予測プログラム。
【請求項１０】
コンピュータの処理により、第１のノードの集合のデータと、第２のノードの集合のデータの間のマルチタイプ・リンクを予測するためのシステムであって、
前記コンピュータによってデータを読み書き可能なメモリと、
前記メモリに記憶された前記第１のノードの集合のデータと、
前記メモリに記憶された前記第２のノードの集合のデータと、
前記第１のノードと前記第２のノードの間のマルチタイプ・リンク情報の集合を前記メモリに格納する手段と、
前記マルチタイプ・リンク情報から、前記第１のノードと、前記第２のノードと、その間の３階テンソル教師データを計算する手段と、
前記第１のノードの集合の第１の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算する手段と、
前記第２のノードの集合の第２の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算する手段と、
前記マルチタイプ・リンク情報の集合の第３の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算する手段と、
前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列の低ランク近似分解を求める手段と、
前記低ランク近似分解の転置行列の固有値分解を求める手段と、
前記固有値分解を用いて、前記低ランク近似分解のその固有値と、固有ベクトルを並べた固有ベクトル行列のデータを求める手段と、
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算する手段と、
前記固有値の値から、３階テンソル・パラメータを計算する手段と、
前記３階テンソル教師データと、前記固有ベクトル行列のクロネッカー積またはクロネッカー和と、前記３階テンソル・パラメータに基づき、マルチタイプ・リンクの予測を計算する手段とを有する、
マルチタイプ・リンク予測システム。
【請求項１１】
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算する手段が、クロネッカー積を計算する場合、前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値をそれぞれλX(i),λY(j),λZ(k)とすると、前記３階テンソル・パラメータのi,j,k成分が、λX(i)λY(j)λZ(k)の値に基づき決定される、請求項１０のマルチタイプ・リンク予測システム。
【請求項１２】
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算する手段が、クロネッカー和を計算する場合、前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値をそれぞれλX(i),λY(j),λZ(k)とすると、前記３階テンソル・パラメータのi,j,k成分が、λX(i)+λY(j)+λZ(k)の値に基づき決定される、請求項１０のマルチタイプ・リンク予測システム。
【請求項１３】
コンピュータの処理により、第１のノードの集合のデータと、第２のノードの集合のデータの間のマルチタイプ・リンクを予測するための方法であって、
前記コンピュータのメモリに前記第１のノードの集合のデータをロードするステップと、
前記メモリに前記第２のノードの集合のデータをロードするステップと、
前記第１のノードと前記第２のノードの間のマルチタイプ・リンク情報の集合を前記メモリにロードするステップと、
前記マルチタイプ・リンク情報から、前記第１のノードと、前記第２のノードと、その間の３階テンソル教師データを計算するステップと、
前記第１のノードの集合の第１の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算するステップと、
前記第２のノードの集合の第２の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算するステップと、
前記マルチタイプ・リンク情報の集合の第３の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算するステップと、
前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列の低ランク近似分解を求めるステップと、
前記低ランク近似分解の転置行列の固有値分解を求めるステップと、
前記固有値分解を用いて、前記低ランク近似分解のその固有値と、固有ベクトルを並べた固有ベクトル行列のデータを求めるステップと、
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算するステップと、
前記固有値の値から、３階テンソル・パラメータを計算するステップと、
前記３階テンソル教師データと、前記固有ベクトル行列のクロネッカー積またはクロネッカー和と、前記３階テンソル・パラメータに基づき、マルチタイプ・リンクの予測を計算するステップとを有する、
マルチタイプ・リンク予測方法。
【請求項１４】
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算するステップが、クロネッカー積を計算する場合、前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値をそれぞれλX(i),λY(j),λZ(k)とすると、前記３階テンソル・パラメータのi,j,k成分が、λX(i)λY(j)λZ(k)の値に基づき決定される、請求項１３のマルチタイプ・リンク予測方法。
【請求項１５】
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算するステップが、クロネッカー和を計算する場合、前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値をそれぞれλX(i),λY(j),λZ(k)とすると、前記３階テンソル・パラメータのi,j,k成分が、λX(i)+λY(j)+λZ(k)の値に基づき決定される、請求項１３のマルチタイプ・リンク予測方法。
【請求項１６】
コンピュータの処理により、第１のノードの集合のデータと、第２のノードの集合のデータの間のマルチタイプ・リンクを予測するためのプログラムであって、
前記コンピュータに、
前記コンピュータのメモリに前記第１のノードの集合のデータをロードするステップと、
前記メモリに前記第２のノードの集合のデータをロードするステップと、
前記第１のノードと前記第２のノードの間のマルチタイプ・リンク情報の集合を前記メモリにロードするステップと、
前記マルチタイプ・リンク情報から、前記第１のノードと、前記第２のノードと、その間の３階テンソル教師データを計算するステップと、
前記第１のノードの集合の第１の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算するステップと、
前記第２のノードの集合の第２の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算するステップと、
前記マルチタイプ・リンク情報の集合の第３の類似度行列のデータを、その対角成分が１、または所定の値に正規化されるように計算するステップと、
前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列の低ランク近似分解を求めるステップと、
前記低ランク近似分解の転置行列の固有値分解を求めるステップと、
前記固有値分解を用いて、前記低ランク近似分解のその固有値と、固有ベクトルを並べた固有ベクトル行列のデータを求めるステップと、
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算するステップと、
前記固有値の値から、３階テンソル・パラメータを計算するステップと、
前記３階テンソル教師データと、前記固有ベクトル行列のクロネッカー積またはクロネッカー和と、前記３階テンソル・パラメータに基づき、マルチタイプ・リンクの予測を計算するステップとを実行させる、
マルチタイプ・リンク予測プログラム。
【請求項１７】
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算するステップが、クロネッカー積を計算する場合、前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値をそれぞれλX(i),λY(j),λZ(k)とすると、前記３階テンソル・パラメータのi,j,k成分が、λX(i)λY(j)λZ(k)の値に基づき決定される、請求項１６のマルチタイプ・リンク予測プログラム。
【請求項１８】
前記固有ベクトル行列のクロネッカー積またはクロネッカー和を計算するステップが、クロネッカー和を計算する場合、前記第１の類似度行列と、前記第２の類似度行列と、前記第３の類似度行列のそれぞれの固有値をそれぞれλX(i),λY(j),λZ(k)とすると、前記３階テンソル・パラメータのi,j,k成分が、λX(i)+λY(j)+λZ(k)の値に基づき決定される、請求項１６のマルチタイプ・リンク予測プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の対象の間のリンクを予測するための技術に関するものである。ここでいうリンクとは、例えば、対象の間の関係の強さである。
【背景技術】
【０００２】
従来より、複数の対象、または、エンティティの間のリンク、あるいは関係の強さを予測したいという要望がある。例えば、ユーザと商品の間の購買関係を予測する、協調フィルタリングという技術があり、本出願人に係る、特開２０００−１４８８６４号などに記載されている。
【０００３】
あるいは、異なるタンパク質の間の相互作用の有無を予測する、生体ネットワーク予測と呼ばれる分野も知られている。
【０００４】
これらは例えば、いくつかの対象物の間のペアについて、正解が与えられており、これらの値に基づき、正解未知のペアについてリンクを強さを予測する、いわゆる教師つき学習として、コンピュータ・システムによって解かれていた。
【０００５】
その後、対象物のペアの間の単一のリンクではなく、複数種類のリンク、すなわち、マルチタイプ・リンクを考慮したモデルも提案されてきた。例えば、協調フィルタリングにおいては、対象物のペアの間の購買関係だけでなく、評価、商品情報の閲覧なども考慮する、という次第である。
【０００６】
同様に、生体ネットワーク予測では、作用の種類や、作用が起こる環境などの複数種類のリンクが考えられる。このようなマルチタイプ・リンクの予測を実現するためには、コンピュータの処理が複雑になる。
【０００７】
ところで、ソーシャル・ネットワーク・サービス（ＳＮＳ）を運営する会社や、ブログを運営する会社は、一般的に、数十万人から数百万人のユーザを抱え、そのユーザ間の活動のログが、システムのサーバに蓄積される。
【０００８】
そのログに記録される活動としては、ブログを読む、ブログを書く、コメントを入れる、ブログをブックマークに登録する、他のユーザと友達になる、有名人のブログのサポーターになる、などがある。
【０００９】
本出願人に係る、特願２００７−３３６９１９号明細書には、ＳＮＳのようなオンライン・コミュニティにおいて、ブログを書く、ニュースを読む、メッセージを読むなどの複数の行動の指標を統一的に扱うことを可能とする行動マトリックスり概念が記載されている。
【００１０】
そこで、それらの情報が記録されたログに基づき、ユーザが読んだ、コメントしたデータから、有名人のブログを推薦したいとか、ユーザが気に入ったプログのデータから、有名人のブログを推薦したいとか、有名人のブログに関わる活動から、有名人へのファン度を測りたいなどの要望が出てきている。
【００１１】
これは、ある意味、マルチタイプ・リンクの予測の問題に帰着される。ところが、ＳＮＳやブログ・サイトの場合、ユーザの数が数十万人から数百万人と膨大で、協調フィルタリングや生体ネットワーク予測で使われている一般のアルゴリズムがＳＮＳやブログ・サイトの規模に十分にスケーラブルでない、という問題がある。
【００１２】
ところで、従来より、機械学習に基づくリンク予測問題へのアプローチが知られているが、これは、(1) 任意の２構成要素、または，エンティティ間のリンクの有無の予測を行う、ペアワイズ予測モデルと、(2) ネットワーク構造全体のモデルである、関係ネットワークモデルとがある。
【００１３】
ペアワイズ予測モデルの方が、通常の教師付き予測の枠組みに帰着できるため、比較的大きな問題が扱いやすいという利点がある。そこで、本願発明者のうちの一人を含む複数の研究者は、ペアワイズ予測モデルにおいて、ペアワイズ特徴ベース推論を用いて、手法を開発した。
【００１４】
この手法は、(a) 半教師付き予測のリンク予測方法であること、(b) マルチタイプリンクの同時予測であること、(c) ノード類似度行列のクロネッカー積またはクロネッカー和をもちいた新規なペアワイズ類似を利用すること、(d) 共役勾配法により高速に計算可能な可能であること、を特徴とする。
【００１５】
この手法では、（ノード、ノード、リンクタイプ）の３つの組のラベルについて、組の第１ノード集合をＸ、組の第２ノード集合をＹ、そして、組のリンクタイプの集合をＺとする場合、「類似したノード同士は、同じラベル（性質）をもつ可能性が高い」という仮説をもとに推論を行う。このリンク伝播原理に基づく推論を、最適化問題の目的関数として表現し、適当な変数で偏微分してゼロとおくと、解くべき式は、次のようになる。
(σＬ + Ｉ)vec(Ｆ) = vec(Ｆ*)  ・・・式１
【００１６】
ここで、σは、例えば0,01のような小さい実数
Ｌは、ラプラシアン行列で、Ｌ ≡ Ｄ - Ｗ
ここでＷは、３つ組の集合Ｘ、Ｙ、Ｚの間の類似度行列ＷZ，ＷY，ＷXのクロネッカー積またはクロネッカー和
Ｄは、ＤZ，ＤY，ＤXのクロネッカー積またはクロネッカー和で、ＤZ，ＤY，ＤXはそれぞれ、ＷZ，ＷY，ＷXの各行の和を対角成分にもつような対角行列
Ｉは、所定のサイズの単位行列
Ｆ*は、その一部に既知の関係を含む、（ノード、ノード、リンクタイプ）の３つの組を成分にもつ３階テンソル
Ｆは、Ｆ*と同じ形をしていて、計算結果の値が格納される未知数の３階テンソルである。
【００１７】
この手法では、式１は共役勾配法を用いて解かれる。
【００１８】
以上のより詳細な議論は、人工知能学会 第73回 人工知能基本問題研究会 2009年3月13日の、リンク伝播：リンク予測のための半教師付き学習法というトピックで発表され、また予稿集として配布された資料に記述されている。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】特願２００７−３３６９１９号明細書
【非特許文献】
【００２０】
【非特許文献１】人工知能学会 第73回 人工知能基本問題研究会 2009年3月13日配布の予稿集における、鹿島久嗣、加藤毅、山西芳裕、杉山将、津田宏治  「リンク伝播：リンク予測のための半教師付き学習法」と題する発表と、配布された予稿集の論文
【発明の概要】
【発明が解決しようとする課題】
【００２１】
上記論文で提案された手法によって、マルチタイプ・リンク予測問題が、従来よりも高速に解けるようになったが、スケーラビリティの点で、十分でないことが分かった。すなわち、試算によると、上記論文で提案された手法では、リンクタイプが１種類の場合、一方のノード集合ＸのサイズをM、他方のノード集合ＹのサイズをNとしたとき、計算量は、
O(M3N2+M2N3)のオーダーであり、計算のために確保しなくてはならないコンピュータのメモリ量は、O(MN)のオーダーである。すると、ＳＮＳやブログ・サイトなどのように、ユーザの数や文書数が数十万から数百万に亘る場合、リンク予測を行なうことが困難になってくる。
【００２２】
従って、この発明の目的は、ＳＮＳやブログ・サイトなどのように、莫大な数のオブジェクトをもつ集合に対して、コンピュータにより、スケーラブルにリンク予測を行なうことを可能とする手法を提供することにある。
【課題を解決するための手段】
【００２３】
上記目的を達成するため、本願発明は、上記の式１、すなわち、
(σＬ + Ｉ)vec(Ｆ) = vec(Ｆ*)から出発し、正規化ラプラシアン行列Ｌは、クロネッカー積の場合、以下の形式で
【数１】
2010250377.tif 000003
そして、クロネッカー和の場合、以下の形式で
【数２】
2010250377.tif 000004
で表されることを仮定する。ここで、
DZ-1/2ＷZDZ-1/2、DY-1/2ＷYDY-1/2、DX-1/2ＷXDX-1/2は、それぞれ一般性を失うことなく表記の簡略化のため新しい行列ＷZ、ＷY、WXとみなすことができることから、本願発明では以降ラプラシアン行列Ｌを以下の一般形式で表すことにする。
【数３】
2010250377.tif 000005
ただし、演算子は下記の数６の通りで、クロネッカー積とクロネッカー和は統一的に記述される。また、クロネッカー積の場合、c=1.0で、クロネッカー和の場合、c=3.0となるが、cの値は演算子によらず、データから学習して、最適な値を効率的に求めることも可能である。
【００２４】
本願発明の１つの側面によれば、式１を、多数のオブジェクトをもつ集合に対してもスケーラブルに解くことを可能とする、厳密解を得るための、コンピュータの処理によって実施される手法が提供される。
【００２５】
この手法では、最初に、類似度行列ＷZ，ＷY，ＷXがそれぞれ固有値分解される。
【００２６】
次の段階では、得られたＷZ，ＷY，ＷXの固有値を用いて、行列Ｌが構成される。ＷZ，ＷY，ＷXがクロネッカー積である場合と、クロネッカー和である場合とで、行列Ｌを構成する式は異なる。
【００２７】
こうして行列Ｌが得られると、ＷZ，ＷY，ＷXのそれぞれの固有ベクトルを並べた行列であるＶZ，ＶY，ＶXとＬを用いて、(σＬ + Ｉ)の部分の逆行列が有利に計算される。(σＬ + Ｉ)の逆行列が求まると、
vec(Ｆ) = (σＬ + Ｉ)-1vec(Ｆ*)であることから、Ｆが計算される。この厳密解では、計算量のオーダーは、O(M3+N3)であり、上述の手法のO(M3N2+M2N3)よりも、実質的に計算量は低減される。
【００２８】
この発明の第２の側面によれば、上記厳密解の精度をあまり犠牲にすることなく、より少ない計算量と、コンピュータのメモリ量で済む、コンピュータの処理によって近似解をもとめる手法が提供される。
【００２９】
この手法では、類似度行列ＷZ，ＷY，ＷXが先ず、不完全コレスキー分解などの技法によって、低ランク近似される。また、この手法では、最終的な解の一歩手前の解をコンパクトにコンピュータのメモリに保持しておくことで、大きい解の必要な部分を、オンデマンドで高速に取ってくることが可能となる。
【００３０】
次に、類似度行列ＷZ，ＷY，ＷXの低ランク近似行列の固有値分解を行なう。低ランク近似とは、図式的には、１つの行列を、長方形の２つの行列の積で近似することである。ここで低ランク近似化されていることで、固有値分解の計算が容易になっている。
【００３１】
次の段階では、得られたＷZ，ＷY，ＷXの低ランク近似行列の固有値を用いて、行列Ｌ~が構成される。ＷZ，ＷY，ＷXがクロネッカー積である場合と、クロネッカー和である場合とで、行列Ｌ~を構成する式は異なる。
【００３２】
こうして行列Ｌ~が得られると、ＷZ，ＷY，ＷXの低ランク近似行列のそれぞれの固有ベクトルを並べた行列であるＶ~Z，Ｖ~Y，Ｖ~XとＬ~を用いて、(σＬ~ + Ｉ)の部分の逆行列が有利に計算される。(σＬ~ + Ｉ)の逆行列が求まると、
vec(Ｆ) = (σＬ~ + Ｉ)-1vec(Ｆ*)であることから、Ｆが計算される。
【００３３】
この近似解の場合、リンクタイプが１種類とすると、ＷXの長方形行列分解の短い方のサイズをdM、ＷYの長方形行列分解の短い方のサイズをdNとすると、
計算量は、O(MdM2 + NdN2 + dM3 + dN3)
メモリは、O(NdM + MdN + dM2 + dN2)
のように、低減される。
【００３４】
基本的には、dM,dNは、リンクの予測精度を所望に保つ範囲で、dM << M, dN << Nとなるように選ばれる。
【発明の効果】
【００３５】
本発明によれば、計算量とコンピュータの必要なメモリ・サイズを大幅に削減して、数十万乃至数百万のノードの数に対応可能な、スケーラブルなリンク予測技法が提供され、ＳＮＳ、ブログ・サイトなどのオンライン・コミュニティ・システムへのリンク予測技法の応用への途が拓かれる。
【図面の簡単な説明】
【００３６】
【図１】オンライン・コミュニティ・サーバに、インターネットを介して、クライアント・コンピュータが接続されることを示す図である。
【図２】クライアント・コンピュータのハードウェア構成を示す図である。
【図３】オンライン・コミュニティ・サーバのハードウェア構成を示す図である。
【図４】本発明の実施例の機能論理ブロック図である。
【図５】２つの集合の間のリンクの例を示す図である。
【図６】ユーザ情報の例を示す図である。
【図７】本発明の処理の全体の処理の概要フローチャートを示す図である。
【図８】パラメータを設定処理のフローチャートを示す図である。
【図９】類似度行列の例を示す図である。
【図１０】類似度行列の例を示す図である。
【図１１】類似度行列の例を示す図である。
【図１２】リンク予測の方程式を解く処理のフローチャートである。
【図１３】リンク予測の厳密解を求める処理のフローチャートである。
【図１４】リンク予測の近似解を求める処理のフローチャートである。
【発明を実施するための形態】
【００３７】
以下、図面を参照して、本発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。また、以下で説明するのは、本発明をオンライン・コミュニティ・システム上で使用する実施例であるが、これは本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はなく、協調フィルタリング、生体ネットワーク予測など、任意の対象の間のリンク予測を行なう用途な使用可能であることを理解されたい。
【００３８】
図１において、オンライン・コミュニティ・サーバ１０２には、インターネット１０４を介して、複数のクライアント・コンピュータ１０６ａ、１０６ｂ・・・１０６ｚが接続されている。図１のシステムにおいては、クライアント・コンピュータのユーザは、Ｗｅｂブラウザを通じて、インターネット１０４の回線を介して、オンライン・コミュニティ・サーバ１０２に、ログインする。具体的には、所定のＵＲＬをＷｅｂブラウザに打ち込んで、所定のページを表示する。なお、Ｗｅｂブラウザではなく、所定の専用クライアント・アプリケーション・プログラムを使ってログインするようにしてもよい。
【００３９】
ログインに当たっては、クライアント・コンピュータのユーザは、与えられたユーザＩＤと、それに関連付けられたパスワードを用いる。クライアント・コンピュータのユーザは、一旦ログインすると、オンライン・コミュニティ内で、日記を書いたり、アクセスを許可されている他人の日記を閲覧してコメントを書いたり、ニュースを見たり、気の合った仲間同士でグループを作成したり、チャットしたり、趣味のコミュニティを検索したり、などの活動を行う。
【００４０】
次に、図２を参照して、図１で参照番号１０６ａ、１０６ｂ・・・１０６ｚのように示されているクライアント・コンピュータのハードウェア・ブロック図について、説明する。図２において、クライアント・コンピュータは、メイン・メモリ２０６、ＣＰＵ２０４、ＩＤＥコントローラ２０８をもち、これらは、バス２０２に接続されている。バス２０２には更に、ディスプレイ・コントローラ２１４と、通信インターフェース２１８と、ＵＳＢインターフェース２２０と、オーディオ・インターフェース２２２と、キーボード・マウス・コントローラ２２８が接続されている。ＩＤＥコントローラ２０８には、ハードディスク・ドライブ（ＨＤＤ）２１０と、ＤＶＤドライブ２１２が接続されている。ＤＶＤドライブ２１２は、必要に応じて、ＣＤ−ＲＯＭやＤＶＤから、プログラムを導入するために使用する。ディスプレイ・コントローラ２１４には、好適には、ＬＣＤ画面をもつディスプレイ装置２１６が接続されている。ディスプレイ装置２１６には、Ｗｅｂブラウザを通じて、オンライン・コミュニティの画面が表示される。
【００４１】
ＵＳＢインターフェース２２０には、必要に応じて、専用コントローラ、加速度センサ・デバイスなどのデバイスを接続をすることができる。これらのデバイスは、オンライン・コミュニティ内での操作性を向上するために使用することができる。
【００４２】
キーボード・マウス・コントローラ２２８には、キーボード２３０と、マウス２３２が接続されている。キーボード２３０は、典型的には、オンライン・コミュニティ内で、チャットのメッセージを書いたり、検索したいコミュニティ内容を記述したするために使用される。マウス２３２は、オンライン・コミュニティ内で、リンクをクリックしてニュースを読んだり、メニューから動作を選択し実行したり、読みたい日記を選んだりするために使用される。
【００４３】
ＣＰＵ２０４は、例えば、３２ビット・アーキテクチャまたは６４ビット・アーキテクチャに基づく任意のものでよく、インテル社のＰｅｎｔｉｕｍ（インテル・コーポレーションの商標）４、Ｃｏｒｅ（商標）２  Ｄｕｏ、ＡＭＤ社のＡｔｈｌｏｎ（商標）などを使用することができる。
【００４４】
ハードディスク・ドライブ２１０には、少なくとも、オペレーティング・システムと、オペレーティング・システム上で動作するＷｅｂブラウザ（図示しない）が格納されており、システムの起動時に、オペレーティング・システムは、メインメモリ２０６にロードされる。オペレーティング・システムは、Ｗｉｎｄｏｗｓ  ＸＰ（マイクロソフト・コーポレーションの商標）、Ｗｉｎｄｏｗｓ  Ｖｉｓｔａ（マイクロソフト・コーポレーションの商標）、Ｌｉｎｕｘ（Linus Torvaldsの商標）などを使用することができる。
【００４５】
通信インターフェース２１８は、オペレーティング・システムが提供するＴＣＰ／ＩＰ通信機能を利用して、イーサネット（商標）・プロトコルなどにより、オンライン・コミュニティ・サーバ１０２と、通信する。
【００４６】
図３は、オンライン・コミュニティ・プロバイダ側のハードウェア構成の概要ブロック図である。図３に示すように、クライアント・コンピュータ１０６ａ、１０６ｂ・・・１０６ｚは、インターネット１０４を経由して、オンライン・コミュニティ・サーバ１０２の通信インターフェース３０２に接続される。通信インターフェース３０２はさらに、バス３０４に接続され、バス３０４には、ＣＰＵ３０６、主記憶（ＲＡＭ）３０８、及びハードディスク・ドライブ（ＨＤＤ）３１０が接続されている。
【００４７】
図示しないが、オンライン・コミュニティ・サーバ１０２にはさらに、キーボード、マウス、及びディスプレイが接続され、これらによって、オンライン・コミュニティ・サーバ１０２全体の管理やメンテナンス作業を行うようにしてもよい。
【００４８】
オンライン・コミュニティ・サーバ１０２のハードディスク・ドライブ３１０には、オペレーティング・システム、クライアント・コンピュータクライアント・コンピュータ１０６ａ、１０６ｂ・・・１０６ｚのログイン管理のための、ユーザＩＤとパスワードの対応テーブルが保存されている。ハードディスク・ドライブ３１０にはさらに、オンライン・コミュニティ・サーバ１０２をＷｅｂサーバとして機能させるためのＡｐａｃｈｅなどのソフトウェアが保存され、オンライン・コミュニティ・サーバ１０２の立ち上げ時に、主記憶３０８にロードされて、動作する。これによって、クライアント・コンピュータ１０６ａ、１０６ｂ・・・１０６ｚが、ＴＣＰ／ＩＰのプロトコルで、オンライン・コミュニティ・サーバ１０２にアクセスすることが可能となる。
【００４９】
オンライン・コミュニティ・サーバ１０２のハードディスク・ドライブ３１０にはさらに、このオンライン・コミュニティ・サービスの各ユーザのメッセージ、日記またはブログ、掲示板などの情報と、オンライン・コミュニティ・サービスの情報が、好適には、ＨＴＭＬファイルと、グラフィック・イメージ、動画ファイル、音楽ファイルなどのマルチメディア形式で、保存されている。
【００５０】
日記またはブログ、及び掲示板には、当該ユーザが書き込むことができ、他のユーザは、許された権限に応じて、ブログ、掲示板を読んだり、コメントを付けたりすることができる。
【００５１】
後で詳しく説明するが、ハードディスク・ドライブ３１０には、本発明に係るマルチタイプ・リンク予測を計算するためのモジュール、すなわち、３階テンソルＦ*を計算するモジュール、類似度行列を計算するモジュール、行列の固有値と固有ベクトルを求めるモジュール、行列のクロネッカー積あるいはクロネッカー和を計算するモジュール、その他必要な行列計算を行なうモジュールなどが保存されている。
【００５２】
ブログ、掲示板などの構成と、それらに対するユーザのアクセス制御は、Perl、Ruby、PHP、Servlet、JSPのような周知のプログラミング言語のツールで実現することができる。あるいは、C、C++、C#、Java（サン・マイクロシステムズの商標）などを用いることもできる。
【００５３】
さらに、ＨＴＭＬファイル中に適宜、JavaScript（商標）を埋め込んで、Perl、Ruby、PHPなどと協働するようにシステムを構成することもできる。
【００５４】
ブログ、掲示板、ニュースなどのコンテンツは、コンテンツ管理データベース（ＣＭＤＢ）に格納して、一元的に管理することも可能である。
【００５５】
尚、上記オンライン・コミュニティ・サーバ１０２として、インターナョナル・ビジネス・マシーンズ・コーポレーションから購入可能な、ＩＢＭ（インターナョナル・ビジネス・マシーンズ・コーポレーションの商標）Ｓｙｓｔｅｍ  Ｘ、Ｓｙｓｔｅｍ  ｉ、Ｓｙｓｔｅｍ  ｐなどの機種のサーバを使うことができる。その際、使用可能なオペレーティング・システムは、ＡＩＸ（インターナョナル・ビジネス・マシーンズ・コーポレーションの商標）、ＵＮＩＸ（The Open Groupの商標）、Ｌｉｎｕｘ（商標）、Ｗｉｎｄｏｗｓ（商標）２００３  Ｓｅｒｖｅｒなどがある。
【００５６】
図４は、本発明に係る機能のブロック図を示すものである。図４において、ユーザ情報４０２は、オンライン・コミュニティ・サーバ１０２のハードディスク・ドライブ３１０に保存されているユーザのプロファイル情報であり、具体的には、図６に示すように、ユーザx1、x2、x3・・・毎に、性別、年齢、などの個人情報を含む。さらに図６に示すように、ユーザ情報４０２は、好適には、ブログなどのコンテンツの個々の記事などの単位に対する関係のリンクの情報ももつ。
【００５７】
コンテンツ４０４は、ハードディスク・ドライブ３１０に保存されている、ブログの記事、コメント、その他の情報の集合である。アクティブなサイトの場合、コンテンツがユーザによって日々書かれ、増大する。
【００５８】
ログ４０６は、ユーザの、ログイン、ログアウト、ブログの書き込み、読取り、コメントすることなど、あらゆる活動を記録したファイルであり、これも、ハードディスク・ドライブ３１０に格納される。ログ４０６の例を示すと、下記のとおりである。
【００５９】
日付         時間        活動     ユーザＩＤ
--------------------------------------------------------------------------
2009/03/01 09:51:001 JST Login    0146230
2009/03/01 10:00:050 JST Logout   0099321
2009/03/01 10:11:130 JST PostBlog 0146230 PostID: 004524082
2009/03/01 10:12:020 JST OpenMsg  2965124 MsgID : 019348003
【００６０】
上述のように、ログ４０６には、少なくとも、活動があった日時と、活動の内容と、その活動をしたユーザのユーザＩＤが含まれる。さらに、ブログを書いた(PostBlog)場合には、書いた記事のＩＤも格納され、メッセージを開いた(OpenMsg)場合には、その開いたメッセージのＩＤが格納される。すなわち、ログ４０６のエントリに基づき、ユーザとコンテンツの要素の間の関係を取得することが可能である。
【００６１】
計算モジュール４０８は、本発明に基づく処理を行なうプログラム・モジュールであって、前述した、本発明に係るマルチタイプ・リンク予測を計算するためのモジュール、すなわち、３階テンソルＦ*を計算するモジュール、類似度行列を計算するモジュール、行列の固有値と固有ベクトルを求めるモジュール、行列のクロネッカー積あるいはクロネッカー和を計算するモジュール、その他必要な行列計算を行なうモジュールなどを含む。これらのモジュールは、好適には、JAVA（商標）、Ｃ、Ｃ＋＋、Ｃ＃などのよく知られたプログラム言語で書かれ、実行可能バイナリ形式でハードディスク・ドライブ３１０に保存され、あるいはオペレーティング・システムの機能によってメモリにロードされ、実行可能である。
【００６２】
計算モジュール４０８は、ユーザ情報４０２、コンテンツ４０４、及びログ４０６の情報を使用して、教師テンソルデータＦ*４１０、類似度行列４１２及び、類似度行列の固有値・固有ベクトル４１４を生成する。こうして生成された教師テンソルデータ４１４、類似度行列４１２及び、類似度行列の固有値・固有ベクトル４１４は、好適には一旦、ＲＡＭ３０８に配置される。このため、オンライン・コミュニティ・サーバ１０２のＲＡＭの容量は、なるべく大きい方が望ましい。
【００６３】
計算モジュール４０８は更に、教師テンソルデータ４１０、類似度行列４１２及び、類似度行列の固有値・固有ベクトル４１４の情報を用いて計算し、リンク予測結果Ｆ４１６を生成する。その実際の計算処理については、後で、図７以降のフローチャートを参照して説明する。
【００６４】
リンク予測結果Ｆ４１６は、この場合、全てのユーザと、全てのコンテンツの要素との間のリンク予測の値を要素として含む３階テンソルである。従って、この結果を用いて、特定のユーザまたはユーザのグループに関連の大きいコンテンツの要素を予測することができ、以って、推奨すべきコンテンツを特定することもできる。
【００６５】
図５は、この実施例における、オンライン・コミュニティにおける、ユーザの集合Ｘと、コンテンツの要素の集合Ｙとの間のリンク関係を模式的に示す図である。図５において、ユーザx1が、コンテンツの要素y2を読み、ユーザx2が、コンテンツの要素y1に対してコメントし、ユーザx3が、コンテンツの要素y3を書くという例がここに示されている。このような既存のリンク関係が、教師テンソルデータＦ*４１０として反映されることになる。このようなリンク関係の情報は、実際上、ログ４０６から抽出可能である。
【００６６】
なお、図５の例では、Ｘ≠Ｙであるが、ユーザの集合Ｘ内でユーザ間のリンクを調べるというモデルもあり、その場合は、Ｘ＝Ｙとなる。
【００６７】
次に図７以下を参照して、本発明のリンク予測処理のアルゴリズムを説明する。特に図７は、全体の処理の概要フローチャートである。
【００６８】
そのステップ７０２は、パラメータを設定するステップ、すなわち、教師データテンソル、類似度行列などのデータを予め用意いるためのステップで、図８のフローチャートに関連して、後で詳細に説明する。
【００６９】
ステップ７０４は、本発明の根幹となる、リンク予測の方程式を解くステップで、図１２のフローチャートに関連して、後で詳細に説明する。
【００７０】
ステップ７０６は、リンク予測の方程式を解くことによって得られた予測値を出力するステップである。得られた予測値は、この実施例の場合、個々のユーザと個々のコンテンツの要素の間の、それぞれのリンクの予測値であり、この値を用いて、特定のコンテンツの要素と高いリンク予測値をもつのは、どのユーザかということが推測できるので、この値に基づきコンテンツの推奨などを行なうことができる。
【００７１】
次に、図８のフローチャートを参照して、パラメータを設定するステップについて説明する。ログ４０６には、ユーザＩＤと、コンテンツの要素のＩＤと、活動の種類が記録されている。そこで、図８のステップ８０２では、計算モジュール４０８が例えば、前述のログ４０６のエントリを走査することによって、ユーザとコンテンツの要素の間のリンクを、その種類毎にカウントする。
【００７２】
そこで、リンクの有無が分かっているユーザとコンテンツの要素のペアの数をNとし、そのうち、リンクがあると分かっているペアの数をN+、リンクがないと分かっているペアの数をN-とすると、テンソルの成分[Ｆ*]i,j,kには、iとjの間にkのリンクがあると分かっている場合はε+ = N/N+、iとjの間にkのリンクがないと分かっている場合はε- = N/N-を格納するようにする。リンクの有無が分かっていていない場合は、単に0を入れるものとする。ここで、リンクの有無が分かっているユーザとは、i,j,kの関係の有無がログ４０６から得られる場合であり、そうでない場合をリンクの有無が分かっていない、すなわち予測の対象のものであると定義する。なお、このようなＦ*のパラメータの与え方は、一例であって、本発明はそのようなパラメータの与え方に限定されないことを理解されたい。
【００７３】
ステップ８０４では、計算モジュール４０８が、図５におけるユーザの集合Ｘ、コンテンツの集合Ｙ、及びＸとＹの間のリンクにおける、集合Ｘの類似度行列、集合Ｙの類似度行列、そして、集合Ｚの類似度行列を計算する。ここで、後の便宜のために、ＸとＹの間のリンクの集合をＺとする。
【００７４】
Ｘ，Ｙ，Ｚの類似度行列は、基本的に、その各々の集合の要素間の性質に基づき、計算される。図９は、ユーザの集合Ｘの類似度行列の例を示す。このような類似度行列は例えば、図６に示すような各ユーザの特徴ベクトルの間の正規化された距離を計算することによって、生成することができる。従って、類似度行列は、ユーザの数をMとすると、M×Mの行列となる。このとき、各要素の値は非負で、対角成分が1、またはその他の値になるように正規化される。この類似度行列は、ＷXと記すことにする。
【００７５】
図１０は、コンテンツの集合Ｙの類似度行列の例を示す。このような類似度行列は例えば、コンテンツの要素の各々を構文解析して、キーワードを抽出し、それらのキーワードの並びとして特徴ベクトルを構成し、それらの特徴ベクトルの間の正規化された距離を計算することによって、生成することができる。従って、類似度行列は、コンテンツの要素の数をNとすると、N×Nの行列となる。このとき、各要素の値は非負で、対角成分が1、またはその他の値になるように正規化される。この類似度行列は、ＷYと記すことにする。
【００７６】
図１１は、リンクの集合Ｚの類似度行列の例を示す。このような類似度行列は例えば、個々のリンクに関連付けられたユーザ及びコンテンツの要素をリストして特徴ベクトルを構成し、それらの特徴ベクトルの間の正規化された距離を計算することによって、生成することができる。従って、類似度行列は、リンクの種類の数をTとすると、T×Tの行列となる。このとき、各要素の値は非負で、対角成分が1、またはその他の値になるように正規化される。この類似度行列は、ＷZと記すことにする。
【００７７】
これらの記法は、以下のアルゴリズムの説明でも、踏襲する。
【００７８】
ステップ８０６では、計算モジュール４０８が、リンク予測の方程式を解くための変数値を取得する。ここでいう変数値は、例えば、結果を格納するための３階テンソルＦである。
【００７９】
次に、図１２を参照して、リンク予測の方程式を解く処理について説明する。図１２のステップ１２０２では、類似度行列の次元が所定の閾値より小さいかどうかを計算モジュール４０８が判断する。これは、本発明に係る厳密解法と、近似解法のどちらを適用するかを判断するためである。すなわち、厳密解法は、より正確なリンク予測を与えるが、必要なコンピュータ・メモリの容量が大きく、より計算時間がかかるので、類似度行列の次元で、どちらを適用するかを判断する。
【００８０】
類似度行列の次元が所定の閾値より小さいと判断すると、ステップ１２０４で、リンク予測の方程式の厳密解を求めるステップを計算モジュール４０８が実行する。リンク予測の方程式の厳密解を求めるステップは、図１３を参照して、後でより詳細に説明する。
【００８１】
類似度行列の次元が所定の閾値より大きいと判断すると、ステップ１２０６で、リンク予測の方程式の近似解を求めるステップを計算モジュール４０８が実行する。リンク予測の方程式の近似解を求めるステップは、図１４を参照して、後でより詳細に説明する。
【００８２】
次に、本発明に係るリンク予測の方程式を解くためのアルゴリズムを説明する。
先ず、上記非特許文献から引用した式１を再掲する。
(σＬ + Ｉ)vec(Ｆ) = vec(Ｆ*)  ・・・式１
【００８３】
この実施例の説明では、類似度行列の対角成分が全て1であると述べるが、実際には類似度行列の要素は集合の要素間の類似度を表すものあるから、非負の値ならすべて可能である。但し、本発明では、このような類似度行列の各行の和を効率的に計算できることが重要な条件である。
【００８４】
厳密解を求める時に、類似度行列の各行の和を単純な方法で効率的に求められるが、近似解を求める時に類似度行列を近似する行列の各行の和も効率的に求められる。このように、各行の和、または、行の和の最大値を利用して、類似度行列を、上記の数１と数２で示したように、正規化することができる。例えば、近似解を求めるステップでは、N×Nの類似度行列の各行の和を求める計算量はO(N2)ステップかかるが、その類似度行列のN×dの低ランク近似行列から各行の和の近似を求める計算量はO(Nd)しかかからない。  
【００８５】
すると、Ｌは、正規化ラプラシアン行列で、数３を再掲すると，以下のように表される。
【数４】
2010250377.tif 000006
よって、解きたい式は、下記の式２のようになる。なお、係数σは、例えば0.01と設定される。
【数５】
2010250377.tif 000007
ここで、類似度行列の間に作用される演算子は下記のとおりであり、
【数６】
2010250377.tif 000008
すなわち、クロネッカー積
【数７】
2010250377.tif 000009
または、クロネッカー和
【数８】
2010250377.tif 000010
のどちらかである。クロネッカー積またはクロネッカー和のどちらを使うかは、用途による。vec(Ｆ)という記法は、テンソルＦの成分を並べてベクトルにしたものである。
【００８６】
ここで、クロネッカー積を使うかクロネッカー和を使うか、という明確な基準は本来特にないが、本発明の手法が高速であるため、データから学習して最適なものを効率的に選べるので、解きたい問題によって精度のよいものを使うことができる。
【００８７】
定義としては、以下のように、
クロネッカー積： 類似度行列の３つ組の要素同士が全て似ているなら、３つ組は似ているとする
クロネッカー和： 類似度行列の３つ組の要素中、２つが共通で、残り１つが似ているなら、３つ組は似ているとする、というものである。
【００８８】
こうして、式２の解は、下記の式３のように書かれる。
【数９】
2010250377.tif 000011
この逆行列をいかに高速に、且つ少ないメモリでコンパクトに解くかが、この技法のキーである。
【００８９】
尚、vec()記法、クロネッカー積、クロネッカー和については、A. J. Laub, Matrix for Scientists and Engineers, Society for Industrial and Applied Mathematics 2005; あるいは、David A. Harville, Matrix Algebra from a Statistician's Perspective, Springer Verlag 1997 などを参照されたい。
【００９０】
さて、図１３に戻って、ステップ１３０２では、計算モジュール４０８がＷX, ＷY, ＷZの固有値分解を求めるのであるが、ここで、A. J. Laub, Matrix for Scientists and Engineers, Society for Industrial and Applied Mathematics 2005にも記載されている有用な定理を書き下しておく。
【００９１】
＜定理１＞
{λX(1), λX(2), ...,λX(M)},
{λY(1), λY(2), ...,λY(N)},
{λZ(1), λZ(2), ...,λZ(T)}
をそれぞれ、ＷX, ＷY, ＷZの固有値とする。
また、ＶX, ＶY, ＶZを、それぞれ、ＷX, ＷY, ＷZの固有ベクトル（縦ベクトル）を並べた行列とする。
すると、クロネッカー積
【数１０】
2010250377.tif 000012
または、クロネッカー和
【数１１】
2010250377.tif 000013
の固有ベクトルは、ともに
【数１２】
2010250377.tif 000014
で与えられる。
また、固有値は、クロネッカー積の場合
【数１３】
2010250377.tif 000015
で与えられ、クロネッカー和の場合
【数１４】
2010250377.tif 000016
で与えられる。
【００９２】
そこで、ステップ１３０２において、ＷX, ＷY, ＷZの固有値分解を、
ＷX = ＶX diag(λX(1), λX(2), ...,λX(M)) ＶXT
ＷY = ＶY diag(λY(1), λY(2), ...,λY(N)) ＶYT
ＷZ = ＶZ diag(λZ(1), λZ(2), ...,λZ(T)) ＶZT
とする。ここで、diag()は、対角行列である。
【００９３】
そこで、クロネッカー積の場合、固有値を保持する３階テンソルＬを、
[Ｌ]i,j,k ≡ λX(i)λY(j)λZ(k)と定義する。
クロネッカー和の場合、固有値を保持する３階テンソルＬは、
[Ｌ]i,j,k ≡ λX(i) + λY(j) + λZ(k)と定義する。
また、本発明では、クロネッカー積とクロネッカー和の両方をあわせてリンクの予測も可能で、そのときの固有値を保持する３階テンソルＬを
[Ｌ]i,j,k ≡ α（λX(i)λY(j)λZ(k) ）＋β（λX(i) + λY(j) + λZ(k)）と定義する。
ただし、αとβは任意の実数で、データから最適な値を学習して設定できる。本発明での３階テンソルＬの値は類似度行列の固有値、またはその近似行列の固有値、のあらゆる関数から効率的に計算できるから、クロネッカー和とクロネッカー積から得られるものだけに限定されるものではない。また、３階テンソルＬの値にはどの関数を利用するかはデータから学習して効率的に選択することが可能である。
【００９４】
すると、定理１により、式３の逆行列は、
【数１５】
2010250377.tif 000017
と書き直せる。ここで
【数１６】
2010250377.tif 000018
であることを利用すると、
【数１７】
2010250377.tif 000019
と書き直せる。
【００９５】
((cσ+1)I - σdiag(vec(L)))は対角行列であるから、その逆行列は容易に求まる。そこで、ステップ１３０４で、３階テンソルＤを、
【数１８】
2010250377.tif 000020
のように定義すると、解は次のように書ける。
【数１９】
2010250377.tif 000021
【００９６】
この式は、さらに以下のように簡略化できる。
【数２０】
2010250377.tif 000022
【００９７】
これから結局、下記の式５を得る。ステップ１３０６で、この式５を用いて、結果のＦを得る。
【数２１】
2010250377.tif 000023
ここで、×1などの演算は、テンソルのモード積で、T. G. Kolder & B. W. Bader, "Tensor decomposition and applications" Tech. Rep. SAND2007-6702, Sandia National Laboratories などにその詳細な定義が記載されている。
【００９８】
次に、図１４のフローチャートを参照して、近似解法について説明する。近似解法は、類似度行列や解Ｆが大きすぎて、コンピュータのメモリに入りきらない場合に用いられる。ステップ１４０２では、類似度行列が大きすぎるという問題に対処するために、計算モジュール４０８は、不完全コレスキー分解などの方法を用いて、下記のように、類似度行列ＷX, ＷY, ＷZを低ランク近似する。
【数２２】
2010250377.tif 000024
【００９９】
ここで、ＧXは、M×M~行列、ＧYは、N×N~行列、ＧZは、T×T~行列で、
M > M~、N > N~、T > T~である。不完全コレスキー分解を用いることで、類似度行列を明示的にメモリ内に構成することなく、計算量O(MM~2 + NN~2 + TT~2)で、この分解を実行できる。
【０１００】
ステップ１４０４では、計算モジュール４０８は、次のようにして、
ＧXTＧX, ＧYTＧY, ＧZTＧZのの固有値分解を求める。
ＧXTＧX = Ｕ~X diag(λ~X(1), λ~X(2), ...,λ~X(M~))Ｕ~XT
ＧYTＧY = Ｕ~Y diag(λ~Y(1), λ~Y(2), ...,λ~Y(N~))Ｕ~XT
ＧZTＧZ = Ｕ~Z diag(λ~Z(1), λ~Z(2), ...,λ~Z(N~))Ｕ~ZT
すなわちここで、Ｕ~X、Ｕ~Y、Ｕ~Zは、それぞれ、
ＧXTＧX, ＧYTＧY, ＧZTＧZの固有ベクトル（縦ベクトル）を並べた行列である。
【０１０１】
ＧXTＧX, ＧYTＧY, ＧZTＧZは、ＧXＧXT, ＧYＧYT, ＧZＧZTよりもずっと次数を小さくすることができるため、より少ないメモリで、固有値分解を行なうことができる。
【０１０２】
次のステップ１４０６では、次のようにして、ＧXＧXT, ＧYＧYT, ＧZＧZTの固有ベクトルを求める。
Ｖ~X = ＧXＵ~Xdiag(λ~X(1), λ~X(2), ...,λ~X(M~))-1/2
Ｖ~Y = ＧYＵ~Ydiag(λ~Y(1), λ~Y(2), ...,λ~Y(N~))-1/2
Ｖ~Z = ＧZＵ~Zdiag(λ~Z(1), λ~Z(2), ...,λ~Z(T~))-1/2
【０１０３】
以上の結果を利用すると、式２の逆行列は、下記のようになる。
【数２３】
2010250377.tif 000025
【０１０４】
ここで、Ｌ~は、クロネッカー積の場合は
[Ｌ~]i,j,k ≡ λ~X(i)λ~Y(j)λ~Z(k)
クロネッカー和の場合は
[Ｌ~]i,j,k ≡ λ~X(i) + λ~Y(j) + λ~Z(k)
と定義される。
【０１０５】
しかし、厳密解の場合と異なり、
【数２４】
2010250377.tif 000026
なので、このままでは厳密解の場合のように、式２の逆行列を変形することはできない。
【０１０６】
そこで、C. M. Bishop, Pattern Recognition and Machine Learning, 2006, Springer Verlagに記載されているWoodburyの公式を用いると、
【数２５】
2010250377.tif 000027
のようになる。
【０１０７】
そこで３階テンソルＤを、下記の式６のように定義する。
【数２６】
2010250377.tif 000028
【０１０８】
すると、解は次のようにあらわされる。
【数２７】
2010250377.tif 000029
【０１０９】
これから、Ｆは、次のように求められる。
【数２８】
2010250377.tif 000030
【０１１０】
特に、ステップ１４１０で、下記を式の中心部分として保持しておく。
【数２９】
2010250377.tif 000031
Ｆ自体のサイズが大きいため、式８の結果を予め計算して保持しておくことにより、ステップ１４１２で、必要な予測だけ、オンデマンドで計算することが可能となる。
【０１１１】
こうして、結果のテンソルＦにおいて、その成分(i,j,k)の値は、集合Ｘの要素iと、集合Ｙの要素jの間のリンクkの値が格納されており、その値が大きいほどリンクkの尤度が高いと解釈される。
【０１１２】
以上のように、本発明のマルチタイプ・リンク予測技法を、オンライン・コミュニティ・サーバを例して説明してきたが、本発明はこれには限定されず、協調フィルタリング、生体ネットワーク予測など、任意のマルチタイプ・リンク予測の応用例に適用可能である。
【０１１３】
また、上記実施例では、Ｗｅｂサーバ上でマルチタイプ・リンク予測のプログラムを実行するようにしたが、スタンドアロンのコンピュータでも同様に実施することが可能であることは、この分野の当業者なら理解するであろう。
【符号の説明】
【０１１４】
４０２・・・ユーザ情報
４０４・・・コンテンツ
４０６・・・ログ
４０８・・・計算モジュール
４１０・・・教師テンソルデータＦ*
４１２・・・類似度行列のデータ
４１４・・・固有ベクトル、固有値のデータ
４１６・・・リンク予測結果
【図１】
2010250377.tif 000032
【図２】
2010250377.tif 000033
【図３】
2010250377.tif 000034
【図４】
2010250377.tif 000035
【図５】
2010250377.tif 000036
【図６】
2010250377.tif 000037
【図７】
2010250377.tif 000038
【図８】
2010250377.tif 000039
【図９】
2010250377.tif 000040
【図１０】
2010250377.tif 000041
【図１１】
2010250377.tif 000042
【図１２】
2010250377.tif 000043
【図１３】
2010250377.tif 000044
【図１４】
2010250377.tif 000045