Low-rank tensor decompositions in Kernel-based machine learning

Abstract

An increasing amount of collected data are high-dimensional multi-way arrays (tensors), and it is crucial for efficient learning algorithms to exploit this tensorial structure as much as possible. The ever present curse of dimensionality for high dimensional data and the loss of structure when vectorizing the data motivates the use of tailored low-rank tensor classi cation methods. In the presence of small amounts of training data, kernel methods o er an attractive choice as they provide the possibility for a nonlinear decision boundary. This thesis focuses on developing low-rank decomposition based kernel methods. One of the rst proposed approach is the Tensor Train Multi-way Multi-level Kernel (TT-MMK), which combines the simplicity of the Canonical Polyadic (CP) decomposition, the classi cation power of the Dual Structure-preserving Support Vector Machine (SVM), and the reliability of the Tensor Train (TT) approximation. This proposed algorithm is based-on computing a CP decomposition by avoiding the NP-hard issue of nding the best CP rank by computing rst a TT decomposition and call it TT- CP factorization. Along with the experiments it is shown that the TT-MMK method is usually more reliable computationally, less sensitive to tuning parameters, and gives higher prediction accuracy in the SVM classi cation when benchmarked against other state-of-the-art techniques. Additionally, the classi cation model that includes low-rank tensor decomposition as a crucial initial step reduces the computational complexity and extracts informative features. However, what decisive features of the tensors are exploited by these kernels is often unclear. Therefore, this work also proposes a novel kernel that is based on the Tucker decomposition. For this kernel the Tucker factors are computed based on re-weighting of the Tucker matrices with tuneable powers of singular values from the Higher Order Singular Value decomposition (HOSVD). This provides a mechanism to balance the contribution of the Tucker core and factors of the data. The support tensor machines with this new kernel benchmark on several datasets. First experiment is using generated synthetic data where two classes di er in either Tucker factors or core, and compare the novel and previously existing kernels. This shows robustness of the new kernel with respect to both classi cation scenarios. Further, testing the new method on real-world datasets is also included. The proposed kernel has demonstrated a similar test accuracy than the state-of-the-art TT-MMK, and a signi cantly lower computational time. Finally, this thesis de nes a regularized form of Support Tensor Machine (STM) as a classi cation machine learning model. The algorithm builds a full Gradient Descent Primal (GDP) optimization problem that takes initialized variables from the partial GDP model, which is a standard STM, optimized with TT-CP low-rank approximation. The full GDP is a tensor decomposition method tailored to the classi cation di culty and a classi cation method that exploits the low-rank model of the data. The proposed optimization regime and the relationship between primal-dual for TT-CP decomposition has been theoretically proven. This proposed work shows some numerical challenges and detailed discussion on the further plausible advancements.

Ein zunehmender Teil der gesammelten Daten sind hochdimensionale Mehrweg-Arrays (Tensoren), und es ist für e ziente Lernalgorithmen entscheidend, diese Tensorstruk- tur so weit wie möglich auszunutzen. Der allgegenwärtige Fluch der Dimensional- ität für hochdimensionale Daten und der Strukturverlust bei der Vektorisierung der Daten motiviert den Einsatz maÿgeschneiderter Tensor-Klassi zierungsverfahren mit niedrigem Rang. Bei kleinen Mengen von Trainingsdaten sind Kernel-Methoden eine attraktive Wahl, da sie die Möglichkeit für eine nichtlineare Entscheidungsgrenze bi- eten. Diese Arbeit konzentriert sich auf die Entwicklung von Kernel-Methoden, die auf Low-Rank-Zerlegung basieren. Einer der ersten vorgeschlagenen Ansätze ist der Tensor Train Multi-way Multi-level Kernel (TT-MMK), der die Einfachheit der kanonischen polyadischen Dekomposition, die Klassi zierungsleistung der Dual Structure-preserving Support Vector Machine und die Zuverlässigkeit der Tensor Train (TT) Approximation kombiniert. Der vorgeschlagene Algorithmus basiert auf der Berechnung einer kanonischen polyadischen (CP) Zerlegung, indem er das NP-schwere Problem, den besten CP-Rang zu nden, vermeidet, indem er zuerst eine Tensor-Train (TT)-Zerlegung berechnet und ihn TT-CP-Faktorisierung nennt. Zusammen mit den Experimenten wird gezeigt, dass die TT-MMK-Methode in der Regel rechnerisch zuverlässiger ist, weniger emp ndlich auf Tuning-Parameter reagiert und eine höhere Vorhersagegenauigkeit bei der SVM-Klassi zierung bietet, wenn sie mit anderen modernen Techniken verglichen wird. Darüber hinaus reduziert das Klassi zierungsmodell, das die Tensorzerlegung mit niedrigem Rang als entscheidenden ersten Schritt beinhaltet, die Rechenkomplexität und extrahiert informative Merkmale. Es ist jedoch oft unklar, welche entscheidenden Merkmale der Tensoren von diesen Kerneln genutzt werden. Daher wird in dieser Arbeit auch ein neuartiger Kernel vorgeschlagen, der auf der Tucker-Zerlegung basiert. Für diesen Kernel werden die Tucker-Faktoren auf der Grundlage einer Neugewichtung der Tucker-Matrizen mit einstellbaren Potenzen der Singulärwerte aus der HOSVD- Zerlegung berechnet. Dies bietet einen Mechanismus, um den Beitrag des Tucker- Kerns und der Faktoren der Daten auszugleichen. Die Support-Tensor-Maschinen mit diesem neuen Kernel werden an verschiedenen Datensätzen getestet. Das erste Ex- periment verwendet synthetische Daten, bei denen sich zwei Klassen entweder in den Tucker-Faktoren oder im Kern unterscheiden, und vergleicht den neuen mit den bereits vorhandenen Kerneln. Dies zeigt die Robustheit des neuen Kernels in Bezug auf beide Klassi zierungsszenarien. Weitere Tests der neuen Methode auf realen Datensätzen sind ebenfalls enthalten. Der vorgeschlagene Kernel hat eine ähnliche Testgenauigkeit wie der Stand der Technik und eine deutlich geringere Rechenzeit gezeigt. Schlieÿlich wird in dieser Arbeit eine regularisierte Form der Support Tensor Machine (STM) als maschinelles Klassi kationslernmodell de niert. Der Algorithmus erstellt ein vollständi- ges Gradient Descent Primal (GDP)-Optimierungsproblem, das initialisierte Variablen aus dem partiellen GDP-Modell übernimmt, das eine Standard-STM ist und mit TT- CP-Niedrigrang-Approximation optimiert wurde. Das vollständige BIP ist eine auf das Klassi zierungsproblem zugeschnittene Tensor-Zerlegungsmethode und eine Klas- si zierungsmethode, die das Low-Rank-Modell der Daten ausnutzt. Das vorgeschlagene Optimierungsregime und die Beziehung zwischen primär-dual für die TTCP-Zerlegung wurden theoretisch nachgewiesen. Die vorgeschlagene Arbeit zeigt einige numerische Herausforderungen und eine detaillierte Diskussion weiterer plausibler Weiterentwicklung.