OpenRaiser/Intern-Atlas huggingface dataset:
Fence - An Efficient Parser with Ambiguity Support for Model-Driven Language Specification
Venue: arXiv cs.CL 2011
Year: 2011

Model-based language specification has applications in the implementation of language processors, the design of domain-specific languages, model-driven software development, data integration, text mining, natural language processing, and corpus-based induction of models. Model-based language specification decouples language design from language processing and, unlike traditional grammar-driven approaches, which constrain language designers to specific kinds of grammars, it needs general parser generators able to deal with ambiguities. In this paper, we propose Fence, an efficient bottom-up parsing algorithm with lexical and syntactic ambiguity support that enables the use of model-based language specification in practice.
The PITA System: Tabling and Answer Subsumption for Reasoning under Uncertainty
Venue: arXiv cs.AI 2011
Year: 2011

Many real world domains require the representation of a measure of uncertainty. The most common such representation is probability, and the combination of probability with logic programs has given rise to the field of Probabilistic Logic Programming (PLP), leading to languages such as the Independent Choice Logic, Logic Programs with Annotated Disjunctions (LPADs), Problog, PRISM and others. These languages share a similar distribution semantics, and methods have been devised to translate programs between these languages. The complexity of computing the probability of queries to these general PLP programs is very high due to the need to combine the probabilities of explanations that may not be exclusive. As one alternative, the PRISM system reduces the complexity of query answering by restricting the form of programs it can evaluate. As an entirely different alternative, Possibilistic Logic Programs adopt a simpler metric of uncertainty than probability. Each of these approaches -- general PLP, restricted PLP, and Possibilistic Logic Programming -- can be useful in different domains depending on the form of uncertainty to be represented, on the form of programs needed to model problems, and on the scale of the problems to be solved. In this paper, we show how the PITA system, which originally supported the general PLP language of LPADs, can also efficiently support restricted PLP and Possibilistic Logic Programs. PITA relies on tabling with answer subsumption and consists of a transformation along with an API for library functions that interface with answer subsumption.
Diffeomorphic Metric Mapping of High Angular Resolution Diffusion Imaging based on Riemannian Structure of Orientation Distribution Functions
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, we propose a novel large deformation diffeomorphic registration algorithm to align high angular resolution diffusion images (HARDI) characterized by orientation distribution functions (ODFs). Our proposed algorithm seeks an optimal diffeomorphism of large deformation between two ODF fields in a spatial volume domain and at the same time, locally reorients an ODF in a manner such that it remains consistent with the surrounding anatomical structure. To this end, we first review the Riemannian manifold of ODFs. We then define the reorientation of an ODF when an affine transformation is applied and subsequently, define the diffeomorphic group action to be applied on the ODF based on this reorientation. We incorporate the Riemannian metric of ODFs for quantifying the similarity of two HARDI images into a variational problem defined under the large deformation diffeomorphic metric mapping (LDDMM) framework. We finally derive the gradient of the cost function in both Riemannian spaces of diffeomorphisms and the ODFs, and present its numerical implementation. Both synthetic and real brain HARDI data are used to illustrate the performance of our registration algorithm.
An iterative feature selection method for GRNs inference by exploring topological properties
Venue: arXiv cs.CV 2011
Year: 2011

An important problem in bioinformatics is the inference of gene regulatory networks (GRN) from temporal expression profiles. In general, the main limitations faced by GRN inference methods is the small number of samples with huge dimensionalities and the noisy nature of the expression measurements. In face of these limitations, alternatives are needed to get better accuracy on the GRNs inference problem. This work addresses this problem by presenting an alternative feature selection method that applies prior knowledge on its search strategy, called SFFS-BA. The proposed search strategy is based on the Sequential Floating Forward Selection (SFFS) algorithm, with the inclusion of a scale-free (Barabási-Albert) topology information in order to guide the search process to improve inference. The proposed algorithm explores the scale-free property by pruning the search space and using a power law as a weight for reducing it. In this way, the search space traversed by the SFFS-BA method combines a breadth-first search when the number of combinations is small (<k> <= 2) with a depth-first search when the number of combinations becomes explosive (<k> >= 3), being guided by the scale-free prior information. Experimental results show that the SFFS-BA provides a better inference similarities than SFS and SFFS, keeping the robustness of the SFS and SFFS methods, thus presenting very good results.
On Combining Linear-Based Strategies for Tabled Evaluation of Logic Programs
Venue: arXiv cs.LO 2011
Year: 2011

