Uncertainty Reasoning for the World Wide Web

W3C Incubator Group Report 31 March 2008

This version:

http://www.w3.org/2005/Incubator/urw3/XGR-urw3-20080331/

Latest version:

http://www.w3.org/2005/Incubator/urw3/XGR-urw3/

Editors:

Kenneth J. Laskey, MITRE

Kathryn B. Laskey, George Mason University

Paulo C. G. Costa, George Mason University

Mieczyslaw M. Kokar, Northeastern University

Trevor Martin, University of Bristol

Thomas Lukasiewicz, Oxford University

Contributors:

See Acknowledgments.

Copyright © 2008 W3C^® (MIT, ERCIM, Keio), All Rights Reserved. W3C liability, trademark and document use rules apply.

1. Introduction

1.1 The Problem of Uncertainty Representation and Reasoning

The World Wide Web community envisions effortless interaction between humans and computers, seamless interoperability and information exchange among web applications, and rapid and accurate identification and invocation of appropriate Web services. As work with semantics and services grows more ambitious, there is increasing appreciation of the need for principled approaches to representing and reasoning under uncertainty. In this Report, the term "uncertainty" is intended to encompass a variety of aspects of imperfect knowledge, including incompleteness, inconclusiveness, vagueness, ambiguity, and others. The term "uncertainty reasoning" is meant to denote the full range of methods designed for representing and reasoning with knowledge when Boolean truth values are unknown, unknowable, or inapplicable. Commonly applied approaches to uncertainty reasoning include probability theory, fuzzy logic, Dempster-Shafer theory, and numerous other methodologies.

To illustrate, consider a few web-relevant reasoning challenges that could be addressed by reasoning under uncertainty.

• Automated agents are used to exchange Web information that in many cases is not perfect. Thus, a standardized format for representing uncertainty would allow agents receiving imperfect information to interpret it in the same way as was intended by the sending agents.
• Much information on the World Wide Web is likely to be uncertain. Examples include weather forecasts or gambling odds. Canonical methods for representing and integrating such information are necessary for communicating it in a seamless fashion.
• Web information is also often incorrect or only partially correct, raising issues related to trust or credibility. Uncertainty representation and reasoning helps to resolve tension amongst information sources having different confidence and trust levels.
• The Semantic Web vision relies on numerous distinct but conceptually overlapping ontologies that co-exist and interoperate. It is likely that in such scenarios ontology mapping will benefit from the ability to represent degrees of membership and/or likelihoods of membership in categories of a target ontology, given information about class membership in the source ontology.
• Dynamic composability of Web Services will require runtime identification of processing and data resources and resolution of policy objectives. Uncertainty reasoning techniques may be necessary to resolve situations in which existing information is not definitive.
• Information extracted from large information networks such as the World Wide Web is typically incomplete. The ability to exploit partial information is very useful for identifying sources of service or information. For example, that an online service deals with greeting cards may be evidence that it also sells stationery. It is clear that search effectiveness could be improved by appropriate use of technologies for handling uncertainty.

Uncertainty is an intrinsic feature of many of the required tasks, and a full realization of the World Wide Web as a source of processable data and services demands formalisms capable of representing and reasoning under uncertainty. Although it is possible to use semantic markup languages such as OWL to represent qualitative and quantitative information about uncertainty, there is no established foundation for doing so. Therefore, each developer must come up with his/her own set of constructs for representing uncertainty. This is a major liability in an environment so dependent on interoperability among systems and applications.

Apart from the interoperability issues caused by proprietary uncertainty representations, there are ancillary issues such as how to balance representational power vs. simplicity of uncertainty representations, which uncertainty representation technique(s) addresses uses such as the examples listed above, how to ensure the consistency of representational formalisms and ontologies, etc. None of these issues can be addressed in a principled way by current Web standards.

1.2 The Incubator Group Activity (XG)

Given the current state of the overall subject of uncertainty representation and reasoning for the WWW, it became clear that the best approach would be to create an Incubator group, which provides an opportunity to share perspectives on the topic with all the advantages already cited in the W3C's Incubator Activity. Once the group was launched, the group's Charter were posted with all the details regarding the group's assignments, rules, and deliverables. Among the instructions, URW3-XG members were reminded that membership conditions include patent disclosure obligations as set out in Section 6 of the W3C Patent Policy and of their goal to produce work that can be implemented on a Royalty Free basis, as defined in the W3C Patent Policy.

2. Intent and Process

2.1 Scope of the URW3-XG

As stated in the URW3-XG's Charter, the objectives of the group were twofold:

• To identify and describe situations on the scale of the World Wide Web for which uncertainty reasoning would significantly increase the potential for extracting useful information; and,
• To identify methodologies that can be applied to these situations and the fundamentals of a standardized representation that could serve as the basis for information exchange necessary for these methodologies to be effectively used.

For the first objective, the URW3-XG has compiled a set of use case descriptions to expand on the examples noted above, and solicited and further developed other examples of the kinds of information management challenges that would benefit (and if available, have already benefited) most from mechanisms for reasoning under uncertainty.

For the second objective, the URW3-XG has identified methodologies that may be applied to address the use cases developed under the first objective and that show promise as candidate solutions for uncertainty reasoning on the scale of the World Wide Web. The combination of use cases and associated methodologies was examined to determine the most commonly required information and also the information that, while not common, may be especially important in particular situations.

The results of this one-year work pursuing the above objectives are listed below, in a total of 16 use cases, some of them including comprehensive information and details on how uncertainty would help to address issues that cannot be properly addressed with current deterministic approaches.

It is our expectation that the URW3-XG would recommend those aspects that are considered most important to be included in a standard representation of vagueness and uncertainty. The information below was written in a way of avoiding any connotation that this group advocates the choice of any one uncertainty methodology over others. Instead, we complied with our directives of seeking to identify the type of information that would need to be saved as part of a general resource description and transmitted to a reasoning engine for useful processing. The recommended set does not include all identified information or address every use case in the initial collection. Instead, the entire use case collection below provides a basis for discussing whether the recommended set is sufficient to advocate further actions along the W3C Recommendation Track, either as a separate Recommendation or as part of other related work.

Finally, our scope did not include recommending a single methodology but to investigate whether standard representations of uncertainty can be identified that will support requirements across a wide spectrum of reasoning approaches.

2.2 Process

To achieve the objectives cited above, the XG group was chartered, eventually comprising 25 participants from North and South America, Europe, and Australia and spread through a range of time zones spanning 18 hours. It conducted over 20 telecons, with an average duration between 90 and 120 minutes, plus partial face-to-face meetings held at the 5th ISWC (Busan - Korea) and the SUM conference in College Park, Maryland USA. The telecons were supported by the W3C resources (e.g. telecon bridge, IRC, RSSAgent, etc) and its results and action items were all catalogued in online Minutes. Every telecon also had an agenda with items to be discussed, the first always being to approve the last telecon's minutes.

Most of the issues being discussed were posted in the group's website in the form of wiki pages, which were  updated as new information became available and conclusions were drawn. Three months before the group's scheduled end, a draft of this report was posted in wiki format to enable participants to actively contribute to the material included here.

This Report is the major deliverable of the URW3-XG and describes the work done by the XG, identifies the elements of uncertainty that need to be represented to support reasoning under uncertainty for the World Wide Web, and includes a set of use cases illustrating conditions under which uncertainty reasoning is important. Along with the use cases (Section 5), this report also includes the Uncertainty Ontology (Section 3) that was developed during the discussions within our work, an overview of the applicability to the World Wide Web of numerous uncertainty reasoning techniques and the information that needs to be represented for effective uncertainty reasoning to be possible (Section 4), and a discussion on the benefits of standardization of uncertainty representation to the WWW and the Semantic Web (Section 6). Finally, it includes a Reference List of work relevant to the challenge of developing standardized representations for uncertainty and exploiting them in Web-based services and applications.

3. Uncertainty Ontology

A simple ontology was developed to demonstrate some basic functionality of exchanging uncertain information. In addition, this ontology was used to classify the use cases developed by this group with the intent of obtaining a relatively complete coverage of the functionalities related to uncertainty reasoning about information available on the World Wide Web.

While this ontology served the purpose of focusing discussion of the use cases allowing us to show examples of annotation of uncertainty, it should be clear that this ontology is just a first iteration in a larger process. We recommend that an effort to develop a more complete ontology for annotating uncertainty should be undertaken following this XG activity.

A short description of the ontology is presented below. First, the top level of the ontology is shown. Then the classes in the ontology are described. And finally the relations among the classes are discussed.

The Uncertainty Ontology can be downloaded as an OWL file.

3.1 Classes of the Uncertainty Ontology

The top level of the ontology is presented below.

OBS: The * means that the multiplicity constraint on the given property has not been specified, i.e., the property can have zero or more values for a given instance of the domain of the property.

3.1.1 Sentence

An expression in some logical language that evaluates to a truth-value (formula, axiom, assertion). It is then assumed that information will be presented in the form of sentences. So the uncertainty will be associated with sentences.

3.1.2 World

This represents the world about which the Sentence is said.

3.1.3 Agent

This is the class representing whoever makes the statement. It can be either a human or a computer agent (machine).

3.1.4 Uncertainty

A statement about the uncertainty associated with the sentence.

3.1.5 Uncertainty Nature

This captures the information about the nature of the uncertainty, i.e., whether the uncertainty is inherent in the phenomenon expressed by the sentence, or it is the result of lack of knowledge of the agent.

Aleatory - the uncertainty comes from the world; uncertainty is an inherent property of the world.

Epistemic - the uncertainty is due to the agent whose knowledge is limited.

3.1.6 Uncertainty Derivation

Objective - derived in a formal way, repeatable derivation process.

Subjective - subjective judgement, possibly a guess.

3.1.7 Uncertainty Type

Ambiguity - The referents of terms in a sentence about the world are not clearly specified and therefore it cannot be determined whether the sentence is satisfied, see also http://en.wikipedia.org/wiki/Ambiguity.

Empirical - a sentence about a world (an event) is either satisfied or not satisfied in each world, but it is not known in which worlds it is satisfied; this can be resolved by obtaining additional information (e.g., an experiment).

Randomness - sentence is an instance of a class for which there is a statistical law governing whether instances are satisfied.

Vagueness - there is not a precise correspondence between terms in the sentence and referents in the world, see also http://en.wikipedia.org/wiki/Vagueness.

Inconsistency - there is no world that would satisfy the statement.

Incompleteness - information about the world is incomplete, some information is missing.

3.1.8 UncertaintyModel

This class contains information on the mathematical theories for the uncertainty types. The specific types of theories include, but are not limited to, the following:

• Probability.
• Fuzzy Sets.
• Belief Functions.
• Random Sets.
• Rough Sets.
• Combination of Several Models (Hybrid), e.g., Fuzzy Sets and Probability.

3.2 Properties of the Uncertainty ontology

hasUncertainty - sentence S has uncertainty U.

saidAbout - sentence S is said about world W.

saidBy - sentence S was said by agent A.

nature - uncertainty U has nature S (either aleatory or epistemic (lack of knowledge)).

uncertaintyType - uncertainty U is of type T.

uncertaintyModel - uncertainty U is modeled using the mathematical theory M.

derivationType - uncertainty U was obtained by derivation of type D.

4. Most Commonly Used Approaches to Uncertainty for the WWW

4.1 Probability Theory

Probability theory provides a mathematically sound representation language and formal calculus for rational degrees of belief, which gives different agents the freedom to have different beliefs about a given hypothesis. This provides a compelling framework for representing uncertain, imperfect knowledge that can come from diverse agents. Not surprisingly, there are many distinct approaches using probability for the Semantic Web. This section briefly mentions the most commonly used approaches to probability for the Semantic Web. Appendix C brings a more detailed view of the subject.

4.1.1 Bayesian Networks (BNs)

Bayesian networks are a powerful graphical language for representing probabilistic relationships among large numbers of uncertain hypotheses. They have been applied to a wide variety of problems including medical diagnosis, classification systems, multi-sensor fusion, and legal analysis for trials. However, Bayesian networks are insufficiently expressive to cope with many real-world reasoning challenges found in the WWW. For example, a standard Bayesian network can represent the relationship between the type of an object, the object’s features, and sensor reports that provide information about the features, but cannot cope with reports from a large number of sensors reporting on an unknown number of objects, with uncertain associations of reports to objects. Section C.1.1 brings a detailed explanation of BNs within the context of the WWW.

4.1.2 Probabilistic Extensions to Description Logics.

Most of the probabilistic extensions aimed at the ontology engineering domain are based on description logics (DLs), which Baader and Nutt (2003, page 47) define as a family of knowledge representation formalisms that represent the knowledge of an application domain (the “world”) by first defining the relevant concepts and roles of the domain (its terminology), which represent classes of objects/individuals and binary relations between such classes, respectively, and then using these concepts and roles to specify properties of objects/individuals occurring in the domain (the world description).

There are several probabilistic extensions of description logics in the literature and some existing systems as well (e.g. Pronto), which can be classified according to the generalized description logics, the supported forms of probabilistic knowledge, and the underlying probabilistic reasoning formalism. These are covered in section C.1.2 in the appendices.

4.1.3 First-Order Probabilistic Approaches

In recent years, a number of languages have appeared that extend the expressiveness of probabilistic graphical models in various ways. This trend reflects the need for probabilistic tools with more representational power to meet the demands of real world problems, and is consistent with the need for Semantic Web representational schemes compatible with incomplete, uncertain knowledge. A clear candidate logic to fulfill this requirement for extended expressivity is first-order logic (FOL), which according to Sowa (2000, page 41) “has enough expressive power to define all of mathematics, every digital computer that has ever been built, and the semantics of every version of logic, including itself.” However, systems based on classical first-order logic lack a theoretically principled, widely accepted, logically coherent methodology for reasoning under uncertainty. Below are some of the approaches addressing this issue.

A workable solution for the Semantic Web requires a general-purpose formalism that gives ontology designers a range of options to balance tractability against expressiveness. Current research on SW formalisms using first-order probabilistic logics is still in its infancy, and generally lacks a complete set of publicly available tools. Examples include PR-OWL (Costa, 2005), which is an upper ontology for building probabilistic ontologies based on MEBN logic, and KEEPER (Pool and Aiken, 2004), an OWL-based interface for the relational probabilistic toolset Quiddity*Suite, developed by IET, Inc. A more detailed account of first-order probabilistic approaches is conveyed in section C.1.3 of the appendices.

4.2 Fuzzy Logic

In contrast to probabilistic formalisms, which allow for representing and processing degrees of uncertainty about ambiguous pieces of information, fuzzy formalisms allow for representing and processing degrees of truth about vague (or imprecise) pieces of information. It is important to point out that vague statements are truth-functional, that is, the degree of truth of a vague complex statement (which is constructed from elementary vague statements via logical operators) can be calculated from the degrees of truth of its constituents, while uncertain complex statements are generally not a function of the degrees of uncertainty of their constituents (Dubois and Prade, 1994).

Vagueness abounds especially in multimedia information processing and retrieval. Another typical application domain for vagueness and thus fuzzy formalisms are natural language interfaces to the Web. Furthermore, fuzzy formalisms have also been successfully applied in ontology mapping, information retrieval, and e-commerce negotiation tasks. Section C.2 of the appendices dwells on the subject at a greater level of detail.

4.2.1 Fuzzy Propositional Logics

Rather than being restricted to a binary truth value among false and true, vague propositions may also have a truth value strictly between false and true. One often assumes the unit interval [0, 1] as the set of all possible truth values, where 0 and 1 represent the ordinary binary truth values false and true, respectively. For example, the vague proposition “John is tall” may be more or less true, and it is thus associated with a truth value in [0, 1], depending on the body height of John.

4.2.2 Fuzzy Description Logics and Ontology Languages

In fuzzy description logics and ontology languages, concept assertions, role assertions, concept inclusions, and role inclusions have a degree of truth rather than a binary truth value. Semantically, this extension is essentially obtained by

• generalizing binary first-order interpretations to fuzzy first-order interpretations and
• interpreting all the logical operators by a corresponding combination function.

Syntactically, as in the fuzzy propositional case, one then also allows for formulas that restrict the truth values of concept assertions, role assertions, concept inclusions, and role inclusions. Some important new ingredients of fuzzy description logics are often also fuzzy concrete domains, which include fuzzy predicates on concrete domains, and fuzzy modifiers (such as “very” or “slightly”), which are unary operators that change the membership functions of fuzzy concepts.

4.3 Belief Functions

Belief functions are closely related to probabilities. Beliefs in a hypothesis is calculated as the sum of the masses of all sets it encloses. A belief function differs from a Bayesian probability model in that one does not condition on those parts of the evidence for which no probabilities are specified. This ability to explicitly model the degree of ignorance makes the theory very appealing and has been applied in areas such as inconsistency handling in OWL ontologies (Nikolov et al., 2007) and ontology mapping (e.g. Yaghlane and Laamari, 2007).

5. Use Cases

The Subsections below provide a brief description of the use case scenarions that have been studied by the incubator group and that corroborate its conclusions and recommendations. Detailed descriptions of all use cases can be found in Appendix A.

5.1 Discovery

Service oriented architecture (SOA) assumes a world of distributed resources which are accessible across a network. It is assumed that catalogues will exist for different classes of resources, such as SOA services, and the user will be able to search these catalogs for a desired item. Note, a class of items will be described using a list of relevant properties and items belonging to that class will be described by assigning values to these properties. For discovery to occur, there must be some alignment of or mediation between the list of properties used by those populating the catalogue and those searching it. There must also be some alignment of or mediation between the nonnumeric values assigned to the properties, both in describing items for the catalogue and defining the search criteria.

Uncertainty occurring in this use case includes the following:

• Terminology mismatches may make it difficult for the system to find the class of items the user intends. (UncAnn - UncertaintyNature: Epistemic; UncAnn - UncertaintyType: Vagueness).
• Given the class of items, the user may not unambiguously understand the meaning of the properties by which the class is described. (UncAnn - UncertaintyNature: Epistemic; UncAnn - UncertaintyType: Vagueness).
• Given a set of properties of interest to the user, there is uncertainty in trading off the user’s target property values against those of items in the catalogue. (UncAnn - UncertaintyNature: Epistemic; UncAnn - UncertaintyType: Empirical).

5.2 Wine Sweetness

Wine domain is a very attracting domain both for experts and non experts. The main reason of its attractiveness is given by:

• The high number of properties that qualify a wine or a set of wines.
• The fuzziness of the properties values for characterizing a wine as belonging to a certain category.

The “Wine Sweetness” use case focuses on a particular wine property that is the wine sweetness. The goal is to present a particular unknown wine’s sweetness to the user, according to his/her personal and possibly vague sweetness criteria. This is done by considering a knowledge base of reference that could have a finer/coarser classification, or it could use a terminology that is different from the one adopted by the user.

Furthermore, even when the same terminology is used, the interpretation of a vague classification label (such as “dry”) may differ between the creator of the knowledge base and the user who queries the knowledge base.

Uncertainty occurring in this use case includes the following:

• Knowledge bases may have different classification granularity, or different terminologies. (UncAnn - UncertaintyNature: Epistemic; UncertaintyType: Vagueness; UncertaintyDerivation: Subjective)
• Even considering the same terminology, the interpretation of a vague classification label (like “dry”) may differ between the creator of the knowledge base and the user. (UncAnn - UncertaintyNature: Epistemic; UncAnn - UncertaintyType: Vagueness; UncAnn - UncertaintyDerivation: Subjective)
• The classification, in a knowledge base, may be based on perception rather than on actual measurement. (UncAnn - UncertaintyNature: Epistemic; UncAnn - UncertaintyType: Vagueness; UncertaintyDerivation: Subjective)
• The information in various knowledge bases may be conflicting. (UncAnn - UncertaintyNature: Epistemic; UncAnn - UncertaintyType: Inconsistency; UncAnn - UncertaintyDerivation: Objective)

5.3 Belief Fusion and Opinion Pooling

A typical situation for web users is the need to aggregate information from multiple sources on the web. Issues related to uncertainty arise in such a situation in case the set of information acquired from multiple sources about the same fact is inconsistent (UncAnn - UncertaintyType: Inconsistency), or - more generally - in case that multiple information sources attribute different grades of belief (for example uncertain or mutually inconsistent beliefs) to the same statement (UncAnn - UncertaintyNature: Epistemic). If the user is not able to decide in favor of a single alternative (due to insufficient trust in the respective information sources, which can be seen as the default situation on the web), the aggregated statement resulting from the fusion of multiple statements is typically uncertain (UncAnn - UncertaintyNature: Epistemic, or if the types of uncertainty in this situation can vary. e.g., we could have UncAnn - UncertaintyType: Empirical).

