OpenRaiser/Intern-Atlas huggingface dataset:
Diffusion Maps for Textual Network Embedding
Venue: arXiv cs.CL 2019
Year: 2019

Textual network embedding leverages rich text information associated with the network to learn low-dimensional vectorial representations of vertices. Rather than using typical natural language processing (NLP) approaches, recent research exploits the relationship of texts on the same edge to graphically embed text. However, these models neglect to measure the complete level of connectivity between any two texts in the graph. We present diffusion maps for textual network embedding (DMTE), integrating global structural information of the graph to capture the semantic relatedness between texts, with a diffusion-convolution operation applied on the text inputs. In addition, a new objective function is designed to efficiently preserve the high-order proximity using the graph diffusion. Experimental results show that the proposed approach outperforms state-of-the-art methods on the vertex-classification and link-prediction tasks.
Learning to Propagate Labels: Transductive Propagation Network for Few-shot Learning
Venue: arXiv cs.LG 2019
Year: 2019

The goal of few-shot learning is to learn a classifier that generalizes well even when trained with a limited number of training instances per class. The recently introduced meta-learning approaches tackle this problem by learning a generic classifier across a large number of multiclass classification tasks and generalizing the model to a new task. Yet, even with such meta-learning, the low-data problem in the novel classification task still remains. In this paper, we propose Transductive Propagation Network (TPN), a novel meta-learning framework for transductive inference that classifies the entire test set at once to alleviate the low-data problem. Specifically, we propose to learn to propagate labels from labeled instances to unlabeled test instances, by learning a graph construction module that exploits the manifold structure in the data. TPN jointly learns both the parameters of feature embedding and the graph construction in an end-to-end manner. We validate TPN on multiple benchmark datasets, on which it largely outperforms existing few-shot learning approaches and achieves the state-of-the-art results.
Pathology Segmentation using Distributional Differences to Images of Healthy Origin
Venue: arXiv cs.CV 2019
Year: 2019

Fully supervised segmentation methods require a large training cohort of already segmented images, providing information at the pixel level of each image. We present a method to automatically segment and model pathologies in medical images, trained solely on data labelled on the image level as either healthy or containing a visual defect. We base our method on CycleGAN, an image-to-image translation technique, to translate images between the domains of healthy and pathological images. We extend the core idea with two key contributions. Implementing the generators as residual generators allows us to explicitly model the segmentation of the pathology. Realizing the translation from the healthy to the pathological domain using a variational autoencoder allows us to specify one representation of the pathology, as this transformation is otherwise not unique. Our model hence not only allows us to create pixelwise semantic segmentations, it is also able to create inpaintings for the segmentations to render the pathological image healthy. Furthermore, we can draw new unseen pathology samples from this model based on the distribution in the data. We show quantitatively, that our method is able to segment pathologies with a surprising accuracy being only slightly inferior to a state-of-the-art fully supervised method, although the latter has per-pixel rather than per-image training information. Moreover, we show qualitative results of both the segmentations and inpaintings. Our findings motivate further research into weakly-supervised segmentation using image level annotations, allowing for faster and cheaper acquisition of training data without a large sacrifice in segmentation accuracy.
Self-Net: Lifelong Learning via Continual Self-Modeling
Venue: arXiv cs.LG 2019
Year: 2019

Learning a set of tasks over time, also known as continual learning (CL), is one of the most challenging problems in artificial intelligence. While recent approaches achieve some degree of CL in deep neural networks, they either (1) grow the network parameters linearly with the number of tasks, (2) require storing training data from previous tasks, or (3) restrict the network's ability to learn new tasks. To address these issues, we propose a novel framework, Self-Net, that uses an autoencoder to learn a set of low-dimensional representations of the weights learned for different tasks. We demonstrate that these low-dimensional vectors can then be used to generate high-fidelity recollections of the original weights. Self-Net can incorporate new tasks over time with little retraining and with minimal loss in performance for older tasks. Our system does not require storing prior training data and its parameters grow only logarithmically with the number of tasks. We show that our technique outperforms current state-of-the-art approaches on numerous datasets---including continual versions of MNIST, CIFAR10, CIFAR100, and Atari---and we demonstrate that our method can achieve over 10X storage compression in a continual fashion. To the best of our knowledge, we are the first to use autoencoders to sequentially encode sets of network weights to enable continual learning.
A Survey of Utility-Oriented Pattern Mining
Venue: arXiv cs.DB 2019
Year: 2019

