Bayesian semantics for the semantic web

НазваниеBayesian semantics for the semantic web
Размер1.34 Mb.
1   2   3   4   5   6   7   8   9   ...   20

The IsA MFrag. The IsA MFrag is the home MFrag for IsA(ptl, ei), where ei is an instance of type ptl. As an example, suppose we replace ptl with the unique identifier corresponding to the Starship type label. If we then replace ei with the unique identifier of a starship entity (say !ST1), then IsA(ptl, ei) becomes Isa(Starhship, !ST1), which has value T. Conversely, if the variable ei is replaced with a unique identifier of a planet entity (say !P1) then IsA(ptl, ei) becomes Isa(Planet, !ST1), which has value F.

The IsA MFrag has only one context node, which is sat­isfied when the variable ptl is replaced by a TypeLabel entity. The MFrag’s only resident node, IsA(ptl, ei), is true when ei represents an instance of the type represented by ptl. This random variable has two parents, the input nodes Type(ei) (the type of ei) and the Boolean RV term Isa(tl,ei)(ptl=ParentType(tl)) (ei represents an in­stance of tl and tl is a subtype of ptl). Its value is T when either of its parents is true. That is, IsA(ptl, ei) is true when Type(ei) is ptl or (recursively) when Isa(tl, ei) is true for a type tl that is a descendant of ptl in the type hierarchy. The distribution for the Boolean RV term Isa(tl,ei)(ptl = Parent­Type(tl)) is defined via the built-in logical MFrags.

We noted above that type systems are typically defined by specifying a unary predicate for each type. Our IsA predicate is binary. We have taken advantage of polymorphism to define a single binary predicate Isa(tl,ei) rather than a unary predicate for each type (e.g., IsaStarship(ei), IsaPlanet(ei), etc.)24

The SubType MFrag. The three upper, unconnected nodes in the SubType MFrag of Figure 22 are context nodes specifying that the variables tl and stl are placeholders for unique identifiers representing TypeLabel entities and that the first TypeLabel (referred to by tl) is the parent type of the second (referred to by stl). The rightmost input note, IsA(tl, ei), has its local distribution defined in the IsA MFrag above, so its value will be T when the unique identifier replacing ei refers to an entity whose type is either tl or one of its descendant types. The other input node, VCount(stl), has a positive number as its value, and represents the relative probability that an entity of type ParentType(stl) is an instance of stl. That is, if our only information about an instance ei is that its type is a subtype of tl, and if stl1 and stl2 are labels for subtypes of tl, the ratio of the probability of Isa(stl1, ei) to the probability of Isa(stl2, ei) is given by VCount(stl1)/VCount(stl2).

The name VCount stands for “virtual count,” a term used in the literature on Bayesian learning to refer to parameters in a prior distribution that correspond roughly to remembered prior observations. That is, we can think of VCount(tl) as the number of instances of tl that have been encountered in previously experienced situations (although there is no requirement that its value be an integer). Virtual counts are important for representing type uncertainty.

Because virtual counts behave like remembered counts, the virtual count for a type is constrained to be equal to the sum of the virtual counts for its subtypes. The distribution for the resident node VCount(tl) enforces this constraint. This MFrag defines virtual counts only for non-leaf nodes in the type hierarchy. Virtual counts for leaf nodes are defined in the virtual count initialization MFrag described below. The context constraint tl=ParentType(stl) ensures that tl is not a leaf node in the type hierarchy. The distribution of VCount(tl) places probability 1 on a value equal to the sum of the virtual counts for subtypes of tl. Although virtual counts are not required to be integers, as for all MEBN random variables, the possible values must be a countable set.

The resident node SubType(tl, ei) has as its possible values all entities of type TypeLabel other than the type label Entity, along with the value  (absurd). When the parent node IsA(tl, ei) has value F, then SubType(tl, ei) has value  (i.e., whether an entity is an instance of something that is not a type is an absurd question). If IsA(tl, ei) has value F, then the distribution for SubType(tl, ei) puts non-zero probability only on values for which there is a VCount(stl) parent (these are stl for which the context constraint tl=ParentType(stl) is met, i.e., subtypes of tl). The probabilities of the subtypes are proportional to their virtual counts.

