OpenRaiser/Intern-Atlas huggingface dataset:
An automated model-based test oracle for access control systems
Venue: arXiv cs.SE 2018
Year: 2018

In the context of XACML-based access control systems, an intensive testing activity is among the most adopted means to assure that sensible information or resources are correctly accessed. Unfortunately, it requires a huge effort for manual inspection of results: thus automated verdict derivation is a key aspect for improving the cost-effectiveness of testing. To this purpose, we introduce XACMET, a novel approach for automated model-based oracle definition. XACMET defines a typed graph, called the XAC-Graph, that models the XACML policy evaluation. The expected verdict of a specific request execution can thus be automatically derived by executing the corresponding path in such graph. Our validation of the XACMET prototype implementation confirms the effectiveness of the proposed approach.
Ultimate Boundedness for Switched Systems with Multiple Equilibria Under Disturbances
Venue: arXiv cs.SY 2018
Year: 2018

In this paper, we investigate the robustness to external disturbances of switched discrete and continuous systems with multiple equilibria. It is shown that if each subsystem of the switched system is Input-to-State Stable (ISS), then under switching signals that satisfy an average dwell-time bound, the solutions are ultimately bounded within a compact set. Furthermore, the size of this set varies monotonically with the supremum norm of the disturbance signal. It is observed that when the subsystems share a common equilibrium, ISS is recovered for solutions of the corresponding switched system; hence, the results in this paper are a natural generalization of classical results in switched systems that exhibit a common equilibrium. Additionally, we provide a method to analytically compute the average dwell time if each subsystem possesses a quadratic ISS-Lyapunov function. Our motivation for studying this class of switched systems arises from certain motion planning problems in robotics, where primitive motions, each corresponding to an equilibrium point of a dynamical system, must be composed to realize a task. However, the results are relevant to a much broader class of applications, in which composition of different modes of behavior is required.
Structure-Preserving Transformation: Generating Diverse and Transferable Adversarial Examples
Venue: arXiv cs.LG 2018
Year: 2018

Adversarial examples are perturbed inputs designed to fool machine learning models. Most recent works on adversarial examples for image classification focus on directly modifying pixels with minor perturbations. A common requirement in all these works is that the malicious perturbations should be small enough (measured by an L_p norm for some p) so that they are imperceptible to humans. However, small perturbations can be unnecessarily restrictive and limit the diversity of adversarial examples generated. Further, an L_p norm based distance metric ignores important structure patterns hidden in images that are important to human perception. Consequently, even the minor perturbation introduced in recent works often makes the adversarial examples less natural to humans. More importantly, they often do not transfer well and are therefore less effective when attacking black-box models especially for those protected by a defense mechanism. In this paper, we propose a structure-preserving transformation (SPT) for generating natural and diverse adversarial examples with extremely high transferability. The key idea of our approach is to allow perceptible deviation in adversarial examples while keeping structure patterns that are central to a human classifier. Empirical results on the MNIST and the fashion-MNIST datasets show that adversarial examples generated by our approach can easily bypass strong adversarial training. Further, they transfer well to other target models with no loss or little loss of successful attack rate.
Multitasking Capacity: Hardness Results and Improved Constructions
Venue: arXiv cs.DS 2018
Year: 2018

We consider the problem of determining the maximal $α\in (0,1]$ such that every matching $M$ of size $k$ (or at most $k$) in a bipartite graph $G$ contains an induced matching of size at least $α|M|$. This measure was recently introduced in Alon et al. (NIPS 2018) and is motivated by connectionist models of cognition as well as modeling interference in wireless and communication networks. We prove various hardness results for computing $α$ either exactly or approximately. En route to our results, we also consider the maximum connected matching problem: determining the largest matching $N$ in a graph $G$ such that every two edges in $N$ are connected by an edge. We prove a nearly optimal $n^{1-ε}$ hardness of approximation result (under randomized reductions) for connected matching in bipartite graphs (with both sides of cardinality $n$). Towards this end we define bipartite half-covers: A new combinatorial object that may be of independent interest. To the best of our knowledge, the best previous hardness result for the connected matching problem was some constant $β>1$. Finally, we demonstrate the existence of bipartite graphs with $n$ vertices on each side of average degree $d$, that achieve $α=1/2-ε$ for matchings of size sufficiently smaller than $n/poly(d)$. This nearly matches the trivial upper bound of $1/2$ on $α$ which holds for any graph containing a path of length 3.
Non-Parametric Variational Inference with Graph Convolutional Networks for Gaussian Processes
Venue: arXiv cs.LG 2018
Year: 2018

