OpenRaiser/Intern-Atlas huggingface dataset:
Substochastic Monte Carlo Algorithms
Venue: arXiv cs.DS 2017
Year: 2017

In this paper we introduce and formalize Substochastic Monte Carlo (SSMC) algorithms. These algorithms, originally intended to be a better classical foil to quantum annealing than simulated annealing, prove to be worthy optimization algorithms in their own right. In SSMC, a population of walkers is initialized according to a known distribution on an arbitrary search space and varied into the solution of some optimization problem of interest. The first argument of this paper shows how an existing classical algorithm, "Go-With-The-Winners" (GWW), is a limiting case of SSMC when restricted to binary search and particular driving dynamics. Although limiting to GWW, SSMC is more general. We show that (1) GWW can be efficiently simulated within the SSMC framework, (2) SSMC can be exponentially faster than GWW, (3) by naturally incorporating structural information, SSMC can exponentially outperform the quantum algorithm that first inspired it, and (4) SSMC exhibits desirable search features in general spaces. Our approach combines ideas from genetic algorithms (GWW), theoretical probability (Fleming-Viot processes), and quantum computing. Not only do we demonstrate that SSMC is often more efficient than competing algorithms, but we also hope that our results connecting these disciplines will impact each independently. An implemented version of SSMC has previously enjoyed some success as a competitive optimization algorithm for Max-$k$-SAT.
Understanding and Detecting Supporting Arguments of Diverse Types
Venue: arXiv cs.CL 2017
Year: 2017

We investigate the problem of sentence-level supporting argument detection from relevant documents for user-specified claims. A dataset containing claims and associated citation articles is collected from online debate website idebate.org. We then manually label sentence-level supporting arguments from the documents along with their types as study, factual, opinion, or reasoning. We further characterize arguments of different types, and explore whether leveraging type information can facilitate the supporting arguments detection task. Experimental results show that LambdaMART (Burges, 2010) ranker that uses features informed by argument types yields better performance than the same ranker trained without type information.
Charting the Complexity Landscape of Waypoint Routing
Venue: arXiv cs.NI 2017
Year: 2017

Modern computer networks support interesting new routing models in which traffic flows from a source s to a destination t can be flexibly steered through a sequence of waypoints, such as (hardware) middleboxes or (virtualized) network functions, to create innovative network services like service chains or segment routing. While the benefits and technological challenges of providing such routing models have been articulated and studied intensively over the last years, much less is known about the underlying algorithmic traffic routing problems. This paper shows that the waypoint routing problem features a deep combinatorial structure, and we establish interesting connections to several classic graph theoretical problems. We find that the difficulty of the waypoint routing problem depends on the specific setting, and chart a comprehensive landscape of the computational complexity. In particular, we derive several NP-hardness results, but we also demonstrate that exact polynomial-time algorithms exist for a wide range of practically relevant scenarios.
Safe Trajectory Synthesis for Autonomous Driving in Unforeseen Environments
Venue: arXiv cs.SY 2017
Year: 2017

Path planning for autonomous vehicles in arbitrary environments requires a guarantee of safety, but this can be impractical to ensure in real-time when the vehicle is described with a high-fidelity model. To address this problem, this paper develops a method to perform trajectory design by considering a low-fidelity model that accounts for model mismatch. The presented method begins by computing a conservative Forward Reachable Set (FRS) of a high-fidelity model's trajectories produced when tracking trajectories of a low-fidelity model over a finite time horizon. At runtime, the vehicle intersects this FRS with obstacles in the environment to eliminate trajectories that can lead to a collision, then selects an optimal plan from the remaining safe set. By bounding the time for this set intersection and subsequent path selection, this paper proves a lower bound for the FRS time horizon and sensing horizon to guarantee safety. This method is demonstrated in simulation using a kinematic Dubin's car as the low-fidelity model and a dynamic unicycle as the high-fidelity model.
Xorshift random number generators from primitive polynomials
Venue: arXiv cs.CR 2017
Year: 2017

