A Preparation of A.I. Qualifying Exam

Research Statement

Big Category

• Computer Vision
• Logics and Reasoning
• Machine Learning
• Planning

Planning

AI Planning

Definition

• nonhierarchical planning
  
• least commitment approach
  
• nonlinear planning
  
• opportunistic planning+
  
• frame problem++
  
• STRIPS assumption
  
• situated activity+
  
• linearity assumption
  
• Sussman anomaly+
  
• interaction - week, strong, and very strong++
  
• reflection
  
• fluent
  
• conjunctive goal - interacting subgoals problems
  
• interacting subgoals
  
• goal regression
  
• STRIPTS operator
  
• causal link
  
• threat causal link
  
• lifting - lifting lemma
  
• downward solution property
  
• upward solution property
  
• unique main subaction codition+
  
• conditional (contingency) planning+
  
• coercion
  
• closed-world assumption
  

Search

Definition

• heuristic
  
• admissible search algorithm
  
• problem space
  
• problem instance
  
• weak methods
  
• heuristic evaluation function
  
• more informed function
  
• monotonic cost function
  
• effective branching factor - a complete tree
  
• constraint satisfaction problem
  
  • constraint graph
    
  • ordered constraint graph
    
  • arc consistency
    
  • path consistency
    
  • d-arc-consistent
    
  • k-consistency
    
• futility
  
• credit assignment problem
  
• backjumping*
  
• OPEN and CLOSED lists
  
• Manhattan distance
  
• classes of search
  

MDP

POMDP

Motion Planning

Definition

• robot
  
• task planner
  
• guarded motion
  
• compliant motion
  
• effector
  
• actuator
  
• degree of freedom
  
• sensor
  
• sonar
  
• infrared
  
• recognizable set
  
• landmark
  

Configuration Space

Mapping Obstacles

Computer Vision

Definitions

• low-level (early) vision
  
• high-level (later) vision
  
• segmentation
  
• primal sketch
  
• point-spread function
  
• Lambertian surface
  
• pyramid
  
• quad trees
  
• texel
  
• epipolar plane
  
• epipolar line
  
• emergent angle
  
• incident angle
  
• phase angle
  
• iso-brightness lines
  
• boundary lines
  
• Waltz's set*
  
• Muller-Lyer illusion
  
• Kanisza subjective edge
  
• convolution
  
• perspective projection
  
• Lambert's cosine law
  
• specular reflection
  
• reflectance map
  
• limb
  
• general viewpoint condition
  
• geometric invariant
  

Geometry

Simple Detector

Object Recognition

Logics and Reasoning

Propositional Logics

First Order Logics

Machine Learning

Definitions

• learning
  
• attribute - nominal, linear or tree structured
  
• analogy
  
• bounded inconsistency
  
• utility problem
  
• concept
  
• learning frame problem
  
• within-trial transfer
  
• across-trask transfer
  
• speedup learning
  
• supervised learning
  
• reinforcement learning
  
• unsupervised learning
  
• inductive learning - approximate evaluation function
  
• bias
  
• decision trees
  
• training set
  
• test set
  
• Ockham's razor
  
• overfitting
  
• version space
  
• generalization hierarchy
  
• PAC learning
  
• Ockham algorithm <-> PAC-learnable
  
• connectionist learning
  
• linearly separable functions
  
• back-propagation
  
• neural network
  
• epoch
  
• Bayesian learning
  
• Q-learning
  
• reward-to-go
  
• adaptive dynamic programming
  
• bandit problem
  
• input generalization
  
• explanation-based learning
  
• relevance-based learning
  
• knowledge-based inductive learning
  
• memorization
  
• functional dependency
  
• constructive induction algorithms
  
• cumulative learning
  
• VC-dimension - expressive power of a hypothesis space
  
• decision lists
  
• incremental learning*
  
• generalization-to-n problem
  

Types of Learning

• speed-up learing - deductive learning, eg. Explanation-based learning
• learning by taking advice -system can reason about new information added to its knowledge
• learning from examples - inductive learning
• clustering - unsupervised, inductive learning
• learning by analogy - inductive learning in which a system transfer knowledge from one database into a that of a different domain

