Let's say you are asked to solve a binary classification problem ($y=0,1$) with very few training examples ($N<1000$) and quite a few, possibly predictive features ($d>1000$). The standard question of "how the heck do I feature select?" becomes very relevant, and in particular, "how the heck do I feature select with so few training examples?!?".
For Categorical features, one of the best ways to test for significance -- i.e. a non-null relationship between a feature column and a label column -- is Fisher's exact test and Laplace-smoothed lift.
Fisher's exact test is a combinatoric way of examining a contingency (or pivot) table. Let's say we have two columns $x$ and $y$, which both take on, in the simplest case, only two values: true and false. If we were to make pivot table, we'd have the number of pair-wise events in a 2x2 grid.
\begin{eqnarray}
\mathrm{pivot}(x,y) &=& \left( \begin{array}{cc} n_{00} & n_{01} \\
n_{10} & n_{11}
\end{array}\right)
\end{eqnarray}
Where $n_{11}$ corresponds to the number of times $x$ and $y$ were both True, $n_{00}$ corresponds to the number of times $x$ and $y$ were both false, $n_{10}$ the number times $x$ was true and $y$ false, etc. (This can be done easily in pandas by writing something like \textit{pandas.pivot(dataFrame,index=x,columns=y,aggFunc=len,fillna=0}).)
We can see that the sum of the entries $n_{11}+n_{01}+n_{10}+n_{00}=N$ equals the number of training examples, and that the sum over rows or columns equals the marginal counts. $n_{11}+n_{10}=R_1$ equals the number times $x$ was true; $n_{01}+n_{11}=C_1$ equals the number times $y$ was true; $n_{01}+n_{00}=R_0$ equals the number times $x$ was false, etc.
What fisher proposed is to take this matrix and ask, given the marginal counts, $R_0,R_1,C_0,C_1$ -- which, if you think about it, correspond to the prior probabilities on $x$ and $y$: $P(x)=\frac{R_1}{N},P(y)=\frac{C_1}{N}$ -- how likely is the resulting contingency matrix if $x$ and $y$ are independent?
The most naive way to answer that question is to take the prior probabilities on $x$ and $y$ that's given two us by the data:
\begin{eqnarray}
P(x)=p &=& \frac{R_1}{N} \\
P(y)=q &=& \frac{C_1}{N}
\end{eqnarray}
and quote our good old multinomial:
\begin{eqnarray}
P(\mathbf{n}) &=& \frac{N!}{n_{00}!\ n_{10}!\ n_{11}!\ n_{01}!} \left[pq\right]^{n_{11}}\left[p(1-q)\right]^{n_{10}}\left[(1-p)q\right]^{n_{01}}\left[(1-p)(1-q)\right]^{n_{00}}
\end{eqnarray}
which, can be simplified to:
\begin{eqnarray}
P(\mathbf{n}) &=& \frac{N!}{n_{00}!\ n_{10}!\ n_{11}!\ n_{01}!} (p)^{n_{10}+n_{11}}(1-p)^{n_{00}+n_{01}}(q)^{n_{11}+n_{01}}(1-q)^{n_{10}+n_{00}}\\
P(\mathbf{n}) &=& \frac{N!}{n_{00}!\ n_{10}!\ n_{11}!\ n_{01}!} (p)^{R_1}(1-p)^{R_0}(q)^{C_1}(1-q)^{C_0}
\end{eqnarray}
The probability distribution above assumes that there is no relationship between $x$ and $y$, and so, if we see a contingency table that is very unlikely given the above pdf, we know something is up! But, how sure are we that the prior distribution estimates, $p,q$ are correct? Our sample size $N$ was very small. That's a troubling question, which can be solved by Laplace Smoothing, which sets a uniform prior distribution on $P(x)$ and $P(y)$:
\begin{eqnarray}
P(x)=p &=& \frac{R_1+\alpha}{N+\alpha d_x}
\end{eqnarray}
where $d_x$ is the number of distinct values $x$ can take on -- in this case two. And similarly, for $y$ we'd have the prior:
\begin{eqnarray}
P(y)=q &=& \frac{C_1+\alpha}{N+\alpha d_y}
\end{eqnarray}
This helps things a little bit, where $\alpha$ is the hyper parameter between 0 and 1 that controls the ``strength'' of our uniform prior. But one also might worry if using a multinomial is even appropriate, given, for very few datapoints $N$, the highly discrete nature of our contingency table.
Fisher's exact test explicitly addresses this discreteness aspect through combinatorics.
Let's recall an experiment where one has a drunken man throw $N$ darts at a dartboard with $d$ cells. The number of different ways in which this drunken dart player can get $n_1$ darts in the first cell $n_2$ in the second, $n_3$ in the third, etc. is:
\begin{eqnarray}
W &=& \frac{N!}{n_1!n_2!\cdots n_d!}
\end{eqnarray}
Taking the log of this combinatoric factor and applying stirling's approximation, we get the Shannon entropy:
\begin{eqnarray}
\log W &=& -\sum_{i=1}^d p_i \log p_i \\
p_i &=& \frac{n_i}{N}
\end{eqnarray}
This is all very interesting because, if one looks at the contingency table above, we need only promote our counts $n_{00},n_{01},n_{10},n_{11}$ to a compound index: $n_{1},n_2,n_3,n_4$ and we get the same formula:
\begin{eqnarray}
W &=& \frac{N!}{n_{00}!n_{01}!n_{10}!n_{11}!}
\end{eqnarray}
This is the number of ways one can get a contingency table with the counts $n_{ij}$. But, this is NOT a probability. It is simply a multiplicity count of some "state" in phase space, $n_{ij}$. (You'll see above that it's a normalization factor for the multinomial). If we want to convert this multiplicity count to a probability, we have to be like Kolgomorov and divide by the multiplicity of the entire sample space $\Omega$. After all,
\begin{eqnarray}
P(x \in X) &=& \frac{\vert X \vert}{\vert \Omega \vert}
\end{eqnarray}
Where I'm using bars for ``multiplicity'', or the count of phase space cells within some region.
For our contingency table, above, we can define precisely what the sample space $\Omega$ is: all contingency tables with the marginal sums $R_0,R_1$ and $C_0,C_1$. This can be written as compound combinatoric factor:
\begin{eqnarray}
\vert \Omega \vert &=& \left(\begin{array}{c}
N \\ C_0
\end{array}\right)
\left(\begin{array}{c}
N \\ R_0
\end{array}\right)\\
&=& \frac{N! N!}{R_0!R_1!C_0!C_1!}
\end{eqnarray}
And so we have, doing our division:
\begin{eqnarray}
P(n_{00},n_{01},n_{10},n_{11} \vert R_1,R_0,C_1,C_0 ) &=& \frac{R_0!R_1!C_0!C_1!}{N! n_{00}!n_{01}!n_{10}!n_{11}!}
\end{eqnarray}
Let the joint event $n_{00},n_{01},n_{10},n_{11}$ be specified by $\mathbf{n}$. Then we can write
\begin{eqnarray}
P(\mathbf{n} \vert \mathbf{R},\mathbf{C} ) &=& \frac{R_0!R_1!C_0!C_1!}{N! n_{00}!n_{01}!n_{10}!n_{11}!}
\end{eqnarray}
or, more generally, for non-binary categorical variables (check it!):
\begin{eqnarray}
P(\mathbf{n} \vert \mathbf{R},\mathbf{C} ) &=& \frac{\prod_{i=1}^{d_x}R_i! \prod_{j=1}^{d_y} C_j!}{N! \prod_{i,j} n_{ij}!}
\end{eqnarray}
This is a very interesting formula, because it gives the precise, discrete probability of seeing some contingency table, conforming to marginal counts $\mathbf{R}$ and $\mathbf{C}$. With a little bit of algebra, one will see that this combinatoric probability converges to the multinomial we quoted above, by noting:
\begin{eqnarray}
\lim_{N \to \infty} N! &\approx & \left(\frac{N}{e}\right)^N
\end{eqnarray}
and so we get:
\begin{eqnarray}
P(n_{00},n_{01},n_{10},n_{11} \vert R_1,R_0,C_1,C_0 ) &\approx & \frac{(\frac{R_0}{e})^{R_0}(\frac{R_1}{e})^{R_1}(\frac{C_0}{e})^{C_0}(\frac{C_1}{e})^{C_1}}{(N/e)^N (\frac{n_{00}}{e})^{n_{00}}(\frac{n_{01}}{e})^{n_{01}}(\frac{n_{10}}{e})^{n_{10}}(\frac{n_{11}}{e})^{n_{11}}}
\end{eqnarray}
All the factors of $e$ cancel out, and we can simplify to get:
\begin{eqnarray}
pq &=& \frac{n_{11}}{N}\\
p(1-q) &=& \frac{n_{10}}{N}\\
(1-p)q &=& \frac{n_{01}}{N}\\
(1-p)(1-q) &=& \frac{n_{00}}{N} \\
P(\mathbf{n} \vert \mathbf{R},\mathbf{C} ) &=& \frac{N!}{\prod_{i,j} n_{ij}! }(\frac{R_0}{N})^{R_0}(\frac{R_1}{N})^{R_1}(\frac{C_0}{N})^{C_0}(\frac{C_0}{N})^{C_0} \\
&=& \frac{N!}{n_{00}!\ n_{10}!\ n_{11}!\ n_{01}!} (p)^{n_{10}+n_{11}}(1-p)^{n_{00}+n_{01}}(q)^{n_{11}+n_{01}}(1-q)^{n_{10}+n_{00}}
\end{eqnarray}
The same multinomial formula we found above!
This really isn't so surprising, as it says the combinatoric probability converges to the multinomial with fully continuous priors $p,q$ in the large sample $N \to \infty$ limit, but it is interesting to note.
Now, Fisher, when quoting p-values, or significance tests for a relationship between $x,y$, would simply use the count of contingency tables that had table counts $\mathbf{n}$ more extreme than what's observed. For instance, let's say we observe a True/True $x,y$ occurence that is higher than expected under the marginals: $n_{11}>N p q$ or $n_{11} > R_1 C_1 / N $: what's the sum of the probabilities of tables that have an even \textit{higher} $n_{11}$? This is called a one-tailed pvalue significance test, and for the fisher exact test and the multinomial method, corresponds to a simple sum.
I won't get too into the details of implementation now, but suffice to say, scipy's got a fisher test calculation all on its own!
------------------------------------------------------------------------------------------------------------------------
Now what hasn't been mentioned is lift. And it relates directly to the laplace smoothed priors discussed earlier. Lift is simply:
\begin{eqnarray}
l(x\vert y) &=& \frac{P(x \vert y)}{P(x)} = \frac{P(x,y)}{P(x)P(y)}
\end{eqnarray}
or, the probability of $x$ taking on some value given $y$ relative to $x$ occurring independently. Lift is a number between zero and infinity, and basically means: how many more times likely is $x$ going to occur given $y$? For low sample size $N < 1000$, it's probably a good idea to smooth the priors $P(x),P(y)$ giving us:
\begin{eqnarray}
l(x\vert y) &=& \frac{P(x,y)}{P(x)P(y)} \\
&=& \frac{(N+\alpha d_x)(N+\alpha d_y)}{N}\frac{n_{xy}}{n_x n_y }
\end{eqnarray}
Where $n_x,n_y$ is the event count of $x$ and $y$. $n_{xy}$ is th joint event count of $x,y$.
------------------------------------------------------------------------------------------------------------------------
For those who are heavily implementation-focused, you'll note that this fisher test can be done for any type of contingency table -- it doesn't have to be two binomial marginal distributions, they could easily be multinomials! -- but often the best way to do things is to OneHotEncode the scikit-learn first, and then do simple fisher exact tests on each of the pairwise 2x2 contingency tables for feature selection. I hope that helps!
