I thank Nolan McCarty, Howard Rosenthal, and Jerry Salancik for many helpful comments.

This paper shows a general non-parametric technique for maximizing the correct classification of binary choice or two-category data. Two general classes of data are analyzed. The first consists of binary choice matrices such as congressional roll calls or preferential rank ordering of stimuli gathered from individuals. For this class of data a general non-parametric unfolding procedure is developed. To unfold binary choice data two subproblems must be solved. First, given a set of chooser or legislator points a cutting plane through the space for the binary choice must be found such that it divides the legislators into two sets that reproduce the actual choices as closely as possible. Second, given a set of cutting planes for the binary choices a point for each chooser or legislator must be found which reproduces the actual choices as closely as possible. Solutions for these two problems are shown in this paper.

The second class of data analyzed consists of a two-category dependent variable and a set of independent variables. This class of data is a subset of the binary choice unfolding problem. The cutting plane procedure can be used to estimate a cutting plane through the space of the independent variables that maximizes the number of correct classifications. The normal vector to this cutting plane closely corresponds to the beta vector from a standard probit, logit, or linear probability analysis.

Categorical choice data occur frequently in the social and behavioral sciences. The purpose of this paper is to show a general non-parametric technique for maximizing the correct classification of binary choice or two-category data. I analyze two general classes of such data. The first class consists of binary choice matrices such as congressional roll calls or preferential rank ordering of stimuli gathered from individuals. For this class of data a general non-parametric unfolding procedure is developed. To unfold binary choice data two subproblems must be solved. First, given a set of chooser or legislator points, a cutting plane through the space for the binary choice must be found such that it divides the legislators into two sets so that the number of correct classifications of the legislators is maximized. Second, given a set of cutting planes for the binary choices, a point for each chooser or legislator must be found such that the number of correct classifications of the choices is maximized. Sections 3 and 4 below show solutions for these two problems.

The second class consists of data sets that would normally be analyzed with probit, logit, or linear probability models; that is, data sets with a two-category dependent variable and a set of independent variables. The cutting plane procedure developed in section 3 can be used to estimate a cutting plane through the space of the independent variables such that the number of correct classifications of the dependent variable is maximized. The counterpart to the beta vector from a probit, logit, or linear probability model is the normal vector of this cutting plane. In a Monte-Carlo analysis below I show that if the underlying error process is symmetric, the normal vector which maximizes classification and the beta vector from a probit analysis are virtually identical.

I make only two assumptions: 1) the choice space is Euclidean; and 2) the individuals making choices behave as if they utilize symmetric, single-peaked preferences.

The techniques I develop below are similar in spirit to those pioneered by Shepard (1962a,b) and Kruskal (1964a,b). They developed what became to be known as non-metric multidimensional scaling. Their initial focus was on similarities data. Their idea was to reproduce the rank ordering of the data as "closely" as possible. This became known as a non-metric approach in contrast to a metric approach such as factor analysis which treated the similarities as ratio scale data. The idea was to estimate a set of points in a Euclidean space such that the interpoint distances between the stimulus pairs were in the same rank order as the observed similarities.

Instead of placing points in a Euclidean space in such a way so as to reproduce the rank ordering of a set of data, I estimate cutting planes or cutting planes and chooser points in an Euclidean space such that the correct classification of the observed two-category data is maximized.

The paper proceeds as follows: section 2 defines the problem and explains the notation I use throughout the paper; section 3 develops the cutting plane procedure; section 4 shows how to estimate the legislator/chooser points; section 5 shows Monte-Carlo results for the roll call problem; section 6 shows empirical applications; and section 7 concludes.

I begin by defining the problem in terms of the first class of data – a binary choice matrix – because the second class of data – a set of independent variables and a two-category dependent variable – is a special case of the binary choice matrix problem.

Given a matrix of binary choice data, the problem consists of finding a set of legislator points and a set of cutting planes corresponding to each binary choice in an Euclidean space of s dimensions such that each cutting plane divides the legislators into two sets that reproduce the actual choices as closely as possible. In other words, the task is to estimate a set points for the legislators (subjects) and a set of cutting planes for the roll calls (stimuli) that maximize the correct classification of the observed choices.

Let i=1,...,p be the number of legislators, j=1,...,q be the number binary choices (hereafter referred to as roll calls), k=1,...,s be the number of dimensions, X be the p by s matrix of legislator coordinates, and let T be the p by q matrix of observed choices. The choices will simply be yea or nay which I will represent as "y" and "n" respectively. T can contain missing entries.

For data sets which consist of a set of independent variables and a two-category dependent variable, the notation above is simply redefined. Let X be the p by s matrix of independent variables, where p is the number of observations and s is the number of independent variables, and let t be the p length vector which is the two-category dependent variable. In the development of the cutting plane procedure below, I will use the notation defined for a matrix of binary choice data. I will return to the problem of a set of independent variables and a two-category dependent variable in section 3.c.

Technically, a plane is defined as z¢ n = v¢ n where z, n, and v are s by 1 vectors and the plane consists of all points z such that (z - v) is perpendicular to the normal vector, n, and v is some point in the plane. In simple algebra, an example of a plane in three dimensions is

3z₁ - 2z₂ + z₃ = 5

This plane is perpendicular to the normal vector -- n¢ = (3, -2, 1) -- and v is any point in the plane, for example (1, -1, 0), such that v¢ n = 5.

In this context, the problem is to solve for the normal vector, n. Let N be the q by s matrix of normal vectors for the q cutting planes. Given the number of dimensions, s, the classification problem consists of finding estimates of X and N, which I will denote as X* and N* respectively, which maximize the correct classifications.

Maximizing the correct classification of a binary choice matrix can be broken down into two subproblems – 1) given the legislator coordinates, find the optimal cutting plane; and 2) given the cutting planes, find the optimal legislator coordinates. Sections 3 and 4 show solutions for these two subproblems.

Given the p by s matrix, X, of legislator coordinates and the p by 1 vector of votes on the jth roll call, t, the problem is to find the plane that divides the legislators into two groups such that the number of correct classifications is maximized. Figure 1 shows an example in two dimensions.

Figure 1 illustrates the fact that the cutting plane problem is equivalent to finding a vector – in this case, n – such that when the legislator points are projected onto the vector a cutting point can be found that maximizes the correct classifications. By definition, all points in the cutting plane are projected onto this cutting point. The problem has two distinct parts which I will discuss in turn. First, given an estimate of the normal vector, I show how to find the optimal plane perpendicular to the normal vector and its associated correct classifications; and second, given an estimated cutting plane, I show how to change the orientation of the plane through the s-dimensional space in order to find a better estimate of the normal vector.

3. a. Calculating the Correct Classifications

Without loss of generality let the legislator coordinates lie within the s dimensional unit hypersphere and let the origin of the space be placed at the centroid of the legislator coordinates; that is, let

In addition, let n_j be the normal vector for the jth roll call that maximizes correct classifications. Without loss of generality n_j can be constrained to be of unit length; i. e., n_j¢ n_j = 1. The projections (see Figure 1B) are, therefore:

Xn_j = w (1)

Note that the elements in the p-length vector, w , range from -1 to +1. (To see this, let one of the legislator points be -n_j and another legislator point be +n_j.) The elements in w all lie on a line that passes through the origin of the s-dimensional unit hypersphere in the direction of the normal vector with exit points -n_j and +n_j respectively. Hereafter, I will refer to this line as the projection line.

Let n_j* be an estimate of n_j and let w* be the corresponding estimate of w. The correct classifications associated with n_j* can be calculated quite easily. Figure 2 illustrates the method.

___________________________________________________________

For ease of exposition, let the projected legislator coordinates from left to right be denoted in order as w₁ to w_p such that -1 £ w₁ £ w₂ £ w_{3 £} ... £ w_{p £} +1 and the "y"s and "n"s above the dimension line in the Figure indicate how the corresponding legislators voted on the jth roll call. There are p+1 possible regions that the cutting point could be in -- (-1, w₁), (w₁ , w₂), ... , (w_p , +1) -- and for each region there are exactly 2 possible perfect voting patterns for an overall total of 2(p+1) possible perfect voting patterns as shown in the Figure. However, region (w_p , +1) is redundant since it produces the same perfect patterns as the region (-1 , w₁) so it may be discarded leaving 2p unique perfect voting patterns to consider.

Since there are only 2p perfect patterns, it is a simple matter to compare each perfect pattern with the actual pattern of votes, t_j. This can be done very efficiently by first assuming that the cutting point is in the region (-1 , w₁) and calculating the corresponding number of correct classifications. Next assume that the cutting point is in the region (w₁ , w₂). Only one calculation has to be made to get the correct classifications for this cutting point since the only change is that the cutting point has been moved from the left of w₂ to the right of w₂. If there is no missing data, either the correct classification increases by 1 or decreases by 1 when the cutting point is moved from the left of w₂ to the right of w₂. Similar reasoning holds for the remaining points. For each possible cutting point the correct classification corresponding to the two possible perfect patterns can be calculated. The estimated cutting point is set equal to the midpoint of the region for which correct classification is a maximum. For the example shown in Figure 2, placing the cutting point at the position of either of the three asterisks would produce only two classification errors for a correct classification of p-2.

Note that this process is equivalent to moving the cutting plane through the unit hypersphere along the estimated normal vector, n_j^*.

Let c* denote the cutting point that maximizes correct classification on the projection line formed by the elements of Xn_j* = w* . The point c* is therefore:

z¢ n_j* = v¢ n_j* = c* (2)

Given n_j* and c*, the estimated cutting plane consists of all points v satisfying equation (2). In order to get a new estimate of n_j , the estimated cutting plane given by equation (2) must be rotated through the space in a direction that increases correct classification. I accomplish this by rotating the cutting plane towards the legislator points which are classification errors.

To do this, I create the cutting plane by projecting all the correctly classified legislator points onto the surface of the cutting plane while leaving the incorrectly classified legislators at their original positions. In two dimensions this produces a line through the space made up of correctly classified legislators around which is a scattering of points corresponding to the incorrectly classified legislators (see Figure 3)[¹]. Much in the spirit of the classic ordinary least squares regression problem, a new cutting plane can then be estimated by simply finding the plane that best fits this set of points using the principle of least squares.

To see how this is done, let x_i be the s by 1 vector denoting the ith legislator’s point in the space and let w_i be the corresponding point on the projection line from equation (1). Construct a p by s matrix, V, as follows: if legislator i is correctly classified, then his point is projected onto the cutting plane and that point becomes the ith row of V; if legislator i is incorrectly classified, then his point remains at its original position and that point becomes the ith row of V. That is:

In the correctly classified case, to see that v_i is on the plane defined in equation (2), note that

n_j*¢ v_i = n_j*¢ x_i + n_j*¢ n_j* (c* - w_i) = w_i + (c* - w_i) = c*

because n_j*¢ n_j* = 1 and (c* - w_i) is a scaler.

Without loss of generality, the centroid of V can be placed at the origin. That is, let m be the s length vector of the means of V, and let J_p be a p by 1 vector of ones. Define V* as

Panel A of Figure 3 shows a vote in two dimensions which would be perfectly classified by the indicated cutting line. Panel B shows the V* produced by using an initial estimate of n_j*¢ = (0 , 1) -- that is, an estimated normal vector perpendicular to the true normal vector. All the "y" and "n" tokens off the plane are classification errors. Clearly, if the plane were rotated counter-clockwise towards the errors a better fit would be obtained. This can be accomplished by fitting a line through the scatterplot of "y"s and "n"s in panel B.

This is accomplished by using a famous result due to Eckart and Young (1936). Eckart and Young addressed the following problem. Let A be a p by s matrix of rank s which, by definition, is a set of p points in an Euclidean space of s dimensions. Estimate the best r-dimensional hyperplane -- where r < s -- through this set of points. That is, find a p by s matrix B of rank r < s, such that

is minimized. Eckart and Young proved that B is found by performing a singular value decomposition of A , inserting zeroes in place of the s-r smallest singular values, and remultiplying. [²]

To show how this is accomplished with respect to V*, let the singular value decomposition of V* be

where U is a p by s orthogonal matrix consisting of the first s eigenvectors of the p by p matrix V*V*¢ , Q is an s by s orthogonal matrix consisting of the s eigenvectors of the s by s matrix V*¢ V*, and L is an s by s diagonal matrix containing the singular values in descending order on the diagonal (V*V*¢ and V*¢ V* have the same non-zero eigenvalues – the singular values are the square roots of these eigenvalues). Let I_s be the s by s identity matrix. By definition, U¢ U = Q ¢ Q = I_s.[³]

By the Eckart-Young result, the best fitting line through the scatterplot shown in panel B of Figure 3 is found by inserting a zero in place of the second singular value in L and remultiplying. That is, let L ^# be the s by s diagonal matrix identical to L except for the replacement of the sth singular value (by construction, the smallest singular value) by zero, then the estimated hyperplane is:

where V^# will be of rank s-1 by construction.

Let n_j^# be the normal vector of the hyperplane defined by V^# and let q _s be the sth singular vector (eigenvector) of Q . I will now prove that n_j^# = q _s .

By the definition of a plane:

where J_p is a p by 1 vector of ones and c^# is a constant. Recall from equation (4) that

, k=1,...,s

and therefore the p length eigenvectors of U in equation (5) must also sum to zero; that is;

, k=1,...,s

From which it follows that the columns of V^# must also sum to zero:

, k=1,...,s

Hence, by simply adding up all p elements of the vectors on either side of the equality in equation (7) it must be the case that c^# = 0. Therefore, equation (7) can be rewritten as

where 0_p is a p length vector of zeroes. Let L ^#-1 be an s by s diagonal matrix with diagonal entries that are the reciprocals of the non-zero diagonal entries of L ^# . Multiplying both sides of equation (8) by L ^#-1U¢

this reduces to

where 0_s is an s length vector of zeroes, and Q * is identical to Q except the sth column of Q * is all zeroes (hence, the sth row of Q *¢ is all zeroes). Now, n_j^# cannot be a vector of zeroes since, by definition, n_j^#¢ n_j^# = 1. Hence, n_j^# = q _s is a solution for equation (8).

In sum, calculating the optimal n_j consists of the following steps:

1. Obtain a starting estimate of n_j* using ordinary least squares.
2. Calculate the correct classifications associated with n_j* .
3. Construct V* using equations (3) and (4).
4. Perform singular value decomposition of V*, UL Q ¢ .
5. Use the sth singular vector of Q , q _s , as the new estimate of n_j .
6. Go to (2).

In a perfect case like that shown in Figure 3, this cutting plane procedure will almost always iterate into the true cutting plane. Panels D and E show the process after the 10^th and 35^th iterations through steps (2) - (5) above.

I say "almost always" because, with perfect data, the rate of convergence is a function of the number of errors. As the number of errors decreases, the mass of the correctly classified choices increases thereby producing very small changes in the newly estimated normal vectors. This can be seen by comparing panels C and D with panels D and E. Indeed, given the right sort of configuration, the convergence can become so slow that it literally gets "lost" in the precision of the computer. Consequently, I have experimented with a number of simple fixes – for example, local grid searches as well as weighting the error so as to speed convergence. However, the basic procedure is so robust that I will limit my Monte-Carlo reports below to it alone so that the reader will have a clear idea of how well it works "barefoot" without any enhancements.

Table 1 shows a Monte-Carlo study of the cutting plane procedure using perfect data for 100 legislators and 500 roll calls for 2 through 10 dimensions. Results for one dimension are not shown since correct classification will always be 100% if perfect data is used. The 100 legislators and 500 normal vectors were randomly drawn from a uniform distribution through the unit hypersphere. The cutting points along the projection line were also randomly drawn but in such a way so as to produce an average majority margin of about 62 percent (typical of congressional roll call data). [⁴] A maximum of 100 iterations through steps (2) - (5) above were allowed.

a Average margin across all 10 trials or 5000 total votes.
^b Average across all 10 trials.
^c Average across all 10 trials or 500,000 total choices.

The cutting plane procedure performs very well. The number of dimensions does not appear to play any role in the accuracy of the procedure. For example, for the ten trials in 10 dimensions, the 5000 total estimated n_j*’s correctly classified 499,868 of 500,000 choices (99.97 percent). As I noted above, this accuracy rate is a baseline; it can be further improved with local searches and other enhancements.

When error is present the cutting plane procedure converges very quickly. In this context I am using "error" in a very artificial sense because I have not stated any behavioral model of the legislators. It simply means that, given a legislator configuration and an observed pattern of yea’s and nay’s, find the cutting plane that maximizes correct classification. The pattern might be produced by a probabilistic model of legislator voting or it might be a lower space projection of perfect voting in a higher dimensional space. An example is shown in Figure 4 which uses the same configuration of legislator ideal points as Figure 3. The choices of 78 of the 435 legislators have been modified so that they are "errors" – "N’s" on the "Y" side of the true cutting line and "Y’s" on the "N" side of the true cutting line. The cutting plane procedure converges on the 30^th iteration as shown in Panel D. As shown by Panels B and C, in the error case the converged cutting plane may not be the one that maximizes classification – however, it will invariably be very close to the optimal cutting plane. This is easily dealt with by simply storing the iteration record and using the normal vector corresponding to the best classification. This works very well in practice.

Given a simple two category dependent variable and a set of fixed independent variables, the cutting plane procedure can be used to estimate a vector of coefficients for the independent variables that maximizes correct classification of the dependent variable. In this instance, with the independent variables scaled so as to lie within a unit hypersphere, the normal vector, n_j*, produced by the cutting plane procedure, plays the role of the coefficient vector, b , in a standard probit, logit, or linear probability analysis.

In order to study the relationship between the cutting plane procedure and a standard probit analysis, I performed a Monte-Carlo study in which I created artificial data that fit the model:

where X is a p by s matrix of randomly generated independent variables scaled so as to be within a unit hypersphere; [⁵] b is a randomly generated s length vector of coefficients with b ¢ b = 1; [⁶] e is a p length vector of error terms; and y^* is the unobserved latent dependent variable. The categorical dependent variable, y , was created by picking a cutpoint on y^* and defining all observations above the cutpoint as one category and all observations below the cutpoint as the second category. I then analyzed X and y with probit and the cutting plane procedure. A portion of the study is shown in Table 2.

Table 2 shows three sets of experiments using normal, uniform, and asymmetric error, respectively. All entries are the average of 10 trials. In the first portion of the Table the number of independent variables was set equal to either 5 or 10 (s=5 or s=10) with 100 observations (p=100). The randomly drawn b -- the normal vector – was used to create the true latent dimension and a cutpoint was selected so that the true margin was 50-50. Normal random error was then drawn and added to Xb to get the noisy latent dimension and the categories were adjusted vis a vis the true cutpoint. The column "True Margin" is the margin before the addition of the error. The next three columns of the Table report the Pearson correlations between: the true b and the vector of coefficients from the Probit analysis; the true b and the estimated normal vector, n_j* , from the cutting plane procedure; and the Probit coefficients and n_j* . Finally, the last two columns show the percent correct classifications of Probit and the cutting plane procedure, respectively. [⁷]

With normally distributed and uniformly distributed error the non-parametric cutting plane procedure recovers essentially the same set of coefficients as Probit. This seems sensible in that as long as the underlying error distribution is symmetric so that the frequency of error diminishes with distance from the cutting plane, then the cutting plane procedure should produce results very similar to those of a parametric procedure like Probit.

The last set of results shown in Table 2 are those for three asymmetric error distributions: chi-square with one degree of freedom; a bimodal distribution where the frequency of error peaks midway between the cutpoint and the ends of the dimension; and one in which the error is clustered near only one end of the dimension. Even though the two procedures are recovering similar vectors, when the error distribution is not normal and not symmetric, the cutting plane procedure comes closer to recovering the true vector of coefficients than does Probit.

Table 3 shows an empirical comparison of the cutting plane procedure and Probit analysis. The sample is 231 Republican members of the House of Representatives [⁸] and the dependent variable is whether or not they signed up as co-sponsors of a minimum wage increase. [⁹] The independent variables measure the liberalness of the representative (the NOMINATE scores; see Poole and Rosenthal, 1991, 1997, for details) and some characteristics of representative’s congressional district (percent rural, percent Black, and median family income). (The independent variables were put in standard deviation form to facilitate comparisons.) The standardized Probit coefficients and the cutting plane coefficients are very close – the simple Pearson correlation is .961. Substantively, the coefficients in Table 3 indicate that Republican moderates from poorer, urban districts support raising the minimum wage.

Probit Log Likelihood = -54.101
Percent Correctly Classified By Probit = 90.9 (210 of 231)
Percent Correctly Classified By Cutting Plane Procedure = 91.8 (212 of 231)
Correlation Between Cutting Plane Coefficients and Standardized
Probit Coefficients = .961
________________________________________________________________________

^a Unadjusted NOMINATE scores range from -1.0 to +1.0
^b Unadjusted data expressed as a percentage
^c Unadjusted data expressed in dollars
^d The sum of the squared coefficients equals 1
^e Based upon 100 trials

