OpenRaiser/Intern-Atlas huggingface dataset:
Macro action selection with deep reinforcement learning in StarCraft
Venue: arXiv cs.AI 2019
Year: 2019

StarCraft (SC) is one of the most popular and successful Real Time Strategy (RTS) games. In recent years, SC is also widely accepted as a challenging testbed for AI research because of its enormous state space, partially observed information, multi-agent collaboration, and so on. With the help of annual AIIDE and CIG competitions, a growing number of SC bots are proposed and continuously improved. However, a large gap remains between the top-level bot and the professional human player. One vital reason is that current SC bots mainly rely on predefined rules to select macro actions during their games. These rules are not scalable and efficient enough to cope with the enormous yet partially observed state space in the game. In this paper, we propose a deep reinforcement learning (DRL) framework to improve the selection of macro actions. Our framework is based on the combination of the Ape-X DQN and the Long-Short-Term-Memory (LSTM). We use this framework to build our bot, named as LastOrder. Our evaluation, based on training against all bots from the AIIDE 2017 StarCraft AI competition set, shows that LastOrder achieves an 83% winning rate, outperforming 26 bots in total 28 entrants.
Permutations Unlabeled beyond Sampling Unknown
Venue: arXiv cs.IT 2019
Year: 2019

A recent unlabeled sampling result by Unnikrishnan, Haghighatshoar and Vetterli states that with probability one over iid Gaussian matrices $A$, any $x$ can be uniquely recovered from an unknown permutation of $y = A x$ as soon as $A$ has at least twice as many rows as columns. We show that this condition on $A$ implies something much stronger: that an unknown vector $x$ can be recovered from measurements $y = T A x$, when the unknown $T$ belongs to an arbitrary set of invertible, diagonalizable linear transformations $\mathcal{T}$. The set $\mathcal{T}$ can be finite or countably infinite. When it is the set of $m \times m$ permutation matrices, we have the classical unlabeled sampling problem. We show that for almost all $A$ with at least twice as many rows as columns, all $x$ can be recovered either uniquely, or up to a scale depending on $\mathcal{T}$, and that the condition on the size of $A$ is necessary. Our proof is based on vector space geometry. Specializing to permutations we obtain a simplified proof of the uniqueness result of Unnikrishnan, Haghighatshoar and Vetterli. In this letter we are only concerned with uniqueness; stability and algorithms are left for future work.
Explore and Eliminate: Optimized Two-Stage Search for Millimeter-Wave Beam Alignment
Venue: arXiv cs.IT 2019
Year: 2019

Swift and accurate alignment of transmitter (Tx) and receiver (Rx) beams is a fundamental design challenge to enable reliable outdoor millimeter-wave communications. In this paper, we propose a new Optimized Two-Stage Search (OTSS) algorithm for Tx-Rx beam alignment via spatial scanning. In contrast to one-shot exhaustive search, OTSS judiciously divides the training energy budget into two stages. In the first stage, OTSS explores and trains all candidate beam pairs and then eliminates a set of less favorable pairs learned from the received signal profile. In the second stage, OTSS takes an extra measurement for each of the survived pairs and combines with the previous measurement to determine the best one. For OTSS, we derive an upper bound on its misalignment probability, under a single-path channel model with training codebooks having an ideal beam pattern. We also characterize the decay rate function of the upper bound with respect to the training budget and further derive the optimal design parameters of OTSS that maximize the decay rate. OTSS is proved to asymptotically outperform state-of-the-art beam alignment algorithms, and is numerically shown to achieve better performance with limited training budget and practically synthesized beams.
Automated Segmentation of Cervical Nuclei in Pap Smear Images using Deformable Multi-path Ensemble Model
Venue: arXiv cs.CV 2019
Year: 2019

Pap smear testing has been widely used for detecting cervical cancers based on the morphology properties of cell nuclei in microscopic image. An accurate nuclei segmentation could thus improve the success rate of cervical cancer screening. In this work, a method of automated cervical nuclei segmentation using Deformable Multipath Ensemble Model (D-MEM) is proposed. The approach adopts a U-shaped convolutional network as a backbone network, in which dense blocks are used to transfer feature information more effectively. To increase the flexibility of the model, we then use deformable convolution to deal with different nuclei irregular shapes and sizes. To reduce the predictive bias, we further construct multiple networks with different settings, which form an ensemble model. The proposed segmentation framework has achieved state-of-the-art accuracy on Herlev dataset with Zijdenbos similarity index (ZSI) of 0.933, and has the potential to be extended for solving other medical image segmentation tasks.
General Support-Effective Decomposition for Multi-Directional 3D Printing
Venue: arXiv cs.RO 2019
Year: 2019

