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

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

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

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

تعريفات

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

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

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

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

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

G=(M,T,R,S,P)

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

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

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

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

بناء القواعد

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

S\to aS,S\to bS,S\to \epsilon

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

S\to aS|bS|\epsilon

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

S\Rightarrow aS\Rightarrow abS\Rightarrow abbS\Rightarrow abb

S\Rightarrow aS\Rightarrow abS\Rightarrow abbS\Rightarrow abb

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

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

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

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

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

تطبيقات

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

المراجع

^ 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.
^ 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.
^ Noam Chomsky, ed. (1957). Syntactic Structures. Mouton & Co. Publishers, Den Haag, Netherlands.
^ 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 308124. PMID 8029015. نسخة محفوظة 15 أبريل 2017 على موقع واي باك مشين.
^ 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. Explicit use of et al. in: |authors= (help)CS1 maint: Uses authors parameter (link)
^ 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 على موقع واي باك مشين.
^ 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.
^ 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.
^ Noam Chomsky، المحرر (1957). Syntactic Structures. Mouton & Co. Publishers, Den Haag, Netherlands.
^ R. Durbin; S. Eddy; A. Krogh; G. Mitchinson, eds. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge University Press. ISBN 978-0-521-62971-3. نسخة محفوظة 18 مارس 2015 على موقع واي باك مشين.
^ "Grammars". Maynooth University Website. Computer Science at Maynooth University. مؤرشف من الأصل في 2018-04-06. اطلع عليه بتاريخ 2019-05-05.
^ 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.
^ Katsirelos، George؛ Narodytska، Nina؛ Walsh، Toby (2008). "The Weighted Cfg Constraint". Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Lecture Notes in Computer Science. ج. 5015. ص. 323. DOI:10.1007/978-3-540-68155-7_31. ISBN:978-3-540-68154-0.
^ Johnson، Mark (2005). "log linear or Gibbs models" (PDF). مؤرشف من الأصل (PDF) في 2019-04-15.
^ Chi، Zhiyi (مارس 1999). "Statistical properties of probabilistic context-free grammars" (PDF). Computational Linguistics. ج. 25 ع. 1: 131–160. مؤرشف من الأصل (PDF) في 2010-08-21.

المرجع "مولد تلقائيا9" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "مولد تلقائيا1" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "مولد تلقائيا4" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "مولد تلقائيا6" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "مولد تلقائيا8" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "مولد تلقائيا5" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "مولد تلقائيا7" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "مولد تلقائيا2" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "مولد تلقائيا3" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Dowell 2004" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "McCaskill 1990" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Juan 1999" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Zuker 2000" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Mathews 1999" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Knudsen 2003" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Knudsen 1999" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Rivas 2001" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Holmes 2002" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Gardner 2010" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Yao 2006" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Rabani 2008" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Goodarzi 2012" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Sipser 1996" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Harrison 1978" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Hopcroft 1979" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Giegerich 2000" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Lari and Young 1990" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Lari and Young 1991" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Nawrocki 2013" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Tavaré 1986" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Muse 1995" المذكور في <references> غير مستخدم في نص الصفحة.
المرجع "Baker 1979" المذكور في <references> غير مستخدم في نص الصفحة.

المرجع "Schöniger 1994" المذكور في <references> غير مستخدم في نص الصفحة.

[Chomsky_1956-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.

[Chomsky_1959-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.

[Chomsky_1957-3] Noam Chomsky, ed. (1957). Syntactic Structures. Mouton & Co. Publishers, Den Haag, Netherlands.

[Eddy_1994-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 308124. PMID 8029015. نسخة محفوظة 15 أبريل 2017 على موقع واي باك مشين.

[Sakakibara_1994-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. Explicit use of et al. in: |authors= (help)CS1 maint: Uses authors parameter (link)

[Grat_1995-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 على موقع واي باك مشين.

[Lefebvre_1995-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.

[Lefebvre_1996-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.

[مولد_تلقائيا10-9] Noam Chomsky، المحرر (1957). Syntactic Structures. Mouton & Co. Publishers, Den Haag, Netherlands.

[Durbin_1998-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 978-0-521-62971-3. نسخة محفوظة 18 مارس 2015 على موقع واي باك مشين.

[11] "Grammars". Maynooth University Website. Computer Science at Maynooth University. مؤرشف من الأصل في 2018-04-06. اطلع عليه بتاريخ 2019-05-05.

[PCFG_WCFG_same-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.

[sumWeightedCFG-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. Lecture Notes in Computer Science. ج. 5015. ص. 323. DOI:10.1007/978-3-540-68155-7_31. ISBN:978-3-540-68154-0.

[logLinear-14] Johnson، Mark (2005). "log linear or Gibbs models" (PDF). مؤرشف من الأصل (PDF) في 2019-04-15.

[15] Chi، Zhiyi (مارس 1999). "Statistical properties of probabilistic context-free grammars" (PDF). Computational Linguistics. ج. 25 ع. 1: 131–160. مؤرشف من الأصل (PDF) في 2010-08-21.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]