ch 13&14

Question 1

status of language processing

Answer 1

still rough but good enough

Question 2

who worked on finite automata and expression of grammer

Answer 2

Kleene, Shannon (applying Markov models)

Question 3

automata

Answer 3

construct made of states designed to determine if the input should be accepted or rejected

Question 4

Shannon wrote a paper on

Answer 4

mathematical foundations of communication

Question 5

formal language theory:

Answer 5

parsing and symbolic approach

Question 6

stochastic approach to language

Answer 6

statistical modeling, capturing ambiguity

Question 7

OCR

Answer 7

Optical Character Recognition

Question 8

4 main paradigms of language (1970’s)

Answer 8

stochastic, symbolic, logic-based, and discourse models

Question 9

components of languages pt 1

Answer 9

morphology, (form of words root-derived), syntax (structure), semantics (meaning)

Question 10

components of languages pt 2

Answer 10

parsing (breaking down-prepositional phrase), lexical (alphabet),

Question 11

components of language pt 3

Answer 11

pragmatics (study of uses), ellipsis, (omission of syntactical part of sentence, clear meaning)

Question 12

Chomsky: syntax and grammar rules

Answer 12

necessary but not sufficient

Question 13

Shanks CD systems pt 1

Answer 13

MARGIE (parser, generator, limited in only able to deal with single sentences)

Question 14

CD

Answer 14

conceptual dependency

Question 15

Shanks CD systems pt 2

Answer 15

SAM (extended MARGIE, able to do scripts, read, paraphrase, translate,)

Question 16

Shanks CD systems pt 3

Answer 16

PAM (used text generator, writing in story goals)

Question 17

Shanks CD systems pt 4

Answer 17

CYRUS (combined earlier systems, modeled memories of cyrus vance secretary of state, learn, recognize, guess info)

Question 18

markov model is

Answer 18

a state transition diagram in which each state has a finite set, diff probabilities

Question 19

markov model assumes

Answer 19

transitions depend only on the current state and the input, prior doesn’t matter

Question 20

Penn Treebank Project

Answer 20

collection of annotated sentences, parse tree for each

Question 21

operator schemata

Answer 21

actions/events, variables,

Question 22

precondition list

Answer 22

what must be true or complete before operator can apply

Question 23

progression

Answer 23

initial state of working toward a goal

Question 24

regression

Answer 24

working backwards from initial goal

Question 25

hierarchical planning

Answer 25

prioritizing goals

Question 26

opportunistic planning

Answer 26

exploits conditions and opportunities (short stop, multtitask etc)

Question 27

Conditional planning

Answer 27

just in case planning

Question 28

General Problem Solver

Answer 28

greedy algorithm, minimize distance between state and goal

Question 29

STRIPS

Answer 29

Stanford Research Institute Problem Solver

Question 30

STRIPS

Answer 30

algorithm, similar to greedy, but with first order logic

Question 31

The frame problem

Answer 31

Keeping track of changes, details, contigencies

Question 32

Least Commitment Planning

Answer 32

partial form plans until decision expands constraints,

Question 33

Select-and-Commit

Answer 33

attempts choice then tests info according to, changing if wrong

Question 34

Depth first with backtracking

Answer 34

backtracking, struggles with exponential growth

Question 35

Beam Search

Answer 35

maintains top k searches, always chooses top k of next ones

Question 36

One, then best

Answer 36

assume, then test or decide whether or not to backtrack

Question 37

Dependency directed search

Answer 37

store a listing of decisions or contraints, you can see the affects if one is removed

Question 38

distributed planning

Answer 38

divided problem, allows separate agents to solve