OpenRaiser/Intern-Atlas huggingface dataset:
String Inference from the LCP Array
Venue: arXiv cs.DS 2017
Year: 2017

The suffix array, perhaps the most important data structure in modern string processing, is often augmented with the longest common prefix (LCP) array which stores the lengths of the LCPs for lexicographically adjacent suffixes of a string. Together the two arrays are roughly equivalent to the suffix tree with the LCP array representing the tree shape. In order to better understand the combinatorics of LCP arrays, we consider the problem of inferring a string from an LCP array, i.e., determining whether a given array of integers is a valid LCP array, and if it is, reconstructing some string or all strings with that LCP array. There are recent studies of inferring a string from a suffix tree shape but using significantly more information (in the form of suffix links) than is available in the LCP array. We provide two main results. (1) We describe two algorithms for inferring strings from an LCP array when we allow a generalized form of LCP array defined for a multiset of cyclic strings: a linear time algorithm for binary alphabet and a general algorithm with polynomial time complexity for a constant alphabet size. (2) We prove that determining whether a given integer array is a valid LCP array is NP-complete when we require more restricted forms of LCP array defined for a single cyclic or non-cyclic string or a multiset of non-cyclic strings. The result holds whether or not the alphabet is restricted to be binary. In combination, the two results show that the generalized form of LCP array for a multiset of cyclic strings is fundamentally different from the other more restricted forms.
Throughput Maximization for Decode-and-Forward Relay Channels with Non-Ideal Circuit Power
Venue: arXiv cs.IT 2017
Year: 2017

This paper studies the throughput maximization problem for a three-node relay channel with non-ideal circuit power. In particular, the relay operates in a half-duplex manner, and the decode-and-forward (DF) relaying scheme is adopted. Considering the extra power consumption by the circuits, the optimal power allocation to maximize the throughput of the considered system over an infinite time horizon is investigated. First, two special scenarios, i.e., the direct link transmission (only use the direct link to transmit) and the relay assisted transmission (the source and the relay transmit with equal probability), are studied, and the corresponding optimal power allocations are obtained. By transforming two non-convex problems into quasiconcave ones, the closed-form solutions show that the source and the relay transmit with certain probability, which is determined by the average power budgets, circuit power consumptions, and channel gains. Next, based on the above results, the optimal power allocation for both the cases with and without direct link is derived, which is shown to be a mixed transmission scheme between the direct link transmission and the relay assisted transmission.
Reconstructing a Bounded-Degree Directed Tree Using Path Queries
Venue: arXiv cs.DS 2017
Year: 2017

We present a randomized algorithm for reconstructing directed rooted trees of $n$ nodes and node degree at most $d$, by asking at most $O(dn\log^2 n)$ path queries. Each path query takes as input an origin node and a target node, and answers whether there is a directed path from the origin to the target. Regarding lower bounds, we show that any randomized algorithm requires at least $Ω(n\log n)$ queries, while any deterministic algorithm requires at least $Ω(dn)$ queries. Additionally, we present a $O(dn\log^3 n)$ randomized algorithm for noisy queries, and a $O(dn\log^2 n)$ randomized algorithm for additive queries on weighted trees.
FVQA: Fact-based Visual Question Answering
Venue: arXiv cs.CV 2017
Year: 2017

Visual Question Answering (VQA) has attracted a lot of attention in both Computer Vision and Natural Language Processing communities, not least because it offers insight into the relationships between two important sources of information. Current datasets, and the models built upon them, have focused on questions which are answerable by direct analysis of the question and image alone. The set of such questions that require no external information to answer is interesting, but very limited. It excludes questions which require common sense, or basic factual knowledge to answer, for example. Here we introduce FVQA, a VQA dataset which requires, and supports, much deeper reasoning. FVQA only contains questions which require external information to answer. We thus extend a conventional visual question answering dataset, which contains image-question-answerg triplets, through additional image-question-answer-supporting fact tuples. The supporting fact is represented as a structural triplet, such as <Cat,CapableOf,ClimbingTrees>. We evaluate several baseline models on the FVQA dataset, and describe a novel model which is capable of reasoning about an image on the basis of supporting facts.
Past, Present, and Future of Simultaneous Localization And Mapping: Towards the Robust-Perception Age
Venue: arXiv cs.RO 2017
Year: 2017

Simultaneous Localization and Mapping (SLAM)consists in the concurrent construction of a model of the environment (the map), and the estimation of the state of the robot moving within it. The SLAM community has made astonishing progress over the last 30 years, enabling large-scale real-world applications, and witnessing a steady transition of this technology to industry. We survey the current state of SLAM. We start by presenting what is now the de-facto standard formulation for SLAM. We then review related work, covering a broad set of topics including robustness and scalability in long-term mapping, metric and semantic representations for mapping, theoretical performance guarantees, active SLAM and exploration, and other new frontiers. This paper simultaneously serves as a position paper and tutorial to those who are users of SLAM. By looking at the published research with a critical eye, we delineate open challenges and new research issues, that still deserve careful scientific investigation. The paper also contains the authors' take on two questions that often animate discussions during robotics conferences: Do robots need SLAM? and Is SLAM solved?
Mining Local Process Models
Venue: arXiv cs.DB 2017
Year: 2017

