Generational Computation Reduction in Informal Counterexample-Driven Genetic Programming
Counterexample-driven genetic programming (CDGP) uses specifications provided as formal constraints to generate the training cases used to evaluate evolving programs. It has also been extended to combine formal constraints and user-provided training data to solve symbolic regression problems. Here we show how the ideas underlying CDGP can also be applied using only user-provided training data, without formal specifications. We demonstrate the application of this method, called ``informal CDGP,'' to software synthesis problems. Our results show that informal CDGP finds solutions faster (i.e. with fewer program executions) than standard GP. Additionally, we propose two new variants to informal CDGP, and find that one produces significantly more successful runs on about half of the tested problems. Finally, we study whether the addition of counterexample training cases to the training set is useful by comparing informal CDGP to using a static subsample of the training set, and find that the addition of counterexamples significantly improves performance.
Code (0)
등록된 구현이 없습니다.
Tasks
Symbolic RegressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
A Note on Non-Composability of Layerwise Approximate Verification for Neural Inference
A natural and informal approach to verifiable (or zero-knowledge) ML inference over floating-point data is: ``prove that each layer was computed correctly up to tolerance $δ$; therefore the final output is a reasonable i…
Learning from Equivalence Queries, Revisited
Modern machine learning systems, such as generative models and recommendation systems, often evolve through a cycle of deployment, user interaction, and periodic model updates. This differs from standard supervised learn…
Recommendation SystemsOne Example Shown, Many Concepts Known! Counterexample-Driven Conceptual Reasoning in Mathematical LLMs
Leveraging mathematical Large Language Models (LLMs) for proof generation is a fundamental topic in LLMs research. We argue that the ability of current LLMs to prove statements largely depends on whether they have encoun…
Mathematical ReasoningTeaching via Best-Case Counterexamples in the Learning-with-Equivalence-Queries Paradigm
We study the sample complexity of teaching, termed as "teaching dimension" (TD) in the literature, for the learning-with-equivalence-queries (LwEQ) paradigm. More concretely, we consider a learner who asks equivalence qu…
Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
Motivated by phase transitions in combinatorial optimization problems, we define two kinds of geometry-preserving reductions between constraint satisfaction problems and other NP-search problems. We give a couple of exam…
Combinatorial Optimization