The world is changing. The World Wide Web is changing. It started out as a set of purely notational conventions for interconnecting information over the Internet. The focus of information processing has now shifted from local disconnected disc-bound silos to Internet-wide interconnected clouds. The nature of information has also evolved. From raw uniform data, it has now taken the shape of semi-structured data and meaningcarrying so-called “Knowledge Bases.” While it was sufficient to process raw data with structure-aware querying, it has now become necessary to process knowledge with contents-aware reasoning. Computing must therefore adapt from dealing with mere explicit data to inferring implicit knowledge. How to represent such knowledge and how inference therefrom can be made effective (whether reasoning or learning) is thus a central challenge among the many now facing the world wide web. So called “ontologies” are being specified and meant to encode formally encyclopedic as well as domain-specific knowledge. One early (still on-going) such effort has been the Cyc1 system. It is a knowledge-representation system (using LISP syntax) that makes use of a set of varied reasoning methods, altogether dubbed “commonsense.” A more recent formalism issued of Description Logic (DL)-viz. the Web Ontology Language (OWL2)-has been adopted as a W3C recommendation. It encodes knowledge using a specific standardized (XML, RDF) syntax. Its constructs are given a modeltheoretic semantics which is usually realized operationally using tableau3-based reasoning.4 The point is that OWL is clearly designed for a specific logic and reasoning method. Saying that OWL is the most adequate interchange formalism for Knowledge Representation (KR) and automated reasoning (AR) is akin to saying that English is the best designed human language for facilitating information interchange among humans-notwithstanding the fact that it was simply imposed by the most recent pervasive ruling power, just as Latin was Europe's Lingua Franca for centuries. Thus, it is fair to ask one's self a simple question: “Is there, indeed, a single most adequate knowledge representation and reasoning method that can be such a norm? ” 1 http://www.cyc.com/platform/opencyc 2 http://www.w3.org/TR/owl-features/ 3 http://en.wikipedia.org/wiki/Method_of_analytic_tableaux 4 Using of tableau methods is the case of the most prominent SW reasoner [6, 5, 7]. Systems using alternative reasoning methods must first translate the DL-based syntax of OWL into their own logic or RDF query processing. This may be costly [9] and/or incomplete [8].
I personally do not think so. In this regard, I share the general philosophy of Doug Lenat5, Cyc’s designer—although not the haphazard approach he has chosen to follow.6
If one ponders what characterizes an ontology making up a knowledge base, some specific traits most commonly appear. For example, it is universally acknowledged that, rather than being a general set of arbitrary formal logical statements describing some generic properties of “the world,” a formal knowledge base is generally organized as a concept-oriented information structure. This is as important a change of perspective, just as object-oriented programming was with respect to traditional method-oriented programming. Thus, some notion of property “inheritance” among partially-ordered “concepts” (with an “is-a” relation) is a characteristic aspect of KR formalisms. In such a system, a concept has a straightforward semantics: its denotes of set of elements (its “instances”) and the “is-a” relation denotes set inclusion. Properties attached to a concept denote information pertaining to all instances of this concept. All properties verified by a concept are therefore inherited by all its subconcepts.
Sharing this simple characteristic, formal KR formalisms have emerged from symbolic mathematics that offer means to reason with conceptual information, depending on mathematical apparatus formalizing inheritance and the nature of properties attached to concepts. In Description Logic7, properties are called “roles” and denote binary relations among concepts. On the other hand, Formal Concept Analysis (FCA8) uses an algebraic approach whereby an “is-a” ordering is automatical derived from propositional properties encoding the concepts that are attached to as bit vectors. A concept is associated an attribute with a boolean marker (1 or “true”) if it possesses it, and with a (0 or “false”) otherwise. The bit vectors are simply the rows of the “property matrix” relating concepts to their attributes. This simple and powerful method, originally proposed by Rudolf Wille, has a dual interpretation when matching attributes with concepts possessing them. Thus, dually, it views attributes also as partially ordered (as the columns of the binary matrix). An elegant Galois-connection ensues that enables simple extraction of conceptual taxonomies (and their dual attribute-ordered taxonomies) from simple facts. Variations such as Relational Concept Analysis (RCA9) offer more expressive, and thus more sophisticated, knowledge while preserving the essential algebraic properties of FCA. It has also been shown how DL-based reasoning (e.g. OWL) can be enhanced with FCA.10
Yet another formalism for taxonomic attributed knowledge, which I will present in more detail in this presentation, is the Order-Sorted Feature (OSF ) constraint formalism. This approach proposes to see everything as an order-sorted labelled graph. 5 http://en.wikipedia.org/wiki/Douglas_Lenat 6 However, I may stand corrected in the future since knowledge is somehow fundamentally haphazard. My own view is that, even for dealing with a heterogenous world, I would rather favor mathematically formal representation and reasoning methods dealing with uncertainty and approximate reasoning, whether probabilistic, fuzzy, or dealing with inconsistency (e.g. rough sets, paraconsistency). 7 http://en.wikipedia.org/wiki/Description_logic 8 http://en.wikipedia.org/wiki/Formal_concept_analysis 9 http://www.hse.ru/data/2013/07/04/1286082694/ijcai_130803.pdf 10 http://ijcai-11.iiia.csic.es/files/proceedings/
T13-ijcai11Tutorial.pdf Sorts are set-denoting and partially ordered with an inclusion-denoting “is-a” relation, and so form a conceptual taxonomy. Attributes, called “features,” are function-denoting symbols labelling directed edges between sort-labelled nodes. Such OSF graphs are a straightforward generalization of algebraic First-Order Terms (FOTs) as used in Logic Programming (LP) and Functional Programming (FP). Like FOTs, they form a lattice structure with OSF graph matching as the partial ordering, OSF graph unification as infimum (denoting set intersection), and OSF graph generalization as supremum.11 Both operations are very efficient. These lattice-theoretic properties are preserved when one endows a concept in a taxonomy with additional order-sorted relational and functional constraints (using logical conjunction for unification and disjunction for generalization for the attached constraints). These constraints are inherited down the conceptual taxonomy in such a way as to be incrementally enforceable as a concept becomes gradually refined.
The OSF system has been the basis of Constraint Logic Programming for KR
and ontological reasoning (viz. LIF E ) [
In this presentation, I will give a rapid overview of the essential OSF formalism for knowledge representation along its reasoning method which is best formalized as order-sorted constraint-driven inference. I will also illustrate its operational efficiency and scalability in comparison with those of prominent DL-based reasoners used for the Semantic Web.
The contribution of this talk to answering the question in its title is that the Semantic Web effort should not impose a priori putting all our eggs in one single (untested) basket. Rather, along with DL, other viable alternatives such as the FCA and OSF formalisms, and surely others, should be combined for realizing a truly semantic web. 11 This supremum operation, however, does not (always) denote set union—as for FOT subsumption, it is is not modular (and hence neither is it distributive). 12 http://en.wikipedia.org/wiki/Head-driven_phrase_structure_ grammar 13 http://www.cs.haifa.ac.il/˜shuly/malta-slides.pdf 14 http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.2021