In this paper, we concentrate on justifying the decisions we made in developing the Text Encoding Initiative (TEI) recommendations for feature structure markup. [Note 1] The first four sections of this paper present the justification for the recommended treatment of feature structures, features and their values, and of combinations of features or values and of alternations and negations of features and their values. Section 5 departs briefly from the linguistic focus to argue that the markup scheme developed for feature structures is in fact a general-purpose mechanism that can be used for a wide range of applications. Section 6 describes an auxiliary document called a "feature system declaration" (FSD) that is used to document and validate a system of feature-structure markup. The seventh and final section illustrates the use of the recommended markup scheme with two examples, lexical tagging and interlinear text analysis.
One of the goals of the Text Encoding Initiative is to provide a markup scheme that will permit scholars to encode linguistic analyses of any text in any language to any desired degree of detail. We envision all sorts of ways of using the TEI recommendations for linguistic markup, ranging from making occasional notations about the grammatical analysis of selected words in a document to preparing a full-blown phonological, morphological, syntactic, and semantic analysis of an entire document. The mechanisms that we provide are designed to express the content of commonly used representations of linguistic analysis, including tree diagrams, feature-structure diagrams, and interlinear glossing. Thus the markup scheme can be used to represent explicitly the implicit linguistic structure of a text (with respect to a particular analysis). The result is a machine-readable and machine-interpretable version of an explicit analysis presented according to familiar human-readable and human-interpretable graphical and typographical conventions.
In developing the recommendations for the markup of linguistic analysis and interpretation within the Text Encoding Initiative, we have chosen to concentrate on providing markup for the data structures that linguists typically use to represent the results of their analysis and interpretation, rather than providing markup for particular analyses and interpretations. In this way, we enable encoders to represent any analysis they wish, and do not force them to use the constructs of predefined analyses which may not be suitable for the material being encoded and which may not be easy to alter or extend. Markup is provided for two data structures in particular: feature structures and tree structures. In fact, the two data structures can be combined; any node in a tree can itself be a feature structure.
In this paper, we concentrate on justifying the decisions we made in developing the TEI recommendations for feature-structure markup. It is not within the scope of this paper to give a formal definition of the markup scheme. For that and for other details concerning feature-structure, tree, and other markup being recommended for linguistic analysis and interpretation, see Sperberg-McQueen and Burnard (1994), henceforth TEI P3.
Within linguistics, feature structures were first used by Roman Jakobson (1949) for the representation of phonemes (the distinctive or contrastive sounds in a natural language) as bundles of what he called distinctive features. Each feature represented an essential articulatory and acoustic property of a phoneme. So, for example, Jakobson considered the phoneme /s/ in English to be a bundle of distinctive features, such as [- grave], [+anterior], [- voice], [+strident], etc. (In Jakobson's theory, the values are restricted to the binary values + and - ; see section 2 for a discussion of the markup of these and other possible feature values.)
The use of feature structures quickly spread to other domains within linguistics. Chomsky (1965) extended Jakobson's distinctive feature theory to morphology and syntax, and developed the idea that a feature value within a particular feature structure could make reference to another feature structure. Subsequent developments in the theory of feature structures (within both linguistics and computer science) have led to the current situation in which feature structures, either by themselves or together with directed graphs (such as phrase-structure trees) in which feature structures are associated with the nodes in the graphs, can be used to express any linguistic analysis whatever. The ability of feature structures to serve as a general purpose linguistic metalanguage is what led us to use them as the basis of linguistic encoding.
To represent the structure that groups together a bundle of features and their values, we need a markup element that groups together (or, in SGML parlance, whose content model is a group of) features. We call that element <fs> (for "feature structure"), and the element that it groups together <f> (for "feature"). Leaving aside details that need not concern us here, the content of an <fs> is zero or more <f>s.
A linguistic analysis may consist of many different types of <fs> elements, each of which may group together different types of <f> elements. To distinguish among the different types of <fs> elements, we provide a type attribute, whose value is a string (such as "phonological structure" or "phrase structure") that specifies the feature-structure type. So, for instance, the markup of the distinctive-feature analysis of a phoneme might look as follows:
<fs type='phonological structure'> <f ... > ... </f><!--Representation for one distinctive feature-->
...
<f ... > ... </f> <!--Representations for other distinctive features--></fs>
One important reason to distinguish among feature-structure types is that different types of feature structures will contain different types of features. However, given that we are proposing to use SGML attributes to distinguish among feature-structure types (and also to a considerable extent among feature types), it will not be possible to use an SGML validator to determine whether the appropriate types of features are being used as the content of a feature structure of a particular type. To enable an encoder to specify explicitly what feature types go with what feature-structure type, we provide recommendations for the creation of a special file called a Feature System Declaration, that specifies, among other things, the correlations between feature-structure and feature types (see section 6).
In this section we justify the approach taken to marking up features, that is, we explain why the <f> tag is defined as it is. The two main issue here are the treatment of feature names and the treatment of feature values. These two topics are covered in the following two subsections. Throughout the discussion we build on a single example, namely, the analysis of the word Kind 'child,' occurring in the sentence Das Kind war einsam 'The child was lonely', as it would appear in a modern German text. The feature-structure analysis that we want to represent may be diagrammed as follows:[Note 2]
+--- --+
| category = noun || wordForm = Kind |
| proper = || |
| +-- --+ || agreement = | gender = neuter | |
| | number = singular | |
| | case = nominative | |
| +-- --+ |+-- --+
That is, the category feature has the value noun, the wordForm feature has the value Kind, the proper feature (for "Is it a proper noun?") has the value - (or minus), and the agreement feature holds an embedded feature structure which groups the gender, number, and case features. The values for these are neuter, singular, and nominative, respectively.
SGML syntax suggests four alternatives for how the name of a feature might be marked up. The feature name could be: the name of an attribute of <fs>, the name of a tag embedded within <fs>, the content of a tag for feature name embedded in a general element for feature, or the value of an attribute of a general tag for "feature". The following paragraphs consider the alternatives in turn and explain our reasons for rejecting the first three and favoring the last.
The attributes of an SGML element tag are very much like features. Could we use them to represent the features of a feature structure as in the following?
<fs category=noun wordForm=Kind
proper=minus agreement=???>
We immediately run into an insurmountable problem. Features must be able to embed feature structures as their values, but attributes do not allow tags to be embedded within them. We could solve this problem by turning the attributes into tags. Thus each feature name would become a unique tag, as in:
<fs> <category>noun</category><wordForm>Kind</wordForm>
<proper>minus</proper> <agreement> <fs> <gender>neuter</gender> <number>singular</number> <case>nominative</case> </fs></agreement>
</fs>
The chief disadvantage of this solution is that it leads to an unbounded proliferation of tags. Every user of TEI markup would be required to modify the DTDs to add a new <!ELEMENT ...> definition for each needed feature. Note, too, that although embedding of feature structures within features becomes possible, it would only be allowed when the content model for a particular feature's <!ELEMENT ...> definition were written in such a way as to permit it.
To prevent the proliferation of tags, we need a single, general-purpose element to represent any feature. Its content model says once and for all that feature structures can be embedded within features. For this we have defined the <f> tag. Within the <f> tag, the name of the feature could be represented as the content of a tag for the feature name. For instance,
<fs><f><fName>category</fName> ... </f>
<f><fName>wordForm</fName> ... </f>
<f><fName>proper</fName> ... </f>
<f><fName>agreement</fName> ... </f>
</fs>
This was essentially the proposal in TEI P1. However, it turns out to be needlessly verbose. It also provides more power than we need, in that it suggests the possibility of embedded structure within the <fName> tag. In actual fact, no embedding is possible.
This leads to our final solution, namely, that a feature's name is the value of an attribute (called name) of the <f> tag. That is,
<fs><f name=category> ... </f>
<f name=wordForm> ... </f><f name=proper> ... </f>
<f name=agreement> ... </f>
</fs>
Similarly, SGML syntax suggests three ways to markup the value of a feature. The feature value could be: the value of an attribute the <f> tag, textual content of the <f> tag, or embedded tags in the <f> tag. The following paragraphs consider the alternatives in turn and explain our reasons for rejecting the first two and favoring the last.
The first possibility might be to treat value as an attribute of <f> analogous to the name attribute, as in:
<fs><f name=category value=noun>
<f name=wordForm value=Kind><f name=proper value=minus>
<f name=agreement value=???>
</fs>
This leads to the same dead end as treating the feature name as an attribute name. The feature value must be able to embed a feature structure and this is impossible in the value of an attribute.
In order to allow feature structures to be the values of features, we must include the value of the feature as the content of the <f> tag. The simplest approach would be to treat values that were not feature structures as textual content of the <f> tag (that is, allow PCDATA or <fs> in the content model of <f>). For instance,
<fs><f name=category>noun</f>
<f name=wordForm>Kind</f><f name=proper>minus</f>
<f name=agreement>
<fs><f name=gender>neuter</f>
<f name=number>singular</f>
<f name=case>nominative</f>
</fs></f>
</fs>
This solution falls short of being ideal in three respects. First, the content model for <f>exhibits the so-called "mixed content" problem. Although the SGML standard does not prohibit mixing PCDATA and tagged elements in the same content model, mixed content is known to pose problems for some processors and thus many practitioners advise against using mixed content models. Second, when the content model contains PCDATA, every space and linebreak within the contents of the tag is interpreted as part of the data; this makes it impossible to encode feature structures in "pretty-printed" indented formats that transparently reflect the structure of the embedded feature structures. Third, the markup treats all the textual content as the same kind of information, failing to distinguish symbols in closed sets (like noun) from arbitrary strings (like Kind) from universally defined concepts (like minus).
These problems are solved by requiring that all feature values be contained in tags. Therefore, the recommended markup for our example (following TEI P3) is as follows:
<fs><f name=category><sym value=noun></f>
<f name=wordForm><str>Kind</str></f>
<f name=proper><minus></f>
<f name=agreement>
<fs> <f name=gender><sym value=neut></f> <f name=number><sym value=sg></f><f name=case><sym value=nominative></f>
</fs></f>
</fs>
The content model for the definition of <f> in TEI P3 allows for the value of a feature to be any of the following:
In this section, we justify the way in which we express the possibility that a feature may have more than a single value. We also justify our method of indicating that a feature structure may have any of several different combinations of features. Finally, we justify our method of specifying that the value of a particular feature is other than some specified value.
Certain features that are used for linguistic analysis are understood to have more than one simple value. For example, a coordinate compound phrase such as Bob and Carol may be analyzed as having a "members" feature, whose value is a list of the phrases that are coordinated. Similarly, for a plural-referring expression, one may wish to provide an "index" feature, whose value is a set of numerical indices which abstractly indicate what things the expression refers to. One way of encoding such values would be to provide explicit tags such as <list> and <set> for enclosing their multiple values. For instance:
<f name=members>
<list> <fs type=phrase><f name=category><sym value=noun></f>
<f name=barLevel><nbr value=2></f>
<f name=form><str>Bob</str></f>
</fs> <fs type=phrase><f name=category><sym value=noun></f>
<f name=barLevel><nbr value=2></f>
<f name=form><str>Carol</str></f>
</fs></list>
</f>
<f name=index>
<set><nbr value=37><nbr value=128><nbr value=354></set>
</f>
However, such use of <list> and <set> tags, especially if <list> and <set> are permitted to nest within each other, provides for more descriptive power than is needed for linguistic representations. This is because whenever a list is contained as a value within another list of values, it does not do so directly but indirectly as the value of a feature within a feature structure in the original list. For instance, consider the coordinate compound phrase Bob and Carol and Ted and Alice, in which the members are the two compound subphrases Bob and Carol and Ted and Alice (one of eleven possible syntactic analyses of the whole phrase). The encoding of this would embed two <list>s (for the subphrases) within a <list> (for the whole phrase). However, the embedding is not direct; the members feature of the whole phrase would contain a list of two feature structures that would in turn have a members feature containing a list.
We conclude, therefore, that it is not necessary to provide a method of allowing a set or list to occur directly as an element of another set or list. We can then simplify the encoding of set and list values by providing the <f> tag with an attribute called org (for "organization"). Its possible values are drawn from "unit", "list", "set", and "bag", where a bag is defined as a collection of values that may contain repetitions but in which the order of the values is not significant. Thus, we encode the list and set values in our original examples as follows:
<f name=members org=list>
<fs type=phrase><f name=category><sym value=noun></f>
<f name=barLevel><nbr value=2></f>
<f name=form><str>Bob</str></f>
</fs> <fs type=phrase><f name=category><sym value=noun></f>
<f name=barLevel><nbr value=2></f>
<f name=form><str>Carol</str></f>
</fs></f>
<f name=index org=set>
<nbr value=37><nbr value=128><nbr value=354>
</f>
In this section, we justify our method of indicating that a feature structure may have any of several different combinations of features and that a feature may have any of several different combinations of values. We also justify our method of specifying that the value of a particular feature is other than some specified value.
First, consider the problem of representing alternative values for a given feature, where we either do not know which value the feature has, or we wish to indicate explicitly that the structure containing that feature is ambiguous. For example, suppose that we wish to encode the fact that the case feature of the German noun Kind may have either the value nominative or the value accusative (where these values do not exhaust all the possible values for the case feature, so that the <any> tag cannot be used). One way that one might try to do this is simply to list both values, as in:
<f name=case>
<sym value=nominative>
<sym value=accusative>
</f>
However, this method of encoding multiple feature values has been reserved for the situation in which the feature is defined as taking a list or set of values, and we assume that case is not such a feature. Rather, we assume that case is defined as taking only a single value.
Thus it seems reasonable to define a tag which encloses the alternative values that a particular instance of a feature may have. Suppose we call that tag <vAlt> (for "value alternation"). Then the encoding of the case feature becomes:
<f name=case>
<vAlt><sym value=nominative>
<sym value=accusative>
</vAlt></f>
In addition to specifying alternations of values, one may also wish to specify alternations of features within a feature structure, as in encoding the grammatical structure of the English verb form were, which may be understood as having either second person or plural number. Since the potential content of this alternation tag must be different from that of the <vAlt> tag, we must give it another name, for example <fAlt> tag (for "feature alternation"), as follows:
<fAlt><f name=person><sym value=second></f>
<f name=number><sym value=plural></f>
</fAlt>
A more difficult problem is posed by the third-person German pronoun sie, which may be understood as having either nominative or accusative case and as having either singular number and feminine gender or plural number and any gender. How might one encode the grammatical structure of this word as a single feature structure? A first attempt, which makes use of both the <vAlt> and the <fAlt> tags, is the following:
<fs type='word structure' n=sie>
<f name=category><sym value=pronoun></f>
<f name=person><sym value=third></f>
<f name=case>
<vAlt><sym value=nominative><sym value=accusative></vAlt></f>
<fAlt><f name=number><sym value=singular></f>
<f name=gender><sym value=feminine></f>
<f name=number><sym value=plural></f>
<f name=gender><any></f>
</fAlt></fs>
However, since any number of features can combine to form a feature structure, this encoding does not make clear how many feature alternatives there are, and where one alternative ends and the next one begins.[Note 3] One way to specify how many feature alternatives there are and where each one ends and the next one begins would be to insert a special empty tag at the points of demarcation. If we call that tag <delim> (for "delimiter"), the encoding of our example becomes:
<fs type='word structure' n=sie>
<f name=category><sym value=pronoun></f>
<f name=person><sym value=third></f>
<f name=case>
<vAlt><sym value=nominative><sym value=accusative></vAlt></f>
<fAlt><f name=number><sym value=singular></f>
<f name=gender><sym value=feminine></f>
<delim><f name=number><sym value=plural></f>
<f name=gender><any></f>
</fAlt></fs>
This solution, however, does not identify the terms of the alternation (that is, the feature groups which are in alternation) as markup elements with which attributes (such as an id attribute, which is useful to indicate disambiguation) can be associated. To overcome these difficulties, we simply use untyped <fs> tags to enclose each group of features in the alternation. Our encoding for this example is as follows.
<fs type='word structure' n=sie>
<f name=category><sym value=pronoun></f>
<f name=person><sym value=third></f>
<f name=case>
<vAlt><sym value=nominative><sym value=accusative></vAlt></f>
<fAlt> <fs><f name=number><sym value=singular></f>
<f name=gender><sym value=feminine></f>
</fs> <fs><f name=number><sym value=plural></f>
<f name=gender><any></f>
</fs> </fAlt></fs>
Thus the content model for <fAlt> allows both <f>s and <fs>s; the alternation is among all the top-level elements occurring within the <fAlt>.
We face a similar problem of potential ambiguity when there is a value alternation for a feature that takes multiple values. For instance, consider the example given above of a feature named index which olds a set of numbers that give referential indices to the persons or things referred to by some expression. If we had a plural pronoun which ambiguously referred either to referencts 37 and 52 or to referents 128 and 354, we might encode it as follows using a <vAlt> with the empty tag <delim> to delimit the terms of the alternation:
<f name=index org=set>
<vAlt> <nbr value=37> <nbr value=52> <delim> <nbr value=128> <nbr value=354> </vAlt></f>
However, as explained above, we have not adopted such a <delim> tag. Our solution in this case is to normalize the complex <vAlt> into an <fAlt> by distributing the feature specification over both terms of the alternation. Our encoding for this example is as follows:
<fAlt><f name=index org=set>
<nbr value=37> <nbr value=52></f>
<f name=index org=set>
<nbr value=128> <nbr value=354></f>
</fAlt>
Next, suppose that we wish to represent the value for a feature in a particular feature structure as being distinct from some specific value; for instance, that the value for case is distinct from "nominative". One possibility would be to provide a <neg> (for "negation") tag as part of the content model for feature values, so that it could be used as in the following example:
<f name=case><neg><sym value=nominative></neg></f>
However, there are a number of reasons not to specify distinctness from a particular value by means of a separate tag such as <neg>. First, it is not desirable to permit <vAlt> within the scope of such a tag. Second, there are other relations of distinctness that are useful to encode besides distinctness from a particular value. For example, for a feature that takes number values, it would be handy to be able to state that the value is greater than (or less than, or greater than or equal to, or less than or equal to) the value specified in the <nbr> tag. More importantly, for feature-structure values, one would like to be able to specify, among other things, that the feature value is any value that is subsumed by the one that actually appears, or is any value that the actually appearing value does not subsume.[Note 4]
These considerations suggest that the specification for distinctness from a particular value should be expressed as the value of an attribute on the value tag itself. We name the attribute rel (for "relation"), and define the property of being distinct from the specified value as the ne (for "not equal") value for the rel attribute. Other relations appropriate for numerical and string values are gt (for "greater than"), ge (for "greater than or equal to"), and lt and le for the "less than" and "less than or equal to" relations. The default value for rel for value tags other than <fs> is eq (for "equal"); for <fs> values, it is sb (for "subsumes"). This means that when the desired feature value is the value actually specified, or in the case of an <fs> value, is any value subsumed by the specified value, the rel attribute can be omitted. Accordingly, our current example may be encoded as follows, and none of our preceding examples need altering to take into account the rel attribute.
<f name=case><sym rel=ne value=nominative>
Of course, this encoding by itself does not state what the possible values for the case feature are. To determine what they are, we need to supplement the feature-structure encoding with a feature system declaration (see section 6) which declares what the possible values of the case feature are. If they are declared to be the symbolic values nominative, genitive, dative, and accusative, then the above encoding is equivalent to the following:
<f name=case>
<vAlt><sym value=genitive><sym value=dative><sym value=accusative>
</vAlt></f>
As argued in section 1, feature structures are a fundamental mechanism for analysis in the field of linguistics, used not only in many subdisciplines of linguistics but also used across a wide variety of competing theories. In fact, "feature structures" have a much wider applicability than just linguistics. They can provide for the encoding of information of nearly any sort, since the data structure in question is the familiar and general one described by Knuth (1968) which consists of "nodes" (here called feature structures) and "fields" (here called features). About such structures, Knuth writes:
... the ideas we have encountered are not limited to computer programming alone; they apply more generally to everyday life. A collection of nodes containing fields, some of which point to other nodes, appears to be a very good abstract model for structural relations of all kinds; it shows how we can build up complicated structures from simple ones, and we have seen that corresponding algorithms for manipulating the structure can be designed in a natural manner. (p. 462)
A similar sentiment is echoed by Shieber (1986) who is writing specifically about the application of feature structures in the representation of grammatical formalisms. After explaining how six different formal approaches to grammar can be handled by the single computational model of unification of feature structures, he says:
In fact, viewed from a computational perspective, it is not surprising that so many paradigms of linguistic description can be encoded directly with generalized feature/value structures of this sort. Similar structures have been put forward by various computer scientists as general mechanisms for knowledge representation (Ait-Kaci 1985) and data types (Cardelli 1984). Thus we have hardly constrained ourselves at all even though limited to this methodology. (p. 10)
Feature structures with features are essentially equivalent to many familiar schemes of data organization like records with fields, objects with attributes, frames with slots, property lists with properties, and even abstract data types with access functions. <fs> and <f> can thus be used to markup records, objects, frames, property lists, or instances of abstract data types, if such a perspective is more to the liking of the encoder. In fact, the tag names <fs> and <f> were deliberately chosen to allow the alternate reading of "field structure" and "field." For instance, the following might be the encoding of a bibliographic record:
<fs type=book><f name=author><str>Goldfarb, Charles</str></f>
<f name=year><nbr value=1990></f><f name=title><str>The SGML Handbook</str></f>
<f name=publisher><str>Clarendon Press</str></f>