نابرابری هوفدینگ

در نظریه احتمال، نابرابری هوفدینگ (Hoeffding's inequality) ابزاری قدرتمند جهت محدود کردن جمع تعدادی متغیر تصادفی مستقل کراندار ($M_n=X_1+X_2+...+X_n$) است که کاربردهای وسیعی در یادگیری ماشین دارد. نابرابری هوفدینگ توسط واسیلی هوفدینگ در سال ۱۹۶۳ ثابت شد.

مقدمه

یکی از سوالات اساسی در احتمالات، آمار و یادگیری ماشین از این قرار است:

متغیر تصادفی $Z$ ، با امید ریاضی $E[Z]$ را در نظر بگیرید. می‌خواهیم بدانیم که $Z$ چه مقدار از میانگین خود فاصله دارد، یا به زبان ریاضی می‌خواهیم

$P(Z>E[Z]+t)$ و $P(Z<E[Z]-t)$

الگو:پایان چپ چین را به ازای $t>0$ حساب کنیم. در مواقعی که با چنین سوالاتی مواجه می‌شویم نیاز داریم که احتمال‌های بالا را به طریقی محدود کنیم، این محدود سازی از طریق نابرابری‌هایی مانند نابرابری مارکف، نابرابری هوفدینگ، نابرابری چبیشف و تعداد زیادی دیگر از نابرابری‌های مشابه انجام می‌شود.

توضیح صورت‌های مختلف نابرابری هوفدینگ

اگر الگو:ریاضی.. , X_n متغیر تصادفی مستقل محدود به بازه [۰٬۱]: الگو:ریاضی باشند و $\bar{X}$ را به صورت زیر تعریف کنیم:

$\bar{X}=\frac{1}{n}(X_1+\cdots +X_n).$

اولین نابرابری هوفدینگ به شرح زیر خواهد بود($0\le t$)

$\begin{array}{c}\mathbb{P}(\bar{X}-\mathrm{E}[\bar{X}]\ge t)\le e^{-2n{t}^2}\end{array}$

نابرابری بعدی در اصل تعمیم نابرابری اول است. اگر الگو:ریاضی.. , X_n متغیر تصادفی مستقل و $a_i\le X_i\le b_i$ باشند این بار خواهیم داشت:

$\begin{array}{cc}\mathbb{P}(\bar{X}-\mathrm{E}\left[\bar{X}\right]\ge t)& \le \exp (-\frac{2n^2{t}^2}{\sum _{i=1}^n(b_i-a_i{)}^2})\\ \mathbb{P}(|\bar{X}-\mathrm{E}\left[\bar{X}\right]|\ge t)& \le 2\exp (-\frac{2n^2{t}^2}{\sum _{i=1}^n(b_i-a_i{)}^2})\end{array}$

اثبات

قضیه را برای $a_i=a$ و $b_i=b$ ثابت می‌کنیم. (یعنی $a_i$ و $b_i$ به ازای تمامی $i$‌ها یکسان است) بنابراین صورت مسئله به صورت زیر در می‌آید:

فرض کنید $Z_1,...,Z_n$ متغیرهای تصادفی مستقل کراندار با $[a,b]$ ∋ $Z_i$ برای تمامی iها باشند. در این صورت خواهیم داشت:

$P(\frac{1}{n}\sum _{i=1}^n(Z_i-E[Z_i])\ge t)\le exp(-\frac{2n{t}^2}{(b-a{)}^2})$

الگو:پایان چپ چین و الگو:چپ چین

$P(\frac{1}{n}\sum _{i=1}^n(Z_i-E[Z_i])\le -t)\le exp(-\frac{2n{t}^2}{(b-a{)}^2})$

این قضیه را با ترکیبی از (۱) کران چرنوف و (۲) یک لم کلاسیک به نام لم هافدینگ که الان آن را بیان می‌کنیم، ثابت می‌کنیم.

• لم هافدینگ:(Hoeffding's lemma)

برای $Z$ یک متغیر تصادفی مستقل کراندار با $[a,b]$ ∋ $Z$ است. در این صورت خواهیم داشت:

به ازای هر $\lambda \in ℝ$

الگو:چپ چین

$E[exp(\lambda (Z-E[Z]))]\le exp(\frac{{\lambda }^2(b-a{)}^2}{8})$ الگو:پایان چپ چین حال با استفاده از این لم به اثبات کران بالای نابرابری هوفدینگ (یعنی$P(\frac{1}{n}\sum _{i=1}^n(Z_i-E[Z_i])\ge t)\le exp(-\frac{2n{t}^2}{(b-a{)}^2})$)می‌پردازیم. (اثبات برای کران پایین دقیقاً به همین شکل است) در مرحلهٔ اول از کران چرنوف استفاده می‌کنیم:

الگو:چپ چین

$P(\frac{1}{n}\sum _{i=1}^n(Z_i-E[Z_i])\ge t)=P(\sum _{i=1}^n(Z_i-E[Z_i])\ge nt)$

$\le E[exp(\lambda \sum _{i=1}^n(Z_i-E[Z_i]))]e^{-\lambda nt}$

$=(\prod _{i=1}^{n}E[e^{\lambda (Z_i-E[Z_i])}])e^{-\lambda nt}$

$\le (\prod _{i=1}^n{e}^{\frac{{\lambda }^2(b-a{)}^2}{8})})e^{-\lambda nt}$ الگو:پایان چپ چین که نامساوی آخر از لم هوفدینگ نتیجه شد. با بازنویسی و کمینه کردن نامساوی آخر روی $\lambda \ge 0$ خواهیم داشت:

الگو:چپ چین

$P(\frac{1}{n}\sum _{i=1}^n(Z_i-E[Z_i])\ge t)\le mi{n}_{\lambda \ge 0}exp(\frac{n{\lambda }^2(b-a{)}^2}{8}-\lambda nt)=exp(-\frac{2n{t}^2}{(b-a{)}^2})$ الگو:پایان چپ چین که همان نابرابری هوفدینگ است.

کاربرد ها

• قانون اعداد بزرگ

قانون اعداد بزرگ یکی از معروف ترین نتیجه در نظریه احتمالات است. این قانون بیان میکند که در صورتی که یک آزمایش را به n بار انجام دهیم و از نتایج آن میانگین بگیریم، این میانگین در حد n به سمت بینهایت به امید ریاضی متغیر تصادفی میل میکند.این قانون توسط نابرابری هوفدینگ (و البته نابرابری های ساده دیگر) اثبات میشود.

فرض کنید $\bar{X}=\frac{X_1+...+X_n}{n}$ در این صورت خواهیم داشت:

الگو:چپ چین

$\underset{n\to \mathrm{\infty }}{\lim }P(-t\le \bar{X}-E[X]\le t)=$

$=\underset{n\to \mathrm{\infty }}{\lim }(1-P(\bar{X}-E[X]\ge t)-P(\bar{X}-E[X]\le -t))\ge li{m}_{n\to \mathrm{\infty }}(1-exp(-\frac{2n{t}^2}{(b-a{)}^2})-exp(-\frac{2n{t}^2}{(b-a{)}^2}))=1$

$\to \underset{n\to \mathrm{\infty }}{\lim }P(-t\le \bar{X}-E[X]\le t)=1$

الگو:پایان چپ چین با توجه به اینکه نامساوی بدست آمده به ازای همهٔ مقادیر مثبت t برقرار است پس می‌توان نتیجه گرفت که حد $\bar{X}$ برابر $E[X]$ خواهد شد.

• بازه ی اطمینان

نابرابری هوفدینگ ابزاری کارآمد برای آنالیز تعداد نمونه های مورد نیاز برای دستیابی به بازه اطمینان است. از نابرابری هوفدینگ داریم:

الگو:چپ چین $P(\bar{X}-E[X]\ge t)\le e^{-2n{t}^2}$ الگو:پایان چپ چین و به‌طور متقارن: الگو:چپ چین $P(\bar{X}-E[X]\le -t)\le e^{-2n{t}^2}$ الگو:پایان چپ چین و با ترکیب دو معادلهٔ بالا می‌توانیم نا معادلهٔ دو طرفهٔ زیر را بدست آوریم: الگو:چپ چین $P(\overline{|}X-E[X]|\ge t)\le 2e^{-2n{t}^2}$ الگو:پایان چپ چین این احتمال می‌تواند به عنوان میزان بزرگی $\alpha$ (احتمال به وجود آمدن خطا) برای بازهٔ اطمینان حول $E[\bar{X}]$ با اندازهٔ $2t$ در نظر گرفته شود: الگو:چپ چین $\to \alpha =P(\bar{X}\notin [E[\bar{X}]-t,E[\bar{X}]+t])\le 2e^{-2n{t}^2}$ الگو:پایان چپ چین که با حل معادلهٔ بالا بر حسب $n$ خواهیم داشت: الگو:چپ چین $n\le \frac{log(2/\alpha )}{2t^2}$ الگو:پایان چپ چین بنابراین متوجه شدیم که برای دستیابی به بازه اطمینان $(1-\alpha )$، $E[\bar{X}]\pm t$ نیاز به حداقل $\frac{log(2/\alpha )}{2t^2}$ نمونه داریم.

منابع

• الگو:یادکرد ویکی