شبکه منطقی مارکوف (Markov Logic Networks)

/
/
/

شبکه ی منطقی مارکوف یا(MLN ) ، یکی از الگوریتم های مورد استفاده در هوش مصنوعی است که در سال ۲۰۰۶ به عنوان پایان نامه دکترای یکی از دانشجویان دانشگاه واشنگتن معرفی گردید.
اپلیکیشن های یادگیری ماشین های هوش مصنوعی مدرن با درجه های پیچیدگی و عدم قطعیتشان دسته بندی می شوند. پیچیدگی توسط منطق مرتبه اول به خوبی کنترل می شود و عدم قطعیت توسط مدل های گرافیکی احتمالاتی.
آنچه کمبودش احساس می شد ترکیب این دو بود.
Markov logic networks (MLNs) این کمبود را با اضافه نمودن وزن به فرمول ها یا کلاز های منطقی و برخورد با آنها به عنوان تمپلیت هایی برای ویژگی های فیلدهای تصادفی مارکوف برطرف کرد.
این شبکه منطقی، یک منطق احتمالاتی است که ایده‌های شبکه مارکوف و منطق مرتبه اول را به کار می‌گیرد و استنتاج نا مطمئنی را ارائه می کند. شبکه‌های منطقی مارکوف ، منطق مرتبه اول را تعمیم می‌دهند؛ به این معنا که، در یک محدوده، تمام جملات unsatisfiable احتمال صفر می گیرند و تمام tautology ها (جملاتی که Satisfy می کنند) احتمال یک می گیرند. شبکه منطقی مارکوف به طور خلاصه کلکسیونی از فرمول هایی از منطق مرتبه اول است که به هر یک از فرمول هایک عددی حقیقی تخصیص داده شده است(وزن). راس های گراف شبکه فرمول های اتمی هستند و یال ها رابط های منطقی استفاده شده در ساخت فرمول می باشند. هر فرمول بعنوان یک کلیک در نظر گرفته می‌شود و Markov blanket مجموعه‌ای از فرمول ها ست که درون آن‌ یک اتم داده شده ظاهر می شود. یک تابع پتانسیل به هر فرمول اختصاص داده می شود و هنگامی که فرمول درست است مقدار ۱ می‌گیرد و در غیر اینصورت صفر. تابع پتانسیل ترکیبی از وزن برای ایجاد Gibbs measure و تابع تجزیه یا partition function برای ایجاد گراف مارکوف می باشد. نکته مهم دیگری که در شبکه های منطقی مارکوف وجود دارد و در مقاله اصلی ارائه شده برای این روش ذکر شده این است که فرمول های اتمی ارزش درستی ندارند مگر آنکه آن‌ها پایه گذاری شده باشند یا به عبارتی grounded  باشند و  interpretationارایه دهند؛ یعنی تا زمانی که ground atom ها با صدها تفسیر باشند ارزش درستی (truth value) دارند. بنابراین شبکه منطقی مارکوف تنها با توجه به پایه و تفسیر ویژه (specific grounding and interpretation) تبدیل به شبکه مارکوف می‌شود، شبکه مارکوف حاصل از این روش، شبکه مارکوف پایه یا ground Markov network نامیده می شود.
راس های گراف شبکه مارکوف پایه، اتم های پایه هستند. بنابراین اندازه شبکه مارکوف حاصل به شدت (بصورت نمایی) بستگی به تعداد constant ها درdomain of discourse یا ناحیه بحث دارد.

