Make bots great again

Friday, September 30, 2016 Fede Torri

An illustrated longread on the perils & pitfalls of building a natural language AI.

Sometimes in 2016, bots became the next big thing. Spurred by positive press coverage and hyped demand, many digital companies jumped on the bandwagon and started providing mediocre solutions for a very complex problem; one that’s still unsolved after more than 60 years of research in the field. 

Forget what you read in the Sunday paper: machines can’t use language efficiently, form abstractions without being coaxed to do so, or represent machine-born concepts in human state. The artificial intelligence Hollywood has you dreaming of just isn’t here yet.

At Datatonic, the company I work for, we’re no experts in bots. We’re a machine learning company; and since we mainly work with very large customers we’re basically immune from the media’s hype machine. We also tend to deliver technology that works — and bots, in their current incarnation, did not fit the bill.

Or so we thought, until Google called us with a challenging offer. A very large IT provider for an even larger European telecom company had been struggling for quite some time with creating believable bots that would take over their customer service. After almost one year, the project had stalled. The IT provider had turned to Google, which in turn decided to ping our team. We had our reservations, but all in all it was an offer we simply couldn’t refuse.

Our NDA unfortunately forbids us from sharing actual code, but we thought we’d give something back to the community and to the general public at large by charting our thought process, technical approach and final results.

Part 1: Why bots don’t work

A complete explanation of each and every issue involved in natural language understanding would be beyond the scope of this article. But we’d like to pinpoint how and why the bot-hype machine lied to you.
First of all: bots (and AIs in general) have no semantic understanding of what a word actually means. Humans are very good at detecting the meaning of a word based on the context: if I told you I’d spent my weekend hunting axolotls in Extremadura, you’d be able to deduce that axolotls are animals and Extremadura a location — probably a hispanic one, even though you can’t really put your finger on why. And even if you’ve never seen an axolotl in your life, you’d immediately understand how it looks like if I were to tell you it’s a ‘transparent lizard that lives underwater’. The semantic representation in your head allows you to do any operation of the sort: Axolotl = lizard + water minus color, even though there’s no obvious way to sum or subtract words.

Second major pain point: a bot has no general context understanding. If I told you ‘someone drew a gun’ your reaction would be vastly different depending on if we were talking about artists or bank robbers.

Last main issue to consider: a bot has no memory. You can trick it into holding a rudimentary ‘database’ of stuff that has already been handled in the conversation; but even on a sentence level every bot suffers from a bad case of memory loss. Just think about the sentence ‘I’d like a pizza’, and how it changes if you prepend ‘I’m not sure if-’, ‘I’m totally positive- ’ or ‘I don’t think -’. A bot that has no memory of what’s been said previously in the sentence and in the conversation cannot possibly understand humans correctly.

Many of the existing off-the-shelf bot AI solutions have decided to sidestep those issue by naively focusing on a very narrow pre-processed user experience path. To configure your bot for prime-time, you need to input all of the possible conversation branches, after which the AI tries to recognize what your users are actually asking. All of the user’s interaction have to be charted beforehand. It’s more of a choose-your-adventure book than a real chatbot.

In this widely used brute-force approach, only an (almost) exact sentence match will be recognized. So you have to define your entire conversation beforehand.

bag-of-words is slightly better: the match probability is calculated on each single word and aggregated: you don’t need an exact sentence match

Bots that focus on intent recognition will often simplify sentences by disregarding their grammar and structure entirely; throwing all of the sentence’s words in a single ‘bag’ and counting the number of occurrences. And while this bag-of-words approach has been very successful in the past for simple tasks such as spam filters (as an e-mail containing many occurrences of ‘Russian brides’ or ‘enlargement’ is probably spam), it fails to account for many nuances in human speech such as word order and punctuation (keep in mind a single comma separates the friendly “let’s eat, grandpa” from the cannibalistic “let’s eat grandpa”)

Even worse, because of their catch-all structure, general purpose bots will only try to count words with a specific overarching meaning (‘entities’), and by doing so miss important clues about the true meaning of the conversation.

For these and many other reasons, not only our client’s bot but actually most chatbots are failing at providing a new, compelling UX paradigm. They are simply not smart enough.

For these and many other reasons, not only our client’s bot but actually most chatbots are failing at providing a new, compelling UX paradigm. They are simply not smart enough.

Part 2: how to fix bots