We present a method for fabricating general models with multi-directional 3D printing systems by printing different model regions along with different directions. The core of our method is a support-effective volume decomposition algorithm that minimizes the area of the regions with large overhangs. A beam-guided searching algorithm with manufacturing constraints determines the optimal volume decomposition, which is represented by a sequence of clipping planes. While current approaches require manually assembling separate components into a final model, our algorithm allows for directly printing the final model in a single pass. It can also be applied to models with loops and handles. A supplementary algorithm generates special supporting structures for models where supporting structures for large overhangs cannot be eliminated. We verify the effectiveness of our method using two hardware systems: a Cartesian-motion based system and an angular-motion based system. A variety of 3D models have been successfully fabricated on these systems.
A Survey on Semantic Parsing
Venue: arXiv cs.CL 2019
Year: 2019

A significant amount of information in today's world is stored in structured and semi-structured knowledge bases. Efficient and simple methods to query them are essential and must not be restricted to only those who have expertise in formal query languages. The field of semantic parsing deals with converting natural language utterances to logical forms that can be easily executed on a knowledge base. In this survey, we examine the various components of a semantic parsing system and discuss prominent work ranging from the initial rule based methods to the current neural approaches to program synthesis. We also discuss methods that operate using varying levels of supervision and highlight the key challenges involved in the learning of such systems.
ZerNet: Convolutional Neural Networks on Arbitrary Surfaces via Zernike Local Tangent Space Estimation
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we propose a novel formulation to extend CNNs to two-dimensional (2D) manifolds using orthogonal basis functions, called Zernike polynomials. In many areas, geometric features play a key role in understanding scientific phenomena. Thus, an ability to codify geometric features into a mathematical quantity can be critical. Recently, convolutional neural networks (CNNs) have demonstrated the promising capability of extracting and codifying features from visual information. However, the progress has been concentrated in computer vision applications where there exists an inherent grid-like structure. In contrast, many geometry processing problems are defined on curved surfaces, and the generalization of CNNs is not quite trivial. The difficulties are rooted in the lack of key ingredients such as the canonical grid-like representation, the notion of consistent orientation, and a compatible local topology across the domain. In this paper, we prove that the convolution of two functions can be represented as a simple dot product between Zernike polynomial coefficients; and the rotation of a convolution kernel is essentially a set of 2-by-2 rotation matrices applied to the coefficients. As such, the key contribution of this work resides in a concise but rigorous mathematical generalization of the CNN building blocks.
Capacity and outage analysis of a dual-hop decode-and-forward relay-aided NOMA scheme
Venue: arXiv cs.IT 2019
Year: 2019

Non-orthogonal multiple access (NOMA) is regarded as a candidate radio access technique for the next generation wireless networks because of its manifold spectral gains. A two-phase cooperative relaying strategy (CRS) is proposed in this paper by exploiting the concept of both downlink and uplink NOMA (termed as DU-CNOMA). In the proposed protocol, a transmitter considered as a source transmits a NOMA composite signal consisting of two symbols to the destination and relay during the first phase, following the principle of downlink NOMA. In the second phase, the relay forwards the symbol decoded by successive interference cancellation to the destination, whereas the source transmits a new symbol to the destination in parallel with the relay, following the principle of uplink NOMA. The ergodic sum capacity, outage probability, and outage sum capacity are investigated comprehensively along with analytical derivations, under both perfect and imperfect successive interference cancellation. The performance improvement of the proposed DU-CNOMA over the conventional CRS using NOMA, is proved through analysis and computer simulation. Furthermore, the correctness of the author's analysis is proved through a strong agreement between simulation and analytical results.
Megaphone: Latency-conscious state migration for distributed streaming dataflows
Venue: arXiv cs.DC 2019
Year: 2019

We design and implement Megaphone, a data migration mechanism for stateful distributed dataflow engines with latency objectives. When compared to existing migration mechanisms, Megaphone has the following differentiating characteristics: (i) migrations can be subdivided to a configurable granularity to avoid latency spikes, and (ii) migrations can be prepared ahead of time to avoid runtime coordination. Megaphone is implemented as a library on an unmodified timely dataflow implementation, and provides an operator interface compatible with its existing APIs. We evaluate Megaphone on established benchmarks with varying amounts of state and observe that compared to naïve approaches Megaphone reduces service latencies during reconfiguration by orders of magnitude without significantly increasing steady-state overhead.
Centralized and Decentralized Cache-Aided Interference Management in Heterogeneous Parallel Channels
Venue: arXiv cs.IT 2019
Year: 2019

