Presenting this Saturday at Atlanta Code Camp

by Administrator 17. May 2012 07:50

I'll be presenting a talk this Saturday at the Atlanta Code Camp about the natural language processing engine I've been blogging about, recently. You can find more details at http://www.atlantacodecamp.org/default.aspx.

Hope to see you there!

ddcfc70d-4c93-4536-a80d-902cee146fba|0|.0

Tags: .net, natural language processing

Writing a Natural Language Parser in C# Part 5 - Questions and Rules

by Administrator 10. April 2012 12:13

This post is part of a series on creating a natural language processor in C#. The other entries in this series are:

Writing a Natural Language Parser in C# Part 1–Why?
Writing a Natural Language Parser in C# Part 2 – Architecture
Writing a Natural Language Parser in C# Part 3–CommandProcessor and ConversationContext
Writing a Natural Language Parser in C# Part 4–Tokens

In this, the last part in this series, I'd like to look at the final step in processing the user's input which is locating a rule that matches the set of tokens that have been generated. If you'll remember, in the last entry we saw how the user's input was tokenized and how those tokens we then organized into a Dictionary<int, List<TokenResult>> structure where the integer key was the index into the string where the tokenized input was found and the TokenResult itself was added to the list corresponding with that position. Now that we have that structure, we need to evaluate the rules we have defined to see if there is a match.

What is a Rule

A rule is a method that represents a form of expected input the system can look for. In a way, the tokens and rules we define make up the system's vocabulary where the tokens represent the words and phrases the system knows about and the rules represent the whole thoughts the system can work out. For example, look at the following rule definition.

A Rule Definition
public static void GetWeather(ConversationContext cContext, TokenList list, TokenWeather weather)
        {
            cContext.Say(WeatherService.GetTodaysWeather(cContext.ConversationUser), null);
        }

All rules are defined in classes that implement the IRuleClass interface. This interface has no members defined on it, but is used as a marker interface so that we can find all the types that contain rules using reflection. Whereas we could use MEF to load all our tokens, we can't do this with rules since there is no commonality between the classes that contain them. Here, we have to resort to using reflection.

Each rule will take a ConversationContext as its first parameter which will be followed by a list of token types. In the above example, we're looking for a TokenList and a TokenWeather. The objective is that if the user passes in something like "what's the weather" or "get the weather", this rule will be found to be a match for that request and our weather service will be called to get the forecast. Then, the Say method on the ConversationContext instance will be called to push the forecast back to the user. The second parameter, if you'll recall (null here) is the tag value that is serialized and saved in the conversation history for future reference.

Finding the matching Rule

So, how do we go about using our dictionary to find a matching rule?

First, locate and load all the rules found in the solution. See code below that uses reflection to locate and get instances of all the rules.

Load rules
var rules = new List<MethodInfo>();
            var assemblies = new List<Assembly>();
            var currentAssembly = Assembly.GetExecutingAssembly();
            string path = currentAssembly.Location;
            IEnumerable methods = null;
 
            foreach (string dll in Directory.GetFiles(Path.GetDirectoryName(path), "*.dll"))
            {
                try
                {
                    assemblies.Add(Assembly.LoadFile(dll));
                }
                catch (Exception)
                {
                }
            }
 
            foreach (var assembly in assemblies)
            {
                List<Type> ruleClasses = (from t in assembly.GetTypes()
                                          where !t.IsInterface
                                          where !t.IsAbstract
                                          where t.GetInterface("SmartHome.Core.IRuleClass") != null
                                          select t).ToList();
 
                foreach (var ruleClass in ruleClasses)
                {
                    if (ruleClass == null)
                    {
                        continue;
                    }
 
                    methods = from m in ruleClass.GetMethods()
                              where m.IsStatic
                              select m;
 
                    rules.AddRange(methods.Cast<object>().Cast<MethodInfo>());
                }
            }
 
            return rules.ToList();

Loop through the rules and for each one, get a list of all the rule's parameters.

Get list of parameters
var parameters = (from p in rule.GetParameters()
                                  where p.ParameterType != typeof(ConversationContext)
                                  select p).ToList();

Now, since the order of the parameters should match the order our tokens are found in the input, we loop though the parameters for each of the rules and for each one, see if we have a token in each of the lists in our dictionary; in index order. For each rule, then, we keep track of how many of our TokenResult classes wrapped a matching Token type, again in the same order that the parameters are specified. After all the rules have been evaluated, we look at these results we have saved for each. If there are tokens in the dictionary that are not found in the parameter list, the rule is thrown out. Next, if there are parameters in a rule that are not in the dictionary, the rule is thrown out. Of the remaining rules, the top 1 is selected. The rule is invoked and an instance of the ConversationContext along with the other defined parameters are passed in.

Questions

As we saw before, the ConversationContext class defines a method, AskQuestion(). This functionality was not in my original implementation. I found, however, that there were some things that were difficult to communicate to the system in a single sentence. For example, I wanted the system to be able to handle reminding the user of something on a particular date at a particular time and also allow the user to specify which channels they were reminded on. For example, "remind me to get a haircut on Friday at 4:00 PM and remind me via email and sms". My thoughts were that it's easier for the user to just say, "remind me to get a haircut" and let the system prompt them for the other details. To enable this, I created two additional types, Question and QuestionManager. The Question type simply contains information about the question. See its definition, below.

Question
[DataContract]
    public class Question
    {
        [DataMember]
        public string QuestionText { get; set; }
 
        [DataMember]
        public List<Token> ExpectedReplys { get; set; }
        
        [DataMember]
        public Action<ConversationContext, object,
            List<Token>> ExecuteIfAnswered { get; set; }
        
        [DataMember]
        public ConversationMode Mode { get; set; }
        
        [DataMember]
        public string Address { get; set; }
        
        [DataMember]
        public Guid UserId { get; set; }
        
        [DataMember]
        public DateTime PosedDateTime { get; set; }
        
        [DataMember]
        public object State { get; set; }
    }

Instances of this class store the text of the question and information about the channel and context the question was asked on. In addition, there is a callback that will be executed when the question is answered and a list of tokens that the input must match in order qualify as an answer to the question. This match is evaluated in exactly the same way we matched rules, before. The QuestionManager stores these questions until they are answered. It is called to evaluate the input from the user to see if it matches any of the questions it is managing and once a question is matched, its callback is called and it is then removed from the QuestionManager.

