Ordering Goals Rather Than Prerequisites
The outcome of my simulated annealing program is a list of prerequisites to learn along with an indication, every so often, of what new goal has been reached. Running on the Greek lexemes of 1John, you might get something starting like this:
learn μαρτυρέω learn θεός learn ἐν learn εἰμί learn ὁ learn τρεῖς learn ὅτι know 230507
This gives seven prerequisites to learn and then a goal that has been reached (230507 = 1John 5.7). The problem is that two of those words are unnecessary. You only need to learn μαρτυρέω, εἰμί, ὁ, τρεῖς and ὅτι to be able to read 1John 5.7.
The problem is that the program is ordering prerequisites first and only then establishing at each point what goals (if any) have been achieved.
I can see two solutions:
- write a post-processor that walks through and, at each goal, takes any "unused" prerequisites and postpones them to after that goal.
- change the program to order goals rather than prerequisites and work out the latter from the former
The second is probably considerably more work but probably ultimately preferred.
UPDATE: I'm almost embarrassed to report that not only was changing over to ordering goals not as hard to do as I thought, but the particular way I did it performs 200 times faster than my previous prerequisite ordering script. New script is at http://jtauber.com/2005/08/sa_goal_ordering.py
Comments (4)
James Tauber on Aug. 4, 2005:
Wow! I'm excited to try this out.
To answer your immediate question about what the score is: it's the sum of the percentage known after each new prerequisite learnt.
So it favours knowing more earlier on.
I'm about to run your script to see if it gives a higher score than simulated-annealing on 1John.
Chris Huntley on Sept. 5, 2006:
I ran across your blog from the Pyjamas mailing list.
I'm curious about the choice of Simulated Annealing for this problem. (Disclosure: I worked on SA variants for my PhD thesis back in the mid-1990s, but haven't done much with SA recently.) Why not try Tabu Search, which works particularly well for things like permutation searches, and shares lots of features with SA. You could likely re-use 80% of your SA code and perhaps get better results.
James Tauber on Nov. 4, 2007:
To be honest, I didn't know about Tabu search. I'll give it a try.
Add a Comment
Last Modified: Aug. 3, 2005
Author: James Tauber
Tim Wegener on Aug. 4, 2005:
I came up with a solution the problem you presented in your post while I was doing the dishes this evening.
My solution doesn't use a simulated-annealing approach. Rather, it feels like some sort of topological sort. I work backwards, using a sort of process of elimination.
Roughly, this is what I do:
- keep track of how many times a root occurs in each verse
- keep track which verses each root occurs in
- Starting with the roots that occur with minimum frequency:
+ find *all* roots found in verses that include the rarest roots
+ decrement the root occurrences for each verse
(so that this these verses are not contributing to the root frequency)
+ remove these verses from the source data
+ remove this round of rarest roots from the absolute root frequency map
+ repeat this process until all verses have been consumed
This seems to do the trick and relatively quickly (a couple of minutes on an old Celeron 850MHz).
In one of your older posts you mentioned some score (which looked like a percentage) by I'm not sure what you meant by that.
My rough script outputs the sorted list (in reverse order), then outputs the 'learn <word>', ..., 'know <verse>' output like in your latest post. It also outputs the percentage of verses that are known up to the current 'know' point.
It's getting pretty late, so I don't have time for rigorous analysis, but it looks like it worked after eyeballing the results.
I'll email you the script. It takes your parsed GNT as input.
P.S. Until I read your post today I was only aware of learning words in order of absolute frequency. I've been interested in finding out techniques like the one you suggested, to speed up learning Hebrew. I haven't tried learning Greek, but your resources will definitely help when I get on to that one day!