דיברגנץ קולבק-לייבלר

בסטטיסטיקה מתמטית ובתורת האינפורמציה דיברגנץ קולבק-לייבלר (KL) (נקרא גם אנטרופיה יחסית), מסומן $D_{\text{KL}}(P\parallel Q)$, הוא סוג של מרחק סטטיסטי בין התפלגויות: מדד לאופן שבו התפלגות הסתברות אחת P שונה מהתפלגות הסתברות שנייה Q.

מתמטית

$D_{\text{KL}}(P\parallel Q)=\sum _{x\in {\mathcal {X}}}P(x)\ \log \left({\frac {\ P(x)\ }{Q(x)}}\right)$ .

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

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

הגדרה

עבור התפלגויות הסתברות בדידות P ו- Q המוגדרות על אותו מרחב מדגם$\ {\mathcal {X}}\ ,$, דיברגנץ קולבק-לייבלר מ- Q ל- P מוגדר כ

$D_{\text{KL}}(P\parallel Q)=\sum _{x\in {\mathcal {X}}}P(x)\ \log \left({\frac {\ P(x)\ }{Q(x)}}\right)$ ,

או לחלופין

$D_{\text{KL}}(P\parallel Q)=-\sum _{x\in {\mathcal {X}}}P(x)\ \log \left({\frac {\ Q(x)\ }{P(x)}}\right)$ .

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

דיברגנץ קולבק-לייבלר מוגדר בדרך זו רק אם לכל $x\in {\mathcal {X}}$, $\ Q(x)=0\$ גורר $\ P(x)=0\$. אחרת, הוא מוגדר כ $+\infty$. אבל דיברגנץ קולבק-לייבלר יכול לקבל את הערך $+\infty \$ גם אם $\ Q(x)\neq 0\$ בכל התומך של $Q$, בתנאי ש$\ {\mathcal {X}}\$אינסופי. הערות דומות חלות גם על התפלגויות רציפות.

בְּכָל נקודה שבה$\ P(x)\$הוא אפס, התרומה של האיבר המתאים בסכום מתאפסת מכיוון ש

$\lim _{x\to 0^{+}}x\log(x)=0$ .

עבור התפלגויות P ו- Q של משתנה אקראי רציף, דיברגנץ קולבק-לייבלר מוגדר כאינטגרל

$D_{\text{KL}}(P\parallel Q)=\int _{-\infty }^{\infty }p(x)\ \log \left({\frac {p(x)}{q(x)}}\right)\ \mathrm {d} \ \!x$

כאשר p ו- q מציינים את צפיפות ההסתברות של P ו- Q.

דוגמה

קולבק נותן את הדוגמה הבאה: יהיו P ו- Q ההתפלגויות המוצגות בטבלה ובאיור להלן. P, ההתפלגות בצד שמאל של האיור, היא התפלגות בינומית עם $N=2$ ו $p=0.4$ . Q ההתפלגות בצד ימין של האיור, היא התפלגות אחידה בדידה עם שלוש התוצאות האפשריות, 0, 1, 2 (כלומר ${\mathcal {X}}=\{0,1,2\}$), כל אחת בהסתברות $1/3$ .

שתי התפלגויות להמחשת דיברגנץ קולבק-לייבלר (אנטרופיה יחסית)

x	0	1	2
Distribution $P(x)$	${\frac {9}{25}}$	${\frac {12}{25}}$	${\frac {4}{25}}$
Distribution $Q(x)$	${\frac {1}{3}}$	${\frac {1}{3}}$	${\frac {1}{3}}$

${\begin{aligned}D_{\text{KL}}(P\parallel Q)&=\sum _{x\in {\mathcal {X}}}P(x)\ln \left({\frac {P(x)}{Q(x)}}\right)\\&={\frac {9}{25}}\ln \left({\frac {9/25}{1/3}}\right)+{\frac {12}{25}}\ln \left({\frac {12/25}{1/3}}\right)+{\frac {4}{25}}\ln \left({\frac {4/25}{1/3}}\right)\\&={\frac {1}{25}}\left(32\ln(2)+55\ln(3)-50\ln(5)\right)\approx 0.0852996\end{aligned}}$

${\begin{aligned}D_{\text{KL}}(Q\parallel P)&=\sum _{x\in {\mathcal {X}}}Q(x)\ln \left({\frac {Q(x)}{P(x)}}\right)\\&={\frac {1}{3}}\ln \left({\frac {1/3}{9/25}}\right)+{\frac {1}{3}}\ln \left({\frac {1/3}{12/25}}\right)+{\frac {1}{3}}\ln \left({\frac {1/3}{4/25}}\right)\\&={\frac {1}{3}}\left(-4\ln(2)-6\ln(3)+6\ln(5)\right)\approx 0.097455\end{aligned}}$

תכונות

• הערך של דיברגנץ קולבק-לייבלר הוא אי-שלילית.$$D_{\text{KL}}(P\parallel Q)\geq 0,$$ תוצאה המכונה גם אי-שוויון גיבס. $D_{\text{KL}}(P\parallel Q)=0$ אם ורק אם $P=Q$ כהתפלגויות.
• חסם תחתון מדויק יותר לערך של דיברגנץ קולבק-לייבלר

$$D_{\text{KL}}(P\parallel Q)\geq {\frac {1}{2}}\left(\sum _{x\in {\mathcal {X}}}|P(x)-Q(x)|\ \right)^{2}$$

• במקרה הכללי אין חסם עליון לערך של דיברגנץ קולבק-לייבלר.
• דיברגנץ קולבק-לייבלר נשאר מוגדר היטב עבור התפלגויות רציפות, ובנוסף הוא אינו משתנה תחת טרנספורמציות פרמטרים. לדוגמה, אם מתבצעת טרנספורמציה ממשתנה $x$ למשתנה $y(x)$ אזי $p(x)\,dx={\tilde {p}}(y)\,dy={\tilde {p}}(y(x))|{\tfrac {dy}{dx}}(x)|\,dx$ ובאותו אופן $q(x)\,dx={\tilde {q}}(y)\,dy={\tilde {q}}(y)|{\tfrac {dy}{dx}}(x)|dx$ כאשר $|{\tfrac {dy}{dx}}(x)|$ האו הערך המוחלט של הנגזרת, או באופן כללי יותר היעקוביאן. ניתן לכתוב את דיברגנץ קולבק-לייבלק: $${\begin{aligned}D_{\text{KL}}(P\parallel Q)&=\int _{x_{a}}^{x_{b}}p(x)\log \left({\frac {p(x)}{q(x)}}\right)\,dx\\[6pt]&=\int _{x_{a}}^{x_{b}}{\tilde {p}}(y(x))|{\frac {dy}{dx}}(x)|\log \left({\frac {{\tilde {p}}(y(x))\,|{\frac {dy}{dx}}(x)|}{{\tilde {q}}(y(x))\,|{\frac {dy}{dx}}(x)|}}\right)\,dx\\&=\int _{y_{a}}^{y_{b}}{\tilde {p}}(y)\log \left({\frac {{\tilde {p}}(y)}{{\tilde {q}}(y)}}\right)\,dy\end{aligned}}$$
• דיברגנץ קולבק-לייבלר הוא אדיטיבי להתפלגויות בלתי תלויות, בדיוק כמו האנטרופיה של שאנון. כלומר אם $P_{1}$ ו $P_{2}$ בלתי תלויות, ונסמן $P(x,y)=P_{1}(x)P_{2}(y)$ ובאותו אופן $Q(x,y)=Q_{1}(x)Q_{2}(y)$ עבור ההתפלגויות הבלתי תלויות $Q_{1}$ ו $Q_{2}$ אזי

$$D_{\text{KL}}(P\parallel Q)=D_{\text{KL}}(P_{1}\parallel Q_{1})+D_{\text{KL}}(P_{2}\parallel Q_{2})$$

• ניתן לפתח את $D_{\text{KL}}(P\parallel Q)$ (i.e. $P=Q$) כטור טיילור סביב נקודת המינימום (כלומר $P=Q$)$$D_{\text{KL}}(P\parallel Q)=\sum _{n=2}^{\infty }{\frac {1}{n(n-1)}}\sum _{x\in {\mathcal {X}}}{\frac {(Q(x)-P(x))^{n}}{Q(x)^{n-1}}}$$

