Semantic Computing

Chapter 1

Semantic Computing

PHILLIP C.-Y. SHEU

We define semantic computing as a field that addresses the derivation and matching of the semantics of computational content and that of naturally expressed user intentions to help retrieve, manage, manipulate, or even create the content, where content may be anything including video, audio, text, process, service, hardware, network, community, and so on. It brings together those disciplines concerned with connecting the (often vaguely formulated) intentions of humans with computational content. This connection can go both ways: retrieving, using, and manipulating existing content according to user’s goals (do what the user means) and creating, rearranging, and managing content that matches the author’s intentions (do what the author means).

1.1 CONNECTIONS BETWEEN CONTENT AND INTENTIONS

The connection between content and the user can be made via (1) semantic analysis, which analyzes content with the goal of converting it to a description (semantics); (2) semantic integration, which integrates content and semantics from multiple sources; (3) semantic services, which utilize content and semantics to solve problems; and (4) service integration, which integrates different kinds of service to provide more powerful services; and (5) semantic interface, which attempts to interpret naturally expressed user intentions (Fig. 1.1). The reverse connection converts descriptions of user intentions to create content of various sorts via techniques of analysis and synthesis.

Figure 1.1 Architecture of semantic computing.

Note that as most of the information is sent and received through a network, security is needed at multiple levels including data-level [1], communication level [1], database level [2], application level [3] and system (community) level [4]. The flows of information are controlled both horizontally and vertically to assure desirable properties including QoS (quality of services) [5, 6] and integrity.

1. Semantic Analysis—analyzes and converts signals such as pixels and words (content) to meanings (semantics).

2. Semantic Integration—integrates the content and semantics from different sources with a unified model; it also includes languages and methodologies needed for developing semantic applications.

3. Semantic Services—utilize the content and semantics to solve problems, and some applications may be made available to other applications as services.

4. Service Integration—integrates different services to provide more power­ful service.

5. Semantic Interface—allows the user intentions to be described in a natural form.

1.2 SEMANTIC ANALYSIS

Semantic analysis is the process of relating syntactic structures, from the levels of phrases, clauses, sentences and paragraphs to the level of the text as a whole, to their language-independent meanings, removing features specific to particular linguistic and cultural contexts, to the extent that such a project is possible. The elements of idiom and figurative speech, being cultural, must also be converted into relatively invariant meanings.¹ Semantic analysis is the foundation of semantic computing; it provides the information resource for semantic integration and semantic services.

The research areas related to semantic analysis include but are not limited to:

1. Natural language understanding and processing

2. Understanding and processing of texts and multimodal content

3. Understanding of texts, images, videos, and audios

4. Speech recognition

5. Web mining

6. Data mining

7. Process mining

Semantic analysis may be the most developed part among the five layers of semantic computing, but it still has a lot of limitations. Most research on semantic analysis has focused on multimedia data analysis [7–9], text analysis (including shallow semantic parsing [10], latent semantic analysis [11, 12], as well as probability latent semantic analysis [13]), structural data analysis [14], and web analysis [15]. Early attempts at semantic analysis addressed complex problems such as semantic understanding, knowledge representation, and reasoning, and some progress has been reported on the understanding of certain domain-specific stories [16, 17]. The success, however, largely depends on domain-specific knowledge. A more robust approach is yet to be developed.

The output of semantic analysis is a description of content. To be useful, the description has to be machine processable. Several languages have been proposed to support such descriptions, including keywords, ontology, Moving Pictures Experts Group (MPEG), and others. In the case that automatic semantic analysis is difficult, descriptions may be generated manually in the form of annotations.

1.3 SEMANTIC INTEGRATION

Semantic integration considers the descriptions derived from the semantic analysis layer that is presented in different formats and integrates such information before it can be used. Existing work on semantic integration includes:

Database Schema Integration [18, 19]Database schemas may have different structures. Schema integration aims at unifying the matching elements. Various data sources are integrated into a data warehouse.

Data Exchange [20, 21]To enable data exchange, applications need to convert messages between the formats required by different trading partners.

Ontology Integration (or Merging) [22–24]Given two distinct and independently developed ontologies, it produces a fragment that captures the intersection of the original ontologies. This area is similar to that of schema integration but is more difficult in nature due to the rich and complex knowledge representation structures found in ontologies.

Ontology Mapping [25, 26]Ontology mapping could provide a common layer from which several ontologies could be accessed by multiple applications. Ontology mapping is different from integration and merging because it does not try to combine several ontologies into a single, complete one.

Semantic Conflict Resolution [30]This is needed to ensure semantic interoperability among heterogeneous information sources.

1.4 SEMANTIC SERVICES

A major goal of semantic computing is providing more powerful computing services for all kinds of users. Semantic services have been developed in several forms:

Web search, including automatic question answering (Q/A) [32, 33] and information retrieval (e.g., Google² and Windows Live³). Both have attracted significant amount of attention in the past and at present.

Multimedia databases, with a primary focus on content-based retrieval [34].

Domain-specific applications, designed to support interoperable machine-to-machine interactions over a network for specific applications.⁴

1.5 SERVICES INTEGRATION

Although semantic services are useful for different kinds of users, sometime they are limited or insufficient for applications requiring several services working together.

A prerequisite for a set of services to collaborate is their ability to understand the mental model, often described in the form of ontology, of each other and communicate with each other. Mapping between ontologies is a major area of interest where automated and scalable solutions are also sought due to the vast number of services. Service integration [27–29, 31] provides the interoperation methods between different services involved in practical scenarios.

On the other hand, for service integration, a significant gap still exists between specialists and nonspecialists, or among specialists focusing on different aspects of a problem. Traditional web services provide a protocol UDDI to perform resources description, discovery and integration. However, this protocol can only be used by experienced specialists. Automatic composition of services hence is strongly desired.

1.6 SEMANTIC INTERFACE

To achieve the goal of providing more powerful computing services to all kinds of users, a portable and friendly user interface is required. This is especially important when cell phones become more capable. Standard graphical user interface (GUI) techniques such as browsing, menu trees, and online help may be far less appealing for the next-generation applications. Therefore new standards of interface, such as natural language interface, multimodal interface, and visual interface, are becoming increasingly important.

