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

learn more… | top users | synonyms

1
vote
0answers
10 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
1answer
38 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
46 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
14 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) ...
0
votes
0answers
26 views

Random Forest closed loop [migrated]

I'm using the Random Forest algorithm for classification. I have some variable to use as features in input, but I was wondering if I can use the output of the classification itself as input. Suppose, ...
2
votes
1answer
36 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
21 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
195 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
66 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
24 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
91 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
84 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
71 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
100 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
46 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
29 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
118 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
190 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
386 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
138 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
0answers
68 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
957 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
110 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
116 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
166 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
210 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. ...
2
votes
1answer
146 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
116 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
70 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
143 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
166 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
87 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 ...
5
votes
0answers
80 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
94 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
158 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
63 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
126 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 ...
5
votes
1answer
217 views

What does PAC-learnability say about the learner runtime?

I am new to PAC-learnability. Assume a class $\mathcal{H}$ of hypotheses is PAC-learnable. Then all we know that if we draw polynomial number of examples (in $\delta$ and $\epsilon$), we can return a ...
0
votes
0answers
44 views

Different estimators for uniform convergence of means/averages to expectations

In uniform converge results of means or averages to their expectations (think of the typical results involving VC-dimension, covering numbers, Pseudo-dimension, fat shattering dimension, ...) , the ...
14
votes
2answers
231 views

Theoretical guarantees for running times of belief propagation methods?

Belief propagation has been shown to be a very powerful method through research in probabilistic graphical models. However, I don't know anything about BP that's comparable to MCMC methods where we ...
-1
votes
1answer
126 views

Is a traditional Multi Layer Perceptron Network capable of non-linear regression? Which activation function should be used for that purpose?

I need to use a Multi Layer Perceptron Network in order to perform some non-linear regression. Any ideas if it's possible to perform a task like that and how? Which activation function should be used ...
1
vote
0answers
66 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 ...
-2
votes
2answers
924 views

Compute Time Complexity of Neural network, SVM and other classification algorithms

I would like to know what is the asymptotic time complexity analysis for general models of Back-propagation Neural Network, SVM and Maximum Entropy. Does it just depend on number of features included ...
-3
votes
1answer
128 views

Mapping input and output sequences using neural networks in high dimensional data

I have this huge dimensional data with 31200 features and only 6000 examples. I want to learn a neural network that can find the non linear relation between the input and outputs. However, I have ...
0
votes
1answer
93 views

How to compute K and n? [Item-based Collaborative Filtering]

I'm currently studying this item-based collaborative filtering algorithm on this thesis that I've researched and I've formulated the algorithm below based on it. I have no problem on steps 1 to 3 but ...
0
votes
1answer
238 views

Using Pearson Correlation Coefficient in computing user/item similarity

I'm researching for an algorithm for item-based/user-based collaborative filtering and I've come to this site. It uses Pearson correlation coefficient to compute similarity between users and when I ...
6
votes
0answers
123 views

VC dimension of Voronoi cells in R^d?

Suppose I have $k$ points in $\mathbb{R}^d$. These induce a Voronoi diagram. If I assign to each of the $k$ points a $\pm$ label, these induce a binary function on $\mathbb{R}^d$. Question: what is ...
4
votes
1answer
383 views

Parameters of energy function for TSP

[This question was initially asked here. It went unanswered so I thought I should ask it in a different community.] I am reading this paper by Hopfield et al. On page six, the authors defined the ...