OpenRaiser/Intern-Atlas huggingface dataset:
Fine-Tuning BERT for Schema-Guided Zero-Shot Dialogue State Tracking
Venue: arXiv cs.CL 2020
Year: 2020

We present our work on Track 4 in the Dialogue System Technology Challenges 8 (DSTC8). The DSTC8-Track 4 aims to perform dialogue state tracking (DST) under the zero-shot settings, in which the model needs to generalize on unseen service APIs given a schema definition of these target APIs. Serving as the core for many virtual assistants such as Siri, Alexa, and Google Assistant, the DST keeps track of the user's goal and what happened in the dialogue history, mainly including intent prediction, slot filling, and user state tracking, which tests models' ability of natural language understanding. Recently, the pretrained language models have achieved state-of-the-art results and shown impressive generalization ability on various NLP tasks, which provide a promising way to perform zero-shot learning for language understanding. Based on this, we propose a schema-guided paradigm for zero-shot dialogue state tracking (SGP-DST) by fine-tuning BERT, one of the most popular pretrained language models. The SGP-DST system contains four modules for intent prediction, slot prediction, slot transfer prediction, and user state summarizing respectively. According to the official evaluation results, our SGP-DST (team12) ranked 3rd on the joint goal accuracy (primary evaluation metric for ranking submissions) and 1st on the requsted slots F1 among 25 participant teams.
Large Hole Image Inpainting With Compress-Decompression Network
Venue: arXiv cs.CV 2020
Year: 2020

Image inpainting technology can patch images with missing pixels. Existing methods propose convolutional neural networks to repair corrupted images. The networks focus on the valid pixels around the missing pixels, use the encoder-decoder structure to extract valuable information, and use the information to fix the vacancy. However, if the missing part is too large to provide useful information, the result will exist blur, color mixing, and object confusion. In order to patch the large hole image, we study the existing approaches and propose a new network, the compression-decompression network. The compression network takes responsibility for inpainting and generating a down-sample image. The decompression network takes responsibility for extending the down-sample image into the original resolution. We construct the compression network with the residual network and propose a similar texture selection algorithm to extend the image that is better than using the super-resolution network. We evaluate our model over Places2 and CelebA data set and use the similarity ratio as the metric. The result shows that our model has better performance when the inpainting task has many conflicts.
Molecule Property Prediction and Classification with Graph Hypernetworks
Venue: arXiv cs.LG 2020
Year: 2020

Graph neural networks are currently leading the performance charts in learning-based molecule property prediction and classification. Computational chemistry has, therefore, become the a prominent testbed for generic graph neural networks, as well as for specialized message passing methods. In this work, we demonstrate that the replacement of the underlying networks with hypernetworks leads to a boost in performance, obtaining state of the art results in various benchmarks. A major difficulty in the application of hypernetworks is their lack of stability. We tackle this by combining the current message and the first message. A recent work has tackled the training instability of hypernetworks in the context of error correcting codes, by replacing the activation function of the message passing network with a low-order Taylor approximation of it. We demonstrate that our generic solution can replace this domain-specific solution.
A Corrective View of Neural Networks: Representation, Memorization and Learning
Venue: arXiv cs.LG 2020
Year: 2020