The main purpose of data mining and analytics is to find novel, potentially useful patterns that can be utilized in real-world applications to derive beneficial knowledge. For identifying and evaluating the usefulness of different kinds of patterns, many techniques and constraints have been proposed, such as support, confidence, sequence order, and utility parameters (e.g., weight, price, profit, quantity, satisfaction, etc.). In recent years, there has been an increasing demand for utility-oriented pattern mining (UPM, or called utility mining). UPM is a vital task, with numerous high-impact applications, including cross-marketing, e-commerce, finance, medical, and biomedical applications. This survey aims to provide a general, comprehensive, and structured overview of the state-of-the-art methods of UPM. First, we introduce an in-depth understanding of UPM, including concepts, examples, and comparisons with related concepts. A taxonomy of the most common and state-of-the-art approaches for mining different kinds of high-utility patterns is presented in detail, including Apriori-based, tree-based, projection-based, vertical-/horizontal-data-format-based, and other hybrid approaches. A comprehensive review of advanced topics of existing high-utility pattern mining techniques is offered, with a discussion of their pros and cons. Finally, we present several well-known open-source software packages for UPM. We conclude our survey with a discussion on open and practical challenges in this field.
Dynamic Network Model from Partial Observations
Venue: arXiv cs.LG 2019
Year: 2019

Can evolving networks be inferred and modeled without directly observing their nodes and edges? In many applications, the edges of a dynamic network might not be observed, but one can observe the dynamics of stochastic cascading processes (e.g., information diffusion, virus propagation) occurring over the unobserved network. While there have been efforts to infer networks based on such data, providing a generative probabilistic model that is able to identify the underlying time-varying network remains an open question. Here we consider the problem of inferring generative dynamic network models based on network cascade diffusion data. We propose a novel framework for providing a non-parametric dynamic network model--based on a mixture of coupled hierarchical Dirichlet processes-- based on data capturing cascade node infection times. Our approach allows us to infer the evolving community structure in networks and to obtain an explicit predictive distribution over the edges of the underlying network--including those that were not involved in transmission of any cascade, or are likely to appear in the future. We show the effectiveness of our approach using extensive experiments on synthetic as well as real-world networks.
Dual Policy Iteration
Venue: arXiv cs.LG 2019
Year: 2019

Recently, a novel class of Approximate Policy Iteration (API) algorithms have demonstrated impressive practical performance (e.g., ExIt from [2], AlphaGo-Zero from [27]). This new family of algorithms maintains, and alternately optimizes, two policies: a fast, reactive policy (e.g., a deep neural network) deployed at test time, and a slow, non-reactive policy (e.g., Tree Search), that can plan multiple steps ahead. The reactive policy is updated under supervision from the non-reactive policy, while the non-reactive policy is improved with guidance from the reactive policy. In this work we study this Dual Policy Iteration (DPI) strategy in an alternating optimization framework and provide a convergence analysis that extends existing API theory. We also develop a special instance of this framework which reduces the update of non-reactive policies to model-based optimal control using learned local models, and provides a theoretically sound way of unifying model-free and model-based RL approaches with unknown dynamics. We demonstrate the efficacy of our approach on various continuous control Markov Decision Processes.
Deep Trustworthy Knowledge Tracing
Venue: arXiv cs.AI 2019
Year: 2019