דוגמאות

התפלגויות רב-נורמליות

נניח שתי התפלגות רב-נורמלית עם תוחלות $\mu _{0},\mu _{1}$ ועם מטריצות קווריאנס (לא סינגולריות) $\Sigma _{0},\Sigma _{1}$ . אם לשתי ההתפלגויות יש אותו ממד, k, אז דיברגנץ קולבק-לייבלר בין ההתפלגויות הוא:

$D_{\text{KL}}\left({\mathcal {N}}_{0}\parallel {\mathcal {N}}_{1}\right)={\frac {1}{2}}\left(\operatorname {tr} \left(\Sigma _{1}^{-1}\Sigma _{0}\right)-k+\left(\mu _{1}-\mu _{0}\right)^{\mathsf {T}}\Sigma _{1}^{-1}\left(\mu _{1}-\mu _{0}\right)+\ln \left({\frac {\det \Sigma _{1}}{\det \Sigma _{0}}}\right)\right).$

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

במימוש נומרי, רצוי לבטא את התוצאה במונחים של פירוק שולסקי $L_{0},L_{1}$ כך ש $\Sigma _{0}=L_{0}L_{0}^{T}$ ו $\Sigma _{1}=L_{1}L_{1}^{T}$ . ואז עם פתרונות M ו- y למערכות הליניאריות המשולשות $L_{1}M=L_{0}$, ו $L_{1}y=\mu _{1}-\mu _{0}$ נקבל

$D_{\text{KL}}\left({\mathcal {N}}_{0}\parallel {\mathcal {N}}_{1}\right)={\frac {1}{2}}\left(\sum _{i,j=1}^{k}(M_{ij})^{2}-k+|y|^{2}+2\sum _{i=1}^{k}\ln {\frac {(L_{1})_{ii}}{(L_{0})_{ii}}}\right).$

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

$D_{\text{KL}}\left({\mathcal {N}}\left(\left(\mu _{1},\ldots ,\mu _{k}\right)^{\mathsf {T}},\operatorname {diag} \left(\sigma _{1}^{2},\ldots ,\sigma _{k}^{2}\right)\right)\parallel {\mathcal {N}}\left(\mathbf {0} ,\mathbf {I} \right)\right)={1 \over 2}\sum _{i=1}^{k}\left(\sigma _{i}^{2}+\mu _{i}^{2}-1-\ln \left(\sigma _{i}^{2}\right)\right).$

עבור שתי התפלגות נורמלית במשתנה אחד, p ו- q האמור לעיל מפשט ל-

$D_{\text{KL}}\left({\mathcal {p}}\parallel {\mathcal {q}}\right)=\log {\frac {\sigma _{1}}{\sigma _{0}}}+{\frac {\sigma _{0}^{2}+(\mu _{0}-\mu _{1})^{2}}{2\sigma _{1}^{2}}}-{\frac {1}{2}}$

במקרה של התפלגויות נורמליות עם אותה תוחלת, נסמן $k=\sigma _{1}/\sigma _{0}$, וניתן לפשט את הביטוי לעיל:

$D_{\text{KL}}\left({\mathcal {p}}\parallel {\mathcal {q}}\right)=\log _{2}k+(k^{-2}-1)/2/\ln(2)\mathrm {bits}$

התפלגויות אחידות

תהיינה שתי התפלגויות אחידות, עם תומך סגור $p=[A,B]$ המוכל בתומך $q=[C,D]$ ( $C\leq A<B\leq D$ ). אזי:

$D_{\text{KL}}\left({\mathcal {p}}\parallel {\mathcal {q}}\right)=\log {\frac {D-C}{B-A}}$

קשר לגדלים אחרים בתורת האינפורמציה

גדלים אחרים בתורת האינפורמציה קשורים לדיברגנץ קולבק-לייבלר

אינפורמציה הדדית

ערך מורחב – אינפורמציה הדדית

