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

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

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 ...


5

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$.


4

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) you want to answer the opposite of $h_t$, so you want $\alpha_t$ to be negative and very large in absolute value. If on the other hand $\epsilon_t$ is very low ...


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

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

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.


3

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 bound the empirical Rademacher complexity in terms of the empirical $L_2$ covering numbers of $\mathcal{A}$. Your result is directly obtained from the chaining ...


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

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

$\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

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 ...


2

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, as these are more likely to be of lasting use. Sometimes, though, to understand how some interesting capability is achieved, you will need to understand the ...


1

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 returns a counterexample $w$. Here a hypothesis is a DFA (a regular language) and $w$ is a word that the DFA gets wrong (either the DFA accepts, but $w$ is ...


1

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 example for chess, a neural network can be trained with the action to be taken in a given state of the board. This can be trained using a database of existing ...


1

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 can shatter only 2 points.


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