استقرای دستور زبان

**استقرای دستور زبان** یا **استنتاج دستور زبان**؛  فرایندی در یادگیری ماشین است که در آن، یک دستور زبان صوری از روی مجموعه‌ای از مشاهده‌ها آموخته می‌شود؛ این دستور زبان معمولاً به‌شکل مجموعه‌ای از قواعد بازنویسی (تولیدها) یا به‌صورت یک ماشین حالت محدود/خودکار ساخته می‌شود تا مدلی فراهم کند که ویژگی‌های اشیای مشاهده‌شده را توضیح دهد. به‌طور کلی، استنتاج دستور زبان شاخه‌ای از یادگیری ماشین است که در آن فضای نمونه‌ها از اشیای ترکیبیِ گسسته مانند رشته‌ها، درخت‌ها و گراف‌ها تشکیل می‌شود.

## رده‌های دستور زبان
استنتاج دستور زبان در بسیاری از پژوهش‌ها به‌طور ویژه بر مسئلهٔ **یادگیری ماشین‌های حالت محدود** از انواع گوناگون متمرکز بوده است (برای جزئیات این رویکردها بنگرید به مقالهٔ «استقرای زبان‌های منظم»)، زیرا از دههٔ ۱۹۸۰ به بعد الگوریتم‌های کارآمدی برای حل این مسئله در دسترس بوده‌اند.

از آغاز قرن بیست‌ویکم، این رویکردها به مسئلهٔ استنتاج دستور زبان‌های مستقل از متن و صورت‌بندی‌های غنی‌تر نیز گسترش یافته‌اند؛ از جمله دستور زبان‌های چندمستقل از متن و دستور زبان‌های چندمستقل از متن موازی. از دیگر رده‌های دستور زبانی که استنتاج آن‌ها مورد مطالعه قرار گرفته است می‌توان به دستور زبان‌های رده‌بندی ترکیبی، دستور زبان‌های مستقل از متن احتمالی، دستور زبان‌های بافتی و زبان‌های الگو اشاره کرد.

## مدل‌های یادگیری
ساده‌ترین شکلِ یادگیری زمانی رخ می‌دهد که الگوریتم یادگیری صرفاً مجموعه‌ای از نمونه‌ها را که از زبانِ مورد نظر استخراج شده‌اند دریافت می‌کند؛ هدف این است که زبان تنها بر اساس نمونه‌های متعلق به آن آموخته شود (و به‌ندرت، بر اساس نمونه‌های نقض‌کننده، یعنی نمونه‌هایی که به زبان تعلق ندارند). با این حال، مدل‌های یادگیری دیگری نیز مورد مطالعه قرار گرفته‌اند. یکی از جایگزین‌های پرکاربرد، حالتی است که در آن یادگیرنده می‌تواند پرسش‌های عضویت مطرح کند؛ همانند مدل یادگیری با پرسش دقیق یا مدل معلم حداقلِ کافی که توسط آنگلوین معرفی شده است.

## روش‌شناسی‌ها
روش‌های متنوعی برای استنتاج دستور زبان وجود دارد. از منابع کلاسیک در این حوزه می‌توان به آثار فو (۱۹۷۷) و فو (۱۹۸۲) اشاره کرد. همچنین دودا، هارت و استورک (۲۰۰۱) بخشی کوتاه را به این مسئله اختصاص داده‌اند و به منابع متعددی ارجاع داده‌اند. روش پایه‌ایِ آزمون‌وخطایی که آن‌ها معرفی می‌کنند، در ادامه توضیح داده می‌شود. برای رویکردهایی که به‌طور خاص به استنتاج زیررده‌هایی از زبان‌های منظم می‌پردازند، می‌توان به «استقرای زبان‌های منظم» مراجعه کرد. کتاب درسی نسبتاً جدیدتری از دلا ایگوئرا (۲۰۱۰) نظریهٔ استنتاج دستور زبان برای زبان‌های منظم و خودکارهای متناهی را پوشش می‌دهد. همچنین دالیزیا، فِری و گریفونی مروری ارائه کرده‌اند که روش‌های استنتاج دستور زبان برای زبان‌های طبیعی را بررسی می‌کند.

### استنتاج دستور زبان‌های احتمالی
روش‌های متعددی برای استنتاج دستور زبان‌های مستقل از متن احتمالی ارائه شده است.

### استنتاج دستور زبان به روش آزمون‌وخطا
روشی که در بخش ۸٫۷ کتاب دودا، هارت و استورک (۲۰۰۱) پیشنهاد شده است، بر حدس‌زدن تدریجیِ قواعد دستور زبان (تولیدها) و آزمون آن‌ها در برابر مشاهده‌های مثبت و منفی استوار است. مجموعهٔ قواعد به‌گونه‌ای گسترش می‌یابد که بتواند هر نمونهٔ مثبت را تولید کند؛ اما اگر همین مجموعهٔ قواعد قادر به تولید یک نمونهٔ منفی نیز باشد، باید کنار گذاشته شود. این رویکرد را می‌توان نوعی «آزمون فرضیه» دانست و شباهت‌هایی با الگوریتم «فضای نسخه» میچل دارد. کتاب دودا، هارت و استورک نمونه‌ای ساده ارائه می‌کند که این فرایند را به‌خوبی نشان می‌دهد، اما عملی بودن چنین روش آزمون‌وخطای بدون راهنما برای مسائل بزرگ‌تر محل تردید است.

