Teóricos de la complejidad computacional han descubierto una nueva y sorprendente forma de comprender qué hace difíciles ciertos problemas.

Un artículo de Lakshmi Chandrasekaran. Historia original reimpresa con permiso de Quanta Magazine, una publicación editorialmente independiente respaldada por la Fundación Simons.

Los informáticos teóricos se ocupan de ideas complicadas. Pero siempre que sea posible, preferirán trabajar con otras más simples. Una herramienta de 2009 conocida como lema de la regularidad les ofrece una excelente manera de hacerlo. De hecho, les permite dividir un problema o función computacional determinado en partes más simples.

Para los teóricos de la complejidad computacional, que estudian la dificultad relativa de diferentes problemas, esta capacidad de simplificar les ha ayudado durante mucho tiempo a comprender funciones matemáticas difíciles de manejar. Pero ciertos problemas con partes complejas todavía desafían el análisis.

Ahora, un nuevo trabajo proporciona una manera de analizar esos problemas difíciles de entender. El avance proviene de un área inesperada de la informática: la equidad algorítmica, donde algoritmos como los utilizados por bancos y compañías de seguros se examinan para asegurar que tratan a las personas de manera justa. Los nuevos resultados muestran que las herramientas de equidad pueden mapear efectivamente las diferentes partes de un problema difícil y aislar las regiones precisas del problema que dificultan su solución.

“Es realmente un trabajo fantástico. Creo que es muy emocionante”, afirma Michael Kim, científico informático de la Universidad de Cornell que ayudó a crear una de las herramientas de equidad que se ha reutilizado en el nuevo trabajo. «Como teórico que trabaja en estos espacios, es un resultado ideal que alguien tome tu trabajo de un área y lo aplique a otra».

Pronósticos de precisión

A medida que las instituciones se sienten más cómodas usando algoritmos para decidir quién obtiene un préstamo bancario, por ejemplo, o quién debe recibir libertad condicional, se ha vuelto más importante tener una manera formal de verificar que los prejuicios humanos no se están infiltrando en los cálculos. Pero hay más de una forma de medir lo que es justo.

Comencemos con el problema general de medir la precisión de una predicción. Digamos que se te ocurre un programa de ordenador que predice si va a llover en tu ciudad y quieres medir su precisión. Digamos también que tiende a llover alrededor del 40% de los días del año. Si utilizas una herramienta de equidad llamada multiprecisión, tu algoritmo podría considerarse preciso si realiza una predicción promedio cercana al 40%. Esto podría lograrse si el algoritmo predice un 40% de probabilidad de lluvia todos los días del año, o si predice un 100% de lluvia solo el 40% de los días (ya que el promedio sería el mismo). Sin embargo, si le pides que sea más específico: ¿lloverá el martes? – y el mismo algoritmo puede no ser preciso.

Consideremos ahora un algoritmo que predice si es probable que los solicitantes de préstamos realicen todos sus pagos. No es suficiente tener un algoritmo que prediga la tasa general correcta: el 40% de probabilidad de lluvia en nuestro ejemplo anterior. Necesita predecir la tasa de individuos específicos en diferentes grupos de población de una manera que sea tan precisa como justa.

Las predicciones precisas generalmente disminuyen a medida que se agregan capas de complejidad, como una fecha específica para el pronóstico del tiempo o una persona específica que solicita un préstamo. Las situaciones de la vida real rápidamente se vuelven demasiado complejas para que la precisión múltiple sea la mejor forma de medirlas.

En 2018, Kim y otros investigadores en equidad idearon un paradigma de equidad nuevo y más sólido llamado multicalibración, que tiene en cuenta estos niveles de complejidades. Este enfoque impone predicciones “calibradas”; básicamente, cada capa de complicación se tiene en cuenta en el sistema. La multicalibración significa que las predicciones de un algoritmo son precisas, ya sea que se miren todos los días o solo el martes. O si estás haciendo predicciones de préstamos para todas las personas o solo para ciertos tipos de personas. La multicalibración debería garantizar la equidad en todos los ámbitos.

Pero su utilidad no termina aquí.

Más allá de la equidad

El año pasado un equipo de informáticos teóricos vio la oportunidad de llevar estas herramientas a un campo diferente. Mostraron cómo la multiprecisión y la multicalibración eran equivalentes a los teoremas existentes en la teoría de grafos, una disciplina matemática que estudia las relaciones entre objetos. Esto hizo que Salil Vadhan, un científico informático de la Universidad de Harvard, se preguntara dónde más podría ser útil la herramienta.

