OpenRaiser/Intern-Atlas huggingface dataset:
Real Time Trajectory Prediction Using Deep Conditional Generative Models
Venue: arXiv cs.LG 2020
Year: 2020

Data driven methods for time series forecasting that quantify uncertainty open new important possibilities for robot tasks with hard real time constraints, allowing the robot system to make decisions that trade off between reaction time and accuracy in the predictions. Despite the recent advances in deep learning, it is still challenging to make long term accurate predictions with the low latency required by real time robotic systems. In this paper, we propose a deep conditional generative model for trajectory prediction that is learned from a data set of collected trajectories. Our method uses encoder and decoder deep networks that maps complete or partial trajectories to a Gaussian distributed latent space and back, allowing for fast inference of the future values of a trajectory given previous observations. The encoder and decoder networks are trained using stochastic gradient variational Bayes. In the experiments, we show that our model provides more accurate long term predictions with a lower latency that popular models for trajectory forecasting like recurrent neural networks or physical models based on differential equations. Finally, we test our proposed approach in a robot table tennis scenario to evaluate the performance of the proposed method in a robotic task with hard real time constraints.
Deep Context-Aware Recommender System Utilizing Sequential Latent Context
Venue: arXiv cs.LG 2020
Year: 2020

Context-aware recommender systems (CARSs) apply sensing and analysis of user context in order to provide personalized services. Adding context to a recommendation model is challenging, since the addition of context may increases both the dimensionality and sparsity of the model. Recent research has shown that modeling contextual information as a latent vector may address the sparsity and dimensionality challenges. We suggest a new latent modeling of sequential context by generating sequences of contextual information and reducing their contextual space to a compressed latent space.We train a long short-term memory (LSTM) encoder-decoder network on sequences of contextual information and extract sequential latent context from the hidden layer of the network in order to represent a compressed representation of sequential data. We propose new context-aware recommendation models that extend the neural collaborative filtering approach and learn nonlinear interactions between latent features of users, items, and contexts which take into account the sequential latent context representation as part of the recommendation process. We deployed our approach using two context-aware datasets with different context dimensions. Empirical analysis of our results validates that our proposed sequential latent context-aware model (SLCM), surpasses state of the art CARS models.
A Study of Context Dependencies in Multi-page Product Search
Venue: arXiv cs.IR 2020
Year: 2020

In product search, users tend to browse results on multiple search result pages (SERPs) (e.g., for queries on clothing and shoes) before deciding which item to purchase. Users' clicks can be considered as implicit feedback which indicates their preferences and used to re-rank subsequent SERPs. Relevance feedback (RF) techniques are usually involved to deal with such scenarios. However, these methods are designed for document retrieval, where relevance is the most important criterion. In contrast, product search engines need to retrieve items that are not only relevant but also satisfactory in terms of customers' preferences. Personalization based on users' purchase history has been shown to be effective in product search. However, this method captures users' long-term interest, which does not always align with their short-term interest, and does not benefit customers with little or no purchase history. In this paper, we study RF techniques based on both long-term and short-term context dependencies in multi-page product search. We also propose an end-to-end context-aware embedding model which can capture both types of context. Our experimental results show that short-term context leads to much better performance compared with long-term and no context. Moreover, our proposed model is more effective than state-of-art word-based RF models.
Follow the Leader: Documents on the Leading Edge of Semantic Change Get More Citations
Venue: arXiv cs.CL 2020
Year: 2020

Diachronic word embeddings -- vector representations of words over time -- offer remarkable insights into the evolution of language and provide a tool for quantifying sociocultural change from text documents. Prior work has used such embeddings to identify shifts in the meaning of individual words. However, simply knowing that a word has changed in meaning is insufficient to identify the instances of word usage that convey the historical or the newer meaning. In this paper, we link diachronic word embeddings to documents, by situating those documents as leaders or laggards with respect to ongoing semantic changes. Specifically, we propose a novel method to quantify the degree of semantic progressiveness in each word usage, and then show how these usages can be aggregated to obtain scores for each document. We analyze two large collections of documents, representing legal opinions and scientific articles. Documents that are scored as semantically progressive receive a larger number of citations, indicating that they are especially influential. Our work thus provides a new technique for identifying lexical semantic leaders and demonstrates a new link between progressive use of language and influence in a citation network.
Learning Transferable Domain Priors for Safe Exploration in Reinforcement Learning
Venue: arXiv cs.AI 2020
Year: 2020

