הצגת המקור של הדף "דיברגנץ קולבק-לייבלר"

בסטטיסטיקה [[מתמטיקה|מתמטית]] וב[[תורת האינפורמציה]] '''[[דיברגנץ]] קולבק-לייבלר''' ('''KL''') (נקרא גם '''אנטרופיה יחסית'''<ref name="Csiszar">{{Cite journal|last=Csiszar|first=I|date=February 1975|title=I-Divergence Geometry of Probability Distributions and Minimization Problems|journal=Ann. Probab.|volume=3|issue=1|pages=146–158|doi=10.1214/aop/1176996454|doi-access=free}}</ref>), מסומן <math>D_\text{KL}(P \parallel Q)</math>, הוא סוג של מרחק סטטיסטי בין התפלגויות: מדד לאופן שבו [[התפלגות|התפלגות הסתברות]] אחת {{Mvar|P}} שונה מהתפלגות הסתברות שנייה {{Mvar|Q}}.<ref name="KullbackLeibler1951">{{Cite journal|last=Kullback|first=S.|last2=Leibler|first2=R.A.|year=1951|title=On information and sufficiency|journal=Annals of Mathematical Statistics|volume=22|issue=1|pages=79–86|doi=10.1214/aoms/1177729694|jstor=2236703|mr=39968|doi-access=free}}</ref>

מתמטית

: <math>D_\text{KL}(P \parallel Q) = \sum_{ x \in \mathcal{X} } P(x)\ \log\left(\frac{\ P(x)\ }{ Q(x) }\right)</math> .

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

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

{{הגבלת תוכן עניינים|רמה=3}}

== הגדרה ==
עבור [[התפלגות|התפלגויות הסתברות בדידות]] {{Mvar|P}} ו- {{Mvar|Q}} המוגדרות על אותו מרחב מדגם<math>\ \mathcal{X}\ ,</math>, דיברגנץ קולבק-לייבלר מ- {{Mvar|Q}} ל- {{Mvar|P}} מוגדר כ<ref name="MacKey2003">{{Cite book|last=MacKay|first=David J.C.|url={{google books| plainurl=y |id=AKuMj4PN_EMC}}|title=Information Theory, Inference, and Learning Algorithms|publisher=Cambridge University Press|year=2003|isbn=9780521642989|edition=1st|page=34|via=Google Books}}</ref>

: <math> D_\text{KL}(P \parallel Q) = \sum_{ x \in \mathcal{X} } P(x)\ \log\left(\frac{\ P(x)\ }{ Q(x) }\right)</math> ,

או לחלופין

: <math> D_\text{KL}(P \parallel Q) = -\sum_{ x \in \mathcal{X} } P(x)\ \log\left(\frac{\ Q(x)\ }{P(x)}\right) </math> .

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

