OpenRaiser/Intern-Atlas huggingface dataset:
Algorithms and Hardness Results for the Maximum Balanced Connected Subgraph Problem
Venue: arXiv cs.DS 2020
Year: 2020

The Balanced Connected Subgraph problem (BCS) was recently introduced by Bhore et al. (CALDAM 2019). In this problem, we are given a graph $G$ whose vertices are colored by red or blue. The goal is to find a maximum connected subgraph of $G$ having the same number of blue vertices and red vertices. They showed that this problem is NP-hard even on planar graphs, bipartite graphs, and chordal graphs. They also gave some positive results: BCS can be solved in $O(n^3)$ time for trees and $O(n + m)$ time for split graphs and properly colored bipartite graphs, where $n$ is the number of vertices and $m$ is the number of edges. In this paper, we show that BCS can be solved in $O(n^2)$ time for trees and $O(n^3)$ time for interval graphs. The former result can be extended to bounded treewidth graphs. We also consider a weighted version of BCS (WBCS). We prove that this variant is weakly NP-hard even on star graphs and strongly NP-hard even on split graphs and properly colored bipartite graphs, whereas the unweighted counterpart is tractable on those graph classes. Finally, we consider an exact exponential-time algorithm for general graphs. We show that BCS can be solved in $2^{n/2}n^{O(1)}$ time. This algorithm is based on a variant of Dreyfus-Wagner algorithm for the Steiner tree problem.
Adaptive Trade-Offs in Off-Policy Learning
Venue: arXiv cs.LG 2020
Year: 2020

A great variety of off-policy learning algorithms exist in the literature, and new breakthroughs in this area continue to be made, improving theoretical understanding and yielding state-of-the-art reinforcement learning algorithms. In this paper, we take a unifying view of this space of algorithms, and consider their trade-offs of three fundamental quantities: update variance, fixed-point bias, and contraction rate. This leads to new perspectives of existing methods, and also naturally yields novel algorithms for off-policy evaluation and control. We develop one such algorithm, C-trace, demonstrating that it is able to more efficiently make these trade-offs than existing methods in use, and that it can be scaled to yield state-of-the-art performance in large-scale environments.
Conditional Importance Sampling for Off-Policy Learning
Venue: arXiv cs.LG 2020
Year: 2020

The principal contribution of this paper is a conceptual framework for off-policy reinforcement learning, based on conditional expectations of importance sampling ratios. This framework yields new perspectives and understanding of existing off-policy algorithms, and reveals a broad space of unexplored algorithms. We theoretically analyse this space, and concretely investigate several algorithms that arise from this framework.
MAVEN: Multi-Agent Variational Exploration
Venue: arXiv cs.LG 2020
Year: 2020

Centralised training with decentralised execution is an important setting for cooperative deep multi-agent reinforcement learning due to communication constraints during execution and computational tractability in training. In this paper, we analyse value-based methods that are known to have superior performance in complex environments [43]. We specifically focus on QMIX [40], the current state-of-the-art in this domain. We show that the representational constraints on the joint action-values introduced by QMIX and similar methods lead to provably poor exploration and suboptimality. Furthermore, we propose a novel approach called MAVEN that hybridises value and policy-based methods by introducing a latent space for hierarchical control. The value-based agents condition their behaviour on the shared latent variable controlled by a hierarchical policy. This allows MAVEN to achieve committed, temporally extended exploration, which is key to solving complex multi-agent tasks. Our experimental results show that MAVEN achieves significant performance improvements on the challenging SMAC domain [43].
Mutual Information-driven Subject-invariant and Class-relevant Deep Representation Learning in BCI
Venue: arXiv cs.LG 2020
Year: 2020

In recent years, deep learning-based feature representation methods have shown a promising impact in electroencephalography (EEG)-based brain-computer interface (BCI). Nonetheless, owing to high intra- and inter-subject variabilities, many studies on decoding EEG were designed in a subject-specific manner by using calibration samples, with no concern of its practical use, hampered by time-consuming steps and a large data requirement. To this end, recent studies adopted a transfer learning strategy, especially domain adaptation techniques. Among those, to our knowledge, an adversarial learning has shown its potential in BCIs. In the meantime, it is known that adversarial learning-based domain adaptation methods are prone to negative transfer that disrupts learning generalized feature representations, applicable to diverse domains, e.g., subjects or sessions in BCIs. In this paper, we propose a novel framework that learns class-relevant and subject-invariant feature representations in an information-theoretic manner, without using adversarial learning. To be specific, we devise two operational components in a deep network that explicitly estimate mutual information between feature representations; (1) to decompose features in an intermediate layer into class-relevant and class-irrelevant ones, (2) to enrich class-discriminative feature representation. On two large EEG datasets, we validated the effectiveness of our proposed framework by comparing with several comparative methods in performance. Further, we conducted rigorous analyses by performing an ablation study in regard to the components in our network, explaining our model's decision on input EEG signals via layer-wise relevance propagation, and visualizing the distribution of learned features via t-SNE.
Teaching Vehicles to Anticipate: A Systematic Study on Probabilistic Behavior Prediction Using Large Data Sets
Venue: arXiv cs.LG 2020
Year: 2020