«Vimos que estaban obteniendo resultados [usando] la multicalibración en teoría de grafos», cuenta Vadhan, uno de los autores del lema de la regularidad de 2009, así como del trabajo más reciente. «Ahora intentemos hacerlo también con la teoría de la complejidad». Formó equipo con su colega de Harvard Cynthia Dwork, quien también fue una de las autoras del artículo sobre teoría de grafos, y su estudiante de grado Sílvia Casacuberta (que ahora es estudiante de posgrado en la Universidad de Oxford).

El trío terminó estableciendo una especie de diccionario que traducía entre herramientas de equidad e ideas en la teoría de la complejidad. Demostraron que cualquier población (ya sean días por pronosticar o solicitantes en espera de préstamos) podría traducirse en un panorama de posibles entradas para un problema computacional.

Una vez establecidas las conexiones, los investigadores demostraron que la multiprecisión, la herramienta de equidad más débil, es equivalente al lema de la regularidad: una función simple, como la predicción promedio de las precipitaciones, puede aproximarse a una compleja, como el promedio verdadero (calculado usando la ocurrencia real de lluvia). «La conexión con la multiprecisión y la regularidad es solo un cambio de terminología», afirma Vadean.

Después de demostrar esto, los investigadores naturalmente se preguntaron si la multicalibración, la herramienta de equidad más poderosa, podría aplicarse para demostrar algo más sólido. Se podía: descubrieron que la capacidad de un algoritmo de equidad para mantener predicciones precisas dentro de subpoblaciones podría aplicarse para fortalecer otro lema, conocido como el lema fundamental de Impagliazzo. El lema nos ayuda a comprender la estructura de un problema difícil, observando todas sus posibles entradas (inputs) y preguntándonos cuáles serían las más difíciles de resolver.

Para imaginar un problema que solo es difícil con ciertos inputs, volvamos a la lluvia. Consideremos una región con una estación lluviosa, en la que llueve casi todos los días, y una estación seca, en la que casi nunca llueve. Gracias a esto, podemos predecir correctamente si lloverá el 90% del tiempo. El 10% restante (presumiblemente días en el límite entre las dos estaciones, en los que la lluvia y los cielos despejados son igualmente probables) son inputs difíciles. Las predicciones para esos días no pueden ser mucho mejores que las conjeturas aleatorias.

«¿Qué inputs de un problema computacional [descrito por una función difícil] son más fáciles y cuáles son más difíciles?» se preguntó el fallecido Luca Trevisan, científico informático teórico de la Universidad Bocconi en Italia y uno de los autores del lema de la regularidad de 2009. Impagliazzo demostró que, para cualquier problema difícil, siempre hay un conjunto común de puntos difíciles que son difíciles para cualquier algoritmo eficiente.

Los autores del nuevo trabajo han demostrado que la aplicación de los estrictos requisitos de la multicalibración mejoran el lema, generalizándolo para aplicarlo a más problemas. Los intentos anteriores de identificar los inputs concretos de un problema, en lugar de simplemente demostrar que existen, implicaban dividir los inputs en fragmentos más pequeños y buscar una función de aproximación que siguiera funcionando. Finalmente, después de suficientes divisiones, era posible identificar los inputs que no podían aproximarse. El único problema era que la división daba como resultado un número exponencial de fragmentos a procesar, por lo que el enfoque no era factible. Pero al aplicar la multicalibración, los investigadores han podido reducir el número total de divisiones, simplificando así el enfoque para aproximar la función difícil.

«Me gusta mucho su resultado», comenta Huijia (Rachel) Lin, científica informática teórica de la Universidad de Washington y una de las autoras del artículo sobre teoría de grafos del año pasado. «Realmente se trata de volver al clásico [lema fundamental] y darle un nuevo giro».

«Es realmente genial ver que tenemos este enfoque de predicción inspirado en la complejidad que ha promovido nuevas ideas chulas en equidad, [y] es guay verlas volver a la complejidad y cerrar el círculo», comenta Kim. «Creo que tienes esperanza en [que] este tipo de cosas [ocurran]».

El artículo original, The Question of What’s Fair Illuminates the Question of What’s Hard, se publicó el 24 de junio de 2024 en Quanta Magazine.

Traducido por César Tomé López