Summary
Knowledge Representation - Summary Slides
- Course
- Institution
Summary of all the slides for the course Knowledge Representation, MSc AI.
[Show more]
Seller
Follow
tararoopram
Content preview
Lecture 1: Introduction to KR, the Course and "Logic Engineering”Definition of intelligence”
● carry out complex reasoning (solve physics problems, prove theorems)
● draw plausible inferences (diagnose cars, solve a murder mystery)
● use natural language (read stories and answer questions about them, carry out
extended conversation)
● solving novel complex problems (generating plans, designing artifacts)
● social activities that require a theory of mind
● we do not (only) mean: recognize familiar objects, execute motor skills, or navigate
around space; abilities we share with dogs and cats (and fish)
But isn’t modern AI all about Machine Learning ?
● Two main lines of development in AI
○ symbolic representations
○ statistical representation
● There have been alternating cycles of one dominating over the other in different decades
of the history of AI.
Statistical vs. symbolic AI: very different types of applications
● statistical:
○ pattern recognition (images, sound, shapes)
○ motor skills (robots)
○ speech generation (sound)
○ search engines
● symbolic:
○ planning (autonomous space missions)
○ reasoning (diagnosis, design, decision support)
○ language generation (conversations)
○ search engines
Human intelligence = thinking fast & thinking slow Stengths and weaknesses
● Scaleable:
○ Symbolic→worse with more data
○ Connectionist→worse with less data
1
,Symbolic knowledge is (not) a theory of everything!
The goal of logic in KR
● To state statements which are known to be true (the “knowledge base”)
● Some statements that describe the current state of the world (the “premises”)
● To state statements for which we want to check if they are true (the “conclusions”)
● To see if the conclusions can be derived from the knowledge base + the premises
through logical reasoning
● A variety of related tasks
The ingredients of a logic in KR
● How to formulate the statements (Syntax)
● Assign meaning to the statements (Semantics)
● Assign what can be derived (Calculus)
○ And all of this differs from application domain to application domain and even application
to application.
Logic Engineering
● Previously, you might have learned that Logics exist, how they are defined, what their
theoretical properties are, etc.
● Knowledge Representation is
○ The field of using the right logic for the right AI task
○ Evaluating logics w.r.t. a task or in general
■ Analytically (e.g. soundess, completeness, decidability, complexity, etc)
■ Empirically (practical complexity, practical completeness)
○ Adapt existing logics for a task (we do that in the course)
○ Develop new logics if needed
Logic Engineering: A (cooking) receipe
1. How to represent a real world problem with a formal system/logic?
2. Which formal system/logic is suitable?
3. Which reasoning task gives us a solution to our problem?
4. What syntax to use?
5. Which algorithm calculates the intended semantics?
● Is it good, and how long does it take?
2
,A toy example: politics in the news
● How to measure success of a political party in the news?
● Are two campaigns comparable? Do they have the same political impact?
● Assumption: Negative news has a higher impact! I need to be in the news twice to
compensate for one bit of negative news.
KR in a nutshell: (syntax, semantics, calculus)
KR in a nutshell 2 (Theory about Logics)
Problem solving by SAT solving → Checking for (in)consistency can be used to
solve problems:
● Many problems can be formulated as a set of constraints on the solution. The
constraints for Sudoku, e.g., can be stated as Propositional Logic constraints.
● Finding a solution
○ is asking if the set of constraints is satisfiable
○ is finding a satisfying truth assignment
● Thus: Solving the problem = finding satisfying truth assignment (that satisfies all
the constraints
3
, Testcase 1: Sudoku, PL and DPLL
1) Formulate the problem as Constraints:
● all squares must have exactly one number from 1-9
● no number can appear twice in a row, column or square
Propositional Logic for Sudokus
● Truth assignments (propositions) are sufficient: If 136 is true, there is value 1 in cell x=3,
y=6. If it is false, this is not the case.
● At least one number in each square:
○ “position 11 is a 1 or a 2 or 3 or a 4” ....
● Maximally one number true in each square
○ “if 111 then NOT 211 AND NOT 311... ” ....
● PL is not the only logic to represent Sudokus, but it is simple, and fast.
Finding Sudoku solutions with PL
● Remember: If 136 is true, there is value 1 in cell x=3, y=6. All we have to do is to look for
those propositions that are true w.r.t the constraints of the game, and the givens. These
are called the models.
● Searching for a solution to a sudoku will thus become a search for models.
● We will look at efficient methods to find models (SAT solving using Davis Putnam
Algorithms).
Logic Engineering for Sudokus=
1. How to represent a real world problem with a formal system/logic?
● Constraint satisfaction
2. Which formal system/logic is suitable?
● Propositional logic
3. Which reasoning task gives us a solution to our problem?
● SAT solving
4. What syntax to use?
● DMAC (or whatever)
5. Which algorithm calculates the intended semantics?
● Davis Putnam (DPLL)
● Is it good, and how long does it take?
4
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller tararoopram. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $15.92. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
48072 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 15 years now