Tabled evaluation is a recognized and powerful technique that overcomes some limitations of traditional Prolog systems in dealing with recursion and redundant sub-computations. We can distinguish two main categories of tabling mechanisms: suspension-based tabling and linear tabling. While suspension-based mechanisms are considered to obtain better results in general, they have more memory space requirements and are more complex and harder to implement than linear tabling mechanisms. Arguably, the SLDT and DRA strategies are the two most successful extensions to standard linear tabled evaluation. In this work, we propose a new strategy, named DRS, and we present a framework, on top of the Yap system, that supports the combination of all these three strategies. Our implementation shares the underlying execution environment and most of the data structures used to implement tabling in Yap. We thus argue that all these common features allows us to make a first and fair comparison between these different linear tabling strategies and, therefore, better understand the advantages and weaknesses of each, when used solely or combined with the others.
The Magic of Logical Inference in Probabilistic Programming
Venue: arXiv cs.LO 2011
Year: 2011

Today, many different probabilistic programming languages exist and even more inference mechanisms for these languages. Still, most logic programming based languages use backward reasoning based on SLD resolution for inference. While these methods are typically computationally efficient, they often can neither handle infinite and/or continuous distributions, nor evidence. To overcome these limitations, we introduce distributional clauses, a variation and extension of Sato's distribution semantics. We also contribute a novel approximate inference method that integrates forward reasoning with importance sampling, a well-known technique for probabilistic inference. To achieve efficiency, we integrate two logic programming techniques to direct forward sampling. Magic sets are used to focus on relevant parts of the program, while the integration of backward reasoning allows one to identify and avoid regions of the sample space that are inconsistent with the evidence.
Fast multi-scale edge-detection in medical ultrasound signals
Venue: arXiv cs.CV 2011
Year: 2011

In this article we suggest a fast multi-scale edge-detection scheme for medical ultrasound signals. The edge-detector is based on well-known properties of the continuous wavelet trans- form. To achieve both good localization of edges and detect only significant edges, we study the maxima-lines of the wavelet transform. One can obtain the maxima-lines between two scales by computing the wavelet transform at several intermediate scales. To reduce computational effort and time we suggest a time-scale filtering procedure which uses only few scales to connect modulus-maxima across time-scale plane. The design of this procedure is based on a study of maxima-lines corresponding to edges typical for medical ultrasound signals. This study allows us to construct an algorithm for medical ultrasound signals which meets the demand for speed, but not on expense of reliability. The edge-detection algorithm has been applied to a large class of medical ultrasound sig- nals including tumour-, liver- and artery-images. Our results show that the proposed algorithm effectively detects major features in such signals, including edges with low contrast.
Submodular Optimization for Efficient Semi-supervised Support Vector Machines
Venue: arXiv cs.LG 2011
Year: 2011

In this work we present a quadratic programming approximation of the Semi-Supervised Support Vector Machine (S3VM) problem, namely approximate QP-S3VM, that can be efficiently solved using off the shelf optimization packages. We prove that this approximate formulation establishes a relation between the low density separation and the graph-based models of semi-supervised learning (SSL) which is important to develop a unifying framework for semi-supervised learning methods. Furthermore, we propose the novel idea of representing SSL problems as submodular set functions and use efficient submodular optimization algorithms to solve them. Using this new idea we develop a representation of the approximate QP-S3VM as a maximization of a submodular set function which makes it possible to optimize using efficient greedy algorithms. We demonstrate that the proposed methods are accurate and provide significant improvement in time complexity over the state of the art in the literature.
A Practical Approach to Polar Codes
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we study polar codes from a practical point of view. In particular, we study concatenated polar codes and rate-compatible polar codes. First, we propose a concatenation scheme including polar codes and Low-Density Parity-Check (LDPC) codes. We will show that our proposed scheme outperforms conventional concatenation schemes formed by LDPC and Reed-Solomon (RS) codes. We then study two rate-compatible coding schemes using polar codes. We will see that polar codes can be designed as universally capacity achieving rate-compatible codes over a set of physically degraded channels. We also study the effect of puncturing on polar codes to design rate-compatible codes.
Edge-coloring series-parallel multigraphs
Venue: arXiv cs.DS 2011
Year: 2011

We give a simpler proof of Seymour's Theorem on edge-coloring series-parallel multigraphs and derive a linear-time algorithm to check whether a given series-parallel multigraph can be colored with a given number of colors.
Controlling wheelchairs by body motions: A learning framework for the adaptive remapping of space
Venue: arXiv cs.RO 2011
Year: 2011

