Common terms, definitions, theorems in statistics and machine learning

ASHIVNI SHEKHAWAT Research scientist at Lyft Inc.

Hypothesis Testing

Term	Definition
H0	Null hypothesis, the default position that there is no change
H1	Alternative hypothesis, the alternative position that there is some change
Type I error	Rejection of H0, when H0 is true
Type II error	Failure to reject H0, when H1 is true
Error	False rejection of H0
α, Significance level, false positive rate	Pr(reject H0 | H0 is true); probability of type I error
β, false negative rate	1 – Pr(reject H0 | H1 is true); probability of type II error
Power	Pr(reject H0 | H1 is true); 1 – probability of type II error; 1 – β
P-value	Probability of observing a result at least as extreme as the observed result, given that H0 and all other model assumptions are true
Confidence Interval	The set of effect sizes whose test produced P > 0.05 define a 1 – 0.05 = 0.95 or 95 % confidence interval.
PCE	Per comparison error rate
PFE	Error rate per family (expected number of false rejections per family)
FWE	Family wise error rate (probability of at least one error in the family)
FDR	False discovery rate (expected number of false significances / number of significances)

Classification

Term	Definition
True positive rate; TPR; Recall; Sensitivity	True positives / All positives, i.e. the fraction of positives that are correctly classified by the model
False positive rate; FPR; Type I error rate	False positives / All negatives, i.e. the fraction of all negatives that are incorrectly classified by the model
False negative rate; FNR; Type II error rate; Miss rate	False negatives / All positives, i.e. the fraction of all positives that are incorrectly classified by the model
True negative rate; Selectivity; Specificity	True negatives / All negatives, i.e. the fraction of all negatives that are correctly classified by the model
Accuracy	True positives + True negatives / Total population, i.e. the fraction of population that is correctly classified by the model
Precision; PPV; Positive predictive value	True positives / Predicted positives, i.e. the fraction of true positives amongst all predicted positives
FDR; False discovery rate	False positives / Predicted positives, i.e the fraction of false positives amongst all predicted positives
Population prevalence	Positives / Population, i.e. the fraction of population that is positive
F1 score	2 * Precision * Recall / (Precision + Recall), i.e. the harmonic mean of precision and recall

Reinforcement Learning

Multi-armed Bandits

Term	Definition
	Action taken by the agent at time step t
	Estimate of the expected reward from action a at time step t
	The number of times the action ‘a’ has been played till time step t
	Reward obtained on the i_th play of action ‘a’
UCB	Upper-Confidence-Bound algorithm for action selection in bandits

Markov Decision Processes

Term	Definition
MDP	Markov Decision Process
	State, reward, and action at time step t
	Set of all valid states, rewards, and actions (in state ‘s’)
Finite MDP	A MDP in which the set of all states, rewards and actions is finite
Trajectory	The sequence of state, action, and rewards starting at some given state,
State dynamics	Also known as the dynamics of a MPD, given by the four argument function . This function gives the probability of reaching a state s’ and receiving a reward r by taking an action a in state s.

Limit Theorems

Weak law of large numbers

The sample average converges in probability to its expected value.

Strong law of large numbers

The sample average converges almost surely to its expected value.

Central limit theorem

The average of a large number of IID random variables, when shifted by the population average and scaled by the square root of the number of variables, approaches a normal distribution. More precisely, let {x₁, x₂, …, x_n} be n IID random variables such that E(x_i) = μ, Var(x_i) = σ². Let S_n = (x₁ + x₂ + … + x_n)/n, then √n(S_n – μ) → N(0, σ²)

Extreme value theorem

The maximum (minimum) of a large number of IID random variables, when centered and scaled properly, converges to a generalized extreme value distribution. The Weibull, Gumbel, and Frechet distributions are members of this family. The centering and scaling here are not as universal as the central limit theorem.

Bootstrap theorem (for sample mean)

Let {x₁, x₂, …, x_n} be an i.i.d with sample mean X̅, sample variance S, and a defined population variance. Let X̅_B denote the mean of a bootstrap sample drawn from {x₁, x₂, …, x_n}. Then, √n(X̅_B – X̅)/S approaches the standard normal distribution in the limit of large n.