Showing posts with label statistics. Show all posts
Showing posts with label statistics. Show all posts

Wednesday, January 3, 2018

Plotting MCMC chains in Python using getdist

This is a quick introduction to the getdist package by Antony Lewis, which allows visualizing MCMC chains.
from getdist import plots, MCSamples
import numpy as np

def main():
    mean = [0, 0, 0]
    cov = [[1, 0, 0], [0, 100, 0], [0, 0, 8]]
    x1, x2, x3 = np.random.multivariate_normal(mean, cov, 5000).T
    s1 = np.c_[x1, x2, x3]

    mean = [0.2, 0.5, 2.]
    cov = [[0.7, 0.3, 0.1], [0.3, 10, 0.25], [0.1, 0.25, 7]]
    x1, x2, x3 = np.random.multivariate_normal(mean, cov, 5000).T
    s2 = np.c_[x1, x2, x3]

    names = ['x_1', 'x_2', 'x_3']
    samples1 = MCSamples(samples=s1, labels=names, label='sample1')
    samples2 = MCSamples(samples=s2, labels=names, label='sample2')

    g = plots.getSubplotPlotter()
    g.triangle_plot([samples1, samples2], filled=True)
    g.export('triangle_plot.png')
    g.export('triangle_plot.pdf')
    return 

if __name__ == "__main__":
    main()
which results in

We can also plot the constraints on the individual parameters
def get_constraints(samples):
    for i, mean in enumerate(samples.getMeans()):
        upper = samples.confidence(i, upper=True, limfrac=0.05)
        print("\nupper limit 95 C.L. = %f" % upper)
        lower = samples.confidence(i, upper=False, limfrac=0.05)
        print("lower limit 95 C.L. = %f" % lower)
        print("%s = %f +/- %f +/- %f" % (samples.parLabel(i),\
        mean, mean - samples.confidence(i, limfrac=0.16),\
        mean - samples.confidence(i, limfrac=0.025)) )
    return 
which in our case looks like this
upper limit 95 C.L. = 1.653261
lower limit 95 C.L. = -1.637202
x_1 = 0.000167 +/- 0.996626 +/- 1.958270

upper limit 95 C.L. = 16.365135
lower limit 95 C.L. = -16.484502
x_2 = -0.010400 +/- 9.874866 +/- 19.682727

upper limit 95 C.L. = 4.637981
lower limit 95 C.L. = -4.656869
x_3 = -0.009280 +/- 2.827152 +/- 5.571246
While in our case we set the variance and covariance of the parameters manually at the beginning to generate the samples, usually one gets an MCMC chain and wants to determine these parameters. To get the covariance matrix between two parameters we have to use the cov() function and provide the index of the parameters
print("cov(x_1, x_3) = ", samples2.cov(pars=[0,2]))
print("cov(x_1, x_2) = ", samples2.cov(pars=[0,1]))
which in our case just reproduces the input values
cov(x_1, x_3) =  [[ 0.69364079  0.10129875]
 [ 0.10129875  7.13148423]]
cov(x_1, x_2) =  [[  0.69364079   0.30451831]
 [  0.30451831  10.05805092]]
I posted the example code above on GitHub
best
Florian

Saturday, May 27, 2017

The second law of thermodynamics

In this blog post I want to discuss one of the most fundamental laws of statistical physics, known as the second law of thermodynamics:

The entropy of a closed system tends to a maximum

This definition is a bit loose and implies that you know what entropy is. I will define entropy formally below, but for now let's say entropy is a measure for how spread out energy is in a system. A system with the same density, temperature and pressure everywhere has a very high entropy. A system where one part has a higher temperature and another has a lower temperature, like a hot and a cold plate as shown in Figure 1 (left),  has a low entropy, because the energy is clustered in the high temperature part.
Figure 1: Example of a low entropy system (left) and a high entropy system (right). Entropy is a measure for how spread out energy is in a system.
After the plates are brought in contact (Figure 1, middle), the temperature averages due to a flow of energy from hot to cold. The system on the right of the figure has a high entropy, since the energy is now evenly spread out in this system.

Entropy 


The formal definition of entropy is given by
\[
S = k_B\ln\left[\Omega(E)\right],
\]where $k_B=8.617\times10^{-5}\,\text{eV/K}$ is the Boltzmann constant and $\Omega(E)$ represents the available states of a system. The fact that systems have states which they can reside in is a fundamental principle of Quantum Mechanics.

For example the electron which is bound to a proton, forming a Hydrogen atom, has different energy levels it can occupy. The electron can go to a lower energy state by emitting photons. Since the energy states are discrete, the photon energies emitted by a hydrogen atom are equivalent to the difference in the energy levels available for the electron.

The energy state with the lowest energy is called the ground state. Using the Bohr-Sommerfeld approximation the different energy levels of the hydrogen atom are given by
\[
E_n = - \frac{  m_e e^4}{2 ( 4 \pi \epsilon_0)^2 \hbar^2 } \frac{1}{n^2} = \frac{-13.606\,\text{eV}}{n^2},
\]with $n = 1$ referring to the ground state, $m_e$ is the electron mass, $e$ is the electron charge and $\epsilon_0$ is the electric permeability. This equation ignores all kinetic states, which are given by the quantum numbers $\ell = 0$, ..., $n-1$, $m = -\ell$, ..., $\ell$ and the spin $\sigma = [-\frac{1}{2}, \frac{1}{2}]$. A more complete treatment would be given by the Dirac equation.

If we simplify the picture and just assume that all kinetic energy states corresponding to the main quantum number $n$ have exactly the same energy, we can calculate the number of states $\Omega$ as a function of energy.
Figure 2: Number of energy states for the hydrogen atom as a function of energy.
Figure 2 shows the enormous increase of available states for the electron in a hydrogen atom at large energies. The ground state is at $E = -13.606\,$eV, which is the minimum energy a hydrogen atom can have. The number of available states is much larger at larger energies which means that entropy is maximised at large energies.

The second law wants to maximise the total entropy of the system. From intuition we know that bringing cold and hot objects together, the temperature will average out. This means that cold atoms are lifted into higher states and hot atoms are moved to lower energy states. But is this really maximising entropy? After all, the hotter atoms now occupy lower energy states, which have smaller $\Omega$ and therefore the entropy of those atoms has decreased.

Let's look at a system of 6 hydrogen atoms. The second law tells us that the total entropy of all hydrogen atoms tends towards a maximum. Let's assume the system has enough energy to put all atoms in $n=2$. We could move one atom from $n=2$ into the ground state, which releases energy, which we can use to lift the other 5 atoms to $n=3$, because the difference in energy between $n=2$ and $n=3$ is only $E = 1.888\,$eV, while moving the one atom from $n=2$ to $n=1$ releases $E = 10.206\,$eV of energy. Since the other 5 atoms are in a larger energy state, they will have more entropy, while the one atom in the ground state lost some entropy.

If such a process would maximise the total entropy, we would expect that a gas left alone would separate into cold and hot atoms over time. This is of course not what happens in reality, so let's check that keeping all atoms at $n=2$ does indeed maximise entropy.

First I have to say that this is a rough treatment, since the different kinetic energy states are not actually all degenerate, so the proper treatment is more complicated. I will also ignore the proportionality constant $k_B$ when calculating entropy.

We start with 6 atoms in n=2. Considering all kinetic quantum numbers we have

$n = 1$: $\Omega = 2$, $E = -13.606\,$eV
$n = 2$: $\Omega = 12$, $E = -3.40\,$eV
$n = 3$: $\Omega = 30$, $E = -1.512\,$eV

The number of states can be calculated by considering all available quantum numbers. The ground state for example has only the spin of the electron which can have two values and hence $\Omega = 2$. With 6 atoms in $n=2$ we have $S_{\rm total} = 6*\ln 12 = 14.88$, where I ignored the Boltzmann constant.

If we now move one atom to $n=1$ we get enough free energy to lift the other 5 atoms to $n=3$. What would be the entropy of this new system?
\[
S_{\rm total} = S_{n=0} + S_{n=3} = \ln 2 + 5*\ln 30 = 10.89,
\]therefore we indeed maximise entropy by putting all hydrogen atoms in the same state. This explains why the temperature of two gases averages when they come in contact and why the second law can also be formulated as 'Heat always moves from high to low temperatures'.

Finally I should say that with 6 atoms we do not actually have a statistically significant sample, which makes the application of the second law difficult. We will for the rest of this post move away from talking about energy states $\Omega$ but you should keep in mind that entropy has a sound motivation based on quantum states.

Maxwell's Demon 


James Clerk Maxwell proposed a thought experiment, which seems to violate the second law of thermodynamics, called Maxwell's Demon. Maxwell imagined two gases A and B in isolated condition with a wall between. The wall can be opened to let particles move between A and B. This wall is operated by a demon. The demon measures speed of particles moving towards the wall and opens the wall whenever a particle with larger than average speed moves from A to B and when a particle with less than average speed moves from B to A. Since speed is equivalent to temperature, this procedure will increase the temperature of B and reduce the temperature of A without any energy being added to the system. This reduces the entropy of the system and therefore violating the second law.

In 1929 the physicist Leo Szilard showed that Maxwell's Demon does not violate the second law, because the demon needs to know the velocities of a very large number of particles, and to obtain that information would require a small amount of energy. Including this energy into the calculation the system does comply with the second law.

Heat engines 


A heat engine is a system where the difference in temperature of two reservoirs is used to produce work. For example petrol is burned in a car engine, which moves pistons to produce mechanical work. Above we formulated the second law of thermodynamics in a sentence as 'a closed system tends towards maximum entropy'. We can define the entropy change of a system ($\Delta S$) as the heat which has entered a closed system ($Q$) divided by the common temperature ($T$) at the point where the heat transfer took place:
\[
\Delta S = \frac{Q}{T}.
\]A perfect heat engine with $100\%$ efficiency would be a system where one uses heat from a hot reservoir and turns all the heat into work. This is in practice impossible, since the efficiency of any heat engine is given by
\[
e = 1 - \frac{T_{\rm cold}}{T_{\rm hot}},
\]which implies that one would need a reservoir with $T_{\rm cold} = 0$ or $T_{\rm hot} = \infty$ to achieve $100\%$ efficiency. Typical combustion engines operating between $1700\,$Kelvin and $298\,$Kelvin, leading to a maximum efficiency for such an engine of $82\%$. Friction and waste processes usually lead to an effective engine efficiency significantly below this limit.

Heat engines work because heat naturally flows from hot to cold places. If there were no cold reservoir towards which it could move there would be no heat flow and the engine would not work. 

Arrow of time 


Given that the second law tells us that systems move towards maximum entropy, we can infer from the entropy of a system at different times, which is earlier and which is later in time. If we see a hot coffee and a cold coffee we can infer that the coffee was hot first and then cooled down. We would never see the process going the other way, in a closed system.

The entropy of the hot coffee is smaller, since the energy is clustered in the coffee, while after a while the heat is distributed to the surroundings and the entropy increased. This means that entropy defines an arrow of time.

You can even take this further and ask what this means for the Universe as a whole, since the second law says that the final state of the Universe will be a state of maximum entropy.

Why do we have structure in the Universe? 


The Universe can, in some approximation, be described as a closed system, and therefore the entropy will increase. That means that the Universe will tend towards a state where the mean density and temperature are equal everywhere, the so called heat death.

You might ask how galaxies and black holes will ever give up their particles. Well our planet does actually lose material all the time, since gas which escapes the gravitational potential will just fly out in space. On a very long timescale this will result in all stars, planets and galaxies to evaporate into space.

Even though black holes in principle cannot lose material (not even light can escape black holes), they do produce a radiation, called Hawking radiation, which eventually will cause all black holes to evaporate. The time scale for that to happen is very very large, but it will happen eventually. Probably black holes are the last low entropy islands, before the total entropy reaches its maximum.

The heat death state of the Universe is fairly hopeless for any life since at that point all energy is trapped in entropy, which cannot be moved to a lower energy state to produce mechanical work. To move a system to a lower state we would need a reservoir with a lower temperature, but at the heat death the temperature is the same everywhere.

Given the law as described above, one might ask how did we end up with structure in the Universe? The Universe started off very homogenous. For example the Cosmic Microwave Background (CMB) tells us that the average fluctuation in the density field of the Universe $300\,000$ years after the big bang was $10^{-5}$. Today, 11 billion years after the big bang, these fluctuations are of order $1$. So this means matter (and hence energy) got more clustered over time? Isn't this violating the second law of thermodynamics and implying a process which leads to a reduced entropy?

Not really. Remember, the temperature is in the denominator of the equation for $\Delta S$ and the high temperature at early times means that the entropy actually increased since then. So the structure growth in the Universe does not violate the second law. However, as mentioned before, given enough time, the second law will smooth out all structure in the Universe.

cheers
Florian

Monday, April 10, 2017

Singular Value Decomposition (SVD) and Principal Component Analysis (PCA) -- finding useful features

In this blog post I will discuss how to use Singular Value Decomposition (SVD) and Principle Component Analysis (PCA) to determine the number of useful features in a feature vector. Whenever tackling a machine learning problem with a large number of available features, one should do a PCA as the first step, since in many cases reducing the dimensions of the problem can speed up the project significantly.

Ok, let's assume we have a table of data on properties, with the age of the house, the size in m$^2$, the size in feet$^2$ (for all the Americans out there) and the price:

Age [years] size [in m$^{2}$] size [in feet$^{2}$] price [in US$]
50 80 861 1 000 000
45 95 1023 850 000
5 115 1238 400 000
12 125 1345 600 000
25 105 1130 800 000
2 120 1292 300 000
33 110 1184 1 000 000
43 75 807 1 200 000
42 145 1561 700 000
21 80 861 400 000
51 80 861 1 300 000
110 80 861 1 000 000
12 80 861 300 000
9 80 861 650 000

Of course this dataset is too small to learn anything useful, but it's big enough for me to show the use of SVD and PCA.

Assume we use the table above to train a machine learning model with the hope that we can predict prices for other houses given the age and size. That would be quite useful to have if you want to buy a house in the same area as the houses in the table, or if you run a real estate business.

Let's use all columns above as features to train our model. We start preparing the data:
X = np.matrix([[50., 80., 861., 1000000], 
               [45., 95., 1023., 850000], 
               [5., 115., 1238., 400000],
               [12., 125., 1345., 600000],
               [25., 105., 1130., 800000],
               [2., 120., 1292., 300000],
               [33., 110., 1184., 1000000],
               [43., 75., 807., 1200000],
               [42., 145., 1561., 700000],
               [21., 80., 861., 400000],
               [51., 80., 861., 1300000],
               [110., 80., 861., 1000000],
               [12., 80., 861., 300000],
               [9., 80., 861., 650000]])
# Lets subtract the mean of each column and divide the by range (feature scaling)
for col in range(0,X.shape[1]):
  X[:,col] = ( X[:,col] - np.mean(X[:,col]) )/( np.max(X[:,col]) - np.min(X[:,col]) )
Here we subtracted the mean of each column and divided by the range. This is important, since if we do not do this the price is dominating the variance, since it has in absolute terms much larger values than the age or size columns.

Ok now we have our feature matrix X with which we want to train the data. Let's assume the best fitting model is determined by some maximum likelihood procedure, minimising the $\chi^2$
\[
\chi^2 = \sum_{ij} (x_i - y_i)C_{ij}^{-1} (x_j - y_j).
\]As you can see to calculate this $\chi^2$ we need the covariance matrix $C_{ij}$, which is defined as
\[
C_{ij} = \frac{1}{N}\sum^N_k(x^k_i - \mu_i)(x^k_j - \mu_j),
\]where $N$ is the number of rows in our table, $x_i^k$ is the $i$-th element in row number $k$ and $\mu_j$ is the mean value of all entries in column $j$.

Given that we already transformed our data by subtracting the mean
\[
x_i \rightarrow x_i - \mu_i,
\]we can write the equation for the covariance matrix simply as
\[
C = \frac{1}{N}X^TX,
\]where $X$ is the matrix representation of our table above, with $6$ rows and $4$ columns.

The covariance matrix can be calculated quite easily using numpy:
C = np.cov(X, rowvar=False)
To calculate $\chi^2$ we need the inverse of that covariance matrix. A matrix can only be inverted if it is non-singular, or in other words the rank of the matrix needs to be equal to its dimension:
from numpy.linalg import matrix_rank
print "rank of C = %d, while shape is %s" % (matrix_rank(C), C.shape)
which gives the output

>> rank of C = 3, while shape is (4, 4)

As you might have expected the $4\times 4$ covariance matrix has only rank $3$ and hence cannot be inverted. The reason why this happened is that our original feature data has two columns that provide identical information. The size in m$^2$ and the size in feet$^2$ represent the same property of the house and are $100\%$ correlated.

Another way of saying this is that the rank of a matrix is determined by the number of orthogonal eigenvectors which one can find for the matrix. Given that in our matrix two columns are just scaled versions of each other, they can be described by the same eigenvector.

For that reason it is important that we only include independent features in our data vector. However, usually the picture is not quite as black and white as shown above. What if the correlation between two features is not quite $100\%$ but $99\%$ or $90\%$? Should we include the feature or exclude it? What if we have $10\,000$ features? Do we really want to go through all of them to check whether they are correlated?

This is where Principal Component Analysis (PCA) can help. PCA allows to detect the components with the largest variance in the data. PCA thus can have the effect of concentrating much of the signal into the first few principal components. Reducing your analysis to those components can make life much easier.

This always has to be balanced against the potential loss of information when removing certain components. We can calculate the principal components using Singular Value Decomposition (SVD). Our covariance matrix $C$ is quadratic, with 4 rows and 4 columns. In the quadratic case SVD is often called eigenvalue decomposition. It can be shown that $C$ can be represented by two other matrices $V$ and $S$ as:
\[
C = VSV^T,
\]where $V$ is a matrix containing the eigenvectors of $C$, and $S$ is a diagonal matrix containing the eigenvalues of $C$. The eigenvectors describe the direction of the principal component and represent an orthogonal base. Projections of the data on the principal axes are called principal components.

The $j$ principal component is given by the $j$-th row of $XV$. SVD of the original data matrix is given by
\[
X = USV^T
\]and that implies for the covariance matrix
\[
C = XX^T = \frac{VSU^TUSV^T}{(N-1)} = \frac{VS^2V^T}{(N-1)}.
\]The principal components can be calculated as $XV = USV^TV = US$
U, s, V = np.linalg.svd(X, full_matrices=False)
S = np.diag(s)
print "US = ", U.dot(S)
which gives

>> US =  [[  4.64105174e-01  -4.58797902e-02   1.87296123e-02   4.84869440e-16]
 [  1.29659668e-01  -8.97596094e-02  -3.32400592e-02   7.15735005e-16]
 [ -5.29410729e-01   1.69369612e-01   4.41330595e-03   5.95354396e-16]
 [ -5.86630610e-01  -1.09955994e-01   6.54082083e-02   5.51960575e-16]
 [ -1.21483834e-01  -7.94351556e-02   8.68858184e-02   4.53123083e-16]
 [ -6.67336389e-01   1.94703324e-01  -3.17861692e-02   4.41462214e-16]
 [ -9.16426053e-02  -3.07119687e-01   1.41294505e-01   5.11747418e-16]
 [  6.16479613e-01  -9.51629654e-02   1.88312161e-01   5.36814447e-16]
 [ -7.86901776e-01  -5.34895939e-01  -1.07054260e-01   4.73497220e-16]
 [  1.07328864e-01   4.91088137e-01  -1.09638239e-01   5.12658847e-16]
 [  6.01525587e-01  -2.54710265e-01   1.84835593e-01   4.60299469e-16]
 [  6.46184026e-01  -3.11006408e-01  -4.34257301e-01   4.94555877e-16]
 [  3.52217810e-02   5.98994362e-01  -9.95754561e-02   4.87155668e-16]
 [  1.82901232e-01   3.73770379e-01   1.25672280e-01   4.96024184e-16]]

To reduce our number of components from 4 to 3 we just have to pick the 3 first columns of $U$ and the $3\times 3$ upper left part of $S$. Their product $X_3 = U_3S_3$ is the required $6\times 3$ matrix containing the $3$ principal components with the highest variance
k = 3
print "k = %d" % k
print "US_k = ", U[:, 0:k].dot(S[0:k, 0:k])
>> US_k =  [[ 0.46410517 -0.04587979  0.01872961]
 [ 0.12965967 -0.08975961 -0.03324006]
 [-0.52941073  0.16936961  0.00441331]
 [-0.58663061 -0.10995599  0.06540821]
 [-0.12148383 -0.07943516  0.08688582]
 [-0.66733639  0.19470332 -0.03178617]
 [-0.09164261 -0.30711969  0.14129451]
 [ 0.61647961 -0.09516297  0.18831216]
 [-0.78690178 -0.53489594 -0.10705426]
 [ 0.10732886  0.49108814 -0.10963824]
 [ 0.60152559 -0.25471026  0.18483559]
 [ 0.64618403 -0.31100641 -0.4342573 ]
 [ 0.03522178  0.59899436 -0.09957546]
 [ 0.18290123  0.37377038  0.12567228]]


But how can we now quantify the amount of information loss due to the removed components?


$X_k$ is going to be an approximation to $X$ and since $X$ contains all the information we want to keep, the difference between $X$ and $X_k$ should be small. We can get the retained variance in the first $k$ principal components directly from the Eigenvalues which the SVD gave us

The Eigenvalues show variances of the respective PCs and hence we can calculate
\[
\frac{\sum^k_i s_{ii}}{\sum^N_i s_{ii}},
\] which gives the ratio of the retained variance in the first k principal components.
print("the retained variance is = ", sum(s[:k])/sum(s))
and with $k=3$ we find

>> the retained variance is =  1.0

