Un coude, sinon rien

Commençons par un exemple que tout le monde peut se figurer. Une boutique en ligne veut ranger ses clients en groupes qui se ressemblent. Les chasseurs de promotions. Les fidèles du dimanche. Les gros paniers. Un algorithme sait faire ce tri, à condition qu'on lui dise d'avance combien de groupes former. Deux groupes ? Le tri reste grossier. Dix ? Chaque groupe devient si petit qu'il ne veut plus rien dire. Quelque part entre les deux se cache le bon nombre.

Pour le trouver, on trace une courbe. L'abscisse porte le nombre de groupes essayé. L'ordonnée porte une mesure du désordre qui reste à l'intérieur des groupes. Cette courbe descend vite au début : chaque groupe ajouté absorbe beaucoup de désordre. Puis elle s'aplatit : les groupes supplémentaires n'apportent presque plus rien. La même silhouette de rendements décroissants apparaît quand on se demande quand arrêter d'entraîner un modèle, ou à partir de quel budget une campagne publicitaire sature. Le point où la courbe cesse de payer porte un nom d'anatomie : le coude¹. Avant lui, chaque unité investie rapporte. Après lui, on s'obstine.

Trouver ce point a l'air facile. C'est là le piège. Un algorithme de détection de coude répond toujours quelque chose, même sur une droite parfaite, même sur du bruit pur. elbow-helper pose une question plus dure. Ce coude est-il net ? Est-il unique ? Reste-t-il au même endroit quand on lisse un peu la courbe ? Revient-il si on rejoue le calcul ? Et surtout : une courbe sans aucun coude pourrait-elle donner la même chose par hasard ? Si une seule de ces réponses est mauvaise, l'outil s'abstient et dit pourquoi. Tout cela tourne à deraison.ai/elbow-helper, dans votre navigateur : collez une courbe, vous aurez la réponse et ses preuves avant d'avoir fini cet article.

Motivation

Les méthodes existantes, à commencer par l'algorithme Kneedle qui fait référence², sont très bonnes pour proposer un emplacement. Mais elles ne disent jamais à quel point elles y croient : un point, sans marge d'erreur, sans probabilité, sans droit de se taire. Sur une courbe bruitée, ce point isolé se surinterprète trop facilement. On choisit quatre groupes, on dimensionne un cache, on arrête une expérience. Tout cela à cause d'un accident du bruit.

Devant un cliché flou, un radiologue ne diagnostique pas. Il écrit que l'examen ne permet pas de conclure. Puis il en demande un autre. Un programme statistique devrait avoir la même retenue devant une courbe bruitée. Il ne doit conclure que ce que les données permettent. La comparaison a une limite : le radiologue exerce un jugement, alors que le programme applique des seuils fixés une fois pour toutes. Il est donc plus prévisible, mais aussi moins fin.

La priorité d'elbow-helper est donc claire : éviter les faux coudes, quitte à se taire plus souvent. Le programme qui l'appelle n'a pas le choix : la réponse est soit un ClearKnee, soit un NoClearKnee. Le premier donne la position du coude, une fourchette et les preuves chiffrées. Cette fourchette vise à contenir la vraie position dans environ neuf cas sur dix, mais seule la famille de courbes de test le confirme à ce jour. Le second donne un code qui dit pourquoi l'outil s'est tu, lisible par une machine. Jamais de repli discret vers une estimation douteuse : l'abstention se traite, elle ne se contourne pas.

Les outils déjà disponibles tombent dans trois groupes. Il y a d'abord ceux qui cherchent le coude et rien d'autre : kneed³, kneebow⁴, le visualiseur de Yellowbrick⁵. Ils répondent toujours par un point, et aucun ne sait dire « il n'y a rien ici ». Il y a ensuite les bibliothèques de détection de ruptures, ruptures⁶ en tête. Elles sont excellentes. Mais elles répondent à une autre question. Combien de ruptures dans un signal ? Les rendements qui diminuent ne les intéressent pas. Le troisième groupe laisse le jugement à un humain, à l'œil ou à un modèle de langage, ce qui ne se reproduit pas. Le parent le plus proche d'elbow-helper n'est finalement aucun des trois : c'est le paquet segmented de R⁷, qui part de la même idée. Dire qu'il y a un coude, c'est dire aussi à quel point on en est sûr. Mais se taire quand la preuve manque reste rare chez tous. C'est l'apport principal d'elbow-helper. La comparaison est chiffrée : le tableau de notes et la carte qui en résume les onze critères sont à la fin de cet article.

Reste à savoir si l'outil est vraiment utilisable. Le paquet est publié sur PyPI, l'entrepôt public où pip install va chercher les bibliothèques Python, en huit versions de v0.1.0 à v0.1.7. Aucun envoi de code n'est accepté tant que les 85 tests automatiques ne passent pas sur Python 3.12, ni tant que le vérificateur de style n'est pas content. Chaque semaine, la même série de tests est rejouée sur les quatre versions de Python supportées, de 3.10 à 3.13. Ces 85 tests exécutent 96 % des lignes du paquet.

On atteint la même chaîne par quatre portes. La bibliothèque Python. Une commande en ligne. Une interface web par laquelle d'autres programmes viennent poser leurs questions, ce qu'on appelle une API HTTP. Et un serveur qui offre les mêmes opérations à un assistant conversationnel, par le protocole Model Context Protocol, abrégé en MCP. Ces quatre portes sont de fines couches posées sur un cœur unique, donc aucune ne peut dire autre chose que les autres. S'y ajoute l'application web, qui exécute la chaîne de bout en bout dans un onglet. Et une note mathématique en LaTeX, qui démontre chaque formule du paquet avec un exemple travaillé : ELBOW.pdf, complétée par LIKELIHOOD.pdf. Ces documents existent en français comme en anglais, tenus à jour avec le code.

Comment ça marche

