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.
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.
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.
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
17974878
Variational Bayesian Dirichlet-Multinomial Allocation for Exponential Family Mixtures
This paper studies a Bayesian framework for density modeling with mixture of exponential family distributions. Variational Bayesian Dirichlet-Multinomial allocation (VBDMA) is introduced, which performs inference and learning efficiently using variational Bayesian methods and performs automatic model selection. The model is closely related to Dirichlet process mixture models and demonstrates similar automatic model selection in the variational Bayesian context.
8514244
A nonparametric hierarchical bayesian framework for information filtering
Information filtering has made considerable progress in recent years. The predominant approaches are content-based methods and collaborative methods. Researchers have largely concentrated on either of the two approaches since a principled unifying framework is still lacking. This paper suggests that both approaches can be combined under a hierarchical Bayesian framework. Individual content-based user profiles are generated and collaboration between various user models is achieved via a common learned prior distribution. However, it turns out that a parametric distribution (e.g. Gaussian) is too restrictive to describe such a common learned prior distribution. We thus introduce a nonparametric common prior, which is a sample generated from a Dirichlet process which assumes the role of a hyper prior. We describe effective means to learn this nonparametric distribution, and apply it to learn users' information needs. The resultant algorithm is simple and understandable, and offers a principled solution to combine content-based filtering and collaborative filtering. Within our framework, we are now able to interpret various existing techniques from a unifying point of view. Finally we demonstrate the empirical success of the proposed information filtering methods.
14165952
Efficient Night Gait Recognition Based on Template Matching
Gait is a useful biometric which can be used to recognize people at a distance when other biometrics are incapable. However, most work on gait recognition has been visible spectrum-oriented over the past decade, ignoring recognition at night which is in reality demand-imperative. This paper deals with the problem of night gait recognition via thermal infrared imagery. First of all, human detection is accomplished, based on the Gaussian mixture modeling of the background. Then, human silhouettes are extracted on the basis of preceding detection results. Moreover, a new gait representation called HTI is proposed to characterize gait signatures for recognition. An infrared night gait database was built to provide a foundation for night gait recognition. Experimental results on two gait datasets show the effectiveness of this method
14182899
DNA computing, sticker systems, and universality
Abstract. We introduce the sticker systems, a computability model, which is an abstraction of the computations using the Watson-Crick complementarity as in Adleman's DNA computing experiment, [1]. Several types of sticker systems are shown to characterize (modulo a weak coding) the regular languages, hence the power of finite automata. One variant is proven to be equivalent to Turing machines. Another one is found to have a strictly intermediate power.

27445105
Minimal cover-automata for finite languages
Abstract A cover-automaton A of a finite language L⊆Σ ∗ is a finite deterministic automaton (DFA) that accepts all words in L and possibly other words that are longer than any word in L . A minimal deterministic finite cover automaton (DFCA) 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.
122735646
Segmentation using multiscale cues
Edges at multiple scales provide complementary grouping cues for image segmentation. These cues are reliable within different ranges. The larger the scale of an edge, the longer range the grouping cues it designates, and the greater impact it has on the final segmentation. A good segmentation respects grouping cues at each scale. These intuitions are formulated in a graph-theoretic framework where multiscale edges define pairwise pixel affinity at multiple grids, each captured in one graph. A novel criterion called average cuts of normalized affinity is proposed to evaluate a simultaneous segmentation through all these graphs. Its near-global optima can be solved efficiently. With a sparse yet complete characterization of pairwise pixel affinity, this graph-cuts approach leads to a hierarchy of coarse to fine segmentations that naturally take care of textured regions and weak contours.
2196967
Multiclass spectral clustering
We propose a principled account on multiclass spectral clustering. Given a discrete clustering formulation, we first solve a relaxed continuous optimization problem by eigen-decomposition. We clarify the role of eigenvectors as a generator of all optimal solutions through orthonormal transforms. We then solve an optimal discretization problem, which seeks a discrete solution closest to the continuous optima. The discretization is efficiently computed in an iterative fashion using singular value decomposition and nonmaximum suppression. The resulting discrete solutions are nearly global-optimal. Our method is robust to random initialization and converges faster than other clustering methods. Experiments on real image segmentation are reported.