Principes de base de la régression linéaire

Bonjour, Habr!



Le but de cet article est de parler de régression linéaire, c'est-à-dire de recueillir et de montrer les formulations et interprétations du problème de régression en termes d'analyse mathématique, statistique, algèbre linéaire et théorie des probabilités. Bien que les manuels définissent ce sujet de manière stricte et exhaustive, un autre article scientifique populaire ne fera pas de mal.



! Attention au trafic! L'article contient un nombre notable d'images pour les illustrations, certaines au format gif.

Contenu

• introduction
• Méthode des moindres carrés
  • Analyse mathematique
  • Statistiques
  • Théorie des probabilités
• Régression multilinéaire
  • Algèbre linéaire
• Base arbitraire
• Remarques finales
  • Problème de sélection de dimension
  • Méthodes numériques
• Publicité et conclusion

introduction

Il existe trois concepts similaires, trois sœurs: l'interpolation, l'approximation et la régression.

Ils ont un objectif commun: à partir d'une famille de fonctions, choisissez celle qui possède une certaine propriété.





Interpolation- un moyen de sélectionner dans une famille de fonctions celle qui passe par les points donnés. La fonction est alors généralement utilisée pour calculer aux points intermédiaires. Par exemple, nous définissons manuellement la couleur sur plusieurs points et voulons que les couleurs des points restants forment des transitions douces entre les points donnés. Ou nous définissons des images clés pour l'animation et souhaitons des transitions fluides entre elles. Exemples classiques: interpolation polynomiale de Lagrange, interpolation spline, interpolation multidimensionnelle (bilinéaire, trilinéaire, plus proche voisin, etc.). Il existe également un concept lié d'extrapolation - prédire le comportement d'une fonction en dehors d'un intervalle. Par exemple, prédire le taux du dollar en fonction des fluctuations précédentes est une extrapolation.



Approximation- une manière de choisir dans une famille de fonctions "simples" une approximation pour une fonction "complexe" sur un segment, alors que l'erreur ne doit pas dépasser une certaine limite. L'approximation est utilisée lorsque vous avez besoin d'obtenir une fonction similaire à une fonction donnée, mais plus pratique pour les calculs et les manipulations (différenciation, intégration, etc.). Lors de l'optimisation de sections critiques du code, une approximation est souvent utilisée: si la valeur d'une fonction est calculée plusieurs fois par seconde et qu'une précision absolue n'est pas nécessaire, alors un approximant plus simple avec un «coût» de calcul inférieur peut être supprimé. Les exemples classiques incluent les séries de Taylor sur un segment, l'approximation polynomiale orthogonale, l'approximation de Padé, l'approximation sinusoïdale de Bhaskar, etc.



Régression- une manière de choisir parmi une famille de fonctions celle qui minimise la fonction de perte. Ce dernier caractérise dans quelle mesure la fonction d'essai s'écarte des valeurs aux points donnés. Si des points sont obtenus dans une expérience, ils contiennent inévitablement une erreur de mesure, du bruit, il est donc plus raisonnable d'exiger que la fonction transmette la tendance générale, et ne passe pas exactement par tous les points. Dans un sens, la régression est un «ajustement interpolant»: nous voulons dessiner la courbe aussi près que possible des points et la garder aussi simple que possible pour capturer la tendance globale. La fonction de perte (dans la littérature anglaise «loss function» ou «cost function») est responsable de l'équilibre entre ces désirs contradictoires.



Dans cet article, nous examinerons la régression linéaire. Cela signifie que la famille de fonctions dans laquelle nous choisissons est une combinaison linéaire de fonctions de base prédéterminées$$${f_i}$

$$

$$f = \sum_i w_i f_i.$$

Le but de la régression est de trouver les coefficients de cette combinaison linéaire, et ainsi de déterminer la fonction de régression $$$f$(également appelé un modèle ). Notez que la régression linéaire est appelée linéaire précisément en raison de la combinaison linéaire des fonctions de base - cela n'est pas lié aux fonctions les plus élémentaires (elles peuvent être linéaires ou non).



La régression est avec nous depuis longtemps: la méthode a été publiée pour la première fois par Legendre en 1805, bien que Gauss y soit venu plus tôt et l'utilise avec succès pour prédire l'orbite de la "comète" (en fait une planète naine) Cérès. Il existe de nombreuses variantes et généralisations de la régression linéaire: CONTRE, Moindres carrés, Régression Ridge, Régression Lasso, ElasticNet, et bien d'autres.

Méthode des moindres carrés

Commençons par le cas bidimensionnel le plus simple. Donnons-nous des points dans l'avion$$$\{(x_1,y_1),\cdots,(x_N,y_N)\}$ et nous recherchons une telle fonction affine

$$

$$f(x) = a + b \cdot x,$$

afin que son graphe soit le plus proche des points. Ainsi, notre base se compose d'une fonction constante et d'un linéaire$$$(1, x)$...



