מחשבון אנטרופיה - חישוב אנטרופיית שאנון באופן מקוון בחינם

מהו מחשבון אנטרופיה?

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

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

נוסחת אנטרופיית שנון

עבור מערך נתונים בעל ערכים ייחודיים x₁ עד xₙ, שכל אחד מהם מופיע בהסתברות p(xᵢ), אנטרופיית שנון H היא:

$H(X) = -\sum_{i=1}^{n} p(x_i) \log_2 p(x_i)$

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

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

מדוע התוצאה אינה יכולה להיות שלילית

כל הסתברות p(xᵢ) נמצאת בין 0 ל־1, ולכן הלוגריתם שלה הוא אפס או שלילי. הכפלת הסתברות בלוגריתם שלילי או אפס נותנת מספר שלילי או אפס. חיבור המספרים האלה והיפוך הסימן תמיד נותנים תוצאה של אפס או יותר.

האנטרופיה המרבית האפשרית

עבור מערך נתונים עם n ערכים ייחודיים, האנטרופיה מרבית כאשר כל ערך מופיע באותה תדירות. הערך המרבי הזה שווה ל־log₂(n) ביטים. מערך נתונים עם 4 ערכים ייחודיים בעלי שכיחות שווה יכול להגיע לכל היותר ל־2 ביטים של אנטרופיה, משום ש־log₂(4) = 2. כל התפלגות לא אחידה של אותם 4 ערכים נותנת אנטרופיה נמוכה יותר.

כיצד לחשב אנטרופיה: שלב אחר שלב

1. מנו את הערכים הייחודיים במערך הנתונים וספרו כמה פעמים כל אחד מהם מופיע.
2. חלקו כל ספירה במספר הערכים הכולל כדי לקבל את ההסתברות של כל ערך ייחודי.
3. חשבו את הלוגריתם בבסיס 2 של כל הסתברות, ולאחר מכן הכפילו אותו באותה הסתברות.
4. חברו את כל המכפלות האלה, ולאחר מכן הכפילו את הסכום ב־−1.

מחשבון זה מבצע אוטומטית את אותם ארבעה שלבים. הקלידו מספרים בתיבת הקלט, כשהם מופרדים ברווחים או בפסיקים, בחרו את התבנית המתאימה, והאנטרופיה, טבלת ההסתברויות ותרשים העמודות יופיעו מיד. בטבלה שמתחת לתוצאה מוצגים הערך, הספירה, ההסתברות ו־p(x) × log₂(p(x)) עבור כל מספר ייחודי, כך שהחישוב גלוי ולא רק התשובה הסופית.

כללי קלט

• מתקבלים ערכים מספריים בלבד: מספרים שלמים, מספרים עשרוניים ומספרים שליליים — כולם נתמכים.
• ערכים מופרדים ברווחים (לדוגמה: 1 2 3 4) או בפסיקים (לדוגמה: 1,2,3,4), בהתאם לתבנית שנבחרה.
• מערך נתונים יכול להכיל עד 100,000 ערכים. הזנה של יותר מכך מציגה הודעת שגיאה המבקשת מערך נתונים קטן יותר.
• סימון מדעי מתקבל, ולכן 1e3 נקרא כ־1000.
• טקסט, סמלים או ערכים ריקים בין מפרידים נדחים ומוצגת שגיאה, במקום להתעלם מהם בשקט.
• גם מספר גדול מדי לאחסון במחשב, כגון 1e400, נדחה. הערך הגדול ביותר שהמחשבון יכול להכיל הוא בערך 1.8 x 10^308.

דוגמה פתורה

נבחן את מערך הנתונים 1 2 3 1 2 1, המכיל שישה מספרים.

ראשית, ספרו כל ערך ייחודי:

לאחר מכן, הפעילו את הנוסחה על כל שורה וחברו את התוצאות:

$H = -(0.5 \log_2 0.5 + 0.3333 \log_2 0.3333 + 0.1667 \log_2 0.1667)$ $H = -(0.5 \times -1 + 0.3333 \times -1.585 + 0.1667 \times -2.585)$ $H \approx 1.4591 \text{ ביטים}$

במערך הנתונים יש 3 ערכים ייחודיים, ולכן האנטרופיה המרבית האפשרית היא log₂(3) ≈ 1.585 ביטים. התוצאה בפועל, 1.4591 ביטים, נמוכה מהערך המרבי משום שהערך 1 מופיע בתדירות גבוהה יותר מהאחרים, ולכן מערך הנתונים מעט פחות אקראי מחלוקה שווה לחלוטין.

מערך נתונים ללא אי־ודאות

במערך הנתונים 5 5 5 5 5 יש ערך ייחודי אחד בלבד, ולכן ההסתברות שלו היא 1. מכיוון ש־log₂(1) = 0, כל איבר בסכום הוא אפס, והאנטרופיה היא בדיוק 0 ביטים. אין דבר לא ודאי במערך נתונים שבו כל הערכים זהים.

כיצד לקרוא את התוצאה

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

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

שימושים באנטרופיית שנון

• למידת מכונה: אלגוריתמים של עצי החלטה משתמשים באנטרופיה כדי להחליט איזו תכונה מפצלת בצורה הטובה ביותר מערך נתונים לקבוצות צפויות.
• דחיסת נתונים: האנטרופיה קובעת את הגבול התאורטי למידת הדחיסה של קובץ בלי לאבד מידע.
• קריפטוגרפיה: האנטרופיה מודדת עד כמה סיסמה או מפתח הצפנה אינם צפויים.
• גנטיקה: אנטרופיה יכולה להבליט אזורים חריגים או בעלי שונות גבוהה ברצף DNA.
• ניתוח טקסט: התייחסות לאותיות או למילים כאל "ערכים" מאפשרת לאנטרופיה למדוד עד כמה קטע טקסט צפוי.

שאלות נפוצות

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

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

האם אנטרופיה יכולה להיות שלילית? לא. הערך הנמוך ביותר האפשרי הוא 0 ביטים, והוא מתקבל כאשר כל הערכים במערך הנתונים זהים.

מהי האנטרופיה המרבית של מערך נתונים? הערך המרבי הוא log₂(n) ביטים, כאשר n הוא מספר הערכים הייחודיים, והוא מתקבל רק כאשר כל ערך ייחודי מופיע באותה תדירות.

האם קיימת הגבלה על גודל מערך הנתונים? כן. מחשבון זה מקבל עד 100,000 ערכים במערך נתונים יחיד. קלטים גדולים יותר מחזירים שגיאה.

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

מקורות

1. שאנון, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27(3), 379–423.
2. Cover, T. M., & Thomas, J. A. (2006). Elements of Information Theory (מהדורה 2). Wiley-Interscience.
3. MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press.