I have a list of short strings each identifying a city. Misspellings are very common. The example below shows some of these short strings, along with the correct city they're supposed to match.

string city
amsterdam amsterdam
asmterddam amsterdam
amstterdm amsterdam
new york new york
new yrok new york
nwe york new york
neew york new york
nw york new york

I would like to train a classifier that takes the input string and then predict the most likely city to be identified. However there is a subtlety which is that the correct city will depend not only on the input string, but also on other factors such as the current location of the person, and of which person is writing.

For instance, the following strings could mean different cities based on these other features:

current_location person string city
uk John dratford dartford
uk Jack dartfford dartford
uk Jill datrfrod dartford
norway Jill dartfoord dartford
norway John datrfrod dartfjord
norway James datrfrod dartfjord
sweden Olaf dratfjod dartfjord
uk Olaf dratfoord dartfjord

As we can see, the same input string can mean a different actual city depending on who writes it, and where the writer is currently located. This means that just a fuzzy search using tf-idf wouldn't be enough to make correct predictions.

I'm thinking of two different approaches to implement an appropriate classifier:

  • boosted trees using character n-grams as features + the other categorical features
  • neural network using convolutions on letters + the other categorical features

One advantage here is that the string will always be limited in size (max about 50/60 characters).

One thing I'm struggling with in particular, for the case of boosted trees, is that, how to make the model learn about the order of character n-grams? For instance, the sequence mst coming after the sequence ams is indicative of amsterdam, but I don't know how to give the model a sense of sequence, where this sequence could be anywhere in the string? (e.g. if the input string is aamsterdam then this sequence would be in position 2, instead of position 1).

So in short, I'd be looking for guidance in the best way to decompose and model the input string, in order to transform it into features usable by either boosted trees or a (convolutional?) neural network, along the other categorical input features.

I'm obviously not looking for a complete solution here, just general guidance would be hugely appreciated.

  • 1
    $\begingroup$ There are at least two possible approaches. One practical. For example, you engineer your candidates according to some rule (edit distance at most k) from a fixed list of cities and engineer some rule based on population/distance of a city and possibly fit some simple classifier. Another one, more interesting, theoretical. You research work on methods for autocomplete. $\endgroup$
    – Valentas
    Commented Oct 7, 2021 at 7:57

1 Answer 1


There are typically many discrete stages in a natural language processing (NLP) pipeline. Two possible stages are normalization and classification. Strings are normalized before being classified. Normalization (aka, standardization) makes string data more consistent. Mapping spelling variates to the same representation is an example. Mapping spelling variations to a consistent representation does not require machine learning. It can be with something like edit distance look-up in a dictionary.

After normalization, classification is more straightforward. Classification models depend on the quality and quantity of features, aka feature engineering. Predicting a city most likely won't happen at the character-level. Modeling at the token-level would probably be more useful.


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.