Categorization with NLP

Since launching my categorization tool Shoppy I've had some fun analyzing collected data which resulted in considerable complication of the prediction model. And now I feel the urge to write a deeper dive into its inner workings. I'm not sure how useful it would be for anyone who isn't a part of the Grocery Categorization industry, but hopefully some NLP tricks could be at least interesting to any general practitioner.

Please note that I'm by no means an NLP expert! Part of the reason for writing this kind of posts is to try and nerd-snipe someone who knows more into sharing their expertise.

Oh, and it's not a short one, this! Settle down :-)

Problem description

Just to remind everyone, what I'm trying to solve for my slowly developing shopping list app is suggesting grocery categories for products. So that it knows that "Milk" is dairy, "Apples" is produce and so on. This categorization helps with grouping and sorting, and it also looks nicer with colors and appropriate icons.

The usual approach to solving such problems is Machine Learning, and specifically — classification . That doesn't work for me though, as I couldn't come up with any means of collecting enough data myself, and hiring a consultancy is way above the budget of a tiny personal project.

So instead I'm manually crafting a clever algorithm with explicitly handled edge cases.

Lexing input

The first step is turning free-form input into something more formal and predictable: a set of lexemes. Step by step, it looks like this:

This gives me a normalized, stable input key independent of basic morphological variants:

A note on stemming. I'm using the original Porter algorithm . It's widely supported, but is also the most simplistic. I don't really care about the correctness of the result from the point of view of the English language. As long as the algorithm used to produce the data is the same as the one used for checking against it, I'm good.

Terms database

The straightforward design for a database is just a mapping from a whole key to a category: ["cream", "whip"] => "dairy" . But that would require listing all likely real-world products: all sorts of apples, peppers, beans, etc. Which doesn't work for me since, as I mentioned, I don't have a firehose of data to fill it up.

But you'll notice that mostly all such product are defined by one word: an apple is an apple and is produce, regardless of the sort. So let's reify this in the form of a CSV file:

These one-word keys are called unigrams . To match a search query, we can simply look up every separate unigram from it in the database.

It works for surprisingly many cases, but it breaks on things like "apple juice", because despite having "apple" in it, it's a beverage, not produce.

This is fixed by making the order of rows in the database significant, so that juic,drink goes before appl,produce . Then, if several of the unigrams in a search query match, the earliest one wins.

This might smell to you like something prone to potentially irresolvable ordering cycles, but I actually found that I only really need two groups of significance:

Things like "juice", "milk" and "oil" are usually derived from something, as in "apple juice", "oat milk" and "olive oil". Keeping those derivations above raw ingredients ensures those tings are categorized correctly.

And don't take the word "raw" too literally. There are things like "ketchup" in there! But since nobody puts "tomato ketchup" on their shopping list, it is considered "raw" in my domain.

Bigrams

The next problem is combinations of words. "Spaghetti squash" is not a pasta, but a kind of squash. And "apple sauce" is neither produce, nor a condiment, but a snack! In both of these examples no single unigram is enough to correctly identify the product. This means I need to consider two-word terms called bigrams :

All bigrams come before unigrams, as their purpose is to serve as more specific disambiguations of conflicting unigrams. But this ordering is less significant than the groups (Derivations and Raw), so each of those gets their own set of bigrams.

At search query time, I produce bigrams as all possible combinations of two from the set of unigrams. Then they're added to unigrams as search terms:

The lookup process stays exactly the same: just check all terms one by one.

By the way, I need this code to also work in the Kotlin code of my Android app, and since Kotlin doesn't have combinations in the standard library, I wrote a trivial recursive implementation by hand:

Felt like solving a coding interview problem :-)

