# How do you find the KL Divergence between two multi-variable datasets?

## Background

I'm working on a tabular data model that performs a binary classification. The model has recently started underperforming and I'd like to know if that's due to a drift in the feature distribution of the model.

The features in the model haven't changed. The model hasn't been retrained. There hasn't been a change to the data collection. With this in mind, I assume changes are due to a change in the underlying feature distribution. I'd like to quantify this change over a series of datasets that I have.

The datasets are large, on the order of $$10,000-100,000$$ rows in size with $$250$$ columns.

I've heard about KL Divergence and think it could be a good measure of the difference between the feature distributions of the new and old datasets.

## Question

According to Wikipedia:

In mathematical statistics, the Kullback–Leibler divergence (also called relative entropy and I-divergence), denoted $$D_{\text{KL}}(P\parallel Q)$$, is a type of statistical distance: a measure of how one probability distribution P is different from a second...

I've read that KL Divergence is a good way to calculate the difference between multi-variable datasets, please see related questions for an example.

However, as KL Divergence explains the difference between probability distributions, I assume I'll have to transform my datasets into probability distributions of some form.

I haven't been able to find a standard way of doing this, but I have two ideas:

1. Compare feature by feature. Bin feature values and use the bin size to calculate the probability of each bin. Use the bins in both datasets to calculate KL Divergence.

2. Compare everything. Cluster all the samples in each dataset and get a probability for each cluster. Use those cluster probabilities to calculate KL Divergence.

Are these ideas sensible? Or is there a standard way of calculating KL Divergence that I haven't been able to find yet?

Related Questions:

• Where did you read that? $D_{KL}$ is not symmetric and it will be sensible to your choice of distribution. Why do you believe that computing it will allow your to calculate how different two datasets are? If you measure $D_{KL}=10$, how would you interpret that? Commented Mar 21, 2023 at 13:41
• "Are these ideas sensible?" They could be, but it can't be said definitely without knowing what the datasets mean and what the point is of the comparison. Commented Mar 21, 2023 at 16:26
• "I read it all over the place" then it shouldn't be too hard to give a quote from a source. "the first couple of sentences in wikipedia" the first sentences of which Wikipedia? Commented Mar 21, 2023 at 16:35
• "have changed the most" KL divergence looks purely to the probabilities. If it is relevant over which distances (in terms of the underlying feature variables) the changes occur, then this does not show in the KL divergence. The earth movers distance would be more appropriate. So, that's an example why the context is important in order to say anything about whether or not the ideas are sensible. Commented Mar 21, 2023 at 16:50
• @Connor The background of the problem. What are the datasets representing (Ideally also some visualisation of the data itself)? What is the reason for making the comparison? ---- The general answer to your question is that your described method is not neccesarily non-sensible. But, whether it is sensible or non-sensible for your particular case, that we can not judge. Commented Mar 21, 2023 at 21:06

Are these ideas sensible? Or is there a standard way of calculating KL Divergence that I haven't been able to find yet?

The standard way to compute the (symmetric) Kullback-Leibler divergence is to apply the formula

$$\sum_{x \in \mathcal{X}_P} P(x) \log\left( \frac{P(x)}{Q(x)} \right) + \sum_{x \in \mathcal{X}_Q} Q(x) \log\left( \frac{Q(x)}{P(x)} \right)$$

where $$P$$ and $$Q$$ are the probabilities of the events $$x$$ and the sum is taken over the space of all events $$\mathcal{X}$$ with non-zero probability.

Or an equivalent for densities

$$\int_{x \in \mathcal{X}_P} f(x) \log\left( \frac{f(x)}{g(x)} \right) \, dx + \int_{x \in \mathcal{X}_Q} g(x) \log\left( \frac{g(x)}{f(x)} \right) \, dx$$

The non-standard step is how you obtain the distributions for your data.

• 1. Binning. This is the simple way to do it. It is especially known to be used in creating histograms. All the typical complications/problems with histograms also apply here. If you have very low numbers in the bins then the method does not work well. And you may even get bins with zero probability such that the divergence becomes infinite. See the below example with two samples from a standard normal distribution

• 1a. kernel smoother an alternative to binning and histograms, is to fit a some kernel smoother to the data. With the vanilla smoothener density from R then the image above would become.

For this example 0.1081095 is the divergence.

1. Using class probabilities. This can work as well. One way to do this is to use a nearest neighbours algorithm that computes the ratio $$P(x)/Q(x)$$ and sum this over all points.

For the example this could go like the following in R code

### generate data
set.seed(1)
x = rnorm(100)
y = rnorm(100)
z = c(x,y)

### 15 compute nearest neighbours
M = outer(z,z, "-")    # matrix with distances
M = abs(M)
M2 = apply(M,1,order)  # get id's of closest neighbour

## compute probabilities
p2 = colSums(M2[1:15,]>100) #compute id 's of class y
odds1 = p2/(15-p2)          # compute odds

