Matrix Factorizationで遊ぶ

機械学習 プログラミング

はじめに

次元削減せずにはいられない。
0の扱いがいまいちピンとこなかったので、ちょっと調べて試してみた。

Matrix Factorizationとは

  • Netflix Prizeという推薦システム・協調フィルタリングのコンテストで良い結果を残した手法
  • 行列Mを、2つの行列P,Qの掛け算で近似するもの
    • 行列Mが与えられたとき、行列Pと行列Qをそれぞれ見つける
    • ユーザー数m、アイテム数nとして、Mはm*n行列。Pはm*k行列。Qはn*k行列。
    • 行列Mには欠損データが含まれている
  • 行列PとQを求めるために次式を最小化する
  • min Σ_{(u,i)∈κ} (M[u][i] - Q_vec[i]*P_vec[u])^2 + λ(|Q_vec[i]|^2 + |P_vec[u]|^2)
    • κは、既知のM[u][i]が存在する(u,i)のペアの集合
  • SGDで解を探す場合は以下の反復式になる
  • e_ui := M[u][i] - Q_vec[i]*P_vec[u]
  • Q_vec[i] ← Q_vec[i] + γ*(e_ui * P_vec[u] - λ*Q_vec[i])
  • P_vec[u] ← P_vec[u] + γ*(e_ui * Q_vec[i] - λ*P_vec[u])

コード

欠損データは0として、学習時には無視する。

#include <iostream>
#include <vector>
#include <cmath>

//xorshift
// 注意: longではなくint(32bit)にすべき
unsigned long xor128(){
  static unsigned long x=123456789, y=362436069, z=521288629, w=88675123;
  unsigned long t;
  t=(x^(x<<11));
  x=y; y=z; z=w;
  return w=(w^(w>>19))^(t^(t>>8));
}
//[0,1)の一様乱数
double frand(){
  return xor128()%10000000000/static_cast<double>(10000000000); 
}


//Matrix Factorization
class MF {
  std::vector< std::vector<double> > P, Q;
  int m, n, k;

public:
  MF(int m, int n, int k):
    P(m, std::vector<double>(k, 0)),
    Q(n, std::vector<double>(k, 0)),
    m(m), n(n), k(k)
  {
    for(int u=0; u<m; u++){
      for(int j=0; j<k; j++){
        P[u][j] = frand();
      }
    }
    for(int i=0; i<n; i++){
      for(int j=0; j<k; j++){
        Q[i][j] = frand();
      }
    }
  }

  void calc(const std::vector< std::vector<double> >& r, int ITER = 100000, double gamma = 0.0002, double lambda = 0.02){
    std::vector<double> tmp_p(k), tmp_q(k);

    for(int itr=0; itr<ITER; itr++){
      double e_sum = 0.0;
      for(int u=0; u<m; u++){
        for(int i=0; i<n; i++){
          if(r[u][i] > 0){
            double e = r[u][i];
            for(int j=0; j<k; j++){
              e -= P[u][j] * Q[i][j];
              tmp_q[j] = Q[i][j];
              tmp_p[j] = P[u][j];
            }
            
            e_sum += fabs(e);
            
            for(int j=0; j<k; j++){
              tmp_q[j] += gamma * (e * P[u][j] - lambda * Q[i][j]);
              tmp_p[j] += gamma * (e * Q[i][j] - lambda * P[u][j]);
            }
            
            for(int j=0; j<k; j++){
              Q[i][j] = tmp_q[j];
              P[u][j] = tmp_p[j];
            }
          }
        }
      }
      std::cout << "err : " << e_sum << std::endl;
    }
  }

  double getQP(int u, int i){
    double ret = 0.0;
    for(int j=0; j<k; j++){
      ret += P[u][j] * Q[i][j];
    }
    return ret;
  }
};


int main(){
  int m, n, k;

  std::cin >> m >> n >> k;

  MF mf(m, n, k);
  std::vector< std::vector<double> > mat(m, std::vector<double>(n));

  for(int i=0; i<m; i++){
    for(int j=0; j<n; j++){
      std::cin >> mat[i][j];//欠損データは0(以下)にしておく
    }
  }

  mf.calc(mat);

  for(int i=0; i<m; i++){
    for(int j=0; j<n; j++){
      //推定値[実際の値]
      std::cout << mf.getQP(i, j) << "[" << mat[i][j] << "] ";
    }
    std::cout << std::endl;
  }

  return 0;
}

結果

以下のパターンを試す。

  • 入力
    • m,n,kと行列の要素
5 4 2
5 3 0 1
4 0 0 1
1 1 0 5
1 0 0 4
0 1 5 4
  • 結果
4.95413[5] 2.96558[3] 4.763[0] 1.0043[1] 
3.96507[4] 2.38903[0] 4.01191[0] 1.00021[1] 
1.00855[1] 0.977924[1] 5.78876[0] 4.94156[5] 
0.995749[1] 0.893576[0] 4.78884[0] 3.96817[4] 
1.21817[0] 1.02418[1] 4.97002[5] 3.98115[4]

既知のデータに対しては近似値、欠損値に対しては推定値がちゃんと入っているのでよさそう。
欠損データも学習したら0に近い値でるんじゃないのかと思ってたけど、観測データのみ(欠損データは使わない)でモデル作るらしいですね。


mを文章、nを形態素の有無として、動詞と格助詞の関係性とか名詞の共起関係とか取り出せたら面白そうと思ったけど、いろいろ無理がある・・・

参考