Human Learning of Hierarchical Graphs

Abstract

Humans are constantly exposed to sequences of events in the environment. Those sequences frequently evince statistical regularities, such as the probabilities with which one event transitions to another. Collectively, inter-event transition probabilities can be modeled as a graph or network. Many real-world networks are organized hierarchically and understanding how these networks are learned by humans is an ongoing aim of current investigations. While much is known about how humans learn basic transition graph topology, whether and to what degree humans can learn hierarchical structures in such graphs remains unknown. Here, we investigate how humans learn hierarchical graphs of the Sierpiński family using computer simulations and behavioral laboratory experiments. We probe the mental estimates of transition probabilities via the surprisal effect: a phenomenon in which humans react more slowly to less expected transitions, such as those between communities or modules in the network. Using mean-field predictions and numerical simulations, we show that surprisal effects are stronger for finer-level than coarser-level hierarchical transitions. Notably, surprisal effects at coarser levels of the hierarchy are difficult to detect for limited learning times or in small samples. Using a serial response experiment with human participants (n=100), we replicate our predictions by detecting a surprisal effect at the finer-level of the hierarchy but not at the coarser-level of the hierarchy. To further explain our findings, we evaluate the presence of a trade-off in learning, whereby humans who learned the finer-level of the hierarchy better tended to learn the coarser-level worse, and vice versa. Taken together, our computational and experimental studies elucidate the processes by which humans learn sequential events in hierarchical contexts. More broadly, our work charts a road map for future investigation of the neural underpinnings and behavioral manifestations of graph learning.

Figure 1.. Schematic of the task design.

(a) Example sequence of visual stimuli; each row is shown to the participant one at a time. In this example, each row represents a unique color pattern of nine squares which corresponds to a unique node in a transition graph. For each participant, a sequence of 1500 stimuli was drawn via a random walk on the same three-level Sierpiński graph ${}^3{S}_p^n$ (Methods). (b) A part of the transition graph that involves the nodes in panel (a). The mapping between the color pattern in panel (a) and the node index in panel (b) was shuffled uniformly at random across participants so that any systematic biases of reactions to certain color patterns would be balanced across nodes. (c) Hand placement; each of the keys highlighted in green corresponds to a square in any row of panel (a). When the squares were highlighted in red in panel (a), the participants were asked to press the corresponding keyboard input combinations, which were drawn from a total of 27 possible combinations that did not require coordination between the two hands.

Figure 2.. Predictions of human learning and its dependence on hierarchy in the structure of transition probabilities between stimuli.

Here we use a validated model of human perception to predict how humans will respond to sequential information drawn from a graph topology [16]. A key indicator of human learning is a slowing of reaction time at the boundary between clusters in the graph. This slowing is referred to as the cross-cluster surprisal (CCS), which we show here for self-loop regularized level-3 Sierpiński graphs with different bases. (a) Visualizations of Sierpiński graphs of base three, four, and five with a power of three. Nodes are shown in pink and edges are shown in green, except for the self-loop edges that are shown in black, because they do not belong to any well-defined edge level. The saturation of the green indicates the level of the hierarchy at which the edge is defined; we refer to this level as the edge level in the color bar label. We use a bottom-up convention for levels, meaning that the finest level is level-1 and the level value increases as the scale increases. (b) The cross-cluster surprisal (CCS) for the corresponding Sierpiński graphs in panel (a) as a function of β: the rate of error in memory when updating the mental model of the transition graph. The β value at which the cross-cluster surprisal peaks is marked for both levels of the graph’s hierarchy.

Figure 3.. Predictions of human learning and its dependence on hierarchy in self-loop regularized base-3 Sierpínski graphs that encode transition probabilities between stimuli.

Here again we use a validated model of human perception to predict how humans will respond to sequential information drawn from a graph topology [16]. (a) Visualizations of Sierpínski graphs of power three, four, and five with a base of three. Nodes are shown in pink and edges are shown in green, except for the self-loop edges that are shown in black, because they do not belong to any well-defined edge level. The saturation of the green indicates the level of the hierarchy at which the edge exists; we refer to this level as the edge level in the color bar label. (b) The cross-cluster surprisal (CCS) for corresponding Sierpínski graphs in panel (a) as a function of β, which is the rate of error in memory when updating the mental model of the transition graph. The β value at which the cross-cluster surprisal peaks is marked for all levels of the graph’s hierarchy.

Figure 4.. Using the maximum entropy model to estimate the cross-cluster surprisal for individual human participants.

