OpenRaiser/Intern-Atlas huggingface dataset:
An Empirical Study on Regularization of Deep Neural Networks by Local Rademacher Complexity
Venue: arXiv cs.LG 2019
Year: 2019

Regularization of Deep Neural Networks (DNNs) for the sake of improving their generalization capability is important and challenging. The development in this line benefits theoretical foundation of DNNs and promotes their usability in different areas of artificial intelligence. In this paper, we investigate the role of Rademacher complexity in improving generalization of DNNs and propose a novel regularizer rooted in Local Rademacher Complexity (LRC). While Rademacher complexity is well known as a distribution-free complexity measure of function class that help boost generalization of statistical learning methods, extensive study shows that LRC, its counterpart focusing on a restricted function class, leads to sharper convergence rates and potential better generalization given finite training sample. Our LRC based regularizer is developed by estimating the complexity of the function class centered at the minimizer of the empirical loss of DNNs. Experiments on various types of network architecture demonstrate the effectiveness of LRC regularization in improving generalization. Moreover, our method features the state-of-the-art result on the CIFAR-$10$ dataset with network architecture found by neural architecture search.
Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions
Venue: arXiv cs.LG 2019
Year: 2019

Stochastic gradient descent (SGD) is a popular and efficient method with wide applications in training deep neural nets and other nonconvex models. While the behavior of SGD is well understood in the convex learning setting, the existing theoretical results for SGD applied to nonconvex objective functions are far from mature. For example, existing results require to impose a nontrivial assumption on the uniform boundedness of gradients for all iterates encountered in the learning process, which is hard to verify in practical implementations. In this paper, we establish a rigorous theoretical foundation for SGD in nonconvex learning by showing that this boundedness assumption can be removed without affecting convergence rates. In particular, we establish sufficient conditions for almost sure convergence as well as optimal convergence rates for SGD applied to both general nonconvex objective functions and gradient-dominated objective functions. A linear convergence is further derived in the case with zero variances.
A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
Venue: arXiv cs.LG 2019
Year: 2019

We propose the first contextual bandit algorithm that is parameter-free, efficient, and optimal in terms of dynamic regret. Specifically, our algorithm achieves dynamic regret $\mathcal{O}(\min\{\sqrt{ST}, Δ^{\frac{1}{3}}T^{\frac{2}{3}}\})$ for a contextual bandit problem with $T$ rounds, $S$ switches and $Δ$ total variation in data distributions. Importantly, our algorithm is adaptive and does not need to know $S$ or $Δ$ ahead of time, and can be implemented efficiently assuming access to an ERM oracle. Our results strictly improve the $\mathcal{O}(\min \{S^{\frac{1}{4}}T^{\frac{3}{4}}, Δ^{\frac{1}{5}}T^{\frac{4}{5}}\})$ bound of (Luo et al., 2018), and greatly generalize and improve the $\mathcal{O}(\sqrt{ST})$ result of (Auer et al, 2018) that holds only for the two-armed bandit problem without contextual information. The key novelty of our algorithm is to introduce replay phases, in which the algorithm acts according to its previous decisions for a certain amount of time in order to detect non-stationarity while maintaining a good balance between exploration and exploitation.
Improving Question Answering with External Knowledge
Venue: arXiv cs.CL 2019
Year: 2019

We focus on multiple-choice question answering (QA) tasks in subject areas such as science, where we require both broad background knowledge and the facts from the given subject-area reference corpus. In this work, we explore simple yet effective methods for exploiting two sources of external knowledge for subject-area QA. The first enriches the original subject-area reference corpus with relevant text snippets extracted from an open-domain resource (i.e., Wikipedia) that cover potentially ambiguous concepts in the question and answer options. As in other QA research, the second method simply increases the amount of training data by appending additional in-domain subject-area instances. Experiments on three challenging multiple-choice science QA tasks (i.e., ARC-Easy, ARC-Challenge, and OpenBookQA) demonstrate the effectiveness of our methods: in comparison to the previous state-of-the-art, we obtain absolute gains in accuracy of up to 8.1%, 13.0%, and 12.8%, respectively. While we observe consistent gains when we introduce knowledge from Wikipedia, we find that employing additional QA training instances is not uniformly helpful: performance degrades when the added instances exhibit a higher level of difficulty than the original training data. As one of the first studies on exploiting unstructured external knowledge for subject-area QA, we hope our methods, observations, and discussion of the exposed limitations may shed light on further developments in the area.
Ranking Episodes using a Partition Model
Venue: arXiv cs.DS 2019
Year: 2019