Comme vous pouvez le voir sur l'illustration, la distance d'un point à une ligne droite peut être comprise de différentes manières, par exemple, géométriquement - c'est la longueur d'une perpendiculaire. Cependant, dans le cadre de notre tâche, nous avons besoin d'une distance fonctionnelle et non géométrique. Nous nous intéressons à la différence entre la valeur expérimentale et la prédiction du modèle pour chaque$$$x_i,$ par conséquent, vous devez mesurer le long de l'axe $$$y$...



La première chose qui me vient à l'esprit est d'essayer une expression qui dépend des valeurs absolues des différences en tant que fonction de perte$$$|f(x_i) - y_i|$... L'option la plus simple est la somme des modules d'écart$$$\sum_i |f(x_i) - y_i|$entraîne une régression de la distance la moins absolue (LAD).



Cependant, la fonction de perte la plus populaire est la somme des carrés des écarts du régressant par rapport au modèle. Dans la littérature anglaise, on l'appelle Sum of Squared Errors (SSE)

$$

$$\text{SSE}(a,b)=\text{SS}_{res[iduals]}=\sum_{i=1}^N{\text{}_i}^2=\sum_{i=1}^N(y_i-f(x_i))^2=\sum_{i=1}^N(y_i-a-b\cdot x_i)^2,$$

Moindres carrés (OLS) - Régression linéaire avec $$$\text{SSE}(a,b)$ comme une fonction de perte.



Ce choix est avant tout pratique: la dérivée d'une fonction quadratique est une fonction linéaire, et les équations linéaires sont facilement résolues. Cependant, j'indiquerai en outre d'autres considérations en faveur de$$$\text{SSE}(a,b)$...

Analyse mathematique

Le moyen le plus simple de trouver $$$\text{argmin}_{a,b} \, \text{SSE}(a,b)$ - calculer des dérivées partielles par rapport à $$$a$ et $$$b$, assimilez-les à zéro et résolvez le système d'équations linéaires

$$

$$\begin{aligned} \frac{\partial}{\partial a}\text{SSE}(a,b)&=-2\sum_{i=1}^N(y_i-a-bx_i), \\ \frac{\partial}{\partial b}\text{SSE}(a,b)&=-2\sum_{i=1}^N(y_i-a-bx_i)x_i. \end{aligned}$$

Les valeurs des paramètres qui minimisent la fonction de perte satisfont les équations

$$

$$\begin{aligned} 0 &= -2\sum_{i=1}^N(y_i-\hat{a}-\hat{b}x_i), \\ 0 &= -2\sum_{i=1}^N(y_i-\hat{a}-\hat{b}x_i)x_i, \end{aligned}$$

qui sont faciles à résoudre

$$

$$\begin{aligned} \hat{a}&=\frac{\sum_i y_i}{N}-\hat{b}\frac{\sum_i x_i}{N},\\ \hat{b}&=\frac{\frac{\sum_i x_i y_i}{N}-\frac{\sum_i x_i\sum_i y_i}{N^2}}{\frac{\sum_i x_i^2}{N}-\left(\frac{\sum_i x_i^2}{N}\right)^2}. \end{aligned}$$

Nous avons des expressions peu maniables et non structurées. Nous allons maintenant les ennoblir et leur insuffler un sens.

Statistiques

Les formules résultantes peuvent être rédigées de manière compacte à l'aide d'estimateurs statistiques: moyenne $$$\langle{\cdot}\rangle$, variations $$$\sigma_{\cdot}$ (écart-type), covariance $$$\sigma({\cdot},{\cdot})$ et corrélations $$$\rho({\cdot},{\cdot})$

$$

$$\begin{aligned} \hat{a}&=\langle{y}\rangle-\hat{b}\langle{x}\rangle, \\ \hat{b}&=\frac{\langle{xy}\rangle-\langle{x}\rangle\langle{y}\rangle}{\langle{x^2}\rangle-\langle{x}\rangle^2}. \end{aligned}$$

Réécrivons $$$\hat{b}$ comme

$$

$$\hat{b} = \frac{\sigma(x,y)}{\sigma_x^2},$$

Où $$$\sigma_x$ est l'écart type de l'échantillon non corrigé (biaisé), et $$$\sigma(x,y)$- covariance. Rappelez-vous maintenant que le coefficient de corrélation (coefficient de corrélation de Pearson)

$$

$$\rho(x,y)=\frac{\sigma(x,y)}{\sigma_x \sigma_y}$$

et écris

$$

$$\hat{b}=\rho(x,y)\frac{\sigma_y}{\sigma_x}.$$

Maintenant, nous pouvons apprécier toute l'élégance des statistiques descriptives en écrivant l'équation de la droite de régression comme celle-ci

$$

$$\boxed{y-\langle {y} \rangle = \rho(x,y)\frac{\sigma_y}{\sigma_x}(x-\langle {x} \rangle)}.$$

Premièrement, cette équation indique immédiatement deux propriétés de la droite de régression:

• la ligne droite passe par le centre de gravité $$$(\langle{x}\rangle, \langle{y}\rangle)$;
• si le long de l'axe $$$x$ par unité de longueur choisir $$$\sigma_x$, et le long de l'axe $$$y$ - $$$\sigma_y$, alors l'angle d'inclinaison de la ligne droite sera de $$$-45^\circ$ avant $$$45^\circ$... Cela est dû au fait que$$$-1 \leq\rho(x,y)\leq 1$...

