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

در نظریه احتمال، نابرابری هوفدینگ (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₁, … , X_n.. , X_n متغیر تصادفی مستقل محدود به بازه [۰٬۱]: ۰ ≤ X_i ≤ ۱ باشند و ${\overline {X}}$ را به صورت زیر تعریف کنیم:

${\overline {X}}={\frac {1}{n}}(X_{1}+\cdots +X_{n}).$

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

${\begin{aligned}\mathbb {P} ({\overline {X}}-\mathrm {E} [{\overline {X}}]\geq t)\leq e^{-2nt^{2}}\end{aligned}}$

نابرابری بعدی در اصل تعمیم نابرابری اول است. اگر X₁, … , X_n.. , X_n متغیر تصادفی مستقل و $a_{i}\leq X_{i}\leq b_{i}$ باشند این بار خواهیم داشت:

${\begin{aligned}\mathbb {P} \left({\overline {X}}-\mathrm {E} \left[{\overline {X}}\right]\geq t\right)&\leq \exp \left(-{\frac {2n^{2}t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right)\\\mathbb {P} \left(\left|{\overline {X}}-\mathrm {E} \left[{\overline {X}}\right]\right|\geq t\right)&\leq 2\exp \left(-{\frac {2n^{2}t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right)\end{aligned}}$

اثبات

قضیه را برای $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}])\geq t)\leq exp(-{\frac {2nt^{2}}{(b-a)^{2}}})$

و

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

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

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

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

به ازای هر $\lambda \in \mathbb {R}$

$E[exp(\lambda (Z-E[Z]))]\leq exp({\frac {\lambda ^{2}(b-a)^{2}}{8}})$

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

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

$\leq 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}$

$\leq (\prod _{i=1}^{n}e^{{\frac {\lambda ^{2}(b-a)^{2}}{8}})})e^{-\lambda nt}$

که نامساوی آخر از لم هوفدینگ نتیجه شد. با بازنویسی و کمینه کردن نامساوی آخر روی $\lambda \geq 0$ خواهیم داشت:

$P({\frac {1}{n}}\sum _{i=1}^{n}(Z_{i}-E[Z_{i}])\geq t)\leq min_{\lambda \geq 0}exp({\frac {n\lambda ^{2}(b-a)^{2}}{8}}-\lambda nt)=exp(-{\frac {2nt^{2}}{(b-a)^{2}}})$

که همان نابرابری هوفدینگ است.

کاربرد ها

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

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

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

$\lim _{n\to \infty }P(-t\leq {\overline {X}}-E[X]\leq t)=$

$=\lim _{n\to \infty }(1-P({\overline {X}}-E[X]\geq t)-P({\overline {X}}-E[X]\leq -t))\geq lim_{n\to \infty }(1-exp(-{\frac {2nt^{2}}{(b-a)^{2}}})-exp(-{\frac {2nt^{2}}{(b-a)^{2}}}))=1$

$\rightarrow \lim _{n\to \infty }P(-t\leq {\overline {X}}-E[X]\leq t)=1$

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

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

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

$P({\overline {X}}-E[X]\geq t)\leq e^{-2nt^{2}}$

و به‌طور متقارن:

$P({\overline {X}}-E[X]\leq -t)\leq e^{-2nt^{2}}$

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

$P({\overline {|}}{X}-E[X]|\geq t)\leq 2e^{-2nt^{2}}$

این احتمال می‌تواند به عنوان میزان بزرگی $\alpha$ (احتمال به وجود آمدن خطا) برای بازهٔ اطمینان حول $E[{\overline {X}}]$ با اندازهٔ $2t$ در نظر گرفته شود:

$\rightarrow \alpha =P({\overline {X}}\notin [E[{\overline {X}}]-t,E[{\overline {X}}]+t])\leq 2e^{-2nt^{2}}$

که با حل معادلهٔ بالا بر حسب $n$ خواهیم داشت:

$n\leq {\frac {log(2/\alpha )}{2t^{2}}}$

بنابراین متوجه شدیم که برای دستیابی به بازه اطمینان $(1-\alpha )$، $E[{\overline {X}}]\pm t$ نیاز به حداقل ${\frac {log(2/\alpha )}{2t^{2}}}$ نمونه داریم.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «نابرابری هوفدینگ». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۶ اسفند ۱۳۹۴.