Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
courses:b4m36smu [2026/05/26 12:51] – [Question 8. (4 points)] jpelccourses:b4m36smu [2026/05/27 09:37] (current) – [Other COLT] jpelc
Line 365: Line 365:
  
 % Layer Box % Layer Box
-\draw[thick, dashed] (-3.5, 2.5) rectangle (3.5, 7.5); +\draw[thick, dashed] (-4.0, 2.5) rectangle (3.5, 10.5); 
-\node at (4.5, 5) [font=\sffamily\bfseries\Large] {$\times N$ Layers};+\node at (5.0, 7) [font=\sffamily\bfseries\Large] {$\times N$ Layers};
  
 \end{tikzpicture} \end{tikzpicture}
Line 836: Line 836:
 For $VC(\mathcal{H}) \geq n$: For $VC(\mathcal{H}) \geq n$:
  
-  - $x_1 = 0 \quad 1 \quad 1 \quad \dots \quad 1$ +  * $x_1 = 0 \quad 1 \quad 1 \quad \dots \quad 1$ 
-  - $x_2 = 1 \quad 0 \quad 1 \quad \dots \quad 1$ +  * $x_2 = 1 \quad 0 \quad 1 \quad \dots \quad 1$ 
-  - $x_n = 1 \quad 1 \quad 1 \quad \dots \quad 0$+  * $x_n = 1 \quad 1 \quad 1 \quad \dots \quad 0$
  
 $\mathcal{I} \subseteq \left[1, 2, \dots n\right]$ $\mathcal{I} \subseteq \left[1, 2, \dots n\right]$
Line 1307: Line 1307:
  
 ++++ Adapt Winnow / Halving algorithm, define $\mathcal{H}$, define mistake bound learning | ++++ Adapt Winnow / Halving algorithm, define $\mathcal{H}$, define mistake bound learning |
-MB-learning (or online learning) is bounded by the number of mistakes which it can do while learning, that is $\leq \text{poly}(n)$.+M-B-learning (or online learning) is bounded by the number of mistakes which it can do while learning, that is $\leq \text{poly}(n)$.
  
 $\mathcal{H}$ is the hypothesis class, with the individual hypotheses being functions $X\rightarrow \left\{0, 1\right\}$ The hypothesis class is the complete set of all hypotheses that a specific learner is capable of expressing. $\mathcal{H}$ is the hypothesis class, with the individual hypotheses being functions $X\rightarrow \left\{0, 1\right\}$ The hypothesis class is the complete set of all hypotheses that a specific learner is capable of expressing.
Line 1343: Line 1343:
 Mistake bound learnability implies PAC-learnability. Mistake bound learnability implies PAC-learnability.
  
-MB learner with $M \lt \text{poly}(n)$ can be transformed into PAC learner by running it on a batch of training examples, stopping when a hypothesis successfully survives $\frac{1}{\epsilon}\text{ln}(\frac{M}{\delta})$ consecutive examples without making a mistake.+M-B learner with $M \lt \text{poly}(n)$ can be transformed into PAC learner by running it on a batch of training examples, stopping when a hypothesis successfully survives $\frac{1}{\epsilon}\text{ln}(\frac{M}{\delta})$ consecutive examples without making a mistake.
 ++++ ++++
  
Line 1349: Line 1349:
 No. No.
  
-PAC-learnability does not guarantee MB-learnability.+PAC-learnability does not guarantee M-B-learnability.
  
-If a concept class is PAC-learnable, then $VC(\mathcal{C}) \leq \text{poly}(n)$. A concept class can have a finite VC-dimension, even when the number of concepts $|\mathcal{C}| is infinite$. This can lead to unbounded number of mistakes, that it may no learn in MB.+If a concept class is PAC-learnable, then $VC(\mathcal{C}) \leq \text{poly}(n)$. A concept class can have a finite VC-dimension, even when the number of concepts $|\mathcal{C}|$ is infinite. This can lead to unbounded number of mistakes, that it may no learn in M-B.
 ++++ ++++
  

Trace:

Navigation

Playground

QR Code
QR Code courses:b4m36smu (generated for current page)