In order to obtain standard errors for the cutting plane procedure, I performed a simple bootstrap analysis. [¹⁰] The standard errors were then used to obtain the reported "t-values". Note that the pattern of significance for the non-parametric cutting plane coefficients is the same as that for the Probit coefficients. Monte-Carlo work with artificial data suggests that the cutting plane coefficients will have nearly identical patterns of significance (using bootstrapping) with those produced by a Probit analysis when the underlying error distribution is symmetric.

I conjecture that the cutting plane procedure is easily generalized to the case of ordered Probit. The only modification necessary is to change the way correct classifications are counted. For example, suppose there are four categories – y, n, a, b – and the order is y > n > a > b (or its mirror image). Given an estimate of the normal vector, n_j*, the problem is to find three parallel cutting planes that divide the space into four regions so as to maximize the correct classifications. This can be solved using a modification of the classification procedure shown in Section 3.a.

To illustrate, consider one of the intermediate categories, "n". Given the projection line, equation (1), the problem now is to find two cutpoints rather than one. Lump the other three categories – y, a, b – into a non-"n" category. Denote the non-"n" category as "c". Using the same logic discussed is Section 3.a, search all the patterns of the form:

cnnnn…nnccccccccc
ccnnn…nnccccccccc
cccnn…nnccccccccc
etc.
ccccc…cccccnnnccc
etc.

Given the restriction that there must be at least one "c" to the left of the left-most "n" and at least two "c"s to the right of the right-most "n", and at least one "n", then there are exactly possible pairs of cutpoints which define possible patterns of "c"s and "n"s. Given these two cutpoints, the simple one point procedure can be used to find the last cutpoint.

Because the three cutting planes are parallel and have the same normal vector, the correctly classified observations can be projected onto a "common" plane which is placed through the origin of the space rather than through the cutpoint, c^*, as shown in equation (3). The errors are then translated so that they are the same distance and orientation from the "common" plane as the plane for which they are an error.

In a multiple choice context where there is no natural ordering of the choices, the parametric approach consists of estimating separate probabilities for each of the choices utilizing a common set of independent variables. For example, in the 1980 U. S. presidential election there were four choices – Reagan, Carter, Anderson, and not-voting. The probability that an eligible voter voted for Reagan is the product of the conditional probability that, given the person decides to vote, she votes for Reagan times the probability that she votes. Using a logit model, three vectors of coefficients will be estimated – one for the vote/not-vote decision, and two for the candidate choices (only two are needed since probabilities add to one). [¹¹]

Because the probability of making a choice rises in the direction of the coefficient vector, in terms of the cutting plane procedure, this is equivalent to estimating three normal vectors – one for the binary choice vote/not-vote; and two for the voters, one for the binary choice Reagan/not-Reagan; and one for the binary choice Anderson/not-Anderson (using Carter as the omitted choice). Geometrically this approach is possible because, from some interior point outward along a vector from the origin, there should be only one choice. However, the cutting plane procedure is linear – that is, it uses straight cuts to divide up the hypersphere when curved boundaries between the choice regions may be more appropriate because the hypersphere must be divided into mutually exclusive regions. Consequently, the cutting plane procedure should not do as well in this context as it should with ordered Probit. Nevertheless, it should provide a very useful benchmark for comparison with parametric methods.

Given the q by s matrix, N, of normal vectors and the q by 1 vector of votes of the ith legislator, t_i, the problem is to find the legislator point, x_i, which minimizes the classification error. Figure 5 shows an example in two dimensions.

Figure 5 shows five cutting lines indicated by the numbering at the rim of the circle. The "Y" and "N" on either side of each cutting line indicates how a legislator on that side of the cutting line should vote – "yea" or "nay" respectively. The five cutting lines divide up the space into 13 regions and each of these 13 regions can be characterized by a unique vector of votes. The voting patterns for several regions are shown in the figure. For example, the region near the center of the circle containing the point "A" corresponds to a voting pattern of yyynn.

Given a legislator’s pattern of votes, in this case nnnyn (technically, t_i¢ = [nnnyn]), the problem is to find the region in Figure 5 that maximizes the correct classification. In this example the point "C" is located in the region corresponding to perfect classification. Suppose the initial estimate of the legislator’s coordinates is at the origin, point "A" in the Figure. This initial estimate is very poor as it only correctly classifies one of the five votes. The problem is to move the point representing the legislator in a direction that increases the number of correct classifications.

Below I show a method for finding the maximum classification point along any arbitrary line passing through the space. This method is used to move the legislator point through the space in a city-block fashion by searching along a line parallel to the first dimension and then solving for the point along this line which maximizes classification. Then the legislator point is moved along a line through this new point but parallel to the second dimension. This is done for each dimension in turn and can be repeated as many times as desired. This always converges to a point for which the coordinates are at a local maximum in terms of classification. That is, the point cannot be moved parallel to any dimension and have the correct classifications increase.

Let x_i^(h) be the initial estimate for legislator i where "h" is the iteration number (1, 2, 3, etc.) and let x_i^(a) be a second point. The problem is to find a new estimate, x_i^(h+1), on the line passing through x_i^(h) and x_i^(a) which increases correct classification. Using equation (1), the projection of x_i^(h) onto the jth normal vector is:

Similarly, the projection of the second point onto the jth normal vector is w_ij^(a). These projections correspond to a correct classification on roll call j depending upon which side of the cutpoint, c_j, they fall. There are six possible orderings of w_ij^(h), w_ij^(a), and c_j. For each ordering there are two possible classification outcomes for a total of 12 cases. Table 4 shows each case.

For example, in case 1 both x_i^(h) and x_i^(a) project to the right of c_j and are on the correct side of the cutting plane for the jth roll call and are therefore correctly classified. Case 2 is the same geometrically only now x_i^(h) and x_i^(a) are on the wrong side of the cutting plane and are therefore projected as classification errors. Cases 1 to 8 represent no change in classification from moving the legislator point from x_i^(h) to x_i^(a). For x_i^(a) to be an improvement over x_i^(h) , the number of cases 10 and 12 must be greater than the number of cases 9 and 11.

Consider the effect of moving x_i^(a) further from x_i^(h) . This has no effect on cases 1, 2, and 7 - 12. Only those cases where x_i^(a) is between x_i^(h) and c_j – cases 3, 4, 5, and 6 – are affected. Depending upon how far x_i^(a) is moved away from x_i^(h) , case 3 could change to case 11 increasing the error by one, case 5 could change to case 9 also increasing the error by one, case 4 could change to case 12 decreasing the error by one, and case 6 could change to case 10 also decreasing the error by one. A similar analysis of the effect of moving x_i^(a) towards x_i^(h) can also be done.

More generally, consider the line equation:

which, when projected onto the jth normal vector, becomes:

For a single roll call, it is easy to solve for a ; these are shown in Table 4 for all 12 cases. For example, for case 2, a must be chosen so that the projection of x_i^(h+1) , w_ij^(h+1) , is in the region (-1, c_j ).