I. giving our Bot semantic knowledge
The first thing we do when starting a new machine learning project is brainstorming about the most important features of the problem at hand. A feature is a parameter that allows you to discern between outcomes, or ‘labels’ . For example, if you were to label pizzas into ‘Margherita’, ‘Pesto’ or ‘Romana’, then ‘sauce colour’ would be a great feature to use, whereas ‘is_round’ would be extremely unhelpful in finding out the right category.

In our case the ‘labels’ we wanted to predict were numerous and open-ended — they basically all are the answer to the questions: ‘what does the customer mean/want?’. That’s all pretty straightforward. The major challenge is identifying relevant features. For what features would you, as a human, use to distinguish between the sentences ‘I’d like a large Pizza’ and ‘my smartphone is not working?’

It’s clear then that meaning of words and their actual structure are completely disconnected. ‘Dog’, ‘Chien’ and ‘Perro’ all refer to the same concept, but they have otherwise nothing in common. The bag-of-word approach only counts total occurrences, and can therefore get away with random tags. But, as research groups realized in the late seventies, this very same flexibility was both a blessing and a curse, making bag-of-words bots very robust but wildly inaccurate.

A more modern standard for context reconstruction was tested in the late eighties under the name Wordnet: it attempted to model relations between words by having humans assign them to synsets- general, tree-structured groups of categories such as ‘’, ‘n.canine’, ‘n.domestic_animal’.

The main issue with Wordnet is that humans still needed to tag each and every word that was going to be used in the system, for each and every language. That is a monumental task considering the numerous, ever-changing thesaurus of our planet. It would be just like having our system discern between ‘cats’ and ‘lions’ by photographing each and every cat and lion under the sun: a no-go, given the size and scope of our project.

Therefore, we needed something entirely different. Our choice fell on a seminal discovery, pioneered by Tomas Mikolov at Google in 2013. This approach is called Word2vec, or more generally a ‘word-embedding approach’, and just like many deep-learning systems it allows a computer to model features all on its own instead of relying on human ‘translators’.

Word2vec basically ingests a very large corpus of texts (usually Wikipedia in the local language), and assigns an N-dimensional vector to each word based on the context that usually occurs around it. So for example, ‘I’m eating cheese’, ‘I’m eating pasta’ and ‘I’m eating pizza’ will have the system identify ‘cheese’, ‘pasta’, and ‘pizza ’ as belonging to a single category: therefore, those three words will be neighbours in an N-dimensional vector space.

As it turns out, this kind of representation has three main advantages: first of all, it’s easy to store, understand and debug, allowing us to reduce a very large set of words (usually in the tens of thousands) to a matrix with just N columns (200, in our case). Secondly, it represents words as vectors, allowing mathematical operations on them (something that would be impossible both using bag-of-words or wordnet-like methods).
Third main advantage: it’s pretty damn similar to what’s actually in our brains. And so if you take the vector for ‘Italy’, sum the vector ‘Rome’ to it and subtract ‘France’, what you get is actually ‘Paris’. If you take ‘King’+’Woman’-’Man’, you totally do get ‘Queen’!

All similar verbs are grouped together, as are prepositions, junk foods, famous figures, past tenses and so on. In the word2vec representation, a basic version of the equality ‘Axolotl = lizard + water — color’ actually holds true. And while it’s true that, unlike a real person, the system still has no idea of what those N-dimensional clusters actually represent (and how could a computer actually understand what a ‘queen’ is?), we are computer scientists, not linguists or philosophers, and it seemed to us we had solved the first issue. Our bot now could do, if not semantic understanding, at least semantics clustering.

II. giving our Bot contextual understanding
Once you have a convincing semantic representation, you still have to account for the relations between words. The bag-of-words approach does entirely away with grammar and sequencing order, and simply focuses on which words appear in the entire sentence. This is a very naive approach; but the technical challenge increases exponentially as soon as you deviate from it. For, if you do so, you need to account for a large number of details and grammatical nuances. The length of your sequence becomes a variable too (and how long can a sentence get?), something that makes it extremely difficult to build coherent optimization routines, to allocate memory and computing power efficiently, and to actually identify what’s important and what isn’t.

To solve this problem you just need to think about how humans read. Not by ingesting the entire sequence at once, but by reading it word-by-word. A human is able to sequentially read a sequence, and break it down in sub-sentences, isolating the most important words.

