プッシュシステムにおけるSVDの詳細な応用とアルゴリズムの導出

1 Star2 Stars3 Stars4 Stars5 Stars (まだ評価されていません)
Loading...

再版は、ソースhttp://blog.csdn.net/zhongkejingwang/article/details/43083603を宣言してください

前回の記事では、 SVDの原理と導出により、SVDプロセスが非常に明確になりました。この記事では、SVDを推奨システムのスコアリング予測問題に適用する方法について説明します。 実際、それはNetFlixコンテストとその拡張RSVDとSVD ++でKorenが使用するSVDアルゴリズムの再現です。

私はSVDと初めて会ったときに兄と一緒にプロジェクトに取り掛かっていた時にこのことを使ったことを覚えています。その後、3学期后、Baiduは映画推薦アルゴリズムコンテストを開催して参加しました。 SVDはこれだけを使用しますが、その後は効果が悪くないと思うので、Korenの論文をもう一度見つけました.SVD ++を見て、2つの結果の融合を実感しました。 最終試合の結果は次のとおりです。

実際には、結果は11番目のチームとマージされるので、結果は同じです。 しかし、SVDとSVD ++を単独で使用した結果、0.606に達することができました。その結果はすでに非常に強く、0.6111が2週間以上にわたってこのリストに残っていたことを覚えています。 当時の後悔は、SVDエクステンションアルゴリズムを実装することができず、融合の結果を改善することができなかったことであり、時間の浪費によりコードが膨らんだこともありました。アルゴリズムはgithubで共有されています。興味がある場合は、http: //github.com/jingchenUSTC/SVDRecommenderSystemをご覧ください。

次のユーザとアイテムのデータ行列があると仮定して、SVDアルゴリズムから始めましょう。

これは非常に疎な行列です。ここでは、このスコアリング行列をRとして記録します。その中の要素は項目のユーザーのスコアを表し、「?」は不明であることを示します。つまり、予測する方法です。未知の評価とは何ですか? 前の記事では、任意の行列Aに対して、完全ランク分解を持つことを証明するためにSVDを使用しました。

次に、スコアリング行列Rの分解が行われるので、2つの行列PおよびQの積を用いてスコアリング行列Rを表すことができる。

上の図のUはユーザ数を示し、Iは項目数を示します。 次に、PとQを乗算した結果が既知のスコアに最もよく適合するように、PとQを訓練するためにRの既知のスコアを使用すると、未知のスコアにQの列を掛けてQの列を得ることができる。上:

これは、項目iのユーザuのスコアの予測であり、P行列のu番目の行にQ行列のi番目の列を掛けたものに等しい。 これは最も基本的なSVDアルゴリズムですので、既知のスコアトレーニングでPとQの特定の値をどのように取得しますか?

既知の格付けは以下の通りであると仮定する。

真値と予測値との誤差は、

次に、二乗誤差の総和を計算することができます。

SSEが訓練によって最小化されている限り、PとQはRに最もよくフィットします。 SSEをどのように最小化しますか? 以下に、一般的に使用される局所最適化アルゴリズムについて説明します。

グラデーション降下

勾配降下法を説明するために、私はPPTを見つけました:

つまり、目的関数を最小限にするには、負の勾配の方向に検索する必要があります。 これは勾配降下法であり、局所最適化アルゴリズムであり、グローバル最適解ではなく局所最適解に落ちる可能性があることに注意してください。

基本SVD

勾配降下法を用いて、Puk変数におけるSSEの勾配(すなわち、P行列のuth行およびk列の値)を得ることができる。

連鎖の規則を使用して、e ^ 2は最初にeを導出し、eにそれを乗じてPuk:

〜のために

だから

上の数式のカッコ内の数式が展開されている場合、Pukに関連する項目はPukQkiのみであり、他の無関係な項目はPukに対して0になります。

したがって、決定の結果は次のとおりです。

だから

数式をより簡潔にするために、

これは結果に影響を及ぼさず、結果の前に2を取り除くだけでよく見えます。 取得する

Pukにおける目的関数の勾配が得られたので、Pukは勾配降下法に従って負の勾配の方向に変更される。

更新されたステップサイズ(学習率)を作成する

その後、Pukのアップデートは

Qikのアップデートを入手するのと同じ方法です

更新された数式を取得して、この更新プログラムの実行方法について説明しましょう。 2つのオプションがあります。1.すべての既知スコアの予測誤差を更新し、PとQを更新します。 2.各euiが計算された直後にPuとqiを更新する。 両方のメソッドには名前があります:1.バッチグラジエントを下げます。 ランダムな勾配が減少する。 この2つの違いは、この反復の更新された値を使用するために、次の反復でバッチ勾配が減少することです。この反復における現在のサンプルで使用される値は、前のサンプル更新の値である可能性があります。 ランダム性は、局所最適解を回避するなど、多くの利点をもたらすことができるため、現在、更新のためにランダム勾配降下を使用する傾向があります。

RSVD

上記は基本的なSVDアルゴリズムですが、問題は、上記のトレーニングが既知のスコアリングデータ用であることです。データのこの部分をオーバーフィットすると、テスト結果が悪くなり、テストセットのパフォーマンスが低下する可能性があります。 これはオーバーフィット問題です。オーバーフィットとアンダーフィッティングについては、この画像を見ることができます。