Given x_i^(h) and x_i^(a) , Table 4 can be used to find the limits of a for each roll call. Let the upper and lower limits for the jth roll call be U_ij and L_ij respectively. The correct classification associated with x_i^(h) can be obtained by setting a =0 and counting the number of roll calls for which 0 Î (L_ij , U_ij ). Similarly, the correct classification associated with x_i^(a) is obtained by setting a =1 and counting the number of roll calls for which 1 Î (L_ij , U_ij). In general, define

and the correct classification is simply

The a that maximizes d (a ) , the number of correct classifications, can be calculated in a simple manner. First, compute the L_ij and U_ij for each roll call. Second, rank order the L_ij and U_ij and use the classification algorithm described in section 3.a above to calculate the optimal a . Here the L_ij play the role of "y" and the U_ij play the role of "n". For example, if there exists an a that results in perfect classification, the ordering of L’s and U’s will look like (dropping the i subscript to reduce clutter and numbering left to right for convenience):

that is, all the L_j will be less than all the U_j. In this example, perfect classification, d (a ) = q , results from a Î (L_q , U₁ ). Table 5 shows a numerical example using the configuration of 5 cutting lines shown in Figure 5.

The starting estimate (h=1) x_i⁽¹⁾ , is placed at the origin – point "A" in Figure 5 – and the second point, x_i^(a) , is placed just to the right of x_i⁽¹⁾ . The upper and lower limits (computed from Table 4) along with their rank order are shown in the Table. The rank ordering is almost a perfect pattern in that 4 of the lower limits are below the 5 upper limits; only L₄ is wrongly placed producing one classification error. Consequently, the point resulting from using a Î (L₂ , U₃ ) , x_i⁽²⁾ , point "B" in Figure 5, only has one classification error with 4 correct classifications. (In practice, a is set equal to the midpoint; in this case,(L₂ + U₃ )/2 .) Note that in Figure 5 point "B" is on the wrong side of the cutting line for roll call 4 in the region associated with the pattern nnnnn.

For the second iteration, h=2, the starting estimate is x_i⁽²⁾ and the second point, x_i^(a), is placed just below x_i⁽²⁾ so that the resulting line is parallel to the second dimension. The upper and lower limits for the second iteration along with their rank order are shown in the Table. The rank ordering is now a perfect pattern with all 5 lower limits below the 5 upper limits so that there are no classification errors. The point resulting from using a Î (L₃ , U₄ ) , x_i⁽³⁾ , point "C" in Figure 5, has 5 correct classifications and no classification error.

The search for the optimal x_i is conducted in a city-block manner. In the first iteration the search is along a line through the origin with all but the first dimension coordinates in x_i⁽¹⁾ and x_i^(a) set to zero. In the second iteration, the first dimension coordinates are all set equal to the value corresponding to the optimal first dimension value and the 3^rd, 4^th, …, s^th dimensional coordinates in x_i⁽²⁾ and x_i^(a) are all set equal to zero. The search is along the corresponding line through x_i⁽²⁾ and x_i^(a) which is orthogonal to the first dimension. In the third iteration, the first and second dimension coordinates are set equal to the optimal values from the first and second iterations respectively, and the 4^th, 5^th, …, s^th dimensional coordinates in x_i⁽³⁾ and x_i^(a) are all set equal to zero. The search is along the corresponding line through x_i⁽³⁾ and x_i^(a) which is orthogonal to the second dimension. This process continues in the same fashion through the s^th dimension. Since the search for the optimal x_i is being done city-block-wise, dimensions 1 to s can now be searched again.

In sum, calculating the optimal x_i consists of the following steps:

1. Obtain a realistic starting estimate, x_i⁽¹⁾ (or set x_i⁽¹⁾ equal to the origin,

that is, x_i⁽¹⁾ = 0 ).

2. Set x_i^(a)¢ = (0.01, x_i2⁽¹⁾ , x_i3⁽¹⁾ , x_i4⁽¹⁾ , x_i5⁽¹⁾ , … , x_is⁽¹⁾ ) , find optimal a and x_i⁽²⁾ = x_i⁽¹⁾ + a (x_i^(a) - x_i⁽¹⁾ ) .
3. Set x_i^(a)¢ = (x_i1⁽²⁾ , 0.01, x_i3⁽¹⁾ , x_i4⁽¹⁾ , x_i5⁽¹⁾ , … , x_is⁽¹⁾ ) , find optimal a and x_i⁽³⁾ = x_i⁽²⁾ + a (x_i^(a) - x_i⁽²⁾ ).
4. Set x_i^(a)¢ = (x_i1⁽²⁾ , x_i2⁽³⁾ , 0.01, x_i4⁽¹⁾ , x_i5⁽¹⁾ , … , x_is⁽¹⁾ ) , find optimal a and x_i⁽⁴⁾ = x_i⁽³⁾ + a (x_i^(a) - x_i⁽³⁾ ).
5. Set x_i^(a)¢ = (x_i1⁽²⁾ , x_i2⁽³⁾ , x_i3⁽⁴⁾ , 0.01, x_i5⁽¹⁾ , … , x_is⁽¹⁾ ) , find optimal a and x_i⁽⁵⁾ = x_i⁽⁴⁾ + a (x_i^(a) - x_i⁽⁴⁾ ).

Note that classification error can never increase from one step to the next. This is true because setting a = 0 preserves the current value of classification. This process converges very quickly (usually less than 10 iterations through steps 2 to s+1 above) to a vector of coordinates which is a local maximum in terms of classification. That is, it converges to a point such that a = 0 for all s dimensions.

In practice, the starting estimate, x_i⁽¹⁾ , and the second point, x_i^(a) , could be placed anywhere within the s dimensional unit hypersphere. In practical applications the starting estimate will not be at the origin; rather, realistic starting estimates for the x_i⁽¹⁾‘s will be generated by a least squares procedure such as eigenvector/eigenvector decomposition or OLS (see Section 5 below). If the line through x_i^(h) and x_i^(a) is parallel to a cutting line then the corresponding difference between w_ij^(a) and w_ij^(h) , w_ij^(a) - w_ij^(h) , which is used in Table 4 to find a _j, may be equal to zero. This presents no problem since if the line through x_i^(h) and x_i^(a) is parallel to a cutting line then the classification on that roll call is the same no matter where on the line x_i^(h+1) is located. Consequently, the roll call is not used to locate x_i^(h+1) . In addition, if the line through w_ij^(a) and w_ij^(h) goes through the hypersphere so that it never intersects a cutting plane this can result in a value of a _j that produces a point that lies outside the unit hypersphere. This is easily handled by computing the upper and lower feasible limits of x_i^(h+1) – that is, the values corresponding to the two exit points of the line from the unit hypersphere – and discarding all the corresponding L_ij and U_ij . This requires some bookkeeping but it has no effect on the search process. Finally, the search process does not have to be done by moving orthogonally (i.e., city-block-wise) through the hypersphere. However, I found it to be the most efficient way to proceed.

To guard against local maxima, I utilize multiple starting points for the x_i⁽¹⁾‘s. If different solutions are found, I then search along the lines joining the unique local maxima for the best solution. After considerable experimentation, I found that 3 starting points work very well in practice. One starting point is generated from a least squares procedure and the other two are randomly generated.

