Timezone: »
It was recently proved using graph covers (Ruozzi, 2012) that the Bethe partition function is upper bounded by the true partition function for a binary pairwise model that is attractive. Here we provide a new, arguably simpler proof from first principles. We make use of the idea of clamping a variable to a particular value. For an attractive model, we show that summing over the Bethe partition functions for each sub-model obtained after clamping any variable can only raise (and hence improve) the approximation. In fact, we derive a stronger result that may have other useful implications. Repeatedly clamping until we obtain a model with no cycles, where the Bethe approximation is exact, yields the result. We also provide a related lower bound on a broad class of approximate partition functions of general pairwise multi-label models that depends only on the topology. We demonstrate that clamping a few wisely chosen variables can be of practical value by dramatically reducing approximation error.
Author Information
Adrian Weller (Cambridge, Alan Turing Institute)
Adrian Weller is Programme Director for AI at The Alan Turing Institute, the UK national institute for data science and AI, where he is also a Turing Fellow leading work on safe and ethical AI. He is a Senior Research Fellow in Machine Learning at the University of Cambridge, and at the Leverhulme Centre for the Future of Intelligence where he leads the project on Trust and Transparency. His interests span AI, its commercial applications and helping to ensure beneficial outcomes for society. He serves on several boards including the Centre for Data Ethics and Innovation. Previously, Adrian held senior roles in finance.
Tony Jebara (Spotify)
Related Events (a corresponding poster, oral, or spotlight)
-
2014 Oral: Clamping Variables and Approximate Inference »
Thu Dec 11th 02:50 -- 03:10 PM Room Level 2, room 210
More from the Same Authors
-
2020 Workshop: Privacy Preserving Machine Learning - PriML and PPML Joint Edition »
Borja Balle · James Bell · Aurélien Bellet · Kamalika Chaudhuri · Adria Gascon · Antti Honkela · Antti Koskela · Casey Meehan · Olga Ohrimenko · Mi Jung Park · Mariana Raykova · Mary Anne Smart · Yu-Xiang Wang · Adrian Weller -
2020 Poster: Ode to an ODE »
Krzysztof Choromanski · Jared Quincy Davis · Valerii Likhosherstov · Xingyou Song · Jean-Jacques Slotine · Jacob Varley · Honglak Lee · Adrian Weller · Vikas Sindhwani -
2019 Workshop: Privacy in Machine Learning (PriML) »
Borja Balle · Kamalika Chaudhuri · Antti Honkela · Antti Koskela · Casey Meehan · Mi Jung Park · Mary Anne Smart · Mary Anne Smart · Adrian Weller -
2019 Workshop: Workshop on Human-Centric Machine Learning »
Plamen P Angelov · Nuria Oliver · Adrian Weller · Manuel Rodriguez · Isabel Valera · Silvia Chiappa · Hoda Heidari · Niki Kilbertus -
2019 Poster: Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models »
Yunfei Teng · Wenbo Gao · François Chalus · Anna Choromanska · Donald Goldfarb · Adrian Weller -
2019 Poster: A New Distribution on the Simplex with Auto-Encoding Applications »
Andrew Stirn · Tony Jebara · David Knowles -
2018 Workshop: Privacy Preserving Machine Learning »
Adria Gascon · Aurélien Bellet · Niki Kilbertus · Olga Ohrimenko · Mariana Raykova · Adrian Weller -
2018 Poster: Geometrically Coupled Monte Carlo Sampling »
Mark Rowland · Krzysztof Choromanski · François Chalus · Aldo Pacchiano · Tamas Sarlos · Richard Turner · Adrian Weller -
2018 Spotlight: Geometrically Coupled Monte Carlo Sampling »
Mark Rowland · Krzysztof Choromanski · François Chalus · Aldo Pacchiano · Tamas Sarlos · Richard Turner · Adrian Weller -
2017 Symposium: Kinds of intelligence: types, tests and meeting the needs of society »
José Hernández-Orallo · Zoubin Ghahramani · Tomaso Poggio · Adrian Weller · Matthew Crosby -
2017 Poster: From Parity to Preference-based Notions of Fairness in Classification »
Muhammad Bilal Zafar · Isabel Valera · Manuel Rodriguez · Krishna Gummadi · Adrian Weller -
2017 Poster: The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings »
Krzysztof Choromanski · Mark Rowland · Adrian Weller -
2017 Poster: Uprooting and Rerooting Higher-Order Graphical Models »
Mark Rowland · Adrian Weller -
2016 Workshop: Reliable Machine Learning in the Wild »
Dylan Hadfield-Menell · Adrian Weller · David Duvenaud · Jacob Steinhardt · Percy Liang -
2016 Symposium: Machine Learning and the Law »
Adrian Weller · Thomas D. Grant · Conrad McDonnell · Jatinder Singh -
2015 Workshop: Learning and privacy with incomplete data and weak supervision »
Giorgio Patrini · Tony Jebara · Richard Nock · Dimitrios Kotzias · Felix Xinnan Yu -
2015 Symposium: Algorithms Among Us: the Societal Impacts of Machine Learning »
Michael A Osborne · Adrian Weller · Murray Shanahan -
2014 Poster: Making Pairwise Binary Graphical Models Attractive »
Nicholas Ruozzi · Tony Jebara -
2014 Spotlight: Making Pairwise Binary Graphical Models Attractive »
Nicholas Ruozzi · Tony Jebara -
2013 Poster: A multi-agent control framework for co-adaptation in brain-computer interfaces »
Josh S Merel · Roy Fox · Tony Jebara · Liam Paninski -
2013 Poster: Adaptive Anonymity via $b$-Matching »
Krzysztof M Choromanski · Tony Jebara · Kui Tang -
2013 Spotlight: Adaptive Anonymity via $b$-Matching »
Krzysztof M Choromanski · Tony Jebara · Kui Tang -
2012 Workshop: Log-Linear Models »
Dimitri Kanevsky · Tony Jebara · Li Deng · Stephen Wright · Georg Heigold · Avishy Carmi -
2012 Poster: Majorization for CRFs and Latent Likelihoods »
Tony Jebara · Anna Choromanska -
2012 Spotlight: Majorization for CRFs and Latent Likelihoods »
Tony Jebara · Anna Choromanska -
2011 Poster: Variance Penalizing AdaBoost »
Pannagadatta K Shivaswamy · Tony Jebara -
2011 Poster: Learning a Distance Metric from a Network »
Blake Shaw · Bert Huang · Tony Jebara -
2008 Workshop: Analyzing Graphs: Theory and Applications »
Edo M Airoldi · David Blei · Jake M Hofman · Tony Jebara · Eric Xing -
2008 Poster: Relative Margin Machines »
Pannagadatta K Shivaswamy · Tony Jebara -
2008 Session: Oral session 8: Physics and High Order Statistics »
Tony Jebara -
2007 Poster: Density Estimation under Independent Similarly Distributed Sampling Assumptions »
Tony Jebara · Yingbo Song · Kapil Thadani -
2007 Spotlight: Density Estimation under Independent Similarly Distributed Sampling Assumptions »
Tony Jebara · Yingbo Song · Kapil Thadani -
2007 Spotlight: Learning Monotonic Transformations for Classification »
Andrew G Howard · Tony Jebara -
2007 Poster: Learning Monotonic Transformations for Classification »
Andrew G Howard · Tony Jebara -
2006 Poster: An EM Algorithm for Localizing Multiple Sound Sources in Reverberant Environments »
Michael Mandel · Daniel P Ellis · Tony Jebara -
2006 Poster: Gaussian and Wishart Hyperkernels »
Risi Kondor · Tony Jebara