Learning to operate a vehicle is generally accomplished by forming a new cognitive map between the body motions and extrapersonal space. Here, we consider the challenge of remapping movement-to-space representations in survivors of spinal cord injury, for the control of powered wheelchairs. Our goal is to facilitate this remapping by developing interfaces between residual body motions and navigational commands that exploit the degrees of freedom that disabled individuals are most capable to coordinate. We present a new framework for allowing spinal cord injured persons to control powered wheelchairs through signals derived from their residual mobility. The main novelty of this approach lies in substituting the more common joystick controllers of powered wheelchairs with a sensor shirt. This allows the whole upper body of the user to operate as an adaptive joystick. Considerations about learning and risks have lead us to develop a safe testing environment in 3D Virtual Reality. A Personal Augmented Reality Immersive System (PARIS) allows us to analyse learning skills and provide users with an adequate training to control a simulated wheelchair through the signals generated by body motions in a safe environment. We provide a description of the basic theory, of the development phases and of the operation of the complete system. We also present preliminary results illustrating the processing of the data and supporting of the feasibility of this approach.
A structured alternative to Prolog with simple compositional semantics
Venue: arXiv cs.PL 2011
Year: 2011

Prolog's very useful expressive power is not captured by traditional logic programming semantics, due mainly to the cut and goal and clause order. Several alternative semantics have been put forward, exposing operational details of the computation state. We propose instead to redesign Prolog around structured alternatives to the cut and clauses, keeping the expressive power and computation model but with a compositional denotational semantics over much simpler states-just variable bindings. This considerably eases reasoning about programs, by programmers and tools such as a partial evaluator, with safe unfolding of calls through predicate definitions. An if-then-else across clauses replaces most uses of the cut, but the cut's full power is achieved by an until construct. Disjunction, conjunction and until, along with unification, are the primitive goal types with a compositional semantics yielding sequences of variable-binding solutions. This extends to programs via the usual technique of a least fixpoint construction. A simple interpreter for Prolog in the alternative language, and a definition of until in Prolog, establish the identical expressive power of the two languages. Many useful control constructs are derivable from the primitives, and the semantic framework illuminates the discussion of alternative ones. The formalisation rests on a term language with variable abstraction as in the λ-calculus. A clause is an abstraction on the call arguments, a continuation, and the local variables. It can be inclusive or exclusive, expressing a local case bound to a continuation by either a disjunction or an if-then-else. Clauses are open definitions, composed (and closed) with simple functional application (β-reduction). This paves the way for a simple account of flexible module composition mechanisms. Cube, a concrete language with the exposed principles, has been implemented.
Scalable and Secure Aggregation in Distributed Networks
Venue: arXiv cs.DC 2011
Year: 2011

We consider the problem of computing an aggregation function in a \emph{secure} and \emph{scalable} way. Whereas previous distributed solutions with similar security guarantees have a communication cost of $O(n^3)$, we present a distributed protocol that requires only a communication complexity of $O(n\log^3 n)$, which we prove is near-optimal. Our protocol ensures perfect security against a computationally-bounded adversary, tolerates $(1/2-ε)n$ malicious nodes for any constant $1/2 > ε> 0$ (not depending on $n$), and outputs the exact value of the aggregated function with high probability.
HyFlex: A Benchmark Framework for Cross-domain Heuristic Search
Venue: arXiv cs.AI 2011
Year: 2011

Automating the design of heuristic search methods is an active research field within computer science, artificial intelligence and operational research. In order to make these methods more generally applicable, it is important to eliminate or reduce the role of the human expert in the process of designing an effective methodology to solve a given computational search problem. Researchers developing such methodologies are often constrained on the number of problem domains on which to test their adaptive, self-configuring algorithms; which can be explained by the inherent difficulty of implementing their corresponding domain specific software components. This paper presents HyFlex, a software framework for the development of cross-domain search methodologies. The framework features a common software interface for dealing with different combinatorial optimisation problems, and provides the algorithm components that are problem specific. In this way, the algorithm designer does not require a detailed knowledge the problem domains, and thus can concentrate his/her efforts in designing adaptive general-purpose heuristic search algorithms. Four hard combinatorial problems are fully implemented (maximum satisfiability, one dimensional bin packing, permutation flow shop and personnel scheduling), each containing a varied set of instance data (including real-world industrial applications) and an extensive set of problem specific heuristics and search operators. The framework forms the basis for the first International Cross-domain Heuristic Search Challenge (CHeSC), and it is currently in use by the international research community. In summary, HyFlex represents a valuable new benchmark of heuristic search generality, with which adaptive cross-domain algorithms are being easily developed, and reliably compared.
A Invertible Dimension Reduction of Curves on a Manifold
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, we propose a novel lower dimensional representation of a shape sequence. The proposed dimension reduction is invertible and computationally more efficient in comparison to other related works. Theoretically, the differential geometry tools such as moving frame and parallel transportation are successfully adapted into the dimension reduction problem of high dimensional curves. Intuitively, instead of searching for a global flat subspace for curve embedding, we deployed a sequence of local flat subspaces adaptive to the geometry of both of the curve and the manifold it lies on. In practice, the experimental results of the dimension reduction and reconstruction algorithms well illustrate the advantages of the proposed theoretical innovation.
Trusted Network Selection using SAW and TOPSIS Algorithms for Heterogeneous Wireless Networks
Venue: arXiv cs.NI 2011
Year: 2011