To implement this, we borrowed a technology that’s used in image and signal recognition: a convolutional neural network. A CNN uses a ‘sliding window’ (think about your eyes while you’re reading) to cluster neighbouring words in a sentence, filter them and isolate key concepts. Just like in image recognition, a convolutional network can robustly ignore small differences in words used and sentence ordering by considering many windows of varying sizes using different ‘filters’. All those filters output a smaller sentence vector, from which the most important dimensions are selected in the step called ‘max-pooling’. Those key terms are then scanned again in a second ‘convolution’ step, then ‘pooled’ again, and so on.

this CNN has just two steps: a convolution step, with a window size of 3, and a max-pooling step with 2 filters at a time.
Such a network will ignore small variation in ordering and context (the so-called location invariance). It will also account for the the local context inside the sliding window, and build many filtered sub-vectors, breaking down the sequencing problem in many smaller subsets. Last but not least, it will analyze an entire variable-length phrase and reduce it to a fixed length vector that is guaranteed to contain the most relevant information about the original input (the so-called compositional completeness).

Convolutional networks are a very wide topic that deserves its own write-up (and we recommend this one from the amazingly talented Chris Olah). But for the sake of keeping it short let’s just quickly recap our results. CNNs were our answer to our semantic representation (a vectorial one, with Word2vec) missing the general context. By coupling Word2vec with CNNs we were finally able to have our bots take into account the entire sentence context, break down longer phrases into sub-vectors, and filter them into their most relevant components. Repeat those steps multiple times, and you get a bot that’s able to understand the entire sequence by systematically reducing her complexity.

At this point our chatbot was performing much better than most competitors, and at least 20% better than our own baseline model, but it was still missing an important component: memory. A CNN breaks down sentences in clusters and only keeps the most relevant items from each of those: it discriminates based on context and word ordering (that is: it sees the difference between ‘it is a great pizza, isn’t it?’ and ‘it isn’t a great pizza, is it?’), but it still forgets that we’re talking about pizza after just a few words.

III. giving memory to our Bot
This was the last, most important point. A bot with no memory will probably understand short statements and unambiguous sentences, but fail badly at decoding meaning swings in a longer phrase. Humans remember the context they’re working with, and use it to nuance the meaning of every following word; CNNs on the other hand start from scratch with each filtered word cluster.

To solve this problem, we chose to work with an LSTM (Long-short-term memory) network. LSTMs are a special kind of recurrent neural networks: whereas a normal neural network (such as a CNN) takes the entire sentence as input and processes it at once, a recurrent network actually ingests information sequentially: the state of the network at a previous timestep is also used as input, allowing the network to have a rudimentary form of memory.

Unfortunately, RNNs tend to be unable to remember more than the last few words. LSTMs, on the other side, replace normal neuron with ‘memory cells’, that allow them to keep track of important (past) informations, while discarding unuseful stuff.

A word-based LSTM memory cell will take two inputs: the word to consider and the memory state of the network. A forget gate will allow the network to discard information that’s no longer relevant: if the sentence’s subject has changed, for example, the cell will forget the previous subject’s gender and number. An input gate will select relevant information about the current word and its interaction with the current network state. That information will be committed to memory; and an output gate will, in turn, spew two outputs: the classification for the current word as well as a general, updated memory state. The second will be used as input in the following cell, along with the next word, and so on.

an LSTM has a memory state flow (above) and an input/output flow (below). Each gate uses its own set of neurons and activations.
LSTMs have been involved in many of the most interesting breakthroughs of the last few years, and they do indeed work as advertised. After a very lengthy training process, our chatbot was ready: time to ship.

Part 3: booting up

We unveiled the first version of the Datatonic-bot to our client after two very long weeks of research, testing and training on Google’s online infrastructure. DT-bot uses its brains to process chat requests from tens of thousands of users every day; it is written in Tensorflow and runs on Google’s Cloud ML, but it is nonetheless able to classify up to 4000 sentences per second into hundreds of different categories (describing the needs of the calling user), and to do so correctly 85% of the times.

Since then, we’ve been busy adding even more functionality to our chatbot, enabling it to work in different languages, automatically process entity names (such as the caller’s address, name, and more), and work not only with chat data, but also with voice and telephone data.

And we’ve grown quite fond of it. It’s not the smart bot you’d see in a big-budget movie. It’s no HAL 9000 or Samantha; heck, it’s not even wall-E! But it’s a great little product that works amazingly well. A shining example of how a small, passionate, talented technology outfit can pull off a state-of-the-art artificial intelligence. It’s lacking in marketing buzzwords, but high in functionality. It’s a work of art, a labour of love, a big step forward.

Of course it’s not the artificial intelligence Hollywood has you dreaming of. Because this one, we dreamed it up ourselves.

1 comment: