The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
1answer
20 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
13 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
26 views

Structural risk minimization erratum in Understanding Machine Learning Theorem 7.4?

Firstly define for a hypothesis class $\mathcal H_n$ with uniform convergence with sample complexity $m_{\mathcal H_n}^{UC}(\epsilon,\delta)$ the following function: $\epsilon_n(m,\delta) := \min\{\...
0
votes
0answers
31 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
50 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
38 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
30 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 ...
0
votes
0answers
14 views

Memory storage capacity of Bienenstock-Cooper-Munro rule

I would like to know the memory storage capacity of the BCM learning rule when it is implemented on a Hopfield network. I understand that it will be a function of n where n is the number of neurons.
3
votes
1answer
26 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
34 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
58 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 ...
0
votes
0answers
141 views

An example for a finite hypothesis class which is not PAC learnable?

I know that with a bounded loss function, every finite hypothesis class is PAC learnable. Are there examples for non PAC learnable hypothesis classes with an unbounded loss function?
7
votes
2answers
180 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
206 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
71 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 ...
2
votes
1answer
465 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 ...
-1
votes
1answer
64 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
281 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
51 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
55 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 ...
0
votes
1answer
119 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}$ ...
5
votes
0answers
90 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\}...
5
votes
2answers
255 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
113 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
89 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
168 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 ...
3
votes
1answer
516 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 "...
7
votes
1answer
282 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
984 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 ...
27
votes
2answers
1k 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 ...