Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [lg.learning]

Machine learning and learning theory: PAC learning, algorithmic learning theory, and computational aspects of Bayesian inference and graphical models.

41
votes
4answers
8k views

Is finding the minimum regular expression an NP-complete problem?

I am thinking of the following problem: I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses). ...
3
votes
1answer
216 views

Rademacher complexity beyond the agnostic setting

The way I know of to bound generalization error by Rademacher complexity is Theorem 2.4 in this lecture notes, http://ttic.uchicago.edu/~tewari/lectures/lecture9.pdf. Here the quantity on the LHS that ...
10
votes
3answers
958 views

Resource / book for recent advances in statistical learning theory

I'm quite familiar with the theory behind VC-Dimension, but I'm now looking at the recent (last 10 years) advances in statistical learning theory: (local) Rademacher averages, Massart's Finite Class ...
6
votes
1answer
9k views

Computational complexity of learning (classification) algorithms - fitting the parameters

My wish is to describe the time complexity of several classification approaches. For example, suppose we have $n$ data points in $m$ dimensional space and a binary class variable. We do not assume ...
15
votes
2answers
268 views

On the status of learnability inside $\mathsf{TC}^0$

I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside $\...
15
votes
3answers
335 views

Combinatorial characterization of exact learning with membership queries

Edit: Since I haven't received any responses/comments in a week, I'd like to add that I'm happy to hear anything about the problem. I don't work in the area, so even if it's a simple observation, I ...
12
votes
2answers
323 views

Computational query complexity of SQ-learning

It is known that for PAC learning, there are natural concept classes (e.g. subsets of decision lists) for which there are polynomial gaps between the sample complexity needed for information theoretic ...
11
votes
1answer
493 views

Lower bounds for learning in the membership query and counterexample model

Dana Angluin (1987; pdf) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a ...
4
votes
2answers
349 views

Complexity of finding a consistent hyperplane

Given $m$ binary labeled points in $\mathbb{R}^d$, it is well-known that in general it's NP-hard to find a hyperplane that minimizes sample error. A brute-force search considers all $O(m^d)$ sample ...
15
votes
4answers
372 views

Worst number of questions needed to learn a monotonic predicate over a poset

Consider $(X, \leq)$ a finite poset over $n$ items, and $P$ an unknown monotonic predicate over $X$ (i.e., for any $x$, $y \in X$, if $P(x)$ and $x \leq y$ then $P(y)$). I can evaluate $P$ by ...
12
votes
1answer
706 views

The Cost of an Equivalence Query for DFA

Inspired by this question, I am curious about the following: What is the worst-case complexity of checking whether a given DFA accepts the same language as a given regular expression? Is this ...
3
votes
2answers
328 views

Support Vector Machines

What is it the relationship between the number of support vectors in an SVM and its generalization ability? When lots of support vectors are used to classify, is the error rate minimized, but only to ...
-1
votes
1answer
2k views

off-policy and offline policy reinforcement learning

What's the difference between off-policy reinforcement learning algorithms and offline policy reinforcement learning algorithms ? Or do they mean the same thing ? thanks
7
votes
0answers
186 views

Sample complexity of PAC learning all k-DNFs over the uniform distribution

Is sample complexity of PAC learning all $k$-DNFs over the uniform distribution known (that is all DNFs with all terms of size at most $k$ and without restriction on the number of terms)? The only ...
5
votes
2answers
370 views

Proper PAC learning VC dimension bounds

It is well known that for a concept class $\mathcal{C}$ with VC dimension $d$, it suffices to obtain $O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$ labelled examples to PAC learn $\...
5
votes
1answer
1k views

PAC learning boolean conjunctions

Kearns and Vazirani (chapter 1) describe an efficient algorithm for PAC learning conjunctions of boolean variables $x_1, x_2, \ldots, x_n$, which starts with the hypothesis $$h=x_1\wedge\overline{x_1}\...
4
votes
1answer
167 views

Tight VC bound for agnostic learning

The following result is supposedly known. However, the proofs I am able to find all prove a weaker result with an extra log factor. Where can I find the proof of the tight bound? Theorem. Let $\...
2
votes
1answer
367 views

Follow the Perturbed Leader for nonlinear cost functions

The famous FTPL algorithm [1] is analyzing linear cost function. Is there any generalized proof for nonlinear functions known? Note that in the last paragraph of [1] it says "It would be great to ...
0
votes
0answers
77 views

Generalizing a set of positive and negative examples through DFAs [duplicate]

Possible Duplicate: Is finding the minimum regular expression an NP-complete problem? Let $\Sigma$ be an alphabet. Let $P$ and $N$ (the set of positive and negative examples) be two disjoint ...