Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [machine-learning]

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

0
votes
0answers
343 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 ...
6
votes
1answer
475 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
53 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
306 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
166 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
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
votes
2answers
4k 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
532 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
104 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
547 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 ...
9
votes
1answer
272 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
517 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
1answer
1k 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 $D_{KL}(P_{...
6
votes
0answers
172 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
960 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
705 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
416 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
323 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^\...
3
votes
0answers
258 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
126 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
204 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
461 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 ...
11
votes
1answer
590 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
557 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 ...
0
votes
0answers
206 views

What machine learning algorithm solves this problem?

I want to solve this classification problem. Basically what I have is a sequence of feature vectors $\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N$, and each feature vector is sequential in time. I ...
-1
votes
1answer
205 views

K means feature learning [closed]

Suppose you have a data set composed of n images as training examples. You run clustering on each image ( initializing 3 clusters per image) and learn the centers. Is it ok to then take the cluster ...
3
votes
1answer
396 views

Online to batch sample complexity

It is well known that a mistake bound can be converted to a PAC bound. I know how to prove a sample complexity of $$ O( (1/\epsilon)[M + \log(M/\delta)] ), $$ where $M$ is an upper bound on the number ...
5
votes
1answer
729 views

Computational Complexity of Computer Vision Problems

What is the computational complexity of computer vision problems (reconstruction, detection, etc.)? Are these problems NP-complete? Are they NP-hard? In most cases this will boil down to determining ...
3
votes
1answer
111 views

Is there an algorithm that's “like” cross-validation for approximation algorithms of NP-hard problems?

I normally do machine learning work, and when I'm evaluating an algorithm on a data set, I always use cross-validation to determine how effective the algorithm is. Is there a similar method for ...
11
votes
4answers
12k views

Why can machine learning not recognize prime numbers?

Say we have a vector representation of any integer of magnitude n, V_n This vector is the input to a machine learning algorithm. First question : For what type of representations is it possible to ...
7
votes
2answers
270 views

Learning Mixture of Univariate Gaussians

There are many papers on learning mixtures of multivariate Gaussians, which exploit various separation/projection techniques. What about one-dimensional (univariate) Gaussians -- any formal guarantees ...
0
votes
0answers
328 views

What kind of reinforcement learning is MENACE?

The famous MENACE matchbox computer for playing tic-tac-toe, invented by Donald Mitchie, is an early example of a reinforcement learning algorithm. Here is a description: ...an interesting machine ...
11
votes
1answer
509 views

Noisy Parity (LWE) lower bounds/hardness results

Some background: I'm interested in finding "lesser-known" lower bounds (or hardness results) for the Learning with Errors (LWE) problem, and generalizations thereof like Learning with Errors over ...
15
votes
3answers
325 views

Combinatorial characterization of exact learning with membership queries

Edit: Since I haven't received any responses/comments in a week, I'd like to add that I'm happy to hear anything about the problem. I don't work in the area, so even if it's a simple observation, I ...
1
vote
2answers
2k 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 ...
3
votes
1answer
2k views

Computational complexity of classifying with an already-trained SVM

If I have a support vector machine which has already been trained, what is the computational complexity of classifying a new example using that machine? I care about both time and space complexity. ...
15
votes
5answers
45k views

To what extent is “advanced mathematics” needed/useful in A.I. research?

I am currently studying mathematics. However, I don't think I want to become a professional mathematician in the future. I am thinking of applying my knowledge of mathematics to do research in ...
0
votes
0answers
77 views

Generalizing a set of positive and negative examples through DFAs [duplicate]

Possible Duplicate: Is finding the minimum regular expression an NP-complete problem? Let $\Sigma$ be an alphabet. Let $P$ and $N$ (the set of positive and negative examples) be two disjoint ...
13
votes
1answer
925 views

Is there any work combining machine learning and the more exotic forms of complexity theory?

It seems to me that machine learning/data mining experts are familiar with P and NP, but rarely talk about some of the more subtle complexity classes (e.g. NC, BPP, or IP) and their implications for ...
13
votes
1answer
240 views

Are there distribution properties which are “maximally” hard to test?

A distribution testing algorithm for a distribution property P (which is just some subset of all distributions over [n]) is allowed access to samples according to some distribution D, and is required ...
22
votes
1answer
450 views

Natural, untestable graph properties

In graph property testing, an algorithm queries a target graph for the presence or absence of edges and needs to determine whether the target either has a certain property or is $\epsilon$-far from ...
3
votes
0answers
119 views

Finding most informative feature subsets given dataset, clustering algorithm and gold standard partition

I have an $n \times m$ matrix of data $\mathbf{D}$ as well as a $k$-partition $P$ of $n$ indices each representing a row in a dataset. Assuming an arbitrary clustering algorithm $A$, I would like to ...
-3
votes
1answer
223 views

Which algorithm for a project about online machine learning?

I have a basic understanding of how machine learning works, but my knowledge isn't enough in order to develop a personal project I would like to start. I want to develop a system based on online ...
1
vote
0answers
108 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 ...
7
votes
0answers
178 views

Testing the degree of a vertex

Let's say we have a graph $G$ with $n$ vertices. Given $\epsilon>0$ and a specific vertex $v$, consider the problem of deciding whether $\mathrm{deg}(v) < \frac{\epsilon}{3}n$ or $\mathrm{deg}(v)...
2
votes
0answers
747 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 ...
7
votes
1answer
144 views

Is it possible to create a machine learning classifier to generate Mock interfaces for systems testing?

I'm investigating whether it is feasible to be able to learn a system interface by watching network traffic (assuming the usual problems are solved e.g. encryption etc) I haven't been able to find ...
7
votes
0answers
181 views

Sample complexity of PAC learning all k-DNFs over the uniform distribution

Is sample complexity of PAC learning all $k$-DNFs over the uniform distribution known (that is all DNFs with all terms of size at most $k$ and without restriction on the number of terms)? The only ...
9
votes
1answer
286 views

Learning with (Signed) Errors

$\underline{\bf Background}$ In 2005, Regev [1] introduced the Learning with Errors (LWE) problem, a generalization of the Learning Parity with Error problem. The assumption of this problem's ...
10
votes
2answers
1k views

Introductory resources on Computational Learning Theory

Recently I've been reading a decent number of CoLT papers. Although I don't struggle with the individual papers (at least not more than I usually struggle with other theory papers), I don't feel I ...