A class of xorshift random number generators (RNGs) are introduced by Marsaglia. We have proposed an algorithm which constructs a full period xorshift RNG from a given primitive polynomial. It is shown there is a weakness present in those RNGs and is suggested its improvement. A separate algorithm is also proposed which returns a full period xorshift generator with desired number of xorshift operations.%We also introduce the notion of tweaked primitive multiple-recursive matrix method with improved linear complexity.
Branch-and-Bound Precoding for Multiuser MIMO Systems with 1-Bit Quantization
Venue: arXiv cs.IT 2017
Year: 2017

Multiple-antenna systems is a key technique to serve multiple users in future wireless systems. For low energy consumption and hardware complexity we first consider transmit symbols with constant magnitude and then 1-bit digital-to-analog converters. We propose precoding designs which maximize the minimum distance to the decision threshold at the receiver. The precoding design with 1-bit DAC corresponds to a discrete optimization problem, which we solve exactly with a branch-and-bound strategy. We alternatively present an approximation based on relaxation. Our results show that the proposed branch-and-bound approach has polynomial complexity. The proposed methods outperform existing precoding methods with 1-bit DAC in terms of uncoded bit error rate and sum-rate. The performance loss in comparison to infinite DAC resolution is small.
Cnvlutin2: Ineffectual-Activation-and-Weight-Free Deep Neural Network Computing
Venue: arXiv cs.LG 2017
Year: 2017

We discuss several modifications and extensions over the previous proposed Cnvlutin (CNV) accelerator for convolutional and fully-connected layers of Deep Learning Network. We first describe different encodings of the activations that are deemed ineffectual. The encodings have different memory overhead and energy characteristics. We propose using a level of indirection when accessing activations from memory to reduce their memory footprint by storing only the effectual activations. We also present a modified organization that detects the activations that are deemed as ineffectual while fetching them from memory. This is different than the original design that instead detected them at the output of the preceding layer. Finally, we present an extended CNV that can also skip ineffectual weights.
Online Learning with Automata-based Expert Sequences
Venue: arXiv cs.LG 2017
Year: 2017

We consider a general framework of online learning with expert advice where regret is defined with respect to sequences of experts accepted by a weighted automaton. Our framework covers several problems previously studied, including competing against k-shifting experts. We give a series of algorithms for this problem, including an automata-based algorithm extending weighted-majority and more efficient algorithms based on the notion of failure transitions. We further present efficient algorithms based on an approximation of the competitor automaton, in particular n-gram models obtained by minimizing the \infty-Rényi divergence, and present an extensive study of the approximation properties of such models. Finally, we also extend our algorithms and results to the framework of sleeping experts.
Extending and Improving Wordnet via Unsupervised Word Embeddings
Venue: arXiv cs.CL 2017
Year: 2017

This work presents an unsupervised approach for improving WordNet that builds upon recent advances in document and sense representation via distributional semantics. We apply our methods to construct Wordnets in French and Russian, languages which both lack good manual constructions.1 These are evaluated on two new 600-word test sets for word-to-synset matching and found to improve greatly upon synset recall, outperforming the best automated Wordnets in F-score. Our methods require very few linguistic resources, thus being applicable for Wordnet construction in low-resources languages, and may further be applied to sense clustering and other Wordnet improvements.
Multi-dueling Bandits with Dependent Arms
Venue: arXiv cs.LG 2017
Year: 2017