Table 6 shows a Monte-Carlo study of the legislator procedure using perfect data – the true cutting planes are known -- for 100 legislators and 500 roll calls in 2 through 10 dimensions. In order to make the test of the legislator procedure reasonably stringent, I use only "unreasonable" starting points – namely, the origin and two randomly generated points are used for the three starting points. Results for one dimension are not shown since classification will always be 100% if perfect data is used. The 100 legislators and 500 normal vectors were randomly drawn from a uniform distribution through the unit hypersphere. The cutting points along the projection line were also randomly drawn but in such a way so as to produce an average majority margin of about 62 percent (typical of congressional roll call data). [¹²]

^aAverage across all 10 trials.
^b Average across all 10 trials or 500,000 total choices.
^c The Pearson Correlation is computed between the 4950 unique legislator pair-wise
distances (100x99/2). The number in the Table is the average across all 10 trials.

The legislator procedure works very well – especially at 7 dimensions and below. There is some deterioration in accuracy at 10 dimensions but it still only makes an average of 46 misclassifications out of 50,000 total choices. For 5 dimensions and below it is practically perfect. Table 6 also shows the Pearson correlation between the true configuration of legislators and the reproduced configuration. These correlations are very high. Even though the legislator procedure is non-parametric, with 500 roll call cutting planes, the unit hypersphere is chopped up into enough regions that, in effect, metric (i.e., ratio scale) information is being extracted from the roll call matrix.

To restate the problem, given a p by q matrix of binary choice data, T, the classification problem consists of finding a set of legislator points in an Euclidean space of s dimensions – the p by s matrix X -- and a set of cutting planes -- the q by s matrix, N, of normal vectors -- such that the predicted choices match the actual choices as closely as possible. To unfold the choice matrix, T, into the legislator coordinates and roll call cutting planes, requires a solution for two subproblems: given X, find the optimal N; and given N, find the optimal X. Sections 3 and 4 show solutions for these two subproblems. I now link them together to unfold binary choice matrices. In this section I show the algorithm and Monte-Carlo tests, and in Section 6 I show empirical examples of the algorithm.

The non-parametric unfolding algorithm consists of three phases:

1. Generate starting values for X, X*, from an eigenvalue/eigenvector decomposition of the legislator by legislator agreement score matrix.
2. Given X*, find the optimal estimate of N, N*.
3. Given N*, find the optimal X*.
4. Go to (2).

Starting values for X are easily generated from an agreement score matrix. The agreement score for a pair of legislators is simply the ratio of the number of roll calls on which they voted for the same alternative (Yea and Yea, or Nay and Nay), divided by the total number of roll calls on which they both voted. This score – which ranges from 0 to 1 -- can be treated as an inverse distance – the higher the agreement score the smaller the distance between the pair of legislators. By subtracting the agreement score from 1.0 and squaring the result, the transformed agreement scores can be treated as squared distances. Double centering this matrix of squared distances – that is, from each element of the matrix subtract the row mean, subtract the column mean, and add the matrix mean – produces a cross product matrix which can be decomposed to yield an estimate of the legislator coordinates, X* (Young and Householder, 1938; Ross and Cliff, 1964).

Table 7 shows a Monte-Carlo study of the non-parametric unfolding algorithm using perfect data for 100 legislators and 500 roll calls in 1 through 10 dimensions. Only roll calls with margins of 97-3 to 50-50 were used because unanimous and near-unanimous roll calls trivially inflate the number of correct classifications. [¹³]

^a Average margin across all 10 trials or 5000 total votes.
^b Average across all 10 trials.
^c Average across all 10 trials or 500,000 total choices.
^d For s=1, the Spearman Rank Correlation is computed between the 100 true and
reproduced legislator ranks. The number in the Table is the average across all 10
trials.
^e For s > 1 the Pearson Correlation is computed between the 4950 unique legislator
pair-wise distances (100x99/2). The number in the Table is the average across all
10 trials.

The algorithm works well regardless of the number of dimensions. The worst result is for two dimensions where, on average, about 28 of 50,000 choices were misclassified. The accuracy of the recovery of the true configuration of legislators declines after 3 dimensions. This is to be expected given that the number of roll call cutting planes is fixed. Simply put, as the number of dimensions is increased, ceteris paribus, there is somewhat more "wiggle room" for the legislator points. However, this statistic – the correlation between the true and reproduced distances between pairs of legislators -- over-states the decline in accuracy because, if a handful of points are recovered some distance from their true location, their distances to the remaining points will deflate the correlation disproportionately. Figure 6 illustrates this point.

The top panel of Figure 6 shows the first 35 true legislator points of one of the two-dimensional trials from Table 7 and the bottom panel shows their recovered locations. [¹⁵]

Given the history of other multidimensional scaling techniques, most empirical applications of the non-parametric unfolding technique I show here will be to data matrices with missing entries and the estimated configurations will be in three or fewer dimensions. [¹⁶] Missing data presents no problem for the algorithm. In the cutting plane procedure it simply means that the total number of legislators may vary from vote to vote. In the legislator procedure it simply means that the number of cutting lines may vary from legislator to legislator. Handling missing data requires a little bookkeeping but it has no effect on the algorithm.

Table 8 shows a set of experiments with binary choice data with and without error at various levels of missing data. Configurations of 100 legislators and 500 roll calls in 2 and 3 dimensions were randomly generated in the same fashion as those used in the Monte-Carlo experiments shown in Table 7. Error was introduced into the choices by making them probabilistic where the probability of making a correct choice increases with distance from the cutting plane. [¹⁷] An error level of about 22 percent was chosen because that is the approximate level of error in U.S. congressional roll call data. Entries were randomly removed and the remaining entries were then analyzed by the algorithm in one through five dimensions. [¹⁸] The upper part of Table 8 shows two-dimensional experiments at four different levels of missing data with and without error, and the lower part shows three-dimensional experiments. Each randomly produced matrix was analyzed at each level of missing data so that the same 10 matrices for two or three dimensions (with varying levels of missing entries) are being averaged in each row of the upper or lower parts of the Table.

The accuracy of the recovery of the legislator configuration is quite good and only begins to fall off at 70 percent missing entries. Consistent with the discussion of Figure 6, the overall Pearson correlation between the 4,950 pairwise true and reproduced distances deteriorates more rapidly than the correlations between the true and reproduced legislator locations on each dimension.

Figure 7 shows the average percent correct classifications from Table 8. The elbows are quite clear at the true dimensionality. With perfect data the procedure unambiguously finds the true dimensionality. With error, there is a tendency for the correct classification to increase with the percentage of missing data. This makes sense because, with respect to locating a legislator point, with more missing data there are fewer roll call cutting planes and hence the legislator position is not as constrained as it is with complete data. This increase in "wiggle room" will increase the correct classification and decrease the correlations of the true and reproduced legislator configurations. In any event, the results shown in Table 8 and Figure 7 suggest that the algorithm will perform well with real world data at realistic levels of missing entries.

6. Empirical Examples of Non-Parametric Unfolding of Binary Choice Matrices

