OpenRaiser/Intern-Atlas huggingface dataset:
The Research Object Suite of Ontologies: Sharing and Exchanging Research Data and Methods on the Open Web
Venue: arXiv cs.DL 2014
Year: 2014

Research in life sciences is increasingly being conducted in a digital and online environment. In particular, life scientists have been pioneers in embracing new computational tools to conduct their investigations. To support the sharing of digital objects produced during such research investigations, we have witnessed in the last few years the emergence of specialized repositories, e.g., DataVerse and FigShare. Such repositories provide users with the means to share and publish datasets that were used or generated in research investigations. While these repositories have proven their usefulness, interpreting and reusing evidence for most research results is a challenging task. Additional contextual descriptions are needed to understand how those results were generated and/or the circumstances under which they were concluded. Because of this, scientists are calling for models that go beyond the publication of datasets to systematically capture the life cycle of scientific investigations and provide a single entry point to access the information about the hypothesis investigated, the datasets used, the experiments carried out, the results of the experiments, the people involved in the research, etc. In this paper we present the Research Object (RO) suite of ontologies, which provide a structured container to encapsulate research data and methods along with essential metadata descriptions. Research Objects are portable units that enable the sharing, preservation, interpretation and reuse of research investigation results. The ontologies we present have been designed in the light of requirements that we gathered from life scientists. They have been built upon existing popular vocabularies to facilitate interoperability. Furthermore, we have developed tools to support the creation and sharing of Research Objects, thereby promoting and facilitating their adoption.
Algorithmic Introduction of Quantified Cuts
Venue: arXiv cs.LO 2014
Year: 2014

We describe a method for inverting Gentzen's cut-elimination in classical first-order logic. Our algorithm is based on first computign a compressed representation of the terms present in the cut-free proof and then cut-formulas that realize such a compression. Finally, a proof using these cut-formulas is constructed. This method allows an exponential compression of proof length. It can be applied to the output of automated theorem provers, which typically produce analytic proofs. An implementation is available on the web and described in this paper.
Cause Identification from Aviation Safety Incident Reports via Weakly Supervised Semantic Lexicon Construction
Venue: arXiv cs.CL 2014
Year: 2014

The Aviation Safety Reporting System collects voluntarily submitted reports on aviation safety incidents to facilitate research work aiming to reduce such incidents. To effectively reduce these incidents, it is vital to accurately identify why these incidents occurred. More precisely, given a set of possible causes, or shaping factors, this task of cause identification involves identifying all and only those shaping factors that are responsible for the incidents described in a report. We investigate two approaches to cause identification. Both approaches exploit information provided by a semantic lexicon, which is automatically constructed via Thelen and Riloffs Basilisk framework augmented with our linguistic and algorithmic modifications. The first approach labels a report using a simple heuristic, which looks for the words and phrases acquired during the semantic lexicon learning process in the report. The second approach recasts cause identification as a text classification problem, employing supervised and transductive text classification algorithms to learn models from incident reports labeled with shaping factors and using the models to label unseen reports. Our experiments show that both the heuristic-based approach and the learning-based approach (when given sufficient training data) outperform the baseline system significantly.
YASCA: A collective intelligence approach for community detection in complex networks
Venue: arXiv cs.SI 2014
Year: 2014

In this paper we present an original approach for community detection in complex networks. The approach belongs to the family of seed-centric algorithms. However, instead of expanding communities around selected seeds as most of existing approaches do, we explore here applying an ensemble clustering approach to different network partitions derived from ego-centered communities computed for each selected seed. Ego-centered communities are themselves computed applying a recently proposed ensemble ranking based approach that allow to efficiently combine various local modularities used to guide a greedy optimisation process. Results of first experiments on real world networks for which a ground truth decomposition into communities are known, argue for the validity of our approach.
An Analysis of Random Projections in Cancelable Biometrics
Venue: arXiv cs.CV 2014
Year: 2014

With increasing concerns about security, the need for highly secure physical biometrics-based authentication systems utilizing \emph{cancelable biometric} technologies is on the rise. Because the problem of cancelable template generation deals with the trade-off between template security and matching performance, many state-of-the-art algorithms successful in generating high quality cancelable biometrics all have random projection as one of their early processing steps. This paper therefore presents a formal analysis of why random projections is an essential step in cancelable biometrics. By formally defining the notion of an \textit{Independent Subspace Structure} for datasets, it can be shown that random projection preserves the subspace structure of data vectors generated from a union of independent linear subspaces. The bound on the minimum number of random vectors required for this to hold is also derived and is shown to depend logarithmically on the number of data samples, not only in independent subspaces but in disjoint subspace settings as well. The theoretical analysis presented is supported in detail with empirical results on real-world face recognition datasets.
Polar Lattices for Strong Secrecy Over the Mod-$Λ$ Gaussian Wiretap Channel
Venue: arXiv cs.IT 2014
Year: 2014

