Basic principles for transfer

The basic idea of the transfer module is to rely on derivation trees to transfer from one language to another. Given a derivation tree, from parsing a sentence in the source language, the target derivation tree will be built by a node to node correspondence in the derivation tree, ie an elementary tree to elementary tree correspondence, preserving the dominance relation between nodes in the derivation tree.

This is illustrated by the simple diagram below:

                a                               a'
              /   \                           /   \
            /       \                       /       \
          /           \                   /           \
        b               c               b'              c'
                        |                               |
                        |                               |
                        |                               |
                        d                               d'

Node to node correspondence

In order to define a complete target derivation tree, we need to know the address where each son is attached to its parent (I will use the term "attach" to mean either "adjoin" or "substitute").

This is specified by a node to node correspondence associated to each elementary tree to elementary tree correspondence. Let's take the example of (a) to (a') correspondence:

(a) (a')

                n0                              n0'
              /    \                            |
            /        \                          |
          /            \                        |
        n1              n2                      n1'
                         |                    /   \
                         |                  /       \
                         |                /           \
                        n21             n11'            n12'

The node to node correspondence defined between the nodes of these two elementary trees are interpreted in this way. Let's say that in the source derivation tree, (b) is attached to (a) at address n1. As the corresponding tree for (b) is (b') and the corresponding node for n2 in (a) is n11' in tree (a'), the target elementary tree (b') has to be attached to the target elementary (a') at address n11', if possible of course (appropriate type of tree and category).

By this way, the node to node correspondence defined for each elementary tree to elementary tree correspondence completely defines the target derivation tree, which has of course to be valid from a structural point of view (no two attachments at the same node in the current derivation paradigm, no substitution nodes left empty), and for feature propagation in the derived tree (no clash).

Lexical entries

As we use a Lexicalized TAG paradigm, from the lexical point of view, the elementary tree to elementary tree correspondence is in fact a lexicalized tree to lexicalized tree correspondence.

In the current paradigm for transfer, the lexical correspondence is defined in terms of what is called a lexical entry. For transfer purposes, a lexical entry is close to a semantic entry (the sense of a word), not a syntactic or morphological class (but see note below).

That means that the derivation tree constructed by the lexicalized tree transfer described above has to be completed by a morphological generation phase to retrieve the actual words and build an actual sentence.

(Note: In the current implementation (Aug 92) of the lexicon, the only class defined is the morphological class, and the current implementation of the transfer module uses this only available class to define lexical transfer. This should be modified to fit the new lexicon implementation).

Feature transfer

In the LTAG formalism with features, we can consider two types of features. The first type is structural features (or syntactic features). These features are related to the structure of the trees and constrain the possible combination of elementary trees. The second type is morphological features. These features are specified by the morphological heads of each elementary tree, and may be different from a morphological form to another.

In the implemented paradigm for transfer, I have to chosen to restrict the feature transfer to morphological features. Structural features are related to the tree definitions in each language, and are in fact transfered implicitly within each tree transfer.

This feature transfer is defined from head to head in each lexicalized tree pair, be they purely local to the morphological head or inherited by the head during the feature propagation process.

The target features (ie the features transfered form the source head features) do not provide absolute specifications for the morphological head in the target language. They are considered as indications to find the best words during morphological generation, but can be cancelled by other constraints in the target language.

The morphological generation phase is therefore an optimization process: given the structural constraints and the proposed transfered features, find the morphological words that satisfy the maximum number of proposed features. (This optimization should be a global optimization, but is currently implemented as a local optimization, which can have global consequences due to feature propagation. See algorithm below).

An example of default cancelation occurs with the the mode feature transfer. The mode feature can be transmitted from verb to verb in main clauses, but in subordinate clauses, the mode is generally imposed by structural constraints that vary from one language to another.

Another example is gender, which is may be different from language to language for most objects, but which is a relevant information when people are involved.

Note that features an also appear to restrict tree or lexical transfer (see data below), but these features are not considered as transfered features per se.

Transfer data specification

We will describe here the basic principles that have been considered to specify the transfer data. The actual specification is described elsewhere.

Different types of transfer data are needed. As we have seen before, there is basically three different elements that are present in transfer.

The first is tree transfer (ie non-lexicalized tree). The tree transfer specifies the correspondence between trees in the two languages, and the node correspondence inside the trees. Some feature restrictions can be added.

In a LTAG grammar, we have also the family notion, which is considered as a set of related trees. Therefore, we can define the (non-lexicalized tree) transfer by two means: a family transfer description and an individual tree transfer description.

The second type of transfer is lexical transfer. It is defined independently from the tree transfer, and gives the correspondence between entries in the two lexicons. Constraints on features and/or trees or families can be added.

