🔭 astrophysics

The Inefficiency of Genetic Programming for Symbolic Regression

이 논문은 등가 포화 알고리즘을 개선하여 의미적으로 고유한 표현의 공간을 탐색함으로써, 제한된 설정에서 유전적 프로그래밍이 무작위 탐색보다 효율적이지 않으며 중복 평가를 수행한다는 것을 실증했습니다.

원저자: Gabriel Kronberger, Fabricio Olivetti de Franca, Harry Desmond, Deaglan J. Bartlett, Lukas Kammerer

게시일 2026-03-30

📖 3 분 읽기☕ 가벼운 읽기

원저자: Gabriel Kronberger, Fabricio Olivetti de Franca, Harry Desmond, Deaglan J. Bartlett, Lukas Kammerer

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

🧩 핵심 비유: "거대한 레고 상자 속의 보물 찾기"

상상해 보세요. 여러분은 거대한 레고 상자 (검색 공간) 안에 숨겨진 **완벽한 성 (최적의 수식)**을 찾아야 합니다.

유전 알고리즘 (GP) 의 방식:
- 이 방법은 마치 수천 명의 레고 장난감 제작자를 고용하는 것과 같습니다.
- 제작자들은 서로의 작품을 섞고 (교차), 일부만 고쳐서 (변이) 새로운 성을 만듭니다.
- 문제는 이 제작자들이 매우 비효율적이라는 것입니다.
- 그들은 이미 만들어본 것과 완전히 똑같은 성을 또다시 만들고, 심지어는 완전히 다른 모양의 레고를 쌓아도 실제 기능은 똑같은 경우를 반복해서 만듭니다.
- 마치 "A+B"와 "B+A"는 같은 뜻인데, 이를 다른 작품으로 취급해서 다시 처음부터 만드는 것과 같습니다.
이 연구의 발견 (비효율성):
- 연구자들은 이 비효율적인 제작자들을 관찰한 결과, 매우 놀라운 사실을 발견했습니다.
- GP 는 모든 가능한 레고 조합 중 유일한 (중복되지 않은) 작품을 찾아내는 데 실패했습니다.
- 오히려 이미 만들어본 것과 똑같은 작품을 반복해서 평가하는 시간이 훨씬 더 많았습니다.
- 심지어 **무작위로 레고를 하나씩 뽑아보는 것 (랜덤 서치)**보다도, GP 가 최고의 작품을 찾을 확률이 더 낮았습니다.
왜 이런 일이 일어났을까? (중복의 늪):
- GP 는 수식의 **모양 (구조)**만 보고 판단합니다. 하지만 수학에서는 모양이 달라도 값이 같은 경우가 많습니다.
- 예: x * (x + 1)과 x^2 + x는 모양은 다르지만, 계산 결과는 똑같습니다.
- GP 는 이 둘을 다른 작품으로 착각하고, 둘 다 시간을 들여 평가합니다. 마치 동일한 맛의 커피를 다른 잔에 담아 두 번 주문하는 것과 같습니다.

🔍 연구가 어떻게 진행되었나요?

연구자들은 이 문제를 증명하기 위해 두 가지 방법을 비교했습니다.

완벽한 목록 만들기 (ESR - Exhaustive Symbolic Regression):
- 가능한 모든 레고 조합을 하나도 빠짐없이 다 만들어보고, 모양이 달라도 기능이 같은 것들은 하나로 합쳐서 (단순화) 목록을 만들었습니다.
- 이렇게 하면 "진짜로 새로운 작품"이 총 몇 개인지 정확히 알 수 있습니다. (이 과정은 컴퓨터의 연산 능력을 크게 개선했기 때문에 가능했습니다.)
비교 실험:
- 그룹 A (GP): 유전 알고리즘을 돌려서 50 번이나 시도해 보았습니다.
- 그룹 B (랜덤 서치): 완벽하게 정리된 목록에서 중복 없이 무작위로 하나씩 뽑아보았습니다.

결과:

**그룹 B (랜덤)**이 훨씬 더 빠르게 최고의 성을 찾았습니다.
**그룹 A (GP)**는 시간이 지날수록 이미 본 것과 똑같은 성을 반복해서 만들고, 정작 중요한 새로운 성은 찾지 못했습니다.

💡 실제 데이터로 확인한 사실

이 연구는 두 가지 실제 과학 데이터 (파이프 속 물 흐름, 은하의 운동) 를 사용했습니다.

