OpenRaiser/Intern-Atlas huggingface dataset:
Barrier-Certified Adaptive Reinforcement Learning with Applications to Brushbot Navigation
Venue: arXiv cs.LG 2019
Year: 2019

This paper presents a safe learning framework that employs an adaptive model learning algorithm together with barrier certificates for systems with possibly nonstationary agent dynamics. To extract the dynamic structure of the model, we use a sparse optimization technique. We use the learned model in combination with control barrier certificates which constrain policies (feedback controllers) in order to maintain safety, which refers to avoiding particular undesirable regions of the state space. Under certain conditions, recovery of safety in the sense of Lyapunov stability after violations of safety due to the nonstationarity is guaranteed. In addition, we reformulate an action-value function approximation to make any kernel-based nonlinear function estimation method applicable to our adaptive learning framework. Lastly, solutions to the barrier-certified policy optimization are guaranteed to be globally optimal, ensuring the greedy policy improvement under mild conditions. The resulting framework is validated via simulations of a quadrotor, which has previously been used under stationarity assumptions in the safe learnings literature, and is then tested on a real robot, the brushbot, whose dynamics is unknown, highly complex and nonstationary.
Crowd Behavior Simulation with Emotional Contagion in Unexpected Multi-hazard Situations
Venue: arXiv cs.MA 2019
Year: 2019

In this paper we present a novel crowd simulation method by modeling the generation and contagion of panic emotion under multi-hazard circumstances. Specifically, we first classify hazards into different types (transient and persistent, concurrent and non-concurrent, static and dynamic ) based on their inherent characteristics. Then, we introduce the concept of perilous field for each hazard and further transform the critical level of the field to its invoked-panic emotion. After that, we propose an emotional contagion model to simulate the evolving process of panic emotion caused by multiple hazards in these situations. Finally, we introduce an Emotional Reciprocal Velocity Obstacles (ERVO) model to simulate the crowd behaviors by augmenting the traditional RVO model with emotional contagion, which combines the emotional impact and local avoidance together for the first time. Our experimental results show that this method can soundly generate realistic group behaviors as well as panic emotion dynamics in a crowd in multi-hazard environments.
Bootstrapping and Multiple Imputation Ensemble Approaches for Missing Data
Venue: arXiv cs.LG 2019
Year: 2019

Presence of missing values in a dataset can adversely affect the performance of a classifier. Single and Multiple Imputation are normally performed to fill in the missing values. In this paper, we present several variants of combining single and multiple imputation with bootstrapping to create ensembles that can model uncertainty and diversity in the data, and that are robust to high missingness in the data. We present three ensemble strategies: bootstrapping on incomplete data followed by (i) single imputation and (ii) multiple imputation, and (iii) multiple imputation ensemble without bootstrapping. We perform an extensive evaluation of the performance of the these ensemble strategies on 8 datasets by varying the missingness ratio. Our results show that bootstrapping followed by multiple imputation using expectation maximization is the most robust method even at high missingness ratio (up to 30%). For small missingness ratio (up to 10%) most of the ensemble methods perform quivalently but better than single imputation. Kappa-error plots suggest that accurate classifiers with reasonable diversity is the reason for this behaviour. A consistent observation in all the datasets suggests that for small missingness (up to 10%), bootstrapping on incomplete data without any imputation produces equivalent results to other ensemble methods.
Evolutionary model discovery of causal factors behind the socio-agricultural behavior of the ancestral Pueblo
Venue: arXiv cs.MA 2019
Year: 2019

Agent-based modeling of artificial societies offers a platform to test human-interpretable, causal explanations of human behavior that generate society-scale phenomena. However, parameter calibration is insufficient to conduct an adequate data-driven exploration of the importance of causal factors that constitute agent rules, resulting in models with limited causal accuracy and robustness. We introduce evolutionary model discovery, a framework that combines genetic programming and random forest regression to evaluate the importance of a set of causal factors hypothesized to affect the individual's decision-making process. We investigated the farm plot seeking behavior of the ancestral Pueblo of the Long House Valley simulated in the Artificial Anasazi model our proposed framework. We evaluated the importance of causal factors not considered in the original model that we hypothesized to have affected the decision-making process. Contrary to the original model, where closeness was the sole factor driving farm plot selection, selection of higher quality land and desire for social presence are shown to be more important. In fact, model performance is improved when agents select farm plots further away from their failed farm plot. Farm selection strategies designed using these insights into the socio-agricultural behavior of the ancestral Pueblo significantly improved the model's accuracy and robustness.
Secure Detection of Image Manipulation by means of Random Feature Selection
Venue: arXiv cs.CR 2019
Year: 2019

We address the problem of data-driven image manipulation detection in the presence of an attacker with limited knowledge about the detector. Specifically, we assume that the attacker knows the architecture of the detector, the training data and the class of features V the detector can rely on. In order to get an advantage in his race of arms with the attacker, the analyst designs the detector by relying on a subset of features chosen at random in V. Given its ignorance about the exact feature set, the adversary attacks a version of the detector based on the entire feature set. In this way, the effectiveness of the attack diminishes since there is no guarantee that attacking a detector working in the full feature space will result in a successful attack against the reduced-feature detector. We theoretically prove that, thanks to random feature selection, the security of the detector increases significantly at the expense of a negligible loss of performance in the absence of attacks. We also provide an experimental validation of the proposed procedure by focusing on the detection of two specific kinds of image manipulations, namely adaptive histogram equalization and median filtering. The experiments confirm the gain in security at the expense of a negligible loss of performance in the absence of attacks.
Explaining First Impressions: Modeling, Recognizing, and Explaining Apparent Personality from Videos
Venue: arXiv cs.CV 2019
Year: 2019

Explainability and interpretability are two critical aspects of decision support systems. Within computer vision, they are critical in certain tasks related to human behavior analysis such as in health care applications. Despite their importance, it is only recently that researchers are starting to explore these aspects. This paper provides an introduction to explainability and interpretability in the context of computer vision with an emphasis on looking at people tasks. Specifically, we review and study those mechanisms in the context of first impressions analysis. To the best of our knowledge, this is the first effort in this direction. Additionally, we describe a challenge we organized on explainability in first impressions analysis from video. We analyze in detail the newly introduced data set, the evaluation protocol, and summarize the results of the challenge. Finally, derived from our study, we outline research opportunities that we foresee will be decisive in the near future for the development of the explainable computer vision field.
Randomized Transmission Protocols for Protection against Jamming Attacks in Multi-Agent Consensus
Venue: arXiv cs.SY 2019
Year: 2019

Multi-agent consensus under jamming attacks is investigated. Specifically, inter-agent communications over a network are assumed to fail at certain times due to jamming of transmissions by a malicious attacker. A new stochastic communication protocol is proposed to achieve finite-time practical consensus between agents. In this protocol, communication attempt times of agents are randomized and unknown by the attacker until after the agents make their communication attempts. Through a probabilistic analysis, we show that the proposed communication protocol, when combined with a stochastic ternary control law, allows agents to achieve consensus regardless of the frequency of attacks. We demonstrate the efficacy of our results by considering two different strategies of the jamming attacker: a deterministic attack strategy and a more malicious communication-aware attack strategy.
Exploring Spatial Context for 3D Semantic Segmentation of Point Clouds
Venue: arXiv cs.CV 2019
Year: 2019

Deep learning approaches have made tremendous progress in the field of semantic segmentation over the past few years. However, most current approaches operate in the 2D image space. Direct semantic segmentation of unstructured 3D point clouds is still an open research problem. The recently proposed PointNet architecture presents an interesting step ahead in that it can operate on unstructured point clouds, achieving encouraging segmentation results. However, it subdivides the input points into a grid of blocks and processes each such block individually. In this paper, we investigate the question how such an architecture can be extended to incorporate larger-scale spatial context. We build upon PointNet and propose two extensions that enlarge the receptive field over the 3D scene. We evaluate the proposed strategies on challenging indoor and outdoor datasets and show improved results in both scenarios.
Universal Deep Neural Network Compression
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we investigate lossy compression of deep neural networks (DNNs) by weight quantization and lossless source coding for memory-efficient deployment. Whereas the previous work addressed non-universal scalar quantization and entropy coding of DNN weights, we for the first time introduce universal DNN compression by universal vector quantization and universal source coding. In particular, we examine universal randomized lattice quantization of DNNs, which randomizes DNN weights by uniform random dithering before lattice quantization and can perform near-optimally on any source without relying on knowledge of its probability distribution. Moreover, we present a method of fine-tuning vector quantized DNNs to recover the performance loss after quantization. Our experimental results show that the proposed universal DNN compression scheme compresses the 32-layer ResNet (trained on CIFAR-10) and the AlexNet (trained on ImageNet) with compression ratios of $47.1$ and $42.5$, respectively.
PoTrojan: powerful neural-level trojan designs in deep learning models
Venue: arXiv cs.CR 2019
Year: 2019

