בבינה מלאכותית, שרשור קדימה ואחורה הוא אחד הנושאים החשובים, אבל לפני שמבינים שרשור קדימה ואחורה, בואו נבין קודם כל מהיכן הגיעו שני המונחים הללו.
עבודת מחשב
מנוע היקש:
מנוע ההסקה הוא המרכיב של המערכת התבונית בבינה מלאכותית, המיישמת כללים לוגיים על בסיס הידע כדי להסיק מידע חדש מעובדות ידועות. מנוע ההסקה הראשון היה חלק ממערכת המומחים. מנוע הסקת מסקנות ממשיך בדרך כלל בשני מצבים, שהם:
סעיף צופר וסעיף סופי:
פסקת הורן וסעיף מובהק הן צורות של משפטים, המאפשרות לבסיס ידע להשתמש באלגוריתם הסקה מוגבל ויעיל יותר. אלגוריתמים של הסקה לוגית משתמשים בגישות שרשור קדימה ואחורה, הדורשות KB בצורה של סעיף מובהק מסדר ראשון .
סעיף מוגדר: סעיף שהוא ניתוק מילולי עם בדיוק מילולית חיובית אחת ידוע כסעיף מובהק או כסעיף קרן קפדני.
סעיף צופר: סעיף שהוא ניתוק מילולי עם לכל היותר מילולית חיובית אחת ידוע כסעיף קרן. מכאן שכל הסעיפים המוגדרים הם סעיפי קרן.
דוגמה: (¬ p V ¬ q V k) . יש לו רק ק מילולי חיובי אחד.
זה שווה ערך ל p ∧ q → k.א. שרשור קדימה
שרשור קדימה ידוע גם בתור ניכוי קדימה או שיטת חשיבה קדימה בעת שימוש במנוע הסקה. שרשרת קדימה היא צורה של חשיבה שמתחילה במשפטים אטומיים בבסיס הידע ומחילה כללי היסק (Modus Ponens) בכיוון קדימה כדי לחלץ יותר נתונים עד להשגת יעד.
אלגוריתם ה-Forward-chaining מתחיל מעובדות ידועות, מפעיל את כל הכללים שהנחות היסוד שלהם מתקיימות, ומוסיף את המסקנה שלהם לעובדות הידועות. תהליך זה חוזר על עצמו עד לפתרון הבעיה.
תכונות של שרשור קדימה:
- זוהי גישה של מטה למעלה, שכן היא נעה מלמטה למעלה.
- זהו תהליך של קבלת מסקנה המבוססת על עובדות או נתונים ידועים, על ידי התחלה מהמצב ההתחלתי והגעה למצב המטרה.
- גישת שרשור קדימה נקראת גם מונעת נתונים כאשר אנו מגיעים ליעד באמצעות נתונים זמינים.
- גישת שרשור קדימה משמשת בדרך כלל במערכת המומחים, כגון CLIPS, מערכות עסקיות וכללי ייצור.
שקול את הדוגמה המפורסמת הבאה שבה נשתמש בשתי הגישות:
דוגמא:
'לפי החוק, זה פשע עבור אמריקאי למכור נשק למדינות עוינות. למדינה א', אויבת אמריקה, יש כמה טילים, וכל הטילים נמכרו לה על ידי רוברט, שהוא אזרח אמריקאי״.
תוכיח את זה 'רוברט הוא פושע.'
כדי לפתור את הבעיה שלעיל, ראשית, נמיר את כל העובדות לעיל לסעיפים מוגדרים מסדר ראשון, ולאחר מכן נשתמש באלגוריתם של שרשור קדימה כדי להגיע למטרה.
המרת עובדות ל-FOL:
- זה פשע עבור אמריקאי למכור נשק למדינות עוינות. (נניח ש-p, q ו-r הם משתנים)
אמריקאי (p) ∧ נשק(q) ∧ מוכר (p, q, r) ∧ עוין(r) → פושע(p) ...(1) - למדינה A יש כמה טילים. ?p Owns(A, p) ∧ טיל(p) . ניתן לכתוב אותו בשני סעיפים מוגדרים על ידי שימוש באינסטציה קיומית, תוך הצגת Constant T1 חדש.
בעלים (A, T1) ......(2)
טיל(T1) .......(3) - כל הטילים נמכרו למדינה A על ידי רוברט.
?p טילים (p) ∧ בעלים (A, p) → מוכר (רוברט, p, A) ......(4) - טילים הם כלי נשק.
טיל (p) → כלי נשק (p) .......(5) - אויב אמריקה ידוע בתור עוין.
Enemy(p, America) →Hosile(p) ........(6) - מדינה A היא אויבת אמריקה.
אויב (A, אמריקה) .........(7) - רוברט הוא אמריקאי
אמריקאי (רוברט). ..........(8)
הוכחה לשרשור קדימה:
שלב 1:
בשלב הראשון נתחיל עם העובדות הידועות ונבחר את המשפטים שאין להם השלכות, כגון: אמריקאי (רוברט), אויב (A, אמריקה), בעלים (A, T1) וטיל (T1) . כל העובדות הללו יוצגו להלן.
שלב 2:
בשלב השני, נראה את העובדות המסיקות מעובדות זמינות ועם הנחות מרוצים.
כלל-(1) אינו עומד בהנחות, ולכן הוא לא יתווסף באיטרציה הראשונה.
כלל-(2) ו-(3) כבר נוספו.
כלל-(4) הסתפק בהחלפה {p/T1}, so Sells (רוברט, T1, A) נוסף, המסיק מהצירוף של כלל (2) ו-(3).
כלל-(6) מסתפק בהחלפה(p/A), ולכן מתווסף עוין(א) ואשר מסיק מכלל-(7).
שלב 3:
בשלב 3, כפי שאנו יכולים לבדוק כלל-(1) מרוצה מההחלפה {p/Robert, q/T1, r/A}, כדי שנוכל להוסיף Criminal(Robert) מה שמסיק את כל העובדות הקיימות. ומכאן הגענו להצהרת המטרה שלנו.
מכאן שמוכח שרוברט הוא פושע תוך שימוש בגישת שרשור קדימה.
ב. שרשור לאחור:
שרשור לאחור ידוע גם בתור דדוקציה לאחור או שיטת חשיבה לאחור בעת שימוש במנוע הסקה. אלגוריתם שרשור לאחור הוא סוג של חשיבה, שמתחילה במטרה ופועלת אחורה, משרשרת דרך כללים כדי למצוא עובדות ידועות התומכות במטרה.
תכונות של שרשור לאחור:
- זה ידוע בתור גישה מלמעלה למטה.
- שרשור לאחור מבוסס על כלל מסקנות מודוס ponens.
- בשרשור לאחור, המטרה מחולקת למטרות משנה או למטרות משנה כדי להוכיח שהעובדות נכונות.
- זה נקרא גישה מונעת מטרה, שכן רשימת יעדים מחליטה אילו כללים נבחרים ומשתמשים בהם.
- אלגוריתם שרשור לאחור משמש בתורת המשחקים, כלי הוכחת משפטים אוטומטיים, מנועי הסקה, עוזרי הוכחה ויישומי AI שונים.
- שיטת השרשור לאחור השתמשה בעיקר ב- a חיפוש עומק ראשון אסטרטגיה להוכחה.
דוגמא:
בשרשראות לאחור, נשתמש באותה דוגמה לעיל, ונכתוב מחדש את כל הכללים.
בעלים (A, T1) ........(2)
הוכחה שרשרת לאחור:
ב-Backward chaining, נתחיל עם פרידיקט המטרה שלנו, כלומר פושע (רוברט) , ולאחר מכן להסיק כללים נוספים.
שלב 1:
בשלב הראשון, ניקח את עובדת המטרה. ומעובדת המטרה, נסיק עובדות אחרות, ולבסוף, נוכיח שהעובדות הללו נכונות. אז עובדת המטרה שלנו היא 'רוברט הוא פושע', אז הבא הוא הפרדיקט של זה.
שלב 2:
בשלב השני, נסיק עובדות אחרות מעובדת מטרה המקיימת את הכללים. אז כפי שאנו יכולים לראות בכלל-1, פרידיקט המטרה פושע (רוברט) קיים עם חילוף {Robert/P}. אז נוסיף את כל העובדות בחיבור מתחת לרמה הראשונה ונחליף את p ברוברט.
כאן אנחנו יכולים לראות שאמריקאי (רוברט) הוא עובדה, אז זה מוכח כאן.
שלב 3: • בשלב 3, נחלץ עובדה נוספת של טיל(q) המסיק מ-Weapon(q), שכן הוא עומד בחוק-(5). נשק (q) נכון גם עם החלפה של T1 קבוע ב-q.
שלב 4:
בשלב 4, אנו יכולים להסיק עובדות טיל (T1) ו- Owns (A, T1) טופס Sells (Robert, T1, r) אשר מספק את כלל- 4 , עם החלפת A במקום r. אז שתי ההצהרות הללו מוכחות כאן.
שלב-5:
בשלב 5, אנו יכולים להסיק את העובדה אויב (A, אמריקה) מ עוין(א) שמקיים את כלל 6. ומכאן שכל ההצהרות מוכחות כנכונות באמצעות שרשור לאחור.
