OpenRaiser/Intern-Atlas huggingface dataset:
Logically-Constrained Neural Fitted Q-Iteration
Venue: arXiv cs.LG 2019
Year: 2019

We propose a method for efficient training of Q-functions for continuous-state Markov Decision Processes (MDPs) such that the traces of the resulting policies satisfy a given Linear Temporal Logic (LTL) property. LTL, a modal logic, can express a wide range of time-dependent logical properties (including "safety") that are quite similar to patterns in natural language. We convert the LTL property into a limit deterministic Buchi automaton and construct an on-the-fly synchronised product MDP. The control policy is then synthesised by defining an adaptive reward function and by applying a modified neural fitted Q-iteration algorithm to the synchronised structure, assuming that no prior knowledge is available from the original MDP. The proposed method is evaluated in a numerical study to test the quality of the generated control policy and is compared with conventional methods for policy synthesis such as MDP abstraction (Voronoi quantizer) and approximate dynamic programming (fitted value iteration).
Neural Approaches to Conversational AI
Venue: arXiv cs.CL 2019
Year: 2019

The present paper surveys neural approaches to conversational AI that have been developed in the last few years. We group conversational systems into three categories: (1) question answering agents, (2) task-oriented dialogue agents, and (3) chatbots. For each category, we present a review of state-of-the-art neural approaches, draw the connection between them and traditional approaches, and discuss the progress that has been made and challenges still being faced, using specific systems and models as case studies.
Pose-Guided Multi-Granularity Attention Network for Text-Based Person Search
Venue: arXiv cs.CV 2019
Year: 2019

Text-based person search aims to retrieve the corresponding person images in an image database by virtue of a describing sentence about the person, which poses great potential for various applications such as video surveillance. Extracting visual contents corresponding to the human description is the key to this cross-modal matching problem. Moreover, correlated images and descriptions involve different granularities of semantic relevance, which is usually ignored in previous methods. To exploit the multilevel corresponding visual contents, we propose a pose-guided multi-granularity attention network (PMA). Firstly, we propose a coarse alignment network (CA) to select the related image regions to the global description by a similarity-based attention. To further capture the phrase-related visual body part, a fine-grained alignment network (FA) is proposed, which employs pose information to learn latent semantic alignment between visual body part and textual noun phrase. To verify the effectiveness of our model, we perform extensive experiments on the CUHK Person Description Dataset (CUHK-PEDES) which is currently the only available dataset for text-based person search. Experimental results show that our approach outperforms the state-of-the-art methods by 15 \% in terms of the top-1 metric.
Fundamental Limits of Invisible Flow Fingerprinting
Venue: arXiv cs.NI 2019
Year: 2019

Network flow fingerprinting can be used to de-anonymize communications on anonymity systems such as Tor by linking the ingress and egress segments of anonymized connections. Assume Alice and Bob have access to the input and the output links of an anonymous network, respectively, and they wish to collaboratively reveal the connections between the input and the output links without being detected by Willie who protects the network. Alice generates a codebook of fingerprints, where each fingerprint corresponds to a unique sequence of inter-packet delays and shares it only with Bob. For each input flow, she selects a fingerprint from the codebook and embeds it in the flow, i.e., changes the packet timings of the flow to follow the packet timings suggested by the fingerprint, and Bob extracts the fingerprints from the output flows. We model the network as parallel $M/M/1$ queues where each queue is shared by a flow from Alice to Bob and other flows independent of the flow from Alice to Bob. The timings of the flows are governed by independent Poisson point processes. Assuming all input flows have equal rates and that Bob observes only flows with fingerprints, we first present two scenarios: 1) Alice fingerprints all the flows; 2) Alice fingerprints a subset of the flows, unknown to Willie. Then, we extend the construction and analysis to the case where flow rates are arbitrary as well as the case where not all the flows that Bob observes have a fingerprint. For each scenario, we derive the number of flows that Alice can fingerprint and Bob can trace by fingerprinting.
Cost Per Action Constrained Auctions
Venue: arXiv cs.GT 2019
Year: 2019

A standard result from auction theory is that bidding truthfully in a second price auction is a weakly dominant strategy. The result, however, does not apply in the presence of Cost Per Action (CPA) constraints. Such constraints exist, for instance, in digital advertising, as some buyer may try to maximize the total number of clicks while keeping the empirical Cost Per Click (CPC) below a threshold. More generally the CPA constraint implies that the buyer has a maximal average cost per unit of value in mind. We discuss how such constraints change some traditional results from auction theory. Following the usual textbook narrative on auction theory, we focus specifically on the symmetric setting, We formalize the notion of CPA constrained auctions and derive a Nash equilibrium for second price auctions. We then extend this result to combinations of first and second price auctions. Further, we expose a revenue equivalence property and show that the seller's revenue-maximizing reserve price is zero. In practice, CPA-constrained buyers may target an empirical CPA on a given time horizon, as the auction is repeated many times. Thus his bidding behavior depends on past realization. We show that the resulting buyer dynamic optimization problem can be formalized with stochastic control tools and solved numerically with available solvers.
A Probabilistic Semi-Supervised Approach to Multi-Task Human Activity Modeling
Venue: arXiv cs.CV 2019
Year: 2019

