OpenRaiser/Intern-Atlas huggingface dataset:
Qualitative Analysis of Concurrent Mean-payoff Games
Venue: arXiv cs.GT 2014
Year: 2014

We consider concurrent games played by two-players on a finite-state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study a fundamental objective, namely, mean-payoff objective, where a reward is associated to each transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite. The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show that for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies, or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (the value problem for turn-based deterministic mean-payoff games) that is not known to be solvable in polynomial time.
Belief revision by examples
Venue: arXiv cs.AI 2014
Year: 2014

A common assumption in belief revision is that the reliability of the information sources is either given, derived from temporal information, or the same for all. This article does not describe a new semantics for integration but the problem of obtaining the reliability of the sources given the result of a previous merging. As an example, the relative reliability of two sensors can be assessed given some certain observation, and allows for subsequent mergings of data coming from them.
SAME but Different: Fast and High-Quality Gibbs Parameter Estimation
Venue: arXiv cs.LG 2014
Year: 2014

Gibbs sampling is a workhorse for Bayesian inference but has several limitations when used for parameter estimation, and is often much slower than non-sampling inference methods. SAME (State Augmentation for Marginal Estimation) \cite{Doucet99,Doucet02} is an approach to MAP parameter estimation which gives improved parameter estimates over direct Gibbs sampling. SAME can be viewed as cooling the posterior parameter distribution and allows annealed search for the MAP parameters, often yielding very high quality (lower loss) estimates. But it does so at the expense of additional samples per iteration and generally slower performance. On the other hand, SAME dramatically increases the parallelism in the sampling schedule, and is an excellent match for modern (SIMD) hardware. In this paper we explore the application of SAME to graphical model inference on modern hardware. We show that combining SAME with factored sample representation (or approximation) gives throughput competitive with the fastest symbolic methods, but with potentially better quality. We describe experiments on Latent Dirichlet Allocation, achieving speeds similar to the fastest reported methods (online Variational Bayes) and lower cross-validated loss than other LDA implementations. The method is simple to implement and should be applicable to many other models.
Antifragile Electronic Warfare
Venue: arXiv cs.NI 2014
Year: 2014

This letter introduces the concept of antifragile electronic warfare (EW), which we define as the ability to allow a communications link to improve performance due to the presence of a jammer. This concept should not be confused with jamming countermeasures (a.k.a. anti-jamming or electronic protection). Rather, antifragile EW can be thought of as the next step beyond simply avoiding or mitigating jamming. After introducing the concept we narrow down the subset of jammers this concept can be applied to, and provide a brief example of an antifragile EW strategy.
A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specifications
Venue: arXiv cs.SY 2014
Year: 2014

We propose to synthesize a control policy for a Markov decision process (MDP) such that the resulting traces of the MDP satisfy a linear temporal logic (LTL) property. We construct a product MDP that incorporates a deterministic Rabin automaton generated from the desired LTL property. The reward function of the product MDP is defined from the acceptance condition of the Rabin automaton. This construction allows us to apply techniques from learning theory to the problem of synthesis for LTL specifications even when the transition probabilities are not known a priori. We prove that our method is guaranteed to find a controller that satisfies the LTL property with probability one if such a policy exists, and we suggest empirically with a case study in traffic control that our method produces reasonable control strategies even when the LTL property cannot be satisfied with probability one.
Using crowdsourcing system for creating site-specific statistical machine translation engine
Venue: arXiv cs.CL 2014
Year: 2014

A crowdsourcing translation approach is an effective tool for globalization of site content, but it is also an important source of parallel linguistic data. For the given site, processed with a crowdsourcing system, a sentence-aligned corpus can be fetched, which covers a very narrow domain of terminology and language patterns - a site-specific domain. These data can be used for training and estimation of site-specific statistical machine translation engine
Watchword-Oriented and Time-Stamped Algorithms for Tamper-Proof Cloud Provenance Cognition
Venue: arXiv cs.DC 2014
Year: 2014

Provenance is derivative journal information about the origin and activities of system data and processes. For a highly dynamic system like the cloud, provenance can be accurately detected and securely used in cloud digital forensic investigation activities. This paper proposes watchword oriented provenance cognition algorithm for the cloud environment. Additionally time-stamp based buffer verifying algorithm is proposed for securing the access to the detected cloud provenance. Performance analysis of the novel algorithms proposed here yields a desirable detection rate of 89.33% and miss rate of 8.66%. The securing algorithm successfully rejects 64% of malicious requests, yielding a cumulative frequency of 21.43 for MR.
Lempel-Ziv Factorization May Be Harder Than Computing All Runs
Venue: arXiv cs.DS 2014
Year: 2014

