חסם הופדינג
בתורת ההסתברות, חסם הופדינג, על שמו של וסילי הופדינג (Hoeffding), הוא חסם עליון על ההסתברות שסכום של משתנים מקריים יהיה שונה מהתוחלת שלו.
חסם הופדינג הוא תוצאה של אי שוויון ברנשטיין.
הגדרה פורמלית
יהיו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1 \dots X_n } משתנים מקריים בלתי תלויים. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i \in [a_i,b_i] } בהסתברות 1. אזי הממוצע שלהם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bar{X}_n = \frac{1}{n}\sum_{i=1}^n X_i } מקיים לכל t חיובי את האי-שוויונות הבאים (Hoeffding 1963):
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr(\bar{X}_n - \mathrm{E}[\bar{X}_n] \geq t) \leq \exp \left( - \frac{2\,n^2\,t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)\!}
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr(|\bar{X}_n - \mathrm{E}[\bar{X}_n]| \geq t) \leq 2\exp \left( - \frac{2\,n^2\,t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)\! }
שימושים
משמעות החסם היא שההסתברות שמדגם כלשהו מתוך הסתברות, לא יהיה "מדגם מייצג", קטנה באופן מעריכי בגודל המדגם. לחסם זה חשיבות רבה בתחום של למידת מכונה, מכיוון שהוא נותן אינדיקציה לגבי גודל המדגם שדרוש כדי ללמוד על התפלגות.
ראו גם
לקריאה נוספת
חסם הופדינג33443990Q1622794