Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Doubly Decomposing
Nonparametric Tensor Regression(ICML 2016)
M.Imaizumi (Univ. of Tokyo / JSPS DC)
K.Hayashi (AIST / JST ERATO)

2016/08/10

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

OutlineTopic
Nonparametric Regression with Tensor input
ModelY = f (X) + ✏Estimate (nonparametric) f

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Outline

MethodPropose a nonparametric model with a Bayes estimator
Improve its performance by controlling bias and variance
trade-o↵M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
ExperimentsSummaryReferences

1Tensor regression problem

2Motivation

3

Our Approach4

Convergence Analysis

5Experiments

6

Summary

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Tensor Regression Problem
Tensor data
X 2 RI1 ⇥...⇥IK
K : mode of tensor X
Ik : dim of k-th modeTensor Regressionn observations Dn = {(Xi , Yi )}ni=1
Input (tensor) : Xi 2 RI1 ⇥...⇥IK Output (scalar) : Yi 2 R
Dn is generated with a function f : RI1 ⇥...⇥IK ! R as
Yi = f (Xi ) + ✏i

for i = 1, . . . , n✏i is a Gaussian noise

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
SummaryReferences

Application of Tensor Regression Problem
Predict health conditions from medical 3D images
Xi : medical 3D image of patient i, Yi : health condition of i

Predict spread of epidemics on networks
Xi : adjacency matrix of network i, Yi : # of infected nodes

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Related researches
Tensor linear regression
Y = hW, Xi + ✏W 2 RI1 ⇥...⇥IK is a parameter tensor
Dyrholm et al. (2007); Zhou et al. (2013); Suzuki (2015);
Guhaniyogi et al. (2015),etc...

Nonparametric tensor regression
Y = f (X) + ✏f : X 7! Y is possibly nonlinear function
Zhao et al. (2014); Hou et al. (2015),etc...

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
SummaryReferences1

Tensor regression problem

2

Motivation

3

Our Approach4

Convergence Analysis

5

Experiments

6

Summary

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Motivation
Interest : Convergence of an estimator fˆn⇣⌘Ekfˆn f ⇤ k2 = O n ?
n : # of observations
fˆn : estimatorf ⇤ : target

Take the nonparametric approach to reduce bias

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence AnalysisExperiments
Summary
References