A natural language interface allows people to interact using a form of a human language, such as English, as opposed to a computer language, a command line interface, or a GUI. Natural language interfaces may be designed for understanding either written or spoken texts. Attempts have been made to replace command lines and database queries with some form of natural language queries and to use some natural language syntax for programming languages. The most common problem of a true natural language interface is ambiguity: The same sentence may have multiple interpretations. Another problem is that users often assume that computers can reason as a human being and has the full knowledge as a human being.⁵

A multimodal natural language interface combines natural language input with other forms of input such as gesture. There are several strong reasons for creating an interface that allows voice to be combined with gesture as the input [35]:

Expression is easy.

Voice and gesture complement each other and when used together create an interface more powerful than either modality alone.

Combining speech and gesture may improve the accuracy of recognition and reduce the length of speech, resulting in faster task completion compared to using speech alone.

Users work more efficiently by using speech and gesture together.

In addition to understanding user intentions, a semantic interface should be able to present the result produced by a semantic application in a form that can be easily understood by the user. In online analytical processing (OLAP), for example, it is important to provide a reporting tool on top of the server. Research on visualization allows the user to effectively visualize complex systems of information/data; it is particularly useful for decision making, training, simulation, virtual reality, augmented reality, and wearable computing applications [36].

Semantic programming is essentially another aspect of semantic interface: It allows users to express, in a natural way, their intentions when creating content which may be a program, a video, a process, a document, or others.

1.7 SUMMARY

Some areas of semantic computing have appeared as isolated pieces in various fields such as computational linguistics, artificial intelligence, multimedia, software engineering, database, and services computing. As shown in Figure 1.2, the field of semantic computing glues these pieces together into an integrated theme and addresses their synergetic interactions. For example, it addresses how retrieval of multimedia content may be facilitated by natural language annotations, how embedded texts may be extracted from images, how software may be derived from requirements described in natural language, how security can be added based on contexts, how Web search can be accomplished effectively with a cell phone, and so on.

Figure 1.2 Technical coverage of semantic computing.

This may be the first book ever that attempts to introduce semantic computing as an integrated discipline. While researchers in the past have focused on their individual fields, considering semantic computing as an integrated discipline has the advantage that people may share their approaches in solving common problems. More importantly, more applications require the integration of different types of content and their corresponding tools to address complex requests from the user.

Notes

A part of this chapter is revised from P. C.-Y. Sheu, Editorial Preface, International Journal of Semantic Computing, 1.1:1–9, 2007.

1 http://www.wikipedia.org.

2 http://www.google.com.

3 http://www.live.com.

4 http://www.w3.org/TR/ws-arch/.

5 http://www.usabilityfirst.com/glossary/term_755.txl.

REFERENCES

1. W. Stallings, Cryptography and Network Security: Principles and Practices, Prentice-Hall, Englewood Cliffs, NJ, 1998.

2. S. Castano, M. G. Fugini, G. Martella, and P. Samarati, Database Security, ACM Press/Addison-Wesley, New York, 1995.

3. J. D. Meier et al., Improving Web Application Security, Threats and Countermeasures, Microsoft Corporation, Portland, OR, 2003.

4. R. Anderson, Security Engineering, Wiley, New York, 2001.

5. M. Ni and X. Xiao, Internet QoS: A big picture, IEEE Network, 13(2):8–18, 1999.

6. C. Aurrecoechea, A. Cambell, and L. Hauw, A survey of QoS architectures,Multimedia Systems, 6(3):138–151, Springer Berlin, Heidelberg, 1998.

7. A. Ekin, A. M. Tekalp, and R. Mehrotra, Integrated semantic-syntactic video modeling for search and browsing, IEEE Trans. Multimedia, 6(6):839–851, 2004.

8. S. Bloehdorn, N. Simou, V. Tzouvaras, K. Petridis, S. Handschuh, Y. Avrithis, I. Kompatsiaris, S. Staab, and M. G. Strintzis, Knowledge representation for semantic multimedia content analysis and reasoning, in Proceedings of the Euro­pean Workshop on the Integration of Knowledge, Semantics and Digital Media Technology, 25–26, Paola Hobson, Ebroul Izquierdo, Ioannis Kompatsiaris and Noel E. O’Connor (Eds.): Knowledge-Based Media Analysis for Self-Adaptive and Agile Multi-Media, QMUL, London, 2004.

9. S. Bloehdorn, K. Petridis, C. Saatho, N. Simou, V. Tzouvaras, Y. Avrithis, S. Handschuh, Y. Kompatsiaris, S. Staab, and M. G. Strintzis, Semantic annotation of images and videos for multimedia analysis, in Proceedings of the Second European Semantic Web Conference, 592–607, Gómez-Pérez, Asuncion; Euzenat, Jerome (Eds.): The Semantic Web: Research and Applications, Springer Berlin, Heidelberg, Heraklion, Crete, Greece, 2005.

10. D. Lin, Automatic retrieval and clustering of similar words, paper presented at 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, COLINGACL’98, Montreal, 1998.

11. T. K. Landauer, P. W. Foltz, and D. Laham, Introduction to latent semantic analysis, Discourse Process., 25:259–284, 1998.

12. S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, and R. Harshman, Indexing by latent semantic analysis, J. Am. Soc. Inform. Sc., 41(6):391–407, 1990.

13. C. Ding, A similarity based probability model for latent semantic indexing, in Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 58–65, Fredric Gey, Marti Hearst, Richard Tong (Eds.), ACM Press, Berkeley, 1999.

14. S. Nestrov, S. Abiteboul, and R. Motwani, Extracting schema from semistructured data, in Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, 295–306, Ashutosh Tiwary and Michael Franklin (Eds.), ACM Press, Seattle, 1998.

15. S. Mehmet, S. Akhil, V. Machiraju, and F. Casati, Semantic Analysis of E-Business Operations, Journal of Network and Systems Management, 11(1), 13–37, Springer, New York, 2003.

16. S. Soderland, Learning information extraction rules for semi-structured and free text, Machine Learning, 34(1–3):233–272, 1999.

17. T. K. Landauer and S. T. Dumais, A solution to Plato’s problem: The latent semantic analysis theory of the acquisition, induction, and representation of knowledge, Psychol. Rev., 104:211–140, 1997.