In this paper we describe a method to discover frequent behavioral patterns in event logs. We express these patterns as \emph{local process models}. Local process model mining can be positioned in-between process discovery and episode / sequential pattern mining. The technique presented in this paper is able to learn behavioral patterns involving sequential composition, concurrency, choice and loop, like in process mining. However, we do not look at start-to-end models, which distinguishes our approach from process discovery and creates a link to episode / sequential pattern mining. We propose an incremental procedure for building local process models capturing frequent patterns based on so-called process trees. We propose five quality dimensions and corresponding metrics for local process models, given an event log. We show monotonicity properties for some quality dimensions, enabling a speedup of local process model discovery through pruning. We demonstrate through a real life case study that mining local patterns allows us to get insights in processes where regular start-to-end process discovery techniques are only able to learn unstructured, flower-like, models.
DualNet: Domain-Invariant Network for Visual Question Answering
Venue: arXiv cs.CV 2017
Year: 2017

Visual question answering (VQA) task not only bridges the gap between images and language, but also requires that specific contents within the image are understood as indicated by linguistic context of the question, in order to generate the accurate answers. Thus, it is critical to build an efficient embedding of images and texts. We implement DualNet, which fully takes advantage of discriminative power of both image and textual features by separately performing two operations. Building an ensemble of DualNet further boosts the performance. Contrary to common belief, our method proved effective in both real images and abstract scenes, in spite of significantly different properties of respective domain. Our method was able to outperform previous state-of-the-art methods in real images category even without explicitly employing attention mechanism, and also outperformed our own state-of-the-art method in abstract scenes category, which recently won the first place in VQA Challenge 2016.
Optimal Scheduling of Reliability-Constrained Relaying System under Outdated CSI in the Finite Blocklength Regime
Venue: arXiv cs.IT 2017
Year: 2017

Under the assumption of outdated channel state information (CSI) at the source, we consider the finite blocklength (FBL) throughput of a two-hop relaying system. Previous work has considered this setting so far only for the infinite blocklength case, where decoding can be arbitrarily reliable as long as operating below the Shannon limit. In contrast, in the FBL regime residual decoding errors can not be avoided even when transmitting below the Shannon limit. This makes the scheduling problem at the source more vulnerable to transmission errors, where we investigate the trade-off between the choice of so called scheduling weights to avoid transmission errors and the resulting coding rate. We show that the corresponding maximization of the throughput under a reliability constraint can be solved efficiently by iterative algorithms. Nevertheless, the optimal solution requires a recomputation of the scheduling weights prior to each transmission. Thus, we also study heuristics relying on choosing the scheduling weights only once. Through numerical analysis, we first provide insights on the structure of the throughout under different scheduling weights and channel correlation coefficients. We then turn to the comparison of the optimal scheduling with the heuristic and show that the performance gap between them is only significant for relay systems with high average signal-to-noise ratios (SNR) on the backhaul and relaying link. In particular, the optimal scheduling scheme provides most value in case that the data transmission is subject to strict reliability constraints, justifying the significant additional computational burden.
An artificial neural network to find correlation patterns in an arbitrary number of variables
Venue: arXiv cs.LG 2017
Year: 2017

Methods to find correlation among variables are of interest to many disciplines, including statistics, machine learning, (big) data mining and neurosciences. Parameters that measure correlation between two variables are of limited utility when used with multiple variables. In this work, I propose a simple criterion to measure correlation among an arbitrary number of variables, based on a data set. The central idea is to i) design a function of the variables that can take different forms depending on a set of parameters, ii) calculate the difference between a statistics associated to the function computed on the data set and the same statistics computed on a randomised version of the data set, called "scrambled" data set, and iii) optimise the parameters to maximise this difference. Many such functions can be organised in layers, which can in turn be stacked one on top of the other, forming a neural network. The function parameters are searched with an enhanced genetic algortihm called POET and the resulting method is tested on a cancer gene data set. The method may have potential implications for some issues that affect the field of neural networks, such as overfitting, the need to process huge amounts of data for training and the presence of "adversarial examples".
Crowdsourcing for Identification of Polyp-Free Segments in Virtual Colonoscopy Videos
Venue: arXiv cs.HC 2017
Year: 2017

