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

نشأت قواعد النحو لنمذجة سلاسل الرموز من العمل في اللغويات الحاسوبية بهدف فهم بنية اللغات الطبيعية.[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 308124. 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. Explicit use of et al. in: |authors= (help)CS1 maint: Uses authors parameter (link)
  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 978-0-521-62971-3. نسخة محفوظة 18 مارس 2015 على موقع واي باك مشين.
  11. "Grammars"، Maynooth University Website، Computer Science at Maynooth University، مؤرشف من الأصل في 6 أبريل 2018، اطلع عليه بتاريخ 05 مايو 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، Lecture Notes in Computer Science، ج. 5015، ص. 323، doi:10.1007/978-3-540-68155-7_31، ISBN 978-3-540-68154-0.
  14. Johnson, Mark (2005)، "log linear or Gibbs models" (PDF)، مؤرشف من الأصل (PDF) في 15 أبريل 2019.
  15. Chi, Zhiyi (مارس 1999)، "Statistical properties of probabilistic context-free grammars" (PDF)، Computational Linguistics، 25 (1): 131–160، مؤرشف من الأصل (PDF) في 21 أغسطس 2010.
  16. 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.
  17. Chomsky, Noam (يونيو 1959)، "On certain formal properties of grammars"، Information and Control، 2 (2): 137–167، doi:10.1016/S0019-9958(59)90362-6.
  18. Noam Chomsky, المحرر (1957)، Syntactic Structures.، Mouton & Co. Publishers, Den Haag, Netherlands.
  19. 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.
  20. Sakakibara Y., Brown M., Hughey R., Mian I. .S وآخرون (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= (مساعدة)صيانة CS1: يستخدم وسيط المؤلفون (link)
  21. 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، مؤرشف من الأصل (PDF) في 4 ديسمبر 2015.
  22. Lefebvre, F (1995)، "An optimized parsing algorithm well suited to RNA folding"، في Rawlings, C.؛ Clark, D.؛ Altman, R.؛ Hunter, L.؛ Lengauer, T.؛ Wodak, S. (المحررون)، Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology، AAAI Press، ص. 222–230.
  23. Lefebvre, F. (1996)، "A grammar-based unification of several alignment and folding algorithms"، في States, D. J.؛ Agarwal, P.؛ Gaasterlan, T.؛ Hunter, L.؛ Smith R. F. (المحررون)، Proceedings of the Fourth International Conference on Intelligent Systems for Molecular Biology، AAAI Press، ص. 143–153.
  24. R. Durbin؛ S. Eddy؛ A. Krogh؛ G. Mitchinson, المحررون (1998)، Biological sequence analysis: probabilistic models of proteins and nucleic acids، Cambridge University Press، ISBN 978-0-521-62971-3، مؤرشف من الأصل في 18 مارس 2015.
  25. Dowell R., Eddy S. (2004)، "Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction"، BMC Bioinformatics، 5 (71): 71، doi:10.1186/1471-2105-5-71، PMC 442121، PMID 15180907.{{استشهاد بدورية محكمة}}: صيانة CS1: يستخدم وسيط المؤلفون (link)
  26. McCaskill J. S. (1990)، "The Equilibrium Partition Function and Base Pair Binding Probabilities for RNA Secondary Structure"، Biopolymers، 29 (6–7): 1105–19، doi:10.1002/bip.360290621، PMID 1695107.
  27. Juan V., Wilson C. (1999)، "RNA Secondary Structure Prediction Based on Free Energy and Phylogenetic Analysis"، J. Mol. Biol.، 289 (4): 935–947، doi:10.1006/jmbi.1999.2801، PMID 10369773.{{استشهاد بدورية محكمة}}: صيانة CS1: يستخدم وسيط المؤلفون (link)
  28. Zuker M (2000)، "Calculating Nucleic Acid Secondary Structure"، Curr. Opin. Struct. Biol.، 10 (3): 303–310، doi:10.1016/S0959-440X(00)00088-9.
  29. Mathews D. H.؛ Sabina J.؛ Zuker M.؛ Turner D. H. (1999)، "Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure"، J. Mol. Biol.، 288 (5): 911–940، doi:10.1006/jmbi.1999.2700، PMID 10329189.
  30. B. Knudsen؛ J. Hein. (2003)، "Pfold: RNA secondary structure prediction using stochastic context-free grammars"، Nucleic Acids Research، 31 (13): 3423–3428، doi:10.1093/nar/gkg614، PMC 169020، PMID 12824339.
  31. Knudsen B., Hein J. (1999)، "RNA Secondary Structure Prediction Using Stochastic Context-Free Grammars and Evolutionary History"، Bioinformatics، 15 (6): 446–454، doi:10.1093/bioinformatics/15.6.446، PMID 10383470.{{استشهاد بدورية محكمة}}: صيانة CS1: يستخدم وسيط المؤلفون (link)
  32. Rivas E., Eddy S. R. (2001)، "Noncoding RNA Gene Detection Using Comparative Sequence Analysis"، BMC Bioinformatics، 2 (1): 8، doi:10.1186/1471-2105-2-8، PMC 64605، PMID 11801179.{{استشهاد بدورية محكمة}}: صيانة CS1: يستخدم وسيط المؤلفون (link)
  33. Holmes I., Rubin G. M. (2002)، Pairwise RNA Structure Comparison with Stochastic Context-Free Grammars، In. Pac. Symp. Biocomput.، ص. 163–174، doi:10.1142/9789812799623_0016، ISBN 978-981-02-4777-5، مؤرشف من الأصل في 27 أغسطس 2020.{{استشهاد بكتاب}}: صيانة CS1: يستخدم وسيط المؤلفون (link)
  34. P. P. Gardner؛ J. Daub؛ J. Tate؛ B. L. Moore؛ I. H. Osuch؛ S. Griffiths-Jones؛ R. D. Finn؛ E. P. Nawrocki؛ D. L. Kolbe؛ S. R. Eddy؛ A. Bateman. (2011)، "Rfam: Wikipedia, clans and the "decimal" release"، Nucleic Acids Research، 39 (Suppl 1): D141–D145، doi:10.1093/nar/gkq1129، PMC 3013711، PMID 21062808.
  35. Yao Z., Weinberg Z., Ruzzo W. L. (2006)، "CMfinder-a covariance model based RNA motif finding algorithm"، Bioinformatics، 22 (4): 445–452، doi:10.1093/bioinformatics/btk008، PMID 16357030.{{استشهاد بدورية محكمة}}: صيانة CS1: يستخدم وسيط المؤلفون (link)
  36. Rabani M., Kertesz M., Segal E. (2008)، "Computational prediction of RNA structural motifs involved in post-transcriptional regulatory processes"، Proc. Natl. Acad. Sci. USA، 105 (39): 14885–14890، doi:10.1073/pnas.0803169105، PMC 2567462، PMID 18815376.{{استشهاد بدورية محكمة}}: صيانة CS1: يستخدم وسيط المؤلفون (link)
  37. Goodarzi H., Najafabadi H. S., Oikonomou P., Greco T. M., Fish L., Salavati R., Cristea I. M., Tavazoie S. (2012)، "Systematic discovery of structural elements governing stability of mammalian messenger RNAs"، Nature، 485 (7397): 264–268، doi:10.1038/nature11013، PMC 3350620، PMID 22495308.{{استشهاد بدورية محكمة}}: صيانة CS1: يستخدم وسيط المؤلفون (link)
  38. Sipser M. (1996)، Introduction to Theory of Computation، Brooks Cole Pub Co..
  39. Michael A. Harrison (1978)، Introduction to Formal Language Theory، Addison-Wesley.
  40. Hopcroft J. E.؛ Ullman J. D. (1979)، Introduction to Automata Theory, Languages, and Computation، Addison-Wesley.
  41. Giegerich R. (2000)، "Explaining and Controlling Ambiguity in Dynamic Programming"، In Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching 1848 Edited By: Giancarlo R., Sankoff D. Montréal, Canada: Springer-Verlag, Berlin: 46–59.
  42. Lari K.؛ Young S. J. (1990)، "The estimation of stochastic context-free grammars using the inside-outside algorithm"، Computer Speech and Language، 4: 35–56، doi:10.1016/0885-2308(90)90022-X.
  43. Lari K.؛ Young S. J. (1991)، "Applications of stochastic context-free grammars using the inside-outside algorithm"، Computer Speech and Language، 5 (3): 237–257، doi:10.1016/0885-2308(91)90009-F.
  44. Nawrocki E. P., Eddy S. R. (2013)، "Infernal 1.1:100-fold faster RNA homology searches"، Bioinformatics، 29 (22): 2933–2935، doi:10.1093/bioinformatics/btt509، PMC 3810854، PMID 24008419.
  45. Tavaré S. (1986)، "Some probabilistic and statistical problems in the analysis of DNA sequences."، Lectures on Mathematics in the Life Sciences. American Mathematical Society، 17: 57–86.
  46. Muse S. V. (1995)، "Evolutionary analyses of DNA sequences subject to constraints of secondary structure."، Genetics، 139 (3): 1429–1439، PMC 1206468، PMID 7768450.
  47. J. K. Baker (1979)، "Trainable grammars for speech recognition"، In D. Klatt and J. Wolf, Editors, Speech Communication Papers for the 97th Meeting of the Acoustical Society of America، 36 (20): 545–550.
  48. Schöniger M.؛ von Haeseler A. (1994)، "A stochastic model for the evolution of autocorrelated DNA sequences"، Mol. Phylogenet. Evol.، 3 (3): 240–7، doi:10.1006/mpev.1994.1026، PMID 7529616.
  • بوابة علم الحاسوب
  • بوابة لسانيات
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.