רשת השפעה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Gnome-edit-clear.svg ערך זה זקוק לעריכה: ייתכן שהערך סובל מפגמים טכניים כגון מיעוט קישורים פנימיים, סגנון טעון שיפור או צורך בהגהה, או שיש לעצב אותו.
אתם מוזמנים לסייע ולתקן את הבעיות, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה.

רשת השפעהאנגלית: Influence Diagram) הוא כלי לייצוג מודל קבלת החלטות, כלומר זהו מודל המייצג באופן גרפי ומתמטי מצב החלטה. זה בעצם מודל סטטיסטי המאפשר הסקה של הסתברויות מותנות.

InfluenceDiagram.pdf

רשת השפעה היא הרחבה של רשת בייסיאנית שבה לא רק בעיות הסתברותיות יכולות להיות ממודלות ולהיפתר, אלא גם בעיות של קבלת החלטות (בעקבות קריטריון תוחלת תועלת מרבית) יכולות להיות כמודל ולהיפתר. הרחבה זו נעשית על ידי הכללה של צמתי החלטה ו- payoffs. הרשת השפעה מורכבת מצמתים בגרף אשר כל צומת הוא משתנה מקרי בעל טבלת הסתברויות ותועלת. המודל מאפשר לנו להעריך את התועלת מהחלטות שונות כאשר הסוכן נמצא במצב של חוסר וודאות ו/או שינוי מתמיד.

רשתות השפעה, בדומה לרשתות בייסיאניות משמשות לתוכנות הדורשות הסקה סטטיסטית, ולתוכנות הלומדות מדוגמאות, ומשתמשים בהם כחלק מתחומי מחקר כגון ביואינפורמטיקה ואנליזה רפואית.

היתרון של רשתות השפעה הוא שהוא מאפשר לנו להציג בעיות מורכבות בצורה קומפקטית ופשוטה.

צורת הייצוג של רשתות ההשפעה:[עריכת קוד מקור | עריכה]

  • Change Node - מייצג אירוע הסתברותי (אי ודאות).
  • Deterministic Node- צומת שערכו הוא פונקציה דטרמיניסטית של הוריו. כלומר שערך ההורים ידוע גם ערך ה- Node ידוע.
  • Decision Node - מייצג החלטות הנמצאות בשליטת מקבל ההחלטה.
  • Value Node - מייצג ערכים (Payoffs).

הקשרים הקיימים ברשתות השפעה[עריכת קוד מקור | עריכה]

Information Link- לפני קבלת ההחלטה, המצב ב- Chance Node ידוע למקבל ההחלטות. הקשת המחברת בין הרכיבים נקראת Informational Arc.

Influence Link- מראה שהחלטה תשפיע על המצב ב- Chance Node.

Decision Link- מראה על סדר בקבלת ההחלטות. הקשת המחברת בין הרכיבים נקראת Not forgetting Arcs

Dependence Link- התרחשות ב- Chance Node אחד משפיעה על ההסתברות ב- Chance Node אחר.

אם אין קשת בין שני רכיבים אזי הם בלתי תלויים, לא משפיעים זה על זה. ליד כל Chance Node תהיה לנו טבלה. הטבלה תכיל את כל השילובים האפשריים של כל מי שמצביע על ה- Chance Node. לכל שילוב אפשרי נגדיר את ההסתברות. ליד כל Value Node תהיה לנו טבלה דומה אך במקום הסתברויות היא תכיל את התועלות הצפויות. כלומר נחזיק את התועלות לכל ה-Outcomes האפשריים. כל רכיב אשר מצביע ישירות על Value Node הוא אירוע שמשפיע ישירות על ערכה של התועלת.

עקרונות חשובים בבניית רשת ההשפעה[עריכת קוד מקור | עריכה]

  1. מתחילים מה-Value Nodes והולכים אחורה ל- Decision Nodes – נתחיל משרטוט ה- Value Nodes, נעבור אחר כך לשרטוט הרכיבים שמשפיעים עליהם ישירות וכך הלאה.
  2. לצייר את החצים בצורה שתהיה לנו הכי קלה לחשב הסתברויות.
  3. לשים Informational Arcs כדי לראות את האירוע הנגרם בעקבות ההחלטה.
  4. לוודא שאם אין קשת בין רכיבים המשמעות היא אי תלות ביניהם.
  5. לוודא שאין מעגלים ברשת ההשפעה.

כאשר אנחנו רוצים לבנות רשת השפעה אנחנו יכולים לסדר את הרשת ב-2 צורות :

  • Observation Order- סידור הצמתים בסדר הצפייה (מייצג את הסדר בחיים האמיתיים), כמו בעץ החלטה. לדוגמה קודם יש סימנים ואחר כך המחלה.
  • Assessment Order - ניתן לסדר את הצמתים בדרך שקלה חישובית. לדוגמה קודם המחלה ואחר כך הסימנים.

יותר קשה לחשב את ה- Observation Order אם נסתכל על הדוגמה הנ"ל יותר קשה לחשב את המחלה מתוך הסממנים שלה מאחר שאותם סממנים יכולים לגרום למספר מחלות. לכן בדרך כלל נבנה את רשת ההשפעה ב Assessment order ועל מנת לפתור את בעיית רשת ההשפעה נהפוך את החצים של הרשת.

הערכת רשת השפעה[עריכת קוד מקור | עריכה]

נגדיר מספר מושגים הרלוונטיים בשלב זה :

  • Barren Node- צומת שאיננו מצביע לצומת אחר.
  • Policy Determination- בוחרים את הצומת עם התועלת הגבוהה ביותר ומורידים אותו.
  • Averaging – מורידים את הצומת על ידי לקיחת משקל ממוצע של הערכים.

האלגוריתם להערכת רשת ההשפעה :

  1. הורדת צמתים שהם Barren Node.
  2. כל עוד קיים צומת אחד או יותר שמצביע ל- Value Node .

a. אם קיים Decision Node D אשר מצביע ל Value Node, וכל שאר הצמתים שמצביעים ל Value Node מצביעים גם ל- D. נוריד את D ע"פ Policy Determination ואם נוצרו בעקבות כך Barren Node נוריד גם אותם. חזור לשלב 2

b.אם קיים Chance Node שמצביע רק ל- Value Node נוריד אותו על ידי Averaging . חזור לשלב 2.

c.מצא Chance Node C אשר מצביע ל- Value Node ולא ל- Decision Node. הפוך את החצים מ- C ל- Chance Node אחר ללא יצירת מעגל. כעת C מצביע רק על ה- Value Node. חזור לשלב 2.

יתרונות רשת השפעה:[עריכת קוד מקור | עריכה]

  • קל ואינטואיטיבי להבנה- כלי מידול נוח מבחינה ויזואלית.
  • הצגה בצורה קומפקטית (חסכונית במצבים)
  • מציג לי תלויות בין גורמים בצורה מפורשת
  • ייצוג הצמתים בדרך אשר קלה יחסית לחישוב
  • תומך באופן מפורש בחישוב ערך המידע- VI

חסרונות רשת השפעה[עריכת קוד מקור | עריכה]

  • סדר ההחלטה לא תמיד מבוטא- לשם כך משתמשים בחיצי "Not forgetting Arcs" אשר אין להם תפקיד מיוחד, רק להראות סדר.
  • הקשר בין ההחלטות לא תמיד ברור והוא נחבא בטבלאות ההסתברות המצורפות לצמתים.
  • לא רואים א-סימטריה כמו בעצי החלטה.
  • בדרך כלל רמת הסיבוכיות הכללית של החישובים היא NP-Hard.

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

http://www.lumina.com/technology/influence-diagrams/