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

گرامر مستقل از متن تصادفی یک گرامر مستقل از متن است که هر کدام از قواعد تولید آن با یک احتمال همراه شده‌است. در این نوع گرامر هر درخت اشتقاق دارای یک احتمال است که این احتمال برابر است با حاصلضرب احتمال قواعد به کار رفته در فرایند اشتقاق آن؛ بنابراین در گرامر مستقل از متن تصادفی، برخی از اشتقاق‌ها پایدارتر از دیگری هستند. به همان طریقی که مدل‌های پنهان مارکوف، تعمیم یافته‌ی گرامرهای منظم هستند، گرامرهای مستقل از متن تصادفی نیز تعمیم یافته‌ی گرامرهای مستقل از متن اند. گرامرهای مستقل از متن تصادفی در زمینه‌های گسترده‌ای، از پردازش زبان‌های طبیعی گرفته تا بیوانفورماتیک، کاربرد دارند. گرامرهای مستقل از متن تصادفی، شکل خاصی از گرامرهای مستقل از متن وزن‌دار هستند.
الگوریتم‌ها
یک گرامر مستقل از متن تصادفی، یک رشته از زبان را می‌تواند از مسیرهای مختلفی تولید کند که به هر کدام از آن‌ها یک اشتقاق گفته می‌شود. از آنجا که هر کدام از قواعد گرامر مستقل از متن تصادفی دارای یک احتمال می‌باشند، هر اشتقاق نیز دارای یک احتمال می‌گردد که برابر است با حاصلضرب احتمال‌های قواعد به کار رفته در آن اشتقاق. از میان اشتقاق‌های ممکن برای یک رشته، آن اشتقاقی که دارای بیشترین احتمال است به عنوان محتمل‌ترین اشتقاق انتخاب می‌گردد که به آن اشتقاق Viterbi گفته می‌شود. گونه‌ی تغییر یافته‌ای از الگوریتم CYK با گرفتن یک رشته از زبان و یک گرامر مستقل از متن تصادفی به عنوان ورودی، اشتقاق Viterbi آن را پیدا می‌کند.
از الگوریتم Inside-Outside می‌توان برای محاسبه کردن مجموع احتمالات تولید یک رشته توسط یک گرامر مستقل از متن خطی استفاده کرد. مجموع احتمالات تولید یک رشته توسط یک گرامر مستقل از متن تصادفی برابر است با حاصل جمع احتمال‌های همه‌ی اشتقاق‌های ممکن برای یک رشته توسط آن گرامر. این احتمال به طور شهودی معیاری از ثبات یک رشته با گرامر داده شده می‌باشد.
در برخی مواقع می‌خواهیم با داشتن مجموعه‌ای از رشته‌ها و اشتقاق‌های آن‌ها، احتمال‌های قواعد یک گرامر مستقل از متن تصادفی را به دست آوریم به طوری که گرامر، رشته‌های داده شده را با اشتقاق‌های داده شده تولید کند. در اینجا نیز الگوریتم Inside-Outside به عنوان قسمتی از الگوریتم بیشینه کردن امید ریاضی(EM) استفاده می‌گردد.
کاربردها
پردازش زبان‌های طبیعی
گرامرهای مستقل از متن در آغاز در طی تلاش برای مدل کردن زبان‌های طبیعی به وجود آمدند. این گرامرها به صورت قواعدی قطعی تعریف شدند که البته هنوز برای کاربردهای گوناگونی من‌جمله طراحی زبان‌های برنامه‌سازی کاربرد دارند. گرامرهای مستقل از متن تصادفی در طی تلاش برای گسترش دادن گرامرهای مستقل از متن برای مقابله با پیچیدگی‌های زبان‌های طبیعی (به عنوان مثال: ابهام) بوجود آمدند. ابهام بدین معنی است که ممکن است برای یک دنباله از کلمات بیش از یک اشتقاق وجود داشته باشد که به دلایل مختلفی اتفاق می‌افتد، مانند کلماتی که املای یکسان و معانی مختلفی دارند.
یک راه مواجه شدن با اشتقاق‌های مبهم، اضافه کردن قواعد بیشتر به گرامر است. راه دیگر اولویت بندی قواعد گرامراست. هر دو این روش‌ها دارای مشکلاتی همچون زیاد شدن بیش از حد تعداد قواعد یا تولید رشته‌های ناخواسته می‌باشند. گرامرهای تصادفی این مشکلات را با استفاده از تنظیم قواعد بر اساس فرکانس تعداد زیادی اشتقاق حل می‌کنند. این امر باعث می‌شود تا آن‌هایی که بیشترین شباهت را دارند انتخاب شوند.
بیوانفورماتیک
گرامرهای مستقل از متن در مدل کردن ساختار دوم آران‌ای بسیار خوب عمل می‌کنند. ساختار دوم آران‌ای شامل نوکلئوتیدهایی است درون یک مولکول تک رشته‌ای آران‌ای که مکمل یکدیگرند و جفت باز تشکیل می‌دهند. این جفت شدن بازها از لحاظ زیست شناسی دارای اهمیت هستند، زیرا با عملکرد آران‌ای در ارتباط اند. اکثر این جفت بازها می‌توانند در یک گرامر مستقل از متن نشان داده شوند(یک استثنا مهم، شبه گره‌ها هستند).
به عنوان مثال، گرامر زیر را در نظر بگیرید که در آن a، c، g و u نشان دهنده‌ی نوکلئوتیدها هستند و S سمبل شروع و تنها ناپایانه‌ی گرامر می‌باشد:
S → aSu | cSg | gSc | uSa
این گرامر مستقل از متن ساده مولکول آران‌ایی را نشان می‌دهد که کلا از دو نوع ناحیه مکمل ساخته شده است و تنها جفت بازهای A-U و C-G در آن وجود دارند.
با اضافه کردن احتمال به گرامرهای مستقل از متن پیچیده‌تر، می‌توان جفت بازهای بیشتر و الگوهای پیچیده‌تر یک مولکول آران‌ای را مدل کرد.