Polar lattices, which are constructed from polar codes, are provably good for the additive white Gaussian noise (AWGN) channel. In this work, we propose a new polar lattice construction that achieves the secrecy capacity under the strong secrecy criterion over the mod-$Λ$ Gaussian wiretap channel. This construction leads to an AWGN-good lattice and a secrecy-good lattice simultaneously. The design methodology is mainly based on the equivalence in terms of polarization between the $Λ/Λ'$ channel in lattice coding and the equivalent channel derived from the chain rule of mutual information in multilevel coding.
Dialectica models of additive-free linear logic
Venue: arXiv cs.LO 2014
Year: 2014

This paper presents a construction which transforms categorical models of additive-free propositional linear logic, closely based on de Paiva's dialectica categories and Oliva's functional interpretations of classical linear logic. The construction is defined using dependent type theory, which proves to be a useful tool for reasoning about dialectica categories. Abstractly, we have a closure operator on the class of models: it preserves soundness and completeness and has a monad-like structure. When applied to categories of games we obtain `games with bidding', which are hybrids of dialectica and game models, and we prove completeness theorems for two specific such models.
Various Views on the Trapdoor Channel and an Upper Bound on its Capacity
Venue: arXiv cs.IT 2014
Year: 2014

Two novel views are presented on the trapdoor channel. First, by deriving the underlying iterated function system (IFS), it is shown that the trapdoor channel with input blocks of length $n$ can be regarded as the $n$th element of a sequence of shapes approximating a fractal. Second, an algorithm is presented that fully characterizes the trapdoor channel and resembles the recursion of generating all permutations of a given string. Subsequently, the problem of maximizing a $n$-letter mutual information is considered. It is shown that $\frac{1}{2}\log_2\left(\frac{5}{2}\right)\approx 0.6610$ bits per use is an upper bound on the capacity of the trapdoor channel. This upper bound, which is the tightest upper bound known proves that feedback increases capacity of the trapdoor channel.
Computing Approximate Nash Equilibria and Robust Best-Responses Using Sampling
Venue: arXiv cs.GT 2014
Year: 2014

This article discusses two contributions to decision-making in complex partially observable stochastic games. First, we apply two state-of-the-art search techniques that use Monte-Carlo sampling to the task of approximating a Nash-Equilibrium (NE) in such games, namely Monte-Carlo Tree Search (MCTS) and Monte-Carlo Counterfactual Regret Minimization (MCCFR). MCTS has been proven to approximate a NE in perfect-information games. We show that the algorithm quickly finds a reasonably strong strategy (but not a NE) in a complex imperfect information game, i.e. Poker. MCCFR on the other hand has theoretical NE convergence guarantees in such a game. We apply MCCFR for the first time in Poker. Based on our experiments, we may conclude that MCTS is a valid approach if one wants to learn reasonably strong strategies fast, whereas MCCFR is the better choice if the quality of the strategy is most important. Our second contribution relates to the observation that a NE is not a best response against players that are not playing a NE. We present Monte-Carlo Restricted Nash Response (MCRNR), a sample-based algorithm for the computation of restricted Nash strategies. These are robust best-response strategies that (1) exploit non-NE opponents more than playing a NE and (2) are not (overly) exploitable by other strategies. We combine the advantages of two state-of-the-art algorithms, i.e. MCCFR and Restricted Nash Response (RNR). MCRNR samples only relevant parts of the game tree. We show that MCRNR learns quicker than standard RNR in smaller games. Also we show in Poker that MCRNR learns robust best-response strategies fast, and that these strategies exploit opponents more than playing a NE does.
Dr.Fill: Crosswords and an Implemented Solver for Singly Weighted CSPs
Venue: arXiv cs.AI 2014
Year: 2014

We describe Dr.Fill, a program that solves American-style crossword puzzles. From a technical perspective, Dr.Fill works by converting crosswords to weighted CSPs, and then using a variety of novel techniques to find a solution. These techniques include generally applicable heuristics for variable and value selection, a variant of limited discrepancy search, and postprocessing and partitioning ideas. Branch and bound is not used, as it was incompatible with postprocessing and was determined experimentally to be of little practical value. Dr.Fillls performance on crosswords from the American Crossword Puzzle Tournament suggests that it ranks among the top fifty or so crossword solvers in the world.
Impact of Correlation between Nakagami-m Interferers on Coverage Probability and Rate in Cellular Systems
Venue: arXiv cs.IT 2014
Year: 2014

Coverage probability and rate expressions are theoretically compared for the following cases: $(i).$ Both the user channel and the $N$ interferers are independent and non identical Nakagami-m distributed random variables (RVs). $(ii).$ The $N$ interferers are correlated Nakagami-m RVs. It is analytically shown that the coverage probability in the presence of correlated interferers is greater than or equal to the coverage probability in the presence of non-identical independent interferers when the shape parameter of the channel between the user and its base station is not greater than one. It is further analytically shown that the average rate in the presence of correlated interferers is greater than or equal to the average rate in the presence of non-identical independent interferers. Simulation results are provided and these match with the obtained theoretical results. The utility of our results are also discussed.
Axioms for Definability and Full Completeness
Venue: arXiv cs.LO 2014
Year: 2014

Axioms are presented which encapsulate the properties satisfied by categories of games which form the basis of results on full abstraction for PCF and other programming languages, and on full completeness for various logics and type theories. Axioms are presented on models of PCF from which full abstraction can be proved. These axioms have been distilled from recent results on definability and full abstraction of game semantics for a number of programming languages. Full completeness for pure simply-typed $λ$-calculus is also axiomatized.
Finding minimum Tucker submatrices
Venue: arXiv cs.DS 2014
Year: 2014

A binary matrix has the Consecutive Ones Property (C1P) if its columns can be ordered in such a way that all 1s on each row are consecutive. These matrices are used for DNA physical mapping and ancestral genome reconstruction in computational biology on the other hand they represents a class of convex bipartite graphs and are of interest of algorithm graph theory researchers. Tucker gave a forbidden submartices characterization of matrices that have C1P property in 1972. Booth and Lucker (1976) gave a first linear time recognition algorithm for matrices with C1P property and then in 2002, Habib, et al. gave a simpler linear time recognition algorithm. There has been substantial amount of works on efficiently finding minimum size forbidden submatrix. Our algorithm is at least $n$ times faster than the existing algorithm where $n$ is the number of columns of the input matrix.
LDPC Codes for Partial-Erasure Channels in Multi-Level Memories
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we develop a new channel model, which we name the $q$-ary partial erasure channel (QPEC). QPEC has a $q$-ary input, and its output is either one symbol or a set of $M$ possible values. This channel mimics situations when current/voltage levels in measurement channels are only partially known, due to high read rates or imperfect current/voltage sensing. Our investigation is concentrated on the performance of low-density parity-pheck (LDPC) codes when used over this channel, due to their low decoding complexity with iterative-decoding algorithms. We give the density evolution equations of this channel, and develop its decoding-threshold analysis. Part of the analysis shows that finding the exact decoding threshold efficiently lies upon a solution to an open problem in additive combinatorics. For this part we give bounds and approximations.
Approximate Capacities of Two-Dimensional Codes by Spatial Mixing
Venue: arXiv cs.IT 2014
Year: 2014

We apply several state-of-the-art techniques developed in recent advances of counting algorithms and statistical physics to study the spatial mixing property of the two-dimensional codes arising from local hard (independent set) constraints, including: hard-square, hard-hexagon, read/write isolated memory (RWIM), and non-attacking kings (NAK). For these constraints, the strong spatial mixing would imply the existence of polynomial-time approximation scheme (PTAS) for computing the capacity. It was previously known for the hard-square constraint the existence of strong spatial mixing and PTAS. We show the existence of strong spatial mixing for hard-hexagon and RWIM constraints by establishing the strong spatial mixing along self-avoiding walks, and consequently we give PTAS for computing the capacities of these codes. We also show that for the NAK constraint, the strong spatial mixing does not hold along self-avoiding walks.
On Low-Complexity Full-diversity Detection In Multi-User MIMO Multiple-Access Channels
Venue: arXiv cs.IT 2014
Year: 2014

Multiple-input multiple-output (MIMO) techniques are becoming commonplace in recent wireless communication standards. This added dimension (i.e., space) can be efficiently used to mitigate the interference in the multi-user MIMO context. In this paper, we focus on the uplink of a MIMO multiple access channel (MAC) where perfect channel state information (CSI) is only available at the destination. We provide a new set of sufficient conditions for a wide range of space-time block codes (STBC)s to achieve full-diversity under \emph{partial interference cancellation group decoding} (PICGD) with or without successive interference cancellation (SIC) for completely blind users. Explicit interference cancellation (IC) schemes for two and three users are then provided and shown to satisfy the derived full-diversity criteria. Besides the complexity reduction due to the fact that the proposed IC schemes enable separate decoding of distinct users without sacrificing the diversity gain, further reduction of the decoding complexity may be obtained. In fact, thanks to the structure of the proposed schemes, the real and imaginary parts of each user's symbols may be decoupled without any loss of performance. Finally, our theoretical claims are corroborated by simulation results and the new IC scheme for two-user MIMO MAC is shown to outperform the recently proposed two-user IC scheme especially for high spectral efficiency while requiring significantly less decoding complexity.
An Evolutionary Approach towards Clustering Airborne Laser Scanning Data
Venue: arXiv cs.NE 2014
Year: 2014

In land surveying, the generation of maps was greatly simplified with the introduction of orthophotos and at a later stage with airborne LiDAR laser scanning systems. While the original purpose of LiDAR systems was to determine the altitude of ground elevations, newer full wave systems provide additional information that can be used on classifying the type of ground cover and the generation of maps. The LiDAR resulting point clouds are huge, multidimensional data sets that need to be grouped in classes of ground cover. We propose a genetic algorithm that aids in classifying these data sets and thus make them usable for map generation. A key feature are tailor-made genetic operators and fitness functions for the subject. The algorithm is compared to a traditional k-means clustering.
Impact of Transceiver Power Consumption on the Energy Efficiency of Zero-Forcing Detector in Massive MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

We consider the impact of transceiver power consumption on the energy efficiency (EE) of the Zero Forcing (ZF) detector in the uplink of massive MIMO systems, where a base station (BS) with $M$ antennas communicates coherently with $K$ single antenna user terminals (UTs). We consider the problem of maximizing the EE with respect to (M,K) for a fixed sum spectral efficiency. Through analysis we study the impact of system parameters on the optimal EE. System parameters consists of the average channel gain to the users and the power consumption parameters (PCPs) (e.g., power consumed by each RF antenna/receiver at BS). When the average user channel gain is high or else the BS/UT design is power inefficient, our analysis reveals that it is optimal to have a few BS antennas and a single user, i.e., non-massive MIMO regime. Similarly, when the channel gain is small or else the BS/UT design is power efficient, it is optimal of have a larger (M,K), i.e., massive MIMO regime. Tight analytical bounds on the optimal EE are proposed for both these regimes. The impact of the system parameters on the optimal EE is studied and several interesting insights are drawn.
Constructing Fewer Open Cells by GCD Computation in CAD Projection
Venue: arXiv cs.SC 2014
Year: 2014

A new projection operator based on cylindrical algebraic decomposition (CAD) is proposed. The new operator computes the intersection of projection factor sets produced by different CAD projection orders. In other words, it computes the gcd of projection polynomials in the same variables produced by different CAD projection orders. We prove that the new operator still guarantees obtaining at least one sample point from every connected component of the highest dimension, and therefore, can be used for testing semi-definiteness of polynomials. Although the complexity of the new method is still doubly exponential, in many cases, the new operator does produce smaller projection factor sets and fewer open cells. Some examples of testing semi-definiteness of polynomials, which are difficult to be solved by existing tools, have been worked out efficiently by our program based on the new method.
Achieving SK Capacity in the Source Model: When Must All Terminals Talk?
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we address the problem of characterizing the instances of the multiterminal source model of Csiszár and Narayan in which communication from all terminals is needed for establishing a secret key of maximum rate. We give an information-theoretic sufficient condition for identifying such instances. We believe that our sufficient condition is in fact an exact characterization, but we are only able to prove this in the case of the three-terminal source model. We also give a relatively simple criterion for determining whether or not our condition holds for a given multiterminal source model.
Büchi Types for Infinite Traces and Liveness
Venue: arXiv cs.LO 2014
Year: 2014

We develop a new type and effect system based on Büchi automata to capture finite and infinite traces produced by programs in a small language which allows non-deterministic choices and infinite recursions. There are two key technical contributions: (a) an abstraction based on equivalence relations defined by the policy Büchi automaton, the Büchi abstraction; (b) a novel type and effect system to correctly capture infinite traces. We show how the Büchi abstraction fits into the abstract interpretation framework and show soundness and completeness.
An Identification System Using Eye Detection Based On Wavelets And Neural Networks
Venue: arXiv cs.CV 2014
Year: 2014

The randomness and uniqueness of human eye patterns is a major breakthrough in the search for quicker, easier and highly reliable forms of automatic human identification. It is being used extensively in security solutions. This includes access control to physical facilities, security systems and information databases, Suspect tracking, surveillance and intrusion detection and by various Intelligence agencies through out the world. We use the advantage of human eye uniqueness to identify people and approve its validity as a biometric. . Eye detection involves first extracting the eye from a digital face image, and then encoding the unique patterns of the eye in such a way that they can be compared with pre-registered eye patterns. The eye detection system consists of an automatic segmentation system that is based on the wavelet transform, and then the Wavelet analysis is used as a pre-processor for a back propagation neural network with conjugate gradient learning. The inputs to the neural network are the wavelet maxima neighborhood coefficients of face images at a particular scale. The output of the neural network is the classification of the input into an eye or non-eye region. An accuracy of 90% is observed for identifying test images under different conditions included in training stage.