Discussion :

[Iradrille]

Hello,

Sujet surement récurent, mais mon problème est un peu particulier.

J'ai une liste de n nombres, à priori aléatoires. A partir de ces nombres je crée des points
(0, n0)
(1, n1)
...
Je peux trouver une fonction polynomiale (de degré n-1) qui passe par tous ces points, mais ce que je cherche, c'est la fonction la "plus simple" (pas plus simple, j'entend qui prendra le moins de place à écrire) même si je dois accepter des anomalies.

Par exemple pour les points
(0, 1)
(1, 1)
(2, 2)
(3, 1)

J'aimerai trouver f(x) = 1, avec une anomalie en x=2.
Et une fonction qui me donnerai les points
(0, 0.99)
(1, 0.99)
(2, 2.01)
(3, 1.01)
ne m'intéresse pas : 4 anomalies ici.

J'espère que c'est clair
Une technique secrète existe ? Où il faut chercher ça avec un algo tabou / génétique ou autre ?

[Alexis.M]

Il n'y a pas de technique secrète. La question est de savoir si tu possède un modèle pour tes données, c'est-à-dire si tu connais la 'loi' qui a généré les données. Dans ce cas tu peux espérer (pour peu que le modèle se comporte bien) déterminer les paramètres éventuels du modèle.

Il n'existe rien dans le cas général. Des modèles de type réseaux de neurones
multi-couche sont connu pour être des approximateurs universels.

Par contre il me paraît douteux que tu puisse atteindre par des méthodes numériques le degrès de précision que tu sembles rechercher.

La question est donc: as-tu des a apriori sur la forme des données ?

Un apriori pourrait être:
une fonction constante sauf en quelques points et à valeurs entières. Auquel cas il n'est pas impossible de pouvoir 'fitter' la fonction que tu donnes en exemple (comme une combinaison linéaire d'une fonction constante et d'une Dirac avec régularisation l1 sur les coefficient de l'ensemble des Diracs, par exemple).

[pseudocode]

Je peux trouver une fonction polynomiale (de degré n-1) qui passe par tous ces points, mais ce que je cherche, c'est la fonction la "plus simple" (pas plus simple, j'entend qui prendra le moins de place à écrire) même si je dois accepter des anomalies.

Si tu cherches uniquement à fitter par une fonction polynomiale, le plus simple c'est de tester tous les degrés de polynôme (de 0 à N-1). Par exemple en utilisant les moindres carrés.

Tu peux alors utiliser le "coefficient of determination" (R²) pour sélectionner le meilleur polynôme parmi les N.

[Iradrille]

La question est donc: as-tu des a apriori sur la forme des données ?

Le seul a-priori que j'ai, c'est que j'aurais que des entiers positifs (en fait des blocs de 32 bits que je peux interpréter comme je veux, mais je pense que les interpréter en entiers sera plus simple)
Le problème d'un réseaux de neurones c'est qu'il faut une certaine logique dans les données (ou avoir de la chance et que les données ressemblent à un modèle appris). Et la relation logique je peux pas la prouver.

Si tu cherches uniquement à fitter par une fonction polynomiale, le plus simple c'est de tester tous les degrés de polynôme (de 0 à N-1). Par exemple en utilisant les moindres carrés.

Tu peux alors utiliser le "coefficient of determination" (R²) pour sélectionner le meilleur polynôme parmi les N.

Je vais essayer ça dans un premier temps, mais l'idéal serait de ne pas se limiter aux polynomes.

[Aleph69]

Bonsoir,

a priori ton problème n'a pas l'air compliqué mais je ne comprends pas ce que tu entends par une fonction "facile à écrire". Dans ton exemple, il suffit de définir les deux ensembles E={0,1,3} et F={2}, et la fonction que tu cherches s'écrit f(x)=1_E+2*1_F où 1_E et 1_F sont les fonctions indicatrices pour E et F respectivement. La généralisation est facile.

Lorsque tu écris que tu ne veux pas
(0, 0.99)
(1, 0.99)
(2, 2.01)
(3, 1.01)
tu écris explicitement que tu cherches une fonction interpolante. Le problème est connu et les polynômes de Lagrange sont solutions de ton problème. Ils sont connus analytiquement. Leur écriture n'est pas compliquée non plus.

Tu peux également interpoler par morceaux. La fonction globale est celle dont la restriction à un segment [i,i+1] est la droite affine passant par les deux points d'interpolation. L'écriture est également très simple.