OCVX

Analyse en composante principale: algo data mining et reduction de dimensions

Pour la reduction de dimension, on garde que les

$n$ premieres.

Ca se formule comme un probleme d'optimisation

Projection de vecteur sur un autre vecteur : produit scalaire.

Pour chercher quelles donnees se dispersent le plus, on va chercher un vecteur

$w$ telle que la projection (

$X.w$) de mes

$x$ soit maximale et soit une matrice

$$X=\left[\begin{array}{cc}{x}_{11}& x_{12}\\ ⋮& ⋮\\ x_{i1}& x_{i2}\\ ⋮& ⋮\\ x_{n1}& x_{n2}\end{array}\right]$$

On cherche a maximiser

$Var(X.w)$ sous contrainte que

$\Vert w\Vert =1$

Exemple perceptron (1 neurone)

On cherche les parametres du vecteurs normal

On a un probleme qui prend comme origine quelque chose de geometrique

On cherche a discriminer les ronds rouges des points verts, on a la marge en plus de la separation.

On cherche a maximiser la marge telle que tous les echantillons d'une meme classe vont d'un cote ou de l'autre d'une separatrice.

Question 1-1

On se place en un premier temps dans le cas de dimension 2, celui du plan euclidien. Soient

$x$ et

$y$ deux vecteurs de

${\mathbb{R}}^2$, on désigne par

$\theta$ l’angle orienté (dans le sens direct) entre

$x$ et

$y$ et par

$\varphi$ (resp.

$\psi$) celui entre

$x$ (resp.

$y$) et la partie positive de l’axe des abscisses.

1. Représenter la description précédente par un dessin
2. Exprimer les coordonnées de
   $x$ et
   $y$ en fonction de leurs normes respectives et des angles
   $\varphi$ et
   $\psi$
3. En déduire une expression du produit scalaire de
   $<x,y>$ en fonction de
   $\theta$ et des normes de
   $x$ et
   $y$

$$\begin{gathered} x,y\in {\mathbb{R}}^4,<x,y>=x^{T}y=\sum _{i=1}^n{x}_i{y}_i \\ \Vert x\Vert =\sqrt{<x,x>}=\sqrt{x^{T}x} \\ d(x,y)=\Vert x-y\Vert \\ \theta (x,y)=\arccos (\frac{<x,y>}{\Vert x\Vert \Vert y\Vert }) \\ \begin{array}{rl}<x,y>& =x_1{y}_1+x_2{y}_2=\sum _i{x}_i{y}_i\\ & =\Vert x\Vert \Vert y\Vert \cos (\theta (x,y))\end{array} \end{gathered}$$

$\theta (x,y)=\arccos (\frac{<x,y>}{\Vert x\Vert \Vert y\Vert })$: cette formule est vraie quelque soit la nature de

$x$ et

$y$.

Question 1-2

Décrire le lieu de

${\mathbb{R}}^2$ donné par la relation matricielle :

$$\left(\begin{array}{cc}1& 2\\ -1& 1\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)\le \left(\begin{array}{c}0\\ 0\end{array}\right)$$

ensemble des vecteurs tels que

$\{x\in \mathbb{R}|<x.y>\ge 0\}$

$y\ne 0$ et

$\{y\}=\{x\in {\mathbb{R}}^2|<x.y>=0\}$

$$\{\begin{array}{l}x+2y\le 0\\ -x+y\le 0\end{array}$$

Prenons la premiere equation et changeons

$\le$ en

$=$ pour la resoudre.

$x+2y=0$ est de la forme

$ax+by=0$.

Pour une equation de la forme

$ax+by=0$:

$$\begin{gathered} \overrightarrow{n}=\left(\begin{array}{c}a\\ b\end{array}\right)\text{ vecteur normal} \\ \overrightarrow{u}=\left(\begin{array}{c}-b\\ a\end{array}\right)\text{ vecteur directeur} \end{gathered}$$

On peut donc en deduire:

$$\begin{gathered} {\overrightarrow{n}}_1=\left(\begin{array}{c}1\\ 2\end{array}\right)\text{ vecteur normal} \\ {\overrightarrow{u}}_1=\left(\begin{array}{c}-2\\ 1\end{array}\right)\text{ vecteur directeur} \end{gathered}$$

On cherche le demi-plan oriente negativement par rapport a:

$$<{\overrightarrow{n}}_1,\left(\begin{array}{c}x\\ y\end{array}\right)>\le 0$$

Prenons la seconde equation et faisons de meme

$$\begin{gathered} -x+y=0 \\ {\overrightarrow{n}}_2=\left(\begin{array}{c}-1\\ 1\end{array}\right)\text{ vecteur normal} \\ {\overrightarrow{u}}_2=\left(\begin{array}{c}-1\\ -1\end{array}\right)\text{ vecteur directeur} \end{gathered}$$

L'intersection des 2 espaces verifie les 2 inegalites.

Question 1-3

Représenter le lieu de

${\mathbb{R}}^3$ décrit par la reations

$x_1+x_2+x_3\ge 0$.

On cherche:

$$\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)\in {\mathbb{R}}^3$$
tel que

$x_1+x_2+x_3\ge 0$

$$<\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right),\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)>\ge 0$$

On va chercher le lieu de

${\mathbb{R}}^3$ ou

$<\overrightarrow{n}.\overrightarrow{x}>={\overrightarrow{n}}^T\overrightarrow{x}=0$. On prend les point apres et dans le plan.

Question 2-6

Écrire paramétriquement :

• la droite de
  ${\mathbb{R}}^2$ de vecteur directeur
  $(1,-1)$ et passant par
  $(2,3)$;
• le plan de
  ${\mathbb{R}}^3$ donné par l’équation
  $x_1+x_2+x_3=2$.

$$\begin{gathered} \begin{array}{rl}(D)& =\{x\in {\mathbb{R}}^2,x=\lambda u,\lambda \in \mathbb{R}\}\\ & =\{\lambda \overrightarrow{u},\lambda \in \mathbb{R}\}\text{ representation parametrique}\\ & =\{\overrightarrow{x}\in {\mathbb{R}}^2,<\overrightarrow{n},\overrightarrow{x}>=0\}\\ & =\{n^{T}x=0\}\\ & =\{n_1{x}_1+n_2{x}_2=0\}=\text{ representation implicite}\end{array} \\ n=\left(\begin{array}{c}{n}_1\\ n_2\end{array}\right) \\ x=\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right) \end{gathered}$$

$(A)=x+(0,1)$ la droite qui passe par

$(0,1)$ et de vecteur directeur

$\overrightarrow{u}$

$$\begin{array}{rl}(A)& =(0,1)+(D)=(0,1)+\{\lambda \overrightarrow{u},\lambda \in \mathbb{R}\}\text{ avec }\overrightarrow{u}=\left(\begin{array}{c}{u}_1\\ u_2\end{array}\right)\\ & =(0,1)+\{(\lambda u_1,\lambda u_2),\lambda \in \mathbb{R}\}\\ & =\{(0,1)+(\lambda u_1,\lambda u_2),\lambda \in \mathbb{R}\}=\{(\lambda u_1,1+\lambda u_2),\lambda \in \mathbb{R}\}\end{array}$$

$$\begin{gathered} {\overrightarrow{n}}^{\perp }x=c\Rightarrow n_{1}x+n_{2}y=c \\ \Rightarrow ax+by+c=0 \end{gathered}$$

On obtient l'equation implicite d'une droite affine.

$$\to \overrightarrow{n}=\left(\begin{array}{c}a\\ b\end{array}\right)\text{ et }\overrightarrow{u}=\left(\begin{array}{c}-b\\ a\end{array}\right)\text{ et passant par }(0,-\frac{c}{b})$$

Ecriture parametrique de:

• la droite de
  ${\mathbb{R}}^2$ de vecteur directeur
  $\overrightarrow{u}=(1,-1)$ et passant par
  $(2,3)$
  $(A)$

$$\begin{array}{rl}(A)& =(2,3)+\{\overrightarrow{x}\in {\mathbb{R}}^2,\overrightarrow{x}=\lambda \overrightarrow{u},\lambda \in \mathbb{R}\}\\ & =(2,3)+\{(\lambda ,-\lambda ),\lambda \in \mathbb{R}\}\\ & =\{(2,3)+(\lambda ,-\lambda ),\lambda \in \mathbb{R}\}\\ & =\{(2+\lambda ,3-\lambda ),\lambda \in \mathbb{R}\}\end{array}$$

• le plan de
  ${\mathbb{R}}^3$ donne par
  $x_1+x_2+x_3=2$
  $(P)$.
  • les points de
    $(P)$ sont les zeros de l'equation
    $x_1+x_2+x_3-2=0$

$$\begin{gathered} x_1+x_2+x_3=2 \\ <\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right),\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)>=2\iff <n,x>=2\text{ avec }\overrightarrow{n}=\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right)\text{ et }\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right) \end{gathered}$$

$(A)=(2,0,0)\in (P)$,

$B=(0,2,0)$,

$C=(0,0,2)\in (P)$

$\overrightarrow{AB}$ et

$\overrightarrow{AC}$,

$\overrightarrow{AB}=(-2,2,0)$,

$\overrightarrow{AC}=(-2,0,2)$

$$\begin{array}{rl}(P)& =(2,0,0)+{\lambda }_1\overrightarrow{AB}+{\lambda }_2\overrightarrow{AC},({\lambda }_1,{\lambda }_2)\in {\mathbb{R}}^2\\ & =(2,0,0)+\{\overrightarrow{x}\in {\mathbb{R}}^3,\overrightarrow{x}={\lambda }_1\overrightarrow{AB}+{\lambda }_2\overrightarrow{AC},({\lambda }_1,{\lambda }_2)\in {\mathbb{R}}^2\}\\ & =(2,0,0)+\{{\lambda }_1(-2,2,0)+{\lambda }_2(-2,0,2),({\lambda }_1,{\lambda }_2)\in {\mathbb{R}}^2\}\\ & =(2,0,0)+\{(-2{\lambda }_1-2{\lambda }_2,2{\lambda }_1,2{\lambda }_2),({\lambda }_1,{\lambda }_2)\in {\mathbb{R}}^2\}\\ & =(2,0,0)+\{(2-2{\lambda }_1-2{\lambda }_2,2{\lambda }_1,{\lambda }_2)({\lambda }_1,{\lambda }_2)\in {\mathbb{R}}^2\}\end{array}$$

Question 2-7

Dessiner le lieu de

${\mathbb{R}}^2$ décrit par les contraintes

$$\left(\begin{array}{cc}-1& 2\\ 1& 1\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)\le \left(\begin{array}{c}-1\\ 1\end{array}\right)$$

• Décrire chacun des composants du lieu géométrique précédent paramétriquement
• Que change le fait de rajouter la contrainte
  $x-3y\le 6$ ?
• Quel lieu correspond à la situation où l’on change le sens de toutes les inégalités ?

On cherche le lieu de

${\mathbb{R}}^2$ definit par

$$\begin{gathered} \left(\begin{array}{cc}-1& 2\\ 1& 1\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)\le \left(\begin{array}{c}-1\\ 1\end{array}\right) \\ \{\begin{array}{l}-x+2y=-1\\ x+y=1\end{array} \\ (D1)=-x+2y=-1\iff \underset{ax+by+c=0}{\underbrace{-x+2y+1}} \\ \overrightarrow{n_1}=\left(\begin{array}{c}-1\\ 2\end{array}\right)\text{ et }\overrightarrow{u_1}=\left(\begin{array}{c}-2\\ -1\end{array}\right) \end{gathered}$$

On a le point particulier

$(0;-\frac{1}{2})$

$$\begin{gathered} (D_2)x+y-1=0 \\ \overrightarrow{n_2}=\left(\begin{array}{c}1\\ 1\end{array}\right)\text{ et }\overrightarrow{u_2}=\left(\begin{array}{c}-1\\ 1\end{array}\right) \end{gathered}$$

On a le point particulier

$(0;1)$