Questions tagged [machine-learning]
Theoretical questions about Machine learning, especially Computational Learning Theory, including Algorithmic Learning Theory, PAC learning, and Bayesian Inference
322
questions
0
votes
0answers
51 views
What is few-shots extrapolation? [migrated]
I'm reading the paper "Learning how to ask" by Qin & Eisner and in the abstract, they mention that using prompts, language models can perform tasks other than text generation. Examples ...
-4
votes
0answers
86 views
Could someone explain the algorithm from this paper?
Trying to get a fair understanding of our artificial immune systems. To do this I’ve been reviewing this paper, but the algorithm and mathematics is over my head, could someone explain the below to me ...
0
votes
2answers
129 views
An (unusual?) risk bound
I am told that that a bound on the generalization error of the following form exists in terms of something called the ``shattering coefficient" - but I am not able to reference this quantity in ...
0
votes
0answers
30 views
Peer Based Machine Learning
Side Note: I originally asked this question on stack overflow but it was closed because apparently it wasn't the right place to ask the question. Please direct me to the right place if you don't think ...
1
vote
1answer
80 views
Generalization bound for parameters rather than loss functions
I was wondering if it is possible to obtain high probability bounds (provided finite sample size of the training data) for the distance (say in the l-1 or l-2 norm) between the best parameter set and ...
2
votes
1answer
68 views
Bayes-consistent cost-sensitive classification
In cost-sensitive classification,
we have a confusion (or cost) matrix
$C$, where $C(i,j)$ is the cost incurred
for predicting label $i$ when nature
specifies $j$. The costs are non-negative,
but no ...
-1
votes
1answer
64 views
No free lunch theorem and finite hypothesis classes
I have read the no free lunch theorem(NFLT) section 5.1 of Understanding machine learning by Shai Shalev-Shwartz. There is also this Corollary 4.6 which states any finite hypothesis class is PAC ...
3
votes
1answer
64 views
Examples of learning via exactly integrable gradient flows
If $\ell (\vec{w}, \vec{z})$ is the loss function at weights $\vec{w}$ and for data $\vec{z}$ then corresponding to a distribution ${\cal D}$ we can consider doing gradient flow with step-length $\eta ...
7
votes
0answers
153 views
A variant of transfer learning
Suppose we want to train $K$ linear classifiers based on iid samples. Each classifier is of the form
$x\mapsto\mathrm{sign}(w\cdot x+\theta)$, with the constraint that the hyperplane $w$ is the same ...
2
votes
1answer
125 views
An invariance theorem for algorithmically random data in statistical learning
Motivation:
The following invariance theorem for statistical learning in the setting of algorithmically random data occurred to me yesterday. This theorem uses the fact that the property of ...
1
vote
0answers
94 views
On the equivalence of incompressibility and incompleteness in machine learning
Motivation:
Motivated by the question of what problems are suitably addressed using methods in machine learning, I decided to formulate this general problem using Algorithmic Information Theory. My ...
1
vote
2answers
86 views
VC generalization bound extended to other types of target functions
In Y. S. Abu-Mostafa's book "Learning from Data", he mentions on page 55 after deriving the VC generalization bound for a binary target function that "it can be extended to other types ...
2
votes
0answers
42 views
Energy-Based Modeling vs Deep Learning
I am doing some research on machine learning algorithms in the context of a seminar, which focuses on Energy-Based Modeling vs Deep Learning specifically in working with images Modeling. Now I know ...
12
votes
2answers
307 views
Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings
We say that a pair $(P,N)$ of subsets of strings from $\{0,1\}^n$ is an $n$-pair if $|P|=|N|=n$. Intuitively, sucha a pair consists of a set $P$ with $n$ positive $n$-bit strings, and a set $N$ with $...
0
votes
1answer
104 views
Generalisations of the Fundamental Theorem of Statistical Learning to different tasks and losses
The fundamental theorem of statistical learning gives an equivalence between uniform convergence of the empirical risk to learning in the PAC framework.
I have only seen this stated in the case of ...
0
votes
1answer
34 views
Machine Learning: Calibrating SubGroups of Probability Predictions inside a Dataset which should sum to 100%
I am working on an interesting type of problem where I want to make predicitons for individual elements within subgroups- with the knowledge that the sum of the probabilities within a subgroup should ...
1
vote
1answer
115 views
VC-dimension of infinite set of triangle wave
I am searching for the VC-dimension of the following:
What is the VC-dimension of the infinite set of triangle wave functions with
amplitude 1 and period parameter p on points on the line?
2πarcsin(...
1
vote
1answer
257 views
What's the intuition behind Rademacher complexity?
As stated, what exactly is the intuition behind Rademacher Complexity which is defined:
Rademacher complexity captures the richness of a family of functions by measuring the degree to which a ...
-2
votes
1answer
148 views
How to calculate complexity in a high dimensional space?
Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong.
For a specific f(), I'm defining a term '...
6
votes
1answer
261 views
Is there an equivalent to VC-dimension for density estimation as opposed to classification?
VC-dimension can be used to quantify the capacity for classifier models and compute generalization bounds, but is there an equivalent concept that can be applied to density estimation, e.g. to compute ...
0
votes
1answer
325 views
VC dimension for balanced binary decision trees
What is the VC dimension of all balanced binary decision tree of
depth $k$ in $\{0,1\}^d$? Does it depend on depth $k$ or dimension $d$?
1
vote
1answer
71 views
Rademacher Complexity of the Composition with an Indicator
Consider the statistical learning setting where you have an arbitrary hypothesis space $\mathcal{H}$, a data space $\mathcal{Z}$, and a bounded loss function $\ell: \mathcal{H}\times \mathcal{Z} \...
7
votes
1answer
264 views
Testing for finite expectation
The mean of a positive random variable $X$ is either finite or infinite; define $J(X)$ to be $0$ in the former case and $1$ in the latter case. Claim: there does not exist a function $J_n$ from the ...
2
votes
0answers
87 views
Polynomial convergence to optimal move of the UCT algorithm. Missing proof?
This is a question regarding the theoretical convergence guarantees of the UCT algorithm, a popular variation of the Monte Carlo Tree Search algorithm (used in games, planning, reinforcement learning, ...
1
vote
0answers
47 views
Is there a notion of Probably Approximately Correctness in Unsupervised Learning? [closed]
I've been learning a little bit about computational learning theory, but most of what I've seen so far is related to supervised learning. Perhaps dimensionality reduction will be touched on, but not ...
6
votes
3answers
511 views
Reference Request: Computational Learning Theory
Pretty soon I will be finishing up Understanding Machine Learning by Shai Ben-David and Shai Shalev-Shwartz. I absolutely love the subject and want to learn more, the only issue is I'm having trouble ...
2
votes
1answer
127 views
Why non-uniform learnability does not imply PAC learnability?
PAC guarantees provide us a a learning algorithm $A_n(\cdot)$ and sample complexity bound $n_{\mathcal{F}}(\epsilon,\sigma)$ that ensures
$
P\left[L_P(A(\mathcal{D}^n))-L_P(f^*)\leq \epsilon\right]\...
3
votes
0answers
143 views
Understanding Dudley Chaining Argument for Rademacher Bound
I follow the proof of the Dudley chaining/metric entropy bound of the (empirical) Rademacher complexity, but I don't have any intuition for why this bound should be true. In particular, I don't know ...
7
votes
1answer
321 views
Complexity of constructing minimum depth decision trees
I am interested in the computational complexity of
Problem 1: Given a finite, non-empty set $J$, given $A, B \subseteq \{0,1\}^J$ such that $A \cap B = \emptyset$, and given $n \in \mathbb{N}$, does ...
0
votes
0answers
55 views
Using martingale arguments to prove convergence of iterative algorithms
Can someone give me typical/educative examples of how martingales can be used to prove convergence of an iterative algorithmS?
The examples I know of can only go so far as to show that there exists ...
4
votes
0answers
93 views
Status of the Junta Problem (soft question)
Does the learning theory community in general believe that juntas can be learned in polynomial time?
The naive algorithm works in quasi-polynomial time. MOS's paper shows how to solve the junta ...
5
votes
1answer
204 views
Latest word on cross validation?
It's a standard result leave-one-out cross-validation is an unbiased estimator of the risk (see, e.g., Lemma 4.1 in Mohri, Rostamizadeh, Talwalkar). Are there any "better" results? Such as, say, with ...
4
votes
1answer
269 views
Is this a known learning problem?
Let $(\mathcal{X},\rho)$ be a metric space (say, $\mathcal{X}=[0,1]$ with the Euclidean metric). Let $\alpha:\mathcal{X}\to[0,1]$ be unknown. Suppose that $\mathcal{X}$ is endowed with a distribution $...
0
votes
1answer
119 views
Singular Value in Machine Learning
I'm reading the paper (http://proceedings.mlr.press/v9/glorot10a/glorot10a.pdf) from Glorot and Bengio. There is something that I don't understand at the abstract section on page 1.
"Training may be ...
1
vote
1answer
67 views
Characterize a point cloud
Background: I have multiple point clouds (sets of objects) $\{S_i\}_{i\in\mathbb{N}}$ of variable size and "purity" (meaning that some sets contain very similar objects, some show a high diversity; ...
4
votes
2answers
193 views
What are some good resources for strengthening my theoretical foundation for machine learning?
I'm a computer science major and I'm taking a lot of machine learning courses. I'm finding that my theoretical foundation on subjects like calculus and linear algebra are not as strong as I'd like ...
4
votes
1answer
80 views
Terminology and references for a learning model
Let's say we're doing regression over $[0,1]^d$ -- either in the PAC sense with bounded-range agnostic noise or in the more classical-statistics sense with additive Gaussian noise. Suppose further ...
1
vote
0answers
51 views
Average smoothness learning rates
This question is somewhat related to this one. There are many results in statistics where convergence rates (including minimax ones) are given in terms of the smoothness properties of the underlying ...
0
votes
0answers
74 views
representation of concept classes and pac learning
I was reading the book of Kearns and Vazirani and I didn't completely understand the following:
Let C be a concept class and suppose we want to PAC learn C, they say first consider a larger ...
1
vote
0answers
56 views
Which algorithms can be used to measure similarity for two very different languages?
recently I have read this paper, A Survey of text similarity approaches, and I discovered that there are a lot of algorithms that can be used to measure similarity.
At present I am applying the ...
1
vote
0answers
70 views
Sentences in what kinds of grammar in the Chomsky hierarchy can be parsed by an LSTM of a given size?
Given
an LSTM $N$ of a given size $A$,
a sentence $S$ with a given number of words $B$,
a Chomsky grammar hierarchy level $C$ in 0-3,
a Chomsky grammar $G$ of level $C$ of size $D$,
A given fixed, ...
1
vote
0answers
179 views
Minimum number of hours of speech needed to train a neural net to recognize speech [closed]
From a theoretical computer science point of view, is there a lower limit on the number of hours of speech needed to train a neural net to translate speech to text? An estimate from CMU is 3000-5000 ...
2
votes
0answers
84 views
Which computational framework lies behind the Chinese “Social Credit System”?
BACKGROUND
The Social Credit System is a data-driven reputation system which draws on several sources to label various entities, namely businesses and individual citizens, with a trustworthiness ...
1
vote
0answers
85 views
Agnostic query learning of decision trees
Gopalan, Kalai, Klivans gave an algorithm
https://dl.acm.org/citation.cfm?id=1374376.1374451
for agnostically learning decision trees $h:\{0,1\}^n\to\{0,1\}$ under the uniform distribution given ...
2
votes
1answer
169 views
How many samples are needed to reconstruct a path?
Consider an input set of vertices $V$ and vertices $s,t\in V$.
The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be ...
3
votes
1answer
81 views
Agnostic query learning for DFAs
Angluin's membership+equivalence query algorithm allows to efficiently and exactly learn a target $n$-state DFA. But what if the target DFA is huge, or the target concept is not even a regular ...
0
votes
0answers
117 views
Lower bound to agnostic learning with membership queries
Setting:
Let $X$ be a finite set and $C = \{0, 1\}^X$ a finite family of classifiers on $X$. Fix an $f \in \{0, 1\}^X$ not in $C$, a (possibly randomized and adaptive) learner $A$ has access to a ...
4
votes
1answer
475 views
What was the significance of Leslie Valiant's, “A Theory of the Learnable?”
It seems like two of the main takeaways were that there is a natural limit to what computers can learn, and learning is bounded by polynomial algorithms. Why was his paper significant in the broader ...
-1
votes
2answers
131 views
Machine Learning Algorithm To Fill Data Holes
I'm having trouble finding a good place to begin with this. I'm just looking for a name or point to start researching a
Let's say I have 1000 records. 10 of these records are only 90% complete. The ...
2
votes
1answer
102 views
References on generalization bounds
I'm looking for references (books, papers, lecture notes etc) on generalization bounds and their proofs. Specifically, I'm looking to fully understand the technique of defining a hypothesis class (or ...
