Semantic Computing E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 949

Veröffentlichungsjahr: 2011

Beschreibung

Presents the state of the technology and points to future directions for semantic computing

Semantic computing, a rapidly evolving interdisciplinary field, seeks to structure, design, and manipulate computer content to better satisfy the needs and intentions of users and create a more meaningful user experience. This remarkable contributed work examines the art, engineering, technology, and applications of the field. Moreover, it brings together researchers from such disciplines as natural language processing, software engineering, multimedia semantics, semantic Web, signal processing, and pattern recognition in order to provide a single source that presents the state of the technology and points to new breakthroughs on the horizon.

Semantic Computing begins with an introduction that explores the concepts, technology, applications, and future of semantic computing. Next, the book is divided into four parts:

• Part One: Semantic Analysis
• Part Two: Semantic Languages and Integration
• Part Three: Semantic Applications
• Part Four: Semantic Programming and Interface

As readers progress through the book, they,ll learn not only the underlying science, but also the fundamental technological building blocks of semantic computing. Moreover, they,ll discover a variety of cross-disciplinary solutions to current computing and communication problems. Throughout the book, references to the primary literature enable further investigation of each individual topic.

Semantic Computing is ideal for industrial managers, researchers, and engineers seeking to design the next generation of computing systems in order to better meet user needs. It is also recommended as a textbook for senior undergraduate and graduate-level semantic computing courses.

Leseprobe

Table of Contents

Cover

Table of Contents

Editorial Board

Title page

Copyright

PREFACE

CONTRIBUTORS

Chapter 1 Semantic Computing

1.1 CONNECTIONS BETWEEN CONTENT AND INTENTIONS

1.2 SEMANTIC ANALYSIS

1.3 SEMANTIC INTEGRATION

1.4 SEMANTIC SERVICES

1.5 SERVICES INTEGRATION

1.6 SEMANTIC INTERFACE

1.7 SUMMARY

Part 1: SEMANTIC ANALYSIS

Chapter 2 What Computers Need to Know About Verbs

2.1 INTRODUCTION

2.2 KEY ROLE OF VERBS

2.3 USEFUL THINGS TO KNOW ABOUT A VERB

2.4 EXISTING RESOURCES

2.5 WHAT WE STILL WANT

Chapter 3 Content-Based Retrieval of Videos

3.1 INTRODUCTION

3.2 BACKGROUND AND RELATED WORKS

3.3 PROPOSED CBVR FRAMEWORK

3.4 CONCLUSION

Chapter 4 A Semantic and Detection-Based Approach to Speech and Language Processing

4.1 INTRODUCTION

4.2 OVERVIEW OF FIXED-SAMPLE-SIZE DETECTION THEORY

4.3 OVERVIEW OF SEQUENTIAL DETECTION THEORY

4.4 APPLYING SEQUENTIAL DETECTION TO SPEECH UNDERSTANDING: CASE STUDY

4.5 SUMMARY

ACKNOWLEDGMENTS

Chapter 5 Link Analysis in Web Mining: Techniques and Applications

5.1 INTRODUCTION

5.2 KNOWLEDGE MODELS

5.3 MEASURES AND ALGORITHMS

5.4 APPLICATIONS OF LINK ANALYSIS

5.6 CONCLUSIONS

Chapter 6 Conversational Thread Extraction and Topic Detection in Text-Based Chat

6.1 INTRODUCTION

6.2 NATURAL LANGUAGE PROCESSING AND CHAT

6.3 CHAT FEATURES

6.4 THREAD EXTRACTION (OR CONVERSATIONAL DISENTANGLEMENT)

6.5 INFORMATION RETRIEVAL VIA VECTOR SPACE MODEL

6.6 TEXT CLASSIFICATION

6.7 CONCLUSION

Chapter 7 Speaker Recognition and Diarization

7.1 INTRODUCTION

