OpenRaiser/Intern-Atlas huggingface dataset:
New Variants of Pattern Matching with Constants and Variables
Venue: arXiv cs.DS 2017
Year: 2017

Given a text and a pattern over two types of symbols called constants and variables, the parameterized pattern matching problem is to find all occurrences of substrings of the text that the pattern matches by substituting a variable in the text for each variable in the pattern, where the substitution should be injective. The function matching problem is a variant of it that lifts the injection constraint. In this paper, we discuss variants of those problems, where one can substitute a constant or a variable for each variable of the pattern. We give two kinds of algorithms for both problems, a convolution-based method and an extended KMP-based method, and analyze their complexity.
Biomedical Event Trigger Identification Using Bidirectional Recurrent Neural Network Based Models
Venue: arXiv cs.CL 2017
Year: 2017

Biomedical events describe complex interactions between various biomedical entities. Event trigger is a word or a phrase which typically signifies the occurrence of an event. Event trigger identification is an important first step in all event extraction methods. However many of the current approaches either rely on complex hand-crafted features or consider features only within a window. In this paper we propose a method that takes the advantage of recurrent neural network (RNN) to extract higher level features present across the sentence. Thus hidden state representation of RNN along with word and entity type embedding as features avoid relying on the complex hand-crafted features generated using various NLP toolkits. Our experiments have shown to achieve state-of-art F1-score on Multi Level Event Extraction (MLEE) corpus. We have also performed category-wise analysis of the result and discussed the importance of various features in trigger identification task.
Inapproximability of VC Dimension and Littlestone's Dimension
Venue: arXiv cs.CC 2017
Year: 2017

We study the complexity of computing the VC Dimension and Littlestone's Dimension. Given an explicit description of a finite universe and a concept class (a binary matrix whose $(x,C)$-th entry is $1$ iff element $x$ belongs to concept $C$), both can be computed exactly in quasi-polynomial time ($n^{O(\log n)}$). Assuming the randomized Exponential Time Hypothesis (ETH), we prove nearly matching lower bounds on the running time, that hold even for approximation algorithms.
Logical and Inequality Implications for Reducing the Size and Complexity of Quadratic Unconstrained Binary Optimization Problems
Venue: arXiv cs.AI 2017
Year: 2017

The quadratic unconstrained binary optimization (QUBO) problem arises in diverse optimization applications ranging from Ising spin problems to classical problems in graph theory and binary discrete optimization. The use of preprocessing to transform the graph representing the QUBO problem into a smaller equivalent graph is important for improving solution quality and time for both exact and metaheuristic algorithms and is a step towards mapping large scale QUBO to hardware graphs used in quantum annealing computers. In an earlier paper (Lewis and Glover, 2016) a set of rules was introduced that achieved significant QUBO reductions as verified through computational testing. Here this work is extended with additional rules that provide further reductions that succeed in exactly solving 10% of the benchmark QUBO problems. An algorithm and associated data structures to efficiently implement the entire set of rules is detailed and computational experiments are reported that demonstrate their efficacy.
Concurrent self-adjusting distributed tree networks
Venue: arXiv cs.DC 2017
Year: 2017

SplayNets are a distributed generalization of the classic splay tree data structures. Given a set of communication requests and a network comprised of n nodes, such that any pair of nodes is capable of establishing a direct connection, the goal is to dynamically find a (locally routable) binary tree topology, which connects all nodes and optimizes the routing cost for that communication pattern, making local topology transformations (rotations) before each request is served. In this work we present a distributed and concurrent implementation of SplayNets. Analytical results show that our proposed algorithm prevents loops and deadlocks from occurring between concurrent rotations. We compute the total amortized average cost of a splay request in number of rounds and number of time-slots and as a function of the empirical entropies of source and destination nodes of the splay requests.
New Optimal Binary Sequences with Period $4p$ via Interleaving Ding-Helleseth-Lam Sequences
Venue: arXiv cs.IT 2017
Year: 2017

Binary sequences with optimal autocorrelation play important roles in radar, communication, and cryptography. Finding new binary sequences with optimal autocorrelation has been an interesting research topic in sequence design. Ding-Helleseth-Lam sequences are such a class of binary sequences of period $p$, where $p$ is an odd prime with $p\equiv 1(\bmod~4)$. The objective of this letter is to present a construction of binary sequences of period $4p$ via interleaving four suitable Ding-Helleseth-Lam sequences. This construction generates new binary sequences with optimal autocorrelation which can not be produced by earlier ones.
Multiresolution Priority Queues
Venue: arXiv cs.DS 2017
Year: 2017

