Questions tagged [approximation]

Approximations to distributions, functions, or other mathematical objects. To approximate something means to find some representation of it which is simpler in some respect, but not exact.

Filter by
Sorted by
Tagged with
38
votes
4answers
18k views

Approximate order statistics for normal random variables

Are there well known formulas for the order statistics of certain random distributions? Particularly the first and last order statistics of a normal random variable, but a more general answer would ...
28
votes
4answers
9k views

Intractable posterior distributions

In Bayesian statistics, it is often mentioned that the posterior distribution is intractable and thus approximate inference must be applied. What are the factors that cause this intractability?
23
votes
2answers
4k views

Are machine learning techniques “approximation algorithms”?

Recently there was a ML-like question over on cstheory stackexchange, and I posted an answer recommending Powell's method, gradient descent, genetic algorithms, or other "approximation algorithms". In ...
23
votes
2answers
4k views

Difference of two i.i.d. lognormal random variables

Let $X_1$ and $X_2$ be 2 i.i.d. r.v.'s where $\log(X_1),\log(X_2) \sim N(\mu,\sigma)$. I'd like to know the distribution for $X_1 - X_2$. The best I can do is to take the Taylor series of both and ...
20
votes
1answer
3k views

Error in normal approximation to a uniform sum distribution

One naive method for approximating a normal distribution is to add together perhaps $100$ IID random variables uniformly distributed on $[0,1]$, then recenter and rescale, relying on the Central Limit ...
19
votes
5answers
2k views

Why bother with low rank approximations?

If you have a matrix with n rows and m columns, you can use SVD or other methods to calculate a low-rank approximation of the given matrix. However, the low rank approximation will still have n rows ...
18
votes
3answers
5k views

Evaluate definite interval of normal distribution