7.2 COMMON APPROACHES TO SPEAKER DIARIZATION AND RECOGNITION

7.3 SPEAKER DIARIZATION

7.4 SPEAKER RECOGNITION

7.5 CONCLUSION

Chapter 8 Machine Learning Methods for Ontology Mining

8.1 INTRODUCTION: ONTOLOGY MINING

8.2 STRUCTURAL LEARNING ALGORITHMS

8.3 DISTANCE-BASED ALGORITHMS

Chapter 9 Visual Ontology Construction and Concept Detection for Multimedia Indexing and Retrieval

9.1 INTRODUCTION

9.2 DESIGNING VISUAL ONTOLOGIES

9.3 ANNOTATING AND MODELING VISUAL CONCEPTS

9.4 APPLICATIONS IN SEARCH

9.5 CHALLENGES AND OPEN ISSUES

9.6 CONCLUSIONS

APPENDIX: ONLINE RESOURCES

Chapter 10 Process Mining and Description

10.1 INTRODUCTION

10.2 PROCESS MINING

10.3 PROCESS DESCRIPTION LANGUAGES

10.4 PROCESS ANNOTATION LANGUAGES

10.5 SUMMARY

Part 2: SEMANTIC LANGUAGES AND INTEGRATION

Chapter 11 Semantic Integration: The Hawkeye Approach

11.1 INTRODUCTION

11.2 BRIEF SURVEY OF SEMANTIC INTEGRATION

11.3 PERSPECTIVES: SEMANTIC INTEGRATION FRAMEWORK

11.4 DLDB: A SEMANTIC WEB QUERY-ANSWERING SYSTEM

11.5 HAWKEYE KNOWLEDGE BASE

11.6 RELATED WORK

11.7 CONCLUSION AND FUTURE WORK

ACKNOWLEDGMENT

Chapter 12 Semantics of Software Modeling

12.1 INTRODUCTION

12.2 MODEL-DRIVEN SOFTWARE DEVELOPMENT AND ONTOLOGY TECHNOLOGIES

12.3 APPLYING ONTOLOGY TECHNOLOGIES IN MODEL-DRIVEN SOFTWARE DEVELOPMENT

12.4 ARCHITECTURE

12.5 CONCLUSION

Chapter 13 Semantic-Driven Component-Based Automated Code Synthesis

13.1 INTRODUCTION

13.2 RELATED WORKS

13.3 CODE PATTERN: COMPONENT-BASED SOFTWARE DEVELOPMENT METHOD

13.4 AI PLANNING-BASED SYNTHESIS

13.5 FUTURE RESEARCH

13.6 SUMMARY

Chapter 14 Semantic Web Services

14.1 INTRODUCTION

14.2 WEB SERVICES

14.3 ADDING SEMANTICS TO WEB SERVICES

14.4 COMPOSITION OF WEB SERVICES BY SCDL

14.5 SUMMARY

Part 3: SEMANTIC APPLICATIONS

Chapter 15 Knowledge Work

15.1 INTRODUCTION

15.2 TOWARD AMBIENT LEARNING

15.3 AMBIENT SEMANTIC COMPUTING: TECHNOLOGY FOR AMBIENT LEARNING

15.4 STATE OF THE ART IN AMBIENT INTELLIGENCE AND SEMANTIC NATURAL LANGUAGE PROCESSING

15.5 SUMMARY AND OUTLOOK

Chapter 16 Searching Videos in Visual Semantic Spaces

16.1 INTRODUCTION

16.2 VISUAL SEMANTIC EXTRACTION

16.3 VISUAL SEMANTICS SCALABLE STORAGE AND INDEXING

16.4 VISUAL SEMANTICS SEARCH EXPERIMENTS

16.5 CONCLUSIONS

Chapter 17 Social and Expert Search in Online Communities

17.1 INTRODUCTION

17.2 PRINCIPLES OF KNOWLEDGE GENERATION ON THE WEB

