lederhosen

So after yesterday's post I thought I'd extend it a little and test my code on a full-sized problem: casting Hamlet.

This helpful site lists the characters present in each scene, although you have to be a little careful - Claudius is also listed as "King", and Gertrude as "Queen". In some cases it just lists groups ("Assistants", "Clowns", etc.); for this work I've just assumed there are two of each, though you'd want to check that. This results in 39 parts.

I entered that data, along with some made-up numbers for how many lines each part has; the exact values don't matter too much, as long as there's enough info to distinguish between major and minor parts. I also tweaked it so that minor characters are assumed to have 5 lines each unless specified otherwise, which saves on data entry.

Unfortunately the demo license for AMPL doesn't allow me quite enough variables to solve this problem. (I could probably reformulate it to reduce it to one variable per part, plus a few extra, but that would be a bit messier.)

Not to fear, there's another option: NEOS. NEOS is a web service that allows anybody to submit optimisation jobs for free, without a size limitation... and it accepts AMPL format. Having tested and debugged my code on a smaller problem, I can then add the full Hamlet data and submit it to NEOS at this page.

I upload three files:

( castingmodel.mod )

( hamlet.dat )

Last, a commands file to tell NEOS what output I want:

casting_commands.txt:

solve;
display Casting;

I then enter my email address and click "submit". In a minute or two, NEOS shows me the results, which you can view for yourself, and also emails me a copy. (A result of "infeasible" would indicate that it's impossible to satisfy the problem as specified, either because of some inconsistency within the constraints or because there aren't enough actors.)

The output shows some information about the solution process, and at the bottom it gives the final casting:

Art: Guildenstern
Bea: Barnardo, Clown 2, English Ambassador, Player Queen, Reynaldo
Chris: Hamlet
Derek: Horatio, Player Lucianus
Eve: Doctor of Divinity, Fortinbras, Laertes Follower 2, Player King
Frank: Ophelia
Greg: Polonius
Hugh: Gertrude
Irene: Francisco, Gentleman, Lord2, Osric, Voltemand
Jo: Claudius
Kate: Clown 1, Rosencrantz
Luke: Laertes, Player Prologue
Meg: Captain, Cornelius, Laertes Follower 1, Lord 1, Sailor 2
Ned: Attendant 2, Ghost, Lucianus
Oli: Attendant 1, Guard, Marcellus, Messenger, Sailor 1

This looks pretty sensible overall: most actors either get one big part, or a bunch of small parts, and our choices for Hamlet and Laertes satisfy the fight training requirement.

Dear story problem people: I want to know what plane you have that can cruise at 40km.

Also, if you're asking a question about rolling "two fair dice", it would probably be a good idea not to accompany it with a stock photo that shows dice with a 6 on EVERY FACE.

Also:

The probability of a boy having blue eyes is 4/11 and blond hair is 2/7 from a group of students. A boy is chosen at random from that group. What is the probability the boy is blue-eyed and has blond hair?

...I don't actually know what the answer is, but I'm pretty sure it's not the 8/77 that you're looking for there.

Answers to yesterday's pi riddle behind the cut.

( Read more... )

Thing 1: I've been doing the free machine learning e-course from Stanford. I can thoroughly recommend it* and if you missed it there's another offering in January.

Thing 2: Stanford are also offering a whole bunch of other free online courses. The PGM one looks like it might be work-relevant, and I think I might do the game theory one on my own time.

Thing 3: The course forums are pretty good, in general, but there's this one guy who makes me cry every time I see his comments. In this case, the OP produced a graph that looked good near the fitting points, but produced negative results (nonsensical in context) elsewhere**. Response, in the original punctuation:

HOLY FLOW CHARTS....I have never have seen negative Water Flow Across a DAM... When the Level Transmitter shows a ZERO LEVEL....you only get SPLASH flow across the Dam (wind and waves cause Splashing). A secondary flow sensor should pick up this random flow. When the Level Signal goes positive you should get a flow signal that follows Weir Flow Charts...I think it is a 3/2 or 5/2 power or something in between depending on how it is constructed.

Modelling it with a Chart showing NEGATIVE FLOW would get you FIRED...recommend erasing everything < than "ZERO" FLOW...the Stanford computers might pick that up as an ERROR in the CALCULATIONS...

Translated into English: "You should censor the results that are obviously wrong, to make the graph look better, without considering what those results might imply for the accuracy of the other results that don't LOOK wrong."

...and that, right there, is a "I would never ever hire you" button.

*although I still don't like their explanation of back propagation - not sure whether I've misunderstood it, or whether it's just a bad explanation of something that should just be "calculate the gradient of the cost function".

**Kids, JUST SAY NO to extrapolating from eighth-order polynomial fits. Please.

Working through boxes. Today I got to some of my old Maths Olympiad material. I feel sad to throw that stuff out - it was one of the biggest things in my school life - but there's way too much to keep it all.

