משתמש:Michael.Aminov/רשת בייסיאנית

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

רשתות בייסיאניות משמשות לתוכנות הדורשות הסקה סטטיסטית, ולתוכנות הלומדות מדוגמאות. סיווג טקסט ("Text classification") (שיוך מסמכים כשייכים לקטגוריה אחת או אחרת כגון: דואר זבל או לגיטימי, ספורט או פוליטיקה, וכו'), אנליזה רפואית ומחקר של ביואינפורמטיקה, הם תחומים בהם נעשה שימוש ברשתות בייסיאניות.

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

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

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

למרות המבנה הנאיבי וככל הנראה ההשערות הפשטניות, רשתות בייסיאניות עבדו די טוב בהרבה מצבים מורכבים במציאות. ב-2004, ניתוח בעיית הסיווג הבייסיאני הראה כי יש נימוקים תיאורטיים מבוססים ליעילות בלתי סבירה לכאורה של המסווגים הבייסיאני הנאיביים[1]. ובכל זאת, השוואה מקיפה עם אלגוריתמי סיווג אחרים ב-2006 הראתה כי הסיווג הבייסיאני הוא בעל ביצועים טובים יותר מאשר מודלים אחרים, כגון עצי שיפרה ("boosted trees") או יערות אקראיים ("random forests")[2].

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


המונח "רשתות בייסיאניות" הוטבע על ידי יהודה פרל בשנת 1985 על מנת להדגיש שלושה היבטים:[3]

  1. לרוב מידע הקלט הינו סובייקטיבי.
  2. הסתמכות על התניית חוק בייס כבסיס לעדכון מידע.
  3. הבחנה בין מצבי חשיבה לוגית סיבתיים לראייתיים, שמדגיש מאמרו של תומאס בייס ("Thomas Bayes") ב-1763 שפורסם לאחר מותו.[4]

בסוף 1980 כתבי העט "חשיבה הסתברותית במערכות חכמות" של יהודה פרל[5] ו"חשיבה הסתברותית במערכות מומחה" של ריצ'רד אי. נפוליטני[6] סיכמו את כלל המאפיינים בנושא של רשתות בייסיאניות, והנושא הוקם כתחום לימודים.

גרסאות לא רשמיות של רשתות כאלה היו בשימוש לראשונה על ידי המשפטן ג'ון הנרי וויגמור ("John Henry Wigmore"), בצורה של תרשימי וויגמור ("Wigmore chart"), על מנת לנתח ראיות משפטיות ב-1913. גרסאות אחרות, שנקראו דיאגרמות נתיב ("path diagrams"), פותחו על ידי הגנטיקאי סיוול רייט ("Sewall Wright")[7] והשתמשו בהם בתחום של מדעי החברה והתנהגות.

מודל ההסתברות (רקע מתמטי)[עריכת קוד מקור | עריכה]

באופן מופשט, מודל ההסתברות לרשת בייסיאנית הוא מודל מותנה

p(C \vert F_1,\dots,F_n)\,

עם משתנה תלוי C בקבוצה עם מספר קטן של תוצאות או קבוצות, מותנה באמצעות מספר משתני תכונה F_1 עד F_n.

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

ע"י שימוש בחוק בייס המודל יראה בצורה הבאה:

p(C \vert F_1,\dots,F_n) = \frac{p(C) \ p(F_1,\dots,F_n\vert C)}{p(F_1,\dots,F_n)} \,

תוך שימוש בטרמינולוגיית הסתברות בייסיאנית ("Bayesian probability"), ניתן לכתוב את המשוואה הנ"ל כך:

\mbox{posterior} = \frac{\mbox{prior} \times \mbox{likelihood}}{\mbox{evidence}} \,

בפועל, יש עניין רק במונה, מכיוון שהמכנה לא תלוי ב-C והערכים של התכונות F_i נתונים, כך שהמכנה הוא למעשה קבוע. המונה הוא שווה ערך למודל ההסתברות המשותפת ("Joint probability")

p(C, F_1, \dots, F_n)\,

אשר ניתן להציגו תוך שימוש בכלל השרשרת ("Chain rule") עבור יישומים חוזרים ונשנים של ההגדרה של ההסתברות מותנית:


\begin{align}
p(C, F_1, \dots, F_n) & = p(C) \ p(F_1,\dots,F_n\vert C) \\
                      & = p(C) \ p(F_1\vert C) \ p(F_2,\dots,F_n\vert C, F_1) \\
                      & = p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3,\dots,F_n\vert C, F_1, F_2) \\
                      & = p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3\vert C, F_1, F_2) \ p(F_4,\dots,F_n\vert C, F_1, F_2, F_3) \\
                      & = p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ \dots p(F_n\vert C, F_1, F_2, F_3,\dots,F_{n-1})
