Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

AI > Exam > Flashcards

Exam Flashcards

1
Q

What is Logic Programming?

A
  • You present facts and rules to infer new facts by just asking questions
  • When a question is asked, the runtime system searches through a database of facts and rules to determine (by logical deduction) the answer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is Proof?

A
  • A sequence of sequences, where each sentence is either a premise or a sentence, derived from earlier sentences in the proof by an inference rule
  • The last sentence is the goal to be proved (T/F)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is Modus Ponens?

A

If P → Q and P are true, then infer Q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is Modus Tollens?

A

If P → Q and ¬ Q are true, then infer ¬ P

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is And Elimination?

A

If P ∧ Q is true, then infer both P and Q are true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is And Introduction?

A

If P and Q are true, then infer P ∧ Q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is Disjunctive Syllogism?

A

If addition (P v Q) and ¬ P are true, then infer Q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What does A→B mean?

A

If A is true, then B is true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What do A⇔B, A↔B and A≡B mean?

A

If both A and B are false, or both A and B are true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What does ¬A mean?

A

If A is false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What does A∧B mean?

A

If A and B are both true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does A∨B mean?

A

If A, B or both are true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Example of Proof with Inference Rules

Premises:

  • It is not sunny this afternoon and it is colder than yesterday. We will go swimming only if it is sunny.
  • If we don’t go swimming, then we will take a canoe
  • If we take a canoe trip, then we will be home by sunset

Conclusion:
- We will be home by sunset

A

Solution

Where:

  • S: It is sunny this afternoon
  • C: It is colder than yesterday
  • W: We will go swimming
  • T: We will take a canoe trip
  • H: We will be home by sunset
Premises:
¬ S ∧ C
W → S
¬ W → T
T → H

Goal: H

Formal Proof:

  1. ¬ S ∧ C Premise
  2. ¬ S Simplification
  3. W → S Premise
  4. ¬ W Modus Tollens (2/3)
  5. ¬ W → T Premise
  6. T Modus Ponens (4/5)
  7. T → H Premise
  8. H Modus Ponens (6/7)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are the limits of Propositional Logic?

A

Cannot represent:

  • If X is married to Y, then Y is married to X
  • If X is West of Y, and Y is West of Z, then X is West of Z

Solution:

  • Extend representation by adding predicates
  • Extend operator (resolution) by adding unification
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are Symbols in Predicate Calculus?

A

Symbols consist of:

  • Set of letters (lower or uppercase)
  • Set of digits: 0….9
  • Underscore
  • Must begin with a letter
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are Constants in Predicate Calculus?

A
  • They name specific objects or properties in the world
  • Must begin with a lowercase letter
  • The constants “true” and “false” are reserved as truth symbols
  • E.g. car, tree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What are Variables in Predicate Calculus?

A
  • Used to assign general classes of objects or properties
  • Must begin with an uppercase letter
  • E.g. Car, Tree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are Functions in Predicate Calculus?

A
  • Must begin with a lowercase letter
  • Replacing a function with its value is called evaluation
    • plus (2, 3) whose value is 5
  • E.g. wife (Ninny)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are Predicates in Predicate Calculus?

A
  • They must begin with a lowercase letter
  • A predicate names a relationship between objects in the world
  • E.g. loves (Billy, Ninny), equals (X, Y)
  • Predicates are special functions with true/false as values
  • Predicates of the same name with varying numbers of arguments are considered distinct
    • E.g. loves (Billy, Ninny), loves (Billy, Ninny, Pepe)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What are Semantics?

A
  • Terms are mapped to objects in their demain

- The semantics determine a truth value of an expression

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is Unification?

A
  • The inference system must be able to determine when two expressions are the same
  • Two expressions only match if syntactically identical
  • Unification is an algorithm of determining the substitution list to make two predicate expressions match
  • If P and Q are logical expressions:
    • Then unify (P, Q) gives a substitution list S, that makes P and Q identical or fails
  • The algorithm is complicated by the existence of variables
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is Substitution?

