Skip to main content

Questions tagged [learning-theory]

Questions about the design and analysis of machine learning algorithms.

Filter by
Sorted by
Tagged with
36 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 ...
Artem Kaznatcheev's user avatar
9 votes
0 answers
179 views

Boolean formula that agrees with most truth assignments

Let $X_1,\dots,X_n$ be $n$ boolean variables. I have an unknown predicate $P(X_1,\dots,X_n)$ on these boolean variables. Of course, I can view the predicate as a function $f_P : \{0,1\}^n \to \{0,1\}...
D.W.'s user avatar
  • 162k
8 votes
2 answers
3k views

VC dimension of linear separator in 3D

I am confused about the Vapnik-Chervonenkis dimension of a linear separator in 3 dimensions. In three dimensions, a linear separator would be a plane, and the classification model would be "...
Jason Smith's user avatar
8 votes
1 answer
827 views

Adapting neural network

I have on a few occasions trained neural networks (back propagation networks) with some rather complicated data sets (backgammon positions and OCR). When doing this, it seems that a lot of the work ...
Ebbe M. Pedersen's user avatar
8 votes
2 answers
2k views

PAC learning axis parallel rectangles

I am trying to understand the proof that the axis parallel rectangles are PAC learnable in the realizable case. This means that given $\epsilon, \delta$ with enough data we can find a function $h$ ...
alejopelaez's user avatar
7 votes
0 answers
2k views

Detecting the damaged regions in cars

Detecting the regions where a car has been damaged and the extent to which it has been damaged is a very interesting problem. It has potential applications in automatic auto insurance claims. ...
malreddysid's user avatar
6 votes
2 answers
475 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}{\...
seteropere's user avatar
6 votes
2 answers
546 views

any hope for a universal automatic parser?

Say you are a program, and you are given some source code but you don't know in what language, it can be C++/Java/Python/Lisp/... all you know is that it is highly structured and LR(1) parse-able, and ...
reuns's user avatar
  • 170
6 votes
2 answers
367 views

Learning juntas, with membership queries

The junta problem is the following: we have a boolean function $f:\{0,1\}^n \to \{0,1\}$ that actually happens to depend on only $k$ of its input variables. Given the value of $f(x)$ for many random ...
D.W.'s user avatar
  • 162k
5 votes
1 answer
3k views

How to implement the regret matching algorithm?

My question is the following: How to calculate the regret in practice? I am trying to implement the regret matching algorithm but I do not understand how to do it. First, I have $n$ players with the ...
drzbir's user avatar
  • 990
5 votes
1 answer
310 views

VC dimensions: Let ${x_1, \ldots, x_N}$ be $N$ labelled points on $\mathbb{R}$, then there exists a sinusoid that separates these points

(Proposition, pg 26): Let ${x_1, \ldots, x_N}$ be $N$ points on $\mathbb{R}$, $N \in \mathbb{Z}$, labelled either $+1$ or $-1$ , then there exists a function from the set $\{t \mapsto \sin(\omega t)| \...
Shamisen Expert's user avatar
4 votes
1 answer
445 views

Random forests on monotone training set yields a monotone classifier?

Suppose I train a random forests classifier on a monotone training set. Is the resulting classifier guaranteed to be a monotone function? Suppose I apply the ID3 algorithm (the greedy algorithm) to ...
D.W.'s user avatar
  • 162k
4 votes
1 answer
2k views

single agent vs multiple agent reinforcement learning

I am confused about 'single' vs 'multiple' agent reinforcement learning. Let's say that I have 1 hunter who I am training to hunt 1 static prey, so that only the hunter is moving around. This is ...
cgo's user avatar
  • 273
4 votes
0 answers
84 views

VC dimension and binary operations

There are two classes of binary functions, $F_1,F_2$. The VC-dimension of $F_i$ is $d_i$. Is there any simple formula for the VC-dimension of the following classes? $F_\lor := \{ f_1(x) \lor f_2(x) |...
Erel Segal-Halevi's user avatar
3 votes
1 answer
111 views

AdaBoost - why using such alpha function?

I'm reading the paper where AdaBoost was invented (link), and I couldn't understand why they have chosen the formula α_t = 1/2 * ln((1-ε_t) / ε_t). snippet: ...
Adi Peled's user avatar
3 votes
2 answers
345 views

How to determine the size of training data using VC dimension?

I want to determine the size of training data ($m$) when I know the parameters $VC(H)$, $δ$ and $e$. As I know the $VC$ bound satisfy this equation: $$ \mathrm{error}_{\mathrm{true}}(h) \le \mathrm{...
Hadi's user avatar
  • 141
3 votes
1 answer
223 views

PAC learning vs. learning on uniform distribution

The class of function $\mathcal{F}$ is PAC-learnable if there exists an algorithm $A$ such that for any distribution $D$, any unknown function $f$ and any $\epsilon, \delta$ it holds that there exists ...
Ernie's user avatar
  • 53
3 votes
1 answer
506 views

The VC dimension when the samples are fixed

The VC dimension is usually used in the following way. There is a space of hypotheses. There is an unknown probability distribution. We sample some training-samples from this distribution. We find the ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
38 views

Learning a small disjunction using an input distribution of our choice

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}.$$ I don't know the values of $i_1,\dots,i_k$, but I ...
D.W.'s user avatar
  • 162k
2 votes
3 answers
827 views

Over-fitting Always Occurs?

i get stuck in one sentence in machine learning. i read tom Mitchel book on ML, and some other materials. if we have small training set, always over-fit can occurs? or is likely to occurs? i read ...
Ebraham's user avatar
  • 35
2 votes
1 answer
2k views

What are the mathematical prerequisites for adaptive machine learning algorithms?

I am a PhD student in Computer Science who switched his PhD a little bit towards ML algorithms combined with something else... I am an expert in that something else, say image processing, but not an ...
paxRoman's user avatar
  • 123
2 votes
1 answer
174 views

proving the error bound for a hypothesis

Given a hypothesis $h:X\rightarrow Y$ ($h$ is returned by an Empirical Risk Minimization (ERM) strategy with realizable case i.e. $h$ is consistent with the sample examples) over $X=[0,1]\subseteq R$ ...
seteropere's user avatar
2 votes
1 answer
3k views

Is it true that PAC is a subset of agnostic PAC?

I would like to see the proof or a refernce to it. I feel it is obvious but my tutor insists the other way (agnostic PAC is a subset of PAC, and there are problems in PAC that are not angostic PAC).
proton's user avatar
  • 123
2 votes
1 answer
64 views

Uniform convergence for a class of finite dimension

The following theorem is cited in Balcan, M.F., Sandholm, T. and Vitercik, E., 2019. Estimating approximate incentive compatibility which I am currently reading and it is referenced to David Pollard. ...
ABIM's user avatar
  • 73
2 votes
1 answer
79 views

Labeled points in $\{0,1\}^n$ such that every linear separator requires exponential weights

I want to find labeled samples in $\{0,1\}^n$ such that the Perceptron algorithm takes $2^{\Omega(n)}$ steps to converge. One way to do this would be to find a sequence of labeled examples that are ...
Ustad Kadir Misiroglu's user avatar
2 votes
1 answer
284 views

Understanding halving algorithm in online learning

I am working through "Understanding Machine Learning Theory" by Shai Shalev-Schwartz. In the chapter "Online learning" I came across the halving algorithm, the author uses the ...
Naren's user avatar
  • 43
2 votes
1 answer
44 views

Neural Network | What is the purpose of hidden layers and how many should I use?

I am pretty new to Neural Networks and I have two questions about hidden layers: 1. What is the purpose of hidden layers? I was wondering this because obviously you can get every result you want with ...
Tobi H.'s user avatar
  • 21
2 votes
1 answer
147 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.'s user avatar
  • 162k
2 votes
1 answer
110 views

Sample compression scheme and bounding the VC dimension

There is a compression function takes any sample $S$, for which there exists a function $h ∈ H$ with $L_S(h)$, and compresses it to a subset of $k$ sample points. Similarly, there is a decompression ...
brianoconner's user avatar
2 votes
0 answers
25 views

Representational power of Neural Neural Networks without a bias term

In a fully connected Neural Network, each perceptron has it's bias term $b$ which is learnt. Often (example, in Linear/ Logistic Regression), when we don't want to treat this bias term explicitly, we ...
Harry's user avatar
  • 21
2 votes
0 answers
68 views

Multi-class sample complexity for PAC learning using "VC dimension"

VC dimension covers the binary classification case, i.e. when we want to get a predictor $X \to \{0, 1\}$. Using VC dimension, we can get the upper bound on the sample complexity for PAC-learning. In ...
Dmitry's user avatar
  • 345
2 votes
1 answer
47 views

Generalization error bound in case of collaborative learning

I am reading the paper "Collaborative PAC Learning" by Blum et al. So I will try to setup the problem here as to avoid reading the complete section (personalized setting). Assume there are $...
Naren's user avatar
  • 43
2 votes
0 answers
43 views

Covering numbers to show that H is agnostically PAC-learnable

Suppose $X=[0,1]$ and $Y=[0,1]$, and we use the squared loss Let's define the hypothesis class $H = {h(x) = (x-a)^2 : a \in [0,1]}$. Question: How can covering numbers be used to show that this ...
Ilan Aizelman WS's user avatar
2 votes
0 answers
33 views

Query complexity of exact learning and combinatorial parameter

When defining the query complexity of exact learning for a concept $c$ (considered as a function from $\{0,1\}^n \mapsto \{0,1\}$) in a concept class $\mathcal{C}$, we often come across the following ...
Plussoyeur's user avatar
2 votes
0 answers
62 views

Automatic learning/discovery of logics

Are there efforts to automatically discover new logics? Logics are simple structures - they have formal language, deduction rules, semantics and certain properties that are proved or discarded for ...
TomR's user avatar
  • 1,401
2 votes
0 answers
297 views

Faster RCNN: how to translate coordinates

I'm trying to understand and use the Faster R-CNN algorithm on my own data. My question is about ROI coordinates: what we have as labels, and what we want in the end, are ROI coordinates in the input ...
gdelab's user avatar
  • 136
2 votes
1 answer
89 views

Supervised learning with no prior information

I am now reading two modern books on machine learning theory. Both of them emphasize that, in order to succeed in supervised learning, one must choose a good hypothesis class. "Good" means that it is ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
39 views

Does selecting the same arm has the same reward?

In multi-armed bandit problem, we have a set of $K$ arms. In each round $t$, a bandit selects an arm $k$ and receives a reward $r_{kt}$. The objective is to maximize the rewards after $T$ rounds. My ...
zdm's user avatar
  • 1,046
1 vote
1 answer
99 views

How can the VC-dimension of Turing machine be finite?

The VC-dimension of a hypothesis class $\mathcal{H}$ is defined to be the size of the maximal set $C$ such that $\mathcal{H}$ cannot shutter. This paper shows that the VC-dimension of the set of all ...
SomeoneHAHA's user avatar
1 vote
1 answer
54 views

What does it mean the norm symbol applied to a concept?

I'm reading this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.14 or http://www.jmlr.org/papers/volume10/kontorovich09a/kontorovich09a.pdf On page 1101 are introduced 2 functions ...
Nick's user avatar
  • 221
1 vote
1 answer
400 views

Empirical Risk and True Risk - Generalization Error Proof

I showed that, over an uncountable domain,learner A and a distribution P, such that for every sample size m and all samples S from $P^m$ $$ : L_S(A(S)) − L_P (A(S))| = 1 $$ Now I wanna prove for ...
brianoconner's user avatar
1 vote
1 answer
57 views

What are the basics of CS i should know,before I start my journey into machine learning

I am myself a non-cs graduate and would love to be a machine learning engineer. I have learned to code and know the basics of <...
Fasty's user avatar
  • 111
1 vote
1 answer
447 views

Geometric intuition behind VC-dimension

Recently, I learnt about VC-dimension and how its boundedness assures PAC learnability on uncountable range spaces (let's assume that hypothesis class is the same as the family of concepts we want to ...
LastIronStar's user avatar
1 vote
1 answer
48 views

Obtaining a set of $O(\log n)$ classifiers using multiplicative weights algorithms

I'm trying to find an algorithm that uses the multiplicative weights algorithm to obtain a set of $O(\log n)$ classifiers that classify a set $X=\{x_1, x_2, ...,x_n\}$ where the set of labels is $l \...
giorgioh's user avatar
  • 317
1 vote
1 answer
163 views

Density of uniform distribution over two disjoint squares

A probability distribution $P$ over $X \times \{0, 1\}$. $P$ can be defined in term of its marginal distribution over $X$ , which we will denote by $P_X$ and the conditional labeling distribution, ...
brianoconner's user avatar
1 vote
1 answer
31 views

what does this phrase mean: "train a policy network"

I am familiar with the basics (and perhaps a substantial amount of basics) of imitation learning and reinforcement learning. In IL (imitation), we take demonstrations from an assumed expert, which we ...
cgo's user avatar
  • 273
1 vote
1 answer
729 views

VC dimension of finite unions of one-sided intervals

What is the VC dimension of $k$ finite unions of one-sided intervals: If we take 3 one-sided intervals like $(-\infty, a_1] $, $(-\infty, a_2] $ and $(-\infty, a_3] $, I think union of these ...
Joshna Gunturu's user avatar
1 vote
1 answer
104 views

In the learning theory version of Occam's razor, why can't I just declare whatever hypothesis I want to be "shortest"?

Occam's razor states that shorter explanations (formally speaking, hypotheses) are more likely to be correct. Indeed this can be formalized: for a hypothesis class $\mathcal H$ one may ascribe ...
djechlin's user avatar
  • 497
1 vote
1 answer
1k views

Why is the VC dimension different on intervals and half intervals?

As I read this lecture for being familiar with VC dimension we find on p. 8: VC(half intervals in $\mathbb{R}$ ) = 1 .... no subset of size 2 can be shattered VC(intervals in $\mathbb{R}$ )...
user17973's user avatar
1 vote
1 answer
30 views

Why we need at most $2n$ examples to determine an axis aligned rectangle

In Ben-David & et al.'s Understanding Machine Learning, the authors wrote: Let $\mathcal{H}_n$ be the class of axis aligned rectangles in $\mathbb{R}^n$ , namely, $$ \mathcal{H}_n = \{h(a_1,\dots,...
Tran Khanh's user avatar