Questions tagged [learning-theory]
Questions about the design and analysis of machine learning algorithms.
87
questions
0
votes
1
answer
85
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 ...
CommunityBot
- 1
0
votes
0
answers
17
views
Transductive Information Maximization vs classification with feature embedding in higher dimensional spaces?
Recent research work has shown that transductive learning/inference outperforms standard methods that were used before, where people embed features in a high dimensional space and then use the ...
- 53
0
votes
1
answer
96
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$, ...
CommunityBot
- 1
2
votes
1
answer
38
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 $...
CommunityBot
- 1
1
vote
1
answer
87
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 ...
CommunityBot
- 1
1
vote
0
answers
24
views
Transductive Learning vs Inductive Learning in Machine Learning
Several recent research work has shown that transductive learning/inference outperforms inductive learning/inference during classification problems. This has been found in few-shot learning, other ...
- 53
0
votes
0
answers
41
views
Question about the proof for the sample complexity of axis-aligned rectangles
The classical proof for the sample complexity of the hypothesis class of axis-aligned rectangles usually begins by stating that our $A(S) \subset R^*$, where $R^*$ is the target function. My only ...
1
vote
0
answers
116
views
Infinite VC Dim not PAC learnable
This is usually shown by an application of the Statistical No Free Lunch Theorem.
But is this possible to show this by working simply with the definition of PAC learnability and the sample complexity ...
- 11
0
votes
2
answers
2k
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 ...
1
vote
0
answers
53
views
Regarding constant * opt approximation in agnostic learning
In standard agnostic learning, we assume that there is a concept class $H\subseteq \{h:\{0,1\}^n\rightarrow \{0,1\}\}$. Given samples from a distribution $D:\{0,1\}^n\times \{0,1\}\rightarrow [0,1]$, ...
- 315
2
votes
0
answers
61
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 ...
- 274k
6
votes
2
answers
510
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 ...
- 136
1
vote
0
answers
36
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 ...
- 11
2
votes
1
answer
176
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 ...
- 274k
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 ...
- 1
1
vote
0
answers
99
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 ...
- 11
1
vote
1
answer
48
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 \...
- 274k
1
vote
0
answers
27
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 ...
- 274k
0
votes
1
answer
124
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 ...
- 12.3k
2
votes
1
answer
53
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. ...
- 73
0
votes
1
answer
51
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 ...
D.W.♦
- 154k
3
votes
1
answer
97
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:
...
- 13.3k
0
votes
1
answer
70
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)...
- 13.3k
1
vote
0
answers
96
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 ...
- 65
2
votes
1
answer
101
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 ...
- 274k
1
vote
0
answers
30
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\|_{...
- 215
1
vote
1
answer
140
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, ...
- 274k
0
votes
0
answers
131
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{...
- 274k
1
vote
1
answer
348
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 ...
- 65
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).
- 56
0
votes
1
answer
422
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_{\...
- 11
0
votes
0
answers
112
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, ...
- 101
2
votes
1
answer
66
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 ...
- 274k
3
votes
1
answer
208
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 ...
- 6,873
0
votes
1
answer
56
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 ...
- 3,562
1
vote
1
answer
50
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 <...
- 1,569
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 ...
- 203
1
vote
0
answers
77
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 ...
CommunityBot
- 1
0
votes
1
answer
188
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 ...
- 41
1
vote
0
answers
22
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 ...
- 11
1
vote
1
answer
97
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 ...
- 274k
0
votes
1
answer
248
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 ...
D.W.♦
- 154k
1
vote
1
answer
30
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 ...
- 653
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. ...
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 ...
- 81.4k
1
vote
1
answer
650
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 ...
CommunityBot
- 1
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 ...
- 121
1
vote
0
answers
68
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 ...
- 2,970
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 ...
- 1,381
5
votes
1
answer
193
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)| \...
CommunityBot
- 1