I've
identified a promising stochastic
search heuristic called hyperclimbing for optimizing over
discrete product spaces (e.g. the space of binary strings of
some fixed length) with noisy objective functions. Hyperclimbing works by recursively sifting
through large numbers of partitions of the search space and by
identifying ones with variegated expected objective values.
Because hyperclimbing is sensitive, not to the local features of
a search space, but to certain more global statistics, it is not
susceptible to the kinds of issues that waylay local search
heuristics. The only visible barrier to the wide and
enthusiastic use of hyperclimbing is that it seems to scale poorly with the size of the search space. When one heeds
the seemingly high cost of applying hyperclimbing to large
search spaces, this heuristic looses its shine. A key
conclusion of my doctoral work is that this seemingly high cost
is illusory. I have uncovered evidence that strongly suggests
that genetic algorithms can implement hyperclimbing
extraordinarily efficiently.
Genetic algorithms are search algorithms that mimic natural
evolution. These algorithms have been used in a wide range of
engineering and scientific fields to quickly procure useful
solutions to poorly understood (i.e. black-box) optimization
problems. Unfortunately, despite the routine use of genetic
algorithms for over three decades, their adaptive
capacity has not been adequately accounted for. Given the
evidence that genetic algorithms can implement efficient hyperclimbing, I've proposed a new explanation for the adaptive
capacity of these algorithms. This new account—the
generative fixation hypothesis—promises to spark significant
advances in the fields of genetic algorithmics and discrete
optimization.
The discovery that
hyperclimbing is efficiently implementable also promises to have
a non-negligible impact on the ecology of machine learning
research. Optimization and machine learning are, after all,
intimately related. The practice of machine learning research,
can broadly be characterized as the effective reduction of
difficult learning problems to optimization problems for which
efficient algorithms exist. In other words, the machine learning
problems that can effectively be tackled are, in large part,
those that can effectively be reduced to optimization problems
that can be tackled efficiently. Currently, this largely limits
the class of tractable machine learning problems to the class of
learning problems that can effectively be reduced to convex
optimization problems [1]. The identification of general-purpose
non-convex optimization heuristics with efficient
implementations (e.g. hyperclimbing), thus, has the potential to
greatly extend the reach of machine learning.
For a description of
hyperclimbing, and evidence that genetic algorithms can
implement this heuristic efficiently, please see my
dissertation
References:
[1] Kristin P. Bennett and Emilio Parrado-Hernandez.
The interplay of optimization and machine learning research.
Journal of Machine Learning Research, 7:1265—1281, 2006.
