The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
38 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 ...
1
vote
1answer
43 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
15 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
147 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
40 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
17 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
40 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
40 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 ...
5
votes
2answers
101 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 ...
3
votes
2answers
72 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 ...
2
votes
1answer
69 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$ ...
5
votes
2answers
103 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
97 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 ...
6
votes
1answer
128 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
590 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 ...
21
votes
1answer
686 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 ...