A new combinatorial approach to supervised learning: Application to gait recognition

Kong Zhang, Akshay Vashist, Ilya Muchnik, Casimir Kulikowski, Dimitris Metaxas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


In many supervised learning problems, objects are represented as a sequence of observations. To classify such data, existing methods build classifiers either based on their dynamics, or the statistics of the observations. However, similar observations shared by most objects are uninformative for identification. In this paper, we present a new approach that identifies similar observations across objects and use only informative data for classification. To do this, we construct a weighted multipartite graph from the training data, with weights representing the similarities between observations from different objects. Identification of uninformative observations is modeled as clustering on this multipartite graph using a combinatorial optimization formulation. Two-level hierarchical classifiers are, then, built using the clustering results. The first layer of the classifiers associates the test observations with a certain cluster, whereas the second level identifies the object within the cluster. Data associated with uninformative clusters are screened out. Final identification for the group of observations is obtained using the majority voting rule only from the informative observations. We apply our algorithm to the gait recognition problem. The hierarchical classifiers are built in four different feature spaces for silhouette images. Final classification is determined by aggregating results from these four feature spaces. The experimental results show that our method results in improved recognition rates in most cases compared with other previously reported methods.

Original languageEnglish (US)
Title of host publicationAnalysis and Modelling of Faces and Gestures - Second International Workshop, AMFG 2005, Proceedings
PublisherSpringer Verlag
Number of pages15
ISBN (Print)3540292292, 9783540292296
StatePublished - 2005
Externally publishedYes
Event2nd International Workshop on Analysis and Modelling of Faces and Gestures, AMFG 2005 - Beijing, China
Duration: Oct 16 2005Oct 16 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3723 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other2nd International Workshop on Analysis and Modelling of Faces and Gestures, AMFG 2005

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A new combinatorial approach to supervised learning: Application to gait recognition'. Together they form a unique fingerprint.

Cite this