The dueling bandits problem is an online learning framework for learning from pairwise preference feedback, and is particularly well-suited for modeling settings that elicit subjective or implicit human feedback. In this paper, we study the problem of multi-dueling bandits with dependent arms, which extends the original dueling bandits setting by simultaneously dueling multiple arms as well as modeling dependencies between arms. These extensions capture key characteristics found in many real-world applications, and allow for the opportunity to develop significantly more efficient algorithms than were possible in the original setting. We propose the \selfsparring algorithm, which reduces the multi-dueling bandits problem to a conventional bandit setting that can be solved using a stochastic bandit algorithm such as Thompson Sampling, and can naturally model dependencies using a Gaussian process prior. We present a no-regret analysis for multi-dueling setting, and demonstrate the effectiveness of our algorithm empirically on a wide range of simulation settings.
Testing the science/technology relationship by analysis of patent citations of scientific papers after decomposition of both science and technology
Venue: arXiv cs.DL 2017
Year: 2017

The relationship of scientific knowledge development to technological development is widely recognized as one of the most important and complex aspects of technological evolution. This paper adds to our understanding of the relationship through use of a more rigorous structure for differentiating among technologies based upon technological domains (defined as consisting of the artifacts over time that fulfill a specific generic function using a specific body of technical knowledge).
High Performance Data Persistence in Non-Volatile Memory for Resilient High Performance Computing
Venue: arXiv cs.DC 2017
Year: 2017

Resilience is a major design goal for HPC. Checkpoint is the most common method to enable resilient HPC. Checkpoint periodically saves critical data objects to non-volatile storage to enable data persistence. However, using checkpoint, we face dilemmas between resilience, recomputation and checkpoint cost. The reason that accounts for the dilemmas is the cost of data copying inherent in checkpoint. In this paper we explore how to build resilient HPC with non-volatile memory (NVM) as main memory and address the dilemmas. We introduce a variety of optimization techniques that leverage high performance and non-volatility of NVM to enable high performance data persistence for data objects in applications. With NVM we avoid data copying; we optimize cache flushing needed to ensure consistency between caches and NVM. We demonstrate that using NVM is feasible to establish data persistence frequently with small overhead (4.4% on average) to achieve highly resilient HPC and minimize recomputation.
Topologically Robust 3D Shape Matching via Gradual Deflation and Inflation
Venue: arXiv cs.GR 2017
Year: 2017

Despite being vastly ignored in the literature, coping with topological noise is an issue of increasing importance, especially as a consequence of the increasing number and diversity of 3D polygonal models that are captured by devices of different qualities or synthesized by algorithms of different stabilities. One approach for matching 3D shapes under topological noise is to replace the topology-sensitive geodesic distance with distances that are less sensitive to topological changes. We propose an alternative approach utilising gradual deflation (or inflation) of the shape volume, of which purpose is to bring the pair of shapes to be matched to a \emph{comparable} topology before the search for correspondences. Illustrative experiments using different datasets demonstrate that as the level of topological noise increases, our approach outperforms the other methods in the literature.
Denominator Bounds for Systems of Recurrence Equations using $ΠΣ$-Extensions
Venue: arXiv cs.SC 2017
Year: 2017

We consider linear systems of recurrence equations whose coefficients are given in terms of indefinite nested sums and products covering, e.g., the harmonic numbers, hypergeometric products, $q$-hypergeometric products or their mixed versions. These linear systems are formulated in the setting of $ΠΣ$-extensions and our goal is to find a denominator bound (also known as universal denominator) for the solutions; i.e., a non-zero polynomial $d$ such that the denominator of every solution of the system divides $d$. This is the first step in computing all rational solutions of such a rather general recurrence system. Once the denominator bound is known, the problem of solving for rational solutions is reduced to the problem of solving for polynomial solutions.
Automated Recurrence Analysis for Almost-Linear Expected-Runtime Bounds
Venue: arXiv cs.PL 2017
Year: 2017

