Summary of "Knowledge - Lecture 1 - CS50's Introduction to Artificial Intelligence with Python 2020"
Summary of "Knowledge - Lecture 1 - CS50's Introduction to Artificial Intelligence with Python 2020"
Main Ideas and Concepts
-
Introduction to Knowledge in AI
- Intelligence relies heavily on knowledge and reasoning.
- AI agents can be knowledge-based, representing facts internally and reasoning to draw new conclusions.
- Reasoning with knowledge is formalized using logic, moving from natural language to formal languages understandable by computers.
-
Propositional Logic
- Propositional symbols represent facts (e.g., P = "It is raining").
- Logical connectives combine propositions:
- Not (¬): negation
- And (∧): conjunction
- Or (∨): disjunction (inclusive or)
- Implication (→): if P then Q
- Biconditional (↔): P if and only if Q
- Truth tables define the semantics of these connectives.
- A model assigns truth values to propositional symbols, representing a "possible world."
- A knowledge base (KB) is a set of propositional sentences known to be true.
- Entailment (⊨): KB entails α if in every model where KB is true, α is also true.
- Inference is the process of deriving new knowledge (conclusions) from known facts.
-
Example of Reasoning with Propositional Logic
- Using statements about Harry Potter visiting Hagrid or Dumbledore and weather conditions, the lecture illustrates how to draw conclusions logically.
- Example inference: From "If it didn’t rain, Harry visited Hagrid," "Harry visited Dumbledore or Hagrid but not both," and "Harry visited Dumbledore," conclude "It did rain" and "Harry did not visit Hagrid."
-
Model Checking Algorithm
- To check if KB entails a query α:
- Enumerate all possible models (assignments of true/false to symbols).
- Verify that in every model where KB is true, α is also true.
- If so, KB entails α; otherwise, it does not.
- Model checking is simple but computationally expensive (exponential in the number of symbols).
- To check if KB entails a query α:
-
Programming with Propositional Logic
- Python classes represent logical symbols and connectives.
- Example code encodes knowledge about Harry Potter’s visits using these classes.
- Model checking function recursively enumerates all models to verify entailment.
-
Knowledge Engineering
- The process of translating real-world problems into Propositional Logic symbols and formulas.
- Examples:
- Clue game: Represent suspects, rooms, weapons as propositional symbols; encode knowledge and use inference to deduce the murderer, location, and weapon.
- Logic puzzles: Assign people to houses using propositional symbols and logical constraints.
- Mastermind game: Deduce correct color positions based on guesses and feedback.
-
Limitations of Model Checking
- Model checking is inefficient for large numbers of variables due to exponential growth of models.
- Motivates the need for more efficient inference methods.
-
Inference Rules
- Alternative to model checking; apply rules to derive new knowledge without enumerating all models.
- Examples:
- Modus Ponens: From (α → β) and α, infer β.
- And Elimination: From (α ∧ β), infer α or β.
- Double Negation Elimination: From ¬¬α, infer α.
- Implication Elimination: (α → β) ≡ (¬α ∨ β).
- Biconditional Elimination: (α ↔ β) ≡ (α → β) ∧ (β → α).
- De Morgan’s Laws:
- ¬(α ∧ β) ≡ ¬α ∨ ¬β
- ¬(α ∨ β) ≡ ¬α ∧ ¬β
- Distributive Laws:
- α ∧ (β ∨ γ) ≡ (α ∧ β) ∨ (α ∧ γ)
- α ∨ (β ∧ γ) ≡ (α ∨ β) ∧ (α ∨ γ)
-
Theorem Proving as a Search Problem
- States: sets of known sentences.
- Actions: applying inference rules.
- Transition model: knowledge base updated with new inferences.
- Goal test: whether the query is proven.
- Path cost: number of inference steps.
- This frames logical proof as a search problem, similar to pathfinding or game playing.
-
Resolution Inference Rule and Algorithm
- (Content incomplete in the source text.)
Category
Educational
