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.
¿Por qué una capa a la vez?
Al entrenar una red profunda con retropropagación desde valores iniciales aleatorios, la señal que viaja hacia atrás tiende a debilitarse al atravesar cada capa, o la red puede estabilizarse en una solución poco buena. Si se parte de pesos que ya captaron las características de los datos, una capa a la vez, el ajuste de toda la red funciona mejor.
Más adelante se descubrió que, mejorando la elección de los pesos iniciales y las funciones de activación (ReLU), se podía aprender sin preentrenamiento (la sección de este capítulo “Evitar que la señal desaparezca al apilar muchas capas”).
Fuentes originales y grado de certeza (1)Se reunieron 3 condiciones
28 de julio de 2006Verificado en la fuente original
Hinton y sus colegas presentan un método descrito como “entrenar redes de creencia profundas y dirigidas, una capa a la vez” (traducción). Se describe como
Las redes neuronales con muchas capas no aprendían bien solo con retropropagación. Hinton y sus colegas mostraron un método que primero entrenaba cada capa sin respuestas correctas (preentrenamiento), descrito como , y después ajustaba toda la red con retropropagación. Obtuvo un error del 1.25% en los dígitos manuscritos de MNIST (artículo de Neural Computation), y también superó los métodos anteriores al representar imágenes y documentos con pocos números (artículo de Science).
Lo que suele decirse:Se suele decir que “en 2006 Hinton inventó la nueva idea del aprendizaje profundo” Según la fuente original:El propio artículo de Science afirma 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) para representar datos con pocos valores numéricos. Para ello se necesitaban computadoras suficientemente rápidas, suficientes datos y pesos iniciales suficientemente cercanos a una buena solución, y el artículo señala: “Ahora se cumplen las tres condiciones.” (traducción). La principal novedad era lo que describe como “Describimos una forma eficaz de inicializar los pesos” (traducción). Bengio y sus colegas presentaron un método similar también en 2006 (referencia 34 de la explicación del Comité Nobel).
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)
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_rbm_layer.py
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).
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.
Resultados de entrenamiento y de prueba
Maron contó las palabras en 260 de los 405 resúmenes de 1959 (90 palabras de pista) y reservó 145, sin verlos en absoluto durante la preparación, para las pruebas. Según las cifras del artículo, el porcentaje de aciertos en primer lugar fue del 84.6% en los documentos de entrenamiento y del 51.8% en los nuevos. Si se mide el rendimiento solo con los datos usados para aprender, se lo sobreestima. Esta idea de “separar los datos para comprobar” reaparece muchas veces hasta el final del capítulo.
Fuentes originales y grado de certeza (2)Del resultado a la causa
23 de diciembre de 1763Verificado en la fuente original
El ensayo de Bayes ── en 1763, su amigo Price encuentra el manuscrito póstumo y lo envía a la Royal Society
El teorema de Bayes permite volver a calcular cuán probable es una causa o hipótesis después de observar un resultado (evidencia). Es la base de la clasificación bayesiana ingenua. El 23 de diciembre de 1763 se leyó ante la Royal Society un ensayo presentado como una carta de Price a John Canton, miembro de la sociedad. Era An Essay towards solving a Problem in the Doctrine of Chances (Ensayo para resolver un problema de la teoría de las probabilidades), que Price había encontrado entre los papeles de su difunto amigo Bayes, y se publicó en el volumen 53 de Philosophical Transactions (a partir de la página 370). Según la carta de Price, Bayes pretendía encontrar un método para determinar la probabilidad de un suceso cuando solo se sabe cuántas veces ha ocurrido y cuántas no, sin disponer de ninguna otra información.
Lo que suele decirse:Suele decirse que “Bayes publicó el teorema de Bayes en 1763” Según la fuente original:Bayes ya había fallecido (el título dice the late, es decir, “difunto”). Fue su amigo Price quien encontró el ensayo entre sus papeles, lo envió a la Royal Society y lo dio a conocer.
Clasificación de documentos con Bayes ingenuo: en 1961, Maron experimenta con predecir el área de los artículos a partir de palabras clave. Él mismo decía que la suposición de independencia entre palabras era incorrecta
La clasificación de Bayes ingenuo, o naïve Bayes, usa el teorema de Bayes para calcular la probabilidad de que un documento pertenezca a cada área a partir de las palabras que contiene, y lo asigna al área más probable. Supone que, una vez fijada el área, las palabras aparecen de forma independiente, lo que permite calcular multiplicando las probabilidades de cada palabra. En su artículo de 1961 (Automatic Indexing: An Experimental Inquiry), M. E. Maron, de The RAND Corporation, experimentó con 405 resúmenes de 1959 de la revista IRE Transactions on Electronic Computers. Usó los 260 de marzo y junio como datos de entrenamiento para contar las relaciones entre palabras y áreas. Dejó sin examinar los 145 de septiembre durante la preparación y los usó después como datos de prueba. Había 32 áreas y 90 palabras clave. De los 85 resúmenes de prueba que contenían al menos 2 palabras clave, el área más probable fue correcta en 44 (51.8%); en 68 (80%), el área correcta estuvo entre las 3 más probables.
Lo que suele decirse:Suele pensarse que “Bayes ingenuo es un método que cree ingenuamente que las palabras no tienen relación entre sí” Según la fuente original:El propio Maron escribió en su artículo de 1961 que la independencia entre palabras era claramente una suposición incorrecta, pero que la usaba para facilitar los cálculos, aunque redujera la precisión. Era un atajo elegido a sabiendas. El artículo no parece contener ni la palabra naive ni el nombre Bayes; llama a ese cálculo razonamiento que va de la evidencia a las hipótesis.
Lo que aún no se sabe:El experimento de 1961 separó los datos de entrenamiento de los de prueba: los 145 resúmenes de prueba no se examinaron durante la preparación. Las cifras del artículo también muestran que la precisión en documentos nuevos, 51.8%, era mucho menor que en los documentos usados para entrenar: 84.6% de aciertos en el área más probable.
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.
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_naive_bayes.py
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.
La disputa de prioridad más famosa
Stigler (1981) la llamó la disputa más famosa por la prioridad de un descubrimiento en la historia de la estadística. En recuerdos posteriores, Gauss a veces indicó 1794, por lo que incluso el año varía.
Fuentes originales y grado de certeza (1)Elevar los errores al cuadrado, sumar y minimizar
1805–1809Verificado en la fuente originalLas fuentes discrepan
Mínimos cuadrados ── Legendre los publica en el apéndice de un libro en 1805; en 1809, Gauss afirma que los usaba desde 1795 (la disputa de prioridad más famosa de la historia de la estadística)
El método de los mínimos cuadrados eleva al cuadrado cada error entre un valor medido y el calculado con una fórmula, suma esos cuadrados y elige las constantes de la fórmula (en una recta, la pendiente y la intersección con el eje) para que la suma sea lo más pequeña posible. En 1805, Legendre (A. M. Legendre) escribió en el apéndice Sur la Méthode des moindres quarrés (Sobre el método de los mínimos cuadrados) de su libro sobre las órbitas de los cometas, Nouvelles méthodes pour la détermination des orbites des comètes (Nuevos métodos para determinar las órbitas de los cometas), publicado en París, que cuando hay más ecuaciones que cantidades desconocidas no se pueden reducir todos los errores a 0. Por ello, minimizar la suma de los cuadrados de los errores es el método más general, preciso y práctico. También escribió que así se equilibran los errores y se evita el efecto de errores extremos. En la sección 186 de Theoria motus corporum coelestium (Teoría del movimiento de los cuerpos celestes), su libro sobre el movimiento de los cuerpos celestes publicado en Hamburgo en 1809, Gauss (C. F. Gauss) escribió que utilizaban desde 1795 el principio de minimizar la suma de los cuadrados de las diferencias, y que Legendre lo había publicado recientemente. Stigler, que volvió a estudiar esta historia en 1981, la llama la disputa de prioridad más famosa de la historia de la estadística.
Lo que suele decirse:Suele decirse que “Gauss ideó el método de los mínimos cuadrados” Según la fuente original:Legendre fue el primero en publicarlo impreso (en el apéndice de su libro de 1805). Gauss escribió en su libro de 1809 que lo usaba desde 1795. Sin embargo, al revisar las pruebas en 1981, Stigler concluyó que Gauss probablemente lo descubrió primero, pero no logró comunicarlo a sus contemporáneos, y advirtió que esta conclusión tampoco era definitiva. Además, el estadounidense Adrain publicó el mismo método a finales de 1808 o principios de 1809: se mencionan 3 personas, no 2.
Lo que aún no se sabe:No se ha resuelto si Gauss realmente lo usaba en 1795. Algunos testimonios posteriores de Gauss indican 1794, por lo que la fecha varía. Stigler escribe que quizá se podría comprobar con los datos de la medición del meridiano francés.
3 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:Año de publicación del libro de Legendre: la portada dice AN XIII − 1805. Gauss lo cita como Paris 1806 en su libro de 1809 (archive.org también tiene una edición de 1806 con suplemento). Año en que Gauss comenzó a utilizarlo: su libro de 1809 indica 1795; según Stigler (1981), algunos testimonios posteriores indican 1794.
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)
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_least_squares.py
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 .
No se puede determinar la forma del freno
Verhulst comparó la fórmula con datos de población de Francia, Bélgica, Essex y Rusia. Escribió que, aunque se cambiara el freno por np³ o n log p, el error respecto a las observaciones era casi el mismo, pero el límite superior cambiaba mucho. Con pocos datos no se puede decidir qué fórmula es correcta. Este problema enlaza con la sección “Cómo detectar el sobreajuste” (AIC y validación cruzada).
Fuentes originales y grado de certeza (2)De una fórmula de población a una de probabilidad
1838Verificado en la fuente original
La función logística (curva en S) ── Verhulst la publica como fórmula del crecimiento de la población en 1838; recibe su nombre en 1845
La función logística describe un crecimiento inicialmente cercano a una duplicación sucesiva, que se vuelve más lento al acercarse a un límite, formando una S. Más tarde, la regresión logística utiliza esta S para representar una probabilidad (un número entre 0 y 1). En 1838, Verhulst (P.-F. Verhulst) expresó la velocidad de crecimiento de una población p con la fórmula dp/dt = mp − np² en un breve artículo del volumen 10 de Correspondance mathématique et physique (Correspondencia matemática y física), revista editada por Quetelet. La fórmula resta al término de crecimiento multiplicativo mp un freno np², que se intensifica cuanto mayor es la población. La solución muestra que, con el tiempo, la población se acerca al límite m/n. Verhulst la comparó con datos de población de Francia, Bélgica, Essex y Rusia, y escribió que había terminado la investigación en 1833 y la publicaba por recomendación de Quetelet. También indicó que cambiar el freno por np³, np⁴ o n log p producía errores respecto a las observaciones casi iguales, pero cambiaba mucho el valor del límite.
Lo que suele decirse:Suele creerse que “logística (logistic) es una palabra para la clasificación” Según la fuente original:Originalmente describía una fórmula del crecimiento de la población. El artículo de 1838 todavía no le daba un nombre. Verhulst la llamó logistique en un artículo de 1845 de la Real Academia de Bélgica, sin explicar el motivo (estudio histórico de Cramer, 2002). En 1920, Pearl y Reed redescubrieron la misma curva al estudiar la población estadounidense, sin conocer el trabajo de Verhulst.
Lo que aún no se sabe:El propio Verhulst señaló que distintos frenos daban errores similares respecto a las observaciones, pero predicciones del límite muy distintas. Concluyó que solo el futuro podría revelar la verdadera forma del freno. La dificultad de decidir qué fórmula es correcta con pocos datos conecta con los debates posteriores sobre la selección de modelos (AIC, entre otros).
Regresión logística: en 1958, Cox publica un estudio de regresión para datos de 0 y 1. Él mismo decía no saber quién la había usado primero
La regresión logística predice la probabilidad de un resultado de 1 a partir de variables explicativas, como la edad, cuando los resultados son 1 o 0, como sí o no. En la regresión lineal habitual, la predicción puede ser menor que 0 o mayor que 1. Con la curva logística en forma de S, siempre queda entre 0 y 1, y los resultados pueden interpretarse mediante razones de momios, que comparan las posibilidades de que algo ocurra. Cox, D. R. Cox, afiliado en el artículo a Birkbeck College de la Universidad de Londres, publicó en julio de 1958 (The Regression Analysis of Binary Sequences). Trató las pruebas y la estimación cuando se observa una secuencia de 0 y 1 y se considera que la probabilidad de obtener 1 depende de una o más variables explicativas. El resumen indica que existían bastantes estudios anteriores y que también los revisaría. En una entrevista de 1994, Cox explicó que buscaba crear un marco sistemático para analizar datos de 0 y 1, parecido a la regresión por mínimos cuadrados. Uno de los motivos fue el gran interés de los investigadores de psicología experimental de Birkbeck College por analizar esos datos.
Lo que suele decirse:Suele decirse que “Cox inventó 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 la había usado primero y que Cornfield quizá la hubiera aplicado en el estudio de Framingham unos años antes de 1958. En 1944, Berkson ya había usado la función logística en bioensayos, experimentos con organismos para medir los efectos de medicamentos y otras sustancias, y había acuñado la palabra (estudio histórico de Cramer de 2002). Un artículo de una revista médica de 2022 afirma que Berkson (1944) creó la regresión logística y Cox (1958) la perfeccionó.
Lo que aún no se sabe:Ni siquiera los testimonios de los participantes aclaran quién usó primero la regresión logística. Cox mencionó a Cornfield, pero también dijo no recordar si había recibido su influencia.
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.
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_logistic.py
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.
¿Por qué components y no factor?
Hotelling partió de la psicología, de la investigación que buscaba extraer los (traducción) detrás de las puntuaciones de las pruebas. Escribió que decidió llamarlos components (componentes) para que el método pudiera usarse fuera de la psicología (en propiedades de postes de teléfono, tipos de cambio de monedas, etc.) y para evitar confusiones con el término matemático factor.
Fuentes originales y grado de certeza (2)¿Qué recta está más cerca de los puntos?
noviembre de 1901Verificado en la fuente original
El precursor del análisis de componentes principales ── en 1901, Pearson muestra que la recta más cercana a un conjunto de puntos sigue el eje más largo de su dispersión
Karl Pearson, del University College de Londres, estudió cómo encontrar la recta o el plano que mejor se ajusta a un conjunto de puntos en un plano o en un espacio de 3 o más dimensiones. Con los mínimos cuadrados habituales (regresión: se supone que solo y tiene errores y se reducen las desviaciones verticales), se obtienen rectas distintas según se tome x o y como referencia. Pearson propuso que, si tanto x como y contienen errores de medición, se debe minimizar la suma de los cuadrados de las distancias perpendiculares desde los puntos hasta la recta. Mostró que esa recta pasa por el centro de gravedad y sigue el eje más largo del elipsoide que representa la dispersión de los puntos. Esta es la dirección del primer componente principal del análisis de componentes principales actual: un método que representa conjuntos de muchos números con pocos, extraídos en orden desde la dirección con mayor variación. El artículo incluye un ejemplo numérico de 10 puntos: la pendiente de la recta más cercana es −0.546; la de la regresión que predice y a partir de x, −0.5396; y la que predice x a partir de y, −0.5659. Así muestra que las 3 rectas son distintas.
Lo que suele decirse:Suele decirse que “Hotelling ideó el análisis de componentes principales en 1933 para resumir muchas variables en pocos números” Según la fuente original:En 1901, Pearson ya había mostrado que la recta más cercana a los puntos sigue el eje más largo de su dispersión. Sin embargo, su objetivo era encontrar rectas y planos que se ajustaran mejor cuando tanto x como y contienen errores, y sus ejemplos solo tenían 2 o 3 variables. También escribió que con 4, 5 o más variables los cálculos resultan laboriosos (hay que resolver ecuaciones de grado 4, 5 o superior), pero estimar las soluciones no es tan difícil. El nombre componentes principales (principal components) procede de Hotelling en 1933.
septiembre de 1933Verificado en la fuente original
Análisis de componentes principales: en 1933, Hotelling llama método de componentes principales a una forma de representar muchos números, como las notas de exámenes, con pocos componentes extraídos en orden de mayor variación
Harold Hotelling, de la Universidad de Columbia, consideró que detrás de muchas variables relacionadas entre sí, como la rapidez de los niños en aritmética o sus notas en pruebas de lectura, hay unas pocas cantidades básicas sin relación entre ellas, y mostró cómo extraerlas. Primero se extrae un componente que explique la mayor parte de la variación de todas las variables; después, entre los componentes sin relación con el primero, se van extrayendo los que más explican la variación restante. Los de poca influencia pueden descartarse. Lo llamó y explicó que equivale a alinear los ejes de coordenadas con los ejes principales del elipsoide de la distribución de puntos. Escribió que eran lo que en psicología se llamaba , pero que también se podían utilizar fuera de la psicología (para las propiedades de postes eléctricos o los tipos de cambio, por ejemplo). Por eso eligió components (componentes), para evitar la confusión con la palabra matemática factor.
Lo que suele decirse:Suele creerse que “el análisis de componentes principales es una técnica de la era de las computadoras para reducir la dimensión de los datos” Según la fuente original:La investigación del artículo de Hotelling de 1933 se desarrolló bajo el comité de Thorndike (Unitary Traits Committee) y la Fundación Carnegie como un estudio psicológico para extraer las funciones mentales básicas (factores, en el vocabulario de entonces) detrás de las notas de exámenes. Se eligió components (componentes) para que sirviera fuera de la psicología y no se confundiera con el término matemático factor. Pearson ya había mostrado en 1901 que la recta más cercana a los puntos sigue la dirección de mayor varianza.
Lo que aún no se sabe:Para este sitio no se ha comprobado si Hotelling conocía el artículo de Pearson de 1901 (la copia guardada es texto obtenido por reconocimiento automático y no se han leído todas las páginas).
Whence Principal Components? (Lawrence Hubert · 2016 · p.3-6 Harold Hotelling and Truman Lee Kelley/Hotelling as a Quant… · Resumen secundario)
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
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_pca.py
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.
La consulta y el artículo
La consulta trataba sobre si conceder la libertad condicional a quienes habían cumplido un tercio de su condena. Hayashi oyó que los presos ejemplares, que se adaptaban bien a la vida en prisión y trabajaban mucho, regresaban enseguida tras salir. Las puntuaciones no siempre siguen una sola dirección en línea recta. El artículo en inglés de 1950 planteó esto como un problema de maximizar el porcentaje de aciertos de las predicciones.
La cuantificación después
Hayashi creó después métodos para cada problema práctico: la encuesta de lectura y escritura (tipo I), las relaciones humanas entre los trabajadores de mantenimiento de vías de los Ferrocarriles Nacionales de Japón (tipo IV) y el diseño de etiquetas de conservas para exportación (tipo III). El tipo III (1956) tiene una relación matemática profunda con el análisis de correspondencias de Benzécri, en Francia (1973), y se publicó antes.
Todavía no se ha comprobado cuánto cambiaron las decisiones reales de libertad condicional al usar los valores de Hayashi.
Fuentes originales y grado de certeza (1)Determinar las puntuaciones a partir de los datos
1950–1956Verificado en la fuente originalJapón
Teoría de la cuantificación: en 1950, Chikio Hayashi publica un método para asignar números a datos cualitativos y predecir los resultados de la libertad condicional
Cuando la encuesta de alfabetización de la población japonesa de 1948 estaba por terminar, un especialista en derecho penal del instituto de formación en correcciones y libertad condicional del Ministerio de Justicia consultó a Chikio Hayashi, del Instituto de Matemáticas Estadísticas. Quería hacer más fiable, mediante la estadística, la decisión de conceder la libertad condicional a presos que habían cumplido un tercio de su condena. Los métodos anteriores asignaban a las respuestas de cada apartado puntuaciones como −2, −1, 0, 1, 2 según el criterio humano, y las sumaban. Hayashi visitó la prisión de Yokohama y oyó que los presos ejemplares, bien adaptados a la vida carcelaria y trabajadores, regresaban pronto incluso después de salir. También observó que los muy rebeldes tendían a reincidir y los intermedios eran los menos propensos a hacerlo. Comprendió que las puntuaciones de valoración no necesariamente siguen una sola dirección. Así concibió la idea de determinar a partir de los datos los propios números asignados a cada respuesta (datos cualitativos), para separar con la mayor claridad a quienes habían reincidido de quienes no. En su artículo en inglés de 1950 formuló el problema como maximizar la tasa de éxito de la predicción. Después desarrolló métodos para distintos problemas prácticos: la encuesta de alfabetización, las relaciones humanas entre trabajadores de mantenimiento de vías de los Ferrocarriles Nacionales y el diseño de etiquetas de conservas para exportación. En conjunto recibieron el nombre de teoría de la cuantificación.
Lo que suele decirse:Suele creerse que “Chikio Hayashi creó y nombró los métodos de cuantificación I, II, III y IV en ese orden” Según la fuente original:El primero fue el método para predecir los resultados de la libertad condicional (actual tipo II). El tipo I nació de la encuesta de alfabetización; el IV, de la encuesta a trabajadores de mantenimiento ferroviario; y el III, del estudio del diseño de etiquetas de conservas para exportación. Los números I–IV son nombres que les dio el psicólogo social Hiroshi Akuto en 1964 y no guardan relación directa con el orden de desarrollo (Morimoto, 2005). Morimoto (2005) también cita el análisis de correspondencias del francés Benzécri (1973), entre otras investigaciones, como un trabajo con fuerte relación matemática con el tipo III. El tipo III de Hayashi (1956) es anterior.
Lo que aún no se sabe:Para este sitio no se ha comprobado cuánto cambiaron realmente las decisiones de libertad condicional con los números (pesos) de Hayashi, ni si se utilizaron en la práctica.
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.
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_quantification.py
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.
Condiciones de la garantía
La garantía del doble se refiere a datos infinitos; no garantiza el rendimiento con pocos datos.
Este sitio todavía no ha consultado directamente el informe de 1951 (se basa en el artículo de 1967 y en las explicaciones que lo presentan).
Fuentes originales y grado de certeza (2)Basta con seguir el ejemplo más cercano
febrero de 1951Confirmado en resúmenes
El inicio del método de los k vecinos más cercanos: Fix y Hodges lo idean en 1951 en un informe de la Fuerza Aérea estadounidense (no se publicó como artículo de revista)
El método de los k vecinos más cercanos (k-NN) busca los k datos etiquetados más próximos a un punto nuevo que se desea clasificar y lo asigna al grupo más numeroso entre ellos. Se llama método no paramétrico porque no fija de antemano la distribución de los datos. En febrero de 1951, E. Fix y J. L. Hodges, Jr. idearon este tipo de regla en el informe Discriminatory Analysis, Nonparametric Discrimination (Análisis discriminante, discriminación no paramétrica) de la USAF School of Aviation Medicine (Randolph Field, Texas). Mostraron que, si k aumenta junto con el número de datos n y k/n se acerca a 0, la regla es consistente (cuantos más datos hay, más se acerca a la clasificación óptima). Así lo presenta el artículo de Cover y Hart de 1967.
Lo que suele decirse:Suele decirse que “Cover y Hart idearon el método de los k vecinos más cercanos en 1967” Según la fuente original:En su propio artículo de 1967, Cover y Hart escriben que parece que Fix y Hodges fueron los primeros en formular la regla de los vecinos más cercanos y estudiar sus propiedades. El informe de 1951 no se publicó como artículo de revista (explicación de Scholarpedia).
Lo que aún no se sabe:Para este sitio todavía no se ha abierto y comprobado el informe original de 1951. El contenido se basa en las presentaciones del artículo de 1967 y de un artículo explicativo.
Garantía teórica del vecino más cercano ── en 1967, Cover y Hart demuestran que incluso clasificar según un solo punto cercano no supera el doble de la tasa mínima teórica de error
El método del vecino más cercano (k vecinos más cercanos con k=1) asigna un dato nuevo a la misma clase (grupo) que el punto ya clasificado más cercano. En su artículo de enero de 1967, Nearest Neighbor Pattern Classification (), Cover (T. M. Cover, Stanford University) y Hart (P. E. Hart, Stanford Research Institute) demostraron que, cuando hay suficientes puntos clasificados, la tasa de error R de este método no baja de la tasa mínima R* que se obtendría conociendo por completo la distribución (error de Bayes), pero tampoco supera el doble de R*. Si el número de clases es M: R* ≤ R ≤ R*(2 − MR*/(M − 1)). El artículo afirma que, en este sentido, el punto más cercano contiene la mitad de la información para clasificar que hay en una cantidad infinita de datos.
Lo que aún no se sabe:Esta garantía teórica se refiere al caso en que hay suficientes datos (large sample, en el artículo); no describe el rendimiento cuando hay pocos datos.
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)
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_knn.py
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.
El artículo 25 años después
El manuscrito de Lloyd apareció en una revista académica en 1982. Él mismo lo llamó (traducción).
El k-means de MacQueen y el actual
MacQueen dio nombre al procedimiento secuencial que añade los puntos de uno en uno. La repetición en 2 etapas habitual en los libros actuales —reasignar todos los puntos y recalcular los promedios— aparece en el mismo artículo como un método que Forgy y Jennrich le enseñaron hacia 1963 (según el resumen de Bock de 2008).
Fuentes originales y grado de certeza (2)Separar y mover al promedio
31 de julio de 1957–1982Verificado en la fuente original
Antecedente de k-means: en 1957, Lloyd escribe en Bell Labs un procedimiento para encontrar la mejor manera de representar señales con pocos valores representativos (publicado en una revista científica en 1982)
Stuart Lloyd, de Bell Labs, estudió la PCM, o modulación por impulsos codificados: un método que transmite el voltaje de una señal sustituyéndolo por uno de un número determinado de valores representativos. El problema consistía en encontrar los límites de los intervalos y los valores representativos que minimizaran la media del cuadrado del error respecto a la señal original, llamado ruido de cuantización. Su método I alterna estos pasos: (1) fijar los límites y tomar el centro de gravedad, o media, de cada intervalo como valor representativo; (2) fijar los nuevos límites justo a mitad de camino entre valores representativos vecinos. Tiene la misma estructura que k-means en 1 dimensión: agrupar los puntos según el representante más cercano y mover cada representante a la media de su grupo, repetidamente. El manuscrito circuló en Bell Labs en 1957, y una parte se presentó en una reunión de una sociedad de estadística en septiembre de ese año. Sin embargo, no apareció en una revista científica hasta 1982, unos 25 años después.
Lo que suele decirse:Suele decirse que “k-means es un método creado por MacQueen en 1967” Según la fuente original:El mismo procedimiento de asignar los puntos al representante más cercano y mover los representantes a las medias ya aparece en el manuscrito que Lloyd hizo circular en Bell Labs en 1957 para cuantizar señales de 1 dimensión. En informática y reconocimiento de patrones suele llamarse algoritmo de Lloyd (Bock 2008). Sin embargo, el manuscrito no se publicó en una revista durante 25 años. En la nota final del artículo de 1982, el propio Lloyd lo describió como un (traducción), publicado casi sin cambios respecto al borrador de 1957.
Lo que aún no se sabe:El manuscrito de 1957, un documento interno de Bell Labs, no está disponible públicamente. Este sitio solo lo ha comprobado mediante la nota final del artículo de 1982. No se sabe exactamente qué presentó ni hasta dónde llegó en la reunión de 1957.
k-means ── en 1967, MacQueen llama k-means (k medias) a un procedimiento para dividir puntos en k grupos
J. MacQueen, de la Universidad de California en Los Ángeles, llamó k-means a un procedimiento que divide datos (puntos) en k grupos para reducir la dispersión dentro de cada grupo (la suma de las distancias al cuadrado respecto a su media). En su procedimiento, los primeros k puntos forman un grupo cada uno. Después se incorpora cada nuevo punto al grupo cuya media está más cerca y se actualiza inmediatamente la media de ese grupo. Lo llamó k-means porque, en cualquier etapa, las k medias son las medias de cada grupo. En el mismo artículo también presentó la forma que hoy suele describirse como el procedimiento k-means: repetir 2 pasos, reasignar todos los puntos al grupo de la media más cercana → recalcular la media de cada grupo. Explicó que Forgy y Jennrich habían descubierto este método por separado y se lo habían comunicado hacia 1963.
Lo que suele decirse:Suele decirse que “MacQueen inventó k-means en 1967” Según la fuente original:El propio MacQueen escribió lo siguiente en ese artículo: el uso explícito más antiguo de la misma idea que conocía era el libro de Sebestyen de 1962; el método que repite 2 pasos se lo habían comunicado Forgy y Jennrich. En una nota añadida durante la corrección de pruebas indicó además que Wallace y Ball también lo habían usado por separado. Según el resumen de Bock (2008), MacQueen dio el nombre k-means al procedimiento secuencial que incorpora un punto cada vez, no al método que repite 2 pasos que hoy suele aparecer en los libros de texto. Antes aún, en 1956, Steinhaus había presentado la misma idea como un problema de mecánica de dividir objetos en k grupos, y en 1957 Lloyd había escrito un procedimiento de la misma forma para cuantificar señales.
Lo que aún no se sabe:Se sabe que varios investigadores llegaron de forma independiente al mismo procedimiento, pero este sitio no ha comprobado cuánto intercambio de información hubo entre ellos (por ejemplo, quién había leído el manuscrito de Lloyd de 1957).
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.
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_kmeans.py
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.
Las personas que calculaban
En 1958 se usaron máquinas de tarjetas perforadas de IBM y personas que calculaban con calculadoras de escritorio. Solo los coeficientes de correlación exigieron 160 horas-persona. El artículo llama computer a las personas que calculaban. Los 2 autores escribieron que una computadora digital de la época tardaría menos de 1 hora.
Aunque suele pensarse que el agrupamiento nació en la IA o la informática, una de sus primeras formas fue creada por entomólogos para que la clasificación de abejas dependiera menos de las preferencias personales.
Fuentes originales y grado de certeza (2)Unir lo más parecido para formar un árbol
20 de marzo de 1958Verificado en la fuente original
Agrupamiento jerárquico: en 1958, Sokal y Michener organizan 97 especies de abejas en un árbol según su semejanza
Robert Sokal y Charles Michener, del departamento de entomología de la Universidad de Kansas, clasificaron 97 especies de abejas solitarias de la familia de las cortadoras de hojas. Compararon 122 características por especie, como si el abdomen era rojo o negro, y expresaron la semejanza entre especies mediante el coeficiente de correlación: un número que indica hasta qué punto 2 conjuntos de valores aumentan y disminuyen de forma parecida. Agruparon las especies semejantes y fueron uniendo los grupos para construir un árbol. Es la idea del actual agrupamiento jerárquico: unir primero los elementos cercanos y formar un árbol de grupos incluidos unos dentro de otros. Las clasificaciones tradicionales daban distintos pesos a unas pocas características según criterios personales. Ellos dieron el mismo peso a muchas características. Para calcular usaron máquinas de tarjetas perforadas de IBM y personas con calculadoras de escritorio; el artículo llama computer a esas personas. Solo los coeficientes de correlación requirieron 160 horas de trabajo humano. Los autores también escribieron que una computadora digital de entonces habría tardado menos de 1 hora.
Lo que suele decirse:Suele pensarse que “el agrupamiento de datos semejantes nació dentro de la IA o la informática” Según la fuente original:Una de las primeras formas de agrupamiento jerárquico fue ideada por entomólogos en 1958 para que la clasificación de las abejas dependiera menos de preferencias personales. Los cálculos se hicieron con máquinas de tarjetas perforadas y personas que usaban calculadoras de escritorio.
Lo que aún no se sabe:Se considera que por la misma época surgieron en otros campos ideas de construir árboles agrupando primero los elementos semejantes. Sin embargo, este sitio no ha consultado sus artículos originales ni lo ha verificado. No se ha determinado cuál fue el primero.
Método de Ward: en 1963, Ward presenta un agrupamiento jerárquico que elige una función objetivo y une grupos de 2 en 2
Joe H. Ward Jr., de la División de Medicina Aeroespacial de la base aérea de Lackland, presentó un procedimiento para reunir personas u objetos en grupos semejantes en estudios grandes, con más de 100 elementos. Partiendo de n grupos, inicialmente de un solo elemento, examina las n(n−1)/2 maneras de unir 2 de ellos. Une los 2 que dan el mejor valor de la función objetivo, un número que expresa la calidad del agrupamiento y que quien analiza elige según su propósito. Así quedan n−1 grupos. Al repetirlo hasta obtener 1 grupo, se revela la estructura jerárquica completa y la cantidad de información perdida en cada paso. En el ejemplo del artículo, si las puntuaciones de 10 personas, 2, 6, 5, 6, 2, 2, 2, 0, 0, 0, se representan como un solo grupo mediante su media, la suma de errores cuadrados, o suma de los cuadrados de las diferencias respecto a la media, es 50.5. Si se dividen en 4 grupos, {0,0,0} {2,2,2,2} {5} {6,6}, es 0.
Lo que suele decirse:Suele enseñarse que “el método de Ward une los grupos que menos aumentan la dispersión interna, medida por la suma de errores cuadrados” Según la fuente original:El artículo de Ward de 1963 presenta un procedimiento general que permite usar cualquier función objetivo que el analista elija según su propósito. La suma de errores cuadrados es solo uno de los ejemplos. El Laboratorio de Investigación de Personal del artículo usaba el mismo programa con funciones objetivo distintas para 4 fines: agrupar personas semejantes, agrupar empleos para reducir el tiempo de formación al reasignar personal, reducir el número de descripciones de puestos y reducir el número de ecuaciones de predicción.
Lo que aún no se sabe:Este sitio ha comprobado las primeras 2 páginas del artículo, p.236-237. No ha leído los detalles del diagrama de flujo ni de los ejemplos numéricos de p.238 en adelante.
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.
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_ward.py
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.
Revistas que los ingenieros de voz no leían
Rabiner (1989) escribió que esta teoría había aparecido en revistas especializadas de matemáticas que los ingenieros de voz no leían, por lo que tardó en difundirse en el reconocimiento del habla. Desde sus primeras aplicaciones a la voz en la década de 1970 hasta su adopción general pasaron más de 10 años.
El título del artículo de 1966 no decía “oculto”, sino que trataba de funciones probabilísticas de cadenas de Markov.
Fuentes originales y grado de certeza (2)Inferir estados invisibles a partir de símbolos
diciembre de 1966–1970Verificado en la fuente original
Modelo oculto de Markov ── en 1966, Baum y Petrie desarrollan las matemáticas de un modelo con estados invisibles que cambian y emiten símbolos
Leonard E. Baum y Petrie, del Institute for Defense Analyses de Princeton, estudiaron un modelo probabilístico. En él, estados que no se ven desde fuera cambian según una cadena de Markov (una transición en la que la probabilidad del siguiente estado depende solo del estado actual), y cada estado emite símbolos de forma probabilística. Lo llamaron una función probabilística de una cadena de Markov. Demostraron que, usando solo la secuencia de símbolos observados Y1, …, YT, era posible estimar la tabla A de probabilidades de transición entre estados y la tabla B de probabilidades de emisión de símbolos. También demostraron que, al aumentar los datos, la estimación por máxima verosimilitud (elegir los valores que hacen más probables esos datos) se acerca a los valores correctos. Este es uno de los orígenes matemáticos del actual modelo oculto de Markov (HMM). En 1970, el mismo grupo (con Petrie, Soules y Weiss) presentó un cálculo iterativo que aumentaba gradualmente la verosimilitud. Dempster y sus colegas escribieron en 1977 que era un caso particular del algoritmo EM.
Lo que suele decirse:Suele pensarse que “el modelo oculto de Markov (HMM) se creó para reconocer el habla” Según la fuente original:Su origen fue un artículo de estadística de 1966 de 2 investigadores del Institute for Defense Analyses. El título hablaba de funciones probabilísticas de cadenas de Markov, no de estados ocultos (hidden). Rabiner 1989 escribe que su aplicación al reconocimiento del habla se retrasó porque la teoría apareció en una revista especializada en matemáticas que los ingenieros del habla no leían. Según una nota al pie de Rabiner 1989, la presentación del HMM mediante 3 problemas básicos (calcular probabilidades, encontrar la secuencia de estados más probable y aprender parámetros) también fue expuesta en clases y textos por Jack Ferguson, del IDA (escrito allí como Institute for Defense Analysis).
Lo que aún no se sabe:Este sitio no ha comprobado quién utilizó por primera vez el nombre modelo oculto de Markov (hidden Markov model) ni en qué año. Las fuentes tampoco indican con qué propósito se realizó esta investigación en el Institute for Defense Analyses.
febrero de 1975–1989Verificado en la fuente originalLas fuentes discrepan
Reconocimiento de voz con modelos ocultos de Markov — Baker empezó a usarlos en 1975 y Jelinek, de IBM, en 1976; la explicación de Rabiner de 1989 los dio a conocer ampliamente
Aunque las palabras sean las mismas, la voz cambia según la persona y la velocidad al hablar. En 1975, J. Baker representó distintos conocimientos del lenguaje en el sistema de comprensión de voz DRAGON mediante una sola forma: funciones probabilísticas de un proceso de Markov (los actuales modelos ocultos de Markov, en los que estados no observables cambian con ciertas probabilidades y cada estado emite características del sonido también de forma probabilística). En 1976, F. Jelinek, del Centro de Investigación Thomas J. Watson de IBM, publicó un artículo sobre el reconocimiento de voz continua con métodos estadísticos. Sin embargo, cuando Rabiner redactó su texto en 1988, este método solo había empezado a comprenderse y utilizarse ampliamente en la investigación de voz durante los últimos años. En 1989, Lawrence R. Rabiner, de AT&T Bell Laboratories, reunió la teoría y sus aplicaciones al reconocimiento de voz en una sola explicación. En sus experimentos de reconocimiento de dígitos pronunciados de uno en uno, independientemente del hablante, la tasa de error de los modelos ocultos de Markov fue similar a la del método tradicional de comparación de patrones (DTW, que ajusta las diferencias de velocidad del habla mediante programación dinámica y después compara con patrones de voz almacenados). En Japón, Hiroaki Sakoe y Seibi Chiba, de NEC, ya habían presentado esta idea de comparar patrones como DP matching en 1971 (otro acontecimiento de este sitio).
Lo que suele decirse:Se suele pensar que “los modelos ocultos de Markov mejoraron de golpe el reconocimiento de voz” Según la fuente original:En las tablas de los experimentos del propio Rabiner de 1989, las tasas de error de los modelos ocultos de Markov y de la comparación tradicional de patrones (DTW) fueron similares para reconocer dígitos aislados independientemente del hablante (1.3% frente a 2.0% en un nuevo grupo de 100 personas, y 1.8% frente a 1.1% en otro grupo de 100). Rabiner destacó como ventajas su capacidad de representar cómo se genera la voz y de extenderse al reconocimiento con vocabularios grandes. Además, transcurrieron más de 10 años desde sus primeras aplicaciones a la voz en la década de 1970 hasta su uso generalizado.
Lo que aún no se sabe:Rabiner 1989 también señala que las suposiciones de independencia entre las observaciones del sonido y de propiedad de Markov tienen aspectos que no encajan con la voz real. La explicación no aclara por qué el método funcionó bien a pesar de ello.
3 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:Afiliación de Baker: Rabiner 1989 escribe “Baker at CMU”, mientras que el registro bibliográfico de IEEE (artículo de 1975) indica IBM Thomas J. Watson Research Center (es posible que la afiliación al publicarse y el lugar donde se realizó el trabajo fueran distintos, pero este sitio no lo ha comprobado).
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.
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_hmm.py
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.
La primera presentación y su recepción
Según sus recuerdos de 1981, Akaike vio de repente la relación la mañana del 16 de marzo de 1971, cuando se sentó en el tren de camino al trabajo. En su conferencia del Premio Kioto de 2006 dijo: (traducción). También explicó que la respuesta de los campos de aplicación fue favorable, pero que (traducción).
La idea de la validación cruzada es antigua: Stone citó como antecedentes a Larson (1931) y a Mosteller y Tukey (1968), entre otros.
Fuentes originales y grado de certeza (3)Cómo detectar el sobreajuste
1973–1974Verificado en la fuente originalLas fuentes discrepanJapón
Criterio de información de Akaike, AIC ── presentado por Hirotugu Akaike en 1971 y publicado en 1973. Combina el ajuste a los datos con una penalización por el número de parámetros
AIC es un criterio para decidir qué modelo usar entre varios modelos estadísticos candidatos. Se calcula como AIC= (−2) × (máxima log-verosimilitud)+2 × (número de parámetros), y se considera mejor el modelo con menor valor. El primer término indica el ajuste a los datos (cuanto mejor se ajusta, menor es el valor); el segundo penaliza aumentar demasiado el número de parámetros ajustables. En 1968, Hirotugu Akaike, del Instituto de Matemática Estadística, estudiaba un modelo de series temporales del movimiento de un horno rotatorio de cemento. Ante el problema de decidir cuántos valores pasados usar (el orden), ideó el error de predicción esperado (FPE). Según sus recuerdos de 1981, la mañana del 16 de marzo de 1971, al sentarse en el tren que lo llevaba al trabajo, advirtió de repente la relación entre máxima verosimilitud e información de Kullback–Leibler. En su conferencia conmemorativa del Premio Kioto de 2006 dijo: (traducción). Añadió que lo presentó en detalle ese mismo año en el 2.º Simposio Internacional de Teoría de la Información, en Armenia; que se publicó en las actas en 1973; y que en 1974 publicó una explicación en una revista estadounidense de IEEE sobre control automático.
Lo que suele decirse:Suele decirse que “la A de AIC es la A de Akaike” Según la fuente original:El propio Akaike escribió en su artículo de 1974 que IC abrevia information criterion (criterio de información) y que añadió la A para que pudieran seguir otros criterios similares, como BIC y DIC. En sus recuerdos de 1981 también dice que AIC abrevia an information criterion (un criterio de información). En cambio, la justificación del Premio Kioto de 2006 usa Akaike Information Criterion.
Lo que aún no se sabe:AIC no fue aceptado desde el principio. En su conferencia de 2006, Akaike dijo que hubo una respuesta entusiasta de los campos aplicados, pero (traducción). En sus recuerdos de 1981 también escribe que aún no estaba plenamente aceptado por los estadísticos profesionales. Además, AIC presupone un modelo regular, en el que parámetros y distribuciones se corresponden uno a uno. Por ello, cómo usarlo con máquinas que aprenden, como las redes neuronales, dio lugar a investigaciones posteriores (como WAIC, de Sumio Watanabe).
5 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:Año de propuesta: el propio Akaike sitúa la primera presentación en 1971 (en la Sociedad Japonesa de Estadística y en un simposio internacional ese mismo año) y la publicación de las actas en 1973. El texto de Genshiro Kitagawa de 2006 dice que se propuso en 1973; la justificación del Premio Kioto, a principios de los años 1970.
Validación cruzada — En 1974, Stone publicó un artículo sobre cómo elegir y evaluar métodos de predicción separando los datos para comprobarlos. La idea ya existía desde la década de 1930
La validación cruzada consiste en dividir los datos disponibles en conjuntos de entrenamiento y validación, repetir la comprobación cambiando la división y elegir un método de predicción a partir del rendimiento promedio. En la modalidad de dejar uno fuera, se excluye 1 de los n datos, se construye un modelo con los n − 1 restantes y se prueba con el dato excluido; esto se repite de n formas. En su artículo Cross-validatory Choice and Assessment of Statistical Predictions (), presentado el 5 de diciembre de 1973 ante la Royal Statistical Society y publicado en 1974 en Journal of the Royal Statistical Society, Series B, M. Stone (University College London) propuso usar este criterio para unir la selección del método de predicción con su evaluación. Lo ilustró con ejemplos de estimación a partir de una muestra, regresión múltiple y análisis de varianza.
Lo que suele decirse:Se suele decir que “Stone ideó la validación cruzada en 1974” Según la fuente original:El propio Stone escribió al principio del artículo que este enfoque de evaluación ya existía. Citó como antecedentes el estudio de Larson de 1931, que dividía los datos en 2 conjuntos; un simposio de 1951 sobre la necesidad y los métodos de validación cruzada; y la explicación de Mosteller y Tukey de 1968, que proponía construir el modelo dejando un dato fuera, probarlo con ese dato y repetirlo con todos los datos. En una nota, Stone también escribió que prefería assessment (evaluación) a validation (dar por válido), porque esta última palabra parecía expresar demasiada confianza.
Lo que aún no se sabe:En 1977, Stone demostró que la validación cruzada dejando uno fuera y el AIC de Akaike se comportan de forma similar cuando hay muchos datos (son asintóticamente equivalentes), según la descripción del artículo de Watanabe de 2010. Sin embargo, esto se refiere a modelos regulares, en los que los parámetros y las distribuciones de probabilidad tienen una correspondencia de 1 a 1. Para modelos singulares, como las redes neuronales, no se sabía qué ocurría hasta el artículo de Watanabe de 2010.
diciembre de 2010Verificado en la fuente originalJapón
WAIC: en 2010, Sumio Watanabe demuestra que un criterio de información aplicable también a redes neuronales y la validación cruzada dejando un dato fuera se aproximan al mismo valor
WAIC (widely applicable information criterion, criterio de información de amplia aplicación) es un criterio propuesto por Sumio Watanabe (afiliación en el artículo: Precision and Intelligence Laboratory, Tokyo Institute of Technology) para estimar la pérdida de generalización de modelos de inferencia bayesiana, es decir, el error de predicción con datos desconocidos. AIC presupone modelos regulares, en los que hay una correspondencia de uno a uno entre parámetros y distribuciones de probabilidad. Sin embargo, muchas máquinas de aprendizaje, como redes neuronales, mezclas de distribuciones normales, modelos ocultos de Markov y máquinas de Boltzmann, son modelos singulares que no cumplen esta condición. En un artículo de diciembre de 2010 en Journal of Machine Learning Research, Watanabe demostró que, incluso en estos modelos singulares, la pérdida de la validación cruzada bayesiana dejando un dato fuera y WAIC se aproximan al mismo valor cuando hay muchos datos: son asintóticamente equivalentes. Para los modelos regulares, ya se conocía la equivalencia asintótica entre esta validación cruzada y AIC, entre otras fuentes por un artículo de Stone de 1977.
Lo que suele decirse:Suele decirse que “la W de WAIC viene de Watanabe” (también se denomina Watanabe-Akaike information criterion, criterio de información de Watanabe y Akaike) Según la fuente original:El nombre usado en el artículo de Watanabe es widely applicable information criterion, criterio de información de amplia aplicación. La denominación Watanabe-Akaike apareció en un artículo explicativo de Gelman y colaboradores de 2013, que también aclara que Watanabe lo llama widely applicable. Al igual que la A de AIC no era la inicial de Akaike, la W de WAIC tampoco era un nombre de persona para quien lo denominó.
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
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_aic_cv.py
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.
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.
Crear a propósito una parte invisible
En el ejemplo de 197 animales, el primer tipo (125 animales) se considera dividido en 2 grupos: uno con probabilidad 1/2 y otro con π/4. No se ve cuántos animales hay en cada grupo, pero esa división deliberada simplifica el cálculo.
Fuentes originales y grado de certeza (1)Completar lo invisible y recalcular
8 de diciembre de 1976–1977Verificado en la fuente original
Algoritmo EM — En 1977, Dempster, Laird y Rubin reunieron en una forma general y dieron nombre a un método para aprender de datos parcialmente no observables
A. P. Dempster, N. M. Laird y D. B. Rubin, de la Universidad de Harvard y Educational Testing Service, presentaron un método general para estimar los parámetros más verosímiles (los números dentro de un modelo) cuando una parte de los datos no se observa o falta. En el paso E (expectation: esperanza), se usan los parámetros actuales para calcular la esperanza de los valores de la parte no observable. En el paso M (maximization: maximización), se utilizan los datos completados para recalcular los parámetros con los valores más verosímiles. Lo llamaron algoritmo EM porque repite estos pasos de forma alternada. Demostraron que, en cada repetición, la verosimilitud de los datos (la probabilidad de obtener esos datos con esos parámetros) no disminuye. También mostraron que muchos casos encajan en esta forma: datos con valores ausentes, distribuciones con varios picos mezclados (distribuciones de mezcla), análisis factorial y otros. El primer ejemplo eran datos de 197 animales divididos en 4 categorías por un mecanismo genético (un ejemplo del libro de Rao de 1965).
Lo que suele decirse:Se suele decir que “Dempster, Laird y Rubin inventaron el algoritmo EM en 1977” Según la fuente original:Los 3 autores escribieron que el algoritmo ya se había propuesto muchas veces para casos particulares. Citaron el ejemplo de Hartley (1958) y los artículos de Baum y sus colaboradores (1967–1972) como derivaciones independientes del mismo método (los de Baum trataban un modelo con estados no observables que cambian según una cadena de Markov: los actuales modelos ocultos de Markov). También escribieron que Baum y sus colaboradores habían mostrado el mismo razonamiento en un caso particular, pero parecían no haber advertido su amplia generalidad. Su aportación fue reunir casos dispersos en una forma general, llamarla EM y demostrar de manera general 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
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_em.py
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.
El artículo en inglés fue anterior
El artículo en inglés (1979) se publicó antes que el japonés (1980). El resumen del artículo japonés dice que se puede ampliar fácilmente a 3 o más clases (una imagen de células se dividió en 3: fondo, citoplasma y núcleo).
El artículo en inglés señala que todavía no se había obtenido una demostración rigurosa de que la función de evaluación siempre tuviera un solo pico.
Fuentes originales y grado de certeza (1)Elegir automáticamente el límite entre blanco y negro
enero de 1979–1980Verificado en la fuente originalJapón
Binarización de Otsu — En 1979, Nobuyuki Otsu presentó un método para fijar automáticamente el umbral que divide una imagen en tonos de gris en blanco y negro, buscando la mejor separación entre 2 grupos
Nobuyuki Otsu (afiliado a Electrotechnical Laboratory, Tokyo, en el artículo en inglés de 1979) presentó un método para determinar automáticamente el nivel de brillo límite (umbral) que separa letras u objetos del fondo en una imagen en tonos de gris. Al dividir la distribución de frecuencias del brillo (histograma) en 2 grupos mediante un nivel k, elige el k que maximiza la variación entre los grupos (varianza entre clases). Esta idea procede del análisis discriminante, un método estadístico que busca un criterio para separar bien 2 grupos, y equivale a minimizar la variación dentro de los grupos (varianza dentro de las clases). El cálculo es muy sencillo porque solo utiliza los momentos acumulados de orden 0 y 1 del histograma (la proporción de píxeles y la suma de sus brillos hasta ese nivel). Es un método no supervisado: decide sin recibir respuestas correctas. El resumen del artículo en japonés de 1980 señala que también es óptimo en el sentido de mínimos cuadrados al aproximar la imagen original con unos pocos valores, y que se puede ampliar fácilmente para dividirla en 3 o más grupos. Los ejemplos del artículo eran letras A escritas a máquina con cintas nuevas y viejas, un patrón de tela e imágenes de células (divididas en fondo, citoplasma y núcleo).
Lo que suele decirse:Se suele pensar que “la binarización de Otsu es un pequeño truco de procesamiento de imágenes para pasarlas a blanco y negro” Según la fuente original:Otsu dedujo la elección del umbral a partir del análisis discriminante y la trató como uno de los problemas fundamentales del reconocimiento de patrones, más allá del procesamiento de imágenes (resumen del artículo en japonés). La conclusión del artículo en inglés también dice que puede aplicarse a otras clasificaciones no supervisadas si se dispone de un histograma de características que distingan los objetos. Es decir, se propuso como un método de aprendizaje no supervisado que divide los datos en 2 grupos sin recibir respuestas correctas. El artículo en inglés (1979) se publicó antes que el japonés (1980).
Lo que aún no se sabe:El artículo en inglés señala que aún no se había obtenido una demostración rigurosa de que la función de evaluación siempre tuviera un solo pico (fuera unimodal), aunque en los experimentos siempre fue suave y unimodal.
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²
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_otsu.py
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.
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.
Origen del nombre y límites
Pearl escribió que las llamaba Bayes Network para destacar que los valores de probabilidad procedían del juicio humano (también las llamó Influence Network).
El propio Pearl señaló en el resumen que actualizar correctamente todo el conjunto solo con intercambios entre vecinos funciona únicamente en redes donde hay un solo camino entre cualquier pareja de puntos.
Fuentes originales y grado de certeza (1)Las pruebas propagan probabilidades por la red
abril de 1985Verificado en la fuente original
Red bayesiana: en 1985, Pearl dio nombre al método que representa relaciones de causa y efecto mediante un grafo de flechas y probabilidades condicionales (la idea venía de 1982)
Judea Pearl, de la Universidad de California en Los Ángeles (UCLA), llamó red bayesiana a un grafo en el que muchas proposiciones o variables son puntos, las dependencias directas se unen con flechas y su fuerza se expresa mediante probabilidades condicionales (probabilidad de que ocurra B cuando ocurre A). Cuando se obtiene nueva evidencia (por ejemplo, el resultado de una prueba), cada punto intercambia mensajes breves solo con sus vecinos y actualiza correctamente las probabilidades de toda la red (cuánto se cree en cada cosa). Así se puede razonar a partir de muchas pistas respetando las reglas del cálculo de probabilidades. En su artículo de AAAI de 1982, Pearl escribió que muchos investigadores de IA aceptaban el mito de que los modelos computacionales del razonamiento incierto debían alterar al menos en parte las reglas de la probabilidad, y utilizaban reglas improvisadas. Mostró que una red en forma de árbol podía actualizarse por completo con una sola ronda de intercambio, siguiendo las reglas de la probabilidad. El informe de 1985 presentó este mecanismo en un congreso de ciencias cognitivas como modelo de la memoria y el razonamiento humanos.
Lo que suele decirse:Se suele pensar: “Las redes bayesianas nacieron como herramientas estadísticas para aprender de los datos” Según la fuente original:El título del informe de Pearl de 1985 se refería a un modelo de memoria autónoma que razona a partir de evidencia, y se presentó en un congreso de ciencias cognitivas. El artículo de 1982 respondió a los cálculos improvisados que alteraban las reglas de la probabilidad en sistemas de IA, como los sistemas expertos (entre las referencias figuran el modelo de razonamiento médico incierto de Shortliffe y Buchanan de 1975 y el sistema experto de prospección minera PROSPECTOR). Sobre el nombre, escribe que lo llama Bayes Network para destacar que los valores de probabilidad proceden del juicio humano, más que por utilizar el teorema de Bayes (también lo llama Influence Network).
Lo que aún no se sabe:El propio Pearl escribe en el resumen que la actualización correcta de toda la red mediante solo intercambios locales se limita a redes con un único camino entre dos puntos cualesquiera. Para redes con varios caminos, este informe solo analiza una orientación de cálculo.
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.
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_bayesnet.py
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.
A partir de finales de ajedrez
Según el artículo, el antepasado de esta familia (los métodos relacionados con ID3) es CLS, de Hunt y sus colegas (libro de 1966). ID3 (1979) nació de un problema planteado por Michie: distinguir posiciones de finales de ajedrez (rey y torre contra rey y caballo) solo a partir de características de su forma.
Fuentes originales y grado de certeza (1)¿Qué pregunta se hace primero?
marzo de 1986Verificado en la fuente originalLas fuentes discrepan
Árboles de decisión: en 1986, Quinlan reunió ID3 en un artículo. Sus orígenes siguen dos líneas: CLS de Hunt y sus colaboradores en 1966 y los árboles estadísticos desde 1963
Un árbol de decisión es un método de clasificación que organiza preguntas, como qué tiempo hace o si la humedad es alta, en forma de ramas. Se siguen las ramas según las respuestas y, al llegar a una hoja, se obtiene el resultado (clase). ID3 construye el árbol eligiendo primero la pregunta que aporta más información al dividir los datos (ganancia de información, medida en bits), y repite el procedimiento en cada rama. Quinlan (J. R. Quinlan, New South Wales Institute of Technology) calculó un ejemplo en su artículo de 1986 Inducción de árboles de decisión (Induction of Decision Trees). Utilizó las condiciones meteorológicas de 14 mañanas de sábado (tiempo, temperatura, humedad y viento, con 2 clases, P o N) y mostró que dividir según el tiempo aportaba 0.246 bits, el máximo, por lo que el tiempo ocupaba la raíz del árbol. Según el artículo, esta familia de métodos procede de CLS, de Hunt y sus colaboradores (libro de 1966). ID3 (1979) se desarrolló al abordar una tarea propuesta por Donald Michie: distinguir posiciones de un final de ajedrez (rey y torre contra rey y caballo) solo a partir de sus características de forma.
Lo que suele decirse:Se suele decir: “Los árboles de decisión nacieron de la investigación en IA (aprendizaje automático)” Según la fuente original:También hay otra línea en estadística. AID, de Morgan y Sonquist (1963), se considera el primer árbol de regresión publicado, y CART, de Breiman y sus colaboradores (1984), renovó el interés con un método que hace crecer mucho el árbol y después lo poda mediante validación cruzada (explicación de Loh de 2014). CART no aparece en la bibliografía del artículo de Quinlan de 1986: las dos líneas crecieron por separado. Además, este artículo contiene datos con la misma estructura que el ejemplo de tiempo y tenis frecuente en los libros de texto, pero las clases son solo P y N y no aparece la palabra tenis.
3 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:Año de publicación del libro de CART: Loh (2014) cita Breiman et al. (1984), mientras que el manuscrito de Friedman de 1999 cita Breiman, Friedman, Olshen y Stone 1983 (este sitio no ha consultado el propio libro).
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.
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_id3.py
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.
Una pregunta sobre los animales
El punto de partida de la tesis de Watkins fue una pregunta de ecología del comportamiento: cómo aprenden los animales, a partir de la experiencia, a actuar de manera óptima. No partió de juegos ni de robots. Escribió que la idea era muy sencilla y que, en un campo estudiado durante tanto tiempo, no podía creer que nadie hubiera pensado en ella.
El artículo de Miyazaki y sus colegas compara ambos métodos: el aprendizaje Q requiere muchísimos ensayos para conocer bien el entorno, mientras que profit sharing necesita muchos menos. En esa época no había un único método considerado la respuesta correcta.
Fuentes originales y grado de certeza (3)Aprender de las recompensas
1988Verificado en la fuente original
Aprendizaje TD: en 1988, Sutton formuló la teoría de un método que aprende del error respecto a la siguiente predicción sin esperar al resultado final
Richard Sutton, de GTE Laboratories, formuló teóricamente el método TD (temporal-difference, aprendizaje por diferencias temporales) para aprender a predecir el futuro a partir de la experiencia. El aprendizaje supervisado habitual utiliza el error entre la predicción y el resultado final para corregir la predicción. En cambio, TD utiliza el error entre “la predicción de hoy” y “la predicción de mañana” para corregir la de hoy. El artículo pone como ejemplo a una persona que predice el tiempo. Supóngase que cada día predice si lloverá el sábado, con un 50% el lunes y un 75% el martes. TD eleva la predicción de días como el lunes sin esperar al resultado del sábado. Sutton argumentó que así se puede calcular un poco cada día, utilizar menos memoria y, en muchos casos, predecir con mayor precisión. Demostró la convergencia y la optimalidad para un caso especial. Como ejemplo de verificación, utilizó un paseo aleatorio que empieza en el punto central D, avanza al azar un paso a izquierda o derecha y termina al llegar a A en el extremo izquierdo o a G en el derecho. El sistema aprendía la probabilidad de llegar a G desde cada punto.
Lo que suele decirse:Se suele decir: “Sutton inventó el aprendizaje TD en 1988” Según la fuente original:El propio Sutton dice en el resumen y la introducción que TD ya se utilizaba en el programa de damas de Samuel (1959), la cadena de cubos de Holland y su propio evaluador adaptativo (Adaptive Heuristic Critic), pero no se comprendía bien. Cita las damas de Samuel como el uso más temprano y conocido y escribe que corregía la evaluación de una posición con la diferencia entre las evaluaciones de dos posiciones consecutivas. La novedad del artículo de 1988 fue aislar TD como método de aprendizaje de predicciones, demostrar su convergencia y optimalidad y compararlo con el aprendizaje supervisado.
Lo que aún no se sabe:Sutton argumentaba que la mayoría de los problemas en los que entonces se utilizaba aprendizaje supervisado eran en realidad problemas de predicción donde TD podía ser ventajoso (perspectiva de 1988). Este sitio no ha comprobado hasta qué punto se cumplió esa perspectiva.
Aprendizaje Q: Watkins lo presentó en 1989 en una tesis doctoral sobre cómo los animales aprenden acciones óptimas (demostración detallada en 1992)
Christopher Watkins planteó cómo pueden los animales aprender acciones óptimas a partir de la experiencia en su tesis doctoral de King's College, Learning from Delayed Rewards (mayo de 1989). La ecología del comportamiento obtiene las acciones óptimas mediante programación dinámica (método que calcula la mejor acción considerando todos los resultados futuros), pero cuesta imaginar que los animales hagan ese cálculo. Watkins presentó el aprendizaje Q de un paso, que actualiza poco a poco el valor de una acción a en un estado x, Q(x, a), utilizando la recompensa r de cada ensayo y el mayor valor Q del siguiente estado. En el apéndice demostró que, aun sin un modelo del entorno, se aproxima al valor de la acción óptima si se prueban repetidamente todas las acciones en todos los estados. En 1992, Watkins y Dayan publicaron en una revista académica un artículo breve con la demostración detallada.
Lo que suele decirse:Se suele decir: “El aprendizaje Q nació en el artículo de Watkins y Dayan de 1992” Según la fuente original:El propio aprendizaje Q ya estaba en la tesis de Watkins de mayo de 1989. El artículo de 1992 era una nota breve (Technical Note) que detallaba la demostración de convergencia esbozada en la tesis. Además, la tesis partía de una pregunta de ecología del comportamiento: cómo aprenden los animales acciones óptimas a partir de la experiencia, en lugar de juegos o robots. Watkins escribió que era una idea muy sencilla y que, hasta donde sabía, no se había propuesto antes, aunque le resultaba difícil creer que nadie la hubiera pensado en un campo investigado durante tanto tiempo.
Lo que aún no se sabe:Según el prefacio de la tesis, Sutton señaló un punto difícil del aprendizaje Q. Este sitio no ha comprobado cuál era.
Teoría del profit sharing: en 1994, Kazuteru Miyazaki, Masayuki Yamamura y Shigenobu Kobayashi, del Instituto Tecnológico de Tokio, demostraron las condiciones para que el aprendizaje por refuerzo que reparte la recompensa entre una secuencia de acciones no aprenda acciones inútiles, y recibieron el premio al mejor artículo de la Sociedad Japonesa de Inteligencia Artificial
El aprendizaje por refuerzo (un método que aprende cómo actuar mediante pruebas, usando las recompensas como guía) incluye métodos como TD y Q-learning, que actualizan el valor de las acciones a cada paso, y profit sharing, que refuerza toda la secuencia de acciones (episodio) cuando se obtiene una recompensa. Kazuteru Miyazaki, Masayuki Yamamura y Shigenobu Kobayashi analizaron matemáticamente cómo repartir la recompensa entre las acciones según el número de pasos que las separa de ella (función de refuerzo). Demostraron una condición necesaria y suficiente para no aprender reglas (acciones) ineficaces que producen desvíos (teorema de supresión de reglas ineficaces), y mostraron que, bajo la misma condición, se puede aprender una política de acción que permita seguir obteniendo recompensas. El artículo compara Q-learning, que requiere muchísimas pruebas para comprender con precisión el entorno, con profit sharing, que necesita muchas menos pruebas para aprender. El artículo recibió el premio al mejor artículo de la Sociedad Japonesa de Inteligencia Artificial correspondiente al año fiscal 1994.
Lo que suele decirse:Se suele pensar que “la investigación en aprendizaje por refuerzo se limita a las líneas de TD y Q-learning desarrolladas en otros países” Según la fuente original:En Japón, en la década de 1990, se investigó la teoría del profit sharing, que refuerza toda una secuencia de acciones cuando aparece una recompensa, y un artículo de 1994 recibió el premio al mejor artículo de la Sociedad Japonesa de Inteligencia Artificial. El propio artículo compara la gran cantidad de pruebas que necesita Q-learning con las muchas menos que requiere profit sharing. No había un único método correcto.
Lo que aún no se sabe:Este sitio no ha comprobado hasta qué punto se utilizó después esta condición en robots reales u otras aplicaciones.
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
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_q_learning.py
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.
Una comparación con las apuestas de caballos
El nombre AdaBoost procede del ajuste adaptativo (adaptively) de los pesos según los errores. El artículo de 1997 comienza con la historia de alguien que pierde repetidamente en las carreras de caballos y redistribuye sus apuestas según los resultados de sus amigos.
El propio Friedman escribió que Rätsch y sus colegas (1998) y Breiman (1999) ya habían señalado la interpretación del boosting como un cálculo de descenso por una pendiente.
Fuentes originales y grado de certeza (2)Combinar aprendices débiles según los errores
junio de 1990–1997Verificado en la fuente original
Boosting: Schapire demostró en 1990 que el aprendizaje débil puede convertirse en fuerte; Freund y Schapire presentaron AdaBoost en 1995
Boosting crea repetidamente clasificadores débiles, solo algo mejores que el azar, entrenándolos con más peso para los datos que se clasificaron mal en la ronda anterior. Al final los combina mediante una votación mayoritaria ponderada para crear un clasificador fuerte. Su origen fue una pregunta de teoría de la computación. Kearns y Valiant dejaron como problema abierto (problema del boosting de hipótesis) si el aprendizaje débil, apenas mejor que el azar, y el fuerte, que puede alcanzar cualquier grado de precisión, tenían la misma capacidad. Schapire (R. E. Schapire, MIT Laboratory for Computer Science) demostró que sí en su artículo de 1990 La fuerza de la capacidad de aprendizaje débil (The Strength of Weak Learnability), y mostró cómo convertir un método débil en uno fuerte. Freund (Y. Freund) y Schapire presentaron AdaBoost en un congreso de Barcelona en marzo de 1995 (artículo publicado en una revista académica en 1997). Según el artículo, el nombre procede de que, a diferencia de los métodos anteriores, cambia los pesos de forma adaptativa (adaptively) según los errores de los clasificadores débiles. El artículo comienza con la comparación con alguien que pierde repetidamente en las carreras de caballos y redistribuye sus apuestas según los resultados de sus amigos.
Lo que suele decirse:Se suele pensar: “Boosting nació como un recurso práctico para reunir modelos débiles” Según la fuente original:Comenzó como una pregunta de teoría de la computación. Kearns había argumentado que repetir el mismo aprendizaje y hacer una votación mayoritaria simple no bastaba. También se suele decir: “Boosting no sobreajusta”. Sin embargo, en una explicación de 2013, el propio Schapire muestra un ejemplo donde la tasa de error de prueba sigue bajando después de llegar a 0 en el entrenamiento (del 8.4% en la ronda 5 al 3.1% en la 1,000), pero escribe que boosting también puede sobreajustar.
Lo que aún no se sabe:¿Por qué sigue bajando el error de prueba aunque el de entrenamiento haya llegado a 0? La explicación de Schapire de 2013 dice que la teoría basada en márgenes es la única que puede explicar los casos sin sobreajuste. También dice que las garantías numéricas son muy poco ajustadas.
24 de febrero de 1999–2001Verificado en la fuente original
Potenciación por gradiente: en 1999, Friedman generaliza como descenso de gradiente la técnica de cubrir poco a poco los residuos con pequeños árboles de decisión
La potenciación por gradiente mejora poco a poco las predicciones mediante un proceso repetido: un pequeño árbol de decisión predice el error (residuo) entre la predicción del modelo actual y la respuesta correcta, y se añade una pequeña parte de ese árbol. Jerome H. Friedman (Stanford University) escribió un artículo fechado el 24 de febrero de 1999, titulado (Greedy Function Approximation: A Gradient Boosting Machine; IMS 1999 Reitz Lecture, publicado en The Annals of Statistics en 2001). Interpretó esa acumulación de sumas como un cálculo que reduce poco a poco el error (pérdida) en la dirección de descenso más pronunciado dentro del espacio de funciones (método de máximo descenso). Si se utiliza el error cuadrático como pérdida, cada árbol aprende directamente los residuos actuales. El procedimiento también se aplica a otras pérdidas, como el error absoluto, la pérdida de Huber y la verosimilitud logística para clasificación. También señala que reducir la cantidad añadida en cada paso mediante la tasa de aprendizaje ν (contracción) suele mejorar los resultados.
Lo que suele decirse:Se suele pensar que “la potenciación por gradiente es una técnica reciente de los concursos de aprendizaje automático” Según la fuente original:El artículo fundamental es un manuscrito de febrero de 1999, presentado como IMS 1999 Reitz Lecture y publicado en The Annals of Statistics en 2001. El propio Friedman escribe que la interpretación de la potenciación como descenso de gradiente ya se había señalado en investigaciones anteriores de aprendizaje automático (Rätsch y sus colegas en 1998 y Breiman en 1999).
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
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_boosting.py
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).
Fuentes originales y grado de certeza (1)Maximizar el margen desde el límite
julio de 1992Verificado en la fuente original
Máquina de vectores de soporte con kernels: en 1992, Boser, Guyon y Vapnik presentaron la maximización del margen para fronteras curvas
Una máquina de vectores de soporte (SVM) traza una frontera entre 2 clases de manera que sea máxima la distancia (margen) desde la frontera hasta los puntos más cercanos. Boser (B. E. Boser, University of California, Berkeley; parte del trabajo se hizo en AT&T Bell Laboratories), Guyon (I. M. Guyon) y Vapnik (V. N. Vapnik, ambos en AT&T Bell Laboratories) resolvieron el problema reformulándolo para utilizar solo una función que mide la similitud entre puntos (kernel), K(x, x'), en forma dual. Lo presentaron en Un algoritmo de entrenamiento para clasificadores de margen óptimo (A Training Algorithm for Optimal Margin Classifiers), en COLT '92, julio de 1992. Esto permite maximizar el margen con el mismo cálculo también para fronteras curvas, como las polinómicas o las basadas en funciones de base radial. La frontera depende solo de unos pocos datos de entrenamiento, los más cercanos a ella (supporting patterns en el artículo). Con dígitos manuscritos de correo real (7,300 imágenes de entrenamiento y 2,000 de prueba), un kernel polinómico de grado 4 obtuvo un error del 4.9%, ligeramente menor que el 5.1% informado para una red neuronal de 5 capas con los mismos datos.
Lo que suele decirse:Se suele decir: “Cortes y Vapnik inventaron la máquina de vectores de soporte en 1995” Según la fuente original:Boser, Guyon y Vapnik ya habían presentado en COLT de 1992 el método que maximiza el margen y usa kernels para fronteras curvas. Ese artículo no contiene la expresión support vector: llama supporting patterns a los puntos que sostienen la frontera. Para la propia idea del kernel, cita como ejemplo el método de funciones de potencial (potential function) de Aizerman, Braverman y Rozonoer de 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.
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_svm.py
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.
Lo que escribió Breiman
Escribió que, al aumentar la cantidad de árboles, la tasa de error se estabiliza en cierto valor (por la ley fuerte de los grandes números), por lo que el sobreajuste no es un problema. Los árboles de Ho mejoraban la precisión tanto en datos de entrenamiento como en datos nuevos.
Aproximadamente un tercio: al seleccionar n veces al azar entre n datos, permitiendo repeticiones, la proporción que nunca se selecciona es aproximadamente(1 − 1
n)n ≒ 0.37. Estos son los datos out-of-bag.
Fuentes originales y grado de certeza (1)Votar entre árboles creados al azar
octubre de 2001Verificado en la fuente original
Bosques aleatorios: en 2001, Breiman combina el voto mayoritario de muchos árboles de decisión modificados aleatoriamente. En 1995 ya existían los random decision forests de Ho
Los bosques aleatorios construyen muchos árboles de decisión en condiciones ligeramente distintas y deciden la predicción por mayoría de votos. Cada árbol se entrena con ejemplos elegidos al azar de los datos de entrenamiento, y en cada bifurcación se escoge la mejor división entre un subconjunto de características seleccionado aleatoriamente. En su artículo de 2001, (Random Forests), Leo Breiman (Departamento de Estadística, University of California, Berkeley) escribió que, al aumentar el número de árboles, la tasa de error converge a un valor constante por la ley fuerte de los grandes números, por lo que el sobreajuste no plantea un problema. También mostró que el error del bosque depende de la fuerza de cada árbol y de la correlación entre árboles. El tercio aproximado de ejemplos no seleccionado al azar (out-of-bag) permite estimar el error sin datos de prueba separados ni validación cruzada. En 1995, Tin Kam Ho (AT&T Bell Laboratories) había mostrado en (Random Decision Forests) que combinar árboles que usan subconjuntos aleatorios de características mejora la precisión del reconocimiento de dígitos manuscritos tanto en los datos de entrenamiento como en datos nuevos.
Lo que suele decirse:Se suele decir que “Breiman ideó los bosques aleatorios por sí solo” Según la fuente original:Ho había presentado en 1995 los random decision forests, de nombre muy parecido. El propio Breiman cita en su artículo de 2001 antecedentes como el bagging (1996), los métodos de selección aleatoria de candidatos a bifurcación y el método random subspace de Ho. También señala la influencia del artículo sobre caracteres manuscritos de Amit y Geman de 1997, y agrupa estas ideas bajo el nombre random forests. Random Forests es, además, una marca de Breiman y Adele Cutler.
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
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_random_forest.py
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.
El método para calcularla con computadoras llegó mucho después
Al principio de su artículo, Beltrami escribió que quería dar a los lectores jóvenes una oportunidad de familiarizarse con este tipo de álgebra. La descomposición en sí es matemática del siglo 19. El método para calcularla rápida y precisamente con computadoras apareció en 1965 (Golub y Kahan), según Stewart (1992).
Fuentes originales y grado de certeza (2)Cualquier tabla se descompone en 3 factores
1873–1874Verificado en la fuente original
Descomposición en valores singulares ── Beltrami en 1873 y Jordan en 1874 muestran que cualquier matriz se puede dividir en 3 pasos: girar, estirar o encoger, y girar
La descomposición en valores singulares (SVD) permite expresar cualquier matriz (una tabla de números en filas y columnas que representa una transformación de vectores) como el producto de 3 transformaciones: cambiar la orientación (girar) → estirar o encoger en cada eje → girar de nuevo. Los factores de estiramiento o encogimiento se llaman valores singulares. Conservar solo los mayores permite aproximar bien la tabla original con pocos números; por eso se utiliza para predecir preferencias (recomendaciones) y calcular análisis de componentes principales. Eugenio Beltrami publicó por primera vez esta descomposición en 1873, en una revista italiana de matemáticas para universitarios. Al principio escribió, en esencia, que quería ofrecer a los lectores jóvenes una oportunidad de familiarizarse con este tipo de cálculos algebraicos. Al año siguiente, en 1874, Camille Jordan presentó de forma independiente la misma descomposición de manera más completa.
Lo que suele decirse:Suele creerse que “la descomposición en valores singulares es una técnica nueva creada para trabajar con datos en computadoras” Según la fuente original:La propia descomposición procede de las investigaciones matemáticas de Beltrami en 1873 y Jordan en 1874. El artículo de Beltrami apareció en una revista para universitarios como material para familiarizarse con el álgebra. El método para calcularla de forma rápida y precisa con computadoras llegó mucho después, en 1965 (Golub y Kahan; Stewart, 1992).
Lo que aún no se sabe:Según Stewart (1992), el uso del término valor singular (singular value) todavía variaba en la primera mitad del siglo 20; para este sitio no se han rastreado las fuentes originales para determinar cuándo se consolidó su significado actual.
La mejor aproximación de rango inferior ── Eckart y Young la resuelven en 1936 en relación con el análisis factorial (redescubrimiento del teorema de Schmidt de 1907)
Carl Eckart y Gale Young, de la Universidad de Chicago, resolvieron el problema de aproximar una matriz mediante otra de rango inferior (con menos direcciones independientes) minimizando la suma de los errores al cuadrado. Según el resumen del artículo, transformar primero la matriz a una forma normal (la actual descomposición en valores singulares) facilita la solución. Esta siempre existe y normalmente es única. Se obtiene haciendo 0 los valores singulares pequeños en la descomposición (explicación de Stewart, 1992). El resumen dice que el problema está estrechamente relacionado con la idea básica del análisis factorial: explicar tablas de notas de exámenes con pocos factores. El artículo apareció en el volumen 1 de Psychometrika, una revista académica de medición psicológica fundada ese año.
Lo que suele decirse:Suele decirse que “Eckart y Young (1936) descubrieron el teorema según el cual la mejor aproximación de rango inferior es la matriz que descarta los valores singulares pequeños” (llamado teorema de Eckart–Young) Según la fuente original:Según Stewart (1992), Erhard Schmidt había demostrado este teorema de aproximación en 1907 al estudiar ecuaciones integrales, y Eckart y Young lo redescubrieron. Stewart escribe que ese nombre es habitual, pero incorrecto.
Lo que aún no se sabe:Para este sitio no se ha comprobado si Eckart y Young conocían el trabajo de Schmidt de 1907 (no se ha abierto el texto completo).
Whence Principal Components? (Lawrence Hubert · 2016 · p.1 The Journal of Educational Psychology as a Precursor to Psy… · Resumen secundario)
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)
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_svd.py
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.
Detalles del concurso
En esa época, Netflix alquilaba películas en DVD. En los datos de valoraciones se habían sustituido los nombres por números. La tasa de aprendizaje de Funk era 0.001. El 21 de septiembre de 2009 ganó BellKor's Pragmatic Chaos, que combinaba cientos de modelos. El segundo equipo obtuvo la misma puntuación (0.8567); ganó el que había entregado su resultado unos 20 minutos antes. Después, la empresa se centró en la transmisión de contenidos y la (traducción) pasó a ser solo una parte de las recomendaciones (blog de 2012).
Incluso sin nombres
Se pensaba que, al eliminar los nombres, no se podía saber a quién pertenecían los datos. Pero los investigadores demostraron que podían identificar a personas comparándolos con valoraciones de películas publicadas abiertamente, y el segundo concurso se canceló.
Fuentes originales y grado de certeza (2)Aprender de una tabla llena de huecos
2 de octubre de 2006–2009Verificado en la fuente original
“Premio Netflix” (Netflix Prize), concurso de predicción de gustos cinematográficos con un premio de 1 millón de dólares (2006–2009): la victoria se decide por 20 minutos
En octubre de 2006, Netflix, que alquilaba películas en DVD, organizó un concurso: ofrecía 1 millón de dólares a quien predijera las valoraciones de películas con un 10% más de precisión que su sistema de recomendación Cinematch. Distribuyó más de 100 millones de valoraciones (de 1 a 5 estrellas) de unas 18,000 películas, hechas por unas 480,000 personas cuyos nombres se sustituyeron por números. Casi 3 años después, el 21 de septiembre de 2009, ganó BellKor's Pragmatic Chaos. El segundo equipo obtuvo la misma puntuación (error de 0.8567, mejora del 10.06%), pero ganó quien envió su resultado unos 20 minutos antes, conforme a la regla de prioridad por orden de entrega en caso de empate.
Lo que suele decirse:Se suele pensar que “Netflix mejoró sus recomendaciones con el sistema encontrado en el concurso de 1 millón de dólares” Según la fuente original:Según el blog de Netflix (2012), se aplicaron los 2 métodos del premio intermedio del primer año, pero no se implantó la combinación de cientos de modelos que ganó el millón: la mejora de precisión no compensaba el esfuerzo. Mientras tanto, la empresa pasó del DVD al video por internet, y la se convirtió en solo una parte del sistema de recomendación. Otra idea: “si se eliminan los nombres, no se puede saber de quién son los datos” → Investigadores demostraron que podían identificar personas comparando esos datos con valoraciones públicas de películas, y se canceló el segundo concurso (carta de la FTC).
11 de diciembre de 2006Verificado en la fuente original
Descomposición de una tabla de preferencias: en 2006, Simon Funk publica en su blog el método de Netflix Prize que aprende solo de las entradas conocidas de una tabla llena de huecos
Simon Funk, participante de Netflix Prize, publicó íntegramente su método en su blog el 11 de diciembre de 2006 (entonces empataba en el tercer puesto). Los datos contenían 100 millones de valoraciones de unas 17,000 películas realizadas por unas 500,000 personas. En una matriz de usuarios × películas, faltaban 8.4 mil millones de los aproximadamente 8.5 mil millones de elementos. Funk representó los gustos de cada usuario y las características de cada película mediante vectores de 40 dimensiones, y predijo las valoraciones con su producto escalar (unos 20 millones de parámetros, 1/400 de la matriz original). Tiene la misma forma que una aproximación mediante descomposición en valores singulares (SVD) que conserva los 40 valores singulares principales, pero la SVD convencional no se puede calcular con valores ausentes. Por ello, calculó el error de predicción solo para las valoraciones conocidas y ajustó repetidamente los parámetros un poco en la dirección que reducía el error (descenso de gradiente, tasa de aprendizaje de 0.001). Él lo llama una SVD modificada.
Lo que suele decirse:Se dice que “en Netflix Prize se utilizó la descomposición en valores singulares (SVD)” Según la fuente original:El método que los participantes llamaban SVD era una factorización de matrices: aproxima una matriz con muchos valores ausentes mediante el producto de 2 matrices estrechas y alargadas, ajustándose a los elementos conocidos. No era exactamente la descomposición en valores singulares en sentido matemático estricto. Funk explica que la SVD convencional no sirve con 8.4 mil millones de huecos y que su método calcula el gradiente del error para aprender solo de las valoraciones conocidas; lo llama una SVD modificada. El blog de Netflix también habla de factorización de matrices, que los participantes solían llamar SVD.
Lo que aún no se sabe:Este sitio no ha comprobado quién había ideado, antes de Funk, métodos semejantes para predecir preferencias mediante la factorización de matrices con valores ausentes.
2 fuentes originales y cómo se verificaron
Netflix Update: Try This at Home (Simon Funk · 2006 · Texto del artículo (explicación del problema; 40 caracterís… · Fuente original)
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
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_funk_mf.py
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.
Lo que no se sabe
En 2009, ImageNet contenía 3.2 millones de imágenes en 5247 grupos. El artículo no indica cuántas personas etiquetaron los datos, en qué países ni por cuánto dinero.
Fuentes originales y grado de certeza (2)¿Quién puso las etiquetas correctas?
2 de noviembre de 2005Verificado en la fuente original
Amazon lanza , que permite a las computadoras encargar pequeñas tareas a personas ()
Amazon presentó , un sistema que permite a un programa encargar pequeñas tareas a personas y recibir los resultados. El anuncio llamó al uso de computadoras para encargar trabajo a muchas personas y utilizar sus resultados. Posteriormente, en ImageNet de 2009, se empleó para comprobar que cada foto mostraba realmente el objeto indicado. El artículo de ImageNet lo describe como una plataforma donde quienes realizan las tareas reciben un pago.
Lo que suele decirse:Se suele decir que “Amazon explicó que el nombre procede de la máquina de ajedrez de 1770, el Turco, que ocultaba una persona en su interior” Según la fuente original:Ni el anuncio de Amazon de 2005 ni la página principal actual que abrió este sitio explican el origen del nombre (la explicación es frecuente, pero aún no se han encontrado las palabras originales de Amazon). La expresión del anuncio fue .
Fei-Fei Li y sus colegas de Princeton presentan ImageNet, una colección de millones de fotos etiquetadas. Las verificaron personas que aceptaban trabajos por internet
Li y sus colegas presentaron ImageNet, basado en WordNet, un diccionario que organiza conceptos jerárquicamente. El proyecto reúne en promedio entre 500 y 1,000 fotos por cada uno de unos 80,000 grupos de sustantivos (el ejemplo del artículo es ). En la presentación ya tenía 12 áreas, 5,247 categorías y 3.2 millones de imágenes. Las fotos se recogían mediante buscadores, y personas de todo el mundo que recibían un pago por las tareas en Amazon Mechanical Turk comprobaban una por una si el objeto indicado aparecía correctamente. La decisión se tomaba mediante los votos de varias personas.
Lo que suele decirse:Se suele decir que “la IA aprendió sola mirando fotos” Según la fuente original:Muchísimas personas que trabajaban por internet a cambio de un pago comprobaban cada foto y le asignaban la etiqueta correcta para el entrenamiento (página 4 del artículo). Las personas dentro de una máquina no son solo una historia del autómata de ajedrez de 1770.
Lo que aún no se sabe:El artículo no indica cuántas personas realizaron las tareas, en qué países residían ni cuánto cobraban (sin comprobar).
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
El razonamiento del artículo
Los mayores éxitos del aprendizaje automático aplicado al lenguaje habían sido el reconocimiento estadístico del habla y la traducción automática. Según el artículo, esto se debía a que en el mundo real ya existía (traducción). También mencionaba los datos de texto de 1 billón de palabras publicados por Google en 2006.
Tamaño de los datos (abrir “Detalles: tamaño de los datos” en la figura)
Los datos de este capítulo incluyen 14 registros (tabla del árbol de decisión de 1986), 97 especies (abejas de 1958), 405 resúmenes (1961), 7300 imágenes (dígitos manuscritos de 1992), 100 millones de valoraciones (Netflix de 2006), 1 billón de palabras (Google de 2006), 3.2 millones de imágenes (ImageNet de 2009) y 10 millones de videos (gato de 2012).
Fuentes originales y grado de certeza (1)Separar entrenamiento y prueba para comprobar
marzo de 2009Verificado en la fuente original
Tres investigadores de Google publican : dejar de buscar teorías de gran elegancia y apoyarse en los datos
Halevy, Norvig y Pereira, de Google, escribieron que los mayores éxitos del aprendizaje automático aplicado al lenguaje eran el reconocimiento estadístico del habla y la traducción automática estadística. Explicaban que la traducción, al igual que la transcripción del habla, se realiza habitualmente cada día para atender necesidades reales, por lo que ya existe en el mundo lo que describen como . También mencionaron que en 2006 Google había publicado datos de textos con 1 billón de palabras (frecuencias de secuencias de hasta 5 palabras). Afirmaron: (traducción) basados en menos datos, y escribieron en el párrafo final: (traducción).
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)
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_digits_train_test.py
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.
Google Brain
Equipo de Google que probaba cálculos con redes neuronales enormes. Comenzó su actividad en 2011 y presentó en un artículo de 2012 DistBelief, un sistema para entrenar una red en miles de computadoras. En abril de 2023 se unió a DeepMind y pasó a ser Google DeepMind.
Fuentes originales y grado de certeza (3)Muchos cálculos iguales al mismo tiempo
8 de noviembre de 2006Verificado en la fuente originalLas fuentes discrepan
NVIDIA presenta CUDA, un sistema para utilizar las GPU, destinadas a dibujar imágenes, también en otros cálculos
Las GPU (chips para procesar imágenes) que dibujan los gráficos de los juegos pueden realizar el mismo cálculo simultáneamente en muchos pequeños núcleos de cálculo (hasta 128 en GeForce 8800 GTX). Junto con GeForce 8800, NVIDIA presentó , un sistema que permite utilizar la GPU para cálculos distintos del procesamiento de imágenes mediante un lenguaje de programación habitual, C. Más tarde se convirtió en una herramienta para entrenar redes neuronales rápidamente (también utilizaron GPU el artículo de Stanford de 2009 y el equipo ganador del concurso de reconocimiento de imágenes de 2012).
1 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:Las fuentes difieren en el año: se anunció en un documento técnico de NVIDIA de noviembre de 2006. La lista de posibles acontecimientos escrita de memoria al iniciar este sitio indicaba 2007. Es posible que 2007 sea el año de la publicación general de las herramientas, pero no se ha comprobado en fuentes originales.
Ng y sus colegas de Stanford muestran que una GPU puede acelerar hasta 70 veces el entrenamiento de redes neuronales
Raina, Madhavan y Ng entrenaron redes profundas de aprendizaje no supervisado con una GPU para videojuegos (NVIDIA GeForce GTX 280). Fueron hasta 70 veces más rápidos que con una CPU corriente de 2 núcleos. Para una red de 4 capas con 100 millones de valores numéricos, describieron la reducción del tiempo de entrenamiento así: (traducción). El artículo señalaba que, pese a la importancia de aprender con grandes cantidades de datos, la lentitud del cálculo limitaba los experimentos a una pequeña escala.
Comienza “Google Brain”, el equipo de Google que experimenta con redes neuronales de gran escala
Según la página oficial de X, una división de Google (al pie figura “X, una división de Google LLC” (traducción) y el título es (Brain - A Google X Moonshot)), el equipo Google Brain comenzó en 2011 y pasó de X a Google a finales de 2012. En diciembre de 2011, investigadores de Google y de la Universidad de Stanford publicaron la primera versión de un artículo sobre aprendizaje a partir de imágenes de YouTube sin etiquetas: el posterior artículo de Google sobre gatos. En un artículo de 2012 presentaron DistBelief, un sistema para entrenar una gran red neuronal en miles de computadoras, e informaron que habían entrenado una red 30 veces mayor que las descritas anteriormente y acelerado también el entrenamiento del reconocimiento de voz comercial. En abril de 2023, Google anunció la unión de este equipo con DeepMind para formar Google DeepMind.
Lo que suele decirse:Suele decirse que “el aprendizaje profundo se extendió gracias a las GPU, chips para procesar imágenes” Según la fuente original:Los grandes experimentos de Google de 2012 (el artículo de los gatos y DistBelief) usaron miles de computadoras convencionales, con, por ejemplo, 16,000 núcleos de CPU. El artículo dice que las GPU de entonces difícilmente aceleraban los modelos demasiado grandes para su memoria, de menos de 6 GB. El equipo ganador de la competencia de reconocimiento de imágenes de ese mismo año usó GPU: había más de un 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).
Blog de Google (6 de agosto de 2012)
La nueva versión de Android se presentó explicando que, al hablar al dispositivo, (traducción).
Watson en el concurso de televisión (2011)
En febrero de 2011, Watson, de IBM, venció a 2 campeones históricos de Jeopardy! (77,147 dólares frente a 24,000 y 21,600). Reunía mediante aprendizaje automático pruebas para las respuestas candidatas y pulsaba el botón solo cuando su confianza era suficiente. El propio equipo escribió en 2010 que (traducción). En la última pregunta de la primera partida respondió (traducción) y se equivocó.
Fuentes originales y grado de certeza (5)La voz antes que las imágenes
2009–2012Verificado en la fuente original
La IA de aprendizaje profundo logró resultados en el antes que en imágenes (2009–2012)
El aprendizaje profundo (un sistema de IA que aprende mediante redes neuronales de muchas capas) comenzó hacia 2009 a superar en reconocimiento del habla los métodos estadísticos (GMM) utilizados durante mucho tiempo. En 2012, 4 grupos de investigación de la Universidad de Toronto, Microsoft Research, Google e IBM publicaron un artículo que describían así: . Entre sus resultados mostraron una reducción de la proporción de palabras erróneas en pruebas de transcripción de conversaciones del 27.4% al 18.5% (aproximadamente un tercio). En su blog del 6 de agosto de 2012, Google escribió que, al hablar al teléfono en la nueva versión de Android, (traducción).
Lo que suele decirse:Se suele decir que “el primer gran éxito del aprendizaje profundo fue el concurso de imágenes de otoño de 2012, ILSVRC 2012” Según la fuente original:Las fuentes originales muestran resultados en reconocimiento del habla desde 2009, una reducción del error de aproximadamente un tercio en la transcripción de conversaciones en 2011 (artículo de los 4 grupos) y su uso por Google en el reconocimiento del habla de Android en agosto de 2012 (blog de Google). Ambos ocurrieron antes de los resultados del concurso de imágenes de octubre de 2012. Además, el blog de Google sitúa los primeros intentos de usar redes neuronales para el habla en un artículo de finales de los años ochenta, con 2 investigadores de ATR, en Osaka, como coautores.
Lo que aún no se sabe:Al revisar los resultados, el artículo de los 4 grupos atribuye la mayor parte de las mejoras a “aprovechar la información de los segmentos temporales vecinos” (traducción) y al “modelado de estados compartidos dependientes del contexto” (traducción). Pero también afirma: “no hay motivo para creer ... que sean los tipos óptimos de unidades ocultas o las arquitecturas de red óptimas” (traducción) (página 13 del PDF). La explicación de por qué las redes neuronales profundas eran mejores todavía estaba en desarrollo.
5 de agosto de 2010Verificado en la fuente originalLas fuentes discrepanJapón
NICT, un instituto público japonés de investigación, lanza en todo el mundo la aplicación para teléfonos inteligentes “VoiceTra”, que traduce lo que se dice y responde con voz
En el verano de 2010, NICT (Instituto Nacional de Tecnología de la Información y las Comunicaciones), un instituto público japonés de investigación, publicó gratuitamente en todo el mundo, en App Store, la aplicación de traducción de voz VoiceTra y la de traducción de texto TexTra. Al hablar al iPhone, VoiceTra traduce a otro idioma y responde con voz. Los cálculos de traducción se realizan en un servidor. Se podía usar con voz en japonés, chino mandarín, inglés, indonesio y vietnamita (el malayo estaba en preparación). Estaba dirigida a conversaciones de viaje, y NICT describió su capacidad de traducción de voz como “una capacidad lingüística aproximadamente equivalente a la de una persona con 600 puntos en el TOEIC” (traducción). El lanzamiento buscaba evaluar su rendimiento y estudiar su facilidad de uso. Según un anuncio de NICT de 2015, esta tecnología también se usó en servicios reales, como una aplicación del Aeropuerto Internacional de Narita. Además, se convirtió en la aplicación central del del Ministerio de Asuntos Internos y Comunicaciones (abril de 2014; buscaba que, para 2020, los visitantes extranjeros de Japón no tuvieran dificultades por el idioma).
2 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:Descripción de la fecha de lanzamiento: el comunicado del 5 de agosto de 2010 dice “hemos publicado” (traducción), mientras que el de 2015 dice “publicada en julio de 2010” (traducción). Es posible que la fecha de publicación en App Store y la del comunicado fueran distintas, pero este sitio no ha resuelto la diferencia.
4 de octubre de 2011Verificado en la fuente original
Apple presenta el iPhone 4S con “Siri”, que ayuda con tareas al hablarle (inicialmente )
El 4 de octubre de 2011, Apple presentó, junto con el iPhone 4S, Siri, “un asistente inteligente” (traducción) que ayuda con tareas solicitadas mediante la voz. Según el ejemplo del anuncio, al preguntarle “¿Necesitaré un paraguas este fin de semana?” (traducción) entiende que se busca el pronóstico del tiempo. Al principio estaba y solo admitía inglés (para Estados Unidos, Reino Unido y Australia), francés y alemán. El iPhone 4S se lanzó en Japón el 14 de octubre, pero Siri en japonés estuvo disponible desde el 8 de marzo de 2012. Su origen fue CALO, una investigación de SRI International dentro de PAL, un programa de DARPA, la agencia de investigación del Departamento de Defensa de Estados Unidos. Se convirtió en una empresa independiente en 2007 y Apple la adquirió en abril de 2010 (explicaciones de SRI y DARPA).
Lo que suele decirse:Suele pensarse que “Apple creó Siri desde cero” Según la fuente original:Según las explicaciones de SRI y DARPA, su origen fue CALO, una investigación del programa PAL de apoyo a decisiones militares (5 años, 150 millones de dólares y más de 300 personas). En 2007 se convirtió en la empresa independiente Siri Inc., que Apple adquirió en 2010. Incluso en su presentación estaba .
1 de marzo de 2012Verificado en la fuente originalJapón
NTT Docomo lanza el servicio de diálogo por voz “Shabette Concier” (marzo de 2012, una semana antes de Siri en japonés)
El 1 de marzo de 2012, NTT Docomo lanzó Shabette Concier como aplicación gratuita para sus teléfonos inteligentes Android. Esta “función de agente de voz” permitía buscar información y manejar el correo, las alarmas y otras funciones con solo hablar al teléfono. Interpretaba la “intención” de quien hablaba a partir de las combinaciones de palabras y elegía servicios o respuestas adecuados. Los procesos complejos, como el reconocimiento de voz, se realizaban en la red de Docomo, en la nube. Docomo lo describió como un servicio que aprovechaba la nube después del “teléfono con interpretación”, cuyas pruebas habían comenzado en noviembre de 2011. Siri en japonés se lanzó una semana después, el 8 de marzo.
14 de febrero de 2011Verificado en la fuente original
La IA de preguntas y respuestas “Watson” de IBM vence a 2 campeones históricos del concurso estadounidense Jeopardy!
En febrero de 2011, Watson, un sistema de preguntas y respuestas desarrollado por el equipo de investigación de IBM —un programa que lee enunciados en lenguaje natural y responde—, disputó 2 partidas contra 2 campeones históricos del concurso televisivo estadounidense Jeopardy! Los resultados finales fueron 77,147 dólares para Watson, 24,000 para Ken Jennings y 21,600 para Brad Rutter (página histórica de IBM). Sin conectarse a internet, Watson proponía respuestas con muchos métodos, reunía pruebas y solo pulsaba el botón para responder cuando la calculada mediante aprendizaje automático (un sistema que aprende de los datos) era suficiente. En la pregunta final de la primera partida, que pedía una ciudad de Estados Unidos, respondió (traducción) y se equivocó.
Lo que suele decirse:Suele interpretarse que “ganar a humanos en un concurso significa que Watson comprendía el lenguaje como una persona” Según la fuente original:El propio equipo escribió en su artículo de 2010 que (traducción). La página histórica de IBM también recoge estas palabras de su director: “El objetivo no es modelar el cerebro humano” (traducción). Durante el concurso cometió un error con una respuesta de baja confianza (Toronto).
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.
Detalles de los 3 recursos
La sigmoide en S tiene una pendiente casi de 0 cuando la entrada es grande. Nair y Hinton, de la Universidad de Toronto, dieron nombre a ReLU en 2010, y el equipo ganador del concurso de imágenes de 2012 también la usó. El método de Glorot y Bengio busca mantener casi igual la dispersión de la señal en todas las capas; en 2015, He y sus colegas publicaron una versión para ReLU. Dropout (julio de 2012) evita la dependencia entre neuronas y reduce el sobreajuste. En las pruebas se usan todas las neuronas y se reducen a la mitad los pesos de salida. El artículo detallado de 2014 indica que la idea se inspiró en una teoría del papel de la reproducción sexual en la evolución (Livnat y sus colegas, 2010).
El nombre Xavier
El artículo de 2010 llama a este método normalized initialization (inicialización normalizada). El artículo de He y sus colegas de 2015 dice que Xavier es el nombre usado en la herramienta Caffe (coincide con el nombre de pila del primer autor).
A menudo se considera dropout una innovación de AlexNet, pero el artículo de AlexNet lo toma de un artículo del mismo laboratorio de julio de 2012, al que cita como (traducción).
Fuentes originales y grado de certeza (3)Evitar que la señal desaparezca al apilar muchas capas
2010–2012Verificado en la fuente original
Cómo ReLU (0 si es negativo, el mismo valor si es positivo) se convirtió en estándar del aprendizaje profundo: recibió su nombre en 2010 y se difundió en 2011–2012. La misma forma aparece en el modelo de Kunihiko Fukushima de 1968
ReLU (rectified linear unit, unidad lineal rectificada) es una unidad o neurona que devuelve la entrada x sin modificar si es mayor que 0, y devuelve 0 si es menor o igual a 0; su fórmula es max(0, x). La sigmoide (función en forma de S) y tanh tienen una pendiente casi nula cuando la entrada es grande (se saturan), pero ReLU mantiene una pendiente de 1 para valores positivos, por lo que la señal que vuelve mediante retropropagación se debilita menos. En 2010, Nair y Hinton, de la Universidad de Toronto, mostraron que, si las unidades ocultas de 0 o 1 de una máquina de Boltzmann restringida se sustituyen por muchas unidades con los mismos pesos y desplazadas ligeramente, se puede aproximar su funcionamiento con unidades lineales rectificadas con ruido. También informaron de mejoras al reconocer fotos de objetos y rostros. En 2011, Glorot y sus colegas de la Universidad de Montreal escribieron que estas unidades también eran un mejor modelo de las células nerviosas reales y permitían representaciones dispersas, con muchos valores exactamente iguales a 0. Además, con suficientes datos etiquetados, las redes profundas podían aprender bien sin aprendizaje no supervisado previo. El artículo de AlexNet de 2012 las llamó ReLU siguiendo a Nair y Hinton, y afirmó que permitían entrenar varias veces más rápido que la misma red con tanh.
Lo que suele decirse:Se suele decir que “Hinton y sus colegas inventaron ReLU en 2010” o que “comenzó con AlexNet en 2012” Según la fuente original:El propio artículo de Nair y Hinton de 2010 indica que Jarrett y sus colegas ya habían probado max(0,x) en 2009 con el nombre positive part (parte positiva). Además, unidades de la misma forma (entrada positiva sin modificar, 0 si es negativa) se utilizaron en una red inspirada en la visión, tanto en una explicación japonesa de Kunihiko Fukushima, de NHK, de 1968 como en su artículo en inglés de 1969. Sin embargo, ninguno de los 3 artículos de 2010, 2011 y 2012 cita el trabajo de Fukushima. La novedad de 2010 fue derivar la unidad del modelo probabilístico de una máquina de Boltzmann restringida y darle nombre; la de 2011 fue mostrar que se podía prescindir del aprendizaje no supervisado previo.
Lo que aún no se sabe:No se ha comprobado si el artículo de 2010 fue el primero en utilizar el nombre Rectified linear (el artículo de 2010 dice que Jarrett y sus colegas lo llamaban positive part en 2009). No se ha abierto el texto del artículo de Fukushima en inglés de 1969 (IEEE), porque es de pago. Tampoco se ha abierto el artículo de Jarrett y sus colegas de 2009.
Cómo elegir los pesos iniciales: ajustar el intervalo al número de neuronas de cada capa (Glorot y Bengio, 2010), y el método para ReLU (He y sus colegas, 2015)
Los valores de los pesos antes de entrenar una red profunda (inicialización) influyen mucho en que pueda aprender. Si la señal crece o disminuye en una proporción fija al pasar por cada capa, al acumular muchas capas los gradientes de la retropropagación pueden desaparecer o divergir. En 2010, Glorot y Bengio, de la Universidad de Montreal, mostraron que el método habitual de elegir valores en el intervalo ±1/√n, con n igual al número de neuronas de la capa anterior, hacía que la variabilidad (varianza) de la señal que retrocede disminuyera entre capas. Propusieron la normalized initialization, que elige uniformemente en el intervalo ±√6/√(nj+nj+1), utilizando el número de neuronas de entrada y salida de la capa, nj y nj+1. El objetivo era mantener casi igual en todas las capas la variabilidad de los valores que avanzan y de las señales que retroceden. En 2015, Kaiming He y sus colegas de Microsoft Research señalaron que esa derivación suponía neuronas lineales (salida proporcional a la entrada), lo que no se ajusta a ReLU. Propusieron elegir los pesos para ReLU mediante una distribución normal de media 0 y desviación estándar √(2/n). Escribieron que incluso una red de 30 capas podía aprender, mientras que con el método de Glorot y Bengio el aprendizaje se detenía.
Lo que suele decirse:Se suele pensar que el nombre procede del artículo de Glorot y Bengio Según la fuente original:El propio artículo de 2010 lo llama normalized initialization. El artículo de He y sus colegas de 2015 dice que Xavier es el nombre utilizado en la herramienta Caffe (Jia y sus colegas, 2014); Xavier coincide con el nombre de pila del primer autor. También se suele decir que “con el preentrenamiento de 2006, las redes profundas pudieron aprender por primera vez”, pero el artículo de 2010 afirma que todos los éxitos desde 2006 se obtuvieron con nuevas inicializaciones o métodos de aprendizaje. Investigó por qué fallaba el descenso de gradiente estándar a partir de los pesos iniciales y de las funciones de activación (funciones que determinan la salida de las neuronas).
Lo que aún no se sabe:No se ha comprobado cuándo ni quién dio el nombre Xavier dentro de Caffe (no se han abierto el artículo de Caffe ni los registros del programa). Tampoco se ha comprobado quién inició ni cuándo el método ±1/√n, que el artículo de 2010 llama commonly used heuristic.
3 de julio de 2012Verificado en la fuente original
Dropout: desactivar al azar la mitad de las neuronas ocultas en cada paso de entrenamiento para evitar el sobreajuste (2012)
Dropout es un método que, cada vez que se presenta un dato durante el entrenamiento, excluye temporalmente al azar las neuronas de las capas ocultas con una probabilidad fija, habitualmente 0.5, poniendo su salida a 0. Evita que determinadas neuronas dependan unas de otras (co-adaptation) y reduce el sobreajuste: ajustarse demasiado a los datos de entrenamiento y equivocarse con datos nuevos. Al usar la red, se activan todas las neuronas y se reducen a la mitad sus pesos de salida (el artículo de 2014 multiplica los pesos por la probabilidad p de conservarlas). El resultado se aproxima al promedio de las predicciones de muchas redes más pequeñas que comparten pesos. El artículo de arXiv de julio de 2012, de Hinton, Srivastava, Krizhevsky, Sutskever y Salakhutdinov, de la Universidad de Toronto, lo probó con dígitos manuscritos de MNIST y otros datos, e informó de nuevos récords en reconocimiento de voz y objetos. El artículo de AlexNet del mismo año también lo utilizó en 2 capas totalmente conectadas y señaló que, sin él, el sobreajuste era grave.
Lo que suele decirse:Suele pensarse que “dropout fue una innovación de AlexNet en 2012” Según la fuente original:El propio artículo de AlexNet lo usa citando el artículo de arXiv de julio de 2012 del mismo laboratorio y lo presenta como una (traducción). El artículo detallado de 2014 explica que se inspiró en una teoría del papel de la reproducción sexual en la evolución (Livnat y colaboradores, 2010). También dice que la idea de añadir ruido a las neuronas ya se había usado en autocodificadores de eliminación de ruido, que reciben entradas con ruido y aprenden a reconstruirlas (Vincent y colaboradores, 2008 y 2010). El artículo sitúa su novedad en aplicarlo también a capas ocultas y en poder interpretarlo como un promedio de muchas redes.
Lo que aún no se sabe:No se describen la fecha en que se ideó dropout ni los relatos posteriores de Hinton sobre su inspiración, de los que existen varios, porque no se han buscado sus declaraciones originales.
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)
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_relu_init.py
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).
Lo que ocurre dentro
El artículo examina desde fuera a qué responde una neurona, reuniendo las imágenes que la activan más y creando imágenes que aumentan su respuesta. Los recursos para estudiar el funcionamiento interno ya comenzaron en esta época. Esta pregunta continúa hasta el capítulo 12.
Fuentes originales y grado de certeza (2)Señales de tráfico y el gato de Google
13 de febrero de 2012Verificado en la fuente original
IDSIA, en Suiza, reduce a la mitad del error humano la tasa de error en reconocimiento de señales de tráfico con redes neuronales convolucionales profundas entrenadas con GPU (8 meses antes de la competencia de 2012)
Dan Cireşan, Ueli Meier y Jürgen Schmidhuber, del instituto suizo IDSIA, entrenaron con GPU para videojuegos varias redes neuronales convolucionales profundas y promediaron sus salidas, un método de redes profundas de varias columnas. 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 humana era el doble. En los dígitos manuscritos de MNIST lograron un 0.23%, y escribieron que por primera vez se acercaban al aproximadamente 0.2% humano.
Lo que suele decirse:Suele contarse que “la IA superó por primera vez a humanos en reconocimiento de imágenes en 2015” y que “el primer éxito de redes convolucionales profundas con GPU fue el de la Universidad de Toronto en otoño de 2012” Según la fuente original:El informe de IDSIA de febrero de 2012 dice que sus redes convolucionales profundas entrenadas con GPU tuvieron la mitad de la tasa de error humana al identificar señales de tráfico. La tarea, sin embargo, era identificar señales, y el sistema del artículo tenía 43 salidas: el número de clases difería del de ImageNet, con 1,000.
26 de junio de 2012Verificado en la fuente originalLas fuentes discrepan
El experimento de los gatos de Google: una red que aprendió solo con imágenes de YouTube sin etiquetas desarrolló neuronas que respondían intensamente a caras de gatos
Quoc Le, Andrew Ng y colaboradores, de Google y la Universidad de Stanford, entrenaron una red neuronal de 9 capas y 1 mil millones de conexiones con imágenes sin etiquetas: una imagen de 200×200 píxeles tomada de cada uno de 10 millones de videos de YouTube. El entrenamiento duró 3 días en 1,000 computadoras (16,000 núcleos). Sin recibir instrucciones al respecto, surgieron neuronas que respondían a rostros humanos, y también a caras de gatos y cuerpos humanos. En su blog, Google explicó que “una de nuestras neuronas artificiales aprendió a responder intensamente a imágenes de... gatos” (traducción) y recalcó que (traducción).
Lo que suele decirse:Suele decirse que “la IA de Google aprendió sola a distinguir gatos” Según la fuente original:El centro del artículo eran las neuronas de (81.7%). La neurona de caras de gatos obtuvo un 74.8% en una prueba que distinguía caras de gatos de imágenes que no eran de gatos. La prueba estaba construida de modo que incluso respuestas al azar obtenían un 64.8% (tabla 1). El artículo sostiene que el sistema encontró por sí mismo conjuntos de características en imágenes sin etiquetas, y no simplemente que había visto muchos gatos. El blog de Google decía que “‘descubrió’ por sí mismo qué aspecto tenía un gato” (traducción) solo a partir de imágenes sin etiquetas (el propio blog puso comillas en la palabra “descubrió”).
Lo que aún no se sabe:El artículo investiga a qué responden las neuronas entrenadas mostrando imágenes que producen respuestas intensas y creando imágenes que las intensifican. Ya entonces se buscaban formas de examinar el funcionamiento interno.
2 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:Duración del entrenamiento: el artículo dice “3 días”; el blog de Google usa la comparación “tras mostrarle YouTube durante una semana” (traducción). Cifras de los gatos: la fila superior de la tabla 1 dice 74.6%, mientras que la inferior y el texto dicen 74.8%.
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é significa “Humanos: 5.1%”
La tasa de error del primer puesto bajó del 28.2% en 2010 al 2.3% en 2017. Los organizadores también midieron a personas. Una que practicó con 500 imágenes obtuvo el 5.1% en 1500; otra, que solo practicó con 100, obtuvo el 12.0% en 258. Los propios investigadores de Microsoft que escribieron en 2015 que habían superado a las personas también señalaron que (traducción).
Fuentes originales y grado de certeza (2)Gran ventaja del ganador; Tokio fue segundo
13 de octubre de 2012Verificado en la fuente originalLas fuentes discrepan
En la competencia de reconocimiento de imágenes ILSVRC 2012, la red convolucional profunda de la Universidad de Toronto (SuperVision) gana con gran ventaja; el equipo de la Universidad de Tokio queda segundo
En una competencia para identificar 1,000 clases de objetos en fotografías, el equipo “SuperVision” de Krizhevsky, Sutskever y Hinton redujo la tasa de error al 15.3% bajo la regla que permite dar hasta 5 respuestas (16.4% usando solo los datos proporcionados por la competencia). El segundo equipo, ISI de la Universidad de Tokio, tuvo un 26.2%: una diferencia de unos 11 puntos. Entrenaron una red neuronal de 8 capas y 60 millones de parámetros con 2 GPU para videojuegos, chips de procesamiento de imágenes de NVIDIA. En un artículo posterior, los organizadores escribieron sobre ese año: (traducción).
Lo que suele decirse:Suele decirse que “el aprendizaje profundo nació de repente en 2012” Según la fuente original:El sistema ganador amplió a gran escala las de LeCun y colaboradores de 1989, cuyo origen fue el neocognitrón de Fukushima de 1979, y las entrenó con GPU. El propio artículo dice (traducción), precedido por la observación de que todos los experimentos lo sugieren. También suele pensarse que “lo de 2012 fue una historia occidental”, pero el segundo equipo era de la Universidad de Tokio.
4 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:Duración del entrenamiento: la descripción del equipo en la página de la competencia dice “aproximadamente una semana”; el artículo, “5–6 días”. Hay 2 cifras para el primer puesto: 15.3% con datos adicionales y 16.4% usando solo los datos proporcionados. La tabla del artículo de los organizadores usa 16.4.
2010–2017Verificado en la fuente originalLas fuentes discrepan
En el concurso de reconocimiento de imágenes, la tasa de del primer puesto baja del 28% al 2% en 8 años. “Los humanos: 5.1%” es la medición de una sola persona
En un concurso para identificar 1,000 tipos de objetos en imágenes, con un máximo de 5 respuestas, el error del primer puesto disminuyó así: 2010, 28.2%; 2011, 25.8%; 2012, 15.3% (16.4% usando solo los datos proporcionados); 2013, 11.7% (11.2% incluyendo datos externos); 2014, 6.7%; 2015, 3.6%; 2016, 3.0%; y 2017, 2.3%. Los organizadores también midieron el error humano con 2 personas, A1 y A2. A1 practicó con 500 imágenes y obtuvo un 5.1% en 1,500; A2 practicó solo con 100 y obtuvo un 12.0% en 258.
Lo que suele decirse:Se suele decir que “en 2015, la IA superó a los humanos en reconocimiento de imágenes (error humano del 5.1%)” Según la fuente original:Ese 5.1% corresponde a una de las 2 personas experimentadas que probaron los organizadores (A1), al identificar 1,500 imágenes después de practicar con 500. La otra, que solo practicó con 100, obtuvo un 12.0%. Los propios investigadores que informaron de haber superado a los humanos (Microsoft, 2015) también escribieron que (traducción).
4 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:El criterio para determinar el “primer puesto” varía según el año. En 2012 y 2013 hubo resultados con y sin datos externos, y la tabla del artículo de los organizadores utiliza solo los datos proporcionados (16.4 y 11.7). Los sitios de 2010 y 2011 publicaban el error bajo el nombre “flat cost”, con el mismo sistema de hasta 5 respuestas.
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)
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_convolution.py
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.
Un método publicado
Se publicó el funcionamiento de Bonanza (y en 2009 también el código fuente del programa). Así surgieron programas de shogi basados en él, como Bonkras.
Las damas se resolvieron (2007)
Schaeffer y sus colegas, de la Universidad de Alberta, mantuvieron computadoras trabajando desde 1989 y demostraron: (traducción). Hay aproximadamente 5×10²⁰ posiciones del tablero. Una de las herramientas centrales fue el método de búsqueda df-pn de la tesis doctoral de Ayumu Nagai en la Universidad de Tokio (2002); Akihiro Kishimoto también figura entre los autores.
Según la fuente, la primera partida entre un profesional y un programa de shogi fue en 2005, 2007 o 2013. Las diferencias entre expresiones como en público, en un contexto oficial u oficialmente permiten llamar primera a cualquiera de ellas.
Fuentes originales y grado de certeza (6)Aprender de partidas y votar las jugadas
5 de mayo de 2006–2007Verificado en la fuente originalJapón
Bonanza, el programa de shogi que aprende de partidas profesionales, gana el campeonato mundial y al año siguiente juega en público contra Akira Watanabe, titular de Ryuo
El investigador en química Kunihito Hoki desarrolló Bonanza y lo publicó gratuitamente en junio de 2005. A diferencia de muchos programas anteriores de shogi, utilizó la “búsqueda de ancho completo”, que examina todas las jugadas legales. También incorporó “aprendizaje automático” (traducción) para aprender a evaluar las posiciones de modo que eligiera las mismas jugadas que en los registros de partidas profesionales. El autor afirma que aplicó una idea de sus investigaciones sobre el control de reacciones químicas al aprendizaje de la evaluación de posiciones. En mayo de 2006, en su primera participación en el 16.º Campeonato Mundial de Shogi por Computadora, ganó con 6 victorias y 1 derrota en la final de todos contra todos entre 8 equipos. El 21 de marzo de 2007 jugó una partida pública contra Akira Watanabe, titular de Ryuo, con 2 horas de tiempo de reflexión. Se dijo que Bonanza tenía ventaja en la fase intermedia, pero Watanabe ganó en 112 jugadas. Más tarde se publicó su método de construcción (y el código en 2009), dando lugar a programas basados en Bonanza, como Bonkras.
Lo que suele decirse:“Para crear un programa fuerte de shogi, su autor también debe ser un buen jugador” (según la entrevista, antes los desarrolladores solían ser aficionados de alto nivel porque construían manualmente la evaluación) Según la fuente original:El autor de Bonanza era un investigador en química que apenas conocía el shogi. Adoptó un método para que la máquina aprendiera la evaluación de partidas profesionales y ganó el campeonato mundial en su primera participación.
11 de octubre de 2010Verificado en la fuente originalLas fuentes discrepanJapón
El programa de shogi “Akara 2010” de la Sociedad de Procesamiento de la Información de Japón vence a Ichiyo Shimizu, campeona femenina Osho
En abril de 2010, la Sociedad de Procesamiento de la Información de Japón envió un desafío a la Asociación Japonesa de Shogi “con el deseo de que se celebren partidas públicas entre programas de shogi y los mejores jugadores profesionales” (traducción) (es decir, con ese deseo). Su presidente, Kunio Yonenaga, lo aceptó y eligió como primera rival a la campeona femenina Osho Ichiyo Shimizu, una de las principales jugadoras profesionales. La partida se celebró el 11 de octubre en el campus de Hongo de la Universidad de Tokio. Shimizu se rindió tras 86 jugadas y Akara 2010 ganó. Akara 2010 hacía que 4 de los principales programas japoneses de shogi (Gekisashi, GPS Shogi, Bonanza y YSS) analizaran la misma posición y jugaba el movimiento elegido más veces, mediante un sistema de . Usó 208 computadoras, con 658 núcleos en total.
Lo que suele decirse:Suele pensarse que “la fuerza del software de shogi depende de un solo programa” Según la fuente original:Akara 2010 reunía a 4 programas rivales mediante votación por mayoría y era fruto de la colaboración de desarrolladores japoneses de shogi por computadora. El desafío describía el programa de la sociedad como capaz de ofrecer “capacidad para competir de igual a igual con el Meijin” (traducción) (es decir, jugar al mismo nivel que el Meijin), pero la primera rival fue una jugadora profesional elegida por la asociación.
3 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:Número de computadoras usadas: el anuncio de agosto indicaba 169 computadoras y 676 núcleos; la nota añadida después de la partida indicaba 208 computadoras y 658 núcleos (aclara que se contaron los núcleos físicos y que algunos equipos no se usaron por averías).
14 de enero de 2012Verificado en la fuente originalLas fuentes discrepanJapón
Primer Den-O-sen de shogi: Kunio Yonenaga, Kisei vitalicio, pierde en 113 jugadas ante el programa “Bonkras”
El 14 de enero de 2012, en la sede del shogi de Tokio, el jugador retirado y presidente de la Asociación Japonesa de Shogi Kunio Yonenaga, Kisei vitalicio, jugó contra “Bonkras”, desarrollado por Hidenori Ito, de Fujitsu Laboratories. Bonkras ganó en 113 jugadas. Partía del programa público Bonanza, mejorado para realizar búsquedas paralelas en varias computadoras. Ese día, con 6 servidores, analizó unos 18 millones de jugadas por segundo. Su nombre combina Bonanza con , que designa un sistema de computadoras paralelas que calculan simultáneamente (explicación del anuncio de Fujitsu Laboratories).
Lo que suele decirse:Suele contarse que “en el primer Den-O-sen un profesional perdió contra un programa” Según la fuente original:Según el resumen de la propia asociación, la primera edición enfrentó al programa con un jugador retirado, entonces presidente de la asociación. Las partidas contra profesionales en activo comenzaron en la segunda edición, en 2013. Además, el programa ganador fue desarrollado por un investigador a partir del software público Bonanza: también es un ejemplo de acumulación de conocimientos publicados.
2 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:Las fuentes describen de manera diferente la “primera partida oficial entre un profesional y software”. La columna de la asociación de shogi (2017) dice “por primera vez de manera oficial” (traducción) sobre el segundo Den-O-sen, de 2013, mientras que una nota del anuncio de Fujitsu (2012) menciona la partida de 2007 entre Akira Watanabe, campeón Ryuo, y Bonanza. Parece una diferencia en lo que se considera “oficial” (estimación del sitio).
19 de julio de 2007Verificado en la fuente original
Sobre las damas: . Una computadora demuestra que, si ninguno de los dos bandos se equivoca, siempre hay empate
Schaeffer y sus colegas de la Universidad de Alberta mantuvieron decenas de computadoras trabajando casi sin interrupción desde 1989 y demostraron que en las damas (traducción). Hay unas 5×10²⁰ posiciones (500 trillones), y era el juego conocido más difícil resuelto hasta entonces. Una de las herramientas centrales de la demostración fue df-pn, el método de búsqueda de la tesis doctoral de Ayumu Nagai, de la Universidad de Tokio, de 2002. También figura como coautor Akihiro Kishimoto, que cuando se publicó el artículo ya se había trasladado a una universidad de Hakodate, Hokkaido.
Lo que suele decirse:Se suele pensar que “la historia de la IA para juegos es una historia de Europa y Estados Unidos” Según la fuente original:En la demostración de las damas de 2007 se utilizó como herramienta central df-pn, el método de búsqueda del japonés Ayumu Nagai (Universidad de Tokio), y el japonés Akihiro Kishimoto también figuraba entre los autores.
3 fuentes originales y cómo se verificaron
Checkers Is Solved (Science 317, 1518–1522) (Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, Steve Sutphen · 2007 · p.1518 abstract · Fuente original)
18 de septiembre de 2005–2013Verificado en la fuente originalLas fuentes discrepanJapón
¿Cuándo fue la primera partida entre un jugador profesional y un programa de shogi? Las fuentes señalan 2005, 2007 o 2013
Las fuentes dan 3 años para el encuentro descrito como “el primero” (traducción) entre un jugador profesional y un programa de shogi. ① Sobre la partida de septiembre de 2005 entre TACOS y Takayoshi Hashimoto, 5-dan, un periódico de entonces citó al autor, el profesor Hiroyuki Iida: “esta es la primera vez que un profesional juega contra una computadora sin hándicap en un evento público” (traducción). ② Sobre la partida de marzo de 2007 entre Bonanza y Akira Watanabe, titular de Ryuo, una explicación de un investigador afirmó: “es la primera vez que un profesional y una computadora se enfrentan en un evento oficial” (traducción); una entrevista de 2020 escribió: “por primera vez en público como jugador profesional” (traducción). ③ Una columna de la Asociación Japonesa de Shogi (2017) describió el segundo Den-O-sen de 2013 así: “por primera vez un jugador profesional se enfrentó oficialmente a un programa de shogi” (traducción). Las diferencias entre las expresiones “un evento público” (traducción), “un evento oficial” (traducción) y “oficialmente” (traducción) permiten describir todas como “por primera vez” (traducción).
Lo que suele decirse:Se suele fijar un único año: “La primera partida entre un jugador profesional y un programa de shogi fue en el año X” Según la fuente original:Las fuentes describen 2005, 2007 y 2013 como “por primera vez” (traducción). Las diferencias entre “un evento público” (traducción) (TACOS, 2005), “un evento oficial” (traducción) (Bonanza, 2007) y “oficialmente” (traducción) (Den-O-sen, 2013; en el primero, en 2012, participó un jugador retirado) permiten que todas las descripciones sean correctas.
4 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:Año descrito como “por primera vez” (traducción): 2005 (Sankei Shimbun, declaración del profesor Hiroyuki Iida; partida pública sin hándicap) / 2007 (explicación de Hitoshi Matsubara: evento oficial; entrevista: evento público) / 2013 (columna de la Asociación Japonesa de Shogi: oficialmente). La sección de discrepancias del registro del primer Den-O-sen de 2012 también recoge la diferencia entre 2007 y 2013.
14 de octubre de 2005Verificado en la fuente originalJapón
La Asociación Japonesa de Shogi dispone que los profesionales deben “consultar y confirmar previamente con el organizador y la federación” (traducción) al jugar en público contra un programa
El 18 de septiembre de 2005, en Komatsu, prefectura de Ishikawa, el programa de shogi , desarrollado por el profesor Hiroyuki Iida y sus colegas del Instituto Avanzado de Ciencia y Tecnología de Japón, jugó una partida pública sin hándicap contra Takayoshi Hashimoto, 5-dan. Ganó el profesional, aunque el programa tuvo ventaja hasta la fase final (Sankei Shimbun). Aproximadamente 1 mes después, el 14 de octubre, la Asociación Japonesa de Shogi anunció que los jugadores profesionales y las jugadoras profesionales debían consultar y confirmar previamente con el organizador y la asociación antes de jugar en público contra un programa, “para crear un entorno en el que los programas de shogi y las personas puedan disputar partidas en un marco adecuado” (traducción). En el mismo anuncio afirmó: “se desea seguir colaborando en el desarrollo de los programas de shogi como hasta ahora” (traducción).
Lo que suele decirse:Se suele decir que “la Asociación de Shogi prohibió a los profesionales jugar contra computadoras” (una explicación de un investigador de 2007 también dice “sin permiso… prohibido” (traducción)) Según la fuente original:El anuncio de la propia asociación dice: “al jugar en público contra un programa de shogi, consultar y confirmar previamente con el organizador y la federación” (traducción), y también “se desea seguir colaborando en el desarrollo de los programas de shogi como hasta ahora” (traducción). De hecho, 1 año y medio después, en marzo de 2007, se celebró una partida pública entre Akira Watanabe, titular de Ryuo, y Bonanza (registro → Bonanza, el programa de shogi que apren…).
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
Este código Python reproduce el mismo mecanismo que “Explorar”. Al pulsar ▶ Ejecutar, el resultado aparece debajo. Se pueden cambiar los números y volver a ejecutarlo.
u09_bonanza_learn.py
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%).
De qué se componía la previsión
Estas cifras también se usaron para justificar financiación estatal de la investigación. La previsión calculaba importes a partir de la proporción del trabajo humano actual que podrían asumir los robots (5–50%). El propio responsable del informe escribió después que era (traducción) y que (traducción) (citado en el análisis de Arai).
En 2006–2008, organismos del Estado y la propia asociación industrial redujeron la previsión para 2010 a 50–75 mil millones de yenes.
Fuentes originales y grado de certeza (2)Metas con fecha y previsiones del mercado
7 de noviembre de 2011Verificado en la fuente originalLas fuentes discrepanJapón
Comienza (ロボットは東大に入れるか), del Instituto Nacional de Informática: Torobo-kun busca puntuaciones altas en el Center Test para 2016 y aprobar el examen de ingreso de Tokio en 2021
En 2011, el Instituto Nacional de Informática inició el para desarrollar un programa informático que resolviera preguntas de los exámenes de ingreso universitario. Buscaba volver a integrar la investigación en inteligencia artificial, fragmentada desde 1980, y dar a los jóvenes una aspiración. Fijó como metas concretas (traducción) y (traducción).
Lo que ocurrió después:Según el anuncio de NII del 14 de noviembre de 2016, obtuvo 525 puntos (promedio nacional: 454.8) y una puntuación estandarizada de 57.1 en un simulacro del Center Test (5 áreas, 8 asignaturas). Esto correspondía a una probabilidad de admisión de al menos el 80% en 1,343 facultades de 512 universidades privadas y 30 facultades de 23 universidades nacionales o públicas locales. En el simulacro de ingreso de la Universidad de Tokio alcanzó una puntuación estandarizada de 76.2 en matemáticas para ciencias: resolvió completamente 4 de 6 preguntas sin ayuda humana. Para el tratamiento de su trabajo sobre el Center Test en la presentación de ese día, véase el evento de Torobo-kun de 2016 (registro → Torobo-kun: ¿qué ocurrió en 2016 con el…). Este sitio no ha encontrado ningún anuncio de que aprobara el examen de ingreso de Tokio en 2021.
2 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:Hay diferencias en la formulación de la meta. El anuncio de NII de 2011 dice (traducción), mientras que el artículo de 2012 dice “obtener para 2021 una puntuación suficiente para aprobar en las preguntas de la segunda fase del examen de ingreso de la Universidad de Tokio” (traducción).
mayo de 2001–2015Verificado en la fuente originalLas fuentes discrepanJapón
Predicción: el mercado japonés de robots alcanzaría unos 3 billones de yenes en 2010 (previsión de asociaciones industriales de 2001). El mercado de robots domésticos y hospitalarios no llegó a 10 mil millones
En 2001, un informe de la Federación Japonesa de la Industria de Maquinaria y la Asociación Japonesa de Robótica pronosticó el mercado robótico en 5 sectores. Para 2010 estimó 1.5 billones de yenes en la vida cotidiana, 850 mil millones en manufactura, 290 mil millones en el sector público, 260 mil millones en salud y bienestar, y 90 mil millones en biotecnología (unos 3 billones en total); para 2025, unos 8 billones en total. Según el análisis de Hirohiko Arai, del Instituto Nacional de Ciencia y Tecnología Industrial Avanzada, de 2009, el Ministerio de Economía, Comercio e Industria y otras entidades usaron esta previsión para justificar presupuestos de investigación y desarrollo, y la prensa la difundió. El anuncio de la Expo de Aichi de 2005 también afirmó: “se prevé que el mercado alcance 1.8 billones de yenes en 2010” (traducción).
Lo que suele decirse: (traducción; Arai cita esta afirmación como una creencia muy extendida entre los investigadores de robótica; los sectores no manufactureros incluyen el hogar, los cuidados y los servicios públicos) Según la fuente original:Los estudios del propio sector industrial mostraban que el mercado de robots de próxima generación fuera de la manufactura se situaba en 1.4–6.8 mil millones de yenes anuales durante el periodo estudiado, sin alcanzar los 10 mil millones, y estaba disminuyendo (−10.2% anual en promedio, según Arai). La estrategia del Gobierno de 2015 también describió el mercado robótico total como (traducción).
Lo que ocurrió después:Según el análisis de Hirohiko Arai de 2009, los estudios de la asociación industrial y otras entidades situaban el mercado de robots de próxima generación fuera de la manufactura en 1.4–6.8 mil millones de yenes anuales (menos de 10 mil millones), muy lejos de la previsión para 2010 (unos 2 billones fuera de la manufactura). Entre 2006 y 2008, organismos estatales y la propia asociación rebajaron la previsión de 2010 a 50–75 mil millones. En 2015, la del Gobierno describió el mercado robótico como (traducción) y fijó un nuevo objetivo de 2.4 billones para 2020 (libro blanco de 2015 del Ministerio de Asuntos Internos y Comunicaciones). Este sitio no ha comprobado la previsión de 2025.
4 fuentes originales y cómo se verificaron
Discrepancias entre las fuentes:El informe del año anterior (2000) de la misma asociación industrial había previsto un mercado no manufacturero de 623.5 mil millones de yenes para 2010 (según el análisis de Arai; no se ha abierto el informe original). La previsión se multiplicó por 3.3 en 1 año.
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.