Why are state-space models more expressive than $n$-gram models?
원문 초록
Recent advancements in recurrent neural networks (RNNs) have reinvigorated interest in their application to natural language processing tasks, particularly with the development of more efficient and parallelizable variants known as state space models (SSMs), which have shown competitive performance against transformer models while maintaining a lower memory footprint. While RNNs and SSMs (e.g., Mamba) have been empirically more successful than rule-based systems based on $n$-gram models, a rigorous theoretical explanation for this success has not yet been developed, as it is unclear how these models encode the combinatorial rules that govern the next-word prediction task. In this paper, we construct state space language models that can solve the next-word prediction task for languages generated from $n$-gram rules, thereby showing that the former are more expressive. Our proof shows how SSMs can encode $n$-gram rules using new theoretical results on their memorization capacity, and demonstrates how their context window can be controlled by restricting the spectrum of the hidden weight matrix. We conduct experiments with a small dataset generated from $n$-gram rules to show how our framework can be applied to SSMs and RNNs obtained through gradient-based optimization.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
MambaFusion: Height-Fidelity Dense Global Fusion for Multi-modal 3D Object Detection
Sparsified State-Space Models are Efficient Highway Networks
Hierarchical Mamba Meets Hyperbolic Geometry: A New Paradigm for Structured Language Embeddings
U-PEN Mamba: 점진적 확장과 선택적 상태 공간 모델링을 활용한 효율적 망막 혈관 분할
U-PEN Mamba: Progressive Expansion with Selective State-Space Modeling for Efficient Retinal Vessel Segmentation
정확한 망막 혈관 분할은 컴퓨터 지원 안과 분석에 중요하지만, 가는 혈관, 낮은 대비, 심한 전경-배경 불균형은 인코더-디코더 네트워크에 여전히 어려운 과제로 남아 있다. 본 논문은 점진적 비선형 특징 확장과 선택적 상태 공간 모델링을 결합한 U자형 망막 혈관 분할 아키텍처인 U-PEN Mamba를 제안한다. 제안 네트워크는 점진적 확장으로 국소 혈관 응답을 풍부하게 하고, 선형 시퀀스 복잡도를 갖는 Mamba Global Context(MGC) 블록을 통해 장거리 공간 의존성을 모델링하며, 어텐션 기반 디코더 융합으로 미세 혈관 경계를 복원한다. 일관된 패치 기반 전처리 파이프라인으로 CHASE DB1과 DRIVE에서 U-PEN Mamba를 평가하고, 합성곱, 어텐션, 트랜스포머, Mamba 기반 분할 기준선과 비교한다. U-PEN Mamba는 비교 방법 중 평균 교집합 대합(mIoU)이 최고이며, 학습 가능 매개변수 21.6M으로 CHASE DB1에서 0.8394, DRIVE에서 0.8221을 달성하고 Dice 점수는 각각 0.8187, 0.8078이다. 소거 연구는 MGC 블록이 U-Net 기준선 대비 가장 큰 이득을 제공함을 보여 주며, 투영 차원과 state size는 실용적인 정확도-효율 조절을 가능하게 한다. 이 결과는 선택적 상태 공간 모델링이 매개변수 효율적 망막 혈관 분할을 위한 유망한 전역 문맥 메커니즘임을 시사한다. 코드는 https://github.com/areyesan/UPEN_Mamba 에서 이용할 수 있다.
DM3D: 오프셋 유도 특징 리샘플링을 통한 동적 Mamba 기반 포인트 클라우드 이해
DM3D: Dynamic Mamba via Offset-Guided Feature Resampling for Point Cloud Understanding
상태 공간 모델(SSM)은 포인트 클라우드의 긴 토큰 시퀀스를 선형 복잡도로 모델링하지만, 순서 없는 포인트 클라우드를 직렬화해야 한다. 기존 방법들은 주로 더 나은 토큰 순서를 설계하거나 학습함으로써 이 요구사항을 해결한다. 그러나 잘 구성된 순서라도 불규칙한 3D 표면에서 모든 지역 관계를 보존할 수는 없다. 고정된 시퀀스는 여전히 인덱스상으로는 가깝지만 3D 공간에서는 멀거나 서로 다른 객체 부분에 속하는 점들을 섞을 수 있다. 우리는 기본 토큰 순서를 유지하면서 지역적 특징 지원과 상태 전파를 적응적으로 조정하는 동적 Mamba 아키텍처인 DM3D를 제안한다. 첫째, 지역 특징 문맥에 따라 DM3D는 전역 순열(permutation)을 구성하지 않고 공간 및 시퀀스 오프셋을 학습한다. 이어서 공간 오프셋은 3D 공간에서 샘플링 앵커를 조정하고, 시퀀스 오프셋은 지역 시퀀스 윈도우 내에서 특징 리샘플링을 유도하여, 서로 다른 슬롯이 각자의 정체성을 유지하면서 겹치는 지역 지원에서 특징을 가져올 수 있게 한다. 이 설계는 원래 순회(traversal)의 전역 prior를 보존하면서 각 토큰이 더 적합한 지역 문맥을 집계할 수 있게 한다. 둘째, 상태 업데이트는 인접 시퀀스 위치에 있는 점들 사이의 3D 거리에 의해 변조(modulated)되어, 이 점들이 공간적으로 멀리 떨어져 있을 때 정보 전파를 줄인다. DM3D는 ModelNet40에서 95.2% 정확도, ScanObjectNN의 PB_T50_RS 분할에서 93.3% 정확도, ShapeNetPart에서 84.8% 클래스 mIoU를 달성한다. 벤치마크 데이터셋에 대한 광범위한 실험은 DM3D가 강력하고 경쟁력 있는 성능을 달성함을 보여주며, 포인트 클라우드 이해를 위한 지역 특징 적응의 효과를 검증한다.
지연 연산자 SSM: 구조화된 상태 공간 모델링을 위한 기하학적 프레임워크
Lag Operator SSMs: A Geometric Framework for Structured State Space Modeling
구조화된 상태 공간 모델(SSM)은 최근 인기 있는 Mamba 아키텍처의 핵심이며, 시퀀스 모델링을 위한 강력한 도구이다. 그러나 이들의 이론적 기반은 연속 시간 모델링과 이후 이산화를 거치는 복잡한 다단계 과정에 의존하므로 직관을 흐릴 수 있다. 우리는 유연하고 모듈적인 이산 시간 SSM을 구성하기 위한 직접적이고 제1원칙(first-principles) 기반의 프레임워크를 제안한다. 우리의 접근법은 새로운 지연 연산자(lag operator)에 기반하며, 시스템의 기저 함수들이 한 타임스텝에서 다음 타임스텝으로 넘어갈 때 우리가 도메인 확장(domain expansion)이라고 부르는 변화를 겪는 방식을 측정하여 이산 시간 재귀 관계를 기하학적으로 유도한다. 결과적인 상태 행렬은 이 연산자를 포함하는 단일 내적을 통해 계산되며, 서로 다른 기저 함수와 시간 왜곡(time-warping) 방안을 유연하게 결합하여 새로운 SSM을 만들 수 있는 모듈형 설계 공간을 가능하게 한다. 프레임워크의 검증을 위해, 특정 인스턴스가 영향력 있는 HiPPO 모델의 재귀 관계를 정확히 복원함을 보여준다. 수치 시뮬레이션은 우리의 유도를 확인하며, 유연하고 견고한 시퀀스 모델을 설계하기 위한 새로운 이론적 도구를 제공한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.