OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Voting in Beep Model
Venue: arXiv cs.DC 2020
Year: 2020

We consider the problem of distributed multi-choice voting in a setting that each node can communicate with its neighbors merely by sending beep signals. Given its simplicity, the beep communication model is of practical importance in different applications such as system biology and wireless sensor networks. Yet, the distributed majority voting has not been resolved in this setting. In this paper, we propose two algorithms, named Distributed Voting with Beeps, to resolve this problem. In the first proposed algorithm, the adjacent nodes having the same value form a set called spot. Afterwards, the spots with majority value try to corrode the spots with non-majority values. The second proposed algorithm is based on pairwise interactions between nodes. The proposed algorithms have a termination detection procedure to check whether voting is achieved. We establish theoretical guarantees for the convergence of these algorithms. In particular, we show that the success probability of the first algorithm tends to one as the percentage of the initial votes in majority increases. For the second algorithm, we show that it returns the correct output with high probability. Our experiments show that the algorithms are fairly invariant to the network topology, initial distribution of values, and network size.
Unshuffling fields in data formats
Venue: arXiv cs.IT 2020
Year: 2020

Data format reverse engineering commonly involves identifying conserved format motifs. However, this process typically requires establishing a common ordering for format elements across instances, particularly for formats using type-(length)-value tuples or "chunk" encoding. It is useful to \emph{unshuffle} chunks with common length statistics as a precursor to identifying conserved internal structures. We formalize the unshuffling problem and subsequently derive probabilistic bounds and outline corresponding algorithms for it. We empirically demonstrate unshuffling and highlight connections with the related class of synchronization problems.
RNN based Incremental Online Spoken Language Understanding
Venue: arXiv cs.CL 2020
Year: 2020

Spoken Language Understanding (SLU) typically comprises of an automatic speech recognition (ASR) followed by a natural language understanding (NLU) module. The two modules process signals in a blocking sequential fashion, i.e., the NLU often has to wait for the ASR to finish processing on an utterance basis, potentially leading to high latencies that render the spoken interaction less natural. In this paper, we propose recurrent neural network (RNN) based incremental processing towards the SLU task of intent detection. The proposed methodology offers lower latencies than a typical SLU system, without any significant reduction in system accuracy. We introduce and analyze different recurrent neural network architectures for incremental and online processing of the ASR transcripts and compare it to the existing offline systems. A lexical End-of-Sentence (EOS) detector is proposed for segmenting the stream of transcript into sentences for intent classification. Intent detection experiments are conducted on benchmark ATIS, Snips and Facebook's multilingual task oriented dialog datasets modified to emulate a continuous incremental stream of words with no utterance demarcation. We also analyze the prospects of early intent detection, before EOS, with our proposed system.
Class-imbalanced Domain Adaptation: An Empirical Odyssey
Venue: arXiv cs.LG 2020
Year: 2020

Unsupervised domain adaptation is a promising way to generalize deep models to novel domains. However, the current literature assumes that the label distribution is domain-invariant and only aligns the feature distributions or vice versa. In this work, we explore the more realistic task of Class-imbalanced Domain Adaptation: How to align feature distributions across domains while the label distributions of the two domains are also different? Taking a practical step towards this problem, we constructed the first benchmark with 22 cross-domain tasks from 6real-image datasets. We conducted comprehensive experiments on 10 recent domain adaptation methods and find most of them are very fragile in the face of coexisting feature and label distribution shift. Towards a better solution, we further proposed a feature and label distribution CO-ALignment (COAL) model with a novel combination of existing ideas. COAL is empirically shown to outperform the most recent domain adaptation methods on our benchmarks. We believe the provided benchmarks, empirical analysis results, and the COAL baseline could stimulate and facilitate future research towards this important problem.
End-to-End Multi-Task Denoising for the Joint Optimization of Perceptual Speech Metrics
Venue: arXiv cs.SD 2020
Year: 2020

Although supervised learning based on a deep neural network has recently achieved substantial improvement on speech enhancement, the existing schemes have either of two critical issues: spectrum or metric mismatches. The spectrum mismatch is a well known issue that any spectrum modification after short-time Fourier transform (STFT), in general, cannot be fully recovered after inverse short-time Fourier transform (ISTFT). The metric mismatch is that a conventional mean square error (MSE) loss function is typically sub-optimal to maximize perceptual speech measure such as signal-to-distortion ratio (SDR), perceptual evaluation of speech quality (PESQ) and short-time objective intelligibility (STOI). This paper presents a new end-to-end denoising framework. First, the network optimization is performed on the time-domain signals after ISTFT to avoid the spectrum mismatch. Second, three loss functions based on SDR, PESQ and STOI are proposed to minimize the metric mismatch. The experimental result showed the proposed denoising scheme significantly improved SDR, PESQ and STOI performance over the existing methods. Moreover, the proposed scheme also provided good generalization performance over generative denoising models on the perceptual speech metrics not used as a loss function during training.
On the Fundamental Recovery Limit of Orthogonal Least Squares
Venue: arXiv cs.IT 2020
Year: 2020

Orthogonal least squares (OLS) is a classic algorithm for sparse recovery, function approximation, and subset selection. In this paper, we analyze the performance guarantee of the OLS algorithm. Specifically, we show that OLS guarantees the exact reconstruction of any $K$-sparse vector in $K$ iterations, provided that a sensing matrix has unit $\ell_{2}$-norm columns and satisfies the restricted isometry property (RIP) of order $K+1$ with \begin{align*} δ_{K+1} &<C_{K} = \begin{cases} \frac{1}{\sqrt{K}}, & K=1, \\ \frac{1}{\sqrt{K+\frac{1}{4}}}, & K=2, \\ \frac{1}{\sqrt{K+\frac{1}{16}}}, & K=3, \\ \frac{1}{\sqrt{K}}, & K \ge 4. \end{cases} \end{align*} Furthermore, we show that the proposed guarantee is optimal in the sense that if $δ_{K+1} \ge C_{K}$, then there exists a counterexample for which OLS fails the recovery.
A Polymorphic RPC Calculus
Venue: arXiv cs.PL 2020
Year: 2020

The RPC calculus is a simple semantic foundation for multi-tier programming languages such as Links in which located functions can be written for the client-server model. Subsequently, the typed RPC calculus is designed to capture the location information of functions by types and to drive location type-directed slicing compilations. However, the use of locations is currently limited to monomorphic ones, which is one of the gaps to overcome to put into practice the theory of RPC calculi for client-server model. This paper proposes a polymorphic RPC calculus to allow programmers to write succinct multi-tier programs using polymorphic location constructs. Then the polymorphic multi-tier programs can be automatically translated into programs only containing location constants amenable to the existing slicing compilation methods. We formulate a type system for the polymorphic RPC calculus, and prove its type soundness. Also, we design a monomorphization translation together with proofs on its type and semantic correctness for the translation.
Vatex Video Captioning Challenge 2020: Multi-View Features and Hybrid Reward Strategies for Video Captioning
Venue: arXiv cs.CV 2020
Year: 2020

This report describes our solution for the VATEX Captioning Challenge 2020, which requires generating descriptions for the videos in both English and Chinese languages. We identified three crucial factors that improve the performance, namely: multi-view features, hybrid reward, and diverse ensemble. Based on our method of VATEX 2019 challenge, we achieved significant improvements this year with more advanced model architectures, combination of appearance and motion features, and careful hyper-parameters tuning. Our method achieves very competitive results on both of the Chinese and English video captioning tracks.
RoboNet: Large-Scale Multi-Robot Learning
Venue: arXiv cs.RO 2020
Year: 2020

Robot learning has emerged as a promising tool for taming the complexity and diversity of the real world. Methods based on high-capacity models, such as deep networks, hold the promise of providing effective generalization to a wide range of open-world environments. However, these same methods typically require large amounts of diverse training data to generalize effectively. In contrast, most robotic learning experiments are small-scale, single-domain, and single-robot. This leads to a frequent tension in robotic learning: how can we learn generalizable robotic controllers without having to collect impractically large amounts of data for each separate experiment? In this paper, we propose RoboNet, an open database for sharing robotic experience, which provides an initial pool of 15 million video frames, from 7 different robot platforms, and study how it can be used to learn generalizable models for vision-based robotic manipulation. We combine the dataset with two different learning algorithms: visual foresight, which uses forward video prediction models, and supervised inverse models. Our experiments test the learned algorithms' ability to work across new objects, new tasks, new scenes, new camera viewpoints, new grippers, or even entirely new robots. In our final experiment, we find that by pre-training on RoboNet and fine-tuning on data from a held-out Franka or Kuka robot, we can exceed the performance of a robot-specific training approach that uses 4x-20x more data. For videos and data, see the project webpage: https://www.robonet.wiki/
Delving into VoxCeleb: environment invariant speaker recognition
Venue: arXiv cs.SD 2020
Year: 2020

Research in speaker recognition has recently seen significant progress due to the application of neural network models and the availability of new large-scale datasets. There has been a plethora of work in search for more powerful architectures or loss functions suitable for the task, but these works do not consider what information is learnt by the models, apart from being able to predict the given labels. In this work, we introduce an environment adversarial training framework in which the network can effectively learn speaker-discriminative and environment-invariant embeddings without explicit domain shift during training. We achieve this by utilising the previously unused `video' information in the VoxCeleb dataset. The environment adversarial training allows the network to generalise better to unseen conditions. The method is evaluated on both speaker identification and verification tasks using the VoxCeleb dataset, on which we demonstrate significant performance improvements over baselines.
Towards Fine-Grained Prosody Control for Voice Conversion
Venue: arXiv cs.SD 2020
Year: 2020

In a typical voice conversion system, prior works utilize various acoustic features (e.g., the pitch, voiced/unvoiced flag, aperiodicity) of the source speech to control the prosody of generated waveform. However, the prosody is related with many factors, such as the intonation, stress and rhythm. It is a challenging task to perfectly describe the prosody through acoustic features. To deal with this problem, we propose prosody embeddings to model prosody. These embeddings are learned from the source speech in an unsupervised manner. We conduct experiments on our Mandarin corpus recoded by professional speakers. Experimental results demonstrate that the proposed method enables fine-grained control of the prosody. In challenging situations (such as the source speech is a singing song), our proposed method can also achieve promising results.
Detecting Fake News with Weak Social Supervision
Venue: arXiv cs.SI 2020
Year: 2020

Limited labeled data is becoming the largest bottleneck for supervised learning systems. This is especially the case for many real-world tasks where large scale annotated examples are either too expensive to acquire or unavailable due to privacy or data access constraints. Weak supervision has shown to be a good means to mitigate the scarcity of annotated data by leveraging weak labels or injecting constraints from heuristic rules and/or external knowledge sources. Social media has little labeled data but possesses unique characteristics that make it suitable for generating weak supervision, resulting in a new type of weak supervision, i.e., weak social supervision. In this article, we illustrate how various aspects of social media can be used to generate weak social supervision. Specifically, we use the recent research on fake news detection as the use case, where social engagements are abundant but annotated examples are scarce, to show that weak social supervision is effective when facing the little labeled data problem. This article opens the door for learning with weak social supervision for other emerging tasks.
Phase Retrieval of Low-Rank Matrices by Anchored Regression
Venue: arXiv cs.IT 2020
Year: 2020

We study the low-rank phase retrieval problem, where we try to recover a $d_1\times d_2$ low-rank matrix from a series of phaseless linear measurements. This is a fourth-order inverse problem, as we are trying to recover factors of matrix that have been put through a quadratic nonlinearity after being multiplied together. We propose a solution to this problem using the recently introduced technique of anchored regression. This approach uses two different types of convex relaxations: we replace the quadratic equality constraints for the phaseless measurements by a search over a polytope, and enforce the rank constraint through nuclear norm regularization. The result is a convex program that works in the space of $d_1 \times d_2$ matrices. We analyze two specific scenarios. In the first, the target matrix is rank-$1$, and the observations are structured to correspond to a phaseless blind deconvolution. In the second, the target matrix has general rank, and we observe the magnitudes of the inner products against a series of independent Gaussian random matrices. In each of these problems, we show that the anchored regression returns an accurate estimate from a near-optimal number of measurements given that we have access to an anchor matrix of sufficient quality. We also show how to create such an anchor in the phaseless blind deconvolution problem, again from an optimal number of measurements, and present a partial result in this direction for the general rank problem.
The Scalability for Parallel Machine Learning Training Algorithm: Dataset Matters
Venue: arXiv cs.DC 2020
Year: 2020

To gain a better performance, many researchers put more computing resource into an application. However, in the AI area, there is still a lack of a successful large-scale machine learning training application: The scalability and performance reproducibility of parallel machine learning training algorithm are limited and there are a few pieces of research focusing on why these indexes are limited but there are very few research efforts explaining the reasons in essence. In this paper, we propose that the sample difference in dataset plays a more prominent role in parallel machine learning algorithm scalability. Dataset characters can measure sample difference. These characters include the variance of the sample in a dataset, sparsity, sample diversity and similarity in sampling sequence. To match our proposal, we choose four kinds of parallel machine learning training algorithms as our research objects: (1) Asynchronous parallel SGD algorithm (Hogwild! algorithm) (2) Parallel model average SGD algorithm (Mini-batch SGD algorithm) (3) Decenterilization optimization algorithm, (4) Dual Coordinate Optimization (DADM algorithm). These algorithms cover different types of machine learning optimization algorithms. We present the analysis of their convergence proof and design experiments. Our results show that the characters datasets decide the scalability of the machine learning algorithm. What is more, there is an upper bound of parallel scalability for machine learning algorithms.
Fast Structured Decoding for Sequence Models
Venue: arXiv cs.LG 2020
Year: 2020

Autoregressive sequence models achieve state-of-the-art performance in domains like machine translation. However, due to the autoregressive factorization nature, these models suffer from heavy latency during inference. Recently, non-autoregressive sequence models were proposed to reduce the inference time. However, these models assume that the decoding process of each token is conditionally independent of others. Such a generation process sometimes makes the output sentence inconsistent, and thus the learned non-autoregressive models could only achieve inferior accuracy compared to their autoregressive counterparts. To improve then decoding consistency and reduce the inference cost at the same time, we propose to incorporate a structured inference module into the non-autoregressive models. Specifically, we design an efficient approximation for Conditional Random Fields (CRF) for non-autoregressive sequence models, and further propose a dynamic transition technique to model positional contexts in the CRF. Experiments in machine translation show that while increasing little latency (8~14ms), our model could achieve significantly better translation performance than previous non-autoregressive models on different translation datasets. In particular, for the WMT14 En-De dataset, our model obtains a BLEU score of 26.80, which largely outperforms the previous non-autoregressive baselines and is only 0.61 lower in BLEU than purely autoregressive models.
Runners in action
Venue: arXiv cs.PL 2020
Year: 2020

Runners of algebraic effects, also known as comodels, provide a mathematical model of resource management. We show that they also give rise to a programming concept that models top-level external resources, as well as allows programmers to modularly define their own intermediate "virtual machines". We capture the core ideas of programming with runners in an equational calculus $λ_{\mathsf{coop}}$, which we equip with a sound and coherent denotational semantics that guarantees the linear use of resources and execution of finalisation code. We accompany $λ_{\mathsf{coop}}$ with examples of runners in action, provide a prototype language implementation in OCaml, as well as a Haskell library based on $λ_{\mathsf{coop}}$.
A Deterministic Linear Program Solver in Current Matrix Multiplication Time
Venue: arXiv cs.DS 2020
Year: 2020

Interior point algorithms for solving linear programs have been studied extensively for a long time [e.g. Karmarkar 1984; Lee, Sidford FOCS'14; Cohen, Lee, Song STOC'19]. For linear programs of the form $\min_{Ax=b, x \ge 0} c^\top x$ with $n$ variables and $d$ constraints, the generic case $d = Ω(n)$ has recently been settled by Cohen, Lee and Song [STOC'19]. Their algorithm can solve linear programs in $\tilde O(n^ω\log(n/δ))$ expected time, where $δ$ is the relative accuracy. This is essentially optimal as all known linear system solvers require up to $O(n^ω)$ time for solving $Ax = b$. However, for the case of deterministic solvers, the best upper bound is Vaidya's 30 years old $O(n^{2.5} \log(n/δ))$ bound [FOCS'89]. In this paper we show that one can also settle the deterministic setting by derandomizing Cohen et al.'s $\tilde{O}(n^ω\log(n/δ))$ time algorithm. This allows for a strict $\tilde{O}(n^ω\log(n/δ))$ time bound, instead of an expected one, and a simplified analysis, reducing the length of their proof of their central path method by roughly half. Derandomizing this algorithm was also an open question asked in Song's PhD Thesis. The main tool to achieve our result is a new data-structure that can maintain the solution to a linear system in subquadratic time. More accurately we are able to maintain $\sqrt{U}A^\top(AUA^\top)^{-1}A\sqrt{U}\:v$ in subquadratic time under $\ell_2$ multiplicative changes to the diagonal matrix $U$ and the vector $v$. This type of change is common for interior point algorithms. Previous algorithms [e.g. Vaidya STOC'89; Lee, Sidford FOCS'15; Cohen, Lee, Song STOC'19] required $Ω(n^2)$ time for this task. [...]
CONNA: Addressing Name Disambiguation on The Fly
Venue: arXiv cs.SI 2020
Year: 2020

Name disambiguation is a key and also a very tough problem in many online systems such as social search and academic search. Despite considerable research, a critical issue that has not been systematically studied is disambiguation on the fly -- to complete the disambiguation in the real-time. This is very challenging, as the disambiguation algorithm must be accurate, efficient, and error tolerance. In this paper, we propose a novel framework -- CONNA -- to train a matching component and a decision component jointly via reinforcement learning. The matching component is responsible for finding the top matched candidate for the given paper, and the decision component is responsible for deciding on assigning the top matched person or creating a new person. The two components are intertwined and can be bootstrapped via jointly training. Empirically, we evaluate CONNA on two name disambiguation datasets. Experimental results show that the proposed framework can achieve a 1.21%-19.84% improvement on F1-score using joint training of the matching and the decision components. The proposed CONNA has been successfully deployed on AMiner -- a large online academic search system.
CTNN: Corticothalamic-inspired neural network
Venue: arXiv cs.NE 2020
Year: 2020

Sensory predictions by the brain in all modalities take place as a result of bottom-up and top-down connections both in the neocortex and between the neocortex and the thalamus. The bottom-up connections in the cortex are responsible for learning, pattern recognition, and object classification, and have been widely modelled using artificial neural networks (ANNs). Here, we present a neural network architecture modelled on the top-down corticothalamic connections and the behaviour of the thalamus: a corticothalamic neural network (CTNN), consisting of an auto-encoder connected to a difference engine with a threshold. We demonstrate that the CTNN is input agnostic, multi-modal, robust during partial occlusion of one or more sensory inputs, and has significantly higher processing efficiency than other predictive coding models, proportional to the number of sequentially similar inputs in a sequence. This increased efficiency could be highly significant in more complex implementations of this architecture, where the predictive nature of the cortex will allow most of the incoming data to be discarded.