🔨 🔵 🖕🏾 レコメンダーシステムの仕組み。 Yandexでの講義 🕙 🏻 🎚️

こんにちは、私の名前はマイケル・ロイズナーです。最近、Yandex Small Shadの学生に、推奨システムとは何か、どのような方法があるのかについて講義しました。講義に基づいて、この投稿を準備しました。

講義計画：

推奨システムの種類と用途。
最も単純なアルゴリズム。
線形代数の紹介。
SVDアルゴリズム。
推奨の品質の測定。
開発の方向。

簡単なものから始めましょう。一般的な推奨システムとは何か、それらは何ですか。おそらく誰もがすでにインターネット上でそれらに遭遇しています。最初の例は映画推薦システムです。

imdb.comでは、ユーザーは映画を10段階で評価できます。評価は集計されており、映画の平均評価です。同じサイトには、特定のユーザー向けの推奨事項を含むブロックがあります。私がサイトに行っていくつかの映画を評価すると、imdbは私に他の映画を勧めることができます。 Facebookにも同様のブロックがあります。

last.fmも同様の機能を備えていますが、音楽専用です。彼は私に行くべきアーティスト、アルバム、イベントを勧めています。ロシアでのPandoraサービスはほとんど不明です。それは私たちには機能しませんが、アメリカでは非常に人気があります。これは個人のラジオであり、ユーザーの評価に基づいて徐々にユーザーに適応し、その結果、好きな曲だけを再生します。

別の注目すべき分野は、製品の推奨事項です。下の写真には、もちろんAmazonがあります。アマゾンで何かを購入した場合、彼らは追加のオファーであなたを探します：同様の商品やアクセサリー。これはユーザーにとって有益であり（これらの製品を自分で検索する必要はありません）、そしてもちろん、ストア自体にとっても有益です。

私たちは3つのカテゴリをリストしましたが、実際にはもっとたくさんあります。地図上の機関、ニュース、記事、ウェブサイト、コンサート、劇場、展示会、ビデオ、書籍、アプリケーション、ゲーム、旅行、ソーシャルネットワークなどです。

推奨システムの種類

推奨システムには、主に2つのタイプがあります。もちろん、それらはもっとありますが、今日はこれら、特にコラボレーションフィルタリングを正確に検討します。

コンテンツベース
- ユーザーは、このユーザーが既に使用しているものと同様の推奨オブジェクトです。
- 類似性は、オブジェクトのコンテンツに基づいて評価されます。
- サブジェクト領域に強く依存しているため、推奨事項の有用性は限られています。
協調フィルタリング
- 推奨事項には、ユーザーと他のユーザーの両方の評価履歴が使用されます。
- 多くの場合、より普遍的なアプローチがより良い結果をもたらします。
- 問題があります（コールドスタートなど）。

推奨システムは、約20年前の昔、インターネットに登場しました。しかし、この分野の本当の上昇は、約5〜10年前にNetflix賞のコンテストが開催されたときに起こりました。 Netflixは、デジタルコピーではなく、VHSテープとDVDを配布しました。推薦の質を改善することは彼らにとって非常に重要でした。 Netflixがユーザーに映画をすすめるほど、より多くの映画をレンタルできます。したがって、会社の利益は成長しています。 2006年に、彼らはNetflix賞のコンテストを開始しました。収集したデータをオープンアクセスで共有しました。5ポイントスケールで約1億件の評価を、それらを置いたユーザーのIDで共有しました。コンテストの参加者は、特定のユーザーが特定の映画にどのような評価を与えるかを予測するために、可能な限り優れている必要がありました。予測の品質は、 RMSE （標準偏差）メトリックを使用して測定されました。 Netflixには、RMSEメトリックに従って0.9514の品質でユーザー評価を予測するアルゴリズムが既にありました。タスクは、予測を少なくとも10％-0.8563に改善することでした。優勝者には賞金100万ドルが約束され、約3年間続きました。初年度に品質が7％改善され、その後すべてが少し遅くなりました。しかし、最後に、差が20分の2つのチームがソリューションを送信し、それぞれが10％のしきい値を超えました。品質は同じで、4桁目まで正確でした。多くのチームが3年間戦ったこの問題では、全員が約20分間決定しました。後期チーム（他の多くの競技者と同様）には何も残されていませんでしたが、競技会自体がこの分野の発展に大きな拍車をかけました。

最も単純なアルゴリズム

まず、タスクを形式化します。何がありますか？多くのユーザー𝑢∈𝑈、多くのオブジェクト𝑖∈𝐼（映画、トラック、製品など）および多くのイベント（ _𝑟𝑢𝑖 、𝑢、𝑖、...）∈𝒟（ユーザーが実行するアクションオブジェクト）。各イベントは、ユーザー𝑢、オブジェクト𝑖、その結果_𝑟𝑢𝑖 、および場合によってはその他の特性によって定義されます。それは私たちに必要です：

好みを予測する：
𝑟̂𝑢𝑖= Predict（𝑢、𝑖、...） _{≈𝑟𝑢𝑖} 。
個人的な推奨事項：
𝑢⟼（𝑖1、...、 _𝑖𝘒 ）= Recommend（𝑢、...）を推奨します。
同様のオブジェクト：
𝑢⟼（𝑖1、...、 _𝑖𝑀 ）=同様の_𝑀 （𝑖）。

成績表

ユーザー評価のテーブルが与えられたとしましょう：

疑問符の付いたセルにどのグレードを含めるべきかをできるだけ予測する必要があります。

ユーザークラスタリング

協調フィルタリングの主な考え方は、類似したユーザーは通常類似したオブジェクトを好むということです。最も簡単な方法から始めましょう。

評価履歴に基づいて、ユーザーの類似性の条件付き尺度を選択します（𝑣、𝑣）。
同様のユーザーが1つのクラスターに表示されるように、ユーザーをグループ（クラスター）に統合します：𝑢⟼𝐹（𝑢）。
オブジェクトのユーザー評価は、このオブジェクトの平均クラスター評価として予測されます。

このアルゴリズムにはいくつかの問題があります。

新規/非定型ユーザーに推奨するものはありません。そのようなユーザーには、それらに似たユーザーを持つ適切なクラスターはありません。
各ユーザーの詳細は考慮されません。ある意味では、すべてのユーザーをいくつかのクラス（テンプレート）に分割します。
クラスター内のオブジェクトを評価したユーザーがいない場合、予測は機能しません。

ユーザーベース

以前の方法をいくらか改善し、ハードクラスタリングを次の式に置き換えてみましょう。

ただし、このアルゴリズムには問題もあります。

新規/非定型ユーザーに推奨するものはありません。そのようなユーザーについては、同様のユーザーはまだ見つかりません。
コールドスタート-新しい施設は誰にも推奨されません。

アイテムベース

絶対に対称的なアルゴリズムがあります：

前の方法では、友人が気に入ったらユーザーが映画を好むという考えから始めました。ここでは、ユーザーが類似の映画が好きなら、その映画が好きになると信じています。

問題は次のとおりです。

コールドスタート-新しい施設は誰にも推奨されません。
推奨事項はしばしば些細なものです。

リストされたメソッドの一般的な問題

これらの方法にはすべて、次の欠点があります。

コールドスタートの問題。
新規/非定型ユーザー/オブジェクトの予測不良。
推奨事項の自明性。
計算のリソース強度。予測を行うには、すべてのユーザーのすべての評価を念頭に置く必要があります。

したがって、実際にはこれらの欠点がない、より複雑なアルゴリズムに進みます。

SVDアルゴリズム

このアルゴリズムには、線形代数からのいくつかの概念が必要です。ベクトル、行列、およびそれらを使用した演算です。ここですべての定義を説明するわけではありません。この知識を更新する必要がある場合、すべての説明は約33分からの講義のビデオにあります。

SVD（特異値分解）、特異行列分解として変換します。特異分解定理では、サイズ𝑛×𝑚の行列anyは、3つの行列product、Ʃおよび𝑉𝑇の積に分解されると述べてい^ます。

行列𝑈と𝑉は直交し、Ʃは対角線（正方形ではありませんが）です。

さらに、行列inのラムダは増加しない順に並べられます。この定理を証明するのではなく、単純に展開そのものを使用します。

しかし、さらに複雑な3つのマトリックスの積に何らかのマトリックスを使用できるという事実についてはどうでしょう。私たちにとって、以下は興味深いものです。通常の分解に加えて、ラムダから最初の𝑑の数だけが残っている場合も切り捨てられ、残りはゼロに等しいと仮定します。

これは、行列𝑈およびforについて、最初のonlyのみを残すという事実と同等です。
列、および行列theを正方形𝑑×𝑑にカットします。

そのため、結果の行列𝐀 'は元の行列wellによく近似し、さらに、標準偏差の観点からは最高の低ランクの近似であることがわかります。

推奨事項のSVD

これをすべて推奨事項に使用する方法は？マトリックスがあり、それを3つのマトリックスの積に分解しました。彼らが正確にレイアウトしたのではなく、おおよそ。 1つのマトリックスの最初の2つのマトリックスの積を示すことにより、すべてを少し単純化します。