Inference for GP models with non-Gaussian noises is computationally expensive when dealing with large datasets. Many recent inference methods approximate the posterior distribution with a simpler distribution defined on a small number of inducing points. The inference is accurate only when data points have strong correlation with these inducing points. In this paper, we consider the inference problem in a different direction: GP function values in the posterior are mostly correlated in short distance. We construct a variational distribution such that the inference for a data point considers only its neighborhood. With this construction, the variational lower bound is highly decomposible, hence we can run stochastic optimization with very small batches. We then train Graph Convolutional Networks as a reusable model to identify variational parameters for each data point. Model reuse greatly reduces the number of parameters and the number of iterations needed in optimization. The proposed method significantly speeds up the inference and often gets more accurate results than previous methods.
Online Mutual Foreground Segmentation for Multispectral Stereo Videos
Venue: arXiv cs.CV 2018
Year: 2018

The segmentation of video sequences into foreground and background regions is a low-level process commonly used in video content analysis and smart surveillance applications. Using a multispectral camera setup can improve this process by providing more diverse data to help identify objects despite adverse imaging conditions. The registration of several data sources is however not trivial if the appearance of objects produced by each sensor differs substantially. This problem is further complicated when parallax effects cannot be ignored when using close-range stereo pairs. In this work, we present a new method to simultaneously tackle multispectral segmentation and stereo registration. Using an iterative procedure, we estimate the labeling result for one problem using the provisional result of the other. Our approach is based on the alternating minimization of two energy functions that are linked through the use of dynamic priors. We rely on the integration of shape and appearance cues to find proper multispectral correspondences, and to properly segment objects in low contrast regions. We also formulate our model as a frame processing pipeline using higher order terms to improve the temporal coherence of our results. Our method is evaluated under different configurations on multiple multispectral datasets, and our implementation is available online.
A Review on Cooperative Adaptive Cruise Control (CACC) Systems: Architectures, Controls, and Applications
Venue: arXiv cs.SY 2018
Year: 2018

Connected and automated vehicles (CAVs) have the potential to address the safety, mobility and sustainability issues of our current transportation systems. Cooperative adaptive cruise control (CACC), for example, is one promising technology to allow CAVs to be driven in a cooperative manner and introduces system-wide benefits. In this paper, we review the progress achieved by researchers worldwide regarding different aspects of CACC systems. Literature of CACC system architectures are reviewed, which explain how this system works from a higher level. Different control methodologies and their related issues are reviewed to introduce CACC systems from a lower level. Applications of CACC technology are demonstrated with detailed literature, which draw an overall landscape of CACC, point out current opportunities and challenges, and anticipate its development in the near future.
Cost-Sensitive Active Learning for Intracranial Hemorrhage Detection
Venue: arXiv cs.CV 2018
Year: 2018

Deep learning for clinical applications is subject to stringent performance requirements, which raises a need for large labeled datasets. However, the enormous cost of labeling medical data makes this challenging. In this paper, we build a cost-sensitive active learning system for the problem of intracranial hemorrhage detection and segmentation on head computed tomography (CT). We show that our ensemble method compares favorably with the state-of-the-art, while running faster and using less memory. Moreover, our experiments are done using a substantially larger dataset than earlier papers on this topic. Since the labeling time could vary tremendously across examples, we model the labeling time and optimize the return on investment. We validate this idea by core-set selection on our large labeled dataset and by growing it with data from the wild.
Accelerating Viterbi Algorithm using Custom Instruction Approach
Venue: arXiv cs.AR 2018
Year: 2018

In recent years, the decoding algorithms in communication networks are becoming increasingly complex aiming to achieve high reliability in correctly decoding received messages. These decoding algorithms involve computationally complex operations requiring high performance computing hardware, which are generally expensive. A cost-effective solution is to enhance the Instruction Set Architecture (ISA) of the processors by creating new custom instructions for the computational parts of the decoding algorithms. In this paper, we propose to utilize the custom instruction approach to efficiently implement the widely used Viterbi decoding algorithm by adding the assembly language instructions to the ISA of DLX, PicoJava II and NIOS II processors, which represent RISC, stack and FPGA-based soft-core processor architectures, respectively. By using the custom instruction approach, the execution time of the Viterbi algorithm is significantly improved by approximately 3 times for DLX and PicoJava II, and by 2 times for NIOS II.
CrowdExpress: A Probabilistic Framework for On-Time Crowdsourced Package Deliveries
Venue: arXiv cs.OH 2018
Year: 2018

Speed and cost of logistics are two major concerns to on-line shoppers, but they generally conflict with each other in nature. To alleviate the contradiction, we propose to exploit existing taxis that are transporting passengers on the street to relay packages collaboratively, which can simultaneously lower the cost and accelerate the speed. Specifically, we propose a probabilistic framework containing two phases called CrowdExpress for the on-time package express deliveries. In the first phase, we mine the historical taxi GPS trajectory data offline to build the package transport network. In the second phase, we develop an online adaptive taxi scheduling algorithm to find the path with the maximum arriving-on-time probability "on-the-fly" upon real- time requests, and direct the package routing accordingly. Finally, we evaluate the system using the real-world taxi data generated by over 19,000 taxis in a month in the city of New York, US. Results show that around 9,500 packages can be delivered successfully on time per day with the success rate over 94%, moreover, the average computation time is within 25 milliseconds.
Elliptical Distributions-Based Weights-Determining Method for OWA Operators
Venue: arXiv cs.AI 2018
Year: 2018