By observing their environment as well as other traffic participants, humans are enabled to drive road vehicles safely. Vehicle passengers, however, perceive a notable difference between non-experienced and experienced drivers. In particular, they may get the impression that the latter ones anticipate what will happen in the next few moments and consider these foresights in their driving behavior. To make the driving style of automated vehicles comparable to the one of human drivers with respect to comfort and perceived safety, the aforementioned anticipation skills need to become a built-in feature of self-driving vehicles. This article provides a systematic comparison of methods and strategies to generate this intention for self-driving cars using machine learning techniques. To implement and test these algorithms we use a large data set collected over more than 30000 km of highway driving and containing approximately 40000 real-world driving situations. We further show that it is possible to classify driving maneuvers upcoming within the next 5 s with an Area Under the ROC Curve (AUC) above 0.92 for all defined maneuver classes. This enables us to predict the lateral position with a prediction horizon of 5 s with a median lateral error of less than 0.21 m.
NAMF: A Non-local Adaptive Mean Filter for Salt-and-Pepper Noise Removal
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, a novel algorithm called a non-local adaptive mean filter (NAMF) for removing salt-and-pepper (SAP) noise from corrupted images is presented. We employ an efficient window detector with adaptive size to detect the noise, the noisy pixel will be replaced by the combination of its neighboring pixels, and finally we use a SAP noise based non-local mean filter to reconstruct the intensity values of noisy pixels. Extensive experimental results demonstrate that NAMF can obtain better performance in terms of quality for restoring images at all levels of SAP noise.
Generalized Absorptive Polynomials and Provenance Semantics for Fixed-Point Logic
Venue: arXiv cs.LO 2020
Year: 2020

Semiring provenance is a successful approach to provide detailed information on the combinations of atomic facts that are responsible for the result of a query. In particular, interpretations in general provenance semirings of polynomials or formal power series give precise descriptions of the successful evaluation strategies for the query. While provenance analysis in databases has, for a long time, been largely confined to negation-free query languages, a recent approach extends this to model checking problems for logics with full negation. Algebraically this relies on new quotient semirings of dual-indeterminate polynomials or power series. So far, this approach has been developed mainly for first-order logic and for the positive fragment of least fixed-point logic. What has remained open is an adequate treatment for fixed-point calculi that admit arbitrary interleavings of least and greatest fixed points. We show that an adequate framework for the provenance analysis of full fixed-point logics is provided by semirings that are (1) fully continuous, (2) absorptive, and (3) chain-positive. Full continuity guarantees that provenance values of least and greatest fixed-points are well-defined. Absorptive semirings provide a symmetry between least and greatest fixed-point computations and make sure that provenance values of greatest fixed points are informative. Finally, chain-positivity is responsible for having truth-preserving interpretations, which give non-zero values to all true formulae. We further identify semirings of generalized absorptive polynomials and prove universal properties that make them the most general appropriate semirings for LFP. We illustrate the power of provenance interpretations in these semirings by relating them to provenance values of plays and strategies in the associated model-checking games.
Deformable Kernel Networks for Joint Image Filtering
Venue: arXiv cs.CV 2020
Year: 2020

Joint image filters are used to transfer structural details from a guidance picture used as a prior to a target image, in tasks such as enhancing spatial resolution and suppressing noise. Previous methods based on convolutional neural networks (CNNs) combine nonlinear activations of spatially-invariant kernels to estimate structural details and regress the filtering result. In this paper, we instead learn explicitly sparse and spatially-variant kernels. We propose a CNN architecture and its efficient implementation, called the deformable kernel network (DKN), that outputs sets of neighbors and the corresponding weights adaptively for each pixel. The filtering result is then computed as a weighted average. We also propose a fast version of DKN that runs about seventeen times faster for an image of size 640 x 480. We demonstrate the effectiveness and flexibility of our models on the tasks of depth map upsampling, saliency map upsampling, cross-modality image restoration, texture removal, and semantic segmentation. In particular, we show that the weighted averaging process with sparsely sampled 3 x 3 kernels outperforms the state of the art by a significant margin in all cases.
A novel centroid update approach for clustering-based superpixel methods and superpixel-based edge detection
Venue: arXiv cs.CV 2020
Year: 2020

