Linear Separation and Learning
By Marvin Minsky and Seymour Papert
Project MAC — Artificial Intelligence Memo No. 167 (October 1968)
Reprint of Chapter 12 of Perceptrons, MIT Press, 1968
12.0 Introduction
The perceptron and the convergence theorems of Chapter 11 are related to many other procedures that are studied in an extensive and disorderly literature under such titles as LEARNING MACHINES, MODELS OF LEARNING, INFORMATION RETRIEVAL, STATISTICAL DECISION THEORY, PATTERN RECOGNITION and many more. In this chapter we will study a few of these to indicate points of contact with the perceptron and to reveal deep differences. We can give neither a fully rigorous account nor a unifying theory of these topics: this would go as far beyond our knowledge as beyond the scope of this book. The chapter is written more in the spirit of inciting students to research than of offering solutions to problems.
12.1 Information Retrieval and Inductive Inference
The perceptron training procedures (Chapter 11) could be used to construct a device that operates within the following pattern of behavior: During a “filing” phase, the machine is shown a “data set” of n-dimensional vectors—one can think of them as n-bit binary numbers or as points in n-space. Later, in a “finding” phase, the machine must be able to decide which of a variety of “query” vectors belong to the data set. To generalize this pattern we will use the term A_file for an algorithm that examines elements of a data set to modify the information in a memory. A_file is designed to prepare the memory for use by another procedure, A_find, which will use the information in the memory to make decisions about query vectors.
This chapter will survey a variety of instances of this general scheme. We will begin by relating the PERCEPTRON procedure to the simplest such scheme: in the COMPLETE STORAGE procedure, A_file merely copies the data vectors, as they come, into the memory. For each query vector, A_find searches exhaustively through memory to see if it is recorded there.
12.1.1 Comparing PERCEPTRON with COMPLETE STORAGE
Our purpose is to illustrate, in this simple case, some of the questions one might ask to compare retrieval schemes:
• Is the procedure universal? The PERCEPTRON scheme works perfectly only under the restriction that the data set is linearly separable. COMPLETE STORAGE is universal: it works for any data set.
• How much memory is required? COMPLETE STORAGE needs a memory large enough to hold the full data set. PERCEPTRON, when it is applicable, sometimes has a summarizing effect, in that the information capacity needed to store its coefficients |α_i| is substantially less than that needed to store the whole data set. We have seen (§10.2) that this is not generally true; the coefficients for parity may need much more storage than does the list of accepted vectors.
• How quickly does A_find operate? The retrieval scheme—exhaustive search specified for COMPLETE STORAGE—is very slow (usually slower than PERCEPTRON’S A_find, which must also retrieve all its coefficients from memory). On the other hand, very similar procedures could be much faster. For example, if A_file did not just store the data set in its order of entry, but sorted the memory into numerical order, then A_find could use a binary search, reducing the query-answer time to log_2(|data set|) memory references. We shall study (in §12.6) A_file algorithms that sacrifice memory size to obtain dramatic further increases in speed (by the so-called hash-coding technique).
• Can the procedure operate with some degree (perhaps measured probabilistically) of success even when A_file has seen only a subset of the data set—call it a “data sample”? PERCEPTRON might, but the COMPLETE STORAGE algorithm, as described, cannot make a reasonable guess when presented with a query vector not in the data sample. This deficiency suggests an important modification of the complete storage procedure: let A_find, instead of merely checking whether the query vector is in the data sample, find that member of the data sample closest to it. This would lead, on an a priori assumption about the “continuity” of the data set, to a degree of generalization as good as the perceptron’s. Unfortunately the speed-up procedures such as hash-coding cease to be available and we conjecture (in a sense to be made more precise in §12.7.6) that the loss is irremediable.
Other considerations we shall mention concern the operation of A_file. We note that the PERCEPTRON and the COMPLETE STORAGE procedures share the following features:
• They act incrementally, that is, change the stored memory slightly as a function of the currently presented member of the data set.
• They operate in “real time” without using large quantities of auxiliary scratch-pad memory.
• They can accept the data set in any order and are tolerant of repetitions that cause only delay but do not change the final state.
On the other hand they differ in at least one very fundamental way: The perceptron’s A_file is a “search procedure” based on feedback from its own results. The complete storage file algorithm is passive. The advantage for the perceptron is that under some conditions it finds an economical summarizing representation. The cost is that it may need to see each data point many times.
12.1.2 Multiple Classification Procedures
It is a slight generalization of these ideas to suppose the data set divided into a number of classes F_1, …, F_k. The algorithm A_file is presented as before with members of the data set but also with indications of the corresponding class. It constructs a body of stored information which is handed over to A_find whose task is to assign query points to their classes using this information.
Example (INNER PRODUCT): We have seen (§11.3.1) how to extend the concept of the perceptron to a multiple classification. The training algorithm, A_file, finds k vectors A_1, …, A_k, and A_find assigns the vector Φ to F_j if Φ · A_j > Φ · A_i (for all i ≠ j).
Example (EUCLIDEAN DISTANCE): The following situation will seem much more familiar to many readers. If we think of each class F_j as a “clump” or “cloud” or “cluster” of points in n-space, then we can imagine that with each F_j is associated a special point B_j that is, somehow, a “typical” or “average” point. For example, B_j could be the center of gravity, that is, the mean of all the vectors in F_j (or, say, of just those vectors that so far have been observed to be in F_j). Then a familiar procedure is: Φ is judged to be in that F_j for which the Euclidean distance ||Φ – B_j|| is the smallest. That is, each Φ is identified with the nearest B-point.
Now this nearness scheme and the inner-product scheme might look quite different, but they are essentially the same! For we have only to observe that the set of points closer to one given point B_1 than to another B_2 is bounded by a hyperplane, and hence can be defined by a linear inequality. Similarly, the points closest to one of a number of B_j’s form a (convex) polygon, and this is true in higher dimensions, also.
Formally, we see this by observing that:
||Φ – B_j||^2 = ||Φ||^2 – 2 Φ · B_j + ||B_j||^2.
Now, if we can assume that all the Φ’s have the same length L, then the Euclidean distance ||Φ – B_j|| will be smallest when Φ · B_j – 1/2 ||B_j||^2 is largest. But this has exactly the inner-product form. To see that the inner-product concept loses nothing by requiring the Φ’s to have the same length, we add an extra dimension and replace each Φ = [ϕ_1, …, ϕ_n] by Φ = [ϕ_1, …, ϕ_n, (L^2 – ∑ ϕ_i^2)^(1/2)] so that all Φ’s have length L. We have to add one dimension to the B’s, too, but can always set its coefficient to zero.
12.2 A Variety of Classification Algorithms
We select, from the infinite variety of schemes that one might use to divide a space into different classes, a few schemes that illustrate aspects of our main subject: computation and linear separation. We will summarize each very briefly here; the remainder of the chapter compares and contrasts some aspects of their algorithmic structures, memory requirements, and commitments they make about the nature of the classes.
Each of our models uses the same basic form of decision algorithm for A_find. In each case there is assigned to each class F_j one or more vectors A_{i,j}; we will represent this assignment by saying that A_{i,j} is associated with F_j. Given a vector Φ, the decision rule is always to choose that F_j for which Φ · A_{i,j} is largest. As noted in §12.1.2 this is mathematically equivalent to a rule that minimizes ||Φ – A_{i,j}|| or some very similar formula.
For each model we must also describe the algorithm A_file that constructs the A’s, on the basis of prior experience, or a priori information about the classes.
12.2.1 The PERCEPTRON Procedure: There is one vector A_j for each class F_j. A_file can be the procedures described in §11.1 for the 2-class case and in §11.4.1 for the multi-class case.
12.2.2 The BAYES Linear Statistical Procedure: Again we have one A_j for each F_j. A_file is quite different, however. For each class F_j and each partial predicate ϕ_i, define w_{i,j} = log(p_{i,j} / (1 – p_{i,j})), where p_{i,j} is the probability that ϕ_i = 1, given that Φ is in F_j. Then define A_j = (θ_j, w_{1,j}, w_{2,j}, …).
We will explain in §12.4.3 the conditions under which this use of “probability” makes sense, and describe some “learning” algorithms that could be used to estimate or approximate the w_{i,j}’s. The BAYES procedure has the advantage that, provided certain statistical conditions are satisfied, it gives good results for classes that are not linearly separable. In fact it gives the lowest possible error rate for procedures in which A_file depends only on conditional probabilities, given that the ϕ’s are statistically independent in the sense explained in §12.4.2. It is astounding that this is achieved by a linear formula.
12.2.3 The BEST PLANES Procedure: In different situations either PERCEPTRON or BAYES may be superior. But often, when the F_j’s are not linearly separable, there will exist a set of A_j vectors which will give fewer errors than either of these schemes. So define the BEST PLANES procedure to use that set of A_j for which choice of the largest Φ · A_j gives the fewest errors.
By definition, BEST PLANES is always at least as good as BAYES or PERCEPTRON. This does not contradict the optimality of BAYES since the search for the best plane uses information other than the conditional probabilities. Unfortunately no practically efficient A_file is known for discovering its A’s. As noted in §12.3, hill-climbing will apparently not work well because of the local peak problem.
12.2.4 The ISODATA Procedure: In the schemes described up to now, we assigned exactly one A-vector to each F-class. If we shift toward the minimum-distance viewpoint, this suggests that such procedures will work satisfactorily only when the F-classes are “localized” into relatively isolated, single regions—one might think of clumps, clusters, or clouds. Given this intuitive picture, one naturally asks what to do if an F-class, while not a neat spherical cluster, is nevertheless semilocalized as a small number of clusters or, perhaps, a snake-like structure. We could still handle such situations, using the least-distance A_find, by assigning an A-vector to each subcluster of each F_j, and using several A’s to outline the spine of the snake. To realize this concept, we need an A_file scheme that has some ability to analyze distributions into clusters. We will describe one such scheme, called ISODATA, in §12.5.
12.2.5 The NEAREST NEIGHBOR Procedure: Our simplest and most radical scheme assumes no limit on the number of A-vectors. A_file stores in memory every Φ that has ever been encountered, together with the name of its associated F-class. Given a query vector Φ_0 we find which Φ in the memory is closest to Φ_0 and choose the F-class associated with that Φ. This is a very generally powerful method: it is very efficient on many sorts of cluster configurations; it never makes a mistake on an already seen point; in the limit it approaches zero error except under rather peculiar circumstances.
NEAREST NEIGHBOR has an obvious disadvantage—the very large memory required—and a subtle disadvantage: there is reason to suspect that it entails large, and fundamentally unavoidable, computation costs (discussed in §12.6).
12.3 Heuristic Geometry of Linear Separation Methods
From the start, the very suggestion that any of these procedures will be any good at all amounts to an a priori proposal that the F-classes can be fitted into simple clouds of some kind, perhaps with a little overlapping. Such an assumption could be justified by some reason for believing that the difference between F_+ and F_- are due to some one major influence plus a variety of smaller, secondary effects. In general PERCEPTRON tends to be sensitive to the outer boundaries of the clouds, and relatively insensitive to the density distributions inside, while BAYES weights all Φ’s equally. In cases that do not satisfy either the single-cloud or the slight-overlap condition, we can expect BAYES to do badly, and presumably PERCEPTRON also. BEST PLANE can be substantially better because it is not subject to the bad influence of symmetry. But finding the BEST PLANE is likely to involve bad computation problems because of multiple, locally optimal “hills.” In the case of a bad “paritylike” situation, even ISODATA will do badly unless it is allowed to have one A-vector for nearly every clump. But in the case of a moderate number of clumps, with an A_k in each, ISODATA should do quite well.
One would expect the NEAREST NEIGHBOR procedure to do well under a very wide range of conditions. Indeed, NEAREST NEIGHBOR in the limiting case of recording all Φ’s with their class names, will do at least as well as any other procedure. There are conditions, though, in which NEAREST NEIGHBOR does not do so well until the sample size is nearly the whole space. Consider, for example, a space in which there are two regions: P(Φ ∈ F_+) = p and P(Φ ∈ F_-) = 1 – p = q. In the upper region a fraction p of the points are in F_+, and these are randomly distributed in space, and similarly for F_- in the lower region. Then if a small fraction of the points are already recorded, the probability that a randomly selected point has the same F as its nearest recorded neighbor is p^2 + q^2 → 1 – 2pq, while the probability of correct identification by BAYES or by BEST PLANE is simply p. Assuming that p > 1/2 we see that:
Error_{NEAREST NEIGHBOR} < 2 × Error_{BEST PLANE}
so that NEAREST NEIGHBOR is worse than BEST PLANE, but not arbitrarily worse. This effect will remain until so many points have been sampled that there is a substantial chance that the sampled point has been sampled before, that is, until a good fraction of the whole space is covered.
On the other side, to the extent that the “mixing” of F_+ and F_- is less severe, NEAREST NEIGHBOR will converge to very good scores as soon as there is a substantial chance of finding one sampled point in most of the microclumps.
A very bad case is a paritylike structure in which NEAREST NEIGHBOR actually does worse than chance. Suppose that Φ ∈ F_1 if and only if ϕ_i = 1 for an even number of i’s. Then, if there are n ϕ’s, each will have exactly n neighbors whose distance d satisfies 0 < d ≤ 1. Suppose that all but a fraction q of all possible Φ’s have already been seen. Then NEAREST NEIGHBOR will err on a given Φ if it has not been seen (probability q) but one of its immediate neighbors has been seen (probability 1 – q^n). So the probability of error is ≥ q(1 – q^n) which, for large n, can be quite near certainty.
This example is, of course, “pathological,” as mathematicians like to say, and NEAREST NEIGHBOR is probably good in many real situations. Its performance depends, of course, on the precise “metric” used to compute distance, and much of classical statistical technique is concerned with optimizing coordinate axes and measurement scales for related applications. Finally, we remark that because the memory and computation costs for this procedure are so high, it is subject to competition from more elaborate schemes outside the regime of linear separation and hence outside the scope of this book.
12.4 Decisions Based on Probabilities of Predicate-Values
Some of the procedures discussed in previous sections might be called “statistical” in the weak sense that their success is not guaranteed except up to some probability. The procedures discussed in this section are statistical also in the firmer sense that they do not store members of the data set directly, but instead store statistical parameters, or measurements, about the data set.
We shall analyze in detail a system that computes—or estimates—the conditional probabilities p_{i,j} that, for each class F_j, the predicate ϕ_i has the value 1. It stores these p_{i,j}’s together with the absolute probabilities p_j of being in each of the F_j’s. Given an observed Φ, the decision to choose an F_j is a typical statistical problem usually solved by a “maximum likelihood” or Bayes-rule method. It is interesting that procedures of this kind resemble very closely the perceptron separation methods. In fact, when we can assume that the conditional probabilities p_{i,j} are suitably independent (§12.4.2) it turns out that the best procedure is the linear threshold decision we called BAYES in §12.2.2. We now show how this comes about.
12.4.1 Maximum Likelihood and Bayes Law
In Chapter 11 we assumed that each Φ is associated with a unique F_j. We now consider the slightly more general case in which the same Φ could be produced by events in several different F-classes. Then, given an observed Φ, we cannot in general be sure which F_j is responsible, but we can at best know the associated probabilities.
Suppose that a particular Φ_0 has occurred and we want to know which F_j is most likely. Now if F_j is responsible, then the “joint event” F_j ∧ Φ_0 has occurred; this has (by definition) probability P(F_j ∧ Φ_0). Now (by definition of conditional probability) we can write:
P(F_j ∧ Φ_0) = P(F_j) · P(Φ_0 | F_j).
That is, the probability that both F_j and Φ_0 will happen together is equal to the probability that F_j will occur multiplied by the probability that if F_j occurs, so will Φ_0.
We should choose that F_j which gives Formula 1 the largest value because that choice corresponds to the most likely of those events that could have occurred. There are serious practical obstacles to the direct use of Formula 1. If there are many different Φ’s it becomes impractical to store all the decisions in memory, let alone to estimate them all on the basis of empirical observation. Nor has the system any ability to guess about Φ’s it has not seen before. We can escape all these difficulties by making one critical assumption—in effect, assuming the situation closely fits a certain model that the partial predicates of Φ = (ϕ_1, …, ϕ_m) are suitably independent.
12.4.2 Independence
We can evade the problems mentioned above if we can assume that the tests ϕ_i(X) are statistically independent over each F-class. Precisely, this means that for any Φ(X) = (ϕ_1(X), …, ϕ_m(X)) we can assert that, for each j:
P(Φ | F_j) = P(ϕ_1 | F_j) × … × P(ϕ_m | F_j).
We emphasize that this is a most stringent condition. For example, it is equivalent to the assertion that: Given that X is in a certain F-class, if one is told also the values of some of the ϕ’s, this gives absolutely no further information about the values of the remaining ϕ’s.
Experimentally, one would expect to find independence when the variations in the values of ϕ’s are due to “noise” or measurement uncertainties within the individual mechanisms. For, to the extent that these have separate causes, one would not expect the values of one to help predict the values of another. But if the variations in the ϕ’s are due to selection of different X’s from the same F-class, one would not ordinarily assume independence, since the value of each tells us something about which X in F has occurred, and hence should help at least partly to predict the values of other ϕ’s.
An extreme example of nonindependence is the following: there are two classes, F_1 and F_2, and two ϕ’s, defined by:
ϕ_1(X) = pure random variable with P(ϕ_1(X) = 1) = 1/2 (its value is determined by tossing a coin, not by X).
ϕ_2(X) = ϕ_1(X) if X ∈ F_1, and 1 – ϕ_1(X) if X ∈ F_2.
Then P(ϕ_1 ∧ ϕ_2 | F_1) = 1/2, but P(ϕ_1 | F_1) · P(ϕ_2 | F_1) = 1/2 · 1/2 = 1/4.
Notice that neither ϕ_1 nor ϕ_2 taken alone gives any information whatever about F! Each appears to be a random coin toss. But from both one can determine perfectly which F has occurred, for ϕ_1 = ϕ_2 implies F_1, while ϕ_1 ≠ ϕ_2 implies F_2 with absolute certainty.
12.4.3 The Maximum Likelihood Decision is a Linear Threshold Predicate
Assume that the ϕ’s are statistically independent for each F_j. Define:
p_j = P(F_j),
p_{i,j} = P(ϕ_i = 1 | F_j),
q_{i,j} = 1 – p_{i,j} = P(ϕ_i = 0 | F_j).
Suppose that we have just observed a Φ = (ϕ_1, …, ϕ_m), and we want to know which F_j was most probably responsible. Then we will choose that j which maximizes:
p_j ∏_{ϕ_i=1} p_{i,j} ∏_{ϕ_i=0} q_{i,j} = p_j ∏_i p_{i,j}^{ϕ_i} q_{i,j}^{1 – ϕ_i} = p_j ∏_i (p_{i,j} / q_{i,j})^{ϕ_i} ∏_i q_{i,j}.
Taking logarithms, we select the largest of:
∑_i ϕ_i log(p_{i,j} / q_{i,j}) + (log p_j + ∑_i log q_{i,j}).
This can be written simply as:
∑_i w_{i,j} ϕ_i + θ_j.
Example 1: In the case that there are just two classes, F_1 and F_2, we decide X ∈ F_1 whenever:
∑ w_{i,1} ϕ_i + θ_1 > ∑ w_{i,2} ϕ_i + θ_2 ⇒ ∑ (w_{i,1} – w_{i,2}) ϕ_i > θ_2 – θ_1,
which has the form of a linear threshold predicate Ψ = [∑ α_i ϕ_i > θ].
Example 2 (Probabilities of Error): Suppose that for all i, p_{i,2} = q_{i,1}. Then p_{i,1} is the probability that ϕ_i(X) = Ψ(X) and q_{i,1} is the probability that ϕ_i(X) ≠ Ψ(X)—that is, that ϕ_i makes an error in predicting Ψ. Then the inequality becomes:
∑ w_{i,1} (2ϕ_i – 1) > log(p_2 / p_1).
Now observe that the (2ϕ_i – 1) term adds or subtracts w_{i,1} according to whether ϕ_i = 1 or 0. Thus we can think of the w’s as weights on a balance scale: log(p_2 / p_1) is the a priori weight in favor of F_2, and each w_{i,1} = log(p_{i,1} / q_{i,1}) is the weight of evidence that ϕ_i = 1 gives in favor of F_1.
12.4.5 Probability-Estimation Procedures
The A_file algorithm for the BAYES procedure has to compute or estimate the probabilities p_{i,j} and p_j. The simplest way to estimate a probability is to find the ratio H/N of favorable events to total events in a sequence. To avoid unlimited memory growth needed to store N, we rewrite the update rule as:
α^[n] = (1 – 1/n) α^[n-1] + (1/n) ϕ^[n].
This suggests a simpler heuristic substitute: define α^[n] = (1 – ε) α^[n-1] + ε ϕ^[n], where ε is a small number between 0 and 1. As n increases, the expected value <α^[n]> approaches p as a limit. This process gives an exponential decay/forgetting mechanism where ancient events decay with coefficient (1 – ε)^(k-n). The variance approaches σ^2 → p(1 – p) ε / (2 – ε), corresponding to an effective forgetting time constant of 1/ε.
12.4.6 The Samuel Compromise
In his classical paper on machine learning in Checkers, Arthur Samuel uses a combination of probability estimation methods. When a new feature is introduced, Samuel uses an adaptive schedule for N:
N = 16 if n < 32; N = 2^m if 2^m ≤ n < 2^{m+1} and 32 ≤ n ≤ 256; N = 256 for n > 256.
Initially the estimate is stabilized as if 16 trials had occurred, then transitions to uniform weighting, and finally converts to exponential decay mode (N = 256) so recent experience outweighs the past.
12.4.7 A Simple Synaptic Reinforcer Theory
We can make a simple neuronal model to estimate p_{i,j} = P(ϕ_i | F_j). Imagine a container B_i with high concentration of substance E and a container C_j associated with F_j. When F_j occurs, C_j loses a fraction ε of E: α’ = (1 – ε)α. When both ϕ_i and F_j occur, an amount b diffuses from B_i to C_j: α’ = (1 – ε)α + b. In the limit, the mean amount of substance approaches b · p_{i,j}, creating an automatic biological estimator of conditional probability.
12.5 A_file Algorithms for the ISODATA Procedure
The ISODATA procedure proposed by G. Ball and D. Hall delineates clusters in an inhomogeneous distribution of vectors. Starting with arbitrary cluster points A_i^[1], each data point is assigned to its nearest A_i^[1] region R_i^[1]. Next, each A_i is replaced by A_i^[2], the mean (center of gravity) of all points in R_i^[1], and regions are recomputed. This process iterates until cluster points stabilize.
12.5.1 ISODATA Convergence Theorem
Let S^[t] = ∑_{Φ} ||Φ – A^[t](Φ)||^2 be the total squared-distance score. Theorem: S^[1] > S^[2] > … > S^[t] until A_i^[n] = A_i^[n+1] for all i.
Proof: Replacing A_i by the mean of R_i strictly minimizes squared distance sum. Reassigning points to their nearest A_i further reduces or preserves distance. For a finite set of points, the sequence of partitions is finite, guaranteeing termination in a finite number of steps.
12.6 Time vs. Memory for Exact Matching
Given a data set of 2^a binary words of length b digits, we want to evaluate the trade-off between memory size M and the average number of memory bit-references required by A_find to answer: “Is w in the data set?”
12.6.1 Case 1 (Enormous Memory): M ≥ 2^b. Table look-up using 1 bit per possible word requires only 1 memory reference.
12.6.2 Case 2 (Inadequate Memory): M < (b – a) 2^a. Impossible to store enough information to describe the set.
12.6.3 Case 3 (Binary Logarithmic Sort): M = b 2^a. Sorting words numerically allows binary search, requiring ~1/2 a · b bit references.
12.6.4 Case 4 (Exhaustive Search): M = (b – a) 2^a. Storing minimal compressed differences requires searching on average half of memory (~1/2 (b – a) 2^a references).
12.6.5 Case 5 (Hash Coding): M = 2b 2^a (a factor of 2 memory redundancy). Using pseudorandom address mapping R(w, j), A_find inspects on average only 4 + ε bit references! Redundancy of 2 yields dramatic speedup.
12.7 Time vs. Memory for Best Matching: An Open Problem
Consider Question 2: Given query word w, find the closest word w_hat in the data set under Hamming distance d(w, w_hat) = ∑ |x_i – x_hat_i|. While exact matching achieves dramatic speedups with minor redundancy (hash coding), best matching appears fundamentally different. We conjecture that for best matching, memory redundancy provides very little speedup, and finding the nearest neighbor in high-dimensional space generally requires inspecting large fractions of memory.
Why is Best Match so different from Exact Match? For exact match, no error is tolerated, converting an n-dimensional problem into 1 dimension via bit weighting ∑ 2^i x_i. For best match, errors in all dimensions are weighted equally, preserving the high-dimensional geometric complexity.
12.8 Incremental Computation
Algorithms with local, incremental properties compute memory state M as M = A_file(data set) by processing one sample at a time without requiring auxiliary scratchpad storage proportional to the data set size. While many statistical parameters can be estimated incrementally by trading time for storage, certain global features (such as computing exact medians in a single pass, or evaluating complex non-local properties) fundamentally require storage scale on the order of the full data set.