We develop a corrective mechanism for neural network approximation: the total available non-linear units are divided into multiple groups and the first group approximates the function under consideration, the second group approximates the error in approximation produced by the first group and corrects it, the third group approximates the error produced by the first and second groups together and so on. This technique yields several new representation and learning results for neural networks. First, we show that two-layer neural networks in the random features regime (RF) can memorize arbitrary labels for arbitrary points under under Euclidean distance separation condition using $\tilde{O}(n)$ ReLUs which is optimal in $n$ up to logarithmic factors. Next, we give a powerful representation result for two-layer neural networks with ReLUs and smoothed ReLUs which can achieve a squared error of at most $ε$ with $O(C(a,d)ε^{-1/(a+1)})$ for $a \in \mathbb{N}\cup\{0\}$ when the function is smooth enough (roughly when it has $Θ(ad)$ bounded derivatives). In certain cases $d$ can be replaced with effective dimension $q \ll d$. Previous results of this type implement Taylor series approximation using deep architectures. We also consider three-layer neural networks and show that the corrective mechanism yields faster representation rates for smooth radial functions. Lastly, we obtain the first $O(\mathrm{subpoly}(1/ε))$ upper bound on the number of neurons required for a two layer network to learn low degree polynomials up to squared error $ε$ via gradient descent. Even though deep networks can express these polynomials with $O(\mathrm{polylog}(1/ε))$ neurons, the best learning bounds on this problem require $\mathrm{poly}(1/ε)$ neurons.
The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians
Venue: arXiv cs.LG 2020
Year: 2020

We consider the problem of spherical Gaussian Mixture models with $k \geq 3$ components when the components are well separated. A fundamental previous result established that separation of $Ω(\sqrt{\log k})$ is necessary and sufficient for identifiability of the parameters with polynomial sample complexity (Regev and Vijayaraghavan, 2017). In the same context, we show that $\tilde{O} (kd/ε^2)$ samples suffice for any $ε\lesssim 1/k$, closing the gap from polynomial to linear, and thus giving the first optimal sample upper bound for the parameter estimation of well-separated Gaussian mixtures. We accomplish this by proving a new result for the Expectation-Maximization (EM) algorithm: we show that EM converges locally, under separation $Ω(\sqrt{\log k})$. The previous best-known guarantee required $Ω(\sqrt{k})$ separation (Yan, et al., 2017). Unlike prior work, our results do not assume or use prior knowledge of the (potentially different) mixing weights or variances of the Gaussian components. Furthermore, our results show that the finite-sample error of EM does not depend on non-universal quantities such as pairwise distances between means of Gaussian components.
3D Object Detection on Point Clouds using Local Ground-aware and Adaptive Representation of scenes' surface
Venue: arXiv cs.CV 2020
Year: 2020

A novel, adaptive ground-aware, and cost-effective 3D Object Detection pipeline is proposed. The ground surface representation introduced in this paper, in comparison to its uni-planar counterparts (methods that model the surface of a whole 3D scene using single plane), is far more accurate while being ~10x faster. The novelty of the ground representation lies both in the way in which the ground surface of the scene is represented in Lidar perception problems, as well as in the (cost-efficient) way in which it is computed. Furthermore, the proposed object detection pipeline builds on the traditional two-stage object detection models by incorporating the ability to dynamically reason the surface of the scene, ultimately achieving a new state-of-the-art 3D object detection performance among the two-stage Lidar Object Detection pipelines.
Avocado: Open-Source Flexible Constrained Interaction Testing for Practical Application
Venue: arXiv cs.SE 2020
Year: 2020

This paper presents the outcome of a research collaboration between academia and industry to implement and utilize the capabilities of constrained interaction testing for an open-source tool for industrial-scale application. The project helps promote flexibility in generating constrained interaction test suites, executing them, and setting up a test oracle to report them--all within the same tool called Avocado. Avocado employs a constraint solver with computational algorithms to generate constrained interaction test suites. The environment of the application under test can be set up to execute the generated test suite with minimum effort. A test oracle can be set up by the tool to report the status and the results of the executed test cases. Avocado represents a comprehensive and flexible solution for conducting combinatorial interaction testing (CIT) and constrained CIT on an industrial application. In this paper, we present the structure of the tool and our method of implementing the algorithms in detail.
Combating False Negatives in Adversarial Imitation Learning
Venue: arXiv cs.LG 2020
Year: 2020

In adversarial imitation learning, a discriminator is trained to differentiate agent episodes from expert demonstrations representing the desired behavior. However, as the trained policy learns to be more successful, the negative examples (the ones produced by the agent) become increasingly similar to expert ones. Despite the fact that the task is successfully accomplished in some of the agent's trajectories, the discriminator is trained to output low values for them. We hypothesize that this inconsistent training signal for the discriminator can impede its learning, and consequently leads to worse overall performance of the agent. We show experimental evidence for this hypothesis and that the 'False Negatives' (i.e. successful agent episodes) significantly hinder adversarial imitation learning, which is the first contribution of this paper. Then, we propose a method to alleviate the impact of false negatives and test it on the BabyAI environment. This method consistently improves sample efficiency over the baselines by at least an order of magnitude.
Integrating Deep Reinforcement Learning with Model-based Path Planners for Automated Driving
Venue: arXiv cs.AI 2020
Year: 2020

Automated driving in urban settings is challenging. Human participant behavior is difficult to model, and conventional, rule-based Automated Driving Systems (ADSs) tend to fail when they face unmodeled dynamics. On the other hand, the more recent, end-to-end Deep Reinforcement Learning (DRL) based model-free ADSs have shown promising results. However, pure learning-based approaches lack the hard-coded safety measures of model-based controllers. Here we propose a hybrid approach for integrating a path planning pipe into a vision based DRL framework to alleviate the shortcomings of both worlds. In summary, the DRL agent is trained to follow the path planner's waypoints as close as possible. The agent learns this policy by interacting with the environment. The reward function contains two major terms: the penalty of straying away from the path planner and the penalty of having a collision. The latter has precedence in the form of having a significantly greater numerical value. Experimental results show that the proposed method can plan its path and navigate between randomly chosen origin-destination points in CARLA, a dynamic urban simulation environment. Our code is open-source and available online.
Accelerating Cooperative Planning for Automated Vehicles with Learned Heuristics and Monte Carlo Tree Search
Venue: arXiv cs.LG 2020
Year: 2020

Efficient driving in urban traffic scenarios requires foresight. The observation of other traffic participants and the inference of their possible next actions depending on the own action is considered cooperative prediction and planning. Humans are well equipped with the capability to predict the actions of multiple interacting traffic participants and plan accordingly, without the need to directly communicate with others. Prior work has shown that it is possible to achieve effective cooperative planning without the need for explicit communication. However, the search space for cooperative plans is so large that most of the computational budget is spent on exploring the search space in unpromising regions that are far away from the solution. To accelerate the planning process, we combined learned heuristics with a cooperative planning method to guide the search towards regions with promising actions, yielding better solutions at lower computational costs.
Towards Brain-Computer Interfaces for Drone Swarm Control
Venue: arXiv cs.NE 2020
Year: 2020

Noninvasive brain-computer interface (BCI) decodes brain signals to understand user intention. Recent advances have been developed for the BCI-based drone control system as the demand for drone control increases. Especially, drone swarm control based on brain signals could provide various industries such as military service or industry disaster. This paper presents a prototype of a brain swarm interface system for a variety of scenarios using a visual imagery paradigm. We designed the experimental environment that could acquire brain signals under a drone swarm control simulator environment. Through the system, we collected the electroencephalogram (EEG) signals with respect to four different scenarios. Seven subjects participated in our experiment and evaluated classification performances using the basic machine learning algorithm. The grand average classification accuracy is higher than the chance level accuracy. Hence, we could confirm the feasibility of the drone swarm control system based on EEG signals for performing high-level tasks.
Bertrand-DR: Improving Text-to-SQL using a Discriminative Re-ranker
Venue: arXiv cs.CL 2020
Year: 2020

To access data stored in relational databases, users need to understand the database schema and write a query using a query language such as SQL. To simplify this task, text-to-SQL models attempt to translate a user's natural language question to corresponding SQL query. Recently, several generative text-to-SQL models have been developed. We propose a novel discriminative re-ranker to improve the performance of generative text-to-SQL models by extracting the best SQL query from the beam output predicted by the text-to-SQL generator, resulting in improved performance in the cases where the best query was in the candidate list, but not at the top of the list. We build the re-ranker as a schema agnostic BERT fine-tuned classifier. We analyze relative strengths of the text-to-SQL and re-ranker models across different query hardness levels, and suggest how to combine the two models for optimal performance. We demonstrate the effectiveness of the re-ranker by applying it to two state-of-the-art text-to-SQL models, and achieve top 4 score on the Spider leaderboard at the time of writing this article.
Relay Selection, Scheduling and Power Control in Wireless Powered Cooperative Communication Networks
Venue: arXiv cs.NI 2020
Year: 2020

Relay nodes are used to improve the throughput, delay and reliability performance of energy harvesting networks by assisting both energy and information transfer between information nodes and access point. Previous studies on radio frequency energy harvesting networks are limited to single source single/multiple relay networks. In this paper, a novel joint relay selection, scheduling and power control problem for multiple source multiple relay network is formulated with the objective of minimizing the total duration of wireless power and information transfer. The formulated problem is non-convex mixed-integer non-linear programming problem, and proven to be NP-hard. We first formulate a sub-problem on scheduling and power control for a given relay selection. We propose an efficient optimal algorithm based on a bi-level optimization over power transfer time allocation. Then, for optimal relay selection, we present optimal exponential-time Branch-and-Bound (BB) based algorithm where the nodes are pruned with problem specific lower and upper bounds. We also provide two BB-based heuristic approaches limiting the number of branches generated from a BB-node, and a relay criterion based lower complexity heuristic algorithm. The performance of the proposed algorithms are demonstrated to outperform conventional harvest-then-cooperate approaches with up to $88\%$ lower schedule length for various network settings.
Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
Venue: arXiv cs.CC 2020
Year: 2020

We consider the following string matching problem on a node-labeled graph $G=(V,E)$: given a pattern string $P$, decide whether there exists a path in $G$ whose concatenation of node labels equals $P$. This is a basic primitive in various problems in bioinformatics, graph databases, or networks. The hardness results of Backurs and Indyk (FOCS 2016) imply that this problem cannot be solved in better than $O(|E||P|)$ time, under the Orthogonal Vectors Hypothesis (OVH), and this holds even under various restrictions on the graph (Equi et al., ICALP 2019). In this paper we consider its offline version, namely the one in which we are allowed to index the graph in order to support time-efficient string matching queries. Indeed, it was tantalizing in the string matching community to believe that sub-quadratic time queries can be achieved, e.g. at the cost of a high-degree polynomial-time indexing. We disprove this belief, showing that, under OVH, no polynomial-time index can support querying $P$ in time $O(|E|^δ|P|^β)$, with either $δ< 1$ or $β< 1$. We prove this tight bound employing a known self-reducibility technique, e.g. from the field of dynamic algorithms, which translates conditional lower bounds for an online problem to its offline version. As a side-contribution, we formalize this technique with the notion of linear independent-components reduction, allowing for a simple proof of our result. As another illustration of our technique, we also translate the quadratic conditional lower bound of Backurs and Indyk (STOC 2015) for the problem of matching a query string inside a text, under edit distance. We obtain an analogous tight quadratic lower bound for its offline version, improving the recent result of Cohen-Addad, Feuilloley and Starikovskaya (SODA 2019), but with a slightly different boundary condition.
Linear predictor on linearly-generated data with missing values: non consistency and solutions
Venue: arXiv cs.LG 2020
Year: 2020

We consider building predictors when the data have missing values. We study the seemingly-simple case where the target to predict is a linear function of the fully-observed data and we show that, in the presence of missing values, the optimal predictor may not be linear. In the particular Gaussian case, it can be written as a linear function of multiway interactions between the observed data and the various missing-value indicators. Due to its intrinsic complexity, we study a simple approximation and prove generalization bounds with finite samples, highlighting regimes for which each method performs best. We then show that multilayer perceptrons with ReLU activation functions can be consistent, and can explore good trade-offs between the true model and approximations. Our study highlights the interesting family of models that are beneficial to fit with missing values depending on the amount of data available.
Agent-Based Proof Design via Lemma Flow Diagram
Venue: arXiv cs.LO 2020
Year: 2020

