11.2 Related Work

Hyponym harvesting has attracted a lot of interest. A large number of approaches were developed so far. The approaches can be divided into pattern-based, kernel-based, and document clustering-based [17] methods. A typical text pattern consists of a sequence of words or sentence marks and two placeholder variables labeled with hypernym or hyponym. An example of such a pattern is the Hearst pattern [18], “hyponym and other hypernym.” If matched to the sentence The secretary and other politicians criticized the law, the placeholder variable hyponym would be assigned to secretary, the variable hypernym to politician, and therefore the correct hyponymy relation “secretary is a hyponym of politician” is extracted. Such a surface-based approach is easy to realize and also quite limited. It fails for instance if an additional subclause is inserted, for example, The secretary and, according to our information, a lot of other politicians criticized the law. In this case, the given surface pattern can no longer be used for the extraction of the above-mentioned relation. This problem can be overcome by employing graph-based representations such as dependency trees. The patterns of such an approach are given by dependency subtrees. An approach to learn these patterns automatically was devised by Snow et al. [15]. For that, the path in the dependency tree is extracted, which connects the corresponding nouns with each other. To account for certain keywords indicating a hyponym relation like such (see first Hearst pattern) they added the links to the word on either side of the two nouns (if not yet contained) to the path too. Frequently occurring paths are then learned as patterns for indicating a hyponymy relation.

Another often used approach is the use of structure kernels, usually tree and sequence kernels. Assume that a relation R₁ = R(a1, a2) should be compared with a relation R₂ = R(a1', a2'). Then the following kernels might be applied to determine the estimated similarity of the surrounding tree structures:

• Argument Kernel. a1 is compared with a1', and a2 with a2' for the conformity of their surface representations, lexical heads and entity types (e.g., person or organization) [3].
• N-Gram. Bigrams, trigrams, and so on that show up in the surface representation between a1 and a2 are compared with the corresponding n-grams between a1' and a2' [3].
• Link Sequence. The conformity of the tokens (surface representation/lexical head/type/word class) in the dependency path from argument a1 to a2 with that from a1' to a2' is determined, that is, the ith token of the first path is compared with the ith token of the second [3-5].
• Labels of the Dependency Paths. All labels in the dependency path from a1 to a2 matching the labels of the path from a1' to a2' are determined, independently of their order (bag of words) [3].
• Local Dependency. The conformity of the dependency relations directly connected with the arguments a1 and a1' (a2 and a2', respectively) is determined. This measure can also be computed if no connection can be established between the two relation arguments for R₁ or/and R₂[3].
• Subtree Comparison. The minimum subtrees, which contain both arguments are compared [5,19].

Hyponym extraction approaches based on document clustering usually try to convert the document hierarchy, as determined by a hierarchical clustering method, into a taxonomy [17,20].