A similar situation can be observed when a single information artifact on the web (e.g., a knowledge base, an ontology, a product rating, meta data, or even an ordinary web page) shall be created from multiple possibly contradictory information sources (e.g., expert opinions, existing ontologies, product recommendations, meta data, web pages...). The result needs to reflect and weight multiple input information appropriately, which typically yields uncertainty in case of heterogeneous input information.

There are several approaches to belief fusion. Examples for belief aggregation operators which can yield uncertain results are logarithmic and linear pools (LogOP, LinOP), and Bayesian Network Aggregation. One possible criterion for a successful fusion is the minimization of the divergence of the resulting probability distribution from the input probability distributions.

5.4 Ontology Based Reasoning and Retrieval from Large-Scale Databases

Consider a production company which has a knowledge base that consists of videos and images about persons (which usually are actors or models), TV spots, advertisements, etc. This company wants to publish its content on the Web so that advertisement or other production companies can use this knowledge base to look for either video footage like films, TV spots, etc or for persons to be employed for advertisements (casting). Each entry in the knowledge base contains a photo or a video, and some specific information like body and face characteristics, age or profession-like characteristic, in the case of persons, or video annotations in the case of spots or sceneries. The casting company has created a user interface for inserting the information of persons as instances of a predefined ontology or for performing semantic annotation of its multimedia content. It also provides a query engine to perform ontology-based search for its content through the web. A user can query the knowledge base providing information like the name, the height, the type of the hair (e.g. good quality, perfect, punk), the body (e.g. slim, athletic, plump), age range (e.g. 30s, 50s, MiddleAged), and more, in the case of persons, or information like the place the video spot is taking place (indoors vs. outdoors), the time of day (morning, afternoon, night), the landscape it depicts (mountain, sea), a sky being cloudy or not, a sea being wavy or not, and many more.

The knowledge engineer of the application has identified that applying a classical (Boolean) knowledge based system in the above scenario is very problematic due to the nature of the knowledge and information. For example, an attempt to assign a Boolean meaning to concepts like "30s", "MiddleAged", "Teen", "Kid", "Slim", "Tall", ... would lead to intuitive paradoxes. On the other hand, it is also very difficult to define other more expressive concepts, like the concept "StudentLooks" in terms of the already problematic concepts "Teen" and "Kid". Similarly, a sky being cloudy or wavy or time being morning or afternoon is also a matter of degree.

His solution to the problem is to use fuzzy ontologies where the membership of an individual (person) or image object to a Concept is annotated with a degree of membership. So one is able to classify "model1" as Tall, Thin, MiddleAged, to degrees 0.6, 0.9, 0.7, respectively, depending on the model's actual height, weight and age. Then, one is able to infer that "model1" is StudentLooking or AccademicLooking to specific degrees according to the definition of the concepts in the ontology and the interpretation of them according to the theory of fuzzy ontologies. Interestingly, the developed system also provides a easy and natural way to provide end-users with rankings in the query results which is not easily supported by Booelan models, or even more to allow end-users specify preferences and weights over the atoms (ingredients) of their queries, thus allowing for far more expressivity.

5.5 SOA Execution Context

As defined in the OASIS Reference Model for Service Oriented Architecture (SOA-RM), the execution context of a service interaction is the set of infrastructure elements, process entities, policy assertions and agreements that are identified as part of an instantiated service interaction, and thus forms a path between those with needs and those with capabilities.

As discussed in SOA-RM, the service description (and a corresponding description associated with the service consumer and its needs) contains information that can include preferred protocols, semantics, policies and other conditions and assumptions that describe how a service can and may be used. The participants (providers, consumers, and any third parties) must agree and acknowledge a consistent set of agreements in order to have a successful service interaction, i.e. realizing the described real world effects. The execution context is the collection of this consistent set of agreements.

Uncertainty occurring in this use case includes the following:

• Service consumer may have insufficient information about provider's capabilities and associated requirements to ascertain whether service provider can meet needs at acceptable cost. (UncAnn - UncertaintyNature: Epistemic; UncAnn - UncertaintyType: could be Ambiguity or Vagueness)
• Service provider may have insufficient information about consumer's need to know whether the functionality it provides can meet that need. (UncAnn - UncertaintyNature: Epistemic; UncAnn - UncertaintyType: could be Ambiguity or Vagueness)

5.6 Recommendation

Recommender systems form a rapidly growing category of web-based system. A recommender system takes input from a user in the form of a query or an exemplar of the kind of item the user seeks, and returns recommendations for information or products. For example, the user might input a list of keywords and the system would return a list of recommended books, articles and/or web sites. The user might input one or a few movies, and the system might return a list of suggested movies for the user to view. Many e-commerce sites employ recommending systems to suggest products that customers might want to purchase. Another well-known example for this use case is the search for web pages using a search engine.

This use case discusses uncertainties that typically occur in the context of recommender systems or recommendations generated using other technical means (e.g., agents). The main scenario is as follows: A single or multiple recommendation searcher(s) express(es) her/their preferences in a machine readable format. A recommender system then combines a set of recommendations (obtained by a number of agents or other recommender systems) into an aggregated recommendation and ranking. For example, a user might input a movie, and the system would form its recommendation by aggregating recommendations provided by consumers who have seen the movie.

In this scenario uncertainty can occur for several reasons:

• The set of recommendations obtained from multiple agents might be inconsistent.
• A recommendation possibly matches the preference(s) of the recommendation searcher only imperfectly.
• A recommender system might have obtained its recommendation using statistical means (e.g., using collaborative filtering).
• An agent or a recommender system might have a low confidence in its recommendation, i.e., it is uncertain whether its recommendation actually matches the preference.
• The preferences provided by a recommendation searcher can be uncertain or inconsistent, e.g., because a user might not be able to express his preferences in sufficient detail.
• Sometimes a single recommendation shall reflect multiple preferences provided by multiple recommendation searchers (e.g., if a group of users seeks a single recommendation which reflects the preferences of all group members as well as possible). Uncertainty arises e.g. in case these input preferences are inconsistent.

In order to enable formal inference to be carried out on the set of recommendations, the semantics of recommendation needs to be cleanly defined and an appropriate formal framework for the representation of recommendations is required. Also, an ability is needed to express preferences, scales and rankings in a formal way.

5.7 Extraction / Annotation

The motivating situation is a user (or a web service) that wants a web scale overview of available information – e.g. overview of all car selling shops or online shops selling notebooks. The advantage would be a possibility of comparison of different market offers. Another application is competitor tracking system.

Main problem is the size of data and the fact that these data are mainly designed for human consumption.

Solution are extraction and annotation tools. There are many annotation tools linked on the SW Annotation & Authoring Website, mainly using a proprietary uncertainty representations (or built in uncertainty handling). Here uncertainty annotation of results would be especially helpful.

Assume that a user is looking for notebooks and we would like to provide a machine support for his/her search. A typical statement which is a subject of uncertainty assignment in this use case is: (UncAnn - Sentence) An html coded web page with URL contains informations, which according to an ontology o1 (UncAnn - World: DomainOntology) about notebooks can be expressed by a RDF triple (ntb1, O1:has_priceProperty, 20000). The agent producing this statement is (UncAnn - Agent: MachineAgent) especially an induction agent (UncAnn - Agent: MachineAgent:InductiveAgent). For extensions of concepts see a finer grained version of Uncertainty Ontology.

Uncertainty nature of this statement isUncAnn - UncertaintyNature: Epistemic:MachineEpistemic), uncertainty type is usually (UncAnn - UncertaintyType: Empirical:Randomness). Instances used for training an extraction tool (UncAnn - World:DomainOntology:Instances) are web pages, the uncertainty model is usually complicated (mixture of html structure, regular expressions, annotation ontology and similarity measures) and combination of several models, typically (UncAnn - UncertaintyModel:CombinationOfSeveralModels:ProbabilityAndFuzzySetsCombinationModels) . Depending on this the evidence for this uncertainty statement (UncAnn - World:DomainOntology:Instances:Evidence) are precision and recall on this training set.

5.8 Soft Shopping Agent

Suppose we have a car selling web site offering cars and we would like to buy a car. Descriptions of the cars are stored in databases and we have some ontology encoding information about the domain. Now, suppose that preferably we would like to pay around €11000 and the car should have fewer than 15000 km on the odometer. Also, if there are leather seats then I would like to have air conditioning, the color is preferably blue, and the car is not old.

Of course, most of our constraints, e.g. on price and kilometers, aren't crisp as we may still accept e.g.~a car's cost of €11200 and with an odometer reading of 16000km. Hence, these constraints are rather vague (fuzzy) (we may model this by means of so-called fuzzy membership functions). We may also give some preference weight to my requirements.

On the other hand, the seller may offer a discount on the car's catalogue price, but the bigger the discount the less satisfied he is. For instance, related to the sale of a Mazda3, the seller may consider optimal to sell above €15000, but can go down to €13500 to a lesser degree of satisfaction.

For each car, there will be an optimal price it can be sold, which maximises the product of the buyer's degree of satisfaction and the seller's degree of satisfaction. This is the so-called NASH equilibrium of the matching. Each car gets an optimal degree of buyer/seller degree of satisfaction.

From the buyer perspective, he asks for the TOP-k cars and their optimal price, ranked by the optimal degree of satisfaction.

From the seller perspective, he may ask for the TOP-k buyer's for a given car and their optimal price, ranked by the optimal degree of satisfaction.

5.9 A Chain from the Web to the User

To get information from the web to the user we have to use a chain of tools – typically web crawling, web data extraction, middleware transformation, user querying and delivering answer. There are several use cases dealing with particular problems of uncertainty along such a chain. Usually there is a middleware connecting those.

The problem is, how does uncertainty evolve along such a chain.

Our understanding of this is to view the whole chain of models, methods and tools from web to the user and especially handling uncertainty combination along this (UncAnn - UncertaintyModel: could be a combination of several models).

5.10 Appointment Making

This use case was inspired by the 2001 Scientific American article, The Semantic Web, by Berners-Lee, Hendler and Lassila. The article describes a scenario in which Lucy and her brother Pete must schedule their mother for a sequence of visits to a physical therapist. They agree to share the chauffeuring, and Lucy tasks her Semantic Web agent to set up the appointments:

Lucy instructed her Semantic Web agent through her handheld Web browser. The agent promptly retrieved information about Mom's prescribed treatment from the doctor's agent, looked up several lists of providers, and checked for the ones in-plan for Mom's insurance within a 20-mile radius of her home and with a rating of excellent or very good on trusted rating services. It then began trying to find a match between available appointment times (supplied by the agents of individual providers through their Web sites) and Pete's and Lucy's busy schedules.