Superpixel is widely used in image processing. And among the methods for superpixel generation, clustering-based methods have a high speed and a good performance at the same time. However, most clustering-based superpixel methods are sensitive to noise. To solve these problems, in this paper, we first analyze the features of noise. Then according to the statistical features of noise, we propose a novel centroid update approach to enhance the robustness of clustering-based superpixel methods. Besides, we propose a novel superpixel-based edge detection method. The experiments on BSD500 dataset show that our approach can significantly enhance the performance of clustering-based superpixel methods in noisy environment. Moreover, we also show that our proposed edge detection method outperforms other classical methods.
User Manual CAI version-1.0: An Open-Source Toolbox for Computer-Aided Investigation on the Fundamental Limits of Information Systems
Venue: arXiv cs.IT 2020
Year: 2020

We provide an open source toolbox on https://github.com/ct2641/CAI/releases/tag/1.0 to conduct computer-aided investigation on the fundamental limits of information systems. The toolbox relies on either Gurobi or Cplex as the linear program solving engine. The program can read a problem description file, and then fulfill the following tasks: 1) compute a bound for a given linear combination of information measures and provide the value of information measures at the optimal solution; 2) efficiently compute a polytope tradeoff outer bound between two information quantities; 3) produce a proof (as a weighted sum of known information inequalities; and 4) provide the range for information quantities between which the optimal value does not change (sensitivity analysis). This technical report provides an overview of this toolbox, a detailed description of the syntax of the problem description file, and a few example use cases.
$\mathrm{P}$-Optimal Proof Systems for Each $\mathrm{coNP}$-Complete Set and no Complete Problems in $\mathrm{NP}\cap\mathrm{coNP}$ Relative to an Oracle
Venue: arXiv cs.CC 2020
Year: 2020

We build on a working program initiated by Pudlák [Pud17] and construct an oracle relative to which each $\mathrm{coNP}$-complete set has $\mathrm{P}$-optimal proof systems and $\mathrm{NP}\cap\mathrm{coNP}$ does not have complete problems.
Fast Portrait Segmentation with Highly Light-weight Network
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we describe a fast and light-weight portrait segmentation method based on a new highly light-weight backbone (HLB) architecture. The core element of HLB is a bottleneck-based factorized block (BFB) that has much fewer parameters than existing alternatives while keeping good learning capacity. Consequently, the HLB-based portrait segmentation method can run faster than the existing methods yet retaining the competitive accuracy performance with state-of-the-arts. Experiments conducted on two benchmark datasets demonstrate the effectiveness and efficiency of our method.
Top-Down Shape Abstraction Based on Greedy Pole Selection
Venue: arXiv cs.GR 2020
Year: 2020

Motivated by the fact that the medial axis transform is able to encode nearly the complete shape, we propose to use as few medial balls as possible to approximate the original enclosed volume by the boundary surface. We progressively select new medial balls, in a top-down style, to enlarge the region spanned by the existing medial balls. The key spirit of the selection strategy is to encourage large medial balls while imposing given geometric constraints. We further propose a speedup technique based on a provable observation that the intersection of medial balls implies the adjacency of power cells (in the sense of the power crust). We further elaborate the selection rules in combination with two closely related applications. One application is to develop an easy-to-use ball-stick modeling system that helps non-professional users to quickly build a shape with only balls and wires, but any penetration between two medial balls must be suppressed. The other application is to generate porous structures with convex, compact (with a high isoperimetric quotient) and shape-aware pores where two adjacent spherical pores may have penetration as long as the mechanical rigidity can be well preserved.
Checking Timed Bisimulation with Bounded Zone-History Graphs -- Technical Report
Venue: arXiv cs.FL 2020
Year: 2020

Timed automata (TA) are a well-established formalism for specifying discrete-state/continuous-time behavior of time-critical reactive systems. Concerning the fundamental analysis problem of comparing a candidate implementation against a specification, both given as TA, it has been shown that timed trace equivalence is undecidable, whereas timed bisimulation equivalence is decidable. The corresponding proof utilizes region graphs, a finite, but generally very space-consuming characterization of TA semantics. Hence, most practical TA tools utilize zone graphs instead, a symbolic and generally more efficient representation of TA semantics, to automate analysis tasks. However, zone graphs only produce sound results for analysis tasks being reducible to plain reachability problems thus being too imprecise for checking timed bisimilarity. In this paper, we propose bounded zone-history graphs, a novel characterization of TA semantics facilitating an adjustable trade-off between precision and scalability of timed-bisimilarity checking. Our tool TimBrCheck is, to the best of our knowledge, the only currently available tool for effectively checking timed bisimilarity and even supports non-deterministic TA with silent moves. We further present experimental results gained from applying our tool to a collection of community benchmarks, providing insights into trade-offs between precision and efficiency, depending on the bound value.
Looking Ahead: Anticipating Pedestrians Crossing with Future Frames Prediction
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we present an end-to-end future-prediction model that focuses on pedestrian safety. Specifically, our model uses previous video frames, recorded from the perspective of the vehicle, to predict if a pedestrian will cross in front of the vehicle. The long term goal of this work is to design a fully autonomous system that acts and reacts as a defensive human driver would --- predicting future events and reacting to mitigate risk. We focus on pedestrian-vehicle interactions because of the high risk of harm to the pedestrian if their actions are miss-predicted. Our end-to-end model consists of two stages: the first stage is an encoder/decoder network that learns to predict future video frames. The second stage is a deep spatio-temporal network that utilizes the predicted frames of the first stage to predict the pedestrian's future action. Our system achieves state-of-the-art accuracy on pedestrian behavior prediction and future frames prediction on the Joint Attention for Autonomous Driving (JAAD) dataset.
Localization of Fake News Detection via Multitask Transfer Learning
Venue: arXiv cs.CL 2020
Year: 2020