The VCount Initialization MFrag. The context nodes for this MFrag ensure that the variable tl is replaced by the unique identifier of an entity that (1) is of type TypeLabel and (2) has no subtypes (i.e. it is a leaf node in the type hierarchy). The context node ($stl, tl=ParentType($stl)) represents the negation of an existentially quantified first-order sentence. It is satisfied when there is no entity instance of which tl is a parent type. The symbol $stl is a Skolem term, which represents a generic instance that satisfies the sentence if it is satisfiable and otherwise has value  (Laskey, 2005). We note that one of the conditions of the theorem of Laskey (2005) that a conditional distribution exists on interpretations of any consistent, finitely axiomatizable first-order theory is that no context RV may contain quantifier random variables. If there are only finitely many types, quantified statements about type labels can be treated as shorthand notation for finite conjunctions and disjunctions. Thus, the theorem still holds for typed MEBN.

The distribution of the resident node VCount(tl) specifies a probability distribution for the leaf node tl in the type hierarchy. The distribution of VCount(tl) for leaf nodes tl in the type hierarchy is supplied by the domain expert.

Note that the random variable VCount(tl) has two resident MFrags, thus violating the original conditions for a valid MTheory (Laskey 2005). However, it satisfies the conditions for extended version defined above, because the contexts for the two home MFrags are disjoint.

1.18.2The Star Trek MTheory Revisited

The MTheory of Figure 23 has takes ad­vantage of our extended version of MEBN, but is equiva­lent, mutatis mutandis, to the MTheory of Figure 21. The most obvious modification is the absence of the Type and the Isa MFrags. Also, the new version allows several similar random variable labels to be combined into a single label, such as in the case of nodes DistFromOwn() in the Transporter and the Starship MFrag.

  1. Star Trek MTheory with the Transporter MFrag – Typed Version

It would be straightforward to add Starship subtypes (e.g., MilitaryStarship and CivilianStarship) to this MTheory. Distributions defined for enti­ties of type Starship would be inherited by entities of type MilitaryStarship and CivilianStarship unless overridden.

The ability to use the same name for similar concepts applied to different types of entities is very useful for the knowledge base designer. It supports portability and reusability, allows for more natural naming conventions, supports more compact representations, and helps to prevent errors. Less obvious potential gains include savings in memory allocation, the possibility of optimizing compilers and reasoners to exploit the type structure, and other advantages of standard type systems. These advantages can now be applied to a probabilistic first-order logic.

1.19Using Quiddity*Suite for Building SSBNs

Information Extraction and Transport’s (IET) Quiddity*Suite™ is a probabilistic frame-based modeling toolkit that implements many features of MEBN logic and supports type uncertainty and multiple inheritance. Quiddity*Suite has been applied to a wide range of problems ranging from visual target recognition to multi-sensor data fusion to dynamic decision systems in the C3I arena (Fung et al., 2004).

A frame is a knowledge representation structure that expresses a concept or a situation (Minsky, 1975), and it was a rather novel approach to knowledge representation for a period in which rule-based or logic-based were the predominant formalisms. Frame-based systems allow knowledge builders to easily describe the types of objects in a domain. As such, they provide the conceptual basis for expressing knowledge in an object-oriented way that inspired many subsequent formalisms (e.g., Bobrow & Winograd, 1977; Brachman & Schmolze, 1985; Kifer et al., 1990; Greco et al., 1992). According to Fikes & Kehler (1985), frames represent entities or classes of entities, and can incorporate sets of attribute descriptions called slots. Also, slots can have a set of properties, which are called facets of a slot.

In standard frame languages, there is no pre-defined way to express uncertainty about values of an attribute.  Unless a slot is left unassigned, either the value must be known or a default value should be used.  Quiddity*Suite expresses uncertainty about the value of an attribute by associating a random variable with each slot for which the value may be uncertain.  When an instance of the frame is created, a random variable is created for each uncertain slot. In order to carry the information needed to define probability distributions for the random variables associated with uncertain slots, Quiddity*Suite uses a set of pre-defined facets, which represent possible states, parents, and conditional distribution given parents.

A detailed coverage on Quiddity*Suite’s approach for representing uncertainty in frame-based systems is outside the scope of this work, but in our research experiments we were able to use it as a means to perform SSBN construction from evidence applied to a generative MTheory.

