Con lo escrito nos hacemos una idea de estos métodos. Damos por terminada la entrada.
0. Introducción.
a) Preliminares.
Deep Learning es una tecnología que no necesita presentación. Es una tecnología que pertenece al campo de la Inteligencia Artificial.
Nota. IA, ¿ un sector estratégico ?.
El tema de la Inteligencia Artificial es claramente de actualidad. Las empresas mencionadas en el artículo tienen las dos patas sobre las que está corriendo el campo de la Inteligencia Artificial. La pata de los datos, mencionada en el artículo y la otra pata que no mencionan en el artículo pero igual de clave, la capacidad computacional: memoria, con las granjas de servidores (los datos no están flotando en el aire) y supercomputación.
En contraste con la fraccionada UE, la teóricamente subdesarrollada China ha conseguido crear su propio ecosistema computacional, en hardware (son líderes o disputan el liderato en supercomputación), en software y plataformas de internet (buscador Baidu, plataforma de ecommerce Alibaba etc….). Aunque esto posiblemente sea, más que un objetivo buscado, un efecto «no deseado», un subproducto, de no permitir, seguramente por motivos más políticos que económicos, que las multinacionales operen en ese mercado.
Fin de nota.
Hemos estudiado algo superficialmente Deep Learning en la entrada anterior. Superficialmente pero lo suficiente como para al menos tener claros cuales son los temas clave que una teoría de Deep Learning tiene que contener. Temas en los que hemos querido profundizar algo más en esta entrada.
Realmente estudiar este tema es complejo dado que, por accidentes históricos, cada practicante de la tecnología utiliza un lenguaje de su padre y de su madre (es decir de su respectiva tradición, que puede ser la estadística, la informática práctica, la investigación operativa…) y que no es el mismo que utilizan los teóricos de las ciencias computacionales. Por eso si integrar teoría y práctica ya es complejo en general, cuando existe esta confusión conceptual y terminológica lo es mucho más. Esto, y la propia complejidad inherente al tema de estudio, ha hecho que hayamos pasado de la claridad a la confusión en varias ocasiones. Y sinceramente hay varios puntos en los que para nosotros la visión es más oscura que clara, lo cual seguramente notará el lector a la hora de redactar la entrada.
Por todo ello, al final la idea de una entrada breve y resumida se ha evaporado y nos ha quedando más un borrador lleno de enlaces a documentos, más o menos confuso según los puntos, que un esbozo. Cuando tengamos todo 100% claro haremos la deseada entrada breve y resumida. La entrada ha sido redactada entre los días 11 y 17 de noviembre y su estructura y contenido ha cambiado varias veces durante su redacción.
En lo que sigue, como modelo de máquina (teórica) computacional de Deep Learning tenemos en mente a los perceptrones multicapa (MLP, multi-layer perceptrón), aunque hay otro tipo de «neuronas» (por ejemplo las de tipo radial, cuyo nombre exacto ahora mismo no recuerdo) que se pueden utilizar como unidad constructiva de la red. No nos gusta la analogía con el cerebro humano por engañosa, ya que se toma de forma literal cuando no lo es (o al menos puede no serlo, realmente no lo sabe nadie pues de momento el conocimiento que tenemos del funcionamiento del cerebro es del tipo caja negra) pero para no complicarnos la vida ni complicársela al lector, con nueva terminología vamos a utilizar de manera intercambiable la palabra perceptrón y neurona.
b) Resumen de contenidos de la entrada.
La entrada es un esbozo de una teoría digamos general del Deep Learning, y vamos a intentar incluir todos los temas relevantes, los puramente tecnológicos, de mayor interés para tecnologos o ingenieros que tratamos en el punto I:
–expresividad eficiente de las redes neuronales,
–entrenamiento / aprendizaje / optimización de la función de ajuste y generalización, teniendo en cuenta el tamaño y representatividad de las muestras para aprendizaje y generalización,
–interpretabilidad de los sistemas computacionales en general y, en concreto, de los métodos de Deep Learning.
y, en un segundo muy breve punto II, otros aspectos como la evaluación de estos sistemas o su regulación, de mayor interés para el ciudadano medio, el inversor o el político que se tenga que relacionar con estos sistemas.
De todos estos contenidos, hasta el apartado 5 inclusive del punto I, creo que la lectura puede ser informativa para el lector, al menos para ver la problemática práctica y teórica vinculada a esta tecnología. En estos puntos tratamos de la capacidad de representación universal y eficiente de las redes profundas, el problema de entrenamiento u optimización (que contiene el problema del tamaño de las muestras y el problema de la generalización). En base a todo esto se define la clase DL-P.
El punto 6 trata de la interpretabilidad e intentamos determinar los elementos necesarios para construir un modelo de complejidad computacional (con la correspondiente clase) que tenga en cuenta esta propiedad. Está en redacción, sobre todo la parte b).
Las clases DL-P y DL-NP.
Uno de los objetivos de la entrada, que además ha sido el hilo conductor a la hora de redactarla, era introducir conceptos de complejidad en este campo, que tras las primeras lecturas veíamos (erróneamente) poco teorizado. Concretamente la idea era introducir clases de complejidad similares a las clases P y NP en complejidad, digamos, clásica.
Al final parece que tiene sentido, al menos desde un punto de vista pedagógico, definir la clase DL-P (que es similar o asimilable bien a la clase Efficient PAC Learnable) y (quizás menos) la clase DL-NP, aunque la definición de esta última está menos clara, sea de momento más analógica o metafórica, y no tenga que ver con la interpretabilidad, como habíamos pensado inicialmente.
Ha tenido sentido pedagógico para mi dado que me ha permitido comprender los elementos / fundamentos (que no los detalles) de algunos rudimentos de la práctica de Machine Learning en general, incluido Deep Learning, y de la teoría computacional y de complejidad computacional aplicable a la práctica del Machine / Deep Learning. Me refiero a la teoría PAC learning.
Modelo de interpretabilidad en sistemas computacionales.
Una vez definidas estas dos clases parece que si que tiene sentido definir unas clases más restringidas que incorporen como condición de pertenencia el concepto de interpretabilidad. Y el introducir esta clase nos lleva a determinadas preguntas que de momento nos parecen relevantes.
Para aterrizarlo hemos utilizado el concepto de representación sucinta (que es un concepto técnico cuantificable) que permita una verificación parcial (concepto técnico cuantificable)usando información limitada procedente del interpretante (de la computación que se quiera interpretar; concepto técnico cuantificable). La clave aquí (lo que hace que pueda ser una teoría de complejidad computacional), además de los conceptos de representación, verificación del método e información del interpretante son los adjetivos sucinto, parcial y limitada.
Más o menos venimos a decir que un método (cualquiera, sea de Deep Learning, Machine Learning o de cualquier otro tipo de computación) es interpretable si admite una representación sucinta que permita una verificación parcial (también concepto técnico) del método (no de la corrección del resultado) usando una cantidad de información limitada proveniente del interpretante .
Por ejemplo si el método son redes neuronales, la representación sucinta debe de permitir que, obteniendo información limitada sobre una computación ya realizada por la red neuronal, se realicen determinadas operaciones sin que se necesite ni construir la red completa ni repetir la computación (la red puede llegar a ser muy grande y repetir una computación en ella puede llegar a ser muy costoso), y que nos informen sobre el comportamiento de esta red. Estas son en nuestra opinión las bases sobre las que se puede construir una teoría de complejidad vinculada al concepto de interpretabilidad.
Nota. Novedades que pensamos aporta esta entrada con respecto a todo lo publicado sobre este tema antes.
La parte incluida en esta nota la hemos escrito prácticamente al principio y a medida que hemos ido avanzando en lecturas hemos visto que lo que pensábamos no era del todo correcto y hemos ido actualizando. Finalmente conservamos este contenido como una nota ya que para nosotros tiene interés: de todo lo que pensábamos que era nuevo seguimos pensando que el «modelo» de interpretabilidad que proponemos puede contener algunas novedades.
El lector tiene que pensar que se la tecnología Deep Learning es una (en definitiva no tan nueva tecnología) que combina tres disciplinas ya clásicas, casi a partes iguales, en el sentido de que las tres son absolutamente necesarias para que la tecnología funcione correctamente: ciencias de la computación, optimización matemática (investigación operativa) y probabilidades / estadística.
Combinamos las tres disciplinas mencionadas en esta entrada cuya principal aportación con respecto a todo lo publicado previamente (si lo es, es dudoso que estas clases no se haya definido ya de la misma manera que lo hacemos nosotros, o al menos de manera aproximada o implicita) sería la propuesta que hacemos de definición de las clases DL-P y DL-NP (al menos del listado de todos los componentes, y de su dimensión, que se tienen que utilizar para definirlas).
–Primera novedad. Este intento de trasladar los conceptos de P y NP al campo del Deep Learning, sea correcto o incorrecto, pensamos que es una primera novedad o aportación de la entrada al estado del arte.
Como sabe cualquiera que haya leído algo sobre el tema, está claro que las clases P y NP de la teoría de complejidad computacional clásica, aplicables a problemas de decisión de computación clásica, ya se han generalizado antes para muchos otros campos. Pienso por ejemplo en:
–las clases #P y #NP para problemas de conteo, o,
–las clases VP y VNP para los problemas funcionales, o,
–las clases BPP y PP y para la computación probabilística o,
–las clases BQP y QMA para la computación cuántica.
No somos exhaustivos. Lo que intentamos en esta entrada es precisamente definir unas clases de complejidad que capturen y trasladen estas diferencias que capturan todas estas clases entre, digamos, la computación eficiente y la verificación eficiente, en el campo del Deep Learning, intento que, ya lo hemos dicho, pensamos es nuevo. Las hemos definido y llamado clases DL-P y DL-NP. Para aquellos que sean nuevos en la disciplina de complejidad computacional y quieran conocer más información sobre como se definen todas estas clases (excepto las dos que hemos definido nosotros) se puede ver el Complexity Zoo.
Actualización 0, mismo día más tarde.
Ya existen diversas teorías de complejidad computacional relacionadas con la disciplina de Machine Learning, dentro de la cual está Deep Learning.
There are several different approaches to computational learning theory. These differences are based on making assumptions about the inference principles used to generalize from limited data.[citation needed] This includes different definitions of probability (see frequency probability, Bayesian probability) and different assumptions on the generation of samples.[citation needed] The different approaches include:[citation needed]
- Exact learning, proposed by Dana Angluin;
- Probably approximately correct learning (PAC learning), proposed by Leslie Valiant;
- VC theory, proposed by Vladimir Vapnik and Alexey Chervonenkis;
- Bayesian inference;
- Algorithmic learning theory, from the work of E. Mark Gold;
- Online machine learning, from the work of Nick Littlestone.
Hay que ver si el planteamiento que hacemos es el mismo que se hace en algunas de estas teorías (en general las teorías listadas no son alternativas sino que son subcasos de la teoría más general de Valiant). Valiant ha sido el autor de varias traslaciones de los conceptos de P y NP a otros ámbitos (conteo, funciones), así que no soprende encontrarle en este contexto. Una entrevista:
https://www.quantamagazine.org/the-hidden-algorithms-underlying-life-20160128/
Fin de actualización 0.
Aunque pensamos que las clases DL-P y DL-NP, tal y como la vamos a definir contiene a todos los componentes que tienen que contener, y pensamos que bien dimensionados cuantitativamente, posiblemente el nombre no sea el más adecuado. Hemos puesto el sufijo P, para que se comprenda la analogía con la bien conocida clase P. Esto nos lleva a la segunda novedad.
–Segunda novedad. el intento de listar todos los elementos que tienen que aparecer para definir la clase DL-P. Y más concretamente indicar que se debe de relacionar el tamaño de la cantidad de muestras con el tamaño del input del MLP.
Actualización 0bis mismo día más tarde. No está claro tampoco que este tema sea nuevo. Hay concepto llamado sample complexity presente en algunas de las teorías de complejidad vinculadas a Machine Learning (Deep Learning): https://en.wikipedia.org/wiki/Sample_complexity
Este enlace nos lleva al concepto de computational learning theory sobre el que había oído hablar pero no conocía en detalle. De interés el aprendizaje PAC. Como no, quien está detrás de este desarrollo es el gran generalizador de la dicotomía P y NP, Valiant :-). Hay que ver si dice exactamente lo mismo que nosotros.
No lo he leído en detalle, pero me da la impresión de que vinculan el número de muestras con el número de parámetros, lo cual, teniendo en cuenta la relación polinómica entre el número de parametros y el tamaño del input del MLP (que impone la primera condición), me parece que así es. En este caso es lo mismo vincular el número de muestras directamente con el tamaño del input o con el número de parámetros a efectos de complejidad.
Actualización 14 nov. Se confirma que nuestra clase DL-P se puede incluir dentro de los conceptos de PAC Learning. Por lo tanto no es nueva.
Fin de actualizaciones 0bis.
Está claro que hay problemas de Deep Learning que están en DL-P y otros que tienen que estar en otra clase que podemos llamar provisionalmente DL-NP y para cuya definición damos unas primeras pinceladas en lo que sigue. Está claro que esta clase, o al menos así lo vemos nosotros, se tiene que definir en función de una interpretabilidad eficiente (la interpretabilidad eficiente es como una generalización de la verificación eficiente y la comprende). La interpretabilidad (lo contrario de la opacidad,problema sobre el que los investigadores de este campo son muy conscientes) es el equivalente en este contexto de verificación eficiente en la clase NP tradicional. De cualquier manera lo que presentamos es sólo un esbozo que obviamente se tiene que completar y pulir.
–Tercera novedad. La identificación del problema de interpretabilidad eficiente como un problema del mismo tipo pero más general que el problema de verificación eficiente del input en las clase P y NP, problema que se debe de utilizar para definir la clase DL-NP.
Actualización 14 de noviembre.
La interpretabilidad es un problema del mismo tipo que el de verificación del resultado, pero la clase de complejidad asociada es más restringida.
El insertar el tema de interpretabilidad en temas de complejidad computacional si es bastante nuevo, y parece que tampoco somos los primeros en tratarlo (bien o mal, sea correcta o incorrecta nuestra incursión en el tema). Acabo de ver un artículo en el que lo comentan:
Machine Learning Interpretability: A Survey on Methods and Metrics.
Julio de 2019.
Algorithmic complexity—It is related to computational complexity of the explanation method. This property is very important to consider regarding feasibility, especially when computation time is a bottleneck in generating explanations.
Realmente este contenido lo sacan de otro artículo que mencionan:
Robnik-Šikonja, M.; Bohanec, M. Perturbation-Based Explanations of Prediction Models. In Human and
Machine Learning; Springer: Berlin, Germany, 2018
Por lo tanto al menos desde hace un par de años hay conciencia de que se pueden combinar estos dos campos. Pero no tengo claro si alguien ha dado ya el paso de crear clases de complejidad que capturen la interpretabilidad.
Fin de actualización.
Queremos advertir desde aquí que la propuesta de definición que hacemos de la clase DL-NP (utilizar la intepretabilidad para definirla) está bastante menos aterrizada que la propuesta para definir la clase DL-P, que tampoco es perfecta, pues hay que aterrizar el tema de la generalización / muestreo representativo.
En las tres novedades que señalamos hemos sentido el ¡¡ ajá !! que todo investigador o inventor siente con las cosas nuevas, pero ya decimos que podrían no serlo. Con respecto a estas novedades, por una parte, nótese que tampoco escribimos la entrada para tener prioridad sobre nada, sino más bien para aclarar las ideas que hemos ido desarrollando a la hora de recopilar enlaces y leer documentos en la entrada anterior y ponerlas negro sobre blanco de manera resumida. Es una manera de asimilar mejor lo aprendido y lo reflexionado sobre estos temas. Pero por otra parte, si estas definiciones son correctas o al menos (como pensamos) van por el buen camino y somos los primeros en haber desbrozado este camino, aquí consta en acta :-).
Tenga en cuenta el lector que lea estas líneas y quiera utilizarlas que en general nos gusta tanto respetar la normas de propiedad intelectual como que los demás los respeten. Para ver como se puede enlazar y citar esta entrada puede o bien contactarnos haciendo un comentario a esta entrada, bien enviando un email a la cuenta que aparece en el about del blog (para ver el about tiene que ir a la home, cosa que puede hacer pulsando en la cabecera). Obviamente puede utilizar los mismo métodos para manifestar su desacuerdo con los contenidos de la entrada.
Fin de nota sobre novedades de la entrada.
I. Esbozo de una teoría del Deep Learning: diseño de la red universal y eficiente, entrenamiento / aprendizaje de la red, generalización e interpretabilidad.
0. Justificación del campo de la Inteligencia Artificial: soluciones a problemas sencillos pero imprecisos.
and adapt
Inglés: The SIX Group AG adhesion canseji, the company that draws the Swiss Bilsa, drafted in Zurich, agreed to hold a public office of adhesion (opaque), of a volatile coracter, on the tetality of the actions of Spanish Stock Exchanges and Markets (BME) , the dirt that manages versatile eperitions in the Spanish mercudo, according to SIX Group
conjecture goes, then there is no polynomial bound on the number of moves necessary to execute a perfect strategy. This is so because Pspace c Exptime, and the “game-tree” of chess can be traversed in endorder to determine the
win-lose-tie membership of each node (game position). Though this takes an exponential amount of time, the memory requirement at each step is only the depth p(n) of the tree-which is kept on a stack-and the description of a
terminal position. Thus, if p(n) is polynomial, then the game is in Pspace. Since chess is complete in Exptime, it belongs to the hardest problems there, hence it lies in Exptime – Pspace if Pspace != Exptime.
1.Diseño de una red (máquina) universal y eficiente.
1.1 Red universal. Capacidad expresiva universal de las redes neuronales (máquina universal, pero con arquitectura o topología ineficiente). Las redes de perceptrones unicapa y los MLP pueden representar cualquier función (representan exactamente funciones booleanas, representan espacios acotados linealmente, aproximan con cualquier grado de precisión funciones continuas acotada en cualquier número de variables…). Esto se demostró hace décadas y no es nada sorprendente. Son una máquina universal más, de las múltiples que hay. La universalidad es una propiedad interesante pero bastante vulgar o común.
1.2. Red universal y eficiente. Capacidad expresiva universal y eficiente de los MLPs (máquina universal y arquitectura o topología eficiente). Los MLPs pueden conseguir la universalidad con un uso eficiente de recursos (los recursos aquí son el número de perceptrones o neuronas), en función del tamaño del input. Eficiente aquí quiere decir un un número polinómico o mejor de perceptrones o neuronas. Esto no es posible para una red neuronal de una sola capa: necesita un número exponencial de recursos (neuronas) en función del tamaño del input. Este es el valor añadido de las diversas capas. Que no es poco. Sin esto, solo por ello esta tecnología no sería eficiente. Es esta una primera condición de eficiencia, pero no la única. Hay dos más que vemos luego.
Todavía no está claro si la cantidad de recursos que necesita una MLP es puede ser constante con respecto al tamaño del input, logaritmica o polilogarítmica. Es decir no se sabe si estructuralmente Deep Learning está en TC^0 o TC^1 o en que nivel de la jerarquía TC. Más claramente: parece que con un número constante de capas ya se puede obtener una representación eficiente que no es posible con una sola capa, pero no se sabe si un número logarítmico de capas es exponencialmente más poderosa que un número constante. Podría haber una función tal que admita una representación eficiente con un número logarítmico de capas pero no con un número constante. Es un problema problema abierto.
Nota. TC^0 y TC^1 son clases de complejidad que pertenecen a la jerarquía TC (Threshold circuits), una clase de complejidad de la teoría de circuitos booleanos. Son circuitos en los que una de las puertas es de umbral. Fin de nota.
Aunque teóricamente se pueden construir MLPs eficientes y de hecho ya se hace, pienso que en la práctica debemos de estar muy lejos del óptimo a este respecto y que se puede mejorar el uso de recursos en los MLP que se construyen actualmente. Lo digo porque veo mucho cable (muchos arcos en las redes neuronales). Y el cable en una máquina es caro, sea en modo hardware o en modo virtual (en cuyo caso el coste es tiempo y espacio de computo). De cualquier manera, esto es normal en una tecnología nueva: los primeros sistemas son siempre torpes.
Nota especulativa. Pero son torpes no solo por los cables. Si uno observa el cerebro no ve, en general, redes neuronales diseñadas por la naturaleza para resolver problemas específicos. Ve redes que se repiten por todas partes (no se si la visión es una excepción a esto). Por lo tanto no es imposible que haya una, digamos, topología (piense el lector en una MLP sin etiquetas de ningún tipo) que sea la óptima para cualquier problema. De momento parece que lo que tenemos en Deep Learning es que hay que diseñar una red para cada problema específico, siendo esta operación de diseño (en la que hay que decidir sobre el número de capas, número de neuronas en cada capa etc…) bastante costosa en tiempo de ingeniero. Fin de nota.
Una vez que se dispone de un MLP universal y eficiente, que no es más que una máquina capaz de representar cualquier función de manera eficiente, el siguiente paso es encontrar la función que dicho MLP vaya a implementar para resolver el problema práctico de interés. Para aquellos que han estudiado estadística esto es equivalente al problema de encontrar una función que ajuste a unos datos de entrada. Por ello vamos a llamarla función de ajuste. Este es el siguiente paso y define la segunda condición de eficiencia. Si este paso no se puede hacer de manera eficiente, en función del tamaño del input, entonces no tendríamos una máquina eficiente. Lo vemos en el punto siguiente.
3.Entrenamiento / aprendizaje de la red: capacidad de obtener la función de ajuste (problema de optimización) de manera eficiente (programación eficiente de la máquina universal).
En el punto anterior hemos visto como se puede construir de manera eficiente (usando la profundidad) una máquina con capacidad de expresión universal. En este punto vamos a ver como se puede programar esta máquina para que resuelva problemas prácticos como reconocimiento de voz, descripción escrita del contenido de una imagen, traducción escrita etc….. Se busca una forma de programación que sea eficiente.
3.1.Terminología usual. A la programación de la máquina (red universal eficiente) para que resuelva este tipo de problemas a veces se le llama aprendizaje (en el sentido de que la máquina está aprendiendo a realizar estas tareas, a resolver este tipo de problemas), a veces entrenamiento (en el sentido de que el programador humano le está enseñando, está entrenando a la máquina a resolver estos problemas). A veces, por parte no de los teóricos sino de los prácticos, a esta fase de los métodos de Deep Learning se le llama fase de optimización, porque el problema a resolver en la práctica consiste, como vamos a ver más adelante, en optimizar, de manera eficiente, la función que ajusta los datos de input y de output.
Dicho esto, aunque en a literatura se habla de aprendizaje, entrenamiento (training), optimización etc…lo cual es perfectamente correcto y nosotros vamos a utilizar también este lenguaje, en esta fase lo que se está haciendo (al optimizar la función de ajuste) es programar a la máquina universal y eficiente que hemos descrito en los puntos anteriores, para que realice la tarea que nos interesa. El programa al final será, de entre todas las funciones posibles una función que sea capaz de resolver el problema con el mínimo de errores.
3.2 Teoría (PAC Learning) y práctica de la fase de entrenamiento en Deep Learning.
Con respecto a la teoría, existe una teoría de complejidad computacional aplicable a estos problemas de aprendizaje. Se llama teoría PAC Learning y se desarrolló en la década de los 80 del siglo pasado por un destacado teórico de complejidad computacional (L.Valiant). Desde que emergió esta teoría, han surgido otras teorías, pero que en general no son más que variaciones de ella.
Sinceramente no tengo claro del todo si esta teoría PAC Learning y sus variaciones capturan bien la actual práctica del Deep Learning, que se ha desarrollado sobre todo en la última década. En la práctica, de lo que se trata es, utilizando un conjunto limitado de ejemplos (una muestra de entrenamiento), encontrar (optimizar) la función (el conjunto de pesos y sesgos de la red) que mejor solucionen el problema. Para ello el estado del arte actual aplica métodos de gradiente estocástico y retropropagación o backtracking.
[Advertencia. Admito que me está costando integrar en un modelo mental sencillo lo que estoy leyendo sobre la teoría y sobre la práctica de la fase de aprendizaje. El lector tiene que tener en cuenta esto a la hora de leer este punto].
3.2.1 Teoría PAC Learning. Muy breve introducción a sus rudimentos.
a) Artículo seminal de Valiant.
Quizás para empezar, el lector quiera leer directamente el artículo de Valiant (de 1984) dónde se expone por primera vez esta teoría.
Haz clic para acceder a Valiant84.pdf
Nosotros le hemos echado una primera ojeada muy en diagonal. Lo que Valiant se plantea es una teoría de lo aprendible similar a la teoría de lo computable de Turing. Para ello define un protocolo de aprendizaje que tiene dos subrutinas (Examples, es decir, la máquina tiene la posibilidad de acceso a ejemplos de lo que quiere aprender, variable que es equivalente al nº de elementos de la muestra, y Oracles, que es la subrutina que le dice a la máquina que está aprendiendo si el ejemplo pertenece al concepto o no).
Extraemos un par de teoremas para que el lector vea como se expresa la complejidad en este artículo original:
THEOREM A: For any positive integer k, the class of k-CNF expressions is learnable via an algorithm A that uses
L = L(h, (2t)^k+1) calls of EXAMPLES and no calls of ORACLE, where t is the number of variables.
Calls of examples se puede traducir exactamente por número de elementos de la muestras.
THEOREM B: The class of monotone DNF expressions is learnable via an algorithm B that uses L = L(h,d) calls of
EXAMPLES and dt calls of ORACLE, where d is the degree of the DNF expression f to be learned and t the number of
variables.
Ahora mismo no tengo claro con que se corresponde la subrutina oracles en nuestro modelo, pero si está claro que en el modelo original de Valiant la complejidad se expresa, entre otras cosas, en función del número de variables, que es el parámetro habitual de complejidad en la teoría clásica.
b) Visiones más actualizadas: algunos enlaces.
A continuación algunos enlaces de interés más actuales que el lector debe de leer para hacerse una idea de en que consiste la teoría PAC Learning.
En el documento que enlazamos a continuación aparece la teoría de complejidad PAC Learning, vista desde un punto de vista má práctico que el que suele aparecer en otros documentos.
Haz clic para acceder a Lecture10.pdf
La página web del autor de este documento con más enlaces. Es el autor de un libro sobre este tema (de 2014).
https://www.cs.huji.ac.il/~shais/
También se puede ver el breve y denso artículo de wikipedia al respecto:
https://en.wikipedia.org/wiki/Probably_approximately_correct_learning
c) Concepciones de eficacia (computabilidad) y eficiencia (complejidad) en PAC Learning.
Según como lo veo la teoría de aprendizaje PAC, tal y como debe de ser en toda teoría computacional, tiene en cuenta dos temas: la eficacia o computabilidad (la capacidad de resolver el problema) y la eficiencia o complejidad (la capacidad de resolver el problema con un uso económico de recursos). Vamos a ver que concepción tiene de la eficacia y eficiencia en esta teoría
c1) Eficacia.
Con respecto a la eficacia introducen el concepto PAC: en vez de buscar un método o algoritmo que resuelva el problema de manera determinista y exactamente aceptan métodos que con un elevado nivel de confianza probabilístico (y en esto contrasta con el determinismo) encuentren soluciones de un grado de aproximación aceptable (y esto contrasta con la exactitud).
El nivel de confianza y el grado de aproximación son dos datos sobre los que el diseñador de métodos de Deep Learning tiene que decidir. Es decir, es el diseñador de estos métodos el que decide que nivel de confianza y que grado de aproximación quiere que tenga una determinada aplicación.
c2) Eficiencia.
En la teoría de PAC Learning también el concepto de eficiencia se divide en dos componentes:
–complejidad del muestreo (del número de elementos de la muestra; sample complexity).
–complejidad de la búsqueda u optimización de la función de ajuste (es decir uso de recursos necesarios para encontrar los pesos y sesgos con los que se va a programar la red neuronal; algorithmic or computational complexity).
De estos dos componentes nos hablan en el artículo de wikipedia.
An important innovation of the PAC framework is the introduction of computational complexity theory concepts to machine learning. In particular, the learner is expected to find efficient functions (time and space requirements bounded to a polynomial of the example size), and the learner itself must implement an efficient procedure (requiring an example count bounded to a polynomial of the concept size, modified by the approximation and likelihood bounds).
Sample complexity.
Dados el nivel de confianza, el grado de aproximación, la clase de funciones más adecuadas para resolver el problema práctico que se quiere resolver (reconocimiento de imágenes etc…) y el tamaño del input, la teoría PAC permite determinar (calcular) cual es el tamaño mínimo de la muestra necesaria para optimizar la clase de funciones dada. La fórmula que permite realizar este cálculo expresa este tamaño de la muestra en función de estos parámetros (nivel de confianza, grado de aproximación, tamaño del input…).
Algorithmic complexity.
Este tema lo vamos a ver en más detalle en el punto 3.2.2. El tema es complejo pues, como es habitual, se quiere que el análisis de complejidad algorítmica sea en términos asintóticos, es decir válido para cualquier tamaño de input. Dicho esto para que un algoritmo de búsqueda de una función de ajuste sea eficiente, se pide que la sample complexity sea polinómica (que el tamaño de la muestra sea polinómico en función de los parámetros indicados en el punto anterior; esta es la condición que se impone en sample complexity) y segundo (y más importante), que el algoritmo haga un uso polinómico de recursos en función del tamaño de la muestra.
Si el algoritmo es polinómico en función del tamaño de la muestra, pero la muestra es de tamaño exponencial, ya estamos fuera de Efficiente PAC Learning. Y los mismo sucede si la muestra es de tamaño polinómico, pero el algoritmo tiene que utilizar los elementos de la muestra un número exponencial de veces.
Obviamente esto es una presentación de estas concepciones de eficacia y eficiencia a vista muy de pájaro, altamente simplificada. Si se quieren complicar las cosas, habría que hablar,por ejemplo, del teorema fundamental del machine learning, que relaciona la teoría PAC con la teoría VC dimension, y que se refiere a sample complexity. No vamos a desarrollar este tema.
d) Algunos ejemplos de problemas PAC Learnable y problemas no PAC Learnable.
Vamos a poner, con ayuda de enlaces externos algunos ejemplos:
–un ejemplo de problema PAC Learnable (bajo el modelo PAC, que no captura todos los tipos de aprendizaje computacional posibles).
Probably Approximately Correct — a Formal Theory of Learning
–y un ejemplo de problema que bajo el mismo modelo no es PAC-Learnable.
Un artículo con muchos más ejemplos es
e) Más enlaces de interés sobre PAC Learning.
Sobre el concepto de concept class, para que se vea lo amplio que puede ser:
Haz clic para acceder a a4f2371259836c2513c2564e34f7b6d0fbaf.pdf
f) Generalización en PAC Learning.
Como vamos a ver luego, nuestra tercera condición para la clase DL-P consiste en una verificación eficiente de la generalización. También en la teoría PAC-Learning aparece la generalización:
In this framework, the learner receives samples and must select a generalization function (called the hypothesis) from a certain class of possible functions. The goal is that, with high probability (the «probably» part), the selected function will have low generalization error (the «approximately correct» part). The learner must be able to learn the concept given any arbitrary approximation ratio, probability of success, or distribution of the samples.
g) Modelo de PAC Learning para funciones booleanas.
Hemos encontrado un artículo en el que nos ilustran sobre esto.
Haz clic para acceder a 79f3b3d9272f636c149446759befd86171f9.pdf
This report surveys some key results on the learning of Boolean functions in a probabilistic model that is a generalization of the well-known ‘PAC’ model. A version of this is to appear as a chapter in a book on Boolean functions, but the report itself is relatively self-contained.
…
In the probabilistic models discussed, there are two separate, but linked, issues of concern.
–First, there is the question of how much information is needed about the values of a function on points before a good approximation to the function can be found.
–Secondly, there is the question of how, algorithmically, we might find a good approximation to the function.
These two issues are usually termed the sample complexity and computational complexity of learning. The report breaks fairly naturally into, first, an exploration of sample complexity and then a discussion of computational complexity.
En este caso aprender una función booleana es, dados los valores de la función para determinados puntos determinar de que función se trata. En el modelo el diseñador fija el nivel de confianza probabilístico aceptable con el que se encontrará la función que aproxime la función objetivo con el grado de aproximación aceptable, y un problema es PAC learnable si dentro de los límites del nivel de confianza puede obtener la aproximación buscada con un número polinómico de elementos en la muestra muestra (¿ en función de ?). La teoría PAC precisamente permite conocer (calcular) el número mínimo de elementos que tiene que tener la muestra para cumplir con el nivel de confianza y el grado de aproximación (esto es la sample complexity). Y es Efficient PAC learnable si además de ser PAC Learneable (necesitar un número polinómico de muestras), la función de aproximación (lo que hemos llamado función de ajuste que minimiza el errror) se puede obtener con un algoritmo polinómico en el peor caso (esto es la computational complexity).
Dejemos que hable de nuevo el propio artículo.
Consider the monomial learning algorithm (for the realizable case) described earlier. This is an efficient algorithm: its running time on a training sample of m data points in {0,1}^n is O(mn), which is linear in the size of the training sample. Furthermore, noting either that VCdim(Mn) = O(n) or that log2 |Mn| = O(n), we can see that, for given epsilon y lambda (grados de aproximación y probabilidad aceptables), we can produce a hypothesis that, with probability at least 1-lambda, has accuracy epsilon, in time of order (ver artículo), where p and q are (small degree) polynomials. This is an example of what we mean by an efficient learning algorithm: as n scales, the time taken to produce a PAC output hypothesis (en nuestro lenguaje, el tiempo de encontrar la función de ajuste optima) scales polynomially with n; additionally, the running time is polynomial in 1/epsilon and ln(1/lambda).
Entonces:
–«clase» PAC learning, cuando la muestra de entrenamiento es de tamaño polinómico, en función del tamaño del input (número de variables).
–clase efficient PAC Learning, cuando además de lo anterior el método de búsqueda es también polinómico.
Está claro que estos dos conceptos son aplicables para casos no booleanos.
h) Pac learning e indecidibilidad.
Un par de enlaces sobre este tema.
Learnability can be undecidable
https://www.nature.com/articles/s42256-018-0002-3
PAC-Learning is Undecidable
https://www.groundai.com/project/pac-learning-is-undecidable/1
3.2.2 Práctica de la fase de entrenamiento / aprendizaje en Deep Learning.
[Advertencia. En esta parte describimos nuestra visión sobre esta tema tras haber leído por encima algunos documentos. La hemos escrito antes de escribir la parte justo anterior (3.2.1), y por lo tanto antes de documentarnos y comprender suficientemente como para escribir sobre ella, sobre la teoría PAC Learning. Mantenemos lo escrito tal cual, con mínimas correcciones. Aunque más o menos llegamos a conclusiones similares(al menos sobre los elementos a tener en cuenta) que la teoría PAC Learning, puede no ser la visión más correcta].
Normalmente esta parte sobre práctica del Deep Learning, se introduce de otra manera, no comentando que el problema es (aproximadamente) equivalente a un programa lineal exponencial. Normalmente se comenta que es un problema de optimización no convexa que en el peor caso es NP-duro y que milagrosamente métodos heurísticos de gradiente estocástico / backpropagation lo resuelven bien en la práctica, lo cual entiendo que es verdad.
Por mi parte prefiero introducirlo utilizando la visión del programa lineal, ya que haciendo esto se aterriza mucho más el tema mentalmente. Le quita parte de la magia a la tecnología, cosa que estimamos conveniente. Que este problema se puede expresar como un programa lineal exponencial se establece de manera aterrizada en un artículo reciente, todavía no publicado (solo en pre-print en 2018 y enviado para publicación a una conferencia; actualmente está en revisión y esto tiene que tenerlo en cuenta el lector). Para mi, para comprender bien este problema, ha sido clave caer en la cuenta que las muestras se deben de considerar como restricciones del programa lineal. Al ir probando muestras, se está acotando el problema.
El problema de optimización de la función de ajuste se puede expresar (aproximar) por un programa lineal exponencial en función del tamaño del input (número de dimensiones) y del número de parámetros (pesos, sesgos) y polinómico en el número de muestras.
La función objetivo del programa lineal es la función de pérdida (que dada una muestra para entrenamiento mide el error entre el ajuste obtenido y el buscado; la función de perdida hace una media de este valor para todos los elementos de las muestras; en la literatura se la llama ERM) y las restricciones son cada uno de los parámetros y cada una de las muestras.
El hecho de que el programa lineal sea exponencial en función del número de parámetros ya nos indica que aquí no se cumple con la condición de eficiencia, pues estamos haciendo un uso exponencial del recurso tiempo y/o espacio. Que las heurísticas lo resuelvan en la práctica no lo hace eficiente en la teoría. Por otra parte, podría ser el caso de que los problemas que actualmente se resuelven bien en la práctica permitiesen una representación mediante un programa lineal polinómico que no se haya identificado todavía, lo cual explicaría que los métodos actuales encuentren buenas soluciones (aproximadas) en la práctica.
Pero para definir la clase de complejidad DL-P, no queremos hablar de esto sino del propio uso de estos dos componentes para determinar la eficiencia.
Tamaño del input (número de dimensiones) y número de parámetros como tamaño a tener en cuenta para determinar la eficiencia del problema de optimización.
Por lo descrito en el punto 2 (representación universal eficiente) está claro que el tamaño del input y el número de parámetros (pesos, sesgos) tienen una relación cuantitativa (se puede conseguir que en un MLP el número de parámetros sea polinómico o mejor con respecto al tamaño del input), con lo cual si el uso es exponencial con respecto al uno, lo es con respecto al otro. Por lo tanto la doble expresión parece redundante.
Bastaría con afirmar, y nosotros lo hacemos para expresar la segunda condición de eficiencia, que el problema de optimización de Deep Learning es eficiente si se pudiese encontrar la función de manera eficiente con respecto al número de parámetros.
Número de muestras en función del tamaño del input.
En este caso, según he visto en diversos artículos (puedo estar equivocado y si veo algo en contra de esta afirmación, corregiré este punto), este parámetro aparece como libre. Se da una cantidad constante (por ejemplo: se han utilizado 200 millones de muestras, como en el caso de AlphaGo). Pero para que se pueda tener en cuenta como criterio de eficiencia, esta cantidad se tiene que vincular con el tamaño del input (dimensiones), lo mismo que el número de parámetros, y esto expresaría la tercera condición de eficiencia.
Por lo tanto, para que un Deep Learning sea resoluble de manera eficiente, tiene que hacer un uso de un número de muestras que sea polinómico con respecto al tamaño del input del MLP.
Cotas sobre el tamaño de las muestras correspondientes a determinado tipo de redes.
Algo de literatura al respecto:
Enero 2019. Sample Complexity Bounds for Recurrent Neural Networks with Application to Combinatorial Graph Problems.
Haz clic para acceder a 1901.10289.pdf
Las cotas se expresan en función de varios «parámetros»:
Sample complexity bounds for RNNs. We derive explicit sample complexity bounds for real-valued single and multi-layer recurrent neural networks. Specifically, we find that the estimation of a RNN with a single hidden layer, a recurrent units, inputs of length at most b, and a single real-valued output unit requires only O˜(a^4 b/ε2) samples in order to attain a population prediction error of ε. In comparison, a d-layer architecture requires at most O˜(d^2a^4 max b/ε2) samples where amax is the width of the first (or widest) layer. During our derivations, we focus on rectified linear units (ReLUs) as these are widespread in machine learning practice.
Como se ve, para acotar el número de muestras, los pesos en concreto no importan, solo «parámetros» de las redes como el número de capas, el número de unidades (neuronas) de la red o de alguna de sus capas, el error aceptado, y también el tamaño del input.
Lo interesante es que en teoría, al parecer ¿ las cotas para el número de muestras suelen ser polínomicas para las redes más interesantes ?. Lo he leído en alguna parte pero no lo he visto en detalle. Y aquí los matices son importantes.
Provable limitations of deep learning
Haz clic para acceder a 1812.06369.pdf
Recall that it is known that the class of neural networks (NNs) with polynomial network size can express any function that can be implemented in polynomial time, and that their sample complexity scales polynomially with the network size. Thus NNs have favorable approximation and estimation errors. The challenge is with the optimization error, as the ERM is NP-hard and there is no known efficient training algorithm with provable guarantees. The success behind deep learning is to train deep NNs with descent algorithms, such as coordinate, gradient or stochastic gradient descent.
Ojo, no dicen que el tamaño de la muestra (número de muestras) sea polinómica con respecto al tamaño de la red sino que a medida que se incrementa el tamaño de la red el incremento en el tamaño de la muestra es polinómico. Pero entiendo que el valor inicial podría ser exponencial. ¿ O no ?.
A través de este artículo se puede acceder a otros artículos relevantes.
Recent examples of bounding sample complexities involve, for instance, binary feed-forward neural networks (Harvey
et al., 2017) and convolutional neural networks (Du et al., 2018). However, similar results are lacking for real-valued
recurrent neural networks (RNNs). This is surprising, since RNNs find widespread adoption in practice such as in natural language processing (e. g., Socher et al., 2011), when other unstructured data serves as input (e. g., Graves et al., 2009), or even when solutions to combinatorial graph problems are predicted (e. g., Wang, 1996). A particular benefit is the flexibility of RNNs over feed-forward neural network (e. g., Rumelhart et al., 1986): even when processing input of variable size, their parameter space remains constant. Hence, this dearth of theoretical findings motivates our research questions: What is the sample complexity of learning recurrent neural networks? How can upper bounding the sample complexity of RNNs be applied in practical use cases?
Sobre el concepto / teoría de PAC (el tema es confuso).
https://stats.stackexchange.com/questions/142906/what-does-pac-learning-theory-mean
Haz clic para acceder a lecture3.pdf
Condiciones para definir la clase DL-P.
Tenemos por lo tanto 3 condiciones que definen la clase de complejidad de los problemas Deep Learning eficientes (DL-P):
a) representación universal eficiente en función del tamaño del input del MLP (y por lo tanto el número de parámetros es polinómico con respecto al tamaño del input del MLP). Esto viene dado por los «teoremas» de universalidad de representación por redes neuronales y de representación universal y eficiente por redes profundas.
b) número de elementos de la muestra polinómica (¿ en función del tamaño del input del MLP ?). Esto nos viene dado por los resultados de la teoría de PAC Learning, concretamente por el concepto de sample complexity.
c) computo eficiente de la función de ajuste en función del número de parámetros y del número de muestras.
Nótese que la condición b) y c) no son equivalentes. Podría darse el caso de que en c) el computo fuese eficiente en función del número de muestras, pero que el número de muestras fuese exponencial con respecto al tamaño del input del MLP, en cuyo caso no hablaríamos de un Deep Learning eficiente.
Obtener un MLP universal y dada la red MLP, obtener la correspondiente función de ajuste de manera eficiente algunos de los objetivos intermedios de esta tecnología, pero no es el objetivo final. El objetivo final es que la función de ajuste funcione correctamente para otras muestras que no son las que se han utilizado para la optimización. Esto es lo interesante de cara a las aplicaciones. Esto es lo que entre los investigadores de este campo se llama el problema de generalización. Para que la función sea interesante de cara de a las aplicaciones tiene que poder generalizar. Vemos esto con más detalle en el punto siguiente.
4. Capacidad de generalización.
[Advertencia. Este es el tema sobre el que he leído menos y por lo tanto conozco menos la literatura técnica. Por lo tanto lo que sigue refleja más nuestra visión que otra cosa. Es posible que el concepto de generalización entre los practicantes expertos sea diferente].
En este punto primero exponemos como vemos nosotros el tema, antes de leer la literatura. Y luego en el punto c) presentamos las principales definiciones de la literatura relevantes para el tema que nos ocupa.
Para nosotros la generalización tiene dos aspectos, aplicándose cada uno en dos fases del proceso de producción del sistema: la fase de diseño, dónde predomina, digamos, el aspecto ingenieril (como conseguir en el entrenamiento que la función generalice) y la fase de verificación, dónde predomina, digamos, un aspecto comercial (que consiste en poder demostrar al propio diseñador del sistema y a potenciales compradores de que efectivamente el sistema generaliza; esto es, la verificación de que el sistema hace aquello para lo que está diseñado). Las dos se tienen que hacer de manera eficiente, o dicho de otra manera, usando recursos polinómicos en función del tamaño del input. Sobre el aspecto ingenieril ya hemos hablado en parte en el punto anterior.
En lo que sigue vamos a comentar sobre los dos tipos de generalización aunque a efectos de definir la clase DL-P es posible que no sea necesario tener a las dos en cuenta.
a) Diseño (generalización ingenieril).
Desconozco que técnicas se utilizan para conseguir esto. A priori, ¿ parece claro ? que, para un problema en concreto, una función de ajuste generalizará bien si la muestra (de tamaño polinómico si queremos que la máquina sea eficiente) que se ha utilizado para obtenerla es representativa de la población o universo del problema al que se va a aplicar. Pensemos en un extremo: seleccionamos como muestra para ajustar siempre la misma fotografía o variaciones muy pequeñas de ella. La función de ajuste identificará a la población con esta fotografía y no reconocerá a toda otra muestra que se presente.
Interesa por lo tanto obtener no sólo una muestra de tamaño polinómico en función del input del MLP, sino también representativa y esta representatividad se tiene que poder obtener de manera eficiente. Este dato o condición, el exigir la representatividad de la muestra, es quizás más complejo que los otros, menos directo, sobre el que hay que elaborar más, se puede bien añadir a la condición b) señalada antes, bien incluir como una nueva condición. Se puede exigir en la condición b) obtener una muestra representativa de la población del problema de tamaño polinómico con respecto al input del MLP.
Elaboramos sobre el tema a continuación.
Población bien definida, muestra representativa.
Está claro que para que una muestra sea representativa de una población, se tiene que:
–poder definir de manera clara ¿ y eficiente ? lo que es la población y,
–se tiene que poder extraer de manera eficiente una muestra estadísticamente representativa (aplicando las conocidas reglas estadísticas, como aleatoriedad etc…) de esta población.
Ciertamente todo esto es muy teórico y exigente, pero la teoría en general es así, es exigente. Otra cosa es lo que se pueda conseguir en la práctica. En realidad en la práctica no se podrá definir bien a la población, ni se conocerá bien la distribución de la población, con lo que garantizar que la muestra sea representativa puede ser complicado.
¿ Muestra representativa ?.
Realmente tras la redacción de este punto no me ha quedado claro que la extracción de una muestra representativa sea el método más adecuado. Puede serlo, pero puede ser también que una muestra no aleatoria sino diseñada consiga obtener funciones que generalicen. Habrá que ver que piensan los investigadores del sector. En cuaquier caso el tamaño de la muestra tiene que ser eficiente, es decir polinómico con respecto al tamaño del input u o el tamaño de otro parámetro intermedio que dependa de este tamaño. Esto si es clave para la definición de la clase DL-P.
b) Verificación (generalización «comercial»).
La forma más clara de demostrar a uno mismo o a terceras partes de que el sistema generaliza es aplicarlo a toda la población, y para cada elemento de la población comprobar de manera independiente y eficiente que la solución es correcta (aproximadamente correcta). Obviamente esta método de verificación aunque convincente no es eficiente: lo normal es que el tamaño de la población sea exponencial con respecto al tamaño del input. Nos tenemos que conformar con poder extraer muestras eficientes de la población, y para cada elemento de la muestra extraída, poder hacer una comprobación independiente de que la solución que da el sistema es (aproximadamente) correcta.
Repetimos punto punto las tres condiciones de verificación eficiente.
–extracción de una muestra de tamaño eficiente, con respecto al tamaño del input del MLP.
–cada elemento de la muestra tiene que tener un tamaño polinómico con respecto al tamaño del input. Esto puede ser obvio en aplicaciones de imagen, pero pensemos en otras aplicaciones como la traducción: se tienen que seleccionar textos de un tamaño eficiente.
–cada elemento de la muestra se pone a prueba en el sistema Deep Learning diseñado, y se anota el resultado. Esto se tiene que poder hacer de manera eficiente con respecto al tamaño del input, lo cual en principio se da por descontado dado que es una de las especificaciones del sistema a la hora de diseñarlo.
–cada elemento de la muestra se pone a prueba con otro método independiente y también eficiente, con el que se pueda obtener el resultado correcto, y este resultado correcto obtenido se compara con el anterior.
Si los dos resultados (aproximadamente) coinciden en una elevada proporción de casos (proporción que se puede ajustar en función de la aplicación) entonces el resultado de la verificación es concluir que el sistema generaliza.
De nuevo el tipo de muestra que se haga para realizar esta verificación puede variar. Puede ser aleatoria representativa o puede ser de diseño de tipo adversario (es decir seleccionando elementos muestrales que se piense puedan demostrar que el sistema no generaliza). En cualquier caso el tamaño de estas muestras para la verificación y cada uno de los pasos que en ella se realizan tienen que ser eficientes.
Nótese como el hecho de que se pueda verificar de manera eficiente e independiente que la solución del sistema es correcta es una condición de definición de las clases P y NP tradicionales.
Ahora mismo no tengo claro si para definir la clase DL-P debemos de tener en cuenta los dos tipos de generalización o nos podemos ceñir a esta segunda clase de generalización, la de verificación. De momento vamos a optar por esta segunda opción.
c) Generalización en la literatura.
Glosario de términos.
La literatura es extremadamente confusa. Y nosotros hemos añadido más. Para aclarar el tema, un breve glosario:
–Lo que hemos llamado función de ajuste, en ocasiones se llama modelo, en otras hipótesis, en otras predictor y seguramente hay más sinónimos para este concepto.
–lo que hemos llamado optimizar la función de ajuste, a veces se llama entrenamiento (entrenar a la máquina) a veces aprendizaje (aprender un predictor) etc…Para ello se utiliza una muestra de aprendizaje.
–lo que hemos llamado en el punto anterior verificación, generalización y muestra de verificación a veces se llama test, a veces se llama certificación de rendimiento (de la aplicación de Deep Learning), a veces predicción, a veces inferencia etc…En definitiva, se trata de utilizar la función de ajuste optimizada para resolver casos que no estaban en la muestra de entrenamiento.
–La función de pérdida mide la diferencia entre el valor del output real y el obtenido al utilizar la aplicación de deep learning. Pensemos por ejemplo en una aplicación que detecta emails spam. Si el email es spam y la aplicación lo clasifica como spam, el error es cero. Si es spam pero la aplicación lo clasifica como que no es spam el error es 1. Hay muchas maneras de implementar una función de perdida.
–En base a la función de pérdida se puede calcular el riesgo teórico, poblacional, o out-of-sample (fuera de muestra), que es el que se obtendría al aplicar la aplicación a toda la población y el riesgo empírico (ERM) que es el que se obtiene al aplicar la aplicación a solo una muestra.
–Cuando se optimiza la función de ajuste (hipótesis, modelo, predictor etc…) el objetivo es minimizar el ERM.
–el ERM se puede optimizar para la muestra de entrenamiento y para la muestra de verificación (de test o de certificación).
Dos definiciones de generalización.
He visto varias definiciones técnicas diferentes vinculadas al concepto de generalización en la literatura. A veces se del error de generalización o del generalization gap:
–En algunos casos la generalización se define como la diferencia entre el ERM de la muestra de entrenamiento y el ERM de la muestra de verificación.
Haz clic para acceder a method07ho.pdf
–pero en otras ocasiones para definir a la generalización se usa la diferencia entre el riesgo teórico y el riesgo empírico.
https://en.wikipedia.org/wiki/Generalization_error
Machine Learning vs. Statistical learning.
Diría que las diferentes terminologías que hemos mencionado así como la diferencia en la definición de generalización se origina en las comunidades de investigadores de Estadística (Statistical Learning theory) y de Ciencias Computacionales (Machine Learning). Estudian los mismos problemas pero con enfoques a veces muy diferentes, a veces convergentes.
–en la comunidad de investigadores de estadística, se hacen hipótesis sobre la población y por lo tanto tiene sentido hablar de riesgo o error poblacional.
–en la comunidad de investigadores de las ciencias de la computación se asume que se desconoce todo sobre la población y nuestro único conocimiento de ella es a través de las muestras que podamos sacar de la población. Y por lo tanto tiene sentido calcular una diferencia de error entre muestras pero no entre una muestra y una población.
Haz clic para acceder a stastical_learning_theory.pdf
Realmente, en lo fundamental, parece una distinción más bien bizantina y son dos campos que seguramente acabarán convergiendo.
https://www.quora.com/How-is-Statistical-Learning-different-from-Machine-Learning
Haz clic para acceder a MachineLearning.pdf
Una posible definición es Machine Learning = Statistical Learning + Computational Complexity. Es decir, en la medida en la que Statistical Learning, que se deriva de la estadística clásica empieza a utilizar ordenadores para resolver sus problemas y empieza a ser consciente del problema de la eficiencia, tiene que converger con Machine Learning.
En casi todos los documentos en general entran en seguida en todo detalle matemático, no dejando los árboles ver el bosque. Pero en fin, probablemente el tema está (aproximadamente) claro.
Generalización y aplicaciones.
Terminamos con un extracto de un artículo dónde muestran la importancia de la generalización para las aplicaciones:
Generalization, the ability of a classifier to perform well on unseen examples, is a desideratum for
progress towards real-world deployment of deep neural networks in domains such as autonomous
cars and healthcare. Until recently, it was commonly believed that deep networks generalize well
to unseen examples. This was based on empirical evidence about performance on held-out dataset.
However, new research has started to question this assumption. Adversarial examples cause networks
to misclassify even slightly perturbed images at very high rates (Goodfellow et al., 2014; Papernot
et al., 2016). In addition, deep networks can overfit to arbitrarily corrupted data (Zhang et al., 2016),
and they are sensitive to small geometric transformations (Azulay & Weiss, 2018; Engstrom et al.,
2017). These results have led to the important question about how the generalization gap (difference
between train and test accuracy) of a deep network can be predicted using the training data and
network parameters. Since in all of the above cases, the training loss is usually very small, it is clear
that existing losses such as cross-entropy cannot serve that purpose. It has also been shown (e.g. in
Zhang et al. (2016)) that regularizers such as weight decay cannot solve this problem either.
Consequently, a number of recent works (Neyshabur et al., 2017b; Kawaguchi et al., 2017; Bartlett
et al., 2017; Poggio et al., 2017; Arora et al., 2018) have started to address this question, proposing
generalization bounds based on analyses of network complexity or noise stability properties. However,
a thorough empirical assessment of these bounds in terms of how accurately they can predict the
generalization gap across various practical settings is not yet available.
d) Generalización para la población de un problema; problemas estrechos.
Este es otro tema que entra dentro de la fenomenología del Deep Learning actual. Uno de los problemas que tienen los sistemas actuales es que generalizan pero para problemas muy específicos. Por ejemplo un sistema de Deep Learning diseñado para jugar al ajedrez, juego en el que puede llegar a un nivel excelente, superhumano, cuando le pones a jugar a otro juego sin ninguna modificación, está completamente perdido. Si lo que se busca es la Inteligencia Artificial general esto es muy insatisfactorio, pues para que un sistema que ha aprendido a jugar un juego aprenda a jugar otro juego, hay que empezar desde cero. Este tema se sale un poco del tema principal de la entrada y no vamos a profundizar en él.
5. La clase DL-P.
[Advertencia. La clase DL-P es una construcción del que escribe estas líneas. Le ayuda a combinar de manera resumida en un mismo «modelo» todas las consideraciones de complejidad computacional que hemos ido viendo a lo largo de los puntos anteriores de la entrada. No existe como tal en la literatura].
Con todo lo comentado anteriormente ya se puede hacer una primera definición de la clase DL-P.
La clase DL-P o Deep Learning eficiente es la clase de problemas que se pueden resolver por métodos de Deep Learning para los que:
–Red universal eficiente. Se puede construir una MLP universal con un uso eficiente de recursos (el número de neuronas y conexiones entre ellas (pesos) es polinómico o menos con respecto al tamaño del input del MLP)
–Optimización función de ajuste eficiente. Se puede resolver el problema de optimización de la función de ajuste de manera eficiente en función del número de muestras (que a su vez tiene que ser eficiente) y del número de parámetros (que por la condición anterior, ya se impone que es eficiente). No hablamos de eficiencia en la práctica sino teórica (se tiene que poder demostrar matemáticamente que la optimización es eficiente, por ejemplo demostrando que existe un programa lineal polinómico que lo resuelve).
–Verificación de la generalización eficiente. se puede realizar la verificación de la generalización de la manera descrita en el punto anterior, de manera eficiente, lo cual implica una muestra de test eficiente y dada la muestra un método de verificación independiente y eficiente de la corrección.
De alguna manera la definición de la clase DL-P contiene los mismos elementos que la definición de la clase P: algoritmo determinista de solución del problema eficiente (dentro de lo cual podemos meter a las dos primeras condiciones, red y optimización de la función de ajuste) y verificación eficiente.
6. Capacidad de interpretabilidad del sistema: ¿ elementos para la definición de la clase DL-NP ?.
a) Introducción.
La interpretabilidad, interpretability en inglés, a veces se llama explainability. Ver por ejemplo este informe de PWC
Explainable AI: Driving business value through greater understanding.
Haz clic para acceder a explainable-ai.pdf
He de confesarlo. Cuando hace unos días por primera vez sobre interpretabilidad, a la hora de redactar la anterior entrada, pensé que era un tema menor, para-tecnológico, sin importancia con respecto a la tecnología. Quizás importante para temas éticos o de regulación, pero que no formaba parte de las tuercas y tornillos de la tecnología.
Ayer por la noche al meterme en la cama la cabeza me bullía con todas las lecturas realizadas para redactar la entrada anterior, y cristalizó la idea de hacer una entrada muy breve resumiendo esquemáticamente los fundamentos básicos de esta tecnología de Deep Learning (fundamentos que aparecen en los puntos anteriores).
En ese momento, mientras ordenaba ideas en la cabeza, surgió la idea de la clase DL-P, de todos los elementos o condiciones que debían de definir esta clase, pero no tenía ni idea, ni siquiera intención de hablar de una clase DL-NP. Tras redactar la entrada, basada en la clase DL-P me volví a meter en la cama y empecé a reflexionar sobre cuales serían los elementos en los que se podría basar o definir la clase DL-NP. E inmediatamente pensé en el tema de la interpretabilidad. Me volví a levantar para escribir unas líneas sobre esta parte que hemos ido completando en los días siguientes.
Ahora pienso que la interpretabilidad es clave para esta tecnología de Deep Learning, como lo es una verificación eficiente para la computación clásica, aunque ya no pensamos que sea la base para definir una clase DL-NP.
b) Preliminares.
En los puntos anteriores hemos definido la clase de problemas DL-P, que contiene a aquellos problemas de Deep Learning que cumplen con las condiciones indicadas: se puede obtener una solución de manera eficiente y se puede verificar esta de manera eficiente (e independiente).
Ya lo hemos comentado en la introducción: pensamos que la clase DL-NP, el equivalente de la clase NP tradicional se tiene que construir partiendo del problema de la interpretabilidad. Dicho esto, admitimos que este tema es complejo y que esta parte es de momento exploratoria, especulativa. Al terminar este punto es posible que lleguemos a diferentes conclusiones que las que eran punto de partida.
Situaciones en las que la interpretabilidad no importa.
Pensemos en una familia de problemas de computación clásico que el lector quiera resolver y para la que él no tiene solución. No sabe como resolverlos. Viene una tercera parte y te ofrece (intenta vender) una aplicación le da una solución general a esa familia de problemas. Pueden darse dos casos: o bien se puede comprobar rápidamente (de manera eficiente), para todos los casos de la familia, que las soluciones lo son (es decir lo que hemos llamado verificación eficiente), o no se puede.
En el primer caso coges varios casos, los pruebas en la aplicación y compruebas si la solución que te da es correcta y si para todos los casos (o incluso para proporción de ellos que consideres aceptable) que pruebas lo es, entonces concluyes que la aplicación funciona bien y la compras. Si resulta que funciona mal, por debajo de la proporción aceptable, no la compras y punto. Las consecuencias de todo el experimento es que has perdido algo de tiempo y nada más. Hay aplicaciones de deep learning para las que puedes comprobar de manera eficiente si funcionan bien o no muy directamente tu mismo, y la prueba no tiene mayores consecuencias. Por ejemplo, las aplicaciones que etiquetan imágenes. Seleccionas una muestra de imágenes y se las das a la aplicación para que las etiquete (describa verbalmente): puedes comprobar tu mismo si las etiqueta bien o no. Es directo e inmediato.
Hay otros casos en los que el tema no está tan claro, la comprobación no es tan directa. Por ejemplo en una traducción automática. Si no conoces el idioma desde el que se está traduciendo un texto, ¿ como sabes que lo traducido se corresponde con el original ?. En este caso también puedes diseñar un sistema de verificación independiente, pero el tema es menos directo aunque puede ser rápido: contratas a un traductor humano, le das los mismos textos que das al sistema que piensas comprar y si para todos los textos de las muestras que has seleccionado las traducciones (aproximadamente) coinciden, entonces puedes concluir que la aplicación de traducción automática funciona (aproximadamente bien). En este caso el experimento de verificación ha sido posible y ha tenido mayores consecuencias: para comprobar de manera independiente que la aplicación funciona, has tenido que contratar a una tercera persona. Mayores consecuencias pero todavía asumibles si tienes que hacer uso de traducciones con frecuencia. Si la aplicación funciona bien y la compras puedes recuperar el coste de haber contratado un traductor para la verificación independiente, evitando tener que contratar a más traductores en el futuro.
Parece que, siempre y cuando se pueda realizar una verificación eficiente (directa y más o menos inmediata) e independiente de los resultados a los que llega el sistema de Deep Learning, y podamos concluir que para las muestras que hayamos seleccionado funciona (aproximadamente) bien, y el experimento de verificación no tenga consecuencias ni para nosotros ni para terceras partes humanas, nos da igual si el sistema es interpretable o no, nos da igual conocer sus tuercas y tornillos. Si se dan estas condiciones, el problema de la interpretabilidad es irrelevante para que usemos el sistema o no.
¿ En que condiciones, en que tipo de aplicaciones de Deep Learning, surge entonces el problema de la interpretabilidad ?.
La respuesta a esta pregunta es compleja. Para desarrollar este tema, hay que tener en cuenta al menos los siguientes elementos (y para tenerlos en cuenta nos tenemos que salir de consideraciones puramente computacionales):
–la capacidad eficiente e independiente de verificación de resultados por parte del usuario del sistema de Deep Learning (tema que ya hemos analizado antes y que es uno de los elementos que define a la calse DL-P),
–la posibilidad de error en los sistemas de Deep Learning. Por su propio diseño, los sistemas de Deep Learning cometen errores. Es inevitable. Ojo, también los seres humanos y otro tipo de sistemas computacionales los cometen. Esta posibilidad de error es más o menos cuantificable en estos tres casos. Cuando la posibilidad de error se puede cuantificar, pasamos a hablar de probabilidad de error. Este es un dato clave: poder conocer la probabilidad de error del sistema con el que trabajamos. Cuanto menor sea la probabilidad de error, mayor confianza nos ofrecerá el sistema, humano o computacional.
–las consecuencias del error para el o los usuarios, y su irreversibilidad o subsanabilidad. En algunas aplicaciones estas consecuencias son mínimas y subsanables. En otras podrían ser vitales e irreversibles. De poco puede ser útil la verificabilidad en aplicaciones en las que el error no es subsanable una vez se ha producido.
–las consecuencias del error (y su subsanabilidad o irreversibilidad) para las partes que no han tomado parte en la decisión de usar la aplicación. Un sistema de reconocimiento de imágenes, un sistema traductor son sistemas o aplicaciones que un usuario tiene en su ordenador. Los utiliza cuando quiere y si hay consecuencias, son solo para el. Pero hay otras aplicaciones que pueden tener consecuencias no solo para quien las usa sino para terceras partes que no han participado en la decisión de usarlas. Pensemos por ejemplo, en una aplicación bancaria para decidir concesiones de crédito. Afecta al banco, que ha decidido libremente usar la aplicación pero también a los solicitantes del crédito, a clientes del banco. En este caso error es que el sistema de Deep Learning tome una decisión diferente a la que se hubiese tomado de haber sido examinado el expediente por empleado humano del banco. O pensemos en una aplicación de diagnostico médico que pueda utilizar un médico de un servicio público o privado. El resultado afecta más al paciente, que no es el que toma la decisión de usarla que al médico, aunque también a este. Entendemos que en estos dos casos, el problema no es tanto o no solo de verificación eficiente e independiente, ya que esta puede . O pensemos en un vehículo sin conductor que circula por carreteras publicas transportando a individuos que han elegido utilizar este servicio, pero si falla puede tener consecuencias para terceras partes que no han tomado ninguna decisión sobre el uso del sistema.
Como hemos comentado, siempre que se pueda hacer una verificación eficiente (aunque más o menos costosa) e independiente del resultado dado por el sistema de Deep Learning, y el error es subsanable (se puede quedar sin consecuencias) no interviene la interpretabilidad.
Veamos esto en uno de los casos comentados: un cliente del banco que no esté satisfecho con la no concesión de un crédito, puede reclamar que un humano examine su solicitud y este, el hacer esto está realizando una verificación independiente y eficiente del resultado, lo cual en este caso es perfectamente posible. Si la aplicación se ha equivocado, el banco subsana el error y punto. En este caso el cliente no va a pedir que le expliquen como funciona la aplicación, sino que hagan una verificación independiente y rápida (eficiente) de este resultado y que si la aplicación se ha equivocado, subsanen el error. Entonces si combinamos verificación independiente y eficiente con derecho de reclamación del cliente y posibilidad de subsanación, no parece problemático que en este tipo de casos se permita el uso de las aplicaciones de Deep Learning.
Llegados a este punto conviene dar una primera definición de interpretabilidad o explicabilidad.
¿ Que es es la interpretabilidad ?
Si la verificación lo que pretende es determinar, siguiendo un método independiente (y eficiente), que el resultado obtenido por otro método (el de Deep Learning) es una solución correcta para el problema que se pretende resolver, la interpretación / explicación / comprensión, lo que pretende es poder reproducir, de manera independiente también, la manera en que funciona un método, el comportamiento del sistema, como obtiene un determinado resultado, no el resultado en sí. La diferencia está clara: verificación = reproducción independiente de un resultado para un problema; interpretación o explicación o comprensión = reproducción independiente de un método que obtiene un resultado, sea este último resultado correcto o incorrecto en relación al problema que el método quiere resolver. Cuando intentamos reproducir un comportamiento, nos interesa reproducir todo comportamiento, el que da resultados correctos y el que da resultados incorrectos.
¿ Por qué nos puede interesar poder reproducir de manera independiente el comportamiento de un método ?. Hay variados motivos. Pensemos por ejemplo en aplicaciones de Deep Learning que tienen consecuencias graves y no subsanables. Tanto al diseñador del sistema como a terceras partes (que por ejemplo tienen que regular esta tecnología) les puede interesar reproducir como funciona el método para ver si responde bien ante situaciones que puedan tener consecuencias graves y no subsanables. Pero hay muchos otros motivos, que no implican necesariamente que el uso de la aplicación pueda tener consecuencias graves y no subsanables.
Realmente para cualquier aplicación nos puede interesar:
–determinar que obtiene resultados correctos, para el problema para el que se ha diseñado, es la verificación del resultado y se corresponde con lo que hemos llamado verificación (independiente y eficiente).
–determinar la manera en que el sistema obtiene resultados, sean correctos o incorrectos. Determinando esto podemos predecir el comportamiento de la máquina, saber si va a funcionar bien o mal para el problema para el que se ha diseñado. Este es otro tipo de verificación, verificación del método, y es a lo que se llama interpretabilidad, que tiene que ser también independiente y eficiente.
¿ Son los sistemas de Deep Learning interpretables ?
Cuando se programa un sistema de Deep Learning, aunque el programador le va orientando, al final es el propio sistema el que al final «decide» el valor de los parámetros (pesos, sesgos…). PDTE DE DESARROLLAR.
c) Interpretabilidad y complejidad computacional.
Advertencia. En esta parte proponemos una teoría propia (realmente de alto nivel, no 100% aterrizada) sobre la interpretabilidad en sistemas computacionales, especialmente sistemas de Deep Learning. La idea es al menos identificar los elementos (variables) que tienen que aparecer en esta teoría.
Las clases P y NP clásicas están construidas en base al uso de recursos necesarios para resolver un problema y verificar la solución. Son clases relativas a problemas de decisión y con tipo de eficacia determinista y exacta.
Para que un problema esté en la clase P, se exige que el mejor algoritmo determinista posible para resolverlo tenga una cota de uso de recursos polinómica con respecto al tamaño del input. Cuando esto sucede, el algoritmo que se usa para encontrar la solución se puede utilizar por una tercera parte para verificar polinómicamente que esta solución es correcta. Por lo tanto los problemas en P tienen soluciones eficiente y verificaciones eficientes.
Los problemas en la clase NP son aquellos que tienen verificaciones del resultado eficientes y (al día de hoy; uso de recursos polinómico en función del tamaño para verificar que la solución es correcta) pero búsqueda de soluciones ineficientes (los mejores métodos conocidos requieren, en el peor caso, un uso de recursos exponencial). Ojo, es problema abierto que esto problemas no puedan tener algoritmos eficientes. Se piensa (la mayoría de los expertos) que no se da el caso, pero es problema abierto.
Con respecto a los problemas que hoy resuelven los métodos de Deep Learning, antes el problema no era de eficiencia, sino de eficacia. No se habían encontrado métodos computacionales para resolverlos.
Markus Lohrey · Manfred
Schmidt-Schauß
| Algorithm | Classification/Regression | Training | Prediction |
|---|---|---|---|
| Decision Tree | C+R | ||
| Random Forest | C+R |
| Neural Network | C+R | ? |
Nota especulativa. Llevando este tema de la interpretación al terreno de las neurociencias, cosa que ya hemos dicho que no nos gusta, pero nos vamos a saltar la regla muy brevemente, la representación sucinta con acceso limitado a la información del proceso interpretante y capaz de verificar parcialmente parece una especie de conciencia o proto-conciencia. El cerebro es el órgano que produce estados mentales tanto en animales como seres humanos. Solo estos son capaces de describir sus propios estados mentales, y siempre de una manera muy limitada, muy aproximada. Para esto se necesita el lenguaje por supuesto, pero también un modelo de la mente de uno mismo.
Podemos pensar que en un principio los mecanismos del cerebro para producir la mente (estados mentales) eran bastante imperfectos. Y de la misma manera, podemos pensar que las primeras conciencias eran bastante deficientes interpretado estados mentales, tal y como sucede ahora mismo con las interpretaciones de algunos métodos de Inteligencia Artificial. Los métodos de interpretación son tan deficientes que no pueden interpretarse ni siquiera…¡¡ teniendo acceso a toda la red y reproduciendo toda la computación !!. Fin de nota.
II. Evaluación y regulación de las tecnologías del Deep Learning.
En los puntos anteriores hemos presentados los aspectos más teóricos, de interés para «ingenieros» que quieran diseñar este tipo de sistemas. En este punto esbozamos (muy brevemente, pues el tema es amplio y se sale fuera del objetivo principal de la entrada) algunos temas que pueden ser de mayor interés para el ciudadano medio, al que a lo mejor se le ha presentado alguna oportunidad de inversión en este tipo de tecnologías o de una manera o de otra se tiene que relacionar con ellas.
Algunas preguntas que el ciudadano medio se puede plantear con respecto a esta tecnología son:
–me han ofrecido invertir en una startup que desarrolla este tipo de tecnología ¿ debo de invertir ?.
–en mi ciudad ya hay servicios de taxi sin conductor humano ¿ puedo utilizarlos sin riesgo ?
–soy banquero y tengo la oportunidad de utilizar esta tecnología para decidir si concedo créditos o no a ciudadamos medios; utilizarla me permitiría abaratar sustancialmente costes, pero no tengo claro ni como funcionan ni que funcionen bien ¿ debo de utilizarlas ?
etc…
7. Evaluando la tecnología actual de Deep Learning.
Teniendo en cuenta lo que venimos describiendo, ¿ en que punto están los sistemas actuales de Deep Learning ?. ¿ Tenemos ya sistemas de la clase DL-P ?. Sinceramente no lo tengo claro, pero me da la impresión de que lo que tenemos en este momento son sobre todo sistemas bastante deficientes tanto con respecto a aspectos cuantitativos como cualitativos.
En lo cuantitativo son ineficientes por diversos aspectos: optimización heurística (que por otra parte funciona bien en la práctica), cantidad exponencial de muestras con respecto al tamaño del input.
En lo cualitativo, tenemos por un lado el problema de que no se garantiza teóricamente la representatividad de las muestras (la única garantía es empírica) y sistemas no interpretables que por lo tanto no están ni siquiera en la clase DL-NP.
8. Ética y política del Deep Learning: legislación / regulación de esta tecnología.
La tecnología Deep Learning ha causado una cierta alarma social, sobre todo en «círculos intelectuales» de científicos y tecnólogos, que en teoría son los que mejor la puedan conocer. Quizás las reacciones hayan sido exageradas. En cualquier caso de momento las aplicaciones de esta tecnología han sido, más o menos prácticas, pero en general inocuas (reconocimiento de imágenes, traducción automática, ganar en juegos…) pero se quiere (las empresas) que se extiendan a campos más delicados en los que puede haber intereses vitales implicados (condición financiera, trabajo…) e incluso vidas en juego (armamento, temas de salud).
En ocasiones estos sistemas serán una herramienta más cuyas conclusiones el experto podrá aceptar o rechazar, según su criterio. Pero en otras ocasiones (pienso en armamento, sistemas de conducción automática, sistemas de diagnóstico médico etc…) el tema puede ser mucho más delicado y el regulador tiene que decidir al respecto. Algunas de las situaciones en las que se puede ver implicado un regulador o legislador:
–hay empresas de conducción automática de servicios de taxi que me solicitan licencia para poder desarrollar este servicio en la ciudad de la que soy alcalde. ¿ teniendo en cuenta consideraciones exclusivamente de seguridad, debería de concederles la licencia ?.
–hay empresas de sistemas de IA para salud que me ofrecen estos sistemas siendo yo el director del hospital público, el que tiene que decidir. ¿ debo comprar estos sistemas y permitir a los médicos que los utilicen ?.
En fin hay múltiples casos similares de diferentes sectores en los que la aplicación de estas tecnologías puedan ser delicados. Quizás, en base a todo lo que hemos escrito, la única recomendación que se pueda a hacer a los reguladores es que en las aplicaciones delicadas sean exigentes en materia de representatividad y sobre todo en materia de interpretabilidad.
Por otra parte, el tema podría no ser tan nuevo:
–¿ se aprueban medicamentos que funcionan, pero cuyo mecanismo, cuyo motivo por el que funcionan se desconoce ?. Es muy parecido.
–y, ¿ no se aprueba hoy la conducción de todo tipo de vehículos conducidos por humanos que agreden al peatón de múltiples maneras haciendo el paseo por la ciudad hoy en día una actividad de alto riesgo, incluso cuando uno circula por las aceras (perros agresivos y sus agresivos dueños, patinetes de todo tipo y otros nuevos vehículos, también de todo tipo, bicicletas de todo tipo, vendedores ambulantes ilegales huyendo de la policía…y, en tercera dimensión: drones de todo tipo) ?. Esto es muy parecido al problema de la regulación de la conducción automática. Es un nuevo objeto que puede, potencialmente agredir a peatones y otros conductores.
Nota. Según estoy viendo, no hacía falta la recomendación sobre poner el foco en la interpretabilidad a la hora de regular estos temas. Ya se está aplicando este criterio en regulaciones de la UE y de otras instituciones. Fin de nota.
III. Bibliografía.
A continuación los enlaces que hemos encontrado más informativos para redactar esta entrada.
a)Historia del Deep Learning / redes neuronales.
On the Origin of Deep Learning
Carnegie Mellon University
Abstract
Haohan Wang, Bhiksha Raj
This paper is a review of the evolutionary history of deep learning models. It covers from the genesis of neural networks when associationism modeling of the brain is studied, to the models that dominate the last decade of research in deep learning like convolutional neural networks, deep belief networks, and recurrent neural networks. In addition to a review of these models, this paper primarily focuses on the precedents of the models above, examining
how the initial ideas are assembled to construct the early models and how these preliminary models are developed into their current forms. Many of these evolutionary paths last more than half a century and have a diversity of directions. For example, CNN is built on prior knowledge of biological vision system; DBN is evolved from a trade-off of modeling power and computation complexity of graphical models and many nowadays models are neural
counterparts of ancient linear models. This paper reviews these evolutionary paths and offers a concise thought flow of how these models are developed, and aims to provide a thorough background for deep learning. More importantly, along with the path, this paper summarizes the gist behind these milestones and proposes many directions to guide the future research of deep learning.
https://arxiv.org/pdf/1702.07800.pdf
Se pueden ver también estas dos entradas de wikipedia.
Algunos enlaces relevantes:
https://en.wikipedia.org/wiki/Progress_in_artificial_intelligence
https://en.wikipedia.org/wiki/Timeline_of_machine_learning
b)Tutorial / clases sobre Deep Learning. Universalidad y eficiencia por profundidad.
Sin los tutoriales que enlazamos a continuación esta entrada no habría sido posible. Sin duda son la mejor introducción accesible al tema. Me he leído en todo detalle la lección 2 y tengo pendiente de leer la lección 3 y 4. Le dedico la entrada a este profesor / autor / investigador, al que obviamente no conozco y al que obviamente no se pueden achacar los errores que hayamos cometido. Su nombre creo que es Bhiksha Raj.
–Neural Networks: What can a network represent.
Deep Learning, Spring 2018
http://www.cs.cmu.edu/~bhiksha/courses/deeplearning/Spring.2018/www/slides/lec2.universal.pdf
–Neural Networks Learning the network: Part 1
http://www.cs.cmu.edu/~bhiksha/courses/deeplearning/Spring.2018/www/slides/lec3.learning.pdf
–Neural Networks. Learning the network part 2: Backprop
http://www.cs.cmu.edu/~bhiksha/courses/deeplearning/Spring.2018/www/slides/lec4.learning.pdf
Hay más del curso de 2018. Se pueden encontrar en esta página web:
http://www.cs.cmu.edu/~bhiksha/courses/deeplearning/Spring.2018/www/
Este es un campo muy dinámico que se investiga ampliamente por múltiples investigadores, en la industria y en la academia. En un año todo puede ser diferente. Del mismo autor, un curso de 2019 se puede encontrar en
http://www.cs.cmu.edu/~bhiksha/courses/deeplearning/Spring.2019/www/
Relevancia de la profundidad para una representación universal eficiente.
Sobre los circuitos booleanos con puertas de umbral se pueden ver las siguientes entradas de wikipedia.
https://en.wikipedia.org/wiki/TC_(complexity)
https://en.wikipedia.org/wiki/TC0
Y un par de artículos sobre este tema.
Is Depth Needed for Deep Learning? Circuit Complexity in Neural Networks
https://users.cs.duke.edu/~rongge/stoc2018ml/Shamir_depthfordeep_STOC.pdf
Learning Functions: When Is Deep Better Than Shallow
https://arxiv.org/pdf/1603.00988.pdf
b) Bis. Libros sobre Deep Learning.
–2015. Understanding Machine Learning: From Theory to Algorithms.
Si al lector le interesa conocer la teoría y la práctica, este es su libro. No obstante se publicó en 2015 con contenidos de 2014, con lo cual seguramente en algunos temas estará obsoleto, siendo este campo tan dinámico.
–El libro editado por Bengio y colegas. Muy completo pero de enfoque más práctico que teórico. No he visto que incluyan nada sobre complejidad computacional del aprendizaje, que es el tema que ha motivado la entrada.
@book{Goodfellow-et-al-2016,
title={Deep Learning},
author={Ian Goodfellow and Yoshua Bengio and Aaron Courville},
publisher={MIT Press},
note={\url{http://www.deeplearningbook.org}},
year={2016}
}
http://www.deeplearningbook.org/
El libro online sobre este tema editado por Michael Nielsen, de enfoque sobre todo práctico. Pasa muy por encima por temas relacionados con la complejidad computacional, sin mencionar explícitamente este disciplina. Pero es interesante pues se centra en diseñar una red para una aplicación en concreto y por lo tanto el lector no se dispersa.
http://neuralnetworksanddeeplearning.com/index.html
c) Problema de optimización de Deep Learning aproximado por un programa lineal exponencial.
La formulación del problema de optimización de la función de ajuste la he visto en los siguientes artículos.
Versión de 2018.
https://arxiv.org/abs/1810.03218
Versión de 2019.
https://openreview.net/pdf?id=HkMwHsCctm
Uno de los autores habla sobre ellos en su blog
http://www.pokutta.com/blog/research/2018/10/12/DNN-learning-lp-abstract.html
Un muy interesante blog en el que hablan de estos temas de optimización vinculados al Deep Learning. También hablan del problema de generalización y otros. Se publica desde 2015 y se puede leer (hojear) en una tarde.
d) Muestreo representativo eficiente, problema de generalización.
Algunas entradas del blog anterior en las que hablan sobre el problema de generalización:
http://www.offconvex.org/2017/12/08/generalization1/
El artículo que mencionan en la entrada.
Haz clic para acceder a 1611.03530.pdf
Y otra entrada en el blog sobre generalización.
http://www.offconvex.org/2018/02/17/generalization2/
Desde otro punto de vista, un artículo que confieso no he comprendido.
A Probabilistic Theory of Deep Learning
Ankit B. Patel, Tan Nguyen, Richard G. Baraniuk. April 2, 2015
https://arxiv.org/pdf/1504.00641.pdf
e) Teoría de complejidad computacional del aprendizaje.
Haz clic para acceder a thesis.pdf
Haz clic para acceder a d84bc10fa96c65a10c7856f6f9bd1b389700.pdf
f) Problema de interpretabilidad.
Si lo que afirmamos en esta entrada sobre la clase DL-NP es correcto, el problema de interpretabilidad es clave para el futuro de la tecnología, para que pueda ser aceptada por el público en general y por los reguladores, y, aunque la comunidad de investigadores (¿ y el ciudadano medio ?) es plenamente consciente del problema, no se si se está estudiando con toda la intensidad y seriedad debida. Un artículo sobre esto:
Un artículo que trata sobre este tema de la interpretabilidad:
Marzo de 2017. The Mythos of Model Interpretability
Zachary C. Lipton 1
https://arxiv.org/pdf/1606.03490.pdf
Abstract
Supervised machine learning models boast remarkable predictive capabilities. But can you trust your model? Will it work in deployment? What else can it tell you about the world? We want models to be not only good, but interpretable. And yet the task of interpretation appears underspecified. Papers provide diverse and
sometimes non-overlapping motivations for interpretability, and offer myriad notions of what
attributes render models interpretable. Despite this ambiguity, many papers proclaim interpretability axiomatically, absent further explanation. In this paper, we seek to refine the discourse on interpretability. First, we examine the
motivations underlying interest in interpretability, finding them to be diverse and occasionally
discordant. Then, we address model properties and techniques thought to confer interpretability,
identifying transparency to humans and post-hoc explanations as competing notions. Throughout,
we discuss the feasibility and desirability of different notions, and question the oft-made assertions that linear models are interpretable and that deep neural networks are no.
Una presentación que demuestra que sí se investiga este tema con amplia intensidad y desde hace tiempo:
2018. Tutorial on Interpretable Machine Learning
Haz clic para acceder a 2018_MICCAI.pdf
Está claro que la literatura es muy amplia.
El tema de la opacidad y otros similares, desde un punto de vista más periodístico,
https://www.sciencemag.org/news/2018/05/ai-researchers-allege-machine-learning-alchemy
The issue is distinct from AI’s reproducibility problem, in which researchers can’t replicate each other’s results because of inconsistent experimental and publication practices. It also differs from the “black box” or “interpretability” problem in machine learning: the difficulty of explaining how a particular AI has come to its conclusions. As Rahimi puts it, “I’m trying to draw a distinction between a machine learning system that’s a black box and an entire field that’s become a black box.”
f) Generalidades sobre Deep Learning: artículos generales, investigadores principales y algunos vídeos interesantes en los que aparecen.
–Un artículo con una visión general.
Abril 2019. A Selective Overview of Deep Learning.
Abstract.
Deep learning has arguably achieved tremendous success in recent years. In simple words, deep learning uses the composition of many nonlinear functions to model the complex dependency between input features and labels. While neural networks have a long history, recent advances have greatly improved their performance in computer vision, natural language processing, etc. From the statistical and scientific perspective, it is natural to ask: What is deep learning? What are the new characteristics of deep learning, compared with classical methods? What are the theoretical foundations of deep learning? To answer these questions, we introduce common neural network models (e.g., convolutional neural nets, recurrent neural nets, generative adversarial nets) and training techniques (e.g., stochastic gradient descent, dropout, batch normalization) from a statistical point of view. Along the way, we highlight new characteristics of deep learning (including depth and over-parametrization) and explain their practical
and theoretical benefits. We also sample recent results on theories of deep learning, many of which are only suggestive. While a complete understanding of deep learning remains elusive, we hope that our perspectives and discussions serve as a stimulus for new statistical research.
Un par de artículos en los que intentan explicar el «aparente» milagro del Deep Learning. Para ello combinan diversas disciplinas, entre ellas la física.
Junio 2017. Why does deep and cheap learning work so well?∗
Henry W. Lin, Max Tegmark, and David Rolnick.
https://arxiv.org/pdf/1608.08225.pdf
THE POWER OF DEEPER NETWORKS FOR EXPRESSING NATURAL FUNCTIONS.
https://openreview.net/pdf?id=SyProzZAW
Las técnicas de la optimización matemática se aplican para resolver problemas planteados por la tecnología de Deep Learning como el problema de la optimización de la función de ajuste. Pero también se estudia la otra dirección: se intenta aplicar las técnicas de Deep Learning para resolver problemas de optimización matemática. Un par de enlaces al respecto.
Machine Learning for Combinatorial Optimization: a Methodological Tour d’Horizon∗
https://arxiv.org/pdf/1811.06128.pdf
Tres de los principales investigadores de este campo son (por orden de edad) Hinton, LeCun y Bengio. En 2018 fueron por ello premiados con el Premio Turing. A continuación 2 vídeos dónde los tres aparecen hablando sobre el tema en el que son expertos.
–Una entrada en un blog, posterior a la redacción de nuestra entrada en la que tratan sobre algunos de los temas inexplicados / misterios que se encuentran en este campo. Sobre algunos de ellos hemos hablado en la entrada (generalización, optimización, interpretabilidad) pero no sobre otros (rendimiento fuera de distribución, robustez, distribuciones naturales).
g) Enlaces sobre la relación entre circuitos booleanos, circuitos aritméticos,
h) Enlaces solo de interés personal (no para el lector general) encontrados al redactar la entrada:
Ciclo hamiltoniano vs. permanente.
HPC MARKET 
Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.