0
$\begingroup$

I am new to machine learning. But have basic understanding of the concepts.

Problem statement : We humans won't perceive much difference between "Tim Cook" and "Tim C0ok". ( 0 is been replaced with zero ). I am trying to model this.

Task is to come-up with a model which can predict if two names are visually similar. The system will be configured with a predefined set of names. When the system is online, it should predict whether a given name is similar to one of the configured name or is not similar to any of the configured name.

My current approach: I'm trying to come up with a two-stage model. First stage is a binary classier which predicts name is know to system or not. Second stage is a multi-class classifier, which tells to which configured name given name is similar.

Features : Using string distance measures Levenshtein Distance, Damerau-Levenshtein Distance, Jaro Distance, Jaro-Winkler Distance and Hamming Distance as the feature vector. Feature vector is computed between a reference string ( Ex : 'aaaaaaaaa' ) and the name.

$\endgroup$
2
  • $\begingroup$ What kinds of similarity do you want to take into account? Only the visual similarity of two characters? $\endgroup$
    – D.W.
    Commented Jun 29, 2016 at 15:25
  • $\begingroup$ Yes, addressing visual similarly $\endgroup$ Commented Jun 29, 2016 at 15:39

1 Answer 1

2
$\begingroup$

There are existing dictionaries that list pairs of characters that are visually similar. See, e.g.,

Therefore, I suggest you try modified edit distance: compute the edit distance, but with a cost function that treats the distance between a pair of visually similar characters as zero or much smaller than the distance between a pair of different characters.

I recommend using the Damerau–Levenshtein edit distance. It includes transpositions among the changes it considers. There's some reason to believe this corresponds better to mistakes made by humans. So, maybe it'll correspond better to what humans consider similar.


Another plausible approach would be to render the two strings to images (using whatever font you think will be used to display them), then compare the images.

To compare how visually similar the images are, a basic starting point would be to use L1 or L2 distance (both have been shown to correspond well to human perception in some situations). This probably won't be enough because it will fail badly if the images aren't perfectly aligned. To address that, I suggest you apply a sort of edit distance that allows inserting or deleting entire columns of pixels (a full-height column), in addition to changing individual pixels.


It's not clear whether machine learning will be useful here. The obvious approach to try first would be to compute the edit distance and compare it to some threshold. That might be sufficient.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.