The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [learning-theory]

Questions about the design and analysis of machine learning algorithms.

Filter by
Sorted by
Tagged with
1
vote
0answers
12 views

Hypothesis space in AdaBoost or general Machine learning

I was curious about the following: in most learning algorithms, when an algorithm is said to learn a concept class $C$ then the algorithm outputs a function from the hypothesis space $H$ and often ...
1
vote
1answer
42 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 ...
0
votes
1answer
59 views

Dana Angluin's L* algorithm - Hypothesis inconsistent

is it possible for the Dana Angluin's L* algorithm that a hypothesis is inconsistent? So assume we have a closded observation table for a regular language L. Now after creating the hypothesis we will ...
0
votes
0answers
33 views

Why is Agnostic PAC learnability a stronger criterion as compared to the PAC learnability?

I am trying to understand the mentioned question. According to me, it should be other way around as it is easier to find hypothesis which is approximately correct compared to the optimal hypothesis in ...
0
votes
1answer
44 views

Weighting function for Non Uniform Learning

Consider a hypothesis class $H = \cup_{n=1}^{\infty} H_n$, where for every $n\in N$, $H_n$ is finite. Find a weighting function $w : H ->[0, 1]$ such that $\sum_{h \in H} w(h) ≤ 1$ and so that for ...
1
vote
1answer
24 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 ...
0
votes
0answers
10 views

OR functions and SQ-Learning

Anyone can describe or give a reference which has a clear description and detailed proof of the SQ-Learning algorithm for the OR class of Boolean functions?
2
votes
0answers
29 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 ...
1
vote
0answers
38 views

What are good examples of computational theories for A.I. according to David Marr's Definition?

I was reading David Marr's "Artificial Intelligence-A Personal View" and he talks about "computational theory of AI" or what he laters labels as "Type 1" Theory. He provides the example of Chomsky's ...
1
vote
1answer
211 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
1answer
34 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 ...
2
votes
0answers
52 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 ...
5
votes
1answer
95 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)| \...
1
vote
1answer
206 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 ...
2
votes
1answer
30 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 ...
1
vote
0answers
117 views

Learning curve for model selection [closed]

I'm a newbie in machine learning field. And I need to choose the best model for my classification model, so i use "learning curve" from sk-learn to make selection. I train and plot learning curve on ...
1
vote
1answer
40 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 ...
2
votes
1answer
1k 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).
2
votes
0answers
250 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 ...
7
votes
0answers
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. ...
0
votes
0answers
39 views

Is feasible learning using just one algorithm and just one class of functions?

Suppose that in an enterprise there is a section specialized in data prediction problems, and to make easier the software maintainance, the next decision is taken: it will be used only one algorithm ...
2
votes
1answer
216 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 ...
3
votes
1answer
70 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 ...
4
votes
0answers
52 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) |...
6
votes
2answers
288 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 ...
3
votes
1answer
371 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 ...
1
vote
1answer
59 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 ...
1
vote
0answers
112 views

Is SRM necessary to prove that a countable union of agnostic PAC learnable classes is nonuniformly learnable?

The following I believe is a direct proof of this fact. If a learner is tasked to be $\epsilon$-competitive with a hypothesis $h \in \mathcal H_n$, where $\mathcal H_n$ is agnostic PAC learnable, it ...
0
votes
0answers
43 views

Is there a non-linear version of ICA?

"Independent Component Analysis" is this : someone is sampling a random vector $s \in \mathbb{R}^d$ such that all its components $s_i$ are mutually independent and $\mathbb{E}[s_i^4] < 3$ and the ...
1
vote
0answers
117 views

Why is it NP-hard to learn a disjunction of k variables as a disjunction of fewer than k log n variables?

I'm looking at the claim in An algorithmic theory of learning: Robust concepts and random projection by R. I. Arriaga and S. Vempala (2006): Further, it is NP-hard to learn a disjunction of k ...
0
votes
1answer
287 views

VC dimension of monotone disjunctions of length k over n variables?

There are of course $n \choose k$ monotone disjunctions which bounds the VC dimension at $\log_2 {n \choose k}$. I'm wondering if this is bound at $k \log_2 n$? (Possibly follows from combinatorial ...
2
votes
1answer
856 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 ...
3
votes
1answer
31 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 ...
2
votes
1answer
89 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$. ...
0
votes
1answer
99 views

A clarification on the taxonomy of Evolutionary Algorithms

A rather basic question but I am confused about the characterization of a certain local search method which I want to describe in the framework of EAs. In particular, consider an EA which in every ...
7
votes
2answers
893 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$ ...
0
votes
1answer
849 views

How do I continue learning programming, beyond the basics? [closed]

DISCLAIMER: I understand that I might not be posting in the right part of StackExchange, or this question might have been asked before (I haven't found it). If this offends anybody, I apologize. I'm ...
1
vote
0answers
148 views

Sample Complexity for Real-Valued PAC-Learnable Functions

Can anyone shed some light on how the VC Dimension affects the sample complexity bounds of infinite hypothesis classes with real-valued outputs in PAC learning, or how to calculate the sample ...
4
votes
1answer
2k 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 ...
-1
votes
1answer
373 views

Training Error & Convergence to True Error

I Take some online class for Machine Learning. one of teacher say this sentence. if we have m data points, the training error converges to the true error as m → ∞. i thought, this sentence not ...
1
vote
3answers
577 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 ...
-1
votes
1answer
64 views

Policy function π in Reinforcement learning unclear

I have one question about policy function in Reinforcement learning. in fact this function indicates which action should be done in each state? Or this function indicate for get the ...
1
vote
0answers
107 views

If one hypothesis class is a proper subset of another, what is the relation of their VC dimensions?

Assume two hypotheses classes $H_A\subset H_B$ defined over the same instance space $\delta$. Assume also $VC(H_A)=d$, does this mean $VC(H_B)\geq d$ ? where $VC$ is the VC dimension. We can use the ...
1
vote
1answer
480 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}$ )...
6
votes
0answers
119 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\}...
6
votes
2answers
419 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}{\...
3
votes
2answers
268 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{...
2
votes
1answer
130 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$ ...
6
votes
2answers
247 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 ...
4
votes
2answers
2k 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 "...