Remplacer des données par une fonction

a marqué ce sujet comme résolu.

Bonjour :-)

J’ai des données qui ressemblent à ça :

80 101 116 105 116 32 109 97 108 105 110 32 106 101 32 116 101 32 115 111 117 104 97 105 116 101 32 117 110 101 32 98 111 110 110 101 32 106 111 117 114 110 101 101 32 58 68 32 33

C’est simplement la représentation décimale d’un fichier

Si je représente ces nombres dans un graphique j’obtiens ça :

Représentation graphique de la réprésentation décimale d'un fichier
Représentation graphique de la réprésentation décimale d’un fichier

Je suppose que c’est possible de trouver une fonction permettant de retrouver ces données (en arrondissant à l’entier), comment puis-je faire ça ?

Je pense à une fonction mathématique, cependant une fonction de programmation m’irait aussi ^^


L’idée à la base était de faire un petit programme qui calcule les données à partir d’une fonction, dans l’idée que le programme serait plus léger que les données en elles-mêmes….

Après un peu de réflexions ça m’étonnerais que la fonction associée soit plus compacte que les données originales, cependant comme je n’ai pas la moindre idée de comment ça peut se faire, ça m’intéresse :D

Merci d’avances pour vos pistes :pirate:

Hello,

Je te mets un extrait de mon mémoire de fin étude, où j’ouvrais sur la question de la compression via des méthodes de Deep Learning qui peuvent être une bonne piste pour résoudre ta problématique :

L’ingénieur Song HAN, professeur et chercheur au MIT, a présenté le 6 janvier 2016 à l’Université de Standford un séminaire intitulé Deep Compression and EIE : Deep Neural Network Model Compression and Hardware Acceleration où il décrit différentes méthodes de compressions :

  • La méthode pruning (élagage [fr]) consiste à reproduire un réseau de neurones plus petit que celui d’origine avec une précision relativement équivalente. Le fonctionnement est le même que pour l’apprentissage, on apprend à un clone à se comporter de la même façon que l’original.
  • La quantization (quantification [fr]) est une méthode de compression fonctionnant sur le même principe qu’une archive Zip : on indexe les poids similaires dans un dictionnaire après une phase d’ajustement.
  • L’encodage de Huffman appliqué aux poids synaptiques. On analyse la fréquence d’apparition des redondances de poids à l’aide d’un arbre afin d’en obtenir un condensé optimal.
+0 -1

Salut, une solution simple c’est de faire de l’interpolation. Si tu as nn points alors il existe un unique polynôme de degré n1n-1 qui passe par tous ces points. Mais par contre pour stocker un polynôme de degré n1n-1 il te faudra toujours nn variables !

Ensuite tu peux t’amuser à trouver un polynôme de degré p<np<n qui passe "au plus près" de tes nn points, c’est ce que montre le graphique que tu as trouvé sur Wikipédia. Tu peux voir ça comme "oublier des détails" de ton set de données initial.

Ensuite si tu regarde le problème de manière plus globale, comme l’a dit Aabu, tu vas te ramener au problème de la compression de données. Tu peux faire de la compression avec ou sans pertes. Mon exemple du paragraphe du dessus peut être vu comme une sorte de compression avec pertes. Mais on sait aussi compresser les données sans pertes. Il y a des limites au taux de compression que l’on peut obtenir, qui dépend de la quantité d’information que contient ton set de données. Par exemple si ton set de données contient 1000 zéros à la suite, tu peux l’écrire "mille fois 0", ce qui te fera économiser beaucoup de place par rapport à écrire mille 0 à la suite. Mais s’il s’agit de 1000 chiffres totalement aléatoires, ça va être plus compliqué. Pour en savoir plus les mot clés sont Théorie de l’information.

+1 -0

Si tu as nn points alors il existe un unique polynôme de degré n+1n+1 qui passe par tous ces points. Mais par contre pour stocker un polynôme de degré n+1n+1 il te faudra toujours nn variables !

