OpenRaiser/Intern-Atlas huggingface dataset:
Flexible Paxos: Quorum intersection revisited
Venue: arXiv cs.DC 2016
Year: 2016

Distributed consensus is integral to modern distributed systems. The widely adopted Paxos algorithm uses two phases, each requiring majority agreement, to reliably reach consensus. In this paper, we demonstrate that Paxos, which lies at the foundation of many production systems, is conservative. Specifically, we observe that each of the phases of Paxos may use non-intersecting quorums. Majority quorums are not necessary as intersection is required only across phases. Using this weakening of the requirements made in the original formulation, we propose Flexible Paxos, which generalizes over the Paxos algorithm to provide flexible quorums. We show that Flexible Paxos is safe, efficient and easy to utilize in existing distributed systems. We conclude by discussing the wide reaching implications of this result. Examples include improved availability from reducing the size of second phase quorums by one when the number of acceptors is even and utilizing small disjoint phase-2 quorums to speed up the steady-state.
Systematic Evaluation of Sandboxed Software Deployment for Real-time Software on the Example of a Self-Driving Heavy Vehicle
Venue: arXiv cs.SE 2016
Year: 2016

Companies developing and maintaining software-only products like web shops aim for establishing persistent links to their software running in the field. Monitoring data from real usage scenarios allows for a number of improvements in the software life-cycle, such as quick identification and solution of issues, and elicitation of requirements from previously unexpected usage. While the processes of continuous integration, continuous deployment, and continuous experimentation using sandboxing technologies are becoming well established in said software-only products, adopting similar practices for the automotive domain is more complex mainly due to real-time and safety constraints. In this paper, we systematically evaluate sandboxed software deployment in the context of a self-driving heavy vehicle that participated in the 2016 Grand Cooperative Driving Challenge (GCDC) in The Netherlands. We measured the system's scheduling precision after deploying applications in four different execution environments. Our results indicate that there is no significant difference in performance and overhead when sandboxed environments are used compared to natively deployed software. Thus, recent trends in software architecting, packaging, and maintenance using microservices encapsulated in sandboxes will help to realize similar software and system engineering for cyber-physical systems.
Structural properties of LPV to LFR transformation: minimality, input-output behavior and identifiability
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, we introduce and study important properties of the transformation of Affine Linear Parameter-Varying (ALPV) state-space representations into Linear Fractional Representations (LFR). More precisely, we show that $(i)$ state minimal ALPV representations yield minimal LFRs, and vice versa, $(ii)$ the input-output behavior of the ALPV represention determines uniquely the input-output behavior of the resulting LFR, $(iii)$ structurally identifiable ALPVs yield structurally identifiable LFRs, and vice versa. We then characterize LFR models which correspond to equivalent ALPV models based on their input-output maps. As illustrated all along the paper, these results have important consequences for identification and control of systems described by LFRs.
Is a good offensive always the best defense?
Venue: arXiv cs.AI 2016
Year: 2016

A checkers-like model game with a simplified set of rules is studied through extensive simulations of agents with different expertise and strategies. The introduction of complementary strategies, in a quite general way, provides a tool to mimic the basic ingredients of a wide scope of real games. We find that only for the player having the higher offensive expertise (the dominant player ), maximizing the offensive always increases the probability to win. For the non-dominant player, interestingly, a complete minimization of the offensive becomes the best way to win in many situations, depending on the relative values of the defense expertise. Further simulations on the interplay of defense expertise were done separately, in the context of a fully-offensive scenario, offering a starting point for analytical treatments. In particular, we established that in this scenario the total number of moves is defined only by the player with the lower defensive expertise. We believe that these results stand for a first step towards a new way to improve decisions-making in a large number of zero-sum real games.
Playing Anonymous Games using Simple Strategies
Venue: arXiv cs.GT 2016
Year: 2016

We investigate the complexity of computing approximate Nash equilibria in anonymous games. Our main algorithmic result is the following: For any $n$-player anonymous game with a bounded number of strategies and any constant $δ>0$, an $O(1/n^{1-δ})$-approximate Nash equilibrium can be computed in polynomial time. Complementing this positive result, we show that if there exists any constant $δ>0$ such that an $O(1/n^{1+δ})$-approximate equilibrium can be computed in polynomial time, then there is a fully polynomial-time approximation scheme for this problem. We also present a faster algorithm that, for any $n$-player $k$-strategy anonymous game, runs in time $\tilde O((n+k) k n^k)$ and computes an $\tilde O(n^{-1/3} k^{11/3})$-approximate equilibrium. This algorithm follows from the existence of simple approximate equilibria of anonymous games, where each player plays one strategy with probability $1-δ$, for some small $δ$, and plays uniformly at random with probability $δ$. Our approach exploits the connection between Nash equilibria in anonymous games and Poisson multinomial distributions (PMDs). Specifically, we prove a new probabilistic lemma establishing the following: Two PMDs, with large variance in each direction, whose first few moments are approximately matching are close in total variation distance. Our structural result strengthens previous work by providing a smooth tradeoff between the variance bound and the number of matching moments.
Fine Hand Segmentation using Convolutional Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