When fitting the maximum entropy model to the human reaction time (rt) data, we estimate three separate parameters as specified by the linear relation rt = r₀ + r₁a(β), where r₀ is intercept, r₁ is slope, and β is the rate of error in memory when updating the mental model of the transition graph. (a) Histogram of the intercept r₀ in the linear model rt = r₀ + r₁a(β). (b) Histogram of the slope r₁ in the linear model rt = r₀ + r₁a(β). (c) Histogram of the β values in the linear model rt = r₀ + r₁a(β). Note, here we only show data from participants whose β satisfied 0 < β < ∞; those excluded were 11 participants whose β = 0 and 2 participants whose β → ∞. (d-e) Cross-cluster surprisal at level-1 (d) and level-2 (e), including the 87 participants whose β satisfied 0 < β < ∞. The p-values were obtained from one-sample Wilcoxon signed-rank tests, where we subtracted 1 from the cross-cluster surprisal value and compared the resultant number to a null distribution centered at zero. An individual asterisk above a boxplot indicates a p-value less than 0.05; two asterisks indicate a p-value less than 0.01; three asterisks indicate a p-value less than 0.001; four asterisks indicate a p-value less than 0.0001. Each one-sample Wilcoxon signed-rank test was performed on the data from a single β bin. The β bins are evenly spaced in logarithmic space and the definition of bins is the same throughout the analysis, except there are more bins in the simulations due to the β range being larger in the simulations than in the experiment. The number below each boxplot is the number of human participants with β values in that β bin. For each bin, the box delineates the interquartile range whereas the bottom whisker delineates the 2.5% percentile and the top whisker delineates the 97.5% percentile.

Figure 5.. Dependence of learning estimates on the number of simulated humans in the participant sample.

Here we show boxplots of the cross-cluster surprisal for the Sierpiński graph, ${}^3{S}_3^3$across ten β values and a walk length of 1500 steps. For each β value, the box delineates the interquartile range, the bottom whisker indicates the 2.5% percentile, and the top whisker indicates the 97.5% percentile. The solid curves are mean-field predictions of the cross-cluster surprisal at an infinite time horizon. We sampled 10, 100, and 10000 agents per bin from the total of ten thousand available; columns differ by sample size. (a) The cross-cluster surprisal (CCS) at the finer level of the hierarchy as a function of β: the rate of error in memory when updating the mental model of the transition graph. (b) The cross-cluster surprisal (CCS) at the coarser level of the hierarchy as a function of β.

Figure 6.. Dependence of learning estimates on the number of simulated humans in the participant sample.

Here we show boxplots of the cross-cluster surprisal for the Sierpiński graph ${}^3{S}_3^3$ , across ten β values and a sample size of 100 simulated participants. For each β value, the box delineates the interquartile range, the bottom whisker indicates the 2.5% percentile, and the top whisker indicates the 97.5% percentile. The solid curves are mean-field predictions of the cross-cluster surprisal at an infinite time horizon. We sampled walk lengths of 1500, 4500, and 7500 steps; columns differ by walk length. (a) The cross-cluster surprisal (CCS) at the finer level of the hierarchy as a function of β: the rate of error in memory when updating the mental model of the transition graph. (b) The cross-cluster surprisal (CCS) at the coarser level of the hierarchy as a function of β.

Figure 7.. A power analysis for estimating the surprisal effect in human experiments.

Here we provide plots of powers of one-sided Wilcoxon signed-rank tests on simulated data obtained from the same Sierpiński graph used in the experiment $\left({}^3{S}_3^3\right)$ . To the leftmost β bin in Fig. 5, Fig. 6, and Fig. 4 we assign an index of one, and to the second leftmost bin we assign an index of two, and so on and so forth. Hence, the β bin indices in the plots here refer to the corresponding β bins in Fig. 5, Fig. 6, and Fig. 4. Note that we only included β bins whose empirical sample size (as shown in Fig. 4) is greater than two. To estimate the power of the one-sided Wilcoxon signed-rank test given a sample size n = 1, 2, ..., 99 for each β bin, we uniformly sampled n agents with replacement from the simulation data that had a total of 10, 000 agents per beta bin. We then repeated this process 1000 times. Next, we approximated the statistical power by calculating the ratio of repetitions in which the one-sided Wilcoxon signed-rank test yielded a p-value that was less than 0.05. Because the surprisal effect can happen at two hierarchical levels in the Sierpiński graph ${}^3{S}_3^3$ , here we show power estimates for both levels (shades of green), with different power baselines (95%, 90%, 80%; dashed lines) for reference.

Figure 8.. Trade-off in learning finer versus coarser scales of hierarchical graphs.

Here we plot the Spearman correlation coefficient between the cross-cluster surprisal at the finer scale and the cross-cluster surprisal at the coarser scale, across all β bins for both simulations (in grey) and the experiment (in red). To estimate the spread of Spearman correlation coefficients at different values of N (the total sample size) for the numerical simulations, we uniformly sampled N agents with replacement from the simulation data which had a total of 10, 000 agents per beta bin. Then, we calculated the Spearman correlation coefficient between the cross-cluster surprisal at the finer scale and the cross-cluster surprisal at the coarser scale. Finally, we repeated this process 1000 times. From the 1000 resultant estimates of the Spearman correlation coefficients for each N, we calculated the median, 50% interval, and 95% interval. The red dot indicates the Spearman correlation coefficient (r_s = −0.468) for the empirical data in Fig. 4.