Two Dimensions Govern Agnostic Multiclass Transductive Learning

En el mundo del aprendizaje automático, las computadoras aprenden a realizar predicciones estudiando ejemplos. Imagine a un estudiante tratando de adivinar la respuesta a una pregunta de un examen. En la forma estándar de aprendizaje, llamada "aprendizaje PAC", el estudiante practica con un conjunto de tarjetas de estudio y luego realiza un examen con tarjetas nuevas y no vistas. El objetivo es desempeñarse bien en promedio sobre muchos exámenes posibles. Pero existe otra forma más específica de aprendizaje llamada "aprendizaje transductivo". Aquí, se le entrega al estudiante el examen completo por adelantado, incluyendo cada pregunta, pero la respuesta a solo una pregunta específica está oculta. El estudiante ve todas las demás respuestas y debe predecir la única etiqueta faltante. Esta configuración es más estricta porque el estudiante no puede confiar en el desempeño promedio; debe estar en lo cierto para ese conjunto específico y fijo de preguntas.

Para problemas simples con solo dos posibles respuestas, como "sí" o "no", los investigadores han sabido durante mucho tiempo que estas dos formas de aprendizaje son esencialmente las mismas en términos de cuánta información se necesita para tener éxito. Sin embargo, cuando las respuestas pueden ser una de muchas posibilidades —como identificar miles de especies diferentes de aves o diagnosticar cientos de enfermedades— las reglas cambian. En estas situaciones complejas de "multiclase", la dificultad del aprendizaje depende de dos medidas matemáticas diferentes de complejidad. Una medida, a menudo llamada dimensión DS, se relaciona con qué tan bien puede el aprendiz manejar situaciones donde existe una respuesta perfecta. La otra, la dimensión de Natarajan, se relaciona con cuánta incertidumbre queda cuando no hay una respuesta perfecta disponible. Durante años, fue una pregunta abierta si las reglas estrictas del "transductivo" obligarían al aprendiz a necesitar más datos de lo que requieren las reglas "PAC" estándar, especialmente cuando el número de posibles respuestas es enorme o incluso infinito.

Un investigador de la Universidad Johns Hopkins ha resuelto ahora esta cuestión, demostrando que, para problemas de multiclase, las reglas estrictas del transductivo no requieren en realidad más datos que las reglas estándar, salvo por ajustes muy pequeños. Demostró que la cantidad de información necesaria para aprender en este entorno estricto está gobernada por las mismas dos medidas de complejidad que controlan el entorno estándar. Su trabajo demuestra que, incluso cuando el aprendiz debe predecir una única etiqueta oculta a partir de un grupo fijo de ejemplos, puede lograr el mismo nivel de precisión que si estuviera aprendiendo de un flujo aleatorio de datos. Este hallazgo es significativo porque unifica dos modelos de aprendizaje diferentes, confirmando que los límites fundamentales del aprendizaje están determinados por la naturaleza del problema en sí, no por la forma específica en que se presenta la información.

Para llegar a esta conclusión, el investigador tuvo que superar un gran obstáculo. En el entorno transductivo estricto, un aprendiz no puede simplemente mirar todas las respuestas visibles y elegir la mejor regla, porque esto puede conducir a una especie de inestabilidad. Si un aprendiz intenta ajustar perfectamente los datos visibles, podría crear accidentalmente una regla que funcione para cada ejemplo visible pero que falle por completo en el elemento oculto. Esto es similar a un estudiante que memoriza las respuestas de cada pregunta de práctica pero reprueba el examen porque no entendió el patrón subyacente. El investigador encontró que, para evitar esta trampa, el aprendiz debe ignorar deliberadamente una parte de los datos visibles.

La solución que ideó involucra una estrategia de "reserva aleatoria". En lugar de usar todos los ejemplos visibles para construir una predicción, el aprendiz reserva aleatoriamente una gran parte de los datos visibles, tratándolos como si fueran el punto de prueba oculto. Al ignorar estas etiquetas reservadas, el aprendiz crea un bloque grande de datos no vistos que es estadísticamente independiente de la regla que construye. Esto le permite utilizar herramientas matemáticas poderosas que se basan en la idea de la generalización: predecir bien sobre datos que no fueron utilizados para construir el modelo. El aprendiz utiliza entonces un proceso de tres pasos para refinar su predicción. Primero, utiliza una pequeña muestra de los datos visibles para crear una lista finita de posibles reglas de predicción. Segundo, utiliza un sistema de votación ponderada para reducir la lista de posibles respuestas para cada pregunta, reduciendo efectivamente la complejidad del problema. Finalmente, utiliza el resto de los datos visibles para seleccionar la mejor regla de esa lista reducida.

Este enfoque se basa en una nueva visión matemática sobre cómo manejar datos que son muestreados sin reemplazo. En muchos escenarios de aprendizaje, se asume que los puntos de datos son independientes, como sacar una carta de un mazo y devolverla. Pero en el entorno transductivo, una vez que se ve un punto de dato, no puede volver a verse. El investigador demostró que, incluso con esta restricción, un tipo específico de sistema de votación ponderada sigue funcionando de manera efectiva. Mostró que los "expertos" o reglas en su sistema obtienen una cantidad predecible de "recompensas" basadas en qué tan bien cubren las partes no vistas de los datos. Esto asegura que el aprendiz no pierda precisión al pasar de los datos visibles a la predicción oculta.

El investigador también demostró que su resultado es el mejor posible mediante la construcción de ejemplos específicos donde el aprendizaje se vuelve difícil. Mostró que si el problema tiene un alto nivel de complejidad en el sentido de la "respuesta perfecta", la tasa de error será proporcional a esa complejidad dividida por el número de ejemplos. Si el problema tiene un alto nivel de incertidumbre en el sentido de "sin respuesta perfecta", la tasa de error será proporcional a la raíz cuadrada de esa complejidad dividida por el número de ejemplos. Ambos factores son necesarios; eliminar cualquiera de ellos haría que la tarea de aprendizaje fuera imposible en ciertos casos. Esto confirma que las dos dimensiones de complejidad identificadas en el aprendizaje estándar son, de hecho, las medidas correctas para el entorno transductivo estricto también.

Las implicaciones de este trabajo son que la brecha entre los dos modelos de aprendizaje se ha cerrado. Para cualquiera que diseñe algoritmos de aprendizaje para problemas complejos de multiclase, significa que los mismos límites teóricos se aplican ya sea que los datos se presenten como un flujo aleatorio o como un conjunto fijo con una respuesta oculta. El investigador no proporcionó un algoritmo específico que esté garantizado de ser rápido en una computadora, ya que su prueba se basa en la teoría de la información y no en la eficiencia computacional. Sin embargo, estableció que la barrera fundamental del aprendizaje es la misma en ambos mundajes. Al demostrar que un enfoque estructurado utilizando la reserva aleatoria y la compresión puede transferir el éxito del aprendizaje estándar al entorno transductivo estricto, han proporcionado una hoja de ruta clara para comprender los límites de la predicción en entornos complejos.

Este trabajo también aclara el papel de los diferentes tipos de complejidad en el aprendizaje. Muestra que la capacidad de aprender una regla perfecta y la capacidad de aprender una buena regla en presencia de ruido son desafíos distintos, cada uno de los cuales requiere una cantidad diferente de datos. El investigador demostró que estos desafíos no se combinan de una manera que haga que el entorno transductivo sea más difícil que el entorno estándar. En cambio, el aprendiz puede navegar por la población fija de datos mediante el hecho de ignorar estratégicamente partes de ella, convirtiendo un problema difícil e inestable en uno manejable. El resultado se mantiene incluso cuando el número de posibles respuestas es infinito, un escenario donde los métodos anteriores solían fallar.

Al final, el estudio confirma que las leyes que gobiernan cómo aprenden las máquinas son robustas. Ya sea que el aprendiz esté practicando con un conjunto aleatorio de ejemplos o resolviendo un rompecabezas específico con una pieza faltante, la cantidad de información requerida para tener éxito está determinada por la misma estructura subyacente del problema. El investigador ha demostrado que, al gestionar cuidadosamente cómo se usan los datos y al comprender las dimensiones específicas de complejidad involucradas, es posible lograr un desempeño óptimo en los entornos de aprendizaje más estrictos. Esto proporciona una base teórica sólida para futuros desarrollos en el aprendizaje automático, asegurando que, a medida que los algoritmos se vuelven más sofisticados, permanezcan fundamentados en una comprensión clara de lo que es posible.