Deuxièmement, on comprend maintenant pourquoi la méthode de régression est appelée ainsi. En unités d'écart type$$$y$ s'écarte de sa moyenne de moins de $$$x$, parce que $$$|\rho(x,y)|\leq1$... C'est ce qu'on appelle la régression (du latin regressus - "retour") par rapport à la moyenne. Ce phénomène a été décrit par Sir Francis Galton à la fin du 19e siècle dans son article «Regression to Mediocrity in the Inheritance of Growth». L'article montre que les traits (comme la hauteur) qui s'écartent fortement de la moyenne sont rarement hérités. Les caractéristiques de la progéniture semblent tendre vers la moyenne - la nature repose sur les enfants des génies.



En mettant au carré le coefficient de corrélation, on obtient le coefficient de détermination$$$R = \rho^2$... Le carré de cette mesure statistique montre dans quelle mesure le modèle de régression s'adapte aux données.$$$R^2$égal à $$$1$, signifie que la fonction s'adapte parfaitement à tous les points - les données sont parfaitement corrélées. On peut prouver que$$$R^2$montre dans quelle mesure la variance des données est due au meilleur modèle linéaire. Pour comprendre ce que cela signifie, nous introduisons les définitions

$$

$$\begin{aligned} \text{Var}_{data} &= \frac{1}{N}\sum_i (y_i-\langle y \rangle)^2, \\ \text{Var}_{res} &= \frac{1}{N} \sum_i (y_i-\text{}(x_i))^2, \\ \text{Var}_{reg} &= \frac{1}{N} \sum_i (\text{}(x_i)-\langle y \rangle)^2. \end{aligned}$$

$$$\text{Var}_{data}$ - variation des données initiales (variation des points $$$y_i$).



$$$\text{Var}_{res}$ - variation des résidus, c'est-à-dire variation des écarts par rapport au modèle de régression - de $$$y_i$ vous devez soustraire la prédiction du modèle et trouver la variation.



$$$\text{Var}_{reg}$ - variation de régression, c'est-à-dire variation des prédictions du modèle de régression en points $$$x_i$ (notez que la moyenne des prédictions du modèle correspond à $$$\langle y \rangle$).



Le fait est que la variation des données d'origine est décomposée en la somme de deux autres variations: la variation expliquée par le modèle, et la variation du bruit aléatoire (résidus)

$$

$$\boxed{{\color{red}{\text{Var}_{data}}} ={\color{green}{\text{Var}_{res}}}+ {\color{blue}{\text{Var}_{reg}}}.}$$

ou

$$

$$\sigma^2_{data} =\sigma^2_{res}+ \sigma^2_{reg}.$$

Comme vous pouvez le voir, les écarts types forment un triangle rectangle.





Nous nous efforçons de nous débarrasser de la variabilité associée au bruit et de ne laisser que la variabilité expliquée par le modèle - nous voulons séparer le blé de l'ivraie. La mesure dans laquelle le meilleur des modèles linéaires a réussi est attestée par$$$R^2$égal à un moins la fraction de la variation d'erreur dans la variation totale

$$

$$R^2=\frac{\text{Var}_{data}-\text{Var}_{res}}{\text{Var}_{data}}=1-\frac{\color{green}{\text{Var}_{res}}}{\color{red}{\text{Var}_{data}}}$$

ou la proportion de variation expliquée (proportion de la variation de régression dans la variation totale)

$$

$$R^2=\frac{\color{blue}{\text{Var}_{reg}}}{\color{red}{\text{Var}_{data}}}.$$

$$$R$ égal au cosinus d'un angle dans un triangle rectangle $$$(\sigma_{data}, \sigma_{reg}, \sigma_{res})$... À propos, parfois une fraction de la variation inexpliquée est introduite $$$FUV=1-R^2$et il est égal au carré du sinus dans ce triangle. Si le coefficient de détermination est petit, nous avons peut-être choisi des fonctions de base infructueuses, la régression linéaire n'est pas du tout applicable, etc.

Théorie des probabilités

Plus tôt, nous sommes arrivés à la fonction de perte $$$\text{SSE}(a,b)$pour des raisons de commodité, mais il peut également être atteint en utilisant la théorie des probabilités et la méthode du maximum de vraisemblance (MMP). Permettez-moi de rappeler brièvement son essence. Supposons que nous ayons$$$N$variables aléatoires indépendantes à distribution identique (dans notre cas, résultats de mesure). Nous connaissons la forme de la fonction de distribution (par exemple, la distribution normale), mais nous voulons déterminer les paramètres qui y sont inclus (par exemple$$$\mu$ et $$$\sigma$). Pour ce faire, vous devez calculer la probabilité d'obtenir$$$N$points de données sous l'hypothèse de paramètres constants, mais inconnus. Du fait de l'indépendance des mesures, on obtient le produit des probabilités de réalisation de chaque dimension. Si nous pensons à la valeur résultante en fonction de paramètres (fonction de vraisemblance) et trouvons son maximum, nous obtenons une estimation des paramètres. Souvent, au lieu de la fonction de vraisemblance, ils utilisent son logarithme - il est plus facile de le différencier, mais le résultat est le même.



