OpenRaiser/Intern-Atlas huggingface dataset:
Data Structures & Algorithms for Exact Inference in Hierarchical Clustering
Venue: arXiv cs.DS 2020
Year: 2020

Hierarchical clustering is a fundamental task often used to discover meaningful structures in data, such as phylogenetic trees, taxonomies of concepts, subtypes of cancer, and cascades of particle decays in particle physics. Typically approximate algorithms are used for inference due to the combinatorial number of possible hierarchical clusterings. In contrast to existing methods, we present novel dynamic-programming algorithms for \emph{exact} inference in hierarchical clustering based on a novel trellis data structure, and we prove that we can exactly compute the partition function, maximum likelihood hierarchy, and marginal probabilities of sub-hierarchies and clusters. Our algorithms scale in time and space proportional to the powerset of $N$ elements which is super-exponentially more efficient than explicitly considering each of the (2N-3)!! possible hierarchies. Also, for larger datasets where our exact algorithms become infeasible, we introduce an approximate algorithm based on a sparse trellis that compares well to other benchmarks. Exact methods are relevant to data analyses in particle physics and for finding correlations among gene expression in cancer genomics, and we give examples in both areas, where our algorithms outperform greedy and beam search baselines. In addition, we consider Dasgupta's cost with synthetic data.
Graphcore C2 Card performance for image-based deep learning application: A Report
Venue: arXiv cs.CV 2020
Year: 2020

Recently, Graphcore has introduced an IPU Processor for accelerating machine learning applications. The architecture of the processor has been designed to achieve state of the art performance on current machine intelligence models for both training and inference. In this paper, we report on a benchmark in which we have evaluated the performance of IPU processors on deep neural networks for inference. We focus on deep vision models such as ResNeXt. We report the observed latency, throughput and energy efficiency.
Secure and Reliable Key Agreement with Physical Unclonable Functions
Venue: arXiv cs.CR 2020
Year: 2020

Different transforms used in binding a secret key to correlated physical-identifier outputs are compared. Decorrelation efficiency is the metric used to determine transforms that give highly-uncorrelated outputs. Scalar quantizers are applied to transform outputs to extract uniformly distributed bit sequences to which secret keys are bound. A set of transforms that perform well in terms of the decorrelation efficiency is applied to ring oscillator (RO) outputs to improve the uniqueness and reliability of extracted bit sequences, to reduce the hardware area and information leakage about the key and RO outputs, and to maximize the secret-key length. Low-complexity error-correction codes are proposed to illustrate two complete key-binding systems with perfect secrecy, and better secret-key and privacy-leakage rates than existing methods. A reference hardware implementation is also provided to demonstrate that the transform-coding approach occupies a small hardware area.
CLARA: Clinical Report Auto-completion
Venue: arXiv cs.LG 2020
Year: 2020

Generating clinical reports from raw recordings such as X-rays and electroencephalogram (EEG) is an essential and routine task for doctors. However, it is often time-consuming to write accurate and detailed reports. Most existing methods try to generate the whole reports from the raw input with limited success because 1) generated reports often contain errors that need manual review and correction, 2) it does not save time when doctors want to write additional information into the report, and 3) the generated reports are not customized based on individual doctors' preference. We propose {\it CL}inic{\it A}l {\it R}eport {\it A}uto-completion (CLARA), an interactive method that generates reports in a sentence by sentence fashion based on doctors' anchor words and partially completed sentences. CLARA searches for most relevant sentences from existing reports as the template for the current report. The retrieved sentences are sequentially modified by combining with the input feature representations to create the final report. In our experimental evaluation, CLARA achieved 0.393 CIDEr and 0.248 BLEU-4 on X-ray reports and 0.482 CIDEr and 0.491 BLEU-4 for EEG reports for sentence-level generation, which is up to 35% improvement over the best baseline. Also via our qualitative evaluation, CLARA is shown to produce reports which have a significantly higher level of approval by doctors in a user study (3.74 out of 5 for CLARA vs 2.52 out of 5 for the baseline).
Disentangling Adaptive Gradient Methods from Learning Rates
Venue: arXiv cs.LG 2020
Year: 2020