Human behavior is a continuous stochastic spatio-temporal process which is governed by semantic actions and affordances as well as latent factors. Therefore, video-based human activity modeling is concerned with a number of tasks such as inferring current and future semantic labels, predicting future continuous observations as well as imagining possible future label and feature sequences. In this paper we present a semi-supervised probabilistic deep latent variable model that can represent both discrete labels and continuous observations as well as latent dynamics over time. This allows the model to solve several tasks at once without explicit fine-tuning. We focus here on the tasks of action classification, detection, prediction and anticipation as well as motion prediction and synthesis based on 3D human activity data recorded with Kinect. We further extend the model to capture hierarchical label structure and to model the dependencies between multiple entities, such as a human and objects. Our experiments demonstrate that our principled approach to human activity modeling can be used to detect current and anticipate future semantic labels and to predict and synthesize future label and feature sequences. When comparing our model to state-of-the-art approaches, which are specifically designed for e.g. action classification, we find that our probabilistic formulation outperforms or is comparable to these task specific models.
Context-Aware Systems for Sequential Item Recommendation
Venue: arXiv cs.IR 2019
Year: 2019

Quizlet is the most popular online learning tool in the United States, and is used by over 2/3 of high school students, and 1/2 of college students. With more than 95% of Quizlet users reporting improved grades as a result, the platform has become the de-facto tool used in millions of classrooms. In this paper, we explore the task of recommending suitable content for a student to study, given their prior interests, as well as what their peers are studying. We propose a novel approach, i.e. Neural Educational Recommendation Engine (NERE), to recommend educational content by leveraging student behaviors rather than ratings. We have found that this approach better captures social factors that are more aligned with learning. NERE is based on a recurrent neural network that includes collaborative and content-based approaches for recommendation, and takes into account any particular student's speed, mastery, and experience to recommend the appropriate task. We train NERE by jointly learning the user embeddings and content embeddings, and attempt to predict the content embedding for the final timestamp. We also develop a confidence estimator for our neural network, which is a crucial requirement for productionizing this model. We apply NERE to Quizlet's proprietary dataset, and present our results. We achieved an R^2 score of 0.81 in the content embedding space, and a recall score of 54% on our 100 nearest neighbors. This vastly exceeds the recall@100 score of 12% that a standard matrix-factorization approach provides. We conclude with a discussion on how NERE will be deployed, and position our work as one of the first educational recommender systems for the K-12 space.
The Containment Problem for Unambiguous Register Automata
Venue: arXiv cs.FL 2019
Year: 2019

We investigate the complexity of the containment problem "Does $L(A)\subseteq L(B)$ hold?", where $B$ is an unambiguous register automaton and $A$ is an arbitrary register automaton. We prove that the problem is decidable and give upper bounds on the computational complexity in the general case, and when $B$ is restricted to have a fixed number of registers.
Hypergraph Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we present a hypergraph neural networks (HGNN) framework for data representation learning, which can encode high-order data correlation in a hypergraph structure. Confronting the challenges of learning representation for complex data in real practice, we propose to incorporate such data structure in a hypergraph, which is more flexible on data modeling, especially when dealing with complex data. In this method, a hyperedge convolution operation is designed to handle the data correlation during representation learning. In this way, traditional hypergraph learning procedure can be conducted using hyperedge convolution operations efficiently. HGNN is able to learn the hidden layer representation considering the high-order data structure, which is a general framework considering the complex data correlations. We have conducted experiments on citation network classification and visual object recognition tasks and compared HGNN with graph convolutional networks and other traditional methods. Experimental results demonstrate that the proposed HGNN method outperforms recent state-of-the-art methods. We can also reveal from the results that the proposed HGNN is superior when dealing with multi-modal data compared with existing methods.
Chinese User Service Intention Classification Based on Hybrid Neural Network
Venue: arXiv cs.AI 2019
Year: 2019

