PaperlayerView exact revision on arXiv

Source-linked AI summary

Relocating Nonlinearity: How a Downstream Learner Reshapes What Genetic Programming Must Evolve

Nam H. Le

arXiv:2610.09347v1cs.NEcs.LO

TL;DR

Prior work that uses a downstream learner in genetic programming leaves unexplained how the choice of learner relates to target structure. This paper makes target nonlinearity exact on Boolean tasks and measures it on evolved programs. Linear learners force successful programs to match target degree, while tree ensembles succeed with simpler programs; evolution also usually grows more dependent on learning rather than internalising it.

  • Problem

    When a downstream learner completes an evolved program, benchmark comparisons show which learner wins but do not identify the target property that should guide learner choice.

    Source: §1 · p. 2

  • Method

    The paper uses Boolean targets with exact Fourier degree and records the order of nonlinearity of evolved programs to measure how the learner and program divide the target structure.

    Source: §3.1 · p. 4, §3.5 · p. 8

  • Results

    Across parity orders one through six, successful linear-learner programs match target degree in all 30 runs per setting, while tree ensembles succeed with simpler programs and more often.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Learner choice can be guided by whether a target admits a low-order representation recoverable by a bounded learner, rather than by benchmark difficulty alone.

    Source: §5 · p. 13

    Boolean experiments use full truth tables on eight inputs, generalising the measure to multiple features remains open, and the paper does not know how to compute ∆ for arbitrary targets.

    Source: §5 · p. 13

Abstract

from arXiv · show

Genetic programming was conceived as a way of evolving solutions: the program is the answer, and fitness is the error of its own output. A substantial line of work instead makes the program an input to a separate learner, so fitness measures the learner's output rather than the program's. Which learner to attach matters, with no account of what decides it. What makes a target hard for genetic programming is how much nonlinearity the program must build by composing primitives; whatever nonlinearity the learner supplies, the program need not. The quantity to measure is therefore how much of a target's nonlinearity a learner can take over, though on continuous benchmarks it can only be estimated. Here we show that how much the program must still build is decided by which learner is attached, and is measurable on the programs themselves. Moving to Boolean domains, where a target's nonlinearity is exactly its Fourier degree, we tune that degree from one to six with everything else fixed. Conditioned on success, a linear learner forces the evolved program to the target's degree exactly, at one through six without exception over thirty runs per setting, while tree ensembles succeed with far simpler programs and four times as often. This gives the field two things: a learner can be chosen from a target's structure instead of its reputation for difficulty, and the degree of the evolved program is a diagnostic free to compute during any run. Our control target has lower degree than the parity problems yet gains nothing from a nonlinear learner, while targets reducible to a simple statistic gain a great deal. The latter comes with a warning: evolution internalises what the learner supplies in only four of sixty-three conditions, and grows more dependent on it in forty-four, so the more capable the learner, the less of the model is legible in the program.

1 Introduction

When a downstream learner completes the evolved program, the learner determines how much nonlinearity the program must build; Boolean experiments make that division measurable and show that it tracks the attached learner. The paper also finds that learning usually does not become internalised in the program, creating a trade-off with model legibility.

1 Introduction

  • In the downstream-learning arrangement, the program becomes an input to a refitted learner and fitness measures the learner’s output, unlike canonical GP, where the program is the answer.A prior single-feature system varied the learner but did not explain why different learners dominated on different benchmark suites or when programs attained targets unaided.Source: §1 · pp. 1–2
  • The learner-choice question is how much target nonlinearity it can take over, but continuous benchmarks require estimates that vary with sampling range, error tolerance, and polynomial basis.The paper argues that this makes target order difficult to test cleanly on those benchmarks.Source: §1 · p. 2
  • On Boolean inputs, target nonlinearity equals Fourier degree and is computable exactly; parity tunes that degree from one to six while other search conditions stay fixed.The study also measures the nonlinearity of each evolved program rather than inferring the division of labour from pipeline performance.Source: §1 · p. 2
  • Across parity orders one through six, successful linear-learner programs match the target degree in all 30 runs per setting, while tree ensembles succeed with order-two or order-three programs.At the highest order, linear learners succeed in six and seven of 30 runs, compared with 22, 19, and 26 for tree ensembles.Source: §1 · p. 2
  • Across 63 problem–learner conditions, genetic assimilation occurs in four, while learning’s contribution widens over evolutionary time in 44.On parity of order four, the best individual’s innate accuracy falls from 0.713 to 0.394 as learned accuracy rises to 1.000.Source: §1 · p. 2
  • An affine learner supplies no order of nonlinearity, while parity of order k can be composed from an order-1 program and a bounded nonlinear learner.The same composition result holds for every symmetric Boolean function, whatever its degree.Source: §1 · pp. 2–3

