عامل های منطقی هوش مصنوعی

عامل های منطقی هوش مصنوعی

اسلاید 1: 1هوش مصنوعيفصل هفتم: عامل‌هاي منطقيتهيه کننده: پورمحققويرايش: حسين عليزادهHA-AI, IUST-CE Dep.

اسلاید 2: 2تعريف مسئله شامل گراف فضاي حالت، تابع آزمون و ...تابع هيوريستيکاستفاده از جستجوي درختي يا گراف براي يافتن راه‌حلعامل حل مسئله چه چيزهايي در اختيار دارد؟دانش در مورد مسئله در قالب مجموعه‌اي از گزاره‌هاي منطقياستفاده از روش‌هاي استنتاج منطقي براي تصميم‌گيري در مورد اقدام بعديعامل مبتني بر دانش چه چيزهايي در اختيار دارد؟HA-AI, IUST-CE Dep.

اسلاید 3: 3پايگاه دانش (Knowledge Base)، يا KB موتور استنتاج (Inference Engine)پايگاه دانش: مجموعه‌اي از حقايق در مورد دنياي عامل است. جمله: هر حقيقت در مورد دنياي عامل توسط يک جمله (Sentence) نمايش داده مي‌شود.جملات: جملات در يک زباني که زبان بازنمايي دانش (Knowledge Representation) ناميده مي‌شود، بيان مي‌شوند.دو بخش مرکزي يک عامل مبتني بر دانش:HA-AI, IUST-CE Dep.

اسلاید 4: 4TELL : افزودن جملات جديد به KBASK : استخراج اطلاعات از KBASKTELLHA-AI, IUST-CE Dep.

اسلاید 5: 5عامل مبتني بر دانش به صورت زير عمل مي‌کند:يک ادراک را به عنوان ورودي دريافت مي‌کند.به پايگاه دانش گفته مي‌شود (TELL) که چه دريافت کرده است.از پايگاه دانش سؤال مي‌شود (ASK) که چه عملي بايد انجام شود.عمل انتخاب شده را در پايگاه دانش ذخيره (TELL) و سپس آنرا اجرا مي‌کند.تشخيص اينکه چه چيزي بايد پس از ASK به KB دنبال شود، مسئوليت مکانيزمي به نام استنتاج (Inference) است.HA-AI, IUST-CE Dep.

اسلاید 6: 6دنياي WUMPUSمعيار کارايي:1000+ انتخاب طلا، 1000- افتادن در گودال يا خورده شدن، 1- هر مرحله، 10- براي استفاده از تيرمحيط:بوي تعفن در مربعهاي همجوار WUMPUSنسيم در مربعهاي همجوار گودالدرخشش در مربع حاوي طلاکشته شدن WUMPUS با شليک در صورت مقابلهتير فقط مستقيم عمل مي‌کندبرداشتن و انداختن طلاحسگرها:بو تعفن، نسيم، تابش، ضربه، جيغ زدنمحرکها:گردش به چپ، گردش به راست، جلو رفتن، برداشتن، انداختن، شليک کردنHA-AI, IUST-CE Dep.

اسلاید 7: 7توصيف جهان WUMPUSقابل مشاهده کامل: خير, فقط ادراک محليقطعي: بله، نتيجه دقيقا مشخص استرويدادي: خير، ترتيبي از فعاليتهاستايستا: بله, WUMPUS و گودالها حرکت ندارندگسسته: بلهتک عامله: بله، WUMPUS در اصل يک خصوصيت طبيعي استHA-AI, IUST-CE Dep.

اسلاید 8: 8عاملهاي منطقيعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = Wعامل نابود خواهد شد زماني که وارد يک مربع شامل سياه چاله و يا وامپوس زنده مي‌شود.هدف عامل يافتن طلا و برگرداندن آن به خانه شروع با سرعت تمام است، بدون آنکه کشته شود.HA-AI, IUST-CE Dep.

اسلاید 9: 9عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = WHA-AI, IUST-CE Dep.

