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 metadata
Contributor : Julien Bect Connect in order to contact the contributor
Submitted on : Saturday, February 22, 2020 - 2:33:59 PM
Last modification on : Sunday, June 26, 2022 - 2:27:56 AM


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 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