Evaluation of decision forests on classification problems using bag of features representations

Evaluation of Random Forests on large-scale classification problems using a Bag-of-Visual-Words representation Titulació Enginyeria Informàtica Autor Xavier Solé Nogués Director Arnau Ramisa Ayats Ponent Renato Alquezar Mancho President Lluís Antonio Belanche Muñoz Vocal Teresa Monreal Arnal Contingut 1 Introducció ............................................................................................................................ 1 1.1 IRI ................................................................................................................................... 1 1.2 El projecte ..................................................................................................................... 1 1.3 Objectius globals ........................................................................................................... 1 1.4 Motivació personal inical .............................................................................................. 1 1.5 Valoració personal ......................................................................................................... 2 1.6 Agraïments .................................................................................................................... 2 2 Planificació i valoració econòmica ........................................................................................ 3 2.1 Objectius assolits ........................................................................................................... 3 2.1.1 Objectius de cerca i d’aprenentatge ..................................................................... 3 2.1.2 Objectius d’experimentació .................................................................................. 3 2.1.3 Objectius de documentació .................................................................................. 4 2.2 Planificació .................................................................................................................... 5 2.2.1 Variacions de la planificació respecte l’informe ................................................... 5 2.3 Valoració econòmica ..................................................................................................... 6 3 Treball relacionat i motivació ................................................................................................ 8 3.1 Classificació d’imatges a gran escala ............................................................................. 8 3.2 Random Forests............................................................................................................. 8 3.3 Eines usades ................................................................................................................ 12 3.3.1 C/C++ ................................................................................................................... 12 3.3.2 Python ................................................................................................................. 12 3.3.3 HMTL, Javascript i CSS ......................................................................................... 13 3.3.4 Latex .................................................................................................................... 13 3.3.5 Matlab ................................................................................................................. 13 3.3.6 ImageNet ............................................................................................................. 13 3.3.7 Caltech256 ........................................................................................................... 14 4 Mètodes utilitzats ............................................................................................................... 15 4.1 Random Forests........................................................................................................... 15 4.1.1 Funció de divisió .................................................................................................. 16 4.1.2 Aleatorietat i supervisió ...................................................................................... 17 4.1.3 Funció objectiu .................................................................................................... 17 4.1.4 Paràmetres .......................................................................................................... 17 4.1.5 Cost computacional ............................................................................................. 18 4.2 Bag of Visual Words .................................................................................................... 19 4.3 ECBND i OvR-SVM ....................................................................................................... 20 5 Metodologia d’experimentació ........................................................................................... 22 5.1 Conjunts de dades utilitzats ........................................................................................ 22 5.2 Mesures de rendiment ................................................................................................ 23 5.2.1 Accuracy i error .................................................................................................. 23 5.2.2 MAP i PRC ........................................................................................................... 23 5.2.3 Mesures pròpies dels Random Forests ............................................................ 23 5.3 Ajustament de paràmetres del mètode Random Forests ....................................... 26 5.3.1 ImageNet LSVRC’10 ............................................................................................. 26 5.3.2 Caltech-256 ......................................................................................................... 27 5.4 Metodologia seguida amb els OvR-SVM ..................................................................... 28 5.5 Metodologia seguida per al mètode ECBND ............................................................... 28 6 Implementació dels experiments ........................................................................................ 29 6.1 Implementació dels diferents mètodes ...................................................................... 29 6.1.1 Random Forests ................................................................................................... 29 6.1.2 OvR-SVM ............................................................................................................. 30 6.1.3 ECBND.................................................................................................................. 30 6.1.4 Càlcul dels BoVW ................................................................................................. 30 6.2 Interfície d’experimentació ......................................................................................... 31 6.2.1 Fitxer configuració i opcions ............................................................................... 31 6.2.2 Gestió de directoris i fitxers ................................................................................ 33 6.3 Dades guardades als experiments .............................................................................. 33 6.4 Interfície gràfica d’examinació de resultats ................................................................ 36 6.4.1 Pàgines d’indexació d’experiments ..................................................................... 36 6.4.2 Pàgina de mostra d’estadístics iterant un paràmetre als Random Forests ........ 37 6.4.3 Pàgina de mostra d’estadístics als OvR-SVM ...................................................... 37 6.4.4 Pàgina de mostra d’estadístics d’una iteració ..................................................... 38 6.4.5 Pàgina d’estadístics per classe ............................................................................ 39 6.4.6 Pàgina de resultats d’imatges per classe ............................................................ 40 6.4.7 Pàgina de resultats d’una imatge ........................................................................ 41 7 Resultats experimentals i comparativa ............................................................................... 42 7.1 Màquina utilitzada per executar els experiments ....................................................... 42 7.2 Resultats experimentals a ImageNet LSVRC’10 .......................................................... 43 7.2.1 Subconjunts de dades utilitzats........................................................................... 43 7.2.2 Paràmetres 𝜌𝑓 i 𝜌𝑡 amb 20 i 100 classes ........................................................... 44 7.2.3 Paràmetres 𝐷 i 𝑇 amb 20 i 100 classes ............................................................... 46 7.2.4 Paràmetres 𝑇 i 𝐷 1000 classes ............................................................................ 48 7.2.5 Experiments amb Power Normalization ............................................................. 50 7.2.6 Mesures per mesurar el rendiment dels boscos ................................................. 52 7.2.7 Comparativa amb altres mètodes ....................................................................... 55 7.3 Resultats experimentals Caltech-256 .......................................................................... 57 7.3.1 Subconjunts de dades utilitzats........................................................................... 57 7.3.2 Experiments OvR-SVM ........................................................................................ 58 7.3.3 Experiments ECBND ........................................................................................... 59 7.3.4 Random Forests Caltech-256 paràmetre 𝐷 ........................................................ 60 7.3.5 Random Forests Caltech-256 mesures de rendiment dels boscos ..................... 64 7.3.6 Random Forests Caltech-256 ajustament de paràmetre 𝑇 ................................. 68 7.3.7 Comparativa Random Forests vs OvR-SVM a Caltech-256 ................................. 70 8 Conclusions dels experiments i treball futur ....................................................................... 74 9 Article CCIA 2014 ................................................................................................................. 75 9.1 Selecció de contingut de l’article ............................................................................. 75 10 Glossari ............................................................................................................................ 76 11 Taula d’il·lustracions ...................................................................................................... 78 12 Taula de taules ................................................................................................................ 80 13 Taula d’equacions ............................................................................................................ 81 14 Referències ...................................................................................................................... 82 1 1 Introducció 1.1 IRI L’Institut de Robòtica i Informàtica Industrial 1 (IRI) és un és un Centre d’Investigació de la Universitat Politècnica de Catalunya (UPC) i el Consell Superior d’Investigacions Científiques (CSIC). Aquest projecte és un projecte de modalitat A, dirigit per l’Arnau Ramisa, un investigador de l’IRI. 1.2 El projecte Partim de l’article Large-scale image classification using ensembles of nested dichotomies [1] d’Arnau Ramisa Ayats i Carme Torras Genís. Aquest article va ser enviat al CCIA (Congrés Internacional de l'Associació Catalana d'Intel·ligència Artificial) l’any 2013. L’article és el resultat d’un estudi sobre l’aplicació del mètode de classificació Ensembles of Class-Balanaced Nested Dichotimies (ECBND) al problema de classificació d’imatges a gran escala. Concretament utilitzant la conjunt de dades d’ImageNet LSVRC’10, que conté 1.000 classes bàsiques, i del ordre d’unes 1.200.000 d’imatges d’entrenament i 150.000 imatges de prova. L’autor de l’article necessitava una comparativa del ECBND contra el mètode Random Forests i aquest va ser el motiu inicial de començar a treballar en aquesta direcció. Durant projecte hem avaluat el mètode Random Forests [2] en el context de classificació d’imatges a gran escala, i l’hem comparat amb el mètode ECBND i el mètode One-vs-Rest Support Vector Machines (OvR-SVM). Per fer-ho, hem realitzar experiments amb el mateix conjunt d’imatges, el LSVRC’10, aprofitant els experiments per realitzar un estudi en particular dels Random Forests i presentar un article sobre aquest estudi al CCIA de l’any 2014. Finalment, també hem realitzat experiments amb Caltech-256 per tenir una altra visió del funcionament i resultats dels Random Forests. Preteníem realitzar comparacions amb més treballs que han utilitzat aquest conjunt de dades, però la gran varietat de descriptors i subconjunts d’entrenament que s’utilitzen a Caltech-256 ha dificultat aquesta tasca. 1.3 Objectius globals Els objectius principals d’aquest projecte són:  Avaluar els Random Forests en el context de classificació d’imatges a gran escala amb: o Conjunt de dades ImageNet LSVRC’10. o Conjunt de dades Caltech256.  Comparar els resultats amb el mètode OvR-SVM, ECBND i altres mètodes.  Presentar un article amb els resultats més importants al CCIA 2014. A la Secció 2.1 podem trobar una descripció més detallada dels subojectius de projecte. 1.4 Motivació personal inical Un dels motius per els quals vaig escollir aquest projecte és que m’agraden els temes de aprenentatge automàtic i visió per computador, en especial també en el món de la recerca. Un altre aspecte que vaig valorar positivament és el fet de treballar fora de la FIB, ja que no hi tenia experiència i em va semblar que seria positiu per a la meva formació. Es per això, que em vaig interessar per aquest projecte i finalment el vaig elegir com a projecte de final de carrera. 1 http://www.iri.upc.edu/ 2 1.5 Valoració personal Crec que aquest projecte ha sigut molt enriquidor per la meva formació i experiència en molts aspectes. Els més importants són:  L’experiència de treballar amb persones de fora de la FIB en el camp de recerca.  Els coneixements assolits en el tema de visió per computador com ara els SIFTs, els BoVW, les Spatial Pyramids, ...  Els coneixements assolits en el tema d’aprenentatge automàtic llegint treballs relacionats, parlant amb investigadors del IRI i experimentant amb alguns classificadors en concret.  Experiència en tractament de Big Data, mai havia treballat abans amb conjunts de dades tant grans.  La gran quantitat d’eines diferents amb les que he hagut de treballar, com podem veure a la Secció 3.3. Això m’ha ajudat a aprendre a utilitzar algunes eines que desconeixia i a millorar en altres que ja coneixia.  L’experiència en la redacció d’un article per a un congrés, assessorat i revisat per investigadors de l’IRI. Tenint en compte tots aquests aspectes, com ja he dit abans, considero que el projecte ha estat molt enriquidor i recomanaria desenvolupar projectes semblants a alumnes que estiguin interessats en aquests temes. 1.6 Agraïments Dedico aquest projecte a la meva mare Conxa Nogués i a la seva parella de fet Albert Riera, per les ajudes i el suport que m’han proporcionat per poder realitzar-lo. Vull donar les gràcies a l’Arnau Raimsa (director del projecte) per el temps que ha dedicat a assessorar-me degut a la meva inexperiència en alguns temes. També li vull donar les gràcies a l’Arnau Ramisa i a la Carme Torras per haver revisar tant detalladament l’article que hem enviat al CCIA 2014. 3 2 Planificació i valoració econòmica 2.1 Objectius assolits A la Secció 1.3 hem vist els objectius del projecte a nivell molt general. En aquest apartat els desglossarem els objectius a un nivell més concret agrupant-los en tres categories, objectius de cerca i aprenentatge; objectius d’experimentació; i objectius de documentació. 2.1.1 Objectius de cerca i d’aprenentatge Els objectius d’aprenentatge són aquells que fan referència a entendre els mètodes que hem utilitzat, i trobar altres treballs que utilitzin aquests mètodes per poder comparar-los amb el nostre i avaluar si la línia que agafem és correcta. Enteniment de els Random Forests Per entendre a fons el funcionament dels Random Forests, hem llegit el llibre Shotton [3] i alguns articles que utilitzaven Random Forests aplicats a la visió per computador. A la Secció 4.1 expliquem els detalls d’aquest mètode i a la Secció 3.2 parlem del treball relacionat amb aquest mètode. Enteniment de els BoVW Per entendre els Bag of Visual Words, hem vist la manera com els calculava el LSVRC’10 i hem llegit alguns treballs que els utilitzen. A la Secció 4.2 expliquem els detalls d’aquests descriptors. Enteniment del LSVRC’10 Per entendre el LSVRC’10, hem vist algunes de les seves classes i com s’utilitza en alguns treballs. Enteniment de Caltech-256 Per entendre el Caltech-256, hem vist algunes de les seves classes i com s’usa en alguns treballs. Cerca i lectura de treball relacionat Per poder comparar i tenir millor idea sobre l’estat de l’art del nostre escenari, hem buscat i llegit a fons altres treballs sobre aquests temes. 2.1.2 Objectius d’experimentació Els objectius d’experimentació són aquells que fan referència al disseny, implementació, i avaluació i comparació de resultats dels experiments que hem realitzat. Enteniment i adaptació de la llibreria Sherwood Per implementar el mètode Random Forests, hem adaptat la llibreria Sherwood per als nostres experiments com descrivim a la Secció 6.1.1. Disseny i implementació de la interfície per a LSVRC’10 Per a poder realitzar i analitzar correctament els nostres experiments amb el LSVRC’10, hem dissenyat i implementat una interfície d’experimentació (Secció 6.2) i anàlisi de resultats (Secció 6.4). 4 Experiments amb el LSVRC’10 Hem realitzar experiments amb el conjunt de dades ImageNet LSVRC’10 utilitzant el mètode Random Forests. A la Secció 5.3.1 hem definit la nostra estratègia de disseny experimental. A la Secció 7.2 hem mostrat i discutit els resultats obtinguts. Implementació i càlcul dels BoVW Hem calculat els descriptors Bag of Visual Words pel conjunt de dades Caltech-256. A la Secció 6.1.4 trobem els detalls d’aquesta implementació. Enteniment i implementació amb la Shogun-toolbox Per implementar el mètode OvR-SVM, hem utilitzant la llibreria Shogun-toolbox com descrivim a la Secció 6.1.2. Adaptació de la interfície a Caltech-256 Per a poder realitzar i analitzar correctament els nostres experiments amb Caltech-256, hem adaptat la interfície d’experimentació (Secció 6.2) i anàlisi de resultats (Secció 6.4) a Caltech256. Adaptació de la interfície del ECBND a Caltech-256 Per a poder realitzar i analitzar correctament els nostres experiments del ECBND amb Caltech256, hem adaptat la interfície implementada per al treball Ramisa et al. [1] (Secció 6.1.3) a Caltech-256. Experiments amb Caltech-256 Hem realitzat experiments amb el conjunt de dades Caltech-256 utilitzant els mètodes Random Forests, OvR-SVM i ECBND. A la Seccions 5.3.2, 5.4 i 5.5 hem definit la nostra estratègia de disseny experimental respectivament. A la Secció 7.3 hem mostrat i discutit els resultats obtinguts. 2.1.3 Objectius de documentació Els objectius de documentació són aquells que fan referència als documents importants resultats d’aquest projecte. CCIA 2014 Hem redactat un article per presentar-lo al Congrés Internacional de l’Associació Catalana d’Intel·ligència Artificial de l’any 2014. Aquest article encara es troba en procés de revisió. Memòria Hem redactat la memòria del projecte, que en concret és aquest document. 5 2.2 Planificació Seguidament trobarem la taula de planificació de tasques definitiva del projecte. Cada període “Px” representa 3 setmanes. Per agrupar la feina en tasques, hem assignat una tasca a cada objectiu de la secció anterior. Els períodes marcats en blau fosc fan referència a tasques de cerca i aprenentatge; els marcats en roig fan referència a tasques d’experimentació; i els marcats en verd fan referència a tasques de documentació. P1 P2 P3 P4 P5 P6 P7 P8 Enteniment de els Random Forests Enteniment de els BoVW Enteniment del LSVRC’10 Enteniment de Caltech-256 Cerca i lectura de treball relacionat Enteniment i adaptació de la llibreria Sherwood Disseny i implementació de la interfície per a LSVRC’10 Experiments amb el LSVRC’10 Implementació i càlcul dels BoVW Enteniment i implementació amb la Shogun-toolbox Adaptació de la interfície a Caltech-256 Adaptació de la interfície del ECBND a Caltech-256 Experiments amb Caltech-256 CCIA14 Memòria Taula 1. Planificació de tasques del projecte 2.2.1 Variacions de la planificació respecte l’informe Després d’estudiar més a fons les tasques que encara no havíem realitzat quan vam presentar l’informe, hem decidit eliminar-ne algunes. També n’hem afegit d’altres que han compensat el volum de feina eliminat. Tasques eliminades Hem eliminat les tasques referents a elaborar experiments amb el mètode ECBND al LSVRC’10, ja que finalment vam poder recuperar els resultats del treball [1]. Per a nosaltres era més important redactar un article per al CCIA 2014 abans que repetir els experiments amb el ECBND al LSVRC’10. Tasques afegides Hem afegit la tasca de redactar un article per al CCIA 2014. També hem afegit la tasca d’executar experiments utilitzant el mètode OvR-SVM al conjunt de dades Caltech-256, amb l’objectiu de validar la bondat dels nostres BoVW (Bag of Visual Words) i comparar els OvR-SVM amb els Random Forests en aquest context. 12 3.3 Eines usades En aquesta secció descriurem la gran varietat d’eines que he utilitzat per dur a terme el projecte. 3.3.1 C/C++ C/C++ és un llenguatge de programació molt robust, transparent i eficient. Necessitàvem utilitzar un llenguatge eficient i que ens permetés gestionar bé la memòria, ja que volíem treballar amb dades d’una dimensió molt gran i mètodes que podien arribar a trigar dies i necessitar quantitats elevades de memòria. Per això l’hem elegit per a implementar el mètode Random Forests en els nostres experiments. També va influir en la nostra decisió el fet de trobar llibreries que implementaven els Random Forests i altres funcionalitats que necessitàvem, ja que això ens estalviava feina i donava més credibilitat a la nostra implementació, sent llibreries ja provades i utilitzades en altres treballs. Per tal d’implementar el mètode Random Forests, hem utilitzat la llibreria Sherwood 3 en C++, presentada com a eina per implementar boscos de decisió en el llibre Decision Forests for Computer Vision and Medical Image Analysis [3]. Per implementar les interfícies necessàries per a la seva adaptació als diferents conjunts de dades, vam utilitzar la llibreria de càlcul matricial Yael 4 , en concret les funcionalitats de poder llegir fitxers en format comprimit fvecs i normalització d’histogrames. Hem realitzat modificacions a la llibreria Sherwood per adaptar-la a les nostres necessitats. Una d’elles ha estat paral·lelitzar l’entrenament i avaluació dels boscos utilitzant OpenMP 5 [11]. Podeu trobar més informació d’aquestes modificacions a la Secció 6.1.1. 3.3.2 Python Python és un llenguatge de programació que agilitza la implementació, però és poc eficient en termes de temps d’execució i de memòria. Facilita el desenvolupament de software per la seva simplicitat, i també la gran quantitat i varietat de mòduls implementats que pots trobar a la xarxa. Necessitàvem un llenguatge que ens permetés implementar una interfície de llançament d’experiments, gestió de fitxers i càlcul d’estadístics, sense haver de dedicar molt temps al seu desenvolupament, ja que només havia de ser utilitzada per aquests experiments. Per això hem decidir utilitzar-lo, implementant amb ell els scripts per llançament d’experiments. Aquests scripts han estat els encarregats de gestionar els paràmetres, directoris, llençar varis experiments iterant paràmetres, i generar alguns estadístics i gràfics dels resultats. Per a generar les gràfiques hem utilitzat la llibreria Matplotib 6 [12]. Per calcular el MAP i PRC dels resultats de regressió hem utilitzat la toolbox Shogun 7 [13]. També hem utilitzat la Shogun per executar experiments amb classificadors OvR-SVM en el conjunt de dades Caltech256. 3 http://research.microsoft.com/en-us/downloads/52d5b9c3-a638-42a1-94a5-d549e2251728/ 4 https://gforge.inria.fr/projects/yael/ 5 http://www.openmp.org/wp/ 6 http://www.matplotlib.org/ 7 http://www.shogun-toolbox.org/ 13 3.3.3 HMTL, Javascript i CSS Una part important de qualsevol experiment és l’anàlisi de resultats, tant per poder validar la seva correcta implementació com per poder estudiar a fons el seu comportament. Hem optat per utilitzar les tecnologies que es fan servir en l’entorn web per a poder tenir una representació gràfica d’aquests resultats, per la seva gran varietat de funcionalitats implementades que es poden trobar a la xarxa, i la seva facilitat d’ús i implementació. Podeu trobar els detalls de l’ús que hem fet d’aquestes tecnologies a la Secció 6.4. 3.3.4 Latex Hem utilitzat Latex per escriure l’article que hem enviat al CCIA 2014, ja que és una eina que ajuda a gestionar de manera ràpida les referències i a més facilita molt la introducció de formules matemàtiques. També l’hem escollit perquè és l’eina que s’acostuma a utilitzar en el món científic de la computació, i per tant dona cert prestigi i un format estàndard que facilita la lectura. 3.3.5 Matlab Per a calcular els descriptors de les imatges del conjunt de dades Caltech256 hem utilitzat Matlab, en concret les llibreries VLFeat 8 [14] i Yael 9 . En el cas de VLFeat, la llibreria de càlcul de descriptors per imatges que utilitza el conjunt de dades LSVRC’10, l’hem utilitzat perquè volíem calcular els descriptors de Caltech256 de la mateixa manera que LSVRC’10, obtenint així resultats més comparables. També hem utilitzat els scripts d’avaluació de ImageNet LSVRC’10, escrits en Matlab, per fer els nostres resultats el més comparable possibles. 3.3.6 ImageNet ImageNet [15] és un conjunt d’imatges categoritzades de manera jeràrquica, concretament seguint la jerarquia de WordNet. El seu objectiu és crear un repositori d’imatges públic de gran escala, per a cobrir la necessitat creixent, que existeix en els mons de la recerca i l’educació, de poder treballar amb una eina d’aquestes característiques. Cada any ImageNet realitza una competició de mètodes de classificació d’imatges a gran escala, per la qual utilitza un subconjunt del seu conjunt de dades. Nosaltres hem aprofitat un d’aquests subconjunts, concretament l’ImageNet LSVRC’10 10 (Large Scale Visual Recognition Challenge 2010), que conté 1.000 classes bàsiques, i de l’ordre d’unes 1.200.000 d’imatges d’entrenament i 150.000 imatges de prova. Utilitzar un conjunt de dades d’aquestes característiques facilita la comparació amb altres mètodes, la reproducció dels experiments en un futur i la interpretació dels nostres resultats per d’altres persones. Ja que proporciona uns descriptors d’imatges precalculats, que són accessibles per a tothom, i molt genèrics, de manera que no intenten beneficiar directament cap mètode en concret. A més, és descriu amb molt detall el procediment seguit per calcular-los. Així doncs, hem utilitzat directament els descriptors 8 http://www.vlfeat.org/ 9 https://gforge.inria.fr/projects/yael/ 10 http://www.image-net.org/challenges/LSVRC/2010/download-public 14 d’aquesta competició i els seus scripts d’avaluació, per a donar als nostres experiments els avantatges descrits anteriorment. 3.3.7 Caltech256 Caltech256 [16] és un conjunt d’imatges categoritzades que conté 256 classes i 30608 imatges. Es tracta d’un conjunt de dades més antic que ImageNet i no té cap subconjunt amb els descriptors precalculat. Preteníem experimentar amb ell per obtenir resultats amb un conjunt d’imatges més fàcil que ImageNet i amb publicacions que ens permetessin comparar-nos amb ell. Però el fet de no tenir un subconjunt d’experimentació amb descriptors bàsics, ha sigut crític a l’hora de realitzar experiments i comparar-ne els resultats, com veurem a les conclusions del projecte. 15 4 Mètodes utilitzats En aquesta secció descriurem a fons els dos mètodes principals d’aquest projecte: el Random Forests i el Bag of Visual Words (BoVW). També descriurem més breument els mètodes ECBND i OvR-SVM, ja que els hem executat per comparar resultats. 4.1 Random Forests En aquesta secció descriurem el mètode Random Forests proposat per Breiman et al. [2], el qual avaluarem en els nostres experiments. Els Random Forests són conjunts d’arbres de decisió generats aleatòriament. Per construir-los, es segueix un procés d’entrenament en el que agafem com a entrada la base de mostres d’entrenament que anomenarem 𝐼. Cada mostra conté un vector amb els seus features i una etiqueta que indica la seva categoria. Els arbres són construïts recursivament partint del node arrel, que conté tot el conjunt d’entrenament. Els fills d’un node contenen subconjunts disjunts del conjunt de mostres del seu pare, la unió d’aquest conjunts (els dels fills) és igual al conjunt de mostres que conté el seu pare. Cada node és avaluat per una funció de divisió que decideix si el node es un node de divisió o bé un node fulla, i en el cas que sigui un node de divisió, aquesta funció també decideix de quina manera s’ha de partir el conjunt de mostres del node pare. Més endavant definirem la funció de divisió que utilitzem en el nostres experiments. Així doncs, tenim dos tipus de nodes als nostres arbres, els nodes de divisió i els nodes fulla. Els nodes de divisió contenen les dades necessàries per a decidir a quin dels seus dos nodes fills pertany una mostra. Aquestes dades són obtingudes mitjançant una funció de divisió, per tant depenen d’aquesta funció. En els nodes fulla emmagatzemem un histograma que conté la probabilitat de que una mostra del seu conjunt de mostres pertanyi a 𝑐𝑗, tal que 𝑐𝑗∈𝐶, i 𝐶 és el conjunt de categories del nostre problema. Aquesta probabilitat es calcula sumant el nombre de mostres d’una classe 𝑐𝑗 que han arribat a un node fulla i dividint-lo per el nombre de mostres total de mostres del subconjunt de mostres d’aquest node fulla. Il·lustració 5. Representació gràfica de l’avaluació d’una mostra de prova per part del mètode Random Forests. Les fletxes pintades de color vermell (i també més gruixudes) indiquen el camí que ha seguit la mostra avaluada en els diferents arbres. 16 Un cop tenim el nostre bosc entrenat, podem passar a la fase d’avaluació de mostres del conjunt de dades de prova. En aquesta fase, cada arbre decideix la probabilitat de que una mostra pertanyi a una certa classe 𝑐𝑗. Per fer-ho, la mostra comença pel node arrel i va seguint el camí que li indica el criteri de cada node de divisió, aquest criteri es pot avaluar amb les dades guardades als nodes de divisió (Secció 4.1.1) i les dades de la mostra. L’arbre dona com a resultat un histograma de probabilitats, contingut en el node fulla al qual arriba aquesta mostra. Després d’obtenir l’avaluació de tots els arbres del bosc, cal unificar els diferents histogrames que han resultat de cada arbre. Per fer-ho realitzem la mitja aritmètica d’aquests histogrames. Més formalment, podem veure com és calcula la probabilitat 𝑃(𝑐𝑗|𝐿) d’una mostra que pertany a una classe 𝑐𝑗, donat el conjunt d’histogrames generat per els arbres en avaluar aquesta mostra 𝐿={𝑙1,…,𝑙𝑇} a l’Equació 3: 𝑃(𝑐𝑗|𝐿)=1 𝑇∑𝑃(𝑐𝑗|𝑙𝑡) 𝑇 𝑡=1 | ∀𝑐𝑗∈𝐶 Equació 3. Unificació de les respostes dels arbres dels Random Forest 4.1.1 Funció de divisió Els Random Forests es poden generar utilitzant diferents funcions de divisió. Aquestes funcions es poden classificar en tres tipus:  Lineal alineada a un eix: Realitza particions de l’espai de features mitjançant un hiperplà aleatori alineat a un eix. Té l’avantatge de que es molt simple d’implementar i de computar. Per altra banda, només permet comparar un feature/eix per node, i si el nostre problema requereix fer moltes subdivisions els arbres seran molt profunds, fet que no ens interessa, ja que l’espai ocupat per un arbre creix exponencialment respecte la seva profunditat.  Lineal: Realitza particions de l’espai de features mitjançant un hiperplà aleatori. Té l’inconvenient que es molt més difícil d’implementar i més costos computacionalment que la anterior. Per altra banda, pot ser una bona alternativa quan el nostre conjunt de dades requereix molts nivells de comparacions, ja que permet comparar més d’un feature/eix per node, i ho fa de la manera més simple possible, amb un hiperplà.  No lineal: Realitza particions de l’espai de features mitjançant funcions no lineals. Aquest tipus de funcions són molt complexes a nivell matemàtic, i per tant, molt difícils d’implementar. Per altra banda, els Random Forests ja poden generar divisions no lineals combinant varies divisions lineals, ho aconsegueixen al combinar els resultats dels diferents arbres. Així doncs, la seva alta complexitat i el fet que Random Forests no les necessiten, fan que aquests tipus de funcions no s’hagin utilitzat gairebé mai i que molts experts recomanin no utilitzar-les, com podem veure al llibre Shotton et al. [3]. En el nostre cas, utilitzarem sempre la funció alineada a un eix. Ja que és la més utilitzada i recomanada típicament en els Random Forests, per la seva simplicitat, el seu baix cost computacional i el fet que els Random Forests poden generar tot tipus de divisions combinant diferents arbres. 17 4.1.2 Aleatorietat i supervisió Vistos els diferents tipus de divisió, en aquesta secció ens centrarem en la manera de seleccionar els hiperplans alineats a un eix, els quals defineixen la divisió en un node. El mètode genera divisions aleatòries, però alhora supervisades. Per a cada node, genera aleatòriament varies divisions candidates i elegeix la millor mitjançant una funció objectiu (Secció 4.1.3). Si la funció objectiu determina que cap de les divisions candidates millora el resultat, aleshores el node en qüestió és una fulla. Cada divisió candidata està formada per un feature/eix i un valor llindar, entenent que dividirem el conjunt de mostres fent baixar cap a un costat les mostres que tinguin un valor superior a aquest llindar en aquest eix, i cap a l’altre les mostres que tinguin un valor superior a aquest llinda en aquest eix. Per generar les diferents divisions candidates el mètode defineix dos paràmetres. El primer, 𝜌𝑓, és la quantitat de features/eixos que són elegits per generar hiperplans candidats que hi estiguin alineats. El segon, 𝜌𝑡, és el nombre de valors llindar que seran elegits per a cada eix. És a dir, en total el nombre de candidats generats a cada node és 𝜌𝑓·𝜌𝑡. 4.1.3 Funció objectiu Com ja hem vist a la anterior, el mètode utilitza una funció objectiu per avaluar la bondat de les divisions candidates a cada node. En el nostre cas utilitzarem la més comuna en els Random Forests, el guany en entropia de Shannon. Sent 𝐼𝑖 el conjunt de mostres que formen un node, 𝐼𝑙 i 𝐼𝑟 el conjunt de mostres de els seus dos fills en una divisió candidata; definim els seus respectius valors d’entropia de Shannon com 𝐸(𝐼𝑖), 𝐸(𝐼𝑙) i 𝐸(𝐼𝑟) respectivament. Veiem la definició de la funció de guany 𝐺: 𝐺(𝐼𝑖,𝐼𝑙,𝐼𝑟)=𝐸(𝐼𝑖)−𝐸(𝐼𝑙)·|𝐼𝑙|+𝐸(𝐼𝑟)·|𝐼𝑟| |𝐼𝑖| Equació 4. Funció objectiu dels Random Forests Considerem que un node és una fulla quan 𝐺< 𝜆𝐺. 4.1.4 Paràmetres Un cop definit el nostre mètode recollim els seu cinc paràmetres:  𝑇, nombre d’arbres del bosc.  𝐷, profunditat màxima dels arbres (excloent el node arrel).  𝜌𝑓, nombre de features/eixos candidats node (Explicat a la Secció 4.1.2).  𝜌𝑡, nombre de valors llindars candidats per eix i per node (Explicat a la Secció 4.1.2).  𝜆𝐺, llindar mínim de guany que ha de complir una divisió candidata per ser considerada vàlida (Explicat a la Secció 4.1.3). 18 4.1.5 Cost computacional El cost computacional d’entrenar el mètode Random Forests és 𝑂(2𝐷·𝑇·𝜌𝑓·𝜌𝑡) en el cas pitjor. Tot i així, cal tenir en compte que els arbres no tenen perquè estar balancejats i per tant el seu cost pot variar en cas mitjà. Aquesta fita superior representa el cost quan tots els arbres del bosc estan balancejats i arriben a la profunditat màxima 𝐷. El cost computacional d’avaluar una mostra en el cas pitjor és 𝑂(𝑇·𝐷), també cal tenir en compte que pot variar en el cas mitjà depenent del balanceig dels arbres. Un altre factor a tenir en compte és el cost d’unificar els resultats dels diferents arbres, en notació asimptòtica no es veu reflectit perquè és una constat que multiplica el paràmetre 𝑇. Aquesta constant té un valor de C sumes i una divisió, sent C el nombre de classes del problema. Per tant, pot ser crític tenir en compte que el paràmetre 𝑇 té molt més pes que el 𝐷, tenint en compte que en cost real està multiplicat per una constant de magnitud molt més gran. El cost espacial del mètode és 𝑂(2𝐷·𝑇) nodes en el cas pitjor. El cas mitjà també depèn del balanceig dels arbres. Un factor important, és el nombre de classes (𝐶) del nostre problema, ja que hem expressat el cost en nodes, i cada node fulla allotja un vector de mida 𝐶 amb la probabilitat de cada classe. Per tant, el nombre de classes multiplicaria linealment el cost. 19 4.2 Bag of Visual Words En aquesta secció descriurem els Bag of Visual Words (BoVW), la representació que hem utilitzat per als features d’imatges als nostres experiments. A la Il·lustració 6 podem veure una representació gràfica d’aquest procediment. Il·lustració 6. Representació gràfica del càlcul dels BoVW. Bag of Visual Words (BoVW) és una representació comprimida de features d’imatges basada en semàntica de textures. Per obtenir aquesta representació, donada una imatge, primer cal calcular els SIFT [17] d’aquesta imatge. Els SIFT són una representació que conté molta informació, i per això són molt costosos i difícils d’interpretar per un algorisme d’aprenentatge automàtic. Una manera de reduir la complexitat d’aquests descriptors és comprimir-los a BoVW. Per a poder comprimir la informació del SIFT en un BoVW, primer cal decidir quines textures pertanyeran a cada classe del vocabulari. Per fer-ho, típicament s’aplica el mètode k-means sobre els SIFTs de totes les imatges del conjunt d’entrenament. D’aquesta manera es determinen K centroides que defineixen les K diferents classes de textures que apareixen a les nostres imatges. Un cop definit el vocabulari, només resta calcular, per a cada imatge del conjunt de dades, el nombre de SIFT que pertanyen a cada classe de vocabulari, i desar-lo en vectors de mida K que seran els descriptors de les nostres imatges. 20 4.3 ECBND i OvR-SVM En aquesta secció explicarem breument els mètodes OvR-SVM i ECBND, els quals es composen de classificadors SVM. Els classificadors SVM resolen el problema de classificació de dues categories buscant un hiperplà que les separa. No aprofundirem tant en els mètodes OvR-SVM i ECBND com hem fet amb els Random Forests, ja que l’objectiu d’aquest projecte no es avaluar els mètodes OvR-SVM i ECBND, només els volem comparar amb els Random Forests. A la Il·lustració 7 podem veure una explicació gràfica d’aquests mètodes. Il·lustració 7. Explicació gràfica dels mètodes OvR-SVM (esquerra) i ECBND (dreta) amb un exemple de 8 classes. Les caixes verdes i vermelles representen els classificadors SVM (les verdes contenen les mostres classificades com a positives i les vermelles les mostres classificades com a negatives). La imatge s’ha extret del treball de Ramisa [1]. OvR-SVM En aquest apartat explicarem el mètode One-vs-Rest Suport Vector Machines (OvR-SVM), avaluat en l’escenari de classificació d’imatges a gran escala en el treball de Perronnin et al. [18]. El mètode OvR-SVM es composa de |𝐶| classificadors SVM, on 𝐶={𝑐1,…,𝑐𝑛} és el conjunt de classes d’un problema de classificació. Cada classificador SVM és entrenat amb un conjunt d’entrenament de dues categories, la primera categoria conté totes les mostres d’una classe 𝑐𝑖, i la segona categoria conté mostres d’imatges que no pertanyen a aquesta classe 𝑐𝑖. Així doncs, tenim un classificador SVM per a cada classe 𝑐𝑖, que ens determina la probabilitat de que una imatge pertanyi a aquesta classe 𝑐𝑖. Finalment, el mètode unifica aquestes probabilitats en un vector on cada posició correspon a una classe, la classe d’aquest vector que tingui probabilitat més alta serà la que es donarà com a solució. ECBND En aquesta secció explicarem el mètode Ensembles of Class-Balanced Nested Dichotomies (ECBND), avaluat al escenari de classificació d’imatges a gran escala en el treball Ramisa [1]. El ECBND té dues variants, la Simple Branching (SB) i la Full Branch Aggregation (FBA). El mètode ECBND està format per un conjunt d’arbres balancejats, on cada arbre conté |𝐶|−1 nodes de divisió, on 𝐶={𝑐1,…,𝑐𝑛} és el conjunt de classes del problema de classificació. Cada node no fulla divideix recursivament el conjunt d’entrenament en dues categories, assignant aleatòriament les imatges de la meitat de les classes a una d’aquestes categories i les imatges de l’altra meitat de les classes a l’altra categoria. Amb les imatges d’aquestes dues categories, 21 per a cada node, s’entrena un classificador SVM que serà l’encarregat de decidir la probabilitat de que una imatge pertanyi a una d’aquestes categories a l’etapa d’avaluació. Un node és una fulla quan el seu conjunt d’entrenament conté les mostres d’una sola classe. A l’hora d’avaluar imatges, cada una de les dues variants de l’ECBND ho fa duna manera diferent. A continuació descriurem la manera de procedir de les dues variants:  SB: En aquesta variant, cada arbre vota una classe. A cada arbre, la imatge que volem avaluar comença per el node arrel i va seguint el camí que li indiquen els classificadors SVM dels nodes fins a arribar a un node fulla. En total s’avaluen log2(|𝐶|−1) classificadors SVM, i l’arbre vota la classe que correspon a la fulla on ha arribat la imatge avaluada. Finalment, es realitza un recompte de vots de tots els arbres i es dona com a resultat la classe que ha obtingut més vots.  FBA: En aquesta variant, els arbres generen un vector de probabilitats on cada posició correspon a una classe. A cada arbre, la imatge que volem avaluar comença pel node arrel i és avaluada recursivament en tots els nodes del arbre. Cada node fulla retorna la probabilitat acumulada resultant d’avaluar els classificadors SVM dels nodes que formen el camí cap aquesta fulla des de l’arrel. S’avaluen tots els classificadors SVM de l’arbre, |𝐶|−1 en total. Tenint en compte que cada fulla correspon a una classe, generem el vector de probabilitats de les classes corresponents. La probabilitat de que una imatge pertanyi a una classe, es calcula multiplicant les probabilitats resultants d’avaluar aquesta imatge amb classificadors SVM que es troben a la branca de la seva fulla associada a aquesta classe. Finalment, s’unifiquen els vectors de probabilitats resultants de cada arbre mitjançant una mitja aritmètica de probabilitats, es a dir, s’unifica de la mateixa manera que en el mètode Random Forests. 28 5.4 Metodologia seguida amb els OvR-SVM L’objectiu del nostre projecte no és avaluar el rendiment del mètode OvR-SVM (One-vs-Rest Support Vector Machines) descrit Secció 4.3, però hem experimentat amb ells en el conjunt de dades Caltech-256 per dues raons. La primera per validar la correctesa dels BoVW que hem calculat per Caltech-256, la segona per tenir un mètode amb que comparar els Random Forests utilitzant aquests descriptors i també validar que la seva implementació és correcta. Per això hem realitzat experiments utilitzant els mateixos subconjunts de Caltech-256 que amb els Random Forests. Així doncs, hem experimentat amb el classificador SVM Kernel RBF 2. Per reduir el nombre de factors, basant-nos en altres treballs, hem fixat el paràmetre 𝐶=1 utilitzat el mateix nombre d’imatges positives i negatives. També hem fixat el paràmetre width, concretament a la mitjana del Kernel calculat amb witdh = 1. Aquests ajustament de 𝐶 i width, donen molt bons resultats segons hem vist en altres treballs, no és el resultat més òptim que es pot aconseguir amb SVM Kernel RBF 2, però s’hi aproxima. Per això s’utilitza aquesta aproximació, per evitar la fase d’ajustament del paràmetres d’aquests classificadors, reduint així el cost d’experimentar amb ells. Després de fixar els paràmetres, només ens queda tractar el tema de la replicació d’experiments. Els SVM depenen de factors aleatoris i per això hem decidit executar 5 rèpliques de cada experiment per obtenir una mitja de resultats més fiable. 5.5 Metodologia seguida per al mètode ECBND L’objectiu del nostre projecte no és avaluar el rendiment del mètode ECBND (Ensembles of ClassBalanced Nested Dichotimies) Secció 4.3, però hem experimentat amb ells en el conjunt de dades Caltech-256 per poder-los comparar amb els Random Forests. Per això hem realitzat experiments utilitzant mateixos subconjunts de Caltech-256 que amb els Random Forests. El mètode ECBND té dues variants diferents, la variant Full Branch Aggregation (FBA) i la variant Single Branching (SB), com podem veure al treball Ramisa [1]. Hem executat els mateixos experiments per les dues variants. Pel que fa als paràmetres, el mètode ECBND només en té un, el nombre d’arbres. Per trobar el seu millor valor a Caltech-256, hem executat experiments amb valors incrementals del nombre d’arbres per a les dues versions de Caltech-256 i les dues variants del ECBND. Després de fixar els paràmetres, només ens queda tractar el tema de la replicació d’experiments. En el cas del ECBND, també hem trobat a la literatura que no necessita replicació si el nombre d’arbres és suficientment gran. Per això hem decidit no replicar els experiments, ja que en el cas dels Random Forests no hem replicat els experiments utilitzant la mateixa premissa. 29 6 Implementació dels experiments En aquesta secció explicarem alguns detalls d’implementació dels mètodes amb els quals hem experimentat, la interfície que hem implementat per analitzar els resultats i les dades que hem guardat en els experiments. No es pretén donar una especificació completa del software que hem implementat, ja que es tracta d’un software d’ús personal. Només es pretén mostrar detalls que permeten aprofundir el la metodologia de treball i els detalls importants d’implementació a nivell experimental. 6.1 Implementació dels diferents mètodes En aquesta secció descriurem la implementació els mètodes Random Forests, OvR-SVM i ECBND. 6.1.1 Random Forests A l’hora de decidir la manera d’implementar el mètode Random Forets [2] en el nostre projecte, primer hem analitzat l’escenari en que l’havíem d’utilitzar. Havíem de treballar amb grans quantitats de dades. Per això hem decidit implementar-los amb un llenguatge eficient com C++, per evitar problemes de memòria i minimitzar el temps d’execució dels nostres experiments, que anticipàvem que seria elevat. També hem valorat positivament la possibilitat d’utilitzar una llibreria que implementes el mètode Random Forests, ja que això reduiria el temps de desenvolupament, facilitaria la reproducció dels nostres experiments, i donaria més credibilitat als nostres resultats tractant-se d’una llibreria provada per diverses persones. Per això hem implementat el mètode Random Forests utilitzat la llibreria Sherwood en C++, presentada com a eina per implementar boscos de decisió en el llibre Decision Forests for Computer Vision and Medical Image Analysis de Shotton et al. [3]. Primer hem implementat les interfícies per adaptar la llibreria Sherwood al conjunt de dades LSVRC’10, utilitzant la llibreria Yael per a implementar la lectura dels features guardats en fitxers en format fvecs. Seguidament hem implementat el codi en C++ per a poder llegir els diferents paràmetres dels experiments, i escriure tots els resultats i estadístics que volíem recollir en els experiments. Finalment, hem decidit fer dues modificacions al codi de la llibreria. La primera, amb l’objectiu d’afegir la funcionalitat d’entrenar i avaluar els arbres en paral·lel, utilitzant la llibreria openMP (en aquesta modificació es paral·lelitza a nivell d’arbre i no a nivell de node). Tenint en compte que la llibreria Sherwood no implementa aquesta opció, i hem cregut necessari disposar d’ella, perquè els nostres experiments trigaven molt temps en executar-se i a més disposàvem d’una maquina amb 12 fils d’execució per executar-los. La segona modificació l’hem realitzada per solucionar un problema que ens ha sorgit al voler executar experiments amb boscos molt grans. Aquest problema era la necessitat d’haver de tenir tot el bosc carregat a memòria per entrenar-lo i/o avaluar-lo. Aquest fet ens limitava molt la mida del bosc, i en els primers experiments hem vist que per treballar amb conjunts de dades de gran escala necessitàvem boscos molt grans, bastant més grans que la memòria de la nostra màquina que era de 16 GB. Per això, hem implementat una opció que permetia guardar el bosc a disc i només mantenir a memòria un arbre per fil d’execució durant l’entrament i l’avaluació. 30 6.1.2 OvR-SVM Per implementar el mètode OvR-SVM, descrit Secció 4.3, hem utilitzat la toolbox Shogun 1.1.0, concretament la seva interfície de python-modular. Tot i tenir la interfície per python, la toolbox Shogun està implementada amb C++ de manera eficient. Així que ens permet gaudir de la agilitat en el desenvolupament de python i de la eficiència de C++. Per això l’hem elegit. Hem implementat el mètode OvR-SVM Kernel RBF 2 utilitzant el mòdul “LibSVM” de la toolbox Shogun. La unificació de resultats dels diferents classificadors SVM l’hem implementat amb python. La lectura dels fitxers de features en format comprimit fvecs, l’hem implementat mitjançant la interfície python de la llibreria Yael. Finalment hem implementat l’escriptura de resultats i estadístics també en python. 6.1.3 ECBND Per a executar els experiments amb el mètode ECBND (Ensembles of Class Balanced Nested dichotomies) descrit a la Secció 4.3, hem utilitzat la implementació que va realitzar l’Arnau Ramisa per en el seu treball [1], així com la seva interfície d’anàlisi de resultats. Només ha calgut adaptar-la als nostres fitxers de features de Caltech-256 en format fvecs. Per fer-ho, hem adaptat els seus scripts en python utilitzant la llibreria Yael. 6.1.4 Càlcul dels BoVW Per implementar el càlcul dels Bag of Visual Words (BoVW) per al conjunt de dades Caltech-256 hem utilitzat Matlab. El motiu és que volíem fer-ho utilitzant la llibreria de càlcul de descriptors per imatges VLFeat, ja que l’altre conjunt de dades amb el que hem experimentat, el d’ImagetNet LSVRC’10, utilitza aquesta llibreria i volíem que els descriptors fossin el més semblant possibles per fer els experiments més comparables. Hem reduït les imatges limitant cada una de les seves dimensions a 1024, utilitzant un petit script que hem implementat amb python. Així doncs, primer calculem els SIFT de les imatges utilitzant la funció “vl_dsift” de VLFeat, seguidament executem el mètode k-means utilitzant la funció “vl_kmeans” de VLFeat per calcular els centroides que definiran el vocabulari, i finalment calculem el veí més proper utilitzant la funció “yael_nn” de la llibreria Yael. Per a calcular els centroides utilitzem 50.000 imatges del subconjunt d’entrenament, equitativament distribuïdes entre les diferents classes. 31 6.2 Interfície d’experimentació Dins l’objectiu de realitzar els experiments, hem trobat la necessitat de gestionar tots els paràmetres i directoris de diferents màquines; calcular estadístics i elaborar-ne gràfiques automàticament; gestionar fitxers; i poder llençar varis experiments consecutius mitjançant un fitxer de configuració. Totes aquestes funcionalitats són costoses d’implementar amb C++ i no són gaire costoses computacionalment. Per això hem decidir elaborar uns scripts en python que s’encarreguin de llençar els experiments i gestionar aquestes funcions. Python és un llenguatge que facilita molt la implementació i l’objectiu d’aquesta interfície és estalviar temps i errors humans. També hem elegit python per la gran quantitat de llibreries que ens ajuden a estalviar temps a l’hora de desenvolupar aquesta interfície. Aquests scripts reben uns paràmetres que defineixen una sèrie d’experiments, amb un classificador concret, i un conjunt de dades concret. El scripts s’encarreguen de realitzar aquests experiments, recollir els resultats, calcular els estadístics dels resultats, comprimir els resultats i guardar tota aquesta informació en un format concret que es pot veure a la Secció 6.3. 6.2.1 Fitxer configuració i opcions Aquests scripts s’executen mitjançant la línia de comandes, i reben com a paràmetre un fitxer de configuració amb la descripció de l’experiment. A continuació podem veure una captura de pantalla parcial d’un d’aquests fitxers: Il·lustració 9. Captura de pantalla d’un fitxer de configuració de la interfície d’experimentació Aquest fitxer de configuració té diferents paràmetres que són llegits per una classe python. Aquests paràmetres es poden agrupar en diferents grups, com descriurem a continuació. 32 Paràmetres d’experiment En el cas dels OvR-SVM, el nostre fitxer de configuració permet elaborar experiments amb varies repliques donant valor el paràmetre NUM_TESTS. El paràmetre SEED és la llavor del sistema de nombres aleatoris que es fa servir per generar els conjunts de classes de cada rèplica, per tant podem repetir exactament el mateix experiment si utilitzem la mateixa llavor o realitzar-ne un amb classes diferents si la canviem. També permet realitzar diverses execucions del mètode Random Forests incrementant progressivament el valor d’un paràmetre i fixant els valors de la resta de paràmetres. Paràmetre Rang Descripció NUM_TEST enter positiu Nombre de repliques de l'experiment NUM_CLASSES enter positiu Nombre de classes per replica SEED enter Llavor inicial de generació de classes i del bosc PARAMETER {NT, MD, NCF, NCTF} Nom del paràmetre que es vol iterar INCREMENT enter positiu Increment del paràmetre a cada iteració NUM_ITERATIONS enter positiu Nombre total d'iteracions Taula 7. Paràmetres d’experiment Paràmetres del mètode Random Forests Aquest subgrup de paràmetres conté, en primer lloc, els paràmetres del mètode Random Forests que podem trobar explicats a la Secció 4.1.4. També conté un paràmetre que permet normalitzar els BoVW utilitzant Random Forets. Paràmetre Rang Descripció NumberOfTrees enter positiu Paràmetre 𝑇 MaxDecisionLevels enter positiu Paràmetre 𝐷 NumberOfCandidateFeatures enter positiu Paràmetre 𝜌𝑓 NumberOfCandidateThresholdsPerFeature enter positiu Paràmetre 𝜌𝑡 MinGain float positiu Paràmetre 𝜆𝐺 norm {0, 1, 2, 3} Tipus de normalització dels BoVW {no notmalitzat, L1, L2, Power Norm} respectivament Taula 8. Paràmetres d’experiment del mètode Random Forests Paràmetres d’elecció del conjunt de dades Aquest subconjunt de paràmetres permet elegir el tipus de conjunts de dades i el directori on es guardaran els experiments. Normalment el nom d’aquest directori fa referència al conjunt de dades i a algun paràmetre. Paràmetre Rang Descripció Conjunt de dades {1, 2, 3} 1: ImageNet, 2: Caltech-256-15, 3: Caltech-256-40 MODE string Directori on es guardaran els resultats Taula 9. Paràmetres d’experiment d’elecció del conjunt de dades 33 6.2.2 Gestió de directoris i fitxers Necessitàvem gestionar l’execució dels experiments en diferents maquines i l’assignació de directoris als diferents experiments. Per això vam implementar una classe en python, que llegia un fitxer amb els directoris base dependents de cada màquina, i construïa els diferents directoris a partir d’aquest fitxer i els paràmetres dels experiments. Cada experiment diferent guarda els seus resultats en un directori diferent. Si es llença a executar un experiment que ja s’havia executat abans, la classe notifica que l’experiment ja existia i dona l’opció d’esborrar-lo mitjançant un flag. Així evitem esborrar i/o repetir experiments per error. 6.3 Dades guardades als experiments Per a poder estudiar correctament és resultats i poder provar a fons el codi, hem cregut convenient guardar molta informació dels resultats i calcular estadístics que ens permetin interpretar-la. Principalment hi ha dos tipus de fitxers que composen el nostre sistema de dades, els fitxers de resultats guardats en CVS i els fitxers d’estadístics guardats en XML. També hi ha un tercer tipus de fitxers específics dels Random Forests que guarden informació estadística de la forma que té el bosc, aquests fitxers es guarden en format CSV. Hem utilitzat formats estàndard independents al llenguatge de programació utilitzat, perquè teníem la necessitat de poder treballar amb ells amb diferents llenguatges. Concretament amb C++ per als Random Forests, python per a la interfície d’experimentació i els altres classificadors, i javascript per a la interfície gràfica d’examinació de resultats. Seguidament, a la Il·lustració 10, podem trobar un diagrama que defineix l’estructura de fitxers i directoris que hem dissenyat per guardar els resultats dels estadístics, així com el contingut de cada fitxer. Aquest diagrama s’interpreta seguint una sèrie d’aclariments que descriurem a continuació agrupant-los per apartats. Restriccions generals  En color blanc trobem els fitxers i en color carn els directoris.  La informació guarda per els fitxers XML està representada en UML.  La informació que guarden els fitxers CSV també està representada en UML, entenent que cada instància de l’objecte UML correspon una línia del fitxer CSV.  El tipus de dades CSVArray(type) fa referencia a una llista de dades separada per comes a dins d’un node XML. En concret s’utilitza per guardar els valors dels eixos que fan referència als gràfics. Definicions dels directoris  ParameterItetationExperiment: guarda la informació general de varies iteracions d’un paràmetre. Es a dir, varis experiments variant incrementalment els valors d’un paràmetre i fixant la resta. Dins d’aquest directori també trobem els subdirectoris “Experiment” que corresponen als experiments fets amb els diferents valors del paràmetre iterat.  Experiment: guarda la informació d’un experiment amb tots els paràmetres fixes. Definicions dels atributs globals  dimensions: És el nombre de valors que pren el paràmetre variable (iterat) de l’experiment en les diferents execucions. Si no hi ha cap paràmetre variable, aleshores “dimension” val 1. 34  startDate: la data en la qual ha començat l’experiment.  startTime: l’hora en format HH:MM:SS en que ha començat l’experiment.  vesion: la versió del codi amb que s’ha executat l’experiment.  trainTime: el temps que ha trigat el mètode de l’experiment a entrenar-se.  testTime: el temps que ha trigat el mètode de l’experiment a avaluar les imatges de prova.  parameterValues: la llista ordenada de diferents valors que ha pres el paràmetre iterat.  treeMemMB: l’espai de memòria que ocupa un arbre del bosc en MB en els experiments del mètode Random Forests.  forestMemMB: l’espai de memòria que ocupa el bosc en MB en els experiments del mètode Random Forests.  accuracy: el valor de la mesura accuray dels resultats dels experiments. En el conjunt de dades ImageNet guardem totes les accuracy del 1 al 5, en el conjunt de dades Caltech256 només la accuracy a 1.  totalTime: el temps total que ha trigat el programa a executar-se.  AP: Average Presicion de la classe amb identificador idClasse.  idImage: l’identificador de la imatge de la que és dona el resultat imatge.  idClass: l’identificador de la classe a la que pertany realment la imatge amb identificador “idImage”.  testResult: booleà que indica la correctesa del resultat de l’avaluació de la imatge amb identificador “idImatge”.  score: la probabilitat de que una imatge pertanyi a una classe segons el nostre mètode de regressió executat en l’experiment. Definicions dels atributs específics dels Random Forests  levelEntropy: entropia d’un nivell del bosc 𝐸(𝐹,𝑙).  numNodes: nombre de nodes d’un nivell del bosc 𝐺(𝐹,𝑙).  numNullNodes: nombre de nodes nulls d’un nivell del bosc 𝑁𝑁𝑃.  numSamplesLevel: nombre de mostres d’entrenament d’un nivell del bosc 𝑁𝑆𝑃. Definicions de les gràfiques  accuracy: gràfica d’accuracy (atribut “accuracy”) entre els diferents valors del paràmetre iterat (atribut “parameterValues”). Si l’experiment guarda diferents tipus d’acuracy, es mostren tots en línies diferents.  trainTime: gràfica de temps d’entrenament (atribut “trainTime”) entre els diferents valors del paràmetre iterat (atribut “parameterValues”).  testTime: gràfica de temps d’avaluació d’imatges de prova (atribut “testTime”) entre els diferents valors del paràmetre iterat (atribut “parameterValues”).  forestMem: gràfica d’espai que ocupa el bosc a la memòria(atribut “forestMemMB”) entre els diferents valors del paràmetre iterat (atribut parameterValues).  treeMem: gràfica d’espai que ocupen els arbres a la memòria (atribut “treeMemMB”) entre els diferents valors del paràmetre iterat (atribut parameterValues).  PRC_[idClass]: gràfiques de la Precision-Recall Curve de la classe amb identificador idClass. Ni ha un per cada classe a cada experiment. 35 Il·lustració 10. Diagrama de disseny de l’estructura de fitxers de resultats i estadístics dels Random Forests 36 6.4 Interfície gràfica d’examinació de resultats Per a poder estudiar bé els resultats dels experiments i poder validar que el codi funciona correctament, hem implementat una interfície gràfica de visualització de resultats. Per fer-ho hem utilitzat HTML, CSS i javascript. Concretament, hem implementat interfícies en HTML/CSS que llegeixen els fitxers de resultats utilitzant javascript. Hem tingut en compte que aquesta interfície seria únicament d’ús personal, de disseny simple però usable i ràpida d’implementar. Per això hem decidit utilitzar aquesta tecnologia, perquè és simple, fàcil d’implementar i pot donar com a resultat interfícies ràpides i usables. Seguidament descriurem les diferents pàgines que formen la interfície, classificades en diferents grups. 6.4.1 Pàgines d’indexació d’experiments Sabent que hauríem de realitzar molts experiments durant el projecte, hem implementat pàgines per poder seleccionar quin és l’experiment que volem veure. Ho hem fet utilitzant taules ordenables de links a altres pàgines, perquè hem cregut que és la manera més fàcil d’implementar-ho, i una de les més ràpides de navegar per una persona que es coneix la interfície. Aquests links condueixen a la pàgina descrita a la Secció 6.4.3 en el cas del mètode OvR-SVM, i a la pàgina descrita a la Secció 6.4.2 en el cas del mètode Random Forests. A la Il·lustració 11 seguidament podem veure captures de pantalla d’algunes d’aquestes pàgines. Il·lustració 11. Pàgines d’indexació d’experiments 37 6.4.2 Pàgina de mostra d’estadístics iterant un paràmetre als Random Forests Aquesta pàgina mostra els resultats estadístics obtinguts iterant un paràmetre dels Random Forests, es a dir, realitzant varis experiments incrementant el valor d’aquest paràmetre i fixant la resta. Conté una taula amb el valor del paràmetre iterat, el temps dedicat a l’entrenament, el temps dedicat a avaluar imatges de prova, les diferents accuracy (1-5) i altres dades. La taula és ordenable per columnes per facilitar l’anàlisi de resultats. Seguidament la pàgina mostra les gràfiques de creixement d’aquest estadístics en funció del valor del paràmetre iterat. També mostra a la dreta una llista de links cap les pàgines dels experiments concrets (Secció 6.4.4) amb els diferents valors del paràmetre iterat. A la Il·lustració 12 poden veure una captura de pantalla d’aquesta pàgina. Il·lustració 12. Pàgina de mostra d’estadístics iterant un paràmetre als Random Forests 6.4.3 Pàgina de mostra d’estadístics als OvR-SVM Aquest pàgina mostra els resultats estadístics dels classificadors OvR-SVM, obtinguts a partir de les diferents rèpliques. En concret mostra, la mitjana d’accuracy a 1, la MAP i les seves desviacions estàndard corresponents. També permet accedir als resultats de cada rèplica mitjançant un link a la pàgina de la Secció 6.4.4. 44 7.2.2 Paràmetres 𝜌𝑓 i 𝜌𝑡 amb 20 i 100 classes Els paràmetres 𝜌𝑓 i 𝜌𝑡 controlen la supervisió i l’aleatorització com hem explicat a la Secció 4.1.2. Sabem que ens convé fixar un valor que sigui suficientment alt com per poder construir arbres lleugerament supervisats, i alhora, suficientment baix com per no perjudicar l’aleatorització, que juga un paper molt important als Random Forests. Un altre factor remarcable d’aquests paràmetres és que incrementen linealment el cost computacional d’entrenament, però no afecten al cost computacional d’avaluació ni al cost espacial. Per altra banda, treballar amb boscos lleugerament supervisats pot donar millors resultats utilitzant menys arbres, ja que la supervisió ajuda a eliminar l’avaluació de parts de l’espai de solucions que no ens interessen. Tenint en compte aquests tots aquests factors, veiem que incrementar la supervisió ajuda a reduir el cost d’avaluació, fet que ens interessa, però massa supervisió ens portaria a realitzar experiments que trigarien temps inassolibles per el projecte, ja que incrementa el cost d’entrenament i també hem d’ajustar altres paràmetres. Experiments amb ρf utilitzant 20 i 100 classes Partim de la hipòtesis que podem trobar experimentalment una cota superior per 𝜌𝑓 que ens doni el millor resultat possible, i que a l’hora sigui el més baixa possible per minimitzar el cost d’entrenament i no perjudicar la supervisió. A la Il·lustració 18, podem veure els resultats dels experiments que hem executat per trobar aquesta cota amb els subconjunts de 20 i 100 classes. Veiem que efectivament, el valor de l’accuracy creix respecte el paràmetre 𝜌𝑓 fins a cert valor llindar. També veiem que aquest creixement no varia significativament respecte el nombre de classes. Tot i que el creixement és poc significatiu per el problema aplicat a 20 i 100 classes, creiem que pot ser més significatiu per 1000 classes, degut a que l’accuracy serà més petita de base. Per tant, fixem el valor del paràmetre 𝜌𝑓 a 35, ja que és el llindar. Il·lustració 18. Gràfics d’iteració del paràmetre 𝜌𝑓 al LSVRC’10 amb 20 classes (esquerra) i 100 classes (dreta). La resta de paràmetres estan fixats a 𝑇=100, 𝐷=10 i 𝜌𝑡=30 en el gràfic de 20 classes; i 𝑇=60, 𝐷=16 i 𝜌𝑡=15 en la gràfic de 100 classes. 10 20 30 40 50 60 70 80 90 5 10 15 20 25 30 35 40 45 50 accuracy 𝜌𝑓 accu racy a 1 10 20 30 40 50 60 70 80 90 510 15 20 25 30 35 40 45 50 accuracy 𝜌𝑓 accuracy a 1 accuracy a 5 45 Experiments amb ρt utilitzant 20 i 100 classes Partim de la hipòtesis que, podem trobar experimentalment una cota superior per 𝜌𝑡 que ens doni el millor resultat possible i que a l’hora sigui el més baixa possible per minimitzar el cost d’entrenament i no perjudicar la supervisió. A la Il·lustració 19, veiem els resultats dels experiments que hem executat per trobar aquesta cota amb els subconjunts de 20 i 100 classes. Veiem que efectivament el valor de la accuracy creix respecte el paràmetre 𝜌𝑓 fins a cert valor llindar. També veiem que aquest creixement no varia significativament respecte el nombre de classes, és encara menys significatiu que el de 𝜌𝑡. Tot i que el creixement és poc significatiu per el problema aplicat a 20 i 100 classes, creiem que pot ser més significatiu per 1000 classes, degut a que l’accuracy serà més petita de base. Per tant, fixem el valor del paràmetre 𝜌𝑓 a 15, ja que és el llindar. Il·lustració 19. Gràfics d’iteració del paràmetre 𝜌𝑓 al LSVRC’10 amb 20 classes (esquerra) i 100 classes (dreta). La resta de paràmetres estan fixats a 𝑇=100, 𝐷=10 i 𝜌𝑓=100 en el gràfic de 20 classes; i 𝑇=60, 𝐷=16 i 𝜌𝑡= 35 en el gràfic de 100 classes. 20 30 40 50 60 70 80 90 5 10 15 20 25 30 35 accuracy 𝜌𝑓 accuracy a 1 accuracy a 5 10 15 20 25 30 35 40 45 510 15 20 25 30 35 accuracy 𝜌𝑡 accuracy a 1 accuracy a 5 46 7.2.3 Paràmetres 𝐷 i 𝑇 amb 20 i 100 classes Els paràmetres 𝐷 i 𝑇 són els més importants del mètode Random Forest. En especial el paràmetre 𝐷 que augmenta exponencialment en nombre de comparacions que realitza el mètode a l’entrenar. Per a que els Random Forests donin el seu resultat proper al seu òptim, hem de trobar un valor per 𝐷 que realitzi un nombre de comparacions suficientment elevat per discriminar bé les classes del conjunt d’entrenament, però vigilant de no passar-nos, perquè això pot provocar overfitting. També cal tenir en compte que el cost computacional d’entrenament i el cost espacial creixen exponencialment respecte aquest paràmetre, per tant no es pot fixar a valors molt alts. El paràmetre T per altra banda, ajuda al bosc crear divisions no lineals, ho fa combinant les divisions lineals dels diferents arbres del bosc. Una de les hipòtesis que tenim és, donat que la profunditat augmenta el nombre de comparacions aleatòries per arbre i que el nombre d’arbres ha de suavitzar aquestes comparacions, llavors cada valor de 𝐷 necessitarà un valor de 𝑇 mínim per suavitzar correctament la aleatorietat del bosc. També tenim la hipòtesis de que aquest valor creixerà respecte al creixement del paràmetre 𝐷, ja que si incrementem el nombre de comparacions aleatòries per mostra necessitem més mostres per suavitzar el resultat. Experiments amb D i T utilitzat 20 classes Partim de la hipòtesis de que el creixement paràmetre 𝐷 provocarà un creixement de l’accuracy molt fort en els primers valors, però arribarà un punt que començarà a haver-hi overfitting i aquest creixement s’anirà reduint fins a ser gairebé nul o negatiu. Efectivament, els resultats de la Il·lustració 20 esquerra validen aquesta hipòtesis per al nostre subconjunt de 20 classes. Per altra banda, a la Il·lustració 20 dreta, podem veure com efectivament el creixement del nombre d’arbres també millora el resultat, però ho fa d’una forma més dèbil. Il·lustració 20. Gràfics d’iteració dels paràmetres 𝐷 i 𝑇 amb 20 classes al LSVRC’10, dreta i esquerra respectivament. La resta de paràmetres estan fixats a 𝑇=60, 𝜌𝑡=35 i 𝜌𝑓=15 en el gràfic de l’esquerra; i 𝐷=17, 𝜌𝑡=35 i 𝜌𝑓=15 en el gràfic de la dreta. 0 10 20 30 40 50 60 70 80 90 1 3 5 7 9 11 13 15 17 19 accuracy 𝐷 accuracy at 1 accuracy at 5 0 10 20 30 40 50 60 70 80 90 10 20 30 40 50 60 70 80 90 100 accuracy 𝑇 accuracy a 1 accuracy a 5 47 Experiments amb D i T utilitzant 100 classes En els experiments de 100 classes, hem verificat que, les teories sobre el paràmetre 𝐷, validades a l’apartat anterior amb 20 classes, també són certes per 100 classes, com podem veure a la Il·lustració 21. Il·lustració 21. Gràfic d’iteració del paràmetre 𝐷 amb 100 classes al LSVRC’10. La resta de paràmetres estan fixats a 𝑇=60, 𝜌𝑡=35 i 𝜌𝑓=15. En aquest apartat ens centrarem però en la relació entre els paràmetres 𝑇 i 𝐷. En aquest sentit, formulem la hipòtesis que cada valor de 𝐷 necessita un valor de 𝑇 diferent per assolir el seu màxim rendiment, i que aquest valor de 𝑇 creix respecte 𝐷. A la Il·lustració 22, podem veure com l’accuracy a 5 deixa de créixer a partir de 160 arbres amb 𝐷=16, i per altra banda segueix creixent amb 𝐷=17. En el resultat d’accuracy a 1 no és veu tant clarament degut a que, amb 𝐷=17, l’accuracy a 1 creix poc, però observem també un cert creixement que no es dona amb 𝐷=16. Il·lustració 22. Gràfics d’iteració del paràmetre 𝑇 amb 100 classes al LSVRC’10 i diferents valors de 𝐷. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. 0 5 10 15 20 25 30 35 40 45 12345678910 11 12 13 14 15 16 17 18 19 accuracy 𝐷 accuracy a 1 accuracy a 5 38 39 40 41 42 43 44 45 60 100 140 180 220 260 accuracy a 5 𝑇 D=16 D=17 16 16,5 17 17,5 18 18,5 19 19,5 20 60 100 140 180 220 260 accuracy a 1 𝑇 D=16 D=17 48 7.2.4 Paràmetres 𝑇 i 𝐷 1000 classes Un cop realitzats els experiments amb subconjunts més petits, coneixem ja suficientment el comportament del mètode Random Forests al LSVRC’10, i podem realitzar els experiments amb 1000 classes. El primer experiment que hem realitzat ha sigut per veure com evoluciona l’accuracy respecte al paràmetre 𝐷. En aquest experiment hem fixant 𝑇 a 60, un valor petit amb la intenció de reduir el temps de duració de l’experiment i que coneixem perquè hem treballat amb ell en els experiments de 20 i 100 classes. A la Il·lustració 23, podem veure els resultats d’aquest experiment. Veiem que el mètode es satura clarament en el valor 𝐷=16 per la accuracy a 5 i a 𝐷=18 per la accuracy a 1. Tot i així, repassant teories vistes als experiments amb menys classes, sabem que podem intentar corregir aquesta saturació incrementant el valor del paràmetre 𝑇. Il·lustració 23. Gràfic d’iteració del paràmetre 𝐷 amb 1000 classes al LSVRC’10. La resta de paràmetres estan fixats a 𝑇=60, 𝜌𝑡=35 i 𝜌𝑓=15. Per això, hem executat experiments amb valors incrementals del paràmetre 𝑇 i diferents valors incrementals de 𝐷, com podem veure a la Il·lustració 24 i a la Il·lustració 25. Inicialment, hem partit del valor 16 per a 𝐷, ja que és el valor de saturació de l’accuracy a 5 amb 𝑇=60 i preteníem millorar el seu resultat incrementant el nombre d’arbres fins a trobar un punt de saturació. Després de veure que el mètode no es saturava amb profunditat màxima 16 si tenia suficients arbres, hem repetit el mateix procés incremental per a les profunditats 17 i 18, validant que tampoc es saturaven amb un suficient nombre d’arbres. No hem continuat incrementant la profunditat perquè no teníem prou espai al disc de la nostra màquina per guardar boscos de profunditat màxima superior a 18 i amb suficients arbres per millorar el resultat. Finalment també hem repetit el procés per a 𝐷=15, amb l’objectiu de tenir una gama més variada de punts per comparar altres mètodes amb els Random Forests. 0 2 4 6 8 10 12 12345678910 11 12 13 14 15 16 17 18 19 accuracy 𝐷 accuracy a 1 accuracy a 5 49 Il·lustració 24. Gràfic d’iteració del paràmetre 𝑇 amb 1000 classes al LSVRC’10 i diferents valors de 𝐷. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. Il·lustració 25. Gràfic d’iteració del paràmetre 𝑇 amb 1000 classes al LSVRC’10 i diferents valors de 𝐷. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. 9 9,5 10 10,5 11 11,5 12 12,5 60 110 160 210 260 310 360 410 460 accuracy a 5 𝑇 D=15 D=16 D=17 D=18 2,5 3 3,5 4 4,5 5 60 110 160 210 260 310 360 410 460 accuracy a 1 𝑇 D=15 D=16 D=17 D=18 50 7.2.5 Experiments amb Power Normalization Un dels objectius dels nostres experiments, és verificar la hipòtesis que el resultat dels Random Forests no millora en accuracy aplicant la normalització Power Normalization (PN) als Bag of Visual Words (BoVW). Per això hem realitzat experiments amb diferents conjunts de classes. Confiem que aquesta hipòtesi serà certa bastant-nos en que utilitzem funcions de divisió alineades a eix. Aquestes funcions assignen un llindar cada dimensió dels features per separat, no com altres mètodes que avaluen tot el vector de features conjuntament. Així doncs les variacions de magnitud entre dimensions no intervenen en les dedicions que pren aquest mètode i per això creiem que la normalització no ajudarà al millorar els resultats. Experiments amb PN utilitzant 20 classes En els resultats amb 20 classes, veiem efectivament que la Power Normalization (PN) no millora cap de les dues accuracy dels Random Forests. El tipus de creixement respecte la variació del paràmetre D és el mateix i sembla que la versió PN dona resultats lleugerament inferiors degut a la informació que es perd en el procés de normalització. Podem veure els resultats d’aquests experiments comparats amb els resultats sense normalitzar a la Il·lustració 26. Il·lustració 26. Gràfic de comparació de resultats amb i sense normalització amb 20 classes iterant el paràmetre 𝐷. La resta de paràmetres estan fixats a 𝑇=60, 𝜌𝑡=35 i 𝜌𝑓=15. 0 10 20 30 40 50 60 70 80 90 12345678910 11 12 13 14 15 16 17 accuracy 𝐷 accuracy at 1 PN accuracy a 5 PN accuracy at 1 no norm accuracy at 5 no norm 51 Experiments amb PN utilitzant 100 classes En els resultats amb 100 classes, veiem efectivament que la PN tampoc millora cap dels dos tipus d’accuracy en el mètode Random Forests. En aquest cas, veiem clarament que els resultats utilitzant PN són inferiors, ja que creixen de manera lleugerament més dèbil respecte al paràmetre D com podem veure a la Il·lustració 27. Il·lustració 27. Gràfic de comparació de resultats amb i sense normalització amb 100 classes iterant el paràmetre 𝐷. La resta de paràmetres estan fixats a 𝑇=60, 𝜌𝑡=35 i 𝜌𝑓=15. Experiments amb PN utilitzant 1000 classes Hem considerat suficients els experiments de comparativa fets amb 20 i 100 classes per avaluar que la versió sense normalitzar dona millor resultat en general. Tot i així, també hem executat amb 1000 classes un experiment utilitzant PN, fixant els paràmetres a un valor que dona bastant bon resultat per validar que aquesta hipòtesis també es compleix en els nostres resultats finals. Efectivament, a la Taula 12 veiem com els resultats indiquen que els Random Forests també classifiquen de manera més precisa sense normalitzar amb 1000 classes. accuracy a 1 accuracy a 5 No normalitzat 4,34 12,04 Power Norm 3,13 9,75 Taula 12. Comparació de resultats amb i sense normalització utilitzant 1000 classes. La resta de paràmetres estan fixats a 𝑇=260, 𝐷=17, 𝜌𝑡=35 i 𝜌𝑓=15. 0 5 10 15 20 25 30 35 40 45 12345678910 11 12 13 14 15 16 17 accuracy 𝐷 accuracy at 1 PN accuracy a 5 PN accuracy at 1 no norm accuracy at 5 no norm 52 7.2.6 Mesures per mesurar el rendiment dels boscos A la Secció 5.2.3 hem definit diferents mesures per avaluar la qualitat dels arbres del mètode Random Forest. En aquesta subsecció recollirem i analitzarem els resultats d’aquestes mesures. En primer lloc, per posar-nos en context, veiem a la Il·lustració 28 els resultats d’error a 5 per als diferents subconjunts de classes amb els que hem treballat. Les altres gràfiques utilitzaran als mateixos paràmetres i ens serà útil tenir present el seu resultat en error a 5. Il·lustració 28.Gràfic d’error a 5 dels Random Forests amb 20, 100 i 1000 classes amb valors creixents de 𝐷. La resta de paràmetres estan fixats a 𝑇=60, 𝜌𝑡=35 i 𝜌𝑓=15. 53 Mesures d’entropia i guany Com hem vist a la Secció 5.2.3, les funcions mesures 𝐸(𝐹|𝑙) i 𝐺(𝐹|𝑙) avaluen l’evolució de la funció objectiu respecte la profunditat del bosc. Comparant la Il·lustració 28 amb la Il·lustració 29, veiem que l’error a 5 es satura aproximadament en el màxim de la funció 𝐺(𝐹|𝑙). Això ens permet estimar que no ens hem quedat lluny del llindar òptim del paràmetre 𝐷 en els nostres experiments, fet que necessitem validar, degut a que, com hem vist a la Secció 7.2.4, no hem pogut acabar d’explorar l’espai de paràmetres per motius de limitació de memòria. Aproximem que la profunditat màxima òptima es troba entre 17 i 18 per 1000 classes, ja que és el màxim de la funció 𝐺(𝐹|𝑙). Tot i així, no hem pogut explotar correctament el paràmetre 𝑇 per a aquest valors de profunditat màxima per limitacions d’espai. Un altra interpretació que hem fet comparant la Il·lustració 28 amb la Il·lustració 29, és que l’error a 5 comença a disminuir el seu creixement bastant abans del màxim de la funció de guany 𝐺(𝐹|𝑙). Això ens porta a pensar que, avaluant els Random Forests en el LSVRC’10, la funció objectiu que utilitzem no s’acosta prou al l’objectiu real. Veiem que dona molt bon resultat per a 20 classes, en especial als primers nivells dels arbres, però si baixem molt de nivell o augmentem el nombre de classes el rendiment de la funció objectiu empitjora. Això no passa amb els experiments de Caltech-256, que veurem més endavant, ni tampoc amb altres treballs que utilitzen el mateix mètode a més petita escala. Per tant, interpretem que és un problema que apareix al treballar amb classificació d’imatges a gran escala. Il·lustració 29. Gràfics de les funcions 𝐸(𝐹|𝑙) (esquerra) i 𝐺(𝐹|𝑙) (dreta) dels Random Forests amb 20, 100 i 1000 classes. Els paràmetres estan fixats a 𝑇=60, 𝐷=19, 𝜌𝑡=35 i 𝜌𝑓=15. 60 7.3.4 Random Forests Caltech-256 paràmetre 𝐷 En aquesta secció volem tornar a comprovar les mateixes teories que hem validat a la Secció 7.2 sobre els paràmetres 𝐷 i 𝑇 dels Random Forests. En aquella secció ho hem fet per al conjunt de dades LSVRC’10 i ara volem veure que també es compleixen per al conjunt de dades Caltech256. Per això hem executat experiments amb tots els nivells de profunditat màxima que ens canvien al disc i per a boscos amb diferent nombre d’arbres. Cal tenir en compte que, a l’incrementar el nombre d’arbres, augmenta el consum d’espai del bosc al disc, i conseqüentment podem arribar a menys nivells de profunditat màxima. En el nostre cas, hem fixat una cota d’espai al disc màxima de 300 GB, i per això, a les gràfiques d’accuracy cada nombre d’arbres arriba a una profunditat màxima diferent. Caltech-256-15 amb 20 classes En els resultats de la Il·lustració 33, veiem que l’accuracy creix clarament fins a 𝐷=14, on arriba al seu màxim valor de 17,1%. Cal tenir en compte que el conjunt d’entrenament d’aquest experiment només té 300 imatges, això explica que el gràfic tingui una forma tant irregular i que a més arribem a trobar el màxim absolut d’accuracy. Per justificar que realment hem trobat el màxim absolut d’accuracy, a la Il·lustració 39, podem veure que al nivell 14 el percentatge de nodes nuls gairebé arriba al 100%. També podem veure, a la Il·lustració 40, que el percentatge de mostres al nivell 14 és només del 3,6%. Una altra observació és que al nivell 14 l’entropia del mitjana del bosc val 0,01 i per tant ja no pot millorar gaire més, tenint en compte que el seu valor màxim era 4. Tot apunta a que el mètode es troba en un estat en el que ja no té més recursos per seguir millorant l’accuracy incrementant el paràmetre 𝐷. Il·lustració 33. Gràfic d’iteració del paràmetre 𝐷 amb 20 classes al Caltech-256-15 i diferents valors de 𝑇. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. 0 2 4 6 8 10 12 14 16 18 12345678910 11 12 13 14 15 16 17 18 19 accuracy a 1 𝐷 T=60 T=150 T= 300 61 Caltech-256-15 256 amb classes En els resultats de la Il·lustració 34, veiem que l’accuracy creix clarament fins a 𝐷=17 amb 300 arbres, on obtenim el nostre màxim de 2,56%. Creiem però que si haguéssim pogut executar el mètode Random Forests amb 300 arbres i profunditat màxima superior a 17 hauríem millorat aquest resultat, ja que en els resultats amb 150 i 60 arbres l’accuracy encara creix. A de més, als gràfics de la Secció 7.3.5, veurem que les mesures de rendiment del bosc encara els falta una mica per assolir els valors crítics que tenien amb 20 classes a la seva profunditat màxima optima. Il·lustració 34. Gràfic d’iteració del paràmetre 𝐷 amb 256 classes al Caltech-256-15 i diferents valors de 𝑇. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. 0 0,5 1 1,5 2 2,5 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 accuracy a 1 𝐷 T=60 T=150 T=300 62 Caltech-256-40 amb 20 classes En els resultats de la Il·lustració 35, veiem que el màxim valor d’accuracy aconseguits en els experiments és 21,25%, amb 𝐷=17 i 𝑇=300. Per altra banda, veient la forma que tenen al gràfic els resultants amb 150 i 60 arbres en el tram de profunditat que va entre 16 i 19, sembla que si haguéssim pogut treballar amb boscos de profunditats 18 i 19 utilitzant 300 arbres hauríem pogut millorar una mica el resultat. Tot i així, analitzant els resultats, i analitzant també les mesures de la Secció 7.3.5 en comparació a les obtingudes amb 15 mostres d’entrenament per classe i 20 classes, intuïm que la d’acurracy seria molt baixa, encara que no ho hem pogut validar per limitació de recursos. Il·lustració 35. Gràfic d’iteració del paràmetre 𝐷 amb 20 classes al Caltech-256-40 i diferents valors de 𝑇. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. 0 5 10 15 20 25 12345678910 11 12 13 14 15 16 17 18 19 accuracy a 1 D T=60 T=150 T=300 63 Caltech-256-40 amb 256 classes En els resultats de la Il·lustració 36, veiem que el màxim valor d’accuracy aconseguits en els experiments és 3,02%, amb 𝐷=17 i 𝑇=300. Seguint la mateixa línia de raonament que en els gràfics anteriors i estudiant les mesures de la Secció 7.3.5, veiem que, en aquest cas encara falta una mica més de profunditat màxima per a que aquestes mesures arribin a saturar-se comparant-les amb resta d’experiments que hem dut a terme amb Caltech-256. Tot i així, també creiem que la millora d’accuracy seria baixa incrementant el valor del paràmetre 𝐷. Il·lustració 36. Gràfic d’iteració del paràmetre 𝐷 amb 256 classes al Caltech-256-40 i diferents valors de 𝑇. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. 0 0,5 1 1,5 2 2,5 3 3,5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 accuracy a 1 𝐷 T=60 T=150 T=300 64 7.3.5 Random Forests Caltech-256 mesures de rendiment dels boscos En aquesta secció, veurem els resultats d’aplicar les mesures de rendiment dels Random Forests vistes a la Secció 5.2.3, als boscos que hem utilitzat per experimentar amb el conjunt de dades Caltech-256. Entropia per nivells A la Il·lustració 37 veiem els gràfics de l’entropia a cada nivell del bosc. Podem observar que tenen la mateixa forma per les dues mides diferents de conjunt d’entrenament amb les que hem treballat. La diferència es que l’entropia triga més a començar a caure amb força amb el conjunt d’entrenament de 40 classes, fet raonable, ja que la màxima profunditat òptima dels Random Forests creix respecte la mida del conjunt d’entrenament. Il·lustració 37. Gràfics de la funció d’entropia per nivells del bosc, 𝐸(𝐹|𝑙), amb els conjunts de dades Caltech-256-15 (esquerra) i Caltech-256-40 (dreta). Els paràmetres estan fixats a 𝑇=60, 𝐷=19, 𝜌𝑡=35 i 𝜌𝑓=15. 0 1 2 3 4 5 6 7 8 9 0246810 12 14 16 18 entropia del nivell del bosc nivell dels arbres 20 classes 256 classes 0 1 2 3 4 5 6 7 8 9 0246810 12 14 16 18 entropia del nivell del bosc nivell dels arbres 20 classes 256 classes 65 Guany per nivells A la Il·lustració 38 veiem les gràfiques de guany per nivell del bosc, podem observar que segueixen una forma similar a una gaussiana, com ja havien comentat abans. Concretament, en el conjunt de dades Caltech-256, que conté menys nombre d’imatges per classe que el LSVRC’10, veiem que s’aproxima més a una funció 2. Sembla que això es degut a que treballem amb menys dades, tot i així no ho hem pogut validar, perquè al LSVRC’10 no hem pogut construir arbres amb suficient profunditat com per veure la forma de la cua de la funció. Una altra característica típica d’aquesta funció són els “bonys” als primers nivells, podem trobar-los al nivell 1 per 256 classes, i entre els nivells 2 i 5 per 20 classes. També veiem que el màxim de la funció es desplaça a la dreta al incrementar el nombre de classes com passava amb el LSVRC’10. Finalment, notem que el màxim de la funció baixa i es mou a la dreta quan augmentem el nombre d’imatges d’entrenament per classe, això es degut a que el bosc necessita més nivells de profunditat per comparar totes les imatges correctament, tenint en compte que incrementem la mida del conjunt d’entrenament. Il·lustració 38. Gràfics de la funció de guany per nivells del bosc, 𝐺(𝐹|𝑙), amb els conjunts de dades Caltech-256-15 (esquerra) i Caltech-256-40 (dreta). Els paràmetres estan fixats a 𝑇=60, 𝐷=19, 𝜌𝑡=35 i 𝜌𝑓=15. 0 0,2 0,4 0,6 0,8 1 1,2 0246810 12 14 16 18 guany per nivell del bosc nivell dels arbres 20 classes 256 classes 0 0,2 0,4 0,6 0,8 1 1,2 0 2 4 6 8 10 12 14 16 18 guany per nivell del bosc nivell dels arbres 20 classes 256 classes 66 Percentatge de nodes nuls per nivell A la Il·lustració 39 veient les gràfiques de nodes nuls per nivell del bosc, observem que, en el conjunt de dades Caltech-256, no podem realitzar la mateixa aproximació que hem utilitzat en el LSVRC’10 per calcular el cost i l’espai de memòria, ja que aquests arbres s’allunyen molt del concepte d’arbre balancejat. Veiem també que en tots els casos gairebé hem arribat a saturar tots els nodes, encara que l’únic cas en que realment estan tots saturats és el punt de 20 classes, 15 mostres d’entrenament per classe i profunditat 19. Validem també que amb més classes necessitem arbres més profunds i que amb més imatges per classe també necessitem arbres més profunds. El factor que augmenta realment la profunditat de saturació dels arbres és el nombre d’imatges del conjunt d’entrenament i la seva dificultat, ja que els Random Forests comparen imatges sense tenir en compte a quina classe concreta pertanyen. Il·lustració 39. Gràfics de la funció de percentatge de nodes nuls per nivell del bosc (NNP) amb els conjunts de dades Caltech-256-15 (esquerra) i Caltech-256-40 (dreta). Els paràmetres estan fixats a 𝑇=60, 𝐷=19, 𝜌𝑡=35 i 𝜌𝑓=15. 0 10 20 30 40 50 60 70 80 90 100 0 2 4 6 8 10 12 14 16 18 percentatge de nodes nuls nivell dels arbres 20 classes 256 classes 0 10 20 30 40 50 60 70 80 90 100 0246810 12 14 16 18 percentatge de nodes nuls nivell dels arbres 20 classes 256 classes 67 Percentatge de mostres per nivell A la Il·lustració 40 veiem els gràfics de mostres per nivell del bosc, en els quals arribem a saturar gairebé totes les mostres en tots els casos. Tot i així, l’únic cas en que realment estan totes saturades és el punt de 20 classes, 15 mostres d’entrenament per classe i profunditat 19. Notem que, el llindar en que les mostres comencen a saturar-se, creix respecte el nombre de classes i també respecte el nombre d’imatges per classe. Per similitud amb l’evolució del nombre de nodes nuls, creiem que el mètode Random Forests, necessita més nivells de profunditat per començar a saturar nodes quan el nombre de mostres d’entrenament de tot el conjunt de dades és més gran. Il·lustració 40. Gràfics de la funció de percentatge de mostres per nivell del bosc (NSP) amb els conjunts de dades Caltech-256-15 (esquerra) i Caltech-256-40 (dreta). Els paràmetres estan fixats a 𝑇=60, 𝐷=19, 𝜌𝑡=35 i 𝜌𝑓=15. 0 10 20 30 40 50 60 70 80 90 100 0 2 4 6 8 10 12 14 16 18 percentatge de nodes nuls nivell dels arbres 20 classes 256 classes 0 10 20 30 40 50 60 70 80 90 100 0 2 4 6 8 10 12 14 16 18 percentatge de nodes nuls nivell dels arbres 20 classes 256 classes 68 7.3.6 Random Forests Caltech-256 ajustament de paràmetre 𝑇 En aquesta secció volem obtenir un valor de saturació més acurat del paràmetre 𝑇. Per fer-ho, fixarem el paràmetre 𝐷 al millor valor obtingut a la Secció 7.3.4 i explorarem els valors del paràmetre 𝑇 propers a l’òptim local obtingut també en aquella secció. Caltech-256-15 A la Il·lustració 41, podem veure els resultats dels experiments que hem executat per trobar el valor de saturació de T a Caltech-256-15. Adoptem com a valors definitiu de T, 240 per 20 classes i 300 per 256 classes. L’accuracy corresponent a aquests paràmetres és 17,1% amb 20 classes i 2,89% amb 256 classes. Observant el creixement del gràfic, concloem també que no podem assegurar haver trobat el valor de saturació del paràmetre T per a 256 classes per limitació d’espai. Il·lustració 41. Gràfics d’iteració del paràmetre 𝑇 amb 20 (esquerra) i 256 (dreta) classes al conjunt de dades Caltech256-15. El paràmetre 𝐷 val 14 per a 20 classes i 17 per a 256 classes La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. 0 2 4 6 8 10 12 14 16 18 60 100 140 180 220 260 300 accuracy a 1 𝑇 0 0,5 1 1,5 2 2,5 3 160 180 200 220 240 260 280 300 accuracy a 1 𝐷 69 Caltech-256-40 A la Il·lustració 42 podem veure els resultats dels experiments que hem executat per trobar el valor de saturació de T a Caltech-256-40. Adoptem com a valor definitiu T=400 per 20 i T=300 per 256 classes. L’accuracy corresponent a aquests paràmetres és 17,1% amb 20 classes i 2,89% amb 256 classes. Observant el creixement de la gràfica, concloem també que no podem assegurar haver trobat el valor de saturació del paràmetre T per a 256 classes, degut a la limitació d’espai. Per a 20 classes hem pogut experimentar amb més arbres perquè el nivell de profunditat màxima òptim és inferior. Il·lustració 42. Gràfics d’iteració del paràmetre 𝑇 amb 20 (esquerra) i 256 (dreta) classes al conjunt de dades Caltech256-40. El paràmetre 𝐷 està fixat a 16 per 20 classes i 17 per 256 classes. La resta de paràmetres estan fixat 𝜌𝑡=35 i 𝜌𝑓=15. 0 5 10 15 20 25 160 200 240 280 320 360 400 accuracy a 1 𝑇 0 0,5 1 1,5 2 2,5 3 3,5 160 180 200 220 240 260 280 300 accuracy a 1 𝑇 76 10 Glossari AP: Average Precision. Big Data: Referent a conjunts de dades molt grans. BoVW: Bag of Visual Words. Caltech-256-15: Subconjunt del conjunt de dades Caltech-256 utilitzant les 15 primeres imatges per entrenar i la resta d’imatges per avaluar. Els descriptors de les imatges són BoVW. Caltech-256-40: Subconjunt del conjunt de dades Caltech-256 utilitzant les 40 imatges per entrenar i les 40 següents per avaluar. Els descriptors de les imatges són BoVW. CCIA: Congrés internacional de l’associació Catalana d’Intel·ligència Artificial. Classe: Categoria d’imatges. CNN: Convolutional Neural Networks. Conjunt d’entrenament: Traducció del terme anglès “training set”. Conjunt de dades: Traducció del terme anglès “data set”. Conjunt de prova/avaluació: Traducció del terme anglès “test set”. ECBND: Ensembles of Class Balanced Nested Dichotomies. Etapa d’avaluació: Referent a la etapa en que un classificador avalua la categoria de les imatges. En anglès “testing phase”. Factor: Una variable que defineix l’estat en que ens trobem dins d’un espai de cerca experimental. FBA: Variant Full Brach Aggregation del ECBND. Features: Referent als descriptors de les imatges sempre en forma vectorial. Gran escala: Referent a conjunts de dades molt grans. Iterar un paràmetre: Realitzar diversos experiments amb valors incrementals d’un paràmetre concret i fixant la resta de paràmetres. k-factorial: Espai de cerca experimental amb k factors. LSVRC’10: Conjunt de dades del ImageNet Large Scale Visual Recognition Challenge 2010. LSVRC’10: Conjunt de dades del Large Scale Visual Recognition Challenge 2010 d’ImageNet. MAP: Mean Average Precision. NNP: Percentatge de nodes nuls a un nivell d’un arbre/bosc. NSP: Percentatge de mostres saturades a un nivell d’un arbre/bosc. Overfitting: Efecte que es produeix quan un classificador s’adapta massa bé al conjunt d’entrenament i perd capacitat de generació cap a les imatges que encara no ha vist. OvR-SVM: One-versus-Rest Support Vector Machines. 77 PN: Power Normalization. PRC: Precision-Recall Curve. SB: Variant Simple Branching del ECBND. SIFT: Scale Invariant Feature Transform. SVM Kernel RBF 2: Suport Vector Machines amb Kernel del Radial Basis Function 2. 78 11 Taula d’il·lustracions Il·lustració 1. Expilació gràfica del funcionament del Kinect extreta d’una presentació del llibre Shotton et al. [3]. ............................................................................................................................................... 9 Il·lustració 2. Mostra gràfica dels resultats del mètode de detecció d’objectes descrit l’article Gall et al. [7], la imatge s’ha extret l’aquest article. ............................................................................................ 9 Il·lustració 3. Explicació gràfica del funcionament del mètode descrit a l’article Criminisi et al. [8], la imatge s’ha extret d’aquest article. ................................................................................................... 10 Il·lustració 4. Representació gràfica de les diferents fases del mètode descrit a l’article Shotton [9], la imatge s’ha extret d’aquest article. ................................................................................................... 10 Il·lustració 5. Representació gràfica de l’avaluació d’una mostra de prova per part del mètode Random Forests. Les fletxes pintades de color vermell (i també més gruixudes) indiquen el camí que ha seguit la mostra avaluada en els diferents arbres. ............................................................................ 15 Il·lustració 6. Representació gràfica del càlcul dels BoVW. ........................................................................ 19 Il·lustració 7. Explicació gràfica dels mètodes OvR-SVM (esquerra) i ECBND (dreta) amb un exemple de 8 classes. Les caixes verdes i vermelles representen els classificadors SVM (les verdes contenen les mostres classificades com a positives i les vermelles les mostres classificades com a negatives). La imatge s’ha extret del treball de Ramisa [1]. ..................................................................................... 20 Il·lustració 8. Explicació gràfica del càlcul del percentatge de nodes nuls (NNP) en el nivell 3 d’un arbre mitjançant un exemple de profunditat 3. .......................................................................................... 25 Il·lustració 9. Captura de pantalla d’un fitxer de configuració de la interfície d’experimentació .............. 31 Il·lustració 10. Diagrama de disseny de l’estructura de fitxers de resultats i estadístics dels Random Forests ............................................................................................................................................... 35 Il·lustració 11. Pàgines d’indexació d’experiments .................................................................................... 36 Il·lustració 12. Pàgina de mostra d’estadístics iterant un paràmetre als Random Forests ........................ 37 Il·lustració 13. Pàgina de mostra d’estadístics d’una iteració .................................................................... 38 Il·lustració 14. Pàgina d’estadístics per classe ............................................................................................ 39 Il·lustració 15. Pàgina de resultats de les imatges d’una classe ................................................................. 40 Il·lustració 16. Pàgina de resultats d’imatges ordenades per la score obtinguda en classe concreta........ 41 Il·lustració 17. Pàgina de resultats d’una imatge........................................................................................ 41 Il·lustració 18. Gràfics d’iteració del paràmetre 𝜌𝑓 al LSVRC’10 amb 20 classes (esquerra) i 100 classes (dreta). La resta de paràmetres estan fixats a 𝑇=100, 𝐷=10 i 𝜌𝑡=30 en el gràfic de 20 classes; i 𝑇=60, 𝐷=16 i 𝜌𝑡=15 en la gràfic de 100 classes. ................................................................... 44 Il·lustració 19. Gràfics d’iteració del paràmetre 𝜌𝑓 al LSVRC’10 amb 20 classes (esquerra) i 100 classes (dreta). La resta de paràmetres estan fixats a 𝑇=100, 𝐷=10 i 𝜌𝑓=100 en el gràfic de 20 classes; i 𝑇=60, 𝐷=16 i 𝜌𝑡=35 en el gràfic de 100 classes. ...................................................... 45 Il·lustració 20. Gràfics d’iteració dels paràmetres 𝐷 i 𝑇 amb 20 classes al LSVRC’10, dreta i esquerra respectivament. La resta de paràmetres estan fixats a 𝑇=60, 𝜌𝑡=35 i 𝜌𝑓=15 en el gràfic de l’esquerra; i 𝐷=17, 𝜌𝑡=35 i 𝜌𝑓=15 en el gràfic de la dreta. .................................................. 46 Il·lustració 21. Gràfic d’iteració del paràmetre 𝐷 amb 100 classes al LSVRC’10. La resta de paràmetres estan fixats a 𝑇=60, 𝜌𝑡=35 i 𝜌𝑓=15. ....................................................................................... 47 Il·lustració 22. Gràfics d’iteració del paràmetre 𝑇 amb 100 classes al LSVRC’10 i diferents valors de 𝐷. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. ................................................................... 47 Il·lustració 23. Gràfic d’iteració del paràmetre 𝐷 amb 1000 classes al LSVRC’10. La resta de paràmetres estan fixats a 𝑇=60, 𝜌𝑡=35 i 𝜌𝑓=15. ....................................................................................... 48 Il·lustració 24. Gràfic d’iteració del paràmetre 𝑇 amb 1000 classes al LSVRC’10 i diferents valors de 𝐷. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. ................................................................... 49 Il·lustració 25. Gràfic d’iteració del paràmetre 𝑇 amb 1000 classes al LSVRC’10 i diferents valors de 𝐷. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. ................................................................... 49 Il·lustració 26. Gràfic de comparació de resultats amb i sense normalització amb 20 classes iterant el paràmetre 𝐷. La resta de paràmetres estan fixats a 𝑇=60, 𝜌𝑡=35 i 𝜌𝑓=15. .......................... 50 79 Il·lustració 27. Gràfic de comparació de resultats amb i sense normalització amb 100 classes iterant el paràmetre 𝐷. La resta de paràmetres estan fixats a 𝑇=60, 𝜌𝑡=35 i 𝜌𝑓=15. .......................... 51 Il·lustració 28.Gràfic d’error a 5 dels Random Forests amb 20, 100 i 1000 classes amb valors creixents de 𝐷. La resta de paràmetres estan fixats a 𝑇=60, 𝜌𝑡=35 i 𝜌𝑓=15. ............................................ 52 Il·lustració 29. Gràfics de les funcions 𝐸𝐹𝑙 (esquerra) i 𝐺(𝐹|𝑙) (dreta) dels Random Forests amb 20, 100 i 1000 classes. Els paràmetres estan fixats a 𝑇=60, 𝐷=19, 𝜌𝑡=35 i 𝜌𝑓=15. .......................... 53 Il·lustració 30. Gràfics de NNP (esquerra) i NSP (dreta) dels Random Forests amb 20, 100 i 1000 classes. Els paràmetres estan fixats a 𝑇=60, 𝐷=19, 𝜌𝑡=35 i 𝜌𝑓=15. ................................................ 54 Il·lustració 31. Gràfics de error a 5 vs costs de la Taula 13. A l’esquerra trobem el gràfic de cost computacional d’avaluació i a la dreta el gràfic de cost espacial del bosc. ....................................... 55 Il·lustració 32. Error a 5 dels mètodes ECBND, OvR-SVM i Random Forests al conjunt de dades LSVRC’10. Els marcadors de l’ECBND corresponen a conjunts d’arbres de mida 2, 3, 4, 10, 25, 50, 100, 200 i 300, respectivament. L’experiment del ECBND Single Branching està ampliat a 400, 500, 600 i 700 arbres per determiner millor el seu punt de saturació. Els marcadors del mètode Random Forests corresponen a les columnes “Cost comp. aval.” i “Cost espacial (bosc)” de la Taula 13. .................. 56 Il·lustració 33. Gràfic d’iteració del paràmetre 𝐷 amb 20 classes al Caltech-256-15 i diferents valors de 𝑇. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. .............................................................. 60 Il·lustració 34. Gràfic d’iteració del paràmetre 𝐷 amb 256 classes al Caltech-256-15 i diferents valors de 𝑇. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. ........................................................... 61 Il·lustració 35. Gràfic d’iteració del paràmetre 𝐷 amb 20 classes al Caltech-256-40 i diferents valors de 𝑇. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. .............................................................. 62 Il·lustració 36. Gràfic d’iteració del paràmetre 𝐷 amb 256 classes al Caltech-256-40 i diferents valors de 𝑇. La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. .......................................................... 63 Il·lustració 37. Gràfics de la funció d’entropia per nivells del bosc, 𝐸𝐹𝑙, amb els conjunts de dades Caltech-256-15 (esquerra) i Caltech-256-40 (dreta). Els paràmetres estan fixats a 𝑇=60, 𝐷=19, 𝜌𝑡=35 i 𝜌𝑓=15. ........................................................................................................................... 64 Il·lustració 38. Gràfics de la funció de guany per nivells del bosc, 𝐺𝐹𝑙, amb els conjunts de dades Caltech256-15 (esquerra) i Caltech-256-40 (dreta). Els paràmetres estan fixats a 𝑇=60, 𝐷=19, 𝜌𝑡=35 i 𝜌𝑓=15. .......................................................................................................................................... 65 Il·lustració 39. Gràfics de la funció de percentatge de nodes nuls per nivell del bosc (NNP) amb els conjunts de dades Caltech-256-15 (esquerra) i Caltech-256-40 (dreta). Els paràmetres estan fixats a 𝑇=60, 𝐷=19, 𝜌𝑡=35 i 𝜌𝑓=15. ............................................................................................... 66 Il·lustració 40. Gràfics de la funció de percentatge de mostres per nivell del bosc (NSP) amb els conjunts de dades Caltech-256-15 (esquerra) i Caltech-256-40 (dreta). Els paràmetres estan fixats a 𝑇=60, 𝐷=19, 𝜌𝑡=35 i 𝜌𝑓=15. ............................................................................................................. 67 Il·lustració 41. Gràfics d’iteració del paràmetre 𝑇 amb 20 (esquerra) i 256 (dreta) classes al conjunt de dades Caltech-256-15. El paràmetre 𝐷 val 14 per a 20 classes i 17 per a 256 classes La resta de paràmetres estan fixats a 𝜌𝑡=35 i 𝜌𝑓=15. ................................................................................. 68 Il·lustració 42. Gràfics d’iteració del paràmetre 𝑇 amb 20 (esquerra) i 256 (dreta) classes al conjunt de dades Caltech-256-40. El paràmetre 𝐷 està fixat a 16 per 20 classes i 17 per 256 classes. La resta de paràmetres estan fixat 𝜌𝑡=35 i 𝜌𝑓=15. ...................................................................................... 69 Il·lustració 43. Gràfics accuracy dels mètodes Random Forests i OvR-SVM al conjunt de dades Caltech256, amb 20 classes. El color de contorn dels marcadors defineix el subconjunt de dades, gris per Caltech-256-15 i negre per Caltrech-256-40. .................................................................................... 72 Il·lustració 44. Gràfics accuracy dels mètodes Random Forests i OvR-SVM al conjunt de dades Caltech256, amb 256 classes. El color de contorn dels marcadors defineix el subconjunt de dades, gris per Caltech-256-15 i negre per Caltrech-256-40. .................................................................................... 73 80 12 Taula de taules Taula 1. Planificació de tasques del projecte ............................................................................................... 5 Taula 2. Avaluació econòmica hardware ...................................................................................................... 6 Taula 3. Avaluació econòmica del software ................................................................................................. 7 Taula 4. Avaluació econòmica dels recursos humans .................................................................................. 7 Taula 5. Avaluació econòmica global............................................................................................................ 7 Taula 6. Taula de característiques dels conjunts de dades. * Hem reduït les imatges de manera que ni la alçada ni la amplada superin 1024 píxels .......................................................................................... 22 Taula 7. Paràmetres d’experiment ............................................................................................................. 32 Taula 8. Paràmetres d’experiment del mètode Random Forests ............................................................... 32 Taula 9. Paràmetres d’experiment d’elecció del conjunt de dades ........................................................... 32 Taula 10. Identificadors de les classes del subconjunt de 20 classes del LSVRC’10 ................................... 43 Taula 11. Identificadors de les classes del subconjunt de 100 classes del LSVRC’10 ................................. 43 Taula 12. Comparació de resultats amb i sense normalització utilitzant 1000 classes. La resta de paràmetres estan fixats a 𝑇=260, 𝐷=17, 𝜌𝑡=35 i 𝜌𝑓=15. ................................................... 51 Taula 13. Cost computacional, cost espacial i error a 5 de boscos de diferents mides amb tot el conjunt de dades LSVRC’10. Els paràmetres 𝜌𝑡 i 𝜌𝑓 estan fixats a 35 i 15 respectivament. El cost espacial s’avalua amb nodes, cada node conté 1000 floats. * Cost computacional d’avaluació. .................... 55 Taula 14. Identificadors de les classes del subconjunt de 20 classes de Caltech-256 ................................ 57 Taula 15. Resultats d’accuracy a 1 dels experiments amb OvR-SVM Kernel RBF  2 a Caltech-256 ........... 58 Taula 16. Resultats del mètode ECBND a Caltech-256. L’accuracy és mitja d’accuracy a 1 obtinguda amb diferents arbres. ................................................................................................................................ 59 Taula 17. Taula de resultats dels OvR-SVM al conjunt de dades Caltech-256. El cost espacial s’avalua amb floats. * Cost computacional d’avaluació en comparacions. ............................................................. 70 Taula 18. Taula de resultats del ECBND SB al conjunt de dades Caltech-256. El cost espacial s’avalua amb floats. * Cost computacional d’avaluació en comparacions............................................................... 70 Taula 19. Taula de resultats del ECBND FBA al conjunt de dades Caltech-256. El cost espacial s’avalua amb floats. * Cost computacional d’avaluació en comparacions. ..................................................... 70 Taula 20. Taula de resultats dels Random Forests al conjunt de dades Caltech-256. El cost espacial s’avalua amb floats. * Cost computacional d’avaluació en comparacions. ....................................... 71 81 13 Taula d’equacions Equació 1. Càlcul del preu d’amortització d’un producte per hora .............................................................. 6 Equació 2. Càlcul de la càrrega d’un producte en el preu del projecte ........................................................ 6 Equació 3. Unificació de les respostes dels arbres dels Random Forest .................................................... 16 Equació 4. Funció objectiu dels Random Forests ....................................................................................... 17 Equació 5. Funció d’entropia d’un arbre en un nivell ................................................................................. 24 Equació 6. Funció d’entropia del bosc en un nivell .................................................................................... 24 Equació 7. Funció de guany del bosc en un nivell ...................................................................................... 24 Equació 8. Cost computacional mitjà d’avaluar un arbre ........................................................................... 71 Equació 9. Cost computacional mitjà d’avaluar un bosc ............................................................................ 71 82 14 Referències [1] A. Ramisa and C. Torras, “Large-scale image classification using ensembles of nested dichotomies,” in Catalan Conference on Artificial Intelligence (CCIA), 2013, pp. 87–90. [2] L. Breiman, “Random Forest,” Mach. Learn., vol. 45, no. 1, pp. 5–32, 2001. [3] A. Criminisi and J. Shotton, Decision Forests for Computer Vision and Medical Image Analysis. Springer, 2013, p. 368. [4] M. D. Zeiler and R. Fergus, “Visualizing and Understanding Convolutional Networks.,” CoRR, vol. abs/1311.2, 2013. [5] M. Ristin, M. Guillaumin, J. Gall, and L. Van Gool, “Incremental Learning of NCM Forests for Large-Scale Image Classification,” in Conference on Computer Vision and Pattern Recognition (CVPR), 2014, p. to appear. [6] J. Shotton, A. Fitzgibbon, M. Cook, T. Sharp, M. Finocchio, R. Moore, A. Kipman, and A. Blake, “Real-time human pose recognition in parts from single depth images,” in Conference on Computer Vision and Pattern Recognition (CVPR), 2011, pp. 1297–1304. [7] J. Gall and V. Lempitsky, “Class-specific Hough forests for object detection,” in Conference on Computer Vision and Pattern Recognition (CVPR), 2009, pp. 1022–1029. [8] A. Criminisi, D. Robertson, E. Konukoglu, J. Shotton, S. Pathak, S. White, and K. Siddiqui, “Regression forests for efficient anatomy detection and localization in computed tomography scans.,” Med. Image Anal., vol. 17, no. 8, pp. 1293–303, Dec. 2013. [9] J. Shotton, M. Johnson, and R. Cipolla, “Semantic texton forests for image categorization and segmentation,” in Conference on Computer Vision and Pattern Recognition (CVPR), 2008, pp. 1–8. [10] A. Bosch, A. Zisserman, and X. Munoz, “Image Classification using Random Forests and Ferns,” in Conference on Computer Vision and Pattern Recognition (CVPR), 2007, pp. 1– 8. [11] OpenMP Architecture Review Board, “{OpenMP} Application Program Interface Version 3.0.” 2008. [12] J. D. Hunter, “Matplotlib: A 2D graphics environment,” Comput. Sci. Eng., vol. 9, no. 3, pp. 90–95, 2007. [13] S. Sonnenburg, G. Ratsch, S. Henschel, C. Widmer, J. Behr, A. Zien, F. de Bona, A. Binder, C. Gehl, and V. Franc, “Shogun Machine Learning Toolbox.” [Online]. Available: http://www.shogun-toolbox.org/. [14] A. Vedaldi and B. Fulkerson, “Vlfeat: an open and portable library of computer vision algorithms,” in Proceedings of the international conference on Multimedia - MM ’10, 2010, p. 1469. 83 [15] R. Socher, “ImageNet: A large-scale hierarchical image database,” in Conference on Computer Vision and Pattern Recognition (CVPR), 2009, pp. 248–255. [16] G. Griffin, A. Holub, and P. Perona, “Caltech-256 Object Category Dataset, Technical report,” 2007. [17] D. G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints,” Int. J. Comput. Vis., vol. 60, no. 2, pp. 91–110, Nov. 2004. [18] F. Perronnin, Z. Akata, Z. Harchaoui, and C. Schmid, “Towards good practice in large-scale learning for image classification,” in Conference on Computer Vision and Pattern Recognition (CVPR), 2012, pp. 3482–3489. [19] T. Huang, “Linear spatial pyramid matching using sparse coding for image classification,” in Conference on Computer Vision and Pattern Recognition (CVPR), 2009, pp. 1794–1801. [20] J. Shotton, T. Sharp, P. Kohli, S. Nowozin, J. Winn, and A. Criminisi, “Decision Jungles: Compact and Rich Models for Classification,” in Advances in Neural Information Processing Systems 26, C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, Eds. Curran Associates, Inc., 2013, pp. 234–242.