用语言学最小主义原理重构遗传编程,避免代码膨胀并精准发现真实模型。
Minimalist Genetic Programming
- 以语言学中的合并操作为核心,逐层构建符号表达式
- 在符号回归任务中稳定找到真实模型,标准遗传编程常失败
- 适合追求简洁、可解释性程序的开发者与研究者
遗传编程(GP)基于两个核心思想:一是将任何学习任务视为程序归纳问题,目标是构建以语法树表示的符号层次模型;二是将其视为搜索问题,通过进化寻找目标模型。自提出以来,GP在多个任务中取得显著成果。本文提出一种新视角,对GP的第二条核心思想进行重构,将问题转为句法推导任务。提出最小化遗传编程(MGP),受人类语言最小主义理论启发,不依赖进化,而是采用二元集合形成算子 $MERGE$,通过马尔可夫过程逐步构建复杂句法结构。MGP 能发现符号表达式的底层构建块,并利用 $MERGE$ 逐步组合。在已知易导致代码膨胀的标准符号回归任务上测试,当选择合适的原子句法对象词汇表时,MGP 可一致生成精确的真值模型,而标准 GP 常无法达成。研究表明,最小主义的洞察对程序归纳具有重要价值,应进一步探索。
原文摘要 · Abstract (English)
Genetic programming (GP) is based on two important insights. First, that any learning task can fundamentally be posed as a program induction problem, where the goal is to construct a symbolic hierarchical model that is expressed as a syntax tree. Second, to pose this task as a search problem, and use evolution to locate the desired model. Since it was proposed, GP has produced notable results in a wide range of tasks and problem domains. This work presents an alternative view by modifying the second core insight of GP, posing the problem as a syntactic derivation task instead. In particular, this paper presents Minimalist Genetic Programming (MGP), an algorithm that like GP is biologically inspired, but instead of evolution it takes inspiration from the Minimalist Program to human language, in which syntax is understood as an optimal solution to the problem of linking two other mental systems. In minimalism, the core computational process is a binary set formation operator called $MERGE$, than can be used to incrementally construct complex syntactic structures using a simple Markovian process. MGP is able to discover the core building blocks of the symbolic expressions, and to incrementally combined them using $MERGE$. The proposed system is benchmarked on symbolic regression tasks that are known to be difficult to solve with standard GP systems because of the propensity for bloat. Results show that when a proper lexicon of atomic syntactic objects are chosen, MGP is able to consistently produce the exact ground truth model on a set of symbolic regression tasks where standard GP struggles to do the same. The insights provided by minimalism are shown to be relevant to the problem of program induction, and should be explored further based on the potential exhibited by MGP in this work.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。