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

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

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

תיאור כללי והיסטוריה של האלגוריתם

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

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

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

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

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

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

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

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

מודל ההסתברות (רקע מתמטי)

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

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

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

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

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

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

תוך שימוש בטרמינולוגיית הסתברות בייסיאנית ניתן לכתוב את המשוואה הנ"ל כך:

$\text{posterior}=\frac{\text{prior}\times \text{likelihood}}{\text{evidence}}$

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

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

אשר ניתן להציגו תוך שימוש בכלל השרשרת תוך יישומים חוזרים ונשנים של ההגדרה של ההסתברות מותנית:

$\begin{array}{cc}p(C,F_1,\dots ,F_n)& =p(C)p(F_1,\dots ,F_n|C)\\ & =p(C)p(F_1|C)p(F_2,\dots ,F_n|C,F_1)\\ & =p(C)p(F_1|C)p(F_2|C,F_1)p(F_3,\dots ,F_n|C,F_1,F_2)\\ & =p(C)p(F_1|C)p(F_2|C,F_1)p(F_3|C,F_1,F_2)p(F_4,\dots ,F_n|C,F_1,F_2,F_3)\\ & =p(C)p(F_1|C)p(F_2|C,F_1)\dots p(F_n|C,F_1,F_2,F_3,\dots ,F_{n-1})\end{array}$

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

$p(F_i|C,F_j)=p(F_i|C)$

$p(F_i|C,F_j,F_k)=p(F_i|C)$

$p(F_i|C,F_j,F_k,F_l)=p(F_i|C)$

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

$\begin{array}{cc}p(C|F_1,\dots ,F_n)& \propto p(C,F_1,\dots ,F_n)\\ & \propto p(C)p(F_1|C)p(F_2|C)p(F_3|C)\cdots \\ & \propto p(C)\prod _{i=1}^{n}p(F_i|C)\end{array}$

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

$p(C|F_1,\dots ,F_n)=\frac{1}{Z}p(C)\prod _{i=1}^{n}p(F_i|C)$

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

בניית מסווג ממודל ההסתברות

עד כה בוצעה נגזרת של מודל התכונה הבלתי תלוי, שזה בעצם, מודל הסתברות בייסיאנית "הנאיבי". מסווג בייסיאני נאיבי משלב מודל זה עם כלל החלטה תבנית:אנ. הכלל המשותף הוא לבחור את ההשערה הסבירה ביותר. כלל זה ידוע גם בשם "הערכה מקסימלית בדיעבד" או בקיצור כלל MAP תבנית:אנ. המסווג הבייסיאני הוא הפונקציה $\mathrm{c}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{f}\mathrm{y}$ המוגדרת באופן הבא:

$\mathrm{c}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{f}\mathrm{y}(f_1,\dots ,f_n)=\underset{c}{\mathrm{argmax}}p(C=c)\prod _{i=1}^{n}p(F_i=f_i|C=c)$

מודלים למקרים פרטיים

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

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

מודל גאוסי

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

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

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

מודל מולטינומי

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

$p(F|C)=\frac{(\sum _i{F}_i)!}{\prod _i{F}_i!}\prod _i{p_i}^{F_i}$

מסווג מולטינומי הבייסיאני הנאיבי הופך למסווג ליניארי תבנית:אנ כאשר הוא מבוטא בסולם לוגריתמי:תבנית:הערה

$\begin{array}{cc}\log p(C|F)& =\log (p(C)\prod _{i=1}^{n}p(F_i|C))\\ & =\log p(C)+\sum _{i=1}^n\log p(F_i|C)\\ & =b+{𝐰}_C^{𝖳}𝐅\end{array}$

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

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

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

מודל ברנולי

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

$p(F_1,\dots ,F_n|C)=\prod _{i=1}^n[F_{i}p(w_i|C)+(1-F_i)(1-p(w_i|C))]$

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

יתרונות וחסרונות

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

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

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

לקריאה נוספת

• תבנית:Cite journal
• תבנית:Cite conference
• תבנית:Cite journal
• תבנית:Cite journal
• תבנית:Cite conference
• תבנית:Cite journal
• תבנית:Cite conference

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

• Book Chapter: Naive Bayes text classification, Introduction to Information Retrieval
• Naive Bayes for Text Classification with Unbalanced Classes
• Benchmark results of Naive Bayes implementations
• Hierarchical Naive Bayes Classifiers for uncertain data (an extension of the Naive Bayes classifier).

Software

• Naive Bayes classifiers are available in many general-purpose machine learning and NLP packages, including Apache Mahout, Mallet, NLTK, Orange, scikit-learn and Weka.
• IMSL Numerical Libraries Collections of math and statistical algorithms available in C/C++, Fortran, Java and C#/.NET. Data mining routines in the IMSL Libraries include a Naive Bayes classifier.
• Winnow content recommendation Open source Naive Bayes text classifier works with very small training and unbalanced training sets. High performance, C, any Unix.
• An interactive Microsoft Excel spreadsheet Naive Bayes implementation using VBA (requires enabled macros) with viewable source code.
• jBNC - Bayesian Network Classifier Toolbox
• Statistical Pattern Recognition Toolbox for Matlab.
• ifile - the first freely available (Naive) Bayesian mail/spam filter
• NClassifier - NClassifier is a.NET library that supports text classification and text summarization. It is a port of Classifier4J.
• Classifier4J - Classifier4J is a Java library designed to do text classification. It comes with an implementation of a Bayesian classifier.