هوش مصنوعی: استنتاج در منطق مرتبه اول

هوش مصنوعی: استنتاج در منطق مرتبه اول

اسلاید 1: 1فصل نهماستنتاج در منطق مرتبه اولهوش مصنوعیايمان مختاري فرددانشگاه پيام نور شهركرد

اسلاید 2: استنتاج مرتبه‌ي اولبر حسب مطالب فصل 7 ، برای استنتاج در منطق مرتبه اول ، ابتدا باید عبارت منتطق مرتبه اول را به گزاره ای تبدیل کنیم و سپس عبارت گزاره ای را با تابع Pl_resolution استنتاج کنیمدر روند گزاره ای کردن عبارت FOL باید سورها و.... حذف شوند چون عبارت گزاره ای سور نداردمراحل تبدیل مرتبه اول به گزاره ای (مهم) حذف دو شرطی و شرطیاعمال نقیض (طبق قوانین دمورگان)انتقال سورها به اول عبارتحذف سور وجودی و جایگزین کردن اسکلماگر متغیر سور وجودی به صورت باشد متغیر اسکلم a جایگزین و سور حذفاگر سور وجودر در یک سور عمومی باشد از تابع اسکلم برای حذف استفاده می کنیکحذف ضمنی سور عمومی(بدون جایگزین کردن)تبدیل به شکل نرمال عطفیx P(x)x (P(x) ᴧ y (z ( q(y,z)))) x (y (z (P(x) ᴧ q(y,z)))) P(a)x (y q(y,z)) x (q(f(x),z)) x (z (P(x) ᴧ q(f(x),z))) (P(x) ᴧ q(f(x),z))

اسلاید 3: استنتاج مرتبه‌ي اولهدف از استنتاج در منطق مرتبه اول ، یافتن الگوریتمی است که بتواند به هر سوالی قابل پاسخ گویی با منطق مرتبه اول ، پاسخ دهد و تعیین کند که آیا استلزام و ایجاب به وجود می آید یا خیر؟روش اول برای استنتاج در منطق مرتبه اول حذف سور و تبدیل پایگاه دانش به منطق گزاره ای و استفاده از قوانین استنتاج در منطق گزاره ای است.لذا روشهای زیر به عنوان الگوریتمهای استنتاج در منطق مرتبه اول ارائه شده اند :نمونه‌سازي عمومی (حذف سور عمومی یا Universal instantiation (UI) )نمونه‌سازي وجودی (حذف سور وجودی یا Existential instantiation (EI) )حدف سورها1- نمونه‌سازي عمومی هر نمونه از يك جمله داراي سور عمومي، توسط آن جمله قابل استلزام است.نمونه‌سازي عمومی براي هر متغيّر  و اصطلاح زمينه g، به‌صورت زیر نوشته مي‌شود:که در آن Subst(,) نتيجه اعمال جايگزيني  به جاي  است. به عنوان مثال جملات King (John)  Greedy (John)  Evil (John)King (Richard)  Greedy (Richard)  Evil (Richard)King (Father (John))  Greedy (Father (John))  Evil (Father (John))از نمونه‌سازی عمومی جملهx King (x)  Greedy (x)  Evil (x) با جايگزيني هاي {x  John}، {x  Richard} و {x  Father (John)} به‌دست‌مي‌آيد.

