برچسب گذاری اجزای واژگانی کلام

برچسب گذاری اجزای واژگانی کلام

اسلاید 1: Part-of-Speech taggingMohammad BahraniMarch 2011In the name of God

اسلاید 2: Part-of-Speech (POS) taggingPart-of-Speech (POS) یا جزء کلام: مقوله نحوی که هر کلمه به آن تعلق دارد.نامهای دیگر: word classes، lexical tags، tagsPOS tagging (tagging): فرایند انتساب مقوله نحوی به هر کلمه در پیکره متنیPOSهای اصلی در انگلیسی:NounsVerbsAdjectivesAdverbsPrepositions (on, to, by, from, with, …)Determiners (a, an, the)Pronouns (she, who, my, others, …)Conjunctions (and, but, if, …)Auxiliaries (can, should, are, …)Particles (up, down, off, in, out, …)Numerals (one, two, three, first, second, …)

اسلاید 3: Part-of-Speech (POS) taggingبسته به کاربرد، ممکن است POS های جزئی تری در پیکره های متنی به کار روند:Singular nounsPlural nounsComparative adjectivesSuperlative adjectivesModal verbsPersonal pronounsPossessive pronouns…برای علائم نقطه گذاری هم tag های متفاوتی ممکن است به کار رود.tag setهای مختلف در انگلیسی:Penn Treebank tag set: شامل 45 tagBrown Corpus tag set: شامل 87 tagC5 tag set: شامل 61 tagC7 tag set: شامل 146 tagدر پیکره متنی زبان فارسی (دکتر بیجن خان) حدود 660 tag به کار رفته است.

اسلاید 4: POS-tagging: کاربردهادانستن مقوله نحوی یک کلمه می تواند اطلاعات بیشتری در مورد خود کلمه و کلمات مجاور آن به ما بدهد.کاربردها:مدل سازی زبانی (در بازشناسی گفتار و ...): مقوله نحوی یک کلمه می تواند در پیش بینی کلمه بعدی کمک کند.مثال: در انگلیسی بعد از ضمایر ملکی، اسم و بعد از ضمایر شخصی، فعل می آید.در فارسی معمولاً بعد از حرف اضافه اسم یا ضمیر می آید.سنتز گفتار: مقوله نحوی یک کلمه می تواند اطلاعاتی در مورد نحوه تلفظ صحیح یک کلمه به ما بدهد.مثال: تلفظ کلمه object در انگلیسی به صورت OBject (noun) و obJECT (verb)تلفظ کلمه ”مرد“ در فارسی به صورت ”مَرد“ (اسم)، ”مُرد“ (فعل)بازیابی اطلاعات: دانستن مقوله نحوی کلمات می تواند به استخراج کلمات مهم در متن کمک کند.رفع ابهام معنایی: دانستن مقوله نحوی کلمات می تواند به رفع ابهام معنایی کلمه کمک کند.مثال: کلمه watch در انگلیسی و کلمه ”در“ در فارسیتجزیه نحوی (parsing): برای parsing پایین به بالا در ابتدا نیاز به تعیین مقوله نحوی کلمات داریم.

اسلاید 5: POS tagging: روش هامشکل اصلی در POS tagging: بعضی از کلمات به چند مقوله نحوی تعلق دارند.حدود 11.5% از انواع کلمات به کار رفته در پیکره brown دارای بیش از یک tag هستند.این کلمات حدود 40% پیکره را شامل می شوند.روش های کلی POS tagging:روش های مبتنی بر قاعده (rule based POS tagging)روش های آماری (probabilistic/stochastic POS tagging)روش های ترکیبی (transformation-based POS tagging)

اسلاید 6: Rule based POS taggingبا استفاده از یک سری rule مقوله نحوی کلمات دارای ابهام را با توجه به کلمات مجاور تعیین می کند.Ruleها به وسیله زبان شناسان نوشته می شوند.دو مرحله کلی از POS tagging مبتنی بر قاعدهابتدا با استفاده از یک دیکشنری تمام tag های ممکن برای کلمات تعیین می شوند.سپس برای هر کلمه در متن، با استفاده از قواعد و با توجه به کلمات مجاور، یکی از tag ها به عنوان tag اصلی تعیین می شود.

اسلاید 7: Rule based POS taggingمثال: I think that you are cleverI: PRONthink: Vthat: PRON, DET, COMP, ADVyou: PRONare: AUXclever: ADJمثالی از یک rule (از ENGTWOL tagger)Adverbial-that rule:Given input: “that”If (+1 ADJ/ADV/QUANT) (+2 SENT-LIM) (NOT -1 V-SVO)then eliminate non-ADV tagselse eliminate ADV tag

اسلاید 8: Probabilistic POS taggingبا استفاده از یک پیکره tagخورده، دنباله tagهای ممکن برای دنباله کلمات مختلف را یاد می گیرد و با استفاده از آن محتمل ترین tag برای هر کلمه را پیدا می کند.مسئله POS tagging به صورت آماری:با فرض داشتن دنباله کلمات W=w1…wn، دنباله tag های T=t1…tn را طوری پیدا کنید که P(T|W) ماکزیمم شود:با استفاده از قانون بيز:

اسلاید 9: Probabilistic POS taggingمحاسبه احتمال هاي فوق در عمل بسيار مشكل است. بنابراين چند فرض ساده كننده براي محاسبه احتمال ها به كار مي رود:(حاصلضرب احتمالات n-gram)(حاصلضرب احتمالات lexical-generation)بنابراين بايد دنباله tag ها را طوري پيدا كنيم كه عبارت زير ماكزيمم شود:

اسلاید 10: Probabilistic POS taggingمحاسبه احتمالات با استفاده از پیکره برچسب خوردهاحتمالات bigramاحتمالات lexical-generationمحاسبه محتمل ترین دنباله از tagهاساده ترین روش: درنظر گرفتن تمام دنباله های محتمل و محاسبه احتمال هر یک به روش فوق (Brute Force Search)با فرض داشتن N برچسب و T كلمه، حداكثر NT دنباله از برچسب ها توليد مي شود.

اسلاید 11: زنجيره ماركوف (Markov Chain)محاسبه احتمال P(T) با استفاده از زنجيره ماركوفزنجيره ماركوف: نوع خاصي از Finite State Machine كه در آن به پرش هاي بين state ها يك احتمال نسبت داده مي شود.فرض ماركوف مرتبه اول: احتمال بودن در هر state فقط به state قبلي وابسته است.

اسلاید 12: زنجيره ماركوف: مثالفرض كنيد كه در يك corpus، 4 برچسب ART، N، V و P با شمارش هاي زير داريم:

اسلاید 13: زنجيره ماركوف: مثالاحتمال رفتن وقوع برچسب هاي مختلف پس از يكديگر را مي توان با زنجيره ماركوف زير نشان داد:P(N V ART N) = 0.29*0.43*0.65*1=0.081

اسلاید 14: مدل مخفي ماركوف (Hidden Markov Model)اگر در هر گره از زنجيره ماركوف يك سري خروجي (با يك توزيع احتمال مشخص) داشته باشيم، زنجيره ماركوف تبديل به مدل مخفي ماركوف (HMM) مي شود.خروجي ها در هر گره مي توانند كلمات مختلف باشند. احتمال خروجي هر كلمه بدين معني است كه با چه احتمالي آن كلمه به وسيله آن گره توليد مي شود (احتمالات lexical-generation)واژه ”مخفي“ به اين دليل به اين مدل اطلاق مي شود كه با فرض داشتن يك دنباله از كلمات خروجي، دنباله stateهاي توليد كننده آن از نظر ما مخفي است.

اسلاید 15: مدل مخفي ماركوف: مثالمحاسبه احتمال P(W|T) با استفاده از مدل مخفي ماركوف:فرض كنيد كه احتمالات lexical-generation در corpus فرضي به صورت زير است:

اسلاید 16: مدل مخفي ماركوف: مثال

اسلاید 17: مدل مخفي ماركوف: مثالبه شرط گذر از مسير ”N V ART N“ در زنجيره ماركوف مثال فوق، احتمال اينكه خروجي برابر با دنباله كلمات ”flies like a flower“ باشد:P(flies like a flower|N V ART N) = P(flies | N) * P(like | V) * P(a | ART) * P(flower | N) = 0.025 * 0.1 * 0.36 * 0.063 = 5.4 * 10-5

اسلاید 18: الگوريتم ويتربيتعيين محتمل ترين دنباله از stateهاي HMM به شرط مشاهده دنباله اي از خروجي هادر POS tagging: تعيين محتمل ترين دنباله از tagها به شرط مشاهده دنباله اي از كلماتدر الگوريتم ويتربي نيز از احتمال هاي bigram و lexical-generation براي محاسبه محتمل ترين دنباله از tagها استفاده مي شود.در الگوريتم ويتربي با مشاهده هر خروجي محتمل ترين دنباله از stateها به صورت جزئي (partial) محاسبه مي شود.

اسلاید 19: الگوريتم ويتربي

اسلاید 20: Supervised & Unsupervised POS taggingPOS tagging به صورت ”با نظارت“ (Supervised)داده آموزش داراي برچسب POS مي باشد و آموزش براساس رويه فوق انجام مي گيرد.POS tagging به صورت ”بدون نظارت“ (Unsupervised)داده آموزش بدون برچسب مي باشد و آموزش بر اساس يك رويه تكراري انجام مي گيرد.

اسلاید 21: POS tagging: ارزيابيپيكره متني به دو بخش تقسيم مي شود:80-90% از پيكره براي آموزش (train)10-20% از پيكره براي آزمون (test)با استفاده از داده آموزش آمارهاي لازم استخراج مي گردد و سپس POS tagging برروي داده آزمون تست مي شود.دقت POS tagging:روش Cross Validation:پيكره متني به K قسمت مساوي تقسيم مي شود.در هر مرحله از ارزيابي، يك بخش براي آزمون و K-1 بخش ديگر براي آموزش به كار مي رود.اين روند K بار تكرار مي گردد و درنهايت از نتايج ارزيابي K مرحله ميانگين گرفته مي شود.