Final State Exam - Artificial Intelligence block (syllabus) ================================================= last modified: 15.6.2003 Problem Solving Methods in Artificial Intelligence (Introduction to Artificial Intelligence) ----------------------------------------------- Search - state space, blind(uninformed) search methods - informed search methods - Minimax, Alfa-beta prunning. CSP - constraint satisfaction problems, backtracking, heuristics - forward checking, edge consistency algorithm, local search Logic - unification, resolution, forward and backward chaining Planning - Strips, Pop, graphs Uncertainty - Bayes Rule, Bayesian Networks, exact inference in Bayesian Networks (inference by enumeration, variables elimination algorithm) - approximate inference in Bayesian Networks (direct sampling, rejection sampling) - approximate inference in Bayesian Networks (likelihood weighting, algorithm MCMC) - Hidden Markov Models - dynamic Bayesian Networks Perception - edge recognition, image segmentation Robotics - hardware, perception, localization, navigation ==== Probabilistic language processing - PCFG, IR systems - Machine translation: language model, translation model Decision making - Markov decision processes (MDP), value iteration, strategy iteration - Partially Observable Markov Decision Processes (POMDP). Learning - EBL, KBL, KBIL - decision trees, algorithm ID3 - statistical learning: discreet models, continuous models, Structure Learning of Bayesian Networks - statistical learning: algorithm expectation-maximization (EM) - statistical learning: clustering, Structure Learning of Bayesian Networks with hidden parameters - passive reinforcement learning (direct utility estimation, ADP, TD learning) - active reinforcement learning (exploration, action value function) - artificial evolution Game Theory - pure and mixed strategies, Nash equilibrium Expert systems I ------------------ Conceptual background of Expert Systems. Characteristic features of implementation of expert systems. Hypoteses of Newell and Simon, Feigenbaum, Smith. Aplications of expert systems. Reproductive and productive problem solving, declarative programming paradigm. Control principles in procedural and declarative programs. Nondeterminism, heuristics, heuric rules. Symbolic knowledge representation, terms and assertions. Frame representations and their relation to other representational formalisms. Frame (object) types, hierarchical frame networks. Slots, meta-slots, slot values. Source priority, 'when-needed' and 'when-changed' methods. Inheritance strategies in static and dynamic networks, multiple-inheritance. Production rules, semaphores, IF and THEN rule parts. Consequents with multiple antecedents. Condition types in the antecedent. Quantified condition sets, quantifier semantics. Implicit object references, matching methods, universal and existential quantifiers, indirect object references, object filtering (wildcard method). Basic and advanced derivation strategies, conflict set, structured agenda, associations, cross-references, complementing, spontaneous data entry, free binding. Non-monotonous inference, chronological revision inference methods also with explanations, protocol, default values - in activated and non-activated states. Approximate inference, uncertainty in production rules, quantitative and qualitative approximate inference methods, advantages and shortcomings. Neural networks --------------- Binary perceptron: supervised learning, perceptron learning rule, pattern classification, linearly separable problems. Different perceptron activation functions. non-linear perceptron, error function and its minimization. Multiple-layer feed-forward neural networks, backpropagation learning method and derivation of its learning rule for 2-layer and n-layer feed-forward neural network Modification of the default learning rule using momentum. Multiple-layer NN as universal function approximator, training and testing sets, generalization, overlearning, premature convergence, model selection, cross-validation, bootstrap. Solvable and suitable tasks for multiple-layer NN. Reinforcement Learning in multiple-layer NN, game playing using NN. "Radial basis function" RBF feedforward neural networks learning and usage. Recurrent NN: data time window, suitable and unsuitable tasks for feed-forward neural networks with time delay. Example of recurrent NN learning on regular grammar. Training of recurrent NN: real-time recurrent learning (RTRL), backpropagation through time (BPTT). Possible applications of recurrent NN for prediction tasks and processing of time data sequences. Extracting rules from examples using NN, analyzing the state space of recurrent NN using iterative functions systems (IFS). Self-organized NN: SOM architecture, Kohonen algorithm, clustering, Voronoi diagrams, topology mapping, data dimension reduction, examples of use. Theory of Knowledge representation and inference ------------------------------------------------ Knowledge representation - elementary concepts and assumptions. Databases and deductive databases. Databases with hypotetical inference. Non-monotonous inference. Preserving consistency, revisions, inference with inconsistences. Default theories. Inference with hierarchical networks with multiple inheritance and exceptions. Induction. Abduction. Negation semantics in logic programming and deductive databases. Revisions. ================================================================== Multiagent systems ------------------ Agent (definition) Autonomy amd mobility. Receptors, controller, sensors, actuators. Classification of agents: reactive, deliberative and hybrid. Communication between agents: direct, indirect. Problem of ontologies and its solutions: XML and KIF. Multiagent system (definition). Communication and representation language. KQML. Implementation of multiagent systems. Classification of agents: intelligent and software agents. Multiagent system as middleware. Implementation over model SRR. Pyramidal architecture Client - Server. Architecture Agent - Space. Robustness, decentralization, normalization. Deliberative and non-deliberative robotics. New AI. Function- vs. behavior- decomposition. Subsumption architecture. PKA model. Expert systems II ----------------- Globalizing forms of inference. Planning mechanisms, hierarchical and causal dependencies, conditional production rules. Planning operators, integration of partially coherent results, methods for detecting mutual dependencies. Constraints, constraint propagation, resolving inconsistencies, constraint satisfaction, principles of symbolic rewriting. Hierarchical problem solving, serializable and non-serializable problem partitioning, interacting subproblem solutions. Qualitative models, three-value space of qualitative values algebra, functional dependencies betweeen qualitative variables, structural operations, propagation and production loop, rules of prediction, detection and propagation of binding. ES architecture, basic components, purpose and functions of communication, explanation, connecting, and output (result generator) modules. Knowledge base building and maintainance methods. Computer linguistics -------------------- (Bibliography: Allen, J., Natural language understanding, chapters 3, 4, 8, 9, 14, 15) Syntactic analysis of natural language. Feature-augmented grammars. Semantic interpretation. verb structure, sematic roles. Grammars augmented by semantic features. Logic form - representation of meaning. Resolving semantic ambiguities - selection restrictions, hierarchy of elementary categories, semantic networks. Context and knowledge. Using context representation in natural language analysis: generating discourse entities, anaphor resolution, interpretation of pronouns. Using general knowledge in actions and causality analysis. Qualitative modelling and simulation ------------------------------------ 1.Basic concepts: physical system, structure, model, behavior, function, modelling versus simulation. 2.Qualitative differential equations (QDE): variable, space of significant values, qualitative value, qualitative binding, corresponding values, transition conditions. 3.QSIM definitions of system, its state and behavior. 4.Structural abstraction: relation between ODE (diferential equations) and QDE. 5.Algorithm QSIM: completion of state (propagation loop), next state prediction (prediction loop) 6.Mathematical properties of QSIM: Theorem on guaranteed cover, false behavior 7.Methods for simulation results improvement (their principles): Bounding by higher-order derivations, omitting difference direction , energetic filters, limiting to non-intersecting trajectories 8.Comparative statics: exogen variable, quasistatic system, equilibrium, perturbation, algorithm for analysis of equilibria, time-decomposition principle 9. Automatic modelling: Component-oriented approach and component modelling, qualitative process theory and compositional modelling Cognitive science ----------------- 1.What is cognitive science Cognitive sceince characterization, knowledge embodiment 2.Mental processes and represenation Symbolic versus subsymbolic representation Gardenfors conceptual space 3.Vision Marr's levels of analysis that a good theory must contain. Rods and cones Computational image analysis steps Depth-perception - stereopsis Color vision 4.Neural science Neuron, synapse, neurotransmiter, mechanism of signal transport Functional assymetry (functional differences) of brain hemispheres Use of double dissociation in neuropsychology Blind-sight phenomenon 5.Memory Memory functions, memory types Short-term and buffer memory Long-term memory types ACT memory model, Hopfield memory model 6.Communication and language Recalled and separated representations, signals, icons and symbols. 6 types of communication systems according to Gardenfors Phonological analysis, Morton and Marslen-Wilson model of word recognition Chomsky theory of universal grammars 7.Language development modelling Three mechanisms of complexity emergence Self-organization - 3 methodologic rules of modelling Emergence of syllabic system Emergence of common lexicon 8.Learning Animal learning types Explain concepts: sample - text/informed, patterns, hypotheses space, limiting convergence Gold algorithm of inductive grammar inference Gold - Feldman theorem about text sample, Gold theorem about informed sample 9.Reasoning: deduction, induction, mental models, creativity Semantic information, deduction and induction from the viewpoint of increasing semantic information Deduction as reasoning with models Induction and specialization/generalization of concepts, induction algorithms 10.Conscious and unconscious mind Computational model of conscious and unconscious processes, model of self, meta-reasoning Computational model of desires and emotions Machine learning ---------------- Instance based learning. Concepts and concept learning. Inductive bias. Version space. Candidate-elimination algorithm. Inductive decision tree building: algorithm ID3. Inductive inference, inference of grammars. Convergence criteria: identification by termination, limiting identification. Chomsky hierarchy and termination/limiting identifiable grammars. Computational learning theory. Concept identification models: PAC (Probably Approximately Correct) learning. Occam razor. Vapnikov-Chervonenkisov dimension and the amount of data required for learning. Computational complexity of learning. Consistency problem and its relation to polynomial time learning. Learning analysis of some representation schemes: boolean functions in disjunctive normal form, neural networks (perceptrons).