\end{align}

כעט ההשערות הבלתי תלויות המותנות "נאיביות" נכנסות למשחק: נניח שכל תכונה F_i היא בלתי תלויה בכל תכונה אחרת F_j כאשר j\neq i בהינתן משתנה C. משמעות הדבר היא:

 p(F_i \vert C, F_j) = p(F_i \vert C)\,
p(F_i \vert C, F_j,F_k) = p(F_i \vert C)\,
p(F_i \vert C, F_j,F_k,F_l) = p(F_i \vert C)\,

וכך הלאה, כאשר  i\ne j,k,l. לפיכך, המודל המשותף בא לידי ביטוי כך:


\begin{align}
p(C \vert F_1, \dots, F_n) & \varpropto p(C, F_1, \dots, F_n) \\
                           & \varpropto p(C) \ p(F_1\vert C) \ p(F_2\vert C) \ p(F_3\vert C) \ \cdots \\
                           & \varpropto p(C) \prod_{i=1}^n p(F_i \vert C)\,
\end{align}

משמעות דבר היא כי עפ"י ההשערות הבלתי תלויות לעיל, התפלגות המותנית על משתנה הקבוצה C היא:

p(C \vert F_1,\dots,F_n) = \frac{1}{Z}  p(C) \prod_{i=1}^n p(F_i \vert C)

שבו הראיה Z = p(F_1, \dots, F_n) היא מקדם קנה מידה התלוי רק ב-F_1,\dots,F_n, כלומר, קבוע אם הערכים של משתני התכונה ידועים.

בניית מסווג ממודל ההסתברות[עריכת קוד מקור | עריכה]

עד כה בוצעה נגזרת של מודל התכונה הבלתי תלוי, שזה בעצם, מודל הסתברות בייסיאנית "הנאיבי". מסווג בייסיאני נאיבי משלב מודל זה עם כלל החלטה ("Decision rule"). הכלל המשותף הוא לבחור את ההשערה הסבירה ביותר. כלל זה ידוע גם בשם "הערכה מקסימלית בדיעבד" או בקיצור כלל MAP. המסווג הבייסיאני הוא הפונקציה \mathrm{classify} המוגדרת באופן הבא:

\mathrm{classify}(f_1,\dots,f_n) = \underset{c}{\operatorname{argmax}} \ p(C=c) \displaystyle\prod_{i=1}^n p(F_i=f_i\vert C=c)

מודלים למקרים פרטיים[עריכת קוד מקור | עריכה]

כל הפרמטרים במודל (כלומר, מקדמי הקבוצות והתפלגויות של התכונה) ניתנים להערכה/אומדן עם שכיחות יחסית מקבוצת נתוני האימון. אלה הם ההערכות עם סבירות מרבית של ההסתברויות. ניתן לחשב את מקדם הקבוצה בהנחה שהקבוצות שווי הסתברות (כלומר, מקדם = 1 / (מספר הקבוצות)), או על ידי חישוב אומדן להסתברות הקבוצה מקבוצת נתוני האימון (כלומר, מקדם של הקבוצה הנתונה = (מספר האיברים בקבוצה) / (מספר כולל של האיברים)). כדי לאמוד את הפרמטרים להתפלגות של התכונה, יש להניח התפלגות או ליצור מודלים א-פרמטריים לתכונות מקבוצת נתוני האימון‏[8] .

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

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