Seamless continuity is the main goal in fourth generation Wireless networks (FGWNs), to achieve this "HANDOVER" technique is used, when a mobile terminal(MT) is in overlapping area for service continuity, Handover mechanism are mainly used. In Heterogeneous wireless networks main challenge is continual connection among the different networks like WiFi, WiMax, WLAN, WPAN etc. In this paper, Vertical handover decision schemes are compared and Multi Attribute Decision Making (MADM) is used to choose the best network from the available Visitor networks (VTs) for the continuous connection by the mobile terminal. In our work we mainly concentrated to the handover decision phase and to reduce the processing delay in the period of handover. MADM algorithms SAW and TOPSIS where compared to reduce the processing delay by using NS2 to evaluate the parameters for processing delay.
On the Correctness of Pull-Tabbing
Venue: arXiv cs.PL 2011
Year: 2011

Pull-tabbing is an evaluation approach for functional logic computations, based on a graph transformation recently proposed, which avoids making irrevocable non-deterministic choices that would jeopardize the completeness of computations. In contrast to other approaches with this property, it does not require an upfront cloning of a possibly large portion of the choice's context. We formally define the pull-tab transformation, characterize the class of programs for which the transformation is intended, extend the computations in these programs to include the transformation, and prove the correctness of the extended computations.
FIFA World Cup 2010: A Network Analysis of the Champion Team Play
Venue: arXiv cs.SI 2011
Year: 2011

We analyze the pass network among the players of the Spanish team (the world champion in the FIFA World Cup 2010), with the objective of explaining the results obtained from the behavior at the complex network level. The team is considered a network with players as nodes and passes as (directed) edges, and a temporal analysis of the resulting passes network is done, looking at the number of passes, length of the chain of passes, and the centrality of players in the turf. Results of the last three matches indicate that the clustering coefficient of the pass network increases with time, and stays high, indicating possession by Spanish players, which eventually leads to victory, even as the density of the pass network decreases with time.
Small witnesses, accepting lassos and winning strategies in omega-automata and games
Venue: arXiv cs.LO 2011
Year: 2011

Obtaining accepting lassos, witnesses and winning strategies in omega-automata and games with omega-regular winning conditions is an integral part of many formal methods commonly found in practice today. Despite the fact that in most applications, the lassos, witnesses and strategies found should be as small as possible, little is known about the hardness of obtaining small such certificates. In this paper, we survey the known hardness results and complete the complexity landscape for the cases not considered in the literature so far. We pay particular attention to the approximation hardness of the problems as approximate small solutions usually suffice in practice.
Using Java for distributed computing in the Gaia satellite data processing
Venue: arXiv cs.CE 2011
Year: 2011

In recent years Java has matured to a stable easy-to-use language with the flexibility of an interpreter (for reflection etc.) but the performance and type checking of a compiled language. When we started using Java for astronomical applications around 1999 they were the first of their kind in astronomy. Now a great deal of astronomy software is written in Java as are many business applications. We discuss the current environment and trends concerning the language and present an actual example of scientific use of Java for high-performance distributed computing: ESA's mission Gaia. The Gaia scanning satellite will perform a galactic census of about 1000 million objects in our galaxy. The Gaia community has chosen to write its processing software in Java. We explore the manifold reasons for choosing Java for this large science collaboration. Gaia processing is numerically complex but highly distributable, some parts being embarrassingly parallel. We describe the Gaia processing architecture and its realisation in Java. We delve into the astrometric solution which is the most advanced and most complex part of the processing. The Gaia simulator is also written in Java and is the most mature code in the system. This has been successfully running since about 2005 on the supercomputer "Marenostrum" in Barcelona. We relate experiences of using Java on a large shared machine. Finally we discuss Java, including some of its problems, for scientific computing.