OpenRaiser/Intern-Atlas huggingface dataset:
Less is More: Data-Efficient Complex Question Answering over Knowledge Bases
Venue: arXiv cs.CL 2020
Year: 2020

Question answering is an effective method for obtaining information from knowledge bases (KB). In this paper, we propose the Neural-Symbolic Complex Question Answering (NS-CQA) model, a data-efficient reinforcement learning framework for complex question answering by using only a modest number of training samples. Our framework consists of a neural generator and a symbolic executor that, respectively, transforms a natural-language question into a sequence of primitive actions, and executes them over the knowledge base to compute the answer. We carefully formulate a set of primitive symbolic actions that allows us to not only simplify our neural network design but also accelerate model convergence. To reduce search space, we employ the copy and masking mechanisms in our encoder-decoder architecture to drastically reduce the decoder output vocabulary and improve model generalizability. We equip our model with a memory buffer that stores high-reward promising programs. Besides, we propose an adaptive reward function. By comparing the generated trial with the trials stored in the memory buffer, we derive the curriculum-guided reward bonus, i.e., the proximity and the novelty. To mitigate the sparse reward problem, we combine the adaptive reward and the reward bonus, reshaping the sparse reward into dense feedback. Also, we encourage the model to generate new trials to avoid imitating the spurious trials while making the model remember the past high-reward trials to improve data efficiency. Our NS-CQA model is evaluated on two datasets: CQA, a recent large-scale complex question answering dataset, and WebQuestionsSP, a multi-hop question answering dataset. On both datasets, our model outperforms the state-of-the-art models. Notably, on CQA, NS-CQA performs well on questions with higher complexity, while only using approximately 1% of the total training samples.
Learning as Abduction: Trainable Natural Logic Theorem Prover for Natural Language Inference
Venue: arXiv cs.CL 2020
Year: 2020

Tackling Natural Language Inference with a logic-based method is becoming less and less common. While this might have been counterintuitive several decades ago, nowadays it seems pretty obvious. The main reasons for such a conception are that (a) logic-based methods are usually brittle when it comes to processing wide-coverage texts, and (b) instead of automatically learning from data, they require much of manual effort for development. We make a step towards to overcome such shortcomings by modeling learning from data as abduction: reversing a theorem-proving procedure to abduce semantic relations that serve as the best explanation for the gold label of an inference problem. In other words, instead of proving sentence-level inference relations with the help of lexical relations, the lexical relations are proved taking into account the sentence-level inference relations. We implement the learning method in a tableau theorem prover for natural language and show that it improves the performance of the theorem prover on the SICK dataset by 1.4% while still maintaining high precision (>94%). The obtained results are competitive with the state of the art among logic-based systems.
FPGA Implementation of Stair Matrix based Massive MIMO Detection
Venue: arXiv cs.IT 2020
Year: 2020

Approximate matrix inversion based methods is widely used for linear massive multiple-input multiple-output (MIMO) received symbol vector detection. Such detectors typically utilize the diagonally dominant channel matrix of a massive MIMO system. Instead of diagonal matrix, a stair matrix can be utilized to improve the error-rate performance of a massive MIMO detector. In this paper, we present very large-scale integration (VLSI) architecture and field programmable gate array (FPGA) implementation of a stair matrix based iterative detection algorithm. The architecture supports a base station with 128 antennas, 8 users with single antenna, and 256 quadrature amplitude modulation (QAM). The stair matrix based detector can deliver a 142.34 Mbps data rate and reach a clock frequency of 258 MHz in a Xilinx Virtex-7 FPGA. The detector provides superior error-rate performance and higher scaled throughput than most contemporary massive MIMO detectors.
String Constraints with Concatenation and Transducers Solved Efficiently (Technical Report)
Venue: arXiv cs.LO 2020
Year: 2020

String analysis is the problem of reasoning about how strings are manipulated by a program. It has numerous applications including automatic detection of cross-site scripting (XSS). A popular string analysis technique includes symbolic executions, which at their core use string (constraint) solvers. Such solvers typically reason about constraints expressed in theories over strings with the concatenation operator as an atomic constraint. In recent years, researchers started to recognise the importance of incorporating the replace-all operator and finite transductions in the theories of strings with concatenation. Such string operations are typically crucial for reasoning about XSS vulnerabilities in web applications, especially for modelling sanitisation functions and implicit browser transductions (e.g. innerHTML). In this paper, we provide the first string solver that can reason about constraints involving both concatenation and finite transductions. Moreover, it has a completeness and termination guarantee for several important fragments (e.g. straight-line fragment). The main challenge addressed in the paper is the prohibitive worst-case complexity of the theory. To this end, we propose a method that exploits succinct alternating finite automata as concise symbolic representations of string constraints. Alternation offers not only exponential savings in space when representing Boolean combinations of transducers, but also a possibility of succinct representation of otherwise costly combinations of transducers and concatenation. Reasoning about the emptiness of the AFA language requires a state-space exploration in an exponential-sized graph, for which we use model checking algorithms (e.g. IC3). We have implemented our algorithm and demonstrated its efficacy on benchmarks that are derived from XSS and other examples in the literature.
Teaching Interactive Proofs to Mathematicians
Venue: arXiv cs.LO 2020
Year: 2020

