# How can machine learning be applied to generate a similarity measure for fuzzy matching?

Consider the problem of performing a fuzzy join between two datasets $J$ and $K$. The standard approach requires a similarity measure $S: D \times D \rightarrow \mathbb{R}$. A full join of $J$ and $K$ is performed and the similarity measure is evaluated on each of the resulting records, and only records that score above a certain threshold are kept. Usually the similarity measure is just a string similarity metric like the Levenshtein distance.

The records I'm working with, though, have several features of various types (strings, categorical variables, even geographic locations), and while those features may have . I also have some labeled data to train on, so I've approached this as a classification problem. For each record in the cross join, I construct features and then train a classifier on those features with the response variable being whether to record was kept or rejected. This has given decent but not great results.

With that set up, here are my questions:

• Is the classification framing a good way to approach this?
• Are there any papers/resources about using machine learning to construct a similarity metric?
• Are there alternative approaches to this problem that I should consider?

## 1 Answer

The literature on learning similarity or distance functions is usually referred to as similarity learning or metric learning. The wikipedia article is: https://en.wikipedia.org/wiki/Similarity_learning. Although the article shows a bilinear formulation, you can also use more complex forms such as a multi-layer neural network. You can use a loss function like margin loss, which forces the similarity of a correct pair to be higher than an incorrect pair by a given margin. See https://en.wikipedia.org/wiki/Hinge_loss (Weston and Watkins ...) for the case where the margin is 1.

However, IMO, your problem is not about finding the right literature. It's about understanding the relationship between your input and desired output. If I understand correctly, the desired distance function is Levenshtein distance. It's hard to see how a simple formulation (e.g., bilinear or MLP) could learn a function that computes Levenshtein distance from the input strings.

The simplest solution is to just provide Levenshtein distance as a feature to your classifier. You could use something more complex that can may learn Levenshtein distance, like https://arxiv.org/abs/1803.00057, but that's probably an overkill.

• Similarity learning is exactly what I was looking for. To clarify, I wasn't proposing feeding the raw strings into the similarity function. Instead, I intend to compute something like the Levenshtein distance, and then use that metric along with all of the other features I construct into the function. – Max Rosett Mar 6 '18 at 17:59