2 Related Work

Related work places downstream learning in a distinct role: it completes an evolved representation rather than guiding search for a standalone program. Earlier studies largely fixed linear learners, while this paper connects that gap to target structure, program complexity, and lifetime learning.

2 Related Work

  • Unlike machine learning used inside GP search, downstream learners are refitted for each candidate and score the learner’s output, making the evolved program a representation rather than the solution.The related work surveys this arrangement in classification and regression, including feature construction and multi-gene GP.Source: §2 · p. 3
  • Most downstream-learning systems use linear models, which supply no order of nonlinearity and therefore leave evolved features to carry the target’s full nonlinear structure.The literature could not observe how varying learner capacity changes that division of labour because it rarely varied the downstream component.Source: §2 · p. 3
  • Linear scaling is the degenerate one-feature, affine-learner case, whereas semantic methods alter variation operators and can incur rapid code growth.The paper locates linear scaling at the boundary of what an affine post-hoc learner can contribute.Source: §2 · p. 3
  • The paper uses Vladislavleva et al.’s minimal-degree measure both on targets to predict learner needs and on evolved programs to measure what runs produce.Earlier work used that measure on models as a complexity constraint inside Pareto GP.Source: §2 · p. 3
  • Parity’s indexed family turns Fourier degree from an estimated property into an experimental variable, enabling controlled tests of target nonlinearity.Earlier GP work used parity as a canonical hard case, rather than varying its order as the quantity under study.Source: §2 · pp. 3–4
  • Although prior work reported a Baldwin effect for downstream learning, it measured unaided program performance only at run end and on the easiest problems.The paper follows the phenomenon generation by generation across target orders and finds that the prevailing direction is increased dependence on learning.Source: §2 · p. 4

3 Method

The method treats the evolved program as a feature completed by a freshly fitted downstream learner, then measures how much target nonlinearity the program must supply. Boolean targets make this order exact and tunable, while propositions characterize when affine or expressive learners can absorb target structure.

3.1 Problem formulation

  • The pipeline scores a freshly fitted downstream learner’s output rather than the evolved program itself, and the learner class is the only condition that changes.The program’s output is handed to the learner for each candidate; selection, variation, primitives, size limit, and seed sequence remain fixed.Source: §3.1 · p. 4

3.2 Benchmark targets and order of nonlinearity

  • On the Boolean hypercube, order of nonlinearity at zero tolerance equals Fourier degree, enabling exact measurement from the target’s spectrum.The experiments use all 256 rows for eight Boolean inputs, split 70/30 into training and held-out data.Source: §3.2 · p. 4
  • Parity tunes target order from one to six while holding the search setting fixed; the 6-multiplexer is a lower-order, nonsymmetric control with spread spectrum.The multiplexer has order 3, below PAR4 through PAR6; continuous-target order is instead estimated from polynomial-fit error and can depend on tolerance.Source: Figure 2 · p. 5, §3.2 · p. 6

3.3 Order preservation under an affine learner

  • An affine learner preserves a program’s order of nonlinearity, so reaching a target’s relative error requires the program’s order to be at least the target’s.Rescaling and shifting cannot change the minimum polynomial degree; an affine learner therefore supplies no additional nonlinearity.Source: §3.3 · pp. 6–7

3.4 Relocatable order of nonlinearity

  • Relocatable order measures how much target order a learner can take over; parity of degree k can be represented by a degree-1 program with a k-piece learner.For PAR4, summing the four relevant inputs gives a degree-1 program whose five possible sums let a capable learner recover parity, three orders below the affine route.Source: §3.4 · p. 7
  • Every symmetric Boolean target, including majority, threshold, and counting functions, can be represented by a degree-1 program and a learner with at most n pieces.Such targets can have full Fourier degree n, so high target degree alone does not determine whether an expressive learner can help.Source: §3.4 · p. 7

3.5 Experimental setup

  • The experiments track each generation’s best program order, innate behavior, pipeline accuracy, and held-out error across six learner classes and canonical GP.Runs use a 30-node limit, fixed Boolean primitives, cross-validated learner fitness, and 30 independent runs per condition.Source: §3.5 · p. 8

4 Results

