Linear Networks: Rare-Event Simulation and Markov Modulation

We consider a linear network under Markov modulation, with a focus on the probability that the joint storage level attains a value in a rare set at a given point in time. The main objective is to develop efficient importance sampling algorithms with provable performance guarantees. For linear networks without modulation, we prove that the number of runs needed (so as to obtain an estimate with a given precision) increases polynomially (whereas the probability under consideration decay essentially exponentially); for networks with modulation our algorithm is asymptotically efficient.

Contextual Explanation Networks

We introduce contextual explanation networks (CENs)—a class of models that learn to predict by generating and leveraging intermediate explanations. CENs combine deep networks with context-specific probabilistic models and construct explanations in the form of locally-correct hypotheses. Contrary to the existing post-hoc model-explanation tools, CENs learn to predict and to explain jointly. Our approach offers two major advantages: (i) for each prediction, valid instance-specific explanations are generated with no computational overhead and (ii) prediction via explanation acts as a regularization and boosts performance in low-resource settings. We prove that local approximations to the decision boundary of our networks are consistent with the generated explanations. Our results on image and text classification and survival analysis tasks demonstrate that CENs can easily match or outperform the state-of-the-art while offering additional insights behind each prediction, valuable for decision support.

Learning Belief Network Structure From Data under Causal Insufficiency

Though a belief network (a representation of the joint probability distribution, see [3]) and a causal network (a representation of causal relationships [14]) are intended to mean different things, they are closely related. Both assume an underlying dag (directed acyclic graph) structure of relations among variables and if Markov condition and faithfulness condition [15] are met, then a causal network is in fact a belief network. The difference comes to appearance when we recover belief network and causal network structure from data. A causal network structure may be impossible to recover completely from data as not all directions of causal links may be uniquely determined [15]. Fortunately, if we deal with causally sufficient sets of variables (that is whenever significant influence variables are not omitted from observation), then there exists the possibility to identify the family of belief networks a causal network belongs to [16]. Regrettably, to our knowledge, a similar result is not directly known for causally insufficient sets of variables. Spirtes, Glymour and Scheines developed a CI algorithm to handle this situation, but it leaves some important questions open. The big open question is whether or not the bidirectional edges (that is indications of a common cause) are the only ones necessary to develop a belief network out of the product of CI, or must there be some other hidden variables added (e.g. by guessing). This paper is devoted to settling this question.

Deep Learning for Ontology Reasoning

In this work, we present a novel approach to ontology reasoning that is based on deep learning rather than logic-based formal reasoning. To this end, we introduce a new model for statistical relational learning that is built upon deep recursive neural networks, and give experimental evidence that it can easily compete with, or even outperform, existing logic-based reasoners on the task of ontology reasoning. More precisely, we compared our implemented system with one of the best logic-based ontology reasoners at present, RDFox, on a number of large standard benchmark datasets, and found that our system attained high reasoning quality, while being up to two orders of magnitude faster.

Local Search Methods for Fast Near Neighbor Search

Near neighbor search (NNS) has been traditionally addressed from an algorithmic perspective, that is, given a dataset and a distance function, the goal is to build a data structure along with discarding rules that quickly find the near neighbor of a query under the given distance function. In this manuscript, we take another approach. We restate NNS as a combinatorial optimization problem, being the goal to minimize the distance from the query to the data set. This cost function is well defined, and the minimum is realized precisely with the nearest object to the query. Adopting this new view allows the use of a rich collection of optimization algorithms with a long tradition. We present three local search algorithms that solve the NNS problem from the combinatorial optimization point of view. Two of the algorithms can be described as the hyper-parameter optimization of two known indexing methods, simplifying their adoption for final users. The third method achieves excellent search tradeoffs among speed, memory, and quality of the approximation. For instance, for moderately large dimensions, our indexes can reach above 0.99 recall reviewing less than 1% of the database. We conducted extensive experimentation with five real-world standard benchmark and five synthetic datasets to prove our claims.

Conducting Simulations in Causal Inference with Networks-Based Structural Equation Models