### استنتاج دستور زبان با الگوریتم‌های ژنتیک
استقرای دستور زبان با استفاده از الگوریتم‌های تکاملی فرایندی است که در آن نمایشِ دستور زبانِ یک زبان هدف از طریق یک فرایند تکاملی تحول می‌یابد. دستور زبان‌های صوری را می‌توان به‌سادگی به‌صورت ساختارهای درختی از قواعد تولید نمایش داد و سپس عملگرهای تکاملی را بر آن‌ها اعمال کرد. این دسته از الگوریتم‌ها ریشه در پارادایم برنامه‌نویسی ژنتیکی دارند که توسط جان کوزا معرفی شد. برخی پژوهش‌های اولیه در زمینهٔ زبان‌های صوری ساده از نمایش رشته‌های دودویی در الگوریتم‌های ژنتیک استفاده می‌کردند، اما ساختار ذاتاً سلسله‌مراتبیِ دستور زبان‌ها در قالب EBNF باعث شد که نمایش درختی رویکردی انعطاف‌پذیرتر باشد.

کوزا برنامه‌های لیسپ را به‌صورت درخت نمایش می‌داد و توانست همتاهایی برای عملگرهای ژنتیکی در مجموعهٔ عملگرهای استاندارد درختی بیابد. برای مثال، جابه‌جایی زیردرخت‌ها معادل فرایند ترکیب ژنتیکی است که در آن زیررشته‌هایی از یک کُد ژنتیکی به فردی در نسل بعد منتقل می‌شوند. برازندگی با امتیازدهی به خروجی توابع برنامه‌های لیسپ سنجیده می‌شود. شباهت میان نمایش درختی برنامه‌های لیسپ و نمایش درختی دستور زبان‌ها، امکان به‌کارگیری برنامه‌نویسی ژنتیکی در استنتاج دستور زبان را فراهم کرده است.

در مسئلهٔ استقرای دستور زبان، جابه‌جایی زیردرخت‌ها متناظر با تعویض قواعد تولیدی است که امکان تجزیهٔ عبارت‌هایی از زبان را فراهم می‌کنند. عملگر برازندگیِ دستور زبان بر پایهٔ معیاری تعریف می‌شود که نشان می‌دهد دستور زبان تا چه حد در تجزیهٔ مجموعه‌ای از جمله‌های زبان هدف موفق بوده است. در نمایش درختی یک دستور زبان، نماد پایانیِ یک قاعدهٔ تولید با یک برگ درخت متناظر است و گره‌های والد آن معمولاً نمادهای ناپایانی (مانند گروه اسمی یا گروه فعلی) را نشان می‌دهند. در نهایت، ریشهٔ درخت می‌تواند متناظر با نماد ناپایانیِ جمله باشد.

### استنتاج دستور زبان با الگوریتم‌های حریصانه
همانند دیگر الگوریتم‌های حریصانه، الگوریتم‌های حریصانهٔ استنتاج دستور زبان نیز به‌صورت تکراری تصمیم‌هایی می‌گیرند که در آن مرحله بهترین به نظر می‌رسند. این تصمیم‌ها معمولاً شامل ایجاد قواعد جدید، حذف قواعد موجود، انتخاب قاعدهٔ قابل‌اعمال یا ادغام برخی قواعد هستند. از آنجا که تعریف «مرحله» و «بهترین» می‌تواند متفاوت باشد، الگوریتم‌های حریصانهٔ گوناگونی برای استنتاج دستور زبان وجود دارد.

برخی از الگوریتم‌های تولید دستور زبان مستقل از متن پس از خواندن هر نماد تصمیم‌گیری می‌کنند، از جمله:
* الگوریتم لمپل–زیو–ولش که یک دستور زبان مستقل از متن را به‌صورت قطعی تولید می‌کند، به‌گونه‌ای که ذخیرهٔ تنها قاعدهٔ شروعِ دستور زبان تولیدشده کافی است.
* الگوریتم سکیویتور و اصلاحات آن.

برخی دیگر از الگوریتم‌ها ابتدا کل دنبالهٔ نمادها را می‌خوانند و سپس تصمیم‌گیری را آغاز می‌کنند، از جمله:
* رمزگذاری جفت‌بایتی و بهینه‌سازی‌های آن.

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

### یادگیری زبان‌های الگو
آنگلوین الگو را «رشته‌ای متشکل از نمادهای ثابت از مجموعهٔ Σ و نمادهای متغیر از مجموعه‌ای جداگانه» تعریف می‌کند. زبانِ یک الگو مجموعهٔ همهٔ نمونه‌های زمینیِ غیرتهی آن است؛ یعنی تمام رشته‌هایی که از جایگزینی سازگار نمادهای متغیر با رشته‌های غیرتهیِ نمادهای ثابت به‌دست می‌آیند. یک الگو برای یک مجموعهٔ متناهی از رشته‌های ورودی «توصیفی» نامیده می‌شود اگر زبان آن، از نظر شمول مجموعه‌ای، در میان همهٔ زبان‌های الگویی که مجموعهٔ ورودی را دربر می‌گیرند کمینه باشد.

