Fundamentals of Artificial Intelligence

Frontmatter

Chapter 1. Introducing Artificial Intelligence

Abstract

The field of Artificial Intelligence (AI) has interfaces with almost every discipline of engineering, and beyond, and all those can be benefited by the use of AI. This chapter presents the introduction to AI, its roots, sub-domains, Turing test to judge if the given program is intelligent, what are the goals of AI for Engineers and Scientists, what are the basic requirements for AI, symbol system, what are the requirements for knowledge representation, and concludes with a chapter summary, and an exhaustive list of exercises. In addition raises many questions to ponder over, like, consciousness, and whether it is possible to create artificial consciousness.

K. R. Chowdhary

Chapter 2. Logic and Reasoning Patterns

Abstract

Logic is the foundation of AI, and the majority of AI’s principles are based on logical or deductive reasoning. The chapter presents: contributions of pioneers of logic, the argumentation theory, which is based on logic and with its roots in propositional logic, the process of validating the propositional formulas, their syntax and semantics, interpretation of a logical expression through semantic tableau, followed with presents the basic reasoning patterns used by human, and their formal notations. In addition, presents the normal forms of propositional formulas and application of resolution principle on these for inference. The nonmonotonic reasoning and its significance is briefly described. At the end, the chapter presents the axiomatic system due to Hilbert and its limitations, and concludes with chapter summary.

K. R. Chowdhary

Chapter 3. First Order Predicate Logic

Abstract

The first order predicate logic (FOPL) is backbone of AI, as well a method of formal representation of Natural Language (NL) text. The Prolog language for AI programming has its foundations in FOPL. The chapter demonstrates how to translate NL to FOPL in the form of facts and rules, use of quantifiers and variables, syntax and semantics of FOPL, and conversion of predicate expressions to clause forms. This is followed with unification of predicate expressions using instantiations and substitutions, compositions of substitutions, unification algorithm and its analysis. The resolution principle is extended to FOPL, a simple algorithm of resolution is presented, and use of resolution is demonstrated for theorem proving. The interpretation and inferences of FOPL expressions are briefly discussed, along with the use of Herbrand’s universe and Herbrand’s theorem. At the end, the most general unifier (mgu) and its algorithms are presented, and chapter is concluded with summary.

K. R. Chowdhary

Chapter 4. Rule Based Reasoning

Abstract

The popularity of rules-based systems (RBSs) is due to their naturalness. This chapter presents the potential applications of RBSs, the working of RBS, forward and backward chaining RBSs, their Algorithms, and inferencing using these systems. The analysis of complexity of preconditions, and efficiency of rule selection are introduced to sufficient depth, as well the cofmparison between the two types of RBSs are presented. A typical RBS, and other methods—model-based and case-based approaches are also discussed. In addition, number of solved, as well exhaustive list of exercises are provided at the end of the chapter for practice. The chapter concludes with its summary.

K. R. Chowdhary

Chapter 5. Logic Programming and Prolog

Abstract

Prolog  is logic programming languages for AI, based on predicate logic. This chapter discusses the structure, syntax, and semantics of Prolog language, provides comparison with procedural language like C, interpretation of predicate logic and that of Prolog, both formally as well through worked out examples, and explain how the recursion is definition as well solution of a problem, and explains with simple examples as how the control sequencing takes place in Prolog. Use of two open source compilers of prolog using simple worked out examples is demonstrated. Each concept of Prolog and logic programming is explained with the help of worked out examples. At the end, a brief summary gives glimpse of the chapter, followed with number of exercises to strengthen the learning.

K. R. Chowdhary

Chapter 6. Real-World Knowledge Representation and Reasoning

Abstract

Apart from its theoretical significance, the AI must represent real-world knowledge, and produce reasoning using that. The real-world things are collections of entities in different classes. This chapter presents the representations structures for such knowledge, e.g., taxonomies and reasoning based on that. Other phenomena in real-world, that are presented are, action and change, commonsense reasoning, ontology structures for different domains, like, language, and world. The Sowa’s ontology for objects, and processes, both concrete and abstract, is explained. The situation calculus is presented in its formal details, along with worked exercises. The more prevalent real-world reasoning, like nonmonotonic and default reasoning are also treated in sufficient details, along with supporting worked exercises. This is followed, with summary of the chapter, and exhaustive list of practice exercises.

K. R. Chowdhary

Chapter 7. Networks-Based Representation

Abstract

Network-based method is another approach for knowledge representation and reasoning. They have particularly the advantage that, using the network one can navigate through the knowledge represented, and can perform the inferences. This chapter presents the semantic networks, conceptual graphs, frames, and conceptual dependencies, as well as their syntax and semantics. The \(\mathscr {DL}\) (description logic)—a modified predicate logic for real-world applications is treated in detail, with examples of its language—the concept language for inferencing. Conceptual dependency (CD) is a language-independent representation and reasoning framework, such that whatever may be the natural language used, as long as its meaning is the same, the CD will be the same. The script language for representation and reasoning along with its syntax, semantics, and reasoning for CD is presented, followed with chapter summary, and an exhaustive list of exercises.

K. R. Chowdhary

Chapter 8. State Space Search

Abstract

State space search is one of the three fundamental requirements to achieve AI. This chapter present the basic techniques, called uninformed search, of searching the goal in problem solution. A search requires the representation of state space in the forms of a directed graph. The basic methods—depth-first search (DFS), breadth-first search (BFS), along with their algorithms, analysis of these algorithms, and along with worked out exercises are presented. The improved techniques—iterative deepening DFS, and bidirectional search, followed with chapter summary, and then large number of practice exercises are provide at the chapter end

K. R. Chowdhary

Chapter 9. Heuristic Search

Abstract

This chapter provides in depth study of heuristic search methods—the methods for searching the goal (solution) to problems, that are more like human, and do not follow the exhaustive search approach, making them far more efficient than the uninformed search methods. The introduction starts with formal definition of heuristic search, then follows Hill-climbing searches, their algorithm and analysis, best-first search, its algorithm and analysis, optimization, A-star search, and approaches to better heuristics. Finally, the search methods—simulated annealing (based on treatment of metals), Genetic Algorithm (GA)-based search method, along with their analyses are presented, followed with chapter summary, and at end an exhaustive list of practice exercises, along with multiple-choice questions are provided.

K. R. Chowdhary

Chapter 10. Constraint Satisfaction Problems

Abstract

Constraint Satisfaction Problems (CSPs) is a theory about some special type of problems, where every move of search is subject to fulfillment  of certain constraints. The chapter introduces with such problems in the beginning, then presents a formal general model of such problems with analysis, explains the solution approach with the synthesis of constraints using simple, as well extended theory of synthesis. Next, it presents the classes of CSP algorithms—generate and test, backtracking, discusses how efficiency can be increased, propagation of constraints, followed with cryptarithmetics, chapter summary, and then at the end a list of exercises for practicing.

K. R. Chowdhary

Chapter 11. Adversarial Search and Game Theory

Abstract

Game theory is the formal study of conflict and cooperation, first time introduced as long back as 1921 by mathematician Emile Borel, then enriched in 1928 by von Neumann and Oskar Morgenstern, and much enriched by Josh Nash, has enormous applications, including    in business, and even in the prediction of election results, etc. The game playing is also a search process. The chapter presents the classes of games as combinatorial and games of chance, then further as zero-sum games and non-zero-sum games, the prisoner’s dilemma, game playing strategies, the games of perfect information, arbitration scheme in games, minimax search in game playing, and analysis of specific games like tic-tac-toe. The more efficient search processes like alpha and beta are presented, as well as the alpha cutoff and beta cutoff methods to prune the search process are presented and analyzed, followed with chapter summary, and an exhaustive list of exercises along with a number of multiple-choice questions provided at the end.

K. R. Chowdhary

Chapter 12. Reasoning in Uncertain Environments

