The following learning problem arises naturally in various applications: Given a finite sample from a categorical or count time series, can we learn a function of the sample that (nearly) maximizes the probability of correctly guessing the values of a given portion of the data using the values from the remaining parts? Unlike classical approaches in statistical inference, our approach avoids explicitly estimating the conditional probabilities.
We propose a non-parametric guessing function with a learning rate independent of the alphabet size. Our analysis focuses on a broad class of time series models that encompasses finite-order Markov chains, some hidden Markov chains, Poisson regression for count processes, and one-dimensional Gibbs measures.
We provide a margin condition that controls the rate of convergence for the risk. Additionally, we establish a minimax lower bound for the convergence rate of the risk associated with our guessing problem. This lower bound matches the upper bound achieved by our estimator up to a logarithmic factor, demonstrating its near-optimality.
논문 ID : 2501.06547제목 : 무한 알파벳을 가진 범주형 시계열에서의 경로별 추측저자 : J.-R. Chazottes, S. Gallo, D. Y. Takahashi분류 : math.ST math.PR stat.TH발표 시간 : 2025년 10월 16일논문 링크 : https://arxiv.org/abs/2501.06547 본 논문은 다양한 응용 분야에서 자연스럽게 발생하는 학습 문제를 연구한다: 범주형 또는 계수 시계열의 유한 표본이 주어졌을 때, 나머지 데이터 부분을 사용하여 주어진 데이터 부분의 값을 올바르게 추측할 확률을 (근사적으로) 최대화하는 표본 함수를 학습할 수 있는가? 고전적 통계 추론 방법과 달리, 본 논문의 방법은 조건부 확률의 명시적 추정을 회피한다. 저자들은 알파벳 크기와 무관한 학습률을 가진 비모수 추측 함수를 제안하며, 분석은 유한 차수 마르코프 연쇄, 특정 숨겨진 마르코프 연쇄, 계수 과정의 포아송 회귀, 1차원 깁스 측도를 포함한 광범위한 시계열 모델 클래스를 다룬다.
실제 응용 주도 : 예측과 보간은 과학의 기초 문제이며, 범주형 시계열에서 광범위한 응용을 가지고 있다. 특히 대규모 언어 모델의 등장 배경에서, 이러한 모델들은 큰 알파벳을 가진 범주형 시계열 모델로 볼 수 있다.전통적 방법의 한계 :고전적 방법은 모든 전이 확률의 점별 추정에 의존한다 알파벳 크기가 크거나 전이 확률이 작을 때 추측이 어려워진다 희귀 사건의 정확한 추정은 많은 데이터를 필요로 하며, 이는 실제로 불가능하다 전통적 방법은 큰 알파벳의 경우 모든 가능한 전이의 확률을 추정하기 어려울 수 있다 기존 과제 :알파벳 크기와 의존성 차수가 일반적으로 모두 높다 무한 의존성과 알파벳 크기를 가진 모델을 처리해야 한다 저자들은 더 실용적인 접근 방식을 제안한다: 가장 가능성 높은 사건, 즉 가장 가능성 높은 결과를 예측하는 데 초점을 맞추고, 희귀하고 가능성 낮은 사건에는 더 적은 가중치를 부여한다. 이 방법은 특히 크거나 무한한 기호 집합을 가진 수열을 처리하는 데 적합하다.
비모수 추측 함수 제안 : 알파벳 크기와 무관한 학습률로 광범위한 범주형 시계열 클래스에 적용 가능이론적 프레임워크 수립 : 임의의 알파벳 크기에 적용 가능하며, 메모리 또는 차수에 대한 제약을 완화한계 조건 제공 : 위험의 수렴률 제어미니맥스 하한 수립 : 제안된 추정기의 근사 최적성 증명, 하한과 상한이 로그 인수 내에서 일치무한 알파벳 경우 최초 고려 : 알파벳 크기에 선험적 상한이 없거나 표본 크기에 따라 증가할 수 있을 때 중요두 개의 독립적이고 동일하게 분포된 과정 복사본 ( X j ) j ∈ Z (X_j)_{j \in \mathbb{Z}} ( X j ) j ∈ Z ( Y j ) j ∈ Z (Y_j)_{j \in \mathbb{Z}} ( Y j ) j ∈ Z D D D G G G
추정기 정의 :
f ^ D , G n : A n × A D → A G \hat{f}^n_{D,G} : A^n \times A^D \to A^G f ^ D , G n : A n × A D → A G
초과 위험 :
R ( f ^ D , G n ) : = sup b ∈ A D ( P ~ ( f ^ D , G n ( Y D ) ≠ Y G ∣ Y D = b ) − inf a ∈ A G P ~ ( a ≠ Y G ∣ Y D = b ) ) P ~ ( Y D = b ) R(\hat{f}^n_{D,G}) := \sup_{b \in A^D} \left( \tilde{P}(\hat{f}^n_{D,G}(Y_D) \neq Y_G | Y_D = b) - \inf_{a \in A^G} \tilde{P}(a \neq Y_G | Y_D = b) \right) \tilde{P}(Y_D = b) R ( f ^ D , G n ) := sup b ∈ A D ( P ~ ( f ^ D , G n ( Y D ) = Y G ∣ Y D = b ) − inf a ∈ A G P ~ ( a = Y G ∣ Y D = b ) ) P ~ ( Y D = b )
핵심 추정기 :
f ^ D , G n [ X 1 n ] ( b ) : = arg max a ∈ A G N D , G n [ X 1 n ] ( b , a ) N D , G n [ X 1 n ] ( b ) \hat{f}^n_{D,G}[X^n_1](b) := \arg\max_{a \in A^G} \frac{N^n_{D,G}[X^n_1](b,a)}{N^n_{D,G}[X^n_1](b)} f ^ D , G n [ X 1 n ] ( b ) := arg max a ∈ A G N D , G n [ X 1 n ] ( b ) N D , G n [ X 1 n ] ( b , a )
여기서 계수 함수는 다음과 같이 정의된다:
N D , G n [ X 1 n ] ( b , a ) : = ∑ i = 0 n − 1 1 { X θ i D = b , X θ i G = a } N^n_{D,G}[X^n_1](b,a) := \sum_{i=0}^{n-1} \mathbf{1}\{X_{\theta^i D} = b, X_{\theta^i G} = a\} N D , G n [ X 1 n ] ( b , a ) := ∑ i = 0 n − 1 1 { X θ i D = b , X θ i G = a }
가정 A : ( X i ) i ∈ Z (X_i)_{i \in \mathbb{Z}} ( X i ) i ∈ Z P P P Γ ( P ) : = ∏ j = 0 ∞ ( 1 − Var j ( p ) ) > 0 \Gamma(P) := \prod_{j=0}^{\infty} (1 - \text{Var}_j(p)) > 0 Γ ( P ) := ∏ j = 0 ∞ ( 1 − Var j ( p )) > 0
여기서 변분은 다음과 같이 정의된다:
Var n ( p ) : = sup { 1 2 ∑ a ∈ A ∣ p ( a ∣ x ) − p ( a ∣ y ) ∣ : x , y ∈ A Z − , x i = y i , i ≥ − n } \text{Var}_n(p) := \sup\left\{\frac{1}{2}\sum_{a \in A}|p(a|x) - p(a|y)| : x,y \in A^{\mathbb{Z}_-}, x_i = y_i, i \geq -n\right\} Var n ( p ) := sup { 2 1 ∑ a ∈ A ∣ p ( a ∣ x ) − p ( a ∣ y ) ∣ : x , y ∈ A Z − , x i = y i , i ≥ − n }
각 b ∈ A D b \in A^D b ∈ A D δ D , G ( b ) = inf { P ( X G ≠ c , X D = b ) − inf a ∈ A G P ( X G ≠ a , X D = b ) > 0 : c ∈ A G } \delta_{D,G}(b) = \inf\{P(X_G \neq c, X_D = b) - \inf_{a \in A^G} P(X_G \neq a, X_D = b) > 0 : c \in A^G\} δ D , G ( b ) = inf { P ( X G = c , X D = b ) − inf a ∈ A G P ( X G = a , X D = b ) > 0 : c ∈ A G }
한계: δ D , G : = inf b ∈ A D δ D , G ( b ) \delta_{D,G} := \inf_{b \in A^D} \delta_{D,G}(b) δ D , G := inf b ∈ A D δ D , G ( b )
표본 크기 n n n R ( f ^ D , G n ) ≤ ε ∧ β D , G R(\hat{f}^n_{D,G}) \leq \varepsilon \land \beta_{D,G} R ( f ^ D , G n ) ≤ ε ∧ β D , G
한계 조건이 약할 때 : δ n n log n → 0 \delta_n\sqrt{\frac{n}{\log n}} \to 0 δ n l o g n n → 0 R ( f ^ D , G n ) ≤ 1 2 log n n ∧ β D , G R(\hat{f}^n_{D,G}) \leq \frac{1}{2}\sqrt{\frac{\log n}{n}} \land \beta_{D,G} R ( f ^ D , G n ) ≤ 2 1 n l o g n ∧ β D , G 한계 조건이 강할 때 : δ n n log n → ∞ \delta_n\sqrt{\frac{n}{\log n}} \to \infty δ n l o g n n → ∞ R ( f ^ D , G n ) ≤ exp ( − Γ 2 n δ n 2 8 ( ∣ G ∣ + ∣ D ∣ ) 2 ) ∧ β D , G R(\hat{f}^n_{D,G}) \leq \exp\left(-\frac{\Gamma^2 n \delta_n^2}{8(|G|+|D|)^2}\right) \land \beta_{D,G} R ( f ^ D , G n ) ≤ exp ( − 8 ( ∣ G ∣ + ∣ D ∣ ) 2 Γ 2 n δ n 2 ) ∧ β D , G 두 가지 경우에서 미니맥스 하한을 수립한다:
한계가 작은 경우 :
inf ψ n ∈ Ψ n sup P ∈ P n R ( ψ n ; P ) ≥ e − 1 n ( 1 4 ) ∣ G ∣ + ∣ D ∣ \inf_{\psi_n \in \Psi_n} \sup_{P \in \mathcal{P}_n} R(\psi_n; P) \geq \frac{e^{-1}}{\sqrt{n}}\left(\frac{1}{4}\right)^{|G|+|D|} inf ψ n ∈ Ψ n sup P ∈ P n R ( ψ n ; P ) ≥ n e − 1 ( 4 1 ) ∣ G ∣ + ∣ D ∣ 한계가 큰 경우 :
inf ψ n ∈ Ψ n sup P ∈ Q n R ( ψ n ; P ) ≥ δ n e − n δ n 2 ( 1 4 ) ∣ D ∣ + ∣ G ∣ \inf_{\psi_n \in \Psi_n} \sup_{P \in \mathcal{Q}_n} R(\psi_n; P) \geq \delta_n e^{-n\delta_n^2}\left(\frac{1}{4}\right)^{|D|+|G|} inf ψ n ∈ Ψ n sup P ∈ Q n R ( ψ n ; P ) ≥ δ n e − n δ n 2 ( 4 1 ) ∣ D ∣ + ∣ G ∣ 논문은 가정 A가 다양한 중요 모델에 적용됨을 보여준다:
상태 공간 A A A Q Q Q d ( Q ) : = sup a , b ∈ A ∥ Q ( a , ⋅ ) − Q ( b , ⋅ ) ∥ T V < 1 d(Q) := \sup_{a,b \in A} \|Q(a,\cdot) - Q(b,\cdot)\|_{TV} < 1 d ( Q ) := sup a , b ∈ A ∥ Q ( a , ⋅ ) − Q ( b , ⋅ ) ∥ T V < 1
이진 자기회귀 과정의 전이 확률:
p ( a ∣ x ) = Υ ( a ∑ j = 1 ∞ ξ j x − j + a ξ 0 ) p(a|x) = \Upsilon\left(a\sum_{j=1}^{\infty}\xi_j x_{-j} + a\xi_0\right) p ( a ∣ x ) = Υ ( a ∑ j = 1 ∞ ξ j x − j + a ξ 0 )
계수 시계열의 포아송 회귀 모델:
p ( a ∣ x ) = e − v ( x ) v ( x ) a a ! p(a|x) = \frac{e^{-v(x)}v(x)^a}{a!} p ( a ∣ x ) = a ! e − v ( x ) v ( x ) a v ( x ) = exp ( ∑ j = 1 ∞ ξ j min { x − j , c } ) v(x) = \exp\left(\sum_{j=1}^{\infty}\xi_j \min\{x_{-j}, c\}\right) v ( x ) = exp ( ∑ j = 1 ∞ ξ j min { x − j , c } )
1차원 깁스 측도는 다음을 만족한다:
P ( X Λ = x Λ ∣ X Λ c = y Λ c ) = exp ( − β H Λ Φ ( x Λ y Λ c ) ) Z Λ Φ ( y ) P(X_\Lambda = x_\Lambda | X_{\Lambda^c} = y_{\Lambda^c}) = \frac{\exp(-\beta H^\Phi_\Lambda(x_\Lambda y_{\Lambda^c}))}{Z^\Phi_\Lambda(y)} P ( X Λ = x Λ ∣ X Λ c = y Λ c ) = Z Λ Φ ( y ) e x p ( − β H Λ Φ ( x Λ y Λ c ))
명시적 확률 추정 회피 : 모든 조건부 확률을 추정할 필요가 없으며, 가장 가능성 높은 결과에만 초점알파벳 크기 무관 학습률 : 크거나 무한한 알파벳을 처리하는 핵심 장점Dvoretzky-Kiefer-Wolfowitz 유형 부등식 : 무작위 연쇄에 대한 새로운 집중 부등식 수립통일된 프레임워크 : 광범위한 시계열 모델 클래스를 포함집중 부등식 : 수정된 Dvoretzky-Kiefer-Wolfowitz 부등식 사용결합 방법 : 다양한 조건 하에서 확률 차이 제어Le Cam 유형 논증 : 미니맥스 하한 수립변분 분석 : 포텐셜 함수의 진동을 통한 변분 제어명제 3.1 : β D , G \beta_{D,G} β D , G 명제 4.1 : 깁스 측도에 대한 구체적 변분 경계 제공정리 A.1 : Dvoretzky-Kiefer-Wolfowitz 유형 부등식의 확장고전적 예측 : 전이 확률의 점별 추정 기반PAC 학습 프레임워크 : 조건부 확률 학습의 최적 율 연구모수 회귀 모델 : 유연성이 있으나 가정이 제한적큰 알파벳 처리 : 학습률이 알파벳 크기에 의존하지 않음비모수 방법 : 모수 모델의 제한적 가정 회피이론적 보장 : 근사 최적 수렴률 제공무한 알파벳에 적용 가능한 비모수 추측 방법 제안 알파벳 크기와 무관한 학습률 수립 방법의 근사 최적성 증명 (로그 인수 내) 광범위한 시계열 모델 클래스에 대한 통일된 프레임워크 제공 가정 A의 검증 : 실제 응용에서 가정 A 검증이 도전적일 수 있음유한 표본 성능 : 이론적 결과는 점근적이며, 유한 표본 행동은 다를 수 있음계산 복잡성 : 논문이 알고리즘의 계산 복잡성을 상세히 논의하지 않음알고리즘 구현 : 효율적인 알고리즘 구현 개발실제 응용 : 대규모 언어 모델 등 실제 응용에서 방법 검증다른 손실 함수로의 확장 : 다양한 위험 측도 고려이론적 기여 현저함 : 무한 알파벳 경우를 최초로 처리하며 완전한 이론적 프레임워크 수립방법 혁신성 강함 : 명시적 확률 추정을 회피하는 아이디어는 실용적 가치가 높음분석 심화 : 상한과 일치하는 하한 제공으로 근사 최적성 증명적용 범위 광범위 : 통일된 프레임워크가 다양한 중요 시계열 모델을 포함실험 검증 부재 : 순수 이론 논문으로 수치 실험이나 실제 응용 사례 미제공알고리즘 세부사항 부족 : 실제 구현 및 계산 복잡성에 대한 상세 논의 부재가정 검증 어려움 : 실제 환경에서 가정 A 검증 방법이 불명확이론적 가치 높음 : 큰 알파벳 시계열 처리를 위한 새로운 이론적 도구 제공실용적 잠재력 큼 : 대규모 언어 모델 등 현대 응용에서 중요한 의미방법 일반성 : 프레임워크가 다른 관련 문제에도 적용 가능할 수 있음대규모 언어 모델 : 어휘가 큰 텍스트 생성 작업생물정보학 : DNA/단백질 수열 분석네트워크 트래픽 분석 : 큰 상태 공간을 가진 네트워크 행동 예측금융 시계열 : 고빈도 거래 데이터 분석논문은 26편의 관련 문헌을 인용하며, 마르코프 연쇄 이론, 통계 학습 이론, 동역학계 및 확률론 등 다양한 분야의 중요 연구를 포함하여 본 논문의 이론적 기초를 견고히 한다.
