OpenRaiser/Intern-Atlas huggingface dataset:
Robust and Precise Vehicle Localization based on Multi-sensor Fusion in Diverse City Scenes
Venue: arXiv cs.CV 2020
Year: 2020

We present a robust and precise localization system that achieves centimeter-level localization accuracy in disparate city scenes. Our system adaptively uses information from complementary sensors such as GNSS, LiDAR, and IMU to achieve high localization accuracy and resilience in challenging scenes, such as urban downtown, highways, and tunnels. Rather than relying only on LiDAR intensity or 3D geometry, we make innovative use of LiDAR intensity and altitude cues to significantly improve localization system accuracy and robustness. Our GNSS RTK module utilizes the help of the multi-sensor fusion framework and achieves a better ambiguity resolution success rate. An error-state Kalman filter is applied to fuse the localization measurements from different sources with novel uncertainty estimation. We validate, in detail, the effectiveness of our approaches, achieving 5-10cm RMS accuracy and outperforming previous state-of-the-art systems. Importantly, our system, while deployed in a large autonomous driving fleet, made our vehicles fully autonomous in crowded city streets despite road construction that occurred from time to time. A dataset including more than 60 km real traffic driving in various urban roads is used to comprehensively test our system.
High-resolution Deep Convolutional Generative Adversarial Networks
Venue: arXiv cs.CV 2020
Year: 2020

Generative Adversarial Networks (GANs) [Goodfellow et al. 2014] convergence in a high-resolution setting with a computational constrain of GPU memory capacity has been beset with difficulty due to the known lack of convergence rate stability. In order to boost network convergence of DCGAN (Deep Convolutional Generative Adversarial Networks) [Radford et al. 2016] and achieve good-looking high-resolution results we propose a new layered network, HDCGAN, that incorporates current state-of-the-art techniques for this effect. Glasses, a mechanism to arbitrarily improve the final GAN generated results by enlarging the input size by a telescope ζ is also presented. A novel bias-free dataset, Curtó & Zarza, containing human faces from different ethnical groups in a wide variety of illumination conditions and image resolutions is introduced. Curtó is enhanced with HDCGAN synthetic images, thus being the first GAN augmented dataset of faces. We conduct extensive experiments on CelebA [Liu et al. 2015], CelebA-hq [Karras et al. 2018] and Curtó. HDCGAN is the current state-of-the-art in synthetic image generation on CelebA achieving a MS-SSIM of 0.1978 and a FRÉCHET Inception Distance of 8.44.
Deep Eyes: Binocular Depth-from-Focus on Focal Stack Pairs
Venue: arXiv cs.CV 2020
Year: 2020

Human visual system relies on both binocular stereo cues and monocular focusness cues to gain effective 3D perception. In computer vision, the two problems are traditionally solved in separate tracks. In this paper, we present a unified learning-based technique that simultaneously uses both types of cues for depth inference. Specifically, we use a pair of focal stacks as input to emulate human perception. We first construct a comprehensive focal stack training dataset synthesized by depth-guided light field rendering. We then construct three individual networks: a Focus-Net to extract depth from a single focal stack, a EDoF-Net to obtain the extended depth of field (EDoF) image from the focal stack, and a Stereo-Net to conduct stereo matching. We show how to integrate them into a unified BDfF-Net to obtain high-quality depth maps. Comprehensive experiments show that our approach outperforms the state-of-the-art in both accuracy and speed and effectively emulates human vision systems.
Deep Image Prior
Venue: arXiv cs.CV 2020
Year: 2020

