June 17, 2018 9:52 AM

Sometimes, Evolution Does What No Pivot Can

From an old New Yorker article about Spotify:

YouTube, which is by far the largest streaming-music site in the world (it wasn't designed that way--that's just what it became)...

Companies starting in one line of business and evolving into something else is nothing new. I mean, The Connecticut Leather Company became Coleco and made video game consoles. But there's something about software that make this sort of evolution seem so normal. We build a computer system to solve one problem and find that our users -- who have needs and desires that neither we nor they fully comprehend -- use it to solve a different problem. Interesting times. Don't hem yourself in, and don't hem your software in, or the people who use it.

Posted by Eugene Wallingford | Permalink | Categories: Computing, Software Development

June 16, 2018 3:58 PM

Computing Everywhere: The Traveling Salesman Problem and Paris Fashion Week

I just read Pops, Michael Chabon's recent book of essays on fatherhood. The first essay, which originally appeared as an article in GQ, includes this parenthetical about his tour of Paris fashion week with his son:

-- a special mapping algorithm seemed to have been employed to ensure that every show was held as far as possible from its predecessor and its successor on the schedule --

My first thought was to approach this problem greedily: Start with the first show, then select a second show that is as far away as possible, then select a third show that is as far away as possible from that one, and so on, until all of the shows had been scheduled. But then I figured that a schedule so generated might seem laborious to travel at first, when there are plenty of faraway shows to choose from, but it might eventually start to seem pretty reasonable as the only shows left to schedule are relatively close.

We can generate a more wholly sort of unsatisfactory schedule by maximizing the total travel time of the circuit. That's the Traveling Salesman Problem, inverted. Taking this approach, our algorithm is quite simple. We start with the usual nxn matrix d, where d[i,j] equals the distance between shows i and j. Then:

  1. Replace the distance between every two show locations d[i,j], with -(d[i,j]), its additive inverse.
  2. Call your favorite TSP solver with the new graph.

Easy! I leave implementation of the individual steps as an exercise for the reader.

