Stack Exchange Network

Stack Exchange network consists of 175 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

6
votes
0answers
114 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
66 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
735 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
176 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
123 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
352 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
492 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
310 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
541 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
549 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
277 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
524 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
175 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
985 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 ...
4
votes
1answer
771 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
345 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
462 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
592 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
569 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
209 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
404 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
735 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 ...
1
vote
1answer
355 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
512 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
329 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
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 ...
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
46k 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
952 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
224 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)...