Revenons au simple problème de régression. Disons que les valeurs$$$x$ nous savons exactement, mais dans la mesure $$$y$il y a un bruit aléatoire (propriété exogène faible ). De plus, nous supposons que tous les écarts par rapport à la ligne droite (propriété de linéarité ) sont causés par du bruit avec une distribution constante ( distribution constante ). Puis

$$

$$y = a + bx + \epsilon,$$

Où $$$\epsilon$ - variable aléatoire normalement distribuée

$$

$$\epsilon \sim \mathcal{N}(0,\,\sigma^{2}), \qquad p(\epsilon) = \frac{1}{\sqrt{2 \pi \sigma^2}} e^{-\frac{\epsilon^2}{2\sigma^2}}.$$

Sur la base des hypothèses ci-dessus, nous écrivons la fonction de vraisemblance

$$

$$\begin{aligned} L(a,b|\mathbf{y})&=P(\mathbf{y}|a,b)=\prod_i P(y_i|a,b)=\prod_i p(y_i-a-bx|a,b)=\\ &= \prod_i \frac{1}{\sqrt{2 \pi \sigma^2}} e^{-\frac{(y_i-a-bx)^2}{2\sigma^2}}= \frac{1}{\sqrt{2 \pi \sigma^2}}e^{-\frac{\sum_i (y_i-a-bx)^2}{2 \sigma^2}}=\\ &= \frac{1}{\sqrt{2 \pi \sigma^2}}e^{-\frac{\text{SSE}(a,b)}{2 \sigma^2}} \end{aligned}$$

et son logarithme

$$

$$l(a,b|\mathbf{y})=\log{L(a,b|\mathbf{y})}=-\text{SSE}(a,b)+const.$$

Ainsi, le maximum de vraisemblance est atteint au minimum $$$\text{SSE}$

$$

$$(\hat{a},\hat{b})=\text{argmax}_{a,b} \, l(a,b|\mathbf{y}) = \text{argmin}_{a,b} \, \text{SSE}(a,b),$$

ce qui donne des raisons de l'accepter comme une fonction de perte. Au fait, si

$$

$$\begin{aligned} \epsilon \sim \text{Laplace}(0, \alpha), \qquad p_{L}(\epsilon; \mu, \alpha) =\frac{\alpha}{2}e^{-\alpha |\epsilon-\mu|} \end{aligned}$$

nous obtenons la fonction de perte de régression LAD

$$

$$E_{LAD}(a,b)=\sum_i |y_i-a-bx_i|,$$

dont nous avons parlé plus tôt.



L'approche que nous avons utilisée dans cette section est une approche possible. Il est possible d'obtenir le même résultat en utilisant des propriétés plus générales. En particulier, la propriété de constance de distribution peut être affaiblie en la remplaçant par les propriétés d'indépendance, de constance de variation (homoscédasticité) et d'absence de multicolinéarité. En outre, au lieu de l'estimation MMP, vous pouvez utiliser d'autres méthodes, par exemple l'estimation MMSE linéaire.

Régression multilinéaire

Jusqu'à présent, nous avons considéré le problème de régression pour une caractéristique scalaire $$$x$, mais généralement le régresseur est $$$n$-vecteur dimensionnel $$$\mathbf{x}$... En d'autres termes, pour chaque dimension, nous enregistrons$$$n$fonctionnalités, en les combinant dans un vecteur. Dans ce cas, il est logique d'accepter le modèle avec$$$n+1$ fonctions de base indépendantes de l'argument vectoriel - $$$n$ les degrés de liberté correspondent $$$n$ fonctionnalités et un autre - régressant $$$y$... Le choix le plus simple est celui des fonctions de base linéaires$$$(1, x_1, \cdots, x_n)$... Quand$$$n = 1$ nous obtenons la base déjà familière $$$(1, x)$...



Donc, nous voulons trouver un tel vecteur (ensemble de coefficients)$$$\mathbf{w}$, quelle

$$

$$\sum_{j=0}^n w_j x_j^{(i)}= \mathbf{w}^{\top}\mathbf{x}^{(i)} \simeq y_i, \qquad \qquad \qquad \qquad i=1\dots N.$$

Signe "$$$\simeq$"signifie que nous recherchons une solution qui minimise la somme des carrés des erreurs

$$

$$\hat{\mathbf{w}}=\text{argmin}_\mathbf{w} \, \sum_{i=1}^N \left({y_i - \mathbf{w}^{\top}\mathbf{x}^{(i)}}\right)^2$$

La dernière équation peut être réécrite d'une manière plus pratique. Pour cela nous plaçons$$$\mathbf{x}^{(i)}$ en lignes de matrice (matrice d'information)

$$

