cpals_math.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "データテンソル（3階のテンソル）を$\\mathcal{X}$で表す。\n",
    "\n",
    "CP分解は、テンソルを以下のように分解する\n",
    "\n",
    "$\\mathcal{X}_{ijk} \\simeq y_{ijk} = \\sum_r u_{ir}v_{jr}w_{kr}$\n",
    "\n",
    "ただし、$u_i$、$v_j$、$w_k$はそれぞれ$r$次元の潜在変数ベクトルである。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Loss functionをこう定義する。これを最小化する潜在変数ベクトルたちを求めたい。\n",
    "\n",
    "$L = \\frac{1}{2} \\sum_{ijk} \\left(\\mathcal{X}_{ijk} - \\sum_r u_{ir}v_{jr}w_{kr}\\right)^2$\n",
    "\n",
    "$= \\frac{1}{2} \\sum_{ijk} \\left(\\mathcal{X}_{ijk} - u_i^T(v_j \\circ w_k)\\right)^2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "まず、$v_j$、$w_k$は固定して$u_i$で微分すると\n",
    "\n",
    "$\\frac{\\partial L}{\\partial u_{i}} = - \\sum_{jk} \\left(\\mathcal{X}_{ijk} - u_i^T(v_j \\circ w_k)\\right)\\left(v_j \\circ w_k\\right)$\n",
    "\n",
    "$ = - \\sum_{jk}\\mathcal{X}_{ijk}\\left(v_j \\circ w_k\\right) + \\sum_{jk} u_i^T\\left(v_j \\circ w_k\\right)\\left(v_j \\circ w_k\\right)$\n",
    "\n",
    "$ = - \\sum_{jk}\\mathcal{X}_{ijk}\\left(v_j \\circ w_k\\right) + \\sum_{jk} \\left(v_j \\circ w_k\\right)\\left(v_j \\circ w_k\\right)^T u_i$\n",
    "\n",
    "$ = - \\sum_{jk}\\mathcal{X}_{ijk}\\left(v_j \\circ w_k\\right) + \\left(V^TV \\circ W^TW\\right) u_i$\n",
    "\n",
    "ただし、$V^T = (v_1, \\cdots, v_{N_v})$、$W^T = (w_1, \\cdots, w_{N_w})$。\n",
    "\n",
    "また、$\\circ$はHadamard積（要素積）を表す。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ここで、\n",
    "\n",
    "$\\bar{x}^{vw}_i = \\sum_{jk}\\mathcal{X}_{ijk}\\left(v_j \\circ w_k\\right)$\n",
    "\n",
    "とおくと、\n",
    "\n",
    "$\\frac{\\partial L}{\\partial u_{i}} = - \\bar{x}^{vw}_i + \\left(V^TV \\circ W^TW\\right) u_i$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\frac{\\partial L}{\\partial u_{i}} = 0$と置いて解くと、\n",
    "\n",
    "$u_i = \\left(V^TV \\circ W^TW\\right)^{-1}\\bar{x}^{vw}_i$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$U^T = (u_1, \\cdots, u_{N_u})$、$(\\bar{X}^{wv})^T = (\\bar{x}^{wv}_1, \\cdots, \\bar{x}^{wv}_{N_u})$と置いて行列で書くと、\n",
    "\n",
    "$U = \\bar{X}^{vw}\\left(V^TV \\circ W^TW\\right)^{-1}$\n",
    "\n",
    "これで$U$が求まった。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "同様に、$V$と$W$についても以下のように書ける\n",
    "\n",
    "$V = \\bar{X}^{wu}\\left(W^TW \\circ U^TU\\right)^{-1}$\n",
    "\n",
    "$W = \\bar{X}^{uv}\\left(U^TU \\circ V^TV\\right)^{-1}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "CP-ALSでは他の２つのパラメータ（V,W）を固定して、一つのパラメータ（U）を更新するということを繰り返す。\n",
    "\n",
    "まとめると、\n",
    "\n",
    "1. $t \\leftarrow 0$\n",
    "2. $U_{(0)}$, $V_{(0)}$, $W_{(0)}$を適当に初期化\n",
    "3. $U_{(t+1)} \\leftarrow \\bar{X}^{vw}\\left({V_{(t)}}^TV_{(t)} \\circ {W_{(t)}}^TW_{(t)}\\right)^{-1}$\n",
    "4. $V_{(t+1)} \\leftarrow \\bar{X}^{wu}\\left({W_{(t)}}^TW_{(t)} \\circ {U_{(t+1)}}^TU_{(t+1)}\\right)^{-1}$\n",
    "5. $W_{(t+1)} \\leftarrow \\bar{X}^{uv}\\left({U_{(t+1)}}^TU_{(t+1)} \\circ {V_{(t+1)}}^TV_{(t+1)}\\right)^{-1}$\n",
    "6. $t \\leftarrow t+1$\n",
    "7. 収束するまで3-6を繰り返す"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}