This work discusses an approach to teach to mathematicians the importance and effectiveness of the application of Interactive Theorem Proving tools in their specific fields of interest. The approach aims to motivate the use of such tools through short courses. In particular, it is discussed how, using as case-of-study algebraic notions and properties, the use of the proof assistant Prototype Verification System PVS is promoted to interest mathematicians in the development of their mechanized proofs.
State sharding model on the blockchain
Venue: arXiv cs.CR 2020
Year: 2020

Blockchain is an incrementally updated ledger maintained by distributed nodes rather than centralized organizations. The current blockchain technology faces scalability issues, which include two aspects: low transaction throughput and high storage capacity costs. This paper studies the blockchain structure based on state sharding technology, and mainly solves the problem of non-scalability of block chain storage. This paper designs and implements the blockchain state sharding scheme, proposes a specific state sharding data structure and algorithm implementation, and realizes a complete blockchain structure so that the blockchain has the advantages of high throughput, processing a large number of transactions and saving storage costs. Experimental results show that a blockchain network with more than 100,000 nodes can be divided into 1024 shards. A blockchain network with this structure can process 500,000 transactions in about 5 seconds. If the consensus time of the blockchain is about 10 seconds, and the block generation time of the blockchain system of the sharding mechanism is 15 seconds, the transaction throughput can reach 33,000 tx/sec. Experimental results show that the throughput of the proposed protocol increases with the increase of the network node size. This confirms the scalability of the blockchain structure based on sharding technology.
LIFI: Towards Linguistically Informed Frame Interpolation
Venue: arXiv cs.CV 2020
Year: 2020

In this work, we explore a new problem of frame interpolation for speech videos. Such content today forms the major form of online communication. We try to solve this problem by using several deep learning video generation algorithms to generate the missing frames. We also provide examples where computer vision models despite showing high performance on conventional non-linguistic metrics fail to accurately produce faithful interpolation of speech. With this motivation, we provide a new set of linguistically-informed metrics specifically targeted to the problem of speech videos interpolation. We also release several datasets to test computer vision video generation models of their speech understanding.
Information-theoretic Feature Selection via Tensor Decomposition and Submodularity
Venue: arXiv cs.LG 2020
Year: 2020

Feature selection by maximizing high-order mutual information between the selected feature vector and a target variable is the gold standard in terms of selecting the best subset of relevant features that maximizes the performance of prediction models. However, such an approach typically requires knowledge of the multivariate probability distribution of all features and the target, and involves a challenging combinatorial optimization problem. Recent work has shown that any joint Probability Mass Function (PMF) can be represented as a naive Bayes model, via Canonical Polyadic (tensor rank) Decomposition. In this paper, we introduce a low-rank tensor model of the joint PMF of all variables and indirect targeting as a way of mitigating complexity and maximizing the classification performance for a given number of features. Through low-rank modeling of the joint PMF, it is possible to circumvent the curse of dimensionality by learning principal components of the joint distribution. By indirectly aiming to predict the latent variable of the naive Bayes model instead of the original target variable, it is possible to formulate the feature selection problem as maximization of a monotone submodular function subject to a cardinality constraint - which can be tackled using a greedy algorithm that comes with performance guarantees. Numerical experiments with several standard datasets suggest that the proposed approach compares favorably to the state-of-art for this important problem.
On Krohn-Rhodes theory for semiautomata
Venue: arXiv cs.FL 2020
Year: 2020

Krohn-Rhodes theory encompasses the techniques for the study of finite automata and their decomposition into elementary automata. The famous result of Krohn and Rhodes roughly states that each finite automaton can be decomposed into elementary components which correspond to permutation and reset automata connected by a cascade product. However, this outcome is not easy to access for the working computer scientist. This paper provides a short introduction into Krohn-Rhodes theory based on the valuable work of Ginzburg.
Accordion: Adaptive Gradient Communication via Critical Learning Regime Identification
Venue: arXiv cs.LG 2020
Year: 2020

Distributed model training suffers from communication bottlenecks due to frequent model updates transmitted across compute nodes. To alleviate these bottlenecks, practitioners use gradient compression techniques like sparsification, quantization, or low-rank updates. The techniques usually require choosing a static compression ratio, often requiring users to balance the trade-off between model accuracy and per-iteration speedup. In this work, we show that such performance degradation due to choosing a high compression ratio is not fundamental. An adaptive compression strategy can reduce communication while maintaining final test accuracy. Inspired by recent findings on critical learning regimes, in which small gradient errors can have irrecoverable impact on model performance, we propose Accordion a simple yet effective adaptive compression algorithm. While Accordion maintains a high enough compression rate on average, it avoids over-compressing gradients whenever in critical learning regimes, detected by a simple gradient-norm based criterion. Our extensive experimental study over a number of machine learning tasks in distributed environments indicates that Accordion, maintains similar model accuracy to uncompressed training, yet achieves up to 5.5x better compression and up to 4.1x end-to-end speedup over static approaches. We show that Accordion also works for adjusting the batch size, another popular strategy for alleviating communication bottlenecks.
Typable Fragments of Polynomial Automatic Amortized Resource Analysis
Venue: arXiv cs.PL 2020
Year: 2020

Being a fully automated technique for resource analysis, automatic amortized resource analysis (AARA) can fail in returning worst-case cost bounds of programs, fundamentally due to the undecidability of resource analysis. For programmers who are unfamiliar with the technical details of AARA, it is difficult to predict whether a program can be successfully analyzed in AARA. Motivated by this problem, this article identifies classes of programs that can be analyzed in type-based polynomial AARA. Firstly, it is shown that the set of functions that are typable in univariate polynomial AARA coincides with the complexity class PTIME. Secondly, the article presents a sufficient condition for typability that axiomatically requires every sub-expression of a given program to be polynomial-time. It is proved that this condition implies typability in multivariate polynomial AARA under some syntactic restrictions.
Distance problems within Helly graphs and $k$-Helly graphs
Venue: arXiv cs.DS 2020
Year: 2020

The ball hypergraph of a graph $G$ is the family of balls of all possible centers and radii in $G$. It has Helly number at most $k$ if every subfamily of $k$-wise intersecting balls has a nonempty common intersection. A graph is $k$-Helly (or Helly, if $k=2$) if its ball hypergraph has Helly number at most $k$. We prove that a central vertex and all the medians in an $n$-vertex $m$-edge Helly graph can be computed w.h.p. in $\tilde{\cal O}(m\sqrt{n})$ time. Both results extend to a broader setting where we define a non-negative cost function over the vertex-set. For any fixed $k$, we also present an $\tilde{\cal O}(m\sqrt{kn})$-time randomized algorithm for radius computation within $k$-Helly graphs. If we relax the definition of Helly number (for what is sometimes called an "almost Helly-type" property in the literature), then our approach leads to an approximation algorithm for computing the radius with an additive one-sided error of at most some constant.
Rate Splitting Multiple Access in C-RAN: A Scalable and Robust Design
Venue: arXiv cs.IT 2020
Year: 2020

Cloud radio access networks (C-RAN) enable a network platform for beyond the fifth generation of communication networks (B5G), which incorporates the advances in cloud computing technologies to modern radio access networks. Recently, rate splitting multiple access (RSMA), relying on multi-antenna rate-splitting (RS) at the transmitter and successive interference cancellation (SIC) at the receivers, has been shown to manage the interference in multi-antenna communication networks efficiently. This paper considers applying RSMA in C-RAN. We address the practical challenge of a transmitter that only knows the statistical channel state (CSI) information of the users. To this end, the paper investigates the problem of stochastic coordinated beamforming (SCB) optimization to maximize the ergodic sum-rate (ESR) in the network. Furthermore, we propose a scalable and robust RS scheme where the number of the common streams to be decoded at each user scales linearly with the number of users, and the common stream selection only depends on the statistical CSI. The setup leads to a challenging stochastic and non-convex optimization problem. A sample average approximation (SAA) and weighted minimum mean square error (WMMSE) based algorithm is adopted to tackle the intractable stochastic non-convex optimization and guarantee convergence to a stationary point asymptotically. The numerical simulations demonstrate the efficiency of the proposed RS strategy and show a gain up to 27\% in the achievable ESR compared with state-of-the-art schemes, namely treating interference as noise (TIN) and non-orthogonal multiple access (NOMA) schemes.
Representation Learning for Integrating Multi-domain Outcomes to Optimize Individualized Treatments
Venue: arXiv cs.LG 2020
Year: 2020

For mental disorders, patients' underlying mental states are non-observed latent constructs which have to be inferred from observed multi-domain measurements such as diagnostic symptoms and patient functioning scores. Additionally, substantial heterogeneity in the disease diagnosis between patients needs to be addressed for optimizing individualized treatment policy in order to achieve precision medicine. To address these challenges, we propose an integrated learning framework that can simultaneously learn patients' underlying mental states and recommend optimal treatments for each individual. This learning framework is based on the measurement theory in psychiatry for modeling multiple disease diagnostic measures as arising from the underlying causes (true mental states). It allows incorporation of the multivariate pre- and post-treatment outcomes as well as biological measures while preserving the invariant structure for representing patients' latent mental states. A multi-layer neural network is used to allow complex treatment effect heterogeneity. Optimal treatment policy can be inferred for future patients by comparing their potential mental states under different treatments given the observed multi-domain pre-treatment measurements. Experiments on simulated data and a real-world clinical trial data show that the learned treatment polices compare favorably to alternative methods on heterogeneous treatment effects, and have broad utilities which lead to better patient outcomes on multiple domains.
Multimodal and self-supervised representation learning for automatic gesture recognition in surgical robotics
Venue: arXiv cs.CV 2020
Year: 2020

Self-supervised, multi-modal learning has been successful in holistic representation of complex scenarios. This can be useful to consolidate information from multiple modalities which have multiple, versatile uses. Its application in surgical robotics can lead to simultaneously developing a generalised machine understanding of the surgical process and reduce the dependency on quality, expert annotations which are generally difficult to obtain. We develop a self-supervised, multi-modal representation learning paradigm that learns representations for surgical gestures from video and kinematics. We use an encoder-decoder network configuration that encodes representations from surgical videos and decodes them to yield kinematics. We quantitatively demonstrate the efficacy of our learnt representations for gesture recognition (with accuracy between 69.6 % and 77.8 %), transfer learning across multiple tasks (with accuracy between 44.6 % and 64.8 %) and surgeon skill classification (with accuracy between 76.8 % and 81.2 %). Further, we qualitatively demonstrate that our self-supervised representations cluster in semantically meaningful properties (surgeon skill and gestures).
Combining Domain-Specific Meta-Learners in the Parameter Space for Cross-Domain Few-Shot Classification
Venue: arXiv cs.LG 2020
Year: 2020

The goal of few-shot classification is to learn a model that can classify novel classes using only a few training examples. Despite the promising results shown by existing meta-learning algorithms in solving the few-shot classification problem, there still remains an important challenge: how to generalize to unseen domains while meta-learning on multiple seen domains? In this paper, we propose an optimization-based meta-learning method, called Combining Domain-Specific Meta-Learners (CosML), that addresses the cross-domain few-shot classification problem. CosML first trains a set of meta-learners, one for each training domain, to learn prior knowledge (i.e., meta-parameters) specific to each domain. The domain-specific meta-learners are then combined in the \emph{parameter space}, by taking a weighted average of their meta-parameters, which is used as the initialization parameters of a task network that is quickly adapted to novel few-shot classification tasks in an unseen domain. Our experiments show that CosML outperforms a range of state-of-the-art methods and achieves strong cross-domain generalization ability.
Self-supervised Representation Learning for Evolutionary Neural Architecture Search
Venue: arXiv cs.CV 2020
Year: 2020

Recently proposed neural architecture search (NAS) algorithms adopt neural predictors to accelerate the architecture search. The capability of neural predictors to accurately predict the performance metrics of neural architecture is critical to NAS, and the acquisition of training datasets for neural predictors is time-consuming. How to obtain a neural predictor with high prediction accuracy using a small amount of training data is a central problem to neural predictor-based NAS. Here, we firstly design a new architecture encoding scheme that overcomes the drawbacks of existing vector-based architecture encoding schemes to calculate the graph edit distance of neural architectures. To enhance the predictive performance of neural predictors, we devise two self-supervised learning methods from different perspectives to pre-train the architecture embedding part of neural predictors to generate a meaningful representation of neural architectures. The first one is to train a carefully designed two branch graph neural network model to predict the graph edit distance of two input neural architectures. The second method is inspired by the prevalently contrastive learning, and we present a new contrastive learning algorithm that utilizes a central feature vector as a proxy to contrast positive pairs against negative pairs. Experimental results illustrate that the pre-trained neural predictors can achieve comparable or superior performance compared with their supervised counterparts with several times less training samples. We achieve state-of-the-art performance on the NASBench-101 and NASBench201 benchmarks when integrating the pre-trained neural predictors with an evolutionary NAS algorithm.