Skip to main content

Questions tagged [learning-theory]

Questions about the design and analysis of machine learning algorithms.

37 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9 votes
0 answers
179 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\}...
D.W.'s user avatar
  • 162k
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. ...
malreddysid's user avatar
4 votes
0 answers
84 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) |...
Erel Segal-Halevi's user avatar
2 votes
0 answers
25 views

Representational power of Neural Neural Networks without a bias term

In a fully connected Neural Network, each perceptron has it's bias term $b$ which is learnt. Often (example, in Linear/ Logistic Regression), when we don't want to treat this bias term explicitly, we ...
Harry's user avatar
  • 21
2 votes
0 answers
68 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 ...
Dmitry's user avatar
  • 345
2 votes
1 answer
47 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 $...
Naren's user avatar
  • 43
2 votes
0 answers
43 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 ...
Ilan Aizelman WS's user avatar
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 ...
Plussoyeur's user avatar
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 ...
TomR's user avatar
  • 1,401
2 votes
0 answers
297 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 ...
gdelab's user avatar
  • 136
1 vote
1 answer
30 views

Why we need at most $2n$ examples to determine an axis aligned rectangle

In Ben-David & et al.'s Understanding Machine Learning, the authors wrote: Let $\mathcal{H}_n$ be the class of axis aligned rectangles in $\mathbb{R}^n$ , namely, $$ \mathcal{H}_n = \{h(a_1,\dots,...
Tran Khanh's user avatar
1 vote
0 answers
140 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 ...
Sandra's user avatar
  • 63
1 vote
0 answers
258 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 ...
JustBlaze's user avatar
1 vote
0 answers
54 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]$, ...
postasguest's user avatar
1 vote
0 answers
43 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 ...
Suraj's user avatar
  • 11
1 vote
0 answers
111 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 ...
somefellow's user avatar
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 ...
Francis's user avatar
  • 65
1 vote
0 answers
104 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 ...
brianoconner's user avatar
1 vote
0 answers
34 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\|_{...
Alex's user avatar
  • 215
1 vote
1 answer
98 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 ...
Marnix.hoh's user avatar
1 vote
0 answers
23 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 ...
wwjohnsmith's user avatar
1 vote
0 answers
76 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 ...
Charlie Parker's user avatar
1 vote
0 answers
141 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 ...
djechlin's user avatar
  • 497
1 vote
0 answers
209 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 ...
djechlin's user avatar
  • 497
1 vote
0 answers
202 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 ...
Ashley's user avatar
  • 11
1 vote
0 answers
194 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 ...
seteropere's user avatar
0 votes
0 answers
52 views

Why can't we say that P=NP if we have an infinite text file with solution for every possible SAT combination?

I believe that I have a misunderstanding in the P=NP problem while I was thinking of how can it be proved in a non-constructive manner. We know that we can build an infinitely large text file with ...
TokieSan's user avatar
0 votes
0 answers
25 views

Computational Learning Problem: 3-DNF Reduction

I'm not sure how to solve this problem. Problem statement is: Consider the binary classification problem where X = R d and Y = {0, 1}. Consider the class of Binary classifiers given by intersection of ...
Mr.Zhang's user avatar
0 votes
0 answers
18 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 ...
Sandra's user avatar
  • 63
0 votes
0 answers
46 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 ...
Sophie's user avatar
  • 1
0 votes
1 answer
102 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$, ...
giorgioh's user avatar
  • 317
0 votes
0 answers
146 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{...
brianoconner's user avatar
0 votes
0 answers
132 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, ...
Moher's user avatar
  • 101
0 votes
1 answer
90 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 ...
Arka Pal's user avatar
  • 311
0 votes
0 answers
42 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 ...
ernico's user avatar
  • 1
0 votes
0 answers
79 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 ...
gradstudent's user avatar
-1 votes
1 answer
714 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 ...
Ebraham's user avatar
  • 35