Abstract

 Real-life propositions are neither fully true nor false, also there is always some uncertainty associated with them. Therefore, the reasoning using real-life knowledge should also be in accord. This chapter is aimed to fulfill the above objectives. The chapter presents the prerequisites—foundations of probability theory, conditional probability, Bayes theorem, and Bayesian networks which are graphical representation of conditional probability, propagation of beliefs through these networks, and the limitations of Bayes theorem. Application of Bayesian probability has been demonstrated for specific problem solutions. Another theory—the Dempster–Shafer theory of evidence—which provides better results as the evidences increase is presented, and has been applied on worked examples. Reasoning using fuzzy sets is yet another approach for reasoning in uncertain environments—a theory where membership of sets is partial. Inferencing using fuzzy relations and fuzzy rules has been demonstrated, followed by chapter summary, and a set of exercises at the end.

K. R. Chowdhary

Chapter 13. Machine Learning

Abstract

To adapt to the environment it necessary that intelligent machines must have the capability to learn. This chapter presents the basic concepts and techniques of learning found in humans, as well as their implementation aspects for machines. The chapter presents the challenges of building learning capabilities in machines, types of machine learning, and the relative efforts needed to build these learning capabilities. The philosophy of the discipline of machine learning is presented. The basic model of learning is discussed, followed by the classes of learning—supervised and unsupervised—then various techniques of inductive learning—argument based learning, online concept learning, propositional and relational learning, and learning through decision trees—are presented in sufficient details. Other techniques like discovery-based learning, reinforced learning, learning and reasoning through analogy, explanation-based learning are presented, with some worked examples. Finally, the potential applications of machine learning, the basic research problems in machine learning, followed by chapter summary, and a set of exercises are appended.

K. R. Chowdhary

Chapter 14. Statistical Learning Theory

Abstract

A machine learning system, in general, learns from the environment, but statistical machine learning programs (systems) learn from the data. This chapter presents techniques for statistical machine learning using Support Vector Machines (SVM) to recognize the patterns and classify them, predicting structured objects using SVM, k-nearest neighbor method for classification, and Naive Bayes classifiers. The artificial neural networks are presented with brief introduction to error-correction rules, Boltzmann learning, Hebbian rule, competitive learning rule, and deep learning. The instance-based learning is treated in details with its algorithm and learning task. The chapter concludes with a summary, and a set of practice exercises.

K. R. Chowdhary

Chapter 15. Automated Planning

Abstract

Automated planning deals with the tasks of finding out ordered sets of actions that allow a system to transform an initial state to a state satisfying goal specification. The set of actions is a plan, and it belongs to PSPACE-complete. Automatic planing or scheduling generates a set of actions automatically. This chapter presents the nature of automated planning, the classical planning problem, agent types that execute the problem, and worked examples. It also covers, the concepts and implementation aspects of forward planning, partial-order planning, planning languages, a case study of general planning language—STRIPS, and search strategies. Planning with propositional logic, planning graphs, and hierarchical network planning are demonstrated. The multiagent planning techniques are presented for goal and task refinement, decentralized planning, and on how to do coordination after it is planned. This is followed by the chapter summary, and a set of exercises.

K. R. Chowdhary

Chapter 16. Intelligent Agents

Abstract

The  intelligent agents are being viewed as new theoretical models of computation that more closely reflects current computing reality, aimed as new generation models for complex and distributed systems. An agent system can work as a single agent, or as a multiagent system. The intelligent agents have many applications—they are used in software engineering, in buying and selling—like online sales, bids, trading; the agents are also modeled for decision-making—with preferences and criteria for making decisions. This chapter also presents the classification of agents, agent system architecture, how the agents should coordinate among themselves, and the formation of a coalition between agents. The multiagents communicate with each other using agents’ communication languages which are oriented towards performing actions. Other categories of agents are mobile agents—programs which can be moved to any far off place, and can communicate with the environment. The chapter ends with chapter summary, and the set of exercises.

K. R. Chowdhary

Chapter 17. Data Mining

Abstract

Data mining, or knowledge discovery in databases, provides the tools to sift through the vast data stores to find the trends, patterns, and correlations that can guide strategic decision-making. The chapter highlights the major applications of data mining, their perspectives, goals of data mining, evolution of data mining algorithms—for transaction data, data streams, graph, and text-based data—and classes of data mining algorithms—prediction methods, clustering, and association rules. This is followed with cluster analysis, components of clustering task, pattern representation and feature extraction, similarity measures, and partitional algorithms. Data classification methods like decision trees and association rule mining are presented with worked examples. Sequential pattern mining algorithms are presented with typical pattern mining and worked examples. The chapter concludes with scientific applications of data mining, chapter summary, and list of practice exercises.

K. R. Chowdhary

Chapter 18. Information Retrieval

Abstract

Information retrieval (IR) is the identification of documents or other units of information in a collection that are relevant to a particular information need—a set of questions to which someone would like to find an answer. This chapter presents the basic strategies of IR in length along with their analysis, particularly emphasizing the vector space and probabilistic models of IR, with worked examples in each category; gives the detailed coverage to construction and maintenance of index, and its parallel processing. The fuzzy logic-based retrieval, concept-based retrieval techniques, their algorithms, and worked examples are presented; and Automatic Query Expansion has been dealt with at length. Application of Bayesian networks, and inferences using these have been demonstrated for IR. The newly emerged semantic web for futuristic IR and its applications have been introduced; and the design aspects of distributed IR suited for currently distributed information resources are treated in depth. The chapter ends with the summary and a set of practice exercises.

K. R. Chowdhary

Chapter 19. Natural Language Processing

Abstract

The abundant volume of natural language text in the connected world, though having a large content of knowledge, but it is becoming increasingly difficult to disseminate it by a human to discover the knowledge/wisdom in it, specifically within any given time limits. The automated NLP is aimed to do this job effectively and with accuracy, like a human does it (for a limited of amount text). This chapter presents the challenges of NLP, progress so far made in this field, NLP applications, components of NLP, and grammar of English language—the way machine requires it. In addition, covers the specific areas like probabilistic parsing, ambiguities and their resolution, information extraction, discourse analysis, NL question-answering, commonsense interfaces, commonsense thinking and reasoning, causal-diversity, and various tools for NLP. Finally, the chapter summary, and a set of relevant exercises are presented.

K. R. Chowdhary

Chapter 20. Automatic Speech Recognition

Abstract

There are basically two application modes for automatic speech recognition (ASR): using speech as spoken input or as knowledge source. Spoken   input addresses applications like dictation systems and navigation (transactional) systems. Using speech as a knowledge source has applications like multimedia indexing systems. The chapter presents the stages of speech recognition process, resources of ASR, role and functions of speech engine—like, Julius speech recognition engine, voice-over web resources, ASR algorithms, language model and acoustic models—like HMM (hidden Markov models). Many open-source tools like—Kaldi speech recognition toolkit, CMU-Sphinx, HTK, and Deep speech tools’ introduction, and guidelines for their usages are presented. These tools have interfaces with high-level languages like C/C++ and Python. The is followed with chapter summary and set of exercises.

K. R. Chowdhary

Chapter 21. Machine Vision

Abstract

The goal of computer vision is to extract information from images—a method that can produce a structure from motion, can recover a three-dimensional model of an object from a sequence of views, e.g., grasping by robot, medical imaging, and graphical modeling. This chapter presents the machine vision applications, the basic principle of vision, cognition and classification, and cognitive architecture. The cognition is—going from image-to-scene, which can be achieved through inversion by fixing scene parameters, inversion by restricting the problem domain, and inversion by acquiring additional images. The machine vision techniques are presented here for low-level, middle-level, and high-level vision. The last one requires indexing of images which can be searched through geometric hashing. One of advanced areas of vision—the object tracking, is presented in-depth, which requires the sequences—subtraction of image from background, segmentation of the image, and learning, followed with tracking. Finally, the axioms of vision, tools for computer vision, chapter summary, and practice exercises are presented.

K. R. Chowdhary

Backmatter