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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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})}}\,$

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

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

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

$p(C,F_{1},\dots ,F_{n})\,$

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

${\begin{aligned}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{aligned}}$

כעט ההשערות הבלתי תלויות המותנות "נאיביות" נכנסות למשחק: נניח שכל תכונה $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\neq j,k,l$. לפיכך, המודל המשותף בא לידי ביטוי כך:

${\begin{aligned}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{aligned}}$

משמעות דבר היא כי על פי ההשערות הבלתי תלויות לעיל, התפלגות המותנית על משתנה הקבוצה $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}$, כלומר, קבוע אם הערכים של משתני התכונה ידועים.

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

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

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

מודל גאוסי

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

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

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

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

מודל ברנולי

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

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

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

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

סיווג מסמכים

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

אופן היישום בתוכנת Weka

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

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

• 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.

לקריאה נוספת

• Domingos, Pedro; Pazzani, Michael (1997). "On the optimality of the simple Bayesian classifier under zero-one loss". Machine Learning. 29: 103–137.
• Rish, Irina (2001). An empirical study of the naive Bayes classifier (PDF). IJCAI 2001 Workshop on Empirical Methods in Artificial Intelligence.
• Hand, D. J.; Yu, K. (2001). "Idiot's Bayes — not so stupid after all?". International Statistical Review. 69 (3): 385–399. ISSN 0306-7734.
• Webb, G. I.; Boughton, J.; Wang, Z. (2005). "Not So Naive Bayes: Aggregating One-Dependence Estimators". Machine Learning. Springer. 58 (1): 5–24.
• Mozina, M.; Demsar, J.; Kattan, M.; Zupan, B. (2004). Nomograms for Visualization of Naive Bayesian Classifier (PDF). Proc. PKDD-2004. pp. 337–348.
• Maron, M. E. (1961). "Automatic Indexing: An Experimental Inquiry". JACM. 8 (3): 404–417.
• Minsky, M. (1961). Steps toward Artificial Intelligence. Proc. IRE. Vol. 49. pp. 8–30.