OpenRaiser/Intern-Atlas huggingface dataset:
Bounded Policy Synthesis for POMDPs with Safe-Reachability Objectives
Venue: arXiv cs.RO 2018
Year: 2018

Planning robust executions under uncertainty is a fundamental challenge for building autonomous robots. Partially Observable Markov Decision Processes (POMDPs) provide a standard framework for modeling uncertainty in many applications. In this work, we study POMDPs with safe-reachability objectives, which require that with a probability above some threshold, a goal state is eventually reached while keeping the probability of visiting unsafe states below some threshold. This POMDP formulation is different from the traditional POMDP models with optimality objectives and we show that in some cases, POMDPs with safe-reachability objectives can provide a better guarantee of both safety and reachability than the existing POMDP models through an example. A key algorithmic problem for POMDPs is policy synthesis, which requires reasoning over a vast space of beliefs (probability distributions). To address this challenge, we introduce the notion of a goal-constrained belief space, which only contains beliefs reachable from the initial belief under desired executions that can achieve the given safe-reachability objective. Our method compactly represents this space over a bounded horizon using symbolic constraints, and employs an incremental Satisfiability Modulo Theories (SMT) solver to efficiently search for a valid policy over it. We evaluate our method using a case study involving a partially observable robotic domain with uncertain obstacles. The results show that our method can synthesize policies over large belief spaces with a small number of SMT solver calls by focusing on the goal-constrained belief space.
Performance Dynamics and Success in Online Games
Venue: arXiv cs.SI 2018
Year: 2018

Online data provide a way to monitor how users behave in social systems like social networks and online games, and understand which features turn an ordinary individual into a successful one. Here, we propose to study individual performance and success in Multiplayer Online Battle Arena (MOBA) games. Our purpose is to identify those behaviors and playing styles that are characteristic of players with high skill level and that distinguish them from other players. To this aim, we study Defense of the ancient 2 (Dota 2), a popular MOBA game. Our findings highlight three main aspects to be successful in the game: (i) players need to have a warm-up period to enhance their performance in the game; (ii) having a long in-game experience does not necessarily translate in achieving better skills; but rather, (iii) players that reach high skill levels differentiate from others because of their aggressive playing strategy, which implies to kill opponents more often than cooperating with teammates, and trying to give an early end to the match.
Communication-Efficient Search for an Approximate Closest Lattice Point
Venue: arXiv cs.IT 2018
Year: 2018

We consider the problem of finding the closest lattice point to a vector in n-dimensional Euclidean space when each component of the vector is available at a distinct node in a network. Our objectives are (i) minimize the communication cost and (ii) obtain the error probability. The approximate closest lattice point considered here is the one obtained using the nearest-plane (Babai) algorithm. Assuming a triangular special basis for the lattice, we develop communication-efficient protocols for computing the approximate lattice point and determine the communication cost for lattices of dimension n>1. Based on available parameterizations of reduced bases, we determine the error probability of the nearest plane algorithm for two dimensional lattices analytically, and present a computational error estimation algorithm in three dimensions. For dimensions 2 and 3, our results show that the error probability increases with the packing density of the lattice.
Earthmover Resilience and Testing in Ordered Structures
Venue: arXiv cs.DS 2018
Year: 2018

One of the main challenges in property testing is to characterize those properties that are testable with a constant number of queries. For unordered structures such as graphs and hypergraphs this task has been mostly settled. However, for ordered structures such as strings, images, and ordered graphs, the characterization problem seems very difficult in general. In this paper, we identify a wide class of properties of ordered structures - the earthmover resilient (ER) properties - and show that the "good behavior" of such properties allows us to obtain general testability results that are similar to (and more general than) those of unordered graphs. A property P is ER if, roughly speaking, slight changes in the order of the elements in an object satisfying P cannot make this object far from P. The class of ER properties includes, e.g., all unordered graph properties, many natural visual properties of images, such as convexity, and all hereditary properties of ordered graphs and images. A special case of our results implies, building on a recent result of Alon and the authors, that the distance of a given image or ordered graph from any hereditary property can be estimated (with good probability) up to a constant additive error, using a constant number of queries.
Algorithms for the Greater Good! On Mental Modeling and Acceptable Symbiosis in Human-AI Collaboration
Venue: arXiv cs.AI 2018
Year: 2018

