רשת השפעה
| יש לערוך ערך זה. ייתכן שהערך סובל מבעיות ניסוח, סגנון טעון שיפור או צורך בהגהה, או שיש לעצב אותו, או מפגמים טכניים כגון מיעוט קישורים פנימיים. | |
| ערך מחפש מקורות | |
רשת השפעה (באנגלית: Influence Diagram) הוא כלי לייצוג מודל קבלת החלטות. כלומר, זהו מודל סטטיסטי המאפשר הסקה של הסתברויות מותנות לשם קבלת החלטות המבוססות על נתונים.[1]
רשת השפעה היא הרחבה של רשת בייסיאנית שבה לא רק בעיות הסתברותיות יכולות להיות ממודלות ולהיפתר, אלא גם בעיות של קבלת החלטות (בעקבות קריטריון תוחלת תועלת מרבית) יכולות להיות כמודל ולהיפתר.
הרחבה זו נעשית על ידי הכללה של צומתי החלטה ו- payoffs. רשת השפעה מורכבת מצמתים בגרף אשר כל צומת היא משתנה מקרי בעל טבלת הסתברויות ותועלת.
המודל מאפשר לנו להעריך את התועלת מהחלטות שונות כאשר הסוכן נמצא במצב של חוסר ודאות ו/או שינוי מתמיד. רשתות השפעה, בדומה לרשתות בייסיאניות משמשות לתוכנות הדורשות הסקה סטטיסטית, ולתוכנות הלומדות מדוגמאות, ומשתמשים בהם כחלק מתחומי מחקר כגון ביואינפורמטיקה ואנליזה רפואית.
היתרון של רשתות השפעה הוא שהיא מאפשרת לנו להציג בעיות מורכבות בצורה קומפקטית ופשוטה.
צורת הייצוג של רשתות ההשפעה עריכה
- Chance 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 הוא אירוע שמשפיע ישירות על ערכה של התועלת.
עקרונות חשובים בבניית רשת ההשפעה עריכה
- נתחיל משרטוט ה- Value Nodes, נעבור אחר כך לשרטוט הרכיבים שמשפיעים עליהם ישירות וכך הלאה.
- לצייר את החצים בצורה שתהיה לנו הכי קלה לחשב הסתברויות.
- לשים Informational Arcs כדי לראות את האירוע הנגרם בעקבות ההחלטה.
- לוודא שאם אין קשת בין רכיבים המשמעות היא אי תלות ביניהם.
- לוודא שאין מעגלים ברשת ההשפעה.
כאשר אנחנו רוצים לבנות רשת השפעה אנחנו יכולים לסדר את הרשת ב-2 צורות:
- Observation Order- סידור הצמתים בסדר הצפייה (מייצג את הסדר בחיים האמיתיים), כמו בעץ החלטה. לדוגמה קודם יש סימנים ואחר כך המחלה.
- Assessment Order - ניתן לסדר את הצמתים בדרך שקלה חישובית. לדוגמה קודם המחלה ואחר כך הסימנים.
יותר קשה לחשב את ה- Observation Order אם נסתכל על הדוגמה הנ"ל יותר קשה לחשב את המחלה מתוך הסממנים שלה מאחר שאותם סממנים יכולים לגרום למספר מחלות.
לכן בדרך כלל נבנה את רשת ההשפעה ב Assessment order ועל מנת לפתור את בעיית רשת ההשפעה נהפוך את החצים של הרשת.
הערכת רשת השפעה עריכה
נגדיר מספר מושגים הרלוונטיים בשלב זה:
- Barren Node- צומת שאיננו מצביע לצומת אחר.
- Policy Determination- בוחרים את הצומת עם התועלת הגבוהה ביותר ומורידים אותו.
- Averaging – מורידים את הצומת על ידי לקיחת ממוצע של הערכים משוקלל על ידי ההסתברויות.
האלגוריתם להערכת רשת ההשפעה:
- הורדת צמתים שהם Barren Node.
- כל עוד קיים צומת אחד או יותר שמצביע ל- 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 קשה.
קישורים חיצוניים עריכה
הערות שוליים עריכה
- ^ Influence Diagram - an overview | ScienceDirect Topics, www.sciencedirect.com