2025-11-24T23:22:17.314102

Pathwise guessing in categorical time series with unbounded alphabets

Chazottes, Gallo, Takahashi
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.
academic

বিভাগীয় সময় শ্রেণীবিন্যাসে পথ অনুমান অসীম বর্ণমালা সহ

মৌলিক তথ্য

  • পত্র আইডি: 2501.06547
  • শিরোনাম: বিভাগীয় সময় শ্রেণীবিন্যাসে পথ অনুমান অসীম বর্ণমালা সহ
  • লেখক: J.-R. Chazottes, S. Gallo, D. Y. Takahashi
  • শ্রেণীবিভাগ: math.ST math.PR stat.TH
  • প্রকাশনার সময়: অক্টোবর ১৬, ২০২৫
  • পত্র লিঙ্ক: https://arxiv.org/abs/2501.06547

সারসংক্ষেপ

এই পত্রটি বিভিন্ন প্রয়োগে স্বাভাবিকভাবে উদ্ভূত একটি শেখার সমস্যা অধ্যয়ন করে: বিভাগীয় বা গণনা সময় শ্রেণীবিন্যাসের সীমিত নমুনা দেওয়া, একটি নমুনা ফাংশন শিখতে পারে যা অবশিষ্ট ডেটা ব্যবহার করে প্রদত্ত ডেটা মূল্যের সঠিক অনুমানের সম্ভাবনা (প্রায়) সর্বাধিক করে? ক্লাসিক্যাল পরিসংখ্যান অনুমানের পদ্ধতির বিপরীতে, এই পত্রের পদ্ধতি শর্তসাপেক্ষ সম্ভাবনার স্পষ্ট অনুমান এড়ায়। লেখকরা একটি অ-প্যারামেট্রিক অনুমান ফাংশন প্রস্তাব করেছেন যার শেখার হার বর্ণমালার আকারের উপর নির্ভর করে না, বিশ্লেষণ সীমিত-ক্রম মার্কভ শৃঙ্খল, নির্দিষ্ট লুকানো মার্কভ শৃঙ্খল, গণনা প্রক্রিয়ার পয়সন রিগ্রেশন এবং এক-মাত্রিক গিবস পরিমাপ সহ বিস্তৃত সময় শ্রেণীবিন্যাস মডেল শ্রেণী অন্তর্ভুক্ত করে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার গুরুত্ব

১. ব্যবহারিক প্রয়োগ চালিত: পূর্বাভাস এবং অন্তর্বেশন বিজ্ঞানে মৌলিক সমস্যা, বিভাগীয় সময় শ্রেণীবিন্যাসে ব্যাপক প্রয়োগ সহ, বিশেষত বড় ভাষা মডেলের উত্থানের প্রেক্ষাপটে, যা বড় বর্ণমালা সহ বিভাগীয় সময় শ্রেণীবিন্যাস মডেল হিসাবে দেখা যায়।

२. ঐতিহ্যবাহী পদ্ধতির সীমাবদ্ধতা:

  • ক্লাসিক্যাল পদ্ধতি সমস্ত রূপান্তর সম্ভাবনার পয়েন্টওয়াইজ অনুমানের উপর নির্ভর করে
  • যখন বর্ণমালার আকার বড় বা রূপান্তর সম্ভাবনা ছোট হয়, অনুমান কঠিন হয়ে ওঠে
  • বিরল ঘটনা সঠিকভাবে অনুমান করতে বিশাল পরিমাণ ডেটা প্রয়োজন, যা ব্যবহারিকভাবে অসম্ভব

३. বিদ্যমান চ্যালেঞ্জ:

  • বর্ণমালার আকার এবং নির্ভরতার ক্রম সাধারণত উভয়ই উচ্চ
  • অসীম নির্ভরতা এবং বর্ণমালার আকার সহ মডেল পরিচালনা করা প্রয়োজন
  • ঐতিহ্যবাহী পদ্ধতি বড় বর্ণমালার ক্ষেত্রে সমস্ত সম্ভাব্য রূপান্তরের সম্ভাবনা অনুমান করতে কঠিন হতে পারে

গবেষণা প্রেরণা