The ordered weighted averaging (OWA) operators play a crucial role in aggregating multiple criteria evaluations into an overall assessment supporting the decision makers' choice. One key point steps is to determine the associated weights. In this paper, we first briefly review some main methods for determining the weights by using distribution functions. Then we propose a new approach for determining OWA weights by using the RIM quantifier. Motivated by the idea of normal distribution-based method to determine the OWA weights, we develop a method based on elliptical distributions for determining the OWA weights, and some of its desirable properties have been investigated.
Time-universal data compression and prediction
Venue: arXiv cs.IT 2018
Year: 2018

Suppose there is a large file which should be transmitted (or stored) and there are several (say, m) admissible data-compressors. It seems natural to try all the compressors and then choose the best, i.e. the one that gives the shortest compressed file. Then transfer (or store) the index number of the best compressor (it requires log m bits) and the compressed file.The only problem is the time, which essentially increases due to the need to compress the file m times (in order to find the best compressor). We propose a method that encodes the file with the optimal compressor, but uses a relatively small additional time: the ratio of this extra time and the total time of calculation can be limited by an arbitrary positive constant. Generally speaking, in many situations it may be necessary find the best data compressor out of a given set, which is often done by comparing them empirically. One of the goals of this work is to turn such a selection process into a part of the data compression method, automating and optimizing it.
On Solving Linear Systems in Sublinear Time
Venue: arXiv cs.DS 2018
Year: 2018

We study \emph{sublinear} algorithms that solve linear systems locally. In the classical version of this problem the input is a matrix $S\in \mathbb{R}^{n\times n}$ and a vector $b\in\mathbb{R}^n$ in the range of $S$, and the goal is to output $x\in \mathbb{R}^n$ satisfying $Sx=b$. For the case when the matrix $S$ is symmetric diagonally dominant (SDD), the breakthrough algorithm of Spielman and Teng [STOC 2004] approximately solves this problem in near-linear time (in the input size which is the number of non-zeros in $S$), and subsequent papers have further simplified, improved, and generalized the algorithms for this setting. Here we focus on computing one (or a few) coordinates of $x$, which potentially allows for sublinear algorithms. Formally, given an index $u\in [n]$ together with $S$ and $b$ as above, the goal is to output an approximation $\hat{x}_u$ for $x^*_u$, where $x^*$ is a fixed solution to $Sx=b$. Our results show that there is a qualitative gap between SDD matrices and the more general class of positive semidefinite (PSD) matrices. For SDD matrices, we develop an algorithm that approximates a single coordinate $x_{u}$ in time that is polylogarithmic in $n$, provided that $S$ is sparse and has a small condition number (e.g., Laplacian of an expander graph). The approximation guarantee is additive $| \hat{x}_u-x^*_u | \le ε\| x^* \|_\infty$ for accuracy parameter $ε>0$. We further prove that the condition-number assumption is necessary and tight. In contrast to the SDD matrices, we prove that for certain PSD matrices $S$, the running time must be at least polynomial in $n$. This holds even when one wants to obtain the same additive approximation, and $S$ has bounded sparsity and condition number.
Can Neural Generators for Dialogue Learn Sentence Planning and Discourse Structuring?
Venue: arXiv cs.CL 2018
Year: 2018

Responses in task-oriented dialogue systems often realize multiple propositions whose ultimate form depends on the use of sentence planning and discourse structuring operations. For example a recommendation may consist of an explicitly evaluative utterance e.g. Chanpen Thai is the best option, along with content related by the justification discourse relation, e.g. It has great food and service, that combines multiple propositions into a single phrase. While neural generation methods integrate sentence planning and surface realization in one end-to-end learning framework, previous work has not shown that neural generators can: (1) perform common sentence planning and discourse structuring operations; (2) make decisions as to whether to realize content in a single sentence or over multiple sentences; (3) generalize sentence planning and discourse relation operations beyond what was seen in training. We systematically create large training corpora that exhibit particular sentence planning operations and then test neural models to see what they learn. We compare models without explicit latent variables for sentence planning with ones that provide explicit supervision during training. We show that only the models with additional supervision can reproduce sentence planing and discourse operations and generalize to situations unseen in training.
How clever is the FiLM model, and how clever can it be?
Venue: arXiv cs.CL 2018
Year: 2018

