The Information Flow Framework (IFF)

Motivation and Overview

“She acknowledged it to be very fitting, that every little social commonwealth should dictate its own matters of discourse; and hoped, ere long, to become a not unworthy member of the one she was now transplanted into. With the prospect of spending at least two months at –, it was highly incumbent on her to clothe her imagination, her memory, and all her ideas in as much of – as possible.”

Persuasion, Chapter 6, (1818). Jane Austen

According to the Scope & Purpose of the IEEE SUO project, “This standard will specify an upper ontology that will enable computers to utilize it for applications such as data interoperability, information search and retrieval, automated inferencing, and natural language processing.”  Further, one of the three purposes of the project is “INTER-OPERABILITY: The standard will provide a basis for achieving Inter-Operability among various software and database applications.” The work presented here proposes a framework, the Information Flow Framework (IFF) to accomplish this goal of interoperability, as well as the goals related to automated reasoning and application areas. The IFF is designed to allow not only the interoperability among software and database applications, but also the semantic interoperability among various object-level ontologies themselves (Figure 1). As such, this work can be seen as complementary to the work being done in the IEEE SUO Working group on the SUMO. At this stage in the development of both the IFF and the SUMO, the major difference between the two works is that the SUMO effort is geared toward providing a single upper ontology, whereas the IFF is designed to support the semantic interoperability among various object-level ontologies. The IFF supports this interoperability by its architecture (Figure 1 and Section 2) and its use of a particular branch of mathematics known as category theory. A major reason that the IFF uses the architecture and formalisms that it does is to support modular ontology development.

Modularity (constructing with standardized units or dimensions for flexibility and variety in use – Merriam-Webster) is essential (John Sowa) to good design decisions in every area of engineering, and most of all knowledge engineering and software engineering. In particular, modularity is important in the development, testing, maintenance, and use of ontologies. Development time will be shortened because separate groups would work on each module with little need for communication. When an ontology is maintained in modular fashion, errors and deficiencies can be traced to specific modules, thus limiting the scope of detailed error searching. With a modular design, it will be possible to make drastic changes to one module without the need to change other modules. Also with a modular design, by considering one module at a time the ontology as a whole will more easily be understood. With this understanding, the whole system can be better utilized. A monolithic ontology, on the other hand, would be very inefficient. In use, some parts would be very stable, well justified and shared across very broad communities, while other parts would not be adopted widely and would be quickly replaced (Austin Tate). A modular design will facilitate these consensual and evolutionary processes of renewal. The categorical approach of the Information Flow Framework provides a framework for modular design via a structural metatheory of ontologies. Such a metatheory is a method for representing the structural relationships between ontologies. As will be quite evident in the Model Theory Ontology, this structural metatheory is compatible with the representation of object-level ontologies in any suitable and appropriate ontology language.

From the point of view (Robert Kent) that “every little social commonwealth should dictate its own matters of discourse,” would it not seem that the SUO should be structured in a modular fashion, as a loose confederation of participating ontologies, or perhaps better a league or commonwealth of ontologies?

We now turn to the modular architecture of the Information Flow Framework.

Architecture

The Information Flow Framework seeks to apply Information Flow to distributed logic, ontologies, and knowledge representation. The IFF takes a building-blocks approach towards the development of object-level ontological structure, This is a rather elaborate categorical approach that uses insights from the theory of distributed logic known as Information Flow (Barwise and Seligman 1997), and also uses ideas from the theory of Formal Concept Analysis initiated by Rudolf Wille (Ganter & Wille 1999). The IFF provides mechanisms for a principled foundation for a metalevel ontological framework – a framework for sharing ontologies, manipulating ontologies as objects, relating ontologies through morphisms, partitioning ontologies, composing ontologies via colimits, discussing ontological structure, noting dependencies between ontologies, declaring the use of other ontologies, etc. The IFF is primarily based upon the theory of Information Flow, which is centered on the notion of a classification. Information Flow is itself based upon the theory of the Chu construction of *-autonomous categories (Barr 1996), thus giving it a connection to concurrency and Linear Logic. The IFF is secondarily based upon the theory of Formal Concept Analysis, which is centered on the notion of a concept lattice. The IFF represents metalogic, and as such operates at the structural level of ontologies. In the IFF, there is a precise boundary between the metalevel and the object level. The architectural structure of the Information Flow Framework is illustrated in Figure 1.

Although the Information Flow Framework is rather large, it is highly structured, representing the structural aspect of the SUO, its metalevel, in terms of meta-ontologies. The Information Flow Framework is partitioned into three metalevels: top, upper and lower. These metalevels correspond to the set-theoretic distinction in foundations between (1) the generic, (2) the large and (3) the small (Mac Lane, 1971/1998).

The Information Flow Framework consists of an adequate amount of set theory which, on the one hand, is sufficiently flexible for the categorical inquiry involved in the Information Flow Framework (IFF) but, on the other hand, is sufficiently restrictive that IFF be consistent (does not produce contradictions). The terminology of the Information Flow Framework is mathematical. As a result, mathematical aesthetics plays a large role in development of the Information Flow Framework, both as a stimulus for change and as a guiding criterion in how to make those changes. Mathematical aesthetics includes such things as simplicity, elegance and power of expression, etc.

From the set-theoretic perspective, the metalevel hierarchy of the Information Flow Framework (Figure 2) corresponds to the hierarchy of (1) collections, (2) classes, and (3) sets. Table 1 locates particular kinds of collections and functions in the three-tiered framework of the IFF. In the IFF, all relations are strictly binary and all functions are strictly unary. Functions that are conceptually binary need to use pair notation for arguments.

Note however, that the Information Flow Framework is being developed from the perspective of category theory. From this perspective, the three IFF metalevels are distinguished by use. Each metalevel provides a language for the representation of the level below it – this is its raison d’etre. The top metalevel provides a language for representing the upper metalevel. The upper metalevel provides a language for representing and reasoning about the lower metalevel. The lower metalevel provides a language for representing and reasoning about the object level. Now, although one could apply the upper metalevel axiomatizations to object level information, a goal of the IFF is to apply these only to upper and lower metalevel information. If a similar axiomatization is needed for the object level, then such an axiomatization can be put in place at the metalevel.

• The top metalevel of the Information Flow Framework is used to represent and axiomatize the upper metalevel. The top metalevel does this by providing an interface between the KIF logical language and the upper metalevel of the Information Flow Framework. The ability to express all of the mechanisms in the upper metalevel needs a limited set of basic notions from mathematics: general terminology for collections, relations, functions, limits, colimits, and specific cases of these – restriction, abridgment, etc.
  

• This ability is axiomatized in the Top Core (Basic KIF) Ontology, which contains rudimentary (fundamental) namespaces for collections, functions, relations, limits and colimits. The Top Core Ontology provides an adequate foundation for representing ontologies in general and for defining the other metalevel ontologies (Figure 1) in particular. All upper metalevel ontologies import and use, either directly or indirectly, the Top Core Ontology. The Top Core Ontology operates at the set-theoretic level of generic collections, whereas Chris Menzel’s Basic Ontology operates at the level of small sets (much of this will be subsumed by the Model Theory Ontology).
  

• The upper metalevel of the Information Flow Framework is used to represent and axiomatize the lower metalevel. The upper metalevel does this by representing category theory, information flow and formal concept analysis. The upper metalevel is partitioned into three sub-ontologies: the Upper Core Ontology, the Category Theory Ontology, and the Upper Classification Ontology. The upper metalevel is organized in order to be able to realize the categorical principle (see below). In particular, the mechanism for expressing composition and limits are axiomatized in the Upper Core ontology, the mechanisms for expressing categories, functors, natural transformations, adjunctions are axiomatized in the Category Theory ontology, and the mechanisms for combining ontologies in a lattice of theories is axiomatized in the Upper Classification ontology.
  

  • The Upper Core Ontology provides an anchor for the other two ontologies at this level. It has a distinguished namespace for set-theoretic classes and their functions. It also contains basic terminology and axiomatics for large relations and endorelations.
    

  • The Category Theory Ontology represents in various namespaces a baseline for the standard ideas of category theory. Much of the content comes from well-known category-theoretic intuitions and some of the semi-standard notation used in papers and textbooks. The Category Theory Ontology provides a framework for reasoning about metalogic, as represented in the lower metalevel ontologies. Examples of provable statements are: “the Classification namespace represents a category,” or “the IF classification functor is left adjoint to the IF theory functor” (Kent 2000). The Category Theory Ontology encodes a KIF formalism for category theory in one of its normal presentations. Other presentations, such as home-set or arrows-only, may also have merit. The Category Theory Ontology is based upon the namespace for large graphs and graph morphisms that includes horizontal multiplication of graphs and a theory of coherence – a category is a monoid in the monoidal category of large graphs.
    

  • The Upper Classification Ontology represents the theory of distributed conceptual structures. This theory is concerned with the distribution and conception of knowledge. It rests upon two related theories, Information Flow and Formal Concept Analysis, which it seeks to unify. The Upper Classification Ontology connects these two studies by representing the basic theorem of Formal Concept Analysis as a categorical equivalence between classifications and concept lattices at the level of functions, and the categorical equivalence between bonds and complete adjoints at the level of relations. With this, the Upper Classification Ontology accomplishes a rapprochement between Information Flow and Formal Concept Analysis.
    

• The lower metalevel of the Information Flow Framework is used to represent and axiomatize the object metalevel. The lower metalevel is the location for various modules that help represent the structural aspect of the SUO using a categorical expression. That is to say, the lower metalevel should follow as closely as possible the categorical principle: it should be expressed at the level of classes and their functions, but using no quantification, no logical connectives, and only the specific terminology organized using composition, limits, and other categorical notions. This should make inferencing highly efficient. The lower metalevel is used to the build the objects and morphisms of ordinary categories such as Set, Classification, Hypergraph, … . It thus represents these categories along with their associated functors, natural transformations, and adjunctions.
  

• The lower metalevel contains at present one module called the Model Theory Ontology consisting of about ten namespaces. This expression of model theory, somewhat novel since it is based upon the theory of Information Flow, is used to represent and axiomatize the object level. Use of this ontology could be direct, but more likely will involve a parse/translation from some “external” (to the IFF) ontological description into the “internal” IFF semantic representation (see the expansion of one of Adam Pease’s examples.
  

• Other modules (namespaces or subontologies), in addition to the Model Theory Ontology, are perhaps possible at the lower metalevel. These might include modules for categorical model theory, modules for modal, tense and linear logic, modules for rough and fuzzy sets, modules for semiotics, etc.
  

• The object level is where the content ontologies reside. These could be very generic, such as a 4D ontology, or specific, such as ontologies for government or higher education. It should be noted that the object level satisfies a representation property similar to the categorical property satisfied by the lower metalevel – the ontological language used is not KIF; instead it is the terminology defined and axiomatized in the lower structural level (terms such as ‘subtype’, ‘instance’, ‘expression’, ‘model’, ‘ontology’, ‘relation’, ‘entity’, ‘role’, etc.).
  

The following principle is critically important in meta-ontology design.

Categorical Design Principle:

• All axioms are expressed in terms of either terms from another lower metalevel module or category-theoretic notions (upper metalevel notions), such as classes, binary relations, order, the composition and identity class functions, the pullback of diagrams of class functions, etc.
• No axioms use explicit logical notation: No variables, quantification (‘forall’, ‘exists’) or logical connectives (‘and’, ‘or’, ‘not’, ‘=>’,‘<=>’) are used.
• No axioms use terms from the Top Core ontology, other than pair bracketing ‘[-]’ or pair projection ‘(- 1)’, ‘(- 2)’.

Here is some representative code in the function sub-namespace of the IFF Ontology of Small Sets (a part of the Model Theory Ontology, which is under development). Notice how this code adheres to the Categorical Property. The lower metalevel terms being introduced in this fragment are: ‘function’, ‘source’, ‘target’ and ‘fn2rel’. The axiomatization uses both previously introduced lower-metalevel terms, and upper metalevel terms imported from the Upper Core Ontology.

• The term ‘set’ comes from the set namespace.
• The terms ‘rel$relation’, ‘rel$set1’ and ‘rel$set2’ come from the rel namespace.
• The terms ‘class’ and ‘subclass’ come from the SET namespace.
• The terms ‘function’, ‘source’, ‘target’, ‘restriction’, ‘composition’, ‘fn2rel’ and ‘injection’ come from the SET.FTN namespace.
• The term ‘tripling’ comes from the SET.LIM.PRD namespace.

It uses no top metalevel terms, and it uses no logical variables, quantifiers or logical connectives.

(SET$class function) (SET$subclass function SET.FTN$function) (SET.FTN$function source) (= (SET.FTN$source source) function) (= (SET.FTN$target source) set$set) (SET.FTN$restriction source SET.FTN$source) (SET.FTN$function target) (= (SET.FTN$source target) function) (= (SET.FTN$target target) set$set) (SET.FTN$restriction target SET.FTN$target) (SET.FTN$function fn2rel) (= (SET.FTN$source fn2rel) function) (= (SET.FTN$target fn2rel) rel$relation) (= (SET.FTN$composition [fn2rel rel$set1]) source) (= (SET.FTN$composition [fn2rel rel$set2]) target) (SET.FTN$restriction fn2rel SET.FTN$fn2rel) (SET.FTN$injection (SET.LIM.PRD$tripling [source target fn2rel]))

Language Levels, Role Types and Ontological Visibility

At its core, the Information Flow Framework is coded in the KIF logical language. As an ontological machine language, the Lisp-y style of logical expression of the KIF logical language is very useful, adequately expressive and conveniently terse. However, in the proposed IFF structure for the SUO the KIF logical language will not be used as the sine qua non for ontological expression. Instead, the IFF Foundation terminology is partitioned into language levels according to the following programming language analogy.

0. The KIF logical language is like an ontological machine language.

1. The Top Core Ontology is like an ontological assembly language. It provides a basic ontological apparatus for the SUO. The purpose of this kind of terminology is to be an interface between the KIF language and other ontological terminology, in general. Because of this purpose, the Top Core Ontology might also be called a bootstrap ontology.

2. The bulk of the Information Flow Framework, as encoded in the of the upper/lower metalevel namespaces,

3. is like a high level programming language such as Lisp, Java, ML, etc. The lower metalevel provides direct representation capabilities, and the upper metalevel provides indirect structuring capabilities.
   

4. The object level of the SUO is like various software applications, such as word processors, browsers, spreadsheet software, databases, etc. The object level provides the content of the SUO coming from the various domain ontologies and philosophies with their own namespaces. The object-level ontologies can be specified using the terminology axiomatized in the lower structural level.

A central goal of the Information Flow Framework is to provide a principled mechanism for interoperability between the various modules at the object level. To support this goal, it is important that a complete distinction and an explicit boundary are kept between the object level and the metalevel. This fundamental partition must be obviously manifest in the SUO. Some ontologies at the object level may choose to represent and discuss metalevel concepts, but they would still be doing so at the object level.

• The contrast or distinction between the designers of an ontology versus the users of that ontology. Note that a designer must do some reasoning about the module being developed.
• The four levels of terminology mentioned above.

Role Types and Ontological Visibility

Truth and Modularity

The categorical approach of the Information Flow Framework provides a framework for modular design via a structural metatheory of ontologies. Such a metatheory is a method for representing the structural relationships between ontologies. As will be quite evident in the Model Theory Ontology, this structural metatheory is compatible with the representation of object-level ontologies in any suitable and appropriate ontology language. A categorical approach for modular design has previously been used in the Kestrel Institute’s SpecWare system. Specware uses the categorical notions of sheavescolimits for realizing a modular approach to software specification. Colimits, which are mechanisms for the fusion (amalgamation) of diagrams within categories, can be constructed from primitives (indexed objects and morphisms in the diagram) using sums (coproducts) and/or quotients (coequalizers, pushouts). Colimits are already represented in the Information Flow Framework: the Core Ontology has a representation for colimits in the quasicategory of set-theoretic classes and class functions; the Classification Ontology has a representation for colimits in the quasicategory of large classifications and infomorphisms, based upon the Core colimits; and the Category Theory Ontology has a representation for colimits in any large category. Extensions to the Category Theory Ontology will be able represent systems such as Specware by adding a namespace for sheaves. A study by Michael Uschold has demonstrated the power of colimits as a composition mechanism, not only for software specifications but also for ontologies. The Information Flow Framework advocates the use colimits for realizing a modular approach to ontology specification, not in terms of specifications and sheaves, but in terms of concept lattices and concept morphisms.

John Sowa has proposed the use of “an infinite lattice of all possible theories as the theoretical foundation of the SUO.” He advocates that the SUO have as its goal “a framework that can support an open-ended collection of ontological theories (potentially infinite) organized in a lattice together with systematic metalevel techniques for moving from one to another, for testing their adequacy for any given problem, and for mixing, matching, combining, and transforming them to whatever form is appropriate for whatever problem anyone is trying to solve.” The IFF approach advocates that the Information Flow Framework be used as this framework, and proposes that Concept Lattice, the category of concept lattices, be used in the SUO as a representation for John Sowa’s “lattice of all theories.” A very detailed formalism for the category of concept lattices is incorporated in the Upper Classification Ontology. The objects in this category are large concept lattices, and each concept lattice has an underlying large classification as its base and on which it is built. Large means that the collections of instances, types and formal concepts are set-theoretic classes, and not just small sets. Thus, this category can accommodate the truth concept lattice for a FOL language, whose instance collection is the class of all (model-theoretic) structures for that language, and whose formal concepts have as their intents the (closed) ontologies for that language. Amongst other things, the axiomatization of large concept lattices in the Upper Classification Ontology answers Chris Menzel’s foundational concerns about a “reasonable class theory.” The morphisms in this category are called concept morphisms. Each concept morphism has an underlying infomorphism as its base and on which it is built. In addition, each concept morphism has a pair of adjoint monotonic functions mapping between the source and target concept lattices. Being adjoint, one function preserves the joins and the other function preserves the meets of formal concepts. In terms of the truth concept lattices, they preserve the joins and meets of ontologies. The essential property of the category of concept lattices (Kent, 2001) is that it is categorically equivalent to Classification, the underlying category of classifications and infomorphisms, which is complete/cocomplete. Therefore, by a basic result from category theory, the category of concept lattices is also complete/cocomplete. This means that we can construct both limits and colimits. However, the colimits are of most interest. A build process that constructs colimits in the Concept Lattice quasicategory can be described as follows.

• [Base (start) step] Such a build process starts with the truth classifications (or their categorical equivalent, the truth concept lattices) and the interpretation infomorphisms between truth classifications associated with FOL interpretations (or their categorical equivalent, the interpretation concept morphisms). Other interesting infomorphisms between truth classifications may come from formalizing and axiomatizing the methodology that is used in various ontological merge operations.
• [Recursion (iteration, induction) step] More interesting concept lattices are iteratively built by taking colimits (sums and/or quotients) of previously built large classifications (or their categorical equivalent, large concept lattices) and previously built large infomorphisms (or their categorical equivalent, large concept morphisms). Sums may involve taking the disjoint union of theories, whereas quotients may involve identifying certain pairs of sentences of theories and restricting the models accordingly.

The notion of the truth classification of a FOL language is discussed as example 4.6 on page 71 of (Barwise and Seligman, 1997). Both this and the associated truth concept lattice, which is illustrated on slides 5 and 6 of the presentation, use the terminology of the Model Theory Ontology and occur as examples within the Upper Classification Ontology. The truth classification of a FOL language L is the meta-classification, whose instances are L-structures (models), whose types are L-sentences, and whose classification relation is satisfaction. In the IFF approach, the concept lattice of the truth meta-classification functions is an appropriate base “lattice of ontological theories.” A formal concept in this lattice has an intent that is a closed theory (set of sentences) and an extent that is the collection of all models for that theory. The theory (intent) of the join or supremum of two concepts is the intersection of the theories (conceptual intents), and the theory (intent) of the meet or infimum of two concepts is the theory of the common models or the closure of the union of the theories (conceptual intents). It is important to note that this truth framework is a fibered structure. Which means that this is not a single lattice of theories but an infinite collection of such lattices, where each truth classification truth-classification(L) and each truth concept lattice truth-concept-lattice(L) is based upon (indexed by, parameterized by) a particular FOL language L. So a particular object level ontology – be it a domain ontology, a middle level ontology, or an upper level ontology – will be an element of a lattice based on its FOL language. Internally, the various ontologies (theories) are connected by generalization-specialization and sideways jumping. Externally, the lattices in the IFF framework can be connected by concept morphisms in numerous ways: by FOL interpretations, by colimit injections (for example, the FCA notions of apposition and subposition), or by concept morphisms defined by ontology merging, etc. The colimit operation can be viewed as an internalization operator, taking an (external) indexed collection of concept lattices and concept morphisms, and producing a single (internal) fused concept lattice.

The notion of a FOL interpretation is discussed as example 4.11 on page 74 of (Barwise and Seligman [op. cit.]). FOL interpretations are axiomatized in the Model Theory Ontology. A FOL interpretation I from one FOL language L₁ to a second FOL language L₂ maps the relations of L₁ to the formulas of L₂ preserving sorts. There are two relevant functorial passages:

FOL interpretation between two FOL languages

⇒ infomorphism between the truth classifications of the languages

⇒ concept morphism between the truth concept lattices of the languages

Each FOL interpretation I defines a truth infomorphism truth-infomorphism(I) from the associated truth classification truth-classification(L₁) to the associated truth classification truth-classification(L₂) (Barwise and Seligman, 1997). This truth infomorphism defines a truth concept morphism truth-concept-morphism(I) from the associated truth concept lattice truth-concept-lattice(L₁) to the associated truth concept lattice truth-concept-lattice(L₂) (Kent 2001). This functorial passage is axiomatized in the Upper Classification Ontology.