Saturday, March 10, 2012

very fast multiple objective optimization?

This paper 

  • Ostrouchov, G.; Samatova, N.F.; , "On FastMap and the convex hull of multivariate data: toward fast and robust dimension reduction," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.27, no.8, pp.1340-1343, Aug. 2005 doi: 10.1109/TPAMI.2005.164 URL:
  • Says that "FastMap is a dimension reduction technique that operates on distances between objects. Although only distances are used, implicitly the technique assumes that the objects are points in a p-dimensional Euclidean space. It selects a sequence of k ≤ p orthogonal axes defined by distant pairs of points (called pivots) and computes the projection of the points onto the orthogonal axes. We show that FastMap uses only the outer envelope of a data set. Pivots are taken from the faces, usually vertices, of the convex hull of the datapoints in the original implicit Euclidean space."

That is, the pivots found by Fastmap map out vertexes in the the convex hull (the minimum polygon that contain all points)

Now they don't go the next step (which I think is obvious). To do multi-objective optimization,

  1. generate candidates
  2. apply recursive divisive clustering with fastmap, keeping track of all the pviots found along the way
  3. apply pareto domination to just the pivots, deleting the dominated ones
  4. use the survivors as parents for the GAs or DEs
  5. loop

Also, this could be a cache for on-line multi-objective optimization.
  1. find 1000 examples, recursively cluster them with fastmap. 
    • Set "important" to be the pivots found in this process 
  2. 1000 times
    • find one more example.
    • if it falls between pivots, ignore it. else, add it to "important"
  3. Recursively cluster the important points. 
    • Set  a new "important" set to be the pivots found in this process 
  4. Goto step 2
Also, it gives us active learner for Multi-objective optimization. Note how, in the following, we only ask the oracle for data in the yellow circumstances.

  1. Apply the above on-line learner
    • When pivots are created, ask an oracle for the value of those pivots.
    • And check for domination between each pivot pair
    • Only  ask the oracle for pivot values
  2. Watch for  new arrivals if they fall outside of a pivot pair
    • Only ask the oracle for score on instances that fall outside the pair.
    • Check them for domination against the non-dominated 2 pivot pairs
    • Forget them if they are dominated
    • Else, add them to that "important" set
  3. Every (say) 1000 instances,
    •  Forget everything except the non-dominated pivots and the non-dominated newbies.
    • Rebuild the cluster tree

No comments:

Post a Comment