Skip to Main content Skip to Navigation
Conference papers

Stepwise Entropy Reduction : Review of Theoretical Results in the Finite/Deterministic case

Abstract : The stepwise entropy reduction idea was introduced in the field of Bayesian optimization by Villemonteix, Vazquez and Walter [1]. In short, given a prior model on the "unknown" function to be minimized, evaluation points are selected sequentially in order to greedily minimize the expected conditional entropy of the minimizer. The same idea can be found under various forms and names in many different fields, such as sequential testing [2], active learning [3], search [4], image processing [5], etc. This communication will review some theoretical results about the performance of stepwise entropy reduction strategies in simple settings where the probability space is finite and the responses are deterministic [6, 7]. References [1] Villemonteix, J., Vazquez, E., and Walter, E. (2009). Aninformational approach to theglobal optimization of expensive-to-evaluate functions.Journal of Global Optimization,44(4):509–534. [2] Johnson, R. (1960). An information theory approach to diagnosis. InProceedings of the6th Symposium on Reliability and Quality Control, pages 102–109. [3] MacKay, D. J. C. (1992). Information-based objective functions for active data selection.Neural Computation, 4(4):590–604. [4] O’Geran, J. H., Wynn, H. P., and Zhiglyavsky, A. A. (1993). Mastermind as a test-bed forsearch algorithms.Chance, 6(1):31–37. [5] Geman, D. and Jedynak, B. (1996). An active testing modelfor tracking roads in satelliteimages.IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(1):1–14. [6] Kosaraju, S. R., Przytycka, T. M., and Borgstrom, R. (1999). On an optimal split treeproblem. In Workshop on Algorithms and Data Structures (pp.157–168). Springer, Berlin,Heidelberg. [7] Dasgupta, S. (2005). Analysis of a greedy active learning strategy. In Advances in NeuralInformation Processing Systems (pp. 337–344)
Complete list of metadatas
Contributor : Julien Bect <>
Submitted on : Saturday, February 22, 2020 - 2:33:59 PM
Last modification on : Wednesday, September 16, 2020 - 4:50:52 PM


Distributed under a Creative Commons Attribution - NonCommercial - ShareAlike 4.0 International License


  • HAL Id : hal-02488242, version 1


Julien Bect. Stepwise Entropy Reduction : Review of Theoretical Results in the Finite/Deterministic case. French-German-Swiss Conference on Optimization (FGS'19), Sep 2019, Nice, France. ⟨hal-02488242⟩



Record views