18. C. Batini, M. Lenzerini, and X. Navathe, A comparative analysis of methodologies for database schema integration, ACM Comput. Surv., 18(4):323–364, 1986.

19. J. Hammer, and D. McLeod, An approach to resolving semantic heterogeneity in a federation of autonomous, heterogeneous database systems, Int. J. Intell. Cooperative Inform. Syst., 2:51–83, 1993.

20. R. Fagin, P. G. Kolaitis, R. J. Miller, and R. Popa, Data exchange: Semantics and query answering, in Proceedings of the International Conference on Database Theory (ICDT), 207–224, Diego Calvanese, Maurizio Lenzerini and Rajeev Motwani (Eds.): Database Theory—ICDT 2003, Springer Berlin, Siena, Italy, 2003.

21. J. Madhavan and A. Y. Halevy, Composing mappings among data sources, in Proceedings of International Conference on Very Large Data Bases (VLDB), 29: 572–583, Johann Christoph Freytag, Peter C. Lockemann, Serge Abiteboul, Michael J. Carey, Patricia G. Selinger and Andreas Heuer (Eds.), VLDB Endowment, Berlin, Germany, 2003.

22. D. Calvanese, G. De Giacomo, and M. Lenzerini, A framework for ontology integration, in Proc. of 2001 Int. Semantic Web Working Symposium (SWWS), 303–316, Isabel F. Cruz, Stefan Decker, Jérôme Euzenat, Deborah L. McGuinness (Eds.): The Emerging Semantic Web, Selected Papers from the First Semantic Web Working Symposium, IOS Press, Stanford University, Palo Alto, CA, 2001.

23. A. Doan and A. Halevy, Semantic integration research in the database community: A brief survey, AI Mag., 26(1):83–94, 2005.

24. N. Noy, Semantic integration: A survey of ontology-based approaches, SIGMOD Record, Volume 33, No. 4, 65–70, 2004.

25. Y. Kalfoglou and M. Schorlemmer, Ontology mapping: The state of the art, Knowledge Eng. Rev., 18(1):1–31, 2003.

26. N. F. Noy and M. A. Musen, Evaluating ontology-mapping tools: Requirements and experience, paper presented at the Workshop on Evaluation of Ontology Tools at EKAW’02 (EON2002), Siguenza, Spain, 2002.

27. L. Levine, B. C. Meyers, E. Morris, P. R. H. Place, and D. Plakosh, System of systems interoperability: Final report, SEI TR-004, Carnegie Mellon Software Engineering Institute, Pittsburgh, PA, 2004.

28. J. Park and S. Ram, Information systems interoperability: What lies beneath? ACM Trans. Inform. Syst. (TOIS), 22(4):595–632, 2004.

29. A. M. Ouksel and A. Sheth, Semantic interoperability in global information systems, ACM SIGMOD Record, 28(1):5–12, 1999.

30. S. Ram and J. Park, Semantic conflict resolution ontology (SCROL): An ontology for detecting and resolving data and schema-level semantic conflicts, IEEE Trans. Knowledge Data Eng., 16(2):189–202, 2004.

31. G. Jiang et al., IXO Seedling Project technical report dynamic integration of distributed semantic services, Thayer School of Engineering, Dartmouth College, Hanover, NH, 2002.

32. J. Heflin and J. Hendler, Searching the Web with SHOE, in Artificial Intelligence for Web Search. Papers from the AAAI Workshop, WS-00–01, Bollacker K (Ed.), AAAI Press, Menlo Park, CA, 2000, pp 35–40.

33. E. Brill, S. Dumais, and M. Banko, An analysis of the AskMSR question-answering system, in Proc. Empirical Methods in Natural Language Processing Conference, 10:257–264, Jan Hajiˇc, Yuji Matsumoto (Eds.), Association for Computational Linguistics, Philadelphia, 2002.

34. V. S. Subrahmanian, Principles of Multimedia Database Systems, Morgan Kaufmann, San Francisco, 1998.

35. O. Stock, Natural language in multimodal human-computer interface, IEEE Expert, 9(2):40–44, 1994.

36. S. N. Murphy, V. Gainer, and H. C. Chueh, A visual interface designed for novice users to find research patient cohorts in a large biomedical database, AMIA Annu. Symp. Proc., Volume 2003, 489–493, 2003.

37. Jim Jacobs and Alexander Linden, Technical Report, T-17-5338, Gartner, Inc., http://www.gartner.com/DisplayDocument?doc_cd=109295.

Part 1: SEMANTIC ANALYSIS

Chapter 2

What Computers Need to Know About Verbs

SUSAN WINDISCH BROWN and MARTHA PALMER

2.1 INTRODUCTION

Verbs are generally considered the core of a sentence because they provide complex information about events or situations and about the relationships between the other items in the sentence. In fact, the particular verb used influences these items’ selection, expression, and connection to each other so strongly that they are often called arguments of the verb. Given the crucial role of the verb in correctly processing the meaning of a sentence, an ideal computational lexicon would provide a rich representation of a verb’s semantic and syntactic patterns. In this chapter we will try to define the criteria for such a lexicon, taking into consideration evidence from psycholinguistics, the fluid nature of language, and the needs of various language processing applications. We will review existing lexical resources, including WordNet, VerbNet, PropBank, and FrameNet, and evaluate how well they match these criteria.

Exactly how useful these lexicons will be for current statistical natural language processing (NLP) systems remains an open question. In the glory days of rule-based systems, lexicons played a central role and were often considered the heart of the system. Transfer-based and interlingua-based machine translation systems still rely heavily on rich bilingual or multilingual lexicons that not only pair source-language verbs with their closest translation in the target language but also map each argument of the source-language verb to its closest equivalent in the target language, even when this requires transforming a grammatical role like subject or object into a prepositional phrase or adjunct. However, more recently, natural language processing has striven to escape the bounds of domain-specific applications through the use of statistical techniques which offer the promise of accurate pro­cessing over a wide range of text corpora. The majority of these approaches are supervised, shifting the effort from the hand crafting of grammars and lexicons to the hand annotation of vast amounts of training data. Linguistics expertise goes into developing the guidelines and example sentences that are used by the annotators. The systems are expected to induce appropriate lexical representations for sentences from sets of individual annotated examples.

