רשת השפעה

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

רשת השפעה היא הרחבה של רשת בייסיאנית שבה לא רק בעיות הסתברותיות יכולות להיות ממודלות ולהיפתר, אלא גם בעיות של קבלת החלטות (בעקבות קריטריון תוחלת תועלת מרבית) יכולות להיות כמודל ולהיפתר. הרחבה זו נעשית על ידי הכללה של צמתי החלטה ו- 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.

ראו גם

• רשת בייסיאנית

קישורים חיצוניים

• רשת השפעה

ערך זה הוא יתום, כלומר אין ערכים במכלול שמקשרים אליו. אתם מוזמנים לתרום למכלול ולקשר אליו מכמה מהערכים שמכילים את המונח "רשת השפעה".