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
1answer
398 views

Results on universal approximation for learners other than ANNs

I have an applied machine-learning and statistics background, and when I read the Universal approximation theorem, which (in the context of the learning theory of ANNs - Artificial Neural Networks) ...
7
votes
2answers
206 views

A PAC-like analogue for 1-class classification?

This is more of a philosophical question -- I am looking for a reasonable mathematical formulation of 1-class learning. In the PAC model, it's very natural to formulate our demand on the learner: ...
10
votes
1answer
314 views

What machine learning classifiers are the most parallelizeable?

What machine learning classifiers are the most parallelizeable? If you had a difficult classification problem, limited time, but a decent LAN of computers to work with, what classifiers would you try? ...
6
votes
1answer
9k views

Computational complexity of learning (classification) algorithms - fitting the parameters

My wish is to describe the time complexity of several classification approaches. For example, suppose we have $n$ data points in $m$ dimensional space and a binary class variable. We do not assume ...
-4
votes
1answer
2k views

Find sentences with similar relative meaning from a list of sentences against an example one

I want to be able to find sentences with the same meaning. I have a query sentence, and a long list of millions of other sentences. Sentences are words, or a special type of word called a symbol which ...
2
votes
1answer
353 views

K-NN or matrix factorization for discovering correlated features?

I am looking to cluster users together in a database, with each user represented by a number of features that are both discrete and continuous in nature. "Similar" users should be clustered together ...
-2
votes
1answer
2k views

off-policy and offline policy reinforcement learning

What's the difference between off-policy reinforcement learning algorithms and offline policy reinforcement learning algorithms ? Or do they mean the same thing ? thanks
27
votes
10answers
2k views

Great algorithms, machine learning and no linear algebra

I teach an advanced algorithms course and would like to include some topics related to machine learning which will be of interest to my students. As a result, I would like to hear people's opinions of ...
13
votes
3answers
2k views

Statistical query model algorithms?

I asked this question in cross validated Q&A but seems that it is related to CS much more than Statistics. Can you give me examples of machine learning algorithms which learn from the statistical ...
5
votes
1answer
311 views

Solving “all-marginals” problem for independent sets on grid

Suppose I have a distribution over independent sets on an $n\times n$ grid where the probability of independent set occupying nodes $(i_1,j_1),\ldots,(i_k,j_k)$ is proportional to $\lambda_{i_1,j_1}\...
13
votes
1answer
1k views

Computational Power of Neural Networks?

Let's say we have a single-layer feed forward neural network with k inputs and one output. It calculates a function from $\lbrace 0,1\rbrace ^{n}\rightarrow\lbrace 0,1\rbrace $, it's fairly easy to ...
2
votes
2answers
319 views

Generate a sequence of numbers

I want to generate an infinite sequence of numbers between $0$ and $9$ such that the percentage of number $i$ appearing in the sequence is $p_i$. Let $p=\lbrace p_0,...,p_9\rbrace$. Another agent $B$ ...
2
votes
1answer
3k views

How does one augment AdaBoost with cross-validation?

How does one augment AdaBoost with cross-validation?
19
votes
1answer
798 views

The Warren Buffett Problem

Here is an abstraction of an online learning / bandit problem that I've been working on in the summer. I haven't seen a problem like this before, and it looks quite interesting. If you know of any ...
12
votes
5answers
524 views

clustering algorithm for non-dimensional data

i have a dataset of thousands of points and a means of measuring the distance between any two points, but the data points have no dimensionality. i want an algorithm to find cluster centers in this ...
13
votes
1answer
518 views

Reference Request: Submodular Minimization and Monotone Boolean Functions

Background: In machine learning, we often work with graphical models to represent high dimensional probability density functions. If we discard the constraint that a density integrates (sums) to 1, ...
11
votes
1answer
370 views

Agnostic learning over arbitrary distributions

Let $D$ be a distribution over bitstring/label pairs $\{0,1\}^d\times \{0,1\}$ and let $C$ be a collection of boolean valued functions $f:\{0,1\}^d\rightarrow\{0,1\}$. For each function $f \in C$, let:...
9
votes
2answers
371 views

Are there families of formal languages known to be truly PAC learnable?

I specifically mean language families that admit arbitrarily long strings -- not conjunctions over n bits or decision lists or any other "simple" language contained in {0,1}^n. I am asking about "...
7
votes
3answers
600 views

What subjects, topics does a computer science graduate need to learn to apply available machine learning frameworks, esp. SVMs

I want to teach myself enough machine learning so that I can, to begin with, understand enough to put to use available open source ML frameworks that will allow me to do things like: Go through the ...
8
votes
2answers
340 views

complexity of fitting models to data

Suppose $f:\mathbf{R}\times \mathbf{R} \to \mathbf{R}$ is some some continuous function $x_1 \ldots x_n$ is a set of real values, and we'd like to compute $\text{argmin}_a \sum_i f(a,x_i)$ to ...
13
votes
12answers
4k views

What are some real world applications for genetic algorithms?

What are some real world problems that have been solved using a genetic algorithm? What is the problem? What is the fitness test used to solve this problem?
12
votes
2answers
316 views

Computational query complexity of SQ-learning

It is known that for PAC learning, there are natural concept classes (e.g. subsets of decision lists) for which there are polynomial gaps between the sample complexity needed for information theoretic ...
10
votes
5answers
3k views

What are good references on understanding online learning?

Specifically, I'm asking for resources to learn about machine learning systems that can update their respective belief networks (or equivalent) during operation. I've even run across a few, though I ...