# Presentation: 083660

## Efficient Computations with Tensors and Examples from Data Mining 

- Tamara G. KoldaSandia National Laboratories*Collaborators*Brett Bader and Peter ChewSandia National Laboratories

- TexPoint fonts used in EMF.
- Read the TexPoint manual before you delete this box.: AAAAAAAA

**Notes:**
This talk considers tensors with special structure and how their structure might be exploited for efficient storage and computation. Sparse tensors have the property that the vast majority of the elements are zero. We propose storing such tensors using coordinate format and consider the computational efficiency of this scheme for mathematical operations typical of those used in tensor decomposition algorithms. Factored tensors have the property that they can be assembled from components. We consider two specific types: a Tucker tensor can be expressed as the product of a core tensor (which itself may be dense, sparse, or decomposed) and a matrix along each mode, and a Kruskal tensor can be expressed as the sum of rank-1 tensors. We are interested in the case where the storage of the components is less than the storage of the full tensor and demonstrate that many elementary operations can be computed using only the components. All of the efficiencies described in this talk are implemented in the Tensor Toolbox for MATLAB. 

## Tensor Background

## Tensor Basics: Fibers and Matricizing

- Tensor Basics: Fibers and Matricizing

- Column (Mode-1) Fibers

- Row (Mode-2)Fibers

- Tube (Mode-3)
- Fibers

*I* x J x K

_**Matricizing/Unfolding**_
**X**(n): The mode-n fibers are rearranged to be the columns of a matrix

- j

- i

- k

**Notes:**
Focusing on I x J x K 3-way tensors in this house.

## Vector Outer and Kronecker Products

- 2-Way Outer Product(I£J Rank-1 Matrix)

- 3-Way Outer Product(I£J£K Rank-1 Tensor)

- 2-Way Kronecker Product(IJ-Vector)

- 3-Way Kronecker Product(IJK-Vector)

## Matrix Kronecker &Khatri-Rao Products

- Kronecker Product(MP x NQ Matrix)

- M x N

- P x Q

- Khatri-Rao Product(MN x R Matrix)

- M x R

- N x R

- MN x R

- MN x PQ

- R x R

- Hadamard(Elementwise)Product

## Tensor Times Matrix

- Tensor Times Matrix in Mode-1

- Tensor Times Matrix in All Modes

## Primary Tensor Decompositions

## What is the higher-order analogue of the Matrix SVD?

- Two views of the matrix SVD:

- Finding bases for row and column subspaces:

- Sum of R rank-1 matrix factors (where R is the rank):

- =

- =

- +

- ++

- TuckerDecomposition

- CANDECOMP/PARAFAC

## Tucker Decomposition

- See Tucker, *Psychometrika*, 1966; see also Hitchcock, 1927.

- Also known as: three-mode factor analysis, three-mode PCA, orthogonal array decomposition
- Sizes R, S, T chosen by the user.
**A**, **B**, and **C** may be orthonormal (generally assume full column rank)
- Core is not diagonal
- Not unique

- I x J x K

**1⁄4**

**A**

- I x R

**B**

- J x S

**C**

- K x T

- R x S x T

**Core**
**Tensor**

## CANDECOMP/PARAFAC (CP)

- CANDECOMP = Canonical Decomposition
- PARAFAC = Parallel Factors
- Columns of **A**, **B**, and **C** are not orthonormal
- Exact decomposition is often unique

- Carroll & Chang, *Psychometrika*, 1970, Harshman, 1970 – plus Hitchcock, 1927.

## MATLAB Tensor Toolbox

## MATLAB has MDAs

- Multidimensional Arrays (MDAs)

*Dense Only!*
*No support for **multiplication, etc.*

- Standard Operations
- Subscripted reference and assignment
- Size queries (size, ndims, nnz)
- Permute/squeeze
- Elementwise and scalar operations (+,-,*,/,^,etc)
- Logical operations (and,or,xor,not)
- Comparisons (==,>,<,>=, <=,~=)

