Gröbner 기저 계산을 위한 빠른 단항식 순서 학습
Learning Fast Monomial Orders for Gröbner Basis Computations
한국어 초록
다항 방정식 시스템을 푸는 표준 엔진인 Gröbner 기저 계산의 효율은 단항식 순서(monomial ordering) 선택에 달려 있다. 가능한 단항식 순서가 거의 연속에 가깝게 많음에도 불구하고, 대부분의 구현은 GrevLex와 같은 정적 휴리스틱에 의존하며 주로 전문가 직관에 기대고 있다. 우리는 허용 가능한 순서 공간 위에서 단항식 순서 선택을 강화학습 문제로 공식화함으로써 이 공백을 메운다. 우리 접근법은 Gröbner 기저 계산의 계산 비용을 정확히 반영하는 도메인 정보 기반 보상 신호를 활용하며, 효율적인 몬테카를로 추정이 가능하다. 시스템 생물학과 컴퓨터 비전(CV)의 벤치마크 문제에 대한 실험에서, 학습된 정책은 표준 휴리스틱을 일관되게 능가하여 계산 비용을 크게 줄였다. 더 나아가 이러한 정책은 단순하고 해석 가능한 모델로의 지식 증류(distillation)에 잘 견디지 못하는 것으로 나타났으며, 이는 심층 강화학습이 에이전트(agent)가 전통적 휴리스틱의 범위를 넘는 비선형 기하 구조를 활용할 수 있게 한다는 실증적 증거를 제공한다.
원문 초록
The efficiency of Gröbner basis computation, the standard engine for solving systems of polynomial equations, depends on the choice of monomial ordering. Despite a near-continuum of possible monomial orders, most implementations rely on static heuristics such as GrevLex, guided primarily by expert intuition. We address this gap by casting the selection of monomial orderings as a reinforcement learning problem over the space of admissible orderings. Our approach leverages domain-informed reward signals that accurately reflect the computational cost of Gröbner basis computations and admits efficient Monte Carlo estimation. Experiments on benchmark problems from systems biology and computer vision show that the resulting learned policies consistently outperform standard heuristics, yielding substantial reductions in computational cost. Moreover, we find that these policies resist distillation into simple interpretable models, providing empirical evidence that deep reinforcement learning allows the agents to exploit non-linear geometric structure beyond the scope of traditional heuristics.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2602.02972v2제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.