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

Title

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

 Author

Hofstede, Bo (TU Delft Electrical Engineering, Mathematics and Computer Science)

Contributor

Dumančić, S. (mentor)
Volaric Horvat, L. (mentor)
Molenaar, M.L. (graduation committee) ORCID 0000-0001-6298-260X

 Degree granting institution

Delft University of Technology

 Programme

Computer Science and Engineering

 Project

CSE3000 Research Project

 Date

2022-06-24

 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.

 Subject

Program Synthesis
Metropolis-Hastings
Inductive Synthesis
Stochastic Search

 To reference this document use:

http://resolver.tudelft.nl/uuid:ff0f83c4-032f-4a53-aa3c-af9dc32da13e

 Part of collection

Student theses

 Document type

bachelor thesis

 Rights

© 2022 Bo Hofstede
Files
PDF Rp_CSE3000_Report_Final_.pdf 485 KB
Close viewer