## divergence
sum(log(1/odds1[1:100]))/100+
sum(log(odds1[101:200]))/100


This gives a divergence of 0.2482063

I made a quick and dirty computation if the nearest neighbours, possibly there is some ready to use function with an algorithm that can be applied here. The basic principle is clear.

A problem here is that some probabilities $$P$$ and $$Q$$ might become zero and the divergence becomes infinite. The kernel smoother does not have this disadvantage and is similar to a nearest neighbours classification.

2. Fit a distribution. In some problems you could fit some parametric distribution.

• This answer is purely about the question in the title, how to compute the divergence. Whether or not it makes sense for your case to apply it is another issue. Commented Mar 22, 2023 at 9:42
• Thank you so much for all the work you put into this answer! It's very helpful. Commented Mar 22, 2023 at 11:24
• Where does the name "kernel smoother" come from? I know a kernel in machine learning can mean a weighting function, is the idea similar in this situation? Commented Mar 22, 2023 at 17:37
• @connor I gave a link in the comments en.m.wikipedia.org/wiki/Kernel_smoother . Why it is called kernel I am not sure. I have tried before to look into the etymology but I did not have much success as a lot of methods refer to 'kernel'. Commented Mar 22, 2023 at 17:44
• @Connor the kernel smoother in the example of this question computes in every point of the curve a sum of contributions from each data point (it is a sort of convolution, and that relates to this term 'kernel'). So you get a lot of computations when your curve is computed for a large space and when you have many points. But points far away should not contribute a lot and you might combine something like nearest neighbours with the distance to those neighbours to get a sort of estimate. (Maybe there exists something like 'wheighted nearest neighbours'?) Commented Mar 22, 2023 at 17:49

This sounds like an xy problem: you are asking the wrong question, the fundamental issue is identifying why the model is performing worse (problem X in wikipedia), instead you are asking about developing metrics to calculate difference between two multidimensional data sets(problem Y in wikipedia). As commenters have pointed out the difference in KL divergence is hard to interpret.

Having found out the actual question is identifying why the model is performing worse, then the direct issue with KL (apart from complexities in calculating it), is that there is no link to the dependent variable. eg if only one variable impacts the model performance, then KL divergence across all the variables will not be very discriminatory.

So what I am suggesting you do is analyse the distribution of your unthresholded model predictions - this links inputs more directly to model performance - eg what proportion of inputs were assigned an output of 30% -35% (from 0 - 100%). These are the "same" inputs in terms of your model. So look at how this distribution has changed over time . Since this is 1 dimensional it's easier to analyse and visualise.

This will give you an idea if the input data distribution has changed over time. (and you could even use KL divergence on it if you so wished, but I suspect it won't be useful vs just a regular histogram)

An alternative explanation is not that the independent data distribution has changed, but the input-output relationship has changed.

you can analyse this using a probability calibration curve. see eg why-model-calibration-matters-and-how.html. I am not advocating you add a calibration step to your model (as in that article) though, just create a plot showing the true probability for each binned output value (eg 30-35% etc). Compare the plot you get when the model was performing well, vs when the model was performing worse.[It doesn't really matter whether the original dataset was well calibrated, just if there is a difference to the new data set]

In the ideal case, either the predicted value distribution changes, but calibration curve stays same or vice versa - to allow you to identify which of these is the reason. Obviously, chances are that both have changed!

For some metrics you could even analyse the relative impact of each (if you can adjust your metric to takes as input probability and binned prediction output and actual probability for that bin).

• What's an "xy problem"? I've had a look at my model thresholds for similar performance across time. From them, it seems the necessary threshold to classify correctly shifts downwards. Does that indicate a data drift? What are calibration plots? Commented Mar 22, 2023 at 11:27
• @Connor the xy problem is when you are asking about a problem $x$ but are actually interested in problem $y$. Such questions may sometimes be confusing because the problem $x$ is not always well motivated and unclear (the question generates additional questions like 'why do you want to solve $x$?' or 'what is the point of $x$?). It can be better to ask about $y$ more directly or at least clarify that problem $x$ has problem $y$ as underlying problem. Commented Mar 22, 2023 at 18:18
• @Connor yes, that is very common: if you don't know the answer to your question, then it might be difficult to ask the question in a correct way. In cases that this becomes a difficulty, explaining the underlying problem in simple English, can often help others to understand what the problem is about. Commented Mar 22, 2023 at 20:11
• @Connor "From them, it seems the necessary threshold to classify correctly shifts downwards.Does that indicate a data drift?" - I don't think so. This is precisely why I am suggesting looking separately at prediction variable and calibration plot. If you need to change the threshold it may be because of data drift or because of model drift. Commented Mar 23, 2023 at 9:12
• An alternative explanation is not that the independent data distribution has changed (data drift), but the input-output relationship has changed (model or concept drift). here is another link showing calibration plots wttech.blog/blog/2021/a-guide-to-model-calibration Commented Mar 23, 2023 at 10:32