Questions tagged [machine-learning]

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

Filter by
Sorted by
Tagged with
5
votes
2answers
2k views

Why is Bayesian filtering better than Neural Networks when classifying spam?

According to several people on StackOverflow Bayesian filtering is better than Neural Networks for detecting spam. According to the literature I've read that shouldn't be the case. Please explain!
1
vote
1answer
801 views

Linear Genetic Programming

I have a few questions about linear genetic programming. I'm struggling to find much information on them, hopefully someone here can help me, it would be much appreciated. 1) Initialisation: When ...
0
votes
0answers
277 views

Fuzzy K-modes clustering how to find the cluster centers

I'm trying to understand [fuzzy k-modes][1] algorithm (look mainly at page 3) in order to implement it. I'm stuck at the calculation of cluster centers they said as shown in the link https://...
0
votes
0answers
94 views

Designing an appropriate training set for CART classification using imbalanced data

I'm experimenting with using CART (or maybe Random Forest) to classify genomic data. There are essentially two classes, whereof one is the 'normal' state and the other is the 'exceptional' state. Now,...
0
votes
1answer
176 views

what is the equivalence class of a given polytree representing a directed graphical model?

Let $T$ be a binary tree, where the internal nodes are $Y_1,...,Y_n$ and the leafs are $X_1,...,X_m$. (The $Y$s and the $X$s will eventuall represent a random variable in a Bayesian network.) We can ...
0
votes
1answer
209 views

K-means with centres outside the data?

Say we want to split a cube in $\mathbb{R}^{64}$ into 10 pieces. NN, nearest-neighbor or Voronoi splits, take 10 cluster centres $c_0, \ldots, c_9$ in the cube, e.g. from K-means, then classify a new ...
4
votes
1answer
194 views

Active learning for inferring a convex optimization formulation

I was wondering if anybody knows of any relevant references on the general topic of active learning for gradually inferring/updating a convex opt. formulation. As a specific example, I am thinking ...
15
votes
1answer
4k views

Universal Function approximation

It is known via the universal approximation theorem that a neural network with even a single hidden layer and an arbitrary activation function can approximate any continuous function. What other ...
1
vote
1answer
146 views

Reinforcement Learning and Optimistic Decisions

Sutton recommended using an optimistic heuristic on decision making by considering the upper bound of the confidence range of an action-value. From my testing, it seems to work. I find this ...
4
votes
1answer
254 views

Higher-order and black-box clustering

As far as I understand a large number of clustering problems can be formulated as: $\underset{\textbf{P}}{ \text{argmin}} \; \sum_{i,j} f \left(x_i, x_j\right)$ where $\textbf{P}$ is a partitioning ...
5
votes
4answers
1k views

Genetic Algorithm to Draw a Graph? Position assignment problem

I have an assignment problem at hand and am wondering how suitable it would be to apply local search techniques to reach a desirable solution (the search space is quite large). I have a directed ...
4
votes
2answers
378 views

Can you make a different learner?

My questions are: [Solved by Dave] Given a learner N, can you design a learner M that behaves differently from N? No. and [Solved by Dave] Given a learner N, can you design a learner M that is ...
2
votes
1answer
174 views

Does a multilayer perceptron taught by simple backprop learn the shape of a character or the exact image of a character?

(Feel free to suggest a better title) (same with tags, none of relevant tags exist yet, and I only have 101) Let's say I have a perceptron with an optimal number of layers and optimal number of ...
10
votes
1answer
396 views

Agnostic PAC sampling lower bound

It is well-known that for classical PAC learning, $\Omega(d/\varepsilon)$ examples are necessary in order to acheive an error bound of $\varepsilon$ w.h.p., where $d$ is the VC-dimension of the ...
15
votes
2answers
610 views

Quantum PAC learning

Background Functions in $AC^0$ are PAC learnable in quasipolynomial time with a classical algorithm that requires $O(2^{log(n)^{O(d)}})$ randomly chosen queries to learn a circuit of depth d [1]. If ...
7
votes
1answer
143 views

Optimal payoff from sampling from a collection of Bernoulli random variables?

Suppose I have several Bernoulli random variables, $\{X_1, \ldots, X_k\}$, each of which has a fixed probability $p_i$ of equaling 1 for each sample. Further suppose each $p_i$ is randomly distributed ...
4
votes
2answers
422 views

Support Vector Machines and privacy-preservation

suppose we have data matrix A m-by-n (m observations and n features) which I want to Apply SVM on it achieving privacy (Privacy-Preserving SVM) the questions are:- 1 - Is applying kernel trick ...
1
vote
0answers
281 views

Using Graphs/Graph Similarity as Features for a Learner

I'm working to construct a learner than can recognize whether two vertices in a property graph (digraph, vertices and edges can have arbitrary keys/values) modelling a social network in fact represent ...
1
vote
1answer
359 views

Clustering of letters - what approach would give the best results?

I am working on letter recognition program. I have a text and divide it into letters, every single letter is written to separate file. Now I want to apply a clustering algorithm to these images to ...
13
votes
1answer
2k views

What is the tradeoff between population size and the number of generations in genetic algorithms

Genetic algorithms evolve in fewer generations with a larger population, but also take longer to compute a generation. Are there some guide lines for balancing those two factors, in order to arrive at ...
6
votes
1answer
412 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
207 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
317 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
360 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 ...
-1
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
30
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
347 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
320 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
4k views

How does one augment AdaBoost with cross-validation?

How does one augment AdaBoost with cross-validation?
19
votes
1answer
806 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
527 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
522 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
382 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
388 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
601 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
344 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
5k 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
324 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 ...