Questions tagged [machine-learning]

Theoretical questions about Machine learning, especially Computational Learning Theory, including Algorithmic Learning Theory, PAC learning, and Bayesian Inference

Filter by
Sorted by
Tagged with
-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), ...

1
2 3 4 5
7