最初はアンダーフィット、2番目はちょうどいい、3番目はオーバーフィットです。 オーバーフィットを回避する方法は? 目的関数に対しては、P行列とQ行列のすべての値が変数です。これらの変数は、どの変数が桁あふれにつながるか分かりません。次に、すべての変数にペナルティを課します。

このとき、目的関数の導関数はPukに変わり、今度はペナルティの後の導関数が追加されます。

カッコ内の最初の項目はPukのガイダンスを求められています.2番目の項目はPukで簡単に見つかります.3番目の項目はPukとは関係がなく、微分は0です。

同様に、qikに対するSSEの導関数は

これらの2つの変数を負の勾配の方向に変更し、式を次のように更新します。

これはRSVDとも呼ばれる正規化されたSVDです。

バイアス付きSVD、RSVDを追加

SVDアルゴリズムのバリエーションが多すぎ、名前が統一されていません。予測式にパラメータを追加すると名前が付けられます。 ユーザーの製品の得点は、ユーザーと製品の特定の関係だけでなく、ユーザーと製品の固有の性質にも依存するため、KorenはSVD予測式をこれに変更します。

最初の項目は合計平均スコア、buはユーザuの属性値、biは項目iの属性値です。追加された2つの変数もまたSSEの公式で処罰する必要があります。

上の方程式から、SSEはPukとqikの微分に変化はないが、この時点ではbuとbiの変数が多く、更新も必要であることが分かる。 まずbuとなるSSEの導関数を求め、最初の項と4番目の項のみがbuに関係する。buの最初の項の導出は前の導出と同様であり、連鎖規則によって得られ、4番目の項は直接導出される。はい、最終的な偏微分は次のようになります。

同様に、biの導関数は

その負の勾配方向に変更して、その更新を

これは修正されたSVD(RSVD)です。

ASVD

正式名称はAsymmetric-SVDで、これは非対称SVDであり、その予測式は次のとおりです。

R(u)は、ユーザuが評価した商品の集合を表し、N(u)はユーザuが閲覧したが評価していない項目の集合を表し、XjおよびYjはその項目の属性である。 このモデルは非常に興味深い。予測式を見ると、ユーザ行列Pは削除されているのではなく、ユーザ属性がユーザ属性を表すために使用され、ユーザがまだスコアリングされていない製品の属性をブラウズした。行動記録自体は、ユーザの嗜好を反映することができる。 さらに、このモデルは大きな利点をもたらすことができます。モールやウェブサイトのユーザー数は数万〜数十億です。ユーザー属性を格納する2次元マトリックスは巨大なストレージスペースを占めますが、製品数はそれほど多くありません。したがって、このモデルの利点は明らかです。 しかし、それには欠点があります。つまり、反復時間が長すぎます。これは予測可能なものであり、スペースを変更する時間があります。

同様に、各パラメータの偏微分を計算し、更新式を見つける必要があります。明らかに、buとbiの更新式は今取得したものと同じです。

ベクトルzは、以下に等しい

ここで、qik、xとyの更新が必要です.puをPuと見てみると、以前に取得した更新メソッドに従ってqikの更新を得ることができます:

Xjの派生物を見つけるにはちょっとした忍耐が必要です.SSEの2番目の項目はXjの派生を得るのが簡単です。

上記の式の総和におけるiとjはR(u)に属し、Zmはm == kのときXjkにのみ関連することが分かる

なぜなら

だから

だからSSEの派生をXjkに

同様に、Yjkに対するSSEの導関数は

だから、XjkとYjkの更新式を得る

これはASVDと呼ばれています。 。 。 。 。 。

SVDPP

最後のモデルは、Korenの記事SVDPlusPlus(SVD ++)にも言及されています。その予測式は次のとおりです。

ここで、N(u)は、ユーザuの行動記録(閲覧され過大評価されたアイテムの集合を含む)を表す。 ASVDの更新された導出プロセスを見ると、非常に簡単であるはずです.Pukとqikの更新式は変わりません.Yjkの更新式はASVDの更新と同じです:

これらは、KorenがNetFlixコンテストで使用したSVDアルゴリズムです。最後にもう一つ言及すべきことがあります:

二重アルゴリズム

RSVDの場合、uとiの位置は等価で対称であるため、デュアルアルゴリズムはそれ自体と変わらないが、ASVDとSVD ++の場合つまり、デュアルアルゴリズムの結果がより正確になることがあります。また、デュアルアルゴリズムと元のアルゴリズムの予測結果を組み合わせると、効果が向上します。

デュアルASVD予測式:

ここで、R(i)はアイテムiをレビューしたユーザの集合を表し、N(i)はアイテムiを見たがコメントを持たないユーザの集合を表す。 多数のユーザーのために、デュアルASVDは多くのスペースを占有し、ここではトレードオフがあります。

デュアルSVD ++予測式:

ここで、N(i)は、アイテムiに対して行動(視聴またはスコア付け)したユーザの集合を表す。

この二重演算を実現するには、実際には非常に単純です。データを読み取る限り、ユーザーIDと製品IDを位置に合わせることができます。つまり、R行列を転置してから訓練します。

一時的に実装されているアルゴリズムはすべてここにあります。コードはgithubにあります。興味がある場合は、チェックアウトしてください 。アドレス: https : //github.com/jingchenUSTC/SVDRecommenderSystem


1 Star2 Stars3 Stars4 Stars5 Stars (まだ評価されていません)
Loading...
      この投稿は審査処理中  | 元のサイトへ