{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Online Low-Rank Tensor Learning (Online-LRTL)\n", "\n", "This notebook shows how to implement the following paper:\n", "\n", "
\n", "\n", "Rose Yu, Dehua Cheng, Yan Liu (2015). Accelerated Online Low-Rank Tensor Learning for Multivariate Spatio-Temporal Streams. ICML 2015. [PDF] \n", "\n", "
\n", "\n", "The authors provide Matlab code, if you have any interest, please download at [http://roseyu.com/Materials/accelerate_online_low_rank_tensor.zip](http://roseyu.com/Materials/accelerate_online_low_rank_tensor.zip)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Necessarity" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "\n", "def ten2mat(tensor, mode):\n", " return np.reshape(np.moveaxis(tensor, mode, 0), (tensor.shape[mode], -1), order = 'F')\n", "\n", "def mat2ten(mat, dim, mode):\n", " index = list()\n", " index.append(mode)\n", " for i in range(dim.shape[0]):\n", " if i != mode:\n", " index.append(i)\n", " return np.moveaxis(np.reshape(mat, list(dim[index]), order = 'F'), 0, mode)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Kernel" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**1) How to initialize paramters?**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def mapTensorKInit(W, nRank):\n", " dim = W.shape\n", " U = []\n", " for i in range(len(dim)):\n", " u, _, _ = np.linalg.svds(ten2mat(W, i), min(nRank, dim[i]))\n", " U.append(u)\n", " if nRank ~= dim[0]:\n", " W = np.einsum('pqm, pr, qs, mt -> rst', W, U[0], U[1], U[2])\n", " W = np.einsum('rst, pr, qs, mt -> pqm', W, U[0], U[1], U[2])\n", " return W, U\n", "\n", "def solve_init(X, Y, nRank):\n", " \"\"\"Get the initial estimation from the first batch.\"\"\"\n", " P, _ = Y[0].shape\n", " Q, M = X[0].shape\n", " nSample = len(Y)\n", " \n", " W_mat = []\n", " W_mat.append(np.zeros((P, Q * M)))\n", " W_mat.append(np.zeros((Q, P * M)))\n", " W_mat.append(np.zeros((M, P * Q)))\n", " \n", " Sigma_X = np.zeros((Q, Q, M))\n", " Sigma_Y = np.zeros((P, Q, M))\n", " \n", " for m in range(M):\n", " X_m = np.zeros((Q, nSample))\n", " Y_m = np.zeros((P, nSample))\n", " for n in range(nSample):\n", " X_m[:, n] = X[n][:, m]\n", " Y_m[:, n] = Y[n][:, m]\n", " S_X = np.linalg.inv(X_m @ X_m.T + 1e-5 * np.eye(Q)) # Q x Q\n", " S_Y = Y_m @ X_m.T # P x Q\n", " W_est = S_Y @ S_X # P x Q\n", " \n", " W_mat[0][:, (m - 1) * Q : m * Q] = W_est # P x MQ\n", " W_mat[1][:, (m - 1) * P : m * P] = W_est.T # Q x MP\n", " W_mat[2][m, :] = W_est.T.reshape(P * Q) # M x PQ\n", " Sigma_X[:, :, m] = S_X\n", " Sigma_Y[:, :, m] = S_Y\n", " W = mat2ten(W_mat[0], np.array([P, Q, M]), 0) # P x Q x M\n", " \n", " W, U = mapTensorKInit(W, nRank, [1, 2, 3])\n", " W = W.data\n", " D_L = U\n", " D_R = 0\n", " \n", " return W, Sigma_X, Sigma_Y, D_L, D_R" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**2) How to update parameters?**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def mapTensorKGreedy(W, nRank):\n", " dim = W.shape\n", " U = []\n", " W0 = np.zeros(dim)\n", " for i in range(len(dim)):\n", " u, s, v = np.linalg.svds(ten2mat(T, i), min(nRank, dim[i]))\n", " U.append(u)\n", " W0 += mat2ten(u @ np.diag(s) @ v.T, np.array(dim), i)\n", " W = W0 / 3\n", " return W, U\n", "\n", "def ALTO(W, U):\n", " D_L = []\n", " dim = W.shape\n", " nRank = U[0].shape[1]\n", " for i in range(len(dim)):\n", " tmp = np.random.randn(U[i].shape)\n", " tmp = tmp - U[i] @ U[i].T @ tmp\n", " tmp = tmp / np.linalg.norm(tmp)\n", " D_L.append(np.append(U[i], tmp.reshape([dim[i], 1]), axis = 1))\n", " T = np.einsum('pqm, pr, qs, mt -> rst', W, D_L[0], D_L[1], D_L[2]) # R+1 x R+1 x R+1\n", " T, U = mapTensorKGreedy(T, nRank)\n", " W_out = np.einsum('rst, pr, qs, mt -> pqm', T, D_L[0], D_L[1], D_L[2])\n", " for i in range(len(dim)):\n", " D_L[i] = D_L[i] @ U[i]\n", " return W_out, D_L\n", "\n", "def solve_update(W, X, Y, Sigma_X, Sigma_Y, D_L, D_R, nRank, nIter):\n", " nSample = len(Y)\n", " Q, _ = X[0].shape\n", " P, M = Y[0].shape\n", " \n", " Sigma_X_out = np.zeros((Q, Q, M))\n", " Sigma_Y_out = np.zeros((P, Q, M))\n", " Delta = np.zeros((P, Q, M))\n", " \n", " for m in range(M): # solve for each variable seperately\n", " X_m = np.zeros((Q, nSample))\n", " Y_m = np.zeros((P, nSample))\n", " for n in range(nSample):\n", " X_m[:, n] = X[n][:, m]\n", " Y_m[:, n] = Y[n][:, m]\n", " # update Sigma_X and Sigma_Y\n", " B = Sigma_X[:, :, m] @ X_m # Q x nSample\n", " E = B @ np.linalg.lstsq(np.eye(nSample) + X_m.T @ B, B.T)[0]\n", " Delta[:, :, m] = 1 / nIter @ (Y_m @ B.T - Simga_Y[:, :, m] @ E\n", " - Y_m @ X_m.T @ E + Sigma_Y[:, :, m] @ Sigma_X[:, :, m])\n", " Sigma_X_out[:, :, m] = Sigma_X[:, :, m] - E\n", " Sigma_Y_out[:, :, m] = Sigma_Y[:, :, m] + Y_m @ X_m.T\n", " \n", " W_out, D_L = ALTO(nIter * Delta, D_L)\n", " \n", " return W_out, Sigma_X_out, Sigma_Y_out, D_L, D_R" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**3) How to build the kernel online low-rank tensor learning?**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def online_tensor_learning(X, Y, At, nInit, batch_size, nRank):\n", " \"\"\"\n", " Main routine for Online Low-Rank Tensor Learning (Online_LRTL)\n", " Refer to \"Accelerated Online Low-Rank Tensor Learning for Multivariate Spatio-Temporal Streams\"\n", " Rose Yu, Dehua Cheng, Yan Liu (ICML 2015)\n", " Input:\n", " - X: predictor, list of length 1 x T, each of size Q x M (array)\n", " - Y: response, list of length 1 x T, each of size P x M (array)\n", " - At:\n", " - if matrix, Laplacian matrix\n", " - if tensor: ground truth tensor, for synthetic evaluation\n", " - nInit: size of the initial batch\n", " - batch_size: size of mini-batch\n", " - nRank: upper bound of the rank\n", " Output:\n", " - W: model tensor: P x Q x M\n", " - obj: objective function value\n", " \"\"\"\n", " \n", " nSample = len(X)\n", " nBatch = int((nSample - nInit) / batch_size)\n", " objs = np.zeros(nBatch)\n", " \n", " W, Sigma_X, Sigma_Y, D_L, D_R = solve_init(X[:nInit], Y[:nInit], nRank)\n", " \n", " for nIter in range(nBatch):\n", " if nIter == nBatch:\n", " X_new = X[nInit + (nBatch - 1) * batch_size - 1 :]\n", " Y_new = Y[nInit + (nBatch - 1) * batch_size - 1 :]\n", " else:\n", " X_new = X[nInit + (nIter - 1) * batch_size - 1 : nIter * batch_size - 1]\n", " Y_new = Y[nInit + (nIter - 1) * batch_size - 1 : nIter * batch_size - 1]\n", " W, Sigma_X, Sigma_Y, D_L, D_R = solve_update(W, X_new, Y_new, Sigma_X, Sigma_Y, D_L, D_R, nRank, nIter)\n", " if len(At.shape) == 3:\n", " objs[nIter] = np.linalg.norm(W - At) / np.linalg.norm(At)\n", " else:\n", " X_test = X[nInit + nIter * batch_size - 1 :]\n", " Y_test = Y[nInit + nIter * batch_size - 1 :]\n", " tmp = 0\n", " for s in range(nSample):\n", " for m in range(M):\n", " tmp += np.linalg.norm(Y_test[s][:, m] - W[:, :, m] @ X_test[s][:, m]) ** 2\n", " objs[nIter] = np.sqrt(tmp / (nSample * P * M))\n", " print('Batch: {}'.format(nIter))\n", " print('Objective function: {:.6}'.format(objs[nIter]))\n", " print()\n", " \n", " return W, objs" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "I have no idea for providing simple example currently, but I will try my best to give some!" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.3" } }, "nbformat": 4, "nbformat_minor": 2 }