child_of(mary, steve). child_of(mary, anne). child_of(alice, anne). child_of(alice, steve). child_of(jane, steve). child_of(leslie, steve). female(mary). female(alice). female(jane). sisters(Person1, Person2) :- child_of(Person1, Parent1), child_of(Person1, Parent2), child_of(Person2, Parent1), child_of(Person2, Parent2), not(Parent1 = Parent2), female(Person1), female(Person2), not(Person1 = Person2).
Query:
?- sisters(Sis1, Sis2).
Answer:
Sis1 = mary, Sis2 = alice; Sis1 = mary, Sis2 = alice; Sis1 = alice, Sis2 = mary; Sis1 = alice, Sis2 = mary; false.
Comment:Essentially there are two persons here who are sisters,
namely mary
and alice
, so we intuitively
expect a single answer, effectively verifying that
sisters(mary, alice).
is true. However, Prolog also
proves sisters(alice, mary).
which doubles the number
of solutions found. It also proves each of these two ways, binding
Parent1
to steve
and Parent2
to anne
in one case, and vice-versa in the other case,
again doubling the number of solutions (to give 4 altogether).
?- believes(X, likes(mary, pizza)) = believes(frank, likes(Y, pizza)).
Answer: It succeeds, with bindings:
X = frank, Y = mary
Comment: Because X and Y start with capital letters, they
are variables, so they match the "atoms" frank
and
mary
on the opposite side of the equals sign.
Integers and floating point numbers are built into most programming languages, including Prolog. However, suppose that numbers and arithmetic operations were not available. It is still possible to define numbers in Prolog and to write programs to implement simple arithmetic operations. In the following question, you MUST NOT use any of Prologs built-in arithmetic predicates such as is, <, +, *, etc. (except in part (f)). Also, do not use the cut operation (!) in your program.
A positive integer can be defined as zero or the successor of another number. Thus, zero can be represented by 0 and a number, such as two, can be represented by s(s(0)), where two is the successor of the successor of 0. Thus s(X) can be thought of as X+1. We call numbers written like this s-expressions.
In parts (c) to (f), don't worry about what happens if X (and Y and Z) are not s-expressions. You don't have to cope with this, and in particular, you don't have to check for this.
See also the Wikipedia entry on the Peano axioms. This link is just for interest - the material at the link is not examinable.
?- s_number(s(s(0)). true.
Answer:
s_number(0). s_number(s(X)) :- s_number(X).
?- minus1(s(s(0)), Y). Y = s(0) ?- minus1(0, Y). false.
Answer:
minus1(s(X), X).
?- subtract(s(s(s(s(0)))), s(s(0)), Z). Z = s(s(0))
Answer:
subtract(X, 0, X). subtract(s(X), s(Y), Z) :- subtract(X, Y, Z).
?- value_of(s(s(s(s(0)))), Y). Y = 4
Answer:
value_of(0, 0). value_of(s(X), Y) :- value_of(X, Z), Y is Z+1.
NB: This question is about semantic nets, not NLP.
Answer:
Answer:
loop
Answer: Pick any two of:
Answer: Head feature values are inherited from the head subsconstituent of the object: thus an S inherits its VAR feature from its VP, a VP from its V, and an NP from its head N, NAME, or PRO.
Answer: A → t or A → tN, where A and N are non-terminals, and t is a terminal symbol.
Answer: plur transforms a predicate like dog1, which is true of a single dog, into a predicate plur(dog1) which is true of a set of more than one dog.
Answer: As well as predicate operators, there are the following components to the logical form language:
terms | like | fido1 and name(j1, 'John') |
predicates | like | bites1 |
logical operators | like | not, & |
propositions | like | bites1(fido1, postman1) |
quantifiers | like | every, most, the |
modal operators | like | believe, pres, assert |
term constructors | like | pro(—, —) and name(—, —) |
Answer: likes(mary, pizza)
Answer: Subcategorization refers to the property of verbs
(and adjectives) of allowing only certain patterns of complement
structure to follow them. For example, laugh cannot be followed
by an NP in English, (so it subcategorizes none
) and tell
can be followed by a NP and then a VP in the infinitive form, such
as tell Peter to buy petrol (so it subcategorizes np_vp:inf
).
Answer: The major exhibits age.
Answer: Two possible answers: here is one - rules must be of the form λAρ → λσρ where λ and ρ are (possibly empty) strings of alphabet symbols, A is a non-terminal, and σ is a string of alphabet symbols.
Answer: Two feature values unify by intersection, and
they agree if they have non-empty intersection.
{3s,3p} ∩ {1s,2s,1p,2p,3p} = {3p}, which is non-empty, so these
two features agree.
Lexicon must cover any words to be processed.
time | NOUN, VERB |
flies | NOUN, VERB |
it | PRONOUN |
like | PREP, ADJ, VERB, NOUN, ADV, CONJ |
an | DET |
arrow | NOUN |
Grammar
Rule | Name |
S → NP VP | G-S1 |
S → VERB NP | G-S2 |
NP → NOUN | G-NP1 |
NP → PRONOUN | G-NP2 |
NP → DET NOUN | G-NP3 |
PP → PREP NP | G-PP1 |
VP → VERB | G-VP1 |
VP → VERB PP | G-VP2 |
Note: The numbers that are part of active arc names are not especially significant. All that matters is that different arcs have different names.
*sentence*: time flies *current-position*: 2
*constituents*: add
NOUN2: NOUN → "flies" from 1 to 2
VERB2: VERB → "flies" from 1 to 2
NP2: NP → NOUN2 by rule TF-NP1 from 1 to 2
VP2: VP → VERB2 by rule G-VP1 from 1 to 2
S1: S → VERB1 NP2 by rule G-S2 from ARC2 from 0 to 2
S2: S → NP1 VP2 by rule G-S1 from ARC1 from 0 to 2
*active-arcs*: add
ARC4: S → NP2 • VP by rule G-S1 from 1 to 2
ARC5: S → VERB2 • NP by rule G-S2 from 1 to 2
ARC6: VP → VERB2 • PP by rule G-VP2 from 1 to 2
Full parses:
(S (NP (NOUN "time")) (VP (VERB "flies")))
(S (VERB "time") (NP (NOUN "flies")))
*sentence*: it *current-position*: 1
*constituents*:
PRON2: PRON → "it" from 0 to 1
NP1: NP → PRON2 by rule G-NP2 from 0 to 1
*active-arcs*:
ARC1: S → NP1 • VP by rule G-S1 from 0 to 1
*sentence*: it flies *current-position*: 2
*constituents*: add
NOUN1: NOUN → "flies" from 1 to 2
VERB1: VERB → "flies" from 1 to 2
NP2: NP → NOUN1 by rule G-NP1 from 1 to 2
VP1: VP → VERB1 by rule G-VP1 from 1 to 2
S1: S → NP1 VP1 from ARC1 from 0 to 2
*active-arcs*: add
ARC2: S → NP2 • VP by rule G-S1 from 1 to 2
ARC3: VP → VERB1 • PP by rule G-VP2 from 1 to 2
ARC4: S → VERB1 • NP by rule G-S2 from 1 to 2
*sentence*: it flies like *current-position*: 3
*constituents*: add
NOUN2: NOUN → "like" from 2 to 3
CONJ2: CONJ → "like" from 2 to 3
ADV1: ADV → "like" from 2 to 3
ADJ1: ADJ → "like" from 2 to 3
PREP1: PREP → "like" from 2 to 3
VERB2: VERB → "like" from 2 to 3
NP3: NP → NOUN2 by rule G-NP1 from 2 to 3
S2: S → VERB1 NP3 from ARC4 from 1 to 3
VP2: VP → VERB2 by rule G-VP1 from 2 to 3
S3: S → NP2 VP2 from ARC2 from 1 to 3
*active-arcs*: add
ARC5: S → NP3 • VP by rule G-S1 from 2 to 3
ARC6: PP → PREP1 • NP by rule G-PP1 from 2 to 3
ARC7: VP → VERB2 • PP by rule G-VP2 from 2 to 3
ARC8: S → VERB2 • NP by rule G-S2 from 2 to 3
*sentence*: it flies like an *current-position*: 4
*constituents*: add
DET1: DET → "an" from 3 to 4
*active-arcs*: add
ARC9: NP → DET1 • NOUN by rule G-NP3 from 3 to 4
*sentence*: it flies like an arrow *current-position*: 5
*constituents*: add
NOUN3: NOUN → "arrow" from 4 to 5
NP5: NP → NOUN3 by rule G-NP1 from 4 to 5
NP4: NP → DET1 NOUN3 from ARC9 from 3 to 5
PP1: PP → PREP1 NP4 from ARC6 from 2 to 5
S4: S → VERB2 NP4 from ARC8 from 2 to 5
VP3: VP → VERB1 PP1 from ARC3 from 1 to 5
S5: S → NP1 VP3 from ARC1 from 0 to 5
*active-arcs*: add
ARC10: S → NP5 • VP by rule G-S1 from 4 to 5
ARC11: S → NP4 • VP by rule G-S1 from 3 to 5
Full parse:
(S | (NP | (PRON "it")) |
(VP | (VERB "flies") | |
(PP (PREP "like") (NP (DET "an") (NOUN "arrow")))))) |
Answer: For solution, see lecture notes. Here's a concrete example, from question 3 of the Machine Learning Exercises.
The attributes and their possible values are:
texture | temperature | size | class |
smooth | cold | large | yes |
smooth | cold | small | no |
smooth | cool | large | yes |
smooth | cool | small | yes |
smooth | hot | small | yes |
wavy | cold | medium | no |
wavy | hot | large | yes |
rough | cold | large | no |
rough | cool | large | yes |
rough | hot | small | no |
rough | warm | medium | yes |
There are 7 positive examples and 4 negative ones overall, so the overall entropy is –(7/11)×log_{2}(7/11) – (4/11)×log_{2}(4/11) which is about 0.94566.
In the exam, you will not have a calculator. You will not, of course, be expected to work out the logarithms by hand. :-) You should therefore leave the entropy as an unevaluated expression: –(7/11)×log_{2}(7/11) – (4/11)×log_{2}(4/11).)
There are 3 values for the texture attribute: smooth, wavy and rough.
For smooth, there are 4 positive examples and 1 negative, so the entropy is -(4/5)×log_{2}(4/5) - (1/5)×log_{2}(1/5) which is about 0.7219.
(Again, in the exam, you would leave this as an unevaluated expression.)
For wavy there is one positive and one negative example, so the
entropy is -(1/2)×log_{2}(1/2) - (1/2)×log_{2}(1/2) = 1.
(I would expect you to know that log_{2}(1/2) = –1, and so evaluate this expression.)
For rough there are two positive and two negative examples, so the entropy is -(1/2)×log_{2}(1/2) - (1/2)×log_{2}(1/2) = 1.
Expected information for a split on texture is thus:
Expected information gain for a split on texture is thus 0.94566 - 0.8736 = 0.07206.
Answer:
Δw_{ji}
= η ×
δ_{j} ×
y_{i}
where
Δw_{ji} is the weight change from unit i
to unit j,
η is the learning rate,
δ_{j} is the local gradient (whose definition is
complex and goes beyond what is required for this question), and
y_{i}
is the input signal to node j.
Answer:
CRICOS Provider Code No. 00098G