17.3 “SPREE” COMM\UNITY

17.4 SUMMARY AND OUTLOOK

Chapter 18 Phase Coherence in Conceptual Spaces for Conversational Agents

18.1 INTRODUCTION

18.2 KNOWLEDGE REPRESENTATION

18.3 CONVERSATIONAL AGENTS

18.4 INTUITIVE CHATBOTS

18.5 PATTERN MATCHING VERSUS INTUITIVE MATCHING

18.6 APPLICATION: DIALOGUE WITH COMMUNITY OF EXPERT CHATBOTS

18.7 CONCLUSIONS

Chapter 19 Role of Semantics in Question Answering

19.1 INTRODUCTION TO QUESTION ANSWERING

19.2 OVERVIEW OF SEMANTICS IN QUESTION ANSWERING

19.3 WORD SENSE DISAMBIGUATION

19.4 EXTENDED WORDNET KNOWLEDGE BASE

19.5 LEXICAL CHAINS

19.6 SEMANTIC RELATIONS

19.7 CONTEXTS

19.8 TEMPORAL EXPRESSIONS AND EVENTS

19.9 ONTOLOGIES

19.10 SEMANTIC REASONER FOR QUESTION ANSWERING

19.11 DISCUSSION

Chapter 20 Developing and Using a National Cross-Domain Semantic Web Infrastructure

20.1 SEMANTIC CROSS-DOMAIN CONTENT INFRASTRUCTURE

20.2 METADATA SCHEMAS FOR SEMANTIC WEB

20.3 SYSTEM OF MUTUALLY ALIGNED CROSS-DOMAIN ONTOLOGIES

20.4 FINNISH COLLABORATIVE HOLISTIC ONTOLOGY KOKO

20.5 FINNISH ONTOLOGY LIBRARY SERVICE ONKI

20.6 PILOT APPLICATIONS

20.7 DISCUSSION

ACKNOWLEDGMENTS

Chapter 21 Semantic Analysis for Multimedia Security Application

21.1 INTRODUCTION

21.2 SEGMENTATION

21.3 SHOT BOUNDARY/SCENE CHANGE DETECTION

21.4 VIDEO SUMMARIZATION

21.5 FEATURE-BASED MODELING

21.6 HIGH-LEVEL SEMANTIC MODELING

21.7 CONCLUSION

Part 4: SEMANTIC INTERFACE

Chapter 22 Semantic Languages for Software Engineering

22.1 INTRODUCTION

22.2 SEMANTIC SOFTWARE ENGINEERING

22.3 SEMANTIC PROGRAMMING

22.4 SUMMARY

Chapter 23 From Semantic Objects to Structured Natural Language

23.1 INTRODUCTION

23.2 BACKGROUND AND RELATED WORK

23.3 OBJECT RELATIONAL ALGEBRA

23.4 STRUCTURED NATURAL LANGUAGE

23.5 INTERACTIVE COMPOSITION OF QUERIES IN STRUCTURED NATURAL LANGUAGE

23.6 TRANSLATION FROM NATURAL LANGUAGE TO STRUCTURED NATURAL LANGUAGE

23.7 SUMMARY

Index

IEEE Press

445 Hoes Lane

Piscataway, NJ 08854

IEEE Press Editorial Board

Lajos Hanzo, Editor in Chief

R. Abari M. El-Hawary S. Nahavandi

J. Anderson B. M. Hammerli W. Reeve

F. Canavero M. Lanzerotti T. Samad

T. G. Croda O. Malik G. Zobrist

Kenneth Moore, Director of IEEE Book and Information Services (BIS)

Copyright © 2010 by the Institute of Electrical and Electronics Engineers, Inc.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey. All rights reserved.

Published simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http: www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Semantic computing Phillip Sheu ... [et al.].

p. cm.

ISBN 978-0-470-92087-9 (cloth)

 1. Semantic computing. I. Sheu, Phillip C.-Y.

