[Julia] 行列分解を書いてみる(関係データ学習 その3)


前回からの引き続きです: 行列分解を書いてみる(関係データ学習その2)
レポジトリも作っています: Bitbucket/MatrixDecompositionJulia

数値的な挙動がいまいち安定しない問題を,会社の先輩に聞いて検証してきました(プログラムを書いてもらいました).

結論

  • 1次の手法は,やはり発散することが多い(誤算がInfに飛ぶ)
    • 小さいデータをサブサンプリングしてやってみると,動く
    • 欠損値の扱いに問題があるのかもしれない(MovieLenzを使っている)
  • 2次の手法を実装すると,そこそこ動く

実装を見てみます

1次の手法(発散しない程度)

  • データを前回使っていたMovieLenz-1mから100Kに変更
  • 前回の反省を活かして,入力のうち一部だけを使用して行列分解をやってみる
using DataFrames
using PyPlot
using JLD

data_file = "./data/u.data"
df = readtable(data_file, separator='\t')
max_user = maximum(df[:, 1])
max_num = maximum(df[:, 2])
X = zeros(max_user, max_num)
for iter=1:size(df)[1]
  X[df[iter,1], df[iter,2]] = df[iter,3]
end

# 小さい行列にする
original_X = copy(X)
X = X[1:100, 1:100]

# 最適化
N, M = size(X)
η = 0.001 # learning parameter
λ = 0.001 # regularization constant
K = 10
ϵ = 1e-5
U = rand(N, K)
V = rand(M, K)

# Error
function fl2(X, U, V, λ)
  N, M = size(X)
  ret = 0.5 * (sum(X - U*V') .^ 2)

  # regularization term
  value = 0.5 * λ * (sum(U .^2) + sum(V .^ 2))
  ret += λ * 0.5 * value
  return ret
end

# 微分
∇u(U, V) = -X * V + U * (V' * V + λ .* eye(K))
∇v(U, V) = -X' * U + V * (U' * U + λ .* eye(K))

# update until convergence ?
n_iter = 1
errors = []
while true
  g = fl2(X, U, V, λ)
  # println("Fro $(Fro(U))")
  U -= η .* ∇u(U, V)
  V -= η .* ∇v(U, V)
  gg = fl2(X, U, V, λ)
  push!(errors, gg)
  println("$n_iter $g -> $gg")
  if abs(g - gg) / gg < ϵ
    break
  end
  n_iter += 1
end
Xsim = U * V'

figure(figsize=(12, 6))
subplot(121)
imshow(X, interpolation="nearest", cmap="Blues")
subplot(122)
imshow(Xsim, interpolation="nearest", cmap="Blues")
savefig("output/compare_1st.png", format="png", dpi=300)

figure(figsize=(6,4))
plot(errors)
yscale("log")
savefig("output/errors_1st.png")
  • 出力を見てみます(学習率0.002,正則化重み0.001)
    • 行列分解ができているように見えます
    • エラーの履歴は若干あやしいです(これが大きいデータを扱ったときに死ぬ原因の一つ?)

元データと近似データ

誤差数値の推移

2次の手法

  • 疑似2次交互勾配降下法の更新式は次のようになります.
    • \( U \leftarrow (1-\eta) U + \eta XV(V^T V + \lambda I)^{-1} \)
    • \( V \leftarrow (1-\eta) V + \eta X^T U(U^T U + \lambda I)^{-1} \)
    • 本のアルゴリズム4.2です.

実装は更新部分が少しだけ変わります.

while true
  g = fl2(X, U, V, λ)
  U = (1-η) * U + η * X * V * inv(V' * V + λ * eye(K))
  V = (1-η) * V + η * X' * U * inv(U' * U + λ * eye(K))
  gg = fl2(X, U, V, λ)
  push!(errors, gg)
  println("$n_iter $g -> $gg")
  if abs(g - gg) / gg < ϵ
    break
  end
  n_iter += 1
end
  • 出力を見てみます(学習率0.01,正則化重み0.01)
    • 値を結構変えて試してみました(このあたりが難しくてよく分からない!)

元データと近似データ

誤差数値の推移

  • そこそこな挙動に見えます.

続く?

  • たぶん続きます