It is clear that many uncertainties arise in handling this classic use case for the Semantic Web use case. For example, both the provider's and the consumer's schedules may be uncertain, and in traffic-clogged metropolitan areas, the amount of time it takes to get from the consumer's location to the place where the service is rendered may be highly uncertain.

5.11 User Preference Modeling for top-k Answers

This is in a sense a generalization of some aspects of Discovery use case. Given a populated catalogue by some extraction tool (see use case about extraction) of items and a user’s criteria and/or multicriterial utility function for item potentially listed in the catalogue retrieve best, top-k matches.

Usually, the main problem is to learn user preferences. This can be done either by implicit information collection (system tracks user behavior, click streams, …) or by explicit information collection (system poses questions, user answers). Sometimes a recommender system finds similar users (UncAnn - UncertaintyModel:SimilarityModels). Another problem is effective retrieval of search results ordered by these preferences (usually top-k answers suffice).

As result of any data mining procedure, results of such user preference mining will be uncertain.

Typical sentence which is a subject of uncertainty assignment is: (UncAnn - Sentence) User1 prefers most item1 (list of of top-k most preferred items for User1 consists of item1, ..., itemk).

There are models using partially ordered sets to represent preferences. Different ad hoc ranking approaches are used. Possible model is UncAnn - UncertaintyModel: FuzzySets or UncAnn - UncertaintyModel: PreferenceModels.

5.12 Ontology Mediated Multimedia Information Retrieval

Suppose we want to device ontology mediated multimedia information retrieval system, which combines logic-based retrieval with multimedia feature-based similarity retrieval. An ontology layer may be used to define (in terms of semantic web like language) the relevant abstract concepts and relations of the application domain, while a content-based multimedia retrieval system is used for feature-based retrieval. We ask to make queries such as

• Find top-k ranked video passages made by Umberto whose title is about 'tour'.
• Find top-k ranked images similar to a given one, which is about an animal.

5.13 Buying Speakers

The main point of this use case is to show that in some cases one needs to combine different kinds of uncertainty. In this particular use case two types of uncertainty are considered: Randomness and Vagueness.

The scenario includes a customer who is interested in purchasing a set of speakers, but the question is (1) whether to go to a store today or wait until tomorrow to buy speakers, (2) which speakers to buy and (3) at which store. Customer is interested in two speaker features: wattage and price. Customer has a valuation formula that combines the likelihood of availability of speakers on a particular day in a particular store, as well as the two features. The features of wattage and price are fuzzy. Optionally, Customer gets the formulas from CustomerService, an ontology based Web service that collects information about products, stores, statistics, evaluations.

It is assumed that there is known probability distribution on the availability of particular speaker type in particular stores on a particular day in the future. Also it is assumed that both the customer's agent and the consumer service agent share the same Uncertainty Ontology. The customer's agent issues a query (a sentence) using terms from the Uncertainty Ontology: Sentence. It is a complex sentence consisting of three basic sentences. One related to the availability, one to the wattage and one to the price of speakers. Each of these sub-sentences will have uncertainty Uncertainty associated with it. The uncertainty type related to the availability of particular speaker type in the stores is of type UncAnn - UncertaintyType: Empirical. The uncertainty nature is UncAnn - UncertaintyNature: Aleatory. The uncertainty model is UncAnn - UncertaintyModel: Probability. The customer has (or obtains from CustomerService) definitions of features of wattage and price in terms of fuzzy membership functions. For wattage, Customer has three such functions: weak, medium and strong. These are of "trapezoid shaped" membership functions. Similarly, for price Customer has three such membership functions: cheap, reasonable and expensive.

In the end, the customer gets necessary information about the availability and types of speakers from stores. This information is sufficient for the customer to compute the required metric and to make the decision on which speakers to buy, where and when.

5.14 Healthcare and Life Sciences

The entire Healthcare and Life Sciences spectrum involves the creation and manipulation of uncertain information and knowledge. A collection of use cases are presented characterized by a simple taxonomy.

5.14.1 Hypothesis Uncertainty

Some examples of Uncertainty in the context of Hypothesis Generation and Validation are enumerated below:

• Mutations in the alpha synuclein could cause Parkinsons Disease.
• Hypotheses of relationships based on statistical analysis of microarray data associated with p-values, confidence intervals, etc.
• Gene Ontology Evidence codes in support of a particular GO annotation of a gene.
• Evidence classes in the OBO Evidence Ontology.

5.14.2 Interpretation/Classification Uncertainty

• Some examples of Uncertainty in the context of interpreting and classifying different types of information are enumerated below:
• The patient has elevated cholesterol based on his reading of X mg/dl.
• Given the same set of symptoms, Doctor X and Y come up with diagnosis of mild and severe disease respectively
• True/False Positive/Negative rates of patient classifications and diagnoses.
• Use of measures such as Precision, Recall, PPV, NPV, etc.

5.14.3 Prediction-oriented Uncertainty

Some examples of Uncertainty in the context of predicting some phenomena based on currently available information are enumerated below:

• A person with the BRCA1 gene has a disposition towards Breast Cancer with 70% probability in the future

5.14.4 Belief oriented uncertainty

Some examples of Uncertainty in the context of believing (or not believing) certain hypotheses and theories are enumerated below.

• It is believed to the best of our knowledge that a particular gene is not implicated in a particular disease.
• Associated non-monotonicity with the above, i.e., if more knowledge is available, the statement could be proven false.

5.14.5 Data Source based Uncertainty

Some examples of Uncertainty in the context of trusting various data sources are enumerated below.

• Samples from the same patient are analyzed by different labs. Lab 1 results show an 80% probability of Disease 1, whereas Lab2 shows a 90% probability for the same.
• If the Cleveland Clinic says that Avandia is bad for Diabetes, the statement has a higher value of certainty as opposed to an individual Dr. X.

5.14.6 Data Uncertainty

Some examples that illustrate the inherent uncertainty of the data generated in the Healthcare and Life Sciences are enumerated below.

• Approximate location of a clinical feature, e.g, tumor in spatial location in the human body as captured in radiological image or any other digital artifact.
• Data inconsistency and incompletenes encountered in Healthcare and Drug Databases.
• Data uncertainty introduced due to sampling errors, sampling rates, etc).
• Data uncertainty introduced due to the limitations (least count error?) of the device measuring patient characteristics (e.g., temperature).
• Data uncertainty introduced due to limitation of instruments used to collect experimental data, e.g., micro-arrays.

6. Benefits of Standardization

6.1 Where use cases imply standardization benefits

We can consider the use cases above as processes in which a consumer of information makes a request to a provider (or multiple providers) of web-accessible information or services, and receives a response (or multiple responses).

The use cases illustrate several examples where uncertainty arises during this interaction and there are a number of topics that are common across use cases. Specifically, we can sub-divide into three areas - the producer’s specification of what can be provided, the consumer’s request (description of what is wanted) and the result. Taking these in turn:

6.1.1 Uncertainty in Provider's Specification

This relates primarily to the provider’s descriptors (i.e. properties used to describe the topic / item / service provided) and the values assigned to these descriptors. Such values may be based on perception rather than measurement (for example, a picture of someone with an ‘athletic physique”), or on overlapping categories where an item can belong to multiple categories at different membership levels (e.g. a film could belong strongly to the genre ‘comedy’ and weakly to the genre ‘adventure’).

Additional uncertainty may arise where the provider makes assertions related to the use of the information or service provided. Standardization could assist (for example) in determining intersection with similar assertions by the consumer, e.g. privacy policies.

6.1.2 Uncertainty in Consumer's Request

The provider has to deal with cases of incomplete and/or inconsistent information in the request from a consumer. Further uncertainty may arise where a request is based partly on submitted data and partly on background information, such as known consumer preferences or history.

As above, further uncertainty may arise where the consumer makes assertions related to the use of the information provided in the request.

6.1.3 Result Returned to Consumer

The consumer may have to deal with uncertainty in the result from a single provider or in results from multiple providers. In the first case, the most obvious possibility is that the result is incomplete or inconsistent in some way. Inconsistency is not a binary state - in many cases, a small inconsistency in a result may not affect the usefulness of the answer. It is however an area in which standardization of uncertainty could aid uniform handling of results. Similarly, incompleteness in a result may not affect its usefulness.

Further uncertainty may arise from use of the provider’s use of consumer preferences, the process of finding responses to a partially matched request, etc. Inconsistency is possible from a single provider but is more likely where results are aggregated from multiple providers. In cases where a consumer is dealing with more than one provider, these problems are multiplied because different providers may have different interpretations of descriptors and values, or even different sets of descriptors, as well as different approaches to processing requests, variation in use of consumer preferences, different historical data on a particular consumer, etc. Clearly standardization would clarify the uncertainty in this process to the benefit of both producers and consumers.

Underlying these aspects are the fundamental questions that motivate standardization - how do the different parties assess uncertainty, and can these assessments be meaningfully combined, particularly when they are derived from different methodologies. The work of this XG is not to develop or even identify many of the mechanisms that these use cases imply are needed to process uncertainty. The current effort intends to identify the types of information that are likely to be valuable for such processing to occur and to provide guidance to those who would develop the syntax to convey this information in a machine-processible way.

6.2 Goals of Standardization

The challenges related to uncertainty reasoning on the scale of the World Wide Web have been introduced in Section 1, and the goal of standardization would be to enable the understanding and processing needed for consistent use of available information when uncertainty is present. Many applications which generate data for the web already handle uncertainty in some form. For example, information retrieval systems may rank pages in terms of “relevance” on a scale of 0-100, weather forecasts are frequently qualified (e.g. 30% chance of showers), product finders return lists which are ordered according to the quality of match with a user’s requirements. These applications implicitly or explicitly define and handle uncertainty, and communicate it to the user. Standardization is not necessary for these individual applications which handle uncertainty internally in a (hopefully) consistent manner.

However, as soon as an application incorporates externally produced uncertain data, there is a need to standardize the representation of the characterization of the uncertainty. The notion of interoperability - being able to access and process data from any web source - is fundamental to a web of distributed information, and cannot be achieved unless all sources conform to common standards. As argued in the introduction, much of the available data on the web is subject to uncertainty - so that without standardization of uncertainty, applications using this information are either (i) inaccurate or (ii) have to make assumptions that enable them to ignore uncertainty. Neither of these options is likely to lead to practical, accurate reasoning about real-world data, except in a limited set of cases.

The aim of uncertainty standardization for the World Wide Web should be

• to enable mark-up of a web-based information source so that the nature of any associated uncertainty is clear - whether the uncertainty is a product of the inference process, is inherent in the stored facts or is due to limited knowledge of the information provider
• to permit the definition of extensions to the uncertainty framework