Motivation
Starting point : the (naive) nonparametric approach
min En [`(Y, f (X))] , ` : loss function
f 2F

F := f : RI1 ⇥...⇥IK ! R|f is -smooth
Let F be a hypothesis set

Problem : the curse of dimensionality
An estimator by this approach has quite slow convergence

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

The curse of dimensionality

Performance of the estimator of f gets worse with tensor input
Naive estimator f˜n⇣⌘Qkf˜n f ⇤ k2 = O n 2 /(2 + k Ik ) ,where is smoothness of f .
Qk Ik = # of elements in X

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
SummaryReferences

Why the curse exists?
The hypothesis set F is quite complex (large)
due to high dimensionality of X
Metric entropy via ✏-nets(measure complexity)

Complex hypothesis sets make variance of estimators larger

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Our idea
Reduce redundancy of hypotheses
Data and models are often redundant
Represent X and f by less complex elements

Example of reduction
1. Low-rank approx. ofmatrix
2. LASSO...

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References1

Tensor regression problem

2Motivation

3

Our Approach4

Convergence Analysis

5Experiments

6

Summary

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Double Decomposition
Outline of Double Decomposition
12Decompose input X 2 RI1 ⇥...⇥IK
Decompose function f 2 F

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Double Decomposition 1
1.Tensor (CP) Decomposition
Consider X 2 RI1 ⇥...⇥IK⇤(k),K
There exists a set of normalized vectors {xr 2 RIk }Rr,k=1,1⇤and scale term r for all r = 1, . . . , R , then⇤

X=RX
r=1⇤

(1)
(2)
(K)
r xr ⌦ xr ⌦ . . . ⌦ xr .

R is a tensor rank

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Double Decomposition 2
2.Functional Decomposition
(1)

(2)

(K)

For each r, consider a function f (xr , xr , . . . , xr)(k)
xr are Ik -dimensional vectors

There exist M ⇤ 2 Z+ [ {1} and a set of local functions⇤(k){fm }K,Mk,m=1 satisfying⇤(2)(K)f (x(1)r , xr , . . . , x r ) =M YKX(k) (k)fm(xr ).

m=1 k=1

M ⇤ is a model complexity

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Proposed Framework
Assumption
f is additive separable with respect to r = 1, . . . , R⇤

Consider doubly decomposed form of f⇤f (X) =⇤M X
RX

m=1 r=1r

KY(k) (k)fm(xr )

k=1

Additive-Multiplicative Nonparametric Regression(AMNR)(k)

Represent f (X) by fm with a low-dimensional (Ik -dim.)
vector as input
M ⇤ (model complexity) and R⇤ (tensor rank) are tuning
parameters

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
SummaryReferences

Proposed FrameworkOur approach
min En [`(Y, f (X))]
f 2Gno(k)G := f : RI1 ⇥...⇥IK ! R|f is AMNR, fm are -smooth

Expected advantage
G can be a less complex hypothesis set than F by tuning M ⇤By calculating the metric entropy

G does not increase bias a few

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
SummaryReferences

Estimation Method
The Bayes method with the Gaussian process prior.
Prior
YY(k)
⇡(f ) =GP (k) (fm),mkPosterior

Pnexp((YG[f ](Xi ))2 )Pn i=1 i⇡(f |Dn ) = R⇡(f ),exp(G[f 0 ](Xi ))2 )⇡(df 0 )
i=1 (YiM⇤ XR⇤ YK⇣⌘X(k)(k)where G[f ](Xi ) :=fm
xr,i .
m=1 r=1 k=1Implementation

The estimation bases on Gibbs sampling

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201Tensor regression problemMotivation
Our Approach
Convergence Analysis
Experiments
Summary
References1

Tensor regression problem

2

Motivation

3

Our Approach4

Convergence Analysis

5Experiments

6

Summary

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Analyze Convergence TheoreticallyIn the form of AMNR, M ⇤ controls the size of bias
As M ⇤ increases, the bias decreases

Focus on the distance between fˆn and f ⇤ with given M ⇤We start with a case then finite M ⇤ is sufficient to represent fThen, we consider M ⇤ is larger (infinite)

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Finite M ⇤ CaseIn the following, we assume that(k)i True fm belongs to Sobolev space with orderii Parameters of the prior estimation is appropriately selectedTheorem 1
Let M ⇤ < 1. Then, with some finite constant C > 0,Ekfˆnf ⇤ k2n  Cn 2 /(2 +maxk Ik ) .

Remind that the naive nonparametricestimator f˜n has aQ2/(2+I)
k k
convergence rate n

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
SummaryReferences

Infinite M ⇤ CaseWith infinite M ⇤ , we estimate first M components with someassumption.
Theorem 2Assume that with some constant
1,PQ (k)1=o m, as m ! 1. Suppose wer rk fm
2
construct the estimator with a proximal complexity M such thatM ⇣ (n2 /(2 +maxk Ik ) )1/(1+ ) .
Then, with some finite constant C > 0,Ekfˆnf ⇤ k2n  C(n 2 /(2 +maxk Ik ) ) /(1+ ) .

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
SummaryReferences

Convergence Rate
Compare Nomparametric method for Tensor Regression
For example case, we set K = 3, Ik = 100,Method
Naive=Convergence Raten 2 /(2 +Qk Ik )=2Example
n 1/2501

AMNR (Finite M ⇤ )n 2 /(2 +maxk Ik )n 1/26AMNR (Infinite M ⇤ )(n 2 /(2 +maxk Ik ) ) /(1+ )n 1/39AMNR achieves better convergence rate, by reducing the sizeof the model space by the double decomposition

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

1Tensor regression problem

2Motivation

3

Our Approach4

Convergence Analysis

5Experiments

6

Summary

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Experiment Outline
We introduce 3 experiments
1 Prediction performance
2 Convergence analysis
3 Real data analysisMethods
AMNR (our method)TGP (Tensor Gaussian Process)
Close to the naive nonparametric estimator

TLR (Tensor Linear Regression)
Not nonparametric method

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Prediction Performance
Generate synthetic data with low rank tensor asPQT x(k) )) 1f (X) = 2r=1 r Kr
k=1 (1 + exp(–Full view2.5Enlarged view
0.20
0.18

2.00.16MSEMSE

1.5
1.0

0.14
0.12
0.10

0.5

0.08

0.0

0.06
−0.5

100200300

n400500

0.04

100200300

400500nM.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
SummaryReferences

Convergence analysis
GenerateP
synthetic
data with smoothness-controlled process
R QK Pf (X) = r=1 k=1 l µl l ( T x)
Asymmetric tensor

log MSElog MSE

Symmetric tensor

TGP(10*10*10)
AMNR(10*10*10)
4.0

4.5

5.0

log n

5.5

TGP(10*3*3)
AMNR(10*3*3)
6.0

4.0

4.5

5.0

5.5

6.0

log n

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
SummaryReferences

Real Data Analysis
Epidemic Spreading Data
Xi : Adjacency matrix of network i
Yi : the number of total infected nodes of network i

Testing MSE7060MSE50403020100050100150200nM.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

1Tensor regression problem

2Motivation

3

Our Approach4

Convergence Analysis

5

Experiments

6

Summary

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our ApproachConvergence Analysis
Experiments
Summary
References

Conclusion

Summary
Proposed nonparametric regression model with tensor input
Doubly decomposition controls the hypothesis complexity
The control reduces the variance of the estimator

Future work
Computational complexity / convergence
Tuning parameters ( , ) selection
Measure bias size

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Reference I
Dyrholm, M., Christoforou, C., and Parra, L. C. (2007). Bilinear
discriminant component analysis. The Journal of Machine
Learning Research, 8:1097–1111.
Guhaniyogi, R., Qamar, S., and Dunson, D. B. (2015). Bayesiantensor regression. arXiv preprint arXiv:1509.06490.
Hou, M., Wang, Y., and Chaib-draa, B. (2015). Online local
gaussian process for tensor-variate regression: Application tofast reconstruction of limb movement from brain signal. In IEEE
International Conference on Acoustics, Speech and Signal
Processing.

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
Summary
References

Reference II
Kolda, T. G. and Bader, B. W. (2009). Tensor decompositions andapplications. SIAM review, 51(3):455–500.
Prettejohn, B. J., Berryman, M. J., and McDonnell, M. D. (2011).
Methods for generating complex networks with selectedstructural properties for simulations: a review and tutorial forneuroscientists. Frontiers in computational neuroscience, 5:11.
Suzuki, T. (2015). Convergence rate of bayesian tensor estimatorand its minimax optimality. In Proceedings of The 32nd
International Conference on Machine Learning, pages
1273–1282.

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201

Tensor regression problem
Motivation
Our Approach
Convergence Analysis
Experiments
SummaryReferences

Reference III

Zhao, Q., Zhou, G., Zhang, L., and Cichocki, A. (2014).
Tensor-variate gaussian processes regression and its application
to video surveillance. In Acoustics, Speech and Signal
Processing, 2014 IEEE International Conference, pages1265–1269. IEEE.
Zhou, H., Li, L., and Zhu, H. (2013). Tensor regression withapplications in neuroimaging data analysis. Journal of theAmerican Statistical Association, 108(502):540–552.

M.Imaizumi (Univ. of Tokyo / JSPS DC) K.Hayashi (AIST / JST ERATO)
Doubly Decomposing Nonparametric Tensor Regression(ICML 201