## Tuesday, November 08, 2005

### The curse of unknown dimensionality

Maybe my professor read this Notional Slurry post, or at least the bit that reads:

"Some of these problems can be answered with a quick and simple Google search and some writing. Some would make good Masters Thesis projects. Some have one right answer; some have no right answer; some have many. Some require explanation, some require programming, some require mathematics, some require historical background, some require number crunching, some require experimentation, some require intuition, some require asking the right person, some require advanced domain skills from outside our department. Some are trick questions; some are so obvious you’ll imagine they’re trick questions; some are inherently time-consuming; some have hard and easy ways to solve them. Many are ill-posed, and need clarification. Some are problems you should already know how to answer. Some are problems you might not be able to answer by yourself when we arrive at the final exam."

... and, inspired, decided to try it out and had it backfire.

I say this because last night the following little note, from my professor, regarding the latest homework assignment, appeared in my inbox:

Problem 2.1 turns out to be harder than expected (i.e., none of us knows the answer). So write down what you understand about it, and don't worry if you don't get it. Extra points to anyone who does!

In other words, this problem apparently breaks the contract that's generally implicit in homework problems, namely that a) the professor knows the answer and b) students should be able to figure it out within the time alloted, without requiring them to be von Neumann.

I can't say I was all that surprised because several of us [students] spent two hours talking to one of the TAs for the class and it became clear that nobody, including the TA, knew definitively what the answer was [or at least how to prove it]. At least the prof had the decency to tell us this a couple of days before the problem set is due.

[For those of you so inclined, the question is: "What is the VC dimension of a single rectangle in the plane, with the freedom to decide whether the inside is positive or negative, and without requiring the rectangle to be aligned with the axes ?". The current money is on "at least 7, and less than 10".]

Son1 said...

"This problem apparently breaks the contract that's generally implicit in homework problems, namely that a) the professor knows the answer and b) students should be able to figure it out within the time alloted, without requiring them to be von Neumann."

Dude, it's MIT man :-). The profs here do this kind of stuff *intentionally* (at least, sometimes -- clearly not the case with your ML class here...)

My algorithms class definitely had "open" questions on the homeworks. Although they were marked as "extra credit."

6:25 PM
Bill Tozier said...

This happened in my first-year intro chemistry class, once upon a time. Something about temperature changes during the expansion of a balloon, is all I recall. Sheepish grins from the professor when it became clear that the post-docs and he had no clue whatever.

7:29 PM
Alex said...

Oh, there are extra credit questions too: "What about 2 rectangles in the plane ? What about k rectangles ?". Maybe there's something that allows easy generalization from one to many, but somehow I doubt it ...

8:12 PM
Kristofer said...

I understand your feelings, but if he had told you that he didn't know how to solve it would you have tried as hard as you did now?

Kristofer
Kristofers' computational biology blog

2:32 AM
Alex said...

Well, I didn't really try very hard to begin with, so I'm not upset =). I just tried the brute-force approach until I got tired of it [which took all of about 5 minutes], decided I didn't really care enough to try getting more sophisticated and wrote down what I had. Other people I talked to hauled out all kinds of heavy mathematical artillery like convex hulls etc and apparently spent ages on it.

12:53 PM