OpenRaiser/Intern-Atlas huggingface dataset:
Kolmogorov complexity in the USSR (1975--1982): isolation and its end
Venue: arXiv cs.GL 2019
Year: 2019

These reminiscences are about the "dark ages" of algorithmic information theory in the USSR. After a great interest in this topic in 1960s and the beginning of 1970s the number of people working in this area in the USSR decreased significantly. At that time L.A. Levin published a bunch of papers that were seminal for the modern algorithmic information theory. Then he left the USSR, and the new wave of interest was triggered by the talk of A.N. Kolmogorov at a Moscow State (Lomonosov) University Mathematical Department (Logic and Algorithms Division) seminar organized by him; several younger researchers obtained some new results in algorithmic information theory.
FIRE: Unsupervised bi-directional inter-modality registration using deep networks
Venue: arXiv cs.CV 2019
Year: 2019

Inter-modality image registration is an critical preprocessing step for many applications within the routine clinical pathway. This paper presents an unsupervised deep inter-modality registration network that can learn the optimal affine and non-rigid transformations simultaneously. Inverse-consistency is an important property commonly ignored in recent deep learning based inter-modality registration algorithms. We address this issue through the proposed multi-task architecture and the new comprehensive transformation network. Specifically, the proposed model learns a modality-independent latent representation to perform cycle-consistent cross-modality synthesis, and use an inverse-consistent loss to learn a pair of transformations to align the synthesized image with the target. We name this proposed framework as FIRE due to the shape of its structure. Our method shows comparable and better performances with the popular baseline method in experiments on multi-sequence brain MR data and intra-modality 4D cardiac Cine-MR data.
Void-and-Cluster Sampling of Large Scattered Data and Trajectories
Venue: arXiv cs.GR 2019
Year: 2019

We propose a data reduction technique for scattered data based on statistical sampling. Our void-and-cluster sampling technique finds a representative subset that is optimally distributed in the spatial domain with respect to the blue noise property. In addition, it can adapt to a given density function, which we use to sample regions of high complexity in the multivariate value domain more densely. Moreover, our sampling technique implicitly defines an ordering on the samples that enables progressive data loading and a continuous level-of-detail representation. We extend our technique to sample time-dependent trajectories, for example pathlines in a time interval, using an efficient and iterative approach. Furthermore, we introduce a local and continuous error measure to quantify how well a set of samples represents the original dataset. We apply this error measure during sampling to guide the number of samples that are taken. Finally, we use this error measure and other quantities to evaluate the quality, performance, and scalability of our algorithm.
Activitynet 2019 Task 3: Exploring Contexts for Dense Captioning Events in Videos
Venue: arXiv cs.CV 2019
Year: 2019

Contextual reasoning is essential to understand events in long untrimmed videos. In this work, we systematically explore different captioning models with various contexts for the dense-captioning events in video task, which aims to generate captions for different events in the untrimmed video. We propose five types of contexts as well as two categories of event captioning models, and evaluate their contributions for event captioning from both accuracy and diversity aspects. The proposed captioning models are plugged into our pipeline system for the dense video captioning challenge. The overall system achieves the state-of-the-art performance on the dense-captioning events in video task with 9.91 METEOR score on the challenge testing set.
REACT: REActive resilience for critical infrastructures using graph-Coloring Techniques
Venue: arXiv cs.NI 2019
Year: 2019

Nowadays society is more and more dependent on critical infrastructures. Critical network infrastructures (CNI) are communication networks whose disruption can create a severe impact. In this paper we propose REACT, a distributed framework for reactive network resilience, which allows networks to reconfigure themselves in the event of a security incidents so that the risk of further damage is mitigated. Our framework takes advantage of a risk model based on multilayer networks, as well as a graph-coloring problem conversion, to identify new, more resilient configurations for networks in the event of an attack. We propose two different solution approaches, and evaluate them from two different perspectives, with a number of centralized optimization techniques. Experiments show that our approaches outperform the reference approaches in terms of risk mitigation and performance.
R Melts Brains -- An IR for First-Class Environments and Lazy Effectful Arguments
Venue: arXiv cs.PL 2019
Year: 2019

The R programming language combines a number of features considered hard to analyze and implement efficiently: dynamic typing, reflection, lazy evaluation, vectorized primitive types, first-class closures, and extensive use of native code. Additionally, variable scopes are reified at runtime as first-class environments. The combination of these features renders most static program analysis techniques impractical, and thus, compiler optimizations based on them ineffective. We present our work on PIR, an intermediate representation with explicit support for first-class environments and effectful lazy evaluation. We describe two dataflow analyses on PIR: the first enables reasoning about variables and their environments, and the second infers where arguments are evaluated. Leveraging their results, we show how to elide environment creation and inline functions.
Fairness without Regret
Venue: arXiv cs.LG 2019
Year: 2019