$$X= \begin{pmatrix} - & \mathbf{x}^{(1)\top} & - \\ \cdots & \cdots & \cdots\\ - & \mathbf{x}^{(N)\top} & - \end{pmatrix} = \begin{pmatrix} | & | & & | \\ \mathbf{x}_0 & \mathbf{x}_1 & \cdots & \mathbf{x}_n \\ | & | & & | \end{pmatrix} = \begin{pmatrix} 1 & x^{(1)}_{1} & \cdots & x^{(1)}_{n} \\ \cdots & \cdots & \cdots & \cdots\\ 1 & x^{(N)}_{1} & \cdots & x^{(N)}_{n} \end{pmatrix}.$$

Puis les colonnes de la matrice $$$\mathbf{x}_{i}$ répondre aux mesures $$$i$-th caractéristique. Il est important de ne pas se confondre ici:$$$N$ - le nombre de mesures, $$$n$- le nombre de signes (caractéristiques) que nous enregistrons. Le système peut être écrit comme

$$

$$X \, \mathbf{w} \simeq \mathbf{y}.$$

Le carré de la norme de la différence entre les vecteurs sur les côtés droit et gauche de l'équation forme la fonction de perte

$$

$$\text{SSE}(\mathbf{w}) = {\|\mathbf{y}-X \mathbf{w}\|}^2, \qquad \qquad \mathbf{w} \in \mathbb{R}^{n+1}; \, \mathbf{y} \in \mathbb{R}^{N},$$

que nous entendons minimiser

$$

$$\begin{aligned} \hat{\mathbf{w}}&=\text{argmin}_\mathbf{w} \, \text{SSE}(\mathbf{w}) = \text{argmin}_\mathbf{w} \, (\mathbf{y}-X \mathbf{w})^{\top}(\mathbf{y}-X \mathbf{w})=\\ &= \text{argmin}_\mathbf{w} \,(\mathbf{y}^{\top}\mathbf{y}-2\mathbf{w}^{\top}X^{\top}\mathbf{y}+\mathbf{w}^{\top}X^{\top}X\mathbf{w}). \end{aligned}$$

Différencions l'expression finale par $$$\mathbf{w}$(si vous avez oublié comment le faire, jetez un œil au livre de recettes Matrix )

$$

$$\frac{\partial \, \text{SSE}(\mathbf{w})}{\partial \mathbf{w}}=-2 X^{\top}\mathbf{y}+2 X^{\top}X\mathbf{w},$$

assimiler le dérivé à $$$\mathbf{0}$et nous obtenons le soi-disant. équations normales

$$

$$X^{\top}X \, \hat{\mathbf{w}}=X^{\top}\mathbf{y}.$$

