Justificar el análisis asintótico del peor de los casos a los científicos

He estado trabajando para introducir algunos resultados de la complejidad computacional en la biología teórica, especialmente la evolución y la ecología , con el objetivo de ser interesante / útil para los biólogos. Una de las mayores dificultades que he enfrentado es justificar la utilidad del análisis asintótico del peor de los casos para los límites inferiores. ¿Hay referencias de longitud de artículos que justifiquen los límites inferiores y el análisis asintótico del peor de los casos para una audiencia científica?

Realmente estoy buscando una buena referencia que pueda diferir en mi escritura en lugar de tener que pasar por las justificaciones en el espacio limitado que tengo disponible (ya que ese no es el punto central del artículo). También conozco otros tipos y paradigmas de análisis, por lo que no busco una referencia que diga que el peor de los casos es el "mejor" análisis (ya que hay configuraciones cuando realmente no lo es), pero no lo es. completeletely inútil: todavía nos da una visión puede teóricamente útiles sobre el comportamiento de los actuales algoritmos de reales entradas. También es importante que la escritura esté dirigida a científicos generales y no solo ingenieros, matemáticos o informáticos.

Como ejemplo, el ensayo de Tim Roughgarden que presenta la teoría de la complejidad a los economistas está en el camino correcto para lo que quiero. Sin embargo, solo las secciones 1 y 2 son relevantes (el resto es demasiado específico para la economía) y la audiencia prevista está un poco más cómoda con el pensamiento a prueba de teorema-lema que la mayoría de los científicos ^[1] .

Detalles

En el contexto de la dinámica adaptativa en la evolución , he conocido dos tipos específicos de resistencia de biólogos teóricos:

[A] "¿Por qué debería importarme el comportamiento del arbitrario ? Ya sé que el genoma tiene pares de bases (o tal vez genes) y nada más". $n$ $n = 3*10^9$ $n = 2*10^4$

Esto es relativamente fácil de ignorar con el argumento de "podemos imaginar esperar segundos, pero no ". Pero, un argumento más complejo podría decir que "claro, usted dice que le importa solo una específica , pero sus teorías nunca usan este hecho, solo usan que es grande pero finito, y es su teoría con la que estamos estudiando análisis asintótico ". $10^9$ $2^{10^9}$ $n$

[B] "Pero solo demostró que esto es difícil al construir este paisaje específico con estos dispositivos. ¿Por qué debería importarme esto en lugar del promedio?"

Esta es una crítica más difícil de abordar, porque muchas de las herramientas que la gente usa comúnmente en este campo provienen de la física estadística, donde a menudo es seguro asumir una distribución uniforme (u otra distribución simple específica). Pero la biología es "física con historia" y casi todo no está en equilibrio o "típico", y el conocimiento empírico es insuficientepara justificar supuestos sobre distribuciones sobre entrada. En otras palabras, quiero un argumento similar al utilizado contra el análisis de caso promedio de distribución uniforme en ingeniería de software: "modelamos el algoritmo, no podemos construir un modelo razonable de cómo el usuario interactuará con el algoritmo o cuál es su distribución de entradas serán, eso es para psicólogos o usuarios finales, no para nosotros ". Excepto en este caso, la ciencia no está en una posición en la que exista el equivalente de 'psicólogos o usuarios finales' para descubrir las distribuciones subyacentes (o si eso es significativo).

Notas y preguntas relacionadas

El enlace discute las ciencias cognitivas, pero la mentalidad es similar en biología. Si navega por Evolution o Journal of Theoretical Biology , rara vez verá prueba de teorema-lema, y cuando lo haga, generalmente será solo un cálculo en lugar de algo así como una prueba de existencia o una construcción intrincada.
Paradigmas para el análisis de complejidad de algoritmos
¿Otros tipos de análisis de tiempo de ejecución además del peor de los casos, el caso promedio, etc.?
Ecología y evolución a través del lente algorítmico.
Por qué los economistas deberían preocuparse por la complejidad computacional

cc.complexity-theory reference-request big-picture application-of-theory worst-case Artem Kaznatcheev
fuente

El comportamiento en el peor de los casos es imposible de justificar ... el algoritmo simplex tiene un comportamiento exponencial en el peor de los casos, y las únicas personas que alguna vez se han preocupado son los teóricos. Lo que necesita argumentar es: (a) el comportamiento asintótico de caso promedio es importante; (b) el comportamiento asintótico en el caso promedio y el comportamiento asintótico en el peor de los casos son bastante similares; (c) el comportamiento asintótico en el peor de los casos es a menudo mucho más fácil de calcular que el comportamiento asintótico en el caso promedio (especialmente porque nadie sabe cuál es la distribución de probabilidad relevante).