We investigate several confounding factors in the evaluation of optimization algorithms for deep learning. Primarily, we take a deeper look at how adaptive gradient methods interact with the learning rate schedule, a notoriously difficult-to-tune hyperparameter which has dramatic effects on the convergence and generalization of neural network training. We introduce a "grafting" experiment which decouples an update's magnitude from its direction, finding that many existing beliefs in the literature may have arisen from insufficient isolation of the implicit schedule of step sizes. Alongside this contribution, we present some empirical and theoretical retrospectives on the generalization of adaptive gradient methods, aimed at bringing more clarity to this space.
Massive MIMO Asymptotics for Ray-Based Propagation Channels
Venue: arXiv cs.IT 2020
Year: 2020

Favorable propagation (FP) and channel hardening (CH) are desired properties in massive multiple-input multiple-output (MIMO) systems. To date, these properties have primarily been analyzed for classical \textit{statistical} channel models, or \textit{ray-based} models with very specific angular parameters and distributions. This paper presents a thorough mathematical analysis of the asymptotic system behavior for ray-based channels with \textit{arbitrary} ray distributions, and considers \textit{two} types of antenna array structures at the cellular base station: a uniform linear array (ULA) and a uniform planar array (UPA). In addition to FP and channel hardening, we analyze the \textit{large system potential} (LSP) which measures the asymptotic ratio of the expected power in the desired channel to the expected total interference power when both the antenna and user numbers grow. LSP is said to hold when this ratio converges to a positive constant. The results demonstrate that while FP is guaranteed in ray-based channels, CH may or may not occur depending on the nature of the model. Furthermore, we demonstrate that LSP will not normally hold as the expected interference power grows logarithmically for both ULAs and UPAs relative to the power in the desired channel as the system size increases. Nevertheless, we identify some fundamental and attractive properties of massive MIMO in this limiting regime.
Tensor Decompositions in Deep Learning
Venue: arXiv cs.LG 2020
Year: 2020

The paper surveys the topic of tensor decompositions in modern machine learning applications. It focuses on three active research topics of significant relevance for the community. After a brief review of consolidated works on multi-way data analysis, we consider the use of tensor decompositions in compressing the parameter space of deep learning models. Lastly, we discuss how tensor methods can be leveraged to yield richer adaptive representations of complex data, including structured information. The paper concludes with a discussion on interesting open research challenges.
Full Duplex Hybrid A/D Beamforming with Reduced Complexity Multi-Tap Analog Cancellation
Venue: arXiv cs.IT 2020
Year: 2020

Although the hardware complexity of the analog self-interference canceller in full duplex Multiple Input Multiple Output (MIMO) designs does not necessarily scale with the number of transceiver antennas, exploiting the benefits of analog cancellation in massive MIMO systems with hundreds of antenna elements is still quite impractical. Hybrid Analog and Digital (A/D) beamforming architectures have been lately considered as a candidate technology for realizing massive MIMO transceivers with very large number of antenna elements, but with much fewer numbers of Radio Frequency (RF) chains. In this paper, we present a novel architecture for full duplex hybrid A/D beamforming transceivers including multi-tap analog cancellation with reduced number of taps and simple multiplexers for efficient signal routing among the transceiver RF chains. Capitalizing on the proposed transceiver architecture, we present a joint design of analog cancellation and A/D beamforming with the objective to maximize the achievable full duplex rate performance. Representative millimeter wave simulation results demonstrate the effectiveness of the proposed architecture and algorithmic framework for enabling simultaneous uplink and downlink communications with reduced complexity analog self-interference cancellation.
Analysis of diversity-accuracy tradeoff in image captioning
Venue: arXiv cs.CL 2020
Year: 2020

