Questions tagged [machine-learning]
Theoretical questions about Machine learning, especially Computational Learning Theory, including Algorithmic Learning Theory, PAC learning, and Bayesian Inference
321
questions
-4
votes
0answers
37 views
Consequence of $CLS=PPAD\cap PLS$
https://arxiv.org/abs/2011.01929 claims $CLS=PPAD\cap PLS$ and it is appearing in http://acm-stoc.org/stoc2021/accepted-papers.html (STOC $2021$) which bolsters its validity.
Is there implications to ...
-1
votes
0answers
33 views
How shall backpropagation manage multiple patterns?
There is an algorithm taken from this source which implements calculation of a gradient of the cost function for each weight in a neural network:
This algorithm happened to do well. We can subtract ...
-3
votes
0answers
25 views
Where should I refer the models used in my dissertation, in the literature review or methodology?
I'm currently writing a computer science dissertation about Cryptocurrency Price Forecasting using Machine Learning Algorithms.
The models I used are from sklearn and, unlike many other papers I have ...
2
votes
1answer
55 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
61 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
61 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
140 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 ...
1
vote
1answer
104 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
87 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
79 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
298 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
61 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
31 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
106 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
189 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
145 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
237 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
273 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
65 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
261 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
75 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, ...
0
votes
0answers
44 views
Would a machine learning algorithm benefit from an “optimization oracle”?
I'm trying to understand the behavior of machine learning algorithms where the loss function is non-convex and the problem of training the ML on a specific data set is computationally hard.
Now let'...
1
vote
0answers
43 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
481 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
113 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
129 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
304 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
51 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
87 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
203 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
265 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
118 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
63 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
185 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
50 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
71 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
55 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
69 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
156 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
82 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
79 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
116 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
426 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
107 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 ...
0
votes
1answer
37 views
Classic Neural Network Layout for regression: is the score function derivable?
I need to solve an optimization problem based on a function f(X). This function is not known, but it can be estimated from a training set. So first I train a model, then I get the score function f(X), ...