If all of the lexical knowledge is represented explicitly or implicitly in the annotation, one might ask: What purpose can be served by additional free-standing lexical resources? In addition to the key roles that WordNet, FrameNet, VerbNet, and PropBank play in providing guidance to annotators, as detailed below, there are three other major potential contributions which have yet to be fully realized. The first has to do with actual attainment of the goal of broad coverage, rather than its current illusion. The NLP field is only too familiar with the degradation in performance that occurs when syntactic parsers, for example, those that have been trained on the Wall Street Journal (WSJ), are tested on different corpora. This was highlighted recently when CoNLL 2005 semantic role labeling (SRL) systems trained on the WSJ were tested on the Brown Corpus [1]. The Charniak POStagger degrades by 5%, and the Charniak parser F score by 8%, from 88.25 to 80.84. For the 19 systems participating in the SRL evaluation, there was in general a 10% performance decrease from WSJ to Brown. Unseen vocabulary is a major factor in the performance degradation on new corpora. At the moment the systems cannot extend their coverage successfully to lexical items that do not appear in the training data. This could change through the use of empirical connections between class-based lexical resources and training data examples. Systems could do a better job of handling unseen vocabulary items that occur in these resources in classes that are well represented in the training data by extrapolating from individual examples to classes and then back to other class members. In this way lexicons that provide information about syntactic and semantic properties that are shared between lexical items could provide important class-based backoff guidance.

In addition, these same lexicons could form the basis of empirically based bilingual lexicons derived from parallel proposition banks (as defined in Section 2.4.5) which could improve the range and accuracy of current statistical machine translation systems.

The third major contribution could assist us in moving past the very superficial level of semantic representations currently in use toward much richer representations that can support the drawing of implicit inferences [2]. An example is the following sentence from a Blog document from www.warjournal.org:

While many of the weapons used by the insurgency are leftovers from the Iran-Iraq war, Iran is still providing deadly weapons such as EFPs—or Explosively Formed Projectiles.

In certain circumstances it might be helpful to conclude that the insurgents are in possession of EFPs. This is implicit in the semantics of provide, as used in this sentence, but is not part of a literal interpretation.

These types of inferences could be especially beneficial to information extraction, summarization, textual entailment, and sophisticated question answering and may eventually inform statistical machine translation (MT) systems. This type of inferencing is an as-yet unrealized goal of much of the effort that has gone into developing ontologies such as Mikrokosmos [3], Omega [4], Suggested Upper Merged Ontology (SUMO) [5], Cyc [6], and many more (see Sections 2.3.5 and 2.5). Richer lexical resources with appropriate empirically based connections to such ontologies could lay the cornerstone for the next generation of NLP systems.

2.2 KEY ROLE OF VERBS

That every language has verbs is one of the few truly universal features of language [7]. This fact is not arbitrary: A basic function of language is describing the behavior and properties of objects, a function that manifests itself in syntax through predication. Verbs are the primary means of expressing predication. Indeed, in some languages, the verb often is the only word in a sentence, with participants in the utterance expressed as affixes on the verb, as illustrated by the following example from Arapaho. Verbs thus convey some of the most basic and essential meaning in an utterance.

né′-cih-yihoon-éít [8, p. 17]

then.PAST-to here-go to (TA)-4/3sg

They came after him (The soldiers came after the scout)

The fundamental semantic contribution of verbs is reflected in the pivotal role they play in syntax. Widely divergent theories of syntax recognize the primacy of predication and, hence, of verbs. Generative grammar considers the verb phrase as mandatory [9], and head-driven phrase structure grammar identifies the verb as the head of a sentence [10]. In their book Syntax, Van Valin and LaPolla [11, p. 25] state, Two [distinctions] which play a role in the syntax of every language are the contrasts between predicating elements and non-predicating [NP] elements, on the one hand, and between those NPs and adpositional phrases (prepositional or postpositional phrases) which are arguments of the predicate and those which are not. This statement highlights the fact that the verb is the organizing force of a sentence, tying together the primary participants and identifying those that are essential and those that are peripheral. In the following example, the court is making the ruling about the Libyan agent. The when phrase in square brackets is peripheral in that it provides information that helps locate the killing event temporally and geographically.

The court ruled this senior Libyan intelligence agent planted the bomb that killed 270, mostly Americans, [when the plane bound for New York exploded over Lockerbie, Scotland].

How do verbs do this? In addition to their meaning, or definition, verbs have semantic preferences for certain types of arguments and syntactic preferences for certain types of grammatical structures. For example, we know that the verb give tends to tie together a giver, a recipient, and a thing given, as in the following sentence:

1. Holly gave Tom the dog.

The verb give also frequently occurs in a ditransitive construction, that is, one with a direct object and an indirect object. For this verb, this syntactic pattern expresses the verb’s semantic preferences in a very regular way, allowing us to identify the first object with the recipient and the second object with the thing given. Although as native speakers we intuitively understand these patterns, enabling an NLP system to recognize them is much more difficult. The rewards in terms of increased semantic accuracy and efficiency would make such an effort worthwhile.

2.3 USEFUL THINGS TO KNOW ABOUT A VERB

2.3.1 Definition and Sense Distinctions

Of course, the first thing one would like to know about any word is its meaning, although pinning that down can be very tricky. Dictionaries provide definitions, although a brief glance in any dictionary will show that one word is often considered to have multiple meanings. Frustratingly, the words we use most also seem to have the most sense distinctions, especially in English. Again, although human beings have little trouble understanding a word’s meaning in context, NLP applications have serious problems with this fundamental aspect of language processing. For an NLP system, assigning the appropriate sense to a word is effectively a search process, where the entire space of possible senses for the word has to be explored. The larger and more amorphous that space is, the more difficult the search problem is.

By their very format, dictionaries encourage us to consider words as having a discrete set of senses. However, rather than having a finite list of senses, many words seem to have senses that shade from one into another. Consider the verb draw in the following sentences:

2. He drew his gun.

3. He drew a knife from his sleeve.

4. He drew a dollar from his pocket.

5. He drew a card from the pile.

6. He drew his cup closer.

7. He drew the stick through the sand.

8. He drew the cart through the mud and down the road.

Although the neighbors of each sentence in the list seem to use fairly similar (if not identical) meanings of draw, those more distant in the list seem distinct. Most would agree that the meaning of draw in sentence 2 is different from that in sentence 8, but deciding exactly where one sense ends and another begins is a difficult task.