Virtual colonoscopy (VC) allows a physician to virtually navigate within a reconstructed 3D colon model searching for colorectal polyps. Though VC is widely recognized as a highly sensitive and specific test for identifying polyps, one limitation is the reading time, which can take over 30 minutes per patient. Large amounts of the colon are often devoid of polyps, and a way of identifying these polyp-free segments could be of valuable use in reducing the required reading time for the interrogating radiologist. To this end, we have tested the ability of the collective crowd intelligence of non-expert workers to identify polyp candidates and polyp-free regions. We presented twenty short videos flying through a segment of a virtual colon to each worker, and the crowd was asked to determine whether or not a possible polyp was observed within that video segment. We evaluated our framework on Amazon Mechanical Turk and found that the crowd was able to achieve a sensitivity of 80.0% and specificity of 86.5% in identifying video segments which contained a clinically proven polyp. Since each polyp appeared in multiple consecutive segments, all polyps were in fact identified. Using the crowd results as a first pass, 80% of the video segments could in theory be skipped by the radiologist, equating to a significant time savings and enabling more VC examinations to be performed.
Divergent discourse between protests and counter-protests: #BlackLivesMatter and #AllLivesMatter
Venue: arXiv cs.CL 2017
Year: 2017

Since the shooting of Black teenager Michael Brown by White police officer Darren Wilson in Ferguson, Missouri, the protest hashtag #BlackLivesMatter has amplified critiques of extrajudicial killings of Black Americans. In response to #BlackLivesMatter, other Twitter users have adopted #AllLivesMatter, a counter-protest hashtag whose content argues that equal attention should be given to all lives regardless of race. Through a multi-level analysis of over 860,000 tweets, we study how these protests and counter-protests diverge by quantifying aspects of their discourse. We find that #AllLivesMatter facilitates opposition between #BlackLivesMatter and hashtags such as #PoliceLivesMatter and #BlueLivesMatter in such a way that historically echoes the tension between Black protesters and law enforcement. In addition, we show that a significant portion of #AllLivesMatter use stems from hijacking by #BlackLivesMatter advocates. Beyond simply injecting #AllLivesMatter with #BlackLivesMatter content, these hijackers use the hashtag to directly confront the counter-protest notion of "All lives matter." Our findings suggest that Black Lives Matter movement was able to grow, exhibit diverse conversations, and avoid derailment on social media by making discussion of counter-protest opinions a central topic of #AllLivesMatter, rather than the movement itself.
Energy Efficiency in Multiuser Transmission Over Parallel Frequency Channels
Venue: arXiv cs.IT 2017
Year: 2017

Energy efficiency is an important design criterion for wireless communications. When parallel frequency channels are used for multiuser transmission, the channel bandwidths and user power are adjusted to maximize the sum information rate with the bandwidth budget, the transmit power budget, and the user-specific rate requirements. The maximum sum rate is used in measuring the energy efficiency. With fixed or flexible bandwidths of the frequency channels, practical methods are developed to find the total transmit power with the unique optimal resource (bandwidth and power) allocation for maximum energy efficiency. This resource allocation ensures that, while each user's minimum rate requirement is satisfied, all the excess resource of the spectrum and transmit power is dedicated to the one user with the best channel quality. Simulation results validate the optimal solutions of total transmit power and resource allocation that support the energy-efficient multiuser transmission.
Low Power Wide Area Networks: An Overview
Venue: arXiv cs.NI 2017
Year: 2017

Low Power Wide Area (LPWA) networks are attracting a lot of attention primarily because of their ability to offer affordable connectivity to the low-power devices distributed over very large geographical areas. In realizing the vision of the Internet of Things (IoT), LPWA technologies complement and sometimes supersede the conventional cellular and short range wireless technologies in performance for various emerging smart city and machine-to-machine (M2M) applications. This review paper presents the design goals and the techniques, which different LPWA technologies exploit to offer wide-area coverage to low-power devices at the expense of low data rates. We survey several emerging LPWA technologies and the standardization activities carried out by different standards development organizations (e.g., IEEE, IETF, 3GPP, ETSI) as well as the industrial consortia built around individual LPWA technologies (e.g., LORa Alliance,WEIGHTLESS-SIG, and DASH7 Alliance). We further note that LPWA technologies adopt similar approaches, thus sharing similar limitations and challenges. This paper expands on these research challenges and identifies potential directions to address them. While the proprietary LPWA technologies are already hitting the market with large nationwide roll-outs, this paper encourages an active engagement of the research community in solving problems that will shape the connectivity of tens of billions of devices in the next decade.
Satisfying Real-world Goals with Dataset Constraints
Venue: arXiv cs.LG 2017
Year: 2017