تکنیک های استنتاج این روش شامل تست satisfiability، auxiliary-variable MCMC و lifted belief propagation هستند. یادگیری شامل voted perceptrons، تکنیک های مرتبه دوم، pseudo-likelihood، inductive logic programming یا برنامه های منطقی استدلالی، predicate invention و transfer learning می باشد. کاربردهای این روش شامل استخراج اطلاعات یا دانش و یکپارچه سازی، پردازش زبان طبیعی، robot mapping، شبکه های اجتماعی، computational biology و غیره است.
در واقع مجموع منطق مرتبه اول (First Order Logic) و شبکه های مارکوف (Markov Networks) می شود Markov Logic Networks.
برای معرفی شبکه منطقی مارکوف ابتدا شبکه مارکوف را تعریف می کنیم:
شبکه مارکوف یک مدل گرافیکی احتمالاتی غیر جهت دارد است که توزیع احتمال مشترک را مشخص می کند. در یک شبکه مارکوف هر راس نشان دهنده یک متغیر تصادفی و هر یال نشان دهنده ارتباط وابستگی میان دو راسی است که به هم وصل نموده است. نود در شبکه مارکوف از نود دیگر با داشتن مجموعه همسایگی اش استقلال شرطی دارد. هر کلیک در گراف یک تابع پتانسیل مربوط به آن دارد که حالات مورد احتمال المان های کلیک را به اعداد حقیقی غیر منفی نگاشت می دهد. توزیع مشترک شبکه مارکوف بصورت زیر است:
که در آن X برداری از متغیرهای تصادفی نشان داده شده در شبکه مارکوف، x ، assignment ای به این متغیرهای تصادفی ، φk تابع پتانسیلی که حالات K امین کلیک را به اعداد حقیقی غیر منفی نگاشت می دهد و Z ، constant   normalizationای است که اطمینان حاصل می کند از اینکه جمع  احتمال همه مقادیر محتمل x برابر با ۱ می شود. بهتر است شبکه مارکوف بصورت مدل log-linear زیر نمایش داده شود:
در این نمایش  fj(x)ویژگی متناظر با هر حالت محتمل از کلیک و wj وزن مربوط به ویژگی است که معمولا مقدار تابع پتانسیل است. در شبکه مارکوف هر استنتاج #P complete است. بنابراین الگوریتم های تخمین مانند Markov Chain Monte Carlo و Gibbs Sampling مورد استفاده برای استدلال تقریب خوب استفاده می شوند.

منطق مرتبه اول:
منطق مرتبه اول سیستمی از نمایش دانش در سیستم های استدلالی است. این سیستم نسبت به منطق گزاره ای خیلی رساتر است زیرا علاوه بر quantification امکان predicate را هم ارائه می دهد.
سینتکس منطق مرتبه اول از متغیرهای تعریف شده توسط کاربر، کانستنت ها، توابع و گزاره ها تشکیل شده است.
محدوده متغیرها در طول آبجکت های دامین است و معمولا با حروف کوچک نمایش داده می شوند. یک constant نشان دهنده یک آبجکت خاص است مانند یک شخص یا یک سازمان. توابع برای نگاشت آبجکت های خاص یا چندین آبجکت به سایر آبجت ها استفاده می شوند ( John =FatherOf(Steve) به معنی تابع پدر بودن: جان پدر استیو است). گزاره ها تعیین کننده ویژگی های خاص یا ارتباطات میان دو آبجکت هستند (Parent(John,Steve)).
حال که توضیح کوتاهی درباره منطق مرتبه اول و شبکه های مارکوف آورده شد می توانیم در باره شبکه های منطقی مارکوف یا MLN ها صحبت کنیم.
MLN در واقع روشی است که توسط Matthew Richardson و Pedro Domingos از دانشگاه واشنگتون ارائه شده. این دو، روشی را ارائه کردند که منطق مرتبه اول و مدل های احتمالی گرافیکی را ترکیب کرده و بصورت یک نمایش واحد در آورده است. یک MLN یک پایگاه دانش مرتبه اول است که به هر کلاز آن یک وزن نسبت داده شده است. که همراه با مجموعه ای از constant ها آبجکت را در دامین نمایش می دهند . این شبکه منطقی یک شبکه مارکوف را نشان می دهد که برای هر کلاز مرتبه اول محتمل در KB دارای یک ویژگی است، همراه با وزن مربوط به آن. استنتاج در  MLN توسط MCMC روی زیرمجموعه کمینه ground network که برای پاسخگویی به کوئری مورد نیاز است انجام می شود. وزن ها از پایگاه داده های رابطه ای با بهینه سازی مرتب (تکرارگونه) یک معیار pseudo-likelihood آموزش داده می شوند. این قسمت نیز بصورت دلخواه است یعنی این آپشن نیز وجود دارد  که کلاز های اضافی دیگر با استفاده از تکنیک های برنامه نویسی منطقی استنتاجی یاد گرفته شوند.
یک KB (knowledge base یا پایگاه دانش) مرتبه اول را می توان بصورت مجموعه ای از hard constraint ها روی مجموعه ای از world های محتمل دید: اگر world ای از حتی یک فرمول تخطی کرد، احتمال آن صفر می شود. ایده اصلی منطق مارکوف این است که این محدودیت های سخت را نرم کند تا عدم قطعیت را کنترل کند: زمانی که world ای از یک فرمول در پایگاه دانش تخطی کرد احتمال آن کمتر می شود ولی غیر محتمل نمی شود. به هر ویژگی یک وزن نسبت داده می شود. اگر گزاره های پایه حداقل در یک پایه از یک کلاز با هم ظاهر شوند این نشان می دهد که رابطه وابستگی میان گزاره ها وجود دارد در نتیجه شبکه مارکوف برای لینک دادن این نودها از یک یال استفاده می کند در نتیجه هر فرمول یک کلیک در شبکه مارکوف پایه ایجاد می کند. به محض اینکه ساخته شود می توان مانند شبکه های مارکوف از شبکه مارکوف پایه نیز استنتاج کرد.
هر world  هرچه از تعداد فرمول کمتری تخطی کند احتمالش بیشتر می شود. به هر فرمول یک وزن  اختصاص داده شده که در جدول زیر نمونه آن آورده شده است. این وزن ها نشان دهنده این هستند که قدرت این محدودیت چگونه است: هرچه وزن بالاتر باشد تفاوت میان لاگ میان world ای که کلاز را satisfy می کند و world ای که satisfy نمی کند بیشتر است، فرض می کنیم بقیه موارد مشابه هستند.

