CAPÍTULO 09/1763–2012

Aprender por sí mismo de los datos

Herramientas reunidas a lo largo de 200 años y 3 lámparas que se encendieron a la vez entre 2006 y 2012

Se muestran muchos ejemplos a una máquina y se deja que encuentre las reglas. Muchas de sus herramientas nacieron de la estadística, la clasificación de abejas, las decisiones de libertad condicional en las prisiones, la investigación sobre transmisión de señales y las pruebas psicológicas. En los 7 años a partir de 2006, las redes neuronales profundas (aprendizaje profundo) se volvieron mucho más potentes porque a esa caja de herramientas se sumaron las GPU y grandes cantidades de datos.

012006 · El inicio del aprendizaje profundo

Se reunieron 3 condiciones

¿Lo nuevo en 2006 fue la idea o las condiciones?

Las redes neuronales con muchas capas no podían aprender bien solo con la retropropagación del error (capítulo 8). En 2006, Hinton y sus colegas presentaron un método para “entrenar redes de creencia profundas y dirigidas, una capa a la vez” (traducción): primero se aprenden las características de los datos sin respuestas correctas (preentrenamiento) y después se ajusta toda la red con retropropagación. La tasa de error con los dígitos manuscritos de MNIST fue del 1.25%.

Un artículo de Science de ese mismo año decía que “era evidente desde la década de 1980 que la retropropagación a través de autocodificadores profundos sería muy eficaz” (traducción). Enumeraba la velocidad de cálculo, la cantidad de datos y la calidad de los valores iniciales de los pesos, y añadía: “Ahora se cumplen las tres condiciones.” (traducción).

En la figura de la derecha se pueden encender y apagar las lámparas de las 3 condiciones y comparar la reconstrucción de imágenes de barras verticales y horizontales. Cuando los valores iniciales de los pesos se fijan mediante preentrenamiento, se aprende sin respuestas correctas, una capa a la vez, y luego se ajusta toda la red con retropropagación (el efecto de las lámparas es un ejemplo creado para este sitio).

Δwij =η(⟨vihj⟩datos − ⟨vihj⟩reconstrucción)
v, h
neuronas de la capa visible (píxeles) y de la capa oculta
w
peso
⟨ ⟩
promedio (se corrige según la diferencia entre los datos y la reconstrucción; es el método de la máquina de Boltzmann restringida)
Lo que se cree saberLo que suele decirse:En 2006, Hinton inventó una idea nueva llamada aprendizaje profundo
Según la fuente original:El propio artículo decía que ya era evidente desde la década de 1980; lo nuevo era, sobre todo, lo que describía así: “Describimos una forma eficaz de inicializar los pesos” (traducción). Ese mismo año, en 2006, Bengio y sus colegas también publicaron un método parecido.

Qué muestra la figura:Lo nuevo en 2006 fue que coincidieran 3 condiciones, la velocidad de cálculo, la cantidad de datos y unos buenos valores iniciales de los pesos, más que la idea de una red profunda.

Error de reconstrucción (disminuye a medida que avanza el aprendizaje)
021763 · 1961 · Bayes

Del resultado a la causa

¿Se puede clasificar el área de un documento solo con palabras que sirven de pista?

El teorema de Bayes permite recalcular qué tan probable es una causa o una hipótesis después de obtener pruebas. El artículo se leyó el 23 de diciembre de 1763 en la Royal Society de Gran Bretaña. Su autor, Bayes, ya había muerto; su amigo Price lo encontró entre sus documentos y lo envió.

En 1961, Maron, de la Corporación RAND, usó esta idea para clasificar resúmenes de artículos en 32 áreas. Supuso que, una vez fijada el área, las palabras aparecían de manera independiente entre sí, y se limitó a multiplicar las probabilidades de cada palabra (hoy se llama Bayes simple o Bayes ingenuo). De 85 resúmenes nuevos que contenían al menos 2 palabras de pista, el área que quedó en primer lugar fue correcta en 44 (51.8%); si se admitían las 3 primeras, lo fue en 68 (80%).

Al pulsar las palabras de pista en la figura de la derecha, las probabilidades de las áreas cambian mediante multiplicaciones (las palabras y probabilidades son un ejemplo creado para este sitio).

P(área | palabras) ∝ P(área) × Π P(palabra | área)
P(A | B)
probabilidad de que ocurra A bajo la condición B
Π
multiplicar las probabilidades de cada palabra
∝
proporcional a (al final se divide para que la suma sea 1)
Lo que se cree saberLo que suele decirse:Bayes ingenuo es un método que cree ingenuamente que las palabras son independientes
Según la fuente original:El propio Maron escribió que la suposición de independencia era claramente incorrecta, pero que la adoptaba para simplificar los cálculos. En el artículo no aparecen ni la palabra naive ni el nombre Bayes.

Qué muestra la figura:Multiplicar las probabilidades de aparición de las palabras en cada campo permite adivinar el campo de un documento a partir de palabras clave. Incluso con la suposición incorrecta de que las palabras son independientes, se obtienen resultados razonables.

031805 · Mínimos cuadrados

Elevar los errores al cuadrado, sumar y minimizar

Cuando los puntos medidos están dispersos, ¿qué recta se “ajusta” mejor?

En 1805, Legendre, en París, publicó el método de mínimos cuadrados en el apéndice de un libro sobre el cálculo de las órbitas de los cometas. Si hay más ecuaciones que incógnitas, no se pueden reducir todos los errores a 0. Por eso escribió que el método más general, preciso y fácil de usar consistía en elevar cada error al cuadrado, sumarlos y elegir los valores que hagan mínima esa suma. También explicó que así los errores se equilibran entre sí y se evita que los errores extremos arrastren el resultado.

En la figura de la derecha, los errores se representan como áreas de cuadrados reales. Al mover los puntos o cambiar la pendiente de la recta (la intersección se ajusta automáticamente), se puede reducir el área total. Al pulsar “Mínimos cuadrados (al fondo del valle)”, se dibuja la recta calculada de una vez mediante la fórmula. Se determinan los números de la fórmula a partir de los datos. Muchos métodos de este capítulo parten de esta forma.

Minimizar S=Σ(yi − (a xi +b))²
a=Σ(xi − x̄)(yi − ȳ) ÷ Σ(xi − x̄)², b= ȳ − a x̄
(xi, yi)
puntos de los datos observados
a, b
pendiente e intersección de la recta
x̄, ȳ
promedios de x e y
Lo que se cree saberLo que suele decirse:Gauss ideó el método de mínimos cuadrados
Según la fuente original:Legendre fue el primero en publicarlo impreso (1805). Gauss escribió en su libro de 1809 que lo usaba desde 1795. Stigler (1981) consideró probable que Gauss hubiera sido el primero, pero no concluyente. En Estados Unidos, Adrain también lo publicó en 1808–1809.

Qué muestra la figura:La recta que se ajusta a puntos dispersos se elige haciendo mínima la suma de los cuadrados de las diferencias.

Suma de errores al cuadrado al cambiar la pendiente a (el fondo del valle corresponde a los mínimos cuadrados)
041838 · 1958 · Curva en S

De una fórmula de población a una de probabilidad

¿Cómo se obtiene una predicción que siempre esté entre 0 y 1?

En 1838, Verhulst, en Bélgica, expresó el crecimiento de la población mediante una fórmula. A la fuerza de crecimiento que duplica la población, mp, le restó un freno np² que se intensifica al aumentar la población. La curva de la solución tiene forma de S y la población se acerca al límite superior m/n. En 1845 llamó logistique a esta curva (sin explicar el motivo).

Más adelante, la misma curva en S se usó para predecir probabilidades. La regresión logística predice, a partir de variables explicativas, la probabilidad de obtener un 1 en datos cuya respuesta es “sí (1)” o “no (0)”. Una recta puede dar predicciones menores que 0 o mayores que 1, pero una curva en S siempre se mantiene entre 0 y 1. En 1958, Cox, de la Universidad de Londres, publicó un artículo sobre regresión para datos de 0 y 1.

En “Población (1838)” de la figura de la derecha se pueden cambiar m y n. En “Sí/no (1958)”, al pulsar “Un paso de aprendizaje”, se observa cómo la curva en S se ajusta a los puntos.

dp/dt=mp − np²
P(y=1)=1 ÷(1+e−(ax+b))
p, m, n
población, fuerza de crecimiento y fuerza del freno
a, b
números determinados mediante aprendizaje
e
aproximadamente 2.718 (base del logaritmo natural)
Lo que se cree saberLo que suele decirse:Cox ideó la regresión logística en 1958
Según la fuente original:En una entrevista de 1994, el propio Cox dijo que no sabía quién había sido el primero y que quizá Cornfield ya lo hubiera hecho. En 1944, Berkson había usado la función logística y creado la palabra .

Qué muestra la figura:La curva en S que describía el crecimiento de la población se utilizó después como fórmula para predecir probabilidades de sí o no entre 0 y 1.

051901 · 1933 · Análisis de componentes principales

¿Qué recta está más cerca de los puntos?

Si tanto x como y tienen errores de medición, ¿cómo se decide qué recta “se ajusta”?

La recta de mínimos cuadrados supone que solo y tiene error y reduce las diferencias verticales. Por eso la recta cambia según se tome como referencia x o y. En 1901, Pearson, en Londres, propuso minimizar la suma de los cuadrados de las distancias perpendiculares desde cada punto hasta la recta. Esa recta pasa por el centro de los puntos y tiene la dirección del eje más largo de la elipse que representa su dispersión.

Al elegir “Los 10 puntos de Pearson” en la figura de la derecha, los 10 puntos corresponden exactamente al ejemplo numérico de su artículo. Al seleccionar “Perpendiculares” y girar la recta, se puede buscar la dirección que minimiza el promedio de los cuadrados de las distancias perpendiculares. La respuesta del artículo es una pendiente de −0.546. La regresión para predecir y a partir de x da −0.5396, y la que predice x a partir de y da −0.5659: las 3 rectas son distintas.

En 1933, Hotelling, de la Universidad de Columbia, llamó (traducción) al procedimiento que extrae, uno tras otro, los componentes que explican la mayor parte de la variación de las puntuaciones de muchas pruebas relacionadas entre sí.

Dirección que minimiza Σ di² =dirección de mayor dispersión de los puntos (primer componente principal)
di
longitud de la perpendicular desde el punto i hasta la recta
elipse de dispersión
elipse que representa la dispersión de los datos
Lo que se cree saberLo que suele decirse:Hotelling ideó el análisis de componentes principales en 1933
Según la fuente original:Pearson ya había mostrado en 1901 que la recta más cercana a los puntos sigue el eje más largo de la dispersión.

Qué muestra la figura:La recta más cercana a los puntos, que minimiza la suma de las distancias perpendiculares al cuadrado, sigue la dirección de mayor dispersión. Es distinta de la recta de regresión que solo considera las diferencias en y.

Dirección de la recta y promedio de los cuadrados de las distancias perpendiculares
061950 · Japón · Cuantificación

Determinar las puntuaciones a partir de los datos

¿Qué puntuación corresponde a respuestas como “se adapta bien, normal, rebelde”?

Cuando terminaba la encuesta de 1948 sobre la capacidad de lectura y escritura de la población japonesa, un especialista en derecho penal consultó a Chikio Hayashi, del Instituto de Matemática Estadística, para hacer más fiables mediante la estadística las decisiones de libertad condicional. Hasta entonces, las personas asignaban a cada respuesta puntuaciones como −2 a 2 y las sumaban.

Hayashi visitó la prisión de Yokohama y observó que tanto los presos ejemplares que se adaptaban bien como los muy rebeldes tendían a reincidir, mientras que los de comportamiento intermedio eran los que menos reincidían. Así llegó a un método que determina a partir de los datos los propios valores numéricos asignados a las respuestas, para separar claramente al grupo que no reincidió del que sí lo hizo (artículo en inglés de 1950).

La figura de la derecha permite comparar las puntuaciones elegidas por personas con las obtenidas a partir de los datos (las cantidades de personas son un ejemplo creado para este sitio).

Elegir las puntuaciones s para maximizar la razón de correlación η²
s
valor numérico asignado a una respuesta (categoría)
η²
proporción de la variación total que explican las diferencias entre grupos (forma de la actual cuantificación de tipo II)
Lo que se cree saberLo que suele decirse:Hayashi creó y nombró los tipos I a IV de cuantificación en ese orden
Según la fuente original:El primero que completó fue el método para predecir la libertad condicional (hoy tipo II). Los números I a IV fueron nombres asignados por el psicólogo social Hiroshi Akuto en 1964 y no corresponden al orden de creación.

Qué muestra la figura:Si las puntuaciones de las respuestas se obtienen de los datos en lugar de fijarlas una persona, se detectan relaciones que no siguen una línea recta, como que las personas del grupo intermedio sean las menos propensas a reincidir.

071951 · 1967 · k vecinos más cercanos

Basta con seguir el ejemplo más cercano

¿Hasta dónde se puede acertar copiando solo el ejemplo conocido más cercano?

El método de los k vecinos más cercanos busca los k datos más próximos al nuevo punto que se quiere clasificar y lo asigna a la clase más frecuente entre ellos. No supone de antemano una forma para la distribución de los datos. En febrero de 1951, Fix y Hodges estudiaron este tipo de regla en un informe de la Escuela de Medicina Aeronáutica de la Fuerza Aérea de Estados Unidos. Mostraron que, si k aumenta con la cantidad de datos n (pero k/n se acerca a 0), el método se aproxima a la clasificación óptima.

En 1967, Cover y Hart, de Stanford, demostraron que, incluso con el método del vecino más cercano (k=1), que sigue un solo punto, si los datos son infinitos la tasa de error no supera el doble del mínimo teórico (error de Bayes). En este sentido, el artículo afirma que la mitad de la información de clasificación contenida en datos infinitos está en el único punto más cercano.

En la figura de la derecha se pueden colocar puntos y cambiar k. Con k=1, todos los datos de entrenamiento se clasifican correctamente, pero aparecen pequeñas islas alrededor de los puntos con ruido.

R* ≤ R ≤ R*(2 − M R* ÷(M − 1))≤ 2R*
R
tasa de error del método del vecino más cercano (con datos infinitos)
R*
error de Bayes (errores que quedan aun conociendo perfectamente la distribución)
M
número de clases
Lo que se cree saberLo que suele decirse:Cover y Hart idearon el método de los k vecinos más cercanos en 1967
Según la fuente original:Los propios autores escribieron que Fix y Hodges parecían haber sido los primeros en formular la regla de vecindad y estudiar sus propiedades. El informe de 1951 no llegó a convertirse en un artículo de revista académica.

Qué muestra la figura:Imitar el ejemplo más cercano puede bastar para acertar. Con k igual a 1 se acierta en todos los datos de entrenamiento, pero se crean pequeñas islas alrededor de los puntos de ruido.

R* y límite superior de R (con 2 clases)
081957 · 1967 · k-means

Separar y mover al promedio

¿Se pueden separar los datos en k grupos sin dar las respuestas correctas?

k-means alterna 2 pasos: (1) asignar cada punto al representante más cercano y (2) mover cada representante al promedio de su grupo. Así reduce la dispersión dentro de los grupos. En cada repetición, la dispersión total disminuye o se mantiene sin cambios.

Varias personas llegaron por separado al mismo tipo de procedimiento. En 1957, Lloyd, de Bell Labs, escribió en un manuscrito que circuló dentro del laboratorio un procedimiento para encontrar las divisiones y representantes que minimizan el error al transmitir voltajes de señales sustituyéndolos por un número fijo de valores representativos (PCM). Apareció en una revista académica unos 25 años después. En 1967, MacQueen, de la Universidad de California en Los Ángeles, llamó k-means a un procedimiento que introduce los puntos de uno en uno en el grupo más cercano y actualiza enseguida el promedio.

En la figura de la derecha se pueden pulsar “Asignar” y “Mover” de forma alternada. Al cambiar las posiciones iniciales de los representantes, el procedimiento puede terminar en otra solución.

W=Σgrupo Σpunto x del grupo ‖x − μgrupo‖²
x, μ
punto y representante (promedio) del grupo
‖ ‖²
distancia al cuadrado
W
dispersión total dentro de los grupos
Lo que se cree saberLo que suele decirse:MacQueen inventó k-means en 1967
Según la fuente original:En el mismo artículo, él citó como antecedentes a Sebestyen (1962), Forgy y Jennrich, y Wallace y Ball. Steinhaus en 1956 y Lloyd en 1957 ya habían presentado la misma idea.

Qué muestra la figura:Alternar entre asignar cada dato al representante más cercano y mover los representantes a la media separa los datos en grupos sin enseñar las respuestas correctas. Según el punto de partida, el método puede terminar en respuestas distintas.

091958 · 1963 · Agrupamiento jerárquico

Unir lo más parecido para formar un árbol

¿Cómo se encuentran grupos en los datos sin fijar cuántos habrá?

En 1958, los entomólogos Sokal y Michener, de la Universidad de Kansas, compararon 97 especies de abejas con 122 características por especie. Primero agruparon las especies parecidas y luego unieron repetidamente los grupos que habían formado, hasta representar el conjunto en un diagrama con forma de árbol (dendrograma).

En 1963, Ward, de un laboratorio de una base de la Fuerza Aérea de Estados Unidos, convirtió esta forma de agrupar en un procedimiento general. Se examinan todas las parejas de grupos existentes y se unen los 2 que mejoran más el número que mide la calidad del agrupamiento (función objetivo). Se repite hasta que queda un solo grupo.

La figura de la derecha reproduce exactamente el ejemplo del artículo de Ward. Si se agrupan las puntuaciones de 10 personas, 2, 6, 5, 6, 2, 2, 2, 0, 0, 0, la suma de las diferencias al cuadrado respecto al promedio es 50.5. Al separarlas en 4 grupos, {0,0,0} {2,2,2,2} {5} {6,6}, es 0. Al pulsar “Unir 2 grupos”, se puede ver crecer el árbol.

Los 2 grupos que se unen=los 2 cuyo agrupamiento produce el menor aumento de ESS (función objetivo de esta figura)
ESS
suma, para todos los grupos, de las diferencias al cuadrado respecto a sus promedios
Lo que se cree saberLo que suele decirse:El método de Ward une los grupos que producen el menor aumento de la suma de diferencias al cuadrado
Según la fuente original:El artículo de 1963 presentó un procedimiento general en el que se puede elegir cualquier función objetivo según la finalidad del estudio. La suma de diferencias al cuadrado era solo uno de los ejemplos.

Qué muestra la figura:Unir primero los elementos más parecidos reúne el conjunto en 1 árbol, llamado dendrograma, sin fijar antes el número de grupos.

101966 · 1975 · Modelos ocultos de Markov

Inferir estados invisibles a partir de símbolos

¿Cómo se reconoce una señal, como la voz, que cambia cada vez incluso para la misma palabra?

En 1966, Baum y Petrie, del Instituto de Análisis de Defensa de Estados Unidos, crearon un modelo matemático en el que estados que no se ven desde fuera cambian según ciertas probabilidades, y cada estado emite símbolos también según probabilidades. Solo a partir de la secuencia de símbolos emitidos se pueden estimar las probabilidades de transición entre estados y de emisión de símbolos. Es el actual modelo oculto de Markov (HMM).

En 1975, Baker usó este mecanismo en el sistema de comprensión del habla DRAGON, y en 1976 Jelinek, de IBM, lo introdujo en el reconocimiento continuo del habla. Se difundió ampliamente en 1989 gracias a una explicación de Rabiner, de AT&T Bell Labs.

En la figura de la derecha cambian los estados invisibles (voz y silencio), pero solo se puede observar el volumen del sonido. A partir de él se estima la secuencia de estados más probable (algoritmo de Viterbi).

Buscar la secuencia que maximiza P(secuencia de estados | secuencia de símbolos)
estados y símbolos
los estados no se ven directamente (voz y silencio); solo se observan los símbolos (volumen del sonido)
Viterbi
método de programación dinámica que avanza conservando solo las rutas más probables hasta ese momento (la misma idea que la comparación mediante programación dinámica del capítulo 5)
Lo que se cree saberLo que suele decirse:La llegada de los modelos ocultos de Markov mejoró de golpe el reconocimiento del habla
Según la fuente original:En los experimentos de Rabiner (1989) con dígitos pronunciados de uno en uno, las tasas de error de HMM y de la comparación de patrones anterior (DTW) eran similares (1.3% frente a 2.0%, y 1.8% frente a 1.1%). Sus ventajas eran la capacidad de representar el mecanismo del sonido y de ampliarse al reconocimiento con vocabularios grandes.

Qué muestra la figura:Los estados ocultos, voz o silencio, cambian según probabilidades, y solo se observa el volumen del sonido. Usar la continuidad entre los momentos anteriores y posteriores permite acertar mejor la secuencia de estados que analizarlos por separado.

111971–2010 · Japón · Elegir modelos

Cómo detectar el sobreajuste

Cuantos más números se ajustan, mejor encajan los datos. ¿Dónde se debe parar?

Cuantos más números ajustables (parámetros) tiene una fórmula, más se adapta a los datos disponibles. Pero tiende a fallar con datos nuevos (sobreajuste). En 1971, Hirotugu Akaike, del Instituto de Matemática Estadística, presentó AIC, un criterio que añade una penalización por la cantidad de parámetros al ajuste a los datos. Cuanto menor, mejor.

En 1974, Stone, en Londres, publicó la validación cruzada: se separan los datos en una parte de entrenamiento y otra de validación, se cambia la forma de dividirlos y se elige el modelo según el resultado promedio. En 1977 mostró que la validación cruzada dejando un dato fuera y AIC se comportan de forma similar cuando hay muchos datos. En 2010, Sumio Watanabe, del Instituto de Tecnología de Tokio, creó WAIC, aplicable a redes neuronales y otros modelos que no cumplen los supuestos de AIC, y demostró que se aproxima al mismo valor que la validación cruzada dejando un dato fuera.

En la figura de la derecha se puede aumentar el grado del polinomio. El error de entrenamiento sigue disminuyendo, pero el error de validación cruzada y AIC empiezan a subir a partir de cierto punto.

AIC= −2 log L̂ +2k
L̂
máxima verosimilitud (probabilidad de los datos con los valores que los hacen más probables)
k
número de parámetros
Lo que se cree saberLo que suele decirse:La A de AIC es la A de Akaike
Según la fuente original:En su artículo de 1974, el propio autor escribió que eligió la A para que después pudieran seguir criterios parecidos, como BIC y DIC. En sus recuerdos de 1981 también explicó que era la abreviatura de an information criterion (un criterio de información). La W de WAIC también significa widely applicable (ampliamente aplicable) en el artículo de Watanabe.

Qué muestra la figura:Aumentar el número de términos de una fórmula mejora el ajuste a los datos disponibles, pero facilita los errores con datos nuevos. AIC y la validación cruzada ayudan a encontrar el equilibrio adecuado.

Error de entrenamiento, error de validación cruzada y AIC según el grado
121977 · Algoritmo EM

Completar lo invisible y recalcular

Si una parte de los datos no se ve, ¿cómo se encuentran los valores más plausibles?

En 1977, Dempster, Laird y Rubin, de Harvard y otras instituciones, presentaron un método general para encontrar parámetros plausibles cuando una parte de los datos no es visible. Alterna un paso E (expectation, esperanza), que calcula el valor esperado de la parte invisible a partir de los valores actuales, y un paso M (maximization, maximización), que recalcula los valores a partir de los datos completados. En cada repetición, la verosimilitud de los datos no disminuye.

El primer ejemplo son datos de 197 animales divididos por un mecanismo genético en 4 tipos: 125, 18, 20 y 34 animales. En la figura de la derecha se puede elegir “Ejemplo de 197 animales” y pulsar alternativamente “E: completar” y “M: recalcular”. En 8 repeticiones, π pasa de 0.5 a estabilizarse en 0.6268214…, los mismos números que en la tabla 1 del artículo. En “2 picos” se separan los puntos mezclados según su pico.

E:x₂ =125 ×(π/4)÷(1/2+π/4)
M:π=(x₂ +34)÷(x₂ +18+20+34)
π
valor que se busca (probabilidad del modelo genético)
x₂
cantidad esperada, entre los 125 animales, de los que pertenecen al segundo grupo invisible
Lo que se cree saberLo que suele decirse:Dempster y sus colegas inventaron EM en 1977
Según la fuente original:Los 3 autores escribieron que ya se había propuesto muchas veces en casos particulares (Hartley en 1958, Baum y sus colegas, entre otros). Su contribución fue reunirlo en una forma general, darle nombre y demostrar que la verosimilitud no disminuye.

Qué muestra la figura:Alternar entre completar las partes ocultas con los valores actuales (E) y recalcular los valores con los datos completados (M) permite acercarse a los valores más verosímiles.

π en cada repetición
131979 · Japón · Binarización de Otsu

Elegir automáticamente el límite entre blanco y negro

Al convertir una imagen en tonos de gris a blanco y negro, ¿cómo se decide el brillo del límite?

Para separar letras u objetos del fondo, se clasifican los píxeles en 2 grupos mediante un nivel de brillo (umbral). En 1979, Nobuyuki Otsu, del Laboratorio Electrotécnico, publicó en inglés un método para determinarlo automáticamente. Al dividir en 2 la distribución de frecuencias del brillo (histograma) mediante un umbral k, se elige el k que maximiza la dispersión entre grupos (varianza entre clases). Esto equivale a minimizar la dispersión dentro de cada grupo.

El cálculo solo utiliza la proporción de píxeles hasta ese nivel de brillo y la suma de sus brillos, por lo que es muy sencillo. Es un método no supervisado, que decide sin ejemplos de respuestas correctas. El artículo mostraba la letra A escrita a máquina con cintas nuevas y viejas, patrones de tela e imágenes de células.

En la figura de la derecha se puede mover el umbral para buscar la cima del pico del gráfico (la imagen es un ejemplo creado para este sitio).

σB²(k)=ω₀ ω₁(μ₀ − μ₁)² → elegir el k que maximiza σB²
ω₀, ω₁
proporción de píxeles en los grupos oscuro y claro
μ₀, μ₁
brillo promedio de cada grupo
Lo que se cree saberLo que suele decirse:La binarización de Otsu es un pequeño truco para convertir imágenes a blanco y negro
Según la fuente original:Otsu la derivó del análisis discriminante y la trató como uno de los problemas básicos del reconocimiento de patrones. La conclusión del artículo también dice que, si se dispone de un histograma, se puede usar para otras clasificaciones no supervisadas.

Qué muestra la figura:El umbral de brillo que separa blanco y negro puede elegirse automáticamente, sin ejemplos correctos, buscando dónde la separación entre los 2 grupos, llamada varianza entre clases, es mayor.

Umbral k y varianza entre clases σB²
141985 · Redes bayesianas

Las pruebas propagan probabilidades por la red

¿Se puede razonar a partir de muchas pistas sin alterar las reglas de la probabilidad?

Muchos sistemas expertos de principios de la década de 1980 (capítulo 6) usaban reglas de cálculo improvisadas para razonar con incertidumbre. En 1982, Pearl, de la Universidad de California, escribió que muchos investigadores de IA aceptaban el mito de que había que alterar al menos algunas reglas de la probabilidad. Propuso un grafo donde los hechos son puntos, las dependencias directas son flechas y su fuerza se expresa con probabilidades condicionales. Mostró que así los puntos podían actualizar correctamente las probabilidades del conjunto intercambiando mensajes breves solo con sus vecinos. En 1985 llamó a esta estructura red bayesiana.

La figura de la derecha es una pequeña red donde “Lluvia” y “Riego” causan “Césped mojado” (las probabilidades son un ejemplo creado para este sitio). Al introducir “El césped estaba mojado”, se vuelven más probables tanto la lluvia como el riego. Pero al introducir también “Había llovido”, la probabilidad de riego disminuye. Una de las causas ya explica el resultado.

P(lluvia | mojado)=P(mojado | lluvia) × P(lluvia) ÷ P(mojado)
P(A | B)
probabilidad de A cuando se conoce B
flecha
dirección de una causa directa hacia su efecto
Lo que se cree saberLo que suele decirse:Las redes bayesianas nacieron como una herramienta estadística para aprender de los datos
Según la fuente original:El informe de Pearl de 1985 tenía por título un modelo de memoria que se activa por sí misma y razona a partir de pruebas, y se presentó en un congreso de ciencias cognitivas. El artículo de 1982 respondía a los cálculos improvisados de los sistemas expertos.

Qué muestra la figura:Si causas y efectos se conectan con flechas, al introducir una evidencia los cambios de probabilidad se transmiten por la red. Cuando una causa explica lo observado, la otra deja de parecer tan probable.

151986 · Árboles de decisión

¿Qué pregunta se hace primero?

¿Cómo se construye un “árbol” que da respuestas mediante una secuencia de preguntas?

Un árbol de decisión organiza preguntas como “¿Qué tiempo hace?” o “¿La humedad es alta?” en una estructura de ramas. Sigue las ramas según las respuestas y da una respuesta al llegar a una hoja. En 1986, Quinlan, en Australia, publicó un procedimiento de construcción llamado ID3. Primero elige la pregunta que aporta más información al separar los datos (ganancia de información, medida en bits) y repite el proceso en cada rama.

Las 14 tarjetas de la figura de la derecha corresponden a las filas de la tabla 1 del artículo. Muestran el número de fila y la respuesta P o N. Al abrir “Detalles: 14 filas de la fuente, árbol completo e información”, se pueden leer también el tiempo, la temperatura, la humedad y el viento del sábado por la mañana. Separar por el tiempo aporta 0.246 bits de información, la mayor cantidad, por lo que el tiempo se convierte en la raíz del árbol. Al pulsar las preguntas se puede hacer crecer el árbol.

Ganancia de información=I(conjunto) − Σ(proporción del grupo separado × I(ese grupo))  I= −p log₂ p − n log₂ n
p, n
proporciones de P y N dentro del grupo
I
cantidad de información necesaria para conocer la respuesta (bits)
Lo que se cree saberLo que suele decirse:Los árboles de decisión nacieron de la investigación en IA (aprendizaje automático)
Según la fuente original:En estadística había otra línea: AID, de Morgan y Sonquist (1963), y CART, de Breiman y sus colegas (1984). CART no aparece en las referencias del artículo de 1986 y las 2 líneas se desarrollaron por separado. El artículo tiene un ejemplo con la misma forma que el de “tiempo y tenis” de los libros de texto, pero no aparece la palabra tenis.

Qué muestra la figura:Un árbol de decisión se construye preguntando primero lo que aporta más información sobre la respuesta y repitiendo el mismo procedimiento en cada rama.

161988 · 1989 · 1994 · Aprendizaje por refuerzo

Aprender de las recompensas

¿Se puede aprender sin recibir respuestas correctas y solo con una “recompensa” de vez en cuando?

El aprendizaje por refuerzo es un aprendizaje automático que adquiere formas de actuar mediante ensayo y error, usando las recompensas como pistas. En 1988, Sutton, de GTE Laboratories, desarrolló la teoría del método TD, que corrige la predicción de hoy según su diferencia con la predicción de mañana, sin esperar al resultado final. En su tesis doctoral de 1989, Watkins presentó el aprendizaje Q, que ajusta poco a poco, con cada ensayo, el valor Q(x, a) de realizar la acción a en el estado x. También demostró que, si se prueba cada acción muchas veces, se aproxima a los mejores valores.

En 1994, Kazuteru Miyazaki, Masayuki Yamamura y Shigenobu Kobayashi, del Instituto de Tecnología de Tokio, investigaron el método profit sharing, que refuerza toda la secuencia de acciones anteriores cuando se obtiene una recompensa. Demostraron las condiciones para no aprender acciones que solo producen rodeos y recibieron el premio al mejor artículo de la Sociedad Japonesa de Inteligencia Artificial.

El laberinto de la figura de la derecha permite aprender el camino hasta el tesoro (recompensa) con aprendizaje Q y con profit sharing.

Q(x, a) ← Q(x, a)+α(r+γ maxb Q(x′, b) − Q(x, a))
r, x′
recompensa recibida y siguiente estado
α, γ
tasa de aprendizaje y factor de descuento de las recompensas futuras (0–1)
Lo que se cree saberLo que suele decirse:Sutton inventó el aprendizaje TD en 1988
Según la fuente original:El propio Sutton escribió que TD ya se usaba en el programa de damas de Samuel (1959, capítulo 3), entre otros, pero no se entendía bien. El aprendizaje Q también nació en la tesis doctoral de 1989, no en el artículo de 1992.

Qué muestra la figura:Incluso sin recibir las respuestas correctas y con una recompensa solo al llegar al tesoro, repetir intentos permite aprender el camino hasta él.

Número de intentos y de pasos hasta llegar al tesoro
171990 · 1995 · 1999 · Boosting

Combinar aprendices débiles según los errores

¿Se pueden reunir métodos apenas mejores que adivinar para construir uno fuerte?

El punto de partida fue una pregunta teórica. ¿Tienen la misma capacidad el aprendizaje débil, apenas mejor que adivinar, y el fuerte, que puede alcanzar tanta precisión como se quiera? En 1990, Schapire, del MIT, demostró que eran equivalentes y presentó un algoritmo para convertir un método débil en uno fuerte. En 1995, Freund y Schapire presentaron AdaBoost. Da más peso a los datos mal clasificados en la ronda anterior para entrenar al siguiente clasificador y, al final, combina sus decisiones mediante una votación ponderada.

En 1999, Friedman, de Stanford, generalizó el boosting de gradiente como un cálculo de optimización que desciende por una pendiente: el siguiente árbol pequeño predice el error (residuo) entre la predicción actual y la respuesta correcta, y sus resultados se suman poco a poco.

Al pulsar “Añadir 1 ronda” en la figura de la derecha, los datos mal clasificados se hacen más grandes y el siguiente límite pasa a clasificarlos.

αt = ½ log((1 − εt) ÷ εt)  peso del ejemplo mal clasificado ← peso × eαt
εt
tasa de error ponderada del clasificador de la ronda t
αt
peso de ese clasificador en la votación
Lo que se cree saberLo que suele decirse:El boosting no produce sobreajuste
Según la fuente original:En una explicación de 2013, el propio Schapire mostró un ejemplo donde el error de prueba seguía disminuyendo después de que el error de entrenamiento llegara a 0 (8.4% en la ronda 5 → 3.1% en la ronda 1000), pero escribió que el boosting también puede producir sobreajuste.

Qué muestra la figura:Incluso clasificadores apenas mejores que el azar se vuelven fuertes si cada uno aprende dando más peso a los datos fallados anteriormente y sus respuestas se combinan por mayoría.

Número de errores de entrenamiento en cada ronda
181992 · Máquinas de vectores de soporte

Maximizar el margen desde el límite

Hay muchas rectas que separan 2 grupos. ¿Cuál es la mejor?

En julio de 1992, Boser, Guyon y Vapnik, que investigaban en AT&T Bell Labs, presentaron un nuevo método de aprendizaje en el congreso COLT '92. Traza el límite entre 2 grupos de modo que la distancia a los puntos más cercanos (margen) sea máxima. El límite depende solo de unos pocos puntos próximos a él; mover los demás no lo cambia.

Además, si se reformula el cálculo para usar solo una función que mide la similitud entre puntos (kernel), el mismo cálculo permite maximizar el margen incluso con límites curvos. Con dígitos manuscritos de correspondencia postal (7300 imágenes de entrenamiento y 2000 de prueba), un kernel polinómico de grado 4 obtuvo una tasa de error del 4.9%, ligeramente menor que la de una red neuronal de 5 capas con los mismos datos (5.1%).

En la figura de la derecha se pueden arrastrar los puntos. Salvo los marcados con un círculo (los que sostienen el límite), moverlos no cambia la recta mientras no entren en la franja del margen.

Maximizar el margen ⇔ minimizar ‖w‖
K(x, x′)=exp(−γ‖x − x′‖²)
w, b
dirección y posición del límite (cada punto cumple yi(w·xi+b) ≥ 1; y representa el grupo con+1 o −1)
K, γ
kernel (similitud entre puntos) y estrechez del alcance de su influencia
Lo que se cree saberLo que suele decirse:Cortes y Vapnik inventaron las máquinas de vectores de soporte en 1995
Según la fuente original:Los 3 investigadores ya habían presentado en 1992 un método de aprendizaje que maximizaba el margen y, mediante kernels, también servía para límites curvos. Ese artículo no usa el término support vector; llama supporting patterns a los puntos que sostienen el límite. Para la idea del kernel cita el método de funciones de potencial de Aizerman y sus colegas (1964).

Qué muestra la figura:El camino más ancho del capítulo 8 solo permitía una frontera recta; manteniendo la idea de maximizar el margen respecto a los puntos más cercanos, reescribir el cálculo con la semejanza entre puntos (el kernel) permite obtener una frontera curva con el mismo cálculo, incluso cuando una recta no separa los datos. De nuevo, la frontera depende solo de unos pocos puntos, los más cercanos a ella.

191995 · 2001 · Bosques aleatorios

Votar entre árboles creados al azar

Un árbol se ajusta demasiado a los datos de entrenamiento. ¿Qué pasa al reunir muchos?

Al hacer crecer mucho un árbol de decisión, puede ajustarse a todos los datos de entrenamiento, pero también memoriza el ruido. En 1995, Ho, de AT&T Bell Labs, mostró que combinar muchos árboles que usan una parte de las características elegida al azar mejora la precisión del reconocimiento de dígitos manuscritos (random decision forests).

En 2001, Breiman, de la Universidad de California en Berkeley, reunió estos métodos en los bosques aleatorios. Se vuelve a seleccionar al azar un conjunto de datos para hacer crecer cada árbol y, en cada ramificación, se elige la mejor división entre características seleccionadas al azar. Al aumentar la cantidad de árboles, la tasa de error se estabiliza en cierto valor. Con aproximadamente un tercio de los datos que no se seleccionaron (out-of-bag) se puede estimar el error sin datos de prueba separados.

Al aumentar la cantidad de árboles en la figura de la derecha, el límite irregular se vuelve más suave.

Respuesta del bosque=votación mayoritaria (respuesta del árbol₁, respuesta del árbol₂, …, respuesta del árbolB)
B
número de árboles
error del bosque
depende de la fuerza (precisión) de cada árbol y de la correlación (similitud) entre los árboles
Lo que se cree saberLo que suele decirse:Breiman ideó por sí solo los bosques aleatorios
Según la fuente original:Ho había presentado en 1995 los random decision forests, de nombre muy parecido. El propio Breiman cita como antecedentes el bagging (1996), el método de Ho y el de Amit y Geman (1997), y los reúne bajo el nombre random forests.

Qué muestra la figura:1 árbol profundo memoriza incluso el ruido, pero reunir muchos árboles creados al azar y votar por mayoría suaviza la frontera y estabiliza la tasa de error.

Número de árboles y tasa de error estimada con out-of-bag
201873 · 1936 · Descomposición en valores singulares

Cualquier tabla se descompone en 3 factores

¿Cómo se representa bien una tabla de números (matriz) con pocos números?

La descomposición en valores singulares (SVD) permite descomponer cualquier matriz en 3 multiplicaciones: girar → estirar o comprimir cada eje → volver a girar. Los factores de estiramiento se llaman valores singulares. Beltrami la publicó por primera vez en 1873, en una revista matemática para estudiantes universitarios italianos. Al año siguiente, en 1874, Jordan la presentó por separado.

Si se conservan solo los valores singulares grandes, se puede aproximar con precisión la tabla original usando pocos números. En 1936, Eckart y Young, de la Universidad de Chicago, resolvieron el problema de encontrar la mejor aproximación matricial de rango bajo, en relación con el análisis de puntuaciones de pruebas psicológicas. La solución consiste en poner a 0 los valores singulares pequeños.

En “Círculo (2×2)” de la figura de la derecha, el círculo se convierte en una elipse al “Girar, estirar, girar”. En “Imagen (24×24)” se reconstruye una imagen representada por una tabla de 24×24 números, conservando solo k valores singulares (la imagen es un ejemplo creado para este sitio).

A=U Σ VT  Ak =σ₁u₁v₁T + … +σkukvkT
U, V
rotaciones (cambios de dirección)
Σ
estiramiento de cada eje (tabla con los valores singulares σ₁ ≥ σ₂ ≥ … en la diagonal)
Ak
aproximación que conserva solo los k valores mayores
Lo que se cree saberLo que suele decirse:Eckart y Young descubrieron el teorema de aproximación (1936)
Según la fuente original:Según Stewart (1992), Schmidt lo había demostrado en 1907 y los 2 lo redescubrieron.

Qué muestra la figura:Cualquier matriz se puede descomponer en 3 operaciones, rotar, estirar y rotar; conservar solo los estiramientos grandes, llamados valores singulares, permite aproximar bien la matriz original con pocos números.

Tamaño de los valores singulares (de mayor a menor)
212006–2009 · Netflix Prize

Aprender de una tabla llena de huecos

¿Se puede predecir qué puntuación dará una persona a una película que no ha visto?

En octubre de 2006, Netflix inició un concurso. El premio era de 1 millón de dólares para quien predijera las puntuaciones de las películas un 10% más precisamente que su propio sistema de recomendaciones. Los datos distribuidos eran más de 100 millones de valoraciones de unas 480,000 personas sobre unas 18,000 películas.

El 11 de diciembre de 2006, Funk, uno de los participantes, publicó todo su método en su blog. Representó las preferencias de cada persona y las características de cada película con 40 números cada una, y predijo la puntuación sumando sus productos. De los aproximadamente 8.5 mil millones de celdas de la tabla, 8.4 mil millones estaban vacías, por lo que no se podía aplicar la descomposición en valores singulares original. Por eso calculó el error solo con las valoraciones conocidas y ajustó los valores poco a poco. Él lo llamó una SVD modificada.

Al pulsar “Seguir aprendiendo” en la figura de la derecha, se completan los huecos (la tabla es un ejemplo creado para este sitio).

Predicción r̂ =pu · qm
pu ← pu +η e qm (qm se actualiza de la misma forma; e=r − r̂)
pu, qm
preferencias de la persona u y características de la película m (conjuntos de números)
r, η
valoración conocida y tasa de aprendizaje
Lo que se cree saberLo que suele decirse:Netflix mejoró sus recomendaciones con el método encontrado en el concurso
Según la fuente original:Según el blog de la empresa (2012), el método ganador no se adoptó porque el esfuerzo no compensaba.

Qué muestra la figura:Representar los gustos de las personas y los rasgos de las películas con pocos números y ajustarlos poco a poco usando solo las valoraciones conocidas permite predecir las casillas vacías de una tabla con muchos huecos.

Número de repeticiones y error con los datos de validación
221770 · 2005 · 2009 · Hay una persona dentro

¿Quién puso las etiquetas correctas?

Cuando “la IA aprendió por sí sola mirando fotos”, ¿de dónde venían las respuestas correctas?

En noviembre de 2005, Amazon lanzó Mechanical Turk, un servicio donde un programa encarga pequeñas tareas a personas y recibe sus resultados. El anuncio llamó (traducción) a hacer que una computadora encargue trabajo a muchas personas y use sus resultados.

En 2009, Li y sus colegas, de la Universidad de Princeton, presentaron ImageNet (3.2 millones de imágenes en ese momento), una colección de fotos para cada grupo de sustantivos de WordNet, que organiza el significado de las palabras en una jerarquía. Las fotos se reunieron con motores de búsqueda y personas de todo el mundo, pagadas por su trabajo en Mechanical Turk, comprobaron una por una si realmente mostraban el objeto; la decisión se tomó con los votos de varias personas (página 4 del artículo). “Hay una persona dentro” no se refiere solo a la máquina de ajedrez de 1770, llamada el Turco.

La figura de la derecha muestra el sistema de votación (la precisión individual es un valor provisional creado para este sitio).

Probabilidad de acierto de la mayoría=Σk>n/2 C(n, k) pk(1 − p)n−k
n
número de personas que comprueban una imagen (impar)
p
probabilidad de acierto individual
C(n, k)
número de combinaciones para elegir k personas entre n
Lo que se cree saberLo que suele decirse:Amazon explica que tomó el nombre de la máquina de ajedrez de 1770 (el Turco)
Según la fuente original:Ni el anuncio de Amazon de 2005 ni la página principal actual consultados por este sitio explican el origen del nombre.

Qué muestra la figura:Las respuestas correctas usadas cuando una IA aprendía de fotos habían sido revisadas imagen por imagen por personas de todo el mundo que trabajaban a cambio de una remuneración, y decididas mediante el voto mayoritario de varias personas.

Número de personas y probabilidad de acierto de la mayoría
232009 · Seguir los datos

Separar entrenamiento y prueba para comprobar

¿Qué gana: un mecanismo elaborado o muchos datos?

En 2009, Halevy, Norvig y Pereira, de Google, escribieron el artículo (traducción). Afirmaron que (traducción) y aconsejaron: (traducción).

Sin embargo, el rendimiento aprendido no se conoce si no se evalúa con datos que no se usaron para aprender. En la figura de la derecha se puede cambiar la cantidad de datos de entrenamiento. Si son pocos, se acierta el 100% de los datos de entrenamiento, pero el porcentaje de aciertos en los de prueba es bajo (sobreajuste).

Exactitud de prueba=número de aciertos entre los ejemplos no usados para aprender ÷ número de esos ejemplos
datos para practicar (entrenamiento)
datos usados para entrenar el modelo
datos de prueba
datos usados solo para comprobar el rendimiento después del aprendizaje

Qué muestra la figura:El rendimiento aprendido solo se conoce al comprobarlo con datos que no se usaron para aprender. Con pocos datos, se puede lograr un 100% en la práctica y fallar en la prueba real.

Tamaño de los datos que aparecen en este capítulo (cada marca multiplica por 10)
242006 · 2009 · GPU

Muchos cálculos iguales al mismo tiempo

¿Por qué una pieza que dibuja imágenes de videojuegos aceleró el aprendizaje de la IA?

La GPU, una pieza que dibuja imágenes de videojuegos, puede realizar el mismo cálculo simultáneamente en muchos núcleos pequeños (hasta 128 en la GeForce 8800 GTX de 2006). En noviembre de 2006, NVIDIA anunció CUDA, un sistema para usar esta pieza con el lenguaje C habitual en cálculos distintos de los gráficos.

La mayor parte del entrenamiento de redes neuronales repite la operación “multiplicar y sumar”. Como todos son cálculos de la misma forma, se pueden repartir y ejecutar a la vez. En 2009, Raina, Madhavan y Ng, de Stanford, entrenaron una red profunda sin respuestas correctas en una GeForce GTX 280, hasta 70 veces más rápido que en una CPU de 2 núcleos. El entrenamiento de una red de 4 capas con 100 millones de parámetros pasó (traducción).

La figura de la derecha muestra una competencia para completar las celdas de una tabla de multiplicaciones cambiando el número de núcleos (esquema creado para este sitio). Cuantos más núcleos, más celdas se completan en el mismo tiempo.

Tiempo necesario ≒ número de cálculos ÷ (número de núcleos × velocidad de un núcleo)
supuestos de la figura
cada celda requiere el mismo trabajo y el esfuerzo para repartirlo es 0 (en la realidad también hace falta tiempo para transportar datos, entre otras cosas)
Lo que se cree saberLo que suele decirse:El aprendizaje profundo se extendió gracias a las GPU
Según la fuente original:El gran proyecto de Google de 2012 (artículo del gato y DistBelief) usó miles de computadoras comunes en lugar de GPU. El artículo decía que las GPU de entonces difícilmente aceleraban modelos grandes que no cabían en su memoria (menos de 6 GB). No había un solo camino.

Qué muestra la figura:El aprendizaje de una red neuronal reúne muchísimos cálculos del mismo tipo, por lo que repartirlos entre los numerosos núcleos pequeños de una GPU lo acelera mucho.

252009–2012 · Voz

La voz antes que las imágenes

¿El primer gran éxito de la IA con aprendizaje profundo fue con imágenes?