اسلاید 10: 10عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = WHA-AI, IUST-CE Dep.

اسلاید 11: 11عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = WHA-AI, IUST-CE Dep.

اسلاید 12: 12عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = WHA-AI, IUST-CE Dep.

اسلاید 13: 13عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = WHA-AI, IUST-CE Dep.

اسلاید 14: 14عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = WHA-AI, IUST-CE Dep.

اسلاید 15: 15عاملهاي منطقيتوصيف جهان WUMPUSعامل = Aنسيم = Bدرخشش،طلا = Gمربع امن = OKگودال = Pتعفن = Sملاقات شده = VWumpus = WHA-AI, IUST-CE Dep.

اسلاید 16: 16منطق (Logic): يک زبان رسمي براي بازنمايي دانش است به گونه‌اي که بتوان بر روي آن دانش، استدلال کرد.هر زبان بازنمايي دانش شامل دو بخش زير است:نحو (Syntax): ساختار جملات زبان را توصيف مي‌کند.معني (Semantic): تعيين مي‌کند که حقايق موجود در دنيا به چه جملاتي نسبت داده شوند.تفاوت بين حقايق و بازنمايي‌هاي آنها: حقايق قسمتي از دنياي واقعي را تشکيل مي‌دهند، اما بازنمايي‌هاي آنها بايد به صورتي کد شوند که بتواند به طور فيزيکي در يک عامل ذخيره شود.HA-AI, IUST-CE Dep.

اسلاید 17: 17SENTENCESSENTENCESRepresentationWorldFOLLOWSFACTSFACTSSemanticsSemanticsEntailsارتباط بين جملات و حقايق توسط معناي زبان توليد مي‌شوند.HA-AI, IUST-CE Dep.

اسلاید 18: 18استلزاماستلزام منطقي بين جملات اين است که جمله اي بطور منطقي از جمله ديگر پيروي مي‌کندa ╞ b اگر a درست باشد، b نيز درست استجمله a استلزام جمله b استجمله a جمله b را ايجاب مي‌کنددر هر مدلي که a درست است، b نيز درست استدرستي b در درستي a نهفته است مثال: 4<=x+y ╞ x+y>=4 ارتباط استلزام بين يک پايگاه دانش KB و يک جمله a به صورت KB|= a نوشته مي‌شود و به اين معني است که اگر و فقط اگر در هر دنيايي که KB درست است، a نيز درست باشد.HA-AI, IUST-CE Dep.

اسلاید 19: 19مزايا و معايب زبان طبيعي:زبان طبيعي راهي خوب براي سخنگو است تا مخاطب را متوجه منظور خود سازد.مشکل اصلي زبان‌هاي طبيعي ابهام است، مانند عبارت «سگ‌ها و گربه‌هاي کوچک»، روشن نيست که آيا سگ‌ها نيز کوچک هستند يا خير.يک زبان بازنمايي خوب مي‌بايست:مزاياي زبان‌هاي طبيعي و رسمي را با هم داشته باشد.پرمعني و رسا باشد.دقيق و غير مبهم قابل استنتاجHA-AI, IUST-CE Dep.

اسلاید 20: 20ما روي دو نوع منطق تمرکز خواهيم کرد:منطق گزاره‌اي (Propositional Logic) يا منطق بولي (Boolean Logic)منطق مرتبه اول (First Order Logic)HA-AI, IUST-CE Dep.

اسلاید 21: 21منطق گزاره‌اي: منطقي ساده شامل نمادها (علائم) و ترکيب‌هاي آنهاعلائم منطق گزاره‌اي: ثابتهاي منطقي (true, False) علائم گزاره‌اي: Q, P رابط‌هاي پرانتز ()HA-AI, IUST-CE Dep.

