arXiv:2608.25034v1 cs.LG

동적 프로그램의 표현 기하학

On the Representational Geometry of Dynamic Programs

Richard F. M. Lim, Ruriko Yoshida

제출 2026-08-25

한국어 초록

표준 신경망 구조는 동적 프로그래밍(DP) 타깃에 대해 더 긴 입력으로 일반화하는 데 종종 실패한다. 우리는 이것이 기하학적으로 왜 어려운지 조사한다. 모든 유한 min-plus DP는 방향성 비순환 그래프 위의 최단 경로이며, 이는 동치적으로 확장 뉴턴 다면체가 어떤 경로가 이기는지의 결정 경계를 인코딩하는 트로피컬 다항식이다. 우리는 이 세 가지 기술(그래프, 다항식, 다면체)이 두 수준에서 — 형식 다항식과 그들이 계산하는 함수 — 동형 세미링을 이루며, 모든 구조적 중복을 특성화하는 연산들로 연결됨을 증명한다. 그다음 길이 일반화 문제를 기하학적으로 다룬다: 길이 $T$에서의 결정 경계가 $T+1$에서의 경계를 결정하는가? 우리는 두 가지 구조적 부정 결과를 제시한다. 세미링의 두 가지 고유한 차원 축소 방식(각 항등원에 변수를 설정하는 것)은 단사도 아니고 DP 내에서 항상 닫혀 있지도 않다. 직렬 및 병렬 합성은 더 작은 하위 방향성 비순환 그래프로부터 모든 방향성 비순환 그래프 위상을 구성하는 데 실패하며, 터미널 전용 연산 전체를 사용해도 모든 DP 합성을 포착하지 못한다.

원문 초록

Standard neural architectures often fail to generalize to longer inputs for dynamic programming (DP) targets. We investigate what makes this hard geometrically. Every finite min-plus DP is a shortest path on a DAG, which is equivalently a tropical polynomial whose extended Newton polyhedron encodes the decision boundary of which path wins. We prove these three descriptions (graph, polynomial, polyhedron) form isomorphic semirings at two levels --- formal polynomials and their computed functions --- connected by operations that characterize all structural redundancies. We then address the length-generalization question geometrically: does the decision boundary at length $T$ decide the boundary at $T+1$? We present two structural negatives. The semiring's two native ways to reduce dimension (setting a variable to each identity) are neither injective nor always closed within the DP. Series and parallel composition fail to construct all DAG topologies from smaller sub-DAGs, and even all terminal-only operations do not capture all DP compositions.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2608.25034v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.