In our case we do not lose any information, since the feature we removed did not have any useful information. If we were to exclude the two smallest principles component ($k=2$) we would get
k = 2
print("k = %d" % k)
print("US_k = ", U[:, 0:k].dot(S[0:k, 0:k]))
print("the retained variance is = ", sum(s[:k])/sum(s))
>> k = 2
US_k =  [[ 0.46410517 -0.04587979]
 [ 0.12965967 -0.08975961]
 [-0.52941073  0.16936961]
 [-0.58663061 -0.10995599]
 [-0.12148383 -0.07943516]
 [-0.66733639  0.19470332]
 [-0.09164261 -0.30711969]
 [ 0.61647961 -0.09516297]
 [-0.78690178 -0.53489594]
 [ 0.10732886  0.49108814]
 [ 0.60152559 -0.25471026]
 [ 0.64618403 -0.31100641]
 [ 0.03522178  0.59899436]
 [ 0.18290123  0.37377038]]
the retained variance is =  0.834720270224

and hence we would lose a significant amount of information.

It makes sense to remove features if they add only a small amount of information, but generally you want to keep this fraction high e.g. $0.9$, which means that the $k$ highest principal components you keep should contain $90\%$ of the information.

I posted the entire Python code on Github. Let me know if you have comments/questions below.
cheers
Florian

Thursday, March 16, 2017

Accounting for the look-elsewhere effect in A/B testing

If we perform an A/B test we are trying to confirm or disprove a null hypothesis. Such a test will never be perfect, but will always have an error associated with it. For example, if we managed to rule out our null hypothesis with $2\sigma$ ($95\%$ confidence level), there is a $5\%$ chance that we just measured a random fluctuation and our null hypothesis is actually true (false positive or type 1 error). If that risk is too high, we can collect more data and reduce the risk, but we will never manage to entirely get rid of it.

So what happens if we perform a double A/B test, meaning we compare our control sample to two modifications. Well, now we have a $5\%$ chance to see a random fluctuation outside the $95\%$ confidence level for either one of our test samples. If we test in both cases for a $95\%$ confidence interval the chance to confirm both null hypotheses is 
\[
(1 - 0.05)^2 = 0.9025,
\] meaning $\approx 90\%$. So this means we have a $10\%$ chance to get at least one $2\sigma$ event, even if the null hypothesis is true. If we compare $20$ samples we get \[
(1 - 0.05)^{20} = 0.358.
\]So now we have already a $64.2\%$ chance to see at least one random $2\sigma$ fluctuation. This is called the look-elsewhere effect. Looking at many experiments, we increase the chance of seeing a significant fluctuation away from the null hypothesis, even if the null hypothesis is true.

This means that performing one test and encountering a $2\sigma$ fluctuation is more significant than performing many tests and encountering one $2\sigma$ fluctuation because if you perform enough tests you are basically guaranteed to find a $2\sigma$ fluctuation. 

How can we account for the look-elsewhere effect? 


The easiest way to correct for it is to keep the participants in an A/B test small. Beyond that, we have to collect more data to get back to a higher confidence level. The most conservative solution is a correction of $1/k$ to the accepted false positive rate, with $k$ being the number of tests. This means if we accepted $5\%$ false positive rate for a one way A/B test we have to change that to $2.5\%$ for a two-way A/B test and to $0.25\%$ for a $20$ way A/B test. 

One should be aware that increasing the confidence level too conservatively might increase our false negative rate (type 2 error). There are many other more relaxed corrections like the Holm-Bonferroni method or the Sidak correction, but in all cases, we end up collecting more data. 

An alternative approach: Analysis of Variances (ANOVA) 


For an ANOVA F-test we start with the null hypothesis that all sample means are equal 
\[
H_0 = \mu_0 = \mu_A = \mu_B = ...
\]The alternative hypothesis is that at least two of the means are not equal. The ANOVA F-test statistic is the ratio of the average variability among groups to the average variability within groups: \[
F = \frac{\frac{1}{k-1}\sum^k_{i=1}N_i(\mu_i - \overline{\mu})^2}{\frac{1}{N-k}\sum^k_{i=1}\sum^N_{j=1}(x_{ji} - \mu_i)^2},
\]where $\mu_i = \frac{1}{N}\sum^N_{j=1}x_{ji}$ is the mean for sample $i$ and $\overline{\mu} = \frac{1}{k}\sum^k_{i=1}\mu_i$ is the mean of the means for all $k$ samples. The denominator of this equation describes the average variance for the different samples, while the numerator describes the variation of the sample means around the global mean.

One should note that the ANOVA method assumes that the variances are approximately equal between the different treatments. This, however, is usually true, if the different samples are reasonably similar. 

After performing the F-test one has to use the degrees of freedom together with the F value to get the p-value from the F distribution. If this fails to reject the null hypothesis, the test is over and none of the variations does better than the control. If the null hypothesis is rejected we know that at least two means are significantly different from another. In this case, one has to proceed with post-hoc tests to identify where the difference occurred. 

The advantage of using ANOVA over multiple t-tests is that the ANOVA F-test will identify if any of the group means are significantly different from at least one of the other group means with a single test. If the significance level is set at $95\%$, the probability of a Type I error for the ANOVA F-test is $5\%$ regardless of the number of groups being compared. 

One disadvantage is that the F-test does not look at deviations from the control sample, but for outliers in the set of samples. There is, for example, no way to account for negative outliers. If you have a layout which is significantly worse compared to the control it will also result in a large F-value even though you might not be interested in layouts which do worse than your control. 

Example 


