基於流形導向之低秩張量完備化

Manifold Guided Tensor Completion under Low-rank Structure

陳以雷(Yi-Lei Chen)

指導教授 ： 許秋婷

國立清華大學/電機資訊學院/資訊工程學系/博士(2014年)

摘要

本論文擬基於張量完備化技術，解決各種實際應用中常見的資料遺失問題。現有方法假定完備化後的張量具有低秩性質，因此將預測張量中的遺失資訊轉化為復原一個低秩張量。其中，張量分解與最小化張量秩是目前最為普及的兩類技術。然而若張量中遺失資訊的比例太高，前者事先定義的低秩結構一旦不夠準確，很容易造成模型的過擬合；相較之下後者雖然可以透過最佳化方式估算張量的秩，但因為沒有考慮張量的隱含結構，通常無法有效表示模型變因。我們提出一種核心概念突破既有方法的瓶頸─「同步估測張量中遺失的資訊及其隱含的內部結構」。因此我們設計了一種可以同步對張量進行分解與完備化的方法。此方法主要貢獻有三。其一，我們結合了最小化秩的最佳化技術與基於Tucker模型的分解技術，因此不但可以利用最佳化方式自動估算張量的秩，也能同時保存張量中的隱含結構。其二，以張量結構表示的真實資料通常包含豐富的語義性，因此我們另外引入低維度流形的特性來描述張量中可觀察資訊與遺失資訊之間的隱含語義關係。由於考量了隱含結構，我們可以利用模型中變因的先驗資訊進而表示這些變因在一個聯合低維度的流形分佈。最後，考量在某些實際應用中變因的先驗資訊可能無法評估，我們對提出的演算法設計一種非監督式的擴展。此擴展的演算法僅基於對流形的的平滑性質假設，估算張量結構中變因的排序結果來恢復其隱含的平滑流形。在實驗的部分，我們首先利用合成資料驗證所提出演算法的收斂性，之後將我們的方法應用至實際問題。實驗結果顯示，在數種基於張量表示的應用中(例如多變因的資料分析以及視覺資料完備化)，我們的方法均大幅超越現今的張量完備化技術。

關鍵字

張量完備化 ； 張量分解 ； 低秩估計 ； 流形學習

並列摘要

In this dissertation, we focus on tensor completion, which is closely related to the ubiquitous missing data problem in real-world applications. Given a tensor with incomplete entries, existing methods assume the desired tensor exhibits low-rank structure. Predicting missing entries then boils down to recovering a low-rank tensor from given entries. Factorization schemes and completion schemes are two popular methodologies. As the number of missing entries increases, factorization schemes overfit the model structure due to their incorrectly predefined tensor’s rank, while completion schemes fail to interpret the model factors because they solely rely on rank minimization. Therefore, we introduce a novel concept to break the current limitations: complete the missing entries and simultaneously capture the underlying model structure. We propose a method called Simultaneous Tensor Decomposition and Completion (STDC). The major contributions are three-fold. First, we leverage rank minimization with Tucker model decomposition; i.e., we automate rank estimation while carefully maintain the latent tensor structure. Second, considering the informative semantics (named factor priors in our work) of real-world tensor objects, we discover the latent manifold with a new presented methodology, called Multilinear Graph Embedding (MGE), and study its significance in tensor completion. Finally, because factor priors are task-dependent and can be unavailable, we further propose a prior-free extension with a new presented methodology, called Permutation on Manifolds (PoM), to automate joint-manifold learning. We conducted experiments to empirically verify the convergence of our algorithm on synthetic data, and evaluate its effectiveness on various kinds of real-world data. The results demonstrate the superiority of our method and its potential usage in tensor-based applications.

並列關鍵字

tensor completion ； tensor decomposition ； low-rank approximation ； manifold learning

參考文獻

[2] Y. X. Wang and Y. J. Zhang, “Image inpainting via weighted sparse non-negative matrix factorization,” in Proc. the IEEE International Conference on Image Processing (ICIP), pp. 3409-3412, 2011.

[4] Y. Peng, A. Ganesh, J. Wright, W. Xu, and Y. Ma, “RASL: robust alignment by sparse and low-rank decomposition for linearly correlated images,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 34, no.11, pp. 2233-2246, 2012.

[6] G. Ye, D. Liu, I. H. Jhuo, and S. F. Chang, “Robust late fusion with rank minimization,” in Proc. the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3021-3028, 2012.

[7] Z. Zeng, T. H. Chan, K. Jia, and D. Xu, “Finding correspondence from multiple images via sparse and low-rank decomposition,” in Proc. the European Conference on Computer Vision (ECCV), pp. 325-339, 2012.

[8] Z. Zhang, X. Liang, and Y. Ma, “Unwrapping low-rank textures on generalized cylindrical surfaces,” in Proc. the IEEE International Conference on Computer Vision (ICCV), pp. 1347-1354, 2011.