The FiLM model achieves close-to-perfect performance on the diagnostic CLEVR dataset and is distinguished from other such models by having a comparatively simple and easily transferable architecture. In this paper, we investigate in more detail the ability of FiLM to learn various linguistic constructions. Our main results show that (a) FiLM is not able to learn relational statements straight away except for very simple instances, (b) training on a broader set of instances as well as pretraining on simpler instance types can help alleviate these learning difficulties, (c) mixing is less robust than pretraining and very sensitive to the compositional structure of the dataset. Overall, our results suggest that the approach of big all-encompassing datasets and the paradigm of "the effectiveness of data" may have fundamental limitations.
Tester versus Bug: A Generic Framework for Model-Based Testing via Games
Venue: arXiv cs.GT 2018
Year: 2018

We propose a generic game-based approach for test case generation. We set up a game between the tester and the System Under Test, in such a way that test cases correspond to game strategies, and the conformance relation ioco corresponds to alternating refinement. We show that different test assumptions from the literature can be easily incorporated, by slightly varying the moves in the games and their outcomes. In this way, our framework allows a wide plethora of game-theoretic techniques to be deployed for model based testing.
Parameterized Verification of Coverability in Well-Structured Broadcast Networks
Venue: arXiv cs.LO 2018
Year: 2018

Parameterized verification of coverability in broadcast networks with finite state processes has been studied for different types of models and topologies. In this paper, we attempt to develop a theory of broadcast networks in which the processes can be well-structured transition systems. The resulting formalism is called well-structured broadcast networks. We give an algorithm to decide coverability of well-structured broadcast networks when reconfiguration of links between nodes is allowed. Further, for various types of communication topologies, we also prove the decidability of coverability in the static case as well. We do this by showing that for these types of static communication topologies, the broadcast network itself is a well-structured transition system, hence proving the decidability of coverability in the broadcast network.
Memristive LSTM network hardware architecture for time-series predictive modeling problem
Venue: arXiv cs.ET 2018
Year: 2018

Analysis of time-series data allows to identify long-term trends and make predictions that can help to improve our lives. With the rapid development of artificial neural networks, long short-term memory (LSTM) recurrent neural network (RNN) configuration is found to be capable in dealing with time-series forecasting problems where data points are time-dependent and possess seasonality trends. Gated structure of LSTM cell and flexibility in network topology (one-to-many, many-to-one, etc.) allows to model systems with multiple input variables and control several parameters such as the size of the look-back window to make a prediction and number of time steps to be predicted. These make LSTM attractive tool over conventional methods such as autoregression models, the simple average, moving average, naive approach, ARIMA, Holt's linear trend method, Holt's Winter seasonal method, and others. In this paper, we propose a hardware implementation of LSTM network architecture for time-series forecasting problem. All simulations were performed using TSMC 0.18um CMOS technology and HP memristor model.
A Multi-Agent Reinforcement Learning Method for Impression Allocation in Online Display Advertising
Venue: arXiv cs.AI 2018
Year: 2018

In online display advertising, guaranteed contracts and real-time bidding (RTB) are two major ways to sell impressions for a publisher. Despite the increasing popularity of RTB, there is still half of online display advertising revenue generated from guaranteed contracts. Therefore, simultaneously selling impressions through both guaranteed contracts and RTB is a straightforward choice for a publisher to maximize its yield. However, deriving the optimal strategy to allocate impressions is not a trivial task, especially when the environment is unstable in real-world applications. In this paper, we formulate the impression allocation problem as an auction problem where each contract can submit virtual bids for individual impressions. With this formulation, we derive the optimal impression allocation strategy by solving the optimal bidding functions for contracts. Since the bids from contracts are decided by the publisher, we propose a multi-agent reinforcement learning (MARL) approach to derive cooperative policies for the publisher to maximize its yield in an unstable environment. The proposed approach also resolves the common challenges in MARL such as input dimension explosion, reward credit assignment, and non-stationary environment. Experimental evaluations on large-scale real datasets demonstrate the effectiveness of our approach.
Learning Time Dependent Choice
Venue: arXiv cs.GT 2018
Year: 2018

We explore questions dealing with the learnability of models of choice over time. We present a large class of preference models defined by a structural criterion for which we are able to obtain an exponential improvement over previously known learning bounds for more general preference models. This in particular implies that the three most important discounted utility models of intertemporal choice -- exponential, hyperbolic, and quasi-hyperbolic discounting -- are learnable in the PAC setting with VC dimension that grows logarithmically in the number of time periods. We also examine these models in the framework of active learning. We find that the commonly studied stream-based setting is in general difficult to analyze for preference models, but we provide a redeeming situation in which the learner can indeed improve upon the guarantees provided by PAC learning. In contrast to the stream-based setting, we show that if the learner is given full power over the data he learns from -- in the form of learning via membership queries -- even very naive algorithms significantly outperform the guarantees provided by higher level active learning algorithms.