OpenRaiser/Intern-Atlas huggingface dataset:
A Simple and Practical Concurrent Non-blocking Unbounded Graph with Reachability Queries
Venue: arXiv cs.DC 2019
Year: 2019

Graph algorithms applied in many applications, including social networks, communication networks, VLSI design, graphics, and several others, require dynamic modifications -- addition and removal of vertices and/or edges -- in the graph. This paper presents a novel concurrent non-blocking algorithm to implement a dynamic unbounded directed graph in a shared-memory machine. The addition and removal operations of vertices and edges are lock-free. For a finite sized graph, the lookup operations are wait-free. Most significant component of the presented algorithm is the reachability query in a concurrent graph. The reachability queries in our algorithm are obstruction-free and thus impose minimal additional synchronization cost over other operations. We prove that each of the data structure operations are linearizable. We extensively evaluate a sample C/C++ implementation of the algorithm through a number of micro-benchmarks. The experimental results show that the proposed algorithm scales well with the number of threads and on an average provides 5 to 7x performance improvement over a concurrent graph implementation using coarse-grained locking.
Repetition avoidance in products of factors
Venue: arXiv cs.DM 2019
Year: 2019

We consider a variation on a classical avoidance problem from combinatorics on words that has been introduced by Mousavi and Shallit at DLT 2013. Let $\texttt{pexp}_i(w)$ be the supremum of the exponent over the products of $i$ factors of the word $w$. The repetition threshold $\texttt{RT}_i(k)$ is then the infimum of $\texttt{pexp}_i(w)$ over all words $w\inΣ^ω_k$. Mousavi and Shallit obtained that $\texttt{RT}_i(2)=2i$ and $\texttt{RT}_2(3)=\tfrac{13}4$. We show that $\texttt{RT}_i(3)=\tfrac{3i}2+\tfrac14$ if $i$ is even and $\texttt{RT}_i(3)=\tfrac{3i}2+\tfrac16$ if $i$ is odd and $i\ge3$.
Massive MIMO Channel Estimation for Millimeter Wave Systems via Matrix Completion
Venue: arXiv cs.IT 2019
Year: 2019

Millimeter Wave (mmWave) massive Multiple Input Multiple Output (MIMO) systems realizing directive beamforming require reliable estimation of the wireless propagation channel. However, mmWave channels are characterized by high variability that severely challenges their recovery over short training periods. Current channel estimation techniques exploit either the channel sparsity in the beamspace domain or its low rank property in the antenna domain, nevertheless, they still require large numbers of training symbols for satisfactory performance. In this paper, we present a novel channel estimation algorithm that jointly exploits the latter two properties of mmWave channels to provide more accurate recovery, especially for shorter training intervals. The proposed iterative algorithm is based on the Alternating Direction Method of Multipliers (ADMM) and provides the global optimum solution to the considered convex mmWave channel estimation problem with fast convergence properties.
Convolutional Neural Network: Text Classification Model for Open Domain Question Answering System
Venue: arXiv cs.IR 2019
Year: 2019

Recently machine learning is being applied to almost every data domain one of which is Question Answering Systems (QAS). A typical Question Answering System is fairly an information retrieval system, which matches documents or text and retrieve the most accurate one. The idea of open domain question answering system put forth, involves convolutional neural network text classifiers. The Classification model presented in this paper is multi-class text classifier. The neural network classifier can be trained on large dataset. We report series of experiments conducted on Convolution Neural Network (CNN) by training it on two different datasets. Neural network model is trained on top of word embedding. Softmax layer is applied to calculate loss and mapping of semantically related words. Gathered results can help justify the fact that proposed hypothetical QAS is feasible. We further propose a method to integrate Convolutional Neural Network Classifier to an open domain question answering system. The idea of Open domain will be further explained, but the generality of it indicates to the system of domain specific trainable models, thus making it an open domain.
Analysis of Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms
Venue: arXiv cs.LG 2019
Year: 2019

We analyze the regret of combinatorial Thompson sampling (CTS) for the combinatorial multi-armed bandit with probabilistically triggered arms under the semi-bandit feedback setting. We assume that the learner has access to an exact optimization oracle but does not know the expected base arm outcomes beforehand. When the expected reward function is Lipschitz continuous in the expected base arm outcomes, we derive $O(\sum_{i =1}^m \log T / (p_i Δ_i))$ regret bound for CTS, where $m$ denotes the number of base arms, $p_i$ denotes the minimum non-zero triggering probability of base arm $i$ and $Δ_i$ denotes the minimum suboptimality gap of base arm $i$. We also compare CTS with combinatorial upper confidence bound (CUCB) via numerical experiments on a cascading bandit problem.
Video Smoke Detection Based on Deep Saliency Network
Venue: arXiv cs.CV 2019
Year: 2019