e3cfb8c3-4baf-4f69-a8b9-476c0c551515|0|.0

Tags: .net, natural language processing

Writing a Natural Language Parser in C# Part 4–Tokens

by Administrator 1. April 2012 06:50

This post is part of a series on creating a natural language processor in C#. The other entries in this series are:

This week, I’d like to look deeper into how the speech processor tokenizes the incoming command.

When I first started thinking about creating a speech processor for my smart home software, I did quite a bit of research on the internet looking to see what the state of this technology was and what people were doing with it. What I found was that there were several pieces of software out there like SharpNLP and Antelope that are capable of taking a sentence and breaking it down into its constituent phrases and words. They can identify the part of speech each is, the definition of words and their synonyms. The output from such a tool might look something like this.

Let/VB 's/PRP see/VB how/WRB tokenization/NN works/VBZ in/IN SmartNLP/NNP ./.

I was amazed at all this until I tried to figure out how to apply this technology to my problem of communicating with my machine. I found that even with all this information about what was said, I still couldn’t understand it enough to act on it. I discovered a different approach which is the conversion of the input into tokens containing a different set of properties. Once the input was tokenized, it was no longer a string, but a collection of objects that could be processed to discover what was being communicated.

Let’s look at how the system tokenizes its input.

Anatomy of A Token

A token has three members; A collection of phrases, a value and one method that takes the input and returns results. A skeleton would look like this:

Token
[DataContract]
    public class Token
    {
        protected List<string> Words;
 
        [DataMember]
        public object Value { get; set; }
 
        public virtual IEnumerable<TokenResult> Parse(string input, Guid userId)
        {
 
        }
    }

Here, the list of strings, Words, holds a collection of words or phrases that the class will locate and generate a result for. The Value property will hold the value that has been parsed. Depending on the token, this could be a string, a DateTime or a number. Last, the Parse method is called to do the actual parsing. All tokens inherit from the base Token class. The parse method is implemented in this class to provide a basic functionality of locating phrases that are in the Words collection and return a TokenResult for each.

Some of the tokens are very simply implemented and others are quite complicated depending on what is being parsed. For example, the token that parses the user’s request for information is TokenList, as in “list reminders”. Its entire implementation looks like this:

TokenList
[DataContract]
    [Export(typeof(IParseToken))]
    public class TokenList : Token, IParseToken
    {
        public TokenList()
        {
            Words = new List<string> { "list", "show", "get", "lists", "what are my", "whats" };   
        }
    }

This class takes advantage of the base class’ Parse implementation. Also, notice that the Words lists contains synonyms for list. If the user specifies any of these values, it will be parsed as TokenList.

As an example of a more complicated Token, consider a token that parses a DateTime. Here, we would override the base class’ implementation of parse and look for portions of the input that could be parsed as a DateTime. This can get quite complicated when you consider that the user could say something like “remind me to call bob next saturday” This token would need to be able to recognize that “next saturday” specifies a date and then calculate what that date is.

TokenResult

The Token classes all return an instance of TokenResult for each value they parse out. The TokenResult class is listed below.

TokenResult
[DataContract]
    [KnownType("GetKnownTypes")]
    public class TokenResult
    {
        [DataMember]
        public object Value { get; set; }
 
        [DataMember]
        public string TokenType { get; set; }
 
        [DataMember]
        public int Start { get; set; }
 
        [DataMember]
        public int Length { get; set; }
 
        [DataMember]
        public Token Token { get; set; }
 
        private static IEnumerable<Type> GetKnownTypes()
        {
            return new List<Type>
                            {
                                typeof (Token),
                                typeof (TokenInt),
                                typeof (TokenLong),
                                typeof (TokenNumeric),
                                typeof (TokenPercentage),
                                typeof (TokenQuotedPhrase),
                                typeof (TokenResult),
                                typeof (Tokens.Nouns.TokenNoun),
                                typeof (Tokens.Nouns.TokenToDo),
                                typeof (Tokens.Nouns.TokenEmail),
                                typeof (Tokens.Nouns.TokenSms),
                                typeof (Tokens.Nouns.TokenWeather),
                                typeof (Tokens.Nouns.TokenNews),
                                typeof (Tokens.Nouns.TokenIm),
                                typeof(Tokens.Nouns.TokenNeither),
                                typeof(Tokens.Nouns.TokenYesNo),
                                typeof(TokenReminder),
                                typeof(TokenDefinedList),
                                typeof(TokenNamed),
                                //typeof (Tokens.Nouns.TokenDevice),
                                //typeof (Tokens.Nouns.TokenRoom),
                                typeof (Tokens.Nouns.TokenState),
                                //typeof (Tokens.Nouns.TokenStructure),
                                //typeof (Tokens.Nouns.TokenZone),
                                typeof (Tokens.Nouns.TokenDim),
                                typeof (Tokens.Prepositions.TokenPreposition),
                                typeof (Tokens.Temporal.TokenDeterminateSeries),
                                typeof (Tokens.Temporal.TokenExactTime),
                                typeof (Tokens.Temporal.TokenIndeterminateSeries),
                                typeof (Tokens.Temporal.TokenTemporal),
                                typeof(Tokens.Temporal.TemporalParts.TokenDayOfWeek),
                                typeof(Tokens.Temporal.TemporalParts.TokenApril),
                                typeof(Tokens.Temporal.TemporalParts.TokenAugust),
                                typeof(Tokens.Temporal.TemporalParts.TokenDayAfterTomorrow),
                                typeof(Tokens.Temporal.TemporalParts.TokenDayBeforeYesterday),
                                typeof(Tokens.Temporal.TemporalParts.TokenDecember),
                                typeof(Tokens.Temporal.TemporalParts.TokenEach),
                                typeof(Tokens.Temporal.TemporalParts.TokenEighteenth),
                                typeof(Tokens.Temporal.TemporalParts.TokenEighth),
                                typeof(Tokens.Temporal.TemporalParts.TokenEleventh),
                                typeof(Tokens.Temporal.TemporalParts.TokenFebruary),
                                typeof(Tokens.Temporal.TemporalParts.TokenFifteenth),
                                typeof(Tokens.Temporal.TemporalParts.TokenFifth),
                                typeof(Tokens.Temporal.TemporalParts.TokenFirst),
                                typeof(Tokens.Temporal.TemporalParts.TokenForteenth),
                                typeof(Tokens.Temporal.TemporalParts.TokenForth),
                                typeof(Tokens.Temporal.TemporalParts.TokenFriday),
                                typeof(Tokens.Temporal.TemporalParts.TokenInt),
                                typeof(Tokens.Temporal.TemporalParts.TokenJanuary),
                                typeof(Tokens.Temporal.TemporalParts.TokenJuly),
                                typeof(Tokens.Temporal.TemporalParts.TokenJune),
                                typeof(Tokens.Temporal.TemporalParts.TokenLong),
                                typeof(Tokens.Temporal.TemporalParts.TokenMarch),
                                typeof(Tokens.Temporal.TemporalParts.TokenMay),
                                typeof(Tokens.Temporal.TemporalParts.TokenMonday),
                                typeof(Tokens.Temporal.TemporalParts.TokenMonth),
                                typeof(Tokens.Temporal.TemporalParts.TokenNinteenth),
                                typeof(Tokens.Temporal.TemporalParts.TokenNinth),
                                typeof(Tokens.Temporal.TemporalParts.TokenNovember),
                                typeof(Tokens.Temporal.TemporalParts.TokenNumeric),
                                typeof(Tokens.Temporal.TemporalParts.TokenOctober),
                                typeof(Tokens.Temporal.TemporalParts.TokenOrdinal),
                                typeof(Tokens.Temporal.TemporalParts.TokenOther),
                                typeof(Tokens.Temporal.TemporalParts.TokenPercentage),
                                typeof(Tokens.Temporal.TemporalParts.TokenRelativeTemporalOrdinal),
                                typeof(Tokens.Temporal.TemporalParts.TokenSaturday),
                                typeof(Tokens.Temporal.TemporalParts.TokenSecond),
                                typeof(Tokens.Temporal.TemporalParts.TokenSeptember),
                                typeof(Tokens.Temporal.TemporalParts.TokenSeventeenth),
                                typeof(Tokens.Temporal.TemporalParts.TokenSeventh),
                                typeof(Tokens.Temporal.TemporalParts.TokenSixteenth),
                                typeof(Tokens.Temporal.TemporalParts.TokenSixth),
                                typeof(Tokens.Temporal.TemporalParts.TokenSpecifiedDate),
                                typeof(Tokens.Temporal.TemporalParts.TokenSunday),
                                typeof(Tokens.Temporal.TemporalParts.TokenTenth),
                                typeof(Tokens.Temporal.TemporalParts.TokenThird),
                                typeof(Tokens.Temporal.TemporalParts.TokenThirteenth),
                                typeof(Tokens.Temporal.TemporalParts.TokenThirtieth),
                                typeof(Tokens.Temporal.TemporalParts.TokenThirtyFirst),
                                typeof(Tokens.Temporal.TemporalParts.TokenThursday),
                                typeof(Tokens.Temporal.TemporalParts.TokenTime),
                                typeof(Tokens.Temporal.TemporalParts.TokenToday),
                                typeof(Tokens.Temporal.TemporalParts.TokenTomorrow),
                                typeof(Tokens.Temporal.TemporalParts.TokenTuesday),
                                typeof(Tokens.Temporal.TemporalParts.TokenTwelth),
                                typeof(Tokens.Temporal.TemporalParts.TokenTwentieth),
                                typeof(Tokens.Temporal.TemporalParts.TokenTwentyEighth),
                                typeof(Tokens.Temporal.TemporalParts.TokenTwentyFifth),
                                typeof(Tokens.Temporal.TemporalParts.TokenTwentyFirst),
                                typeof(Tokens.Temporal.TemporalParts.TokenTwentyFourth),
                                typeof(Tokens.Temporal.TemporalParts.TokenTwentyNinth),
                                typeof(Tokens.Temporal.TemporalParts.TokenTwentySecond),
                                typeof(Tokens.Temporal.TemporalParts.TokenTwentySeventh),
                                typeof(Tokens.Temporal.TemporalParts.TokenTwentySixth),
                                typeof(Tokens.Temporal.TemporalParts.TokenTwentyThird),
                                typeof(Tokens.Temporal.TemporalParts.TokenWednesday),
                                typeof(Tokens.Temporal.TemporalParts.TokenYesterday),
                                typeof (Tokens.Verbs.TokenCreate),
                                typeof (Tokens.Verbs.TokenDelete),
                                typeof (Tokens.Verbs.TokenList),
                                typeof (Tokens.Verbs.TokenRemind),
                                typeof (Tokens.Verbs.TokenReset),
                                typeof (Tokens.Verbs.TokenWhatIs),
                                typeof(Tokens.Verbs.TokenWhereIs),
                                typeof(Tokens.Verbs.TokenWhoIs),
                                typeof (Tokens.Verbs.TokenWhoSang),
                                typeof (Tokens.Verbs.TokenWhoWasIn),
                                typeof (Tokens.Verbs.TokenRemindMeTo),
                                typeof (Tokens.Verbs.TokenRemindMeAt),
                                typeof(System.Type),
                                typeof(Questions.Question)
                                //typeof(StructuredSpeech2.House.Structure.Device),
                                //typeof(StructuredSpeech2.House.Structure.House),
                                //typeof(StructuredSpeech2.House.Structure.Room),
                                //typeof(StructuredSpeech2.House.Structure.X10Device),
                                //typeof(StructuredSpeech2.House.Structure.Zone),
                                //typeof(StructuredSpeech2.House.Devices.X10LampDevice),
                                //typeof(StructuredSpeech2.Tokens.Verbs.TokenTurn),
                                //typeof(StructuredSpeech2.Tokens.Nouns.TokenDeviceList)
                            };
        }
    }

This class wraps a token instance and additionally holds the start position and length of the parsed value. You’ll also notice code here that facilitates the serializing of tokens. The application often stores tokens and token results in the database and this code allows the types to be serialized and persisted.