Peter Shor

Las asíntóticas ya son un aspecto problemático. Todos conocemos la historia sobre algoritmos de multiplicación de matrices (los límites superiores asintóticos no tienen sentido en la práctica), y quizás también la historia sobre la elección de parámetros en criptografía (los límites inferiores asintóticos no tienen sentido en la práctica; los algoritmos exponenciales a veces son factibles [DES]). Si su análisis tiene constantes reales, entonces es más convincente.

Yuval Filmus

Si piensa en la computación como un juego (es decir, una guerra) entre el proveedor de entrada y el algoritmo, entonces el análisis del peor de los casos es un enfoque militar estándar: desea saber qué tan malo puede ser. En segundo lugar, y lo que es más importante, el análisis del peor de los casos no le permite ser intelectualmente perezoso y aceptar soluciones que podrían ser buenas para lo que usted cree que es el mundo (y no como es realmente el mundo). Finalmente, y quizás lo más importante, proporciona una forma uniforme de comparar algoritmos de una manera esperanzadora y significativa. En resumen, es el peor enfoque, a excepción de todos los demás.

Sariel Har-Peled

Creo que un límite inferior en el peor de los casos debería verse como devolver la pelota a su cancha. Ha demostrado que no existe un algoritmo que pueda resolver su problema en todas las instancias en un plazo razonable. Pueden creer razonablemente que sus instancias son fáciles, pero usted acaba de demostrar que si es así, no es un hecho trivial. Por lo tanto, su modelo es incompleto a menos que presenten una explicación de por qué es así.

Aaron Roth

(Este es el enfoque que parece funcionar cuando se habla con los teóricos de los juegos. Plantea la pregunta, si los mercados realmente se equilibran rápidamente, ¿qué propiedad especial tienen los mercados reales que supere la peor dureza de los casos? Es probable que sea posible definir un plausible dicha propiedad, y los límites inferiores solo sugieren que hacerlo es una dirección de investigación importante)

Aaron Roth

Respuestas:

Mi opinión personal (y parcial) es que el análisis asintótico del peor de los casos es un paso histórico hacia tipos de análisis más prácticos. Por lo tanto, parece difícil justificar a los practicantes.

Probar límites para el peor de los casos es a menudo más fácil que probar límites incluso para definiciones "agradables" de caso promedio. El análisis asintótico también suele ser mucho más fácil que demostrar límites razonablemente estrechos. El análisis asintótico en el peor de los casos es, por lo tanto, un excelente lugar para comenzar.

El trabajo de Daniel Spielman y Shanghua Teng sobre el análisis simplificado de Simplex me parece un presagio de lo que puede suceder cuando comenzamos a comprender mejor la forma de un problema: abordar el peor de los casos primero permite que se comprenda mejor. desarrollado. Además, como Aaron Roth sugirió en los comentarios, si el comportamiento "habitual" de un sistema es significativamente diferente de su peor caso, entonces el sistema aún no está completamente especificado y se necesita más trabajo para mejorar el modelo. Por lo tanto, ir más allá del peor de los casos generalmente parece importante como un objetivo a largo plazo.

En lo que respecta al análisis asintótico, generalmente sirve para mantener una prueba larga y desordenada libre de detalles que distraigan. Desafortunadamente, actualmente no parece haber una manera de recompensar el tedioso trabajo de completar los detalles para obtener las constantes reales, por lo que rara vez parece hacerse. (Los límites de página también funcionan en contra de esto). El análisis cuidadoso de los detalles de un límite asintótico ha llevado a algoritmos reales, con buenos límites en las constantes, por lo que personalmente me gustaría ver más de este tipo de trabajo. Quizás si se formalizaran más pruebas utilizando sistemas asistentes de prueba, entonces las constantes podrían estimarse con menos esfuerzo adicional. (O los límites en las constantes, en la línea del límite de Gowers para el Lema de regularidad de Szemerédi, podrían volverse más rutinarios). También hay formas de probar los límites inferiores que están libres de constantes, mediante el uso de modelos de máquina más explícitos (como los autómatas deterministas de estado finito). Sin embargo, tales límites inferiores (casi) exactos para modelos de cómputo más generales pueden requerir mucho trabajo o estar fuera de alcance por completo. Esto parece haberse llevado a cabo en ~ 1958-1973 durante el primer apogeo de la teoría de los autómatas, pero, por lo que puedo decir, desde entonces se ha dejado solo en gran medida.

$O$ $(n^k)$