## Tensor Toolbox adds functionality & sparse support

- Standard Operations
- Subscripted reference and assignment
- Size queries (size, ndims, nnz)
- Permute/squeeze
- Elementwise and scalar operations (+,-,*,/,^,etc)
- Logical operations (and,or,xor,not)
- Comparisons (==,>,<,>=, <=,~=)

- Tensor-Specific Operations
- Matricize
- Tensor multiplication
- outer product, etc.
- Contraction
- Norm
- Other Tensor Operations
- Collapse/scale
- Matricized-tensor-times-Khatrio-Rao-product
- Mode-n singular vectors
- Khatri-Rao product, etc.

*For dense, sparse, and structured tensors.*
*Fully object-oriented.*

## Sparse Tensors

## Exploiting Sparsity:Sparse Tensors (sptensor)

- Exploiting Sparsity:Sparse Tensors (**sptensor**)

*Sparse *if majority of entries (xijk) are zero
- Some storage options
- Each two-dimensional slice stored as sparse matrix
- Unfold and store as sparse matrix
- Lin, Liu, Chung, IEEE Trans. Computers, 2002 & 2003
- Coordinate format

- Storage for **sptensor**
- P = # nonzeros
**vals** = P x 1 vector of nonzero values
**subs** = P x 3 matrix of subscripts

**Norm of sparse tensor**

## Sparse Storage Example

- 2 x 2 x 2 Tensor with P = 4 Nonzeros

## Tucker for Sparse

## Fitting Tucker

- Fact 1: Optimal core exists

- Fact 2: Core can be eliminated to form objective in A,B,C

- Fixing B & C, can solve this equation for A

- If B & C are completely unknown, solve:

- Assume A, B, Corthonormal

## HO-SVD (Tucker1)

- Convert tensor to MATLAB sparse matrix
- Bad: X(1) is a wide, short matrix
- Size I x JK
- Worst possible aspect ratio for MATLAB’s CSC format
- Good: U = X(1)T, which is tall and skinny
- Size JK x I
- To compute left singular vectors of X(1), calculate eigenvalues of V = UUT
- Size I x I

- Find optimal component w/o knowledge of other components:

- Need to find leading left singular vectors of X(n)

*Simplest approach; much more sophisticated methods exist.*

- De Lathauwer, De Moor, & Vandewalle, SIMAX, 2000.
- Also known as “Method 1” in Tucker, 1966.

## eigs vs. svds

- >> I = 100; J = 100; K = 100; P = 5000;
- >> U = sprand(J*K, I, P/(I*J*K));
- >> R = 10;
- >> tic; V = U'*U; [U1,D1] = eigs(V,R,'LM'); toc
- Elapsed time is **0.023073** seconds.
- >> tic; [U2,S2,V2] = svds(U,R); toc
- Elapsed time is **0.237503** seconds.

- Create 100x100x100(matricized) tensor with 5000 nonzeros.

- Calculate eigenvectorsof UTU

- Calculate singular vectorsof U

- In MATLAB, eigenvalue calculation is 10x faster than SVD.

## Computing Core Tensor is Difficult

- Final core is small
- But intermediate results are large
- Requires too much time and memory for even moderate sizes (1000 x 1000 x 1000)
- Currently researching ways to compute this efficiently...

- R x S x Tdense

- I x J x Ksparse

- R x I

- S x J

- T x K

- R x J x Kdense

## CP for Sparse

## Fitting CP

- shorthand notation for sum –corresponds to **ktensor** in theTensor Toolbox

- Successively solve least squares problems.
- Exploit structure of Khatri-Rao inverse.

- Continue until fit ceases to improve:

## CP-ALS Algorithm

- Tucker1

- Norm

- Matricized tensor times Khatri-Rao product (mttkrp)

- Inner Product

- Norm

## Matricized Tensor Times Khatri-Rao Product (mttkrp)

