TruthSift is a cloud-based platform that logically combines members' contributions into a collective intelligence. Members add statements and directed connectors to diagrams. TruthSift monitors which statements have been logically established by demonstrations for which every challenge raised has been refuted by an established refutation. When members run out of rational objections, the result is a converged diagram succinctly representing the state of knowledge about a topic, including plausible challenges and how they were refuted. Previous computer systems for collaborative intelligence did not have a qualitatively better solution for combining contributions than voting and are subject to groupthink, interest group capture, and inability to follow a multistep logical argument. They did not settle issues automatically point by point and logically propagate the consequences. I review indications that many practically important statements most people believe to be firmly established will be revealed to be firmly refuted upon computer-assisted scrutiny. TruthSift also supports construction of powerful probabilistic models over networks of causes, implications, tests, and necessary factors.

We analyze the performance of a genetic algorithm (GA) we call Culling, and a variety of other algorithms, on a problem we refer to as the Additive Search Problem (ASP). We show that the problem of learning the Ising perceptron is reducible to a noisy version of ASP. Noisy ASP is the first problem we are aware of where a genetic-type algorithm bests all known competitors. We generalize ASP to k-ASP to study whether GAs will achieve "implicit parallelism" in a problem with many more schemata. GAs fail to achieve this implicit parallelism, but we describe an algorithm we call Explicitly Parallel Search that succeeds. We also compute the optimal culling point for selective breeding, which turns out to be independent of the fitness function or the population distribution. We also analyze a mean field theoretic algorithm performing similarly to Culling on many problems. These results provide insight into when and how GAs can beat competing methods.

We address the problem of how to reinforce learning in ultracomplex environments, with huge state-spaces, where one must learn to exploit a compact structure of the problem domain. The approach we propose is to simulate the evolution of an artificial economy of computer programs. The economy is constructed based on two simple principles so as to assign credit to the individual programs for collaborating on problem solutions. We find empirically that starting from programs that are random computer code, we can develop systems that solve hard problems. In particular, our economy learned to solve almost all random Blocks World problems with goal stacks that are 200 blocks high. Competing methods solve such problems only up to goal stacks of at most 8 blocks. Our economy has also learned to unscramble about half a randomly scrambled Rubik's cube and to solve several commercially sold puzzles.

In a previous article, we considered game trees as graphical models. Adopting an evaluation function that returned a probability distribution over values likely to be taken at a given position, we described how to build a model of uncertainty and use it for utility-directed growth of the search tree and for deciding on a move after search was completed. In some games, such as chess and Othello, the same position can occur more than once, collapsing the game tree to a directed acyclic graph (DAG). This induces correlations among the distributions at sibling nodes. This article discusses some issues that arise in extending our algorithms to a DAG. We give a simply described algorithm for correctly propagating distributions up a game DAG, taking account of dependencies induced by the DAG structure. This algorithm is exponential time in the worst case. We prove that it is #P complete to propagate distributions up a game DAG correctly. We suggest how our exact propagation algorithm can yield a fast but inexact heuristic.

Several recent papers (Gardner and Derrida 1989; Györgyi 1990; Sompolinsky et al. 1990) have found, using methods of statistical physics, that a transition to perfect generalization occurs in training a simple perceptron whose weights can only take values ±1. We give a rigorous proof of such a phenomena. That is, we show, for α = 2.0821, that if at least αn examples are drawn from the uniform distribution on {+1, −1} n and classified according to a target perceptron w t ∈ {+1, −1} n as positive or negative according to whether w t ·x is nonnegative or negative, then the probability is 2 −(√n) that there is any other such perceptron consistent with the examples. Numerical results indicate further that perfect generalization holds for α as low as 1.5.

An algorithm which trains networks using examples and queries is proposed. In a query, the algorithm supplies a y and is told t(y) by an oracle. Queries appear to be available in practice for most problems of interest, e.g. by appeal to a human expert. The author's algorithm is proved to PAC learn in polynomial time the class of target functions defined by layered, depth two, threshold nets having n inputs connected to k hidden threshold units connected to one or more output units, provided k=/<4. While target functions and input distributions can be described for which the algorithm will fail for larger k, it appears likely to work well in practice. Tests of a variant of the algorithm have consistently and rapidly learned random nets of this type. Computational efficiency figures are given. The algorithm can also be proved to learn intersections of k half-spaces in R(n) in time polynomial in both n and k. A variant of the algorithm can learn arbitrary depth layered threshold networks with n inputs and k units in the first hidden layer in time polynomial in the larger of n and k but exponential in the smaller of the two.

Within the context of Valiant's protocol for learning, the perceptron algorithm is shown to learn an arbitrary half-space in time O(n2/∊3) if D, the probability distribution of examples, is taken uniform over the unit sphere Sn. Here ∊ is the accuracy parameter. This is surprisingly fast, as “standard” approaches involve solution of a linear programming problem involving Ω(n/∊) constraints in n dimensions. A modification of Valiant's distribution-independent protocol for learning is proposed in which the distribution and the function to be learned may be chosen by adversaries, however these adversaries may not communicate. It is argued that this definition is more reasonable and applicable to real world learning than Valiant's. Under this definition, the perceptron algorithm is shown to be a distribution-independent learning algorithm. In an appendix we show that, for uniform distributions, some classes of infinite V-C dimension including convex sets and a class of nested differences of convex sets are learnable.

Let N be the class of functions realizable by feedforward linear threshold nets with n input units, two hidden units each of zero threshold, and an output unit. This class is also essentially equivalent to the class of intersections of two open half spaces that are bounded by planes through the origin. We give an algorithm that probably almost correctly (PAC) learns this class from examples and membership queries. The algorithm runs in time polynomial in n, ∊ (the accuracy parameter), and δ (the confidence parameter). If only examples are allowed, but not membership queries, we give an algorithm that learns N in polynomial time provided that the probability distribution D from which examples are chosen satisfies D(x) = D(−x) ∀x. The algorithm yields a hypothesis net with two hidden units, one linear threshold and the other quadratic threshold.

Judd (1988) and Blum and Rivest (1988) have recently proved that the loading problem for neural networks is NP complete. This makes it very unlikely that any algorithm like backpropagation which varies weights on a network of fixed size and topology will be able to learn in polynomial time. However, Valiant has recently proposed a learning protocol (Valiant 1984), which allows one to sensibly consider generalization by learning algorithms with the freedom to add neurons and synapses, as well as simply adjusting weights. Within this context, standard circuit complexity arguments show that learning algorithms with such freedom can solve in polynomial time any learning problem that can be solved in polynomial time by any algorithm whatever. In this sense, neural nets are universal learners, capable of learning any learnable class of concepts.

We address the question of when a network can be expected to generalize from m random training examples chosen from some arbitrary probability distribution, assuming that future test examples are drawn from the same distribution. Among our results are the following bounds on appropriate sample vs. network size. Assume 0 < ∊ ≤ 1/8. We show that if m ≥ O(W/∊ log N/∊) random examples can be loaded on a feedforward network of linear threshold functions with N nodes and W weights, so that at least a fraction 1 − ∊/2 of the examples are correctly classified, then one has confidence approaching certainty that the network will correctly classify a fraction 1 − ∊ of future test examples drawn from the same distribution. Conversely, for fully-connected feedforward nets with one hidden layer, any learning algorithm using fewer than Ω(W/∊) random training examples will, for some distributions of examples consistent with an appropriate weight choice, fail at least some fixed fraction of the time to find a weight choice that will correctly classify more than a 1 − ∊ fraction of the future test examples.