# Tag Info

### any hope for a universal automatic parser?

You might be interested in learning about grammar induction: given a set of examples of strings from a context-free language, there are algorithms to learn a context-free grammar that generates those ...
• 161k
Accepted

### Does selecting the same arm has the same reward?

In the version of the Multi-Armed Bandit problem I'm familiar with, there is a fixed list of distributions $B = R_1, R_2 \cdots R_n$, and the reward for pulling lever $k$ is chosen from the ...
• 7,138
Accepted

### Is it true that PAC is a subset of agnostic PAC?

The trivial implication is: $\mathcal{C}\subseteq 2^\mathcal{X}$ is agnostic PAC learnable $\Rightarrow$ $\mathcal{C}$ is PAC learnable Intuitively, being agnostic PAC learnable is a stronger ...
• 13.4k
Accepted

### AdaBoost - why using such alpha function?

Recall that the final hypothesis after $T$ rounds is $h_T(x)=sign\left(\sum\limits_{i=1}^T \alpha_t h_t(x)\right)$, i.e. $\alpha_t$ is the weight of $h_t$ in $h_T$. If $\epsilon_t$ is high (near one) ...
• 13.4k
Accepted

### What does it mean the norm symbol applied to a concept?

The only property that the functions $|\cdot|$ and $\|\cdot\|$ need to satisfy is that for every $n$ there is a finite number of $x$'s in the domain such that $|x|=n$ or $\|x\|=n$. The difference ...
• 278k

### Uniform convergence for a class of finite dimension

The keyword to look for is Dudley's chaining integral, see e.g. Vershynin's book "High Dimensional Probability" which contains a chapter on the chaining technique. Chaining allows us to ...
• 13.4k
Accepted

### VC dimension of the class of polynomial classifiers of degree $n$

The idea is that a polynomial of degree $n$ has at most $n$ roots, and so can change signs at most $n$ times. Therefore no polynomial of degree $n$ can form an alternating pattern +-+-... or -+-+... ...
• 278k
Accepted

• 15.8k
1 vote

### Obtaining a set of $O(\log n)$ classifiers using multiplicative weights algorithms

At each step, you are dividing the weights of correctly labelled elements by $e^{-\epsilon}$, and multiplying the weights of wrongly labelled elements by $e^{\epsilon}$. If a $p \geq 1/2 + \delta$ ...
• 278k
1 vote

### Compression Bounds - Determine and Visualize for hypothesis vs VC dimension

Generally, every class of finite VC dimension admits to a (exponential size in the dimension) compression scheme. This was an open question resolved a few years ago by Shay and Amir in this paper. ...
• 13.4k
1 vote
Accepted

### Sample compression scheme and bounding the VC dimension

Suppose that $H$ shatters a set $S$ of size $\ell$, and has a compression scheme of size $k$. For each of the $2^\ell$ labelings of $S$, the compression scheme associates a labeled subset of size $k$, ...
• 278k
1 vote
Accepted

### Density of uniform distribution over two disjoint squares

The density $p_R$ of the uniform distribution over a rectangle $R$ is given by $p_R(x) = 0$ if $x \notin R$, and $p_R(x) = 1/\mathit{area}(R)$ otherwise. Indeed, up to scaling the distribution must ...
• 278k
1 vote
Accepted

### Uniform Convergence and VC Theroy

What is considered in VC theory is about the bound of error between empirical risk and real expected risk. Hence, the worst-case function is when the difference between these two risks is maximized.
• 3,572
1 vote

### VC dimension of the class of polynomial classifiers of degree $n$

Here is a proof (not the only one). This proof appeals to the fact that our hypothesis class is a subset of a linear hypothesis class of degree $n+1$. Let $\cal{P}_n$ denote the set of all d-degree ...
1 vote
Accepted

### Dana Angluin's L* algorithm - Hypothesis inconsistent

I have no idea what it would mean for a hypothesis to be inconsistent in this context, but the answer to your second question is: No. You won't receive the same counterexample twice. The teacher ...
• 161k
1 vote

### what does this phrase mean: "train a policy network"

A policy is just a response or action given a state (situation). Training a neural network with samples from an expert is just searching for a function F that efficiently maps states to actions. For ...
• 649
1 vote

### VC dimension of finite unions of one-sided intervals

Finite unions of one-sided intervals can shatter only 2 points, because as said by @YuvalFilmus in comments the union of Finite unions is a single one-sided interval, and a single one-sided interval ...

Only top scored, non community-wiki answers of a minimum length are eligible