In making these distinctions, how finely the distinctions should be drawn must also be considered. The lexical resource WordNet (see Section 2.4.2) makes a distinction between break as an event of coming apart, as in

9. The vase broke.

and as an event of becoming dysfunctional, as in

10. The radio broke.

Good arguments can be made for that distinction, such as the difference in entailments with respect to the final state of the object after the event. However, other arguments can be made for considering them in the same sense, such as the ability to describe both these events with the same instance of the verb, as in the following coordination:

11. When the wind toppled the table, the vase broke with a crash and the radio with a sigh of static.

Some have questioned whether WordNet’s fine-grained sense distinctions are appropriate for word sense disambiguation (WSD) or if they are making the search task unnecessarily hard. Ide and Wilks [12] suggest that distinctions on the level of homonyms (typically a very small set) are all that are really needed for most tasks. In addition, there are questions about whether it is reasonable to expect computer systems to accomplish something human beings seem to have difficulty achieving. Interannotator agreement with fine-grained WordNet senses is around 70% [13, 14]. Some tasks, however, seem to require such fine distinctions, such as machine translation into languages like Chinese and Korean that have separate words for fine-grained distinctions.

Cognitive linguistics argues that the various meanings of a polysemous word can form a radial network based on family resemblances, with fuzzy boundaries between the nodes of meaning [15, 16]. In addition, recent psycholinguistic research suggests that what we describe as sense distinctions may rather be overlapping mental representations of meaning [17]. Multiple meanings associated with a word form may overlap to a greater or lesser extent. Subjects asked to access the meaning of a verb in the context of a short phrase reacted more quickly and accurately if they were first shown a phrase involving the same verb with a closely related meaning. In fact, there were discernable differences in reaction time and accuracy between trials with same-sense pairs of phrases, closely related pairs, distantly related pairs, and homonyms. The difference between closely related sense pairs and same-sense pairs was slight, implying that these usages activate the same or largely overlapping meaning representations which could be clustered into a more general verb sense with little meaning loss. Conversely, people reacted to distantly related senses much as they did to homonyms, suggesting that making distinctions between these usages would be useful in a WSD system. These psycholinguistic results and the practical needs of different NLP applications for different levels of sense granularity argue for a flexible resource that would allow systems to draw upon finer- or coarser-grained senses as necessary. OntoNotes (see Section 2.4.6) and SemLink (see Section 2.4.7) represent current efforts to link fine-grained and coarse-grained resources for sense distinctions and semantic roles.

2.3.2 Selectional Preferences for Semantic Roles

Semantic roles, also called thematic roles, refer to general classes of participants in a sentence. Identifying the semantic roles of arguments and adjuncts in a sentence is fundamental to understanding its meaning. In sentence 12 it is not enough to know which thing in the world Holly refers to, we must also know that she is the agent of the action described in the sentence. We must know that the dog is the gift and Tom the recipient instead of the other way around.

12. Holly gave Tom the dog.

Much of this information comes from the interaction of the arguments with the specific verb. Many verbs have strong preferences for combining with certain semantic roles, as we have seen with the verb give. These roles can be described more broadly or more narrowly, depending on the purpose of the description. For example, compare the application of different semantic role schemas in 13 and 14; the first set of role labels for each sentence are broad, traditional labels, and the second set are narrow FrameNet labels:

13.

14.

As you can see, the broad labels would consider the arguments in each sentence to have the same roles, whereas the FrameNet labels would place the arguments in different and much more specific categories. Both approaches have their advantages: Broad labels allow generalization, whereas more specific labels can be associated with precise, fine-grained inferences.

Different senses of the same verb can have different semantic role preferences. Knowing those preferences and how well various arguments fit with those preferences can help select the appropriate verb sense. For example, most senses of give prefer an animate subject, such as a person, an animal, or a corporation, which fit with the agentive role the subject plays. When the subject is inanimate, as in

15. Rich food gives him indigestion.

16. The farm gave us a bumper crop.

the choice of senses narrows, specifically to those that prefer a nonagentive subject, making more likely the selection of the appropriate sense be the source of.

Knowing the selectional preferences of a verb sense can help identify the role being played by an argument in the sentence. For example, the role of the dog is quite different in the following sentences:

17. Holly told Tom about the dog.

18. Holly scared Tom with the dog.

With the verb tell, we know a sentence is likely to contain a message or topic. With scare, a prepositional phrase is more likely to present the instrument, or the thing causing the scare, than a topic.

Resolving ambiguous parses could also benefit from identifying the selectional preferences of the verb. For example, knowing that the verb dig prefers instrument arguments but the verb kiss does not could lead a parser to correctly attach the prepositional phrase in 19 to the verb, while attaching it to the object in 20:

19. Holly dug the hole with the new shovel.

20. Holly kissed the man with the new shovel.

Correctly identifying the semantic roles of the sentence constituents is a crucial part of interpreting text, and, in addition to forming a component of the information extraction problem, it can serve as an intermediate step in machine translation, automatic summarization, or question answering.

2.3.3 Syntactic Preferences (Subcategorization Frames)

A verb tends to occur in certain syntactic patterns and not others. These syntactic preferences, or subcategorization frames, are another way to classify verbs and can be used in similar ways to semantic preferences. For example, syntactic preferences can be different for different senses of a verb and so can be used to make sense distinctions. The ditransitive pattern in 21 is associated with the transfer possession sense of give, whereas the intransitive pattern is associated with the yield or open senses of give in 22 and 23:

21. Holly gave Tom the dog.

22. Holly won’t give under pressure.

23. The doors gave onto the terrace.

Syntactic preferences often go hand in hand with semantic preferences. Certain syntactic patterns become so associated with particular semantic roles that one can infer these roles for the arguments of a novel verb. For example, the ditransitive is so associated with transfer verbs and the roles of agent, recipient, and theme that one can infer a great deal of the information in a sentence like 24, even without being familiar with the verb pleem:

24. He pleemed him the shirt.

This association of syntactic patterns with semantics is one of the basic insights of construction grammar [18].