Recall that the CommandProcessor class calls into the TokenManager which calls into each token, in turn, and compiles all the results into buckets.

TokenManager

The TokenManager holds a collection of tokens and manages giving each a shot at parsing the input. It, then, uses the start position and length properties on the results to organize then into a dictionary that can be used to determine a matching rule to be executed. The TokenManager class is listed, below.

TokenManager
[Export]
    public class TokenManager
    {
        [ImportMany(typeof(IParseToken))]
        private List<IParseToken> Tokens { get; set;}
 
        public Dictionary<int, List<TokenResult>> TokenizeInput(
            string input, Guid userId)
        {
            var results = new List<TokenResult>();
 
            try
            {
                foreach (var token in Tokens)
                {
                    results.AddRange(token.Parse(input, userId));
                }
            }
            catch (Exception e)
            {
                Logger.Log(e.Message);
            }
 
 
            CreateQuotedPhraseTokens(results, input);
 
            //arrange all token results by their start positions
            var buckets = new Dictionary<int, List<TokenResult>>();
 
            foreach (var result in results.OrderBy(r => r.Start))
            {
                if (!buckets.ContainsKey(result.Start))
                {
                    buckets[result.Start] = new List<TokenResult>();
                }
 
                buckets[result.Start].Add(result);
            }
 
            return buckets;
        }
 
        private void CreateQuotedPhraseTokens(
            List<TokenResult> results, string input)
        {
            int index = 0;
            List<WordInfo> words = new List<WordInfo>();
            string accumulator = "";
 
            for (index = 0; index < input.Length - 1; index++)
            {
                if (input[index] == ' ')
                {
                    words.Add(new WordInfo
                    {
                        Found = false,
                        Length = accumulator.Length,
                        Start = index - accumulator.Length,
                        Value = accumulator
                    });
 
                    accumulator = "";
                    continue;
                }
 
                accumulator += input[index];
            }
 
            accumulator += input[index];
 
            words.Add(new WordInfo
            {
                Found = false,
                Length = accumulator.Length,
                Start = (index + 1) - accumulator.Length,
                Value = accumulator
            });
 
            accumulator = "";
 
            foreach (var word in words)
            {
                var match = results.Where(r =>
                    word.Start >= r.Start && (word.Start + word.Length) <=
                    (r.Start + r.Length)).FirstOrDefault();
 
                if (match != null)
                {
                    if (accumulator.Length > 0)
                    {
                        results.Add(new TokenResult
                        {
                            Length = accumulator.Trim().Length,
                            Start = word.Start - 1 - accumulator.Trim().Length,
                            Token = new TokenQuotedPhrase { Value = accumulator.Trim() },
                            TokenType = typeof(TokenQuotedPhrase).ToString(),
                            Value = accumulator.Trim()
                        });
                        accumulator = "";
                    }
                }
                else
                {
                    accumulator += word.Value + " ";
                }
            }
 
            if (accumulator.Length > 0)
            {
                results.Add(new TokenResult
                {
                    Length = accumulator.Trim().Length,
                    Start = input.Length - 1 - accumulator.Trim().Length,
                    Token = new TokenQuotedPhrase { Value = accumulator.Trim() },
                    TokenType = typeof(TokenQuotedPhrase).ToString(),
                    Value = accumulator.Trim()
                });
            }
        }
    }

In lines 4 and 5, you can see that we’re using MEF to load all the Tokens into a collection. The TokenizeInput method loops through the tokens and passes the input to each. It then calls the CreateQuotedPhraseTokens method, which I’ll discuss shortly. Next, the results are iterated through and organized into a dictionary.

It’s quite possible the user will sometimes specify words or phrases that we have no token for. In fact, there are situations where we expect the user to do this. For example, when the user asks the system to create a reminder for them they will say something like, “Remind me to cook the golden goose next Friday”. We can parse out enough of the input to determine the users would like a reminder created and when they would like to be reminded. We don’t have tokens, however, to represent the “cook the golden goose” portion of the input. For this reason, after all the token classes have parsed out their results from the input, the TokenManager tokenizes the “left out” portions of the input as a TokenQuotedPhrase type. This allows us to use these values when locating rules to execute and inside those rules we can use that portion of the input as data.

The tokenization of the input is an important part of understanding what the user is asking for. It allows us to work with the input as a collection of objects as opposed to dealing with a string. The last part of the process is matching the tokens to a rule. We’ll look at how this is done next time.

3e06b1f1-96b4-4dd6-bbf3-e48053375f76|0|.0

Tags: .net, natural language processing

.Net | Natural Language Processing

Writing a Natural Language Parser in C# Part 3–CommandProcessor and ConversationContext

by Administrator 25. March 2012 06:51

This post is part of a series on creating a natural language processor in C#. The other entries in this series are:

Writing a Natural Language Parser in C# Part 1–Why?
Writing a Natural Language Parser in C# Part 2 - Architecture
Writing a Natural Language Parser in C# Part 4–Tokens
Writing a Natural Language Parser in C# Part 5 - Questions and Rules

The command processor is is the class that controls the flow of parsing a request and replying to it. Below is a full listing of the class.

CommandProcessor class
[Export]
    [PartCreationPolicy(CreationPolicy.NonShared)]
    public class CommandProcessor
    {
        [Import]
        private QuestionManager _questionManager { get; set; }
 
        public void ProcessCommand(string command, Guid userId,
            SmartHome.Global.ConversationMode mode,
            string address,
            Action<string> callback)
        {
            string localCommand = command.ToLower().Replace("'", "");
            var context = ServiceLocator.GetInstance<ConversationContext>();
            context.Init(userId, mode, address, callback);
            var tokenManager = ServiceLocator.GetInstance<TokenManager>();
            var buckets = tokenManager.TokenizeInput(command, userId);
            context.LogRequest(command, buckets);
 
            //before we check the tokens against rules, let's see if we match any questions
            Question question = null;
            List<Token> tokens = new List<Token>();
 
            _questionManager.CheckForMatchingQuestion(buckets, mode, userId,
                address, ref question, ref tokens);
 
            if (question != null)
            {
                question.ExecuteIfAnswered.Invoke(context,
                    question.State, tokens);
                
                _questionManager.RemoveQuestion(question);
                
                return;
            }
 
            RuleMethod ruleMethod = RuleManager.LocateMatchingRule(buckets, context);
 
            if (ruleMethod != null)
            {
                ruleMethod.Rule.Invoke(null, ruleMethod.PassIns);
            }
            else
            {
                context.Say("I didn't understand your request", null);
            }
        }
    }