We have 3 website layouts (variation $A$ and $B$ and the control sample $0$) and we want to study whether any of those increases the download rate. First, we state the null hypothesis, which in this case is that the mean download rate is the same for the new and the control samples 
\[
H_0 = \mu_0 = \mu_A = \mu_B.
\]Now we have to state what is the improvement we are aiming for and with what significance do we want to confirm our null hypothesis? Well, let's assume we are looking for a $10\%$ improvement and are content with a $95\%$ confidence level.

Since we are working in a business environment we now want to ask the question how much data do we have to collect? Collecting too much data is connected to a cost. To estimate the sample size, we just need to re-write our equation for the F-test above 
\[
N-k = \frac{F\sum^N_{j=1}(x_{ji} - \mu_i)^2}{\frac{1}{k-1}(0.1\mu_0)^2},
\]where I replaced $\sum^k_{i=1}(\mu^i - \overline{\mu})^2$ with $(0.1\mu_0)^2$, which basically states that one sample has a $10\%$ deviation in the mean download rate. I also assumed that all samples have the same size $N_i = N_j$.

Now we go to the F-statistic and check what F value would represent a $95\%$ confidence level. For that, we need the degrees of freedom. We have $k-1$ degrees of freedom in the numerator quantity and $N-k$ degrees of freedom in the denominator. Note that the F-distribution is not symmetric, so you have to use the correct order here. 

We can assume that $N-k$ is very large (here I assume $N = 10\,000$) and integrate the F distribution
# Input parameters
Nminusk = 10000
kminus1 = 2
step = 0.001

# Integrate the F-distribution to get the critical value
F = 0.
integrate = 0
while integrate < 0.95:
    F += step
    integrate += f.pdf(F, kminus1, Nminusk)*step
    if integrate > 0.95:
        print "F value at 95%% confidence level is %0.1f" % F
        break
which gives

>> F value at 95% confidence level is 3.0

As long as $N$ is large ($>30$), the result does not depend on its exact value. There might be a Python function to directly print out this value, but I could not find it (there are also online tools available). Here is a plot of the F distribution for our case
Figure 1: F-distribution for the case of $N = 10\,000$ and $2$ degrees of freedom. The dashed line shows the $2\sigma$ significance level, meaning any F value larger than that indicates a significant result.

Finally, we need an estimate of the variance in the distribution. If we assume we had a download rate of $2\%$ in the past, we get $\sigma^2_s = 0.02(1 - 0.02) = 0.0196$ assuming a Bernoulli distribution for the variance. Putting it all together we get
\[
N = \frac{3\sigma_s^2}{\frac{1}{2}(0.1\mu_0)^2} = 29400.
\]Great! Now we have a number to work with.

Let's assume after a few days we get a table back showing

samplevisitorsdownloadsfraction
control294005000.0190
A294006200.0235
B294004900.0186

The first step is to test whether the F-test assumptions actually held in this case, meaning we have to check whether the sample variances $\sigma^2_s$ for the different samples are approximately equal. Let's assume that this is true in our case above.

Next we have to calculate the $F$ value, which in the above case gives $F = 3.38 > 3$. This means we can rule out the null hypothesis and know that the scatter of the means is not consistent with them all being equal (at our chosen confidence level). Note that this does not necessarily mean that one of the new layouts does better than the control.

So where do we go from here?

Post-hoc tests 


The problem after ruling out the F-test null hypothesis is that now we want to know where the difference actually happened. This requires to look at the samples themselves and that has all the look-elsewhere issues we discussed before. So to protect us from the look-elsewhere effects, we now have to ask for a higher confidence level, in our case with $k = 3$ we should ask for $1 - 0.05/3 = 0.983 \rightarrow 98.3\%$ confidence levels.

Next we have to state the t-test null hypothesis. In our case that is
\[
\begin{align}
H^A_0 &= \mu_A - \mu_0 \leq 0,\\
H^B_0 &= \mu_B - \mu_0 \leq 0
\end{align}
\] and we still look for a $10\%$ improvement over the control sample with the now required confidence of $98.3\%$. The details about t-tests have been discussed in my last blog post.

The required t-value can be obtained from a t-distribution and for a $98.3\%$ significance we need a t-value of $2.12$. Our t-values are $t = 3.26$ for layout $A$ and $t=-0.32$ for layout $B$, indicating a significant improvement of the download rate with layout $A$ compared to the control. It is definitely possible that the post-hoc t-tests are inconclusive and that more data needs to be collected.

As a final note, I would like to point out that looking at your experiment many times can be beneficial. Some layouts might be so good, that you can already see a significant improvement over control after looking at a small sample $N$, even though your smaller target improvement (in our case $10\%$) requires a much larger $N$.

So one strategy could be to look at your data at certain intervals and check whether a significant improvement is already present. Of course, every look at your data comes with a price tag, since now one has to increase the required confidence level as described above. However, one might catch significant improvements early and be able to stop the trial earlier. Or one could send more data into the good layouts and less into the bad layouts. Google for example follows such an approach.

The Python code used above is available on Github. Let me know if you have any questions/comments below.
cheers
Florian

Monday, March 6, 2017

Hypothesis testing: Using the t-test to evaluate an A/B test

A/B testing is a common tool to improve the customer engagement with a website. The objectives are often to increase the sign up or download rate.

Let's assume we have a website and we want to test it against a modification $A$ of that website (we changed the download button for example). How do we determine whether the new layout does better than the old?

Well we divide the website traffic up into 2 groups, each directed to one of the layouts. We then check whether the new layout increases our measure of interest (download rate).

Before starting the A/B test we have to clearly specify:

(1) What is the null hypothesis?
(2) What is the minimum/expected improvement we are looking for?
(3) What is the level of significance we are content with?

