معیار واگرایی کولبک-لیبلر

در آمار ریاضی از Kullback–Leibler واگرایی به عنوان معیاری برای اندازه‌گیری واگرایی یک توزیع احتمال از یک توزیع احتمال ثانویه، یاد می‌شود.[1][2] از جمله کاربردهای این مفهوم شامل توصیف آنتروپی نسبی (Shannon) در سیستم‌های اطلاعاتی، رندمنس در سریهای زمانی پیوسته و بهره اطلاعاتی در زمانی که به مقایسه با مدلهای آماری استنباطی می‌پردازیم، می‌باشد. برخلاف تنوع اطلاعات، این معیار، یک معیار نامتقارن می‌باشد و در نتیجه نمی‌توان آن را به عنوان یک معیار پراکندگی معرفی کرد. به عبارت دیگر، مقدار ۰ برای Kullback–Leibler واگرایی نشان می‌دهد که ما می‌توانیم انتظار رفتار مشابهی (نه دقیقاً یکسان) از دو توزیع داشته باشیم در حالی که مقدار ۱ برای این معیار نشان می‌دهد که دو توزیع رفتارهای متضادی دارند.

ریشه‌شناسی

عبارت واگرایی Kullback–Leibler در اصل توسط Solomon Kullback و Richard Leibler در سال ۱۹۵۱ به عنوان واگرایی جهت‌دار بین دو توزیع معرفی گردید؛ هرچند که Kullback خودش نامتمییز اطلاعات را بیشتر ترجیح می‌داد.[3] در Kullback's historic text, Information Theory and Statistics، این معیار مورد بحث قرار گرفته است.

تفسیر

