Stepwise Entropy Reduction : Review of Theoretical Results in the Finite/Deterministic case - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1, 2)
1
2

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)
Not file

Dates and versions

hal-02488242 , version 1 (22-02-2020)

Licence

Attribution - NonCommercial - NoDerivatives - CC BY 4.0

Identifiers

  • HAL Id : hal-02488242 , version 1

Cite

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⟩
41 View
0 Download

Share

Gmail Facebook Twitter LinkedIn More