How The Optimal Classification Scaling (OC) Program Works In One Dimension:
The "Edith" Algorithm

7 May 2001

          YYYYYYYYYYYYYYYYYNNNNNNNNNNNNNNNNNN
                           *
          NNNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
             *
          YYYYYYYYNNNNNNNNNNNNNNNNNNNNNNNNNNN
                  *
                        Etc.

The asterisks indicate the "cutting point" for the roll call; that is, the midpoint of the Yea and Nay outcomes. A legislator located exactly on the midpoint would be indifferent between voting Yea or voting Nay.

Suppose roll call voting is in accord with this model. Then the scaling problem consists of taking a roll call matrix and "unscrambling" it – that is, finding a rank ordering of legislators and the correct "polarity" (Yea to the left of the cutpoint or Yea to the right of the cutpoint) for each roll call such that patterns like those above are produced for each roll call. This is what Edith is designed to do. If the data is perfect, then the solution is easy and the correct rank ordering is always found (see Proof that if Voting is Perfect in One Dimension, then the First Eigenvector Extracted from the Double-Centered Transformed Agreement Score Matrix has the Same Rank Ordering as the True Data).

However, when there is error in the data, things get a bit complicated. When there is error the aim is to find a rank ordering that maximizes the correct classification of the observed Yeas and Nays. This is easier said than done because if there are n legislators, then there are n!/2 possible rank orders to check to find the best one. For example, for 50 legislators this number is about 1.52 * 10⁶⁴ – a formidable number even with modern supercomputers. Consequently, Edith embodies a "sensible" search procedure (what the Operations Researchers call a "Heuristic") to find a solution. Namely, a good starting rank order of the legislators is generated using the technique discussed for the perfect voting problem ( Proof that if Voting is Perfect in One Dimension...) and the corresponding cutting points are found. These cutting points are used to get a new rank ordering of the legislators, and so on. At each step the correct classification increases until a rank order is found that produces cutting points that in return reproduce the rank order.

Finding the optimal rank ordering requires three steps:

• First, generate a starting estimate of the rank order of the legislators using the method cited above and translate this rank ordering into evenly spaced coordinates between -1.0 and +1.0;
  
  
• Second, given these coordinates, find the best cutting point for each roll call that maximizes correct classification;
  
  
• Third, given these cutting points, find a new coordinate for each legislator that maximizes correct classification.
  
  

To see how this process works, let the current ordering of the legislators from left to right be represented by coordinates from x₁ to x_p such that:

-1 £ x₁ £ x₂ £ x₃ £ ... £ x_p £ +1.

(-1, x₁), (x₁ , x₂), ... , (x_p , +1)

Perfect Voting Patterns

(-1 , x₁) produces nnnnnnnnn.....nn or yyyyyyyyy.....yy
(x₁ , x₂) produces ynnnnnnnn.....nn or nyyyyyyyy.....yy
(x₂ , x₃) produces yynnnnnnn.....nn or nnyyyyyyy.....yy
(x₃ , x₄) produces yyynnnnnn.....nn or nnnyyyyyy.....yy
(x₄ , x₅) produces yyyynnnnn.....nn or nnnnyyyyy.....yy
(x₅ , x₆) produces yyyyynnnn.....nn or nnnnnyyyy.....yy


etc.

(x_p-1 , x_p) produces yyyyyyyyy.....yn or nnnnnnnnn.....ny
(x_p , +1) produces yyyyyyyyy.....yy or nnnnnnnnn.....nn

Since there are only 2p perfect patterns, it is a simple matter to compare each perfect pattern with the actual pattern of votes. This can be done very efficiently by first assuming that the cutting point is in the region (-1 , x₁) and calculating the corresponding number of correct classifications. Next assume that the cutting point is in the region (x₁ , x₂). 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 x₂ to the right of x₂. 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 x₂ to the right of x₂. 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. This requires only 2p calculations to find the maximum classification cutting point. For the example shown above, placing the cutting point at the position of any of the three asterisks would produce only two classification errors for a correct classification of p-2.

Let the ordering of the q roll call midpoints estimated above be represented by coordinates from z₁ to z_q such that:

-1 £ z₁ £ z₂ £ z₃ £ ... £ z_q £ +1.

LLLLLLLLLCCCCCCCCCCCCCCCCCCCCCCCCC
or
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLCCCCCC

The Figure below shows that by taking the polarity of the roll calls into account the legislator problem is equivalent to the roll call cutting point problem. Hence, the algorithm described above can be used to find the optimal legislator location. There are only 2q possible perfect patterns and only 2q calculations are required to find the maximum classification location for each legislator.

Perfect Voting Patterns

(-1 , z₁) produces CCCCCCCCC.....CC or LLLLLLLLL.....LL
(z₁ , z₂) produces LCCCCCCCC.....CC or CLLLLLLLL.....LL
(z₂ , z₃) produces LLCCCCCCC.....CC or CCLLLLLLL.....LL
(z₃ , z₄) produces LLLCCCCCC.....CC or CCCLLLLLL.....LL
(z₄ , z₅) produces LLLLCCCCC.....CC or CCCCLLLLL.....LL
(z₅ , z₆) produces LLLLLCCCC.....CC or CCCCCLLLL.....LL


etc.

(z_q-1 , z_q) produces LLLLLLLLL.....LC or CCCCCCCCC.....CL
(z_q , +1) produces LLLLLLLLL.....LL or CCCCCCCCC.....CC

This simple algorithm converges very rapidly to a solution in which the rank ordering of the legislators and the rank ordering of the roll call midpoints reproduce each other. This is a very strong form of conditional global maximum. Technically, if there are multiple sets of parameters (for example, as in this case, parameters corresponding to rows of a matrix and parameters corresponding to columns of a matrix), and every set of parameters is at a global maximum conditioned on the other sets being held fixed, and these sets reproduce each other, then they are at a conditional global maximum. Note that the overall global maximum, by definition, is a conditional global maximum.

Conditional Global maxima are quite rare because of the nature of the constraints. Indeed, in the metric similarities problem, conditional global minima are very rare and their number declines as the number of parameters increases (Poole, 1990).

1. Suppose we start with the scrambled ordering of the legislators shown below. Using the method described above, we would place the Ace at the left end of the dimension because this results in only one classification error. Placing it between the Ace and Two of diamonds would produce four classifcation errors -- the Six, Seven, Four, and Nine of Diamonds. The same logic holds for the Two and Three of Spades. No interior point does better. When we get to the Four of Spades, however, placing it between the Three and Eight of Diamonds produces four classification errors (the Six, Seven, Nine and Five of Diamonds). The Four of Spades could be placed at the left end also producing four errors. In the case of a tie, I always put the cutpoint/legislator at the interior most position.
   
   

2. With respect to the ordering of the cutpoints represented by the Ace to the Nine of Spades, the new legislator ordering is shown below. The Ace of Diamonds is placed to the left of the Ace, Two, and Three of Spades, the Two and Three of Diamonds are placed at the same position as the Ace, Two, and Three of Spades because of the tied ranks. The Four of Diamonds is placed between the Ace, Two, Three stack, and the Four to Seven stack. The Five, Six, Seven of Diamonds are placed at the same position as the Four to Seven stack of Spades. The Eight of Diamonds is placed between the Four to Seven stack and the Eight and Nine of Spades. The Nine of Diamonds is placed at the same position as the Eight and Nine of Spades. Finally, the Ten of Diamonds is place to the right of the Eight and Nine of Spades.
   
   

3. With respect to the ordering of the legislators represented by the Ace to Ten of Diamonds, the new ordering of the cutpoints is shown below. The Ace of Spades is placed between the Ace of Diamonds and the Two and Three of Diamonds. The Two of Spades is placed at the same position and the tied Two and Three of Diamonds. The Three of Spaces is placed between the tied Two and Three of Diamonds and the Four of Diamonds. The Four of Spaces is placed between the Four of Diamonds the the tied Five to Seven stack. The Five and Six of Spaces are placed at the same position as the Five to Seven stack of Diamonds. The Seven of Spades is placed between the Five to Seven stack and the Eight of Diamonds. The Eight of Spades is placed between Eight and Nine of Diamonds. Finally, the Nine of Spades is placed between the Nine and Ten of Diamonds.
   
   

4. With respect to the ordering of the roll cutpoints represented by the Ace to Nine of Spades, the ordering of the legislators represented by the Ace to Ten of Diamonds is shown below. All are now in the correct position with perfect classification.
   
   

Site Links