লেখকরা একটি আরও ব্যবহারিক পদ্ধতি প্রস্তাব করেছেন: সবচেয়ে সম্ভাব্য ঘটনাগুলিতে ফোকাস করা, অর্থাৎ সবচেয়ে সম্ভাব্য ফলাফল পূর্বাভাস দেওয়া, যখন বিরল, অসম্ভাব্য ঘটনাগুলিতে কম ওজন দেওয়া। এই পদ্ধতি বিশেষভাবে বড় বা অসীম প্রতীক সেট সহ অনুক্রম পরিচালনার জন্য উপযুক্ত।

মূল অবদান

१. অ-প্যারামেট্রিক অনুমান ফাংশন প্রস্তাব: শেখার হার বর্ণমালার আকারের উপর নির্ভর করে না, বিভাগীয় সময় শ্রেণীবিন্যাসের বিস্তৃত শ্রেণীতে প্রযোজ্য २. তাত্ত্বিক কাঠামো প্রতিষ্ঠা: যেকোনো বর্ণমালার আকারের জন্য প্রযোজ্য, স্মৃতি বা ক্রমের উপর সীমাবদ্ধতা শিথিল করে ३. প্রান্তিক শর্ত প্রদান: ঝুঁকির সংমিশ্রণ হার নিয়ন্ত্রণ করে ४. মিনিম্যাক্স নিম্ন সীমা প্রতিষ্ঠা: প্রস্তাবিত অনুমানকারীর আনুমানিক সর্বোত্তমতা প্রমাণ করে, নিম্ন সীমা এবং উপরের সীমা লগারিদমিক ফ্যাক্টরের মধ্যে মেলে ५. প্রথমবারের জন্য অসীম বর্ণমালার ক্ষেত্রে বিবেচনা: যখন বর্ণমালার আকারের কোনো পূর্বনির্ধারিত উপরের সীমা নেই বা নমুনা আকারের সাথে বৃদ্ধি পায় তখন গুরুত্বপূর্ণ

পদ্ধতির বিস্তারিত বিবরণ

কাজের সংজ্ঞা

দুটি স্বাধীন সমবিতরণ প্রক্রিয়া কপি (Xj)j∈Z(X_j)_{j \in \mathbb{Z}} এবং (Yj)j∈Z(Y_j)_{j \in \mathbb{Z}} দেওয়া, লক্ষ্য হল ডেটাসেট DD এর তথ্য ব্যবহার করে অনুমান সেট GG এর মূল্য পূর্বাভাস দেওয়া।

অনুমানকারীর সংজ্ঞা: f^D,Gn:An×AD→AGf̂^n_{D,G} : A^n \times A^D \to A^G

অতিরিক্ত ঝুঁকি: R(f^D,Gn):=sup⁡b∈AD(P~(f^D,Gn(YD)≠YG∣YD=b)−inf⁡a∈AGP~(a≠YG∣YD=b))P~(YD=b)R(f̂^n_{D,G}) := \sup_{b \in A^D} \left( \tilde{P}(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)

মডেল স্থাপত্য

মূল অনুমানকারী: f^D,Gn[X1n](b):=arg⁡max⁡a∈AGND,Gn[X1n](b,a)ND,Gn[X1n](b)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)}

যেখানে গণনা ফাংশন সংজ্ঞায়িত করা হয়: ND,Gn[X1n](b,a):=∑i=0n−11{XθiD=b,XθiG=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\}

প্রধান অনুমান

অনুমান A: (Xi)i∈Z(X_i)_{i \in \mathbb{Z}} পরিমাপ PP সহ একটি স্থির প্রক্রিয়া হতে দিন, যদি সন্তুষ্ট হয়: Γ(P):=∏j=0∞(1−Varj(p))>0\Gamma(P) := \prod_{j=0}^{\infty} (1 - \text{Var}_j(p)) > 0

যেখানে ভেদ সংজ্ঞায়িত করা হয়: Varn(p):=sup⁡{12∑a∈A∣p(a∣x)−p(a∣y)∣:x,y∈AZ−,xi=yi,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\}

প্রান্তিক শর্ত

