II. SIMPLE EXPLANATIONS OF KEY IDEAS IN ORDINAL OPTIMIZATION



II.4 THE IMPORTANCE OF REPRESENTATION IN SEARCHES


  1. Suppose you have a design space of 10 billion which is small by most combinatorial standards. You uniformly and randomly sample 10,000 designs in this space which by definition is the limit of your computing budget. What is the probability that NONE OF YOUR SAMPLES will fall in the top-50, top-500, top-5,000, top-50,000 of the designs?

    Answer: 0.99995, 0.9995, 0.99501, 0.951 respectively, i.e., virtually no chance pure random search will get you anything good.

  2. Now suppose you have a representation which can focus your sampling within the top-1 million designs exclusively, what will your answers be now?

    Answer: 0.606, 0.00673, 1.7x10-22, and > 1x10-222 or zero essentially, i.e., you can't fail.

  3. One can interpolate in between to see the truth of the statement: WITH THE RIGHT REPRESENTATION ANYTHING WOULD WORK; WITHOUT THE RIGHT REPRESENTATION, FORGET IT.

    Philosophically this is comforting since it says that there is room for human beings who have to dream up the right representation. We have not learned to automate that step as yet. I personally do not subscribe to the idea that anytime soon some general purpose optimization scheme such as simulated annealing or genetic algorithms can be let loose on a computer without human supervision and expected to perform well uniformly.


To Next Slide / To Table of Content