Oct24 '14 by Tim Menzies

Been reading on MOEA/D (see also PADE. Its kind of a meta-learner. It builds islands then runs a standard learner on each island. E.g. MOEA/D-DE would run differential evolution on various islands.

There are some standard methods for making the islands but I was thinking, why not just use linear-time binary-split FastMap?

Then, build recommendations for jumping from current to better, as follows. For each current island I1..

  • Find “better” islands where “better” means that for at least one objective, the Cliff’s delta effect size (using the thresholds proposed top of p14 of here, pword=user=guest, o) says they are truly different and the medians are skewed in a “better” way.
  • For each island I2 build a contrast learning task as follows where class1= I1, class2= I2 and class3= every other island.
  • Discretize all numerics by minimizing entropy of class1,class2,class3.
  • Sort the ranges by BORE where best=class2 and rest=class1_ (for notes on BORE, see section 4.2 of this paper.
  • Let the value of the first i items of that sort be what percentage of class1,class2,class3 instances that have those i ranges contain class2 (the target class).
  • Return the smallest i ranges where i+1 has less value.

If this is data mining (where no new data can be generated) then stop. Call what you have “islands, first generation”. Else:

  • For each island with a contrast set, collect new instances by interpolating instances in that island, then applying the contrast set.
  • Repeat till new improvements are only epsilon better than last. This generates, “islands, generation last”.
  • Run the above current to better algorithm using a combination of the first and last generation algorithms.

Not some short cuts:

  • Instead of discretizing for each new pair of current,better, discretize ONCE across all the islands. Proably would work just fine.
  • Once the data is discretized, build a reverse index from the ranges back to the candidates they select for. Which would make testing the value stuff very fast.
  • When looking for better, be simpler.
  • Active learning: on the way down with fastmap, prune dull islands. Also, when testing if one island is better than another, only pick some items at random in each island (say, the small m examples nearest the fastmap poles of each island)

But why is it called Keys West? An algorithm that builds bridges between islands? That extends an older algorithm of mine called Keys2? Well, see if you can figure that out.