প্রতিটি b∈ADb \in A^D এর জন্য, সংজ্ঞায়িত করুন: δD,G(b)=inf⁡{P(XG≠c,XD=b)−inf⁡a∈AGP(XG≠a,XD=b)>0:c∈AG}\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:=inf⁡b∈ADδD,G(b)\delta_{D,G} := \inf_{b \in A^D} \delta_{D,G}(b)

প্রধান তাত্ত্বিক ফলাফল

উপরের সীমা ফলাফল (উপপাদ্য ३.१)

যদি নমুনা আকার nn নির্দিষ্ট শর্ত পূরণ করে, তাহলে: R(f^D,Gn)≤ε∧βD,GR(f̂^n_{D,G}) \leq \varepsilon \land \beta_{D,G}

সংমিশ্রণ হার (অনুসিদ্ধান্ত ३.१)

१. যখন প্রান্তিক শর্ত দুর্বল হয়: যদি δnnlog⁡n→0\delta_n\sqrt{\frac{n}{\log n}} \to 0, তাহলে: R(f^D,Gn)≤12log⁡nn∧βD,GR(f̂^n_{D,G}) \leq \frac{1}{2}\sqrt{\frac{\log n}{n}} \land \beta_{D,G}

२. যখন প্রান্তিক শর্ত শক্তিশালী হয়: যদি δnnlog⁡n→∞\delta_n\sqrt{\frac{n}{\log n}} \to \infty, তাহলে: R(f^D,Gn)≤exp⁡(−Γ2nδn28(∣G∣+∣D∣)2)∧βD,GR(f̂^n_{D,G}) \leq \exp\left(-\frac{\Gamma^2 n \delta_n^2}{8(|G|+|D|)^2}\right) \land \beta_{D,G}

মিনিম্যাক্স নিম্ন সীমা (উপপাদ্য ३.२)

দুটি ক্ষেত্রে মিনিম্যাক্স নিম্ন সীমা প্রতিষ্ঠা করে:

१. প্রান্তিক ছোট ক্ষেত্রে: inf⁡ψn∈Ψnsup⁡P∈PnR(ψn;P)≥e−1n(14)∣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∈Ψnsup⁡P∈QnR(ψn;P)≥δne−nδn2(14)∣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|}

প্রয়োগের উদাহরণ

পত্রটি দেখায় যে অনুমান A বিভিন্ন গুরুত্বপূর্ণ মডেলের জন্য প্রযোজ্য:

মার্কভ শৃঙ্খল

অবস্থা স্থান AA এবং রূপান্তর ম্যাট্রিক্স QQ সহ মার্কভ শৃঙ্খলের জন্য, শর্ত Dobrushin ergodic সহগে সরল হয়: d(Q):=sup⁡a,b∈A∥Q(a,⋅)−Q(b,⋅)∥TV<1d(Q) := \sup_{a,b \in A} \|Q(a,\cdot) - Q(b,\cdot)\|_{TV} < 1

স্বয়ংরিয় রিগ্রেশন মডেল

দ্বিমুখী স্বয়ংরিয়গ্রেশন প্রক্রিয়ার রূপান্তর সম্ভাবনা: p(a∣x)=Υ(a∑j=1∞ξjx−j+aξ0)p(a|x) = \Upsilon\left(a\sum_{j=1}^{\infty}\xi_j x_{-j} + a\xi_0\right)

পয়সন রিগ্রেশন

গণনা সময় শ্রেণীবিন্যাসের পয়সন রিগ্রেশন মডেল: p(a∣x)=e−v(x)v(x)aa!p(a|x) = \frac{e^{-v(x)}v(x)^a}{a!} যেখানে v(x)=exp⁡(∑j=1∞ξjmin⁡{x−j,c})v(x) = \exp\left(\sum_{j=1}^{\infty}\xi_j \min\{x_{-j}, c\}\right)

গিবস পরিমাপ

এক-মাত্রিক গিবস পরিমাপ সন্তুষ্ট করে: 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)}

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

