Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [machine-learning]

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

294 questions
Filter by
Sorted by
Tagged with
207 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 ...
221 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 ...
417 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 ...
789 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 ...
114 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 ...
13k 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 ...
274 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 ...
481 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 ...
534 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 ...
338 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 ...
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 ...
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. ...
49k 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 ...
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 ...
1k 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 ...
246 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 ...
457 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 ...
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 ...
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 ...
109 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 ...
182 views

148 views

### Separation result for proper learning under the uniform vs. adversarial distributions?

Does anyone know of a concept class known to be (1) efficiently learnable under the uniform distribution but (1) NP-hard to learn under arbitrary [adversarial] distributions? I mean "learning" in the ...
3k views

### machine learning for code and compiler optimization?

I am looking into ML for generating more efficient code (i.e. compile time and run time heuristics). I have a phd (compilers, hpc), but very little ML experience. I would appreciate any references ...
6k views

### Is there any gradient descent based technique for searching absolute minimum (maximum) of a function in multidimensional space?

I'm familiar with gradient descent algorithm which can find local minimum (maximum) of a given function. Is there any modification of gradient descent which allows to find absolute minimum (maximum),...
1k views

### What is the significance of abstract linear algebra in machine learning/computer vision research?

I am a computer science research student working in application of Machine Learning to solve Computer Vision problems. Since, lot of linear algebra(eigen-values, SVD etc.) comes up when reading ...
994 views

### Stochastic Gradient Descent with integer arithmetics

Most implementations of stochastic gradient descent (SGD) rely on floating points. Is there implementations using infinite or finite precision integer arithmetics ?
134 views

### Semi-supervised learning on graphs

What is semi-supervised learning on graphs? We have been told that if we just have a function which has an input graph, or a given graph with labeled nodes, we should be able to predict labels on ...
388 views

### What kind of machine learning is this?

The objective is to build a classifier that produces M correct outputs when given N inputs. Let a "sample" be M outputs and N inputs. Each output is some function some of the N inputs but the ...
120 views

### Derivation of Expected-Maximization training equations for a noisy-OR Bayesian network

How do I derive the EM training equations for a noisy-OR Bayesian network? I am familiar with one solution to these equations. If I remember correctly, the result is: Given a model with link ...