A popular approach of achieving fairness in optimization problems is by constraining the solution space to "fair" solutions, which unfortunately typically reduces solution quality. In practice, the ultimate goal is often an aggregate of sub-goals without a unique or best way of combining them or which is otherwise only partially known. I turn this problem into a feature and suggest to use a parametrized objective and vary the parameters within reasonable ranges to get a "set" of optimal solutions, which can then be optimized using secondary criteria such as fairness without compromising the primary objective, i.e. without regret (societal cost).
Challenges and Directions for Authentication in Pervasive Computing
Venue: arXiv cs.CR 2019
Year: 2019

We quickly approach a "pervasive future" where pervasive computing is the norm. In this scenario, humans are surrounded by a multitude of heterogeneous devices that assist them in almost every aspect of their daily routines. The realization of this future demands strong authentication guarantees to ensure that these devices are not abused and that their users are not endangered. However, providing authentication for these systems is a challenging task due to the high heterogeneity of pervasive computing applications. This heterogeneity makes it unfeasible to propose a single authentication solution for all of the pervasive computing applications. In this paper, we review several pervasive application scenarios and promising authentication methods for each. To do this, we first identify the key characteristics of each pervasive application scenario. Then, we review the strengths and weaknesses of prominent authentication methods from the literature. Finally, we identify which authentication methods are well suited for each application scenario based on the identified characteristics. Our goal is to provide promising directions to be explored for authentication in each of these scenarios.
Variance-Based Risk Estimations in Markov Processes via Transformation with State Lumping
Venue: arXiv cs.LG 2019
Year: 2019

Variance plays a crucial role in risk-sensitive reinforcement learning, and most risk measures can be analyzed via variance. In this paper, we consider two law-invariant risks as examples: mean-variance risk and exponential utility risk. With the aid of the state-augmentation transformation (SAT), we show that, the two risks can be estimated in Markov decision processes (MDPs) with a stochastic transition-based reward and a randomized policy. To relieve the enlarged state space, a novel definition of isotopic states is proposed for state lumping, considering the special structure of the transformed transition probability. In the numerical experiment, we illustrate state lumping in the SAT, errors from a naive reward simplification, and the validity of the SAT for the two risk estimations.
Time series cluster kernels to exploit informative missingness and incomplete label information
Venue: arXiv cs.LG 2019
Year: 2019

The time series cluster kernel (TCK) provides a powerful tool for analysing multivariate time series subject to missing data. TCK is designed using an ensemble learning approach in which Bayesian mixture models form the base models. Because of the Bayesian approach, TCK can naturally deal with missing values without resorting to imputation and the ensemble strategy ensures robustness to hyperparameters, making it particularly well suited for unsupervised learning. However, TCK assumes missing at random and that the underlying missingness mechanism is ignorable, i.e. uninformative, an assumption that does not hold in many real-world applications, such as e.g. medicine. To overcome this limitation, we present a kernel capable of exploiting the potentially rich information in the missing values and patterns, as well as the information from the observed data. In our approach, we create a representation of the missing pattern, which is incorporated into mixed mode mixture models in such a way that the information provided by the missing patterns is effectively exploited. Moreover, we also propose a semi-supervised kernel, capable of taking advantage of incomplete label information to learn more accurate similarities. Experiments on benchmark data, as well as a real-world case study of patients described by longitudinal electronic health record data who potentially suffer from hospital-acquired infections, demonstrate the effectiveness of the proposed methods.
A Targeted Acceleration and Compression Framework for Low bit Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

1 bit deep neural networks (DNNs), of which both the activations and weights are binarized , are attracting more and more attention due to their high computational efficiency and low memory requirement . However, the drawback of large accuracy dropping also restrict s its application. In this paper, we propose a novel Targeted Acceleration and Compression (TAC) framework to improve the performance of 1 bit deep neural networks W e consider that the acceleration and compression effects of binarizing fully connected layer s are not sufficient to compensate for the accuracy loss caused by it In the proposed framework, t he convolutional and fully connected layer are separated and optimized i ndividually . F or the convolutional layer s , both the activations and weights are binarized. For the fully connected layer s, the binarization operation is re placed by network pruning and low bit quantization. The proposed framework is implemented on the CIFAR 10, CIFAR 100 and ImageNet ( ILSVRC 12 ) datasets , and experimental results show that the proposed TAC can significantly improve the accuracy of 1 bit deep neural networks and outperforms the state of the art by more than 6 percentage points .
Human detection of machine manipulated media
Venue: arXiv cs.CV 2019
Year: 2019

