Fuzzy joining on mixed typed columns is with unequal weights

[jovan-stojanovic]

Fuzzy joining on mixed typed columns is with unequal weights

[Vincent-Maladiere]

Hi @jovan-stojanovic, @GaelVaroquaux, @ogrisel, after further diving into this issue, we might not need to use the Frobenius norm or pairwise distance at all!

The concern of having equal representativity for each column's type (str, num) stems from the downstream kNN tasks with Euclidean distance. For example, let's say we run a fuzzy join on one string column and one numerical column. Below is the Euclidean distance between two mixed embeddings of index $i$ and $j$:

$$d_{ij} = \sqrt{\sum_{k\in \mathcal{S}{ij}} (x{ik} - x_{jk})^2 + (x_{ik_{num}} - x_{jk_{num}})^2}$$

Where $S_{ij}$ is the set of string embedding columns where $x_i$ and $x_j$ are not both zero and $k_{num}$ is the column with numerical values.

Ideally, to equally take into account both numerical and string columns, we would like to ensure:

$$\frac{1}{N}\sum_{i=1}^N\sum_{k\in \mathcal{S}{ij}} (x{ik} - x_{jk})^2 \approx \frac{1}{N}\sum^N_{i=1}(x_{ik_{num}} - x_{jk_{num}})^2 $$

We now compute the Frobenius norm for the string and numerical column blocks.

Square Frobenius norm for the string column:

We use HashingVectorizer followed by TfIdfTransformer. By default, TfIdfTransformer uses the l2 norm. Note that HashingVectorizer creates a sparse matrix with $2^{20} \approx 10^6$ columns.

$$
||\tilde{X}{\mathrm{str}}||F^2=\sum{i=1}^N \sum{k=1}^K \tilde{x}{ik} ^ 2 = \sum{i=1}^N \sum_{k=1}^K \frac{x_{ik} ^ 2}{||x_i||^2_2} = \sum_{i=1}^N \frac{1}{||x_i||^2_2} \sum_{k=1}^K x_{ik} ^ 2 = N
$$

Square Frobenius norm for the numerical column:

We use StandardScaler on our single numerical column.

$$||\tilde{X}_{\mathrm{num}}||F^2=\sum{i=1}^N \tilde{x}_i ^ 2 = N \mathbb{E}[\tilde{X}^2] = N (\mathbb{V}(\tilde{X}) + \mathbb{E}^2[\tilde{X}]) = N (1 + 0) = N
$$

Therefore, we have established:

$$||\tilde{X}_{{str, num}}||_F = \sqrt{N}$$

---

The initial proposal was to divide each element by the Frobenius norm / N of its feature block, by doing so, we would divide each element —string or numerical alike— by:
$$\frac{||\tilde{X}_{{str, num}}||_F}{N} = \frac{\sqrt{N}}{N}=\frac{1}{\sqrt{N}}$$

i.e. multiply each element by $\sqrt{N}$, which is unstable.

Experiment

from dirty_cat import datasets
from sklearn.model_selection import train_test_split
from dirty_cat._fuzzy_join import _numeric_encoding, _string_encoding

salaries = datasets.fetch_employee_salaries()
X, y = salaries.X, salaries.y

X_train, X_test, y_train, y_test = train_test_split(X, y)

# numerical encoding
num_cols = ["year_first_hired"]
main_num_encoding, aux_num_encoding = _numeric_encoding(
    X_train,
    num_cols,
    X_test,
    num_cols,
)

print((main_num_encoding ** 2).mean())
>> 0.9876
print((aux_num_encoding ** 2).mean())
>> 1.0372

# string encoding
str_cols = ["employee_position_title"]
main_str_encoding, aux_str_encoding = _string_encoding(
    X_train,
    str_cols,
    X_test,
    str_cols,
    encoder=None,
    analyzer="char_wb",
    ngram_range=(2, 4),
)

print(
    main_str_encoding[:5].toarray() ** 2).sum(axis=1)
)
>>> [1., 1., 1., 1., 1.]
print(
    main_aux_encoding[:5].toarray() ** 2).sum(axis=1)
)
>>> [1., 1., 1., 1., 1.]

Conclusion

Due to the l2 scaling of TfIdfTransformer for string columns and the StandardScaler for numerical columns, dividing by the Frobenius norm is unnecessary :)