SynGuar: Guaranteeing Generalization in Programming by Example
| Autor: | Teodora Baluta, Aashish Kolluri, Prateek Saxena, Bo Wang |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
D.3.0
Reverse engineering FOS: Computer and information sciences Computer Science - Programming Languages D.2.0 Unification Computer science Generalization Programming by example Function (mathematics) Overfitting computer.software_genre Set (abstract data type) Software Engineering (cs.SE) Computer Science - Software Engineering computer Algorithm Program synthesis Programming Languages (cs.PL) |
| Zdroj: | ESEC/SIGSOFT FSE |
| DOI: | 10.48550/arxiv.2106.11610 |
| Popis: | Programming by Example (PBE) is a program synthesis paradigm in which the synthesizer creates a program that matches a set of given examples. In many applications of such synthesis (e.g., program repair or reverse engineering), we are to reconstruct a program that is close to a specific target program, not merely to produce some program that satisfies the seen examples. In such settings, we wish that the synthesized program generalizes well, i.e., has as few errors as possible on the unobserved examples capturing the target function behavior. In this paper, we propose the first framework (called SynGuar) for PBE synthesizers that guarantees to achieve low generalization error with high probability. Our main contribution is a procedure to dynamically calculate how many additional examples suffice to theoretically guarantee generalization. We show how our techniques can be used in 2 well-known synthesis approaches: PROSE and STUN (synthesis through unification), for common string-manipulation program benchmarks. We find that often a few hundred examples suffice to provably bound generalization error below $5\%$ with high ($\geq 98\%$) probability on these benchmarks. Further, we confirm this empirically: SynGuar significantly improves the accuracy of existing synthesizers in generating the right target programs. But with fewer examples chosen arbitrarily, the same baseline synthesizers (without SynGuar) overfit and lose accuracy. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|