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
2
votes
0answers
887 views

How is the complexity of PCA $O(\min(p^3,n^3))$?

I've been reading a paper on Sparse PCA, which is: http://stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf And it states that, if you have $n$ data points, each represented with $p$ features, ...
2
votes
0answers
432 views

VC dimension for ellipsoidal classifiers

What is the VC dimension of $g: \mathbb{R}^n \times (\mathbb{R}^{n \times n} \times \mathbb{R}^n \times \mathbb{R}) \rightarrow \{-1,1\}$ defined as $$ g( x, (P_1,p_2,p_3), ) := \text{sgn} \left( x^\...
2
votes
0answers
755 views

Ultimate Jedi Challenge - Multiarmed Bandit / Reinforcment Learning / advanced AI problem

(This is an attempt to reformulate this question more concisely.) Context You are a Jedi master who wants to prepare a training program (online-algorithm) for his apprentice, "Luke". Luke needs to ...
1
vote
1answer
2k views

What is the significance of abstract linear algebra in machine learning/computer vision research?

I am a computer science research student working in application of Machine Learning to solve Computer Vision problems. Since, lot of linear algebra(eigen-values, SVD etc.) comes up when reading ...
1
vote
1answer
144 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, ...
1
vote
2answers
3k views

Derive logitboost using the logistic loss function

An additive model constructed using the exponential loss function $$L(y, f (x)) = \exp(−yf (x))$$ gives Adaboost. How can we derive the corresponding additive model (known as logitboost) using ...
1
vote
1answer
171 views

Reference for Dudley's chaining integral

Dudley's chaining integral is commonly used to bound Rademacher complexities. I recall seeing several papers give this as the reference ...
1
vote
1answer
232 views

What is the VC dimension of Turing machines with specified maximum size?

Note by "maximum size" in the question I'm referring to the size of the Turing machine's state machine. I chose Turing machines in the question to make the question concrete, but I'm also more ...
1
vote
1answer
194 views

$L_\mathcal{D}(A(S)) \le 0.1$ with prob at least $0.9$ implies PAC learnability

Suppose we have a hypothesis class $\mathcal{H}$ that is non-uniform learnable via sample compelxity function $m_{\text{NUL}}:[0,1]^2 \times \mathcal{H} \rightarrow \mathbb{N}$. If we define $\mathcal{...
1
vote
1answer
403 views

direct connection between gradient descent and follow the (perturbed) leader algorithm or weighted majority?

Is there a direct conversion between gradient descent ([1], Alg 1 ) and any of the following algorithms? 1) Weighted Majority: http://onlineprediction.net/?n=Main.WeightedMajorityAlgorithm 2) ...
1
vote
1answer
59 views

How to define the _regret_ in multiagent systems? Any good definition please?

I am reading this book. In chapter 7, section 7.5 page 240 (in the pdf), the authors defined (definition 7.5.1) the regret as being the difference between the average per-period reward the agent ...
1
vote
1answer
817 views

Linear Genetic Programming

I have a few questions about linear genetic programming. I'm struggling to find much information on them, hopefully someone here can help me, it would be much appreciated. 1) Initialisation: When ...
1
vote
1answer
147 views

Reinforcement Learning and Optimistic Decisions

Sutton recommended using an optimistic heuristic on decision making by considering the upper bound of the confidence range of an action-value. From my testing, it seems to work. I find this ...
1
vote
1answer
56 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; ...
1
vote
1answer
70 views

Sample complexity for learning Boltzmann Distribution parameters

I am trying to think through the number of samples that I would need to estimate the parameters of a Boltzmann partition function to a desirable precision. Suppose that there are N possible states ...
1
vote
1answer
86 views

References for the computational complexity of training neural networks

I'm looking for a good review paper or book chapter that offers an accessible introduction to the computational complexity of training neural networks for classification problems. In particular, I'm ...
1
vote
2answers
1k views

Hyperspherical nature of K-means and similar clustering methods

Jain, Murty, and Flynn state in their article Data Clustering: A Review all squared error based clustering methods like K-means tend to generate hyperspherical clusters. However, they do not give a ...
1
vote
1answer
299 views

Theoretical proof of convergence of sequential weight update procedure (Neural Networks and Machine Learning)

My question is at the bottom. (Most of the descriptive words come from Chris. Bishop's Neural Networks for Pattern Recognition) let $w$ be the weight vector of the neural network and $E$ the error ...
1
vote
1answer
417 views

Clustering of letters - what approach would give the best results?

I am working on letter recognition program. I have a text and divide it into letters, every single letter is written to separate file. Now I want to apply a clustering algorithm to these images to ...
1
vote
0answers
41 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 ...
1
vote
0answers
47 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 ...
1
vote
0answers
53 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
68 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
129 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 ...
1
vote
0answers
78 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 ...
1
vote
0answers
90 views

Complexity of low-rank matrix factorizations with rows in a simplex and outliers

Our goal is to obtain a matrix factorization in form of $M = U V'$, where $U\in\mathbb{R}^{d\times r}, V \in\mathbb{R}^{N\times r}$ and each row of $V$ satisfies $$ \sum_{j}(V)_{ij}=1, (V)_{ij}\ge 0 $$...
1
vote
0answers
59 views

Back-propagation for computing derivative of certain line integral

Consider a function F (think of neural networks) with two sets of parameters: (1) model parameters $\mathbf{w}$, and (2) input data ${\bf x} \in {\mathbb R}^d$. Fix $i \in [d]$, consider the following ...
1
vote
0answers
80 views

Average margin bounds for separable SVM

Suppose we're training a linear separator in the realizable PAC setting. Given $m$ labeled examples $(x_i,y_i)$ in $\mathbb R^d\times\{-1,1\}$, a (consistent) linear separator is a vector $w\in\mathbb ...
1
vote
0answers
55 views

Is there a theoretical guarantee that an autoencoder $g$ has $I(x;g(x)) \approx H(x)$?

I know that in general, a function $g$ can be a good auto-encoder (i.e., $g(x) \approx x$ for $x \sim D$) and on the same time $I(g(x);x)$ is small. This is the case when $g$ forms a good correlation ...
1
vote
0answers
48 views

Variability of gradient estimates and convergence rate in stochastic gradient descent/ascent

I am aware that convergence in stochastic gradient problems is very sensitive to the variance of your gradient estimator. One issue I'm running into is that the gradient is a random vector and so ...
1
vote
0answers
50 views

Ranking problem (single instance before others)

Suppose I am trying to learn function $f$ for a ranking-like objective: The mapping: ranking one element at the top and the rest at the bottom. More formally, suppose each input instance $I_i$ ...
1
vote
0answers
61 views

Learnability of under some characteristics of the distribution

TLDR; is there any results showing that more concentrated (or easier) distributions are easier to learn? In PAC-learning, the guarantee is given for any underlying distributions. But in reality, we ...
1
vote
0answers
66 views

To what extent supervised learning ERM learn first-order knowledge

Suppose I have a collection of (hidden) first-order rules: $$ \mathcal{R}: \{ Q_i(x) => P_i(x) \}_{i=1}^{k} $$ all defined over $x \in \mathcal{X}$. I can use these rules and (automatically) ...
1
vote
0answers
204 views

Convergence of Q-learning with non-linear function approximation

Q-learning is a well-known algorithm in Reinforcement learning which enjoys great empirical success but with insufficient theoretical understanding. In the tabular setting, it is known that if each ...
1
vote
0answers
141 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
vote
0answers
116 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 ...
1
vote
0answers
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-...
1
vote
0answers
63 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 ...
1
vote
0answers
36 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 ...
1
vote
0answers
23 views

Identifying ambiguities in inductively learned concepts

I'm looking at ways in which "ambiguities" can be identified in labeled training data by a system undergoing some sort of inductive learning process. Do you know if there is any literature on this ...
1
vote
0answers
150 views

How to define deep learning? [closed]

Ive read some articles about deep learning but I found its hard to provide a clear definition of deep learning. For me its like an intelligent feature selection method. But it seems that its not ...
1
vote
0answers
279 views

What's the meaning of the class indicator matrix when transforming the class label matrix into it in canonical correlation analysis?

When using canonical correlation analysis (CCA), we can integrate the dataset and label information via transforming the class label matrix Y into the class indicator matrix T. Such as: $T = (YY^T)^½Y$...
1
vote
0answers
239 views

Generalization Issues with Practical Suggestions from Universal Approximation Theorem with Neural Networks

After having read matus's beautiful answer in this thread explaining (among other things) Cybenko's proof of the Universal Approximation Theorem for Neural Networks, I wonder: if we use a piecewise ...
1
vote
0answers
120 views

How to find the shattering set size without visualising the target function behaviour?

My aim is to prove a vc-dimension $d$ for different problems. All the problems I have do not have visualised target function (or concept) . I know this is unnecessarily. But this unlike most of the ...
1
vote
0answers
110 views

Techniques to get nodes in the best Markov Cluster?

I was using Markov Clustering to cluster nodes in my bidirectional graph, and overall the results were great. However, there were a couple instances where a weakly connected node would attract a node ...
1
vote
0answers
93 views

Belief Propagation on MRF with complex cliques

Is there a belief propagation algorithm for exact inference on a MRF with complex clique structures (i.e. ones involving more than 2 neighbours)? For MRF's with cliques that only involve pairwise ...
1
vote
0answers
120 views

Derivation of Expected-Maximization training equations for a noisy-OR Bayesian network

How do I derive the EM training equations for a noisy-OR Bayesian network? I am familiar with one solution to these equations. If I remember correctly, the result is: Given a model with link ...
1
vote
0answers
282 views

Using Graphs/Graph Similarity as Features for a Learner

I'm working to construct a learner than can recognize whether two vertices in a property graph (digraph, vertices and edges can have arbitrary keys/values) modelling a social network in fact represent ...
0
votes
1answer
3k views

off-policy and offline policy reinforcement learning

What's the difference between off-policy reinforcement learning algorithms and offline policy reinforcement learning algorithms ? Or do they mean the same thing ? thanks
0
votes
1answer
192 views

Estimating graphs using random cuts

How easy is it to estimate a graph by observing only a few random cuts? Is there prior work related to this? I did google but could not find anything concrete. Any help would be appreciated. Thanks.

1
3 4
5
6 7