La courbe est d'abord mise en ordre. Les points invalides sont écartés. Les abscisses sont triées et dédoublonnées. Les deux échelles sont ramenées entre 0 et 1. Cette mise à l'échelle prend une précaution. Elle ne se cale pas sur le point le plus bas et le point le plus haut, mais sur le 5^e et le 95^e centile. Le 5^e centile, c'est la valeur sous laquelle tombent 5 % des points ; le 95^e, celle sous laquelle il en tombe 95 %. Un seul point aberrant ne peut donc pas écraser toute la courbe contre le bord.

Vient ensuite un premier examen de forme. La courbe monte-t-elle, ou descend-elle, sans jamais changer de sens ? On dit alors qu'elle est monotone. La corrélation de Spearman⁸ répond à cette question en regardant seulement l'ordre des valeurs, jamais leur taille. Un second contrôle, qui tient compte des écarts, vient la confirmer. Une courbe sans tendance nette est écartée tout de suite, avant même qu'on cherche un coude.

Vous n'avez pas à dire dans quel sens va la courbe, sauf si vous voulez l'imposer. Le programme le lit dans le signe de la tendance. Pour savoir si elle est creuse ou bombée, il la compare à la corde qui joint son premier et son dernier point. Au-dessus de la corde, elle est bombée comme un dôme. En dessous, elle est creuse comme un bol. Les quatre cas possibles sont donc couverts, bombée ou creuse, montante ou descendante, sans que vous ayez à nommer la forme. Si vous la donnez quand même, c'est la vôtre qui gagne.

La courbe est propre, son sens est connu. Reste à dire ce qu'on cherche. Commençons par le mot « coude ». Il mérite une définition honnête. Prenez une courbe en racine carrée, qui monte vite puis se calme. Tracez la droite qui joint ses deux extrémités, puis soustrayez-la de la courbe. Il reste une bosse, nulle aux deux bouts, maximale là où la courbe s'écarte le plus de cette droite. Ce sommet, c'est le coude. Une fois les données ramenées entre 0 et 1, cette courbe de différence s'écrit :

Ses maxima locaux, les points plus hauts que leurs voisins immédiats, sont les candidats. Un seuil de sensibilité décide ensuite si un sommet est un vrai coude ou une simple ondulation : le candidat doit dominer son voisinage d'une marge proportionnelle à un paramètre \(S\) :

où la barre désigne l'écart moyen entre deux abscisses voisines. Plus \(S\) est grand, plus la marge exigée est large. Toute cette recherche est rejouée sur une grille de lissages et de sensibilités. Seuls survivent les candidats qui reviennent au même endroit à chaque réglage. Un vrai coude résiste quand on floute un peu la courbe ; un accident de bruit, lui, disparaît.

Cette recherche de sommets porte un nom et a des auteurs. C'est l'algorithme Kneedle², décrit par Satopää, Albrecht, Irwin et Raghavan en 2011, réécrit ici de zéro en NumPy. La façon de parcourir la courbe, la table des orientations et le seuil de sensibilité suivent de près les choix de la bibliothèque kneed de Kevin Arvai³. Cette bibliothèque est sous licence BSD et le dépôt la crédite. elbow-helper n'en a pas besoin pour fonctionner. Ce qu'elbow-helper ajoute est donc ailleurs. Il tient à ce qu'il exige d'un candidat avant de l'appeler un coude.

Vient ensuite la vérification par le calcul. Première exigence : la pente doit changer, et changer d'une façon que trois points aberrants ne suffisent pas à fabriquer. C'est ce que mesure un estimateur de Theil-Sen⁹. La méthode habituelle s'appelle les moindres carrés. Elle cherche la droite qui rend la somme des carrés des écarts la plus petite possible. Une valeur folle y pèse donc très lourd. Theil-Sen fait autrement. Il calcule la pente de toutes les paires de points, puis prend la valeur du milieu, la médiane. Quelques points fous ne décident plus du résultat.

Reste à écrire le modèle lui-même. Un vrai coude est un changement de pente : une droite, puis une autre pente après le point \(k\). Pour fabriquer cette ligne brisée d'un seul morceau, sans saut, on utilise une fonction qui vaut zéro avant \(k\) et qui monte tout droit après :

Le coefficient \(c\) porte toute l'histoire du coude. Si \(c\) vaut zéro, on retombe sur une droite sans coude. Plus \(c\) s'éloigne de zéro, plus la pente casse fort en \(k\). Ce modèle brisé doit ensuite battre la simple droite sur deux terrains. Le premier est un examen par morceaux¹⁰ : on cache une partie de la courbe, puis on regarde si le modèle devine ce qu'on lui a caché. On enlève des tronçons entiers, jamais des points isolés, parce qu'un point isolé se devine bien trop facilement d'après ses voisins. Le second terrain est un score qui compare les deux modèles en tenant compte de leur complexité. Mais ce score demande d'abord qu'on dise ce que « mieux ajusté » veut dire.

Ce que « mieux ajusté » veut dire : la vraisemblance

Supposons le modèle vrai. S'il colle bien aux données, ce qu'on observe n'a rien de surprenant. C'est l'idée de vraisemblance. Pour la calculer, il faut d'abord se donner un modèle du hasard. Chaque point observé s'écarte un peu de la courbe théorique. Cet écart est un bruit gaussien. C'est le hasard en courbe en cloche, celui que produisent de petites erreurs qui s'additionnent. Chaque écart est tiré indépendamment des autres, avec une taille typique notée \(\sigma\). Chaque observation reçoit alors une densité de probabilité, c'est-à-dire un nombre qui dit à quel point cette valeur était attendue. Plus le point tombe près de la courbe proposée, plus ce nombre est grand.

Les manuels multiplient ces nombres entre eux, sur les \(n\) points. Ce produit pose un problème pratique. Multiplier \(n\) nombres tous inférieurs à un donne un résultat qui s'effondre à toute vitesse quand \(n\) grandit. Une courbe de 80 points et une courbe de 800 ne se comparent alors plus du tout. elbow-helper prend donc la vraisemblance par observation. On multiplie les \(n\) nombres. Puis on prend la racine \(n\)-ième du résultat, ce qui revient à une moyenne. Le nombre de points cesse ainsi de peser :

