OpenRaiser/Intern-Atlas huggingface dataset:
Structure Learning of $H$-colorings
Venue: arXiv cs.DM 2018
Year: 2018

We study the structure learning problem for $H$-colorings, an important class of Markov random fields that capture key combinatorial structures on graphs, including proper colorings and independent sets, as well as spin systems from statistical physics. The learning problem is as follows: for a fixed (and known) constraint graph $H$ with $q$ colors and an unknown graph $G=(V,E)$ with $n$ vertices, given uniformly random $H$-colorings of $G$, how many samples are required to learn the edges of the unknown graph $G$? We give a characterization of $H$ for which the problem is identifiable for every $G$, i.e., we can learn $G$ with an infinite number of samples. We also show that there are identifiable constraint graphs for which one cannot hope to learn every graph $G$ efficiently. We focus particular attention on the case of proper vertex $q$-colorings of graphs of maximum degree $d$ where intriguing connections to statistical physics phase transitions appear. We prove that in the tree uniqueness region (when $q>d$) the problem is identifiable and we can learn $G$ in ${\rm poly}(d,q) \times O(n^2\log{n})$ time. In contrast for soft-constraint systems, such as the Ising model, the best possible running time is exponential in $d$. In the tree non-uniqueness region (when $q\leq d$) we prove that the problem is not identifiable and thus $G$ cannot be learned. Moreover, when $q<d-\sqrt{d} + Θ(1)$ we prove that even learning an equivalent graph (any graph with the same set of $H$-colorings) is computationally hard---sample complexity is exponential in $n$ in the worst case. We further explore the connection between the efficiency/hardness of the structure learning problem and the uniqueness/non-uniqueness phase transition for general $H$-colorings and prove that under the well-known Dobrushin uniqueness condition, we can learn $G$ in ${\rm poly}(d,q)\times O(n^2\log{n})$ time.
Proof-Relevant Logical Relations for Name Generation
Venue: arXiv cs.LO 2018
Year: 2018

Pitts and Stark's $ν$-calculus is a paradigmatic total language for studying the problem of contextual equivalence in higher-order languages with name generation. Models for the $ν$-calculus that validate basic equivalences concerning names may be constructed using functor categories or nominal sets, with a dynamic allocation monad used to model computations that may allocate fresh names. If recursion is added to the language and one attempts to adapt the models from (nominal) sets to (nominal) domains, however, the direct-style construction of the allocation monad no longer works. This issue has previously been addressed by using a monad that combines dynamic allocation with continuations, at some cost to abstraction. This paper presents a direct-style model of a $ν$-calculus-like language with recursion using the novel framework of proof-relevant logical relations, in which logical relations also contain objects (or proofs) demonstrating the equivalence of (the semantic counterparts of) programs. Apart from providing a fresh solution to an old problem, this work provides an accessible setting in which to introduce the use of proof-relevant logical relations, free of the additional complexities associated with their use for more sophisticated languages.
Learning Universal Adversarial Perturbations with Generative Models
Venue: arXiv cs.CR 2018
Year: 2018

Neural networks are known to be vulnerable to adversarial examples, inputs that have been intentionally perturbed to remain visually similar to the source input, but cause a misclassification. It was recently shown that given a dataset and classifier, there exists so called universal adversarial perturbations, a single perturbation that causes a misclassification when applied to any input. In this work, we introduce universal adversarial networks, a generative network that is capable of fooling a target classifier when it's generated output is added to a clean sample from a dataset. We show that this technique improves on known universal adversarial attacks.
The streaming $k$-mismatch problem
Venue: arXiv cs.DS 2018
Year: 2018

