Questions tagged [learning-theory]

Questions about the design and analysis of machine learning algorithms.

Filter by
Sorted by
Tagged with
2 votes
0 answers
42 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 ...
user avatar
  • 227
1 vote
0 answers
30 views

Precise definition of Universal Learner in Machine Learning

It is surprising to me that I cannot find a precise definition of universal learner on the internet. I can guess what it should bebut I don't want to make a mistake, therefore I have come here. Here's ...
user avatar
  • 11
1 vote
1 answer
29 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 $...
user avatar
  • 33
2 votes
1 answer
76 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 ...
user avatar
  • 33
0 votes
0 answers
42 views

pseudo-dimension for knapsack problem

Let $v_i, s_i$ be the value and size of item $i$, let $\rho \in \mathbb{R}$, n be the maximum number of items. Then we add items based on $\frac{v_i}{s_i^{\rho}}$ in decreasing order. I was trying to ...
user avatar
  • 1
1 vote
0 answers
73 views

Hoeffding's inequality applicability for sample complexity

I am trying to determine some bounds for sample complexity. Suppose we have a bounded loss function $\ell$ and target function $f:\mathcal{X}\to\mathcal{Y}$. Hypothesis $h$ is learned, then the ...
user avatar
0 votes
1 answer
75 views

A confidence interval algorithm for Disagreement coefficient

My question has to do with the disagreement coefficient in active learning. I've been trying to solve the following question, where I need an algorithm to derive a confidence interval for $\theta$, ...
user avatar
  • 317
1 vote
0 answers
26 views

Applications of derivative only, zeroth-order free optimization

I understand what is derivative-free optimization, and I am thinking a similar problem where the function $f$ we are optimizing is unknown and the only information we can acquire is the derivative. In ...
user avatar
  • 65
0 votes
1 answer
88 views

Pseudo-dimension of a subset of affine functions

Let's say there are two sets of affine functions. $\mathcal{A} = \{ax +b \mid a,b \in \mathbb{R}\}$ $\mathcal{H} = \{2x + 1, x, 3x + 4, 4x\}$ I know that the $\mathrm{Pdim}(\mathcal{A}) = 2$. From ...
user avatar
  • 73
2 votes
1 answer
43 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. ...
user avatar
  • 73
0 votes
1 answer
44 views

Is memorization necessary in learning computer science?

Backgrounds Hi guys, I am now trying to teach myself some basic computer science theories. Specifically, I am using the book, CSAPP (computer systems, from a programmer’s perspective) and 15-213 ...
user avatar
  • 1
3 votes
1 answer
84 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: ...
user avatar
1 vote
1 answer
47 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 \...
user avatar
  • 317
1 vote
0 answers
67 views

Perceptron - Generalization Bounds & Compression Bounds

A distribution $P$ over $\mathbb{R}^{d} \times\{-1,+1\}$ being $(\gamma, R)$ -separable. We now let $\mathcal{P}_{\gamma}$ denote the set of all $(\gamma, 1)$ separable distributions. For a ...
user avatar
0 votes
1 answer
69 views

Compression Bounds - Determine and Visualize for hypothesis vs VC dimension

I want to visualize or calculate the compression bounds for hypothesis classes. I learnt how to figure out the VC dimension. Let's say I define two hypothesis class. For example: $$ H_k = \{h ∈ (0,1)...
user avatar
2 votes
1 answer
94 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 ...
user avatar
1 vote
0 answers
21 views

How is the RKHS norm related to sample complexity or other learning theory properties?

This is a somewhat soft question. Given two reproducing kernel Hilbert spaces (RKHSs) $H_1$ and $H_2$, if their RKHS norms only differ by a constant, i.e., $C_1\|f\|_{H_1}\le \|f\|_{H_2} \le C_2\|f\|_{...
user avatar
  • 215
1 vote
1 answer
79 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, ...
user avatar
0 votes
0 answers
113 views

VC dimension of axis-aligned hyperplanes and their complements

This is a problem of VC that I've been trying to solve. Any help is appreciated. Let's assume hypothesis classes $H_{\mathit{init}}$ of initial segments over domain $X = \mathbb R$ and $H_{\mathit{...
user avatar
1 vote
1 answer
279 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 ...
user avatar
0 votes
1 answer
248 views

What is the VC dimension of the hypothesis class $H=\left\{f_{\theta_{1}, \theta_{2}}: R^{2} \rightarrow\{0,1\} \mid 0<\theta_{1}<\theta_{2}\right\}$?

I would like to know what is the VC dimension of the following hypothesis class. $$H=\left\{f_{\theta_{1}, \theta_{2}}: R^{2} \rightarrow\{0,1\} \mid 0<\theta_{1}<\theta_{2}\right\}$$ where $f_{\...
user avatar
  • 11
1 vote
1 answer
71 views

Method for combining derivative free optimization results of different data inputs

I am working on an algorithm that has multiple fixed parameters. The algorithm analyzes time series data and spits out a number. The fixed parameters need to be such that this number is as small as ...
user avatar
0 votes
0 answers
54 views

Is class of threshold functions Agnostic PAC Learnable?

In "Understanding Machine Learning, From Theory to Algorithms" by Shalev and Ben-David, on page 44 example 6.1, it is proved that the class of threshold functions are PAC learnable. on the other hand, ...
user avatar
  • 101
2 votes
1 answer
60 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 ...
user avatar
3 votes
1 answer
134 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 ...
user avatar
  • 53
0 votes
1 answer
40 views

Uniform Convergence and VC Theroy

I've started reading more about statistical learning theory, specifically this paper right here and I cannot understand the following part: It turns out the conditions required to render empirical ...
user avatar
1 vote
1 answer
47 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 <...
user avatar
  • 111
0 votes
1 answer
1k views

VC dimension of the class of polynomial classifiers of degree $n$

I came across this statement on page 85 of the book "understanding machine learning: from theory to algorithms" The general idea is as follows: Consider a binary classification problem with the ...
user avatar
  • 41
1 vote
0 answers
54 views

How can I understand the multi-class version of "shattering" intuitively? [closed]

I'm learning machine learning. VC dimension is a good way to measure the complexity of hypothesis class for binary classifier and has a very good intuitive explanation from shattering. When we discuss ...
user avatar
  • 41
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 ...
user avatar
0 votes
1 answer
131 views

How do you prove the Natarajan's Lemma intuitively?

Let $H$ be a hypothesis class of multiclass predictors; namely, each $h\in H$ is a function from $X$ to $[k]$. Denote the Natarajan dimension of $H$ by $Ndim(H)$. Hope you can give me an intuitive ...
user avatar
  • 41
1 vote
0 answers
21 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 ...
user avatar
1 vote
1 answer
84 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 ...
user avatar
0 votes
1 answer
215 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 ...
user avatar
  • 113
0 votes
1 answer
75 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 ...
user avatar
  • 301
1 vote
1 answer
28 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 ...
user avatar
  • 243
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 ...
user avatar
1 vote
0 answers
62 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 ...
user avatar
1 vote
1 answer
527 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 ...
user avatar
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 ...
user avatar
  • 1,016
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 ...
user avatar
  • 1,351
5 votes
1 answer
174 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)| \...
user avatar
1 vote
1 answer
406 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 ...
user avatar
2 votes
1 answer
35 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 ...
user avatar
  • 21
1 vote
0 answers
161 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 ...
user avatar
  • 111
1 vote
1 answer
44 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 ...
user avatar
  • 211
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).
user avatar
  • 123
2 votes
0 answers
293 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 ...
user avatar
  • 136
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. ...
user avatar
0 votes
0 answers
40 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 ...
user avatar
  • 1