Avec un bruit en cloche, tout se simplifie d'un coup. Il ne reste que l'erreur quadratique moyenne, c'est-à-dire la moyenne des carrés des écarts entre les points observés et la courbe ajustée :

Le logarithme n'est pas un choix arbitraire ici. La densité gaussienne contient une exponentielle, et le logarithme népérien la défait exactement.

Cette ligne contient une petite surprise. À bruit fixé, rendre l'erreur quadratique moyenne la plus petite possible revient exactement à rendre la vraisemblance la plus grande possible. On apprend les moindres carrés comme une recette géométrique. On apprend le maximum de vraisemblance comme un principe statistique. Ce sont la même chose. En poussant le calcul un peu plus loin, on retombe sur une quantité que la théorie de l'information appelle la perplexité. Le mot vient des modèles de langage, où la perplexité se lit comme le nombre de mots entre lesquels le modèle hésite à chaque pas. Ici elle porte sur des nombres et non sur des mots. Elle mesure la même chose : l'étendue des valeurs que le modèle juge possibles. Plus elle est basse, moins le modèle hésite :

Ramenée à l'échantillon entier, elle donne la log-vraisemblance négative \(\mathrm{NLL}\), écrite avec la somme des carrés des résidus \(\mathrm{SCR}\), c'est-à-dire l'erreur quadratique moyenne avant division par \(n\) :

Comparer deux modèles sur leur seul ajustement serait truqué d'avance. Un modèle qui a plus de réglages colle toujours mieux aux données, jusqu'à épouser le bruit lui-même. Il faut donc faire payer les réglages. C'est ce que font les critères de la famille du BIC (Bayesian Information Criterion)¹¹ : ils partent de la vraisemblance et y ajoutent une pénalité proportionnelle au nombre de réglages dépensés. Le coude coûte des réglages. Il doit les rembourser en ajustement, sinon la simple droite gagne.

Reste à rendre tout cela lisible pour un humain. Le réflexe serait d'utiliser le \(R^2\), le score d'ajustement des manuels. Il compare l'erreur du modèle à celle qu'on ferait en répondant toujours la même valeur, la moyenne des observations : 1 pour un ajustement parfait, 0 pour « pas mieux que de répondre la moyenne ». Le problème est que la moyenne minimise justement l'erreur. C'est donc le meilleur adversaire possible parmi les réponses bêtes. Un \(R^2\) peut ainsi passer sous zéro. elbow-helper se compare plutôt à un adversaire franchement mauvais : le point observé depuis lequel il est le plus difficile de prédire tous les autres.

Ce score vaut 1 pour un ajustement parfait, et 0 pour un ajustement aussi mauvais que cette pire valeur fixe. Comme cette référence est toujours plus mauvaise que la moyenne, il est beaucoup plus difficile de tomber sous zéro qu'avec un \(R^2\). C'est ce nombre qui s'affiche dans la légende de la figure. Trois autres l'accompagnent : la probabilité de détection, la valeur \(p\) définie à la section suivante, et un poids qui compare les deux modèles. Ce dernier est la cote entre le modèle à coude et la simple droite, calculée à partir de l'écart de BIC¹². Un mot de prudence : cette cote ne vaut que si l'on a beaucoup d'observations. La lire comme une probabilité demanderait en plus de se donner d'avance une confiance dans chacun des deux modèles, ce qu'aucune donnée ne fournit ici. On la prend donc pour ce qu'elle est. C'est un poids qui compare deux modèles. Il ne prétend pas être une probabilité.

Les épreuves de robustesse

Un modèle peut gagner ce duel sur les données qu'on a, et n'être qu'un caprice du bruit. Deux épreuves s'en assurent. La première s'appelle le bootstrap¹³. Le nom vient d'une expression anglaise. Elle parle de se hisser en tirant sur ses propres lacets. Faute d'autres jeux de données, on en fabrique à partir de celui qu'on a. On retire de la courbe le modèle ajusté, ce qui laisse les écarts. On mélange ces écarts au hasard, puis on les recolle sur le modèle. Chaque copie est une courbe qu'on aurait pu observer si le hasard avait tiré autrement. On refait la recherche complète sur chaque copie. Pour passer, le coude doit revenir au même endroit dans au moins 90 % des copies, avec une fourchette serrée. La seconde épreuve est le test de la droite pure. On simule des milliers de droites portant le même niveau de bruit. Puis on compte combien de fois le hasard seul produit une preuve aussi forte que celle qu'on a observée.

Ce nombre, la valeur \(p\), mérite qu'on s'arrête, parce que c'est la quantité la plus mal lue de toute la statistique. Elle ne dit pas la probabilité qu'il n'y ait pas de coude. Elle dit l'inverse : en supposant qu'il n'y en ait aucun, à quelle fréquence le hasard seul fabriquerait une preuve aussi convaincante. Une valeur \(p\) de 0,01 veut dire qu'une droite pure y arriverait une fois sur cent. C'est peu, donc on garde le coude. Ce n'est pas zéro, donc on peut se tromper une fois sur cent. Ce passage par la simulation n'est pas un luxe. S'il n'y a pas de coude, alors sa position n'existe pas. Les tests classiques perdent donc la référence sur laquelle ils s'appuient d'habitude¹⁴. Il faut donc que les deux barres soient franchies :

Seul un candidat qui franchit toutes ces portes devient un ClearKnee. La figure de diagnostic affiche ce dossier de preuves à côté de la courbe. En cas d'abstention, elle passe à un état honnête. Courbe grisée, raison affichée. Jamais un marqueur qui laisserait croire à plus de certitude qu'il n'y en a.

La figure suivante montre la même courbe, la même cassure en dessous, avec un bruit plus fort et rien d'autre de changé.

Ce que « s'abstenir » veut dire

