Artificial Intelligence

Strong AI

… - addressing abstract general-purpose problem solving

Weak AI

… - addressing concrete domain-specific task performance

Expert systems

… - Explicitly code the entirety of the information contained in the adult mind

Supervised learning

… - Code only the core mechanisms of the child mind and then expose it to supervised education

Reinforcement learning

… - Supplement learning with (unemotional) punishment/reward in a symbolic communication language

Weak criterion of ML

… -
1. System uses training data for improved performance
2. International ML meetings … operating … unspoken community criterion (p.107) ...“satisfies weak criterion and also involves some biology”
3. Scope of ML: Neural Networks / Genetic Algorithms / Symbolic Methods

Strong criterion of ML

… -
1. and also can communicate its internal updates in explicit symbolic form.
2. New dictum: “Until you have figured out a way for the machine to tell you what it has learned, it is not going to be very interesting to have it learn things anyway”.

Ultra-strong criterion for ML

… -
1. and also can “communicate its internal updates in explicit and operationally effective symbolic form
2. It must also show skill in the role of coach

Prolog

… is the most common logic programming language. … is a variation of clausal form where exactly one atom must be used in the head of each clause (but nested conjunctions, disjunctions and negations of atoms may be used in the body).

facts, rules, queries

INPUT1, INPUT2, INPUT3 - 3 key parts of a Prolog/Datalog program

Facts

… (cf. relational database):
- Extensional definition (one fact per table row)
- Predicate (terms,…)
movie(american_beauty, 1999).

Rules

… (cf. relational views):
- Intentional definition; materialised when needed
- operators
:- if
, and
; or
\+ not
released_after(M,Y) :- movie(M,Z), Z > Y.

Queries

… (cf. relational algebra):
Prolog is much easier than database queries like SQL.
?- (actor(M,A,_) ; actress(M,A,_)), director(M,A), released_after(M,1999).

listing.

… SWI command - shows current predicate definitions.

make.

… SWI command - detect and reload any modified definitions.

ground numbers

Comparison operators for … :
<
>
=<
>=
\==

arbitrary terms

Comparison operators for … :
@<
@>
@=<
@>=
==
\==

term

A … is a constant c, variable X or function f of artity n applied to an n-tuple of terms f(t1 , ... , tn)

atom

An … a proposition p or a predicate r of arity n applied to an n-tuple of terms r(t1 , ... , tn)

formula

A … is an atom a; a logical constant T or ⊥; a negation ¬θ of a formula θ; a conjunction θANDɣ,

disjunction θORɣ or conditional (if) θ←ɣ of formulae θ and ɣ; a universal quantification AllXθ or an existential quantification ExistsXθ of a formula θ with respect to a variable X

prenex normal forms

… - only allow formulae of the form <prefix><matrix> where the prefix is a string of quantifiers and the matrix is a quantifier-free formula

conjunctive normal form

… - most common Prenex Normal Form, where the prefix is further restricted to a string of universal quantifiers and the matrix is further restricted to a conjunction of disjunctions (aka clauses) of atoms or their negations (aka literals)

transitive closure

… allows to define patrilineal ancestorship:

Lists

… - prototypical structured term:
empty … : []/0
… constructor: [|]/2
‘[|]’(Head, Tail) is written [Head|Tail]
[Head|[]] is written [Head]
[Head1|[Head2|Tail]] is written [Head1, Head2 | Tail]

list length

Primitive definition of … :

list member

Primitive definition of … :

list append

Primitive definition of … :

bagof(C,Q,L), setof(C,Q,L), findall(C,Q,L)

… formulas: collect all instantiations of term C generated by solutions to query Q all together in list L.

bagof/3

… Prolog formula allows explicit (existential) quantification of (free) query variables (in Q but not in C); and fails if Q fails​.

setof/3

… Prolog formula is like bagof/3, but returns a sorted list (without duplicates)

findall/3

… Prolog formula is like bagof/3 but with all implicit quantification over all free query variables, it succeeds with L=[] if Q fails

Selection rule

A query literal is chosen by a … (which, by default, returns the leftmost literal)

Search rule

A clause is chosen by a … (which, by default, returns clauses from top-to-bottom)

variant of the database clause

A fresh … is created by renaming all of the variables to new ones (alternative clauses can be considered in backtracking).

Substitution

A … is a set of bindings of (distinct) variables to terms:
θ = {X₁/t₁, …, X_n/t_n} where ε is used to denote the empty … . The application of a … θ to an expression E is denoted Eθ and obtained by replacing any (free) variable X_i in E by the corresponding term t_i from θ, if one exists.

More general substitution

A substitution θ1 is (as or) … than a θ2 iff there exists some θ3 such that θ1θ3 = θ2

Unifier

A substitution θ is a … of two expressions E₁ and E₂ iff E₁θ=E₂θ

Most general unifier (mgu)

A substitution θ is a … of two expressions E₁ and E₂ iff θ is a unifier of E₁ and E₂ that is more general than all other unifiers of E₁ and E₂. We can compute an … as follows:
…(E₁,E₂,θ)=…(E₁{X/t}, E₂{X/t}, θ{X/t}) where X is a variable from one expression at the first syntactic position where the two expressions differ, and t is the corresponding term in the other; neither is a variable if there is no …; if both are variables then we can bind either to the other; strictly we should fail if t mentions X but this ‘occurs check’ is usually omitted in Prolog.

Search (SLD) Tree

… - shows the search space reachable through backtracking. Nodes are queries: the root is the initial query and children of a node are the resolvents of the parent query on its first literal.
Success branches are leaves with an empty clause, denoted [] (or □).
Failure branches (with no further resolvents) are denoted # (or †,■, _).
A proof tree can be obtained for each success branch by reconstructing the implicit side clauses and their corresponding MGUs.
The computed answer is shown underneath each success branch.

Proof tree

… corresponding to the second answer of member(X, [a,b,c]).

Cut

… operator - has a procedural side-effect of pruning choice points made until now by the current and parent clause.

Green cut

… (for efficiency) - avoid branches that contain no additional answers. … prune redundant failure branches (to avoid unnecessary tests when guards are mutually exclusive).

Red cut

… (for correctness) - avoid branches that contain “incorrect”/”unwanted” answers. Can further increase efficiency (and also program compactness) by letting us make some guards completely implicit!

If-Then-Else

… - unline !/0, the choice point of the predicate as a whole (due to multiple clauses) is not destroyed.

new operator

op/3 Prolog directive is used to declare a … :
op(900, fy, \\+).
900 - precedence of new operator (900 is similar to built-in \+).
fy - type of operator. f means prefix - comes before its argument. y means it can take arguments of same/lower precedence.
\\+ - name of the new operator being defined.

Negation-as-failure

… can be defined in terms of cut as shown by the following definitions of the new user-defined operators \\+, \\\+ and \\\\+ which are logically equivalent to Prolog’s built-in \+ operator (at least for calls X not containing explicit cuts):
]

include(:Goal, +List1, ?List2)

… - filter elements for which Goal succeeds. True if List2 contains those elements Xi of List1 for which call(Goal, Xi) succeeds.

exclude(:Goal, +List1, ?List2)

… - filter elements for which Goal fails. True if List2 contains those elements Xi of List1 for which call(Goal, Xi) succeeds.

maplist(:Goal, ?List1, ?List2)

… - true if Goal is successfully applied on all elements of the list.

sort/2

… Behaviour - first sort on the values of the first item (if it exists), and then sort on the values of the second items(if it exists):
…([ [g,b], [c,d,e], [f], [] ], S). returns S = [ [], [c, d, e], [f], [g, b] ].

Numeric evaluation

… - 

Term equivalence

… - 

meta-predicate

… clause/2 - succeeds once for every clause in the knowledge base that resolves with the given Goal in order to leave a corresponding Resolvent, which is returned.

vanilla meta-interpreter

… - Prolog predicate that simulates the evaluation of Prolog queries with respect to (pure) Prolog programs:

Depth-bounded meta-interpreter

… - The vanilla meta-interpreter can easily be adapted to customise the search strategy.

Blind search

… methods - look for goals in a systematic way, but do not take the quality of partial solutions into account (using heuristics).

Agenda-based search

… - makes abstraction of the order in which search nodes are added to and removed from agenda.
Given an +Agenda (represents a set of nodes at the frontier, initially set to start node)
Returns -Goal node (identified by a Goal function), that is accessible from the nodes on the agenda

Depth-first search

… -
- Agenda = stack (LIFO)
- Incomplete: may get trapped in infinite branch
- No shortest-path property
- Requires O(B*n) memory; B is branching factor (number of children), n is the depth

Breadth-first search

… -
- Agenda = queue (FIFO)
- Complete: will find all solutions
- First solution found along shortest path
- Requires O(Bⁿ) memory

Iterative Deepening Search

… -
- Combines good features of BFS and DFS
- Optimality of BFS + Memory footprint of DFS
- Repeats work, but works well in practice
In a binary tree, half the nodes are in the leaves

Best-First

… search - when adding children into the agenda, we can order them with respect to some easily-computed metric (function) that tries to assess the quality of each node (by estimating the cost of the best solution path through that node). Thus we should put nodes with low scores at the front of the agenda.
Agenda - Priority Queue.
Behaviour - depends on heuristic employed.

“A algorithm”

… -best-first search algorithm that aims to minimise the total cost of solution paths via some node n using a metric f which combines the actual cost g of reaching n from the start together with an estimate of the cost of reaching a goal from n.
f(n) = g(n) + h(n)
estimate of total cost along path through n = actual cost to reach n from start + estimate of cost to reach goal from n
h(n) == 0 at any goal

