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

ג'וזיה וילארד גיבס

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

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

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

${\displaystyle -\sum _{i=1}^{n}p_{i}\log p_{i}\leq -\sum _{i=1}^{n}p_{i}\log q_{i}}$

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

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

${\displaystyle D_{\mathrm {KL} }(P\|Q)\equiv \sum _{i=1}^{n}p_{i}\log {\frac {p_{i}}{q_{i}}}\geq 0.}$

הוכחה

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

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

${\displaystyle -\sum _{i\in I}p_{i}\ln {\frac {q_{i}}{p_{i}}}\geq -\sum _{i\in I}p_{i}\left({\frac {q_{i}}{p_{i}}}-1\right)<=-\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 שאינם אפס הושמטו מאחר שבחירת האינדקסים ${\displaystyle I}$ נקבעת על סמך הדרישה ש p_i אינו אפס. לכן, סכום ה- q_i עשוי להיות קטן מ-1.

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

${\displaystyle -\sum _{i\in I}p_{i}\ln {\frac {q_{i}}{p_{i}}}\geq 0}$ ,

או לחלופין

${\displaystyle -\sum _{i\in I}p_{i}\ln q_{i}\geq -\sum _{i\in I}p_{i}\ln p_{i}}$ .

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

${\displaystyle -\sum _{i=1}^{n}p_{i}\ln q_{i}\geq -\sum _{i=1}^{n}p_{i}\ln p_{i}}$

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

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

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

הוכחה חלופית

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

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

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

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

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

• ${\displaystyle {\frac {q_{1}}{p_{1}}}={\frac {q_{2}}{p_{2}}}=\cdots ={\frac {q_{n}}{p_{n}}}}$
• ${\displaystyle \sum _{i}q_{i}=1}$ .

נסמן ב${\displaystyle \sigma }$ את היחס בתנאי הראשון לעיל. נתקבל

${\displaystyle 1=\sum _{i}q_{i}=\sum _{i}\sigma p_{i}=\sigma }$

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

הערות שוליים

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