A
  • A substitution is assigning values to variables
  • Two terms unify if there is a substituion making them identical
    • E.g. unifying f (X, 2) and f (3, Y), to produce X=3, Y=2 (Written as 3/X, 2/Y)
  • The notation X/Y indicates that X is substituted for the variable Y in the original expression
23
Q

What are Biological Neurons?

A
  • A neuron has a cell body, a branching input structure (the dendrite), and a branching output structure (the axon)
  • Axons connect to dendrites via synapses
  • Electro-chemical signals are propagated from the dendritic input, through the cell body, and down the axon to other neurons
  • A neuron only fires if its input signal exceeds a certain threshold in a short time
  • Synapses vary in strength based on their connections
24
Q

What is an ANN?

A
  • Artificial Neuron Network
  • An emulation of a biological neuron system
  • Consists of nodes and weights (neuronal connection)
  • Each node has weighted connections to other nodes in adjacent layers
  • Each takes inuts received from connected nodes, and uses the weight together with a function to compute output values
  • ‘Knowledge’ is stored in the connections between neurons
25
Q

How do ANNs work?

A

Training the neural network

a. Introduce data
b. Compute ouput
c. Compare to desired output
d. Modify weights to reduce error

Using the neural network

a. Introduce new data to network
b. Allow network to compute output based on training

26
Q

What is a Single Layer Neural Network?

A
  • An adder sums up all the inputs modified by their respective weights
  • This activity is referred to as linear combination
  • An activation functions controls the amplitude and output of the neuron
  • An acceptable range of output is usually between 0 and 1, or -1 and 1
27
Q

What are the advantages and disadvantages of a Single Layer Network?

A 
\+
Simple to implement
Fast learning
-
Can only learn linearly separable functions
The X OR problem
28
Q

What is a Multi-layer Neural Network?

A
  • A multi-layer is a feedforward neural network with one or more hidden layers
  • The network consists of: an input layer of source neurons, at least one middle/hidden layer of computational neurons, and an output layer of computational neurons
  • The input signals are propagated in a forward direction on a layer-by-layer basics
29
Q

What are the Characteristics of a Multi-layer Neural Network?

A
  • Overcome limitations of a linear perceptron
    • Learns non-linear relationships
  • Solves difficult problems
    • Classification, stock prediction, control of complex systems etc.
  • Number of layers
    • One hidden layer is usually sufficient
  • Learning
    • More complex learning methods
    • Can be very slow
    • Requires lots of training data
30
Q

How to Train Neural Networks?

A

Training

  • Finding the correct weight values
  • Supervised training: show the network the desired output
  • Apply a learning method to modify weights

Training Data

  • Input values
  • Corrensponding desired output values
31
Q

When should ANNs be used?

A
  • Data is rich
  • Non-linear, multidimenstional input/output mapping
  • Enough time to design the final ANN (hours to days for training)
32
Q

What are the Design Steps of an ANN?

