Remplacer des données par une fonction

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.

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

Ensuite tu peux t’amuser à trouver un polynôme de degré $p<n$ qui passe "au plus près" de tes $n$ 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.

J’ai édité, c’est un polynôme de degré $n-1$ qu’il faut chercher. Tu peux utiliser la méthode de Lagrange pour trouver ton polynôme.

Par contre si ton problème c’est de compresser des données, ce n’est pas la bonne voie.

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.