ここで、これらすべてのマトリックスから少し逸脱して、結果のアルゴリズムに集中しましょう。映画userのユーザーの評価predictを予測するために、このユーザーのベクター_𝑝 （パラメーターのセット）とこの映画のベクターvector takeを_取ります。それらのスカラー積は、必要な予測になります： _𝑢𝑢𝑖 = _⟨𝑝need 、 _𝑞𝑖⟩ 。

アルゴリズムは非常に単純ですが、驚くべき結果が得られます。推定値を予測するだけではありません。その助けを借りて、オブジェクトの隠された兆候とユーザーの興味をユーザーの履歴によって明らかにすることができます。たとえば、ベクトルの最初の座標で、各ユーザーは、ユーザーが男の子か女の子のどちらであるかを示す数字、2番目の座標でユーザーのおおよその年齢を反映する数字を持つことがあります。映画では、最初の座標は男の子と女の子のどちらがより面白いかを示し、2番目はユーザーのどの年齢層にとってそれが面白いかを示します。

しかし、それほど単純ではありません。いくつかの問題があります。まず、推定値の行列𝑹が完全にわからないため、SVD分解だけを行うことはできません。第二に、SVD分解は（𝑈Ω）Ʃ（𝑉Ω） _𝑇 = 𝑈Ʃ𝑉 _onlyだけではないため、少なくともいくらかの分解が見つかったとしても、最初の座標がユーザーの性別に対応し、2番目が年齢に対応する可能性は低いです。

トレーニング

最初の問題に対処してみましょう。ここでは、機械学習が必要です。そのため、行列のSVD分解を見つけることができません。マトリックス自体はわかりません。しかし、このアイデアを使用して、SVDと同様の方法で機能する予測モデルを考え出します。私たちのモデルは多くのパラメーターに依存します-ユーザーベクターとフィルム。与えられたパラメータについて、推定値を予測するために、ユーザーベクトル、フィルムベクトルを取得し、それらのスカラー積を取得します。

しかし、ベクターがわからないため、それらを取得する必要があります。私たちのモデルがこれらの評価を可能な限り最適に予測するための最適なパラメーターを見つけることができるユーザー評価があるという考えです。

したがって、二乗誤差ができるだけ小さくなるように、このようなパラメーターθを見つけたいと思います。しかし、パラドックスがあります。私たちは将来 、間違いを減らしたいと思っていますが 、どのような見積もりを求めるのかわかりません。したがって、これを最適化することはできません。しかし、ユーザーがすでに行った評価はわかっています。すでに持っているエラーができるだけ小さくなるように、パラメーターを選択してみましょう。さらに、別の用語-レギュラライザーを追加します。

なぜレギュラーが必要なのですか？

再訓練と戦うために正則化が必要です-構築されたモデルが訓練セットの例をうまく説明するが、訓練に参加しなかった例ではうまく機能しない現象。一般に、再訓練と戦う方法はいくつかありますが、そのうちの2つに注目したいと思います。まず、単純なモデルを選択する必要があります。モデルが単純であるほど、将来のデータに対してより一般化されます（これは、Occamのかみそりのよく知られた原理に似ています）。そして、2番目の方法は正則化です。トレーニングセットのモデルを調整するとき、エラーを最適化します。正則化とは、エラーだけでなく、エラーとパラメーターの機能（パラメーターベクトルのノルムなど）を最適化することです。これにより、ソリューションのパラメーターのサイズを制限し、モデルの自由度を減らすことができます。

数値最適化

どのようにして最適なパラメーターを見つけるのですか？この機能を最適化する必要があります。

多くのパラメーターがあります。ユーザーごと、オブジェクトごとに、最適化する独自のベクターがあります。多数の変数に依存する関数があります。彼女の最小値を見つける方法は？ここでは勾配が必要です-各パラメーターの偏導関数のベクトル。

グラデーションは視覚化するのに非常に便利です。この図には、表面があります。2つの変数の関数です。たとえば、高度。そして、特定のポイントでの勾配は、関数が最も大きくなる方向に向けられたベクトルです。そして、このポイントから水を流した場合、それは勾配とは反対の方向に流れます。

最も有名な関数最適化手法は勾配降下法です。多くの変数の関数があると仮定して、それを最適化します。初期値を取得し、次にこの値を最小化するために移動できる場所を探します。勾配降下法は反復アルゴリズムです。特定の点のパラメータを繰り返し取得し、勾配を見て、その方向に反してステップします。

この方法の問題は、第一に、私たちの場合、非常にゆっくりと動作し、第二に、グローバルな最小値ではなくローカルな最小値を見つけることです。 2番目の問題は、私たちにとってそれほど怖いものではありません。私たちの場合、局所的最小値での汎関数の値はグローバルな最適値に近いです。