We investigate the effect of different model architectures, training objectives, hyperparameter settings and decoding procedures on the diversity of automatically generated image captions. Our results show that 1) simple decoding by naive sampling, coupled with low temperature is a competitive and fast method to produce diverse and accurate caption sets; 2) training with CIDEr-based reward using Reinforcement learning harms the diversity properties of the resulting generator, which cannot be mitigated by manipulating decoding parameters. In addition, we propose a new metric AllSPICE for evaluating both accuracy and diversity of a set of captions by a single value.
Simulation of Real-time Routing for UAS traffic Management with Communication and Airspace Safety Considerations
Venue: arXiv cs.MA 2020
Year: 2020

Small Unmanned Aircraft Systems (sUAS) will be an important component of the smart city and intelligent transportation environments of the near future. The demand for sUAS related applications, such as commercial delivery and land surveying, is expected to grow rapidly in next few years. In general, sUAS traffic routing and management functions are needed to coordinate the launching of sUAS from different launch sites and determine their trajectories to avoid conflict while considering several other constraints such as expected arrival time, minimum flight energy, and availability of communication resources. However, as the airborne sUAS density grows in a certain area, it is difficult to foresee the potential airspace and communications resource conflicts and make immediate decisions to avoid them. To address this challenge, we present a temporal and spatial routing algorithm and simulation platform for sUAS trajectory management in a high density urban area that plans sUAS movements in a spatial and temporal maze taking into account obstacles that are either static or dynamic in time. The routing allows the sUAS to avoid static no-fly areas (i.e. static obstacles) or other in-flight sUAS and areas that have congested communication resources (i.e. dynamic obstacles). The algorithm is evaluated using an agent-based simulation platform. The simulation results show that the proposed algorithm outperforms other route management algorithms in many areas, especially in processing speed and memory efficiency. Detailed comparisons are provided for the sUAS flight time, the overall throughput, conflict rate and communication resource utilization. The results demonstrate that our proposed algorithm can be used to address the airspace and communication resource utilization needs for a next generation smart city and smart transportation.
Stochastic Matching with Few Queries: $(1-\varepsilon)$ Approximation
Venue: arXiv cs.DS 2020
Year: 2020

Suppose that we are given an arbitrary graph $G=(V, E)$ and know that each edge in $E$ is going to be realized independently with some probability $p$. The goal in the stochastic matching problem is to pick a sparse subgraph $Q$ of $G$ such that the realized edges in $Q$, in expectation, include a matching that is approximately as large as the maximum matching among the realized edges of $G$. The maximum degree of $Q$ can depend on $p$, but not on the size of $G$. This problem has been subject to extensive studies over the years and the approximation factor has been improved from $0.5$ to $0.5001$ to $0.6568$ and eventually to $2/3$. In this work, we analyze a natural sampling-based algorithm and show that it can obtain all the way up to $(1-ε)$ approximation, for any constant $ε> 0$. A key and of possible independent interest component of our analysis is an algorithm that constructs a matching on a stochastic graph, which among some other important properties, guarantees that each vertex is matched independently from the vertices that are sufficiently far. This allows us to bypass a previously known barrier towards achieving $(1-ε)$ approximation based on existence of dense Ruzsa-Szemerédi graphs.
Using a thousand optimization tasks to learn hyperparameter search strategies
Venue: arXiv cs.LG 2020
Year: 2020

We present TaskSet, a dataset of tasks for use in training and evaluating optimizers. TaskSet is unique in its size and diversity, containing over a thousand tasks ranging from image classification with fully connected or convolutional neural networks, to variational autoencoders, to non-volume preserving flows on a variety of datasets. As an example application of such a dataset we explore meta-learning an ordered list of hyperparameters to try sequentially. By learning this hyperparameter list from data generated using TaskSet we achieve large speedups in sample efficiency over random search. Next we use the diversity of the TaskSet and our method for learning hyperparameter lists to empirically explore the generalization of these lists to new optimization tasks in a variety of settings including ImageNet classification with Resnet50 and LM1B language modeling with transformers. As part of this work we have opensourced code for all tasks, as well as ~29 million training curves for these problems and the corresponding hyperparameters.
A Purely-Reactive Manipulability-Maximising Motion Controller
Venue: arXiv cs.RO 2020
Year: 2020

