Teadmiste formaliseerimine

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.

Time, place, result

Lectures: Tuesdays 14:00-15:30 room SOC 312/313 (313 weeks 1,3,5,...; 312 weeks 2,4,6,...)
Practice sessions: 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 lecturers/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 tasks will start from the week two; i.e. no weekly task at the first week.

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.

Second lab

See Details of the KR second lab in 2025

Third lab: questions in NLP

• Experiment with neurosymbolic reasoning: LLM as a parser plus a symbolic reasoner: 2025
• Use a semantic parser and a reasoner to solve questions posed in natural language: 2025

Books to use

Main materials:

• Get the basic background about classical automated reasoning from the book chapter pages 297-345 by Tanel Tammet and optionally more details from the set of course notes from Geoff Sutcliffe.
• The book for natural language (NLP): Speech and Language Processing by Dan Jurafsky and James H. Martin. here is the 2nd edition and (suggested) here the web page for the draft 3rd edition. Recommendation: read from the beginning up to an including chapter 6: Vector Semantics and Embeddings, then read the appendix chapter Logical Representations of Sentence Meaning.

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:

• Andrej Karpathy nanoGPT and neural networks zero to hero course
• GPT architecture

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_intro2024.pdf

Recommended non-obligatory listening:

• Marcus episode on the Lex Fridman podcast https://lexfridman.com/gary-marcus/
• Gary Marcus (KR&R commonsense proponent) & Joshua Bengio (ML proponent) https://www.facebook.com/watch/live/?v=498403850881660&ref=watch_permalink read also the related Marcus paper https://arxiv.org/ftp/arxiv/papers/1801/1801.00631.pdf
• David Ferrucci (IBM Watson team leader) on the Lex Fridman podcast https://lexfridman.com/david-ferrucci/
• Tim Rocktäschel (Facebook A.I.) episode https://towardsdatascience.com/language-models-symbolic-learning-and-the-road-to-agi-75725985cdf7
• Reading, not listening: on Hybrid A.I. in image analysis https://knowablemagazine.org/article/technology/2020/what-is-neurosymbolic-ai

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

Lecture materials:

• We cover Background: relations of sql and logic E1

• and start with schemaless databases, RDF and RDFS E1 (also important for practice work)

See also

• Json in Postgresql: json datatype and functions for json

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

• Main lecture material: schemaless databases, RDF and RDFS looked at rdfs rule meanings in logic and sparql (up to page 30 in the presentation).
• 2023 Loengusalvestuse link.
• Rdf example developed during lecture

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

• Official w3c rdf and rdfs primer E2

The main materials covered in the lecture:

• json-ld (check out playground examples) E1 currently most popular triple representation language on top of json. see also wikipedia and w3c standard: for the latter, read the basic concepts chapter E2.
• rdfa E2 triple markup language suited for html, see also wikipedia
• schema.org (E2 you can surf on the schema.org site and understand/find answers there)) we looked at in the last lecture: property markup vocabulary suggested by Google, Microsoft and others.

And then have brief look (skim through) at:

• Official w3c owl primer but it is better to look at this intro presentation and continue with the owl rules presentation
• sparql tutorial and wikipedia take on sparql.

Certainly read:

• Hea jutt Whatever Happened to the Semantic Web?

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

More resources:

• sparql implementations in wikipedia
• various rdf tools listed at the bottom of the page

Lecture: what the reasoner does: 25. February

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

• rules, logic, provers E1
• logictools system running gkc reasoner in the browser: try out the "simple" and "complex" examples, read explanatory texts and the manual about predicate logic
• Have a look at the gkc github repo, including precompiled binaries for command line in the release 0.6.0 and the tutorial Examples/Readme.md.
• Travel examples from lecture 2021

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

• book chapter pages 297-345 and optional extras, 346-382; by Tanel Tammet.
• the set of course notes from Geoff Sutcliffe,
• the implementation presentation from Stephan Schulz
• 5-lecture prover course from the authors of Vampire
• and the readable-and-hackable PyRes reasoner for educational use.

Lecture: looking into main large knowledge bases

Guest lecture by Martin Verrev. 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:

• wordnet see tptp axioms
• dbpedia, see also classes and dbpedia wiki
• wikidata
• yago old page and new page
• babelnet described in wikipedia
• conceptnet described in wikipedia
• nell website (sometimes down) and in wiki and a good paper.
• framenet described in wikipedia, see example
• cyc but just read wikipedia and see whitepaper also tptp small random selection of axioms
• adimen-sumo see sumo in wikipedia and tptp axioms
• tptp: a large set of axioms and problems in logic usable for automated reasoners
• schema.org: property markup vocabulary suggested by Google, Microsoft and others.
• Wolfram alpha stuff

Block 4: natural language and question answering

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

Loengusalvestus teamsis

