Teadmiste formaliseerimine

Allikas: Lambda
teadmised

Name: Knowlege representation
Code: ITI8700
Link: http://lambda.ee/Teadmiste_formaliseerimine
Lecturer: Tanel Tammet tanel.tammet@ttu.ee ICT-426
Practice sessions: Riina Maigre
Archives of previous years: 2024.

NB! about next week, 25. February

The 25. February lecture will be a recording from 2024 pluss self-study reading and experiments only, not in the lecture room: please see the 25. Feb chapter below.


Time, place, result

Lectures (Tanel): Tuesdays 14:00-15:30 room SOC 312/313 (313 weeks 1,3,5,...; 312 weeks 2,4,6,...)
Practice sessions (Riina): Wednesdays 12:00-13:30 room U06A-204.

The lectures and sessions will be on site (physical room) plus teams. Later we may decide to do some lectures/practice sessions on teams only: this will be advertised on the page here early. Beware: recording may not always succeed.

Please join the teams of the course. The code for joining is y0bd8e5.

Weekly teams link for the lecture.

Weekly teams link for the practice session.

Grading

Practical work will give 50%, exam 50% of points, and weekly tasks additional extra up to 10%, underlying the final grade. The exam will consist of (a) several questions asking for the explanation of important concepts along with examples (b) some small excercises.

The materials below marked with the red E1 are the main materials for the exam, while E2 materials will also come up, but less and/or in a simpler form. The markings will be changed as the course progresses, i.e. the future ones will not necessarily persist!

To finish the course successfully, you need to

  • successfully pass three practical works
  • receive at least 1/3 of the max points at exam
  • get practice work + weekly tasks + exam at least 50% points altogehter.

Contents overview: what the course is about

The theme of the course: from SQL to natural language.

Hence the main focus of the course is on hybrid methods for knowledge representation and reasoning: symbolic AI, machine learning / neural methods and their neurosymbolic combinations. We look at this spectrum from simple (representing and using knowledge in databases) to complex (meaning of sentences in natural language and commonsense knowledge) tasks. A closely related subject is commonsense reasoning.

The course contains the following blocks:

  • Knowledge in SQL, RDF and JSON
  • Handling simple facts and rules in symbolic AI and logic
  • General-knowledge databases
  • Natural language and question answering
  • Uncertain knowledge and hybrid systems

Weekly tasks

The small weekly tasks are in addition to the practical work: their goal is to practice with the stuff presented at the last lecture.

The first weekly task

Ülesanne on eksperimenteerida veidi logictools.org saidiga ja teha ise läbi loengus toodud näited SQL data ja päringute esitamisest loogikas. Tähtaeg 25. veebruar.

Konkreetselt tee järgmist:

  • Eksperimenteeri veidi logictools.org "simple examples" valikuboksi näidetega basic ... equality, loe nende selgitusi ja püüa aru saada tõestustest.
  • Loe seejuures predikaatloogika väikest seletust about lehel kuni lausearvutuseni (seda pole enam otse vaja lugeda).
  • Kirjuta ise valmis näide vastavalt kursuse materjali Background: relations of sql and logic lk pealkirjaga "SQL join as logical rule", kus on toodud ühe client tabeliga ja client ning cars tabelitega näide sql päringute teisendamisest loogikasse (üks lihtne select ja üks join). Tee need näited reaalselt valmis nii, et logictools.org sööb nad sisse ja annab ootuspärase vastuse. Seejuures on sul vaja kasutada $ans predikaati, nagu "answers" näites toodud. Kui tahad mitut vastust (ei ole kohustuslik), siis vaata ka "multiple answers" näidet.
  • Saada näite-sisendid ja genereeritud tõestused õppejõule emailiga (riina.maigre at taltech.ee ja cc tanel.tammet at taltech.ee). Kui jääd nendega hätta, siis kirjuta, mida proovisid, too oma näitetekst ja selgita, mille juures hätta jäid (see on ka arvestatav tulemus): kirjuta aadressile riina.maigre at taltech.ee või tanel.tammet at taltech.ee ja pane pealkirja sisse mh sõna "formaliseerimine", et kirja kergesti üles leiaks.

Soovitused:

  • Negatiivset arvu sa logictoolsi vaikimisi süntaksiga otse sisestada ei saa: -200 interpreteeritakse kui loogilise eituse rakendamist 200-le. Kaks head võimalust negatiivse arvu sisestamiseks on kas kirjutada 0-200 või $difference(0,200).
  • Aritmeetika jaoks vaata help teksti Arithmetic peatükki.
  • Väiksem-tingimuse jaoks vaata complex examples valikuboksis "arithmetic" näidet.

Practical work

NB! The details of the labs are currently from 2024 and will be updated asap.

There are three labs.

The labs have to be presented (as a demo + small overview of the software and principles) to the course teachers and all students present at labwork time, either in the auditorium or over MS teams. The labs can be prepared alone or by teams of two or three people.