Recent advances in neural networks for content generation enable artificial intelligence (AI) models to generate high-quality media manipulations. Here we report on a randomized experiment designed to study the effect of exposure to media manipulations on over 15,000 individuals' ability to discern machine-manipulated media. We engineer a neural network to plausibly and automatically remove objects from images, and we deploy this neural network online with a randomized experiment where participants can guess which image out of a pair of images has been manipulated. The system provides participants feedback on the accuracy of each guess. In the experiment, we randomize the order in which images are presented, allowing causal identification of the learning curve surrounding participants' ability to detect fake content. We find sizable and robust evidence that individuals learn to detect fake content through exposure to manipulated media when provided iterative feedback on their detection attempts. Over a succession of only ten images, participants increase their rating accuracy by over ten percentage points. Our study provides initial evidence that human ability to detect fake, machine-generated content may increase alongside the prevalence of such media online.
State-of-The-Art Sparse Direct Solvers
Venue: arXiv cs.DS 2019
Year: 2019

In this chapter we will give an insight into modern sparse elimination methods. These are driven by a preprocessing phase based on combinatorial algorithms which improve diagonal dominance, reduce fill-in, and improve concurrency to allow for parallel treatment. Moreover, these methods detect dense submatrices which can be handled by dense matrix kernels based on multithreaded level-3 BLAS. We will demonstrate for problems arising from circuit simulation, how the improvements in recent years have advanced direct solution methods significantly.
Graph Neural Based End-to-end Data Association Framework for Online Multiple-Object Tracking
Venue: arXiv cs.CV 2019
Year: 2019

In this work, we present an end-to-end framework to settle data association in online Multiple-Object Tracking (MOT). Given detection responses, we formulate the frame-by-frame data association as Maximum Weighted Bipartite Matching problem, whose solution is learned using a neural network. The network incorporates an affinity learning module, wherein both appearance and motion cues are investigated to encode object feature representation and compute pairwise affinities. Employing the computed affinities as edge weights, the following matching problem on a bipartite graph is resolved by the optimization module, which leverages a graph neural network to adapt with the varying cardinalities of the association problem and solve the combinatorial hardness with favorable scalability and compatibility. To facilitate effective training of the proposed tracking network, we design a multi-level matrix loss in conjunction with the assembled supervision methodology. Being trained end-to-end, all modules in the tracker can co-adapt and co-operate collaboratively, resulting in improved model adaptiveness and less parameter-tuning efforts. Experiment results on the MOT benchmarks demonstrate the efficacy of the proposed approach.
Performance Boundary Identification for the Evaluation of Automated Vehicles using Gaussian Process Classification
Venue: arXiv cs.LG 2019
Year: 2019

Safety is an essential aspect in the facilitation of automated vehicle deployment. Current testing practices are not enough, and going beyond them leads to infeasible testing requirements, such as needing to drive billions of kilometres on public roads. Automated vehicles are exposed to an indefinite number of scenarios. Handling of the most challenging scenarios should be tested, which leads to the question of how such corner cases can be determined. We propose an approach to identify the performance boundary, where these corner cases are located, using Gaussian Process Classification. We also demonstrate the classification on an exemplary traffic jam approach scenario, showing that it is feasible and would lead to more efficient testing practices.
Using Chinese Characters To Generate Text-Based Passwords For Information Security
Venue: arXiv cs.IT 2019
Year: 2019

Graphical passwords (GPWs) are in many areas of the current world. Topological graphic passwords (Topsnut-gpws) are a new type of cryptography, and they differ from the existing GPWs. A Topsnut-gpw consists of two parts: one is a topological structure (graph), and one is a set of discrete elements (a graph labelling, or coloring), the topological structure connects these discrete elements together to form an interesting "story". Our idea is to transform Chinese characters into computer and electronic equipments with touch screen by speaking, writing and keyboard for forming Hanzi-graphs and Hanzi-gpws. We will use Hanzigpws to produce text-based passwords (TB-paws). We will introduce flawed graph labellings on disconnected Hanzi-graphs.
Adversarial Objects Against LiDAR-Based Autonomous Driving Systems
Venue: arXiv cs.CR 2019
Year: 2019

