
ا نمونههای موجود میباشند و همانطور که در گراف به سمت بالا حرکت میکنیم، میبینیم نقاطی که با توجه به تابع تشابهِ مفروض به یکدیگر نزدیک هستند ادغام شدهاند. با حرکت در جهت بالا، اندازه خوشهها نیز افزایش مییابد. از طرف دیگر فرآیند ادغام تا زمانی ادامه مییابد که یا تنها یک خوشه داشته باشیم و یا اینکه به یک آستانه مناسب برسیم.
شکل3-5: مثالی از نمودار دندوگرام در تشخیص عبارتهای اسمی هممرجع 207
شکل 3-6، یک پیاده سازی مناسب از الگوریتم خوشهبندی سلسله مراتبی پایین به بالا را نمایش میدهد. این الگوریتم با مقداردهی اولیه خوشهبندی C آغاز میشود؛ به این ترتیب که خوشهبندی C، شامل تمامی نمونهها در قالب خوشههای یگانه خواهد بود. از آنجائیکه، خوشهبندی اولیه، شامل تعداد زیادی خوشه میباشد، مکررآً، جفت خوشهای ⟨c_i ┤,├ c_j ⟩که دارای امتیاز بالاتری نسبت به سایرین هستند انتخاب میشوند و درصورتی که امتیاز آنها از حد آستانه مورد نظر τ=f(0,0) بیشتر باشد، خوشههای c_i,c_j با یکدیگر ادغام و تشکیل یک خوشهی جدید میدهند، و این فرآیند با جفت خوشه دیگری که دارای امتیاز بالاتری نسبت به سایرین هستند ادامه پیدا میکند. تابع امتیازدهی f(c_i,c_j ) یک ترکیب وزندار خطی از ویژگیهای φ(c_i,c_j ) میباشد که از جفت خوشهها استخراج شده، و توسط بردار وزن W پارامتردهی میشود. از سویی دیگر، تابع ρ نیز، خوشهبندی208 C را به عنوان ورودی گرفته و طبق رابطه 3-14، مجموعهای از جفت خوشهها ⟨c_i ┤,├ c_j ⟩را برمیگرداند.
رابطه (3-14) } }∪{⟨0┤,├ 0⟩ c_i,c_j∈c, c_i≠c_j | ⟨c_i ┤,├ c_j ⟩ ρ(C)={
همانطور که در رابطهی 3-14، مشاهده میشود، ρ(C) شامل جفت ⟨0┤,├ 0⟩ نیز میباشد، که برای آن، φ(0,0) تعریف خواهد شد تا شامل ویژگی دودویی منحصر بفردی برای جفتهای خالی نیز باشد. وزن متناظرِ آن، به همراه تمام وزنهای دیگر، مورد یادگیری قرار میگیرد تا به طور موثر به عنوان آستانهی خوشهبندی τ=f(0,0) عمل نماید.
3-2-1-2. آموزش الگوريتم خوشهبندی سلسله مراتبی
الگوریتمهایی که در شکلهای 3-7 و 3-8 آمدهاند، بیانگر یک مدل یادگیری افزایشی میباشند. در الگوریتم 3-7، بردار وزنی W، با تکراری به اندازهی تعداد دورههای آموزشیT و یک مجموعه خوشهبندی شده209، بروزرسانی میشود؛ بدین ترتیب که این الگوریتم مکرراً، از خوشهبندیهای مشخص شده برای نیل به این منظور استفاده میکند. این اقدام و استفاده از میانگین در بردارِ وزنی مانع از بروز بیشبرازش210 خواهد شد. همان طور که مشاهده میشود، هسته اصلی مدل یادگیری، رویه بروزرسانی است و بطوریکه الگوریتم یادگیری، برای بروزرسانی آخرین بردار وزنی، این رویه را فراخوانی میکند.
الگوریتم خوشهبندی سلسله مراتبی پایین به بالا با ورودیهای (X,F):
X={x_1,x_2,…,x_n } و
f(c_i,c_j )=W^T φ(c_i,c_j )
به ازای i=n تا i=1 انجام بده
C_i←{x_i }
پایان حلقه اول
C ←{C_i }1≪i≪n
در همهی جفت خوشههایی که فاصلهی میان آنها را بوسیله تابع f(c_i,c_j ) محاسبه شده است، آنکه دارای بیشترین امتیاز است را در نظر بگیر ⟨c_i ┤,├ c_j ⟩←argmaxf(p)/(p∈ρ(c) )
تا زمانی که |C|1 و f(c_i,c_j )τ ادامه بده
در C، c_i,c_jرا با c_i∪c_j جایگزین کن
حالا از میان جفتهای باقیمانده، جفت بعدی که دارای بیشترین امتیاز است را انتخاب کن ⟨c_i ┤,├ c_j ⟩←argmaxf(p)/(p∈ρ(c) )
پایان حلقه دوم
بازگرداندن C در خروجی
شکل 3-6: الگوریتم خوشهبندی سلسله مراتبی پایین به بالا
الگوریتم بروزرسانی، نخست مانند الگوریتم خوشهبندی حریصانه عمل میکند، تا تمام دادههای ورودی را در قالب خوشههای تک عنصری در مجموعه خوشهبندی C ̂ قرار دهد. در هر تکرار ازحلقه(خطوط 6 تا 17)، یک جفت خوشه ⟨c ̂_i ┤,├ c ̂_j ⟩ که دارای بیشترین امتیاز نسبت به سایرین هستند ادغام میشوند، حلقه آنقدر ادامه پیدا میکند تا تمام خوشهها با هم یکی شده و تشکیل یک خوشه را بدهند و یا جفت خوشه خالی نیز به حداکثر امتیاز برسد. منطق بروزرسانی وزن در خطوط8-11 تعبیه شدهاست. به این ترتیب که اگر بتوان جفت دقیق تری پیدا کرد، آنرا به عنوان جفتی که دارای بالاترین امتیاز است به ورودی پرسپترون در خط 11 دادهمیشود.
الگوریتم یادگیری با ورودیهای (C,T)
ورودی این الگوریتم: دریافت مجموعه خوشهبندیهای ∁ به عنوان مجموعهی آموزشی و تعداد دورههای آموزش T
خروجی: مقدار میانگین شده W ̅
مقدار 0 را به W اختصاص بده
به ازای t=T تا t=1 انجام بده
برای تمام C∈∁ انجام بده
UPDATE(C,W) W←
پایان حلقه اول
پایان حلقه دوم
بازگرداندن W ̅
شکل 3-7: الگوریتم آموزش خوشهبندی حریصانه
اگر چندین جفت خوشه در خطوط 7و10 کاندیدا شوند، به طور تصادفی یکی از آنها انتخاب میشود. این عمل به خصوص در هنگام شروع فرآیند و هنگامی که بردار وزن برابر با صفر است، میتواند موثر واقع شود. از طرفی دیگر در خط 8، تابع خوبی211 یا تناسب استفاده شدهاست، این تابع برای جفت خوشه⟨c ̂_k ┤,├ c ̂_l ⟩ به صورت g(c ̂_k,c ̂_l│C ̂ ) تعریف شده است. این مقدار با توجه به خوشهبندی برچسبدار آموزشیِ ∁ به عنوان صحتِ212 جفتهای هممرجع درنظر گرفته میشود، که در صورت ادغام c ̂_k وc ̂_l ایجاد گردیده است.
رابطه (3-15) g(.)=|{(x,y)∈c_k×c_l |∃c_i∈C:x,y∈c_i }|/(|C ̂_k |.|C ̂_l | )
رابطهی3-4 نشان میدهد، تابع تناسب، در خطوط 8تا 10، جفت خوشهای را انتخاب میکند که در هنگام ادغامشان، نتایج در خوشهبندی به دقت بهتری منتج شوند. به طورکلی این الگوریتم سعی دارد به گونهای با جستجو در دادههای آموزشی، پارامترهایی را پیدا کند که هم بیشبرازش را تحت کنترل داشته باشد(با استفاده از پارامترهای میانگین) و هم دقت خوشهبندی، بیشینه گردد.
الگوریتم UPDATE با ورودیهای (C,W)
X←{C_1∪C_2∪…∪C_m }={x_1,x_2,…,x_n }
به ازای i=n تا i=1 انجام بده
C ̂_i←{x_i }
پایان حلقه اول
C ̂ ←{ C ̂_i }1≪i≪n
تا زمانیکه |C ̂ |1 ادامه بده
⟨c ̂_i ┤,├ c ̂_j ⟩←(argmaxW^T φ(ρ))/(p∈ρ(c) )
β←{⟨c ̂_k ┤,├ c ̂_l ⟩∈ρ(C ̂)|g(c ̂_k,c ̂_l |C ̂)g(c ̂_i,c ̂_j |C ̂)
اگر β≠0 آنگاه
حالا از میان جفتهای باقیمانده، جفت بعدی که دارای بیشترین امتیاز است را انتخاب کن ⟨c ̂_k ┤,├ c ̂_l ⟩←(argmaxW^T φ(ρ))/(p∈ρ(c) )
W←W+φ(c ̂_k,c ̂_l )-φ(c ̂_i,c ̂_j)
پایان شرط اول
اگر ⟨c ̂_i ┤,├ c ̂_j ⟩=⟨0,├ 0⟩┤ آنگاه
بازگرداندن W در خروجی
پایان شرط دوم
در C ̂، c ̂_i,c ̂_jرا با c ̂_i∪c ̂_j جایگزین کن
پایان حلقه دوم
بازگرداندن Wدر خروجی
شکل3-8: الگوریتم بروز رسانی
3-3.جمعبندی
در این فصل الگوریتمهای یادگیری مناسب برای ارزیابی تشخیص مرجع مشترک در این پایاننامه مورد بررسی قرار گرفت، این روشها شامل روشهای ردهبندی پرسپترون، ماشین بردار پشتیبان، درخت تصمیم C5 و خوشهبندی سلسله مراتبی میباشند.
فصل چهارم
سيستم ارزيابی
« شناسايی اشاره و تشخيص اشارههای هممرجع »
4-۱.مقدمه
امروزه اغلب پژوهشگران، فرآیند تشخیص مرجع مشترک را به دو مرحله تقسیم میکنند؛ (۱) کشف اشاره؛ برای شناسایی عبارتهای اسمی که به موجودیتها در دنیای واقعی اشاره دارند، (۲) شناسایی اشارههای که به یک مرجع واحد اشاره دارند. از آنجائیکه ما نیز از این رویکرد پیروی میکنیم، در این فصل، این دو فرآیند را در قالب چارچوبی شامل سیستم ارزیابی معرفی مینمائیم. در بخش اول، برای فرآیند مهم کشف اشاره سیستمی معرفی میکنیم که میتواند اشارههای موجود در پیکره لوتوس را شناسایی کرده و علاوه بر نمایش ویژگیهای مهم هر اشاره، محدوده و هسته هر اشاره را نیز شناسایی و ذخیره نماید. در بخش دوم نیز با به کارگیری الگوریتمهای گفته شده در فصل سوم، به تحلیل جفت اشارههای هممرجع در پیکره میپردازیم.
4-۲. سيستم شناسايی اشاره لوتوس
این سیستم، سه رکن اساسی دارد؛ پیکره ورودی، بانک اطلاعاتی و برنامه کاربردی. ورودی این سیستم پیکرهی نشانهگذاری شده لوتوس میباشد که ویژگیهای آن در فصل دوم معرفی شدند. در ادامه به معرفی مختصری از بانک اطلاعاتی لوتوس و سیستم شناسایی اشارهها میپردازیم.
4-۲-۱. بانک اطلاعاتی
با پیروی از سیستم ارائه شده توسط [40]، ما نیز رویکرد تبدیل پیکره، به اطلاعات ساختار یافته بانک اطلاعاتی را دنبال میکنیم، با این تفاوت که مبنای کار ما استخراج اطلاعاتِ مربوط به اشارههای موجود در پیکره میباشد. به همین منظور بانک اطلاعاتی سیستم پایه لوتوس را طراحی نمودیم، این بانک اطلاعاتی شامل جداولی است که تمام چهار گروه موجودیتهای گفته شده در فصل قبل را پوشش میدهد و به گونهای طراحی شده است تا بتواند نقش فرهنگ جغرافیایی213 را نیز ایفا نموده و به شبکه واژگان نیز مرتبط گردد. در جدول 4-1، یک شمای کلی از جداول این بانک اطلاعاتی نمایش داده شده است.
همانطور که گفته شد، در سیستم شناسایی اشاره با در نظر گرفتن یک سری قوانین و اولویتها، اشارهها و اطلاعات مربوط به آنها را از پیکره استخراج شده و در بانک اطلاعاتی ذخیره میشوند. سیستم شناسایی اشاره ارائه شده دراین پایاننامه، به موازات ذخیره اطلاعات اشارهها در جدول مربوط به اشارهها، تمامی واژههای موجود در متن را نیز به جدول واژگان منتقل مینماید. ویژگیهای جدول واژگان در جدول 4-۱ مشاهده میشود.
شکل4-1: شمای کلی از جداول این بانک اطلاعاتی لوتوس
جدول 4-۱: بانک اطلاعاتی سیستم کشف اشاره؛ جدول واژگان
Word_Table
Word_ID
Primary Key
کلید اصلی
Document_ID
Attribute
به ازای هر متن یک شناسه تعیین میشود
Sentence_ID
Attribute
به ازای هر متن یک شناسه تعیین میشود
Word_String
Attribute
واژه
Word_Feature1
Attribute
نوع واژه
Word_Feature2
Attribute
تعداد واژه
در این جدول اطلاعات پایه در مورد هر واژه ذخیره خواهد شد، این اطلاعات پایه شامل خود واژه، متنی که واژه به آن تعلق دارد، شماره جملهای که واژه به آن تعلق دارد، نوع واژه، مفرد یا جمع بودن واژه میشود. از طرفی دیگر ویژگیهای جدول اشارهها، که شامل اطلاعات مورد نیاز برای تشخیص مرجع مشترک میباشد نیز در جدول 4-۲، آمده است. در جدول اشارهها، نوع اشاره، نوع موجودیت، زیر گروه موجودیت، نوع کلاس موجودیت، کد موجودیتی که اشاره به آن ارجاع دارد، جملهای که اشاره در آن قرار گرفته است و شناسه متنی که اشاره در آن قرار دارد ذخیره خواهد شد. بعلاوه اینکه، محدودهی اشاره نیز در قالب سه ویژگی شناسه واژه آغازین اشاره، شناسه واژه پایانی اشاره و شناسه هسته اشاره ذخیره خواهد شد. لازم به ذکر است که شماره ارجاع از جداول انواع موجودیتهایی که در دنیای واقعی وجود دارند گرفته شده است. (از آنجائیکه تهیه اطلاعات این جدول کاری سخت و زمان بر بوده و از حوزه این پایاننامه خارج است، ما به موجودیتهای ارجاع شده در پیکره لوتوس و برخی از اطلاعات در دسترس اکتفا نمودهایم). نکتهی مهم دیگر اینکه اطلاعات مربوط به اشاره، در اشارههایی که از بیش از یک واژه تشکیل شدهاند، از هسته واژه گرفته شده است.
جدول4-۲: بانک اطلاعاتی سیستم کشف اشاره؛ جدول اشارهها
Tbl_Markables
Markable_ID
Primary Key
شناسه اشاره
Begin_Word_ID
Foreign key
شناسه واژه آغازین اشاره
End_Word_ID
Foreign key
شناسه واژه پایانی اشاره
Head_Word_ID
Foreign key
شناسه واژه هسته
Mention_Type
Attribute
نوع اشاره*
Entity_Type
Attribute
نوع موجودیت*
Entity_Sub_Type
Attribute
نوع موجودیت*
Entity_Class
Attribute
نوع کلاس موجودیت*
Entity
Attribute
شماره
