Algorithmes de streaming

Bonjour,

Je pense que j’ai à peu près fini de parler de tous les sujets que je voulais aborder ou, a minima, mentionner concernant les problèmes de streaming algorithm.

La position est un peu difficile parce qu’il s’agit d’un sujet particulièrement orienté statistiques et avec des notions très avancées. J’ai essayé de ne pas trop m’y perdre en présentant davantage les briques qui composent ce champ et éviter de rentrer dans les détails (qui sont parfois très jolis).

Salut,

C’est intéressant, mais le niveau technique n’a pas été la difficulté principale pour moi en première lecture. J’ai eu plus de mal avec la clarté de l’exposition au début de chaque section et le liant, qui est primordial pour ne pas perdre le lecteur.

Aussi, j’ai l’impression que tu as très envie tout de suite de plonger dans l’analyse des algos, qui apporte certes de la valeur ajoutée, mais qui n’est pas efficace si on n’arrive pas à comprendre l’algorithme avant.

Je trouve que ça fait très catalogue à cause de ça, parce que le niveau de détails de l’analyse des algos tend à eclipser un peu l’exposition des idées principales que tu sembles vouloir faire. En tout cas, c’est mon impression.

J’ai du mal à savoir à la lecture si c’est pour découvrir ce sujet, même très technique, ou si c’est pour le comprendre en détail, notamment les démonstrations de correction.

Par exemple, pour le comptage approximatif, tu énonces quelques trivialités, puis tu balances sans cérémonie :

Dans le cas d’un comptage approximatif, on cherche un $\tilde{N}$ tel que $P(∣\tilde{N}−N∣>\epsilon N)< \delta$.

Une petite phrase pour dire "On cherche un estimateur du nombre effectif d’événements tel que les chances de trop se tromper soient suffisamment faibles", et peut-être rattacher ça à la formule (on mesure l’erreur par l’erreur relative, on se donne un seuil à partir duquel on n’est plus satisfait et on se donne un autre seuil pour juger la probabilité, etc.).

Aussi, expliquer l’idée de l’algo peut faciliter la lecture. L’algo de Morris est clair, mais sans explication, c’est au lecteur de décoder l’idée, à savoir ne compter qu’une fraction variable des événements de manière à ce que l’exposant "tombe juste" en moyenne (et donc estime le nombre qu’on cherche).

Pour le « count distinct elements », c’est un peu pareil. Tu passes très vite au début. Je crois que tu ne dis à aucun moment de manière explicite qu’on cherche à estimer $t$, a priori inconnu. Au début je me disais "si on se donne t éléments distincts, à quoi ça sert de compter ?".

Tu passes aussi tellement vite sur HyperLogLog que pour moi, c’est comme si tu ne disais rien de plus que "Hyperloglog c’est fun jetez y un oeil, ils jouent avec les substreams".

« Linear sketching & Count-Min sketch », j’ai essentiellement rien compris, mais c’est peut-être que je me suis pas accroché assez.

Les aspects historiques des avancées de la discipline me font décrocher instantanément aussi. Je ne connais pas les chercheurs, je ne connais pas l’état de la recherche avant eux de toute façon et ça m’est égal en quelle année ils ont publié leur nouvelle idée. Pour une exposition au sujet, ça me passe complètement au dessus.

Pour « Sparce recovery », tu retombes dans le "j’explique pas j’expose" pour moi.

C’est quoi l ? C’est quoi z ? C’est quoi f ? C’est quoi les fj ? Pourquoi s n’apparaît pas dans la formule si c’est une hypothèse (parce qu’il est égal à 1 ?) ?

Et je ne suis pas sûr d’avoir compris, mais tu parles de fréquence nulle, mais t’as bien plus de s éléments distincts et on fait l’hypothèse que les autres sont négligeables ?

J’ai lu en travers les matrices, donc pas trop de commentaire dessus.

J’ai d’autres commentaires beaucoup plus mineurs, je les garde pour plus tard.

Bonjour Aabu,

Merci pour ton retour, c’est toujours très constructif.

C’est intéressant, mais le niveau technique n’a pas été la difficulté principale pour moi en première lecture. J’ai eu plus de mal avec la clarté de l’exposition au début de chaque section et le liant, qui est primordial pour ne pas perdre le lecteur.

J’ai essayé d’améliorer les différentes transitions en:

• Ajoutant une introduction décrivant les différents points qui seront abordés ici.
• Définissant ce qu’est un streaming algorithme, chose qui n’était pas faite 🤦‍♂️
• Essayant de mettre davantage en évidence les points principaux qui apparaissent dans les sections.

Aussi, j’ai l’impression que tu as très envie tout de suite de plonger dans l’analyse des algos, qui apporte certes de la valeur ajoutée, mais qui n’est pas efficace si on n’arrive pas à comprendre l’algorithme avant.

Je trouve que ça fait très catalogue à cause de ça, parce que le niveau de détails de l’analyse des algos tend à eclipser un peu l’exposition des idées principales que tu sembles vouloir faire. En tout cas, c’est mon impression.

