Home Classroom Artificial Intelligence

Moving another step forward

Last time, you were able to get an idea about the philosophical and scientific aspects which are at the heart of AI based solutions. The definitions and thoughts about intelligence and how we try to mimic intelligence in the machines are some of the areas that we had a look in to. Now let’s move forward to discuss about the basics of Knowledge representation and Reasoning in AI. This is one of the most interesting and importance sub areas in AI due to the fact that knowledge and how it is represented in order to come up with reasoning methods to take better decisions is a ‘must’ factor in an intelligent agent/machine if we are trying to model them to behave in the general world. Therefore, let’s have a look at what this is all about while focusing on propositional logic for knowledge representation as a starting point to such vast area of study, throughout this article.

Knowledge Representation&Reasoning

Knowledge is a very difficult term to define just as ‘Intelligence’. It defines what and how much we know and about something. For example, if I say that I know “Sri Lanka is an island” it tells that I have certain knowledge about the country Sri Lanka and I know for sure that it is an island. There could be another instance where I say “I hope that my friend would come to have tea with me today”. In this sentence, I am not sure whether my friend would turn up to have tea or not, but I just hope he/she does. So there is a distinction between the former in which I was sure about what I was saying and in the latter, I was not so sure. Therefore, with knowledge the notion of belief is also linked. If we say “I believe that it would rain tomorrow” there is a certain amount of belief in it like there can be a 60% chance of rain whereas if I say that “I am confident that I would rain tomorrow” there is a far better conviction level associated. Thus knowledge is something which is extremely hard to describe and even to represent with such different variations, levels of certainly/conviction and ways of expression based on the different individuals in concern.

Representing knowledge in machines is a way of storing the knowledge in the machines in a manner which could be used to define a model of the world we know of. In the context of AI, a Knowledgebase is used to describe the storage of knowledge in machines which would have representations of the knowledge we have gathered, stored in a variety of ways based on the type of knowledgebase used. It could use a normal database with data, a logical model, a symbolic representation model, etc.

A part of intelligence is the ability to reason out things based on the knowledge we have gathered about a certain thing/situation based on our past experience, on what others have told, from literature and other various means of gathering knowledge. So based on those, we do reason about things which is required for us to take decisions in everyday life. So in the subject of AI, there is a specific sub area called Knowledge representation and reasoning which is used to define the knowledge inside the machines on what we know of the world in which they operate and then to use that knowledge so that the machines could do reasoning to come up with decisions in performing the actions they have to do. In this aspect, there are different ways in which we can represent the knowledge which some are listed as follows.

  1. Propositional logic
  2. Predicate Logic (First order logic)
  3. Description logics
  4. Modal Logic
  5. Intuitionist Logic
  6. Semantic nets
  7. Ontological modeling

In this article we would mainly focus on defining what ‘Propositional Logic’ is all about and how machines can represent knowledge using it.

“First things first”: Propositional Logic

‘Propositional Logic’ is also known as ‘Boolean logic’. This language was invented by a logician called George Boole in the 18th century. This language was used by AI researchers in the area of knowledge representation due to its simplicity and reasoning ability although it has its limitations when dealing with complex domains which we would look in to later in the next article. Propositional logic is the simplest logical language to learn the basics. Before learning any knowledge representation language we have to understand the foundations of such which are described as follows.

  1. Syntax – How we have to use the group of symbols and other items used in the representation language in a way that sentences constructed out of those are properly formed. In other words it can be said as this is the ‘grammar’ of the language which defines the different ways which would yield correct sentences adhering to the grammar of the language (as the grammar in English defines that a verb has to be followed by a noun as in “She eats”.)
  2. Semantics – What is the meaning of each of the sentences that we have constructed based on the syntax of that language. In logical terms this means, it defines the truth of each sentence based in each possible world being considered.

Now we would look at each of the above aspects in detail with regard to Propositional logic.

‘Syntax’ in detail

In the section of syntax, the following are the things used in Propositional logic.

