OpenRaiser/Intern-Atlas huggingface dataset:
Decoder Choice Network for Meta-Learning
Venue: arXiv cs.LG 2019
Year: 2019

Meta-learning has been widely used for implementing few-shot learning and fast model adaptation. One kind of meta-learning methods attempt to learn how to control the gradient descent process in order to make the gradient-based learning have high speed and generalization. This work proposes a method that controls the gradient descent process of the model parameters of a neural network by limiting the model parameters in a low-dimensional latent space. The main challenge of this idea is that a decoder with too many parameters is required. This work designs a decoder with typical structure and shares a part of weights in the decoder to reduce the number of the required parameters. Besides, this work has introduced ensemble learning to work with the proposed approach for improving performance. The results show that the proposed approach is witnessed by the superior performance over the Omniglot classification and the miniImageNet classification tasks.
The Good, the Bad and the Ugly: Evaluating Convolutional Neural Networks for Prohibited Item Detection Using Real and Synthetically Composited X-ray Imagery
Venue: arXiv cs.CV 2019
Year: 2019

Detecting prohibited items in X-ray security imagery is pivotal in maintaining border and transport security against a wide range of threat profiles. Convolutional Neural Networks (CNN) with the support of a significant volume of data have brought advancement in such automated prohibited object detection and classification. However, collating such large volumes of X-ray security imagery remains a significant challenge. This work opens up the possibility of using synthetically composed imagery, avoiding the need to collate such large volumes of hand-annotated real-world imagery. Here we investigate the difference in detection performance achieved using real and synthetic X-ray training imagery for CNN architecture detecting three exemplar prohibited items, {Firearm, Firearm Parts, Knives}, within cluttered and complex X-ray security baggage imagery. We achieve 0.88 of mean average precision (mAP) with a Faster R-CNN and ResNet-101 CNN architecture for this 3-class object detection using real X-ray imagery. While the performance is comparable with synthetically composited X-ray imagery (0.78 mAP), our extended evaluation demonstrates both challenge and promise of using synthetically composed images to diversify the X-ray security training imagery for automated detection algorithm training.
A Self-consistent-field Iteration for Orthogonal Canonical Correlation Analysis
Venue: arXiv cs.LG 2019
Year: 2019

We propose an efficient algorithm for solving orthogonal canonical correlation analysis (OCCA) in the form of trace-fractional structure and orthogonal linear projections. Even though orthogonality has been widely used and proved to be a useful criterion for pattern recognition and feature extraction, existing methods for solving OCCA problem are either numerical unstable by relying on a deflation scheme, or less efficient by directly using generic optimization methods. In this paper, we propose an alternating numerical scheme whose core is the sub-maximization problem in the trace-fractional form with an orthogonal constraint. A customized self-consistent-field (SCF) iteration for this sub-maximization problem is devised. It is proved that the SCF iteration is globally convergent to a KKT point and that the alternating numerical scheme always converges. We further formulate a new trace-fractional maximization problem for orthogonal multiset CCA (OMCCA) and then propose an efficient algorithm with an either Jacobi-style or Gauss-Seidel-style updating scheme based on the same SCF iteration. Extensive experiments are conducted to evaluate the proposed algorithms against existing methods including two real world applications: multi-label classification and multi-view feature extraction. Experimental results show that our methods not only perform competitively to or better than baselines but also are more efficient.
Hotelling Games with Random Tolerance Intervals
Venue: arXiv cs.GT 2019
Year: 2019

The classical Hotelling game is played on a line segment whose points represent uniformly distributed clients. The $n$ players of the game are servers who need to place themselves on the line segment, and once this is done, each client gets served by the player closest to it. The goal of each player is to choose its location so as to maximize the number of clients it attracts. In this paper we study a variant of the Hotelling game where each client $v$ has a tolerance interval, randomly distributed according to some density function $f$, and $v$ gets served by the nearest among the players eligible for it, namely, those that fall within its interval. (If no such player exists, then $v$ abstains.) It turns out that this modification significantly changes the behavior of the game and its states of equilibria. In particular, it may serve to explain why players sometimes prefer to "spread out", rather than to cluster together as dictated by the classical Hotelling game. We consider two variants of the game: symmetric games, where clients have the same tolerance range to their left and right, and asymmetric games, where the left and right ranges of each client are determined independently of each other. We fully characterize the Nash equilibria of the 2-player game. For at least 3 players, we characterize a specific class of strategy profiles, referred to as canonical profiles, and show that these profiles are the only ones that may yield Nash equilibria in our game. Moreover, the canonical profile, if exists, is uniquely defined for every $n$ and $f$. In both the symmetric and asymmetric setting, we give necessary and sufficient conditions for the canonical profile to be a Nash equilibrium, and demonstrate their application for several distributions.
20 Years of Evolution from Cognitive to Intelligent Communications
Venue: arXiv cs.NI 2019
Year: 2019