Deep convolutional networks have become a popular tool for image generation and restoration. Generally, their excellent performance is imputed to their ability to learn realistic image priors from a large number of example images. In this paper, we show that, on the contrary, the structure of a generator network is sufficient to capture a great deal of low-level image statistics prior to any learning. In order to do so, we show that a randomly-initialized neural network can be used as a handcrafted prior with excellent results in standard inverse problems such as denoising, super-resolution, and inpainting. Furthermore, the same prior can be used to invert deep neural representations to diagnose them, and to restore images based on flash-no flash input pairs. Apart from its diverse applications, our approach highlights the inductive bias captured by standard generator network architectures. It also bridges the gap between two very popular families of image restoration methods: learning-based methods using deep convolutional networks and learning-free methods based on handcrafted image priors such as self-similarity. Code and supplementary material are available at https://dmitryulyanov.github.io/deep_image_prior .
Towards Real-Time Advancement of Underwater Visual Quality with GAN
Venue: arXiv cs.CV 2020
Year: 2020

Low visual quality has prevented underwater robotic vision from a wide range of applications. Although several algorithms have been developed, real-time and adaptive methods are deficient for real-world tasks. In this paper, we address this difficulty based on generative adversarial networks (GAN), and propose a GAN-based restoration scheme (GAN-RS). In particular, we develop a multi-branch discriminator including an adversarial branch and a critic branch for the purpose of simultaneously preserving image content and removing underwater noise. In addition to adversarial learning, a novel dark channel prior loss also promotes the generator to produce realistic vision. More specifically, an underwater index is investigated to describe underwater properties, and a loss function based on the underwater index is designed to train the critic branch for underwater noise suppression. Through extensive comparisons on visual quality and feature restoration, we confirm the superiority of the proposed approach. Consequently, the GAN-RS can adaptively improve underwater visual quality in real time and induce an overall superior restoration performance. Finally, a real-world experiment is conducted on the seabed for grasping marine products, and the results are quite promising. The source code is publicly available at https://github.com/SeanChenxy/GAN_RS.
Specifying and Computing Causes for Query Answers in Databases via Database Repairs and Repair Programs
Venue: arXiv cs.DB 2020
Year: 2020

A correspondence between database tuples as causes for query answers in databases and tuple-based repairs of inconsistent databases with respect to denial constraints has already been established. In this work, answer-set programs that specify repairs of databases are used as a basis for solving computational and reasoning problems about causes. Here, causes are also introduced at the attribute level by appealing to a both null-based and attribute-based repair semantics. The corresponding repair programs are presented, and they are used as a basis for computation and reasoning about attribute-level causes. They are extended to deal with the case of causality under integrity constraints.
Arrangements of Pseudocircles: On Circularizability
Venue: arXiv cs.CG 2020
Year: 2020

An arrangement of pseudocircles is a collection of simple closed curves on the sphere or in the plane such that any two of the curves are either disjoint or intersect in exactly two crossing points. We call an arrangement intersecting if every pair of pseudocircles intersects twice. An arrangement is circularizable if there is a combinatorially equivalent arrangement of circles. In this paper we present the results of the first thorough study of circularizability. We show that there are exactly four non-circularizable arrangements of 5 pseudocircles (one of them was known before). In the set of 2131 digon-free intersecting arrangements of 6 pseudocircles we identify the three non-circularizable examples. We also show non-circularizability of 8 additional arrangements of 6 pseudocircles which have a group of symmetries of size at least 4. Most of our non-circularizability proofs depend on incidence theorems like Miquel's. In other cases we contradict circularizability by considering a continuous deformation where the circles of an assumed circle representation grow or shrink in a controlled way. The claims that we have all non-circularizable arrangements with the given properties are based on a program that generated all arrangements up to a certain size. Given the complete lists of arrangements, we used heuristics to find circle representations. Examples where the heuristics failed were examined by hand.
On the Longest Spanning Tree with Neighborhoods
Venue: arXiv cs.CG 2020
Year: 2020

We study a maximization problem for geometric network design. Given a set of $n$ compact neighborhoods in $\mathbb{R}^d$, select a point in each neighborhood, so that the longest spanning tree on these points (as vertices) has maximum length. Here we give an approximation algorithm with ratio $0.511$, which represents the first, albeit small, improvement beyond $1/2$. While we suspect that the problem is NP-hard already in the plane, this issue remains open.
Multi-Fidelity Reinforcement Learning with Gaussian Processes
Venue: arXiv cs.RO 2020
Year: 2020

