11104953
Multi-Output Regularized Feature Projection
Dimensionality reduction by feature projection is widely used in pattern recognition, information retrieval, and statistics. When there are some outputs available (e.g., regression values or classification results), it is often beneficial to consider supervised projection, which is based not only on the inputs, but also on the target values. While this applies to a single-output setting, we are more interested in applications with multiple outputs, where several tasks need to be learned simultaneously. In this paper, we introduce a novel projection approach called multi-output regularized feature projection (MORP), which preserves the information of input features and, meanwhile, captures the correlations between inputs/outputs and (if applicable) between multiple outputs. This is done by introducing a latent variable model on the joint input-output space and minimizing the reconstruction errors for both inputs and outputs. It turns out that the mappings can be found by solving a generalized eigenvalue problem and are ready to extend to nonlinear mappings. Prediction accuracy can be greatly improved by using the new features since the structure of outputs is explored. We validate our approach in two applications. In the first setting, we predict users' preferences for a set of paintings. The second is concerned with image and text categorization where each image (or document) may belong to multiple categories. The proposed algorithm produces very encouraging results in both settings
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.
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.
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.
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.
5352244
Minimal Cover-Automata for Finite Languages
A cover-automaton A of a finite language L ⊆ Σ * is a finite automaton that accepts all words in L and possibly other words that are longer than any word in L. A minimal deterministic cover automaton of a finite language L usually has a smaller size than a minimal DFA that accept L. Thus, cover automata can be used to reduce the size of the representations of finite languages in practice. In this paper, we describe an efficient algorithm that, for a given DFA accepting a finite language, constructs a minimal deterministic finite cover- automaton of the language. We also give algorithms for the boolean operations on deterministic cover automata, i.e., on the finite languages they represent.
12739377
Word Complexity And Repetitions In Words
With ideas from data compression and combinatorics on words, we introduce a complexity measure for words, called repetition complexity, which quantifies the amount of repetition in a word. The repetition complexity of w, R(w), is defined as the smallest amount of space needed to store w when reduced by repeatedly applying the following procedure: n consecutive occurrences uu…u of the same subword u of w are stored as (u,n). The repetition complexity has interesting relations with well-known complexity measures, such as subword complexity, SUB, and Lempel-Ziv complexity, LZ. We have always R(w)≥LZ(w) and could even be that the former is linear while the latter is only logarithmic; e.g., this happens for prefixes of certain infinite words obtained by iterated morphisms. An infinite word α being ultimately periodic is equivalent to: (i) , (ii) , and (iii) . De Bruijn words, well known for their high subword complexity, are shown to have almost highest repetition complexity; the precise complexity remains open. R(w) can be computed in time and it is open, and probably very difficult, to find fast algorithms.
329765
Unsupervised segmentation of color images
A novel technique for unsupervised learning in feature space is presented. The feature space is considered as composed of two distinct sources, "mode" and "valley", in the point of view of information theory. An entropy-based thresholding is taken to distinguish the discretized cells in the feature space. The cells labeled as "mode" are then chained to form mode areas. Thereafter a modified Akaike's information criterion is proposed to solve the cluster validity problem. After all the parameters are estimated, a labeling algorithm is developed based on the majority game theory. The method is applied to color image segmentation. The segmentation process is completely autonomous.
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.