We discuss an agent-based approach to proof design and implementation, which we call {\it Lemma Flow Diagram} (LFD). This approach is based on the multicut rule with $shared$ cuts. This approach is modular and easy to use, read and automate. Thus, we consider LFD an appealing alternative to `flow proof' which is popular in mathematical education. Some examples are provided.
Algorithmic Complexity of Secure Connected Domination in Graphs
Venue: arXiv cs.DM 2020
Year: 2020

Let $G = (V,E)$ be a simple, undirected and connected graph. A connected (total) dominating set $S \subseteq V$ is a secure connected (total) dominating set of $G$, if for each $ u \in V \setminus S$, there exists $v \in S$ such that $uv \in E$ and $(S \setminus \lbrace v \rbrace) \cup \lbrace u \rbrace $ is a connected (total) dominating set of $G$. The minimum cardinality of a secure connected (total) dominating set of $G$ denoted by $ γ_{sc} (G) (γ_{st}(G))$, is called the secure connected (total) domination number of $G$. In this paper, we show that the decision problems corresponding to secure connected domination number and secure total domination number are NP-complete even when restricted to split graphs or bipartite graphs. The NP-complete reductions also show that these problems are w[2]-hard. We also prove that the secure connected domination problem is linear time solvable in block graphs and threshold graphs.
Evolutionary algorithms for constructing an ensemble of decision trees
Venue: arXiv cs.NE 2020
Year: 2020

Most decision tree induction algorithms are based on a greedy top-down recursive partitioning strategy for tree growth. In this paper, we propose several methods for induction of decision trees and their ensembles based on evolutionary algorithms. The main difference of our approach is using real-valued vector representation of decision tree that allows to use a large number of different optimization algorithms, as well as optimize the whole tree or ensemble for avoiding local optima. Differential evolution and evolution strategies were chosen as optimization algorithms, as they have good results in reinforcement learning problems. We test the predictive performance of this methods using several public UCI data sets, and the proposed methods show better quality than classical methods.
Reducing Noise from Competing Neighbours: Word Retrieval with Lateral Inhibition in Multilink
Venue: arXiv cs.CL 2020
Year: 2020

Multilink is a computational model for word retrieval in monolingual and multilingual individuals under different task circumstances (Dijkstra et al., 2018). In the present study, we added lateral inhibition to Multilink's lexical network. Parameters were fit on the basis of reaction times from the English, British, and Dutch Lexicon Projects. We found a maximum correlation of 0.643 (N=1,205) on these data sets as a whole. Furthermore, the simulations themselves became faster as a result of adding lateral inhibition. We tested the fitted model to stimuli from a neighbourhood study (Mulder et al., 2018). Lateral inhibition was found to improve Multilink's correlations for this study, yielding an overall correlation of 0.67. Next, we explored the role of lateral inhibition as part of the model's task/decision system by running simulations on data from two studies concerning interlingual homographs (Vanlangendonck et al., in press; Goertz, 2018). We found that, while lateral inhibition plays a substantial part in the word selection process, this alone is not enough to result in a correct response selection. To solve this problem, we added a new task component to Multilink, especially designed to account for the translation process of interlingual homographs, cognates, and language-specific control words. The subsequent simulation results showed patterns remarkably similar to those in the Goertz study. The isomorphicity of the simulated data to the empirical data was further attested by an overall correlation of 0.538 (N=254) between reaction times and simulated model cycle times, as well as a condition pattern correlation of 0.853 (N=8). We conclude that Multilink yields an excellent fit to empirical data, particularly when a task-specific setting of the inhibition parameters is allowed.