S'abstenir n'est pas échouer en silence. C'est une réponse, qui porte un nom. La fonction rend toujours l'un de deux objets, jamais autre chose. Le programme qui l'appelle est donc obligé de regarder lequel avant de continuer. Voici les deux réponses telles qu'elles s'affichent, sur la même courbe à deux niveaux de bruit :

>>> from elbow_helper import robust_knee

>>> robust_knee(x, y)            # bruit d'écart-type 0,02
ClearKnee(knee_x=0.3038, ci90=(0.3038, 0.3418), detection_rate=0.98, null_p=0.00498)

>>> robust_knee(x, y_bruite)     # même coude, bruit dix fois plus fort
NoClearKnee(reason='INCOMPATIBLE_GLOBAL_SHAPE')

La première ligne se lit sans documentation. Coude en 0,304. Fourchette allant de 0,304 à 0,342. Coude retrouvé dans 98 % des copies. Probabilité qu'une droite sans coude fasse aussi bien : cinq pour mille. La seconde ne donne aucune position. C'est voulu : à ce niveau de bruit, la courbe ne passe même plus l'examen de forme, sa tendance n'étant plus assez nette.

Chaque refus porte un code stable, lisible par une machine comme par un humain. Ces codes forment une liste arrêtée d'avance, quinze motifs et pas un de plus. Un tableau de bord peut donc compter ses abstentions, et savoir si ses courbes sont trop courtes, trop bruitées, ou simplement ambiguës.

Les quinze façons de dire non, dans l'ordre où la chaîne peut les rencontrer.

Ce détail a une conséquence pratique : un refus dit quoi faire. INSUFFICIENT_DATA demande plus de points. BOOTSTRAP_MULTIMODAL suggère qu'il y a peut-être deux coudes plutôt qu'aucun, et renvoie vers la recherche au pluriel décrite ensuite. NULL_NOT_REJECTED dit que la courbe est jolie, mais que le bruit suffirait à l'expliquer.

Cinq portes, un seul verdict

Un détecteur ne sert que si on peut l'appeler depuis l'endroit où l'on travaille. elbow-helper offre donc la même chaîne par cinq accès. La bibliothèque Python, pour un carnet d'analyse. La commande en terminal, pour un script ou pour ces vérifications automatiques qu'on rejoue à chaque modification du code. L'API HTTP, pour un service écrit dans un autre langage que Python. Le serveur MCP, pour un assistant conversationnel. Et l'application web, pour qui ne veut rien installer. Les quatre premiers partagent le même cœur et offrent les quatre mêmes opérations. knee rend un coude avec son incertitude. elbow est le raccourci du cas k-means, où la courbe est connue d'avance comme creuse et descendante. diagnostics rend la figure, en SVG, un format de dessin qui reste net à toute taille. Et locator rend la position seule, sans les preuves. Ce que l'un renvoie, les autres le renvoient aussi.

Installer, c'est choisir son accès. Le cœur ne dépend que de NumPy. Les accès réseau sont des options, entre crochets, qu'on n'installe que si on s'en sert :

$ pip install elbow-helper            # bibliothèque + ligne de commande
$ pip install "elbow-helper[api]"     # + l'API HTTP
$ pip install "elbow-helper[mcp]"     # + le serveur MCP (qui embarque l'API)

La bibliothèque

Deux fonctions suffisent. robust_knee prend une courbe et devine sa forme. robust_elbow est le raccourci du cas k-means, où la forme est connue d'avance. Les abscisses sont facultatives : si vous ne donnez que les ordonnées, elles seront numérotées de zéro à n moins un.

from elbow_helper import robust_knee, robust_elbow, RobustKneeConfig

res = robust_knee(x, y)                     # forme et sens devinés
res = robust_elbow(k_values, inerties)      # le cas k-means, forme imposée
res = robust_knee(y)                        # x implicite : 0, 1, 2, ...

# Plus de rejeux : plus lent, plus sûr.
res = robust_knee(x, y, config=RobustKneeConfig(bootstrap_replicates=500,
                                                null_replicates=1000,
                                                random_seed=0))

if res.is_clear:
    print(res.knee_x, res.ci90, res.detection_rate, res.null_p_value)
else:
    print("pas de coude net :", res.reason)

Tous les seuils vivent dans RobustKneeConfig, une structure qu'on ne modifie pas : on en fabrique une copie avec config.with_(...). Les réglages livrés visent la seconde plutôt que la décimale : cent copies de bootstrap, deux cents droites simulées. Les valeurs ci-dessus sont celles d'une validation sérieuse, cinq à dix fois plus lentes.

La ligne de commande

Elle offre les quatre mêmes opérations et répond en JSON. Ce format de texte se relit sans ambiguïté par un programme. On peut donc l'enchaîner aux outils habituels. Les données entrent au choix en valeurs séparées par des virgules, en fichier NumPy, ou en colonne d'un CSV désignée par son numéro :

$ elbow-helper knee --y-values 0,0.1,0.3,0.6,0.85,0.9,0.92,0.93,0.94,0.95
{
  "reason": "INSUFFICIENT_DATA",
  "diagnostics": {
    "curve": "auto",
    "direction": "auto",
    "n": 10,
    "min_samples": 20
  },
  "is_clear": false
}

$ elbow-helper elbow --x-npy k.npy --y-npy inertie.npy
$ elbow-helper knee --y-csv mesures.csv:2 --config-json '{"bootstrap_replicates": 500}'
$ elbow-helper diagnostics --x-npy k.npy --y-npy inertie.npy > diagnostic.svg

La première commande mérite qu'on s'arrête. La courbe qu'elle reçoit a tout à fait la bonne allure, et n'importe quel détecteur classique aurait rendu un chiffre. Mais dix points ne suffisent pas pour affirmer qu'il y a un coude. La réponse est donc un refus documenté, qui dit combien de points ont été fournis et combien il en faudrait. Pas d'estimation de complaisance. La règle vaut par tous les accès.

L'API HTTP

Un serveur se lance en une ligne et écoute quatre adresses, du nom des quatre opérations. La courbe voyage en JSON, les réglages aussi, dans un objet config_overrides. L'adresse diagnostics renvoie le SVG lui-même, sans emballage autour.

# uvicorn : le serveur qui fait tourner l'application Python.
$ uvicorn elbow_helper.api:app --port 8000

$ curl -s -X POST localhost:8000/knee -H 'Content-Type: application/json' \
       -d '{"x": [0, 0.0127, ...], "y": [0.0043, 0.0361, ...],
            "config_overrides": {"random_seed": 0}}'
{"reason": "CLEAR_KNEE", "knee_x": 0.3038, "ci90": [0.3038, 0.3418],
 "detection_rate": 0.98, "null_p_value": 0.00498, "is_clear": true,
 "diagnostics": {...}}                       # réponse abrégée

Le serveur MCP

Le serveur MCP est cette même application, avec les quatre opérations déclarées comme outils qu'un assistant conversationnel peut découvrir et appeler, servies sur /mcp :

$ uvicorn elbow_helper.mcp_server:app --port 8021
# L'assistant se connecte à http://127.0.0.1:8021/mcp et y découvre
# quatre outils : knee, elbow, diagnostics, locator.

L'intérêt dépasse le confort. Montrez une courbe à un assistant : il produira volontiers un coude plausible, sans rien pour le contredire. Branché sur cet outil, il obtient un verdict calculé, avec sa fourchette et sa valeur \(p\), ou bien un refus nommé qu'il ne peut pas transformer en certitude.

L'application web

La dernière surface ne demande rien : deraison.ai/elbow-helper fait tourner la chaîne entière dans le navigateur, sur vos données, sans les téléverser nulle part. On y colle une courbe, on récupère le même verdict et la même figure de diagnostic que par les quatre autres portes, en français ou en anglais.

Plusieurs coudes : la programmation dynamique

Une courbe change parfois plusieurs fois de régime : trois paliers de prix sur une courbe de demande, par exemple. La question devient alors : combien de cassures, et où ? C'est ce que répond robust_knees, au pluriel. Changer de question oblige à changer de modèle. On découpe la courbe en morceaux et on ajuste à chacun sa propre droite, en acceptant un saut à la jointure. On renonce donc à la ligne brisée d'un seul tenant de tout à l'heure. C'est assumé. Dès que plusieurs cassures peuvent bouger, le coût d'un découpage ne se calcule plus morceau par morceau. Déplacer une cassure change ce que ses voisines doivent respecter. Or c'est justement ce découpage en petits problèmes indépendants qui rend la recherche rapide.

Premier ingrédient : pouvoir calculer d'un coup le coût d'un morceau. Ajuster une droite sur \(m\) points et mesurer son erreur semble demander de repasser sur chaque point. Il n'en est rien : six totaux cumulés suffisent,

d'où la pente et l'ordonnée à l'origine des moindres carrés, puis l'erreur du morceau :

Cette dernière égalité vient des équations des moindres carrés. Elle dit que le coût de n'importe quelle tranche de la courbe se lit dans ces totaux, sans jamais retoucher aux points. Les calculer une fois demande un temps proportionnel au nombre de points. Chaque coût de morceau est ensuite obtenu en temps constant, quelle que soit la longueur de la courbe.

Deuxième ingrédient : la recherche elle-même. Essayer toutes les façons de placer \(k\) cassures parmi \(n\) points est hors de portée : le nombre de combinaisons se chiffre vite en milliards. La programmation dynamique contourne l'obstacle : elle construit la réponse à partir de réponses plus petites déjà calculées. Notons \(C[k][t]\) le coût le plus faible pour expliquer les \(t\) premiers points avec \(k+1\) morceaux :

La formule se lit ainsi. On essaie chaque position possible \(s\) de la dernière coupe. Pour chacune, on additionne deux choses. D'un côté, le meilleur coût pour expliquer les \(s\) premiers points avec une cassure de moins : il est déjà calculé, on le relit. De l'autre, le coût du dernier morceau, de \(s\) à \(t\). Puis on garde le minimum.

Pourquoi a-t-on le droit de relire une réponse plus petite au lieu de tout recalculer ? Faisons le raisonnement à l'envers. Supposons que le meilleur découpage des \(t\) premiers points ait sa dernière coupe en \(s^\ast\), mais que son début ne soit pas le meilleur découpage possible de ce début. On pourrait alors y remplacer ce début par le moins cher, garder le dernier morceau tel quel, et obtenir un découpage valide encore moins cher que le meilleur. C'est impossible. Donc le début d'une solution optimale est lui-même optimal : c'est le principe de Bellman¹⁵.

Remplir toutes les cases du tableau reste raisonnable, là où l'énumération brute demandait un nombre astronomique d'opérations. Une flèche gardée dans chaque case permet ensuite de remonter le tableau pour retrouver où sont les coupes. C'est la méthode classique de la détection de ruptures. L'algorithme PELT¹⁶ repose sur elle et l'accélère, en abandonnant en cours de route les découpages devenus sans espoir. Ici, elle est vérifiée contre une énumération complète sur de petits jeux de données, plutôt que tenue pour acquise.

Troisième ingrédient : choisir le nombre de cassures. Plus on en ajoute, mieux on colle aux données, jusqu'à l'absurde d'un morceau par point. Un BIC modifié¹⁷ tranche : il ajoute une pénalité qui fait payer chaque cassure, et qui surveille en plus la longueur de chaque morceau :

Le signe moins devant cette somme mérite une anecdote, parce qu'elle dit comment ce projet travaille. La littérature écrit ce terme avec un plus. Testé tel quel, il produit l'effet inverse de celui qu'on lui prête : le terme étant toujours négatif, l'ajouter récompense les découpages déséquilibrés au lieu de les punir. Avec un moins, en revanche, les morceaux courts et inégaux sont bien pénalisés, comme annoncé. La convention retenue ici est donc celle que les tests confirment, et l'écart est documenté plutôt que caché. Reste à dire ce qui n'est pas tranché : un signe qui paraît inversé peut venir d'une définition différente de la vraisemblance, d'un score qu'on minimise au lieu de le maximiser, ou d'une longueur normalisée autrement. Faire la correspondance terme à terme avec la formulation d'origine demanderait une annexe que le dépôt n'a pas encore écrite. Il s'agit donc d'un désaccord mesuré, pas d'une correction de la littérature.

