¿Cuándo la aleatorización acelera los algoritmos y "no debería"?

39

La prueba de Adleman de que está contenido en muestra que si hay un algoritmo aleatorio para un problema que se ejecuta en el tiempo en entradas de tamaño , entonces también hay un algoritmo determinista para el problema que se ejecuta en el tiempo en entradas de tamaño [el algoritmo ejecuta el algoritmo aleatorio en cadenas de aleatoriedad independientes . Debe haber aleatoriedad para el algoritmo repetido que es bueno para todosP / p o l y t ( n ) n Θ ( t ( n ) n ) n Θ ( n ) 2 nBPPP/polyt(n)nΘ(t(n)n)nΘ(n)2nposibles entradas]. El algoritmo determinista no es uniforme; puede comportarse de manera diferente para diferentes tamaños de entrada. Entonces, el argumento de Adleman muestra que, si a uno no le importa la uniformidad, la aleatorización solo puede acelerar los algoritmos por un factor que es lineal en el tamaño de entrada.

¿Cuáles son algunos ejemplos concretos donde la aleatorización acelera la computación (según nuestro conocimiento)?

Un ejemplo es la prueba de identidad polinómica. Aquí la entrada es un circuito aritmético de tamaño n que computa un polinomio de variante m sobre un campo, y la tarea es averiguar si el polinomio es idénticamente cero. Un algoritmo aleatorio puede evaluar el polinomio en un punto aleatorio, mientras que el mejor algoritmo determinista que conocemos (y posiblemente el mejor que existe) evalúa el polinomio en muchos puntos.

Otro ejemplo es el árbol de expansión mínimo, donde el mejor algoritmo aleatorio de Karger-Klein-Tarjan es el tiempo lineal (¡y la probabilidad de error es exponencialmente pequeña!), Mientras que el mejor algoritmo determinista de Chazelle se ejecuta en el tiempo ( es la función inversa de Ackermann, por lo que la aceleración de la aleatorización es realmente pequeña). Curiosamente, Pettie y Ramachandran demostraron que si hay un algoritmo de tiempo lineal determinista no uniforme para un árbol de expansión mínimo, entonces también existe un algoritmo de tiempo lineal determinista uniforme.αO(mα(m,n))α

¿Cuáles son algunos otros ejemplos? ¿Qué ejemplos sabe donde la aceleración de la aleatorización es grande, pero esto es posiblemente solo porque todavía no hemos encontrado algoritmos deterministas suficientemente eficientes?

Dana Moshkovitz
fuente
55
Estrechamente relacionado: Problemas en BPP que no se sabe que están en P
usul
Siempre puede convertir cualquier algoritmo aleatorio en un algoritmo determinista, reemplazando el generador aleatorio con un generador pseudoaleatorio de calidad criptográfica. Bajo supuestos criptográficos plausibles que, según nuestro conocimiento, son válidos, esto funciona bien. Por lo tanto, mi respuesta sería: "según nuestro conocimiento, la respuesta es: no existen tales problemas en el mundo real". (En otras palabras, según nuestro conocimiento, la brecha en el tiempo de ejecución refleja nuestra incapacidad para probar límites de tiempo de ejecución ajustados en lugar de cualquier diferencia subyacente real.)
DW
1
Bajo suposiciones de dureza razonables, puede alimentar la aleatoriedad del algoritmo desde un generador pseudoaleatorio, sin embargo, para obtener un algoritmo determinista, debe ejecutar el algoritmo en todas las semillas posibles. Esto explota el tiempo de ejecución!
Dana Moshkovitz
Además del punto de Dana, creo que para desrandomizar BPP, el PRG necesita ejecutarse en más tiempo que el algoritmo original (aunque no sé cuál debe ser la brecha). Además, esto podría ilustrar una brecha (¿fundamental?) Entre certeza y confianza exponencialmente alta: es suficiente repetir un algoritmo aleatorio veces (para cualquier constante ) para obtener la probabilidad de corrección , pero La versión determinista necesita verificar todas las semillas polinomialmente. c 2 - O ( c )cc2O(c)
usul
@DanaMoshkovitz, depende de si abordas esto desde una perspectiva teórica o una perspectiva profesional. Desde la perspectiva de un profesional, no, no necesita hacer eso. Vea la construcción que describo en cs.stackexchange.com/a/41723/755 , que ejecuta el algoritmo solo en semillas . Según el modelo de oráculo aleatorio, se puede demostrar que no hay un aumento en el tiempo de ejecución asintótico y que ningún adversario limitado computacionalmente podrá encontrar ninguna entrada al algoritmo donde el algoritmo produce la respuesta incorrecta. Esto es probablemente lo suficientemente bueno para todos los fines prácticos. O(1)
DW