Some verbs share similar semantic and syntactic preferences and can be grouped together based on those preferences, as has been done in Levin’s [19] verb classes and the VerbNet hierarchy based on those classes (see Section 2.4.4). Group membership can be used as another feature in supervised learning, for backoff purposes, or to make certain kinds of inferences. Recognizing similar semantic and syntactic behavior may help with processing novel verbs as well.

2.3.4 Collocations

Collocation refers to words that occur together more often than one would expect by chance. The co-occurring words often stand in a certain syntactic relation to each other, such as the verb–object relation in give a damn or give a reception. Algorithms that use windowing techniques, such as looking at words within two positions to the right or left of a word, are actually targeting collocations. A lexicon that associated collocations with the senses of a word would provide more directly useful information for tasks such as parsing or word sense disambiguation. For example, a machine-learning program that relies on windowing to identify word sense might not encounter enough (or any) instances of give a damn in its training materials to identify this meaning of give in new text. In addition, with a phrase like give a good God damn, the pertinent word damn occurs outside the typical two- or three-word window for give, making windowing ineffective in catching this collocation. By using a resource that provides verb–argument collocations, a system would improve its ability to recognize word meanings in infrequent but reliable collocations. (See Section 2.5 for some examples of resources that provide collocational information.)

2.3.5 Class Membership and Semantic Neighbors

Automatically recognizing the semantic similarity of lexical items has great potential for improving such tasks as information retrieval and question answering. One way to access such information is to link word senses to an ontology, where sisterhood relations and links to higher nodes inform about class memberships and semantic neighbors. In addition, connection to an ontology with a rich knowledge base could also enable the type of inferencing useful for more complex language processing tasks.

Cyc represents one effort to supply such an ontology, an ambitious project that has been 25 years in the making. The open-source version, OpenCyc, contains 47,000 concepts and 306,000 facts, while ResearchCyc adds a lexicon and more semantic information about the concepts. Other ontology projects include SUMO, which has merged several domain-specific ontologies under a broad, general upper model. The ontology has been mapped to the WordNet lexicon and includes 70,000 axioms, many from the domain-specific ontologies. The Omega ontology has been assembled semiautomatically by merging a variety of sources, including Princeton’s WordNet, New Mexico State University’s Mikrokosmos, and a variety of upper models. OntoNotes sense groupings (see Section 2.4.6) are being used to fill in the middle level of the existing ontology and to construct an eventive portion of the ontology in a bottom-up manner. However, none of these resources has yet achieved the breadth and depth of knowledge necessary for seamless domain-independent reasoning.

2.4 EXISTING RESOURCES

2.4.1 Dictionaries

The most familiar lexical resource is, of course, the dictionary. Traditionally, dictionaries provide definitions of words, often in an hierarchical structure that lists closely related senses of a word as subentries of a more general, encompassing sense. Although example sentences are sometimes included, syntactic information is usually limited to part of speech and whether a verb sense is used in a transitive or intransitive structure. These resources were of limited use for NLP tasks until machine-readable resources became available, such as the Oxford English Dictionary, Cambridge Dictionaries Online, and Longman Dictionary of Contemporary English (LDOCE). LDOCE has been widely used for research on word sense disambiguation. Its definitions are written in a restricted vocabulary and word senses receive a subject field label, which can act as a broad domain tag. The LDOCE NLP database is a version specifically designed for NLP.

2.4.2 WordNet

Created by George Miller and his team at Princeton University, WordNet [20, 21] is a large electronic database organized as a semantic network built on paradigmatic relations. In WordNet, nouns, verbs, adjectives, and adverbs are grouped into sets of cognitive synonyms (synsets); words and synsets are interrelated by means of lexical and conceptual–semantic relations, including super-/subordinate relations, part–whole relations, antonymy, and lexical entailment. The resultant network structure makes it possible not only to identify the meanings of a word but also to quantify its semantic similarity to other words.

WordNet’s format makes it a useful tool for computational linguistics and natural language processing. Because it is freely and publicly available for download, WordNet has become a de facto community standard for the English lexicon, providing a commonsense inventory for language processing systems. Richer lexical resources, such as FrameNet [22] and VerbNet [23, 24], all provide links to WordNet synsets.

WordNets have been created for dozens of genetically and typologically unrelated languages. EuroWordNet (EWN) is a multilingual lexical database patterned on the original. It connects WordNets from eight European languages, including Spanish, German, English, and Czech, at a conceptual level. Other WordNets are being developed for languages as diverse as Hebrew, Japanese, Chinese, and Tamil. As these WordNets are linked to the Princeton WordNet, they have interesting potential for use in automatic machine translation.

WordNet’s sense inventory is very fine grained, and automatic word sense discrimination has been limited when it has relied exclusively on WordNet’s structure. Human annotators have trouble distinguishing such fine-grained senses reliably; in fact, interannotator agreement with WordNet senses is only around 70% [13, 14]. It is understandable that WSD systems would have difficulty surpassing this upper bound. Comparisons of system performance when using WordNet senses and when using more coarse-grained senses show a significant improvement with the coarse-grained senses [2b, 25].

WordNet can also be used to judge or measure the semantic relatedness of verbs. Synonyms can be found directly in a verb’s synset, of course, but more wide-ranging comparisons and groupings can be made. The super-/subordinate relationships allow verbs to be placed in semantic groups based on sisterhood relations. In addition, WordNet identifies troponym links between verbs, which specify such relations as manner, intensity, or degree of force. For example, doze is related to sleep by a troponym relationship based on intensity. These links, along with the super-/subordinate links, provide a means of quantifying the similarity between two verbs. By finding the nearest common node for two words and counting the number of edges that connect the two through that node, one can roughly quantify the semantic distance between the words. Various algorithms that refine this method have been used to compute semantic distance for nouns and verbs [26]. The results were less satisfactory for verbs because the hierarchy for verbs is more shallow than for nouns and its network of other relations is less complex.

2.4.3 FrameNet

FrameNet [22] consists of collections of semantic frames, lexical units that evoke these frames, and annotation reports that demonstrate uses of lexical units in these frames. Based on a theory of frame semantics, each semantic frame describes a situation type and the elements that are involved in that situation, such as participants or instruments. These frame elements can be considered very fine-grained semantic roles. Frame elements are classified in terms of how central they are to a particular frame, distinguishing three levels: core, peripheral, and extrathematic. FrameNet is designed to group lexical items based on frame semantics rather than their use in similar syntactic patterns. Therefore, sets of verbs with similar syntactic behavior may appear in multiple frames, and a single FrameNet frame may contain sets of verbs with related senses but different subcategorization properties.

Semantic frames are related to one another via a set of possible relations, such as inherits from and uses. For example, the Telling frame inherits from the Statement frame, which in turn inherits from the Communication frame. The Reporting frame uses the Communication frame, which indicates only partial inheritance. In this way, FrameNet provides an ontology of sorts which could be used for the creation of entailment rules or inferencing.

FrameNet places a primary emphasis on providing rich, idiosyncratic descriptions of semantic properties of lexical units in context and making explicit subtle differences in meaning. As such it could provide an important foundation for reasoning about context-dependent semantic representations. Shen and Lapata [27] show that FrameNet has the potential to improve question-answering systems. However, they also point out that many more lexical items need to be covered in FrameNet for the resource to be practical for this purpose. In addition, the large number of frame elements and the current sparseness of available annotations for each one has been an impediment to automatic semantic role labeling. In combination with other resources, FrameNet has proved useful, such as in the construction of a knowledge base for semantic parsing [28].

2.4.4 VerbNet

VerbNet [23, 24] consists of hierarchically arranged verb classes inspired by and extended from the classes of Levin [19]. These classes were based on the insight that verbs with similar semantics often occur with a similar group of syntactic frames. Each class and subclass is characterized extensionally by its set of verbs and intensionally by a list of the arguments of those verbs and syntactic and semantic information about the verbs. This resource provides several types of information that we mentioned in Section 2.3, including a verb’s selectional preferences for certain thematic roles, its syntactic preferences, and its semantic neighbors as determined by its VerbNet class membership. Additional information about sense distinctions can be inferred from a verb’s membership in multiple classes or from the links provided from the verb to the appropriate WordNet synset.

VerbNet’s argument list consists of 29 thematic roles which are both broader and more vague than the hundreds of frame elements found in FrameNet. These roles provide less nuance than FrameNet elements but allow greater generalization across verb classes. Slightly more nuance is provided by selectional restrictions on some arguments, which are expressed using 36 binary types. As part of the SemLink project (see Section 2.4.7), VerbNet has made available a mapping between VerbNet thematic roles and FrameNet elements (e.g., Speaker vnrole=Agent />), which should allow the user to choose between the fine- and coarse-grained interpretations.

Each class contains the syntactic frames that are compatible with the member verbs and the semantic predicates that correspond to those frames. The semantic predicates describe the participants during various stages of the event covered by the syntactic frame and provide class-specific interpretations of the thematic roles. VerbNet now covers approximately 5700 verb senses, which slightly surpasses FrameNet’s coverage of 4100 verb senses but which falls far short of WordNet’s 11,500 verbs. A primary emphasis for VerbNet is the coherent syntactic and semantic characterization of the classes, which will facilitate the acquisition of new class members based on observable syntactic and semantic behavior. The pairing of each syntactic frame in a class with a semantic representation is a unique feature of VerbNet that emphasizes the close interplay of syntax and semantics.

VerbNet has been used as a resource for a variety of natural language processing tasks. It has been used most widely for automatic semantic role labeling with both supervised and unsupervised systems [29–31]. However, it has also provided the means to automatically generate representations for previously unknown verbs in a spoken language dialog system [32], contributed to the construction of a knowledge base for semantic parsing [28], and served as a component in a question-answering system [33].

2.4.5 PropBank

PropBank focuses on the argument structure of verbs and provides a corpus annotated with semantic roles, including participants traditionally viewed as arguments and adjuncts. The 1M word Penn Treebank II Wall Street Journal corpus has been successfully annotated with semantic argument structures for verbs and is available via the Linguistic Data Consortium as PropBank I [2a]. As part of the OntoNotes project (see Section 2.4.6) and a National Science Foundation (NSF) grant, Towards Unified Linguistics Annotation, a further 630K words are being annotated with PropBank argument labels, including parts of the Brown corpus and spoken text from the GALE Broadcast News and Broadcast Conversation corpora.

PropBank annotation provides argument labels, annotations of modifiers, and coreference chains for empty categories. The primary goal is providing consistent argument labels across different syntactic realizations of the same verb, as in

[ARG0 John] broke [ARG1 the window]

[ARG1 The window] broke.

As this example shows, semantic arguments are tagged with numbered argument labels, such as Arg0, Arg1, and Arg2, where these labels are defined on a verb-by-verb basis. PropBank annotation also assigns functional tags to all modifiers of the verb, such as MNR (manner), LOC (locative), TMP (temporal), DIS (discourse connectives), PRP (purpose) or DIR (direction), and others. Finally, PropBank annotation identifies antecedents for empty arguments of the verbs, as in the following example:

Each new trading roadblock is likely to be Beaten by institutions seeking better ways *trace* to serve their high-volume clients.

Arg0: *trace* -> institutions

REL: serve

Arg2: their high-volume clients

The subject of the verb serve in this example is represented as an empty category [*] in TreeBank. In PropBank, all empty categories which could be coreferred with an NP element within the same sentence are linked in coreference chains. Here, the trace would be labeled as the Arg0 of the verb serve and linked to the NP institutions occurring earlier in the sentence.

Although argument labels are verb specific (i.e., Arg1 can mean something different for each verb), certain trends make generalizations across verbs possible. For example, Arg0 predominantly represents a prototypical agent (an agent, a cause, etc.), while Arg1 generally represents a prototypical patient (a patient, theme, topic, etc.). This type of thematic role scheme can thus be considered the most coarse grained among the resources we have described here.

For each verb, PropBank supplies one or more role sets, each corresponding to a very general sense of the verb. For example, excluding verb particle constructions, leave has two role sets, one for the sense move away from and one for the sense give. Compared to 14 senses in WordNet and 5 in the OntoNotes groupings, PropBank’s 2 senses make it again the most coarse-grained resource.

PropBank has predominantly been used for automatic semantic role labeling. Although one can generalize across the referents of Arg0 and Arg1 fairly well, as noted above, Arg2 through Arg5 vary a great deal in the type of semantic roles they refer to. Some researchers have therefore first translated the PropBank argument labels of a corpus into the VerbNet thematic roles, then trained their SRL systems using these data [30, 31]. Another application of PropBank has been as a very coarse-grained sense inventory for verb sense discrimination systems [35].

