تجزیه و تحلیل مبتنی بر ساختار و تجزیه بدون متن

محاسبه درخت ساختار عبارتی یک جمله با استفاده از گرامرهای بدون متن، الگوریتم‌های برنامه‌ریزی پویا مانند CKY و Earley، و گرامرهای احتمالی که ابهام را برطرف می‌کنند.

Definition

تجزیه و تحلیل مبتنی بر ساختار، یک درخت ساختار عبارتی تو در تو را بر اساس یک گرامر بدون متن به یک جمله اختصاص می‌دهد، که معمولاً محتمل‌ترین درخت را تحت یک گرامر احتمالی انتخاب می‌کند.

Scope

این موضوع شامل تجزیه و تحلیل با گرامرهای بدون متن: الگوریتم‌های CKY و Earley، فرم نرمال چامسکی، گرامرهای بدون متن احتمالی و اصلاحات واژگانی آن‌ها، و تجزیه‌کننده‌های آماری آموزش‌دیده با درخت‌بانک می‌شود. همچنین به رفع ابهام و ارزیابی تجزیه‌کننده می‌پردازد. نمایش‌های وابستگی و فرمالیسم‌های غیر بدون متن در موضوعات مرتبط دیگر بررسی می‌شوند.

Core questions

• چگونه الگوریتم CKY یک جمله را در زمان مکعبی تجزیه می‌کند؟
• چرا گرامرها اغلب باید ابتدا به فرم نرمال چامسکی تبدیل شوند؟
• چگونه گرامرهای احتمالی و واژگانی به رفع ابهام کمک می‌کنند؟
• دقت تجزیه‌کننده در مقایسه با یک درخت‌بانک چگونه اندازه‌گیری می‌شود؟

Key concepts

• گرامر بدون متن
• الگوریتم CKY
• الگوریتم Earley
• فرم نرمال چامسکی
• گرامر بدون متن احتمالی
• واژگانی‌سازی
• درخت تجزیه
• درخت‌بانک

Key theories

تجزیه و تحلیل برنامه‌ریزی پویا

الگوریتم‌های CKY و Earley با پر کردن یک نمودار از زیرساخت‌ها، تمام تجزیه‌ها را در زمان چندجمله‌ای محاسبه می‌کنند و از انفجار نمایی جستجوی ساده جلوگیری می‌کنند.

تجزیه و تحلیل احتمالی واژگانی‌شده

مشروط کردن احتمالات قواعد بر کلمات اصلی، دقت تجزیه را با دربرگرفتن ترجیحات واژگانی که در PCFGهای ساده وجود ندارد، به طور قابل توجهی بهبود می‌بخشد.

History

الگوریتم CKY (دهه ۱۹۶۰) و الگوریتم Earley در سال ۱۹۷۰، تشخیص کارآمد بدون متن را فراهم کردند. با ظهور Penn Treebank، تجزیه‌کننده‌های احتمالی و سپس واژگانی از کالینز و چارنیاک در اواخر دهه ۱۹۹۰ به دقت بالایی دست یافتند و دوران تجزیه آماری را پیش از مدل‌های عصبی تعریف کردند.

Debates

چه مقدار واژگانی‌سازی لازم است؟

تجزیه‌کننده‌های واژگانی‌شده دقیق اما پراکنده هستند؛ بحث بر سر این بود که آیا PCFGهای غیرواژگانی‌شده با تقسیم حالت دقیق می‌توانند با آن‌ها برابری کنند، که کارهای بعدی نشان داد تا حدی ممکن است.

Key figures

• Jay Earley
• Michael Collins
• Eugene Charniak

Seminal works

• earley1970
• collins2003

Frequently asked questions

نمودار در تجزیه و تحلیل چیست؟

نمودار جدولی است که هر جزء جزئی یافت شده در هر بازه از جمله را ذخیره می‌کند، به طوری که زیرساخت‌های مشترک یک بار محاسبه شده و دوباره استفاده می‌شوند، که منجر به تجزیه در زمان چندجمله‌ای می‌شود.