The past decade has seen an increasing body of literature devoted to the estimation of causal effects in network-dependent data. However, the validity of many classical statistical methods in such data is often questioned. There is an emerging need for objective and practical ways to assess which causal methodologies might be applicable and valid in network-dependent data. This paper describes a set of tools implemented in the simcausal R package that allow simulating data based on user-specified structural equation model for connected units. Specification and simulation of counterfactual data is implemented for static, dynamic and stochastic interventions. A new interface aims to simplify the specification of network-based functional relationships between connected units. A set of examples illustrates how these simulations may be applied to evaluation of different statistical methods for estimation of causal effects in network-dependent data.

Collaborative Deep Learning for Speech Enhancement: A Run-Time Model Selection Method Using Autoencoders

We show that a Modular Neural Network (MNN) can combine various speech enhancement modules, each of which is a Deep Neural Network (DNN) specialized on a particular enhancement job. Differently from an ordinary ensemble technique that averages variations in models, the propose MNN selects the best module for the unseen test signal to produce a greedy ensemble. We see this as Collaborative Deep Learning (CDL), because it can reuse various already-trained DNN models without any further refining. In the proposed MNN selecting the best module during run time is challenging. To this end, we employ a speech AutoEncoder (AE) as an arbitrator, whose input and output are trained to be as similar as possible if its input is clean speech. Therefore, the AE can gauge the quality of the module-specific denoised result by seeing its AE reconstruction error, e.g. low error means that the module output is similar to clean speech. We propose an MNN structure with various modules that are specialized on dealing with a specific noise type, gender, and input Signal-to-Noise Ratio (SNR) value, and empirically prove that it almost always works better than an arbitrarily chosen DNN module and sometimes as good as an oracle result.

Model Selection in Bayesian Neural Networks via Horseshoe Priors

Bayesian Neural Networks (BNNs) have recently received increasing attention for their ability to provide well-calibrated posterior uncertainties. However, model selection—even choosing the number of nodes—remains an open question. In this work, we apply a horseshoe prior over node pre-activations of a Bayesian neural network, which effectively turns off nodes that do not help explain the data. We demonstrate that our prior prevents the BNN from under-fitting even when the number of nodes required is grossly over-estimated. Moreover, this model selection over the number of nodes doesn’t come at the expense of predictive or computational performance; in fact, we learn smaller networks with comparable predictive performance to current approaches.

Twitter Hashtag Recommendation using Matrix Factorization

Twitter, one of the biggest and most popular microblogging Websites, has evolved into a powerful communication platform which allows millions of active users to generate huge volume of microposts and queries on a daily basis. To accommodate effective categorization and easy search, users are allowed to make use of hashtags, keywords or phrases prefixed by hash character, to categorize and summarize their posts. However, valid hashtags are not restricted and thus are created in a free and heterogeneous style, increasing difficulty of the task of tweet categorization. In this paper, we propose a low-rank weighted matrix factorization based method to recommend hashtags to the users solely based on their hashtag usage history and independent from their tweets’ contents. We confirm using two-sample t-test that users are more likely to adopt new hashtags similar to the ones they have previously adopted. In particular, we formulate the problem of hashtag recommendation into an optimization problem and incorporate hashtag correlation weight matrix into it to account for the similarity between different hashtags. We finally leverage widely used matrix factorization from recommender systems to solve the optimization problem by capturing the latent factors of users and hashtags. Empirical experiments demonstrate that our method is capable to properly recommend hashtags.

Federated Multi-Task Learning

Federated learning poses new statistical and systems challenges in training machine learning models over distributed networks of devices. In this work, we show that multi-task learning is naturally suited to handle the statistical challenges of this setting, and propose a novel systems-aware optimization method, MOCHA, that is robust to practical systems issues. Our method and theory for the first time consider issues of high communication cost, stragglers, and fault tolerance for distributed multi-task learning. The resulting method achieves significant speedups compared to alternatives in the federated setting, as we demonstrate through simulations on real-world federated datasets.