2.4.6 OntoNotes

The OntoNotes project is annotating a large corpus (300K words) with multiple layers of semantic and syntactic information [36]. The corpus includes the TreeBanked portion of the WSJ, the Broadcast News corpus, and portions of the Brown corpus. In addition to TreeBanking, the corpus is being annotated with PropBank roles, coreference information, and coarse-grained noun and verb senses.

The coarse-grained senses are developed by manually clustering related WordNet senses. As of 2007, the 1400 most frequent verbs in the data had been grouped and double annotated with 89% interannotator agreement (averaged across types). Training both maximum entropy and support vector machine models on these new data, Chen et al. [37] report accuracy for verbs comparable to that of humans.

Each grouped sense lists the WordNet senses on which it is based, provides a gloss and example sentences, and maps to corresponding VerbNet classes and FrameNet frames, if any exist. Subcategorization frames and semantic classes of arguments play major roles in determining the groupings [38]. Examples can be found at http://verbs.colorado.edu/html_groupings/. As part of the OntoNotes project, the grouped verb senses are also being used to build the eventive portion of the Omega ontology, which should eventually allow access to additional information about a verb sense, such as feature inheritance and semantic neighbors.

2.4.7 SemLink

SemLink links together several of the lexical resources we have discussed here via a set of mappings. It currently links PropBank role sets, FrameNet frames, OntoNotes sense groupings, and WordNet senses. These mappings make it possible to combine the different types of information provided by these resources for more complex tasks, such as inferencing. Additional mappings between FrameNet and VerbNet thematic roles and between verb-specific PropBank arguments and VerbNet thematic roles allow researchers to translate the semantic role labels of one corpus to that of another, resulting in more data in the preferred annotation scheme.

The mapping between VerbNet and PropBank consists of two parts: a lexical mapping and an annotated corpus. The lexical mapping is responsible for specifying the potential mappings between PropBank and VerbNet for a given word, but it does not specify which of those mappings should be used for any given occurrence of the word. That is the job of the annotated corpus, which for any given instance gives the specific VerbNet mapping and semantic role labels. This can be thought of as a form of sense tagging. Where a PropBank frame maps to several VerbNet classes, they can be thought of as more fine-grained senses, and labeling with the class label corresponds to providing a sense tag label. The lexical mapping was used to automatically predict VerbNet classes and role labels for each instance. Where the resulting mapping was one to many, the correct mapping was selected manually [39].

The SemLink VerbNet/FrameNet mapping consists of three parts. The first part is a many-to-many mapping of VerbNet classes and FrameNet frames. It is many to many in that a given FrameNet lexical unit can map to more than one VerbNet member, and more frequently, a given VerbNet member can map to more than one FrameNet frame. The second part is a mapping of VerbNet semantic roles and FrameNet frame elements. These two parts have been provided in separate files in order to offer the cleanest possible formatting. The third part is the PropBank corpus with mappings from PropBank frame set IDs to FrameNet frames and mappings from the PropBank arguments to FrameNet frame elements.

SemLink mappings are available for download at verbs.colorado.edu/semlink or for browsing through the Unified Verb Index at http://verbs.colorado.edu/verb-index/.

2.5 WHAT WE STILL WANT

Lexical resources for NLP have advanced considerably in the last couple of decades, especially in the crucial area of verb-specific semantic and syntactic information. Linguistically rich and reasonably accurate features gathered from these resources are now being used to produce shallow semantic representations that are improving such tasks as automatic word sense disambiguation, semantic role labeling, question answering, summarization, and information extraction. Many of the resources described in Section 2.4 are being revised and expanded. In addition, efforts such as Global WordNet and SemLink are mapping information between resources to give researchers greater coverage and flexibility. With those improvements, we can expect further advances in the performance and portability of various NLP systems.

As encouraging as these expansion and linking efforts are, we are still a long way from deep semantic representations that could be used as a basis for knowledge representation and reasoning. We see several unaddressed needs from our list of desirable lexical information. First, comprehensive treatment of multiword expressions is lacking, despite their pervasiveness in English and other languages. Several resources, including PropBank, FrameNet, WordNet, and the OntoNotes groupings, attempt to cover verb particle constructions (e.g., go down, as in The system went down again), and some include idioms. However, information about collocations is minimal. The LDOCE now associates some collocation information with certain lexical entries, but more widespread coverage is needed to truly make use of this information. One pattern for such a resource can be found in DiCo, a French language resource that lists collocations for each lexical entry [40].

Recent research has suggested that certain syntactic patterns carry meaning themselves, such as the ditransitive pattern described in Section 2.3 [18]. These grammatical constructions can account for many of the novel uses of lexical items that confound NLP systems. For example, I faxed him the letter was at one time a novel use of fax. Understanding and identifying grammatical constructions would enable us to extract some information about an activity even when the verb is unfamiliar, improving our coverage of novel items. A resource somewhat like a dictionary could list such constructions and their meanings and perhaps identify their preferences for certain classes of verbs.

Another welcome innovation would be a means of flexibly interpreting the sense divisions of a word. As mentioned in Section 2.2, verb senses often grade from one to another. In addition, one context may encourage a fine-grained interpretation of a word, while another may suggest a broader definition. A gradable or flexible meaning representation would more accurately reflect actual usage and improve our adaptation for sense extensions. Such a representation may also facilitate the connection of lexical items to an ontology. SemLink, which provides mappings from coarse-grained PropBank frame sets to more fine-grained VerbNet and FrameNet frames and eventually WordNet senses, is a first step in that direction.

Although ontology construction has been underway for some time, the creation of a practical, wide-coverage, knowledge-rich resource has remained elusive. The connection of a conceptual ontology to a lexicon is essential to its usefulness for NLP. However, the coverage of verbs has been particularly troublesome. Verbs do not lend themselves well to a strict hierarchy, since many refer to complex sequences of actions and results. Yet the usefulness of a well-constructed ontology is apparent for the many NLP tasks that require reasoning and making inferences.

The most intractable problem concerning verbs is the inability of computer systems to recognize new or unusual extensions of meaning. Computers function best when supplied with static knowledge sources, such as current dictionaries. The inherent