سلاسل عشوائية ذات ذاكرة متغيرة الطول

لنفترض نظامًا يتكون من مصباح ومراقب وباب بينهما. للمصباح حالتان محتملتان : مضاء، ويرمز له بالرقم 1، أو مطفأ، ويرمز له بالرقم 0. عندما يكون المصباح مضاءً، قد يرى المراقب الضوء من خلال الباب، وذلك بحسب حالة الباب في تلك اللحظة: مفتوح، ويرمز له بالرقم 1، أو مغلق، ويرمز له بالرقم 0. هذه الحالات مستقلة عن الحالة الأصلية للمصباح.

يترك${\displaystyle (X_{n})_{n\geq 0}}$سلسلة ماركوف التي تمثل حالة المصباح، بقيم في${\displaystyle A={0,1}}$ودع${\displaystyle p}$لتكن مصفوفة انتقال احتمالية . ولتكن أيضًا${\displaystyle (\xi _{n})_{n\geq 0}}$لتكن سلسلة من المتغيرات العشوائية المستقلة التي تمثل حالات الباب، وتأخذ أيضًا قيمًا في${\displaystyle A}$، بغض النظر عن السلسلة${\displaystyle (X_{n})_{n\geq 0}}$ومثل ذلك

${\displaystyle \mathbb {P} (\xi _{n}=1)=1-\varepsilon }$

أين${\displaystyle 0<\epsilon <1}$عرّف تسلسلاً جديداً${\displaystyle (Z_{n})_{n\geq 0}}$بحيث

${\displaystyle Z_{n}=X_{n}\xi _{n}}$لكل${\displaystyle (Z_{n})_{n\geq 0}.}$

لتحديد آخر لحظة تمكن فيها المراقب من رؤية المصباح مضاءً، أي لتحديد أقل لحظة${\displaystyle k}$، مع${\displaystyle k<n}$في أي${\displaystyle Z_{k}=1}$.

باستخدام شجرة السياق، من الممكن تمثيل الحالات السابقة للتسلسل، مما يوضح أيها ذو صلة لتحديد الحالة التالية.

السلسلة العشوائية${\displaystyle (Z_{n})_{n\in \mathbb {Z} }}$إذن، هي سلسلة ذات ذاكرة متغيرة الطول، تأخذ قيمًا في${\displaystyle A}$ومتوافق مع شجرة السياق الاحتمالية${\displaystyle (\tau ,p)}$، أين

${\displaystyle \tau =\{1,10,100,\cdots \}\cup \{0^{\infty }\}.}$

في مقال "نظام ضغط بيانات شامل" ^{[ 1 ]} ، قدم ريسانين خوارزمية متسقة لتقدير شجرة السياق الاحتمالية التي تولد البيانات. ويمكن تلخيص وظيفة هذه الخوارزمية في خطوتين:

1. بالنظر إلى العينة التي تنتجها سلسلة ذات ذاكرة ذات طول متغير، نبدأ بالشجرة القصوى التي تكون فروعها جميع المرشحين للسياقات الخاصة بالعينة؛
2. ثم تُقطع فروع هذه الشجرة حتى نحصل على أصغر شجرة تتناسب مع البيانات. ويتم تحديد ما إذا كان سيتم تقصير السياق أم لا من خلال دالة ربح معينة، مثل نسبة احتمالية اللوغاريتم.

يكون${\displaystyle X_{0},\ldots ,X_{n-1}}$عينة من شجرة احتمالية محدودة${\displaystyle (\tau ,p)}$لأي تسلسل${\displaystyle x_{-j}^{-1}}$مع${\displaystyle j\leq n}$، من الممكن الإشارة إلى${\displaystyle N_{n}(x_{-j}^{-1})}$عدد مرات ظهور التسلسل في العينة، أي

${\displaystyle N_{n}(x_{-j}^{-1})=\sum _{t=0}^{nj}\mathbf {1} \left\{X_{t}^{t+j-1}=x_{-j}^{-1}\right\}}$