We study the problem of Reinforcement Learning (RL) using as few real-world samples as possible. A naive application of RL can be inefficient in large and continuous state spaces. We present two versions of Multi-Fidelity Reinforcement Learning (MFRL), model-based and model-free, that leverage Gaussian Processes (GPs) to learn the optimal policy in a real-world environment. In the MFRL framework, an agent uses multiple simulators of the real environment to perform actions. With increasing fidelity in a simulator chain, the number of samples used in successively higher simulators can be reduced. By incorporating GPs in the MFRL framework, we empirically observe up to $40\%$ reduction in the number of samples for model-based RL and $60\%$ reduction for the model-free version. We examine the performance of our algorithms through simulations and through real-world experiments for navigation with a ground robot.
Path Loss and Directional Gain Measurements at 28 GHz for non-Line-of-Sight Coverage of Indoors with Corridors
Venue: arXiv cs.IT 2020
Year: 2020

Adequate coverage with high gain antennas is key to realizing the full promise of the bandwidth available at mm/cm wave bands. We report extensive indoor measurements at 28 GHz (1000 links, 9.9 million individual power measurements, 10 offices, 2 buildings), with/without line-of-sight (LOS) using a continuous wave channel sounder, with a 10o spinning horn, capable of capturing a full azimuth scan every 200 ms, in up to 171 dB path loss to characterize coverage with 90% confidence level. The environment had prominent corridors and rooms, as opposed to open/mixed offices in latest 3GPP standards. Guiding in corridors leads to much lower RMS azimuth spread (7 degree median in corridor non-LOS vs. 42 degree in 3GPP) and higher penetration loss into rooms and around corners (30-32 dB, some 12 dB more loss than 3GPP at 20 m non-LOS). Measured path gain in non-LOS is predicted by a mode-diffusion model with 3.9 dB RMS error. Scattering degraded azimuth gain by up to 4 dB in the corridor and 7 dB in rooms with 90% probability. Link simulations in a canonical building indicate every corridor needs an access point to provide 1 Gbps rate to adjoining rooms within 50 m using 400 MHz of bandwidth.
Automata Minimization: a Functorial Approach
Venue: arXiv cs.LO 2020
Year: 2020

In this paper we regard languages and their acceptors - such as deterministic or weighted automata, transducers, or monoids - as functors from input categories that specify the type of the languages and of the machines to categories that specify the type of outputs. Our results are as follows: A) We provide sufficient conditions on the output category so that minimization of the corresponding automata is guaranteed. B) We show how to lift adjunctions between the categories for output values to adjunctions between categories of automata. C) We show how this framework can be instantiated to unify several phenomena in automata theory, starting with determinization, minimization and syntactic algebras. We provide explanations of Choffrut's minimization algorithm for subsequential transducers and of Brzozowski's minimization algorithm in this setting.
Combinatorics of Beacon-based Routing in Three Dimensions
Venue: arXiv cs.CG 2020
Year: 2020

