7566163
Dirichlet enhanced relational learning
We apply nonparametric hierarchical Bayesian modelling to relational learning. In a hierarchical Bayesian approach, model parameters can be "personalized", i.e., owned by entities or relationships, and are coupled via a common prior distribution. Flexibility is added in a nonparametric hierarchical Bayesian approach, such that the learned knowledge can be truthfully represented. We apply our approach to a medical domain where we form a nonparametric hierarchical Bayesian model for relations involving hospitals, patients, procedures and diagnosis. The experiments show that the additional flexibility in a nonparametric hierarchical Bayes approach results in a more accurate model of the dependencies between procedures and diagnosis and gives significantly improved estimates of the probabilities of future procedures.
2852882
Hierarchy-regularized latent semantic indexing
Organizing textual documents into a hierarchical taxonomy is a common practice in knowledge management. Beside textual features, the hierarchical structure of directories reflect additional and important knowledge annotated by experts. It is generally desired to incorporate this information into text mining processes. In this paper, we propose hierarchy-regularized latent semantic indexing, which encodes the hierarchy into a similarity graph of documents and then formulates an optimization problem mapping each document into a low dimensional vector space. The new feature space preserves the intrinsic structure of the original taxonomy and thus provides a meaningful basis for various learning tasks like visualization and classification. Our approach employs the information about class proximity and class specificity, and can naturally cope with multi-labeled documents. Our empirical studies show very encouraging results on two real-world data sets, the new Reuters (RCVI) benchmark and the Swissprot protein database.
3164237
Multi-output regularized projection
Dimensionality reduction via feature projection has been widely used in pattern recognition and machine learning. It is often beneficial to derive the projections not only based on the inputs but also on the target values in the training data set. This is of particular importance in predicting multivariate or structured outputs which is an area of growing interest. In this paper we introduce a novel projection framework which is sensitive to both input features and outputs. Based on the derived features prediction accuracy can be greatly improved. We validate our approach in two applications. The first is to model users' preferences on a set of paintings. The second application is concerned with image categorization where each image may belong to multiple categories. The proposed algorithm produces very encouraging results in both settings.
268086
Collaborative ordinal regression
Ordinal regression has become an effective way of learning user preferences, but most research focuses on single regression problems. In this paper we introduce collaborative ordinal regression, where multiple ordinal regression tasks are handled simultaneously. Rather than modeling each task individually, we explore the dependency between ranking functions through a hierarchical Bayesian model and assign a common Gaussian Process (GP) prior to all individual functions. Empirical studies show that our collaborative model outperforms the individual counterpart in preference learning applications.
1394662
Dirichlet Enhanced Latent Semantic Analysis
This paper describes nonparametric Bayesian treatments for analyzing records containing occurrences of items. The introduced model retains the strength of previous approaches that explore the latent factors of each record (e.g. topics of documents), and further uncovers the clustering structure of records, which reflects the statistical dependencies of the latent factors. The nonparametric model induced by a Dirichlet process (DP) flexibly adapts model complexity to reveal the clustering structure of the data. To avoid the problems of dealing with infinite dimensions, we further replace the DP prior by a simpler alternative, namely Dirichlet-multinomial allocation (DMA), which maintains the main modelling properties of the DP. Instead of relying on Markov chain Monte Carlo (MCMC) for inference, this paper applies efficient variational inference based on DMA. The proposed approach yields encouraging empirical results on both a toy problem and text data. The results show that the proposed algorithm uncovers not only the latent factors, but also the clustering structure.
11243052
Improving pseudo-relevance feedback in web information retrieval using web page segmentation
In contrast to traditional document retrieval, a web page as a whole is not a good information unit to search because it often contains multiple topics and a lot of irrelevant information from navigation, decoration, and interaction part of the page. In this paper, we propose a VIsion-based Page Segmentation (VIPS) algorithm to detect the semantic content structure in a web page. Compared with simple DOM based segmentation method, our page segmentation scheme utilizes useful visual cues to obtain a better partition of a page at the semantic level. By using our VIPS algorithm to assist the selection of query expansion terms in pseudo-relevance feedback in web information retrieval, we achieve 27% performance improvement on Web Track dataset.
13332239
A Hierarchical Markov Random Field Model for Figure-Ground Segregation
To segregate overlapping objects into depth layers requires the integration of local occlusion cues distributed over the entire image into a global percept. We propose to model this process using hierarchical Markov random field (HMRF), and suggest a broader view that clique potentials in MRF models can be used to encode any local decision rules. A topology-dependent multiscale hierarchy is used to introduce long range interaction. The operations within each level are identical across the hierarchy. The clique parameters that encode the relative importance of these decision rules are estimated using an optimization technique called learning from rehearsals based on 2-object training samples. We find that this model generalizes successfully to 5-object test images, and that depth segregation can be completed within two traversals across the hierarchy. This computational framework therefore provides an interesting platform for us to investigate the interaction of local decision rules and global representations, as well as to reason about the rationales underlying some of recent psychological and neurophysiological findings related to figure-ground segregation.
10900126
Measures of Nondeterminism for Pushdown Automata
D. Vermeir and W. Savitch (Fund. Inform.4 (1981), 401-418) introduced two measures of nondeterminism for pushdown automata and showed interestingly that the second measure, which we refer to as the depth measure, yields an infinite hierarchy of language families between the deterministic context-free and general context-free languages. However, the proof given in op. cit. for this hierarchy theorem was incorrect. In this paper, using a pumping result for deterministic context-free languages we give a new proof for the strictness of the depth hierarchy. We introduce the monadic depth measure which is also shown to give rise to an infinite hierarchy of language families. Furthermore, we show that the monadic hierarchy is shifted by at most one level from the unrestricted depth hierarchy.
7865019
Follow automata
We give two new algorithms for constructing small nondeterministic finite automata (NFA) from regular expressions. The first constructs NFAs with e-transitions (eNFA) which are smaller than all the other eNFAs obtained by similar constructions. Their size is at most 3/2 |α| + 5/2, where α is the regular expression. This is very close to optimal since we prove also the lower bound 4/3; |α| + 5/2. The second constructs NFAs. It uses e-elimination in the eNFAs we just introduced and builds a quotient of the well-known position automaton w.r.t. the equivalence given by the follow relation; therefore giving the name of follow automaton. The new automaton uses optimally the information from the positions of a regular expression. We compare the follow automaton with the best constructions to date and show that it has important advantages over those.
38593151
Performance Comparison of a Deterministic and a Stochastic Method for Image Classification
In this paper, we compare the performances of two methods that we proposed for image classification. The first method is a stochastic approach which uses a Markov random field modelization. An optimization technique based on the game theory is used for the maximization of the a posteriori probability of the classes. The second method is a deterministic one which uses a feed-forward neural network. A novel learning method called projection learning is employed to train the neural network. The performances of these two methods are compared through their applications to image classification. The advantages and disadvantages of both methods, as well as possibilities to improve them are discussed.
14436503
Implementing a Model Checker for LEGO
Interactive theorem proving provides a general approach to modelling and verification of both hardware and software systems but requires significant human efforts to deal with many tedious proofs. To be effectively used in practice, we need some automatic tools such as model checkers to deal with those tedious proofs. In this paper, we formalise a verification system of both CCS and an imperative language in the proof development system LEGO which can be used to verify both finite and infinite problems. Then a model checker, LegoMC, is implemented to generate LEGO proof terms for finite-state problems automatically. Therefore people can use LEGO to verify a general problem with some of its finite sub-problems verified by LegoMC. On the other hand, this integration extends the power of model checking to verify more complicated and infinite models as well.