Effective collaboration between humans and AI-based systems requires effective modeling of the human in the loop, both in terms of the mental state as well as the physical capabilities of the latter. However, these models can also open up pathways for manipulating and exploiting the human in the hopes of achieving some greater good, especially when the intent or values of the AI and the human are not aligned or when they have an asymmetrical relationship with respect to knowledge or computation power. In fact, such behavior does not necessarily require any malicious intent but can rather be borne out of cooperative scenarios. It is also beyond simple misinterpretation of intents, as in the case of value alignment problems, and thus can be effectively engineered if desired. Such techniques already exist and pose several unresolved ethical and moral questions with regards to the design of autonomy. In this paper, we illustrate some of these issues in a teaming scenario and investigate how they are perceived by participants in a thought experiment.
ReNN: Rule-embedded Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

The artificial neural network shows powerful ability of inference, but it is still criticized for lack of interpretability and prerequisite needs of big dataset. This paper proposes the Rule-embedded Neural Network (ReNN) to overcome the shortages. ReNN first makes local-based inferences to detect local patterns, and then uses rules based on domain knowledge about the local patterns to generate rule-modulated map. After that, ReNN makes global-based inferences that synthesizes the local patterns and the rule-modulated map. To solve the optimization problem caused by rules, we use a two-stage optimization strategy to train the ReNN model. By introducing rules into ReNN, we can strengthen traditional neural networks with long-term dependencies which are difficult to learn with limited empirical dataset, thus improving inference accuracy. The complexity of neural networks can be reduced since long-term dependencies are not modeled with neural connections, and thus the amount of data needed to optimize the neural networks can be reduced. Besides, inferences from ReNN can be analyzed with both local patterns and rules, and thus have better interpretability. In this paper, ReNN has been validated with a time-series detection problem.
Pilot study for the COST Action "Reassembling the Republic of Letters": language-driven network analysis of letters from the Hartlib's Papers
Venue: arXiv cs.CL 2018
Year: 2018

The present report summarizes an exploratory study which we carried out in the context of the COST Action IS1310 "Reassembling the Republic of Letters, 1500-1800", and which is relevant to the activities of Working Group 3 "Texts and Topics" and Working Group 2 "People and Networks". In this study we investigated the use of Natural Language Processing (NLP) and Network Text Analysis on a small sample of seventeenth-century letters selected from Hartlib Papers, whose records are in one of the catalogues of Early Modern Letters Online (EMLO) and whose online edition is available on the website of the Humanities Research Institute at the University of Sheffield (http://www.hrionline.ac.uk/hartlib/). We outline the NLP pipeline used to automatically process the texts into a network representation, in order to identify the texts' "narrative centrality", i.e. the most central entities in the texts, and the relations between them.
Modeling Influence with Semantics in Social Networks: a Survey
Venue: arXiv cs.IR 2018
Year: 2018

The discovery of influential entities in all kinds of networks (e.g. social, digital, or computer) has always been an important field of study. In recent years, Online Social Networks (OSNs) have been established as a basic means of communication and often influencers and opinion makers promote politics, events, brands or products through viral content. In this work, we present a systematic review across i) online social influence metrics, properties, and applications and ii) the role of semantic in modeling OSNs information. We end up with the conclusion that both areas can jointly provide useful insights towards the qualitative assessment of viral user-generated content, as well as for modeling the dynamic properties of influential content and its flow dynamics.
A Linear Complementarity Theorem to solve any Satisfiability Problem in conjunctive normal form in polynomial time
Venue: arXiv cs.CC 2018
Year: 2018

Any satisfiability problem in conjunctive normal form can be solved in polynomial time by reducing it to a 3-sat formulation and transforming this to a Linear Complementarity problem (LCP) which is then solved as a linear program (LP). Any instance in this problem class, reduced to a LCP may be solved, provided certain necessary and sufficient conditions hold. The proof that these conditions will be satisfied for all problems in this class is the contribution of this paper and this derivation requires a nonlinear Instrumentalist methodology rather than a Realistic one and confirms the advantages of a Variational Inequalities implementation.
Model Based Active Slosh Damping Experiment
Venue: arXiv cs.SY 2018
Year: 2018

This paper presents a model based experimental investigation to demonstrate the usefulness of an active damping strategy to manage fluid sloshing motion in spacecraft tanks. The active damping strategy is designed to reduce the degrading impact on maneuvering and pointing performance via a force feedback strategy. Many problems have been encountered until now, such as instability of the closed loop system, excessive consumption in the attitude propellant or problems for engine re-ignition in upper stages. Mostly, they have been addressed in a passive way via the design of baffles and membranes, which on their own have mass and constructive impacts. Active management of propellant motion in launchers and satellites has the potential to increase performance on various levels. This paper demonstrates active slosh management using force feedback for the compensation of the slosh resonances. Force sensors between tank and the carrying structure provide information of the fluid motion via the reaction force. The control system is designed to generate an appropriate acceleration profile that leads to desired attenuation profiles in amplitude, frequency and time. Two robust control design methods, one based on $μ$ design and the other on parametric structured design based on non-smooth optimization of the worst-case $H_{\infty}$ norm, are applied. The controller is first tested with a computational fluid dynamics simulation in the loop. Finally a water tank mounted on a Hexapod with up to $1100$ liter is used to evaluate the control performance. The paper illustrates that is possible to actively influence sloshing via closed loop.
Simultaneous Deployment and Tracking Multi-Robot Strategies with Connectivity Maintenance
Venue: arXiv cs.RO 2018
Year: 2018