In order to satisfy the consumers' increasing personalized service demand, the Intelligent service has arisen. User service intention recognition is an important challenge for intelligent service system to provide precise service. It is difficult for the intelligent system to understand the semantics of user demand which leads to poor recognition effect, because of the noise in user requirement descriptions. Therefore, a hybrid neural network classification model based on BiLSTM and CNN is proposed to recognize users service intentions. The model can fuse the temporal semantics and spatial semantics of the user descriptions. The experimental results show that our model achieves a better effect compared with other models, reaching 0.94 on the F1 score.
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Venue: arXiv cs.LG 2019
Year: 2019

Substantial progress has been made recently on developing provably accurate and efficient algorithms for low-rank matrix factorization via nonconvex optimization. While conventional wisdom often takes a dim view of nonconvex optimization algorithms due to their susceptibility to spurious local minima, simple iterative methods such as gradient descent have been remarkably successful in practice. The theoretical footings, however, had been largely lacking until recently. In this tutorial-style overview, we highlight the important role of statistical models in enabling efficient nonconvex optimization with performance guarantees. We review two contrasting approaches: (1) two-stage algorithms, which consist of a tailored initialization step followed by successive refinement; and (2) global landscape analysis and initialization-free algorithms. Several canonical matrix factorization problems are discussed, including but not limited to matrix sensing, phase retrieval, matrix completion, blind deconvolution, robust principal component analysis, phase synchronization, and joint alignment. Special care is taken to illustrate the key technical insights underlying their analyses. This article serves as a testament that the integrated consideration of optimization and statistics leads to fruitful research findings.
BanditSum: Extractive Summarization as a Contextual Bandit
Venue: arXiv cs.CL 2019
Year: 2019

In this work, we propose a novel method for training neural networks to perform single-document extractive summarization without heuristically-generated extractive labels. We call our approach BanditSum as it treats extractive summarization as a contextual bandit (CB) problem, where the model receives a document to summarize (the context), and chooses a sequence of sentences to include in the summary (the action). A policy gradient reinforcement learning algorithm is used to train the model to select sequences of sentences that maximize ROUGE score. We perform a series of experiments demonstrating that BanditSum is able to achieve ROUGE scores that are better than or comparable to the state-of-the-art for extractive summarization, and converges using significantly fewer update steps than competing approaches. In addition, we show empirically that BanditSum performs significantly better than competing approaches when good summary sentences appear late in the source document.
Rediscovering Deep Neural Networks Through Finite-State Distributions
Venue: arXiv cs.LG 2019
Year: 2019

We propose a new way of thinking about deep neural networks, in which the linear and non-linear components of the network are naturally derived and justified in terms of principles in probability theory. In particular, the models constructed in our framework assign probabilities to uncertain realizations, leading to Kullback-Leibler Divergence (KLD) as the linear layer. In our model construction, we also arrive at a structure similar to ReLU activation supported with Bayes' theorem. The non-linearities in our framework are normalization layers with ReLU and Sigmoid as element-wise approximations. Additionally, the pooling function is derived as a marginalization of spatial random variables according to the mechanics of the framework. As such, Max Pooling is an approximation to the aforementioned marginalization process. Since our models are comprised of finite state distributions (FSD) as variables and parameters, exact computation of information-theoretic quantities such as entropy and KLD is possible, thereby providing more objective measures to analyze networks. Unlike existing designs that rely on heuristics, the proposed framework restricts subjective interpretations of CNNs and sheds light on the functionality of neural networks from a completely new perspective.
Trading information complexity for error II: the case of a large error and external information complexity
Venue: arXiv cs.CC 2019
Year: 2019

Two problems are studied in this paper. (1) How much external or internal information cost is required to compute a Boolean-valued function with an error at most $1/2-ε$ for a small $ε$? It is shown that information cost of order $ε^2$ is necessary and of order $ε$ is sufficient. (2) How much external information cost can be saved to compute a function with a small error $ε>0$ comparing to the case when no error is allowed? It is shown that information cost of order at least $ε$ and at most $h(\sqrtε)$ can be saved. Except the $O(h(\sqrtε))$ upper bound, the other three bounds are tight. For distribution $μ$ that is equally distributed on $(0,0)$ and $(1,1)$, it is shown that $IC^{ext}_μ(XOR, ε)=1-2ε$ where XOR is the two-bit xor function. This equality seems to be the first example of exact information complexity when an error is allowed.
Asymptotic Loss in Privacy due to Dependency in Gaussian Traces
Venue: arXiv cs.IT 2019
Year: 2019

