\chapter{Décomposition matricielle/tensorielle}
\label{ch:decomposition}

%\section{Motivations}
%\section{Décomposition matricielle}
%\subsection{Formulation générale du problème}
%\subsection{Décomposition en valeurs singulières}
%\subsection{Décomposition en matrices non-négatives}
%\subsection{Extensions}
\input{Subsections/Decompositions/motivations} 
\input{Subsections/Decompositions/svd}
\input{Subsections/Decompositions/nmf} 

\section{Décomposition tensorielle}

Nous allons maintenant présenter une généralisation des méthodes précédentes aux tenseurs, \index{tenseur} c'est-à-dire à des tableaux multidimensionnels. Nous nous intéressons ici aux tenseurs réels du troisième ordre, notés $\mathbf{\underline{T}} (\in \mathbb{R}^{I \times J \times K})$ et caractérisés par trois dimensions : lignes, colonnes et \textit{tubes}. L'extension aux ordres supérieurs est directe. Les tenseurs du troisième ordre permettent de représenter des ensembles de matrices. L'élément général d'un tenseur, à la ligne $i$,  colonne $j$  et au tube $k$, sera noté $T_{ijk}$. En fixant $i$, $j$ ou $k$, on obtient respectivement une tranche horizontale ($T_{i::}$), latérale ($T_{:j:}$) ou frontale ($T_{::k}$). De même, en fixant deux indices sur trois, nous obtenons des fibres colonne ($T_{:jk}$), ligne ($T_{i:k}$) ou tube ($T_{ij:}$). La figure~\ref{fig:tensor}, tirée de \cite{kolda-2009}, illustre ces éléments.

\vspace{0.3cm}
\begin{figure}[h!]
\centering
\begin{tabular}{c}
\includegraphics[width=0.7\textwidth]{Figs/chapter-Decomposition/FibresTenseur.png} \\
\textbf{(a)} Fibres colonne, ligne et tube (de gauche à droite)\\
\includegraphics[width=0.7\textwidth]{Figs/chapter-Decomposition/TranchesTenseur.png}\\
\textbf{(b)} Tranches horizontales, latérales et frontales (de gauche à doite)\\
\end{tabular}
%\begin{subfigure}[b]{0.8\textwidth}
%\centering \includegraphics[width=0.7\textwidth]{./Figs/chapter-Decomposition/FibresTenseur.pdf}
%\caption{Fibres colonne, ligne et tube (de gauche à droite)}
%\end{subfigure}

