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 [algorithms]

An unambiguous list of computational steps involved in finding a solution to a class of problems.

54
votes
3answers
4k views

Who created the first standard normal table?

I'm about to introduce the standard normal table in my introductory statistics class, and that got me wondering: who created the first standard normal table? How did they do it before computers came ...
52
votes
7answers
25k views

Best PCA algorithm for huge number of features (>10K)?

I previously asked this on StackOverflow, but it seems like it might be more appropriate here, given that it didn't get any answers on SO. It's kind of at the intersection between statistics and ...
51
votes
9answers
13k views

Measuring entropy/ information/ patterns of a 2d binary matrix

I want to measure the entropy/ information density/ pattern-likeness of a two-dimensional binary matrix. Let me show some pictures for clarification: This display should have a rather high entropy: ...
50
votes
7answers
25k views

Period detection of a generic time series

This post is the continuation of another post related to a generic method for outlier detection in time series. Basically, at this point I'm interested in a robust way to discover the periodicity/...
47
votes
6answers
12k views

Efficient online linear regression

I'm analysing some data where I would like to perform ordinary linear regression, however this is not possible as I am dealing with an on-line setting with a continuous stream of input data (which ...
45
votes
10answers
21k views

What is a good algorithm for estimating the median of a huge read-once data set?

I'm looking for a good algorithm (meaning minimal computation, minimal storage requirements) to estimate the median of a data set that is too large to store, such that each value can only be read once ...
43
votes
5answers
17k views

Optimized implementations of the Random Forest algorithm

I have noticed that there are a few implementations of random forest such as ALGLIB, Waffles and some R packages like randomForest. Can anybody tell me whether ...
42
votes
6answers
25k views

What algorithm is used in linear regression?

I usually hear about "ordinary least squares". Is that the most widely used algorithm used for linear regression? Are there reasons to use a different one?
37
votes
3answers
31k views

What are the differences between hidden Markov models and neural networks?

I'm just getting my feet wet in statistics so I'm sorry if this question does not make sense. I have used Markov models to predict hidden states (unfair casinos, dice rolls, etc.) and neural networks ...
35
votes
5answers
34k views

What is the difference between the forward-backward and Viterbi algorithms?

I want to know what the differences between the forward-backward algorithm and the Viterbi algorithm for inference in hidden Markov models (HMM) are.
34
votes
6answers
7k views

Approximate $e$ using Monte Carlo Simulation

I've been looking at Monte Carlo simulation recently, and have been using it to approximate constants such as $\pi$ (circle inside a rectangle, proportionate area). However, I'm unable to think of a ...
33
votes
6answers
4k views

Data mining: How should I go about finding the functional form?

I'm curious about repeatable procedures that can be used to discover the functional form of the function y = f(A, B, C) + error_term where my only input is a set of ...
25
votes
3answers
6k views

Best bandit algorithm?

The most well-known bandit algorithm is upper confidence bound (UCB) which popularized this class of algorithms. Since then I presume there are now better algorithms. What is the current best ...
25
votes
1answer
17k views

Difference between standard and spherical k-means algorithms

I would like to understand, what is the major implementation difference between standard and spherical k-means clustering algorithms. In each step, k-means computes distances between element vectors ...
24
votes
7answers
5k views

Algorithm to dynamically monitor quantiles

I want to estimate the quantile of some data. The data are so huge that they can not be accommodated in the memory. And data are not static, new data keep coming. Does anyone know any algorithm to ...
22
votes
4answers
2k views

Textbook on the *theory* of neural nets/ML algorithms?

Every textbook I've seen so far describes ML algorithms and how to implement them. Is there also a textbook that builds theorems and proofs for the behaviour of those algorithms? e.g. stating that ...
22
votes
1answer
21k views

How to define the termination condition for gradient descent?

Actually, I wanted to ask you how can I define the terminating condition for gradient descent. Can I stop it based upon the number of iterations, i.e. considering parameter values for, say, 100 ...
21
votes
2answers
6k views

Is it possible to accumulate a set of statistics that describes a large number of samples such that I can then produce a boxplot?

I must clarify immediately that I am a practicing software developer, not a statistician, and that my college stats class was a very long time ago… That said, I would like to know if there is a ...
21
votes
2answers
14k views

Why PCA of data by means of SVD of the data?

This question is about an efficient way to compute principal components. Many texts on linear PCA advocate using singular-value decomposition of the casewise data. That is, if we have data $\bf X$ ...
21
votes
6answers
10k views

Examples of hidden Markov models problems?