• These three wikipages give useful introductory details:Natural language processing, Knowledge extraction, Natural language understanding.
• Tanel Alumäe keelemudelitesse sissejuhatavad slaidid E1 ja loengusalvestus
• Väga hea õpik: 3. variandi draft või 2. variandi terve pdf.
  • Vektorsemantikast arusaamiseks loe 3. variandi ptk 3. N-gram Language Models ja siis chapter 6: Vector Semantics and Embeddings E2. Vektorsemantika kasutamine närvivõrkudes a la Bert ja GPT on hästi kirjas ptks 7: Neural Networks and Neural Language Models
  • Slaidid eelmiste peatükkide kohta: Ngrams ja word vectors.
• Google ngrams ja reaalne data.
• GloVE: a relatively simple vector representation
• Kui tahad katsetada toore Wikipedia dataga, siis saab loengus vaadatud töödeldud variante siit (tarballid sisaldavad datat, selgitavat README-d ja tarkvara selle ise ehitamiseks): a compacted pure-text version of full wikipedia, A lemmatized version of wikipedia texts, Several co-occurrence matrices and lists of top-co-occurring words for wikipedia
• Online demo of NTLK running some basic NLP tasks

Recommended listening:

• A cool 14-minute philosophy podcast episode to listen: Jonathan Webber on Deception With Words plus a a direct audio link (may expire at some point)
• A bit old (i.e. few new episodes) NLP highlights podcast series from the Allen institute for AI. Makes sense to start from the very first ones and pick these which have a title looking interesting to you. World-leading stuff and quite understandable.

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:

• Jurafsky & Martin book: neural networks and the slides. Alternative: CMU Mitchell course: neural networks basics
• Jurafsky & Martin: transformers and LLMs
• GPT arhitektuuri üldseletus: eriti head intuitsiooni ei maksa loota :)

Mida lisaks vaadata ja lugeda:

Kindlasti

• Andrej Karpathy progemisega-koos loeng: vaata see süvenemisega läbi! Vt ka Karpathy.

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:

• Jann LeCun: värske episood Lex Fridmani podcastist
• Wolframi pikk jutt lugemiseks koos närvivõrkudega üldisema taustaga
• Rodney Brooksi ennustused transformerite kohta

Optsionaalselt diipim arusaam:

• nanoGPT: [Karpathy reaalne näitekood GPT ise-ehitamiseks (otse eelmise loenguga seotud) : seda saab ilma suuremate pingutusteta käima linuxil ja macil, windowsil tekib aga suuremaid probleeme (proovisin ise linuxil järgi).
• Taustaks: Karpathy terve loenguseeria, kui sul tekib sügavam huvi
• Jurafsky & Martin ptk 10 Transformers and Pretrained Language Models kui tahad ise juurde lugeda.
• väga detailne ja mahukas videoloengutega deep learningu kursus, mh raamat.

Lecture: LLM usage patterns and RAG

loengusalvestus

NB! Loeng jäi 20 minutit hiljaks, sest meie audikasse planeeriti eksikombel ad hoc seminar, seega pidime kolima.

Useful reading:

• application landscape overview
• early taxonomy of real business use
• LLM improvement for applications and a basic overview of customizing llms
• Finetuning llama 2
• RAG:
  • simplest RAG intro E1
  • more rag details: a good architecture picture, may skip the improvements part after that
  • encoder/decoder and Seq2seq as a generalization of word2vec and openai embedding model api
  • vector database as a useful tool
  • different kinds of rag based on paper
  • rag by langchain
  • a fancy rag paper
  • example estonian startup using a kind of rag

Block 5: 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:

• generating computation tasks
• alphageometry
• a position paper on hybrid systems
• a large survey of tool use

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:

• tiny video of the Boston Dynamics robot failing: looks like a frame problem in the blocks world :)
• overview presentation: E1 must read.
• a classic AI philosophy paper about the frame problem: must read the first three pages (rest is optional).
• wikipedia about frame problem: E2 skim it through (no need to read all the details) to get a rough idea about different approaches to the frame problem. None of these are really good.

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).

• Simple axiomatization of the blocks world: E2 please also read through the comments explaining the axiomatization and queries!
• More complex blocks world axiomatization taken from the TPTP problem set for first order logic, concretely by concatenanting and commenting axiom sets PLA001-0.ax, PLA001-1.ax and queries PLA004-1.p, PLA005-1.p, PLA019-1.p

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:

• Problog start with a tutorial E2
• Try out some examples via browser from the tutorial

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:

• https://ceur-ws.org/Vol-3432/
• https://ceur-ws.org/Vol-3432/paper5.pdf
• https://ceur-ws.org/Vol-3432/paper8.pdf
• https://aclanthology.org/2023.emnlp-main.313.pdf
• https://ojs.aaai.org/index.php/AAAI/article/view/29938/31639
• https://arxiv.org/pdf/2404.12698
• https://proceedings.neurips.cc/paper_files/paper/2023/file/79fea214543ba263952ac3f4e5452b14-Paper-Conference.pdf
• https://proceedings.neurips.cc/paper_files/paper/2023/file/ba90e56a74fd77d0ddec033dc199f0fa-Paper-Conference.pdf