الرئيسيةعريقبحث

القواعد الاحتمالية الخالية من السياق

☰ جدول المحتويات

نشأت قواعد النحو لنمذجة سلاسل الرموز من العمل في اللغويات الحاسوبية بهدف فهم بنية اللغات الطبيعية . [1] [2] [3] وقد تم تطبيق القواعد الاحتمالية الخالية من السياق ( PCFGs ) (ق.ا.خ.س) في النمذجة الاحتمالية في معالجة اللغات الطبيعية وفي هياكل الحمض النووي الريبي بعد حوالي 40 عامًا من طرحها في اللغويات الحاسوبية . [4] [5] [6] [7] [8]

تقوم القواعد الاحتمالية النحوية الخالية من السياق بتوسيع مفهوم القواعد النحوية الخالية من السياق على غرار الطريقة التي يتم بها توسيع نماذج ماركوف الخفية لقواعد اللغة العادية. حيث يتم تعيين احتمالية معينة لكل ناتج من النواتج. احتمال الاشتقاق (تحليل) هي نتاج محصلة الاحتماليات للنواتج المستخدمة في هذا الاشتقاق. يمكن عرض هذه الاحتمالات كمعاملات معينة للنموذج، أما بالنسبة للمشاكل الكبيرة، فمن الأسهل تعلم هذه المعاملات من خلال التعلم الآلي . يتم تقييد صلاحية قواعد اللغة الاحتمالية من خلال السياق الوارد في البيانات التدريبية الخاصة بها.

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

تعريفات

الاشتقاق: عملية التوليد العكسي للجمل من خلال القواعد.

التجزئة : العثور على الاشتقاق الصحيح آلياً.

شجرة التحليل: محاذاة القواعد مع التسلسلات الموجودة.

التعريف الرسمي

على غرار القواعد الخالية من السياق ، يمكن تعريف القواعد النحوية الخالية من السياق G بواسطة قيد يتكون من خمس قيم:

  • M هي مجموعة الرموز غير الطرفية
  • T هي مجموعة الرموز الطرفية
  • R هي مجموعة قواعد الإنتاج
  • S هو رمز البداية
  • P هي مجموعة من الاحتمالات الخاصة بقواعد الإنتاج

العلاقة مع نماذج ماركوف الخفية

تقوم نماذج القواعد الاحتمالية الخالية من السياق بتوسيع قواعد اللغة الخالية من السياق بنفس الطريقة التي توسع بها بها نماذج ماركوف الخفية القواعد النحوية المنتظمة .

خوارزمية من الداخل إلى الخارج هي خوارزمية مناظرة لخوارزمية الأمام والخلف (forward-backword). وهي تحسب الاحتمال الكلي لجميع الاشتقاقات التي تتوافق مع تسلسل معين، بناءً على بعض القواعد الاحتمالية الخالية من السياق. يعادل هذا احتمالية قيام (ق.ا.خ.س) بإنشاء التسلسلات، وهو مقياس لمدى اتساق التسلسل مع قواعد معينة. تُستخدم خوارزمية من الداخل إلى الخارج في تحديد معالم النموذج لتقدير الترددات السابقة التي لوحظت من متواليات التدريب في حالة الرنا.

بناء القواعد

يتم تمثيل القواعد النحوية الخالية من السياق كمجموعة من القواعد المستوحاة من محاولات نمذجة اللغات الطبيعية. [9] القواعد مطلقة ولها تمثيل بناء جملة نموذجي يعرف باسم صيغة باكوس نور . قواعد الإنتاج تتكون من المحطة (a,b) والرموز S غير الطرفية وإشارة المجموعة الخالية التي يُمكن أيضا أن تستخدم في النهاية. في قواعد الإنتاج الخاصة بالقواعد الخالية من السياق و(ق.ا.خ.س)، فإن الجانب الأيسر ليس له سوى نقطة واحدة في حين أن الجانب الأيمن يمكن أن يكون أي سلسلة من الأطراف الطرفية أو غير الطرفية. وتجدر الإشارة إلى ان القيم الخالية يتم استثناؤها في ق.ا.خ.س [10] مثال:

يمكن اختصار هذه القاعدة باستخدام الرمز "|" حرف (أو) إلى:

الرموز الطرفية في القواعد هي ما لا يُمكن تجزئته، أما الرموز غير الطرفية فهي ما يُمكن تجزئته والتي يُمكن أن يتم تحويلها إلى جمل أخرى تتكون من رموز طرفية أو غير طرفية (الأحرف والأرقام على سبيل المثال هي رموز طرفية، لأنها غير قابلة للتجزئة أكثر)[11]، القاعدة أعلاه تُعرف بأنها تبدأ برمز S غير الطرفي ويُمكن أن تولد الرموز e، b أو a (مثال على الرموز غير الطرفية مثلاً صنف الأرقام أي عندما نقول "رقم" فحسب فيُمكن استبداله بأي من الأرقام):

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