The complexity of computing the Lempel-Ziv factorization and the set of all runs (= maximal repetitions) is studied in the decision tree model of computation over ordered alphabet. It is known that both these problems can be solved by RAM algorithms in $O(n\logσ)$ time, where $n$ is the length of the input string and $σ$ is the number of distinct letters in it. We prove an $Ω(n\logσ)$ lower bound on the number of comparisons required to construct the Lempel-Ziv factorization and thereby conclude that a popular technique of computation of runs using the Lempel-Ziv factorization cannot achieve an $o(n\logσ)$ time bound. In contrast with this, we exhibit an $O(n)$ decision tree algorithm finding all runs in a string. Therefore, in the decision tree model the runs problem is easier than the Lempel-Ziv factorization. Thus we support the conjecture that there is a linear RAM algorithm finding all runs.
Local Optimal Sets and Bounded Archiving on Multi-objective NK-Landscapes with Correlated Objectives
Venue: arXiv cs.AI 2014
Year: 2014

The properties of local optimal solutions in multi-objective combinatorial optimization problems are crucial for the effectiveness of local search algorithms, particularly when these algorithms are based on Pareto dominance. Such local search algorithms typically return a set of mutually nondominated Pareto local optimal (PLO) solutions, that is, a PLO-set. This paper investigates two aspects of PLO-sets by means of experiments with Pareto local search (PLS). First, we examine the impact of several problem characteristics on the properties of PLO-sets for multi-objective NK-landscapes with correlated objectives. In particular, we report that either increasing the number of objectives or decreasing the correlation between objectives leads to an exponential increment on the size of PLO-sets, whereas the variable correlation has only a minor effect. Second, we study the running time and the quality reached when using bounding archiving methods to limit the size of the archive handled by PLS, and thus, the maximum size of the PLO-set found. We argue that there is a clear relationship between the running time of PLS and the difficulty of a problem instance.
Hyperspectral and Multispectral Image Fusion based on a Sparse Representation
Venue: arXiv cs.CV 2014
Year: 2014

This paper presents a variational based approach to fusing hyperspectral and multispectral images. The fusion process is formulated as an inverse problem whose solution is the target image assumed to live in a much lower dimensional subspace. A sparse regularization term is carefully designed, relying on a decomposition of the scene on a set of dictionaries. The dictionary atoms and the corresponding supports of active coding coefficients are learned from the observed images. Then, conditionally on these dictionaries and supports, the fusion problem is solved via alternating optimization with respect to the target image (using the alternating direction method of multipliers) and the coding coefficients. Simulation results demonstrate the efficiency of the proposed algorithm when compared with the state-of-the-art fusion methods.
Tight Error Bounds for Structured Prediction
Venue: arXiv cs.LG 2014
Year: 2014

Structured prediction tasks in machine learning involve the simultaneous prediction of multiple labels. This is typically done by maximizing a score function on the space of labels, which decomposes as a sum of pairwise elements, each depending on two specific labels. Intuitively, the more pairwise terms are used, the better the expected accuracy. However, there is currently no theoretical account of this intuition. This paper takes a significant step in this direction. We formulate the problem as classifying the vertices of a known graph $G=(V,E)$, where the vertices and edges of the graph are labelled and correlate semi-randomly with the ground truth. We show that the prospects for achieving low expected Hamming error depend on the structure of the graph $G$ in interesting ways. For example, if $G$ is a very poor expander, like a path, then large expected Hamming error is inevitable. Our main positive result shows that, for a wide class of graphs including 2D grid graphs common in machine vision applications, there is a polynomial-time algorithm with small and information-theoretically near-optimal expected error. Our results provide a first step toward a theoretical justification for the empirical success of the efficient approximate inference algorithms that are used for structured prediction in models where exact inference is intractable.
Poster Abstract: Bits and Watts: Improving energy disaggregation performance using power line communication modems
Venue: arXiv cs.OH 2014
Year: 2014

Non-intrusive load monitoring (NILM) or energy disaggregation, aims to disaggregate a household's electricity consumption into constituent appliances. More than three decades of work in NILM has resulted in the development of several novel algorithmic approaches. However, despite these advancements, two core challenges still exist: i) disaggregating low power consumption appliances and ii) distinguishing between multiple instances of similar appliances. These challenges are becoming increasingly important due to an increasing number of appliances and increased usage of electronics in homes. Previous approaches have attempted to solve these problems using expensive hardware involving high sampling rates better suited to laboratory settings, or using additional number of sensors, limiting the ease of deployment. In this work, we explore using commercial-off-the-shelf (COTS) power line communication (PLC) modems as an inexpensive and easy to deploy alternative solution to these problems. We use the reduction in bandwidth between two PLC modems, caused due to the change in PLC modulation scheme when different appliances are operated as a signature for an appliance. Since the noise generated in the powerline is dependent both on type and location of an appliance, we believe that our technique based on PLC modems can be a promising addition for solving NILM.
IP Tracing and Active Network Response
Venue: arXiv cs.CR 2014
Year: 2014

