Sujet Le pub des programmeurs
- 1 925 réponses
- 117 participants
- 120 425 vues
- 130 followers
y a des programeurs sur AF si oui vous bossez sous quoi ?
Pov Gabou
batman14
bigbill
Citation : J'imagine que c'est relatif, mais la moyenne des bouquins traitant de pbs scientifiques recents sont en general bien plus chers que le bouquin de Mallat
Je suggérais juste que si batman14 veut se pencher sur MP, le Mallat/Zhang de 93 est tout à fait suffisant, pas la peine d'acheter le bouquin rien que pour ça..Citation : Dans le cas des atomes de Gabor, on est pas vraiment dans le cadre de MP.
Je comprends pas le sens de ta phrase. Qu'entends-tu par 'cadre'?Citation : La transformee de Fourier a court terme est elle meme une representation temps frequence qui y correspond si tees fenetres sont gaussiennes.
Je comprends pas que tu compares la STFT à MP qui est un algo adaptatif
Citation : C'est un algo qui est en gros N^3*P, ou N est le nombre de samples et P le nombre d'atomes.
D'où tires-tu cet ordre de complexité? De plus ta formule a l'air de suggérer que N et P sont indépendants, ce qui n'est pas vrai. Si tu prends un signal plus long, ton dictionnaire devra être plus volumineux également.Citation : Je suis pas sur d'etre d'accord. L'Algo est couteur, certes, mais tu n'as pas besoin de lister toutes les solutions pour avoir le resultat.
Ben si tu te places à l'étape n, où tu as trouvé n atomes et qu'il te reste un signal résiduel Rn, le but de l'étape n+1 est de trouver dans tout ton dictionnaire l'atome qui te donnera la corrélation max avec Rn. Et tu peux pas faire autrement que de calculer toutes les corrélations en tous lieux de Rn et pour tous les atomes
C'est le principe général de MP, après bien sûr il y a des optims..
Citation : Sur les problèmes NP complets il y a souvent moyen de contraindre le domaine d'etudes pour se permettre d'accélérer le process de résolution...
.. par exemple une optim qu'on doit à Krstulovic & GribonvalPov Gabou
Citation :
Je suggérais juste que si batman14 veut se pencher sur MP, le Mallat/Zhang de 93 est tout à fait suffisant, pas la peine d'acheter le bouquin rien que pour ça..
Non mais on est pas non plus oblige d'acheter le bouquin, il est, comme je l'ai bien precise, certainement disponible dans la bibliotheque si ton universite/ecole a un labo de signal. Mallat etant un des francais les plus cites/celebres en signal, son bouquin est bien present dans les bibliotheques francaises.
L'article de Mallat/Zang est un peu abrupt; en general, c'est difficile d'implementer a partir d'un seul article. Le bouquin introduit MP naturellement, et perso, je trouve le bouquin extraordinaire, c'est le meilleur bouquin que je connaisse en traitement du signal. T'as une mise en relation de pleins de champs differents (ce qui fait un des interets de la theorie des ondelettes, je trouve, d'un point de vue 'philosophique').
Citation :
Je comprends pas le sens de ta phrase. Qu'entends-tu par 'cadre'?
Et bien decomposition en atomes de Gabor, c'est "vieux". Je crois, sans etre sur, que l'article original de Gabor dans Nature (ou Science ?, je sais plus non plus) qui mettait en relation les atomes et le fonctionnement de l'ouie date des annees 50. Je vais verifier.
La STFT et la tranformee de Gabor sont tres semblables dans le principe; en fait, je crois meme qu'historiquement Gabor a ete le premier a suggerer une representation temps frequence (alors qu'avant on raisonnait plutot soit en temps, soit en frequence; mais bon, je suis pas sur non plus, j'ai du mal a imaginer comment on envosageait ces choses la il y a 60 ans
). Bref, l'idee de Gabor, c'est d'utiliser un noyau (exp modulee par une gaussienne), et de translater le noyau en temps et en frequence (je crois que la dilatation etait fixee au depart, mais la encore, je connait pas trop l'historique). Bref, c'est comme la STFT; fondamentalement, je pense meme que la transformee de Gabor est une STFT avec une fenetre gaussienne.Citation :
D'où tires-tu cet ordre de complexité? De plus ta formule a l'air de suggérer que N et P sont indépendants, ce qui n'est pas vrai. Si tu prends un signal plus long, ton dictionnaire devra être plus volumineux également.
Oui mais justement MP est une solution pour ne pas avoir a faire ca ! L'idee de base est simple: tu as un ensembles de vecteurs, le dictionnaire, qui est beaucoup plus volumineux qu'une base. Tu veux representer un signal s donne avec le minimum d'elements du dictionnaire: tu prends l'element f qui maximise la projection <s, f>, puis tu procedes recursivement.
En disant que l'algo est NP complet, tu dis que MP consiste a calculer la representation <s, f> pour tout f du dictionnaire, puis a faire pareil avec le residu, jusqu'a la fin. Si MP, c'etait ca, il y aurait pas grand chose a dire, c'est plutot evident. L'article seminal de Mallat, c'est que tu n'as *pas* besoin de parcourir tous les elements du dictionnaire pour "bien" approcher la fonction (en gros, l'article demontre des resultats sur le *comportement* du residuel lorsque le nombre d'etapes croit).
En fait, mon N^3 * P etait debile (j'avais etudie ca pendant mon DEA, ca date deja de quelques annees
, mais j'aimerais bien m'y remettre), car ca depend totalement de ton dictionnaire. Par exemple, si ton dictionnaire contient le signal de depart, ben il y a rien a faire, t'as ta decomposition en une etape (ce qui est un peu debile, evidemment). Par contre, avec les atomes de Gabor, dans l'article de Mallat, en decomposant les echelles temps, frequence et scaling en 1/2^i (i entier, positif et negatif en general), pour un signal de taille N, le dictionnaire est de taille Nlog2N, une etape de MP est en O(NlogN), et en general, tu n'as pas besoin de beaucoup d'iterations (sinon, ca sert a rien de toute facon), c'est pour ca qu'on parle de "greedy algorithms" d'ailleurs.C'est pour ca que parler de complexiste NP est un peu un non sens pour moi, parce que le but c'est de se retrouver avec une representation compacte, en utilisant justement le fait que l'ensemble de representation est "over-complet" (je sais pas comment on dit en francais).
En tout cas, je suis persuade que toute cette idee de redondance n'est que le debut, et qu'il y a vachement d'idees a explorer. D'ailleurs, un peu dans le meme ordre d'idees, un des medailles Field de cette annee, le fameux Terence Tao, s'interesse a ce type de problemes (parmi les nombreux problemes auxquels il s'interesse, mais je regarde pas trop ailleurs, c'est decourageant sinon )
https://www.math.ucla.edu/~tao/preprints/sparse.html
batman14
Pov Gabou
bigbill
overcomplete dictionary -> dictionnaire redondant
sparse decomposition -> décomposition parcimonieuse
greedy algorithm -> algorithme glouton
Je sais, ça fait bizarre
mais c'est les termes employés dans les publis en français sur le sujet.Pov Gabou >
Citation : fondamentalement, je pense meme que la transformee de Gabor est une STFT avec une fenetre gaussienne
C'est aussi mon avis, en revanche je vois pas le rapport avec une décomposition adaptative en atomes de Gabor. D'autre part, ceux-ci sont peut-être 'vieux' mais ça n'empêche pas qu'ils soient optimaux en résolution temps/fréquence. Mallat le démontre dans son bouquin, aux pages 31 et 32.Au sujet de l'ordre de complexité, il y a quelques éléments de réponse dans la thèse de Davis supervisée par Mallat.
Citation : En disant que l'algo est NP complet, tu dis que MP consiste a calculer la representation <s, f> pour tout f du dictionnaire, puis a faire pareil avec le residu, jusqu'a la fin. Si MP, c'etait ca, il y aurait pas grand chose a dire, c'est plutot evident. L'article seminal de Mallat, c'est que tu n'as *pas* besoin de parcourir tous les elements du dictionnaire pour "bien" approcher la fonction (en gros, l'article demontre des resultats sur le *comportement* du residuel lorsque le nombre d'etapes croit).
Oui mais.. le problème c'est que Mallat embraye tout de suite sur l'implémentation, avec un moyen d'optimisation de cette recherche qui est basé sur la formule d'update (9.101) page 424 du bouquin, ou (33) page 11 du Mallat/Zhang. OR cette formule suppose qu'on a des ressources mémoire illimitées pour stocker les précieuses corrélations croisées <gi,gj> ce qui est loin d'être le cas dans la réalité, en dehors de samples courts. Quelqu'un qui voudrait implémenter sur des signaux quelconques serait obligé de laisser tomber cette implémentation et d'en trouver une meilleure. S'il n'en trouve pas, il devra tout faire en brute force => il est ramené au NP-hard.Citation : Par exemple, si ton dictionnaire contient le signal de depart, ben il y a rien a faire, t'as ta decomposition en une etape (ce qui est un peu debile, evidemment).
Exact, dans ce cas la poursuite se résume à un seul atome. Mais il faudra effectuer les P corrélations entre le signal et chacun des P atomes du dictionnaire avant d'arriver à cette conclusion. On peut pas vraiment dire qu'il n'y a rien à faire. Quand tu dis que le résultat est débile, imagine cette expérience de pensée: on considère un sample inconnu, mono de longueur 1000 échantillonné en 16 bits. On considère d'autre part LE dictionnaire 'exhaustif' dont les atomes sont tous les signaux normés de longueur 1000 possibles. Le nombre d'atomes est astronomique. Si tu effectues la poursuite du sample de départ avec ce dictionnaire tu vas effectivement trouver comme solution:- l'atome qui est la version normée du sample inconnu
- la corrélation associée (i.e: la racine carrée de l'énergie du sample)
Au lieu de quelque chose de débile, je trouve au contraire que c'est le nirvana de la compression de données. Il y a juste à stocker l'index de l'atome et la corrélation. Et la compression est sans pertes
Aux chi*ttes les mp3.Bon d'accord, tant qu'on saura pas faire ça en un temps raisonnable, en analyse et en synthèse, ça reste du rêve
et heu.. c'est pas demain la veille.Mais peut-être avais-tu autre chose en tête au sujet de cette unicité
Citation : un des medailles Field de cette annee, le fameux Terence Tao, s'interesse a ce type de problemes
Ouais ce mec est monstrueux, il travaille vraiment tous azimuts
batman14 >
Citation : De plus, dans le domaine de l'audio, est ce nécessaire d'avoir une analyse plus fine que celle que l'on a déjà ?
Soit, tu peux faire des STFT glissantes avec une 'bonne' fenêtre de pondération de durée fixe. Mais à cause de cette durée fixe, tu te condamnes à une certaine résolution temps/fréquence. Si tu vas plus loin et que tu envisages plusieurs STFT avec des durées différentes, tu tombes sur la difficulté de la hierarchisation des pics. En utilisant une décomposition adaptative basée sur un dictionnaire qui contient une grande variété d'événements temps/fréquence, tu résous la difficulté de façon élégante, car cette hiérarchisation se fait de manière naturelle dans l'algo. Tout se passe comme si les pics les plus énergétiques étaient gommés du signal, au fur et à mesure.Citation : mais d'une manière générale, on a peut d'effets sonores adaptifs à l'heure actuelle
La décomposition est adaptative, ça veut pas forcément dire que les effets le soient! On peut voir MP comme de l'analyse granulaire: en fin d'analyse tu te retrouves avec une somme finie d'événements temps/fréquence, parfaitement quantifiés, par énergies décroissantes. Après tu en fais absolument ce que tu veux! Soit tu fais du clustering plus ou moins intelligent et tu retombes dans les grands classiques du traitement du signal: débruitage, détection de contours (en l'occurrence: attaques), décorrélation, séparation de sources, compression de données. Soit tu vas vers la (re)synthèse et vraiment il y a moyen de produire des effets extrèmement sophistiqués, comme des échos qui n'agissent que sur des bandes de fréquences très étroites, ou bien de la compression de dynamique intelligente qui n'agit que sur des notes isolées et pas sur des accords, etc..A ce niveau-là tu n'es limité que par ton imagination
Pour en revenir à un sujet de thèse possible, une idée serait d'écrire un framework d'exploration des effets possibles, justement. On pourrait imaginer un soft qui applique des régles sous forme de scripts. Dans cette perspective, à la limite t'as même pas besoin d'implémenter MP. Suffirait que tu te constitues un catalogue d'une dizaine de sons réels dont tu ferais calculer les poursuites par un toolkit quelconque une fois pour toutes.
Pour ma part, ma bidouille de MP remonte à 1 an et demi et je m'étais intéressé à ce que je suggérais dans le post #390: observer comment la parcimonie peut varier suivant le dictionnaire de départ, avec dans l'idée de faire de la synthèse de façon économique. Je me souviens être arrivé à un résultat absolument sensationnel sur des samples de balaphon et de tabla. Avec un dictionnaire de chirps hyperboliques dont l'enveloppe était la fonction FoF je suis arrivé à capturer 40 dB de l'énergie de départ avec moins de 10 atomes. Et je peux t'assurer que le signal reconstitué avec cette poignée d'atomes était vraiment très proche du signal de départ, et débruité qui plus est
Pour te donner une idée, il fallait plusieurs centaines d'atomes dans le cas d'un dictionnaire de Gabor pour arriver à la même qualité de poursuite.
La fonction FoF (cf Gribonval) est une enveloppe qui est appropriée à la détection d'événements musicaux, vu qu'elle atteint son maximum dans le voisinage du début du support, contrairement à une gaussienne
Le projet était tombé à l'eau, comme beaucoup de mes bidouilles, mais néanmoins je suis sûr et certain de me replonger dedans un jour. J'attends juste d'avoir les idées un peu plus claires en AI avant d'y retoucher ;)
batman14
Pov Gabou
Citation :
Je sais, ça fait bizarre mais c'est les termes employés dans les publis en français sur le sujet.
C'est surtout que je lis jamais rien en Francais (je fais une these au Japon, alors le francais...), et tout ces termes, je les connais pas en francais (redondant, j'aurais pu m'en rapperler
).Citation :
D'autre part, ceux-ci sont peut-être 'vieux' mais ça n'empêche pas qu'ils soient optimaux en résolution temps/fréquence
Vieux n'etait certainement pas pejoratif lorsque je l'utilisais ;)
Citation :
OR cette formule suppose qu'on a des ressources mémoire illimitées pour stocker les précieuses corrélations croisées <gi,gj> ce qui est loin d'être le cas dans la réalité, en dehors de samples courts. Quelqu'un qui voudrait implémenter sur des signaux quelconques serait obligé de laisser tomber cette implémentation et d'en trouver une meilleure. S'il n'en trouve pas, il devra tout faire en brute force => il est ramené au NP-hard.
Bon, je connais pas trop les champs d'applications du MP, j'ai pas pousse le truc super loin dans mes lectures, mais si tu peux pas stocker les correlations <gi, gj>, je vois pas tres bien les applications possibles. Parce qu'avoir un algo NP pour de la representation, ca me parait totalement irrealiste, surtout si tu parles de compression (pour les effets audio, c'est encore autre chose).
Citation :
Exact, dans ce cas la poursuite se résume à un seul atome. Mais il faudra effectuer les P corrélations entre le signal et chacun des P atomes du dictionnaire avant d'arriver à cette conclusion. On peut pas vraiment dire qu'il n'y a rien à faire. Quand tu dis que le résultat est débile, imagine cette expérience de pensée: on considère un sample inconnu, mono de longueur 1000 échantillonné en 16 bits. On considère d'autre part LE dictionnaire 'exhaustif' dont les atomes sont tous les signaux normés de longueur 1000 possibles. Le nombre d'atomes est astronomique. Si tu effectues la poursuite du sample de départ avec ce dictionnaire tu vas effectivement trouver comme solution:
- l'atome qui est la version normée du sample inconnu
- la corrélation associée (i.e: la racine carrée de l'énergie du sample)
Au lieu de quelque chose de débile,
Si ton dictionnaire contient une base, c'est evident qu'a la fin tu retrouves le signal de depart, c'est ca que je voulais dire (dans ma critique du MP "NP complet").
Citation :
Il y a juste à stocker l'index de l'atome et la corrélation. Et la compression est sans pertes Aux chi*ttes les mp3.
Ca me parait un peu bizarre de parler de compression si ton dictionnaire contient tous les atomes possibles; je vois pas la difference entre ce que tu dis et avoir en memoire tous les signaux possibles... La compression dont tu parles sans perte n'est pas possible, ne serait-ce qu'en invoquant la theorie de Shanon... Par contre, si tu acceptes une perte, et que tu arrives a trouver un critere de cout qui soit pertinent au niveau perceptif, ca devient beaucoup plus interessant (et t'as un sacre algo en mains, a mon avis, si tu arrives a trouver un truc suffiasament rapide dans ce cadre).
Il me semble plutot que la recherche (mais je suis pas trop ce qui s'y passe en musique, et en parole, les contraintes sont pas du tout les memes) se focalise sur le codage avec un model de signal (par exemple sinus + bruit) plutot que sur le codage de l'onde directement (il me semble que l'impression generale, c'est qu'on est un peu arrive au bout de ce qui est possible avec les derniers codeurs audio qui donnent un signal "correct" pour un taux de compression de 90%).
Pov Gabou
- < Liste des sujets
- Charte