Learning the Selection of a Good Control

With many different search controls available to the user of a search system, deciding which of these controls should be used for a particular problem instance already can determine whether the instance will be solved or not. Or, seeing these controls as different agents that can work on the search problem, selecting the right one decides already much of the outcome of a search.

By analyzing successful and unsuccessful search runs of different agents for different problem instances, human users get a feeling for this selection process. And this can be automated by storing data about already solved problem instances and the performance of different search controls on them. Then, for deciding which control to select, the given problem instance is compared to the stored instances and the best control for the most similar instance is selected. We use so-called features of the problem instances, i.e. properties of them that can be described by numbers, to determine such a similarity, by comparing feature vectors and computing a weighted sum of the difference in each element of the vectors.

In terms of our nine questions, this general approach can be described as follows:

• What or whom do we learn from?
  The own positive experiences of the search system, especially for easy problem instances (with trying out many or all of the available controls).
• What to learn?
  Pairs of feature vectors describing a problem instance and search controls used to solve them, the later together with the time needed to find a solution.
• How to represent and store the learned knowledge?
  So far, we just stored the pairs mentioned above in a list. With a growing number of pairs, indexing with respect to all or only some key features might become necessary.
• What learning method to use?
  Simply learning by heart. Again, with a growing number of pairs some more elaborated learning techniques that compact the data and remove redundant information might be needed.
• How to detect applicable knowledge?
  All pairs with feature vectors whose similarity with the vector of the given problem instance is high enough, i.e. over a given threshold, are considered applicable knowledge. Usually the pair with the highest similarity is then applied first. If two pairs have the same similarity then the one that solved the problem faster is the one tried first.
• How to apply knowledge?
  The search control of the selected pair is used as search control.
• How to detect and deal with misleading knowledge?
  We apply a selected search control only for a given time limit and then restart the system with the initial problem instance and the next similar vector-control pair.
• How to combine knowledge from different sources?
  No solution except that we want to use this learning approach together with a cooperation concept and then have several other search agents helping during the search.
• Which concepts of similarity are helpful?
  The similarity of two problem instances is the higher, the lower the weighted sum of their feature vector differences is.

Although this selection idea for search controls is rather general, the success of the approach heavily depends on the detection and selection of useful features for the vectors. And this depends on the concrete search problem.

to our page on flexible re-enactment.

Last Change: 5/12/2013