10350219
Multi-label informed latent semantic indexing
Latent semantic indexing (LSI) is a well-known unsupervised approach for dimensionality reduction in information retrieval. However if the output information (i.e. category labels) is available, it is often beneficial to derive the indexing not only based on the inputs but also on the target values in the training data set. This is of particular importance in applications with multiple labels, in which each document can belong to several categories simultaneously. In this paper we introduce the multi-label informed latent semantic indexing (MLSI) algorithm which preserves the information of inputs and meanwhile captures the correlations between the multiple outputs. The recovered "latent semantics" thus incorporate the human-annotated category information and can be used to greatly improve the prediction accuracy. Empirical study based on two data sets, Reuters-21578 and RCV1, demonstrates very encouraging results.
946526
A Probabilistic Clustering-Projection Model for Discrete Data
For discrete co-occurrence data like documents and words, calculating optimal projections and clustering are two different but related tasks. The goal of projection is to find a low-dimensional latent space for words, and clustering aims at grouping documents based on their feature representations. In general projection and clustering are studied independently, but they both represent the intrinsic structure of data and should reinforce each other. In this paper we introduce a probabilistic clustering-projection (PCP) model for discrete data, where they are both represented in a unified framework. Clustering is seen to be performed in the projected space, and projection explicitly considers clustering structure. Iterating the two operations turns out to be exactly the variational EM algorithm under Bayesian model inference, and thus is guaranteed to improve the data likelihood. The model is evaluated on two text data sets, both showing very encouraging results.
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.
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.
13007604
Extracting Content Structure for Web Pages Based on Visual Representation
A new web content structure based on visual representation is proposed in this paper. Many web applications such as information retrieval, information extraction and automatic page adaptation can benefit from this structure. This paper presents an automatic top-down, tag-tree independent approach to detect web content structure. It simulates how a user understands web layout structure based on his visual perception. Comparing to other existing techniques, our approach is independent to underlying documentation representation such as HTML and works well even when the HTML structure is far different from layout structure. Experiments show satisfactory results.
2476670
Soft Clustering on Graphs
We propose a simple clustering framework on graphs encoding pairwise data similarities. Unlike usual similarity-based methods, the approach softly assigns data to clusters in a probabilistic way. More importantly, a hierarchical clustering is naturally derived in this framework to gradually merge lower-level clusters into higher-level ones. A random walk analysis indicates that the algorithm exposes clustering structures in various resolutions, i.e., a higher level statistically models a longer-term diffusion on graphs and thus discovers a more global clustering structure. Finally we provide very encouraging experimental results.
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.
546963
Decision Problems for Patterns
We settle an open problem, the inclusion problem for pattern languages. This is the first known case where inclusion is undecidable for generative devices having a trivially decidable equivalence problem. The study of patterns goes back to the seminal work of Thue and is important also, for instance, in recent work concerning inductive inference and learning. Our results concern both erasing and nonerasing patterns.
10375023
A Pumping Lemma for Deterministic Context-Free Languages
Abstract In this paper, we introduce a new pumping lemma and a new iteration theorem for deterministic context-free languages (DCFLs). As application of the lemma, several languages are shown not to be deterministic context-free by using this lemma. An iteration theorem for DCFLs has already been introduced by Harrison in [3]. However, the result presented in this paper is different from his. Instead of considering the pumping property of individual words, we consider the pumping property of pairs of words. The latter approach seems more natural to the DCFLs (LR(1) languages). The pumping lemma introduced in this paper also appears to be easier to understand and use. We conjecture that there exist languages that can be shown not to be DCFLs by this new result but cannot be shown by the existing one. In Section 1, we introduce the basic notations used in this paper. In Section 2, we state our pumping lemma (without a proof) and show two applications of the lemma. In Section 3, a left-part theorem for LR ( k ) grammars is introduced, which is crucial to the proof of the pumping lemma and interesting on its own right. In the last section, we prove the lemma and extend it to an iteration theorem.
5267471
Fault-Tolerant Servers for Anycast Communication
Plenty of research has been done for any cast service, but few research touches the fault-tolerant problem based on the best of our knowledge. In this paper, we propose and analyse a fault-tolerant model, called twin server model, for anycast communication to provide reliable and continuous anycast services. We select a twin server in an anycast group for a given anycast server, the primary server. If the twin server suspects that its primary server is dead, it will take the unfinished job(s) of its primary server. We propose two algorithms: the server failure detecting algorithm and the server failure broadcasting algorithm. We then analyse the performance change when a primary server fails using queue theory and obtain some interesting conclusions. At the end, we summary the paper and present the future work.
12352201
Tight Lower Bound for the State Complexity of Shuffle of Regular Languages
The upper bound for the state complexity of the shuffle of two regular languages is 2mn -1. We prove that this bound can be reached for some (not necessarily complete) deterministic finite automata with, respectively, m and n states. Our construction uses an alphabet of size 5.