Video smoke detection is a promising fire detection method especially in open or large spaces and outdoor environments. Traditional video smoke detection methods usually consist of candidate region extraction and classification, but lack powerful characterization for smoke. In this paper, we propose a novel video smoke detection method based on deep saliency network. Visual saliency detection aims to highlight the most important object regions in an image. The pixel-level and object-level salient convolutional neural networks are combined to extract the informative smoke saliency map. An end-to-end framework for salient smoke detection and existence prediction of smoke is proposed for application in video smoke detection. The deep feature map is combined with the saliency map to predict the existence of smoke in an image. Initial and augmented dataset are built to measure the performance of frameworks with different design strategies. Qualitative and quantitative analysis at frame-level and pixel-level demonstrate the excellent performance of the ultimate framework.
Distribution-aware Block-sparse Recovery via Convex Optimization
Venue: arXiv cs.IT 2019
Year: 2019

We study the problem of reconstructing a block-sparse signal from compressively sampled measurements. In certain applications, in addition to the inherent block-sparse structure of the signal, some prior information about the block support, i.e. blocks containing non-zero elements, might be available. Although many block-sparse recovery algorithms have been investigated in Bayesian framework, it is still unclear how to incorporate the information about the probability of occurrence into regularization-based block-sparse recovery in an optimal sense. In this work, we bridge between these fields by the aid of a new concept in conic integral geometry. Specifically, we solve a weighted optimization problem when the prior distribution about the block support is available. Moreover, we obtain the unique weights that minimize the expected required number of measurements. Our simulations on both synthetic and real data confirm that these weights considerably decrease the required sample complexity.
On the Optimality of Treating Inter-Cell Interference as Noise in Uplink Cellular Networks
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we explore the information-theoretic optimality of treating interference as noise (TIN) in cellular networks. We focus on uplink scenarios modeled by the Gaussian interfering multiple access channel (IMAC), comprising $K$ mutually interfering multiple access channels (MACs), each formed by an arbitrary number of transmitters communicating independent messages to one receiver. We define TIN for this setting as a scheme in which each MAC (or cell) performs a power-controlled version of its capacity-achieving strategy, with Gaussian codebooks and successive decoding, while treating interference from all other MACs (i.e. inter-cell interference) as noise. We characterize the generalized degrees-of-freedom (GDoF) region achieved through the proposed TIN scheme, and then identify conditions under which this achievable region is convex without the need for time-sharing. We then tighten these convexity conditions and identify a regime in which the proposed TIN scheme achieves the entire GDoF region of the IMAC and is within a constant gap of the entire capacity region.
Toward a Standardized and More Accurate Indonesian Part-of-Speech Tagging
Venue: arXiv cs.CL 2019
Year: 2019

Previous work in Indonesian part-of-speech (POS) tagging are hard to compare as they are not evaluated on a common dataset. Furthermore, in spite of the success of neural network models for English POS tagging, they are rarely explored for Indonesian. In this paper, we explored various techniques for Indonesian POS tagging, including rule-based, CRF, and neural network-based models. We evaluated our models on the IDN Tagged Corpus. A new state-of-the-art of 97.47 F1 score is achieved with a recurrent neural network. To provide a standard for future work, we release the dataset split that we used publicly.
Not Just Privacy: Improving Performance of Private Deep Learning in Mobile Cloud
Venue: arXiv cs.LG 2019
Year: 2019

The increasing demand for on-device deep learning services calls for a highly efficient manner to deploy deep neural networks (DNNs) on mobile devices with limited capacity. The cloud-based solution is a promising approach to enabling deep learning applications on mobile devices where the large portions of a DNN are offloaded to the cloud. However, revealing data to the cloud leads to potential privacy risk. To benefit from the cloud data center without the privacy risk, we design, evaluate, and implement a cloud-based framework ARDEN which partitions the DNN across mobile devices and cloud data centers. A simple data transformation is performed on the mobile device, while the resource-hungry training and the complex inference rely on the cloud data center. To protect the sensitive information, a lightweight privacy-preserving mechanism consisting of arbitrary data nullification and random noise addition is introduced, which provides strong privacy guarantee. A rigorous privacy budget analysis is given. Nonetheless, the private perturbation to the original data inevitably has a negative impact on the performance of further inference on the cloud side. To mitigate this influence, we propose a noisy training method to enhance the cloud-side network robustness to perturbed data. Through the sophisticated design, ARDEN can not only preserve privacy but also improve the inference performance. To validate the proposed ARDEN, a series of experiments based on three image datasets and a real mobile application are conducted. The experimental results demonstrate the effectiveness of ARDEN. Finally, we implement ARDEN on a demo system to verify its practicality.
PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning
Venue: arXiv cs.RO 2019
Year: 2019

