Follow-up for Monday 4:15pm Tutorial

Master / Vertiefung Künstliche Intelligenz
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Follow-up for Monday 4:15pm Tutorial
Dear all,

yesterday, I had problems to understand the last ALC example on slide 481. In particular, I got the parentheses wrong.
So, here is an explanation, starting with a simpler example:

students ⊓ ∀audits_course.graduatelevelcourse

This expression describes students for which the following property is true: every course they audit is a graduate-level course.
In other words: students who only audit graduate-level courses

Now to the actual expression:

students ⊓ ∀audits_course.((∃hastutorial.T) ⊑ ∀has_TA.woman)

This describes students who only audit courses in category X, where X is (∃hastutorial.T) ⊑ ∀has_TA.woman.
A ⊑ B is defined as complement(A) ⊔ B. For more details see this thread: https://fsi.cs.fau.de/forum/thread/18212-Tableau-Contains-relation-in-NNF
T corresponds to the full set, so ∃hastutorial.T matches anything that has a tutorial. Therefore, c : (∃hastutorial.T) ⊑ ∀has_TA.woman means that c either doesn’t have a tutorial or all its TAs are women.

So the entire concept stands for ‘students that only audit courses that either have no tutorial or tutorials that are TAed by women’.

There was one other discussion we had: ternary (or more generally n-ary) constraints in a constraint network can be translated into binary constraints. This is briefly mentioned on slide 231.
Since I don’t understand that explanation, here is a different one:

Let’s say we have three Variables: X1, X2, X3 and we have a ternary constraint C on them.
So C ⊆ X1 x X2 x X3.

We can create an equivalent binary constraint network by removing C and instead introducing a new variable Y, which has the elements of C in the domain.
Now we add binary constraints C1 ⊆ X1 x Y, C2 ⊆ X2 x Y, C3 ⊆ X3 x Y, which require that the value C1 equals the first element of the value of Y etc.

A more detailed explanation can be found here: https://ktiml.mff.cuni.cz/~bartak/constraints/binary.html

Frederik

3

Thanks for the follow up! :slight_smile:

I have one very minor question remaining:

Could be nitpicking, but wouldn’t this be „more“ correct, since in the expression ((∃hastutorial.T) ⊑ ∀has_TA.woman) we’re talking about courses, and not tutorials?

4

Yes, I think you’re completely right there.

Thanks for pointing it out!

1 „Gefällt mir“