تتجنب القواعد النحوية الاحتمالية هذه المشكلات بتصنيف مختلف الإنتاجات على أوزان بحسب تردد ورودها.

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

القواعد الموزونة الخالية من السياق

تعد القواعد الموزونة النحوية الخالية من السياق ( ق.م.خ.س) فئة عامة أكثر من القواعد الخالية من السياق ، حيث يكون لكل إنتاج وزن رقمي مرتبط به. وزن شجرة تحليل معينة في ق.م.خ.س هو المنتج [12] (أو المجموع [13] ) لجميع أوزان القاعدة في الشجرة. يتم تضمين وزن كل قاعدة كلما استخدمت القاعدة في الشجرة. وهناك حالة خاصة تكون فيها ق.م.خ.س هي ق.خ.س، عندما تمثل الأوزان المرفقة مع الانتاجات هي ( لوغاريتمات [14] [15] ) الاحتمالات .

تطبيقات

فضلاً عن التطبيقات في اللغات الطبيعية، فإن القواعد الاحتمالية الخالية من السياق تطبق أيضاً في التنبؤ ببنية الحمض النووي الريبي.

المراجع

  1. Chomsky, Noam (1956). "Three models for the description of language". IRE Transactions on Information Theory. 2 (3): 113–124. doi:10.1109/TIT.1956.1056813.
  2. Chomsky, Noam (June 1959). "On certain formal properties of grammars". Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6.
  3. Noam Chomsky, ed. (1957). Syntactic Structures. Mouton & Co. Publishers, Den Haag, Netherlands.
  4. Eddy S. R. & Durbin R. (1994). "RNA sequence analysis using covariance models". Nucleic Acids Research. 22 (11): 2079–2088. doi:10.1093/nar/22.11.2079. PMC . PMID 8029015. نسخة محفوظة 15 أبريل 2017 على موقع واي باك مشين.
  5. Sakakibara Y., Brown M., Hughey R., Mian I. .S et al. (1994). "Stochastic context-free grammars for tRNA modelling". Nucleic Acids Research. 22 (23): 5112–5120. doi:10.1093/nar/22.23.5112.
  6. Grat, L. (1995). "Automatic RNA secondary structure determination with stochastic context-free grammars" ( كتاب إلكتروني PDF ). In Rawlings, C., Clark, D., Altman, R., Hunter, L., Lengauer, T and Wodak, S. Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology, AAAI Press: 136–144. نسخة محفوظة 04 ديسمبر 2015 على موقع واي باك مشين.
  7. Lefebvre, F (1995). "An optimized parsing algorithm well suited to RNA folding". In Rawlings, C.; Clark, D.; Altman, R.; Hunter, L.; Lengauer, T.; Wodak, S. (eds.). Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology. AAAI Press. pp. 222–230.
  8. Lefebvre, F. (1996). "A grammar-based unification of several alignment and folding algorithms". In States, D. J.; Agarwal, P.; Gaasterlan, T.; Hunter, L.; Smith R. F. (eds.). Proceedings of the Fourth International Conference on Intelligent Systems for Molecular Biology. AAAI Press. pp. 143–153.
  9. Noam Chomsky, المحرر (1957). Syntactic Structures. Mouton & Co. Publishers, Den Haag, Netherlands.
  10. R. Durbin; S. Eddy; A. Krogh; G. Mitchinson, eds. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge University Press. ISBN . نسخة محفوظة 18 مارس 2015 على موقع واي باك مشين.
  11. "Grammars". Maynooth University Website. Computer Science at Maynooth University. مؤرشف من الأصل في 6 أبريل 201805 مايو 2019.
  12. Smith, Noah A.; Johnson, Mark (2007). "Weighted and Probabilistic Context-Free Grammars Are Equally Expressive". Computational Linguistics. 33 (4): 477. doi:10.1162/coli.2007.33.4.477.
  13. Katsirelos, George; Narodytska, Nina; Walsh, Toby (2008). "The Weighted Cfg Constraint". Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 5015. صفحة 323. doi:10.1007/978-3-540-68155-7_31.  .
  14. Johnson, Mark (2005). "log linear or Gibbs models" ( كتاب إلكتروني PDF ). مؤرشف من الأصل ( كتاب إلكتروني PDF ) في 15 أبريل 2019.
  15. Chi, Zhiyi (March 1999). "Statistical properties of probabilistic context-free grammars" ( كتاب إلكتروني PDF ). Computational Linguistics. 25 (1): 131–160. مؤرشف من الأصل ( كتاب إلكتروني PDF ) في 21 أغسطس 2010.

































موسوعات ذات صلة :