3. Tensor Decomposition

In this section, we will show how to perform tensor decomposition. Refer to [1] [2] for more mathematical details.

In the following subsections, we present examples of four basic decomposition and pairwise interaction tensor decomposition, and the data flow graph generated by using TensorBoard, which is a visual tool offered by TensorFlow. We also provide example for multiple decompositions in one script.

Before using each decomposition model, import Enviroment and Provider for decomposition model, and DataGenerator for synthetic tensor generation:

from tensorD.factorization.env import Environment
from tensorD.dataproc.provider import Provider
from tensorD.demo.DataGenerator import *

3.1. The Tucker decomposition

\[\chi = g \times_1 \mathbf{U}\times_2 \mathbf{V}\times_3 \mathbf{W}=\sum_r \sum_s \sum_t g_{rst}\,\mathbf{u}_r \circ \mathbf{v}_s\circ \mathbf{w}_t\equiv \left [ g;\mathbf{U},\mathbf{V},\mathbf{W} \right ]\]
_images/tucker-HOOI.png 
# generate a random tensor with shape 20x20x20
X = synthetic_data_tucker([20, 20, 20], [10, 10, 10])
data_provider = Provider()
data_provider.full_tensor = lambda: X

# HOSVD
from tensorD.factorization.tucker import HOSVD
env = Environment(data_provider, summary_path='/tmp/hosvd_' + '20')
hosvd = HOSVD(env)
args = HOSVD.HOSVD_Args(ranks=[10, 10, 10], validation_internal=1, tol=1.0e-4)
hosvd.build_model(args)
hosvd.train()
# obtain factor matrices from trained model
factor_matrices = hosvd.factors
# obtain core tensor from trained model
core_tensor = hosvd.core

# HOOI
from tensorD.factorization.tucker import HOOI
env = Environment(data_provider, summary_path='/tmp/hooi_' + '20')
hooi = HOOI(env)
args = HOOI.HOOI_Args(ranks=[10, 10, 10], validation_internal=1, tol=1.0e-4)
# build HOOI model
hooi.build_model(args)
# train HOOI model with the maximum iteration of 100
hooi.train(100)
# obtain factor matrices from trained model
factor_matrices = hooi.factors
# obtain core tensor from trained model
core_tensor = hooi.core

3.2. The CANDECOMP/PARAFAC (CP) decomposition

\[\mathcal{X} = \sum_{r}\lambda_{r} \mathbf{u}_{r}\circ \mathbf{v}_{r}\circ \mathbf{w}_{r}\equiv \left [\lambda;\mathbf{U},\mathbf{V},{\mathbf{W}}\right]\]
_images/cp.png 
from tensorD.factorization.cp import CP_ALS
# generate a random tensor with shape 20x20x20
X = synthetic_data_cp([20, 20, 20], 10)
data_provider = Provider()
data_provider.full_tensor = lambda: X
env = Environment(data_provider, summary_path='/tmp/cp_' + '20')
cp = CP_ALS(env)
args = CP_ALS.CP_Args(rank=10, validation_internal=1)
# build CP model with arguments
cp.build_model(args)
# train CP model with the maximum iteration of 100
cp.train(100)
# obtain factor matrices from trained model
factor_matrices = cp.factors
# obtain scaling vector from trained model
lambdas = cp.lambdas

3.3. The non-negative CANDECOMP/PARAFAC (NCP) decomposition

_images/ncp.png 
from tensorD.factorization.ncp import NCP_BCU
# generate a random tensor with shape 20x20x20
X = synthetic_data_cp([20, 20, 20], 10)
data_provider = Provider()
data_provider.full_tensor = lambda: X
env = Environment(data_provider, summary_path='/tmp/ncp_' + '20')
ncp = NCP_BCU(env)
args = NCP_BCU.NCP_Args(rank=10, validation_internal=1)
# build NCP model
ncp.build_model(args)
# train NCP model with the maximum iteration of 100
ncp.train(100)
# obtain factor matrices from trained model
factor_matrices = ncp.factors
# obtain scaling vector from trained model
lambdas = ncp.lambdas

3.4. The non-negative Tucker (NTucker) decomposition

_images/ntucker_core-update.png _images/ntucker_factor-update.png 
from tensorD.factorization.ntucker import NTUCKER_BCU
# generate a random tensor with shape 20x20x20
X = synthetic_data_tucker([20, 20, 20], [10, 10, 10])
data_provider = Provider()
data_provider.full_tensor = lambda: X
env = Environment(data_provider, summary_path='/tmp/ntucker_demo_' + '30')
ntucker = NTUCKER_BCU(env)
args = NTUCKER_BCU.NTUCKER_Args(ranks=[10, 10, 10], validation_internal=1)
# build NTucker model
ntucker.build_model(args)
# train NCP model with the maximum iteration of 500
ntucker.train(500)
# obtain factor matrices from trained model
factor_matrices = ntucker.factors
# obtain core tensor from trained model
core_tensor = ntucker.core