-   Propositional symbols – Each symbol stands for a proposition that can be either ‘true’ or ‘false’. Since we are dealing with Boolean logic, a proposition can only take either of the two states; true or false. Propositional symbols are usually written as upper case English letters like P, Q, R, etc.

-     Logical connectives – There are number of logical connectives which we can use to combine more than one propositional symbol to define meaningful sentences.

·  Conjunction – Is simply the ‘AND’ and is usually denoted by ˄

·  NegationThis is simply the ‘Not’ connective to tell negate the truth value of a proposition which is denoted by  ̚ or ~

·  Disjunction – Means ‘OR’ and is denoted by the symbol ˅

·  Implication – Two parts of propositions are linked with this connective. The premise or antecedent is the part on the side of the tail of the connective and the conclusion or consequent of those is on the head side of the connective and is denoted by ->

oFor example:- P˅Q-> R (where antecedent is P˅Q and the conclusion is R)

 

·Biconditional – This means the statement is true ‘if and only if’ the right hand side of the connective implies that left hand side is true and vice versa. This is denoted by the symbol  .

 

Sentences made out of propositional symbols can be of two kinds.

  • Atomic sentences – Having one propositional symbol which can have either the truth value ‘True’ or ‘False’
  • Complex sentences – Having more than one propositional symbols being connected with the use of one or more logical connectives shown above
    • Examples: – ((P ˄ Q)˅ R), ((P ˄ Q)->R), (((~P) ˅ Q)-> (R ˄ S))

Some more rules in the propositional logic syntax to remember is that it is very important to use parentheses to enclose every sentence which is created with the use of logical connectives and also to remember the order of precedence of logical connectives.

  • Use of parentheses is done to ensure that the syntax does not lead to any unambiguity as well as makes reading and understanding complex sentences easy. This rule is sometimes not followed by all the books and other material written on this topic but, it is always advisable to adhere to it to avoid any confusion later.
  • The order of precedence (as the order of precedence in arithmetic operators such as (), /, X, +, -) in logical connectives from highest to lowest precedence are as follows.

Negation, Conjunction, Disjunction, Implication, Biconditional (~, ˄, ˅,->,)

 

What are the ‘Semantics’?

Once the sentences of propositional logic are formed with guidelines from the syntax section, then we have to define its meaning based on its truth value. Based on the number of propositional symbols (let’s say ‘n’) used in a sentence there can be 2n number of possible models to how we can assign truth values to those propositional symbols. For example, if we use two propositional symbols we can assign the truth values ‘true’/’false’ to the two symbols in 4 (= 22)different ways as shown table

              Table 1: Possible models of truth values for a two propositional case

Likewise, if the number of propositional symbols is 4 then there can be 24 = 16 different models of how truth values could be assigned. Then to come up with the semantics(meaning in terms of truth value for the entire sentence as a whole) of a sentence based on the truth models for the propositional symbols appearing in them, we use a method called ‘Truth tables’.

As you may have already come across Boolean logic, you may know that each statement linked with above defined connectives has a truth value associated with it based on the truth value of the propositions appearing in them. Let’s assume there are two propositional logic symbols in concern known as P and Q. Then the following truth table depicts each of the truth values based on the various ways in which those two can be linked with the logical connectives discussed in the section is syntax.

                                            
                                                                                                   Table 2: Truth Table

 

Now let’s try to model some sentences using propositional logic we learnt so far.

Let’s assume a small world like below where we have the following knowledge.

  • It is cloudy today.
  • It is gloomy today.
  • If it is cloudy and gloomy, it is definitely going to rain today.

So let’s represent the above sentences in propositional logic.

  • C -Cloudy
  • G – Gloomy      Propositional symbols required to represent the world in concern
  • R – Rain
  • ((C ˄ G) -> R) (It is known that if it is both cloudy and gloomy then it would rain, so we have link C and G with a logical conjunction and then R with an implication)

