CAP4630 - Exam 2 (PPTs)

Ch 5&9

rules, system

using ____ to tell a _______:

* what to do in certain circumstances
* what conclusion to draw from what inputs

knowledge representation

rules for _________ _________:

usually expressed in the form of

IF A THEN B

A → B

antecedent

In A → B, A is called the:

consequent

* In A → B, B is called the:
* it usually represents an action or conclusion

rule

* can represent a recommendation or casual relationship
* ex: IF temp is below zero THEN weather is cold

rule-based system

* AKA production system
* computer system that uses rules to:
* provide recommendations or diagnoses
* determine a course of action
* solve a problem
* consists of:
* a fact base
* a knowledge base
* an inference base

fact base

database of facts

knowledge base

database of rules

inference engine

* interpreter
* controls process of deriving conclusions by forward or backward chaining

forward chaining

* start from a set of fact/rules
* try to find a way to deduce a conclusion (come up with course of action)
* data-driven → reasoning starts from set of data, ends up at goal

forward chaining steps

* keep checking facts in fact base
* see if any combination of facts matches all the antecents of 1 of the rules in the knowledge base
* if all antecedents of a rule are matched, the rule is triggered and fired → its conclusion is added to the fact database

conflict

a fact has mutliple conclusions and the conclusions are incompatible

conflict resolution methods

1\.) priority levels

2\.) longest-matching strategy

3\.) most recently added

priority levels

* each rule is given a priority level
* rule with highest priority is fired

longest matching strategy

* fire the rule that was derived from the longest antecedents
* if all antecedents of a rule are matched, then it should be fired → more specific match, less chance to go wrong
* ex: IF A AND B AND C THEN X vs. IF A THEN Y

most recently added

* fire the rule that matched the facts most recently added to the database
* recently added facts tend to be closer to possible conclusions

meta rules

* rules that define how conflicts will be solved
* treated as ordinary rules, given higher priority
* override normal rules, can control the conflict resolution process

meta knowledge

* used to resolve different types of conflicts
* built by knowledge engineer into the system

backward chaining

* start from conclusion → the hypothesis to prove
* show how conclusion can be reached from rules and facts

goal

hypothesis to be proven

backward chaining pros

* ensures that each action taken will definitely lead to the goal
* usually makes planning process more efficient

a

when is forward chaining more appropriate?

a.) when a set of facts is available but the conclusion is not already known

b.) when there are few (or just one) possible conclusions and many possible facts

b

when is backward chaining more appropriate?

a.) when a set of facts is available but the conclusion is not already known

b.) when there are few (or just one) possible conclusions and many possible facts

expert system

* designed to model the behavior of an expert in some field
* involves the end user, knowledge engineer, and domain expert

rule-based expert system

designed to use rules that an expert would use to draw conclusion from set of facts

end user

person who has the need for the system

knowledge engineer

* person who designs the rules for the system
* observes expert at work or asks the domain expert questions

domain expert

person who can explain to the knowledge engineer how to draw conclusions

inference engine, explanation system, knowledge base editor, user interface

List the components of the expert system shell

fact base

contains specific data in a particular case to derive a conclusion

knowledge base

contains domain knowledge used to derive conclusions

inference engine

uses forward chaining, backward chaining, or combination of both to make inferences

explanation system

explains how inference engine derives its conclusions, based on inference chain

knowledge base editor

allows knowledge engineer or expert to edit info in the knowledge base

user interface

provides access to inference engine, explanation system, and knowledge base editor

expert system shell

* does not contain domain specific or case specific info
* a general toolkit that can be used to build a number of different expert systems

constraint satisfaction problem

* problems limited by constraints
* solution: search
* ex: 8 queens problem

8 queens problem

8 queens must be placed on a chess board so that no 2 queens are on the same diagonal/row/column

8 queens problem search tree

* 8 levels deep
* 1st level has branching factor of 64
* 2nd level has branching factor of 63
* 8th level has branching factor of 57

8 queens problem simplified search tree

* each row and column must have 1 queen
* 1st level has branching factor of 8
* 2nd level has branching factor of 7
* 3rd level has branching factor of 6
* further simplified:
* each queen uses 1-2 diagonals
* branching factor is 5 or 6 after 1st choice

forward checking

* can significantly improve the performance of solutions for CSPs
* used to delete a set of impossible future choices
* if placing a queen results in removing all remaining squares → system can backtrack immediately

chronological backtracking

* problem: error may not be caused by most recently placed queen
* may backtrack moves that aren’t leading to an error

most constraint variable

* heuristic to further improve performance
* at each search stage, work with variable that has the least possible valid choices

heuristic repair

* can be used to improve performance of solutions
* generate an intuitive initial state using a simple heuristic and then try to fix it
* keep making changes to get closer to goal

min-conflicts heuristic

* heuristic repair in 8 queens problem
* moving from 1 state to another → likely to be closer to a solution
* select 1 queen that conflicts with another queen
* move selected queen to a square where it conflicts with as few queens as possible

local search

* starting from some initial configuration using random generating
* making small changes to config until a state is reached where no better successor states can be achieved
* tends to find local optimal solution instead of global optimal solution
* ex: hill climbing, steepest ascent hill climbing, exchanging heuristics

exchanging heuristics

* simplest manner of local search
* move from 1 state to another by changing one or more variables

k-exchange

* method where k variables are changed at each step
* 1-exchange for solving 8 queens problem
* using larger value of k will get a better result but requires more iterations

metaheuristics

* used to guide other heuristics
* get away from a local optimal solution and move towards the global optimal solution
* ex: iterative local search, tabu search, ant colony optimization, simulated annealing

iterative local search

* can overcome problem of local maxima → by running optimization procedure repeatedly from different initial states
* if used with sufficient iterations → will almost always find a global optimal solution
* purpose: provide a very good solution without exhaustively searching the entire problem space

tabu search

* maintain list of states that were already visited → to prevent repeating paths
* used in combination with another heuristic
* operates on principle: it’s worth going down a path that seems poor if it’s not repeating a visited path
* no repetitive path → good way to avoid local optimal solution

ant colony optimization (ACO)

* a metaheuristic
* foraging ants leave trail of pheromones to lead other ants to find food
* trail of pheromones is renewed regularly → if better route is found, old route will gradually fade
* used to find the best way to route cables through communication network

simulated annealing

* strength of a material
* if most of atoms are attracting other atoms → material will be very durable
* if excluding other atoms → material will be crispy
* AKA Monte Carlo simulation

annealing

* process of producing very strong glass or material
* atoms able to be relocated in a way so most of atoms are attracting others → great strength
* optimal arrangement of atoms have:
* greatest strength
* lowest thermodynamic free energy of system

state transitions

* cool down process is a sequence of this
* new state chosen by making small change to current state
* if new state has lower energy than current state → it’s accepted
* if new state has higher energy → Boltzmann acceptance criterion

simulated annealing

* to determine whether to move to higher energy or not:
* probability calculated, random number between 0 and 1 is generated
* if random number is lower than calculated probability, then new state is accepted
* when inc in energy is very high (or temp is very low) → very few states will be accepted as Boltzmann approaches zero
* inc energy → process can escape local minima
* extremely powerful method for solving complex problems

cooling schedule

* determines the way temp is lowered for successive iterations
* 2 popular cooling schedules (formulas)
* algorithm loops around temp until it reaches near zero value