OpenRaiser/Intern-Atlas huggingface dataset:
Probabilistic Models for Query Approximation with Large Sparse Binary Datasets
Venue: arXiv cs.AI 2013
Year: 2013

Large sparse sets of binary transaction data with millions of records and thousands of attributes occur in various domains: customers purchasing products, users visiting web pages, and documents containing words are just three typical examples. Real-time query selectivity estimation (the problem of estimating the number of rows in the data satisfying a given predicate) is an important practical problem for such databases. We investigate the application of probabilistic models to this problem. In particular, we study a Markov random field (MRF) approach based on frequent sets and maximum entropy, and compare it to the independence model and the Chow-Liu tree model. We find that the MRF model provides substantially more accurate probability estimates than the other methods but is more expensive from a computational and memory viewpoint. To alleviate the computational requirements we show how one can apply bucket elimination and clique tree approaches to take advantage of structure in the models and in the queries. We provide experimental results on two large real-world transaction datasets.
Monte Carlo Inference via Greedy Importance Sampling
Venue: arXiv cs.LG 2013
Year: 2013

We present a new method for conducting Monte Carlo inference in graphical models which combines explicit search with generalized importance sampling. The idea is to reduce the variance of importance sampling by searching for significant points in the target distribution. We prove that it is possible to introduce search and still maintain unbiasedness. We then demonstrate our procedure on a few simple inference tasks and show that it can improve the inference quality of standard MCMC methods, including Gibbs sampling, Metropolis sampling, and Hybrid Monte Carlo. This paper extends previous work which showed how greedy importance sampling could be correctly realized in the one-dimensional case.
Exploiting Qualitative Knowledge in the Learning of Conditional Probabilities of Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

Algorithms for learning the conditional probabilities of Bayesian networks with hidden variables typically operate within a high-dimensional search space and yield only locally optimal solutions. One way of limiting the search space and avoiding local optima is to impose qualitative constraints that are based on background knowledge concerning the domain. We present a method for integrating formal statements of qualitative constraints into two learning algorithms, APN and EM. In our experiments with synthetic data, this method yielded networks that satisfied the constraints almost perfectly. The accuracy of the learned networks was consistently superior to that of corresponding networks learned without constraints. The exploitation of qualitative constraints therefore appears to be a promising way to increase both the interpretability and the accuracy of learned Bayesian networks with known structure.
Efficient Identification of Equivalences in Dynamic Graphs and Pedigree Structures
Venue: arXiv cs.DS 2013
Year: 2013

We propose a new framework for designing test and query functions for complex structures that vary across a given parameter such as genetic marker position. The operations we are interested in include equality testing, set operations, isolating unique states, duplication counting, or finding equivalence classes under identifiability constraints. A motivating application is locating equivalence classes in identity-by-descent (IBD) graphs, graph structures in pedigree analysis that change over genetic marker location. The nodes of these graphs are unlabeled and identified only by their connecting edges, a constraint easily handled by our approach. The general framework introduced is powerful enough to build a range of testing functions for IBD graphs, dynamic populations, and other structures using a minimal set of operations. The theoretical and algorithmic properties of our approach are analyzed and proved. Computational results on several simulations demonstrate the effectiveness of our approach.
Efficient Sample Reuse in Policy Gradients with Parameter-based Exploration
Venue: arXiv cs.LG 2013
Year: 2013

The policy gradient approach is a flexible and powerful reinforcement learning method particularly for problems with continuous actions such as robot control. A common challenge in this scenario is how to reduce the variance of policy gradient estimates for reliable policy updates. In this paper, we combine the following three ideas and give a highly effective policy gradient method: (a) the policy gradients with parameter based exploration, which is a recently proposed policy search method with low variance of gradient estimates, (b) an importance sampling technique, which allows us to reuse previously gathered data in a consistent way, and (c) an optimal baseline, which minimizes the variance of gradient estimates with their unbiasedness being maintained. For the proposed method, we give theoretical analysis of the variance of gradient estimates and show its usefulness through extensive experiments.
Another look at expurgated bounds and their statistical-mechanical interpretation
Venue: arXiv cs.IT 2013
Year: 2013

We revisit the derivation of expurgated error exponents using a method of type class enumeration, which is inspired by statistical-mechanical methods, and which has already been used in the derivation of random coding exponents in several other scenarios. We compare our version of the expurgated bound to both the one by Gallager and the one by Csiszar, Korner and Marton (CKM). For expurgated ensembles of fixed composition codes over finite alphabets, our basic expurgated bound coincides with the CKM expurgated bound, which is in general tighter than Gallager's bound, but with equality for the optimum type class of codewords. Our method, however, extends beyond fixed composition codes and beyond finite alphabets, where it is natural to impose input constraints (e.g., power limitation). In such cases, the CKM expurgated bound may not apply directly, and our bound is in general tighter than Gallager's bound. In addition, while both the CKM and the Gallager expurgated bounds are based on Bhattacharyya bound for bounding the pairwise error probabilities, our bound allows the more general Chernoff distance measure, thus giving rise to additional improvement using the Chernoff parameter as a degree of freedom to be optimized.
On the Product Rule for Classification Problems
Venue: arXiv cs.LG 2013
Year: 2013

