Inference and Search on Graph-Structured Spaces
- PDF / 5,911,389 Bytes
- 23 Pages / 595.224 x 790.955 pts Page_size
- 16 Downloads / 214 Views
ORIGINAL PAPER
Inference and Search on Graph-Structured Spaces Charley M. Wu1,2,3
· Eric Schulz4 · Samuel J. Gershman2,5
Accepted: 4 September 2020 © The Author(s) 2020
Abstract How do people learn functions on structured spaces? And how do they use this knowledge to guide their search for rewards in situations where the number of options is large? We study human behavior on structures with graph-correlated values and propose a Bayesian model of function learning to describe and predict their behavior. Across two experiments, one assessing function learning and one assessing the search for rewards, we find that our model captures human predictions and sampling behavior better than several alternatives, generates human-like learning curves, and also captures participants’ confidence judgements. Our results extend past models of human function learning and reward learning to more complex, graph-structured domains. Keywords Function learning · Generalization · Inference · Graphs · Exploration-exploitation
Introduction On September 15th, 1835, Charles Darwin and the crew of the HMS Beagle arrived in the Galapagos Islands. As part of a 5-year journey to study plants and animals along the coast of South America, Darwin collected specimens of Galapagos finches, which would become an important keystone for his theory of evolution. Back in England, Darwin began to study the geographical distribution of the birds, particularly the relationship between their features and their habitat. He noticed that while finches on nearby islands had similar beaks (e.g., the vegetarian tree finches and the large insectivorous tree finches with their broad and stout beaks), finches on more distant islands were more dissimilar (e.g., the cactus ground finch with its long and spike-like beak). From these observations, Darwin Charley M. Wu
[email protected] 1
Present address: Human and Machine Cognition Lab, University of T¨ubingen, T¨ubingen, Germany
2
Harvard University, Cambridge, MA, USA
3
Center for Adaptive Rationality, Max Planck Institute for Human Development, Berlin, Germany
4
Max Planck Institute for Biological Cybernetics, T¨ubingen, Germany
5
Center for Brains, Minds and Machines, Cambridge, MA, USA
concluded that these finches all originally derived from the same finch and then gradually adapted to the conditions of the Islands. Since nearby islands had similar conditions, finches on these islands had more similar beaks. Darwin’s historical insight is an example of function learning, where a function represents a mapping from some input space to some output space. In Darwin’s case, the hypothesis was a function mapping a bird’s habitat to the characteristics of its beak (e.g., size). Function learning has traditionally been studied with continuous input spaces, but functions can also be defined over discrete input spaces such as graphs. While the geography of habitats can sometimes be described by a Cartesian coordinate system (latitude and longitude), the Galapagos is structured as a chain of islands,
Data Loading...
