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.♦
- 154k
5
votes
Are there improvements on Dana Angluin's algorithm for learning regular sets
I do not know if my answer is still relevant. Recently it has been described the implementation of a new algorithm called Observation Pack or in some circumstances Discrimination Tree by Falk Howar. ...
- 211
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 ...
- 13.3k
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 ...
- 7,038
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) ...
- 13.3k
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 ...
- 274k
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 ...
- 274k
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 -+-+... ...
- 274k
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 $...
- 274k
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.♦
- 154k
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 ...
- 13.3k
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 ...
- 13.3k
2
votes
single agent vs multiple agent reinforcement learning
A key difference between RL and MARL arises when you consider that other agents are strategic and their behaviour is adaptive. Game theoretical concepts are very important within the scope of MARL and ...
- 325
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$...
- 274k
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 ...
- 13.3k
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 ...
- 274k
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 $\...
- 1,516
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 ...
- 1,516
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 ...
- 1,569
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 ...
- 6,873
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.♦
- 154k
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 ...
- 274k
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$ ...
- 274k
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.3k
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$, ...
- 274k
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 ...
- 274k
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,562
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 ...
D.W.♦
- 154k
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 ...
- 653
Only top scored, non community-wiki answers of a minimum length are eligible