Skip to main content
10 votes

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 ...
D.W.'s user avatar
  • 161k
4 votes
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 ...
Draconis's user avatar
  • 7,138
4 votes
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 ...
Ariel's user avatar
  • 13.4k
4 votes
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) ...
Ariel's user avatar
  • 13.4k
3 votes
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 ...
Yuval Filmus's user avatar
3 votes

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 ...
Ariel's user avatar
  • 13.4k
3 votes
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 -+-+... ...
Yuval Filmus's user avatar
3 votes
Accepted

How can the VC-dimension of Turing machine be finite?

First, let me correct your definition of VC dimension: it is the largest size of a set which can be shattered. If the VC dimension is $d$, then this means that for every set $C$ of size larger than $...
Yuval Filmus's user avatar
3 votes
Accepted

Labeled points in $\{0,1\}^n$ such that every linear separator requires exponential weights

HÃ¥stad gave an even better example in his paper On the Size of Weights for Threshold Gates, which requires super exponential weights. A simple example which requires exponential weights is the ...
Yuval Filmus's user avatar
3 votes

Random forests on monotone training set yields a monotone classifier?

No, it's not guaranteed. You can end up with a decision tree or classifier that is non-monotone. Here is an explicit counterexample, i.e., a training set of 5 samples on 5 attributes: $$\begin{...
D.W.'s user avatar
  • 161k
2 votes
Accepted

VC dimensions: Let ${x_1, \ldots, x_N}$ be $N$ labelled points on $\mathbb{R}$, then there exists a sinusoid that separates these points

Here are some ideas. Denote by $\{x\}$ the fractional value of $x$, and consider the function $f_n(x) = \operatorname{sgn} (\sin 2\pi n x)$. Then: $f_n(x) = +1$ iff $\{nx\} \in (0,1/2)$. $f_n(x) = -1$...
Yuval Filmus's user avatar
2 votes

Geometric intuition behind VC-dimension

The VC dimension is a complexity measure for a family of boolean functions over some domain $\mathcal{X}$. Families who allow "richer" behavior have a higher VC dimension. Since $\mathcal{X}$ can be ...
Ariel's user avatar
  • 13.4k
2 votes

Neural Network | What is the purpose of hidden layers and how many should I use?

It is actually not true that you can get any result that you want without any hidden layers. Consider for example a neural network with one input and one output. The only functions that such a network ...
Yuval Filmus's user avatar
2 votes
Accepted

The VC dimension when the samples are fixed

Suppose were in the realizable model, i.e. we want to learn some $f^*\in\mathcal{H}\subseteq 2^\mathcal{X}$ where $VCdim(\mathcal{H})=d$. Let $M(\epsilon,\delta)$ be the minimal number of samples ...
Ariel's user avatar
  • 13.4k
2 votes

What are the basics of CS i should know,before I start my journey into machine learning

Computer science is a very broad subject area, and many of its sub-disciplines have little or no overlap with others. For example, knowing the basics of operating systems design, compiler design or ...
gandalf61's user avatar
  • 1,589
2 votes
Accepted

PAC learning vs. learning on uniform distribution

Is there a case where a class $\mathcal{F}$ is not efficiently PAC learnable, yet it is efficiently learnable on the uniform distribution? This has been asked on TCS.SE. It looks like the short ...
Caleb Stanford's user avatar
2 votes

Is memorization necessary in learning computer science?

It's hard to answer what you "need", as that depends on your purpose, and hard to answer this question concretely, as it is very broad. I recommend you focus on learning concepts and ideas, ...
D.W.'s user avatar
  • 161k
2 votes
Accepted

Empirical Risk and True Risk - Generalization Error Proof

This answer (as, I presume, the question) uses the notation of the book Understanding Machine Learning: From Theory to Algorithms by Shai Shalev-Shwartz and Shai Ben-David. Suppose our domain set is $\...
Watercrystal's user avatar
  • 1,526
2 votes

What is the VC dimension of the hypothesis class $H=\left\{f_{\theta_{1}, \theta_{2}}: R^{2} \rightarrow\{0,1\} \mid 0<\theta_{1}<\theta_{2}\right\}$?

The VC-dimension of your hypothesis class $\mathcal H$ is 2. To see this, we begin by showing that $\mathcal H$ shatters any 2-element set $\{(a_1 a_2), (b_1, b_2)\}$ of real numbers where all ...
Watercrystal's user avatar
  • 1,526
2 votes
Accepted

Understanding halving algorithm in online learning

The prediction is the value of $r$ which maximizes the quantity $$ | \{ h \in V_t : h (\mathbf{x}_t) = r \} |. $$ This is the number of surviving hypotheses (belonging to $V_t$) which predict $r$ on ...
Yuval Filmus's user avatar
1 vote
Accepted

Pseudo-dimension of a subset of affine functions

I am using the definition of pseudo-dimension found here, page 10 of the pdf. Denote $h_1(x) = 2x+1$, $h_2(x) = 4x$, $h_3(x) = x$ and $h_4(x) =3x+4$. Let's consider $C = (-2, 2)$ a vector. Then $r = (-...
Nathaniel's user avatar
  • 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$ ...
Yuval Filmus's user avatar
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. ...
Ariel's user avatar
  • 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$, ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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.
OmG's user avatar
  • 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 ...
Selina Carter's user avatar
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 ...
D.W.'s user avatar
  • 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 ...
Koenig Lear's user avatar
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 ...
Joshna Gunturu's user avatar

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