Iterative Machine Teaching

In this paper, we consider the problem of machine teaching, the inverse problem of machine learning. Different from traditional machine teaching which views the learners as batch algorithms, we study a new paradigm where the learner uses an iterative algorithm and a teacher can feed examples sequentially and intelligently based on the current performance of the learner. We show that the teaching complexity in the iterative case is very different from that in the batch case. Instead of constructing a minimal training set for learners, our iterative machine teaching focuses on achieving fast convergence in the learner model. Depending on the level of information the teacher has from the learner model, we design teaching algorithms which can provably reduce the number of teaching examples and achieve faster convergence than learning without teachers. We also validate our theoretical findings with extensive experiments on different data distribution and real image datasets.

Preliminary results on Ontology-based Open Data Publishing

Despite the current interest in Open Data publishing, a formal and comprehensive methodology supporting an organization in deciding which data to publish and carrying out precise procedures for publishing high-quality data, is still missing. In this paper we argue that the Ontology-based Data Management paradigm can provide a formal basis for a principled approach to publish high quality, semantically annotated Open Data. We describe two main approaches to using an ontology for this endeavor, and then we present some technical results on one of the approaches, called bottom-up, where the specification of the data to be published is given in terms of the sources, and specific techniques allow deriving suitable annotations for interpreting the published data under the light of the ontology.

Exploiting Restricted Boltzmann Machines and Deep Belief Networks in Compressed Sensing

This paper proposes a CS scheme that exploits the representational power of restricted Boltzmann machines and deep learning architectures to model the prior distribution of the sparsity pattern of signals belonging to the same class. The determined probability distribution is then used in a maximum a posteriori (MAP) approach for the reconstruction. The parameters of the prior distribution are learned from training data. The motivation behind this approach is to model the higher-order statistical dependencies between the coefficients of the sparse representation, with the final goal of improving the reconstruction. The performance of the proposed method is validated on the Berkeley Segmentation Dataset and the MNIST Database of handwritten digits.

Quantum Low Entropy based Associative Reasoning or QLEAR Learning

In this paper, we propose the classification method based on a learning paradigm we are going to call Quantum Low Entropy based Associative Reasoning or QLEAR learning. The approach is based on the idea that classification can be understood as supervised clustering, where a quantum entropy in the context of the quantum probabilistic model, will be used as a ‘capturer’ (measure, or external index), of the ‘natural structure’ of the data. By using quantum entropy we do not make any assumption about linear separability of the data that are going to be classified. The basic idea is to find close neighbors to a query sample and then use relative change in the quantum entropy as a measure of similarity of the newly arrived sample with the representatives of interest. In other words, method is based on calculation of quantum entropy of the referent system and its relative change with the addition of the newly arrived sample. Referent system consists of vectors that represent individual classes and that are the most similar, in Euclidean distance sense, to the vector that is analyzed. Here, we analyze the classification problem in the context of measuring similarities to prototype examples of categories. While nearest neighbor classifiers are natural in this setting, they suffer from the problem of high variance (in bias-variance decomposition) in the case of limited sampling. Alternatively, one could use machine learning techniques (like support vector machines) but they involve time-consuming optimization. Here we propose a hybrid of nearest neighbor and machine learning technique which deals naturally with the multi-class setting, has reasonable computational complexity both in training and at run time, and yields excellent results in practice.

IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models

This paper provides a unified account of two schools of thinking in information retrieval modelling: the generative retrieval focusing on predicting relevant documents given a query, and the discriminative retrieval focusing on predicting relevancy given a query-document pair. We propose a game theoretical minimax game to iteratively optimise both models. On one hand, the discriminative model, aiming to mine signals from labelled and unlabelled data, provides guidance to train the generative model towards fitting the underlying relevance distribution over documents given the query. On the other hand, the generative model, acting as an attacker to the current discriminative model, generates difficult examples for the discriminative model in an adversarial way by minimising its discrimination objective. With the competition between these two models, we show that the unified framework takes advantage of both schools of thinking: (i) the generative model learns to fit the relevance distribution over documents via the signals from the discriminative model, and (ii) the discriminative model is able to exploit the unlabelled data selected by the generative model to achieve a better estimation for document ranking. Our experimental results have demonstrated significant performance gains as much as 23.96% on Precision@5 and 15.50% on MAP over strong baselines in a variety of applications including web search, item recommendation, and question answering.

