OCVX: TD 1

Lien de la note Hackmd

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= \begin{bmatrix} x_{11} & x_{12}\\ \vdots & \vdots\\ x_{i1} & x_{i2}\\ \vdots & \vdots\\ x_{n1} & x_{n2} \end{bmatrix}\)

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 $\phi$ (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 $\phi$ 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$

\[x,y\in\mathbb R^4, <x,y>=x^Ty=\sum_{i=1}^nx_iy_i\\ \Vert x\Vert=\sqrt{<x,x>}=\sqrt{x^Tx}\\ d(x,y)=\Vert x-y\Vert\\ \theta(x,y)=\arccos(\frac{<x,y>}{\Vert x\Vert\Vert y\Vert})\\ \begin{aligned} <x,y>&=x_1y_1+x_2y_2=\sum_ix_iy_i\\ &= \Vert x\Vert\Vert y\Vert\cos(\theta(x,y)) \end{aligned}\]

$\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 :

\[\begin{pmatrix} 1&2\\ -1&1 \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix}\le \begin{pmatrix} 0\\ 0 \end{pmatrix}\]

ensemble des vecteurs tels que \(\{x\in\mathbb R\vert<x.y>\ge0\}\)

$y\neq0$ et \(\{y\}=\{x\in\mathbb R^2\vert<x.y>=0\}\)

\[\begin{cases} x+2y\le0\\ -x+y\le0 \end{cases}\]

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$:

\(\vec n= \begin{pmatrix} a\\ b \end{pmatrix}\text{ vecteur normal}\\ \vec u= \begin{pmatrix} -b\\ a \end{pmatrix}\text{ vecteur directeur}\\\)

On peut donc en deduire: \(\vec n_1= \begin{pmatrix} 1\\ 2 \end{pmatrix}\text{ vecteur normal}\\ \vec u_1= \begin{pmatrix} -2\\ 1 \end{pmatrix}\text{ vecteur directeur}\\\)

On cherche le demi-plan oriente negativement par rapport a: \(<\vec n_1,\begin{pmatrix} x\\ y \end{pmatrix}>\le0\)

Prenons la seconde equation et faisons de meme \(-x+y=0\\ \vec n_2= \begin{pmatrix} -1\\ 1 \end{pmatrix}\text{ vecteur normal}\\ \vec u_2= \begin{pmatrix} -1\\ -1 \end{pmatrix}\text{ vecteur directeur}\\\)

L’intersection des 2 espaces verifie les 2 inegalites.

Question 1-3

Représenter le lieu de $\mathbb R^3$ décrit par la relations $x_1 +x_2 +x_3 \ge 0$.

On cherche:

\(\begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix}\in\mathbb R^3\\\) tel que $x_1 +x_2 +x_3 \ge 0$ \(<\begin{pmatrix} 1\\ 1\\ 1 \end{pmatrix},\begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix}>\ge0\)

On va chercher le lieu de $\mathbb R^3$ ou $<\vec n.\vec x>=\vec n^T\vec 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{aligned} (D)&=\{x\in\mathbb R^2,x=\lambda u,\lambda\in\mathbb R\}\\ &= \{\lambda\vec u,\lambda\in\mathbb R\} \text{ representation parametrique}\\ &= \{\vec x\in\mathbb R^2,<\vec n,\vec x>=0\}\\ &=\{n^Tx=0\}\\ &=\{n_1x_1+n_2x_2=0\} = \text{ representation implicite}\\ \end{aligned}\\ n=\begin{pmatrix} n_1\\ n_2\\ \end{pmatrix}\\ x=\begin{pmatrix} x_1\\ x_2\\ \end{pmatrix}\]

$(A)=x+(0,1)$ la droite qui passe par $(0,1)$ et de vecteur directeur $\vec u$

\[\begin{aligned} (A)&=(0,1)+(D) = (0,1)+\{\lambda\vec u,\lambda\in\mathbb R\} \text{ avec } \vec u=\begin{pmatrix} u_1\\ u_2\\ \end{pmatrix}\\ &= (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{aligned}\] \[\vec n^{\perp}x=c\Rightarrow n_1x+n_2y=c\\ \Rightarrow ax+by+c=0\]

On obtient l’equation implicite d’une droite affine. \(\rightarrow \vec n = \begin{pmatrix} a\\ b\\ \end{pmatrix} \text{ et }\vec u = \begin{pmatrix} -b\\ a\\ \end{pmatrix} \text{ et passant par } (0,-\frac{c}{b})\)

Ecriture parametrique de:

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

\[\begin{aligned} (A) &= (2,3)+\{\vec x\in\mathbb R^2, \vec x=\lambda\vec 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{aligned}\]

• 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$

\[x_1+x_2+x_3=2\\ <\begin{pmatrix} 1\\ 1\\ 1 \end{pmatrix}, \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix}>=2\Leftrightarrow<n,x>=2 \text{ avec } \vec n=\begin{pmatrix} 1\\ 1\\ 1 \end{pmatrix}\text{ et }\begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix}\]

$(A)=(2,0,0)\in(P)$, $B=(0,2,0)$, $C=(0,0,2)\in(P)$ $\vec{AB}$ et $\vec{AC}$, $\vec{AB}=(-2,2,0)$, $\vec{AC}=(-2,0,2)$

\[\begin{aligned} (P) &= (2,0,0)+\lambda_1\vec{AB}+\lambda_2\vec{AC}, (\lambda_1,\lambda_2)\in\mathbb R^2\\ &= (2,0,0)+\{\vec{x}\in\mathbb R^3,\vec{x}=\lambda_1\vec{AB}+\lambda_2\vec{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-2\lambda_1-2\lambda_2,2\lambda_1,\lambda_2) (\lambda_1,\lambda_2)\in\mathbb R^2\} \end{aligned}\]

Question 2-7

Dessiner le lieu de $\mathbb R^2$ décrit par les contraintes

\[\begin{pmatrix} -1 & 2\\ 1 & 1\\ \end{pmatrix} \begin{pmatrix} x\\ y\\ \end{pmatrix}\le \begin{pmatrix} -1\\ 1\\ \end{pmatrix}\]

• 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{pmatrix} -1 & 2\\ 1 & 1\\ \end{pmatrix} \begin{pmatrix} x\\ y\\ \end{pmatrix}\le \begin{pmatrix} -1\\ 1\\ \end{pmatrix}\\ \begin{cases} -x+2y=-1\\ x+y=1 \end{cases}\\ (D1)=-x+2y=-1\Leftrightarrow \underbrace{-x+2y+1}_{ax+by+c=0}=0\\ \vec{n_1} = \begin{pmatrix} -1\\ 2\\ \end{pmatrix} \text{ et } \vec{u_1} = \begin{pmatrix} -2\\ -1\\ \end{pmatrix}\]

On a le point particulier $(0;-\frac{1}{2})$

\[(D_2)= x+y-1=0\\ \vec{n_2} = \begin{pmatrix} 1\\ 1\\ \end{pmatrix} \text{ et } \vec{u_2} = \begin{pmatrix} -1\\ 1\\ \end{pmatrix}\]

On a le point particulier $(0;1)$