# Questions tagged [algorithms]

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

737 questions
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 ...
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 ...
14k 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: ...
26k 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/...
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 ...
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 ...
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 ...
26k 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?
36k 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.
32k 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 ...
8k 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 ...
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 ...
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 ...
7k 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 ...
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 ...
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 ...
23k 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 ...
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 ...
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$ ...
11k 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 ...
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 ...
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 ...
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, ...
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 ...
15k 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?
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.), ...
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 ...
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 ...
7k views

### Which optimization algorithm is used in glm function in R?

One can perform a logit regression in R using such code: ...
4k 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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
2k views

### Testing random variate generation algorithms

Which methods are used for testing random variate generation algorithms?
10k 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 ...
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)?
31k 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 ...
18k 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 ...
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 ...
3k views

### Can someone please explain the back-propagation algorithm?

What is the back-propagation algorithm and how does it work?
16k 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: ...
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 ...
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 ...
8k views

### What fast algorithms exist for computing truncated SVD?

Possibly off topic here, but there exist several (one, two) related questions already. Poking around in the literature (or a google search for Truncated SVD Algorithms) turns up a lot of papers that ...