Probabilistic DAG search

Julia Grosse, Cheng Zhang, Philipp Hennig
Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, PMLR 161:1424-1433, 2021.

Abstract

Exciting contemporary machine learning problems have recently been phrased in the classic formalism of tree search — most famously, the game of Go. Interestingly, the state-space underlying these sequential decision-making problems often posses a more general latent structure than can be captured by a tree. In this work, we develop a probabilistic framework to exploit a search space’s latent structure and thereby share information across the search tree. The method is based on a combination of approximate inference in jointly Gaussian models for the explored part of the problem, and an abstraction for the unexplored part that imposes a reduction of complexity ad hoc. We empirically find our algorithm to compare favorably to existing non-probabilistic alternatives in Tic-Tac-Toe and a feature selection application.

Cite this Paper

BibTeX
@InProceedings{pmlr-v161-grosse21a, title = {Probabilistic DAG search}, author = {Grosse, Julia and Zhang, Cheng and Hennig, Philipp}, booktitle = {Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence}, pages = {1424--1433}, year = {2021}, editor = {de Campos, Cassio and Maathuis, Marloes H.}, volume = {161}, series = {Proceedings of Machine Learning Research}, month = {27--30 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v161/grosse21a/grosse21a.pdf}, url = {https://proceedings.mlr.press/v161/grosse21a.html}, abstract = {Exciting contemporary machine learning problems have recently been phrased in the classic formalism of tree search — most famously, the game of Go. Interestingly, the state-space underlying these sequential decision-making problems often posses a more general latent structure than can be captured by a tree. In this work, we develop a probabilistic framework to exploit a search space’s latent structure and thereby share information across the search tree. The method is based on a combination of approximate inference in jointly Gaussian models for the explored part of the problem, and an abstraction for the unexplored part that imposes a reduction of complexity ad hoc. We empirically find our algorithm to compare favorably to existing non-probabilistic alternatives in Tic-Tac-Toe and a feature selection application.} }
Endnote
%0 Conference Paper %T Probabilistic DAG search %A Julia Grosse %A Cheng Zhang %A Philipp Hennig %B Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2021 %E Cassio de Campos %E Marloes H. Maathuis %F pmlr-v161-grosse21a %I PMLR %P 1424--1433 %U https://proceedings.mlr.press/v161/grosse21a.html %V 161 %X Exciting contemporary machine learning problems have recently been phrased in the classic formalism of tree search — most famously, the game of Go. Interestingly, the state-space underlying these sequential decision-making problems often posses a more general latent structure than can be captured by a tree. In this work, we develop a probabilistic framework to exploit a search space’s latent structure and thereby share information across the search tree. The method is based on a combination of approximate inference in jointly Gaussian models for the explored part of the problem, and an abstraction for the unexplored part that imposes a reduction of complexity ad hoc. We empirically find our algorithm to compare favorably to existing non-probabilistic alternatives in Tic-Tac-Toe and a feature selection application.
APA
Grosse, J., Zhang, C. & Hennig, P.. (2021). Probabilistic DAG search. Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 161:1424-1433 Available from https://proceedings.mlr.press/v161/grosse21a.html.

Related Material