A few words about "pepper"… When combined with another word, it most often belongs in produce: "bell pepper", "chili pepper", "serrano pepper", etc. And since there are many of such, I want to classify the unigram "pepper" as produce to cover them all. However the single word "pepper" usually means ground black pepper, which is a spice! I tried to complicate the model at first, supporting wildcards like "* pepper". But I didn't find any other exception that would use it, so I de-complicated the model back and hard-coded a dumb `if` substituting "pepper" with "black pepper" before any lookups :-) Practicality beats purity!

Etymology woes

Human languages tend to merge words commonly used together. So something straight and forward becomes straight-forward and then just straightforward. I realized I need to care about it here after I collected examples like "redbull" and "lipbalm". Both should properly be spelled as two separate words, but people usually don't consult a dictionary before doing their groceries, so…

Funny factoid: "breadcrumbs" and "seaweed" are spelled as single words.

This can't be solved by spellchecking because my database doesn't contain original spelling: it has the bigram "bull red" and the unigram "balm", and they both are too far away from those search queries.

Instead, I started thinking about splitting words into syllables. To my everlasting surprise, nltk turned out to have several of those, from which I picked SyllableTokenizer . It is pretty simple, but it does work for "redbull" and "lipbalm" as you'd expect.

At first, I tried to switch the entire database to contain only syllables instead of full stemmed words, but it didn't work out. There are common syllables like "bar" and "can" that are also full words in their own right. So something like "barbecue sauce" would be split into ["bar", "be", "cue", ...] and will suddenly become a snack because I have a record saying that any kind of "bar" is a snack.

So instead I converged on a two-step lookup. First I split the search query into regular words and look them up as I did before. Then, if I didn't get a match, I split the words further into syllables and do a second lookup.

The syllabilization algorithm was another thing I had to port to Kotlin, because I couldn't find anything like that in the entire Java ecosystem. Drop me a note if you want that code for some reason.

Spell checking

Spell checking proved to be necessary nonetheless. Do you know if it's "fusilli" or "fussili"? Does "camamber(t?) has a "t" at the end? Or is it "haloumi" or "halloumi"? (Answers: 1) the former, 2) it does and 3) both spellings are correct.)

Unfortunately, a regular spell checker against English wouldn't work very well: all kinds of international foods and deliberately misspelled brand names kill the idea. Fortunately, I can spell check against my own database, which naturally represents the entire language that my app knows!

And the standard approach to spell checking is to employ some "edit distance" algorithm which shows how far apart is the spelling of two arbitrary words. I went with Damerau-Levenshtein (standard Levenshtein plus transpositions). I also had to come up with empirical numbers for maximum allowed distance depending on the word length. This was done completely unscientifically, and I expect to have to tweak it further. But for now it works!

Optimizations

The most astute reader might have already spotted a problem: what was a single hash-table lookup before the introduction of edit distance calculation has now turned into a linear search with each test being way more expensive than a straightforward string comparison.

So I had to to some low-hanging fruit plucking in terms of optimizations:

But I have to say that the main thing working in my favor here is that the data is just small !

"Separilla"?

I want to highlight two particularly weird wins made possible by the combined effect of syllabilization and spell checking.

A single term "may o" works for: "mayo", "mayonnaise", "mayones" and even "mayochup". Syllabilizing these words produces "may" and some variant of "o"/"on"/"oc", which is then smoothed over by spell checking.

And I just want to state for the record that the existence of such a thing as "mayochup" made me die a little inside. Is the trouble of mixing mayo and ketchup by yourself in your kitchen so unfathomably hard that you need a brand to produce it for you? Geez…

One of the previously unknown to me items in the feedback was submitted as "separilla", which turned out to be a misspelling of " sarsaparilla ". So I picked out three syllables conveying the meaning: "sar", "pa" and "ril". And, thanks to spell checking, they're enough to cover both the correct spelling and a few incorrect ones.

Real data

Initially I thought of putting the collected data up on Kaggle , but since it's now heavily dependent on a custom algorithm, I'm just going to leave it as is in the Shoppy repo:

Content version: df2c304dee56