Prior access to domain knowledge could significantly improve the performance of a reinforcement learning agent. In particular, it could help agents avoid potentially catastrophic exploratory actions, which would otherwise have to be experienced during learning. In this work, we identify consistently undesirable actions in a set of previously learned tasks, and use pseudo-rewards associated with them to learn a prior policy. In addition to enabling safer exploratory behaviors in subsequent tasks in the domain, we show that these priors are transferable to similar environments, and can be learned off-policy and in parallel with the learning of other tasks in the domain. We compare our approach to established, state-of-the-art algorithms in both discrete as well as continuous environments, and demonstrate that it exhibits a safer exploratory behavior while learning to perform arbitrary tasks in the domain. We also present a theoretical analysis to support these results, and briefly discuss the implications and some alternative formulations of this approach, which could also be useful in certain scenarios.
Synthesis of Boolean Networks from Biological Dynamical Constraints using Answer-Set Programming
Venue: arXiv cs.AI 2020
Year: 2020

Boolean networks model finite discrete dynamical systems with complex behaviours. The state of each component is determined by a Boolean function of the state of (a subset of) the components of the network. This paper addresses the synthesis of these Boolean functions from constraints on their domain and emerging dynamical properties of the resulting network. The dynamical properties relate to the existence and absence of trajectories between partially observed configurations, and to the stable behaviours (fixpoints and cyclic attractors). The synthesis is expressed as a Boolean satisfiability problem relying on Answer-Set Programming with a parametrized complexity, and leads to a complete non-redundant characterization of the set of solutions. Considered constraints are particularly suited to address the synthesis of models of cellular differentiation processes, as illustrated on a case study. The scalability of the approach is demonstrated on random networks with scale-free structures up to 100 to 1,000 nodes depending on the type of constraints.
Convex Controller Synthesis for Robot Contact
Venue: arXiv cs.RO 2020
Year: 2020

Controlling contacts is truly challenging, and this has been a major hurdle to deploying industrial robots into unstructured/human-centric environments. More specifically, the main challenges are: (i) how to ensure stability at all times; (ii) how to satisfy task-specific performance specifications; (iii) how to achieve (i) and (ii) under environment uncertainty, robot parameters uncertainty, sensor and actuator time delays, external perturbations, etc. Here, we propose a new approach -- Convex Controller Synthesis (CCS) -- to tackle the above challenges based on robust control theory and convex optimization. In two physical interaction tasks -- robot hand guiding and sliding on surfaces with different and unknown stiffnesses -- we show that CCS controllers outperform their classical counterparts in an essential way.
Taming the Tail of Maximal Information Age in Wireless Industrial Networks
Venue: arXiv cs.NI 2020
Year: 2020

In wireless industrial networks, the information of time-sensitive control systems needs to be transmitted in an ultra-reliable and low-latency manner. This letter studies the resource allocation problem in finite blocklength transmission, in which the information freshness is measured as the age of information (AoI) whose maximal AoI is characterized using extreme value theory (EVT). The considered system design is to minimize the sensors' transmit power and transmission blocklength subject to constraints on the maximal AoI's tail behavior. The studied problem is solved using Lyapunov stochastic optimization, and a dynamic reliability and age-aware policy for resource allocation and status updates is proposed. Simulation results validate the effectiveness of using EVT to characterize the maximal AoI. It is shown that sensors need to send larger-size data with longer transmission blocklength at lower transmit power. Moreover, the maximal AoI's tail decays faster at the expense of higher average information age.
Provably Secure Group Signature Schemes from Code-Based Assumptions
Venue: arXiv cs.CR 2020
Year: 2020

We solve an open question in code-based cryptography by introducing two provably secure group signature schemes from code-based assumptions. Our basic scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise problem, and a variant of the Syndrome Decoding problem. The construction produces smaller key and signature sizes than the previous group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed $2^{24}$, which is roughly comparable to the current population of the Netherlands. We develop the basic scheme further to achieve the strongest anonymity notion, i.e., CCA-anonymity, with a small overhead in terms of efficiency. The feasibility of two proposed schemes is supported by implementation results. Our two schemes are the first in their respective classes of provably secure groups signature schemes. Additionally, the techniques introduced in this work might be of independent interest. These are a new verifiable encryption protocol for the randomized McEliece encryption and a novel approach to design formal security reductions from the Syndrome Decoding problem.
Local Large Deviation Principle, Large Deviation Principle and Information theory for the Signal -to- Interference -Plus- Noise Ratio Graph Models
Venue: arXiv cs.IT 2020
Year: 2020

