Human Variability and the Explore-Exploit Trade-Off in Recommendation.

The enormous scale of the available information and products on the Internet has necessitated the development of algorithms that intermediate between options and human users. These algorithms attempt to provide the user with relevant information. In doing so, the algorithms may incur potential negative consequences stemming from the need to select items about which it is uncertain to obtain information about users versus the need to select items about which it is certain to secure high ratings. This tension is an instance of the exploration-exploitation trade-off in the context of recommender systems. Because humans are in this interaction loop, the long-term trade-off behavior depends on human variability. Our goal is to characterize the trade-off behavior as a function of human variability fundamental to such human-algorithm interaction. To tackle the characterization, we first introduce a unifying model that smoothly transitions between active learning and recommending relevant information. The unifying model gives us access to a continuum of algorithms along the exploration-exploitation trade-off. We then present two experiments to measure the trade-off behavior under two very different levels of human variability. The experimental results inform a thorough simulation study in which we modeled and varied human variability systematically over a wide rage. The main result is that exploration-exploitation trade-off grows in severity as human variability increases, but there exists a regime of low variability where algorithms balanced in exploration and exploitation can largely overcome the trade-off.

The Inner Loop of Collective Human-Machine Intelligence.

With the rise of artificial intelligence (AI) and the desire to ensure that such machines work well with humans, it is essential for AI systems to actively model their human teammates, a capability referred to as Machine Theory of Mind (MToM). In this paper, we introduce the inner loop of human-machine teaming expressed as communication with MToM capability. We present three different approaches to MToM: (1) constructing models of human inference with well-validated psychological theories and empirical measurements; (2) modeling human as a copy of the AI; and (3) incorporating well-documented domain knowledge about human behavior into the above two approaches. We offer a formal language for machine communication and MToM, where each term has a clear mechanistic interpretation. We exemplify the overarching formalism and the specific approaches in two concrete example scenarios. Related work that demonstrates these approaches is highlighted along the way. The formalism, examples, and empirical support provide a holistic picture of the inner loop of human-machine teaming as a foundational building block of collective human-machine intelligence.

Mitigating belief projection in explainable artificial intelligence via Bayesian teaching.

State-of-the-art deep-learning systems use decision rules that are challenging for humans to model. Explainable AI (XAI) attempts to improve human understanding but rarely accounts for how people typically reason about unfamiliar agents. We propose explicitly modelling the human explainee via Bayesian teaching, which evaluates explanations by how much they shift explainees' inferences toward a desired goal. We assess Bayesian teaching in a binary image classification task across a variety of contexts. Absent intervention, participants predict that the AI's classifications will match their own, but explanations generated by Bayesian teaching improve their ability to predict the AI's judgements by moving them away from this prior belief. Bayesian teaching further allows each case to be broken down into sub-examples (here saliency maps). These sub-examples complement whole examples by improving error detection for familiar categories, whereas whole examples help predict correct AI judgements of unfamiliar cases.

A Unifying Computational Framework for Teaching and Active Learning.

Traditionally, learning has been modeled as passively obtaining information or actively exploring the environment. Recent research has introduced models of learning from teachers that involve reasoning about why they have selected particular evidence. We introduce a computational framework that takes a critical step toward unifying active learning and teaching by recognizing that meta-reasoning underlying reasoning about others can be applied to reasoning about oneself. The resulting Self-Teaching model captures much of the behavior of information-gain-based active learning with elements of hypothesis-testing-based active learning and can thus be considered as a formalization of active learning within the broader teaching framework. We present simulation experiments that characterize the behavior of the model within three simple and well-investigated learning problems. We conclude by discussing such theory-of-mind-based learning in the context of core cognition and cognitive development.

Theoretical perspectives on active sensing.

A key component of interacting with the world is how to direct ones' sensors so as to extract task-relevant information - a process referred to as active sensing. In this review, we present a framework for active sensing that forms a closed loop between an ideal observer, that extracts task-relevant information from a sequence of observations, and an ideal planner which specifies the actions that lead to the most informative observations. We discuss active sensing as an approximation to exploration in the wider framework of reinforcement learning, and conversely, discuss several sensory, perceptual, and motor processes as approximations to active sensing. Based on this framework, we introduce a taxonomy of sensing strategies, identify hallmarks of active sensing, and discuss recent advances in formalizing and quantifying active sensing.

Active sensing in the categorization of visual patterns.

Interpreting visual scenes typically requires us to accumulate information from multiple locations in a scene. Using a novel gaze-contingent paradigm in a visual categorization task, we show that participants' scan paths follow an active sensing strategy that incorporates information already acquired about the scene and knowledge of the statistical structure of patterns. Intriguingly, categorization performance was markedly improved when locations were revealed to participants by an optimal Bayesian active sensor algorithm. By using a combination of a Bayesian ideal observer and the active sensor algorithm, we estimate that a major portion of this apparent suboptimality of fixation locations arises from prior biases, perceptual noise and inaccuracies in eye movements, and the central process of selecting fixation locations is around 70% efficient in our task. Our results suggest that participants select eye movements with the goal of maximizing information about abstract categories that require the integration of information from multiple locations.

Modeling genome-wide replication kinetics reveals a mechanism for regulation of replication timing.

Microarrays are powerful tools to probe genome-wide replication kinetics. The rich data sets that result contain more information than has been extracted by current methods of analysis. In this paper, we present an analytical model that incorporates probabilistic initiation of origins and passive replication. Using the model, we performed least-squares fits to a set of recently published time course microarray data on Saccharomyces cerevisiae. We extracted the distribution of firing times for each origin and found that the later an origin fires on average, the greater the variation in firing times. To explain this trend, we propose a model where earlier-firing origins have more initiator complexes loaded and a more accessible chromatin environment. The model demonstrates how initiation can be stochastic and yet occur at defined times during S phase, without an explicit timing program. Furthermore, we hypothesize that the initiators in this model correspond to loaded minichromosome maintenance complexes. This model is the first to suggest a detailed, testable, biochemically plausible mechanism for the regulation of replication timing in eukaryotes.

Reconciling stochastic origin firing with defined replication timing.

Eukaryotic chromosomes replicate with defined timing patterns. However, the mechanism that regulates the timing of replication is unknown. In particular, there is an apparent conflict between population experiments, which show defined average replication times, and single-molecule experiments, which show that origins fire stochastically. Here, we provide a simple simulation that demonstrates that stochastic origin firing can produce defined average patterns of replication firing if two criteria are met. The first is that origins must have different relative firing probabilities, with origins that have relatively high firing probability being likely to fire in early S phase and origins with relatively low firing probability being unlikely to fire in early S phase. The second is that the firing probability of all origins must increase during S phase to ensure that origins with relatively low firing probability, which are unlikely to fire in early S phase, become likely to fire in late S phase. In addition, we propose biochemically plausible mechanisms for these criteria and point out how stochastic and defined origin firing can be experimentally distinguished in population experiments.

Computational methods to study kinetics of DNA replication.

New technologies such as DNA combing have led to the availability of large quantities of data that describe the state of DNA while undergoing replication in S phase. In this chapter, we describe methods used to extract various parameters of replication--fork velocity, origin initiation rate, fork density, numbers of potential and utilized origins--from such data. We first present a version of the technique that applies to "ideal" data. We then show how to deal with, a number of real-world complications, such as the asynchrony of starting times of a population of cells, the finite length of fragments used in the analysis, and the finite amount of DNA in a chromosome.

How Xenopus laevis embryos replicate reliably: investigating the random-completion problem.

DNA synthesis in Xenopus frog embryos initiates stochastically in time at many sites (origins) along the chromosome. Stochastic initiation implies fluctuations in the time to complete and may lead to cell death if replication takes longer than the cell cycle time ( approximately 25 min) . Surprisingly, although the typical replication time is about 20 min , in vivo experiments show that replication fails to complete only about 1 in 300 times. How is replication timing accurately controlled despite the stochasticity? Biologists have proposed two solutions to this "random-completion problem." The first solution uses randomly located origins but increases their rate of initiation as S phase proceeds, while the second uses regularly spaced origins. In this paper, we investigate the random-completion problem using a type of model first developed to describe the kinetics of first-order phase transitions. Using methods from the field of extreme-value statistics, we derive the distribution of replication-completion times for a finite genome. We then argue that the biologists' first solution to the problem is not only consistent with experiment but also nearly optimizes the use of replicative proteins. We also show that spatial regularity in origin placement does not alter significantly the distribution of replication times and, thus, is not needed for the control of replication timing.