I read quite a bit of hidden Markov models and was able to code a pretty basic version of it myself. But there are two main ways I seem to learn. One is to read and implement it into code (which is ...
20
votes
2answers
4k views

How does random forest generate the random forest

I am not an expert of random forest but I clearly understand that the key issue with random forest is the (random) tree generation. Can you explain me how the trees are generated? (i.e. What is the ...
20
votes
2answers
9k views

Compute approximate quantiles for a stream of integers using moments?

migrated from math.stackexchange. I'm processing a long stream of integers and am considering tracking a few moments in order to be able to approximately compute various percentiles for the stream ...
19
votes
2answers
1k views

Simulating time-series given power and cross spectral densities

I am having trouble generating a set of stationary colored time-series, given their covariance matrix (their power spectral densities (PSDs) and cross-power spectral densities (CSDs)). I know that, ...
18
votes
9answers
8k views

Pairwise Mahalanobis distances

I need to calculate the sample Mahalanobis distance in R between every pair of observations in a $n \times p$ matrix of covariates. I need a solution that is efficient, i.e. only $n(n-1)/2$ distances ...
18
votes
8answers
14k views

Algorithms to compute the running median?

On smaller window sizes, n log n sorting might work. Are there any better algorithms to achieve this?
17
votes
1answer
6k views

Updating SVD decomposition after adding one new row to the matrix

Suppose that I have a dense matrix $ \textbf{A}$ of $m \times n$ size, with SVD decomposition $$\mathbf{A}=\mathbf{USV}^\top.$$ In R I can calculate the SVD as ...
17
votes
2answers
1k views

Speed, computational expenses of PCA, LASSO, elastic net

I am trying to compare computational complexity / estimation speed of three groups of methods for linear regression as distinguished in Hastie et al. "Elements of Statistical Learning" (2nd ed.), ...
16
votes
2answers
6k views

Which optimization algorithm is used in glm function in R?

One can perform a logit regression in R using such code: ...
16
votes
5answers
3k views

Online algorithm for mean absolute deviation and large data set

I have a little problem that is making me freaking out. I have to write procedure for an online acquisition process of a multivariate time series. At every time interval (for example 1 second), I get ...
16
votes
1answer
5k views

What are efficient algorithms to compute singular value decomposition (SVD)?

The Wikipedia article on principal component analysis states that Efficient algorithms exist to calculate the SVD of $X$ without having to form the matrix $X^TX$, so computing the SVD is now the ...
15
votes
4answers
1k views

In what kind of real-life situations can we use a multi-arm bandit algorithm?

Multi-arm bandits work well in situation where you have choices and you are not sure which one will maximize your well being. You can use the algorithm for some real life situations. As an example, ...
15
votes
1answer
5k views

How does extreme random forest differ from random forest?

Is ER more efficient implementation (somelike Extreme Gradient Boosting is to gradient boosting)-- is the difference important from practical point of view ? There ...
15
votes
1answer
2k views

What are the pros and cons of learning about a distribution algorithmically (simulations) versus mathematically?

What are the pros and cons of learning about a distribution's properties algorithmically (via computer simulations) versus mathematically? It seems like computer simulations can be an alternative ...
15
votes
1answer
14k views

How should decision tree splits be implemented when predicting continuous variables?

I'm actually writing an implementation of Random Forests but I believe the question is specific to decision trees (independent of RFs). So the context is that I'm creating a node in a decision tree ...
14
votes
2answers
1k views

What are some important uses of random number generation in computational statistics?

How and why are random number generators (RNGs) important in computational statistics? I understand that randomness is important when choosing samples for many statistical tests to avoid bias towards ...
14
votes
2answers
1k views

What is a 'message passing method'?

I have a vague sense of what a message passing method is: an algorithm that builds an approximation to a distribution by iteratively building approximations of each of the factors of the distribution ...
13
votes
8answers
2k views

Testing random variate generation algorithms

Which methods are used for testing random variate generation algorithms?
13
votes
2answers
9k views

Algebra of LDA. Fisher discrimination power of a variable and Linear Discriminant Analysis

Apparently, the Fisher analysis aims at simultaneously maximising the between-class separation, while minimising the within-class dispersion. A useful measure of the discrimination power of a ...
13
votes
3answers
30k views

Why do we use k-means instead of other algorithms?

I researched about k-means and these are what I got: k-means is one of the simplest algorithm which uses unsupervised learning method to solve known clustering issues. It works really well with large ...
13
votes
1answer
17k views

Generating values from a multivariate Gaussian distribution

I am currently trying to simulate values of a $N$-dimensional random variable $X$ that has a multivariate normal distribution with mean vector $\mu = (\mu_1,...,\mu_N)^T$ and covariance matrix $S$. I ...
13
votes
1answer
9k views

Machine learning classifiers big-O or complexity

To evaluate the performance a new classifier algorithm, I'm trying to compare the accuracy and the complexity (big-O in training and classifying). From Machine Learning: a review I get a complete ...
13
votes
1answer
10k views

What's the forward stagewise regression algorithm?

Maybe it's just that I'm tired, but I'm having trouble trying to understand the Forward Stagewise Regression algorithm. From "Elements of Statistical Learning" page 60: Forward-stagewise ...
12
votes
3answers
3k views

Can someone please explain the back-propagation algorithm?

What is the back-propagation algorithm and how does it work?
12
votes
1answer
15k views

Steps done in factor analysis compared to steps done in PCA

I know how to perform PCA (principal component analysis), but I would like to know steps that should be used for factor analysis. To perform PCA, let us consider some matrix $A$, for instance: ...
12
votes
4answers
5k views

How to apply LASSO to IRLS (logistic regression)?

I have programmed a logistic regression using the IRLS algorithm. I would like to apply a LASSO penalization in order to automatically select the right features. At each iteration, the following is ...
12
votes
5answers
3k views

Is automated machine learning a dream?

As I discover machine learning I see different interesting techniques such as: automatically tune algorithms with techniques such as grid search, get more ...
12
votes
2answers
2k views

Run-time analysis of common machine learning algorithms

Does anyone have reference to a summary of run-time analyses for common machine learning algorithms (different flavors of NN, SVMs, etc)?
12
votes
3answers
444 views

Mathematics base for data mining and artificial intelligence algorithms

Could you give me some clarification about data mining and artificial intelligence algorithms? What mathematics base they used for? Could you give me starting point, in mathematics, to understand ...
11
votes
2answers
8k views

Why doesn't runif generate the same result every time?

Why is it that random number generators like runif() in R don't generate the same result every time? For example: ...
11
votes
4answers
6k views

How can I (numerically) approximate values for a beta distribution with large alpha & beta

Is there a numerically stable way to calculate values of a beta distribution for large integer alpha, beta (e.g. alpha,beta > 1000000)? Actually, I only need a 99% confidence interval around the mode,...