Abstract
We have applied the min-max modular support vector machine and the part-versus-part task decomposition method to dealing with multi-view face recognition problems. We have demonstrated that face pose information can be easily incorporated into the procedure of dividing a multi-view face recognition problem into a series of relatively easier two-class subproblems. We have performed some experiments on the UMIST database and compared with the standard support vector machines. The experimental results indicate that the min-max modular support vector machine can improve the accuracy of multi-view face recognition and reduce the training time. As a future work, we will perform experiments on large-scale face databases with various face poses. We believe that the min-max modular support vector machine with incorporating pose information into task decomposition will have more advantages over traditional support vector machines in both training time and recognition accuracy when a more number of training samples are available.
Introduction
Standard Support Vector Machines (SVMs) are highly effective classifiers, but their training time typically scales quadratically with the number of samples. This poses a significant hurdle for large-scale, multi-class problems. Multi-view face recognition exemplifies this challenge; while algorithms like Eigenfaces perform well for frontal views, they struggle with the complex, nonlinear data manifolds created by varying head poses, such as profile and half-profile shots. This paper addresses these challenges by rethinking the classification task structure through a modular decomposition approach.
The $M^3$-SVM Architecture
The core innovation is a "divide and conquer" strategy using Min-Max Modular SVMs ($M^3$-SVMs). The architecture breaks a massive multi-class problem into thousands of tiny, independent two-class subproblems.
Part-Versus-Part Task Decomposition
Instead of training one monolithic multi-class SVM, the authors decompose a $K$-class problem into $K(K-1)/2$ two-class problems. They further refine this by using prior knowledge—specifically, face pose angles (e.g., 0°, 30°, 60°, 90°)—to divide the training data of each class into smaller subsets. For a 20-class problem, this shatters the dataset into thousands of micro-SVMs.
Min-Max Combination
Once these sub-SVMs are trained, their outputs are integrated using logical MIN and MAX units. This bottom-up integration follows strict minimization and maximization principles to arrive at the final classification decision.
Computational Complexity and Scalability
The modular nature of $M^3$-SVM significantly impacts the number of elements required for the system. The table below summarizes the theoretical number of elements for different components of the architecture.
By breaking a 20-class problem into over 3,000 subproblems, the complexity of each individual optimization task drops significantly. This modularity makes the system "embarrassingly parallel," as every subproblem is independent during training, making it ideal for distributed computing environments.
Feature Selection with SVM-DFS
To handle high-dimensional image data, the authors employ SVM-Discriminative Feature Selection (SVM-DFS). This technique uses the weights of linear SVM decision boundaries to rank and select the most informative features. By reducing dimensionality before the $M^3$-SVM training phase, the system maintains efficiency without sacrificing discriminative power.
Experimental Results
The approach was evaluated using the UMIST Face Database, which contains 575 grayscale images of 20 subjects across various poses. The dataset was split into 240 training images (12 specific poses per person) and 335 testing images.
- Accuracy Boost: $M^3$-SVM consistently outperformed standard one-vs-all SVMs. With 300 features, $M^3$-SVM achieved 93.13% accuracy, compared to 92.83% for the standard SVM.
- Massive Speedups: When trained in parallel, $M^3$-SVM required only 0.531 seconds (at 300 features), whereas the standard SVM took 0.862 seconds.
- Robustness at Low Dimensionality: Even at a reduced feature count of 100, $M^3$-SVM maintained 83.88% accuracy, surpassing the standard SVM's 82.38%.
Conclusion
The $M^3$-SVM architecture demonstrates that incorporating physical metadata like face pose into task decomposition can simplify decision boundaries and drastically reduce training time. While the current evaluation uses a relatively small dataset, the authors anticipate that the advantages of this modular approach will scale exponentially with larger databases, making it a promising solution for real-world biometric systems. Future work will focus on large-scale databases and continuous pose variations.
Summary updated