On cascading small decision trees

Abstract

Aquesta tesi tracta sobre la utilització d'arbres de decisió petits per a la classificació i la mineria de dades. La idea intuïtiva darrera d'aquesta tesi és que una seqüència d'arbres de decisió petits pot rendir millor que un arbre de decisió gran, reduint tan el cost d'entrenament com el d'explotació.<br/>El nostre primer objectiu va ser desenvolupar un sistema capaç de reconèixer diferents tipus d'elements presents en un document com ara el fons, text, línies horitzontals i verticals, dibuixos esquemàtics i imatges. Aleshores, cada element pot ser tractat d'acord a les seves característiques. Per exemple, el fons s'elimina i no és processat, mentre que les altres regions serien comprimides usant l'algorisme apropiat, JPEG amb pèrdua per a les imatges i un mètode sense pèrdua per a la resta, per exemple. Els primers experiments usant arbres de decisió varen mostrar que els arbres de decisió construïts eren massa grans i que patien de sobre-entrenament. Aleshores, vàrem tractar d'aprofitar la redundància espacial present en les imatges, utilitzant una aproximació de resolució múltiple: si un bloc gran no pot ser correctament classificat, trencar-lo en quatre sub-blocs i repetir el procés recursivament per a cada sub-bloc, usant tot el coneixement que s'hagi calculat amb anterioritat. Els blocs que no poden ser processats per una mida de bloc donada s'etiqueten com a "mixed", pel que la paraula progressiu pren sentit: una primera versió de poca resolució de la imatge classificada és obtinguda amb el primer classificador, i és refinada pel segon, el tercer, etc., fins que una versió final és obtinguda amb l'últim classificador del muntatge. De fet, l'ús de l'esquema progressiu porta a l'ús d'arbres de decisió més petits, ja que ja no cal un classificador complex. En lloc de construir un classificador gran i complex per a classificar tot el conjunt d'entrenament, només provem de resoldre la part més fàcil del problema de classificació, retardant la resta per a un segon classificador, etc.<br/>La idea bàsica d'aquesta tesi és, doncs, un compromís entre el cost i la precisió sota una restricció de confiança. Una primera classificació es efectuada a baix cost; si un element és classificat amb una confiança elevada, s'accepta, i si no ho és, es rebutja i s'efectua una segona classificació, etc. És bàsicament, una variació del paradigma de "cascading", on un primer classificador s'usa per a calcular informació addicional per a cada element d'entrada, que serà usada per a millorar la precisió de classificació d'un segon classificador, etc. El que presentem en aquesta tesi és, bàsicament, una extensió del paradigma de "cascading" i una avaluació empírica exhaustiva dels paràmetres involucrats en la creació d'arbres de decisió progressius. Alguns aspectes teòrics relacionats als arbres de decisió progressius com la complexitat del sistema, per exemple, també són tractats.

This thesis is about using small decision trees for classification and data mining. The intuitive idea behind this thesis is that a sequence of small decision trees may perform better than a large decision tree, reducing both training and exploitation costs.<br/>Our first goal was to develop a system capable to recognize several kinds of elements present in a document such as background, text, horizontal and vertical lines, line drawings and images. Then, each element would be treated accordingly to its characteristics. For example, background regions would be removed and not processed at all, while the other regions would be compressed using an appropriate algorithm, the lossy JPEG standard operation mode for images and a lossless method for the rest, for instance. Our first experiments using decision trees showed that the decision trees we built were too large and they suffered from overfitting. Then, we tried to take advantage of spatial redundancy present in images, using a multi-resolution approach: if a large block cannot be correctly classified, split it in four subblocks and repeat the process recursively for each subblock, using all previous computed knowledge about such block. Blocks that could not be processed at a given block size were labeled as mixed, so the word progressive came up: a first low resolution version of the classified image is obtained with the first classifier, and it is refined by the second one, the third one, etc, until a final version is obtained with the last classifier in the ensemble. Furthermore, the use of the progressive scheme yield to the use of smaller decision trees, as we no longer need a complex classifier. Instead of building a large and complex classifier for classifying the whole input training set, we only try to solve the easiest part of the classification problem, delaying the rest for a second classifier, and so.<br/>The basic idea in this thesis is, therefore, a trade-off between cost and accuracy under a confidence constraint. A first classification is performed at a low cost; if an element is classified with a high confidence, it is accepted, and if not, it is rejected and a second classification is performed, and so. It is, basically, a variation of the cascading paradigm, where a first classifier is used to compute additional information from each input sample, information that will be used to improve classification accuracy by a second classifier, and so on. What we present in this thesis, basically, is an extension of the cascading paradigm and an exhaustive empirical evaluation of the parameters involved in the creation of progressive decision trees. Some basic theoretical issues related to progressive decision trees such as system complexity, for example, are also addressed.

Esta tesis trata sobre la utilización de árboles de decisión pequeños para la clasificación y la minería de datos. La idea intuitiva detrás de esta tesis es que una secuencia de árboles de decisión pequeños puede rendir mejor que un árbol de decisión grande, reduciendo tanto el coste de entrenamiento como el de explotación. <br/>Nuestro primer objetivo fue desarrollar un sistema capaz de reconocer diferentes tipos de elementos presentes en un documento, como el fondo, texto, líneas horizontales y verticales, dibujos esquemáticos y imágenes. Entonces, cada elemento puede ser tratado de acuerdo a sus características. Por ejemplo, el fondo se elimina y no se procesa, mientras que las otras regiones serían comprimidas usando el algoritmo apropiado, JPEG con pérdida para las imágenes y un método sin pérdida para el resto, por ejemplo. Los primeros experimentos usando árboles de decisión mostraron que los árboles de decisión construidos eran demasiado grandes y que sufrían de sobre-entrenamiento. Entonces, se trató de aprovechar la redundancia espacial presente en las imágenes, utilizando una aproximación de resolución múltiple: si un bloque grande no puede ser correctamente clasificado, romperlo en cuatro sub-bloques y repetir el proceso recursivamente para cada sub-bloque, usando todo el conocimiento que se haya calculado con anterioridad. Los bloques que no pueden ser procesados para una medida de bloque dada se etiquetan como "mixed", por lo que la palabra progresivo toma sentido: una primera versión de poca resolución de la imagen clasificada se obtiene con el primer clasificador, y se refina por el segundo, el tercero, etc., hasta que una versión final es obtenida con el último clasificador del montaje. De hecho, el uso del esquema progresivo lleva al uso de árboles de decisión más pequeños, ya que ya no es necesario un clasificador complejo. En lugar de construir un clasificador grande y complejo para clasificar todo el conjunto de entrenamiento, sólo tratamos de resolver la parte más fácil del problema de clasificación, retardando el resto para un segundo clasificador, etc.<br/>La idea básica de esta tesis es, entonces, un compromiso entre el coste y la precisión bajo una restricción de confianza. Una primera clasificación es efectuada a bajo coste; si un elemento es clasificado con una confianza elevada, se acepta, y si no lo es, se rechaza y se efectúa una segunda clasificación, etc. Es básicamente, una variación del paradigma de "cascading", donde un primer clasificador se usa para calcular información adicional para cada elemento de entrada, que será usada para mejorar la precisión de clasificación de un segundo clasificador, etc. Lo que presentamos en esta tesis es, básicamente, una extensión del paradigma de "cascading" y una evaluación empírica exhaustiva de los parámetros involucrados en la creación de árboles de decisión progresivos. Algunos aspectos teóricos relacionados con los árboles de decisión progresivos como la complejidad del sistema, por ejemplo, también son tratados.