Análisis suavizado

Un mapa de bits generado aleatoriamente no se parece a las imágenes típicas.

Una imagen típica no se parece a un mapa de bits aleatorio.

En informática teórica , el análisis suavizado es una forma de medir la complejidad de un algoritmo . Desde su introducción en 2001, el análisis suavizado se ha utilizado como base para una considerable investigación, para problemas que van desde la programación matemática , el análisis numérico , el aprendizaje automático y la minería de datos . ^[1] Puede ofrecer un análisis más realista del rendimiento práctico (por ejemplo, tiempo de ejecución, tasa de éxito, calidad de la aproximación) del algoritmo en comparación con el análisis que utiliza escenarios del peor de los casos o del caso promedio.

El análisis suavizado es un híbrido de análisis del peor de los casos y del caso promedio que hereda las ventajas de ambos. Mide el rendimiento esperado de los algoritmos bajo ligeras perturbaciones aleatorias de las entradas del peor de los casos. Si la complejidad suavizada de un algoritmo es baja, entonces es poco probable que el algoritmo tarde mucho tiempo en resolver casos prácticos cuyos datos están sujetos a ligeros ruidos e imprecisiones. Los resultados de complejidad suavizada son resultados probabilísticos fuertes, que establecen aproximadamente que, en cada vecindad suficientemente grande del espacio de entradas, la mayoría de las entradas son fácilmente solucionables. Por tanto, una complejidad suavizada baja significa que la dureza de las entradas es una propiedad "frágil".

Aunque la complejidad del peor de los casos ha sido ampliamente exitosa para explicar el desempeño práctico de muchos algoritmos, este estilo de análisis arroja resultados engañosos para una serie de problemas. La complejidad del peor de los casos mide el tiempo que lleva resolver cualquier entrada, aunque es posible que las entradas difíciles de resolver nunca surjan en la práctica. En tales casos, el tiempo de ejecución en el peor de los casos puede ser mucho peor que el tiempo de ejecución observado en la práctica. Por ejemplo, la complejidad del peor de los casos al resolver un programa lineal usando el algoritmo simplex es exponencial, ^[2] aunque el número de pasos observado en la práctica es aproximadamente lineal. ^{[3] [4]} El algoritmo simplex es de hecho mucho más rápido que el método del elipsoide en la práctica, aunque este último tiene una complejidad en el peor de los casos en tiempo polinomial .

El análisis del caso promedio se introdujo por primera vez para superar las limitaciones del análisis del peor de los casos. Sin embargo, la complejidad promedio resultante depende en gran medida de la distribución de probabilidad que se elija sobre la entrada. Los insumos reales y su distribución pueden ser diferentes en la práctica de los supuestos hechos durante el análisis: un insumo aleatorio puede ser muy diferente a un insumo típico. Debido a esta elección del modelo de datos, un resultado teórico de caso promedio podría decir poco sobre el desempeño práctico del algoritmo.

El análisis suavizado generaliza tanto el análisis del peor de los casos como el del caso promedio y hereda las fortalezas de ambos. Se pretende que sea mucho más general que la complejidad del caso promedio, al mismo tiempo que permite probar límites de baja complejidad.

Historia

ACM y la Asociación Europea de Informática Teórica otorgaron el Premio Gödel 2008 a Daniel Spielman y Shanghua Teng por desarrollar un análisis suavizado. El nombre Análisis Suavizado fue acuñado por Alan Edelman . ^[1] En 2010, Spielman recibió el Premio Nevanlinna por desarrollar un análisis suavizado. El artículo JACM de Spielman y Teng "Análisis suavizado de algoritmos: por qué el algoritmo simplex normalmente toma tiempo polinómico" también fue uno de los tres ganadores del Premio Fulkerson 2009 patrocinado conjuntamente por la Sociedad de Programación Matemática (MPS) y la Sociedad Matemática Estadounidense (AMS). .

Ejemplos

Algoritmo simplex para programación lineal.

El algoritmo simplex es un algoritmo muy eficiente en la práctica y es uno de los algoritmos dominantes para la programación lineal en la práctica. En problemas prácticos, el número de pasos dados por el algoritmo es lineal en el número de variables y restricciones. ^{[3] [4]} Sin embargo, en el peor de los casos teóricos, se necesitan exponencialmente muchos pasos para lograr reglas de pivote analizadas con mayor éxito. Esta fue una de las principales motivaciones para desarrollar un análisis suavizado. ^[5]