One of the biggest setbacks in traditional frequent pattern mining is that overwhelmingly many of the discovered patterns are redundant. A prototypical example of such redundancy is a freerider pattern where the pattern contains a true pattern and some additional noise events. A technique for filtering freerider patterns that has proved to be efficient in ranking itemsets is to use a partition model where a pattern is divided into two subpatterns and the observed support is compared to the expected support under the assumption that these two subpatterns occur independently. In this paper we develop a partition model for episodes, patterns discovered from sequential data. An episode is essentially a set of events, with possible restrictions on the order of events. Unlike with itemset mining, computing the expected support of an episode requires surprisingly sophisticated methods. In order to construct the model, we partition the episode into two subepisodes. We then model how likely the events in each subepisode occur close to each other. If this probability is high---which is often the case if the subepisode has a high support---then we can expect that when one event from a subepisode occurs, then the remaining events occur also close by. This approach increases the expected support of the episode, and if this increase explains the observed support, then we can deem the episode uninteresting. We demonstrate in our experiments that using the partition model can effectively and efficiently reduce the redundancy in episodes.
Online Multiclass Classification Based on Prediction Margin for Partial Feedback
Venue: arXiv cs.LG 2019
Year: 2019

We consider the problem of online multiclass classification with partial feedback, where an algorithm predicts a class for a new instance in each round and only receives its correctness. Although several methods have been developed for this problem, recent challenging real-world applications require further performance improvement. In this paper, we propose a novel online learning algorithm inspired by recent work on learning from complementary labels, where a complementary label indicates a class to which an instance does not belong. This allows us to handle partial feedback deterministically in a margin-based way, where the prediction margin has been recognized as a key to superior empirical performance. We provide a theoretical guarantee based on a cumulative loss bound and experimentally demonstrate that our method outperforms existing methods which are non-margin-based and stochastic.
Robust Environmental Sound Recognition with Sparse Key-point Encoding and Efficient Multi-spike Learning
Venue: arXiv cs.NE 2019
Year: 2019

The capability for environmental sound recognition (ESR) can determine the fitness of individuals in a way to avoid dangers or pursue opportunities when critical sound events occur. It still remains mysterious about the fundamental principles of biological systems that result in such a remarkable ability. Additionally, the practical importance of ESR has attracted an increasing amount of research attention, but the chaotic and non-stationary difficulties continue to make it a challenging task. In this study, we propose a spike-based framework from a more brain-like perspective for the ESR task. Our framework is a unifying system with a consistent integration of three major functional parts which are sparse encoding, efficient learning and robust readout. We first introduce a simple sparse encoding where key-points are used for feature representation, and demonstrate its generalization to both spike and non-spike based systems. Then, we evaluate the learning properties of different learning rules in details with our contributions being added for improvements. Our results highlight the advantages of the multi-spike learning, providing a selection reference for various spike-based developments. Finally, we combine the multi-spike readout with the other parts to form a system for ESR. Experimental results show that our framework performs the best as compared to other baseline approaches. In addition, we show that our spike-based framework has several advantageous characteristics including early decision making, small dataset acquiring and ongoing dynamic processing. Our framework is the first attempt to apply the multi-spike characteristic of nervous neurons to ESR. The outstanding performance of our approach would potentially contribute to draw more research efforts to push the boundaries of spike-based paradigm to a new horizon.
Dynamic Epistemic Logic with Communication Actions
Venue: arXiv cs.LO 2019
Year: 2019

This work proposes a Dynamic Epistemic Logic with Communication Actions that can be performed concurrently. Unlike Concurrent Epistemic Action Logic introduced by Ditmarsch, Hoek and Kooi, where the concurrency mechanism is the so called true concurrency, here we use an approach based on process calculus, like CCS and CSP, and Action Models Logic. Our approach makes possible the proof of soundness, completeness and decidability, different from the others approaches. We present an axiomatization and show that the proof of soundness, completeness and decidability can be done using a reduction method.
Real-Time Steganalysis for Stream Media Based on Multi-channel Convolutional Sliding Windows
Venue: arXiv cs.MM 2019
Year: 2019

