,
56 tweets,
5 min read
Read on Twitter
C'est une excellente question, disais-je.
Je verrais plusieurs sens à cette question.
(Je précise que je ne me pique d'aucune connaissance ou aptitude spécialisée en philosophie ou épistémologie...
..et que donc ce qui suivra sera peut-être considéré comme très basique par les spécialistes de ces questions.)
Je me place dans le cas d'un article présentant d'une part un algorithme ou une méthode d'autre part des résultats expérimentaux.
En effet, sur un article de pure théorie (algorithme + preuve, théorème + preuve...) la question ne se pose pas.
1) Est-ce que des collègues réimplémentant l'algorithme et l'appliquant à des exemples semblables obtiendraient des résultats semblables?
2) Est-ce que des collègues réimplémentant l'algorithme et l'appliquant aux mêmes exemples que moi obtiendraient des résultats semblables?
3) Est-ce que des collègues utilisant mon implémentation sur d'autres exemples que les miens obtiendraient des résultats semblables?
4) Est-ce que des collègues utilisant mon implémentation sur mes exemples obtiendraient des résultats semblables?
Pour le point 4) il me suffit de fournit mes exemples et mon implémentation.
Mais rien ne dit que mes exemples soient représentatifs des problèmes que les gens voudraient résoudre !
Il me serait possible de fournir des exemples choisis tandis que mon outil serait inefficace sur d'autres, tout aussi réalistes.
Se pose donc la question du réalisme des exemples de test.
Rappelons qu'à peu près tout en vérification est indécidable (pas d'algorithme), PSPACE-dur ou du moins NP-dur (forte complexité).
Je ne peux donc pas prétendre fournir un algorithme efficace sur toute instance (ou alors je prouve P=NP et je deviens riche et célèbre).
Je vais donc argumenter qu'ok c'est NP-dur et mon algorithme est exponentiel dans le pire cas, mais le pire cas n'arrive pas en pratique.
"Les vrais problèmes du vrai monde" par opposition à "des instances tordues artificielles".
(Variante de "les vrais gens" vs "les bobos parisianistes sophistiqués")
Par exemple, "sur les vrais problèmes, les dénominateurs dans l'algorithme du simplexe en rationnels ne croissent pas tant que cela".
Mais qu'est-ce qu'un "vrai problème" ?
Il existe, pour certaines catégories de problèmes, des bibliothèques de "cas de test" destinés à l'évaluation de performance.
Mais rien ne nous dit que ces cas de tests soient significatifs de ce que des vrais gens voudraient résoudre !
Parfois, les cas de tests ne sont pas fournis: c'est le cas notamment s'il s'agit d'exemples industriels obtenus sous NDA.
NDA = non disclosure agreement = je n'ai pas le droit de communiquer à d'autres un document qu'on m'a confié, voire de commenter dessus
Tout ceci n'est déjà guère réjouissant. Mais il y a pire!
Parfois, l'outil n'est pas disponible, donc impossible pour un tiers de vérifier les prétentions des auteurs dans un article.
Ou alors l'outil est disponible, mais il ne fonctionne qu'avec telle vieille version de tel logiciel mais nouvelle version de tel autre.
Ou il est tellement mal documenté et on ne sait plus où sont les fichiers d'exemple et puis le doctorant est parti et puis
(Il faut se rendre compte dans quelle urgence les articles sont parfois finis avant soumission..)
Bref, tout ceci est fort peu reproductible. CEPENDANT
De plus en plus de publications recommandent fortement d'envoyer, après acceptation d'un article, un "artefact".
Cet artefact doit permettre à des tiers de constater les performances de l'outil, au moins sur les exemples fournis par l'auteur.
Surtout, dans ce que je fais, le résultat scientifique objet des articles n'est PAS un résultat expérimental.
L'article dit "je propose un algorithme pour résoudre X et je démontre mathématiquement qu'il résout effectivement X"...
"...pour justifier que cet algorithme est utile, je l'ai essayé sur des exemples et ça semble cool en performance et précision".
Le "ça semble cool" est évidemment de portée limitée, ce n'est pas "ce traitement est plus efficace que tel autre contre ce type de cancer".
Prenons un exemple concret. @DLeBerre et @lorensipro développent des outils appelés "SAT-solveurs".
Ils testent leurs outils notamment sur des exemples de la "SAT competition".
Leurs outils résolvent un problème NP-complet, et on sait générer des exemples qui les feront forcément exploser.
Ce qui est reproductible, c'est que si on reprend leurs outils et qu'on les repasse sur ces exemples, on aura des performances similaires.
Et encore! Ces outils ont un générateur de nombres pseudo-aléatoires, il faut donc l'initialiser identiquement pour pouvoir comparer.
Si un outil est efficace sur ces exemples, puis-je en déduire qu'il sera efficace sur les miens? Pas vraiment
Où suis-je censé prendre des exemples significatifs? Bonne question!
Mardi prochain nous discuterons avec des collègues de l'ETH Zürich sur le problème d'obtenir des bons exemples sur les polyèdres.
Parfois aussi il est difficile de comparer des outils pour en gros le même problème car le format d'entrée est différent.
Parfois la conversion est simple, parfois il y a des divergences de vision qui rendent l'écriture d'un convertisseur difficile.
Il y a aussi qu'une thèse dure 3 ans et qu'un doctorant ne peut passer sa vie à faire de l'ingénierie pour des problèmes de benchmark.
Je conçois que ces réponses soient peu satisfaisantes.
Toutefois, je rappelle que dans mon domaine, on prétend rarement montrer expérimentalement un résultat universel.
On ne dit pas quelque chose d'équivalent à "nous savons reconnaître les homosexuels d'après leur portrait".
On dit "notre algorithme semble se comporter favorablement par rapport aux autres sur ces exemples: XXX".
Une des difficultés pour les "vrais exemples" est que prendre des exemples industriels en vraie grandeur est compliqué.
C'est un peu comme si pour tester une hypothèse sur la combustion dans les moteurs on vous demandait de concevoir et construire...
...vous même toute une automobile suffisamment fiable pour rouler avec des passagers.
Nous avons rarement le temps, les moyens humains, etc. de faire cela.