We consider the streaming complexity of a fundamental task in approximate pattern matching: the $k$-mismatch problem. It asks to compute Hamming distances between a pattern of length $n$ and all length-$n$ substrings of a text for which the Hamming distance does not exceed a given threshold $k$. In our problem formulation, we report not only the Hamming distance but also, on demand, the full \emph{mismatch information}, that is the list of mismatched pairs of symbols and their indices. The twin challenges of streaming pattern matching derive from the need both to achieve small working space and also to guarantee that every arriving input symbol is processed quickly. We present a streaming algorithm for the $k$-mismatch problem which uses $O(k\log{n}\log\frac{n}{k})$ bits of space and spends \ourcomplexity time on each symbol of the input stream, which consists of the pattern followed by the text. The running time almost matches the classic offline solution and the space usage is within a logarithmic factor of optimal. Our new algorithm therefore effectively resolves and also extends an open problem first posed in FOCS'09. En route to this solution, we also give a deterministic $O( k (\log \frac{n}{k} + \log |Σ|) )$-bit encoding of all the alignments with Hamming distance at most $k$ of a length-$n$ pattern within a text of length $O(n)$. This secondary result provides an optimal solution to a natural communication complexity problem which may be of independent interest.
A Stronger Foundation for Computer Science and P=NP
Venue: arXiv cs.CC 2018
Year: 2018

