دانلود پایان نامه ارشد درمورد درخت تصمیم، ناسازگاری، زبان عربی

از آن نیز عماد زیتونی و همکارانش از این روش برای زبان عربی استفاده نمودند.[49] به طور کلی در این روش درختِ بل، مسئله تشخیص مرجع مشترک به‏عنوان یافتن بهترین مسیر از ریشه درختِ بل به گره‏های انتهایی است. در این روش از مدل حداکثر آنتروپی جهت رتبه‏بندی این مسیرها استفاده می‏شود. هر یک از برگ‏های درختِ بل، نمایانگر یکی از خروجی‏های ممکن برای تشخیص زنجیره‏ی عبارت اسمی هم‏مرجع می‏باشد.گره‏ی ریشه، وضعیت آغازین فرآیند و تنها شامل یک موجودیت است که اولین عبارت اسمی به آن تعلق دارد. هنگام اضافه کردن دومین عبارت اسمی، می‏توان از هر یک از عملیات‏های «اضافه کردن به یک موجودیت قبلی» و یا «آغاز کردن یک موجودیت جدید» استفاده نمود.
پس از انجام هر یک از عملیات‏ها، لایه دوم گره ایجاد می‏شود. به‏عنوان مثال سه عبارت اسمی را در یک متن در نظر بگیرید. درختِ بل متناظر با فرآیند تشخیص مرجع مشترک بر روی متن شامل سه عبارت مذکور مطابق شکل 2-۲ خواهد بود.