Since there are 3 propositions in this sentence there are 23 = 8 possible models of truth values for which we can define the semantics of this sentence. But out of those 8 models, the sentence ((C ˄ G) -> R) would only be false in the model where C = True, G = True and R= False (where “it is both cloudy and gloomy but, it does not rain” which contradicts our knowledge of rain as per the assumption made) as per the truth table. (You can try this out by constructing the truth table for this sentence)

Likewise for anything in concern for each of the known facts (knowledge about the world in concern) you can construct propositional sentences using propositional symbols and connectives based on the syntax to come up with different semantics which in turn would yield a knowledge base full of propositional sentences.

Wrapping up

In this article we looked at what Knowledge representation and reasoning with regard to AI is all about as well as went in to learning how to use simple propositional logic in this matter. We would go in to discuss reasoning with propositional logic, advantages and disadvantages of propositional logic in the next article, for which you would need to have grasped the basics I have described today. So make sure, you understand these simple concepts which would be extremely essential in learning how to use a knowledgebase to reason out things and also to understand more complex logics such as predicate logic and other knowledge representation languages to follow.

Reference

·  
Artificial Intelligence – A modern Approach, Second edition, Stuart Russell&Peter Norvig
·  Knowledge Representation&Reasoning – Ronald Brachman&Hector Levesque

 

Moving forward

In the previous article we took a glimpse of the vast field of Artificial Intelligence. Hope you all learnt about the history and the basic background to research in this area. Let’s move forward so that we can learn about more interesting areas in AI in depth.  This article would be covering up some philosophical and scientific aspects of AI which are important to be aware of which would yield to better understanding the material which follows up in the articles to come.

 

Concepts of modeling intelligence

The concept of intelligence is a very hard thing to describe. As humans, we have the notion that we are superior and that we have the highest intelligence compared to all the other living animals on this planet. Philosophically speaking, we believe that we are intelligent and define intelligence as a property of human beings. Nevertheless, we do not know for sure, whether there are any other species that are far more intelligent than humans because, we tend to believe that man-kind is born with intelligence. All the concepts of AI are based on the fact that they are compared to human intelligence, because as humans that is the only form of intelligence that we know of and that we have experienced. Yet, we are faced with a whole bunch of questions such as what exactly is intelligence, how do we measure it, what are the factors that contribute to creating intelligence, etc? With regard to these we then face the query as to how we narrow these down. Is it being smart? Being able to think and take decisions? Act correctly to suit a specific situation? Ability to gather knowledge, remembering, recalling and reasoning it when such occasion occurs? Skill of learning things? Is it a genetically inherited aspect? This is an extremely difficult thing to define because, based on personal experience different people define intelligence differently in any way that they think is the best. In the past, researches in the area of AI also faced this situation. Ultimately, different areas of thought on intelligence were brought in to limelight. The researchers defined AI based on two main characteristics that they observed and thought which contribute a great deal in to human intelligence which are as follows.

The mental thought processes and reasoning

Behavior or actions

Based on the above two characteristics that researchers believed that intelligence can be generated the following approaches to AI were originated. The names of these approaches were mentioned in the last article but in here we go in to more detail and provide an in depth view of each one of them.

Thinking humanly – This was more linked with the thought processes and reasoning ability which generated intelligence rather that the behavioral aspect. It was believed that if we can build machines which can think and reason like humans then we have achieved some part of intelligence in those machines. The areas of interest were decision making, problem solving, learning abilities which led to researching in psychologically understanding how the human mind thinks and how the thought processes work, linking cognitive science and natural languages with AI.

Thinking rationally – The idea behind rationality is such that, to think the right thing at the right time based on what is known. Humans usually think rationally although they do make mistakes in their reasoning processes sometimes due to mistakes in thought processes, lack of information, stress and other mental factors, beliefs and emotions which results in irrational thinking. But nevertheless, this notion of rationality whether it being a human being or any other being if they can think of the right thing based on the what they know it can be considered as the best thing to think of given the circumstances. Thus, this shows a form of intelligence. In AI this approach was closely linked to studying of mental processes with the use of computational models so that it leads to rational thinking. The ideas of logic based reasoning were connected to AI with this approach.

Acting humanly – This approach was mainly trying to define AI as building machines which can perform the actions that are done by humans without human intervention in the same or closer manner. Thus, this idea is highly linked with the aspect of humans being the intelligent species of all and what they do is right because they do it with intelligence. The areas which nurtured from this aspect are humanoid robots, robots which perform day to day tasks such as cleaning, making coffee/tea, etc. This lead to linking mechanical and motor skills of humans in to machines so that they can perform the actions that the humans were better off doing. The subject areas such as Natural language processing, learning, computer vision, robotics and knowledge representation were nurtured with this approach to AI.

Acting rationally – The last approach was making agents or machines act in a rational manner so that they would be able to perform the right action and the right time. This was when the notion of ‘rational agents’ came in to the scene. This approach was highly adopted by many scientists in the field of AI because it was less linked to human centered approaches such as ‘acting humanly’ or ‘thinking humanly’ because they tend to focus on the fact that intelligence in some characteristic inherent to humans which is certainly of doubt and can lead to many philosophical and scientific arguments. Further, it was a more general approach looking at rationality and also more generalized than the notion of ‘thinking rationally’ which is dealing with logically representing the thought process which would be not very successful in highly dynamic environments and will not be perform well under uncertainty.

 

Further thoughts on AI

Although the above approaches defined what is required and intended out of AI, the areas to discover were immense. Here are some aspects which future of AI would highly depend on.

Further research was carried out and it was found out that even though the mental processes are a key to intelligence, it requires a fair amount of perceptual abilities such as vision which gives the edge to intelligent beings such as so called humans to think far better than others. Computers, on the other hand had a disadvantage when compared to humans of not being able to perceive their environments in which they operate other than by means of the data or other facts that humans themselves feed in to the machine. The area of ‘computer vision’ was then brought out in to the picture, so that researches were able to discover how humans perceive things in their environment through the ability to see using their eyes. Various researches are being undertaken in this domain of Computer Vision which spans across multiple disciplines such as Biology, Neuroscience and AI. There have been attempts to build in human like vision capabilities and perceiving systems in to robots and other machines with some success. Researchers were able to build the vision aspect to see and visualize things using image sensors and other mechanisms in machines, yet the actual goal of computer vision is yet to be discovered. It is not just seeing things from the eyes or any other visual systems that matters most, but the process afterwards which maps the images to symbols and other mental representations which generates knowledge. Still the robots and agents which act as machines with high capabilities of intelligence lack the real power of human vision system which is being able to symbolically represent the world they perceive while linking it with the other things they have perceived in the past to generate new knowledge, ideas, thoughts and reasoning. Thus, the future of intelligent systems would really benefit from the advancements in Computer vision which would enable the machines to perceive the world closer to how humans do.

The aspect of ‘consciousness’ or ‘self awareness’ which makes humans know beforehand about the world based on their past experiences is another thing which is a hard thing to replicate in a machine. It is found out that ‘Consciousness’ also contributes to human intelligence in terms of making learning more easier. For example, if we know that fire would burn the skin if it was taken too closer to our body because our parents have taught us so when we were kids or with experience we would tend not to bring harm to us using fire carelessly. This shows that we are conscious of the fact that fire is dangerous although it is useful for day to day life. But, a machine on the other hand, would not have this ability unless we explicitly insert a rule so that not to use fire too close. But still then, it is very difficult to model such characteristic in a machine because, then you have to deal with lots of minor details such as how close it can come without causing damage, how strong the fire would be to cause a damage, etc, because as the machine cannot perceive as well and use the self-awareness as we have. Some other thoughts that were brought up were the notion of ‘memes’ which are like the genes which contribute to the fact that which makes humans different and more superior to other living beings. Philosopher, Susan Blackmore wrote in her book named “The Meme machine” that humans imitate what other humans do and learn from those. This is passed on from person to person and was known as “meme” as in genes pass our heredity and actual structure of our organisms in a physical sense she argues that “memes” pass on our knowledge and ideas gained from others. This ideas have brought challenges to the field of AI if the researches are focused on building machines which are acting humanly or thinking humanly because, then they have to think of ways and means of how to model knowledge and ideas are passed on from one being to another, aspects such as ability to imitate in to the machines as well.

 

Where are we heading at?

In this article, the main intention was to give you all a philosophical and scientific background to the thought in AI so that you develop to think of this subject in a more in depth manner before we go on to details of each sub area. We have to keep in mind that the four main approaches described in the second section are very important in understanding where we are heading next. The other areas and thoughts that were presented in the third section give a good insight to where AI’s future direction would be and a brief idea of where we have to focus on. In all the other articles to follow, you would have the opportunity to get an understanding of all the sub areas of AI such as learning (which is known as ‘machine leaning’ when related to machines), logic and reasoning, knowledge representation and knowledge bases, data mining, decision making, intelligent agents, search techniques, computer vision, natural language processing and many more.

 

References

Artificial Intelligence – A modern Approach, Second edition, Stuart Russell&Peter Norvig

The Meme Machine, Susan Blackmore

He was desperate to find her when he was abandoned by the mother despite her love towards the boy due to social phenomena. Think for a minute. Am I describing a real scenario that happened between a human son and a mother or can you recall some story which had the same resemblance?  Yeah, you are right. I was just giving a short description of Steven Spielberg’s film “Artificial Intelligence”. So, David was actually a humanoid robot boy with emotions such as love as well as a certain level of intelligence fed in to his systems to be able to appear quite similar to a human boy. So what is Artificial Intelligence (AI)? It has been a question which was answered in many different ways based on the emphasis of the era that was being considered. First it was termed to describe machines which act as humans. There were other definitions such as machines ‘acting rationally’ (doing the right thing to suit the situation and problem in hand), ‘thinking rationally’ and ‘thinking humanly’.

 

History of Artificial Intelligence

The first research which can be considered as to be in-line with AI was done by Warren McCullouch and Walter Pitts in 1943 They proposed a model of neurons (as the ones which are in a human brain) in an artificial manner to represent neural properties. They also suggested that with the use of many such neurons combined as in a network could be used to model logical connectives such as AND, OR, NOT. Another important point that they suggested was that given the necessary data such neural networks could learn which is one of the early births of learning techniques to be suggested which later improved to neural network based learning in greater scale. In 1949 Donald Hebb was successful in introducing a simple updating rule so that the neural network connections which were used to connect each of the neurons to their neighboring neurons could be updated. It was known as “Hebbian Rule” which is even used in neural network learning at the simplest level nowadays. Princeton university graduate students, Marvin Minsky and Dean Edmonds started working on the neural network computer in 1951 which was called as SNARC. It is said that although the above mentioned research had resemblances of Artificial Intelligence, Alan Turing was the first to introduce the whole concept of AI with the an article named “Computing Machinery and Intelligence” in which he introduced the famous Turing test and other AI concepts such as Machine Learning, genetic algorithms and reinforcement learning to the world.

The coining of the name “Artificial Intelligence” was done at the Dartmouth conference held in 1956 which consisted of many US researchers of the era such as Allen Newell, Herbert Simon, John McCarthy and Marvin Minsky. It was proposed my John McCarthy to name the field of machines being able to simulate or act with intelligence as “Artificial Intelligence” which was since then called by that name irrespective of whether that term precisely depicts the area in concern.

The time period after the Dartmouth conference, many researches came up with computer programs to address AI aspects, within the limited computational power and tools available at that time. In 1957 Newell and Simon created a computer program called “General Problem Solver” which was intended to act as a universal problem solver for problems which can be formulated in to symbolic representations. But this was not able to handle real world problems other than defined problems such as chess games, theorem proving, towers of Hanoi, etc. Many such problem solving programs such as ‘Geometry Theorem Prover’ by Herbert Gelertner(1959), Program for playing checkers by Samuel(1952-1956) followed. LISP, a high level programming language specifically to cater to the AI domain was introduced by McCarthy in 1958 making a great breakthrough to the future of Artificial Intelligence. The next major aspect which was introduced was the concept of Knowledge-based systems. In the mean time, researches started thinking in the line of how humans gain intelligence through learning from the knowledge they gather. This gave rise to the development of Knowledge based systems, one of the first main such systems being the DENDRAL program by Buchanan and fellow researchers in 1969 in order to solve the problem of inferring molecular structures. Another system that was developed for diagnosing blood infections was called MYCIN and was quite successful in its task even sometimes better than human experts showing that the area of research is promising. AI based expert systems and knowledge based systems was used for industrial purposes as well for some time but it the systems lacked long term prospects. AI was developed and continued as a Science where new areas of research coming in to the scene. Neural networks were given more importance and research was carried out further since 1986. Speech recognition, Linguistics, Data mining, Machine learning, Pattern classification, clustering, and many more areas were interlinked to AI and was starting to boom.

 

An unbroken bond

AI is a vast subject where many other disciplines are intermingled. Mathematics, Logic, Medicine, Genetics, Philosophy, Economics, Psychology, Cognitive Sciences, Computer Science, Computer Engineering, Robotics and Linguistics are some of the other subject areas which foster the research in AI and also whom which get improved from AI’s contributions. For example, most of the AI programs are based on foundations in Mathematics and logic. Further areas such as medical diagnosis, robots for surgeries have been developed to assist the human medical practitioners to provide a better service to the patients. Projects such as identifying human genomes, DNA classifications have benefited from the AI related experiments such as pattern classifications, clustering, etc. This shows that AI has a strong bond between lots of other disciplines which make the subject having lots of research to be carried out in a vast number of lines. This makes the evolving of AI to be wider but slower compared to other scientific subjects. Nevertheless, as the various contributions in all these domains help make the life of mankind better and more easier, so that the bond among these interlinked subjects remain while researches find means of  strengthening it further in the future with many other findings.

 

Artificial Intelligence in practice

For a general person what would AI mean? He would not care whether it is an advanced interrelated subject or not. You and I should have some benefit for us to believe and identify the importance of AI. Therefore, let’s look at how AI has approached our lives in practice. Have you encountered when you are browsing the internet to buy something, some sites recommend you products to buy based on your past buying trends and likings? Do you know that you can even delegate the task of ordering your weekly grocery goods online to a computer agent? Yes, you can. All these are enabled due to the existence of intelligent software agent systems which can act rationally and perform the task given, which is a part of AI. Further, have you heard of robot pets that are used to behave like actual pets in giving total love and caring to the elderly people in Japan? There are medical testing devices, which enables the lab technicians as well as the medical practitioners to easily diagnose an illness of a patient and also prescribe required drugs or treatments accurately with the help of AI. Nowadays there are even programs which can automatically generate and compose music and programs and which can select music to play based on the rhythm of walking (enabled using wireless communication between your music player and a device placed in your shoe as you are walking).

For sure, you must have heard about the world renowned chess master Gary Kasparov being defeated against a chess game from his opponent “Deep Blue” an intelligent chess playing machine developed by IBM in 1997. Gaming is another area where AI related concepts could be applied to build computers to play different games that can play against human or other computer players effectively. The above are only a very few of the applications of AI which a general user would be able to witness as at resent.

There is yet more to tell, yet more to find, yet more to explore in this vast and exciting field of Artificial Intelligence. The specific details and technical aspects of the various areas in AI would be covered in the articles to follow in the months to come, giving you a better feeling of Artificial Intelligence and to create wonder, interest and enthusiasm in this field.