We consider the problem of developing automated techniques for solving recurrence relations to aid the expected-runtime analysis of programs. Several classical textbook algorithms have quite efficient expected-runtime complexity, whereas the corresponding worst-case bounds are either inefficient (e.g., QUICK-SORT), or completely ineffective (e.g., COUPON-COLLECTOR). Since the main focus of expected-runtime analysis is to obtain efficient bounds, we consider bounds that are either logarithmic, linear, or almost-linear ($\mathcal{O}(\log n)$, $\mathcal{O}(n)$, $\mathcal{O}(n\cdot\log n)$, respectively, where n represents the input size). Our main contribution is an efficient (simple linear-time algorithm) sound approach for deriving such expected-runtime bounds for the analysis of recurrence relations induced by randomized algorithms. Our approach can infer the asymptotically optimal expected-runtime bounds for recurrences of classical randomized algorithms, including RANDOMIZED-SEARCH, QUICK-SORT, QUICK-SELECT, COUPONCOLLECTOR, where the worst-case bounds are either inefficient (such as linear as compared to logarithmic of expected-runtime, or quadratic as compared to linear or almost-linear of expected-runtime), or ineffective. We have implemented our approach, and the experimental results show that we obtain the bounds efficiently for the recurrences of various classical algorithms.
An Order-based Algorithm for Minimum Dominating Set with Application in Graph Mining
Venue: arXiv cs.SI 2017
Year: 2017

Dominating set is a set of vertices of a graph such that all other vertices have a neighbour in the dominating set. We propose a new order-based randomised local search (RLS$_o$) algorithm to solve minimum dominating set problem in large graphs. Experimental evaluation is presented for multiple types of problem instances. These instances include unit disk graphs, which represent a model of wireless networks, random scale-free networks, as well as samples from two social networks and real-world graphs studied in network science. Our experiments indicate that RLS$_o$ performs better than both a classical greedy approximation algorithm and two metaheuristic algorithms based on ant colony optimisation and local search. The order-based algorithm is able to find small dominating sets for graphs with tens of thousands of vertices. In addition, we propose a multi-start variant of RLS$_o$ that is suitable for solving the minimum weight dominating set problem. The application of RLS$_o$ in graph mining is also briefly demonstrated.
Matrix completion with queries
Venue: arXiv cs.LG 2017
Year: 2017

In many applications, e.g., recommender systems and traffic monitoring, the data comes in the form of a matrix that is only partially observed and low rank. A fundamental data-analysis task for these datasets is matrix completion, where the goal is to accurately infer the entries missing from the matrix. Even when the data satisfies the low-rank assumption, classical matrix-completion methods may output completions with significant error -- in that the reconstructed matrix differs significantly from the true underlying matrix. Often, this is due to the fact that the information contained in the observed entries is insufficient. In this work, we address this problem by proposing an active version of matrix completion, where queries can be made to the true underlying matrix. Subsequently, we design Order&Extend, which is the first algorithm to unify a matrix-completion approach and a querying strategy into a single algorithm. Order&Extend is able identify and alleviate insufficient information by judiciously querying a small number of additional entries. In an extensive experimental evaluation on real-world datasets, we demonstrate that our algorithm is efficient and is able to accurately reconstruct the true matrix while asking only a small number of queries.
A Statistical Model for Simultaneous Template Estimation, Bias Correction, and Registration of 3D Brain Images
Venue: arXiv cs.CV 2017
Year: 2017

Template estimation plays a crucial role in computational anatomy since it provides reference frames for performing statistical analysis of the underlying anatomical population variability. While building models for template estimation, variability in sites and image acquisition protocols need to be accounted for. To account for such variability, we propose a generative template estimation model that makes simultaneous inference of both bias fields in individual images, deformations for image registration, and variance hyperparameters. In contrast, existing maximum a posterori based methods need to rely on either bias-invariant similarity measures or robust image normalization. Results on synthetic and real brain MRI images demonstrate the capability of the model to capture heterogeneity in intensities and provide a reliable template estimation from registration.
Outage analysis in two-way communication with RF energy harvesting relay and co-channel interference
Venue: arXiv cs.NI 2017
Year: 2017

The study of relays with the scope of energy-harvesting (EH) looks interesting as a means of enabling sustainable, wireless communication without the need to recharge or replace the battery driving the relays. However, reliability of such communication systems becomes an important design challenge when such relays scavenge energy from the information bearing RF signals received from the source, using the technique of simultaneous wireless information and power transfer (SWIPT). To this aim, this work studies bidirectional communication in a decode-and-forward (DF) relay assisted cooperative wireless network in presence of co-channel interference (CCI). In order to quantify the reliability of the bidirectional communication systems, a closed form expression for the outage probability of the system is derived for both power splitting (PS) and time switching (TS) mode of operation of the relay. Simulation results are used to validate the accuracy of our analytical results and illustrate the dependence of the outage probability on various system parameters, like PS factor, TS factor, and distance of the relay from both the users. Results of performance comparison between PS relaying (PSR) and TS relaying (TSR) schemes are also presented. Besides, simulation results are also used to illustrate the spectral-efficiency and the energy-efficiency of the proposed system. The results show that, both in terms of spectral efficiency and the energy-efficiency, the two-way communication system in presence of moderate CCI power, performs better than the similar system without CCI. Additionally, it is also found that PSR is superior to TSR protocol in terms of peak energy-efficiency.
Consensus analysis of systems with time-varying interactions : An event-triggered approach
Venue: arXiv cs.SY 2017
Year: 2017

We present consensus analysis of systems with single integrator dynamics interacting via time-varying graphs under the event-triggered control paradigm. Event-triggered control sparsifies the control applied, thus reducing the control effort expended. Initially, we consider a multi-agent system with persistently exciting interactions and study the behaviour under the application of event-triggered control with two types of trigger functions- static and dynamic trigger.We show that while in the case of static trigger, the edge-states converge to a ball around the origin, the dynamic trigger function forces the states to reach consensus exponentially. Finally, we extend these results to a more general setting where we consider switching topologies. We show that similar results can be obtained for agents interacting via switching topologies and validate our results by means of simulations.
Labelled network subgraphs reveal stylistic subtleties in written texts
Venue: arXiv cs.CL 2017
Year: 2017

The vast amount of data and increase of computational capacity have allowed the analysis of texts from several perspectives, including the representation of texts as complex networks. Nodes of the network represent the words, and edges represent some relationship, usually word co-occurrence. Even though networked representations have been applied to study some tasks, such approaches are not usually combined with traditional models relying upon statistical paradigms. Because networked models are able to grasp textual patterns, we devised a hybrid classifier, called labelled subgraphs, that combines the frequency of common words with small structures found in the topology of the network, known as motifs. Our approach is illustrated in two contexts, authorship attribution and translationese identification. In the former, a set of novels written by different authors is analyzed. To identify translationese, texts from the Canadian Hansard and the European parliament were classified as to original and translated instances. Our results suggest that labelled subgraphs are able to represent texts and it should be further explored in other tasks, such as the analysis of text complexity, language proficiency, and machine translation.
Query-adaptive Video Summarization via Quality-aware Relevance Estimation
Venue: arXiv cs.CV 2017
Year: 2017

Although the problem of automatic video summarization has recently received a lot of attention, the problem of creating a video summary that also highlights elements relevant to a search query has been less studied. We address this problem by posing query-relevant summarization as a video frame subset selection problem, which lets us optimise for summaries which are simultaneously diverse, representative of the entire video, and relevant to a text query. We quantify relevance by measuring the distance between frames and queries in a common textual-visual semantic embedding space induced by a neural network. In addition, we extend the model to capture query-independent properties, such as frame quality. We compare our method against previous state of the art on textual-visual embeddings for thumbnail selection and show that our model outperforms them on relevance prediction. Furthermore, we introduce a new dataset, annotated with diversity and query-specific relevance labels. On this dataset, we train and test our complete model for video summarization and show that it outperforms standard baselines such as Maximal Marginal Relevance.