edu(b)log

Frames cont. and Predicate Calculus

For the test (next Monday)

• Search algorithms
  • Best First
  • Depth First
  • Breadth First
  • Hill Climbing
  • A*
• El Paso
• GPS (go over proofs of theorems)
• Expert Systems
• Semantic Networks
• Frames

Predicate Calculus will not be included on the test.

Frames — A frame is a structure that represents a priori knowledge about something. Compare to a semantic network, which is an association of nodes. The example used in the book is a hotel form.

Another example is an office. There are different kinds of offices, and there are subclasses of those kinds of offices, and on and on.

You can also have a frame of 'restaurant' and within that frame there are different sub-frames.

Default reasoning is the knowledge we have about things that can be considered common knowledge. It can be considered true unless there is something you know that goes against it.

Procedure attachment (consult the book on this). Procedures are functions are stored in the frame entries and are executed as needed. They may ask for information from the user, etc.

Constraints are conditions that need to be satisfied before a frame is modified. Database systems are not intelligent; frames address the question of "how can you have an intelligent database system that won't let you make mistakes?"

(FLORIDA
	(POPULATION (16 MILLION) (PROCEDURE))
	(CAPITAL (TALLAHASSEE))
	(MAIN.CITIES (MIAMI, TAMPA, ORLANDO, JACKSONVILLE))
)

The superframe of Florida would be "American States." There may be another frame in between like "Southeastern State."

Predicate Calculus

Example: All Floridians are mortal. This is equivalent to: ∀x(F(x) ⇒ M(x)). The capital letters represent the predicates.

Example: Some Floridians are nice. Equivalent to ∃x(F(x) ∧ nice)

Example: All men are mortal. All Greeks are men. == All Greeks are mortal. Equivalent to:

      ∀x(M(x) → Mo(x))
      ∀x(G(x) → M(x))
   C: ∀x(G(x) → Mo(x))

Proof by contradiction is also known as an indirect proof. You negate what you need to prove.

Axiom 1:
∃xA(x)
C: A(a)

Axiom 2:
∀x A(x)
A(x)

⌉∀x(A(x)⇔∃x⌉A(x)
⌉∃x(A(x)⇔∀x⌉A(x)
∃x⌉(G(x)→Mo(x))
⌉(G(a)→Mo(a))
⌉(⌉(G(a)∨Mo(a))
G(a) ∧⌉Mo(a)

Some assertions:

1. ⌉M(x) ∨ Mo(x)
2. ⌉G(y) ∨ M(y)
3. G(x)
4. ⌉Mo(a)

Unify 2 and 3 and you get: (replace y with a, or {y/a}) M(a) which contradicts 1. You can replace the x with a.

Suppose you have G(a)∨⌉G(x)∨... This violates modus ponens.

Modus ponens:
p → q
p
--
q

Non-Rule-Based Knowledge Representation

There are other ways than rules to represent knowledge.

Semantic Netowrks — conceived around 1969. Often used as a form of knowledge representation. It is a directed graph consisting of vertices which represent concepts and edges which represent semantic relations between the concepts.

Frames — the frame problem was initially formulated as the problem of expressing a dynamical domain in logic without explicitly specifying which conditions are not affected by an action.

Predicate Calculus — a system of deduction extending propositional logic (equivalently, sentential logic). It is in turn extended by second-order logic.

We use words like 'bat' to refer to more than one thing. Take a sentence like "The astronomer married the star," for example. In our minds, we have a close association between astronomer and star, but you cannot marry a star (unless it's in a metaphoric sense). Some other examples are "the sailor at the submarine," "she put the flowers in the pot," "the farmer likes the plants," and "the pitcher put the batter in the oven."

George Miller is credited with coming up with the notion of cognitive psychology. He wrote a paper, "Magic Number 7 Plus Or Minus 2."

Types of Expert Systems

Homework 3 Notes

The representation of this list would be ((4 10) (14 2) (6 5)). For the homework, don't look for the most complex solution; sometimes the easiest solution is the best way. You can use any helper function you want for this assignment.

Example: Auto Mechanic

R1: If the engine is getting gas, and the engine will turn over then the problem is spark plugs.

R2: If the engine does not turn over, and the lights do not come on then the problem is the batter or cables.

R3: If the engine does not turn over, and the lights do come on then the problem is the starter.

R4: If there is gas in the tank, and there is gas in the carburetor then the engine is getting gas.

This is a Shallow (or superficial) expert system. We aren't going into great detail with how the cables work, etc. It's just a set of rules.

Deep (or model-based) expert systems can diagnose problems via rules or more complex models. They are based on causal relationships between the different components of what you're trying to model.

A physician will use reasoning to figure out what causes a particular problem, taking into account great detail about how different organs function and what affect different disorders has on those organ functions.

What advantages are there to the rule-based system (versus the model-based system)? It's simpler. The system design is generally not complicated. The model-based system is more complex but in the end more accurate. Model-based is also a better tool to represent, for example, the human body and its functions than a simple rule-based system would be.

There is also case-based reasoning. This means that you have in memory a set of cases you have already solved and when a new problem you examine your memory to see if it is similar to a problem you have solved before. If it not similar you produce a transformation in the problem that will use the solution you already know.

In case-based reasoning you have a set of cases stored in memory. You know the solution for those cases. A new problem comes and you make some transformation in the problem and you try to make the new problem identical to the one you know the solution for. We (humans) use that form of problem solving. For instance, if you go to the car example you may find a problem that is similar to the one you had two weeks ago. If a patient comes to a practitioner (s)he might say "gee, this is very similar to the patient I saw two weeks ago." You try to establish an analogy between problems.

You give rules to the machine for rule-based reasoning, and in case-based reasoning you also have to give cases to the machine.

A suspended hypothesis suggests that there is not strong enough evidence to make a decision. (This would be known as "inconclusive").

Rule Based (Expert) Systems

Expert Systems

You represent knowledge in an expert system using rules. That's why another name for expert systems is rule-based systems.

Some Famous Expert Systems

1. Dendral — analyse mass spectra
2. Mycin — diagnose infectious blood diseases and recommend antibiotics
3. Dipmeter Advisor — analysis of data gathered during oil exploration
4. CADUCEUS — blood-borne infectious bacteria

Example 1: Mycin Rule 209

IF
  1) The site of the culture is blood, and
  2) There is significant disease associated with the occurrence of the
     organism, and
  3) the portal of entry of the organism is GI, and
  4) The patient is a compromised host
THEN
  It is definite (1.0) that bacteroides is an organism for which 
  therapy should cover.

The antecedent is everything in the "IF" block. The conclusion is under the "THEN" statement.

Example 2: Mycin

IF
  1) The site of the culture is urine, and
  2) The method of collection of the culture is voided, and
  3) The colony count (in thousands) of the organism is
     greater than or equal to 100
THEN
  1) This is SUGGESTIVE evidence (0.5) that the infection that
     requires therapy is CYSTITIS, and
  2) There is SUGGESTIVE evidence (0.7) that there is a significant
     disease associated  with this occurrence of the organism.

The database of facts will include things such as site of culture, method of collection, etc. From the initial facts, you can infer new facts and store those also in the databse of facts. When you apply a rule to the database, if the rule becomes true, the rule fires.

Forward chaining — apply rules until no rule fires. *This is what Dr. Gomez said but it doesn't seem to make much sense.... It seems to make more sense to say that you apply rules until one does fire and then move forward... When/if that doesn't work, back up and try to find another rule the does fire and move forward again from there.

If the expert comes up with a new rule, it can be inserted into the beginning, middle, or end without making a difference. You can insert the rule anywhere. This is called a commutative production rule system.

Backwards chaining — the user will have a conclusion in mind and input antecedents until it backs up and confirms the conclusion.

Example 3

R1: If a and b then d.
R2: If k then a.
R3: If m then b.

Start state:

***DEF*********
*             *
*   k m       *
***************

End state:

***DEF*********
*             *
*   k m a b d *
***************

(The system backs up once it realizes that a and b are true.)

Example 4

1. In order to prove d, you need R1 (from Example 3). So you need to prove a and b.
2. In order to prove a, you need R2 to pass (so prove k).
3. In order to prove b, you need R3 to pass (so prove m).

Now we'll add a new rule to the system:

R4: If w then d.

You can use either R4 or R1 to prove d now. When you graph this out, it is called an and/or graph.

If you use backward chaining it will be more efficient. Forward chaining uses all the rules, whereas backward chaining tries only the relevant rules.

Rule based systems have the drawback of needing to know the guess.

searching algorithms

Complete means that the algorithm is guaranteed to find the solution to the goal. If you give it all the time in the universe, it will find the answer.

Depth-first is not complete. If the search space is very big there's no guarantee that it will back all the way out.

The breadth-first search is admissible/optimal and complete but its complexity is very high (it's inefficient). The depth first has a much smaller complexity.

When we do a heuristic/informed search, the key to a good heuristic algorithm is good heuristic. The better the heuristic, the better the algorithm is going to be.

A* is an optimal algorithm insofar as the heuristic associated with it is optimal. But it's not easy to determine whether the heuristic is admissible or optimal.

Breadth-first is a top-down search, and depth-first starts all the way down. The iterative deepening algorithm is a combination of the two.

The hill climbing is a depth-first algorithm but it doesn't keep anything in memory. If you are sure that your heuristic is good (infallible) then hill-climbing is great. You can't back out with this algorithm because nothing is stored in memory.

In chess, the smaller the number, the better for the human. The bigger the number, the better for the computer. (Minimax is the name of the algorithm but max-mini makes more sense).

Indirect Recursion occurs when one function calls another and the other calls the original back and forth. For example, if the function finds a list it might call max, then if max finds a list it might call min, and back and forth until only an atom is found.

α-β is one way to prune the tree.

α-cut-off

    [ ]
    /  \
   /    \
  (7)    o
        /|\
       / x x
      /  |  \
    (5) (20) (100)

β-cut-off

    [ ]
    /  \
   /    \
  (3)    o
        /|\
       / x x
      /  |  \
    (7) (2) (1)