One of my favourite competitions was Tournament of the Towns, which was run from Russia. We'd sit down, attempt the problems, and then our efforts would be sent off to Russia by sea-mail. Then they'd be marked, and sent back (again by sea-mail) so it would be about six months before we found out our results. (Looking at my old papers, I feel sorry for the poor markers who had to read my utterly awful handwriting. One of the best things I ever did was give up on cursive. And English wouldn't even have been their first language.)

It had a couple of nifty features: if you did well you got a diploma in Cyrillic (I have a few somewhere around), and the problems had a different flavour to the ones I got in most Australian/US competitions. The Russian ones tended to be quite simple to state, but no easier to solve.

The marking scheme was pretty simple: IIRC it went 0 for no attempt, - for efforts towards a solution, ± for a mostly complete solution, and + for a complete solution. But occasionally they'd give out a +! for a solution they really liked (i.e. better than theirs). This was one of the things I liked about TotT; most contests, a proof was a proof and if it had no holes you got full marks. But for me, an elegant proof that cuts to the heart of the matter is worlds away from a plodding grindy one, and occasionally I managed to get that prized +!.

Anyway, here's one I found today, from the November 1990 junior paper:

An 8 by 8 square is painted white. We are allowed to choose any rectangle consisting of 3 of the 64 (1 by 1) squares and paint each of the 3 squares in the opposite colour (the white ones black, the black ones white). Is it possible to paint the entire square black by means of such operations?

Anybody want to try it? I'll post up my solution in a couple of days.

So, this story about Daryl Bem's alleged experimental evidence for precognition has been doing the rounds.

I was going to launch into a lengthy post about the problems with this experiment, but four Dutch researchers have already produced a very good response that covers all the points I was going to make and several more.

In brief: when you have a large long-running experiment and you get to chose the analysis techniques, exclusion criteria, and the stopping point after looking at the results, it is really easy to find 'significant' patterns.

One of my favourite demonstrations of this is Brendan McKay's 'Bible Code' work, in which he shows how 'Moby Dick' predicted the assassinations of Indira Gandhi, JFK, Rene Moawad, Leon Trotsky, MLK, Yitzhak Rabin, and others.

One of the standard techniques throughout science (well, a whole family of techniques really) is 'fitting'.

The way it goes is like this: we have something that we consider important (cost, blood pressure, whatever) that's affected by a whole bunch of other things (how far we drive, how many people we employ, how much the patient gets of what drugs - we call these "predictive variables").

The relationship is complex enough that we can't just predict it from first principles, so what we do instead is we take a bunch of observations in which we record both the predictive variables and the results. Then we try to come up with a mathematical model that matches our observations.

For instance: suppose I go to the shops and buy myself an apple and an orange. The receipt isn't itemised, but the total cost is $1.50. Next day I go back, and buy myself an apple and two oranges, and it costs me $2.00.

From this, you might reasonably conclude that an apple costs $1.00 and an orange costs 50 cents. If I was buying a dozen different things every trip, you'd need more observations before you could figure out prices (at least one for each predictive variable we're considering). You would probably also want to use a computer to work the numbers, but there are plenty of packages that will do that - it's really quite easy to do, which is part of why it's such a popular technique.

Unfortunately, like many easy things, it's a little too good to be true. The catch is that while what we want to do is predict the future, what we're really doing here is describing the past. Up to a certain point, that's useful - we can expect the future will behave something like the past. But it's possible to overdescribe the past...

On Monday, I go to a new greengrocer and buy myself an apple and ten oranges, for a total of $6.00. The next day I buy myself an apple and *nine* oranges... and it costs me $6.10. What do you make of this?

Under the 'fitting' approach, there's only one way to interpret this: apples cost $7.00, and oranges cost minus ten cents each. WTF?

In fact, the explanation is much more reasonable: apples still cost about $1.00 each, and oranges cost about 50 cents. But this relationship isn't exact - oranges are actually sold by weight, and the ones I bought on Tuesday were a little heavier, so they cost a little more - about 56 cents each.

The problem here is that we forgot that the relationship between predictive and output variables is not exact - we don't know all the factors that affect our output variable. The more predictive variables we have, the easier it is to mistakenly credit them with effects that are really due to factors outside our knowledge. (You can see a LOT of this happening in electioneering or sports coverage - see Edward Tufte's debunking of 'belwether districts'.) Past a certain point, over-fitting becomes a sophisticated form of superstition - one to which scientists are especially susceptible.

(Jotting this down because I suspect I'm going to have to deal with these concepts at some length in the near future...)

It's probably a sad thing that my first reaction to this theoretical ecology of vampires is neither "who cares", nor "wow, that's cool", but "wait, I think there's an error in that first expression".

http://www.citeulike.org/user/ima/article/3351944

"In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of practical importance due to a European industry norm which requires car manufacturers to state the trunk volume according to this measure..."

The article goes on to note that this is an NP-hard problem.