تعریف دیگری از MLN به این صورت است: یک شبکه منطقی مارکوف L مجموعه ای از زوج های(Fi,wi) است که  Fi فرمول یا کلازی در منطق مرتبه اول بوده و wi یک عدد حقیقی است.  همراه با  مجموعه متناهی از constant هایی به نام C ={c1, c2, . . . , c|C|} یک شبکه مارکوف را تعریف میکند ML,C  که:
۱- ML,C حاوی یک نود باینری برای هر  پایه ممکن از هر اتمی که در L ظاهر می شود می باشد. مقدار نود اگر اتم پایه، True باشد ۱ است در غیر این صورت ۰٫
۲- ML,C حاوی یک ویژگی برای هر پایه ممکن از هر کلاز Fi در L است. ارزش این ویژگی اگر ground formula، True باشد ۱ است در غیر این صورت ۰ است. وزن ویژگی wi مربوط به Fi در L است.
بنابراین یالی میان دو نود ML,C وجود دارد اگر و تنها اگر اتم های پایه مربوطه حداقل در یک پایه از یک formula در L با هم ظاهر شوند. برای مثال MLN ای شامل formulas یا کلازهای  xSmokes(x)Cancer(x) (سیگار باعث سرطان می شود) و xySmokes(x)Friends(x, y)Smokes(y)
(اگر x و y دوست باشند و x سیگار بکشد آنگاه y هم سیگار می کشد یعنی دوستان عادات سیگار کشیدن یکسانی دارند) برای دو constant ، Anna و Bob به کار گرفته شده (یا به طور خلاصه A و B) که ground Markov network شکل زیر را به دست می دهد. ویژگی های آن عبارتند از
Smokes(Anna) Cancer(Anna)و …
توجه کنید که با اینکه دو کلاز فوق با توجه به اظهارات منطقی جهانی false هستند، به عنوان ویژگی های وزن دار یک MLN قواعد آماری معتبری به دست می آورند و در واقع نشان دهند یک مدل شبکه اجتماعی استاندارد می باشند.
شکل بالا Ground Markov network به دست آمده توسط MLN است که شامل کلازهایی که در بالا معرفی کردیم می شود.
به عنوان مثال ساده ای از Social Network Analysis از شبکه اجتماعی ساده دوستان، سیگار و سرطان استفاده شده. شبکه سعی می کند ارتباطات دوستی میان افراد، عادات سیگار کشیدن و احتمال سرطان را مدل کند.
MLN را می توان به عنوان تمپلیتی برای ساخت شبکه های مارکوف دید. توزیع احتمال worldهای محتمل x مشخص شده توسط ground Markov network ML,C بصورت زیر است:
زمانی که عملیات جمع روی همه ground clauseها به پایان برسد، Z کانستنت normalize کردن است ، wi وزن iمین کلاز است، اگر iامین کلاز true باشد fi = 1 و در غیر اینصورت fi = 0 خواهد بود. میتوان معادله را متعاقبا بصورت زیر نوشت:
F تعداد کلازهای MLN است و ni(x) تعداد پایه های صحیح  Fi در X می باشد. هرچه وزن کلاز بیشتر شود، MLN به طور فزاینده یک پایگاه دانش کاملا منطقی را شبیه سازی می کند و با متناهی کردن همه وزنهای نامتناهی تبدیل به یک پایگاه دانش منطقی می شود. زمانی که وزنها مثبت و متناهی باشند و همه فرمول ها بصورت همزمان satisfiable باشند، راهکارهای satisfy کننده حالات توزیع نمایش داده شده توسط ground Markov network خواهند بود. منطق مارکوف تناقضات میان فرمول ها یا کلازها را ممکن میکند که با وزن کردن هر دو طرف به سادگی برطرف می شود. این کار باعث می شود به خوبی با چندین پایگاه دانش ادغام شود. منطق مارکوف یک رویکرد طبیعی و قدرتمند برای مسائل ادغام دانش و داده در نمایش های مختلف که به خوبی هم تراز نمی شوند ارائه می دهد.
به راحتی می توان دید که همه مدل های گسسته احتمال از جمله شبکه های مارکوف و شبکه های بیزین را می توان با منطق مارکوف نمایش داد. بسیاری از مدلهایی که اغلب در هوش مصنوعی استفاده می شوند را می توان با MLN ها نمایش داد و آنها را با اضافه نمودن فرمول های مربوطه (کلازهای مربوطه) ترکیب کرده و بسط داد.
مهم تر اینکه منطق مارکوف ساخت مدل های non-i.i.d.  (مدل هایی که در آنها آبجکت ها مستقل نیستند و به طور یکسان توزیع شده اند) را آسان می کند.
زمان کار با منطق مارکو ف تخمین برای نمایش منطقی در نظر گرفته می شود:
Constant های مختلف نشان دهنده آبجت های مختلف (نام های منحصر به فرد) هستند، تنها آبجکت هایی که در دامین وجود دارند آنهایی هستند که با استفاده از سمبل های تابع و کانستنت قابل نمایش اند و مقدار هر تابع برای هر تعداد argument یا استدلال همواره یک constant شناخته شده است (توابع شناخته شده). این تخمین ها تضمین می کند که تعداد worldهای محتمل متناهی است و اینکه شبکه منطقی مارکوف توزیع احتمال به خوبی تعریف شده ای ارائه می دهد. این تخمین ها در بسیاری کاربردهای عملی کاملا منطقی هستند و استفاده از MLN ها را ساده می سازند.
کاربردهای شبکه منطقی مارکوف
از شبکه منطقی مارکوف برای استخراج اطلاعات استفاده می شود. به عبارت دقیق تر برای پیدا کردن موجودیت های نام در یک جمله برای مثال تگ کردن نام های افراد به  عنوان اسم شخص و تگ کردن نام های Iraq، Iran و US و … به عنوان موجودیت های سیاسی .
برای این کار می توان از روش MLN که یک مدل یادگیری رابطه ای آماری قدرتمند است و نمایش قوی ارائه می کند استفاده نمود. با استفاده از این روش برای NAME TAGGING می توان وابستگی های پیچیده در استخراج نام را مدل کرد.
در این مثال مربوط به entity tagging model می توان برخی فرمول های منطق مرتبه اول را برای به دست آوردن مدل مورد نظر تعریف کرد:
Identical tokens should be tagged the same: SameToken(x, y) ∧ Label(x, l) ⇒ Label(y, l)
در این فرمول x و y متغیرهایی از جنس token هستند و I متغیری برای نوع lable است. برای این فرمول می توان وزن هم تعریف کرد و هم می تواند از داده های آموزشی وزنها را یاد بگیرد.
استفاده از این فرمول برای توکن های A و B و لیبل هایPerson (P) و Organization(O) شبکه مارکوف پایه زیر را می دهد:

استنتاج در MLN نیازمند منطق و استنتاج در احتمالات و در وابستگی های قطعی است. الگوریتم های MCMC از قدیم برای استنتاج در مدل های احتمالاتی و الگوریتم های satisfiability برای سیستم های کاملا منطقی استفاده می شدند. از آنجایی که MLN هم شامل وابستگی های قطعی و هم احتمالاتی است هیچ یک از این الگوریتم ها نتایج خوبی نمی دهند. در این کابرد از الگوریتم MC-SAT استفاده شده تا ارزش گزاره های پرسشی را تعیین کند. الگوریتم MC-SAT الگوریتمی است که تکنیک های MCMC و satisfiability را ادغام میکند بنابراین در استنتاج MLN خوب عمل می کند.
سایر کاربردهایی که MLN دارد با توجه به آنچه در دانشگاه واشنگتن تدریس می شود از ابزار نرم افزاری به نام Alchemy استفاده می شود و گفته شده که هر کس که  نیاز به پایگاه دانشی با عدم قطعیت دارد Alchemy را مفید خواهد یافت. برای استفاده از این ابزار نیاز به آشنایی با الگوریتم های کلاسیک یادگیری ماشین و منطق مرتبه اول و منطق مارکوف و برخی تئوری های احتمالاتی وجود دارد. کد این نرم افزار برای دانلود قرار داده شده است که به زبان لینوکس می باشد و آموختار یا tutorial آن نیز در سایت قرار داده شده و انواع اپلیکیشن هایی که این ابزار ارائه می دهد نام برده شده است.
http://alchemy.cs.washington.edu/tutorial/tutorial.pdf
این آموختار نشان می دهد که یادگیری های متداول چگونه انجام می شود و کابر را با استنتاج و یادگیری در منطق مارکوف آشنا می کند طوری که کاربر بتواند از ابزارهای اولیه برای توسعه اپلیکیشن های مخصوص به خود در این framework استفاده کند. این نرم افزار توسط ارائه دهنده روش شبکه منطقی مارکوف ساخته شده و هنوز همه روش های جدید در آن در نظر گرفته نشده است و تمام دیتابیس های مرتبط با آن هم در اینترنت برای دانلود موجود است.
Alchemy می تواند اعمال اصلی structure learning، weight learning و inference را انجام دهد. که دو مورد اول شامل یادگیری ساختار یا پارامترهای یک مدل با دادن یک دیتابیس آموزشی شامل اتم های پایه است. مورد آخر احتمال یا حالتی که محتمل تر است برای اتم های کوئری با دادن یک پایگاه داده تست شامل اتم های پایه evidence را شامل می شود.
سایر کاربردهای شبکه منطقی مارکوف که در این نرم افزار قابل پیاده سازی است عبارتند از:
• Collective classification
• Link prediction
• Entity resolution
• Social network modeling
• Information extraction

مراجع
http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=40&ved=0CGMQFjAJOB4&url=http%3A%2F%2Fcse.iitkgp.ac.in%2Fresgrp%2Fcnerg%2Fosn%2Fparag_singla.pptx&ei=vfG3VOv_MsrzasGPgegN&usg=AFQjCNFxQoOW1KXoE-q2TourM2eyPR5SMQ&sig2=Qrt0br3OEgAojI-71JUseg&bvm=bv.83640239,d.bGQ&cad=rja
http://homes.cs.washington.edu/~pedrod/papers/mlj05.pdf
http://www.cse.iitd.ernet.in/~parags/papers/thesis.pdf
http://en.wikipedia.org/wiki/Markov_logic_network
ftp://ftp.cs.utexas.edu/pub/techreports/honor_theses/cs-08-11-chen.pdf
http://homes.cs.washington.edu/~pedrod/803/
http://alchemy.cs.washington.edu/tutorial/tutorial.pdf

————————————-

برگردان : هدی ابیضی

نظر بدهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

It is main inner container footer text