The availability of an uncertainty mark-up language for annotating web data would make it possible to (semi)automate and manage the trustworthiness of the information on the Web. Indeed, there are many cases in which the same data can have different reliability depending on: the source from which they are generated, the context in which they are produced, the time in which they are made available. Currently, such information generally cannot be managed simply because there are no way for knowing the associated uncertainty. With the availability of uncertainty mark-up annotation, such information can be properly treated for the first time.

6.3 Aspects of Uncertainty Reasoning for Potential Standardization

Many approaches to uncertainty use a numerical scale (e.g. from 0 to 1 or 0 to 100) but interpret and process these values in different ways. It is not necessary for every implemented system to interpret and process every form of uncertainty. The aim should be for common understanding and interpretation of the core forms, and the ability to extend the framework as necessary. For example, if data is published with probabilities attached, any other application would be able to perform specified operations on those probabilities and know that the results were meaningful.

In summary, the following aspects must be considered:

• semantics - any standarization proposal should have a semantics related to the model-theoretic semantics of OWL.
• extensibility - the standard should support uncertainty models listed above (section 3) but should not restrict the expression of uncertainty to these models.
• expressibility / ease of use.

As such, we conclude the following as guidelines when considering possible standards development efforts related to uncertainty:

• We see no single approach to uncertainty reasoning that will solve all problems, so a standard must support current and, to the extent we currently understand, future uncertainty reasoning methodologies.
• A standard must provide a means to clearly identify the context under which provided uncertainty information was generated and, possibly, the intended use of the information.
• A standard must provide the means to convey uncertainty information needed to support any methodology.

7. Conclusions and Recommendations

According to the URW3-XG's Charter. The objectives of the group are twofold:

• To identify and describe situations on the scale of the World Wide Web for which uncertainty reasoning would significantly increase the potential for extracting useful information.
• To identify methodologies that can be applied to these situations and the fundamentals of a standardized representation that could serve as the basis for information exchange necessary for these methodologies to be effectively used.

To motivate our debate, we have studied several use cases in which uncertainty would play a significant role. In all of those cases, we assumed the need of an unified model of uncertainty annotation of web resources and the need of those annotations to be done automatically, due to the size of the web. We also found that in order to address the situations presented here, an ontology on uncertainty is needed, so deductive engines would be able to use uncertainty information properly and third party users would understand the annotated resources. In all use cases we studied, a successful end would mean to have automatic processing of web resources with greater accuracy, while a failed end would just leave the web as it is today.

7.1 Conclusions Relating to UncertaintyOntology

In automated Web data processing, we often face situations where Boolean truth values are unknown, unknowable, or inapplicable. Our conclusions follow the UncertaintyOntology as described above but also imply that a finer grained version of UncertaintyOntology might be useful.  Such an extension could provide a means to visualize a possible evolution of upper level UncertaintyOntology and to emphasize uncertainty issues connected to machine processing (lot of situations are perfectly certain when considering human consumption of web resources). In the current discussion, we focus especially on finer classification of Machine Agents (UncAnnAgent: MachineAgent) and uncertainty caused by lack of knowledge of a machine agent (UncAnn UncertaintyNature:Epistemic:MachineEpistemic).

• Information extracted from large information networks such as the World Wide Web is typically incomplete (UncAnnUncertaintyType:Incompleteness). The ability to exploit partial information is very useful for identifying sources of service or information. For example, that an online service deals with greeting cards may be evidence that it also sells stationery. It is clear that search effectiveness could be improved by appropriate use of technologies for handling uncertainty.
• Much information on the World Wide Web is likely to be uncertain. In some cases this is an inherent property of the world (UncAnn UncertaintyNature:Aleatory). Nevertheless, it is a difference, whether this world is the physical world, or living, society or business. Examples include weather forecasts (UncAnn UncertaintyNature:Aleatory:PhysicalWorldAleatory), gambling odds or stock exchange (UncAnnUncertaintyNature:Aleatory:BusinessWorldAleatory). Canonical methods for representing and integrating such information are necessary for communicating it in a seamless fashion.
• Web information is also often incorrect or only partially correct, raising issues related to trust or credibility (UncAnn UncertaintyNature: Trust, UncertaintyType:Lie). Uncertainty representation and reasoning helps to resolve tension amongst information sources having different confidence and trust levels (this is one of few cases where even a human agent has problems with processing information).
• The Semantic Web vision implies that numerous distinct but conceptually overlapping ontologies will co-exist and interoperate (UncAnn UncertaintyNature:Epistemic:MachineEpistemic). It is likely that in such scenarios ontology mapping will benefit from the ability to represent degrees of membership and/or likelihoods of membership in categories of a target ontology, given information about class membership in the source ontology.
• Dynamic composability of Web Services will require runtime identification of processing and data resources and resolution of policy objectives. Uncertainty reasoning techniques may be necessary to resolve situations in which existing information is not definitive (UncAnn UncertaintyNature:Epistemic:MachineEpistemic).

We recommend aspects that are considered most important to be included in a standard representation of uncertainty : Extensions of UncertaintyOntology which prove to be useful in annotation of web resources in order to improve their machine processing.

7.2 Conclusions Relating to Kinds of Uncertainty

The use cases demonstrate that there are two very different kinds of uncertainty that we need to consider in standardization.

1. Uncertainty inherent in the data.
2. Uncertainty reasoning for the processing and presentation of information
   1. using uncertainty reasoning to draw conclusions; or
   2. uncertainty inherent in semantic processing, vagueness, ontology mapping, terminology mismapping.

Each of (a) and (b) represent different standardization motivations and requirements.

In the first case, the standardization should be done at the representation level. When sharing information that has an inherent level of uncertainty, it is useful to have a single syntactical system so that people can identify and process this information quickly. These kinds of use case may require something like uncertain extensions to OWL (i.e., probabilistic, fuzzy, belief function, random set, rough set, and hybrid uncertain extensions to OWL; see Section 3.1.8). For example, as for probabilistic uncertainty, we may want to be able to pass on information that Study X shows that people with property Y have an X% increased likelihood of this disease, or that the probability of a four of a kind given pocket Aces and an Ace in the flop is 0.043. This simply requires a standard syntax.

But many of the use cases we've considered involve uncertainty reasoning on the part of the tools used to access and share web information, not the information itself. For example, if a web service uses uncertainty reasoning to find and rank hotel rooms for me, the uncertain information would not reside on the web. In such situations the role of standardization is different and the motivation may be less clear. After all, if the hotel room information is useful and rankings are roughly accurate, many users will be unconcerned with the reasoning process or the uncertainties attached to the rankings. So, here, we'd want to use standardization for a different purpose. It would be used to represent meta-information about the reasoning models and assumptions. And it would also play a different role, e.g., developing trust models, finding compatible web services. However, it could also require a very extensive representation task. Standardization questions here include determining how to represent this information, how detailed it would be, where it would reside.

7.3 Specific Recommendations for Standardization

It is acknowledged that while uncertainty is pervasive in both normal life and its reflections on the Web, it is not always necessary to characterize this uncertainty. However, there are significant instances where knowledge of uncertainties could be used to positively support decision making, and it is with such instances in mind that the URW3-XG makes the following recommendations:

1. Whereas we have demonstrated use cases for which uncertainty can have a significant effect on the conclusions that can be drawn from viewing and processing information available on the World Wide Web, we believe a principled means for expressing uncertainty will increase the usefulness of Web-based information and believe a standard way of representing that information should be developed.
2. Whereas the different use cases appear to lend themselves to different uncertainty formalisms, the standard representation should provide a means to unambiguously identify the formalism providing the context for assigning other uncertainty characteristics and values.
3. Whereas different uncertainty formalisms assign values to properties specifically related to the underlying meaning and processing of these values, the representation should support defining different standard properties for each formalism without requiring changes to the representation itself.
4. Whereas consistent understanding and processing must be enabled both within and across uncertainty formalisms, adjunct specification should be developed for the most commonly used uncertainty formalisms, as discussed in Section 4 and Appendix C. Such adjunct specifications would not be intended to prescribe an exclusive set of relevant formalisms but merely those found most useful at that time, with the ability to expand the set as circumstances might indicate to be prudent.
5. Whereas uncertainty can be present anywhere, the representation should support associating uncertainty with any property or value expressible across the Web.

The recommendations point to the desirability of having a means to annotate information with relevant uncertainty information. The mechanism could be similar to that specified under Semantic Annotations for WSDL and XML Schema(SAWSDL), where the annotation approach is described as follows:

The specification defines how semantic annotation is accomplished using references to semantic models, e.g. ontologies. Semantic Annotations for WSDL and XML Schema (SAWSDL) does not specify a language for representing the semantic models. Instead it provides mechanisms by which concepts from the semantic models, typically defined outside the WSDL document, can be referenced from within WSDL and XML Schema components using annotations.

In the realm of uncertainty representation, we would specify uncertainty models and uncertainty annotations rather than SAWSDL's semantic counterparts. For such uncertainty annotations, a possible standard would need to support both inherent uncertainty in the data and uncertainty connected to results of processing that data, but at this point it is unclear whether there is a need for separate portions of the syntax for each data and processing uncertainty or whether a single syntax would be able to cover the entire range.

In addition, a question that remains with this approach but one which is outside the scope of the URW3-XG is whether existing languages (e.g. OWL, RDFS, RIF) are sufficiently expressive to support the necessary annotations. If so, the development of such annotations might merely require work on a more complete uncertainty ontology and possibly rules; otherwise, the expressiveness of existing languages might need to be extended. As an example of the latter, it might be advisable to develop a probabilistic extension to OWL (e.g. PR-OWL) or a Fuzzy-OWL format or profiles associated with the type of uncertainty to be represented. Further work is required to investigate the adequacy of the existing languages against the compiled use cases.

An eventual goal in continuing the current work would be to define a format to represent uncertainty in an agreed upon way to enable reliable communications for situations such as the compiled use cases. The work of the URW3-XG has made a significant contribution in defining the problem space and identifying continuing work. These questions will likely be the subject of discussion at a proposed 4th Uncertainty Reasoning for the Semantic Web (URSW) workshop at ISWC 2008, and just as the 2nd URSW workshop decided to pursue the question of uncertainty representation through what became the URW3-XG, a proposal for continued work may be an output of the 2008 URSW workshop.

8. Acknowledgements

The editors acknowledge significant contributions from the following persons (in alphabetical order):