The rapid growth of the Internet of Things (IoT) necessitates employing privacy-preserving techniques to protect users' sensitive information. Even when user traces are anonymized, statistical matching can be employed to infer sensitive information. In our previous work, we have established the privacy requirements for the case that the user traces are instantiations of discrete random variables and the adversary knows only the structure of the dependency graph, i.e., whether each pair of users is connected. In this paper, we consider the case where data traces are instantiations of Gaussian random variables and the adversary knows not only the structure of the graph but also the pairwise correlation coefficients. We establish the requirements on anonymization to thwart such statistical matching, which demonstrate the significant degree to which knowledge of the pairwise correlation coefficients further significantly aids the adversary in breaking user anonymity.
Boosting Trust Region Policy Optimization by Normalizing Flows Policy
Venue: arXiv cs.AI 2019
Year: 2019

We propose to improve trust region policy search with normalizing flows policy. We illustrate that when the trust region is constructed by KL divergence constraints, normalizing flows policy generates samples far from the 'center' of the previous policy iterate, which potentially enables better exploration and helps avoid bad local optima. Through extensive comparisons, we show that the normalizing flows policy significantly improves upon baseline architectures especially on high-dimensional tasks with complex dynamics.
Generative replay with feedback connections as a general strategy for continual learning
Venue: arXiv cs.LG 2019
Year: 2019

A major obstacle to developing artificial intelligence applications capable of true lifelong learning is that artificial neural networks quickly or catastrophically forget previously learned tasks when trained on a new one. Numerous methods for alleviating catastrophic forgetting are currently being proposed, but differences in evaluation protocols make it difficult to directly compare their performance. To enable more meaningful comparisons, here we identified three distinct scenarios for continual learning based on whether task identity is known and, if it is not, whether it needs to be inferred. Performing the split and permuted MNIST task protocols according to each of these scenarios, we found that regularization-based approaches (e.g., elastic weight consolidation) failed when task identity needed to be inferred. In contrast, generative replay combined with distillation (i.e., using class probabilities as "soft targets") achieved superior performance in all three scenarios. Addressing the issue of efficiency, we reduced the computational cost of generative replay by integrating the generative model into the main model by equipping it with generative feedback or backward connections. This Replay-through-Feedback approach substantially shortened training time with no or negligible loss in performance. We believe this to be an important first step towards making the powerful technique of generative replay scalable to real-world continual learning applications.
Encoding Robust Representation for Graph Generation
Venue: arXiv cs.LG 2019
Year: 2019

Generative networks have made it possible to generate meaningful signals such as images and texts from simple noise. Recently, generative methods based on GAN and VAE were developed for graphs and graph signals. However, the mathematical properties of these methods are unclear, and training good generative models is difficult. This work proposes a graph generation model that uses a recent adaptation of Mallat's scattering transform to graphs. The proposed model is naturally composed of an encoder and a decoder. The encoder is a Gaussianized graph scattering transform, which is robust to signal and graph manipulation. The decoder is a simple fully connected network that is adapted to specific tasks, such as link prediction, signal generation on graphs and full graph and signal generation. The training of our proposed system is efficient since it is only applied to the decoder and the hardware requirements are moderate. Numerical results demonstrate state-of-the-art performance of the proposed system for both link prediction and graph and signal generation.
Modeling Uncertainty with Hedged Instance Embedding
Venue: arXiv cs.LG 2019
Year: 2019

Instance embeddings are an efficient and versatile image representation that facilitates applications like recognition, verification, retrieval, and clustering. Many metric learning methods represent the input as a single point in the embedding space. Often the distance between points is used as a proxy for match confidence. However, this can fail to represent uncertainty arising when the input is ambiguous, e.g., due to occlusion or blurriness. This work addresses this issue and explicitly models the uncertainty by hedging the location of each input in the embedding space. We introduce the hedged instance embedding (HIB) in which embeddings are modeled as random variables and the model is trained under the variational information bottleneck principle. Empirical results on our new N-digit MNIST dataset show that our method leads to the desired behavior of hedging its bets across the embedding space upon encountering ambiguous inputs. This results in improved performance for image matching and classification tasks, more structure in the learned embedding space, and an ability to compute a per-exemplar uncertainty measure that is correlated with downstream performance.
Learning Deep Representations from Clinical Data for Chronic Kidney Disease
Venue: arXiv cs.LG 2019
Year: 2019

We study the behavior of a Time-Aware Long Short-Term Memory Autoencoder, a state-of-the-art method, in the context of learning latent representations from irregularly sampled patient data. We identify a key issue in the way such recurrent neural network models are being currently used and show that the solution of the issue leads to significant improvements in the learnt representations on both synthetic and real datasets. A detailed analysis of the improved methodology for representing patients suffering from Chronic Kidney Disease (CKD) using clinical data is provided. Experimental results show that the proposed T-LSTM model is able to capture the long-term trends in the data, while effectively handling the noise in the signal. Finally, we show that by using the latent representations of the CKD patients obtained from the T-LSTM autoencoder, one can identify unusual patient profiles from the target population.