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

learn more… | top users | synonyms

-5
votes
0answers
31 views

I need a textbook for machine learning with programming approach [on hold]

I'm taking an online course of machine learning, and I need a good textbook in machine learning better to be with MATLAB applications.
-4
votes
0answers
32 views

Original topic for a computer science bachelor thesis? [on hold]

Im looking specifically for some topics that nobody pay attention on machine learning/KDD/data mining in order to reaserch and make my thesis on some of these... Could anybody provide me some of this ...
5
votes
2answers
104 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 ...
-4
votes
0answers
31 views

What is known about the following problem? [closed]

Consider the class of hypotheses of the form [a , ∞) where a is a real number. What is the VC dimension for this class? thank you
-2
votes
0answers
28 views

Method to recognize abstract objects such as hand-drawn objects? [migrated]

My research is in the area of Document Image Analysis. To be specific, the topic of my thesis is to automatically recognize and index characters in a set of hand-drawn objects, e.g. given a volume of ...
0
votes
0answers
41 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 ...
-1
votes
0answers
15 views

How to calculate precision and recall in a 3 x 3 confusion matrix [migrated]

Predicted class Cat Dog Rabbit Actual class Cat 5 3 0 Dog 2 3 1 Rabbit 0 2 11 How can I ...
8
votes
2answers
611 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
0answers
76 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
90 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
90 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
143 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
156 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
85 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
57 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
42 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 ...
3
votes
0answers
123 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
141 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
68 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
78 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
44 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 ...
0
votes
0answers
47 views

Expected number of Support Vector's in Vapnik's book

I would like to ask this community the question in http://mathoverflow.net/questions/150747/expected-number-of-support-vectors-in-vapniks-book: In Vapnik's book "Statistical Learning Theory", ...
2
votes
0answers
86 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, ...
0
votes
0answers
58 views

grammar compression/induction in proofs

are there (interesting/notable) cases of grammar compression and/or grammar induction used in TCS proofs or analysis? this question is somewhat related to [1]. [1] techniques or examples of ...
4
votes
2answers
149 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
58 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
72 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
187 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
39 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
214 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
100 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
59 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 ...
-3
votes
2answers
267 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
72 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
80 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
194 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
110 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
367 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 ...
5
votes
0answers
249 views

What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$ under the Kullback-Leibler divergence?

If $D_{KL}$ is the Kullback-Leibler divergence, minimizing $D_{KL}(P_{data}||P_{parameters})$ performs maximum likelihood estimation of the parameters. What happens if you minimize ...
6
votes
0answers
79 views

Occam razor for exact learning with membership/equivalence queries

In PAC learning, there is the "Occam razor" principle, which says that learning is qualitatively equivalent finding a succinct hypothesis that is consistent with the training samples. My question is ...
1
vote
2answers
189 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 ...
2
votes
0answers
184 views

VC dimension of intersection of half-spaces

Define $$l_i(x) := \text{sgn} \left( w_i^\top x - b_i \right)$$ for $i=1,...,n$, where $x \in \mathbb{R}^d$. Then define the classifier $$ g(x) := \max \{ l_1(x),..., l_n(x) \}$$ which represents ...
-1
votes
1answer
241 views

canopy clustering: what should we do with samples in overlapping canopies?

In canopy clustering http://www.kamalnigam.com/papers/canopy-kdd00.pdf, if a sample falls in an overlap of 2 canopies, how do we choose its cluster?
2
votes
0answers
165 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( ...
3
votes
0answers
224 views

PAC learning and computation over real numbers

I became familiar with the BSS model of computation recently. I find it to be a better model of computation to study complexity of numerical analysis methods (cf. Complexity and Real Computation; ...
4
votes
1answer
101 views

Are there perceptrons that maximize the average margin, rather than the minimum?

A perceptron is a linear classifier. The standard method for training a perceptron involves maximizing the minimum margin. That is, we are trying to find: $x^* = \text{argmax}_{x\in \text{unit ...
2
votes
1answer
149 views

Clustering massive data sets in practice

If you have a very large data set of $n$ vectors and you want to cluster them according to some metric measure, what is the current state of the art when you can not afford to do more than $\Theta(n)$ ...
2
votes
2answers
190 views

Size of decision tree for f is polynomial in the DNF size of f and CNF size of f

I've been having hard time with proving the following claim: Let $f:\{T,F\}^n\rightarrow \{T,F\}$ be a boolean function. Let $size_{DT}(f)$ denote the number of leaves in the smallest (w.r.t the ...
7
votes
1answer
260 views

How do database aggregations form a monoid?

On cs.stackexchange I asked about the algebird scala library on github, speculating on why they might need an abstract algebra package. The github page has some clues: Implementations of Monoids ...
3
votes
1answer
179 views

Applying Expectation Propagation to Factor Graph

Expectation Propagation(EP) is now quite a standard technique to approximate marginal in graphical model. Moreover, EP can replace sum-product algorithm in factor graph. For this reason, I try to ...