Active security is mainly concerned with performing one or more security functions when a host in a communication network is subject to an attack. Such security functions include appropriate actions against attackers. To properly afford active security actions a set of software subsystems should be integrated together so that they can automatically detect and appropriately address any vulnerability in the underlying network. This work presents integrated model for active security response model. The proposed model introduces Active Response Mechanism (ARM) for tracing anonymous attacks in the network back to their source. This work is motivated by the increased frequency and sophistication of denial-of-service attacks and by the difficulty in tracing packets with incorrect, or "spoofed", source addresses. This paper presents within the proposed model two tracing approaches based on: 1.Sleepy Watermark Tracing (SWT) for unauthorized access attacks. 2.Probabilistic Packet Marking (PPM) in the network for Denial of Service (DoS) and Distributed Denial of Service (DDoS) attacks. On the basis of the proposed model a cooperative network security tools such as firewall, intrusion detection system with IP tracing mechanism has been designed for taking a rapid active response against real IPs for attackers. The proposed model is able to detect network vulnerabilities, trace attack source IP and reconfigure the attacked subnetworks.
From "I love you babe" to "leave me alone" - Romantic Relationship Breakups on Twitter
Venue: arXiv cs.SI 2014
Year: 2014

We use public data from Twitter to study the breakups of the romantic relationships of 661 couples. Couples are identified through profile references such as @user1 writing "@user2 is the best boyfriend ever!!". Using this data set we find evidence for a number of existing hypotheses describing psychological processes including (i) pre-relationship closeness being indicative of post-relationship closeness, (ii) "stonewalling", i.e., ignoring messages by a partner, being indicative of a pending breakup, and (iii) post-breakup depression. We also observe a previously undocumented phenomenon of "batch un-friending and being un-friended" where users who break up experience sudden drops of 15-20 followers and friends. Our work shows that public Twitter data can be used to gain new insights into psychological processes surrounding relationship dissolutions, something that most people go through at least once in their lifetime.
Reconfigurable Wireless Networks
Venue: arXiv cs.NI 2014
Year: 2014

Driven by the advent of sophisticated and ubiquitous applications, and the ever-growing need for information, wireless networks are without a doubt steadily evolving into profoundly more complex and dynamic systems. The user demands are progressively rampant, while application requirements continue to expand in both range and diversity. Future wireless networks, therefore, must be equipped with the ability to handle numerous, albeit challenging requirements. Network reconfiguration, considered as a prominent network paradigm, is envisioned to play a key role in leveraging future network performance and considerably advancing current user experiences. This paper presents a comprehensive overview of reconfigurable wireless networks and an in-depth analysis of reconfiguration at all layers of the protocol stack. Such networks characteristically possess the ability to reconfigure and adapt their hardware and software components and architectures, thus enabling flexible delivery of broad services, as well as sustaining robust operation under highly dynamic conditions. The paper offers a unifying framework for research in reconfigurable wireless networks. This should provide the reader with a holistic view of concepts, methods, and strategies in reconfigurable wireless networks. Focus is given to reconfigurable systems in relatively new and emerging research areas such as cognitive radio networks, cross-layer reconfiguration and software-defined networks. In addition, modern networks have to be intelligent and capable of self-organization. Thus, this paper discusses the concept of network intelligence as a means to enable reconfiguration in highly complex and dynamic networks. Finally, the paper is supported with several examples and case studies showing the tremendous impact of reconfiguration on wireless networks.
Joint Optimization of Power Allocation and Training Duration for Uplink Multiuser MIMO Communications
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider a multiuser multiple-input multiple-output (MU-MIMO) communication system between a base station equipped with multiple antennas and multiple mobile users each equipped with a single antenna. The uplink scenario is considered. The uplink channels are acquired by the base station through a training phase. Two linear processing schemes are considered, namely maximum-ratio combining (MRC) and zero-forcing (ZF). We optimize the training period and optimal training energy under the average and peak power constraint so that an achievable sum rate is maximized.
Fixed points of Boolean networks, guessing graphs, and coding theory
Venue: arXiv cs.DM 2014
Year: 2014

