OpenRaiser/Intern-Atlas huggingface dataset:
The Impact of Information in Greedy Submodular Maximization
Venue: arXiv cs.DS 2019
Year: 2019

The maximization of submodular functions is an NP-Hard problem for certain subclasses of functions, for which a simple greedy algorithm has been shown to guarantee a solution whose quality is within 1/2 of the optimal. When this algorithm is implemented in a distributed way, agents sequentially make decisions based on the decisions of all previous agents. This work explores how limited access to the decisions of previous agents affects the quality of the solution of the greedy algorithm. Specifically, we provide tight upper and lower bounds on how well the algorithm performs, as a function of the information available to each agent. Intuitively, the results show that performance roughly degrades proportionally to the size of the largest group of agents which make decisions independently. Additionally, we consider the case where a system designer is given a set of agents and a global limit on the amount of information that can be accessed. Our results show that the best designs partition the agents into equally-sized sets and allow agents to access the decisions of all previous agents within the same set.
Clustering Prominent People and Organizations in Topic-Specific Text Corpora
Venue: arXiv cs.CL 2019
Year: 2019

Named entities in text documents are the names of people, organization, location or other types of objects in the documents that exist in the real world. A persisting research challenge is to use computational techniques to identify such entities in text documents. Once identified, several text mining tools and algorithms can be utilized to leverage these discovered named entities and improve NLP applications. In this paper, a method that clusters prominent names of people and organizations based on their semantic similarity in a text corpus is proposed. The method relies on common named entity recognition techniques and on recent word embeddings models. The semantic similarity scores generated using the word embeddings models for the named entities are used to cluster similar entities of the people and organizations types. Two human judges evaluated ten variations of the method after it was run on a corpus that consists of 4,821 articles on a specific topic. The performance of the method was measured using three quantitative measures. The results of these three metrics demonstrate that the method is effective in clustering semantically similar named entities.
On the Capacity of Symmetric $M$-user Gaussian Interference Channels with Feedback
Venue: arXiv cs.IT 2019
Year: 2019

A general time-varying feedback coding scheme is proposed for $M$-user fully connected symmetric Gaussian interference channels. Based on the analysis of the general coding scheme, we prove a theorem which gives a criterion for designing good time-varying feedback codes for Gaussian interference channels. The proposed scheme improves the Suh-Tse and Kramer inner bounds of the channel capacity for the cases of weak and not very strong interference when $M=2$. This capacity improvement is more significant when the signal-to-noise ratio (SNR) is not very high. In addition, our coding scheme can be proved mathematically and numerically to outperform the Kramer code for $M\geq 2$ when Signal to Noise Ratio (SNR) is equal to Interference to Noise Ratio (INR). Besides, the generalized degrees-of-freedom (GDoF) of our proposed coding scheme can be proved to be optimal in the all network situations (very weak, weak, strong, very strong) for any $M$. The numerical results show that our coding scheme can attain better performance than the Suh-Tse coding scheme for $M=2$ or the Mohajer-Tandon-Poor lattice coding scheme for $M>2$. Furthermore, the simplicity of the encoding/decoding algorithms is another strong point of our proposed coding scheme compared with the Suh-Tse coding scheme when $M=2$ and the Mohajer-Tandon-Poor lattice coding scheme when $M>2$. More importantly, our results show that an optimal coding scheme for the symmetric Gaussian interference channels with feedback can be achieved by only using marginal posterior distributions under a better cooperation strategy between transmitters.
Recurrently Exploring Class-wise Attention in A Hybrid Convolutional and Bidirectional LSTM Network for Multi-label Aerial Image Classification
Venue: arXiv cs.CV 2019
Year: 2019

Aerial image classification is of great significance in remote sensing community, and many researches have been conducted over the past few years. Among these studies, most of them focus on categorizing an image into one semantic label, while in the real world, an aerial image is often associated with multiple labels, e.g., multiple object-level labels in our case. Besides, a comprehensive picture of present objects in a given high resolution aerial image can provide more in-depth understanding of the studied region. For these reasons, aerial image multi-label classification has been attracting increasing attention. However, one common limitation shared by existing methods in the community is that the co-occurrence relationship of various classes, so called class dependency, is underexplored and leads to an inconsiderate decision. In this paper, we propose a novel end-to-end network, namely class-wise attention-based convolutional and bidirectional LSTM network (CA-Conv-BiLSTM), for this task. The proposed network consists of three indispensable components: 1) a feature extraction module, 2) a class attention learning layer, and 3) a bidirectional LSTM-based sub-network. Particularly, the feature extraction module is designed for extracting fine-grained semantic feature maps, while the class attention learning layer aims at capturing discriminative class-specific features. As the most important part, the bidirectional LSTM-based sub-network models the underlying class dependency in both directions and produce structured multiple object labels. Experimental results on UCM multi-label dataset and DFC15 multi-label dataset validate the effectiveness of our model quantitatively and qualitatively.
High-dimensional estimation via sum-of-squares proofs
Venue: arXiv cs.DS 2019
Year: 2019

Estimation is the computational task of recovering a hidden parameter $x$ associated with a distribution $D_x$, given a measurement $y$ sampled from the distribution. High dimensional estimation problems arise naturally in statistics, machine learning, and complexity theory. Many high dimensional estimation problems can be formulated as systems of polynomial equations and inequalities, and thus give rise to natural probability distributions over polynomial systems. Sum-of-squares proofs provide a powerful framework to reason about polynomial systems, and further there exist efficient algorithms to search for low-degree sum-of-squares proofs. Understanding and characterizing the power of sum-of-squares proofs for estimation problems has been a subject of intense study in recent years. On one hand, there is a growing body of work utilizing sum-of-squares proofs for recovering solutions to polynomial systems when the system is feasible. On the other hand, a general technique referred to as pseudocalibration has been developed towards showing lower bounds on the degree of sum-of-squares proofs. Finally, the existence of sum-of-squares refutations of a polynomial system has been shown to be intimately connected to the existence of spectral algorithms. In this article we survey these developments.
Kalman Filter-based Heuristic Ensemble (KFHE): A new perspective on multi-class ensemble classification using Kalman filters
Venue: arXiv cs.LG 2019
Year: 2019

This paper introduces a new perspective on multi-class ensemble classification that considers training an ensemble as a state estimation problem. The new perspective considers the final ensemble classifier model as a static state, which can be estimated using a Kalman filter that combines noisy estimates made by individual classifier models. A new algorithm based on this perspective, the Kalman Filter-based Heuristic Ensemble (KFHE), is also presented in this paper which shows the practical applicability of the new perspective. Experiments performed on 30 datasets compare KFHE with state-of-the-art multi-class ensemble classification algorithms and show the potential and effectiveness of the new perspective and algorithm. Existing ensemble approaches trade off classification accuracy against robustness to class label noise, but KFHE is shown to be significantly better or at least as good as the state-of-the-art algorithms for datasets both with and without class label noise.
Deep Graph Laplacian Regularization for Robust Denoising of Real Images
Venue: arXiv cs.CV 2019
Year: 2019

Recent developments in deep learning have revolutionized the paradigm of image restoration. However, its applications on real image denoising are still limited, due to its sensitivity to training data and the complex nature of real image noise. In this work, we combine the robustness merit of model-based approaches and the learning power of data-driven approaches for real image denoising. Specifically, by integrating graph Laplacian regularization as a trainable module into a deep learning framework, we are less susceptible to overfitting than pure CNN-based approaches, achieving higher robustness to small datasets and cross-domain denoising. First, a sparse neighborhood graph is built from the output of a convolutional neural network (CNN). Then the image is restored by solving an unconstrained quadratic programming problem, using a corresponding graph Laplacian regularizer as a prior term. The proposed restoration pipeline is fully differentiable and hence can be end-to-end trained. Experimental results demonstrate that our work is less prone to overfitting given small training data. It is also endowed with strong cross-domain generalization power, outperforming the state-of-the-art approaches by a remarkable margin.
Spectrum concentration in deep residual learning: a free probability approach
Venue: arXiv cs.LG 2019
Year: 2019

We revisit the initialization of deep residual networks (ResNets) by introducing a novel analytical tool in free probability to the community of deep learning. This tool deals with non-Hermitian random matrices, rather than their conventional Hermitian counterparts in the literature. As a consequence, this new tool enables us to evaluate the singular value spectrum of the input-output Jacobian of a fully-connected deep ResNet for both linear and nonlinear cases. With the powerful tool of free probability, we conduct an asymptotic analysis of the spectrum on the single-layer case, and then extend this analysis to the multi-layer case of an arbitrary number of layers. In particular, we propose to rescale the classical random initialization by the number of residual units, so that the spectrum has the order of $O(1)$, when compared with the large width and depth of the network. We empirically demonstrate that the proposed initialization scheme learns at a speed of orders of magnitudes faster than the classical ones, and thus attests a strong practical relevance of this investigation.
Mod-DeepESN: Modular Deep Echo State Network
Venue: arXiv cs.LG 2019
Year: 2019

