Timezone: »
A common classifier for unlabeled nodes on undirected graphs uses label propagation from the labeled nodes, equivalent to the harmonic predictor on Gaussian random fields (GRFs). For active learning on GRFs, the commonly used V-optimality criterion queries nodes that reduce the L2 (regression) loss. V-optimality satisfies a submodularity property showing that greedy reduction produces a (1 − 1/e) globally optimal solution. However, L2 loss may not characterise the true nature of 0/1 loss in classification problems and thus may not be the best choice for active learning. We consider a new criterion we call Σ-optimality, which queries the node that minimizes the sum of the elements in the predictive covariance. Σ-optimality directly optimizes the risk of the surveying problem, which is to determine the proportion of nodes belonging to one class. In this paper we extend submodularity guarantees from V-optimality to Σ-optimality using properties specific to GRFs. We further show that GRFs satisfy the suppressor-free condition in addition to the conditional independence inherited from Markov random fields. We test Σ-optimality on real-world graphs with both synthetic and real data and show that it outperforms V-optimality and other related methods on classification.
Author Information
Yifei Ma (Amazon)
This is Yifei Ma. I work in Bayesian optimization, recommender systems, graph theory, and temporal modeling. Thanks.
Roman Garnett (Washington University in St. Louis)
Jeff Schneider (CMU)
More from the Same Authors
-
2023 Poster: PID-Inspired Inductive Biases for Deep Reinforcement Learning in Partially Observable Control Tasks »
Ian Char · Jeff Schneider -
2022 Poster: Exploration via Planning for Information about the Optimal Trajectory »
Viraj Mehta · Ian Char · Joseph Abbate · Rory Conlin · Mark Boyer · Stefano Ermon · Jeff Schneider · Willie Neiswanger -
2021 : Bayesian Active Reinforcement Learning »
Viraj Mehta · Biswajit Paria · Jeff Schneider · Willie Neiswanger -
2021 : Reinforcement Learning for Autonomous Driving »
Jeff Schneider · Jeff Schneider -
2021 Poster: Beyond Pinball Loss: Quantile Methods for Calibrated Uncertainty Quantification »
Youngseog Chung · Willie Neiswanger · Ian Char · Jeff Schneider -
2019 : Coffee + Posters »
Benjamin Caine · Renhao Wang · Nazmus Sakib · Nana Otawara · Meha Kaushik · elmira amirloo · Nemanja Djuric · Johanna Rock · Tanmay Agarwal · Angelos Filos · Panagiotis Tigkas · Donsuk Lee · Wootae Jeon · Nikita Jaipuria · Pin Wang · Jinxin Zhao · Liangjun Zhang · Ashutosh Singh · Ershad Banijamali · Mohsen Rohani · Aman Sinha · Ameya Joshi · Ching-Yao Chan · Mohammed Abdou · Changhao Chen · Jong-Chan Kim · eslam mohamed · Matt OKelly · Nirvan Singhania · Hiroshi Tsukahara · Atsushi Keyaki · Praveen Palanisamy · Justin Norden · Micol Marchetti-Bowick · Yiming Gu · Hitesh Arora · Shubhankar Deshpande · Jeff Schneider · Shangling Jui · Vaneet Aggarwal · Tryambak Gangopadhyay · Qiaojing Yan -
2019 Poster: Offline Contextual Bayesian Optimization »
Ian Char · Youngseog Chung · Willie Neiswanger · Kirthevasan Kandasamy · Oak Nelson · Mark Boyer · Egemen Kolemen · Jeff Schneider -
2018 : Marginalized Off-Policy Evaluation for Reinforcement Learning »
Yifei Ma -
2018 Poster: Neural Architecture Search with Bayesian Optimisation and Optimal Transport »
Kirthevasan Kandasamy · Willie Neiswanger · Jeff Schneider · Barnabas Poczos · Eric Xing -
2018 Spotlight: Neural Architecture Search with Bayesian Optimisation and Optimal Transport »
Kirthevasan Kandasamy · Willie Neiswanger · Jeff Schneider · Barnabas Poczos · Eric Xing -
2016 Poster: The Multi-fidelity Multi-armed Bandit »
Kirthevasan Kandasamy · Gautam Dasarathy · Barnabas Poczos · Jeff Schneider -
2016 Poster: Gaussian Process Bandit Optimisation with Multi-fidelity Evaluations »
Kirthevasan Kandasamy · Gautam Dasarathy · Junier B Oliva · Jeff Schneider · Barnabas Poczos -
2015 : Bayesian Optimization and Embedded Learning Systems »
Jeff Schneider -
2014 Poster: Flexible Transfer Learning under Support and Model Shift »
Xuezhi Wang · Jeff Schneider -
2014 Poster: Sampling for Inference in Probabilistic Models with Fast Bayesian Quadrature »
Tom Gunter · Michael A Osborne · Roman Garnett · Philipp Hennig · Stephen J Roberts -
2013 Poster: Learning Hidden Markov Models from Non-sequence Data via Tensor Decomposition »
Tzu-Kuo Huang · Jeff Schneider -
2011 Poster: Group Anomaly Detection using Flexible Genre Models »
Liang Xiong · Barnabas Poczos · Jeff Schneider -
2011 Poster: Learning Auto-regressive Models from Sequence and Non-sequence Data »
Tzu-Kuo Huang · Jeff Schneider -
2010 Poster: Learning Multiple Tasks with a Sparse Matrix-Normal Penalty »
Yi Zhang · Jeff Schneider -
2008 Poster: Learning the Semantic Correlation: An Alternative Way to Gain from Unlabeled Text »
Yi Zhang · Jeff Schneider · Artur Dubrawski