First Steps in School Choice

Do you know what algorithm your district uses to assign students to public schools? A fair school-choice process is an essential part of a functioning democracy, and determining the “best” algorithm involves carefully weighing tradeoffs between student welfare, equity, and distributional goals like gender equality and racial diversity. Such considerations are the basis for my thesis research in the Management Science/Optimization lab here at SNU.

I coded a few commonly used algorithms in Julia, and this week I've been running computer simulations to reproduce a few well-known results in this area of the literature. Check out my implementation and a brief discussion on Github.

The Optimal Stable Marriage

A one-to-one assignment problem involves a set of two groups, candidates and reviewers, each of whom has ranked the members of the other group on the basis of how much they would like to be paired together. A classic problem in game theory involves finding a stable assignment, or a way of pairing up candidates and reviewers such that no member of either group is incentivized to cheat on their partner. In a large problem, there may be more than one way to do this, but it isn’t necessarily easy to find all of the stable assignments or determine which one represents the best compromise between the candidates’ and reviewers’ interests. I have written some code that solves this latter problem. The algorithm it uses was developed in the 1980s, and I am currently working on improving its performance and extending it to many-to-one assignment problems. My code and further discussion are on Github here.

Three Creations

Python implementations of a two-phase simplex method and sparse LU matrix factorization.

An article about Korean SF in the Emory Journal of Asian Studies.

And an EP:

Day Seven of Fourteen

I’m trying to make everything last. But I already ate the chocolate. I had promised it to myself as a reward for getting halfway through isolation halfway intact, and I kept that promise this afternoon, most of the way between lunch and dinner. Otherwise, I’ve been spending most of my time on math, learning as many math words as I can in Korean and getting comfortable with the concepts I’ll need in my research group. I coded a simplex method.

One of the staff at the quarantine facility gave me his contact info and said we should stay in touch. I have my first friend, then, at SNU, and you could do some Bayesian stuff to argue it won’t be long before I have a couple others. This has me in high spirits. That, and that they are feeding us well.

It occurs to me that there will be a day at the end of this when I look back and say, I can’t believe how fast it went. Certainly it was like that with my time in Naju. I can still recall, if I look far enough inward, the feeling of my bed in my apartment by the river, the way the trees framed the window, the awkward hop between the bedroom and the shower … but I can also feel the memory fading, already, as irretrievable as every other mundane sensation.


They say that we perceive time by the accumulation of novel experiences, so that if you want to have a subjectively long life, you ought to do many spontaneous and hard-to-repeat things, but if you want to have a happy life, you ought to find one or two high pleasures that you can enjoy on a spiritual level and repeat the hell out of them, because they also say that on average, people derive more happiness from repeating a good experience than from trying something new.

You could write a linear program that targets your ideal mix of longevity and happiness and it would tell you exactly how many times to do this or that activity before moving onto something new. But what this calculus leaves out is the feelings of uncertainty that stain the transitions.

I am leaving Naju, after having grown accustomed to this routine, this commute, these faces, and I cannot say with any confidence that I have reached a joy plateau. Every week of teaching here has been better than the last: my skills have improved, my confidence has grown, and the teachers and students have become only more important to me. I could be happy like this for a long time. But.

But too much comfort has a way of smearing all the time together, so that the things that take place in a given day feel less like events and more like footnote references to proto-events hovering in the firmament of the distant past. I have already seen the river clog itself with duckweed; I have already looked down the street from all four of the intersection’s corners, trying to make the buildings line up with the trees. Upon inspection, a more sensitive man might look at these rhododendrons and see something more than last year’s blossoms in a different configuration, but I am a pattern-matcher by nature, too easily bored to remain a recluse. It is time for a new challenge.

As I wrap up my Fulbright grant, I am delighted to share that I have been accepted into the Government of Korea Scholarship program, through which I will be returning to Korea in the fall to pursue a fully funded master’s degree in industrial engineering at Seoul National University.

Thank you to all who have encouraged me.

A Parametric Curve Utility in Python

To run certain kinds of simulations, we need to generate random points that are evenly distributed along a certain curve (say, a circle) or over a surface (like a cube). If you have a formula for the length of the curve or the surface area, you can work backwards to find a procedure for generating the random points. But there are many mathematical curves, like ellipses, whose perimeter cannot be expressed using a formula. Instead, it must be computed numerically, by picking a large number of points along the curve and adding up the distance between them. The same applies to the surface area of many surfaces in three dimensions.

I have recently published param_tools, a small Python module that performs these numerical computations for a given curve or surface and generates random data in the desired region. The curve or surface can be given in either parametric coordinates or as a set of ordered points. And instead of generating random data, it can also map uniformly-spaced data or data from an arbitrary probability distribution to a specified curve.

This is the first standalone module I have posted to Github, so I welcome feedback on the implementation and documentation.

And here are some puppies who followed my students to school this week:

The Benefits of a Nonnative Teacher

In addition to the myth that it’s impossible for adults to “really” learn a foreign language, a widely held misconception about language learning is the notion that beginners must learn from native speakers. Many are willing to allow that a nonnative English speaker could make as good a teacher as a native speaker, but fewer recognize the pedagogical advantages offered by someone who has learned the target language as an adult and can understand what it looks like from the student’s perspective.

In the ELL classroom, we often encounter questions like: Why is it correct to say I am going to school but wrong to say I am going to home? A native speaker has to think about this: Is there a reason we drop the to before home, maybe something to do with the fact that you can attend, in theory, multiple schools but can have only one true home? Or is it because it just “sounds better”? Or maybe it’s just a random exception, but then, which one is the exception and which one is the rule?

Someone who learned English as an adult can tell you immediately that I am going home is a random exception, and that to is the rule when you are going to a specific, named place. The only reason I, a native English speaker, know this is that a similar exception exists in German: Ich bin zu Hause. When I asked my German teacher (a nonnative English speaker) about that sentence, she asked, rhetorically, “Why is it correct to say I am going to school but wrong to say I am going to home?”—having learned this very thing in school.

With some effort, you can generate sentence pairs that demonstrate the opposite case, where a native speaker feels inclined to call the difference a random exception when in fact there’s a grammatical rule in play. Here’s a test question that I’ve encountered in various forms:

I think dogs are awesome. I think cats are OK. Circle all correct sentences:

  1. I like dogs more than cats.
  2. I like dogs better than cats.
  3. I like more dogs than cats.
  4. I like cats less than dogs.
  5. I like cats fewer than dogs.

The answer is choices B and D. Most native speakers see nothing wrong with A, because it’s something that we actually do say, but according to a strict interpretation of the rules of English grammar, A is wrong for the same reason that C and E are wrong: more is for comparing quantities of things, but like expresses a binary preference. By an even stricter interpretation of the rules, you can argue that choice D should have worse instead of less, but the prescriptivists who write Korean standardized tests of English grammar have moved past that archaism even as they’ve resisted allowing choice A.

Native English speakers who teach in Korea are often given test questions like these, along with the answer key, and asked to explain the correct choice. Because the answer key disagrees with our intuition, we tend to grasp for an explanation and fail. On the other hand, a Korean teacher can reference the textbook page that discusses more than and better than and be done with it.

You might argue that memorizing these kinds of formalisms falls short of actual language acquisition, and you would be correct—language learners need also to engage with authentic texts and audio, experiment with the target language in roleplay scenarios, and practice speaking freely without worrying about errors. But teaching the more than/better than distinction, even if the student will eventually discard that rule as they encounter English in the wild, is useful because it primes the student’s awareness of the different kinds of comparisons available in the language.

Consider: You can allow choice A in the above question, but then students will ask why its parallel, choice E, is wrong, and you’ll teach them the fewer than/less than distinction, but then you’ll have to explain why there isn’t a more than/better than distinction as well. Yuck! It’s better (more?) to avail beginners of a consistent set of principles that mostly work, while maintaining a mental inventory of exceptions, and exceptions to the exceptions, in case a smart kid asks a good question.

Most native teachers long to do away with multiple-choice questions like the above. At best, they make for interesting illustrations of how English grammar is a moving target and there’s no universal set of rules obeyed by all English speakers everywhere forever. At worst, they make for frustrating illustrations of how English grammar is a moving target and there’s no universal set of rules obeyed by all English speakers everywhere forever. A nonnative speaker, who can detach herself from personal feelings about what constitutes “natural” English, can distinguish between language usage and test-taking strategy. A savvy test-taker, confronted with the above question, doesn’t have to know whether I like dogs more than cats is admissible in Korean Standard English; she merely recognizes that this question is “about” the more than/better than distinction and eliminates choice A because standardized examinations test rules, not exceptions.