ניתן לבטא את האינפורמציה הדדית במונחי דיברגנץ קולבק-לייבלר

${\begin{aligned}\operatorname {I} (X;Y)&=D_{\text{KL}}(P(X,Y)\parallel P(X)P(Y))\\[5pt]&=\operatorname {E} _{X}\{D_{\text{KL}}(P(Y\mid X)\parallel P(Y))\}\\[5pt]&=\operatorname {E} _{Y}\{D_{\text{KL}}(P(X\mid Y)\parallel P(X))\}\end{aligned}}$

האינפורמציה ההדדית היא המספר הצפוי של סיביות נוספות שיש להעביר לזיהוי X ו- Y אם הם מקודדים רק באמצעות ההתפלגות השולית שלהם במקום ההתפלגות המשותפת. באותו אופן, אם ההסתברות המשותפת $P(X,Y)$ ידועה, זהו תוחלת מספר הסיביות הנוספות שיש לשלוח בממוצע כדי לזהות את Y אם הערך של X אינו ידוע.

אנטרופיה של שאנון

ערך מורחב – אנטרופיה (סטטיסטיקה)

אם בוחרים עבור $Q$ בהתפלגות בדידה של N איברים ( $N=|{\mathcal {X}}|$) ניתן לכתוב את האנטרופיה של P

$\mathrm {H} (X)=\log(N)-D_{\text{KL}}\left(p_{X}(x)\parallel P_{U}(X)\right)$

זהו מספר הסיביות שיהיה צורך לשדר כדי לזהות את X מתוך N אפשרויות סבירות באותה מידה, בהפחתת האנטרופיה היחסית של ההתפלגות האחידה על המשתנים המקריים של X, $P_{U}(X)$, מההתפלגות האמיתית $P(X)$ - כלומר פחות המספר הצפוי של סיביות שנשמרו, שהיה צריך להישלח אם הערך של X היה מקודד לפי ההתפלגות האחידה $P_{U}(X)$ ולא את ההתפלגות האמיתית $P(X)$ . הגדרה זו של אנטרופיה שאנון מהווה את הבסיס להכללה האלטרנטיבית של אדווין תומפסון ג'יינס להתפלגות רציפות, הצפיפות המגבילה של נקודות בדידות (בניגוד לאנטרופיה הדיפרנציאלית הרגילה), המגדירה את האנטרופיה הרציפה

$\lim _{N\rightarrow \infty }H_{N}(X)=\log(N)-\int p(x)\log {\frac {p(x)}{m(x)}}\,dx,$

שהוא שווה ערך ל:

$\log(N)-D_{\text{KL}}(p(x)||m(x))$

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

ערך מורחב – אנטרופיה מותנית
ניתן לנסח את האנטרופיה המותנית באמצעות דיברגנץ קולבק-לייבלר

${\begin{aligned}\mathrm {H} (X\mid Y)&=\log(N)-D_{\text{KL}}(P(X,Y)\parallel P_{U}(X)P(Y))\\[5pt]&=\log(N)-D_{\text{KL}}(P(X,Y)\parallel P(X)P(Y))-D_{\text{KL}}(P(X)\parallel P_{U}(X))\\[5pt]&=\mathrm {H} (X)-\operatorname {I} (X;Y)\\[5pt]&=\log(N)-\operatorname {E} _{Y}\left[D_{\text{KL}}\left(P\left(X\mid Y\right)\parallel P_{U}(X)\right)\right]\end{aligned}}$

זהו מספר הסיביות שיש להעביר כדי לזהות את X מתוך N אפשרויות סבירות באותה מידה, בהפחתת האנטרופיה היחסית של התפלגות המכפלה $P_{U}(X)P(Y)$ מההתפלגות המשותפת האמיתית $P(X,Y)$ - כלומר פחות המספר הצפוי של ביטים שנשמרו שהיה צריך להישלח אם הערך של X היה מקודד לפי ההתפלגות האחידה $P_{U}(X)$ במקום ההתפלגות המותנית $P(X|Y)$ של X בהינתן Y.

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

• דיברגנץ קולבק-לייבלר, באתר MathWorld (באנגלית)