Decorrelation of Neutral Vector Variables: Theory and Applications

In this paper, we propose novel strategies for neutral vector variable decorrelation. Two fundamental invertible transformations, namely serial nonlinear transformation and parallel nonlinear transformation, are proposed to carry out the decorrelation. For a neutral vector variable, which is not multivariate Gaussian distributed, the conventional principal component analysis (PCA) cannot yield mutually independent scalar variables. With the two proposed transformations, a highly negatively correlated neutral vector can be transformed to a set of mutually independent scalar variables with the same degrees of freedom. We also evaluate the decorrelation performances for the vectors generated from a single Dirichlet distribution and a mixture of Dirichlet distributions. The mutual independence is verified with the distance correlation measurement. The advantages of the proposed decorrelation strategies are intensively studied and demonstrated with synthesized data and practical application evaluations.

Constrained Policy Optimization

For many applications of reinforcement learning it can be more convenient to specify both a reward function and constraints, rather than trying to design behavior through the reward function. For example, systems that physically interact with or around humans should satisfy safety constraints. Recent advances in policy search algorithms (Mnih et al., 2016, Schulman et al., 2015, Lillicrap et al., 2016, Levine et al., 2016) have enabled new capabilities in high-dimensional control, but do not consider the constrained setting. We propose Constrained Policy Optimization (CPO), the first general-purpose policy search algorithm for constrained reinforcement learning with guarantees for near-constraint satisfaction at each iteration. Our method allows us to train neural network policies for high-dimensional control while making guarantees about policy behavior all throughout training. Our guarantees are based on a new theoretical result, which is of independent interest: we prove a bound relating the expected returns of two policies to an average divergence between them. We demonstrate the effectiveness of our approach on simulated robot locomotion tasks where the agent must satisfy constraints motivated by safety.

Universal Reinforcement Learning Algorithms: Survey and Experiments

Many state-of-the-art reinforcement learning (RL) algorithms typically assume that the environment is an ergodic Markov Decision Process (MDP). In contrast, the field of universal reinforcement learning (URL) is concerned with algorithms that make as few assumptions as possible about the environment. The universal Bayesian agent AIXI and a family of related URL algorithms have been developed in this setting. While numerous theoretical optimality results have been proven for these agents, there has been no empirical investigation of their behavior to date. We present a short and accessible survey of these URL algorithms under a unified notation and framework, along with results of some experiments that qualitatively illustrate some properties of the resulting policies, and their relative performance on partially-observable gridworld environments. We also present an open-source reference implementation of the algorithms which we hope will facilitate further understanding of, and experimentation with, these ideas.

Boosting Functional Regression Models with FDboost

The R add-on package FDboost is a flexible toolbox for the estimation of functional regression models by model-based boosting. It provides the possibility to fit regression models for scalar and functional response with effects of scalar as well as functional covariates, i.e., scalar-on-function, function-on-scalar and function-on-function regression models. In addition to mean regression, quantile regression models as well as generalized additive models for location scale and shape can be fitted with FDboost. Furthermore, boosting can be used in high-dimensional data settings with more covariates than observations. We provide a hands-on tutorial on model fitting and tuning, including the visualization of results. The methods for scalar-on-function regression are illustrated with spectrometric data of fossil fuels and those for functional response regression with a data set including bioelectrical signals for emotional episodes.

A Multi-Layer K-means Approach for Multi-Sensor Data Pattern Recognition in Multi-Target Localization