First of all, you can see that MEF is being used as an IOC container. The only method in this class is the ProcessCommand method that takes the following parameters.

A string that is the command the user sent in, “What’s the weather” for example.
The user id. This is a Guid because we are using the Membership provider for authentication.
The conversation mode is specified, next, as an enumeration. The values in the enumeration specify what channel the user specified the command through (email, IM, etc.).
An address is specified as a string for the next parameter. We can tell from the mode what channel the user is on, but if they have multiple IM accounts or email addresses, we also need the address to figure out how to reply to them on the right account.
Last is a call back to be called after the command is processed. This is primarily here for commands sent to the system on a duplex WCF service. In order to reply to the user on this service, we need to be able to respond on the specified interface defined in the WCF service. This callback allows that.

To start off, we clean the command up a bit by making it lower case and removing apostrophes. Now, we create an instance of ConversationContext and initialize it. We’ll look at this class in just a minute. Next, we create the TokenManager and pass the user’s command to it. What is passes us back is a Dictionary<int, List<TokenResult>> where the int specifies a start position where tokens were found and the List contains all the tokens that were found there. We’ll look at the tokenization of the string in detail in the next part in this series.

Since the system saves all messages sent by the system or the user, we next log the users request. The buckets are passed in because they will be serialized and saved along with the command. When future requests come in, this will allow us to pull any past request from the database, de-serialize it and inspect it.

In some cases, the system will ask clarifying questions of the user. For example, if you as the system to remind you of something, it will need to know when to remind you and how. So, it will ask you these questions and wait for your reply. In the next code block we use the QuestionManager to check and see if the current request is actually the answer to a previously asked question.

If the command is not the answer to a question, we need to check and see if it matches one of the rules we have defined. Rules are how you specify sentences the system should recognize and what it should do when it receives that sentence. The RuleManager class compares our buckets with the rules to find a match. If one is found, it is invoked. Otherwise, the system replies that it did not understand the command.

Notice that the response is sent via the Say method on the ConversationContext class. Since this functionality completes the processing cycle, let’s look at that class next.

ConversationContext

As has been said before, the purpose of this class is to manage the conversation’s details such as the user it belongs to, it’s mode, address and history. Below is a listing of this class.

ConversationContext Class
[Export]
    [PartCreationPolicy(CreationPolicy.NonShared)]
    public class ConversationContext
    {
        public User ConversationUser { get; set; }
        public Conversation Conversation { get; set; }
        public List<ConversationHistory> ConversationHistory { get; set; }
        public SmartHome.Global.ConversationMode Mode { get; set; }
        public Action<string> Callback { get; set; }
        public string Address { get; set; }
 
        [Import]
        private IEventAggregator EventAggregator { get; set; }
 
        [Import]
        public QuestionManager QuestionManagerReference { get; set; }
 
        public void Init(Guid userId, SmartHome.Global.ConversationMode mode,
            string address, Action<string> callback)
        {
            ConversationUser = UserData.GetUserByUserId(userId);
            Conversation = ConversationData.GetConversationByUserAndMode(
                userId, mode, address);
            ConversationHistory = ConversationData.GetConversationHistory(
                Conversation.ConversationId);
            Mode = mode;
            Callback = callback;
            Address = address;
        }
 
        public void LogRequest(string request, object tag)
        {
            string tagString = SerializeTag(tag);
            var history = ConversationData.CreateConversationHistory(
                Conversation.ConversationId, request, tagString, tag, true);
            ConversationHistory.Add(history);
        }
 
        public void Say(string comment, object tag)
        {
            string tagString = string.Empty;
            tagString = SerializeTag(tag);
 
            EventAggregator.GetEvent<ReplyToChannelEvent>().Publish
                (new ReplyToChannelEventArgs
            {
              Mode = (SmartHome.Global.ConversationMode)Conversation.Mode,
              Reply = comment,
              TagString = tagString,
              Tag = tag,
              ConversationId = Conversation.ConversationId,
              Callback = Callback,
              UserId = ConversationUser.UserId,
              Address = Address
            });
        }
 
        private string SerializeTag(object tag)
        {
            string tagString = string.Empty;
 
            if (tag != null)
            {
                if (tag is IEntityWithChangeTracker)
                    (tag as IEntityWithChangeTracker).SetChangeTracker(null);
                var ser = new DataContractSerializer(tag.GetType());
                var ms = new MemoryStream();
                ser.WriteObject(ms, tag);
                tagString = Encoding.Default.GetString(ms.ToArray());
            }
 
            return tagString;
        }
 
        public void AskQuestion(string text, List<Token> expectedReplies, object state,
            Action<ConversationContext, object, List<Token>> executeOnAnswer)
        {
            Question question = new Question
            {
                Address = Address,
                ExecuteIfAnswered = executeOnAnswer,
                ExpectedReplys = expectedReplies,
                Mode = Mode,
                PosedDateTime = DateTime.Now,
                UserId = ConversationUser.UserId,
                State = state,
                QuestionText = text
            };
 
            QuestionManagerReference.AddQuestion(question);
 
            Say(text, null);
        }
    }

At the top of this class are instance variables that hold the instance’s state. The Init method initializes these variables.

Next is the LogRequest method we saw earlier that serializes the tag that is passed in (the buckets) and writes the request to the database.

The next method is Say(). We saw this method being used in the CommandProcessor class to reply to the user. It’s also used by the various rules for the same purpose. If you as the system about the weather, it will send the details back to you with the Say method. As you can see, I’m using the EventAggregator from the PRISM library to make the component of the system more loosely coupled. The say method serializes the tag parameter just like the LogRequest method does and then it raises an event asking someone to reply to a user. There are various classes responsible for communicating with the user on different channels. These classes are listening for this event and when they receive it, they will inspect the event args to see if they should respond. If so, they will send the response to the user and log the communication to the database.

Context

