ABSTRACT

Several research fields have to deal with very large classification problems, e.g. human-computer interface and bioinformatics. However, the majority of the pattern recognition methods intended for large-scale problems aim to merely adapt standard classification models, without considering if those algorithms are actually appropriated for dealing with large data. Some models specifically developed for problems with large number of samples had been proposed, but few works have been done concerning problems with large number of classes. CombNET-II was one of the first methods proposed for such a kind of task. It consists of a sequential clustering vector-quantization based gating network (stem network) and several multilayer perceptron based expert classifiers (branch networks). With the objectives of increasing the classification accuracy and providing a more flexible solution, this work proposes a new model based on the CombNET-II structure, the CombNET-III. It replaces the branch networks’ algorithm with multiclass support vector machines and introduces a new probabilistic framework that outputs posterior class probabilities, enabling the model to be applied in different scenarios. In order to address the new model’s major drawback, its high classification computational complexity, a new two-layered gating network structure, the SGA-II, is presented. It reduces the compromise between number of clusters and accuracy, increasing the model’s performance. This high accuracy gating network enables the removal the low confidence expert networks from the decoding procedure. This, in addition to a new faster strategy for calculating multiclass support vector machines outputs, results in a computational complexity reduction of more than one order of magnitude. The extended structure also outperforms compared methods when applied to database with a large number of samples, confirming the CombNET-III model’s flexibility. In addition to those structures, several solutions for accuracy improvement and complexity reduction are presented, including methods based on feature subset selection.

あらまし

ヒューマン・コンピュータ・インターフェースやバイオインフォマティクスなどの研究分野では非常に大規模な分類問題に対処する必要がある。しかし従来の大規模分類問題においては通常の分類アルゴリズムをそのまま大規模分類に適用しているため、そのアルゴリズムが大規模データに実際に適しているかどうかを考慮していなかった。大規模問題のうち、サンプル数が非常に多い問題に対してはいくつかのモデルも提案されているが、クラス数が非常に多い問題に適応したモデルはわずかである。CombNET-II はこのようなクラス数が多い問題のために提案された方法の一つである。CombNET-II はベクトル量子化によるクラスタ化を行う大分類ネットワーク (Stem Network) と、複数の識別専門の多層パーセプトロン (Branch Network) から構成される。本研究では、CombNET-IIの認識率を向上させ、かつ汎用性を高める目的で、CombNET-II の構造を基にした新しいモデル、CombNET-III を提案した。CombNET-III では Branch Network におけるアルゴリズムをマルチクラス SVM に置き換え、またStem Networkにおいてクラスの事後確率を出力する新たな確率的構造を導入することにより、Branch Networkを構成するアルゴリズムとしてマルチクラスSVMに限らず多種のアルゴリズムに適応できるよう改善した。また、CombNET-IIIは学習性能の向上が可能であるが、SVMの性質に起因して認識時の計算コストが非常に高いという問題点がある。そこで本論文では新しい2層構造分類ネットワーク SGA-II を提案した。SGA-II はクラス数と精度の依存関係を減少させることで大分類ネットワークの性能を向上させることが可能であり、またこれにより入力パターンとの関連性の低い識別ネットワークの計算を省略することができるようになった。本論文ではSGA-IIにマルチクラス SVM の出力を高速に計算するための新たな戦略を加えることにより、従来法と比べて1桁以上の計算量の減少をもたらすことができた。また、提案手法を多くのサンプルをもつデータベースに適用した場合においても、他の手法と比較してCombNET-IIIの優位性を示すことが出来た。

RESUMO

Diversas áreas de pesquisa dependem do processamento de enormes quantidades de dados, e.g. aplicaçõoes de interface homem-máquina e bioinformática. A maioria dos métodos de classificação de larga escala, no entanto, meramente adaptam modelos convencionais, sem considerar se tais métodos são ou não apropriados a este tipo de problema. Alguns modelos especificamente desenvolvidos para problemas de larga escala contendo grande número de amostras são propostos na literatura. Poucos trabalhos, porém, abordam problemas contendo grande número de categorias. A CombNET-II foi um dos primeiros métodos propostos para tal situação. O modelo consiste de um algoritmo de clustering seqüencial baseado em quantização de vetores chamado stem network e várias redes neurais (perceptrons de múltiplas camadas) chamadas branch networks. Visando a redução da taxa de erro de classificação e o aumento de flexibilidade, este trabalho propõe um novo modelo baseado na estrutura da CombNET-II, chamado CombNET-III. Este modelo substitui o algoritmo das branch networks por support vector machines multi-classes e introduz um novo framework probabilístico, o qual gera probabilidades a posteriori de cada categoria, permitindo a aplicação do modelo proposto em diferentes cenários. Com o objetivo de minimizar o alto custo computacional de classificação da CombNET-III, é apresentada uma nova estrutura de dupla camada para a gating network, chamada SGA-II. O novo algoritmo, além de reduzir o compromisso entre o número de clusters e o erro de classificação, apresenta uma alta taxa de acerto, permitindo a eliminação de branch networks com baixa confidência no processo de decodificação. Em conjunto com uma nova estratégia para acelerar o cálculo da resposta de saída de support vector machines multi-classes, este procedimento resulta na redução da complexidade em mais de uma ordem de magnitude. Além disso, esta nova estrutura, quando aplicada a um problema de classificação contendo um grande número de amostras, apresentou uma taxa de erro menor que outros métodos de larga escala, confirmando a maior flexibilidade da CombNET-III. Além dessas estruturas principais, são apresentadas outras soluções para redução da taxa de erro de classificação e complexidade computacional, incluindo métodos baseados em redução de dimensionalidade por seleção de características.