گرامر مستقل از متن تصادفی

گرامر مستقل از متن تصادفی (به انگلیسی: Stochastic context-free grammar) یک گرامر مستقل از متن است که هر کدام از قواعد تولید آن با یک احتمال همراه شده‌است. در این نوع گرامر هر درخت اشتقاق دارای یک احتمال است که این احتمال برابر است با حاصلضرب احتمال قواعد به کار رفته در فرایند اشتقاق آن؛ بنابراین در گرامر مستقل از متن تصادفی، برخی از اشتقاق‌ها پایدارتر از دیگری هستند. به همان طریقی که مدل‌های پنهان مارکوف، تعمیم یافتهٔ گرامرهای منظم هستند، گرامرهای مستقل از متن تصادفی نیز تعمیم یافتهٔ گرامرهای مستقل از متن‌اند. گرامرهای مستقل از متن تصادفی در زمینه‌های گسترده‌ای، از پردازش زبان‌های طبیعی گرفته تا بیوانفورماتیک، کاربرد دارند. گرامرهای مستقل از متن تصادفی، شکل خاصی از گرامرهای مستقل از متن وزن‌دار هستند.

الگوریتم‌ها

یک گرامر مستقل از متن تصادفی، یک رشته از زبان را می‌تواند از مسیرهای مختلفی تولید کند که به هر کدام از آن‌ها یک اشتقاق گفته می‌شود. از آنجا که هر کدام از قواعد گرامر مستقل از متن تصادفی دارای یک احتمال می‌باشند، هر اشتقاق نیز دارای یک احتمال می‌گردد که برابر است با حاصلضرب احتمال‌های قواعد به کار رفته در آن اشتقاق. از میان اشتقاق‌های ممکن برای یک رشته، آن اشتقاقی که دارای بیشترین احتمال است به عنوان محتمل‌ترین اشتقاق انتخاب می‌گردد که به آن اشتقاق Viterbi گفته می‌شود. گونهٔ تغییر یافته‌ای از الگوریتم CYK با گرفتن یک رشته از زبان و یک گرامر مستقل از متن تصادفی به عنوان ورودی، اشتقاق Viterbi آن را پیدا می‌کند.

از الگوریتم Inside-Outside می‌توان برای محاسبه کردن مجموع احتمالات تولید یک رشته توسط یک گرامر مستقل از متن خطی استفاده کرد. مجموع احتمالات تولید یک رشته توسط یک گرامر مستقل از متن تصادفی برابر است با حاصل جمع احتمال‌های همهٔ اشتقاق‌های ممکن برای یک رشته توسط آن گرامر. این احتمال به‌طور شهودی معیاری از ثبات یک رشته با گرامر داده شده است.

در برخی مواقع می‌خواهیم با داشتن مجموعه‌ای از رشته‌ها و اشتقاق‌های آن‌ها، احتمال‌های قواعد یک گرامر مستقل از متن تصادفی را به دست آوریم به طوری که گرامر، رشته‌های داده شده را با اشتقاق‌های داده شده تولید کند. در اینجا نیز الگوریتم Inside-Outside به عنوان قسمتی از الگوریتم بیشینه کردن امید ریاضی(EM) استفاده می‌گردد.

کاربردها

پردازش زبان‌های طبیعی

گرامرهای مستقل از متن در آغاز در طی تلاش برای مدل کردن زبان‌های طبیعی به وجود آمدند. این گرامرها به صورت قواعدی قطعی تعریف شدند که البته هنوز برای کاربردهای گوناگونی من‌جمله طراحی زبان‌های برنامه‌سازی کاربرد دارند. گرامرهای مستقل از متن تصادفی در طی تلاش برای گسترش دادن گرامرهای مستقل از متن برای مقابله با پیچیدگی‌های زبان‌های طبیعی (به عنوان مثال: ابهام) به وجود آمدند. ابهام بدین معنی است که ممکن است برای یک دنباله از کلمات بیش از یک اشتقاق وجود داشته باشد که به دلایل مختلفی اتفاق می‌افتد، مانند کلماتی که املای یکسان و معانی مختلفی دارند.

یک راه مواجه شدن با اشتقاق‌های مبهم، اضافه کردن قواعد بیشتر به گرامر است. راه دیگر اولویت بندی قواعد گرامراست. هر دو این روش‌ها دارای مشکلاتی همچون زیاد شدن بیش از حد تعداد قواعد یا تولید رشته‌های ناخواسته می‌باشند. گرامرهای تصادفی این مشکلات را با استفاده از تنظیم قواعد بر اساس فرکانس تعداد زیادی اشتقاق حل می‌کنند. این امر باعث می‌شود تا آن‌هایی که بیشترین شباهت را دارند انتخاب شوند.

بیوانفورماتیک

گرامرهای مستقل از متن در مدل کردن ساختار دوم آران‌ای بسیار خوب عمل می‌کنند. ساختار دوم آران‌ای شامل نوکلئوتیدهایی است درون یک مولکول تک رشته‌ای آران‌ای که مکمل یکدیگرند و جفت باز تشکیل می‌دهند. این جفت شدن بازها از لحاظ زیست‌شناسی دارای اهمیت هستند، زیرا با عملکرد آران‌ای در ارتباط‌اند. اکثر این جفت بازها می‌توانند در یک گرامر مستقل از متن نشان داده شوند(یک استثنا مهم، شبه گره‌ها هستند). به عنوان مثال، گرامر زیر را در نظر بگیرید که در آن a، c، g و u نشان دهندهٔ نوکلئوتیدها هستند و S سمبل شروع و تنها ناپایانهٔ گرامر است:

S → aSu | cSg | gSc | uSa

این گرامر مستقل از متن ساده مولکول آران‌ایی را نشان می‌دهد که کلاً از دو نوع ناحیه مکمل ساخته شده‌است و تنها جفت بازهای A-U و C-G در آن وجود دارند. با اضافه کردن احتمال به گرامرهای مستقل از متن پیچیده‌تر، می‌توان جفت بازهای بیشتر و الگوهای پیچیده‌تر یک مولکول آران‌ای را مدل کرد.

مشارکت‌کنندگان ویکی‌پدیا. «Stochastic context-free grammar». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۶ ژوئن ۲۰۱۱.