It has been 20 years since the concept of cognitive radio (CR) was proposed, which is an efficient approach to provide more access opportunities to connect massive wireless devices. To improve the spectrum efficiency, CR enables unlicensed usage of licensed spectrum resources. It has been regarded as the key enabler for intelligent communications. In this article, we will provide an overview on the intelligent communication in the past two decades to illustrate the revolution of its capability from cognition to artificial intelligence (AI). Particularly, this article starts from a comprehensive review of typical spectrum sensing and sharing, followed by the recent achievements on the AI-enabled intelligent radio. Moreover, research challenges in the future intelligent communications will be discussed to show a path to the real deployment of intelligent radio. After witnessing the glorious developments of CR in the past 20 years, we try to provide readers a clear picture on how intelligent radio could be further developed to smartly utilize the limited spectrum resources as well as to optimally configure wireless devices in the future communication systems.
Internal Dictionary Matching
Venue: arXiv cs.DS 2019
Year: 2019

We introduce data structures answering queries concerning the occurrences of patterns from a given dictionary $\mathcal{D}$ in fragments of a given string $T$ of length $n$. The dictionary is internal in the sense that each pattern in $\mathcal{D}$ is given as a fragment of $T$. This way, $\mathcal{D}$ takes space proportional to the number of patterns $d=|\mathcal{D}|$ rather than their total length, which could be $Θ(n\cdot d)$. In particular, we consider the following types of queries: reporting and counting all occurrences of patterns from $\mathcal{D}$ in a fragment $T[i..j]$ and reporting distinct patterns from $\mathcal{D}$ that occur in $T[i..j]$. We show how to construct, in $\mathcal{O}((n+d) \log^{\mathcal{O}(1)} n)$ time, a data structure that answers each of these queries in time $\mathcal{O}(\log^{\mathcal{O}(1)} n+|output|)$. The case of counting patterns is much more involved and needs a combination of a locally consistent parsing with orthogonal range searching. Reporting distinct patterns, on the other hand, uses the structure of maximal repetitions in strings. Finally, we provide tight---up to subpolynomial factors---upper and lower bounds for the case of a dynamic dictionary.
The Power of Communities: A Text Classification Model with Automated Labeling Process Using Network Community Detection
Venue: arXiv cs.CL 2019
Year: 2019

Text classification is one of the most critical areas in machine learning and artificial intelligence research. It has been actively adopted in many business applications such as conversational intelligence systems, news articles categorizations, sentiment analysis, emotion detection systems, and many other recommendation systems in our daily life. One of the problems in supervised text classification models is that the models' performance depends heavily on the quality of data labeling that is typically done by humans. In this study, we propose a new network community detection-based approach to automatically label and classify text data into multiclass value spaces. Specifically, we build networks with sentences as the network nodes and pairwise cosine similarities between the Term Frequency-Inversed Document Frequency (TFIDF) vector representations of the sentences as the network link weights. We use the Louvain method to detect the communities in the sentence networks. We train and test the Support Vector Machine and the Random Forest models on both the human-labeled data and network community detection labeled data. Results showed that models with the data labeled by the network community detection outperformed the models with the human-labeled data by 2.68-3.75% of classification accuracy. Our method may help developments of more accurate conversational intelligence and other text classification systems.
Extending the Message Passing Interface (MPI) with User-Level Schedules
Venue: arXiv cs.DC 2019
Year: 2019

Composability is one of seven reasons for the long-standing and continuing success of MPI. Extending MPI by composing its operations with user-level operations provides useful integration with the progress engine and completion notification methods of MPI. However, the existing extensibility mechanism in MPI (generalized requests) is not widely utilized and has significant drawbacks. MPI can be generalized via scheduled communication primitives, for example, by utilizing implementation techniques from existing MPI-3 nonblocking collectives and from forthcoming MPI-4 persistent and partitioned APIs. Non-trivial schedules are used internally in some MPI libraries; but, they are not accessible to end-users. Message-based communication patterns can be built as libraries on top of MPI. Such libraries can have comparable implementation maturity and potentially higher performance than MPI library code, but do not require intimate knowledge of the MPI implementation. Libraries can provide performance-portable interfaces that cross MPI implementation boundaries. The ability to compose additional user-defined operations using the same progress engine benefits all kinds of general purpose HPC libraries. We propose a definition for MPI schedules: a user-level programming model suitable for creating persistent collective communication composed with new application-specific sequences of user-defined operations managed by MPI and fully integrated with MPI progress and completion notification. The API proposed offers a path to standardization for extensible communication schedules involving user-defined operations. Our approach has the potential to introduce event-driven programming into MPI (beyond the tools interface), although connecting schedules with events comprises future work. Early performance results described here are promising and indicate strong overlap potential.
Optimal-Rate Characterisation for Pliable Index Coding using Absent Receivers
Venue: arXiv cs.IT 2019
Year: 2019