QA76.5913.S46 2010

006.7—dc22

2009033995

PREFACE

Semantic computing is emerging quickly as an interdisciplinary area that is full of promises. Tremendous amount of research has been done in the past and there is a lot more to be done in the future.

For the past three years, we have tried to give semantic computing a more precise definition; the following is a summary of our attempts, published at various times by the Institute for Semantic Computing (homepage, http://www.isc-home.org).

2007: “Semantic Computing addresses the computing technologies (e.g., artificial intelligence, natural language, software engineering, data and knowledge engineering, computer systems, signal processing, etc.), and their interactions, that may be used to extract or process the Content and Semantics of multimedia, texts, services as well as structured data.”

2008: “The field of Semantic Computing (SC) 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’).”

2008: “Computing facilitated by using the descriptions of content.”

2009: “Semantic Computing is defined 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, etc. 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’).”

Until now, its “definition” is still evolving; perhaps it will not have a precise definition for good. What we know for sure is that “semantics” may play a major role in future computing.

The intention of this book is not trying to define what exactly “semantic computing” is. Rather, it is a humble effort to bring together researchers from several areas, including natural language processing, software engineering, multimedia, semantic Web, and semantic services and share with the reader what we think may contribute to a better definition of semantic computing.

Many subjects are missing in the book. One obvious reason is that we are limited by our knowledge about the broad coverage of semantic computing. Another reason may be that some subjects are already well known in the literature (e.g., data mining, keyword-based search engines). Yet another reason may be that such knowledge does not exist yet (e.g., semantic computer architecture?)

The book is divided into four parts, based on a preliminary architecture of a semantic computing system: semantic analysis, semantic integration, semantic application, and semantic programming and interface.

The book may be considered an attempt to bring together researchers with different backgrounds based on an assumption that we may have worked “together” on a common problem: finding and utilizing the “semantics” to better access or manage “content” of some sort. Hopefully a synergy may be created so we can all work even more closely to solve or address some grand challenges of computing we are facing today.

We would like to thank Ms. Mary Mann and Lisa Van Horn of Wiley for their outstanding editorial support. We thank all authors for contributing their original work to the book and sharing their wisdom with us.

PHILLIP C.-Y. SHEU

HEATHER YU

C. V. RAMAMOORTHY

ARAVIND KOSHI

LOTFI. A. ZADEH

CONTRIBUTORS

Paige Adams, Naval Post Graduate School, Monterey, California

Agnese Augello, Institute of High Performance Computing and Networking, Palermo, Italy

Fadi Almasalha, College of Engineering, Purdue University, West Lafayette, Indiana

Tansu Alpcan, Carnegie Mellon University, Pittsburgh, Pennsylvania

Uwe Assmann, University of Koblenz-Landau, Koblenz, Germany

Faisal Bashir, College of Engineering, Purdue University, West Lafayette, Indiana

Farokh B. Bastani, Department of Computer Science, University of Texas, Dallas, Texas

Christian Bauckhage, Carnegie Mellon University, Pittsburgh, Pennsylvania

Susan Windisch Brown, University of Colorado, Boulder, Colorado

Aljoscha Burchardt, Saarland University, Saarbrücken, Germany

Shih-Fu Chang, Electrical Engineering, Columbia University, New York, New York

Min Chen, Florida International University, Miami, Florida

Shu-Ching Chen, Florida International University, Miami, Florida

Christine Clark, Lymba Corporation, Richardson, Texas

Claudia D’Amato, Universita degli Studi di Bari, Bari, Italy

Colin DeLong, Naval Postgraduate School, Monterey, California

Li Deng, Microsoft Research Corporation, Redmond, Washington

Prasanna Desikan, Naval Postgraduate School, Monterey, California

Jürgen Ebert, University of Koblenz-Landau, Koblenz, Germany

Floriana Esposito, Universita degli Studi di Bari, Bari, Italy

