- title: 'Semi-supervised learning, causality, and the conditional cluster assumption'
abstract: 'While the success of semi-supervised learning (SSL) is still not fully understood, Schölkopf et al. (2012) have established a link to the principle of independent causal mechanisms. They conclude that SSL should be impossible when predicting a target variable from its causes, but possible when predicting it from its effects. Since both these cases are restrictive, we extend their work by considering classification using cause and effect features at the same time, such as predicting a disease from both risk factors and symptoms. While standard SSL exploits information contained in the marginal distribution of all inputs (to improve the estimate of the conditional distribution of the target given in-puts), we argue that in our more general setting we should use information in the conditional distribution of effect features given causal features. We explore how this insight generalises the previous understanding, and how it relates to and can be exploited algorithmically for SSL.'
volume: 124
URL: https://proceedings.mlr.press/v124/kugelgen20a.html
PDF: http://proceedings.mlr.press/v124/kugelgen20a/kugelgen20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-kugelgen20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Julius
family: Kügelgen
- given: Alexander
family: Mey
- given: Marco
family: Loog
- given: Bernhard
family: Schölkopf
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1-10
id: kugelgen20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1
lastpage: 10
published: 2020-08-27 00:00:00 +0000
- title: 'Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise'
abstract: 'Greedy-GQ is an off-policy two timescale algorithm for optimal control in reinforcement learning. This paper develops the first finite-sample analysis for the Greedy-GQ algorithm with linear function approximation under Markovian noise. Our finite-sample analysis provides theoretical justification for choosing stepsizes for this two timescale algorithm for faster convergence in practice, and suggests a trade-off between the convergence rate and the quality of the obtained policy. Our paper extends the finite-sample analyses of two timescale reinforcement learning algorithms from policy evaluation to optimal control, which is of more practical interest. Specifically, in contrast to existing finite-sample analyses for two timescale methods, e.g., GTD, GTD2 and TDC, where their objective functions are convex, the objective function of the Greedy-GQ algorithm is non-convex. Moreover, the Greedy-GQ algorithm is also not a linear two-timescale stochastic approximation algorithm. Our techniques in this paper provide a general framework for finite-sample analysis of non-convex value-based reinforcement learning algorithms for optimal control.'
volume: 124
URL: https://proceedings.mlr.press/v124/wang20a.html
PDF: http://proceedings.mlr.press/v124/wang20a/wang20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-wang20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Yue
family: Wang
- given: Shaofeng
family: Zou
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 11-20
id: wang20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 11
lastpage: 20
published: 2020-08-27 00:00:00 +0000
- title: 'PAC-Bayesian Contrastive Unsupervised Representation Learning'
abstract: 'Contrastive unsupervised representation learning (CURL) is the state-of-the-art technique to learn representations (as a set of features) from unlabelled data. While CURL has collected several empirical successes recently, theoretical understanding of its performance was still missing. In a recent work, Arora et al. (2019) provide the first generalisation bounds for CURL, relying on a Rademacher complexity. We extend their framework to the flexible PAC-Bayes setting, allowing to deal with the non-iid setting. We present PAC-Bayesian generalisation bounds for CURL, which are then used to derive a new representation learning algorithm. Numerical experiments on real-life datasets illustrate that our algorithm achieves competitive accuracy, and yields non-vacuous generalisation bounds.'
volume: 124
URL: https://proceedings.mlr.press/v124/nozawa20a.html
PDF: http://proceedings.mlr.press/v124/nozawa20a/nozawa20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-nozawa20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Kento
family: Nozawa
- given: Pascal
family: Germain
- given: Benjamin
family: Guedj
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 21-30
id: nozawa20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 21
lastpage: 30
published: 2020-08-27 00:00:00 +0000
- title: 'Static and Dynamic Values of Computation in MCTS'
abstract: 'Monte-Carlo Tree Search (MCTS) is one of the most-widely used methodsfor planning, and has powered many recent advances in artificialintelligence. In MCTS, one typically performs computations(i.e., simulations) to collect statistics about the possible futureconsequences of actions, and then chooses accordingly. Manypopular MCTS methods such as UCT and its variants decide whichcomputations to perform by trading-off exploration and exploitation. Inthis work, we take a more direct approach, and explicitly quantify thevalue of a computation based on its expected impact on the quality ofthe action eventually chosen. Our approach goes beyond the \emph{myopic}limitations of existing computation-value-based methods in two senses:(I) we are able to account for the impact of non-immediate (ie, future)computations (II) on non-immediate actions. We show that policies thatgreedily optimize computation values are optimal under certainassumptions and obtain results that are competitive with thestate-of-the-art.'
volume: 124
URL: https://proceedings.mlr.press/v124/sezener20a.html
PDF: http://proceedings.mlr.press/v124/sezener20a/sezener20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-sezener20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Eren
family: Sezener
- given: Peter
family: Dayan
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 31-40
id: sezener20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 31
lastpage: 40
published: 2020-08-27 00:00:00 +0000
- title: 'Kernel Conditional Moment Test via Maximum Moment Restriction'
abstract: 'We propose a new family of specification tests called kernel conditional moment (KCM) tests. Our tests are built on a novel representation of conditional moment restrictions in a reproducing kernel Hilbert space (RKHS) called conditional moment embedding (CMME). After transforming the conditional moment restrictions into a continuum of unconditional counterparts, the test statistic is defined as the maximum moment restriction (MMR) within the unit ball of the RKHS. We show that the MMR not only fully characterizes the original conditional moment restrictions, leading to consistency in both hypothesis testing and parameter estimation, but also has an analytic expression that is easy to compute as well as closed-form asymptotic distributions. Our empirical studies show that the KCM test has a promising finite-sample performance compared to existing tests.'
volume: 124
URL: https://proceedings.mlr.press/v124/muandet20a.html
PDF: http://proceedings.mlr.press/v124/muandet20a/muandet20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-muandet20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Krikamol
family: Muandet
- given: Wittawat
family: Jitkrittum
- given: Jonas
family: Kübler
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 41-50
id: muandet20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 41
lastpage: 50
published: 2020-08-27 00:00:00 +0000
- title: 'Bounding the expected run-time of nonconvex optimization with early stopping'
abstract: ' This work examines the convergence of stochastic gradient-based optimization algorithms that use early stopping based on a validation function. The form of early stopping we consider is that optimization terminates when the norm of the gradient of a validation function falls below a threshold. We derive conditions that guarantee this stopping rule is well-defined, and provide bounds on the expected number of iterations and gradient evaluations needed to meet this criterion. The guarantee accounts for the distance between the training and validation sets, measured with the Wasserstein distance. We develop the approach in the general setting of a first-order optimization algorithm, with possibly biased update directions subject to a geometric drift condition. We then derive bounds on the expected running time for early stopping variants of several algorithms, including stochastic gradient descent (SGD), decentralized SGD (DSGD), and the stochastic variance reduced gradient (SVRG) algorithm. Finally, we consider the generalization properties of the iterate returned by early stopping.'
volume: 124
URL: https://proceedings.mlr.press/v124/flynn20a.html
PDF: http://proceedings.mlr.press/v124/flynn20a/flynn20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-flynn20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Thomas
family: Flynn
- given: Kwangmin
family: Yu
- given: Abid
family: Malik
- given: Nicholas
family: D’Imperio
- given: Shinjae
family: Yoo
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 51-60
id: flynn20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 51
lastpage: 60
published: 2020-08-27 00:00:00 +0000
- title: 'Amortized variance reduction for doubly stochastic objective'
abstract: 'Approximate inference in complex probabilistic models such as deep Gaussian processes requires the optimisation of doubly stochastic objective functions. These objectives incorporate randomness both from mini-batch subsampling of the data and from Monte Carlo estimation of expectations. If the gradient variance is high, the stochastic optimisation problem becomes difficult with a slow rate of convergence. Control variates can be used to reduce the variance, but past approaches do not take into account how mini-batch stochasticity affects sampling stochasticity, resulting in sub-optimal variance reduction. We propose a new approach in which we use a recognition network to cheaply approximate the optimal control variate for each mini-batch, with no additional model gradient computations. We illustrate the properties of this proposal and test its performance on logistic regression and deep Gaussian processes.'
volume: 124
URL: https://proceedings.mlr.press/v124/boustati20a.html
PDF: http://proceedings.mlr.press/v124/boustati20a/boustati20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-boustati20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Ayman
family: Boustati
- given: Sattar
family: Vakili
- given: James
family: Hensman
- given: ST
family: John
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 61-70
id: boustati20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 61
lastpage: 70
published: 2020-08-27 00:00:00 +0000
- title: 'Randomized Exploration for Non-Stationary Stochastic Linear Bandits'
abstract: 'We investigate two perturbation approaches to overcome conservatism that optimism based algorithms chronically suffer from in practice. The first approach replaces optimism with a simple randomization when using confidence sets. The second one adds random perturbations to its current estimate before maximizing the expected reward. For non-stationary linear bandits, where each action is associated with a $d$-dimensional feature and the unknown parameter is time-varying with total variation $B_T$, we propose two randomized algorithms, Discounted Randomized LinUCB (D-RandLinUCB) and Discounted Linear Thompson Sampling (D-LinTS) via the two perturbation approaches. We highlight the statistical optimality versus computational efficiency trade-off between them in that the former asymptotically achieves the optimal dynamic regret $\tilde{O}(d ^{2/3}B_T^{1/3} T^{2/3})$, but the latter is oracle-efficient with an extra logarithmic factor in the number of arms compared to minimax-optimal dynamic regret. In a simulation study, both algorithms show the outstanding performance in tackling conservatism issue that Discounted LinUCB struggles with.'
volume: 124
URL: https://proceedings.mlr.press/v124/kim20a.html
PDF: http://proceedings.mlr.press/v124/kim20a/kim20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-kim20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Baekjin
family: Kim
- given: Ambuj
family: Tewari
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 71-80
id: kim20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 71
lastpage: 80
published: 2020-08-27 00:00:00 +0000
- title: 'Divergence-Based Motivation for Online EM and Combining Hidden Variable Models'
abstract: 'Expectation-Maximization (EM) is a prominent approach for parameter estimation of hidden (aka latent) variable models. Given the full batch of data, EM forms an upper-bound of the negative log-likelihood of the model at each iteration and updates to the minimizer of this upper-bound. We first provide a “model level” interpretation of the EM upper-bound as a sum of relative entropy divergences to a set of singleton models induced by the batch of observations. Our alternative motivation unifies the “observation level” and the “model level” view of the EM. As a result, we formulate an online version of the EM algorithm by adding an analogous inertia term which is a relative entropy divergence to the old model. Our motivation is more widely applicable than the previous approaches and leads to simple online updates for mixture of exponential distributions, hidden Markov models, and the first known online update for Kalman filters. Additionally, the finite sample form of the inertia term lets us derive online updates when there is no closed-form solution. Finally, we extend the analysis to the distributed setting where we motivate a systematic way of combining multiple hidden variable models. Experimentally, we validate the results on synthetic as well as real-world datasets.'
volume: 124
URL: https://proceedings.mlr.press/v124/amid20a.html
PDF: http://proceedings.mlr.press/v124/amid20a/amid20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-amid20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Ehsan
family: Amid
- given: Manfred
family: K. Warmuth
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 81-90
id: amid20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 81
lastpage: 90
published: 2020-08-27 00:00:00 +0000
- title: 'Iterative Channel Estimation for Discrete Denoising under Channel Uncertainty'
abstract: 'We propose a novel iterative channel estimation (ICE) algorithm that essentially removes the critical known noisy channel assumption for universal discrete denoising problem. Our algorithm is based on Neural DUDE (N-DUDE), a recently proposed neural network-based discrete denoiser, and it estimates the channel transition matrix as well as the neural network parameters in an alternating manner until convergence. While we do not make any probabilistic assumption on the underlying clean data, our ICE resembles Expectation-Maximization (EM) with variational approximation, and it takes advantage of the property that N-DUDE can always induce a marginal posterior distribution of the clean data. We carefully validate the channel estimation quality of ICE, and with extensive experiments on several radically different types of data, we show the ICE equipped neural network-based denoisers can perform \emph{universally} well regardless of the uncertainties in both the channel and the clean source. Moreover, we show ICE becomes extremely robust to its hyperparameters, and show the denoisers with ICE significantly outperform the strong baseline that can handle the channel uncertainties for denoising, the widely used Baum-Welch (BW) algorithm for hidden Markov models (HMM).'
volume: 124
URL: https://proceedings.mlr.press/v124/ahn20a.html
PDF: http://proceedings.mlr.press/v124/ahn20a/ahn20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-ahn20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Hongjoon
family: Ahn
- given: Taesup
family: Moon
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 91-100
id: ahn20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 91
lastpage: 100
published: 2020-08-27 00:00:00 +0000
- title: 'Nonparametric Fisher Geometry with Application to Density Estimation'
abstract: 'It is well known that the Fisher information induces a Riemannian geometry on parametric families of probability density functions. Following recent work, we consider the nonparametric generalization of the Fisher geometry. The resulting nonparametric Fisher geometry is shown to be equivalent to a familiar, albeit infinite-dimensional, geometric object—the sphere. By shifting focus away from density functions and toward square-root density functions, one may calculate theoretical quantities of interest with ease. More importantly, the sphere of square-root densities is much more computationally tractable. As discussed here, this insight leads to a novel Bayesian nonparametric density estimation model.'
volume: 124
URL: https://proceedings.mlr.press/v124/holbrook20a.html
PDF: http://proceedings.mlr.press/v124/holbrook20a/holbrook20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-holbrook20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Andrew
family: Holbrook
- given: Shiwei
family: Lan
- given: Jeffrey
family: Streets
- given: Babak
family: Shahbaba
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 101-110
id: holbrook20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 101
lastpage: 110
published: 2020-08-27 00:00:00 +0000
- title: 'Learning Intrinsic Rewards as a Bi-Level Optimization Problem'
abstract: 'We reinterpret the problem of finding intrinsic rewards in reinforcement learning (RL) as a bilevel optimization problem. Using this interpretation, we can make use of recent advancements in the hyperparameter optimization literature, mainly from Self-Tuning Networks (STN), to learn intrinsic rewards. To facilitate our methods, we introduces a new general conditioning layer: Conditional Layer Normalization (CLN). We evaluate our method on several continuous control benchmarks in the Mujoco physics simulator. On all of these benchmarks, the intrinsic rewards learned on the fly lead to higher final rewards.'
volume: 124
URL: https://proceedings.mlr.press/v124/stadie20a.html
PDF: http://proceedings.mlr.press/v124/stadie20a/stadie20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-stadie20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Bradly
family: Stadie
- given: Lunjun
family: Zhang
- given: Jimmy
family: Ba
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 111-120
id: stadie20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 111
lastpage: 120
published: 2020-08-27 00:00:00 +0000
- title: 'Regret Bounds for Decentralized Learning in Cooperative Multi-Agent Dynamical Systems'
abstract: 'Regret analysis is challenging in Multi-Agent Reinforcement Learning (MARL) primarily due to the dynamical environments and the decentralized information among agents. We attempt to solve this challenge in the context of decentralized learning in multi-agent linear-quadratic (LQ) dynamical systems. We begin with a simple setup consisting of two agents and two dynamically decoupled stochastic linear systems, each system controlled by an agent. The systems are coupled through a quadratic cost function. When both systems’ dynamics are unknown and there is no communication among the agents, we show that no learning policy can generate sub-linear in $T$ regret, where $T$ is the time horizon. When only one system’s dynamics are unknown and there is one-directional communication from the agent controlling the unknown system to the other agent, we propose a MARL algorithm based on the construction of an auxiliary single-agent LQ problem. The auxiliary single-agent problem in the proposed MARL algorithm serves as an implicit coordination mechanism among the two learning agents. This allows the agents to achieve a regret within $O(\sqrt{T})$ of the regret of the auxiliary single-agent problem. Consequently, using existing results for single-agent LQ regret, our algorithm provides a $\tilde{O}(\sqrt{T})$ regret bound. (Here $\tilde{O}(\cdot)$ hides constants and logarithmic factors). Our numerical experiments indicate that this bound is matched in practice. From the two-agent problem, we extend our results to multi-agent LQ systems with certain communication patterns which appear in vehicle platoon control.'
volume: 124
URL: https://proceedings.mlr.press/v124/mohammad-asghari20a.html
PDF: http://proceedings.mlr.press/v124/mohammad-asghari20a/mohammad-asghari20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-mohammad-asghari20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Seyed
family: Mohammad Asghari
- given: Yi
family: Ouyang
- given: Ashutosh
family: Nayyar
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 121-130
id: mohammad-asghari20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 121
lastpage: 130
published: 2020-08-27 00:00:00 +0000
- title: 'Learning Behaviors with Uncertain Human Feedback'
abstract: 'Human feedback is widely used to train agents in many domains. However, previous works rarely consider the uncertainty when humans provide feedback, especially in cases that the optimal actions are not obvious to the trainers. For example, the reward of a sub-optimal action can be stochastic and sometimes exceeds that of the optimal action, which is common in games or real-world. Trainers are likely to provide positive feedback to sub-optimal actions, negative feedback to the optimal actions and even do not provide feedback in some confusing situations. Existing works, which utilize the Expectation Maximization (EM) algorithm and treat the feedback model as hidden parameters, do not consider uncertainties in the learning environment and human feedback. To address this challenge, we introduce a novel feedback model that considers the uncertainty of human feedback. However, this incurs intractable calculus in the EM algorithm. To this end, we propose a novel approximate EM algorithm, in which we approximate the expectation step with the Gradient Descent method. Experimental results in both synthetic scenarios and two real-world scenarios with human participants demonstrate the superior performance of our proposed approach.'
volume: 124
URL: https://proceedings.mlr.press/v124/he20a.html
PDF: http://proceedings.mlr.press/v124/he20a/he20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-he20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Xu
family: He
- given: Haipeng
family: Chen
- given: Bo
family: An
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 131-140
id: he20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 131
lastpage: 140
published: 2020-08-27 00:00:00 +0000
- title: 'Regret Analysis of Bandit Problems with Causal Background Knowledge'
abstract: 'We study how to learn optimal interventions sequentially given causal information represented as a causal graph along with associated conditional distributions. Causal modeling is useful in real world problems like online advertisement where complex causal mechanisms underlie the relationship between interventions and outcomes. We propose two algorithms, causal upper confidence bound (C-UCB) and causal Thompson Sampling (C-TS), that enjoy improved cumulative regret bounds compared with algorithms that do not use causal information. We thus resolve an open problem posed by Lattimore et al. (2016). Further, we extend C-UCB and C-TS to the linear bandit setting and propose causal linear UCB (CL-UCB) and causal linear TS (CL-TS) algorithms. These algorithms enjoy a cumulative regret bound that only scales with the feature dimension. Our experiments show the benefit of using causal information. For example, we observe that even with a few hundreds of iterations, the regret of causal algorithms is less than that of standard algorithms by a factor of three. We also show that under certain causal structures, our algorithms scale better than the standard bandit algorithms as the number of interventions increases.'
volume: 124
URL: https://proceedings.mlr.press/v124/lu20a.html
PDF: http://proceedings.mlr.press/v124/lu20a/lu20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-lu20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Yangyi
family: Lu
- given: Amirhossein
family: Meisami
- given: Ambuj
family: Tewari
- given: William
family: Yan
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 141-150
id: lu20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 141
lastpage: 150
published: 2020-08-27 00:00:00 +0000
- title: 'Evaluation of Causal Structure Learning Algorithms via Risk Estimation'
abstract: 'Recent years have seen many advances in methods for causal structure learning from data. The empirical assessment of such methods, however, is much less developed. Motivated by this gap, we pose the following question: how can one assess, in a given problem setting, the practical efficacy of one or more causal structure learning methods? We formalize the problem in a decision-theoretic framework, via a notion of expected loss or risk for the causal setting. We introduce a theoretical notion of causal risk as well as sample quantities that can be computed from data, and study the relationship between the two, both theoretically and through an extensive simulation study. Our results provide an assumptions-light framework for assessing causal structure learning methods that can be applied in a range of practical use-cases.'
volume: 124
URL: https://proceedings.mlr.press/v124/eigenmann20a.html
PDF: http://proceedings.mlr.press/v124/eigenmann20a/eigenmann20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-eigenmann20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Marco
family: Eigenmann
- given: Sach
family: Mukherjee
- given: Marloes
family: Maathuis
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 151-160
id: eigenmann20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 151
lastpage: 160
published: 2020-08-27 00:00:00 +0000
- title: 'Kidney Exchange with Inhomogeneous Edge Existence Uncertainty'
abstract: 'Patients with end-stage renal failure often find kidney donors who are willing to donate a life-saving kidney, but who are medically incompatible with the patients. Kidney exchanges are organized barter markets that allow such incompatible patient-donor pairs to enter as a single agent—where the patient is endowed with a donor “item”—and engage in trade with other similar agents, such that all agents “give” a donor organ if and only if they receive an organ in return. In practice, organized trades occur in large cyclic or chain-like structures, with multiple agents participating in the exchange event. Planned trades can fail for a variety of reasons, such as unforeseen logistical challenges, or changes in patient or donor health. These failures cause major inefficiency in fielded exchanges, as if even one individual trade fails in a planned cycle or chain, \emph{all or most of the resulting cycle or chain fails}. Ad-hoc, as well as optimization-based methods, have been developed to handle failure uncertainty; nevertheless, the majority of the existing methods use very simplified assumptions about failure uncertainty and/or are not scalable for real-world kidney exchanges.Motivated by kidney exchange, we study a stochastic cycle and chain packing problem, where we aim to identify structures in a directed graph to maximize the expectation of matched edge weights. All edges are subject to failure, and the failures can have nonidentical probabilities. To the best of our knowledge, the state-of-the-art approaches are only tractable when failure probabilities are identical. We formulate a relevant non-convex optimization problem and propose a tractable mixed-integer linear programming reformulation to solve it. In addition, we propose a model that integrates both risks and the expected utilities of the matching by incorporating conditional value at risk (CVaR) into the objective function, providing a robust formulation for this problem. Subsequently, we propose a sample-average-approximation (SAA) based approach to solve this problem. We test our approaches on data from the United Network for Organ Sharing (UNOS) and compare against state-of-the-art approaches. Our model provides better performance with the same running time as a leading deterministic approach (PICEF). Our CVaR extensions with an SAA-based method improves the $\alpha \times 100%$ ($0<\alpha\leq 1$) worst-case performance substantially compared to existing models.'
volume: 124
URL: https://proceedings.mlr.press/v124/bidkhori20a.html
PDF: http://proceedings.mlr.press/v124/bidkhori20a/bidkhori20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-bidkhori20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: hoda
family: bidkhori
- given: John
family: Dickerson
- given: Duncan
family: McElfresh
- given: Ke
family: Ren
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 161-170
id: bidkhori20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 161
lastpage: 170
published: 2020-08-27 00:00:00 +0000
- title: 'On the design of consequential ranking algorithms'
abstract: 'Ranking models are typically designed to optimize some measure of immediate utility to the users. As a result, they have been unable to anticipate an increasing number of undesirable long-term consequences of their proposed rankings, from fueling the spread of misinformation and increasing polarization to degrading social discourse. Can we design ranking models that anticipate the consequences of their proposed rankings and are able to avoid the undesirable ones? In this paper, we first introduce a joint representation of rankings and user dynamics using Markov decision processes. Then, we show that this representation greatly simplifies the construction of consequential ranking models that trade off theimmediate utility and the long-term welfare. In particular, we can obtain optimal consequential rankings by applying weighted sampling on the rankings provided by models that maximize measures of immediate utility. However, in practice, such a strategy may be inefficient and impractical, specially in high dimensional scenarios. To overcome this, we introduce an efficient gradient-based algorithm to learn parameterized consequential ranking models that effectively approximate optimal ones. We illustrate our methodology using synthetic and real data gathered from Reddit and show that our consequential rankings may mitigate the spread of misinformation and improve the civility of online discussions.'
volume: 124
URL: https://proceedings.mlr.press/v124/tabibian20a.html
PDF: http://proceedings.mlr.press/v124/tabibian20a/tabibian20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-tabibian20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Behzad
family: Tabibian
- given: Vicenç
family: Gómez
- given: Abir
family: De
- given: Bernhard
family: Schölkopf
- given: Manuel
family: Gomez Rodriguez
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 171-180
id: tabibian20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 171
lastpage: 180
published: 2020-08-27 00:00:00 +0000
- title: 'Fair Contextual Multi-Armed Bandits: Theory and Experiments'
abstract: 'When an AI system interacts with multiple users, it frequently needs to make allocation decisions. For instance, a virtual agent decides whom to pay attention to in a group, or a factory robot selects a worker to deliver a part.Demonstrating fairness in decision making is essential for such systems to be broadly accepted. We introduce a Multi-Armed Bandit algorithm with fairness constraints, where fairness is defined as a minimum rate at which a task or a resource is assigned to a user. The proposed algorithm uses contextual information about the users and the task and makes no assumptions on how the losses capturing the performance of different users are generated. We provide theoretical guarantees of performance and empirical results from simulation and an online user study. The results highlight the benefit of accounting for contexts in fair decision making, especially when users perform better at some contexts and worse at others. '
volume: 124
URL: https://proceedings.mlr.press/v124/chen20a.html
PDF: http://proceedings.mlr.press/v124/chen20a/chen20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-chen20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Yifang
family: Chen
- given: Alex
family: Cuellar
- given: Haipeng
family: Luo
- given: Jignesh
family: Modi
- given: Heramb
family: Nemlekar
- given: Stefanos
family: Nikolaidis
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 181-190
id: chen20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 181
lastpage: 190
published: 2020-08-27 00:00:00 +0000
- title: 'Submodular Bandit Problem Under Multiple Constraints'
abstract: 'The linear submodular bandit problemwas proposedto simultaneously address diversified retrieval and online learning in a recommender system.If there is no uncertainty, this problem is equivalent toa submodular maximization problem under a cardinality constraint.However, in some situations, recommendation lists should satisfyadditional constraints such as budget constraints,other than a cardinality constraint.Thus, motivated by diversified retrieval considering budget constraints,we introduce a submodular bandit problem under the intersection of$l$ knapsacks and a $k$-system constraint.Here $k$-system constraints forma very general class of constraints includingcardinality constraints and the intersection of $k$ matroid constraints.To solve this problem, we propose a non-greedy algorithm that adaptively focuses ona standard or modified upper-confidence bound.We provide a high-probability upper bound of an approximation regret,where the approximation ratio matches that of a fast offline algorithm.Moreover, we perform experimentsunder various combinations of constraints using asynthetic and two real-world datasetsand demonstrate that our proposed method outperforms the existing baselines.'
volume: 124
URL: https://proceedings.mlr.press/v124/takemori20a.html
PDF: http://proceedings.mlr.press/v124/takemori20a/takemori20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-takemori20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Sho
family: Takemori
- given: Masahiro
family: Sato
- given: Takashi
family: Sonoda
- given: Janmajay
family: Singh
- given: Tomoko
family: Ohkuma
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 191-200
id: takemori20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 191
lastpage: 200
published: 2020-08-27 00:00:00 +0000
- title: 'Exploration Analysis in Finite-Horizon Turn-based Stochastic Games'
abstract: 'Exploration and exploitation trade-off is one of the key concerns in reinforcement learning. Previous work on one-player Markov Decision Processes has reached near-optimal results for both PAC and high probability regret guarantees. However, such an analysis is lacking for the more complex stochastic games with multi-players, where all players aim to find an approximate Nash Equilibrium. In this work, we address the exploration issue for the $N$-player finite-horizon turn-based stochastic games (FTSG). We propose a framework, \textit{Upper Bounding the Values for Players} (UBVP), to guide exploration in FTSGs. UBVP leverages the key insight that players choose the optimal policy conditioning on the policies of the others simultaneously; thus players can explore \textit{in the face of uncertainty} and get close to the Nash Equilibrium. Based on UBVP, we present two provable algorithms. One is \textit{Uniform}-PAC with a sample complexity of $\tilde{O}(1/\epsilon^2)$ to get an $\epsilon$-Nash Equilibrium for arbitrary $\epsilon>0$, and the other has a cumulative exploitability of $\tilde{O}(\sqrt{T})$ with high probability.'
volume: 124
URL: https://proceedings.mlr.press/v124/li20a.html
PDF: http://proceedings.mlr.press/v124/li20a/li20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-li20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Jialian
family: Li
- given: Yichi
family: Zhou
- given: Tongzheng
family: Ren
- given: Jun
family: Zhu
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 201-210
id: li20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 201
lastpage: 210
published: 2020-08-27 00:00:00 +0000
- title: 'Amortized Nesterov’s Momentum: A Robust Momentum and Its Application to Deep Learning'
abstract: 'This work proposes a novel momentum technique, the Amortized Nesterov’s Momentum, for stochastic convex optimization. The proposed method can be regarded as a smooth transition between Nesterov’s method and mirror descent. By tuning only a single parameter, users can trade Nesterov’s acceleration for robustness, that is, the variance control of the stochastic noise. Motivated by the recent success of using momentum in deep learning, we conducted extensive experiments to evaluate this new momentum in deep learning tasks. The results suggest that it can serve as a favorable alternative for Nesterov’s momentum.'
volume: 124
URL: https://proceedings.mlr.press/v124/zhou20a.html
PDF: http://proceedings.mlr.press/v124/zhou20a/zhou20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-zhou20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Kaiwen
family: Zhou
- given: Yanghua
family: Jin
- given: Qinghua
family: Ding
- given: James
family: Cheng
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 211-220
id: zhou20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 211
lastpage: 220
published: 2020-08-27 00:00:00 +0000
- title: 'Testing Goodness of Fit of Conditional Density Models with Kernels'
abstract: 'We propose two nonparametric statistical tests of goodness of fit for conditional distributions: given a conditional probability density function p(y|x) and a joint sample, decide whether the sample is drawn from p(y|x)q(x) for some density q(x). Our tests, formulated with a Stein operator, can be applied to any differentiable conditional density model, and require no knowledge of the normalizing constant. We show that 1) our tests are consistent against any fixed alternative conditional model; 2) the statistics can be estimated easily, requiring no density estimation as an intermediate step; and 3) our second test offers an interpretable test result providing insight on where the conditional model does not fit well in the domain of the covariate. We demonstrate the interpretability of our test on a task of modeling the distribution of New York City’s taxi drop-off location given a pick-up point. To our knowledge, our work is the first to propose such conditional goodness-of-fit tests that simultaneously have all these desirable properties.'
volume: 124
URL: https://proceedings.mlr.press/v124/jitkrittum20a.html
PDF: http://proceedings.mlr.press/v124/jitkrittum20a/jitkrittum20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-jitkrittum20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Wittawat
family: Jitkrittum
- given: Heishiro
family: Kanagawa
- given: Bernhard
family: Schölkopf
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 221-230
id: jitkrittum20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 221
lastpage: 230
published: 2020-08-27 00:00:00 +0000
- title: 'Scalable and Flexible Clustering of Grouped Data via Parallel and Distributed Sampling in Versatile Hierarchical Dirichlet Processes'
abstract: 'Adaptive clustering of grouped data is often done via the Hierarchical Dirichlet Process Mixture Model (HDPMM). That approach, however, is limited in its flexibility and usually does not scale well. As a remedy, we propose another, but closely related, hierarchical Bayesian nonparametric framework. Our main contributions are as follows. 1) a new model, called the Versatile HDPMM (vHDPMM), with two possible settings: full and reduced. While the latter is akin to the HDPMM’s setting, the former supports not only global features (as HDPMM does) but also local ones. 2) An effective mechanism for detecting global features. 3) A new sampler that addresses the challenges posed by the vHDPMM and, in the reduced setting, scales better than HDPMM samplers. 4) An efficient, distributed, and easily-modifiable implementation that offers more flexibility (even in the reduced setting) than publicly-available HDPMM implementations. Finally, we show the utility of the approach in applications such as image cosegmentation, visual topic modeling, and clustering with missing data.'
volume: 124
URL: https://proceedings.mlr.press/v124/dinari20a.html
PDF: http://proceedings.mlr.press/v124/dinari20a/dinari20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-dinari20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Or
family: Dinari
- given: Oren
family: Freifeld
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 231-240
id: dinari20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 231
lastpage: 240
published: 2020-08-27 00:00:00 +0000
- title: 'Statistically Efficient Greedy Equivalence Search'
abstract: 'We establish the theoretical foundation for statistically efficient variants of the Greedy Equivalence Search algorithm. If each node in the generative structure has at most $k$ parents, we show that in the limit of large data, we can recover that structure using greedy search with operator scores that condition on at most $k$ variables. We present simple synthetic experiments that compare a backward-only variantof the new algorithm to GES using finite data, showing increasing benefit of the new algorithm as the complexity of the generative model increases.'
volume: 124
URL: https://proceedings.mlr.press/v124/chickering20a.html
PDF: http://proceedings.mlr.press/v124/chickering20a/chickering20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-chickering20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Max
family: Chickering
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 241-249
id: chickering20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 241
lastpage: 249
published: 2020-08-27 00:00:00 +0000
- title: 'Robust Collective Classification against Structural Attacks'
abstract: 'Collective learning methods exploit relations among data points to enhance classification performance. However, such relations, represented as edges in the underlying graphical model, expose an extra attack surface to the adversaries. We study adversarial robustness of an important class of such graphical models, Associative Markov Networks (AMN), to structural attacks, where an attacker can modify the graph structure at test time. We formulate the task of learning a robust AMN classifier as a bi-level program, where the inner problem is a challenging non- linear integer program that computes optimal structural changes to the AMN. To address this technical challenge, we first relax the attacker problem, and then use duality to obtain a convex quadratic upper bound for the robust AMN problem. We then prove a bound on the quality of the resulting approximately optimal solutions, and experimentally demonstrate the efficacy of our approach. Finally, we apply our approach in a transductive learning setting, and show that robust AMN is much more robust than state-of-the-art deep learning methods, while sacrificing little in accuracy on non-adversarial data.'
volume: 124
URL: https://proceedings.mlr.press/v124/zhou20b.html
PDF: http://proceedings.mlr.press/v124/zhou20b/zhou20b.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-zhou20b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Kai
family: Zhou
- given: Yevgeniy
family: Vorobeychik
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 250-259
id: zhou20b
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 250
lastpage: 259
published: 2020-08-27 00:00:00 +0000
- title: 'Efficient Rollout Strategies for Bayesian Optimization'
abstract: 'Bayesian optimization (BO) is a class of sample-efficient global optimization methods, where a probabilistic model conditioned on previous observations is used to determine future evaluations via the optimization of an acquisition function. Most acquisition functions are myopic, meaning that they only consider the impact of the next function evaluation. Non-myopic acquisition functions consider the impact of the next h function evaluations and are typically computed through rollout, in which h steps of BO are simulated. These rollout acquisition functions are defined as h-dimensional integrals, and are expensive to compute and optimize. We show that a combination of quasi-Monte Carlo, common random numbers, and control variates significantly reduce the computational burden of rollout. We then formulate a policy-search based approach that removes the need to optimize the rollout acquisition function. Finally, we discuss the qualitative behavior of rollout policies in the setting of multi-modal objectives and model error.'
volume: 124
URL: https://proceedings.mlr.press/v124/lee20a.html
PDF: http://proceedings.mlr.press/v124/lee20a/lee20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-lee20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Eric
family: Lee
- given: David
family: Eriksson
- given: David
family: Bindel
- given: Bolong
family: Cheng
- given: Mike
family: Mccourt
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 260-269
id: lee20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 260
lastpage: 269
published: 2020-08-27 00:00:00 +0000
- title: 'IDA with Background Knowledge'
abstract: 'In this paper, we consider the problem of estimating all possible causal effects from observational data with two types of background knowledge: direct causal information and non-ancestral information. Following the IDA framework, we first provide locally valid orientation rules for maximal partially directed acyclic graphs (PDAGs), which are widely used to represent background knowledge. Based on the proposed rules, we present a fully local algorithm to estimate all possible causal effects with direct causal information. Furthermore, we consider non-ancestral information and prove that it can be equivalently transformed into direct causal information, meaning that we can also locally estimate all possible causal effects with non-ancestral information. The test results on both synthetic and real-world data sets show that our methods are efficient and stable.'
volume: 124
URL: https://proceedings.mlr.press/v124/fang20a.html
PDF: http://proceedings.mlr.press/v124/fang20a/fang20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-fang20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Zhuangyan
family: Fang
- given: Yangbo
family: He
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 270-279
id: fang20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 270
lastpage: 279
published: 2020-08-27 00:00:00 +0000
- title: 'Complete Dictionary Learning via $\ell_p$-norm Maximization'
abstract: 'Dictionary learning is a classic representation learning method that has been widely applied in signal processing and data analytics. In this paper, we investigate a family of $\ell_p$-norm ($p>2,p \in N$) maximization approaches for the complete dictionary learning problem from theoretical and algorithmic aspects. Specifically, we prove that the global maximizers of these formulations are very close to the true dictionary with high probability, even when Gaussian noise is present. Based on the generalized power method (GPM), an efficient algorithm is then developed for the $\ell_p$-based formulations. We further show the efficacy of the developed algorithm: for the population GPM algorithm over the sphere constraint, it first quickly enters the neighborhood of a global maximizer, and then converges linearly in this region. Extensive experiments will demonstrate that the $\ell_p$-based approaches enjoy a higher computational efficiency and better robustness than conventional approaches and $p=3$ performs the best.'
volume: 124
URL: https://proceedings.mlr.press/v124/shen20a.html
PDF: http://proceedings.mlr.press/v124/shen20a/shen20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-shen20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Yifei
family: Shen
- given: Ye
family: Xue
- given: Jun
family: Zhang
- given: Khaled
family: Letaief
- given: Vincent
family: Lau
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 280-289
id: shen20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 280
lastpage: 289
published: 2020-08-27 00:00:00 +0000
- title: 'Collapsible IDA: Collapsing Parental Sets for Locally Estimating Possible Causal Effects'
abstract: 'It is clear that some causal effects cannot be identified from observational data when the causal directed acyclic graph is absent. In such cases, IDA is a useful framework which estimates all possible causal effects by adjusting for all possible parental sets. In this paper, we combine the adjustment set selection procedure with the original IDA framework. Our goal is to find a common set that can be subtracted from all possible parental sets without influencing the back-door adjustment. To this end, we first introduce graphical conditions to decide whether a treatment’s neighbor or parent in a completed partially directed acyclic graph (CPDAG) can be subtracted and then provide a procedure to construct a subtractable set from those subtractable vertices. We next combine the procedure with the IDA framework and provide a fully local modification of IDA. Experimental results show that, with our modification, both the number of possible parental sets and the size of each possible parental set enumerated by the modified IDA decrease, making it possible to estimate all possible causal effects more efficiently.'
volume: 124
URL: https://proceedings.mlr.press/v124/liu20a.html
PDF: http://proceedings.mlr.press/v124/liu20a/liu20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-liu20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Yue
family: Liu
- given: Zhuangyan
family: Fang
- given: Yangbo
family: He
- given: Zhi
family: Geng
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 290-299
id: liu20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 290
lastpage: 299
published: 2020-08-27 00:00:00 +0000
- title: 'Learning Joint Nonlinear Effects from Single-variable Interventions in the Presence of Hidden Confounders'
abstract: 'We propose an approach to estimate the effect of multiple simultaneous interventions in the presence of hidden confounders. To overcome the problem of hidden confounding, we consider the setting where we have access to not only the observational data but also sets of single-variable interventions in which each of the treatment variables is intervened on separately. We prove identifiability under the assumption that the data is generated from a nonlinear continuous structural causal model with additive Gaussian noise. In addition, we propose a simple parameter estimation method by pooling all the data from different regimes and jointly maximizing the combined likelihood. We also conduct comprehensive experiments to verify the identifiability result as well as to compare the performance of our approach against a baseline on both synthetic and real-world data.'
volume: 124
URL: https://proceedings.mlr.press/v124/saengkyongam20a.html
PDF: http://proceedings.mlr.press/v124/saengkyongam20a/saengkyongam20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-saengkyongam20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Sorawit
family: Saengkyongam
- given: Ricardo
family: Silva
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 300-309
id: saengkyongam20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 300
lastpage: 309
published: 2020-08-27 00:00:00 +0000
- title: 'Causal screening in dynamical systems'
abstract: 'Many classical algorithms output graphical representations of causal structures by testing conditional independence among a set of random variables. In dynamical systems, local independence can be used analogously as a testable implication of the underlying data-generating process. We suggest some inexpensive methods for causal screening which provide output with a sound causal interpretation under the assumption of ancestral faithfulness. The popular model class of linear Hawkes processes is used to provide an example of a dynamical causal model. We argue that for sparse causal graphs the output will often be close to complete. We give examples of this framework and apply it to a challenging biological system.'
volume: 124
URL: https://proceedings.mlr.press/v124/wengel-mogensen20a.html
PDF: http://proceedings.mlr.press/v124/wengel-mogensen20a/wengel-mogensen20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-wengel-mogensen20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Søren
family: Wengel Mogensen
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 310-319
id: wengel-mogensen20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 310
lastpage: 319
published: 2020-08-27 00:00:00 +0000
- title: 'Bayesian Online Prediction of Change Points'
abstract: 'Online detection of instantaneous changes in the generative process of a data sequence generally focuses on retrospective inference of such change points without considering their future occurrences. We extend the Bayesian Online Change Point Detection algorithm to also infer the number of time steps until the next change point (i.e., the residual time). This enables to handle observation models which depend on the total segment duration, which is useful to model data sequences with temporal scaling. The resulting inference algorithm for segment detection can be deployed in an online fashion, and we illustrate applications to synthetic and to two medical real-world data sets.'
volume: 124
URL: https://proceedings.mlr.press/v124/agudelo-espana20a.html
PDF: http://proceedings.mlr.press/v124/agudelo-espana20a/agudelo-espana20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-agudelo-espana20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Diego
family: Agudelo-España
- given: Sebastian
family: Gomez-Gonzalez
- given: Stefan
family: Bauer
- given: Bernhard
family: Schölkopf
- given: Jan
family: Peters
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 320-329
id: agudelo-espana20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 320
lastpage: 329
published: 2020-08-27 00:00:00 +0000
- title: 'Walking on Two Legs: Learning Image Segmentation with Noisy Labels'
abstract: 'Image segmentation automatically segments a target object in an image and has recently achieved prominent progress due to the development of deep convolutional neural networks (DCNNs). However, the quality of manual labels plays an essential role in the segmentation accuracy, while in practice it could vary a lot and in turn could substantially mislead the training process and limit the effectiveness. In this paper, we propose a novel label refinement and sample reweighting method, and a novel generative adversarial network (GAN) is introduced to fuse these two models into an integrated framework. We evaluate our approach on the publicly available datasets, and the results show our approach to be competitive when compared with other state-of-the-art approaches dealing with the noisy labels in image segmentation.'
volume: 124
URL: https://proceedings.mlr.press/v124/cheng20a.html
PDF: http://proceedings.mlr.press/v124/cheng20a/cheng20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-cheng20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Guohua
family: Cheng
- given: Hongli
family: Ji
- given: Yan
family: Tian
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 330-339
id: cheng20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 330
lastpage: 339
published: 2020-08-27 00:00:00 +0000
- title: 'Election Control by Manipulating Issue Significance'
abstract: 'Integrity of elections is vital to democratic systems, but it is frequently threatened by malicious actors.The study of algorithmic complexity of the problem of manipulating election outcomes by changing its structural features is known as election control Rothe [2016].One means of election control that has been proposed, pertinent to the spatial voting model, is to select a subset of issues that determine voter preferences over candidates.We study a variation of this model in which voters have judgments about relative importance of issues, and a malicious actor can manipulate these judgments.We show that computing effective manipulations in this model is NP-hard even with two candidates or binary issues.However, we demonstrate that the problem becomes tractable with a constant number of voters or issues.Additionally, while it remains intractable when voters can vote stochastically, we exhibit an important special case in which stochastic voting behavior enables tractable manipulation.'
volume: 124
URL: https://proceedings.mlr.press/v124/estornell20a.html
PDF: http://proceedings.mlr.press/v124/estornell20a/estornell20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-estornell20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Andrew
family: Estornell
- given: Sanmay
family: Das
- given: Edith
family: Elkind
- given: Yevgeniy
family: Vorobeychik
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 340-349
id: estornell20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 340
lastpage: 349
published: 2020-08-27 00:00:00 +0000
- title: 'Coresets for Estimating Means and Mean Square Error with Limited Greedy Samples'
abstract: ' In a number of situations, collecting a function value for every data point may be prohibitively expensive, and random sampling ignores any structure in the underlying data. We introduce a scalable optimization algorithm with no correction steps (in contrast to Frank–Wolfe and its variants), a variant of gradient ascent for coreset selection in graphs, that greedily selects a weighted subset of vertices that are deemed most important to sample. Our algorithm estimates the mean of the function by taking a weighted sum only at these vertices, and we provably bound the estimation error in terms of the location and weights of the selected vertices in the graph. In addition, we consider the case where nodes have different selection costs and provide bounds on the quality of the low-cost selected coresets. We demonstrate the benefits of our algorithm on the semi-supervised node classification of graph convolutional neural network, point clouds and structured graphs, as well as sensor placement where the cost of placing sensors depends on the location of the placement. We also elucidate that the empirical convergence of our proposed method is faster than random selection and various clustering methods while still respecting sensor placement cost. The paper concludes with validation of the developed algorithm on both synthetic and real datasets, demonstrating that it outperforms the current state of the art.'
volume: 124
URL: https://proceedings.mlr.press/v124/vahidian20a.html
PDF: http://proceedings.mlr.press/v124/vahidian20a/vahidian20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-vahidian20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Saeed
family: Vahidian
- given: Baharan
family: Mirzasoleiman
- given: Alexander
family: Cloninger
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 350-359
id: vahidian20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 350
lastpage: 359
published: 2020-08-27 00:00:00 +0000
- title: 'Robust Spatial-Temporal Incident Prediction'
abstract: 'Spatio-temporal incident prediction is a central issue in law enforcement, with applications in fighting crimes like poaching, human trafficking, illegal fishing, burglaries and smuggling. However, state of the art approaches fail to account for evasion in response to predictive models, a common form of which is spatial shift in incident occurrence. We present a general approach for incident forecasting that is robust to spatial shifts. We propose two techniques for solving the resulting robust optimization problem: first, a constraint generation method guaranteed to yield an optimal solution, and second, a more scalable gradient-based approach. We then apply these techniques to both discrete-time and continuous-time robust incident forecasting. We evaluate our algorithms on two different real-world datasets, demonstrating that our approach is significantly more robust than conventional methods. '
volume: 124
URL: https://proceedings.mlr.press/v124/mukhopadhyay20a.html
PDF: http://proceedings.mlr.press/v124/mukhopadhyay20a/mukhopadhyay20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-mukhopadhyay20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Ayan
family: Mukhopadhyay
- given: Kai
family: Wang
- given: Andrew
family: Perrault
- given: Mykel
family: Kochenderfer
- given: Milind
family: Tambe
- given: Yevgeniy
family: Vorobeychik
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 360-369
id: mukhopadhyay20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 360
lastpage: 369
published: 2020-08-27 00:00:00 +0000
- title: 'Lagrangian Decomposition for Neural Network Verification'
abstract: 'A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. Previous methods have either used off-the-shelf solvers, discarding the problem structure, or relaxed the problem even further, making the bounds unnecessarily loose. We propose a novel approach based on Lagrangian Decomposition. Our formulation admits an efficient supergradient ascent algorithm, as well as an improved proximal algorithm. Both the algorithms offer three advantages: (i) they yield bounds that are provably at least as tight as previous dual algorithms relying on Lagrangian relaxations; (ii) they are based on operations analogous to forward/backward pass of neural networks layers and are therefore easily parallelizable, amenable to GPU implementation and able to take advantage of the convolutional structure of problems; and (iii) they allow for anytime stopping while still providing valid bounds. Empirically, we show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time, and obtain tighter bounds in the same time as previous dual algorithms. This results in an overall speed-up when employing the bounds for formal verification. Code for our algorithms is available at https://github.com/oval-group/decomposition-plnn-bounds.'
volume: 124
URL: https://proceedings.mlr.press/v124/bunel20a.html
PDF: http://proceedings.mlr.press/v124/bunel20a/bunel20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-bunel20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Rudy
family: Bunel
- given: Alessandro
family: De Palma
- given: Alban
family: Desmaison
- given: Krishnamurthy
family: Dvijotham
- given: Pushmeet
family: Kohli
- given: Philip
family: Torr
- given: M.
family: Pawan Kumar
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 370-379
id: bunel20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 370
lastpage: 379
published: 2020-08-27 00:00:00 +0000
- title: 'Robust modal regression with direct gradient approximation of modal regression risk'
abstract: 'Modal regression is aimed at estimating the global mode (i.e., global maximum) of the conditional density function of the output variable given input variables, and has led to regression methods robust against a wide-range of noises. A typical approach for modal regression takes a two-step approach of firstly approximating the modal regression risk (MRR) and of secondly maximizing the approximated MRR with some gradient method. However, this two-step approach can be suboptimal in gradient-based maximization methods because a good MRR approximator does not necessarily give a good gradient approximator of MRR. In this paper, we take a novel approach of \emph{directly} approximating the gradient of MRR in modal regression. Based on the direct approach, we first propose a modal regression method with reproducing kernels where a new update rule to estimate the conditional mode is derived based on a fixed-point method. Then, the derived update rule is theoretically investigated. Furthermore, since our direct approach is compatible with recent sophisticated stochastic gradient methods (e.g., Adam), another modal regression method is also proposed based on neural networks. Finally, the superior performance of the proposed methods is demonstrated on various artificial and benchmark datasets.'
volume: 124
URL: https://proceedings.mlr.press/v124/sasaki20a.html
PDF: http://proceedings.mlr.press/v124/sasaki20a/sasaki20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-sasaki20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Hiroaki
family: Sasaki
- given: Tomoya
family: Sakai
- given: Takafumi
family: Kanamori
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 380-389
id: sasaki20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 380
lastpage: 389
published: 2020-08-27 00:00:00 +0000
- title: 'A Simple Online Algorithm for Competing with Dynamic Comparators'
abstract: 'Online learning in dynamic environments has recently drawn considerable attention, where dynamic regret is usually employed to compare decisions of online algorithms to dynamic comparators. In previous works, dynamic regret bounds are typically established in terms of regularity of comparators $C_T$ or that of online functions $V_T$. Recently, Jadbabaie et al. [2015] propose an algorithm that can take advantage of both regularities and enjoy an $\tilde{O}(\sqrt{1+D_T} + \min\{\sqrt{(1+D_T)C_T}, (1+D_T)^{1/3}V_T^{1/3}T^{1/3}\})$ dynamic regret, where $D_T$ is an additional quantity to measure the niceness of environments. The regret bound adapts to the smaller regularity of problem environments and is tighter than all existing dynamic regret guarantees. Nevertheless, their algorithm involves non-convex programming at each iteration, and thus requires burdensome computations. In this paper, we design a simple algorithm based on the online ensemble, which provably enjoys the same (even slightly stronger) guarantee as the state-of-the-art rate, yet is much more efficient because our algorithm does not involve any non-convex problem solving. Empirical studies also verify the efficacy and efficiency.'
volume: 124
URL: https://proceedings.mlr.press/v124/zhang20a.html
PDF: http://proceedings.mlr.press/v124/zhang20a/zhang20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-zhang20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Yu-Jie
family: Zhang
- given: Peng
family: Zhao
- given: Zhi-Hua
family: Zhou
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 390-399
id: zhang20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 390
lastpage: 399
published: 2020-08-27 00:00:00 +0000
- title: 'Skewness Ranking Optimization for Personalized Recommendation'
abstract: 'In this paper, we propose a novel optimization criterion that leverages features of the skew normal distribution to better model the problem of personalized recommendation. Specifically, the developed criterion borrows the concept and the flexibility of the skew normal distribution, based on which three hyperparameters are attached to the optimization criterion. Furthermore, from a theoretical point of view, we not only establish the relation between the maximization of the proposed criterion and the shape parameter in the skew normal distribution, but also provide the analogies and asymptotic analysis of the proposed criterion to maximization of the area under the ROC curve. Experimental results conducted on a range of large-scale real-world datasets show that our model significantly outperforms the state of the art and yields consistently best performance on all tested datasets.'
volume: 124
URL: https://proceedings.mlr.press/v124/wang20c.html
PDF: http://proceedings.mlr.press/v124/wang20c/wang20c.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-wang20c.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Chuan-Ju
family: Wang
- given: Yu-Neng
family: Chuang
- given: Chih-Ming
family: Chen
- given: Ming-Feng
family: Tsai
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 400-409
id: wang20c
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 400
lastpage: 409
published: 2020-08-27 00:00:00 +0000
- title: 'High Dimensional Discrete Integration over the Hypergrid'
abstract: 'Recently Ermon et al. (2013) pioneered a way to practically compute approximations to large scale counting or discrete integration problems by using random hashes. The hashes are used to reduce the counting problem into many separate discrete optimization problems. The optimization problems then can be solved by an NP-oracle such as commercial SAT solvers or integer linear programming (ILP) solvers. In particular, Ermon et al. showed that if the domain of integration is $\{0,1\}^n$ then it is possible to obtain a solution within a factor of $16$ of the optimal (16-approximation) by this technique. In many crucial counting tasks, such as computation of partition function of ferromagnetic Potts model, the domain of integration is naturally $\{0,1,…, q-1\}^n, q>2$, the hypergrid. The straightforward extension of Ermon et al.’s method allows a $q^2$-approximation for this problem. For large values of $q$, this is undesirable. In this paper, we show an improved technique to obtain an approximation factor of $4+O(1/q^2)$ to this problem. We are able to achieve this by using an idea of optimization over multiple bins of the hash functions, that can be easily implemented by inequality constraints, or even in unconstrained way. The NP oracle in this setting can be simulated by using an ILP solver as in Ermon et. al. We provide simulation results to support the theoretical guarantees of our algorithms.'
volume: 124
URL: https://proceedings.mlr.press/v124/kumar-maity20a.html
PDF: http://proceedings.mlr.press/v124/kumar-maity20a/kumar-maity20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-kumar-maity20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Raj
family: Kumar Maity
- given: Arya
family: Mazumdar
- given: Soumyabrata
family: Pal
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 410-419
id: kumar-maity20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 410
lastpage: 419
published: 2020-08-27 00:00:00 +0000
- title: 'Neural Likelihoods via Cumulative Distribution Functions'
abstract: 'We leverage neural networks as universal approximators of monotonic functions to build a parameterization of conditional cumulative distribution functions (CDFs). By the application of automatic differentiation with respect to response variables and then to parameters of this CDF representation, we are able to build black box CDF and density estimators. A suite of families is introduced as alternative constructions for the multivariate case. At one extreme, the simplest construction is a competitive density estimator against state-of-the-art deep learning methods, although it does not provide an easily computable representation of multivariate CDFs. At the other extreme, we have a flexible construction from which multivariate CDF evaluations and marginalizations can be obtained by a simple forward pass in a deep neural net, but where the computation of the likelihood scales exponentially with dimensionality. Alternatives in between the extremes are discussed. We evaluate the different representations empirically on a variety of tasks involving tail area probabilities, tail dependence and (partial) density estimation.'
volume: 124
URL: https://proceedings.mlr.press/v124/chilinski20a.html
PDF: http://proceedings.mlr.press/v124/chilinski20a/chilinski20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-chilinski20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Pawel
family: Chilinski
- given: Ricardo
family: Silva
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 420-429
id: chilinski20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 420
lastpage: 429
published: 2020-08-27 00:00:00 +0000
- title: 'Unknown mixing times in apprenticeship and reinforcement learning'
abstract: 'We derive and analyze learning algorithms for apprenticeship learning, policy evaluation and policy gradient for average reward criteria. Existing algorithms explicitly require an upper bound on the mixing time. In contrast, we build on ideas from Markov chain theory and derive sampling algorithms that do not require such an upper bound. For these algorithms, we provide theoretical bounds on their sample-complexity and running time.'
volume: 124
URL: https://proceedings.mlr.press/v124/zahavy20a.html
PDF: http://proceedings.mlr.press/v124/zahavy20a/zahavy20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-zahavy20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Tom
family: Zahavy
- given: Alon
family: Cohen
- given: Haim
family: Kaplan
- given: Yishay
family: Mansour
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 430-439
id: zahavy20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 430
lastpage: 439
published: 2020-08-27 00:00:00 +0000
- title: 'TX-Ray: Quantifying and Explaining Model-Knowledge Transfer in (Un-)Supervised NLP'
abstract: 'While state-of-the-art NLP explainability (XAI) methods focus on explaining per-sample decisions in supervised end or probing tasks, this is insufficient to explain and quantify model knowledge transfer during (un-)supervised training. Thus, for TX-Ray, we modify the established computer vision explainability principle of ‘visualizing preferred inputs of neurons’ to make it usable for both NLP and for transfer analysis. This allows one to analyze, track and quantify how self- or supervised NLP models first build knowledge abstractions in pretraining (1), andthen transfer abstractions to a new domain (2), or adapt them during supervised finetuning (3) – see Fig. 1. TX-Ray expresses neurons as feature preference distributions to quantify fine-grained knowledge transfer or adaptation and guide human analysis. We find that, similar to Lottery Ticket based pruning, TX-Ray based pruning can improve test set generalization and that it can reveal how early stages of self-supervision automatically learn linguistic abstractions like parts-of-speech.'
volume: 124
URL: https://proceedings.mlr.press/v124/rethmeier20a.html
PDF: http://proceedings.mlr.press/v124/rethmeier20a/rethmeier20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-rethmeier20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Nils
family: Rethmeier
- given: Vageesh
family: Kumar Saxena
- given: Isabelle
family: Augenstein
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 440-449
id: rethmeier20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 440
lastpage: 449
published: 2020-08-27 00:00:00 +0000
- title: ' What You See May Not Be What You Get: UCB Bandit Algorithms Robust to $\varepsilon$-Contamination'
abstract: 'Motivated by applications of bandit algorithms in education, we consider a stochastic multi-armed bandit problem with $\varepsilon$-contaminated rewards. We allow an adversary to arbitrarily give unbounded contaminated rewards with full knowledge of the past and future. We impose only the constraint that at any time t the proportion of contaminated rewards for any actions is less than or equal to $\varepsilon$. We derive concentration inequalities for two robust mean estimators for sub-Gaussian distributions in the $\varepsilon$-contamination context. We define the $\varepsilon$-contaminated stochastic bandit problem and use our robust mean estimators to give two variants of a robust Upper Confidence Bound (UCB) algorithm, crUCB. Using regret derived from only the underlying stochastic rewards, both variants of crUCB achieve $O(\sqrt{KTlogT}$. Our simulations are designed to reflect reasonable settings a teacher would experience when implementing a bandit algorithm. We show that in certain adversarial regimes crUCB not only outperforms algorithms designed for stochastic (UCB1) and adversarial bandits (EXP3) but also those that have “best of both worlds” guarantees (EXP3++ and Tsallis-Inf) even when our constrainton the proportion of contaminated rewards is broken.'
volume: 124
URL: https://proceedings.mlr.press/v124/niss20a.html
PDF: http://proceedings.mlr.press/v124/niss20a/niss20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-niss20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Laura
family: Niss
- given: Ambuj
family: Tewari
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 450-459
id: niss20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 450
lastpage: 459
published: 2020-08-27 00:00:00 +0000
- title: 'The Hawkes Edge Partition Model for Continuous-time Event-based Temporal Networks'
abstract: 'We propose a novel probabilistic framework to model continuously generated interaction events data. Our goal is to infer the \emph{implicit} community structure underlying the temporal interactions among entities, and also to exploit how the latent structure influence their interaction dynamics. To this end, we model the reciprocating interactions between individuals using mutually-exciting Hawkes processes. The base rate of the Hawkes process for each pair of individuals is built upon the latent representations inferred using the hierarchical gamma process edge partition model (HGaP-EPM). In particular, our model allows the interaction dynamics between each pair of individuals to be modulated by their respective affiliated communities.Moreover, our model can flexibly incorporate the auxiliary individuals’ attributes, or covariates associated with interaction events. Efficient Gibbs sampling and Expectation-Maximization algorithms are developed to perform inference via Pólya-Gamma data augmentation strategy. Experimental results on real-world datasets demonstrate that our model not only achieves competitive performance compared with state-of-the-art methods, but also discovers interpretable latent structure behind the observed temporal interactions.'
volume: 124
URL: https://proceedings.mlr.press/v124/yang20a.html
PDF: http://proceedings.mlr.press/v124/yang20a/yang20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-yang20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Sikun
family: Yang
- given: Heinz
family: Koeppl
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 460-469
id: yang20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 460
lastpage: 469
published: 2020-08-27 00:00:00 +0000
- title: 'Learning by Repetition: Stochastic Multi-armed Bandits under Priming Effect'
abstract: 'We study the effect of persistence of engagement on learning in a stochastic multi-armed bandit setting. In advertising and recommendation systems, repetition effect includes a wear-in period, where the user’s propensity to reward the platform via a click or purchase depends on how frequently they see the recommendation in the recent past. It also includes a counteracting wear-out period, where the user’s propensity to respond positively is dampened if the recommendation was shown too many times recently. Priming effect can be naturally modelled as a temporal constraint on the strategy space, since the reward for the current action depends on historical actions taken by the platform. We provide novel algorithms that achieves sublinear regret in time and the relevant wear-in/wear-out parameters. The effect of priming on the regret upper bound is also additive, and we get back a guarantee that matches popular algorithms such as the UCB1 and Thompson sampling when there is no priming effect. Our work complements recent work on modeling time varying rewards, delays and corruptions in bandits, and extends the usage of rich behavior models in sequential decision making settings.'
volume: 124
URL: https://proceedings.mlr.press/v124/agrawal20a.html
PDF: http://proceedings.mlr.press/v124/agrawal20a/agrawal20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-agrawal20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Priyank
family: Agrawal
- given: Theja
family: Tulabandula
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 470-479
id: agrawal20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 470
lastpage: 479
published: 2020-08-27 00:00:00 +0000
- title: 'Compositional uncertainty in deep Gaussian processes'
abstract: 'Gaussian processes (GPs) are nonparametric priors over functions. Fitting a GP implies computing a posterior distribution of functions consistent with the observed data. Similarly, deep Gaussian processes (DGPs) should allow us to compute a posterior distribution of compositions of multiple functions giving rise to the observations. However, exact Bayesian inference is intractable for DGPs, motivating the use of various approximations. We show that the application of simplifying mean-field assumptions across the hierarchy leads to the layers of a DGP collapsing to near-deterministic transformations. We argue that such an inference scheme is suboptimal, not taking advantage of the potential of the model to discover the compositional structure in the data. To address this issue, we examine alternative variational inference schemes allowing for dependencies across different layers and discuss their advantages and limitations.'
volume: 124
URL: https://proceedings.mlr.press/v124/ustyuzhaninov20a.html
PDF: http://proceedings.mlr.press/v124/ustyuzhaninov20a/ustyuzhaninov20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-ustyuzhaninov20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Ivan
family: Ustyuzhaninov
- given: Ieva
family: Kazlauskaite
- given: Markus
family: Kaiser
- given: Erik
family: Bodin
- given: Neill
family: Campbell
- given: Carl
family: Henrik Ek
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 480-489
id: ustyuzhaninov20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 480
lastpage: 489
published: 2020-08-27 00:00:00 +0000
- title: 'Streaming Nonlinear Bayesian Tensor Decomposition'
abstract: 'Despite the success of the recent nonlinear tensor decomposition models based on Gaussian processes (GPs), they lack an effective way to deal with streaming data, which are important for many applications. Using the standard streaming variational Bayes framework or the recent streaming sparse GP approximations will lead to intractable model evidence lower bounds; although we can use stochastic gradient descent for incremental updates, they are unreliable and often yield poor estimations. To address this problem, we propose Streaming Nonlinear Bayesian Tensor Decomposition (SNBTD) that can conduct high-quality, closed-form and iteration-free updates upon receiving new tensor entries. Specifically, we use random Fourier features to build a sparse spectrum GP decomposition model to dispense with complex kernel/matrix operations and to ease posterior inference. We then extend the assumed-density-filtering framework by approximating all the data likelihoods in a streaming batch with a single factor to perform one-shot updates. We use conditional moment matching and Taylor approximations to fulfill efficient, analytical factor calculation. We show the advantage of our method on four real-world applications.'
volume: 124
URL: https://proceedings.mlr.press/v124/pan20a.html
PDF: http://proceedings.mlr.press/v124/pan20a/pan20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-pan20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Zhimeng
family: Pan
- given: Zheng
family: Wang
- given: Shandian
family: Zhe
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 490-499
id: pan20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 490
lastpage: 499
published: 2020-08-27 00:00:00 +0000
- title: 'Relaxed Multivariate Bernoulli Distribution and Its Applications to Deep Generative Models'
abstract: 'Recent advances in variational auto-encoder (VAE) have demonstrated the possibility of approximating the intractable posterior distribution with a variational distribution parameterized by a neural network. To optimize the variational objective of VAE, the reparameterization trick is commonly applied to obtain a low-variance estimator of the gradient. The main idea of the trick is to express the variational distribution as a differentiable function of parameters and a random variable with a fixed distribution. To extend the reparameterization trick to inference involving discrete latent variables, a common approach is to use a continuous relaxation of the categorical distribution as the approximate posterior. However, when applying continuous relaxation to the multivariate cases, multiple variables are typically assumed to be independent, making it suboptimal in applications where modeling dependency is crucial to the overall performance. In this work, we propose a multivariate generalization of the Relaxed Bernoulli distribution, which can be reparameterized and can capture the correlation between variables via a Gaussian copula. We demonstrate its effectiveness in two tasks: density estimation with Bernoulli VAE and semi-supervised multi-label classification.'
volume: 124
URL: https://proceedings.mlr.press/v124/wang20b.html
PDF: http://proceedings.mlr.press/v124/wang20b/wang20b.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-wang20b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Xi
family: Wang
- given: Junming
family: Yin
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 500-509
id: wang20b
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 500
lastpage: 509
published: 2020-08-27 00:00:00 +0000
- title: 'One-Bit Compressed Sensing via One-Shot Hard Thresholding'
abstract: 'This paper concerns the problem of 1-bit compressed sensing, where the goal is to estimate a sparse signal from a few of its binary measurements. We study a non-convex sparsity-constrained program and present a novel and concise analysis that moves away from the widely used notion of Gaussian width. We show that with high probability a simple algorithm is guaranteed to produce an accurate approximation to the normalized signal of interest under the L2-metric. On top of that, we establish an ensemble of new results that address norm estimation, support recovery, and model misspecification. On the computational side, it is shown that the non-convex program can be solved via one-step hard thresholding which is dramatically efficient in terms of time complexity and memory footprint. On the statistical side, it is shown that our estimator enjoys a near-optimal error rate under standard conditions. The theoretical results are further substantiated by numerical experiments.'
volume: 124
URL: https://proceedings.mlr.press/v124/shen20b.html
PDF: http://proceedings.mlr.press/v124/shen20b/shen20b.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-shen20b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Jie
family: Shen
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 510-519
id: shen20b
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 510
lastpage: 519
published: 2020-08-27 00:00:00 +0000
- title: 'GPIRT: A Gaussian Process Model for Item Response Theory'
abstract: 'The goal of item response theoretic (IRT) models is to provide estimates of latent traits from binary observed indicators and at the same time to learn the item response funcitons (IRFs) that map from latent trait to observed response. However, in many cases observed behavior can deviate significantly from the parametric assumptions of traditional IRT models. Nonparametric IRT (NIRT) models overcome these challenges by relaxing assumptions about the form of the IRFs, but standard tools are unable to simultaneously estimate flexible IRFs and recover ability estimates for respondents. We propose a Bayesian nonparametric model that solves this problem by placing Gaussian process priors on the latent functions defining the IRFs. This allows us to simultaneously relax assumptions about the shape of the IRFs while preserving the ability to estimate latent traits. This in turn allows us to easily extend the model to further tasks such as active learning. GPIRT therefore provides a simple and intuitive solution to several longstanding problems in the IRT literature.'
volume: 124
URL: https://proceedings.mlr.press/v124/duck-mayr20a.html
PDF: http://proceedings.mlr.press/v124/duck-mayr20a/duck-mayr20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-duck-mayr20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: JBrandon
family: Duck-Mayr
- given: Roman
family: Garnett
- given: Jacob
family: Montgomery
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 520-529
id: duck-mayr20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 520
lastpage: 529
published: 2020-08-27 00:00:00 +0000
- title: 'Identifying causal effects in maximally oriented partially directed acyclic graphs'
abstract: 'We develop a necessary and sufficient causal identification criterion for maximally oriented partially directed acyclic graphs (MPDAGs). MPDAGs as a class of graphs include directed acyclic graphs (DAGs), completed partially directed acyclic graphs (CPDAGs), and CPDAGs with added background knowledge. As such, they represent the type of graph that can be learned from observational data and background knowledge under the assumption of no latent variables. Our identification criterion can be seen as a generalization of the g-formula of Robins (1986). We further obtain a generalization of the truncated factorization formula for DAGs (Pearl, 2009) and compare our criterion to the generalized adjustment criterion of Perkovic et al. (2017) which is sufficient, but not necessary for causal identification.'
volume: 124
URL: https://proceedings.mlr.press/v124/perkovic20a.html
PDF: http://proceedings.mlr.press/v124/perkovic20a/perkovic20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-perkovic20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Emilija
family: Perkovic
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 530-539
id: perkovic20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 530
lastpage: 539
published: 2020-08-27 00:00:00 +0000
- title: 'Pairwise Supervised Hashing with Bernoulli Variational Auto-Encoder and Self-Control Gradient Estimator'
abstract: 'Semantic hashing has become a crucial component of fast similarity search in many large-scale information retrieval systems, in particular, for text data. Variational auto-encoders (VAEs) with binary latent variables as hashing codes provide state-of-the-art performance in terms of precision for document retrieval. We propose a pairwise loss function with discrete latent VAE to reward within-class similarity and between-class dissimilarity for supervised hashing. Instead of solving the optimization for training relying on existing biased gradient estimators, an unbiased, low-variance gradient estimator, which evaluates the non-differentiable loss function over two correlated sets of binary hashing codes to control the gradient variance, is adopted to optimize the hashing function to achieve superior performance compared to the state-of-the-arts, as demonstrated by our comprehensive experiments.'
volume: 124
URL: https://proceedings.mlr.press/v124/zamani-dadaneh20a.html
PDF: http://proceedings.mlr.press/v124/zamani-dadaneh20a/zamani-dadaneh20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-zamani-dadaneh20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Siamak
family: Zamani Dadaneh
- given: Shahin
family: Boluki
- given: Mingzhang
family: Yin
- given: Mingyuan
family: Zhou
- given: Xiaoning
family: Qian
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 540-549
id: zamani-dadaneh20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 540
lastpage: 549
published: 2020-08-27 00:00:00 +0000
- title: 'Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison'
abstract: 'We prove performance guarantees of two algorithms for approximating Q* in batch reinforcement learning. Compared to classical iterative methods such as Fitted Q-Iteration—whose performance loss incurs quadratic dependence on horizon—these methods estimate (some forms of) the Bellman error and enjoy linear-in-horizon error propagation, a property established for the first time for algorithms that rely solely on batch data and output stationary policies. One of the algorithms uses a novel and explicit importance-weighting correction to overcome the infamous "double sampling" difficulty in Bellman error estimation, and does not use any squared losses. Our analyses reveal its distinct characteristics and potential advantages compared to classical algorithms. '
volume: 124
URL: https://proceedings.mlr.press/v124/xie20a.html
PDF: http://proceedings.mlr.press/v124/xie20a/xie20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-xie20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Tengyang
family: Xie
- given: Nan
family: Jiang
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 550-559
id: xie20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 550
lastpage: 559
published: 2020-08-27 00:00:00 +0000
- title: 'Towards Threshold Invariant Fair Classification'
abstract: 'Effective machine learning models can automatically learn useful information from a large quantity of data and provide decisions in a high accuracy. These models may, however, lead to unfair predictions in certain sense among the population groups of interest, where the grouping is based on such sensitive attributes as race and gender. Various fairness definitions, such as demographic parity and equalized odds, were proposed in prior art to ensure that decisions guided by the machine learning models are equitable. Unfortunately, the "fair" model trained with these fairness definitions is threshold sensitive, i.e., the condition of fairness may no longer hold true when tuning the decision threshold. This paper introduces the notion of threshold invariant fairness, which enforces equitable performances across different groups independent of the decision threshold. To achieve this goal, this paper proposes to equalize the risk distributions among the groups via two approximation methods. Experimental results demonstrate that the proposed methodology is effective to alleviate the threshold sensitivity in machine learning models designed to achieve fairness.'
volume: 124
URL: https://proceedings.mlr.press/v124/chen20b.html
PDF: http://proceedings.mlr.press/v124/chen20b/chen20b.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-chen20b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Mingliang
family: Chen
- given: Min
family: Wu
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 560-569
id: chen20b
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 560
lastpage: 569
published: 2020-08-27 00:00:00 +0000
- title: 'Optimal Statistical Hypothesis Testing for Social Choice'
abstract: 'We address the following question in this paper: “What are the most robust statistical methods for social choice?” By leveraging the theory of uniformly least favorable distributions in the Neyman-Pearson framework to finite models and randomized tests, we characterize uniformly most powerful (UMP) tests, which is a well-accepted statistical optimality w.r.t. robustness, for testing whether a given alternative is the winner under Mallows’ model and under Condorcet’s model, respectively.'
volume: 124
URL: https://proceedings.mlr.press/v124/xia20a.html
PDF: http://proceedings.mlr.press/v124/xia20a/xia20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-xia20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Lirong
family: Xia
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 570-579
id: xia20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 570
lastpage: 579
published: 2020-08-27 00:00:00 +0000
- title: 'A SUPER* Algorithm to Optimize Paper Bidding in Peer Review'
abstract: 'A number of applications involve sequential arrival of users, and require showing each user an ordering of items. A prime example is the bidding process in conference peer review where reviewers enter the system sequentially, each reviewer needs to be shown the list of submitted papers, and the reviewer then "bids" to review some papers. The order of the papers shown has a significant impact on the bids due to primacy effects. In deciding on the ordering of the list of papers to show, there are two competing goals: (i) obtaining sufficiently many bids for each paper, and (ii) satisfying reviewers by showing them relevant items. In this paper, we develop a framework to study this problem in a principled manner. We present an algorithm called SUPER*, inspired by the A* algorithm, for this goal. Theoretically, we show a local optimality guarantee of our algorithm and prove that popular baselines are considerably suboptimal. Moreover, under a community model for the similarities, we prove that SUPER* is near-optimal whereas the popular baselines are considerably suboptimal. In experiments on real data from ICLR 2018 and synthetic data, we find that SUPER* considerably outperforms baselines deployed in existing systems, consistently reducing the number of papers with fewer than requisite bids by 50-75% or more, and is also robust to various real world complexities. '
volume: 124
URL: https://proceedings.mlr.press/v124/fiez20a.html
PDF: http://proceedings.mlr.press/v124/fiez20a/fiez20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-fiez20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Tanner
family: Fiez
- given: Nihar
family: Shah
- given: Lillian
family: Ratliff
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 580-589
id: fiez20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 580
lastpage: 589
published: 2020-08-27 00:00:00 +0000
- title: 'Measurement Dependence Inducing Latent Causal Models'
abstract: 'We consider the task of causal structure learning over measurement dependence inducing latent (MeDIL) causal models. We show that this task can be framed in terms of the graph theoretic problem of finding edge clique covers,resulting in an algorithm for returning minimal MeDIL causal models (minMCMs). This algorithm is non-parametric, requiring no assumptions about linearity or Gaussianity. Furthermore, despite rather weak assumptions aboutthe class of MeDIL causal models, we show that minimality in minMCMs implies some rather specific and interesting properties. By establishing MeDIL causal models as a semantics for edge clique covers, we also provide a starting point for future work further connecting causal structure learning to developments in graph theory and network science.'
volume: 124
URL: https://proceedings.mlr.press/v124/markham20a.html
PDF: http://proceedings.mlr.press/v124/markham20a/markham20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-markham20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Alex
family: Markham
- given: Moritz
family: Grosse-Wentrup
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 590-599
id: markham20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 590
lastpage: 599
published: 2020-08-27 00:00:00 +0000
- title: 'The Indian Chefs Process'
abstract: 'This paper introduces the Indian chefs process (ICP) as a Bayesian nonparametric prior on the joint space of infinite directed acyclic graphs (DAGs) and orders that generalizes the Indian buffet process. As our construction shows, the proposed distribution relies on a latent Beta process controlling both the orders and outgoing connection probabilities of the nodes, and yields a probability distribution on sparse infinite graphs. The main advantage of the ICP over previously proposed Bayesian nonparametric priors for DAG structures is its greater flexibility. To the best of our knowledge, the ICP is the first Bayesian nonparametric model supporting every possible DAG involving latent nodes. We demonstrate the usefulness of the ICP on learning the structure of deep generative sigmoid networks as well as convolutional neural networks. '
volume: 124
URL: https://proceedings.mlr.press/v124/dallaire20a.html
PDF: http://proceedings.mlr.press/v124/dallaire20a/dallaire20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-dallaire20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Patrick
family: Dallaire
- given: Luca
family: Ambrogioni
- given: Ludovic
family: Trottier
- given: Umut
family: Güçlü
- given: Max
family: Hinne
- given: Philippe
family: Giguère
- given: Marcel
family: Gerven
- given: François
family: Laviolette
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 600-608
id: dallaire20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 600
lastpage: 608
published: 2020-08-27 00:00:00 +0000
- title: 'Spectral Methods for Ranking with Scarce Data'
abstract: 'Given a number of pairwise preferences of items, a common task is to rank all the items.Examples include pairwise movie ratings, New Yorker cartoon caption contests, and many other consumer preferences tasks. What these settings have in common is two-fold: a scarcity of data (it may be costly to get comparisons for all the pairs of items) and additional feature information about the items (e.g., movie genre,director, and cast). In this paper we modify a popular and well studied method, RankCentrality for rank aggregation to account for few comparisons and that incorporates additional feature information. This method returns meaningful rankings even under scarce comparisons.Using diffusion based methods, we incorporate feature information that outperforms state-of-the-art methods in practice. We also provide improved sample complexity for RankCentrality in a variety of sampling schemes.'
volume: 124
URL: https://proceedings.mlr.press/v124/jain20a.html
PDF: http://proceedings.mlr.press/v124/jain20a/jain20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-jain20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Lalit
family: Jain
- given: Anna
family: Gilbert
- given: Umang
family: Varma
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 609-618
id: jain20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 609
lastpage: 618
published: 2020-08-27 00:00:00 +0000
- title: 'Anchored Causal Inference in the Presence of Measurement Error'
abstract: 'We consider the problem of learning a causal graph in the presence of measurement error.This setting is for example common in genomics, where gene expression is corrupted through the measurement process. We develop a provably consistent procedure for estimating the causal structure in a linear Gaussian structural equation model from corrupted observations on its nodes, under a variety of measurement error models. We provide an estimator based on the method-of-moments, which can be used in conjunction with constraint-based causal structure discovery algorithms. We prove asymptotic consistency of the procedure and also discuss finite-sample considerations. We demonstrate our method’s performance through simulations and on real data, where we recover the underlying gene regulatory network from zero-inflated single-cell RNA-seq data.'
volume: 124
URL: https://proceedings.mlr.press/v124/saeed20a.html
PDF: http://proceedings.mlr.press/v124/saeed20a/saeed20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-saeed20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Basil
family: Saeed
- given: Anastasiya
family: Belyaeva
- given: Yuhao
family: Wang
- given: Caroline
family: Uhler
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 619-628
id: saeed20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 619
lastpage: 628
published: 2020-08-27 00:00:00 +0000
- title: 'How Private Are Commonly-Used Voting Rules?'
abstract: 'Differential privacy has been widely applied to provide privacy guarantees by adding random noise to the function output. However, it inevitably fails in many high-stakes voting scenarios, where voting rules are required to be deterministic. In this work, we present the first framework for answering the question:“How private are commonly-used voting rules?" Our answers are two-fold. First, we show that deterministic voting rules provide sufficient privacy in the sense of distributional differential privacy (DDP). We show that assuming the adversarial observer has uncertainty about individual votes, even publishing the histogram of votes achieves good DDP. Second, we introduce the notion of exact privacy to compare the privacy preserved in various commonly-studied voting rules, and obtain dichotomy theorems of exact DDP within a large subset of voting rules called generalized scoring rules.'
volume: 124
URL: https://proceedings.mlr.press/v124/liu20b.html
PDF: http://proceedings.mlr.press/v124/liu20b/liu20b.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-liu20b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Ao
family: LIU
- given: Yun
family: Lu
- given: Lirong
family: Xia
- given: Vassilis
family: Zikas
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 629-638
id: liu20b
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 629
lastpage: 638
published: 2020-08-27 00:00:00 +0000
- title: 'Differentially Private Small Dataset Release Using Random Projections'
abstract: 'Small datasets form a significant portion of releasable data in high sensitivity domains such as healthcare. But, providing differential privacy for small dataset release is a hard task, where current state-of-the-art methods suffer from severe utility loss. As a solution, we propose DPRP (Differentially Private Data Release via Random Projections), a reconstruction based approach for releasing differentially private small datasets. DPRP has several key advantages over the state-of-the-art. Using seven diverse real-life datasets, we show that DPRP outperforms the current state-of-the-art on a variety of tasks, under varying conditions, and for all privacy budgets.'
volume: 124
URL: https://proceedings.mlr.press/v124/gondara20a.html
PDF: http://proceedings.mlr.press/v124/gondara20a/gondara20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-gondara20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Lovedeep
family: Gondara
- given: Ke
family: Wang
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 639-648
id: gondara20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 639
lastpage: 648
published: 2020-08-27 00:00:00 +0000
- title: 'Semi-supervised Sequential Generative Models'
abstract: 'We introduce a novel objective for training deep generative time-series models with discrete latent variables for which supervision is only sparsely available. This instance of semi-supervised learning is challenging for existing methods, because the exponential number of possible discrete latent configurations results in high variance gradient estimators. We first overcome this problem by extending the standard semi-supervised generative modeling objective with reweighted wake-sleep. However, we find that this approach still suffers when the frequency of available labels varies between training sequences. Finally, we introduce a unified objective inspired by teacher-forcing and show that this approach is robust to variable length supervision. We call the resulting method caffeinated wake-sleep (CWS) to emphasize its additional dependence on real data. We demonstrate its effectiveness with experiments on MNIST, handwriting, and fruit fly trajectory data.'
volume: 124
URL: https://proceedings.mlr.press/v124/teng20a.html
PDF: http://proceedings.mlr.press/v124/teng20a/teng20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-teng20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Michael
family: Teng
- given: Tuan
family: Anh Le
- given: Adam
family: Scibior
- given: Frank
family: Wood
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 649-658
id: teng20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 649
lastpage: 658
published: 2020-08-27 00:00:00 +0000
- title: 'Robust contrastive learning and nonlinear ICA in the presence of outliers'
abstract: 'Nonlinear independent component analysis (ICA) is a general framework for unsupervised representation learning, and aimed at recovering the latent variables in data. Recent practical methods perform nonlinear ICA by solving classification problems based on logistic regression. However, it is well-known that logistic regression is vulnerable to outliers, and thus the performance can be strongly weakened by outliers. In this paper, we first theoretically analyze nonlinear ICA models in the presence of outliers. Our analysis implies that estimation in nonlinear ICA can be seriously hampered when outliers exist on the tails of the (noncontaminated) target density, which happens in a typical case of contamination by outliers. We develop two robust nonlinear ICA methods based on the $\gamma$-divergence, which is a robust alternative to the KL-divergence in logistic regression. The proposed methods are theoretically shown to have desired robustness properties in the context of nonlinear ICA. We also experimentally demonstrate that the proposed methods are very robust and outperform existing methods in the presence of outliers. Finally, the proposed method is applied to ICA-based causal discovery and shown to find a plausible causal relationship on fMRI data.'
volume: 124
URL: https://proceedings.mlr.press/v124/sasaki20b.html
PDF: http://proceedings.mlr.press/v124/sasaki20b/sasaki20b.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-sasaki20b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Hiroaki
family: Sasaki
- given: Takashi
family: Takenouchi
- given: Ricardo
family: Monti
- given: Aapo
family: Hyvarinen
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 659-668
id: sasaki20b
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 659
lastpage: 668
published: 2020-08-27 00:00:00 +0000
- title: 'Selling Data at an Auction under Privacy Constraints'
abstract: 'Private data query combines mechanism design with privacy protection to produce aggregated statistics from privately-owned data records. The problem arises in a data marketplace where data owners have personalised privacy requirements and private data valuations. We focus on the case when the data owners are single-minded, i.e., they are willing to release their data only if the data broker guarantees to meet their announced privacy requirements. For a data broker who wants to purchase data from such data owners, we propose the SingleMindedQuery (SMQ) mechanism, which uses a reverse auction to select data owners and determine compensations. SMQ satisfies interim incentive compatibility, individual rationality, and budget feasibility. Moreover, it uses purchased privacy expectation maximisation as a principle to produce accurate outputs for commonly-used queries such as counting, median and linear predictor. The effectiveness of our method is empirically validated by a series of experiments. '
volume: 124
URL: https://proceedings.mlr.press/v124/zhang20b.html
PDF: http://proceedings.mlr.press/v124/zhang20b/zhang20b.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-zhang20b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Mengxiao
family: Zhang
- given: Fernando
family: Beltran
- given: Jiamou
family: Liu
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 669-678
id: zhang20b
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 669
lastpage: 678
published: 2020-08-27 00:00:00 +0000
- title: 'Mixed-Membership Stochastic Block Models for Weighted Networks'
abstract: 'We address in this study the problem of modeling weighted networks through generalized stochastic block models. Stochastic block models, and their extensions through mixed-membership versions, are indeed popular methods for network analysis as they can account for the underlying classes/communities structuring real-world networks and can be used for different applications.Our goal is to develop such models to solve the weight prediction problem that consists in predicting weights on links in weighted networks. To do so, we introduce new mixed-membership stochastic block models that can efficiently be learned through a coupling of collapsed and stochastic variational inference. These models, that represent the first weighted mixed-membership stochastic block models to our knowledge, can be deployed on large networks comprising millions of edges. The experiments, conducted on diverse real-world networks, illustrate the good behavior of these new models.'
volume: 124
URL: https://proceedings.mlr.press/v124/dulac20a.html
PDF: http://proceedings.mlr.press/v124/dulac20a/dulac20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-dulac20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Adrien
family: Dulac
- given: Eric
family: Gaussier
- given: Christine
family: Largeron
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 679-688
id: dulac20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 679
lastpage: 688
published: 2020-08-27 00:00:00 +0000
- title: 'MaskAAE: Latent space optimization for Adversarial Auto-Encoders'
abstract: 'The field of neural generative models is dominated by the highly successful Generative Adversarial Networks (GANs) despite their challenges, such as training instability and mode collapse. Auto-Encoders (AE) with regularized latent space provide an alternative framework for generative models, albeit their performance levels have not reached that of GANs. In this work, we hypothesise that the dimensionality of the AE model’s latent space has a critical effect on the quality of generated data. Under the assumption that nature generates data by sampling from a “true" generative latent space followed by a deterministic function, we show that the optimal performance is obtained when the dimensionality of the latent space of the AE-model matches with that of the “true" generative latent space. Further, we propose an algorithm called the Mask Adversarial Auto-Encoder (MaskAAE), in which the dimensionality of the latent space of an adversarial auto encoder is brought closer to that of the “true" generative latent space, via a procedure to mask the spurious latent dimensions. We demonstrate through experiments on synthetic and several real-world datasets that the proposed formulation yields betterment in the generation quality.'
volume: 124
URL: https://proceedings.mlr.press/v124/mondal20a.html
PDF: http://proceedings.mlr.press/v124/mondal20a/mondal20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-mondal20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Arnab
family: Mondal
- given: Sankalan
family: Pal Chowdhury
- given: Aravind
family: Jayendran
- given: Himanshu
family: Asnani
- given: Parag
family: Singla
- given: Prathosh
family: A P
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 689-698
id: mondal20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 689
lastpage: 698
published: 2020-08-27 00:00:00 +0000
- title: 'Slice Sampling for General Completely Random Measures'
abstract: 'Completely random measures provide a principled approach to creating flexible unsupervised models, where the number of latent features is infinite and the number of features that influence the data grows with the size of the data set. Due to the infinity the latent features, posterior inference requires either marginalization—resulting in dependence structures that prevent efficient computation via parallelization and conjugacy—or finite truncation, which arbitrarily limits the flexibility of the model. In this paper we present a novel Markov chain Monte Carlo algorithm for posterior inference that adaptively sets the truncation level using auxiliary slice variables, enabling efficient, parallelized computation without sacrificing flexibility. In contrast to past work that achieved this on a model-by-model basis, we provide a general recipe that is applicable to the broad class of completely random measure-based priors. The efficacy of the proposed algorithm is evaluated on several popular nonparametric models, demonstrating a higher effective sample size per second compared to algorithms using marginalization as well as a higher predictive performance compared to models employing fixed truncations.'
volume: 124
URL: https://proceedings.mlr.press/v124/zhu20a.html
PDF: http://proceedings.mlr.press/v124/zhu20a/zhu20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-zhu20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Peiyuan
family: Zhu
- given: Alexandre
family: Bouchard-Cote
- given: Trevor
family: Campbell
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 699-708
id: zhu20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 699
lastpage: 708
published: 2020-08-27 00:00:00 +0000
- title: 'Semi-Supervised Learning: the Case When Unlabeled Data is Equally Useful'
abstract: 'Semi-supervised learning algorithms attempt to take advantage of relatively inexpensive unlabeled data to improve learning performance. In this work, we consider statistical models where the data distributions can be characterized by continuous parameters. We show that under certain conditions on the distribution, unlabeled data is equally useful as labeled date in terms of learning rate. Specifically, let $n, m$ be the number of labeled and unlabeled data, respectively. It is shown that the learning rate of semi-supervised learning scales as $O(1/n)$ if $m\sim n$, and scales as $O(1/n^{1+\gamma})$ if $m\sim n^{1+\gamma}$ for some $\gamma>0$, whereas the learning rate of supervised learning scales as $O(1/n)$. '
volume: 124
URL: https://proceedings.mlr.press/v124/zhu20b.html
PDF: http://proceedings.mlr.press/v124/zhu20b/zhu20b.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-zhu20b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Jingge
family: Zhu
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 709-718
id: zhu20b
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 709
lastpage: 718
published: 2020-08-27 00:00:00 +0000
- title: 'Generalized Bayesian Posterior Expectation Distillation for Deep Neural Networks'
abstract: 'In this paper, we present a general framework for distilling expectations with respect to the Bayesian posterior distribution of a deep neural network classifier, extending prior work on the Bayesian Dark Knowledge framework. The proposed framework takes as input "teacher" and "student" model architectures and a general posterior expectation of interest. The distillation method performs an online compression of the selected posterior expectation using iteratively generated Monte Carlo samples. We focus on the posterior predictive distribution and expected entropy as distillation targets. We investigate several aspects of this framework including the impact of uncertainty and the choice of student model architecture. We study methods for student model architecture search from a speed-storage-accuracy perspective and evaluate down-stream tasks leveraging entropy distillation including uncertainty ranking and out-of-distribution detection.'
volume: 124
URL: https://proceedings.mlr.press/v124/vadera20a.html
PDF: http://proceedings.mlr.press/v124/vadera20a/vadera20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-vadera20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Meet
family: Vadera
- given: Brian
family: Jalaian
- given: Benjamin
family: Marlin
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 719-728
id: vadera20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 719
lastpage: 728
published: 2020-08-27 00:00:00 +0000
- title: 'Complex Markov Logic Networks: Expressivity and Liftability'
abstract: 'We study expressivity of Markov logic networks (MLNs). We introduce complex MLNs, which use complex-valued weights, and show that, unlike standard MLNs with real-valued weights, complex MLNs are"fully expressive". We then observe that discrete Fourier transform can be computed using weighted first order model counting (WFOMC) with complex weights and use this observation to design an algorithm for computing "relational marginal polytopes" which needs substantially less calls to a WFOMC oracle than an existing recent algorithm.'
volume: 124
URL: https://proceedings.mlr.press/v124/kuzelka20a.html
PDF: http://proceedings.mlr.press/v124/kuzelka20a/kuzelka20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-kuzelka20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Ondrej
family: Kuzelka
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 729-738
id: kuzelka20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 729
lastpage: 738
published: 2020-08-27 00:00:00 +0000
- title: 'Faster algorithms for Markov equivalence'
abstract: 'Maximal ancestral graphs (MAGs) have many desirable properties; in particular they can fully describe conditional independences from directed acyclic graphs (DAGs) in the presence of latent and selection variables. However, different MAGs may encode the same conditional independences, and are said to be \emph{Markov equivalent}. Thus identifying necessary and sufficient conditions for equivalence is essential for structure learning. Several criteria for this already exist, but in this paper we give a new non-parametric characterization in terms of the heads and tails that arise in the parameterization for discrete models. We also provide a polynomial time algorithm ($O(ne^{2})$, where $n$ and $e$ are the number of vertices and edges respectively) to verify equivalence. Moreover, we extend our criterion to ADMGs and summary graphs and propose an algorithm that converts an ADMG or summary graph to an equivalent MAG in polynomial time ($O(n^{2}e)$). Hence by combining both algorithms, we can also verify equivalence between two summary graphs or ADMGs.'
volume: 124
URL: https://proceedings.mlr.press/v124/hu20a.html
PDF: http://proceedings.mlr.press/v124/hu20a/hu20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-hu20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Zhongyi
family: Hu
- given: Robin
family: Evans
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 739-748
id: hu20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 739
lastpage: 748
published: 2020-08-27 00:00:00 +0000
- title: 'Verifying Individual Fairness in Machine Learning Models'
abstract: 'We consider the problem of whether a given decision model, working with structured data, has individual fairness. Following the work of Dwork, a model is individually biased (or unfair) if there is a pair of valid inputs which are close to each other (according to an appropriate metric) but are treated differently by the model (different class label, or large difference in output), and it is unbiased (or fair) if no such pair exists. Our objective is to construct verifiers for proving individual fairness of a given model, and we do so by considering appropriate relaxations of the problem. We construct verifiers which are sound but not complete for linear classifiers, and kernelized polynomial/radial basis function classifiers. We also report the experimental results of evaluating our proposed algorithms on publicly available datasets.'
volume: 124
URL: https://proceedings.mlr.press/v124/george-john20a.html
PDF: http://proceedings.mlr.press/v124/george-john20a/george-john20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-george-john20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Philips
family: George John
- given: Deepak
family: Vijaykeerthy
- given: Diptikalyan
family: Saha
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 749-758
id: george-john20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 749
lastpage: 758
published: 2020-08-27 00:00:00 +0000
- title: 'An Interpretable and Sample Efficient Deep Kernel for Gaussian Process'
abstract: 'We propose a novel Gaussian process kernel that takes advantage of a deep neural network (DNN) structure but retains good interpretability. The resulting kernel is capable of addressing four major issues of the previous works of similar art, i.e., the optimality, explainability, model complexity, and sample efficiency. Our kernel design procedure comprises three steps: (1) Derivation of an optimal kernel with a non-stationary dot product structure that minimizes the prediction/test mean-squared-error (MSE); (2) Decomposition of this optimal kernel as a linear combination of shallow DNN subnetworks with the aid of multi-way feature interaction detection; (3) Updating the hyper-parameters of the subnetworks via an alternating rationale until convergence. The designed kernel does not sacrifice interpretability for optimality. On the contrary, each subnetwork explicitly demonstrates the interaction of a set of features in a transformation function, leading to a solid path toward explainable kernel learning. We test the proposed kernel with both synthesized and real-world data sets, and the proposed kernel is superior to its competitors in terms of prediction performance in most cases. Moreover, it tends to maintain the prediction performance and be robust to data over-fitting issue, when reducing the number of samples. '
volume: 124
URL: https://proceedings.mlr.press/v124/dai20a.html
PDF: http://proceedings.mlr.press/v124/dai20a/dai20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-dai20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Yijue
family: Dai
- given: Tianjian
family: Zhang
- given: Zhidi
family: Lin
- given: Feng
family: Yin
- given: Sergios
family: Theodoridis
- given: Shuguang
family: Cui
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 759-768
id: dai20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 759
lastpage: 768
published: 2020-08-27 00:00:00 +0000
- title: 'Amortized Bayesian Optimization over Discrete Spaces'
abstract: 'Bayesian optimization is a principled approach for globally optimizing expensive, black-box functions by using a surrogate model of the objective. However, each step of Bayesian optimization involves solving an inner optimization problem, in which we maximize an acquisition function derived from the surrogate model to decide where to query next. This inner problem can be challenging to solve, particularly in discrete spaces, such as protein sequences or molecular graphs, where gradient-based optimization cannot be used. Our key insight is that we can train a generative model to generate candidates that maximize the acquisition function. This is faster than standard model-free local search methods, since we can amortize the cost of learning the model across multiple rounds of Bayesian optimization. We therefore call this Amortized Bayesian Optimization. On several challenging discrete design problems, we show this method generally outperforms other methods at optimizing the inner acquisition function, resulting in more efficient optimization of the outer black-box objective.'
volume: 124
URL: https://proceedings.mlr.press/v124/swersky20a.html
PDF: http://proceedings.mlr.press/v124/swersky20a/swersky20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-swersky20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Kevin
family: Swersky
- given: Yulia
family: Rubanova
- given: David
family: Dohan
- given: Kevin
family: Murphy
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 769-778
id: swersky20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 769
lastpage: 778
published: 2020-08-27 00:00:00 +0000
- title: 'Batch simulations and uncertainty quantification in Gaussian process surrogate approximate Bayesian computation'
abstract: 'The computational efficiency of approximate Bayesian computation (ABC) has been improved by using surrogate models such as Gaussian processes (GP). In one such promising framework the discrepancy between the simulated and observed data is modelled with a GP which is further used to form a model-based estimator for the intractable posterior. In this article we improve this approach in several ways. We develop batch-sequential Bayesian experimental design strategies to parallellise the expensive simulations. In earlier work only sequential strategies have been used. Current surrogate-based ABC methods also do not fully account the uncertainty due to the limited budget of simulations as they output only a point estimate of the ABC posterior. We propose a numerical method to fully quantify the uncertainty in, for example, ABC posterior moments. We also provide some new analysis on the GP modelling assumptions in the resulting improved framework called Bayesian ABC and discuss its connection to Bayesian quadrature (BQ) and Bayesian optimisation (BO). Experiments with toy and real-world simulation models demonstrate advantages of the proposed techniques. '
volume: 124
URL: https://proceedings.mlr.press/v124/jarvenpaa20a.html
PDF: http://proceedings.mlr.press/v124/jarvenpaa20a/jarvenpaa20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-jarvenpaa20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Marko
family: Jarvenpaa
- given: Aki
family: Vehtari
- given: Pekka
family: Marttinen
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 779-788
id: jarvenpaa20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 779
lastpage: 788
published: 2020-08-27 00:00:00 +0000
- title: 'Deep Sigma Point Processes'
abstract: 'We introduce Deep Sigma Point Processes, a class of parametric models inspired by the compositional structure of Deep Gaussian Processes (DGPs). Deep Sigma Point Processes (DSPPs) retain many of the attractive features of (variational) DGPs, including mini-batch training and predictive uncertainty that is controlled by kernel basis functions. Importantly, since DSPPs admit a simple maximum likelihood inference procedure, the resulting predictive distributions are not degraded by any posterior approximations. In an extensive empirical comparison on univariate and multivariate regression tasks we find that the resulting predictive distributions are significantly better calibrated than those obtained with other probabilistic methods for scalable regression, including variational DGPs–often by as much as a nat per datapoint.'
volume: 124
URL: https://proceedings.mlr.press/v124/jankowiak20a.html
PDF: http://proceedings.mlr.press/v124/jankowiak20a/jankowiak20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-jankowiak20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Martin
family: Jankowiak
- given: Geoff
family: Pleiss
- given: Jacob
family: Gardner
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 789-798
id: jankowiak20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 789
lastpage: 798
published: 2020-08-27 00:00:00 +0000
- title: 'Robust $k$-means++'
abstract: 'A good seeding or initialization of cluster centers for the $k$-means method is important from both theoretical and practical standpoints. The $k$-means objective is inherently non-robust and sensitive to outliers. A popular seeding such as the $k$-means++ [3] that is more likely to pick outliers in the worst case may compound this drawback, thereby affecting the quality of clustering on noisy data.For any $0 < \delta \leq 1$, we show that using a mixture of $D^{2}$ [3] and uniform sampling, we can pick $O(k/\delta)$ candidate centers with the following guarantee: they contain some $k$ centers that give $O(1)$-approximation to the optimal robust $k$-means solution while discarding at most $\delta n$ more points than the outliers discarded by the optimal solution. That is, if the optimal solution discards its farthest $\beta n$ points as outliers, our solution discards its $(\beta + \delta) n$ points as outliers. The constant factor in our $O(1)$-approximation does not depend on $\delta$. This is an improvement over previous results for $k$-means with outliers based on LP relaxation and rounding [7] and local search [17]. The $O(k/\delta)$ sized subset can be found in time $O(ndk)$. Our \emph{robust} $k$-means++ is also easily amenable to scalable, faster, parallel implementations of $k$-means++ [5]. Our empirical results show a comparison of the above \emph{robust} variant of $k$-means++ with the usual $k$-means++, uniform random seeding, threshold $k$-means++ [6] and local search on real world and synthetic data.'
volume: 124
URL: https://proceedings.mlr.press/v124/deshpande20a.html
PDF: http://proceedings.mlr.press/v124/deshpande20a/deshpande20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-deshpande20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Amit
family: Deshpande
- given: Praneeth
family: Kacham
- given: Rameshwar
family: Pratap
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 799-808
id: deshpande20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 799
lastpage: 808
published: 2020-08-27 00:00:00 +0000
- title: 'On Counterfactual Explanations under Predictive Multiplicity'
abstract: 'Counterfactual explanations are usually obtainedby identifying the smallest change made to an input to change a prediction made by a fixed model (hereafter called sparse methods). Recent work, however, has revitalized an old insight: there often does not exist one superior solution to a prediction problem with respect to commonly used measures of interest (e.g. error rate). In fact, often multiple different classifiers give almost equal solutions. This phenomenon is known as predictive multiplicity (Breiman, 2001; Marx et al., 2019). In this work, we derive a general upper bound for the costs of counterfactual explanations under predictive multiplicity. Most notably, it depends on a discrepancy notion between two classifiers, which describes how differently they treat negatively predicted individuals. We then compare sparse and data support approaches empirically on real-world data. The results show that data support methods are more robust to multiplicity of different models. At the same time, we show that those methods have provably higher cost of generating counterfactual explanations under one fixed model. In summary, our theoretical and empirical results challenge the commonly held view that counterfactual recommendations should be sparse in general.'
volume: 124
URL: https://proceedings.mlr.press/v124/pawelczyk20a.html
PDF: http://proceedings.mlr.press/v124/pawelczyk20a/pawelczyk20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-pawelczyk20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Martin
family: Pawelczyk
- given: Klaus
family: Broelemann
- given: Gjergji.
family: Kasneci
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 809-818
id: pawelczyk20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 809
lastpage: 818
published: 2020-08-27 00:00:00 +0000
- title: 'A Practical Riemannian Algorithm for Computing Dominant Generalized Eigenspace'
abstract: 'Dominant generalized eigenspace computation, concerned with how to find one of the top-k generalized eigenspaces of a pair of real symmetric matrices, is one of the fundamental problems in scientific computing, data analysis, and statistics. In this work, we propose a practical Riemannian algorithm based on the first-order optimization on generalized Stiefel manifolds while efficiently leveraging second-order information. Particularly, we use inexact Riemannian gradients which result from running a fast least-squares solver to approximate matrix multiplications for avoiding costly matrix inversions involved therein. We also conduct a theoretical analysis that is different than existing ones, achieving a unified linear convergence rate regardless of the conventional generalized eigenvalue gap which is the key parameter to the currently dichotomized analysis: gap-dependent or gap-free. The resulting linear rate, albeit not optimal, remains valid in full generality. Despite the simplicity, empirically, our algorithm as a block generalized eigensolver remarkably outperforms existing solvers.'
volume: 124
URL: https://proceedings.mlr.press/v124/xu20a.html
PDF: http://proceedings.mlr.press/v124/xu20a/xu20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-xu20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Zhiqiang
family: Xu
- given: Ping
family: Li
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 819-828
id: xu20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 819
lastpage: 828
published: 2020-08-27 00:00:00 +0000
- title: 'No-regret Exploration in Contextual Reinforcement Learning'
abstract: 'We consider the recently proposed reinforcement learning (RL) framework of Contextual Markov Decision Processes (CMDP), where the agent interacts with a (potentially adversarial) sequence of episodic tabular MDPs. In addition, a context vector determining the MDP parameters is available to the agent at the start of each episode, thereby allowing it to learn a context-dependent near-optimal policy. In this paper, we propose a no-regret online RL algorithm in the setting where the MDP parameters are obtained from the context using generalized linear mappings (GLMs). We propose and analyze optimistic and randomized exploration methods which make (time and space) efficient online updates. The GLM based model subsumes previous work in this area and also improves previous known bounds in the special case where the contextual mapping is linear. In addition, we demonstrate a generic template to derive confidence sets using an online learning oracle and give a lower bound for the setting.'
volume: 124
URL: https://proceedings.mlr.press/v124/modi20a.html
PDF: http://proceedings.mlr.press/v124/modi20a/modi20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-modi20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Aditya
family: Modi
- given: Ambuj
family: Tewari
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 829-838
id: modi20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 829
lastpage: 838
published: 2020-08-27 00:00:00 +0000
- title: 'Layering-MCMC for Structure Learning in Bayesian Networks'
abstract: 'Bayesian inference of the Bayesian network structure requires averaging over all possible directed acyclic graphs, DAGs, each weighted by its posterior probability. For approximate averaging, the most popular method has been Markov chain Monte Carlo, MCMC. It was recently shown that collapsing the sampling space from DAGs to suitably defined ordered partitions of the nodes substantially expedites the chain’s convergence; this partition-MCMC is similar to order-MCMC on node orderings, but it avoids biasing the sampling distribution. Here, we further collapse the state space by merging some number of adjacent members of a partition into layers. This renders the computation of the (unnormalized) posterior probability of a state, called layering, more involved, for which task we give an efficient dynamic programming algorithm. Our empirical studies suggest that the resulting layering-MCMC is superior to partition-MCMC in terms of mixing time and estimation accuracy.'
volume: 124
URL: https://proceedings.mlr.press/v124/viinikka20a.html
PDF: http://proceedings.mlr.press/v124/viinikka20a/viinikka20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-viinikka20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Jussi
family: Viinikka
- given: Mikko
family: Koivisto
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 839-848
id: viinikka20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 839
lastpage: 848
published: 2020-08-27 00:00:00 +0000
- title: 'C-MI-GAN : Estimation of Conditional Mutual Information using MinMax formulation'
abstract: 'Estimation of information theoretic quantities such as mutual information and its conditional variant has drawn interest in recent times owing to their multifaceted applications. Newly proposed neural estimators for these quantities have overcome severe drawbacks of classical $k$NN-based estimators in high dimensions. In this work, we focus on conditional mutual information (CMI) estimation by utilizing its formulation as a \textit{minmax} optimization problem. Such a formulation leads to a joint training procedure similar to that of generative adversarial networks. We find that our proposed estimator provides better estimates than the existing approaches on a variety of simulated datasets comprising linear and non-linear relations between variables. As an application of CMI estimation, we deploy our estimator for conditional independence (CI) testing on real data and obtain better results than state-of-the-art CI testers.'
volume: 124
URL: https://proceedings.mlr.press/v124/mondal20b.html
PDF: http://proceedings.mlr.press/v124/mondal20b/mondal20b.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-mondal20b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Arnab
family: Mondal
- given: Arnab
family: Bhattacharjee
- given: Sudipto
family: Mukherjee
- given: Himanshu
family: Asnani
- given: Sreeram
family: Kannan
- given: Prathosh
family: A P
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 849-858
id: mondal20b
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 849
lastpage: 858
published: 2020-08-27 00:00:00 +0000
- title: 'Stochastic Variational Inference for Dynamic Correlated Topic Models'
abstract: 'Correlated topic models (CTM) are useful tools for statistical analysis of documents. They explicitly capture the correlation between topics associated with each document. We propose an extension to CTM that models the evolution of both topic correlation and word co-occurrence over time. This allows us to identify the changes of topic correlations over time, e.g., in the machine learning literature, the correlation between the topics “stochastic gradient descent” and “variational inference” increased in the last few years due to advances in stochastic variational inference methods. Our temporal dynamic priors are based on Gaussian processes (GPs), allowing us to capture diverse temporal behaviours such as smooth, with long-term memory, temporally concentrated, and periodic. The evolution of topic correlations is modeled through generalised Wishart processes (GWPs). We develop a stochastic variational inference method, which enables us to handle large sets of continuous temporal data. Our experiments applied to real world data demonstrate that our model can be used to effectively discover temporal patterns of topic distributions, words associated to topics and topic relationships.'
volume: 124
URL: https://proceedings.mlr.press/v124/tomasi20a.html
PDF: http://proceedings.mlr.press/v124/tomasi20a/tomasi20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-tomasi20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Federico
family: Tomasi
- given: Praveen
family: Chandar
- given: Gal
family: Levy-Fix
- given: Mounia
family: Lalmas-Roelleke
- given: Zhenwen
family: Dai
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 859-868
id: tomasi20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 859
lastpage: 868
published: 2020-08-27 00:00:00 +0000
- title: 'Adversarial Learning for 3D Matching'
abstract: 'Structured prediction of objects in spaces that are inherently difficult to search or compactly characterize is a particularly challenging task. For example, though bipartite matchings in two dimensions can be tractably optimized and learned, the higher-dimensional generalization—3D matchings—are NP-hard to optimally obtain and the set of potential solutions cannot be compactly characterized. Though approximation is therefore necessary, prevalent structured prediction methods inherit the weaknesses they possess in the two-dimensional setting either suffering from inconsistency or intractability—even when the approximations are sufficient. In this paper, we explore extending an adversarial approach to learning bipartite matchings that avoids these weaknesses to the three dimensional setting. We assess the benefits compared to margin-based methods on a three-frame tracking problem.'
volume: 124
URL: https://proceedings.mlr.press/v124/xing20a.html
PDF: http://proceedings.mlr.press/v124/xing20a/xing20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-xing20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Wei
family: Xing
- given: Brian
family: Ziebart
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 869-878
id: xing20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 869
lastpage: 878
published: 2020-08-27 00:00:00 +0000
- title: 'Ordering Variables for Weighted Model Integration'
abstract: 'State-of-the-art probabilistic inference algorithms, such as variable elimination and search-based approaches, rely heavily on the order in which variables are marginalized. Finding the optimal ordering is an NP-complete problem. This computational hardness has led to heuristics to find adequate variable orderings. However, these heuristics have mostly been targeting discrete random variables. We show how variable ordering heuristics from the discrete domain can be ported to the discrete-continuous domain. We equip the state-of-the-art F-XSDD(BR) solver for discrete-continuous problems with such heuristics. Additionally, we propose a novel heuristic called bottom-up min-fill (BU-MiF), yielding a solver capable of determining good variable orderings without having to rely on the user to provide such an ordering. We empirically demonstrate its performance on a set of benchmark problems.'
volume: 124
URL: https://proceedings.mlr.press/v124/derkinderen20a.html
PDF: http://proceedings.mlr.press/v124/derkinderen20a/derkinderen20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-derkinderen20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Vincent
family: Derkinderen
- given: Evert
family: Heylen
- given: Pedro
family: Zuidberg Dos Martires
- given: Samuel
family: Kolb
- given: Luc
family: Raedt
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 879-888
id: derkinderen20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 879
lastpage: 888
published: 2020-08-27 00:00:00 +0000
- title: 'Online Parameter-Free Learning of Multiple Low Variance Tasks'
abstract: 'We propose a method to learn a common bias vector for a growing sequence of low-variance tasks. Unlike state-of-the-art approaches, our method does not require tuning any hyper-parameter. Our approach is presented in the non-statistical setting and can be of two variants. The “aggressive” one updates the bias after each datapoint, the “lazy” one updates the bias only at the end of each task. We derive an across-tasks regret bound for the method. When compared to state-of-the-art approaches, the aggressive variant returns faster rates, the lazy one recovers standard rates, but with no need of tuning hyper-parameters. We then adapt the methods to the statistical setting: the aggressive variant becomes a multi-task learning method, the lazy one a meta-learning method. Experiments confirm the effectiveness of our methods in practice.'
volume: 124
URL: https://proceedings.mlr.press/v124/denevi20a.html
PDF: http://proceedings.mlr.press/v124/denevi20a/denevi20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-denevi20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Giulia
family: Denevi
- given: Massimiliano
family: Pontil
- given: Dimitrios
family: Stamos
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 889-898
id: denevi20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 889
lastpage: 898
published: 2020-08-27 00:00:00 +0000
- title: 'Zeroth Order Non-convex optimization with Dueling-Choice Bandits'
abstract: 'We consider a novel setting of zeroth order non-convex optimization, where in addition to querying the function value at a given point, we can also duel two points and get the point with the larger function value. We refer to this setting as optimization with dueling-choice bandits, since both direct queries and duels are available for optimization. We give the COMP-GP-UCB algorithm based on GP-UCB (Srinivas et al., 2009),, where instead of directly querying the point with the maximum Upper Confidence Bound (UCB), we perform constrained optimization and use comparisons to filter out suboptimal points. COMP-GP-UCB comes with theoretical guarantee of $O(\frac{\Phi}{\sqrt{T}})$ on simple regret where $T$ is the number of direct queries and $\Phi$ is an improved information gain stemming from a comparison-based constraint set that restricts the space for optimum search. In contrast, in the plain direct query setting, $\Phi$ depends on the entire domain. We discuss theoretical aspects and show experimental results to demonstrate efficacy of our algorithm.'
volume: 124
URL: https://proceedings.mlr.press/v124/xu20b.html
PDF: http://proceedings.mlr.press/v124/xu20b/xu20b.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-xu20b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Yichong
family: Xu
- given: Aparna
family: Joshi
- given: Aarti
family: Singh
- given: Artur
family: Dubrawski
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 899-908
id: xu20b
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 899
lastpage: 908
published: 2020-08-27 00:00:00 +0000
- title: 'Semi-bandit Optimization in the Dispersed Setting'
abstract: 'The goal of data-driven algorithm design is to obtain high-performing algorithms for specific application domains using machine learning and data. Across many fields in AI, science, and engineering, practitioners will often fix a family of parameterized algorithms and then optimize those parameters to obtain good performance on example instances from the application domain. In the online setting, we must choose algorithm parameters for each instance as they arrive, and our goal is to be competitive with the best fixed algorithm in hindsight.There are two major challenges in online data-driven algorithm design. First, it can be computationally expensive to evaluate the loss functions that map algorithm parameters to performance, which often require the learner to run a combinatorial algorithm to measure its performance. Second, the losses can be extremely volatile and have sharp discontinuities. However, we show that in many applications, evaluating the loss function for one algorithm choice can sometimes reveal the loss for a range of similar algorithms, essentially for free. We develop online optimization algorithms capable of using this kind of extra information by working in the semi-bandit feedback setting. Our algorithms achieve regret bounds that are essentially as good as algorithms under full-information feedback and are significantly more computationally efficient. We apply our semi-bandit results to obtain the first provable guarantees for data-driven algorithm design for linkage-based clustering and we improve the best regret bounds for designing greedy knapsack algorithms.'
volume: 124
URL: https://proceedings.mlr.press/v124/balcan20a.html
PDF: http://proceedings.mlr.press/v124/balcan20a/balcan20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-balcan20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Maria-Florina
family: Balcan
- given: Travis
family: Dick
- given: Wesley
family: Pegden
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 909-918
id: balcan20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 909
lastpage: 918
published: 2020-08-27 00:00:00 +0000
- title: 'Adapting Text Embeddings for Causal Inference'
abstract: 'Does adding a theorem to a paper affect its chance of acceptance? Does labeling a post with the author’s gender affect the post popularity? This paper develops a method to estimate such causal effects from observational text data, adjusting for confounding features of the text such as the subject or writing quality. We assume that the text suffices for causal adjustment but that, in practice, it is prohibitively high-dimensional. To address this challenge, we develop causally sufficient embeddings, low- dimensional document representations that preserve sufficient information for causal identification and allow for efficient estimation of causal effects. Causally sufficient embeddings combine two ideas. The first is supervised dimensionality reduction: causal adjustment requires only the aspects of text that are predictive of both the treatment and outcome. The second is efficient language modeling: representations of text are designed to dispose of linguistically irrelevant information, and this information is also causally irrelevant. Our method adapts language models (specifically, word embeddings and topic models) to learn document embeddings that are able to predict both treatment and outcome. We study causally sufficient embeddings with semi-synthetic datasets and find that they improve causal estimation over related embedding methods. We illustrate the methods by answering the two motivating questions—the effect of a theorem on paper acceptance and the effect of a gender label on post popularity. Code and data available at github.com/vveitch/causal-text-embeddings-tf2.'
volume: 124
URL: https://proceedings.mlr.press/v124/veitch20a.html
PDF: http://proceedings.mlr.press/v124/veitch20a/veitch20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-veitch20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Victor
family: Veitch
- given: Dhanya
family: Sridhar
- given: David
family: Blei
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 919-928
id: veitch20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 919
lastpage: 928
published: 2020-08-27 00:00:00 +0000
- title: 'Joint Stochastic Approximation and Its Application to Learning Discrete Latent Variable Models'
abstract: 'Although with progress in introducing auxiliary amortized inference models, learning discrete latent variable models is still challenging. In this paper, we show that the annoying difficulty of obtaining reliable stochastic gradients for the inference model and the drawback of indirectly optimizing the target log-likelihood can be gracefully addressed in a new method based on stochastic approximation (SA) theory of the Robbins-Monro type. Specifically, we propose to directly maximize the target log-likelihood and simultaneously minimize the inclusive divergence between the posterior and the inference model. The resulting learning algorithm is called joint SA (JSA). To the best of our knowledge, JSA represents the first method that couples an SA version of the EM (expectation-maximization) algorithm (SAEM) with an adaptive MCMC procedure. Experiments on several benchmark generative modeling and structured prediction tasks show that JSA consistently outperforms recent competitive algorithms, with faster convergence, better final likelihoods, and lower variance of gradient estimates.'
volume: 124
URL: https://proceedings.mlr.press/v124/ou20a.html
PDF: http://proceedings.mlr.press/v124/ou20a/ou20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-ou20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Zhijian
family: Ou
- given: Yunfu
family: Song
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 929-938
id: ou20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 929
lastpage: 938
published: 2020-08-27 00:00:00 +0000
- title: 'Hidden Markov Nonlinear ICA: Unsupervised Learning from Nonstationary Time Series'
abstract: 'Recent advances in nonlinear Independent Component Analysis (ICA) provide a principled framework for unsupervised feature learning and disentanglement. The central idea in such works is that the latent components are assumed to be independent conditional on some observed auxiliary variables, such as the time-segment index. This requires manual segmentation of data into non-stationary segments which is computationally expensive, inaccurate and often impossible. These models are thus not fully unsupervised. We remedy these limitations by combining nonlinear ICA with a Hidden Markov Model, resulting in a model where a latent state acts in place of the observed segment-index. We prove identifiability of the proposed model for a general mixing nonlinearity, such as a neural network. We also show how maximum likelihood estimation of the model can be done using the expectation-maximization algorithm. Thus, we achieve a new nonlinear ICA framework which is unsupervised, more efficient, as well as able to model underlying temporal dynamics.'
volume: 124
URL: https://proceedings.mlr.press/v124/halva20a.html
PDF: http://proceedings.mlr.press/v124/halva20a/halva20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-halva20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Hermanni
family: Hälvä
- given: Aapo
family: Hyvarinen
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 939-948
id: halva20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 939
lastpage: 948
published: 2020-08-27 00:00:00 +0000
- title: 'Identification and Estimation of Causal Effects Defined by Shift Interventions'
abstract: 'Causal inference quantifies cause effect relationships by means of counterfactual responses had some variable been artificially set to a constant. A more refined notion of manipulation, where a variable is artificially set to a fixed function of its natural value is also of interest in particular domains. Examples include increases in financial aid, changes in drug dosing, and modifying length of stay in a hospital.We define counterfactual responses to manipulations of this type, which we call shift interventions. We show that in the presence of multiple variables being manipulated, two types of shift interventions are possible. Shift interventions on the treated (SITs) are defined with respect to natural values, and are connected to effects of treatment on the treated. Shift interventions as policies (SIPs) are defined recursively with respect to values of responses to prior shift interventions, and are connected to dynamic treatment regimes. We give sound and complete identification algorithms for both types of shift interventions, and derive efficient semi-parametric estimators for the mean response to a shift intervention in a special case motivated by a healthcare problem. Finally, we demonstrate the utility of our method by using an electronic health record dataset to estimate the effect of extending the length of stay in the intensive care unit (ICU) in a hospital by an extra day on patient ICU readmission probability.'
volume: 124
URL: https://proceedings.mlr.press/v124/sani20a.html
PDF: http://proceedings.mlr.press/v124/sani20a/sani20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-sani20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Numair
family: Sani
- given: Jaron
family: Lee
- given: Ilya
family: Shpitser
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 949-958
id: sani20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 949
lastpage: 958
published: 2020-08-27 00:00:00 +0000
- title: 'Risk Bounds for Low Cost Bipartite Ranking'
abstract: 'Bipartite ranking is an important supervised learning problem; however, unlike regression or classification, it has a quadratic dependence on the number of samples. To circumvent the prohibitive sample cost, many recent work focus on stochastic gradient-based methods. In this paper we consider an alternative approach, which leverages the structure of the widely-adopted pairwise squared loss, to obtain a stochastic and low cost algorithm that does not require stochastic gradients or learning rates. Using a novel uniform risk bound—based on matrix and vector concentration inequalities—we show that the sample size required for competitive performance against the all-pairs batch algorithm does not have a quadratic dependence. Generalization bounds for both the batch and low cost stochastic algorithms are presented. Experimental results show significant speed gain against the batch algorithm, as well as competitive performance against state-of-the-art bipartite ranking algorithms on real datasets.'
volume: 124
URL: https://proceedings.mlr.press/v124/gultekin20a.html
PDF: http://proceedings.mlr.press/v124/gultekin20a/gultekin20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-gultekin20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: San
family: Gultekin
- given: John
family: Paisley
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 959-968
id: gultekin20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 959
lastpage: 968
published: 2020-08-27 00:00:00 +0000
- title: 'Multitask Soft Option Learning'
abstract: 'We present Multitask Soft Option Learning (MSOL), a hierarchical multitask framework based on Planning as Inference. MSOL extends the concept of options, using separate variational posteriors for each task, regularized by a shared prior. This “soft” version of options avoids several instabilities during training in a multitask setting, and provides a natural way to learn both intra-option policies and their terminations. Furthermore, it allows fine-tuning of options for new tasks without forgetting their learned policies, leading to faster training without reducing the expressiveness of the hierarchical policy. We demonstrate empirically that MSOL significantly outperforms both hierarchical and flat transfer-learning baselines.'
volume: 124
URL: https://proceedings.mlr.press/v124/igl20a.html
PDF: http://proceedings.mlr.press/v124/igl20a/igl20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-igl20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Maximilian
family: Igl
- given: Andrew
family: Gambardella
- given: Jinke
family: He
- given: Nantas
family: Nardelli
- given: N
family: Siddharth
- given: Wendelin
family: Boehmer
- given: Shimon
family: Whiteson
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 969-978
id: igl20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 969
lastpage: 978
published: 2020-08-27 00:00:00 +0000
- title: '99% of Worker-Master Communication in Distributed Optimization Is Not Needed'
abstract: 'In this paper we discuss sparsification of worker-to-server communication in large distributed systems. We improve upon algorithms that fit the following template: a local gradient estimate is computed independently by each worker, then communicated to a master, which subsequently performs averaging. The average is broadcast back to the workers, which use it to perform a gradient-type step to update the local version of the model. We observe that the above template is fundamentally inefficient in that too much data is unnecessarily communicated from the workers to the server, which slows down the overall system. We propose a fix based on a new update-sparsification method we develop in this work, which we suggest be used on top of existing methods. Namely, we develop a new variant of parallel block coordinate descent based on independent sparsification of the local gradient estimates before communication. We demonstrate that with only $m/n$ blocks sent by each of $n$ workers, where $m$ is the total number of parameter blocks, the theoretical iteration complexity of the underlying distributed methods is essentially unaffected. As an illustration, this means that when $n=100$ parallel workers are used, the communication of 99% blocks is redundant, and hence a waste of time. Our theoretical claims are supported through extensive numerical experiments which demonstrate an almost perfect match with our theory on a number of synthetic and real datasets.'
volume: 124
URL: https://proceedings.mlr.press/v124/mishchenko20a.html
PDF: http://proceedings.mlr.press/v124/mishchenko20a/mishchenko20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-mishchenko20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Konstantin
family: Mishchenko
- given: Filip
family: Hanzely
- given: Peter
family: Richtarik
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 979-988
id: mishchenko20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 979
lastpage: 988
published: 2020-08-27 00:00:00 +0000
- title: 'Graphical continuous Lyapunov models'
abstract: 'The linear Lyapunov equation of a covariance matrix parametrizes theequilibrium covariance matrix of a stochastic process. This parametrization canbe interpreted as a new graphical model class, and we show how the model classbehaves under marginalization and introduce a method for structure learning via$\ell_1$-penalized loss minimization. Our proposed method is demonstrated tooutperform alternative structure learning algorithms in a simulation study, andwe illustrate its application for protein phosphorylation network reconstruction.'
volume: 124
URL: https://proceedings.mlr.press/v124/varando20a.html
PDF: http://proceedings.mlr.press/v124/varando20a/varando20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-varando20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Gherardo
family: Varando
- given: Niels
family: Richard Hansen
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 989-998
id: varando20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 989
lastpage: 998
published: 2020-08-27 00:00:00 +0000
- title: 'Structure Learning for Cyclic Linear Causal Models'
abstract: 'We consider the problem of structure learning for linear causal models based on observational data. We treat models given by possibly cyclic mixed graphs, which allow for feedback loops and effects of latent confounders. Generalizing related work on bow-free acyclic graphs, we assume that the underlying graph is simple. This entails that any two observed variables can be related through at most one direct causal effect and that (confounding-induced) correlation between error terms in structural equations occurs only in absence of direct causal effects.We show that, despite new subtleties in the cyclic case, the considered simple cyclic models are of expected dimension and that a previously considered criterion for distributional equivalence of bow-free acyclic graphs has an analogue in the cyclic case. Our result on model dimension justifies in particular score-based methods for structure learning of linear Gaussian mixed graph models, which we implement via greedy search.'
volume: 124
URL: https://proceedings.mlr.press/v124/amendola20a.html
PDF: http://proceedings.mlr.press/v124/amendola20a/amendola20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-amendola20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Carlos
family: Amendola
- given: Philipp
family: Dettling
- given: Mathias
family: Drton
- given: Federica
family: Onori
- given: Jun
family: Wu
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 999-1008
id: amendola20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 999
lastpage: 1008
published: 2020-08-27 00:00:00 +0000
- title: 'Sensor Placement for Spatial Gaussian Processes with Integral Observations'
abstract: 'Gaussian processes (GP) are a natural tool for estimating unknown functions, typically based on a collection of point-wise observations. Interestingly, the GP formalism can be used also with observations that are integrals of the unknown function along some known trajectories, which makes GPs a promising technique for inverse problems in a wide range of physical sensing problems. However, in many real world applications collecting data is laborious and time consuming. We provide tools for optimizing sensor locations for GPs using integral observations, extending both model-based and geometric strategies for GP sensor placement.We demonstrate the techniques in ultrasonic detection of fouling in closed pipes. '
volume: 124
URL: https://proceedings.mlr.press/v124/longi20a.html
PDF: http://proceedings.mlr.press/v124/longi20a/longi20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-longi20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Krista
family: Longi
- given: Chang
family: Rajani
- given: Tom
family: Sillanpää
- given: Joni
family: Mäkinen
- given: Timo
family: Rauhala
- given: Ari
family: Salmi
- given: Edward
family: Haeggström
- given: Arto
family: Klami
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1009-1018
id: longi20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1009
lastpage: 1018
published: 2020-08-27 00:00:00 +0000
- title: 'Active Model Estimation in Markov Decision Processes'
abstract: 'We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP). Efficient exploration in this problem requires the agent to identify the regions in which estimating the model is more difficult and then exploit this knowledge to collect more samples there. In this paper, we formalize this problem, introduce the first algorithm to learn an $\epsilon$-accurate estimate of the dynamics, and provide its sample complexity analysis. While this algorithm enjoys strong guarantees in the large-sample regime, it tends to have a poor performance in early stages of exploration. To address this issue, we propose an algorithm that is based on maximum weighted entropy, a heuristic that stems from common sense and our theoretical analysis. The main idea here is to cover the entire state-action space with the weight proportional to the noise in their transition functions. Using a number of simple domains with heterogeneous noise in their transitions, we show that our heuristic-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime, while achieving similar asymptotic performance as that of the original algorithm. '
volume: 124
URL: https://proceedings.mlr.press/v124/tarbouriech20a.html
PDF: http://proceedings.mlr.press/v124/tarbouriech20a/tarbouriech20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-tarbouriech20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Jean
family: Tarbouriech
- given: Shubhanshu
family: Shekhar
- given: Matteo
family: Pirotta
- given: Mohammad
family: Ghavamzadeh
- given: Alessandro
family: Lazaric
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1019-1028
id: tarbouriech20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1019
lastpage: 1028
published: 2020-08-27 00:00:00 +0000
- title: 'Dueling Posterior Sampling for Preference-Based Reinforcement Learning'
abstract: 'In preference-based reinforcement learning (RL), an agent interacts with the environment while receiving preferences instead of absolute feedback. While there is increasing research activity in preference-based RL, the design of formal frameworks that admit tractable theoretical analysis remains an open challenge. Building upon ideas from preference-based bandit learning and posterior sampling in RL, we present DUELING POSTERIOR SAMPLING (DPS), which employs preference-based posterior sampling to learn both the system dynamics and the underlying utility function that governs the preference feedback. As preference feedback is provided on trajectories rather than individual state-action pairs, we develop a Bayesian approach for the credit assignment problem, translating preferences to a posterior distribution over state-action reward models. We prove an asymptotic Bayesian no-regret rate for DPS with a Bayesian linear regression credit assignment model. This is the first regret guarantee for preference-based RL to our knowledge. We also discuss possible avenues for extending the proof methodology to other credit assignment models. Finally, we evaluate the approach empirically, showing competitive performance against existing baselines.'
volume: 124
URL: https://proceedings.mlr.press/v124/novoseller20a.html
PDF: http://proceedings.mlr.press/v124/novoseller20a/novoseller20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-novoseller20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Ellen
family: Novoseller
- given: Yibing
family: Wei
- given: Yanan
family: Sui
- given: Yisong
family: Yue
- given: Joel
family: Burdick
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1029-1038
id: novoseller20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1029
lastpage: 1038
published: 2020-08-27 00:00:00 +0000
- title: 'Permutation-Based Causal Structure Learning with Unknown Intervention Targets'
abstract: 'We consider the problem of estimating causal DAG models from a mix of observational and interventional data, when the intervention targets are partially or completely unknown. This problem is highly relevant for example in genomics, since gene knockout technologies are known to have off-target effects. We characterize the interventional Markov equivalence class of DAGs that can be identified from interventional data with unknown intervention targets. In addition, we propose a provably consistent algorithm for learning the interventional Markov equivalence class from such data. The proposed algorithm greedily searches over the space of permutations to minimize a novel score function. The algorithm is nonparametric, which is particularly important for applications to genomics, where the relationships between variables are often non-linear and the distribution non-Gaussian. We demonstrate the performance of our algorithm on synthetic and biological datasets. Links to an implementation of our algorithm and to a reproducible code base for our experiments can be found at https://uhlerlab.github.io/causaldag/utigsp.'
volume: 124
URL: https://proceedings.mlr.press/v124/squires20a.html
PDF: http://proceedings.mlr.press/v124/squires20a/squires20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-squires20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Chandler
family: Squires
- given: Yuhao
family: Wang
- given: Caroline
family: Uhler
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1039-1048
id: squires20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1039
lastpage: 1048
published: 2020-08-27 00:00:00 +0000
- title: 'MASSIVE: Tractable and Robust Bayesian Learning of Many-Dimensional Instrumental Variable Models'
abstract: 'The recent availability of huge, many-dimensional data sets, like those arising from genome-wide association studies (GWAS), provides many opportunities for strengthening causal inference. One popular approach is to utilize these many-dimensional measurements as instrumental variables (instruments) for improving the causal effect estimate between other pairs of variables. Unfortunately, searching for proper instruments in a many-dimensional set of candidates is a daunting task due to the intractable model space and the fact that we cannot directly test which of these candidates are valid, so most existing search methods either rely on overly stringent modeling assumptions or fail to capture the inherent model uncertainty in the selection process. We show that, as long as at least some of the candidates are (close to) valid, without knowing a priori which ones, they collectively still pose enough restrictions on the target interaction to obtain a reliable causal effect estimate. We propose a general and efficient causal inference algorithm that accounts for model uncertainty by performing Bayesian model averaging over the most promising many-dimensional instrumental variable models, while at the same time employing weaker assumptions regarding the data generating process. We showcase the efficiency, robustness and predictive performance of our algorithm through experimental results on both simulated and real-world data.'
volume: 124
URL: https://proceedings.mlr.press/v124/gabriel-bucur20a.html
PDF: http://proceedings.mlr.press/v124/gabriel-bucur20a/gabriel-bucur20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-gabriel-bucur20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Ioan
family: Gabriel Bucur
- given: Tom
family: Claassen
- given: Tom
family: Heskes
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1049-1058
id: gabriel-bucur20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1049
lastpage: 1058
published: 2020-08-27 00:00:00 +0000
- title: 'Popularity Agnostic Evaluation of Knowledge Graph Embeddings'
abstract: 'In this paper, we show that the distribution of entities and relations in common knowledge graphs is highly skewed, with some entities and relations being much more popular than the rest. We show that while knowledge graph embedding models give state-of-the-art performance in many relational learning tasks such as link prediction, current evaluation metrics like hits@k and mrr are biased towards popular entities and relations. We propose two new evaluation metrics, strat-hits@k and strat-mrr, which are unbiased estimators of the true hits@k and mrr when the items follow a power-law distribution. Our new metrics are generalizations of hits@k and mrr that take into account the popularity of the entities and relations in the data, with a tuning parameter determining how much emphasis the metric places on popular vs. unpopular items. Using our metrics, we run experiments on benchmark datasets to show that the performance of embedding models degrades as the popularity of the entities and relations decreases, and that current reported results overestimate the performance of these models by magnifying their accuracy on popular items.'
volume: 124
URL: https://proceedings.mlr.press/v124/mohamed20a.html
PDF: http://proceedings.mlr.press/v124/mohamed20a/mohamed20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-mohamed20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Aisha
family: Mohamed
- given: Shameem
family: Parambath
- given: Zoi
family: Kaoudi
- given: Ashraf
family: Aboulnaga
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1059-1068
id: mohamed20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1059
lastpage: 1068
published: 2020-08-27 00:00:00 +0000
- title: 'Learning LWF Chain Graphs: A Markov Blanket Discovery Approach'
abstract: 'This paper provides a graphical characterization of Markov blankets in chaingraphs (CGs) under the Lauritzen-Wermuth-Frydenberg (LWF) interpretation. The characterization is different from the well-known one for Bayesian networks and generalizes it. We provide a novel scalable and sound algorithmfor Markov blanket discovery in LWF CGs and prove that the Grow-Shrink algorithm, the IAMB algorithm, and its variants are still correct for Markov blanket discovery in LWF CGs under the same assumptions as for Bayesian networks. We provide a sound and scalable constraint-based framework for learning the structure of LWF CGs from faithful causally sufficient data and prove its correctness when the Markov blanket discovery algorithms in this paper are used. Our proposed algorithms compare positively/competitively against the state-of-the-art LCD (Learn Chain graphs via Decomposition) algorithm, depending on the algorithm that is used for Markov blanket discovery. Our proposed algorithms make a broad range of inference/learning problems computationallytractable and more reliable because they exploit locality.'
volume: 124
URL: https://proceedings.mlr.press/v124/ali-javidian20a.html
PDF: http://proceedings.mlr.press/v124/ali-javidian20a/ali-javidian20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-ali-javidian20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Mohammad
family: Ali Javidian
- given: Marco
family: Valtorta
- given: Pooyan
family: Jamshidi
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1069-1078
id: ali-javidian20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1069
lastpage: 1078
published: 2020-08-27 00:00:00 +0000
- title: 'Batch norm with entropic regularization turns deterministic autoencoders into generative models'
abstract: 'The variational autoencoder is a well defined deep generative model that utilizes an encoder-decoder framework where an encoding neural network outputs a non-deterministic code for reconstructing an input. The encoder achieves this by sampling from a distribution for every input, instead of outputting a deterministic code per input. The great advantage of this process is that it allows the use of the network as a generative model for sampling from the data distribution beyond provided samples for training. We show in this work that utilizing batch normalization as a source for non-determinism suffices to turn deterministic autoencoders into generative models on par with variational ones, so long as we add a suitable entropic regularization to the training objective.'
volume: 124
URL: https://proceedings.mlr.press/v124/ghose20a.html
PDF: http://proceedings.mlr.press/v124/ghose20a/ghose20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-ghose20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Amur
family: Ghose
- given: Abdullah
family: Rashwan
- given: Pascal
family: Poupart
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1079-1088
id: ghose20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1079
lastpage: 1088
published: 2020-08-27 00:00:00 +0000
- title: 'Adaptive Hyper-box Matching for Interpretable Individualized Treatment Effect Estimation'
abstract: 'We propose a matching method for observational data that matches units with others in unit-specific, hyper-box-shaped regions of the covariate space. These regions are large enough that many matches are created for each unit and small enough that the treatment effect is roughly constant throughout. The regions are found as either the solution to a mixed integer program, or using a (fast) approximation algorithm. The result is an interpretable and tailored estimate of the causal effect for each unit. '
volume: 124
URL: https://proceedings.mlr.press/v124/morucci20a.html
PDF: http://proceedings.mlr.press/v124/morucci20a/morucci20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-morucci20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Marco
family: Morucci
- given: Vittorio
family: Orlandi
- given: Sudeepa
family: Roy
- given: Cynthia
family: Rudin
- given: Alexander
family: Volfovsky
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1089-1098
id: morucci20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1089
lastpage: 1098
published: 2020-08-27 00:00:00 +0000
- title: 'Generalized Policy Elimination: an efficient algorithm for Nonparametric Contextual Bandits'
abstract: 'We propose the Generalized Policy Elimination (GPE) algorithm, an oracle-efficient contextual bandit (CB) algorithm inspired by the Policy Elimination algorithm of Dudik et al. [2011]. We prove the first regret-optimality guarantee theorem for an oracle-efficient CB algorithm competing against a nonparametric class with infinite VC-dimension. Specifically, we show that GPE is regret-optimal (up to logarithmic factors) for policy classes with integrable entropy. For classes with larger entropy, we show that the core techniques used to analyze GPE can be used to design an $\varepsilon$-greedy algorithm with regret bound matching that of the best algorithms to date. We illustrate the applicability of our algorithms and theorems with examples of large nonparametric policy classes, for which the relevant optimization oracles can be efficiently implemented.'
volume: 124
URL: https://proceedings.mlr.press/v124/bibaut20a.html
PDF: http://proceedings.mlr.press/v124/bibaut20a/bibaut20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-bibaut20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Aurelien
family: Bibaut
- given: Antoine
family: Chambaz
- given: Mark
family: Laan
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1099-1108
id: bibaut20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1099
lastpage: 1108
published: 2020-08-27 00:00:00 +0000
- title: 'Differentially Private Top-k Selection via Stability on Unknown Domain'
abstract: 'We propose a new method that satisfies approximate differential privacy for top-$k$ selection with unordered output in the unknown data domain setting, not relying on the full knowledge of the domain universe. Our algorithm only requires looking at the top-$\bar{k}$ elements for any given $\bar{k} \geq k$, thus, enforcing the principle of minimal privilege. Unlike previous methods, our privacy parameter $\varepsilon$ does not scale with $k$, giving improved applicability for scenarios of very large $k$. Moreover, our novel construction, which combines the sparse vector technique and stability efficiently, can be applied as a general framework to any type of query, thus being of independent interest. We extensively compare our algorithm to previous work of top-$k$ selection on the unknown domain, and show, both analytically and on experiments, settings where we outperform the current state-of-the-art.'
volume: 124
URL: https://proceedings.mlr.press/v124/silva-carvalho20a.html
PDF: http://proceedings.mlr.press/v124/silva-carvalho20a/silva-carvalho20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-silva-carvalho20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Ricardo
family: Silva Carvalho
- given: Ke
family: Wang
- given: Lovedeep
family: Gondara
- given: Chunyan
family: Miao
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1109-1118
id: silva-carvalho20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1109
lastpage: 1118
published: 2020-08-27 00:00:00 +0000
- title: 'Active Learning of Conditional Mean Embeddings via Bayesian Optimisation'
abstract: 'We consider the problem of sequentially optimising the conditional expectation of an objective function, with both the conditional distribution and the objective function assumed to be fixed but unknown. Assuming that the objective function belongs to a reproducing kernel Hilbert space (RKHS), we provide a novel upper confidence bound (UCB) based algorithm CME-UCB via estimation of the conditional mean embeddings (CME), and derive its regret bound. Along the way, we derive novel approximation guarantees for the CME estimates. Finally, experiments are carried out in a synthetic example and in a likelihood-free inference application that highlight the useful insights of the proposed method.'
volume: 124
URL: https://proceedings.mlr.press/v124/ray-chowdhury20a.html
PDF: http://proceedings.mlr.press/v124/ray-chowdhury20a/ray-chowdhury20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-ray-chowdhury20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Sayak
family: Ray Chowdhury
- given: Rafael
family: Oliveira
- given: Fabio
family: Ramos
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1119-1128
id: ray-chowdhury20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1119
lastpage: 1128
published: 2020-08-27 00:00:00 +0000
- title: 'Flexible Prior Elicitation via the Prior Predictive Distribution'
abstract: ' The prior distribution for the unknown model parameters plays a crucial role in the process of statistical inference based on Bayesian methods. However, specifying suitable priors is often difficult even when detailed prior knowledge is available in principle. The challenge is to express quantitative information in the form of a probability distribution. Prior elicitation addresses this question by extracting subjective information from an expert and transforming it into a valid prior. Most existing methods, however, require information to be provided on the unobservable parameters, whose effect on the data generating process is often complicated and hard to understand. We propose an alternative approach that only requires knowledge about the observable outcomes - knowledge which is often much easier for experts to provide. Building upon a principled statistical framework, our approach utilizes the prior predictive distribution implied by the model to automatically transform experts judgements about plausible outcome values to suitable priors on the parameters. We also provide computational strategies to perform inference and guidelines to facilitate practical use.'
volume: 124
URL: https://proceedings.mlr.press/v124/hartmann20a.html
PDF: http://proceedings.mlr.press/v124/hartmann20a/hartmann20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-hartmann20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Marcelo
family: Hartmann
- given: Georgi
family: Agiashvili
- given: Paul
family: Bürkner
- given: Arto
family: Klami
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1129-1138
id: hartmann20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1129
lastpage: 1138
published: 2020-08-27 00:00:00 +0000
- title: 'Model-Augmented Conditional Mutual Information Estimation for Feature Selection'
abstract: 'Markov blanket feature selection, while theoretically optimal, is generally challenging to implement. This is due to the shortcomings of existing approaches to conditional independence (CI) testing, which tend to struggle either with the curse of dimensionality or computational complexity. We propose a novel two-step approach which facilitates Markov blanket feature selection in high dimensions. First, neural networks are used to map features to low-dimensional representations. In the second step, CI testing is performed by applying the $k$-NN conditional mutual information estimator to the learned feature maps. The mappings are designed to ensure that mapped samples both preserve information and share similar information about the target variable if and only if they are close in Euclidean distance. We show that these properties boost the performance of the $k$-NN estimator in the second step. The performance of the proposed method is evaluated on both synthetic and real data.'
volume: 124
URL: https://proceedings.mlr.press/v124/yang20b.html
PDF: http://proceedings.mlr.press/v124/yang20b/yang20b.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-yang20b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Alan
family: Yang
- given: AmirEmad
family: Ghassami
- given: Maxim
family: Raginsky
- given: Negar
family: Kiyavash
- given: Elyse
family: Rosenbaum
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1139-1148
id: yang20b
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1139
lastpage: 1148
published: 2020-08-27 00:00:00 +0000
- title: 'Finite-Memory Near-Optimal Learning for Markov Decision Processes with Long-Run Average Reward'
abstract: 'We consider learning policies online in Markov decision processes with the long-run average reward (a.k.a. mean payoff). To ensure implementability of the policies, we focus on policies with finite memory. Firstly, we show that near optimality can be achieved almost surely, using an unintuitive gadget we call forgetfulness. Secondly, we extend the approach to a setting with partial knowledge of the system topology, introducing two optimality measures and providing near-optimal algorithms also for these cases.'
volume: 124
URL: https://proceedings.mlr.press/v124/kretinsky20a.html
PDF: http://proceedings.mlr.press/v124/kretinsky20a/kretinsky20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-kretinsky20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Jan
family: Kretinsky
- given: Fabian
family: Michel
- given: Lukas
family: Michel
- given: Guillermo
family: Perez
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1149-1158
id: kretinsky20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1149
lastpage: 1158
published: 2020-08-27 00:00:00 +0000
- title: 'Constraint-Based Causal Discovery using Partial Ancestral Graphs in the presence of Cycles'
abstract: 'While feedback loops are known to play important roles in many complex systems, their existence is ignored in a large part of the causal discovery literature, as systems are typically assumed to be acyclic from the outset. When applying causal discovery algorithms designed for the acyclic setting on data generated by a system that involves feedback, one would not expect to obtain correct results. In this work, we show that—surprisingly—the output of the Fast Causal Inference (FCI) algorithm is correct if it is applied to observational data generated by a system that involves feedback. More specifically, we prove that for observational data generated by a simple and sigma-faithful Structural Causal Model (SCM), FCI is sound and complete, and can be used to consistently estimate (i) the presence and absence of causal relations, (ii) the presence and absence of direct causal relations, (iii) the absence of confounders, and (iv) the absence of specific cycles in the causal graph of the SCM. We extend these results to constraint-based causal discovery algorithms that exploit certain forms of background knowledge, including the causally sufficient setting (e.g., the PC algorithm) and the Joint Causal Inference setting (e.g., the FCI-JCI algorithm).'
volume: 124
URL: https://proceedings.mlr.press/v124/m-mooij20a.html
PDF: http://proceedings.mlr.press/v124/m-mooij20a/m-mooij20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-m-mooij20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Joris
family: M. Mooij
- given: Tom
family: Claassen
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1159-1168
id: m-mooij20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1159
lastpage: 1168
published: 2020-08-27 00:00:00 +0000
- title: 'Estimation Rates for Sparse Linear Cyclic Causal Models'
abstract: 'Causal models are fundamental tools to understand complex systems and predict the effect of interventions on such systems. However, despite an extensive literature in the population (or infinite-sample) case, where distributions are assumed to be known, little is known about the statistical rates of convergence of various methods, even for the simplest models. In this work, allowing for cycles, we study linear structural equations models with homoscedastic Gaussian noise and in the presence of interventions that make the model identifiable. More specifically, we present statistical rates of estimation for both the LLC estimator introduced by Hyttinen, Eberhardt and Hoyer and a novel two-step penalized maximum likelihood estimator. We establish asymptotic near minimax optimality for the maximum likelihood estimator over a class of sparse causal graphs in the case of near-optimally chosen interventions. Moreover, we find evidence for practical advantages of this estimator compared to LLC in synthetic numerical experiments.'
volume: 124
URL: https://proceedings.mlr.press/v124/huetter20a.html
PDF: http://proceedings.mlr.press/v124/huetter20a/huetter20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-huetter20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Jan-Christian
family: Huetter
- given: Philippe
family: Rigollet
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1169-1178
id: huetter20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1169
lastpage: 1178
published: 2020-08-27 00:00:00 +0000
- title: 'Prediction Intervals: Split Normal Mixture from Quality-Driven Deep Ensembles'
abstract: 'Prediction intervals are a machine- and human-interpretable way to represent predictive uncertainty in a regression analysis. In this paper, we present a method for generating prediction intervals along with point estimates from an ensemble of neural networks. We propose a multi-objective loss function fusing quality measures related to prediction intervals and point estimates, and a penalty function, which enforces semantic integrity of the results and stabilizes the training process of the neural networks. The ensembled prediction intervals are aggregated as a split normal mixture accounting for possible multimodality and asymmetricity of the posterior predictive distribution, and resulting in prediction intervals that capture aleatoric and epistemic uncertainty. Our results show that both our quality-driven loss function and our aggregation method contribute to well-calibrated prediction intervals and point estimates. '
volume: 124
URL: https://proceedings.mlr.press/v124/saleh-salem20a.html
PDF: http://proceedings.mlr.press/v124/saleh-salem20a/saleh-salem20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-saleh-salem20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Tárik
family: S. Salem
- given: Helge
family: Langseth
- given: Heri
family: Ramampiaro
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1179-1187
id: saleh-salem20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1179
lastpage: 1187
published: 2020-08-27 00:00:00 +0000
- title: 'On the Relationship Between Probabilistic Circuits and Determinantal Point Processes'
abstract: 'Scaling probabilistic models to large realistic problems and datasets is a key challenge in machine learning. Central to this effort is the development of tractable probabilistic models (TPMs): models whose structure guarantees efficient probabilistic inference algorithms. The current landscape of TPMs is fragmented: there exist various kinds of TPMs with different strengths and weaknesses. Two of the most prominent classes of TPMs are determinantal point processes (DPPs) and probabilistic circuits (PCs). This paper provides the first systematic study of their relationship. We propose a unified analysis and shared language for discussing DPPs and PCs. Then we establish theoretical barriers for the unification of these two families, and prove that there are cases where DPPs have no compact representation as a class of PCs. We close with a perspective on the central problem of unifying these tractable models.'
volume: 124
URL: https://proceedings.mlr.press/v124/zhang20c.html
PDF: http://proceedings.mlr.press/v124/zhang20c/zhang20c.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-zhang20c.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Honghua
family: Zhang
- given: Steven
family: Holtzen
- given: Guy
family: Broeck
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1188-1197
id: zhang20c
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1188
lastpage: 1197
published: 2020-08-27 00:00:00 +0000
- title: 'Probabilistic Safety for Bayesian Neural Networks'
abstract: 'We study probabilistic safety for Bayesian Neural Networks (BNNs) under adversarial input perturbations. Given a compact set of input points, $T \subseteq R^m$, we study the probability w.r.t. the BNN posterior that all the points in $T$ are mapped to the same region $S$ in the output space. In particular, this can be used to evaluate the probability that a network sampled from the BNN is vulnerable to adversarial attacks. We rely on relaxation techniques from non-convex optimization to develop a method for computing a lower bound on probabilistic safety for BNNs, deriving explicit procedures for the case of interval and linear function propagation techniques. We apply our methods to BNNs trained on a regression task, airborne collision avoidance, and MNIST, empirically showing that our approach allows one to certify probabilistic safety of BNNs with millions of parameters.'
volume: 124
URL: https://proceedings.mlr.press/v124/wicker20a.html
PDF: http://proceedings.mlr.press/v124/wicker20a/wicker20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-wicker20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Matthew
family: Wicker
- given: Luca
family: Laurenti
- given: Andrea
family: Patane
- given: Marta
family: Kwiatkowska
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1198-1207
id: wicker20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1198
lastpage: 1207
published: 2020-08-27 00:00:00 +0000
- title: 'Distortion estimates for approximate Bayesian inference'
abstract: 'Current literature on posterior approximation for Bayesian inference offers many alternative methods. Does our chosen approximation scheme work well on the observed data? The best existing generic diagnostic tools treating this kind of question by looking at performance averaged over data space, or otherwise lack diagnostic detail. However, if the approximation is bad for most data, but good at the observed data, then we may discard a useful approximation. We give graphical diagnostics for posterior approximation at the observed data. We estimate a “distortion map” that acts on univariate marginals of the approximate posterior to move them closer to the exact posterior, without recourse to the exact posterior.'
volume: 124
URL: https://proceedings.mlr.press/v124/xing20b.html
PDF: http://proceedings.mlr.press/v124/xing20b/xing20b.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-xing20b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Hanwen
family: Xing
- given: Geoff
family: Nicholls
- given: Jeong
family: (Kate) Lee
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1208-1217
id: xing20b
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1208
lastpage: 1217
published: 2020-08-27 00:00:00 +0000
- title: 'Mutual Information Based Knowledge Transfer Under State-Action Dimension Mismatch'
abstract: 'Deep reinforcement learning (RL) algorithms have achieved great success on a wide variety of sequential decision-making tasks. However, many of these algorithms suffer from high sample complexity when learning from scratch using environmental rewards, due to issues such as credit-assignment and high-variance gradients, among others. Transfer learning, in which knowledge gained on a source task is applied to more efficiently learn a different but related target task, is a promising approach to improve the sample complexity in RL. Prior work has considered using pre-trained teacher policies to enhance the learning of the student policy, albeit with the constraint that the teacher and the student MDPs share the state-space or the action-space. In this paper, we propose a new framework for transfer learning where the teacher and the student can have arbitrarily different state- and action-spaces. To handle this mismatch, we produce embeddings which can systematically extract knowledge from the teacher policy and value networks, and blend it into the student networks. To train the embeddings, we use a task-aligned loss and show that the representations could be enriched further by adding a mutual information loss. Using a set of challenging simulated robotic locomotion tasks involving many-legged centipedes, we demonstrate successful transfer learning in situations when the teacher and student have different state- and action-spaces.'
volume: 124
URL: https://proceedings.mlr.press/v124/wan20a.html
PDF: http://proceedings.mlr.press/v124/wan20a/wan20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-wan20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Michael
family: Wan
- given: Tanmay
family: Gangwani
- given: Jian
family: Peng
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1218-1227
id: wan20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1218
lastpage: 1227
published: 2020-08-27 00:00:00 +0000
- title: 'Provably Efficient Third-Person Imitation from Offline Observation'
abstract: 'Domain adaptation in imitation learning represents an essential step towards improving generalizability. However, even in the restricted setting of third-person imitation where transfer is between isomorphic Markov Decision Processes, there are no strong guarantees on the performance of transferred policies. We present problem-dependent, statistical learning guarantees for third-person imitation from observation in an offline setting, and a lower bound on performance in the online setting.'
volume: 124
URL: https://proceedings.mlr.press/v124/zweig20a.html
PDF: http://proceedings.mlr.press/v124/zweig20a/zweig20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-zweig20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Aaron
family: Zweig
- given: Joan
family: Bruna
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1228-1237
id: zweig20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1228
lastpage: 1237
published: 2020-08-27 00:00:00 +0000
- title: 'Automated Dependence Plots'
abstract: 'In practical applications of machine learning, it is necessary to look beyond standard metrics such as test accuracy in order to validate various qualitative properties of a model. Partial dependence plots (PDP), including instance-specific PDPs (i.e., ICE plots), have been widely used as a visual tool to understand or validate a model. Yet, current PDPs suffer from two main drawbacks: (1) a user must manually sort or select interesting plots, and (2) PDPs are usually limited to plots along a single feature. To address these drawbacks, we formalize a method for automating the selection of interesting PDPs and extend PDPs beyond showing single features to show the model response along arbitrary directions, for example in raw feature space or a latent space arising from some generative model. We demonstrate the usefulness of our automated dependence plots (ADP) across multiple use-cases and datasets including model selection, bias detection, understanding out-of-sample behavior, and exploring the latent space of a generative model. The code is available at .'
volume: 124
URL: https://proceedings.mlr.press/v124/inouye20a.html
PDF: http://proceedings.mlr.press/v124/inouye20a/inouye20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-inouye20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: David
family: Inouye
- given: Liu
family: Leqi
- given: Joon
family: Sik Kim
- given: Bryon
family: Aragam
- given: Pradeep
family: Ravikumar
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1238-1247
id: inouye20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1238
lastpage: 1247
published: 2020-08-27 00:00:00 +0000
- title: 'EiGLasso: Scalable Estimation of Cartesian Product of Sparse Inverse Covariance Matrices'
abstract: 'In this paper, we address the problem of jointly estimating dependencies across samples and dependencies across multiple features, where each set of dependencies is modeled as an inverse covariance matrix. In particular, we study a matrix-variate Gaussian distribution with the Kronecker-sum of sample-wise and feature-wise inverse covariances. While this Kronecker-sum model has been studied as an intuitively more appealing convex alternative to the Kronecker-product of two inverse covariance matrices, the existing methods do not scale to large datasets. We introduce a highly-efficient optimization method for estimating the Kronecker-sum structured inverse covariance matrix from matrix-variate data. In addition, we describe an alternative simpler approach for handling the non-identifiability of parameters than the strategies proposed in previous works. Using simulated and real data, we demonstrate our approach leads to one or two orders-of-magnitude speedup of the previous methods.'
volume: 124
URL: https://proceedings.mlr.press/v124/ho-yoon20a.html
PDF: http://proceedings.mlr.press/v124/ho-yoon20a/ho-yoon20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-ho-yoon20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Jun Ho
family: Yoon
- given: Seyoung
family: Kim
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1248-1257
id: ho-yoon20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1248
lastpage: 1257
published: 2020-08-27 00:00:00 +0000
- title: 'Improved Vector Pruning in Exact Algorithms for Solving POMDPs'
abstract: 'Exact dynamic programming algorithms for solving partially observable Markov decision processes (POMDPs) rely on a subroutine that removes, or “prunes,” dominated vectors from vector sets that represent piecewise-linear and convex value functions. The subroutine solves many linear programs, where the size of the linear programs is proportional to both the number of undominated vectors in the set and their dimension, which severely limits scalability. Recent work improves the performance of this subroutine by limiting the number of constraints in the linear programs it solves by incrementally generating relevant constraints. In this paper, we show how to similarly limit the number of variables. By reducing the size of the linear programs in both ways, we further improve the performance of exact algorithms for POMDPs, especially in solving problems with larger state spaces.'
volume: 124
URL: https://proceedings.mlr.press/v124/hansen20a.html
PDF: http://proceedings.mlr.press/v124/hansen20a/hansen20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-hansen20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Eric
family: Hansen
- given: Thomas
family: Bowman
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1258-1267
id: hansen20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1258
lastpage: 1267
published: 2020-08-27 00:00:00 +0000
- title: 'Symbolic Querying of Vector Spaces: Probabilistic Databases Meets Relational Embeddings'
abstract: 'We propose unifying techniques from probabilistic databases and relational embedding models with the goal of performing complex queries on incomplete and uncertain data. We formalize a probabilistic database model with respect to which all queries are done. This allows us to leverage the rich literature of theory and algorithms from probabilistic databases for solving problems. While this formalization can be used with any relational embedding model, the lack of a well-defined joint probability distribution causes simple query problems to become provably hard. With this in mind, we introduce TractOR, a relational embedding model designed to be a tractable probabilistic database, by exploiting typical embedding assumptions within the probabilistic framework. Using a principled, efficient inference algorithm that can be derived from its definition, we empirically demonstrate that TractOR is an effective and general model for these querying tasks.'
volume: 124
URL: https://proceedings.mlr.press/v124/friedman20a.html
PDF: http://proceedings.mlr.press/v124/friedman20a/friedman20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-friedman20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Tal
family: Friedman
- given: Guy
family: Broeck
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1268-1277
id: friedman20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1268
lastpage: 1277
published: 2020-08-27 00:00:00 +0000
- title: 'Learning to learn generative programs with Memoised Wake-Sleep'
abstract: 'We study a class of neuro-symbolic generative models in which neural networks are used both for inference and as priors over symbolic, data-generating programs. As generative models, these programs capture compositional structures in a naturally explainable form. To tackle the challenge of performing program induction as an ‘inner-loop’ to learning, we propose the Memoised Wake-Sleep (MWS) algorithm, which extends Wake Sleep by explicitly storing and reusing the best programs discovered by the inference network throughout training. We use MWS to learn accurate, explainable models in three challenging domains: stroke-based character modelling, cellular automata, and few-shot learning in a novel dataset of real-world string concepts.'
volume: 124
URL: https://proceedings.mlr.press/v124/hewitt20a.html
PDF: http://proceedings.mlr.press/v124/hewitt20a/hewitt20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-hewitt20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Luke
family: Hewitt
- given: Tuan
family: Anh Le
- given: Joshua
family: Tenenbaum
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1278-1287
id: hewitt20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1278
lastpage: 1287
published: 2020-08-27 00:00:00 +0000
- title: 'Flexible Approximate Inference via Stratified Normalizing Flows'
abstract: 'A major obstacle to forming posterior distributions in machine learning is the difficulty of evaluating partition functions. Monte-Carlo approaches are unbiased, but can suffer from high variance. Variational methods are biased, but tend to have lower variance. We develop an approximate inference procedure that allows explicit control of the bias/variance tradeoff, interpolating between the sampling and the variational regime. We use a normalizing flow to map the integrand onto a uniform distribution. We then randomly sample regions from a partition of this uniform distribution and fit simpler, local variational approximations in the image of these regions through the flow. When a partition with only one region is used, we recover standard variational inference, and in the limit of an infinitely fine partition we recover Monte-Carlo sampling. We show experiments validating the effectiveness of our approach.'
volume: 124
URL: https://proceedings.mlr.press/v124/cundy20a.html
PDF: http://proceedings.mlr.press/v124/cundy20a/cundy20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-cundy20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Chris
family: Cundy
- given: Stefano
family: Ermon
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1288-1297
id: cundy20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1288
lastpage: 1297
published: 2020-08-27 00:00:00 +0000
- title: 'Bounded Rationality in Las Vegas: Probabilistic Finite Automata Play Multi-Armed Bandits'
abstract: 'While traditional economics assumes that humans are fully rational agents who always maximize their expected utility, in practice, we constantly observe apparently irrational behavior. One explanation is that people have limited computational power, so that they are, quite rationally, making the best decisions they can, given their computational limitations. To test this hypothesis, we consider the multi-armed bandit (MAB) problem. We examine a simple strategy for playing an MAB that can be implemented easily by a probabilistic finite automaton (PFA). Roughly speaking, the PFA sets certain expectations, and plays an arm as long as it meets them. If the PFA has sufficiently many states, it performs near-optimally. Its performance degrades gracefully as the number of states decreases. Moreover, the PFA acts in a "human-like" way, exhibiting a number of standard human biases, like an optimism bias and a negativity bias.'
volume: 124
URL: https://proceedings.mlr.press/v124/liu20c.html
PDF: http://proceedings.mlr.press/v124/liu20c/liu20c.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-liu20c.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Xinming
family: Liu
- given: Joseph
family: Halpern
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1298-1307
id: liu20c
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1298
lastpage: 1307
published: 2020-08-27 00:00:00 +0000
- title: 'Greedy Policy Search: A Simple Baseline for Learnable Test-Time Augmentation'
abstract: 'Test-time data augmentation—averaging the predictions of a machine learning model across multiple augmented samples of data—is a widely used technique that improves the predictive performance. While many advanced learnable data augmentation techniques have emerged in recent years, they are focused on the training phase. Such techniques are not necessarily optimal for test-time augmentation and can be outperformed by a policy consisting of simple crops and flips. The primary goal of this paper is to demonstrate that test-time augmentation policies can be successfully learned too. We introduce greedy policy search (GPS), a simple but high-performing method for learning a policy of test-time augmentation. We demonstrate that augmentation policies learned with GPS achieve superior predictive performance on image classification problems, provide better in-domain uncertainty estimation, and improve the robustness to domain shift.'
volume: 124
URL: https://proceedings.mlr.press/v124/lyzhov20a.html
PDF: http://proceedings.mlr.press/v124/lyzhov20a/lyzhov20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-lyzhov20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Alexander
family: Lyzhov
- given: Yuliya
family: Molchanova
- given: Arsenii
family: Ashukha
- given: Dmitry
family: Molchanov
- given: Dmitry
family: Vetrov
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1308-1317
id: lyzhov20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1308
lastpage: 1317
published: 2020-08-27 00:00:00 +0000
- title: 'Non Parametric Graph Learning for Bayesian Graph Neural Networks'
abstract: 'Graphs are ubiquitous in modelling relationalstructures. Recent endeavours in machine learningfor graph structured data have led to manyarchitectures and learning algorithms. However,the graph used by these algorithms is oftenconstructed based on inaccurate modellingassumptions and/or noisy data. As a result, itfails to represent the true relationships betweennodes. A Bayesian framework which targetsposterior inference of the graph by consideringit as a random quantity can be beneficial. Inthis paper, we propose a novel non-parametricgraph model for constructing the posterior distributionof graph adjacency matrices. The proposedmodel is flexible in the sense that it caneffectively take into account the output of graphbased learning algorithms that target specifictasks. In addition, model inference scales wellto large graphs. We demonstrate the advantagesof this model in three different problem settings:node classification, link prediction andrecommendation.'
volume: 124
URL: https://proceedings.mlr.press/v124/pal20a.html
PDF: http://proceedings.mlr.press/v124/pal20a/pal20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-pal20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Soumyasundar
family: Pal
- given: Saber
family: Malekmohammadi
- given: Florence
family: Regol
- given: Yingxue
family: Zhang
- given: Yishi
family: Xu
- given: Mark
family: Coates
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1318-1327
id: pal20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1318
lastpage: 1327
published: 2020-08-27 00:00:00 +0000
- title: 'Stable Policy Optimization via Off-Policy Divergence Regularization'
abstract: 'Trust Region Policy Optimization (TRPO) and Proximal Policy Optimization (PPO) are among the most successful policy gradient approaches in deep reinforcement learning (RL). While these methods achieve state-of-the-art performance across a wide range of challenging tasks, there is room for improvement in the stabilization of the policy learning and how the off-policy data are used. In this paper we revisit the theoretical foundations of these algorithms and propose a new algorithm which stabilizes the policy improvement through a proximity term that constrains the discounted state-action visitation distribution induced by consecutive policies to be close to one another. This proximity term, expressed in terms of the divergence between the visitation distributions, is learned in an off-policy and adversarial manner. We empirically show that our proposed method can have a beneficial effect on stability and improve final performance in benchmark high-dimensional control tasks.'
volume: 124
URL: https://proceedings.mlr.press/v124/touati20a.html
PDF: http://proceedings.mlr.press/v124/touati20a/touati20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-touati20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Ahmed
family: Touati
- given: Amy
family: Zhang
- given: Joelle
family: Pineau
- given: Pascal
family: Vincent
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1328-1337
id: touati20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1328
lastpage: 1337
published: 2020-08-27 00:00:00 +0000
- title: 'PoRB-Nets: Poisson Process Radial Basis Function Networks'
abstract: 'Bayesian neural networks (BNNs) are flexible function priors well-suited to situations in which data are scarce and uncertainty must be quantified. Yet, common weight priors are able to encode little functional knowledge and can behave in undesirable ways. We present a novel prior over radial basis function networks (RBFNs) that allows for independent specification of functional amplitude variance and lengthscale (i.e., smoothness), where the inverse lengthscale corresponds to the concentration of radial basis functions. When the lengthscale is uniform over the input space, we prove consistency and approximate variance stationarity. This is in contrast to common BNN priors, which are highly nonstationary. When the input dependence of the lengthscale is unknown, we show how it can be inferred. We compare this model’s behavior to standard BNNs and Gaussian processes using synthetic and real examples.'
volume: 124
URL: https://proceedings.mlr.press/v124/coker20a.html
PDF: http://proceedings.mlr.press/v124/coker20a/coker20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-coker20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Beau
family: Coker
- given: Melanie
family: Fernandez Pradier
- given: Finale
family: Doshi-Velez
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1338-1347
id: coker20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1338
lastpage: 1347
published: 2020-08-27 00:00:00 +0000
- title: 'Deriving Bounds And Inequality Constraints Using Logical Relations Among Counterfactuals'
abstract: ' Causal parameters may not be point identified in the presence of unobserved confounding. However, information about non-identified parameters, in the form of bounds, may still be recovered from the observed data in some cases. We develop a new general method for obtaining bounds on causal parameters using rules of probability and restrictions on counterfactuals implied by causal graphical models. We additionally provide inequality constraints on functionals of the observed data law implied by such causal models. Our approach is motivated by the observation that logical relations between identified and non-identified counterfactual events often yield information about non-identified events. We show that this approach is powerful enough to recover known sharp bounds and tight inequality constraints, and to derive novel bounds and constraints.'
volume: 124
URL: https://proceedings.mlr.press/v124/finkelstein20a.html
PDF: http://proceedings.mlr.press/v124/finkelstein20a/finkelstein20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-finkelstein20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Noam
family: Finkelstein
- given: Ilya
family: Shpitser
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1348-1357
id: finkelstein20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1348
lastpage: 1357
published: 2020-08-27 00:00:00 +0000
- title: 'Locally Masked Convolution for Autoregressive Models'
abstract: 'High-dimensional generative models have many applications including image compression, multimedia generation, anomaly detection and data completion. State-of-the-art estimators for natural images are autoregressive, decomposing the joint distribution over pixels into a product of conditionals parameterized by a deep neural network, e.g. a convolutional neural network such as the PixelCNN. However, PixelCNNs only model a single decomposition of the joint, and only a single generation order is efficient. For tasks such as image completion, these models are unable to use much of the observed context. To generate data in arbitrary orders, we introduce LMConv: a simple modification to the standard 2D convolution that allows arbitrary masks to be applied to the weights at each location in the image. Using LMConv, we learn an ensemble of distribution estimators that share parameters but differ in generation order, achieving improved performance on whole-image density estimation (2.89 bpd on unconditional CIFAR10), as well as globally coherent image completions. Code is available at https://ajayjain.github.io/lmconv.'
volume: 124
URL: https://proceedings.mlr.press/v124/jain20b.html
PDF: http://proceedings.mlr.press/v124/jain20b/jain20b.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-jain20b.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Ajay
family: Jain
- given: Pieter
family: Abbeel
- given: Deepak
family: Pathak
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1358-1367
id: jain20b
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1358
lastpage: 1367
published: 2020-08-27 00:00:00 +0000
- title: 'Time Series Analysis using a Kernel based Multi-Modal Uncertainty Decomposition Framework'
abstract: 'This paper proposes a kernel based information theoretic framework with quantum physical underpinnings for data characterization that is relevant to online time series applications such as unsupervised change point detection and whole sequence clustering. In this framework, we utilize the Gaussian kernel mean embedding metric for universal characterization of data PDF. We then utilize concepts of quantum physics to impart a local dynamical structure to characterized data PDF, resulting in a new energy based formulation. This facilitates a multi-modal physics based uncertainty representation of the signal PDF at each sample using Hermite polynomial projections. We demonstrate in this paper using synthesized datasets that such uncertainty features provide a better ability for online detection of statistical change points in time series data when compared to existing non-parametric and unsupervised methods. We also demonstrate a better ability of the framework in clustering time series sequences when compared to discrete wavelet transform features on a subset of VidTIMIT speaker recognition corpus.'
volume: 124
URL: https://proceedings.mlr.press/v124/singh20a.html
PDF: http://proceedings.mlr.press/v124/singh20a/singh20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-singh20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Rishabh
family: Singh
- given: Jose
family: Principe
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1368-1377
id: singh20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1368
lastpage: 1377
published: 2020-08-27 00:00:00 +0000
- title: 'OCEAN: Online Task Inference for Compositional Tasks with Context Adaptation'
abstract: 'Real-world tasks often exhibit a compositional structure that contains a sequence of simpler sub-tasks. For instance, opening a door requires reaching, grasping, rotating, and pulling the door knob. Such compositional tasks require an agent to reason about the sub-task at hand while orchestrating global behavior accordingly. This can be cast as an online task inference problem, where the current task identity, represented by a context variable, is estimated from the agent’s past experiences with probabilistic inference. Previous approaches have employed simple latent distributions, e.g., Gaussian, to model a single context for the entire task. However, this formulation lacks the expressiveness to capture the composition and transition of the sub-tasks. We propose a variational inference framework OCEAN to perform online task inference for compositional tasks. OCEAN models global and local context variables in a joint latent space, where the global variables represent a mixture of sub-tasks required for the task, while the local variables capture the transitions between the sub-tasks. Our framework supports flexible latent distributions based on prior knowledge of the task structure and can be trained in an unsupervised manner. Experimental results show that OCEAN provides more effective task inference with sequential context adaptation and thus leads to a performance boost on complex, multi-stage tasks.'
volume: 124
URL: https://proceedings.mlr.press/v124/ren20a.html
PDF: http://proceedings.mlr.press/v124/ren20a/ren20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-ren20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Hongyu
family: Ren
- given: Yuke
family: Zhu
- given: Jure
family: Leskovec
- given: Animashree
family: Anandkumar
- given: Animesh
family: Garg
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1378-1387
id: ren20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1378
lastpage: 1387
published: 2020-08-27 00:00:00 +0000
- title: 'Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets'
abstract: 'The paper introduces a novel conditional independence (CI) based method for linear and nonlinear, lagged and contemporaneous causal discovery from observational time series in the causally sufficient case. Existing CI-based methods such as the PC algorithm and also common methods from other frameworks suffer from low recall and partially inflated false positives for strong autocorrelation which is an ubiquitous challenge in time series. The novel method, PCMCI$^+$, extends PCMCI [Runge et al., 2019b] to include discovery of contemporaneous links. PCMCI$^+$ improves the reliability of CI tests by optimizing the choice of conditioning sets and even benefits from autocorrelation. The method is order-independent and consistent in the oracle case. A broad range of numerical experiments demonstrates that PCMCI$^+$ has higher adjacency detection power and especially more contemporaneous orientation recall compared to other methods while better controlling false positives. Optimized conditioning sets also lead to much shorter runtimes than the PC algorithm. PCMCI$^+$ can be of considerable use in many real world application scenarios where often time resolutions are too coarse to resolve time delays and strong autocorrelation is present.'
volume: 124
URL: https://proceedings.mlr.press/v124/runge20a.html
PDF: http://proceedings.mlr.press/v124/runge20a/runge20a.pdf
edit: https://github.com/mlresearch//v124/edit/gh-pages/_posts/2020-08-27-runge20a.md
series: 'Proceedings of Machine Learning Research'
container-title: 'Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)'
publisher: 'PMLR'
author:
- given: Jakob
family: Runge
editor:
- given: Jonas
family: Peters
- given: David
family: Sontag
page: 1388-1397
id: runge20a
issued:
date-parts:
- 2020
- 8
- 27
firstpage: 1388
lastpage: 1397
published: 2020-08-27 00:00:00 +0000