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

learn more… | top users | synonyms

0
votes
0answers
5 views

Known results for active learning algorithms?

A question for people in Active Learning community: What are the best results known (for regression and classification) in terms of number of the queries needed to reach to a given accuracy (for ...
0
votes
1answer
35 views

Bounding Rademacher Averages, with and without chaining

One can bound the Rademacher average $R_n(A)$ of a finite set of vectors $A\subseteq\{0,1\}^n$ using Massart's Finite Lemma: $$ R_n(A)\le \max_{a\in A}\|a\|\frac{\sqrt{2\ln|A|}}{n} $$ where ...
4
votes
1answer
135 views

Sample complexity of distinguishing two Gaussian distributions?

Below is a description of the problem: Suppose I have two $p$-dimensional Gaussian distributions with the same covariance matrix $\Sigma$ and means $\mu_1$, $\mu_0$. And I can get $n$ samples ...
6
votes
0answers
48 views

Learning read-once branching programs with membership queries

Let $B=\{0,1\}$. A read-once branching program of width $n$ and size $w$ is given by a graph with layers $0,\ldots, n$, where the first layer has just the starting node, the last layer has nodes ...
0
votes
0answers
40 views

Implementation of Sparse Johnson Lindenstauss Lemma [on hold]

I am trying to implement the sparse Johnson Lindenstrauss in matlab from the paper: Sparser Johnson-Lindenstrauss Transforms by Daniel M. Kane and Jelani Nelson. Can somebody give pointers on how to ...
2
votes
1answer
52 views

How to exploit knowledge of the sampling distribution for better generalization bounds?

In the PAC learning model, suppose the learner actually knows the sampling distribution $P$. Surely this knowledge can be exploited to yield better generalization bounds -- but how? One idea is using ...
0
votes
1answer
73 views

VC-dimension of triangles in 2D space

I have been reading in multiple places (e.g. [1], section 4) that the VC-dimension of the class of triangles (in 2D space) is 7. The issue is that, for the case when 4 points lying on a straight line ...
0
votes
1answer
44 views

Are single hidden-layered neural networks at least as good as multi hidden-layered neural networks?

If I have a multi hidden-layered neural network that is getting a better approximation for a function than a single one, does that mean that there is something "fishy" about my multi layered one ...
2
votes
1answer
86 views

Characterizing the exponential savings in active learning

Let $H$ be a hypothesis class with VC dimension $d$. In supervised learning, we need almost $O(\frac{d}{\epsilon})$ random labelled examples to return a hypothesis within $\epsilon$ from the target ...
7
votes
1answer
223 views

Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics). I am particularly ...
2
votes
0answers
71 views

What mathematical models can analyze and optimize such message passing system?

I look for a mathematical model that can accommodate, analyze and suggest optimizations for a system that can be humanly described as message passing black box programs to which where optimal message ...
2
votes
1answer
100 views

minimal finite automata given in-words and out-words

this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight. given: two finite sets of words $S_{in}$ and $S_{out}$. ...
1
vote
0answers
21 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 ...
2
votes
1answer
49 views

Are (empirical) Rademacher complexity always positive?

Rademacher complexity and empirical Rademacher complexity are used to provide upper bound on the loss of solving an learning problem. That seems to imply that Rademacher complexity and empirical ...
1
vote
0answers
53 views

Follow the Perturbed Leader for nonlinear cost functions

The famous FTPL algorithm [1] is analyzing linear cost function. Is there any generalized proof for nonlinear functions known? Note that in the last paragraph of [1] it says "It would be great to ...
1
vote
1answer
27 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) ...
2
votes
1answer
44 views

Are there closed-form expressions providing the VC-dimension for the multi-class case for different classifiers?

So far, I've only encountered the VC-dim for binary classifiers. I'm interested to learn how this notion can be extended to the multi-class case. Are there expressions that provide bounds on the ...
2
votes
0answers
39 views

Cellular neural networks

I'm a new at the cellular neural network, which is a special case of the recurrent neural network: my questions are: I understand the implementation of Chua circuit for the CNN, but I still need to ...
9
votes
2answers
216 views

Theoretical results for random forests?

Random forests have a reputation among practitioners of being among the most effective classification techniques. Yet we don't encounter them much in the learning-theoretic literature, from which I ...
2
votes
0answers
70 views

Do Genetic Algorithms Expect a Independent Search Space

Genetic Algorithms seem like multiple simulated annealing instances, augmented with a crossover genetic operator. The crossover operator selects predefined genes from two different parent solutions to ...
0
votes
0answers
28 views

Are there other names for multilayer perceptrons or multidimensional interpolants based on Kolmogorov's approximation work?

Are there other names for multilayer perceptrons that are used outside of the neural net community? At its core, multilayer perceptrons form a multidimensional interpolant of the form $$ ...
1
vote
0answers
97 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 ...
4
votes
0answers
90 views

extracting/ exploiting similarity of SAT instances by solver

suppose that two SAT formulas on different variables $F_1, F_2$ are given on the input that are known to be true and the problem is to build an algorithm that finds a solution to each. the formulas ...
2
votes
0answers
72 views

Fast rates — cleanest proof

Fast rates generally refers to generalization bounds interpolating between the $1/n$ consistent rate and the $1/\sqrt n$ agnostic rate. I am aware of two basic approaches for obtaining these: (1) ...
2
votes
1answer
110 views

Doubt in John Langford's “Tutorial on Practical Prediction Theory for Classification” paper

I am reading John Langford's paper on practical prediction theory (link), and I have the following doubt with definition of Binomial Tail inversion. The paper says that binomial tail inversion is the ...
0
votes
1answer
48 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 ...
0
votes
0answers
42 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 = ...
2
votes
0answers
131 views

How useful is program search in the field of programming-language theory?

I've been thinking: computing systems such as the Lambda Calculus and its variations are usually very simple and can be implemented in as few as ~80 lines of Haskell code. There is a self-interpreter ...
11
votes
1answer
192 views

Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value

Here is a problem with a similar flavor to learning juntas: Input: A function $f: \{0,1\}^n \rightarrow \{-1,1\}$, represented by a membership oracle, i.e. an oracle that given $x$, returns $f(x)$. ...
7
votes
1answer
393 views

Is testing easier/harder than learning?

How is the Property testing is related to PAC model of learning? More precisely, Let we have given a property tester, $\mathcal{A}$, for the (concept) class of function $\mathcal{F_n}$ which ...
5
votes
2answers
161 views

Learnability of constraint satisfaction problems CSPs?

This may sound more like a soft question but I am struggling to find an answer for it. While the learnability of Bayesian Networks and other graphical models are well detailed in the literature of ...
0
votes
1answer
124 views

Representation of procedural knowledge

I know that knowledge about relationships between things can be represented using ontologies and stored in some sort of file or database system. Can a network of procedural knowledge also be created ...
12
votes
3answers
1k views

When to use the Johnson-Lindenstrauss lemma over SVD?

The Johnson-Lindenstrauss lemma allows one to represent points in a high dimensional space into points in lower dimension. When finding lower dimensional spaces of best fit, a standard technique is to ...
2
votes
1answer
118 views

How to deal with concept classes with exponential value of VC dimension

Let $C$ be a concept class with VC dimension $d$ exponential to the input size (i.e number of variables represented in each concept $c\in C$). I am looking for papers/resources/suggestions of how ...
3
votes
1answer
123 views

Is this variant of PAC learning known?

Here is a problem I've never seen, in a model similar to the PAC model. It asks a similar question to PAC learning, but wishes to optimize, rather than learn. I wonder if this problem is known, has ...
3
votes
1answer
188 views

Objective function for stochastic optimization

Stochastic Optimization problems in general deals with random variables in the 'loss function'. Incase of a Deterministic optimization problem with basic objective $\parallel Ax-b \parallel_2^2$, we ...
5
votes
0answers
154 views

Complexity of the Transductive SVM training problem

The Transductive Support Vector Machine training problem is a non-convex mixed integer programming problem: Transductive Support Vector Machine training problem. $$ \begin{align} ...
1
vote
3answers
226 views

Which algorithms have been proposed to learn the architecture of a deep neural network?

Yoshua Benhgio's Learning Deep Architectures for AI book mentions that we should [...] strive to develop learning algorithms that use the data to determine the depth of the final architecture. ...
3
votes
1answer
171 views

Using Indicator Functions as Transfer Functions for Neural Networks

Does there exist any theory (other than Cybenko's proof of the Universal Approximation Theorem with sigmoids) advocating the use of indicator functions as transfer functions for machine learning with ...
3
votes
0answers
148 views

Practical Implications of Kolmogorov's Result on the Universal Approximation Theorem with Neural Networks

After having read matus's beautiful answer in this thread explaining (among other things) Kolmogorov's result regarding the Universal Approximation Theorem with Neural Networks, I wonder: if just ...
1
vote
0answers
78 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 ...
2
votes
0answers
149 views

Expected probability of error in Vapnik's book

In Vapnik's book "Statistical Learning Theory", Theorem 10.5 states that - for a Support Vector Machine - the expected probability of error (of the optimal hyperplane) is upper bounded by $1/(l+1)$ ...
5
votes
1answer
172 views

Statistical query model with Gaussian noise?

Kearns' statistical query model is a well-known learning model with noise tolerance. The statistical query oracle takes as input a statistical query of the form $\{\chi, \tau\}$. Here $\chi$ is any ...
1
vote
1answer
92 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 ...
6
votes
0answers
106 views

Branching Boosting Algorithms

Long/Servedio showed AdaBoost/etc doesn't perform well under noisy environments, but that branching forms of boosting do. Can any point me to a list of branching boosting algorithms, or a reference ...
3
votes
0answers
49 views

Lower Bound on Zero-order Regret

Here is a brief summary of the experts framework: Given $n$ experts who either give correct or wrong advice for each round $t\in [T]$, an algorithm is required to give a best prediction for each round ...
2
votes
0answers
97 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, ...
4
votes
2answers
161 views

How to compute the disagreement between hypotheses

Given a class of hypothesis $\mathcal{H}$ representing the set of all consistent hypotheses with the examples seen so far, how to compute the region of uncertainty? The region of uncertainty is ...
0
votes
1answer
67 views

Mutual information and entropy to prove minimal Relevance Maximum Dependency

I'm reading through a paper on feature selection: Feature Selection Based on Mutual Information: Criteria of Max-Dependency, Max-Relevance,and in-Redundancy but I'm unable to understand parts of the ...
0
votes
0answers
140 views

Making feature vector from Gabor filters for classification using Neural Networks

My aim is to classify types of cars (Sedans,SUV,Hatchbacks) and earlier I was using corner features for classification but it didn't work out very well so now I am trying Gabor features. code from ...