Learning Word-to-Meaning Mappings in Logical Semantics

Makoto Kanazawa

                       kanazawa@iii.u-tokyo.ac.jp

Interfaculty Initiative in Information Studies, University of Tokyo

Siskind (1996, 2000) discusses the problem of learning word-to-meaning mappings from sentences coupled with their meanings. In his setup, sentence meanings are represented by first-order terms built up from constants and function symbols (called conceptual symbols), and word meanings are represented by first-order terms with zero or more individual variables. For instance, the meaning of John lifted Mary may be represented by CAUSE(John, GO(Mary, UP)), where CAUSE, John, GO, Mary, and UP are conceptual symbols. The learner is fed with a stream of word strings coupled with expressions like the one above, and is expected to arrive at a word-to-meaning mapping like:

John ↦ John
lifted ↦ CAUSE(x, GO(y, UP))
Mary ↦ Mary

(1)

Semantic composition is supposed to be done by substitution. An equivalent way of looking at it is to view word meanings as λ-terms like λxy.CAUSE(x, GO(y, UP)), where all subterms are of first-order types, and semantic composition as application plus β-reduction.

Siskind shows that one can reduce the complexity of learning by breaking down the learning process into two phases. In the first phase, the learner forms, for each word, the set of conceptual symbols involved in the meaning of that word. This can be done efficiently by an online algorithm that maintains two sets of conceptual symbols: the set of symbols that are possibly in the correct word meaning, and the set of symbols that are necessarily in the correct word meaning. The second phase then builds the correct meaning expression out of the symbol set learned in the first phase. For instance, suppose that the learner has arrived at the following association of words with symbol sets:

John : {John}
lifted : {CAUSE, GO, UP}
Mary : {Mary}

Then, given that the sentence John lifted Mary has meaning CAUSE(John, GO(Mary, UP)), the learner can now uniquely determine the word-to-meaning mapping given in (1).

The aim of this paper is to study a generalization of Siskind’s problem, where conceptual symbols, as well as variables, can be of arbitrary types, and meaning expressions are typed λ-terms built out of these, using λ-abstraction as well as application. This is the usual setup of logical semantics. For instance, the sentence every man finds a unicorn may have a meaning represented by ∀x[MAN(x) → ∃y[UNICORN(y) ∧ FIND(x, y)]], which is just a shorthand for

∀^{(e→t)→t}(λx^{e}. →^{t→t→t} (MAN^{e→t}(x))

(∃^{(e→t)→t}(λy^{e}. ∧^{t→t→t} (UNICORN^{e→t}(y))(FIND^{e→e→t}(y)(x))))). (2)

The meanings of the words in this sentence may be (suppressing the type when it is clear):

every  ↦ λu^{e→t}v^{e→t}.∀(λx^{e}. → (ux)(vx))
man  ↦ MAN
finds  ↦ FIND
a  ↦ λu^{e→t}v^{e→t}.∃(λy^{e}. ∧ (uy)(vy))
unicorn ↦ UNICORN

(3)

(I mostly follow the notational convention of Hindley 1997, except that I may write the application of two terms M and N either MN or M(N), depending on which is more readable.)

Just as in the simple first-order case of Siskind, the problem of learning word-to-meaning mappings can be broken down into two subproblems: the problem of finding for each word the set of constants that appear in the meaning of that word, and the problem of building the correct λ-term for each word using the symbol set associated with that word. The first problem can be solved efficiently in exactly the same way as in the case of Siskind. How to solve the second problem was rather obvious in the case of Siskind, but becomes far from so in our generalized setting. I formulate the heart of the problem as a problem in typed λ-calculus.

Mapping Problem. Given m sets of distinct variables

x⃗_{1} = x_{1,1}^{σ_{1,1}}, …, x_{1,n_{1}}^{σ_{1,n_{1}}}
⋮
x⃗_{m} = x_{m,1}^{σ_{m,1}}, …, x_{m,n_{m}}^{σ_{m,nm}}

and a λI-term T^{ρ}[x⃗_{1}, …, x⃗_{m}] (with free variables x⃗_{1}, …, x⃗_{m}) in βη-normal form, find m λI-terms S_{1}^{τ_{1}}[x⃗_{1}], …, S_{m}^{τ_{m}}[x⃗_{m}] and a BCIλ-term D^{ρ}[y_{1}^{τ_{1}}, …, y_{m}^{τ_{m}}], each in βη-normal form, such that

D[S_{1}[x⃗_{1}], …, S_{m}[x⃗_{m}]] ▷_{βη} T [x⃗_{1}, …, x⃗_{m}].

I denote this problem by T^{ρ}[x⃗_{1}; …; x⃗_{m}], and I call ⟨S_{1}^{τ_{1}}[x⃗_{1}], …, S_{m}^{τ_{m}}[x⃗_{m}]⟩ a solution to this problem.

In the solution to a mapping problem, S_{i}^{τ_{i}}[x⃗_{i}]’s represent the ‘meaning recipe’ of individual words, where the free variables x⃗_{i} are supposed to be filled by conceptual symbols. D^{ρ}[y_{1}^{τ_{1}}, …, y_{m}^{τ_{m}}] then gives the meaning recipe for the sentence. Thus I assume that simultaneous binding of multiple occurrences of a variable is possible in word meanings, but not in meaning recipes for sentences.

A ‘mapping problem’ of a more restricted kind corresponding to Siskind’s setup always has at most one solution, and the condition under which a solution exists is easy to state. As for the general version, we have

Theorem 1. Every mapping problem has infinitely many solutions.

Theorem 2. For any sequence of terms M⃗ = M_{1}^{σ_{1}}, …, M_{n}^{σ_{n}}, let U_{ρ}[M⃗] = λy^{σ_{1}→···→σ_{n}→ρ}.yM_{1} … M_{n}. Then, for every mapping problem T^{ρ}[x⃗_{1}; …; x⃗_{m}] such that T^{ρ}[x⃗_{1}, …, x⃗_{m}] is a BCIλ-term, ⟨U_{ρ}[x⃗_{1}], …, U_{ρ}[x⃗_{m}]⟩ solves T^{ρ}[x⃗_{1}; …; x⃗_{m}].

‘Universal’ solutions like U_{ρ}[x⃗] are not very interesting: they not only derive correct sentence meanings but also many unwanted ones. The following example illustrates the case of a λI mapping problem.

Example 3. Consider a mapping problem T^{t}[x⃗_{1}; x⃗_{2}], where x⃗_{1} = x_{1,1}^{(e→t)→t}, x_{1,2}^{t→t→t}, x_{1,3}^{e→t}, x⃗_{2} = x_{2,1}^{e→t}, and T^{t}[x⃗_{1}, x⃗_{2}] = x_{1,1}(λz^{e}.x_{1,2}(x_{1,3}z)(x_{2,1}z)). This corresponds to the situation where the learner is faced with a sentence everyone walks coupled with the meaning ∀z(PERSON(z) → WALK(z)), having arrived at the word-to-symbol-set association:

everyone : {∀, →, PERSON}
walks  : {WALK}

A solution ⟨U_{t}[x⃗_{1}, W^{(e→e→t)→e→t}], x_{2,1}⟩, where W^{(e→e→t)→e→t} = λy^{e→e→t}x^{e}.yxx, corresponds to the word-to-meaning mapping:

everyone ↦ λy^{((e→t)→t)→(t→t→t)→(e→t)→((e→e→t)→e→t)→t}.y(∀)(→)(PERSON)(W)
walks  ↦ WALK

⟨U_{t}[x⃗_{1}, W^{(e→e→t)→e→t}], x_{2,1}⟩ solves not only T^{t}[x⃗_{1}; x⃗_{2}], but also V^{t}[x⃗_{1}; x⃗_{2}] = x_{1,1}(λz^{e}.x_{1,2}(x_{2,1}z)(x_{1,3}z)), corresponding to ∀z(WALK(z) → PERSON(z)). Of course, ⟨λv^{e→t}.x_{1,1}(λz^{e}.x_{1,2}(x_{1,3}z)(vz)), x_{2,1}⟩, corresponding to the word-to-meaning mapping:

everyone ↦ λv^{e→t}.∀z(PERSON(z) → vz)
walks  ↦ WALK

only solves the former.

Certainly, the second solution in the above example is preferable to the first as a hypothesis for the learner. Perhaps what the learner should find is a ‘minimal’ solution, in the sense of solving as few unwanted problems as possible. To define a suitable sense of minimality, I introduce a ‘definability relation’ ⪯ between terms and a slightly weaker notion ⪯_{ρ}.

Definition 4. Let M^{σ}[x⃗] and N^{τ} [x⃗] be two λ-terms in βη-normal form with the same set of free variables.

(i) We say that N^{τ} [x⃗] is BCI-definable by M^{σ}[x⃗] and write N^{τ} [x⃗] ⪯ M^{σ}[x⃗] if there is a closed BCIλ-

term P^{σ→τ} such that

P^{σ→τ} M^{σ}[x⃗] ▷_{βη} N^{τ} [x⃗].

We write N^{τ} [x⃗] ≃ M^{σ}[x⃗] if N^{τ} [x⃗] ⪯ M^{σ}[x⃗] and N^{τ} [x⃗] ⪰ M^{σ}[x⃗]; and write N^{τ} [x⃗] ≺ M^{σ}[x⃗] if N^{τ} [x⃗] ⪯ M^{σ}[x⃗] but N^{τ} [x⃗] ⪰̸ M^{σ}[x⃗].