• Fernando Bobillo, University of Granada.
• Anne Cregan, NationalICT Australia/University of New South Wales
• Claudia d'Amato, Department of Computer Science - University of Bari.
• Nicola Fanizzi, Department of Computer Science - University of Bari.
• Francis Fung, IET/Eduworks.
• Vipul Kashyap, Partners HealthCare System, Inc.
• Sebastian Kruk, DERI Galway.
• Eric Monk, McDonald Bradley, Inc.
• Matthias Nickles, University of Bath.
• Jeff Pan, University of Aberdeen.
• Michael Pool, Convera, Inc.
• Pavel Smrz, Brno University of Technology.
• Giorgos Stamou, Image, Video and Multimedia Systems Lab (IVML-NTUA).
• Giorgos Stoilos, Image, Video and Multimedia Systems Lab (IVML-NTUA).
• Umberto Straccia, CNR - Consiglio Nazionale delle Ricerche.
• Edward Thomas, University of Aberdeen, Computing Science.
• Miroslav Vacura, Prague University of Economics.
• Peter Vojtas, Charles University Prague.

Reference List

This is a collection of references that were added by XG members. Their intent was to collect a set of references for various methodologies and to "investigate proposed and implemented methodologies that may be applied to address the use cases developed under the first objective and that show promise as candidate solutions for uncertainty reasoning on the scale of the World Wide Web. The combination of use cases and associated methodologies would be examined to determine the most commonly required information and also that information that while not common may be especially important in select situations."

The list is by no means exhaustive and should be merely regarded as a set of recommended reading for people interested in the subject of uncertainty representation and reasoning in general.

Agarwal, S.; and Lamparter, S. (2005) sMART - A Semantic Matchmaking Portal for Electronic Markets. Proceedings of the 7th International IEEE Conference on E-Commerce Technology. Munich, Germany, 2005.

Baader, F.; and Nutt, W. (2003). Basic Description Logics. In Baader, F., Calvanese, D., McGuiness, D., Nardi, D., & Patel-Schneider, P. (Eds.), The Description Logics Handbook: Theory, Implementation and Applications. 1st edition, chapter 2, pp. 47-100. Cambridge, UK: Cambridge University Press.

Bangsø, O., & Wuillemin, P.-H. (2000) Object Oriented Bayesian Networks: A Framework for Topdown Specification of Large Bayesian Networks and Repetitive Structures. Technical Report No. CIT-87.2-00-obphw1. Department of Computer Science, Aalborg University, Aalborg, Denmark.

Bednarek, D.; Obdrzalek, D.; Yaghob, J.; and Zavoral, F. (2005) Data Integration Using Data Pile Structure, in Advances in Databases and Information Systems, Springer-Verlag, 2005, ISBN 3 540 42555 1, pp. 178-188.

Berners-Lee, T.; and Fischetti, M. (2000). Weaving the Web: The Original Design and Ultimate Destiny of the World Wide Web by its Inventor. 1st edition. New York, NY, USA: HarperCollins Publishers.

Berners-Lee, T.; Hendler, J.; and Lassila, O. (2001) The Semantic Web, Scientific American (pp. 29-37).

Bonatti, P.; and Tettamanzi, A. (2006) Some Complexity Results on Fuzzy Description Logics. In Di Gesu, V., Masulli, F.,& Petrosino, A. (Eds.), Fuzzy Logic and Applications, Vol. 2955 of LNCS, pp. 19-24. Springer.

Brachman, R. J. (1977). What's in a Concept: Structural Foundations for Semantic Networks. International Journal of Man-Machine Studies, 9(2), 127-152.

Buntine, W. L. (1994) Learning with Graphical Models. Technical Report No. FIA-94-03. NASA Ames Research Center, Artificial Intelligence Research Branch.

Calì, Andrea; Lukasiewicz, Thomas; Predoiu, Livia; and Stuckenschmidt, Heiner (2008) Tightly Integrated Probabilistic Description Logic Programs for Representing Ontology Mappings. Proceedings of the 5th International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2008).

Calvanese, D.; and De Giacomo, G. (2003). Expressive Description Logics. In Baader, F., Calvanese, D., McGuiness, D., Nardi, D., & Patel-Schneider, P. (Eds.), The Description Logics Handbook: Theory, Implementation and Applications. 1st edition, chapter 5, pp. 184-225. Cambridge, UK: Cambridge University Press.

Carvalho, R. N.; Santos, L. L.; Ladeira, M.; and Costa, P. C. G. (2007) A Tool for Plausible Reasoning in the Semantic Web using MEBN. In Proceedings of the Seventh International Conference on Intelligent Systems Design and Applications (ISDA 2007). Mourele, L.; Nedjah, N.; Kacprzyk, J.; and Abraham, A. (eds.); pp. 381-386. October 22-24, 2007, Rio de Janeiro, Brazil.

Charniak, E. (1991). Bayesian Networks without Tears. AI Magazine, 12, 50-63.

Clemen, R. (1996). Making Hard Decisions. CA, Brooks/Cole.

Codd, E. F. (1970). A Relational Model for Large Shared Data Banks. Communications of the ACM, 13(6), 377-387.

Costa, P. C. G. (2005). Bayesian Semantics for the Semantic Web. Doctoral Dissertation. Department of Systems Engineering and Operations Research. 2005, George Mason University: Fairfax, VA, USA. p. 312.

Costa, P. C. G.; and Laskey, K. B. (2006). PR-OWL: A Framework for Probabilistic Ontologies. In Proceedings of the International Conference on Formal Ontology in Information Systems (FOIS 2006). November 9-11, 2006, Baltimore, MD, USA.

Costa, P. C. G.; Laskey, K. B.; Laskey, K. J.; and Pool, M. (2005). Proceedings of the First Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2005). Nov 7, 2005, Galway, Ireland.

Costa, P. C. G., Fung, F., Laskey, K. B., Laskey, K. J., & Pool, M. (2006).Proceedings of the Second Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2006). Nov 5, 2006, Athens, GA, USA.

Costa, P. C.G.; Ladeira, M.; Carvalho, R. N.; Laskey, K. B.; Santos, L. L.; and Matsumoto, S. (2008) A First-Order Bayesian Tool for Probabilistic Ontologies. To appear at the 21st International Florida Artificial Intelligence Research Society Conference (FLAIRS-21). May 15-17, 2008, Coconut Grove, Florida, USA.

D'Amato, C.; Fanizzi, N.; and Esposito F. (2006) Analogical Reasoning in Description Logics. In Proceedings of the Second Workshop on Uncertainty Reasoning for the Semantic Web. Athens, Georgia (USA), November, 5-9, 2006.

Damasio, C., Pan, J., Stoilos, G., & Straccia, U. (2006). An Approach to Representing Uncertainty Rules in RuleML. In Proceedings of the 2nd International Conference on Rules and Rule Markup Languages for the Semantic Web (RuleML-06). IEEE Computer Society. Available at

Ding, Z. (2005). BayesOWL: A Probabilistic Framework for Semantic Web. Doctoral dissertation. Computer Science and Electrical Engineering. 2005, University of Maryland, Baltimore County: Baltimore, MD, USA. p. 168.

Ding, Z., & Peng, Y. (2004). A Probabilistic Extension to Ontology Language OWL. In Proceedings of the 37th Annual Hawaii International Conference on System Sciences (HICSS'04). Jan, 5-8, 2004. Big Island, Hawaii, USA.

Dubois, D.; and Prade, H. (1994) Can We Enforce Full Compositionality in Uncertainty Calculi? Proceedings AAAI-1994, pp. 149-154. AAAI Press.

Eckhardt, A.; Horváth, T.; Maruščák, D.; Novotný, R.; and Vojtáš, P. (2007) Uncertainty Issues in Automating Process Connecting Web and User. In Proceedings of the Third Workshop on Uncertainty Reasoning for the Semantic Web (URSW- 2007). November 12, Busan, Korea.

Enderton, H. B. (2001) A Mathematical Introduction to Logic. 2nd Edition. Harcourt Academic Press

Fagin, R.; Lotem, A.; and Naor, M. (2003) Optimal Aggregation Algorithms for Middleware. In J. Computer and System Sciences 66 (2003), pp. 614-656.

Frege, G. (1879). Begriffsschrift, 1879, translated in Jean van Heijenoort, ed., From Frege to Gödel, Cambridge, MA: Harvard University Press, 1967.

Fukushige, Y. (2004). Representing Probabilistic Knowledge in the Semantic Web, W3C Workshop on Semantic Web for Life Sciences. Cambridge, MA, USA.

Jousselme, A. L.; Maupin, P.; and Bosse, E. (2003). Uncertainty in a Situation Analysis Perspective. In Proceedings of the Sixth International Conference of Information Fusion, vol. 2, pages 1207-1214. July 8-11, 2003, Cairns, Queensland, Australia.

Getoor, L.; Friedman, N.; Koller, D.; and Pfeffer, A. (2001). Learning Probabilistic Relational Models. New York, NY, USA: Springer-Verlag.

Getoor, L.; Koller, D.; Taskar, B.; and Friedman, N. (2000). Learning Probabilistic Relational Models with Structural Uncertainty. Paper presented at the ICML-2000 Workshop on Attribute-Value and Relational Learning:Crossing the Boundaries. Stanford, CA, USA.

Gilks, W.; Thomas, A.; and Spiegelhalter, D. J. (1994). A Language and Program for Complex Bayesian Modeling. The Statistician, 43, 169-178.

Giugno, R.; and Lukasiewicz, T. (2002) P-SHOQ(D): A Probabilistic Extension of SHOQ(D) for Probabilistic Ontologies in the Semantic Web. Proceedings of the 8th European Conference on Logics in Artificial Intelligence (JELIA 2002). Extended version: Lukasiewicz, Thomas (2007) Expressive Probabilistic Description Logics, Artificial Intelligence, 172(6-7), 852-883, April 2008.

Gu, T.; Pung, H. K.; and Zhang, D. Q. (2004) A Bayesian Approach for Dealing with Uncertainty Contexts, in Second International Conference on Pervasive Computing. 2004. Vienna, Austria: Austrian Computer Society.

Gurský, P.; Horváth, T.; Jirásek, J.; Krajči, S.; Novotný, R.; Vaneková, V.; and Vojtáš, P. (2007) Knowledge Processing for Web Search – An Integrated Model, In: C. Badica and M. Paprzycki (eds.) Proceedings of the 1st International Symposium on Intelligent and Distributed Computing (IDC 2007), Studies in Computational Intelligence (vol. 78), Springer, 2007, pp: 95-104.

Gurský, P.; Horváth, T.; Jirásek, J.; Krajči, S.; Novotný, R.; Vaneková, V.; and Vojtáš, P. (2007) Web Search with Variable User Model. In Datakon 2007, L. Popelinsky and O. Vyborny eds. Masarykova Univerzita, 111-121.

Hájek, P. (1998). Metamathematics of Fuzzy Logic. Kluwer.

Hájek, P. (2005). Making Fuzzy Description Logics More Expressive. Fuzzy Sets and Systems, 154(1), 1-15.

Hájek, P. (2006). What Does Mathematical Fuzzy Logic Offer to Description Logic? In Sanchez, E. (Ed.), Capturing Intelligence: Fuzzy Logic and the Semantic Web. Elsevier.

Heckerman, D.; Mamdani, A.; and Wellman, M. P. (1995). Real-World Applications of Bayesian Networks. Communications of the ACM, 38(3), 24-68.

Heckerman, D.; Meek, C.; and Koller, D. (2004) Probabilistic Models for Relational Data. Technical Report MSR-TR-2004-30, Microsoft Corporation, March 2004. Redmond, WA, USA.

Heinsohn, J. (1994) Probabilistic Description Logics. Paper presented at the Tenth Conference on Uncertainty in Artificial Intelligence (UAI-94), Jul 29-31.Seattle, WA, USA.

Hölldobler, S.; Khang, T. D.; and Störr, H.-P. (2002) A Fuzzy Description Logic with Hedges as Concept Modifiers. In Proceedings InTech/VJFuzzy-2002, pp. 25-34.

Hölldobler, S.; Nga, N. H.; and Khang, T. D. (2005) The Fuzzy Description Logic ALCflh. In Proceeedings DL-2005.

Horridge, M.; Knublauch, H.; Rector, A.; Stevens, R.; and Wroedn, S. (2004) A Practical Guide to Building OWL Ontologies using the Protégé-OWL Plugin and CO-ODE Tools. The University of Manchester.

Horrocks, I. (2002) DAML+OIL: A Reasonable Web Ontology Language. Keynote talk at the WES/CAiSE Conference. Toronto, Canada.

Horrocks, I.; and Sattler, U. (2001) Ontology Reasoning in the SHOQ(D) Description Logic. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI 2001), Aug 4-10. Seattle, WA, USA.

