OpenRaiser/Intern-Atlas huggingface dataset:
A Game-Theoretic Taxonomy and Survey of Defensive Deception for Cybersecurity and Privacy
Venue: arXiv cs.CR 2019
Year: 2019

Cyberattacks on both databases and critical infrastructure have threatened public and private sectors. Ubiquitous tracking and wearable computing have infringed upon privacy. Advocates and engineers have recently proposed using defensive deception as a means to leverage the information asymmetry typically enjoyed by attackers as a tool for defenders. The term deception, however, has been employed broadly and with a variety of meanings. In this paper, we survey 24 articles from 2008-2018 that use game theory to model defensive deception for cybersecurity and privacy. Then we propose a taxonomy that defines six types of deception: perturbation, moving target defense, obfuscation, mixing, honey-x, and attacker engagement. These types are delineated by their information structures, agents, actions, and duration: precisely concepts captured by game theory. Our aims are to rigorously define types of defensive deception, to capture a snapshot of the state of the literature, to provide a menu of models which can be used for applied research, and to identify promising areas for future work. Our taxonomy provides a systematic foundation for understanding different types of defensive deception commonly encountered in cybersecurity and privacy.
Hierarchical decomposition of LTL synthesis problem for nonlinear control systems
Venue: arXiv cs.SY 2019
Year: 2019

This paper deals with the control synthesis problem for a continuous nonlinear dynamical system under a Linear Temporal Logic (LTL) formula. The proposed solution is a top-down hierarchical decomposition of the control problem involving three abstraction layers of the problem, iteratively solved from the coarsest to the finest. The LTL planning is first solved on a small transition system only describing the regions of interest involved in the LTL formula. For each pair of consecutive regions of interest in the resulting accepting path satisfying the LTL formula, a discrete plan is then constructed in the partitioned workspace to connect these two regions while avoiding unsafe regions. Finally, an abstraction refinement approach is applied to synthesize a controller for the dynamical system to follow each discrete plan. The second main contribution, used in the third abstraction layer, is a new monotonicity-based method to over-approximate the finite-time reachable set of any continuously differentiable system. The proposed framework is demonstrated in simulation for a motion planning problem of a mobile robot modeled as a disturbed unicycle.
Visual Explanation by Interpretation: Improving Visual Feedback Capabilities of Deep Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

Interpretation and explanation of deep models is critical towards wide adoption of systems that rely on them. In this paper, we propose a novel scheme for both interpretation as well as explanation in which, given a pretrained model, we automatically identify internal features relevant for the set of classes considered by the model, without relying on additional annotations. We interpret the model through average visualizations of this reduced set of features. Then, at test time, we explain the network prediction by accompanying the predicted class label with supporting visualizations derived from the identified features. In addition, we propose a method to address the artifacts introduced by stridded operations in deconvNet-based visualizations. Moreover, we introduce an8Flower, a dataset specifically designed for objective quantitative evaluation of methods for visual explanation.Experiments on the MNIST,ILSVRC12,Fashion144k and an8Flower datasets show that our method produces detailed explanations with good coverage of relevant features of the classes of interest
Boolean Tensor Decomposition for Conjunctive Queries with Negation
Venue: arXiv cs.DB 2019
Year: 2019

We propose an algorithm for answering conjunctive queries with negation, where the negated relations have bounded degree. Its data complexity matches that of the best known algorithms for the positive subquery of the input query and is expressed in terms of the fractional hypertree width and the submodular width. The query complexity depends on the structure of the negated subquery; in general it is exponential in the number of join variables occurring in negated relations yet it becomes polynomial for several classes of queries. This algorithm relies on several contributions. We show how to rewrite queries with negation on bounded-degree relations into equivalent conjunctive queries with not-all-equal (NAE) predicates, which are a multi-dimensional analog of disequality (not-equal). We then generalize the known color-coding technique to conjunctions of NAE predicates and explain it via a Boolean tensor decomposition of conjunctions of NAE predicates. This decomposition can be achieved via a probabilistic construction that can be derandomized efficiently.
Multisensor Poisson Multi-Bernoulli Filter for Joint Target-Sensor State Tracking
Venue: arXiv cs.SY 2019
Year: 2019