Priority queues are container data structures essential to many high performance computing (HPC) applications. In this paper, we introduce multiresolution priority queues, a data structure that improves the performance of the standard heap based implementations by trading off a controllable amount of resolution in the space of priorities. The new data structure can reduce the worst case performance of inserting an element from O(log(n)) to O(log(r)), where n is the number of elements in the queue and r is the number of resolution groups in the priority space. The worst case cost of removing the top element is O(1). When the number of elements in the table is high, the amortized cost to insert an element becomes O(1).
Anomaly Detection in a Digital Video Broadcasting System Using Timed Automata
Venue: arXiv cs.LG 2017
Year: 2017

This paper focuses on detecting anomalies in a digital video broadcasting (DVB) system from providers' perspective. We learn a probabilistic deterministic real timed automaton profiling benign behavior of encryption control in the DVB control access system. This profile is used as a one-class classifier. Anomalous items in a testing sequence are detected when the sequence is not accepted by the learned model.
word2vec Skip-Gram with Negative Sampling is a Weighted Logistic PCA
Venue: arXiv cs.CL 2017
Year: 2017

We show that the skip-gram formulation of word2vec trained with negative sampling is equivalent to a weighted logistic PCA. This connection allows us to better understand the objective, compare it to other word embedding methods, and extend it to higher dimensional models.
Evolution of Social Power in Social Networks with Dynamic Topology
Venue: arXiv cs.SI 2017
Year: 2017

The recently proposed DeGroot-Friedkin model describes the dynamical evolution of individual social power in a social network that holds opinion discussions on a sequence of different issues. This paper revisits that model, and uses nonlinear contraction analysis, among other tools, to establish several novel results. First, we show that for a social network with constant topology, each individual's social power converges to its equilibrium value exponentially fast, whereas previous results only concluded asymptotic convergence. Second, when the network topology is dynamic (i.e., the relative interaction matrix may change between any two successive issues), we show that each individual exponentially forgets its initial social power. Specifically, individual social power is dependent only on the dynamic network topology, and initial (or perceived) social power is forgotten as a result of sequential opinion discussion. Last, we provide an explicit upper bound on an individual's social power as the number of issues discussed tends to infinity; this bound depends only on the network topology. Simulations are provided to illustrate our results.
KlusTree: Clustering Answer Trees from Keyword Search on Graphs
Venue: arXiv cs.IR 2017
Year: 2017

Graph structured data on the web is now massive as well as diverse, ranging from social networks, web graphs to knowledge-bases. Effectively querying this graph structured data is non-trivial and has led to research in a variety of directions -- structured queries, keyword and natural language queries, automatic translation of these queries to structured queries, etc. We are concerned with a class of queries called relationship queries, which are usually expressed as a set of keywords (each keyword denoting a named entity). The results returned are a set of ranked trees, each of which denotes relationships among the various keywords. The result list could consist of hundreds of answers. The problem of keyword search on graphs has been explored for over a decade now, but an important aspect that is not as extensively studied is that of user experience. We propose KlusTree, which presents clustered results to the users instead of a list of all the results. In our approach, the result trees are represented using language models and are clustered using JS divergence as a distance measure. We compare KlusTree with the well-known approaches based on isomorphism and tree-edit distance based clustering. The user evaluations show that KlusTree outperforms the other two in providing better clustering, thereby enriching user experience, revealing interesting patterns and improving result interpretation by the user.
On the relation between dependency distance, crossing dependencies, and parsing. Comment on "Dependency distance: a new perspective on syntactic patterns in natural languages" by Haitao Liu et al
Venue: arXiv cs.CL 2017
Year: 2017

Liu et al. (2017) provide a comprehensive account of research on dependency distance in human languages. While the article is a very rich and useful report on this complex subject, here I will expand on a few specific issues where research in computational linguistics (specifically natural language processing) can inform DDM research, and vice versa. These aspects have not been explored much in the article by Liu et al. or elsewhere, probably due to the little overlap between both research communities, but they may provide interesting insights for improving our understanding of the evolution of human languages, the mechanisms by which the brain processes and understands language, and the construction of effective computer systems to achieve this goal.
Quadratic Unconstrained Binary Optimization Problem Preprocessing: Theory and Empirical Analysis
Venue: arXiv cs.AI 2017
Year: 2017

The Quadratic Unconstrained Binary Optimization problem (QUBO) has become a unifying model for representing a wide range of combinatorial optimization problems, and for linking a variety of disciplines that face these problems. A new class of quantum annealing computer that maps QUBO onto a physical qubit network structure with specific size and edge density restrictions is generating a growing interest in ways to transform the underlying QUBO structure into an equivalent graph having fewer nodes and edges. In this paper we present rules for reducing the size of the QUBO matrix by identifying variables whose value at optimality can be predetermined. We verify that the reductions improve both solution quality and time to solution and, in the case of metaheuristic methods where optimal solutions cannot be guaranteed, the quality of solutions obtained within reasonable time limits. We discuss the general QUBO structural characteristics that can take advantage of these reduction techniques and perform careful experimental design and analysis to identify and quantify the specific characteristics most affecting reduction. The rules make it possible to dramatically improve solution times on a new set of problems using both the exact Cplex solver and a tabu search metaheuristic.
An RFID Based Generalized Integrated System for the Identification and Traceability of Products and Subsets in Enterprises
Venue: arXiv cs.CY 2017
Year: 2017

RFID tags are small electronic devices that can be used to identify objects and people. The present paper presents an RFID-based integrated system that has been developed to allow the identification and traceability of products and subsets in whatever activity field. Thus this system offers to the users the possibility to define their own information format to be stored in the transponder. The potential beneficiaries of this system are companies that activate in fields that lend themselves admirably to RFID technologies.
Continuous Video to Simple Signals for Swimming Stroke Detection with Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

In many sports, it is useful to analyse video of an athlete in competition for training purposes. In swimming, stroke rate is a common metric used by coaches; requiring a laborious labelling of each individual stroke. We show that using a Convolutional Neural Network (CNN) we can automatically detect discrete events in continuous video (in this case, swimming strokes). We create a CNN that learns a mapping from a window of frames to a point on a smooth 1D target signal, with peaks denoting the location of a stroke, evaluated as a sliding window. To our knowledge this process of training and utilizing a CNN has not been investigated before; either in sports or fundamental computer vision research. Most research has been focused on action recognition and using it to classify many clips in continuous video for action localisation. In this paper we demonstrate our process works well on the task of detecting swimming strokes in the wild. However, without modifying the model architecture or training method, the process is also shown to work equally well on detecting tennis strokes, implying that this is a general process. The outputs of our system are surprisingly smooth signals that predict an arbitrary event at least as accurately as humans (manually evaluated from a sample of negative results). A number of different architectures are evaluated, pertaining to slightly different problem formulations and signal targets.
Projection Theorems of Divergences and Likelihood Maximization Methods
Venue: arXiv cs.IT 2017
Year: 2017

Projection theorems of divergences enable us to find reverse projection of a divergence on a specific statistical model as a forward projection of the divergence on a different but rather "simpler" statistical model, which, in turn, results in solving a system of linear equations. Reverse projection of divergences are closely related to various estimation methods such as the maximum likelihood estimation or its variants in robust statistics. We consider projection theorems of three parametric families of divergences that are widely used in robust statistics, namely the Rényi divergences (or the Cressie-Reed power divergences), density power divergences, and the relative $α$-entropy (or the logarithmic density power divergences). We explore these projection theorems from the usual likelihood maximization approach and from the principle of sufficiency. In particular, we show the equivalence of solving the estimation problems by the projection theorems of the respective divergences and by directly solving the corresponding estimating equations. We also derive the projection theorem for the density power divergences.
Neural Semantic Parsing by Character-based Translation: Experiments with Abstract Meaning Representations
Venue: arXiv cs.CL 2017
Year: 2017

We evaluate the character-level translation method for neural semantic parsing on a large corpus of sentences annotated with Abstract Meaning Representations (AMRs). Using a sequence-to-sequence model, and some trivial preprocessing and postprocessing of AMRs, we obtain a baseline accuracy of 53.1 (F-score on AMR-triples). We examine five different approaches to improve this baseline result: (i) reordering AMR branches to match the word order of the input sentence increases performance to 58.3; (ii) adding part-of-speech tags (automatically produced) to the input shows improvement as well (57.2); (iii) So does the introduction of super characters (conflating frequent sequences of characters to a single character), reaching 57.4; (iv) optimizing the training process by using pre-training and averaging a set of models increases performance to 58.7; (v) adding silver-standard training data obtained by an off-the-shelf parser yields the biggest improvement, resulting in an F-score of 64.0. Combining all five techniques leads to an F-score of 71.0 on holdout data, which is state-of-the-art in AMR parsing. This is remarkable because of the relative simplicity of the approach.
User Selection and Widely Linear Multiuser Precoding for One-dimensional Signalling
Venue: arXiv cs.IT 2017
Year: 2017

Massive deployment of low data rate Internet of things and ehealth devices prompts us to develop more practical precoding and user selection techniques that comply with these requirements. Moreover, it is known that when the data is real-valued and the observation is complex-valued, widely linear (WL) estimation can be employed in lieu of linear estimation to improve the performance. With these motivations, in this paper, we study the transmit precoding (beamforming) in multiuser multiple-input single-output communications systems assuming the transmit signal is one-dimensionally modulated and widely linear estimation is performed at the receivers. Closed-form solutions for widely linear maximum ratio transmission (MRT), WL zero-forcing (ZF), WL minimum mean square error (MMSE), and WL maximum signal to leakage and noise ratio (MSLNR) precoding are obtained. It is shown that widely linear processing can potentially double the number of simultaneous users compared to the linear processing of one-dimensionally modulated signals. Furthermore, to deal with the increasing number of communications devices a user selection algorithm compatible with widely linear processing of one-dimensionally modulated signals is proposed. The proposed user selection algorithm can double the number of simultaneously selected users compared to conventional user selection methods.
VERIFAS: A Practical Verifier for Artifact Systems
Venue: arXiv cs.DB 2017
Year: 2017

Data-driven workflows, of which IBM's Business Artifacts are a prime exponent, have been successfully deployed in practice, adopted in industrial standards, and have spawned a rich body of research in academia, focused primarily on static analysis. The present research bridges the gap between the theory and practice of artifact verification with VERIFAS, the first implementation of practical significance of an artifact verifier with full support for unbounded data. VERIFAS verifies within seconds linear-time temporal properties over real-world and synthetic workflows of complexity in the range recommended by software engineering practice. Compared to our previous implementation based on the widely-used Spin model checker, VERIFAS not only supports a model with richer data manipulations but also outperforms it by over an order of magnitude. VERIFAS' good performance is due to a novel symbolic representation approach and a family of specialized optimizations.
Data Driven Coded Aperture Design for Depth Recovery
Venue: arXiv cs.CV 2017
Year: 2017

Inserting a patterned occluder at the aperture of a camera lens has been shown to improve the recovery of depth map and all-focus image compared to a fully open aperture. However, design of the aperture pattern plays a very critical role. Previous approaches for designing aperture codes make simple assumptions on image distributions to obtain metrics for evaluating aperture codes. However, real images may not follow those assumptions and hence the designed code may not be optimal for them. To address this drawback we propose a data driven approach for learning the optimal aperture pattern to recover depth map from a single coded image. We propose a two stage architecture where, in the first stage we simulate coded aperture images from a training dataset of all-focus images and depth maps and in the second stage we recover the depth map using a deep neural network. We demonstrate that our learned aperture code performs better than previously designed codes even on code design metrics proposed by previous approaches.
Rate $(n-1)/n$ Systematic MDS Convolutional Codes over $GF(2^m)$
Venue: arXiv cs.IT 2017
Year: 2017

A systematic convolutional encoder of rate $(n-1)/n$ and maximum degree $D$ generates a code of free distance at most ${\cal D} = D+2$ and, at best, a column distance profile (CDP) of $[2,3,\ldots,{\cal D}]$. A code is \emph{Maximum Distance Separable} (MDS) if it possesses this CDP. Applied on a communication channel over which packets are transmitted sequentially and which loses (erases) packets randomly, such a code allows the recovery from any pattern of $j$ erasures in the first $j$ $n$-packet blocks for $j<{\cal D}$, with a delay of at most $j$ blocks counting from the first erasure. This paper addresses the problem of finding the largest ${\cal D}$ for which a systematic rate $(n-1)/n$ code over $GF(2^m)$ exists, for given $n$ and $m$. In particular, constructions for rates $(2^m-1)/2^m$ and $(2^{m-1}-1)/2^{m-1}$ are presented which provide optimum values of ${\cal D}$ equal to 3 and 4, respectively. A search algorithm is also developed, which produces new codes for ${\cal D}$ for field sizes $2^m \leq 2^{14}$. Using a complete search version of the algorithm, the maximum value of ${\cal D}$, and codes that achieve it, are determined for all code rates $\geq 1/2$ and every field size $GF(2^m)$ for $m\leq 5$ (and for some rates for $m=6$).
Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs
Venue: arXiv cs.DS 2017
Year: 2017

In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph $G$ and a source node $s$ the goal is to maintain shortest distances between $s$ and all other nodes in $G$ under a sequence of online adversarial edge deletions. In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem in unweighted graphs with only $O(mn)$ total update time over all edge deletions. Their classic algorithm was the state of the art for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed. A series of results showed how to improve upon $O(mn)$ if approximation is allowed, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a $(1+ε)$-approximate algorithm for undirected weighted graphs whose total update time is near linear: $O(m^{1+o(1)}\log(W))$, where $W$ is the ratio of the heaviest to the lightest edge weight in the graph. In this paper they posed as a major open problem the question of derandomizing their result. Until very recently, all known improvements over the Even-Shiloach algorithm were randomized and required the assumption of a non-adaptive adversary. In STOC 2016, Bernstein and Chechik showed the first \emph{deterministic} algorithm to go beyond $O(mn)$ total update time: the algorithm is also $(1+ε)$-approximate, and has total update time $\tilde{O}(n^2)$. In SODA 2017, the same authors presented an algorithm with total update time $\tilde{O}(mn^{3/4})$. However, both algorithms are restricted to undirected, unweighted graphs. We present the \emph{first} deterministic algorithm for \emph{weighted} undirected graphs to go beyond the $O(mn)$ bound. The total update time is $\tilde{O}(n^2 \log(W))$.