Looking at the listing, the next method is a helper that serializes objects into xml so they can be written to the database. This is a very important piece of functionality. When a rule is invoked by the system, it is passed an instance of the ConversationContext class. You can see the ConversationHistory property on this class which contains the entire history of the conversation. Most of these entries have a piece of context that helps to either explain why the system responded the way it did or to store a piece of information that may be useful later. For example, suppose you ask the system to list all the reminders it has for you. These will be returned to you in a numbered list. Suppose you’d like to delete the third item in the list. You could do that by telling the system to “delete 3”. How does the system know what was listed, much less which in the list was number three? It does this by walking backward through the conversation history until it finds a list that was stored in the tag. It then uses that list.

As another example, suppose you ask the system to remind you to meet with Phil. The system will ask you what time you would like to be reminded. You reply that you’d like to be reminded at 4:00 pm. How does the system know what you’re talking about? You guessed it. By storing the reminder as a tag. This is a powerful idea and allows the system to have a stateful conversation via a stateless protocol in a similar way that ASP.Net does with its serialized state.

The last method in the ConversationContext class is AskQuestion(). This is similar to Say() in that it also raised the event to have the reply sent back to the user. However, it also adds the question to a collection maintained by the QuestionManager.

Next time, we’ll look at the TokenManager and how the commands are tokenized.

3185132a-5803-4bf7-946b-1f347b11f230|0|.0

Tags: natural language processing, .net

.Net | Natural Language Processing

Writing a Natural Language Parser in C# Part 2 - Architecture

by Administrator 18. March 2012 11:16

This post is part of a series on creating a natural language processor in C#. The other entries in this series are:

Writing a Natural Language Parser in C# Part 1–Why?
Writing a Natural Language Parser in C# Part 3–CommandProcessor and ConversationContext
Writing a Natural Language Parser in C# Part 4–Tokens
Writing a Natural Language Parser in C# Part 5 - Questions and Rules

In our last post we discussed why one might be interested in building and using a natural language processor in a business or home project. This week, I’d like to look at the architecture of the processor I’ve written. This will be a high-level look at the various pieces of the system, the flow of processing a single sentence and how each piece contributes to the process.

An Activity Diagram

Below is an activity diagram depicting the interaction of the major parts of the system and how they work together to process a sentence sent to the system by the user.

The steps involved in this process are as follows:

The string the user submits, along with a User ID and other bits of information are submitted to the Command Processor.
The command processor creates an instance of a conversation context. This is a very important part of the system as a whole. It keeps track of what user made the request, what method was used to communicate the request (email, IM, etc.) and has a history of all statements that have occurred in both directions for the duration of the conversation.
The system contains a collection of Tokens that know how to inspect the input for certain strings or conditions. They generate a TokenResult instance for each interesting piece of the statement and records where the interesting part begins in the string and how long it is. The token result also records a strong type that indicates the kind of thing that was found such as a certain phrase, a date or the name of something it knows about.
After all the tokens have had a chance to process the string, the resulting TokenResults all exist in a single collection. This collection is then organized into buckets where each bucket corresponds to a start position in the string. For example, all interesting things found to have begun at position zero would be in a bucket together. How can there be more than one token result for the same phrase? Well consider that the string contained a numeral “1”. This could represent an integer, a long, a decimal, and ordinal (think “first” as in the first day of the month or first day of the week), etc,
Rules are methods that return void and have any number of parameters which are each a type of token. These rules are all defined in classes that are marked with a particular interface and are obtained via reflection. After all the token result instances have been organized into buckets, each of these methods is inspected and its parameters are compared to the contents of each bucket, in order, to see if a match for the parameter is found in the corresponding bucket.
Once a matching rule is found, it is executed by passing in the conversation context and all the matching tokens. The context can be used from within the method to inspect the history of the conversation and also to send responses back to the user.

An Example

Lets’ look at a simple example. Even if this example does not make complete sense to you right now, as we look into each piece of the system in more detail, it will become clear to you.

Let’s say the user sends in a request, “What’s the weather”. Once the tokens have all had a chance to look at this string, we will have a collection of token results. In fact, we will have two results. The first will say that “What’s the” can be tokenized into a TokenList beginning at position 0 in our string. The second will say that the remainder of the string can be tokenized into a TokenWeather beginning at position 10 (I know this seems like an incorrect position, but I will explain in a future post).

Now, these two tokens will be put into a couple of buckets and the system will begin to go through all the defined rules. Once of these rules has a signature like this:

Weather Rule
public static void GetWeather(ConversationContext cContext, TokenList list, TokenWeather weather)

Since TokenList matches what’s in our first bucket and TokenWeather matches what’s in the second, this will be the matching rule and will be executed.

Threading

It should be noted that the entire process diagrammed above executes on a single thread. However, much like a web server, each request is handled on a separate thread that is initiated by classes that listen on different protocols.

b4ca943f-a18d-4623-8055-53072235acd4|0|.0

Tags: .net, natural language processing

.Net | Natural Language Processing

Writing a Natural Language Parser in C# Part 1–Why?

by Administrator 9. March 2012 11:35

This post is part of a series on creating a natural language processor in C#. The other entries in this series are:

Writing a Natural Language Parser in C# Part 2 - Architecture
Writing a Natural Language Parser in C# Part 3–CommandProcessor and ConversationContext
Writing a Natural Language Parser in C# Part 4–Tokens
Writing a Natural Language Parser in C# Part 5 - Questions and Rules

Recently, I did a refactor of several key pieces of the natural language processor I created for my smart home. Spending the time refocusing on how it works convinced me to write a series of posts explaining how it works and how it was built. In this first installment, I'll look at why an NLP engine is a useful piece of software and other things it could be used for.

Originally Written for Smart House

Obviously, I created this engine for use in my smart house. As I've said many times, the original idea was inspired by similar work done by Ian Mercer. By making this a part of my smart house, I can communicate with the system to request information and ask it to carry out work for me using natural language. What's more, since the interface to my system is nothing more than text, I can communicate through any channel that supports text: email, instant messaging, SMS, etc. By using text to speech and speech recognition functionality available on multiple platforms, I can even have a conversation with the system through speech.

Is There Room for NLP in Business

