Lukas Biewald

A post on God Plays Dice and Ars Mathematica directed me to a new website, Rejecta Mathematica that puts rejected papers online.

They give the following rationales for publishing rejected papers:

* “mapping the blind alleys of science”: papers containing negative results can warn others against futile directions;

* “reinventing the wheel”: papers accidentally rederiving a known result may contain new insight or ideas;

* “squaring the circle”: papers discovered to contain a serious technical flaw may nevertheless contain information or ideas of interest;

* “applications of cold fusion”: papers based on a controversial premise may contain ideas applicable in more traditional settings;

* “misunderstood genius”: other papers may simply have no natural home among existing journals.

I think the first reason is very useful for AI. It always seemed to me that there is a general word of mouth consensus on what techniques don’t work but it’s hard to pin down and negative results are rarely published. I wasted a lot of time working on things that I’m sure people have wasted their time on before and after, so if this site takes off it could be great. We often joked about how there should be a journal of negative results.

On the other hand you could easily see this site filling up with nonsense. I liked this part of the FAQ:

Will you publish anything?

No, we select papers based on several loosely defined criteria. In short, we aim to publish a variety of interesting papers that allow some opportunity for learning. Specifically, we do not see much value to the community in papers that were rejected solely based on their incomprehensibility. While we do not anticipate accepting such papers, we would encourage any interested party in starting the Journal of Impenetrable Results to give them a home.

As someone with a strange love of Perl, a bitter forced education in Latin, and a ton of coworkers that love crazy ass useless languages, I’m surprised that no one pointed me to Perligata. This might be the best fake language I’ve seen. The fact that you conjugate variables to manipulate them is pretty funny.

Here’s a few sample tables:


Perligata Number, Case, and Declension Perl Role
========= ============================ ==== ====
nextum accusative singular 2nd $next scalar rvalue
nexta accusative plural 2nd @next array rvalue
nextus accusative plural 4th %next hash rvalue
nexto dative singular 2nd $next scalar lvalue
nextis dative plural 2nd @next array lvalue
nextibus dative plural 4th %next hash lvalue
nexti genitive singular 2nd [$next]… scalar index
nextorum genitive plural 2nd $next[...] array element
nextuum genitive plural 4th $next{…} hash entry

Perligata Number, Mood, etc Perl Role Context
========= ================= ==== ==== =======
countere infinitive sub count defn -
counte imperative sing. count() call void
countementum acc. sing. resultant count() call scalar
countementa acc. plur. resultant count() call list
countemento dat. sing. resultant count() call scalar lvalue
countementis dat. plur. resultant count() call list lvalue


I was thinking about another interesting little puzzle on the train:

You have an m by n chocolate bar. You break it into two (integer sized) pieces along a vertical or horizontal line. Then you break either piece again, and so on until you have all 1×1 pieces.

Prove that all methods of breaking take the same amount of breaks until you’re done.

There’s a trick to doing a really easy proof which I’m embarrassed to say took me the whole train ride to figure out. If you have some spare time this is kind of a fun little puzzle to think about.

Anyway, I gave this puzzle to my old intern John Le and he proved it by induction in about five minutes. You can show that all breaks have an invariant number of future breaks required. There’s a small number of cases and the algebra is a tiny bit messy but it’s pretty easy.

The whole thing reminded me of that story about the puzzle of a dog running back and forth at velocity v between two people walking towards each other at velocity w starting distance d apart. The question is how far the dog runs before the people meet. According to folklore someone asked John Conway that puzzle and he just summed the infinite series in his head. It turns out the infinite series is not very complicated. (I hope I got the mathematician write, someone correct me if I’m wrong… )

I feel like there’s a life lesson here :).

The comment to my Netflix prize post inspired me to dig up a paper I’ve always liked a lot, Combining heterogeneous classifiers for word-sense disambiguation, where Chris Manning assigned his students to build a word sense classifier as a class project. He then used the output of each one to build an ensemble classifier and entered it in SENSEVAL-2 where it was one of the best performing classifiers.

I’ve never seen a company take the approach of having multiple teams/people build classifiers independently and then combine the results, but it seems like a fairly promising approach. Contrary to the Netflix comment, I actually think this might be a pretty hard thing to publish in proportion to the effort involved. This might account for why people don’t do this kind of thing very often.

Interesting article on Bit Player about naming conventions for complexity classes and in particular, NP.

My favorite part is a random side node at the end of the article that quotes Knuth from a paper in 1974:

I’m willing to give a prize of one live turkey to the first person who proves that P = NP.

My friend told me a great math/visualization puzzle over the weekend. I feel like it has to be well known, but I hadn’t heard it before.

Can you pass a cube through a hole in a smaller cube?

From the framing of the problem, the answer is obviously yes so I guess the real question is how do you do it. An interesting follow up question is for a cube of edge length N, how small of a cube can you pass it through?

Hmm… as I write this I wonder if “pass through” has to be defined. This definitely isn’t a trick question.

The Netflix prediction contest is over and no one won the big prize, but they got pretty close (8.5% improvement when 10% improvement won the big prize of a million dollars).

It’s neat that in the end the top teams combined forces and the best engine ended up being an ensemble of the top predictors.

It was somewhat surprising to me that the teams were able to make steady, nearly linear progress on the metric for an entire year. I wonder how feasible the 10% improvement really is.

This graph from the winning BellKor team charts the leader’s score over time:

I read this excellent Slate review of the real Nintendo Mario sequel that you can now buy for the Wii. I immediately went home and downloaded it.

This is my favorite quote from the article:

But the Real Super Mario Bros. 2 isn’t just hard—it’s “difficult,” like a book or a movie that initially rebuffs you but becomes rewarding as you unlock its secrets. As a standalone game, it would be a disappointment, too challenging and too impenetrable. But as a reflection and inversion of one of the few titles in the gaming canon, it provides a sort of meditation on game design and player expectations, and how to flout them. I only wish I’d had a chance to play it in 1986.

After a few enraging hours of playing, I completely agree with everything in the review. It’s interesting to go back to a time before many of the videgame metaphors that we take for granted.