The goal of minimizing misclassification error on a training set is often just one of several real-world goals that might be defined on different datasets. For example, one may require a classifier to also make positive predictions at some specified rate for some subpopulation (fairness), or to achieve a specified empirical recall. Other real-world goals include reducing churn with respect to a previously deployed model, or stabilizing online training. In this paper we propose handling multiple goals on multiple datasets by training with dataset constraints, using the ramp penalty to accurately quantify costs, and present an efficient algorithm to approximately optimize the resulting non-convex constrained optimization problem. Experiments on both benchmark and real-world industry datasets demonstrate the effectiveness of our approach.
Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
Venue: arXiv cs.DS 2017
Year: 2017

In this paper we give a f-approximation algorithm for the minimum unweighted Vertex Cover problem with Hard Capacity constraints (VCHC) on f-hypergraphs. This problem generalizes standard vertex cover for which the best known approximation ratio is also f and cannot be improved assuming the unique game conjecture. Our result is therefore essentially the best possible. This improves over the previous 2.155 (for f=2) and 2f-approximation algorithms by Cheung, Goemans and Wong (CGW). At the heart of our approach is to apply iterative rounding to the problem with ideas coming from several previous works. We also give a faster implementation of the method based on certain iteratively rounding the solution to certain CGW-style covering LPs. We note that independent of this work, Kao [#kao2017iterative] also recently obtained the same result.
STransE: a novel embedding model of entities and relationships in knowledge bases
Venue: arXiv cs.CL 2017
Year: 2017

Knowledge bases of real-world facts about entities and their relationships are useful resources for a variety of natural language processing tasks. However, because knowledge bases are typically incomplete, it is useful to be able to perform link prediction or knowledge base completion, i.e., predict whether a relationship not in the knowledge base is likely to be true. This paper combines insights from several previous link prediction models into a new embedding model STransE that represents each entity as a low-dimensional vector, and each relation by two matrices and a translation vector. STransE is a simple combination of the SE and TransE models, but it obtains better link prediction performance on two benchmark datasets than previous embedding models. Thus, STransE can serve as a new baseline for the more complex models in the link prediction task.
Two-way relay beamforming optimization for full-duplex SWIPT systems
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we investigate the problem of two-way relay beamforming optimization to maximize the achievable sum-rate of a simultaneous wireless information and power transfer (SWIPT) system with a full-duplex (FD) multiple-input multiple-output (MIMO) amplify-and-forward (AF) relay. In particular, we address the optimal joint design of the receiver power splitting (PS) ratio and the beamforming matrix at the relay node given the channel state information (CSI). Our contribution is an iterative algorithm based on difference of convex (DC) programming and one-dimensional searching to achieve the joint optimal solution. Simulation results are provided to demonstrate the effectiveness of the proposed algorithm.
SCTL: Towards Combining Model Checking and Proof Checking
Venue: arXiv cs.LO 2017
Year: 2017

Model checking and automated theorem proving are two pillars of formal methods. This paper investigates model checking from an automated theorem proving perspective, aiming at combining the expressiveness of automated theorem proving and the complete automaticity of model checking. The focus of this paper is on the verification of temporal logic properties of Kripke models. The main contributions of this paper are: first the definition of an extended computation tree logic that allows polyadic predicate symbols, then a proof system for this logic, taking Kripke models as parameters, then, the design of a proof-search algorithm for this calculus and a new automated theorem prover to implement it. The verification process is completely automatic, and produces either a counterexample when the property does not hold, or a certificate when it does. The experimental result compares well to existing state-of-the-art tools on some benchmarks, including an application to air traffic control and the design choices that lead to this efficiency are discussed.
knor: A NUMA-Optimized In-Memory, Distributed and Semi-External-Memory k-means Library
Venue: arXiv cs.DC 2017
Year: 2017

k-means is one of the most influential and utilized machine learning algorithms. Its computation limits the performance and scalability of many statistical analysis and machine learning tasks. We rethink and optimize k-means in terms of modern NUMA architectures to develop a novel parallelization scheme that delays and minimizes synchronization barriers. The \textit{k-means NUMA Optimized Routine} (\textsf{knor}) library has (i) in-memory (\textsf{knori}), (ii) distributed memory (\textsf{knord}), and (iii) semi-external memory (\textsf{knors}) modules that radically improve the performance of k-means for varying memory and hardware budgets. \textsf{knori} boosts performance for single machine datasets by an order of magnitude or more. \textsf{knors} improves the scalability of k-means on a memory budget using SSDs. \textsf{knors} scales to billions of points on a single machine, using a fraction of the resources that distributed in-memory systems require. \textsf{knord} retains \textsf{knori}'s performance characteristics, while scaling in-memory through distributed computation in the cloud. \textsf{knor} modifies Elkan's triangle inequality pruning algorithm such that we utilize it on billion-point datasets without the significant memory overhead of the original algorithm. We demonstrate \textsf{knor} outperforms distributed commercial products like H$_2$O, Turi (formerly Dato, GraphLab) and Spark's MLlib by more than an order of magnitude for datasets of $10^7$ to $10^9$ points.