Les matheux sont dans la place - pt=prout

[FMP-thE_mAd]

C'est évident quand tu réfléchis à la contraposé. Si tu avais une probabilité non nulle p d'être sur un segment, la probabilité d'être dans un ensemble de p+1 segments disjoints est supérieure à 1.

Je vois pas bien ton calcul avec le p+1. Tu additionnes une proba avec un nombre de segment ???
Je vois ce que tu veux dire, mais je pense que tu le dis mal :

Soit p(être sur un segment) = p1 avec P1<>0, alors il existe n entier tel que n*p1>1.
Et donc p(être sur n segments distincts)=p(segment 1)+p(segment2)+...+p(segment n)=p1+p1+...+p1=n*p1>1.
Effectivement.

[Souly]

Je vois pas bien ton calcul avec le p+1. Tu additionnes une proba avec un nombre de segment ???
Je vois ce que tu veux dire, mais je pense que tu le dis mal :

Soit p(être sur un segment) = p1 avec P1<>0, alors il existe n entier tel que n*p1>1.
Et donc p(être sur n segments distincts)=p(segment 1)+p(segment2)+...+p(segment n)=p1+p1+...+p1=n*p1>1.
Effectivement.

Oui effectivement, je vois pas non plus ce que j'ai voulu dire avec mon p+1 Ça devait être un E(1/p)+1 mal dégrossi.

[Orhin]

[Félire]

Juste pour faire suite à mes dernières questions sur ce topic. Finalement j'ai programmé un spectrogramme avec des transformées rapides de Fourier à court-terme. J'obtiens d'assez bons résultats. Merci à vous les canards !

[PMJ]

Petite question, je vais passer des tests d'entrée de l'afpa (...) pour une formation pro bts logistique. Donc il y aura surement un peu de maths niveau bac pro. A quel genre de merdier dois-je m'attendre ?

[BentheXIII]

Conclusion d'un projet d'estimation rigolol. Bon, j'ai un peu galéré avec le conditionnement de ma matrice d'information over 9000 mais un truc aussi naif que M = M + eye(M.shape) a suffit.

[Enyss]

Tu estimais quoi ?

[BentheXIII]

Une surface 3D discretisée en vertices et facettes. L'estimée que je reconstruis itérations aprés itérations est paramétrée de manière équivalente. La vidéo commence avec ma surface dite a-priori (c'est à dire l'estimée qui initialise le filter) et les images successives illustrent l'estimée convergeant vers la vrai forme ("truth") itérations après itérations. Cette"vraie" forme étant la surface sur laquelle N mesures de distance ont été prises au préalable. Une estimée parfaite doit donc fournir les mêmes mesures de distance que celles produites par la vraie forme.

