How to train your dragon: on the application of the Metropolis-Hastings algorithm for program synthesis

Bachelor thesis (2022)

Authors

Q.B. Hofstede Electrical Engineering, Mathematics and Computer Science

Contributors

S. Dumančić Algorithmics - EEMCS (mentor)
L. Volaric Horvat Algorithmics - EEMCS (mentor)
M.L. Molenaar Computer Graphics and Visualisation - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 Bo Hofstede
More Info
expand_more

Published Date

24-06-2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

This paper addresses the problem of Inductive Synthesis by analysing the Metropolis-Hastings stochastic search algorithm. The goal of Inductive Synthesis is to generate programs whose intended behaviour is established through the use of input and output examples. The Metropolis-Hastings algorithm searches the set of all possible programs and finds possible solutions. Our experiments show that while optimization can be done under certain conditions, it does not improve the
algorithm’s success rate in synthesizing programs on complex domains compared to more randomized but domainspecific approaches.