3.5. The example: Pairwise Interaction Tensor Decomposition

Formally, pairwise interaction tensor assumes that each entry \(T_{ijk}\) of a tensor \(\mathcal{T}\) of size \(n_1 \times n_2\times n_3\) is given by following:

\[T_{ijk}=\left \langle \mathbf{u}_{i}^{\left ( a \right )},\mathbf{v}_{j}^{\left ( a \right )} \right \rangle+\left \langle \mathbf{u}_{j}^{\left ( b \right )},\mathbf{v}_{k}^{\left ( b \right )} \right \rangle+\left \langle \mathbf{u}_{k}^{\left ( c \right )},\mathbf{v}_{i}^{\left ( c \right )} \right \rangle,\mathrm{for\,all}\left ( i,j,k \right )\in \left [ n_1 \right ]\times \left [ n_2 \right ] \times \left [ n_3 \right ]\]

The pairwise vectors in this formula are \(r_1, r_2, r_3\) dimensions:

\[ \begin{align}\begin{aligned}\left \{ \mathbf{u}_i^{\left \{a \right \}} \right \}_{i\in \left [ n_1 \right ]} , \left \{ \mathbf{v}_j^{\left \{a \right \}} \right \}_{j\in \left [ n_2 \right ]}\\\left \{ \mathbf{u}_j^{\left \{b \right \}} \right \}_{j\in \left [ n_2 \right ]} , \left \{ \mathbf{v}_k^{\left \{b \right \}} \right \}_{k\in \left [ n_3 \right ]}\\\left \{ \mathbf{u}_k^{\left \{c \right \}} \right \}_{k\in \left [ n_3 \right ]} , \left \{ \mathbf{v}_i^{\left \{c \right \}} \right \}_{i\in \left [ n_1 \right ]}\end{aligned}\end{align} \]
from tensorD.factorization.pitf_numpy import PITF_np
X = synthetic_data_tucker([20, 20, 20], [10, 10, 10])
data_provider = Provider()
data_provider.full_tensor = lambda: X
pitf_np_env = Environment(data_provider, summary_path='/tmp/pitf')
pitf_np = PITF_np(pitf_np_env)
sess_t = pitf_np_env.sess
init_op = tf.global_variables_initializer()
sess_t.run(init_op)
tensor = pitf_np_env.full_data().eval(session=sess_t)
args = PITF_np.PITF_np_Args(rank=5, delt=0.8, tao=12, sample_num=100, validation_internal=1, verbose=False, steps=500)
y, X_t, Y_t, Z_t, Ef_t, If_t, Rf_t = pitf_np.exact_recovery(args, tensor)
y = tf.convert_to_tensor(y)
X = tf.convert_to_tensor(X_t)
Y = tf.convert_to_tensor(Y_t)
Z = tf.convert_to_tensor(Z_t)
Ef = tf.convert_to_tensor(Ef_t)
If = tf.convert_to_tensor(If_t)
Rf = tf.convert_to_tensor(Rf_t)

Specific details can refer to the paper “Exact and Stable Recovery of Pairwise Interaction Tensors, NIPS 2013” [3] .

3.6. Multiple decompositions

To perform multiple decompositions or one decomposition algorithm on several different tensors, we can use tf.Graph() to build several graphs and perform decompositions on different graphs. Take performing HOOI decomposition on 3 tensors as example:

for i in range(3):
    g1 = tf.Graph()
    data_provider = Provider()
    X = np.arange(60).reshape(3, 4, 5) + i
    data_provider.full_tensor = lambda: X
    hooi_env = Environment(data_provider, summary_path='/tmp/tensord')
    hooi = HOOI(hooi_env)
    args = hooi.HOOI_Args(ranks=[2, 2, 2], validation_internal=5)
    with g1.as_default() as g:
        hooi.build_model(args)
        hooi.train(100)
    print(np.sum(hooi.full - X))
    tf.reset_default_graph()

3.7. Tips

The test files include in the project.

The images shown above can clearly see the decomposition process and relationship between each step in decomposition algorithm.

3.8. References

[1]Tamara G. Kolda and Brett W. Bader, Tensor Decompositions and Applications, SIAM REVIEW, vol. 51, n. 3, pp. 455-500, 2009.
[2]Y. Xu, W. Yin, A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion, SIAM J. Imaging Sci. 6 (3) (2013) 1758–1789.
[3]Chen, S., Lyu, M. R., King, I., & Xu, Z. (2013). Exact and stable recovery of pairwise interaction tensors. In Advances in Neural Information Processing Systems (pp. 1691-1699).