Data-target association is an important step in multi-target localization for the intelligent operation of un- manned systems in numerous applications such as search and rescue, traffic management and surveillance. The objective of this paper is to present an innovative data association learning approach named multi-layer K-means (MLKM) based on leveraging the advantages of some existing machine learning approaches, including K-means, K-means++, and deep neural networks. To enable the accurate data association from different sensors for efficient target localization, MLKM relies on the clustering capabilities of K-means++ structured in a multi-layer framework with the error correction feature that is motivated by the backpropogation that is well-known in deep learning research. To show the effectiveness of the MLKM method, numerous simulation examples are conducted to compare its performance with K-means, K-means++, and deep neural networks.

Inverse Lyndon words and Inverse Lyndon factorizations of words

Towards Visual Ego-motion Learning in Robots

Session-Based Cooperation in Cognitive Radio Networks: A Network-Level Approach

Feature Incay for Representation Regularization

Localisation of soft modes at the depinning transition

Local ergodicity in the exclusion process on an infinite weighted graph

Construction of and efficient sampling from the simplicial configuration model

Robustness to unknown error in sparse regularization

Near Optimal Online Distortion Minimization for Energy Harvesting Nodes

Auto-Encoding Sequential Monte Carlo

Disorder-induced mixing of transverse and longitudinal polarizations and Rayleigh anomalies: theory and experimental verification

Approximate confidence distribution computing: An effective likelihood-free method with statistical guarantees

LLT polynomials, chromatic quasisymmetric functions and graphs with cycles

Sparsity enforcing priors in inverse problems via Normal variance mixtures: model selection, algorithms and applications

Neural Embeddings of Graphs in Hyperbolic Space

Dynamics of entanglement and transport in 1D systems with quenched randomness

DNN-based uncertainty estimation for weighted DNN-HMM ASR

Emergent Language in a Multi-Modal, Multi-Step Referential Game

Covariate Assisted Variable Ranking

A New Voltage Stability-Constrained Optimal Power Flow Model: Sufficient Condition, SOCP Representation, and Relaxation

Extensions of the Burr Type XII distribution and Applications

Fair Inference On Outcomes

Sharp asymptotic for the chemical distance in long-range percolation

Fast Locating with the RLBWT

Good Things Come in LogLog(n)-Sized Packages: Robustness with Small Quorums

Zero forcing number of graphs

On a relational theory of biological systems: a natural model for complex biological behavior

Further Approximations for Demand Matching: Matroid Constraints and Minor-Closed Graphs

Periodic Patrols on the Line and Other Networks

Successive Rank-One Approximations for Nearly Orthogonally Decomposable Symmetric Tensors

Distributed SAGA: Maintaining linear convergence rate with limited communication

Solving Almost all Systems of Random Quadratic Equations

Gradient Descent Can Take Exponential Time to Escape Saddle Points

Learning to Generate Chairs with Generative Adversarial Nets

On the ‘Calligraphy’ of Books

Solving the Conjugacy Decision Problem via Machine Learning

Discriminatively Learned Hierarchical Rank Pooling Networks

Learning End-to-end Multimodal Sensor Policies for Autonomous Navigation

A Novel/Old Modification of the First Zagreb Index

Fine-grained acceleration control for autonomous intersection management using deep reinforcement learning

The Bispectrum and Its Relationship to Phase-Amplitude Coupling

On a Dehn-Sommerville functional for simplicial complexes

The Approximation Properties of Copulas by Mixtures

MOBA: a New Arena for Game AI

Unsupervised Person Re-identification: Clustering and Fine-tuning

Asymptotic Properties of the Maximum Likelihood Estimator in Regime Switching Econometric Models

An EM Algorithm for Estimating an Oral Reading Speed and Accuracy Model

Robust Tracking Using Region Proposal Networks

Gaussian Variant of Freivalds’ Algorithm for Efficient and Reliable Matrix Product Verification

RSI-CB: A Large Scale Remote Sensing Image Classification Benchmark via Crowdsource Data

Deep-LMS for gigabit transmission over unshielded twisted pair cables

The Numerics of GANs

Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication

Vertex transitive graphs $G$ with $χ_D(G) > χ(G)$ and small automorphism group