C'est grosso-modo la définition d'un filtre hors-ligne dans le contexte d'un problème d'estimation arbitraire. Le challenge réside dans le caractère extrêmement non linéaire des dérivées partielles impliquée dans la synthèse du filtre, qui requiert donc un peu de tuning (au delà de la formulation et implementation de la minimisation des residus d'observation) pour converger.

[Autiste Redding]

Pardon aux familles si c'est déjà passé...

[FMP-thE_mAd]

Je me suis un peu amusé avec Scratch :



Mais bon, évidemment le rendu est hyper long là.
Et j'ai un peu cherché mais pas vraiment trouvé : est-ce qu'il existe des optimisations mathématiques qui permettraient de générer la fractale plus rapidement ? (notamment des tests à faire pour voir si la suite va diverger ou pas).
Parce qu'au départ j'étais parti pour faire une option "zoom" dessus, mais bon là ça a mis 45 minutes pour générer ce dessin (bon, j'affiche plein de points en trop aussi, faurdait que je calle mieux l'échelle par rapport à la taille du stylo, mais quand même).

[Møgluglu]

Et j'ai un peu cherché mais pas vraiment trouvé : est-ce qu'il existe des optimisations mathématiques qui permettraient de générer la fractale plus rapidement ? (notamment des tests à faire pour voir si la suite va diverger ou pas).

Pas dans les zones "intéressantes" vu que c'est chaotique. Sur la partie centrale éventuellement, avec une comparaison avec une valeur arbitraire pour laisser tomber là où tu es sûr que 10 itérations ne suffiront pas.

Sinon faut optimiser le calcul lui-même (voire l'interpréteur scratch), si ça prend 45 minutes sur un ordinateur du 21e siècle c'est qu'il y a de la marge.
Ou alors tu as finalement réussi à installer Scratch sur ton Amiga ?

[FMP-thE_mAd]

Ouais je vois pas trop comment optimiser les calculs du coup. Vu que je suis limité aux fonctions de calculs de Scratch. Peut-être en décomposant les calculs ça irait plus vite ? (plutôt que de tout mettre dans une commande verte). Faut que je teste.

Ca va déjà un peu plus vite sur la version offline (la photo précédente c'est sur la version online de Scratch).
Avec 20 itérations, en 40 minutes j'ai ça :

[Enyss]

Il y a un problème : ça ne devrait pas mettre 40 min pour tracer 100k points (surtout avec 20 itérations max').

Après, c'est peut-être la procédure de dessin de scratch qui est affreusement lente. Essaye de voir combien de temps ton algo met si tu ne dessines pas les points

[FMP-thE_mAd]

Ouais je pense que la clé c'est bien le dessin. Sur Scratch c'est un crayon qui se déplace, et c'est hyper lent. Même sur des programmes simples, on voit le dessin se faire.
Je vais optimiser pour n'afficher que des pixels réels, ça ira déjà plus vite.

Bonne idée le coup du programme sans dessin. Je teste ça de suite.

EDIT : oui bah c'est le problème effectivement. Ca a mis 3s pour calculer les 84 000 points sans les tracer.
Bon bah flûte...
Ah moins que du coup je les mette en mémoire puis je les trace... damned...

EDIT 2 : nan bah mettre les résultats dans une liste ça rend pas le dessin plus rapide... Autant le faire directement.

[Janer]

Je suis pas encore super à l'aise, est-ce que quel qu'un qui s'y connaît pourrait jeter un oeil à ma fonction pour créer un moyenne glissante sur un tableau à deux dimension en python?

def SmoothMap(array, radius, xSizeM, ySizeM): #custom SmoothFunction more suited than the Gaussian
pixelX = len(array)
pixelY = len(array[0])

xRadius = int(radius/xSizeM * pixelX)
yRadius = int(radius/ySizeM * pixelY)

#pad the array
padded_array = np.pad(array, (xRadius, yRadius), 'symmetric')

#build kernel
g = np.ones((xRadius*2, yRadius*2))
g = (g / g.sum()).astype(array.dtype)

#smooth
return fftconvolve(padded_array, g, mode='valid')

[Dr.Kant]

Je suis pas expert, mais ca a l'air de faire ce que tu decris. J'aurai peut etre utilise un array.shape() pour les dimensions des pixels, et fait attention au typage de radius et xSizeM dans les divisions. Tu peux faire un exemple minimal pour verifier, du type array = zeros partout sauf au centre.

[Aghora]

Je connais pas le langage python.

Moi ce que je ferais, c'est une fenêtre en 2D centrée sur une case de ton tableau qui prendra la valeur moyenne de toutes les cases dans la fenêtre.

Comme je l'ai dis, je connais pas le langage. Mais quand je vois "fftconvolve", je suis un peu dubitatif, à moins que ce soit une manière rapide de décaler ta fenêtre...

[Dr.Kant]

De memoire, fftconvolve opere une operation de convolution en passant dans le domaine de Fourier. Ca a du sens si ton tableau est suffisamment large.

[Janer]

Je suis pas expert, mais ca a l'air de faire ce que tu decris. J'aurai peut etre utilise un array.shape() pour les dimensions des pixels, et fait attention au typage de radius et xSizeM dans les divisions. Tu peux faire un exemple minimal pour verifier, du type array = zeros partout sauf au centre.

Bien vu. Merci! Je m'inquiétais aussi pour les bords, du coup le tableau minimal peut aider.

Je connais pas le langage python.

Moi ce que je ferais, c'est une fenêtre en 2D centrée sur une case de ton tableau qui prendra la valeur moyenne de toutes les cases dans la fenêtre.

Comme je l'ai dis, je connais pas le langage. Mais quand je vois "fftconvolve", je suis un peu dubitatif, à moins que ce soit une manière rapide de décaler ta fenêtre...

Je travaille sur une image de résolution 8192*8192 qui représente des densités de population autour de Paris, ce qui fait déjà 67 108 864 pixels à parcourir, et pour chacun de ces pixels, devoir faire une moyenne sur fenêtre de dimension de l'ordre de 10^3*10^3. Cela fait énormément de calcul avec la méthode brut, au début je me disais que c'était pas grave parce que je ne dois faire le calcul qu'une fois, mais c'était déjà de l'ordre de l'heure et c'est très chiant pour faire des essais.

Ensuite je me suis dit que je pouvais écrire ma propre fonction optimisée pour ne pas refaire des calcul (à chaque fois que la fenêtre glisse, ne pas tout resommer, juste soustraire ce qui sort du cadre et mettre ce qui rendre dedans), mais il était tard, j'étais fatigué, je voulais pas me prendre la tête avec les effets de bord du coup j'ai pensé utiliser une convolution avec une fonction uniforme 1/n, n étant le nombre de cases dans le pixel, cela revient à faire une moyenne glissante.

De memoire, fftconvolve opere une operation de convolution en passant dans le domaine de Fourier. Ca a du sens si ton tableau est suffisamment large.

Oui voilà!


Pour info le résultat :

[Møgluglu]

Ensuite je me suis dit que je pouvais écrire ma propre fonction optimisée pour ne pas refaire des calcul (à chaque fois que la fenêtre glisse, ne pas tout resommer, juste soustraire ce qui sort du cadre et mettre ce qui rendre dedans), mais il était tard, j'étais fatigué, je voulais pas me prendre la tête avec les effets de bord du coup j'ai pensé utiliser une convolution avec une fonction uniforme 1/n, n étant le nombre de cases dans le pixel, cela revient à faire une moyenne glissante.

En théorie, l'algo à base de fenêtre glissante sera bien plus efficace (O(n) au lieu de O(n log n) pour la FFT).
Maintenant, si tu programmes en Python, tu te bouffes un facteur 100 ou 1000 par rapport au code optimisé, parallélisé et vectorisé de la FFT, donc ton implème de l'algo risque d'être à la rue quand-même. Ou alors tu fais le calcul en C, C++ ou Fortran. Python c'est bien pour coller des briques de calcul ensemble pour construire des protos, comme tu fais, mais pas plus.

Aussi, question stabilité numérique, je me méfierais d'une FFT avec fonction 1/n, mais si tu sais vérifier les résultats pourquoi pas.

[Laya]

En théorie, l'algo à base de fenêtre glissante sera bien plus efficace (O(n) au lieu de O(n log n) pour la FFT).
Maintenant, si tu programmes en Python, tu te bouffes un facteur 100 ou 1000 par rapport au code optimisé, parallélisé et vectorisé de la FFT, donc ton implème de l'algo risque d'être à la rue quand-même. Ou alors tu fais le calcul en C, C++ ou Fortran. Python c'est bien pour coller des briques de calcul ensemble pour construire des protos, comme tu fais, mais pas plus.

Je croyais que la plupart des outils d'algèbres utilisés en python était des appelles à des libraires fortran. Ils ont recoder le tout en full python?

[Møgluglu]

Je croyais que la plupart des outils d'algèbres utilisés en python était des appelles à des libraires fortran.

Oui, c'est ça. Si tu te contentes d'utiliser des fonctions de haut niveau genre fftconvolve en les branchant les unes à la suite des autres, avec un peu de chance tu auras des perfs raisonnables. Par contre si tu écris ton propre algo de calcul entièrement en Python, tu auras des perfs de merde même si ton algo est bien meilleur. C'est pas fait pour.

Ou tant qu'à faire tu codes ça en Scratch.

[Laya]

Oui, c'est ça. Si tu te contentes d'utiliser des fonctions de haut niveau genre fftconvolve en les branchant les unes à la suite des autres, avec un peu de chance tu auras des perfs raisonnables. Par contre si tu écris ton propre algo de calcul entièrement en Python, tu auras des perfs de merde même si ton algo est bien meilleur. C'est pas fait pour.

Ou tant qu'à faire tu codes ça en Scratch.

Ok, merci pour les précisions. Sinon tu utilises pypy. C'est un assez bon compromis sans passer à des langage de bas niveau.
http://pypy.org/

[Janer]

En théorie, l'algo à base de fenêtre glissante sera bien plus efficace (O(n) au lieu de O(n log n) pour la FFT).
Maintenant, si tu programmes en Python, tu te bouffes un facteur 100 ou 1000 par rapport au code optimisé, parallélisé et vectorisé de la FFT, donc ton implème de l'algo risque d'être à la rue quand-même. Ou alors tu fais le calcul en C, C++ ou Fortran. Python c'est bien pour coller des briques de calcul ensemble pour construire des protos, comme tu fais, mais pas plus.

Aussi, question stabilité numérique, je me méfierais d'une FFT avec fonction 1/n, mais si tu sais vérifier les résultats pourquoi pas.

Euh tu es sûr pour la fenêtre glissante? Parce que ok y'a le O(n) de l'exploration mais ensuite pour calculer la moyenne sur chaque point il faut multiplier par la dimension de la fenêtre (en force brut). Sinon y'a un aussi une fonction de convolution discrète pure, un peu équivalente à celle que je voulais imaginer, mais elle aussi est plus lente que FFT bien que plus précise. Si j'écrivais ma fonction je l'aurais écris en autre chose que Python (genre Julia ou C) puis je l'aurais intégré. J'utilise en effet Python pour interfacer tout mon programme.

Sinon pour la stabilité, le minimum et le maximum se partent pas en couille et la convolution est une opération régularisante donc je le sens bien.

[Møgluglu]

Pour calculer pour tout n les sommes S_n depuis i=n jusqu'à i=n+c des a_i, tu calcules S_0, puis par récurrence S_(n+1) = S_n - a_n + a_(n+1+c). C'est ce que tu proposais d'ailleurs. Tu ne t'amuses pas à recalculer toutes les sommes intermédiaires.
Et en entier, le calcul est exact, ce qui est toujours mieux qu'un algo numérique approché aussi stable soit-il.

Laya: oui, Pypy ça a l'air pas mal pour récupérer un des ordres de grandeur perdu, et s'approcher de la perf d'un langage jitté à la Java/C#. Après Python reste un langage complèment dynamique, la génération de code est merdique par définition.

[Janer]

Pour calculer pour tout n les sommes S_n depuis i=n jusqu'à i=n+c des a_i, tu calcules S_0, puis par récurrence S_(n+1) = S_n - a_n + a_(n+1+c). C'est ce que tu proposais d'ailleurs. Tu ne t'amuses pas à recalculer toutes les sommes intermédiaires.
Et en entier, le calcul est exact, ce qui est toujours mieux qu'un algo numérique approché aussi stable soit-il.

Laya: oui, Pypy ça a l'air pas mal pour récupérer un des ordres de grandeur perdu, et s'approcher de la perf d'un langage jitté à la Java/C#. Après Python reste un langage complèment dynamique, la génération de code est merdique par définition.

Ah oui oui en ne recalculant pas tout bien sûr, je sais pas pourquoi je suis revenu à la solution naïve dans ma tête. Oui ce serait une solution exacte. Après parfois étant donné la nature du problème et la nature de ce que l'on veut faire, on a pas besoin d'une solution exacte! Et là je suis en train de faire une première approche, si ça se trouve je trouverai déjà un résultat satisfaisant sans rentrer dans les détails.

Ah et aussi je suis débutant, et je sais que l'algorithme pourrait être au minimum parallélisé (pas de résultat intermédiaires, on peut calculer tout "en même temps") ce qui pourrait diviser le temps de calcul... mais je débute et ce point n'est qu'un aspect du problème que j'essaye de traiter.

[Janer]

Sinon j'ai une idée et je voudrais juste une piste sur comment l'implémenter. En gros je fias un modèle prédictif, qui prédit des trucs à des endroits donnés, et je veux qu'il puisse prédire des trucs à des endroits sur lesquels je n'ai pas encore de donnés, en interpolant en quelque sorte le modèle entre les points où j'ai des données.

Mon idée c'est de créer une variable qui englobe tout ce que le modèle ne comprend pas et l'interpoler, mais je vois pas trop comment faire...

[Aghora]

Filtrage de Kalman peut-être ? Mais il te faut un modèle théorique de tes données et un modèle d'observation.

[Enyss]

Mon idée c'est de créer une variable qui englobe tout ce que le modèle ne comprend pas et l'interpoler, mais je vois pas trop comment faire...

Ça n'a, à mon avis, pas trop de sens... ou alors je n'ai pas compris ton idée

[Janer]

Je suis fatigué et j'ai du mal à m'exprimer, en gros c'est un modèle de prédiction sur des stations de transport et j'utilise des données historiques pour paramétrer le modèle. Je peux faire l'estimation pour l'ensemble des stations ou alors pour un modèle pour chaque station qui a ses particularités, le modèle sur chaque sation sera plus précis, mais il sera propre à chaque sation et je ne peux pas l'appliquer à une station hypothétique nouvelle ou alors à des stations qui manquent de données historiques. Et le modèle global risque d'être imprécis.

Mon idée est la suivante : les stations peuvent se paramétrer indépendamment, mais ce qui différencie une station d'une autre (géographiquement j'entends) n'est pas discret mais continu, c'est-à-dire, que pour une station donnée, je la déplace de 5m, le modèle ne doit varier que d'un peu (en gros la définition de la continuité non?), c'est une hypothèse empirique, mais elle me parraît très sensé. Du coup comme les stations pour lesquelles j'ai des données forment un quadrillage satisfaisant, mon idée c'est d'inclure d'une façon ou d'une autre une variable bâtarde qui comprendra tout ce qui est en rapport avec ce qui est géographique, et ensuite d'interpoler cette variable pour les stations pour lesquelles je n'ai pas pu estimer cette variable, soit parce que je n'ai pas de données, soit parce qu'elle n'existe pas encore!