אי-שוויון גיבס

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

אי-שוויון גיבס

תהיינה $P = {p_{1}, \dots, p_{n}}$ ו $Q = {q_{1}, \dots, q_{n}}$ התפלגויות הסתברות בדידות. אזי

- \sum_{i = 1}^{n} p_{i} \log p_{i} \leq - \sum_{i = 1}^{n} p_{i} \log q_{i}

השוויון בין האגפים מתקיים אם ורק אם $p_{i} = q_{i}$ לכל $i = 1, \dots n$ .^[1] במילים אחרות, האנטרופיה של התפלגות $P$ קטנה או שווה לאנטרופיה הצולבת(אנ') שלו עם כל התפלגות אחרת $Q$ .

ההפרש בין שני הגדלים הוא דיברגנץ קולבק-לייבלר (אנטרופיה היחסית), כך שניתן לכתוב את אי השוויון גם כ^[2]

D_{K L} (P ‖ Q) \equiv \sum_{i = 1}^{n} p_{i} \log \frac{p_{i}}{q_{i}} \geq 0 .

הוכחה

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

נסמן ב $I$ את קבוצת כל ערכי $i$ שעבורם p_i אינו אפס. מכיוון ש $\ln x \leq x - 1$ עבור כל x > 0, עם שוויון אם ורק אם x=1, מקבלים

- \sum_{i \in I} p_{i} \ln \frac{q_{i}}{p_{i}} \geq - \sum_{i \in I} p_{i} (\frac{q_{i}}{p_{i}} - 1) < = - \sum_{i \in I} q_{i} + \sum_{i \in I} p_{i} = - \sum_{i \in I} q_{i} + 1 \geq 0

אי השוויון האחרון נובעת מכך ש p_i ו- q_i הם ערכים של התפלגות הסתברות, כך שסכום כל הערכים p_i שאינם אפס הוא 1. עם זאת, ייתכן שחלק מה q_i שאינם אפס הושמטו מאחר שבחירת האינדקסים $I$ נקבעת על סמך הדרישה ש p_i אינו אפס. לכן, סכום ה- q_i עשוי להיות קטן מ-1.

עד כה, בהינתן קבוצת האינדקסים $I$ , יש לנו:

- \sum_{i \in I} p_{i} \ln \frac{q_{i}}{p_{i}} \geq 0

,

או לחלופין

- \sum_{i \in I} p_{i} \ln q_{i} \geq - \sum_{i \in I} p_{i} \ln p_{i}

.

ניתן להרחיב את שני הסכומים לכל $i = 1, \dots, n$ . כלומר כולל $p_{i} = 0$ , כאשר זוכרים כי הביטוי $p \ln p$ שואף ל-0 בגבול ש $p$ שואף ל-0, ו $(- \ln q)$ שואף ל $\infty$ כאשר $q$ שואף ל-0. לסיכום מתקבל

- \sum_{i = 1}^{n} p_{i} \ln q_{i} \geq - \sum_{i = 1}^{n} p_{i} \ln p_{i}

השוויון מתקבל כאשר מתקיימים שני התנאים:

לכל $i \in I$ $\frac{q_{i}}{p_{i}} = 1$ כך שמתקבל השוויון $\ln \frac{q_{i}}{p_{i}} = \frac{q_{i}}{p_{i}} - 1$ ,
$\sum_{i \in I} q_{i} = 1$ כלומר $q_{i} = 0$ אם $i \notin I$ . במילים אחרות, $q_{i} = 0$ אם $p_{i} = 0$ .

שני תנאים אלה יתקיימו אם ורק אם $p_{i} = q_{i}$ עֲבוּר $i = 1, \dots, n$ , כלומר ההתפלגויות $P$ ו $Q$ זהות.

הוכחה חלופית

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

מכיוון שהלוגריתם הוא פונקציה קעורה

\sum_{i} p_{i} \log \frac{q_{i}}{p_{i}} \leq \log \sum_{i} p_{i} \frac{q_{i}}{p_{i}} = \log \sum_{i} q_{i} = 0

כאשר אי-השוויון הראשון נובע מאי-השוויון של ינסן. השוויון האחרון נובע מכך ש $Q$ היא התפלגות הסתברות, ולכן $\sum q_{i} = 1$ .

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

$\frac{q_{1}}{p_{1}} = \frac{q_{2}}{p_{2}} = \dots = \frac{q_{n}}{p_{n}}$
$\sum_{i} q_{i} = 1$ .

נסמן ב $σ$ את היחס בתנאי הראשון לעיל. נתקבל

1 = \sum_{i} q_{i} = \sum_{i} σ p_{i} = σ

כלומר $p_{i} = q_{i}$ לכל $i = 1, \dots n$ . במילים אחרות, השוויון באי-שוויון ינסן מתקבל אם ורק אם ההתפלגויות $P$ ו $Q$ זהות.

הערות שוליים

↑ Pierre Bremaud (6 בדצמבר 2012). An Introduction to Probabilistic Modeling. Springer Science & Business Media. ISBN 978-1-4612-1046-7. {{cite book}}: (עזרה)
↑ David J. C. MacKay (25 בספטמבר 2003). Information Theory, Inference and Learning Algorithms. Cambridge University Press. ISBN 978-0-521-64298-9. {{cite book}}: (עזרה)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

אי-שוויון גיבס40194776Q1425564

[Bremaud2012-1] Pierre Bremaud (6 בדצמבר 2012). An Introduction to Probabilistic Modeling. Springer Science & Business Media. ISBN 978-1-4612-1046-7. {{cite book}}: (עזרה)

[MacKay2003-2] David J. C. MacKay (25 בספטמבר 2003). Information Theory, Inference and Learning Algorithms. Cambridge University Press. ISBN 978-0-521-64298-9. {{cite book}}: (עזרה)

[1]

[2]

אי-שוויון גיבס

תוכן עניינים