Question d'approximation des moindres carrés

11

Je prends un cours sur le calcul scientifique, et nous venons de passer en revue l'approximation des moindres carrés. Ma question concerne spécifiquement l'approximation à l'aide de polynômes. Je comprends que si vous avez n + 1 points de données, vous pouvez trouver un polynôme unique de degré n qui décrit tous ces points. Mais je peux aussi voir pourquoi ce n'est pas toujours idéal. Avec une telle approche, vous pouvez obtenir beaucoup de bruit entre les points de données. Je suppose que c'est bien d'avoir un polynôme de degré inférieur qui estime assez bien vos données.

Ma question est: comment décidez-vous dans la pratique du degré de polynôme que vous allez utiliser? Existe-t-il une règle d'or ou cela dépend-il uniquement du problème en question? Doit-on tenir compte de divers compromis lors du choix entre plus ou moins de degrés? Ou est-ce que je comprends mal quelque chose ici?

Merci d'avance.

Uday Pramod
la source
2
Je pense que dans la pratique, les gens utilisent des choses comme l'interpolation spline en.wikipedia.org/wiki/Spline_interpolation pour utiliser des polys de faible ordre, mais ils s'accordent bien les uns avec les autres sur le domaine global. De cette façon, il n'est pas nécessaire de deviner un ordre polynomial global.
Nasser
Merci pour le lien. Nous n'avons pas encore examiné les splines, c'est donc une lecture intéressante.
Uday Pramod
Qu'est-ce que tu veux faire exactement? Essayez-vous d'interpoler les points ou d'ajuster des données données? Par exemple, il est inutile d'interpoler des données qui consistent en une distribution normale avec du bruit. Pour le premier, la réponse de Nasser est bonne. Pour ces derniers, la fonction d'ajustement dépend uniquement du problème en question et n'est pas, dans de nombreux cas, polynomiale.
hauntergeist
Vous pourriez être intéressé par les réponses de cette question sur la validation croisée .
Bort

Réponses:

18

L'aspect le plus important de l'interpolation et de l'ajustement de courbe est de comprendre pourquoi les ajustements polynomiaux d'ordre élevé peuvent être un problème et quelles sont les autres options, puis vous pouvez comprendre quand elles sont / ne sont pas un bon choix.

Quelques problèmes avec les polynômes d'ordre élevé:

  • Les polynômes sont naturellement des fonctions oscillatoires. À mesure que l'ordre du polynôme augmente, le nombre d'oscillations augmente et ces oscillations deviennent plus sévères. Je simplifie ici, la possibilité de racines multiples et imaginaires le rend un peu plus complexe, mais le point est le même.

  • Les polynômes approchent +/- l'infini à un taux égal à l'ordre polynomial lorsque x va à +/- l'infini. Ce n'est souvent pas un comportement souhaité.

  • Le calcul des coefficients polynomiaux pour les polynômes d'ordre élevé est généralement un problème mal conditionné. Cela signifie que de petites erreurs (telles que l'arrondi dans votre ordinateur) peuvent créer de grands changements dans la réponse. Le système linéaire à résoudre implique une matrice Vandermonde qui peut facilement être mal conditionnée.

Je pense que peut-être le cœur de ce problème est la distinction entre l' ajustement de courbe et l' interpolation .

L'interpolation est utilisée lorsque vous pensez que vos données sont très précises et que vous souhaitez que votre fonction corresponde exactement aux points de données. Lorsque vous avez besoin de valeurs entre vos points de données, il est généralement préférable d'utiliser une fonction fluide qui correspond à la tendance locale des données. Les splines cubiques ou hermites sont souvent un bon choix pour ce type de problème car elles sont beaucoup moins sensibles aux changements ou erreurs non locaux (c'est-à-dire à des points de données éloignés d'un point donné) dans les données et sont moins oscillatoires qu'un polynôme. Considérez l'ensemble de données suivant:

x = 1   2   3   4   5   6   7   8   9  10
y = 1   1 1.1   1   1   1   1   1   1   1

Interpolation
Un ajustement polynomial a des oscillations beaucoup plus importantes, en particulier près des bords de l'ensemble de données, qu'une spline Hermite.