(ii) We write N^{τ} [x⃗] ⪯_{ρ} M^{σ}[x⃗] if λy^{τ→ρ}.yN^{τ} [x⃗] ⪯ M^{σ}[x⃗]. We write N^{τ} [x⃗] ≃_{ρ} M^{σ}[x⃗] if N^{τ} [x⃗] ⪯_{ρ} M^{σ}[x⃗] and N^{τ} [x⃗] ⪰_{ρ} M^{σ}[x⃗]; and write N^{τ} [x⃗] ≺_{ρ} M^{σ}[x⃗] if N^{τ} [x⃗] ⪯_{ρ} M^{σ}[x⃗] but N^{τ} [x⃗] ⪰̸_{ρ} M^{σ}[x⃗].

Clearly, N^{τ} [x⃗] ⪯ M^{σ}[x⃗] implies N^{τ} [x⃗] ⪯_{ρ} M^{σ}[x⃗] for all ρ. Also, if τ ‘ends in’ ρ, N^{τ} [x⃗] ⪯_{ρ} M^{σ}[x⃗] implies N^{τ} [x⃗] ⪯ M^{σ}[x⃗]. The two relations do not coincide in general: x^{e} ⪯_{t} λy^{e→t}.yx, but x^{e} ⪯̸ λy^{e→t}.yx. Both ⪯ and ⪯_{ρ} are reflexive and transitive. Also, both relations are decidable. The latter follows from the known fact that every type is inhabited by finitely many BCIλ-terms in βη-normal form (van Benthem 1991).

Theorem 5. If ⟨S_{1}[x⃗_{1}], …, S_{m}[x⃗_{m}]⟩ solves T^{ρ}[x⃗_{1}; …; x⃗_{m}], and S_{i}[x⃗_{i}] ⪯_{ρ} P [x⃗_{i}], then ⟨S_{1}[x⃗_{1}], …, S_{i−1}[x⃗_{i−1}], P [x⃗_{i}], S_{i+1}[x⃗_{i+1}], …, S_{m}[x⃗_{m}]⟩ solves T^{ρ}[x⃗_{1}; …; x⃗_{m}].

Even though a mapping problem has infinitely many solutions, many of them turn out to be equivalent with respect to ≃ and ≃_{ρ}. A trivial example is T^{t}[x^{e}; y^{e→t}] = yx, which has just two solutions modulo ≃, namely ⟨x, y⟩ and ⟨λy^{e→t}.yx, y⟩ (which, in turn, are equivalent with respect to ≃_{t}). I conjecture that every mapping problem has only finitely many solutions modulo ≃.

The relations ⪯ and ⪯_{ρ} can be naturally extended to solutions of mapping problems. In general, a mapping problem T^{ρ}[x⃗_{1}; …; x⃗_{n}] can have more than one ⪯_{ρ}-incomparable minimal solution.

Example 6. A problem T^{t}[x^{e}; y^{e→e→t}; z^{e}] = yzx has the following solutions, among others:

⟨λy^{e→e→t}z^{e}.yzx, y, λy^{e→e→t}v^{(e→e→t)→e→t}.v(λxz.yzx)z⟩,
⟨λy^{e→e→t}v^{(e→e→t)→e→t}.vyx, y, λy^{e→e→t}.yz⟩.

Since λy^{e→e→t}z^{e}.yzx ≺_{t} λy^{e→e→t}v^{(e→e→t)→e→t}.vyx and λy^{e→e→t}v^{(e→e→t)→e→t}.v(λxz.yzx)z⟩ ≻_{t} λy^{e→e→t}.yz, the two solutions are incomparable with respect to ⪯_{t}. Their ‘meet’,

⟨λy^{e→e→t}z^{e}.yzx, y, λy^{e→e→t}.yz⟩,

does not solve T_{t}[x^{e}; y^{e→e→t}; z^{e}], and indeed the two solutions can be shown to be minimal with respect to ⪯_{t}.

The above example suggests that it may not be desirable for the purpose of learning to collect all minimal solutions to a given mapping problem. A simple algorithm exists that finds a ‘reasonably small’ solution to a mapping problem, together with a pure application term as a sentence meaning recipe.

References

Benthem, Johan van. 1991. Language in Action: Categories, Lambdas and Dynamic Logic. Amsterdam: North-

Holland. (Second edition, 1995, Cambridge, Mass.: MIT Press.) Hindley, J. Roger. 1997. Basic Simple Type Theory. Cambridge: Cambridge University Press. Siskind, J. Mark. 1996. A computational study of cross-situational techniques for learning word-to-meaning

mappings. Cognition 61(1–2), 39–91. (Reprinted in Michael Brent, ed., 1996, Computational Approaches to Language Acquisition, pp. 39–91, Amsterdam: Elsevier.)

Siskind, J. Mark. 2000. Learning word-to-meaning mappings. In Peter Broeder and Jaap Murre, eds., Models of Language Acquisition: Inductive and Deductive Approaches, pp. 121–153. Oxford: Oxford University Press.