Why perfectly dependent variables have so low pair level ?

[folmos-at-orange]

Description

I found that when I run an unsupervised analysis with pairs enabled, pairs that are perfectly correlated have a rather low level.

To reproduce:

import numpy as np
import pandas as pd
from khiops import core as kh

# Generate data
# - When y == 0: X ~ Unif(0,1)
# - When y == 1: X ~ Unif(2,3)
np.random.seed(123)
n = 10000
x = np.concatenate([np.random.uniform(0, 1, n), np.random.uniform(2, 3, n)])
y = np.concatenate([np.zeros(n), np.ones(n)])
pd.DataFrame({"x": x, "y": y}).to_csv("data.csv", index=False)

# Unsupervised analysis with fast path
kh.train_predictor("", "", "data.csv", "", "report.khj", max_pairs=2)

# Print level
report = kh.read_analysis_results_file("report.khj")
print(report.bivariate_preparation_report.variables_pairs_statistics[0].level)
# 0.0402902

I have also noted that for larger values of n the level keeps going down. This is rather unintuitive.

[marcboulle]

When analyzing a pair of variables (X, Y), Khiops exploits a co-clustering model M by partitioning each variable into intervals or groups of values according to their type, numerical or categorical.
Observations are then assigned to the co-clustering cells to capture the dependency structure across the variables. Finally, the variables are described using this dependency structure.

The resulting model cost, Cost(M), corresponds to the coding length of the co-clustering structure plus the coding length of both variables given the model:

Cost(M) = CL(M) + CL(X|M) + CL(Y|M)

The null model M₀ corresponds to the case of two independent variables, where the co-clustering reduces to a single co-cluster.
The null cost Cost(M₀) is essentially the coding length of each variable encoded independently.

The level of the pair can be interpreted as a compression rate:

Level(M) = 1 - Cost(M) / Cost(M₀)

This compression rate ranges between 0 and 1, is zero when the two variables are independent, and increases with the model's ability to capture the dependency structure.

In an ideal case, with two identical variables, the co-clustering structure would perfectly encode the dependency, allowing one variable to be fully deduced from the other.
Asymptotically, even assuming (falsely) that the cost of the co-clustering structure is null, this implies Cost(M) ≈ ½ Cost(M₀), and thus Level ≈ 0.5.

However, encoding all values precisely is costly, and the compression rate is limited by the structure's ability to capture dependencies at a fine granularity.

For example, in an experiment with two numerical variables and N=10,000, the dependency structure is captured with a co-clustering of K×K cells, with K=60.
This results in an average of less than 3 instances per cell.
In this case, all instances are on the 60 diagonal cells, but the remaining coding length involves encoding the rank of approximately N/K instances within each interval of the marginal distributions of both variables.
Empirical results show that the level is approximately 0.2 in this scenario.

When one of the variables is Boolean, the co-clustering will consist of at most two parts per variable, which is too coarse to encode the values at a fine granularity.
This explains why the level is around 0.04 in this case, far below the value when both variables can be split finely.

[folmos-at-orange]

Thanks, I understand now why this happens.

However, I thinks this render the Level more difficult to use as proxy for "good correlation" in this case, because 0.2 is a rather low level in the supervised case. The 0.2 value may also seem arbitrary to the user (a magic number) and it is nowhere documented.

Maybe this can be supplemented with other KPI's ? It comes to mind the ratio $I(X,Y)/H(X,Y)$, where we evaluate the mutual information / entropy over the distribution induced by the model's grid. This value would be 1 in the example above.

[marcboulle]

You are right, the Level of variable pairs is difficult to interpret:

• it is 0 in case of independent variables, or insufficient data w.r.t. the dependence pattern
• it is bounded by 0.5 for identical variables, meaning that coding both variables reduces to coding one variable
• it can reach almost 0.5 only in case of identical categorical variables with a reasonably small number of values
• with categorical variables having a large number of values, this requires datasets with very large size
• with numerical variables, the level can never reach 0.5, as it would require each variable to be discretized in as many intervals as instances, which is not possible. In practice, a level of around 0.2 can be reached for two identical numerical variables

But the suggested criterion based on mutual information (actually asymptotically similar to the level) cannot solve the problem.

Perfectly dependent variables means that knowing the value of one variable, the value of the other can be perfectly derived. This will never be the case with two numerical variables.

Note

This problem is complex in the general case, and not tackled by any alternative method.
The MODL bivariate approach is the only one that can evaluate the dependence between two variables, whatever their number of values, their type (numerical or categorical), and the complexity of the dependence pattern, as the method is non-parametric.
For example, the Pearson correlation coefficient (cf. https://en.wikipedia.org/wiki/Pearson_correlation_coefficient) is a parametric method, and many bivariate numerical datasets with strong dependence patterns have a correlation of 0.

Note

The entropy of a numerical variable, known as differential entropy (cf. https://en.wikipedia.org/wiki/Entropy_(information_theory)#Entropy_for_continuous_random_variables), raises numerous problems. It corresponds to the transformation of a sum into an integral, in the limit where the bin size goes to zero. It can even be negative, and is therefore not exploitable in this context.

More Details

Actually, the data part of the MDL criterion $Cost(\text{Model}) + Cost(\text{Data} \mid \text{Model})$ in MODL approaches can asymptotically be expressed in terms of entropy or mutual information, as you suggest.

For pairs of categorical variables with few values, the asymptotic regime is rapidly attained, and the level increases towards 0.5 for identical variables, meaning that coding one variable is the same as coding both, once the dependence model is described and its coding length becomes negligible.
This can be easily verified using Khiops with identical categorical variables having few values.

For categorical variables involving many values, the asymptotic regime is not attained as quickly, resulting in a level significantly below 0.5. This is related to the uncertainty of the model, which needs to group values to increase frequencies, at the expense of a decayed fit of the data.

For numerical variables, the problem is still more complex, as the asymptotic regime is never reached. With more data, more intervals are built, and more data is used to populate the contingency table between the parts of the two variables. One never reaches a point with a finite-sized variable partition (as with categorical variables), and can therefore never reach the asymptotic regime where the equality of two variables is exhaustively captured in the diagonal of the contingency table.

[folmos-at-orange]

Ok, got it. I still think the KPI remains difficult to interpret for pairs:

• As a compression rate, it is never reaches 1, even if the variables are copies
• Now I realize that, for example, Num-Num pairs aren't comparable to Cat-Cat pairs in terms of level

Maybe a KPI LevelNorm normalizing by the bounds aforementioned, or even redefining it as Level = Bound - Cost(M)/Cost(M_0), with the proper bound for each case (if they are computable of course). Also, I still think that the ratio of the mutual information/entropy for the encoded variables (the data part) could be a useful supplementary KPI.

[marcboulle]

Thank you for the suggestion. Still, designing a theoretically sound, well-behaved, and useful KPI remains a complex and open challenge.