Unsupervised Structural Learning And Its Applications

The representation of data is one of the key in machine learning.Traditional methods usually represent the data as points in high dimensional space via feature vector. Due to its simplicity,great progress and developments have been made in methods based on feature vector.However,recent research showed that feature vector can not describe some properties of data.Therefore,the representation based on structure attracts more and more attention of researchers.This dissertation focuses on the unsupervised structure learning.Because of the huge space of data structure,how to rapidly search the space by approximate method is the key problem of unsupervised structure learning.According to properties of the tasks,different algorithms are proposed. For document clustering,spectral hierarchical clustering algorithm is proposed to do hierarchical document clustering and blog tag taxonomy construction.For object recognition,structure induction and knowledge propagation are used to learn the structure and parameters of the graphical model of object.The main content and innovations in this dissertation are as follows:1.We introduce a Probabilistic Grammar-Markov Model(PGMM) which couples probabilistic context free grammars and Markov Random Fields.PGMM is a generative model defined over attributed features and is used to detect and classify objects in natural images.PGMM is designed so that it can perform rapid inference,parameter learning,and the more difficult task of structure induction. PGMM can deal with unknown 2D pose(position,orientation and scale) in both inference and learning different aspects of the model.The PGMM can be learnt in an unsupervised manner where the image can contain one objects of different object categories or even be pure background.We first study the weakly supervised case,where each image contains an example of the object category,and then generalize to less supervised cases.The experiments on a subset of the Caltech dataset show that our results are comparable with the current state of the art and our inference is performed in less than five seconds. 2.We present a method to learn probabilistic object models(POMs) with minimal supervision which can exploit different visual cues and perform tasks such as classification,segmentation,and recognition.We formulate this as a structure induction and learning task and our strategy is to learn and combine basic POMs that make use of complementary image cues.We describe a novel structure induction procedure which uses knowledge propagation to enable one POM to provide information to other POM and "teach them"(which greatly reduces the amount of supervision required for training and speeds up the inference). We give detailed experimental analysis on large datasets which show that the POMs is invariant to scale and rotation of the object(for learning and inference) and performs inference rapidly.In addition,the experimental results show that POMs can be applied to learn hybrid objects classes(i.e.when there are several objects and the identity of the object in each image is unknown).We emphasize that these models can match between different objects from the same category and hence enable object recognition.3.We present spectral hierarchical clustering(SHC),a novel hierarchical clustering algorithm.Spectral analysis on SHC is provided by spectral graph theory which is commonly used in flat clustering but novel for hierarchical clustering.SHC uses the numeric techniques of Algebraic Multi-Grid method to perform fine-tocoarse weighted aggregation recursively.We evaluate the proposed algorithm on a number of different benchmark datasets.The comparison results show that our algorithm performs much better than the state-of-the-art hierarchical clustering algorithms.SHC is applied to the application of blog tag taxonomy construction. The results demonstrate that SHC performs more consistently with human judgments than other methods.Moreover,the resulting natural irregular tag hierarchy obtained by SHC is easier for users to browse the structure and locate the tags of interest.