Learning in high dimensional spaces: Applications, theory, and algorithms

Integration of audio and visual information plays a critical role in multimedia analysis. However, this poses a challenging problem of learning in high-dimensional space. Although the standard learning theory can be used to analyze learning problems in high dimensions, it falls short of giving practical guarantees.; In this dissertation, we study certain application scenarios where multimodal information fusion is necessary. In particular, the problem of activity recognition in office scenario and event detection in videos is analyzed. We present a hierarchical approach—layered hidden Markov model and duration-dependent input/output Markov model—to solve these two problems. The analysis of the methods shows that although a number of assumptions are made with respect to the conditional independencies and the dimensions of the data are huge, good generalization performance is achieved. This is not surprising. Most of the theoretical analysis is done keeping the worst case scenario in mind. This motivated us to revisit the existing results in learning theory leading to our study of various classification algorithms. We analyze the learning problems from the perspectives of both probabilistic classifiers and statistical learning theory. We develop the understanding of probabilistic classifiers, and give bounds on the additional penalty that is incurred when there is a mismatch between true distribution and one that is being used for classification. From the perspective of statistical learning theory, we use random projection based arguments to develop margin based bounds on the generalization error of linear classifiers. These are compared with the existing bounds on a number of real world problems and the results show that these are tighter than almost all the existing bounds.; The theoretical results are used to extend the existing learning algorithms. Based on the results from probabilistic classifiers, we have proposed an improved learning algorithm for HMMs which attempts to learn a maximum likelihood classifier under the minimum conditional entropy prior. A margin distribution optimization algorithm is proposed based on the results on generalization bounds and our results show that this new algorithm is better than the existing SVM and boosting algorithms.