جملاتی
که توسط نمونه سازی عمومی بدست میآیند
حتما KB
مستلزم
آنهاست.
با
انجام نمونه سازی وجودی یک جمله به KB
اضافه
میشود و خود سور وجودی را میتوان حذف کرد.
اما
از نظر استنتاجی هم ارز هستند.
چون
عمق توابع تو در تو برای جایگزینی یک سور
عمومی بینهایت است الگوریتمهای استنتاج
گزاره ای را با مشکل مواجه میکند.
تکنیک
گزاره سازی ناکارآمد است.
چون
جملات زیادی میسازد که بدرد رسیدن به هدف
نمیخورند.
یک
جمله اتمی مثبت هم یک فراکرد معین حساب
میشود.
امکان
تبدیل همه پایگاههای دانش به فراکرد معین
وجود ندارد.
هر
جمله منطق مرتبه اول قابل تبدیل به CNF
است.
در
یکسان سازی سه نکته مهم وجود دارد:
۱.
هر
متغیر میتواند حداکثر با یک عبارت جایگزین
شود.
۲.
متغیری
که در یک یکسان ساز پر سمت چپ /
قرار
گرفته باشد نمیتواند در سمت راست هیچ یک
از /
ها
قرار بگیرد.
۳.
در
سمت چپ /
فقط
متغیر میتواند باشد.
پیچیدگی
زمانی MGU
از
درجه دوم است.
قانون
استنتاج GMP
یک
قانون استنتاج صحیح است.
امتیاز
GMP
به
گزاره ای این است که جملاتی که نیاز است
را تولید میکند و آنهایی که نیاز نیست را
تولید نمیکند.
برای
استفاده از GMP
باید
هر جمله از پایگاه داده بصورت فراکرد معین
definite
clause باشد.
در
زنجیرسازی رو به جلو برای منطق مرتبه اول
اگر جمله ای نامگذاری جمله ای موجود در
KB
باشد
آنرا به KB
اضافه
نمیکنیم.
زنجیرسازی
رو به جلو صحیح است و برای یک KB
با
فراکردهای معین کامل است.
استلزام
با فراکردهای معین نیمه تصمیم پذیر است.
اگر
فراکردهای معین دارای سمبلهای تابعی
باشند الگوریتم زنجیر سازی رو به جلو ممکن
است بی نهایت حقیقت تولید کند.
مشکلات
الگوریتم زنجیرسازی رو به جلو مرتبه اول:
۱.پرهزینه
بودن تطبیق الگو.
۲.بررسی
مجدد همه قوانین در هر تکرار.
۳.ممکن
است حقایق زیادی تولید کند که به هدف مرتبط
نیستند.
که
برای حل این مشکل میتوان از زنجیر سازی
رو به عقب و یا استفاده از magic
روی
آورد.
مرتب
کردن عطفها همان هیورستیک MRV
است.
روش
مجموعه جادویی ترکیبی از زنجیرسازی رو
به جلو و زنجیر سازی رو به عقب است.
برای
زنجیر سازی رو به عقب باید جملات KB
به
شکل فراکرد معین باشند.
زنجیر
سازی رو به عقب یک الگوریتم مبتنی بر هدف
است.
زنجیرسازی
رو به عقب کامل نیست.
و
مشکل حالتهای تکراری را نیز دارد.
در
برنامه نویسی منطقی معمولا از زنجیر سازی
رو به عقب استفاده میشود(prolog)
همانند
آنچه قبلا گفته شد با هر بار رزولوشن فقط
یک لیترال را میتوان resolve
کرد.
رزولوشن
دودویی به تنهایی یک رویه استنتاجی کامل
نیست و باید آنرا با فاکتورگیری ترکیب
کرد.
در
الگوریتم رزولوشن همه جملات حتی ~a
به
فرم CNF
هستند.
الگوریتم
رزولوشن کامل است.
رزولوشن
نمیتواند تمام نتایج منطقی را بدست دهد
و فقط تعیین میکند آیا یک جمله را میتوان
از روی KB
نتیجه
گرفت و یا نه؟
زنجیرسازی
رو به جلو از رزولوشن کارا تر است ولی
مشکلش این است که پایگاه داده حتما باید
به فرم فراکردهای معین باشد که همیشه
اینجوری نیست.
استراتژی
های رزولوشن:
۱.
تقدم
واحد.
۲.
مجموعه
پشتیبان.
۳.
رزولوشن
ورودی.
۴.
رزولوشن
خطی.
۵.
استراتژی
حذف.
تقدم
واحد در مسایل کوچک مفید است اما در مسایل
متوسط به بالا خیلی مفید نیست و باید کنار
سایر استراتژی ها باشد.
رزولوشن
واحد کامل نیست اما برای پایگاه دانش به
فرم هورن کامل است.
اغلب
تمام عبارات حاصل از نقیض سوالی که از KB
میپرسیم
را به عنوان مجموعه پیشتیبان در نظر
میگیرند.
اگر
نقیض سوال را به عنوان مجموعه پشتیبان در
نظر بگیریم آنگاه رزولوشن همانند روش
عقبگرد هدفگراست و از هدف به سمت حقایق
حرکت میکند.
اگر
مجموعه پشتیبان جوری انتخاب شود که بقیه
جملات ارضا شدنی باشند آنگاه رزولوشن
کامل است.
درخت
اثبات با رزولوشن ورودی کوچکتر از همه
اثباتهای گراف دیگر است.
در
پایگاه دانش هورن modus
ponens نوعی
از رزولوشن ورودی است.
رزولوشن
ورودی برای پایگاه دانش به شکل هورن کامل
است اما برای همه نیست.
رزولوشن
خطی کامل است.
استراتژی
حذف به سه استراتژی دارد:
۱.
حذف
لیترال مطلق.
۲.
حذف
جملات همیشه درست.
۳.
حذف
استنتاج.
روش
حذف صحیح و کامل است.
پرولوگ
برای پاسخ دادن به سوالات از روش زنجیرسازی
رو به عقب استفاده میکند.
در
پرولوگ عملگر =
سبب
ارزیابی عبارت سمت راست و انتساب نتیجه
به متغیر سمت چپ نمیشود!
در
پرولوگ بهتر است is
را
جایی به کار ببریم که نیاز به ارزیابی
عبارت ریاضی سمت راست آن باشد.
در
پرولوگ میتوان لیستهای تودرتو داشت.
به
کمک cut
میتوان
از انجام محاسبات غیر ضروری جلوگیری
کرد.(حتما
یاد گرفته شود)
در
برنامه ای که cut
ندارد
میشود جای جملات را میشود عوض کرد اما در
برنامه ای که cut
دارد
نمیشود.
نقاط
ضعف پرولوگ:
استنتاج
اضافی و حلقه نامتناهی.(چون
عقبگرد است)
مشکل
اول را میتوان با memorization
حل
کرد و مشکل دوم باعث میشود پرولوگ کامل
نباشد.
Deduction
میگوید
اگر بدانیم گزاره p
و
گزاره p
میدهد
q
درست
است آنگاه q
درست
است.
Induction
همان
استنتاج استقرایی است مثلا از دیدن تعداد
زیادی قو که سفید هستند به این نتیجه
میرسیم که همه قوها سفیدند که این غلط
است.
Abduction
با
دانستن اینکه گزاره p
میدهد
q
و
گزاره q
هر
دو صحیح هستند نتیجه میگیریم p
صحیح
است که این استنتاج نیز اشتباه است.
در
اثبات با برهان خلف از رزولوشن استفاده
میکنیم و یک استنتاج کامل است.
اگر
در رزولوشن یکسان سازی انجام نشود ویژگی
کامل بودن آن نقض میشود.
چیزهایی
که باید از کتاب خوانده شود:
لیست
جانشینی.
عمل
جایگزینی.
نمونه
سازی عمومی و وجودی.
ثابت
اسکولم.
تقلیل
استنتاج مرتبه اول به استنتاج گزاره ای.
تعریف
فراکرد معین.
پایگاه
دانش datalog.
مراحل
تبدیل جمله به CNF.یکسان
سازی.
کلی
ترین یکسان ساز(MGU).
استنتاج
قیاسی و استنتاج قیاسی تعمیم یافته در
منطق مرتبه اول.
الگوریتم
زنجیرسازی روبه جلو در FOL.
مرتب
کردن عطفها.
زنجیر
سازی رو به جلو افزایشی.
مجموعه
magic.
زنجیرسازی
رو به عقب در FOL.
لیترالهای
مکمل.
استنتاج
رزولوشن در FOL.
فاکتورگیری.
الگوریتم
رزولوشن.
تقدم
واحد و رزولوشن واحد.
مجموعه
پشتیبان.
رزولوشن
ورودی.
رزولوشن
خطی.
استراتژی
حذف.زبان
پرولوگ
هیچ نظری موجود نیست:
ارسال یک نظر