This paper presents an approach for automatically learning reference resolution, which involves using natural language expressions, including spatial language descriptions, to refer to an object in a context. This is useful in conversational systems that need to understand the context of an utterance, like multi-modal or embodied dialogue systems. Markov Logic Networks are explored as a way of jointly inferring a reference object from an utterance with some simple utterance structure, and properties from the real world context. An introduction to mlns, with a small example, is given. Reference resolution and the role of spatial language are introduced. Different aspects of combining an utterance with properties of a context are explored. It is concluded that mlns are promising in resolving a contextual reference object.
When we speak in a dialogue setting, we are often co-located (situated) in space and refer to objects in that space. Besides using salient properties to refer to an object, like its color, shape, and size, the language which is often used to refer to those objects make up spatial language; that is, where the object is relative to some frame of reference, or as relative to other objects in that space. Understanding spatial language has application in fields like dialogue systems, multi-modal systems, and robotics, and makes up a part of natural language understanding (nlu) in situated environments.
Work done in reference resolution has focused mainly on word-level approaches
(see [
Plan of this paper: In the following section, mlns are defined and a simple example is given. The last part of the section will define reference resolution, with particular attention to spatial language and how it pertains to the task of this paper. In section 2, the domain, task, data, and procedure are explained. The experiment section then shows how well the system performs in reference resolution, as well as some visual representations of how well the system learned about spatial language. 1.1
Markov Logic Networks have recently received attention in language processing fields
like coreference resolution [
As an example mln, consider the following statement: If you write something down, you are twice as likely to remember it. We can represent this by the predicates W rite(person) and Remember(person). This can be formulated as: 2 W rite(x) ⇒ Remember(x). This defines a relationship between Write and Remember. The argument in both Write and Remember have the type person and for this example, we will introduce only one constant: Mary. Building all possible formulas given this information requires all combinations of positive and negative predicates in the formula, resulting in four formulas, all with weight 2, which will be referred to as worlds. It is then necessary to determine which of those four formulas are satisfied by the original formula of W rite(x) ⇒ Remember(x). It is satisfied when W rite is negative or when Remember is positive, or both. The only time it is not satisfied is when W rite(M ary) ⇒ ¬P ositive(M ary).
After a set of worlds is created, one can perform inference by calculating a probability: (1) (2) P (X = x) = 1 ePj wjfj(x)
Z Z =
X x in X
ePj wjfj(x)
Where j indexes over the formulas. Here wj is defined as the weight of the corresponding formula (in our example, the weight was 2), and fj is a function that returns 1 if the formula is satisfiable, and 0 if it is not satisfiable. After the worlds and their satisfiabilities are identified, the next step is to determine Z. If our evidence is W rite(M ary), Z can be computed by finding which of the four formulas by:
Where Z, also known as the partition function, is the normalizing constant given satisfy the evidence W rite(M ary), which results in one world that is satisfiable by the original formula, and one that is not. Given this set of worlds, the numerator of the probability is found by identifying the formulas which satisfy a query, for example, Remember(M ary)?, which results in only one satisfiable formula. In this case, the probability of Remember(M ary) given the evidence W rite(M ary) is e2e+2e0 = 0.88.
This simple example only considered a very small set of possible worlds. It doesn’t
take many more formulas, predicates, arguments, or constants to make computing mlns
intractable for large domains. In fact, inference alone is NP-Hard [
Learning the meaning of spatial relationships has been done in navigational
direction tasks using reinforcement learning [
Spatial language involves the language humans use to describe space and the objects in that space. Humans require a common understanding of absolute and relative spatial descriptions in order to communicate effectively. Words such as left, right, top, bottom, and middle can represent absolute descriptions. Relative means that objects identified relative to another, perhaps more visually salient object. This is where prepositions are often used; on top of, below, next to, to the left of, beside. Even if we can gesture by pointing or looking at an object, we still usually need to be able to articulate the linguistic description of the object such that the hearer of the utterance can uniquely identify the object to which we are referring. This linguistic description becomes even more important when a human is interfaced with a computer and language is the only medium for communication from human to computer, which is the experimental setting for this paper.
It is essential to establish a frame of reference when using spatial language. It
has been shown that alignment of the reference point is an ongoing process across
utterances, depending on the context [
In this section, the domain, task, data, and procedure of the experiment which will use mln to automatically learn reference resolution, particularly using spatial language, are defined. By giving accuracies of successfully referred objects, we show that mlns can be used successfully in reference resolution, as well as some figures that show the extent that spatial language was learned. 2.1
In this study, we used the Pentomino puzzle piece domain. A Pentomino board is
visually represented in rows and columns with pieces viewable by a human. On the
computer side, pieces are identified with unique arbitrary identifiers. The properties of
the pieces which are visually distinguishable by a human (color, shape, row, column,
relation to other pieces) are accessible also to the computer. In this way, the board and
pieces effectively become a shared visual context between the human and the computer,
as described in [
Selected
Property WordGroup
WordGroup
Perspective is not being studied in this paper, so assumptions need to be made
about the frame of reference. The Pentomino board defines a fixed frame of reference
which is a board on a computer screen. Also, given the nature of the utterances used in
this paper (both generated from a corpus), egocentric descriptions such as my left were
not used. The utterances used involve three components to each spatial description:
target, a possible reference object, and spatial term(s) [
The Pentomino board as implemented in the InPro toolkit [
The training and evaluation data were automatically generated. This was a natural choice because one of the goals of this paper is to determine how well mlns perform on language data. We can infer that if mlns can’t be made to work well on simplistic, automatically generated data with simple relational structures, then they will not work on real speech data with more complex structures. Further, the use of automatically generated data was motivated by the fact that the perspective is fixed, making the utterances of a finite type. Also, the task is reference resolution so the verb can be assumed to be a command-form select (as in “Select the piece ...”), thus reducing the possible syntactic structures. This puts focus on the spatial language and words that describe other properties of a piece, which can be generated to be representative of typical real-world language use. Finally, we don’t generate actual utterances, but a simple semantic representation that defines relationships between words and word groups (phrases), though we will refer to them as the utterance. This kind of semantic representation can be obtained from most syntactic or semantic formalisms, though no syntactic or semantic parsing is done here.
The training data were generated by creating one thousand boards. Each board was randomly assigned 3-5 rows and 3-5 columns (number of rows and columns need not be the same), creating a small variability in the dimensions of the boards which allowed for generality. The number of pieces was also randomly assigned, between 4 and 6 pieces for training where the maximum number of pieces must be no larger than the number fields in the smallest possible board. Each piece was assigned a random color, shape, row, and column, and of course multiple pieces could not occupy the same space. After each piece was in place, one was chosen randomly to be the selected piece, the piece that was referred. A pseudo-utterance that described that piece was then generated in the form of a simple semantic representation. The pseudo-utterance contained words that described the shape, color, absolute, and relative descriptions. There were a total of 5 colors and 7 shapes. I used the following absolute spatial descriptions: left, right, top, bottom, middle, corner, and the following relative spatial descriptions: above, higher than, on top of, next to, beside, below, under, beneath, on the left of, and on the right of. The shape, color, and all absolute spatial descriptions were treated as a bag of words. The words in a relative spatial description were treated as a word group, which corresponds to a small amount of linguistic structure (grouped, for example, as prepositional phrases).
An example of this is given in Figure 3. Here, the selected piece is a red cross somewhere near the middle, below a gray cross which is in the middle of the top row. The generated pseudo-utterance would be something like select the middle red cross below the gray cross in the top middle, where red, middle, and cross are treated as simple words, and below the gray cross in the top middle is treated as a word group. 1http://sourceforge.net/projects/inprotk/
The evaluation set was similarly generated, but used 100 boards, with row and column lengths between 3 and 7, and the number of pieces was between 4 and 9. The range of rows and columns, and the range of possible number of pieces was larger than in training. For each evaluation experiment, the evaluation set was randomly generated, so each one was different.
Part of the effort in using mlns is determining what should be specified as predicates (e.g. Color, Shape, Row, etc) and what should be learned automatically. In this paper, only one abstract predicate, Property, that implicitly does the typing into different features was used. The example in Figure 3 shows a single Piece, and multiple Property predicates for that piece. Where numbers would cause confusion, they can simply be annotated with a unique property type (e.g. column 1 = 1C). The properties used as represented in Figure 3 were type, color, % horizontal from center, % vertical from center, row, and column. The predicates Word and WordGroup represent the words, and group of words, respectively, as previously explained. The final argument for all the predicates is the board identifier, which separated states of the board and corresponding selected pieces and utterances from other boards. The second argument in WordGroup, groupID, is a unique identifier that is the same across a group of words. In Figure 3, the identifier is simply 1, but if more WordGroups existed, then they would be represented by a different number. A typical representation of a board would have many pieces and more word groups for the utterance.
The Alchemy system [
To test, a board is similarly randomly generated as in training, and a piece is again randomly selected. However, the selected piece is what was being inferred about by the mln, so it was kept hidden. The pseudo-utterance was generated in the same way as in training. Using the state of the board and the utterance, the mln system then inferred which piece was being described by that utterance. If the piece with the highest probability matched the selected piece, it was marked as correct. If there was a tie, then the first one returned by the query was chosen. This is therefore a simple measure of accuracy. In this scenario, the majority class baseline would be 25%, where 4 is the minimum number of possible pieces during evaluation. 2.2
Though the main goal of this paper is to show that a mln can effectively learn spatial language reference resolution, it is also useful to see how a mln performs in different settings, as shown in Table 1. Overall, alchemy and mln perform above baseline in all areas. Most interesting to note is the fact that when all types were used (shape, color, absolute, and relative spatial), the accuracy was only 58%. This is possibly due to the fact that it was trained on a system which included the rows and columns (information that was not used at evaluation). This is evidenced by the fact that the Ind column for the same row gave 88% and was trained on similar settings, only minus rows and columns, forcing the model to learn how to resolve without rows and columns as piece properties. It is further interesting to note that shape, color, and absolute spatial received high accuracies for both systems. However, a system with relative spatial knowledge will be more robust to real language input in a real-world environment, despite the somewhat lower probability. 2.3
Another way of showing how well the mln learned about spatial language is to look at a graphical representation of the probabilities of each piece in the board as a gradient, where the darker in color, the higher the probability. Some of these gradient boards (using a 5x5 board) are displayed, where all fields are taken by a piece with the same color and shape, thus nullifying them as distinguishing features. First, a look at absolute spatial language. An example of absolute top-left, and absolute centre-right are represented in Figures 4 and 5 respectively. These show that the absolute language was well learned, especially for a specific point like top-left in Figure 5.
Relative spatial language is a little more difficult to visualize in a gradient, but certain relative relations can be isolated by looking at a gradient map with its corresponding board, where the board is not completely filled. The board and gradient map for the relation above can be found in Figures 6 and 7. For a piece to be above another piece, it simply needed to be in a higher row than that piece, regardless of the column. The notion of above is learned, but the distribution over the pieces is somewhat unexpected. Any piece that is above another piece should have some probability, with the darker gradients starting at the higher pieces, decreasing with the rows. The concept of above here is generally learned, though there is need for improving the model when it comes to relative spatial relationships.
After the submission of this paper, we used the principles that were learned here
and applied them to real, non-generated Pentomino data collected in a
Wizard-ofOz study [
Markov Logic Networks are effective in reference resolution in a two-dimensional domain like Pentomino. They can effectively learn a mapping between an utterance and real world object properties, including utterances that contain spatial language descriptions.
Future work involves using what was learned via this task and implementing it into a larger natural language understanding framework. We will continue to use mlns, and further incorporate other real-world information, such as eye gaze and gestural information from the human. We will extend this to domains beyond Pentomino, domains which use real world spatial representations, and apply it in interactive settings.