تحليل المكونات والتحليل الخالي من السياق

حساب شجرة بنية العبارة لجملة باستخدام قواعد النحو الخالية من السياق، وخوارزميات البرمجة الديناميكية مثل CKY و Earley، وقواعد النحو الاحتمالية التي تحل الغموض.

Definition

يُسند تحليل المكونات شجرة بنية عبارة متداخلة إلى جملة وفقًا لقواعد النحو الخالية من السياق، وعادةً ما يختار الشجرة الأكثر احتمالًا ضمن قواعد النحو الاحتمالية.

Scope

يغطي التحليل باستخدام قواعد النحو الخالية من السياق: خوارزميات CKY و Earley، والشكل الطبيعي لتشومسكي، وقواعد النحو الخالية من السياق الاحتمالية وتعديلاتها المعجمية، والمحللات الإحصائية المدربة على بنوك الأشجار. ويتناول حل الغموض وتقييم المحلل. وتُعالج تمثيلات التبعية والصيغ غير الخالية من السياق في مواضيع ذات صلة.

Core questions

• كيف تحلل خوارزمية CKY جملة في زمن تكعيبي؟
• لماذا يجب غالبًا تحويل قواعد النحو أولاً إلى الشكل الطبيعي لتشومسكي؟
• كيف تحسن قواعد النحو الاحتمالية والمعجمية إزالة الغموض؟
• كيف تُقاس دقة المحلل مقارنة ببنك الأشجار؟

Key concepts

• قواعد النحو الخالية من السياق
• خوارزمية CKY
• خوارزمية Earley
• الشكل الطبيعي لتشومسكي
• قواعد النحو الخالية من السياق الاحتمالية
• التمثيل المعجمي
• شجرة التحليل
• بنك الأشجار

Key theories

تحليل البرمجة الديناميكية

تحسب خوارزميات CKY و Earley جميع التحليلات في زمن متعدد الحدود عن طريق ملء جدول من المكونات الفرعية، مما يتجنب التضخم الأسي للبحث الساذج.

التحليل الاحتمالي المعجمي

يؤدي تكييف احتمالات القواعد على الكلمات الرئيسية إلى تحسين دقة التحليل بشكل كبير من خلال التقاط التفضيلات المعجمية الغائبة عن قواعد النحو الخالية من السياق الاحتمالية البسيطة.

History

قدمت خوارزمية CKY (في الستينيات) وخوارزمية Earley لعام 1970 تعرفًا فعالًا خاليًا من السياق. ومع بنك بنسلفانيا للأشجار (Penn Treebank)، حققت المحللات الاحتمالية ثم المعجمية من كولينز وتشارنياك دقة عالية في أواخر التسعينيات، مما حدد عصر التحليل الإحصائي قبل النماذج العصبية.

Debates

ما مقدار التمثيل المعجمي المطلوب؟

المحللات المعجمية دقيقة ولكنها متفرقة؛ دار النقاش حول ما إذا كانت قواعد النحو الخالية من السياق الاحتمالية غير المعجمية مع تقسيم الحالة الدقيق يمكن أن تضاهيها، وهو ما أظهرته الأعمال اللاحقة أنه ممكن جزئيًا.

Key figures

• Jay Earley
• Michael Collins
• Eugene Charniak

Seminal works

• earley1970
• collins2003

Frequently asked questions

ما هو المخطط في التحليل؟

المخطط هو جدول يخزن كل مكون جزئي تم العثور عليه عبر كل مدى من الجملة، بحيث يتم حساب الهياكل الفرعية المشتركة مرة واحدة وإعادة استخدامها، مما يوفر تحليلًا في زمن متعدد الحدود.