math.aau.dk

이 이메일 도메인이 관측된 논문 1건

arXiv:2608.25034v1cs.LG

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

On the Representational Geometry of Dynamic Programs

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