Desde alrededor de 2009, el aprendizaje profundo empezó a superar, en el reconocimiento del habla, al método estadístico usado durante mucho tiempo (GMM). En 2012, 4 grupos —Universidad de Toronto, Microsoft Research, Google e IBM— publicaron un artículo que (traducción). Mostraron, entre otros resultados, una reducción de la tasa de error de palabras del 27.4% al 18.5% en una prueba de transcripción de conversaciones. En agosto de 2012, Google ya lo había adoptado para el reconocimiento del habla de Android. Todo esto ocurrió antes del concurso de imágenes de octubre de 2012.

Por la misma época aparecieron muchas aplicaciones que recibían pedidos por voz: VoiceTra de NICT en agosto de 2010, Siri de Apple en octubre de 2011 y Shabette Concier de NTT Docomo el 1 de marzo de 2012. La versión japonesa de Siri llegó 1 semana después.

La figura de la derecha muestra cómo se cuentan los errores del reconocimiento del habla (tasa de error de palabras).

Tasa de error= (sustituciones+omisiones+inserciones) ÷ número de palabras de la respuesta correcta
forma de contar
se alinean las 2 frases con el menor número de correcciones y se cuentan (programación dinámica, la misma idea que la comparación mediante programación dinámica del capítulo 5)
Lo que se cree saberLo que suele decirse:El primer gran éxito del aprendizaje profundo fue el concurso de imágenes del otoño de 2012
Según la fuente original:En el reconocimiento del habla, los resultados comenzaron en 2009 y Google lo adoptó para Android en agosto de 2012. Su blog citaba, como primer intento de usar redes neuronales para la voz, un artículo de finales de la década de 1980 (con 2 investigadores de ATR, en Osaka, como coautores).

Qué muestra la figura:El primer gran éxito del aprendizaje profundo fue la voz, antes que las imágenes. Los errores de reconocimiento de voz se cuentan alineando 2 textos con el menor número de correcciones posible.

262010–2012 · Redes profundas

Evitar que la señal desaparezca al apilar muchas capas

¿Qué ocurre al apilar 30 capas?

En las redes neuronales profundas, la señal que propaga el error hacia atrás se debilita o crece demasiado al atravesar cada capa. Entre 2010 y 2012 se reunieron 3 recursos para evitarlo.

La función de activación ReLU (si la entrada es positiva, pasa sin cambios; si es negativa, se convierte en 0; en el lado positivo la pendiente siempre es 1). Un intervalo de pesos iniciales ajustado al número de neuronas (Glorot y Bengio, 2010). Y dropout (2012), que desactiva al azar la mitad de las neuronas de la capa oculta en cada paso de aprendizaje.

En la figura de la derecha se pueden cambiar la función de activación y los valores iniciales para observar la magnitud de la señal en cada capa.

ReLU(x)=max(0, x)
intervalo de los pesos ±√6 ÷ √(nentrada +nsalida), desviación estándar √(2 ÷ nentrada)
nentrada, nsalida
número de neuronas de entrada y salida de la capa (el intervalo corresponde al método de Glorot y Bengio; la desviación estándar, al de He y sus colegas)
Lo que se cree saberLo que suele decirse:Hinton y sus colegas inventaron ReLU en 2010
Según la fuente original:El propio artículo de 2010 cita el intento de Jarrett y sus colegas de 2009. Una función de activación de la misma forma aparece en la red de Kunihiko Fukushima de 1968–1969 (capítulo 4), pero los 3 artículos de 2010–2012 no citan a Fukushima.

Qué muestra la figura:Al añadir muchas capas, la señal que se transmite hacia atrás se debilita en cada una hasta desaparecer. ReLU y una mejor elección de los pesos iniciales permitieron que llegara incluso a través de 30 capas.

Magnitud de la señal retropropagada en cada capa (cada marca multiplica por 10)
272012 · 3 resultados en un año

Señales de tráfico y el gato de Google

¿Cuántos resultados produjo el aprendizaje profundo en 2012?

En febrero, Cireşan, Meier y Schmidhuber, del laboratorio suizo IDSIA, entrenaron con GPU un método que combina varias redes convolucionales profundas y promedia sus resultados. Lograron una tasa de error del 0.54% al identificar señales de tráfico alemanas (12,569 imágenes de prueba). Según el artículo, la tasa de error humana era el doble. Pero solo había 43 respuestas posibles, por lo que la dificultad era distinta a la de fotos con 1000 categorías.

En junio, Le, Ng y sus colegas, de Google y Stanford, extrajeron una imagen de cada uno de 10 millones de videos de YouTube y las usaron para entrenar, sin etiquetas correctas, una red de 9 capas con 1,000 millones de conexiones (3 días en 1000 computadoras con 16,000 núcleos). Sin que nadie se lo enseñara, aparecieron neuronas que respondían a rostros humanos, y también a caras de gatos y cuerpos humanos. El blog de Google insistió en que (traducción).

En octubre llegó el concurso de reconocimiento de imágenes (la siguiente sección). La figura de la derecha permite comparar el resultado de la neurona del gato con el de “Responder al azar”.

Tabla 1 del artículo: neurona de rostros humanos, 81.7%; neurona de caras de gatos, 74.8%; respuestas al azar, 64.8% (prueba del gato). Los resultados se deben comparar con la puntuación que se obtiene sin hacer nada.

Lo que se cree saberLo que suele decirse:La IA de Google aprendió por sí sola a identificar gatos
Según la fuente original:El resultado central del artículo es la neurona de rostros humanos (81.7%); la de caras de gatos alcanzó el 74.8%. Era una prueba donde responder al azar ya daba un 64.8% (tabla 1 del artículo).

Qué muestra la figura:En 2012 se sucedieron resultados de aprendizaje profundo: la neurona de gatos de Google obtuvo un 74.8% en una prueba donde responder al azar ya daba un 64.8%. El rendimiento se interpreta comparándolo con la puntuación que se puede obtener sin hacer nada.

282012 · Concurso de imágenes

Gran ventaja del ganador; Tokio fue segundo

¿Qué ocurrió en el concurso de imágenes de octubre de 2012 para que se afirmara (traducción)?

En ILSVRC, un concurso para identificar 1000 tipos de objetos en fotografías, SuperVision, el equipo de Krizhevsky, Sutskever y Hinton, de la Universidad de Toronto, consiguió una tasa de error del 15.3% con la regla que permitía 5 respuestas (16.4% usando solo los datos proporcionados por el concurso). El equipo de la Universidad de Tokio (ISI), que quedó segundo, obtuvo el 26.2%: una diferencia de unos 11 puntos. Entrenaron una red neuronal convolucional de 8 capas con 60 millones de parámetros en 2 GPU para videojuegos. Los organizadores describieron lo que ese año significó para la investigación del reconocimiento de muchos tipos de objetos: (traducción).

La convolución es un cálculo que desliza una pequeña ventana (filtro) sobre una imagen y responde con fuerza donde aparece la misma forma que en la ventana. Su estructura procede del Neocognitron de Kunihiko Fukushima de 1979 (capítulo 5) y de la red de LeCun y sus colegas de 1989. En la figura de la derecha se puede elegir la forma de la ventana y deslizarla sobre la imagen. El gráfico inferior muestra las tasas de error del primer puesto del concurso durante 8 años.

salida(i, j)=Σa Σb ventana(a, b) × imagen(i+a, j+b)
ventana
tabla de pesos de 3×3 (al aprender, adopta formas que responden a líneas verticales, horizontales, etc.)
Lo que se cree saberLo que suele decirse:El aprendizaje profundo nació de repente en 2012
Según la fuente original:El sistema ganador era la red de LeCun y sus colegas de 1989 (basada en el Neocognitron de Fukushima de 1979), ampliada y entrenada con GPU. El propio artículo dice que (traducción).

Qué muestra la figura:En el concurso de imágenes de 2012, una red convolucional ganó por una gran diferencia de unos 11 puntos sobre el segundo puesto. Su mecanismo era el cálculo de deslizar una ventana pequeña, desarrollado desde 1979 y 1989.

Tasa de error del primer puesto del concurso (2010–2017)
292005–2012 · Japón · Shogi y damas

Aprender de partidas y votar las jugadas

¿La fuerza de un programa de shogi depende de lo bien que juegue su creador?

En la mayoría de los programas de shogi anteriores, sus creadores decidían manualmente cómo puntuar si una posición era buena o mala. Bonanza (publicado en 2005), creado por el investigador de química Kunihito Hoki, hizo que la máquina aprendiera a puntuar para elegir las mismas jugadas que en los registros de partidas profesionales. En mayo de 2006 ganó el Campeonato Mundial de Shogi por Computadora en su primera participación. En marzo de 2007 jugó una partida pública contra Akira Watanabe, titular del título Ryuo (Watanabe ganó en 112 jugadas).

En octubre de 2010, “Akara 2010” (traducción), de la Sociedad de Procesamiento de Información de Japón, venció a Ichiyo Shimizu, titular del título femenino Osho. Hacía que los 4 mejores programas japoneses analizaran la misma posición y elegía por mayoría la jugada más votada. En la primera competición Shogi Den'o-sen, en enero de 2012, Bonkras, basado en Bonanza, venció en 113 jugadas a Kunio Yonenaga, profesional retirado, presidente de la Asociación Japonesa de Shogi y titular vitalicio del título Kisei.

La figura de la derecha muestra un método que actualiza los pesos para que la jugada profesional tenga la puntuación más alta (esquema creado para este sitio).

w ← w+η(f(jugada profesional) − f(m))
m
jugada que ha obtenido una puntuación mayor que la profesional
w, η
pesos de la puntuación y tasa de aprendizaje
f
características de la posición después de jugar (ganancia de piezas, protección del rey y actividad de las piezas)
Lo que se cree saberLo que suele decirse:Para crear un programa de shogi fuerte, su creador también debe jugar bien
Según la fuente original:El autor de Bonanza era un investigador de química que apenas conocía el shogi, pero ganó el campeonato mundial en su primera participación haciendo que la máquina aprendiera a puntuar a partir de registros de partidas.

Qué muestra la figura:Si se deja de fijar a mano la puntuación del programa de shogi y se hace que aprenda a dar la puntuación más alta a la misma jugada que elegiría un profesional, el programa mejora aunque su creador no sepa mucho de shogi.

Número de rondas de aprendizaje y proporción de jugadas iguales a las profesionales
302001 · 2011 · Japón · Predicciones

Metas con fecha y previsiones del mercado

¿Qué metas de “para este año” se anunciaban en Japón en esa época?

En noviembre de 2011, el Instituto Nacional de Informática inició (traducción), el proyecto Todai Robot. Buscaba integrar la investigación en IA, dividida en áreas cada vez más pequeñas desde 1980, y dar un sueño a los jóvenes. Como indicadores concretos fijó metas con fecha: (traducción) y (traducción) (la comparación con los resultados aparece en el capítulo 10).

10 años antes, en 2001, un informe de una asociación industrial japonesa del sector de maquinaria y robótica pronosticó un mercado de robots de unos 3 billones de yenes en 2010 (1.5 billones en el ámbito de la vida cotidiana) y unos 8 billones en 2025. Sin embargo, el mercado real de robots de nueva generación fuera de la fabricación era de 1.4–6.8 mil millones de yenes al año: no llegaba ni a 10 mil millones y, de hecho, disminuía (análisis de Hirohiko Arai, del Instituto Nacional de Ciencia y Tecnología Industrial Avanzada, 2009). Incluso la estrategia del gobierno de 2015 describía el mercado completo de robots como (traducción).

La figura de la derecha coloca las previsiones y los valores reales en una escala donde cada marca multiplica por 10.

Previsión ÷ valor real=cuántas veces difieren
escala de factores de 10
1 → 10 → 100 se sitúan a intervalos iguales (la distancia entre 2 puntos representa cuántas veces difieren)
Lo que se cree saberLo que suele decirse: (traducción) (opinión habitual entre investigadores de robótica)
Según la fuente original:La encuesta de la propia asociación industrial mostró un mercado de robots de nueva generación de solo 1.4–6.8 mil millones de yenes al año, que además disminuía (promedio anual de −10.2%).

Qué muestra la figura:En Japón, durante esta época, se publicaron previsiones y metas para años concretos. La previsión del mercado de robots se apartó de la realidad por un factor de varios cientos o más.

Para terminar

Las herramientas eran antiguas; reunirlas fue lo nuevo

Muchas herramientas para aprender de los datos son anteriores al término IA. Bayes (1763), mínimos cuadrados (1805), curva en S (1838), descomposición en valores singulares (1873), componentes principales (1901 y 1933). Muchas herramientas posteriores también surgieron de problemas fuera de la IA: clasificación de abejas, predicción de libertad condicional, investigación sobre transmisión de señales, pruebas psicológicas y preguntas sobre el comportamiento animal. Además, varias personas llegaron por separado a los mismos métodos. La pregunta “quién fue el primero” rara vez tiene como respuesta una sola persona.

Entre 2006 y 2012, lo nuevo fueron las condiciones más que las ideas: cálculo rápido con GPU, grandes cantidades de datos etiquetados por muchas personas y buenos pesos iniciales y funciones de activación. En 2012, al reunirse estos recursos, el aprendizaje profundo produjo resultados sucesivos en voz, señales de tráfico, gatos y el concurso de imágenes.

Todavía hay muchas cosas que no se saben. ¿Cuántas personas etiquetaron ImageNet, en qué países y por cuánto dinero? ¿Qué ocurre dentro de una red entrenada (los intentos de estudiarla desde fuera apenas habían comenzado)? ¿Por qué HMM y Bayes simple funcionan bien aunque traten como independientes cosas que no lo son? ¿Por qué en el boosting sigue mejorando el resultado de prueba después de que el error de entrenamiento llegue a 0? ¿Por qué es mejor apilar más capas? Ninguna de estas preguntas tiene una respuesta clara en las fuentes de este capítulo. En el siguiente, después de 2012, la IA vence a profesionales en go y shogi, se comprueban los resultados del Todai Robot y la previsión de que “desaparecerán los empleos” se convierte en tema de debate en todo el mundo.

Otros acontecimientos de este capítulo (1; todos con fuentes originales y grados de certeza)
2006Verificado en la fuente originalLas fuentes discrepan

Los 2 artículos que dieron origen a la , que fortaleció los programas de go

En go hay muchas jugadas posibles en cada posición y es difícil evaluar las posiciones. Por eso, los métodos de búsqueda como los del ajedrez no producían programas fuertes. En 2006, un artículo del francés Rémi Coulom presentó un nuevo método, la búsqueda en árbol de Monte Carlo (MCTS). Consiste en jugar al azar repetidamente desde una posición hasta el final (Monte Carlo), comparar las jugadas por su proporción de victorias y explorar más profundamente las ramas prometedoras. Coulom ganó un torneo de go por computadora (KGS) con Crazy Stone, su programa para tableros de 9×9. Ese mismo año, Levente Kocsis y Csaba Szepesvári, de Hungría, propusieron UCT, un método para decidir cuánto explorar cada rama. Diez años después, el artículo de AlphaGo (2016) citó ambos trabajos como referencias de MCTS y combinó MCTS con 2 redes neuronales (predicción de la siguiente jugada y evaluación de la posición).

3 fuentes originales y cómo se verificaron

Discrepancias entre las fuentes:Número de edición de la conferencia del artículo de Kocsis y Szepesvári: la bibliografía de AlphaGo indica “15th European Conference on Machine Learning”. En cambio, el registro de Springer describe ECML 2006 como la 17.ª edición (solo se comprobó en resultados de búsqueda; no se abrió la fuente original). No se ha resuelto cuál es correcto.

  1. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search (CG 2006; PDF del sitio del autor) (Rémi Coulom · 2006 · Página 1 del PDF Abstract / 5 Game Results (página 8 del PDF) / 6 Conclusion… · Fuente original)
  2. Bandit based Monte-Carlo Planning (ECML 2006; PDF de la página universitaria del autor) (Levente Kocsis, Csaba Szepesvári · 2006 · Página 1 del PDF Abstract / 1 Introduction · Fuente original)
  3. Mastering the game of Go with deep neural networks and tree search (Nature 529; PDF alojado por DeepMind) (David Silver, Aja Huang y otros (Google DeepMind, Google) · 2016 · Página 1 del PDF Resumen y primera página del texto; rivales comparados en l… · Fuente original)