無限次元を用いた高速行列因子分解による推薦システム
無限次元の行列因子分解を用いて協調フィルタリングを行うこと、協調フィルタリングを用いて１つまたは２つ以上の推薦を生成すること、推薦をユーザに表示すること、により推薦を生成するシステムおよび方法が開示される。
【発明の詳細な説明】
【背景技術】
【０００１】
推薦システムは、ａｍａｚｏｎ．ｃｏｍおよびｎｅｔｆｌｉｘ．ｃｏｍのようなサイトを通じて普及してきた。これらのシステムは、製品、例えば映画に対する多くのユーザの評価のデータベースを解析し、未見／未購入の製品に対するユーザの評価／嗜好に関する予測を行う。多くの最先端技術の推薦システムは、「協調フィルタリング」に依存してユーザの嗜好やパターンを見いだしている。該技術は、ユーザデータを、例えば行がユーザごとに指標を付けられ、次に列が製品ごとに指標を付けられた１次元の大きな行列として解釈する。行列の要素は製品に対するユーザの評価である。該行列は、ユーザおよび製品の数が多いので通常大きくなり、各ユーザが少数の製品に対する評価を与えていたものなので非常に疎な行列になる。次に、協調フィルタリングは、これらの製品について観測された評価のパターンを解析し、該製品の未観測の／欠損している評価に対する予測を行う。莫大で疎な評価行列の豊富な構造を見いだすために、実証的研究は要素の数が十分に大きくあるべきであることを示した。この意味で、協調フィルタリングは行列補完問題となる。
【０００２】
従来の技術は、データがＭ×Ｎ（ここで、ＭはＮ個の製品に対するユーザの評価数を表す）の行列としてデータベースに保存される低階数行列因子分解法を含んでいる。行列の評価のほんの一部のみが観測されるので、該行列はかなり大きくて疎な行列になる。低階数因子分解法は、行列を、１つはユーザ固有の要素、もう１つは製品固有の要素を表す２つの行列の積に因子分解する。最適化手順を用いて、データについて最も良く説明することができる要素を見つける。ユーザ要素または製品要素のいずれか一方の数は有限である。製品に対するユーザの評価の予測は、ユーザの要素ベクトルおよび製品の要素ベクトルを検索し、次に結果を与えるそれらの内積を計算することによって行われる。オンラインユーザデータの完全な成長によって、正確でスケーラブルな学習アルゴリズムを開発することが大きな課題となっている。
【０００３】
協調フィルタリングの最近の進歩が、低階数行列因子分解法の成長を刺激した。協調フィルタリングの低階数行列因子分解アルゴリズムは、概略非確率的手法と確率的手法とに分類することができる。最近のネットフリックス（Ｎｅｔｆｌｉｘ）コンテストでは、行列因子分解法（ｍａｔｒｉｘ ｆａｃｔｏｒｉｚａｔｉｏｎ ｔｅｃｈｎｉｑｕ）が参加者のランキングで非常に人気がある。行列因子分解がユーザ要素数と映画要素数との乗算によって適用される場合、要素の両面が行列因子分解によって見つかる。計算効率に関して、すべての技法は要素数が少ないと仮定している。したがって、行列の因子分解は低階数因子分解となる。しかしながら、多種多様なユーザパターンには説明すべき多くの要素が必要なので、システムの階数を制限することは、予測精度を低下させる場合が多い。
【発明の概要】
【０００４】
無限次元の行列因子分解を用いて協調フィルタリングを行うこと、協調フィルタリングを用いて１つまたは２つ以上の推薦を発生させること、推薦をユーザに表示することによって、推薦を生成するシステムおよび方法が開示される。
【０００５】
好ましい実施形態の利点は、次の１つまたは２つ以上のものを含んでいてもよい。推薦システムは、非常に大きな数の要素または無限の数の要素すら用いる協調フィルタリング技法を用いる。インスタントフィルタリング技術は、ユーザの評価／嗜好に対する正確な予測を行う高い精度を維持しながら、大量のデータを効率的に処理する拡張性および効率性を提供する。能力が増強されたことにより、システムはユーザの評価／嗜好をより正確に予測することができる。システムが非常に大規模なユーザの評価用データベースにスケーリングできるように、計算は効率的に行われる。システムは、ユーザの嗜好に関してよりよい理解を持つ必要があるオンラインストア、ニュースウェブサイト、オンライン広告を含む多くのオンラインサービスのパフォーマンスを改善することができる。ユーザ満足度および事業収益の両方を改善することができるように、システムを用いて、広範囲のユーザが示す嗜好を明示的な方法（例えば数的な評価）でまたは暗黙的な方法（例えばクリックスルー）でより効率的により正確に分析することができる。
【図面の簡単な説明】
【０００６】
【図１】特に、ユーザの嗜好を予測する協調フィルタリングエンジンを用いた典型的な認識システムを示す図である。
【図２】無限次元の特異値分解（ｉＳＶＤ：ｉｎｆｉｎｉｔｅ−ｄｉｍｅｎｓｉｏｎａｌ Ｓｉｎｇｕｌａｒ Ｖａｌｕｅ Ｄｅｃｏｍｐｏｓｉｔｉｏｎ）を行う典型的な処理を示す図である。
【図３】無限次元の確率的主成分分析（ｐＰＣＡ：ｉｎｆｉｎｉｔｅ−ｄｉｍｅｎｓｉｏｎａｌ ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｐｒｉｎｃｉｐａｌ Ｃｏｍｐｏｎｅｎｔ Ａｎａｌｙｓｉｓ）を行う典型的な処理を示す図である。
【図４】高速ｐＰＣＡを行う典型的な処理を示す図である。
【発明を実施するための形態】
【０００７】
図１は、１群の新製品／アイテムに対するアクティブなユーザの評価／関心／嗜好を予測する協調フィルタリングエンジンを用いた典型的な認識システムを示している。予測は、製品／アイテムの大きな群に対する多くのユーザの評価／関心／嗜好に関する過去のデータを包含したデータベースの解析に基づいている。
【０００８】
図１のシステムはデータベース１２からのデータを検索する。データベースはＮ個の製品に対するＭ個のユーザの評価を含んでいるので、情報はＭ×Ｎ行列になる。情報は推薦を生成するエンジン３０に提供される。エンジン３０は、無限次元の行列因子分解（ｉｎｆｉｎｉｔｅ ｄｉｍｅｎｓｉｏｎａｌ ｍａｔｒｉｘ ｆａｃｔｏｒｉｚａｔｉｏｎ）を用いて協調フィルタリングを行う。エンジン３０は現在アクティブなユーザからの情報２０を収集し、協調フィルタリングを用いて１つまたは２つ以上の推薦または予測４０を生成する。
【０００９】
システムは、特異値分解（ＳＶＤ：Ｓｉｎｇｕｌａｒ Ｖａｌｕｅ Ｄｅｃｏｍｐｏｓｉｔｉｏｎ）および確率的主成分分析（ｐＰＣＡ：ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｐｒｉｎｃｉｐａｌ Ｃｏｍｐｏｎｅｎｔ Ａｎａｌｙｓｉｓ）のような無限次元の行列因子分解法を用いる。
【００１０】
特異値分解および確率的主成分分析の２つの低階数行列因子分解法の次元を、無限大に近づかせることができる。無限次元を持つ学習は、ユーザの評価を予測する際に驚くほど優れた精度を得る。
【００１１】
無限次元の極限では、上記２つの方法は、ｉＳＶＤおよびｉＰＣＡと呼ばれる簡単で類似した定式化にそれぞれ収束する。データの疎性を活用しかつ慎重に計算を再編成することによって、そのような無限次元のモデルは大規模な疎行列の処理に対して効率的になる。テストでは、ｉＰＣＡはその非確率的な相当方法ｉＳＶＤと同じくらい速く動作する。
低階数行列因子分解
行列、ベクトル、およびガウス分布に関する以下の議論において、大文字は行列を表すのに用いられ、小文字はデフォルト列ベクトルによるベクトルを表すのに用いられる。例えば、Ｙ∈ＲM×Nは１つの行列であり、その（ｉ，ｊ）番目の要素はＹi,jであり、そのｉ番目の行はＮ×１ベクトルｙiによって表される。Ｙの転置（ｔｒａｎｓｐｏｓｅ）、トレース（ｔｒａｃｅ）、および、行列式（ｄｅｔｅｒｍｉｎａｎｔ）は、ＹT、ｔｒ（Ｙ）、およびｄｅｔ（Ｙ）によってそれぞれ表される。Ｉは、適切な次元を持つ単位行列を表す。さらに、||ｙ||はベクトルｌ2−ノルムであり、||ｙ||Fは、フロベニウスノルム（Ｆｒｏｂｅｎｉｕｓ ｎｏｒｍ）を表し、||ｙ||＊は、Ｙの特異値の和に等しいトレースノルムを表す。平均値μおよび共分散行列Σを持つベクトルｙの多変数ガウス分布は、Ｎ（ｙ；μ，Σ）、またはｙ：Ｎ（μ，Σ）によって表すことができる。Ｅ（・）は
、Ｅ（ｙ）＝μおよびＥ［（ｙ−μ）(y-μ)T］＝Ｃｏｖ（ｙ）＝Σのような確率変数の
期待値を意味している。
【００１２】
疎行列に関して、Ｙが欠損値を含んでいる場合、ＯはＹの観測要素の指標を表し、｜Ｏ｜は観測要素数を表す。（ｉ，ｊ）∈Ｏ下で、Ｙi,jが観測された場合、（Ｙ）O2＝Σ
(j,j)∈OＹi,j2は、すべての観測されたＹの２乗の和である。Ｏiは、ｉ番目の行ｙiの欠損していない要素の指標を表す。例えば、ｙiの要素の１番目および３番目の要素以外のすべての要素が欠損している場合、（ｉ）Ｏi＝［１，３］T、およびｙoi＝［Ｙi,1，Ｙi,3］Tとなり、（ｉｉ）Ｋが正方行列の場合、Ｋ:,Oiは、Ｋの１番目の列および３番目の列によって構成された部分行列を表し、（ｉｉｉ）ＫOiは、Ｋの１番目および３番目の行と、１番目および３番目の列との間の共通部分によって構成された部分正方行列である。
【００１３】
行列因子分解および協調フィルタリングでは、Ｎ個のアイテムに対するＭ個のユーザの数的な評価を記述するＭ×Ｎの評価行列Ｙに対して、低階数行列因子分解法は低階数要素の乗算によってＹを近似しようとする。すなわち次式のように記述できる。
【００１４】
【数１】
【００１５】
ここで、ＵはＭ×Ｌ行列、ＶはＮ×Ｌ行列、ただし、Ｌ＜ｍｉｎ（Ｍ，Ｎ）である。一般性を喪失することなく、Ｍ＞Ｎであることが仮定される。各ユーザはアイテムのほんの一部のみを評価しているので、Ｙは通常極めて疎である。協調フィルタリングは、観測要素から学習された低階数要素が、同じ行列の観測されていない要素を埋めるために用いられる、行列補完問題と見なすことができる。
【００１６】
特異値分解では、||Ｙ−ＵＶT||を最小化することによって十分に観測された行列Ｙを近似する結果から、ＳＶＤを導き出すことができる。しかしながら、Ｙが多数の欠損値を含んでいる場合、修正化ＳＶＤが、Ｙのこれらの既知の要素を近似しようとする。
【００１７】
【数２】
【００１８】
ここで、γ1，γ2＞０、２つの正則化項、||Ｕ||F2および||Ｖ||F2が過学習を回避するために付加される。最適化問題は非凸である。勾配に基づいた手法を適用して極小値を見つけることができ、該手法は協調フィルタリングに適用される最も普及した方法の１つである。
【００１９】
確率的主成分分析では、ｐＰＣＡは、Ｙの各要素が線形変換の雑音の多い結果であると仮定する。
【００２０】
Ｙi,j＝ｕiTｖj＋ｅi,j（ただし、（ｉ，ｊ）∈Ｏ） （３）
ここで、Ｕ＝［ｕi］∈ＲM×Lは、事前分布ｕi：Ｎ（０，Ｉ）（ただし、ｉ＝１，．．．，Ｍ）に従う潜在変数、ｅi,j：Ｎ（０，σ2）は、独立したガウス雑音である。学習は、Ｅ−ステップで、ｐ（ｕi｜Ｖ，σ2）、（ただし、ｉ＝１，．．．，Ｍ）の十分統計量を反復して算出し、次にＭ−ステップでＶおよびσ2を更新する期待値最大化（ＥＭ）アルゴリズムを用いて観測値の過小評価された尤度を最大化することによって行うことができる。そのデータは簡潔化のために事前中心化されているので、元の定式化はｙiの平均値を含んでいる。関連する確率的行列因子分解が協調フィルタリングに適用された。
「無限次元」を持つ行列因子分解
極限Ｌ→∞におけるＳＶＤ
「無限次元」（すなわちＬ→∞）の極限では、低階数行列因子分解問題（２）は凸最適化問題に収束する。Ｌ→∞で、ＵおよびＶがいずれも最大階数である場合、該問題（２）は次式と等価になる。
【００２１】
【数３】
【００２２】
最適条件Ｋ＝（γ1／γ2）1/2ｔｒ［（ＸＸT）1/2］を数式（４）に当てはめると、トレースノルム正則化を強いる凸学習問題と等価な式が次式として得られる。
【００２３】
【数４】
【００２４】
該等価性は数式（４）が凸であることを示唆している。したがって、その大域的最適解には、局所最適解を探索する任意のアルゴリズムによって到達することができる。
【００２５】
等価性にかかわらず、数式（５）は小さな行列のみを処理することができる半定値計画法を用いているが、一方数式（４）は解を得るのがはるかに容易で、よりスケーラブルである。数式（５）はγ1とγ2とを区別する必要がないことを示唆しているので、γ＝γ1＝γ2となる。ＥＭのようなアルゴリズムを、ＸおよびＫを代わりに更新することにより用いることができる。良い特性は、両方の更新が解析的な解を有しているということである。
【００２６】
・Ｅ−ステップ−Ｘの更新：現在のＫが与えられると、標準のカーネル回帰問題、ｍｉｎxi［（ｙi−ｘi）O2＋γｘiTＫ-1ｘi］を解くことによってＸの各行を独立して更新し、次式が導かれる。
【００２７】
ｘi←Ｋ:,Oi（ＫOi＋γＩ）-1ｙOi（ただし、ｉ＝１，．．．，Ｍ） （６）
ここで、Ｋ:Oi∈ＲN×|Oi|，ＫOi∈Ｒ|Oi|×|Oi|である。各ユーザは多くのアイテムを評価しないので、通常｜Ｏi｜は小さい数となる。
【００２８】
・Ｍ−ステップ−Ｋの更新：現在のＸが与えられると、次式が得られる。
【００２９】
Ｋ←（ＸTＸ）1/2＝ＱＳ1/2ＱT （７）
ここで、ＱおよびＳは標準の固有値分解ＸTＸ＝ＱＳＱTの結果であり、Ｓ1/2は固有値の平方根によって構成された対角行列である。
【００３０】
アルゴリズムの実施には基底行列計算が必要である。カーネル回帰問題（６）は、恐らく「無限次元」を使って処理するであろうが、いわゆる「カーネルトリック」を適用してデータの大きな疎性を活用できることを示唆している。しかしながら、より高い効率性を達成する大きな余地がなお存在し、それについて以下に説明する。
【００３１】
極限Ｌ→∞におけるｐＰＣＡ
無限次元の極限におけるｐＰＣＡモデル（３）に関して、ｕiまたはｖjのいずれか一方を直接処理することは実行不可能なので、ｘi＝［Ｘi,1，．．．，Ｘi,N］Tとおく。ここで、Ｘi,j＝ｕiTｖjである。平均値Ｅ（ｘi）＝ＶＥ（ｕi）＝０および共分散Ｅ（ｘiｘiT）＝ＶＥ（ｕiｕiT）ＶT＝ＶＶTを持つＮ次元のガウス分布に従うそのｘiを理解するのは容易である。Ｋ＝ＶＶTとし、Ｋが正定値カーネル行列になるように階数制約を緩和すると、ｐＰＣＡ（３）は次式のような簡単な発生モデルに一般化される。
【００３２】
ｙi＝ｘi＋ｅi（ただし、ｉ＝１，．．．，Ｍ） （８）
ここで、ｅi＝［ｅi,1，．．．，ｅi,N］であり、ｘi：Ｎ（０，Ｋ）およびｅi：Ｎ（０，σ2Ｉ）である。該モデルは、潜在的処理Ｘと観測的処理Ｙとを記述し、その周辺確率は次式で与えられる。
【００３３】
【数５】
【００３４】
ｐＰＣＡは、Ｙの各行が共分散Ｋ＋σ2Ｉを持つガウス分布から取り出された独立同分布サンプルであると仮定している。ＸおよびＫに関して共有の尤度ｐ（Ｙ，Ｘ｜Ｋ，σ2）を最大化するために、１つの解が次の最適化問題について得られる。
【００３５】
【数６】
【００３６】
上述の問題をＳＶＤ問題（４）と比較すると、２つの定式化は非常に類似している。１つの大きな違いは、数式（１０）が、トレースノルムを使用する代わりに、低複雑性罰則として対数行列式を適用しているということである。しかしながら、数式（１０）は不確実性および欠損データに対処する確率的な方法ではない。理に適った手法はすべての欠損／潜在変数の完全化を必要とし、過小評価された尤度（９）を最大化することを目標とする。これは正準期待値最大化（ＥＭ）アルゴリズムによってなされる。
【００３７】
・Ｅ−ステップ：ｐ（ｘi｜ｙoi，Ｋ，σ2）（ただし、ｉ＝１．．．、Ｍ）の十分統計量を算出する
Ｅ（ｘi）＝Ｋ:Oi（ＫOi＋σ2Ｉ）-1ｙOi （１１）
Ｃｏｖ（ｘi）＝Ｋ−Ｋ:Oi（ＫOi＋σ2Ｉ）-1ＫOi （１２）
・Ｍ−ステップ：最後のＥ−ステップの結果に基づいてパラメータを更新する
【００３８】
【数７】
【００３９】
【数８】
【００４０】
ここで、Ｃi,jは、Ｃｏｖ（ｘi）のｊ番目の対角線要素、すなわちＸi,jの事後分散である。
【００４１】
ＥＭアルゴリズムおよびセクション３．１に示したアルゴリズムは、Ｅ−ステップでカーネル回帰手順（６）および（１１）を含んでいるので、両アルゴリズムは同じように見える。最適化は非凸であるので、上述のアルゴリズムは局所最適解を見つける。
大規模な実施
記法上の便宜のために、２つのアルゴリズムをｉＳＶＤ（無限次元のＳＶＤ）およびｐＰＣＡ（無限次元のｐＰＣＡ）と呼ぶ。２つのアルゴリズムの大規模な実施を次に説明する。２つのＥＭアルゴリズムは、次のようないくつかの共通の計算上の側面を共有している。（１）潜在的要素ＵおよびＶを評価する代わりに、上記アルゴリズムは近似行列Ｘを処理する、（２）主な計算の負担はＥ−ステップである、（３）いずれの場合においても、Ｅ−ステップはｘi（ただし、ｉ＝１，．．．，Ｍ）の独立した更新に分解される、（４）ｘiの各更新に対して、カーネルトリックがＹの疎性を活用するのに適用される。最後の２つの特性は若干の望みをもたらすが、稚拙な実施は大規模なデータにはなお高価すぎる。例えば、Ｎｅｔｆｌｉｘ問題では、たった１つのＥ−ステップが、３．０ＧＨｚのＣＰＵおよび３.０Ｇメモリを持つＰＣ上でｉＳＶＤにより４０時間以上消費する。さらに悪いことに、ｐＰＣＡはＸの分布を考慮に入れて、数式（１２）によりその２次統計量を算出するので、該計算は単一のＥ−ステップでさらに４,０００時間かかる。以下では、数式（６）または（１１）の計算コストを著しく低減することができ、数式（１２）によってもたらされるオーバーヘッドをほぼ完全に回避することができる。その結果、ｉＳＶＤは低階数行列因子分解法と同じくらい高速になるが、一方ｐＰＣＡはその非確率的な相当ｉＳＶＤと同じくらい高速になる。
ｉＳＶＤ
ｉＳＶＤのボトルネックである数式（６）の計算コストは、計算を次式のように書き換えることによって低減される。
【００４２】
ｘi＝Ｋｚi
ここで、ＫはＮ×Ｎの完全なカーネル行列であり、ｚi∈ＲNは、位置Ｏiでゼロの要素を除いたゼロのベクトルであり、その値は次式によって割り当てられる。
【００４３】
ｚOi＝（ＫOi＋γＩ）-1ｙOi
次の数式（１５）から、数式（６）の再定式化は、明示的にＸを算出することなく数式（７）を実現できることを示唆している。
【００４４】
【数９】
【００４５】
上述の解析は、すべての行ｉに対して、システムが長さ｜Ｏi｜のベクトルｚOiを持つＮ×｜Ｏi｜行列Ｋ:Oiの乗算と、Ｎ2の乗算ｘiｘiT（すなわち、より小さな｜Ｏi｜2の乗算ｚOiｚOiTと置き換えられた）とを回避できることを示唆している。全体として、システムは、
【００４６】
【数１０】
【００４７】
の乗算演算の減少を得る。Ｎｅｔｆｌｉｘデータについて、このことは、１つのＥ−ステップについて４０時間以上の減少を意味しており、結果として発生する計算は４時間未満となる。
【００４８】
次の計算は数式（７）によって必要とされる固有値分解である。トレースノルム正規化は階数最小化ヒューリスティックであるので、いくつかのステップの後でＫが階数Ｒの場合、次のＫは、数式（１５）に基づいてＲより小さい階数を持つ。したがって、システムは各反復でＫの階数Ｒをチェックし、次の反復でＫの先行の階層Ｒの固有値のみを算出する。
【００４９】
擬似コードがアルゴリズム１によって記述される。記述をコンパクトに維持するために、（１）予測がバリデーション要素の小さな集合について低下した場合、該低下が起こったらプログラムを中止する、（２）ＱおよびＳを用いて、ステップ１をＫＢＫ＝ＱＳ（ＱＢＱ）ＳＱTによって算出し、結果として発生した行列はＫ用のメモリに格納される、ということを含んだ重要でない詳細については省略する。最大のメモリ消費は、システムが全体としてＮ（Ｎ−１）のメモリコストがかかる２つのＮ×Ｎ行列ＢおよびＫを格納する内側ループ中に生じる。ＯΣi=1M｜Ｏi｜3である主要な計算も内側ループであり、こ
こで、｜Ｏi｜＝Ｎである。Ｋを得た後、（ｉ，ｊ）の欠損要素に対する予測は、Ｘi,j＝Ｋj,Oi（ＫOi＋σ2Ｉ）-1ｙOiによる。
【００５０】
【表１】
【００５１】
上述の処理について、
１．Ｙ：疎なＭ×Νの評価行列、Ｍ個のユーザ、Ν個のアイテム
２．ガンマ（γ）：正則化パラメータ
３．ｉｔｅｒmax：アルゴリズムの最大反復回数
４．Ｋ：Ｎ×Ｎのカーネル行列、このアルゴリズムが最後に最適化して出力するパラメータ
５．Ｂ：Ｎ×Ｎ行列、これはステップ９でいくつかの中間結果を格納するのに用いられる
６．ｔ：Ｎ×１ベクトル、これはステップ８でいくつかの中間結果を格納するのに用いられる。
７．Ｒ：ステップ１１での固有値行列因子分解の階数
８．ｉｔｅｒ：現在の反復回数
９．ｉ：アルゴリズムによって現在処理されているユーザの指標
１０．Ｑ、Ｓ：行列ＫＢＫの固有値分解ＱＳＱ’の結果、ここで、Ｑ’はＱの転置、ＱはＮｘＲの行列、ＳはＮ×Ｎ対角行列である。
【００５２】
図２は典型的なｉＳＶＤ処理を示している。ｂ０で、該処理は必要な入力を受け取る。次にｂ１で、処理は、対称なｎ×ｎ行列ＫおよびＢを格納するメモリを事前に割り当てる。ｂ２で、処理は複数のパラメータを初期化し、その結果、ｉｔｅｒは０にリセットされ、Ｋは単位行列になり、およびＲはアイテム数Ｎに等しくなる。次に、ｂ３からｂ８で、処理は現在の反復回数を示すカウンタｉｔｅｒでループする。ｂ４で、ｉは現在処理されているユーザの指標である。ｂ５で、処理は、Ｋの現在の値が与えられると、ユーザＩの局所統計量および更新Ｂを収集する。ｂ６で、処理は、Ｍ個のユーザがすべて処理されているかどうかをチェックする。処理されていない場合、ｂ４にジャンプすることによって次のユーザを処理する。ｂ７は、アルゴリズム１のステップ１１〜１５を実行してＫを更新する。ｂ８で、処理は最大反復回数に達しているかどうかをチェックする。達していない場合、さらなる反復のためにｂ３へジャンプする。ｂ９で、達している場合、処理は計算を終了し、結果としてＫを返す。
ｉＰＣＡ
非確率的なｉＳＶＤと比較して、ｉＰＣＡのＥ−ステップは、すべてのｉ＝１，．．．，Ｍに対してＮ×Ｎの事後共分散行列を算出する１つの追加ステップ（１２）を持っている。しかしながら、オーバーヘッドはほぼ回避可能である。Ｂを、要素がゼロとして初期化され、次に次式によって局所情報を収集するのに用いられる、Ｎ×Ｎ行列としよう。
【００５３】
ＢOi←ＢOi−Ｇi＋ｚOiｚOiT（ただし、ｉ＝１，．．．，Ｍ） （１６）
ここで、Ｇi＝（ＫOi＋σ2Ｉ）-1、およびｚoi＝Ｇi＊ｙOiである。上式が与えられると、Ｍ−ステップ（１３）は次式によって実現することができる。
【００５４】
Ｋ←Ｋ＋（１／Ｍ）ＫＢＫ． （１７）
それ故、すべてのｉに対してＮ×Ｎの事後共分散行列を算出する数式（１２）を明示的に行う必要性はなく、このことは、ＮΣi=1M｜Ｏi｜2＋Ｎ2Σi=1M｜Ｏi｜回の乗算
を不要にする。Νｅｔｆｌｉｘ問題において、これは１つのＥ−ステップについて４，０００時間以上短縮することになる。擬似コードがアルゴリズム２で与えられる。
【００５５】
【表２】
【００５６】
【表３】
【００５７】
図３を説明する際に、次の表記を用いている。
１．Ｙ：疎なＭ×Νの評価行列、Ｍ個のユーザ、Ν個のアイテム
２．ｉｔｅｒmax：アルゴリズムの最大反復回数
３．Ｋ：Ｎ×Ｎのカーネル行列、このアルゴリズムが最後に最適化して出力するパラメータ
４．Ｂ：Ｎ×Ｎ行列、これはステップ１３でいくつかの中間結果を格納するのに用いられる
５．Ｇ：行列、これはステップ９で中間結果を格納するのに用いられる
６．ｔ：ベクトル、これはステップ１０で中間結果を格納するのに用いられる
７．Ｅｒ：スカラー、これはステップ１１および１２で中間結果を格納するのに用いられる
８．ｉｔｅｒ：現在の反復回数
９．ｉ：アルゴリズムによって現在処理されているユーザの指標
１０．シグマ（σ）：雑音の標準偏差、σ2は雑音の分散である。
【００５８】
図３は典型的なｉＰＣＡ処理を示している。この処理で、ｃ０は必要な入力を受け取る。ｃ１で、処理は、対称なＮ×Ｎ行列ＫおよびＢを格納するメモリを事前に割り当てる。次にｃ２で、処理はいくつかのパラメータを初期化し、その結果、ｉｔｅｒは０にリセットされ、Ｋは単位行列になる。ｃ３で、現在の反復回数がインクリメントされ、Ｂ、Ｅｒ、およびｉがリセットされる。ｃ４で、現在処理されているユーザの指標ｉがインクリメントされる。ｃ５で、各ユーザの局所統計量が収集され、ＢおよびＥｒが更新される。ｃ６で、処理は、Ｍ個のユーザがすべて処理されているかどうかをチェックする。処理されていない場合、ｃ４にジャンプすることによって次のユーザを処理する。ｃ７で、Ｋおよびシグマ（σ）が更新される。次にｃ８で、処理は最大反復回数に達しているかどうかをチェックする。達していない場合、さらなる反復のためにｃ３へジャンプする。処理は、計算を終了し結果としてＫおよびシグマ（σ）を返すｃ９で終わる。
【００５９】
図４は典型的な高速ｉＰＣＡ処理を示している。次の表記が図４の処理に適用される。
１．Ｙ：疎なＭ×Νの評価行列、Ｍ個のユーザ、Ν個のアイテム
２．ｉｔｅｒmax：アルゴリズムの最大反復回数
３．Ｋ：Ｎ×Ｎのカーネル行列、このアルゴリズムが最後に最適化して出力するパラメータ
４．Ｂ：Ｎ×Ｎ行列、これはステップ１１でいくつかの中間結果を格納するのに用いられる
５．ｂ：Ｎ×１ベクトル、これはステップ１０で中間結果を格納するのに用いられる
６．ミュー（μ）：Ｎ×１ベクトル、このアルゴリズムが最後に最適化して出力する他のパラメータ
７．Ｇ：行列、これはステップ８で中間結果を格納するのに用いられる
８．ｔ：ベクトル、これはステップ９で中間結果を格納するのに用いられる
９．ｉｔｅｒ：現在の反復回数
１０．ｉ：アルゴリズムによって現在処理されているユーザの指標。
【００６０】
ここで、図４を参照して、ｄ０で、該処理は必要な入力を受け取る。ｄ１で、処理は、対称なＮ×Ｎ行列ＫおよびＢ、およびＮ×１ベクトルｂおよびミュー（μ）を格納するメモリを事前に割り当てる。ｄ２で、処理はパラメータを初期化し、その結果、ｉｔｅｒは０にリセットされ、Ｋは単位行列になる。ｄ３で現在の反復回数がインクリメントされ、ｄ４で次のユーザが選択される。ｄ５で、現在のユーザの局所統計量が収集され、Ｂおよびｂが更新される。ｄ６で、処理は、Ｍ個のユーザがすべて処理されているかどうかをチェックする。処理されていない場合、ｄ４にジャンプすることによって次のユーザを処理する。ｄ７で、処理は、アルゴリズム３のステップ１３および１４に従ってＫおよびミュー（μ）を更新する。ｄ８で、処理は最大反復回数に達しているかどうかをチェックする。達していない場合、処理はさらなる反復のためにｄ３へジャンプする。ｄ９で、処理は計算を終了し、結果としてＫおよびミュー（μ）を返す。
【００６１】
アルゴリズム２をアルゴリズム１と比較すると、確率的な手法の残りの計算のオーバーヘッドは、雑音の分散σ2の更新を準備して、局所的な不確実性情報を収集するステップにあり、該ステップは各Ｅ−ステップに対して追加のΣi=1M（２｜Ｏi｜2＋｜Ｏi｜
3）回の乗算を必要とする。アルゴリズムをさらに高速化するために、ｉＰＣＡを簡略化することができる。数式（８）の本質的なモデル化推定は、Ｙが、独立して同じくガウス分布Ｎ（０，Ｋ＋σ2Ｉ）に従う行ｙiの集合であるということである。次に、この着想は、雑音および信号を明示的にモデル化するのではなく、処理がＫ←Ｋ＋σ2Ｉによって結合して雑音の多い観測値ｙi（ただし、ｉ＝１，．．．，Ｍ）の共分散を直接処理することにある。得られたモデルは次のように簡単になる。
【００６２】
Ｙi,j：δ（Ｘi,j）（ここで、ｘi：Ｎ（μ，Ｋ） （１８）
さらに、δ（Ｘi,j）は、Ｙi,j＝Ｘi,jの場合に１、そうでなければ０の確率を持つ分布である。このモデルに対して、ＥＭアルゴリズムは次のようになる。
【００６３】
・Ｅ−ステップ：Ｅ（ｘi）＝Ｋ:Oi（ＫOi）-1（ｙOi−μOi）、およびＣｏｖ（ｘi）＝Ｋ−Ｋ:Oi（ＫOi）-1ＫOi
・Ｍ−ステップ：Ｋ←１／ＭΣi=1M［Ｃｏｖ（ｘi）＋Ｅ（ｘi）Ｅ（ｘi）T］お
よびμ←μ＋１／ＭΣi=1MＥ（ｘi）
該実施はアルゴリズム２で要約されている。雑音を評価する必要がないので、Ｅ−ステップでの計算コストは非確率的なアルゴリズム１の計算コストと比べてわずかな違いしかない。アルゴリズム２と比較して、新バージョンは、１つのＥ−ステップで、Ｎｅｔｆｌｉｘデータについて約１１．７時間節減し、たった４時間で終了する。メモリコストも、ＫおよびＢを格納するのにＮ（Ｎ−１）となるアルゴリズム１と同じである。予測は期待値Ｅ（Ｙi,j）＝Ｋj,Oi（ＫOi）-1（ｙOi−μOi）＋μjを算出することによってなされる。その著しい単純性により、ｉＰＣＡのより高速なバージョンを実験で用いた。
【００６４】
次に、説明したアルゴリズム１および２の効率性および精度を、２つの最大の公的に入手可能なベンチマーク、ＥａｃｈＭｏｖｉｅデータおよびＮｅｔｆｌｉｘデータと対照してテストした。
【００６５】
２つのアルゴリズムが、今日まで２つの最大の公的なベンチマークである、大きさ７４，４２４×１，６４８のＥａｃｈＭｏｖｉｅデータおよび大きさ４８０，１８９×１７，７７０のＮｅｔｆｌｉｘデータについてテストされ、効率性と精度の両方について、低階数行列因子分解法によって達成された最先端技術の性能に匹敵するかまたはそれより優れているという結果を達成した。
ＥａｃｈＭｏｖｉｅデータ
１，６４８本の映画に対する７４，４２４人のユーザの２，８１１，７１８個の異なる数的評価を含んだ全体のＥａｃｈＭｏｖｉｅデータに関する一連の実験。平均で要素の９７．１７％が欠損しているので、これは非常に疎な行列である。ランダムに、各ユーザの評価の約８０％がトレーニング用に選択され、残りの２０％がテストケースとして選択された。無作為抽出を２０回独立して行った。次のアルゴリズムがテストされる。
【００６６】
（１）ＳＶＤ：上で説明したｉＳＶＤを加えた２０および４０の次元を持つ低階数ＳＶＤ
２つの低階数法が共役勾配法によって最適化される。停止基準は、トレーニング要素の１つの小さなホールドアウト集合（ｈｏｌｄ−ｏｕｔ ｓｅｔ）の性能に基づいている。各アルゴリズムについて、第１の区画をテストする場合、正則化パラメータが、ホールドアウト集合の性能に基づいて、γ＝１、５、１０、２０、５０、および１００から設定された。
【００６７】
（２）ＰＣＡ：上で説明したｉＰＣＡを加えた２０および４０の次元を持つ低階数ｐＰＣＡ
これらの３つの方法について、停止基準は、ＥＭの反復総数が３０を超えるべきでないということに加えて、ホールドアウト集合にも基づいている。これらのｐＰＣＡモデルに関する素晴らしい利点は、調整する正則化パラメータがないことである！
平均化された結果を示す代わりに、２０回の試行のすべての個々のＲＭＳＥ結果を下の表に挙げている。すべての方法について、ランダムな列／テスト区画にわたる変動量は小さい。ＳＶＤおよびｐＰＣＡの２つのカテゴリーの各々について、無限のモデルは、各自分自身の低階数の相当モデルよりも常に優れた性能を示した。これは、モデルの次元制約を緩和するという利点が確かにあるということを意味している。次に、確率的な手法はそれらのＳＶＤ法より常に優れた性能を示した。特に、ｉＰＣＡは２０回の試行すべてにわたって勝利者である。ｉＰＣＡの平均ＲＭＳＥ誤りは、ｉＳＶＤの平均ＲＭＳＥ誤りより４．３３％低く、ＳＶＤ（次元ｄ＝２０）の平均ＲＭＳＥ誤りより６．９０％低い。この結果は、予測精度に関する確率的なモデルの利点を明確に支持している。
【００６８】
アルゴリズムはＣ＋＋を用いて実行された。２０回の試行を通して平均化された実行時間を表２に報告する。共役勾配を用いたＳＶＤは、非常にゆっくり収束した。上で解析したように、ｉＳＶＤとｉＰＣＡとは本質的に同一の計算コストを持っている。ここで、ｉＳＶＤは検出された過学習により通常５回の反復の後に停止したが、一方該過学習は３０回の反復をすべて終了したｐＰＣＡ法については観測されなかったので、ｉＰＣＡにはより長時間を要した。
【００６９】
【表４】
【００７０】
Ｎｅｔｆｌｉｘデータ
１９９８〜２００５年の期間に得られたＮｅｔｆｌｉｘ．ｃｏｍの評価の分布を表すＮｅｔｆｌｉｘデータが収集された。発表されたトレーニングデータは、１７，７７０本の映画に対する４８０，１８９人のユーザからの１００，４８０，５０７個の評価から成る。さらに、Ｎｅｔｆｌｉｘは、１，４０８，３９５個の評価を持つ検証データ群も提供する。したがって、要素の９８．８１％が評価行列で欠損している。予測精度を評価するために、すべての参加者について値が保留されたおよび不明の２，８１７，１３１個の評価を含んだテストセットがある。テストセットのＲＭＳＥを評価するために、参加者は、ＲＭＳＥ誤りを知らせる電子メールを後で返送するＮｅｔｆｌｉｘに、結果を提出する必要がある。結果は全く同一のテストデータについて評価されるので、それは異なったアルゴリズムを比較するのに優れたプラットフォームを提供する。
【００７１】
アルゴリズム１および２は、検証データの９５％のランダムな集合を加えたトレーニングデータについてテストされ、該検証データの残りの５％は停止基準に用いられた。行列因子分解法による文献で報告されている最先端技術の結果と共に、２つのモデルによって得られた結果を次の表３に示している。異なった性質からなる異種のモデルを合成することによる優れた結果が報告されているが、一方本システムによって達成された結果は単一のモデルを用いている。同表において、ベースラインの結果はＮｅｔｆｌｉｘ自身のアルゴリズムによってなされた。ＢＰＭＦは、これまで低階数法によって最先端技術の精度を生み出した、ＭＣＭＣを用いたベイズの確率的行列因子分解（Ｂａｙｅｓｉａｎ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｍａｔｒｉｘ ｆａｃｔｏｒｉｚａｔｉｏｎ）である。ｉＰＣＡはＢＰＭＦよりもさらに良好な結果を達成し、ベースラインから６．１８％だけ精度を改善した。恐らく正則化パラメータを微調整する必要性があるためであろうが、ｉＳＶＤはこのデータセットについてはあまりうまく動作しなかった。しかしながら、これは、調整するパラメータを持たないｉＰＣＡの利点を際立たせている。実行時間の効率性に関して、両アルゴリズムは１つの反復当たり約５時間を費やした。ｉＰＣＡの結果は３０回の反復によって得られた。
【００７２】
【表５】
【００７３】
無限次元の行列因子分解モデルは大規模な協調フィルタリング問題を解くことができる。該モデルの２つの例とは、特異値分解（ＳＶＤ）および確率的主成分分析（ｐＰＣＡ）である。テストは、無限次元のモデルが１億個の評価を含んだ非常に大規模なデータについて実際に効率的であることを示している。さらに、確率的な手法は非確率的な方法ほどスケーラブルでないと通常考えられているが、ｉＰＣＡは確率的な手法と同じくらい速い非確率的な相当手法である。予測精度に関しては、無限次元のモデルは低階数法より優れた性能を示すことが多く、確率的なモデルは非確率的なモデルよりもより正確な結果を提供した。
【００７４】
本発明は、ハードウェア、ファームウェア、またはソフトウェア、または、これら３つの組み合わせで実行されてもよい。好ましくは、本発明は、プロセッサ、データ記憶システム、揮発性および不揮発性メモリ、および／または記憶素子、少なくとも１つの入力装置、および少なくとも１つの出力装置を持つプログラム可能なコンピュータ上で実行されるコンピュータプログラムで実行される。
【００７５】
例として、システムを支援するコンピュータのブロックダイアグラムを次に説明する。該コンピュータは、プロセッサと、ランダムアクセスメモリ（ＲＡＭ）と、プログラムメモリ（好ましくはフラッシュＲＯＭのような書き込み可能な読み出し専用メモリ（ＲＯＭ））と、ＣＰＵバスによって接続された入出力（Ｉ／Ｏ）制御装置とを含むのが好ましい。コンピュータは、ハードディスクおよびＣＰＵバスに接続されたハードディスクドライブ制御装置を随意に含んでいてもよい。ハードディスクは、本発明のようなアプリケーションプログラム、およびデータを格納するのに使用されてもよい。あるいは、アプリケーションプログラムはＲＡＭまたはＲＯＭに格納されてもよい。入出力制御装置は入出力インタフェースに入出力バスによって接続される。入出力インタフェースは、シリアルリンク、ローカルエリアネットワーク、無線リンク、およびパラレルリンクのような通信リンクを通して、アナログ形態またはディジタル形態のデータを受信し送信する。随意に、表示装置、キーボード、およびポインティングデバイス（マウス）も入出力バスに接続されてもよい。あるいは、個別の接続（個別のバス）が、入出力インタフェース、表示装置、キーボード、およびポインティングデバイス用に使用されてもよい。プログラム可能な処理システムは事前にプリプログラムされていてもよく、または該システムは、他のソース（例えばフロッピーディスク、ＣＤ−ＲＯＭ、または他のコンピュータ）からプログラムをダウンロードすることによってプログラム（および再プログラム）されてもよい。
【００７６】
各コンピュータプログラムは、汎用のまたは専用のプログラム可能コンピュータによって読取り可能な、機械可読の記憶媒体または装置（例えばプログラムメモリまたは磁気ディスク）に明確に格納され、記憶媒体または装置が、ここで説明している手順を実行するコンピュータによって読まれるとき、該コンピュータの動作を構成し、制御する。発明的システムは、コンピュータプログラムで構成されたコンピュータ可読記憶媒体で具体化されると考えることもでき、そのように構成された記憶媒体は、コンピュータをここで説明している機能を実行するように特定の事前に定められた方法で動作させる。
【００７７】
特許法に準拠するために、および新規な原理を適用して、必須のそのような特殊な構成要素を構築して使用するのに必要な情報を当業者に提供するために、本発明をかなり詳細にここで説明した。しかしながら、本発明は明確に異なった設備および装置で実行することができ、種々の修正を、設備詳細および動作手順の両方について、本発明そのものの範囲から逸脱することなく行うことができることが理解されよう。
【００７８】
本発明の具体的実施形態は添付の図面に示されており、前述の詳細な説明で説明されたが、本発明はここで説明している特定の実施形態に限定されるものではなくて、本発明の範囲から逸脱することなく多くの再配置、修正、および代替が可能であることが理解されよう。添付の特許請求の範囲は、そのような修正をすべて包含するように意図されている。
【背景技術】
【０００１】
推薦システムは、ａｍａｚｏｎ．ｃｏｍおよびｎｅｔｆｌｉｘ．ｃｏｍのようなサイトを通じて普及してきた。これらのシステムは、製品、例えば映画に対する多くのユーザの評価のデータベースを解析し、未見／未購入の製品に対するユーザの評価／嗜好に関する予測を行う。多くの最先端技術の推薦システムは、「協調フィルタリング」に依存してユーザの嗜好やパターンを見いだしている。該技術は、ユーザデータを、例えば行がユーザごとに指標を付けられ、次に列が製品ごとに指標を付けられた１次元の大きな行列として解釈する。行列の要素は製品に対するユーザの評価である。該行列は、ユーザおよび製品の数が多いので通常大きくなり、各ユーザが少数の製品に対する評価を与えていたものなので非常に疎な行列になる。次に、協調フィルタリングは、これらの製品について観測された評価のパターンを解析し、該製品の未観測の／欠損している評価に対する予測を行う。莫大で疎な評価行列の豊富な構造を見いだすために、実証的研究は要素の数が十分に大きくあるべきであることを示した。この意味で、協調フィルタリングは行列補完問題となる。
【０００２】
従来の技術は、データがＭ×Ｎ（ここで、ＭはＮ個の製品に対するユーザの評価数を表す）の行列としてデータベースに保存される低階数行列因子分解法を含んでいる。行列の評価のほんの一部のみが観測されるので、該行列はかなり大きくて疎な行列になる。低階数因子分解法は、行列を、１つはユーザ固有の要素、もう１つは製品固有の要素を表す２つの行列の積に因子分解する。最適化手順を用いて、データについて最も良く説明することができる要素を見つける。ユーザ要素または製品要素のいずれか一方の数は有限である。製品に対するユーザの評価の予測は、ユーザの要素ベクトルおよび製品の要素ベクトルを検索し、次に結果を与えるそれらの内積を計算することによって行われる。オンラインユーザデータの完全な成長によって、正確でスケーラブルな学習アルゴリズムを開発することが大きな課題となっている。
【０００３】
協調フィルタリングの最近の進歩が、低階数行列因子分解法の成長を刺激した。協調フィルタリングの低階数行列因子分解アルゴリズムは、概略非確率的手法と確率的手法とに分類することができる。最近のネットフリックス（Ｎｅｔｆｌｉｘ）コンテストでは、行列因子分解法（ｍａｔｒｉｘ ｆａｃｔｏｒｉｚａｔｉｏｎ ｔｅｃｈｎｉｑｕ）が参加者のランキングで非常に人気がある。行列因子分解がユーザ要素数と映画要素数との乗算によって適用される場合、要素の両面が行列因子分解によって見つかる。計算効率に関して、すべての技法は要素数が少ないと仮定している。したがって、行列の因子分解は低階数因子分解となる。しかしながら、多種多様なユーザパターンには説明すべき多くの要素が必要なので、システムの階数を制限することは、予測精度を低下させる場合が多い。
【発明の概要】
【０００４】
無限次元の行列因子分解を用いて協調フィルタリングを行うこと、協調フィルタリングを用いて１つまたは２つ以上の推薦を発生させること、推薦をユーザに表示することによって、推薦を生成するシステムおよび方法が開示される。
【０００５】
好ましい実施形態の利点は、次の１つまたは２つ以上のものを含んでいてもよい。推薦システムは、非常に大きな数の要素または無限の数の要素すら用いる協調フィルタリング技法を用いる。インスタントフィルタリング技術は、ユーザの評価／嗜好に対する正確な予測を行う高い精度を維持しながら、大量のデータを効率的に処理する拡張性および効率性を提供する。能力が増強されたことにより、システムはユーザの評価／嗜好をより正確に予測することができる。システムが非常に大規模なユーザの評価用データベースにスケーリングできるように、計算は効率的に行われる。システムは、ユーザの嗜好に関してよりよい理解を持つ必要があるオンラインストア、ニュースウェブサイト、オンライン広告を含む多くのオンラインサービスのパフォーマンスを改善することができる。ユーザ満足度および事業収益の両方を改善することができるように、システムを用いて、広範囲のユーザが示す嗜好を明示的な方法（例えば数的な評価）でまたは暗黙的な方法（例えばクリックスルー）でより効率的により正確に分析することができる。
【図面の簡単な説明】
【０００６】
【図１】特に、ユーザの嗜好を予測する協調フィルタリングエンジンを用いた典型的な認識システムを示す図である。
【図２】無限次元の特異値分解（ｉＳＶＤ：ｉｎｆｉｎｉｔｅ−ｄｉｍｅｎｓｉｏｎａｌ Ｓｉｎｇｕｌａｒ Ｖａｌｕｅ Ｄｅｃｏｍｐｏｓｉｔｉｏｎ）を行う典型的な処理を示す図である。
【図３】無限次元の確率的主成分分析（ｐＰＣＡ：ｉｎｆｉｎｉｔｅ−ｄｉｍｅｎｓｉｏｎａｌ ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｐｒｉｎｃｉｐａｌ Ｃｏｍｐｏｎｅｎｔ Ａｎａｌｙｓｉｓ）を行う典型的な処理を示す図である。
【図４】高速ｐＰＣＡを行う典型的な処理を示す図である。
【発明を実施するための形態】
【０００７】
図１は、１群の新製品／アイテムに対するアクティブなユーザの評価／関心／嗜好を予測する協調フィルタリングエンジンを用いた典型的な認識システムを示している。予測は、製品／アイテムの大きな群に対する多くのユーザの評価／関心／嗜好に関する過去のデータを包含したデータベースの解析に基づいている。
【０００８】
図１のシステムはデータベース１２からのデータを検索する。データベースはＮ個の製品に対するＭ個のユーザの評価を含んでいるので、情報はＭ×Ｎ行列になる。情報は推薦を生成するエンジン３０に提供される。エンジン３０は、無限次元の行列因子分解（ｉｎｆｉｎｉｔｅ ｄｉｍｅｎｓｉｏｎａｌ ｍａｔｒｉｘ ｆａｃｔｏｒｉｚａｔｉｏｎ）を用いて協調フィルタリングを行う。エンジン３０は現在アクティブなユーザからの情報２０を収集し、協調フィルタリングを用いて１つまたは２つ以上の推薦または予測４０を生成する。
【０００９】
システムは、特異値分解（ＳＶＤ：Ｓｉｎｇｕｌａｒ Ｖａｌｕｅ Ｄｅｃｏｍｐｏｓｉｔｉｏｎ）および確率的主成分分析（ｐＰＣＡ：ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｐｒｉｎｃｉｐａｌ Ｃｏｍｐｏｎｅｎｔ Ａｎａｌｙｓｉｓ）のような無限次元の行列因子分解法を用いる。
【００１０】
特異値分解および確率的主成分分析の２つの低階数行列因子分解法の次元を、無限大に近づかせることができる。無限次元を持つ学習は、ユーザの評価を予測する際に驚くほど優れた精度を得る。
【００１１】
無限次元の極限では、上記２つの方法は、ｉＳＶＤおよびｉＰＣＡと呼ばれる簡単で類似した定式化にそれぞれ収束する。データの疎性を活用しかつ慎重に計算を再編成することによって、そのような無限次元のモデルは大規模な疎行列の処理に対して効率的になる。テストでは、ｉＰＣＡはその非確率的な相当方法ｉＳＶＤと同じくらい速く動作する。
低階数行列因子分解
行列、ベクトル、およびガウス分布に関する以下の議論において、大文字は行列を表すのに用いられ、小文字はデフォルト列ベクトルによるベクトルを表すのに用いられる。例えば、Ｙ∈ＲM×Nは１つの行列であり、その（ｉ，ｊ）番目の要素はＹi,jであり、そのｉ番目の行はＮ×１ベクトルｙiによって表される。Ｙの転置（ｔｒａｎｓｐｏｓｅ）、トレース（ｔｒａｃｅ）、および、行列式（ｄｅｔｅｒｍｉｎａｎｔ）は、ＹT、ｔｒ（Ｙ）、およびｄｅｔ（Ｙ）によってそれぞれ表される。Ｉは、適切な次元を持つ単位行列を表す。さらに、||ｙ||はベクトルｌ2−ノルムであり、||ｙ||Fは、フロベニウスノルム（Ｆｒｏｂｅｎｉｕｓ ｎｏｒｍ）を表し、||ｙ||＊は、Ｙの特異値の和に等しいトレースノルムを表す。平均値μおよび共分散行列Σを持つベクトルｙの多変数ガウス分布は、Ｎ（ｙ；μ，Σ）、またはｙ：Ｎ（μ，Σ）によって表すことができる。Ｅ（・）は
、Ｅ（ｙ）＝μおよびＥ［（ｙ−μ）(y-μ)T］＝Ｃｏｖ（ｙ）＝Σのような確率変数の
期待値を意味している。
【００１２】
疎行列に関して、Ｙが欠損値を含んでいる場合、ＯはＹの観測要素の指標を表し、｜Ｏ｜は観測要素数を表す。（ｉ，ｊ）∈Ｏ下で、Ｙi,jが観測された場合、（Ｙ）O2＝Σ
(j,j)∈OＹi,j2は、すべての観測されたＹの２乗の和である。Ｏiは、ｉ番目の行ｙiの欠損していない要素の指標を表す。例えば、ｙiの要素の１番目および３番目の要素以外のすべての要素が欠損している場合、（ｉ）Ｏi＝［１，３］T、およびｙoi＝［Ｙi,1，Ｙi,3］Tとなり、（ｉｉ）Ｋが正方行列の場合、Ｋ:,Oiは、Ｋの１番目の列および３番目の列によって構成された部分行列を表し、（ｉｉｉ）ＫOiは、Ｋの１番目および３番目の行と、１番目および３番目の列との間の共通部分によって構成された部分正方行列である。
【００１３】
行列因子分解および協調フィルタリングでは、Ｎ個のアイテムに対するＭ個のユーザの数的な評価を記述するＭ×Ｎの評価行列Ｙに対して、低階数行列因子分解法は低階数要素の乗算によってＹを近似しようとする。すなわち次式のように記述できる。
【００１４】
【数１】
【００１５】
ここで、ＵはＭ×Ｌ行列、ＶはＮ×Ｌ行列、ただし、Ｌ＜ｍｉｎ（Ｍ，Ｎ）である。一般性を喪失することなく、Ｍ＞Ｎであることが仮定される。各ユーザはアイテムのほんの一部のみを評価しているので、Ｙは通常極めて疎である。協調フィルタリングは、観測要素から学習された低階数要素が、同じ行列の観測されていない要素を埋めるために用いられる、行列補完問題と見なすことができる。
【００１６】
特異値分解では、||Ｙ−ＵＶT||を最小化することによって十分に観測された行列Ｙを近似する結果から、ＳＶＤを導き出すことができる。しかしながら、Ｙが多数の欠損値を含んでいる場合、修正化ＳＶＤが、Ｙのこれらの既知の要素を近似しようとする。
【００１７】
【数２】
【００１８】
ここで、γ1，γ2＞０、２つの正則化項、||Ｕ||F2および||Ｖ||F2が過学習を回避するために付加される。最適化問題は非凸である。勾配に基づいた手法を適用して極小値を見つけることができ、該手法は協調フィルタリングに適用される最も普及した方法の１つである。
【００１９】
確率的主成分分析では、ｐＰＣＡは、Ｙの各要素が線形変換の雑音の多い結果であると仮定する。
【００２０】
Ｙi,j＝ｕiTｖj＋ｅi,j（ただし、（ｉ，ｊ）∈Ｏ） （３）
ここで、Ｕ＝［ｕi］∈ＲM×Lは、事前分布ｕi：Ｎ（０，Ｉ）（ただし、ｉ＝１，．．．，Ｍ）に従う潜在変数、ｅi,j：Ｎ（０，σ2）は、独立したガウス雑音である。学習は、Ｅ−ステップで、ｐ（ｕi｜Ｖ，σ2）、（ただし、ｉ＝１，．．．，Ｍ）の十分統計量を反復して算出し、次にＭ−ステップでＶおよびσ2を更新する期待値最大化（ＥＭ）アルゴリズムを用いて観測値の過小評価された尤度を最大化することによって行うことができる。そのデータは簡潔化のために事前中心化されているので、元の定式化はｙiの平均値を含んでいる。関連する確率的行列因子分解が協調フィルタリングに適用された。
「無限次元」を持つ行列因子分解
極限Ｌ→∞におけるＳＶＤ
「無限次元」（すなわちＬ→∞）の極限では、低階数行列因子分解問題（２）は凸最適化問題に収束する。Ｌ→∞で、ＵおよびＶがいずれも最大階数である場合、該問題（２）は次式と等価になる。
【００２１】
【数３】
【００２２】
最適条件Ｋ＝（γ1／γ2）1/2ｔｒ［（ＸＸT）1/2］を数式（４）に当てはめると、トレースノルム正則化を強いる凸学習問題と等価な式が次式として得られる。
【００２３】
【数４】
【００２４】
該等価性は数式（４）が凸であることを示唆している。したがって、その大域的最適解には、局所最適解を探索する任意のアルゴリズムによって到達することができる。
【００２５】
等価性にかかわらず、数式（５）は小さな行列のみを処理することができる半定値計画法を用いているが、一方数式（４）は解を得るのがはるかに容易で、よりスケーラブルである。数式（５）はγ1とγ2とを区別する必要がないことを示唆しているので、γ＝γ1＝γ2となる。ＥＭのようなアルゴリズムを、ＸおよびＫを代わりに更新することにより用いることができる。良い特性は、両方の更新が解析的な解を有しているということである。
【００２６】
・Ｅ−ステップ−Ｘの更新：現在のＫが与えられると、標準のカーネル回帰問題、ｍｉｎxi［（ｙi−ｘi）O2＋γｘiTＫ-1ｘi］を解くことによってＸの各行を独立して更新し、次式が導かれる。
【００２７】
ｘi←Ｋ:,Oi（ＫOi＋γＩ）-1ｙOi（ただし、ｉ＝１，．．．，Ｍ） （６）
ここで、Ｋ:Oi∈ＲN×|Oi|，ＫOi∈Ｒ|Oi|×|Oi|である。各ユーザは多くのアイテムを評価しないので、通常｜Ｏi｜は小さい数となる。
【００２８】
・Ｍ−ステップ−Ｋの更新：現在のＸが与えられると、次式が得られる。
【００２９】
Ｋ←（ＸTＸ）1/2＝ＱＳ1/2ＱT （７）
ここで、ＱおよびＳは標準の固有値分解ＸTＸ＝ＱＳＱTの結果であり、Ｓ1/2は固有値の平方根によって構成された対角行列である。
【００３０】
アルゴリズムの実施には基底行列計算が必要である。カーネル回帰問題（６）は、恐らく「無限次元」を使って処理するであろうが、いわゆる「カーネルトリック」を適用してデータの大きな疎性を活用できることを示唆している。しかしながら、より高い効率性を達成する大きな余地がなお存在し、それについて以下に説明する。
【００３１】
極限Ｌ→∞におけるｐＰＣＡ
無限次元の極限におけるｐＰＣＡモデル（３）に関して、ｕiまたはｖjのいずれか一方を直接処理することは実行不可能なので、ｘi＝［Ｘi,1，．．．，Ｘi,N］Tとおく。ここで、Ｘi,j＝ｕiTｖjである。平均値Ｅ（ｘi）＝ＶＥ（ｕi）＝０および共分散Ｅ（ｘiｘiT）＝ＶＥ（ｕiｕiT）ＶT＝ＶＶTを持つＮ次元のガウス分布に従うそのｘiを理解するのは容易である。Ｋ＝ＶＶTとし、Ｋが正定値カーネル行列になるように階数制約を緩和すると、ｐＰＣＡ（３）は次式のような簡単な発生モデルに一般化される。
【００３２】
ｙi＝ｘi＋ｅi（ただし、ｉ＝１，．．．，Ｍ） （８）
ここで、ｅi＝［ｅi,1，．．．，ｅi,N］であり、ｘi：Ｎ（０，Ｋ）およびｅi：Ｎ（０，σ2Ｉ）である。該モデルは、潜在的処理Ｘと観測的処理Ｙとを記述し、その周辺確率は次式で与えられる。
【００３３】
【数５】
【００３４】
ｐＰＣＡは、Ｙの各行が共分散Ｋ＋σ2Ｉを持つガウス分布から取り出された独立同分布サンプルであると仮定している。ＸおよびＫに関して共有の尤度ｐ（Ｙ，Ｘ｜Ｋ，σ2）を最大化するために、１つの解が次の最適化問題について得られる。
【００３５】
【数６】
【００３６】
上述の問題をＳＶＤ問題（４）と比較すると、２つの定式化は非常に類似している。１つの大きな違いは、数式（１０）が、トレースノルムを使用する代わりに、低複雑性罰則として対数行列式を適用しているということである。しかしながら、数式（１０）は不確実性および欠損データに対処する確率的な方法ではない。理に適った手法はすべての欠損／潜在変数の完全化を必要とし、過小評価された尤度（９）を最大化することを目標とする。これは正準期待値最大化（ＥＭ）アルゴリズムによってなされる。
【００３７】
・Ｅ−ステップ：ｐ（ｘi｜ｙoi，Ｋ，σ2）（ただし、ｉ＝１．．．、Ｍ）の十分統計量を算出する
Ｅ（ｘi）＝Ｋ:Oi（ＫOi＋σ2Ｉ）-1ｙOi （１１）
Ｃｏｖ（ｘi）＝Ｋ−Ｋ:Oi（ＫOi＋σ2Ｉ）-1ＫOi （１２）
・Ｍ−ステップ：最後のＥ−ステップの結果に基づいてパラメータを更新する
【００３８】
【数７】
【００３９】
【数８】
【００４０】
ここで、Ｃi,jは、Ｃｏｖ（ｘi）のｊ番目の対角線要素、すなわちＸi,jの事後分散である。
【００４１】
ＥＭアルゴリズムおよびセクション３．１に示したアルゴリズムは、Ｅ−ステップでカーネル回帰手順（６）および（１１）を含んでいるので、両アルゴリズムは同じように見える。最適化は非凸であるので、上述のアルゴリズムは局所最適解を見つける。
大規模な実施
記法上の便宜のために、２つのアルゴリズムをｉＳＶＤ（無限次元のＳＶＤ）およびｐＰＣＡ（無限次元のｐＰＣＡ）と呼ぶ。２つのアルゴリズムの大規模な実施を次に説明する。２つのＥＭアルゴリズムは、次のようないくつかの共通の計算上の側面を共有している。（１）潜在的要素ＵおよびＶを評価する代わりに、上記アルゴリズムは近似行列Ｘを処理する、（２）主な計算の負担はＥ−ステップである、（３）いずれの場合においても、Ｅ−ステップはｘi（ただし、ｉ＝１，．．．，Ｍ）の独立した更新に分解される、（４）ｘiの各更新に対して、カーネルトリックがＹの疎性を活用するのに適用される。最後の２つの特性は若干の望みをもたらすが、稚拙な実施は大規模なデータにはなお高価すぎる。例えば、Ｎｅｔｆｌｉｘ問題では、たった１つのＥ−ステップが、３．０ＧＨｚのＣＰＵおよび３.０Ｇメモリを持つＰＣ上でｉＳＶＤにより４０時間以上消費する。さらに悪いことに、ｐＰＣＡはＸの分布を考慮に入れて、数式（１２）によりその２次統計量を算出するので、該計算は単一のＥ−ステップでさらに４,０００時間かかる。以下では、数式（６）または（１１）の計算コストを著しく低減することができ、数式（１２）によってもたらされるオーバーヘッドをほぼ完全に回避することができる。その結果、ｉＳＶＤは低階数行列因子分解法と同じくらい高速になるが、一方ｐＰＣＡはその非確率的な相当ｉＳＶＤと同じくらい高速になる。
ｉＳＶＤ
ｉＳＶＤのボトルネックである数式（６）の計算コストは、計算を次式のように書き換えることによって低減される。
【００４２】
ｘi＝Ｋｚi
ここで、ＫはＮ×Ｎの完全なカーネル行列であり、ｚi∈ＲNは、位置Ｏiでゼロの要素を除いたゼロのベクトルであり、その値は次式によって割り当てられる。
【００４３】
ｚOi＝（ＫOi＋γＩ）-1ｙOi
次の数式（１５）から、数式（６）の再定式化は、明示的にＸを算出することなく数式（７）を実現できることを示唆している。
【００４４】
【数９】
【００４５】
上述の解析は、すべての行ｉに対して、システムが長さ｜Ｏi｜のベクトルｚOiを持つＮ×｜Ｏi｜行列Ｋ:Oiの乗算と、Ｎ2の乗算ｘiｘiT（すなわち、より小さな｜Ｏi｜2の乗算ｚOiｚOiTと置き換えられた）とを回避できることを示唆している。全体として、システムは、
【００４６】
【数１０】
【００４７】
の乗算演算の減少を得る。Ｎｅｔｆｌｉｘデータについて、このことは、１つのＥ−ステップについて４０時間以上の減少を意味しており、結果として発生する計算は４時間未満となる。
【００４８】
次の計算は数式（７）によって必要とされる固有値分解である。トレースノルム正規化は階数最小化ヒューリスティックであるので、いくつかのステップの後でＫが階数Ｒの場合、次のＫは、数式（１５）に基づいてＲより小さい階数を持つ。したがって、システムは各反復でＫの階数Ｒをチェックし、次の反復でＫの先行の階層Ｒの固有値のみを算出する。
【００４９】
擬似コードがアルゴリズム１によって記述される。記述をコンパクトに維持するために、（１）予測がバリデーション要素の小さな集合について低下した場合、該低下が起こったらプログラムを中止する、（２）ＱおよびＳを用いて、ステップ１をＫＢＫ＝ＱＳ（ＱＢＱ）ＳＱTによって算出し、結果として発生した行列はＫ用のメモリに格納される、ということを含んだ重要でない詳細については省略する。最大のメモリ消費は、システムが全体としてＮ（Ｎ−１）のメモリコストがかかる２つのＮ×Ｎ行列ＢおよびＫを格納する内側ループ中に生じる。ＯΣi=1M｜Ｏi｜3である主要な計算も内側ループであり、こ
こで、｜Ｏi｜＝Ｎである。Ｋを得た後、（ｉ，ｊ）の欠損要素に対する予測は、Ｘi,j＝Ｋj,Oi（ＫOi＋σ2Ｉ）-1ｙOiによる。
【００５０】
【表１】
【００５１】
上述の処理について、
１．Ｙ：疎なＭ×Νの評価行列、Ｍ個のユーザ、Ν個のアイテム
２．ガンマ（γ）：正則化パラメータ
３．ｉｔｅｒmax：アルゴリズムの最大反復回数
４．Ｋ：Ｎ×Ｎのカーネル行列、このアルゴリズムが最後に最適化して出力するパラメータ
５．Ｂ：Ｎ×Ｎ行列、これはステップ９でいくつかの中間結果を格納するのに用いられる
６．ｔ：Ｎ×１ベクトル、これはステップ８でいくつかの中間結果を格納するのに用いられる。
７．Ｒ：ステップ１１での固有値行列因子分解の階数
８．ｉｔｅｒ：現在の反復回数
９．ｉ：アルゴリズムによって現在処理されているユーザの指標
１０．Ｑ、Ｓ：行列ＫＢＫの固有値分解ＱＳＱ’の結果、ここで、Ｑ’はＱの転置、ＱはＮｘＲの行列、ＳはＮ×Ｎ対角行列である。
【００５２】
図２は典型的なｉＳＶＤ処理を示している。ｂ０で、該処理は必要な入力を受け取る。次にｂ１で、処理は、対称なｎ×ｎ行列ＫおよびＢを格納するメモリを事前に割り当てる。ｂ２で、処理は複数のパラメータを初期化し、その結果、ｉｔｅｒは０にリセットされ、Ｋは単位行列になり、およびＲはアイテム数Ｎに等しくなる。次に、ｂ３からｂ８で、処理は現在の反復回数を示すカウンタｉｔｅｒでループする。ｂ４で、ｉは現在処理されているユーザの指標である。ｂ５で、処理は、Ｋの現在の値が与えられると、ユーザＩの局所統計量および更新Ｂを収集する。ｂ６で、処理は、Ｍ個のユーザがすべて処理されているかどうかをチェックする。処理されていない場合、ｂ４にジャンプすることによって次のユーザを処理する。ｂ７は、アルゴリズム１のステップ１１〜１５を実行してＫを更新する。ｂ８で、処理は最大反復回数に達しているかどうかをチェックする。達していない場合、さらなる反復のためにｂ３へジャンプする。ｂ９で、達している場合、処理は計算を終了し、結果としてＫを返す。
ｉＰＣＡ
非確率的なｉＳＶＤと比較して、ｉＰＣＡのＥ−ステップは、すべてのｉ＝１，．．．，Ｍに対してＮ×Ｎの事後共分散行列を算出する１つの追加ステップ（１２）を持っている。しかしながら、オーバーヘッドはほぼ回避可能である。Ｂを、要素がゼロとして初期化され、次に次式によって局所情報を収集するのに用いられる、Ｎ×Ｎ行列としよう。
【００５３】
ＢOi←ＢOi−Ｇi＋ｚOiｚOiT（ただし、ｉ＝１，．．．，Ｍ） （１６）
ここで、Ｇi＝（ＫOi＋σ2Ｉ）-1、およびｚoi＝Ｇi＊ｙOiである。上式が与えられると、Ｍ−ステップ（１３）は次式によって実現することができる。
【００５４】
Ｋ←Ｋ＋（１／Ｍ）ＫＢＫ． （１７）
それ故、すべてのｉに対してＮ×Ｎの事後共分散行列を算出する数式（１２）を明示的に行う必要性はなく、このことは、ＮΣi=1M｜Ｏi｜2＋Ｎ2Σi=1M｜Ｏi｜回の乗算
を不要にする。Νｅｔｆｌｉｘ問題において、これは１つのＥ−ステップについて４，０００時間以上短縮することになる。擬似コードがアルゴリズム２で与えられる。
【００５５】
【表２】
【００５６】
【表３】
【００５７】
図３を説明する際に、次の表記を用いている。
１．Ｙ：疎なＭ×Νの評価行列、Ｍ個のユーザ、Ν個のアイテム
２．ｉｔｅｒmax：アルゴリズムの最大反復回数
３．Ｋ：Ｎ×Ｎのカーネル行列、このアルゴリズムが最後に最適化して出力するパラメータ
４．Ｂ：Ｎ×Ｎ行列、これはステップ１３でいくつかの中間結果を格納するのに用いられる
５．Ｇ：行列、これはステップ９で中間結果を格納するのに用いられる
６．ｔ：ベクトル、これはステップ１０で中間結果を格納するのに用いられる
７．Ｅｒ：スカラー、これはステップ１１および１２で中間結果を格納するのに用いられる
８．ｉｔｅｒ：現在の反復回数
９．ｉ：アルゴリズムによって現在処理されているユーザの指標
１０．シグマ（σ）：雑音の標準偏差、σ2は雑音の分散である。
【００５８】
図３は典型的なｉＰＣＡ処理を示している。この処理で、ｃ０は必要な入力を受け取る。ｃ１で、処理は、対称なＮ×Ｎ行列ＫおよびＢを格納するメモリを事前に割り当てる。次にｃ２で、処理はいくつかのパラメータを初期化し、その結果、ｉｔｅｒは０にリセットされ、Ｋは単位行列になる。ｃ３で、現在の反復回数がインクリメントされ、Ｂ、Ｅｒ、およびｉがリセットされる。ｃ４で、現在処理されているユーザの指標ｉがインクリメントされる。ｃ５で、各ユーザの局所統計量が収集され、ＢおよびＥｒが更新される。ｃ６で、処理は、Ｍ個のユーザがすべて処理されているかどうかをチェックする。処理されていない場合、ｃ４にジャンプすることによって次のユーザを処理する。ｃ７で、Ｋおよびシグマ（σ）が更新される。次にｃ８で、処理は最大反復回数に達しているかどうかをチェックする。達していない場合、さらなる反復のためにｃ３へジャンプする。処理は、計算を終了し結果としてＫおよびシグマ（σ）を返すｃ９で終わる。
【００５９】
図４は典型的な高速ｉＰＣＡ処理を示している。次の表記が図４の処理に適用される。
１．Ｙ：疎なＭ×Νの評価行列、Ｍ個のユーザ、Ν個のアイテム
２．ｉｔｅｒmax：アルゴリズムの最大反復回数
３．Ｋ：Ｎ×Ｎのカーネル行列、このアルゴリズムが最後に最適化して出力するパラメータ
４．Ｂ：Ｎ×Ｎ行列、これはステップ１１でいくつかの中間結果を格納するのに用いられる
５．ｂ：Ｎ×１ベクトル、これはステップ１０で中間結果を格納するのに用いられる
６．ミュー（μ）：Ｎ×１ベクトル、このアルゴリズムが最後に最適化して出力する他のパラメータ
７．Ｇ：行列、これはステップ８で中間結果を格納するのに用いられる
８．ｔ：ベクトル、これはステップ９で中間結果を格納するのに用いられる
９．ｉｔｅｒ：現在の反復回数
１０．ｉ：アルゴリズムによって現在処理されているユーザの指標。
【００６０】
ここで、図４を参照して、ｄ０で、該処理は必要な入力を受け取る。ｄ１で、処理は、対称なＮ×Ｎ行列ＫおよびＢ、およびＮ×１ベクトルｂおよびミュー（μ）を格納するメモリを事前に割り当てる。ｄ２で、処理はパラメータを初期化し、その結果、ｉｔｅｒは０にリセットされ、Ｋは単位行列になる。ｄ３で現在の反復回数がインクリメントされ、ｄ４で次のユーザが選択される。ｄ５で、現在のユーザの局所統計量が収集され、Ｂおよびｂが更新される。ｄ６で、処理は、Ｍ個のユーザがすべて処理されているかどうかをチェックする。処理されていない場合、ｄ４にジャンプすることによって次のユーザを処理する。ｄ７で、処理は、アルゴリズム３のステップ１３および１４に従ってＫおよびミュー（μ）を更新する。ｄ８で、処理は最大反復回数に達しているかどうかをチェックする。達していない場合、処理はさらなる反復のためにｄ３へジャンプする。ｄ９で、処理は計算を終了し、結果としてＫおよびミュー（μ）を返す。
【００６１】
アルゴリズム２をアルゴリズム１と比較すると、確率的な手法の残りの計算のオーバーヘッドは、雑音の分散σ2の更新を準備して、局所的な不確実性情報を収集するステップにあり、該ステップは各Ｅ−ステップに対して追加のΣi=1M（２｜Ｏi｜2＋｜Ｏi｜
3）回の乗算を必要とする。アルゴリズムをさらに高速化するために、ｉＰＣＡを簡略化することができる。数式（８）の本質的なモデル化推定は、Ｙが、独立して同じくガウス分布Ｎ（０，Ｋ＋σ2Ｉ）に従う行ｙiの集合であるということである。次に、この着想は、雑音および信号を明示的にモデル化するのではなく、処理がＫ←Ｋ＋σ2Ｉによって結合して雑音の多い観測値ｙi（ただし、ｉ＝１，．．．，Ｍ）の共分散を直接処理することにある。得られたモデルは次のように簡単になる。
【００６２】
Ｙi,j：δ（Ｘi,j）（ここで、ｘi：Ｎ（μ，Ｋ） （１８）
さらに、δ（Ｘi,j）は、Ｙi,j＝Ｘi,jの場合に１、そうでなければ０の確率を持つ分布である。このモデルに対して、ＥＭアルゴリズムは次のようになる。
【００６３】
・Ｅ−ステップ：Ｅ（ｘi）＝Ｋ:Oi（ＫOi）-1（ｙOi−μOi）、およびＣｏｖ（ｘi）＝Ｋ−Ｋ:Oi（ＫOi）-1ＫOi
・Ｍ−ステップ：Ｋ←１／ＭΣi=1M［Ｃｏｖ（ｘi）＋Ｅ（ｘi）Ｅ（ｘi）T］お
よびμ←μ＋１／ＭΣi=1MＥ（ｘi）
該実施はアルゴリズム２で要約されている。雑音を評価する必要がないので、Ｅ−ステップでの計算コストは非確率的なアルゴリズム１の計算コストと比べてわずかな違いしかない。アルゴリズム２と比較して、新バージョンは、１つのＥ−ステップで、Ｎｅｔｆｌｉｘデータについて約１１．７時間節減し、たった４時間で終了する。メモリコストも、ＫおよびＢを格納するのにＮ（Ｎ−１）となるアルゴリズム１と同じである。予測は期待値Ｅ（Ｙi,j）＝Ｋj,Oi（ＫOi）-1（ｙOi−μOi）＋μjを算出することによってなされる。その著しい単純性により、ｉＰＣＡのより高速なバージョンを実験で用いた。
【００６４】
次に、説明したアルゴリズム１および２の効率性および精度を、２つの最大の公的に入手可能なベンチマーク、ＥａｃｈＭｏｖｉｅデータおよびＮｅｔｆｌｉｘデータと対照してテストした。
【００６５】
２つのアルゴリズムが、今日まで２つの最大の公的なベンチマークである、大きさ７４，４２４×１，６４８のＥａｃｈＭｏｖｉｅデータおよび大きさ４８０，１８９×１７，７７０のＮｅｔｆｌｉｘデータについてテストされ、効率性と精度の両方について、低階数行列因子分解法によって達成された最先端技術の性能に匹敵するかまたはそれより優れているという結果を達成した。
ＥａｃｈＭｏｖｉｅデータ
１，６４８本の映画に対する７４，４２４人のユーザの２，８１１，７１８個の異なる数的評価を含んだ全体のＥａｃｈＭｏｖｉｅデータに関する一連の実験。平均で要素の９７．１７％が欠損しているので、これは非常に疎な行列である。ランダムに、各ユーザの評価の約８０％がトレーニング用に選択され、残りの２０％がテストケースとして選択された。無作為抽出を２０回独立して行った。次のアルゴリズムがテストされる。
【００６６】
（１）ＳＶＤ：上で説明したｉＳＶＤを加えた２０および４０の次元を持つ低階数ＳＶＤ
２つの低階数法が共役勾配法によって最適化される。停止基準は、トレーニング要素の１つの小さなホールドアウト集合（ｈｏｌｄ−ｏｕｔ ｓｅｔ）の性能に基づいている。各アルゴリズムについて、第１の区画をテストする場合、正則化パラメータが、ホールドアウト集合の性能に基づいて、γ＝１、５、１０、２０、５０、および１００から設定された。
【００６７】
（２）ＰＣＡ：上で説明したｉＰＣＡを加えた２０および４０の次元を持つ低階数ｐＰＣＡ
これらの３つの方法について、停止基準は、ＥＭの反復総数が３０を超えるべきでないということに加えて、ホールドアウト集合にも基づいている。これらのｐＰＣＡモデルに関する素晴らしい利点は、調整する正則化パラメータがないことである！
平均化された結果を示す代わりに、２０回の試行のすべての個々のＲＭＳＥ結果を下の表に挙げている。すべての方法について、ランダムな列／テスト区画にわたる変動量は小さい。ＳＶＤおよびｐＰＣＡの２つのカテゴリーの各々について、無限のモデルは、各自分自身の低階数の相当モデルよりも常に優れた性能を示した。これは、モデルの次元制約を緩和するという利点が確かにあるということを意味している。次に、確率的な手法はそれらのＳＶＤ法より常に優れた性能を示した。特に、ｉＰＣＡは２０回の試行すべてにわたって勝利者である。ｉＰＣＡの平均ＲＭＳＥ誤りは、ｉＳＶＤの平均ＲＭＳＥ誤りより４．３３％低く、ＳＶＤ（次元ｄ＝２０）の平均ＲＭＳＥ誤りより６．９０％低い。この結果は、予測精度に関する確率的なモデルの利点を明確に支持している。
【００６８】
アルゴリズムはＣ＋＋を用いて実行された。２０回の試行を通して平均化された実行時間を表２に報告する。共役勾配を用いたＳＶＤは、非常にゆっくり収束した。上で解析したように、ｉＳＶＤとｉＰＣＡとは本質的に同一の計算コストを持っている。ここで、ｉＳＶＤは検出された過学習により通常５回の反復の後に停止したが、一方該過学習は３０回の反復をすべて終了したｐＰＣＡ法については観測されなかったので、ｉＰＣＡにはより長時間を要した。
【００６９】
【表４】
【００７０】
Ｎｅｔｆｌｉｘデータ
１９９８〜２００５年の期間に得られたＮｅｔｆｌｉｘ．ｃｏｍの評価の分布を表すＮｅｔｆｌｉｘデータが収集された。発表されたトレーニングデータは、１７，７７０本の映画に対する４８０，１８９人のユーザからの１００，４８０，５０７個の評価から成る。さらに、Ｎｅｔｆｌｉｘは、１，４０８，３９５個の評価を持つ検証データ群も提供する。したがって、要素の９８．８１％が評価行列で欠損している。予測精度を評価するために、すべての参加者について値が保留されたおよび不明の２，８１７，１３１個の評価を含んだテストセットがある。テストセットのＲＭＳＥを評価するために、参加者は、ＲＭＳＥ誤りを知らせる電子メールを後で返送するＮｅｔｆｌｉｘに、結果を提出する必要がある。結果は全く同一のテストデータについて評価されるので、それは異なったアルゴリズムを比較するのに優れたプラットフォームを提供する。
【００７１】
アルゴリズム１および２は、検証データの９５％のランダムな集合を加えたトレーニングデータについてテストされ、該検証データの残りの５％は停止基準に用いられた。行列因子分解法による文献で報告されている最先端技術の結果と共に、２つのモデルによって得られた結果を次の表３に示している。異なった性質からなる異種のモデルを合成することによる優れた結果が報告されているが、一方本システムによって達成された結果は単一のモデルを用いている。同表において、ベースラインの結果はＮｅｔｆｌｉｘ自身のアルゴリズムによってなされた。ＢＰＭＦは、これまで低階数法によって最先端技術の精度を生み出した、ＭＣＭＣを用いたベイズの確率的行列因子分解（Ｂａｙｅｓｉａｎ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｍａｔｒｉｘ ｆａｃｔｏｒｉｚａｔｉｏｎ）である。ｉＰＣＡはＢＰＭＦよりもさらに良好な結果を達成し、ベースラインから６．１８％だけ精度を改善した。恐らく正則化パラメータを微調整する必要性があるためであろうが、ｉＳＶＤはこのデータセットについてはあまりうまく動作しなかった。しかしながら、これは、調整するパラメータを持たないｉＰＣＡの利点を際立たせている。実行時間の効率性に関して、両アルゴリズムは１つの反復当たり約５時間を費やした。ｉＰＣＡの結果は３０回の反復によって得られた。
【００７２】
【表５】
【００７３】
無限次元の行列因子分解モデルは大規模な協調フィルタリング問題を解くことができる。該モデルの２つの例とは、特異値分解（ＳＶＤ）および確率的主成分分析（ｐＰＣＡ）である。テストは、無限次元のモデルが１億個の評価を含んだ非常に大規模なデータについて実際に効率的であることを示している。さらに、確率的な手法は非確率的な方法ほどスケーラブルでないと通常考えられているが、ｉＰＣＡは確率的な手法と同じくらい速い非確率的な相当手法である。予測精度に関しては、無限次元のモデルは低階数法より優れた性能を示すことが多く、確率的なモデルは非確率的なモデルよりもより正確な結果を提供した。
【００７４】
本発明は、ハードウェア、ファームウェア、またはソフトウェア、または、これら３つの組み合わせで実行されてもよい。好ましくは、本発明は、プロセッサ、データ記憶システム、揮発性および不揮発性メモリ、および／または記憶素子、少なくとも１つの入力装置、および少なくとも１つの出力装置を持つプログラム可能なコンピュータ上で実行されるコンピュータプログラムで実行される。
【００７５】
例として、システムを支援するコンピュータのブロックダイアグラムを次に説明する。該コンピュータは、プロセッサと、ランダムアクセスメモリ（ＲＡＭ）と、プログラムメモリ（好ましくはフラッシュＲＯＭのような書き込み可能な読み出し専用メモリ（ＲＯＭ））と、ＣＰＵバスによって接続された入出力（Ｉ／Ｏ）制御装置とを含むのが好ましい。コンピュータは、ハードディスクおよびＣＰＵバスに接続されたハードディスクドライブ制御装置を随意に含んでいてもよい。ハードディスクは、本発明のようなアプリケーションプログラム、およびデータを格納するのに使用されてもよい。あるいは、アプリケーションプログラムはＲＡＭまたはＲＯＭに格納されてもよい。入出力制御装置は入出力インタフェースに入出力バスによって接続される。入出力インタフェースは、シリアルリンク、ローカルエリアネットワーク、無線リンク、およびパラレルリンクのような通信リンクを通して、アナログ形態またはディジタル形態のデータを受信し送信する。随意に、表示装置、キーボード、およびポインティングデバイス（マウス）も入出力バスに接続されてもよい。あるいは、個別の接続（個別のバス）が、入出力インタフェース、表示装置、キーボード、およびポインティングデバイス用に使用されてもよい。プログラム可能な処理システムは事前にプリプログラムされていてもよく、または該システムは、他のソース（例えばフロッピーディスク、ＣＤ−ＲＯＭ、または他のコンピュータ）からプログラムをダウンロードすることによってプログラム（および再プログラム）されてもよい。
【００７６】
各コンピュータプログラムは、汎用のまたは専用のプログラム可能コンピュータによって読取り可能な、機械可読の記憶媒体または装置（例えばプログラムメモリまたは磁気ディスク）に明確に格納され、記憶媒体または装置が、ここで説明している手順を実行するコンピュータによって読まれるとき、該コンピュータの動作を構成し、制御する。発明的システムは、コンピュータプログラムで構成されたコンピュータ可読記憶媒体で具体化されると考えることもでき、そのように構成された記憶媒体は、コンピュータをここで説明している機能を実行するように特定の事前に定められた方法で動作させる。
【００７７】
特許法に準拠するために、および新規な原理を適用して、必須のそのような特殊な構成要素を構築して使用するのに必要な情報を当業者に提供するために、本発明をかなり詳細にここで説明した。しかしながら、本発明は明確に異なった設備および装置で実行することができ、種々の修正を、設備詳細および動作手順の両方について、本発明そのものの範囲から逸脱することなく行うことができることが理解されよう。
【００７８】
本発明の具体的実施形態は添付の図面に示されており、前述の詳細な説明で説明されたが、本発明はここで説明している特定の実施形態に限定されるものではなくて、本発明の範囲から逸脱することなく多くの再配置、修正、および代替が可能であることが理解されよう。添付の特許請求の範囲は、そのような修正をすべて包含するように意図されている。
【特許請求の範囲】
【請求項１】
ａ．無限次元の行列因子分解を用いて協調フィルタリングを行うこと、
ｂ．前記協調フィルタリングを用いて１つまたは２つ以上の推薦を発生させること、
ｃ．前記推薦をユーザに表示すること、
を含む、推薦を生成するコンピュータ実施方法。
【請求項２】
データに対して確率的な行列因子分解を行うことを含む請求項１に記載の方法。
【請求項３】
データに対して非確率的な行列因子分解を行うことを含む請求項１に記載の方法。
【請求項４】
ｉＳＶＤ（無限次元の特異値分解）で行列因子分解を行うことを含む請求項１に記載の方法。
【請求項５】
ｐＰＣＡ（無限次元の確率的な主成分分析）で行列因子分解を行うことを含む請求項１に記載の方法。
【請求項６】
１つまたは２つ以上のアイテムに関するユーザの嗜好を収集することを含む請求項１に記載の方法。
【請求項７】
１つまたは２つ以上のアイテムに関するユーザの嗜好の平均値および共分散を収集することを含む、請求項１に記載の方法。
【請求項８】
すべてのユーザに対する大域的アイテム対アイテムの関連性または類似度を決定することを含む、請求項１に記載の方法。
【請求項９】
各ユーザに関連づけられたアイテム対アイテムの関連性または類似度を決定することを含む、請求項１に記載の方法。
【請求項１０】
前記アイテム対アイテムの関連性または類似度を適用してユーザの嗜好を推測することを含む、請求項９に記載の方法。
【請求項１１】
局所統計量を用いて１つまたは２つ以上のアイテムに関するユーザの嗜好の平均値および共分散を推測する、請求項１０に記載の方法。
【請求項１２】
局所統計量はユーザの嗜好およびデータ雑音エラーの共分散を含む請求項１０に記載の方法。
【請求項１３】
前記ユーザの嗜好およびデータ雑音エラーは、処理時間を短縮するために一緒に処理される、請求項１２に記載の方法。
【請求項１４】
各ユーザに関連づけられたアイテム対アイテムの関連性または類似度を含む大域的統計量を生成することを含む、請求項１に記載の方法。
【請求項１５】
正準期待値最大化（ＥＭ）演算を処理することを含む請求項１に記載の方法。
【請求項１６】
Ｋ←Ｋ＋（１／Ｍ）ＫＢＫを決定することを含む請求項１に記載の方法。
【請求項１７】
ａ．無限次元の行列因子分解による協調フィルターを持つプロセッサと、
ｂ．前記プロセッサによって実行され、前記協調フィルターを用いて１つまたは２つ以上の推薦を生成する推薦エンジンと、
ｃ．前記プロセッサによって実行され、ユーザに推薦を与えるユーザインターフェースエンジンと、
を有する、ユーザに対して推薦を生成するシステム。
【請求項１８】
前記行列因子分解はｉＳＶＤ（無限次元の特異値分解）を含む請求項１７に記載のシステム。
【請求項１９】
前記行列因子分解はｐＰＣＡ（無限次元の確率的な主成分分析）を含む請求項１７に記載のシステム。
【請求項２０】
前記行列因子分解は、１つまたは２つ以上のアイテムに関するユーザの嗜好の平均値および共分散を演算する、請求項１７に記載のシステム。
【請求項１】
ａ．無限次元の行列因子分解を用いて協調フィルタリングを行うこと、
ｂ．前記協調フィルタリングを用いて１つまたは２つ以上の推薦を発生させること、
ｃ．前記推薦をユーザに表示すること、
を含む、推薦を生成するコンピュータ実施方法。
【請求項２】
データに対して確率的な行列因子分解を行うことを含む請求項１に記載の方法。
【請求項３】
データに対して非確率的な行列因子分解を行うことを含む請求項１に記載の方法。
【請求項４】
ｉＳＶＤ（無限次元の特異値分解）で行列因子分解を行うことを含む請求項１に記載の方法。
【請求項５】
ｐＰＣＡ（無限次元の確率的な主成分分析）で行列因子分解を行うことを含む請求項１に記載の方法。
【請求項６】
１つまたは２つ以上のアイテムに関するユーザの嗜好を収集することを含む請求項１に記載の方法。
【請求項７】
１つまたは２つ以上のアイテムに関するユーザの嗜好の平均値および共分散を収集することを含む、請求項１に記載の方法。
【請求項８】
すべてのユーザに対する大域的アイテム対アイテムの関連性または類似度を決定することを含む、請求項１に記載の方法。
【請求項９】
各ユーザに関連づけられたアイテム対アイテムの関連性または類似度を決定することを含む、請求項１に記載の方法。
【請求項１０】
前記アイテム対アイテムの関連性または類似度を適用してユーザの嗜好を推測することを含む、請求項９に記載の方法。
【請求項１１】
局所統計量を用いて１つまたは２つ以上のアイテムに関するユーザの嗜好の平均値および共分散を推測する、請求項１０に記載の方法。
【請求項１２】
局所統計量はユーザの嗜好およびデータ雑音エラーの共分散を含む請求項１０に記載の方法。
【請求項１３】
前記ユーザの嗜好およびデータ雑音エラーは、処理時間を短縮するために一緒に処理される、請求項１２に記載の方法。
【請求項１４】
各ユーザに関連づけられたアイテム対アイテムの関連性または類似度を含む大域的統計量を生成することを含む、請求項１に記載の方法。
【請求項１５】
正準期待値最大化（ＥＭ）演算を処理することを含む請求項１に記載の方法。
【請求項１６】
Ｋ←Ｋ＋（１／Ｍ）ＫＢＫを決定することを含む請求項１に記載の方法。
【請求項１７】
ａ．無限次元の行列因子分解による協調フィルターを持つプロセッサと、
ｂ．前記プロセッサによって実行され、前記協調フィルターを用いて１つまたは２つ以上の推薦を生成する推薦エンジンと、
ｃ．前記プロセッサによって実行され、ユーザに推薦を与えるユーザインターフェースエンジンと、
を有する、ユーザに対して推薦を生成するシステム。
【請求項１８】
前記行列因子分解はｉＳＶＤ（無限次元の特異値分解）を含む請求項１７に記載のシステム。
【請求項１９】
前記行列因子分解はｐＰＣＡ（無限次元の確率的な主成分分析）を含む請求項１７に記載のシステム。
【請求項２０】
前記行列因子分解は、１つまたは２つ以上のアイテムに関するユーザの嗜好の平均値および共分散を演算する、請求項１７に記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公表番号】特表２０１１−５２３７５３（Ｐ２０１１−５２３７５３Ａ）
【公表日】平成２３年８月１８日（２０１１．８．１８）
【国際特許分類】
【出願番号】特願２０１１−５１２４４１（Ｐ２０１１−５１２４４１）
【出願日】平成２０年１２月２２日（２００８．１２．２２）
【国際出願番号】ＰＣＴ／ＵＳ２００８／０８７９８５
【国際公開番号】ＷＯ２００９／１４８４７５
【国際公開日】平成２１年１２月１０日（２００９．１２．１０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５０４０８０６６３）エヌイーシー ラボラトリーズ アメリカ インク (68)
【氏名又は名称原語表記】ＮＥＣ Ｌａｂｏｒａｔｏｒｉｅｓ Ａｍｅｒｉｃａ， Ｉｎｃ．
【Ｆターム（参考）】
【公表日】平成２３年８月１８日（２０１１．８．１８）
【国際特許分類】
【出願日】平成２０年１２月２２日（２００８．１２．２２）
【国際出願番号】ＰＣＴ／ＵＳ２００８／０８７９８５
【国際公開番号】ＷＯ２００９／１４８４７５
【国際公開日】平成２１年１２月１０日（２００９．１２．１０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５０４０８０６６３）エヌイーシー ラボラトリーズ アメリカ インク (68)
【氏名又は名称原語表記】ＮＥＣ Ｌａｂｏｒａｔｏｒｉｅｓ Ａｍｅｒｉｃａ， Ｉｎｃ．
【Ｆターム（参考）】
[ Back to top ]