Nicola Fanizzi, Universita degli Studi di Bari, Bari, Italy

Gerald Friedland, ICSI, University of California, Berkeley, California

Jicheng Fu, Department of Computer Science, University of Texas, Dallas, Texas

Salvatore Gaglio, Institute of High Performance Computing and Networking, Palermo, Italy

Arif Ghafoor, College of Engineering, Purdue University, West Lafayette, Indiana

Dave Gibbon, AT&T Research, Middletown, New Jersey

Haitao Gong, University of California, Irvine, California

Rodrigo Capobianco Guido, Institute of Physics at Sao Carlos, University of Sao Paulo, Sao Paulo, Brazil

Iryna Gurevych, Saarland University, Saarbrücken, Germany

Hammad Haseeb, College of Engineering, Purdue University, West Lafayette, Indiana

Jeff Heflin, Lehigh University, Bethlehem, Pennsylvania

Jakob Henriksson, University of Koblenz-Landau, Koblenz, Germany

Eero Hyvönen, Helsinki University of Technology, Helsinki, Finland

Chihiro Ishii, NEC Soft, Koto, Japan

Kenichi Kaneko, NEC Soft, Koto, Japan

Lyndon Kennedy, Columbia University, New York, New York

Ashfaq Khokhar, College of Engineering, Purdue University, West Lafayette, Indiana

Atsushi Kitazawa, NEC Soft, Koto, Japan

Harald Kühn, University of Koblenz-Landau, Koblenz, Germany

Zhu Liu, AT&T Research, Middletown, New Jersey

Craig Martel, Naval Postgraduate School, Monterey, California

Florian Metze, Carnegie Mellon University, Pittsburgh, Pennsylvania

Krzysztof Miksa, University of Koblenz-Landau, Koblenz, Germany

Dan Moldovan, Lymba Corporation, Richardson, Texas

Max Mühlhäuser, Saarland University, Saarbrücken, Germany

Martha Palmer, University of Colorado, Boulder, Colorado

Jeff Z. Pan, University of Koblenz-Landau, Koblenz, Germany

Zhengxiang Pan, Lehigh University, Bethlehem, Pennsylvania

Fernando Silva Parreiras, University of Koblenz-Landau, Koblenz, Germany

Giovanni Pilato, Institute of High Performance Computing and Networking, Palermo, Italy

Behzad Shahraray, AT&T Research, Middletown, New Jersey

Min Shen, Florida International University, Miami, Florida

Phillip C.-Y. Sheu, University of California, Irvine, California

Mei-Ling Shyu, Florida International University, Miami, Florida

Jaideep Srivastava, Computer Science and Engineering, University of Minnesota, Minneapolis, Minnesota

Steffen Staab, University of Koblenz-Landau, Koblenz, Germany

Marta Tatu, Lymba Corporation, Richardson, Texas

Stefano Tinella, University of Koblenz-Landau, Koblenz, Germany

David van Leeuwen, ICSI, University of California, Berkeley, California

Giorgio Vassallo, Institute of High Performance Computing and Networking, Palermo, Italy

Kuansan Wang, Microsoft Research Corporation, Redmond, Washington

Qi Wang, University of California, Irvine, California

Shu Wang, University of California, Irvine, California

Fei Xei, University of California, Irvine, California

I.-Ling Yen, Department of Computer Science, University of Texas, Dallas, Texas

Eric Zavesky, AT&T Research, Middletown, New Jersey

Srdjan Zivkovic, University of Koblenz-Landau, Koblenz, Germany

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.”1 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., Google2 and Windows Live3). 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.4

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.5

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.

1http://www.wikipedia.org.

2http://www.google.com.

3http://www.live.com.

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

5http://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.

Holly gave Tomthe dog.agentrecipientthemedonorrecipienttheme

14.

Holly told Tomabout the dog.agentrecipientthemespeakeraddresseemessage

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., <role fnrole=“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