Relações entre Ranking, Análise ROC e Calibração em Aprendizado de Máquina Edson Takashi Matsubara SERVIÇO DE PÓS-GRADUAÇÃO DO ICMC-USP Data de Depósito: Assinatura: Relações entre Ranking, Análise ROC e Calibração em Aprendizado de Máquina 1 Edson Takashi Matsubara Orientadora: Profa Dra Maria Carolina Monard Tese apresentada ao Instituto de Ciências Ma- temáticas e de Computação - ICMC-USP como parte dos requisitos necessários à obtenção para do título em Doutor em Ciências de Computação e Matemática Computacional. USP - São Carlos julho/2008 1Trabalho Realizado com Auxílio da FAPESP Proc. No: 2005/03792-9 Aos meus pais, Ryuiti e Ritie, Aos meus irmãos, Koiti e Sayuri, À Maria Carolina Monard. v vi Agradecimentos Gostaria de agradecer a Deus por estar sempre ao meu lado, sempre me indicando caminhos que me levam a sua bondade, por nunca ter desistido de mim, por mostrar que nenhuma passagem pode ser sem esforço, por me dar coragem, por mostrar os valores que realmente valem, por colocar pessoas tão boas e especiais em meu caminho, por cuidar de cada simples detalhe em minha vida. Como diria o poeta, mesmo que tivesse em minhas mãos todo o perfume das rosas, toda a beleza do céu, toda a pureza dos anjos, toda a inocência das crianças, toda a grandeza do mar, toda a força das ondas, mesmo que eu tivesse todas as coisas belas da vida e todos os belos lugares do mundo nada teria sentido se eu não tivesse o presente mais valioso, mais nobre e mais sagrado que o Senhor pode me dar... minha família. Agradeço meu pai Ryuiti, por me ensinar muito, mas muito mesmo, sobre todas as coisas da vida. Agradeço minha mãe Ritie por seu imenso carinho e amor. Agradeço aos meus irmãos Koiti, Sayuri, e agora a mais nova irmã Miwa, por serem os melhores irmãos que alguém pode ter. Mestres nos conduzem, não somente ao conhecimento, mas também ao saber. Agradeço à professora Carolina, por tudo que tem me ensinado, pelos conselhos e pelas conversas, sem você eu não teria chegado onde cheguei. Te- nho muito carinho por você. Gostaria de agradecer também ao professor Peter Flach e sua esposa Lisa por terem me ensinado muito no ano em que passei pela Universidade de Bristol. Por terem me acolhido em sua casa e pelas ho- ras de utilizávamos os ladrilhos da cozinha me explicando sobre curvas ROC. Gostaria de agradecer aos professores Huei e Paulo, por serem exemplos de dedicação e ensino na formação de pessoas. Gostaria de agradecer também à professora Solange e ao professor André pelo apoio ao meu trabalho. Além dessas pessoas que considero grandes mestres, existem as pessoas que dão um toque muito especial a minha vida. Considero a minha vida como um rio que se forma pela mistura de pequenos encontros e quando unidas vii trazem força e sentido à vida. Assim considero as amizades que faço nos caminhos da vida. Muitas vezes essas amizades de distanciam de nós, mas elas estão sempre lá, sempre agregando força a esse rio, querendo o nosso bem gratuitamente. Gostaria muito de agradecer aos amigos que fiz aqui em São Carlos. Aos amigos de república Mauro, Ronaldo, Sidão, Danielzinho e Marcio. À dois grandes amigos, Gustavo Batista e Richardson pelos bons momentos projetando e fazendo aviõezinhos e pelas conversas das mais diversas coisas. Pelos amigos que fiz na graduação, em especial ao Marcio, Alex, Kleber, Testa e Zóid. Agradeço a todos vocês por momentos onde a alegria, descontração e amizade se fizeram presentes. Cada um que passa em nossa vida, passa sozinho, pois cada pessoa é única e nenhuma substitui outra. Também gostaria de agradecer aos amigos que fiz na Inglaterra: Sebastian, Virgínia, Tarek, Bill, Ksenia, Susanna e Rob. Ao pes- soal do LABIC: André Maletzke, André Rossi, Andrés Ferrero, Bruno Ferres, Bruno Nogueira, Caneca, Claudio, Camila, Claudia Martins, Claudia Milaré, Christiane, Damiance, Débora, Edson Melanda, Eduardo Spinosa, Evandro, Fabiano, Flávia, Igor, Jaqueline, Jean, Katti, Leonardo, Lorena, Magaly, Mar- cio Basgalupp, Marcos Cintra, Marcos Quiles, Mariza, Merley, Murilo, Patrícia Rufino, Rafael Giusti, Renatinho, Roberta, Robson, Rodrigo Bianchi, Rodrigo Calvo e Valmir. Gostaria de agradecer à Pâmela, por ser tão única em minha vida e ter me ensinado coisas que somente você poderia ter me ensinado. Agradeço ao pessoal da pós-graduação do ICMC, à Beth, à Laura, à Ana Paula, por serem tão atenciosas a cada um de nós pós-graduandos. É incrí- vel como vocês decoram o nome de todos nós. Também à Marília por seus maravilhosos coffe breaks. Você tem um papel determinante na presença dos alunos e professores nas palestras. Agradeço também as pessoas que mantém a USP funcionando, como Pau- linho, Dotta, Sonia, Dagoberto, Cabral, Seu Arly e tantos outros que vão do setor administrativo ao faxineiro e jardineiro. Finalmente gostaria de agradecer à FAPESP pela minha bolsa de douto- rado, à CAPES pela minha bolsa de doutorado sandwich e ao ICMC-USP, pelo suporte e estrutura disponibilizados para o desenvolvimento de minha forma- ção. viii Abstract Supervised learning has been used mostly for classification. In this work we show the benefits of a welcome shift in attention from classification to ranking. A ranker is an algorithm that sorts a set of instances from highest to lowest expectation that the instance is positive, and a ranking is the out- come of this sorting. Usually a ranking is obtained by sorting scores given by classifiers. In this work, we are concerned about novel approaches to pro- mote the use of ranking. Therefore, we present the differences and relations between ranking and classification followed by a proposal of a novel ranking algorithm called LEXRANK, whose rankings are derived not from scores, but from a simple ranking of attribute values obtained from the training data. One very important field which uses rankings as its main input is ROC analysis. The study of decision trees and ROC analysis suggested an interesting way to visualize the tree construction in ROC graphs, which has been implemented in a system called PROGROC. Focusing on ROC analysis, we observed that the slope of segments obtained from the ROC convex hull is equivalent to the likelihood ratio, which can be converted into probabilities. Interestingly, this ROC convex hull calibration method is equivalent to Pool Adjacent Violators (PAV). Furthermore, the ROC convex hull calibration method optimizes Brier Score, and the exploration of this measure leads us to find an interesting con- nection between the Brier Score and ROC Curves. Finally, we also investigate rankings build in the selection method which increments the labelled set of CO-TRAINING, a semi-supervised multi-view learning algorithm. ix x