We consider the problem of cache-aided interference management in a network consisting of $K_{\mathrm{T}}$ single-antenna transmitters and $K_{\mathrm{R}}$ single-antenna receivers, where each node is equipped with a cache memory. Transmitters communicate with receivers over two heterogenous parallel subchannels: the P-subchannel for which transmitters have perfect instantaneous knowledge of the channel state, and the N-subchannel for which the transmitters have no knowledge of the instantaneous channel state. Under the assumptions of uncoded placement and separable one-shot linear delivery over the two subchannels, we characterize the optimal degrees-of-freedom (DoF) to within a constant multiplicative factor of $2$. We extend the result to a decentralized setting in which no coordination is required for content placement at the receivers. In this case, we characterize the optimal one-shot linear DoF to within a factor of $3$.
On the stability of nucleic acid feedback controllers
Venue: arXiv cs.SY 2019
Year: 2019

Recent work has shown how chemical reaction network theory may be used to design dynamical systems that can be implemented biologically in nucleic acid-based chemistry. While this has allowed the construction of advanced open-loop circuitry based on cascaded DNA strand displacement (DSD) reactions, little progress has so far been made in developing the requisite theoretical machinery to inform the systematic design of feedback controllers in this context. Here, we develop a number of foundational theoretical results on the equilibria, stability, and dynamics of nucleic acid controllers. In particular, we show that the implementation of feedback controllers using DSD reactions introduces additional nonlinear dynamics, even in the case of purely linear designs, e.g. PI controllers. By decomposing the effects of these non-observable nonlinear dynamics, we show that, in general, the stability of the linear system design does not necessarily imply the stability of the underlying chemical network, which can be lost under experimental variability when feedback interconnections are introduced. We provide an in-depth theoretical analysis of an example illustrating this phenomenon, whereby the linear design does not capture the instability of the full nonlinear system implemented as a DSD reaction network, and we further confirm these results using VisualDSD, a bespoke software tool for simulating nucleic acid-based circuits. Our analysis highlight the many interesting and unique characteristics of this important new class of feedback control systems.
How Energy-Efficient Can a Wireless Communication System Become?
Venue: arXiv cs.IT 2019
Year: 2019

The data traffic in wireless networks is steadily growing. The long-term trend follows Cooper's law, where the traffic is doubled every two-and-a-half year, and it will likely continue for decades to come. The data transmission is tightly connected with the energy consumption in the power amplifiers, transceiver hardware, and baseband processing. The relation is captured by the energy efficiency metric, measured in bit/Joule, which describes how much energy is consumed per correctly received information bit. While the data rate is fundamentally limited by the channel capacity, there is currently no clear understanding of how energy-efficient a communication system can become. Current research papers typically present values on the order of 10 Mbit/Joule, while previous network generations seem to operate at energy efficiencies on the order of 10 kbit/Joule. Is this roughly as energy-efficient future systems (5G and beyond) can become, or are we still far from the physical limits? These questions are answered in this paper. We analyze a different cases representing potential future deployment and hardware characteristics.
Influence of Demand and Generation Uncertainty on the Operational Efficiency of Smart Grids
Venue: arXiv cs.SY 2019
Year: 2019

To ensure the smooth and near optimal operation of storage and controllable generation in a grid with a high share of renewable energies, it is important to have accurate forecasts for load and generation. But even with the advanced forecasts available today, the prediction error can have a significant impact on the operation performance of the system. This paper compares and analyzes the impact of the prediction-error on the operational performance in case of a small virtual power plant.
Wireless Data Acquisition for Edge Learning: Data-Importance Aware Retransmission
Venue: arXiv cs.IT 2019
Year: 2019

By deploying machine-learning algorithms at the network edge, edge learning can leverage the enormous real-time data generated by billions of mobile devices to train AI models, which enable intelligent mobile applications. In this emerging research area, one key direction is to efficiently utilize radio resources for wireless data acquisition to minimize the latency of executing a learning task at an edge server. Along this direction, we consider the specific problem of retransmission decision in each communication round to ensure both reliability and quantity of those training data for accelerating model convergence. To solve the problem, a new retransmission protocol called data-importance aware automatic-repeat-request (importance ARQ) is proposed. Unlike the classic ARQ focusing merely on reliability, importance ARQ selectively retransmits a data sample based on its uncertainty which helps learning and can be measured using the model under training. Underpinning the proposed protocol is a derived elegant communication-learning relation between two corresponding metrics, i.e., signal-to-noise ratio (SNR) and data uncertainty. This relation facilitates the design of a simple threshold based policy for importance ARQ. The policy is first derived based on the classic classifier model of support vector machine (SVM), where the uncertainty of a data sample is measured by its distance to the decision boundary. The policy is then extended to the more complex model of convolutional neural networks (CNN) where data uncertainty is measured by entropy. Extensive experiments have been conducted for both the SVM and CNN using real datasets with balanced and imbalanced distributions. Experimental results demonstrate that importance ARQ effectively copes with channel fading and noise in wireless data acquisition to achieve faster model convergence than the conventional channel-aware ARQ.
Learn to See by Events: Color Frame Synthesis from Event and RGB Cameras
Venue: arXiv cs.CV 2019
Year: 2019