Let's start with (1), what is the null hypothesis that we want to disprove. Usually the null hypothesis is that the new layout does not do any better than the original layout, which can be written as
\[
H_0 = \mu_A - \mu_0 \leq 0,
\]where $\mu$ is the mean download rate. The alternative hypothesis is that $\mu_A > \mu_0$, meaning that there is an actual improvement. However, we can't just look for any improvement; we need to look for a clearly specified goal. That is the point of (2).

Let's assume we are looking for an improvement of at least $10\%$ in the download rate. This is a clear goal and we can write the alternative hypothesis as $\mu_A - \mu_0 > 0.1\mu_0$.

Finally (3), we have to specify a level of confidence which is enough for us to make a decision. A common value people like to choose is $95\%$ confidence level, meaning that if we claim at the end that the null hypothesis has been ruled out, there is a $5\%$ chance that we are wrong and we just observed a random fluctuation in the data (type 1 error). This might be too risky for some applications, e.g. clinical trials. In that case one can require a higher confidence level like $99.9\%$, which reduces the chance for a type 1 error to $0.1\%$. Note that statistics will never give you $100\%$ certainty, but if you are willing to collect more and more data, you can approach $100\%$ as closely as you want.

After specifying the setup of the A/B test we can now calculate the number of users required to rule out or confirm the null hypothesis. This is usually required in an industry environment, since our A/B test is always connected to a cost.

Before we calculate the number of users we have to specify how we want to evaluate the A/B test. There are at least two options here, a Z-test or a t-test, so what is the difference between the two?

Difference between Z-test and t-test


The Z-test and t-test are both used to determine the hypothesis that a population mean equals a particular value or that two population means are equal. In both cases we only approximate the confidence level, since we calculate the confidence under certain assumptions for the probability distribution. The Z-test for example assumes that the probability distribution around the null hypothesis is Normal distributed. The t-test assumes that the probability distribution around the null hypothesis follows a Student-t distribution. Note that in both cases we assume that the null hypothesis is true.

Both the Z-test and the t-test rely on other assumptions, which are often broken in real data, so it is important to be aware of these assumptions (and test them):

(1) The samples we look at are random selections from the population
(2) The samples are independent
(3) The sample distribution is approximately Normal

The t-test accounts for additional variations because of small number statistics by using the degrees of freedom (dof) in the probability distribution. For a large number of degrees of freedom the t-test becomes very similar to the Z-test, since the Student-t distribution approximates a Normal distribution. So in general one should use the t-test if the sample is small, while the Z-test can be used if the sample is large.

Here is the definition for the Z-test:
\[
Z = \frac{x - \mu_p}{\frac{\sigma_p}{\sqrt{N}}},
\]where $\sigma_p$ is the population standard deviation, $\mu_p$ is the population mean and $N$ is the sample size. The Z-value calculated with this equation has to be compared to a Normal distribution to get the p-value.

The t-test is defined as
\[
t = \frac{x - \mu_s}{\frac{\sigma_s}{\sqrt{N}}},
\]where $\mu_s$ is the mean of the sample and $\sigma_s$ is the standard deviation of the sample. The t-test has to deal with the additional uncertainty from the fact that the standard deviation $\sigma_s$ has been derived from the sample itself. It does this by using the Student-t distribution instead of the Normal distribution, which is generally broader than a Normal distribution, but approximates the normal distribution for large samples $N$.
Figure 1: Several Student-t distributions with different degrees of freedom (black lines) compared to a normal distribution (blue line).

So the claim here is, that if we pick many samples $X_i$ from the population, construct a t-test for all samples and plot their distribution, they will follow a t-distribution, if the null hypothesis is true.

The number of degrees of freedom is given by the number of samples minus the number of constraints. Since for these tests we usually use the data to constrain two parameters (the mean and standard deviation), we get $N-2$. However, you should check in your particular case whether this is still true. We will talk more about the exact treatment later.


Example


Here we will look at the download rate of a website, meaning the ratio of users who download our product, relative to the total number of users who come to the site. We have two layouts for our website, the new layout $A$ and the old (control) layout. First we specify the setup of our test:

(1) The null hypothesis is that the new layout is not any better than the control $H_0 = \mu_A - \mu_0 \leq 0$
(2) We are looking for a $10\%$ improvement in the download rate
(3) We want to see a confidence level of $95\%$

The next question is, do we use a Z-test or a t-test? Well first of all do we know the standard deviation of the population? Not really... we know that it is a binomial distribution with a probability to click on the download button of $p$ and a probability to not click of $(1 - p)$. This means the standard deviation of the download rate is
\[
\sigma_s = \sqrt{p(1-p)}.
\]And usually $p$ is estimated from the sample itself. So the t-test seems more appropriate, since we do not have much information on the total population.

Before we move on we should note that $\sigma_s$ for this test is not really given by the equation above. In our case, both the sample testing the new layout $A$ and the control sample have an error associated, and hence the combined error is given by
\[
\sigma_{\mu_A - \mu_0}\sqrt{\frac{1}{N_A} + \frac{1}{N_0}} = \sqrt{\frac{(N_A - 1)\sigma_{s,A}^2 + (N_0 - 1)\sigma_{s,0}^2}{N_A + N_0 - 2}}\sqrt{\frac{1}{N_A} + \frac{1}{N_0}} \approx \sqrt{\frac{\sigma^2_{s,A}}{N_A} + \frac{\sigma^2_{s,0}}{N_0}},
\]where the approximation on the right is justified for samples with $N>30$.