Horvath, T.; and Vojtas, P. (2006) Ordinal Classification with Monotonicity Constraints. In ICDM 2006, LNAI 4065, Springer, 2006, p. 217-225.

Jaeger, M. (1994) Probabilistic Reasoning in Terminological Logics. Paper presented at the Fourth International Conference on Principles of Knowledge Representation and Reasoning (KR94), May 24-27. Bonn, Germany.

Jaeger, M. (1997) Relational Bayesian Networks. Paper presented at the 13th Annual Conference on Uncertainty in Artificial Intelligence (UAI-97), August 1-3, Providence, RI, USA.

Jaeger, M. (2006) Probabilistic Role Models and the Guarded Fragment. In Proceedings IPMU-2004, pp. 235–242. Extended version in Int. J. Uncertain. Fuzz., 14(1), 43–60, 2006.

Koller, D.; Levy, A. Y.; and Pfeffer, A. (1997) P-CLASSIC: A Tractable Probabilistic Description Logic. Paper presented at the Fourteenth National Conference on Artificial Intelligence (AAAI-97), July 27-31. Providence, RI, USA.

Koller, D.; and Pfeffer, A. (1997) Object-Oriented Bayesian Networks. Paper presented at the Thirteenth Conference on Uncertainty in Artificial Intelligence (UAI-97). San Francisco, CA, USA.

Kolmogorov, A. N. (1960) Foundations of the Theory of Probability. 2nd edition. New York, NY, USA: Chelsea Publishing Co. Originally published in 1933.

Langseth, H.; and Nielsen, T. (2003) Fusion of Domain Knowledge with Data for Structured Learning in Object-Oriented Domains. Journal of Machine Learning Research, Special Issue on the Fusion of Domain Knowledge with Data for Decision Support, vol. 4, pp. 339-368, July 2003.

Laskey, K.B. (2007) MEBN: A Language for First-Order Bayesian Knowledge Bases. Artificial Intelligence, 172(2-3), 2007.

Laskey, K. B.; and Costa P. C. G. (2005). Of Klingons and Starships: Bayesian Logic for the 23rd Century, in Uncertainty in Artificial Intelligence: Proceedings of the Twenty-first Conference. 2005, AUAI Press: Edinburgh, Scotland.

Laskey, K. B.; and Mahoney, S. M. (1997). Network Fragments: Representing Knowledge for Constructing Probabilistic Models. In Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence (UAI-97), August, 1997. Providence, RI, USA.

Liu, B. (2005) WWW-2005 Tutorial: Web Content Mining. Presented at the Fourteenth International World Wide Web Conference (WWW-2005), May 10-14, 2005, Chiba, Japan.

Li, Y.; Xu, B.; Lu, J.; and Kang, D. (2006) Discrete Tableau Algorithms for SHI. In Proceeedings DL-2006.

Li, Y.; Xu, B.; Lu, J.; Kang, D.; and Wang, P. (2005a) Extended Fuzzy Description Logic ALCN. In Proceedings KES-2005, Vol. 3684 of LNCS, pp. 896-902. Springer.

Li, Y.; Xu, B.; Lu, J.; Kang, D.; and Wang, P. (2005b). A Family of Extended Fuzzy Description Logics. In Proceedings COMPSAC-2005, pp. 221-226. IEEE Computer Society.

Lloyd, J.; and Ng, K.S (2008) Probabilistic Reasoning in a Classical Logic. In Journal of Applied Logic.

Lukasiewicz, T. (2002). Probabilistic Default Reasoning with Conditional Constraints. Ann. Math. Artif. Intell., 34(1-3), 35-88, 2002.

Lukasiewicz, T. (2005). Probabilistic Description Logic Programs. In Proceedings ECSQARU 2005, Barcelona, Spain, July 2005. Vol. 3571 of LNCS, pp. 737-749. Springer. Extended version:International Journal of Approximate Reasoning 45(2), 288-307, 2007.

Lukasiewicz, T. (2006). Fuzzy Description Logic Programs under the Answer Set Semantics for the Semantic Web. In Proceedings of the 2nd International Conference on Rules and Rule Markup Languages for the Semantic Web (RuleML-06), pp. 89-96. IEEE Computer Society. Extended version: Fundamenta Informaticae 82, 1-22, 2008.

Lukasiewicz, T. (2007) Tractable Probabilistic Description Logic Programs. Proceedings of the 1st International Conference on Scalable Uncertainty Management (SUM 2007).

Lukasiewicz, T. (2008). Expressive Probabilistic Description Logics. Artificial Intelligence, 172(6-7), 852-883.

Lukasiewicz, T.; and Schellhase, J. (2006) Variable-Strength Conditional Preferences for Ranking Objects in Ontologies. Proceedings of the 3rd European Semantic Web Conference (ESWC 2006). Extended version: Variable-Strength Conditional Preferences for Ranking Objects in Ontologies. Journal of Web Semantics, 5(3), 180-194, September 2007.

Lukasiewicz, T.; and Straccia, U. (2007a) Description Logic Programs under Probabilistic Uncertainty and Fuzzy Vagueness. In Proceedings ECSQARU 2007, Hammamet, Tunisia, October/November 2007. Vol. 4724 of LNCS, pp. 187-198. Springer.

Lukasiewicz, T.; and Straccia, U. (2007b) Top-k Retrieval in Description Logic Programs Under Vagueness for the Semantic Web. Proceedings of the 1st International Conference on Scalable Uncertainty Management (SUM 2007).

Lukasiewicz, T.; and Straccia, U. (2007c) Tightly Integrated Fuzzy Description Logic Programs Under the Answer Set Semantics for the Semantic Web. Proceedings of the 1st International Conference on Web Reasoning and Rule Systems (RR 2007).

Minsky, M. L. (1975). Framework for Representing Knowledge. In The Psychology of Computer Vision. P. H. Winston (Eds.), pp. 211-277. New York, NY: McGraw-Hill.

Mitra, P.; Noy, N. F.; and Jaiswal, A. R. (2004) OMEN: A Probabilistic Ontology Mapping Tool. Workshop on Meaning Coordination and Negotiation at the Third International Conference on the Semantic Web (ISWC-2004), November, 2004. Hisroshima, Japan.

Mitra, P.; Noy, N.; and Jaiswal, A. R. (2005) Ontology Mapping Discovery with Uncertainty. Presented at the Fourth International Semantic Web Conference (ISWC 2004). November, 7th 2005, Galway, Ireland.

Morgan, M. G.; and M. Henrion (1990) Uncertainty: A Guide to Dealing with Uncertainty in Quantitative Risk and Policy Analysis. New York, Cambridge University Press.

Neapolitan, R. E. (1990) Probabilistic Reasoning in Expert Systems: Theory and Algorithms. New York, NY, USA: John Wiley and Sons,Inc.

Neapolitan, R. E. (2003) Learning Bayesian Networks. New York, NY, USA: Prentice Hall.

Nickles, M. (2007)Social Acquisition of Ontologies from Communication Processes. Applied Ontology, 2007.

Nikolov, A.; Uren, V.; Motta, E.; and de Roeck, A. (2007) Using the Dempster-Shafer Theory of Evidence to Resolve ABox Inconsistencies. In Proceedings of the 3rd Workshop on Uncertainty Represention for the Semantic Web (URSW 2007). November 12, 2007. Busan, Korea.

Pan, R.; Ding, Z.; Yu, Y.; and Peng, Y. (2005). A Bayesian Approach to Ontology Mapping. In Proceedings of the Fourth International Semantic Web Conference (ISWC-2005), November, 2005. Galway, Ireland.

Pan, J. Z.; Stoilos, G.; Stamou, G.; Tzouvaras, V.; and Horrocks, I. (2006). f-SWRL: A Fuzzy Extension of SWRL. In Data Semantics, special issue on Emergent Semantics, Volume 4090/2006: 28-46.

Pan, J. Z.; Stamou, G.; Stoilos, G.; and Thomas, E. (2008) Scalable Querying Services over Fuzzy Ontologies. To Appear 17th International World-Wide-Web Conference (WWW 2008), Beijin, 2008.

Parsons, S. (1996). Current Approaches to Handling Imperfect Information in Data Acknowledgement Bases. In IEEE Transactions on Knowledge and Data Engineering, vol. 8, issue 3, June 1996, pages 353-372. Los Alamitos, CA, USA: IEEE Computer Society.

Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Mateo, CA, USA: Morgan Kaufmann Publishers.

Peng, Y.; Ding, Z.; Pan, R.; Yu, Y.; Kulvatunyou, B.; Izevic, N.; Jones, A.; and Cho, H. (2007). A Probabilistic Framework for Semantic Similarity and Ontology Mapping. In Proceedings of the 2007 Industrial Engineering Research Conference (IERC), May, 2007. Nashville, TN, USA.

Peirce, C. S. (1885) On the Algebra of Logic. American Journal of Mathematics, 7:180-202.

Pfeffer, A. (2001) IBAL: A Probabilistic Rational Programming Language International. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-2001), August 4-10, vol. 1, pp. 733-740. Seattle, WA, USA.

Pfeffer, A.; Koller, D.; Milch, B.; and Takusagawa, K. T. (1999) SPOOK: A System for Probabilistic Object-Oriented Knowledge Representation. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, pp. 541-550, July 30 – August 1. Stockholm, Sweden

Pool, M.; and Aikin, J. (2004). KEEPER and Protégé: An Elicitation Environment for Bayesian Inference Tools. Paper presented at the Workshop on Protégé and Reasoning held at the Seventh International Protégé Conference, July 6 – 9. Bethesda, MD, USA.

Ragone, A.; Straccia, U.; Di Noia, T.; Di Sciascio, E; and Donini, F. M. (2007) Vague Knowledge Bases for Matchmaking in P2P E-Marketplaces. In Proceedings of the Fourth European Semantic Web Conference (ESWC-07). pp. 414-428.

Ramsey, F. P. (1931) The Foundations of Mathematics and other Logical Essays. London, UK: Kegan Paul, Trench, Trubner & Co.

Richardson, M.; Agrawal, R.; and Domingos, P. (2003) Trust Management for the Semantic Web. Proceedings of the Second International Semantic Web Conference, 2003.

Sanchez, D.; and Tettamanzi, A. (2004) Generalizing Quantification in Fuzzy Description Logics. In Proceedings 8th Fuzzy Days in Dortmund.

Sanchez, D.; and Tettamanzi, A. (2006). Fuzzy Quantification in Fuzzy Description Logics. In Sanchez, E. (Ed.), Capturing Intelligence: Fuzzy Logic and the Semantic Web. Elsevier.

Sanchez, E. (2006) Fuzzy Logic and the Semantic Web. 1st edition, April 3, 2006. Oxford, UK: Elsevier Science.

Schmidt-Schauß, M.; and Smolka, G. (1991) Attributive Concept Descriptions with Complements. Artificial Intelligence, 48(1), 1-26.

Schum, D. (1994). Evidential Foundations of Probabilistic Reasoning. New York, Wiley.

Spiegelhalter, D. J.; Thomas, A.; and Best, N. (1996) Computation on Graphical Models. Bayesian Statistics, 5, 407-425.

Sowa, J. F. (2000). Knowledge Representation: Logical, Philosophical, and Computational Foundations. Pacific Grove, CA, USA: Brooks/Cole.

Stoilos, G.; Stamou, G.; Tzouvaras, V.; Pan, J. Z.; and Horrocks, I. (2005a). Fuzzy OWL: Uncertainty and the Semantic Web. In Proceedings of the International Workshop on OWL: Experience and Directions (OWL-ED2005).

Stoilos, G.; Stamou, G. B.; Tzouvaras, V.; Pan, J. Z.; and Horrocks, I. (2005b). The Fuzzy Description Logic f-SHIN. In Proceedings of the First Workshop on Uncertainty Reasoning for the Semantic Web (URSW-2005), pp. 67-76.

Stoilos, G.; Stamou, G.; Tzouvaras, V.; Pan, J. Z.; and Horrock, I. (2005) A Fuzzy Description Logic for Multimedia Knowledge Representation. In Proceedings of the International Workshop on Multimedia and the Semantic Web.

Stoilos, G.; Straccia, U.; Stamou, G.; and Pan, J. Z. (2006) General Concept Inclusions in Fuzzy Description Logics. In Proceedings ECAI-2006, pp. 457-61. IOS Press.

Stoilos, G.; Simou, N.; Stamou, G.; and Kollias, S. (2006) Uncertainty and the Semantic Web. IEEE Intelligent Systems, 21(5), p. 84-87, 2006.

Stoilos, G.; Stamou, G.; Pan J. Z.; Tzouvaras, V.; and Horrocks, I. (2007) Reasoning with Very Expressive Fuzzy Description Logics, Journal of Artificial Intelligence Research, 30(8), p. 273-320.

Stoll, R. P. (1963) Set Theory and Logic. Dover Publications Inc.

Straccia, U. (1998) A Fuzzy Description Logic. In Proceedings AAAI-1998, pp. 594-599. AAAI Press/MIT Press.

Straccia, U. (2001) Reasoning within Fuzzy Description Logics. J. Artif. Intell. Res., 14, 137-166.

Straccia, U. (2004) Transforming Fuzzy Description Logics into Classical Description Logics. In Proceedings JELIA-2004, Vol. 3229 of LNCS, pp. 385-399. Springer.

Straccia, U. (2005a) Description Logics with Fuzzy Concrete Domains. In Proceedings UAI-2005, pp. 559-567. AUAI Press.

Straccia, U. (2005b) Fuzzy ALC with Fuzzy Concrete Domains. In Proceeedings DL-2005, pp. 96-103.

Straccia, U. (2005c) Towards a Fuzzy Description Logic for the Semantic Web. In Proceedings of the Second European Semantic Web Conference, ESWC 2005.

Straccia, U. (2007) Towards Vague Query Answering in Logic Programming for Logic-based Information Retrieval. In Proceedings of the World Congress of the International Fuzzy Systems Association (IFSA-07). Cancun, Mexico.

Straccia, U.; and Visco, G. (2007) DLMedia: an Ontology Mediated Multimedia Information Retrieval System. InProceedings of the International Workshop on Description Logics (DL-07). Insbruck, Austria.

Tresp, C.; and Molitor, R. (1998) A Description Logic for Vague Knowledge. In Proceedings ECAI-1998, pp. 361-365. J. Wiley & Sons.

Viegas Damasio, C.; Pan, J. Z.; Stoilos, G.; and Straccia, U. (2007) Representing Uncertainty in RuleML. To Appear in Fundamenta Informaticae.

Vojtas, P. (2007) EL Description Logic with Aggregation of User Preference Concepts. M. Duzi et al. Eds. Information modelling and Knowledge Bases XVIII, pp. 154-165. Amsterdam: IOS Press.

Vojtas P.; and Vomlelova, M. (2006) On Models of Comparison of Multiple Monotone Classifications. In Proceedings of the IPMU'2006, B. Bouchon-Meunier and R. R. Yager eds., pp. 1236-1243. Paris: Editions EDK.

Yaghlane, B. B.; and Laamari, N. (2007) OWL-CM : OWL Combining Matcher Based on Belief Functions Theory. In Proceedings of the 2nd International Workshop on Ontology Matching (OM-2007). November 11, 2007. Busan, Korea.

Yaghob, J.; and Zavoral, F. (2006) Semantic Web Infrastructure using Data Pile. In WI IATW 06, IEEE Los Alamitos, ISBN 0 7695 2749 3, 2006, pp.630-633.

Yang, Y.; and Calmet, J. (2005) OntoBayes: An Ontology-Driven Uncertainty Model. Presented at the International Conference on Intelligent Agents, Web Technologies and Internet Commerce (IAWTIC2005). Vienna, Austria.

Yen, J. (1991) Generalizing Term Subsumption Languages to Fuzzy Logic. In Proceedings IJCAI-1991, pp. 472-177. Morgan Kaufmann.

Yelland, P. M. (2000) An Alternative Combination of Bayesian Networks and Description Logics. In Proceedings KR-2000, pp. 225–234. Morgan Kaufmann.

Appendix A: Use Cases

A.1. Use case 1: Discovery

A.1.1. Purpose and Goals

Given a populated catalogue of items and a user’s criteria for a particular item potentially listed in the catalogue, identify the best match.

A.1.2 Assumptions and Preconditions

• The catalogue has been populated using a property set and property values that have a machine processable representation of the vocabulary used
• A similar machine processable representation exists for the vocabulary used to state the search criteria.

A.1.3 Required Resources

1. Catalogue populated by independent entities whose native descriptions may not directly align with the catalogue property and value vocabularies. Catalogue entries may be collected from other catalogues. Catalogue may also contain entries for multiple items, each with its own property vocabulary.
2. Description of catalogue property and value vocabularies.
3. Description of user property and value vocabularies.

A.1.4 Successful End

The user finds an item sufficiently close to their search criteria and is not hampered by vocabulary differences with those who populated the catalogue.

A.1.5 Failed End

The user does not find an item sufficiently close to their search criteria but has an explanation of how the criteria was not met, e.g. there were no screws of the length needed.

A.1.6 Main Scenario

1. User specifies item of interest, e.g. looking for a MP3 player.
2. System identifies item class and returns form with list of properties used to describe item. (If system does not recognize exact class requested, uncertainty in whether system identifies most appropriate class. UncAnn - UncertaintyNature: Epistemic; UncAnn - UncertaintyType: Vagueness)
3. User provides target search values for properties of interest (e.g., hard drive size, impact resistance, price). System may also support indicating relative importance of search properties chosen.
   (Uncertainty in whether user understands semantics of properties, whether catalogue entry provider entered values consistent with property semantics intended by system, assumed by user. UncAnn - UncertaintyNature: Epistemic; UncAnn - UncertaintyType: Vagueness)
4. System returns ranked list of item instances, e.g. different models of MP3 players from different producers.
   (Uncertainty in whether user understands semantics of target values, e.g. "high impact resistance" vs. "5g impact". UncAnn - UncertaintyNature: Epistemic; UncAnn - UncertaintyType: Empiricial)

A.1.7 Additional Background Information or References

Service oriented architecture (SOA) assumes a world of distributed resources which are accessible across a network. It is assumed that catalogues will exist for different classes of resources, such as SOA services, and the user will be able to search these catalogues for a desired item. Note, a class of items will be described using a list of relevant properties and items belonging to that class will be described by assigning values to these properties. For discovery to occur, there must be some alignment of or mediation between the list of properties used by those populating the catalogue and those searching it. There must also be some alignment of or mediation between the nonnumeric values assigned to the properties, both in describing items for the catalogue and defining the search criteria.

A.1.8 General Issues and Relevance to Uncertainty

• Terminology mismatches (UncAnn - UncertaintyNature: Epistemic;