¿Quién inventó el árbol de decisión?

Question

Estoy tratando de rastrear quién inventó la estructura de datos y algoritmo del árbol de decisión.

En la entrada de Wikipedia sobre aprendizaje de árboles de decisión hay una afirmación de que "ID3 y CART fueron inventados de forma independiente casi al mismo tiempo (entre 1970 y 1980)". ID3 fue presentado más tarde en:

• Quinlan, J. R. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (Mar. 1986), 81-106

así que no estoy seguro de que la afirmación sea cierta.

Encontré a través de Google Books una referencia a un libro de 1959 Statistical decision series y una colección de 1958 de Working papers. El contexto no está claro y no parecen presentar un algoritmo. Sin embargo, no definen la estructura de datos y la tratan como si fuera bien conocida.

Usando Google Scholar encontré citas que se remontaban a 1853 pero eran errores de análisis y no citas reales de esa fecha.

Answer 1

Buena pregunta. @G5W va por buen camino al referirse al artículo de Wei-Yin Loh. El artículo de Loh analiza el estadística antecedentes de los árboles de decisión y, correctamente, se remonta al artículo de Fisher (1936) sobre el análisis discriminante -esencialmente la regresión que clasifica múltiples grupos como la variable dependiente- y desde allí, a través de los modelos AID, THAID, CHAID y CART.

La respuesta corta es que el primer artículo que he podido encontrar que desarrolla un enfoque de "árbol de decisiones" data de 1959 y de un investigador británico, William Belson, en un artículo titulado Comparación y predicción según el principio de clasificación biológica , ( JRSS (Serie C, Estadística Aplicada, Vol. 8, No. 2, junio, 1959, pp. 65-75), cuyo resumen describe su enfoque como uno de que se ajusta a muestras de población y el desarrollo de criterios para hacerlo:

En este artículo, el Dr. Belson describe una técnica para cotejar muestras de población. Ésta depende de la combinación de métodos empíricos empíricamente para obtener la mejor predicción disponible, o compuesto disponible. El principio subyacente es bastante distinto de el inherente al método de correlación múltiple.

La respuesta "larga" es que otras corrientes de pensamiento, incluso anteriores, parecen relevantes aquí. Por ejemplo, los simples desgloses de cohortes por edad y sexo que se emplean en las tablas actuariales de mortalidad ofrecen un marco para pensar en las decisiones que se remonta a varios siglos atrás. También se podría argumentar que los esfuerzos que se remontan a los babilonios empleaban ecuaciones cuadráticas, que eran no lineales en las variables (no en los parámetros, http://www-history.mcs.st-and.ac.uk/HistTopics/Quadratic_etc_equations.html ) tienen relevancia, al menos en la medida en que presagian modelos paramétricos de crecimiento logístico (reconozco que esto es una estiramiento comentario, siga leyendo para una motivación más completa del mismo). Además, los filósofos han reconocido y teorizado durante mucho tiempo sobre la existencia de información cualitativa ordenada jerárquicamente, por ejemplo, el libro de Aristóteles sobre Categorías . El concepto y la asunción de un jerarquía es la clave aquí. Otros descubrimientos relevantes, mucho más tardíos, fueron la superación de los límites del espacio euclidiano tridimensional en el desarrollo del infinito de David Hilbert, Hilbert espacio, la combinatoria, los descubrimientos de la física relacionados con el espacio de Minkowski en 4 dimensiones, la distancia y el tiempo, la mecánica estadística que subyace a la teoría de la relatividad especial de Einstein, así como las innovaciones en la teoría de la probabilidad relacionadas con los modelos de las cadenas de Markov, las transiciones y los procesos. La cuestión es que puede haber un desfase importante entre cualquier teoría y su aplicación; en este caso, el desfase entre las teorías sobre la información cualitativa y los desarrollos relacionados con su evaluación empírica, predicción, clasificación y modelización.

Una de las mejores conjeturas es que estos desarrollos pueden asociarse con la historia de la creciente sofisticación de los estadísticos, sobre todo en el siglo XX, en el desarrollo de modelos que aprovechan los tipos de escala distintos de los continuos (por ejemplo, nominal o, más sencillamente, información categórica), modelos de datos de recuento (poisson), tablas de contingencia cruzadas, estadísticas no paramétricas sin distribución, escalamiento multidimensional (por ejemplo, J.G. Carroll, entre otros), modelos con variables dependientes cualitativas como la regresión logística de dos grupos, así como el análisis de correspondencia (sobre todo en Holanda y Francia en los años 70 y 80).

Existe una amplia literatura que discute y compara la regresión logística de dos grupos con el análisis discriminante de dos grupos y, para características totalmente nominales, encuentra que proporcionan soluciones equivalentes (por ejemplo, Dillon y Goldstein Análisis multivariante , 1984).

El artículo de J.S. Cramer sobre la historia de la regresión logística ( La historia de la regresión logística , http://papers.tinbergen.nl/02119.pdf ) la describe como originada con el desarrollo de la función univariante, logística o la clásica En forma de S curva:

La supervivencia del término logística y la amplia aplicación del dispositivo han sido determinados de manera decisiva por las historias personales y acciones individuales de unos pocos estudiosos...

Los modelos deterministas de la curva logística se originaron en 1825, cuando Benjamin Gompertz ( https://en.wikipedia.org/wiki/Benjamin_Gompertz ) publicó un artículo en el que desarrollaba el primer modelo logístico verdaderamente no lineal (no lineal en los parámetros y no sólo en las variables, como en el caso de los babilonios): el modelo y la curva de Gompertz.

Me gustaría sugerir que otro eslabón importante en esta cadena que lleva a la invención de los árboles de decisión fue el trabajo del sociólogo de Columbia Paul Lazarsfeld sobre los modelos de estructura latente. Su trabajo comenzó en los años 30 y continuó durante la Segunda Guerra Mundial con su análisis de contenido de los periódicos alemanes para la naciente OSS (más tarde la CIA, como se comenta en el libro de John Naisbett Megatendencias ) y finalmente se publicó en 1950. Andersen lo describe así ( Análisis de la estructura latente: Un estudio Erling B. Andersen, Revista Escandinava de Estadística Vol. 9, nº 1, 1982, pp. 1-12):

Llaa ffooorrmmaacciióónn ddee llaa ccllaassssiiccaa ddee llaa eennttrruuccttuurraa ddee aannaalliizzaacciióónn een eevveellooppeedd ddee llaa PPaauull LLaazzaarrssffeellddaa eenn 11995500 eenn uunn ssttuuddiioo ddee llaa eetthnoocceennttrriissmmoo ddee ssoolliiddaadd ddee AAmmeerriiccaa ddee llaa WWWIIII.. La información de la empresa se ha convertido en algo muy importante. eenn llaa ddee sseerrvviicciióónn ddee llaa ccoonncceeppttuuaa ddee llaa ccoonnttrraacciióónn ddee llaa ccoonnttrruuccttuurraa mmooddeellss......TTe llaass eennccuueerrttaass ddee sseerrvviicciioonneess ddee llaa ccoommuunniiccaacciióónn ddee llaa ccoommuunniiccaacciióónn ddee llaass eessppeerriioonneess,, ccoonnttrraanncciiaa,, ccoonnttrraanncciiaa ......AAnn ccoonnttrraann ccoonnttrraanncciiaa pprriimmiittiivvaa pprreesseennttaa pprreesseennttaa pprriimmiittiivvaa pprreesseennttaa pprreesseennttaa pprreesseennttaa pprreesseennttaa pprreesseennttaa las reuniones y los resultados de los trabajos se han llevado a cabo en el marco del programa de la UE ccoolllleeaagguuee aa CCoolluummbbiiaa UUnniivveerrssiiddaadd,, TT..WW... AAnnddeerrssoonn,,, qquuee ppaappeerr aa ppaappeerr (( Psychometrika , marzo de 1954, volumen 19, número 1, pp. 1-10, En estimación de los parámetros en el análisis de la estructura latente ), desarrollaron un método eficiente de estimación de los parámetros del modelo de clase latente Para introducir el marco (de los modelos de clase latente) para introducir el marco (de los modelos de clases latentes), esbozaremos brevemente los conceptos básicos... y utilizaremos un sistema de notación desarrollado mucho más tarde por Goodman (1974a). sistema notacional desarrollado mucho más tarde por Goodman (1974a)...Los datos se dan en la forma de un tabla de contingencia múltiple ...

Hay una distinción útil que vale la pena hacer aquí, ya que puede relacionarse con la progresión de AID a CHAID (más tarde CART), entre los modelos basados en tablas de contingencia (todas las variables del modelo están nominalmente escaladas) y los modelos de clase latente más recientes (más precisamente, modelos de mezcla finita basados en "mezclas" de escalas y distribuciones, por ejemplo, Kamakura y Russell, 1989, Un modelo probabilístico de elección para la segmentación del mercado y la estructura de la elasticidad ) en la forma de crear los residuos del modelo. En los modelos de tabla de contingencia más antiguos, los recuentos de celdas inherentes a la tabla de clasificación cruzada completa constituían la base de las "réplicas" y, por tanto, de la heterogeneidad de los residuos del modelo utilizados en la partición en clases. Por otro lado, los modelos de mezcla más recientes se basan en medidas repetidas en un solo sujeto como base para la partición de la heterogeneidad en los residuos. Esta respuesta es no lo que sugiere una conexión directa entre los modelos de clases latentes y los árboles de decisión. La relevancia de AID y CHAID puede resumirse en los estadísticos empleados para evaluar los modelos, AID utiliza una distribución F continua mientras que CHAID utiliza la distribución chi-cuadrado, apropiada para información categórica. Más bien en su análisis y modelización de las tablas de contingencia, los LCM constituyen, en mi opinión, una pieza importante en el rompecabezas o narrativa que conduce al desarrollo de los árboles de decisión, junto con las muchas otras innovaciones ya señaladas.

El CHAID fue un desarrollo posterior, propuesto por primera vez en una tesis doctoral de 1980 por el sudafricano Gordon Kass, como se indica en este artículo de Wiki sobre el CHAID ( https://en.wikipedia.org/wiki/CHAID ). Por supuesto, el CART llegó unos años más tarde, en la década de los 80, con el ahora famoso libro de Breiman, et al. Árboles de clasificación y regresión .

Tanto AID como CHAID y CART proponen estructuras arbóreas y jerarquizadas como representación óptima de la realidad. Sólo que lo hacen con algoritmos y métodos diferentes. Para mí, los siguientes pasos en esta cadena progresiva de innovación son la aparición de teorías heterárquicas de la estructura. Como se define en este artículo de la Wiki, las heterarquías "son un sistema de organización en el que los elementos de la organización no están clasificados (no jerárquicos) o en el que poseen el potencial de ser clasificados de varias maneras diferentes" ( https://en.wikipedia.org/wiki/Heterarchy o para una perspectiva más profunda y filosófica de la heterarquía, véase Kontopoulos, La lógica de la estructura social ). Desde un punto de vista empírico, el análisis y la modelización de las estructuras de red son los más representativos de este desarrollo histórico en la comprensión de la estructura (por ejemplo, el libro de Freeman El desarrollo del análisis de redes sociales ). Aunque muchos analistas de redes intentan forzar una disposición jerárquica en la red resultante, esto es más una expresión de suposiciones arraigadas e inconscientes que una afirmación sobre la realidad empírica de la estructura de la red múltiple en un mundo complejo.

Esta respuesta sugiere que el arco de la evolución que llevó al desarrollo de los árboles de decisión creó nuevas preguntas o insatisfacción con los métodos "de vanguardia" existentes en cada paso o fase del proceso, lo que requiere nuevas soluciones y nuevos modelos. En este caso, las insatisfacciones pueden verse en las limitaciones de la modelización de dos grupos (regresión logística) y el reconocimiento de la necesidad de ampliar ese marco a más de dos grupos. Insatisfacciones con los supuestos no representativos de una distribución normal subyacente (análisis discriminante o AID), así como la comparación con la relativa "libertad" que se encuentra al emplear supuestos y modelos no paramétricos y sin distribución (por ejemplo, CHAID y CART).

Como se ha sugerido, el origen de los árboles de decisión tiene casi con toda seguridad una larga historia que se remonta a siglos atrás y está geográficamente dispersa. Se pueden rastrear múltiples corrientes de la historia humana, la ciencia, la filosofía y el pensamiento para esbozar la narrativa que conduce al desarrollo de los muchos tipos de árboles de decisión que existen hoy en día. Seré el primero en reconocer las importantes limitaciones de mi breve esbozo de esta historia.

/** Apéndices **/

1. Este artículo de 2014 en el Nueva Ciencia se titula ¿Por qué nos gusta organizar el conocimiento en árboles? ( https://www.newscientist.com/article/mg22229630-800-why-do-we-love-to-organise-knowledge-into-trees/ ), es una reseña del libro del gurú de la visualización de datos Manuel Lima El libro de los árboles que rastrea el uso milenario de los árboles como medio de visualización y ayuda mnemotécnica del conocimiento. No parece haber duda de que los modelos y gráficos seculares y empíricos inherentes a métodos como AID, CHAID y CART representan la evolución continua de esta tradición de clasificación originalmente religiosa.

2. En este vídeo (publicado en Internet por Salford Systems, empresa que implementa el software CART), Homenaje a Leo Breiman Breiman habla sobre el desarrollo de su pensamiento que condujo a la metodología CART. Todo empezó con una pared revestida con las siluetas de distintos acorazados de la Segunda Guerra Mundial.

https://www.salford-systems.com/videos/conferences/cart-founding-fathers/a-tribute-to-leo-breiman?utm_source=linkedin&utm_medium=social&utm_content=3599323

3. Al leer la introducción de la obra de Denis Konig de 1936 Teoría de grafos finitos e infinitos Tutte, ampliamente considerado como el primer fundamento matemático riguroso de un campo que anteriormente se consideraba una fuente de diversión y rompecabezas para niños, señala (p. 13) que el capítulo 4 (que comienza en la p. 62) del libro de Konig está dedicado a los árboles en la teoría de grafos. La explicación de Tutte de la definición de Konig de un árbol es "donde un gráfico 'acíclico' es un gráfico sin circuito, un árbol es un gráfico acíclico conectado finito... en otras palabras, en un árbol hay uno y sólo un camino desde un vértice dado a otro..." Para mí (y no soy ni teórico de los grafos ni matemático), esto sugiere que la teoría de los grafos y sus precursores en la teoría de Poincare Análisis Situs o la de Veblen Coloquio de Cambridge conferencias sobre topología combinatoria, puede haber proporcionado los primeros antecedentes intelectuales y matemáticos de lo que más tarde se convirtió en un tema para los estadísticos.

4. La primera Árbol del conocimiento se atribuye ampliamente al filósofo neoplatónico Porfirio, quien, hacia el año 270 de la era cristiana, escribió un Introducción a la lógica que utilizaba un árbol metafórico para describir y organizar el conocimiento ... http://www.historyofinformation.com/expanded.php?id=3857

5. Acabo de descubrir una referencia incluso anterior a un Árbol del conocimiento en el Libro del Génesis en la Biblia, discutido en este artículo de la Wiki ... https://en.wikipedia.org/wiki/Tree_of_life_(bíblico) . El Génesis se remonta probablemente al año 1.400 a.C. basándose en esta referencia ... https://www.biblica.com/bible/bible-faqs/when-was-the-bible-written/ En cualquier caso, el Libro del Génesis es muy anterior a Porfirio.

Answer 2

La gran referencia sobre CART es:

Classification and Regression Trees
Leo Breiman, Jerome Friedman, Charles J. Stone, R.A. Olshen (1984)

pero ciertamente no fue el trabajo más temprano sobre el tema.

En su documento de 1986 Induction of Decision Trees, Quinlan identifica al propio Sistema de Aprendizaje de Conceptos de Hunt (CLS) como un precursor de ID3. Él ubica a CLS en 1963, pero hace referencia a

E.B. Hunt, J.Marin, P.J. Stone,
Experiments in Induction
Academic Press, Nueva York, 1966

Wei-Yin Loh de la Universidad de Wisconsin ha escrito sobre la historia de los árboles de decisión. Hay un Documento

Cincuenta años de árboles de clasificación y regresión Wei-Yin Loh Revisión Estadística Internacional (2014), 82, 3, 329–348 doi:10.1111/insr.12016

También hay una Presentación de una charla que él dio sobre el tema.