lederhosen: (Default)
2016-10-16 07:45 pm
Entry tags:

Tinkering #2: The Play's The Thing

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:


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.
lederhosen: (Default)
2016-10-16 12:47 am
Entry tags:

Tinkering: using AMPL/Gurobi to allocate parts in a play

Now and then Rey and I do play readings with friends. Usually there are rather more roles than there are readers, so "one man in his time plays many parts", which works fine until you end up playing two roles in the same scene and having to have an extended conversation with yourself.

So you want to cast roles in a way that avoids that kind of overlap, and you probably also want to make sure the different readers each get a decent share of the lines. You could do this by hand, but since I'm currently teaching myself AMPL, I thought it'd be a fun challenge to program a solution.

AMPL (A Mathematical Programming Language) is similar to MiniZinc, which I posted about a while back: it's designed for specifying optimisation/constraint problems and then passing them to a solver of one's choice.

It's very much a declarative language: instead of giving the computer a set of steps to follow, you give it a set of requirements and then let it figure out how to satisfy those requirements. (This still feels like magic to me.)

AMPL and other optimisation languages usually take input in two parts: a "model" which is a generic description of the problem and requirements, and "data" which defines a specific instance of the problem.

So, here's some AMPL code:

The model )
The data: )

In the unlikely event that anybody other than me actually wants to use this, you can download a free demo from AMPL (unlimited duration, restricts to about 300 variables i.e. number of actors x number of parts should be less than 300).

The demo comes bundled with a selection of top-notch and open-source commercial solvers, all free to use subject to that size restriction. By default it uses the MINOS solver, which is nice for generic nonlinear problems but doesn't handle integer constraints; since those are important here you'll want to use "options solver gurobi" (or cplex or xpress).
lederhosen: (Default)
2012-12-01 07:05 pm
Entry tags:

Red Pen Of Truth, part n+1

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.


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.
lederhosen: (Default)
2012-09-22 09:51 am
Entry tags:

goodbye productivity

Found the source of the Escher .gif I posted yesterday.

lederhosen: (Default)
2012-08-04 12:13 pm
Entry tags:

In which I am ineptly ept.

Managed to fix* the programming problem for Tech Apps and got a very grateful phone call - apparently they'd been wrestling with this for weeks. I was coasting on a wave of "I AM A TECH GOD" until I remembered that I'd just spent six weeks procrastinating on getting my "broken" headphones replaced, before realising that I'd plugged them into the wrong port. So yeah.

Then almost called helpdesk to report a broken monitor before figuring out that if I unplugged it and replugged it, the problem went away. At least I did figure this out BEFORE calling them.

*FCVO "fix". TLDR version: they changed their code and couldn't figure out why the new results were slightly different from the old one. After staring at ~150 pages of code for two days and looking up the mathematical technique involved I was able to tell them: "probably not a bug as such". The old code calculates an approximation; the new one calculates an approximation for the same data via slightly different methods, so there's no guarantee that it'd give the same results.

Problem is that figuring this out requires (a) understanding of the maths involved and (b) familiarity with IML, which isn't exactly a Top Ten programming language.
lederhosen: (Default)
2012-03-14 08:15 am
Entry tags:

A problem for Pi Day

An interesting little probability problem:

Suppose we want to divide the interval [0,1] into 100 sub-intervals (wrapping around in a ring, so 1 is 'glued' to 0). We choose to do this by generating 100 random numbers between 0 and 1 (uniform distribution, independent of one another), sorting them from smallest to largest, and using them as the borders of these intervals.

For instance, if our 100 random numbers turned out to be {0.025, 0.030, 0.038, ..., 0.971, 0.988} then our intervals would be [0.025, 0.030) and [0.030, 0.038) and ... and [0.971, 0.988) and then the 'wrapping interval' [0.988,1]+[0,0.025).

NB: it doesn't really matter for this problem, but in case you're trying to remember notation, square brackets mean the endpoint is INCLUDED, round brackets mean it's not. So the interval [0.2,0.3) would contain 0.2 but not 0.3.

Between them, these 100 sub-intervals completely cover the space between 0 and 1, with no interlap.

Two questions:

(1) What is the average length of one of these intervals?

(2) What is the average length of the interval that contains 1/pi?
lederhosen: (Default)
2011-11-18 07:39 am
Entry tags:

Machine learning

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.
lederhosen: (Default)
2011-04-25 10:42 am
Entry tags:

Problem solution

The problem I posted a couple of days ago:

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?

Solution below the cut. )
lederhosen: (Default)
2011-04-23 12:40 pm
Entry tags:


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.
lederhosen: (Default)
2010-11-14 01:55 pm
Entry tags:

A modest proposal for parapsych research

Once upon a time, the usual explanation for parapsychology "findings" was bad experimental technique (subjects were getting cues as to the correct answer, that sort of thing). Sometimes due to deliberate dishonesty, often because experimental design is hard.

These days, experimental technique has tightened up a lot, due largely to sceptics and partly to those parapsych researchers who think they've got something and want to be taken seriously.

This has established that if psi effects exist, they're weak*. If we had psychics who could predict the outcome of a coin-toss with 100% accuracy - or even 55% - one of them would long ago have claimed James Randi's money. To detect weak effects, you need to run very large experiments containing thousands or millions of trials, and perhaps apply sophisticated statistical techniques to analyse the data.

The problem with this is that with a large data set and a lot of choices about how to perform your analysis, it's awfully easy to cherry-pick for significance. So, my suggestion is:

Every time a human subject generates a data point (makes a prediction, etc etc), we should use a random number generator to generate, say, a thousand fake versions of the same data point, all consistent with the null hypothesis. From these, we form one real data set, and a thousand fakes.

Stats analysis is then performed blind - the statistician decides on appropriate analysis techniques without knowing which is the real data set. The decision on journal publication is also made blind; only after the article is irrevocably committed to publication does anybody get to find out whether the 'significant' data set identified is the real one.

This wouldn't fix all problems with parapsych research (and depending on the nature of the data, it might take some work to generate fake data that can pass as the real thing) but I think it would be useful in many cases. This needn't be restricted to parapsych; I'm pretty sure there are other fields that would benefit from this too.

*I'm not inclined to dignify the "we have strong psi powers that completely vanish under fraud-proof conditions" argument with a response.
lederhosen: (Default)
2010-11-13 01:14 pm
Entry tags:

Beaten to the punch

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.
lederhosen: (Default)
2010-10-17 09:13 am
Entry tags:


Benoit Mandelbrot. Whose work was rather more important than giving the world some gorgeous screensavers and wall posters.
lederhosen: (Default)
2009-05-14 04:20 pm
Entry tags:

The perils of fitting

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...)
lederhosen: (Default)
2009-04-21 10:18 pm
Entry tags:

(no subject)

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".
lederhosen: (Default)
2009-04-02 11:29 pm
Entry tags:


Been meaning to post this one for a while (I didn't forget and post it already, did I?) It caught my attention because the end result is very similar to some of the stuff that came up in my work last year, though for somewhat different reasons.

Strong profiling is not mathematically optimal for discovering rare malfeasors.

The result, in a nutshell: suppose you're looking for Bad People via random screening, and you know that certain types of people (nationality, age, gender, whatever) are ten times more likely to be malfeasors than other people.

The natural response would be to screen the first type of person ten times as often ('strong profiling')... but it turns out that this is actually no more efficient that screening everybody at random with the same probability. When malfeasors do fit the stereotype, strong profiling lets you find them slightly faster; when they don't, strong profiling takes a lot longer to find them, because your efforts are concentrated too much on the wrong people. It turns out that the optimal solution here (ignoring moral considerations and the possibility that people will change behaviour in response to your strategy) is somewhere in between the two - 'weak profiling'.

(I should add that this result is for one specific formulation, as described in the paper; it could easily be argued that some scenarios don't fit this particular mathematical model. But it's still interesting as an illustration that putting too much faith in your information can be a bad idea.)
lederhosen: (Default)
2008-12-17 11:21 am
Entry tags:

Why would you do it this way?


"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.
lederhosen: (Default)
2008-11-08 11:55 am
Entry tags:

African Americans, Prop 8, and sampling theory

(Not sure whether to use my politics icon or my maths icon for this one.)

Since a couple of y'all have been discussing this: there has been much mention of the alleged fact that 70% of African American voters in California voted for Prop 8. But how reliable is that number? Read more... )