قام ريسانين أولاً ببناء مرشح أقصى سياق، معطى بواسطة${\displaystyle X_{nK(n)}^{n-1}}$، أين${\displaystyle K(n)=C\log {n}}$و${\displaystyle C}$هو ثابت موجب اختياري. والسبب البديهي لاختيار${\displaystyle C\log {n}}$ينشأ ذلك من استحالة تقدير احتمالات التسلسلات ذات الأطوال الأكبر من${\displaystyle \log {n}}$استنادًا إلى عينة بحجم${\displaystyle n}$.

ومن ثم، يقوم ريسانين بتقصير المرشح الأقصى من خلال قطع الفروع تباعًا وفقًا لتسلسل من الاختبارات القائمة على نسبة الاحتمالية الإحصائية. بتعريف أكثر رسمية، إذا كان bANnxk1b0 يُعرّف مُقدِّر احتمالية الانتقال${\displaystyle p}$بواسطة

${\displaystyle {\hat {p}}_{n}(a\mid x_{-k}^{-1})={\frac {N_{n}(x_{-k}^{-1}a)}{\sum _{b\in A}N_{n}(x_{-k}^{-1}b)}}}$

أين${\displaystyle x_{-j}^{-1}a=(x_{-j},\ldots ,x_{-1},a)}$. لو${\displaystyle \sum _{b\in A}N_{n}(x_{-k}^{-1}b)\,=\,0}$، يُعرِّف${\displaystyle {\hat {p}}_{n}(a\mid x_{-k}^{-1})\,=\,1/|A|}$.

ل${\displaystyle i\geq 1}$، يُعرِّف

${\displaystyle \Lambda _{n}(x_{-i}^{-1})\,=\,2\,\sum _{y\in A}\sum _{a\in A}N_{n}(yx_{-i}^{-1}a)\log \left[{\frac {{\hat {p}}_{n}(a\mid x_{-i}^{-1}y)}{{\hat {p}}_{n}(a\mid x_{-i}^{-1})}}\right]\,}$

أين${\displaystyle yx_{-i}^{-1}=(y,x_{-i},\ldots ,x_{-1})}$و

${\displaystyle {\hat {p}}_{n}(a\mid x_{-i}^{-1}y)={\frac {N_{n}(yx_{-i}^{-1}a)}{\sum _{b\in A}N_{n}(yx_{-i}^{-1}b)}}.}$

لاحظ أن${\displaystyle \Lambda _{n}(x_{-i}^{-1})}$تمثل هذه النسبة نسبة احتمالية اللوغاريتم لاختبار اتساق العينة مع شجرة السياق الاحتمالية${\displaystyle (\tau ,p)}$مقابل البديل الذي يتوافق مع${\displaystyle (\tau ',p')}$، أين${\displaystyle \tau }$و${\displaystyle \tau '}$لا يختلفان إلا بمجموعة من العقد الشقيقة.

يتم تحديد طول السياق المقدر الحالي بواسطة

${\displaystyle {\hat {\ell }}_{n}(X_{0}^{n-1})=\max \left\{i=1,\ldots ,K(n):\Lambda _{n}(X_{ni}^{n-1})\,>\,C\log n\right\}\,}$

أين${\displaystyle C}$أي ثابت موجب. وأخيرًا، بحسب ريسانين، ^{[ 1 ]} توجد النتيجة التالية. معطى${\displaystyle X_{0},\ldots ,X_{n-1}}$من شجرة سياق احتمالية محدودة${\displaystyle (\tau ,p)}$، ثم

${\displaystyle P\left({\hat {\ell }}_{n}(X_{0}^{n-1})\neq \ell (X_{0}^{n-1})\right)\longrightarrow 0,}$

متى${\displaystyle n\rightarrow \infty }$.

تقدير شجرة السياق باستخدام معيار معلومات بايز (BIC) مع ثابت جزاء${\displaystyle c>0}$يُعرَّف بأنه

$//$

يتم حساب معيار المُعظِّم الأصغر ^{[ 3 ]} عن طريق اختيار أصغر شجرة τ من مجموعة أشجار الأبطال C بحيث

${\displaystyle \lim _{n\to \infty }{\frac {\log L_{\tau }(X_{1}^{n})-\log L_{\hat {\tau }}(X_{1}^{n})}{n}}=0}$