Le gagnant est enfin confirmé par un test de permutation. On mélange la courbe des milliers de fois : aucune de ces versions mélangées ne porte de vraie cassure, donc presque toutes doivent faire moins bien que l'ajustement réel. Et comme multiplier les tests multiplie les occasions d'avoir de la chance, une correction de Bonferroni resserre la barre de chaque test en proportion de leur nombre¹⁸.

Une nuance sépare le singulier du pluriel. Elle compte. Au pluriel, une réponse vide n'est pas une abstention : c'est une conclusion. Cette courbe n'a aucune cassure réelle. Ce verdict a franchi exactement les mêmes portes qu'une réponse non vide. Seul un problème de préparation, une entrée invalide, des données trop courtes ou une plage nulle, renvoie une erreur au lieu d'une liste de cassures.

Ces choix, la programmation dynamique plutôt que la méthode gloutonne, le signe moins, la confirmation par permutation, ont été tranchés par la mesure. Dix combinaisons ont été mises en concurrence. D'un côté, deux façons de chercher : la programmation dynamique, qui examine tous les découpages, et la méthode gloutonne, qui pose ses cassures une par une sans jamais revenir dessus. De l'autre, cinq façons de choisir le nombre de cassures. Deux fois cinq. Chaque méthode a traité trois cents courbes fabriquées pour l'essai : cent points chacune, vingt-cinq exemplaires pour chaque combinaison de quatre nombres de cassures, de zéro à trois, et de trois niveaux de bruit. Les étiquettes des deux figures qui suivent se lisent ainsi. DP, c'est la programmation dynamique ; Greedy, la méthode gloutonne. BIC, c'est le critère seul ; mBIC_add et mBIC_sub, les deux signes du terme de longueur. ICL est un critère voisin, qui fait payer en plus l'incertitude du découpage¹⁹. FWER, c'est le test de permutation corrigé à la Bonferroni.

Deux enseignements se lisent directement sur ce classement. D'abord, la recherche complète bat la méthode gloutonne à chaque fois, et de loin : 0,85 contre 0,60 pour le même critère. Le mécanisme est connu²⁰ : la méthode gloutonne s'engage tôt sur une coupe imparfaite. Les coupes suivantes servent alors à réparer cette erreur au lieu de décrire la courbe. Ensuite, le signe du terme de longueur, l'anecdote racontée plus haut, se chiffre aussi. Avec le moins, le score est de 0,85 ; avec le plus de la littérature, 0,77.

Reste le défaut qui intéresse le plus ce projet : inventer une cassure là où il n'y en a aucune. La seconde figure mesure exactement cela, sur des courbes tracées plates exprès.

Une limite est commune à toutes les méthodes. Elle mérite d'être dite. À fort bruit, avec trois cassures réelles, aucune ne les retrouve toutes : la meilleure en annonce 1,8 en moyenne. L'erreur va donc vers moins de coudes, jamais vers plus. C'est exactement la direction dans laquelle ce paquet accepte de se tromper. Ces chiffres valent pour cette famille de courbes et pour elle seule. Le protocole complet est publié dans le dépôt, avec le tableau détaillé par niveau de bruit²².

Le tout tient avec une seule dépendance de calcul, NumPy. L'algorithme de recherche est réécrit de zéro. La figure est dessinée trait par trait en SVG, sans aucune bibliothèque de graphiques. Chaque formule de cette chaîne, de la mise à l'échelle au test de permutation, est démontrée pas à pas dans la note mathématique du dépôt, ELBOW.pdf²³. Cette note est écrite intuition d'abord, avec un exemple travaillé avant chaque formule. La partie sur la vraisemblance est traitée à part, dans LIKELIHOOD.pdf²⁴, parce qu'elle ne doit rien à l'ajustement de courbes.

Ce que ça ne fait pas

Un projet qui se réclame de la prudence doit dire ses propres limites, sinon il commet l'excès de confiance qu'il reproche aux autres.

Le lissage suppose des abscisses à peu près régulièrement espacées : une courbe échantillonnée n'importe comment le mettrait en défaut. La position rendue est l'un des points fournis, pas une valeur entre deux. Avec peu de points, le coude peut donc tomber à quelques échantillons de la vérité. Sur la famille de courbes qui sert d'essai, l'erreur reste sous 5 % de la largeur de la courbe une fois sur deux. La droite simulée et le bootstrap font une autre hypothèse : ils supposent un bruit de taille constante d'un bout à l'autre de la courbe, et un point qui ne dépend pas du suivant. Les variantes qui s'en passent restent à écrire.

Enfin, les seuils sont des valeurs calibrées sur une famille de courbes documentée, pas des constantes universelles. 90 % de redétections et une valeur \(p\) à 1 % sont des choix défendables, pas des lois de la nature. Le paquet est en version 0.1. Son auteur le dit : si votre décision en dépend, recalibrez sur vos propres courbes. Aucune méthode travaillant sur des données limitées n'est infaillible. Celle-ci se contente de rendre ses hypothèses vérifiables.

Conclusion

Un détecteur qui sait se taire rend un meilleur service qu'un détecteur qui répond toujours. « Pas de coude net » est une vraie information : elle évite de dimensionner un système, d'arrêter une expérience ou de trancher un budget sur un hasard. Cette confiance affichée se paie en abstentions. C'est un échange que j'assume.

elbow-helper s'installe en une ligne, pip install elbow-helper. Il s'essaie aussi sans rien installer, dans le bac à sable en ligne, où la chaîne complète tourne dans votre navigateur sans téléverser vos données. Le code, les exemples, le comparatif des outils voisins et les notes mathématiques sont réunis sur le dépôt GitHub. Apportez une courbe ; vous repartirez avec un coude défendable ou avec une bonne raison de ne pas y croire.

