Questions tagged [machine-learning]
Theoretical questions about Machine learning, especially Computational Learning Theory, including Algorithmic Learning Theory, PAC learning, and Bayesian Inference
365
questions
6
votes
2
answers
657
views
Learning a coin's bias (localized)
It's well known that the minimax sample complexity for estimating the bias $p$ of a coin to additive error $\epsilon$ with confidence $\delta$ is
$\Theta(\epsilon^{-2}\log(1/\delta))$. What if we ...
- 10.5k
4
votes
1
answer
278
views
Adversarial Machine Learning, Learning with (Malicious) noise
I am reading some old papers regarding Learning With Malicious Noise. In one of them, Learning in the presence of Malicious Errors, by Kearns and Li $[1]$ (https://www.cis.upenn.edu/~mkearns/papers/...
- 51
6
votes
2
answers
779
views
Applications of Takens' theorem to TCS?
My apologies if the question is a tad vague—I did try to search the literature for more, but didn't find anything (the similarity between the keywords "Takens" and "taken" on Google may be partly to ...
- 4,461
6
votes
1
answer
542
views
Textbook/resources for a beginning researcher in (Machine) Learning Theory
I'm looking to begin understanding basic concepts, notions, results and definitions in the area of Computational Learning Theory (or the theory of Machine Learning), as is done in the theoretical ...
- 123
1
vote
0
answers
185
views
Boolean functions with high query complexity for PAC learning
The most general theorem for PAC learning of Boolean functions that I am aware of is the theorem in section 3.4 of Ryan O'Donnel's book where its basically shown that Boolean functions whose Fourier ...
- 1,453
4
votes
0
answers
1k
views
Universal Approximation Theorem for non-sigmoidal activation functions
The most cited Universal Approximation Theories for multi-layer feedforward neural networks by Cybenko (1989) and Hornik (1991) assume the activation functions of the network to be sigmoidal. However, ...
- 41
1
vote
0
answers
202
views
Off-policy Monte Carlo Control
The off-policy Monte Carlo control algorithm to learn the optimal state-value function $V^*$ is given as follows, which is obtained from Sutton's book.
I have three questions concerning this ...
- 451
24
votes
2
answers
791
views
If machine learning techniques keep improving, what's the role of algorithmics in the future?
Let's look at the future some 30 years from now. Let's be optimistic and assume that areas related to machine learning keep developing as quickly as what we have seen in the past 10 years. That would ...
- 11.5k
-2
votes
1
answer
122
views
Supervised learning from "bad" examples - ANN [closed]
I want to recommend one of three possible treatments for a patient, based on his blood values A, B and C.
To solve this task, I have constructed a supervised feed-forward NN with back-propagation (...
- 113
3
votes
1
answer
1k
views
Examples of Fat-Shattering Dimension
What are some good examples for analysis of a class's Fat-Shattering dimension?
By (Alon et al) I know that the Fat-Shattering Dimension characterizes the learnability of real-valued function classes ...
- 168
-1
votes
1
answer
324
views
What is the connection between adversarial learning in machine learning and program synthesis?
In particular, I'm considering the similarities in Generative Adversarial Networks and Combinatorial Sketching for Finite Programs.
In the first paper, our concern is with learning generator ...
- 1,572
6
votes
0
answers
102
views
Looking for an easy/pedantic exposition of Renegar's famous result on polynomial optimization
In September $1989$, Renegar had this famous sequence of 3 papers titled, "On the Computational Complexity and Geometry of the First-order Theory of the Reals, Part I/II/III". I was wondering if ...
- 1,453
1
vote
0
answers
17
views
Can the distribution over the squared moduli of the 'probabilities' defined by an RBM with complex weights be written as an RBM with real weights? [closed]
I posted this question originally on the math boards, but figured it would be better suited here.
https://math.stackexchange.com/questions/2203967/can-the-distribution-over-the-squared-moduli-of-the-...
- 111
3
votes
1
answer
145
views
Minimax agnostic risk for Lipschitz functions
For $L>0$, let $F_L$ be the class of all $L$-Lipschitz functions on $[0,1]$. Let $D$ be a joint distribution on $[0,1]\times\mathbb{R}$, from which we sample $n$ iid copies $(X_i,Y_i)$. Given any $...
- 10.5k
4
votes
1
answer
192
views
Kleinberg-consistency of spectral clustering
Spectral clustering refers to a family of graph-based algorithms, which usually rely on a similarity function rather than a metric, though a metric $\rho(x,y)$ can always be converted to a similarity ...
- 10.5k
2
votes
1
answer
124
views
Upper bound on the size of a Concept Lattice (Galois Lattice)?
A context is a tuple $(O, A, R)$ where $O$ is the set of objects, $A$ the set of attributes and $R \subseteq O\times A$ is a relation. For $o \in O$ and $a \in A$ we read $oRa$ as the object $o$ ...
- 427
-2
votes
1
answer
136
views
Can Pattern Recognition algorithms be considered Oracle Machines (in the Turing sense)?
I was reading Paul Churchland's "Engine of Reason, Seat of the Soul", where argues that humans (and potentially artificial neural networks as well) are capable of non-Turing computation because they ...
- 301
-2
votes
2
answers
157
views
Machine Learning: How ML algorithms build classification rules [closed]
I am truly fascinated by algorithms learning on their own with a little help from humans and as a newbie in this field (with programming experience mainly in C/C++), seek your help to obtain the big ...
- 107
2
votes
0
answers
90
views
How does white noise on the output channels influence the training of a neural network?
Let $\rho(\sigma): \mathbb{R} \rightarrow \mathbb{R}$ be a probability density that is parametrized by a parameter vector $\sigma \in \mathbb{R}^s$ (for example the normal distribution where $s = 1$ ...
- 121
2
votes
1
answer
165
views
Learning from derivative data
In many machine learning algorithm, it is often assumed that outputs of unknown function and their corresponding inputs are given to estimate the unknown function. However, I wonder whether there ...
54
votes
5
answers
6k
views
What kind of answer does TCS want to the question "Why do neural networks work so well?"
My Ph.D. is in pure mathematics, and I admit I don't know much (i.e. anything) about theoretical CS. However, I have started exploring non-academic options for my career and in introducing myself to ...
- 649
1
vote
0
answers
72
views
A well-known instance of overcomplete dictionaries
sparse representation is:
A signal can be represented as a linear combination of basis functions where the set of basis functions is called dictionary and data samples are much more than their ...
- 141
5
votes
0
answers
252
views
What precisely is the extra power afforded by using deeper nets?
For any choice of activation function (fix the choice for all the hidden nodes for both the following DNNs) do we know of functions which some $k$ (hidden layer) DNN can compute but a $(k-1)-$DNN can'...
- 1,453
0
votes
1
answer
523
views
Serial and parallel neural network [closed]
The question is: can exist a parallel or serial neural network or someone talked about this?
For explanation, in the network a single record in a data set enter in the input layer as a value between ...
- 11
2
votes
2
answers
922
views
Convergence and representation theorems for machine learning
I come from a pure math background and am not very familiar with machine learning. So, I'll start with an example to compensate for my confused grasp of the terminology.
Let's say we have a function $...
- 247
2
votes
1
answer
355
views
Are biases necessary to make neural networks universal approximators when using sigmoid activations?
In a neural network, a bias is a constant term that is added to the weighted input in a neuron/unit:
output = activation_function( input1*weight1 + ... + inputn*weightn + bias)
I can see that the ...
- 123
4
votes
0
answers
104
views
Adversarial distributions for PAC lower bounds
The various PAC lower bounds (realizable, agnostic, bounded noise) construct distributions supported on $d$ points, where $d$ is the VC-dimension of the hypothesis class in question.
Does anyone ...
- 10.5k
-2
votes
1
answer
108
views
Can you use only the first summation term of cost function for typical logistic regression?
I have recently come across a Matlab implementation that appears to be using only the first term (i.e. in itself a product) of the typical logistic regression cost function.
...
- 105
2
votes
0
answers
170
views
About lower bounding the sample complexity of a distribution
Given a joint probability distribution over a finite number of random variables (each with a finite range space) of which only a certain subset is observable, is there a notion of "sample complexity" ...
- 654
6
votes
0
answers
169
views
Machine learning algorithms on hypergrap models
Graphical models are a very useful tool with many applications,
whereby a joint distribution of a set of random variables is modeled
using only pairwise dependencies between the variables, and
two ...
- 359
5
votes
1
answer
122
views
Generalization bounds for multiclass learning when the output is vector space?
There are plenty of results for muli-class learning with with fixed discrete labels:
$$
\text{Standard multi-class classification:}
\begin{cases}
f: X \rightarrow Y_{index} = \{1, 2, 3, ..., k \}, \\ ...
- 749
0
votes
1
answer
94
views
The dependence of learning generalization bounds on the dimension of the instance space
Here is a popular generalization bound:
If $X$ is the input space and
$Y=\{0, 1\}$ is the output/label space, and
there is a joint distribution $D$ defined on this space.
We sample $m$ ...
- 749
2
votes
0
answers
71
views
Impossibility result on metric learning?
Are there any fundamental limitations (impossibility results) known for metric learning?
Are there any direct connection reduction from/to that I can use results in clustering? (e.g. this: 2 )
2 ...
- 749
8
votes
1
answer
455
views
Competing against an optimal weighted majority in experts algorithm
In the experts problem, $n$ experts give you binary predictions on a daily basis, and you have to predict whether it's going to rain tomorrow.
That is, at day $t$, you know the past predictions of ...
- 9,448
2
votes
0
answers
54
views
Question about the definition of projecting concepts in learning
I am self-studying in the area of query learning and having a difficulty in understanding the definition of closed under projection for concept classes discussed in several papers (for example, here (...
- 467
2
votes
1
answer
157
views
Tolerance parameter of statistical query model and adaptivity
It seems that the reasonable assumption for the tolerance parameter of statistical query model is roughly $1/\sqrt{n}$, which is obtained from concentration inequalities (see, e.g., Definition 2.3 of ...
- 852
1
vote
1
answer
183
views
Does MCMC belong to the statistical query model?
It is known that a wide range of algorithms fall into the statistical query (SQ) learning model by Michael Kearns. Examples include k-means, logistic regression, naive Bayes (NB), SVM, ICA, PCA, ...
- 852
4
votes
1
answer
499
views
Does Approx Carathéodory's theorem implies dimensionality reduction
Carathéodory's theorem says that if a point $x$ of $R^d$ lies in the convex hull of a point set $P$, then there is a subset $P′ \subseteq P$ consisting of $d + 1$ or fewer points such that $x$ can be ...
- 639
7
votes
2
answers
907
views
How does the Multiplicative Weights Update method maximize entropy?
"The Multiplicative Weights Update (MWU) method is known to maximize both utility and entropy". This is a comment by C. Papadimitriou on MWU. I understand that MWU maximizes utility as it solves ...
- 93
7
votes
1
answer
323
views
Trying to understand a paper on ksvd algorithm (dictionary learning) by Elad, et al
Trying to understand a paper titled KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation by M.Elad, et al;
my take of section IV.C. detailed description of KSVD, is ...
- 133
2
votes
0
answers
206
views
Convergence of online convex optimization methods
I am new to this subject so this question might seem a bit trivial
Assume that in each round $t\in{{1,...T}}$ we choose $x_t\in K $ where $K$ is a compact and convex set, The common methods for ...
- 21
2
votes
0
answers
1k
views
Is there a closed form equation for the back-propagation equation update in Neural Networks?
I was trying to understand if there was a way to express the back-propagation equations from neural networks in a better way as to understand them better. I believe the equations can be written in a ...
- 262
4
votes
1
answer
91
views
Data Mining of self-replicators
My current (very limited) understanding of the creative process that leads to the design of self-replicators is that any particular self-replicator, like Universal Constructor, Langton's loop or ...
- 185
1
vote
0
answers
42
views
How to find a proper probabilistic formulation given the objective function terms?
I want to pose a problem as maximisation of MAP probability $P(X,Y|Z)$ and I know which terms I want to have in the objective function. However, I am unable to combine these terms to form a joint ...
- 31
2
votes
0
answers
48
views
second order regularisation on a neurofuzzy network with Bernstein basis functions
We're trying to build a neural network that uses a neurofuzzy approach. Our reference is the book Adaptive Modelling, Estimation and Fusion from Data: A Neurofuzzy Approach by Chris Harris, Xia Hong, ...
- 31
-2
votes
2
answers
253
views
Lemma needed for my machine learning research [closed]
Say $\sigma_1, \sigma_2, \dots, \sigma_m$ are i.i.d distributed $\pm1$ variables. How do I show that for any choice of $S_1, S_2, \dots, S_d$ subsets of $\{1, 2, \dots, m\}$, the expectation of the ...
- 97
2
votes
1
answer
102
views
List of papers on Runtime and Statistical Tradeoffs on Machine Learning
I was interested in the connection between (statistical) learning guarantees (or any statistical properties) and their relation to run time. For example, I was wondering, in what cases does having ...
- 262
4
votes
1
answer
277
views
Are there any learning algorithms with any provable guarantees for manifold learning or manifold regularization?
First of all, I want to make clear that my question is about algorithms. I'd like to know if there are any algorithms with provable guarantees in the context of manifold learning (or manifold ...
- 262
5
votes
3
answers
409
views
Dimensionality reduction in machine learning
This is less of a question and more of a "here's my take let me know if you agree" (so I guess it might turn into a big-list?).
Dimensionality reduction refers to a collection of techniques that ...
- 10.5k
2
votes
0
answers
243
views
Dynamical systems analysis of deep learning
I am interested in finding out references that apply dynamical systems analysis to develop the "theory" of deep learning, specifically (say) feedforward deep neural nets. The only paper I seem to have ...
- 21