We propose a method for extracting very accurate masks of hands in egocentric views. Our method is based on a novel Deep Learning architecture: In contrast with current Deep Learning methods, we do not use upscaling layers applied to a low-dimensional representation of the input image. Instead, we extract features with convolutional layers and map them directly to a segmentation mask with a fully connected layer. We show that this approach, when applied in a multi-scale fashion, is both accurate and efficient enough for real-time. We demonstrate it on a new dataset made of images captured in various environments, from the outdoors to offices.
Syntax and semantics of the weak consistency model specification language cat
Venue: arXiv cs.PL 2016
Year: 2016

We provide the syntax and semantics of the cat language, a domain specific language to describe consistency properties of parallel/distributed programs. The language is implemented in the herd7 too (http://diy.inria.fr/doc/herd.html)l.
An algorithm for dividing two complex numbers
Venue: arXiv cs.DS 2016
Year: 2016

In this work a rationalized algorithm for calculating the quotient of two complex numbers is presented which reduces the number of underlying real multiplications. The performing of a complex number division using the naive method takes 4 multiplications, 3 additions, 2 squarings and 2 divisions of real numbers while the proposed algorithm can compute the same result in only 3 multiplications ( or multipliers in hardware implementation case), 6 additions, 2 squarings and 2 divisions of real numbers.
Mitosis Detection in Intestinal Crypt Images with Hough Forest and Conditional Random Fields
Venue: arXiv cs.CV 2016
Year: 2016

Intestinal enteroendocrine cells secrete hormones that are vital for the regulation of glucose metabolism but their differentiation from intestinal stem cells is not fully understood. Asymmetric stem cell divisions have been linked to intestinal stem cell homeostasis and secretory fate commitment. We monitored cell divisions using 4D live cell imaging of cultured intestinal crypts to characterize division modes by means of measurable features such as orientation or shape. A statistical analysis of these measurements requires annotation of mitosis events, which is currently a tedious and time-consuming task that has to be performed manually. To assist data processing, we developed a learning based method to automatically detect mitosis events. The method contains a dual-phase framework for joint detection of dividing cells (mothers) and their progeny (daughters). In the first phase we detect mother and daughters independently using Hough Forest whilst in the second phase we associate mother and daughters by modelling their joint probability as Conditional Random Field (CRF). The method has been evaluated on 32 movies and has achieved an AUC of 72%, which can be used in conjunction with manual correction and dramatically speed up the processing pipeline.
Spatio-temporal Aware Non-negative Component Representation for Action Recognition
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents a novel mid-level representation for action recognition, named spatio-temporal aware non-negative component representation (STANNCR). The proposed STANNCR is based on action component and incorporates the spatial-temporal information. We first introduce a spatial-temporal distribution vector (STDV) to model the distributions of local feature locations in a compact and discriminative manner. Then we employ non-negative matrix factorization (NMF) to learn the action components and encode the video samples. The action component considers the correlations of visual words, which effectively bridge the sematic gap in action recognition. To incorporate the spatial-temporal cues for final representation, the STDV is used as the part of graph regularization for NMF. The fusion of spatial-temporal information makes the STANNCR more discriminative, and our fusion manner is more compact than traditional method of concatenating vectors. The proposed approach is extensively evaluated on three public datasets. The experimental results demonstrate the effectiveness of STANNCR for action recognition.
CISER: An Amoebiasis inspired Model for Epidemic Message Propagation in DTN
Venue: arXiv cs.NI 2016
Year: 2016

Delay Tolerant Networks (DTNs) are sparse mobile networks, which experiences frequent disruptions in connectivity among nodes. Usually, DTN follows store-carry-and forward mechanism for message forwarding, in which a node store and carry the message until it finds an appropriate relay node to forward further in the network. So, The efficiency of DTN routing protocol relies on the intelligent selection of a relay node from a set of encountered nodes. Although there are plenty of DTN routing schemes proposed in the literature based on different strategies of relay selection, there are not many mathematical models proposed to study the behavior of message forwarding in DTN. In this paper, we have proposed a novel epidemic model, called as CISER model, for message propagation in DTN, based on Amoebiasis disease propagation in human population. The proposed CISER model is an extension of SIR epidemic model with additional states to represent the resource constrained behavior of nodes in DTN. Experimental results using both synthetic and real-world traces show that the proposed model improves the routing performance metrics, such as delivery ratio, overhead ratio and delivery delay compared to SIR model.
Logic programming: laxness and saturation
Venue: arXiv cs.LO 2016
Year: 2016

A propositional logic program $P$ may be identified with a $P_fP_f$-coalgebra on the set of atomic propositions in the program. The corresponding $C(P_fP_f)$-coalgebra, where $C(P_fP_f)$ is the cofree comonad on $P_fP_f$, describes derivations by resolution. That correspondence has been developed to model first-order programs in two ways, with lax semantics and saturated semantics, based on locally ordered categories and right Kan extensions respectively. We unify the two approaches, exhibiting them as complementary rather than competing, reflecting the theorem-proving and proof-search aspects of logic programming. While maintaining that unity, we further refine lax semantics to give finitary models of logic programs with existential variables, and to develop a precise semantic relationship between variables in logic programming and worlds in local state.
Testing APSyn against Vector Cosine on Similarity Estimation
Venue: arXiv cs.CL 2016
Year: 2016

In Distributional Semantic Models (DSMs), Vector Cosine is widely used to estimate similarity between word vectors, although this measure was noticed to suffer from several shortcomings. The recent literature has proposed other methods which attempt to mitigate such biases. In this paper, we intend to investigate APSyn, a measure that computes the extent of the intersection between the most associated contexts of two target words, weighting it by context relevance. We evaluated this metric in a similarity estimation task on several popular test sets, and our results show that APSyn is in fact highly competitive, even with respect to the results reported in the literature for word embeddings. On top of it, APSyn addresses some of the weaknesses of Vector Cosine, performing well also on genuine similarity estimation.
Sum Secrecy Rate Maximization for Full-Duplex Two-Way Relay Networks Using Alamouti-based Rank-Two Beamforming
Venue: arXiv cs.IT 2016
Year: 2016

Consider a two-way communication scenario where two single-antenna nodes, operating under full-duplex mode, exchange information to one another through the aid of a (full-duplex) multi-antenna relay, and there is another single-antenna node who intends to eavesdrop. The relay employs artificial noise (AN) to interfere the eavesdropper's channel, and amplify-forward (AF) Alamouti-based rank-two beamforming to establish the two-way communication links of the legitimate nodes. Our problem is to optimize the rank-two beamformer and AN covariance for sum secrecy rate maximization (SSRM). This SSRM problem is nonconvex, and we develop an efficient solution approach using semidefinite relaxation (SDR) and minorization-maximization (MM). We prove that SDR is tight for the SSRM problem and thus introduces no loss. Also, we consider an inexact MM method where an approximately but computationally cheap MM solution update is used in place of the exact update in conventional MM. We show that this inexact MM method guarantees convergence to a stationary solution to the SSRM problem. The effectiveness of our proposed approach is further demonstrated by an energy-harvesting scenario extension, and by extensive simulation results.
MindX: Denoising Mixed Impulse Poisson-Gaussian Noise Using Proximal Algorithms
Venue: arXiv cs.CV 2016
Year: 2016

We present a novel algorithm for blind denoising of images corrupted by mixed impulse, Poisson, and Gaussian noises. The algorithm starts by applying the Anscombe variance-stabilizing transformation to convert the Poisson into white Gaussian noise. Then it applies a combinatorial optimization technique to denoise the mixed impulse Gaussian noise using proximal algorithms. The result is then processed by the inverse Anscombe transform. We compare our algorithm to state of the art methods on standard images, and show its superior performance in various noise conditions.
Fault Localization in Web Applications via Model Finding
Venue: arXiv cs.LO 2016
Year: 2016

We describe a generic technique for fault localization independent from the nature of the object or the specification language used to declare its expected properties. This technique is based on the concept of "repair", a minimal set of transformations which, when applied to the original object, restores its satisfiability with respect to the specification. We show how this technique can be applied with various specification languages, including propositional and finite first-order logic. In particular, we focus on its use in the detection of layout faults in web applications.
Recent Results on Fault-Tolerant Consensus in Message-Passing Networks
Venue: arXiv cs.DC 2016
Year: 2016

Fault-tolerant consensus has been studied extensively in the literature, because it is one of the most important distributed primitives and has wide applications in practice. This paper surveys important results on fault-tolerant consensus in message-passing networks, and the focus is on results from the past decade. Particularly, we categorize the results into two groups: new problem formulations and practical applications. In the first part, we discuss new ways to define the consensus problem, which includes larger input domains, link fault models, different network models . . . etc, and briefly discuss the important techniques. In the second part, we focus on Crash Fault-Tolerant (CFT) systems that use Paxos or Raft, and Byzantine Fault-Tolerant (BFT) systems. We also discuss Bitcoin, which can be related to solving Byzantine consensus in anonymous systems, and compare Bitcoin with BFT systems and Byzantine consensus.
Crossing Minimization in Storyline Visualization
Venue: arXiv cs.DS 2016
Year: 2016

A storyline visualization is a layout that represents the temporal dynamics of social interactions along time by the convergence of chronological lines. Among the criteria oriented at improving aesthetics and legibility of a representation of this type, a small number of line crossings is the hardest to achieve. We model the crossing minimization in the storyline visualization problem as a multi-layer crossing minimization problem with tree constraints. Our algorithm can compute a layout with the minimum number of crossings of the chronological lines. Computational results demonstrate that it can solve instances with more than 100 interactions and with more than 100 chronological lines to optimality.
Fuzzy Logic in Narrow Sense with Hedges
Venue: arXiv cs.AI 2016
Year: 2016

Classical logic has a serious limitation in that it cannot cope with the issues of vagueness and uncertainty into which fall most modes of human reasoning. In order to provide a foundation for human knowledge representation and reasoning in the presence of vagueness, imprecision, and uncertainty, fuzzy logic should have the ability to deal with linguistic hedges, which play a very important role in the modification of fuzzy predicates. In this paper, we extend fuzzy logic in narrow sense with graded syntax, introduced by Novak et al., with many hedge connectives. In one case, each hedge does not have any dual one. In the other case, each hedge can have its own dual one. The resulting logics are shown to also have the Pavelka-style completeness
Maximizing Data Rate for Multiway Relay Channels with Pairwise Transmission Strategy
Venue: arXiv cs.IT 2016
Year: 2016

In a multiway relay channel (MWRC), pairwise transmission strategy can be used to reduce the computational complexity at the relay and the users without sacrificing the data rate, significantly. The performance of such pairwise strategies, however, is affected by the way that the users are paired to transmit. In this paper, we study the effect of pairing on the common rate and sum rate of an MWRC with functional-decode-forward (FDF) relaying strategy where users experience asymmetric channel conditions. To this end, we first develop a graphical model for an MWRC with pairwise transmission strategy. Using this model, we then find the maximum achievable common rate and sum rate as well as the user pairings that achieve these rates. This marks the ultimate performance of FDF relaying in an MWRC setup. Further, we show that the rate enhancement achieved through the optimal user pairing becomes less pronounced at higher SNRs. Using computer simulations, the performance of the optimal pairing is compared with those of other proposed pairings in the literature.
Smart Policies for Artificial Intelligence
Venue: arXiv cs.CY 2016
Year: 2016

We argue that there already exists de facto artificial intelligence policy - a patchwork of policies impacting the field of AI's development in myriad ways. The key question related to AI policy, then, is not whether AI should be governed at all, but how it is currently being governed, and how that governance might become more informed, integrated, effective, and anticipatory. We describe the main components of de facto AI policy and make some recommendations for how AI policy can be improved, drawing on lessons from other scientific and technological domains.
Temporal Convolutional Networks: A Unified Approach to Action Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

The dominant paradigm for video-based action segmentation is composed of two steps: first, for each frame, compute low-level features using Dense Trajectories or a Convolutional Neural Network that encode spatiotemporal information locally, and second, input these features into a classifier that captures high-level temporal relationships, such as a Recurrent Neural Network (RNN). While often effective, this decoupling requires specifying two separate models, each with their own complexities, and prevents capturing more nuanced long-range spatiotemporal relationships. We propose a unified approach, as demonstrated by our Temporal Convolutional Network (TCN), that hierarchically captures relationships at low-, intermediate-, and high-level time-scales. Our model achieves superior or competitive performance using video or sensor data on three public action segmentation datasets and can be trained in a fraction of the time it takes to train an RNN.
About Learning in Recurrent Bistable Gradient Networks
Venue: arXiv cs.NE 2016
Year: 2016

Recurrent Bistable Gradient Networks are attractor based neural networks characterized by bistable dynamics of each single neuron. Coupled together using linear interaction determined by the interconnection weights, these networks do not suffer from spurious states or very limited capacity anymore. Vladimir Chinarov and Michael Menzinger, who invented these networks, trained them using Hebb's learning rule. We show, that this way of computing the weights leads to unwanted behaviour and limitations of the networks capabilities. Furthermore we evince, that using the first order of Hintons Contrastive Divergence algorithm leads to a quite promising recurrent neural network. These findings are tested by learning images of the MNIST database for handwritten numbers.