Le paysage, outil par outil

Reste à situer tout cela. Le dépôt note huit façons de chercher un coude, sur onze critères. La note porte sur le travail que fait ce paquet, c'est-à-dire annoncer un coude seulement quand la preuve le soutient. Aucun outil n'est puni pour être excellent à un autre métier.

Les onze critères du dépôt, de une à cinq étoiles. La ligne surlignée est celle du paquet dont parle cet article.

• elbow-helper : le seul du lot qui puisse refuser de répondre. Un coude doit tenir d'un lissage à l'autre, survivre au bootstrap et battre le modèle nul. L'outil rend alors un coude avec son intervalle, ou un motif d'abstention nommé.
• kneed : l'implémentation de référence de Kneedle, déterministe et immédiate. Un point, toujours, sans marge d'erreur ni porte de sortie.
• kneebow : la même idée géométrique, obtenue en faisant tourner la courbe. Très léger en dépendances, mais il s'engage à chaque appel.
• KElbowVisualizer : la façon la plus répandue de lire un coude de k-means : on trace, on regarde. Un outil de visualisation, taillé pour une seule forme de courbe, qui hérite de scikit-learn et de matplotlib.
• ruptures : l'outil juste quand la question est « combien de ruptures et où », avec PELT et la segmentation binaire déjà en place. La notion de rendements décroissants lui est étrangère.
• Paquet R segmented : le plus rigoureux statistiquement : régression en ligne brisée, erreurs types, test de Davies, cassures multiples. Il demande R et une réelle aisance statistique.
• Estimation visuelle manuelle : un œil averti sait dire « je ne vois rien de net ici », ce que la plupart des outils ne savent pas. Mais le jugement ne se reproduit ni d'une personne à l'autre, ni à l'échelle.
• Demander à un LLM : décrit une forme en mots avec aisance, sait nuancer si on le lui demande ; sans incertitude calibrée, sans dérivation vérifiable, jamais deux fois la même réponse.

Bibliographie

Voici les travaux dont ce paquet dépend, rangés dans l'ordre où l'article s'en sert. Chaque notice dit ce que la source établit et à quel endroit elle sert ici. Les classiques y sont cités pour le résultat standard qu'ils fondent, les notes du dépôt pour les dérivations et les mesures qu'elles portent.