Is there a place for this interface in business? I think so. UX technologies are changing rapidly. Touch is an expected interface in most devices, now. Certainly mobile phones are expected to support touch, as well as tablet computers. The Kinnect introduced motion gestures for gaming and this method of interacting with systems is coming to PCs. The point is that interfaces not involving a keyboard and mouse are getting more common-place and natural language certainly has a place at the table.

Some examples of business use might include:

An ad-hoc query system that lets users ask for what they want from the data source using sentences.
Personal Assistant software that could ask the user for direction on what to do with emails or documents and allow the user to specify answers in natural language.
Conference room software that controls displays and / or whiteboards via natural language requests.

I've found working with this technology to be a lot of fun and the results have been satisfying. I invite all of you to follow this series to see how it all works and to contribute your own ideas.

In part 2, we'll look at the architecture of the system. From there, we'll take deep dives into the individual parts.

32d2814c-ad67-44fc-8863-59fd21a9b320|0|.0

Tags: .net, natural language processing

.Net | Natural Language Processing

Smart House Alerts

by mgordon 25. August 2011 09:15

Bad weather on the way? My Smart House let's me know. I have an appointment this afternoon? It lets me know. A favorite blog has an update? Yep.

I decided early on that I wanted my smart house to notify me of some things. As a result, the time I used to spend checking the weather site, checking for blog updates, checking my calendar is now free time. These things are pushed to me, now, by my smart home.

The system has a series of alerts that do little more than poll various end-points or database records on timers. When conditions are such that I need to be notified, I get a message.

How does the application know how to reach me? Well, a couple of ways. In my system, there is a concept of a communication channel. This channel is associated with a particular user of the system and a certain mode of communication (IM, SMS, email, more to come). When I log into IM, for example, the system knows I'm online and that channel is marked as being open. If an alert occurs, it knows I can be reached on that channel.

For other channels, such as email and SMS, the channel always remains open. For these, I can configure the application to notify me on that channel or not depending on the alert.

IM

I use the XMPP protocol for IM communication with my Smart House. This allows me to use Google Talk or Jabber to get messages from or send messages to the system. I have taken a dependency on the the XMPP SDK from Ags. It allows me to connect to the network, to be notified when any of the Smart House's buddies go on or off line, and to send and receive messages.

Connecting is simple. First, instantiate and configure a connection.

Connect 
to XMPP

Conn = new XmppClientConnection(ConfigurationManager.AppSettings["XmppServer"]);
            Contacts = null;
            Contacts = new List<Contact>();
            Conn.EnableCapabilities = true;
            Conn.ClientSocket.ConnectTimeout = 60000;
            Conn.AutoResolveConnectServer = 
false;
            Conn.ConnectServer = "talk.google.com";
            Conn.Port = int.Parse(ConfigurationManager.AppSettings["XmppPort"]);
            Conn.UseStartTLS = false;
            Conn.UseSSL = true;

Then, add some event handlers.

Set 
Event Handlers

Conn.OnError += conn_OnError;
            Conn.OnMessage += 
conn_OnMessage;
 
            Conn.OnPresence += 
_conn_OnPresence;
 
            Conn.OnLogin += s =>
                                {
                                    IsConnected 
= true;
                                    var 
p = new Presence(ShowType.chat, "Online") { Type = PresenceType.available };
                                    Conn.Send(p);
                                };
 
            Conn.OnAuthError += (s, e) => StructuredSpeech2.Logging.Logging.Log("XMPP 
Authentication Error");
 
            Conn.OnRegisterError += (s, e) => 
StructuredSpeech2.Logging.Logging.Log("XMPP Register Error: " + e.InnerXml);
            Conn.OnSocketError +=
                (s, e) =>
                StructuredSpeech2.Logging.Logging.Log("XMPP 
Socket Error: " + e.Message + " :: " 
+ e.StackTrace);
 
            Conn.OnStreamError += (s, e) => 
StructuredSpeech2.Logging.Logging.Log("XMPP Stream Error: " + 
e.InnerXml);

Finally, connect.

Connect

try
            {
                Conn.Open(ConfigurationManager.AppSettings["XmppUsername"],
                       ConfigurationManager.AppSettings["XmppPassword"]);
            }
            catch
            {
                Initialize();
            }

Notice that many of the event handlers we're handling have to do with various things that can go wrong. There are logged for investigation later. The OnLogin event fires when a connection to the network has been established. Here, I'm setting the system's status to online and available.

When a login fails, we recurse and try again.

The OnPresence event fires when the presence status of a user has changed such as their becoming available or signing off. The event args let us know the buddy and what their new presence value is. When I handle this event, I evaluate the new presence value and then do two things. I keep a collection of all online contacts so I can quickly broadcast a message. The first thing I do when I get a presence event is to update this collection by adding or removing the contact as appropriate. The second thing I do is update the state of the communication channel for the user the buddy represents.

The OnMessage event fires when a message has been received from a buddy. The event arguments specify the the buddy the message is from and the text of the message. When a message is received, I check to see that the buddy is a user on the system and if they are, I process the message with the Language Processor. If the user is not found, a response is sent to the buddy stating they are not a known user and cannot interact with the system.

Finally, I can send a message to any online buddy by calling the send method on the connection class. As with the the previous discussions about the Speech Processor, the entire conversation is logged and used in processing the text sent in a particular message. In the case of IM, the conversation starts when the buddy connects to the network and ends when they disconnect. When a message has been received, the Language Processor processes it and then uses this send method to reply to the appropriate user. Alerts are send in the same way.

The bottom line is that I can send commands to my house via IM and have it act appropriately or it can send me messages to alert me if my attention is needed. A true conversational interface.

Email

I'm using OpenPop to provide the functionality need to check and manipulate emails on the POP server. My Smart House has it's own email account which it polls on a timer. Each time, all messages are pulled from the email account, processed and then deleted. OpenPop allows the system to connect to the pop account and pull down all the messages. First, the connection object is created and configured.

Connect 
to POP3 account

_client = new Pop3Client();
                _client.Connect(_popEmailServer, 
_popEmailPort, _popEmailUseSsl);
                _client.Authenticate(_popEmailUname, 
_popEmailPassword);
                _client.Reset();

Next, the messages are pulled down and processed.

Process 
Email Messages

_emailCheckTimer.Stop();
 
            try
            {
                ConnectClient();
 
                if 
(!_client.Connected)
                    return;
 
                int messageCount = _client.GetMessageCount();
 
                var messages = new List<Message>(messageCount);
 
                for (int i = 
1; i <= messageCount; i++)
                {
                    messages.Add(_client.GetMessage(i));
                    _client.DeleteMessage(i);
                }
 
                List<Message> staticMessages = messages;
 
                var enc = new 
ASCIIEncoding();
 
                foreach (Message msg in 
staticMessages)
                {
                    string request = 
enc.GetString(msg.FindFirstPlainTextVersion().Body);
                    string fromAddress = 
msg.Headers.From.Address;
 
                    User user = UserRepository.GetUserByEmail(fromAddress);
 
                    if (user == null)
                    {
                        SendResponse("I don't 
know this email address.", msg.Headers.From.Address, 
msg.Headers.Subject);
                        return;
                    }
 
                    if (_client != null)
                    {
                        _client.Disconnect();
                        _client.Dispose();
                    }
 
 
                    CommandProcessor.ProcessCommand(request, user, 
ConversationMode.Email, fromAddress);
                }
 
            }
            catch (Exception ex)
            {
                StructuredSpeech2.Logging.Logging.Log("Checking 
mail " + ex.Message + ex.StackTrace);
            }
            finally
            {
                if (_client.Connected)
                    _client.Disconnect(); ;
 
                _client.Dispose();
            }
 
            _emailCheckTimer.Start();

For sending emails, I use the SmtpClient class in the .Net Framework. See its documentation for usage.

SMS

Once email has been implemented, SMS is easy. I use SMS for outgoing messages, only. Most cell phone carriers allow SMS messages to be send via email. For example, an email sent to an address such as 10digitnumber@txt.att.net, will be received as an SMS message on the AT&T network phone having that 10 digit number. For this reason, I use exactly the same approach to send SMS messages as I do for sending emails.

bdcf0873-4cde-46bb-8817-59da1e9fa753|0|.0

Tags: .net, natural language processing, smart home

.Net | Smart Home | Natural Language Processing

Letting My Smart Home Keep a TODO List for Me

by mgordon 25. August 2011 05:26

In my last post, I summarized how I created a Natural Language Processor around which I am building a Home Automation solution. I want my smart home to be able to more than just turn things on an off, so I have been adding pieces of functionality that will automate more than that. The first piece of functionality I added was the ability to create and manage items on a TODO list.

Add the Tokens

If you'll recall from my last post, the language processor contains several Token classes that know how to parse out and tokenize words or phrases. These classes are the building blocks which are used to define the system's vocabulary. For the TODO list functionality, we need to define Token classes for the following:

"todo"
"list", "get", "show"
"create"
"delete"
"mark"
"done"
"for", "on"
dates and times

The language processor will parse the command we specify into a list of tokens that will be compared to the parameter lists of our command methods. When a match is found, that method is called. We need to define our command methods, next.

Create the Command Methods

In the end, we are wrapping little more than CRUD operations for a TODO list table in the database. One example of a command method is below.

Code Snippet

public static void CreateNewToDoItem(ConversationContext cContext, TokenCreate create, TokenToDo todo, TokenQuotedPhrase phrase)
{
var repos = new ToDoRepository();
var newTodo = repos.CreateNewTodo((string)phrase.Value, null, cContext.ConversationUser.UserId);
cContext.Say("Added ToDo \"" + phrase.Value + "\"", newTodo);
}

This method takes a token for "create", one for "todo" and another for a quoted phrase which is any phrase found between quotes. So an example of a command that might result in this method's being called would be

create a new todo "Call the hardware store about paint"

You can see that when the method is executed, a new record is created for the todo item. The first parameter is the conversation context. This context contains information such as what channel the communication is on (IM, email, etc.), the user being conversed with and a list of incoming and outgoing messages in this conversation. This is important in some cases. Consider when the user wants to delete a todo item. We could allow them to specify the item by its text, but that could be error prone and a lot of typing. It'd be better if they could specify only a number. So, in my implementation, the user requests a list of their items and what is returned is a numbered list. The user can then say, "delete 2" to remove the second item.

How does the system know which item was number 2? When the list is generated, it's stored in the context such that 2 corresponds to a particular item. From that point on, it doesn't matter what else happens to the records in the database because 2 doesn't just mean the second item, but the item that was second in that list at that point in time. This is possible because of the context.

The reply to the user gets sent to the right user through the right channel because of the context. In this implementation, we don't have to worry about these details in the command method, the context keeps it sorted out for us.

By repeating the process of creating the necessary tokens to build up our vocabulary and then creating rules to match, functionality is layered onto the system to allow the user to associate a due date and time with the item,

create new todo "call the insurance man" for tomorrow 1:30

5eef4c44-a08b-4156-af64-88804df10889|0|.0

Tags: .net, smart home, natural language processing

.Net | Smart Home | Natural Language Processing

Presenting this Saturday at Atlanta Code Camp

Writing a Natural Language Parser in C# Part 5 - Questions and Rules

What is a Rule

Finding the matching Rule

Questions

Writing a Natural Language Parser in C# Part 4–Tokens

Anatomy of A Token

TokenResult

TokenManager

Writing a Natural Language Parser in C# Part 3–CommandProcessor and ConversationContext

ConversationContext

Context

Writing a Natural Language Parser in C# Part 2 - Architecture

An Activity Diagram

An Example

Threading

Writing a Natural Language Parser in C# Part 1–Why?

Originally Written for Smart House

Is There Room for NLP in Business

Smart House Alerts

IM

Email

SMS

Letting My Smart Home Keep a TODO List for Me

Add the Tokens

Create the Command Methods

About the author

RecentPosts

Month List

What is a Rule

Finding the matching Rule

Questions

Anatomy of A Token

TokenResult

TokenManager

ConversationContext

Context

An Activity Diagram

An Example

Threading

Originally Written for Smart House

Is There Room for NLP in Business

IM

Email

SMS

Add the Tokens

Create the Command Methods

About the author

RecentPosts

Tag cloud

Month List