Now, native speakers can learn to speak abstractly about grammar like nonnative speakers do, but it’s an acquired skill, just like algebra. While it’s theoretically possible for a native speaker to deduce the rules of his language’s grammar from first principles, a speaker who learned the language as an adult learned those rules at the same time, whereas native teachers like me have to scramble through Google to find answers or make up rules that seem right at first but collapse upon inspection.

I have learned a great deal of Korean from native speakers, but my foundation in the Korean language was established in a class at the UW taught by an American. After that, I had Korean professors and TAs who had invested considerable time in learning to speak about Korean, and they understood the utility of abstract grammar because they had relied on it themselves in learning English. To the extent that I’m good at Korean now, I attribute my success more to the many opportunities I’ve had to carefully examine Korean grammar and etymology than to my friendships with native speakers. That part’s just fun.

Accidental Signals

It is a well-known result in psychology that measures of intelligence correlate across domains. If you are good at math, you are probably also good at verbal reasoning, and vice versa. Therefore, if a company is hiring for a position that requires a variety of skills (as most jobs do), it should pick a candidate who has demonstrated impressive skill in one domain over someone who has demonstrated middling proficiency in a number of different domains.*

Hiring managers’ preference for specialists is widely known. So, smart people, who tend to be good at estimating job-market incentives (thanks to the correlation between domains of intelligence), gravitate toward programs that award narrow, in-demand credentials—even when the credentials are nominally equivalent (a BA in linguistics vs. a BA in English). This can create a feedback loop in which fields that are perceived as “challenging,” like computer science, attract challenge-seeking entrants, raising the standards of proficiency within the field and making it more difficult for a newcomer to rise above average. On the other hand, majors that are perceived as relatively easy, like sociology, may attract less-ambitious students, leading to deflated expectations and dissuading hard workers. (I have met a few people who told me that they majored in the liberal arts because they were “bad at math.” I have never met a STEM major who chose their field because they were “bad at writing.”)

(National Center for Education Statistics, Undergraduate Degree Fields)

Nothing in this argument depends on the skills actually conferred by a given degree program or the skills actually required by an employer. A tech company needs managers and product designers just as much as it needs engineers, but positions in management and product design are typically reserved as rewards for distinguished engineers rather than handed out to people who majored in management or design. This is because a coder’s science degree(s), plus a few years of demonstrated commitment to the company, signals greater potential for success in the new role than some stranger’s design credential, which may relate more to the job but is also easier to obtain.

The problem comes when we confuse these signals of potential with the thing itself. To depart from credentials for a moment, one such signal is “grit” (tenacity, work ethic, passion), which Angela Duckworth argues is the best predictor of career success. This conclusion is obvious if taken as a prescription for moneymaking. But the book (Grit: The Power of Passion and Perseverance, 2016) becomes more interesting if we read it as a diagnosis: an attempt to organize American capitalism’s scattered, ever-changing incentives under a handy label. It is this explanatory power that makes grit conceptually coherent. Successful people come from a range of economic and educational backgrounds, but what they all have in common is—see book title.

However, grit’s conceptual strength comes at the cost of moral clarity. In a later chapter, Duckworth begins to caution that grit is morally neutral: good and bad people (she mentions Hitler) alike can be possessed of grit, so we should not regard someone as morally virtuous just because they are gritty. This is correct, but Duckworth fails to take the further step of disclaiming the converse: she assumes that moral people will see value in grit and pursue it for its own sake. On the contrary, we (moral people, presumably) ought to question the value of grit, because the positive traits by which Duckworth defines it can be easily reframed as negatives: Where does tenacity end and stubbornness begin? What about work ethic and workaholism, or passion and temper? We can think of a few geniuses whose “passion” had disastrous consequences for their personal and professional lives.

While you may cultivate success through grit (and leverage your success for moral good), will you, in your power, recognize the worth of someone who is highly intelligent and hardworking but has not developed grit as a signal of this potential? Under a different incentive structure—an unstable family environment, for example—an effective learner might develop, in place of tenacity, the ability to recognize a losing battle; in place of discipline, flexibility; in place of passion, consideration of communal needs. These latter traits are not incompatible with grit’s essence, but they may interfere with grit’s signal when it is measured by prompts like, “I finish whatever I begin” (to which the respondent answers on a scale from “not like me at all” to “very much like me”). Grit is an abstract concept that attempts to unify many disjoint values under one label. It may reliably indicate career potential—it may even be the most reliable such indicator available—but it does so only “by accident”: it signals the presence of a collection of traits that employers value, not the merit that undergirds the traits themselves.

So it goes with credentials. Achieving a high level of expertise in any field is hard. But the accidental arrangement of the job market at a particular moment in time has stiffened competition in some fields and weakened it in others. Today, it is relatively easy to parlay a STEM degree into a number of careers. That is not because everyone “needs” to know differential equations, but because knowing that someone passed a differential equations (MATH 235) tells us more about their overall intelligence than knowing that they can speak intermediate French (FREN 235). A STEM degree is a proximate signal of being good at following directions, which is in turn a proximate signal of career success.

Ideally, employers, grad schools, and other such gatekeepers would shun such imperfect signals. Instead, they ought to evaluate each candidate on an individual basis, combing through their background in search of desirable traits. But this is cost-intensive, so gatekeepers bet on the reliability of cheap signals like credentials and test scores instead. They do not work perfectly, but they work well enough, most of the time.

* You may have heard that the instruments we use to measure “intelligence” are biased toward people from dominant cultural backgrounds and people of financial means. This is a good argument against the use of standardized testing in college admissions, but it does not contradict the claim that I am using here, namely, that intelligence between domains (and within an individual) is correlated.

Math Imitates Life

You can write a linear program to determine the minimum-weight structure needed to support a fixed load. The optimal solution is a leaf!

Here are some more linear programming notes.

English Notes

  • Bypass vs. pass by
    Overturn vs. turn over
    Outrun vs. run out
    Inlay vs. lay in
  • He struggled for years to overcome his addiction. (He overcame it.)
    He struggled for years to overcome his addiction. (He succumbed.)
  • I was so upset, she slapped me. (I was upset and she slapped me.)
    I was so upset she slapped me. (I was upset because she slapped me.)
  • Cyan vs. cayenne. You’d think the vowels would be the different thing here.
  • What do you need, to be happy forever? (Don’t take happiness for granted.)
    What do you need to be happy forever? (How can I make you happy?)
  • Upheld in court (vindicated)
    Held up in court (delayed)
  • I want to do it because I want to, not because I have to. (I would rather choose freely to do so than be compelled.)
    I want to do it because I want to, not because I have to. (I am choosing freely to do it, not being compelled.)
    I think this one works in Korean, too.

Requisite Season

Lately I’ve been reading Helen Dewitt’s The Last Samurai, listening to Gene Harris’s Live in London, and consuming this enigmatic tea:

The owner of the café, who I will call Imo because that’s what I call her, just brought it to my corner seat. Imo said her little sister had sent it from Iran, and when I asked how someone from Naju could possibly end up in Iran, she said, “Oh, she works there.” I was calculating my follow-up question when Imo pulled out her phone and started scrolling through her sister’s Instagram. The photos she showed me looked like anywhere but Iran: little sister dancing in a party dress, little sister sunbathing, little sister peeking out from under a comforter.

“She’s 43,” Imo explained, “and I know she looks young now, but she’ll catch up to me soon. I’m over 50, as you know.”

I did not know.

Then Imo went and watered her plants for a while, and I did a section in my linear programming textbook. When she returned, she gave me plastic bag filled with what she called 보름밥 (fifteen-day rice), which as best as I can tell is a homely way of referring to 오곡밥 (five-grain rice), rice cooked together with ginkgo nuts, beans, and other assorted protein nuggets. As she put the rice and a few seaweed packets into a shopping bag from Guess, Imo explained that the early weeks of February (the first fifteen days of the lunar year, I gather) are the requisite season for eating this kind of mixed rice.

Perhaps I understand the strong duality theorem, but I can make no sense of my daily interactions.

What You Learn in a Humanities Degree

The more I learn, I find myself with fewer and fewer things to say.