(By the way, Chabon's article is a sweet story about an already appreciative dad coming to appreciate his son even better. If you like that sort of thing, give it a read.)

Posted by Eugene Wallingford | Permalink | Categories: Computing

June 14, 2018 8:39 AM

Making Exceptions

When I became head of my department, one of the things that became a near-daily part of my life was enforcing administrative rules and fielding requests for exceptions to those rules. I like writing code a lot more, but these decisions involve a surprising amount of judgment, which can make them occasionally interesting.

A couple of weeks ago, Matt Reed wrote about the challenge of making exceptions to administrative rules. He opens by pointing to someone else's tweet asserting that exceptions to rules will largely flow to a certain group of students: those who grow up believing they have a right to question the rules. Reed acknowledges that this is true but goes on to argue that, even so, exceptions are an essential part of a fair system. I agree with him that there is a lot going here.

One of the few administrative tasks about which I had well-formed ideas before I started as head was applying rules. I'm in the group of students that many people would think of as privileged enough to be comfortable asking for exceptions. But I was also raised as a rule follower and, as a result, almost never asked for exceptions. I went through school following the rules as they were given to me and finding ways to move forward when the rules slowed me down. Occasionally I would learn that a friend had asked for an exception on a lark and ended up with an easier path. At first, I usually felt foolish for not asking myself; later, I would feel bad about myself for being a patsy, or cynical toward the system.

So, when I became an administrator, I wanted to be careful to apply the rules fairly, as they were intended, and not make exceptions just because someone asked for an out. It's tempting to help out a student when he or she asks for a break, but what about those students who didn't ask -- because they didn't know they could, or because they were afraid, or because they assumed the request would be denied? Things get hard sometimes when a faculty member presses for an exception to help a student they like or want to help. The faculty member will often say, "Well, the student wouldn't ask for this, so let's help them out anyway." But my thoughts stay with the students who won't ask and don't have an advocate. What about them?

If we start getting a lot of requests from faculty and students for an exception to a specific rule, I figure it's time for us to consider changing the rule.

However, as Reed argues, with any non-trivial rule, there really are exceptions to the spirit of the rule that we need to take into account. In his words, we need to exercise a little "epistemological humility". Even wise and experienced faculty members can't envision all possible circumstances that may arise when they write a rule. It's even harder to anticipate how a policy will interact with the myriad other policies enacted in the department or by other departments on campus. When those unexpected circumstances or interactions arise, we have to make exceptions if we really want to be fair. This means exercising judgment.

In my time as head, I have worked hard to walk the fine line between enforcing the rule as intended and making exceptions when exceptional circumstances arise. The challenge comes in dealing with groups of people at either end of a spectrum:

  • Some faculty want to make exceptions all the time. "It's just a rule," they say. "Why make someone suffer?"
  • Some faculty never want to make exceptions. They fear that our (or their) judgment will be called into question, and it's simpler -- and safer -- to never go out on a limb.

I learned early on that I was not omniscient and that the only way to be fair to students and faculty is to make exceptions. But I prefer to exercise judgment carefully. In order to do that, I ask for well-considered justifications.

To be honest, the justifications on most of the student requests I receive boil down to "because I want you to" or "because it would help me". If we enforce a prerequisite, it will push back a student's graduation date. (Sadly, failing a course has consequences...) If we enforce a distribution requirement, the student will have to take a course they don't like, or take a course from a professor they don't like.

In most of these cases, I sympathize with the student's plight, but that doesn't mean I can grant an exception. I try to probe for more details to see if there are grounds for further consideration, but most often I simply have to be the bearer of bad news.

(I've been talking about student requests a lot here, but my years as department head have taught me that faculty are not all that different. Some never ask for exceptions to rules that apply to them, while others ask freely. A surprising number of the requests also boil down to "because I want you to".)

With some effort, it is possible to walk the fine line. As Reed says:

The folks of whom exceptions are being asked need to be able to explain why they said "yes" to student A and "no" to student B. Ideally, they should know not only the rules, but the reasons behind the rules. That's a tall order, but in many cases, it can be done.

My general practice works something like this: Require that each request for an exception come with an actual justification that explains the exceptional circumstance. If the given justification is weak but I think there may be something worth considering, I work with the student (or faculty member) to elicit the deeper rationale behind the request. If the ultimate justification is solid, then I consider making an exception, sometimes in consultation with the faculty. Absent a solid justification, I enforce the rule. In those cases, I try to help the requestors understand why and, if possible, try to help them find other ways to handle the challenge facing them.

In my dozen or so years as head, I've surely made a few mis-steps, granting a request or two that should have been denied and denying a request or two that probably should have been approved. But I've worked hard to make good decisions, to recognize those cases in which I needed to update my thinking, and to recommend that we change rules when they no longer serve the purpose we intended. As with so many other tasks that we teachers and department heads perform, a little epistemological humility comes in awfully handy. Mistakes and struggles remind us to stay humble.

Posted by Eugene Wallingford | Permalink | Categories: Managing and Leading

June 03, 2018 10:50 AM

Two Thoughts on Teaching

... from my morning reading.

First, a sentence from Bryan Caplan, about one of his influences, philosopher Michael Huemer:

I think what's great about this book, and really all of Mike's work, is he always tries to start off with premises that make sense to people who don't already agree, and then try to get somewhere.

I value people who take the time to construct arguments in this way. It's surprisingly rare in academic discourse and public discourse. Teachers usually learn pretty quickly, though, that the most effective way to teach is start where your students are: recognize the state of their knowledge and respect their current beliefs. I try to remind myself of this principle regularly during a course, or I'm likely to go off track.

Second, the closing exchange from a 1987 interview with Stanley Kubrick. Kubrick has been talking about how the critics' views of his films tend to evolve over time. The interviewer wrapped up the conversation with:

Well, you don't make it easy on viewers or critics. You create strong feelings, but you won't give us any easy answers.
That's because I don't have any easy answers.

That seems like a pretty good aspiration to have for teaching, that people can say it creates strong feelings but doesn't give any easy answers. Much of teaching is simpler than this, of course, especially in a field such as computer science. A closure is something that we can understand as it is, as is, say, an algorithm for parsing a stream of tokens. But after you learn a few concepts and start trying to build or understand a complex system, easy answers are much harder to come by. Even so, I do hope that students leave my courses with strong feelings about their craft. Those feelings may not match my own, and they'll surely still be evolving, but they will be a product of the student engaging with some big ideas and trying them out on challenging problems.

Maybe if I keep reading interested articles on the exercise the bike and making connections to my craft, I can get this computer science thing down better.

Posted by Eugene Wallingford | Permalink | Categories: General, Teaching and Learning

June 01, 2018 3:05 PM

Prepare to Appreciate the Solution

This post isn't really about chess, though it might seem at first to be.

In The Reviled Art, chess grandmaster Stuart Rachels says that most grandmasters don't like composed chess problems because they are too difficult. It's easy to imagine why average chessplayers find problems too difficult: they aren't all that great chess. But why grandmasters? Rachels contends that problems are hard for tournament players because they are counterintuitive: the solutions contradict the intuitions developed by players whose chess skill is developed and sharpened over the board.

Rachels then says:

Most problems stump me too, so I conceive of the time I spend looking at them as time spent preparing to appreciate their solutions -- not as time spent trying to solve them.

I love this attitude. If I view time spent banging my head against a puzzle or a hard problem as "trying to solve the problem", then not solving the problem might feel like failure. If I view that time as "preparing to appreciate the solution", then I can feel as if my time was well spent even if I don't solve it -- as long as I can appreciate the beauty or depth or originality of the solution.

This attitude is helpful outside of chess. Maybe I'm trying to solve a hard programming problem or trying to understand a challenging area of programming language theory that is new to me. I don't always solve the problem on my own or completely understand the new area without outside help or lots of time reading and thinking. But I often do appreciate the solution once I see it. All the time I spent working on the problem prepared me for that moment.

I often wish that more of my students would adopt Rachels's attitude. I frequently pose a problem for them to work on for a few minutes before we look at a solution, or several candidates, as a group. All too often some students look at the problem, think it's too difficult, and then just sit there waiting for me to show them the answer. This approach often results in them feeling two kinds of failure: they didn't solve the problem, and they don't even appreciate the solution when they see it. They haven't put in the work thinking about it that prepares their minds to really get the solution. Maybe I can do more to help students realize that the work is worth worth the effort even if they don't think they can solve the problem. Send me your suggestions!

Rachels's point about the counterintuitiveness of composed chess problems indicates another way in which trying to solve unorthodox problems can be worthwhile. Sometimes our intuitions let us down because they are too narrow, or even wrong. Trying to solve an unorthodox problem can help us broaden our thinking. My experience with chess compositions is that most of the ideas I need to solve them will not be helpful in over-the-board play; those kinds of positions simply don't occur in real games. But a few themes do apply, and practicing with them helps me learn how to play better in game situations. If nothing else, working on unorthodox problems reminds me to look outside the constraints of my intuitions sometimes when a problem in real life seems too hard.

Posted by Eugene Wallingford | Permalink | Categories: General, Teaching and Learning

May 29, 2018 3:41 PM

Software as Adaptation-Executer, Not Fitness-Maximizer

In Adaptation-Executers, not Fitness-Maximizers, Eliezer Yudkowsky talks about how evolution has led to human traits that may no longer be ideal in the our current environment. He also talks about tools, though, and this summary sentence made me think of programs:

So the screwdriver's cause, and its shape, and its consequence, and its various meanings, are all different things; and only one of these things is found within the screwdriver itself.

I often fall victim to thinking that the meaning of software is at least somewhat inherent in its code, but that really is what the designer intended as its use -- a mix of what Yudkowsky calls its cause and its consequence. These are things that exist only in the mind of the designer and the user, not in the computational constructs that constitute the code.

When approaching new software, especially a complex piece of code with many parts, it's helpful to remember that it doesn't really have objective meaning or consequences, only those intended by its designers and those exercised by its users. Over time, the users' conception tends to drive the designers' conception as they put the software to particular uses and even modify it to better suit these new uses.

Perhaps software is best thought of as an adaptation-executer, too, and not as a fitness-maximizer.

Posted by Eugene Wallingford | Permalink | Categories: Computing, Software Development

May 27, 2018 10:20 AM

AI's Biggest Challenges Are Still To Come

Semantic Information Processing on my bookshelf

A lot of people I know have been discussing last week's NY Times op-ed about recent advances in neural networks and what they mean for AI. The article even sparked conversation among colleagues from my grad school research lab and among my PhD advisor's colleagues from when he was in grad school. It seems that many of us are frequently asked by non-CS folks what we think about recent advances in AI, from AlphaGo to voice recognition to self-driving cars. My answers sound similar to what some of my old friends say. Are we now afraid of AI being able to take over the world? Um, no. Do you think that the goals of AI are finally within reach? No. Much remains to be done.

I rate my personal interest in recent deep learning advances as meh. I'm not as down on the current work as the authors of the Times piece seem to be; I'm just not all that interested. It's wonderful as an exercise in engineering: building focused systems that solve a single problem. But, as the article points out, that's the key. These systems work in limited domains, to solve limited problems. When I want one of these problems to be solved, I am thankful that people have figured out how to solve and make it commercially available for us to use. Self-driving cars, for instance, have the potential to make the world safer and to improve the quality of my own life.

My interest in AI, though, has always been at a higher level: understanding how intelligence works. Are there general principles that govern intelligent behavior, independent of hardware or implementation? One of the first things to attract me to AI was the idea of writing a program that could play chess. That's an engineering problem in a very narrow domain. But I soon found myself drawn to cognitive issues: problem-solving strategies, reflection, explanation, conversation, symbolic reasoning. Cognitive psychology was one of my favorite courses in grad school in large part because it tried to connect low-level behaviors in the human brain connected to the symbolic level. AlphaGo is exceedingly cool as a game player, but it can't talk to me about Go, and for me that's a lot of the fun of playing.

In an email message earlier this week, my quick take on all this work was: We've forgotten the knowledge level. And for me, the knowledge level is what's most interesting about AI.

That one-liner oversimplifies things, as most one-liners do. The AI world hasn't forgotten the knowledge level so much as moved away from it for a while in order to capitalize on advances in math and processing power. The results have been some impressive computer systems. I do hope that the pendulum swings back soon as AI researchers step back from these achievements and builds some theories at the knowledge level. I understand that this may not be possible, but I'm not ready to give up on the dream yet.

Posted by Eugene Wallingford | Permalink | Categories: Computing

May 22, 2018 3:30 PM


This weekend, my family headed to St. Paul, Minnesota, to celebrate my younger daughter's graduation from college. The day served as a bookend to the day. seven years ago this fall when I dropped my older daughter off at college. Two beginnings, two endings -- and the beginnings they created.

Graduation day was emotional for me in a different way. It is wonderful gift to hear faculty and friends say such good things about your child. This is a young women I've always known to be special, and now we know some of the ways the rest of the world appreciates her. They appreciate some of the same things I appreciate, but they also know her in ways I do not and so can appreciate her ways I don't always have access to. Another gift.

Off into the world she goes to do her thing. To be honest, though, she's been out in the world for a long time doing her thing and making it a better place. It's one of the things I admire so in her, and in her big sister. I enjoy admiring my daughters as much as I do.

With both daughters out of college, I will miss the time we've spent visiting their college campuses. I tried to savor this weekend more knowing as I do how much I missed my older daughter's campus after she graduated. Of course, now I'll get to visit them in places like Boston and Minneapolis and get to know these cities better, through their eyes. Yet another gift.

Posted by Eugene Wallingford | Permalink | Categories: Personal

May 18, 2018 1:24 PM

Sharing Control

Sidney Lumet, in his book Making Movies, writes:

Arthur Miller's first, and I think, only novel, Focus, was, in my opinion, every bit as good as his first produced play, All My Sons. I once asked him why, if he was equally talented in both forms, he chose to write plays. Why would he give up the total control of the creative process that a novel provides to write instead for communal control, where a play would first go into the hands of a director and then pass into the hands of a cast, set designer, producer, and so forth? His answer was touching. He loved seeing what his work evoked in others. The result could contain revelations, feelings, and ideas that he never knew existed when he wrote the play. That's what he hoped for.

Writing software for people to use is something quite different from writing a play for audiences to watch, but this paragraph brought to mind experiences I had as a grad student and new faculty member. As a part of my doctoral work, I implemented a expert system shells for a couple of problem-solving styles. Experts and grad students in domains such as chemical engineering, civil engineering, education, manufacturing, and tax accounting used these shells to build expert systems in their domains. I often found myself in the lab with these folks as they used my tools. I learned a lot by watching them and discussing with them the languages implemented in the tools. Their comments and ideas sometimes changed how I thought about the languages and tools, and I was able to fold some of these changes back into the systems.

Software design can be communal, too. This is, of course, one of the cornerstones of agile software development. Giving up control can help us write better software, but it can also be a source of the kind of pleasure I imagine Miller got from working to bring his plays to life on stage.

Posted by Eugene Wallingford | Permalink | Categories: Software Development, Teaching and Learning

May 09, 2018 4:02 PM


In an old blog post promoting his book on timing, Daniel Pink writes:

... Connie Gersick's research has shown that group projects rarely progress in a steady, linear way. Instead, at the beginning of a project, groups do very little. Then at a certain moment, they experience a sudden burst of activity and finally get going. When is that moment? The temporal midpoint. Give a team 34 days, they get started in earnest on day 17. Give a team 11 days, they get really get going on day 6. In addition, there’s other research showing that being behind at the midpoint--in NBA games and in experimental settings--can boost performance in the second half.
So we need to recognize midpoints and try to use them as a spark rather than a slump.

I wonder if this research suggests that we should favor shorter projects over longer ones. If most of us start going full force only at the middle of our projects, perhaps we should make the middle of our projects come sooner.

I'll admit that I have a fondness for short over long: short iterations over long iterations in software development, quarters over semesters in educational settings, short books (especially non-fiction) over long books. Shorter cycles seem to lead to higher productivity, because I spend more time working and less time ramping up and winding down. That seems to be true for my students and faculty colleagues, too.

In the paragraph that follows the quoted passage, Pink points inadvertently to another feature of short projects that I appreciate: more frequent beginnings and endings. He talks about the poignancy of endings, which adds meaning to the experience. On the other end of the cycle are beginnings, which create a sense of newness and energy. I always look forward to the beginning of a new semester or a new project for the energy it brings me.

Agile software developers know that, on top of these reasons, short projects offer another potent advantage: more opportunities to take stock of what we have learned and feed that learning back into what we do.

Posted by Eugene Wallingford | Permalink | Categories: General, Software Development, Teaching and Learning