- Trick 1: compute solution column-wise (for r=1,...,R):

- Trick 2: Do not form unfolded tensor or Kronecker product

- Trick 3: Optimize in MATLAB by avoiding loops

- JK x Rvery big!

- I x JKsparse

*Don’t want to compute explicitly*

## Avoiding loops in mttkrp

**z = vals .* b(subs(:,2)) .* c(subs(:.3)) ****a = accumarray(z, subs(:,1))**

- 2 x 2 x 2 tensor with 4 nonzeros

- Vectors

- Storage for **sptensor**
- P = # nonzeros
**vals** = P x 1 vector of nonzero values
**subs** = P x 3 matrix of subscripts

- .*

- .*

- =

## CP-ALS Algorithm

- Tucker1

- Norm

- Matricized tensor times Khatri-Rao product (mttkrp)

- Inner Product

- Norm

## Norm of ktensor

- I x R

- J x R

- K x R

- I x J x Kdense

*Cannot form tensor explicitly because it would be too large.*

- R x R

## Inner Product: sptensor & ktensor

- write outproduct

- rearrangeterms

**sum( vals .* ar(subs(:,1)) .* br(subs(:,2)) .* cr(subs(:.3)) ) **

## Toolbox Numerical Results

## Numerical Results:Dense vs. Sparse

- Tests on 256 x 256 x 256 tensor with 32,000 nonzeros.1.66GHz Intel CoreDuo laptop with 2GB of RAM

## Numerical Results:Sparse – 500,000 nonzeros

- Tests on a 10,000 x 10,000 x 10,000 tensor with 1⁄2 million nonzeros.1.66GHz Intel CoreDuo laptop with 2GB of RAM

## Toolbox Summary

## Tensor Toolbox

- Seamless integration into MATLAB
- Object-oriented classes
- Enables storage of large-scale sparse tensors
- Most extensive library of tensor operations available
- Documentation available within MATLAB
- Over 1000 unique registered users since release in 9/06

- Areas for toolbox improvement
- Smarter memory manipulation in dense operations; avoid memory copies
- Extend to other languages (C++)
- More and better decomposition methods
- Suggestions welcome!

- http://csmr.ca.sandia.gov/~tgkolda/TensorToolbox/

## PARAFAC2 and an Application in Data Mining

## Yet another view of PARAFAC

- +...+

- =

- =

- A

- B

- Xk

- Sk

**S****k**** **= diag(**k**th _*row*_ of **C**)

- This representation only works for 3rd-order tensors.
- Looks like SVD.

## PARAFAC2

- (not, strictly speaking, a tensor decomposition)

- Not a tensor,but similar

- PARAFAC

- orthonormalcolumns

- diagonal

- used to enforceuniqueness

- R. A. Harshman, *UCLA Working Papers in Phonetics,* 1972.

## Application: Cross-Language Information Retrieval

## Latent Semantic Indexing (LSI)in Multilingual Environment

- Term-Doc Matrix

**1⁄4**

- Term-Concept Matrix

- Concept-Doc Matrix

**U**

**V****T**

****

**X**

- Low-rank SVD Approximation

- Step 1: Compute SVD on Parallel Corpus for training. Each “document” consists of _all_ its translations.

- Step 2: Map test documents to concept space. Each document is only a _single_ translation.

- all terms from all languages

- Same U for all languages.

## A Different View

- LSI Matrix (though terms are mixed)

- Stack of Matrices

## PARAFAC2 Model

- Step 1: Compute PARAFAC2 on Parallel Corpus for training. Each “document” consists of _all_ its translations.

- Step 2: Map test documents to concept space. Each document is only a _single_ translation.

- Need to know language of test document.

**Minor****Drawback**

## Results Comparison

- Trained on Bible. Tested on Quran.

- For each document in each language on the vertical axis, we ranked documents in each of the other languages. The bar represents the average rank of the correct document. Rank 1 is ideal.

- SVD
- Rank-300

