\section[D\'ecomposition en matrices \\ non n\'egatives]{D\'ecomposition en matrices \\ non n\'egatives}\label{sec:nmf}

Dans bien des situations, la matrice d'int\'er\^et $A$ est \`a coefficients tous positifs ou nuls (\textit{non negative matrix} en anglais). C'est le cas par exemple des matrices utilisateurs/items qui interviennent dans les syst\`emes de recommandation. On peut alors chercher une expression de $A$ comme produit de matrices qui conserve ce caract\`ere positif. C'est l'objectif de la factorisation en matrices non négatives (\textit{Non negative Matrix Factorization} - NMF) que nous allons exposer maintenant. 

Dans tout ce qui suit, on se donne $A$ une matrice \`a termes positifs ou nuls.  On souhaite trouver $U,V$ facteurs \`a termes positifs tels que $A\approx UV$. Pour cela, la d\'emarche va consister \`a r\'esoudre le probl\`eme d'optimisation:
\[
\inf_{U,V}\|A-UV\|
\]
pour diff\'erentes normes matricielles $\|\cdot\|$ et en imposant diff\'erentes contraintes sur les matrices $U$ et $V$.
% qui vont chaque fois mener \`a diff\'erents algorithmes. 
Nous allons consid\'erer la norme de Frobenius et exposer l'algorithme originel introduit par~\cite{lee2001algorithms}. 
%Nous comparerons ensuite la NMF et la SVD et donnerons quelques exemples d'application avec des r\'ef\'erences. 
%Nous allons dans un premier temps commencer par des notions pr\'eliminaires d'optimisation, en nous int\'eressant \`a un probl\`eme plus simple mais qui interviendra dans toute la suite.

\subsection{Algorithme de Seung et Lee}
Tout ce qui suit est tir\'e de~\cite{lee2001algorithms}. Nous commencons par consid\'erer le cas simple o\`u la matrice $A$ est un vecteur $y$ et o\`u la matrice $U$ est fix\'ee. On cherche donc un vecteur $x$ \`a coefficients tous positifs tel que :
%$x\in \mathrm{Argmin}\;\|y-Ux\|_2^2$. 
\begin{equation}\label{eq:nnls}
x\in \mathrm{Argmin}\;\|y-Ux\|_2^2 \nonumber
\end{equation}
Ce probl\`eme de minimisation au sens des moindres carr\'es avec contrainte de positivit\'e admet une solution, sans garantie toutefois d'unicit\'e.

%Donnons un r\'esultat d'existence de la solution.
%\begin{thm}
%Le probl\`eme~\eqref{eq:nnls} admet une solution, sans garantie d'unicit\'e sans hypoth\`ese suppl\'ementaire sur $U$.
%\end{thm}

De\index{algorithme!NMF} nombreux algorithmes ont \'et\'e propos\'es pour trouver une solution de ce probl\`eme, en particulier via des mises \`a jour multiplicatives qui ont la bonne propri\'et\'e de conserver la positivit\'e. Nous d\'etaillons l'algorithme qui est un cas particulier de celui de la NMF. %, que nous d\'etaillerons plus loin.

\restylealgo{algoruled}
\begin{algorithm}[H]\label{algo:nmf-simple}
    \SetKwInOut{Entr}{Entrée}
    \SetKwInOut{Sort}{Sortie}
    \SetKwInOut{Init}{Initialisation}
\caption{Version de l'algorithme de la NMF dans le cas simple o\`u $A$ est un vecteur $y$}
\Entr{\begin{itemize}\item matrice $U$ de taille $p\times n$ \`a coefficients positifs, $y$ vecteur de taille $(\mathbb{R}_+)^p$\end{itemize}}
       \textbf{Initialisation :}
       \begin{itemize} \item $x\leftarrow x^{(0)}$ avec $x^{(0)}\in (\mathbb{R}_+)^n$ \end{itemize}
\Pour{$k=0,\cdots,n_{iter}-1 $}{
\Pour{$\ell=1,\cdots,n$ } {$x^{(k+1)}_{\ell}\leftarrow x^{(k)}_{\ell}\frac{(U^T y)_\ell}{(U^T U x^{(k)})_\ell}$}}
\Sort{$x$ vecteur de $(\mathbb{R}_+)^n$ minimisant $\|Ux-y\|_2$} 
\end{algorithm}

\noindent Commentons cet algorithme. Remarquons que minimiser $\|Ux-y\|_2$ sans tenir compte de la contrainte revient \`a r\'esoudre $U^T Ux=U^T y$. On est donc amen\'e \`a r\'esoudre un probl\`eme de point fixe, qui s'\'ecrit coordonn\'ee \`a coordonn\'ee $x_\ell=f_{\ell}(x_\ell)$ avec $f_{\ell}(x_\ell)=(U^T y)_\ell/(U^T Ux)_\ell$. Comme la fonction $f=\begin{pmatrix}f_1\\ \vdots\\ f_n\end{pmatrix}$  conserve la positivit\'e des coordonn\'ees, il devient naturel de proposer:
\[
x^{(k+1)}_\ell\leftarrow f_\ell(x_\ell)
\]  
Nous nous pla\c cons maintenant dans le cas g\'en\'eral o\`u $A$ est une matrice donn\'ee de taille $p\times n$. Les matrices $U$ et $V$ ne sont cette fois-ci connues ni l'une ni l'autre et nous devons les d\'eterminer. Nous cherchons donc $U,V$ deux matrices de tailles respectives $p\times r$ et $r\times n$ \`a coefficients tous positifs, telles que:
\[
\min\|A-UV\|_2
\]
Pour r\'esoudre num\'eriquement ce probl\`eme, on va fixer $U$ puis optimiser $\|A-UV\|_2$ par rapport \`a $V$, puis fixer $V$ et optimiser $\|A-UV\|_2$ par rapport \`a $U$. 

\restylealgo{algoruled}
\begin{algorithm}[H]
    \SetKwInOut{Entr}{Entrée}
    \SetKwInOut{Sort}{Sortie}
    \SetKwInOut{Init}{Initialisation}
\caption{Version g\'en\'erale de l'algorithme de Seung et Lee}
       \textbf{Initialisation :}
       \begin{itemize}\item $U,V\leftarrow U^{(0)},V^{(0)}$        \end{itemize}
\Pour{$k=0,\cdots,n_{iter}-1$}
{
\Pour{$\ell,m$} 
{
\begin{itemize}
\item $U^{(k+1)}_{\ell m}\leftarrow U^{(k)}_{\ell m}\;\frac{(AV^{(k)\, T})_{\ell m}}{(U^{(k)}V^{(k)}V^{(k)\,T})_{\ell m}}$
\item $V^{(k+1)}_{\ell m}\leftarrow V^{(k)}_{\ell m}\;\frac{(U^{(k+1)\,T} \,A)_{\ell m}}{(U^{(k+1)\,T}\,U A)_{\ell m}}$
\end{itemize}
}
}
\end{algorithm}

\noindent Les it\'erations :
\[
U^{(k+1)}_{\ell m}\leftarrow U^{(k)}_{\ell m}\;\frac{(AV^{(k)\, T})_{\ell m}}{(U^{(k)}V^{(k)}V^{(k)\,T})_{\ell m}}\mbox{ et }V^{(k+1)}_{\ell m}\leftarrow V^{(k)}_{\ell m}\;\frac{(U^{(k+1)\,T} \,A)_{\ell m}}{(U^{(k+1)\,T}\,U A)_{\ell m}}
\]
reviennent \`a r\'esoudre $\min\|A-XV^{(k)}\|_2$ et $\min\|A-U^{(k+1)}Y\|_2$ en utilisant l'algorithme~\eqref{algo:nmf-simple}.

\noindent Seung et Lee ont montr\'e que:
\begin{thm}
La distance $\|A-U^{(k)}V^{(k)}\|_2$ est une fonction d\'ecroissante de $k$.
\end{thm}

\subsection{Algorithme des moindres carr\'es altern\'es}

Comme nous l'avons d\'ej\`a remarqu\'e, nous avons deux probl\`emes des moindres carr\'es avec contrainte de positivit\'e \`a r\'esoudre en fixant succesivement $U$ et $V$. Une m\'ethode alternative \`a celle de Seung et Lee consiste \`a r\'esoudre chacun de ces probl\`emes de moindres carr\'es en utilisant cette fois-ci une mise \`a jour classique, puis \`a projeter sur l'ensemble des matrices positives pour avoir \`a chaque fois des matrices it\'er\'ees qui sont positives\index{algorithme!des moindres carrés alternés}. Cela donne l'algorithme suivant :  

\restylealgo{algoruled}
\begin{algorithm}[H]
    \SetKwInOut{Entr}{Entrée}
    \SetKwInOut{Sort}{Sortie}
    \SetKwInOut{Init}{Initialisation}
\caption{Algorithme ALS}

       \textbf{Initialisation :}
       \begin{itemize}\item  $U$ \end{itemize}
\Pour {$i = 1,\cdots,n_{iter}$} 
{ 
\begin{itemize}
\item R\'esoudre en $V$ : $U^T U V = U^T A$
\item Mettre \`a $0$ les termes n\'egatifs de $V$
\item R\'esoudre en $U$ : $VV^T U^T = VA^T$
\item Mettre \`a $0$ les termes n\'egatifs de $U$
\end{itemize}
}
\end{algorithm}

Dans chacun des deux algorithmes que nous venons de pr\'esenter, diff\'erentes variantes existent pour l'initialisation, initialisation al\'eatoire notamment. Il existe aussi  des versions parall\'elisables de chacun. Nous renvoyons \`a~\cite{gillis2017introduction} pour plus de d\'etails.
\subsection{Comparaison de la SVD et de la NMF}
La NMF est donc, de m\^eme que la SVD, une autre technique de d\'ecomposition de matrice qui va pr\'esenter l'avantage de plus d'interpr\'etabilit\'e puisque les entr\'ees des matrices sont toutes positives. Soulignons toutefois qu'il n'y a pas unicit\'e de la NMF, contrairement \`a ce qui se passe pour la SVD.