Each lab is evaluated independently and gives the same number of points. NB! When you do not meet the lab deadline, you will be awarded half of the points for this lab.

First lab

The 2025 task for the first lab is about handling and understanding triplet stores, meaning of rdf types/properties/etc and writing simple logical rules for answering questions.

Lab is updated! Future updates may include clarifications, but the task itself will not change.

Deadline: 5. March.

Second lab

See Details of the KR second lab in 2025. This is not updated yet!

Deadline: 9. April

Third lab: questions in NLP

These are also not updated yet!

Deadline: 14. May.

Books to use

Main materials:

Other useful books and tools for symbolic K&R:

  • logictools.org for experimenting with classical automated reasoning
  • Symbolic reasoning themes are covered in this book with (hopefully) freely accessible pdf-s via Taltech. See also slides for the book.
  • Similarly, the freely accessible pdf of the handbook of knowledge representation gives a detailed and thorough coverage of the subject; far more than necessary for the course.
  • You may want to get a small intro to Prolog by reading the first 100 pages of a classic Art of Prolog book. It is not strictly necessary for the course (we will not be using Prolog) but it surely helps. Besides, the book is interesting, quite easy to read and works out a lot of interesting examples.

Other useful material for neural NLP:

Observe that a noticeable part of the course contents are not covered by these books: use the course materials and links to papers, standards and tutorials provided.

Blocks and lectures: the main content of the course

The details and materials of lectures in the future are from 2024 and will be revised/extended. The materials of the current or passed lectures are up to date.


Block 1: knowledge in SQL, RDF and JSON

Lecture: Intro and background: 4. February

Intro presentation:

teadmised_intro2025.pdf

Recommended non-obligatory listening: Francois Chollet, Yann LeCun, Gary Marcus, Demis Hassabis, Ilya Sutskever, Ben Goertzel, Tim Rocktäschel,

Lecture: Nosql, json and rdf in databases: 11. February

Lecture materials:

See also

The weekly homework will be about trying out small things in logic: please try out logictools from "basics" to "equality" in simple examples selectbox. Details will appear after the lecture.


Block 2: handling simple facts and rules in symbolic AI and logic

Lecture: simple rules in rdfs, logic and owl: 18. February

Rdf example developed during lecture

Have a brief a look at this, no need to read thoroughly:

The main materials covered in the lecture:


And then have brief look (skim through) at:

Certainly read:

We will also start at looking and understanding the examples in logictools.org

More resources:

Lecture: what the reasoner does: 25. February

NB!This lecture will be the following recording from 2024 pluss self-study reading and experiments only, not in the lecture room:

Recording

We will consider the reasoning part of K&R to understand what provers do:

You may want to have a look at the additional materials - from easier to harder - from the

Lecture: looking into main large knowledge bases: 4. March

Slides:lecture slides E2, a tool to explore Wordnet taxonomies can be found here: https://github.com/martinve/wntool

You can search/investigate what kind of data is available and you can find out actual data from these databases with some work, by surfing on the web pages of the systems.

We will have a look at the goals, main content and differences between:


Block 3: natural language and question answering

Lecture: Intro to NLP, n-grams, word vectors

Loengusalvestus teamsis

Recommended listening:

Lecture: large language models (LLM), BERT and GPT families, plus intro to second lab

loengusalvestus koos teise praksi ülesannetega

Eesmärk: saada pinnaliselt aru LLM ja transformerite (NLP masinõppe põhiasjad) peamistest ideedest. Detailid on tegelikult keerulised ja nendest arusaamine võtab hulga rohkem aega, kui meil kursuses on, sestap lepime vähesega. Samas, kui sul endal huvi, siis loomulikult on teretulnud detailsem iseõpe.

Enne järgmisse materjali süvenemist tutvu kindlasti vektorsemantikaga, mida seletasime 14 märtsi loengus.

Loengus plaanime kasutada:

Mida lisaks vaadata ja lugeda:

Kindlasti

Paratamatult jääb enamus detaile loengus vähearusaadavaks (kui ise ei kuluta hulga aega järele katsetamiseks), aga sellegipoolest on see tõenäoliselt kõige parem loeng transformeritest: mingi tunnetuse sellest, et mis toimub, saab.

Optsionaalselt üldisem arusaam klassikutelt:

Optsionaalselt diipim arusaam:

Lecture: LLM usage patterns and RAG

Useful reading:

Block 4: hybrid systems and uncertain knowledge

We will focus on (a) world modeling and uncertainty in KR (open/closed world, frame problem, probabilities, exceptions) and (b) current research on building hybrid systems

Lecture: neurosymbolic reasoning, open/closed world, planning, frame problem, blocks world

For intro/recalling hybrid neurosymbolic reasoning:

See also an interesting recent piece about learning chess

We will first give a brief overview / reminder of the work/tasks in hybrid neurosymbolic AI.

