An unsupervised approach to feature discretization and selection

Many learning problems require handling high dimensional datasets with a relatively small number of instances. Learning algorithms are thus confronted with the curse of dimensionality, and need to address it in order to be effective. Examples of these types of data include the bag-of-words representation in text classification problems and gene expression data for tumor detection/classification. Usually, among the high number of features characterizing the instances, many may be irrelevant (or even detrimental) for the learning tasks. It is thus clear that there is a need for adequate techniques for feature representation, reduction, and selection, to improve both the classification accuracy and the memory requirements. In this paper, we propose combined unsupervised feature discretization and feature selection techniques, suitable for medium and high-dimensional datasets. The experimental results on several standard datasets, with both sparse and dense features, show the efficiency of the proposed techniques as well as improvements over previous related techniques.     

Time–HOBI: Index for optimizing star queries

One of the important research and technological problems in data warehouse query optimization concerns star queries. So far, most of the research focused on optimizing such queries by means of join indexes, bitmap join indexes, or various multidimensional indexes. These structures neither support navigation well along dimension hierarchies nor optimize joins with the Time dimension, which in practice is used in most of the star queries. In this paper we propose an index, called Time–HOBI, for optimizing the star queries that compute aggregates along dimension hierarchies. Time–HOBI, created on a dimension hierarchy, is composed of (1) a Hierarchically Organized Bitmap Index (HOBI), where one bitmap index is maintained for one dimension level, and (2) a Time Index (TI) that implicitly encodes time in every dimension. HOBI allows to quickly search for fact rows satisfying predicates defined on different levels of dimension hierarchies. With the support of TI joining a fact table with the Time dimension is avoided. Thus, Time–HOBI supports a broad class of star queries. In this paper we explain how query execution plans for star queries can profit from Time–HOBI. We show, based on experiments, the efficiency of Time–HOBI for different classes of queries, as compared to HOBI and a traditional bitmap index. Based on the experiments, we also demonstrate how sensitive Time–HOBI is to variable selectivity of queries. We also analyze the maintenance time of Time–HOBI as compared to HOBI and a traditional bitmap index. The experiments used in the paper have been conducted on a real dataset, coming from the biggest East-European Internet auction platform Allegro.pl. The experiments show that Time–HOBI can be successfully applied to the optimization of star queries as it offers promising performance improvement.     

Fast relational learning using bottom clause propositionalization with artificial neural networks

Relational learning can be described as the task of learning first-order logic rules from examples. It has enabled a number of new machine learning applications, e.g. graph mining and link analysis. Inductive Logic Programming (ILP) performs relational learning either directly by manipulating first-order rules or through propositionalization, which translates the relational task into an attribute-value learning task by representing subsets of relations as features. In this paper, we introduce a fast method and system for relational learning based on a novel propositionalization called Bottom Clause Propositionalization (BCP). Bottom clauses are boundaries in the hypothesis search space used by ILP systems Progol and Aleph. Bottom clauses carry semantic meaning and can be mapped directly onto numerical vectors, simplifying the feature extraction process. We have integrated BCP with a well-known neural-symbolic system, C-IL²P, to perform learning from numerical vectors. C-IL²P uses background knowledge in the form of propositional logic programs to build a neural network. The integrated system, which we call CILP++, handles first-order logic knowledge and is available for download from Sourceforge. We have evaluated CILP++ on seven ILP datasets, comparing results with Aleph and a well-known propositionalization method, RSD. The results show that CILP++ can achieve accuracy comparable to Aleph, while being generally faster, BCP achieved statistically significant improvement in accuracy in comparison with RSD when running with a neural network, but BCP and RSD perform similarly when running with C4.5. We have also extended CILP++ to include a statistical feature selection method, mRMR, with preliminary results indicating that a reduction of more than 90 % of features can be achieved with a small loss of accuracy.     

Sampling from repairs of conditional functional dependency violations

Violations of functional dependencies (FDs) and conditional functional dependencies (CFDs) are common in practice, often indicating deviations from the intended data semantics. These violations arise in many contexts such as data integration and Web data extraction. Resolving these violations is challenging for a variety of reasons, one of them being the exponential number of possible repairs. Most of the previous work has tackled this problem by producing a single repair that is nearly optimal with respect to some metric. In this paper, we propose a novel data cleaning approach that is not limited to finding a single repair, namely sampling from the space of possible repairs. We give several motivating scenarios where sampling from the space of CFD repairs is desirable, we propose a new class of useful repairs, and we present an algorithm that randomly samples from this space in an efficient way. We also show how to restrict the space of repairs based on constraints that reflect the accuracy of different parts of the database. We experimentally evaluate our algorithms against previous approaches to show the utility and efficiency of our approach.     

Ambient bloom: new business, content, design and models to increase the semantic ambient media experience

Semantic ambient media are the novel trend in the world of media reaching from the pioneering subareas such as ambient advertising to the new and emerging subareas such as ambient assisted living. They will likely shape the upcoming years in terms of modeling smart environments and also media consumption and interaction. This work analyzes semantic ambient media by considering business models, content and media, interaction design and consumer experience, and methods and techniques that are important to create this new form of media. Discussion is led using the state-of-the-art event of the semantic ambient media, which is the annual international workshop on Semantic Ambient Media Experience (SAME). The study also creates a vision for how ambient media will evolve and how they will look like in the future decade.     

Automatic contrast enhancement of low-light images based on local statistics of wavelet coefficients

This paper describes a new method for contrast enhancement in images and image sequences of low-light or unevenly illuminated scenes based on statistical modelling of wavelet coefficients of the image. A non-linear enhancement function has been designed based on the local dispersion of the wavelet coefficients modelled as a bivariate Cauchy distribution. Within the same statistical framework, a simultaneous noise reduction in the image is performed by means of a shrinkage function, thus preventing noise amplification. The proposed enhancement method has been shown to perform very well with insufficiently illuminated and noisy imagery, outperforming other conventional methods, in terms of contrast enhancement and noise reduction in the output data.     

Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures

We consider randomized simulations of shared memory on a distributed memory machine (DMM) where thenprocessors and thenmemory modules of the DMM are connected via a reconfigurable architecture. We first present a randomized simulation of a CRCW PRAM on a reconfigurable DMM having a complete reconfigurable interconnection. It guarantees delay (log *n), with high probability. Next we study a reconfigurable mesh DMM (RM-DMM). Here thenprocessors andnmodules are connected via ann×nreconfigurable mesh. It was already known that ann×mreconfigurable mesh can simulate in constant time ann-processor CRCW PRAM with shared memory of sizem. In this paper we present a randomized step by step simulation of a CRCW PRAM with arbitrarily large shared memory on an RM-DMM. It guarantees constant delay with high probability, i.e., it simulates in real time. Finally we prove a lower bound showing that sizeΩ(n²) for the reconfigurable mesh is necessary for real time simulations.     

Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth

It has recently been proved (Je?, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some non-regular languages over a one-letter alphabet. The present paper improves this result by constructing conjunctive grammars for a larger class of unary languages. The results imply undecidability of a number of decision problems of unary conjunctive grammars, as well as non-existence of a recursive function bounding the growth rate of the generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations.