Posts

During a lunchtime conversation the other day, a coworker mentioned that he was hacking in his spare time on an entry for the Netflix Prize. This got me to thinking about collaborative filtering: why had I never seen a good description of how to do it? I suspect that people who might ordinarily have a casual interest in the subject hear that there are some statistics involved, whereupon they immediately freeze in the mathematical headlights, and turn the conversation to something else, anything else. In early 2005, a researcher named Daniel Lemire published, with Anna Maclachlan, a paper with the jazzy title of “Slope One Predictors for Online Rating-Based Collaborative Filtering”. This is an important paper, because it presents a family of really simple collaborative filtering schemes. I mean really simple: there are no statistics involved, just a little bit of linear algebra. Unfortunately, because the Lemire/Maclachlan paper is aimed at an academic audience, it’s not trivial to tell by merely reading it how simple the technique it presents is, so what follows is my attempt to translate its ideas into my native language of Attention Deficit Programmerese. To make things more concrete, I’m going to present an implementation in less than 40 lines of Python (and I’ll try to explain any obscure bits of Python as I go). Cool, huh? Regardless of the underlying implementation, collaborative filters tend to try to solve the same broad problem using much the same data. ...

Some time ago, I read a Nature review (subscription required) of Doug Macdougall’s “Frozen Earth”. As is the way of such things, after I ordered my copy, the book suffered several months of neglect before I finally had a chance to pick it up. However, once I started reading it, I quickly became engrossed, and polished it off in a matter of days. The book opens with a few chapters on the history of scientific inquiry into climate change. This I consider its only weak part: it follows a formula of the past decade in popular science writing, of sketching the characters involved in the early study of the field. Many of the founders of the field that Macdougall introduces, and the controversies in which they were involved, merit multiple volumes of their own, and so the first few chapters are necessarily skeletal. I found these passages interesting, but not satisfying. The world probably has enough thumbnail sketches of Louis Agassiz at this point. Once Macdougall leaves behind the early historical narrative, the book kicks into intellectual high gear, and I found the entire rest of the book to be superb. In discussing the Missoula Floods, Macdougall touches on both the evidence for catastrophic flooding and the lengthy controversy that Harlen Bretz’s identification of the source of the Channeled Scablands engendered in the American geological community. This chapter is notable for its discussion of both the astounding physical evidence involved, the research that Bretz and subsequent generations of scientists performed, and how scientific controversy works. Another notable feature of the book is Macdougall’s discussion of the effects of climate on the development of the human species and human culture, both during early human evolution and through the written records of the past few millenia. Among the surprising topics he touches on is a study of paintings from the Little Ice Age (roughly the 13th through 19th centuries) in which someone noted light levels and counted the number of times in which the sky was represented as clear or overcast, as a proxy for weather conditions of the time. I appreciated Macdougall’s discussion of the drawing together of data from a variety of sources to try to portray a consistent and continuous picture of climate over time. Since so many of the signals upon which paleoclimatologists rely are either faint, broken up, or distorted, they look for correlations between as many sources of data as possible, and correct for numerous possible errors as they go. Macdougall discusses many of the proxies used, such as isotopic stratigraphy and measurements of many properties of ice cores; why some of the data are unreliable; and how climate scientists identify and correct errors. Most importantly, Macdougall writes clearly and engagingly throughout the book. He doesn’t shy away from complex topics, but he presents them clearly; he limits his use of jargon, and he remembers to introduce a new term by telling the reader what it means. Once I got over my dubious reaction to the first few chapters, I found the bulk of “Frozen Earth” to be intellectually exhilarating and thoroughly enjoyable.

I was shocked to read this evening about a local family that became snowbound for days in the mountains of southern Oregon; three of the four family members were rescued this afternoon. (This has apparently been big news around here, but I’m afraid I don’t follow the local news much.) The husband, James Kim, left his wife and two small children to seek help, and hasn’t been seen in over two days. It seems that there’s a good chance he’s still alive. The Kims own a store two blocks from my house, and their kids are only a few months removed in age from my own. I hope that James has found shelter and is sitting tight, waiting to be found. What an ordeal for them all. Update, 2006/12/06: James’s body was found today. My condolences to his wife, children, and friends.

I’ve used blosxom for a few years to manage my blog, and while I appreciate its simplicity and “Unix nature”, it’s not actually very usable. It’s difficult to extend; the code is impenetrable; and it’s been orphaned by its author, who has gone on to better things. For example, as I couldn’t find a simple automated way to deal with the tide of comment spam I was receiving, I ended up disabling comments entirely. Since I’d still like to be able to blog, and would prefer to host the service myself, the only realistic-looking choice to migrate to was WordPress. I’m feeling nervous about the move, as WordPress is written in PHP, and PHP has a deserved notoriety for security problems. Indeed, WordPress and its plugins have a history of security problems. But the alternatives all appear less usable and less widely supported. After taking a deep breath, I started the migration process yesterday. A nice benefit of running Fedora on my new server is that I was able to install a prebuilt package from Extras, named wordpress, and have the necessary dependencies (PHP and MySQL) installed automatically for me. A quick glance through the README.fedora file that ships with the wordpress package, and a few configuration tweaks, and I was ready to get started. The first thing that I wanted to do was import my old blog postings from blosxom. After trying other approaches for an hour or so, I wrote a small Python script to generate an RSS 2.0 feed directly from the text files that blosxom reads. This let me handle the obscure markup format I’d been using with blosxom. At this point, I hit the first serious snag. No way could I get WordPress to successfully import my carefully crafted RSS 2.0 feed, no matter how I tried. I ended up reading the WordPress source, and found a bug in the code that tries to print an informative error message when WordPress fails to import a file successfully. It tries to print the value of the wrong variable, which is undefined, and so (PHP trying to be helpful) prints an empty string: ...

Since 2003, I’d been using a Thinkpad X31 for much of my work; it was the best laptop I’d ever owned, and was really the only one I used heavily over a long period of time. It had an irresistible combination of small size, light weight, good performance (for its time), and excellent support from Linux. A few months ago, I dropped my formerly dependable workhorse on its head. It didn’t quite die, but it became increasingly erratic. It was clear that I’d jarred loose some power-related connection, because it would rarely survive a suspend-to-RAM long enough to actually resume. The last straw came when it ploughed an unexpected furrow in its root filesystem. Since I use distributed development tools, I lost maybe an hour of work in total, but I was now nervous. I couldn’t rely on it any longer. Since my employers recently got bought out, and our new corporate IT standards almost mandate the purchase of Dell hardware, I looked through Dell’s laptop line for a suitable replacement. In my ideal world, I’d have preferred a Thinkpad X60 to any Dell, but I wasn’t inclined to try to wrestle with the purchasing policies of an unfamiliar IT department so soon after a buyout. I wanted an ultraportable (i.e. small and light) dual-core system, but the closest approximation in Dell’s current product lineup is the XPS M1210. It’s too big and heavy to fit in the ultraportable category, but at 2kg (4.4lb), it will do fine. The system I ended up getting came packed with a surprise or two. It was outfitted with a GeForce Go 7400 GPU, which I had asked not to get. I had been hoping to use as many completely open device drivers as possible (the Linux drivers that NVIDIA provides are very fast, but proprietary), and I figured that the Intel 915 integrated graphics that were my other option would surely have better heat and power consumption characteristics. In spite of this preference, once the system arrived with the unexpected “bonus GPU”, I felt disinclined to kibitz with my IT department or Dell and go without a reliable laptop for an additional few weeks. I initially installed Fedora Core 5 on the laptop, as I’ve used Fedora for a long time, and like it. Although the install went without a hitch, I found that I could not suspend to memory or disk. Otherwise, the machine seemed to work well. The Intel 3945 driver worked without a problem, although it has a clumsy installation mechanism and nobody has volunteered to package it for the livna package repository yet. Indeed, the 3945 seems to have several better characteristics than the Atheros wifi hardware I’d used in the X31 (and which is still used in more recent Thinkpad laptops). With the 3945, I can associate quickly and reliably to every wireless network I’ve tried, using NetworkManager. The Atheros chip wouldn’t talk to encrypted wifi networks at all. Also, NetworkManager-on-Atheros took about 40 seconds to associate to unencrypted networks, and would drop an association every so often for no apparent reason. Ugh. Finally, the 3945 reports sane signal strengths, while Atheros seems to be measuring some other strange characteristic of a signal that never goes above 50%, even if you’re sitting two feet from an access point. From the perspective of wanting open drivers, neither wireless chipset is ideal. Much of the madwifi driver is proprietary, even though it lives in the kernel, while the 3945 requires both a binary firmware blob and a proprietary userspace daemon that enforces airwave regulation compliance. Out of curiosity, I installed the proprietary NVIDIA drivers, and whatever power and thermal management they perform improved my battery life from about five hours to over six. This impressed me. Unfortunately, there was little I could do about the lack of suspend support in FC5. At least part of the problem is that stock kernels don’t power-manage the Intel SATA controller, so it is guaranteed to die during suspend or resume. Just as I was rolling up my sleeves to install a custom patched kernel and debug it, I noticed that recent Fedora rawhide (testing) kernels incorporate exactly the patch I needed. I upgraded to Fedora Core 6 test 1 without a hitch, using yum; installed a rawhide kernel; rebooted; and I could suspend, both to RAM and to disk! And all without having to do any “real work”. The only downside to the upgrade has been that NVIDIA hasn’t updated its proprietary drivers to handle the newest X.org ABI or kernel build infrastructure, so they don’t work with fc6t1; another good reason to prefer not to use proprietary drivers. For now, at least, I’m back to running the open nv driver for graphics. I can’t discern a speed difference for the kind of stuff I do (lots of terminals, Emacs, and Firefox), and it’s nice to be running with a free driver, but I miss that extra 20% of battery life. Anyway, after all that blather, what are the actual specs of the machine? ...

Having not set hand or foot on an honest-to-god rock in well over a year, I was full of uncertainty last weekend as Tony and I left San Francisco, bound for four days of climbing near Bishop. A few flurries of snow in Tuolumne Meadows forced us to detour over Sonora Pass. Not having passed through that portion of the Sierra Nevada before, I was impressed by both the beauty of the scenery and the quantity of climbable alpine-style granite that seems to receive little traffic. On the steep descent towards Highway 395, we were surprised to see a number of groups of heavily-armed troops lining up for food in the few relatively flat areas off the sides of the road. Their presence lost its brief at lower altitude, when we drove past a US Marine winter warfare training camp. Even with the miles added by the diversion, we completed the drive in a respectable six and a half hours. Friday morning began with the long scramble down the blocky central gully into the Owens River Gorge. On my first visit as a neophyte climber, around seven years ago, I had found the descent intimidating. Subsequent experience has relegated it to “comparatively trivial” status in my mind, as it would require considerable creativity or astounding bad luck to kill oneself on the descent. The only feature that remains constant across the years is that the descent is guaranteed to turn the quadriceps of your ill-seasoned weekend warrior into a twitching rubbery mass. Starting the first day of a trip in such a state after a long furlough makes for unnecessary excitement, as events at the Great Wall of China quickly demonstrated. China Doll (5.8) is a typical Owens climb of “moderate difficulty”. What “moderate” means in Owens is that the climbing is at a low angle, the holds are mediocre, and traffic has polished everything you might prefer to trust to a slick, confidence-sapping sheen. After quivering through three bolts to the crux, I found my will to continue sapped, my arms pumped, and my ability to think clearly enshrouded in fog. I backed off, took a break while Tony led the route, and re-led it cleanly a few minutes later. The poor start didn’t cloud the rest of my day, though, as we spent the following five hours treating the Wall area as an almost empty gym. The snow over the Sierra must have kept a number of climbers at home, as I have never seen the Bishop area so empty of climbers. It was wonderful to have the run of every climb we wanted for three solid days. On the morning of day two, we took ourselves to the Buttermilks, the famous (among boulderers, anyway) granite boulders east of Bishop. My outdoor bouldering experience is minuscule, so I found the tiny features and harsh crystals of the Buttermilks absolutely overpowering. I thrashed through perhaps two easy problems during our visit. It’s a beautiful area, but not a good destination for the casual climber, I think. Much more to my taste were the Happy Boulders, which we visited after lunch. The volcanic rock features many newbie-friendly problems where you can gain a bit of experience without feeling like you’re wearing down your fingertips on a coarse cheesegrater. Even here, I was stumped by mere V2-level problems, as my poor condition and lack of outdoor bouldering know-how conspired against me. This failed to dampen my enthusiasm, as I simply dropped back to overhung routes with huge holds. On the evening of the second day, we attended a fund-raising screening of the Reel Rock Tour, a pair of climbing movies made by Josh Lowell (“Dosage IV”) and Peter Mortimer (“First Ascent”). Dosage was a moderately entertaining formula film (being the fourth in a now-annual series), featuring many of the “usual suspects” climbing hard routes. The only eye-opener (for me) was a sequence involving ridiculously talented teenagers free soloing hard routes over water on Thailand’s limestone pinnacle islands. Wow. Mortimer’s “First Ascent” was a much more personal movie, as Mortimer blatantly inserted himself into the narrative, making it a highly engaging and entertaining show. We returned to the Gorge on the third day, focusing on more difficult routes in the Pub Wall area. As my endurance is negligible, Tony led every route (taking some fine falls), and I did my game best to follow them without floundering too much. The highlights for me were Hammered (5.11b) and Hardly Wallbanger (5.10c), both of which feature steep climbing of stellar quality. For a small town, Bishop has surprisingly good food. I’ve long been a fan of Erick Schat’s Bäkkery (one of the better bakeries I’ve ever visited) and the Whiskey Creek restaurant. Another of the great pleasures of visiting the Eastern Sierra is Wild Willy’s hot spring next to Crowley Lake, where we had a good soak. The old trail has recently been replaced by a boardwalk to prevent damage to the surrounding salt flats, and it remains an incredibly pleasant place to spend a few hours on a chilly October evening. Had we conceived of the trip more than a few weeks in advance, I might have trained for it, and hence been able to climb at a more respectable level, but what a fantastic weekend it nevertheless was! My previously flagging enthusiasm for pulling plastic at the climbing gym has received a shot in the arm as I remember why I do it. Right, back to daydreaming about when the next climbing trip might happen…

I spent a few hours on Sunday putting together a web site for my friend Carole Moore, a talented San Francisco painter. This was my first time paying any attention to web design in years. All of my prior knowledge dated back to HTML 3.2, circa middle-dot-com-boom. How pleasant it was to discover that I no longer need to use endless nested tables to create a decent-looking page layout! And that cascading style sheets are quite decent to work with. And, of course, I am relieved that my knowledge is no longer so embarrassingly rusty. ...

Among the line-up of trendy ethnic restaurants in San Francisco’s Mission district is Dosa, which has been open for about nine months. Dosa purports to offer up South Indian food, which only vaguely resembles the North Indian fare usually served at Indian restaurants. As Silicon Valley is bursting with excellent South Indian restaurants, but San Francisco was until now bereft of them, I was quite excited when Dosa opened, and wasted no time in paying it a visit. ...

I read in Bill Bumgarner’s blog that Dell has released a new model in its XPS line, the M2010. It’s not somethhing one could plausibly refer to as a laptop, due to its weight of 18.3lbs (8.3kg!) and 20" screen. Being a curious sort, and owning the M2010’s tiny cousin, the M1210 (the weight of which is a feathery 23% that of the M2010), I visited Dell’s web site to try to configure a system and see what it would cost. ...

I’m giving a talk at OSCON in Portland this week; the title is “Painless maintenance of local changes to fast-moving software”. The content is about how managing and developing patches with Mercurial Queues will make you a happier person and straighten your teeth while you sleep, all for free. The talk is in room F150, on Wednesday, July 26, at 2:35pm. It’ll be a lot of fun.