The way the system is, at a moment in time.

nothing about possible changes 

- Inital state (definition)

- a set of operators/ actions to go from one state to another 

- states and operators define the state space 

- goal test 

- path and funtions

- solution

- no knowledge about the distance (cost) from the current state to the goal state

- only detect when a goal state has been found

(brute force/blind search)

- access to extra information (an estimation of cost for the remaining path from current to goal state 

- estimation by heuristic function 

- "informed search"

The programmer specifies a goal to be achieved and the system works out how to achieve it

e.g. prolog

The programmer specifies how to achieve a goal

e.g. C, C++, Java

- Ease of programming (prolog programs are smaller in size relative to procedual)

- Increases programmer productivity

- Facilitates proving correctness of programs

Paper Needed

List Member

member(X,[X|T]).

member(X,[H|T]) :- member(X,T).

Paper Needed

Take a list and give a copy of it

clist([],[]).

clist([H|T],[H|R]) :- clist(T,R).

Paper Needed

last element 

last(X,[X]).

last(X, [H|T]):-last(X,T).

len([], 0).

len([H|T],N):- len(T,X), N is X+1.

intlist([]).

intlist([X]) :- integer(X).

intlist([H|T]):- integer(H), intlist(T).

max2(X,Y,Z):- X>=Y, Z is X.

max2(X,Y,Z):- X < Y, Z is Y.

maxlist([X],X).

maxlist([H|T], M):- maxlist(T, Mt), max2(H,Mt,M).

io([]).

io([H|T]):- H>0, write (H), io(T).

io([H|T]):- H <= 0, io(T).

del(H, [H|T], T).

del(X,[H|T], [H|T1]):- del(X, T, T1).

evenlength([]).

evenlength([H|T]):- oddlength(T).

oddlength([H|T]) :- evenlength(T).

mul([],[]).

mul([H|T], Result) :- mul(T,R) x is Z * H, concat([X], R, Result).

member(X, [X | T]).

member(X, [H | T]) :- member(X, T).

add(Element, List, List) :- member(Element, List), !. add(Element, List, [Element | List]).

run:- read(X), test(X).

test(1) :- !, write('Invalid Number').

test(_) :- write('Invalid Input').

classify(Number, positive):- Number > 0, !.

classify(0, zero).

classify(Number, negative) :- Number < 0, !.

factorial(0,1).

factorial(N, Result):- 

N > 1,

N1 is N-1,

factorial(N1, Result),

Result is Result1 * N.

- Expand the shallowest nodes on the fringe first

- All nodes at depth d are expanded before any nodes at depth d + 1 

Time Complexity: b^d

Space Complexity: b^d

Optimal: yes

Completeness: yes

Time Complexity: b^d

Space Complexity: b^d

Optimal: yes

Completeness: yes

Time Complexity: b^m

Space Complexity: bm

Optimal: no

Completeness: no

Time Complexity: b^l

Space Complexity: bl

Optimal: no

Completeness: yes if l > d

Time Complexity: b^d

Space Complexity: bd

Optimal: yes

Completeness: yes 

Time Complexity: b^d/2

Space Complexity: b^d/2

Optimal: yes

Completeness: yes

- close to the target function. I.e. minimises error

- describes a large number of instances in a concise way

- generalises well to unseen test data

Ockhams Razor Princiable

- This is the most likely hypothesis is the simpliest one that is consistent with the training data

- '?' which indiciates that any value is acceptable for the attribute

- specify a single value for the attribute 

- Ø indicates that no value is acceptable for the attribute

- Guarenteed to output the most specific hypothesis within H that is consistent with the positive training example

- Output of FIND-S will be consistent with the negative training examples

- Finds only one of the possible hypothesis

- Requires H to be finite 

- Guarenteed to output all hypothesis consisten with the training data 

- Requires exhaustive ennumeration of hypothesis in H

- Methods are conceptually simple

- Can be used to represent attribute value pairs

- Difficult to use these method with structured data 

- Each non-leaf node specifies an attribute

- Each leaf node has an integer value

- Each edge from a non leaf node is labled with a value for the attribute specified by the node 

- Calculate the info gain for all attributes

- The attribute with the highest info gain in the root node

- At every level, choose the attribute with the highest info gain

- only use a part of the training data for leaving the hypothesis

- use the remaining training data for testing the hypothesis

- repeat this with different subsets of data, and choose a hypothesis with good prediction performance

- Take the majority classifcation for the set examples

- consider the estimated probablities for each classification using their relative frequency 

- Prune irrelevant attributes

- cross validate hypothesis and choose best at decsion making

                                                               If a hypothesis and an example are inconsistent, a logical inference system can learn from the example by eliminating the hypothesis.

                                                               i.      Start with an initial hypothesis and call it the current hypothesis

                                                             ii.      For each training instance check if it is consistent with current hypothesis and if not adjust the current hypothesis to make it consistent

1.       Generalisation – dropping conditions

2.       Specialised – Adding conditions

1.       This method is conceptually simple

2.       Non-deterministic; so several generalisations and specialisations can be made

3.       Choices made may not lead to simple hypothesis

4.       Choices may lead to irrecoverable situations, so you must backtrack

                                                               i.      Data is linearly separable if a straight line can separate positive and negative instances

What is    Perceptron Learning

                                                               i.      For the classification of linearly separable data using a binary classifier, a perceptron, It receives info from perceptrons/environment, processes it then transmits to other perceptrons/environments

1.       For linearly separable training data, guaranteed to find a solution in a finite number of steps

2.       Conceptually simple

3.       Multiple solutions possible

4.       May not converge for training data that isn’t linearly separable

5.       Does not readily generalise more than 2 classes

a.       Used to classify data that is

                                                               i.      Not linearly separable

                                                             ii.      Represented in Euclidean space

b.    

   Do not construct hypothesis

c.      

Each time new data is encountered a prediction is made based on new to old

This method is for classification of data represented in Euclidean space. It is used to classify data that is not linearly separable. In order to classify a point x_q:

• find its k nearest neighbors by using Euclidean distance measure

• then, find the majority class for these k neighbors and classify x_q as the majority class.

                                                               i.      Pros

1.       Useful local approximation of complex non-linearly separable training data

                                                             ii.      Cons

1.       The cost of classifying new test data can be high since computation must be repeated for each test data

2.       The classification of test data os sensitive to the value of k

                                                               i.      Advantages

1.       Useful for graph search or traversal

2.       BFS – complete, simple to implement on any search problem

3.       DFS – memory O(bm)

4.       Iterative – memory O(bm)

5.       Uniform – optimal

a.       Uninformed Search

                                                               i.      Disadvantages

1.       Has no knowledge about distance from the current state to the goal

2.       Can only detect when a goal state has been found

3.       BFS – Memory is high O(b^d) as its inefficient

4.       DFS – not complete

5.       Iterative – not optimal

6.       Uniform – exponential memory

1.       A* -If h is admissible and consistent then is optimal and complete

2.       Good to have an estimate

3.       Can solve problems quicker

                                                               i.      Disadvantages

1.       Need to keep everything that happens in the memory

2.       Need to be able to do quick cost comparisons

3.       Need to choose good heuristics

4.       Greedy – Not complete or optimal, can be false starts

5.       A* - high memory required

a.       A sentence S is satisfiable if there exists a structure that S evaluates to true. Otherwise S is unsatisfiable or contradictory

b.       A sentence S is valid or a tautology if for each possible structure for S, S evaluates to true

                                                               i.      Hard to express properties of objects or relations between them

                                                             ii.      Propositional logic ant deal with facts changing over time

                                                           iii.      Propositional logic is sound, complete, monotonic and consistent

                                                           iv.      Propositional logic is decidable 

                                                               i.      Assumes the world contains objects and relations or properties with them

                                                             ii.      Contains quantifiers

                                                           iii.      More expressive