اسلاید 4: در مورد ∃x : LivesIn(x, Springfield) ∧ knows(x, Homer) ما مي دانيم كه اين بايد براي لااقل يك شي ، درست باشد . بياييد اين شي را K بناميم ؛ داريم ، LivesIn(k, Springfield) ∧ knows(k, Homer) که در این مورد،K يك ثابت اسكُولِم ناميده مي شود.پس ، براي هر عبارت α و متغیر v و سمبل ثابت k كه در جاي ديگري در پايگاه دانش وجود ندارد داريم :2- نمونه‌سازي وجودیمثال : نتيجه ي ∃xCrown(x) ∧ OnHead (x, John) به صورت Crown(C1) ∧ OnHead(C1,John) مي تواند باشد كه C1 به وجود آمده از يك سمبل ثابت جديد به نام ثابت اسكلم می باشد.مثالي ديگر : از ∃x : d(x y ) / dy = x y ما نتيجه مي گيريم ، d(ey ) / dy = ey ، e ای که به وجود آمده است يك سمبل ثابت جديد مي باشد)گزاره بنديما مي توانيم هر عبارت داراي سور وجودي را با يك نوع اسكلمايز شده جايگزين نماييم . براي عبارت هاي با سور عمومي ، مي توانيد هر جايگزين ممكن را جايگزين نماييد ؛ كه اين كار به ما اجازه مي دهد كه از قانون هاي استنتاج گزاره اي استفاده نماييم . البتّه اين كار خيلي ناكارآمد مي باشد ؛ تا سال 1960 از همين روش استفاده مي كردند .

اسلاید 5: پایگاه دانش مقابل را در نظر بگیرید:x King (x)  Greedy (x)  Evil (x)King (John)Greedy (John)Brother (Richard, John)با اعمال تمامی جايگزيني هاي ممکن به اوّلین جمله، داریم: (پایگاه دانش گزاره‌ای شده)(UI) ({x/John} و {x/Richard})King (John)  Greedy (John)  Evil (John)King (Richard)  Greedy (Richard)  Evil (Richard)ساده سازی به استنتاج گزاره ایKB جدید گزاره اي سازي شده است. سيمبول هاي(نمادها) گزاره اي عبارتند از:King(John) , Greedy(John) , Evil(John) , King(Richard)هر پایگاه دانش با منطق مرتبه اول را می توان گزاره ای کرد به گونه‌ای که ایجاب در آن حفظ شود، یعنی هر جمله زمینه‌ای که از پایگاه دانش جدید به دست می آید، اگر و فقط اگر از پایگاه دانش جدید نیز حاصل شود.یک روش برای استنتاج: پایگاه دانش و پرس‌وجوي مرتبه‌ي اوّل را گزاره‌اي نمود، و از الگوریتمهای استنتاج گزاره ای برای استنتاج استفاده کرد.• مشكل: در مورد سيمبول هاي تابعي(دارای خروجی) تعداد نامحدودي ترم زميني وجود دارد، مثلاً:Father(Father(Father(John)))

اسلاید 6: قضیه هربراند (1930): اگر جمله‌اي به وسیله پایگاه دانش مرتبه‌ي اوّل اصلی ایجاب شود، آنگاه یک اثبات با زيرمجموعه‌ي متناهی از پایگاه دانش گزاره‌اي شده، وجود دارد. با توجه به متناهی بودن زيرمجموعه، يك مقدار حداکثر براي عمق تودرتو بودن اصطلاحات زمینه موجود مي‌باشد.قضیه هربراند (1930) : اثبات با یک زیر مجموعه...قضیه ي تورينگ و چورچ (1936) : فقط بلی می تواند بگویدمي‌توان ابتدا زيرمجموعه‌اي با استفاده از تمامی نمونه‌سازيهاي نمادهای ثابت (Richard و John) را توليد كنيم. سپس، با تمامی اصطلاحات با عمق 1 (Father (Richard) و Father (john))، و بعد از آن تمامي اصطلاحات با عمق 2 و ... را بيابيم تا زمانی كه قادر به اثبات گزاره‌اي جمله ایجاب شده بشویم.قضیه تورینگ و چرچ (1936): مسأله ايجاب در منطق مرتبه‌ي اوّل، يك مسأله‌ي نيمه‌تصميم‌پذير است، يعني الگوريتمهايي وجود دارد كه به هر جمله ايجاب شونده پاسخ مثبت مي‌دهد. امّا هيچ الگوريتمي وجود ندارد كه به هر جمله ايجاب‌ناپذير پاسخ منفي بدهد.

اسلاید 7: مشكلات گزاره اي سازي نمودن• به نظر مي رسد كه گزاره اي سازي كردن جملات نامربوط زيادي توليد مي كند. براي مثال از جملات زير:∀x King(x) ∧ Greedy(x) ⇒ Evil(x)King(John)Brother(Richard,John)حاصل Evil(John) است ، اما گزاره اي سازي كردن حقايق زيادي مانند Greedy(Richard) توليد مي كند كه نامربوط مي باشنديكسان سازي (Unification ) : حل مشکل گزاره سازی:سازگار بودن دو جمله اگر يک جایگزینی θ وجود داشته باشد كه مقدم استلزام را با جملات موجود در پایگاه دانش، يكسان‌سازي كند، یا به عبارتی يكسان سازی، اين است كه ما فقط مي خواهيم جايگزين هايي براي عباراتي كه به ما كمك مي كنند چيزهايي را ثابت نماييم پيدا كنيم .آنگاه مي‌توان با اعمال θ، تالي استلزام را اظهار نمود. مانند جايگزيني{x / John} در پایگاه دانش، Evil (John) را نتیجه می‌دهد.x King (x)  Greedy (x)  Evil (x)King (John)Greedy (John)Brother (Richard, John)ابتدا باید بتوان روشی برای انتخاب مناسب x پیدا کرد (یکسان سازی).Unify(α,β) = θ if αθ = βθ {y/John,x/Mother(John)}}{fail}{x/OJ,y/John}}{x/Jane}}Unification: دو ترم s و t اصطلاحاً unifiable هستند اگر يک جانشينی مانند وجود داشته باشد به طوری که ..

اسلاید 8: قیاس استثنائی تعمیم یافته آیا می‌توان در پایگاه دانش با انتخاب مقداری برای x ، یک دفعه یک واقعیت را استنتاج کرد؟ x King (x)  Greedy (x)  Evil (x)King (John)y Greedy (y)Brother (Richard, John)برای این کار باید قانونp1, p2, … , pn, ( p1  p2  …  pn q) Subst(θ,q)p1 is King(John) p1 is King(x) p2 is Greedy(y) p2 is Greedy(x) θ is {x/John,y/John} q is Evil(x) q θ is Evil(John)در این قانون اگر جمله هایی به صورت ^ با هم ترکیب شوند و جمله ی دیگری را ایجاد کنند. در را الزام می کرد با وجود چند جمله به تعداد جملات ترکیبی می توان جایگزاری مقادیرθ در q را طبق شرط یکسان سازی نتیجه گرفت که به آن قیاس استثنایی توسعه یافته می گویند

اسلاید 9: توابع ابتدایی Ask وTell و یا استفاده از نسخه ابتدایی تر مثل Store و Fetchپرس و جوها (ASK) ) از طریق یک شبکه شمول به دست می آیند. در این شبکه هر گره در شبکه تنها با یک جابجایی از والد خود بدست می آید(شکل صفحه 130)ذخیره و بازیابی

اسلاید 10: قانون می گوید که برای یک آمریکایی، فروش تسلیحات به ملل متخاصم جرم است.کشور نونو که دشمن آمریکا است، تعدادی موشک دارد و تمامی موشکهایش را از سرهنگ وست که یک آمریکایی است، خریده است.ثابت کنید سرهنگ وست مجرم است.ذخیره و بازیابی

اسلاید 11: مثالی از یک پایگاه دانشفروش تسلیحات به ملل متخاصم برای یک آمریکایی جرم استAmerican(x)  Weapon(y)  Sells(x,y,z)  Hostile(z)  Criminal(x)نونو تعدادی موشک دارد., x Owns(Nono,x)  Missile(x):Owns(Nono,M1) and Missile(M1)سرهنگ وست تمامی موشک ها را را به نونو فروخته بودMissile(x)  Owns(Nono,x)  Sells(West,x,Nono)موشک ها جزو تسلیحات هستندMissile(x)  Weapon(x)هر دشمن آمریکا به عنوان متخاصم تلقی می شودEnemy(x,America)  Hostile(x)وست یک آمریکایی استAmerican(West)کشور نونو دشمن آمریکاستEnemy(Nono,America)

اسلاید 12: مثالی از یک پایگاه دانشفروش تسلیحات به ملل متخاصم برای یک آمریکایی جرم استAmerican(x)  Weapon(y)  Sells(x,y,z)  Hostile(z)  Criminal(x)نونو تعدادی موشک دارد., x Owns(Nono,x)  Missile(x):Owns(Nono,M1) and Missile(M1)سرهنگ وست تمامی موشک ها را را به نونو فروخته بودMissile(x)  Owns(Nono,x)  Sells(West,x,Nono)موشک ها جزو تسلیحات هستندMissile(x)  Weapon(x)هر دشمن آمریکا به عنوان متخاصم تلقی می شودEnemy(x,America)  Hostile(x)وست یک آمریکایی استAmerican(West)کشور نونو دشمن آمریکاستEnemy(Nono,America)

اسلاید 13: الگوریتم زنجیره ای پیش رو از جملات بسیط حرکت می کند و مبتنی بر داده هاست

اسلاید 14: الگوریتم زنجیره ای پیش رو

اسلاید 15: الگوریتم زنجیره ای پیش رو

اسلاید 16: الگوریتم زنجیره ای پیش رو

اسلاید 17: ویژگی های الگوریتم زنجیره ای پیش رواین الگوریتم صحیح است به دلیل آنکه هر استنتاج از به کارگیری قیاس استثنائی تعمیم یافته ناشی می شود که آن نیز به نوبه خود صحیح می باشد.این الگوریتم در مورد پایگاه های دانش با بندهای معین کامل است.

اسلاید 18: الگوریتم زنجیره ای پس رو از هدف حرکت می کند تا به داده ها برسد یعنی هدف گراست

اسلاید 19: مثالی از الگوریتم زنجیره ای پس رو

اسلاید 20: مثالی از الگوریتم زنجیره ای پس رو

اسلاید 21: مثالی از الگوریتم زنجیره ای پس رو

اسلاید 22: مثالی از الگوریتم زنجیره ای پس رو

اسلاید 23: مثالی از الگوریتم زنجیره ای پس رو

اسلاید 24: مثالی از الگوریتم زنجیره ای پس رو

اسلاید 25: مثالی از الگوریتم زنجیره ای پس رو

اسلاید 26: مثالی از الگوریتم زنجیره ای پس رو

اسلاید 27: برنامه نویسی منطقی ( اثبات استلزام و ...) - پرولوگالگوریتم = منطق + کنترلبر اساس : الگوریتم زنجیره ای پس گرد با استفاده از عبارت های هورنبرنامه= مجموعه ای از عبارات head :- literal1, … literaln.criminal(X) :- american(X), weapon(Y), sells(X,Y,Z), hostile(Z).

اسلاید 28: يک برنامه بسيار ساده پرولوگ را در نظر می گيريم. اين برنامه شامل چهار کلاز است که در يک ديتابيس ذخيره شده اند. likes( hossein, food).likes( hossein, icecream).likes( naeem, icecream).likes( naeem, hossein).?- likes( hossein, X) , likes( naeem, X).Query که در انتها آمده می پرسد که آيا حسين چيزی را دوست دارد که نعيم هم آنرا دوست دارد؟ پرولوگ اولين ترم از query را می گيرد likes( hossein, X) و تلاش می کند که آنرا بايک کلاز در ديتابيس unify کند. پرولوگ با توليد جانشينی موفق می شودکه دو جمله likes( hossein, food) و likes( hossein, X) را بايکديگر unify کند. سپس پرولوگ جانشينی به دست آمده را به تمامی ترم های query اعمال می کند. سپس به سراغ دومين ترم می رود، که اکنون likes( naeem, food) شده است. اين جمله با هيچ جمله ديگری در ديتابيس unify نمی شود.بعد از هر شکست، پرولوگ backtrack می کند. يعنی به unification قبلی باز می گردد، که در اين مورد unify کردن likes( hossein, X) با likes( hossein, food) است. اکنون پرولوگ تلاش می کند که اولين ترم query رابا يک کلاز ديگر در ديتابيس unify کند، که likes( hossein, icecream) است. اين دو ترم با جانشينی با يکديگر unify می شوند، که به ترم دوم query يعنی likes( naeem, X) هم اعمال می شود تا likes( naeem, icecream) را ايجاد کند. ترم جديد با سومين کلاز ديتابيس قابل unify شدن است.بعد از تمام شدن کار با تمامی ترم های query، پرولوگ جانشينی های به دست آمده را خروجی می دهد، که در اين جا X=icecream است. يک برنامه بسيار ساده پرولوگ

اسلاید 29: يکی از مسائل کلاسيکی که معمولاً در ابتدای آموزش پرولوگ مطرح می کنند مساله شجره نامه خانوادگی می باشد.برای مثال شجره نامه زير را درنظر بگيريد: اين شجره نامه را به زبان پرولوگ توصيف می نماييم. برای اين کار سه محمول پايه يعنی male، female و parent را اختيار می کنيم و با يک سری درخت را نمايش می دهيم.male(jamshid).male(saeed).male(javad).male(reza).male(hassan).female(zahra).female(mina).female(roya).parent( jamshid, saeed).parent( jamshid, mina).parent( saeed, javad).parent( saeed, zahra).parent( saeed, reza).parent( mina, roya).parent( roya, hassan).پس از ساختن پايگاه دانش يک سری query به سيستم می دهيم.Is hassan the parent of saeed?Query: parent( hassan, saeed).Who is saeeds parent?Query: parent( X, saeed).Who were the children of saeed?Query: parent( saeed, X).

اسلاید 30: لیست ها در پرولوگappend([],Y,Y)الحاق با لیست خالی برابر با خود لیست append([X|L],Y,[X|Z]) :- append(L,Y,Z). پرس و جو: append(A,B,[1,2]) ? پاسخ ها: A=[] B=[1,2] A=[1] B=[2] A=[1,2] B=[]

اسلاید 31: تحلیلl1  ···  lk, m1  ···  mn(l1  ···  li-1  li+1  ···  lk  m1  ···  mj-1  mj+1  ···  mn)θ زمانی که Unify(li, mj) = θ.مثالRich(x)  Unhappy(x) Unhappy(Ken)با θ = {x/Ken} Rich(Ken)

اسلاید 32: هر کس همه حیوانات را دوست داشته باشد، توسط یک نفردوست داشته خواهد شد.x [y Animal(y)  Loves(x,y)]  [y Loves(y,x)]1. حذف یک دوشرطی ها و یک شرطی هاx [y Animal(y)  Loves(x,y)]  [y Loves(y,x)]2. Move  inwards: x p ≡ x p,  x p ≡ x px [y (Animal(y)  Loves(x,y))]  [y Loves(y,x)] x [y Animal(y)  Loves(x,y)]  [y Loves(y,x)] x [y Animal(y)  Loves(x,y)]  [y Loves(y,x)] 3. استاندارد ساز متغیرهاx [y Animal(y)  Loves(x,y)]  [z Loves(z,x)]4. اسکولم سازی x [Animal(F(x))  Loves(x,F(x))]  Loves(G(x),x)5-حذف سورها (عمومی) [Animal(F(x))  Loves(x,F(x))]  Loves(G(x),x)6-توزیع  بر [Animal(F(x))  Loves(G(x),x)]  [Loves(x,F(x))  Loves(G(x),x)] تبدیل به فر م CNF

اسلاید 33: اثبات به روش تحلیل