파이프 흐름 데이터: GP 는 최고의 공식을 찾지 못했고, 이미 찾은 것과 비슷한 공식을 반복해서 평가했습니다.
은하 운동 데이터: 역시 GP 는 최고의 공식을 찾지 못했고, 무작위 검색보다 성과가 나빴습니다.

특히 놀라운 점은, GP 가 만든 수식 중 **약 50%~90%**가 이미 평가했던 것과 중복이거나, **상수 (단순한 숫자)**로 단순화되는 쓸모없는 것이었다는 것입니다.

📝 결론: 무엇을 배울 수 있을까요?

이 논문은 **"유전 알고리즘이 수학적 공식을 찾는 데는 아직 한계가 있다"**는 것을 경고합니다.

비유하자면: GP 는 미로에서 길을 찾을 때, 이미 지나온 길을 다시 지나가거나, 같은 길인데 다른 이름으로 붙여 다시 지나가는 실수를 반복합니다.
해결책의 방향: 앞으로는 GP 가 이미 본 것과 똑같은 수식을 다시 만들지 않도록 (중복 제거) 하거나, 수식의 본질 (기능) 을 먼저 파악하는 더 똑똑한 방법을 개발해야 합니다.

한 줄 요약:

"유전 알고리즘은 수학적 보물을 찾으려 노력하지만, 중복된 보물을 반복해서 주워 담는 비효율적인 탐험가입니다. 때로는 무작위로 하나씩 찾는 것이 더 빠를 수도 있습니다."

1. 문제 제기 (Problem)

배경: 기호 회귀 (Symbolic Regression, SR) 는 주어진 데이터셋을 가장 잘 설명하는 수학적 표현식을 찾는 머신러닝 작업입니다. 유전 프로그래밍 (Genetic Programming, GP) 은 이를 해결하는 데 널리 사용되는 진화 알고리즘입니다.
핵심 문제: GP 는 탐색 공간 (Search Space) 이 매우 크고 중복된 표현 (Redundancy) 이 많아 효율성이 낮을 수 있다는 의문이 제기되어 왔습니다. 많은 다른 표현식이 동일한 함수 (동치 표현) 를 나타내지만, GP 는 이를 구별하지 못하고 중복 평가하거나, 최적 해를 찾지 못해 비효율적으로 탐색할 수 있습니다.
연구 목적: 제한된 탐색 공간 내에서 GP 가 실제로 얼마나 효율적으로 작동하는지, 그리고 무작위 탐색 (Random Search) 과 비교하여 얼마나 많은 중복된 표현을 평가하는지 정량적으로 분석하는 것입니다.

2. 방법론 (Methodology)

연구팀은 GP 의 탐색 효율성을 정밀하게 분석하기 위해 다음과 같은 방법론을 사용했습니다.

완전 열거형 기호 회귀 (Exhaustive Symbolic Regression, ESR) 의 개선:
- 기존 ESR 알고리즘을 개선하여, 주어진 연산자 집합과 길이 제한 내에서 생성 가능한 모든 수학적 표현식을 완전 열거하고, 이를 의미론적으로 고유한 (Semantically Unique) 표현식으로만 필터링하는 시스템을 구축했습니다.
- 동치 포화 (Equality Saturation, Eq-sat) 기술 적용: MetaTheory.jl 패키지를 사용하여 교환법칙, 결합법칙, 분배법칙 등 수학적 등식 규칙을 기반으로 표현식을 정규형 (Canonical Form) 으로 단순화했습니다. 이를 통해 파라미터 값이 달라도 동일한 함수를 나타내는 표현식 (Isomorphic expressions) 을 식별하고 제거할 수 있었습니다.
- 이를 통해 전체 탐색 공간 (Expression Trees) 대비 의미론적으로 고유한 표현식 집합의 크기를 파악했습니다.
비교 대상 설정:
1. 유전 프로그래밍 (GP): TinyGP 및 Operon (최신 GP 구현체) 을 사용하여 50 회 독립 실행을 수행했습니다.
2. 이상적 무작위 탐색 (Idealized Random Search, RS): 의미론적으로 고유한 표현식 집합에서 중복 없이 무작위로 샘플링하여 최적 해를 찾는 알고리즘을 구현했습니다. (파라미터 최적화 비용은 제외하고 구조 탐색 효율성만 비교).
데이터셋:
1. Nikuradse 데이터셋: 거친 파이프 내 유동 (Flow in rough pipes) 데이터.
2. Radial Acceleration Relation (RAR): 은하 역학 데이터 (가시 물질과 관측된 동적 가속도 간의 관계).
실험 설정:
- 표현식 길이 제한 (Length limits): 10, 12, 20 노드.
- GP 는 250 세대, 집단 크기 100~500 으로 설정.
- 파라미터 최적화에는 BFGS 또는 VAR1 알고리즘 사용.