A
  1. Set up ANN architecture
    - Number of inputs, outputs
    - Which of input features to take
    - How large of sample to take
    - Number of hidden layers
    - Number of neurons (too many takes too much training time)
    - Learning rate (from exp value should be small ~0.1
  2. Tune/optimise internal parameters
    - By presenting learning data set to ANN
  3. Test ANN
    - If successful, then it is done
    - If it fails, then go back to previous steps and try different values of parameters, or a different topology
33
Q

What are the Advantages of ANNs?

A
  • Largely parallel processing, which benefits real-time application
  • Self-trainable, when given training data
  • Learning involves increasing/decreasing connection strengths
  • Excellent at generalisation, and dealing with uncertain information
  • Works well with ‘noisy’ data
  • Does not need to be reprogrammed
  • Performs tasks that a linear program cannot
34
Q

What are the Disadvantages of ANNs?

A
  • Needs training to operate
  • Requires high processing time for large networks
  • Do not explain the results obtained
  • Processing time quickly rises as the problem size grows
  • May not always converge to an optimal solution
  • Overtraining
35
Q

What are some Applications of ANNs?

A
  • Pattern recognition (supervised learning) e.g. in computer vision, speech and characyer recognition, bitometrics etc.
  • Clustering (unsupervised learning)
  • Optimisation
  • Control e.g. autonomous robots, manufacturing
  • Medical applications e.g. disease diagnosis, cancer cells analysis
  • Business applications e.g. market segmentation, sales forecasting
36
Q

How would you Train a ‘Full’ Network?

A
  1. Propagate signal through different layers of the network until an outcome is achieved
  2. Compare the outcome with the target, i.e. calculate error signal
  3. Back propagate the error to the hidden layers
  4. Modify weights
37
Q

What are the two Methods of Searching a Node Tree?

A

Breadth first: visit each level, one by one

Depth first: visit each child node to its maximum depth

38
Q

Compare Breadth and Depth Search

A
  • Implementation is similar
  • Depth first uses a stack to expand child nodes, while breadth first uses a queue
  • Branching factor is usually larger than the depth, so breadth typically uses more memory
  • Both worst case complexity of O (V + E)
  • In video games, we should look for a fixed number of moves ahead, and look for the outcomes (Breadth first)
  • When considering all outcomes, depth search usually uses less memory, and is easier to implement
  • Our approach depends on what we already know about the tree
39
Q

What is Dijkstra’s Algorithm?

A
  • Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph
  • Planning: works out complete route in advance
  • Divide and conquer: decomposes planning into iterative process
  • Eliminates suboptimal directions early on
  • Explores all possible paths
  • Needs a general graph with distances
  • Reject potential paths if they’re too long
  • Systematic; breadth first is a good starting point
40
Q

Formally Define Dijsktra’s Algorithm

A

We need:

  • Set of nodes and pair costs to traverse to neighbours
  • Our case: grid and cost 1 up/down/left/right, cost 1.4 diagonal
  • Start and end nodes

For each node, we keep:

  • Total cost from beginning
  • Link to the neighbour which got us there for that cost

We also need two node lists: open and closed

Initialisation

  • Set total costs of all nodes to infinity
  • Set total cost of start node to zero
  • Ignore links
  • Put all nodes on open list

Each iteration:

  • Find node N on open list with lowest estimated cost
  • Move to closed list with curretn estimate as best
  • Re-estimate each open neighbour (cost of N + pair cost)
  • If new neighbour estimate is lower, update node cost and set link to N
  • When N == end node, it is complete
41
Q

Formally define Dijsktra’s Algorithm

A

We need:

  • Set of nodes and pair costs to traverse to neighbours
  • Our case: grid and cost 1 up/down/left/right, cost 1.4 diagonal
  • Start and end nodes

For each node, we keep:

  • Total cost from beginning
  • Link to the neighbour which got us there for that cost

We also need two node lists: open and closed

Initialisation

  • Set total costs of all nodes to infinity
  • Set total cost of start node to zero
  • Ignore links
  • Put all nodes on open list

Each iteration:

  • Find node N on open list with lowest estimated cost
  • Move to closed list with curretn estimate as best
  • Re-estimate each open neighbour (cost of N + pair cost)
  • If new neighbour estimate is lower, update node cost and set link to N
  • When N == end node, it is complete
42
Q

Explain the role of Intermediate Nodes in Dijkstra’s Algorithm

A
  1. Remember the best route found so far for each intermediate node, and use it to reject any partial candidate paths which are longer
  2. Possibly find better path segments as it goes along
  3. Where there are no possible better ways, determine best solution
  4. Use knowledge to refine best routes to its neighbours
43
Q

What are the limitations of Dijkstra’s Algorithm?

A
  • Needs to plan entire solution in advance
  • Doesn’t adapt to changes in environment
  • Doesn’t adapt to changes in target position
  • Doesn’t take into account any moving objects in the environment
44
Q

What is the A* Algorithm?

A
  • This is the de facto standard for pathfinding in games, and is known to be optimal
  • Builds on Dijkstra’s algorithm by changing from a SPF search to a best-first search
  • It modifies Djikstra to search more likely paths first, by choosing what would be most direct first
  • This is achieved by adding a heuristic function to the open node costs when choosing which node to close next
45
Q

Formally define the A* Algorithm

A
  • Define a new cost function f(x) = g(x) + h(x)
  • g(x) = cost from start for node x, determined in exactly the same way as Dijkstra
  • h(x) = “heuristic”function for node x = some estimate of the minimum cost go get to the destination from x
  • Open node with lowest f(x) is selected for closing at each step
46
Q

What are the limitations of A*?

A
  • Doesn’t adapt to changing environment or player
    • If a change occurs, it may need to re-run with many agents, resulting in recalculations
  • Doesn’t plan around other AI objects
  • Difficult to improve speed
47
Q

What is the Heuristic Function f(x)?

A
  • The heuristic function can be any function which estimates the distance from a node to its target
  • Admissible: don’t overestimate the shortest distance
  • Examples of suitable heuristics in a 2D space:
Manhattan Distance:
- Total difference in X + TD in Y
- Suitable for 4 connected grid
Diagonal Distance (Chebyshev):
- Max (difference in X, d in Y)
- Suitable for 8 connected grid
Euclidean Distance
- sqrt ((difference in X) ^2 + (d in Y)^2)
48
Q

Discuss a 3D Example, involving two Agents

How can you plan Agent 2’s path around Agent 1?

A

Plan the movement of Agent 1 as normal

  • For each time-step of Agent 1’s path, make a map which includes fixed obstructions, and positions of Agent 1 (different at each step)
  • Stack these maps to make a 3D grid
  • Plan the movement of A2 as a 3D path

Rules for Agent 2

  • Must step to next layer at each time step
  • Moving to same location in next layer; wait in position

Potential Issues

  • Not necessarily optimal path
  • Agents may have different speed
  • Paths generally get longer (wait state)
  • Can’t patch easily
49
Q

How can you use Pre-Calculate to improve A*?

A
  • A* is very slow when given many maps and agents
  • Can we pre-calculate all routes?
    • N nodes = database of NxN routes
  • Make optimisations: a route between two points is a whole set of routes
  • Only need to store next step: N x N x 1 byte
    • Or even better: N x N x 3 bits
50
Q

How can you use Hierarchy to improve A*?

A
  • Pre-compute inter-section routes
  • At run-time: insert start/end points, connect to local transitions, then apply A* to graph

Advantages:

  • Partially pre-computed
  • Can patch and rebuild at run-time
  • Faster (x10 on Baldur’s Gate)
  • Nearly as optimal (99%)
51
Q

How can you use Symmetry to improve A*?

A
  • A* and Dijkstra can run at arbitrar node graph, but many examples use a grid with 1/1.4 pair costs

The result is there exists many symmetric routes

  • A number of optimisations exploit this symmetry, such as Rectangular Symmetry Reduction
    • Conceptually similar to hierarchical approach, but identifies clear rectangular areas with symmetric blocks
    • Removes interior nodes, and links opposite nodes directly
    • Inserts start and end point into graph, then search
52
Q

What is Planning?

A

Given: initial state (s0) and goal state (g)

Find: sequence of actions leading to goal

53
Q

What are Actions?

A
  • Must be valid and optimal
  • Preconditions represent conditions under which an action is valid
  • Effects represent the new state after an action is performed
  • There are two things to be considered when choosing a set of actions:
    • They must be valid; its preconditions must be satisfied
    • They should be the optimal set of actions for solving the planning problem in question
54
Q

What does AI Planning consist of?

A
  • Firstly, we define the initial/goal states of a planning problem, to inform the AI agent
  • We also have to define both the preconditions and effects for every action, to inform the agent of the actions requirements, and the result of that action
  • Usually, the original planning problem is converted into a graph search problem, to be solved by certain algorithms
  • PDDL uses predicate logics to represent state/action

AI (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions