Knowledge Representation in Artificial Intelligence

Knowledge representation is a field of artificial intelligence focused on representing information about the world in a form that a computer system can understand and use to communicate with other components within the system in order to perform some tasks. The concept of knowledge is a collection of facts, principles, and related concepts. Knowledge representation is the key to any communication language and a fundamental issue in Multi-Agent System (MAS). The way knowledge is represented and expressed has to be meaningful so that communicating agents can grasp the concept of the knowledge transmitted amongst them. In order for agents to understand information exchanged between them, they must share knowledge of concepts in specific representation language or ontology [1]. Ontology is a specification of concepts, meaning, and relationships applicable in a particular domain of knowledge. In other words, ontology is a shared vocabulary of words and their meaning that allows agents to understand each other when talking in a specific domain. 

In computer symbols (numbers and characters) are used to store and manipulate knowledge. “There are different approaches for storing and representing knowledge. Some popular approaches for storing knowledge in computers include procedural, relational, and hierarchical representations” [2].

The Procedural Representation method encodes knowledge into program code and sequential instructions. Encoding knowledge into the algorithm that is used to process it makes it difficult to modify knowledge. Declarative knowledge concepts are used to represent facts, rules, and relationships separate from the algorithm used to process them. In the Relational Representation method, data is stored in a set of fields and columns based on the attributes of items. The Structured Query Language (SQL) is an example of rational representation methods. These methods are flexible but not as good as Hierarchical Representation methods when stating the relationships and shared attributes of different objects or concepts. These methods Network Hierarchical Representation methods are very strong in representing knowledge and ‘isa’ relationships between related groups. An ‘isa’ relationship is when a specific object is linked to a more abstract term. For instance the object ‘apple’ can be linked to the category of ‘fruits’ using the ‘isa’ relationship. 

Some popular examples of languages used for defining ontology and the body of knowledge in Information Technology (IT) include Knowledge Interchange Format (KIF) and Extensible Mark-up Language (XML).

Knowledge Interchange Format 

Knowledge Interchange Format (KIF) is a language developed by the Defence Advanced Research Project Agency (DARPA) knowledge-sharing Effort group for interchanging knowledge between agents [3]. The aim was to improve interoperability in the computing environment. KIF is a language for representing knowledge using first-order logic and a basic vocabulary of objects within a particular domain. It allows agents to represent the properties and relationships of things. It was initially intended to be used for expressing the content of KQML messages. 

KIF can be the common intermediate language between two agents with different representation languages [4]. With the use of the KIF translator, an agent’s messages can be translated between KIF and any other agent’s language instead of translating directly from one agent’s language to the other. This reduces the complexity of the system because if agents can read and write in KIF format then they can share knowledge, even though they have different internal representations of knowledge. Consequently each agent needs to know how to translate only between its language and KIF and not all the other languages that exist in the system. 

The language syntax of KIF consists of variables, constants, and operators. KIF operators are used for a variety of tasks that include defining variables and constants and representing facts, rules, and terms. Variables can be of individual and sequence types. Constants can be of all types of numbers, characters, and strings. They can also indicate objects, relations, and functions over objects. There are also logical constants that express real-world facts in terms of logical Boolean expressions. For example, a logical KIF statement is shown below. 

( < ( * (height rect) (width rect) )
     ( * (2) (+ (height rect) (width rect)) ) )

This expression states that the perimeter of rectangle rect is greater than its area. The order in which parentheses are put is important to the result of the operation and defines which operation should take place first. 

KIF is not a programming language but it can also describe programming instructions for an agent to follow [5]. For example, below is an instruction in KIF language that can be sent to an agent. 

(GetValue ?userValue)(checkValue ?userValue "=" VALUE)

This instruction tells the agent to get the user’s value and store it in the userValue variable, then check whether the user’s value is the same as the VALUE variable. The GetValue method and the VALUE variable are predefined for the agent. 

KIF was primarily intended to be a language for processing computers. A number of software packages were developed to allow users to develop KIF ontology. An example of these is Ontolinqua [6]. A disadvantage of KIF language is that as an expression gets longer, the order of statements becomes more complex and it then becomes increasingly difficult for people to follow. 

Extensible Markup Language 

The Extensible Mark-up Language (XML) is a way of representing data in a standardised text-based format and sharing it across different platforms [7]. It is a markup language similar to HyperText Mark-up Language (HTML) but with distinctive advantages. HTML was invented by Tim Berners-Lee and became the language that defined the structure of web pages and presented a wide range of content. Tim Berners-Lee wrote the first World Wide Web server and client in 1990. HTML represents data in a manner that is accessible to humans for viewing via web browsers but is not meant for computers to understand what the data means. 

XML and its close relatives make it possible for computers to understand and process data in meaningful ways. The concept of Semantic Web has emerged where computers have become capable of analysing all data on the web [8]. 

XML makes data transportable to other systems. It is designed to be as simple as possible so that it is easy for humans to understand. Structured data can be extended with XML tags. In other words, XML is a language for defining languages and ontology [6]. Each command consists of an opening tag in angle brackets and a closing tag.

A sample XML file representing a personal profile:

<?xml version="1.0" encoding="ISO-8859-1" ?> 
<!DOCTYPE Profile SYSTEM "profile.dtd">  
<Profile>
  <Name>Mr Smith</Name> 
  <Address>
    <Street>9999 Main Street</Street>
    <State>South Australia</State>
  </Address>
  <Job>Engineer</Job> 
  <Phone>99999999</Phone> 
</Profile>

An important feature of XML is the ability to place verifiable preconditions on data in a simple and declarative way [9]. The process of checking an XML document against said conditions is referred to as validation. Generally, the conditions are expressed in schema languages. The documents that list these conditions are called schemas. Several schema languages have been developed. 

Document Type Definition (DTD) is a standard schema language that has been built into most XML parsers. Apart from validating the data, it can define entities and notations. In other words, DTDs can be used to define ontology in XML. A DTD document specifies the structure of elements, the order in which they appear, and their attributes. It can also provide default values for attributes. Each element must be declared in the DTD document in order to be validated. 

The DTD document needs to be referenced in the XML file. 

The above XML file representing a personal profile uses the DTD document of ‘Profile.dtd’, which is shown below. This DTD document declares the elements of the XML file. 

It includes the content model of the Profile element. ELEMENT defines the name and content of XML elements. It also indicates whether the element is composed of sub-elements or not. #PCDATA defines the value of a parameter. It indicates that the parameter is text and has no child elements. A collection of elements can be grouped together with parentheses to indicate that they should be treated as one unit. 

The DTD (Profile.dtd):

<!ELEMENT Profile (Name, Address, Phone)>
<!ELEMENT Name (#PCDATA)>
<!ELEMENT Address (Street, State)>
<!ELEMENT Street (#PCDATA)>
<!ELEMENT State  (#PCDATA)>
<!ELEMENT Phone  (#PCDATA)>

The W3C XML Schema (WXS) or XML Schema Document (XSD) is an expressive schema language in widespread use which has some advantages over DTD. WXS schemas are written in XML syntax using tags, elements, and attributes. Unlike DTD, WXS schemas can assign data types, such as double and Date, to elements. With DTD, data can be validated based on the element structure but with WXS the content of elements can also be validated. 

An example of WXS schemas (‘Profile.xsd’):

<?xml version="1.0" encoding="utf-8"?>
<xs:schema elementFormDefault="qualified" 
  xmlns:xs="http://www.w3.org/2001/XMLSchema">
  <xs:element name="Profile">
    <xs:complexType>
      <xs:sequence>
        <xs:element name="Name" type="xs:string" />        
        <xs:element name="Address">
          <xs:complexType>
            <xs:sequence>
              <xs:element name="Street" type="xs:string" />        			
              <xs:element name="State" type="xs:string" />
            </xs:sequence>
          </xs:complexType>
        </xs:element>        
        <xs:element name="Phone" type="xs:int" />        
      </xs:sequence>
    </xs:complexType>
  </xs:element>
</xs:schema>

When using schemas for declaring XML tags, the schemas needs to be referenced in the XML file content. The above WXS schemas is used for defining XML tags and declaration and verification of the XML content shown below. It shows a version of the XML content similar to the XML file we saw earlier representing a personal profile but it uses schemas instead of DTD. A reference to the schemas (‘Profile.xsd’) is included to validate the XML content.

<?xml version="1.0" encoding="ISO-8859-1" ?> 
<Profile xmlns="http://www.w3schools.com"
  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
  xsi:schemaLocation="Profile.xsd">
  <Name>Mr Smith</Name> 
  <Address>
    <Street>9999 Main Street</Street>
    <State>South Australia</State>
  </Address>
  <Phone>99999999</Phone> 
</Profile>

The schema allows for converting elements in XML document to objects within the programming environment [10]. This is referred to as XML Data Binding. XML is a popular language of choice for describing the content and is a common representation format for messages.

In the next article, we look into Agent Communication Languages and some of the protocols used to share knowledge between agents.

References and Credits

• [1] Y. Labrou, T. Finin, and Y. Peng. Agent communication languages: The current landscape. IEEE Intelligent Systems and Their Applications, IEEE Computer Society, US, 14(2):45–52, 1999.
• [2] J. P. Bigus and J. Bigus. Constructing Intelligent Agents Using Java. Wiley, New York, 2nd edition, 2001.
• [3] M. R. Genesereth and R. E. Fikes. Knowledge interchange format, version 3.0 reference manual. Technical report, Computer Science Department, Stanford University, 1992.
• [4] J. M. Bradshaw. Software Agents. AAAI Press / The MIT Press, 1997. [20]M. Bratman. Intention, Plans, and Practical Reason. Harvard University Press, 1987.
• [5] T. Finin, Y. Labrou, and J. Mayfield. KQML as an agent communication language. In Software Agents, pages 456 – 480. AAAI Press / The MIT Press, 1997.
• [6] 239
• [7] B. Benz, J. Durant, and J. Durant. XML Programming Bible. Wiley Publishing, Inc., 909 Third Avenue. New York, 2003.
• [8] T. Berners-Lee. Weaving the Web. Orion Business, London, 1999.
• [9] E. R. Harold. Processing XML with Java: A Guide to SAX, DOM, JDOM, JAXP, and TrAX. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA, 2002.
• [10] M. D. Hansen. SOA Using Java EE 5 Web Services. Pearson Education, Inc., RR Donnelley in Crawfordsville, Indiana, 2007.
• Thumbnail Photo by Markus Spiske on Unsplash