Journal
Ce journal contient 6 entrées.
RSS Feed
Tag cloud
Computing linear regression in one pass
Dans le même ordre d'idée que le lien précédent, sauf qu'il s'agit cette fois d'effectuer une régression linéaire en continu. Comme beaucoup d'algorithmes continu, il présente l'avantage de travailler en mémoire constante.
Le thumbnail vient de XKCD : https://xkcd.com/1725
lun. 10 avril 2017 10:32:57 CEST -
-
link
- https://www.johndcook.com/blog/running_regression/
mathématiques statistiques stream-processing
Le thumbnail vient de XKCD : https://xkcd.com/1725
lun. 10 avril 2017 10:32:57 CEST -
-
link
- https://www.johndcook.com/blog/running_regression/
mathématiques statistiques stream-processing
Computing skewness and kurtosis in one pass
Comme vous l'avez peut être déjà remarqué, une bonne partie de mes travaux de thèse ont porté sur le traitement continu de flux de données : http://benjaminbillet.fr/media/benjaminbillet_memoire.pdf
De fait, je m'intéresse beaucoup aux techniques mathématiques permettant de réaliser des calculs en continu (c'est-à-dire sans mémoriser l'intégralité des résultats passés).
Cet article de blog décrit comment calculer en continu l'espérance, la variance, l'écart-type, le coefficient de dissymétrie et le coefficient d'aplatissement sur un flux d'échantillons. De manière plus générale il s'agit d'une méthode pour calculer les moments (https://fr.wikipedia.org/wiki/Moment_%28mathématiques%29). On pourrait imaginer donc l'utiliser pour calculer d'autres mesures statistiques d'ordre supérieur. J'essayerais d'ailleurs, si je parviens à bien tout comprendre, d'en faire une implémentation généralisée :)
Quelques références:
- B. P. Welford (1962)."Note on a method for calculating corrected sums of squares and products".
- Donald E. Knuth (1998). The Art of Computer Programming, volume 2: Seminumerical Algorithms, 3rd edn.
lun. 10 avril 2017 10:22:27 CEST -
-
link
- https://www.johndcook.com/blog/skewness_kurtosis/
mathématiques statistiques stream-processing
De fait, je m'intéresse beaucoup aux techniques mathématiques permettant de réaliser des calculs en continu (c'est-à-dire sans mémoriser l'intégralité des résultats passés).
Cet article de blog décrit comment calculer en continu l'espérance, la variance, l'écart-type, le coefficient de dissymétrie et le coefficient d'aplatissement sur un flux d'échantillons. De manière plus générale il s'agit d'une méthode pour calculer les moments (https://fr.wikipedia.org/wiki/Moment_%28mathématiques%29). On pourrait imaginer donc l'utiliser pour calculer d'autres mesures statistiques d'ordre supérieur. J'essayerais d'ailleurs, si je parviens à bien tout comprendre, d'en faire une implémentation généralisée :)
Quelques références:
- B. P. Welford (1962)."Note on a method for calculating corrected sums of squares and products".
- Donald E. Knuth (1998). The Art of Computer Programming, volume 2: Seminumerical Algorithms, 3rd edn.
lun. 10 avril 2017 10:22:27 CEST -
-
link
- https://www.johndcook.com/blog/skewness_kurtosis/
mathématiques statistiques stream-processing
3 years of work
C'est quoi une thèse ? 3 ans de travail et 180 tableaux blancs résumés en 11 secondes :')
http://benjaminbillet.fr/media/3yearsofwork.mp4
dim. 06 sept. 2015 20:48:17 CEST -
-
link
- http://benjaminbillet.fr/media/3yearsofwork.mp4
informatique stream-processing recherche
http://benjaminbillet.fr/media/3yearsofwork.mp4
dim. 06 sept. 2015 20:48:17 CEST -
-
link
- http://benjaminbillet.fr/media/3yearsofwork.mp4
informatique stream-processing recherche
Dioptase: Data Stream Processing for the Future Internet of Things
Oh, mon équipe vient de créer une page dédiée à mon middleware de traitement de flux pour l'Internet des objets.
jeu. 12 févr. 2015 11:55:35 CET -
-
link
- https://mimove.inria.fr/dioptase
stream-processing middleware
jeu. 12 févr. 2015 11:55:35 CET -
-
link
- https://mimove.inria.fr/dioptase
stream-processing middleware
Continuous processing vs Streaming algorithm
J'ai vu passer ce lien récemment dans mes flux RSS, qui présente l'algorithme de Morris comme le premier "streaming algorithm". C'est peut être une lubie de jeune chercheur borné, mais le terme streaming algorithm constitue un abus de langage malheureusement assez répandu. Le verbe "stream" en anglais courant se traduit en "ruisseler", tandis qu'il est utilisé figurativement en informatique pour désigner la transmission de données en flux continu.
Il ne faut donc pas confondre :
- le flux de données (data stream), qui s'apparente à un modèle de données utilisé dans deux cas : (i) décrire des informations dépendantes du temps et (ii) décrire des jeux de données si grand qu'il est impossible de les stocker. Dans les deux cas, la notion de temps est importante car, à un instant t donné, on ne connaît qu'une infime partie des informations du flux.
- la diffusion de flux (data streaming), qui correspond aux différentes techniques permettant de maintenir un flux de données entre un émetteur et un récepteur. Ces techniques comprennent la diffusion audio/vidéo mais aussi la diffusion de flux d'informations plus "petites" ; par exemple, les mesures produites en continu par des capteurs embarqués.
- le traitement continu/traitement de flux (continous processing/stream processing), qui s'apparente à un modèle de calcul utilisé pour traiter les informations d'un flux au fur et à mesure de leur réception. A un instant t, un opérateur de traitement continu traite la partie connue du flux et produit des résultats qui composeront un nouveau flux de données. C'est à cette catégorie qu'appartient l'algorithme de Morris.
Concrètement, j'ignore pourquoi le terme streaming algorithm est employé à la place de continuous processing algorithm, mais il semble que ce soit passé dans les moeurs malgré sa sémantique discutable. Comme je vois souvent ce terme employé pour des travaux d'algorithmique, j'imagine que les informaticiens théoriques s'intéressent aux problèmes de traitement plutôt qu'aux problèmes de diffusion. Pourtant, si l'on lit les papiers cités comme des streaming algorithms, aucun d'entre eux ne fait référence à ce terme, de près ou de loin :
- Algorithme de Morris : http://www.inf.ed.ac.uk/teaching/courses/exc/reading/morris.pdf
- Alon-Matias-Szegedy sketch (AMS) : http://courses.cs.washington.edu/courses/cse590z/03wi/alonmatiasszegedy.pdf
- Flajolet-Martin sketch (FMS) : http://algo.inria.fr/flajolet/Publications/FlMa85.pdf
- Count-min sketch (CMS) : http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf (pourtant en 2004 !)
Même Wikipédia s'y laisse prendre : http://en.wikipedia.org/wiki/Streaming_algorithm
Ils citent AMS comme ayant formalisé et popularisé les "streaming algorithms" alors que le papier sur AMS n'emploie jamais ce terme. Dès lors, comment les auteurs auraient pu en formaliser le concept ?
C'est d'autant plus problématique qu'en employant le terme "data streaming" pour ce qui est en réalité du traitement continu, cela induit une confusion entre les problématiques théoriques posées par le traitement continu u et les aspects pratiques liés à la diffusion de flux : maintien et reprise des flux, gestion de l'ordre, détection et correction d'erreurs.
Pour en revenir à l'algorithme de Morris, il appartient à une famille d'algorithme de traitement continu nommée "synopsis methods", ce qui est difficile à traduire (méthode à synopsis ?). La métaphore derrière ces techniques emprunte au cinéma, où un synopsis est un résumé très court d'un scénario : une "synopsis method" est un opérateur qui produit des résultats approchés (avec ou sans erreur bornée) en ne maintenant en mémoire qu'un "résumé" du flux (le synopsis).
Concrètement, l'algorithme de Morris n'est ni plus ni moins qu'un "SELECT COUNT(x) GROUP BY x" approché. Dans le même genre, FMS (Flajolet-Martin sketch) est un "COUNT DISTINCT(x)" approché.
Si vous n'êtes pas trop rebutés par les maths et l'anglais, ce document donne une vue d'ensemble des synopsis methods par types (échantillonnage, sketches, etc.), avec quelques méthodes décrites en détail :
http://charuaggarwal.net/synopsis.pdf
Au final, l'avantage de telles techniques provient de la très faible quantité de mémoire nécessaire mais leur principal défaut réside dans leur ultra-spécialisation ; par exemple, AMS permet de calculer la taille approximative du résultat d'une jointure mais pas le contenu de la jointure elle même.
La littérature sur le traitement continu est donc très riche malgré la "jeunesse" du domaine. C'est cependant un problème majeur dans le traitement des très grands volumes de données, si grands qu'il est impossible de les stocker. Pour donner une idée, Walmart produit plusieurs tera-octets d'évènements RFID... par jour (de 10 à 100 To selon les sources).
mar. 10 févr. 2015 14:03:33 CET -
-
link
- http://page.mi.fu-berlin.de/kashif/algorithm/2014/10/17/morris-algorithm.html
stream-processing
Il ne faut donc pas confondre :
- le flux de données (data stream), qui s'apparente à un modèle de données utilisé dans deux cas : (i) décrire des informations dépendantes du temps et (ii) décrire des jeux de données si grand qu'il est impossible de les stocker. Dans les deux cas, la notion de temps est importante car, à un instant t donné, on ne connaît qu'une infime partie des informations du flux.
- la diffusion de flux (data streaming), qui correspond aux différentes techniques permettant de maintenir un flux de données entre un émetteur et un récepteur. Ces techniques comprennent la diffusion audio/vidéo mais aussi la diffusion de flux d'informations plus "petites" ; par exemple, les mesures produites en continu par des capteurs embarqués.
- le traitement continu/traitement de flux (continous processing/stream processing), qui s'apparente à un modèle de calcul utilisé pour traiter les informations d'un flux au fur et à mesure de leur réception. A un instant t, un opérateur de traitement continu traite la partie connue du flux et produit des résultats qui composeront un nouveau flux de données. C'est à cette catégorie qu'appartient l'algorithme de Morris.
Concrètement, j'ignore pourquoi le terme streaming algorithm est employé à la place de continuous processing algorithm, mais il semble que ce soit passé dans les moeurs malgré sa sémantique discutable. Comme je vois souvent ce terme employé pour des travaux d'algorithmique, j'imagine que les informaticiens théoriques s'intéressent aux problèmes de traitement plutôt qu'aux problèmes de diffusion. Pourtant, si l'on lit les papiers cités comme des streaming algorithms, aucun d'entre eux ne fait référence à ce terme, de près ou de loin :
- Algorithme de Morris : http://www.inf.ed.ac.uk/teaching/courses/exc/reading/morris.pdf
- Alon-Matias-Szegedy sketch (AMS) : http://courses.cs.washington.edu/courses/cse590z/03wi/alonmatiasszegedy.pdf
- Flajolet-Martin sketch (FMS) : http://algo.inria.fr/flajolet/Publications/FlMa85.pdf
- Count-min sketch (CMS) : http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf (pourtant en 2004 !)
Même Wikipédia s'y laisse prendre : http://en.wikipedia.org/wiki/Streaming_algorithm
Ils citent AMS comme ayant formalisé et popularisé les "streaming algorithms" alors que le papier sur AMS n'emploie jamais ce terme. Dès lors, comment les auteurs auraient pu en formaliser le concept ?
C'est d'autant plus problématique qu'en employant le terme "data streaming" pour ce qui est en réalité du traitement continu, cela induit une confusion entre les problématiques théoriques posées par le traitement continu u et les aspects pratiques liés à la diffusion de flux : maintien et reprise des flux, gestion de l'ordre, détection et correction d'erreurs.
Pour en revenir à l'algorithme de Morris, il appartient à une famille d'algorithme de traitement continu nommée "synopsis methods", ce qui est difficile à traduire (méthode à synopsis ?). La métaphore derrière ces techniques emprunte au cinéma, où un synopsis est un résumé très court d'un scénario : une "synopsis method" est un opérateur qui produit des résultats approchés (avec ou sans erreur bornée) en ne maintenant en mémoire qu'un "résumé" du flux (le synopsis).
Concrètement, l'algorithme de Morris n'est ni plus ni moins qu'un "SELECT COUNT(x) GROUP BY x" approché. Dans le même genre, FMS (Flajolet-Martin sketch) est un "COUNT DISTINCT(x)" approché.
Si vous n'êtes pas trop rebutés par les maths et l'anglais, ce document donne une vue d'ensemble des synopsis methods par types (échantillonnage, sketches, etc.), avec quelques méthodes décrites en détail :
http://charuaggarwal.net/synopsis.pdf
Au final, l'avantage de telles techniques provient de la très faible quantité de mémoire nécessaire mais leur principal défaut réside dans leur ultra-spécialisation ; par exemple, AMS permet de calculer la taille approximative du résultat d'une jointure mais pas le contenu de la jointure elle même.
La littérature sur le traitement continu est donc très riche malgré la "jeunesse" du domaine. C'est cependant un problème majeur dans le traitement des très grands volumes de données, si grands qu'il est impossible de les stocker. Pour donner une idée, Walmart produit plusieurs tera-octets d'évènements RFID... par jour (de 10 à 100 To selon les sources).
mar. 10 févr. 2015 14:03:33 CET -
-
link
- http://page.mi.fu-berlin.de/kashif/algorithm/2014/10/17/morris-algorithm.html
stream-processing
Mining of Massive Datasets
Un super bouquin sur le data mining, dont la couverture est certes moche, mais dont vous pouvez lire le contenu en ligne.
J'apprécie tout particulièrement son chapitre sur le stream processing, qui me concerne spécifiquement.
J'ai fait un backup du PDF du livre ici : http://benjaminbillet.fr/media/mining-of-massive-datasets.pdf
mer. 11 déc. 2013 19:36:15 CET -
-
link
- http://infolab.stanford.edu/~ullman/mmds.html
stream-processing datamining algorithmique
J'apprécie tout particulièrement son chapitre sur le stream processing, qui me concerne spécifiquement.
J'ai fait un backup du PDF du livre ici : http://benjaminbillet.fr/media/mining-of-massive-datasets.pdf
mer. 11 déc. 2013 19:36:15 CET -
-
link
- http://infolab.stanford.edu/~ullman/mmds.html
stream-processing datamining algorithmique
Ce journal est basé sur Ginger, un gestionnaire de lien minimaliste développé dans le cadre d'un stage de perfectionnement. Pour plus d'informations, consulter le wiki consacré à mes projets personnels.