This article describes a Turing machine which can solve for $β^{'}$ which is RE-complete. RE-complete problems are proven to be undecidable by Turing's accepted proof on the Entscheidungsproblem. Thus, constructing a machine which decides over $β^{'}$ implies inconsistency in ZFC. We then discover that unrestricted use of the axiom of substitution can lead to hidden assumptions in a certain class of proofs by contradiction. These hidden assumptions create an implied axiom of incompleteness for ZFC. Later, we offer a restriction on the axiom of substitution by introducing a new axiom which prevents impredicative tautologies from producing theorems. Our discovery in regards to these foundational arguments, disproves the SPACE hierarchy theorem which allows us to solve the P vs NP problem using a TIME-SPACE equivalence oracle.
Sim4CV: A Photo-Realistic Simulator for Computer Vision Applications
Venue: arXiv cs.CV 2018
Year: 2018

We present a photo-realistic training and evaluation simulator (Sim4CV) with extensive applications across various fields of computer vision. Built on top of the Unreal Engine, the simulator integrates full featured physics based cars, unmanned aerial vehicles (UAVs), and animated human actors in diverse urban and suburban 3D environments. We demonstrate the versatility of the simulator with two case studies: autonomous UAV-based tracking of moving objects and autonomous driving using supervised learning. The simulator fully integrates both several state-of-the-art tracking algorithms with a benchmark evaluation tool and a deep neural network (DNN) architecture for training vehicles to drive autonomously. It generates synthetic photo-realistic datasets with automatic ground truth annotations to easily extend existing real-world datasets and provides extensive synthetic data variety through its ability to reconfigure synthetic worlds on the fly using an automatic world generation tool. The supplementary video can be viewed a https://youtu.be/SqAxzsQ7qUU
Kirchhoff Index As a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms
Venue: arXiv cs.DS 2018
Year: 2018

Most previous work of centralities focuses on metrics of vertex importance and methods for identifying powerful vertices, while related work for edges is much lesser, especially for weighted networks, due to the computational challenge. In this paper, we propose to use the well-known Kirchhoff index as the measure of edge centrality in weighted networks, called $θ$-Kirchhoff edge centrality. The Kirchhoff index of a network is defined as the sum of effective resistances over all vertex pairs. The centrality of an edge $e$ is reflected in the increase of Kirchhoff index of the network when the edge $e$ is partially deactivated, characterized by a parameter $θ$. We define two equivalent measures for $θ$-Kirchhoff edge centrality. Both are global metrics and have a better discriminating power than commonly used measures, based on local or partial structural information of networks, e.g. edge betweenness and spanning edge centrality. Despite the strong advantages of Kirchhoff index as a centrality measure and its wide applications, computing the exact value of Kirchhoff edge centrality for each edge in a graph is computationally demanding. To solve this problem, for each of the $θ$-Kirchhoff edge centrality metrics, we present an efficient algorithm to compute its $ε$-approximation for all the $m$ edges in nearly linear time in $m$. The proposed $θ$-Kirchhoff edge centrality is the first global metric of edge importance that can be provably approximated in nearly-linear time. Moreover, according to the $θ$-Kirchhoff edge centrality, we present a $θ$-Kirchhoff vertex centrality measure, as well as a fast algorithm that can compute $ε$-approximate Kirchhoff vertex centrality for all the $n$ vertices in nearly linear time in $m$.
Gradient-based Camera Exposure Control for Outdoor Mobile Platforms
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a novel method to automatically adjust camera exposure for image processing and computer vision applications on mobile robot platforms. Because most image processing algorithms rely heavily on low-level image features that are based mainly on local gradient information, we consider that gradient quantity can determine the proper exposure level, allowing a camera to capture the important image features in a manner robust to illumination conditions. We then extend this concept to a multi-camera system and present a new control algorithm to achieve both brightness consistency between adjacent cameras and a proper exposure level for each camera. We implement our prototype system with off-the-shelf machine-vision cameras and demonstrate the effectiveness of the proposed algorithms on practical applications, including pedestrian detection, visual odometry, surround-view imaging, panoramic imaging and stereo matching.
Review on Computer Vision Techniques in Emergency Situation
Venue: arXiv cs.CV 2018
Year: 2018

In emergency situations, actions that save lives and limit the impact of hazards are crucial. In order to act, situational awareness is needed to decide what to do. Geolocalized photos and video of the situations as they evolve can be crucial in better understanding them and making decisions faster. Cameras are almost everywhere these days, either in terms of smartphones, installed CCTV cameras, UAVs or others. However, this poses challenges in big data and information overflow. Moreover, most of the time there are no disasters at any given location, so humans aiming to detect sudden situations may not be as alert as needed at any point in time. Consequently, computer vision tools can be an excellent decision support. The number of emergencies where computer vision tools has been considered or used is very wide, and there is a great overlap across related emergency research. Researchers tend to focus on state-of-the-art systems that cover the same emergency as they are studying, obviating important research in other fields. In order to unveil this overlap, the survey is divided along four main axes: the types of emergencies that have been studied in computer vision, the objective that the algorithms can address, the type of hardware needed and the algorithms used. Therefore, this review provides a broad overview of the progress of computer vision covering all sorts of emergencies.
Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern
Venue: arXiv cs.DS 2018
Year: 2018

The kTree problem is a special case of Subgraph Isomorphism where the pattern graph is a tree, that is, the input is an $n$-node graph $G$ and a $k$-node tree $T$, and the goal is to determine whether $G$ has a subgraph isomorphic to $T$. We provide evidence that this problem cannot be computed significantly faster than $2^{k} \textsf{poly}(n)$, which matches the fastest algorithm known for this problem by Koutis and Williams [ICALP 2009 and TALG 2016]. Specifically, we show that if kTree can be solved in time $(2-\varepsilon)^k \textsf{poly}(n)$ for some constant $\varepsilon>0$, then Set Cover with $n'$ elements and $m'$ sets can be solved in time $(2-δ)^{n'} \textsf{poly}(m')$ for a constant $δ(\varepsilon) > 0$, which would refute the Set Cover Conjecture by Cygan et al. [CCC 2012 and TALG 2016]. Our techniques yield a new algorithm for the p-Partial Cover problem, a parameterized version of Set Cover that requires covering at least $p$ elements (rather than all elements). Its running time is $(2+\varepsilon)^p (m')^{O(1/\varepsilon)}$ for any fixed $\varepsilon>0$, which improves the previous $2.597^p \textsf{poly}(m')$-time algorithm by Zehavi [ESA 2015]. Our running time is nearly optimal, as a $(2-\varepsilon')^p \textsf{poly}(m')$-time algorithm would refute the Set Cover Conjecture.
Deep learning with convolutional neural networks for decoding and visualization of EEG pathology
Venue: arXiv cs.LG 2018
Year: 2018

We apply convolutional neural networks (ConvNets) to the task of distinguishing pathological from normal EEG recordings in the Temple University Hospital EEG Abnormal Corpus. We use two basic, shallow and deep ConvNet architectures recently shown to decode task-related information from EEG at least as well as established algorithms designed for this purpose. In decoding EEG pathology, both ConvNets reached substantially better accuracies (about 6% better, ~85% vs. ~79%) than the only published result for this dataset, and were still better when using only 1 minute of each recording for training and only six seconds of each recording for testing. We used automated methods to optimize architectural hyperparameters and found intriguingly different ConvNet architectures, e.g., with max pooling as the only nonlinearity. Visualizations of the ConvNet decoding behavior showed that they used spectral power changes in the delta (0-4 Hz) and theta (4-8 Hz) frequency range, possibly alongside other features, consistent with expectations derived from spectral analysis of the EEG data and from the textual medical reports. Analysis of the textual medical reports also highlighted the potential for accuracy increases by integrating contextual information, such as the age of subjects. In summary, the ConvNets and visualization techniques used in this study constitute a next step towards clinically useful automated EEG diagnosis and establish a new baseline for future work on this topic.
Automatic Dataset Augmentation
Venue: arXiv cs.CV 2018
Year: 2018

Large scale image dataset and deep convolutional neural network (DCNN) are two primary driving forces for the rapid progress made in generic object recognition tasks in recent years. While lots of network architectures have been continuously designed to pursue lower error rates, few efforts are devoted to enlarge existing datasets due to high labeling cost and unfair comparison issues. In this paper, we aim to achieve lower error rate by augmenting existing datasets in an automatic manner. Our method leverages both Web and DCNN, where Web provides massive images with rich contextual information, and DCNN replaces human to automatically label images under guidance of Web contextual information. Experiments show our method can automatically scale up existing datasets significantly from billions web pages with high accuracy, and significantly improve the performance on object recognition tasks by using the automatically augmented datasets, which demonstrates that more supervisory information has been automatically gathered from the Web. Both the dataset and models trained on the dataset are made publicly available.
Re-run, Repeat, Reproduce, Reuse, Replicate: Transforming Code into Scientific Contributions
Venue: arXiv cs.GL 2018
Year: 2018

Scientific code is not production software. Scientific code participates in the evaluation of a scientific hypothesis. This imposes specific constraints on the code that are often overlooked in practice. We articulate, with a small example, five characteristics that a scientific code in computational science should possess: re-runnable, repeatable, reproducible, reusable and replicable.
A Compromise Principle in Deep Monocular Depth Estimation
Venue: arXiv cs.CV 2018
Year: 2018

Monocular depth estimation, which plays a key role in understanding 3D scene geometry, is fundamentally an ill-posed problem. Existing methods based on deep convolutional neural networks (DCNNs) have examined this problem by learning convolutional networks to estimate continuous depth maps from monocular images. However, we find that training a network to predict a high spatial resolution continuous depth map often suffers from poor local solutions. In this paper, we hypothesize that achieving a compromise between spatial and depth resolutions can improve network training. Based on this "compromise principle", we propose a regression-classification cascaded network (RCCN), which consists of a regression branch predicting a low spatial resolution continuous depth map and a classification branch predicting a high spatial resolution discrete depth map. The two branches form a cascaded structure allowing the classification and regression branches to benefit from each other. By leveraging large-scale raw training datasets and some data augmentation strategies, our network achieves top or state-of-the-art results on the NYU Depth V2, KITTI, and Make3D benchmarks.
Deterministic Digital Clustering of Wireless Ad Hoc Networks
Venue: arXiv cs.DS 2018
Year: 2018

We consider deterministic distributed communication in wireless ad hoc networks of identical weak devices under the SINR model without predefined infrastructure. Most algorithmic results in this model rely on various additional features or capabilities, e.g., randomization, access to geographic coordinates, power control, carrier sensing with various precision of measurements, and/or interference cancellation. We study a pure scenario, when no such properties are available. As a general tool, we develop a deterministic distributed clustering algorithm. Our solution relies on a new type of combinatorial structures (selectors), which might be of independent interest. Using the clustering, we develop a deterministic distributed local broadcast algorithm accomplishing this task in $O(Δ\log^*N \log N)$ rounds, where $Δ$ is the density of the network. To the best of our knowledge, this is the first solution in pure scenario which is only polylog$(n)$ away from the universal lower bound $Ω(Δ)$, valid also for scenarios with randomization and other features. Therefore, none of these features substantially helps in performing the local broadcast task. Using clustering, we also build a deterministic global broadcast algorithm that terminates within $O(D(Δ+ \log^* N) \log N)$ rounds, where $D$ is the diameter of the network. This result is complemented by a lower bound $Ω(D Δ^{1-1/α})$, where $α> 2$ is the path-loss parameter of the environment. This lower bound shows that randomization or knowledge of own location substantially help (by a factor polynomial in $Δ$) in the global broadcast. Therefore, unlike in the case of local broadcast, some additional model features may help in global broadcast.
A simple expression for the map of Asplund's distances with the multiplicative Logarithmic Image Processing (LIP) law
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a simple expression for the map of Asplund's distances with the multiplicative Logarithmic Image Processing (LIP) law. It is a difference between a morphological dilation and a morphological erosion with an additive structuring function which corresponds to a morphological gradient.
Real-Time 6DOF Pose Relocalization for Event Cameras with Stacked Spatial LSTM Networks
Venue: arXiv cs.CV 2018
Year: 2018

We present a new method to relocalize the 6DOF pose of an event camera solely based on the event stream. Our method first creates the event image from a list of events that occurs in a very short time interval, then a Stacked Spatial LSTM Network (SP-LSTM) is used to learn the camera pose. Our SP-LSTM is composed of a CNN to learn deep features from the event images and a stack of LSTM to learn spatial dependencies in the image feature space. We show that the spatial dependency plays an important role in the relocalization task and the SP-LSTM can effectively learn this information. The experimental results on a publicly available dataset show that our approach generalizes well and outperforms recent methods by a substantial margin. Overall, our proposed method reduces by approx. 6 times the position error and 3 times the orientation error compared to the current state of the art. The source code and trained models will be released.
Simultaneously Color-Depth Super-Resolution with Conditional Generative Adversarial Network
Venue: arXiv cs.CV 2018
Year: 2018

Recently, Generative Adversarial Network (GAN) has been found wide applications in style transfer, image-to-image translation and image super-resolution. In this paper, a color-depth conditional GAN is proposed to concurrently resolve the problems of depth super-resolution and color super-resolution in 3D videos. Firstly, given the low-resolution depth image and low-resolution color image, a generative network is proposed to leverage mutual information of color image and depth image to enhance each other in consideration of the geometry structural dependency of color-depth image in the same scene. Secondly, three loss functions, including data loss, total variation loss, and 8-connected gradient difference loss are introduced to train this generative network in order to keep generated images close to the real ones, in addition to the adversarial loss. Experimental results demonstrate that the proposed approach produces high-quality color image and depth image from low-quality image pair, and it is superior to several other leading methods. Besides, we use the same neural network framework to resolve the problem of image smoothing and edge detection at the same time.
Cascade Residual Learning: A Two-stage Convolutional Neural Network for Stereo Matching
Venue: arXiv cs.CV 2018
Year: 2018

Leveraging on the recent developments in convolutional neural networks (CNNs), matching dense correspondence from a stereo pair has been cast as a learning problem, with performance exceeding traditional approaches. However, it remains challenging to generate high-quality disparities for the inherently ill-posed regions. To tackle this problem, we propose a novel cascade CNN architecture composing of two stages. The first stage advances the recently proposed DispNet by equipping it with extra up-convolution modules, leading to disparity images with more details. The second stage explicitly rectifies the disparity initialized by the first stage; it couples with the first-stage and generates residual signals across multiple scales. The summation of the outputs from the two stages gives the final disparity. As opposed to directly learning the disparity at the second stage, we show that residual learning provides more effective refinement. Moreover, it also benefits the training of the overall cascade network. Experimentation shows that our cascade residual learning scheme provides state-of-the-art performance for matching stereo correspondence. By the time of the submission of this paper, our method ranks first in the KITTI 2015 stereo benchmark, surpassing the prior works by a noteworthy margin.