Deep neural networks (DNNs) are found to be vulnerable against adversarial examples, which are carefully crafted inputs with a small magnitude of perturbation aiming to induce arbitrarily incorrect predictions. Recent studies show that adversarial examples can pose a threat to real-world security-critical applications: a "physical adversarial Stop Sign" can be synthesized such that the autonomous driving cars will misrecognize it as others (e.g., a speed limit sign). However, these image-space adversarial examples cannot easily alter 3D scans of widely equipped LiDAR or radar on autonomous vehicles. In this paper, we reveal the potential vulnerabilities of LiDAR-based autonomous driving detection systems, by proposing an optimization based approach LiDAR-Adv to generate adversarial objects that can evade the LiDAR-based detection system under various conditions. We first show the vulnerabilities using a blackbox evolution-based algorithm, and then explore how much a strong adversary can do, using our gradient-based approach LiDAR-Adv. We test the generated adversarial objects on the Baidu Apollo autonomous driving platform and show that such physical systems are indeed vulnerable to the proposed attacks. We also 3D-print our adversarial objects and perform physical experiments to illustrate that such vulnerability exists in the real world. Please find more visualizations and results on the anonymous website: https://sites.google.com/view/lidar-adv.
Predicting engagement in online social networks: Challenges and opportunities
Venue: arXiv cs.SI 2019
Year: 2019

Since the introduction of social media, user participation or engagement has received little research attention. In this survey article, we establish the notion of participation in social media and main challenges that researchers may face while exploring this phenomenon. We surveyed a handful of research articles that had been done in this area, and tried to extract, analyze and summarize the techniques performed by the researchers. We classified these works based on our task definitions, and explored the machine learning models that have been used for any kind of participation prediction. We also explored the vast amount of features that have been proven useful, and classified them into categories for better understanding and ease of re-implementation. We have found that the success of a technique mostly depends on the type of the network that has been researched on, and there is no universal machine learning algorithm or feature sets that works reasonably well in all types of social media. There is a lack of attempts in implementing state-of-the-art machine learning techniques like neural networks, and the possibility of transfer learning and domain adaptation has not been explored.
General Evaluation for Instruction Conditioned Navigation using Dynamic Time Warping
Venue: arXiv cs.RO 2019
Year: 2019

In instruction conditioned navigation, agents interpret natural language and their surroundings to navigate through an environment. Datasets for studying this task typically contain pairs of these instructions and reference trajectories. Yet, most evaluation metrics used thus far fail to properly account for the latter, relying instead on insufficient similarity comparisons. We address fundamental flaws in previously used metrics and show how Dynamic Time Warping (DTW), a long known method of measuring similarity between two time series, can be used for evaluation of navigation agents. For such, we define the normalized Dynamic Time Warping (nDTW) metric, that softly penalizes deviations from the reference path, is naturally sensitive to the order of the nodes composing each path, is suited for both continuous and graph-based evaluations, and can be efficiently calculated. Further, we define SDTW, which constrains nDTW to only successful paths. We collect human similarity judgments for simulated paths and find nDTW correlates better with human rankings than all other metrics. We also demonstrate that using nDTW as a reward signal for Reinforcement Learning navigation agents improves their performance on both the Room-to-Room (R2R) and Room-for-Room (R4R) datasets. The R4R results in particular highlight the superiority of SDTW over previous success-constrained metrics.
Coverage Probability Analysis Under Clustered Ambient Backscatter Nodes
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we consider a new large-scale communication scheme where randomly distributed AmBC nodes are involved as secondary users to primary transmitter (PT) and primary receiver (PR) pairs. The secondary communication between a backscatter transmitter (BT) and a backscatter receiver (BR) is conducted by the BT's reflecting its corresponding PT's signal with different antenna impedances, which introduces additional double fading channels and potential inter-symbol-interference to the primary communications. Thus, at a typical PR, the backscatter signals are regarded as either decodable signals or interference. Assuming the locations of PTs form a Poisson point process and the locations of BTs form a Poisson cluster process, we derive the SINR and SIR based coverage probabilities for two network configuration scenarios. Numerical results on the coverage probabilities indicate the possibility to involve a large amount of AmBC nodes in existing wireless networks.
Collaborative Multi-Agent Dialogue Model Training Via Reinforcement Learning
Venue: arXiv cs.HC 2019
Year: 2019

We present the first complete attempt at concurrently training conversational agents that communicate only via self-generated language. Using DSTC2 as seed data, we trained natural language understanding (NLU) and generation (NLG) networks for each agent and let the agents interact online. We model the interaction as a stochastic collaborative game where each agent (player) has a role ("assistant", "tourist", "eater", etc.) and their own objectives, and can only interact via natural language they generate. Each agent, therefore, needs to learn to operate optimally in an environment with multiple sources of uncertainty (its own NLU and NLG, the other agent's NLU, Policy, and NLG). In our evaluation, we show that the stochastic-game agents outperform deep learning based supervised baselines.