Machine Intelligence vimm 3241 – 4025

Machine Intelligence VIMM 3241 – 4025

4. Define the elements of Hidden Markov models. Explain its application and the three-layered temporal probabilistic models in speech recognition (signal, phone, word). (10 p)

5. Select an optimal action from the set of actions with the following outcomes (P:0.1,0.3,0.6;U:1,2,3) and (P:0.3,0.3,0.4;U:3,1,3). (10 p)
++. Draw an arbitrary decision tree and explain the components and usage of the representation (2). Give a general algorithm to transform an arbitrary logical expression to a decision tree(3). Derive the size of the space of decision trees for n boolean attributes? (2 p)
1. Which complete(!) search algorithm has linear space complexity (explain/demonstrate why)? (3 p)
2. Define the concept of dominant heuristic function. Describe a method to construct a dominant heuristic function from admissible heuristic functions. (2 p)
3. Enumerate the main features of agent environments (4). Which properties are necessary for an agent in an „inaccessible environment”? (2 p)

4. You have to travel from the Lido to the station (Ferrovia) in Venice. The only available vehicle of transport is the vaporetto (water-bus), whose simplified network is shown in the figure. The (time) cost is 4 for a bold black section, 3 for a dotted section, 2 for a dashed section and 1 (fastest) is for the sections indicated with normal black line. Select an appropriate search strategy and find the fastest route. Number the stations as they are expanded/checked by the algorithm. (8 p)

5. Formalize the reasoning of the penguin on the figure in propositional logic and demonstrate its error with truth table. (4 p)

7. Describe the main steps of the resolution proof. (7 p)

9. How many probabilities are necessary to define completely the Bayesian network in the figure? How much is the gain compared to a naive table representation? (3 p) Decompose the joint distribution P(ABCDEFG) using the conditional probabilities corresponding to the graph! (3 p)

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 truth-tables that it is sound (6p). Is it complete in first-order 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 trade-off 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 successor-state 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 goal-oriented 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 d-separation 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₁(tile) = x+y,

h₂(tile) = max(x, y), and

h₃(tile) = sqrt ((x)²+(y)²).

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 truth-tables! (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 single-state problem? Explain your answer! (8p)
2. What is the resolution inference step (4p)? Show its soundness with truth-tables for three variables (8p).
3. What does semi-decidability of proof methods mean in first-order 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 (3-valued) 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 truth-table 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 truth-table 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

• depth-first-search:

• breadth-first-search

• 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 AB, AC, BC (XY 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.
  

1. 
   Define the statements SA, SB, SC using the propositions P_AB, P_AC, P_BC.
   
2. 
   Convert them to conjunctive normal form (CNF).
   
3. 
   Indicate the models of the knowledge base (assuming that the knowledge base includes assumptions about completeness and transitivity of the ordering).
   
4. 
   Prove with truth-table that the knowledge base KB entails P_BC, (KB╞ P_BC), that is that B has a better position than C („BC”).
   
5. 
   Using a first-order 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 alpha-beta 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

1. 
   depth-first-search,
   
2. 
   breadth-first-search,
   
3. 
   uniform cost search,
   
4. 
   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 alpha-beta 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)

Directory: system -> files
files -> Haiti Relief – esf 15 Support Organization Situation Report # 17 1/28/10
files -> Haiti Relief – esf 15 Support Organization Situation Report # 16 1/27/10
files -> Right to Carbon or Right to Life: Human Rights Approaches to Climate Change
files -> Enhancing interactive learning in the classroom with Turning Point
files -> Curriculum vita
files -> -
files -> Acknowledgements
files -> Nw, Washington D. C 20037 Telephone: (202)884-1080, (202)939-6125/7
files -> Grey-headed Flying-fox Management Strategy for the Lower Hunter Grey-headed Flying-fox