Event cameras are biologically-inspired sensors that gather the temporal evolution of the scene. They capture pixel-wise brightness variations and output a corresponding stream of asynchronous events. Despite having multiple advantages with respect to traditional cameras, their use is partially prevented by the limited applicability of traditional data processing and vision algorithms. To this aim, we present a framework which exploits the output stream of event cameras to synthesize RGB frames, relying on an initial or a periodic set of color key-frames and the sequence of intermediate events. Differently from existing work, we propose a deep learning-based frame synthesis method, consisting of an adversarial architecture combined with a recurrent module. Qualitative results and quantitative per-pixel, perceptual, and semantic evaluation on four public datasets confirm the quality of the synthesized images.
Understanding Individual Decisions of CNNs via Contrastive Backpropagation
Venue: arXiv cs.CV 2019
Year: 2019

A number of backpropagation-based approaches such as DeConvNets, vanilla Gradient Visualization and Guided Backpropagation have been proposed to better understand individual decisions of deep convolutional neural networks. The saliency maps produced by them are proven to be non-discriminative. Recently, the Layer-wise Relevance Propagation (LRP) approach was proposed to explain the classification decisions of rectifier neural networks. In this work, we evaluate the discriminativeness of the generated explanations and analyze the theoretical foundation of LRP, i.e. Deep Taylor Decomposition. The experiments and analysis conclude that the explanations generated by LRP are not class-discriminative. Based on LRP, we propose Contrastive Layer-wise Relevance Propagation (CLRP), which is capable of producing instance-specific, class-discriminative, pixel-wise explanations. In the experiments, we use the CLRP to explain the decisions and understand the difference between neurons in individual classification decisions. We also evaluate the explanations quantitatively with a Pointing Game and an ablation study. Both qualitative and quantitative evaluations show that the CLRP generates better explanations than the LRP. The code is available.
Solving High Volume Capacitated Vehicle Routing Problem with Time Windows using Recursive-DBSCAN clustering algorithm
Venue: arXiv cs.OH 2019
Year: 2019

This paper introduces a new approach to improve the performance of the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) solvers for a high number of nodes. It proposes to cluster nodes together using Recursive-DBSCAN - an algorithm that recursively applies DBSCAN until clusters below the preset maximum number of nodes are obtained. That approach leads to 61% decrease in runtimes of the CVRPTW solver as benchmarked against Google Optimization Tools, while the difference of total distance and number of vehicles used by found solutions is below 7%. The improvement of runtimes with the Recursive-DBSCAN method is because of splitting the node-set into constituent clusters, which limits the number of solutions checked by the solver, consequently reducing the runtime. The proposed method consumes less memory and is able to find solutions for problems up to 5000 nodes, while the baseline Google Optimisation Tools solves problems up to 2000 nodes.
Variational Saccading: Efficient Inference for Large Resolution Images
Venue: arXiv cs.CV 2019
Year: 2019

Image classification with deep neural networks is typically restricted to images of small dimensionality such as 224 x 244 in Resnet models [24]. This limitation excludes the 4000 x 3000 dimensional images that are taken by modern smartphone cameras and smart devices. In this work, we aim to mitigate the prohibitive inferential and memory costs of operating in such large dimensional spaces. To sample from the high-resolution original input distribution, we propose using a smaller proxy distribution to learn the co-ordinates that correspond to regions of interest in the high-dimensional space. We introduce a new principled variational lower bound that captures the relationship of the proxy distribution's posterior and the original image's co-ordinate space in a way that maximizes the conditional classification likelihood. We empirically demonstrate on one synthetic benchmark and one real world large resolution DSLR camera image dataset that our method produces comparable results with ~10x faster inference and lower memory consumption than a model that utilizes the entire original input distribution. Finally, we experiment with a more complex setting using mini-maps from Starcraft II [56] to infer the number of characters in a complex 3d-rendered scene. Even in such complicated scenes our model provides strong localization: a feature missing from traditional classification models.
Attend More Times for Image Captioning
Venue: arXiv cs.CV 2019
Year: 2019

Most attention-based image captioning models attend to the image once per word. However, attending once per word is rigid and is easy to miss some information. Attending more times can adjust the attention position, find the missing information back and avoid generating the wrong word. In this paper, we show that attending more times per word can gain improvements in the image captioning task, without increasing the number of parameters. We propose a flexible two-LSTM merge model to make it convenient to encode more attentions than words. Our captioning model uses two LSTMs to encode the word sequence and the attention sequence respectively. The information of the two LSTMs and the image feature are combined to predict the next word. Experiments on the MSCOCO caption dataset show that our method outperforms the state-of-the-art. Using bottom up features and self-critical training method, our method gets BLEU-4, METEOR, ROUGE-L, CIDEr and SPICE scores of 0.381, 0.283, 0.580, 1.261 and 0.220 on the Karpathy test split.