J’ai du mal à savoir à la lecture si c’est pour découvrir ce sujet, même très technique, ou si c’est pour le comprendre en détail, notamment les démonstrations de correction.

Tu mets pile-poil le doigt sur ce qui me posait problème. Personnellement, je suis plus un papillon, c’est-à-dire que je m’intéresse surtout à l’articulation des idées sur un sujet, percevoir les principaux généraux, stocker ça dans ma tête et peut-être le ressortir de manière inattendu (comme ce problème de vérification formelle de programme que j’ai pu exploiter dans le cadre de détections des flux financiers).

Ce domaine est particulièrement retors parce que tu tombes très vite dans des montagnes de calcul afin d’obtenir un résultat. Je t’invite à ouvrir un des papiers de Flajolet, de ce style (Approximate counting: a detailed analysis). J’avais donc voulu montrer quels sont les deux points principaux pour étudier ce genre d’algorithmes (la justesse et les caractéristiques statistiques) sur deux exemples 'simples’.

Donc j’ai essayé d’insister sur le fait que c’est ça l’objectif d’un chercheur et le type de techniques que l’on peut rencontrer. Et, après les deux exemples classico-classiques, que l’on se concentre sur les idées et non la démonstration per se.

---

Par exemple, pour le comptage approximatif, tu énonces quelques trivialités, puis tu balances sans cérémonie :

Dans le cas d’un comptage approximatif, on cherche un $\tilde{N}$ tel que $P(∣\tilde{N}−N∣>\epsilon N)< \delta$.

Une petite phrase pour dire "On cherche un estimateur du nombre effectif d’événements tel que les chances de trop se tromper soient suffisamment faibles", et peut-être rattacher ça à la formule (on mesure l’erreur par l’erreur relative, on se donne un seuil à partir duquel on n’est plus satisfait et on se donne un autre seuil pour juger la probabilité, etc.).

Aussi, expliquer l’idée de l’algo peut faciliter la lecture. L’algo de Morris est clair, mais sans explication, c’est au lecteur de décoder l’idée, à savoir ne compter qu’une fraction variable des événements de manière à ce que l’exposant "tombe juste" en moyenne (et donc estime le nombre qu’on cherche).

Que c’est joliment exprimé, je te la reprends

---

Pour le « count distinct elements », c’est un peu pareil. Tu passes très vite au début. Je crois que tu ne dis à aucun moment de manière explicite qu’on cherche à estimer $t$, a priori inconnu. Au début je me disais "si on se donne t éléments distincts, à quoi ça sert de compter ?".

Tu passes aussi tellement vite sur HyperLogLog que pour moi, c’est comme si tu ne disais rien de plus que "Hyperloglog c’est fun jetez y un oeil, ils jouent avec les substreams".

En même temps, il n’y a rien à dire dessus. C’est juste l’application bête et méchante de l’algorithme de Flajolet et Martin (mais avec plusieurs estimateurs). J’ai complété quand même.

---

« Linear sketching & Count-Min sketch », j’ai essentiellement rien compris, mais c’est peut-être que je me suis pas accroché assez.

Les aspects historiques des avancées de la discipline me font décrocher instantanément aussi. Je ne connais pas les chercheurs, je ne connais pas l’état de la recherche avant eux de toute façon et ça m’est égal en quelle année ils ont publié leur nouvelle idée. Pour une exposition au sujet, ça me passe complètement au dessus.

Aie, aie, aie. C’est dommage que j’ai à ce point-là raté alors que c’est vraiment l’esthétisme de ce domaine.

---

Pour « Sparce recovery », tu retombes dans le "j’explique pas j’expose" pour moi.

C’est quoi l ? C’est quoi z ? C’est quoi f ? C’est quoi les fj ? Pourquoi s n’apparaît pas dans la formule si c’est une hypothèse (parce qu’il est égal à 1 ?) ?

Et je ne suis pas sûr d’avoir compris, mais tu parles de fréquence nulle, mais t’as bien plus de s éléments distincts et on fait l’hypothèse que les autres sont négligeables ?

J’ai essayé de corriger ça. J’espère que c’est mieux.

Je vais encore repasser une fois dessus s’il n’y a pas d’autres remarques.

Ce domaine est particulièrement retors parce que tu tombes très vite dans des montagnes de calcul afin d’obtenir un résultat. Je t’invite à ouvrir un des papiers de Flajolet, de ce style (Approximate counting: a detailed analysis).

C’est un problème spécifique à Flajolet, qui adorait tout calculer avec trois termes de développement asymptotique (personne ne fait ça). Par exemple, l’article d’Alon-Matias-Szegedy est plus facile à lire.

Un autre problème avec Flajolet c’est que dans tous ses articles il suppose implicitement l’existence de fonctions de hachage aléatoires qu’on est (très) loin de savoir construire avec aussi peu de mémoire — d’ailleurs "l’algorithme réaliste" que tu décris pour $F_0$ est ultérieur à Flajolet-Martin. Et ça vaut aussi pour cet 'hyperloglog’…