I know that an easy to handle formula for the CDF of a normal distribution is somewhat missing, due to the complicated error function in it. However, I wonder if there is a a nice formula for $N(c_{-}...
17
votes
1answer
493 views

Root finding for stochastic function

Suppose we have a function $f(x)$ that we can only observe through some noise. We can not compute $f(x)$ directly, only $f(x) + \eta$ where $\eta$ is some random noise. (In practice: I compute $f(x)$...
16
votes
1answer
3k views

How does a random kitchen sink work?

Last year at NIPS 2017 Ali Rahimi and Ben Recht won the test of time award for their paper "Random Features for Large-Scale Kernel Machines" where they introduced random features, later codified as ...
15
votes
5answers
995 views

Approximation error of confidence interval for the mean when $n \geq 30$

Let $\{X_i\}_{i=1}^n$ be a family of i.i.d. random variables taking values in $[0,1]$, having a mean $\mu$ and variance $\sigma^2$. A simple confidence interval for the mean, using $\sigma$ whenever ...
13
votes
3answers
4k views

How to compute the probability associated with absurdly large Z-scores?

Software packages for network motif detection can return enormously high Z-scores (the highest I've seen is 600,000+, but Z-scores of more than 100 are quite common). I plan to show that these Z-...
12
votes
1answer
2k views

One sided Chebyshev inequality for higher moment

Is there an analogue to the higher moment Chebyshev's inequalities in the one sided case? The Chebyshev-Cantelli inequality only seem to work for the variance, whereas Chebyshevs' inequality can ...
12
votes
1answer
702 views

Approximate distribution of product of N normal i.i.d.? Special case μ≈0

Given $N\geq30$ i.i.d. $X_n\approx\mathcal{N}(\mu_X,\sigma_X^2)$, and $\mu_X \approx 0$, looking for: accurate closed form distribution approximation of $Y_N=\prod\limits_{1}^{N}{X_n}$ asymptotic (...
12
votes
3answers
17k views

Normal approximation to the Poisson distribution

Here in Wikipedia it says: For sufficiently large values of $λ$, (say $λ>1000$), the normal distribution with mean $λ$ and variance $λ$ (standard deviation $\sqrt{\lambda}$), is an excellent ...
12
votes
1answer
673 views

Assessments of “Approximately Normal” for t-tests

I am testing equality of means using Welch's t-test. The underlying distribution is far from normal (more skewed than the example in a related discussion here). I can obtain more data but would like ...
11
votes
1answer
186 views

Approximating $\log( E(X))$

I was casually reading an article (in economics) which had the following approximation for $\log(E(X))$: $\log(E(X)) \approx E(\log(X))+0.5 \mathrm{var}(\log(X))$, which the author says is exact if ...
11
votes
3answers
249 views

Approximating $Pr[n \leq X \leq m]$ for a discrete distribution

What's the best way to approximate $Pr[n \leq X \leq m]$ for two given integers $m,n$ when you know the mean $\mu$, variance $\sigma^2$, skewness $\gamma_1$ and excess kurtosis $\gamma_2$ of a ...
11
votes
1answer
191 views

Should degrees of freedom corrections be used for inference on GLM parameters?

This question is inspired by Martijn's answer here. Suppose we fit a GLM for a one parameter family like a binomial or Poisson model and that it is a full likelihood procedure (as opposed to say, ...
10
votes
1answer
8k views

What is the normal approximation of the multinomial distribution?

If there are multiple possible approximations, I'm looking for the most basic one.
10
votes
1answer
1k views

Do Gaussian process (regression) have the universal approximation property?

Can any continuous function on [a, b], where a and b are real numbers, be approximated or arbitrarily close to the function (in some norm) by Gaussian Processes (Regression)?
10
votes
2answers
4k views

When do Taylor series approximations to expectations of (entire) functions converge?

Take an expectation of the form $E(f(X))$ for some univariate random variable $X$ and an entire function $f(\cdot)$ (i.e., the interval of convergence is the whole real line) I have a moment ...
9
votes
2answers
844 views

Universal approximation theorem for convolutional networks

The universal approximation theorem is a quite famous result for neural networks, basically stating that under some assumptions, a function can be uniformly approximated by a neural network withing ...
8
votes
3answers
2k views

Does the universal approximation theorem for neural networks hold for any activation function?

Does the universal approximation theorem for neural networks hold for any activation function (sigmoid, ReLU, Softmax, etc...) or is it limited to sigmoid functions? Update: As shimao points out in ...
8
votes
4answers
5k views

normal approximation to the binomial distribution: why np>5?

Nearly every text book which discusses the normal approximation to the binomial distribution mentions the rule of thumb that the approximation can be used if $np\geq5$ and $n(1-p)\geq 5$. Some books ...
8
votes
2answers
2k views

variational bayes vs expectation propagation

Just wondering what are the advantages of using one over the other. I'm just looking for some general answers here. For starters: VB gives a guaranteed lower bound for the likelihood. EP is faster? ...
8
votes
2answers
372 views

What is the justification of using taylor approximations inside expectation operators?

I sometimes see people use taylor approximation as follows: $$E(e^x)\approx E(1+x)$$ I know that the taylor approximation works for $$e^x \approx 1+x$$ But it is not clear to me that we can do the ...
8
votes
1answer
2k views

How to understand the geometric intuition of the inner workings of neural networks?

I've been studying the theory behind ANNs lately and I wanted to understand the 'magic' behind their capability of non-linear multi-class classification. This led me to this website which does a good ...
8
votes
2answers
773 views

How to calculate tridiagonal approximate covariance matrix, for fast decorrelation?

Given a data matrix $X$ of say 1000000 observations $\times$ 100 features, is there a fast way to build a tridiagonal approximation $A \approx cov(X)$ ? Then one could factor $A = L L^T$, $L$ all 0 ...
8
votes
1answer
274 views

Analytically solving sampling with or without replacement after Poisson/Negative binomial

Short version I am trying to analytically solve/approximate the composite likelihood that results from independent Poisson draws and further sampling with or without replacement (I don't really care ...
8
votes
0answers
915 views

Universal Approximation Theorem — Neural Networks [closed]

I have posted this question elsewhere--MSE-Meta, MSE, TCS, MetaOptimize. Previously, no one had given a solution. But now, here is a really excellent and comprehensive answer. Universal approximation ...
7
votes
2answers
4k views

Fast approximation to inverse Beta CDF

I am looking for a fast approximation to the inverse CDF of the Beta distribution. The approximation need not be precise, but more stress is on simplicity (I'm thinking Taylor expansion of the first 1 ...
7
votes
3answers
1k views

How do extreme values scale with sample size?

Assume I have a random vector $X = \{x_1, x_2, ..., x_N\}$, composed of i.i.d. binomially distributed values. If it would simplify the problem substantially, we can approximate them as normally ...
7
votes
5answers
2k views

Approximation of logarithm of standard normal CDF for x<0

Does anyone know of an approximation for the logarithm of the standard normal CDF for x<0? I need to implement an algorithm that very quickly calculates it. The straightforward way, of course, is ...
7
votes
2answers
4k views

When is a second hidden layer needed in feed forward neural networks?

I'm using a feed forward neural network to approximate a function with 24 inputs, and 3 outputs. Most of the literature suggests that a single layer neural network with a sufficient number of hidden ...
7
votes
1answer
2k views

Why does the reconstruction error of truncated SVD equal the sum of squared singular values?

I saw this formula in a textbook: squared Frobenius norm of the original matrix $\mathbf X$ minus its truncated SVD $\mathbf X_k$ (which can be seen as the approximation error) equals the sum of ...
7
votes
1answer
158 views

Kernel smoothing for Edgeworth expansion

Suppose I have an estimator which includes an indicator function in the objective function, then the objective function is not smooth. But if I want to approximate the behavior of this estimator in ...
7
votes
1answer
500 views

Is applying the CLT to the sum of random variables a good approximation?

I use $(\mu, \sigma^2)$ to mean a distribution with mean $\mu$ and variance $\sigma^2$, $\mathcal{N}$ added to mean the normal distribution. Let's suppose $X_1, \dots, X_n\overset{\text{iid}}{\sim}(\...
7
votes
1answer
1k views

Distribution of the Levenshtein distance between two random strings

The Levenshtein or edit distance between two strings is the minimum number of edits (adding a letter, removing a letter or changing a letter) required to transform one into the other. Assume that we ...
7
votes
1answer
832 views

Berry-Esseen bound for binomial distribution

From the Berry-Essen theorem I can deduce $$\sup_{x\in\mathbb R}\left|P\left(\frac{B(p,n)-np}{\sqrt{npq}} \le x\right) - \Phi(x)\right| \le \frac{C(p^2+q^2)}{\sqrt{npq}}$$ with $C \le 0.4748$. My ...
6
votes
1answer
678 views

Numbers too large for R. How to approximate probability mass function?

Social network data is frequently found in a two-mode form: people vs. events they attend, people vs. classes they attend, countries vs. treaties they sign, etc. A strategy for analyzing this data is ...
6
votes
3answers
992 views

Approximation of Cauchy distribution

I have a ratio of two random, (dependent or independent) normally distributed variables. Knowing that the resulting Cauchy-distribution does not produce any moments. May I ask: Is there an ...
6
votes
2answers
373 views

Bayes Factor approximation

A brute force method to approximate the Bayes Factor (the ratio of the denominators (normalizing constants) in the Bayes formula) is to do the following for the two models of interest: repeat ...
6
votes
2answers
182 views

How to go about selecting an algorithm for approximate Bayesian inference

I am wondering if there are any good rules of thumb for how to go about selecting an approximate inference algorithm for a problem/model (specifically when exact inference is intractable)? When you ...
6
votes
3answers
325 views

Probability for finding a double-as-likely event

Repeating an experiment with $n$ possible outcomes $t$ times independently, where all but one outcomes have probability $\frac{1}{n+1}$ and the other outcome has the double probability $\frac{2}{n+1}$,...
6
votes
1answer
1k views

Approximating the distribution of a linear combination of beta-distributed independent random variables

This question is related with these other two questions in Cross Validated, which has been already answered: Approximate the distribution of the sum of ind. Beta r.v Central limit theorem when the ...
6
votes
1answer
303 views

Approximating P(A,B,C) using P(A,B), P(A,C), P(B,C), and P(A), P(B), P(C)

For some events $A$, $B$, $C$ I know the occurrence probabilities $P(A),\: P(B),\: P(C)$ I also know the pairwise co-occurance probabilities $P(A,B),\: P(A,C),\: P(B,C)$ I want to approximate the ...
6
votes
1answer
552 views

Half-normal probability plot

To construct the half-normal probability plot, plot the absolute values in a certain statistical diagnostic (residual, leverage, Cook distance and others) versus $z_i$ where: $\displaystyle z_{i} = \...
6
votes
1answer
203 views

Approximating the mathematical expectation of the argmax of a Gaussian random vector

Let $X = \left( {{X_1},...,{X_n}} \right) \sim \mathcal{N}\left( {{\mathbf{\mu }},{\mathbf{\Sigma }}} \right)$ be a Gaussian random vector and $I = \mathop {\arg \max }\limits_{i = 1,n} {X_i}$. $I$ ...
6
votes
3answers
2k views

What is the CDF of the sum of weighted Bernoulli random variables?

Let's say we have a random variable $Y$ defined as the sum of $N$ Bernoulli variables $X_i$, each with a different, success probability $p_i$ and a different (fixed) weight $w_i$. The weights are ...
6
votes
0answers
37 views

What bounds can we place on approximation error for a moment-matching approximation with $N$ moments?

Suppose I have a distribution over the real line ($p$) and I'm approximating it by matching its first $N$ moments. What can I say about the approximation error as a function of $N$? Alternatively, ...