Inductive Learning

• Decision Trees
  • any Boolean function can be represented as a decision tree.
  • parity or majority function is not appropriate for the diection tree.
  • smaller tree is better according to Ockham's razor.
  • algorithm - in each iteration, choose the attribute that has highest information gain (gains on entropy given on an input).
  • overfitting and diminishing utility - decision tree pruning or cross-validation.
• Information Theory
  • Information Gain
• Inducing General Logical Descriptions
  • Current-Best-Hypothesis Search
    • If it is a false positive -> specialize the hypothesis not to cover it.
    • If it is a false negative -> generalize the hypothesis by adding disjuctions or droppping terms.
    • If no consistent specialization/generalization -> backtrack

• • Least-Commitment Search
    • candidate elimination learning or version space learning algorithm
    • assuming that hypotheses are ordered by more-specific-than ordering (eg. G1 < G2)
    • enormous number of hpotheses -> solution: boundary sets: G-set and S-set.
      • false positive for Si (false inside): Si is too general, throw it out.
      • false negative for Si (false outside): Si is too specific, generalize it.
      • false positive for Gi (false inside): Gi is to general, specify it.
      • false negative for Gi (false outside): Gi is too specific, throw it out.
    • cannot handle noisy data.
  • Computation Compexltiy

PAC Learning

• computational learning theory: how can we justify the accuracy of a hypothesis h with respect to some function f?
• stationarity assumption: the training set and the test are randomly drawn using the same probability distribution
• A hypothesis h is called approximately correct, if error(h) <= e.
• Unfortunately Hbad (a bad hypothesis) may consist with m samples
  • the probability of agreement with m examples is then <= (1-e)^m
  • P( Hbad contains a consistent hypothesis ) <= |H|(1-e)^m <= d confidence parameter
  • Thus, m >= 1/3 (ln(1/d) + ln|H|)
  • the number of examples requried for learning is proportional to the log of the size of hypothesis space
• A space of hypotheses H is PAC-learnable <-> it has finate VC-dimension
  • PAC-learnable classes (The size of Hypothesis space is not the one factor.)
    • Polynomial time: k-CNF, k-DNF, k-DL, Boolean conjuction
    • NP-hard: k-term-DNF and k-3NN (k-term-DNF is proper subset of K-CNF)

Bayesian Learning in Belief Networks

• maximum a posteriori (MAP) hypothesis
• Belief Network Learning Problems
  • know structure, fully observable
  • unknow structure, fully observable
  • known structure, hidden variables
  • unknown structure, hidden variables

Reinforcement Learning

• right action is not told.
• two basic information * utility function: keep a model of the environment * action-value: (Q-learning), model-free approach
• Passive Learning in a Known Environment * Goal: use the reaward information to learn the expected utility of each of the nonterminal states. * Simplifying assumption: the utility of a sequence is the sum of the rewards accumulated in the states of the sequence. * estimation for * U: the utility of each sate * N: how many times each state was seen * M: transition probabilities * Update Methods * Naive Updating: least mean squares (LMS): it slowly converges, because it ignores the fact that the actual utility of a state is the probability-weighted average og its successor's uilities, plus its own reward * Adaptive Dynamic Programming: one step in Markov decision processes * Temporal Difference Learning: Approximate ADP
• Passive Learning in an Unknown Environment
  • ADP approach changes in the unknown environment. Adjustment is required for the changed (firstly known) environment.
• Active Learning in an Unknown Environment
  • active agent must decide what actions to take and how it will affect its rewards

• Learning Action-Value Functions
  • Q-learning is similar to the state-based learning agents.
  • Difference: Q-learning agents do not need models of the world.

Linear Classifier

Boosting

My Personal Preferences

Uncomment preferences variables to activate them (remove the #-sign). Help and details on preferences variables are available in TWikiPreferences.

• Show tool-tip topic info on mouse-over of WikiWord links, on or off:
  • #Set LINKTOOLTIPINFO = off