Previous VoIP steganalysis methods face great challenges in detecting speech signals at low embedding rates, and they are also generally difficult to perform real-time detection, making them hard to truly maintain cyberspace security. To solve these two challenges, in this paper, combined with the sliding window detection algorithm and Convolution Neural Network we propose a real-time VoIP steganalysis method which based on multi-channel convolution sliding windows. In order to analyze the correlations between frames and different neighborhood frames in a VoIP signal, we define multi channel sliding detection windows. Within each sliding window, we design two feature extraction channels which contain multiple convolution layers with multiple convolution kernels each layer to extract correlation features of the input signal. Then based on these extracted features, we use a forward fully connected network for feature fusion. Finally, by analyzing the statistical distribution of these features, the discriminator will determine whether the input speech signal contains covert information or not.We designed several experiments to test the proposed model's detection ability under various conditions, including different embedding rates, different speech length, etc. Experimental results showed that the proposed model outperforms all the previous methods, especially in the case of low embedding rate, which showed state-of-the-art performance. In addition, we also tested the detection efficiency of the proposed model, and the results showed that it can achieve almost real-time detection of VoIP speech signals.
TrackNet: Simultaneous Object Detection and Tracking and Its Application in Traffic Video Analysis
Venue: arXiv cs.CV 2019
Year: 2019

Object detection and object tracking are usually treated as two separate processes. Significant progress has been made for object detection in 2D images using deep learning networks. The usual tracking-by-detection pipeline for object tracking requires that the object is successfully detected in the first frame and all subsequent frames, and tracking is done by associating detection results. Performing object detection and object tracking through a single network remains a challenging open question. We propose a novel network structure named trackNet that can directly detect a 3D tube enclosing a moving object in a video segment by extending the faster R-CNN framework. A Tube Proposal Network (TPN) inside the trackNet is proposed to predict the objectness of each candidate tube and location parameters specifying the bounding tube. The proposed framework is applicable for detecting and tracking any object and in this paper, we focus on its application for traffic video analysis. The proposed model is trained and tested on UA-DETRAC, a large traffic video dataset available for multi-vehicle detection and tracking, and obtained very promising results.
HAHE: Hierarchical Attentive Heterogeneous Information Network Embedding
Venue: arXiv cs.SI 2019
Year: 2019

Heterogeneous information network (HIN) embedding has recently attracted much attention due to its effectiveness in dealing with the complex heterogeneous data. Meta path, which connects different object types with various semantic meanings, is widely used by existing HIN embedding works. However, several challenges have not been addressed so far. First, different meta paths convey different semantic meanings, while existing works assume that all nodes share same weights for meta paths and ignore the personalized preferences of different nodes on different meta paths. Second, given a meta path, nodes in HIN are connected by path instances while existing works fail to fully explore the differences between path instances that reflect nodes' preferences in the semantic space. rTo tackle the above challenges, we propose aHierarchical Attentive Heterogeneous information network Embedding (HAHE) model to capture the personalized preferences on meta paths and path instances in each semantic space. As path instances are based on a particular meta path, a hierarchical attention mechanism is naturally utilized to model the personalized preference on meta paths and path instances. Extensive experiments on several real-world datasets show that our proposed \model model significantly outperforms the state-of-the-art methods in terms of various data mining tasks.
What is the dimension of your binary data?
Venue: arXiv cs.LG 2019
Year: 2019

Many 0/1 datasets have a very large number of variables; on the other hand, they are sparse and the dependency structure of the variables is simpler than the number of variables would suggest. Defining the effective dimensionality of such a dataset is a nontrivial problem. We consider the problem of defining a robust measure of dimension for 0/1 datasets, and show that the basic idea of fractal dimension can be adapted for binary data. However, as such the fractal dimension is difficult to interpret. Hence we introduce the concept of normalized fractal dimension. For a dataset $D$, its normalized fractal dimension is the number of columns in a dataset $D'$ with independent columns and having the same (unnormalized) fractal dimension as $D$. The normalized fractal dimension measures the degree of dependency structure of the data. We study the properties of the normalized fractal dimension and discuss its computation. We give empirical results on the normalized fractal dimension, comparing it against baseline measures such as PCA. We also study the relationship of the dimension of the whole dataset and the dimensions of subgroups formed by clustering. The results indicate interesting differences between and within datasets.
Confusion matrices and rough set data analysis
Venue: arXiv cs.LG 2019
Year: 2019

A widespread approach in machine learning to evaluate the quality of a classifier is to cross -- classify predicted and actual decision classes in a confusion matrix, also called error matrix. A classification tool which does not assume distributional parameters but only information contained in the data is based on the rough set data model which assumes that knowledge is given only up to a certain granularity. Using this assumption and the technique of confusion matrices, we define various indices and classifiers based on rough confusion matrices.
Window-based Streaming Graph Partitioning Algorithm
Venue: arXiv cs.DS 2019
Year: 2019

In the recent years, the scale of graph datasets has increased to such a degree that a single machine is not capable of efficiently processing large graphs. Thereby, efficient graph partitioning is necessary for those large graph applications. Traditional graph partitioning generally loads the whole graph data into the memory before performing partitioning; this is not only a time consuming task but it also creates memory bottlenecks. These issues of memory limitation and enormous time complexity can be resolved using stream-based graph partitioning. A streaming graph partitioning algorithm reads vertices once and assigns that vertex to a partition accordingly. This is also called an one-pass algorithm. This paper proposes an efficient window-based streaming graph partitioning algorithm called WStream. The WStream algorithm is an edge-cut partitioning algorithm, which distributes a vertex among the partitions. Our results suggest that the WStream algorithm is able to partition large graph data efficiently while keeping the load balanced across different partitions, and communication to a minimum. Evaluation results with real workloads also prove the effectiveness of our proposed algorithm, and it achieves a significant reduction in load imbalance and edge-cut with different ranges of dataset.
Total stochastic gradient algorithms and applications in reinforcement learning
Venue: arXiv cs.LG 2019
Year: 2019

Backpropagation and the chain rule of derivatives have been prominent; however, the total derivative rule has not enjoyed the same amount of attention. In this work we show how the total derivative rule leads to an intuitive visual framework for creating gradient estimators on graphical models. In particular, previous "policy gradient theorems" are easily derived. We derive new gradient estimators based on density estimation, as well as a likelihood ratio gradient, which "jumps" to an intermediate node, not directly to the objective function. We evaluate our methods on model-based policy gradient algorithms, achieve good performance, and present evidence towards demystifying the success of the popular PILCO algorithm.
Robust Regression via Online Feature Selection under Adversarial Data Corruption
Venue: arXiv cs.LG 2019
Year: 2019

The presence of data corruption in user-generated streaming data, such as social media, motivates a new fundamental problem that learns reliable regression coefficient when features are not accessible entirely at one time. Until now, several important challenges still cannot be handled concurrently: 1) corrupted data estimation when only partial features are accessible; 2) online feature selection when data contains adversarial corruption; and 3) scaling to a massive dataset. This paper proposes a novel RObust regression algorithm via Online Feature Selection (\textit{RoOFS}) that concurrently addresses all the above challenges. Specifically, the algorithm iteratively updates the regression coefficients and the uncorrupted set via a robust online feature substitution method. We also prove that our algorithm has a restricted error bound compared to the optimal solution. Extensive empirical experiments in both synthetic and real-world datasets demonstrated that the effectiveness of our new method is superior to that of existing methods in the recovery of both feature selection and regression coefficients, with very competitive efficiency.
Exploiting NOMA for UAV Communications in Large-Scale Cellular Networks
Venue: arXiv cs.IT 2019
Year: 2019

This paper advocates a pair of strategies in non-orthogonal multiple access (NOMA) in unmanned aerial vehicles (UAVs) communications, where multiple UAVs play as new aerial communications platforms for serving terrestrial NOMA users. A new multiple UAVs framework with invoking stochastic geometry technique is proposed, in which a pair of practical strategies are considered: 1) the UAV-centric strategy for offloading actions and 2) the user-centric strategy for providing emergency communications. In order to provide practical insights for the proposed NOMA assisted UAV framework, an imperfect successive interference cancelation (ipSIC) scenario is taken into account. For both UAV-centric strategy and user-centric strategy, we derive new exact expressions for the coverage probability. We also derive new analytical results for orthogonal multiple access (OMA) for providing a benchmark scheme. The derived analytical results in both user-centric strategy and UAV-centric strategy explicitly indicate that the ipSIC coefficient is a dominant component in terms of coverage probability. Numerical results are provided to confirm that i) for both user-centric strategy and UAV-centric strategy, NOMA assisted UAV cellular networks is capable of outperforming OMA by setting power allocation factors and targeted rate properly; and ii) the coverage probability of NOMA assisted UAV cellular framework is affected to a large extent by ipSIC coefficient, target rates and power allocations factors of paired NOMA users.
MIMO Capacity with Average Total and Per-Antenna Power Constraints
Venue: arXiv cs.IT 2019
Year: 2019

MIMO capacity with a joint total and per-antenna average power constraint is considered in this work. The problem arises when, besides having a limited available power at the transmitter, also the individual antennas cannot radiate power beyond the limits of their corresponding RF chains. Closed-form results are illustrated in specific cases and, in particular, in the unit-rank channel matrix case. Lower-complexity optimization problems are derived for the other cases. Numerical complexity is derived in terms of the number of equivalent real variables for the optimization problem and a general formula is provided depending on the channel matrix rank. Numerical results are included to validate and illustrate the application of the proposed optimization algorithms and also to evaluate the time complexity of its implementation.