Uncertainty-Guided Likelihood Tree Search
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911137522515968 |
|---|---|
| author | Grosse, Julia Wu, Ruotian Rashid, Ahmad Zhang, Cheng Hennig, Philipp Poupart, Pascal Kristiadi, Agustinus |
| author_facet | Grosse, Julia Wu, Ruotian Rashid, Ahmad Zhang, Cheng Hennig, Philipp Poupart, Pascal Kristiadi, Agustinus |
| contents | Tree search is a fundamental tool for planning, as many sequential decision-making problems can be framed as searching over tree-structured spaces. We propose an uncertainty-guided tree search algorithm for settings where the reward function is a log-likelihood function of the paths. Due to the combinatorial explosion of the tree size, the set of paths for which one can obtain rewards is sparse, particularly when the likelihood is obtained through expensive evaluations, such as by querying a large language model. We address this challenge by deriving an probabilistic search heuristic based on regularity assumptions for the likelihood. Unlike existing tree search methods, the proposed method can perform backtracking and trade-off exploration with exploitation, and yet does not require expensive roll-outs, or sophisticated Bayesian inference. Through extensive on-model and off-model experiments on timely, large-scale practical applications, we demonstrate that our method identifies paths with high likelihood while requiring fewer costly evaluations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_03951 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Uncertainty-Guided Likelihood Tree Search Grosse, Julia Wu, Ruotian Rashid, Ahmad Zhang, Cheng Hennig, Philipp Poupart, Pascal Kristiadi, Agustinus Machine Learning Tree search is a fundamental tool for planning, as many sequential decision-making problems can be framed as searching over tree-structured spaces. We propose an uncertainty-guided tree search algorithm for settings where the reward function is a log-likelihood function of the paths. Due to the combinatorial explosion of the tree size, the set of paths for which one can obtain rewards is sparse, particularly when the likelihood is obtained through expensive evaluations, such as by querying a large language model. We address this challenge by deriving an probabilistic search heuristic based on regularity assumptions for the likelihood. Unlike existing tree search methods, the proposed method can perform backtracking and trade-off exploration with exploitation, and yet does not require expensive roll-outs, or sophisticated Bayesian inference. Through extensive on-model and off-model experiments on timely, large-scale practical applications, we demonstrate that our method identifies paths with high likelihood while requiring fewer costly evaluations. |
| title | Uncertainty-Guided Likelihood Tree Search |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2407.03951 |