D'un autre côté, l'approximation des moindres carrés est un ajustement de courbetechnique. L'ajustement de courbe est utilisé lorsque vous avez une idée de la fonctionnalité attendue de vos données, mais que vous n'avez pas besoin que votre fonction traverse exactement tous les points de données. Cela est typique lorsque les données peuvent contenir des erreurs de mesure ou d'autres imprécisions ou lorsque vous souhaitez extraire la tendance générale des données. L'approximation des moindres carrés est le plus souvent introduite dans un cours en utilisant des polynômes pour l'ajustement de la courbe car cela se traduit par un système linéaire qui est relativement simple à résoudre en utilisant les techniques que vous avez probablement apprises plus tôt dans votre cours. Cependant, les techniques des moindres carrés sont beaucoup plus générales que les ajustements polynomiaux et peuvent être utilisées pour adapter n'importe quelle fonction souhaitée à un ensemble de données. Par exemple, si vous vous attendez à une croissance exponentielle de votre ensemble de données,

Enfin, le choix de la fonction adaptée à vos données est aussi important que l'exécution correcte des calculs d'interpolation ou des moindres carrés. Cela permet même une extrapolation (prudente). Considérez la situation suivante. Compte tenu des données démographiques (en millions de personnes) pour les États-Unis de 2000 à 2010:

Year:  2000   2001   2002   2003   2004   2005   2006   2007   2008   2010
Pop.: 284.97 287.63 290.11 292.81 295.52 298.38 301.23 304.09 306.77 309.35

L'utilisation d'un ajustement par moindres carrés exponentiel linéarisé N(t)=A*exp(B*t)ou d'un interpolant polynomial du 10e ordre donne les résultats suivants:
Graphique de la population

La croissance de la population américaine n'est pas tout à fait exponentielle, mais je vous laisse juger de la meilleure adéquation.

Doug Lipinski
la source
1
Un point que je voudrais faire avec votre graphique de la population américaine, de mémoire un bon ajustement dans le domaine ne signifie pas qu'il extrapolera bien. Dans cette optique, il peut être trompeur de montrer les grandes erreurs polynomiales en dehors de la région où vous avez des données.
Daryl
@Daryl D'accord, c'est pourquoi j'ai souligné que l'extrapolation doit être faite avec prudence et que le choix d'une fonction appropriée est crucial dans ce cas.
Doug Lipinski
@DougLipinski Merci pour la réponse perspicace. Pouvez-vous expliquer ce que vous entendez par moindres carrés linéarisés par opposition aux moindres carrés?
bela83
@ bela83 Répondre correctement serait trop long pour un commentaire. Je pense que ce serait une très bonne nouvelle question si vous voulez la poser.
Doug Lipinski
@DougLipinski Je vais essayer!
bela83
2

Très peu scientifique, mais une bonne règle de base est que les polynômes du 3ème degré sont généralement un bon début, et dans la pratique, je n'ai jamais vu personne utiliser plus d'un 6ème degré pour obtenir de bons résultats.

Le polynôme «idéal» serait l'ordre le plus bas qui représente suffisamment les données silencieuses pour votre objectif.

Si vos données sont suffisamment petites pour le permettre (elles le sont généralement), vous pouvez simplement essayer d'ajuster avec des polynômes d'ordre supérieur jusqu'à ce que vous commenciez à voir des oscillations, qui ont tendance à être le signe d'un «surajustement».

Une alternative serait une spline de lissage , mais cela dépend beaucoup de l'application. Les splines et les splines de lissage ne sont utiles que pour l'interpolation. Pour les données bruyantes, j'ai tendance à préférer les ajustements polynomiaux aux splines de lissage, mais les données avec lesquelles je travaille sont généralement bien approximées par les polynômes.

LKlevin
la source
1

Une approche décemment efficace que j'ai utilisée avec l'approximation polynomiale consiste à calculer les polynômes des moindres carrés à divers degrés (par exemple, de 1 à 10), puis à choisir la courbe qui minimise l'erreur quadratique moyenne à des points à mi-chemin entre les consécutifs (lorsque triés par x) points dans votre ensemble de données. Cela permet d'exclure les courbes avec des oscillations trop sévères.

dan04
la source