اسلاید 22: 22منطق گزاره ايجملات اتميک(عناصر غير قابل تعميم): تشکيل شده از يک نماد گزاره‌ايهر يک از اين نمادها به گزاره اي درست يا نادرست اختصاص داردنمادها از حروف بزرگ مثل P,Q,R استفاده مي‌کنندجملات پيچيده با استفاده از رابط‌هاي منطقي، از جملات ساده تر ساخته مي‌شوند¬ (not): جمله اي مثل ¬W1,3 نقيض W1,3 استليترال: يک جمله اتميک(ليترال مثبت)، يا يک جمله اتميک منفي(ليترال منفي) است^ (and) مثل P1,3 ^ W1,3 ترکيب عطفي نام دارد. هر بخش آن يک عطف ناميده مي‌شودν (or) مثل W2,2 ν (P3,1 ^ W1,3) ترکيب فصلي مربوط به فصل هاي W2,2 و P3,1 ^ W1,3=> (استلزام): W2,2 ¬ => (P3,1 ^ W1,3) استلزام يا شرطي ناميده مي‌شود. مقدمه يا مقدم آن P3,1 ^ W1,3 و نتيجه يا تالي آن W2,2 ¬ است جمله W2,2  W1,3 دو شرطي نام داردHA-AI, IUST-CE Dep.

اسلاید 23: 23هم‌ارزي‌هاي معروف در منطق گزاره ايHA-AI, IUST-CE Dep.

اسلاید 24: 24جدول درستييکي از راه‌هاي ارزيابي درستي يک گزاره استفاده از جدول درستي است.جدول درستي پنج عملگر منطقي معروف به صورت زير است:HA-AI, IUST-CE Dep.

اسلاید 25: 25جمله معتبر (Valid) يا جمله هميشه درست (Tautology):يک جمله معتبر است اگر و فقط اگر در تمام مدل‌ها درست باشد. به عبارت ديگر يک جمله معتبر است اگر به ازاي تمام سطرهاي جدول درستي، آن جمله درست باشد. مثل: Pν¬P (P=>P)جمله ارضاشدني يا صدق‌پذير (satisfiable):يک جمله صدق‌پذير (satisfiable) است اگر و فقط اگر مدلي وجود داشته باشد که آن جمله در آن مدل درست باشد. به عبارت ديگر آن جمله حداقل به ازاي يک سطر از جدول درستي برابر true باشد.جمله‌اي که صدق‌پذير نباشد صدق ناپذير (unsatisfiable) است.مدل:جمله (Aν¬B)^C در دنيايي با A=true, C=true برابر true مي‌شود، پس {A=true, C=true} يک مدل براي جمله (Aν¬B)^C است.HA-AI, IUST-CE Dep.

اسلاید 26: 26منطق گزاره اي در دنياي Wumpusدر [1,1] گودالي وجود ندارد ¬P1,1 در [1,1] نسيمي وجود ندارد ¬B1,1  (¬P1,2 ^ ¬P2,1)در [2,1] نسيمي وجود دارد B2,1  (P3,1 ν P2,2 ν P1,1)ترجمه از زبان طبیعی به منطق گزاره‌ایHA-AI, IUST-CE Dep.

اسلاید 27: 27الگوهاي استدلال در منطق گزاره ايقياس استثنايي (Modus Ponens): در صورت درست بودن سمت چپ قاعده، مي‌توان سمت راست قاعده را استنتاج کرد.مثال: مي‌توان از(WumpusAhead ^ WumpusAlive)و(WumpusAhead ^ WumpusAlive) => ShootShoot را استنتاج کردقوانين استنتاج: الگوهايي استاندارد که زنجيره اي از نتايج را براي رسيدن به هدف ايجاد مي‌کنند.HA-AI, IUST-CE Dep.

اسلاید 28: 28عاملهاي منطقيحذف and: هر عطف را مي‌توان از ترکيب عطفي استنتاج کردمثال: WumpusAlive را مي‌توان از جمله زير استناج کرد(WumpusAhead ^ WumpusAlive)خاصيت يکنواختي (Monotonicity)مجموعه اي از جملات استلزامي که فقط مي‌تواند در صورت اضافه شدن اطلاعات به پايگاه دانش رشد کند. HA-AI, IUST-CE Dep.

