Science as Search and The Curse of Dimensionality

Computer and cognitive scientists have long thought of problem-solving in terms of the search for good solutions in a potentially very large space of possible solutions.^{Reference Newell, Simon and Gardner2} More recently, this way of thinking about research and problem-solving has been generalized to other areas of science, such as astronomy, physics, chemistry, and biology.^{Reference Simon, Langley, Bradshaw, Shrager and Langley3} When applied to medical research, the relevant search is through the space of all possible decision rules that relate particular observations (e.g., a patient's biomarkers) to particular treatments that most effectively alleviate pain and suffering.⁴ How quickly we can search this space for highly effective treatments, guided by specific biomarkers, depends upon how large the space is, and upon the efficiency of our search strategy.

Classically, this search space was not considered to be very large, so a fairly simplistic search strategy based upon large clinical trials was effective. At the peak of the success of classical clinical trials, say 25 years ago, cancer was thought of as what might be called a “10 by 10” disease: There were roughly 10 types of cancer, corresponding to tissue of origin, crossed with roughly 10 types of chemotherapy. This way of thinking is represented by the 100-cell matrix, shown on the left in Figure 1. Each cell in this matrix represents a biomarker-treatment relationship which needs to be tested, with the biomarkers here being the tissue of origin of the cancer, and some other high-level features such as stage and node involvement. For example, non-small cell lung cancer might be a column in this matrix, and the search for the right treatment would involve conducting large, randomized controlled trials for each of the 10 chemotherapies. The roughly 200,000 lung cancer patients each year would provide roughly 10,000 patients per matrix cell (in the lung cancer column), which is plenty of patients to run several large clinical trials of each proposed therapy.

Figure 1

Left: In the "pre-OMIC" era we classified cancers by a handful of features (columns), mostly tissue of origin and stage, crossed with a small number of possible chemotherapeutic treatments (rows), under a small number of protocols. With order 10,000 patients per cell, large trials are efficient. Right: In the present "molecular" era, the feature space in hugely expanded, including molecular and many other observables, and there is a likewise huge combination explosion in treatment number and complexity. As a result there are ∼zero patients per cell!

However, as our understanding of cancer has evolved — recognizing that there are potentially thousands of molecular biomarkers that influence whether a treatment will be effective — we are now facing a very different kind of problem. The space of possible treatment decisions is enormously larger, represented by the matrix on the right in Figure 1. With thousands of molecular features, leading to tens of thousands of combinatorial subtypes, and hundreds of plausible combination therapies, there may be many millions of treatment-decision rules (i.e., matrix cells) that have to be tested. Yet, because (thankfully) there are only about a million advanced cancer patients in the US each year, each cell in this matrix will have, on average, approximately zero observations.

The number of features that determine the size of this search space is called the “dimensionality” of the data, and the number of independent observations is sometimes referred to as the sample size, or “n” of a study. As a result of the combinatorial structure of the problem, each new feature grows the size of the search space exponentially. This is what computer scientists call “The Curse of Dimensionality”; there will simply never be enough patients and clinical trials to fully explore this space and identify the optimal treatments in the traditional way. In fact, even modern adaptive trials, which can potentially test many decision rules, are impotent in the face of this challenge. Therefore, if we are to make progress in identifying effective biomarker-guided treatment strategies, a new, more efficient search strategy is needed.

AI and Big Data to the Rescue?

Now you may be thinking: “Perhaps ‘Big Data’ and artificial intelligence (AI) can solve this problem. Isn't this problem exactly what those tools are supposed to help us do?” Unfortunately, Big Data and AI cannot solve this problem. Let us take a short (self-)drive through some of the details of modern AI, examine why it is so successful in some settings, and then see why cancer research is not analogous to these settings.

The settings in which modern AI has been successful typically share one or more of the following five properties:

1. 1. There are well-defined criteria of success, and the signal of success or failure is rapidly available;

2. 2. Data are cheap and plentiful, so that there is a very large amount of data, relative to the size of the search space;

3. 3. There are expert teachers;

4. 4. It is easy and cheap to run experiments;

5. 5. There are highly veridical simulators based upon detailed (e.g., formal, mathematical) models of the underlying physical processes.

These five properties are closely inter-related. For instance, good simulations and models can be used to create simulated data, to simulate a teacher, to run simulated experiments, and — as we will describe later — to analytically reduce the size of the search space. Games such as chess and Go, and even domains as seemingly complex as self-driving cars, have all or most of the above properties: Go and chess have been played by humans for hundreds or thousands of years. The rules, and what counts as a win or loss, are completely clear, we have a plethora of expert teachers, and we can build perfect simulators. And, for better or worse, pretty much every teenager drives — or can learn to drive — acceptably well.

We therefore have both an existence proof that Go, chess, and driving can be solved — at least to a nominal level — and we know that we can use human players and drivers to train the self-driving cars and Go/chess computers. Moreover, we can build very good simulators for games because we completely understand, and can perfectly model those problem settings. This is only slightly less the case for driving, where there is a significant social aspect, but the physics of driving can at least be modeled in near-perfect detail, enabling near-perfect simulations.

The domain of medicine, by contrast, has almost none of the above five properties: Medical experiments are extremely costly and we lack good treatments for most diseases, and correspondingly lack expert guidance. Indeed, unlike games and puzzles, or even self-driving cars, it is unclear whether some medical problems have solutions at all. There are no existence proofs for most of medicine. You can't just teach your robot doctor to cure cancer by observing good doctors curing cancer, because there are no such doctors and cures. Moreover, there may well not be a cure for cancer at all.

We also cannot create near perfect simulations of disease. In fact, we struggle to create even good simulations for disease, except for certain simple functions, such as those for which we have dynamical models, such as drug metabolism. The immune-system, which is a critical participant in the preponderance of human disease, is of the order of magnitude of complexity of the human brain, and is similarly a self-modifying machine, so that to model someone's immune profile in detail is similar in difficulty to modeling their entire brain, including all of their learned skills and memories. This is well beyond our current, or even our foreseeable simulation capabilities.

In some fields, experiments are extremely expensive — planetary science, for example, might pay millions of dollars to recover a tiny amount of asteroid dust. Yet medical experiments are in some ways worse. Beyond the in vitro and in silico experiments, medical experiments are both extremely expensive and ethically fraught, both in terms of privacy and because data from in vivo and in-patient experiments can subject the participants to extreme pain and suffering, perhaps even death. For example, a phase 2 cancer clinical trial may need 100 to 500 patients, can cost tens of millions of dollars, and can take years to complete.^{Reference Martinez5} Consider, by contrast, that Facebook ran an experiment involving almost 700,000 unpaid subjects in the space of a single week.^{Reference Kramer, Guillory and Hancock6} This volume and efficiency of data generation in Facebook's experiment is what is usually referred to as “Big Data.” Data in medicine is nothing like this.⁷

Global Cumulative Treatment Analysis

One might, at this point, despair that medicine will ever succeed. We are cursed by dimensionality, with no possibility of simulation, very small amounts of extremely expensive, very high dimensionality data whose gathering may well harm or kill people or animals, and not even an existence proof, with rare exception, that medicine works at all!

But there remain untapped resources that can help us climb out of this admittedly very deep hole. We will describe two of these: (1) Treatment Rationales and (2) System-wide Coordination.

Dimensionality Origami: Folding the Map and the Special Role of Treatment Rationales

One way to make a space easier to search is to make it smaller. Think of the matrix like an old-style paper map — one of those giant pieces of paper with well-worn creases at various places, which, if you could just figure it all out, folds into a conveniently glove-compartment-sized package. If you imagine those creases in our matrix (depicted on the right in Figure 2), each crease allows us to bring together some columns and/or rows, and thereby reduces the overall dimensionality of the space, hence reducing the size of the search space, and improving the efficiency of any search method.

Figure 2

Left: Treatment Rationales (diagonal line - one positive (+) and one negative (-) TR is shown, each having two observable "inputs" along the base), as well as other sorts of knowledge and data, provide clues that let us hypothesize "folds" (right) that reduce the size of the space. This makes search (ants as "8"s) more tractable. In addition, coordinating search (ants communicating with "controller") improves search rate by spreading the search more efficiently.

But how are we to discover these “creases” in the map/matrix? The “big data” way to do this is to empirically observe correlations between features. But, as discussed above, this requires much more data than is available, or is likely to become available. Another approach is to use prior knowledge such as formal models, or even partial models. For example, reducing thousands of ACGT base sequences into genes enormously reduces the 3 billion bases of DNA sequence information to around 20,000 features, and this can be reduced even further by recording only aberrations from a standard genome, or by using pathway models, such as BioCyc^{Reference Karp, Billington, Caspi, Fulcher, Latendresse, Kothari, Keseler, Krummenacker, Midford, Ong, Ong, Paley and Subhraveti8} to relate the genes to one another via their associated protein-catalyzed reactions.

Unfortunately, highly veridical biochemical models of mammalian processes, and especially about abnormalities in these processes, are rare.^{Reference Shrager9} Sweetnam, et al.^{Reference Sweetnam, Mocellin, Krauthammer, Knopf, Baertsch and Shrager10} proposed to augment the sparse existing data and models through the collection of what they termed “Treatment Rationales” (TRs). A TR is an explanation for why a particular course of action (e.g., test, treatment, watchful waiting, etc.) was either recommended or rejected.¹¹ TRs are distinct from, and complementary to the many other, already duly recorded aspects of treatment such as case history, test results, treatment hypotheses, and outcomes. All of these are critically important to the progress of the search that is biomedicine, but having TRs which represent the explanations underlying the treatment hypotheses, is, in our view, a critical overlooked resource, given the dearth of good biological models. These TRs represent expert knowledge, contextualized by real cases, that help to reduce the dimensionality of the problem by providing hints as to how to fold the space (Fig. 2, left).¹²

The capture and use of TRs also honors both patients' and physicians' knowledge, and the whole process honors their decision authority. Not only do we encourage complete autonomy, but we want to know the reason for physicians' and patients' decisions because these almost certainly provide valuable insights into the domain.