१. স্পষ্ট সম্ভাবনা অনুমান এড়ানো: সমস্ত শর্তসাপেক্ষ সম্ভাবনা অনুমান করার প্রয়োজন নেই, শুধুমাত্র সবচেয়ে সম্ভাব্য ফলাফলের উপর ফোকাস করুন २. বর্ণমালা আকার নির্ভরশীল শেখার হার: এটি বড় বা অসীম বর্ণমালা পরিচালনার মূল সুবিধা ३. Dvoretzky-Kiefer-Wolfowitz ধরনের অসমতা: র্যান্ডম চেইনের জন্য নতুন ঘনীভূত অসমতা প্রতিষ্ঠা করা হয়েছে ४. একীভূত কাঠামো: বিস্তৃত সময় শ্রেণীবিন্যাস মডেল শ্রেণী অন্তর্ভুক্ত করে

পরীক্ষা এবং প্রমাণ কৌশল

প্রধান প্রমাণ কৌশল

१. ঘনীভূত অসমতা: সংশোধিত Dvoretzky-Kiefer-Wolfowitz অসমতা ব্যবহার করা হয় २. সংযোগ পদ্ধতি: বিভিন্ন শর্তের অধীনে সম্ভাবনা পার্থক্য নিয়ন্ত্রণের জন্য ३. Le Cam ধরনের যুক্তি: মিনিম্যাক্স নিম্ন সীমা প্রতিষ্ঠার জন্য ४. ভেদ বিশ্লেষণ: সম্ভাব্য ফাংশনের দোলনের মাধ্যমে ভেদ নিয়ন্ত্রণ

মূল লেম্মা

  • প্রস্তাব ३.१: βD,G\beta_{D,G} এবং সেট আকারের মধ্যে সম্পর্ক প্রতিষ্ঠা করে
  • প্রস্তাব ४.१: গিবস পরিমাপের জন্য নির্দিষ্ট ভেদ সীমা প্রদান করে
  • উপপাদ্য A.१: Dvoretzky-Kiefer-Wolfowitz ধরনের অসমতার সম্প্রসারণ

সম্পর্কিত কাজ

ঐতিহ্যবাহী পদ্ধতি

१. ক্লাসিক্যাল পূর্বাভাস: রূপান্তর সম্ভাবনার পয়েন্টওয়াইজ অনুমানের উপর ভিত্তি করে २. PAC শেখার কাঠামো: শর্তসাপেক্ষ সম্ভাবনা শেখার সর্বোত্তম হার অধ্যয়ন করে ३. প্যারামেট্রিক রিগ্রেশন মডেল: নমনীয়তা কিন্তু সীমাবদ্ধ অনুমান সহ

এই পত্রের সুবিধা

१. বড় বর্ণমালা পরিচালনা: শেখার হার বর্ণমালার আকারের উপর নির্ভর করে না २. অ-প্যারামেট্রিক পদ্ধতি: প্যারামেট্রিক মডেলের সীমাবদ্ধ অনুমান এড়ায় ३. তাত্ত্বিক গ্যারান্টি: আনুমানিক সর্বোত্তম সংমিশ্রণ হার প্রদান করে

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. অসীম বর্ণমালার জন্য প্রযোজ্য অ-প্যারামেট্রিক অনুমান পদ্ধতি প্রস্তাব করা হয়েছে २. বর্ণমালার আকারের সাথে অসম্পর্কিত শেখার হার প্রতিষ্ঠা করা হয়েছে ३. পদ্ধতির আনুমানিক সর্বোত্তমতা প্রমাণ করা হয়েছে (লগারিদমিক ফ্যাক্টরের মধ্যে) ४. বিস্তৃত সময় শ্রেণীবিন্যাস মডেল শ্রেণীর জন্য একীভূত কাঠামো প্রদান করা হয়েছে

সীমাবদ্ধতা

१. অনুমান A এর যাচাইকরণ: ব্যবহারিক প্রয়োগে অনুমান A যাচাই করা চ্যালেঞ্জিং হতে পারে २. সীমিত নমুনা কর্মক্ষমতা: তাত্ত্বিক ফলাফল অ্যাসিম্পটোটিক, সীমিত নমুনা আচরণ ভিন্ন হতে পারে ३. গণনা জটিলতা: পত্রটি অ্যালগরিদমের গণনা জটিলতা বিস্তারিতভাবে আলোচনা করে না