With the popularity of deep learning (DL), artificial intelligence (AI) has been applied in many areas of human life. Neural network or artificial neural network (NN), the main technique behind DL, has been extensively studied to facilitate computer vision and natural language recognition. However, the more we rely on information technology, the more vulnerable we are. That is, malicious NNs could bring huge threat in the so-called coming AI era. In this paper, for the first time in the literature, we propose a novel approach to design and insert powerful neural-level trojans or PoTrojan in pre-trained NN models. Most of the time, PoTrojans remain inactive, not affecting the normal functions of their host NN models. PoTrojans could only be triggered in very rare conditions. Once activated, however, the PoTrojans could cause the host NN models to malfunction, either falsely predicting or classifying, which is a significant threat to human society of the AI era. We would explain the principles of PoTrojans and the easiness of designing and inserting them in pre-trained deep learning models. PoTrojans doesn't modify the existing architecture or parameters of the pre-trained models, without re-training. Hence, the proposed method is very efficient.
Ultra-Reliable Communication in 5G mmWave Networks: A Risk-Sensitive Approach
Venue: arXiv cs.NI 2019
Year: 2019

This letter investigates the problem of providing gigabit wireless access with reliable communication in 5G millimeter-Wave (mmWave) massive multiple-input multiple-output (MIMO) networks. In contrast to the classical network design based on average metrics, a distributed risk-sensitive reinforcement learning-based framework is proposed to jointly optimize the beamwidth and transmit power, while taking into account the sensitivity of mmWave links due to blockage. Numerical results show that our proposed algorithm achieves more than 9 Gbps of user throughput with a guaranteed probability of 90%, whereas the baselines guarantee less than 7.5 Gbps. More importantly, there exists a rate-reliability-network density tradeoff, in which as the user density increases from 16 to 96 per km2, the fraction of users that achieve 4 Gbps are reduced by 11.61% and 39.11% in the proposed and the baseline models, respectively.
Temporal and volumetric denoising via quantile sparse image prior
Venue: arXiv cs.CV 2019
Year: 2019

This paper introduces an universal and structure-preserving regularization term, called quantile sparse image (QuaSI) prior. The prior is suitable for denoising images from various medical imaging modalities. We demonstrate its effectiveness on volumetric optical coherence tomography (OCT) and computed tomography (CT) data, which show different noise and image characteristics. OCT offers high-resolution scans of the human retina but is inherently impaired by speckle noise. CT on the other hand has a lower resolution and shows high-frequency noise. For the purpose of denoising, we propose a variational framework based on the QuaSI prior and a Huber data fidelity model that can handle 3-D and 3-D+t data. Efficient optimization is facilitated through the use of an alternating direction method of multipliers (ADMM) scheme and the linearization of the quantile filter. Experiments on multiple datasets emphasize the excellent performance of the proposed method.
Image Retargetability
Venue: arXiv cs.CV 2019
Year: 2019

Real-world applications could benefit from the ability to automatically retarget an image to different aspect ratios and resolutions, while preserving its visually and semantically important content. However, not all images can be equally well processed that way. In this work, we introduce the notion of image retargetability to describe how well a particular image can be handled by content-aware image retargeting. We propose to learn a deep convolutional neural network to rank photo retargetability in which the relative ranking of photo retargetability is directly modeled in the loss function. Our model incorporates joint learning of meaningful photographic attributes and image content information which can help regularize the complicated retargetability rating problem. To train and analyze this model, we have collected a database which contains retargetability scores and meaningful image attributes assigned by six expert raters. Experiments demonstrate that our unified model can generate retargetability rankings that are highly consistent with human labels. To further validate our model, we show applications of image retargetability in retargeting method selection, retargeting method assessment and photo collage generation.
Efficient Exploration through Bayesian Deep Q-Networks
Venue: arXiv cs.AI 2019
Year: 2019

We study reinforcement learning (RL) in high dimensional episodic Markov decision processes (MDP). We consider value-based RL when the optimal Q-value is a linear function of d-dimensional state-action feature representation. For instance, in deep-Q networks (DQN), the Q-value is a linear function of the feature representation layer (output layer). We propose two algorithms, one based on optimism, LINUCB, and another based on posterior sampling, LINPSRL. We guarantee frequentist and Bayesian regret upper bounds of O(d sqrt{T}) for these two algorithms, where T is the number of episodes. We extend these methods to deep RL and propose Bayesian deep Q-networks (BDQN), which uses an efficient Thompson sampling algorithm for high dimensional RL. We deploy the double DQN (DDQN) approach, and instead of learning the last layer of Q-network using linear regression, we use Bayesian linear regression, resulting in an approximated posterior over Q-function. This allows us to directly incorporate the uncertainty over the Q-function and deploy Thompson sampling on the learned posterior distribution resulting in efficient exploration/exploitation trade-off. We empirically study the behavior of BDQN on a wide range of Atari games. Since BDQN carries out more efficient exploration and exploitation, it is able to reach higher return substantially faster compared to DDQN.
Graph Coarsening with Preserved Spectral Properties
Venue: arXiv cs.SI 2019
Year: 2019