3. 주요 기여 (Key Contributions)

동치 포화 (Eq-sat) 를 활용한 의미론적 중복 제거: 기존 연구들이 피트니스 (적합도) 값의 유사성으로 중복을 판단하던 것과 달리, 수학적 규칙 기반의 정규화 (Canonicalization) 를 통해 파라미터 값과 무관하게 동치인 표현식을 정확히 식별했습니다.
제한된 공간에서의 완전 열거 및 분석: 물리 과학의 실제 데이터셋에 대해, 길이 제한을 두어 모든 의미론적 고유 표현식을 생성하고, GP 가 이 공간 중 얼마나만 탐색했는지 정량화했습니다.
GP 의 비효율성 정량화: GP 가 최적 해를 찾지 못하는 이유를 '탐색 공간의 크기'가 아닌 '중복된 표현의 반복 평가'와 '유용한 영역의 낮은 탐색 확률'에서 찾았습니다.

4. 주요 결과 (Results)

탐색 공간의 중복성:
- 길이 10 노드 기준, 생성 가능한 트리 구조는 약 50 배 더 많았으며, 길이가 길어질수록 중복 비율은 기하급수적으로 증가했습니다.
- GP 가 평가한 표현식 중 의미론적으로 고유한 (Unique) 표현식은 전체의 10~20% 에 불과했습니다. 나머지 80~90% 는 이미 평가했거나 단순화 시 동일한 표현식이었습니다.
- 특히, 단순한 상수 모델 ( $p_1$ ) 로 단순화되는 표현식이 GP 에 의해 빈번하게 생성되었습니다 (길이 10, 12 의 경우 약 50%).
성공 확률 (Success Probability) 비교:
- Nikuradse 데이터셋: GP 는 50 회 실행 중 전역 최적해 (Global Optimum) 를 단 한 번도 찾지 못했습니다. 반면, 무작위 탐색 (RS) 은 제한된 공간 내에서 최적해를 100% 찾았습니다.
- RAR 데이터셋: GP 는 최상위 100 개 솔루션 중 하나를 찾는 성공 확률이 매우 낮았습니다 (길이 12 기준 약 15%). RS 는 동일한 수의 평가 횟수로 훨씬 높은 성공 확률을 보였습니다.
- 효율성: 동일한 성공 확률에 도달하기 위해 GP 는 RS 보다 약 10 배 더 많은 표현식을 평가해야 했습니다.
GP vs Operon:
- 단순한 TinyGP 와 최신 구현체인 Operon 모두 유사한 비효율성 패턴을 보였으며, 이는 GP 알고리즘 자체의 구조적 한계임을 시사합니다.

5. 의의 및 결론 (Significance & Conclusion)

GP 의 비효율성 확인: 기호 회귀에서 GP 는 많은 계산 자원을 소모하면서도 의미론적으로 중복된 표현식을 반복 평가하고, 실제 최적 해가 존재하는 좁은 영역을 우회하는 경향이 있음을 증명했습니다.
중복 평가의 필요성 불명확: GP 가 중복된 표현을 평가하는 것이 진화 과정에서 중립적 단계 (Neutral steps) 를 통해 최적 해에 도달하는 데 도움이 되는지, 아니면 단순한 낭비인지에 대한 논의가 필요함을 제기했습니다.
향후 연구 방향:
- 현재 연구는 짧은 표현식 (10~20 노드) 에 국한되었으나, 더 긴 표현식이나 다변수 문제에서도 유사한 중복 현상이 발생하는지 확인이 필요합니다.
- GP 의 효율성을 높이기 위해 의미론적 중복을 사전에 제거하거나, 중복 평가를 방지하는 새로운 탐색 전략이 필요함을 시사합니다.

요약: 본 논문은 개선된 ESR 과 동치 포화 기술을 활용하여 GP 가 기호 회귀 문제에서 매우 비효율적으로 작동함을 실증했습니다. GP 는 탐색 공간의 대부분을 의미론적으로 동일한 표현식으로 채우며, 최적 해를 찾는 데 있어 이상적인 무작위 탐색보다 훨씬 낮은 성공 확률을 보였습니다. 이는 GP 기반 기호 회귀 시스템의 설계에 있어 중복 제거 및 효율적 탐색 전략의 중요성을 강조합니다.