Breadth-first search

An “A" algorithm with f(n) = g(n) gives … 

Greedy best-first search

An “A" algorithm with f(n) = h(n) gives … 

Globally optimistic / admissible

A heuristic is … the estimated cost of reaching a goal is always less than the actual cost (from any node n), h(n) <= h*(n). With … heuristic, an A algorithm is guaranteed to return a solution if one exists.

Monotonic / locally optimistic / consistent

A heuristic is … if it never decreases by more than the cost c of an edge from a node n1 to a child n2.
… is a stronger condition than admissibility. It means that the estimated cost from a node n to the goal, plus the cost of one step to a successor n′, is no greater than the estimated cost from the successor to the goal: h(n)≤cost(n,n′)+h(n′).
With … heuristic, an A algorithm is guaranteed to return an optimal solution if one exists.

Manhattan distance

… formula:

Euclidean distance

… formula:

Minkowski distance

… formula:

The negation operator

… can be defined in Prolog as follows:
neg(G) :- call(G), !, fail.
neg(_) :- true.
?- neg(round(earth)).

c = 1

Define value of cost c in this unit.

Procedure box model

… - the debugger executes a program step by step tracing an invocation to a predicate (call) and the return from this predicate due to either a success (exit) or a failure (fail). When a failure occurs the execution backtracks to the last predicate with an alternative clause. The predicate is then re-invoked (redo). Another source of change of the control flow is due to exceptions. When an exception is raised from a predicate (exception) by throw/1, the control is given back to the most recent predicate that has defined a handler to recover this exception using catch/3.

Deterministic predicate

… - well-behaved: closing off the REDO port, i.e. “leaving no choicepoint”

Nondeterministic predicate

… - well-behaved if it closes off the REDO port at the last solution, i.e. “leaves no choicepoint”

Semi-deterministic predicate

… - well-behaved: closing off the REDO port, i.e. “leaving no choicepoint”

Multi predicate

… - well-behaved if it closes off the REDO port at the last solution, i.e. “leaves no choicepoint”

Evolutionary computing

… refers to a family of optimization algorithms inspired by biological evolution and natural selection. They're used to find solutions to NP-hard optimization problems. Such techniques are:
- Heuristic (opposite of “exact”) - not guaranteed to find the best solution.
- Stochastic (opposite of “deterministic”) - use random number generators and return different answers every time. Kinds: Genetic Algorithms (GA), Genetic Programming (GP); Evolutionary Strategies; Differential Evolution etc..

metaheuristic

Evolutionary Computing problems are examples of … approaches:
A … is a way to guide search - some are nature or population-based, some build an explicit model of the problem as it’s being solved.

Individual-based metaheuristics

… - in contrast to Evolutionary Computing approaches, … do not use a population of solutions, e.g. hill climbing, simulated annealing, tabu search, etc. .

Simple hill climbing

… algorithm exploits current local knowledge of the search space - not even interested in fully exploring the local neighbourhood:
1. Make a random starting solution.
2. Change it a little.
3. If new solution is better - keep it, else discard it.
4. If stuck - stop (local optimum solution found), else - go to 2.

Steepest ascent hill climbing

… algorithm - Explores the local neighbourhood fully before greedily exploiting the best local next step

Simple Tabu Search

… algorithm -hill climb, but don’t consider solutions on a finite list of previously visited solutions. More exploratory than hill climbing, keeps a record of solutions that haven’t been fully exploited.

Simulated Annealing

… algorithm - hill climbing, but moves to worse solutions with a probability (temperature) that is initially high, but decreases as more steps are made. Starts exploratory at high steps, gets more exploitative as temperature falls.

Genetic Algorithms

… maintain a population of solutions to help balance the explore/exploit trade-off. They share the same basic form: assess, breed, mutate a population of solutions.

Competition and crossover

… allow success in one part of the space to be exploited by the rest of the population.

Population of solutions

… allows exploration to take place in multiple parts of the solution space.

Population

… - the set of individual solutions that the GA is acting on.

Individual

… - a member of the population

Genotype

… - a string of symbols from some alphabet that encodes a particular solution (aka genome or chromosome)

Phenotype

… - the actual solution encoded by a genotype (blue eyes, blonde hair)

Genotype-phenotype mapping

… - analogous to development

Genes

… (aka loci) - chunks of genome, each taking a value “allele”

Fitness

… - the value or quality of an individual solution phenotype

Selection

… - choosing which current individuals reproduce

Parents

… - individuals selected to reproduce

Offspring

… - the new individuals that result from reproduction

Crossover

… - the recombination of alleles from multiple parents

Mutation

… - replacing offspring alleles with random alternatives

Fitness landscape

… - an evolutionary search space organising all possible solutions according to the neighbourhood relationships that result from GAs “Genotype Structure” and “Genetic Operators”, with landscape “altitude” set by each solution’s fitness.

Simple genetic

… algorithm: