A* algorithm (pronounced ``A-star'') an algorithm for heuristic search, using an admissible heuristic function f(n) = g(n) + h(n), where g(n) is the known cost to reach node n from the start, and h(n) is the estimated cost from node n to a goal. A* is guaranteed to find a minimum-cost solution if one exists and examines the fewest possible nodes.
abduction inference in which the result of a causal relationship is taken to imply the cause: given P &rarr Q , if Q is known, infer P . While not logically valid, this kind of reasoning is involved in areas such as medical diagnosis, in which a disease is inferred from the symptoms it causes.
active image in a frame system or object-oriented system, a connection between a data value and a displayed image, such that the image reflects the value of the data as the program runs, and in some cases such that changes made interactively to the displayed image cause corresponding changes to the data.
active value in a frame system or object-oriented system, a means of associating procedures with a data value such that the procedures will be called when the data is accessed or written.
add list A list of facts to be added to the world model after application of a STRIPS operator.
adjective a word that modifies a noun, e.g. big or red.
admissible describes a heuristic function that does not over-estimate the cost of reaching a goal from a given state. cf. A* algorithm.
afferent of a neuron, carrying signals toward the brain: input.
AFSTN augmented finite state transition network. See augmented transition network.
agent a program that acts independently, perhaps on a different computer, to attempt to accomplish a goal for a user or other program.
agreement correct matching between words or phrases. In Mary loves her cat. there is gender agreement between Mary and her, and there is number agreement between Mary and loves ( * Mary love her cat. would be wrong).
AKO a kind of. See is-a link.
algebraic simplification reduction of a mathematical formula to a simpler form by the application of algebraic laws.
alist association list.
alpha and beta cutoffs in alpha/beta search, threshold values that allow un-promising avenues of play to be identified and eliminated from the search.
alpha/beta search a kind of game tree search that uses alpha and beta cutoffs to avoid unnecessary search of un-promising avenues of play.
ambiguity in understanding natural language, images, or other inputs, the superficial possibility of interpreting an input in more than one way.
anaphor (plural is anaphora) a word that refers to another word in a sentence, such as a pronoun.
AND node a node in an AND/OR graph that is true (or satisfied) if all of its successors are true.
AND/OR graph a graph or tree structure describing the decomposition of a goal in terms of alternative subgoals (OR nodes) or combinations of subgoals that must all be satisfied (AND nodes).
answer extraction a technique for extracting a desired answer from a resolution proof by introducing an artificial answer predicate that serves to carry the variable bindings of the solution.
answer literal an artificial literal that serves to carry the variable bindings in a resolution proof to allow answer extraction. While the prover will return True if it proves a question (e.g., ``does there exist an x such that ...''), the desired answer may be the value of x that makes the statement true.
antecedent the left-hand side of an implication or rule; e.g., in the rule P &rarr Q , P is the antecedent.
antecedent method if-added method.
antecedent reasoning forward chaining.
antonym a word that means the opposite of another word.
AO* algorithm (pronounced ``A-O-star'') an algorithm similar to A* for heuristic search of an AND/OR graph.
arc consistency in Waltz filtering, a requirement that the labels of two graph nodes that are connected by a constraint arc must be consistent with a single label for the arc.
arity the number of arguments of a function.
assert to add a fact to the database of currently believed facts; this could trigger forward chaining.
assertion a logical expression in the database of true or currently believed facts.
association list in Lisp, a list composed of pairs of a symbolic name and associated value, used to represent variable bindings, substitutions, and data sets.
associationist theory of memory the theory that human memory is organized in terms of concepts that are related by associational links. cf. spreading activation.
ATMS assumption-based truth maintenance system. See truth maintenance.
ATN augmented transition network.
atom 1. in propositional or predicate calculus, a predicate symbol with the appropriate number of arguments. For example, MORTAL(Socrates) is an atom, where MORTAL is the predicate and Socrates is a constant term that is its argument. Also, atomic formula. 2. in Lisp, any data that is not a cons cell, such as a symbol or a number.
atom set see Herbrand base.
augmented transition network (ATN) a formalism for describing parsers, especially for natural language. Similar to a finite automaton, but augmented in that arbitrary tests may be attached to transition arcs, subgrammars may be called recursively, and structure-building actions may be executed as an arc is traversed.
automated reasoning the derivation of conclusions from observed or given data, often by a proof procedure operating on the data and a set of axioms.
auxiliary verb and extra verb that modifies a main verb, e.g. will, have, been.
average branching factor the ``average'' number of possible alternatives from any given state in a search tree.
axiom in theorem proving, an initially given fact, rule, or theorem.
axon a long fiber projecting from a neuron and carrying an output signal.
back propagation the adjustment of the weights of connections in a neural network, using reward and punishment based on training data for which the desired outcome is known, so that the output of the network will eventually approximate the desired output.
backed-up value in a game tree search, the value of a position as determined by starting with approximate evaluations of positions at terminal nodes of the tree (given by a static evaluation function), then calculating the values of higher nodes by assuming that each player will select the most advantageous of the available moves at each point.
backprop back propagation.
backquote in Lisp, a character macro, specified by the backward-quote or accent-grave symbol, that allows a symbolic structure of specified form to be created, with values substituted in certain positions.
backward chaining a proof that starts with the conclusion and searches for rules or facts that support the conclusions, recursively.
backward search a search that starts from the goal and searches for actions that could achieve that goal, recursively.
base-level activity activity that works directly on the problem, as opposed to meta-level activity (``management'').
base-metalevel tradeoff the tradeoff between base-level activity (``work'', e.g. search) and meta=level activity (``management'', e.g. deciding whether to continue a search that has taken a long time).
beam search a search method that maintains a predetermined number of the best search paths found thus far at any given point. Thus, it considers more possibilities than depth-first search, but avoids the exponential number of possibilities of breadth-first search.
belief function a function that determines how strongly an uncertain conclusion is believed. cf. certainty factor.
best-first search a search in which the next fringe node to be expanded is the node that is estimated to be the best according to an evaluation function. If the evaluation function f(n) is appropriately chosen, this becomes A*.
bidirectional search search that is done both from the start toward the goal and from the goal back toward the start, until the fringes of the two searches intersect. This can take much less time (2 * bd/2 < < bd) but can require a lot of storage.
bigram a sequence of two words.
blind search a search in which no heuristic information is available to distinguish one search path from another, so that exhaustive examination of possibilities must be done.
blocks world a microworld used in early A.I. research, involving the perception, manipulation, or planning for manipulation of toy blocks on a table.
Boolean satisifiability a problem expressed as a CNF conjunction of disjunctions of propositional variables, in which the goal is to find a set of assignments of True or False to each variable that will make the whole formula True, if such an assignment exists.
bottom-up a form of parsing in which structure is built from the bottom (words) up to phrases and sentences.
bound occurrence in a predicate calculus formula, an occurrence of a variable within the scope of a quantifier ( &forall or &exist ) of that variable.
bounded depth-first search a depth-first search in which a bound is placed on the number of operator applications that can be considered; any sequence of operations that exceeds the depth bound is considered a failure.
box in logic or resolution theorem proving, the empty clause; from its mathematical symbol, □ .
branching factor in a search tree, the number of children of a given node. Usually, the branching factors of individual nodes will vary.
breadth-first a search strategy in which all nodes at a given depth are examined before any deeper nodes are examined.
break in Lisp, the halting of execution due to occurrence of an error. It is possible to examine the conditions that caused the error, and possibly to modify the program and continue from the broken state.
canonical form a convention for representing a symbolic expression that allows easier manipulation of such expressions.
car in Lisp, the function that extracts the first half of a cons cell, usually containing a value that is an element of a list.
case see case relation.
case-based reasoning reasoning based on similarity of a given set of data to a known case stored in a library, as in the use of legal precedents.
case frame in natural language processing, a lexical entry that specifies a single sense meaning of a verb, together with information about related phrases such as case relation slots, selection restrictions on the phrases that can fill the slots, prepositions that are used for each case, etc.
case relation a relation between a verb and a phrase related to it, such as agent (subject), patient (object), etc. cf. surface case, deep case.
cdr (pronounced ``could-er'') 1. in Lisp, the function that extracts the second half of a cons cell, usually pointing to the remainder of a list following the first element. 2. to move down a list of elements by taking successive cdr's.
cdr coding a method of reducing the amount of storage required for a cons cell, taking advantage of the fact that the next cell is usually located close to its predecessor in memory.
CF certainty factor.
certainty factor a numeric measure of the degree of belief in a proposition. In EMYCIN, the CF ranges from -1 (false) to 1 (true).
character macro in Lisp, a macro that is invoked by a single character in the source code.
chart parser a parser in which a triangular array is built in which each cell contains an entry for each phrase beginning at that column and spanning the diagonal downward from the cell.
Chomsky hierarchy a hierarchy of language types defined by Chomsky: Type 0 (no restrictions) is the highest class, containing Type 1 (context sensitive), Type 2 (context free), and Type 3 (regular).
chronological backtracking in a tree search, a form of backtracking in which decisions that led to a failure are retracted or modified in the reverse of the order in which they were made, so that the most recently made decision in the current search tree is modified first. cf. dependency-directed backtracking.
chunk a hypothesized unit of human knowledge, such as a rule, pattern, or concept.
chunking a form of learning by forming a new chunk, whose components are existing chunks.
Church-Turing Thesis the thesis that computers can perform any effectively specified symbolic process.
circumscription a form of non-monotonic reasoning based on making explicit the assumption that the explicitly provided information is the only important information about a situation, and that is safe to assume that unmentioned things may be assumed to be as usual.
class in a frame system or in object-oriented programming, a representation of data and methods that are shared by individual instances of the class and its subclasses.
clause in resolution theorem proving, a logical formula consisting of a disjunction of literals that is treated as a unit.
CLIPS a widely used forward-chaining expert system shell developed at NASA.
CLOS Common Lisp Object System, a standardized object-oriented programming system that is part of Common Lisp.
closed list in A* search, a list of nodes that have been examined and no longer will be considered further (unless a cheaper path to such a node is found later).
closed world assumption (CWA) in a theorem prover, logic programming language, or database system, the convention that if a question cannot be proved to be true, it may be assumed to be false. cf. open world assumption.
closure in Lisp, the combination of a function definition and a binding environment; can be used in constructing generators or coroutines.
CNF conjunctive normal form.
cognitive science study of human and animal cognition, making use of the insights provided by AI and neuroscience as well as psychology, linguistics, and philosophy.
combinatoric explosion the rapid growth of the number of possibilities to be explored in a search, often exponential because it is the product of the number of possible choices at each level of the search tree.
Common Lisp a large, standardized dialect of Lisp.
common-sense reasoning the ability to reason about a new and unforeseen situation using a person's accumulated knowledge of the world.
competence the speaker-hearer's knowledge of his language [Chomsky]. cf. performance.
compiled knowledge knowledge, of humans or machines, that is analogous to a compiled procedure: it can be executed, but its internal structure cannot easily be examined or understood.
complete of a theorem prover, able to (eventually) prove any true theorem. More generally, able to solve any problem in a specified class.
compositional semantics a semantics in which the meaning of a phrase is composed from the meanings of its components.
concept learning a form of learning in which example data sets and classifications of the examples are given, and in which the goal of learning is to form a description of the concept implied by the examples.
conceptual dependency a theory in which the meanings of natural language sentences are represented using a small number of primitive acts that are related to other primitive acts and phrases of the sentence by deep case relations.
conflict set in a forward-chained production system, the set of potential rule firings, i.e., the set of all rules whose antecedents are satisfied by some combination of working memory elements together with the bindings of variables to those elements. cf. conflict resolution.
conjunction a compound logical statement using the AND operator: true iff all of its components are true.
conjunctive normal form (CNF) a canonical form of writing predicate calculus formulas as a conjunction (AND) of clauses (disjunction (OR) of literals); used in resolution theorem proving.
cons 1. in Lisp, the function that constructs a dotted pair or basic element of list structure. 2. to make a data structure. 3. a cons cell.
cons cell the basic record from which list structures are constructed in Lisp, consisting of two pointers; it is constructed by cons, and the pointers are extracted by car and cdr.
consequent the right-hand side of an implication or rule; e.g., in the rule P &rarr Q , Q is the consequent.
consequent method if-needed method.
consequent reasoning backward chaining.
consistent of a logical formula, true under some interpretation.
constant in mathematical logic, a particular or abstract term that represents an individual. A constant can be considered to be a function of no arguments.
constituent a group of consecutive words in natural language that make up a unit, e.g. the old man would be a constituent (a noun phrase).
constraint 1. a condition that must always be true or that must be true of any valid solution to a problem. 2. a rule, formula, axiom, or program that expresses a constraint.
constraint-based reasoning problem solving based on reasoning about given constraints and propagating constraints to narrow the range of possible solutions.
constraint network a representation of a constraint satisfaction problem in which nodes represent variables and arcs represent that a constraint connects variables.
constraint posting storing a symbolic constraint in a location where other processes working on the same problem can examine it.
constraint propagation a form of reasoning, using a network of related facts, in which a value or range of possible values determined for one variable constrains the possible values of variables to which it is related. When the range of possible values of a variable is narrowed, the constraints may allow the ranges of related variables to be narrowed, eventually resulting in consistent values or value sets for all variables in the network.
constraint satisfaction problem (CSP) a type of problem in which the goal is to find values for a set of variables that will satisfy a given set of constraints.
constraint violation a situation in which a constraint is not true.
context free a grammar in which the left-hand side of each production rule is a single nonterminal; thus, there is no context around this nonterminal.
context sensitive a grammar in which the left-hand side of each production rule has a length that is less than or equal to the length of the right-hand side. There may be some symbols (context) around the nonterminal on the left-hand side.
continuous speech normal human speech, without silent pauses between words; this makes machine understanding much more difficult.
control structure the method by which a program or problem solving system determines what task to perform next.
credit assignment problem the problem of determining which rule, heuristic, or procedure should receive credit (or blame) when a game-playing or decision-making program succeeds (or fails).
CSP constraint satisfaction problem.
CWA closed world assumption.
data-driven search a search in which arrival of data causes conclusions to be drawn, which cause further conclusions, and so forth: forward chaining.
decidable of a theorem proving or decision making task, able to be decided one way or the other (e.g., proved or disproved) within a finite time bound that can be determined from the size of the input problem. cf. undecidable.
decision tree see discrimination network.
declarative representation a form of knowledge representation in terms of formulas, data structures, or rules of a restricted form, as opposed to a procedural representation.
declarativism the view that knowledge should be represented declaratively (e.g. as axioms or rules) rather than procedurally (as executable programs).
deduction the process of deriving new facts or theorems from known facts and axioms.
deduction tree a data structure, in the form of a tree or directed acyclic graph, that shows the facts, axioms, and intermediate conclusions from which a conclusion was derived.
deep case the semantic case relation between a verb and a related phrase, e.g., in ``mother baked'' and ``the pie baked'' both ``mother'' and ``pie'' are in the subject surface case, but ``mother'' is in agent deep case, while ``pie'' is in patient deep case. cf. surface case.
deep structure in Chomsky's theory of transformational grammar, a representation of the meaning of a sentence that can be transformed into a surface structure or actual sentence; e.g., ``John hit the ball'' and ``The ball was hit by John'' have different surface structures but the same deep structure. More generally, a representation of the meaning of a sentence that contains less syntactic detail and more semantic detail than the surface representation or parse tree.
default reasoning reasoning based on things that are usually, but not necessarily, true; e.g. most people can drive a car.
default value in a frame system, a slot value that is stored in a class and inherited by instances of the class for which no value for that slot is defined.
definite determiner a determiner that specifies a particular referent, such as the, one, this.
definite reference in natural language, a phrase that refers to a particular object, e.g., a noun phrase using a determiner such as the, one, or that. cf. indefinite reference.
defun 1. in Lisp, the function that is used to define a new function. 2. a function definition.
delete list a set of facts to be deleted from the world model when a STRIPS operator is applied.
demon 1. a procedure that is activated automatically when a certain condition occurs, such as an if-added method. 2. see pandemonium model.
Dempster-Shafer theory a theory of reasoning under uncertainty in which probability is assigned to subsets of the universe of possible outcomes rather than only to individual outcomes.
DENDRAL an early AI program that determined molecular structure of organic compounds given mass spectrometer data.
dendrite a tree-like branched structure on a neuron that receives inputs from other neurons.
dependency-directed backtracking a kind of search in which the action taken when a failure (e.g. a contradiction) is reached is to use dependency information to modify one of the decisions that led to the failure, as opposed to chronological backtracking (modifying the last decision).
depth the number of operator applications between the root of a search tree and a given node.
depth bound the maximum depth that is permitted in a bounded depth-first search.
depth-first a search in which children of a node are considered (recursively) before siblings are considered.
derives formula f derives a formula g, written f ⊢p g, iff a prover p can derive g given that f is true.
destructive operation in Lisp, an operation that replaces values in existing list structure, which may change the values of other variables due to shared use of the same structure.
determiner an article that begins a noun phrase, such as a, an, the, one.
diagnosis 1. a finite classification problem involving a predetermined set of possible diseases or malfunctions. 2. a problem in which a representation of the structure and normal operation of a mechanism is used, together with observed behavior of the mechanism, to determine what component failure(s) could account for the observed behavior.
diameter the maximum number of steps between any two states in a search space.
difference in GPS, a representation of a difference between the current state of the search and the goal, used to guide action to reduce the difference.
disagreement set in unification, the set of terms in a particular argument position that have different values.
disambiguate to resolve a situation in which there are multiple possibilities, often by using an additional kind of knowledge to eliminate some possibilities.
disambiguating rules rules used to make decisions that would otherwise be ambiguous, e.g., rules to resolve syntactic ambiguity in a natural language sentence by applying semantic constraints.
discrimination network a method for classifying a given data set into one of a fixed set of categories. At each interior node of the tree, a data attribute is compared to several possible values or ranges, and the matching branch is taken; leaf nodes are labeled with classifications. Also, discrimination net, decision tree.
disjunction a compound logical statement using the OR operator: true iff any of its components is true.
disjunctive normal form (DNF) a canonical form of writing predicate calculus formulae as a disjunction of conjuncts.
disparity in a binocular vision system, the displacement of a pixel between the two images due to the difference in point of observation.
DNF disjunctive normal form.
domain expert a human expert in a particular area who provides the knowledge that is the basis for an expert system.
dotted pair see cons cell.
EBL explanation-based learning.
edge detector in natural or machine vision systems, a neuron or operator that responds to the abrupt change in stimulus across a (locally) straight edge between two regions of approximately uniform intensity or color.
effective branching factor the average branching factor in terms of nodes that are actually examined using a given heuristic. A good heuristic will achieve a low effective branching factor (ideally near 1).
efferent of a neuron, carrying signals away from the brain: output.
elision omission of some words in a natural language statement, e.g. He gave John cookies and [he gave] Mary candy. The second set of words he gave may be elided.
ELIZA a program by Joseph Weizenbaum that simulated a Rogerian psychotherapist.
embedded language a programming or problem-oriented language that is implemented within another language, such as an expert system shell implemented within Lisp.
empty clause in resolution theorem proving, a clause that contains no literals and thus represents the value False or contradiction; the goal of the theorem proving process. Traditionally called ``box''.
endorsement a symbolically represented justification for belief or disbelief in a proposition.
entail a formula f entails a formula g, written f ⊨ g, iff in any interpretation in which f is true, g is true.
eval in Lisp, the function that performs evaluation of a specified expression, allowing code that is constructed as a runtime data structure to be executed directly.
evaluation 1. in Lisp, the process of determining the value of a symbol, number, or function applied to arguments. 2. the process of determining the estimated value of a state during a search process. 3. in logic, the process of determining the value of a formula given an interpretation.
excitatory describes a connection between neurons that excites (makes more likely to fire) the target neuron.
exhaustive search a search that examines all possibilities; usually not feasible due to combinatoric explosion.
expand a node in a search, the process of computing the set of successors of a given node.
explanation a justification of a conclusion in terms of the facts and rules that led to it.
explanation-based learning a kind of machine learning in which the result of learning from a new example is a general rule that explains the basis for the classification of the example.
expressiveness the ability of a knowledge representation formalism to express the features important for representing a problem domain.
extension the actual object(s) denoted by a description, or the enumeration of the members of a set. cf. intension.
facet a named component of a slot in a frame, e.g. a value facet, if-needed facet, data type facet.
factor to break a problem into relatively independent subproblems.
false under an interpretation of a logical formula, evaluating to the value False for a particular interpretation.
falsify to cause a logical formula to have the value False.
finite automaton an automaton (abstract computer) that is organized as a transition network, where transitions between nodes are labeled by input symbols.
finite classification a kind of expert system task in which the goal is to classify a given case as one of a prespecified set of possibilities, e.g. diagnosing a disease or identifying an aircraft.
fire (1) to execute a rule whose antecedent is satisfied by adding its consequent, with appropriate variable substitutions, to the database of facts, or by executing a procedure associated with the rule. (2) of a neuron, to send an electrical pulse down the axon, causing release of neurotransmitters at synapses at the end of the axon.
first-order logic see predicate calculus.
first-order predicate calculus see predicate calculus.
flavors an object-oriented programming system furnished by some Lisp dialects.
fluent a predicate whose value may change over time, e.g. AT(object, position, s)
FOL first-order logic.
FOPC first-order predicate calculus.
forward chaining a process of reasoning in which known facts and rules are used to deduce additional facts, which are added to the database; e.g., given the formula A &and B &rarr C , if A and B are true, C could be deduced and added as a new fact. cf. backward chaining.
forward search search that begins in the initial state and applies operators to derive new states in an attempt to reach a goal state.
fragile of a program or reasoning technique, easily broken, or failing to work unless all of the inputs are exactly right. cf. robust.
frame a representation of an object, with slots that represent properties of the object or connections to other frames, and pointers to super-classes from which the fram may inherit information.
frame problem the problem of efficiently maintaining a correct and consistent world model as some aspects of the world are changed by operators (but most aspects remain the same).
free variable 1. in a logical formula, an occurrence of a variable that is not within the scope of a quantifier. 2. in Lisp, a variable that is not bound within a function in which it appears.
fringe in a search, the set of nodes, being expanded out from the start state towards the goal, that have been generated but not yet examined.
function 1. in Lisp, a procedure that returns a value. 2. in mathematical logic, a function from terms to terms.
fuzzy set theory a variant of set theory in which set membership is not all-or-nothing, but is represented by a numeric degree of membership in the range 0 to 1. Related techniques are sometimes used in expert systems for estimating the degree of certainty of conclusions.
game playing development of computer programs to play games, such as chess.
game tree a search tree for a game, in which a node represents a game state and arcs represent moves by a player leading to new states.
garbage memory space that has become unused because there are no pointers to it.
garbage collection the process of identifying unused memory and collecting it so that it can be recycled.
garden path sentence a sentence that is misleading to a reader because the initially ``obvious'' parsing is incorrect, e.g. ``The old man the boats.''
gender the gender (masculine, feminine, or neuter) of a word or phrase in natural language, e.g. her has feminine gender.
gender agreement matching in gender between words in a natural language statement, e.g. in Mary lost her book. the words Mary and her agree in gender.
generalization given a particular instance or data set, to represent a more general case that includes the instance.
generation the production of a statement in a language given a grammar of the language and a representation of the meaning that is to be conveyed.
generator a program that generates natural language statements, e.g. from a meaning representation.
genetic algorithm a class of algorithms that attempt to solve a problem by an evolution-like process. A set of candidate solutions is evaluated in terms of quality of solution; those candidates that are better are allowed to reproduce, sometimes with mutations. If one candidate comes to dominate the population, it is selected as the best solution. In some versions, different candidates are combined as in sexual reproduction.
gensym 1. in Lisp, a function that generates a new symbol at runtime. 2. a symbol so generated.
goal 1. something that is to be achieved by a program. 2. a representation in a formal language or data structure of the goal or of a set of conditions that, if satisfied, will accomplish the goal.
goal state a state of a search that represents or satisfies the goal.
GPS General Problem Solver, an early program for state space search in several application domains.
grammar a specification of a formal language in terms of a set of productions that transform nonterminal symbols (phrase names) into strings of other nonterminal symbols and/or terminal symbols (words or characters).
ground instance a logical formula containing no variables, or in which constants or functions of constants have been substituted for all variables.
ground substitution a substitution of constants or functions of constants for variables.
Herbrand base the set of all predicates whose arguments are taken from the Herbrand universe; also, atom set.
Herbrand universe in mathematical logic, a recursively defined set of terms, in which the first level is the set of all constant symbols and each subsequent level includes all functions applied to terms in the previous level.
Heuristic DENDRAL see DENDRAL.
heuristic function a function that estimates the value of a state, e.g. the remaining cost to reach a goal from a state, in a search.
heuristic knowledge knowledge of approaches that are likely to work or of properties that are likely to be true (but not guaranteed).
heuristic search the A* algorithm for search using an admissible heuristic function.
hidden units or hidden layer in a neural network, a layer of artificial neurons between the layer connected to inputs and the layer connected to outputs; it may not be clear to a human observer what the individual units in this layer represent.
hierarchical planning a form of planning in which a task is decomposed into subtasks, which are likewise decomposed, until primitive actions are reached.
high-pass filter a filter that lets high frequencies pass through and blocks low frequencies. In vision processing a high-pass filter emphasizes change and amplifies noise. Differentiation is a high-pass operation.
hill climbing a form of search in which the path of steepest ascent towards the goal is taken at each step. It is excellent if the domain is well-behaved, but can get stuck on local maxima or mesas.
histogram a way of summarizing a set of data by sorting the data items into bins and counting the number of samples that fall into each bin.
holonym name of a whole of which a meronym names a part.
homographs words or symbols whose written form is the same but whose meanings are different, e.g. bit may mean ``binary digit'' or the past tense of the verb ``bite''.
homonym one of two or more words that are spelled and pronounced the same but have different meanings.
homophones words whose sound is the same but whose meanings are different, e.g. to, too, and two.
horizon effect the tendency of a search procedure, such as a game-playing program, to make innocuous moves that have the effect of postponing bad news so that it lies beyond the horizon formed by the depth bound of the search.
Horn clause a logical formula that is a disjunction (OR) of literals and has at most one positive literal. Viewed as a rule, a Horn clause is a rule from a conjunction (AND) of positive literals to a single positive conclusion literal.
Hough transform an algorithm for identifying desired objects (e.g. straight lines) in image data by mapping each input point (from an edge detector) to all possible objects that is could be part of, and incrementing histogram counters for each such object. After the whole input image has been processed, histogram counters with high counts identify objects.
hypernym a word that generalizes another word, e.g. tool is a hypernym of hammer.
hyponym a word that is a specialization of another word, e.g. hammer is a hyponym of tool.
IDA* Iterative Deepening A*, a depth-first variant of the A* algorithm. A depth-first search is performed, in which any node whose cost exceeds a threshold is failed; if the search fails, the threshold is increased to the minimum cost above threshold, and the search is repeated.
ID3 an algorithm for learning a decision tree from a set of training examples with known classifications.
if-added method in a frame system, a procedure that is called automatically when a new value is stored into a slot; can be used as a demon to perform monitoring, display information, or propagate activity to related frames.
if-needed method in a frame system, a procedure that is called automatically to compute the value of a slot; e.g., an if-needed method could compute age from birth-date and the current date.
if-removed method in a frame system, a procedure that is called automatically when a value is removed from a slot.
in in a truth maintenance system, describes a proposition that is currently believed or supported. cf. out.
inconsistent of a logical formula, false under every interpretation.
indefinite determiner a word such as a or an.
indefinite reference in natural language, a phrase that refers to an unspecified object, e.g., a noun phrase using an indefinite determiner such as a. cf. definite reference.
independent subgoals subgoals whose solutions do not interact. For example, in theorem proving, proof of a lemma cannot hurt the proof of another lemma; but in shopping with a total cost constraint, buying an expensive item can make it impossible to buy another needed item, so these subgoals are not independent.
induction inference of a rule that explains a body of data. For example, given P(a), P(b), P(c), Q(a), Q(b), Q(c), Q(d), infer &forall x P(x) &rarr Q(x). Induction is not logically valid, but is the basis of learning and concept formation.
inductive bias in a machine learning system, the effect of the data that are examined and the representation of learned information on the result of the learning process.
inference rule a rule that allows derivation of additional true statements from a given set of true statements.
informed describes the quality of information provided by a heuristic: a heuristic that gives more accurate estimates is called more informed.
inheritance in a frame system, to infer information about an object from the same information in a superclass of that object, e.g. a dog may inherit information from mammal.
inhibitory describes a connection between neurons that inhibits (makes less likely to fire) the target neuron.
input layer the first layer in a neural net, composed of artificial neurons that receive inputs and combine them.
instance in a frame system or object-oriented system, a frame or object that represents an individual that is an instance of a particular class.
instance variables in a frame system or object-oriented system, the data values stored in an instance.
instantiate to make an instance of a pattern, rule, or frame by substituting particular facts for variables in a pattern.
intension an abstract description of something, as distinguished from the extension, which is the thing described. For example, ``John wants to own the fastest car in town'' is an intensional description of what John wants. Assuming that Bill owns the fastest car in town, it does not mean that John wants Bill's car (the extension).
interpreted knowledge knowledge that is analogous to an interpreted procedure: it can be executed, but it is also possible to examine it or reason about it. cf. compiled knowledge.
interpretation in mathematical logic, an assignment of a universe of possible objects for terms, of particular objects for constants, of the meanings of functions from terms to terms, and of the truth values of predicates applied to terms.
invalid of a logical formula, false under some interpretation.
invoke to cause a procedure to be executed and applied to a given problem or data.
is-a link in a frame system or semantic network, a link between an instance and its class (e.g., Fido is-a Dog) or between a class and its superclass (e.g., Dog is-a Mammal). Also, ISA, AKO (a kind of).
iterative deepening a search method in which a depth-first search is done with a fixed depth bound; if no solution is found, the depth bound is increased by one and the process is repeated.
ith-level constant set the set of constants (and functions of constants) at the ith level of construction of the Herbrand universe.
key operator an operator that can be determined a priori to be necessary in a search or planning task.
Kleene star an asterisk written after a grammar element to indicate zero or more repetitions of that element.
KL-ONE a frame-like representation language that allows a new concept to be classified within a hierarchy where it best fits.
knowbot a knowledge-based agent that attempts to accomplish a goal for a user, e.g. to find desired materials in a remote library.
knowledge acquisition the process of collecting the knowledge for an expert system from a human domain expert and formalizing it.
knowledge acquisition bottleneck the notion that knowledge acquisition is the major impediment and most time-consuming part of development of an expert system.
knowledge base the collection of knowledge of an expert system, including facts, rules, heuristics, and procedures.
knowledge engineer a person who develops an expert system by gathering knowledge of the domain from human experts and other sources, organizing the knowledge, choosing appropriate software tools, codifying the knowledge in machine-processable form, and verifying the quality of the result.
knowledge source 1. a kind of information about a problem that can be used to help solve it. 2. in a blackboard system, a procedure or set of rules (a small expert system for a part of the problem) that is triggered by addition of data to the blackboard and examines that data, adding its own conclusions to the blackboard or taking other action.
lambda expression in Lisp, a way of specifying an unnamed function as a list whose first element is the symbol lambda, followed by arguments and code.
Lambertian describes a surface whose reflectance is ``flat'', i.e. uniform in all directions. cf. specular.
learning by analogy a form of machine learning that attempts to understand a new domain more rapidly by making analogies with a domain that is already understood.
least commitment strategy a search strategy of deferring, as long as possible, a commitment to a particular choice. Instead, constraints on possible values are posted and propagated; when a variable is fully constrained, a choice is made. This can significantly reduce search and backup for some problems.
lemma the form of a word found in a lexicon.
lemmatizer a program that converts a word into its root word and affixes: running -> run + ing.
level-saturation method two-pointer method.
lexical in natural language processing, referring to information contained in the lexicon.
lexical ambiguity in natural language, ambiguity caused by multiple definitions or parts of speech of words.
lexicon in a natural language processing system, a table of words with their parts of speech, root words, relationships to other words or phrases, semantic features, definitions in machine-processable form, etc.
linear planning planning in a domain in which subgoals are independent; the subgoals can therefore be accomplished in any order.
linear resolution a form of resolution in which one of the two clauses resolved is the result of the previous resolution step.
Lisp interpreter 1. a procedure that can evaluate a Lisp expression at runtime to determine its value: the eval function. 2. the user interface of Lisp, which reads an expression input by the user, evaluates it, and prints the result. Also, read-eval-print loop.
list in Lisp, a linked-list structure, composed of cons cells, whose external representation is the elements of the list enclosed in parentheses.
literal in a logical formula, a predicate or the negation of a predicate.
literals resolved upon in performing resolution, the two literals of opposite sign (one from each clause) that are unified and then removed in forming the result clause.
local maximum in a hill-climbing search, a point that is higher than its neighbors, but may not be the global maximum.
logic programming a form of programming, as in PROLOG, in which programs take the form of logical statements, usually as Horn clauses, and the solution to a desired problem is found by a backchaining search using the database of facts and the logical axioms.
Logic Theorist one of the earliest AI programs, by Newell and Simon, which proved theorems in set theory from Principia Mathematica.
logical consequence a logical formula Q is a logical consequence of a formula P iff in any interpretation in which P is true, Q is also true. Written P &rarr Q (`` P implies Q '').
low-pass filter a filter that allows low frequencies to pass through, while blocking high frequencies. A low-pass filter reduces noise, blurs detail, and introduces delay in the time domain. Low-pass operations include summation, integration, and averaging.
machine learning study of ways by which a program can automatically modify its knowledge and procedures to improve its performance, based on explicit instruction from a human teacher, training examples, its experiences, or experiments generated by the program.
machine translation automatic translation from one natural language to another, e.g., translation of German to English.
macro in Lisp, a special form of procedure that is called in the same manner as a function, but that produces as its output Lisp code; this code is compiled or executed to accomplish the result of the macro call.
macro operator a large-scale operator that is composed of multiple smaller operators.
MACSYMA an early program for symbolic algebraic manipulation by computer.
mapping function in Lisp, a function that applies a specified function to each element of a list.
matching problem the problem of determining what parts of a program's knowledge are relevant to a given task or real-world situation.
Mathematica a widely used program for symbolic algebraic manipulation by computer.
matrix the quantifier-free portion of a predicate calculus formula that has all the quantifiers at the front.
McCullough-Pitts neuron an artificial neuron that produces an output of 1 if the weighted sum of its inputs exceeds a threshold; otherwise its output is 0.
means-ends analysis in GPS, the connection of goals (ends) with operators (means) that might accomplish those goals, using the table of connections.
message in object-oriented programming, an indirect procedure call; the procedure that is called depends on the class of the object to which the message is sent.
metaknowledge knowledge about knowledge, e.g. knowledge about what kinds of things are known or about the form of knowledge.
method a procedure for performing a specific function; especially, the procedure that implements the response to a message in an object-oriented or frame system.
meronym name of a part, member, or substance of a whole (the holonym).
metonymy use of a term associated with something to refer to that thing, as in The White House denied the report. The term White House is a metonym for executive branch of the U.S. government.
MGU most general unifier.
microworld a small, restricted, artificial model of the world used for initial development or testing of AI techniques or programs.
minimax 1. an algorithm for determining the backed-up value of a node in a game tree from the values of child nodes one move below: if it is the player's move, the maximum of the values below is taken; if the opponent's move, the minimum. 2. to perform a search in a game tree, using the minimax algorithm to determine the best move.
modal auxiliary an auxiliary verb such as should, would, could, and might.
model an interpretation under which a given logical formula is true.
model checking a form of proof in which a theorem is proved by checking whether it is true in all possible models. The set of possible models may be huge, but the proof may be reduced to propositional calculus (since models involve constants).
modus ponens a rule of logical inference: if P is true and P &rarr Q , conclude Q .
mood property of a verb form that expresses whether the action it denotes is a fact ( he went ...) or not ( if he had gone ..., subjunctive mood).
monosemous of a word, having a single meaning in a syntactic category.
morphological analysis in natural language processing, the process of removing affixes and reducing words to root words and affixes, e.g., running becomes run + ing.
morphology study of the forms that natural language words can take, e.g by addition of suffixes.
most general unifier a unifier of a set of literals such that any other unifier can be derived from it by substituting terms for its variables. Abbreviated MGU.
motor describes a neuron that controls a muscle.
move generator in a search, a procedure that enumerates the possible moves or operator applications from a given state, e.g., all the legal moves from a given chess position.
multiple inheritance inheritance of properties from more than one parent class in a frame system or object-oriented system.
natural language a human language, such as English, German, Hindi, Mandarin Chinese.
natural language processing (NLP) computer processing of speech or machine-readable text in a natural language; includes machine translation, natural language understanding, content extraction, summarization, natural language generation.
near miss in human-guided training of a machine learning system, a carefully chosen example that is only slightly different from a previous example, making it easy for the program to determine the difference between the new example and its existing model and to determine the significance of this difference.
negation as failure in a logic programming language such as Prolog, accepting a negative conclusion as true if its positive version cannot be proved, e.g., concluding that a man does not have a wife if no wife can be found. cf. closed world assumption.
neural network a computational network, often for pattern recognition, composed of mathematically defined elements that are thought to approximate the working of biological neurons; often composed of a layer that receives and organizes inputs, a hidden layer, and an output layer in which individual neurons identify particular patterns. Networks can be trained by back-propagation.
neuron a cell found in the brain and nerves that performs computation.
neurotransmitter a chemical that is emitted from axon terminals of a neuron, diffuses across the synapse, and binds to receptors on the target neuron to stimulate or inhibit that neuron.
NLP natural language processing.
nonlinear planning a planning task in which subgoals interact and cannot simply be done in an arbitrary order, e.g., a task of painting the ladder and painting the ceiling.
non-monotonic logic a form of logic in which conclusions can be drawn based on assumptions of things that are typically true; later information could force such conclusions to be withdrawn. cf. truth maintenance system.
nonterminal a grammar symbol that denotes the name of a phrase in a context-free grammar.
number a property of a noun phrase or pronoun that denotes whether it is singular or plural, e.g. they is plural.
number agreement matching of the number property, e.g. between a noun phrase and a pronoun or verb.
ontology the set of kinds of things that exist (or that are represented in an AI system), usually represented in a taxonomy.
open list in A* search, the set of nodes that have been generated (as successors of existing nodes), but not yet examined.
open world assumption the assumption that if a proposition cannot be proved or disproved, its truth status is unknown; this is the normal assumption in mathematical logic. cf. closed world assumption.
operationalize to convert general knowledge or principles, e.g. ``buy low, sell high'', into executable decision procedures in terms of available data.
operator in a state space search, an action that changes a state into a new state, e.g. a move in chess.
opportunistic describes an expert system or program that is able to take advantage of data that may not always be available, but that provides valuable information leading to or constraining the solution when it is available.
orthogonal knowledge sources knowledge sources that involve different kinds of data or constraints and that therefore are independent constraints on possible solutions.
OR node a node in an AND/OR graph which is true if any of its successors is true.
out in a truth maintenance system, describes a proposition that is currently not believed or supported. cf. in.
output layer the final layer of a neural net, composed of artificial neurons that combine results from neurons in the hidden layer and produce outputs.
override see shadow.
pandemonium model a model of human pattern recognition, due to Oliver Selfridge, in which a collection of ``demons'' observe the input data, a demon ``squeaks'' in proportion to how well the data match its pattern, and the demon that squeaks the loudest is taken as recognizing the pattern.
parallel distributed processing see neural network.
parent clauses in resolution theorem proving, the two original clauses from which a new clause is derived by resolution.
parse tree a tree structure describing the derivation of a sentence in a language according to the rules of a context-free grammar. The root of the tree is the ``sentence'' symbol, the leaves are the words or lexical units of the sentence, and each interior node represents a derivation step from the grammar.
parser a program that determines one or more ways in which a given sentence in a language could have been derived according to the rules of a grammar.
parsing the process of ascribing structure to a linear sequence of words or symbols according to the rules of a grammar.
part of speech a syntactic category of words in a natural language, e.g., noun or verb.
pattern matching the process of comparing an input to see whether it is an instance of a pattern, and if so, how variables in the pattern match items in the input.
PDP parallel distributed processing. see neural network.
perception the process of interpreting the meaning of sensory information.
perceptron an early pattern-recognition device using an artificial retina and combining inputs from retinal receptors using McCullough-Pitts neurons.
performance the actual use of language in concrete situations [Chomsky]. cf. competence.
phoneme the smallest unit of spoken natural language.
phonology the study of speech sounds.
physical symbol system hypothesis the hypothesis that representation and processing of symbolic structures are necessary and sufficient to account for intelligence.
pixel short for ``picture cell'', the smallest spot of intensity or color in a digital picture.
plan monitoring the process of monitoring execution of a plan, i.e. (1) are preconditions of operators actually true when it is time to apply the operators? (2) do operators have the expected effects?
ply 1. in a game-playing search, one level of the search tree, representing one move by one player. 2. hyphenated with a number, the number of moves ahead that a program or search is able to examine before running out of time, e.g., 8-ply.
polysemous of a word, having multiple meanings in a syntactic category.
postcondition a fact or set of facts that will be true after an action has been taken.
pragmatics aspects of a natural language that are arbitrarily dependent on a particular language, culture, or facts about the world.
precondition a fact or set of facts that must be true before an action can be taken; e.g., before a robot can pick up an object, its hand must be empty.
predicate 1. in predicate calculus, a symbol that is applied to zero or more arguments and is assigned values of True or False in an interpretation. 2. in Lisp, a function that tests a condition and returns a value of T (true) or nil (false).
predicate calculus a form of logical representation that includes: quantification of variables, terms (including functions of terms), and predicates whose arguments are terms.
preference semantics use of numeric weights to indicate preferred interpretations of words in context.
premise in a proof, things that are initially assumed to be true.
prenex normal form a representation of formulas in first-order predicate calculus, in which all quantifiers are at the front of the formula.
pretend it's English the use of English words or phrases in a knowledge representation scheme. This may make the scheme appear more powerful than it is because the human reader infers meaning from the English words that are used.
pretty-print to print an expression using indentation to show the nesting of substructures.
pretty-printer a function that will pretty-print a given expression.
primitive act in conceptual dependency, one of a small number of abstract actions, such as physical transfer, in terms of which natural language verbs are analyzed.
primitive subproblem a subproblem that is sufficiently simple that it is considered to be directly solvable or executable.
problem description a description, usually in a formal representation language, of a problem to be solved.
problem reduction search a technique for solving problems by solving primitive subproblems directly and breaking more difficult problems into simpler subproblems, which the problem solver attempts to solve recursively.
procedural attachment the ability to attach a procedure to a data structure and invoke it, e.g. an if-needed method in a frame system.
procedural representation representation of knowledge by means of procedures that can perform skills, but usually cannot be inspected or reasoned about. cf. declarative representation.
procedural semantics representation of the meanings of words by procedures that construct the meanings, as opposed to a declarative, dictionary-like representation.
production in a grammar, a rule that specifies that a phrase name can be replaced by a sequence of words or phrases.
production system a forward-chaining rule-based system, in which the contents of a working memory is compared to a set of rules, rules whose preconditions are satisfied are identified, and one or more rules is selected to be fired or executed. cf. OPS-5.
production memory in a production system, the memory that represents the rules used in analyzing and responding to a problem; analogous to human long-term memory. cf. working memory.
pronoun referece the word or phrase to which a pronoun refers.
property list in Lisp, a set of pairs, each consisting of a property name and corresponding value, that is associated with each symbol.
propositional database a database of facts, stored in the form of logical formulae, that allows retrieval of facts that match (unify with) a query predicate.
propositional logic a logical representation in terms of propositional variables, each of which is true or false and has no arguments.
protocol a transcript of what a human subject says when asked to ``think aloud'' while solving a problem.
punish to decrease the importance of a rule or network connection that is implicated in an incorrect decision, often by reducing its numerical weight. cf. reward.
qualitative simulation simulation of a physical system described by differential equations whose form is known, but whose coefficients are unknown or known only approximately; it can provide the set of possible behaviors of the system.
quantifier in a predicate calculus formula, a universal (for-all or &forall ) or existential (there-exists or &exist ) quantification of a variable.
quotation see quote.
quote 1. in Lisp, a pseudo-function that indicates that a symbol itself, rather than the value of the symbol, is to be used as a function argument. 2. to use a single-quote character as an abbreviation for quote. 3. to specify a function argument using quotation.
r-literal clause a clause containing r literals, e.g. 2-literal clause.
ramification the problem of deriving indirect consequences of an action. For example, if a book is on a table and the table is moved, the book is moved.
read-eval-print loop see Lisp interpreter.
reason maintenance system see truth maintenance system.
reasoning under uncertainty reasoning about situations, e.g. in medical diagnosis, in which good or complete data is not available, and in which decisions must be made based on available data and knowledge of likelihoods of the various possibilities.
recognize-act cycle in a forward-chaining production system, the cycle of operation, in which rules whose left-hand sides are satisfied by the data are identified (recognize), one or more of the enabled rules is selected (conflict resolution), and the selected rules are executed (act).
recognizer an automaton that reads an input string and determines whether the string is a member of the language it recognizes.
recursive 1. of or involving recursion. 2. defined in terms of itself.
referent the thing referred to by a phrase in natural language.
referent identification the process of determining to what object(s) in a program's model of the world a phrase in natural language refers.
referential ambiguity in natural language understanding, the apparent possibility that a word, such as a pronoun, might refer to one of several other words or concepts.
refutation completeness the ability of a proof procedure, such as resolution, eventually to derive a contradiction if the set of axioms is contradictory.
refutation graph a data structure, in the form of a tree or directed acyclic graph, that shows the facts, axioms, and intermediate conclusions from which a contradiction was derived in a resolution proof. cf. deduction tree.
regular regular grammars and languages are a restricted subset of context-free grammars and languages. The right-hand side of a regular production can have at most one nonterminal symbol, appearing at the end.
representation hypothesis the hypothesis that intelligence consists primarily of a symbolic representation of the world, manipulation of that representation by reasoning processes, and connection of it to perception and action.
resolution a sound and complete method for obtaining proofs by contradiction. The axioms and the negation of the desired conclusion are converted to a set of clauses in conjunctive normal form. Pairs of clauses from the set are resolved, and the resolvents are added to the set. If the empty clause is produced, the theorem is proved.
resolve in the resolution method, to form a new clause from a pair of given clauses. Given two clauses that have exactly one pair of unifiable predicates whose signs are opposite, a new clause is formed from the remaining literals of both clauses, with substitution of variables from the unification of the complementary literals.
resolvent the result obtained by resolving two clauses.
retina the tissue in the eye that converts light into electrical signals.
retract to remove a fact from the database of currently believed facts. This may be complicated because conclusions may have been derived based on the retracted fact.
reward to increase the importance of a rule or network connection that helped make a correct decision, often by increasing its numerical weight. cf. punish.
rewrite rule a rule for modifying an expression, often expressed as an input pattern and an output pattern, e.g. (- ?x (- ?y)) -> (+ ?x ?y)
rhetorical relations relations that denote the high-level structure of a natural language text, e.g. one sentence may provide a justification for the statement in another sentence.
RMS reason maintenance system. see truth maintenance system.
robust of a program or reasoning technique, able to work despite difficulties such as unexpected developments or missing, ambiguous, or incorrect inputs. cf. fragile.
root word the basic word of which an inflected word is a variant, e.g., ``go'' is the root word for ``went''.
rote learning learning of particular facts or of the classification of particular data sets.
rule a statement that makes a conclusion or suggests an action based on its premises; often written as a logical implication.
rule application 1. see fire (a rule). 2. the application of a rule to particular data by instantiating it for that data.
rule interpreter inference engine.
s-expression a symbolic expression in Lisp, consisting of a symbol or a list structure whose components are s-expressions.
SAT Boolean satisifiability.
SAT solver a program that can efficiently find solutions to problems expressed as SAT problems, e.g. WalkSAT and CHAFF.
satisfiable consistent, i.e. true for some interpretation.
satisfy to provide a set of data values that makes a logical formula or the antecedent of a rule true.
satisficing searching for a solution that is satisfactory, though not necessarily optimal.
Scheme a small, elegant dialect of Lisp that is sometimes used for teaching Lisp and for applications.
script a frame-like structure that describes a sequence of actions, e.g., the sequence of steps involved in dining at a restaurant.
search tree a tree structure, either explicit or implicit, of the states or goals considered in a search process. The initial state is the root of the tree; branches from a state correspond to operator applications or subgoals.
segmentation the process of dividing a visual image into regions that are visually coherent.
selection restrictions restrictions on the semantic categories of words that can be in certain case relationships to a particular sense-meaning of a verb; e.g., the subject of walk must be animate.
semantic grammar a grammar in which the phrases have meaning in the domain of application, e.g. part-name, as opposed to being general syntactic units, e.g., noun-phrase.
semantic markers markers associated with a word, especially a noun, that describe semantic categories to which the word belongs, e.g., animate, human, countable.
semantic network a representation of meaning based on a network of nodes that represent objects and labeled arcs between nodes that represent relations between the objects denoted by the nodes.
semantics the study of how statements in a language denote meanings.
sense one meaning of a word.
sensory describes neurons that carry information from sensory receptors, such as touch receptors.
sentence symbol the top-level symbol in a grammar, often abbreviated S.
set of support in theorem proving, a restriction that every proof step must involve a goal clause or a clause derived from a goal clause.
setf (pronounced ``set-eff'') in Lisp, a macro that takes as arguments code to retrieve a component of a data structure and a value, and produces code to store the value into the specified component of the data structure.
setq (pronounced ``set-cue'') in Lisp, the function that assigns a value to a variable.
shadow in a frame system, a specified slot value in an instance frame overrides or shadows a normal or default value specified in the class to which the instance belongs; e.g., if the color of a particular elephant is specified as pink, it shadows the normal elephant color of gray.
sigmoid S-shaped. In neural networks, the use of a sigmoid transfer function (as opposed to a step function) allows the function to be differentiated and thus allows back-propagation of values for automated learning.
similarity-based learning learning based upon the similarities and differences of training instances.
simplification the replacement of a formula or expression by one that is equivalent but simpler.
simulated annealing a technique, related to hill climbing, that attempts to find optimal assignments of values to multiple parameters. Moves (changes to parameters) that improve the value of the objective function are always accepted. Moves that worsen the value of the objective function may be accepted, with the probability being a function of ``temperature'', which is progressively reduced. This allows the search to escape local maxima.
situation calculus the technique of representing fluents by adding a ``state'' argument to each predicate whose value may change over time: AT(object, place, si) where si is a state variable.
Skolem constant in mathematical logic, a constant introduced as a substitute for an existentially quantified variable.
Skolem function in mathematical logic, a function introduced as a substitute for an existentially quantified variable that depends on universally quantified variables.
Skolemization the process of eliminating existential quantifiers by replacing them with Skolem constants and Skolem functions.
slot a named entry in a frame representation in which data about a particular aspect of the object represented by the frame is stored; e.g., a person frame might have an age slot. A slot may have multiple facets, including a value facet, if-needed or if-added methods, data type, documentation, etc.
Socratic completeness logical completeness {\em if} the right questions are asked in the right order.
solution graph a graph structure showing how a solution or proof is derived from premises.
somatotopy the principle that the connections between sensory and motor neurons and the brain are organized so that adjacent areas of body or retina are connected to adjacent areas of brain.
sombrero function a function that is the second derivative of a gaussian distribution, useful for computing a center-surround difference function for vision, similar to that computed by the retina.
sound of a theorem prover or algorithm, guaranteed to produce only correct results, i.e., anything that is proved is indeed a theorem. cf. complete.
specular describes a surface whose reflectance is mirror-like. cf. Lambertian.
splitting in natural deduction theorem proving, a method of proof by cases, i.e., splitting a theorem to be proved into multiple cases and proving each case separately.
spreading activation the notion that knowledge, in humans or machines, may be organized as a network of related concepts, and that activation of nodes that are explicitly mentioned can spread to activate other nodes; thus, ``red'' and ``siren'' may suggest ``fire engine''.
standard form a form of a predicate calculus formula in which all quantifiers are at the left, the matrix is converted to conjunctive normal form, and existential quantifiers are eliminated by Skolemization.
start state the initial state of a state space search; e.g., the starting position of a board game.
state description a data structure or set of values containing the information that specifies a particular state in a state space search.
state space the set of all states a system could be in, e.g. the set of all places reachable by a road network.
state space search a search for a sequence of operators that will transform a given starting state into some goal state. Each operator transforms a state into a different state.
state variable a variable that is added to fluent predicates, in situation calculus, to account for the possibility that the pedicates may be true in some states but not in others.
static evaluation function a function that computes an approximate value of a state (e.g., a position in a board game) without doing any search.
steepest ascent in a hill-climbing search, taking the move that gives the largest improvement in the evaluation function.
stepping-stone state in a state-space search, a state that is known to be a necessary intermediate state between the start state and a goal.
STRIPS STanford Research Institute Problem Solver. A planning system that represented the capabilities of a robot as a set of STRIPS operators and used search to find a sequence of operators that could achieve a goal.
STRIPS operator a representation of a possible action of a robot in terms of a precondition, add list, and delete list.
subclass in a frame system or object-oriented system, a class that is a subset of a given class and inherits properties from it; e.g., dog is a subclass of mammal.
subgoal a goal that is part of the accomplishment of a higher-level goal.
subproblem a smaller problem that needs to be solved as part of a larger problem. cf. problem reduction search.
substitution 1. the creation of an instance of a formula or pattern in which particular values are substituted for variables in the pattern. 2. a set of variables and the corresponding values to be substituted for them.
subsumed clause in predicate calculus, a clause that can be deleted because another clause is present that is stronger; e.g., P(x) subsumes P(x) &or Q(x) because whenever P(x) is true, P(x) &or Q(x) must also be true.
successor operator an operator that produces all successors of a given state.
suffix stripping see morphological analysis.
superclass in a frame system or object-oriented system, a class that is a superset of a given class; e.g., mammal is a superclass of dog.
supervised learning learning in which a human instructor provides training instances and their correct classifications.
support list in a truth maintenance system, a list of concepts related to a given concept that must be either in or out for the given concept to be true (in).
surface structure the actual (written or spoken) syntactic form of a sentence, as opposed to deep structure.
surface case the syntactic case relation between a verb and a related phrase, e.g., subject, indirect object, etc. cf. deep case.
symbol 1. a data structure that corresponds to an object in the real world, a word, or a concept. A symbol typically has a print name, a set of properties, and relationships with other symbols. 2. an instance of the symbol data type in the Lisp language.
symbolic algebraic manipulation the manipulation of mathematical formulas, expressed as symbolic structures within the computer, to produce new formulas or derived information, e.g., symbolic integration, solving equations simultaneously, or producing a graph of an equation.
symbolic information a representation in terms of symbols and their properties and relationships, as opposed to purely numeric data.
symbolic integration the mathematical integration of a given formula, with the result expressed as another formula.
symbolic manipulation 1. the processing of symbolic information to produce derived conclusions or new symbolic structures. 2. symbolic algebraic manipulation.
synapse the interface between the axon terminals of one neuron and the dendrites of the next neuron.
synonym a word that means the same thing as another word.
syntactic ambiguity the possibility that a natural language sentence can be parsed in more than one way, e.g., ``I saw John's dog driving to work today.''
synset synonym set.
syntax study of the ways in which language components can legally be combined into sentences.
table of connections in GPS, a table that connects a difference between a given state and a goal state with operators that might be relevant for reducing that difference.
tautology a logical formula that is always true.
taxonomy in a knowledge representation system, the tree structure formed by the class-superclass relations.
template matching in vision or other perception, direct matching of an input against a stored set of data values that represents a particular object.
tense a verb feature describing the time of the action, e.g. went is the past tense of go.
terminal symbol a symbol or word that appears in sentences of a language.
term in predicate calculus, an argument of a predicate that represents an object in the domain over which formulas are interpreted. Terms include variables, constants, and functions applied to terms.
theorem proving the process of proving a mathematical theorem, or solving a problem stated by means of axioms in predicate calculus, by mechanically deriving new formulas using rules of inference.
TMS truth maintenance system.
token an instance of a word in language. cf. type. The phrase to be or not to be contains 4 types and 6 tokens [Jurafsky & Martin].
top-down construction of a parse tree beginning at the top with the S nonterminal symbol and constructing the tree downward toward the leaf nodes (words).
top-down filtering in top-down parsing, restricting the phrases that are tried to only those that could begin with the current input word.
transformation in Chomsky's theories of language, a process that transforms a deep structure representation into a surface language representation; e.g., ``John hit the ball'' and ``The ball was hit by John'' are related by a passive transformation.
trigger 1. to cause a procedure to be executed or scheduled for execution. 2. a condition, specified with a knowledge source or procedure, such that the procedure is to be executed when the condition becomes true.
trigram a sequence of three words.
true under an interpretation of a logical formula, evaluating to the value True for a given interpretation.
truth maintenance system a system for maintaining a knowledge base (set of predicates) that allows a retract operation to remove predicates and that handles the problem that additional facts may have been derived from the retracted predicate.
truth table a tabular method of proof in which the truth of a formula is shown for each interpretation (set of values of propositional variables).
Turing test a proposal, due to A. M. Turing, that if an interrogator, examining either a person or a program remotely via a terminal, cannot tell whether the examinee is a person or a program, then the program must be regarded as intelligent.
two-pointer method a strategy for controlling resolution, in which two pointers into a list of clauses are used to select the clauses to be resolved. The inner-loop pointer starts at the beginning and moves until it reaches the outer-loop pointer. The outer-loop pointer begins at the negated conclusion.
type a word form. cf. token. The phrase to be or not to be contains 4 types and 6 tokens [Jurafsky & Martin].
Type 0 the most general class of languages in the Chomsky hierarchy, having no restrictions on the grammar.
uncertain reasoning see reasoning under uncertainty.
underlying concept in conceptual dependency theory, an abstract concept used in the representation of a verb, e.g., ``run'' would have PTRANS (physical transfer) as an underlying concept.
underlying verb a general verb in terms of which a surface verb could be expressed. For example, ``stand'' might be expressed in terms of the underlying verb ``attach'' with some extra arguments, e.g. that the location on the subject is ``feet''.
undo to reverse the effects of an operation that turned out to be undesirable.
unification algorithm an algorithm for finding a substitution of terms for variables in a set of predicate calculus literals that will make the literals the same.
unifier a set of substitutions of terms for variables that, when applied to a set of predicates, will make them all identical.
uniform cost search a search that examines operations in order of increasing cost from the start state.
unigram a single word.
unit clause a logical formula consisting of only a single literal.
unit preference a resolution theorem proving strategy of preferring to resolve unit clauses, or clauses with the fewest literals.
unsatisfiable of a logical formula, false under every interpretation; inconsistent or contradictory.
valid of a logical formula, true under every interpretation.
variable in a formula or pattern, a symbol that can be replaced by other symbols or data structures.
version space a machine learning technique in which a most general description and most specific description of a set of training instances are constructed until the two descriptions converge.
Waltz filtering an algorithm for finding consistent label sets for a labeled graph structure, e.g., interpretations of a line drawing of a polyhedron. Given a graph structure in which each node has a set of possible labels and nodes are connected by edges that represent constraints, the label sets are reduced by requiring arc consistency and by constraint propagation.
weak method a problem-solving technique, such as search, that may apply to a variety of problems but is not guaranteed to find a solution or to be efficient.
well-formed formula (wff) a formula composed of symbols that are arranged in a way that is allowed under the rules of the language.
wetware the brain, viewed as a kind of computer hardware that is wet, as opposed to electronic computers that are dry.
wff (pronounced ``woof'') well-formed formula.
working memory in a production system, the memory that represents the data about the current problem; analogous to human short-term memory. cf. production memory.
Zipf's law the principle that frequently used words are short. More precisely, length is proportional to negative log of frequency.