10. Describe the phases of the construction(!) of a probabilistic knowledge base using Bayesian network representation. (4 p)
11. What is the „Ockham razor”/principle and its relevance for statistical machine learning. (3 p)
2. What are the problems with local search (optimization) methods (4p)? Is there any global optimization method (2p)?
6p
3. What are the definitions of soundness and completeness(4p)? What is the resolution inference step (4p)? Show with truthtables that it is sound (6p). Is it complete in firstorder logic (2p)?
16p
5, Define formally the Maximum Expected Utility principle (4p). Give an example for a preference relation that can not be represented by utilities (2p). Select the best action in the following case (4 point):
Action

Probabilities of outcomes

Utilities of outcomes

1

0.3, 0.3,0.4

3, 2, 10

2

0.7, 0.2, 0.1

2, 9, 40

10p
++, Explain the tradeoff between model complexity and sample size in statistics/machine learning? What is bias and variance (selection error)? (8p)
8p
Q1A. The FESTIMO syllogism is as follows: x. B(x) A(x)
x. C(x) A(x)
x. C(x) B(x)
Is it sound? Prove your answer with resolution! Take care of the Skolemization. (8 points)
Q2A. What is the type of the next statement: valid, satisfiable, not satisfiable, none of these. Prove your answer with truth tables. (5 points)
(A ¬B) (C B).
Q3A.
Define the completeness of a proof method! (5 points)
Q4A. In a simple world a
Card(c) can be
TurnedUp(c,s) or
TurnDown(c,s), which can be changed by the
Flip operator or leave unchanged by the operator
DoNothing. Define a successorstate axiom in situation calculus for the
TurnedUp state. (8 points)
Q5A. Apply the algorithm
A* from A to B and fill the cells according to the scheme on the right (
h the value of heuristic,
g denotes the minimal cost of the path,
f is th total cost, and
a is the altitude of the cell). The applied heuristics is the Manhattan distance (minimum number of steps using only the four neighbours). The real cost
to a neighbouring cell is 1 + , where
is the distance between the altitudes if we step to higher place, otherwise it is 0. Indicate the optimal path on the map! (12 points)
Q6A. What is an empty plan? Give a formal description and an example. (12 points)
Q7A. What is the best search method, if we have no heuristic function, a priori knowledge about the depth of the solution, and the state space is infinite? Why (what are the properties)? (5 points)
Q8A. Define the diagrams of the
reflex and
the goaloriented agents. (5 points)

4. What is the meaning of true positive, false positive, true negative, false negative in (logical) hypothesis learning (4p) How can these errors be corrected? (4p)
6. What is the learning framework for the following equation? (3p) What are the meaning of the symubols (
U,
R,
,
i,
j)? (4p) Explain the corresponding concepts (3p)
U(
i)
U(
i) +
(
R(
i) +
U(
j) –
U(
i))
5. Define dseparation and explian its use in Bayesian networsk. Describe at least 5 conditional independences implied by the Bayesian network in the figure
K1. Three heuristics was proposed for the puzzle game based ont he following functions:
h_{1}(tile) = x+y,
h_{2}(tile) = max(x, y), and
h_{3}(tile) = sqrt ((x)^{2}+(y)^{2}).
The „estimed distance” of a configuration from a goal is given by the sum _{lapka} h(lapka). Compute the „estimed distance” from the start state on the left (Kiindulóállapot) to the goal state on the right (Célállapot), using all three heuristic function. (4p)
Characterize the heuristics with the „h_{x} admissible”, „h_{x} not admissible”, „h_{x} dominates h_{y}”. (4p)
P1. In a parity function over three arguments the output is 1, if exactly one of the three inputs is odd, otherwise the output is 0.
Can we implement this function with a multilayer perceptron? Specify a network or show why this function can not be represented! (6p)
L1. Convert to a clause form! (5p)
" a, s Risky(a,s) Ù
(Ø $
b Great(b,s) Ú
Good(b,s) Ú
Mediocre(b,s))
® Action(a, s)
L2. Show the type of the following expression using truthtables! (4p)
(A ® B) XOR (B ® A)
A1. What are the main characteristics of the environment? (3p)
K1. In the search tree below the costs of the movements and the heuristic estimates are shown. Which node will be expanded next in
(i) in uniform cost search? (3p)
(iv) in A* search? (3p)
P1. Is it possible to implement a parity detector with a perceptron? Specify the parameters or show that is impossible. (6p)
L1. Using the statements below
P (R V S), ¬P (R V S), ¬S, (R V U) T
(a) transform to clause form (CNF)! (3p)
(b) Prove T with resolution! Draw the proof tree! (5p)
T1. What is „Ockham razor”? (3p) What is the danger of using powerful models? (4p) Demonstrate it in scalar function learning (3p).
T2. Specify the logical expression represented by the decision tree below! (7p)
1. Is it possible to achieve linear time(!) complexity in solving a singlestate problem? Explain your answer! (8p)
2. What is the resolution inference step (4p)? Show its soundness with truthtables for three variables (8p).
3. What does semidecidability of proof methods mean in firstorder logic? Explain and illustrate it with considering a true and a false statement. (6p)
4. Consider the following naive Bayesian network with discrete variables(number of values are indicated in parenthesis). Assuming that the edges are necessary and sufficient construct a Bayesian network structure for the following ordering of the variables: E, F, G, D (meaning that arrows are allowed only from earlier to later variables) (6p). Compare the number of parameters used in the networks. (6 p)
D(4)
E(2)
F(3)
G(4)
5. Define the maximum expected utility principle (4p) Select the best action in the following case (6 point):
Action

Probabilities of outcomes

Utilities of outcomes

1

0.2, 0.4,0.4

2, 5, 1

2

0.6, 0.3, 0.1

2, 1, 10

3

1

2

6, Derive the number of functionally different decision trees over n ternary (3valued) attributes and binary output (4p). Construct an equivalent logical expression for the following decision tree (8p):
A/1. What is the definition of partial observability? Draw an appropriate agent architecture for a partially observable environment and explain which part is a consequence of the partially observable property (10p)
A/2. What is an admissible heuristics? Give an example and a counterexample (5p)
A/3. Give examples for search methods with different space and time complexity (use
the maximum branching factor b, depth of least cost solution d, and maximum depth of diameter m ). Explain the properties of the iterative deeping search (10 p)
A/4. Find an optimal solution using A* in the search tree below. S denotes the initial state, G indicates goal states, the heuristic values of the states are shown in the nodes, costs of actions are indicated along the edges. (10p)
A/5. Define completeness and soundness in theorem proving. Give an example. (5p)
A/6. Decide with truthtable what is the status of the following statements (not satisfiable, satisfiable, or valid): (10p)
a. (Smoke Fire) (¬Smoke ¬Fire)
b. Big Silent (Big Silent)
A/7. Tim, Neal és Elisabeth are Club members. Club members are hiker or skier. Hikers do not like rain, skiers like snow. Elisabeth does not like what Tim likes, and she likes what Tim does not like. Tim likes rain and snow.Is there any club member who is hiker, but not skier? Answer this question with resolution!
M(x) denotes that x is club member, H(x) denotes that x is Hiker, S(x) denotes that x is a skier, L(x,y) denotes that x likes y (if x is a club member and y denotes rain or snow): (10p)
x. S(x) v H(x)
x. H(x) L(x, Rain)
x. S(x) L(x, Snow)
y. L(Elisabeth, y) L(Tim, y)
L(Tim, Rain)
L(Tim, Snow)
question: x. M(x) ^ ~S(x)
A/1. What is the definition of partial observability? Draw an appropriate agent architecture for a partially observable environment and explain which part is a consequence of the partially observable property (10p)
A/2. What is an admissible heuristics? Give an example and a counterexample (5p)
A/3. Give examples for search methods with different space and time complexity (use the maximum branching factor b, depth of least cost solution d, and maximum depth of diameter m ). Explain the properties of the iterative deeping search (10 p)
A/4. Find an optimal solution using A* in the search tree below. S denotes the initial state, G indicates goal states, the heuristic values of the states are shown in the nodes, costs of actions are indicated along the edges. (10p)
A/5. Define completeness and soundness in theorem proving. Give an example. (5p)
A/6. Decide with truthtable what is the status of the following statements (not satisfiable, satisfiable, or valid): (10p)
a. (Smoke Fire) (¬Smoke ¬Fire)
b. Big Silent (Big Silent)
1. What is the main assumption of the declarative approach in AI (compared to the procedural approach)? (5p)
2. Using three nodes, give an example for an inconsistent, but admissible heuristic function! (5p)
3. Which node will be selected from the queue containing the leaf nodes of the tree in Fig. 1 (assuming that equivalent nodes are selected from left to right) in case of
• depthfirstsearch:
• breadthfirstsearch
• uniform cost search:
• iterative deepening search:
• greedy search:
• A*:
(10p)
Fig.1. Search tree with costs on edges and heuristic values indicated by h.
4. Apply the MINIMAX algorithm for the tree in Fig.2., propagate the values and indicate the MINIMAX moves! (10p)
Fig.2. MINIMAX tree.
5. Estimate the effective branching factor for the search tree in Fig.3. (the goal state is the node 12, in bold)! (10p)
Fig.3. Search tree with found goal (in bold).
6. There is a contest with three players, Adam (A), Betty (B) and Chris (C), in which the result is a single complete ordering/ranking of the players (a permutation of A, B,C). We assume that there are no ties/draws, ranking is complete and transitivity holds, which constraints are formalized in a knowledge base KB. Let the propositions P
_{AB}, P
_{AC}, P
_{BC} denote the following relations of the result AB, AC, BC (XY denotes that X preceeds/has a better position than Y in the result of the contest). We do not know the complete
order of the three players, but we have the following statements also in the knowledge base KB:

A claims (SA): C is not the first.

B claims (SB): I’m not the last.

C claims (SC): A is not the second.

Define the statements SA, SB, SC using the propositions P_{AB}, P_{AC}, P_{BC}.

Convert them to conjunctive normal form (CNF).

Indicate the models of the knowledge base (assuming that the knowledge base includes assumptions about completeness and transitivity of the ordering).

Prove with truthtable that the knowledge base KB entails P_{BC}, (KB╞ P_{BC}), that is that B has a better position than C („BC”).

Using a firstorder logic semantics , the world corresponding to this KB, are permutations of A,B and C. Illustrate the entailment relation KB╞ P_{BC} using this representation (that is indicate the models of the knowledge base KB and the models of the proposition P_{BC}).
(20p)
++: Assuming that nodes are evaluated from left to right, what alphabeta cuts are possible in Fig.2.?
1. What is the order of expansion and the final goal state in Fig. 1 (assuming that equivalent nodes are
selected from left to right, costs are indicated on the edges, heuristic values are indicated at the nodes) in case of

depthfirstsearch,

breadthfirstsearch,

uniform cost search,

greedy search.
Is the heuristic function admissible (prove or refute)?
(10p)
Fig.1. Search tree with costs on edges and heuristic values.
2. Apply the MINIMAX algorithm for the tree in Fig.2., propagate the values and indicate the MINIMAX moves! Indicate the alphabeta cuts in Fig.2., assuming that nodes are evaluated from left to right. (10p)
Fig.2. MINIMAX tree.
3. Estimate the effective branching factor for the search tree in Fig.3. (the goal state is the node 12, in bold)! (10p)
Fig.3. Search tree with found goal (in bold).
4. Define completeness and soundness in theorem proving. Give an example. (5p)
5. Is the next statement valid? Prove your answer with truth tables. (5 p)
(A XOR B) (A B), where (A XOR B) = (A ¬B) (¬A B).
6. Prove with resolution that
x. ¬Small(x), if we assume that {
x. (Small(x) → Cube (x)),
x. ¬Cube(x) }.
(10p)
7. Tim and Elisabeth are Club members. Club members are hiker or skier. Hikers do not like rain, skiers like snow. Elisabeth does not like what Tim likes, and she likes what Tim does not like. Tim likes rain and snow.Is there any club member who is hiker, but not skier? Answer this question with resolution!
H(x) denotes that x is Hiker, S(x) denotes that x is a skier, L(x,y) denotes that x likes y (if x is a club member and y denotes rain or snow).
(10p)