26732443
Preventing False Inferences
I I n t r o d u c t i o n In cooperative man-machine interaction, it is taken as necessary that a system truthfully and informatively respond to a user's question. It is not, however, sufficient. In particular, if the system has reason to believe that its planned response nfight lead the user to draw an inference that it knows to be false, then it must block it by nmdifying or adding to its response. The problem is that a system neither can nor should explore all eonchtsions a user might possibly draw: its reasoning must be constrained in some systematic and well-motivated way. Such cooperative behavior was investigated in [5], in which a modification of Griee's Maxim of Quality is proposed: Grice's Maxim of QualityDo not say what you believe to be false or for which you lack adequate evidence. Joshi's Revised Maxim of Quality If you, the speaker, plan to say anything which may imply for the hearer something that you believe to be false, then provide further information to block it. This behavior was studied in the context of interpreting certain definite noun phrases. In this paper, we investigate this revised principle as applied to question answering. In particular the goals of the research described here are to: I. characterize tractable cases in which the system as respondent (R) can anticipate the possibility of the user/questioner (Q) drawing false conclusions from its response and can hence alter or expand its response so as to prevent it happening; 2. develop a formal method for computing the projected inferences that Q may draw from a particular response, identifying those 1This work is partially supported by NSF Grants MCS 81-07290, MCS 8.3-05221, and [ST 83-11,100. 2At present visiting the Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104. factors whose presence or absence catalyzes the inferences; 3. enable the system to generate modifications of its response that can defuse possible false inferences and that [nay provide additional useful information as well. Before we begin, it is important to see how this work differs from our related work on responding when the system notices a discrepancy between its beliefs and those of its user [7, 8, 9, 18]. For example, if a user asks • How many French students failed CSEI21 last t e rm? ' , he shows that he .believes inter alia that the set of French students is non-empty, that there is a course CSEI21, and that it, was given last term. If the system simply answers " N o n e ' , he will assume the system concurs w'ith these b~diefs since the answer is consistent with them. Furthermore, he may conclude that French students do r;'d.her well in a difficult course. But this may be a false conclusion if the system doesn' t hold to all of those beliefs (e.g., it doesn' t know of any French students). Thus while the system's assertion "No French students failed CSEI21 last term" is true, it has misled the user (1) inlo believing it concurs with the user's beliefs and (2) into drawing additional false conclusions from its response. 3 The differences between this related work and the current enterprise are that: 1. It is no_~t assumed in the current enterprise that there is any overt indication that the domain beliefs of the user are in any way at odds with those of the system. 2. In our related work, the user draws a false conclusion from what is said because the presuppositions of the response are not in accord with the system's beliefs {following a nice analysis in [lO]). In the current enterpri.~e, the us~,r draws a false conclusion from what is said because the system's response behavior is not in accord with the user's expectations. It. may or may not also 31t is a feature of Kaplan's CO-OP system [7] that it point~ out the discrepancy by saying "| don't know of any French students °
9264341
Discourse Relations: A Structural and Presuppositional Account Using Lexicalised TAG
We show that discourse structure need not bear the full burden of conveying discourse relations by showing that many of them can be explained nonstructurally in terms of the grounding of anaphoric presuppositions (Van der Sandt, 1992). This simplifies discourse structure, while still allowing the realisation of a full range of discourse relations. This is achieved using the same semantic machinery used in deriving clause-level semantics.
5138605
String Adjunct Grammars
In this paper, we have introduced a new style of formal grammars called String Adjunct Grammars (AG). The rules in an AG have a considerably different formal character as compared to the 'rewrite rule' in a Phrase Structure Grammar (PSG). Such a study of formal grammars of different styles (i.e., formal character of rules) is of great interest because each style is well suited for characterizing certain aspects of natural language structure and is awkward for characterizing certain other aspects. Several subclasses of AG's motivated by strong linguistic considerations have been studied, comparing them with PSG's. Linguistic relevance of these grammars (and other gram mars suggested by this study) has been discussed at the end.
38151734
Role of Constrained Computational Systems in Natural Language Processing
Abstract The use of constrained formal/computational systems just adequate for modeling various aspects of language—syntax, semantics, pragmatics and discourse, among others, has proved to be an effective research strategy leading to deep understanding of these aspects, with implications to both machine processing and human processing. This approach enables one to distinguish between the universal and stipulative constraints. This is in contrast to an approach where we start with the most powerful formal/computational system and then model the phenomena by making all constraints stipulative in a sense. The use of constrained systems for modeling leads to some novel ways of describing locality of structures and brings out the relationship between the complexity of description of primitives and local computations over them. These ideas serve to unify theoretical, computational and statistical aspects of natural languages processing in AI. It is expected that this approach will be productive in other domains of AI.
34341997
Local Transformations
2954113
Tree Adjunct Grammars
In this paper, a tree generating system called a tree adjunct grammar is described and its formal properties are studied relating them to the tree generating systems of Brainerd (Information and Control14 (1969), 217-231) and Rounds (Mathematical Systems Theory 4 (1970), 257-287) and to the recognizable sets and local sets discussed by Thatcher (Journal of Computer and System Sciences1 (1967), 317-322; 4 (1970), 339-367) and Rounds. Linguistic relevance of these systems has been briefly discussed also.
7627284
Information Retrieval and the Semantic Web
Information retrieval technology has been central to the success of the Web. For semantic web documents or annotations to have an impact, they will have to be compatible with Web based indexing and retrieval technology. We discuss some of the underlying problems and issues central to extending information retrieval systems to handle annotations in semantic web languages. We also describe three prototype systems that we have implemented to explore these ideas.
3018861
Using peer-to-peer data routing for infrastructure-based wireless networks
A mobile ad-hoc network is an autonomous system of mobile routers that are self-organizing and completely decentralized with no requirements for dedicated infrastructure support. Wireless infrastructure in terms of base stations is often available in many popular areas offering highspeed data connectivity to a wired network. In this paper we describe an approach where infrastructure components utilize passing by mobile nodes to route data to other devices that are out of range. In our scheme, base stations track user mobility and determine data usage patterns of users as they pass by. Based on this, base stations predict the future data needs for a passing mobile device. These base stations then collaborate (over the wired network) to identify other mobile devices with spare capacity whose routes intersect that of a needy device and use these carriers to transport the needed data. When such a carrier meets a needy device, they form ad hoc peer-to-peer communities to transfer this data. In this paper, we describe the motivation behind our approach and the different component interactions. We present the results of simulation work that we have done to validate the viability of our approach. We also describe, Numi, our framework for supporting collaborative infrastructure and ad hoc computing along with a sample application built on top of this highlighting the benefits of our proposed approach.
109110
On Mining Web Access Logs
Abstract : The proliferation of information on the world wide web has made the personalization of this information space a necessity. One possible approach to web personalization is to mine typical user profiles from the vast amount of historical data stored in access logs. In the absence of any a priori knowledge, unsupervised classification or clustering methods seem to be ideally suited to analyze the semi-structured log data of user accesses. In this paper, we define the notion of a user session , as well as a dissimilarity measure between two web sessions that captures the organization of a web site. To extract a user access profile, we cluster the user sessions based on the pair-wise dissimilarities using a robust fuzzy clustering algorithm that we have developed. We report the results of experiments with our algorithm and show that this leads to extraction of interesting user profiles. We also show that it outperforms association rule based approaches for this task.
17869517
A Secure Infrastructure for Service Discovery and Access in Pervasive Computing
Security is paramount to the success of pervasive computing environments. The system presented in this paper provides a communications and security infrastructure that goes far in advancing the goal of anywhere-anytime computing. Our work securely enables clients to access and utilize services in heterogeneous networks. We provide a service registration and discovery mechanism implemented through a hierarchy of service management. The system is built upon a simplified Public Key Infrastructure that provides for authentication, non-repudiation, anti-playback, and access control. Smartcards are used as secure containers for digital certificates. The system is implemented in Java and we use Extensible Markup Language as the sole medium for communications and data exchange. Currently, we are solely dependent on a base set of access rights for our distributed trust model however, we are expanding the model to include the delegation of rights based upon a predefined policy. In our proposed expansion, instead of exclusively relying on predefined access rights, we have developed a flexible representation of trust information, in Prolog, that can model permissions, obligations, entitlements, and prohibitions. In this paper, we present the implementation of our system and describe the modifications to the design that are required to further enhance distributed trust. Our implementation is applicable to any distributed service infrastructure, whether the infrastructure is wired, mobile, or ad hoc.
6404739
How the Semantic Web is Being Used: An Analysis of FOAF Documents
Semantic Web researchers have initially focused on the representation, development and use of ontologies but paid less attention to the social and structural relationships involved. The past year has seen a dramatic increase in the amount of published RDF documents using the Friend of a Friend (FOAF) vocabulary, providing a valuable resource for investigating how early Semantic Web adopters use this technology as well as build social networks. We describe an approach to identify, discover, and analyze FOAF documents. Over 1.5 million of FOAF documents are collected to show the variety and scalability of the web of FOAF documents. We analyzed the empirical usage of namespace and properties in the FOAF community, which helps the FOAF project in standardizing vocabularies. We also analyzed the social networks induced by those FOAF documents and revealed interesting patterns which can become powerful resource for outsourcing and justification of scientific knowledge.