Resultados empíricos en documentos CS

31

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?

toto
fuente
26
La respuesta corta es que la "informática" es muchas cosas. Algunas partes como (algunas) IA en realidad son ciencia. Otras partes son ingeniería, y el lado teórico es la matemática (aplicada). Partes de HCI se parecen más al arte. La informática es una tienda de campaña amplia.
Aaron Roth
66
Si tiene pruebas, ¿por qué necesita resultados empíricos?
Aryabhata
2
@ Moron: ¿Cómo demuestras que un algoritmo es implementable sin implementarlo?
Jukka Suomela
8
El CS teórico parece ser similar a la física matemática, que también evita resultados empíricos. Si desea algo como Física Experimental, puede buscar investigación en Ingeniería de Software, Verificación de Programas, Sistemas de Base de Datos, etc.
Yaroslav Bulatov
44
nitpicking: " el método científico"?
Kaveh

Respuestas:

21

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?

Jeremy
fuente
Gracias, realmente ayuda mucho. Últimamente me ha interesado la teoría de gráficos y en los artículos que estaba leyendo, casi ninguno de ellos tenía código o resultados experimentales. Por eso pregunté. Cuando haces matemáticas puras, no puedes producir resultados experimentales, por lo tanto, las pruebas lo son todo. ¡Pero en Graph Theory no es tan difícil codificar su algoritmo y producir resultados experimentales útiles! Tomemos el problema MST. Las implementaciones actuales de la industria son Prim / Kruskal y Boruvska y, sin embargo, se describen algoritmos más potentes en los documentos, pero no se utilizan ya que nadie los ha codificado.
toto
1
NP
1
@ toto Ciertamente, lo que está diciendo se aplica a algunos problemas, pero para el problema de MST, puede ver los resultados (quizás algo desactualizados) de implementar algunos de los algoritmos poderosos en books.google.com/…
Abel Molina
1
O(n)O(nlogn)
24

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.

Peter Shor
fuente
44
Entonces, ¿estás diciendo que aunque en física no hay expectativas de que la misma persona haga ambas cosas, en teoría CS deberíamos hacer ambas? ¿Es porque los modelos de computación son mucho más una aproximación a la realidad que los modelos físicos?
Suresh Venkat
10
Estoy diciendo que los teóricos deberían hablar más con los practicantes. Si miras la historia de la física, las cosas malas comienzan a suceder cuando los teóricos dejan de hablar con los experimentadores. De hecho, creo que tenemos una cantidad razonable de comunicación entre los dos grupos en este momento, pero que no estaría de más tener algo más.
Peter Shor
3
No voy a generalizar, pero creo que muchos investigadores simplemente no pueden codificar / no les gusta y prefieren dejar que el trabajo práctico sea realizado por uno de sus estudiantes. Ese es el caso conmigo y mi mentor.
toto
La tensión asociada a la especificación formal versus la computación práctica se remonta a la historia de STEM. A veces, los pliegos de especificación formales ("Sobre la teoría de las ondas de detonación estacionarias" de von Neumann [1948] versus simulaciones computacionales posteriores) y, a veces, plomos de cómputo prácticos ("El nuevo navegador práctico estadounidense" de Bowditch [1807] versus "Disquisiciones generales alrededor de las superficies" de Gauss [1827]). Los mejores matemáticos (Gauss y von Neumann en los ejemplos citados anteriormente) a menudo han combinado especificaciones formales con cálculos prácticos.
John Sidles
3
La historia de Lempel-Ziv, y mirando publicaciones en StackOverflow, me han llevado a formular un precepto muy simple que podría ayudar a que los teóricos de algoritmos presenten practicantes vy implementados: si cree que su algoritmo podría ser práctico, coloque pseudocódigo en su papel.
Peter Shor
17

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 .

Chad Brewbaker
fuente
44
Tanto ALENEX como ESA fomentan el trabajo de algoritmos aplicados, y también hay una conferencia (SAE) sobre este tema.
Suresh Venkat
¿Qué es SAE? Ese TLA no se puede googlear. ¿Tienes una URL para ello?
Peter Boothe
55
SAE es un error tipográfico para SEA, el Simposio sobre algoritmos experimentales.
David Eppstein
1
También puede realizar la Ingeniería de algoritmos de una manera más rigurosa, es decir, refinar los modelos teóricos para que se ajusten a la realidad pero aún así realizar análisis precisos. Sin embargo, es difícil.
Raphael
O(CubeRoot(n))
12

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.

chrisaycock
fuente
10

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.

Dave Clarke
fuente
7

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.

π

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.

usuario834
fuente