As a humanities student, I studied many “theories.” One theory is historicism, which says that things are the products of their historical settings. Example: At a career mixer, a well-dressed alumnus, class of ’70, approaches a sophomore journalism major. “The first thing you should do once you’re financially independent and you’ve got some money saved up is make a down payment on a house. Nobody will ever stop needing houses,” he says. The advice is a historical artifact, extruded from a certain moment in American politics and a certain set of assumptions about credit scores and work contingency and citizenship status. The student may react with with doubt; her doubt is also historical. It encodes her upbringing, and a different relationship with houses and banks and the word independent.

We could apply any number of other theories to this interaction. There is a theory that explains why the man feels no reservation in handing out unsolicited advice, and another that explains why the student smiles and sips her iced tea instead of challenging him. There is another theory that explains why conversations about what to do with wealth are appropriate at a university career mixer—what the conversation implies about the prestige of the university, the status of the alumnus, the prospects of a nascent journalism career. Given a set of questions about a situation, or “text,” we can use contrasting theories to harvest competing answers to the questions. Then the merits of the theories can stand in for the merits of the answers. (If we are especially cunning, we might presuppose which answers we want to find and then focus on the theory that guides us there. You can bring up this point as a lazy counterargument next time I say I am using an “interdisciplinary approach” to argue for an idea you disdain.)

When I was a student, my favorite theory was what we might call discursivism, a literary theory that says, essentially, that language is simultaneously “about” both language itself and whatever it is that the language at hand is talking about. “Nobody will ever stop needing houses” is not just a phrase, but a catchphrase, an idea whose snappy wording embeds a claim about its salience. The secret message is something like: If what I am telling you right now isn’t true, then how come I can say it so succinctly? Indeed, anytime we raise our voice, we are secretly transmitting a claim about our own act of speech: I am able to put these thoughts into words, therefore they must have some merit.

Theories are quite powerful, because they allow us to convert small amounts of information into large amounts of information. (More words have been written about Shakespeare than Shakespeare ever wrote.) We use theories to put words into others’ mouths. For example, Americans tend to think of themselves as formidable amateur psychoanalysts. It is not uncommon to hear Americans dismiss each other by saying they are “projecting” or “deflecting” or “repressing” something. Psychoanalysis is a theory, a theory according to which we spend life restaging traumatic incidents from childhood in a hopeless search for resolution. Like many theories, psychoanalysis rejects the possibility of objective observation; thus you can talk in circles by telling your opponent, “No, I think you’re repressing!” Without realizing it, we are two levels of abstraction away from the issues at hand, but because culture has made us comfortable with pushing theories around like pieces on a chess board, both parties proceed in the illusion that material gains are at stake. In fact, when we pit theories against each other, what we are gaining is information: about the matter in question, yes, but also about the theories themselves, their breadth and depth.

We cannot break free of theories. Whether or not you have received a traditional education, your thought patterns have been shaped by your experiences of people and your interactions with “texts.” A theory doesn’t need to have a Wikipedia entry for it to color your thoughts. Thus, one of the goals of a liberal education is to equip you with a wide range of theories, so that in an unfamiliar situation, you can try out various theories in succession as a corrective against your default narrative, the hope being that you will test out various responses and select the best one. However, being theoretically versatile—I have called this narrative fluency—is more likely to make us good at justifying our prior beliefs (whether or not they are correct) than at reexamining and overturning them.

Thus, I am finding myself with less and less to say, because I am paralyzed by the sense that if I manage to say something convincing, it will be so only because I have applied a theory in a novel or resonant way, and not because the underlying idea has merit. I have spent so much time playing with theories that nowadays, I sometimes myself testing facts against beliefs rather than beliefs against facts, so that when I encounter a set of facts that resist one of my beloved theories, I search for better facts instead of modifying my assumptions.

In courtroom dramas, lawyers begin their closing arguments by saying, “Let’s let the facts stand on their own,” and then they proceed to enumerate the facts, thereby preventing them from standing on their own. When—not if—the facts are inventoried, curated, rehearsed, ordered, voiced in a measured tone, calibrated for this trial and these jurors, then the facts are being coerced to an invisible theory. We are awash in theories, and the only way to let the facts stand on their own is to say nothing.

Aretha and Brad

I have been measuring the leaves of my houseplants.

It is surprising how normal these distributions are.
I’m putting my stats notes here.