We will then consider the issues regarding the world model and the output we expect from the neural part / LLM, along with some demonstrations of semantic parsing with and without the use of LLM.

We will then consider planning, open/closed worlds and the frame problem. The standard example for these is a blocks world: some blocks are on the table and the robot arm can lift single blocks and put them on other blocks or on the table. The arm cannot lift several blocks or a tower of blocks. Then, given a position of blocks at initial situation, can the robot arm create a required new position of blocks? Can we get the steps required? For getting the steps we use the $ans predicate.

One hard issue arising is that how do we know that doing some action like lifting a block does not create side effects like stumbling existing towers, moving other blocks etc? This issue is called the frame problem and it has no easy solutions.

Importantly, the frame problem arises since normal first order logic has

  • the open world assumption E1 (must read): if we do not have (and cannot derive) a positive fact like P(a) and neither a negative fact like -P(a), we assume we simply do not know which holds.

Prolog and databases operate under the

  • closed world assumption E1 (must read): if we do not have (and cannot derive) a positive fact like P(a), we automatically assume that -P(a) must be true. For example, Prolog "negation" really means "cannot prove". One consequence of this assumption is that we cannot represent real negation and disjunction in an OK manner (Prolog does not contain these) and cannot satisfactorily speak about "true", "false" and "unknown". See also negation as failure in prolog


Please look at and read these materials about the frame problem:

These two readings are optional:

  • frame problem at the Stanford Encyclopedia of philosophy: not obligatory, but a good read to get a better understanding.
  • another classic about frame problem: read this only if you became really really interested about the whole issue: it goes quite deep, although it is not especially technical.

You may also want to have a look at the algorithmic complexity and efficient solution algorithms, regardless of how we formalize the problem: see this article.

Next, importantly, you should experiment yourself with gkc and both of the following files. Please copy and read the files and understand the encoding. At the end of the files are several queries to experiment with: instructions are also there.

In both of them the predicate holds(X,Y) is used to describe something X about the blocks world (like, one block is on another or robot holds some block) and the second argument Y describes the state we have arrived to via robot actions from the original state (like, picked up a block in the initial state and then did put the block down on top of another).

To get a simple visualization of the blocks world, have a look at this tiny video.

Blocks world examples, then reasoning with uncertainty

Loengu sissejuhatava osa presentatsioon: Reasoning_with_uncertainty.pdf E1.

Almost all the knowledge we have is uncertain: there are many exceptions to a rule or a fact/rule holds with some vague probability. Notice that, in contrast, typical databases in companies contain facts with very high certainty, but they do not contain rule or commonsense knowledge: the latter is built into brittle software code of systems using these databases.

We will consider two different ways to tackle uncertainty:

  • Numeric methods: uncertainty is estimated with probability-like numbers of various kinds.
  • Discrete methods: no numbers used. Instead, uncertainty is described as exceptions or beliefs of people.

NB! Both of these ways are hard to actually implement, neither have they been understood very well, despite an immense amount of research and papers. For example, typical machine learning methods operate with extremely vague probability-like numbers and do not attempt to put these numbers into a real properly-theoretical-and-correct probabilities framework.

The main material for reading about numeric methods is an overview-followed-in-depth by the lecturer Numeric uncertainty: (E2 up to and including the chapter 3, see also E2 tags inside)

  • Read carefully up to and including the chapter 4 "Different ways to encode confidences in logic" and have a quick look at all the wikipedia links.
  • Skim through the later parts and look only into these subchapters which you found interesting.

Next,

  • Read the paper E2 about confidences. containing intro, algorithms and experiments. Then look at the web page with the confer reasoner and a wealth of examples.
  • Read the paper E2 about exceptions (default logic). containing intro, alorithms and experiments. Then look at the web page with the gk reasoner and a wealth of examples.

Next, have a brief look at a good example system doing some specific kinds of probability reasoning:


Lecture: continue with uncertainty, then intro to lab 3: 9 April

Numeric confidences and probabilities.

A presentation of our paper about implementing numeric confidences. Here are examples, a binary, etc.

Lecture: continuing with uncertain knowledge: 16 aprill

Wider background: non-monotonic logic

A presentation E2 of our paper about implementing default logic E1. Here are examples, a binary, etc.

Additionally, we look at non-montonic logic using s(CASP) and dlv. Both are examples of Answer set programming (ASP) and related to datalog. For ASP, have a look at this intro, written by Ilkka Niemelä who is currently the president (rehtori) of the Aalto University


Lecture: Semantic parsing

Loenguslaidid: Media:KR_2024_Parsing_01.pdf E2

Semantic parsing continued

Loenguslaidid (lisatud linkidega): Media:KR_2024_Parsing_02.pdf E2


Topics in neurosymbolic reasoning ja konsultatsioon eksamiks

Some papers to explore:

Pärit leheküljelt "http://lambda.ee/w/index.php?title=Teadmiste_formaliseerimine&oldid=22001"