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/24 19:36] – [Other questions] jpelccourses:b4m36smu [2026/05/27 09:37] (current) – [Other COLT] jpelc
Line 3: Line 3:
 {{courses:smu:smu_2023_model_exam.pdf| Sample Exam (2023)}} {{courses:smu:smu_2023_model_exam.pdf| Sample Exam (2023)}}
  
-======= Sample test =======+{{courses:smu:smu_skripta_thirtyfourth_draft.pdf| Skripta}} 
 +======= Sample exam 1 =======
  
 ===== Question 1. (10 points) ===== ===== Question 1. (10 points) =====
Line 364: 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 673: Line 674:
 \begin{tikzpicture}[ \begin{tikzpicture}[
     >=Stealth,     >=Stealth,
-    % Added label styling 
     label_style/.style={font=\sffamily\scriptsize, text=gray},     label_style/.style={font=\sffamily\scriptsize, text=gray},
     box/.style={draw, rectangle, rounded corners, minimum width=1.2cm, minimum height=0.8cm, fill=white, font=\sffamily},     box/.style={draw, rectangle, rounded corners, minimum width=1.2cm, minimum height=0.8cm, fill=white, font=\sffamily},
Line 699: Line 699:
 \node (h_next) at (12, 1) {$h_t$}; \node (h_next) at (12, 1) {$h_t$};
  
-\draw[thick] (h_prev) -- (9.5, 1);+% Fixed: Stop the continuous line at the output gate (8.5) 
 +\draw[thick] (h_prev) -- (8.5, 1);
 \draw[->, thick] (x_curr) -- (1, 1); \draw[->, thick] (x_curr) -- (1, 1);
  
Line 710: Line 711:
  
 \node[box] (g) at (6.5, 2.5) {$\tanh$}; \node[box] (g) at (6.5, 2.5) {$\tanh$};
-% Candidate gate doesn't have a label in your request, but usually it's "cand" 
 \node[label_style, below=of g] {candidate}; \node[label_style, below=of g] {candidate};
  
Line 741: Line 741:
 % Final Hidden State routing % Final Hidden State routing
 \draw[->, thick] (mult_o) -- (9.5, 1) -- (h_next); \draw[->, thick] (mult_o) -- (9.5, 1) -- (h_next);
-\node[dot] at (9.5, 1) {}; 
  
 % Label % Label
Line 837: 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 863: Line 862:
 $VC(\mathcal{H}) \leq n \land VC(\mathcal{H}) \geq n \implies VC(\mathcal{H}) = n$ $VC(\mathcal{H}) \leq n \land VC(\mathcal{H}) \geq n \implies VC(\mathcal{H}) = n$
 ++++ ++++
 +
 +====== Other questions ======
 +
  
 ===== Question 5. (10 points) ===== ===== Question 5. (10 points) =====
Line 1188: Line 1190:
 Latent Dirichlet allocation tries to discover hidden topics within a set of documents, by finding clusters of terms that tend to occur together. Latent Dirichlet allocation tries to discover hidden topics within a set of documents, by finding clusters of terms that tend to occur together.
  
-The model extracts these topics and infers the topic distribution $\thata$ for each document and the word distribution $\beta$ for each topic.+The model extracts these topics and infers the topic distribution $\theta$ for each document and the word distribution $\beta$ for each topic.
  
 The document-topic distribution $\theta$ is modeled as a random variable $\theta \sim \text{Dirichlet}(\alpha)$ The document-topic distribution $\theta$ is modeled as a random variable $\theta \sim \text{Dirichlet}(\alpha)$
Line 1305: 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 1311: Line 1313:
 WINNOW algorithm is used to learn linearly separable concept (like perceptron). The initial $h$ is all ones, if it makes a mistake: WINNOW algorithm is used to learn linearly separable concept (like perceptron). The initial $h$ is all ones, if it makes a mistake:
  
-  * false positive (if $x$ is True and we predicted False) - double all $h_i$ where $x_i = 1$ +  * false negative (if $x$ is True and we predicted False) - double all $h_i$ where $x_i = 1$ 
-  * false negative - nullify all $h_i$ where $x_i$ = 1+  * false positive - nullify all $h_i$ where $x_i$ = 1
  
 WINNOW natively learns monotone conjunctions and disjunctions, we adapt it to learn non-monotone by introducing new variables. WINNOW natively learns monotone conjunctions and disjunctions, we adapt it to learn non-monotone by introducing new variables.
Line 1341: 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 1347: 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)