Résultats empiriques dans les articles CS

Je suis nouveau dans le domaine CS et j'ai remarqué que dans la plupart des articles que j'ai lus, il n'y a pas de résultats empiriques (pas de code, juste des lemmes et des preuves). Pourquoi donc? Étant donné que l'informatique est une science, ne devrait-elle pas suivre la méthode scientifique?

Les mathématiques sont aussi une science, et il faudrait chercher longtemps pour trouver des résultats empiriques publiés dans ce domaine (même si je suppose qu'il doit y en avoir). Il existe d'autres domaines scientifiques où «les lemmes et les preuves» sont valorisés par rapport à l'expérience, comme la physique quantique. Cela dit, la plupart des sciences mélangent théorie et pratique (avec différents ratios), et l'informatique ne fait pas exception.

L'informatique a ses racines dans les mathématiques (voir la biographie de Turing par exemple http://en.wikipedia.org/wiki/Alan_Turing ), et à ce titre de nombreux résultats (généralement surnommés comme dans le domaine de "l'informatique théorique") consistent en des preuves que les ordinateurs dans certains modèles de calcul peuvent résoudre certains problèmes dans un nombre d'opérations donné (par exemple, des conférences telles que FOCS, STOC, SODA, SoCG, etc.). Néanmoins, de nombreux autres résultats de l'informatique se préoccupent de l'applicabilité de ces théories à la vie pratique, à travers l'analyse de résultats expérimentaux (par exemple des conférences telles que WADS, ALENEX, etc ...).

Il est souvent suggéré que l'idéal est un bon équilibre entre la théorie et la pratique, comme dans les "sciences naturelles", où l'observation des expériences incite à la génération de nouvelles théories, qui à leur tour suggèrent de nouvelles expériences pour confirmer ou infirmer celles-ci: comme beaucoup les conférences tentent d'accepter les résultats expérimentaux et théoriques (par exemple ESA, ICALP, LATIN, CPM, ISAAC, etc ...). Le sous-domaine des "algorithmes et structures de données" en informatique pourrait souffrir d'un déséquilibre dans le sens où les conférences "théoriques" sont généralement mieux classées que les conférences expérimentales. Je crois que ce n'est pas vrai dans d'autres sous-domaines de l'informatique, tels que HCI ou AI.

J'espère que ça aide?

La bonne mise en œuvre des algorithmes est une compétence qui nécessite un ensemble d'outils différent de la simple démonstration des théorèmes. De nombreux algorithmes qui ont été découverts par la communauté théorique ont en effet été mis en œuvre dans la pratique (bien que j'aimerais que la communauté théorique joue un rôle plus important dans ce processus). La physique ne demande pas aux mêmes chercheurs de faire de la théorie et de l'expérimentation, bien que l'on s'attende à ce que les deux groupes communiquent. Pourquoi ne vous attendriez-vous pas à voir le même fossé en informatique?

AJOUTÉ EN ÉDIT:

En développant mon commentaire en réponse à celui de Suresh sur ce que je voulais dire par «rôle» ci-dessus, aux Bell Labs et AT&T Labs, les chercheurs en algorithmes ont été encouragés à parler aux personnes en développement. Je n'ai pas fait autant de choses que j'aurais probablement dû, mais j'en ai retiré au moins un document , et je pense que ce serait bon pour le domaine s'il y avait plus de communication entre les gens théoriques dans les universités et les praticiens . Cela ne signifie pas que je pense que tous ceux qui proposent un algorithme devraient le coder (même si c'est pratique).

D'un autre côté, les algorithmes de codage (ou demander à un élève de les coder) que vous pensez être pratiques peuvent être utiles pour les faire adapter par les praticiens. Prenons un exemple. Lempel et Ziv ont écrit deux articles techniques en 1977 et 1978 sur les nouveaux algorithmes de compression de données. Tout le monde les a ignorés. En 1984, Welch a écrit un article beaucoup moins technique donnant une légère torsion au LZ78 qui a quelque peu amélioré ses performances et a donné les résultats d'une petite étude comparant ses performances avec d'autres méthodes de compression de données. Il a été publié dans un journal lu par un certain nombre de programmeurs, et l'algorithme a été donné par quelques lignes de pseudocode. La méthode a été rapidement adaptée dans un certain nombre d'endroits, ce qui a finalement abouti à un tristement célèbre litige de propriété intellectuelle.

Bien sûr, l'un des meilleurs moyens pour les chercheurs en algorithmes de communiquer avec la pratique est de former des étudiants diplômés qui partent travailler chez Google, IBM ou d'autres entreprises, et nous le faisons déjà. Une autre façon pourrait être de répondre aux questions des pratiquants dans ce forum. J'espère que nous faisons également un travail raisonnable.

Un domaine de recherche qui utilise des méthodes empiriques et des méthodes de l'informatique théorique est le domaine appelé "algorithmique expérimentale" ou "génie algorithmique". Comme Chris l'a mentionné, l'informatique haute performance dépend fortement de cela, car les systèmes modernes ont des problèmes complexes de cache et de latence que nous avons du mal à modéliser.

Gerth Brodal et Peter Sanders sont de bons exemples de chercheurs qui maintiennent un pied dans les domaines "preuve" et "empirique".

--Mise à jour 1/20 / 2013-- Je mentionnerais également une excellente présentation de Robert Sedgewick .

Cela dépend de la discipline dans laquelle vous vous trouvez; comme le dit Jeremy, il y a un spectre de théorie contre pratique.

Des sujets comme la complexité ont tendance à être pondérés du côté de la théorie, car le but est souvent de trouver une limite pour l'espace ou le temps d'exécution. Implémenter un algorithme en C ++ puis l'exécuter plusieurs fois ne va pas prouver qu'un problème est NP-complet.

En tant qu'opposé polaire, le calcul haute performance (avec des conférences comme le Supercalcul ) est tout empirique; personne ne soumettrait jamais de preuve à une publication HPC car il y a trop de variabilité en ce qui concerne la hiérarchie de la mémoire et la surcharge du noyau.

Donc, ce qui semble être la même question (combien de temps faut-il pour fonctionner?) Sera abordé de deux manières complètement différentes selon les objectifs, les techniques, la communauté, etc. Voir Poul-Henning Kamp's Vous le faites mal pour un exemple de la dissonance.

Dans les langages de programmation, de nombreuses idées pour de nouvelles constructions de langage de programmation ou de nouveaux mécanismes de vérification de type découlent de la théorie (peut-être fondées sur l'expérience pratique, peut-être pas). Souvent, un article est écrit sur ces mécanismes d'un point de vue formel / théorique / conceptuel. C'est relativement facile à faire. Vient ensuite le premier obstacle: mettre en œuvre les nouvelles constructions dans le contexte d'un compilateur existant et l'expérimenter, en termes d'efficacité ou de flexibilité. Cela aussi est relativement facile.

Mais peut-on alors dire que la construction de la programmation constitue une avancée dans la science de la programmation? Peut-on dire que cela facilite l'écriture de programmes? Peut-on dire que cela améliore le langage de programmation?

La réponse est non. Une évaluation empirique appropriée impliquant des dizaines de programmeurs expérimentés sur de longues périodes serait nécessaire pour répondre à ce type de questions. Cette recherche est rarement réalisée. Le seul juge de la valeur d'un langage de programmation (et de ses constructions) est la popularité du langage. Et pour les puristes du langage de programmation, cela va à l'encontre de ce que nos hypothèses nous disent.

Je manque peut-être la motivation de votre question, mais il existe de nombreux exemples de résultats empiriques motivant la recherche, les algorithmes et d'autres résultats.

Les MP3 utilisent la psychoacoustique pour optimiser l'algorithme d'encodage humain.

$\pi$

Dans le même ordre d'idées, Bailey et Borwein sont de grands partisans des mathématiques expérimentales. Voir «L'ordinateur comme creuset: une introduction aux mathématiques expérimentales» , «Excursions computationnelles en théorie des nombres», entre autres . On pourrait soutenir qu'il s'agit de mathématiques plus expérimentales, mais je dirais qu'à ce niveau, la discussion est une distinction sémantique.

Les transitions de phase des problèmes NP-Complete sont un autre domaine où les résultats empiriques sont largement utilisés. Voir Monasson, Zecchina, Kirkpatrick, Selman et Troyansky et Gent et Walsh pour les débutants, bien qu'il y en ait beaucoup, beaucoup plus (voir ici pour un bref aperçu).

Bien que n'étant pas tout à fait au niveau de l'informatique théorique ou des mathématiques, il y a une discussion ici sur la façon dont l'exécution moyenne des cas de grep de l'utilitaire unix bat les algorithmes optimisés dans le pire des cas, car il repose sur le fait qu'il recherche du texte lisible par l'homme (grep fait aussi mal ou pire sur les fichiers contenant des caractères aléatoires).

Même Gauss a utilisé des preuves expérimentales pour donner son hypothèse du théorème des nombres premiers.

L'exploration de données ( solution de Bellkor au prix Netflix pour faire un meilleur système de recommandation) pourrait être considérée comme une théorie entièrement basée sur des preuves empiriques. L'intelligence artificielle (algorithmes génétiques, réseaux de neurones, etc.) s'appuie fortement sur l'expérimentation. La cryptographie est en constante évolution entre les créateurs de code et les casseurs de code. Je n'en ai vraiment cité que quelques-uns et si vous assouplissez votre définition de l'empirique, vous pourriez jeter un filet encore plus large.

Je m'excuse d'avoir été si dispersé en répondant à votre question, mais j'espère avoir donné au moins quelques exemples utiles.