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

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

מתמטית

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

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

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

הגדרה

עבור התפלגויות הסתברות בדידות תבנית:Mvar ו- תבנית:Mvar המוגדרות על אותו מרחב מדגם$𝒳,$, דיברגנץ קולבק-לייבלר מ- תבנית:Mvar ל- תבנית:Mvar מוגדר כ

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

או לחלופין

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

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

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

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

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

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

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

כאשר תבנית:Mvar ו- תבנית:Mvar מציינים את צפיפות ההסתברות של תבנית:Mvar ו- תבנית:Mvar.

דוגמה

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

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

תבנית:Mvar	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{array}{cc}{D}_{\text{KL}}(P\parallel Q)& =\sum _{x\in 𝒳}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}(32\ln (2)+55\ln (3)-50\ln (5))\approx 0.0852996\end{array}$

$\begin{array}{cc}{D}_{\text{KL}}(Q\parallel P)& =\sum _{x\in 𝒳}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}(-4\ln (2)-6\ln (3)+6\ln (5))\approx 0.097455\end{array}$

תכונות

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

$$D_{\text{KL}}(P\parallel Q)\ge \frac{1}{2}{(\sum _{x\in 𝒳}|P(x)-Q(x)|)}^2$$

• במקרה הכללי אין חסם עליון לערך של דיברגנץ קולבק-לייבלר.
• דיברגנץ קולבק-לייבלר נשאר מוגדר היטב עבור התפלגויות רציפות, ובנוסף הוא אינו משתנה תחת טרנספורמציות פרמטרים. לדוגמה, אם מתבצעת טרנספורמציה ממשתנה $x$ למשתנה $y(x)$ אזי $p(x)dx=\tilde{p}(y)dy=\tilde{p}(y(x))|\frac{dy}{dx}(x)|dx$ ובאותו אופן $q(x)dx=\tilde{q}(y)dy=\tilde{q}(y)|\frac{dy}{dx}(x)|dx$ כאשר $|\frac{dy}{dx}(x)|$ האו הערך המוחלט של הנגזרת, או באופן כללי יותר היעקוביאן. ניתן לכתוב את דיברגנץ קולבק-לייבלק: $$\begin{array}{cc}{D}_{\text{KL}}(P\parallel Q)& =\underset{x_a}{\overset{x_b}{\int }}p(x)\log \left(\frac{p(x)}{q(x)}\right)dx\\ & =\underset{x_a}{\overset{x_b}{\int }}\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\\ & =\underset{y_a}{\overset{y_b}{\int }}\tilde{p}(y)\log \left(\frac{\tilde{p}(y)}{\tilde{q}(y)}\right)dy\end{array}$$
• דיברגנץ קולבק-לייבלר הוא אדיטיבי להתפלגויות בלתי תלויות, בדיוק כמו האנטרופיה של שאנון. כלומר אם $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}^{\mathrm{\infty }}\frac{1}{n(n-1)}\sum _{x\in 𝒳}\frac{(Q(x)-P(x){)}^n}{Q(x{)}^{n-1}}$$

דוגמאות

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

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

$D_{\text{KL}}({𝒩}_0\parallel {𝒩}_1)=\frac{1}{2}(\mathrm{tr}\left({\mathrm{\Sigma }}_1^{-1}{\mathrm{\Sigma }}_0\right)-k+{({\mu }_1-{\mu }_0)}^{𝖳}{\mathrm{\Sigma }}_1^{-1}({\mu }_1-{\mu }_0)+\ln \left(\frac{\det {\mathrm{\Sigma }}_1}{\det {\mathrm{\Sigma }}_0}\right)).$

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

במימוש נומרי, רצוי לבטא את התוצאה במונחים של פירוק שולסקי $L_0,L_1$ כך ש ${\mathrm{\Sigma }}_0=L_0{L}_0^T$ ו ${\mathrm{\Sigma }}_1=L_1{L}_1^T$ . ואז עם פתרונות תבנית:Mvar ו- תבנית:Mvar למערכות הליניאריות המשולשות $L_{1}M=L_0$, ו $L_{1}y={\mu }_1-{\mu }_0$ נקבל

$D_{\text{KL}}({𝒩}_0\parallel {𝒩}_1)=\frac{1}{2}(\sum _{i,j=1}^k(M_{ij}{)}^2-k+|y{|}^2+2\sum _{i=1}^k\ln \frac{(L_1{)}_{ii}}{(L_0{)}_{ii}}).$

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

$D_{\text{KL}}(𝒩({({\mu }_1,\dots ,{\mu }_k)}^{𝖳},\mathrm{diag}({\sigma }_1^2,\dots ,{\sigma }_k^2))\parallel 𝒩(\mathrm{𝟎},𝐈))=\frac{1}{2}\sum _{i=1}^k({\sigma }_i^2+{\mu }_i^2-1-\ln \left({\sigma }_i^2\right)).$

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

$D_{\text{KL}}(𝓅\parallel 𝓆)=\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}}(𝓅\parallel 𝓆)={\log }_{2}k+(k^{-2}-1)/2/\ln (2)\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}$

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

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

$D_{\text{KL}}(𝓅\parallel 𝓆)=\log \frac{D-C}{B-A}$

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

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

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

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

$\begin{array}{cc}\mathrm{I}(X;Y)& =D_{\text{KL}}(P(X,Y)\parallel P(X)P(Y))\\ & ={\mathrm{E}}_X\{D_{\text{KL}}(P(Y\mid X)\parallel P(Y))\}\\ & ={\mathrm{E}}_Y\{D_{\text{KL}}(P(X\mid Y)\parallel P(X))\}\end{array}$

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

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

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

$\mathrm{H}(X)=\log (N)-D_{\text{KL}}(p_X(x)\parallel P_U(X))$

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

$\underset{N\to \mathrm{\infty }}{\lim }{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{array}{cc}\mathrm{H}(X\mid Y)& =\log (N)-D_{\text{KL}}(P(X,Y)\parallel P_U(X)P(Y))\\ & =\log (N)-D_{\text{KL}}(P(X,Y)\parallel P(X)P(Y))-D_{\text{KL}}(P(X)\parallel P_U(X))\\ & =\mathrm{H}(X)-\mathrm{I}(X;Y)\\ & =\log (N)-{\mathrm{E}}_Y\left[D_{\text{KL}}(P(X\mid Y)\parallel P_U(X))\right]\end{array}$

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

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

• תבנית:MathWorld