واگرایی Kullback-Leibler توزیع Q نسبت به P اغلب به صورت (DKL(P‖Q نوشته می‌شود.

در حوزه یادگیری ماشین از (P‖Q)D_KL عموماً به نام بهره اطلاعاتی حاصله به شرطی که به جای توزیع P از توزیع Q استفاده شود، یاد می‌شود. از منظر تئوری اطلاعات، به این مسئله آنتروپی نسبی از توزیع P با توجه به توزیع Q نامیده می‌شود. در حوزه نظریه کدینگ، (DKL(P‖Q می‌تواند به عنوان معیاری برای اندازه‌گیری متوسط تعداد بیت‌های اضافی مورد نیاز به منظور کد کردن نمونه‌ای از توزیع P با استفاده از یک کد بهینه‌سازی شده برای توزیع Q، به جای استفاده از کد بهینه‌سازی شده برای P می‌باشد.

از منظر استنتاج بیزین (D_KL(P‖Q، یک معیار اندازه‌گیری اطلاع کسب شده هنگامی که یک اصلاح باورهای از توزیع پیشین احتمال Q به توزیع پسین احتمال P رخ دهد. به عبارت دیگر، مقداری از اطلاع است که به واسطه تقریب زدن P در هنگامی که از Q برای آن استفاده می‌شود، می‌باشد.[4] در عمل، P به طور معمول نشان دهنده توزیع «صحیح» داده‌ها، مشاهدات یا یک توزیع تئوری ایست که دقیق محاسبه شده است در حالی که Q به طور معمول نشان دهنده یک نظریه، مدل، توصیف یا تقریبی از P می‌باشد. به منظور پیدا کردن یک توزیع Q که نزدیکترین توزیع به P باشد، می‌توان به دنبال محاسبه توزیعی گشت که معیار واگرایی KL را کمینه می‌کند.

تعریف

برای توزیعهای احتمالاتی گسسته P و Q معیار واگرایی Kullback–Leibler واگرایی از Q به P، به صورت زیر تعریف می‌شود[5]

${\displaystyle D_{\mathrm {KL} }(P\|Q)=\sum _{i}P(i)\,\log {\frac {P(i)}{Q(i)}}.}$

به عبارت دیگر، امید تفاوت لگاریتمی بین احتمالات P و Q در جایی که امید با استفاده از توزیع P به دست آمده باشد، می‌باشد. معیار واگرایی Kullback–Leibler تنها در صورتی Q(i)=0 نتیجه دهد P(i)=0 تعریف شده است، هر زمان که (P(i برابر صفر گردد سهم iمین ترم صفر تفسیر می‌شود و این بخاطر ${\displaystyle \lim _{x\to 0}x\log(x)=0}$ می‌باشد.

برای توزیعهای P و Q از یک متغیر تصادفی پیوسته، معیار واگرایی Kullback–Leibler به صورت انتگرال زیر تعریف می‌شود:[6]

${\displaystyle D_{\mathrm {KL} }(P\|Q)=\int _{-\infty }^{\infty }p(x)\,\log {\frac {p(x)}{q(x)}}\,{\rm {d}}x,\!}$

به طوریکه در آن p و q به معنی چگالی احتمال P و Q می‌باشد.

به طور کلی، اگر P و Q احتمالهایی تعریف شده بر روی یک مجموعه X باشند و P اکیداً پیوسته نسبت به Q باشد، آنگاه معیار واگرایی Kullback–Leibler از Q به P به صورت زیر تعریف می‌گردد:

${\displaystyle D_{\mathrm {KL} }(P\|Q)=\int _{X}\log {\frac {{\rm {d}}P}{{\rm {d}}Q}}\,{\rm {d}}P,\!}$

در این تعریف،${\displaystyle {\frac {{\rm {d}}P}{{\rm {d}}Q}}}$ مشتق Radon–Nikodym از P نسبت به Q می‌باشد و می‌تواند به صورت زیر بازنویسی شود:

${\displaystyle D_{\mathrm {KL} }(P\|Q)=\int _{X}\log \!\left({\frac {{\rm {d}}P}{{\rm {d}}Q}}\right){\frac {{\rm {d}}P}{{\rm {d}}Q}}\,{\rm {d}}Q,}$

که ما آن را به عنوان آنتروپی نسبی P نسبت به Q می‌شناسیم. در ادامه در این مورد، اگر ${\displaystyle \mu }$ هر اندازه‌گیری بر روی X باشد که در آن ${\displaystyle p={\frac {{\rm {d}}P}{{\rm {d}}\mu }}}$ و${\displaystyle q={\frac {{\rm {d}}Q}{{\rm {d}}\mu }}}$ برقرار باشد (به این معنی که p و q اکیداً نسبت به ${\displaystyle \mu }$) آنگاه معیار واگرایی Kullback–Leibler از Q به P، به صورت زیر می‌باشد

${\displaystyle D_{\mathrm {KL} }(P\|Q)=\int _{X}p\,\log {\frac {p}{q}}\,{\rm {d}}\mu .\!}$

در صورتی که اطلاعات با واحد بیت اندازه‌گیری شده باشد لگاریتمها در مبنای 2 می‌باشند و در صورتی که از واحد nats برای سنجش اطلاعات استفاده شده باشد، پایه لگاریتمها e خواهد بود.

قراردادهای مختلفی برای اشاره به D_KL(P‖Q) به صورت لفظی وجود دارد. اغلب از آن به عنوان اختلاف بین توزیعهای P و Q یاد می‌شود;در حالی که این توصیف با خاصیت نامتقارن بودن فرمول (یعنی واگرایی توزیع P از Q با میزان واگرایی توزیع Q از P لزوماً برابر نیست) در تعارض است. از این رو برخی مواقع، همان‌طور که در این مقاله هم از آن یاد شد، از آن به عنوان واگرایی توزیع P از یا نسبت به توزیع Q یاد می‌کنند.

خصوصیات

Arthur Hobson ثابت کرد که معیار واگرایی Kullback–Leibler تنها معیار تفاوت بین توزیعهای احتمالی است که برخی از خواص مورد نظر را در خود دارد.[7] و نتیجتاً، اطلاعات متقابل نیز تنها معیار وابستگی متقابل میان متغیرهای تصادفی است که یکسری شرایط خاص را دارا می‌باشد، چرا که آن می‌تواند از منظر معیار واگرایی مورد نظر نیز تعریف گردد.اطلاعات متقابل

همچنین خصوصیاتی از نقطه نظر بیز هم برای این معیار وجود دارد.[8]

انگیزه

در تئوری اطلاعات، قضیه Kraft–McMillan بیان می‌کند که هر شمای کدگذاری قابل دیکد کردنی برای کد کردن یک پیام به طوریکه بتوان مقدار x_i را از مجموعه تمامی مقادیر ممکن X به صورت مستقیم دیکد کند نیاز تا احتمال نمایش هر مقدار را به صورت توزیع احتمال q(x_i)=2^−l_i در نظر گرفته شود که در آن l_i، طول کد برای x_i در واحد بیت می‌باشد. بنابراین، معیار واگرایی Kullback–Leibler را می‌توان به عنوان امید مقدار طول پیام اضافی به ازای هر داده دانست که در صورتی که اگر از یک کد که برای توزیع Q بهینه است (توزیع ناصحیح) برای انتقال آن استفاده گردد، باید به صورت اضافی (نسبت به حالتی که از یک کد بهینه برای توزیع صحیح استفاده شود) مخابره گردد.

${\displaystyle {\begin{matrix}D_{\mathrm {KL} }(P\|Q)&=&-\sum _{x}p(x)\log q(x)&+&\sum _{x}p(x)\log p(x)\\[0.5em]&=&H(P,Q)&-&H(P)\,\!\end{matrix}}}$

در اینجا H(P,Q) آنتروپی مشترک توزیعهای P و Q می‌باشد و H(P) نیز آنتروپی توزیع P می‌باشد.

همچنین توجه داشته باشید که یک رابطه میان معیار واگرایی Kullback–Leibler و «تابع نرخ» در نظریه انحراف بزرگ وجود دارد.[9][10]

رابطه با معیارهای

ممکن است برخی معیار واگرایی Kullback–Leibler را به عنوان یک «معیار فاصله» در فضای توزیعهای احتمالی معرفی نماید اما این فرض صحیح نیست چراکه این معیار متقارن نیست، یعنی ${\displaystyle D_{\mathrm {KL} }(P\|Q)\neq D_{\mathrm {KL} }(Q\|P)}$ و همچنین نامساوی مثلث در مورد آن صادق نیست.

اگر ${\displaystyle \{P_{1},P_{2},\cdots \}}$ دنباله‌ای از توزیعها باشد به صورتی که حد میزان واگرایی توزیع Pn نسبت به Q در زمانی که n به سمت بینهایت میل می‌کند برابر صفر باشد.

(1)

به این ترتیب می‌توان گفت

${\displaystyle {\begin{matrix}{}\\P_{n}{\xrightarrow {D}}Q\\{}\end{matrix}}}$.

(2)

به این ترتیب از نامساوی Pinsker نتیجه می‌گیریم

${\displaystyle {\begin{matrix}{}\\P_{n}{\xrightarrow {\mathrm {D<nowiki>} }}</nowiki>P\Rightarrow P_{n}{\xrightarrow {\mathrm {TV<nowiki>} }}</nowiki>P\\{}\end{matrix}}}$,

(3)

که آن به معنای همگرایی در مجموع تنوع می‌باشد.

برگرفته شده از Rényi (1970, 1961)[11][12]

جستارهای وابسته

• Akaike Information Criterion
• بیزی اطلاعات معیار
• Bregman واگرایی
• Cross-entropy
• انحراف معیار اطلاعات
• آنتروپی ارزش در معرض خطر
• آنتروپی قدرت نابرابری
• به دست آوردن اطلاعات در درخت‌های تصمیم‌گیری
• اطلاعات به دست آوردن نسبت
• اطلاعات تئوری و نظریه اندازه‌گیری
• جنسن–Shannon واگرایی
• کوانتومی آنتروپی نسبی
• جزایر Kullback و ریچارد Leibler

منابع

1. Kullback, S.; Leibler, R.A. (1951). "On information and sufficiency". Annals of Mathematical Statistics. 22 (1): 79–86. doi:10.1214/aoms/1177729694. MR 0039968.
2. Kullback, S. (1959). Information Theory and Statistics. John Wiley & Sons.
3. Kullback, S. (1987). "Letter to the Editor: The Kullback–Leibler distance". The American Statistician. 41 (4): 340–341. doi:10.1080/00031305.1987.10475510. JSTOR 2684769.
4. Burnham K.P. , Anderson D.R. (2002), Model Selection and Multi-Model Inference (Springer). (2nd edition), p.51
5. MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms (First ed.). Cambridge University Press. p. 34.
6. Bishop C. (2006).
7. Hobson, Arthur (1971). Concepts in statistical mechanics. New York: Gordon and Breach. ISBN 0-677-03240-4.
8. Baez, John; Fritz, Tobias (2014). "A Bayesian characterization of relative entropy". Theory and Application of Categories. 29: 421–456.
9. Sanov, I.N. (1957). "On the probability of large deviations of random magnitudes". Matem. Sbornik. 42 (84): 11–44.
10. Novak S.Y. (2011), Extreme Value Methods with Applications to Finance ch. 14.5 (Chapman & Hall).
11. Rényi A. (1970). Probability Theory. Elsevier. Appendix, Sec.4. ISBN 0-486-45867-9.
12. Rényi, A. (1961), "On measures of entropy and information" (PDF), Proceedings of the 4th Berkeley Symposium on Mathematics, Statistics and Probability 1960, pp. 547–561