CS 381K: Artificial Intelligence: Lecture Notes


Copyright © 2006 by Gordon S. Novak Jr.

Permission is granted for individuals to make copies of these notes for personal use, or for instructors to make copies for classroom use.

Note: Many of these pages use math symbols such as: &forall &exist . Microsoft Internet Explorer will not display the math symbols, but Netscape or Firefox will.

Contents

8-puzzle 131

a* 61, 65

abduction 225

abstraction spaces 111

add list 205

admissible 65

affix 271

albedo 437

alpha-beta search 104

ambiguity 268, 281, 306

anaphora 269

and node 95

and/or graph 95

answer extraction 199

antecedent 387

aphasia 419

artificial intelligence 2

ask 218

assert 218

assumption-based tms 221

atms 221

atn 297

atom 152

augmented transition network 297

average branching factor 40

axon 414

axon terminal 414

backward 144

backward chaining 156, 216

backward search 71

bayes theorem 377

bayesian network 381

beam search 70

bidirectional search 71

bigram 275

blind search 43

bottom-up parser 295

bound 172

bounded depth-first 44

bounded depth-first search 46

brain anatomy 416

breadth-first 44

breadth-first search 55

brocas area 419

case 308

case frame 272, 311

case relation 309

case theory 308

certainty factor 385

certainty factor combination 390

chaff 171

chain rule 380

chart parser 296

checkers 108

chess 107

chomsky hierarchy 288

chronological backtracking 112

class 236, 246

clause 178

clos 249

closed 56

closed world assumption 222

cnf 162

combinatoric explosion 40

complete 188

compositional semantics 334

conceptual dependency 314

conceptual island 410

conditional probability 377

conflict resolution 374

conjunction 152

conjunctive normal form 162, 178

consistent 153

constraints 116

context free 290

context sensitive 291

context-free 278

convolution 431

counterexamples 99

credit assignment problem 108

criticality number 210

cwa 222

davis-putnam 171

de morgans laws 154

decision tree 398

deduction 225

deduction theorem 163

deep case 308

default 236

definite determiner 320

delete list 205

demon 236, 369

dendral 133

dendrite 414

dependency-directed backtracking 113

depth bound 46

depth-first 34, 44

depth-first search 45

determiner 320

diameter 40

difference 109

differences 109

disambiguation 312

disjunction 152

effective branching factor 67

eight puzzle 131

eliza 329, 330, 331

emycin 367, 368

entail 163, 188

evaluation function 60

evolution 114

facet 236

feature detection 432

finite automaton 289

fire 370

first-order logic 172

fluent 255

fmri scan 420

forward 144

forward chaining 158, 215

frame axiom 204

frame problem 201

frames 17, 230, 234

free 172

frustration 52

game tree 101

genetic algorithms 114

gps 109

grammar 278, 286

grammar notation 285

grammatical ambiguity 268, 282

ground literal 155

herbrand base 180

herbrand universe 180

herbrands theorem 180

heuristic dendral 133

heuristic function 61

heuristic search 61

hidden markov 276

hierarchical planning 209

high-pass filter 430

hill climbing 50

homograph 282

horizon effect 107

horn clause 156, 194

hough transform 433

ida* 69

if-added 236

if-needed 236

if-removed 236

implication 152

inconsistent 153

indefinite determiner 320

induction 225

inference 143, 144

information theory 265

inherit 236

inheritance 246

instance 246

instantiate 207

interpretation 153, 173

invalid 153

isaac 352

isomorphism 141

iterative deepening 47

iterative-deepening 69

joint probability distribution 379

jtms 219

justification-based tms 219

knowledge base 143

knowledge representation 139

knowledge retrieval 139

knowledge source 413

knowledge-based strategy 361

lambert cosine law 437

lambertian 437

language generation 279

lexical ambiguity 268, 282, 306

lexical features 273

lexicon 272

line detection 422

linear planning 209

linear resolution 190, 195

literal 162, 165

local maximum 50

logical consequence 163

low-pass filter 108, 407, 429

ma* 70

machine translation 351

machine vision 427

matching problem 147

max 101

mental rotation 425

message 247

meta-dendral 136

metonymy 269

min 101

minimax 103

model 153

model checking 155

modus ponens 154

monotone 67

monotonic logic 224

morphological analyzer 271

morphology 271

motion vision 439

multiple inheritance 240

n-gram 275

natural deduction 194

natural language 262

negation 152

neuron 414

non-monotonic logic 224

non-terminal 278

nonlinear planning 209

nonterminal symbol 286

object 246

oop 246

open 56

open world assumption 222

operators 25

ops-5 369

or node 95

pandemonium model 369

parsing 280, 293

part of speech 272, 278

pattern matching 83

pet scan 420

phrase structure 286

plan monitoring 211

ply 27, 101

pragmatics 267

precondition 205

predicate calculus 172

preference 313

prefix 271

prenex normal form 175

pretend its english 324

primitive act 314

problem reduction search 93

production 278, 286

production memory 369

production system 369

prolog 223

pronoun reference 318

property list 231

propositional database 213

propositional logic 152

propositional variable 152

ramdom restart 50

reason maintenance 218

reasoning 139

recognize-act cycle 370

recognizer 287

recognizing automaton 287

recursively enumerable 284

reference 320

referent 321

regular language 289

representation hypothesis 140

resolution 160

resolution step 165, 166

retract 218

retrieval 147

rewrite rule 77

rhetorical relation 327

root word 271

rule 365

rule induction 400

rule subsumption 394

rule-based system 365

samuel 108

sat 171

satisfiability 171

script 257, 322

search 21

segmentation 435

selection restriction 311, 312

semantic grammar 331

semantic marker 272, 312

semantic network 17, 230, 233

semantics 267, 269, 304, 328, 334

sensitivity analysis 397

sentence symbol 286

set of support 189

shadow 239

shape from shading 436

simplification 77

simula 246

simulated annealing 51

simulation 141

situated action 261

situation calculus 202

skolem constant 177

skolem function 177

skolemization 177

slot 236

sma* 70

solution graph 97

solution tree 101

somatotopy 417, 426

sombrero function 432

sound 188

specular 437

splitting 194

standard form 178

start symbol 286

state space 25

states 25

static evaluation function 102

static value 103

strips 205

strips operator 205, 207

sublis 183

subproblem 93

substitution 88, 183

successor 56

suffix 271

suffix-stripping 271

super 237

superclass 239

synapse 414

syntactic ambiguity 306

syntax 267

table of connections 109

terminal 278

terminal symbol 286

tms 218, 220, 221

token 275, 325

top-down filtering 294

top-down parser 294

transposition table 105

truth maintenance 218, 220

truth table 155

two-pointer method 189

type 275

unification 184

unification algorithm 186

uniform-cost search 57

unigram 275

unit preference 190

unsatisfiable 153

valid 153

visual cortex 422

vocabulary 286

walksat 171

waltz filtering 116

wernickes area 419

working memory 369

zipfs law 266


CS 381K