In this section I show two empirical examples of the non-parametric unfolding procedure. The first is to U.S. Senate roll call data and the second is to feeling thermometer ratings of political figures gathered from respondents in the NES 1968 presidential election study. Both sets of data have been extensively analyzed by numerous researchers utilizing a variety of methodologies.

Feeling thermometer data is technically not binary choice – however, it can be interpreted as rank order data and that can be converted to binary choice. A feeling thermometer measures how warm or cold a person feels towards the stimulus and the measure ranges from 0 – very cold and unfavorable opinion – to 100 – very warm and favorable opinion with 50 being a neutral point. In 1968 respondents were asked to give feeling thermometer ratings to 12 political figures: George Wallace, Hubert Humphrey, Richard Nixon, Eugene McCarthy, Ronald Reagan, Nelson Rockefeller, Lyndon Johnson, George Romney, Robert Kennedy, Edmund Muskie, Spiro Agnew, and Curtis LeMay. [¹⁹]

Suppose a respondent gave ratings of 30, 80, and 55 to Wallace (W), Humphrey (H), and Nixon (N) respectively. With respect to these three candidates, the rank order is H > N > W. Now suppose a second respondent gave ratings of 45, 65, and 95, respectively, for a rank order of N > H > W. These rank orders can be converted to binary choice data by treating each pair of candidates as a roll call vote. For example, consider the pair of Wallace and Humphrey. If a respondent rates Wallace higher than Humphrey make that Yea, and if Humphrey is rated higher than Wallace, make that Nay. Doing this consistently across respondents creates a roll call vote where the outcomes are Wallace and Humphrey, respectively.

With the actual 1968 data, I used the order of the 12 political figures listed above (which is their actual order in the NES data set) to create the roll calls. That is, given a pair of politicians, the one earlier in the NES ordering was treated as a Yea and the later one a Nay. So if the pair was Ronald Reagan and Curtis LeMay, then if a respondent rated Reagan higher than LeMay that is a Yea vote. If a respondent gave a pair of politicians the same rating, for example, 55 and 55, then I treated it as missing data (that is, as if the respondent abstained on the roll call).

6.a. U.S. Senate Roll Call Matrices

My first application is to Senate voting after World War II. I focus on this period because it has been extensively analyzed by Poole and Rosenthal (1997) which will facilitate the interpretation of the results. I compare the two-dimensional senator coordinates from the non-parametric unfoldings with those produced by KYST, a non-metric multidimensional scaling procedure developed by Kruskal, Young, and Seery (1973), and NOMINATE, a maximum likelihood procedure developed by Poole and Rosenthal (1991, 1997).

Table 9 reports the classification results for Senates 80 to 104 (first session) in one and two dimensions for the non-parametric procedure. These percentages are about 3 to 5 percentage points better than NOMINATE in both one and two dimensions (Poole and Rosenthal, 1997, chapter 3). This is not surprising given that the NOMINATE procedure maximizes a likelihood function – that is, it estimates legislator and roll call outcome coordinates which maximize the probabilities of the observed choices. It does not attempt to maximize correct classifications.

^a Number of Senators may exceed two times the number of States because of within Congress replacements.
^b Number of roll calls with at least 2.5% voting, paired, or announced, on losing side.
^c Total choices may not equal number of Senators times number of roll calls because of non-voting due to absences, etc..
^d Classifications from non-parametric unfolding algorithm.
^e Pearson correlation between Senator coordinates from KYST and Senator coordinates from non-parametric unfolding. Non-parametric unfolding configuration rotated to best match KYST configuration.
^f Pearson correlation between Senator coordinates from W-NOMINATE and Senator coordinates from non-parametric unfolding. Non-parametric unfolding configuration rotated to best match W-NOMINATE configuration.

Table 9 also shows the Pearson correlations between the estimated dimensions of the non-parametric procedure and those produced by KYST and NOMINATE, respectively, in two dimensions. [²⁰] These correlations are, for the most part, very high – most of the first dimension correlations are above .95 and the second dimension correlations are mostly above .9. Because the non-parametric unfolding produces configurations very similar to those of both KYST and NOMINATE, these results strongly support the substantive interpretations of the legislator configurations discussed in Poole and Rosenthal (1997).

Table 10 shows the rank order from most liberal to most conservative for the 104^th Senate using roll call data through December 1995. Campbell of Colorado switched from Democrat to Republican in April of 1995 so he appears twice (ranks 47 and 53). If two or more senators tied in the ranking, the average of the associated ranks was used. For example, 72 senators were more liberal and 26 more conservative than the threesome Shelby (R-AL), Abraham (R-MI), and Frist (R-TN), who were tied. Consequently they all were assigned the average rank of 74.

The polarization of American politics is evident from an inspection of the table. There is no overlap of the two parties. [²¹] Campbell’s voting record as a Democrat made him the most conservative Democrat in the Senate. His conversion only moved him from 47^th to 53^rd rank – from the right edge of the Democratic party to the midst of the moderates of the Republican party.

Figure 8 shows the two dimensional configuration of senators for the 85^th Senate along with a histogram of the roll call cutting line angles. The two major parties are clearly separated with the Democratic party being split into its Northern and Southern wings. The 85^th Senate occurred during the height of the three-party system which lasted from the late 1930s to the late 1970s (Poole and Rosenthal, 1991, 1997; McCarty, Poole, and Rosenthal, 1996). The approximate angle of a party-line vote and the approximate angle of a conservative coalition vote (Northern Democrats versus a coalition of Southern Democrats and Republicans) are indicated in the histogram of the cutting line angles. The second dimension picked up the split in the Democratic party over race-related issues.

6.b. NES 1968 Feeling Thermometer Ratings of Political Figures

The thermometer ratings were converted to binary choices as explained earlier. If a respondent gave a thermometer rating to all 12 politicians, then the respondent was treated as casting 66 (12x11/2) roll call votes. In order to be included in the analysis, the respondent had to vote on at least 25 out of the 66 total possible pairings. The first 450 respondents in the survey were analyzed of which 418 rated enough politicians to be included in the analysis. [²²]

The results were quite good. The correct classifications were 84.6 percent in one dimension and 88.9 percent in two dimensions (average margin, 0.699; total choices, 21,839). Figure 9 shows several plots of the 418 respondents coded as to how they reported they had voted (or not voted) in the 1968 presidential election.

Panel A of Figure 9 shows all 418 respondents, panel B just the non-voters, and panels C, D, and E show the Humphrey, Nixon, and Wallace voters, respectively, along with the cutting lines between the relevant presidential candidate pairs. The distribution of the voters and non-voters is very similar to that found by other scaling techniques (Wang et al. [1975]; Rabinowitz [1976]; Cahoon et al. [1978]; Poole and Rosenthal [1984]). [²³] Specific locations for the political figures cannot be estimated with this technique. However, ceteris paribus, the cutting lines do create regions where the politicians must lie. For example, there are no cutting lines for Wallace that are above the two shown in panel E. The cutting lines for Wallace versus Johnson and Wallace versus Kennedy are almost exactly where the Wallace versus Humphrey line is in the Figure. Hence, Wallace must be located in the pie slice defined by the Wallace versus Nixon and Wallace versus Humphrey cutting lines.