Neuro-inspired recurrent neural network algorithms, such as echo state networks, are computationally lightweight and thereby map well onto untethered devices. The baseline echo state network algorithms are shown to be efficient in solving small-scale spatio-temporal problems. However, they underperform for complex tasks that are characterized by multi-scale structures. In this research, an intrinsic plasticity-infused modular deep echo state network architecture is proposed to solve complex and multiple timescale temporal tasks. It outperforms state-of-the-art for time series prediction tasks.
Network Optimization for Unified Packet and Circuit Switched Networks
Venue: arXiv cs.NI 2019
Year: 2019

Internet traffic continues to grow relentlessly, driven largely by increasingly high resolution video content. Although studies have shown that the majority of packets processed by Internet routers are pass-through traffic, they nonetheless have to be queued and routed at every hop in current networks, which unnecessarily adds substantial delays and processing costs. Such pass-through traffic can be better circuit-switched through the underlying optical transport network by means of pre-established circuits, which is possible in a unified packet and circuit switched network. In this paper, we propose a novel convex optimization framework based on a new destination-based multicommodity flow formulation for the allocation of circuits in such unified networks. In particular, we consider two deployment settings, one based on real-time traffic monitoring, and the other relying upon history-based traffic predictions. In both cases, we formulate global network optimization objectives as concave functions that capture the fair sharing of network capacity among competing traffic flows. The convexity of our problem formulations ensures globally optimal solutions.
Covariance Matrix Estimation from Linearly-Correlated Gaussian Samples
Venue: arXiv cs.IT 2019
Year: 2019

Covariance matrix estimation concerns the problem of estimating the covariance matrix from a collection of samples, which is of extreme importance in many applications. Classical results have shown that $O(n)$ samples are sufficient to accurately estimate the covariance matrix from $n$-dimensional independent Gaussian samples. However, in many practical applications, the received signal samples might be correlated, which makes the classical analysis inapplicable. In this paper, we develop a non-asymptotic analysis for the covariance matrix estimation from correlated Gaussian samples. Our theoretical results show that the error bounds are determined by the signal dimension $n$, the sample size $m$, and the shape parameter of the distribution of the correlated sample covariance matrix. Particularly, when the shape parameter is a class of Toeplitz matrices (which is of great practical interest), $O(n)$ samples are also sufficient to faithfully estimate the covariance matrix from correlated samples. Simulations are provided to verify the correctness of the theoretical results.
Generalization Error in Deep Learning
Venue: arXiv cs.LG 2019
Year: 2019

Deep learning models have lately shown great performance in various fields such as computer vision, speech recognition, speech translation, and natural language processing. However, alongside their state-of-the-art performance, it is still generally unclear what is the source of their generalization ability. Thus, an important question is what makes deep neural networks able to generalize well from the training set to new data. In this article, we provide an overview of the existing theory and bounds for the characterization of the generalization error of deep neural networks, combining both classical and more recent theoretical and empirical results.
Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
Venue: arXiv cs.LG 2019
Year: 2019

Neural networks have many successful applications, while much less theoretical understanding has been gained. Towards bridging this gap, we study the problem of learning a two-layer overparameterized ReLU neural network for multi-class classification via stochastic gradient descent (SGD) from random initialization. In the overparameterized setting, when the data comes from mixtures of well-separated distributions, we prove that SGD learns a network with a small generalization error, albeit the network has enough capacity to fit arbitrary labels. Furthermore, the analysis provides interesting insights into several aspects of learning neural networks and can be verified based on empirical studies on synthetic data and on the MNIST dataset.
Designing molecular circuits for approximate maximum a posteriori demodulation of concentration modulated signals
Venue: arXiv cs.IT 2019
Year: 2019

Motivated by the fact that living cells use molecular circuits (i.e. a set of chemical reactions) for information processing, this paper investigates the problem of designing molecular circuits for demodulation. In our earlier work, we use a Markovian approach to derive a demodulator for diffusion-based molecular communication. The demodulation filters take the form of an ordinary differential equation which computes the log-posteriori probability of a transmission symbol being sent. This work considers the realisation of these demodulation filters using molecular circuits assuming the transmission symbols are rectangular pulses of the same duration but different amplitudes, i.e. concentration modulation. This paper makes a number of contributions. First, we use time-scale separation and renewal theory to analytically derive an approximation of the demodulation filter from our earlier work. Second, we present a method to turn this approximation into a molecular circuit. By using simulation, we show that the output of the derived molecular circuit is approximately equal to the log-posteriori probability calculated by the exact demodulation filter if the log-posteriori probability is positive. Third, we demonstrate that a biochemical circuit in yeast behaves similarly to the derived molecular demodulation filter and is therefore a candidate for implementing the derived filter.
Autoencoder Based Sample Selection for Self-Taught Learning
Venue: arXiv cs.LG 2019
Year: 2019

Self-taught learning is a technique that uses a large number of unlabeled data as source samples to improve the task performance on target samples. Compared with other transfer learning techniques, self-taught learning can be applied to a broader set of scenarios due to the loose restrictions on the source data. However, knowledge transferred from source samples that are not sufficiently related to the target domain may negatively influence the target learner, which is referred to as negative transfer. In this paper, we propose a metric for the relevance between a source sample and the target samples. To be more specific, both source and target samples are reconstructed through a single-layer autoencoder with a linear relationship between source samples and reconstructed target samples being simultaneously enforced. An $\ell_{2,1}$-norm sparsity constraint is imposed on the transformation matrix to identify source samples relevant to the target domain. Source domain samples that are deemed relevant are assigned pseudo-labels reflecting their relevance to target domain samples, and are combined with target samples in order to provide an expanded training set for classifier training. Local data structures are also preserved during source sample selection through spectral graph analysis. Promising results in extensive experiments show the advantages of the proposed approach.
Finite Blocklength Analysis of Multiple Access Channels with/without Cooperation
Venue: arXiv cs.IT 2019
Year: 2019

Motivated by the demand of reliable and low latency communications, we employ tools from information theory, stochastic processes and queueing theory, in order to provide a comprehensive framework regarding the analysis of a Time Division Multiple Access (TDMA) network with bursty traffic, in the finite blocklength regime. Specifically, we re-examine the stability conditions of a noncooperative TDMA multiple access channel, evaluate the optimal throughput, and identify the optimal trade-off between data packet size and latency. The evaluation is performed both numerically and via the proposed approximations that result in closed form expressions. Then, we examine the stability conditions and the performance of the Multiple Access Relay Channel with TDMA scheduling, subject to finite blocklength constraints, by applying a cognitive cooperation protocol that assumes relaying is enabled when sources are idle. Finally, we propose the novel Batch-And-Forward (BAF) strategy, that can significantly enhance the performance of cooperative networks in the finite blocklength regime, as well as reduce the requirement in metadata. The BAF strategy is quite versatile, thus, it can be embedded in existing cooperative protocols, without imposing additional complexity on the overall scheme.
Non-Learning based Deep Parallel MRI Reconstruction (NLDpMRI)
Venue: arXiv cs.CV 2019
Year: 2019

Fast data acquisition in Magnetic Resonance Imaging (MRI) is vastly in demand and scan time directly depends on the number of acquired k-space samples. Recently, the deep learning-based MRI reconstruction techniques were suggested to accelerate MR image acquisition. The most common issues in any deep learning-based MRI reconstruction approaches are generalizability and transferability. For different MRI scanner configurations using these approaches, the network must be trained from scratch every time with new training dataset, acquired under new configurations, to be able to provide good reconstruction performance. Here, we propose a new generalized parallel imaging method based on deep neural networks called NLDpMRI to reduce any structured aliasing ambiguities related to the different k-space undersampling patterns for accelerated data acquisition. Two loss functions including non-regularized and regularized are proposed for parallel MRI reconstruction using deep network optimization and we reconstruct MR images by optimizing the proposed loss functions over the network parameters. Unlike any deep learning-based MRI reconstruction approaches, our method doesn't include any training step that the network learns from a large number of training samples and it only needs the single undersampled multi-coil k-space data for reconstruction. Also, the proposed method can handle k-space data with different undersampling patterns, and the different number of coils. Experimental results show that the proposed method outperforms the current state-of-the-art GRAPPA method and the deep learning-based variational network method.
eQASM: An Executable Quantum Instruction Set Architecture
Venue: arXiv cs.AR 2019
Year: 2019

A widely-used quantum programming paradigm comprises of both the data flow and control flow. Existing quantum hardware cannot well support the control flow, significantly limiting the range of quantum software executable on the hardware. By analyzing the constraints in the control microarchitecture, we found that existing quantum assembly languages are either too high-level or too restricted to support comprehensive flow control on the hardware. Also, as observed with the quantum microinstruction set QuMIS, the quantum instruction set architecture (QISA) design may suffer from limited scalability and flexibility because of microarchitectural constraints. It is an open challenge to design a scalable and flexible QISA which provides a comprehensive abstraction of the quantum hardware. In this paper, we propose an executable QISA, called eQASM, that can be translated from quantum assembly language (QASM), supports comprehensive quantum program flow control, and is executed on a quantum control microarchitecture. With efficient timing specification, single-operation-multiple-qubit execution, and a very-long-instruction-word architecture, eQASM presents better scalability than QuMIS. The definition of eQASM focuses on the assembly level to be expressive. Quantum operations are configured at compile time instead of being defined at QISA design time. We instantiate eQASM into a 32-bit instruction set targeting a seven-qubit superconducting quantum processor. We validate our design by performing several experiments on a two-qubit quantum processor.