The use of the internet as a fast medium of spreading fake news reinforces the need for computational tools that combat it. Techniques that train fake news classifiers exist, but they all assume an abundance of resources including large labeled datasets and expert-curated corpora, which low-resource languages may not have. In this work, we make two main contributions: First, we alleviate resource scarcity by constructing the first expertly-curated benchmark dataset for fake news detection in Filipino, which we call "Fake News Filipino." Second, we benchmark Transfer Learning (TL) techniques and show that they can be used to train robust fake news classifiers from little data, achieving 91% accuracy on our fake news dataset, reducing the error by 14% compared to established few-shot baselines. Furthermore, lifting ideas from multitask learning, we show that augmenting transformer-based transfer techniques with auxiliary language modeling losses improves their performance by adapting to writing style. Using this, we improve TL performance by 4-6%, achieving an accuracy of 96% on our best model. Lastly, we show that our method generalizes well to different types of news articles, including political news, entertainment news, and opinion articles.
POTL: A First-Order Complete Temporal Logic for Operator Precedence Languages
Venue: arXiv cs.LO 2020
Year: 2020

The problem of model checking procedural programs has fostered much research towards the definition of temporal logics for reasoning on context-free structures. The most notable of such results are temporal logics on Nested Words, such as CaRet and NWTL. Recently, the logic OPTL was introduced, based on the class of Operator Precedence Languages (OPL), more powerful than Nested Words. We define the new OPL-based logic POTL, prove its FO-completeness, and provide a model checking procedure for it. POTL improves on NWTL by enabling the formulation of requirements involving pre/post-conditions, stack inspection, and others in the presence of exception-like constructs. It improves on OPTL by being FO-complete, and by expressing more easily stack inspection and function-local properties.
A Neural Entity Coreference Resolution Review
Venue: arXiv cs.CL 2020
Year: 2020

Entity Coreference Resolution is the task of resolving all mentions in a document that refer to the same real world entity and is considered as one of the most difficult tasks in natural language understanding. It is of great importance for downstream natural language processing tasks such as entity linking, machine translation, summarization, chatbots, etc. This work aims to give a detailed review of current progress on solving Coreference Resolution using neural-based approaches. It also provides a detailed appraisal of the datasets and evaluation metrics in the field, as well as the subtask of Pronoun Resolution that has seen various improvements in the recent years. We highlight the advantages and disadvantages of the approaches, the challenges of the task, the lack of agreed-upon standards in the task and propose a way to further expand the boundaries of the field.
Causal bootstrapping
Venue: arXiv cs.LG 2020
Year: 2020

To draw scientifically meaningful conclusions and build reliable models of quantitative phenomena, cause and effect must be taken into consideration (either implicitly or explicitly). This is particularly challenging when the measurements are not from controlled experimental (interventional) settings, since cause and effect can be obscured by spurious, indirect influences. Modern predictive techniques from machine learning are capable of capturing high-dimensional, nonlinear relationships between variables while relying on few parametric or probabilistic model assumptions. However, since these techniques are associational, applied to observational data they are prone to picking up spurious influences from non-experimental (observational) data, making their predictions unreliable. Techniques from causal inference, such as probabilistic causal diagrams and do-calculus, provide powerful (nonparametric) tools for drawing causal inferences from such observational data. However, these techniques are often incompatible with modern, nonparametric machine learning algorithms since they typically require explicit probabilistic models. Here, we develop causal bootstrapping for augmenting classical nonparametric bootstrap resampling with information on the causal relationship between variables. This makes it possible to resample observational data such that, if it is possible to identify an interventional relationship from that data, new data representing that relationship can be simulated from the original observational data. In this way, we can use modern machine learning algorithms unaltered to make statistically powerful, yet causally-robust, predictions. We develop several causal bootstrapping algorithms for drawing interventional inferences from observational data, for classification and regression problems, and demonstrate, using synthetic and real-world examples, the value of this approach.