1. Thorndike, R. L. (1953). « Who belongs in the family? », Psychometrika, 18(4), 267-276. 10.1007/BF02289263 Adresse présidentielle à la Psychometric Society, couramment donnée comme la première formulation du critère du coude : on trace une mesure de dispersion contre le nombre de groupes et l'on cherche le pli. Elle pose la question dont vit cet article, sans proposer de règle de décision.
2. Satopää, V., Albrecht, J., Irwin, D. et Raghavan, B. (2011). « Finding a Kneedle in a Haystack: Detecting Knee Points in System Behavior », ICDCSW, IEEE. Définit le coude comme le maximum de l'écart à la corde après normalisation, avec un seuil de sensibilité : c'est l'algorithme de localisation réécrit ici. Sa limite est dans son énoncé même : il propose un emplacement, il ne dit pas si ce coude existe.
3. Arvai, K. kneed, bibliothèque Python, licence BSD à trois clauses. github.com/arvkevi/kneed L'implémentation de référence de Kneedle en Python. Sa logique de parcours, sa table d'orientations et son seuil de sensibilité ont guidé la réécriture NumPy d'elbow-helper, qui n'en dépend pas à l'exécution.
4. kneebow, bibliothèque Python, licence MIT. github.com/georg-un/kneebow Fait tourner la courbe puis prend l'extremum de la courbe tournée. Représentatif du camp qui répond toujours par un point, sans jamais pouvoir se taire.
5. Bengfort, B. et Bilbro, R. (2019). « Yellowbrick: Visualizing the Scikit-Learn Model Selection Process », Journal of Open Source Software, 4(35), 1075. 10.21105/joss.01075 Bibliothèque de diagnostics visuels pour scikit-learn, dont le KElbowVisualizer qui trace l'inertie et marque un coude. L'outil vise la lecture à l'œil, pas la décision chiffrée.
6. Truong, C., Oudre, L. et Vayatis, N. (2020). « Selective review of offline change point detection methods », Signal Processing, 167, 107299. arxiv.org/abs/1801.00718 Revue qui range la détection de ruptures en trois briques, une fonction de coût, une méthode de recherche, une contrainte sur le nombre de ruptures ; elle accompagne la bibliothèque ruptures. C'est le cadre dont la partie multi-coudes de cet article hérite, sur une question voisine mais distincte de celle des rendements décroissants.
7. Muggeo, V. M. R. (2003). « Estimating regression models with unknown break-points », Statistics in Medicine, 22(19), 3055-3071. 10.1002/sim.1545 Estime la position d'une cassure par linéarisations successives et en donne une erreur type, donc un intervalle. C'est le parent le plus proche d'elbow-helper sur l'idée qu'une affirmation de coude doit venir avec son incertitude ; le paquet R segmented en est la mise en œuvre.
8. Spearman, C. (1904). « The Proof and Measurement of Association between Two Things », American Journal of Psychology, 15(1), 72-101. Corrélation calculée sur les rangs plutôt que sur les valeurs. Elle sert ici d'examen de forme, insensible à l'échelle et peu troublée par quelques points extrêmes.
9. Theil, H. (1950). « A Rank-Invariant Method of Linear and Polynomial Regression Analysis », Proceedings of the Royal Netherlands Academy of Sciences, 53 ; Sen, P. K. (1968). « Estimates of the Regression Coefficient Based on Kendall's Tau », Journal of the American Statistical Association, 63(324), 1379-1389. Les deux articles fondent l'estimateur de pente par médiane des pentes de toutes les paires de points. C'est lui qui permet d'exiger un changement de pente sans qu'une poignée de valeurs aberrantes décide du verdict.
10. Arlot, S. et Celisse, A. (2010). « A survey of cross-validation procedures for model selection », Statistics Surveys, 4, 40-79. 10.1214/09-SS054 Revue qui sépare soigneusement ce qui est démontré de ce qui n'est qu'observé en validation croisée et montre que la forme des blocs retirés doit épouser la dépendance des données. C'est la justification du retrait par tronçons contigus employé ici.
11. Schwarz, G. (1978). « Estimating the Dimension of a Model », The Annals of Statistics, 6(2), 461-464. Fonde le BIC : une pénalité égale au nombre de paramètres multiplié par le logarithme du nombre d'observations, obtenue comme approximation de la vraisemblance marginale. C'est le score que la ligne brisée doit battre pour mériter son coude.
12. Kass, R. E. et Raftery, A. E. (1995). « Bayes Factors », Journal of the American Statistical Association, 90(430), 773-795. Donne l'approximation par laquelle un écart de BIC se lit comme une cote entre deux modèles et l'échelle de lecture qui va avec. C'est la probabilité a posteriori affichée dans la légende de la figure de diagnostic.
13. Efron, B. (1979). « Bootstrap Methods: Another Look at the Jackknife », The Annals of Statistics, 7(1), 1-26. Introduit le rééchantillonnage comme substitut à une loi d'échantillonnage qu'on ne sait pas écrire. Ici, c'est le bruit résiduel qu'on rebrasse, pour mesurer à quelle fréquence et à quel endroit le coude revient.
14. Davies, R. B. (1977). « Hypothesis testing when a nuisance parameter is present only under the alternative », Biometrika, 64(2), 247-254. 10.1093/biomet/64.2.247 Traite exactement la difficulté du coude : un paramètre qui n'existe que si l'hypothèse alternative est vraie, ici la position \(k\). Le test du rapport de vraisemblance y perd sa loi asymptotique usuelle, ce qui explique le recours à une valeur \(p\) simulée plutôt que lue dans une table.
15. Bellman, R. (1957). Dynamic Programming, Princeton University Press. Source canonique du principe d'optimalité : le début d'une solution optimale est optimal pour son propre sous-problème. C'est ce qui autorise la récursion utilisée ici pour placer plusieurs cassures.
16. Killick, R., Fearnhead, P. et Eckley, I. A. (2012). « Optimal Detection of Changepoints With a Linear Computational Cost », Journal of the American Statistical Association, 107(500), 1590-1598. PELT : la même récursion exacte, accélérée par un élagage qui écarte définitivement les découpages devenus sans espoir, d'où un coût linéaire sous certaines conditions sur la pénalité.
17. Zhang, N. R. et Siegmund, D. O. (2007). « A Modified Bayes Information Criterion with Applications to the Analysis of Comparative Genomic Hybridization Data », Biometrics, 63(1), 22-32. Introduit le BIC modifié dont le terme supplémentaire surveille la longueur des segments. C'est la référence dont le signe, repris tel quel d'abord, a dû être corrigé ici après mesure de son effet réel.
18. Dunn, O. J. (1961). « Multiple Comparisons Among Means », Journal of the American Statistical Association, 56(293), 52-64. 10.1080/01621459.1961.10482090 Établit et met en pratique l'inégalité qui porte en statistique le nom de Bonferroni : diviser le seuil par le nombre de tests borne le risque de se tromper au moins une fois. Employée ici dès que plusieurs nombres de cassures sont mis à l'épreuve.
19. Biernacki, C., Celeux, G. et Govaert, G. (2000). « Assessing a Mixture Model for Clustering with the Integrated Completed Likelihood », IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(7), 719-725. Le critère ICL, qui ajoute au BIC une pénalité sur l'incertitude du classement. Concurrent testé dans le comparatif, où il atteint 0,82 d'exactitude et 4 % de faux positifs.
20. Fryzlewicz, P. (2014). « Wild Binary Segmentation for Multiple Change-Point Detection », The Annals of Statistics, 42(6), 2243-2281. Analyse le défaut des recherches gloutonnes, qui s'engagent trop tôt sur une coupe et propagent l'erreur et propose d'y remédier par des intervalles tirés au hasard. Le comparatif de cet article retrouve ce défaut : chaque méthode gloutonne reste sous sa jumelle exhaustive.
21. Yao, Y.-C. (1988). « Estimating the number of change-points via Schwarz' criterion », Statistics and Probability Letters, 6(3), 181-189. Étudie le BIC appliqué au nombre de ruptures et documente sa tendance à en retenir trop. Les 27 % de faux positifs mesurés ici en sont une illustration sur des courbes linéaires par morceaux.
22. Harchaoui, W. (2026). Multi-knee method comparison: results, note de recherche du dépôt elbow-helper. research/multiknee/RESULTS.md Le protocole complet du comparatif cité plus haut : dix méthodes, trois cents courbes chacune, résultats détaillés par nombre de cassures et par niveau de bruit, temps de calcul et les six conclusions qui en sont tirées.
23. Harchaoui, W. (2026). ELBOW: Noise-Robust Knee and Elbow Detection, note technique du dépôt elbow-helper, en anglais. doc/ELBOW-en.pdf Dérive pas à pas chaque formule du paquet, de la normalisation au test de permutation, intuition et exemple travaillé avant chaque formule. C'est la version longue de tout ce que cet article résume.
24. Harchaoui, W. (2026). LIKELIHOOD, note technique du dépôt elbow-helper, en anglais. doc/LIKELIHOOD-en.pdf Le socle de vraisemblance repris plus haut : pourquoi la vraisemblance par observation, moyenne géométrique des densités, plutôt que le produit brut et comment la même construction se lit sur un modèle de classification.

Pour finir, trois lectures plus agréables qu'un article de revue. Mes livres préférés en IA donnent le panorama commenté dont sont tirés les deux suivants. The Elements of Statistical Learning de Hastie, Tibshirani et Friedman couvre la sélection de modèles et la validation croisée en général. Information Theory, Inference and Learning Algorithms de MacKay éclaire le lien, esquissé ici, entre vraisemblance, codage et perplexité.