Respuestas:

28

No sé si la aleatorización "debería" o "no debería" ayudar, sin embargo, la prueba de primalidad de enteros se puede hacer a tiempo usando Miller – Rabin aleatorizado, mientras que, hasta donde yo sé, el Los algoritmos deterministas más conocidos son suponiendo GRH (determinista Miller – Rabin) o incondicionalmente (variantes de AKS). ˜ O (n4) ˜ O (n6)O~(n2)O~(n4)O~(n6)

Emil Jeřábek apoya a Monica
fuente
Aunque hay razones para creer que el testigo de composición más pequeño para es del orden , lo que daría un algoritmo . Pero esto sigue sin probarse incluso bajo conjeturas teóricas numéricas estándar como variantes de RH. log N log log N ˜ O ( n 3 )NlogNloglogNO~(n3)
Emil Jeřábek apoya a Monica el
Un problema similar es la prueba de irreductibilidad polinómica sobre campos finitos, donde nuevamente el algoritmo determinista conocido tiene peores límites que los algoritmos aleatorios, pero no recuerdo los detalles.
Emil Jeřábek apoya a Monica el
19

Un viejo ejemplo es el cálculo de volumen. Dado un politopo descrito por un oráculo de membresía, hay un algoritmo aleatorio que se ejecuta en tiempo polinómico para estimar su volumen a un factor , pero ningún algoritmo determinista puede acercarse incluso incondicionalmente .1+ϵ

El primer ejemplo de dicha estrategia aleatoria fue Dyer, Frieze y Kannan, y el resultado de dureza para algoritmos deterministas es Bárány y Füredi. Alistair Sinclair tiene buenas notas de lectura sobre esto .

No estoy seguro de entender completamente la parte "y no debería" de la pregunta, así que no estoy seguro de que esto se ajuste a la factura.

Suresh Venkat
fuente
1
Conocía el método MCMC pero no este límite inferior, y estoy bastante sorprendido (pensé que todo lo que se sabía era la dureza # P). El documento es "Calcular el volumen es difícil", accesible desde la página web de Füredi , y dan un límite inferior de esencialmente sobre qué tan bien se puede aproximar el volumen. [n/logn]n
Jeremy Kun
9

No sé si esto responde a su pregunta (o al menos parte de ella). Pero para los ejemplos del mundo real donde la aleatorización puede proporcionar una aceleración está en los problemas de optimización y la relación con el teorema de No Free Lunch ( NFL ) .

Hay un documento "Quizás no un almuerzo gratis, sino al menos un aperitivo gratis" donde se demuestra que el uso de la asignación al azar, los algoritmos (de optimización) pueden tener un mejor rendimiento.

Abstracto:

A menudo se afirma que los Algoritmos Evolutivos son superiores a otras técnicas de optimización, en particular, en situaciones en las que no se sabe mucho acerca de la función objetivo a optimizar. En contraste con eso, Wolpert y Macready (1997) demostraron que todas las técnicas de optimización tienen el mismo comportamiento --- en promedio sobre todos donde e son conjuntos finitos. Este resultado se llama [el] Teorema de no almuerzo gratis. Aquí se presentan diferentes escenarios de optimización. Se argumenta por qué el escenario en el que se basa el Teorema de No Free Lunch no modela la optimización de la vida real. Para escenarios más realistas se argumenta por qué las técnicas de optimización difieren en su eficiencia. Para un pequeño ejemplo, esta afirmación está probada.X Yf:XYXY

Referencias

  1. No hay teoremas de almuerzo gratis para la optimización ( teorema original de la NFL para la optimización)
  2. Quizás no sea un almuerzo gratis sino al menos un aperitivo gratis
  3. La duración sin descripción y sin almuerzo (muestra que los resultados de la NFL se mantienen para cualquier subconjunto del conjunto de todas las funciones posibles si se cierra bajo permutación, taza )FFF
  4. En las clases de funciones para las que se mantienen los resultados de No Free Lunch (está comprobado que la fracción de subconjuntos que son taza es insignificantemente pequeña)
  5. Dos clases amplias de funciones para las cuales no se cumple el resultado de no almuerzo gratis (muestra que un resultado NFL no se aplica a un conjunto de funciones cuando la longitud de la descripción de las funciones está suficientemente limitada)
  6. Los almuerzos continuos son gratuitos más el diseño de algoritmos de optimización óptimos (muestra que para dominios continuos, [la versión oficial de] NFL no se cumple. Este teorema del almuerzo gratis se basa en la formalización del concepto de funciones aleatorias de acondicionamiento físico mediante campos aleatorios )
  7. Más allá de No Free Lunch: Algoritmos realistas para clases de problemas arbitrarios (muestra que "... [todas] las violaciones de los teoremas de No Free Lunch se pueden expresar como distribuciones no uniformes en bloque sobre subconjuntos de problemas que son taza ")
  8. Algoritmos metaheurísticos basados ​​en enjambres y teoremas sin almuerzo gratuito ("[..t] por lo tanto, los resultados de las iteraciones ordenadas por tiempo que no vuelven a visitarse pueden no ser ciertas para los casos de revisión de casos, porque las iteraciones de revisión rompen una suposición importante de taza requerida para probar los teoremas de la NFL (Marshall y Hinton, 2010) ")
  9. Sin almuerzo gratis y aleatoriedad algorítmica
  10. No Free Lunch and Benchmarks (un enfoque teórico de conjuntos se generaliza a criterios no específicos de la taza , pero aún señala que los algoritmos aleatorios (no triviales) pueden superar a los algoritmos deterministas en promedio, "[..] se ha demostrado que la probabilidad es inadecuada para afirmar resultados no restringidos de la NFL en el caso general. [...] este artículo abandona la probabilidad, prefiriendo un marco teórico de conjuntos que obvie las limitaciones de la medida teórica al prescindir por completo de la probabilidad ")

Resumen sobre almuerzos gratuitos (y almuerzos gratis) por David H. Wolpert, ¿Cuánto cuesta la cena? ( tenga en cuenta que los teoremas de tipo NFL nunca especifican un " precio " real debido a su tipo de prueba)

Específicamente para la optimización generalizada (GO):

  1. Dos espacios y . Por ejemplo, son entradas, son distribuciones sobre salidas.Z X ZXZXZ

  2. Función Fitnessf:XZ

  3. m (quizás repetido) puntos muestreados de : donde , cada una función (quizás estocástica) def

    dm={dm(1),dm(2),...,dm(m)}
    t
    dm(t)={dmX(t),dmZ(t)}
    dmZ(t)f[dmX(t)]
  4. Algoritmo de búsquedaa={dtdmX(t):t=0..m}

  5. Función de coste euclidiana con valor vectorialC(f,dm)

  6. Para capturar un tipo particular de problema de optimización, gran parte de la estructura del problema se expresa enC(.,.)

Los teoremas de la NFL dependen fundamentalmente de que sea ​​independiente de . Si depende de , pueden ser posibles almuerzos gratis. Por ejemplo, tener independiente de , a menos que .f C f C ( f , d m ) f = f CfCfC(f,dm)f=f

Finalmente, una observación simple (y no tan simple) de por qué la aleatorización (de una forma u otra) puede proporcionar un rendimiento superior sobre algoritmos estrictamente deterministas.

  1. En el contexto de la optimización (aunque no está restringido en esto), un procedimiento de búsqueda aleatoria puede, en promedio, escapar de los extremos locales mejor que la búsqueda determinista y alcanzar los extremos globales.
  2. Existe una relación interesante (pero no simple a primera vista) entre el orden, la cardinalidad y la aleatorización de un conjunto (en el sentido general). El powerset de un conjunto (y su cardinalidad), depende intrinsicaly en un cierto (staticaly) ordenamiento fijo del conjunto (elementos de) . Suponiendo que el orden en (elementos de) no está (estadísticamente) fijo (la aleatorización puede ingresar aquí, en forma de orden aleatorio), el conjunto puede ser capaz de representar su propio conjunto de poderes (si ayuda a considerarlo como un tipo del análogo cuántico de un conjunto clásico, donde el ordenamiento dinámico juega un papel que explica un tipo de principio de superposición ). A A A A2AAAAA
Nikos M.
fuente
1

El mejor ejemplo es en el área considerada actualmente como los mejores candidatos para OWF, donde parece que cada OWF popular que se prepara sorprendentemente tiene un algoritmo sub-exponencial aleatorio, mientras que no existe un algoritmo sub-exponencial determinista (tome la factorización entera por ejemplo). De hecho, en muchos casos, probablemente exista un algoritmo eficiente dado algunas cadenas de consejos (criptoanálisis).

T ....
fuente
-5

Si tiene un algoritmo que usa la asignación al azar, siempre puede reemplazarlo con un algoritmo determinista que usa números pseudoaleatorios: tome la descripción del problema, calcule un código hash, use ese código hash como la semilla de un buen generador de números pseudoaleatorios . En la práctica, eso es lo que probablemente sucederá cuando alguien implemente un algoritmo utilizando la asignación al azar.

Si omitimos el código hash, la diferencia entre este algoritmo y un algoritmo que utiliza la asignación al azar verdadera es que puedo predecir la secuencia de números aleatorios generados, y podría producir un problema de tal manera que el número aleatorio predicho aplicado a mi problema siempre tomar la peor decisión posible Por ejemplo, para Quicksort con un pivote pseudoaleatorio, podría construir una matriz de entrada donde el pivote pseudoaleatorio siempre encuentre el mayor valor posible en la matriz. Con una verdadera aleatoriedad que no es posible.

Con el código hash, sería muy difícil para mí construir un problema donde los números pseudoaleatorios producen peores resultados. Todavía puedo predecir los números aleatorios, pero si cambio el problema, la secuencia de números pseudoaleatorios cambia completamente. Aún así, sería casi imposible para ti demostrar que no puedo construir tal problema.

gnasher729
fuente
Soy nuevo en cstheory.SE. Entonces, downvoters: ¿qué tiene de malo esta respuesta?
galdre
3
Dos cosas están mal: (1) no sabemos cómo construir números pseudoaleatorios en general, (2) incluso si sabemos cómo construirlos, son computacionalmente caros. No se garantiza que los números pseudoaleatorios utilizados en la práctica funcionen en teoría; todo lo que sabemos es que parecen funcionar empíricamente. (De hecho, la mayoría de los PRNG realmente en uso pueden romperse, por lo que en realidad no son seguros para su uso en general, solo cuando no está tratando específicamente de romperlos.)
Yuval Filmus
2
cstheory.se trata de la informática teórica *, no de la práctica de la programación. Nos guste o no, las dos áreas están bastante separadas.
Yuval Filmus
2
@YuvalFilmus: El generador de pasos alternos inventado por C. Gunther en 1987 todavía no se ha roto (aún no hay una ruptura pública, y dudo que la NSA lo haya roto tampoco). Veintiocho años es mucho tiempo para permanecer ininterrumpido, me sorprende que un generador tan simple (tres puertas LFSR y una puerta XOR, ¿qué tan simple sea eso?) Aún no se ha roto y no se usa con más frecuencia.
William Hird
2
@WilliamHird: Dependiendo de una definición de "roto", parece haberse roto realmente (más o menos en un grado similar al de la familia A5 / x relacionada, más eficiente y ampliamente utilizada). Ver crypto.stackexchange.com/a/342 .
Emil Jeřábek apoya a Monica el