MTC: Multiresolution Tensor Completion from Partial and Coarse Observations

KDD 2021

Chaoqi Yang¹, Navjot Singh¹, Cao Xiao², Cheng Qian³, Edgar Solomonik¹, Jimeng Sun¹

¹UIUC, ²Amplitude, ³IQVIA

​

1

Outline

• Problem Setting
• Solution
• Experiment
• Conclusion

2

Partial and Coarse Data

3

?

?

?

?

?

?

?

survey data at specific locations for severe diseases at important dates

different agencies have different data accessibility

from local government

hospital

Fine-granular Tensor Completion

4

?

?

?

?

?

?

?

known

Partial observation

Coarse observations

unknown

Low-rank

recover

Outline

• Problem Setting
• Solution
• Experiment
• Conclusion

5

Background

• CP decomposition

​

• Mode product

​

6

Solution Sketch

7

The tensor is related to the observations by operations on factors

Design objective on the observations

Optimize the objective function and obtain the factors

​

Our multiresolution approach

Recover

Relations to known observations

8

Partial observation

Coarse observations

• The mask is known
• The aggregation matrix is known, is unknown

A

B

C

A

B

C

A

b

C

a

B

C

B

b

A

a

binary mask

Objective Function

9

Parameters:

Optimize the Loss

• Need a good Initialization
• Multi-resolution approach
• recursively solve low-resolution problem to initialize high-resolution parameters
• Need a good optimization algorithm
• Effective ALS-solver (for coupled decomposition)
• In each sub-iteration, we fix other factors and update one
• form joint normal equations from multiple linear equations

​

10

Fewer iterations are needed in high resolution!

Reformulate Objective

• Step1. Parameter replacement. We use ,
• Step2. Interim tensor.

11

Transform the loss function

New loss function (for k+1 iteration)

Original loss

Build Solver

• Alternating least square (ALS)
• Sub-iteration: optimize U by fixing V, W, Q1, Q2

​

​

​

​

​

• Sub-iteration: optimize V by fixing U, W, Q1, Q2
• Sub-iteration: optimize W by fixing U, V, Q1, Q2
• Sub-iteration: optimize Q1 by fixing U, V, W, Q2
• Sub-iteration: update Q2 by

12

New objective

Overall Framework

13

(1)

(2)

(3)

(4)

(5)

(6)

(7)

Subsampling and Interpolation

14

Continuous mode

Categorical mode

Continuous mode (e.g., date)

• Subsample

​

​

• Interpolate

15

Intuition: smoothness allows subsampling

Categorical mode (e.g., ICD-10)

• Subsample

​

​

​

• Interpolate
• Copy and fill

16

Intuition: dense part provides better estimation

Outline

• Problem Setting
• Solution
• Experiment
• Conclusion

17

Datasets

• IQVIA Covid-19 disease case health tensor (HT)
• Zipcode by ICD-10 by date
• ~ half a year
• Google Covid-19 symptom search (GCSS)
• Location identifier by keyword by date
• ~ a complete year 2020

​

​

​

​

​

18

Baselines and Metric

• Reference models
• CPC-ALS[1], OracleCPD
• Related baselines
• Block gradient descent (BGD)[2], B-PREMA[3], CMTF-OPT[4]
• Parameter initialization methods
• MRTL[5], TendiB[6], Higher-order singular value decomposition (HOSVD)
• Three model variants

​

​

​

19

Metric:

where

Main Comparison Results

20

• MTC outperforms baselines in tensor completion result (i.e., PoF)
• MTC outperforms baselines significantly in CPU Time

​

Compared to Reference Models

21

• OracleCPD: on the original tensor
• CPC-ALS: only on the partial observation
• MTC: on both partial and coarse observation

• OracleCPD is the upper bound of the results
• Coarse observation helps the completion task. MTC is better than CPC-ALS.

​

Comparison on Optimization Landscape

22

• MTC shows faster and better convergence over baselines

Comparison on Initialization

23

• Our multiresolution initialization technique outperforms other initialization methods

Comparison on Future Tensor Prediction

24

• MTC outperforms the baselines in tensor prediction task

Gaussian process prediction

Predicted tensor

Procedures:

Results:

Outline

• Problem Setting
• Solution
• Experiment
• Conclusion

25

Conclusion

• We formulate the fine-granular tensor completion problem from coarse and partial observations
• We propose an effective multiresolution ALS optimization framework to solve the coupled decomposition problem
• Our solution has the same asymptotical space and time complexity as applying standard CPD
• We show the effectiveness of our solution on two COVID-19 tensors, compared to multiple baselines on various aspects.

26

References

[1] Lars Karlsson, Daniel Kressner, and André Uschmajew. 2016. Parallel Algorithms for Tensor Completion in the CP Format. Parallel Comput.57, C (2016).

[2] Yangyang Xu and Wotao Yin. 2013. A block coordinate descent method for regularized multi convex optimization with applications to nonnegative tensor factorization and completion. SIAM Journal on imaging sciences6, 3 (2013).

[3] Faisal M Almutairi, Charilaos I Kanatsoulis, and Nicholas D Sidiropoulos. 2021. PREMA: principled tensor data recovery from multiple aggregated views. IEEE Journal of Selected Topics in Signal Processing(2021).

[4] Evrim Acar, Tamara G Kolda, and Daniel M Dunlavy. 2011. All-at-once optimization for coupled matrix and tensor factorizations. arXiv:1105.3422(2011).

[5] J. Park, K. Carr, S. Zheng, Y. Yue, and R. Yu. 2020. Multiresolution Tensor Learning for Efficient and Interpretable Spatial Analysis. In ICML. PMLR, 7499–7509

[6] Faisal M Almutairi, Charilaos I Kanatsoulis, and Nicholas D Sidiropoulos. 2020. Tendi: Tensor disaggregation from multiple coarse views. In PAKDD. Springer.

27

MTC: Multiresolution Tensor Completion from Partial and Coarse Observations

Thanks for Listening!

Chaoqi Yang¹, Navjot Singh¹, Cao Xiao², Cheng Qian³, Edgar Solomonik¹, Jimeng Sun¹

¹UIUC, ²Amplitude, ³IQVIA

​

28