Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [learning-theory]

Questions about the design and analysis of machine learning algorithms.

1
vote
1answer
23 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
6 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?
-1
votes
0answers
17 views

Understanding the computational power of neural networks

It is known that a recurrent neural network with rational weights is computationally equivalent to a Turing Machine (a proof can be found in this paper). I don't understand how is it possible, it ...
2
votes
0answers
24 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
24 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
99 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 ...
0
votes
0answers
11 views

Learning evolutionary structure of a network

I know that structure learning in a probabilistic graphical model can be hard in general and needs exponential data. Are there some results that if have some assumptions about the underlying structure,...
1
vote
1answer
33 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
50 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
71 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
108 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
88 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
37 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
685 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).
3
votes
0answers
192 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 ...
6
votes
0answers
1k 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 ...
3
votes
1answer
174 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
61 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
41 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) |...
7
votes
2answers
235 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
260 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
50 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
79 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
40 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
103 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
227 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
611 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
30 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
66 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
93 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
706 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
750 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 ...
0
votes
0answers
129 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
1k 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
309 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
467 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
63 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
97 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
358 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
116 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
410 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
208 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
117 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
238 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
1k 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 "...
8
votes
1answer
722 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 ...
2
votes
1answer
1k 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 ...
32
votes
2answers
2k 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 ...