CS 229 - Machine Learning

Rappels d'algèbre linéaire et d'analyse
Star

Par Afshine Amidi et Shervine Amidi

Notations générales

Définitions

Vecteur On note $x\in\mathbb{R}^n$ un vecteur à $n$ entrées, où $x_i\in\mathbb{R}$ est la $i^{ème}$ entrée :

\[x=\left(\begin{array}{c}x_1\\x_2\\\vdots\\x_n\end{array}\right)\in\mathbb{R}^n\]

Matrice On note $A\in\mathbb{R}^{m\times n}$ une matrice à $m$ lignes et $n$ colonnes, où $A_{i,j}\in\mathbb{R}$ est l'entrée située à la $i^{ème}$ ligne et $j^{ième}$ colonne:

\[A=\left(\begin{array}{ccc}A_{1,1}& \cdots&A_{1,n}\\\vdots&& \vdots\\A_{m,1}& \cdots&A_{m,n}\end{array}\right)\in\mathbb{R}^{m\times n}\]

Remarque : le vecteur $x$ défini ci-dessus peut être vu comme une matrice $n\times1$ et est aussi appelé vecteur colonne.


Matrices principales

Matrice identité La matrice identité $I\in\mathbb{R}^{n\times n}$ est une matrice carrée avec des 1 sur sa diagonale et des 0 partout ailleurs :

\[I=\left(\begin{array}{cccc}1&0& \cdots&0\\0& \ddots& \ddots& \vdots\\\vdots& \ddots& \ddots&0\\0& \cdots&0&1\end{array}\right)\]

Remarque : pour toute matrice $A\in\mathbb{R}^{n\times n}$, on a $A\times I=I\times A=A$.


Matrice diagonale Une matrice diagonale $D\in\mathbb{R}^{n\times n}$ est une matrice carrée avec des valeurs non nulles sur sa diagonale et des zéros partout ailleurs.

\[D=\left(\begin{array}{cccc}d_1&0& \cdots&0\\0& \ddots& \ddots& \vdots\\\vdots& \ddots& \ddots&0\\0& \cdots&0&d_n\end{array}\right)\]

Remarque : on note aussi $D=\textrm{diag}(d_1,...,d_n)$.


Opérations matricielles

Multiplication

Vecteur-vecteur Il y a deux types de multiplication vecteur-vecteur :

- Produit scalaire : pour $x,y\in\mathbb{R}^n$, on a :

\[\boxed{x^Ty=\sum_{i=1}^nx_iy_i\in\mathbb{R}}\]

- Produit dyadique : pour $x\in\mathbb{R}^m, y\in\mathbb{R}^n$, on a :

\[\boxed{xy^T=\left(\begin{array}{ccc}x_1y_1& \cdots&x_1y_n\\\vdots&& \vdots\\x_my_1& \cdots&x_my_n\end{array}\right)\in\mathbb{R}^{m\times n}}\]

Matrice-vecteur Le produit de la matrice $A\in\mathbb{R}^{m\times n}$ et du vecteur $x\in\mathbb{R}^{n}$ est un vecteur de taille $\mathbb{R}^{m}$, tel que :

\[\boxed{Ax=\left(\begin{array}{c}a_{r,1}^Tx\\\vdots\\a_{r,m}^Tx\end{array}\right)=\sum_{i=1}^na_{c,i}x_{i}\in\mathbb{R}^{m}}\]
où $a_{r,i}^T$ sont les vecteurs-ligne et $a_{c,j}$ sont les vecteurs-colonne de $A$ et $x_i$ sont les entrées de $x$.


Matrice-matrice Le produit des matrices $A\in\mathbb{R}^{m\times n}$ et $B\in\mathbb{R}^{n\times p}$ est une matrice de taille $\mathbb{R}^{m\times p}$, tel que :

\[\boxed{AB=\left(\begin{array}{ccc}a_{r,1}^Tb_{c,1}& \cdots&a_{r,1}^Tb_{c,p}\\\vdots&& \vdots\\a_{r,m}^Tb_{c,1}& \cdots&a_{r,m}^Tb_{c,p}\end{array}\right)=\sum_{i=1}^na_{c,i}b_{r,i}^T\in\mathbb{R}^{m\times p}}\]
où $a_{r,i}^T, b_{r,i}^T$ sont des vecteurs-ligne et $a_{c,j}, b_{c,j}$ sont des vecteurs-colonne de $A$ et $B$ respectivement.


Autres opérations

Transposée La transposée d'une matrice $A\in\mathbb{R}^{m\times n}$ est notée $A^T$ et est dans $\mathbb{R}^{n\times m}$ tel que:

\[\boxed{\forall i,j,\quad\quad A_{i,j}^T=A_{j,i}}\]

Remarque : pour des matrices $A, B$, on a $(AB)^T=B^TA^T$.


Inverse L'inverse d'une matrice carrée inversible $A$ est notée $A^{−1}$ et est l'unique matrice telle que :

\[\boxed{AA^{-1}=A^{-1}A=I}\]

Remarque : toutes les matrices carrés ne sont pas inversibles. Aussi, pour des matrices $A,B$, on a $(AB)^{-1}=B^{-1}A^{-1}$.


Trace La trace d'une matrice carrée $A$, notée $\textrm{tr}(A)$, est la somme de ses entrées diagonales :

\[\boxed{\textrm{tr}(A)=\sum_{i=1}^nA_{i,i}}\]

Remarque : pour toutes matrices $A, B$, on a $\textrm{tr}(A^T)=\textrm{tr}(A)$ et $\textrm{tr}(AB)=\textrm{tr}(BA)$.


Déterminant Le déterminant d'une matrice carrée $A\in\mathbb{R}^{n\times n}$ notée $|A|$ ou $\textrm{det}(A)$ est exprimée récursivement en termes de $A_{\backslash i, \backslash j}$, qui est la matrice $A$ sans sa $i^{ème}$ ligne et $j^{ième}$ colonne, de la manière suivante :

\[\boxed{\textrm{det}(A)=|A|=\sum_{j=1}^n(-1)^{i+j}A_{i,j}|A_{\backslash i,\backslash j}|}\]

Remarque : $A$ est inversible si et seulement si $|A|\neq0$. Aussi, $|AB|=|A||B|$ et $|A^T|=|A|$.


Propriétés matricielles

Définitions

Décomposition symétrique Une matrice donnée $A$ peut être exprimée en termes de ses parties symétrique et antisymétrique de la manière suivante :

\[\boxed{A=\underbrace{\frac{A+A^T}{2}}_{\textrm{symétrique}}+\underbrace{\frac{A-A^T}{2}}_{\textrm{Antisymétrique}}}\]

