Of Running and Programming

Seems like this has been my life of late: as spring blooms and the end of the semester nears, I’ve had time for running and working. Both have been progressing well, so I suppose I can’t complain.

Well, mostly progressing well.

Running

Two weekends ago was the Just A Short Run race, which The Lady and I (plus a bunch of my fellow Ph.D. students!) participated in. We ran the 13.1mi race, while Devin ran the 5k (it was his first race ever), MCC and Rachel ran the 8.1mi, and Rob ran the 30k.

I won’t go into a full race report (though The Lady posted hers here, check it out!), but I will mention a few details. This race was about 5 weeks out from the Pittsburgh half and served as a solid test run to see how we were doing. My previous PR–Air Force–stood at 1:53. I definitely wanted sub-1:50 on this race, but given that I was still kicking the final vestiges of the Moroccan Plague, I wasn’t expecting much more than that.

Plus it was cold the morning of the 31st of March. Figures.

Pwned.

I started with the 1:50 pace group and decided I’d stay with them as long as I could, and if I was feeling good, I’d push it at the end. I stayed with them for the first 3-4 miles, at which point one of the runners in the group–a cross-country runner–broke off from the group. I shrugged, thought what the heck, and followed.

For the rest of the race.

Yeah, I beat the time I’d wanted for the Pittsburgh half. The Lady also had a fantastic outing, beating her previous half marathon PR and finishing in under 2 hours.

Now I’m wondering what to do about the Pittsburgh half. PR once again is always a goal, for sure, but the next 5-minute increment, 1:40, is a pretty lofty goal, demanding an average pace of 7:37/mi. My tempo runs are currently 7:30/mi, but I only have to maintain that pace for 4, 5 miles at most. Yesterday I pushed this limit and went on a run with Rob (who will be in this year’s Boston marathon, by the way), and these were the results: 8.5 miles at a 7:45 moving pace (it was probably lower than that, as the GPS had to decide when I was waiting at a stoplight, since for whatever reason I didn’t manually stop and start my watch). So I can do 8.5 miles at the pace I want, but can I extend this another 4.5 miles? We’ll find out, I suppose.

I felt like the black one after that run with Rob.

Here’s the thing about that particular run: it was incredibly taxing. The route itself was extremely hilly almost entirely throughout (though the last few miles were ok). Rob is also an amazing runner; the 7:30 pace we were shooting for is effectively his easy pace, as we were often speeding up to 7:00 or even 6:50.

If I had tried that by myself, I would have quit. Several times (in fact, I did). But in running with someone who is a far better runner than I, and someone who is also a pleasure to run with (he’s ridiculously encouraging and easygoing), plus my own football-honed sense of competition and stubbornness, got me through the run without any breaks aside from the stoplights. It was intense.

Needless to say, running is going well, but by virtue of–quite literally–rushing into these new speeds, I don’t feel quite as certain about my strategies as I used to.

Programming

I’ve mentioned before that I have a group of undergraduate seniors working with me for their capstone project. Well, we’re drawing dangerously close to the end of the semester, and the time to start getting some deliverables. The original objective–implementing this algorithm on Mahout–was tossed out fairly early on in favor of some more in-depth analysis that only required their sequential implementation.

Other questions we pondered when deciding what to implement.

Fast forward to this week. We’re two weeks out from deadline, and we’re just now getting the algorithm off the ground and turning our attention to analyzing the results somehow. I’ve largely tried to be hands-off, as this is their own capstone project so the details of the implementation should be under their control. After all, they’re Computer Science seniors, about to jump into the real world.

Problem: evidently there was a miscommunication, and the students ended up diverging from the theory and writing their own algorithm. It wasn’t terrible: the actual code needed was all of 15 lines, and I went ahead and wrote it myself. Furthermore, at the request of one of the other students, we’ll simply compare the two methods for accuracy. So it’s not all bad.

Just for grins, here’s the code I added:

    public void estimateTransitionMatrices(int subspace) {
        // X is our X.
        RealMatrix X = this.svd.getX(subspace);

        // W is our stacked matrix of "order" number of offset X's.
        RealMatrix W = new Array2DRowRealMatrix(X.getRowDimension() * this.order, X.getColumnDimension() - this.order);

        // Loop over the "order" sub-matrices of X needed. This loops stacks
        // the matrix from the top down (so the last element inserted, at the
        // bottom of the matrix W, will be X1).
        RealMatrix Xi = null;
        for (int i = 1; i <= this.order; ++i) {
            Xi = X.getSubMatrix(0, X.getRowDimension() - 1, this.order - i, X.getColumnDimension() - (this.order + i - 1));
            W.setSubMatrix(Xi.getData(), (i - 1) * Xi.getRowDimension(), 0);
        }
        // Now we need, for a markov system of order "order", the "order + 1" X:
        Xi = X.getSubMatrix(0, X.getRowDimension() - 1, this.order, X.getColumnDimension() - 1);

        // Finally, do the multiplication to get the transition matrices. This
        // requires taking the pseudo-inverse of W (also described in the same
        // section of the Hyndman thesis).
        SingularValueDecomposition inv = new SingularValueDecomposition(W);
        RealMatrix A = Xi.multiply(inv.getSolver().getInverse());

        // Now some housekeeping: the transition matrices are all horizontally
        // packed in A, so we need to extract them.
        for (int i = 0; i < this.order; ++i) {
            RealMatrix Ai = A.getSubMatrix(0, A.getRowDimension() - 1,
                                           i * A.getRowDimension(), (i * A.getRowDimension()) + (subspace - 1));
            transition.add(Ai);
        }
    }

This is easily the most hardcore indexing voodoo magic I’ve ever done.

There’s still a lot of work to do (check out our project page on github if you’re interested), but I think we’ve got some solid momentum right now. The timing will be close, but we should be able to meet our deadlines. I know it’s been a great experience for me; I’ve gleaned a much deeper understanding of the theory my own research makes use of, in addition to learning a lot about how to effectively mentor students. I would absolutely do it again. I just hope the students have learned from me as well.

Conclusion

I apologize for the lull in updates, but that will probably continue over the next couple of weeks. I spent a lovely Easter and Passover with The Lady and her family this past weekend, and school is only going to get busier as the semester wraps up. I’ll try to update when I can but I make no promises, though the upcoming Google Codejam should provide some inspiration!