OpenRaiser/Intern-Atlas huggingface dataset:
Federated Scheduling Admits No Constant Speedup Factors for Constrained-Deadline DAG Task Systems
Venue: arXiv cs.DS 2016
Year: 2016

In the federated scheduling approaches in multiprocessor systems, a task either 1) is restricted to execute sequentially on a single processor or 2) has exclusive access to the assigned processors. There have been several positive results to conduct good federated scheduling policies, which have constant speedup factors with respect to any optimal federated scheduling algorithm. This paper answers an open question: "For constrained-deadline task systems with directed acyclic graph (DAG) dependency structures, do federated scheduling policies have a constant speedup factor with respect to any optimal scheduling algorithm?" The answer is "No!" This paper presents an example, which demonstrates that any federated scheduling algorithm has a speedup factor of at least $Ω(\min\{M, N\})$ with respect to any optimal scheduling algorithm, where $N$ is the number of tasks and $M$ is the number of processors.
ENFT: Efficient Non-Consecutive Feature Tracking for Robust Structure-from-Motion
Venue: arXiv cs.CV 2016
Year: 2016

Structure-from-motion (SfM) largely relies on feature tracking. In image sequences, if disjointed tracks caused by objects moving in and out of the field of view, occasional occlusion, or image noise, are not handled well, corresponding SfM could be affected. This problem becomes severer for large-scale scenes, which typically requires to capture multiple sequences to cover the whole scene. In this paper, we propose an efficient non-consecutive feature tracking (ENFT) framework to match interrupted tracks distributed in different subsequences or even in different videos. Our framework consists of steps of solving the feature `dropout' problem when indistinctive structures, noise or large image distortion exists, and of rapidly recognizing and joining common features located in different subsequences. In addition, we contribute an effective segment-based coarse-to-fine SfM algorithm for robustly handling large datasets. Experimental results on challenging video data demonstrate the effectiveness of the proposed system.
Toward fault-tolerant parallel-in-time integration with PFASST
Venue: arXiv cs.DC 2016
Year: 2016

We introduce and analyze different strategies for the parallel-in-time integration method PFASST to recover from hard faults and subsequent data loss. Since PFASST stores solutions at multiple time steps on different processors, information from adjacent steps can be used to recover after a processor has failed. PFASST's multi-level hierarchy allows to use the coarse level for correcting the reconstructed solution, which can help to minimize overhead. A theoretical model is devised linking overhead to the number of additional PFASST iterations required for convergence after a fault. The potential efficiency of different strategies is assessed in terms of required additional iterations for examples of diffusive and advective type.
What's Decidable about Syntax-Guided Synthesis?
Venue: arXiv cs.LO 2016
Year: 2016

Syntax-guided synthesis (SyGuS) is a recently proposed framework for program synthesis problems. The SyGuS problem is to find an expression or program generated by a given grammar that meets a correctness specification. Correctness specifications are given as formulas in suitable logical theories, typically amongst those studied in satisfiability modulo theories (SMT). In this work, we analyze the decidability of the SyGuS problem for different classes of grammars and correctness specifications. We prove that the SyGuS problem is undecidable for the theory of equality with uninterpreted functions (EUF).We identify a fragment of EUF, which we call regular-EUF, for which the SyGuS problem is decidable. We prove that this restricted problem is EXPTIME-complete and that the sets of solution expressions are precisely the regular tree languages. For theories that admit a unique, finite domain, we give a general algorithm to solve the SyGuS problem on tree grammars. Finite-domain theories include the bit-vector theory without concatenation. We prove SyGuS undecidable for a very simple bit-vector theory with concatenation, both for context-free grammars and for tree grammars. Finally, we give some additional results for linear arithmetic and bit-vector arithmetic along with a discussion of the implication of these results.
Build your own clarithmetic II: Soundness
Venue: arXiv cs.LO 2016
Year: 2016

Clarithmetics are number theories based on computability logic (see http://www.csc.villanova.edu/~japaridz/CL/ ). Formulas of these theories represent interactive computational problems, and their "truth" is understood as existence of an algorithmic solution. Various complexity constraints on such solutions induce various versions of clarithmetic. The present paper introduces a parameterized/schematic version CLA11(P1,P2,P3,P4). By tuning the three parameters P1,P2,P3 in an essentially mechanical manner, one automatically obtains sound and complete theories with respect to a wide range of target tricomplexity classes, i.e. combinations of time (set by P3), space (set by P2) and so called amplitude (set by P1) complexities. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a solution from the given tricomplexity class and, furthermore, such a solution can be automatically extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a solution from the given tricomplexity class is represented by some theorem of the system. Furthermore, through tuning the 4th parameter P4, at the cost of sacrificing recursive axiomatizability but not simplicity or elegance, the above extensional completeness can be strengthened to intensional completeness, according to which every formula representing a problem with a solution from the given tricomplexity class is a theorem of the system. This article is published in two parts. The previous Part I has introduced the system and proved its completeness, while the present Part II is devoted to proving soundness.
Interdependent Security Games on Networks under Behavioral Probability Weighting
Venue: arXiv cs.GT 2016
Year: 2016

We consider a class of interdependent security games on networks where each node chooses a personal level of security investment. The attack probability experienced by a node is a function of her own investment and the investment by her neighbors in the network. Most of the existing work in these settings considers players who are risk-neutral. In contrast, studies in behavioral decision theory have shown that individuals often deviate from risk-neutral behavior while making decisions under uncertainty. In particular, the true probabilities associated with uncertain outcomes are often transformed into perceived probabilities in a highly nonlinear fashion by the users, which then influence their decisions. In this paper, we investigate the effects of such behavioral probability weightings by the nodes on their optimal investment strategies and the resulting security risk profiles that arise at the Nash equilibria of interdependent network security games. We characterize graph topologies that achieve the largest and smallest worst case average attack probabilities at Nash equilibria in Total Effort games, and equilibrium investments in Weakest Link and Best Shot games.
Spatial Semantic Scan: Jointly Detecting Subtle Events and their Spatial Footprint
Venue: arXiv cs.LG 2016
Year: 2016

Many methods have been proposed for detecting emerging events in text streams using topic modeling. However, these methods have shortcomings that make them unsuitable for rapid detection of locally emerging events on massive text streams. We describe Spatially Compact Semantic Scan (SCSS) that has been developed specifically to overcome the shortcomings of current methods in detecting new spatially compact events in text streams. SCSS employs alternating optimization between using semantic scan to estimate contrastive foreground topics in documents, and discovering spatial neighborhoods with high occurrence of documents containing the foreground topics. We evaluate our method on Emergency Department chief complaints dataset (ED dataset) to verify the effectiveness of our method in detecting real-world disease outbreaks from free-text ED chief complaint data.
A Functional Composition Approach to Filter Sharpening and Modular Filter Design
Venue: arXiv cs.SY 2016
Year: 2016

Designing and implementing systems as an interconnection of smaller subsystems is a common practice for modularity and standardization of components and design algorithms. Although not typically cast in this framework, many of these approaches can be viewed within the mathematical context of functional composition. This paper re-interprets and generalizes within the functional composition framework one such approach known as filter sharpening, i.e. interconnecting filter modules which have significant approximation error in order to obtain improved filter characteristics. More specifically, filter sharpening is approached by determining the composing polynomial to minimize the infinity-norm of the approximation error, utilizing the First Algorithm of Remez. This is applied both to sharpening for FIR, even-symmetric filters and for the more general case of subfilters that have complex-valued frequency responses including causal IIR filters and for continuous-time filters. Within the framework of functional composition, this paper also explores the use of functional decomposition to approximate a desired system as a composition of simpler functions based on a two-norm on the approximation error. Among the potential advantages of this decomposition is the ability for modular implementation in which the inner component of the functional decomposition represents the subfilters and the outer the interconnection.
Computing Feasible Vehicle Platooning Opportunities for Transport Assignments
Venue: arXiv cs.SY 2016
Year: 2016

Vehicle platooning facilitates the partial automation of vehicles and can significantly reduce fuel consumption. Mobile communication infrastructure makes it possible to dynamically coordinate the formation of platoons en route. We consider a centralized system that provides trucks with routes and speed profiles allowing them to dynamically form platoons during their journeys. For this to work, all possible pairs of vehicles that can platoon based on their location, destination, and other constraints have to be identified. The presented approach scales well to large vehicle fleets and realistic road networks by extracting features from the transport assignments of the vehicles and rules out a majority of possible pairs based on these features only. Merely a small number of remaining pairs are considered in depth by a complete and computationally expensive algorithm. This algorithm conclusively decides if platooning is possible for a pair based on the complete data associated with the two vehicles. We derive appropriate features for the problem and demonstrate the effectiveness of the approach in a simulation example.
Equivalence Checking By Logic Relaxation
Venue: arXiv cs.LO 2016
Year: 2016

We introduce a new framework for Equivalence Checking (EC) of Boolean circuits based on a general technique called Logic Relaxation (LoR). The essence of LoR is to relax the formula to be solved and compute a superset S of the set of new behaviors. Namely, S contains all new satisfying assignments that appeared due to relaxation and does not contain assignments satisfying the original formula. Set S is generated by a procedure called partial quantifier elimination. If all possible bad behaviors are in S, the original formula cannot have them and so the property described by this formula holds. The appeal of EC by LoR is twofold. First, it facilitates generation of powerful inductive proofs. Second, proving inequivalence comes down to checking the presence of some bad behaviors in the relaxed formula i.e. in a simpler version of the original formula. We give some experimental evidence that supports our approach.
Efficient community detection of network flows for varying Markov times and bipartite networks
Venue: arXiv cs.SI 2016
Year: 2016

Community detection of network flows conventionally assumes one-step dynamics on the links. For sparse networks and interest in large-scale structures, longer timescales may be more appropriate. Oppositely, for large networks and interest in small-scale structures, shorter timescales may be better. However, current methods for analyzing networks at different timescales require expensive and often infeasible network reconstructions. To overcome this problem, we introduce a method that takes advantage of the inner-workings of the map equation and evades the reconstruction step. This makes it possible to efficiently analyze large networks at different Markov times with no extra overhead cost. The method also evades the costly unipartite projection for identifying flow modules in bipartite networks.
Multinomial Loss on Held-out Data for the Sparse Non-negative Matrix Language Model
Venue: arXiv cs.CL 2016
Year: 2016

We describe Sparse Non-negative Matrix (SNM) language model estimation using multinomial loss on held-out data. Being able to train on held-out data is important in practical situations where the training data is usually mismatched from the held-out/test data. It is also less constrained than the previous training algorithm using leave-one-out on training data: it allows the use of richer meta-features in the adjustment model, e.g. the diversity counts used by Kneser-Ney smoothing which would be difficult to deal with correctly in leave-one-out training. In experiments on the one billion words language modeling benchmark, we are able to slightly improve on our previous results which use a different loss function, and employ leave-one-out training on a subset of the main training set. Surprisingly, an adjustment model with meta-features that discard all lexical information can perform as well as lexicalized meta-features. We find that fairly small amounts of held-out data (on the order of 30-70 thousand words) are sufficient for training the adjustment model. In a real-life scenario where the training data is a mix of data sources that are imbalanced in size, and of different degrees of relevance to the held-out and test data, taking into account the data source for a given skip-/n-gram feature and combining them for best performance on held-out/test data improves over skip-/n-gram SNM models trained on pooled data by about 8% in the SMT setup, or as much as 15% in the ASR/IME setup. The ability to mix various data sources based on how relevant they are to a mismatched held-out set is probably the most attractive feature of the new estimation method for SNM LM.
To Motivate Social Grouping in Wireless Networks
Venue: arXiv cs.SI 2016
Year: 2016

We consider a group of neighboring smartphone users who are roughly at the same time interested in the same network content, called common interests. However, ever-increasing data traffic challenges the limited capacity of base-stations (BSs) in wireless networks. To better utilize the limited BSs' resources under unreliable wireless networks, we propose local common-interests sharing (enabled by D2D communications) by motivating the physically neighboring users to form a social group. As users are selfish in practice, an incentive mechanism is needed to motivate social grouping. We propose a novel concept of equal-reciprocal incentive over broadcast communications, which fairly ensures that each pair of the users in the social group share the same amount of content with each other. As the equal-reciprocal incentive may restrict the amount of content shared among the users, we analyze the optimal equal-reciprocal scheme that maximizes local sharing content. While ensuring fairness among users, we show that this optimized scheme also maximizes each user's utility in the social group. Finally, we look at dynamic content arrivals and extend our scheme successfully by proposing novel on-line scheduling algorithms.
Recovering hard-to-find object instances by sampling context-based object proposals
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we focus on improving object detection performance in terms of recall. We propose a post-detection stage during which we explore the image with the objective of recovering missed detections. This exploration is performed by sampling object proposals in the image. We analyze four different strategies to perform this sampling, giving special attention to strategies that exploit spatial relations between objects. In addition, we propose a novel method to discover higher-order relations between groups of objects. Experiments on the challenging KITTI dataset show that our proposed relations-based proposal generation strategies can help improving recall at the cost of a relatively low amount of object proposals.
Population size predicts lexical diversity, but so does the mean sea level - why it is important to correctly account for the structure of temporal data
Venue: arXiv cs.CL 2016
Year: 2016

In order to demonstrate why it is important to correctly account for the (serial dependent) structure of temporal data, we document an apparently spectacular relationship between population size and lexical diversity: for five out of seven investigated languages, there is a strong relationship between population size and lexical diversity of the primary language in this country. We show that this relationship is the result of a misspecified model that does not consider the temporal aspect of the data by presenting a similar but nonsensical relationship between the global annual mean sea level and lexical diversity. Given the fact that in the recent past, several studies were published that present surprising links between different economic, cultural, political and (socio-)demographical variables on the one hand and cultural or linguistic characteristics on the other hand, but seem to suffer from exactly this problem, we explain the cause of the misspecification and show that it has profound consequences. We demonstrate how simple transformation of the time series can often solve problems of this type and argue that the evaluation of the plausibility of a relationship is important in this context. We hope that our paper will help both researchers and reviewers to understand why it is important to use special models for the analysis of data with a natural temporal ordering.
An Efficient Multilinear Optimization Framework for Hypergraph Matching
Venue: arXiv cs.CV 2016
Year: 2016

Hypergraph matching has recently become a popular approach for solving correspondence problems in computer vision as it allows to integrate higher-order geometric information. Hypergraph matching can be formulated as a third-order optimization problem subject to the assignment constraints which turns out to be NP-hard. In recent work, we have proposed an algorithm for hypergraph matching which first lifts the third-order problem to a fourth-order problem and then solves the fourth-order problem via optimization of the corresponding multilinear form. This leads to a tensor block coordinate ascent scheme which has the guarantee of providing monotonic ascent in the original matching score function and leads to state-of-the-art performance both in terms of achieved matching score and accuracy. In this paper we show that the lifting step to a fourth-order problem can be avoided yielding a third-order scheme with the same guarantees and performance but being two times faster. Moreover, we introduce a homotopy type method which further improves the performance.
Integrating a large-scale testing campaign in the CK framework
Venue: arXiv cs.SE 2016
Year: 2016

We consider the problem of conducting large experimental campaigns in programming languages research. Most research efforts require a certain level of bookkeeping of results. This is manageable via quick, on-the-fly infrastructure implementations. However, it becomes a problem for large-scale testing initiatives, especially as the needs of the project evolve along the way. We look at how the Collective Knowledge generalized testing framework can help with such a project and its overall applicability and ease of use. The project in question is an OpenCL compiler testing campaign. We investigate how to use the Collective Knowledge framework to lead the experimental campaign, by providing storage and representation of test cases and their results. We also provide an initial implementation, publicly available.
Traffic Sign Classification Using Deep Inception Based Convolutional Networks
Venue: arXiv cs.CV 2016
Year: 2016

In this work, we propose a novel deep network for traffic sign classification that achieves outstanding performance on GTSRB surpassing all previous methods. Our deep network consists of spatial transformer layers and a modified version of inception module specifically designed for capturing local and global features together. This features adoption allows our network to classify precisely intraclass samples even under deformations. Use of spatial transformer layer makes this network more robust to deformations such as translation, rotation, scaling of input images. Unlike existing approaches that are developed with hand-crafted features, multiple deep networks with huge parameters and data augmentations, our method addresses the concern of exploding parameters and augmentations. We have achieved the state-of-the-art performance of 99.81\% on GTSRB dataset.
Drawing from hats by noise-based logic
Venue: arXiv cs.ET 2016
Year: 2016

We utilize the asymmetric random telegraph wave-based instantaneous noise-base logic scheme to represent the problem of drawing numbers from a hat, and we consider two identical hats with the first 2^N integer numbers. In the first problem, Alice secretly draws an arbitrary number from one of the hats, and Bob must find out which hat is missing a number. In the second problem, Alice removes a known number from one of the hats and another known number from the other hat, and Bob must identify these hats. We show that, when the preparation of the hats with the numbers is accounted for, the noise-based logic scheme always provides an exponential speed-up and/or it requires exponentially smaller computational complexity than deterministic alternatives. Both the stochasticity and the ability to superpose numbers are essential components of the exponential improvement.
Generative Concatenative Nets Jointly Learn to Write and Classify Reviews
Venue: arXiv cs.CL 2016
Year: 2016

A recommender system's basic task is to estimate how users will respond to unseen items. This is typically modeled in terms of how a user might rate a product, but here we aim to extend such approaches to model how a user would write about the product. To do so, we design a character-level Recurrent Neural Network (RNN) that generates personalized product reviews. The network convincingly learns styles and opinions of nearly 1000 distinct authors, using a large corpus of reviews from BeerAdvocate.com. It also tailors reviews to describe specific items, categories, and star ratings. Using a simple input replication strategy, the Generative Concatenative Network (GCN) preserves the signal of static auxiliary inputs across wide sequence intervals. Without any additional training, the generative model can classify reviews, identifying the author of the review, the product category, and the sentiment (rating), with remarkable accuracy. Our evaluation shows the GCN captures complex dynamics in text, such as the effect of negation, misspellings, slang, and large vocabularies gracefully absent any machinery explicitly dedicated to the purpose.