For a while I've been interested in how you could select the order in which vocabulary is learnt in order to maximise one's ability to read a particular corpus of sentences. Or more generally, imagine you have a set of things you want to learn and each item has prerequisites drawn from a large set with items sharing a lot of common prerequisites.
As an abstract example, imagine you want to be able to read the "sentences":
{"a b", "b a", "h a b", "d a b e c", "d a g f"}
where we assume you must first learn each "word". Further assuming that all sentences are equally valuable to learn, how would you order the learning of words to maximise what you know at any given point in time?
One approach would be to learn the prerequisites in order of their frequency. So you might learn in an order like
<a, b, d, c, e, f, g, h>
However, had we put h before d, we could have had an overall learning programme that, although equal in length by the end, enabled the learner, at the half-way mark, to understand three sentences instead of just two.
To investigate this further, I needed a way to score a particular learning programme and decided that one reasonable way to do so would be to sum, across each step, the fraction of the overall set of sentences understandable at that point.
I then needed an algorithm that would find the ordering that would maximise this score.
After the quick realisation that the number of possible learning programmes was factorial in the number of words, it dawn on me that this was essentially a travelling salesman problem.
So my sister, Jenni and I wrote a Python script that implements a simulated annealing approach to the TSP. We then applied it to the above contrived example. Sure enough, it found a solution that was better than a straight prerequisite frequency ordering.
I then decided to try applying it to a small extract of the Greek New Testament (which, of course, I have in electronic form, already stemmed). So I ran it on the first chapter of John's Gospel. 198 words and 51 verses. A straight frequency ordering on this text achieves a score of 48 so that was the score to beat.
My first attempt, it didn't even come close to that. What a disappointment! Jenni and I wondered if it was just the initial parameters to the annealing model. So we increased the number of iterations at a given temperature to 50 and lowered the final temperature to 0.001 (keeping the initial temperature at 1 and the alpha at 0.9).
Success!! It found a solution that scored 82.94. The first verse readable (after 27 words) was John 1.34. John 1.20 was then readable after just 2 more words and John 1.4 after another 7.
I decided to try different parameters. With 100 iterations per temp, a final temp of 0.0001 and a few hours, it achieved a score of 91.59 (and was still increasing at the time). This time the first verse readable was John 1.24, after only 8 words; then John 1.4 after another 9; John 1.10 after 4; and both John 1.1 and John 1.6 after another 4 and John 1.2 just 1 word after that.
Overall a very promising approach. I doubt it's anything new but it was fun discovering the approach ourselves rather than just reading about it in some textbook. The example I tested it on was vocabulary learning, but it could apply to anything that can similarly be modelled as items to learn with prerequisites drawn from a large, shared set.
The next step (besides more optimised code and even more long-running parameters) would be to try to work out how to model layered prerequisites - i.e. where prerequisites themselves have prerequisites - to any number of levels. I haven't thought yet how (or even whether) that boils down (no pun intended) to a simulated annealing solution to the TSP.
UPDATE (2005-08-03): Now see Using Simulated Annealing to Order Goal Prerequisites.
by : Created on Nov. 26, 2004 : Last modified Aug. 3, 2005 : (permalink)
This blog is nine months old today.
Every couple of days, I find a new person that has added me to their blog roll. I can't tell you what a nice feeling it is knowing that, not only do people read your blog, but they are willing to admit to it publicly :-)
I still worry that my journeyman of some lack of focus...err...breadth of topics means that each post is completely irrelevant to 90% of readers—the filmmakers tracking the progress of Alibi Phone Network likely don't care if a school dance pairing is a bijection or not.
But I think I'll still just continue to blog about things that interest me and things that I'm working on. After all, pretty much every single topic I've written on has put me in contact with some interesting person that I've learnt and am continuing to learn new things from.
So thanks for reading!
by : Created on Nov. 26, 2004 : Last modified Feb. 8, 2005 : (permalink)
Okay, I didn't get to it last weekend but today I finally managed to do an edit of Alibi Phone Network that cut around the line we didn't like as well as fix a bunch of other little things.
The latter included some sound level normalization and removing a sigh noise that didn't fit because the audio was from a different take than the video and in the video you couldn't see any sighing.
There are a bunch of places where I used audio from a different take than the visuals. Mostly it's during an over-the-shoulder shot during a dialog. The clearest dialog is usually recorded from the person facing the camera, so when the person with their back to the camera is speaking, it's generally better to try to use the audio from the take when they were facing the camera themselves. Syncing is generally not too difficult because you rarely see their lips so you just have to sync to their general head movement.
Sometimes, though, you mix takes when the person is facing the camera (if the audio is much clearer on a take that is different from the one with the best performance visually) and that's what I did that resulted in the sigh. To fix it, I literally cut out one second and replaced it with a second of "silence" from another part of the take. You have to replace it with something to get the sound of the room.
The whole concept of using audio from one take with visuals from another would never have occurred to me had it not been for a remark Bryan Singer makes in the commentary to The Usual Suspects (the first director commentary I ever owned—and on video, long before I owned a DVD player). The commentary on The Usual Suspects was probably the single best lesson in filmmaking I've ever had.
So, I think the film is pretty much done. Now to send a DVD to Tom who's arranged duplication for festival submission.
by : Created on Nov. 26, 2004 : Last modified Feb. 8, 2005 : (permalink)