Phone dialing conversational agent

Introduction

This blog post proclaims the first committed project in the repository ConversationalAgents at GitHub. The project has designs and implementations of a phone calling conversational agent that aims at providing the following functionalities:

  • contacts retrieval (querying, filtering, selection),
  • contacts prioritization, and
  • phone call (work flow) handling.
  • The design is based on a Finite State Machine (FSM) and context free grammar(s) for commands that switch between the states of the FSM. The grammar is designed as a context free grammar rules of a Domain Specific Language (DSL) in Extended Backus-Naur Form (EBNF). (For more details on DSLs design and programming see [1].)

    The (current) implementation is with Wolfram Language (WL) / Mathematica using the functional parsers package [2, 3].

    This movie gives an overview from an end user perspective.

    General design

    The design of the Phone Conversational Agent (PhCA) is derived in a straightforward manner from the typical work flow of calling a contact (using, say, a mobile phone.)

    The main goals for the conversational agent are the following:

    1. contacts retrieval — search, filtering, selection — using both natural language commands and manual interaction,
    2. intuitive integration with the usual work flow of phone calling.

    An additional goal is to facilitate contacts retrieval by determining the most appropriate contacts in query responses. For example, while driving to work by pressing the dial button we might prefer the contacts of an up-coming meeting to be placed on top of the prompting contacts list.

    In this project we assume that the voice to text conversion is done with an external (reliable) component.

    It is assumed that an user of PhCA can react to both visual and spoken query results.

    The main algorithm is the following.

    1) Parse and interpret a natural language command.

    2) If the command is a contacts query that returns a single contact then call that contact.

    3) If the command is a contacts query that returns multiple contacts then :

    3.1) use natural language commands to refine and filter the query results,

    3.2) until a single contact is obtained. Call that single contact.

    4) If other type of command is given act accordingly.

    PhCA has commands for system usage help and for canceling the current contact search and starting over.

    The following FSM diagram gives the basic structure of PhCA:

    "Phone-conversational-agent-FSM-and-DB"

    This movie demonstrates how different natural language commands switch the FSM states.

    Grammar design

    The derived grammar describes sentences that: 1. fit end user expectations, and 2. are used to switch between the FSM states.

    Because of the simplicity of the FSM and the natural language commands only few iterations were done with the Parser-generation-by-grammars work flow.

    The base grammar is given in the file "./Mathematica/PhoneCallingDialogsGrammarRules.m" in EBNF used by [2].

    Here are parsing results of a set of test natural language commands:

    "PhCA-base-grammar-test-queries-125"

    using the WL command:

    ParsingTestTable[ParseJust[pCALLCONTACT\[CirclePlus]pCALLFILTER], ToLowerCase /@ queries]
     

    (Note that according to PhCA’s FSM diagram the parsing of pCALLCONTACT is separated from pCALLFILTER, hence the need to combine the two parsers in the code line above.)

    PhCA’s FSM implementation provides interpretation and context of the functional programming expressions obtained by the parser.

    In the running script "./Mathematica/PhoneDialingAgentRunScript.m" the grammar parsers are modified to do successful parsing using data elements of the provided fake address book.

    The base grammar can be extended with the "Time specifications grammar" in order to include queries based on temporal commands.

    Running

    In order to experiment with the agent just run in Mathematica the command:

    Import["https://raw.githubusercontent.com/antononcube/ConversationalAgents/master/Projects/PhoneDialingDialogsAgent/Mathematica/PhoneDialingAgentRunScript.m"]

    The imported Wolfram Language file, "./Mathematica/PhoneDialingAgentRunScript.m", uses a fake address book based on movie creators metadata. The code structure of "./Mathematica/PhoneDialingAgentRunScript.m" allows easy experimentation and modification of the running steps.

    Here are several screen-shots illustrating a particular usage path (scan left-to-right):

    "PhCA-1-call-someone-from-x-men"" "PhCA-2-a-producer" "PhCA-3-the-third-one

    See this movie demonstrating a PhCA run.

    References

    [1] Anton Antonov, "Creating and programming domain specific languages", (2016), MathematicaForPrediction at WordPress blog.

    [2] Anton Antonov, Functional parsers, Mathematica package, MathematicaForPrediction at GitHub, 2014.

    [3] Anton Antonov, "Natural language processing with functional parsers", (2014), MathematicaForPrediction at WordPress blog.

    Advertisements

    Creating and programming domain specific languages

    Introduction

    In this blog post I will provide links to documents, packages, blog posts, and discussions for creating and utilizing Domain Specific Languages (DSLs). I have discussed a few DSLs in previous blog posts (linked below). This blog post provides a more general, higher level view on the application and creation of DSLs. The concrete examples are with Mathematica, but the steps are general and can be done with any programming languages and tools.

    When to apply DSLs

    Here are some situations for applying DSLs.

    1. When designing conversational engines.
    2.  When there are too many usage scenarios and tuning options for the developed algorithms.
      • For example, we have a bunch of search, recommendation, and interaction algorithms for a dating site. A different, User Experience Department (UED) designs interactive user interfaces for these algorithms. We make a natural language DSL that invokes the different algorithms according to specified outcomes. With the DSL the different designs produced by UED are much easily prototyped, implemented, or fleshed out. The DSL also gives to UED easier to understand view on the functionalities provided by the algorithms.
    3. When designing an API for a collection of algorithms.
      • Just designing a DSL can bring clarity of what signatures should be in the API.
      • NIntegrate‘s Method option was designed and implemented using a DSL. See this video between 25:00 and 27:30.

    Designing DSLs

    1. Decide what kind of sentences the DSL is going to have.
      • Are natural language sentences going to be used?
      • Are the language words known beforehand or not?
    2. Prepare, create, or accumulate a list of representative sentences.
      • In some cases using Morphological Analysis can greatly help for coming up with use cases and the corresponding sentences.
    3. Create a context free grammar that describes the sentences from the previous step. (Or a large subset of them.)
      • At this stage I use exclusively Extended Backus-Naur Form (EBNF).
      • In some cases the grammar terminals are not know at the design stage and have to retrieved in some way. (From a database or though natural language processing.)
      • Some conversational engine systems allow or require to the grammar specification to be done in XML. I would still do BNF and then move to XML
        •  It is not that hard to write a parser-and-interpreter that translates BNF into XML. See the end of this blog post for that kind of translation of BNF into OMPL.
    4. Program parser(s) for the grammar.
      • I use most of the time functional parsers.
      • The package FunctionalParsers.m provides a Mathematica implementation of this kind of parsing.
      • The package can automatically generate parsers from a grammar given in EBNF. (See the coding example below.)
      • I have programmed versions of this package in R and Lua.
    5. Program an interpreter for the parsed sentences.
      • At this stage the parsed sentences are hooked to the algorithms of the problem domain.
      • The package FunctionalParsers.m allows this to be done fairly easy.
    6. Test the parsing and interpretation.

    See the code example below illustrating steps 3-6.

    Introduction to using DSLs in Mathematica

    1. This blog post “Natural language processing with functional parsers” gives an introduction to the DSL application in Mathematica.
    2. This detailed slide-show presentation “Functional parsers for an integration requests language grammar” shows how to use the package FunctionalParsers.m over a small grammar.
    3. The answer of the MSE question “How to parse a clojure expression?” gives a good introduction with a simple grammar and shows both direct parser programming and automatic generation from EBNF.

    Advanced example

    The blog post “Simple time series conversational engine” discusses the creation (design and programming) of a simple conversational engine for time series analysis (data loading, finding outliers and trends.)

    Here is a movie demonstrating that conversational engine: http://youtu.be/wlZ5ANglVI4.

    Other discussions

    1. A small part, from 17:30 to 21:00, of the WTC 2012 “Spatial Access Methods and Route Finding” presentation shows a DSL for points of interest queries.
    2. The answer of the MSE question “CSS Selectors for Symbolic XML” uses FunctionalParsers.m .
    3. This Quantile Regression presentation is aided by the  “Simple time series conversational engine” mentioned above.

    Coding example

    This coding example demonstrates steps 3-6 discussed above.

    EBNF-and-parsers-for-LoveFood

    Interpreters-and-parsing-for-LoveFood

    Simple time series conversational engine

    Introduction

    In this blog post I am going to discuss the creation (design and programming) of a simple conversational engine for time series analysis. The conversational engine responds to commands for:
    1. loading time series data (weather data, stock data, or data files),
    2. finding outliers,
    3. analysis by curve fitting,
    4. plotting, and
    5. help and state changes.

    This blog post is related to the blog post [1] and uses the package with functional parsers [2] and the Quantile regression package [3].

    I programmed this engine ten months ago and here is link to a movie that demonstrates it, [4]: https://www.youtube.com/watch?v=wlZ5ANglVI4 .

    A package with all of the code of the conversational engine can be downloaded from GitHub, [12] and executed with Import:


    Import["https://raw.githubusercontent.com/antononcube/MathematicaForPrediction/master/Examples/SimpleTimeSeriesConversationalEngine.m"]

    More about functional parsers, which were essential for the building of the conversational engine, can be read in “Functional parsers” by Fokker, [5].

    Design of the conversational engine

    The conversational engine is a finite state machine. It has a command recognizer state and command application state. The switching between the states is done upon completion states functions. The recognized commands are English sentences. Some of the sentences include Mathematica code.

    Let use describe the structure of the conversational engine.

    States

    1. Acceptor state
    The Acceptor state parses and recognizes commands. If the given command is successfully parsed then the parsing result is given to the Transducer state. Otherwise a message “Unknown command” is emitted and no state change is made (i.e.we are still in the Acceptor state).

    2. Transducer state
    Interprets the parsed a command by the Acceptor state. This state emits different messages according to the loaded data and accumulated graphics objects.

    The states are named according to the classification given in the Wikipedia article about finite-state machines, [5]. According to that classification the conversational engine is a Mealy machine.

    Responses

    The results of the applied time series analysis are graphical. The Transducer state accumulates the graphs of the commands and displays them with the data. The conversational engine responses have a spoken part and a graphics part. The responses have at least a spoken part. The graphics part can omitted.

    Commands

    The weather data commands can be for temperature, wind speed, and pressure over a specified city. For example, “load temperature of Atlanta” or “load the Chicago wind speeds”.

    The financial data commands can be for stock price or trading volume. For example, “load trade volume of NYSE:GOOG” or “load stock price of NYSE:APPL”.

    The weather and stocks data loading commands do not take time period, they take only city and company specifications for WeatherData and FinancialData respectively.

    The loading of data files is done with commands like “load file ‘~/LogDataWithSkewedNoise.csv’ “.

    The time series analysis commands we consider are: curve fitting by a list specified functions, finding regression quantiles, and finding outliers. For example, “compute least squares fit of {1,x,Sin[x/10^6]}”, “compute 5 regression quantiles”, “find top outliers”.

    The graphics commands are “plot data”, “plot(s) joined”, “plot(s) not joined”, “clear graphics”.

    In addition, the conversational engine takes global, service commands like “help”, “all commands”, “start over’, etc.

    Grammar specification

    In order to respond to the commands that are English sentences we have to be able to parse these sentences into concrete state or message specifications. This means that we have to define the grammatical structures of the command sentences and the words in them.

    This section describes the grammar of the commands using Extended Backus-Naur Form (EBNF). The package FunctionalParsers.m, [2], has Mathematica functions that generate parsers from EBNF of a grammar (see [9] and the next section). The resulting parsers are used in the conversational engine described above.

    Commands for loading data explanations

    Let us explain the derivation and rationale of the grammar rules for the data loading commands. (I am not going to describe all the language considerations and decisions I have made for the commands grammar. These decisions can be traced in the EBNF grammar specification.)

    We want to parse and interpret commands like:
    1. load data file ‘timeTable.csv’ ,
    2. load temperature of Atlanta ,
    3. load the wind speeds of Chicago ,
    4. load the stock price of NYSE:APPL ,
    5. load trading volume of NYSE:GOOG .

    We can see that we have three different types of data loading commands: for files, for weather data, and for financial data. Each of these commands when parsed would be easy to interpret using Mathematica’s functions Import, WeatherData, and FinancialData respectively. Note that — because we want to keep the grammar simple — for the weather and financial data there is no time period specification. For the weather data we are going to load data for the last 60 days; for the financial data for the last 365 days. Also, for simplicity, we are not going to consider data loading commands that start with the phrases “get”, “get me”, “please load”, etc.

    To this end the general load data command structure is:

    DidacticLoadDataGrammarRules

    Note that in the grammar rules above some of the words are optional; the optional words are put within square brackets. With the first rule we have separated the file loading from the weather and financial data loading. The file loading is further specified with rule 2. Rule 3 separates the preamble of the weather and financial data loading commands from the data specification. The latter is partitioned in rule 4. Rule 5 gives all of the possible data type requests for the weather data: temperature, pressure, and wind speed. Rule 6 gives the two possible types for financial data requests: stock price and trade volume. The file name, city, and company specifications are left out, but the rules for them are be easy to formulate.

    The command grammar used in the conversational engine uses additional data loading definitions and allows “reverse” data load commands like: “load the Chicago wind speeds”.

    Full grammar specification

    In this sub-section the full grammar specification is given. Note that some parts of the commands are specified to be dropped from the parsing results using the symbols “\[RightTriangle]” and “\[LeftTriangle]”. (For example ” ‘trade’ \[RightTriangle] ‘volume’ ” means “parse the sequence of words ‘trade’ ‘volume’ and return ‘volume’ as a result”.) The specification ‘_LetterString’ is an implementation shortcut for matching words and identifiers with the package FunctionalParsers.m, [2].

    TimeSeriesGrammarEBNF

    The rules were simplified for clarity, the actual conversational engine code can be retrieved, [8].

    The grammar specified above takes complicated commands like “find regression quantiles over temperature of Atlanta”.

    (In certain cases I prefer reading grammars in EBNF using Emacs and ebnf-mode.el, [7].)

    Parsers for the grammar

    Using the grammar specification [8] and the package FunctionalParsers.m, [2], we can generate the parsers for that grammar. A detailed description of the parser generation process is given in [9].

    Here is the generation step:


    tokens = ToTokens[timeSeriesEBNFCode];
    res = GenerateParsersFromEBNF[tokens];
    res // LeafCount

    Out[4]= 3069

    The generation step creates a set of parsers:

    In[16]:= Magnify[Shallow[res[[1, 1, 2]], 6], 0.8]

    TimeSeriesGrammarEBNFParseTree

    Here are the parsing results returned by the “master” rule pTSCOMMAND:
    TableOfParsingCommands1

    Here is another list for the engine’s “service” commands:
    TableOfParsingCommands2

    And see their parsing outcome using the function ParsingTestTable provided by FunctionalParsers.m:

    questions = {"load data file '~/example.csv'",
    "load file '~/anotherExample.csv'"};
    ParsingTestTable[ParseShortest[pLOADFILECOMMAND], questions]

    LoadDataFileParseTable

    Note that the parser takes commands with Mathematica expressions parts if those expressions are written without spaces:

    questions = {"least squares fit with x+Sin[x]"};
    ParsingTestTable[ParseShortest[pTSCOMMAND], questions]

    LeastSquaresFitParseTable

    This type of commands are specified with the grammar rule:

    = ( ‘least’ , ‘squares’ , [ ‘fit’ ] , [ ‘with’ | ‘of’ ] ) \[RightTriangle] ‘_String’ ;

    Interpreters (for the parsers)

    Next we have to write interpreters for the parsing results. Note that the parsing results are Mathematica expressions with heads that hint to the semantic meaning behind the parsed commands. Since we are viewing the conversational engine as a finite state machine we can say that for each parsing result we have to write a function that “reacts” to result’s head and content. This is a fairly straightforward process very similar to the one described by the Interpreter design pattern, [10].

    A package with all of the code of the conversational engine can be downloaded from GitHub, [12]. The interpreters code can be found in the section “Interpreters”.

    The conversational engine programming

    The conversational engine was programmed using Mathematica’s dynamic evaluation functions and mechanisms. The implementation follows the Absorber and Transductor state design described above in the section “Design of the conversational engine”.

    The engine has three panels: for command input, for spoken output, and for graphical output. It is fully demonstrated with the movie “Time series conversational engine” posted on YouTube, [4].

    As it was mentioned in the introduction the engine can be run using Import:

    Import[“https://raw.githubusercontent.com/antononcube/MathematicaForPrediction/master/Examples/SimpleTimeSeriesConversationalEngine.m”%5D

    SimpleTimeSeriesConversationalEngineExample

    Future plans

    The engine can be extended in many directions depending on the final goals for it.

    One must have extension is the ability to take time period specifications for the weather and financial data.

    The time series analysis can be extended with more detailed analysis using functions like TimeSeriesModelFit or heteroscedasticity analysis using multiple regression quantiles, [11].

    A third set of extensions is the ability to load additional kinds of data, like, the evolutions of countries populations or gross domestic products.

    References

    [1] Anton Antonov, Natural language processing with functional parsers, blog post at WordPress, (2014).

    [2] Anton Antonov, Functional parsers Mathematica package, source code at GitHub, https://github.com/antononcube/MathematicaForPrediction, package FunctionalParsers.m, (2014).

    [3] Anton Antonov, Quantile regression Mathematica package, source code at GitHub, https://github.com/antononcube/MathematicaForPrediction, package QuantileRegression.m, (2013).

    [4] Anton Antonov, Time series conversational engine, a YouTube movie.

    [5] Wikipedia entry: Finite-state Machine, http://en.wikipedia.org/wiki/Finite-state_machine .

    [6] Jeroen Fokker, Functional parsers, In: Advanced Functional Programming, Tutorial text of the First international spring school on advanced functional programming techniques in Båstad, Sweden, may 1995. (Johan Jeuring and Erik Meijer, eds). Berlin, Springer 1995 (LNCS 925), pp. 1-23. http://www.staff.science.uu.nl/~fokke101/article/parsers/index.html .

    [7] Jeramey Crawford, Extended Backus-Naur Form Mode, ebnf-mode.el, emacs LISP at Github, https://github.com/jeramey/ebnf-mode .

    [8] Anton Antonov, Time series conversational engine grammar in EBNF, TimeSeriesConversationalEngineGrammar.ebnf at the MathematicaForPrediction project at GitHub.

    [9] Anton Antonov, Functional parsers for an integration requests language, PDF document at GitHub, https://github.com/antononcube/MathematicaForPrediction/tree/master/Documentation , (2014).

    [10] Erich GammaTaligent, Richard Helm, Ralph Johnson, John Vlissides, Design patterns: elements of reusable object-oriented softwareAddison-Wesley Longman Publishing Co., Inc. Boston, MA, USA ©1995, ISBN:0-201-63361-2, http://en.wikipedia.org/wiki/Design_Patterns .

    [11] Anton Antonov, Estimation of conditional density distributions, “Mathematica for prediction algorithms” blog at WordPress, (2014).

    [12] Anton Antonov, Simple Time Series Conversational Engine Mathematica package, SimpleTimeSeriesConversationalEngine.m at the MathematicaForPrediction project at GitHub.

    Natural language processing with functional parsers

    Natural language Processing (NLP) can be done with a structural approach using grammar rules. (The other type of NLP is using statistical methods.) In this post I discuss the use of functional parsers for the parsing and interpretation of small sets of natural language sentences within specific contexts. Functional parsing is also known as monadic parsing and parsing combinators.

    Generally, I am using functional parsers to make Domain-Specific Languages (DSL’s). I use DSL’s to make command interfaces to search and recommendation engines and also to design and prototype conversational engines. I use extensively the so called Backus-Naur Form (BNF) for the grammar specifications. Clearly a DSL can be very close to natural language and provide sufficient means for interpretation within a given (narrow) context. (Like function integration in Calculus, smart phone directory browsing and selection, or search for something to eat nearby.)

    I implemented and uploaded a package for construction of functional parsers: see FunctionalParsers.m hosted by the project MathematicaForPrediction at GitHub.

    The package provides ability to quickly program parsers using a core system of functional parsers as described in the article “Functional parsers” by Jeroen Fokker .

    The parsers (in both the package and the article) are categorized in the groups: basic, combinators, and transformers. Immediate interpretation can be done with transformer parsers, but the package also provides functions for evaluation of parser output within a context of data and functions.

    Probably most importantly, the package provides functions for automatic generation of parsers from grammars in EBNF.

    Here is an example of parsing the sentences of an integration requests language:

    Interpretation of integration requests

    Here is the grammar:
    Integration requests EBNF grammar

    The grammar can be visualized with this mind map:

    Integration command

    The mind map was hand made with MindNode Pro. Generally, the branches represent alternatives, but if two branches are connected the direction of the arrow connecting them shows a sequence combination.

    With the FunctionalParsers.m package we can automatically generate a
    mind map parsing the string of the grammar in EBNF to OMPL:

    IntegrationRequestsGenerated

    (And here is a PDF of the automatically generated mind map: IntegrationRequestsGenerated . )

    I also made a slide show that gives an introduction to how the package is used: “Functional parsers for an integration requests language grammar”.

    A more complicated example is this conversational engine for manipulation of time series data. (Data loading, finding outliers and trends. More details in the next blog post.)