As a proof of concept on the feasibility of using Quiddity*Suite as a partial implementation of MEBN, we have translated the Star Trek MTheory into Quiddity*Suite format. The resulting model is capable of building any SSBN that can be generated from the original Star Trek MTheory. The source code for the model is presented in Appendix A. In this Section; we describe the translation process emphasizing which features could be directly translated and which required some additional effort. Also, we address some of the issues and details that should be taken into account when translating MTheories to Quiddity Models.

Readers should have in mind that the next Subsections are not meant to be a Quiddity*Suite tutorial or learning asset. Instead, the main purpose is to show how the concepts in MEBN logic translate (or not) to Quiddity*Suite elements. Even though knowledge on Quiddity*Suite is necessary for understanding/applying the general translation rules presented below, readers that are familiar with frame systems notation would find relatively easy to understand the general idea of the translation procedures.

1.19.1Concepts with Direct Translation

In the typed version of MEBN logic developed for this research, every domain-specific entity has a type, which is represented as one of the possible values of node Type(e) in the built-in Type MFrag). By definition, all possible values of node Type(e) have their type defined as TypeLabel, which is itself a built-in possible value or Type(e). As an example, the Starship MTheory has four types of entities (starships, sensor reports, zones, and time steps), so the possible states of its built-in node Type(e) are the special built-in states plus the domain-specific states Starship, SensorReport, Zone, and TimeStep. Also, the typed version of MEBN logic presented here also supports sub-typing, so we could easily create a type hierarchy in which starships would have subtypes (say) military and civilian.

Quiddity*Suite represents entity types as frames, and also supports frame sub-typing. An entity type in MEBN logic corresponds to a frame in Quiddity*Suite. Thus, a good way of enforcing compatibility between models based on MEBN logic and their counterparts in Quiddity*Suite is to use an approach that makes such correspondence more explicit.

As explained in Chapter 3, MEBN logic allows multiple, equivalent ways of portraying the same knowledge (recall example in Figure 13). Therefore, MEBN modelers willing to achieve full compatibility with Quiddity*Suite (and with frame systems in general) are encouraged to use the object oriented approach we sought with the Star Trek MTheory, which used the concept of an entity cluster.

Definition 3: An entity cluster is a group of MFrags within a generative MTheory having the following characteristics:

  1. In any MFrag contained in the entity cluster, there is an ordinary variable, called the subject argument of the MFrag, such that any non-constant random variable in the MFrag has the subject argument as one of its arguments.

  2. The context constraints of each MFrag in the entity cluster specify the type of the subject argument. This type is called the subject type of the MFrag.

  3. The subject types of all MFrags in the entity cluster are the same.◼

The above definition addresses only the top-level classes. That is, if entity clustering is desired for subclasses then this definition will have to be extended to accommodate subtyping. As an example, if we had different subtypes of starship, we might have entity clusters that contained definitions for some nodes at the supertype level, and other nodes at the subtype level. However, formalizing the translation rules for subtyping is a subject for future work.

Figure 24 depicts the Star Trek MTheory divided by its entity clusters. Building an MEBN model using the entity clusters approach facilitates the interoperability among different modeling tools. In the specific case of the Star Trek MTheory, it allows a direct mapping between frames and domain-specific entities (which have all of its attributes within the same entity cluster). In addition, using this modeling approach makes it easier to keep MEBN logic’s flexibility to display the same information in different MFrag configurations. As an example, depending on the model objectives, the Starship MFrag in Figure 24 could be easily replaced with the three equivalent MFrags in Figure 13.

  1. Entity Clusters of Star Trek MTheory

Using the entity cluster modeling approach, most concepts in MEBN logic can be easily translated to Quiddity*Suite syntax. Within a given entity cluster, all resident nodes are directly mapped as slots of the frame that corresponds to that entity cluster. Input nodes are mapped in accordance with the MFrag in which they are resident nodes. If an input node is a “copy” of a resident node defined in an MFrag within the entity cluster, then it is listed directly in the Parents facet of their children. Input nodes defined outside the entity cluster are also listed in the Parents facet of their children, but have their name preceded by a pointer slot. A pointer slot is a slot that has another frame as its domain, and it is used for making references to that frame.

Figure 25 exemplifies the above explanation using the Sensor Report entity cluster depicted in the MTheory in Figure 24. The cluster’s name is directly used in the frame (bullet 1 in the figure), and each of the resident nodes of the cluster’s two MFrags is transformed into a slot in that frame (bullets 2 to 4). It is important to note that node Subject(sr) is an attribute of a sensor report that links each instance of a sensor report to its respective subject. In our model, subjects of sensor reports are starships and thus the possible states of Subject(st) are starship entities. Therefore, slot subject has frame Starship as its domain and works as a pointer to that domain.

The use of a pointer is easily observable in this example, since all the input nodes were defined outside the Sensor Report entity cluster. That is, there are no parent resident nodes and also no input nodes defined within the cluster. In this case, each input node is defined in the Parents facet of its respective children with the pointer node’s name preceding it (see bullet 5 for the parents of SRClass).

  1. Mapping the Sensor Report Entity Cluster to a Frame

Although not emphasized in Figure 25 for the sake of simplicity, the probability distribution and the states of a resident node are directly translated to its respective slot’s distribution and domain facets respectively. Quiddity*Suite’s syntax provide a rich list of possibilities for portraying a probability distribution via the distribution facet, from built-in standard distributions (e.g. UniformDiscreteDistribution for the discrete uniform distribution) to highly complex combinations of functions. Also, there are different possibilities for defining the domain of a slot via the domain facet, but covering all the possibilities is outside the scope of this dissertation. Table 3 summarizes the concepts discussed above, which can be directly translated from MEBN to Quiddity*Suite, and presents some examples.

  1. MEBN Elements Directly Translated into Quiddity*Suite

MEBN Concept

Quiddity*Suite Representation

Quiddity*Suite Examples
(from the Star Trek MTheory)

Entity Type


frame Starship isa Frame

Type hierarchy

Frame hierarchy.

frame MilitaryStarship isa Starship

Resident nodes


slot z_ZoneEShips

Parent resident and input nodes defined within the entity Cluster

Parents facet

facet parents = [z_ZoneNature]

Parent input nodes defined outside the entity cluster

Parents facet + pointer Slot

facet parents = [PointerSlot.z_ZoneNature]

Probability Distribution

Distribution facet

facet distribution =

facet distribution = MaxDistribution


Domain facet

facet domain = booleandomain

facet domain = Starship

facet domain = [ ]
1   2   3   4   5   6   7   8   9   ...   20


Bayesian semantics for the semantic web iconQueries: Enabling Querying for Semantic Associations on the Semantic Web

Bayesian semantics for the semantic web iconSemantic Web : a guide to the Future of xml, Web Services, and Knowledge Management

Bayesian semantics for the semantic web iconThe Semantic Model contains a high level description of the Actions that operate on the objects and attributes in the model. This document does not describe the mapping of the semantics onto a specific protocol or network environment

Bayesian semantics for the semantic web iconЗадача: Предоставляет пользователю унифицированную среду содержащую сервисы и функциональности, варьирующиеся от информационных сервисов и сервисов извлечения
По аналогии с Semantic Web, Semantic Grid может быть определен как расширение современных grid, где информация и сервисы имеют четкий...
Bayesian semantics for the semantic web iconThis document contains a list of references to publications and reports about Bayesian Net technology, and especially Bayesian Net applications. The report will

Bayesian semantics for the semantic web iconValentina Janev, Sanja Vranes, Semantic Web Tools and Technologies for Competence Management, Lambert Academic Publishing GmbH, isbn: 978-8454-4166-5, Sarbrucken, Germany, 2011

Bayesian semantics for the semantic web iconИнтеллектуальное реферирование: онтологический подход и его реализация в решениях Ontos
Обсуждению вопросов создания системы реферирования под управлением онтологий, разработанной в рамках решений Ontos для Semantic Web,...
Bayesian semantics for the semantic web iconWeb dizains web design
Основные компоненты web-страницы и способы их визуального представления на страницах сайта
Bayesian semantics for the semantic web iconDependency Tree Semantics and Underspecification

Bayesian semantics for the semantic web iconSemantics of contour lines' spatial relation

Разместите кнопку на своём сайте:

База данных защищена авторским правом © 2014
обратиться к администрации
Главная страница