In a typical multitarget tracking (MTT) scenario, the sensor state is either assumed known, or tracking is performed in the sensor's (relative) coordinate frame. This assumption does not hold when the sensor, e.g., an automotive radar, is mounted on a vehicle, and the target state should be represented in a global (absolute) coordinate frame. Then it is important to consider the uncertain location of the vehicle on which the sensor is mounted for MTT. In this paper, we present a multisensor low complexity Poisson multi-Bernoulli MTT filter, which jointly tracks the uncertain vehicle state and target states. Measurements collected by different sensors mounted on multiple vehicles with varying location uncertainty are incorporated sequentially based on the arrival of new sensor measurements. In doing so, targets observed from a sensor mounted on a well-localized vehicle reduce the state uncertainty of other poorly localized vehicles, provided that a common non-empty subset of targets is observed. A low complexity filter is obtained by approximations of the joint sensor-feature state density minimizing the Kullback-Leibler divergence (KLD). Results from synthetic as well as experimental measurement data, collected in a vehicle driving scenario, demonstrate the performance benefits of joint vehicle-target state tracking.
APEx: Accuracy-Aware Differentially Private Data Exploration
Venue: arXiv cs.DB 2019
Year: 2019

Organizations are increasingly interested in allowing external data scientists to explore their sensitive datasets. Due to the popularity of differential privacy, data owners want the data exploration to ensure provable privacy guarantees. However, current systems for answering queries with differential privacy place an inordinate burden on the data analysts to understand differential privacy, manage their privacy budget, and even implement new algorithms for noisy query answering. Moreover, current systems do not provide any guarantees to the data analyst on the quality they care about, namely accuracy of query answers. We present APEx, a novel system that allows data analysts to pose adaptively chosen sequences of queries along with required accuracy bounds. By translating queries and accuracy bounds into differentially private algorithms with the least privacy loss, APEx returns query answers to the data analyst that meet the accuracy bounds, and proves to the data owner that the entire data exploration process is differentially private. Our comprehensive experimental study on real datasets demonstrates that APEx can answer a variety of queries accurately with moderate to small privacy loss, and can support data exploration for entity resolution with high accuracy under reasonable privacy settings.
Emotion-Based Crowd Simulation Model Based on Physical Strength Consumption for Emergency Scenarios
Venue: arXiv cs.MA 2019
Year: 2019

Increasing attention is being given to the modeling and simulation of traffic flow and crowd movement, two phenomena that both deal with interactions between pedestrians and cars in many situations. In particular, crowd simulation is important for understanding mobility and transportation patterns. In this paper, we propose an emotion-based crowd simulation model integrating physical strength consumption. Inspired by the theory of "the devoted actor," the movements of each individual in our model are determined by modeling the influence of physical strength consumption and the emotion of panic. In particular, human physical strength consumption is computed using a physics-based numerical method. Inspired by the James-Lange theory, panic levels are estimated by means of an enhanced emotional contagion model that leverages the inherent relationship between physical strength consumption and panic. To the best of our knowledge, our model is the first method integrating physical strength consumption into an emotion-based crowd simulation model by exploiting the relationship between physical strength consumption and emotion. We highlight the performance on different scenarios and compare the resulting behaviors with real-world video sequences. Our approach can reliably predict changes in physical strength consumption and panic levels of individuals in an emergency situation.
Sampling-Based Methods for Factored Task and Motion Planning
Venue: arXiv cs.RO 2019
Year: 2019

This paper presents a general-purpose formulation of a large class of discrete-time planning problems, with hybrid state and control-spaces, as factored transition systems. Factoring allows state transitions to be described as the intersection of several constraints each affecting a subset of the state and control variables. Robotic manipulation problems with many movable objects involve constraints that only affect several variables at a time and therefore exhibit large amounts of factoring. We develop a theoretical framework for solving factored transition systems with sampling-based algorithms. The framework characterizes conditions on the submanifold in which solutions lie, leading to a characterization of robust feasibility that incorporates dimensionality-reducing constraints. It then connects those conditions to corresponding conditional samplers that can be composed to produce values on this submanifold. We present two domain-independent, probabilistically complete planning algorithms that take, as input, a set of conditional samplers. We demonstrate the empirical efficiency of these algorithms on a set of challenging task and motion planning problems involving picking, placing, and pushing.
A diagrammatic calculus of fermionic quantum circuits
Venue: arXiv cs.LO 2019
Year: 2019