شکل 2-۲. درختِ بل به ازای سه عبارت اسمی100
همانطور که در شکل2-2 مشاهده می‏نمایید، این فرآیند یک فرآیند همزمان با عبارات اسمی است، بدین معنی که هر لایه از گره‏ها تنها با اضافه کردن یک عبارت اسمی جدید ایجاد می‏شود. از آنجائیکه تعداد برگهای درخت برابر است با تعداد خروجی‏های ممکن فرآیند تشخیص مرجع مشترک، و این عدد با عدد بل یکسان است، درخت تشکیل شده را درختِ بل می‏نامند. عدد بل تعداد راه‏هایی است که می‏توان n شیء متمایز را به زیر مجموعه‏هایی که با هم اشتراکی ندارند، افراز نمود.
در سال ۲۰۰۷، لو، یک مدل دوگانه101 برای بهبود روش درختِ بل ارائه داد. در روش درختِ بل تنها یک مدل با استفاده از حداکثرآنتروپی آموزش داده می‏شد و آن مدل «متصل کردن به یک موجودیت قبلی» بود. همچنین احتمال «آغاز کردن یک موجودیت جدید» نیز از روی احتمال متصل نشدن به موجودیت‏های قبلی محاسبه می‏شد. شیوه ارائه شده توسط لو مشابه شیوه درختِ بل است، با این تفاوت که دو مدل جداگانه برای «متصل کردن به یک موجودیت قبلی» و «آغاز کردن یک موجودیت جدید» در نظر گرفته می‏شود. هر کدام از این مدل‏ها بصورت مجزا آموزش داده می‏شوند. نتایج نشان داده‏است که این شیوه بهتر از شیوه‏ی درختِ بل عمل می‏کند.[107]
مزایا و معایب روش درختِ بل
مزیت این روش، در نظر گرفتن و رعايت روابط متعدی، است. مشکل این روش در آن است که عدد بل با افزایش n (تعداد عبارات اسمی متمایز) به سرعت افزایش می‏یابد و بدین ترتیب با افزایش تعداد عبارت‏های اسمی، جستجو در درختِ بل مشکل‏تر می‏شود. جهت رفع این مشکل از یک مکانیزم جستجوی کارا و روش‏های هرس کردن درخت استفاده می‏شود.
2-1-۳-۲-۲-۲.افراز گراف102
در روش افراز گراف، پس از رده‏بندی و تصمیم‏گیری که در مورد هم‏مرجع بودن دو عبارت اسمی صورت می‏گیرد. نوبت به مرحله تعیین زنجیره‏های عبارت‏های اسمیِ هم‏مرجع که در یک گروه قرار داشته و به یک موجودیت اشاره می‏پردازند، مي‏رسد.
در افراز گراف، گره‏های گراف، عبارت‏های اسمی(یا اشاره‏ها) و وزن یال‏های میان هردو گره، بیانگر ارتباط یا به عبارت دیگر میزان احتمال هم‏مرجع بودن آن دو گره می‏باشد. این وزن‏ها از مرحله رده‏بندی بدست می‏آیند. برای تشخیص موجودیت‏های موجود در متن که با هم هم‏مرجع هستند، باید گراف را به گونه‏ای افراز کرد که تمام گره‏های قرار گرفته در یک زیرگراف به یک موجودیت یکسان اشاره داشته باشند[18،20،30،51]
در مرحله تعیین زنجیره عبارات هم‏مرجع، نیکلای103 و همکارانش در سال ۲۰۰۶، از روشی استفاده نمودند که در آن فضای عبارات اسمی هم‏مرجع، به صورت یک گراف بدون جهت وزن‏دار نمایش داده می‏شود. [18]در این روش از رده‏بند حداکثر آنتروپی برای وزن‏دهی یال‏ها استفاده شده (آن‏ها بر این باورند که مدل حداکثر آنتروپی می‏تواند نتایج بهتری نسبت به مدل درخت تصمیم ارائه دهد) و به ازای هر یک از انواع موجودیت‏ها گراف جداگانه‏ای ایجاد می‏شود. در نهایت، نمونه تغییر یافته‏ای از الگوریتم «برش کمینه104 ی» استور105 [64]بر روی هر کدام از گراف‏ها اعمال می‏شود و بدین ترتیب مرحله خوشه‏بندی به انجام پیمانه‏هاي که افرازهای ایجاد شده توسط این الگوریتم، عبارت‏های اسمی خواهند ‏بود که به یک موجودیت واحد اشاره می‏پردازند. همچنین می‏توان مانند بانسال106 ، از الگوریتم خوشه‏بندی رابطه‏ای نیز برای تخمین مسئله‏ی افراز گراف استفاده نمود.[72] در این شیوه، ناسازگاری حضور یک گره در هر افراز محاسبه می‏شود و مرحله افرازبندی بگونه‏ای انجام می‏پذیرد که این ناسازگاری‏ها به حداقل ممکن برسند.
در سال ۲۰۱۰، ساپنا107 و همکارانش یک روش افراز گراف محدود شده را پیشنهاد نمودند. آن‏ها برای وزن‏دهی به یال‏ها از رده‏بند درخت تصمیم استفاده کردند و برای بهینه سازی نتایج از یک الگوریتم تکرارشونده تحت عنوان برچسب‏گذاری‏ راحت108 استفاده نمودند.[47] در این الگوریتم، برای تخصیص هر گره به هر افراز، محدودیت‏هایی بررسی می‏شود. و هدف آن پیدا کردن یک برچسب‏گذاری‏ وزنی بیشینه است.[30]
از طرف دیگر، کای و همکارانش یک مدل افراز ابرگراف عمومی را پیشنهاد دادند. هدف نهائی این مدل انجام تحلیل مرجع مشترک در یک مرحله است. نخست کل متن به عنوان یک ابرگراف109 در نظر گرفته می‏شود. سپس این ابرگراف با در نظر گرفتن ویژگی‏هایی مانند تطابق رشته‏ای، تطبیق ضمیر و… به تعدادی زیرگراف تقسیم می‏شود. برای افراز گراف نیز، خوشه‏بندی طیفی بازگشتی در میان تمام زیر گراف‏ها اجرا شده و به جای استفاده از برش کمینه، از برش نرمال110 استفاده می‏شود، این کار آنقدر ادامه پیدا می‏کند تا به شرط توقف برسد.[20]
مزایا و معایب روش افراز گراف
روش افراز گراف نسبت به برخی از روش‏ها مانند روش درختِ بل[106]عملکرد بهتری نشان داده است. البته روش افراز گراف نیز مانند روش درختِ بل، روابط متعدی را در نظر می‏گیرد، و در عین حال از برخی خصوصیت‏های الگوریتم‏های گراف مانند سادگی و موثر بودن بهره می‏برد. از طرفی دیگر، این روش هنگام تشکیل و افراز گراف‏ها، تنها از افراز غیر‏اشاره استفاده می‏کند و برای تشخیص مرجع مشترک، از یک شیوه‏ی رده‏بندی ساده بهره می‏گیرد. در نتیجه عملکرد آن در تشخیص مرجع مشترک خيلي مناسب نیست.
2-1-۳-۳.روش‏های مبتنی بر پيکره
تکنیک‏های داده کاوی111، از جمله روش‏هایی هستند که در مسئله‏ی تشخیص مرجع مشترک استفاده شده‏اند. هاراباگیو112 و همکارانش در سال ۲۰۰۱ ، از پایگاه داده‏های برچسب‏گذاری شده‏ی MUC-6 و MUC-7 استفاده کردند. آن‏ها به منظور استفاده از شیوه‏های داده‏کاوی با استفاده از این دو پایگاه داده، داده‏های بیشتری تولید کردند.[93]
یکی از نتایج بدست آمده‏ی قابل توجه آن‏ها این است که تعداد پیوندهایی که یک عبارت اسمی را به یک عبارت اسمی خاص متصل کرده‏است ۲۹٫۱ % و تعداد پیوندهای هم‏مرجع میان دو عبارت اسمی عام ۱۰% است. از طرفی دیگر حدود۸۳% از زنجیره‏های هم‏مرجع در پیکره‏ی MUC-6 با ویژگی‏ها و قواعد ساده‏ای مانند تکرار یک عبارت اسمی، نام مستعار، هسته113 مشترک و غیره حل خواهد شد.
پس از تولید پایگاه‏داده بزرگتر با استفاده از پایگاه داده‏های برچسب‏گذاری‏ شده موجود، تعدادی قاعده استخراج می‏شود و به ازای هر قاعده، آنتروپی آن به‏عنوان معیاری برای درجه صحت آن قاعده در نظر گرفته می‏شود. سپس افراز عبارت‏های اسمی به گونه‏ای انجام می‏پذیرد که تعداد بیشتری از قاعده‏هایی که درجه صحت بالاتری دارند، این افراز را تایید نمایند.
می‏توان از پیکره‏ها برای کاوش در الگوهایی مانند الگوهایی که بوسیله آن‏ها دو عبارت اسمی به یکدیگر مرتبط می‏شوند، بهره‏گرفت. الگوهایی که به کرات میان دو عبارت اسمی مشاهده شده‏اند، بیانگر رابطه‏ی میان آن دو عبارت اسمی هستند.
بین114 و همکارانش در سال ۲۰۰۴، سیستمی ایجاد کردند که در آن سیستم براساس رابطه میان کلمات و زمینه‏ای را که آن کلمات می‏توانند در آن باشند را به شیوه‏ای بدون نظارت آموزش می‏بینند. مشخص کردن نقش معنایی عبارت‏های اسمی، نقش بسیار مهمی در زنجیره‏های عبارات اسمی هم‏مرجع دارد. [25] به‏عنوان نمونه مثال‏های ذیل را در نظر بگیرید.
Maria, Roberto, and Dino, who were staying at the Tecun hotel مثال7: kid-napped by armed men …
ماریا، ربرتو و داینو که در هتل«تکان»مستقر بودند، توسط مردا‏‏‏‏‏ن نقابدار دزدیده شدند.
After they were released …مثال8:
پس از آنکه آن‏ها آزاد شدند…
After they blindfolded the men…مثال9:
پس از آنکه مردها دستگیر شدند…
درمورد (مثال8)، « آن‏ها» با «ماریا»، «ربرتو» و «داینو» (پسران) هم‏مرجع هستند.و در مورد (مثال9)، «آن‏ها» با «مردان نقابدار» مرجع مشترک دارند.
در چنین شرایطی، یافتن عبارات اسمی که به یک مرجع واحد اشاره دارند، نیاز به یک دانش قبلی دارد. به عنوان مثال کسانی که به اسارت گرفته می‏شوند، آزاد می‏شوند. کسب و استفاده از چنین دانشی در زبان‏های طبیعی، یک مسئله حل نشده‏است. در عین حال وجود پیکره‏های بزرگ می‏تواند برای آسان‏تر شدن کاوش در چنین الگوهایی کمک بسزائی داشته باشد. بین و همکارانش نیز از شیوه بدون نظارت مبتنی بر پیکره برای این منظور استفاده نموده‏اند. در شیوه‏ی ارائه شده توسط آن‏ها، مفاهیم به صورت چارچوب‏های موضوعی نمایش داده می‏شوند که می‏توان قاب‏های موضوعی115 را به عنوان عبارت‏هایی با یک پرکننده در نظر گرفت.[25] مانند مثال ذیل:
“Murder of ”, “killed”مثال10: .
این سیستم از چند پیمانه تشکیل شده است. یک پیمانه با این فرض که قاب‏هایی از واژه‏ها که با یکدیگر رخ می‏دهند با یکدیگر مرتبط نیستند، شبکه قاب موضوعی را، با مشخص کردن قاب‏های مرتبط می‏سازد. بنابراین با دادن قاب موضوعی، می‏توان تمامی قاب‏های موضوعی که با آن قاب رخ می‏دهند را لیست کرد. به عنوان نمونه، برای مثال فوق می‏توان انتظار داشت که “ were kidnapped” با “ were released” رخ دهد.
یک پیمانه دیگر، قاب‏های موضوعی مرتبط با واژه‏ها را مشخص می‏نماید. به این ترتیب که اگر دو واژه با یکدیگر رخ دهند، پس آن‏ها با قاب‏های موضوعی یکدیگر مرتبط خواهند‏بود. بنابراین با داشتن یک قاب موضوعی می‏توان تمام واژه‏هایی که انتظار می‏رود با آن رخ دهند را لیست نمود. در نهایت نیز پیمانه دیگری با رابطه‏ی میان قاب‏ها و نوع معنایی واژه‏ها آموزش می‏بیند. این نوع معنایی از شبکه واژگانی استخراج می‏شود.
در سال ۲۰۰۶، برگسما116 و لین117 احتمال اینکه یک عبارت اسمی با کاندیداهای احتمالی خود هم‏مرجع باشد را بر اساس مسیری که درخت تجزیه118ی میان آن‏ها وجود دارد، محاسبه کردند. این اطلاعات به صورت خودکار و با استفاده از پایگاه داده‏ی بزرگی که در آن ساختار وابستگی119 جملات مشخص شده است، استخراج می‏شوند. به عنوان مثال، دو جمله‏ی زیر را در نظر بگیرید:

مثال11:جان به دوستش نیاز دارد

مثال12:جان به حمایت او نیاز دارد
“His” و”John”در جمله اول به یک موجودیت اشاره دارند در صورتی در جمله دوم”His” و”John” نمی‏توانند به یک موجودیت اشاره داشته باشند. چون یک فرد به حمایت خودش نیاز ندارد.[94]
با استفاده از این روش، ابتدا مسیرهای وابستگی میان دو عبارت اسمی استخراج می‏گردد. به عنوان نمونه مسیر وابستگی در مثال 11، برابرست با needs friend که در آن دو عبارت اسمی مورد بررسی که همان پایانه120ها هستند، حذف شده‏اند. بدین ترتیب، تعداد دفعاتی که یک مسیر وابستگی خاص در پایگاه داده آموزشی دیده‏شده و در آن دو عبارت پایانه هم‏مرجع بوده‏اند. از طرف دیگر تعداد دفعاتی که این مسیر وابستگی دیده شده و دو عبارت پایانه هم‏مرجع نبوده‏اند نیز محاسبه می‏شود. به علاوه اینکه این روش با استفاده از همین مسیرهای وابستگی اطلاعات جنس