J’ai du mal à voir comment trouver ce polynôme de degré n+1n+1 (autrement que par bruteforce)

Si mes souvenirs de lycée sont bons (c’était il n’y as pas si longtemps pourtant :-° ) un polynôme de degré n+1n+1 s’écrit y=a0+(a1X2)+(a2X3)+(a3X4)+(a4X5)+...+(anXn+1)y = a_0 + (a_1 \cdot X^2) + (a_2 \cdot X^3) + (a_3 \cdot X^4) + (a_4 \cdot X^5) + ... + (a_n * X^{n+1})

En fait je ne vois pas comment trouver la valeur des variables a0a_0 à ana_n autrement que par bruteforce :(

EDIT : je viens de trouver ça je vais y jeter un oeil :-°

+0 -0

Bonsoir,

Je pense à une fonction mathématique, cependant une fonction de programmation m’irait aussi

Les fonctions en programmation sont en pratique un sous-ensemble des fonctions mathématiques. Les choses non-calculables ne sont pas forcément d’un grand intérêt, donc sur les cas pratiques, ça coïncide pas mal.


Si tu représentes des données par une fonction, tu dois aussi utiliser des données pour décrire la fonction en question. La fonction la plus simple qui représente tes données, c’est tout simplement… les données elles-mêmes. En travaillant sur des entiers quelconques, parler d’interpolation polynomiale pour représenter une suite d’entier est peu intéressante, parce que tu stockeras la représentation du polynôme, qui fait la même taille que ta suite d’entier initiale.

Pour avoir un intérêt, il faut que la description de la fonction soit plus petite que les données initiale. On en vient au problème de la compression. Dans plein d’applications pratiques, on peut avoir des compresseurs/décompresseurs à part, dont la taille importe peu, parce qu’on ne les transfère pas avec les données. Parfois, on veut embarquer le décompresseur avec les données. Quoi qu’il en soit, il faut que ce qu’on fournit au décompresseur pour retrouver la données initiale soit plus petit que la donnée initiale elle-même.

Pour la compression (sans perte), on a plein de techniques. Ce sont des fonctions mathématiques qu’on peut évidemment programmer. On représentera une séquence par une autre séquence avec des instructions pour faire le chemin inverse. Tous les algos de compression sans perte sont basés là-dessus, en particulier ceux génériques comme zip, rar, etc.

Quand on a des données spécialisées, on peut utiliser des astuces pour comprimer plus efficacement. Par exemple, FLAC utilise le fait que le signal musical soit corrélé d’un instant à l’autre, pour décrire de manière très compacte le signal sur de petites durées. Le MP3 enregistre une approximation du signal sonore faite de petites briques élémentaires qu’on connaît bien et qu’on sait décrire avec seulement quelques paramètres (les ondelettes). Le JPEG utilise une idée similaire mais pour les images. Avec des données très spécialisées, on peut se retrouver avec des compressions vraiment très impressionnantes. Quoi qu’il en soit, on a en général un compromis entre la compression qu’on obtient et la connaissance qu’on a des données.

On peut s’amuser à faire du deep learning pour résoudre le problème de la compression, mais c’est clairement pas la première approche à considérer ou à découvrir en tant que novice. Et c’est assez anecdotique dans l’état de la technique.


Dans le sujet, on a parlé d’interpolation. Pour moi, ça résout un autre problème, qui est de boucher les trous quand on sait qu’on a une fonction réelle qui passe par certains points. Ce n’est pas vraiment utile pour représenter une séquence d’entier parce que ça revient à stocker les entiers en question d’une manière ou d’une autre.

Drulac a aussi montré des images de régression polynomiale. C’est assez intéressant, parce qu’il s’agit d’une estimation "au plus proche" et que ce genre d’idée est effectivement utilisé dans la compression de données (notamment FLAC), parce qu’on peut représenter beaucoup d’information avec peu de paramètres.

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte