Questions tagged [computational-learning-theory]

For questions related to computational learning theory (or, in short, learning theory), which is a research subfield of artificial intelligence devoted to studying the design and mathematical analysis of machine learning algorithms. Computational learning theory (COLT) is largely concerned with computational and data efficiency. A seminal paper in COLT is Valiant's "A theory of the learnable" (1984).

Filter by
Sorted by
Tagged with
2
votes
1answer
52 views

A model for each sub-problem vs one model for the whole problem

Let's say one wants to use a neural net to learn some function $g(x)$. Let's say that we know that $g$ is a combination of two functions (or two sub-problems), $g(x)=f_2(f_1(x))$, and that we have two ...
2
votes
1answer
96 views

An infinite VC dimensional space vs using hierarchical subspaces of finite but growing VC dimensions

I have the following scenario. I have a binary classification problem, whose underlying function is a step function. The probability distribution of feature vectors is a uniform over the domain. Case ...
2
votes
1answer
170 views

How can neural networks approximate any continuous function but have $\mathcal{VC}$ dimension only proportional to their number of parameters?

Neural networks typically have $\mathcal{VC}$ dimension that is proportional to their number of parameters and inputs. For example, see the papers Vapnik-Chervonenkis dimension of recurrent neural ...
2
votes
0answers
67 views

How to Prove This Inequality, Related to Generalization Error (Not Using Rademacher Complexity)?

This is an inequality on page 36 of the Foundations of Machine Learning by Mohri, but the author only states it without proof. $$ \mathbb{P}\left[\left|R(h)-\widehat{R}_{S}(h)\right|>\epsilon\right]...
1
vote
0answers
13 views

Characterize the high probability bound for learning algorithm

Suppose we have a dataset $S = (x_1, \dots x_n)$ drawn i.i.d from distribution $D$, a learning algorithm $A$ and error function $err$. The performance of $A$ is therefore defined by the error/...
5
votes
1answer
739 views

What are some resources on computational learning theory?

Pretty soon I will be finishing up Understanding Machine Learning: From Theory to Algorithms by Shai Ben-David and Shai Shalev-Shwartz. I absolutely love the subject and want to learn more, the only ...
0
votes
2answers
76 views

Why was the VC dimension not defined for all configurations of $d$ points?

Let's start with a typical definition of the VC dimension (as described in this book) Definition $3.10$ (VC-dimension) The $V C$ -dimension of a hypothesis set $\mathcal{H}$ is the size of the ...
0
votes
1answer
68 views

Is it possible to overfit a model on infinite amounts of data?

This is a theoretical question. Is it possible to overfit a model on infinite amounts of data? Let me clarify there are no duplicates. Say, we have a generator function that produces data, with the ...
3
votes
1answer
173 views

What's the difference between estimation and approximation error?

I'm unable to find online, or understand from context - the difference between estimation error and approximation error in the context of machine learning (and, specifically, reinforcement learning). ...
2
votes
1answer
36 views

What is meant by "stable training" of a deep learning model?

I have read it said that the "stable training" of a deep learning model is important. What is meant by "stable training" of a deep learning model?
2
votes
1answer
262 views

How do I prove that $\mathcal{H}$, with $\mathcal{VC}$ dimension $d$, shatters all subsets with size less than $d-1$?

If a certain hypothesis class $\mathcal{H}$ has a $\mathcal{VC}$ dimension $d$ over a domain $X$, how can I prove that $H$ will shatter all subsets of $X$ with size less than $d$, i.e. $\mathcal{H}$ ...
2
votes
3answers
87 views

How would you intuitively but rigorously explain what the VC dimension is?

The VC dimension is a very important concept in computational/statistical learning theory. However, the first time you read its definition, you may not immediately understand what it really represents ...
1
vote
0answers
12 views

Does distribution of data augmentation parameters matter?

Idea Let's say we have simple pictures dataset containing 40x40 images of digits. We have only one image of each digit. We want to use that as training set, but we need more data, so we use data ...
1
vote
1answer
228 views

Minimum number of perceptrons for an n-bit truth table?

Suppose I have a Boolean function that maps N bits to one bit. If I understand correctly, this function will have $2^{2^N}$ possible configurations of its truth table. What is the minimum number of ...
3
votes
0answers
119 views

How to show Sauer's Lemma when the inequalities are strict or they are equalities?

I have the following homework. We proved Sauer's lemma by proving that for every class $H$ of finite VC-dimension $d$, and every subset $A$ of the domain, $$ \left|\mathcal{H}_{A}\right| \leq |\...
5
votes
2answers
120 views

Is it possible to control asymptotic behaviour of neural network models?

Is it possible to specify what the asymptotic behaviour of a Neural Networks (NN) model should be? I am thinking of a NN which tries to learn a mapping $\vec y=f(\vec x)$ with $\vec x$ a vector of ...
2
votes
0answers
53 views

What is the effect of K in K-NN on the VC dimension?

What is the effect of K in K-NN on the VC dimension? When K increases, is the VC dimension decreased or increased, or we can't say anything about this? Is there a reference book that discusses this?
2
votes
2answers
67 views

In classification, how does the number of classes affect the model size and amount of data needed to train?

When solving a classification problem with neural nets, be it text or images, how does the number of classes affect the model size and amount of data needed to train? Are there any soft or hard ...
1
vote
0answers
33 views

How can I estimate the minimum number of training samples needed to get interesting results with WGAN?

Let's say we have a WGAN where the generator and critic have 8 layers and 5 million parameters each. I know that the greater the number of training samples the better, but is there a way to know the ...
1
vote
0answers
53 views

Can an ML model sort a random sequence of numbers from 1 to $ 2^{2^{512}} $ in our universe in infinite time?

I am pondering on the question in the title. As a human being, somehow I can sort a random sequence of numbers from 1 to $ 2^{2^{512}} $ in our universe in infinite time (But I am not sure.). Can an ...
4
votes
1answer
128 views

Does a neural network exist that can learn every possible training data?

The universal approximation theorem states, that a feed-forward network with a single hidden layer containing a finite number of neurons can approximate continuous functions on compact subsets of $R^n$...
5
votes
2answers
1k views

What are other examples of theoretical machine learning books?

I am looking for a book about machine learning that would suit my physics background. I am more or less familiar with classical and complex analysis, theory of probability, сcalculus of variations, ...
7
votes
3answers
2k views

What is the difference between hypothesis space and representational capacity?

I am reading Goodfellow et al Deeplearning Book. I found it difficult to understand the difference between the definition of the hypothesis space and representation capacity of a model. In Chapter 5,...
5
votes
2answers
515 views

How to estimate the capacity of a neural network?

Is it possible to estimate the capacity of a neural network model? If so, what are the techniques involved?
9
votes
3answers
392 views

Are there any rules of thumb for having some idea of what capacity a neural network needs to have for a given problem?

To give an example. Let's just consider the MNIST dataset of handwritten digits. Here are some things which might have an impact on the optimum model capacity: There are 10 output classes The inputs ...
1
vote
1answer
125 views

Is the VC Dimension meaningful in the context of Reinforcement Learning?

Is the VC dimension meaningful for reinforcement learning (RL), as a machine learning (ML) method? How?
1
vote
1answer
94 views

If a neural network is a universal function approximator, can it have any prior beliefs?

Let us confine ourselves to the case where we have a $n$ dimensional input and a $+1$ or $-1$ output. It can be shown that: For every $n$, there exists a dense NN of depth 2, such that it contains ...
2
votes
1answer
38 views

What does the notation $[m]=\{1, \ldots, m\}$ mean in the equation of the empirical error?

The empirical error equation given in the book Understanding Machine Learning: From Theory to Algorithms is My intuition for this equation is: total wrong predictions divided by the total number of ...
10
votes
2answers
606 views

What are the learning limitations of neural networks trained with backpropagation?

In 1969, Seymour Papert and Marvin Minsky showed that Perceptrons could not learn the XOR function. This was solved by the backpropagation network with at least one hidden layer. This type of network ...
4
votes
2answers
172 views

Mathematical foundations of the ability to learn

I am an undergraduate student in applied mathematics with an interest in artificial intelligence. I am currently exploring topics where I could do research. Coming from a mathematical background I am ...
2
votes
1answer
83 views

Is there anything theoretically revolutionary about Deep Neural Networks?

In recent years, we have seen quite a lot of impressive display of Deep Neural Network (DNN), as demonstrated most famously by AlphaGo and its cousin programs. But if I understand correctly, deep ...
3
votes
2answers
174 views

Will a neural network always predict the correct label if it sees the exact same input during training and testing?

If I'm performing a text classification task using a model built in Keras, and, for example, I am attempting to predict the appropriate tag for a given Stack Overflow question: How do I subtract 1 ...
10
votes
0answers
161 views

What is the number of neurons required to approximate a polynomial of degree n?

I learned about the universal approximation theorem from this guide. It states that a network even with a single hidden layer can approximate any function within some bound, given a sufficient number ...
5
votes
4answers
1k views

How does size of the dataset depend on VC dimension of the hypothesis class?

This might be a little broad question, but I have been watching Caltech youtube videos on Machine Learning, and in this video prof. is trying to explain how we should interpret the VC dimension in ...
1
vote
2answers
401 views

What is the difference between a learning algorithm and a hypothesis?

What's the distinction between a learning algorithm $A$ and a hypothesis $f$? I'm looking for a few concrete examples, if possible. For example, would the decision tree and random forest be considered ...
1
vote
1answer
161 views

How can a machine learning problem be reduced as a communication problem?

I once heard that the problem of approximating an unknown function can be modeled as a communication problem. How is this possible?
0
votes
0answers
21 views

Utilizing continuous variables in concept learning algorithms

Suppose I'm using the Spambase dataset, with 57 real continuous variables and one binary label, and I'd like to implement the Find-S or LGG or similar algorithms. How do I represent the dataset for ...
2
votes
1answer
143 views

How does the number of stacked LSTM layers or units in each layer affect the model complexity?

I playing around sequence modeling to forecast the weather using LSTM. How does the number of layers or units in each layer exactly affect the model complexity (in an LSTM)? For example, if I ...
1
vote
0answers
20 views

Given a dataset and a neural network, is there some heuristic or theorem to determine whether this neural network has enough capacity? [duplicate]

What is the consensus regarding NN "capacity" or expressive power? I remember reading somewhere that expressive power grows exponentially with depth, but I cannot seem to find that exact ...
5
votes
3answers
3k views
2
votes
4answers
951 views

How do you distinguish between a complex and a simple model in machine learning?

How do you distinguish between a complex and a simple model in machine learning? Which parameters control the complexity or simplicity of a model? Is it the number of inputs, or maybe the number of ...
1
vote
1answer
67 views

What is the representational capacity of a learning algorithm? [duplicate]

The definition I see for representational capacity is "the family of functions the learning algorithm can choose from when varying the parameters in order to reduce a training objective." (...
1
vote
1answer
77 views

Does this $\max$ mean that we need to maximize the regret in this regret formula?

I found that the regret in Online Machine Learning is stated as: $$\operatorname{Regret}_{T}(h)=\sum_{t=1}^{T} l\left(p_{t}, y_{t}\right)-\sum_{t=1}^{T} l\left(h(x), y_{t}\right),$$ where $p_t$ is the ...
4
votes
1answer
92 views

In deep learning, do we learn a continuous distribution based on the training dataset?

At least at some level, maybe not end-to-end always, but deep learning always learns a function, essentially a mapping from a domain to a range. The domain and range, at least in most cases, would be ...
1
vote
0answers
39 views

How estimate the minimum size of an autoencoder to overfit the training data?

Given e.g. $1$M vectors of $1000$ floating points each, where every point in vectors is sampled from a uniform distribution between $-1$ to $1$, how to estimate the minimum network size required ...
2
votes
1answer
66 views

Is there any practical application of knowing whether a concept class is PAC-learnable?

A concept class $C$ is PAC-learnable if there exists an algorithm that can output a hypothesis with probability at least $(1-\delta)$ (the "probably" part), and an error that is less than $\epsilon$ (...
7
votes
2answers
145 views

Can we teach an artificial intelligence through sentences?

Could we teach an AI with sentences such as "ants are small" and "the sky is blue"? Is there any research work that attempts to do this?
1
vote
1answer
52 views

Why is probability that at least one hypothesis out of $k$ being consistent with $m$ training examples $k(1- \epsilon)^m$?

My question is actually related to the addition of probabilities. I am reading on computational learning theory from Tom Mitchell's machine learning book. In chapter 7, when proving the upper bound ...
1
vote
0answers
58 views

What is the relationship between PAC learning and classic parameter estimation theorems?

What are the differences and similarities between PAC learning and classic parameter estimation theorems (e.g. consistency results when estimating parameters, e.g. with MLE)?
1
vote
1answer
122 views

What do we mean by saying "VC dimension gives a LOOSE, not TIGHT bound"?

From what I understand VC dimension is what establishes the feasibility of learning for infinite hypothesis sets, the only kind we would use in practice. But, the literature (i.e. Learning from Data)...