ভবিষ্যত দিকনির্দেশনা

१. অ্যালগরিদম বাস্তবায়ন: দক্ষ অ্যালগরিদম বাস্তবায়ন বিকাশ করা २. ব্যবহারিক প্রয়োগ: বড় ভাষা মডেল ইত্যাদি ব্যবহারিক প্রয়োগে পদ্ধতি যাচাই করা ३. অন্যান্য ক্ষতি ফাংশনে সম্প্রসারণ: বিভিন্ন ঝুঁকি পরিমাপ বিবেচনা করা

গভীর মূল্যায়ন

শক্তি

१. উল্লেখযোগ্য তাত্ত্বিক অবদান: প্রথমবারের জন্য অসীম বর্ণমালার ক্ষেত্রে পরিচালনা, সম্পূর্ণ তাত্ত্বিক কাঠামো প্রতিষ্ঠা করা হয়েছে २. শক্তিশালী পদ্ধতি উদ্ভাবন: স্পষ্ট সম্ভাবনা অনুমান এড়ানোর ধারণা ব্যবহারিক মূল্য রাখে ३. গভীর বিশ্লেষণ: উপরের সীমা এবং মেলানো নিম্ন সীমা প্রদান করে, আনুমানিক সর্বোত্তমতা প্রমাণ করে ४. বিস্তৃত প্রযোজ্যতা: কাঠামো বিভিন্ন গুরুত্বপূর্ণ সময় শ্রেণীবিন্যাস মডেল অন্তর্ভুক্ত করে

অপূর্ণতা

१. পরীক্ষামূলক যাচাইকরণের অভাব: পত্রটি বিশুদ্ধ তাত্ত্বিক, সংখ্যাগত পরীক্ষা বা ব্যবহারিক প্রয়োগ কেস প্রদান করে না २. অ্যালগরিদম বিবরণ অপর্যাপ্ত: ব্যবহারিক বাস্তবায়ন এবং গণনা জটিলতা বিস্তারিতভাবে আলোচনা করা হয় না ३. অনুমান যাচাইকরণ কঠিন: অনুমান A এর ব্যবহারিক যাচাইকরণ পদ্ধতি স্পষ্ট নয়

প্রভাব

१. উচ্চ তাত্ত্বিক মূল্য: বড় বর্ণমালা সময় শ্রেণীবিন্যাস পরিচালনার জন্য নতুন তাত্ত্বিক সরঞ্জাম প্রদান করে २. বড় ব্যবহারিক সম্ভাবনা: বড় ভাষা মডেল ইত্যাদি আধুনিক প্রয়োগে গুরুত্বপূর্ণ অর্থ রাখে ३. পদ্ধতি সর্বজনীনতা: কাঠামো অন্যান্য সম্পর্কিত সমস্যায় প্রযোজ্য হতে পারে

প্রযোজ্য পরিস্থিতি

१. বড় ভাষা মডেল: বড় শব্দভাণ্ডার সহ পাঠ্য উৎপাদন কাজ २. জৈব তথ্যবিজ্ঞান: DNA/প্রোটিন অনুক্রম বিশ্লেষণ ३. নেটওয়ার্ক ট্রাফিক বিশ্লেষণ: বড় অবস্থা স্থান সহ নেটওয়ার্ক আচরণ পূর্বাভাস ४. আর্থিক সময় শ্রেণীবিন্যাস: উচ্চ ফ্রিকোয়েন্সি ট্রেডিং ডেটা বিশ্লেষণ

তথ্যসূত্র

পত্রটি ২৬টি সম্পর্কিত তথ্যসূত্র উদ্ধৃত করে, যা মার্কভ শৃঙ্খল তত্ত্ব, পরিসংখ্যান শেখার তত্ত্ব, গতিশীল সিস্টেম এবং সম্ভাবনা তত্ত্বের একাধিক ক্ষেত্রের গুরুত্বপূর্ণ কাজ অন্তর্ভুক্ত করে, এই পত্রের তাত্ত্বিক ভিত্তির জন্য দৃঢ় সমর্থন প্রদান করে।