סיבוכיות ראדמאכר

בתורת הלמידה, **סיבוכיות ראדמאכר**, הקרויה על שמו של הנס ראדמאכר, מודדת את העושר של קבוצת וקטורים ב- \mathbb{R}^m או של מחלקת פונקציות עם ערכים ממשיים. בדרך כלל משתמשים בסיבוכיות ראדמאכר כדי לחקור מחלקות של פונקציות עם ערכים ב - \{-1,1\}, כלומר בעיות סיווג עם שתי מחלקות. אינטואיטיבית, ככל שעושר של קבוצה של וקטורים או של מחלקה של פונקציות גבוה יותר, כך סיבוכיות ראדמאכר תהיה גבוהה יותר.

## הגדרות
### סיבוכיות ראדמאכר של קבוצה
בהינתן קבוצה A \subset \mathbb{R}^m, סיבוכיות ראדמאכר של A מוגדרת באופן הבא:

R(A):=
\frac{1}{m}\mathbb{E}_{\sigma}
\left[ \sup_{a \in A}{\sum_{i=1}^m \sigma_i a_i} \right]

כאשר a=\left( a_1, \dots, a_m \right), ו \sigma_i הם משתנים מקריים בלתי תלויים שמתפלגים בהתפלגות ראדמאכר:

P(\sigma_i=1)=P(\sigma_i=-1)=\frac{1}{2}.

### סיבוכיות ראדמאכר של משפחת פונקציות
יהיו מרחב Z והתפלגות D עליו. נניח ש - S=\{z_1, \dots, z_m\} היא קבוצה שנדגמה מ - Z באופן בלתי תלוי לפי ההתפלגות D. בנוסף, תהי \mathcal{F} משפחת פונקציות מהצורה f:Z\to\mathbb{R}.

#### סיבוכיות ראדמאכר אמפירית
סיבוכיות ראדמאכר האמפירית של \mathcal{F} מוגדרת להיות:

\hat{R}_m(\mathcal{F})
:=
\mathbb{E}_{\sigma}
\left[ \sup_{f \in \mathcal{F}}{\frac{1}{m}\sum_{i=1}^m \sigma_i f(z_i)} \right]

כאשר גם כאן, \sigma_i בלתי תלויים ומתפלגים לפי התפלגות ראדמאכר.

אפשר גם להסתכל על \mathcal{F} \circ S := \{ (f(z_1), \dots, f(z_m)) : f \in \mathcal{F} \} כקבוצה ב - \mathbb{R}^m ולקבל שההגדרה של סיבוכיות ראדמאכר של קבוצה מכלילה את הגדרת סיבוכיות ראדמאכר אמפירית.

#### סיבוכיות ראדמאכר
סיבוכיות ראדמאכר של \mathcal{F} מוגדרת להיות:

{R}_m(\mathcal{F})
:=
\mathbb{E}_{S \sim D^m} \left[ \hat R_m\left( \mathcal{F} \right) \right]

## דוגמאות

# עבור A = \{\left( a,b \right)\} \subset \mathbb{R}^2, מתקיים: R\left(A \right)=\frac{1}{2}\mathbb{E}_\sigma \left[ a\sigma_1 + b\sigma_2 \right]=
a\mathbb{E}_\sigma \left[ \sigma_1 \right] + b\mathbb{E}_\sigma \left[ \sigma_2 \right]=0
# עבור S=\{x_1\} \subset \mathbb{R} ו - \mathcal{F} = \{ f(x)=c : c \in [0,1] \}, נקבל: \hat{R}_1(\mathcal{F})=
\mathbb{E}_{\sigma}
\left[ \sup_{f \in \mathcal{F}}{\sigma f(x_1)} \right]=
\mathbb{E}_{\sigma} \left[ \sup_{c\in[0,1]}{\sigma c} \right]=
\frac{1}{2}\sup_{c\in[0,1]}{c} + \frac{1}{2}\sup_{c\in[0,1]}{-c}=
\frac{1}{2}

## תכונות
לסיבוכיות ראדמאכר יש מספר תכונות שעוזרות בחישוב או במציאת חסם:

