Análisis suavizado

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 cantidad de investigaciones, para problemas que abarcan desde programación matemática , análisis numérico , aprendizaje automático y minería de datos . ^[1] Puede brindar un análisis más realista del desempeño práctico (por ejemplo, tiempo de ejecución, tasa de éxito, calidad de aproximación) del algoritmo en comparación con el análisis que utiliza escenarios de peor caso o de caso promedio.

El análisis suavizado es un híbrido entre el análisis del peor de los casos y el análisis 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 sólidos, que indican aproximadamente que, en cada vecindario suficientemente grande del espacio de entradas, la mayoría de las entradas son fácilmente solucionables. Por lo 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 del 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 de resolver un programa lineal utilizando el algoritmo símplex es exponencial, ^[2] aunque el número observado de pasos en la práctica es aproximadamente lineal. ^{[3] [4]} El algoritmo símplex es de hecho mucho más rápido que el método del elipsoide en la práctica, aunque este último tiene una complejidad del peor de los casos de tiempo polinomial .

El análisis de casos promedio se introdujo por primera vez para superar las limitaciones del análisis de casos peores. Sin embargo, la complejidad resultante de los casos promedio depende en gran medida de la distribución de probabilidad que se elija sobre la entrada. Las entradas reales y la distribución de las entradas pueden ser diferentes en la práctica de las suposiciones realizadas durante el análisis: una entrada aleatoria puede ser muy diferente de una entrada típica. Debido a esta elección del modelo de datos, un resultado teórico de caso promedio podría decir poco sobre el rendimiento 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 ventajas de ambos. Su objetivo es ser mucho más general que la complejidad del caso promedio, pero al mismo tiempo permite demostrar límites de complejidad bajos.

La 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 el análisis suavizado. El nombre Análisis Suavizado fue acuñado por Alan Edelman . ^[1] En 2010 Spielman recibió el Premio Nevanlinna por desarrollar el análisis suavizado. El artículo JACM de Spielman y Teng "Análisis suavizado de algoritmos: por qué el algoritmo simplex suele tardar un tiempo polinomial" 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 Americana (AMS).

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 que da el algoritmo es lineal en relación con 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 la mayoría de las reglas pivote analizadas con éxito. Esta fue una de las principales motivaciones para desarrollar el análisis suavizado. ^[5]

Para el modelo de perturbación, suponemos que los datos de entrada están perturbados por el ruido de una distribución gaussiana . Para fines de normalización, suponemos 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 . Establecemos . 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} }})}$${\estilo de visualización 0}$${\estilo de visualización \sigma}$${\displaystyle \mathbf {A} ={\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},\mathbf {b} ={\bar {\mathbf {b} }} +{\sombrero {\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 los 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 se cumple para una regla pivote específica llamada regla del vértice de sombra. La regla del vértice de sombra es más lenta que las reglas pivote más utilizadas, como la regla de Dantzig o la regla de la arista más empinada ^[7], pero tiene propiedades que la hacen muy adecuada para el análisis probabilístico. ^[8]

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 2-opt para el problema del viajante de comercio . Puede requerir 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 razón de aproximación , que es la razó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 darse por puntos en la caja , donde sus distancias por pares provienen de una norma . Ya en dos dimensiones, la heurística 2-opt podría tomar 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 independientemente de acuerdo con distribuciones de probabilidad con función de densidad de probabilidad . Para , los puntos se distribuyen uniformemente. Cuando es grande, el adversario tiene más capacidad para aumentar la probabilidad de instancias de problemas difíciles. En este modelo de perturbación, el número esperado de iteraciones de la heurística 2-opt, así como las razones de aproximación de la salida resultante, están limitadas 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 fue exitoso 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 es ampliamente utilizado y muy rápido en la práctica, aunque puede tomar iteraciones en el peor de los casos para encontrar una solución localmente óptima. Sin embargo, asumiendo 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 }$

• Complejidad de caso promedio
• Tiempo pseudo-polinomial
• Complejidad en el peor de los casos