Les méthodes de réseau de tenseurs (TN) ont été un ingrédient essentiel des progrès de la physique de la matière condensée et ont récemment suscité l'intérêt de la communauté de l'apprentissage automatique pour leur capacité à représenter de manière compacte des objets de très grande dimension. Les méthodes TN peuvent par exemple être utilisées pour apprendre efficacement des modèles linéaires dans des espaces de caractéristiques exponentiellement grands [1]. Dans ce manuscrit, nous dérivons des limites supérieures et inférieures sur la VC-dimension et la pseudo-dimension d'une grande classe de Modèles TN pour la classification, la régression et la complétion . Nos bornes supérieures sont valables pour les modèles linéaires paramétrés par structures TN arbitraires, et nous dérivons des limites inférieures pour les modèles de décomposition tensorielle courants (CP, Tensor Train, Tensor Ring et Tucker) montrant l'étroitesse de notre borne supérieure générale. Ces résultats sont utilisés pour dériver une
borne de généralisation qui peut être appliquée à la classification avec des matrices de faible rang ainsi qu'à des classificateurs linéaires basés sur l'un des modèles de décomposition tensorielle couramment utilisés. En corollaire de nos résultats, nous obtenons une borne sur la VC-dimension du classificateur basé sur le matrix product state introduit dans [1] en fonction de la dimension de liaison
(i.e. rang de train tensoriel), qui répond à un problème ouvert répertorié par Cirac, Garre-Rubio et Pérez-García [2]. / Tensor network (TN) methods have been a key ingredient of advances in condensed matter physics and have recently sparked interest in the machine learning community for their ability to compactly represent very high-dimensional objects. TN methods can for example be used to efficiently learn linear models in exponentially large feature spaces [1]. In this manuscript, we derive upper and lower bounds on the VC-dimension and pseudo-dimension of a large class of TN models for classification, regression and completion. Our upper bounds hold for linear models parameterized by arbitrary TN structures, and we derive lower bounds for common tensor decomposition models (CP, Tensor Train, Tensor Ring and Tucker) showing the tightness of our general upper bound. These results are used to derive a generalization bound which can be applied to classification with low-rank matrices as well as linear classifiers based on any of the commonly used tensor decomposition models. As a corollary of our results, we obtain a bound on the VC-dimension of the matrix product state classifier introduced in [1] as a function of the so-called bond dimension (i.e. tensor train rank), which answers an open problem listed by Cirac, Garre-Rubio and Pérez-García [2].
| Identifer | oai:union.ndltd.org:umontreal.ca/oai:papyrus.bib.umontreal.ca:1866/27058 |
| Date | 01 1900 |
| Creators | Khavari, Behnoush |
| Contributors | Rabusseau, Guillaume |
| Source Sets | Université de Montréal |
| Language | English |
| Detected Language | French |
| Type | thesis, thèse |
| Format | application/pdf |
Page generated in 0.0016 seconds