Knowledge tracing (KT), a key component of an intelligent tutoring system, is a machine learning technique that estimates the mastery level of a student based on his/her past performance. The objective of KT is to predict a student's response to the next question. Compared with traditional KT models, deep learning-based KT (DLKT) models show better predictive performance because of the representation power of deep neural networks. Various methods have been proposed to improve the performance of DLKT, but few studies have been conducted on the reliability of DLKT. In this work, we claim that the existing DLKTs are not reliable in real education environments. To substantiate the claim, we show limitations of DLKT from various perspectives such as knowledge state update failure, catastrophic forgetting, and non-interpretability. We then propose a novel regularization to address these problems. The proposed method allows us to achieve trustworthy DLKT. In addition, the proposed model which is trained on scenarios with forgetting can also be easily extended to scenarios without forgetting.
Adaptive neural network classifier for decoding MEG signals
Venue: arXiv cs.LG 2019
Year: 2019

Convolutional Neural Networks (CNN) outperform traditional classification methods in many domains. Recently these methods have gained attention in neuroscience and particularly in brain-computer interface (BCI) community. Here, we introduce a CNN optimized for classification of brain states from magnetoencephalographic (MEG) measurements. Our CNN design is based on a generative model of the electromagnetic (EEG and MEG) brain signals and is readily interpretable in neurophysiological terms. We show here that the proposed network is able to decode event-related responses as well as modulations of oscillatory brain activity and that it outperforms more complex neural networks and traditional classifiers used in the field. Importantly, the model is robust to inter-individual differences and can successfully generalize to new subjects in offline and online classification.
Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
Venue: arXiv cs.CC 2019
Year: 2019

The polynomial-time hierarchy ($\mathrm{PH}$) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as $\mathrm{PH}$ does not collapse). Here, we study whether two quantum generalizations of $\mathrm{PH}$ can similarly prove separations in the quantum setting. The first generalization, $\mathrm{QCPH}$, uses classical proofs, and the second, $\mathrm{QPH}$, uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, $\mathrm{Q} Σ_3$, into $\mathrm{NEXP}$ {using the Ellipsoid Method for efficiently solving semidefinite programs}. These results yield two implications for $\mathrm{QMA}(2)$, the variant of Quantum Merlin-Arthur ($\mathrm{QMA}$) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if $\mathrm{QCPH} = \mathrm{QPH}$ (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs "equivalent"), then $\mathrm{QMA}(2)$ is in the Counting Hierarchy (specifically, in $\mathrm{P}^{\mathrm{PP}^{\mathrm{PP}}}$). Second, unless $\mathrm{QMA}(2)={\mathrm{Q} Σ_3}$ (i.e., alternating quantifiers do not help in the presence of "unentanglement"), $\mathrm{QMA}(2)$ is strictly contained in $\mathrm{NEXP}$.
LSTMs Exploit Linguistic Attributes of Data
Venue: arXiv cs.CL 2019
Year: 2019

While recurrent neural networks have found success in a variety of natural language processing applications, they are general models of sequential data. We investigate how the properties of natural language data affect an LSTM's ability to learn a nonlinguistic task: recalling elements from its input. We find that models trained on natural language data are able to recall tokens from much longer sequences than models trained on non-language sequential data. Furthermore, we show that the LSTM learns to solve the memorization task by explicitly using a subset of its neurons to count timesteps in the input. We hypothesize that the patterns and structure in natural language data enable LSTMs to learn by providing approximate ways of reducing loss, but understanding the effect of different training data on the learnability of LSTMs remains an open question.
Android Malware Detection based on Factorization Machine
Venue: arXiv cs.CR 2019
Year: 2019

As the popularity of Android smart phones has increased in recent years, so too has the number of malicious applications. Due to the potential for data theft mobile phone users face, the detection of malware on Android devices has become an increasingly important issue in cyber security. Traditional methods like signature-based routines are unable to protect users from the ever-increasing sophistication and rapid behavior changes in new types of Android malware. Therefore, a great deal of effort has been made recently to use machine learning models and methods to characterize and generalize the malicious behavior patterns of mobile apps for malware detection. In this paper, we propose a novel and highly reliable classifier for Android Malware detection based on a Factorization Machine architecture and the extraction of Android app features from manifest files and source code. Our results indicate that the numerical feature representation of an app typically results in a long and highly sparse vector and that the interactions among different features are critical to revealing malicious behavior patterns. After performing an extensive performance evaluation, our proposed method achieved a test result of 100.00% precision score on the DREBIN dataset and 99.22% precision score with only 1.10% false positive rate on the AMD dataset. These metrics match the performance of state-of-the-art machine-learning-based Android malware detection methods and several commercial antivirus engines with the benefit of training up to 50 times faster.
Robustifying Models Against Adversarial Attacks by Langevin Dynamics
Venue: arXiv cs.LG 2019
Year: 2019

Adversarial attacks on deep learning models have compromised their performance considerably. As remedies, a lot of defense methods were proposed, which however, have been circumvented by newer attacking strategies. In the midst of this ensuing arms race, the problem of robustness against adversarial attacks still remains unsolved. This paper proposes a novel, simple yet effective defense strategy where adversarial samples are relaxed onto the underlying manifold of the (unknown) target class distribution. Specifically, our algorithm drives off-manifold adversarial samples towards high density regions of the data generating distribution of the target class by the Metroplis-adjusted Langevin algorithm (MALA) with perceptual boundary taken into account. Although the motivation is similar to projection methods, e.g., Defense-GAN, our algorithm, called MALA for DEfense (MALADE), is equipped with significant dispersion - projection is distributed broadly, and therefore any whitebox attack cannot accurately align the input so that the MALADE moves it to a targeted untrained spot where the model predicts a wrong label. In our experiments, MALADE exhibited state-of-the-art performance against various elaborate attacking strategies.
PIQUE: Progressive Integrated QUery Operator with Pay-As-You-Go Enrichment
Venue: arXiv cs.DB 2019
Year: 2019

Big data today in the form of text, images, video, and sensor data needs to be enriched (i.e., annotated with tags) prior to be effectively queried or analyzed. Data enrichment (that, depending upon the application could be compiled code, declarative queries, or expensive machine learning and/or signal processing techniques) often cannot be performed in its entirety as a pre-processing step at the time of data ingestion. Enriching data as a separate offline step after ingestion makes it unavailable for analysis during the period between the ingestion and enrichment. To bridge such a gap, this paper explores a novel approach that supports progressive data enrichment during query processing in order to support interactive exploratory analysis. Our approach is based on integrating an operator, entitled PIQUE, to support a prioritized execution of the enrichment functions during query processing. Query processing with the PIQUE operator significantly outperforms the baselines in terms of rate at which answer quality improves during query processing.
Neural Network Acceptability Judgments
Venue: arXiv cs.CL 2019
Year: 2019

This paper investigates the ability of artificial neural networks to judge the grammatical acceptability of a sentence, with the goal of testing their linguistic competence. We introduce the Corpus of Linguistic Acceptability (CoLA), a set of 10,657 English sentences labeled as grammatical or ungrammatical from published linguistics literature. As baselines, we train several recurrent neural network models on acceptability classification, and find that our models outperform unsupervised models by Lau et al (2016) on CoLA. Error-analysis on specific grammatical phenomena reveals that both Lau et al.'s models and ours learn systematic generalizations like subject-verb-object order. However, all models we test perform far below human level on a wide range of grammatical constructions.
Text normalization using memory augmented neural networks
Venue: arXiv cs.CL 2019
Year: 2019

