Temps total: 150 heures
Étude initiale du domaine : 6h + 2h (complété)
Peaufinage et confirmation finale de la question de recherche (calendrier plus détaillé) : 2h (complété)
Préparation du site web du projet : 4h (complété)
Étude approfondie du domaine : 40h + 4h (complété)
Temps total accordé: 64h
Planification, horaire détaillé, objectifs, et limites : 2h
Application et test d'hypothèses : 58h
Formatages des tests d'hypothèse en données analysables : 8h
Analyse et réflexion : 8h
Préparation de la synthèse pour le rapport : 4h
Rédaction du rapport : 7h
Préparation présentation : 3h
Est-ce que l’utilisation des algorithmes de compression dans les données d’entrées leur permettent un enrichissement utilisable par les algorithmes d’apprentissage automatique?
Ma recherche se produira sur un laptop de gaming, ma capacité d’exécution de code sera limité à ça. Mon budget consiste à trois cartons de berlingots de lait au chocolat et une demie monster (coupé verticalement).
Le concept d’un code aléatoire défini par la complexité de kolmogorov introduit une limite potentielle de la compression des données bruitées (la chose la plus applicable de ma recherche). J’ai l’intuition que dans mon application des algorithmes de compression sans perte, le bruit introduit des données sera soit imcompressable ou soit introduira plus de bruitage (comme un sur-accommodement sur le bruitage qui ignorera la structure utile). Ceci risque de faire pivoter ma recherche vers des algorithmes de compression avec perte pour améliorer la performance (et éviter des failles potentiellement fondamentales des algorithmes de compression sans perte)
Commencer avec un apprentissage supervisé sur des modèles linéaires, élaborer les techniques sur des modèles non-linéares (idéalement les cas MLP comme un autoencodeur)
SOIT Explorer ensuite les cas d'apprentissage non-supervisé
OU SOIT Explorer les cas de compression de données de perte acceptable (potentiellement la direction primaire étant donné les limites des algorithmes de compression sans perte sur des données bruitées)
- Création d'un ACP supervisé (préservation de plus grande variation par rapport au changement des données d'entrées et l'effet sur la sortie), élaboration à un auto-encodeur
- compression par classe -> compression de chaque données de chaque classe (dans un arbre), apprentissage par arbre. hypothèse : redondance statistique dans les données (interprétée comme chaque classe a un langage) compressé offre une meilleure
- hypothèse: la compresssion des redondances dans les entrées offrent une meilleure valeur des données
- avoir un algorithme de compression à perte qui mesure le taux optimal de perte, qui apprend la fonction du bruit, et qui permet une compression utile en fonction des deux derniers (le problème sera comment on implémente cette fonction de compression dans le contexte d'apprentissage automatique)
- Le plus grand problème à survenir est de trouver l'implémentation idéale d'un algorithme de compression dans le contexte d'apprentissage automatique (l'extraction utile des données comprimées). si on regarde à l'idée de compression par classe, on a une application spécifique mais j'en suis convaincu qu'il existe une meilleure implémentation. Sûrement ce serait un algorithme hybride des algorithmes d'apprentissage automatique et de compression pûre.
- Je veux un algorithme d'apprentissage de distribution qui commence comme une distribution uniforme et apprend très peu d'information (surprise de shannon) à l'ajout d'information (de nouvelles données). L'ajout d'information s'augmenterait graduellement à l'ajout des données. Si les données suivent tous la même distribution, l'ajout d'information aura un plateau pour indiquer que la distribution est confortablement apprise (sûrement contrôlé par un hyperparamètre de perte, est-ce que cet hyperparamètre peut-être appris par un algorithme décrite par une idée précédente?).
- dictionnaire d'un algorithme de compression peut-il être similaire au transformer (un dictionnaire souple)?
- J'ai la notion intuitive que K(x) est purement non-biaisé. Dans le contexte de l'apprentissage automatique, ceci ferait que K(x) est pûrement vulnérable à la variance. Ça fait du sens, K(x) est obligé à compresser le bruit intrinsèque dans les données aussi. La question suit: serait-il possible de concevoir un aspect de K(x) avec perte, ceci serait une introduction de biais dans la compression qui pourrait aussi avoir un hyperparamêtre qui gêre directement le compromis biais-variance. En utilisant K(x) directement, ce concept demeura dans le monde théorique; mais ça pourrait être quand même une piste intéressante à explorer (probablement très dur/compliquer à explorer).
J’ai lu des sites Wikipédia à propos de la redondance(info théo), MDL, complexité Kolmogorov, compression des données, auto-encodeurs, théorie algorithmique de l’information. Je retiens une notion centrale qui est la complexité de Kolmogorov, et son travail avec Chaitin, Solomonoff. Je trouve que cette piste me semble être digne d’une étude approfondie. De multiples articles décrivent les limites de la compression de données (ex: notion aléatoire Kolmogorov, redondance, etc… ). Avec la connexion entre la compression des données et l’apprentissage automatique, je vois une piste à explorer sur la limite des méthodes d’apprentissage automatique théorique.
De ma lecture secondaire (liens ci-dessous), je n’ai pas trouvé d’autres articles wikipédia qui m’ont ouvert d’autres pistes.
utilise un algorithme non-paramétré (une variante de k-ppv), fonction de distance NCD (normalised compression distance).
Algo: pour x^ à prédire -> pour chaque (k plus proches) x_i concatener avec x^ pour x_ix^, comprimer x_i pour Cx_i et x_ix^ pour Cx_ix^, calculer la distance NCD et appliquer k-ppv.
J'aimerai modifier cet algorithme pour que la compression des données soit effectuée par rapport à toute l'ensemble de données d'une classe des données d'entrainement. L'argument est que des parties individuelles de chaque x_i peuvent individuellement être considérée comme aléatoire dans le sens kolmogorov, mais ensemble, contiennent de l'information comprimable plus efficacement. On peut aussi rajouter un élément potentiellement normalisateur de la compression de toutes les données ensemble peu importe la classe. Avec ça, je pourrai essayer de créer une équation qui modélise (un gain d'information?) la séparation du langage de la classe et le langage des données qui permet aux entrées d'avoir des prédictions indépêndantes du langage des données (correspond plus au langage de la classe). L'algorithme ne sera plus capable de faire de la régression du sens de k-ppv (puisqu'il ne sera plus k-ppv).
Les méthodes non-paramétrées n'introduisent pas un biais inductif lors de l'entraînement. Le compresseur est indépendant du type des données par nature. Le modèle du papier est universel en termes de distributions de données. Cependant, une compression sans perte exige naturellement des données non-bruitées pour bien fonctionner.
Les résultats avec un algorithme de compression plus performant (bz2) a été trouvé d'avoir une pire performance comparé à gzip (compression moins performante). Les auteurs soupçonnent que c'est dû à la permutation de charactères par bz2 qui nuit à la performance.
TODO Peut-être à ne pas lire… Si ma piste courante (utilisation pure des algorithmes de compression) se mène nulle part, j’y visterai ce papier…
TODO Peut-être à ne pas lire… Une méthode très intéressante à étudier, mais je ne vois plus la pertinence d’y lire.
Mesure la similarité de deux séquences (IMPORTANT), utilise le principe de la complexité de kolmogorov
Développe la théorie d'une distance d'information normalisée, et propose une formule de distance d'information qui utilise un algorithme de compression concrèt (au lieu de la complexité kolmogorov).
Le papier démontre l'application de la notion de distance sur la création d'arbres de similarité des langues et des séquences d'ADN, et conclut l'utilisabilité dans ces cas.
Je tire une notion de séquence que je vois être très importante sur l'application de la notion de distance. Par exemple, le papier utilise l'algorithme de compression lempel-ziv (gzip) pour créer un arbre de langues. L'algorithme se fie sur les récurrences de séquences binaires. La séquence d'une image est totalement différente de la séquence du langage naturel. Serait-it possible de soit trouver un algorithme ayant une différente interprétation d'une séquence, altérer la notion de séquence dans un algorithme de compression exitant, ou de créer un algorithme de compression avec un interprétation plus générale (ou même universel, ou est-ce essentiellement trouver la complexité de kolmogorov pure) ?
Utilise ce papier comme référence théorique pour les modifications potentielles de l'algorithme modifié proposé (limitation potentielles théoriques) #### [The Limits of AI Explainability: An Algorithmic Information Theory Approach](https://arxiv.org/pdf/2504.20676)
Side quest de lecture. Lecture très brève. pas tant pertinent
Rien compris... peut-être à relire
Espaces métrique. Étudie l'idée d'une métrique normalisée. La distance absolue prend seulement en compte le delta des éléments. Par exemple d(0.1,0.2)=d(1000.1,1000.2) dans l'espace euclédien (l2). Le papier veut prendre en compte les distances relatives. L'auteur développe 2 normalisations de métriques
Introduit 3 formules d'approximations de NID: NCD, CDM, et CLM. I; n'y a pas de grosse différence dans la performance des différentes formules d'approximation, mais plutôt par les différents types de compressesurs. Le compresseur le plus efficace était BB-ANS. L'algorithme de compression avec variables latentes présenté applique ANS sur un autoencodeur variationnel entrainé pour recevoir un compresseur, qui ensuite fait k-ppv avec une métrique de distance normalisée (dans ce cas NCD).
Utilise NCD comme métrique normalisée (avec précision pratique de e<0.1). Développe les propriétés du NCD (quasi universalité, métrique normalisée).
NCD(x,y) = 0 -> x = y
NCD(x,y) = 1 -> x très différent de y d'u n point de vue du compresseur
Identifie les propriétés d'un comrpresseur normal (compatible pour le NCD).
Fait du clustering de données sur une matrice de distance (NCD). Utilise la méthode de quartet.
Expérimente avec des gênes, textes, fichiers de musique, photos et conclut que la méthode a une robustesse remarquable à travers de divers sujets d'applications.
Définit: NID = E(x,y)/max{K(x),K(y)}
Prouve que NID n'est ni lower semicomputable, ni upper semi computable #### [How Incomputable Is Kolmogorov Complexity?](https://homepages.cwi.nl/~paulv/papers/incomp.pdf)
Article d'introduction à la complexité de kolmogorov, prouve K(x) incalculable (on le sait déjà), fait référence à un autre article qui approxime la complexité de kolmogorov avec des listes quadratiques (à lire cet article). #### [A Brief on Short Descriptions](https://dl.acm.org/doi/epdf/10.1145/2902945.2902957) à lire svp....