Week 10, continued

If you’re coming down for the Harvard-Yale game and getting there a little early, you should definitely check it out!

ELIZA clearly responds to some pieces of what you’re saying, but without any real understanding.

This is a kind of system called pattern matching, where we’re taking bits of text that were provided by the user, performing some transformation on them, and returning them back to the user.

The asterisk at the end indicates that this is just going to be the beginning of ELIZA’s response, and the rest of the user’s input will be filled in to finish the sentence:

WHY DO YOU WANT*TO IMPRESS MY BOSS.

But there’s actually a little more processing that goes on here, to convert pronouns, etc.

Rather than just sticking the rest of the user’s utterance on the end, we’ll take the words - the string tokens - one at a time and perform conversions as necessary:

I want to impress my boss.
-
WHY DO YOU WANT
WHY DO YOU WANT TO
WHY DO YOU WANT TO IMPRESS
WHY DO YOU WANT TO IMPRESS *YOUR*
WHY DO YOU WANT TO IMPRESS YOUR BOSS
WHY DO YOU WANT TO IMPRESS YOUR BOSS_*?*_

In fact, he had to fire his assistant, who spent all her time talking to ELIZA about her problems.

Everyone who talked to ELIZA anthropomorphized it, to the point that psychotherapists worried they would be replaced.

First, we have a list of keywords:

char *keywords[]= {
        "CAN YOU","CAN I","YOU ARE","YOURE","I DONT","I FEEL",
        "WHY DONT YOU","WHY CANT I","ARE YOU","I CANT","I AM","IM ",
        "YOU ","I WANT","WHAT","HOW","WHO","WHERE",
        "WHEN","WHY",
        "NAME","CAUSE","SORRY","DREAM","HELLO","HI ","MAYBE",
        " NO","YOUR","ALWAYS","THINK","ALIKE","YES","FRIEND",
        "COMPUTER","CAR","NOKEYFOUND"};

We also have a set of words to swap, like converting MY to YOUR:

char *SWAPS[NUMSWAPS][2] = {
    {"ARE","AM"},
    {"WERE", "WAS"},
    {"YOU","I"},
    {"YOUR", "MY"},
    {"IVE", "YOU'VE"},
    {"IM", "YOU'RE"},
    {"YOU", "ME"},
    {"ME", "YOU"},
    {"AM","ARE"},
    {"WAS", "WERE"},
    {"I","YOU"},
    {"MY", "YOUR"},
    {"YOUVE", "I'VE"},
    {"YOURE", "I'M"}
};

And then we have prewritten responses, with multiple responses for each scenario, so that if we say "yes" to ELIZA four times in a row, we could get four different responses:

char *responses[NUMKEYWORDS][9] = {
    {   "DON'T YOU BELIEVE THAT I CAN*",
        "PERHAPS YOU WOULD LIKE TO BE ABLE TO*",
        "YOU WANT ME TO BE ABLE TO*"},
    {   "PERHAPS YOU DON'T WANT TO*",
        "DO YOU WANT TO BE ABLE TO*"},
    ...
    {   "YOU SEEM QUITE POSITIVE.",
        "ARE YOU SURE?",
        "I SEE.",
        "I UNDERSTAND."},
    ...
    {   "SAY, DO YOU HAVE ANY PSYCHOLOGICAL PROBLEMS?",
        "WHAT DOES THAT SUGGEST TO YOU?",
        "I SEE.",
        "I'M NOT SURE I UNDERSTAND YOU FULLY.",
        "COME, COME ELUCIDATE YOUR THOUGHTS.",
        "CAN YOU ELABORATE ON THAT?",
        "THAT IS QUITE INTERESTING."}
};

In the actual main function, we initialize some variables, do some housekeeping, but then we get to the very understandable loop that actually controls ELIZA’s behavior:

int main(int argc, char * argv[])
{
    ...
    while (1) {
        readline(inputstr);

        // check for termination
        if (strcmp(inputstr,"BYE")==0)
            break;

        // check for repeated entries
        if (strcmp(lastinput,inputstr)==0)
        {
            printf( "PLEASE DON'T REPEAT YOURSELF!\n");
            continue;
        }
        strncpy(lastinput,inputstr,strlen(inputstr)+1);
...

We follow a statistical model that starts with phonetics, to identify what letters correspond to the sounds.

On top of that, we’ll build a word pronunciation model that combines these into a word.

We then need a language model to combine words into sentences.

All of these models are really just going to be statistics, so we can work with them all simultaneously.

For example, when you make an M sound, there’s a short intake of breath, a sort of humming with your lips together, and then a plosive, or expelling of breath.

The model is designed to take into account that different people may have slightly different timing of these stages, or that the same letter comes out slightly differently in different words.

To recognize a particular sound, we build a hidden Markov model of every letter we have, and then determine which has the highest probability of creating the sound.

We need multiple paths because any speech recognition system is going to have to work with lots of differen speakers with different accents and even different uses of the same words.

The language model operates on what’s called an N-gram model, which determines how likely a given word is to appear after the previous word or words.

For example, a bigram model determines its probability on just the immediate previous word (so the probability of the sentence The rat ate cheese. would be the probability of a sentence starting with The, times the probability of the word rat following the word the, times the probability of the word ate following the word rat, times the probability of the word cheese following the word ate).

Similarly, with a trigram model, we could indicate that the words Weather forecast are likely to be followed by the word today or tomorrow but unlikely to be followed by the word artichoke.

We can build an N-gram language model by counting the occurrences of each N-gram in a large corpus of text (e.g., every Wall Street Journal published since 1930).

If we do this with a large enough sample of data, it works really well.

They have to do a little more than this to actually answer questions, but these three steps are what it takes to recognize what you’re saying.

Now that we know these models are just statistical, we can play some games with Siri, like asking "Siri, what is the weather hippopotamus New Haven today?" - and we’ll see that even though Siri does recognize the word hippopotamus in our question, it gets ignored and the exact same weather results are returned, because Siri has figured out the pattern.

However, if we go far enough away from this model - like asking "Siri, what is the weather armadillo artichoke hippopotamus New Haven?" - Siri can’t pick up on the weather + New Haven pattern and instead resorts to just giving us search results instead.

This includes recognizing which words are nouns, verbs, etc, as well as determining whether a given sentence structure is grammatically valid within a particular grammar (e.g., English grammar).

This helps, but isn’t enough on its own to determine the meaning of a sentence.

We associate with each word a function, a certain transformation that it allows to happen.

Any type of semantic processing requires a little bit of knowledge and a lot of work on our part - just plain statistics aren’t generally enough to generate a semantic model.

Most of these systems require humans to spend a great deal of time encoding how these sentences can be represented semantically.

Sometimes there are ambiguities that semantics can’t resolve, e.g.:

Red-hot star to wed astronomer.
Squad helps dog bite victim.
Helicopter powered by human flies.

Syntax and semantics can’t distinguish between these interpretations! But question-answering systems need to be able to tell the difference.

There have been huge improvements in these systems in the last decade.

IBM’s Watson is one of the best examples of a question-answering system today.

These methods aren’t much different from what you’ve learned in this class! We can parse HTTP requests, get information from an external database, and so on.

There are various domain-specific question-answering systems in areas like medical informatics and even food-beer pairings.

However, they don’t work across domains - asking the food-beer system about medical issues won’t work.

We’re still hand-coding the infrastructure to make these run.

Siri doesn’t care about these differences, giving the same answer regardless of tone of voice.

Some interfaces, though, do react to those differences, such as a robot that Scaz brought with him named Jibo.