Study on non-parametric methods for fast pattern recognition with emphasis on neural networks and cascade classifiers

Abstract

Esta tese concentra-se em reconhecimento de padrões, com particular ênfase para o con ito de escolha entre capacidade de generalização e custo computacional, a m de fornecer suporte para aplicações em tempo real. Neste contexto são apresentadas contribuições metodológicas e analíticas para a abordagem de dois tipos de datasets: balanceados e desbalanceados. Um dataset é denominado balanceado quando há um número aproximadamente igual de observações entre as classes, enquanto datasets que têm números desiguais de observações entre as classes são denominados desbalanceados, tal como ocorre no caso de detecção de objetos baseada em imagem. Para datasets balanceados é adoptado o perceptrão multicamada (MLP) como classi cador, uma vez que tal modelo é um aproximador universal, ou seja MLPs podem aproximar qualquer conjunto de dados. Portanto, ao invés de propor novos modelos de classi cadores, esta tese concentra-se no desenvolvimento e análise de novos métodos de treinamento para MLP, de forma a melhorar a sua capacidade de generalização através do estudo de quatro abordagens diferentes: maximização da margem de classi cação, redundância, regularização, e transdução. A idéia é explorar novos métodos de treino para MLP com vista a obter classi cadores não-lineares mais rápidos que o usual SVM com kernel não-linear, mas com capacidade de generalização similar. Devido à sua função de decisão, o SVM com kernel não-linear exige um esforço computacional elevado quando o número de vetores de suporte é grande. No contexto dos datasets desbalanceados, adotou-se classi cadores em cascata, já que tal modelo pode ser visto como uma árvore de decisão degenerativa que realiza rejeições em cascata, mantendo o tempo de processamento adequado para aplicações em tempo real. Tendo em conta que conjuntos de classi cadores são susceptíveis a ter alta dimensão VC, que pode levar ao over- tting dos dados de treino, foram deduzidos limites para a capacidade de generalização dos classi cadores em cascata, a m de suportar a aplicação do princípio da minimização do risco estrutural (SRM). Esta tese também apresenta contribuições na seleção de características e dados de treinamento, devido à forte in uência que o pre-processamento dos dados tem sobre o reconhecimento de padrões. Os métodos propostos nesta tese foram validados em vários datasets do banco de dados da UCI. Alguns resultados experimentais já podem ser consultados em três revistas da ISI, outros foram submetidos a duas revistas e ainda estão em processo de revisão. No entanto, o estudo de caso desta tese é limitado à detecção e classi cação de peões.

This thesis focuses on pattern recognition, with particular emphasis on the trade o between generalization capability and computational cost, in order to provide support for on-the- y applications. Within this context, two types of datasets are analyzed: balanced and unbalanced. A dataset is categorized as balanced when there are approximately equal numbers of observations in the classes, while unbalanced datasets have unequal numbers of observations in the classes, such as occurs in case of imagebased object detection. For balanced datasets it is adopted the multilayer perceptron (MLP) as classi er, since such model is a universal approximator, i.e. MLPs can t any dataset. Therefore, rather than proposing new classi er models, this thesis focuses on developing and analysing new training methods for MLP, in order to improve its generalization capability by exploiting four di erent approaches: maximization of the classi cation margin, redundancy, regularization, and transduction. The idea is to exploit new training methods for MLP aiming at an nonlinear classi er faster than the usual SVM with nonlinear kernel, but with similar generalization capability. Note that, due to its decision function, the SVM with nonlinear kernel requires a high computational e ort when the number of support vectors is big. For unbalanced datasets it is adopted the cascade classi er scheme, since such model can be seen as a degenerate decision tree that performs sequential rejection, keeping the processing time suitable for on-the- y applications. Taking into account that classi er ensembles are likely to have high VC dimension, which may lead to over- tting the training data, it were derived generalization bounds for cascade classi ers, in order to support the application of structural risk minimization (SRM) principle. This thesis also presents contributions on feature and data selection, due to the strong in uence that data pre-processing has on pattern recognition. The methods proposed in this thesis were validated through experiments on several UCI benchmark datasets. Some experimental results can be found in three ISI journals, others has been already submitted to two ISI journals, and are under review. However, the case study of this thesis is limited to pedestrian detection and classi cation.