In this paper, we are interested in the number of fixed points of functions $f:A^n\to A^n$ over a finite alphabet $A$ defined on a given signed digraph $D$. We first use techniques from network coding to derive some lower bounds on the number of fixed points that only depends on $D$. We then discover relationships between the number of fixed points of $f$ and problems in coding theory, especially the design of codes for the asymmetric channel. Using these relationships, we derive upper and lower bounds on the number of fixed points, which significantly improve those given in the literature. We also unveil some interesting behaviour of the number of fixed points of functions with a given signed digraph when the alphabet varies. We finally prove that signed digraphs with more (disjoint) positive cycles actually do not necessarily have functions with more fixed points.
Compliance error compensation in robotic-based milling
Venue: arXiv cs.RO 2014
Year: 2014

The paper deals with the problem of compliance errors compensation in robotic-based milling. Contrary to previous works that assume that the forces/torques generated by the manufacturing process are constant, the interaction between the milling tool and the workpiece is modeled in details. It takes into account the tool geometry, the number of teeth, the feed rate, the spindle rotation speed and the properties of the material to be processed. Due to high level of the disturbing forces/torques, the developed compensation technique is based on the non-linear stiffness model that allows us to modify the target trajectory taking into account nonlinearities and to avoid the chattering effect. Illustrative example is presented that deals with robotic-based milling of aluminum alloy.
Approximating Betweenness Centrality in Large Evolving Networks
Venue: arXiv cs.SI 2014
Year: 2014

Betweenness centrality ranks the importance of nodes by their participation in all shortest paths of the network. Therefore computing exact betweenness values is impractical in large networks. For static networks, approximation based on randomly sampled paths has been shown to be significantly faster in practice. However, for dynamic networks, no approximation algorithm for betweenness centrality is known that improves on static recomputation. We address this deficit by proposing two incremental approximation algorithms (for weighted and unweighted connected graphs) which provide a provable guarantee on the absolute approximation error. Processing batches of edge insertions, our algorithms yield significant speedups up to a factor of $10^4$ compared to restarting the approximation. This is enabled by investing memory to store and efficiently update shortest paths. As a building block, we also propose an asymptotically faster algorithm for updating the SSSP problem in unweighted graphs. Our experimental study shows that our algorithms are the first to make in-memory computation of a betweenness ranking practical for million-edge semi-dynamic networks. Moreover, our results show that the accuracy is even better than the theoretical guarantees in terms of absolutes errors and the rank of nodes is well preserved, in particular for those with high betweenness.
Constructing Coverability Graphs for Time Basic Petri Nets
Venue: arXiv cs.LO 2014
Year: 2014

Time-Basic Petri nets, is a powerful formalism for modeling real-time systems where time constraints are expressed through time functions of marking's time description associated with transition, representing possible firing times. We introduce a technique for coverability analysis based on the building of a finite graph. This technique further exploits the time anonymous concept [5,6], in order to deal with topologically unbounded nets, exploits the concept of a coverage of TA tokens, i.e., a sort of ω anonymous timestamp. Such a coverability analysis technique is able to construct coverability trees/graphs for unbounded Time-Basic Petri net models. The termination of the algorithm is guaranteed as long as, within the input model, tokens growing without limit, can be anonymized. This means that we are able to manage models that do not exhibit Zeno behavior and do not express actions depending on infinite past events. This is actually a reasonable limitation because, generally, real-world examples do not exhibit such a behavior.
Optimal local routing on Delaunay triangulations defined by empty equilateral triangles
Venue: arXiv cs.CG 2014
Year: 2014

We present a deterministic local routing algorithm that is guaranteed to find a path between any pair of vertices in a half-$θ_6$-graph (the half-$θ_6$-graph is equivalent to the Delaunay triangulation where the empty region is an equilateral triangle). The length of the path is at most $5/\sqrt{3} \approx 2.887$ times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing algorithm can achieve a better routing ratio, thereby proving that our routing algorithm is optimal. This is somewhat surprising because the spanning ratio of the half-$θ_6$-graph is 2, meaning that even though there always exists a path whose lengths is at most twice the Euclidean distance, we cannot always find such a path when routing locally. Since every triangulation can be embedded in the plane as a half-$θ_6$-graph using $O(\log n)$ bits per vertex coordinate via Schnyder's embedding scheme (SODA 1990), our result provides a competitive local routing algorithm for every such embedded triangulation. Finally, we show how our routing algorithm can be adapted to provide a routing ratio of $15/\sqrt{3} \approx 8.660$ on two bounded degree subgraphs of the half-$θ_6$-graph.