We discuss theoretical aspects of the product rule for classification problems in supervised machine learning for the case of combining classifiers. We show that (1) the product rule arises from the MAP classifier supposing equivalent priors and conditional independence given a class; (2) under some conditions, the product rule is equivalent to minimizing the sum of the squared distances to the respective centers of the classes related with different features, such distances being weighted by the spread of the classes; (3) observing some hypothesis, the product rule is equivalent to concatenating the vectors of features.
DSAT-MAC : Dynamic Slot Allocation based TDMA MAC protocol for Cognitive Radio Networks
Venue: arXiv cs.NI 2013
Year: 2013

Cognitive Radio Networks (CRN) have enabled us to efficiently reuse the underutilized radio spectrum. The MAC protocol in CRN defines the spectrum usage by sharing the channels efficiently among users. In this paper we propose a novel TDMA based MAC protocol with dynamically allocated slots. Most of the MAC protocols proposed in the literature employ Common Control Channel (CCC) to manage the resources among Cognitive Radio (CR) users. Control channel saturation in case of large number of CR users is one of the main drawbacks of the CCC based MAC protocols. In contrast with CCC based MAC protocols, DSAT-MAC protocol is based on the TDMA mechanism, without using any CCC for control information exchange. The channels are divided into time slots and CR users send their control or data packets over their designated slot. The protocol ensures that no slot is left vacant. This guarantees full use of the available spectrum. The protocol includes the provision for Quality of Service, where real-time and safety critical data is transmitted with highest priority and least delay. The protocol also ensures a fair sharing of available spectrum among the CR users, with the mechanism to regulate the transmission of malicious nodes. Energy saving techniques are also presented for longer life of battery operated CR nodes. Theoretical analysis and simulations over ns-2 of the proposed protocol reveal that the protocol performs better in various CR adhoc network applications.
Storage codes -- coding rate and repair locality
Venue: arXiv cs.IT 2013
Year: 2013

The {\em repair locality} of a distributed storage code is the maximum number of nodes that ever needs to be contacted during the repair of a failed node. Having small repair locality is desirable, since it is proportional to the number of disk accesses during repair. However, recent publications show that small repair locality comes with a penalty in terms of code distance or storage overhead if exact repair is required. Here, we first review some of the main results on storage codes under various repair regimes and discuss the recent work on possible (information-theoretical) trade-offs between repair locality and other code parameters like storage overhead and code distance, under the exact repair regime. Then we present some new information theoretical lower bounds on the storage overhead as a function of the repair locality, valid for all common coding and repair models. In particular, we show that if each of the $n$ nodes in a distributed storage system has storage capacity $\ga$ and if, at any time, a failed node can be {\em functionally} repaired by contacting {\em some} set of $r$ nodes (which may depend on the actual state of the system) and downloading an amount $\gb$ of data from each, then in the extreme cases where $\ga=\gb$ or $\ga = r\gb$, the maximal coding rate is at most $r/(r+1)$ or 1/2, respectively (that is, the excess storage overhead is at least $1/r$ or 1, respectively).
Deriving program transformations by demonstration
Venue: arXiv cs.PL 2013
Year: 2013

Automatic code transformation in which transformations are tuned for specific applications and contexts are difficult to achieve in an accessible manner. In this paper, we present an approach to build application specific code transformations. Our approach is based on analysis of the abstract syntax representation of exemplars of the essential change to the code before and after the transformation is applied. This analysis entails a sequence of steps to identify the change, determine how to generalize it, and map it to term rewriting rules for the Stratego term rewriting system. The methods described in this paper assume programs are represented in a language-neutral term format, allowing tools based on our methods to be applied to programs written in the major languages used by computational scientists utilizing high performance computing systems.
Simultaneous computation of the row and column rank profiles
Venue: arXiv cs.NA 2013
Year: 2013

Gaussian elimination with full pivoting generates a PLUQ matrix decomposition. Depending on the strategy used in the search for pivots, the permutation matrices can reveal some information about the row or the column rank profiles of the matrix. We propose a new pivoting strategy that makes it possible to recover at the same time both row and column rank profiles of the input matrix and of any of its leading sub-matrices. We propose a rank-sensitive and quad-recursive algorithm that computes the latter PLUQ triangular decomposition of an m \times n matrix of rank r in O(mnr^{ω-2}) field operations, with ωthe exponent of matrix multiplication. Compared to the LEU decomposition by Malashonock, sharing a similar recursive structure, its time complexity is rank sensitive and has a lower leading constant. Over a word size finite field, this algorithm also improveLs the practical efficiency of previously known implementations.
Regional Consistency: Programmability and Performance for Non-Cache-Coherent Systems
Venue: arXiv cs.DC 2013
Year: 2013

Parallel programmers face the often irreconcilable goals of programmability and performance. HPC systems use distributed memory for scalability, thereby sacrificing the programmability advantages of shared memory programming models. Furthermore, the rapid adoption of heterogeneous architectures, often with non-cache-coherent memory systems, has further increased the challenge of supporting shared memory programming models. Our primary objective is to define a memory consistency model that presents the familiar thread-based shared memory programming model, but allows good application performance on non-cache-coherent systems, including distributed memory clusters and accelerator-based systems. We propose regional consistency (RegC), a new consistency model that achieves this objective. Results on up to 256 processors for representative benchmarks demonstrate the potential of RegC in the context of our prototype distributed shared memory system.
Requirements Management for Service Providers: the Case of Services for Citizens
Venue: arXiv cs.SE 2013
Year: 2013

Take the Internet of Things, a piece of cloud computing, a handful of smart cities, don't forget social platforms, flavour it with mobile technologies and ever-changing environments, shake it up and... voila! What a wonderful service! Oops! Wait a minute, where did my requirements go?
Schedulability Analysis of Distributed Real-Time Applications under Dependence and Several Latency Constraints
Venue: arXiv cs.OS 2013
Year: 2013

This paper focuses on the analysis of real-time non preemptive multiprocessor scheduling with precedence and several latency constraints. It aims to specify a schedulability condition which enables a designer to check a priori -without executing or simulating- if its scheduling of tasks will hold the precedences between tasks as well as several latency constraints imposed on determined pairs of tasks. It is shown that the required analysis is closely linked to the topological structure of the application graph. More precisely, it depends on the configuration of tasks paths subject to latency constraints. As a result of the study, a sufficient schedulability condition is introduced for precedences and latency constraints in the hardest configuration in term of complexity with an optimal number of processors in term of applications parallelism. In addition, the proposed conditions provides a practical lower bounds for general cases. Performances results and comparisons with an optimal approach demonstrate the effectiveness of the proposed approach.
The Hidden Structural Rules of the Discontinuous Lambek Calculus
Venue: arXiv cs.LO 2013
Year: 2013

The sequent calculus sL for the Lambek calculus L (lambek 58) has no structural rules. Interestingly, sL is equivalent to a multimodal calculus mL, which consists of the nonassociative Lambek calculus with the structural rule of associativity. This paper proves that the sequent calculus or hypersequent calculus hD of the discontinuous Lambek calculus (Morrill and Valentín), which like sL has no structural rules, is also equivalent to an omega-sorted multimodal calculus mD. More concretely, we present a faithful embedding translation between mD and hD in such a way that it can be said that hD absorbs the structural rules of mD.
Dirichlet draws are sparse with high probability
Venue: arXiv cs.LG 2013
Year: 2013

This note provides an elementary proof of the folklore fact that draws from a Dirichlet distribution (with parameters less than 1) are typically sparse (most coordinates are small).
From 9-IM Topological Operators to Qualitative Spatial Relations using 3D Selective Nef Complexes and Logic Rules for bodies
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents a method to compute automatically topological relations using SWRL rules. The calculation of these rules is based on the definition of a Selective Nef Complexes Nef Polyhedra structure generated from standard Polyhedron. The Selective Nef Complexes is a data model providing a set of binary Boolean operators such as Union, Difference, Intersection and Symmetric difference, and unary operators such as Interior, Closure and Boundary. In this work, these operators are used to compute topological relations between objects defined by the constraints of the 9 Intersection Model (9-IM) from Egenhofer. With the help of these constraints, we defined a procedure to compute the topological relations on Nef polyhedra. These topological relationships are Disjoint, Meets, Contains, Inside, Covers, CoveredBy, Equals and Overlaps, and defined in a top-level ontology with a specific semantic definition on relation such as Transitive, Symmetric, Asymmetric, Functional, Reflexive, and Irreflexive. The results of the computation of topological relationships are stored in an OWL-DL ontology allowing after what to infer on these new relationships between objects. In addition, logic rules based on the Semantic Web Rule Language allows the definition of logic programs that define which topological relationships have to be computed on which kind of objects with specific attributes. For instance, a "Building" that overlaps a "Railway" is a "RailStation".
A formalization of re-identification in terms of compatible probabilities
Venue: arXiv cs.CR 2013
Year: 2013

Re-identification algorithms are used in data privacy to measure disclosure risk. They model the situation in which an adversary attacks a published database by means of linking the information of this adversary with the database. In this paper we formalize this type of algorithm in terms of true probabilities and compatible belief functions. The purpose of this work is to leave aside as re-identification algorithms those algorithms that do not satisfy a minimum requirement.
On the Distribution of MIMO Mutual Information: An In-Depth Painlevé Based Characterization
Venue: arXiv cs.IT 2013
Year: 2013

This paper builds upon our recent work which computed the moment generating function of the MIMO mutual information exactly in terms of a Painlevé V differential equation. By exploiting this key analytical tool, we provide an in-depth characterization of the mutual information distribution for sufficiently large (but finite) antenna numbers. In particular, we derive systematic closed-form expansions for the high order cumulants. These results yield considerable new insight, such as providing a technical explanation as to why the well known Gaussian approximation is quite robust to large SNR for the case of unequal antenna arrays, whilst it deviates strongly for equal antenna arrays. In addition, by drawing upon our high order cumulant expansions, we employ the Edgeworth expansion technique to propose a refined Gaussian approximation which is shown to give a very accurate closed-form characterization of the mutual information distribution, both around the mean and for moderate deviations into the tails (where the Gaussian approximation fails remarkably). For stronger deviations where the Edgeworth expansion becomes unwieldy, we employ the saddle point method and asymptotic integration tools to establish new analytical characterizations which are shown to be very simple and accurate. Based on these results we also recover key well established properties of the tail distribution, including the diversity-multiplexing-tradeoff.
Connecting the Dots: Computer Systems Education using a Functional Hardware Description Language
Venue: arXiv cs.CY 2013
Year: 2013

A functional hardware description language enables students to gain a working understanding of computer systems, and to see how the levels of abstraction fit together. By simulating circuits, digital design becomes a living topic, like programming, and not just a set of inert facts to memorise. Experiences gained from more than 20 years of teaching computer systems via functional programming are discussed.
Balanced Sparsest Generator Matrices for MDS Codes
Venue: arXiv cs.IT 2013
Year: 2013

We show that given $n$ and $k$, for $q$ sufficiently large, there always exists an $[n, k]_q$ MDS code that has a generator matrix $G$ satisfying the following two conditions: (C1) Sparsest: each row of $G$ has Hamming weight $n - k + 1$; (C2) Balanced: Hamming weights of the columns of $G$ differ from each other by at most one.
"Seed+Expand": A validated methodology for creating high quality publication oeuvres of individual researchers
Venue: arXiv cs.DL 2013
Year: 2013

The study of science at the individual micro-level frequently requires the disambiguation of author names. The creation of author's publication oeuvres involves matching the list of unique author names to names used in publication databases. Despite recent progress in the development of unique author identifiers, e.g., ORCID, VIVO, or DAI, author disambiguation remains a key problem when it comes to large-scale bibliometric analysis using data from multiple databases. This study introduces and validates a new methodology called seed+expand for semi-automatic bibliographic data collection for a given set of individual authors. Specifically, we identify the oeuvre of a set of Dutch full professors during the period 1980-2011. In particular, we combine author records from the National Research Information System (NARCIS) with publication records from the Web of Science. Starting with an initial list of 8,378 names, we identify "seed publications" for each author using five different approaches. Subsequently, we "expand" the set of publication in three different approaches. The different approaches are compared and resulting oeuvres are evaluated on precision and recall using a "gold standard" dataset of authors for which verified publications in the period 2001-2010 are available.
Information systems security in special and public libraries: an assessment of status
Venue: arXiv cs.DL 2013
Year: 2013

Explores the use of an assessment instrument based on a model named library information systems security assessment model (LISSAM) to assess the 155 status in special and public libraries in Malaysia. The study aims to determine the implementation status of technological and organizational components of the LISSAM model. An implementation index as well as a scoring tool is presented to assess the IS safeguarding measures in a library. Data used was based on questionnaires distributed to a total of 50 individuals who are responsible for the information systems (IS) or IT in the special and public libraries in Malaysia. Findings revealed that over 95% of libraries have high level of technological implementation but 54% were fair poorly on organizational measures, especially on lack of security procedures, administrative tools and awareness creation activities.
Broadword Implementation of Parenthesis Queries
Venue: arXiv cs.DS 2013
Year: 2013

We continue the line of research started in "Broadword Implementation of Rank/Select Queries" proposing broadword (a.k.a. SWAR, "SIMD Within A Register") algorithms for finding matching closed parentheses and the k-th far closed parenthesis. Our algorithms work in time O(log w) on a word of w bits, and contain no branch and no test instruction. On 64-bit (and wider) architectures, these algorithms make it possible to avoid costly tabulations, while providing a very significant speedup with respect to for-loop implementations.