論文読みメモ： Temporal regularized matrix factorization for high-dimensional time series prediction（その1）

以下の論文を読みます。

Hsiang-Fu Yu, Nikhil Rao, and Inderjit S Dhillon. Temporal regularized matrix factorization for high-dimensional time series prediction. In Advances in neural information processing systems, pages 847–855, 2016. https://papers.nips.cc/paper/6160-temporal-regularized-matrix-factorization-for-high-dimensional-time-series-prediction

※ キャラクターは架空のものです。解釈の誤りは筆者に帰属します。お気付きの点がありましたらご指摘ください。

前回：論文読みメモ： Think Globally, Act Locally: A Deep Neural Network Approach to High-Dimensional Time Series Forecasting（その1） - クッキーの日記

f:id:cookie-box:20200101101614p:plain:w60

前回の論文の引用文献の話が長くなりそうだったから記事をスピンアウトするね。つまり、高次元時系列予測モデルの先行研究であって、ニューラルネットを利用するものであって、グローバルなパターンも学習するものの2つ目の方ね。論文の図のまんまだけど、時系列を下図のように $Y \approx FX$ と行列分解（MF）するんだね。 $F$ の各行は $i$ 番目の商品の特徴で、 $X$ の各列はその時刻の特徴って感じだね。

f:id:cookie-box:20200216104950p:plain:w480

こんな行列分解を求めるには以下を解くんだけど、2番目の項と3番目の項は正則化項だね。 $\displaystyle \underset{F, X}{\rm min} \sum_{(i, t) \in \Omega} (Y_{it} - f_i^\top x_t)^2 + \lambda_f \mathcal{R}_f(F) + \lambda_x \mathcal{R}_x(X)$ でも通常（とは）の行列分解みたいに $\mathcal{R}_x(X) = \| X \| _F$ （ $\| \cdot \| _F$ は後で出てくるけどフロベニウスノルムだね…最初 $Y \approx FX$ の $F$ と関係ある何らかのノルムなのかと思った…）なる正則化は適切ではないといっているね。もし $Y$ がアイテム×ユーザという行列だったら、各ユーザがどのアイテムをより好きかを表現できればいいけど、いまはアイテム×時刻という行列だから、「各時刻にどのアイテムがより強い（？）」だけでは不十分で、次の時刻にその強さがどう変わるかも必要だもんね。

多変量時系列分析に行列分解を用いた先行研究ではこういう時間方向の依存性をグラフベースで取り扱ってラプラス正則化を適用しているみたいだけど、これだと2時点間の負の相関を考慮できなかったり、そもそも時間依存性が明示的に手に入っていない場合は推測しないといけなかったり、欠損値には強いものの予測は不得手だったりするって。

でも、この論文で提案する temporal regularized matrix factorization framework (TRMF) は「時間的正則化項」を導入することでデータドリブンで時間依存性を学習できて予測性能もあると。MF の特徴であるスケーラビリティと欠損値への強さはそのままに。あと先行のグラフベースアプローチとの統一的な見方も与えると。そうすることで既存のソルバーが活用できるって。

f:id:cookie-box:20200101101603p:plain:w60

MFを用いる先行手法にはかなり制約があるのですね…？本論文の2節には先行手法とその限界についてまとめてありますね。

まず、AR や DLM は計算量が時系列の本数や参照ステップ数にスケールしないと。
- L次のARモデルって $O(Ln^2)$ のパラメータの推測に $O(TL^2n^4 + L^3n^6)$ かかるんですか？
- DLMってパラメータを更新するのに $O(kn^2T + k^3 T)$ かかるんですか（ $k$ は隠れ変数の次元数でしばしば $n$ よりも大きい）？なので R の DLM で数十を超える次元数を取り扱うことはできないと。
次に、MF を用いる手法ですね。まず、グラフベースの正則化をする手法が以下ですよね。3番目の文献は5番目の文献の extended version にみえるのですがどう違うのですかね…。
ただ以下の先行手法は例外で、正則化項をカスタマイズしているということですが、これは音声認識の論文でしょうか。
- Regularized Non-negative Matrix Factorization with Temporal Dependencies for Speech Denoising (2008)
まあそれで、グラフベースの正則化とは以下のようなものであるということですね。
$\displaystyle \mathcal{R}_x(X) = \mathcal{G}(X|G, \eta) := \frac{1}{2}\sum_{t \sim s}G_{ts} \| x_t - x_s \|^2 + \frac{\eta}{2}\sum_t \|x_t\|^2$ が時刻と時刻の間の枝の重みということでしょうか。は枝があるところについての和ですね。なるほど、つまり、「結びつきが強い枝でつながっているとほど同じ値であれ」という最適化ですね。2項目はよくあるように、最適な点があることを保証するためのものっぽいですね。そして、でなければなりません。それはそうでなければ最小化が実行できませんものね…。そして、実際には相関があると信ずるタイムラグの集合、例えばなどに対して適当な時不変な重みを設定して上の最適化をするのですね。しかしそれでは、負の相関を考慮できないし、そもそも明示的に時間依存構造が必要だし、予測性能もよくないのですね。
じゃあ、時間依存構造 $w_l$ そのものもデータから学びたいということになりますよね。素朴には、以下のような最適化をしたいということになります。
$\displaystyle \underset{F, X, w \geqq 0}{\rm min} \sum_{(i, t) \in \Omega} (Y_{it} - f_i^\top x_t)^2 + \lambda_f \mathcal{R}_f(F) + \frac{\lambda_x}{2} \sum_{l \in \mathcal{L}} \sum_{t:t-l>0} w_l (x_t - x_{t-l})^2 + \frac{\lambda_x \eta}{2} \sum_t \|x_t\|^2$ しかし、これを解くと任意の $l$ に $w_l=0$ となるのは明白だと…当然ですね…。なのでこのアプローチは取れません…いったいどうすれば…。

もう少しつづく