Is Holism A Problem For Inductive Inference? A Computational Analysis

Is Holism A Problem For Inductive Inference? A Computational Analysis Maxwell A. Bertolero (bertolero@berkeley.edu) Thomas L. Griffiths (tom griffiths@berkeley.edu) Department of Psychology & Helen Wills Neuroscience Institute, University of California, Berkeley, Berkeley, CA 94720 USA Abstract (Koller & Friedman, 2009). Thus, the connectivity struc- ture of our concepts might not render inductive inference in- tractable if the size of the largest clique only increases slowly as the network grows. Here, we examine whether the connectivity structure of hu- man concepts supports efficient probabilistic inference, pro- viding a potential response to concerns about holism. We an- alyze a large network of concepts intended to capture human common-sense knowledge, using tools from graph theory and results concerning the computational complexity of inference in Bayesian networks. By examining the rate at which the largest clique grows—and the factors that contribute to the growth—we determine whether probabilistic inference could be conducted efficiently over human concepts. We investigate whether holism presents a problem for in- ductive inference by examining the relationship between the size of a Bayesian network that represents human conceptual knowledge and the computational complexity of probabilistic inference in that network. We find that, despite prior claims, holism may not be a problem for inductive inference, as com- putational cost does not increase exponentially as the network grows. While the network we analyze is holistic, it has a mod- ular organization and grows in a way that potentially makes efficient inductive inference possible. Keywords: holism; inductive inference; Fodor; Bayesian net- works; graph theory; complex networks; ConceptNet Introduction Fodor (1983) claims that, while processes like vision can function adaptively almost purely based on sensory input from the eyes, central cognitive processes like decision- making only function adaptively if they integrate every bit of relevant information (i.e., if every variable is connected). Fodor argues that this holism—that everything we experience is potentially relevant to every conclusion we might want to draw—makes inductive inference intractable. This argument revisits Hume’s (1739) observation that there are no rules of induction—one cannot know a priori what variables to evalu- ate for evidence of a belief, as every variable is potentially rel- evant to the belief in question. This seems to make inductive inference intractable, as one must do an exhaustive analysis of every connected variable during inductive inference. If the intractability of inductive inference was not suffi- ciently concerning by itself, Fodor (2001) raises the stakes by arguing that holism may also make cognitive science a futile effort. If central cognitive processes involve inductive infer- ence, then they are potentially holistic. Science carves nature at its joints, dividing and conquering. However, holistic sys- tems have no joints, so Fodor argues that scientists should give up studying central cognitive processes, like decision making, where holism is an issue. He recommends focusing on non-holistic processes like vision. Concerns about the impact of holism are based on the idea that all human concepts are connected (more precisely, that any one proposition involving particular concepts could bear on the confirmation of any other proposition, even ones in- volving different concepts). However, research in statistical machine learning has shown that variables being connected is not intrinsically a problem for inductive inference. Work on Bayesian networks shows that the complexity of probabilis- tic inference increases as a (potentially exponential) function of the size of the largest “clique” (i.e., fully connected set of nodes) in the graph of dependencies between variables Bayesian Networks and Holism A graph is a mathematical model that represents a network. This model represents the network’s entities as nodes, and connections between entities as edges that connect the nodes (see Figure 1). A Bayesian network is probabilistic graphi- cal model that represents a set of variables as nodes and the dependencies between those variables as edges in a graph (Pearl, 1988). The graph structure can be used to support probabilistic inference, calculating the probability distribu- tion over the variables given the observed values of a subset of those variables. Concerns about holism are based on the fact that all hu- man concepts seem potentially related. If we imagine these concepts being arranged as the nodes in a graph, with edges indicating relationships, then we might be concerned about holism if the graph is connected—if we can find a sequence of edges that links any pair of nodes. But the fundamental con- cern is about the tractability of inductive inference—whether it is possible to make inductive inferences under these cir- cumstances. In computer science, problems are considered intractable if the amount of time taken to solve the problem increases exponentially in the size of the problem. This es- tablishes a basic criterion for determining whether holism is a challenge for inductive inference: determining whether the time taken to perform probabilistic inference in a Bayesian network that captures the dependency structure of human concepts increases exponentially as the network grows. Probabilistic inference in Bayesian networks is #P-hard, and the (worst-case) computational complexity of known ex- act (e.g. Koller & Friedman, 2009) and approximate algo- rithms (e.g., Koller, Lerner, & Angelov, 1999; Murphy & Weiss, 2001) for solving this problem is exponential with the size of the largest clique in the moralized and triangulated version of the graph. In other words, the size of the largest