Resultados empíricos en documentos CS

Soy nuevo en el campo de CS y he notado que en muchos de los artículos que leo, no hay resultados empíricos (sin código, solo lemas y pruebas). ¿Porqué es eso? Teniendo en cuenta que la informática es una ciencia, ¿no debería seguir el método científico?

Las matemáticas también son una ciencia, y tendrías que buscar durante mucho tiempo para encontrar resultados empíricos publicados en este campo (aunque supongo que debe haber algunos). Hay otros dominios científicos donde los "lemas y las pruebas" se valoran por encima de la experiencia, como la física cuántica. Dicho esto, la mayoría de las ciencias mezclan teoría y práctica (con varias proporciones), y la informática no es una excepción.

La informática tiene sus raíces en las matemáticas (véase la biografía de Turing, por ejemplo, http://en.wikipedia.org/wiki/Alan_Turing ), y como tal muchos resultados (generalmente denominados en el campo de la "informática teórica") consisten en pruebas que las computadoras en algún modelo computacional pueden resolver algún problema en una cantidad dada de operaciones (por ejemplo, conferencias como FOCS, STOC, SODA, SoCG, etc.). Sin embargo, muchos otros resultados de la informática están relacionados con la aplicabilidad de esas teorías a la vida práctica, a través del análisis de resultados experimentales (por ejemplo, conferencias como WADS, ALENEX, etc.).

A menudo se sugiere que el ideal es un buen equilibrio entre la teoría y la práctica, como en "Ciencias Naturales", donde la observación de los experimentos lleva a la generación de nuevas teorías, que a su vez sugieren nuevos experimentos para confirmar o debilitarlos: las conferencias intentan aceptar resultados tanto experimentales como teóricos (por ejemplo, ESA, ICALP, LATIN, CPM, ISAAC, etc.). El subcampo de "Algoritmos y estructuras de datos" en ciencias de la computación podría sufrir un desequilibrio en el sentido de que las conferencias "teóricas" generalmente están mejor clasificadas que las experimentales. Creo que esto no es cierto en otros subcampos de la informática, como HCI o AI.

¿Espero eso ayude?

Implementar bien los algoritmos es una habilidad que requiere un conjunto diferente de herramientas que solo probar teoremas. Muchos algoritmos que fueron descubiertos por la comunidad teórica se han implementado en la práctica (aunque me gustaría ver que la comunidad teórica desempeñara un papel más importante en este proceso). La física no le pide a los mismos investigadores que hagan teoría y experimenten, aunque se espera que los dos grupos se comuniquen. ¿Por qué no debería esperar ver la misma división en informática?

AGREGADO EN EDITAR:

Ampliando mi comentario en respuesta a Suresh sobre lo que quise decir con "rol" arriba, en los Laboratorios Bell Labs y AT&T, se alentó a los investigadores en algoritmos a hablar con las personas en desarrollo. No hice tanto de lo que probablemente debería haber hecho, pero obtuve al menos un trabajo , y creo que sería bueno para el campo si hubiera más comunicación entre las personas en teoría en las universidades y los profesionales. . Esto no significa que piense que todos los que presenten un algoritmo deberían codificarlo (incluso si es práctico).

Por otro lado, los algoritmos de codificación (o hacer que un alumno los codifique) que creas que pueden ser prácticos pueden ser útiles para que los profesionales los adapten. Considere un ejemplo. Lempel y Ziv escribieron dos documentos técnicos en 1977 y 1978 sobre nuevos algoritmos de compresión de datos. Todos los ignoraron. En 1984, Welch escribió un artículo mucho menos técnico dando un ligero giro en LZ78 que mejoró un poco su rendimiento, y dio los resultados de un pequeño estudio que compara su rendimiento con otros métodos de compresión de datos. Fue publicado en una revista leída por varios programadores, y el algoritmo fue dado por unas pocas líneas de pseudocódigo. El método se adaptó rápidamente en varios lugares, lo que finalmente resultó en una disputa infame de propiedad intelectual.

Por supuesto, una de las mejores formas para que los investigadores de algoritmos se comuniquen con la práctica es producir estudiantes graduados que se vayan y trabajen en Google, IBM u otras compañías, y ya lo estamos haciendo. Otra forma podría ser responder las preguntas de los profesionales en este foro. Con suerte, también estamos haciendo un trabajo razonable al respecto.

Un área de investigación que utiliza métodos empíricos y métodos de informática teórica es el campo llamado "Algoritmos experimentales" o "Ingeniería de algoritmos". Como mencionó Chris, la informática de alto rendimiento depende en gran medida de esto, ya que los sistemas modernos tienen problemas complejos de caché y latencia que nos cuesta modelar.

Gerth Brodal y Peter Sanders son buenos ejemplos de investigadores que mantienen un pie en los reinos "prueba" y "empírico".

--Actualización 20/01/2013-- También mencionaría una gran presentación de Robert Sedgewick .

Esto depende de la disciplina en la que se encuentre; Como afirma Jeremy, hay un espectro de teoría versus práctica.

Temas como la complejidad tienden a ser ponderados hacia el lado de la teoría, ya que a menudo el objetivo es encontrar un límite para el espacio o el tiempo de ejecución. Implementar un algoritmo en C ++ y luego ejecutarlo varias veces no probará que un problema es NP-completo.

Como polar opuesto, la informática de alto rendimiento (con conferencias como Supercomputing ) es empírica; nadie presentará una prueba a una publicación de HPC ya que hay demasiada variabilidad con respecto a la jerarquía de memoria y la sobrecarga del núcleo.

Entonces, lo que parece ser la misma pregunta (¿Cuánto tiempo lleva ejecutar algo?) Se abordará de dos maneras completamente diferentes dependiendo de los objetivos, las técnicas, la comunidad, etc. Vea Poul-Henning Kamp's You're Doing It Wrong para un ejemplo de La disonancia.

En la investigación de lenguajes de programación, muchas ideas para nuevas construcciones de lenguaje de programación o nuevos mecanismos de verificación de tipos provienen de la teoría (quizás informadas por la experiencia en la práctica, quizás no). A menudo se escribe un artículo sobre tales mecanismos desde una perspectiva formal / teórica / conceptual. Eso es relativamente fácil de hacer. Luego viene el primer obstáculo: implementar las nuevas construcciones en el contexto de un compilador existente y experimentar con él, en términos de eficiencia o flexibilidad. Esto también es relativamente fácil.

Pero, ¿podemos decir que la construcción de programación constituye un avance para la ciencia de la programación? ¿Podemos decir que facilita la escritura de programas? ¿Podemos decir que mejora el lenguaje de programación?

La respuesta es no. Sería necesaria una evaluación empírica adecuada que involucrara a decenas de programadores experimentados durante largos períodos de tiempo para responder a ese tipo de preguntas. Esta investigación casi nunca se hace. El único juez del valor de un lenguaje de programación (y sus construcciones) es la popularidad del lenguaje. Y para los puristas del lenguaje de programación, esto va en contra de lo que nos dicen nuestras hipótesis.

Quizás me falta la motivación para su pregunta, pero hay muchos ejemplos de resultados empíricos que motivan la investigación, los algoritmos y otros resultados.

MP3 utiliza psicoacústica para optimizar el algoritmo para la codificación humana.

$\pi$

En la misma línea, Bailey y Borwein son grandes defensores de las matemáticas experimentales. Consulte "La computadora como crisol: una introducción a las matemáticas experimentales" , "Excursiones computacionales en teoría de números", entre otros . Se podría argumentar que se trata de Matemáticas más experimentales, pero yo diría que a este nivel la discusión la distinción es semántica.

Las transiciones de fase de los problemas de NP-Complete son otra área en la que los resultados empíricos son muy utilizados. Ver Monasson, Zecchina, Kirkpatrick, Selman y Troyansky y Gent y Walsh para empezar, aunque hay muchos, muchos más (ver aquí para una breve encuesta).

Aunque no es en el nivel del teórico Informática o Matemáticas, hay una discusión aquí sobre cómo promedio de latidos caso de ejecución del grep utilidad Unix optimizados peores algoritmos de casos porque se basa en el hecho de que es la búsqueda de texto legible por humanos (grep hace lo malo o peor en archivos con caracteres aleatorios en ellos).

Incluso Gauss utilizó evidencia experimental para dar su hipótesis del teorema del número primo.

Se podría argumentar que la minería de datos ( la solución de Bellkor al Premio Netflix para hacer un mejor sistema de recomendación) es una teoría completamente basada en evidencia empírica. La inteligencia artificial (algoritmos genéticos, redes neuronales, etc.) depende en gran medida de la experimentación. La criptografía está en un constante empuje y atracción entre los creadores de código y los rompedores de código. Realmente solo he nombrado algunos y si relaja su definición de empírico, entonces podría lanzar una red aún más amplia.

Mis disculpas por estar tan disperso al responder su pregunta, pero espero haber dado al menos algunos ejemplos que sean útiles.