I thought the writer Neal Stephenson did an excellent job of explaining the phenomenon of lock-in with regards to rocket technology in this article: http://www.slate.com/id/2283469/pagenum/all. It is an excellent reminder that the technologies we have are often the result of contingent (historical) factors rather than rational ones.
There's another great example here, by Alexis Madrigal. Apparently, the U.S. Navy ended up deciding that light-water reactors would be THE model for nuclear power. Another one about electric cars and electric refrigerators. And one more about, of all things, pants.
Here are two examples of lock-in that are near and dear to my heart -- that is, they drive me crazy:
1. Have you ever wondered why the U.S. math curriculum goes Algebra 1, Geometry, Algebra 2? It's a completely irrational system that no sane person would design. Algebra 2 classes start off with an extensive review of algebra since it's been 15 months since the students last saw algebra. In fact, the review can last nearly a quarter of the year. Perhaps the review period would last only a few weeks if the students were to go directly from Algebra 1 to Algebra 2. What's worse, many students aren't really developmentally ready for Algebra 1 when they take it; many need a more robust pre-algebra course. A more rational sequence would be Geometry/Pre-Algebra, Algebra 1, Algebra 2. Geometry is developmentally appropriate in 8th grade and serves as a perfect medium for pre-algebra concepts: that x stands for something that is unknown but fixed, and that one can use geometric properties to deduce x, makes sense in a geometric context. One can even get at the idea of x as a variable with similarity and ratios. And yet, year after year, school district after school district decides to keep the irrational sequence unchanged.
Why? At around the turn of the last century, when high schools were the new thing, students took Algebra and Geometry. Period. Geometry, with its logical proofs, was deemed material for seniors. As time went on, more classes were added on, always at the end. First, Algebra 2/Trigonometry was added. Then, Pre-Calculus was the senior math class. Now it's Calculus -- and thus, Algebra 1 got pushed down to 8th grade.
2. You know I'm going to talk about debate tab. I have never tabbed a tournament on notecards, but I know exactly how to do it because I've used the current generation of debate tab programs. The programs are electronic notecards. Don't get me wrong -- I'm very glad that we have the programs! They automate the mindless tasks and don't make careless mistakes like people do. My point is that when the tab programs came along, they were designed to do the existing tournament practices, only more efficiently. The debate community hasn't seriously thought about whether we can design better practices that can only be done by computers. In other words, we are locked-in to tournament procedures (brackets, speaker points, dropped high-low speaker points) that were designed to be (relatively) easy to do by hand, even though we have phenomenally powerful optimizing devices at our fingertips.
A high-low pairing algorithm literally ranks all the teams and then pairs them off two-by-two. Why not have a computer run 10,000 possible pairings and pick the best one?
I've written another post about lock-in.
Thursday, February 3, 2011
Wednesday, February 2, 2011
A method to create balanced groups
I like for my students to work together in groups. Unfortunately, they always choose to sit with their friends. So I have to assign their groups.
Let's say on the first day of class, I give them a 20 point quiz to see how much of last year's math they remember. I can also use that information to create balanced groups; I don't want to put all the weak students in one group and all the strong students in another. Rather, I would like each group to include weak students, strong students, and average students.
One way to look at this problem is that I want each group's average to be close to the class average. One could design an algorithm to create the groups this way. But I realized as I was designing it that one has to make ad hoc rules that throw out (a) groups composed of entirely average students and (b) groups composed evenly of strong and weak students but no average ones. I wanted a more elegant algorithm.
The other way to look at the problem is that I want each group to be as diverse as possible. If one maximizes each group's standard deviation, then (a) groups are ruled out. It is true that (b) groups would have the largest standard deviation possible -- but the magic here is that standard deviation is non-linear. Let's say that you have starting forming two groups -- group 1 {S, W, W} and group 2 {S, A, A} -- you have two more students to assign {S, A}. It is true that assigning the strong student to group 1 {S, S, W, W} makes its standard deviation bigger than assigning to it the average student {S, A, W, W}. In other words, std. dev. 1s > std. dev. 1a. But the key is that it makes a much bigger difference to group 2: std. dev. 2s is much, much bigger than std. dev. 2a.
Algebraically, (std. dev. 1s - std. dev. 1a) < (std. dev. 2s - std. dev. 2a). Equivalently, (std. dev. 1s + std. dev. 2a) < (std. dev. 2s + std. dev. 1a). Without algebra, the point is that (b) groups would never happen if you try to maximize the standard deviation of each group -- overall, you're always better to maximize the standard deviation of the least diverse group first. With this fact in mind, this becomes a simple maximization problem. This is an extremely powerful idea: to create the most balanced groupings, you make each group as diverse as possible. Below is an example. A fictional class of six will be divided into two groups.
As you can see, each colored line represents a possible set of groupings. The worst groupings are highlighted in red, the mediocre groupings are highlighted in yellow, and the good groupings are highlighted in green. The first cell under a group is its standard deviation, and the second cell is the group's average. I ranked the groupings by creating a geometric average (a b) ^ 0.5 of the two groups' standard deviations. I do generally agree with the rankings. In the red groupings, the groups are skewed: all strong students in one, all weak students in the other. As a result, both groups have low standard deviations. In the yellow groupings, one group is skewed, and the other group includes too many average students. As a result, one group has a high standard deviation, while the other has a low standard deviation. In the green groupings, both groups are balanced, so both have decent standard deviations.
As you'll notice, even for the best groupings, the average standard deviation of the groups doesn't exceed the standard deviation of the entire class. That's as it should be, but I'll leave that proof to an industrious reader.
Another, more realistic (though still fictional) example follows: dividing a 16-student class into four groups. There are too many possible groupings to list (more than 2.6 million), so I used an algorithm to pick a reasonably good solution. (I started by putting the four students in the very middle in different groups, then given that initial condition, the algorithm then assigned the remaining students in a way that attempted to maximize each group's standard deviation.) You can see the results below:
I lettered the students from A to P, strongest to weakest, and indicated a percentage grade for each. The four middle students were G, H, I, and J. You can see that the algorithm was able to do a decent job of maximizing each group's standard deviation (its explicit task); some came out slightly ahead, but they're all relatively large. But you can see how well the algorithm did creating balanced groups: 82.2, 82.4, 84, and 84.2. Remember, this result is an accidental byproduct of trying to create a solution that maximizes each group's standard deviation.
Why do I care so much about this? For one, I really do like having an algorithm that creates evenly balanced groups in my class. But two, I want to build this algorithm into a tabulation program -- for partial round robins. In a partial round robin, each team should hit a representative cross-section of the pool. Consider a 12-team round robin with 6 preliminary rounds. It's too tight to run a regular tournament and respect win-loss brackets. But if you can rank the teams before they arrive, then using my algorithm, each team could debate six opponents that are strong, mediocre, and weak.
Let's say on the first day of class, I give them a 20 point quiz to see how much of last year's math they remember. I can also use that information to create balanced groups; I don't want to put all the weak students in one group and all the strong students in another. Rather, I would like each group to include weak students, strong students, and average students.
One way to look at this problem is that I want each group's average to be close to the class average. One could design an algorithm to create the groups this way. But I realized as I was designing it that one has to make ad hoc rules that throw out (a) groups composed of entirely average students and (b) groups composed evenly of strong and weak students but no average ones. I wanted a more elegant algorithm.
The other way to look at the problem is that I want each group to be as diverse as possible. If one maximizes each group's standard deviation, then (a) groups are ruled out. It is true that (b) groups would have the largest standard deviation possible -- but the magic here is that standard deviation is non-linear. Let's say that you have starting forming two groups -- group 1 {S, W, W} and group 2 {S, A, A} -- you have two more students to assign {S, A}. It is true that assigning the strong student to group 1 {S, S, W, W} makes its standard deviation bigger than assigning to it the average student {S, A, W, W}. In other words, std. dev. 1s > std. dev. 1a. But the key is that it makes a much bigger difference to group 2: std. dev. 2s is much, much bigger than std. dev. 2a.
Algebraically, (std. dev. 1s - std. dev. 1a) < (std. dev. 2s - std. dev. 2a). Equivalently, (std. dev. 1s + std. dev. 2a) < (std. dev. 2s + std. dev. 1a). Without algebra, the point is that (b) groups would never happen if you try to maximize the standard deviation of each group -- overall, you're always better to maximize the standard deviation of the least diverse group first. With this fact in mind, this becomes a simple maximization problem. This is an extremely powerful idea: to create the most balanced groupings, you make each group as diverse as possible. Below is an example. A fictional class of six will be divided into two groups.
As you can see, each colored line represents a possible set of groupings. The worst groupings are highlighted in red, the mediocre groupings are highlighted in yellow, and the good groupings are highlighted in green. The first cell under a group is its standard deviation, and the second cell is the group's average. I ranked the groupings by creating a geometric average (a b) ^ 0.5 of the two groups' standard deviations. I do generally agree with the rankings. In the red groupings, the groups are skewed: all strong students in one, all weak students in the other. As a result, both groups have low standard deviations. In the yellow groupings, one group is skewed, and the other group includes too many average students. As a result, one group has a high standard deviation, while the other has a low standard deviation. In the green groupings, both groups are balanced, so both have decent standard deviations.
As you'll notice, even for the best groupings, the average standard deviation of the groups doesn't exceed the standard deviation of the entire class. That's as it should be, but I'll leave that proof to an industrious reader.
Another, more realistic (though still fictional) example follows: dividing a 16-student class into four groups. There are too many possible groupings to list (more than 2.6 million), so I used an algorithm to pick a reasonably good solution. (I started by putting the four students in the very middle in different groups, then given that initial condition, the algorithm then assigned the remaining students in a way that attempted to maximize each group's standard deviation.) You can see the results below:
I lettered the students from A to P, strongest to weakest, and indicated a percentage grade for each. The four middle students were G, H, I, and J. You can see that the algorithm was able to do a decent job of maximizing each group's standard deviation (its explicit task); some came out slightly ahead, but they're all relatively large. But you can see how well the algorithm did creating balanced groups: 82.2, 82.4, 84, and 84.2. Remember, this result is an accidental byproduct of trying to create a solution that maximizes each group's standard deviation.
Why do I care so much about this? For one, I really do like having an algorithm that creates evenly balanced groups in my class. But two, I want to build this algorithm into a tabulation program -- for partial round robins. In a partial round robin, each team should hit a representative cross-section of the pool. Consider a 12-team round robin with 6 preliminary rounds. It's too tight to run a regular tournament and respect win-loss brackets. But if you can rank the teams before they arrive, then using my algorithm, each team could debate six opponents that are strong, mediocre, and weak.
Subscribe to:
Posts (Atom)