We introduce the fermionic ZW calculus, a string-diagrammatic language for fermionic quantum computing (FQC). After defining a fermionic circuit model, we present the basic components of the calculus, together with their interpretation, and show how the main physical gates of interest in FQC can be represented in our language. We then list our axioms, and derive some additional equations. We prove that the axioms provide a complete equational axiomatisation of the monoidal category whose objects are systems of finitely many local fermionic modes (LFMs), with maps that preserve or reverse the parity of states, and the tensor product as monoidal product. We achieve this through a procedure that rewrites any diagram in a normal form. As an example, we show how the statistics of a fermionic Mach-Zehnder interferometer can be calculated in the diagrammatic language. We conclude by giving a diagrammatic treatment of the dual-rail encoding, a standard method in optical quantum computing used to perform universal quantum computation.
Approximate solutions to large nonsymmetric differential Riccati problems with applications to transport theory
Venue: arXiv cs.NA 2019
Year: 2019

In the present paper, we consider large scale nonsymmetric differential matrix Riccati equations with low rank right hand sides. These matrix equations appear in many applications such as control theory, transport theory, applied probability and others. We show how to apply Krylov-type methods such as the extended block Arnoldi algorithm to get low rank approximate solutions. The initial problem is projected onto small subspaces to get low dimensional nonsymmetric differential equations that are solved using the exponential approximation or via other integration schemes such as Backward Differentiation Formula (BDF) or Rosenbrok method. We also show how these technique could be easily used to solve some problems from the well known transport equation. Some numerical experiments are given to illustrate the application of the proposed methods to large-scale problems
A tractable class of binary VCSPs via M-convex intersection
Venue: arXiv cs.DM 2019
Year: 2019

A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions. An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper and Živný classified the tractability of binary VCSP instances according to the concept of "triangle," and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa, Murota, and Živný made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two quadratic M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given. In this paper, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be represented as the sum of two quadratic M-convex functions and can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.
Grassmannian Codes with New Distance Measures for Network Coding
Venue: arXiv cs.IT 2019
Year: 2019

Grassmannian codes are known to be useful in error-correction for random network coding. Recently, they were used to prove that vector network codes outperform scalar linear network codes, on multicast networks, with respect to the alphabet size. The multicast networks which were used for this purpose are generalized combination networks. In both the scalar and the vector network coding solutions, the subspace distance is used as the distance measure for the codes which solve the network coding problem in the generalized combination networks. In this work we show that the subspace distance can be replaced with two other possible distance measures which generalize the subspace distance. These two distance measures are shown to be equivalent under an orthogonal transformation. It is proved that the Grassmannian codes with the new distance measures generalize the Grassmannian codes with the subspace distance and the subspace designs with the strength of the design. Furthermore, optimal Grassmannian codes with the new distance measureshave minimal requirements for network coding solutions of some generalized combination networks. The coding problems related to these two distance measures, especially with respect to network coding, are discussed. Finally, by using these new concepts it is proved that codes in the Hamming scheme form a subfamily of the Grassmannian codes.
Representation Learning with Autoencoders for Electronic Health Records: A Comparative Study
Venue: arXiv cs.LG 2019
Year: 2019

Increasing volume of Electronic Health Records (EHR) in recent years provides great opportunities for data scientists to collaborate on different aspects of healthcare research by applying advanced analytics to these EHR clinical data. A key requirement however is obtaining meaningful insights from high dimensional, sparse and complex clinical data. Data science approaches typically address this challenge by performing feature learning in order to build more reliable and informative feature representations from clinical data followed by supervised learning. In this paper, we propose a predictive modeling approach based on deep learning based feature representations and word embedding techniques. Our method uses different deep architectures (stacked sparse autoencoders, deep belief network, adversarial autoencoders and variational autoencoders) for feature representation in higher-level abstraction to obtain effective and robust features from EHRs, and then build prediction models on top of them. Our approach is particularly useful when the unlabeled data is abundant whereas labeled data is scarce. We investigate the performance of representation learning through a supervised learning approach. Our focus is to present a comparative study to evaluate the performance of different deep architectures through supervised learning and provide insights in the choice of deep feature representation techniques. Our experiments demonstrate that for small data sets, stacked sparse autoencoder demonstrates a superior generality performance in prediction due to sparsity regularization whereas variational autoencoders outperform the competing approaches for large data sets due to its capability of learning the representation distribution.
Five Proofs of Chernoff's Bound with Applications
Venue: arXiv cs.DM 2019
Year: 2019

We discuss five ways of proving Chernoff's bound and show how they lead to different extensions of the basic bound.
Formalized Conceptual Spaces with a Geometric Representation of Correlations
Venue: arXiv cs.AI 2019
Year: 2019