- PARAFAC2
- Rank-240

- Closer to
- 1.0 is better

- Arabic (AR)

- English (EN)

- Spanish (ES)

- French (FR)

- Russian (RU)

## Other Decompositions

## Other Decompositions

**INDSCAL:** Individual Differences in Scaling (Carroll & Chang, 1972)
**PARAFAC2:** (Harshman, 1978)
**CANDELINC:** Linearly constrained CP (Carroll, Pruzansky, Kruskal, 1980)
**DEDICOM:** Decomposition into directional components (Harshman, 1972)
**PARATUCK2:** Generalization of DEDICOM (Harshman & Lundy, 1996)
**Nonnegative tensor factorizations:** (Bro and De Jung, 1997; Paatero, 1997; Welling and Weber, 2001; etc.)
**Block factorizations:** (De Lathauwer, 2007; etc.)

## Other Data Mining Applications

**Higher-Order PCA** – Tucker or CP to decompose a data stream. Useful in a variety of contexts such as chemometrics. (R. Bro, Critical Reviews in Analytical Chemistry, 2007)
**TuckerFaces and Image Analysis** – HO-SVD of image tensor. (M.A.O. Vasilescu & D. Terzopoulos, CVPR, 2003)
**Hand-Written Digit Analysis** – Classification problem. (Eldén and Savas, Pattern Recognition, 2007)
**Chatroom Analysis(*)** – Comparison of Tucker and CP to distinguish conversations in chatrooms. (Acar et al, ISI 2005 and ISI 2006)
**TOPHITS(*) **– CP of page x page x anchor text link tensor from the web graph to compute hubs, authorities, and topics. (Kolda, Bader, and Kenney, ICDM, 2005)
**Window-Based Tensor Analysis and Dynamic Tensor Analysis(*)** – Network intrusion detection. (Sun et al., ICDM 2006 and KDD 2006)
**Multi-way Clustering on Relational Graphs(*)** – Using a variety of metrics for clustering. (Banerjee, Basu, and Merugu, SDM 2007)
**Enron email analysis(*)** – Using CP and nonnegative CP. (Bader, Berry, Browne, Text Analysis Workshop at SDM 2007)
**EEG Analysis** – Detecting onset of epileptic seizure using CP and multiway PLS. (Acar et al., 2007)

## Conclusions & Future Work

- Conclusions
- Special data structures enable computations with large-scale tensors
- Applications to data mining
- Future work
- Tucker for sparse tensors (with J. Sun)
- Tensor methods for clustering (with T. Selee)
- Development of C++ tensor libraries (serial and parallel) with colleagues at Sandia
- FAQ for Einstein notation and the tensor toolbox

## References & Contact Info

- B. W. Bader and T. G. Kolda. ***Efficient MATLAB computations with sparse and factored tensors***. SIAM Journal on Scientific Computing, Volume 30, Number 1, Pages 205-231, December 2007. [_[DOI:10.1137/060676489](http://dx.doi.org/10.1137/060676489)_]
- B. W. Bader and T. G. Kolda. ***Algorithm 862: MATLAB tensor classes for fast algorithm prototyping***. ACM Transactions on Mathematical Software, Volume 32, Number 4, Pages 635-653, December 2006. [_[DOI:10.1145/1186785.1186794](http://dx.doi.org/10.1145/1186785.1186794)_]
- T. G. Kolda and B. W. Bader. ***Tensor Decompositions and Applications***. Technical Report Number SAND2007-6702, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, November 2007.
- P. A. Chew, B. W. Bader, T. G. Kolda and A. Abdelali. ***Cross-language information retrieval using PARAFAC2***. KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Pages 143-152, ACM Press, 2007. [_[DOI:10.1145/1281192.1281211](http://dx.doi.org/10.1145/1281192.1281211)_]

- Tammy Koldatgkolda@sandia.govhttp://csmr.ca.sandia.gov/~tgkolda/

- Questions?