András Salamon
fuente

No comparto su entusiasmo por deshacerse de los asintóticos en favor de límites precisos con constantes definidas. Los asintóticos pueden ser imprecisos, pero son útilmente imprecisos. Se resumen sobre las diferencias de implementación para el mismo modelo de máquina. Por ejemplo, un algoritmo de clasificación que era cuadrático en el hardware de la década de 1950 seguirá siendo cuadrático en el hardware de hoy. Además, las fórmulas asintóticas se componen muy bien. Los lineales y los polinomios están cerrados bajo composición, por ejemplo. (Tenga en cuenta que argumentar a favor de mejores límites en el caso promedio en comparación con el peor de los casos es ortogonal de argumentar en contra de los asintóticos)

Brandjon

Tiene razón en general, pero hay una gran diferencia entre una constante pequeña y una que es una función no elemental de un parámetro relevante.

András Salamon

Me gusta esta respuesta en general, pero estoy de acuerdo con @brandjon en que ocultar las constantes es crucial. Para mí, la razón por la cual TCS es útil en biología es porque necesita hacer muchas menos suposiciones acerca de la micro dinámica que la física. Sin embargo, si no hace suposiciones sobre la micro dinámica (es decir, la especificación exacta del modelo de cálculo), entonces no puede obtener los factores constantes. La otra característica útil de TCS son las rigurosas dicotomías cualitativas (algo que es más fácil de comparar con las observaciones más cualitativas en bio), por lo general, para obtenerlas también hay que deshacerse de las constantes.

Artem Kaznatcheev

\tilde{O} (n^{\tilde{O} (1 / ϵ)})

$\tilde{O}(n^{\tilde{O}(1/\epsilon)})$

Como nota al margen, hay ejemplos en los que el análisis del peor de los casos tiene sentido. Por ejemplo, cuando desarrolla una biblioteca de subrutinas de propósito general y no sabe en qué dominios de aplicación serán útiles: no puede anticipar todos los casos de cuándo y por qué alguien querrá calcular una coincidencia bipartita de costo mínimo, por ejemplo. Las configuraciones adversas, como la criptografía, son aún más claras (sin embargo, en la criptografía le gustaría saber las constantes cuando se trata de parámetros de seguridad).

Sasho Nikolov

Los límites inferiores y el análisis del peor de los casos no suelen ir de la mano. No dice que un algoritmo tomará al menos tiempo exponencial en el peor de los casos, por lo tanto, es malo. Dices que puede llevar más tiempo lineal en el peor de los casos y, por lo tanto, es bueno. El primero solo es útil si va a ejecutar su algoritmo en todas las entradas posibles, y no simplemente en una entrada promedio.

Si desea utilizar límites inferiores para demostrar la maldad, entonces desea un análisis del mejor caso o un análisis de caso promedio. Puede simplificar las cosas confiando en el punto de @ PeterShor de que lo peor y el promedio son a menudo muy similares, y proporciona una lista exhaustiva de algoritmos para los que esto es cierto. (Ej: todos los tipos clásicos además de quicksort).

En cuanto a demostrar que las asintóticas son importantes cuando se comparan con entradas constantes y factores constantes, mi artículo favorito sobre el tema es "Perlas de programación: técnicas de diseño de algoritmos" de Jon Bentley. Presenta cuatro soluciones diferentes para un problema de matriz simple y demuestra cómo el enfoque lineal aniquila al cúbico. Él llama a su mesa "La tiranía de las asíntotas", después del término utilizado por los físicos para la intratabilidad de la ecuación del cohete. Utilizo este ejemplo para motivar la búsqueda de mejores algoritmos para estudiantes preuniversitarios.

¿Un científico que no sea informático leerá un artículo que contiene código y sabrá omitir los detalles de bajo nivel para obtener una visión general? No lo sé. Quizás haya una mejor presentación en otro lado. Pero creo que este es un recurso decente para citar.

Y si argumentan que no les importa la n arbitrariamente grande, haga que ejecuten Fibonacci recursiva no memorizada en 3 * 10 ⁹ pares de bases, y dígales que es O (1) ya que el tamaño de la secuencia de ADN es fijo. ;)

Brandjon
fuente

Me gusta el ejemplo de Fibonacci :)

Suresh Venkat

Re: su primer párrafo: en realidad, eso es casi exactamente lo que hace mucha teoría de la complejidad. Si un problema es EXP-complete, eso significa que requiere tiempo exponencial en las entradas del peor de los casos. Esto generalmente se toma como una indicación de su dificultad general (que, para ser justos, en la práctica a menudo no es tan malo como un indicador general). Este es el estándar de facto, llamado límite "infinitamente frecuente" o io inferior; Conseguir límites inferiores en el caso promedio o casi en todas partes (es decir, para todas menos muchas entradas) es un objetivo a veces perseguido, pero a menudo fuera del alcance en comparación con los límites inferiores.