Multi robot teams composed by ground and aerial vehicles have gained attention during the last years. We present a scenario where both types of robots must monitor the same area from different view points. In this paper we propose two Lloyd-based tracking strategies to allow the ground robots (agents) follow the aerial ones (targets), keeping the connectivity between the agents. The first strategy establishes density functions on the environment so that the targets acquire more importance than other zones, while the second one iteratively modifies the virtual limits of the working area depending on the positions of the targets. We consider the connectivity maintenance due to the fact that coverage tasks tend to spread the agents as much as possible, which is addressed by restricting their motions so that they keep the links of a Minimum Spanning Tree of the communication graph. We provide a thorough parametric study of the performance of the proposed strategies under several simulated scenarios. In addition, the methods are implemented and tested using realistic robotic simulation environments and real experiments.
Anomaly detection in wide area network mesh using two machine learning anomaly detection algorithms
Venue: arXiv cs.NI 2018
Year: 2018

Anomaly detection is the practice of identifying items or events that do not conform to an expected behavior or do not correlate with other items in a dataset. It has previously been applied to areas such as intrusion detection, system health monitoring, and fraud detection in credit card transactions. In this paper, we describe a new method for detecting anomalous behavior over network performance data, gathered by perfSONAR, using two machine learning algorithms: Boosted Decision Trees (BDT) and Simple Feedforward Neural Network. The effectiveness of each algorithm was evaluated and compared. Both have shown sufficient performance and sensitivity.
Surprise in Elections
Venue: arXiv cs.GT 2018
Year: 2018

Elections involving a very large voter population often lead to outcomes that surprise many. This is particularly important for the elections in which results affect the economy of a sizable population. A better prediction of the true outcome helps reduce the surprise and keeps the voters prepared. This paper starts from the basic observation that individuals in the underlying population build estimates of the distribution of preferences of the whole population based on their local neighborhoods. The outcome of the election leads to a surprise if these local estimates contradict the outcome of the election for some fixed voting rule. To get a quantitative understanding, we propose a simple mathematical model of the setting where the individuals in the population and their connections (through geographical proximity, social networks etc.) are described by a random graph with connection probabilities that are biased based on the preferences of the individuals. Each individual also has some estimate of the bias in their connections. We show that the election outcome leads to a surprise if the discrepancy between the estimated bias and the true bias in the local connections exceeds a certain threshold, and confirm the phenomenon that surprising outcomes are associated only with {\em closely contested elections}. We compare standard voting rules based on their performance on surprise and show that they have different behavior for different parts of the population. It also hints at an impossibility that a single voting rule will be less surprising for {\em all} parts of a population. Finally, we experiment with the UK-EU referendum (a.k.a.\ Brexit) dataset that attest some of our theoretical predictions.
REOH: Using Probabilistic Network for Runtime Energy Optimization of Heterogeneous Systems
Venue: arXiv cs.DC 2018
Year: 2018

Significant efforts have been devoted to choosing the best configuration of a computing system to run an application energy efficiently. However, available tuning approaches mainly focus on homogeneous systems and are inextensible for heterogeneous systems which include several components (e.g., CPUs, GPUs) with different architectures. This study proposes a holistic tuning approach called REOH using probabilistic network to predict the most energy-efficient configuration (i.e., which platform and its setting) of a heterogeneous system for running a given application. Based on the computation and communication patterns from Berkeley dwarfs, we conduct experiments to devise the training set including 7074 data samples covering varying application patterns and characteristics. Validating the REOH approach on heterogeneous systems including CPUs and GPUs shows that the energy consumption by the REOH approach is close to the optimal energy consumption by the Brute Force approach while saving 17% of sampling runs compared to the previous (homogeneous) approach using probabilistic network. Based on the REOH approach, we develop an open-source energy-optimizing runtime framework for selecting an energy efficient configuration of a heterogeneous system for a given application at runtime.
Compressed Anomaly Detection with Multiple Mixed Observations
Venue: arXiv cs.IT 2018
Year: 2018

We consider a collection of independent random variables that are identically distributed, except for a small subset which follows a different, anomalous distribution. We study the problem of detecting which random variables in the collection are governed by the anomalous distribution. Recent work proposes to solve this problem by conducting hypothesis tests based on mixed observations (e.g. linear combinations) of the random variables. Recognizing the connection between taking mixed observations and compressed sensing, we view the problem as recovering the "support" (index set) of the anomalous random variables from multiple measurement vectors (MMVs). Many algorithms have been developed for recovering jointly sparse signals and their support from MMVs. We establish the theoretical and empirical effectiveness of these algorithms at detecting anomalies. We also extend the LASSO algorithm to an MMV version for our purpose. Further, we perform experiments on synthetic data, consisting of samples from the random variables, to explore the trade-off between the number of mixed observations per sample and the number of samples required to detect anomalies.
A Continuous - Time Quantum Walk for Attributed Graphs Matching
Venue: arXiv cs.DS 2018
Year: 2018

Diverse facets Of the Theory of Quantum Walks on Graph are reviewed Till now .In specific, Quantum network routing, Quantum Walk Search Algorithm, Element distinctness associated to the eigenvalues of Graphs and the use of these relation /connection in the study of Quantum walks is furthermore described. Different Researchers had contribution and put their benchmark idea Pertaining with this research concept. I furthermore try to investigate recent Application of Quantum walks, In specific the problem pertained with Graph matching i.e Matching nodes(vertices) of the Graphs. In this research paper,I consider how Continuous-time quantum walk (CTQW) can be directed to Graph-matching problems. The matching problem is abstracted using weighted(attributed) Graphs that connects vertices's of one Graph to other and Try to compute the distance b/n those Graphs Node's Beside that finding the matched nodes and the Cost related to Matching. eventually measuring the distance between two Graphs which might have different size then by using k-nearest neighbor (k-NN) method try to classifying those graph based on closest training examples in the feature space.
ConvCSNet: A Convolutional Compressive Sensing Framework Based on Deep Learning
Venue: arXiv cs.CV 2018
Year: 2018

Compressive sensing (CS), aiming to reconstruct an image/signal from a small set of random measurements has attracted considerable attentions in recent years. Due to the high dimensionality of images, previous CS methods mainly work on image blocks to avoid the huge requirements of memory and computation, i.e., image blocks are measured with Gaussian random matrices, and the whole images are recovered from the reconstructed image blocks. Though efficient, such methods suffer from serious blocking artifacts. In this paper, we propose a convolutional CS framework that senses the whole image using a set of convolutional filters. Instead of reconstructing individual blocks, the whole image is reconstructed from the linear convolutional measurements. Specifically, the convolutional CS is implemented based on a convolutional neural network (CNN), which performs both the convolutional CS and nonlinear reconstruction. Through end-to-end training, the sensing filters and the reconstruction network can be jointly optimized. To facilitate the design of the CS reconstruction network, a novel two-branch CNN inspired from a sparsity-based CS reconstruction model is developed. Experimental results show that the proposed method substantially outperforms previous state-of-the-art CS methods in term of both PSNR and visual quality.
Internet of things forensics: Challenges and Case Study
Venue: arXiv cs.CR 2018
Year: 2018

Today is the era of Internet of Things (IoT), millions of machines such as cars, smoke detectors, watches, glasses, webcams, etc. are being connected to the Internet. The number of machines that possess the ability of remote access to monitor and collect data is continuously increasing. This development makes, on one hand, the human life more comfort- able, convenient, but it also raises on other hand issues on security and privacy. However, this development also raises challenges for the digital investigator when IoT devices involve in criminal scenes. Indeed, current research in the literature focuses on security and privacy for IoT environments rather than methods or techniques of forensic acquisition and analysis for IoT devices. Therefore, in this paper, we discuss firstly different aspects related to IoT forensics and then focus on the cur- rent challenges. We also describe forensic approaches for a IoT device smartwatch as a case study. We analyze forensic artifacts retrieved from smartwatch devices and discuss on evidence found aligned with challenges in IoT forensics
Efficient Algorithms for Measuring the Funnel-likeness of DAGs
Venue: arXiv cs.DS 2018
Year: 2018

Funnels are a new natural subclass of DAGs. Intuitively, a DAG is a funnel if every source-sink path can be uniquely identified by one of its arcs. Funnels are an analog to trees for directed graphs that is more restrictive than DAGs but more expressive than in-/out-trees. Computational problems such as finding vertex-disjoint paths or tracking the origin of memes remain NP-hard on DAGs while on funnels they become solvable in polynomial time. Our main focus is the algorithmic complexity of finding out how funnel-like a given DAG is. To this end, we study the NP-hard problem of computing the arc-deletion distance to a funnel of a given DAG. We develop efficient exact and approximation algorithms for the problem and test them on synthetic random graphs and real-world graphs.