協調フィルタリングのためのコンピュータ実施方法および協調フィルタリングシステム
【課題】協調フィルタリングシステムにおいて、類似メトリックがシステム設計者によって決定されるのではなく、データの学習により決定できるようにする。
【解決手段】協調フィルタリング方法は、最初に、関係データベースを、エッジによって接続されるノードのグラフに変換する。関係データベースは、消費者属性、製品属性、及び製品評価を含む。グラフ上の、マルコフ連鎖ランダムウォークの統計量が決定される。その後、クエリ状態に応答して、提案を行うために、統計量に従って、マルコフ連鎖の状態が決定される。
【解決手段】協調フィルタリング方法は、最初に、関係データベースを、エッジによって接続されるノードのグラフに変換する。関係データベースは、消費者属性、製品属性、及び製品評価を含む。グラフ上の、マルコフ連鎖ランダムウォークの統計量が決定される。その後、クエリ状態に応答して、提案を行うために、統計量に従って、マルコフ連鎖の状態が決定される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的に、協調フィルタリングに関し、より詳細には、マルコフ連鎖による協調フィルタリングに関する。
【背景技術】
【０００２】
従来技術の協調フィルタリングシステムは、通常、或る製品についての消費者の嗜好を、消費者の属性、並びに、その製品を好む他の消費者の属性に基づいて予測する。本明細書で使用される「製品」という用語は、商品等の有形の製品、並びに、サービス、映画、テレビ番組、本、ウェブページ、スポーツ、娯楽、又は、「評価される（rated）」ことができる他のあらゆるものを意味し得ることに留意されたい。「消費者」という用語は、ユーザ、閲覧者、読み手等を意味し得る。一般に、年齢及び性別等の属性は消費者に関連し、ジャンル、コスト、又は製造業者等の属性は、製品に関連する。
【０００３】
協調フィルタリングは、一般に、欠測値問題として扱うことができる。製品評価表は、一般に、非常に疎である。すなわち、考え得る製品の非常に大きなセット（集合）内の任意の１つの製品について、評価は、非常に小さな消費者の部分集合から利用可能なだけである。通常、目的は、個々の消費者の好みと一貫性のある順序付けで、欠測値を予測し、且つ／又は、未評価アイテムを並べる（rank）ことである。システムは、提案を行うのに、これらの予測を使用する。
【０００４】
協調フィルタリングは、以下の米国特許、すなわち第６，４９６，８１６号「Collaborative filtering with mixtures of Bayesian networks」、第６，４８７，５３９号「Semantic based collaborative filtering」、第６，３２１，１７９号「System and method for using noisy collaborative filtering to rank and present items」、第６，１１２，１８６号「Distributed system for facilitating exchange of user information and opinion using automated collaborative filtering」、第６，０９２，０４９号「Method and apparatus for efficiently recommending items using automated collaborative filtering and feature-guided automated collaborative filtering」、第６，０４９，７７７号「Computer-implemented collaborative filtering based method for recommending an item to a user」、第６，０４１，３１１号「Method and apparatus for item recommendation using automated collaborative filtering」、及び、以下の米国公開出願、すなわち第２００４／００５４５７２号「Collaborative filtering」、第２００３／００５５８１６号「Recommending search terms using collaborative filtering and web spidering」、第２００２／００６５７９７号「System, method and computer program for automated collaborative filtering of user data」に記載されている。
【０００５】
技術的見地及び科学的見地からの協調フィルタリングの広範な調査は、Gediminas Adomavicius及びAlexander Tuzhilin著「Recommendation technoligies: Survey of current methods and possible extensions」University of Minnisota, USA, MISRC WP 03-29, 2004によって提供されている。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従来技術の方法は、他の同様な消費者によって行われる選択を組み合わせることによって、消費者の選択を実質的に予測する。従来技術の協調フィルタリングシステムに伴う１つの問題は、類似（similarity）メトリックが、データから学習されるのではなく、システム設計者によって決定されることである。
【０００７】
データ内の任意の２つのアイテム間の類似が、データ内の全ての関係によって知らされることが望ましい。これは、消費者間の関係と、製品間の関係の両方を含む。
【０００８】
従来技術の協調フィルタリングシステムに伴う別の問題は、データのサンプリングアーチファクトに対する感度である。これは、曖昧であるが、個人的に適切な製品よりも、一般的に人気のある製品を提案する方への偏りを生成することが多い。この偏りを取り除くことが望ましい。
【課題を解決するための手段】
【０００９】
［発明の概要］
本発明は、製品についての消費者の嗜好を、重み付き関連付け（association）グラフ上でのランダムウォークとしてモデル化する。グラフは、消費者、消費者属性、製品及び製品属性を連結する、関係データベースから導出される。
【００１０】
ランダムウォークは、マルコフ連鎖によって記述される。マルコフ連鎖は、全ての知られている消費者にわたって特定の消費者の嗜好を融合する。個々の消費者は、マルコフ連鎖の現在の状態によって識別される。
【００１１】
ランダムウォークは、情報検索を容易にする類似測度（measure）をもたらす。連鎖内の２つの状態間の類似測度は、その２つの状態から連鎖の残りの状態までの期待通過（travel）時間の間の相関である。相関は、連鎖の２つの状態を記述する２つのベクトルの間の角度の余弦として計算される。この測度は、個々の消費者によって行われる将来の選択を非常によく予測でき、提案及び分類用途に有益である。類似測度は、疎行列の逆転又は疎行列−ベクトル乗算の反復によって得られる。
【発明を実施するための最良の形態】
【００１２】
［好ましい実施形態の詳細な説明］
図１は、製品評価の例示的な関係データベース１００の一部を示す。消費者１０１は、消費者属性１１１〜１１３と関連する（符号１１０）。製品１０２は、製品属性１２１〜１２３と関連する（符号１２０）。消費者は、４という評価１３０を製品に与えた。データベースは、多くの異なる消費者によって行われた多くの製品評価を記憶することができることが理解されるべきである。
【００１３】
図２に示すように、関係データベース１００は、有向エッジによって接続されたノードのグラフ２１１に変換される（符号２１０）。グラフ上でマルコフ連鎖ランダムウォークを実施することによって、統計量（statistics）が決定される（符号２２０）。ランダムウォークは、連鎖の現在の状態が個々の消費者を表すマルコフ連鎖を生成する。状態の統計量は、余弦相関２２１及び期待割引（discounted）利益２２２を含む。提案２３２を行うために、クエリ状態２３１に応答して、統計量がソートされる（符号２３０）。
【００１４】
本発明は、関係データベース１００を表す重み付き関連付けグラフ２１１のランダムウォーク２２０に基づいて提案を行う協調フィルタリングシステムを提供する。関連付けは、消費者の属性と製品の属性の間で行われる。
【００１５】
連鎖の状態間の期待通過時間は、類似測度への自然な変換を有する距離メトリックをもたらす。類似測度は、状態間の余弦相関２２１である。この測度は、従来のグラフベースの相違測度と比べて個々の消費者の嗜好をずっとよく予測できる。利点として、ランダムウォーク２２０は、従来の協調フィルタリングの通常の「誰が何を好きだったか（who-liked-what）」に勝る文脈情報を組み入れることができる。
【００１６】
本発明はまた、非常に大きなグラフ上で機能することができる近似戦略を提供する。近似により、状態の期待割引利益２２２等の従来通りに有益な統計量を決定すること（符号２２０）が実用的になり、利益を最適化する提案２３２を作成することができる。
【００１７】
マルコフ連鎖の統計量
疎で、任意に重み付けされた、非負の行列は、有向の関連付けグラフ３１１のエッジを指定する。エッジは、イベントのカウントを表す。すなわち、エッジＷｉｊは、イベントｉがイベントｊを伴う回数である。たとえば、ユーザｉ１０１が映画ｊ１０２を評価した時、Ｗｉｊは、ゼロより大きい。
【００１８】
本発明は、行列Ｗによって指定される有向グラフ２１１上でランダムウォークを実施する。行を正規化した確率行列Ｔ＝ｄｉａｇ（Ｗ１）−１Ｗは、関連付けされたマルコフ連鎖の状態の推移確率を記憶し、ここで、１は複数の１からなるベクトルである。
【００１９】
マルコフ連鎖は既約であり（irreducible）、到達できない（unreachable）状態又は吸収的な（absorbing）状態はないと考えられる。連鎖は非対称であることができ、自己遷移は、繰り返されたイベントの発生をモデル化する。行列Ｗの統計量が、母集団の集合的振る舞いの公正なサンプルから導出される場合、短期間にわたって、グラフ２１１上でのランダムウォーク２２０は、母集団から無作為に抽出された個々の消費者の嗜好をモデル化する。
【００２０】
ランダムウォークの種々の統計量が、予測タスクにとって有益である。定常分布は、無限に長いランダムウォークにおいて各状態を横切る相対頻度を記述する。連鎖における状態が、消費者によって使用される製品を表す場合、比較的大きな統計量は、人気のある製品を指示する。
【００２１】
形式的に、定常分布は、
【数１】
及びｓＴ１＝１を満たす。行列Ｗが対称である場合、定常分布ｓ＝（１ＴＷ）／（１ＴＷ１）である。その他の場合、分布は、反復（recurrence）ｓｉ＋１Ｔ←ｓｉＴＴ，ｓ０＝１／Ｎから決定することができる。
【００２２】
反復時間：ｒｉ＝ｓｉ−１は、同じ状態への２回の連続する訪問の間の期待時間を記述する。反復時間は、以下に述べる、自己コミュート（self-commute）時間、すなわちＣｉｉ＝０と混同されるべきではない。
【００２３】
状態ｉから「ヒット」状態ｊまでのランダムウォークについての期待ヒット時間は、
【００２４】
【数２】
【００２５】
から決定することができ、ここで、ｆは、ｓと直交しない任意の非ゼロベクトルであり、Ｔは、
【００２６】
【数３】
【００２７】
による、転置演算子であり、期待ラウンドトリップコミュート時間は、
【００２８】
【数４】
【００２９】
である。
【００３０】
ｆ＝ｓである時、行列Ａは、基本行列の逆行列である。提案２３２を作成するために、２つの相違測度Ｃｉｊ及びＨｉｊを使用することができる。しかしながら、これらの相違測度は、定常分布によって支配される可能性がある。これによって、個々の消費者の好みにかかわらず、人気のある同じ製品が、全ての消費者に提案される。
【００３１】
図５は、上記統計量を使用して、本発明に従って行った平均的な提案の評価を比較する。たとえば、閲覧者がどの映画を観て好きになるかを予測することについて、余弦相関は、全ての他の測度のほぼ２倍有効である。
【００３２】
ランダムウォーク相関
本発明は、情報検索の最も有益な統計量のうちの１つ、すなわち余弦相関２２１をランダムウォークに結合する。情報検索において、データアイテムは、ベクトルで表されることが多い。ベクトルは、アイテムの種々の属性、たとえば、文書中の特定の語句の頻度を「カウントする」。２つのアイテムは、その属性ベクトルの内積が大きい時、類似であると考えられる。この例では、文書は、語句の特定の分布を生成する「プロセス」のサンプルである。より長い文書は、分布のサンプリングを増加させ、より多数の語句及びより大きな内積をもたらす。しかしながら、より大きな内積は、類似の程度を増加させるべきではない。
【００３３】
この「サンプリングアーチファクト」をなくすために、情報検索は、２つの属性ベクトル間の角度を測定する。この角度の余弦は、正規化されたベクトルの内積に等しい。角度の余弦はまた、２つの分布の間の実験的な相関を測定する。
【００３４】
ランダムウォークの相関２２１を取得する重要なアイデアは、これにより、ランダムウォークの長期の振る舞いを幾何学的にモデル化することが可能になることである。
【００３５】
ラウンドトリップコミュート時間の平方根は、三角不等式√Ｃｉｊ＋√Ｃｊｋ≧√Ｃｉｋ、対称√Ｃｉｊ＝√Ｃｊｉ、及び、恒等式√Ｃｉｊ＝０を満たす。コミュート時間を２乗距離
【数５】
と同一視することは、各状態が或る点に割り当てられた状態で、ユークリッド空間におけるマルコフ連鎖の幾何学的埋め込みを提供する。
【００３６】
ユークリッド埋め込みにおいて、同様な状態は、頻繁に訪れる状態を原点の近くに配置した状態で、ほとんど同じ場所に配置される。しかしながら、コミュート時間と同様に、人気があるが、おそらく相違する状態の近接性により、ユークリッド距離がほとんどの用途に適さなくなる。
【００３７】
上述したように、相関２２１は、この中心性（centrality）を排除する。相関は、状態ｉ及びｊの属性ベクトルｘｉ、ｘｊの間の角度（ｘｉ，ｘｊ）の余弦である。
【００３８】
角度の余弦を取得するために、２乗距離Ｃの行列は、
【００３９】
【数６】
【００４０】
であることを遵守することによって、内積Ｐの行列に変換される。
【００４１】
２重中心化（double-centering）
【００４２】
【数７】
【００４３】
によって、行平均Ｐｉｉ=ｘｉＴｘｉ及び列平均Ｐｊｊ=ｘｊＴｘｊが、行列Ｃから除去され、Ｐｉｊ＝ｘｉＴｘｊが生じる。そのため、余弦相関２２１は、角度
【００４４】
【数８】
【００４５】
の余弦である。
【００４６】
付録Ａは、密行列Ｃを決定することなく、疎行列Ｔ及びＷから直接に行列Ｐを決定する方法を記述する。対称であるゼロ対角行列Ｗの特別な場合について、行列Ｐは、グラフラプラシアンｄｉａｇ（Ｗ１）−Ｗの擬似逆転へと単純化される。
【００４７】
余弦相関２２１はまた、幾何学的な解釈を有する。一般的な人気の影響を除去するために、全ての点が単位超球（unit hyper-sphere）上に投影され、その対ごとのユークリッド距離が、
【数９】
と示される場合、
【００４８】
【数１０】
【００４９】
である。
【００５０】
この埋め込みでは、１つの点の別の点との相関は、ユークリッド距離の２乗和が減少するにつれて増加する。これは、合計され且つ平均された相関を、２つの状態グループの間の類似を測定するための、幾何学的に意味のある方法にする。
【００５１】
大きなマルコフ連鎖において、ノルム
【数１１】
は、状態のほぼ逆転した「人気」である、反復時間ｒｉ＝ｓｉ−１の、所定の規模までの精密な近似である。したがって、余弦相関２２１は、一様でないサンプリングによるアーチファクトを減らす類似測度として解釈することができる。
【００５２】
たとえば、２つのウェブ「ページ」が、非常に人気がある場合、任意の他のページからいずれかのページを訪問する期待時間は短く、２つのページは互いのコミュート時間が短い。しかしながら、２つのページが、通常、異なる人々によってアクセスされるか、異なる属性のセットと関連する場合、属性ベクトル間の角度の余弦は大きく、相違を意味する。
【００５３】
同様に、映画のデータベースの場合、恐怖スリラー「羊たちの沈黙」から子供向け映画「フリーウィリー」までのコミュート時間は、いずれかの映画への平均コミュート時間より短い。これは、両方の映画が非常に人気があったためである。しかし、それらの属性ベクトル間の角度は、それらの聴衆にほとんど重なりが存在しないため、平均より大きい。
【００５４】
しかしながら、密なＮ×Ｎ行列を構築し、且つ逆転することは、約Ｎ３回の操作を必要とし、大きなマルコフ連鎖にとって明らかに実用的でない。これはまた、ほとんどのクエリが、行列Ｐ及び余弦行列の小行列を含むだけであるため無駄が多い。付録Ａは、小行列が、疎なマルコフ連鎖パラメータから直接推定することができる方法を記述する。
【００５５】
提案及び分類
提案を行うために、クエリ状態２３１が選択され、マルコフ連鎖の他の状態が、クエリ状態２３１に対する、対応する余弦相関２２１に従ってソートされる（符号２３０）。クエリ状態は、消費者属性、製品属性、又は、消費者属性と製品属性の両方を表すことができる。
【００５６】
このモデルによる提案は、半教師あり（semi-supervised）分類問題に関連する。そこでは、状態は、ラベル付けされた（分類された）点及びラベル付けされていない（分類されていない）点として、ユークリッド空間内に埋め込まれる。類似測度は、ラベル付けされていない点とラベル付けされた点の間で決定される。完全な教師あり（fully supervised）分類と違って、ラベル付けされていない点とラベル付けされた点の間の類似は、空間内の他のラベル付けされていない点の分布によって媒介され、他のラベル付けされていない点の分布は、全体のデータセットにわたって距離メトリックに影響を与える。
【００５７】
同様に、グラフ２１１上でのランダムウォークにおいて、２つの状態間の類似は、グラフのランダムウォークによって実施される全ての可能な経路の分布に依存する。
【００５８】
図３Ａ及び図３Ｂはこれを示す。２０個の点３０２からなる弧によって囲まれた、２Ｄ平面の２つのガウスクラスタ内に、８０個の点３０１が配列される。図３Ａは、全ての点を、そのｋ個の最近傍に接続する疎なグラフである。
【００５９】
図３Ｂは、全ての点を所定の距離内の全ての近傍に接続する密なグラフである。エッジの重みは、ユークリッド距離、たとえば、
【数１２】
の急速減衰関数に従う。各頂点ドットのサイズは、その分類スコアの大きさを指示する。ゼロより大きいスコアを有する頂点は、弧に属するものとして分類される。
【００６０】
連結性（connectivity）及びエッジの重みは、ユークリッド距離に大まかに関連するが、類似は、グラフによって完全に媒介される。各グラフ内の３つのラベル付けされた点３１１（１つは弧上に、１つは各クラスタ上にある）は２つのクラスを表す。残りの点は、正規化された組み合わせラプラス関数であり、且つ、０＜α＜１が所定の正則化パラメータである、類似測度
【数１３】
に従って分類することができる。
【００６１】
図４Ａ及び図４Ｂは、グラフ２１１上でのランダムウォーク２２０の余弦相関２２１を使用して、点が分類される方法を示す。分類は、ラベル付けされた点に対する相関を合計するか、又は平均することによって実施される。グラフの頂点のサイズで示す分類スコアは、２つのクラスについての提案スコア間の差である。
【００６２】
図４Ａ及び図４Ｂは、エッジをグラフに加える基準が変わる時の分類の対応する変動を示す。余弦相関及びコミュート時間は共に、グラフ内のエッジの密度が変動する時に、比較的安定である直感的に正確な分類を与えるという意味で、うまく働く。余弦相関は、かなり広い分類裕度（classification margin）を提供し、したがって、グラフ内の小さな変化に対する安定性を提供する。
【００６３】
正規化されたコミュート時間（Ｉ−αＮ）−１、到達時間（hitting time）、逆転到達時間、及びそれらの正規化された変形は、密なグラフ上で適切に分類されるが、疎なグラフ上では不適切に分類される。この例から、余弦相関２２１は、関連付けグラフ２１１において、小さな変動下では一貫した提案を与えることが期待される。
【００６４】
期待利益
消費者は、関心のある製品を見出すことに関心があるが、販売業者は、利益の多い製品を提案することを好むであろう。消費者が、将来、追加の製品を取得することになり、その購入決定が利幅（profit margin）と無関係であると仮定すると、決定理論により、最適な戦略は、所定の期間にわたって割り引かれる、期待利益が最大になる製品（状態）を提案することが示される。すなわち、販売業者は、ランダムウォークが、そこから、非常に利益の多い状態、したがって、「目玉商品」等の小売戦略を通過する状態に消費者を「押しやりたい」と思う。さらに、これらの利益の多い状態は、ランダムウォークの早期において横切られるべきである。
【００６５】
それぞれの状態についての、利益又は損失のベクトルは、
【数１４】
であり、割引係数ｅ−β，β＞０は、将来の利益の時間値を決定する。ｉ番目の状態の期待割引利益２２２νｉは、到着時間について割り引かれた、ｉ番目の状態からの全ての到達可能な状態の平均化した利益である。ベクトル形式で、
【数１５】
である。
【００６６】
単位スペクトル半径より小さい（λｍａｘ（Ｘ）＜１）行列について恒等式
【数１６】
を使用して、上記級数（series）は、疎な線形系
【数１７】
として配列される。
【００６７】
たとえば、状態ｉにおいて、消費者にとって最も利益の多い提案は、最も多い期待割引利益
【数１８】
を有する、状態ｉの近傍の状態ｊである。
【００６８】
マルコフ連鎖における状態が、現在の状態からｋステップのところにある製品を表す場合、適切な項は、
【数１９】
である。
【００６９】
図６は、種々の統計量に基づいて提案を比較する。長期利益を最大にする提案を行うことは、狭義に利益の多い製品を提案することより遥かに効果的な戦略であり、利益の見通しなしの提案は、全く利益を生まない。
【００７０】
市場分析
本発明による方法は、マルコフ連鎖内の任意の状態から提案２３２を作成することができるため、特定の消費者人口統計に関して特に効果的である製品、又は、特定の製品種類に特に忠実である消費者を識別することが可能である。
【００７１】
たとえば、映画データベースは、J. Herlocker, J. Konstan, A. Borchers及びJ. Riedl著「An algorithmic framework for performing collaborative filtering」に記載されるように、映画の評価、並びに、消費者の性別及び年齢を記憶する。本発明による方法を、性別による嗜好を決定するデータベースに適用した。
【００７２】
図７は、各性別について、最上位の１０の提案を示す。図７に示すように、これらの状態からのコミュート時間又は期待到達時間によって映画を評価することは、評価が定常分布評価とほとんど同じであるため、無益であることがわかる。データベース内の消費者のほとんどが男性であるため、これは、男性については理解できる。しかしながら、余弦相関による評価は、男性がアクション映画及びＳＦ映画を好み、女性が恋愛映画及びドラマを好むという、２つの非常に異なる一覧を生成する。
【００７３】
図８に示すように、同じ方法は、特定の年齢層の消費者によって、どのジャンルが優先的に鑑賞されるかを決定することができる。図８は、年齢が実際には、ジャンル嗜好を予測しにくいことを示している。年齢のジャンル嗜好に対する相関は、弱いが、明らかに、ＳＦ映画８０２への関心が、１０代及び２０代でピークに達することを示している。その直後、冒険映画８０１への関心がピークに達し、ドラマ８０３及びフィルムノワール８０４への関心が上昇し始める。
【００７４】
発明の効果
関連付けグラフのランダムウォークは、関係データベースにおいて、類似性の関係を決定する自然な方法である。ランダムウォークは、協調フィルタリングアプリケーションにおいて、人口統計及び製品種類等の、広範囲な文脈情報を利用する方法を提供する。
【００７５】
本発明は、新規な類似測度、すなわち、関係データベースを表す重み付きグラフのランダムウォークにおける２つの状態の余弦相関を導出する。この測度は、提案用途及び分類用途について非常によい予測を行うことができる。
【００７６】
相関ベースの評価は、従来技術のコミュート時間、到達時間、及び関連するグラフベースの相違測度に基づく評価に比べて、よりよく予測でき、グラフのエッジセットの摂動に対してロバストである。
【００７７】
本発明は好ましい実施形態の例として述べられたが、本発明の精神及び範囲内で、種々の他の適応及び修正が行われてもよいことが理解される。したがって、本発明の真の精神及び範囲内に入る、全てのこうした変形及び修正を包含することが、添付の特許請求の範囲の目的である。
【００７８】
付録Ａ
【００７９】
実施戦略
Ｎ＞＞１０３の状態を有する連鎖について、コミュート時間の完全行列、又は、さらに、
【数２０】
の形態の大きな逆行列を決定することは実用的でない。資源要求を最小にするために、ほとんどの計算が（Ｉ−Ｘ）−１Ｇの形態を有することが利用され、ここで、行列Ｘ及びＧは疎である。多くのクエリについて、可能な状態の部分集合のみが比較される。行列Ｇが疎であるため、行列の逆転の列の小さな部分集合のみが必要である。これらは、級数展開
【数２１】
によって計算することができ、級数展開は、高速混合の疎なマルコフ連鎖について良好な近似をもたらすために、打ち切ることができる。特に、加法級数のｎ項の合計は、乗法展開による２ｌｏｇ２ｎの疎な行列の乗算によって評価することができる。逆転の任意の１つの列について、これは、疎行列−ベクトル積に帰着する。
【００８０】
１つの問題は、これらの級数が、単位スペクトル半径（λｍａｘ（Ｘ）＜１）より小さい行列についてしか収束しないことである。一致しない逆転について、関連する級数展開は、数値的に正確な結果を取得するために、増分的に除去することができる発散成分を有する。たとえば、到達時間の場合、Ｘ＝Ｔ＋１ｓＴであり、このスペクトル半径は２である。加法級数を展開することによって、１ｓＴの望ましくない倍数が、合計に急速に蓄積する。代わりに、望ましくない倍数を除去する反復が、必要に応じて（as the arise）
【００８１】
【数２２】
【００８２】
として構築され、ｉが無限に近づくにつれ、
【００８３】
【数２３】
【００８４】
に収束する。
【００８５】
これは、Ａｉ及びＢｉの列の任意の部分集合を計算するのに容易に適合し、Ｈの小行列を簡潔に計算することに留意されたい。ｉ＜Ｎであっても、疎な連鎖は、迅速に混合する傾向があるため、Ｂｉは、定常分布１ｓＴに急速に収束し、Ａｉは、良好な近似である。乗法級数についてのより高速な収束漸化式は、
【００８６】
【数２４】
【００８７】
として構築することができる。
【００８８】
これは、指数関数的に高速に収束するが、全てのＢｉの計算を必要とする。両方の反復において、ｓの代わりに１／Ｎを用いることができる。これは、最終の計算で除去される列の平均をシフトさせる。
【００８９】
【数２５】
【００９０】
収束したＢｉ＝１ｓＴから、反復時間ｒｉ＝ｓｉ−１を取得することができる。マルコフ連鎖パラメータから直接に内積行列Ｐを計算することが可能である。
【００９１】
【数２６】
【００９２】
である、恒等式
【００９３】
【数２７】
【００９４】
は、展開及び置換によって検証することができる。Ｐの小行列について、上記反復の適した変形を使用して、Ｑの対応する列を計算することだけが必要とされる。
【００９５】
再び、ｓ及びｒが、反復前に知られていない場合、置換ｓ→１／Ｎを行うことができる。収束において、結果として得られる
【数２８】
は、
【００９６】
【数２９】
【００９７】
及び、
【００９８】
【数３０】
【００９９】
を満たす。
【０１００】
しかしながら、定常分布ｓは、予め決まっていないため、最後の２つの等式は、Ａｉの全ての行を必要とし、小行列Ｐを簡潔に計算するという目標を無効にする。
【０１０１】
こうした部分的計算は、自己ループを持たない無向グラフについては完全に実行可能である。Ｗが対称で、且つ、ゼロ対角成分（zero-diagonal）であると、式（２４）のＱは、ラプラシアンｄｉａｇ（Ｗ１）−Ｗがゼロ固有値を有するために、ラプラシアンカーネル
【０１０２】
【数３１】
【０１０３】
すなわち、擬似逆転へと単純化される。ラプラシアンは、擬似逆転がブロックのより小さい特異値分解によって計算されることを可能にする疎なブロック構造を有するが、これでさえも、極めて難しい可能性がある。
【０１０４】
擬似逆転は、ゼロ特異値を１にシフトし、級数展開によって逆転し、その後、特異値をゼロに戻すことによって、完全に回避することができる。これらの操作は、等式
【０１０５】
【数３２】
【０１０６】
において集められ、ここで、
【数３３】
である。
【０１０７】
構成によると、中括弧｛・｝内の項は、ｉ≦１について、スペクトル半径＜１を有する。そのため、逆転及びＰの列の任意の部分集合は、直接的な加法反復によって計算することができる。
【０１０８】
これらの計算を疎行列逆転によって表現する（couch）１つの利点は、顧客による一連の購入等の新しいデータを、逆転の低ランク更新のための、シャーマン−ウッドベリ−モリソン（Sherman-Woodbury-Morrison）公式を使用して、軽い計算によってモデルに組み入れることができることである。
【図面の簡単な説明】
【０１０９】
【図１】本発明によって使用される製品評価の関係データベースのブロック図である。
【図２】本発明に従って製品を提案する方法のフロー図である。
【図３Ａ】本発明による例示的な疎なグラフである。
【図３Ｂ】本発明による例示的な密なグラフである。
【図４Ａ】図３Ａのグラフについて、対応する分類スコアを比較するグラフである。
【図４Ｂ】図３Ｂのグラフについて、対応する分類スコアを比較するグラフである。
【図５】本発明に従って行われた平均的な提案の評価を比較する棒グラフである。
【図６】統計量に基づく提案を比較するグラフである。
【図７】本発明によって行われた提案の表である。
【図８】年齢の条件として、映画ジャンルへの関心を示すグラフである。
【技術分野】
【０００１】
本発明は、包括的に、協調フィルタリングに関し、より詳細には、マルコフ連鎖による協調フィルタリングに関する。
【背景技術】
【０００２】
従来技術の協調フィルタリングシステムは、通常、或る製品についての消費者の嗜好を、消費者の属性、並びに、その製品を好む他の消費者の属性に基づいて予測する。本明細書で使用される「製品」という用語は、商品等の有形の製品、並びに、サービス、映画、テレビ番組、本、ウェブページ、スポーツ、娯楽、又は、「評価される（rated）」ことができる他のあらゆるものを意味し得ることに留意されたい。「消費者」という用語は、ユーザ、閲覧者、読み手等を意味し得る。一般に、年齢及び性別等の属性は消費者に関連し、ジャンル、コスト、又は製造業者等の属性は、製品に関連する。
【０００３】
協調フィルタリングは、一般に、欠測値問題として扱うことができる。製品評価表は、一般に、非常に疎である。すなわち、考え得る製品の非常に大きなセット（集合）内の任意の１つの製品について、評価は、非常に小さな消費者の部分集合から利用可能なだけである。通常、目的は、個々の消費者の好みと一貫性のある順序付けで、欠測値を予測し、且つ／又は、未評価アイテムを並べる（rank）ことである。システムは、提案を行うのに、これらの予測を使用する。
【０００４】
協調フィルタリングは、以下の米国特許、すなわち第６，４９６，８１６号「Collaborative filtering with mixtures of Bayesian networks」、第６，４８７，５３９号「Semantic based collaborative filtering」、第６，３２１，１７９号「System and method for using noisy collaborative filtering to rank and present items」、第６，１１２，１８６号「Distributed system for facilitating exchange of user information and opinion using automated collaborative filtering」、第６，０９２，０４９号「Method and apparatus for efficiently recommending items using automated collaborative filtering and feature-guided automated collaborative filtering」、第６，０４９，７７７号「Computer-implemented collaborative filtering based method for recommending an item to a user」、第６，０４１，３１１号「Method and apparatus for item recommendation using automated collaborative filtering」、及び、以下の米国公開出願、すなわち第２００４／００５４５７２号「Collaborative filtering」、第２００３／００５５８１６号「Recommending search terms using collaborative filtering and web spidering」、第２００２／００６５７９７号「System, method and computer program for automated collaborative filtering of user data」に記載されている。
【０００５】
技術的見地及び科学的見地からの協調フィルタリングの広範な調査は、Gediminas Adomavicius及びAlexander Tuzhilin著「Recommendation technoligies: Survey of current methods and possible extensions」University of Minnisota, USA, MISRC WP 03-29, 2004によって提供されている。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従来技術の方法は、他の同様な消費者によって行われる選択を組み合わせることによって、消費者の選択を実質的に予測する。従来技術の協調フィルタリングシステムに伴う１つの問題は、類似（similarity）メトリックが、データから学習されるのではなく、システム設計者によって決定されることである。
【０００７】
データ内の任意の２つのアイテム間の類似が、データ内の全ての関係によって知らされることが望ましい。これは、消費者間の関係と、製品間の関係の両方を含む。
【０００８】
従来技術の協調フィルタリングシステムに伴う別の問題は、データのサンプリングアーチファクトに対する感度である。これは、曖昧であるが、個人的に適切な製品よりも、一般的に人気のある製品を提案する方への偏りを生成することが多い。この偏りを取り除くことが望ましい。
【課題を解決するための手段】
【０００９】
［発明の概要］
本発明は、製品についての消費者の嗜好を、重み付き関連付け（association）グラフ上でのランダムウォークとしてモデル化する。グラフは、消費者、消費者属性、製品及び製品属性を連結する、関係データベースから導出される。
【００１０】
ランダムウォークは、マルコフ連鎖によって記述される。マルコフ連鎖は、全ての知られている消費者にわたって特定の消費者の嗜好を融合する。個々の消費者は、マルコフ連鎖の現在の状態によって識別される。
【００１１】
ランダムウォークは、情報検索を容易にする類似測度（measure）をもたらす。連鎖内の２つの状態間の類似測度は、その２つの状態から連鎖の残りの状態までの期待通過（travel）時間の間の相関である。相関は、連鎖の２つの状態を記述する２つのベクトルの間の角度の余弦として計算される。この測度は、個々の消費者によって行われる将来の選択を非常によく予測でき、提案及び分類用途に有益である。類似測度は、疎行列の逆転又は疎行列−ベクトル乗算の反復によって得られる。
【発明を実施するための最良の形態】
【００１２】
［好ましい実施形態の詳細な説明］
図１は、製品評価の例示的な関係データベース１００の一部を示す。消費者１０１は、消費者属性１１１〜１１３と関連する（符号１１０）。製品１０２は、製品属性１２１〜１２３と関連する（符号１２０）。消費者は、４という評価１３０を製品に与えた。データベースは、多くの異なる消費者によって行われた多くの製品評価を記憶することができることが理解されるべきである。
【００１３】
図２に示すように、関係データベース１００は、有向エッジによって接続されたノードのグラフ２１１に変換される（符号２１０）。グラフ上でマルコフ連鎖ランダムウォークを実施することによって、統計量（statistics）が決定される（符号２２０）。ランダムウォークは、連鎖の現在の状態が個々の消費者を表すマルコフ連鎖を生成する。状態の統計量は、余弦相関２２１及び期待割引（discounted）利益２２２を含む。提案２３２を行うために、クエリ状態２３１に応答して、統計量がソートされる（符号２３０）。
【００１４】
本発明は、関係データベース１００を表す重み付き関連付けグラフ２１１のランダムウォーク２２０に基づいて提案を行う協調フィルタリングシステムを提供する。関連付けは、消費者の属性と製品の属性の間で行われる。
【００１５】
連鎖の状態間の期待通過時間は、類似測度への自然な変換を有する距離メトリックをもたらす。類似測度は、状態間の余弦相関２２１である。この測度は、従来のグラフベースの相違測度と比べて個々の消費者の嗜好をずっとよく予測できる。利点として、ランダムウォーク２２０は、従来の協調フィルタリングの通常の「誰が何を好きだったか（who-liked-what）」に勝る文脈情報を組み入れることができる。
【００１６】
本発明はまた、非常に大きなグラフ上で機能することができる近似戦略を提供する。近似により、状態の期待割引利益２２２等の従来通りに有益な統計量を決定すること（符号２２０）が実用的になり、利益を最適化する提案２３２を作成することができる。
【００１７】
マルコフ連鎖の統計量
疎で、任意に重み付けされた、非負の行列は、有向の関連付けグラフ３１１のエッジを指定する。エッジは、イベントのカウントを表す。すなわち、エッジＷｉｊは、イベントｉがイベントｊを伴う回数である。たとえば、ユーザｉ１０１が映画ｊ１０２を評価した時、Ｗｉｊは、ゼロより大きい。
【００１８】
本発明は、行列Ｗによって指定される有向グラフ２１１上でランダムウォークを実施する。行を正規化した確率行列Ｔ＝ｄｉａｇ（Ｗ１）−１Ｗは、関連付けされたマルコフ連鎖の状態の推移確率を記憶し、ここで、１は複数の１からなるベクトルである。
【００１９】
マルコフ連鎖は既約であり（irreducible）、到達できない（unreachable）状態又は吸収的な（absorbing）状態はないと考えられる。連鎖は非対称であることができ、自己遷移は、繰り返されたイベントの発生をモデル化する。行列Ｗの統計量が、母集団の集合的振る舞いの公正なサンプルから導出される場合、短期間にわたって、グラフ２１１上でのランダムウォーク２２０は、母集団から無作為に抽出された個々の消費者の嗜好をモデル化する。
【００２０】
ランダムウォークの種々の統計量が、予測タスクにとって有益である。定常分布は、無限に長いランダムウォークにおいて各状態を横切る相対頻度を記述する。連鎖における状態が、消費者によって使用される製品を表す場合、比較的大きな統計量は、人気のある製品を指示する。
【００２１】
形式的に、定常分布は、
【数１】
及びｓＴ１＝１を満たす。行列Ｗが対称である場合、定常分布ｓ＝（１ＴＷ）／（１ＴＷ１）である。その他の場合、分布は、反復（recurrence）ｓｉ＋１Ｔ←ｓｉＴＴ，ｓ０＝１／Ｎから決定することができる。
【００２２】
反復時間：ｒｉ＝ｓｉ−１は、同じ状態への２回の連続する訪問の間の期待時間を記述する。反復時間は、以下に述べる、自己コミュート（self-commute）時間、すなわちＣｉｉ＝０と混同されるべきではない。
【００２３】
状態ｉから「ヒット」状態ｊまでのランダムウォークについての期待ヒット時間は、
【００２４】
【数２】
【００２５】
から決定することができ、ここで、ｆは、ｓと直交しない任意の非ゼロベクトルであり、Ｔは、
【００２６】
【数３】
【００２７】
による、転置演算子であり、期待ラウンドトリップコミュート時間は、
【００２８】
【数４】
【００２９】
である。
【００３０】
ｆ＝ｓである時、行列Ａは、基本行列の逆行列である。提案２３２を作成するために、２つの相違測度Ｃｉｊ及びＨｉｊを使用することができる。しかしながら、これらの相違測度は、定常分布によって支配される可能性がある。これによって、個々の消費者の好みにかかわらず、人気のある同じ製品が、全ての消費者に提案される。
【００３１】
図５は、上記統計量を使用して、本発明に従って行った平均的な提案の評価を比較する。たとえば、閲覧者がどの映画を観て好きになるかを予測することについて、余弦相関は、全ての他の測度のほぼ２倍有効である。
【００３２】
ランダムウォーク相関
本発明は、情報検索の最も有益な統計量のうちの１つ、すなわち余弦相関２２１をランダムウォークに結合する。情報検索において、データアイテムは、ベクトルで表されることが多い。ベクトルは、アイテムの種々の属性、たとえば、文書中の特定の語句の頻度を「カウントする」。２つのアイテムは、その属性ベクトルの内積が大きい時、類似であると考えられる。この例では、文書は、語句の特定の分布を生成する「プロセス」のサンプルである。より長い文書は、分布のサンプリングを増加させ、より多数の語句及びより大きな内積をもたらす。しかしながら、より大きな内積は、類似の程度を増加させるべきではない。
【００３３】
この「サンプリングアーチファクト」をなくすために、情報検索は、２つの属性ベクトル間の角度を測定する。この角度の余弦は、正規化されたベクトルの内積に等しい。角度の余弦はまた、２つの分布の間の実験的な相関を測定する。
【００３４】
ランダムウォークの相関２２１を取得する重要なアイデアは、これにより、ランダムウォークの長期の振る舞いを幾何学的にモデル化することが可能になることである。
【００３５】
ラウンドトリップコミュート時間の平方根は、三角不等式√Ｃｉｊ＋√Ｃｊｋ≧√Ｃｉｋ、対称√Ｃｉｊ＝√Ｃｊｉ、及び、恒等式√Ｃｉｊ＝０を満たす。コミュート時間を２乗距離
【数５】
と同一視することは、各状態が或る点に割り当てられた状態で、ユークリッド空間におけるマルコフ連鎖の幾何学的埋め込みを提供する。
【００３６】
ユークリッド埋め込みにおいて、同様な状態は、頻繁に訪れる状態を原点の近くに配置した状態で、ほとんど同じ場所に配置される。しかしながら、コミュート時間と同様に、人気があるが、おそらく相違する状態の近接性により、ユークリッド距離がほとんどの用途に適さなくなる。
【００３７】
上述したように、相関２２１は、この中心性（centrality）を排除する。相関は、状態ｉ及びｊの属性ベクトルｘｉ、ｘｊの間の角度（ｘｉ，ｘｊ）の余弦である。
【００３８】
角度の余弦を取得するために、２乗距離Ｃの行列は、
【００３９】
【数６】
【００４０】
であることを遵守することによって、内積Ｐの行列に変換される。
【００４１】
２重中心化（double-centering）
【００４２】
【数７】
【００４３】
によって、行平均Ｐｉｉ=ｘｉＴｘｉ及び列平均Ｐｊｊ=ｘｊＴｘｊが、行列Ｃから除去され、Ｐｉｊ＝ｘｉＴｘｊが生じる。そのため、余弦相関２２１は、角度
【００４４】
【数８】
【００４５】
の余弦である。
【００４６】
付録Ａは、密行列Ｃを決定することなく、疎行列Ｔ及びＷから直接に行列Ｐを決定する方法を記述する。対称であるゼロ対角行列Ｗの特別な場合について、行列Ｐは、グラフラプラシアンｄｉａｇ（Ｗ１）−Ｗの擬似逆転へと単純化される。
【００４７】
余弦相関２２１はまた、幾何学的な解釈を有する。一般的な人気の影響を除去するために、全ての点が単位超球（unit hyper-sphere）上に投影され、その対ごとのユークリッド距離が、
【数９】
と示される場合、
【００４８】
【数１０】
【００４９】
である。
【００５０】
この埋め込みでは、１つの点の別の点との相関は、ユークリッド距離の２乗和が減少するにつれて増加する。これは、合計され且つ平均された相関を、２つの状態グループの間の類似を測定するための、幾何学的に意味のある方法にする。
【００５１】
大きなマルコフ連鎖において、ノルム
【数１１】
は、状態のほぼ逆転した「人気」である、反復時間ｒｉ＝ｓｉ−１の、所定の規模までの精密な近似である。したがって、余弦相関２２１は、一様でないサンプリングによるアーチファクトを減らす類似測度として解釈することができる。
【００５２】
たとえば、２つのウェブ「ページ」が、非常に人気がある場合、任意の他のページからいずれかのページを訪問する期待時間は短く、２つのページは互いのコミュート時間が短い。しかしながら、２つのページが、通常、異なる人々によってアクセスされるか、異なる属性のセットと関連する場合、属性ベクトル間の角度の余弦は大きく、相違を意味する。
【００５３】
同様に、映画のデータベースの場合、恐怖スリラー「羊たちの沈黙」から子供向け映画「フリーウィリー」までのコミュート時間は、いずれかの映画への平均コミュート時間より短い。これは、両方の映画が非常に人気があったためである。しかし、それらの属性ベクトル間の角度は、それらの聴衆にほとんど重なりが存在しないため、平均より大きい。
【００５４】
しかしながら、密なＮ×Ｎ行列を構築し、且つ逆転することは、約Ｎ３回の操作を必要とし、大きなマルコフ連鎖にとって明らかに実用的でない。これはまた、ほとんどのクエリが、行列Ｐ及び余弦行列の小行列を含むだけであるため無駄が多い。付録Ａは、小行列が、疎なマルコフ連鎖パラメータから直接推定することができる方法を記述する。
【００５５】
提案及び分類
提案を行うために、クエリ状態２３１が選択され、マルコフ連鎖の他の状態が、クエリ状態２３１に対する、対応する余弦相関２２１に従ってソートされる（符号２３０）。クエリ状態は、消費者属性、製品属性、又は、消費者属性と製品属性の両方を表すことができる。
【００５６】
このモデルによる提案は、半教師あり（semi-supervised）分類問題に関連する。そこでは、状態は、ラベル付けされた（分類された）点及びラベル付けされていない（分類されていない）点として、ユークリッド空間内に埋め込まれる。類似測度は、ラベル付けされていない点とラベル付けされた点の間で決定される。完全な教師あり（fully supervised）分類と違って、ラベル付けされていない点とラベル付けされた点の間の類似は、空間内の他のラベル付けされていない点の分布によって媒介され、他のラベル付けされていない点の分布は、全体のデータセットにわたって距離メトリックに影響を与える。
【００５７】
同様に、グラフ２１１上でのランダムウォークにおいて、２つの状態間の類似は、グラフのランダムウォークによって実施される全ての可能な経路の分布に依存する。
【００５８】
図３Ａ及び図３Ｂはこれを示す。２０個の点３０２からなる弧によって囲まれた、２Ｄ平面の２つのガウスクラスタ内に、８０個の点３０１が配列される。図３Ａは、全ての点を、そのｋ個の最近傍に接続する疎なグラフである。
【００５９】
図３Ｂは、全ての点を所定の距離内の全ての近傍に接続する密なグラフである。エッジの重みは、ユークリッド距離、たとえば、
【数１２】
の急速減衰関数に従う。各頂点ドットのサイズは、その分類スコアの大きさを指示する。ゼロより大きいスコアを有する頂点は、弧に属するものとして分類される。
【００６０】
連結性（connectivity）及びエッジの重みは、ユークリッド距離に大まかに関連するが、類似は、グラフによって完全に媒介される。各グラフ内の３つのラベル付けされた点３１１（１つは弧上に、１つは各クラスタ上にある）は２つのクラスを表す。残りの点は、正規化された組み合わせラプラス関数であり、且つ、０＜α＜１が所定の正則化パラメータである、類似測度
【数１３】
に従って分類することができる。
【００６１】
図４Ａ及び図４Ｂは、グラフ２１１上でのランダムウォーク２２０の余弦相関２２１を使用して、点が分類される方法を示す。分類は、ラベル付けされた点に対する相関を合計するか、又は平均することによって実施される。グラフの頂点のサイズで示す分類スコアは、２つのクラスについての提案スコア間の差である。
【００６２】
図４Ａ及び図４Ｂは、エッジをグラフに加える基準が変わる時の分類の対応する変動を示す。余弦相関及びコミュート時間は共に、グラフ内のエッジの密度が変動する時に、比較的安定である直感的に正確な分類を与えるという意味で、うまく働く。余弦相関は、かなり広い分類裕度（classification margin）を提供し、したがって、グラフ内の小さな変化に対する安定性を提供する。
【００６３】
正規化されたコミュート時間（Ｉ−αＮ）−１、到達時間（hitting time）、逆転到達時間、及びそれらの正規化された変形は、密なグラフ上で適切に分類されるが、疎なグラフ上では不適切に分類される。この例から、余弦相関２２１は、関連付けグラフ２１１において、小さな変動下では一貫した提案を与えることが期待される。
【００６４】
期待利益
消費者は、関心のある製品を見出すことに関心があるが、販売業者は、利益の多い製品を提案することを好むであろう。消費者が、将来、追加の製品を取得することになり、その購入決定が利幅（profit margin）と無関係であると仮定すると、決定理論により、最適な戦略は、所定の期間にわたって割り引かれる、期待利益が最大になる製品（状態）を提案することが示される。すなわち、販売業者は、ランダムウォークが、そこから、非常に利益の多い状態、したがって、「目玉商品」等の小売戦略を通過する状態に消費者を「押しやりたい」と思う。さらに、これらの利益の多い状態は、ランダムウォークの早期において横切られるべきである。
【００６５】
それぞれの状態についての、利益又は損失のベクトルは、
【数１４】
であり、割引係数ｅ−β，β＞０は、将来の利益の時間値を決定する。ｉ番目の状態の期待割引利益２２２νｉは、到着時間について割り引かれた、ｉ番目の状態からの全ての到達可能な状態の平均化した利益である。ベクトル形式で、
【数１５】
である。
【００６６】
単位スペクトル半径より小さい（λｍａｘ（Ｘ）＜１）行列について恒等式
【数１６】
を使用して、上記級数（series）は、疎な線形系
【数１７】
として配列される。
【００６７】
たとえば、状態ｉにおいて、消費者にとって最も利益の多い提案は、最も多い期待割引利益
【数１８】
を有する、状態ｉの近傍の状態ｊである。
【００６８】
マルコフ連鎖における状態が、現在の状態からｋステップのところにある製品を表す場合、適切な項は、
【数１９】
である。
【００６９】
図６は、種々の統計量に基づいて提案を比較する。長期利益を最大にする提案を行うことは、狭義に利益の多い製品を提案することより遥かに効果的な戦略であり、利益の見通しなしの提案は、全く利益を生まない。
【００７０】
市場分析
本発明による方法は、マルコフ連鎖内の任意の状態から提案２３２を作成することができるため、特定の消費者人口統計に関して特に効果的である製品、又は、特定の製品種類に特に忠実である消費者を識別することが可能である。
【００７１】
たとえば、映画データベースは、J. Herlocker, J. Konstan, A. Borchers及びJ. Riedl著「An algorithmic framework for performing collaborative filtering」に記載されるように、映画の評価、並びに、消費者の性別及び年齢を記憶する。本発明による方法を、性別による嗜好を決定するデータベースに適用した。
【００７２】
図７は、各性別について、最上位の１０の提案を示す。図７に示すように、これらの状態からのコミュート時間又は期待到達時間によって映画を評価することは、評価が定常分布評価とほとんど同じであるため、無益であることがわかる。データベース内の消費者のほとんどが男性であるため、これは、男性については理解できる。しかしながら、余弦相関による評価は、男性がアクション映画及びＳＦ映画を好み、女性が恋愛映画及びドラマを好むという、２つの非常に異なる一覧を生成する。
【００７３】
図８に示すように、同じ方法は、特定の年齢層の消費者によって、どのジャンルが優先的に鑑賞されるかを決定することができる。図８は、年齢が実際には、ジャンル嗜好を予測しにくいことを示している。年齢のジャンル嗜好に対する相関は、弱いが、明らかに、ＳＦ映画８０２への関心が、１０代及び２０代でピークに達することを示している。その直後、冒険映画８０１への関心がピークに達し、ドラマ８０３及びフィルムノワール８０４への関心が上昇し始める。
【００７４】
発明の効果
関連付けグラフのランダムウォークは、関係データベースにおいて、類似性の関係を決定する自然な方法である。ランダムウォークは、協調フィルタリングアプリケーションにおいて、人口統計及び製品種類等の、広範囲な文脈情報を利用する方法を提供する。
【００７５】
本発明は、新規な類似測度、すなわち、関係データベースを表す重み付きグラフのランダムウォークにおける２つの状態の余弦相関を導出する。この測度は、提案用途及び分類用途について非常によい予測を行うことができる。
【００７６】
相関ベースの評価は、従来技術のコミュート時間、到達時間、及び関連するグラフベースの相違測度に基づく評価に比べて、よりよく予測でき、グラフのエッジセットの摂動に対してロバストである。
【００７７】
本発明は好ましい実施形態の例として述べられたが、本発明の精神及び範囲内で、種々の他の適応及び修正が行われてもよいことが理解される。したがって、本発明の真の精神及び範囲内に入る、全てのこうした変形及び修正を包含することが、添付の特許請求の範囲の目的である。
【００７８】
付録Ａ
【００７９】
実施戦略
Ｎ＞＞１０３の状態を有する連鎖について、コミュート時間の完全行列、又は、さらに、
【数２０】
の形態の大きな逆行列を決定することは実用的でない。資源要求を最小にするために、ほとんどの計算が（Ｉ−Ｘ）−１Ｇの形態を有することが利用され、ここで、行列Ｘ及びＧは疎である。多くのクエリについて、可能な状態の部分集合のみが比較される。行列Ｇが疎であるため、行列の逆転の列の小さな部分集合のみが必要である。これらは、級数展開
【数２１】
によって計算することができ、級数展開は、高速混合の疎なマルコフ連鎖について良好な近似をもたらすために、打ち切ることができる。特に、加法級数のｎ項の合計は、乗法展開による２ｌｏｇ２ｎの疎な行列の乗算によって評価することができる。逆転の任意の１つの列について、これは、疎行列−ベクトル積に帰着する。
【００８０】
１つの問題は、これらの級数が、単位スペクトル半径（λｍａｘ（Ｘ）＜１）より小さい行列についてしか収束しないことである。一致しない逆転について、関連する級数展開は、数値的に正確な結果を取得するために、増分的に除去することができる発散成分を有する。たとえば、到達時間の場合、Ｘ＝Ｔ＋１ｓＴであり、このスペクトル半径は２である。加法級数を展開することによって、１ｓＴの望ましくない倍数が、合計に急速に蓄積する。代わりに、望ましくない倍数を除去する反復が、必要に応じて（as the arise）
【００８１】
【数２２】
【００８２】
として構築され、ｉが無限に近づくにつれ、
【００８３】
【数２３】
【００８４】
に収束する。
【００８５】
これは、Ａｉ及びＢｉの列の任意の部分集合を計算するのに容易に適合し、Ｈの小行列を簡潔に計算することに留意されたい。ｉ＜Ｎであっても、疎な連鎖は、迅速に混合する傾向があるため、Ｂｉは、定常分布１ｓＴに急速に収束し、Ａｉは、良好な近似である。乗法級数についてのより高速な収束漸化式は、
【００８６】
【数２４】
【００８７】
として構築することができる。
【００８８】
これは、指数関数的に高速に収束するが、全てのＢｉの計算を必要とする。両方の反復において、ｓの代わりに１／Ｎを用いることができる。これは、最終の計算で除去される列の平均をシフトさせる。
【００８９】
【数２５】
【００９０】
収束したＢｉ＝１ｓＴから、反復時間ｒｉ＝ｓｉ−１を取得することができる。マルコフ連鎖パラメータから直接に内積行列Ｐを計算することが可能である。
【００９１】
【数２６】
【００９２】
である、恒等式
【００９３】
【数２７】
【００９４】
は、展開及び置換によって検証することができる。Ｐの小行列について、上記反復の適した変形を使用して、Ｑの対応する列を計算することだけが必要とされる。
【００９５】
再び、ｓ及びｒが、反復前に知られていない場合、置換ｓ→１／Ｎを行うことができる。収束において、結果として得られる
【数２８】
は、
【００９６】
【数２９】
【００９７】
及び、
【００９８】
【数３０】
【００９９】
を満たす。
【０１００】
しかしながら、定常分布ｓは、予め決まっていないため、最後の２つの等式は、Ａｉの全ての行を必要とし、小行列Ｐを簡潔に計算するという目標を無効にする。
【０１０１】
こうした部分的計算は、自己ループを持たない無向グラフについては完全に実行可能である。Ｗが対称で、且つ、ゼロ対角成分（zero-diagonal）であると、式（２４）のＱは、ラプラシアンｄｉａｇ（Ｗ１）−Ｗがゼロ固有値を有するために、ラプラシアンカーネル
【０１０２】
【数３１】
【０１０３】
すなわち、擬似逆転へと単純化される。ラプラシアンは、擬似逆転がブロックのより小さい特異値分解によって計算されることを可能にする疎なブロック構造を有するが、これでさえも、極めて難しい可能性がある。
【０１０４】
擬似逆転は、ゼロ特異値を１にシフトし、級数展開によって逆転し、その後、特異値をゼロに戻すことによって、完全に回避することができる。これらの操作は、等式
【０１０５】
【数３２】
【０１０６】
において集められ、ここで、
【数３３】
である。
【０１０７】
構成によると、中括弧｛・｝内の項は、ｉ≦１について、スペクトル半径＜１を有する。そのため、逆転及びＰの列の任意の部分集合は、直接的な加法反復によって計算することができる。
【０１０８】
これらの計算を疎行列逆転によって表現する（couch）１つの利点は、顧客による一連の購入等の新しいデータを、逆転の低ランク更新のための、シャーマン−ウッドベリ−モリソン（Sherman-Woodbury-Morrison）公式を使用して、軽い計算によってモデルに組み入れることができることである。
【図面の簡単な説明】
【０１０９】
【図１】本発明によって使用される製品評価の関係データベースのブロック図である。
【図２】本発明に従って製品を提案する方法のフロー図である。
【図３Ａ】本発明による例示的な疎なグラフである。
【図３Ｂ】本発明による例示的な密なグラフである。
【図４Ａ】図３Ａのグラフについて、対応する分類スコアを比較するグラフである。
【図４Ｂ】図３Ｂのグラフについて、対応する分類スコアを比較するグラフである。
【図５】本発明に従って行われた平均的な提案の評価を比較する棒グラフである。
【図６】統計量に基づく提案を比較するグラフである。
【図７】本発明によって行われた提案の表である。
【図８】年齢の条件として、映画ジャンルへの関心を示すグラフである。
【特許請求の範囲】
【請求項１】
協調フィルタリングのためのコンピュータ実施方法であって、
消費者属性、製品属性、及び製品評価を含む関係データベースを、エッジによって接続されるノードのグラフに変換すること、
前記グラフ上で、マルコフ連鎖ランダムウォークの統計量を決定すること、及び、
該統計量に従って、前記マルコフ連鎖の状態を、クエリ状態に応答してソートして、提案を行うこと
を含む協調フィルタリングのためのコンピュータ実施方法。
【請求項２】
前記マルコフ連鎖の現在の状態は、個々の消費者を識別する、請求項１に記載の方法。
【請求項３】
前記統計量は、前記ランダムウォークの状態間の相関を含んでおり、前記方法は、
２つの状態の類似の程度を、該２つの状態から全ての他の状態までの期待通過時間に従って測定することをさらに含む、請求項１に記載の方法。
【請求項４】
前記グラフは、重み付き関連付けグラフであり、前記マルコフ連鎖の状態間の期待通過時間は、前記２つの状態間の相違測度に対応する距離メトリックをもたらす、請求項３に記載の方法。
【請求項５】
非負行列が、前記エッジ及び関連する重みを指定し、より大きな重みが、特定のユーザと特定の製品の間のより大きな類似性を指示する、請求項３に記載の方法。
【請求項６】
行を正規化した確率行列が、前記ランダムウォークにおける推移確率を指定する、請求項５に記載の方法。
【請求項７】
前記統計量は、前記製品を提案するための期待割引利益を含む、請求項１に記載の方法。
【請求項８】
前記クエリ状態は消費者属性を表す、請求項１に記載の方法。
【請求項９】
前記クエリ状態は製品属性を表す、請求項１に記載の方法。
【請求項１０】
前記クエリ状態は消費者属性及び製品属性を表す、請求項１に記載の方法。
【請求項１１】
協調フィルタリングシステムであって、
消費者属性、製品属性、及び製品評価を含む関係データベースと、
該関係データベースから導出されるエッジによって接続されるノードのグラフと、
該グラフ上のマルコフ連鎖ランダムウォークの統計量と、
該統計量に従って、前記マルコフ連鎖の状態を、クエリ状態に応答してソートして、提案を行う手段と
を備えた協調フィルタリングシステム。
【請求項１】
協調フィルタリングのためのコンピュータ実施方法であって、
消費者属性、製品属性、及び製品評価を含む関係データベースを、エッジによって接続されるノードのグラフに変換すること、
前記グラフ上で、マルコフ連鎖ランダムウォークの統計量を決定すること、及び、
該統計量に従って、前記マルコフ連鎖の状態を、クエリ状態に応答してソートして、提案を行うこと
を含む協調フィルタリングのためのコンピュータ実施方法。
【請求項２】
前記マルコフ連鎖の現在の状態は、個々の消費者を識別する、請求項１に記載の方法。
【請求項３】
前記統計量は、前記ランダムウォークの状態間の相関を含んでおり、前記方法は、
２つの状態の類似の程度を、該２つの状態から全ての他の状態までの期待通過時間に従って測定することをさらに含む、請求項１に記載の方法。
【請求項４】
前記グラフは、重み付き関連付けグラフであり、前記マルコフ連鎖の状態間の期待通過時間は、前記２つの状態間の相違測度に対応する距離メトリックをもたらす、請求項３に記載の方法。
【請求項５】
非負行列が、前記エッジ及び関連する重みを指定し、より大きな重みが、特定のユーザと特定の製品の間のより大きな類似性を指示する、請求項３に記載の方法。
【請求項６】
行を正規化した確率行列が、前記ランダムウォークにおける推移確率を指定する、請求項５に記載の方法。
【請求項７】
前記統計量は、前記製品を提案するための期待割引利益を含む、請求項１に記載の方法。
【請求項８】
前記クエリ状態は消費者属性を表す、請求項１に記載の方法。
【請求項９】
前記クエリ状態は製品属性を表す、請求項１に記載の方法。
【請求項１０】
前記クエリ状態は消費者属性及び製品属性を表す、請求項１に記載の方法。
【請求項１１】
協調フィルタリングシステムであって、
消費者属性、製品属性、及び製品評価を含む関係データベースと、
該関係データベースから導出されるエッジによって接続されるノードのグラフと、
該グラフ上のマルコフ連鎖ランダムウォークの統計量と、
該統計量に従って、前記マルコフ連鎖の状態を、クエリ状態に応答してソートして、提案を行う手段と
を備えた協調フィルタリングシステム。
【図１】
【図２】
【図３Ａ】
【図３Ｂ】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３Ａ】
【図３Ｂ】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００６−２２８２１４（Ｐ２００６−２２８２１４Ａ）
【公開日】平成１８年８月３１日（２００６．８．３１）
【国際特許分類】
【外国語出願】
【出願番号】特願２００６−３５３４４（Ｐ２００６−３５３４４）
【出願日】平成１８年２月１３日（２００６．２．１３）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公開日】平成１８年８月３１日（２００６．８．３１）
【国際特許分類】
【出願番号】特願２００６−３５３４４（Ｐ２００６−３５３４４）
【出願日】平成１８年２月１３日（２００６．２．１３）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]