Neural–Evolutionary Symbolic Regression with Global Constraints: Constraint-Aware Decoding and Reward Shaping

Motivation

• Known: 기존 neural symbolic regression 방법들(DSR, E2ESR, DGSR 등)은 expression tree를 preorder token sequence로 선형화해 autoregressive Transformer/RNN으로 생성하며, 이는 batching과 표준 시퀀스 모델링을 가능하게 하지만 tree hierarchy를 명시적으로 노출하지 않는다. 또한 hybrid neural-evolutionary 방법(NGGP 등)은 GP-refined elite를 직접 모방 학습 대상으로 사용하여 distribution mismatch 문제를 겪을 수 있다.
• Gap: 시퀀스 기반 디코더는 ancestor-descendant path나 subtree 경계와 같은 구조 정보를 파서 상태나 스택 등을 통해 간접적으로만 복원할 수 있어, operator composition 제약과 같은 구조 의존적 global constraint를 통일된 방식으로 직접 질의(query)할 수 있는 explicit tree state를 제공하지 못한다. 또한 GP-refined elite를 직접 지도학습 타깃으로 사용하면 off-policy 샘플에 학습이 민감해지는 문제가 있다.
• Why: 구조 정보를 명시적으로 유지하면서도 batched neural decoding이 가능해지면, 불안정하거나 중복된 표현(예: exp-log 반복 중첩, 역함수 상쇄, 깊은 삼각함수 중첩)을 구조 기반 마스킹만으로 효율적으로 억제할 수 있어 해석 가능성과 탐색 효율을 동시에 높일 수 있다. 이는 과학적 모델링에서 신뢰할 수 있는 symbolic regression 도구 개발에 중요하다.
• Approach: 변수 크기의 expression tree를 placeholder node를 삽입해 고정 토폴로지의 perfect binary tree(SPBT)로 임베딩함으로써 생성을 그래프 상의 node-attribute prediction 문제로 재구성하고, GCN 기반 생성기와 GP refinement를 Similarity-Weighted Policy Gradient(SWPG)로 결합한다.

Achievement

Figure 4. Tradeoff Experiments

1. SPBT(Symbolic Perfect Binary Trees) 제안: placeholder node 삽입을 통해 가변 토폴로지 expression tree를 고정 토폴로지 scaffold로 정렬시켜 tree hierarchy를 보존하면서 batched 그래프 연산을 가능하게 함.
2. 그래프 기반 SPBT generator 개발: expression 생성을 node-attribute prediction으로 재구성하고, ancestor-path 및 subtree 기반 구조 제약을 precomputed structural index와 masking으로 구현하는 constraint-aware decoding을 실현함.
3. Similarity-Weighted Policy Gradient(SWPG) 도입: GP-refined elite를 직접적인 지도학습 타깃으로 사용하지 않고, 현재 policy가 샘플링한 on-policy 후보에 대한 similarity-weighted reward로 변환하여 distribution mismatch를 완화함.
4. GCN-SR 프레임워크 통합 및 실험적 검증: 표준 symbolic regression 벤치마크와 ablation에서 동일한 평가 budget 하에 강력한 neural 및 hybrid baseline 대비 exact recovery 성능을 일관되게 개선함.

How

Figure 3. A. Expression sampling based on GCNs, leveraging matrix operations to encode global structural information. Th

• expression tree(예: sin(x3x2 + cos(x))의 두 표현 방식을 비교하며 SPBT가 placeholder node를 통해 어떻게 고정 depth의 perfect binary tree로 확장되는지 정의(Fig. 2, Fig. 5의 adjacency matrix 참고).
• GCN 기반 생성기가 행렬 연산을 활용해 SPBT 위에서 node attribute를 배치(batch) 단위로 샘플링(Fig. 3A).
• ancestor-path 및 subtree-dependent global constraint를 SPBT의 구조적 인덱스와 마스킹을 통해 decoding 시점에 하드하게 강제.
• 신경망 생성기를 depth가 제한된 constrained proposal mechanism으로 간주하고, 더 복잡한 표현 복원을 위해 GP mutation/crossover로 subexpression을 재조합하는 refinement 단계를 결합.
• GP로 refine된 elite expression의 sampling probability가 현재 policy 하에서 알려져 있지 않다는 점에 착안, 이를 직접 모방 학습 타깃으로 쓰지 않고 on-policy 샘플과의 유사도에 기반한 reward shaping(SWPG)으로 변환하여 policy gradient 업데이트에 반영.
• SPBT depth에 따른 표현력(expressivity)과 node 수의 지수적 증가 사이의 trade-off를 실험적으로 분석(Fig. 4).
• 표준 symbolic regression 벤치마크와 ablation study를 통해 exact recovery 성능을 강력한 neural 및 hybrid baseline과 동일 평가 budget 하에서 비교.

Originality

• 기존 GNN 기반 SR 방법들이 GNN을 GP/MCTS 등 외부 탐색을 안내하는 scoring/surrogate 모델로만 활용한 것과 달리(Fig. 1A), GCN 자체를 expression generator로 사용해 고정 scaffold 위에서 직접 node attribute를 디코딩하는 새로운 패러다임을 제시함(Fig. 1B).
• 가변 토폴로지 tree를 고정 토폴로지 perfect binary tree로 임베딩하는 SPBT라는 구조적 장치는 tree hierarchy 보존과 batched 그래프 연산 가능성을 동시에 확보하는 참신한 표현 방식임.
• GP-refined elite를 지도학습 타깃이 아닌 similarity 기반 reward shaping 신호로만 활용하는 SWPG는 기존 PQT류의 elite-matching 방식과 차별화되는 off-policy mismatch 완화 전략임.

Limitation & Further Study

• SPBT depth 증가에 따라 노드 수가 지수적으로 증가하므로, 신경망 생성기는 본질적으로 moderate-depth 탐색 공간 내의 constrained proposal mechanism으로 제한되며 임의로 깊은 수식을 단독으로 생성하기 어려움.
• placeholder node 도입으로 인한 계산·메모리 오버헤드가 존재할 것으로 예상되나, 본문 발췌에서는 이에 대한 정량적 분석(예: 실제 runtime, 메모리 사용량 비교)이 충분히 제시되지 않음.
• similarity-weighted reward 설계에서 similarity metric의 선택이 성능에 미치는 영향에 대한 민감도 분석이 추가로 필요해 보임.
• 후속 연구로는 SPBT depth를 적응적으로 조정하는 메커니즘이나, 더 다양한 operator set 및 고차원 입력에 대한 확장성 검증이 필요함.

Evaluation

총평: tree 구조를 명시적으로 보존하면서 batched neural decoding과 GP refinement를 결합한 GCN-SR은 symbolic regression 분야에 구조 인식 생성이라는 새로운 관점을 제시하는 견고한 연구로, exact recovery 개선을 통해 실질적 기여를 보여준다.