Questions tagged [learning-theory]
Questions about the design and analysis of machine learning algorithms.
87
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
9
votes
0
answers
170
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.♦
- 154k
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 "...
- 81
8
votes
1
answer
822
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 ...
- 209
8
votes
2
answers
1k
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$ ...
- 181
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. ...
- 181
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
6
votes
2
answers
510
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 ...
- 170
6
votes
2
answers
355
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.♦
- 154k
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 ...
- 970
5
votes
1
answer
193
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)| \...
- 153
4
votes
1
answer
435
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.♦
- 154k
4
votes
0
answers
83
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) |...
- 5,790
3
votes
1
answer
97
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:
...
- 68
3
votes
2
answers
344
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{...
- 141
3
votes
1
answer
208
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 ...
- 53
3
votes
1
answer
498
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 ...
- 5,790
3
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 ...
- 263
3
votes
1
answer
37
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.♦
- 154k
2
votes
3
answers
815
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 ...
- 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 ...
- 123
2
votes
1
answer
165
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$ ...
- 677
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).
- 123
2
votes
1
answer
53
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. ...
- 73
2
votes
1
answer
66
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 ...
2
votes
1
answer
176
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 ...
- 43
2
votes
1
answer
39
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 ...
- 21
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
2
votes
1
answer
101
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 ...
- 65
2
votes
0
answers
61
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 ...
- 315
2
votes
1
answer
38
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 $...
- 43
2
votes
0
answers
41
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 ...
- 203
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 ...
- 121
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 ...
- 1,381
2
votes
0
answers
296
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 ...
- 136
2
votes
1
answer
84
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 ...
- 5,790
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 ...
- 1,046
1
vote
1
answer
97
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 ...
- 101
1
vote
1
answer
53
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 ...
- 211
1
vote
1
answer
348
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 ...
- 65
1
vote
1
answer
50
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 <...
- 111
1
vote
1
answer
423
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 ...
- 142
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 \...
- 317
1
vote
1
answer
140
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, ...
- 65
1
vote
1
answer
30
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 ...
- 263
1
vote
1
answer
650
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 ...
1
vote
1
answer
95
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 ...
- 487
1
vote
1
answer
994
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}$ )...
- 11
1
vote
0
answers
24
views
Transductive Learning vs Inductive Learning in Machine Learning
Several recent research work has shown that transductive learning/inference outperforms inductive learning/inference during classification problems. This has been found in few-shot learning, other ...
- 53
1
vote
0
answers
115
views
Infinite VC Dim not PAC learnable
This is usually shown by an application of the Statistical No Free Lunch Theorem.
But is this possible to show this by working simply with the definition of PAC learnability and the sample complexity ...
- 11