Norme Une norme est une fonction $N:V\longrightarrow[0,+\infty[$ où $V$ est un espace vectoriel, et tel que pour tous $x,y\in V$, on a :

- $N(x+y)\leqslant N(x)+N(y)$
- $N(ax)=|a|N(x)$ pour $a$ scalaire
- si $N(x)=0$, alors $x=0$

Pour $x\in V$, les normes les plus utilisées sont récapitulées dans le tableau ci-dessous :

Norme Notation Définition Cas
Manhattan, $L^1$ $||x||_1$ $\displaystyle\sum_{i=1}^n|x_i|$ LASSO
Euclidean, $L^2$ $||x||_2$ $\displaystyle\sqrt{\sum_{i=1}^nx_i^2}$ Ridge
$p$-norme, $L^p$ $||x||_p$ $\displaystyle\left(\sum_{i=1}^nx_i^p\right)^{\frac{1}{p}}$ Inégalité de Hölder
Infini, $L^{\infty}$ $||x||_{\infty}$ $\underset{i}{\textrm{max }}|x_i|$ Convergence uniforme

Dépendance linéaire Un ensemble de vecteurs est considéré comme étant linéairement dépendant si un des vecteurs de cet ensemble peut être défini comme une combinaison des autres.

Remarque : si aucun vecteur ne peut être noté de cette manière, alors les vecteurs sont dits linéairement indépendants.


Rang d'une matrice Le rang d'une matrice donnée $A$ est notée $\textrm{rang}(A)$ et est la dimension de l'espace vectoriel généré par ses colonnes. Ceci est équivalent au nombre maximum de colonnes indépendantes de $A$.


Matrice semi-définie positive Une matrice $A\in\mathbb{R}^{n\times n}$ est semi-définie positive et est notée $A\succeq 0$ si l'on a :

\[\boxed{A=A^T}\quad\textrm{ et }\quad\boxed{\forall x\in\mathbb{R}^n,\quad x^TAx\geqslant0}\]

Remarque : de manière similaire, une matrice $A$ est dite définie positive et est notée $A\succ0$ si elle est semi-définie positive et si pour tout vecteur $x$ non nul, on a $x^TAx>0$.


Valeur propre, vecteur propre Étant donné une matrice $A\in\mathbb{R}^{n\times n}$, $\lambda$ est une valeur propre de $A$ s'il existe un vecteur $z\in\mathbb{R}^n\backslash\{0\}$, appelé vecteur propre, tel que :

\[\boxed{Az=\lambda z}\]

Théorème spectral Soit $A\in\mathbb{R}^{n\times n}$. Si $A$ est symétrique, alors $A$ est diagonalisable par une matrice orthogonale réelle $U\in\mathbb{R}^{n\times n}$. En notant $\Lambda=\textrm{diag}(\lambda_1,...,\lambda_n)$, on a :

\[\boxed{\exists\Lambda\textrm{ diagonal},\quad A=U\Lambda U^T}\]

Décomposition en valeurs singulières Pour une matrice $A$ de dimensions $m\times n$, la décomposition en valeurs singulières est une technique de factorisation qui garantit l'existence d'une matrice unitaire $U$ $m\times m$, d'une matrice diagonale $\Sigma$ $m\times n$ et d'une matrice unitaire $V$ $n\times n$, tel que :

\[\boxed{A=U\Sigma V^T}\]

Analyse matricielle

Gradient Soit $f:\mathbb{R}^{m\times n}\rightarrow\mathbb{R}$ une fonction et $A\in\mathbb{R}^{m\times n}$ une matrice. Le gradient de $f$ par rapport à $A$ est une matrice de taille $m\times n$, notée $\nabla_A f(A)$, telle que :

\[\boxed{\Big(\nabla_A f(A)\Big)_{i,j}=\frac{\partial f(A)}{\partial A_{i,j}}}\]

Remarque : le gradient de $f$ est seulement défini lorsque $f$ est une fonction donnant un scalaire.


Hessienne Soit $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ une fonction et $x\in\mathbb{R}^{n}$ un vecteur. La hessienne de $f$ par rapport à $x$ est une matrice symétrique $n\times n$, notée $\nabla_x^2 f(x)$, telle que :

\[\boxed{\Big(\nabla_x^2 f(x)\Big)_{i,j}=\frac{\partial^2 f(x)}{\partial x_i\partial x_j}}\]

Remarque : la hessienne de $f$ est seulement définie lorsque $f$ est une fonction qui donne un scalaire.


Opérations de gradient Pour des matrices $A,B,C$, les propriétés de gradient suivants sont bons à savoir :

\[\boxed{\nabla_A\textrm{tr}(AB)=B^T}\quad\quad\boxed{\nabla_{A^T}f(A)=\left(\nabla_Af(A)\right)^T}\] \[\boxed{\nabla_A\textrm{tr}(ABA^TC)=CAB+C^TAB^T}\quad\quad\boxed{\nabla_A|A|=|A|(A^{-1})^T}\]