نامساوی مک‌دیارمید

نامساوی مک‌دیارمید (McDiarmid Inequality):

این نامساوی یکی از نامساوی‌های احتمالاتی است که در تحلیل الگوریتم‌ها و مسائل مرتبط با حوزه تئوری احتمالات و آمار به کار می‌رود. این نامساوی توسط کلی مک‌دیارمید ارائه شده‌است و از آن برای تخمین احتمالات و حدود بسیار بالای احتمالاتی استفاده می‌شود.

نامساوی مک‌دیارمید به زبان ساده:

نامساوی مک‌دیارمید یکی از مفاهیم اساسی ریاضیات است که در حل مسائل به کار می‌رود. این نامساوی به صورت عمومی به شکل زیر است:

$$ax+b<c$$

در این نامساوی $a\neq 0$ و $a,b,c\in \mathbb {R}$

مثال: برای حل نامعادله زیر و بدست‌ آوردن مقادیر ممکن برای $x$

$$2x+3<7$$

ابتدا از دو طرف نامعادله $3$ واحد کم میکنیم:

$$2x+3-3<7-3$$$$\Downarrow$$$$2x<4$$

سپس برای حذف ضریب $x$، دو طرف نامعادله را در عبارت ${\frac {1}{2}}$ ضرب میکنیم:

$${\frac {1}{2}}\times 2x<{\frac {1}{2}}\times 4$$$$\Downarrow$$$$x<2$$$$\Downarrow$$ $$x\in (-\infty ,2)$$

پس مقادیر ممکن برای $x$ تمام اعداد حقیقی کوچک تر از $2$ میباشد.

نامساوی مک‌دیارمید یکی از ابزار‌های مهم در تحلیل و حل مسائل ریاضیاتی و کاربرد‌های علمی است.

معادلات مک‌دیارمید (McDiarmid Equations):

این معادلات به شیوه‌ای مختصر در مورد رفتار دینامیکی و توزیع‌هایی که در حالت تعادلی در معادلات دیفرانسیلی ظاهر می‌شوند توضیح می‌دهد. این معادلات معمولاً در زمینه‌های مختلفی از علوم مورد استفاده قرار می‌گیرند. از جمله فیزیک، مهندسی و بیولوژی.

معادلات مک‌دیارمید در موارد مختلف علوم از جمله فیزیک، مهندسی، اقتصاد و بیولوژی به کار می‌روند. این معادلات برای توصیف رفتار‌هایی مانند انتقال حرارت، جریان سیالات، دینامیک سیالات و بسیاری موارد دیگر استفاده می‌شوند.

معمولاً معادلات مک‌دیارمید به صورت یک معادله دیفرانسیلی خطی با ضرایب متغیرهای زمان و فضا و معمولاً در ابعاد چندین متغیره بیان می‌شوند. این معادلات می‌توانند به صورت تحلیلی یا عددی حل شوند، و معمولاً در موارد پیچیده، روش‌های تقریبی مانند روش المان محدود برای حل آن‌ها استفاده می‌شود.

برای مطالعه بیشتر در مورد معادلات مک‌دیارمید، می‌توانید به کتب مرجع در زمینه فیزیک و ریاضیات، منابع دانشگاهی یا مقالات علمی در این زمینه مراجعه کنید.

توضیح کلی درمورد موضوع

در بیشتر مواقع ما نیاز داریم که نشان دهیم که یک quantity رندوم $f(Z_{1},...,Z_{n})$ نزدیک میانگینش هست. برای همین است که ما یک نتیجه به شکل زیر می‌خواهیم:

$P(|f(Z_{1},...,Z_{n})-\mu (f)|>\epsilon )<\delta$

اینگونه نتایج با عنوان concentration of measure شناخته می‌شوند. این نتایج برای ایجاد تضمین‌های عملکرد بسیاری از الگوریتم‌ها اساسی هستند. در واقع برای تئوری یادگیری آماری، ما به باند یکنواخت به فرم زیر نیاز داریم:

$P(\sup _{f\in \digamma }|f(Z_{1},...,Z_{n})-\mu (f)|>\epsilon )<\delta$

روی یک کلاس از توابع $\digamma$ .

در قضیه احتمال و تئوری علوم کامپیوتر نامساوی McDiarmid یک نوع نامساوی concentration هست که کران بالایی برای انحراف بین نمونه‌های آزمایش که به صورت متغیرهای تصادفی مستقل هستند و امید ریاضی تابع مشخص ارائه می‌دهد.

این نامساوی روی توابعی که bounded differences property هستند تعریف می‌شود.

معرفی مفاهیم اصلی موضوع

bounded differences property

از جمله مفاهیم اصلی در این موضوع می‌توان به مفهوم bounded differences property اشاره کرد. وقتی یک تابع این ویژگی را برای $(c_{1},...,c_{n})$ دارد. یعنی برای هر $i=1,...,n$ و هر $(x_{1},...x_{n}),(x_{1}',...,x_{n}')\in X^{n}$ که تنها تفاوتشان در جمله i ام هست داشته باشیم:

$|f(x_{1},...x_{n})-f(x_{1}',...,x_{n}')|<c_{i}$

در اینصورت می‌گوییم این تابع bounded differences property-$(c_{1},...,c_{n})$ هست.

نامساوی concentration

مفهوم دیگری که در اینجا داریم مفهوم concentration inequalities هست. اینگونه نامساوی‌ها یک کرانی درمورد اینکه یک متغیر تصادفی چگونه از یک مقدار که به‌طور معمول امید ریاضی هست انحراف دارد. در قانون اعداد بزرگ جمع متغیر تصادفی‌های مستقل به احتمال زیاد نزدیک به امید ریاضی آنها است. البته نتایج اخیر نشان می‌دهد که این رفتار با تابع‌های دیگری از متغیرهای تصادفی نیز به اشتراک گذاشته شده‌است.

قضایا ی اصلی مرتبط با این موضوع

نامساوی McDiarmid

نامساوی McDiarmid به صورت زیر تعریف می‌شود:

فرض کنید $X_{1},...,X_{n}\in X$ متغییرهای تصادفی مستقل باشند و $f:X^{n}\rightarrow R$ تابعی با bounded differences property-$(c_{1},...,c_{n})$ باشد. آنگاه برای هر t بزرگتر از صفر داریم:

$P(f(x_{1},...x_{n})-E(f(x_{1},...x_{n}))\geq t)\leq \exp(-{\frac {2t^{2}}{\sum _{i=1}^{N}c_{i}^{2}}})$

حال به اثبات این قضیه می پردازیم.

ابتدا $V_{i}$ را به صورت زیر تعریف می کنیم:

$V_{i}=E(f|X_{1},...,X_{i})-E(f|X_{1},...,X_{i-1})$

حال با استفاده از امید شرطی به راحتی می توان اثبات کرد که $E(V_{i})=0$ و همچنین داریم:

$\textstyle \sum _{i=1}^{N}\displaystyle V_{i}=E(f|X_{1},...,X_{N})-E(f)=f(X_{1},...,X_{N})-E(f)$

حال دو کران بالا و پایین برای $V_{i}$ تعریف می کنیم.

$L_{i}={\underset {x}{\inf }}E(f|X_{1},...,X_{i-1},x)-E(f|X_{1},...,X_{i-1})$

$U_{i}={\underset {x}{\sup }}E(f|X_{1},...,X_{i-1},x)-E(f|X_{1},...,X_{i-1})$

میدانیم که $U_{i}\geq V_{i}\geq L_{i}$ هست. حال با توجه به اینکه $X_{i}$ها مستقل هستند داریم: $U_{i}-L_{i}\leq c_{i}$

حال همانطور که در نامساوی Hoeffding داریم :

$P(f(x_{1},...x_{n})-E(f(x_{1},...x_{n}))\geq t)\leq {\underset {s>0}{\inf }}e^{-st}E(\prod _{i=1}^{N}e^{sV_{i}})$

در نتیجه با استفاده از لم Hoeffding داریم:

$E(\prod _{i=1}^{N}e^{sV_{i}})=EE(\prod _{i=1}^{N-1}e^{sV_{i}}e^{sV_{N}}|X_{1},...,X_{N-1})=E(\prod _{i=1}^{N-1}e^{sV_{i}}E(e^{sV_{N}}|X_{1},...,X_{N-1}))\leq E(\prod _{i=1}^{N-1}e^{sV_{i}})e^{\tfrac {s^{2}c_{N}^{2}}{8}}\Longrightarrow \leq e^{\tfrac {s^{2}\sum _{i=1}^{N}c_{i}^{2}}{8}}$می دانیم برای کمترین بودن باید مشتق توان e برابر با صفر شود پس درنتیجه داریم :

$-t+2s\textstyle \sum _{i=1}^{N}{\tfrac {c_{i}^{2}}{8}}\displaystyle =0\rightarrow s={\tfrac {4t}{\sum _{i=1}^{N}c_{i}^{2}}}$

حال با جایگذاری s در نامساوی به‌دست آمده نامساوی McDiarmid اثبات می شود.

لم Hoeffding

فرض کنید X متغیر تصادفی باشد که امید ریاضی آن صفر باشد و $a\leq X\leq b$ باشد. آنگاه داریم:

$E(e^{t}X)\leq e^{\frac {t^{2}(b-a)^{2}}{8}}$

حال به اثبات آن می پردازیم:

چون X کران بالا و کران پایین دارد پس می توان آن را به شکل ترکیب خطی a,b نوشت.

$X=\alpha b+(1-\alpha )a\rightarrow \alpha ={\frac {X-a}{b-a}}$

طبق نامساوی ینسن داریم:

$\Rightarrow e^{tX}\leq \alpha e^{tb}+(1-\alpha )e^{ta}$

$E{e^{tX}}\leq {\frac {-a}{b-a}}e^{tb}+{\frac {b}{b-a}}e^{ta}=e^{g(u)}$

که u و تابع g(u) را به شکل زیر تعریف می کنیم:

$u=t(b-a),g(u)=-\gamma u+\log(1-\gamma +\gamma e^{u}),\gamma ={\frac {-a}{b-a}}$

$g(0)=g'(0)=0,g''(0)\leq {\frac {1}{4}}\forall u>0$

با استفاده از قضیه تیلور می دانیم:

$\exists \epsilon \in (0,u):g(u)=g(0)+ug'(0)+{\frac {u^{2}}{2}}g''(\epsilon )={\frac {u^{2}}{2}}g''(\epsilon )\leq {\frac {u^{2}}{8}}={\frac {t^{2}(a-b)^{2}}{8}}$

$\Longrightarrow E(e^{tX})\leq e^{g(u)}\leq e^{\frac {t^{2}(b-a)^{2}}{8}}\blacksquare$

صورت‌های دیگر نامساوی McDiarmid

نامساوی McDiarmid برای توزیع‌های unbalanced

فرض کنید $X_{1},...,X_{n}\in X$ متغییرهای تصادفی مستقل از یک توزیع باشند که یک مقدار مشخص $X_{0}\in X$ با احتمال p وجود نداشته باشد و $f:X^{n}\rightarrow R$ تابعی با bounded differences property-$(c_{1},...,c_{n})$ باشد. آنگاه برای هر t بزرگتر از صفر داریم:

$P(f(x_{1},...x_{n})-E(f(x_{1},...x_{n}))\geq t)\leq 2\exp(-{\frac {t^{2}}{2p(2-p)\sum _{i=1}^{N}c_{i}^{2}+{\frac {2}{3}}t\max c_{i}}})$

نامساوی McDiarmid برای نورم sub-Gaussian

فرض کنید $X_{1},...,X_{n}\in X$ متغییرهای تصادفی مستقل باشند و $f:X^{n}\rightarrow R$ یک تابع باشد که $f_{k}(X)$همان kامین ورژن centered conditional از f باشد. $\lVert .\rVert _{\psi }$ را نورم sub-Gaussian یک متغیر تصادفی در نظر بگیرید. آنگاه برای هر t بزرگتر از صفر داریم:

$P(f(x_{1},...x_{n})-E(f(x_{1},...x_{n}))\geq t)\leq \exp(-{\frac {t^{2}}{32e\lVert \sum \lVert f_{k}(X)\rVert _{\psi }^{2}\rVert _{\bar {\infty }}}})$

نامساوی McDiarmid برای نورم sub-Exponential

فرض کنید $X_{1},...,X_{n}\in X$ متغییرهای تصادفی مستقل باشند و $f:X^{n}\rightarrow R$ یک تابع باشد که $f_{k}(X)$همان kامین ورژن centered conditional از f باشد. $\lVert .\rVert _{\psi }$ را نورم sub-Exponential یک متغیر تصادفی در نظر بگیرید. آنگاه برای هر t بزرگتر از صفر داریم:

$P(f(x_{1},...x_{n})-E(f(x_{1},...x_{n}))\geq t)\leq \exp(-{\frac {t^{2}}{4e^{2}\lVert \sum \lVert f_{k}(X)\rVert _{\psi }^{2}\rVert _{\bar {\infty }}+2te\max \lVert \lVert f_{k}(X)\rVert _{\psi }\rVert _{\infty }}})$

نامساوی Hoeffding (حالت خاص برای تابع f)

$S_{n}=\sum _{i=1}^{n}X_{i}$ را در نظر بگیرید و فرض کنید $X_{1},...,X_{n}\in X$ متغییرهای تصادفی مستقل باشند. آنگاه برای s بزرگتر از صفر داریم:

$P(S_{n}-E(S_{n})\geq t)=P(\exp {s(S_{n}-E(S_{n}))\geq e^{st}})\leq e^{-st}E(e^{s(S_{n}-E(S_{n}))})=e^{-st}\prod E(e^{s(X_{i}-E(X_{i}))})$

مثال‌هایی از مسائل کلاسیک

از مثال‌های کلاسیک این نامساوی می‌توان به نامساوی Hoeffding که در بالا آن را بیان کردیم اشاره نمود.

مثال دیگری که می‌توان از حالت خاص unbalanced این نامساوی داشت استفاده آن در یک تابع در گراف‌ها هنگام ارزیابی بر روی گراف‌های تصادفی پراکنده‌است زیرا در یک گراف تصادفی پراکنده احتمال نبودن یک یال خاص بسیار بیشتر از وجود آن است.

کاربردهایی از قضایای این موضوع در حل سایر مسائل

از کاربردهای سایر بخش‌ها در این بخش می‌توان به entropy اشاره کرد. درواقع وقتی ما می‌خواهیم از حالت جمع (در نامساوی Hoeffding) به حالت تابع general از متغیرهای تصادفی مستقل نامساوی را extend کنیم از متد entropy استفاده می‌کنیم.

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

از این نامساوی‌ها در برخی از مسایل استاندارد در تیوری یادگیری و vector valued concentration و تعمیم PCA و روش پیچیدگی Rademacher استفاده می‌شود. و البته در مرور زمان از اینها برای تعمیم کران‌ها در شرایط مختلف نیز اثبات شد.

همچنین می‌توان نشان داد با استفاده از این نامساوی‌ها که نامساوی Kontorovich که تمرکز بر محصولات فضاهای احتمال متریک زیر گاوسی را توصیف می‌کند و کاربردهایی برای پایداری الگوریتم دارد می‌تواند به حالت زیر نمایی نیز بسط پیدا کند.

منابع

[۱] [۲] [۳] [۴] [۵] [۶]