اسلاید 29: 29قانون Resolutionقانون resolution واحد، يک عبارت و يک ليترال را گرفته، عبارت ديگري توليد مي‌کندقانون resulotion واحد را مي‌توان به قانون resulotion کامل تعميم داد:HA-AI, IUST-CE Dep.

اسلاید 30: 30فرم نرمال عطفي Conjunctive Normal Form (CNF)فرم نرمال عطفي يا CNF: ترکيبات عطفي از يک يا چند ترکيب فصلي ليترال‌ها. در هر عبارت موجود در جمله k-CNF دقيقا k ليترال وجود دارد. نکته: هر جمله به تنهايي يک ترکيب فصلي است.مثال:¬P1P1 ν ¬ P2 ν P3(P1 ν ¬ P2) Λ (P3 ν P4 ν P5) Λ P6HA-AI, IUST-CE Dep.

اسلاید 31: 31رويه‌اي براي تبديل به فرم نرمال:حذف حذف 2) کاهش دامنه ¬3) توزيع ν روي ΛA (B ν C)(A (B ν C)) Λ ((B ν C)A)(¬A ν B ν C) Λ (¬(B ν C) ν A)(¬A ν B ν C) Λ ((¬B Λ ¬C) ν A)(¬A ν B ν C) Λ ((¬B ν A) Λ (¬C ν A)HA-AI, IUST-CE Dep.

اسلاید 32: 32الگوريتم Resolution (الگوريتم تحليل)براي اينکه نشان دهيمKB|=a , ثابت مي‌کنيم (KB ^ ¬a) ارضانشدني است.ابتدا (KB ^ ¬a) را به CNF تبديل مي‌کنيمسپس قانون رزولوشن به عبارات کوچک حاصل اعمال مي‌شودهر جفتي که شامل ليترال‌هاي مکمل باشد، رزولوشن مي‌شود تا عبارت جديدي ايجاد گردداگر اين عبارت قبلا در مجموعه نباشد، به آن اضافه مي‌شودفرايند تا محقق شدن يکي از شروط زير ادامه مي يابد:هيچ عبارت ديگري وجود نداشته باشد که بتواند اضافه شود. در اين مورد، b استلزام a نيستکاربرد قانون resolution، عبارت تهي را به دست مي‌دهد که در اين مورد، b استلزام a استHA-AI, IUST-CE Dep.

اسلاید 33: 33مثال:الگوريتم رزولوشنفرض کنيد پايگاه دانش دنياي وامپوس را به شکل زير داشته باشيم. مي‌خواهيم ثابت کنيم در خانه [1,2] چاله‌اي وجود ندارد.KB = (B11  (P12 P21))  B11α = P1,2عبارت KB ^ ¬ α را به فرم نرمال عطفي تبديل مي‌کنيم:KB ^ ¬ α = (P21  B11 )  (B11  P12  P21)  (P12  B11)  B11  P12HA-AI, IUST-CE Dep.

اسلاید 34: 34کلاس مفيدي از جملات براي زماني که رويه استنتاجي با زمان چند جمله‌اي وجود دارد که اين کلاس جملات هورن (Horn sentences) ناميده مي‌شود. يک جمله هورن فرمي به صورت زير دارد:که Pi و Q اتم‌هاي خنثي هستند.HA-AI, IUST-CE Dep.

اسلاید 35: 35عاملهاي منطقيزنجير پيشرو و عقبگردعبارات هورن: ترکيب فصلي ليترال‌هايي است که فقط يکي از آنها مثبت استهر عبارت هورن را مي‌توان به صورت يک استلزام نوشت که مقدمه آن ترکيب عطفي ليترال‌هاي مثبت و تالي آن يک ليترال مثبت استاين نوع عبارات هورن که فقط يک ليترال مثبت دارند، عبارات معين ناميده مي‌شوندليترال مثبت را رأس و ليترال‌هاي منفي را بدنه عبارت گويندعبارت معيني که فاقد ليترال‌هاي منفي باشد، گزاره اي بنام حقيقت نام داردعبارات معين اساس برنامه نويسي منطقي را ميسازداستنتاج با عبارات هورن، از طريق الگوريتم هاي زنجير پيشرو و زنجير عقبگرد انجام مي‌گيردHA-AI, IUST-CE Dep.

اسلاید 36: 36عاملهاي منطقيزنجير پيشروالگوريتم زنجير پيشرو تعيين مي‌کند آيا نماد گزاره اي q(تقاضا)، توسط پايگاه دانش عبارات هورن ايجاب مي‌شود يا خيرHA-AI, IUST-CE Dep.

اسلاید 37: 37عاملهاي منطقيزنجير پيشروHA-AI, IUST-CE Dep.

اسلاید 38: 38عاملهاي منطقيزنجير پيشروHA-AI, IUST-CE Dep.

اسلاید 39: 39عاملهاي منطقيزنجير پيشروHA-AI, IUST-CE Dep.

اسلاید 40: 40عاملهاي منطقيزنجير پيشروHA-AI, IUST-CE Dep.

اسلاید 41: 41عاملهاي منطقيزنجير پيشروHA-AI, IUST-CE Dep.

اسلاید 42: 42عاملهاي منطقيزنجير پيشروHA-AI, IUST-CE Dep.

اسلاید 43: 43عاملهاي منطقيزنجير پيشروHA-AI, IUST-CE Dep.

اسلاید 44: 44عاملهاي منطقيزنجير پيشروHA-AI, IUST-CE Dep.

اسلاید 45: 45عاملهاي منطقيالگوريتم عقبگرد کاملHA-AI, IUST-CE Dep.

اسلاید 46: 46عاملهاي منطقيالگوريتم عقبگرد کاملتغييرات عمده: خاتمه زودرس، اکتشاف نماد محض، اکتشاف عبارت واحدHA-AI, IUST-CE Dep.

اسلاید 47: 47عاملهاي منطقيالگوريتم عقبگرد کاملHA-AI, IUST-CE Dep.

اسلاید 48: 48عاملهاي منطقيالگوريتم عقبگرد کاملHA-AI, IUST-CE Dep.

اسلاید 49: 49عاملهاي منطقيالگوريتم عقبگرد کاملHA-AI, IUST-CE Dep.

اسلاید 50: 50عاملهاي منطقيالگوريتم عقبگرد کاملHA-AI, IUST-CE Dep.

اسلاید 51: 51عاملهاي منطقيالگوريتم عقبگرد کاملHA-AI, IUST-CE Dep.

اسلاید 52: 52عاملهاي منطقيالگوريتم عقبگرد کاملHA-AI, IUST-CE Dep.

اسلاید 53: 53عاملهاي منطقيالگوريتم عقبگرد کاملHA-AI, IUST-CE Dep.

اسلاید 54: 54عاملهاي منطقيالگوريتم عقبگرد کاملHA-AI, IUST-CE Dep.

اسلاید 55: 55عاملهاي منطقيالگوريتم عقبگرد کاملHA-AI, IUST-CE Dep.

اسلاید 56: 56منطق گزاره‌اي به ما اجازه مي‌دهد که به تمام نکات مهم درمورد منطق و چگونگي استفاده از آن به منظور ارائه استنتاج که نهايتاً به عمليات تبديل مي‌شود، برسيم. اما منطق گزاره‌اي بسيار ضعيف است.مشکل کند شدن رويه استنتاج:1) مشکل فقط نوشتن اين قوانين نيست بلکه تعداد زياد آنها، باعث مشکل مي‌شود.2) مشکل ديگر، روبرو شدن با تغييرات محيط است. ما جزيي از عامل استدلال کننده را در يک مکان و زمان ويژه نشان داديم، و تمام گزاره‌ها در پايگاه دانش در آن زمان خاص، درست بودند. اما در حالت کلي، دنيا هر لحظه در حال تغيير است.اندازه يک جدول درستي n2 است. که n تعداد سيمبولهاي گزاره‌اي در پايگاه دانش است.HA-AI, IUST-CE Dep.