כאשר מתמודדים עם נתונים רציפים, ההנחה הטיפוסית היא שהערכים הרציפים משויכים לכל קבוצה מתפלגים לפי התפלגות גאוס. לדוגמא, נניח שקבוצת נתוני האימון, מכילה תכונה רציפה x. דבר ראשון מפלחים את הנתונים לקבוצות, לאחר מכן מחשבים את הממוצע והשונות של x בכל קבוצה. \mu_c הוא הממוצע של הערכים בתכונה x השייכים לקבוצה c ו-\sigma^2_c הוא השונות של הערכים בתכונה x השייכים לקבוצה c. הצפיפות של ערך כלשהו בקבוצה P(x=v|c), תחושב על ידי חיבור של v למשוואת התפלגות הנורמלית עם הפרמטרים \mu_c ו- \sigma^2_c. כלומר, המשוואה תיראה כך:


p(x=v|c)=\frac{1}{\sqrt{2\pi\sigma^2_c}}\,e^{ -\frac{(v-\mu_c)^2}{2\sigma^2_c} }

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

מודל מולטינומי[עריכת קוד מקור | עריכה]

במודל המולטינומי, איברים (וקטורי התכונה) מייצגים את השכיחות שבה מקרים מסוימים נוצרו על ידי ההתפלגות המולטינומית (p_1, \dots, p_n) כאשר p_i זה ההסתברות שמקרה i מתרחש (או k במקרה מרובה קבוצות). מודל זה משמש בדרך כלל לסיווג מסמכים ("Document classification"). ערכי התכונה הם שכיחויות האיברים, שנוצרו על ידי ההתפלגות המולטינומית שמפיק מספר מסוים של מילים (דוגמת הנחת שק-מילים – ("Bag-of-words")). הסבירות הנצפית של וקטור התכונה (היסטוגרמה) F מתקבלת ע"י המשוואה:


p(F|C) = \frac{(\sum_i F_i)!}{\prod_i F_i !} \prod_i {p_i}^{F_i}

מסווג מולטינומי הבייסיאני הנאיבי הופך למסווג ליניארי ("Linear classifier") כאשר הוא מבוטא בסולם לוגריתמי:[11]


\begin{align}
\log p(C|F) & = \log \left( p(C) \prod_{i=1}^n p(F_i \vert C) \right) \\
            & = \log p(C) + \sum_{i=1}^n \log p(F_i \vert C)          \\
            & = b + \mathbf{w}_C^\mathsf{T} \mathbf{F}
\end{align}

כאשר b = \log p(C) וגם w_{Ci} = \log p(F_i \vert C).

אם הקבוצה הנתונה וערך התכונה, אף פעם, לא מופיעים יחד בנתוני האימון, השכיחות המבוססת על אומדן הסתברותי תהיה שווה לאפס. תוצאה זו בעייתית מכיוון שהיא תמחק את כל המידע בהסתברויות האחרות כאשר אלה מוכפלות. לכן, לרוב רצוי לשלב תיקון למספר איברים קטן, הנקרא פאסיו-דוקאונט ("Pseudocount"), כך שבכל הערכות ההסתברות, אף הסתברות לא תהיה אפס בדיוק. דרך זו של רגולריזציה ("regularizing") של המסווג הבייסיאני הנאיבי נקראת החלקת תוסף ("Additive smoothing") כאשר פאסיו-דוקאונט שווה אחד, והחלקת אבן-דרך ("Lidstone smoothing") במקרה הכללי.

ג'ייסון רני ועמיתיו דנים בבעיות שיש להנחה המולטינומית בהקשר של סיווג מסמכים ודרכים אפשריות כדי להקל על בעיות אלה, כולל שימוש במשקולות ti-idf במקום שכיחות אותיות ונרמול אורך המסמך, כדי ליצור מסווג בייסיאני נאיבי שיתחרה עם מחולל תמיכה וקטורית ("Support vector machines")[11].

מודל ברנולי[עריכת קוד מקור | עריכה]

במודל ברנולי בעל המשתנים הרבים, התכונות הם משתנים בוליאניים ("Booleans") בלתי תלויים המתארים את נתוני הקלט. מודל זה פופולרי לסיווג מסמכים[9] כאשר נעשה שימוש בתכונות בעלי איברים בינאריים במקום שכיחויות האיברים. אם F_i הוא משתנה בוליאני המבטא את התרחשותו או היעדרו של האיבר ה-i' מאוצר המילים, אז הסבירות של המסמך בהינתן קבוצה C נתונה על ידי המשוואה[9]:


p(F_1, \dots, F_n \vert C) = \prod_{i=1}^n \left[ F_i\, p(w_i \vert C) + (1 - F_i)(1 - p(w_i \vert C)) \right]

שבה p(w_i \vert C) זו ההסתברות של קבוצה C שמניבה/יוצרת את האיברים. המודל פופולרי במיוחד לסיווג טקסטים קצרים. יש לו את היתרון של מידול ("Modelling") האיברים הנעדרים בצורה מפורשת. שימו לב שמסווג בייסיאני נאיבי עם מודל ברנולי לא זהה למסווג בייסיאני נאיבי עם מודל מולטינומי הכולל ספירת שכיחויות הקטומות לאחד.

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

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

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

סיווג מין[עריכת קוד מקור | עריכה]

בעיה - לסווג האם אדם מסוים הוא זכר או נקבה על בסיס התכונות שנמדדו.

התכונות - גובה, משקל, ומידת נעליים

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

להלן סט נתוני האימון:

מס"ד מין גובה (ס"מ) משקלה (ק"ג) מידת נעליים
1 זכר 182.9 81.65 46.5
2 זכר 180.45 86.2 45
3 זכר 170.1 77.1 46.5
4 זכר 180.45 74.4 44
5 נקבה 152.4 45.35 36
6 נקבה 167.65 68.05 38.5
7 נקבה 165.2 58.9 37.5
8 נקבה 175.25 68.05 40

המסווג שנוצר מקבוצת נתוני האימון באמצעות הנחת התפלגות גאוס יהיה (השונות הנתונה זאת שונות המדגם ("sample variance")):

מין ממוצע (גובה) שונות (גובה) ממוצע (משקל) שונות (משקל) ממוצע (מידת נעליים) שונות (מידת נעליים)
זכר 178.46 3.5033e-02 176.25 1.2292e+02 11.25 9.1667e-01
נקבה 165.125 9.7225e-02 132.5 5.5833e+02 7.5 1.6667e+00

נגיד שיש לנו קבוצות שוות הסתברות כך ש- 0.5=(זכר-male)P = (נקבה-female)P. מקדם התפלגות זה עשוי להיות מבוסס על הידע שלנו משכיחות באוכלוסייה הגדולה יותר, או בשכיחות קבוצת נתוני האימון.

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

להלן דגימה שתסווג כזכר או נקבה:

מין גובה (רגל) משקל (ליברה) מידת נעליים (אינץ')
דגימה 6 130 8

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

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

יושלם בהמשך...

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

  1. ^ Zhang, Harry. "The Optimality of Naive Bayes". 
  2. ^ תבנית:Cite conference
  3. ^ Judea Pearl (1985). "Bayesian Networks: A Model of Self-Activated Memory for Evidential Reasoning" (UCLA Technical Report CSD-850017): 329–334. אוחזר ב־2009-05-01. 
  4. ^ Thomas Bayes (1763). "An Essay towards solving a Problem in the Doctrine of Chances". Philosophical Transactions of the Royal Society 53: 370–418. doi:10.1098/rstl.1763.0053. 
  5. ^ Pearl, J.. Probabilistic Reasoning in Intelligent Systems. San Francisco CA: Morgan Kaufmann, 1988. ISBN 1558604790. 
  6. ^ Neapolitan, Richard E. (1989). Probabilistic reasoning in expert systems: theory and algorithms. Wiley. ISBN 978-0-471-61840-9. 
  7. ^ Sewall Wright (1921). "Correlation and Causation" (PDF). Journal of Agricultural Research 20 (7): 557–585. 
  8. ^
    הוספת הערת שוליים נעשית באופן הבא, במקום שבו רוצים שיופיע הקישור להערה:
    {{הערה|יש להזין הערת שוליים כאן}}

    שימו לב: אם הערת השוליים כוללת סימן שווה (=), יש להגדיר את הערת השוליים באופן הבא:

    {{הערה|1=יש להזין הערת שוליים שכוללת סימן שווה כאן}}
    שימו לב לתוספת "1=".
  9. ^ 9.0 9.1 9.2 תבנית:Cite conference
  10. ^ תבנית:Cite conference
  11. ^ 11.0 11.1 תבנית:Cite conference

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

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

Software

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

Allianz AG.png ערך זה הוא קצרמר בנושא סטטיסטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.