Introduction to Artificial Intelligence

The lecture starts from the logic fundamentals of Artificial Intelligence and presents methods of automated inference in the predicate logic. Then the inference process is re-interpreted as a space searching task, and depth-first and breadth-first search methods are presented. Next step is the overview of decision rule inference methodologies, with a stress on Rough Sets. The process of searching for decision rules is again presented as a space searching task, and few searching techniques are introduced and compared. They include various versions of best-first heuristic search methods, and few selected metaheuristics, including simulated annealing, artificial immune and evolutionary methods. After that, decision trees inference is presented, in particular ID3 and C4.5 methods, and random forests.

Lecture contents

1. Introduction (2h): weak and strong AI, concept of problem solving by searching, relation between the formulating the problem as a search task and its solvability.


2. Predicate logic(2h): basic concepts: formulas, logical functions, variables, relation to the set theory, normal forms.


3. PROLOG as an example system of inference in predicate logic (4h): example predicates, inference mechanism, substitution and unification.


4. Inference in predicate logic as a search task (2h): space of
   proofs, depth-first and breadth-first search.


5. Learning from data (2h): taxonomy of learning tasks, decision rules as a method to represent knowledge, concept of decision rules learning, ideas of AQ and Rough Set approach.


6. Rough Set approach (4h): indiscernibility relation, concepts of reduct and core indescernibility matrix, reduct derivation, decision rules inference as a searching task.


7. Heuristic search methods (4h): heuristic function, best-first search algorithms: uniform cost, greedy and A*.


8. Metaheuristic search methods (4h): simulated annealing,
   artificial immune system, evolutionary algorithm, role of randomness in
   attaining global optimization.


9. Decision trees (4h): relation between decision trees and decision rules, learning decision tree from data (ID3), overview of problems with unbalanced attribute domains and examples, measures of quality of a tree, overlearning, C4.5.


10. Ensembles of learning systems (2h): idea of bootstrapping,
    reducing generalization error by bootstrapping, random forests.

1. Writing example predicates in PROLOG (4h): searching paths in graphs, solving simple puzzles.


2. Introduction to R (2h).


3. Exercising Rough Set methology (2h): finding reducts of example information systems, learning role of attribute discretization.


4. Defining heuristic functions (4h): graph problems and board
   puzzles.


5. Exercising ID3 algorithm (2h): finding decision trees of example information systems, comparison to the Rough Set methodology, learning role of attribute discretization.


6. Bagging and random forests(1h).

1. Learning decision rules or decision trees from specific types of data, with the use of methods which are modifications of standard ones.


2. Implementation of programs of the following types:

• G. Luger, Artificial Intelligence: Structures and Strategies for Complex Problem Solving, Addison-Wesley, 2008.


• Z. Michalewicz, D. Fogel: How to solve it: modern heuristics,
  Springer, 2004.


• S.Russell, P.Norvig, Artificial Intelligence: a modern approach,
  Prentice Hall, 2002.


• http://www.roughsets.org

During the lab exercises it is possible to score up to 20 points:

• 5 points for exercise 1.


• 5 points for the exercise 3


• 5 points for the exercise 4


• 5 points for the exercise 5

• 5.0: 91-100 points


• 4.5: 81-90 points


• 4.0: 71-80 points


• 3.5: 61-70 points


• 3.0: 51-60 points


• 2.0: 0-50 points