Si les colonnes de la matrice d'informations $$$X$ sont linéairement indépendants (il n'y a pas de caractéristiques parfaitement corrélées), alors la matrice $$$X^{\top}X$a le contraire (la preuve peut être vue, par exemple, dans la vidéo de l'académie de Khan ). Ensuite, nous pouvons écrire

$$

$$\boxed{\hat{\mathbf{w}} = (X^{\top}X)^{-1}X^{\top}\mathbf{y}=X^{+}\mathbf{y}},$$

Où

$$

$$X^{+}=(X^{\top}X)^{-1}X^{\top}$$

pseudo-inverse à $$$X$... Le concept de matrice pseudo-inverse a été introduit en 1903 par Fredholm et a joué un rôle important dans les travaux de Moore et Penrose.



Laisse moi te rappeler quoi tourner$$$X^{\top}X$ et trouve $$$X^{+}$ seulement possible si les colonnes $$$X$sont linéairement indépendants. Cependant, si les colonnes$$$X$ proche de la dépendance linéaire, calcul $$$(X^{\top}X)^{-1}$devient déjà numériquement instable. Le degré de dépendance linéaire des caractéristiques dans$$$X$ou, comme on dit, la multicolinéarité de la matrice$$$X^{\top}X$, peut être mesuré par le nombre de conditionnalité - le rapport de la valeur propre maximale au minimum. Plus il est gros, plus il est proche$$$X^{\top}X$ calcul dégénéré et instable de la pseudo-inverse.

Algèbre linéaire

La solution au problème de la régression multilinéaire peut être atteinte tout naturellement à l'aide de l'algèbre linéaire et de la géométrie, car même le fait que la norme du vecteur d'erreur apparaisse dans la fonction de perte laisse déjà entendre que le problème a un côté géométrique. Nous avons vu qu'une tentative de trouver un modèle linéaire décrivant les points expérimentaux conduit à l'équation

$$

$$X \, \mathbf{w} \simeq \mathbf{y}.$$

Si le nombre de variables est égal au nombre d'inconnues et que les équations sont linéairement indépendantes, alors le système a une solution unique. Cependant, si le nombre de dimensions dépasse le nombre d'entités, c'est-à-dire qu'il y a plus d'équations que d'inconnues, le système devient incohérent, surdéterminé. Dans ce cas, le mieux que nous puissions faire est de choisir le vecteur$$$\mathbf{w}$dont l'image $$$X\mathbf{w}$ le plus proche de $$$\mathbf{y}$... Permettez-moi de vous rappeler que de nombreuses images ou espace de colonne$$$\mathcal{C}(X)$ Est une combinaison linéaire des vecteurs colonnes de la matrice $$$X$

$$

$$\begin{pmatrix} | & | & & | \\ \mathbf{x}_0 & \mathbf{x}_1 & \cdots & \mathbf{x}_n \\ | & | & & | \end{pmatrix} \mathbf{w} = w_0 \mathbf{x}_0 + w_1 \mathbf{x}_1 + \cdots w_n \mathbf{x}_n .$$

$$$\mathcal{C}(X)$ - $$$n+1$-Sous-espace linéaire dimensionnel (nous considérons les entités linéairement indépendantes), étendue linéaire des vecteurs colonnes $$$X$... Donc si$$$\mathbf{y}$ fait parti $$$\mathcal{C}(X)$, alors nous pouvons trouver une solution, sinon, nous chercherons, pour ainsi dire, le meilleur des non résolus.



Si en plus des vecteurs$$$\mathcal{C}(X)$ nous considérons tous les vecteurs perpendiculaires à eux, puis nous obtenons un sous-espace supplémentaire et nous pouvons tout vecteur de $$$\mathbb{R}^{N}$se décomposer en deux composants, dont chacun vit dans son propre sous-espace. Le second espace perpendiculaire peut être caractérisé comme suit (nous en aurons besoin plus tard). Laisser aller$$$\mathbf{v} \in \mathbb{R}^{N}$puis

$$

$$X^\top \mathbf{v} = \begin{pmatrix} - & \mathbf{x}_0^{\top} & - \\ \cdots & \cdots & \cdots\\ - & \mathbf{x}_n^{\top} & - \end{pmatrix} \mathbf{v} = \begin{pmatrix} \mathbf{x}_0^{\top} \cdot \mathbf{v} \\ \cdots \\ \mathbf{x}_n^{\top} \cdot \mathbf{v} \\ \end{pmatrix}$$

vaut zéro si et seulement si $$$\mathbf{v}$ perpendiculaire à tout $$$\mathbf{x}_i$, et donc le tout $$$\mathcal{C}(X)$... Ainsi, nous avons trouvé deux sous-espaces linéaires perpendiculaires, combinaisons linéaires de vecteurs dont complètement, sans trous, «recouvrent» tout$$$\mathbb{R}^N$... Ceci est parfois désigné par le symbole de somme directe orthogonale





Où $$$\text{ker}(X^{\top})=\{\mathbf{v}|X^{\top}\mathbf{v}=\mathbf{0}\}$... Chacun des sous-espaces peut être atteint en utilisant l'opérateur de projection correspondant, mais plus d'informations ci-dessous.



Maintenant imaginons $$$\mathbf{y}$ décomposition

$$

$$\mathbf{y} = \mathbf{y}_{\text{proj}} + \mathbf{y}_{\perp}, \qquad \mathbf{y}_{\text{proj}} \in \mathcal{C}(X), \qquad \mathbf{y}_{\perp} \in \text{ker}(X^{\top}).$$

Si nous recherchons une solution $$$\hat{\mathbf{w}}$, alors il est naturel d'exiger que $$$|| \mathbf{y} - X\mathbf{w} ||$était minime, car c'est la longueur du vecteur de reste. Considérant la perpendicularité des sous-espaces et le théorème de Pythagore

$$

$$\text{argmin}_\mathbf{w} || \mathbf{y} - X\mathbf{w} || = \text{argmin}_\mathbf{w} || \mathbf{y}_{\perp} + \mathbf{y}_{\text{proj}} - X\mathbf{w} || = \text{argmin}_\mathbf{w} \sqrt{|| \mathbf{y}_{\perp} ||^2 + || \mathbf{y}_{\text{proj}} - X\mathbf{w} ||^2},$$

mais depuis le choix d'un convenable $$$\mathbf{w}$, Je peux obtenir n'importe quel vecteur d'espace de colonne, alors le problème est réduit à

$$

$$X\hat{\mathbf{w}} = \mathbf{y}_{\text{proj}},$$

et $$$\mathbf{y}_{\perp}$restera comme une erreur fatale. Tout autre choix$$$\hat{\mathbf{w}}$ ne fera que faire plus l'erreur.



Si nous nous en souvenons maintenant $$$X^{\top} \mathbf{y}_{\perp} = \mathbf{0}$alors c'est facile à voir

$$

$$X^\top X \mathbf{w} = X^{\top} \mathbf{y}_{\text{proj}} = X^{\top} \mathbf{y}_{\text{proj}} + X^{\top} \mathbf{y}_{\perp} = X^{\top} \mathbf{y},$$

ce qui est très pratique, car $$$\mathbf{y}_{\text{proj}}$ nous n'avons pas, mais $$$\mathbf{y}$- il y a. Rappelez-vous de la section précédente que$$$X^{\top} X$ a l'inverse sous la condition d'indépendance linéaire des traits et écrit la solution

$$

$$\mathbf{w} = (X^\top X)^{-1} X^\top \mathbf{y} = X^{+} \mathbf{y},$$

Où $$$X^{+}$la matrice pseudo-inverse déjà familière. Si nous sommes intéressés par la projection$$$\mathbf{y}_{\text{proj}}$, alors nous pouvons écrire

$$

$$\mathbf{y}_{\text{proj}} = X \mathbf{w} = X X^{+} \mathbf{y} = \text{Proj}_X \mathbf{y},$$

Où $$$\text{Proj}_X$- opérateur de projection sur l'espace colonne.



Clarifions la signification géométrique du coefficient de détermination.



Notez que le vecteur violet $$$\bar{y} \cdot \boldsymbol{1}=\bar{y} \cdot (1,1,\dots,1)^{\top}$ proportionnel à la première colonne de la matrice d'information $$$X$, qui se compose d'une unité selon notre choix de fonctions de base. Dans le triangle RVB

$$

$${\color{red}{\mathbf{y}-\hat{y} \cdot \boldsymbol{1}}}={\color{green}{\mathbf{y}-\bar{\mathbf{y}}}}+{\color{blue}{\hat{\mathbf{y}}-\bar{y} \cdot \boldsymbol{1}}}.$$

Puisque ce triangle est rectangulaire, alors par le théorème de Pythagore

$$

$${\color{red}{\|\mathbf{y}-\hat{y} \cdot \boldsymbol{1}\|^2}}={\color{green}{\|\mathbf{y}-\bar{\mathbf{y}}\|^2}}+{\color{blue}{\|\hat{\mathbf{y}}-\bar{y} \cdot \boldsymbol{1}\|^2}}.$$

Il s'agit d'une interprétation géométrique du fait déjà connu que

$$

$${\color{red}{\text{Var}_{data}}} = {\color{green}{\text{Var}_{res}}}+{\color{blue}{\text{Var}_{reg}}}.$$

Nous savons que

$$

$$R^2=\frac{\color{blue}{\text{Var}_{reg}}}{\color{red}{\text{Var}_{data}}},$$

ce qui signifie

$$

$$R=\cos{\theta}.$$

Nice, n'est-ce pas?

Base arbitraire

Comme nous le savons, la régression est effectuée sur des fonctions de base $$$f_i$ et son résultat est le modèle

$$

$$f = \sum_i w_i f_i,$$

mais jusqu'à présent, nous avons utilisé le plus simple $$$f_i$qui ont simplement relayé les fonctionnalités d'origine sans changements, enfin, sauf qu'ils les ont complétées avec des fonctionnalités constantes $$$f_0(\mathbf{x}) = 1$... Comme vous pouvez le voir, en fait, aucun genre$$$f_i$, ni leur nombre n'est limité par quoi que ce soit - l'essentiel est que les fonctions de la base soient linéairement indépendantes. Habituellement, le choix est fait sur la base d'hypothèses sur la nature du processus que nous modélisons. Si nous avons des raisons de croire que les points$$$\{(x_1,y_1),\cdots,(x_N,y_N)\}$ tomber sur une parabole et non sur une ligne droite, alors il vaut la peine de choisir une base $$$(1, x, x^2)$... Le nombre de fonctions de base peut être inférieur ou supérieur au nombre de fonctionnalités d'origine.



Si nous avons décidé sur la base, nous procédons comme suit. Nous formons une matrice d'informations

$$

$$\Phi = \begin{pmatrix} - & \boldsymbol{f}^{(1)\top} & - \\ \cdots & \cdots & \cdots\\ - & \boldsymbol{f}^{(N)\top} & - \end{pmatrix} = \begin{pmatrix} {f}_{0}\left(\mathbf{x}^{(1)}\right) & {f}_{1}\left(\mathbf{x}^{(1)}\right) & \cdots & {f}_{n}\left(\mathbf{x}^{(1)}\right) \\ \cdots & \cdots & \cdots & \cdots\\ {f}_{0}\left(\mathbf{x}^{(N)}\right) & {f}_{1}\left(\mathbf{x}^{(N)}\right) & \cdots & {f}_{n}\left(\mathbf{x}^{(N)}\right) \end{pmatrix},$$

écrire la fonction de perte

$$

$$E(\mathbf{w})={\|{\boldsymbol{\epsilon}}(\mathbf{w})\|}^2={\|\mathbf{y}-\Phi \, \mathbf{w}\|}^2$$

et trouver son minimum, par exemple, en utilisant la matrice pseudo-inverse

$$

$$\hat{\mathbf{w}} = \text{argmin}_\mathbf{w} \,E(\mathbf{w}) = (\Phi^{\top}\Phi)^{-1}\Phi^{\top}\mathbf{y}=\Phi^{+}\mathbf{y}$$

ou une autre méthode.

Remarques finales

Problème de sélection de dimension

Dans la pratique, il est souvent nécessaire de construire indépendamment un modèle du phénomène, c'est-à-dire de déterminer combien et quelles fonctions de base doivent être prises. La première impulsion pour «obtenir plus» peut jouer une blague cruelle: le modèle sera trop sensible au bruit dans les données (overfitting). En revanche, si vous contraignez trop le modèle, il sera trop grossier (sous-ajustement).



Il y a deux façons de sortir de la situation. La première consiste à augmenter systématiquement le nombre de fonctions de base, à vérifier la qualité de la régression et à s'arrêter dans le temps. Ou la seconde: choisissez une fonction de perte qui déterminera automatiquement le nombre de degrés de liberté. Comme critère de succès de la régression, vous pouvez utiliser le coefficient de détermination, qui a déjà été mentionné ci-dessus, cependant, le problème est que$$$R^2$croît de manière monotone avec la dimension croissante de la base. Par conséquent, le coefficient ajusté est introduit

$$

$$\bar{R}^2=1-(1-R^2)\left[\frac{N-1}{N-(n+1)}\right],$$

Où $$$N$ - taille de l'échantillon, $$$n$- le nombre de variables indépendantes. Suivant le$$$\bar{R}^2$, nous pouvons nous arrêter à temps et arrêter d'ajouter des degrés de liberté supplémentaires.



Le deuxième groupe d'approches est la régularisation, dont la plus connue est Ridge ($$$L_2$/ crête / régularisation de Tikhonov), Lasso ($$$L_1$régularisation) et Elastic Net (Ridge + Lasso). L'idée principale de ces méthodes est de modifier la fonction de perte avec des termes supplémentaires qui ne permettront pas le vecteur de coefficients$$$\mathbf{w}$ grandir indéfiniment et ainsi empêcher le recyclage

$$

$$\begin{aligned} E_{\text{Ridge}}(\mathbf{w})&=\text{SSE}(\mathbf{w})+\alpha \sum_i |w_i|^2 = \text{SSE}(\mathbf{w})+\alpha \| \mathbf{w}\|_{L_2}^2,\\ E_{\text{Lasso}}(\mathbf{w})&=\text{SSE}(\mathbf{w})+\beta \sum_i |w_i| =\text{SSE}(\mathbf{w})+\beta \| \mathbf{w}\|_{L_1},\\ E_{\text{EN}}(\mathbf{w})&=\text{SSE}(\mathbf{w})+\alpha \| \mathbf{w}\|_{L_2}^2+\beta \| \mathbf{w}\|_{L_1}, \\ \end{aligned}$$

Où $$$\alpha$ et $$$\beta$- les paramètres qui contrôlent la "force" de la régularisation. C'est un vaste sujet avec une belle géométrie qui mérite une discussion séparée. En passant, je mentionnerai que pour le cas de deux variables, en utilisant l'interprétation probabiliste, on peut obtenir les régressions Ridge et Lasso en choisissant avec succès la distribution a priori pour le coefficient$$$b$

$$

$$y = a + bx + \epsilon,\qquad \epsilon \sim \mathcal{N}(0,\,\sigma^{2}),\qquad \left\{\begin{aligned} &b \sim \mathcal{N}(0,\,\tau^{2})&\leftarrow\text{Ridge},\\ &b \sim \text{Laplace} (0,\,\alpha)&\leftarrow\text{Lasso}. \end{aligned}\right.$$

Méthodes numériques

Permettez-moi de dire quelques mots sur la façon de minimiser la fonction de perte dans la pratique. SSE est une fonction quadratique ordinaire qui est paramétrée par les données d'entrée, donc en principe elle peut être minimisée par la méthode de descente la plus raide ou d'autres méthodes d'optimisation. Bien entendu, les meilleurs résultats sont montrés par des algorithmes qui prennent en compte la forme de la fonction SSE, par exemple la méthode de descente de gradient stochastique. L'implémentation de la régression par Lasso dans scikit-learn utilise la méthode de descente de coordonnées.



Vous pouvez également résoudre des équations normales à l'aide de méthodes d'algèbre linéaire numérique. Une méthode efficace utilisée par scikit-learn pour OLS consiste à trouver la pseudo-inverse en utilisant la décomposition de valeurs singulières. Les champs de cet article sont trop étroits pour aborder ce sujet, pour plus de détails je vous conseille de vous référer au cours des conférences de K.V. Vorontsov.

Publicité et conclusion

Cet article est un récit abrégé de l'un des chapitres d'un cours sur l'apprentissage automatique classique à l' Université universitaire de Kiev (successeur de la branche de Kiev de l'Institut de physique et de technologie de Moscou, KO MIPT). L'auteur de l'article a aidé à créer ce cours. Le cours se déroule techniquement sur la plate-forme Google Colab, qui vous permet de combiner des formules au format LaTeX, du code exécutable Python et des démonstrations interactives en Python + JavaScript, afin que les étudiants puissent travailler avec le matériel du cours et exécuter le code à partir de n'importe quel ordinateur équipé d'un navigateur. La page d'accueil contient des liens vers des résumés, des cahiers d'exercices pratiques et des ressources supplémentaires. Le cours est basé sur les principes suivants:

• tout le matériel doit être disponible pour les étudiants de la première paire;
• la conférence est nécessaire pour comprendre, pas pour prendre des notes (les notes sont déjà prêtes, il ne sert à rien de les écrire si vous ne le souhaitez pas);
• une conférence est plus qu'une conférence (il y a plus de matière dans les notes que ce qui a été annoncé lors de la conférence, en fait, les notes sont un manuel à part entière);
• visibilité et interactivité (illustrations, photos, démos, gifs, code, vidéos de youtube).

Si vous voulez voir le résultat, jetez un œil à la page du cours sur GitHub .



J'espère que vous avez été intéressé, merci de votre attention.