Interpolation spline d'ordre supérieur

8

J'ai remarqué que l'interpolation spline avec un degré supérieur à 3 (tout au-delà des splines cubiques) a une erreur d'interpolation très élevée, donc la prédiction est pour la plupart horrible. Je suis tombé sur diverses notes de cours, diapositives et vidéos Youtube qui indiquent simplement que les splines cubiques (3ème degré) sont optimales et que tout ce qui est au-delà est une mauvaise idée. Ces sources ne mentionnent cependant jamais pourquoi c'est le cas.

Quelqu'un peut-il m'expliquer pourquoi c'est le cas et peut-être me donner un titre / lien vers un journal / document de conférence qui explique cela ou peut-être même en donner une preuve.

goocreations
la source
1
Je dois faire référence à ce phénomène de surajustement, mais je ne trouve aucune littérature universitaire qui le mentionne. Connaissez-vous peut-être un article / un livre / une thèse que je peux utiliser?
goocreations

Réponses:

10

Il n'y a pas une telle preuve car ce n'est pas toujours vrai. C'est une règle de base, car je vous garantis que vous pourriez trouver une situation - un nombre infini de situations en fait - où des splines d'ordre supérieur feraient mieux que des splines cubiques. L'ordre de spline optimal pour une situation donnée est exactement le même ordre que le système que vous essayez de modéliser. Si l'ordre est le même et que vos points de données sont exempts d'erreurs (jamais le cas, bien sûr, sauf pour des problèmes théoriques), alors vous devriez pouvoir modéliser parfaitement le système.

La raison pour laquelle ils recommandent de ne pas aller plus haut que les splines cubiques est que le sur- ajustement est vraiment, vraiment mauvais. Le sur-ajustement peut considérablement amplifier les erreurs, tandis que le "sous-ajustement" (en choisissant une méthode spline avec un ordre inférieur à l'ordre du système que vous modélisez) introduit un filtrage passe-bas qui n'est pas si mal ou parfois même bénéfique.

Jim Clay
la source
+1. Notez que le choix d' un ajustement d'ordre inférieur que le modèle étant représentant est pas « pseudo » passe bas filtrage - il est une forme de filtrage passe - bas dans son propre droit.
Tarin Ziyaee
@ user4619 Vous avez raison. Je voulais dire que ce n'est pas un filtrage passe-bas dans le sens auquel nous pensons habituellement avec les filtres FIR et IIR, mais c'est un filtrage passe-bas, il n'est tout simplement pas facilement caractérisable. Modifié la réponse.
Jim Clay
3

Voici un aperçu approximatif (qui peut être correct ou non). La spline est une interpolation polynomiale, c'est-à-dire que chaque section de la courbe entre les points de support voisins est un polynôme. Un polynôme d'ordre N a N + 1 coefficients (degrés de liberté) et peut donc satisfaire 4 conditions aux limites par section. Le choix des conditions aux limites détermine le type d'interpolation. Pour une spline qui frappe exactement les points de support et crée une première et une seconde dérivées continues.

Pour les splines d'ordre supérieur, vous pouvez également obtenir des dérivées d'ordre supérieur pour qu'elles soient continues, mais cela a tendance à ajouter beaucoup de contenu haute fréquence à des transitions plus nettes et entraîne souvent une "sonnerie" ou une oscillation excessive. Les mots originaux "spline" proviennent d'une règle flexible que les gens utilisaient pour effectuer des interpolations "mécaniques". Je pense que vous pouvez réellement montrer en analysant la mécanique des règles que la spline cubique correspond à ce comportement.

Comme pour la plupart des choses, cela dépend de votre application et de ce que vous voulez faire. Une alternative intéressante aux splines cubiques sont les interpolations hermitiennes qui peuvent garantir la monotonie et s'assurer que l'interpolation ne oscille jamais en dehors des points d'appui. Depuis la fonction d'aide de MATLAB

Tips

spline constructs  in almost the same way pchip constructs . However, spline chooses the slopes at the  differently, namely to make even  continuous. This has the following effects:

   - spline produces a smoother result, i.e.  is continuous.    
   - spline produces a more accurate result if the data consists of values of a smooth function.    
   - pchip has no overshoots and less oscillation if the data are not smooth.    
   - pchip is less expensive to set up.
   - The two are equally expensive to evaluate.
Hilmar
la source
2

Il existe plusieurs types de splines, avec des objectifs contradictoires:

  • aller près des points de données d'entrée
  • courbes lisses vs ondulées

Pour quelques points de données, vous pouvez souhaiter interpoler exactement; mais pour des milliers de points, voire une douzaine avec du bruit, une interpolation exacte se tortillera. La plupart des ajusteurs de cannelures ont des paramètres pour comparer la proximité de l'ajustement par rapport à la douceur globale. Voici un tracé de splines de degré 1 (linéaire par morceaux, connectez les points) avec données = ligne + bruit. Vous voyez que l'ajustement exact des données zigzague en haut et en bas, tandis que le lissage maximum donne une ligne droite:

entrez la description de l'image ici Il existe des splines pour différents travaux, en fonction des données d'entrée et des nouveaux points intermédiaires: des dizaines / millions de points, le niveau de bruit, la dispersion / sur une grille, 1d 2d 3d ... Sur une grille régulière en 3d par exemple, un la spline de degré regardera voisins de chaque point de requête: 1 (voisin le plus proche), 8 (trilinéaire), 27, 64 ... Pouvez-vous vous permettre 64? Avez-vous besoin de 64? Ça dépend.d(d+1)3

(Très brièvement, les splines B sont lisses; les splines
Catmull-Rom interpolent, par exemple des images de films; des
mélanges comme 1/3 B + 2/3 CR sont utiles entre les deux.)

Comment le degré polynomial affecte-t-il la ondulation? Voir le phénomène de Runge .

Sur dépassement en 1d 2d 3d ... voir (ahem) cette question sur math.stackexchange.
Sur les dangers de l'extrapolation avec des splines au-delà du linéaire, voir ceci sur SO.

Voir aussi stackoverflow.com/questions/tagged/spline .

denis
la source
-1

Une autre façon de voir les choses est de remarquer que les images et les ensembles de données les plus intéressants sont «lisses» dans une certaine mesure. L'interpolation du bruit gaussien, par exemple, devrait mieux fonctionner avec des splines d'ordre supérieur.

Hasan
la source