Using what we have established so far, we can formulate our t-test as
\[
t = \frac{(\mu_A - \mu_0)}{\sqrt{\frac{\sigma^2_{s,A}}{N_A} + \frac{\sigma^2_{s,0}}{N_0}}}.
\]Here we want to test a specific case, we want to know whether layout $A$ provides a $10\%$ improvement over the control sample. So we want to know when the statistics are good enough to rule out such an improvement.

We can re-write the t-test to answer that question
\[
t = \frac{(0.1\mu_0)}{\sqrt{2\sigma_s^2/N}},
\]where we assumed $N_A = N_0$ (because any other choice is sub-optimal) and $\sigma^2_{s,A} = \sigma^2_{s,0}=\sigma^2_{s}$ for simplicity. Now we solve this equation for the sample size
\[
N = \frac{2t^2\sigma_s^2}{(0.1\mu_0)^2}.
\]Before we can calculate $N$ we have to know $t$ corresponding to a $2\sigma$ ($95\%$) confidence level. To get this from the Student-$t$ distribution we need the number of degrees of freedom, which can be calculated as
\[
dof = \frac{\left(\frac{\sigma_{s,A}^2}{N_A}+ \frac{\sigma_{s,0}^2}{N_0}\right)^2}{ \left[ \frac{\left(\frac{\sigma_{s,A}^2}{N_A}\right)^2}{(N_A - 1)} \right] + \left[ \frac{\left(\frac{\sigma_{s,0}^2}{N_0}\right)^2}{(N_0 - 1)} \right] }.
\]If we assume $N_A = N_0$ and $\sigma_{s,A} = \sigma_{s,0}$, this simplifies to
\[
dof = 2(N - 1).
\]This means there is a problem here. To calculate $N$ we need to know $t$ and to calculate $t$ we need to know the degrees of freedom, which depend on $N$.

However, we can just assume that we are going to deal with a sample $N > 30$, which means the Normal distribution is a good approximation to the Student-$t$ distribution. For the normal distribution we do not need the degrees of freedom, hence
print("The 90\% confidence interval is = (%0.2f %0.2f)" % (norm.interval(0.9, loc=0, scale=1))
>> The 90% confidence interval is = (-1.64 1.64)

We calculated the $90\%$ confidence interval, instead of the $95\%$, since we are interested in a one tail distribution. We do not care about the probability that the new layout $A$ is worse than the control. We just want to know when do we have $95\%$ confidence that layout $A$ is not doing any better than the control. Since the distribution is symmetric, $5\%$ of the probability is above $1.64$ and $5\%$ is below $-1.64$. So we ignore the lower limit and set $t = 1.64$.

Putting this information in our equation for the Number of users we get
\[
N \geq \frac{5.3792 \sigma_s^2}{(0.1\mu_0)^2}.
\]We still need to estimate the standard deviation $\sigma_s$ somehow. One could use the download rate in the past, but one should be aware that this might have a time dependence... so think carefully where you get this estimate from. Let's assume we estimate the download rate to be $2\%$ so
\[
\sigma_s^2 = 0.02(1 - 0.02) = 0.0196.
\]With this we can calculate $N \geq 26359$.

Ok so let's run the test with this many users... imagine that after a day or so you get this table back:

sample
visitors
downloads
fraction
t
control
26359
500
0.0187
N/A
A
26359
560
0.0210
1.893

This looks great! Because of $t_A > 1.64$ we have ruled out the null hypothesis with $> 2\sigma$ and we should probably switch to the new layout $A$.

Even though there wasn't much programming included in this exercise, below I attached a small python script producing the plot above and the numbers used in this example (also available on Github).
cheers
Florian

'''
This program goes through the different steps of an A/B test analysis
'''
import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import t as student_t
from scipy.stats import norm


def main():

    mu = 0
    variance = 1
    sigma = np.sqrt(variance)
    x = np.linspace(-10, 10, 1000)
    linestyles = ['-', '--', ':', '-.']
    dofs = [1, 2, 4, 30]

    # plot the different student t distributions
    for dof, ls in zip(dofs, linestyles):
        dist = student_t(dof, mu)
        label = r'$\mathrm{t}(dof=%1.f, \mu=%1.f)$' % (dof, mu)
        plt.plot(x, dist.pdf(x), ls=ls, color="black", label=label)

    plt.plot(x,norm.pdf(x, mu, sigma), color="green", linewidth=3, label=r'$\mathrm{N}(\mu=%1.f,\sigma=%1.f)$' % (mu, sigma))
    
    plt.xlim(-5, 5)
    plt.xlabel('$x$')
    plt.ylabel(r'$p(x|k)$')
    plt.title("Student's $t$ Distribution approximates Normal")

    plt.legend()
    plt.show()

    print "The 90%% confidence interval is = (%0.2f %0.2f)" % (norm.interval(0.9, loc=0, scale=1))
    download_rate_estimate = 0.02
    sigma_s = download_rate_estimate*(1. - download_rate_estimate)
    N = 5.3792*sigma_s/(0.1*download_rate_estimate)**2
    print "estimate of N = %d" % round(N)

    # Calculate the t value given the measured download fractions 
    download_fractions = [0.0187, 0.0210]
    print "t_A = %0.2f (for a measured download rate of 2.1%%)" % t_test(N, download_fractions[1], N, download_fractions[0])

    return 


# function to calculate the t value
def t_test(N_A, p_A, N_0, p_0):
    variance_A = p_A*(1. - p_A)
    variance_0 = p_0*(1. - p_0)
    return (p_A - p_0)/np.sqrt(variance_A/N_A + variance_0/N_0)

if __name__ == '__main__':
  main()