Across Boolean parity targets, the learner determines how much nonlinearity the evolved representation must supply, while results on MUX6 and continuous targets show that target order alone does not determine learner benefit. Across generations, learned behavior often improves without genetic assimilation; continuous-target innateness is measured more strictly than its Boolean counterpart.

4.1 Contribution of each component in isolation

  • With the same order-1 representation, nonlinear learners fit exactly through order seven while linear learning cannot recover above order one; MUX6 defeats every learner on that representation.Raw-input learning and evolution alone also fail differently: the random forest reaches 0.112 at order six, while GP alone is at chance from order four and often collapses to a constant.Source: §4.1 · p. 8, Table 1 · p. 8, Table 2 · p. 9

4.2 Success rate and order of the evolved programs

  • At order six, tree, forest, and boosting succeeded in 22, 19, and 26 runs of thirty, versus six and seven for the linear variants.The linear variants were significantly outperformed by nonlinear learners from order four onward.Source: §4.2 · p. 9, Table 3 · p. 9
  • Across target orders 1–6, linear variants evolved matching-order representations without exception in successful runs, while tree-based learners succeeded with representations of order two or three.The order measurements are conditioned on successful runs.Source: Table 4 · p. 9, §4.2 · p. 9, Figure 5 · p. 10

4.3 Multiplexer control and continuous targets

  • MUX6 has order three, below PAR4–PAR6, yet no learner shows the large advantage seen at higher parity orders; target order alone does not predict benefit.On continuous targets, the predicted ordering appears: linear learning is significantly better on the low-order target, and tree-based learners on the high-order target; tolerance also lets order-five representations achieve R2 ≥0.99 on an order-eight target.Source: §4.3 · pp. 10–11, Table 5 · p. 11

4.4 Innate and learned behaviour across generations

  • Across 63 problem–learner combinations, genetic assimilation occurred in four, while the gap between learned and innate behavior widened in 44.On PAR4 with a random forest, innate accuracy fell from 0.713 to 0.394 as learned accuracy rose from 0.713 to 1.000.Source: §4.4 · p. 11
  • At the lowest order, 26.7% versus 3.3% of runs reached perfect innateness on PAR1, a difference capacity alone does not predict; shielding depends on the size of the target-mapped representation set.For an affine learner, that set is a two-parameter family, and every affinely related representation attains optimal fitness without pressure to match the target exactly.Source: Table 6 · p. 11, §4.4 · p. 12
  • On continuous targets, R2 of the innate representation penalizes scale differences that an affine learner removes; Boolean innateness is sign-based and rescaling-invariant.The paper treats Boolean measurements as primary evidence because continuous measurements capture strict equality to the target, not just its structure.Source: §4.4 · p. 12

5 Discussion

The discussion reframes downstream learning as relocating structural complexity rather than reducing it, and argues that target structure—not benchmark difficulty—should guide learner choice.

5 Discussion

  • Changing only the learner can shift the target's nonlinear order from six to three while leaving the problem's total structural complexity unchanged.The transfer is visible on evolved programs rather than inferred from error.Source: §5 · p. 13
  • Learner choice depends on whether a target admits a low-order representation that a bounded learner can recover, not on the target's benchmark reputation for difficulty.MUX6 gains nothing from a nonlinear learner, whereas a linear learner is significantly better than every alternative on Nguyen-11.Source: §5 · p. 13
  • Attaching a learner can reduce selection pressure for standalone symbolic models; on PAR4 with a random forest, evolution moves away from representations that predict the target unaided.The authors say this tension also applies to systems pairing evolved features with deterministic classifiers or regressors.Source: §5 · p. 13
  • Earlier findings for single-feature systems are reproduced, but the benchmark-suite contrast reflects differences in relocatable order rather than difficulty.Unaided target attainment occurs only in the low-order corner, never above order four, while the prevailing direction is the opposite.Source: §5 · p. 13
  • Evidence separating target order from relocatable order is thin because parity couples them, leaving MUX6 and two continuous targets to dissociate them.The experiments use one feature and full truth tables on eight inputs; the authors also lack a method to compute Δ for arbitrary targets, and continuous innate measurement is not scale-invariant.Source: §5 · p. 13
  • Proposed tests include matched targets with equal order but opposite decomposability, and families such as majority and threshold functions beyond parity.The authors also propose using evolved-representation order as a selective pressure and testing whether relocatable order grows with feature count.Source: §5 · p. 14
Loading 2610.09347v1…