Para el modelo de perturbación, asumimos que los datos de entrada están perturbados por el ruido de una distribución gaussiana . Para fines de normalización, asumimos que los datos no perturbados satisfacen para todas las filas de la matriz. El ruido tiene entradas independientes muestreadas de una distribución gaussiana con media y desviación estándar . Establecimos . Los datos de entrada suavizados consisten en el programa lineal. ${\displaystyle {\bar {\mathbf {A} }}\in \mathbb {R} ^{n\times d},{\bar {\mathbf {b} }}\in \mathbb {R} ^{n},\mathbf {c} \in \mathbb {R} ^{d}}$ ${\displaystyle \|({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})\|_{2}\leq 1}$ ${\displaystyle ({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})}$ ${\displaystyle ({\bar {\mathbf {A} }},{\bar {\mathbf {b} }}).}$ ${\displaystyle ({\hat {\mathbf {A} }},{\hat {\mathbf {b} }})}$ ${\displaystyle 0}$ ${\displaystyle \sigma }$ ${\displaystyle \mathbf {A} ={\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},\mathbf {b} ={\bar {\mathbf {b} }}+{\hat {\mathbf {b} }}}$

maximizar

${\displaystyle \mathbf {c^{T}} \cdot \mathbf {x} }$

sujeto a

${\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} }$.

Si el tiempo de ejecución de nuestro algoritmo sobre datos está dado por entonces la complejidad suavizada del método simplex es ^[6] ${\displaystyle \mathbf {A} ,\mathbf {b} ,\mathbf {c} }$ ${\displaystyle T(\mathbf {A} ,\mathbf {b} ,\mathbf {c} )}$

${\displaystyle C_{s}(n,d,\sigma ):=\max _{{\bar {\mathbf {A} }},{\bar {\mathbf {b} }},\mathbf {c} }~\mathbb {E} _{{\hat {\mathbf {A} }},{\hat {\mathbf {b} }}}[T({\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},{\bar {\mathbf {b} }}+{\hat {\mathbf {b} }},\mathbf {c} )]={\rm {poly}}(d,\log n,\sigma ^{-1}).}$

Este límite es válido para una regla de pivote específica llamada regla del vértice de sombra. La regla del vértice de la sombra es más lenta que las reglas de pivote más utilizadas, como la regla de Dantzig o la regla del borde más pronunciado ^[7] , pero tiene propiedades que la hacen muy adecuada para el análisis probabilístico. ^[8]

Búsqueda local de optimización combinatoria.

Varios algoritmos de búsqueda local tienen malos tiempos de ejecución en el peor de los casos, pero funcionan bien en la práctica. ^[9]

Un ejemplo es la heurística de 2 opciones para el problema del viajante . Pueden ser necesarias exponencialmente muchas iteraciones hasta encontrar una solución localmente óptima, aunque en la práctica el tiempo de ejecución es subcuadrático en el número de vértices. ^[10] La relación de aproximación , que es la relación entre la longitud de la salida del algoritmo y la longitud de la solución óptima, tiende a ser buena en la práctica, pero también puede ser mala en el peor de los casos teóricos.

Una clase de instancias de problemas puede estar dada por puntos en el cuadro , donde sus distancias por pares provienen de una norma . Ya en dos dimensiones, la heurística de 2 opciones podría requerir exponencialmente muchas iteraciones hasta encontrar un óptimo local. En este contexto, se puede analizar el modelo de perturbación donde los vértices se muestrean de forma independiente según distribuciones de probabilidad con función de densidad de probabilidad . Para , los puntos están distribuidos uniformemente. Cuando es grande, el adversario tiene más capacidad para aumentar la probabilidad de que se produzcan casos de problemas difíciles. En este modelo de perturbación, el número esperado de iteraciones de la heurística de 2 opciones, así como los ratios de aproximación de la salida resultante, están limitados por funciones polinómicas de y . ^[10] ${\displaystyle n}$ ${\displaystyle [0,1]^{d}}$ ${\displaystyle v_{1},\dots ,v_{n}}$ ${\displaystyle f_{1},\dots ,f_{n}:[0,1]^{d}\rightarrow [0,\theta ]}$ ${\displaystyle \theta =1}$ ${\displaystyle \theta >1}$ ${\displaystyle n}$ ${\displaystyle \theta }$

