10

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 strings. To learn more about it, read the Wikipedia article I linked to, and Inducing a context free grammar, Is there a known method for constructing a ...


9

You have a small (but crucial) misunderstanding of what the VC dimension of a class is. The VC dimension is the maximal number $d$ such that there exists a set of $d$ points that is shattered by the class. It doesn't mean that every set is shattered. In this case, indeed 4 co-planar points cannot be shattered, but if they are placed in a tetraeder then ...


9

Roughly speaking, over-fitting typically occurs when the ratio $\frac{\text{complexity of the model}}{\text{training set size}} $ is too high. Think of over-fitting as a situation where your model learn the training data by heart instead of learning the big pictures which prevent it from being able to generalized to the test data: this happens when the model ...


6

If, as you've stated, you're interested in coming up with a PAC learning algorithm then finite VC-dimension is a prerequisite. This follows from what is sometimes referred to as the Fundamental Theorem of Statistical Learning Theory. In brief this results says that if a concept class $C$ has finite VC-dimension $d$ then a learning algorithm that produces a ...


6

A distinction should be made between constructing practical machine learning algorithms and theoretical algorithms, such as PAC learning algorithms. A machine learning practitioner doesn't usually invoke the concept of VC dimension — indeed, many of them probably have never heard of it, especially if they're applying machine learning in some other ...


5

Consider a case where the actual label is $1$ for all $x\in [0,1]$. Suppose $H$ consists of two classifiers: one that realizes this (i.e. $\forall x\in [0,1], h(x)=1$), and one that is almost entirely wrong: $g(x)=0$ except for some finite set of numbers $S$. If the sample is exactly $S$, then both classifiers have the same error on the sample set (0), so ...


5

Lerning juntas from membership queries can be done in $O_k(\log(n))$ queries indeed. According to Yuval's answer, this give a correct dependence of $n$. However, the dependence on $k$ is not tight (it will be something like $2^k$). The answer to this question is actually written in the Learning juntas by Mossel, O'Donnell and R. Servedio, but I'll spell it ...


5

Information theory shows that you need at least $\log_2 \binom{n}{k}$ queries. When $k$ is small, this is $\Theta(k\log n)$, which is probably enough. Consider for example the case $k=1$, and suppose for simplicity that $n$ is a power of $2$. By feeding the inputs $x_i = \text{bit $r$ of $i$}$ to $f$ you can recover the index $i_1$. (To determine whether the ...


5

This is roughly an open problem subject to ongoing research with various different strategies and heuristics known. A key word is "neural network architecture". The most basic strategy is to iterate through various network topologies and retrain for each one. Another strategy is to start with a relatively larger network and prune connections that have low ...


5

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. This algorithm is like L* but use Rivest-Shapire or a other method(see Steffen and Isberner) for handle counterexample decomposition; and it uses a data ...


4

The index set of the max operation is $A_i$, the actions of player $i$. The formula says: take each such action $a_i \in A_i$ and compute its regret (with the sub-formula you say you can implement easily), and then take the maximum of those regrets. The reason for the $\max(R,0)$ is that actions with negative regrets are performing worse than the action ...


4

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 condition, since you can, for all distributions on $\mathcal{X}\times\{-1,1\}$, get close to the optimal error (in particular, you can do so when the labels are ...


4

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 distribution $R_k$. So pulling the same lever twice might lead to different rewards, but the rewards are connected through the distribution $R_k$.


3

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{align*} &(01011, 0)\\ &(01101, 0)\\ &(00111, 1)\\ &(10110, 0)\\ &(11000, 1) \end{align*}$$ This training set is monotone: it is consistent with ...


3

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 between the two is the domain: $|\cdot|$ is defined on $\mathcal{X}$ while $\|\cdot\|$ is defined on $\mathcal{C}$. These functions are instantiated on page 1115: ...


3

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 $d$ there exists a function $f\colon C \to \{0,1\}$ which is not compatible with any function computed by an $n$-state Turing machine. You are attempting to ...


3

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 function $\sum_i 2^i (x_i - y_i) \geq 0$ or variants.


2

Suppose you're aiming for a specific error rate. Suppose for the moment that there is no training error. You have an inequality involving all your known parameters and the unknown $m$, and you can solve it to obtain a value of $m$ that guarantees the specific true error rate, assuming that there is no training error. If you then run classification, you can ...


2

$\Theta(2^k \lg n)$ queries are necessary and sufficient. Algorithm Define $I = \{i_1,\dots,i_k\}$. Our goal is to recover $I$. Given $x$, define $Z(x) = \{i : x_i = 0\}$. For each $x$ where $f(x)=0$, we learn that $Z(x) \subseteq I$. This suggests the following algorithm: Set $J := \{1,2,\dots,n\}$. For each $x$ in the input such that $f(x)=0$, set $...


2

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 required to obtain an error of at most $\epsilon$ with probability at least $1-\delta$. Since the bound you mentioned on $M(\epsilon, \delta)$ holds for any ...


2

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$ iff $\{nx\} \in (1/2,1)$. Suppose first that the set of points is independent over the rationals. Weyl's equidistribution theorem shows that $\{nx_1\},\ldots,...


2

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 arbitrary, there isn't a general geometric interpretation. However, if you think of $\mathcal{X}$ as $\mathbb{R}^d$, then you can think of binary functions as ...


2

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 can be compute is threshold functions – whether the input is at most something or at least something (assuming the output is converted to Boolean). Roughly ...


2

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 -+-+... of length $n+2$. This shows that the VC dimension is at most $n+1$. On the other hand, for any set of $n+1$ pairs $(x_1,y_1),\ldots,(x_{n+1},y_{n+1})$, there is ...


2

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 microprocessor design are unlikely to help you make progress in machine learning (although each one is an interesting topic in its own right). Machine learning ...


2

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 answer is yes -- Aaron Roth gives the example of width-$k$ conjunctions for $k \gg \log n$. And in the comments, Avrim Blum is quoted as giving the answer of $2$-...


2

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 components of the pairs are positive: $\emptyset$ is accounted for by $f_{c, c + \varepsilon}$ for any real $c$ such that $ca_1 \neq a_a$ and $cb_1 \neq b_2$ and some ...


2

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 $\mathbb N$ and we are interested in binary classification. We want to show that there exists a distribution $P$ on $\mathbb N$ and a learning algorithm $A$ such ...


1

I think that the success of a newborn child follows from the fact that the phenomena he's trying to learn is describable (or can be sufficiently approximated) by the hypothesis class generated by the learning algorithm which is going on in his brain. This is of course, not formal in any way, but say a baby is equipped with some neural network (of fixed ...


1

It may be possible to automatically generate parsers for multiple programming languages using example-based machine translation systems. These systems have been used to translate natural languages, so it is also possible that they could be used to translate and parse programming languages. Example-based machine translation systems can be designed to "learn" ...


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