Después de leer la pregunta, la descripción asociada con la pregunta y las dos respuestas anteriores, puedo decir con seguridad que la pregunta formulada es muy reflexiva, es una pregunta abierta y de gran interés en la investigación del aprendizaje automático, y necesita un comprensión de algunos aspectos centrales de la teoría del aprendizaje computacional incluso para comenzar a encontrar una respuesta. Entonces, muchas felicitaciones a Saumitra Mishra por hacerle esta pregunta a Quora en forma genérica.
Preferiría ir paso a paso para responder esta pregunta, dando una delineación bastante intuitiva en cada paso para mejorar la comprensión. Cualquier lector informado puede omitir las porciones elegidas.
Notación Big-Oh: podemos medir la eficiencia computacional de cualquier algoritmo dado (de cualquier tipo: probabilístico, determinista, iterativo, etc.) en términos del número de operaciones básicas que realiza en función de algún parámetro de entrada p.
En la literatura de complejidad computacional común, p es la longitud de entrada = n, es decir, el número de entradas. Las elecciones del parámetro de entrada p que debemos hacer dependen de algunas características de un algoritmo que discutiremos a medida que avancemos.
La notación Big-Oh simplemente caracteriza una función que limita el número máximo de operaciones básicas que realiza el algoritmo basado en p . Para hacer nuestro análisis invariable de lo que uno puede describir como operaciones básicas , la formulación matemática de la notación Big-Oh introduce una constante.
Para obtener más detalles, consulte la Teoría de la complejidad computacional: un enfoque moderno, de Sanjeev Arora y Boaz Barak, Cambridge University Press.
Algoritmos de aprendizaje automático versus algoritmos generales: en el aprendizaje automático, el objetivo de un algoritmo es aprender un conjunto de reglas que puedan describir los datos (un conjunto de entradas y salidas). Intuitivamente conocemos esas reglas como humanos, pero no las conocemos de manera precisa para poder describirlas matemáticamente con suficiente concreción. Esto contrasta el aprendizaje automático con los algoritmos informáticos tradicionales, así como con la IA convencional basada en reglas. Ahora, uno puede suponer en este punto, que esta diferencia también podría hacer que la noción de complejidad computacional para los algoritmos de aprendizaje automático sea diferente de lo que sabemos de otra manera.
Complejidad de la muestra: dado cualquier algoritmo de aprendizaje automático, tenemos un conjunto de capacitación (en términos más simples, un conjunto de entradas y etiquetas / salidas de verdad fundamental) donde cada muestra de entrada tiene alguna dimensión , y queremos lograr cierta precisión prevista, con cierta confianza , dado algún modelo (bosques aleatorios, redes profundas, SVM, etc.) al que nos referimos como la clase de hipótesis . Por lo tanto, nuestro objetivo G es encontrar una hipótesis (conjunto de parámetros sobre nuestro modelo de elección) de la clase de hipótesis (un conjunto diferente de parámetros corresponderá a diferentes hipótesis, por lo tanto, en toda su clase llamada) que logra la precisión deseada con el requisito confianza usando nuestro conjunto de entrenamiento dado.
En toda esta descripción, una pregunta natural es preguntar cuál debería ser el número de muestras (cada muestra de dimensión d, que se fija debido a nuestro tipo de datos como 256x256x3 para imágenes) que deberíamos tener en el conjunto de capacitación para lograr nuestro objetivo . Prácticamente, sabemos que puede ser innecesario un mayor número de muestras de entrenamiento, y depende en gran medida del tipo de conjunto de datos que tengamos, etiquetas que tengamos, etc. Además, un algoritmo de aprendizaje automático dado puede omitir automáticamente algunas muestras de entrenamiento redundantes que se le dan. . Por lo tanto, para un objetivo como G, nunca podemos decir que el número de muestras de entrenamiento en el conjunto es la medida correcta del tamaño de entrada. De hecho, queremos algo así como un tamaño de entrada efectivo que realmente satisfaga nuestro objetivo. Así definimos la complejidad de la muestra.
Complejidad de la muestra es el término formal que equivale al número mínimo de muestras requerido para lograr el objetivo G. Ahora se puede ver fácilmente que la complejidad de la muestra es una función de precisión, confianza y la clase de hipótesis.
Por lo tanto, el parámetro de entrada p en la notación Big-Oh es esencialmente la complejidad de la muestra para los algoritmos de aprendizaje automático en lugar del número de entradas n en el conjunto de entrenamiento.
Definición de la complejidad computacional de los algoritmos de aprendizaje automático: ahora estamos en condiciones de definir la complejidad computacional de un algoritmo de aprendizaje automático en un sentido general.
Definición 1: Sea H una clase de hipótesis de funciones definidas sobre un espacio de instancia con muestras de dimensiones d, y sea e, δ parámetros de precisión y confianza. Sea m (H, e, δ) la muestra de la complejidad del aprendizaje de H con precisión e y confianza 1 − δ. Entonces, se dice que la complejidad computacional del aprendizaje H está limitada por T (dm (H, e, δ)) si existe un algoritmo de aprendizaje que aprende H y cuyo tiempo de ejecución está limitado por T (dm (H, e, δ) ), y tal que el tiempo de ejecución de la hipótesis que emite en cualquier nueva instancia también está limitado por T (dm (H, e, δ)).
Entonces, donde, por ejemplo, para un algoritmo de clasificación de fusión, la complejidad computacional es O (n log (n)), la complejidad computacional de un algoritmo de aprendizaje es O (d m (H, e, δ) ), dependiendo de la dimensión d de entradas y la complejidad de la muestra.
Tenga en cuenta que la definición dice que el tiempo de ejecución de la hipótesis que genera en cualquier nueva instancia también debe estar limitado por la misma cantidad. Esto es solo para garantizar que el algoritmo de aprendizaje no haya engañado de ninguna manera, y no es que cada vez que se hace una inferencia en una nueva muestra pensando que el algoritmo ya ha aprendido una hipótesis adecuada, el sistema realmente comienza a aprender la hipótesis de El conjunto de entrenamiento. Si esto sucediera, se podría concluir que la complejidad del aprendizaje es constante, pero la complejidad de la inferencia es enorme, lo que anulará todo nuestro propósito de definir la complejidad computacional de los algoritmos de aprendizaje automático.
Preguntas abiertas en la teoría del aprendizaje computacional
Ahora discutimos cuáles son los principales cuellos de botella en la teoría del aprendizaje computacional y concretamos la noción de complejidad computacional de los algoritmos de aprendizaje automático.
(1) Se puede ver en la Definición 1, que si podemos definir la complejidad de la muestra para un algoritmo dado, podemos informar concretamente a la comunidad sobre la complejidad computacional del algoritmo. Aquí yace la trampa. Aunque hay muchas teorías como Probablemente Aproximadamente Correcta (PAC por la ganadora del premio Turing Leslie Valiant), PAC-Bayes (PAC combinado con nociones bayesianas) que pueden dar algunos límites en la complejidad de la muestra, todos los límites son generalmente flojos. Donde los límites pueden ser más estrictos (como en PAC Bayes), uno debe elegir los antecedentes apropiados, lo que nuevamente es un problema difícil. Por lo tanto, para un algoritmo dado, un problema abierto es obtener límites teóricos realistas (que coincidan con la práctica) para la complejidad de la muestra.
(2) Si de alguna manera se conoce un buen límite para la complejidad de la muestra, existen problemas abiertos en la teoría de la complejidad computacional para los algoritmos de aprendizaje automático. Teóricamente, uno puede probar que para una tarea de aprendizaje automático dada, ningún algoritmo de aprendizaje puede resolverlo de manera eficiente; pero tales pruebas y límites relacionados no se mantienen en la práctica (Un ejemplo clásico es el aprendizaje profundo, donde el Descenso de gradiente estocástico hace que casi todo sea manejable). Por lo tanto, una pregunta importante es proporcionar límites para la eficiencia computacional de un algoritmo que pueda explicar aspectos prácticos. Esto incluiría definir la complejidad computacional de un algoritmo de manera diferente pero precisa.
(3) Otro aspecto de investigación en la teoría de la complejidad computacional para algoritmos de aprendizaje automático es la noción de hipótesis aproximada. Normalmente, deseamos tener una hipótesis que pertenezca a una clase predefinida, y en tal caso, una tarea de aprendizaje puede ser difícil de aprender. ¿Qué pasa si atenuamos esta restricción y dejamos que la hipótesis aprendida esté fuera de la clase de hipótesis original, pero en algún lugar cerca de ella? ¿Puede entonces conducir a soluciones que se puedan aprender de manera eficiente para una tarea de aprendizaje o no? En algunos casos, es cierto, mientras que en otros no.
Tenga en cuenta que (1), (2), (3) sobre todo se vuelven interdependientes si uno comienza a desarrollar una teoría profunda.
Complejidad computacional de los algoritmos de optimización Tenga en cuenta que la complejidad computacional de los algoritmos de optimización (CCOA) es diferente de la de los algoritmos de aprendizaje automático.
Para CCOA, el parámetro p es típicamente una función del tamaño de entrada n y el número de iteraciones que tomará el algoritmo. Dado que el número de iteraciones depende del tipo de datos de entrada, en CCOA (lea los documentos de FOCS, SODA, STOC), los objetivos de la investigación son (a) probar los límites en el número de iteraciones que un algoritmo tomará para converger (b ) para descubrir las propiedades de los datos de entrada (generalmente alguna estructura) bajo los cuales el algoritmo puede ser eficiente (como obtener soluciones integrales para problemas de programación enteros es idealmente NP-duro, pero bajo restricciones unimodulares en la entrada, se convierte en tiempo polinómico usando Relajación LP, con garantías de obtener la misma solución integral óptima). (c) diseñar nuevos algoritmos que puedan ser más eficientes dadas las propiedades genéricas de los datos de entrada.
Cada algoritmo de aprendizaje automático implementa alguna función de optimización subyacente. Sin embargo, si bien CCOA solo analiza el número de iteraciones y las propiedades de las entradas independientes de cualquier restricción de salida que deba cumplirse, el algoritmo de Complejidad computacional del aprendizaje automático necesita estudiar las propiedades de entrada (datos de entrenamiento) al tiempo que tiene en cuenta las restricciones de precisión de salida , la confianza y también la complejidad de la clase de hipótesis considerada, ya que el objetivo de los algoritmos de aprendizaje automático es diferente de un algoritmo de optimización. Por lo tanto, si hablamos simplemente de la complejidad computacional de un algoritmo de optimización, no estamos hablando de la complejidad del algoritmo de aprendizaje automático que lo utiliza.
Referencias utiles
(1) Comprensión del aprendizaje automático: de la teoría a los algoritmos por Shai Shalev Shwartz y Shai Ben David, Cambridge University Press
(2) Introducción a la teoría del aprendizaje computacional, por Michael Kerns y Umesh Vazirani, MIT Press.
(3) Varios documentos COLT y algunos documentos NIPS relacionados.
(4) Notas de escriba de Rob Schapire en aprendizaje automático teórico en Princeton (COS 511, primavera de 2014: inicio)
¡Espero que mi respuesta ayude de alguna manera!
