Sequential labeling with structural SVM under non-decomposable loss functions

Publication Type:
Issue Date:
Full metadata record
This thesis mainly focuses on the sequential labeling problem. Sequential labeling is a fundamental problem in computer vision and machine learning areas and has been researched in many applications. The most popular model for sequential labeling is the hidden Markov model where the sequence of class labels to be predicted is encoded as a Markov chain. In recent years, other structural models, in particular, the extension of SVM to the classification of sequences and other structures have benefited from minimum-loss training approaches which in many cases lead to greater classification accuracy. However, SVM training requires the choice of a suitable loss function. Common loss functions available for training are restricted to decomposable cases such as the zero-one loss and the Hamming loss. Other useful losses such as the F₁ loss, average precision (AP) loss, equal error rates and others are not available for sequential labeling. For the average precision, some results have been proposed in the past, but our results are more general. On the other hand, classification accuracy often suffers from the uncertainty of ground truth labeling and traditional structural SVM only ensures that the ground-truth labeling of each sample receives a score higher than that of any other labeling. However, no specific score ranking is imposed among the other labelings. For the loss functions problem, we propose a training algorithm that can cater for the F₁ loss and any other loss function based on the contingency table. In our thesis, we propose exact solutions for the F₁ loss, precision/recall at fixed value of recall/precision, precision for a fixed value of predicted positives ("precision at k"), precision/recall Break-Even Point and a formulation of the Average Precision (AP loss). For further experiments, we not only apply the AP loss in the training, but also in testing. For the uncertainty in the ground-truth labeling problem, we extend the standard constraint set of structural SVM with constraints between "almost-correct" labelings and less desirable ones to obtain a partial ranking structural SVM (PR-SSVM) approach. We choose different datasets to verify our approaches: human activity datasets including the challenging TUM Kitchen dataset and CMU-MMAC dataset, and the Ozone Level Detection dataset. The experimental results show the efficiency of our approaches on different performance measurements, such as detection rate, false alarm rate and F₁ measure, compared to the conventional SVM, HMM and structural SVM with decomposable losses such as the 0-1 loss and Hamming loss.
Please use this identifier to cite or link to this item: