COS3751 EXAM PACK 2023

Cos3751 exam pack 2022 Artificial intelligence (University of South Africa) lOMoARcPSD| COS3751 Examination Preparation Page 1 of 12 Question 1 State Spaces [7] (a) Define the concept of a Fully observable environment. (1) An environment is said to be Fully observable if an agent’s sensors give it access to the complete state of the environment at each point in time. (b) Consider a game of chess. Is this a deterministic or stochastic environment? Clearly explain why. (2) Deterministic: because, in chess, the next state of the game (environment) is completely determined by the current state of the game and the move (action) executed by a player (agent). (c) Differentiate between discrete and continuous environments. Provide an example of each (4) An environment is said to be discrete if its state-space is finite and, for each state, there are only finitely many percepts to be perceived and only finitely many actions to choose from. The game of chess is an example of such an environment. On the other hand, a continuous environment has infinitely many distinct states, infinitely many percepts, and infinitely many actions to choose from at any state. Taxi driving is an example of a continuous environment. Question 2 Searching [16] Consider the provided diagram and answer the questions that follow (the / value of each node is provided in brackets after the node name, and the ā value is provided next to the edges between nodes) e(4) k(2) a(10) m(1) b(12) n(0) d(5) l(1) f(7) g(4) c(4) h(5) i(4) 5 2 7 10 3 8 8 5 5 4 3 3 1 2 4 3 7 6 lOMoARcPSD| COS3751 Examination Preparation Page 2 of 12 (a) Explain what an admissible heuristic is. (2) An admissible heuristic is one that never overestimates the true cost of reaching the nearest goal. (b) List the nodes and their Ā̂values that are added to the frontier when node d is expanded. Assume that node a is already on the explored (closed) list. (3) l(10), i(14) Not enough information is provided to answer this question& Which search strategy should we use, Greedy-Best-First or A*? If A*, which node is the initial (root) node? You cannot calculate PATH-cost if you don’t know where the root is! Let’s ASSUME that A* should be used, and that node a is the start node. Expanding a gives e(4) a(10) b(12) d(5) c(4) 2 7 8 3 f(e) = 6 f(d) = 8 f(c) = 12 f(b) = 19 Next; e has the lowest f-cost, so it will be expanded next: e(4) a(10) b(12) d(5) c(4) 2 7 8 3 f(d) = 8 f(c) = 12 f(b) = 19 5 k(2) f(k) = 9 Finally, expanding node d: e(4) a(10) b(12) d(5) c(4) 2 7 8 3 f(c) = 12 f(i) = 14 f(b) = 19 5 k(2) f(k) = 9 l(1) i(4) 7 6 f(l) = 10 Notice that k is already on the frontier. This is how I got to my answer& lOMoARcPSD| COS3751 Examination Preparation ©ornelis Dubbelman- Page 3 of 12 (c) Suppose we have the following frontier list (i(14), c(12), g(20)). Which one of these nodes will be selected for expansion next? State why. (2) Node c: because it has the lowest f-cost among all current frontier nodes. (I assume that the values in brackets indicate f-costs) (d) Explain what is meant by consistence with respect to heuristic searches (1) If the heuristic function of a graph-search strategy is consistent, then the algorithm is guaranteed to be optimal (and complete when the branching factor is finite). For every node in the search tree, the following inequality must hold Ă(ÿ ) ≤ ý(ÿ, � 㖂 , ÿ ′ ) + Ă(ÿ’ ). (e) Assume that a graph-search is used. Is the heuristic used in this diagram consistent? Explain why/why not. (2) No, this heuristic is not consistent! Āÿ = Ă (�) 㔚≰ ā (� 㔚 , þ ) + Ă(þ) = ą or Āÿ = Ă (�) 㔚≰ ā (� 㔚 , ý ) + Ă(ý) = ÿ (f) Consider the following diagram J K L M H I E F G A B C D Assume that loops are detected and that you consider moves in the order Up, Right, Down, Left. Also assume that the start node is node E, and the goal node is node G. List the order in which nodes are visited for a depth-first search. (6) E, A, B, C, D, G NB: Depth-first search uses a LIFO queue. A LIFO queue means that the most recently generated node is chosen for expansion. I used depth-first-GRAPH-search to obtain my solution (see diagram below) The labels on the left of each node has the form GENERATE| EXPAND, where GENERATE depicts the order in which nodes are generated and EXPAND depicts the order in which nodes are expanded (visited). lOMoARcPSD| COS3751 Examination Preparation ©ornelis Dubbelman- Pge 4 of 12 E H F A C B G D 1|1 2|_ 3|_ 4|2 6|4 5|3 Up Right Down Left 7|5 8|6 Question 3 Adversarial Search [14] Consider the following game tree and then answer the questions that follow (the static utility values for the leaf nodes are provided below each leaf node) A D E F G H I B J C 7 K 5 L 4 M 9 N 10 P 3 20 O Q 25 R 22 (a) Which choice should Max make (move B or move C)? Explain why. (2) Move B: The minimax (utility) value for MAX for move B is higher than that of move C. lOMoARcPSD| S - The study-notes marketplace COS3751 Examination Preparation ©ornelis Dubbelman- Page 5 of 12 A D E F G H I B J C 7 K 5 L 4 M 9 N 10 P 3 20 O Q 25 R 22 7 5 9 10 3 25 5 3 5 (b) Write down the ÿ and Ā values for nodes B, D, E, and F. (4) Using the algorithm in our textbook: B = (2∞ , 5), D = (7, ∞), E = (5, 7), F = (2∞ , 5) OR Using the algorithm in the video: B = (2∞ , 5), D = (7, ∞), E = (5, 7), F = (9, 5) I guess the algorithm used in the videos available from myUnisa ( follows: function LPHAA -BETA-SEARCH (state) returns an action v ← M AX -VALUE (state, −∞ , +∞ ) return action the in ACTIONS(state) with value v. function AXM-VALUE (state, ³, ´) returns a utility value if TERMINAL -TEST(state) then return TILITYU(state) for each a in ACTIONS(state) do ³ ← M AX (³, MIN-VALUE (RESULT(s, a), ³, ´)) if ³ g ´then return ³ return³. function IN-VMALUE (state, ³, ´) returns a utility value if ERMINAL T -TEST(state) then return TILITYU(state) for each a in ACTIONS(state) do ´ ← M IN(´, MAX -VALUE (RESULT(s, a) , ³, ´)) if ´f ³ then return ´ return ´ Using this algorithm, I got the following alpha/beta values (green values indicate the value returned by a node) S - The study-notes marketplace Downloaded by: mphomolokomme | Distribution of this document is illegal Want to earn R1,135 per month? Downloaded by Genial Adventures () lOMoARcPSD| S - The study-notes marketplace COS3751 Examination Preparation ©ornelis Dubbelman- Page 6 of 12 A D E F G H I B J C 7 K 5 L 4 M 9 N 10 P 3 20 O Q 25 R 22 7 ∞ 5 7 9 5 10 ∞ 5 10 5 5 -∞ 5 5 ∞ Using the algorithm in the prescribed textbook, I obtained the following values. The 3-arrays next to nodes take the form ă ÿ Ā A D E F G H I B J C 7 K 5 L 4 M 9 N 10 P 3 20 O Q 25 R 22 7 7 ∞ 5 5 7 9 -∞ 5 10 10 ∞ 3 5 10 3 5 10 5 -∞ 5 5 5 ∞ (c) If alpha/beta pruning is applied, a cut occurs. Indicate where this cut occurs, state what type of cut it is, and what the relevant ÿ/Ā values are when the cut occurs (4) The right-most child of node C, namely I (and I’s children etc. of course), is pruned from the search tree. This is an ÿ -cut. The relevant ÿ/Ā values are ÿ = Ą and Ā = Āÿ if you use the textbook’s algorithm OR ÿ = Ą and Ā = Ą if you use the video’s algorithm. (d) Clearly explain why ordering in alpha/beta searching is important, and how it benefits alpha/beta searching. (2) S - The study-notes marketplace Downloaded by: mphomolokomme | Distribution of this document is illegal Want to earn R1,135 per month? Downloaded by Genial Adventures () lOMoARcPSD| S - The study-notes marketplace COS3751 Examination Preparation ©ornelis Dubbelman- Page 7 of 12 The right order of nodes can result in pruning larger section of the search tree earlier. This benefits alpha/beta searching because it reduces the runtime of the algorithm. (e) Is it possible to re-order the game tree to effect a cut earlier? Is so, explain which branches you would re-order. If it is not possible, explain why it would not make a difference to re-order the tree. (2) Yes, I will swap the order of branch G and H (This will result in G also being pruned) Question 4 Constraint Satisfaction Problems [14] Consider the problem of assigning registers on a central processing unit (CPU) to the variables in a program. Since a program may have many variables and there are a limited number of registers on the CPU, assigning registers to variables is an important problem. Since only certain variables are in use at different times during the execution of the program (variables that are being used at a particular time are called alive), the real task is merely to figure out which alive variables to assign to the limited number of registers. The problem is actually trivially solved by visually arranging the variables in such a way that those variables that are alive together lie adjacent to each other and colouring each program variable (a register is thus represented by a colour) –adjacent variables cannot have the same colour. For a certain program the following holds: 1- There are six variables in use in the program 2- Program variables A, B, and C are alive together. Program variables C, D, E, and F are alive together, and program variables A, E, and F are alive together. 3- There are four registers available for assignment to program variables. Do not confuse the program variables with the CSP variables for this question. (a) Define the variables for this CSP. (3) The variables for this CSP are the program variables. Thus � 㕿{ý, þ, ÿ, Ā, ā, Ă = } (b) Define the domain for each variable in the CSP. (2) The domain of each variable is the set of four registers. Thus Ā � 㕿 = {ý Ā, ý ā , ý Ă, ý ă } where each ý ă (Ā ≤ ă ≤ ă ) is an abbreviation meaning <Register ă=. (c) Define the constraints for the variables in the CSP. (5) ÿ = {ý = þ, þ = ÿ, ý = ÿ, ÿ = Ā, Ā = ā, ā = Ă, ÿ = ā, ÿ = Ă, Ā = Ă, ý = ā, ý = Ă} NB: �ă 㕽= �Ą㕽(where �ă, 㕽�Ą �㕽 㕐 㕿) is a shorthand notation for � +(�ă, 㕽�Ą), 㕽�ă㕽= �Ą ,㕽, which means variables �ÿ and 㕉 �Ā are alive together. 㕉 S - The study-notes marketplace Downloaded by: mphomolokomme | Distribution of this document is illegal Want to earn R1,135 per month? Downloaded by Genial Adventures () lOMoARcPSD| S - The study-notes marketplace COS3751 Examination Preparation ©ornelis Dubbelman- Page 8 of 12 (d) Provide the solution to this problem if it exists. If no solution exists, explain what parameters from the problem would have to change in order to get to a solution.(4) One possible solution is: Variables A and D can use the same register; variables B and E can use the same variable; variable C requires its own register; and variable F require its own variable. For example, {ý = ý Ā, þ = ý ā , ÿ = ý Ă, Ā = ý Ā, ā = ý ā , Ă = ý ă } A B C D E F Register 1 (R₁) Register 2 (R¢ ) Register 3 (R£ ) Register 4 (R¤ ) Question 5 Predicate Logic [15] (a) Clearly explain what a Horn clause is, and state why they are useful (3) A Horn clause is a disjunction of literals of which at most one is positive. Deciding entailment with Horn clauses can be done in time that is linear in the size of the knowledge base (backward- and forward-chaining). (b) Closely examine the following sentences in a knowledge base ā 1. ¬ý ( ¬þ ( ¬ÿ ( Ā 2. ¬Ā ( ¬Ă ( ă 3. ¬ă ( ¬Ą ( ą 4. ¬ý ( ¬Ą ( ÿ 5. ¬ý ( þ 6. ý 7. Ą 8. Ă Show that ā ⊨ ą using forward chaining (12) First I rewrite these sentences in their equivalent implication form: 1. ý ' þ ' ÿ ⇒ Ā 2. Ā ' Ă ⇒ ă 3. ă ' Ą ⇒ ą 4. ý ' Ą ⇒ ÿ 5. ý ⇒ þ 6. ý 7. Ą 8. Ă Now I will attempt to derive ą: ý , Ą , and Ă are facts, so I add them to my (currently empty) list of true symbols. The premise of 5 is only ý ; ý is known to be true, so I add þ to my list of true S - The study-notes marketplace Downloaded by: mphomolokomme | Distribution of this document is illegal Want to earn R1,135 per month? Downloaded by Genial Adventures () lOMoARcPSD| S - The study-notes marketplace COS3751 Examination Preparation ©ornelis Dubbelman- Page 9 of 12 symbols. The premise of 4 is ý ' Ą ; both ý and Ą are known to be true, so I add ÿ to my list of true symbols. The premise of 1 is ý ' þ ' ÿ ; all three of these are in my list of true symbols, so I can add Ā to my list of true symbols. The premise of 2 is Ā ' Ă ; both of these are in my list of true symbols, so I add ă . Finally, the premise of 3 is ă ' Ą ; Both ă and Ą are in my list of true symbols, so I am entitled to infer that ą is true. Hence, by means of forward chaining I have shown that ā ⊨ ą (as required) Question 6 First-Order Logic [8] Consider the following sentences in a knowledge base ā 1. (∀þ) [(ā� 㕎 ĀĀ (þ, /ÿĀāĀÿÿ) ' ýÿÿ (þ, þĀāāÿÿÿ) ) ⇒ /� 㕎 āāÿ (þ)] 2. (∀ÿ)(∀Ā)[(ĀāĂþÿ(ÿ) ( þĂýýÿ(ÿ) ) ⇒ ā� 㕎 ĀĀ (ÿ, Ā)] 3. ¬ĀāĂþÿ(ĆĀ/ÿ) 4. þĂýýÿ(ĆĀ/ÿ) 5. (∀ý )[þĂýýÿ(ý ) ⇒ ýÿÿ (ý, þĀāāÿÿÿ)] (a) Use backward chaining to prove that John is happy, show all your steps (8) According to tutorial letter 102, backward chaining for FOL is not part of the syllabus. Instead, I will use a proof of resolution with refutation to prove the query. However, I will choose my resolver pairs in such a way that a backward chaining proof is simulated. First, I rewrite the sentences in the above knowledge base into clause form: 1. ¬ā� 㖂 ĀĀ (ą, ĂăĀāĀÿĆ) ( ¬Ąăÿ (ą, ĆĀāāÿÿĆ) ( Ă� 㖂 āāĆ (ą) 2. ¬ĀāĂþĆ(Ć) ( ā� 㖂 ĀĀ (Ć, ć) 3. ¬ĆĂýąĆ(Ć) ( ā� 㖂 ĀĀ (Ć, ć) 4. ¬ĀāĂþĆ(ĆĀĂÿ) 5. ĆĂýąĆ(ĆĀĂÿ) 6. ¬ĆĂýąĆ(Ą ) ( Ąăÿ (Ą, ĆĀāāÿÿĆ) To prove ā ⊨ Ă� 㖂 āāĆ(ĆĀĂÿ) by means of resolution refutation, I must show that the empty clause follows from (ā ' ¬Ă� 㖂 āāĆ(ĆĀĂÿ)): 1 ¬ā� 㖂 ĀĀ (ą, ĂăĀāĀÿĆ) ( ¬Ąăÿ (ą, ĆĀāāÿÿĆ) ( Ă� 㖂 āāĆ (ą) premise 2 ¬ĀāĂþĆ(Ć) ( ā� 㖂 ĀĀ (Ć, ć) premise 3 ¬ĆĂýąĆ(Ć) ( ā� 㖂 ĀĀ (Ć, ć) premise 4 ¬ĀāĂþĆ(ĆĀĂÿ) premise 5 ĆĂýąĆ(ĆĀĂÿ) premise 6 ¬ĆĂýąĆ(Ą ) ( Ąăÿ (Ą, ĆĀāāÿÿĆ) premise 7 ¬Ă� 㖂 āāĆ (ĆĀĂÿ) negated goal 8 ¬ā� 㖂 ĀĀ (ĆĀĂÿ, ĂăĀāĀÿĆ) ( ¬Ąăÿ (ĆĀĂÿ, ĆĀāāÿÿĆ) 1&7 {x/John} 9 ¬ĆĂýąĆ(ĆĀĂÿ) ( ¬Ąăÿ (ĆĀĂÿ, ĆĀāāÿÿĆ) 3&8 {y/John, z/History 10 ¬Ąăÿ (ĆĀĂÿ, ĆĀāāÿÿĆ) 5&9 {} 11 ¬ĆĂýąĆ(ĆĀĂÿ) 6&10 {w/John} 12 NULL 5&11 {} Hence, by means of resolution refutation; John is indeed happy :-) S - The study-notes marketplace Downloaded by: mphomolokomme | Distribution of this document is illegal Want to earn R1,135 per month? Downloaded by Genial Adventures () lOMoARcPSD| S - The study-notes marketplace COS3751 Examination Preparation ©ornelis Dubbelman- Page 10 of 12 ¬happy(John) ¬pass(John, history) ( ¬win(John, lottery) ¬lucky(John) ( ¬win(John, lottery) ¬pass(x, history) ( ¬win(x, lottery) ( happy(x) ¬lucky(y) ( pass(y, z) lucky(John) ¬lucky(w) ( win(w, lottery) ¬win(John,lottery) lucky(John) ¬lucky(John) Question 7 Machine Learning [16] (a) Explain what is meant by Supervised Learning. (2) In supervised learning the agent observes some example input–output pairs (training set) and learns a function that maps from input to output. (b) Consider the following table and answer the questions that follow Instance Classification Size Nationality Family 1 + Large French Single 2 + Small German Single 3 - Large German Married 4 - Small Italian Single 5 - Large Italian Single i. Using the entropy table on the last page of this document, calculate the entropy for the data. (2) I assume that <Classification= is the output, whereas <Size=, <Nationality=, and <Family= are the attributes (input). Thus, 2 of the 5 examples are positive, so ā = ā Ą = ÿ. ă . Using the table, I find that Ą (ÿĆ� 㖂 ĀĀăĀăý� 㖂 āăĀÿ ) = ā [ā, Ă] = ÿ. Āą ii. On which characteristic should the first node be split? Clearly show why you choose that characteristic. Refer to the table on the last page of this document for entropy values. (7) I will make use of the following abbreviations: Cl = Classification Sz = Size Na = Nationality Fa = Family. S - The study-notes marketplace Downloaded by: mphomolokomme | Distribution of this document is illegal Want to earn R1,135 per month? Downloaded by Genial Adventures () lOMoARcPSD| S - The study-notes marketplace COS3751 Examination Preparation ©ornelis Dubbelman- Page 11 of 12 Calculate ă� 㖂 ăÿ(þć) : ă� 㖂 ăÿ (þć) = Ą (ÿĆ) 2 Ă Ą ā [Ā, ā] 2 ā Ą ā [Ā, Ā] = ÿ. Āą 2 ÿ. ą ∙ ÿ. ÿÿ 2 ÿ. ă ∙ Ā = ÿ. ÿĂā Calculate ă� 㖂 ăÿ (� 㕵 㖂): � ă� 㖂 ăÿ (� 㕵 㖂) = Ą � (ÿĆ) 2 Ā Ą ā [Ā, ÿ] 2 ā Ą ā [Ā, Ā] 2 ā Ą ā [ÿ, ā ] = ÿ. Āą 2 ÿ. ā ∙ ÿ 2 ÿ. ă ∙ Ā 2 ÿ. ă ∙ ÿ = ÿ. Ąą Calculate ă� 㖂 ăÿ(Ă� 㖂 ) : ă� 㖂 ăÿ (Ă�)㖂= Ą (ÿĆ) 2 ă Ą ā [ā, ā ] 2 Ā Ą ā [ÿ, Ā] = ÿ. Āą 2 ÿ. ÿ ∙ Ā 2 ÿ. ā ∙ ÿ = ÿ. Āą According to my calculations, <Nationality= has the highest data gain, namely 0.56. Hence, I will choose <Nationality= to split on first (at the root)! Complete decision tree based on the given data: (You can split on either <Size= or <Family= at the {Nationality = <German=} test node) Nationality + Family - + - French German Italian Single Married (c) Many machine learning techniques suffer from the problem of over-fitting. Briefly discus two techniques that have been developed to reduce the problem of overfitting during decision tree learning. (5) One technique, called decision tree pruning, works by eliminating nodes that are not clearly relevant: Start with a full decision tree; then look at a test node that has only leaf nodes as decedents: If the test appears to be irrelevant-detecting only noise in the data-then eliminate the test, replacing it with a leaf node. Repeat this process, considering each test with only leaf descendants, until each one has either been pruned or accepted as is. � 㕌 ā pruning is an example of such a strategy. Another technique involves limiting the number of input attributes and the size of the hypothesis space. Increasing the number of training examples is also a good idea! S - The study-notes marketplace Downloaded by: mphomolokomme | Distribution of this document is illegal Want to earn R1,135 per month? Downloaded by Genial Adventures () lOMoARcPSD| S - The study-notes marketplace COS3751 Examination Preparation ©ornelis Dubbelman- Page 12 of 12 Entropy Table ā: Ratio of positive examples ā : Corresponding entropy ā ā 0.00 0.00 0.10 0.47 0.20 0.72 0.30 0.88 0.40 0.96 0.50 1.00 0.60 0.98 0.70 0.88 0.80 0.72 0.90 0.47 1.00 0.00 Example: For ā [4, 1], the ratio ā = 4 5 , or 0.80. The corresponding entropy value is given by the table as 0.72 Good luck S - The study-notes marketplace Downloaded by: mphomolokomme | Distribution of this document is illegal Want to earn R1,135 per month? Downloaded by Genial Adventures () lOMoARcPSD| S - The study-notes marketplace ASSIGNMENT 1 Solution Total Marks: 150 Unique Assignment Number: / Study material: Chapters 1 through 4. You may skip sections 4.2 and 4.5. Important: When we use the phrase ‘define’ (particularly in Question 2), we are looking for a formal definition using some form of formal notation, and not simply an English description or definition. For example: ‘Define the initial state for an agent in Johannesburg’. Answer: In(Johannesburg). ‘Define the actions available to this agent given that the agent simply moves between major metropolitan areas’. Answer: Actions(In(Johannesburg)) = {Go(Bloemontein), Go(Durban), . . . }. When we want an English definition we will explicitly ask for it. Question 1: 13 Marks (1.1) Explain the difference between a single and multi-agent environment. (6) An agent solving a problem by itself is a single agent environmentX . The key distinction is if an agent X’s behavior is best described as maximizing a performance measure whose value depends on agent Y’s behavior XX . For example in a chess game the opponent agent X is trying to maximize its performance measure, which by the rules of chess minimises agent Y’s performance measureX . Thus chess is a competitive multi agent environment. In multiagent environments communication emerges as a rational behaviorX while non-existent in single agent environmentsX . Pg 42-43 (1.2) Explain the difference between a Deterministic and Stochastic environment. (4) In a deterministic environment the next state is completelyX determined by the current state and the agent’s action X . In a stochastic environment one cannot completely X determine the next state based solely on the current environment and on the agent’s actions X. (1.3) Consider a game of chess. Is this a fully observable, partially observable, or unob- (3) servable environment? Clearly explain your answer. Fully observable X . The entire stateX can be observed at each distinct state in the state spaceX . Question 2: 22 Marks (2.1) List the 5 components that can be used to define a problem. (5) 1. Initial stateX 2. ActionsX 3. Transition modelX 2 S - The study-notes marketplace Downloaded by: mphomolokomme | Distribution of this document is illegal Want to earn R1,135 per month? Downloaded by Genial Adventures () lOMoARcPSD| S - The study-notes marketplace COS3751/201/1/2021 4. Goal testX 5. Path costX (2.2) Differentiate between search space and goal space. (2) The search space is the set of states that have to be searched for a solutionX , whereas a goal space is a set of goal statesX . (2.3) What is the purpose of the explored set? (1) Avoids infinite loops since it holds the list of nodes that have already been explored. X (2.4) List and discuss three types of queues that may be employed in a search. (6) 1. FIFOX : used in DFS searches, nodes are added in reverse order to ensure that the last node added will be the first node to be explored.X 2. LIFOX : Typically used in BFS searches: nodes are added in the order they are generated.X 3. Priority queueX : Nodes are added and sorted based on some key, this ensures that certain states take priority over others during the expansion phase.X (2.5) List and explain the measures used to determine problem solving performance. (8) 1. CompletenessX : Will the algorithm find a solution if it exists? X 2. OptimalityX : Will the algorithm find the best solution (optimal path cost among all solutions)? X 3. Time complexityX : How long does the algorithm take to find a solution? X 4. Space complexityX : How much memory is needed to perform the search for a solution? X