Wallace was such a divisive figure in 1968 that the cutting lines for Wallace versus the other 11 political figures all classify at 95 percent or higher. Consequently, the noise level is so low that the region of the space that Wallace must lie in can be inferred with some confidence. This is not as true for either Humphrey or Nixon. For example, when paired against Robert Kennedy, 78 respondents voted for Humphrey and 223 voted for Kennedy. The estimated cutting line produced 66 classification errors – little better than the marginals of the roll call. Consequently, the cutting line for Humphrey versus Kennedy yields little useful information. However, this is an exception, not the rule. The overall correct classification in two dimensions was 88.9 percent and most of the cutting lines for Nixon and Humphrey are well above that figure. Although I will not pursue the topic here, it should be possible to infer what regions the outcomes are in when faced with noisy cutting lines.

In this paper I have shown a general non-parametric technique for maximizing the correct classification of binary choice or two-category data. I estimate cutting planes or cutting planes and chooser points in an Euclidean space such that the correct classification of the observed two-category data is maximized. I make only two assumptions: 1) the choice space is Euclidean; and 2) the individuals making choices behave as if they utilize symmetric, single-peaked preferences. I strongly suspect that the first assumption can be relaxed to a general Minkowski metric. That is a topic for future research. However, the assumption of symmetric preferences cannot be relaxed.

In order to perform a non-parametric unfolding of a binary choice matrix, two subproblems must be solved. First, given the chooser coordinates, for each binary choice find the cutting plane that maximizes correct classification; and second, given the cutting planes, for each chooser find the point that maximizes correct classification. Solutions for these two subproblems were shown in sections 3 and 4.

Although I do not have formal proofs that either technique converges to the classification maximum, Monte-Carlo tests show that both in fact work very well in practice. In the presence of error, the cutting plane procedure does not necessarily converge to a classification maximum. However, because of the way that the cutting plane procedure is operationalized, it almost certainly passes through, or very near to, the classification maximum and the maximum can be recovered from the iteration record. The legislator/chooser procedure is guaranteed to converge to a very strong local maximum. That is, a local maximum for which the point cannot be moved in any orthogonal direction and have the correct classifications increase. When the two procedures are used together in an alternating framework to analyze binary choice matrices, their performance is very good. The Monte-Carlo tests in section 5 and the empirical applications in section 6 are testimony to this fact.

For data sets which consist of a two-category dependent variable and a set of independent variables, the cutting plane procedure shown in section 3 recovers essentially the same coefficients as a probit analysis of the same data when the underlying error distribution is symmetric. The bootstrapped standard errors for the cutting plane coefficients almost always produce the same pattern of significance as that for the probit coefficients.

The cutting plane procedure can be easily generalized to multi-category ordered probit using a single normal vector. In the multiple choice context where there is no natural ordering of the choices so that there are multiple normal vectors, it should be possible to modify the cutting plane procedure to handle curved surfaces. This is a topic for future research. If successful, it would permit the non-parametric estimation of multiple choice and conditional choice models.

Cahoon, Lawrence S., Melvin J. Hinich, and Peter C. Ordeshook. 1978. "A Statistical
Multidimensional Scaling Method Based on the Spatial Theory of Voting." In
Graphical Representation of Multivariate Data, edited by P. C. Wang. New
York: Academic Press.

Eckart, Carl and Gale Young. 1936. "The Approximation of One Matrix by Another
of Lower Rank." Psychometrika, 1:211-218.

Green, Paul E., Frank J. Carmone Jr., and Scott M. Smith. 1989. Multidimensional
Scaling: Concepts and Applications. Boston: Allyn and Bacon.

Johnson, Richard M. 1963. "On a Theorem Stated by Eckart and Young."
Psychometrika, 28:259-263.

Keller, Joseph B. 1962. "Factorization of Matrices by Least-Squares." Biometrika,
49:239-242.

Kruskal, Joseph B. 1964a. "Multidimensional Scaling by Optimizing a Goodness of Fit
to a Nonmetric Hypothesis." Psychometrika, 29:1-27.

Kruskal, Joseph B. 1964b. "Nonmetric Multidimensional Scaling: A Numerical
Method." Psychometrika, 29:115-129.

Kruskal, Joseph B. and Myron Wish. 1978. Multidimensional Scaling. Beverly Hills,
Ca: Sage Publications.

Kruskal, Joseph B., Forrest W. Young, and J. B. Seery. 1973. "How to Use KYST: A
Very Flexible Program to Do Multidimensional Scaling and Unfolding."
Multidimensional Scaling Program Package of Bell Laboratories. Bell
Laboratories, Murray Hill, N.J.

McCarty, Nolan M., Keith T. Poole, and Howard Rosenthal. 1996. "The Realignment of
American Politics: From Goldwater to Gingrich." Manuscript, GSIA, Carnegie-
Mellon University, Pittsburgh, PA 15213.

Palfrey, Thomas R. and Keith T. Poole. 1987. "The Relationship Between Information,
Ideology, and Voting Behavior." American Journal of Political Science,
31:511-530.

Poole, Keith T. 1990. "Least Squares Metric, Unidimensional Scaling of Multivariate
Linear Models." Psychometrika, 55:123-149.

Poole, Keith T. and Howard Rosenthal. 1984. "U.S. Presidential Elections 1968-1980:
A Spatial Analysis." American Journal of Political Science, 28:282-312.

Poole, Keith T. and Howard Rosenthal. 1991. "Patterns of Congressional Voting."
American Journal of Political Science, 35:228-278.

Poole, Keith T. and Howard Rosenthal. 1997. Congress: A Political-Economic History
of Roll Call Voting. New York: Oxford University Press.

Rabinowitz, George. 1976. "A Procedure for Ordering Object Pairs Consistent With the
Multidimensional Unfolding Model." Psychometrika, 45:349-373.

Ross, John and Norman Cliff. 1964. "A Generalization of the Interpoint Distance
Model." Psychometrika, 29:167-176.

Schonemann, Peter H. 1966. "A Generalized Solution of the Orthogonal Procrustes
Problem." Psychometrika, 31:1-10.

Shepard, Roger N. 1962a. "The Analysis of Proximities: Multidimensional Scaling
With an Unknown Distance Function: I." Psychometrika, 27: 125-140.

Shepard, Roger N. 1962b. "The Analysis of Proximities: Multidimensional Scaling
With an Unknown Distance Function: II." Psychometrika, 27: 219-246.

Weisberg, Herbert F. and Jerrold G. Rusk. 1970. "Dimensions of Candidate
Evaluation." American Political Science Review, 64:1167-1185.

Wang, Ming-Mei, Peter H. Schonemann, and Jerrold G. Rusk. 1975. "A Conjugate
Gradient Algorithm for the Multidimensional Analysis of Preference Data."
Multivariate Behavioral Research, 10:45-80.

Young, Gale and A. S. Householder. 1938. "Discussion of a Set of Points in Terms of
Their Mutual Distances." Psychometrika, 3:19-22.