The two types of transfer databases above have to be combined in order to define an actual lexicalized tree transfer, from a source lexicalized tree to a target lexicalized tree.

This two types of data can be seen as generic or generalized definitions of transfer. In order to deal with very specific transfer units, that don't need any generalization, it is also possible to define directly lexicalized tree transfers, which already combines tree and lexical information.

The last type of transfer data is the feature transfer. It is defined very simply by specifying, for each relevant head category pair, the explicit correspondence between features (path and value).

Ambiguity: multiple transfers

By applying this correspondence to the source derivation tree, we obtain a target derivation tree. In fact, due to ambiguities (ie multiple translations for a single elementary tree), the result is not a tree, but what I will call a derivation lattice. The derivation lattice stores the multiples target elementary trees (the nodes of the lattice) and the compatibilities between parent and son (the links in the lattice), as in the example below:

a a1' a2'

b c b1' b2' c1' c2'

d d1' d2'

In this example, we have two target elementary trees for each source elementary tree. The links in the target derivation lattice represent the compatibilities between the elementary trees, ie the node transfer as provided a node in the parent where the son can be attached. In the example above, we have the links from a1' to b1' and b2' (b1' and b2' can be attached to a1') but only from a2' to b2' (b1' cannot be attached to a2').

Another source of ambiguity occurs when more than one target node is given for one node in a source elementary tree. If the two target nodes have the same category and are of the same type (adjoining or substitution node), a target elementary tree can be attached to any of them. (I am not sure this has really a practical use (with actual data), but these configuration is allowed at least theoretically, and as the implementation has already to deal with the first type of ambiguities, this second type doesn't really add to complexity.)

Given these ambiguities, the first phase of transfer is to built the derivation lattice, with the correct links between compatible elementary trees (this phase is called transfer in the implementation below). If an ambiguity is present, this derivation lattice represent implicitly more than one actual derivation trees (in fact, an exponential number of them).

The second phase of the transfer (called generation in the implementation below) will be an expanding phase, where all the individual derivation trees are built, their validity checked (features, and structural constraints), and finally the morphological generation done.

Notes about synchronous Tugs

The implementation is not a rewriting implementation of synchronous TAG, as presented in [Abeille, Schabes, Joshi: Using Lexicalized Tags for Machine Translation, Coling 90] or even implicitly in [Shieber, Schabes: Synchronous Tree-Adjoining Grammars, Coling 90]. The derived tree is never considered as relevant, never built, all the transfer operations are considered local to one elementary tree, the only existing non-local link is the feature propagation process.

The implementation described here is not really a synchronous implementation, in the sense that the transfer operation is not executed in parallel with the parsing operation, they are two different phases of the process of translating.

It doesn't seem to me that the parallel implementation is really useful from the point of view of translation: is the target language relevant to help or restrict the parsing in the source language ? Nevertheless, a real synchronous transfer could be required for an incremental system (simultaneous translation or other).

In a syntactic to semantic transfer, a synchronous implementation could be useful, as the semantics could bring relevant information to disambiguate the parsing process, but this case has not been considered here.

Extension to complex transfer

The transfer operation described above, based on one-to-one elementary tree correspondence, has been extended for a practical use. Here are some examples where this simple paradigm is insufficient:

In all these examples, the correspondence is not between two elementary trees, but between an elementary tree and a (partial) derivation tree. The transfer paradigm has been extended to deal with this kind of transfers (which will be called "complex" transfer thereafter). The diagram below shows a configuration of complex transfer:

a a'

b c b'

d d'

Here, it is the partial derivation tree (a) + (c) which is transfered into a single elementary tree (a').

This kind of transfer is restricted in the actual implementation to derivations where the sons are all completely specified, ie they are lexicalized trees. The only lexical entry that can be left unspecified, is the lexical entry of the root of the partial derivation. This allows the use of complex transfer specification for generic tree or family transfers (examples like "melt/fondre", see data transfer examples below).

With this extension, the feature transfer process has been extended to feature transfer between any heads in the derivation. In the "melt/faire fondre" example, the mode and tense features are transfered between "melt" and "faire" instead of between "melt" and "fondre".

Extension to tree/feature transfer

An other extension that is useful is to allow tree to feature transfer.

Some aspects of one language may have different forms in a different language. For example one language can use a morphological derivation to express some aspect while another language uses a syntactic derivation to express the same aspect.

An example between French and English is the future tense: an auxiliary verb is used in English and morphological derivation in French.

Not completely implemented yet, see algorithm for details.

[ Index Page | XTAG Page ]

This page is a modified version of the original written by Gilles Prigent (prigentg@lannion.cnet.fr). The page is currently maintained by Anoop Sarkar (anoop@linc.cis.upenn.edu).