# לכל A \subset \mathbb{R}^m, c \in \mathbb{R} ו - a_0 \in \mathbb{R}^m מתקיים R\left( \{ ca + a_0 : a \in A \} \right) \leq |c|R\left( A \right).
# לכל A \subset \mathbb{R}^m, הקמור של A הוא בעל אותה סיבוכיות ראדמאכר כמו של A.
# (למת מסאר) תהי A = \{ a_1, \dots, a_N \} \subset \mathbb{R}^m ו - \bar{a}=\frac{1}{N}\sum_{i=1}^{N}{a_i}, אז מתקיים R\left( A \right) \leq \max_{a \in A} \|a-\bar{a}\| \frac{\sqrt{2\log{N}}}{m}.
# (למת הכיווץ) לכל i \in [m], תהיינה \phi_i:\mathbb{R}\to\mathbb{R} פונקציות \rho-ליפשיץ, כלומר לכל \alpha,\beta \in \mathbb{R} מתקיים |\phi_i(\alpha)-\phi_i(\beta)| \leq \rho |\alpha - \beta|. עבור a \in \mathbb{R}^m נסמן \phi(a) := (\phi_1(a_1), \dots, \phi_m(a_m)) ו - \phi \circ A := \{ \phi(a) : a \in A \}, אז מתקיים R\left( \phi \circ A \right) \leq \rho R\left( A \right).

## שימושים
### לחסום את תוחלת היציגות
נגדיר את היציגות של קבוצה S \subset \mathbb{R}^n
 סופית של דגימות בלתי תלויות מהתפלגות D
, ביחס למשפחת פונקציות \mathcal{F}
, על ידי

\text{Rep}_D(\mathcal{F}, S) := \sup_{f \in \mathcal{F}} \left( L_D(f) - L_S(f) \right)



כאשר L_D(f) = \mathbb{E}_{z \sim D} \left[ f(z) \right], \quad L_S(f) = \frac{1}{m} \sum_{i=1}^{m} f(z_i)

 עבור f \in \mathcal{F}
.

ניתן לחסום את תוחלת היציגות על ידי החסם הבא:

\mathbb{E}_{S \sim D^m} \left[ \text{Rep}_D(\mathcal{F}, S) \right] \leq 2 \mathbb{E}_{S \sim D^m} \, \hat{R}_{m}(\mathcal{F}) = 2R_{m}(\mathcal{F})

### לחסום את שגיאת ההכללה
נניח ש - Z
 קבוצה סופית של זוגות מהצורה (\bold{x}, y)
, כאשר \bold{x}
 זה דגימה ו - y
 זה הלייבל של \bold{x}
, ונניח ש - \ell : \mathcal{F} \times Z \to \mathbb{R}
 היא פונקציית loss, כך שלכל z \in Z
 ו - f \in \mathcal{F}
 מתקיים |\ell(f,z)| \leq c
. אזי, בהסתברות 1-\delta לפחות, לכל f \in \mathcal{F}
 מתקיים:

# L_D(f) - L_S(f)
\le
2\,\mathbb{E}_{S'\sim D^m}\!\hat{R}_{m}(\ell\circ \mathcal{F} \circ S')
+ c\sqrt{\frac{2\log(\frac{2}{\delta})}{m}}


# L_D(f) - L_S(f)
\le
2\,\hat{R}_{m}(\ell\circ \mathcal{F} \circ S)
+4c\sqrt{\frac{2\log(\frac{4}{\delta})}{m}}

מהחסם האחרון אפשר לראות שאם הגודל \hat{R}_{m}(\ell\circ \mathcal{F} \circ S) קטן, שגיאת ההכללה L_D לא תהיה רחוקה מדי משגיאת האימון L_S. במקרה של החסם האחרון, משתמשים ב - S גם בזמן הלמידה וגם בזמן בדיקת איכות הלמידה.

## חסמים על הסיבוכיות
### חסמים הקשורים למחלקות ליניאריות
נרצה לחסום את סיבוכיות ראדמאכר של מחלקות הפונקציות הבאות:

\mathcal{H}_1 = \{x \mapsto \langle w,x \rangle : \|w\|_1 \leq 1 \} ו - \mathcal{H}_2 = \{x \mapsto \langle w,x \rangle : \|w\|_2 \leq 1 \}.

עבור \mathcal{H}_2, יש לנו את הלמה הבאה:

תהי S = \{ x_1, \dots, x_m \} קבוצה של וקטורים במרחב הילברט. נסמן \mathcal{H}_2 \circ S := \{ (\langle w,x_1 \rangle, \dots, \langle w,x_m \rangle) : \|w\|_2 \leq 1 \}, אז מתקיים R \left( \mathcal{H}_2 \circ S \right) \leq \frac{\max_i{\|x_i\|_2}}{\sqrt{m}}.

ההוכחה מתבססת על שימוש באי-שוויון קושי-שוורץ ובאי-שוויון ינסן.

עבור \mathcal{H}_1 יש לנו למה דומה:

תהי S = \{ x_1, \dots, x_m \} קבוצה של וקטורים ב - \mathbb{R}^n, אז מתקיים R \left( \mathcal{H}_1 \circ S \right) \leq \max_i{\|x_i\|_\infty} \sqrt{\frac{2\log{2n}}{m}}.

פה ההוכחה מתבססת על אי-שוויון הלדר ולמת מסאר.

### חסמים הקשורים למספר כיסוי של קבוצה
#### מספר כיסוי של קבוצה
תהי A \subset \mathbb{R}^m. עבור \varepsilon > 0, נקרא ל - B \subset A \varepsilon-רשת של A אם לכל a \in A קיים b \in B כך ש - \|a-b\| . מספר הכיסוי N \left( A,\varepsilon \right) מוגדר להיות העוצמה המינימלית של \varepsilon-רשת של A.

#### חסם על הסיבוכיות
אפשר לחסום את סיבוכיות ראדמאכר של קבוצה A \subset \mathbb{R}^m על ידי הלמה הבאה:

נסמן c := \min_{\bar{a}}\max_{a \in A}{\|a-\bar{a}\|}. אז לכל שלם M > 0 מתקיים

R \left( A \right) \leq
\frac{c2^{-M}}{\sqrt{m}} +
\frac{6c}{m} \sum_{k=1}^{M}{2^{-k}}\sqrt{\log{N\left( A,c2^{-k} \right)}}

בנוסף, אם נניח שיש \alpha, \beta > 0 כך ש לכל k \geq 1 מתקיים \sqrt{\log{N \left( A,c2^{-k} \right)}} \leq \alpha + \beta k, אז על ידי לקיחת M לאינסוף נקבל

R \left( A \right) \leq \frac{6c}{m} \left( \alpha + 2\beta \right), כאשר השתמשנו בעובדה ש - \sum_{k=1}^{\infty}{2^{-k}}=1 ו - \sum_{k=1}^{\infty}{k2^{-k}}=2.

## סיבוכיות גאוסית
### הגדרה
עבור קבוצה K \subset \mathbb{R}^d, סיבוכיות גאוסית מוגדרת באופן הבא:

\mathcal{G}(K) := \mathbb{E}_\epsilon \left[ \sup_{\theta \in K}{\langle \epsilon, \theta \rangle} \right]

כאשר \epsilon \sim \mathcal{N} \left( 0, I_d \right).

ניתן לראות שההגדרה מאוד דומה להגדרה של סיבוכיות ראדמאכר של קבוצה, כאשר השינוי העיקרי הוא ש - \epsilon הוא וקטור גאוסי ולא וקטור שרכיביו מתפלגים לפי התפלגות ראדמאכר. ניתן לחשב את הסיבוכיות הגאוסית של משפחת פונקציות באופן דומה לסיבוכיות ראדמאכר.

### דוגמאות
להלן מספר דוגמאות בסיסיות לחישוב סיבוכיות גאוסית של קבוצה:
# עבור קבוצה סופית, K = \{ \theta_1, \dots, \theta_N \}, מתקיים \mathcal{G}(K) = \mathbb{E} \left[ \max_{\theta \in K}{\langle \epsilon, \theta \rangle} \right]
\asymp \sqrt{\log{N}}.
# עבור הקבוצה K = \{ \theta | \|\theta \|_2 \leq 1 \} \subset \mathbb{R}^d מתקיים \mathcal{G}(K) = \mathbb{E} \left[ \max_{\|\theta\|_2 \leq 1}{\langle \epsilon, \theta \rangle} \right] =
\mathbb{E} \left[ \|\epsilon\|_2 \right] \leq \sqrt{d}.

### קשר לסיבוכיות ראדמאכר
עבור קבוצה K \subset \mathbb{R}^d, בהתאם להגדרות בעמוד, מתקיים:

\frac{\mathcal{G}(K)}{2 \sqrt{\log{d}}} \leq dR(K) \leq \sqrt{\frac{\pi}{2}}\mathcal{G}(K)

אז אפשר לומר שסיבוכיות גאוסית וסיבוכיות ראדמאכר (ליתר דיוק dR(K)) שקולות עד כדי גורם מסדר \sqrt{\log{d}}.

## הערות שוליים

קטגוריה:למידת מכונה