דיברגנץ קולבק-לייבלר מוגדר בדרך זו רק אם לכל <math>x \in \mathcal{X} </math>, <math>\ Q(x) = 0\ </math> גורר <math>\ P(x) = 0\ </math>. אחרת, הוא מוגדר כ {{ללא גלישה|<math>+\infty</math><ref name=Csiszar/>}}. אבל דיברגנץ קולבק-לייבלר יכול לקבל את הערך <math> +\infty\ </math> גם אם <math>\ Q(x) \ne 0\ </math> בכל ה[[תומך (מתמטיקה)|תומך]] של <math>Q </math>,<ref>{{Cite web|title=What's the maximum value of Kullback-Leibler (KL) divergence?|url=https://stats.stackexchange.com/q/351947|website=Statistics Stack Exchange (stats.stackexchange.com)|series=Cross validated}}</ref><ref>{{Cite web|title=In what situations is the integral equal to infinity?|url=https://math.stackexchange.com/q/20961|website=Mathematics Stack Exchange (math.stackexchange.com)}}</ref> בתנאי ש<math>\ \mathcal{X}\ </math>אינסופי. הערות דומות חלות גם על התפלגויות רציפות.

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

: <math> \lim_{x \to 0^{+}} x \log(x) = 0 </math> .

עבור התפלגויות {{Mvar|P}} ו- {{Mvar|Q}} של [[התפלגות|משתנה אקראי רציף]], דיברגנץ קולבק-לייבלר מוגדר כאינטגרל<ref>{{Cite book|last=Bishop|first=Christopher M.|url=http://worldcat.org/oclc/1334664824|title=Pattern recognition and machine learning|page=55|oclc=1334664824}}</ref>

: <math> D_\text{KL}(P \parallel Q) = \int_{-\infty}^\infty p(x)\ \log\left(\frac{p(x)}{q(x)}\right)\ \mathrm{d}\ \!x</math>

כאשר {{Mvar|p}} ו- {{Mvar|q}} מציינים את [[פונקציית צפיפות|צפיפות ההסתברות]] של {{Mvar|P}} ו- {{Mvar|Q}}.

== דוגמה ==
קולבק נותן את הדוגמה הבאה: יהיו {{Mvar|P}} ו- {{Mvar|Q}} ההתפלגויות המוצגות בטבלה ובאיור להלן. {{Mvar|P}}, ההתפלגות בצד שמאל של האיור, היא [[התפלגות בינומית]] עם <math>N = 2</math> ו <math>p = 0.4</math> . {{Mvar|Q}} ההתפלגות בצד ימין של האיור, היא [[התפלגות אחידה בדידה]] עם שלוש התוצאות האפשריות, 0, 1, 2 (כלומר <math>\mathcal{X}=\{0,1,2\}</math>), כל אחת בהסתברות <math> 1/3</math> .
[[קובץ:Kullback–Leibler_distributions_example_1.svg|ללא|ממוזער|400x400 פיקסלים| שתי התפלגויות להמחשת דיברגנץ קולבק-לייבלר (אנטרופיה יחסית)]]
{| class="wikitable" style="text-align: center;"
!{{Mvar|x}}
|0
|1
|2
|-
!Distribution <math>P(x)</math>
|<math>\frac 9{25}</math>
|<math>\frac{12}{25}</math>
|<math>\frac 4{25}</math>
|-
!Distribution <math>Q(x)</math>
|<math>\frac 1 3</math>
|<math>\frac 1 3</math>
|<math>\frac 1 3</math>
|}

: <math>\begin{align}
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{align}</math>

: <math>\begin{align}
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{align}</math>

== תכונות ==
* הערך של דיברגנץ קולבק-לייבלר הוא אי-שלילית.<math display="block">D_\text{KL}(P \parallel Q) \geq 0,</math> תוצאה המכונה גם [[אי-שוויון גיבס]]. <math>D_\text{KL}(P\parallel Q) = 0</math> [[אם ורק אם]] <math>P = Q</math> כהתפלגויות.
* חסם תחתון מדויק יותר לערך של דיברגנץ קולבק-לייבלר<ref>{{צ-מאמר|מחבר=PANTELIMON G. POPESCU, SEVER S. DRAGOMIR,
EMIL I. SLUS¸ANSCHI, OCTAVIAN N. STAN˘ AS¸IL ˘ A|שם=BOUNDS FOR KULLBACK-LEIBLER DIVERGENCE|כתב עת=Electronic Journal of Differential Equations|כרך=2016|שנת הוצאה=2016|עמ=6–1|קישור=https://ejde.math.txstate.edu/Volumes/2016/237/popescu.pdf}}</ref>
<math display="block">D_\text{KL}(P \parallel Q) \geq \frac{ 1 }{2} \left (\sum_{ x \in \mathcal{X} } | P(x) - Q(x) |\ \right)^2</math>
* במקרה הכללי אין [[חסם (מתמטיקה)|חסם עליון]] לערך של דיברגנץ קולבק-לייבלר.
* דיברגנץ קולבק-לייבלר נשאר מוגדר היטב עבור התפלגויות רציפות, ובנוסף הוא אינו משתנה תחת טרנספורמציות פרמטרים. לדוגמה, אם מתבצעת טרנספורמציה ממשתנה <math>x</math> למשתנה <math>y(x)</math> אזי <math> p(x) \, dx = \tilde{p}(y) \, dy = \tilde{p}(y(x)) |\tfrac{dy}{dx}(x)| \,dx </math> ובאותו אופן <math>q(x)\, dx = \tilde{q}(y) \, dy = \tilde{q}(y) |\tfrac{dy}{dx}(x)| dx</math> כאשר <math>|\tfrac{dy}{dx}(x)|</math> האו [[ערך מוחלט|הערך המוחלט]] של הנגזרת, או באופן כללי יותר ה[[יעקוביאן]]. ניתן לכתוב את דיברגנץ קולבק-לייבלק: <math display="block">\begin{align}
 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{align}</math>
* דיברגנץ קולבק-לייבלר הוא אדיטיבי להתפלגויות בלתי תלויות, בדיוק כמו האנטרופיה של שאנון. כלומר אם <math>P_1</math> ו <math>P_2</math> בלתי תלויות, ונסמן <math>P(x, y) = P_1(x)P_2(y)</math> ובאותו אופן <math>Q(x, y) = Q_1(x)Q_2(y)</math> עבור ההתפלגויות הבלתי תלויות <math>Q_1</math> ו <math>Q_2</math> אזי
:: <math display="block">D_\text{KL}(P \parallel Q) = D_\text{KL}(P_1 \parallel Q_1) + D_\text{KL}(P_2 \parallel Q_2)</math>
* ניתן לפתח את <math>D_\text{KL}(P \parallel Q)</math> (i.e. <math>P=Q</math>) כ[[טור טיילור]] סביב נקודת המינימום (כלומר <math>P=Q</math>)<math display="block">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}} </math>

== דוגמאות ==
=== התפלגויות רב-נורמליות ===
נניח שתי [[התפלגות רב-נורמלית]] עם תוחלות <math>\mu_0, \mu_1</math> ועם מטריצות קווריאנס (לא סינגולריות) <math>\Sigma_0, \Sigma_1</math> . אם לשתי ההתפלגויות יש אותו ממד, {{Mvar|k}}, אז דיברגנץ קולבק-לייבלר בין ההתפלגויות הוא:<ref>{{Cite web|last=Duchi J.|title=Derivations for Linear Algebra and Optimization|url=https://web.stanford.edu/~jduchi/projects/general_notes.pdf|page=13}}</ref>

: <math>
 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).
</math>

באיבר האחרון יש להשתמש ב[[לוגריתם]] בבסיס הטבעי מכיוון שכל האיברים מלבד האחרון הם לוגריתמים טבעיים של ביטויים שהם גורמים של פונקציית הצפיפות או שנוצרים באופן טבעי בדרך אחרת. כדי כדי שהדיברגנץ יבטא יחידות של [[סיבית|סיביות]] יש לחלק את הביטוי לעיל ב <math>\ln(2)</math> .

במימוש נומרי, רצוי לבטא את התוצאה במונחים של [[פירוק שולסקי]] <math>L_0, L_1</math> כך ש <math>\Sigma_0 = L_0L_0^T</math> ו <math>\Sigma_1 = L_1L_1^T</math> . ואז עם פתרונות {{Mvar|M}} ו- {{Mvar|y}} למערכות הליניאריות המשולשות <math>L_1 M = L_0</math>, ו <math>L_1 y = \mu_1 - \mu_0</math> נקבל

: <math>
 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).
</math>

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

: <math>
 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).
</math>

עבור שתי התפלגות נורמלית במשתנה אחד, {{Mvar|'''p'''}} ו- {{Mvar|'''q'''}} האמור לעיל מפשט ל- <ref>{{Cite journal|last=Belov|first=Dmitry I.|last2=Armstrong|first2=Ronald D.|date=2011-04-15|title=Distributions of the Kullback-Leibler divergence with applications|url=http://dx.doi.org/10.1348/000711010x522227|journal=British Journal of Mathematical and Statistical Psychology|volume=64|issue=2|pages=291–309|doi=10.1348/000711010x522227|issn=0007-1102|pmid=21492134}}</ref>

: <math>
 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}
</math>

במקרה של התפלגויות נורמליות עם אותה תוחלת, נסמן <math>k=\sigma_1/\sigma_0</math>, וניתן לפשט את הביטוי לעיל<ref name="auto">{{Cite book|last=Buchner|first=Johannes|url=http://worldcat.org/oclc/1363563215|title=An intuition for physicists: information gain from experiments|date=2022-04-29|oclc=1363563215}}</ref>:

<math>
 D_\text{KL}\left(\mathcal{p} \parallel \mathcal{q}\right) = \log_2 k + (k^{-2}-1)/2/\ln(2) \mathrm{bits}
</math>

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

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

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

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

: <math>\begin{align}
 \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{align}</math>

האינפורמציה ההדדית היא המספר הצפוי של סיביות נוספות שיש להעביר לזיהוי {{Mvar|X}} ו- {{Mvar|Y}} אם הם מקודדים רק באמצעות ההתפלגות השולית שלהם במקום ההתפלגות המשותפת. באותו אופן, אם ההסתברות המשותפת <math>P(X,Y)</math> ''ידועה'', זהו תוחלת מספר הסיביות הנוספות שיש לשלוח בממוצע כדי לזהות את {{Mvar|Y}} אם הערך של {{Mvar|X}} אינו ידוע.

=== אנטרופיה של שאנון ===
{{הפניה לערך מורחב|אנטרופיה (סטטיסטיקה)}}

אם בוחרים עבור <math>Q</math> בהתפלגות בדידה של N איברים ( <math>N = |\mathcal{X}|</math>) ניתן לכתוב את האנטרופיה של P
: <math>
 \Eta(X) =\log(N) - D_\text{KL}\left(p_X(x) \parallel P_U(X)\right)
</math>

זהו מספר הסיביות שיהיה צורך לשדר כדי לזהות את {{Mvar|X}} מתוך {{Mvar|N}} אפשרויות סבירות באותה מידה, ''בהפחתת'' האנטרופיה היחסית של ההתפלגות האחידה על המשתנים המקריים של {{Mvar|X}}, <math>P_U(X)</math>, מההתפלגות האמיתית <math>P(X)</math> - כלומר ''פחות'' המספר הצפוי של סיביות שנשמרו, שהיה צריך להישלח אם הערך של {{Mvar|X}} היה מקודד לפי ההתפלגות האחידה <math>P_U(X)</math> ולא את ההתפלגות האמיתית <math>P(X)</math> . הגדרה זו של אנטרופיה שאנון מהווה את הבסיס להכללה האלטרנטיבית של [[אדווין תומפסון ג'יינס]] להתפלגות רציפות, הצפיפות המגבילה של נקודות בדידות (בניגוד לאנטרופיה הדיפרנציאלית הרגילה), המגדירה את האנטרופיה הרציפה

: <math>\lim_{N \rightarrow \infty} H_{N}(X) = \log(N) - \int p(x)\log\frac{p(x)}{m(x)}\,dx,</math>

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

: <math>\log(N) - D_\text{KL}(p(x)||m(x))</math>

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

: <math>\begin{align}
 \Eta(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]
 &= \Eta(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{align}</math>

זהו מספר הסיביות שיש להעביר כדי לזהות את {{Mvar|X}} מתוך {{Mvar|N}} אפשרויות סבירות באותה מידה, ''בהפחתת'' האנטרופיה היחסית של התפלגות המכפלה <math>P_U(X) P(Y)</math> מההתפלגות המשותפת האמיתית <math>P(X,Y)</math> - כלומר ''פחות'' המספר הצפוי של ביטים שנשמרו שהיה צריך להישלח אם הערך של {{Mvar|X}} היה מקודד לפי ההתפלגות האחידה <math>P_U(X)</math> במקום ההתפלגות המותנית <math>P(X|Y)</math> של {{Mvar|X}} בהינתן {{Mvar|Y}}.

==קישורים חיצוניים==
* {{MathWorld}}

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{בקרת זהויות}}

[[קטגוריה:תרמודינמיקה]]
[[קטגוריה:דפים עם תרגומים שלא נסקרו]]