Multi-agent path finding (MAPF) is an essential component of many large-scale, real-world robot deployments, from aerial swarms to warehouse automation. However, despite the community's continued efforts, most state-of-the-art MAPF planners still rely on centralized planning and scale poorly past a few hundred agents. Such planning approaches are maladapted to real-world deployments, where noise and uncertainty often require paths be recomputed online, which is impossible when planning times are in seconds to minutes. We present PRIMAL, a novel framework for MAPF that combines reinforcement and imitation learning to teach fully-decentralized policies, where agents reactively plan paths online in a partially-observable world while exhibiting implicit coordination. This framework extends our previous work on distributed learning of collaborative policies by introducing demonstrations of an expert MAPF planner during training, as well as careful reward shaping and environment sampling. Once learned, the resulting policy can be copied onto any number of agents and naturally scales to different team sizes and world dimensions. We present results on randomized worlds with up to 1024 agents and compare success rates against state-of-the-art MAPF planners. Finally, we experimentally validate the learned policies in a hybrid simulation of a factory mockup, involving both real-world and simulated robots.
Visual Attention Model for Cross-sectional Stock Return Prediction and End-to-End Multimodal Market Representation Learning
Venue: arXiv cs.CE 2019
Year: 2019

Technical and fundamental analysis are traditional tools used to analyze individual stocks; however, the finance literature has shown that the price movement of each individual stock correlates heavily with other stocks, especially those within the same sector. In this paper we propose a general purpose market representation that incorporates fundamental and technical indicators and relationships between individual stocks. We treat the daily stock market as a "market image" where rows (grouped by market sector) represent individual stocks and columns represent indicators. We apply a convolutional neural network over this market image to build market features in a hierarchical way. We use a recurrent neural network, with an attention mechanism over the market feature maps, to model temporal dynamics in the market. We show that our proposed model outperforms strong baselines in both short-term and long-term stock return prediction tasks. We also show another use for our market image: to construct concise and dense market embeddings suitable for downstream prediction tasks.
5G Massive MIMO Architectures: Self-Backhauled Small Cells versus Direct Access
Venue: arXiv cs.NI 2019
Year: 2019

In this paper, we focus on one of the key technologies for the fifth-generation wireless communication networks, massive multiple-input-multiple-output (mMIMO), by investigating two of its most relevant architectures: 1) to provide in-band backhaul for the ultra-dense network (UDN) of self-backhauled small cells (SCs), and 2) to provide direct access (DA) to user equipments (UEs). Through comprehensive 3GPP-based system-level simulations and analytical formulations, we show the end-to-end UE rates achievable with these two architectures. Differently from the existing works, we provide results for two strategies of self-backhauled SC deployments, namely random and ad-hoc, where in the latter SCs are purposely positioned close to UEs to achieve line-of-sight (LoS) access links. We also evaluate the optimal backhaul and access time resource partition due to the in-band self-backhauling (s-BH) operations. Our results show that the ad-hoc deployment of self-backhauled SCs closer to the UEs with optimal resource partition and with directive antenna patterns, provides rate improvements for cell-edge UEs that amount to 30% and tenfold gain, as compared to mMIMO DA architecture with pilot reuse 3 and reuse 1, respectively. On the other hand, mMIMO s-BH underperforms mMIMO DA above the median value of the UE rates when the effect of pilot contamination is less severe, and the LoS probability of the DA links improves.
Discovering Low-Precision Networks Close to Full-Precision Networks for Efficient Embedded Inference
Venue: arXiv cs.CV 2019
Year: 2019

To realize the promise of ubiquitous embedded deep network inference, it is essential to seek limits of energy and area efficiency. To this end, low-precision networks offer tremendous promise because both energy and area scale down quadratically with the reduction in precision. Here we demonstrate ResNet-18, -34, -50, -152, Inception-v3, Densenet-161, and VGG-16bn networks on the ImageNet classification benchmark that, at 8-bit precision exceed the accuracy of the full-precision baseline networks after one epoch of finetuning, thereby leveraging the availability of pretrained models. We also demonstrate ResNet-18, -34, -50, -152, Densenet-161, and VGG-16bn 4-bit models that match the accuracy of the full-precision baseline networks -- the highest scores to date. Surprisingly, the weights of the low-precision networks are very close (in cosine similarity) to the weights of the corresponding baseline networks, making training from scratch unnecessary. We find that gradient noise due to quantization during training increases with reduced precision, and seek ways to overcome this noise. The number of iterations required by SGD to achieve a given training error is related to the square of (a) the distance of the initial solution from the final plus (b) the maximum variance of the gradient estimates. Therefore, we (a) reduce solution distance by starting with pretrained fp32 precision baseline networks and fine-tuning, and (b) combat gradient noise introduced by quantization by training longer and reducing learning rates. Sensitivity analysis indicates that these simple techniques, coupled with proper activation function range calibration to take full advantage of the limited precision, are sufficient to discover low-precision networks, if they exist, close to fp32 precision baseline networks. The results herein provide evidence that 4-bits suffice for classification.
Temporal Pattern Attention for Multivariate Time Series Forecasting
Venue: arXiv cs.LG 2019
Year: 2019

Forecasting multivariate time series data, such as prediction of electricity consumption, solar power production, and polyphonic piano pieces, has numerous valuable applications. However, complex and non-linear interdependencies between time steps and series complicate the task. To obtain accurate prediction, it is crucial to model long-term dependency in time series data, which can be achieved to some good extent by recurrent neural network (RNN) with attention mechanism. Typical attention mechanism reviews the information at each previous time step and selects the relevant information to help generate the outputs, but it fails to capture the temporal patterns across multiple time steps. In this paper, we propose to use a set of filters to extract time-invariant temporal patterns, which is similar to transforming time series data into its "frequency domain". Then we proposed a novel attention mechanism to select relevant time series, and use its "frequency domain" information for forecasting. We applied the proposed model on several real-world tasks and achieved state-of-the-art performance in all of them with only one exception.
Hyperspectral Image Classification in the Presence of Noisy Labels
Venue: arXiv cs.CV 2019
Year: 2019

Label information plays an important role in supervised hyperspectral image classification problem. However, current classification methods all ignore an important and inevitable problem---labels may be corrupted and collecting clean labels for training samples is difficult, and often impractical. Therefore, how to learn from the database with noisy labels is a problem of great practical importance. In this paper, we study the influence of label noise on hyperspectral image classification, and develop a random label propagation algorithm (RLPA) to cleanse the label noise. The key idea of RLPA is to exploit knowledge (e.g., the superpixel based spectral-spatial constraints) from the observed hyperspectral images and apply it to the process of label propagation. Specifically, RLPA first constructs a spectral-spatial probability transfer matrix (SSPTM) that simultaneously considers the spectral similarity and superpixel based spatial information. It then randomly chooses some training samples as "clean" samples and sets the rest as unlabeled samples, and propagates the label information from the "clean" samples to the rest unlabeled samples with the SSPTM. By repeating the random assignment (of "clean" labeled samples and unlabeled samples) and propagation, we can obtain multiple labels for each training sample. Therefore, the final propagated label can be calculated by a majority vote algorithm. Experimental studies show that RLPA can reduce the level of noisy label and demonstrates the advantages of our proposed method over four major classifiers with a significant margin---the gains in terms of the average OA, AA, Kappa are impressive, e.g., 9.18%, 9.58%, and 0.1043. The Matlab source code is available at https://github.com/junjun-jiang/RLPA
An Ontology-Based Artificial Intelligence Model for Medicine Side-Effect Prediction: Taking Traditional Chinese Medicine as An Example
Venue: arXiv cs.AI 2019
Year: 2019

In this work, an ontology-based model for AI-assisted medicine side-effect (SE) prediction is developed, where three main components, including the drug model, the treatment model, and the AI-assisted prediction model, of proposed model are presented. To validate the proposed model, an ANN structure is established and trained by two hundred and forty-two TCM prescriptions. These data are gathered and classified from the most famous ancient TCM book and more than one thousand SE reports, in which two ontology-based attributions, hot and cold, are introduced to evaluate whether the prescription will cause SE or not. The results preliminarily reveal that it is a relationship between the ontology-based attributions and the corresponding predicted indicator that can be learnt by AI for predicting the SE, which suggests the proposed model has a potential in AI-assisted SE prediction. However, it should be noted that, the proposed model highly depends on the sufficient clinic data, and hereby, much deeper exploration is important for enhancing the accuracy of the prediction.
Finding Cheeger Cuts in Hypergraphs via Heat Equation
Venue: arXiv cs.DS 2019
Year: 2019

Cheeger's inequality states that a tightly connected subset can be extracted from a graph $G$ using an eigenvector of the normalized Laplacian associated with $G$. More specifically, we can compute a subset with conductance $O(\sqrt{ϕ_G})$, where $ϕ_G$ is the minimum conductance of a set in $G$. It has recently been shown that Cheeger's inequality can be extended to hypergraphs. However, as the normalized Laplacian of a hypergraph is no longer a matrix, we can only approximate to its eigenvectors; this causes a loss in the conductance of the obtained subset. To address this problem, we here consider the heat equation on hypergraphs, which is a differential equation exploiting the normalized Laplacian. We show that the heat equation has a unique solution and that we can extract a subset with conductance $\sqrt{ϕ_G}$ from the solution. An analogous result also holds for directed graphs.