Questions tagged [learning-theory]
Questions about the design and analysis of machine learning algorithms.
5
questions
34
votes
2
answers
3k
views
Are there improvements on Dana Angluin's algorithm for learning regular sets
In her 1987 seminal paper Dana Angluin presents a polynomial time algorithm for learning a DFA from membership queries and theory queries (counterexamples to a proposed DFA).
She shows that if you are ...
- 4,812
6
votes
2
answers
466
views
What is usually the next step after showing the VC dimension?
I am new to statistical learning. I have a structure $X$ where I showed its hypothesis class $H$ has VC dimension $d$. All I know now is that I can bound the number of examples by $m\geq \frac{1}{\...
- 677
2
votes
1
answer
145
views
Learning a small disjunction
I have a boolean function $f: \{0,1\}^n \to \{0,1\}$ that I know takes the form
$$f(x_1,\dots,x_n) = x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k},$$
but I don't know the values of $i_1,\dots,i_k$. ...
D.W.♦
- 154k
1
vote
0
answers
190
views
Why is it NP-hard to learn a disjunction of k variables as a disjunction of fewer than k log n variables?
I'm looking at the claim in An algorithmic theory of learning: Robust concepts and random projection by R. I. Arriaga and S. Vempala (2006):
Further, it is NP-hard to learn a disjunction of k ...
- 487
0
votes
1
answer
625
views
VC dimension of monotone disjunctions of length k over n variables?
There are of course $n \choose k$ monotone disjunctions which bounds the VC dimension at $\log_2 {n \choose k}$. I'm wondering if this is bound at $k \log_2 n$? (Possibly follows from combinatorial ...
- 487