7

ここで機械学習に関する質問をいくつか見たので、関連する質問を投稿することにしました。

丘陵コースの 10 km と 20 km のランニング競技にアスリートが参加するデータセットがあるとします。つまり、すべての競技には独自の難易度があります。

ユーザーからのフィニッシュタイムは、すべての競技でほぼ逆正規分布になっています。

この問題を行列として書くことができます:

       Comp1 Comp2 Comp3
User1  20min  ??   10min

User2  25min 20min 12min

User3  30min 25min ??

User4  30min ??    ??

サイズが 1000x20 で、スパース性が 8% (!) の上記のマトリックスを完成させたいと思います。

すべてのユーザー (能力) のパラメーターとすべての競技のパラメーター (mu、分布のラムダ) を計算できるため、このマトリックスを完成させる非常に簡単な方法があるはずです。さらに、競技間の相関関係は非常に高いです。

ランキング User1 < User2 < User3 および Item3 << Item2 < Item1 を利用できます

どの方法を使用できるかヒントを教えていただけますか？

4

4 に答える 4

7

これが行列補完問題であるというあなたの鋭い観察は、解決への道のりのほとんどをあなたにもたらします。ユーザーの能力とコースの難易度の組み合わせがレースのタイムを生み出すというあなたの直感を体系化し、さまざまなアルゴリズムを提示します。

モデル

u_i がユーザー i の速度になるように、ベクトル u がユーザーの速度を表すとします。ベクトル v がコースの難易度を表し、v_j がコース j の難易度になるようにします。また、可能な場合、t_ij をユーザー i のコース j での時間とし、y_ij = 1/t_ij、コース j でのユーザー i の速度と定義します。

時間は逆ガウス分布であると言うので、観測の賢明なモデルは

y_ij = u_i * v_j + e_ij、

ここで、e_ij はゼロ平均ガウス確率変数です。

このモデルに適合させるために、観測された速度の中で予測誤差を最小化するベクトル u と v を検索します。

f(u,v) = sum_ij (u_i * v_j - y_ij)^2

アルゴリズム 1: 欠損値特異値分解

これは古典的なHebbian アルゴリズムです。勾配降下によって上記のコスト関数を最小化します。u と v に対する f の勾配は

df/du_i = sum_j (u_i * v_j - y_ij) v_j
df/dv_j = sum_i (u_i * v_j - y_ij) u_i

これらの勾配を共役勾配ソルバーまたは BFGS オプティマイザー (MATLABfmin_uncまたは scipy やoptimize.fmin_ncgなど ) にプラグインしoptimize.fmin_bfgsます。非常に優れた直線探索アルゴリズムを実装する意思がない限り、独自の勾配降下をロールバックしないでください。

アルゴリズム 2: トレース ノルム ペナルティを伴う行列分解

最近、この問題に対する単純な凸緩和が提案されました。結果として得られるアルゴリズムは、コードを作成するのと同じくらい簡単で、非常にうまく機能するようです。たとえば、不均一な世界での協調フィルタリング: 加重トレース ノルムを使用した学習 を確認してください。これらのメソッドは、f(m) = sum_ij (m_ij - y_ij)^2 + ||m||_* を最小化します。ここ||.||_*で、 は行列 m のいわゆる核ノルムです。実装は、u と v に関する勾配を再度計算し、非線形オプティマイザに依存することになります。

于 2012-11-25T00:00:22.377 に答える
4

これを行うにはいくつかの方法がありますが、おそらく最初に試すのに最適なアーキテクチャは次のとおりです。

（いつものように、前処理ステップとして、データを平均0、標準偏差1の均一関数に正規化します。これは、関数をすべてのレース結果の分布に当てはめ、その逆数を適用してから減算することで実行できます平均と標準偏差による除算)。

ハイパーパラメータ N を選択します (クロス検証セットを使用して通常どおり調整できます)。

各参加者と各レースに対して、最初はランダムな N 次元の特徴ベクトルを作成します。したがって、R レースと P 参加者がいる場合、合計 N(R+P) 個のパラメーターを持つ R+P 個の特徴ベクトルがあります。

特定の参加者と特定のレースの予測は、2 つの対応する特徴ベクトルの関数です (最初の試みとして、これら 2 つのベクトルのスカラー積を使用します)。

参加者の特徴ベクトルとレースの特徴ベクトルを段階的に改善することを交互に行います。

特徴ベクトルを改善するには、既知のデータ要素 (結果が得られた参加者/レースのペア) に対して勾配降下法 (またはより複雑な最適化手法) を使用します。

つまり、損失関数は次のとおりです。

total_error = 0

forall i,j
    if (Participant i participated in Race j)
        actual = ActualRaceResult(i,j)
        predicted = ScalarProduct(ParticipantFeatures_i, RaceFeatures_j)
        total_error += (actual - predicted)^2

したがって、この関数の偏導関数を特徴ベクトルに対して計算し、通常の ML アルゴリズムに従って段階的に調整します。

(特徴ベクトルの長さの 2 乗など、損失関数に正則化項も含める必要があります)

このアーキテクチャが明確かどうか、またはさらに詳しく説明する必要があるかどうかをお知らせください。

于 2012-11-21T19:58:24.650 に答える
2

これは、失われたデータの回復の古典的なタスクだと思います。いくつかの異なる方法が存在します。私が提案できるそれらの 1 つは、自己組織化機能マップ(Kohonen のマップ)に基づいています。

以下では、すべてのアスリートの記録がパターンであり、すべての競技データが特徴であると想定しています。

基本的に、データを 2 つのセットに分割する必要があります。1 つ目は完全に定義されたパターンで、2 つ目は機能が部分的に失われたパターンです。スパース性が 8% であるため、これは適格であると思います。つまり、破損していないレコードでネットをトレーニングするのに十分なデータ (92%) があるためです。

次に、最初にセットを SOM にフィードし、このデータでトレーニングします。このプロセスでは、すべての機能が使用されます。ここではアルゴリズムをコピーしません。これは、多くの公開ソースで見つけることができ、一部の実装も利用できるためです。

ネットがトレーニングされた後、2 番目のセットからネットにパターンをフィードできます。各パターンについて、ネットは、現在のパターンに存在する機能のみに基づいて、ベスト マッチング ユニット(BMU) を計算する必要があります。次に、欠落している特徴に対応する重みを BMU から取得できます。

別の方法として、データ全体を 2 つのセットに分割することはできませんが、特徴が欠落しているパターンを含むすべてのパターンでネットをトレーニングします。しかし、そのようなパターンについては、学習プロセスを同様に変更する必要があります。つまり、BMU はすべてのパターンの既存の特徴に対してのみ計算する必要があります。

于 2012-11-21T19:24:57.630 に答える
1

最近の低ランクの行列補完方法をご覧いただければと思います。マトリックスの次元と比較して、マトリックスのランクが低いことが前提です。

min rank(M)
s.t. ||P(M-M')||_F=0

M は最終結果で、M' は現在持っている未完成の行列です。このアルゴリズムは、行列 M のランクを最小化します。制約の P は、行列 M' の既知の項を取り、M の項を M' と同じになるように制約する演算子です。

この問題の最適化には、緩和されたバージョンがあります。

min ||M||_* + \lambda*||P(M-M')||_F

rank(M) はその凸包 ||M||_* に緩和されます。次に、パラメーター lambda を制御することによって 2 つの項をトレードオフします。

于 2012-11-25T05:32:36.843 に答える