Exercise 8: Language transformations algorithmAugust 5, 2008
SummaryCreate a web application to allow a user to type a statement or question and have the system respond.
  | If at any time the system doesn't understand, no response should be given. (Only debug output: See below) |
| If a question is asked, and the system understands, the system should respond with the value that answers the question. If the system understands but doesn't know the answer, it should respond with "I don't know [...]", and fill in the square brackets with the path to the requested property. For example: "I don't know [speaker.age]". At this time, only questions that can be answered with a value are permitted. |
| If a statement is entered, and the system understands, it should update its data structure and respond with "Ok: ...", and fill in the appropriate assignment. For example: "Ok: speaker.age = 27". |
| A link will be provided named "Show details", which will show a hidden pane. This pane will show debug output, which is described later on. |
| A link will be provided to a second page entitled "Brain state" which will contain three large text areas. The first text area will contain a dump of the brain's core state. The text area can be edited and a "Save" button clicked to update the brain state. Likewise, there should be text areas for editing the word-to-entity mappings as well as the transformations. |
Applying transformationsThe core of this exercise is to create an algorithm that, given a statement or question, determines which sequence of transformations to apply to end up with a representation that can be directly interpreted.
The first step is to transform a list of words into a list of
EntityTrees. Each tree represents the
is_a relationships of the word it corresponds to. Rather than storing the tree, however, it should be converted into a flat list using the
GetList() method. We'll call this list of lists the
entityTypeLists structure.
The next step is to permute the lists to arrive at all possible combinations of entity types. For example, taking the first entity type from each list arrives at one combination. Taking the second entity type from the first list and first entity type from the rest of the lists arrives at another combination, etc. We'll call this the
permutedEntityTypes list.
The core algorithm iterates over the
permutedEntityTypes list. Each permutation of entity types consists of a list of entity types. Taking the first two entity types, we determine which transformations can be applied. To determine this, we need an indexed structure that allows us to get all applicable transformations given two sequential entity types. For example, we could use a two-deep hash.
Once we have determined what transformations we can apply, we go ahead and apply each one separately. (If there are no transformations to apply, then we need to look for transformations that can be applied starting at the second token, etc.) For each application, we have to ask ourselves whether the resultant fragment is
complete. ie. In a format that can be directly interpreted. If it is, we add it to a list of
interpretations. If it is not, we add it back onto the
permutedEntityTypes stack.
Note that because transformations take
Fragments as their input and produce
Fragments as their output, the
permutedEntityTypes list needs to be a list of
Fragments. Thus we'll call it the
unresolvedFragments list.
The class that orchestrates this process should be called
TransformationSearch.
Debug output | The debug output will be displayed if the "View details" link is clicked. The primary purpose of the debug output is to see what happened when unexpected response was given. |
| For each word, the list of possible entities will be listed. Format: |
| | word1: entity1, entity2, entity3, etc. |
|
etc. |
| The initial list of permuted fragments will be listed. |
| If a fragment is clicked, the list of applicable transformations will be listed. |
| If one of the applicable transformations is clicked, the resultant fragments and outputs will be listed. |
| This is effectively a recursive process that allows the user to drill down into the search space. |
Test casesClick hereSolutionClick hereWeb UIClick hereExercise 7: Mapping words to entitiesAugust 5, 2008
SummaryBefore we can transform language, we need to convert words to entities. We can do this my defining word-to-entity mappings. For example:
What this says is that the word "I" might refer to the
speaker entity, which is a
noun. The specification that speaker is a noun is a convenience feature and simply ensures that the relationship
speaker is_a noun exists. Any entity can be used in place of
noun. For example:
adjective,
verb,
adverb, etc.
Implement a representation and parser. Also implement a web UI that allows the user to specify one or more word-to-entity mappings to be parsed.
In addition to these mappings, allow the user to specify a word, which will return all of the entities that that word maps to. Implement this feature with classes called
EntityTree and
EntityTreeNode which will represent the tree of
is_a relationships that stem from a word. The tree should be doubly linked so that, given a node, you can get either its children or its parent, and it should prevent duplicate tree nodes. The tree will contain a method named
GetList which will traverse the tree and return a flat list of
EntityTreeNodes.
Test casesClick hereSolutionClick hereWeb UIClick hereExercise 6: Language transformation parserAugust 5, 2008
SummaryWith classes to represent language transformations, we can now write a parser.
Test casesClick hereSolutionClick hereolder >>