We present a novel approach to controlling the instantaneous velocity of a robot end-effector that is able to simultaneously maximise manipulability and avoid joint limits. It operates on non-redundant and redundant robots, which is achieved by adding artificial redundancy in the form of controlled path deviation. We formulate the problem as a quadratic programme and provide an open-source Python implementation that provides solutions in just a few milliseconds. It accepts a robot model expressed using URDF or Denavit-Hartenberg parameterisation. We compare our method to previous work in simulation and on a physical robot.
Integrating Boundary Assembling into a DNN Framework for Named Entity Recognition in Chinese Social Media Text
Venue: arXiv cs.CL 2020
Year: 2020

Named entity recognition is a challenging task in Natural Language Processing, especially for informal and noisy social media text. Chinese word boundaries are also entity boundaries, therefore, named entity recognition for Chinese text can benefit from word boundary detection, outputted by Chinese word segmentation. Yet Chinese word segmentation poses its own difficulty because it is influenced by several factors, e.g., segmentation criteria, employed algorithm, etc. Dealt improperly, it may generate a cascading failure to the quality of named entity recognition followed. In this paper we integrate a boundary assembling method with the state-of-the-art deep neural network model, and incorporate the updated word boundary information into a conditional random field model for named entity recognition. Our method shows a 2% absolute improvement over previous state-of-the-art results.
How Much Can A Retailer Sell? Sales Forecasting on Tmall
Venue: arXiv cs.LG 2020
Year: 2020

Time-series forecasting is an important task in both academic and industry, which can be applied to solve many real forecasting problems like stock, water-supply, and sales predictions. In this paper, we study the case of retailers' sales forecasting on Tmall|the world's leading online B2C platform. By analyzing the data, we have two main observations, i.e., sales seasonality after we group different groups of retails and a Tweedie distribution after we transform the sales (target to forecast). Based on our observations, we design two mechanisms for sales forecasting, i.e., seasonality extraction and distribution transformation. First, we adopt Fourier decomposition to automatically extract the seasonalities for different categories of retailers, which can further be used as additional features for any established regression algorithms. Second, we propose to optimize the Tweedie loss of sales after logarithmic transformations. We apply these two mechanisms to classic regression models, i.e., neural network and Gradient Boosting Decision Tree, and the experimental results on Tmall dataset show that both mechanisms can significantly improve the forecasting results.
Energy Resolved Neutron Imaging for Strain Reconstruction using the Finite Element Method
Venue: arXiv cs.CE 2020
Year: 2020

A pulsed neutron imaging technique is used to reconstruct the residual strain within a polycrystalline material from Bragg edge strain images. This technique offers the possibility of a nondestructive analysis of strain fields with a high spatial resolution. A finite element approach is used to reconstruct the strain using the least square method constrained by the conditions of equilibrium. The procedure is developed and verified by validating for a cantilevered beam problem. It is subsequently demonstrated by reconstructing the strain from experimental data for a ring-and-plug sample, measured at the spallation neutron source RADEN at J-PARC in Japan. The reconstruction is validated by comparison with conventional constant wavelength strain measurements on the KOWARI diffractometer at ANSTO in Australia. It is also shown that the addition of a simple Tikhonov regularization can improve the reconstruction.
Vortex: OpenCL Compatible RISC-V GPGPU
Venue: arXiv cs.DC 2020
Year: 2020

The current challenges in technology scaling are pushing the semiconductor industry towards hardware specialization, creating a proliferation of heterogeneous systems-on-chip, delivering orders of magnitude performance and power benefits compared to traditional general-purpose architectures. This transition is getting a significant boost with the advent of RISC-V with its unique modular and extensible ISA, allowing a wide range of low-cost processor designs for various target applications. In addition, OpenCL is currently the most widely adopted programming framework for heterogeneous platforms available on mainstream CPUs, GPUs, as well as FPGAs and custom DSP. In this work, we present Vortex, a RISC-V General-Purpose GPU that supports OpenCL. Vortex implements a SIMT architecture with a minimal ISA extension to RISC-V that enables the execution of OpenCL programs. We also extended OpenCL runtime framework to use the new ISA. We evaluate this design using 15nm technology. We also show the performance and energy numbers of running them with a subset of benchmarks from the Rodinia Benchmark suite.
Cautious Reinforcement Learning with Logical Constraints
Venue: arXiv cs.LG 2020
Year: 2020

This paper presents the concept of an adaptive safe padding that forces Reinforcement Learning (RL) to synthesise optimal control policies while ensuring safety during the learning process. Policies are synthesised to satisfy a goal, expressed as a temporal logic formula, with maximal probability. Enforcing the RL agent to stay safe during learning might limit the exploration, however we show that the proposed architecture is able to automatically handle the trade-off between efficient progress in exploration (towards goal satisfaction) and ensuring safety. Theoretical guarantees are available on the optimality of the synthesised policies and on the convergence of the learning algorithm. Experimental results are provided to showcase the performance of the proposed method.
A Comprehensive Approach to Unsupervised Embedding Learning based on AND Algorithm
Venue: arXiv cs.LG 2020
Year: 2020

Unsupervised embedding learning aims to extract good representation from data without the need for any manual labels, which has been a critical challenge in many supervised learning tasks. This paper proposes a new unsupervised embedding approach, called Super-AND, which extends the current state-of-the-art model. Super-AND has its unique set of losses that can gather similar samples nearby within a low-density space while keeping invariant features intact against data augmentation. Super-AND outperforms all existing approaches and achieves an accuracy of 89.2% on the image classification task for CIFAR-10. We discuss the practical implications of this method in assisting semi-supervised tasks.
Random-Order Models
Venue: arXiv cs.DS 2020
Year: 2020

This chapter introduces the \emph{random-order model} in online algorithms. In this model, the input is chosen by an adversary, then randomly permuted before being presented to the algorithm. This reshuffling often weakens the power of the adversary and allows for improved algorithmic guarantees. We show such improvements for two broad classes of problems: packing problems where we must pick a constrained set of items to maximize total value, and covering problems where we must satisfy given requirements at minimum total cost. We also discuss how random-order model relates to other stochastic models used for non-worst-case competitive analysis.
Infinitely Wide Graph Convolutional Networks: Semi-supervised Learning via Gaussian Processes
Venue: arXiv cs.LG 2020
Year: 2020

Graph convolutional neural networks~(GCNs) have recently demonstrated promising results on graph-based semi-supervised classification, but little work has been done to explore their theoretical properties. Recently, several deep neural networks, e.g., fully connected and convolutional neural networks, with infinite hidden units have been proved to be equivalent to Gaussian processes~(GPs). To exploit both the powerful representational capacity of GCNs and the great expressive power of GPs, we investigate similar properties of infinitely wide GCNs. More specifically, we propose a GP regression model via GCNs~(GPGC) for graph-based semi-supervised learning. In the process, we formulate the kernel matrix computation of GPGC in an iterative analytical form. Finally, we derive a conditional distribution for the labels of unobserved nodes based on the graph structure, labels for the observed nodes, and the feature matrix of all the nodes. We conduct extensive experiments to evaluate the semi-supervised classification performance of GPGC and demonstrate that it outperforms other state-of-the-art methods by a clear margin on all the datasets while being efficient.