Artificial Intelligence/Knowledge Representation

For all but the most basic AI, there will need to be some representation of the surrounding environment and world.

See also: Discrete Math - Propositional Logic

Terminology

• Intelligent Agent - an entity that perceives some value from the environment, and makes rational choices accordingly. The agent attempts to do some action to or within said environment.
• Knowledge-Based Agents - Takes the "Intelligent Agent" a step further. They try to form internal representations of the world, and use inference to update these representations to the best of their ability.
• Knowledge Base (KB) - The set of information maintained by the Agent.
• (KB) World - The environment in which a KB Agent exists within and gathers knowledge about.
• (KB) Sentence - A language representation for some assertion about the world.
• (KB) Model - A "possible world", comprised of a set of specific state information.
• Entailment - With logic, when one thing naturally follows from another.
• Inference - The derivation of new sentences, from existing sentences.
• Valid Sentence - A sentence which is true in all models (aka, all possible worlds).
• Satisfiable Sentence - A sentence that is true in some models (aka, only certain possible worlds).
• Unsatisfiable Sentence - A sentence that is true in no models (aka, no possible worlds).
• Completeness - A KB in which "not a" is False also implies that "a" is True.
• Soundness - A KB in which "a" is True also implies that "not a" is False.

Knowledge Bases

The KB generally contains domain-specific content. Often, domain-independent algorithms act as the "inference engine", working to update the knowledge base and help the agent decide what action to take next.

If information available in the KB is both correct and complete enough, then the conclusion is guaranteed to be correct.

KB Representation

Often, the KB is represented in the form of "sentences":

• Each "sentence" is represented in the form of a formal "knowledge representation language" with a consistent syntax.
• Each "sentence" also represents some assertion about the surrounding world.
• Sentences should be defined such that conclusions can be drawn from them.
• Generally speaking, each new percept updates the KB with new information.

Forward-Chaining

Forward-Chaining is an algorithm which determines if a statement is true, using logical inference of existing known facts in the KB.

In essence, this is a data-driven algorithm, but may do significant work that is irrelevant to goal.

Tends to be good for things like object recognition and routine decisions.

Forward-Chaining Steps

1. Starts by grabbing the relevant known facts.
2. Determine implications (from two or more facts). The conclusion is added to the set of known facts in the KB.
3. Repeat steps with the expanded KB. This continues until the desired query is reached, or no further inferences can be made.

Backward-Chaining

Backward-Chaining is an algorithm which attempts to work backwards, from a desired query to prove as true.

Is a goal-driven algorithm, which attempts to prove relevant sub-goals until a valid path to "known facts" is determined.

Tends to be good for problem-solving, as overall runtime complexity can be much smaller than forward-chaining.

Backward-Chaining Steps

1. Starts by determining the query q which we wish to "prove correct".
2. Determine if q is already known. Otherwise, determines all premises of any rules which would conclude q.
3. Add these rules to a stack.
4. Take sub-goal off stack, recursively trying to check if it's already known, or determining rules which would conclude it.
   • If a given sub-goal fails, discard that sub-goal and move on to the next, assuming stack is not empty.
5. Continue popping sub-goals from stack and checking them, until original premise is proven true, or stack is empty.