Samenvatting
Knowledge Representation - Summary Slides
Summary of all the slides for the course Knowledge Representation, MSc AI.
[Meer zien]Voorbeeld 4 van de 84 pagina's
Voorbeeld 4 van de 84 pagina's
In winkelwagengesponsord bericht van onze partner
Verkoper
Volgen
Voorbeeld van de inhoud
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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper tararoopram. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €14,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 48298 samenvattingen verkocht
Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen