Pourquoi un problème de ficelles révèle l'intelligence des data scientists ?

UN PROBLÈME SIMPLE QUI DÉCHIRE LES CERVEAUX

Pourquoi perdre son temps à résoudre un problème de probabilité absurde avec des ficelles au lieu de scroller sur TikTok ? Parce que c’est exactement le genre d’exercice qui maintient l’esprit vif dans une époque où l’intelligence artificielle générative peut prendre en charge une grande partie de notre réflexion critique. Si vous lisez des articles sur la data science, vous partagez probablement ce même objectif : garder son cerveau en forme.

Cet article propose de résoudre un casse-tête de probabilité lancé par un YouTubeur préféré, 3Blue1Brown. Ce créateur se distingue par des explications visuelles intuitives qui donnent envie de se demander pourquoi les maths sont enseignées autrement. La vidéo en lien offre la meilleure introduction, mais voici l’énoncé du problème pour compléter.

COMMENT FONCTIONNE LE JEU DES FICELLES ?

Si vous attachez deux ficelles différentes, vous remettez la ficelle plus longue dans la boîte. Si vous formez une boucle, vous l’enlevez de la boîte. Ce processus de tirage aléatoire continue jusqu’à ce qu’il n’y ait plus de ficelles dans la boîte. La question est : combien de boucles ce processus crée-t-il en moyenne ? Si vous répétiez cette expérience des milliers de fois, quel serait le nombre moyen de boucles formées ?

LES OBSERVATIONS CLÉS POUR COMPRENDRE LE PROBLÈME

Avant de chercher une solution, il faut bien saisir le problème. Chaque tour de tirage aléatoire comporte deux composantes aléatoires : le premier tirage et le second. Le premier tirage n’est pas très important, car c’est le second qui détermine si on forme une boucle ou une ficelle plus longue.

Chaque tour réduit le nombre de ficelles dans la boîte, peu importe le résultat. Si une boucle est formée, la ficelle qui l’a créée est retirée. Si une ficelle plus longue est créée, deux ficelles deviennent une seule, ce qui réduit le nombre total de ficelles de un.

Le nombre de tirages n’est pas une variable aléatoire. Chaque tour retire une ficelle de la boîte, quel que soit le résultat (observation n°2). Chaque tour comprend deux tirages, donc le nombre de tours sera égal au nombre de ficelles. Par exemple, avec 10 ficelles, il y a 20 tirages aléatoires répartis en 10 tours. Notez que le dernier tour n’a qu’une ficelle restante et forme toujours une boucle.

Cette observation est la plus importante : du point de vue du comptage des boucles, chaque tour de tirage aléatoire est indépendant des tours précédents. Cela signifie que le problème peut être décomposé en tours individuels plutôt que de considérer l’ensemble de la séquence des tours.

UNE SOLUTION BRUTE : LE CALCUL MANUEL

Presque tous les problèmes de ce type (et les problèmes réels) ont une solution de force brute, comme creuser un trou pour une piscine à la main. Pour ce problème, on peut construire un arbre de probabilités et calculer manuellement le nombre attendu de boucles. Cette méthode fonctionne pour un petit nombre de ficelles, mais devient rapidement ingérable. Dans sa vidéo, Grant mentionne spécifiquement 50 ficelles comme nombre à résoudre (ce qui nécessiterait un arbre à 250 feuilles .). Il pousse ainsi son public à abandonner la méthode de force brute pour des solutions plus intelligentes.

UNE APPROCHE PLUS MALINE : LA PROBABILITÉ PAR TOUR

En analysant attentivement les caractéristiques du processus aléatoire, on réalise que chaque tour de tirage est indépendant des autres (observation n°4). Grâce à cette propriété, on peut calculer l’espérance de valeur d’un seul tirage et voir s’il est possible de combiner plusieurs tirages pour résoudre le problème.

On a déjà compris que le premier tirage n’est pas très important (observation n°1) : tout dépend du second tirage. Prenons un exemple simple avec 4 ficelles. On fait un premier tirage aléatoire pour obtenir la première extrémité (peu importe laquelle). Le second tirage peut être n’importe quelle extrémité de la boîte, sauf celle que nous avons sélectionnée pour le premier tirage.

Avec 4 ficelles dans la boîte, cela donne 8 extrémités. Après avoir choisi la première extrémité, il reste 7 extrémités possibles. Une seule de ces 7 extrémités résultera en une boucle, les autres non. L’image ci-dessous illustre mieux cette situation que les chiffres.

La probabilité de former une boucle est donc de 1/7, et la probabilité de ne pas en former est de 6/7. Cela donne une espérance de 1/7 boucle (1 × 1/7 + 0 × 6/7).

Généralisons cette formule en utilisant le nombre de ficelles comme entrée. Si S est le nombre de ficelles, le nombre d’extrémités est 2S (deux extrémités par ficelle). Après le premier tirage, il reste 2S - 1 extrémités possibles, et seule une d’entre elles forme une boucle. La formule pour l’espérance du nombre de boucles est donc 1/(2S - 1).

COMBINER LES TOURS POUR UNE SOLUTION GÉNÉRALE

Maintenant que nous avons une formule pour calculer l’espérance du nombre de boucles pour un seul tour, voyons comment combiner plusieurs tours. Grâce à l’observation n°4 (l’indépendance des tours pour compter les boucles) et à l’observation n°2 (le nombre déterministe de tours), on peut simplement additionner les espérances de boucles de chaque tour. Bien sûr, il faut mettre à jour le nombre de ficelles pour chaque tour, ce qui se fait avec la fonction de sommation.

Avec cette formule, terminer le défi revient à insérer 50 pour S, ce qui donne environ 2,94 boucles. Mission accomplie .

POURQUOI UTILISER UNE SIMULATION DE MONTE CARLO ?

Bien que ce problème ait une solution analytique (une formule fermée), il est utile de discuter de la façon dont on pourrait le résoudre avec une simulation de Monte Carlo. Même si ce n’est pas nécessaire pour des problèmes simples, Monte Carlo peut être salvateur si on ajoute des complications.

Les simulations de Monte Carlo estiment des valeurs en utilisant des processus aléatoires répétés. Dans notre problème, on simule le processus de tirage aléatoire plusieurs fois et on prend la moyenne du nombre de boucles comptées à travers ces simulations.

À mesure que le nombre de simulations augmente (grâce à la loi des grands nombres), le résultat de Monte Carlo converge vers la vraie valeur espérée. Voici le lien vers le code complet, mais voici la boucle qui crée la simulation elle-même :

from montecarlofuncs import createstrings, selectends, tie_ends

# Exécuter la simulation de Monte Carlo
listofcircles = []
num_strings = 50
num_simulations = 10000

if __name__ == "__main__":
    for  in range(0, numsimulations):
        # Créer la boîte simulée de ficelles
        strings = createstrings(numstrings)
        
        # Initialiser le compteur de boucles pour cette simulation
        circle_counter = 0
        
        # Tirer des ficelles jusqu'à ce qu'il n'y en ait plus
        while len(strings) > 0:
            end1, end2, strings = select_ends(strings)
            strings, circlebool = tieends(strings, end1, end2)
            circlecounter += circlebool
        
        # Ajouter le nombre de boucles comptées pour ce tour
        listofcircles.append(circle_counter)

print(np.mean(listofcircles))

Lorsque j’ai exécuté ce code (le résultat change légèrement à chaque fois), j’ai obtenu 2,95, ce qui est très proche de la valeur correcte de 2,94. Cela montre une chose importante : le processus de Monte Carlo est un bon moyen d’obtenir une estimation, mais la flexibilité se fait au prix de la précision.

QUAND MONTE CARLO DEVIENT INDISPENSABLE

Prenons le temps de souligner où l’approche de Monte Carlo brille vraiment en rendant le problème beaucoup plus complexe. Et si on changeait le problème : au lieu de calculer le nombre attendu de boucles, on calculait la circonférence moyenne des boucles ? Ce problème est bien plus complexe car il dépend des dépendances entre chaque tour de tirage aléatoire.

Je n’ai pas réussi à trouver de solution analytique pour ce problème (bien qu’elle puisse exister). Quand on ne peut pas trouver de solution analytique — ce qui sera la majorité du temps — Monte Carlo peut sauver la situation . On pourrait facilement modifier le code de Monte Carlo pour suivre les longueurs de chaque ficelle, puis utiliser ces longueurs pour calculer les circonférences des boucles lorsqu’elles sont créées. Grâce à Monte Carlo, ce calcul passe d’un problème mathématique très difficile à un problème de codage assez simple.

La principale leçon à retenir est que lorsque la création d’une solution analytique est difficile ou impossible, Monte Carlo peut être un moyen plus simple de résoudre le problème.

POURQUOI CE PROBLÈME EST UNE MÉTAPHORE DE LA DATA SCIENCE

La capacité à comprendre profondément un problème et à concevoir une solution de manière réfléchie a toujours été une compétence distinctive en data science. Avec notre dépendance récente à l’intelligence artificielle générative, cette compétence devient encore plus rare. J’ai trouvé ce casse-tête être un exercice amusant pour aiguiser ces compétences.

Bien que vous n’ayez pas à calculer le nombre attendu de boucles dans une boîte de ficelles en tant que professionnel de la data science (ou du moins, c’est très peu probable), vous rencontrerez fréquemment des situations où le chemin vers une solution n’est pas immédiatement évident. Comprendre profondément le problème, le décomposer en plus petits composants et développer soigneusement une solution sur mesure sont des compétences qui se transposent directement dans le travail réel de data science et d’analyse.

LES ENSEIGNEMENTS À RETENIR POUR LES DATA SCIENTISTS

Ce problème illustre trois compétences essentielles pour un data scientist :

1. Comprendre le problème en profondeur : Avant de chercher une solution, il faut bien saisir les mécanismes et les observations clés. Chaque détail compte, même s’il semble anodin au premier abord.

2. Décomposer le problème : En identifiant que chaque tour est indépendant, on peut résoudre le problème tour par tour plutôt que de considérer l’ensemble de la séquence. Cette décomposition est cruciale pour simplifier des problèmes complexes.

3. Choisir la bonne méthode : Pour des problèmes simples, une solution analytique (comme une formule) est la meilleure option. Pour des problèmes plus complexes ou impossibles à résoudre analytiquement, une simulation de Monte Carlo peut être une alternative efficace et plus simple à mettre en œuvre.

COMMENT ADAPTER CE PROBLÈME À D'AUTRES DOMAINES

Ce problème de ficelles peut sembler très spécifique, mais il est en réalité une métaphore de nombreux problèmes réels en data science. Voici quelques exemples où cette approche peut être utile :

Chaînes de Markov : Ce problème est une illustration simple d’un processus aléatoire où l’état futur dépend de l’état présent. Les chaînes de Markov sont utilisées en finance, en biologie et même en traitement du langage naturel pour modéliser des séquences d’événements.

Processus de Poisson : Un processus où des événements se produisent de manière aléatoire et indépendante dans le temps. Ce modèle est utilisé pour modéliser des arrivées de clients dans un magasin, des pannes de machines ou des appels téléphoniques.

Algorithmes de tri aléatoires : Certains algorithmes de tri utilisent des processus aléatoires pour organiser des données. Comprendre comment fonctionne un processus aléatoire peut aider à concevoir des algorithmes plus efficaces.

Simulations de Monte Carlo : Comme illustré dans ce problème, les simulations de Monte Carlo sont utilisées pour estimer des valeurs dans des systèmes complexes où une solution analytique est difficile, voire impossible. Elles sont couramment utilisées en finance pour évaluer des risques ou en ingénierie pour tester des scénarios.

UN EXEMPLE CONCRET : LA GESTION DE PROJETS

Prenons un exemple concret en dehors de la data science : la gestion de projets. Imaginez que vous gérez un projet avec plusieurs tâches interdépendantes. Chaque tâche a une durée aléatoire, et vous voulez estimer le temps total nécessaire pour terminer le projet. Une simulation de Monte Carlo peut vous aider à modéliser ces incertitudes et à obtenir une estimation réaliste du temps total, plutôt que de vous fier à une estimation unique et potentiellement erronée.

LES LIMITES DES SIMULATIONS DE MONTE CARLO

Bien que les simulations de Monte Carlo soient puissantes, elles ont aussi des limites. Voici quelques points à garder à l’esprit :

1. Précision vs. Flexibilité : Les simulations de Monte Carlo fournissent des estimations, pas des solutions exactes. Plus vous augmentez le nombre de simulations, plus l’estimation sera précise, mais cela prendra plus de temps.

2. Complexité du code : Bien que les simulations de Monte Carlo simplifient certains problèmes complexes, elles peuvent introduire une complexité supplémentaire dans le code. Il faut s’assurer que le code est bien structuré et optimisé pour éviter des erreurs ou des lenteurs.

3. Interprétation des résultats : Les résultats d’une simulation de Monte Carlo doivent être interprétés avec prudence. Il est important de comprendre les limites du modèle et de ne pas tirer de conclusions hâtives.

COMMENT DÉBUTER AVEC LES SIMULATIONS DE MONTE CARLO

Si vous souhaitez vous lancer avec les simulations de Monte Carlo, voici quelques étapes simples pour commencer :

1. Définir le problème : Identifiez le problème que vous souhaitez résoudre et déterminez s’il est adapté à une simulation de Monte Carlo.

2. Modéliser le processus aléatoire : Décrivez comment fonctionne le processus aléatoire que vous souhaitez simuler. Quels sont les paramètres ? Quelles sont les règles ?

3. Écrire le code : Utilisez un langage de programmation comme Python pour écrire la simulation. Des bibliothèques comme NumPy ou Pandas peuvent vous aider à manipuler les données et à effectuer des calculs.

4. Exécuter la simulation : Lancez la simulation avec un nombre suffisant de répétitions pour obtenir une estimation précise.

5. Analyser les résultats : Comparez les résultats de la simulation avec des données réelles ou des solutions analytiques, si disponibles. Ajustez le modèle si nécessaire.

UN OUTIL POUR LES PROBLÈMES COMPLEXES

Les simulations de Monte Carlo ne sont pas réservées aux casse-têtes abstraits. Elles sont utilisées dans des domaines variés pour résoudre des problèmes complexes :

Finance : Pour évaluer les risques d’un portefeuille d’investissement ou pour estimer la valeur d’une option financière.

Ingénierie : Pour tester la robustesse d’un système ou pour simuler des scénarios de panne.

Logistique : Pour optimiser les tournées de livraison ou pour gérer les stocks dans un entrepôt.

LES COMPÉTENCES TRANSFÉRABLES DE CE PROBLÈME

Ce problème de ficelles illustre plusieurs compétences transférables qui sont essentielles pour un data scientist :

1. La pensée algorithmique : Savoir décomposer un problème en étapes logiques et séquentielles est une compétence clé en programmation et en data science.

2. La modélisation mathématique : Transformer un problème réel en un modèle mathématique permet de mieux comprendre les mécanismes sous-jacents et de trouver des solutions.

3. La programmation : Écrire du code pour simuler des processus aléatoires renforce la compréhension des concepts de probabilité et de statistique.

4. L’analyse critique : Savoir évaluer les limites d’une solution (comme la précision d’une simulation de Monte Carlo) est crucial pour éviter des erreurs coûteuses.

POUR ALLER PLUS LOIN : D'AUTRES PROBLÈMES À EXPLORER

Si ce problème de ficelles vous a plu, voici d’autres casse-têtes ou concepts qui pourraient vous intéresser :

Le problème du collectionneur de coupons : Un problème classique où l’on cherche à estimer le nombre d’essais nécessaires pour collecter tous les coupons d’un ensemble.

Le paradoxe de Saint-Pétersbourg : Un problème de probabilité qui illustre comment les humains perçoivent la valeur des gains et des pertes.

Les processus de naissance et de mort : Des modèles mathématiques utilisés pour décrire des systèmes où des individus naissent ou meurent au fil du temps, comme dans les populations biologiques ou les files d’attente.

Les algorithmes de bandits manchots : Des algorithmes utilisés pour résoudre des problèmes d’optimisation où il faut choisir entre exploiter une option connue ou explorer de nouvelles options.

CONCLUSION : POURQUOI CE PROBLÈME EST PLUS UTILE QU'IL N'Y PARAÎT

Ce problème de ficelles peut sembler absurde, mais il cache une leçon puissante : la data science ne se résume pas à utiliser des Outils tout faits. Elle repose sur la capacité à comprendre un problème en profondeur, à le décomposer en parties gérables, et à choisir la bonne méthode pour le résoudre. Que ce soit avec une formule analytique ou une simulation de Monte Carlo, l’important est de garder son esprit critique et de ne pas se reposer uniquement sur l’intelligence artificielle pour penser à notre place.

Dans un monde où l’IA peut générer des solutions en un clin d’œil, cette compétence devient encore plus précieuse. Les data scientists qui savent résoudre des problèmes comme celui-ci — même s’ils semblent inutiles — sont ceux qui construiront les solutions de demain.