A beacon is a point-like object which can be enabled to exert a magnetic pull on other point-like objects in space. Those objects then move towards the beacon in a greedy fashion until they are either stuck at an obstacle or reach the beacon's location. Beacons placed inside polyhedra can be used to route point-like objects from one location to another. A second use case is to cover a polyhedron such that every point-like object at an arbitrary location in the polyhedron can reach at least one of the beacons once the latter is activated. The notion of beacon-based routing and guarding was introduced by Biro et al. [FWCG'11] in 2011 and covered in detail by Biro in his PhD thesis [SUNY-SB'13], which focuses on the two-dimensional case. We extend Biro's result to three dimensions by considering beacon routing in polyhedra. We show that $\lfloor\frac{m+1}{3}\rfloor$ beacons are always sufficient and sometimes necessary to route between any pair of points in a given polyhedron $P$, where $m$ is the number of tetrahedra in a tetrahedral decomposition of $P$. This is one of the first results that show that beacon routing is also possible in three dimensions.
Complexity Theory, Game Theory, and Economics: The Barbados Lectures
Venue: arXiv cs.CC 2020
Year: 2020

This document collects the lecture notes from my mini-course "Complexity Theory, Game Theory, and Economics," taught at the Bellairs Research Institute of McGill University, Holetown, Barbados, February 19--23, 2017, as the 29th McGill Invitational Workshop on Computational Complexity. The goal of this mini-course is twofold: (i) to explain how complexity theory has helped illuminate several barriers in economics and game theory; and (ii) to illustrate how game-theoretic questions have led to new and interesting complexity theory, including recent several breakthroughs. It consists of two five-lecture sequences: the Solar Lectures, focusing on the communication and computational complexity of computing equilibria; and the Lunar Lectures, focusing on applications of complexity theory in game theory and economics. No background in game theory is assumed.
A Study of Bug Resolution Characteristics in Popular Programming Languages
Venue: arXiv cs.SE 2020
Year: 2020

This paper presents a large-scale study that investigates the bug resolution characteristics among popular Github projects written in different programming languages. We explore correlations but, of course, we cannot infer causation. Specifically, we analyse bug resolution data from approximately 70 million Source Line of Code, drawn from 3 million commits to 600 GitHub projects, primarily written in 10 programming languages. We find notable variations in apparent bug resolution time and patch (fix) size. While interpretation of results from such large-scale empirical studies is inherently difficult, we believe that the differences in medians are sufficiently large to warrant further investigation, replication, re-analysis and follow up research. For example, in our corpus, the median apparent bug resolution time (elapsed time from raise to resolve) for Ruby was 4X that for Go and 2.5X for Java. We also found that patches tend to touch more files for the corpus of strongly typed and for statically typed programs. However, we also found evidence for a lower elapsed resolution time for bug resolution committed to projects constructed from statically typed languages. These findings, if replicated in subsequent follow on studies, may shed further empirical light on the debate about the importance of static typing.
Between an Arena and a Sports Bar: Online Chats of eSports Spectators
Venue: arXiv cs.HC 2020
Year: 2020

Hundreds of thousands of spectators use Twitch.tv to watch The International, a Dota 2 eSports tournament and communicate in massive chats. In this paper, we analyse crowd behavior in these chats, disentangle features of social communication, such as contextual meanings of emojis and short messages. We apply structural topic modelling and cross-correlation analysis to investigate topical and temporal patterns of chat messages and their relation to in-game events. We show that in-game events drive the communication in the massive chat and define its emergent topical structure to a various extent. Following the discussion in communication and social computing literature, we discuss these findings in the framework of analysis of communication of physical sports crowds and outline some limitations of the 'stadium' metaphor, suggesting a complementary metaphor of 'sports bar' as a useful analytical and design device.
Generalizations of Fano's Inequality for Conditional Information Measures via Majorization Theory
Venue: arXiv cs.IT 2020
Year: 2020

Fano's inequality is one of the most elementary, ubiquitous, and important tools in information theory. Using majorization theory, Fano's inequality is generalized to a broad class of information measures, which contains those of Shannon and Rényi. When specialized to these measures, it recovers and generalizes the classical inequalities. Key to the derivation is the construction of an appropriate conditional distribution inducing a desired marginal distribution on a countably infinite alphabet. The construction is based on the infinite-dimensional version of Birkhoff's theorem proven by Révész [Acta Math. Hungar. 1962, 3, 188{\textendash}198], and the constraint of maintaining a desired marginal distribution is similar to coupling in probability theory. Using our Fano-type inequalities for Shannon's and Rényi's information measures, we also investigate the asymptotic behavior of the sequence of Shannon's and Rényi's equivocations when the error probabilities vanish. This asymptotic behavior provides a novel characterization of the asymptotic equipartition property (AEP) via Fano's inequality.
A Human-Grounded Evaluation Benchmark for Local Explanations of Machine Learning
Venue: arXiv cs.HC 2020
Year: 2020

Research in interpretable machine learning proposes different computational and human subject approaches to evaluate model saliency explanations. These approaches measure different qualities of explanations to achieve diverse goals in designing interpretable machine learning systems. In this paper, we propose a human attention benchmark for image and text domains using multi-layer human attention masks aggregated from multiple human annotators. We then present an evaluation study to evaluate model saliency explanations obtained using Grad-cam and LIME techniques. We demonstrate our benchmark's utility for quantitative evaluation of model explanations by comparing it with human subjective ratings and ground-truth single-layer segmentation masks evaluations. Our study results show that our threshold agnostic evaluation method with the human attention baseline is more effective than single-layer object segmentation masks to ground truth. Our experiments also reveal user biases in the subjective rating of model saliency explanations.
Coded Computing for Distributed Graph Analytics
Venue: arXiv cs.DC 2020
Year: 2020

Performance of distributed graph processing systems significantly suffers from 'communication bottleneck' as a large number of messages are exchanged among servers at each step of the computation. Motivated by graph based MapReduce, we propose a coded computing framework that leverages computation redundancy to alleviate the communication bottleneck in distributed graph processing. We develop a novel 'coding' scheme that systematically injects structured redundancy in computation phase to enable 'coded' multicasting opportunities during message exchange between servers, reducing communication load substantially in large-scale graph processing. For theoretical analysis, we consider random graph models, and prove that our proposed scheme enables an (asymptotically) inverse-linear trade-off between 'computation load' and 'average communication load' for two popular random graph models -- Erdos-Renyi model, and power law model. Particularly, for a given computation load r, (i.e. when each graph vertex is carefully stored at r servers), the proposed scheme slashes the average communication load by (nearly) a multiplicative factor of r. For the Erdos-Renyi model, our proposed scheme is optimal asymptotically as the graph size increases by providing an information-theoretic converse. To illustrate the benefits of our scheme in practice, we implement PageRank over Amazon EC2, using artificial as well as real-world datasets, demonstrating significant gains over conventional PageRank. We also specialize our scheme and extend our theoretical results to two other random graph models -- random bi-partite model, and stochastic block model. They asymptotically enable inverse-linear trade-offs between computation and communication loads in distributed graph processing for these popular random graph models as well. We complement the achievability results with converse bounds for both of these models.
Bayesian Filtering with Unknown Sensor Measurement Losses
Venue: arXiv cs.SY 2020
Year: 2020

This work studies the state estimation problem of a stochastic nonlinear system with unknown sensor measurement losses. If the estimator knows the sensor measurement losses of a linear Gaussian system, the minimum variance estimate is easily computed by the celebrated intermittent Kalman filter (IKF). However, this will no longer be the case when the measurement losses are unknown and/or the system is nonlinear or non-Gaussian. By exploiting the binary property of the measurement loss process and the IKF, we design three suboptimal filters for the state estimation, i.e., BKF-I, BKF-II and RBPF. The BKF-I is based on the MAP estimator of the measurement loss process and the BKF-II is derived by estimating the conditional loss probability. The RBPF is a particle filter based algorithm which marginalizes out the loss process to increase the efficiency of particles. All the proposed filters can be easily implemented in recursive forms. Finally, a linear system, a target tracking system and a quadrotor's path control problem are included to illustrate their effectiveness, and show the tradeoff between computational complexity and estimation accuracy of the proposed filters.
Theory of higher order interpretations and application to Basic Feasible Functions
Venue: arXiv cs.LO 2020
Year: 2020

Interpretation methods and their restrictions to polynomials have been deeply used to control the termination and complexity of first-order term rewrite systems. This paper extends interpretation methods to a pure higher order functional language. We develop a theory of higher order functions that is well-suited for the complexity analysis of this programming language. The interpretation domain is a complete lattice and, consequently, we express program interpretation in terms of a least fixpoint. As an application, by bounding interpretations by higher order polynomials, we characterize Basic Feasible Functions at any order.