Estimation of the lead-lag parameter between two stochastic processes driven by a fractional Brownian motion

On the Fundamental Limits of Random Non-orthogonal Multiple Access in Cellular Massive IoT

Multi-Modal Imitation Learning from Unstructured Demonstrations using Generative Adversarial Nets

Mod-$φ$ convergence, II: Estimates on the speed of convergence

Bayesian Clustering and Dimension Reduction in Multivariate Extremes

Joint auto-encoders: a flexible multi-task learning framework

Zonotope hit-and-run for efficient sampling from projection DPPs

Online to Offline Conversions and Adaptive Minibatch Sizes

Implications of Decentralized Q-learning Resource Allocation in Wireless Networks

Is the annual growth rate in balance of trade time series for Ireland nonlinear

Diversity Combining for RF Energy Harvesting

Secret sharing on large girth graphs

On the TASEP with second class particles

Parcellation of Visual Cortex on high-resolution histological Brain Sections using Convolutional Neural Networks

Saliency Revisited: Analysis of Mouse Movements versus Fixations

A Faster Construction of Phylogenetic Consensus Trees

Diffuse Behaviour of Ergodic Sums Over Rotations

Interpreting and Extending The Guided Filter Via Cyclic Coordinate Descent

Machine learning for precision psychiatry

End-to-end Active Object Tracking via Reinforcement Learning

The complexity of recognizing minimally tough graphs

Multi-Focus Image Fusion Via Coupled Sparse Representation and Dictionary Learning

Some estimates for the higher eigenvalues of sets close to the ball

Finite Ramsey degrees and Fraïssé expansions with the Ramsey property

Nighttime sky/cloud image segmentation

Universal secure rank-metric coding schemes with optimal communication overheads

(Quantum) Min-Entropy Resources

The Dynamic Bowser Routing Problem

Grammatical Inference as a Satisfiability Modulo Theories Problem

Optimizing Trade-offs Among Stakeholders in Real-Time Bidding by Incorporating Multimedia Metrics

The Logarithmic Funnel Heap: A Statistically Self-Similar Priority Queue

Discovering Visual Concept Structure with Sparse and Incomplete Tags

Random Matrices with Slow Correlation Decay

Long-time limits and occupation times for stable Fleming-Viot processes with decaying sampling rates

Feature Squeezing Mitigates and Detects Carlini/Wagner Adversarial Examples

Deep Learning is Robust to Massive Label Noise

Localized Gaussian width of $M$-convex hulls with applications to Lasso and convex aggregation

ResnetCrowd: A Residual Deep Learning Architecture for Crowd Counting, Violent Behaviour Detection and Crowd Density Level Classification

On a conjecture of George Beck

Multi-Labelled Value Networks for Computer Go

Cautious Model Predictive Control using Gaussian Process Regression

Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness

Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs

Multi-View Task-Driven Recognition in Visual Sensor Networks

Addressing Ambiguity in Multi-target Tracking by Hierarchical Strategy

A method for constructing parity-check matrices of non-binary quasi-cyclic LDPC codes

Hilbert series for twisted commutative algebras

Low Impact Artificial Intelligences

Fast Regression with an $\ell_\infty$ Guarantee

Strength Factors: An Uncertainty System for a Quantified Modal Logic

A geometric perspective on Landau’s problem over function fields

Deep manifold-to-manifold transforming network for action recognition

The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics

Efficient Decentralized Visual Place Recognition From Full-Image Descriptors

Generating Steganographic Text with LSTMs

The Cramer Distance as a Solution to Biased Wasserstein Gradients

Knowledge Base Completion: Baselines Strike Back

A Kernel Redundancy Removing Policy for Convolutional Neural Network

Recurrent Estimation of Distributions

Tutte Polynomials of Symmetric Hyperplane Arrangements

A Low Dimensionality Representation for Language Variety Identification

Generative Models of Visually Grounded Imagination

Reflection Invariant and Symmetry Detection

Forward-Backward Selection with Early Dropping