We perform text normalization, i.e. the transformation of words from the written to the spoken form, using a memory augmented neural network. With the addition of dynamic memory access and storage mechanism, we present a neural architecture that will serve as a language-agnostic text normalization system while avoiding the kind of unacceptable errors made by the LSTM-based recurrent neural networks. By successfully reducing the frequency of such mistakes, we show that this novel architecture is indeed a better alternative. Our proposed system requires significantly lesser amounts of data, training time and compute resources. Additionally, we perform data up-sampling, circumventing the data sparsity problem in some semiotic classes, to show that sufficient examples in any particular class can improve the performance of our text normalization system. Although a few occurrences of these errors still remain in certain semiotic classes, we demonstrate that memory augmented networks with meta-learning capabilities can open many doors to a superior text normalization system.
The real tau-conjecture is true on average
Venue: arXiv cs.CC 2019
Year: 2019

Koiran's real $τ$-conjecture claims that the number of real zeros of a structured polynomial given as a sum of $m$ products of $k$ real sparse polynomials, each with at most $t$ monomials, is bounded by a polynomial in $m,k,t$. This conjecture has a major consequence in complexity theory since it would lead to superpolynomial bounds for the arithmetic circuit size of the permanent. We confirm the conjecture in a probabilistic sense by proving that if the coefficients involved in the description of $f$ are independent standard Gaussian random variables, then the expected number of real zeros of $f$ is $O(mk^2t)$.
On the Sub-Packetization Size and the Repair Bandwidth of Reed-Solomon Codes
Venue: arXiv cs.IT 2019
Year: 2019

Reed-Solomon (RS) codes are widely used in distributed storage systems. In this paper, we study the repair bandwidth and sub-packetization size of RS codes. The repair bandwidth is defined as the amount of transmitted information from surviving nodes to a failed node. The RS code can be viewed as a polynomial over a finite field $GF(q^\ell)$ evaluated at a set of points, where $\ell$ is called the sub-packetization size. Smaller bandwidth reduces the network traffic in distributed storage, and smaller $\ell$ facilitates the implementation of RS codes with lower complexity. Recently, Guruswami and Wootters proposed a repair method for RS codes when the evaluation points are the entire finite field. While the sub-packization size can be arbitrarily small, the repair bandwidth is higher than the minimum storage regenerating (MSR) bound. Tamo, Ye and Barg achieved the MSR bound but the sub-packetization size grows faster than the exponential function of the number of the evaluation points. In this work, we present code constructions and repair schemes that extend these results to accommodate different sizes of the evaluation points. In other words, we design schemes that provide points in between. These schemes provide a flexible tradeoff between the sub-packetization size and the repair bandwidth. In addition, we generalize our schemes to manage multiple failures.
A Fast and Scalable Joint Estimator for Integrating Additional Knowledge in Learning Multiple Related Sparse Gaussian Graphical Models
Venue: arXiv cs.LG 2019
Year: 2019

We consider the problem of including additional knowledge in estimating sparse Gaussian graphical models (sGGMs) from aggregated samples, arising often in bioinformatics and neuroimaging applications. Previous joint sGGM estimators either fail to use existing knowledge or cannot scale-up to many tasks (large $K$) under a high-dimensional (large $p$) situation. In this paper, we propose a novel \underline{J}oint \underline{E}lementary \underline{E}stimator incorporating additional \underline{K}nowledge (JEEK) to infer multiple related sparse Gaussian Graphical models from large-scale heterogeneous data. Using domain knowledge as weights, we design a novel hybrid norm as the minimization objective to enforce the superposition of two weighted sparsity constraints, one on the shared interactions and the other on the task-specific structural patterns. This enables JEEK to elegantly consider various forms of existing knowledge based on the domain at hand and avoid the need to design knowledge-specific optimization. JEEK is solved through a fast and entry-wise parallelizable solution that largely improves the computational efficiency of the state-of-the-art $O(p^5K^4)$ to $O(p^2K^4)$. We conduct a rigorous statistical analysis showing that JEEK achieves the same convergence rate $O(\log(Kp)/n_{tot})$ as the state-of-the-art estimators that are much harder to compute. Empirically, on multiple synthetic datasets and two real-world data, JEEK outperforms the speed of the state-of-arts significantly while achieving the same level of prediction accuracy. Available as R tool @ http://jointnets.org/