Given devices space $D$, an intensity measure $λm\in(0,\infty)$, a transition kernel $Q$ from the space $D$ to positive real numbers $(0,\infty,$ a path-loss function (which depends on the Euclidean distance between the devices and a positive constant $α$), we define a Marked Poisson Point process (MPPP). For a given MPPP and technical constants $τ_λ,γ_λ:(0,\,\infty)\to (0,\infty),$ we define a Marked Signal-to- Interference and Noise Ratio (SINR) graph, and associate with it two empirical measures; the \emph{empirical marked measure} and the \emph{empirical connectivity measure}. For a class of marked SINR graphs, we prove a joint \emph{ large deviation principle}(LDP) for these empirical measures, with speed $λ$ in the $τ$-topology. From the joint large deviation principle for the empirical marked measure and the empirical connectivity measure, we obtain an Asymptotic Equipartition Property(AEP) for network structured data modelled as a marked SINR graph. Specifically, we show that for large dense marked SINR graph one require approximately about $λ^{2}H(Q\times Q)/\log 2$ bits to transmit the information contained in the network with high probability, where $ H(Q\times Q)$ is a properly defined entropy for the exponential transition kernel with parameter $c$. Further, we prove a \emph {local large deviation principle} (LLDP) for the class of marked SINR graphs on $D,$ where $λ[τ_λ(a)γ_λ(a)+λτ_λ(b)γ_λ(b)]\to β(a,b),$ $ a,b\in (0,\infty)$, with speed $λ$ from a \emph{ spectral potential} point. From the LLDP we derive a conditional LDP for the marked SINR graphs.
Semantic Foreground Inpainting from Weak Supervision
Venue: arXiv cs.CV 2020
Year: 2020

Semantic scene understanding is an essential task for self-driving vehicles and mobile robots. In our work, we aim to estimate a semantic segmentation map, in which the foreground objects are removed and semantically inpainted with background classes, from a single RGB image. This semantic foreground inpainting task is performed by a single-stage convolutional neural network (CNN) that contains our novel max-pooling as inpainting (MPI) module, which is trained with weak supervision, i.e., it does not require manual background annotations for the foreground regions to be inpainted. Our approach is inherently more efficient than the previous two-stage state-of-the-art method, and outperforms it by a margin of 3% IoU for the inpainted foreground regions on Cityscapes. The performance margin increases to 6% IoU, when tested on the unseen KITTI dataset. The code and the manually annotated datasets for testing are shared with the research community at https://github.com/Chenyang-Lu/semantic-foreground-inpainting.
Neural Networks for Relational Data
Venue: arXiv cs.LG 2020
Year: 2020

While deep networks have been enormously successful over the last decade, they rely on flat-feature vector representations, which makes them unsuitable for richly structured domains such as those arising in applications like social network analysis. Such domains rely on relational representations to capture complex relationships between entities and their attributes. Thus, we consider the problem of learning neural networks for relational data. We distinguish ourselves from current approaches that rely on expert hand-coded rules by learning relational random-walk-based features to capture local structural interactions and the resulting network architecture. We further exploit parameter tying of the network weights of the resulting relational neural network, where instances of the same type share parameters. Our experimental results across several standard relational data sets demonstrate the effectiveness of the proposed approach over multiple neural net baselines as well as state-of-the-art statistical relational models.
PDA: Progressive Data Augmentation for General Robustness of Deep Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Adversarial images are designed to mislead deep neural networks (DNNs), attracting great attention in recent years. Although several defense strategies achieved encouraging robustness against adversarial samples, most of them fail to improve the robustness on common corruptions such as noise, blur, and weather/digital effects (e.g. frost, pixelate). To address this problem, we propose a simple yet effective method, named Progressive Data Augmentation (PDA), which enables general robustness of DNNs by progressively injecting diverse adversarial noises during training. In other words, DNNs trained with PDA are able to obtain more robustness against both adversarial attacks as well as common corruptions than the recent state-of-the-art methods. We also find that PDA is more efficient than prior arts and able to prevent accuracy drop on clean samples without being attacked. Furthermore, we theoretically show that PDA can control the perturbation bound and guarantee better generalization ability than existing work. Extensive experiments on many benchmarks such as CIFAR-10, SVHN, and ImageNet demonstrate that PDA significantly outperforms its counterparts in various experimental setups.
Sublinear Latency for Simplified Successive Cancellation Decoding of Polar Codes
Venue: arXiv cs.IT 2020
Year: 2020

This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is $O(N^{1-1/μ})$, where $N$ is the block length and $μ$ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate $0$ or $1$.
Optimal Machine Intelligence at the Edge of Chaos
Venue: arXiv cs.LG 2020
Year: 2020

It has long been suggested that the biological brain operates at some critical point between two different phases, possibly order and chaos. Despite many indirect empirical evidence from the brain and analytical indication on simple neural networks, the foundation of this hypothesis on generic non-linear systems remains unclear. Here we develop a general theory that reveals the exact edge of chaos is the boundary between the chaotic phase and the (pseudo)periodic phase arising from Neimark-Sacker bifurcation. This edge is analytically determined by the asymptotic Jacobian norm values of the non-linear operator and influenced by the dimensionality of the system. The optimality at the edge of chaos is associated with the highest information transfer between input and output at this point similar to that of the logistic map. As empirical validations, our experiments on the various deep learning models in computer vision demonstrate the optimality of the models near the edge of chaos, and we observe that the state-of-art training algorithms push the models towards such edge as they become more accurate. We further establishes the theoretical understanding of deep learning model generalization through asymptotic stability.
Cogsworth: Byzantine View Synchronization
Venue: arXiv cs.DC 2020
Year: 2020

Most methods for Byzantine fault tolerance (BFT) in the partial synchrony setting divide the local state of the nodes into views, and the transition from one view to the next dictates a leader change. In order to provide liveness, all honest nodes need to stay in the same view for a sufficiently long time. This requires \emph{view synchronization}, a requisite of BFT that we extract and formally define here. Existing approaches for Byzantine view synchronization incur quadratic communication (in $n$, the number of parties). A cascade of $O(n)$ view changes may thus result in $O(n^3)$ communication complexity. This paper presents a new Byzantine view synchronization algorithm named Cogsworth, that has optimistically linear communication complexity and constant latency. Faced with benign failures, Cogsworth has expected linear communication and constant latency. The result here serves as an important step towards reaching solutions that have overall quadratic communication, the known lower bound on Byzantine fault tolerant consensus. Cogsworth is particularly useful for a family of BFT protocols that already exhibit linear communication under various circumstances, but suffer quadratic overhead due to view synchronization.
Crucial and Redundant Shares and Compartments in Secret Sharing
Venue: arXiv cs.CR 2020
Year: 2020

Secret sharing is the well-known problem of splitting a secret into multiple shares, which are distributed to shareholders. When enough or the correct combination of shareholders work together the secret can be restored. We introduce two new types of shares to the secret sharing scheme of Shamir. Crucial shares are always needed for the reconstruction of the secret, whereas mutual redundant shares only help once in reconstructing the secret. Further, we extend the idea of crucial and redundant shares to a compartmented secret sharing scheme. The scheme, which is based on Shamir's, allows distributing the secret to different compartments, that hold shareholders themselves. In each compartment, another secret sharing scheme can be applied. Using the modifications the overall complexity of general access structures realized through compartmented secret sharing schemes can be reduced. This improves the computational complexity. Also, the number of shares can be reduced and some complex access structures can be realized with ideal amount and size of shares.
Contrastively Smoothed Class Alignment for Unsupervised Domain Adaptation
Venue: arXiv cs.LG 2020
Year: 2020

Recent unsupervised approaches to domain adaptation primarily focus on minimizing the gap between the source and the target domains through refining the feature generator, in order to learn a better alignment between the two domains. This minimization can be achieved via a domain classifier to detect target-domain features that are divergent from source-domain features. However, by optimizing via such domain classification discrepancy, ambiguous target samples that are not smoothly distributed on the low-dimensional data manifold are often missed. To solve this issue, we propose a novel Contrastively Smoothed Class Alignment (CoSCA) model, that explicitly incorporates both intra- and inter-class domain discrepancy to better align ambiguous target samples with the source domain. CoSCA estimates the underlying label hypothesis of target samples, and simultaneously adapts their feature representations by optimizing a proposed contrastive loss. In addition, Maximum Mean Discrepancy (MMD) is utilized to directly match features between source and target samples for better global alignment. Experiments on several benchmark datasets demonstrate that CoSCA can outperform state-of-the-art approaches for unsupervised domain adaptation by producing more discriminative features.
Cascade Size Distributions: Why They Matter and How to Compute Them Efficiently
Venue: arXiv cs.AI 2020
Year: 2020

Cascade models are central to understanding, predicting, and controlling epidemic spreading and information propagation. Related optimization, including influence maximization, model parameter inference, or the development of vaccination strategies, relies heavily on sampling from a model. This is either inefficient or inaccurate. As alternative, we present an efficient message passing algorithm that computes the probability distribution of the cascade size for the Independent Cascade Model on weighted directed networks and generalizations. Our approach is exact on trees but can be applied to any network topology. It approximates locally tree-like networks well, scales to large networks, and can lead to surprisingly good performance on more dense networks, as we also exemplify on real world data.