Joshua Grochow

Permítanme señalar que no solo puede dar una larga lista de algoritmos para los que el análisis del caso más desfavorable y el caso promedio son los mismos, sino que también puede dar numerosos ejemplos en los que son muy diferentes (el algoritmo simplex es el más famoso de estos). Realmente necesita argumentar de alguna manera que son iguales para su aplicación particular; Las pruebas experimentales son una buena manera de hacer esto.

Peter Shor

@JoshuaGrochow Bastante justo. ¿Qué tal si revisamos el enunciado de la siguiente manera? Los límites inferiores en los peores casos son importantes cuando se quiere demostrar la ausencia de una garantía matemática de no horror. ;)

brandjon

-3

Estuvo de acuerdo en que este es un tema importante para la encuesta / cobertura, pero parece que todavía no ha sido mucho. algunas referencias de estilo / cobertura / audiencia / formalidad diferentes, no exactamente como se solicitó, pero algo cercanas (mejor visto en línea hasta ahora en búsqueda media, espero escuchar más sobre mejores; más notas a continuación):

La complejidad de los algoritmos Atkinson (por desgracia, solo una referencia a la biología en el documento, pero puede ser suficiente en términos más generales de ciencia / ingeniería)

La teoría moderna de los algoritmos data de finales de la década de 1960 cuando comenzó a usarse el método de medición del tiempo de ejecución asintótico. Se argumenta que el sujeto tiene tanto un ala de ingeniería como científica. El ala de ingeniería consta de metodologías de diseño bien entendidas, mientras que el ala científica se ocupa de los fundamentos teóricos. Se analizan los temas clave de ambas alas. Finalmente, se ofrecen algunas opiniones personales sobre dónde irá el tema a continuación.
Complejidad y algoritmos J. Díaz. 100 diapositivas ancho; uno podría extraer los relevantes en particular.
Una suave introducción al algoritmo de análisis de complejidad Dionysis "dionyziz" Zindros

en otras palabras, ¿hay algún tipo de introducción / encuesta / visión general de la lente teórica de la complejidad en combinación / conjunción / acompañante con la lente algorítmica avanzada en ciencia, algo así como "Teoría de la complejidad para científicos, ingenieros e investigadores" ?

hay buenas referencias en la "lente algorítmica" anterior que ha citado, por ejemplo, Papadimitriou, pero no parece una referencia muy satisfactoria por parte de un experto en el campo que se ha escrito en la última "lente de complejidad" ... aún (tal vez alguna "élite" " miembro de este sitio lo considerará como su próximo libro o proyecto en papel).

Tenga en cuenta también que hay muchas referencias sobre la relevancia P vs NP fuera de la teoría de la complejidad y en otros campos científicos que podrían usarse de alguna manera para este propósito. los agregará en los comentarios si hay algún interés.

vzn
fuente

No creo que esto realmente responda la pregunta.

Huck Bennett

eh eh, ¿miraste a alguno de los árbitros? parte mi respuesta es que no hay (todavía) ninguna respuesta ideal / perfecta: |

vzn

Parecen definir el análisis asintótico y el peor de los casos en lugar de centrarse en justificarlo, pero ¿tal vez me perdí algo?

Huck Bennett el

En realidad, creo que los investigadores fuera de TCS podrían fácilmente descartar el peor de los casos como "ejemplos construidos artificialmente que nunca ocurrirían en la práctica" y estarían (sin una fuerte convicción de lo contrario) mucho más interesados en el caso promedio (a pesar de que no está claro que el caso promedio es mucho más cercano a las instancias del mundo real).

Joshua Grochow

@vzn: Asintótico (por ejemplo, big-Oh) y el peor de los casos son algo ortogonales. Se puede hacer un análisis asintótico del peor de los casos, un análisis asintótico del caso promedio o incluso un análisis asintótico del caso más fácil (aunque admito que este último parece algo perverso). En cambio, se podría hacer un análisis exacto del peor de los casos, o un análisis exacto del caso promedio, y así sucesivamente, aunque estos serían mucho más dependientes del modelo y menos robustos. Justificar el uso de asintóticos (y esconder cosas como factores constantes) es completamente distinto de justificar el caso más desfavorable frente al caso promedio o al caso "real" (lo que sea que esto último signifique ...).

Joshua Grochow