آنگلوین الگوریتمی چندجمله‌ای ارائه می‌کند که برای یک مجموعهٔ ورودی از رشته‌ها، همهٔ الگوهای توصیفی با یک متغیر x را محاسبه می‌کند. برای این منظور، خودکاری ساخته می‌شود که همهٔ الگوهای بالقوهٔ مرتبط را نمایش می‌دهد؛ با استفاده از استدلال‌های دقیق دربارهٔ طول واژه‌ها و با اتکا به این فرض که x تنها متغیر است، می‌توان تعداد حالت‌ها را به‌طور چشمگیری کاهش داد.

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

### نظریهٔ الگو
نظریهٔ الگو که توسط اولف گرِناندر ارائه شد، چارچوبی ریاضی برای توصیف دانش دربارهٔ جهان به‌صورت الگوهاست. این نظریه با بسیاری از رویکردهای دیگر هوش مصنوعی تفاوت دارد، زیرا به‌جای آغاز از تجویز الگوریتم‌ها و سازوکارهای تشخیص و دسته‌بندی الگو، واژگانی ارائه می‌کند تا مفاهیم الگوها به‌صورت دقیق صورت‌بندی و بازبیان شوند.

رویکرد آماری این نظریه از این جهت نوآورانه بود که اهداف زیر را دنبال می‌کرد:
* شناسایی متغیرهای پنهانِ یک مجموعه‌داده با استفاده از داده‌های واقعی، نه محرک‌های مصنوعی که در آن زمان رایج بودند.
* صورت‌بندی توزیع‌های پیشین برای متغیرهای پنهان و مدل‌هایی برای متغیرهای مشاهده‌شده که رأس‌های یک گراف شبیه به گیبس را تشکیل می‌دهند.
* مطالعهٔ تصادفی‌بودن و تغییرپذیری این گراف‌ها.
* ایجاد رده‌های پایه‌ای از مدل‌های تصادفی از طریق فهرست‌کردن دگرریختی‌های الگوها.
* سنتز (نمونه‌گیری) از مدل‌ها، نه صرفاً تحلیل سیگنال‌ها با استفاده از آن‌ها.

از نظر پوشش ریاضی، نظریهٔ الگو حوزه‌هایی چون جبر و آمار، و نیز ویژگی‌های موضعی توپولوژیک و ویژگی‌های سراسری آنتروپیک را در بر می‌گیرد.

## کاربردها
اصلِ استنتاج دستور زبان در جنبه‌های گوناگونِ پردازش زبان طبیعی به‌کار گرفته شده است و (در میان مسائل متعدد دیگر) در حوزه‌هایی مانند تجزیهٔ معنایی، درک زبان طبیعی، ترجمهٔ مبتنی بر مثال، اکتساب زبان، فشرده‌سازی مبتنی بر دستور زبان و کشف ناهنجاری کاربرد داشته است.

### الگوریتم‌های فشرده‌سازی
بندانگشتی|دستور زبان خطی مستقیم (با نماد شروع ß) برای جملهٔ دومِ اعلامیهٔ استقلال ایالات متحدهٔ آمریکا. هر نویسهٔ آبی‌رنگ نشان‌دهندهٔ یک نماد ناپایانی است که از طریق فشرده‌سازی جمله با الگوریتم gzip به‌دست آمده است.
کُدهای مبتنی بر دستور زبان یا فشرده‌سازی مبتنی بر دستور زبان دسته‌ای از الگوریتم‌های فشرده‌سازی هستند که بر ایدهٔ ساختن یک دستور زبان مستقل از متن (CFG) برای رشته‌ای که باید فشرده شود تکیه دارند. از جملهٔ این الگوریتم‌ها می‌توان به نمونه‌هایی از الگوریتم‌های فشرده‌سازی بدون اتلافِ همگانی اشاره کرد. برای فشرده‌سازی یک دنبالهٔ داده x=x1⋯xn، یک کُد مبتنی بر دستور زبان، دنبالهٔ x را به یک دستور زبان مستقل از متن G تبدیل می‌کند. مسئلهٔ یافتن کوچک‌ترین دستور زبان برای یک دنبالهٔ ورودی (که به «مسئلهٔ کوچک‌ترین دستور زبان» معروف است) یک مسئلهٔ NP-سخت محسوب می‌شود؛ ازاین‌رو، الگوریتم‌های متعددی برای تبدیل رشته به دستور زبان، از دیدگاه‌های نظری و عملی، پیشنهاد شده‌اند.

به‌طور معمول، دستور زبانِ تولیدشدهٔ G در مرحله‌ای بعدی با استفاده از رمزگذارهای آماری، مانند کُدگذاری حسابی، بیشتر فشرده می‌شود.

## منابع

رده:استنباط
رده:دستور زبان