Toward Automated Provability-Bad Semantic Interoperability Between Ontologies for the Intelligence Community
(extended abstract)
Andrew Shilliday,Joshua Taylor,Selmer Bringsjord,Konstantine Arkoudas {shilla,tayloj,lmer}@rpi.edu,konstantine@alum.mit.edu
Department of Cognitive Science
Department of Computer Science
Renslaer AI&Reasoning(RAIR)Lab:
Troy NY12180USA
July15,2007
1Introduction
The need for interoperability is dire:Knowledge repre-ntation systems employ ontologies that u disparate formalisms to describe related domains;to be truly u-ful to the intelligence community,they must meaningfully share information.Ongoing rearch[3,4,7,15]strives toward the holy grail of complete interoperability,but has been hindered by techniques that are specialized for par-ticular ontologies,and that lack the expressivity needed to describe complex ontological relationships.In the quel, we describe provability-bad mantic interoperability (PBSI)[16],a means to surmount the hindrances;trans-lation graphs,one of our key formalism for describing the complex relationships among arbitrary ontologies;and ways in which the techniques might be automated.
2PBSI and PBSI+
We clarify our us of syntactic and mantic.The syntax of a knowledgeba regiments the structure of expressions in ,that(mother-of Amy)is a well-formed KIF term owes to KIF’s syntax);mantics attribute meaning to otherwi abstract constructs((mother-of Amy)des-ignates Amy’s mother according to the mantics of an ontology).A syntactic translation occurs when knowl-edge from one ontology is moved into another using the same mantics.In other words,when ontologies de-scribe the same kind of things,and differ only in the way object-level information is stru
ctured,interoperabil-
ity is achieved by mere syntactic translation.When on-tologies differ not only in syntax,but also in mantics (yet relate meaningfully),a stronger form of translation is needed:mantic translation enables the transfer of in-formation across such ontologies.Systems capable of -mantic ,[4,6])provide some language in which to formalize the mantic connections between on-tologies.Unfortunately,the relationships associating on-tologies may be so complex that translation of knowledge from one ontology into another is not feasible.Moreover, when interoperability is achieved between complex on-tologies,justification is needed to support trust that the meaning of the data has been prerved.
PBSI provides a language for formalizing the rela-tionships between ontologies via bridging axioms,and our extension,PBSI+,associates each information ex-change with a proof certifying the conrvation of man-tic meaning.The basic construct of PBSI+is the signa-ture,a collection of statements in the meta-theory which, coupled with a t of axioms,captures a given ontology.
A signatureΣconsists of a tσof sorts,and a tφof functors.A sort s∈σis a domain—a collection who elements are considered the same kind of thing,,the months in the year,boolean values,
natural numbers,US citizens).A functor f∈φmaps between objects of the sorts inσ.In the ca that f maps onto the boolean val-1Our current formalization draws on many-sorted logic,and so do-mains are disjoint.While this is a limitation on the expressitivity of the language(many ontologies require a subsort hierarchy),it is not a technical restriction.Specifically,we are investigating the u of other ontology reprentation languages[11,8].
1
Figure1:A sample translation graph enabling interoper-ability between four related ontologies.
余光中经典
ues,f is a relation;if it also takes no arguments,it is a proposition.Having defined signatures,the specifications of ontologies,we prent translation graphs,a framework for bridging signatures(and so,ontologies)while prerv-ing mantics.
3Translation Graphs
A translation graph,like the one infigure1,is a directed graph G=(V,E)where the vertices v∈V are each unique signatures,and each edge e=(u,v)∈E describes the ap-plication of a primitive operation to u yielding v,viz., adding or removing either a sort or functor.The addition of a new functor also has associated information poten-tially relating the new functor to existing functors of the modified signature.
As a toy example,let signatureΣ1consist of the do-mainsσ1={People,Firearms}and just one functorφ1= {OwnerOf:Firearms→People},which is understood to map afirearm to its owner.Furthermore,signature Σ2consists of the domainσ2={People}and the func-torφ2={IsArmed:People→Boolean}so that IsArmed holds for tho people who own guns(in this example, all signatures implicitly have the boolean domain).A translation graph enabling interoperability between the signatures might apply the following primitive operations bridgingΣ1toΣ2:
1.AddFunctor(IsArmed)with the bridging axiom
∀p[∃g OwnerOf(g)=p]→IsArmed(p) so that the the relation IsArmed holds for any person, p where there is afirearm that p owns.
2.RemoveFunctor(OwnerOf)
ps羽化怎么用3.RemoveSort(Firearms)
PBSI between the two described ontologies is made possible:Suppo that thefirst ontology has among the declarative information in its knowledgeba that Mo-hammed Al Harbi is the owner of an AKS-74U assault riffle,and that the knowledgeba of the cond ontol-ogy contains no information about Mohammed Al Harbi except that he is a person.A query of whether or not Mohammed is armed,issued in the cond ontology and making u ofσ1’s knowledgeba along with bridging axioms generated by traversing the path fromσ1toσ2, would yield the correct answer and the associated,certi-fying proof.
4Automation
In this ction,we discuss ways to automate the process of creating and applying translations graphs.
The proce-dure to extract appropriate bridging axioms from a trans-lation graph has been accomplished,and systems who ontologies are prent as nodes in a translation graph can interoperate with other nodes in the graph.PBSI does not always yield translation;in some cas,bridging axioms can be converted to techniques for syntactic translation, but typically interoperability is achieved by a system is-suing a query expresd in its own syntax and mantics and the arch for an answer incorporates knowledge from related ontologies.
A detailed example of the above is prented in the in-teroperability experiment[2]between our own advanced reasoning system,Slate,and Oculus’geospatial and tem-poral visualization system,GeoTime.In the experiment, Slate and GeoTime collaborate to solve a portion of a ca study ud at the Joint Military Intelligence College. Additionally,the IKRIS Workshop[12]culminated in a demonstration of interoperability between three systems, Slate[1],Cycorp’s N¨o scape[14],and IBM and Stanford’s KANI[5].2
This automation gets us half way there,but the holy grail of PBSI is to automate not only the intoperation be-tween systems,but the generation of translation graphs as well.Translation graphs are of cour implemented in code,so the challenge of fully automating PBSI+be-comes the challenge of so-called automatic programming [13].Becau of the capability of the system we have
de-signed for intelligence analysts(Slate),we are optimistic 2Demonstrations of the experiments and other Slate-related content is made available online sci.rpi.edu/slate/Demos/
2
about being able to devi programs that generate the pro-grams that implement translation graphs.Slate integrates deductive,inductive,and abductive reasoning.To the best of our knowledge,there has not been a single effort in automatic programming that synthesizes the three el-ements.The tradition of deductive program automation [10]is bad exclusively on deduction;the tradition of machine ,genetic programming[9])is bad exclusively on induction;while abduction has not even been explored in thisfield.And yet,typically,when hu-mans approach a programming problem they employ all three of the.They u induction(in tandem with testing and checking)to formulate conjectures about the problem and their tentative solutions;they u deduction in order to reason about the conquences of their design decisions and about the correctness of their solutions;and they u abduction to explain the behavior of their algorithms.We look forward to reporting on our progress toward full au-tomaticity at OIC2007.
5A Robust Example
In the prentation corresponding to this extended ab-stract at OIC2007itlf,we will also describe a PBSI+-enabled interoperabilty example too robust to prent within prent space constraints.The example will be bad on ongoing DTO-sponsored R&D,in which the aforementioned Oculus and Slate systems interoperate to enable analysts,working on a challenging ca study,to issue hypothes and recommendations that would not otherwi be attainable.
References
[1]B RINGSJORD,S.,S HILLIDAY,A.,AND T AYLOR,
J.sci.rpi.edu/slate/,2007.
[2]C HAPPELL, A.,B RINGSJORD,S.,S HILLIDAY,
A.,T AYLOR,J.,AND W RIGHT,W.Integra-
形容绿的四字词语
南朝梁tion Experiment with GeoTime,Slate,and VIKRS.
ARIV A Principal Investigator Meeting Handout, March2007.
uno怎么玩[3]C HOI,N.,S ONG,I.-Y.,AND H AN,H.A survey
on ontology mapping.SIGMOD Rec.35,3(2006), 34–41.
[4]D OU, D.,M C D ERMOTT, D.,AND Q I,P.On-
tology Translation by Ontology Merging and Au-tomated Reasoning.Whitestein Series in Soft-ware Agent Technologies and Autonomic Comput-ing.Birkh¨a ur Bal,2005,pp.73–94.
[5]F IKES,R.E.,F ERRUCCI, D.,AND T HURMAN,
D.A.Knowledge Associates for Novel Intelligence.
In Proceedings of the2005International Conference
on Intelligence Analysis(IA2005)(McLean,V A,
USA,May2005).
[6]G OGUEN,J.A.Data,Schema,Ontology and Logic
Integration.Logic Journal IGPL13,6(2005),685–
715.
[7]H ENDLER,J.Agents and the Semantic Web.IEEE
Intelligent Systems(March/April2001),30–37.
[8]K LYNE,G.,AND C ARROLL,J.J.Resource
description framework(rdf):Concepts and ab-
stract syntax,available at www.w3/tr/rdf-
concepts/.p.,W3C,February2004.
[9]K OZA,J.Genetic Programming:On the Program-
ming of Computers by Means of Natural Selection.
MIT Press,Cambridge,MA,1992.
[10]M ANNA,Z.,AND W ALDINGER,R.Fundamentals毕业证明书怎么开
of deductive program synthesis.In Logic,Algebra,
and Computation,F.L.Bauer,Ed.Springer,Berlin,
Heidelberg,1991,pp.41–107.
[11]M C G UINNESS,D.L.,AND VAN H ARMELEN,F.
OWL Web Ontology Language overview.Tech.
rep.,W3C,Available at www.w3/TR/owl-
features/,2004.
[12]MITRE.IKRIS,workshop site:
nrrc.mitre/NRRC/ikris.htm,2007. [13]R ICH,C.,AND W ATERS,R.C.Automatic pro-
gramming:Myths and prospects.Computer21,8
(Aug.1988),40–51.
[14]S IEGEL,N.,S HEPARD, B.,C ABRAL,J.,AND
女儿结婚祝福语W ITBROCK,M.Hypothesis Generation and Evi-
dence Asmbly for Intelligence Analysis:Cycorp’s
No¨o scape Application.In Proceedings of the2005
International Conference on Intelligence Analysis
ps怎么去除水印(IA2005)(McLean,V A,USA,May2005). [15]S MITH, B.The basic tools of formal ontology.
In Formal Ontology in Information Systems(1998),
N.Guarino,Ed.,IOS Press,pp.19–28.
[16]T AYLOR,J.,S HILLIDAY,A.,AND B RINGSJORD,
S.Provability-bad mantic interoperability via
translation graphs.In International Workshop on
Ontologies and Information Systems for the Seman-
tic Web(ONISW2007)(2007).
3