Large-scale graphs are widely used to represent object relationships in many real world applications. The occurrence of large-scale graphs presents significant computational challenges to process, analyze, and extract information. Graph coarsening techniques are commonly used to reduce the computational load while attempting to maintain the basic structural properties of the original graph. As there is no consensus on the specific graph properties preserved by coarse graphs, how to measure the differences between original and coarse graphs remains a key challenge. In this work, we introduce a new perspective regarding the graph coarsening based on concepts from spectral graph theory. We propose and justify new distance functions that characterize the differences between original and coarse graphs. We show that the proposed spectral distance naturally captures the structural differences in the graph coarsening process. In addition, we provide efficient graph coarsening algorithms to generate graphs which provably preserve the spectral properties from original graphs. Experiments show that our proposed algorithms consistently achieve better results compared to previous graph coarsening methods on graph classification and block recovery tasks.
Query learning of derived $ω$-tree languages in polynomial time
Venue: arXiv cs.LO 2019
Year: 2019

We present the first polynomial time algorithm to learn nontrivial classes of languages of infinite trees. Specifically, our algorithm uses membership and equivalence queries to learn classes of $ω$-tree languages derived from weak regular $ω$-word languages in polynomial time. The method is a general polynomial time reduction of learning a class of derived $ω$-tree languages to learning the underlying class of $ω$-word languages, for any class of $ω$-word languages recognized by a deterministic Büchi acceptor. Our reduction, combined with the polynomial time learning algorithm of Maler and Pnueli [1995] for the class of weak regular $ω$-word languages yields the main result. We also show that subset queries that return counterexamples can be implemented in polynomial time using subset queries that return no counterexamples for deterministic or non-deterministic finite word acceptors, and deterministic or non-deterministic Büchi $ω$-word acceptors. A previous claim of an algorithm to learn regular $ω$-trees due to Jayasrirani, Begam and Thomas [2008] is unfortunately incorrect, as shown in Angluin [2016].
Using Trusted Data to Train Deep Networks on Labels Corrupted by Severe Noise
Venue: arXiv cs.LG 2019
Year: 2019

The growing importance of massive datasets used for deep learning makes robustness to label noise a critical property for classifiers to have. Sources of label noise include automatic labeling, non-expert labeling, and label corruption by data poisoning adversaries. Numerous previous works assume that no source of labels can be trusted. We relax this assumption and assume that a small subset of the training data is trusted. This enables substantial label corruption robustness performance gains. In addition, particularly severe label noise can be combated by using a set of trusted data with clean labels. We utilize trusted data by proposing a loss correction technique that utilizes trusted examples in a data-efficient manner to mitigate the effects of label noise on deep neural network classifiers. Across vision and natural language processing tasks, we experiment with various label noises at several strengths, and show that our method significantly outperforms existing methods.
Learning Determinantal Point Processes by Corrective Negative Sampling
Venue: arXiv cs.LG 2019
Year: 2019

Determinantal Point Processes (DPPs) have attracted significant interest from the machine-learning community due to their ability to elegantly and tractably model the delicate balance between quality and diversity of sets. DPPs are commonly learned from data using maximum likelihood estimation (MLE). While fitting observed sets well, MLE for DPPs may also assign high likelihoods to unobserved sets that are far from the true generative distribution of the data. To address this issue, which reduces the quality of the learned model, we introduce a novel optimization problem, Contrastive Estimation (CE), which encodes information about "negative" samples into the basic learning model. CE is grounded in the successful use of negative information in machine-vision and language modeling. Depending on the chosen negative distribution (which may be static or evolve during optimization), CE assumes two different forms, which we analyze theoretically and experimentally. We evaluate our new model on real-world datasets; on a challenging dataset, CE learning delivers a considerable improvement in predictive performance over a DPP learned without using contrastive information.
Refining the $r$-index
Venue: arXiv cs.DS 2019
Year: 2019

Gagie, Navarro and Prezza's $r$-index (SODA, 2018) promises to speed up DNA alignment and variation calling by allowing us to index entire genomic databases, provided certain obstacles can be overcome. In this paper we first strengthen and simplify Policriti and Prezza's Toehold Lemma (DCC '16; Algorithmica, 2017), which inspired the $r$-index and plays an important role in its implementation. We then show how to update the $r$-index efficiently after adding a new genome to the database, which is likely to be vital in practice. As a by-product of this result, we obtain an online version of Policriti and Prezza's algorithm for constructing the LZ77 parse from a run-length compressed Burrows-Wheeler Transform. Our experiments demonstrate the practicality of all three of these results. Finally, we show how to augment the $r$-index such that, given a new genome and fast random access to the database, we can quickly compute the matching statistics and maximal exact matches of the new genome with respect to the database.