Otro algoritmo de búsqueda local para el cual el análisis suavizado tuvo éxito es el método k-means . Dados los puntos en , es NP-difícil encontrar una buena partición en grupos con pequeñas distancias por pares entre puntos en el mismo grupo. El algoritmo de Lloyd se utiliza ampliamente y es muy rápido en la práctica, aunque en el peor de los casos puede ser necesario iterar para encontrar una solución localmente óptima. Sin embargo, suponiendo que los puntos tienen distribuciones gaussianas independientes , cada una con expectativa en y desviación estándar , el número esperado de iteraciones del algoritmo está limitado por un polinomio en , y . ^[11] ${\displaystyle n}$ ${\displaystyle [0,1]^{d}}$ ${\displaystyle e^{\Omega (n)}}$ ${\displaystyle [0,1]^{d}}$ ${\displaystyle \sigma }$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle \sigma }$

Ver también

• Complejidad de caso promedio
• Tiempo pseudopolinomial
• Complejidad en el peor de los casos

Referencias

1. Spielman, Daniel ; Teng, Shang-Hua (2009), "Análisis suavizado: un intento de explicar el comportamiento de los algoritmos en la práctica" (PDF) , Comunicaciones de la ACM , 52 (10), ACM: 76–84, doi :10.1145/1562764.1562785, S2CID  7904807
2. Amenta, Nina ; Ziegler, Günter (1999), "Productos deformados y sombras máximas de politopos", Matemáticas contemporáneas , 223 , Sociedad Matemática Estadounidense: 10–19, CiteSeerX 10.1.1.80.3241 , doi :10.1090/conm/223, ISBN  9780821806746, señor  1661377
3. Shamir, Ron (1987), "La eficiencia del método simplex: una encuesta", Management Science , 33 (3): 301–334, doi :10.1287/mnsc.33.3.301
4. Andrei, Neculai (2004), "Andrei, Neculai. "Sobre la complejidad del paquete MINOS para programación lineal", Estudios de Informática y Control , 13 (1): 35–46
5. Spielman, Daniel ; Teng, Shang-Hua (2001), "Análisis suavizado de algoritmos", Actas del trigésimo tercer simposio anual de ACM sobre teoría de la computación , ACM, págs. 296–305, arXiv : cs/0111050 , Bibcode : 2001cs... ....11050S, doi :10.1145/380752.380813, ISBN 978-1-58113-349-3, S2CID  1471{{citation}}: CS1 maint: date and year (link)
6. Dadush, Daniel; Huiberts, Sophie (2018), "Un análisis simplificado y amigable del método simplex", Actas del 50.º Simposio anual ACM SIGACT sobre teoría de la computación , págs. 390–403, arXiv : 1711.05667 , doi : 10.1145/3188745.3188826, ISBN 9781450355599, S2CID  11868079{{citation}}: CS1 maint: date and year (link)
7. Borgwardt, Karl-Heinz; Maldita sea, Renate; Dönig, Rudolf; Joas, Gabriele (1993), "Estudios empíricos sobre la eficiencia promedio de variantes simplex bajo simetría de rotación", ORSA Journal on Computing , 5 (3), Operations Research Society of America: 249–260, doi :10.1287/ijoc.5.3. 249
8. Borgwardt, Karl-Heinz (1987), El método simplex: análisis probabilístico, algoritmos y combinatoria, vol. 1, Springer-Verlag, doi :10.1007/978-3-642-61578-8, ISBN 978-3-540-17096-9
9. Manthey, Bodo (2021), Roughgarden, Tim (ed.), "Análisis suavizado de búsqueda local", Más allá del análisis de algoritmos en el peor de los casos , Cambridge: Cambridge University Press, págs. 285–308, doi :10.1017/9781108637435.018 , ISBN 978-1-108-49431-1, S2CID  221680879 , consultado el 15 de junio de 2022
10. Englert, Matías; Röglin, Heiko; Vöcking, Berthold (2007), "Peor caso y análisis probabilístico del algoritmo de 2 opciones para el TSP", Actas del decimoctavo simposio anual ACM-SIAM sobre algoritmos discretos , 68 : 190–264, arXiv : 2302.06889 , doi : 10.1007 /s00453-013-9801-4
11. Arturo, David; Manthey, Bodo; Röglin, Heiko (2011), "Análisis suavizado del método k-Means" (PDF) , Journal of the ACM , 58 (5): 1–31, doi :10.1145/2027216.2027217, S2CID  5253105