交互最小二乗

ただし、勾配降下法を常に使用する必要はありません。たとえば、放物線の最小値を計算する必要がある場合、このメソッドを使用する必要はありません。その最小値がどこにあるかを正確に知ることができます。最適化しようとしている関数-誤差の合計とすべてのパラメーターの平方の合計-も二次関数であり、放物線に非常に似ていることがわかります。特定のパラメーターごとに、他のパラメーターをすべて修正すると、放物線になります。つまり少なくとも1つの座標、正確に決定できます。交互最小二乗法は、この考慮事項に基づいています。私はそれについて詳しく説明しません。その中で、ある座標または別の座標で最小値を交互に正確に見つけることができるとしか言えません。

オブジェクトのすべてのパラメーターを修正し、ユーザーパラメーターを正確に最適化してから、ユーザーパラメーターを修正してオブジェクトパラメーターを最適化します。私たちは繰り返し行動します：

これはすべて非常に迅速に機能しますが、各ステップは並列化できます。

推奨の品質の測定

推奨事項の品質を改善したい場合、それを測定する方法を学ぶ必要があります。このため、あるサンプルでトレーニングされたアルゴリズム-トレーニング、別のサンプルでチェックされます-テスト。 Netflixは、RMSEメトリックの推奨事項の品質を測定することを提案しました。

今日では、スコアを予測するための標準的なメトリックです。ただし、次のような欠点があります。

各ユーザーは、評価尺度について独自の考えを持っています。評価の範囲が広いユーザーは、他のユーザーよりもメトリックの値により大きな影響を与えます。
高得点の予測における誤差は、低得点の予測における誤差と同じ重みを持っています。同時に、真のスコア7の代わりに9のスコアを予測することは、2の代わりに4を予測するよりも悪い（10点スケールで）。
ほぼ完璧なRMSEメトリックを使用できますが、品質ランキングは非常に低く、その逆も同様です。

その他の推奨プロパティ

推奨の認識は、ランキングの品質だけでなく、他のいくつかの特性にも影響されることがわかります。たとえば、多様性（1つのトピックまたはシリーズのみでユーザーに映画を提供するべきではありません）、驚き（非常に人気のある映画を推奨する場合、そのような推奨事項はあまりにも平凡でほとんど役に立たないでしょう）、ノベルティ（古典的な映画のような多くの人々が、推奨事項通常、新しい何かを発見するために使用されます）および他の多く。

同様の特性

オブジェクトの類似性はそれほど明白ではありません。このタスクにはさまざまなアプローチがあります。

類似オブジェクトとは、特性が類似している（コンテンツベースの）オブジェクトです。
同様のオブジェクトは、よく一緒に使用されるオブジェクトです（「𝑖を購入した顧客は、boughtも購入しました」）。
同様のオブジェクトは、このオブジェクトを気に入ったユーザーへの推奨事項です。
同様のオブジェクトは、特定のオブジェクトがコンテキストとして機能する単なる推奨事項です。

開発方向

概念的な問題

予測推奨リストを作成する方法は？（通常のトップは常に良いアイデアではありません。）
予測ではなく、推奨の品質を改善する方法は？
オブジェクトの類似性を測定する方法は？
推奨事項を正当化する方法は？（いくつかの説明を提供すれば、ユーザーは推奨をはるかによく理解することがわかります。）

技術的な問題

新しいユーザーと新しいオブジェクトのコールドスタートの問題を解決する方法
推奨事項をすばやく更新する方法は？（推奨事項をサービスに導入することの有用性は、これに大きく依存します。）
予測が最も高いオブジェクトをすばやく見つける方法は？
オンラインの推奨事項の品質を測定する方法は？（トレーニングおよびテストサンプルを使用した従来のアプローチは、うまく機能しない場合があります。）
システムのスケーリング方法

追加情報の説明方法は？

明示的なフィードバックだけでなく、暗黙的なフィードバックも考慮する方法は？（暗黙のフィードバックは、しばしば数桁大きくなります。）
コンテキストを考慮する方法は？ （コンテキスト対応の推奨事項）
オブジェクトの兆候を考慮する方法は？ （ハイブリッドシステム）
オブジェクト間の関係を考慮する方法は？ （分類）
ユーザーのサインと関係を考慮する方法は？
他のソースやサブジェクト領域からの情報を考慮する方法は？ （クロスドメインの推奨事項）

文学

代数入門 、コストリキンA. I.
数学的分析 、Zorich V.A.
機械学習 、ボロンツォフK.V.、講義コース

レコメンダーシステムの仕組み。 Yandexでの講義