The highly influential framework of conceptual spaces provides a geometric way of representing knowledge. Instances are represented by points in a similarity space and concepts are represented by convex regions in this space. After pointing out a problem with the convexity requirement, we propose a formalization of conceptual spaces based on fuzzy star-shaped sets. Our formalization uses a parametric definition of concepts and extends the original framework by adding means to represent correlations between different domains in a geometric way. Moreover, we define various operations for our formalization, both for creating new concepts from old ones and for measuring relations between concepts. We present an illustrative toy-example and sketch a research project on concept formation that is based on both our formalization and its implementation.
LDPC Codes with Local and Global Decoding
Venue: arXiv cs.IT 2019
Year: 2019

This paper presents a theoretical study of a new type of LDPC codes motivated by practical storage applications. LDPCL codes (suffix L represents locality) are LDPC codes that can be decoded either as usual over the full code block, or locally when a smaller sub-block is accessed (to reduce latency). LDPCL codes are designed to maximize the error-correction performance vs. rate in the usual (global) mode, while at the same time providing a certain performance in the local mode. We develop a theoretical framework for the design of LDPCL codes. Our results include a design tool to construct an LDPC code with two data-protection levels: local and global. We derive theoretical results supporting this tool and we show how to achieve capacity with it. A trade-off between the gap to capacity and the number of full-block accesses is studied, and a finite-length analysis of ML decoding is performed to exemplify a trade-off between the locality capability and the full-block error-correcting capability.
Conditional Probability Models for Deep Image Compression
Venue: arXiv cs.CV 2019
Year: 2019

Deep Neural Networks trained as image auto-encoders have recently emerged as a promising direction for advancing the state-of-the-art in image compression. The key challenge in learning such networks is twofold: To deal with quantization, and to control the trade-off between reconstruction error (distortion) and entropy (rate) of the latent image representation. In this paper, we focus on the latter challenge and propose a new technique to navigate the rate-distortion trade-off for an image compression auto-encoder. The main idea is to directly model the entropy of the latent representation by using a context model: A 3D-CNN which learns a conditional probability model of the latent distribution of the auto-encoder. During training, the auto-encoder makes use of the context model to estimate the entropy of its representation, and the context model is concurrently updated to learn the dependencies between the symbols in the latent representation. Our experiments show that this approach, when measured in MS-SSIM, yields a state-of-the-art image compression system based on a simple convolutional auto-encoder.
Some Generalizations of Good Integers and Their Applications in the Study of Self-Dual Negacyclic Codes
Venue: arXiv cs.IT 2019
Year: 2019

Good integers introduced in 1997 form an interesting family of integers that has been continuously studied due to their rich number theoretical properties and wide applications. In this paper, we have focused on classes of $2^β$-good integers, $2^β$-oddly-good integers, and $2^β$-evenly-good integers which are generalizations of good integers. Properties of such integers have been given as well as their applications in characterizing and enumerating self-dual negacyclic codes over finite fields. An alternative proof for the characterization of the existence of a self-dual negacyclic code over finite fields has been given in terms of such generalized good integers. A general enumeration formula for the number of self-dual negacyclic codes of length $n$ over finite fields has been established. For some specific lengths, explicit formulas have been provided as well. Some known results on self-dual negacyclic codes over finite fields can be formalized and viewed as special cases of this work.
Strategies for Stable Merge Sorting
Venue: arXiv cs.DS 2019
Year: 2019

We introduce new stable natural merge sort algorithms, called $2$-merge sort and $α$-merge sort. We prove upper and lower bounds for several merge sort algorithms, including Timsort, Shivers' sort, $α$-stack sorts, and our new $2$-merge and $α$-merge sorts. The upper and lower bounds have the forms $c \cdot n \log m$ and $c \cdot n \log n$ for inputs of length~$n$ comprising $m$~monotone runs. For Timsort, we prove a lower bound of $(1.5 - o(1)) n \log n$. For $2$-merge sort, we prove optimal upper and lower bounds of approximately $(1.089 \pm o(1))n \log m$. We prove similar asymptotically matching upper and lower bounds for $α$-merge sort, when $φ< α< 2$, where $φ$ is the golden ratio. Our bounds are in terms of merge cost; this upper bounds the number of comparisons and accurately models runtime. The merge strategies can be used for any stable merge sort, not just natural merge sorts. The new $2$-merge and $α$-merge sorts have better worst-case merge cost upper bounds and are slightly simpler to implement than the widely-used Timsort; they also perform better in experiments. We report also experimental comparisons with algorithms developed by Munro-Wild and Jugé subsequently to the results of the present paper.