%\begin{subfigure}[b]{0.8\textwidth}
%\centering \includegraphics[width=0.7\textwidth]{./Figs/chapter-Decomposition/TranchesTenseur.pdf}
%\caption{Tranches horizontales, latérales et frontales (de gauche à doite)}
%\end{subfigure}
\caption{Tranches et fibres d'un tenseur du troisième ordre}
\label{fig:tensor}
\end{figure}
\vspace{0.3cm}

Nous présentons ici la décomposition de tenseurs du troisième ordre sous forme d'une somme d'un produit tensoriel de vecteurs, qui est très utilisée en pratique et qui porte le nom de décomposition canonique polyadique. D'autres types de décomposition existent, mettant par exemple en jeu des tenseurs d'ordre 2 ou 3 (comme celle de Tucker). Leur présentation dépasse néanmoins le cadre du présent chapitre et nous renvoyons le lecteur intéressé à \cite{kolda-2009}.

\subsection{Décomposition canonique polyadique}

La décomposition canonique polyadique \index{décomposition!canonique de tenseur} d'un tenseur consiste à trouver la somme d'un produit de tenseurs de rang 1 (c'est-à-dire de vecteurs) qui approche au mieux un tenseur $\mathbf{\underline{T}}$ donné. En d'autres termes, on cherche les vecteurs $\mathbf{a}_r \in \mathbb{R}^{I}$, $\mathbf{b}_r \in \mathbb{R}^{J}$ et $\mathbf{c}_r \in \mathbb{R}^{K}$ ($1 \le r \le R$) tels que :
%
\begin{equation}\label{eq:cpd}
\mathbf{\underline{T}} \approx \sum_{r=1}^R \mathbf{a}_r \otimes  \mathbf{b}_r \otimes \mathbf{c}_r
\end{equation}
%
où $\otimes$ dénote le produit tensoriel. Le plus petit $r$ pour lequel la décomposition ci-dessus est exacte correspond au rang du tenseur $\mathbf{\underline{T}}$.

Chaque terme $T_{ijk}$ du tenseur est donc approché par la somme $\sum_{r=1}^R a_{ir} b_{jr} c_{kr}$. En notant $\mathbf{A}$ (resp. $\mathbf{B}$ et $\mathbf{C}$) la matrice dont les $R$ colonnes correspondent aux vecteurs $\mathbf{a}_r$ (resp. $\mathbf{b}_r$ et $\mathbf{c}_r$), on voit que la décomposition polyadique d'un tenseur du troisième ordre vise à trouver trois matrices qui permettent de réécrire chaque terme du tenseur sous la forme d'un produit trilinéaire des vecteurs lignes de ces matrices.

L'erreur commise par l'approximation est mesurée par la somme des carrés des résidus :
%
\begin{equation}\label{eq:error}
\sum_{i,j,k} (T_{ijk} - \sum_{r=1}^R a_{ir} b_{jr} c_{kr})^2
\end{equation}
%

La décomposition polyadique a été introduite par \cite{cpd}, puis réutilisée indépendamment par \cite{parafac} et \cite{candecomp} sous les noms de PARAFAC (\textit{Parallel Factor Analysis}) et CANDECOMP (\textit{Canonical Decomposition}). Le succès de cette décomposition vient du fait qu'elle est en général unique modulo la permutation et le changement d'échelle des facteurs\footnote{Nous renvoyons le lecteur intéressé à \cite{kolda-2009} pour plus de détails.}.

Une méthode standard pour trouver les matrices $\mathbf{A}$, $\mathbf{B}$ et $\mathbf{C}$ passe par l'algorithme des moindres carrés alternés, vu précédemment, qui consiste à calculer alternativement $\mathbf{A}$, $\mathbf{B}$ et $\mathbf{C}$ de manière à minimiser l'erreur donnée par \ref{eq:error}, les deux autres matrices étant fixées. Pour cela, on \textbf{déplie} tout d'abord le tenseur du troisième ordre $\mathbf{\underline{T}}$ sous la forme d'une matrice qui comporte $I$ lignes  et $JK$ colonnes et que nous noterons $\mathbf{T}_A$. Les $J$ premières colonnes correspondent aux éléments $T_{ijk}$ pour lesquels $k=1$, les $J$ suivantes aux éléments pour lesquels $k=2$ et ainsi de suite. Un dépliage similaire est obtenu en considérant une matrice à $J$ ou $K$ lignes, donnant lieu à $\mathbf{T}_B$ et $\mathbf{T}_C$. 

Connaissant $\mathbf{B}$ et $\mathbf{C}$, on peut former la matrice $\mathbf{Z}$ à $R$ lignes et $JK$ colonnes dans laquelle les $J$ premières colonnes correspondent au produit terme à terme des vecteurs $\mathbf{b}_j, \, 1 \le j \le J$ et $\mathbf{c}_1$. Les $J$ colonnes suivantes sont obtenues avec $\mathbf{c}_2$ et ainsi de suite jusqu'à $\mathbf{c}_K$. Connaissant $\mathbf{Z}$ et $\mathbf{T}_A$, le problème donné par \ref{eq:cpd} consiste alors à trouver la matrice $\mathbf{A}$ qui permette de reconstruire $\mathbf{T}_A$ à partir de $\mathbf{Z}$:
%
\[
\mathbf{T}_A \approx \mathbf{A} \mathbf{Z}
\]
%
L'erreur est mesurée par la somme des carrés des résidus. Dans ce cas, l'estimé de $\mathbf{T}_A$ par la méthode des moindres carrés est donné par :
%
\begin{equation}\label{eq:estA}
\mathbf{A} = \mathbf{T}_A \mathbf{Z}^t(\mathbf{Z}\mathbf{Z}^t)^{-1}
\end{equation}
%
où $^t$ dénote la transposée.

L'algorithme complet prend alors la forme :

\restylealgo{algoruled}
\begin{algorithm}[H]
    \SetKwInOut{Entr}{Entrée}
    \SetKwInOut{Sort}{Sortie}
    \SetKwInOut{Init}{Initialisation}
\caption{Algorithme des moindres carrés alternés (\textit{ALS}) pour la décomposition polyadique\index{algorithme!des moindres carrés alternés}}

\Entr{\begin{itemize}\item La matrice  $R$\end{itemize}}
       \textbf{Initialisation :}
       \begin{itemize}\item Les matrices  $\mathbf{B}$ et $\mathbf{C}$
       \end{itemize}
\Tq{Critère d'arrêt non satisfait}
{
\begin{itemize}
\item Construire $\mathbf{T}_A$ et $\mathbf{Z}$ et estimer $\mathbf{A}$ à partir de \ref{eq:estA}
\item Estimer $\mathbf{B}$ de la même façon
\item Estimer $\mathbf{C}$ de la même façon
\end{itemize}
}
\end{algorithm}
\vspace{0.3cm}

Plusieurs critères d'arrêt sont envisageables en pratique, fondés sur le nombre d'itérations ou sur le fait que les estimés des matrices $\mathbf{A}$, $\mathbf{B}$ et $\mathbf{C}$ n'évoluent plus. Il est de plus possible d'accélérer l'algorithme précédent en appliquant tout d'abord une ACP sur une des matrices dépliées, puis en reconstruisant un tenseur de dimension réduite sur lequel l'algorithme PARAFAC est appliqué. En pratique, cela peut conduire à gagner plusieurs ordres de grandeur. D'autres méthodes d'accélération ont été proposées, comme celles fondées sur des recherches en lignes (voir par exemple \cite{rajih-2008}).

%\subsection{Décomposition de Tucker}

%Il existe une autre décomposition de tenseurs fondée sur le produit tensoriel entre une matrice et un tenseur. Soit  $\mathbf{\underline{T}} (\in \mathbb{R}^{I_1 \times I_2 \times I_3})$ un tenseur du troisième ordre et $\mathbf{A}$ une matrice de $\mathbb{R}^{I_2 \times J}$. Le produit tensoriel de $\mathbf{\underline{T}}$ par $\mathbf{A}$, noté $\mathbf{\underline{T}} \otimes \mathbf{A}$

\section{Conclusion}

Les méthodes de décompositions matricielles et tensorielles sont utilisées dans diverses applications : compression de données, reconstruction/prédiction de valeurs manquantes ou non observées, dé-bruitage des données, (co-)clustering. Il existe des liens forts entre ces méthodes et les modèles probabilistes latents (voir par exemple \cite{GaussierG05} et \cite{Peng-2011}) qui montrent que les méthodes de décomposition non négatives ont presque toujours un équivalent probabiliste. Un modèle comme PLSI (\textit{Probabilistic Latent Semantic Indexing}) introduit dans \cite{Hofmann-1999} est également considéré comme une version probabiliste du modèle LSI (\textit{Latent Semantic Indexing}) fondé sur une décomposition en valeurs singulières (\cite{Deerwester90}). Plus récemment, des liens entre ces méthodes et les méthodes permettant d'obtenir des plongements de mots (\textit{word embeddings}) ont été établis (\cite{Levy-2014}). Enfin, comme nous l'avons déjà signalé, il existe de plus de nombreuses extensions de ces méthodes ; ainsi, \cite{TrouillonWRGB16} s'intéressent à une décomposition dans le domaine complexe pour rendre compte de relations entre entités qui peuvent être symétriques ou antisymétriques.

\input{Subsections/Decompositions/exercices} 

%\bibliographystyle{plainnat-fr}
%\bibliography{biblio-Decomposition}