We characterise the optimal broadcast rate for a few classes of pliable-index-coding problems. This is achieved by devising new lower bounds that utilise the set of absent receivers to construct decoding chains with skipped messages. This work complements existing works by considering problems that are not complete-S, i.e., problems considered in this work do not require that all receivers with a certain side-information cardinality to be either present or absent from the problem. We show that for a certain class, the set of receivers is critical in the sense that adding any receiver strictly increases the broadcast rate.
Improving the Intelligibility of Electric and Acoustic Stimulation Speech Using Fully Convolutional Networks Based Speech Enhancement
Venue: arXiv cs.SD 2019
Year: 2019

The combined electric and acoustic stimulation (EAS) has demonstrated better speech recognition than conventional cochlear implant (CI) and yielded satisfactory performance under quiet conditions. However, when noise signals are involved, both the electric signal and the acoustic signal may be distorted, thereby resulting in poor recognition performance. To suppress noise effects, speech enhancement (SE) is a necessary unit in EAS devices. Recently, a time-domain speech enhancement algorithm based on the fully convolutional neural networks (FCN) with a short-time objective intelligibility (STOI)-based objective function (termed FCN(S) in short) has received increasing attention due to its simple structure and effectiveness of restoring clean speech signals from noisy counterparts. With evidence showing the benefits of FCN(S) for normal speech, this study sets out to assess its ability to improve the intelligibility of EAS simulated speech. Objective evaluations and listening tests were conducted to examine the performance of FCN(S) in improving the speech intelligibility of normal and vocoded speech in noisy environments. The experimental results show that, compared with the traditional minimum-mean square-error SE method and the deep denoising autoencoder SE method, FCN(S) can obtain better gain in the speech intelligibility for normal as well as vocoded speech. This study, being the first to evaluate deep learning SE approaches for EAS, confirms that FCN(S) is an effective SE approach that may potentially be integrated into an EAS processor to benefit users in noisy environments.
Approximation Algorithms for Scheduling with Class Constraints
Venue: arXiv cs.DS 2019
Year: 2019

Assigning jobs onto identical machines with the objective to minimize the maximal load is one of the most basic problems in combinatorial optimization. Motivated by product planing and data placement, we study a natural extension called Class Constrainted Scheduling (CCS). In this problem, each job additionally belongs to a class and each machine can only schedule jobs from at most $c$ different classes. Even though this problem is closely related to the Class Constraint Bin Packing, the Class Constraint Knapsack and the Cardinality Constraint variants, CCS lacks results regarding approximation algorithms, even though it is also well-known to be NP-hard. We fill this gap by analyzing the problem considering three different ways to feasibly allot the jobs: The splittable case, where we can split and allot the jobs arbitrarily; the preemptive case, where jobs pieces belonging to the same job are not allowed to be scheduled in parallel; and finally the non-preemptive case, where no splitting is allowed at all. For each case we introduce the first PTAS where neither $c$ nor the number of all classes have to be a constant. In order to achieve this goal, we give new insights about the structure of optimal solutions. This allows us to preprocess the instance appropriately and by additionally grouping variables to set up a configuration Integer Linear Program (ILP) with N-fold structure. This N-fold structure allows us to solve the ILP efficiently. Further we developed the first simple approximation algorithms with a constant approximation ratio running in strongly polynomial time. The splittable and the preemptive case admit algorithms with ratio $2$ and a running time of $O(n^2 \log(n))$. The algorithm for the non-preemptive case has a ratio of $7/3$ and a running time of $O(n^2 \log^2(n))$. All results even hold if the number of machines cannot be bounded by a polynomial in $n$.
Selecting Artificially-Generated Sentences for Fine-Tuning Neural Machine Translation
Venue: arXiv cs.CL 2019
Year: 2019

Neural Machine Translation (NMT) models tend to achieve best performance when larger sets of parallel sentences are provided for training. For this reason, augmenting the training set with artificially-generated sentence pairs can boost performance. Nonetheless, the performance can also be improved with a small number of sentences if they are in the same domain as the test set. Accordingly, we want to explore the use of artificially-generated sentences along with data-selection algorithms to improve German-to-English NMT models trained solely with authentic data. In this work, we show how artificially-generated sentences can be more beneficial than authentic pairs, and demonstrate their advantages when used in combination with data-selection algorithms.
How does object fatness impact the complexity of packing in d dimensions?
Venue: arXiv cs.CG 2019
Year: 2019

Packing is a classical problem where one is given a set of subsets of Euclidean space called objects, and the goal is to find a maximum size subset of objects that are pairwise non-intersecting. The problem is also known as the Independent Set problem on the intersection graph defined by the objects. Although the problem is NP-complete, there are several subexponential algorithms in the literature. One of the key assumptions of such algorithms has been that the objects are fat, with a few exceptions in two dimensions; for example, the packing problem of a set of polygons in the plane surprisingly admits a subexponential algorithm. In this paper we give tight running time bounds for packing similarly-sized non-fat objects in higher dimensions. We propose an alternative and very weak measure of fatness called the stabbing number, and show that the packing problem in Euclidean space of constant dimension $d \geq 3$ for a family of similarly sized objects with stabbing number $α$ can be solved in $2^{O(n^{1-1/d}α)}$ time. We prove that even in the case of axis-parallel boxes of fixed shape, there is no $2^{o(n^{1-1/d}α)}$ algorithm under ETH. This result smoothly bridges the whole range of having constant-fat objects on one extreme ($α=1$) and a subexponential algorithm of the usual running time, and having very "skinny" objects on the other extreme ($α=n^{1/d}$), where we cannot hope to improve upon the brute force running time of $2^{O(n)}$, and thereby characterizes the impact of fatness on the complexity of packing in case of similarly sized objects. We also study the same problem when parameterized by the solution size $k$, and give a $n^{O(k^{1-1/d}α)}$ algorithm, with an almost matching lower bound.
GradVis: Visualization and Second Order Analysis of Optimization Surfaces during the Training of Deep Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Current training methods for deep neural networks boil down to very high dimensional and non-convex optimization problems which are usually solved by a wide range of stochastic gradient descent methods. While these approaches tend to work in practice, there are still many gaps in the theoretical understanding of key aspects like convergence and generalization guarantees, which are induced by the properties of the optimization surface (loss landscape). In order to gain deeper insights, a number of recent publications proposed methods to visualize and analyze the optimization surfaces. However, the computational cost of these methods are very high, making it hardly possible to use them on larger networks. In this paper, we present the GradVis Toolbox, an open source library for efficient and scalable visualization and analysis of deep neural network loss landscapes in Tensorflow and PyTorch. Introducing more efficient mathematical formulations and a novel parallelization scheme, GradVis allows to plot 2d and 3d projections of optimization surfaces and trajectories, as well as high resolution second order gradient information for large networks.
Two-stage Image Classification Supervised by a Single Teacher Single Student Model
Venue: arXiv cs.CV 2019
Year: 2019

The two-stage strategy has been widely used in image classification. However, these methods barely take the classification criteria of the first stage into consideration in the second prediction stage. In this paper, we propose a novel two-stage representation method (TSR), and convert it to a Single-Teacher Single-Student (STSS) problem in our two-stage image classification framework. We seek the nearest neighbours of the test sample to choose candidate target classes. Meanwhile, the first stage classifier is formulated as the teacher, which holds the classification scores. The samples of the candidate classes are utilized to learn a student classifier based on L2-minimization in the second stage. The student will be supervised by the teacher classifier, which approves the student only if it obtains a higher score. In actuality, the proposed framework generates a stronger classifier by staging two weaker classifiers in a novel way. The experiments conducted on several face and object databases show that our proposed framework is effective and outperforms multiple popular classification methods.
Autoencoder-Based Error Correction Coding for One-Bit Quantization
Venue: arXiv cs.IT 2019
Year: 2019

This paper proposes a novel deep learning-based error correction coding scheme for AWGN channels under the constraint of one-bit quantization in the receivers. Specifically, it is first shown that the optimum error correction code that minimizes the probability of bit error can be obtained by perfectly training a special autoencoder, in which "perfectly" refers to converging the global minima. However, perfect training is not possible in most cases. To approach the performance of a perfectly trained autoencoder with a suboptimum training, we propose utilizing turbo codes as an implicit regularization, i.e., using a concatenation of a turbo code and an autoencoder. It is empirically shown that this design gives nearly the same performance as to the hypothetically perfectly trained autoencoder, and we also provide a theoretical proof of why that is so. The proposed coding method is as bandwidth efficient as the integrated (outer) turbo code, since the autoencoder exploits the excess bandwidth from pulse shaping and packs signals more intelligently thanks to sparsity in neural networks. Our results show that the proposed coding scheme at finite block lengths outperforms conventional turbo codes even for QPSK modulation. Furthermore, the proposed coding method can make one-bit quantization operational even for 16-QAM.