Artificial Intelligence A Modern Approach 4th Edition Stuart Russell, Peter Norvig - Solutions

Section 19.6.5 (page 684) noted that the output of the logistic function could be interpreted as a probability p assigned by the model to the proposition that f(x) = 1; the probability that f(x) = 0 is therefore 1 − p. Write down the probability p as a function of x and calculate the derivative
Describe the differences between supervised, unsupervised, and reinforcement learning.
Define the following terms in your own words. a. Bagging b. Boosting c. Stacking d. Random forest
Consider the problem of detecting human faces in images of larger scenes that may contain one or more faces, or no faces at all. The specific goal is to identify the location and size of each face in an image, rather than merely determining whether a face is present in the image. Suppose you are
Prove that a decision list can represent the same function as a decision tree while using at most as many rules as there are leaves in the decision tree for that function. Give an example of a function represented by a decision list using strictly fewer rules than the number of leaves in a
Which of the following are true or false. Briefly justify your answer.a. In the case of a binary class and all binary features, Naive Bayes is a linear classifier. b. Naive Bayes trained using maximum-likelihood parameter estimation is guaranteed not to perform worse if more features are
Suppose you train a classifier and test it on a held-out validation set. It gets 30% classification accuracy on the training set and 30% classification accuracy on the validation set.a. From what problem is your model most likely suffering: underfitting or overfitting?b. What could reasonably be
Your boss provides you with an image dataset in which some of the images contain your company’s logo, and others contain competitors’ logos. You are tasked to code up a classifier to distinguish your company’s logos from competitors’ logos. You complete the assignment quickly and even send
Construct a data set (set of examples with attributes and classifications) that would cause the decision-tree learning algorithm to find a non-minimal-sized tree. Show the tree constructed by the algorithm and the minimal-sized tree that you can generate by hand.
This exercise considers χ2 pruning of decision trees.a. Create a data set with two input attributes, such that the information gain at the root of the tree for both attributes is zero, but there is a decision tree of depth 2 that is consistent with all the data. What would χ2 pruning do on this
The standard DECISION-TREE-LEARNING algorithm described in the chapter does not handle cases in which some examples have missing attribute values.a. First, we need to find a way to classify such examples, given a decision tree that includes tests on the attributes for which values can be missing.
Construct a decision list to classify the data below. Select tests to be as small as possible (in terms of attributes), breaking ties among tests with the same number of attributes by selecting the one that classifies the greatest number of examples correctly. If multiple tests have the same number
Suppose you have a state-space search problem defined by the usual stuff:• A set of states s; • An initial state s0; • A set of actions A including the NoOp action that has no effect; • A transition model Result(s, a); • A set of goal states G.Unfortunately, you have
Explain why the following set of clauses is unsatisfiable without using truth tables: AV BVC AV BV¬C AV¬BVC AV¬BV¬C AV BVC AV BV C ¬AV¬BVC ¬AV¬BV¬C
For each English sentence on the left, there is a corresponding logical sentence on the right, but not necessarily the one across from it. Work out which English sentence corresponds to which propositional logic sentence, and hence determine the meaning (in English) of each proposition
Suppose an agent inhabits a world with two states, S and ¬S, and can do exactly one of two actions, a and b. Action a does nothing and action b flips from one state to the other. Let St be the proposition that the agent is in state S at time t, and let at be the proposition that the agent does
How many solutions are there for the three-color map-coloring problem in Figure 6.1? How many solutions if four colors are allowed? Two colors?
Futoshiki is a Sudoku-like Japanese logic puzzle that is very simple, but can be quite challenging. You are given an n x n grid, and must place the numbers 1, . . . n in the grid such that every row and column has exactly one of each. Additionally, the assignment must satisfy the inequalities
Suppose we are solving a CSP with local search. The problem has N variables, each of which has a domain with d values (for example, in Sudoku, N = 81 and d = 9). We are interested in the successors of any state in the local search: from a given assignment to variables, what other assignments will
Mom, Dad, Baby, Student, Teacher, and Guide are lining up next to each other in six linear spots labeled 1 to 6, one to a spots. Baby needs to line up between Mom and Dad. Student and Teacher need to be next to each other. Guide needs to be at one end, in spot 1 or 6. Formulate this problem as a
Consider a CSP with variables X, Y with domains {1, 2, 3, 4, 5, 6} for X and {2, 4, 6} for Y , and constraints X < Y and X +Y > 8. List the values that will remain in the domain of X after enforcing arc consistency for the arc X → Y (which prunes the domain of X, not Y).
Using a CSP solver program and another program to generate random problem instances of CSPs, report on the time to solve the problem as a function of the ratio of the number of constraints to the number of variables.
Consider a CSP with a constraint graph consisting of n variables arranged in a circle, where each variable has two constraints, one with each neighbor on either side. Explain how to solve this class of CSPs efficiently, in time O(n).
Are the following statements true or false? a. Running forward checking after the assignment of a variable in backtracking search will ensure that every variable is arc consistent with every other variable. b. In a CSP constraint graph, a link (edge) between any two variables implies that
Consider a CSP with three variables: A, B, and C. Each of the three variables can take on one of two values: either 1 or 2. There are three constraints: A ≠ B, B ≠ C, and A ≠ C. What values for what variables would be eliminated by enforcing arc-consistency? Explain your answer.
Ali, Bo, Cleo, and Dallas are picking their entrees at a restaurant. The choices are pasta, quesadillas, risotto, and sushi. They have some strict dietary preferences: • Cleo will not order sushi. • Ali and Bo want to steal each other’s food, so they will order different
What is the worst-case complexity of running AC-3 on a tree-structured CSP?
Consider the problem of tiling a surface (completely and exactly covering it) with n dominoes (2 × 1 rectangles). The surface is an arbitrary edge-connected (i.e., adjacent along an edge, not just a corner) collection of 2n 1×1 squares (e.g., a checkerboard, a checkerboard with some squares
In a general constraint satisfaction problem with N binary-valued variables, what is the minimum, and the maximum number of times that backtracking search will backtrack, expressed in O() notation (i.e. O(1), O(n2), etc.).
What are the primary differences in the logical inferences required for a logic-based agent operating in a fully observable environment versus a partially observable environment?
In Figure 11.14 we showed how to describe actions in a scheduling problem by using separate fields for DURATION, USE, and CONSUME. Now suppose we wanted to combine scheduling with nondeterministic planning, which requires nondeterministic and conditional effects. Consider each of the three fields
Prove each of the following assertions: a. Every pair of propositional clauses either has no resolvents, or all their resolvents are logically equivalent. b. There is no clause that, when resolved with itself, yields (after factoring) the clause (¬P ∨ ¬Q). c. If a propositional
The DPLL satisfiability algorithm is a backtracking search algorithm with 3 heuristic improvements: PURE-SYMBOLS, UNIT-CLAUSES, and EARLY TERMINATION. This question connects these improvements to more general CSP techniques used with backtracking search. a. In the following CNF expression,
a. A certain procedure to convert a sentence to CNF contains four steps (1–4 below); each step is based on a logical equivalence. For each step, which of the stated equivalences are valid? (i) Step 1: drop biconditionals a) (α ⇔ β) ≡ ((α ⇒ β) ∧ (β ⇒ α)) b) (α ⇔
Obtain a passport application for your country, identify the rules determining eligibility for a passport, and translate them into first-order logic, following the steps outlined in Section 8.4.
True or false? Explain. a. ∃ x x = Rumpelstiltskin is a valid (necessarily true) sentence of first-order logic. b. Every existentially quantified sentence in first-order logic is true in any model that contains exactly one object. c. ∀ x, y x = y is satisfiable.
Translate into first-order logic the sentence “Everyone’s DNA is unique and is derived from their parents’ DNA.” You must specify the precise intended meaning of your vocabulary terms.
This question considers Horn KBs, such as the following: P(F(x)) ⇒ P(x)Q(x) ⇒ P(F(x))P(A)Q(B)Let FC be a breadth-first forward-chaining algorithm that repeatedly adds all consequences of currently satisfied rules; let BC be a depth-first left-to-right backward-chaining algorithm that tries
Find values for the probabilities a and b in joint probability table below so that the binary variables X and Y are independent. XYP(X,Y) 3/5 tt tf 1/5 ft ff a b
Consider a game played with a deck of just 8 cards, 4 aces and 4 kings. The three players, Alice, Bob, and Carlos, are dealt two cards each. Without looking at them, they place the cards on their foreheads so that the other players can see them. Then the players take turns either announcing that
Your mission is to capture, in logical form, enough knowledge to answer a series of questions about the following simple scenario:Yesterday John went to the North Berkeley Safeway supermarket and bought two pounds of tomatoes and a pound of ground beef.Start by trying to represent the content of
Make the necessary additions or changes to your knowledge base from the previous exercise so that the questions that follow can be answered. Include in your report a discussion of your changes, explaining why they were needed, whether they were minor or major, and what kinds of questions would
A non-angler, curious to know what counts as a good day of fishing (F) at the lake and puzzled by the phenomenon that it can sometimes be a good day even when no fish are caught, decides to create a naive Bayes model with F as the Boolean class variable and three features: whether it rained (R),
Consider a robot whose operation is described by the following PDDL operators:Op(ACTION:Go(x, y), PRECOND:At(Robot, x), EFFECT:¬At(Robot, x) ∧ At(Robot, y))Op(ACTION:P ick(o), PRECOND:At(Robot, x) ∧ At(o, x), EFFECT:¬At(o, x) ∧ Holding(o))Op(ACTION:Drop(o), PRECOND:At(Robot, x) ∧
Suppose that the optimistic reachable set of a high-level plan is a superset of the goal set; can anything be concluded about whether the plan achieves the goal? What if the pessimistic reachable set doesn’t intersect the goal set? Explain.
Write an algorithm that takes an initial state (specified by a set of propositional literals) and a sequence of HLAs (each defined by preconditions and angelic specifications of optimistic and pessimistic reachable sets) and computes optimistic and pessimistic descriptions of the reachable set of
Suppose X and Y are independent random variables over the domain {1, 2, 3} with P(X = 3) = 1/6. Given the following partially specified joint distribution, what are the remaining values? Write your answers as simplified fractions in the blanks. X\Y 1 2 …. 3 1 1/4 1/16 1/6 1/24 23
Consider the following probability distributions: Given just these tables and no independence assumptions, calculate the following probabilities, showing your working. If it is impossible to calculate without more independence assumptions, specify instead a minimal set of independence
Formulate each of the following as probability models, stating all your assumptions, and use the probability model to answer the questions.a. Aliens can be friendly or not; 75% are friendly. Friendly aliens arrive during the day 90% of the time, while unfriendly ones always arrive at night. If an
The chapter proposes probability theory as the basis for reasoning under uncertainty and provides one argument based on work by de Finetti. Compare and contrast de Finetti’s argument with other arguments by Ramsey, Cox, Savage, Jeffrey, and Jaynes (see the historical and bibliographical notes for
Consider a model with one binary class variable Y and n k-ary features F1, F2, . . . , Fn. a. How many parameters are required to represent the full joint distribution P(Y, F1, F2, . . . , Fn) in tabular form, given no conditional independence properties?b. How many are needed when the naive
You are given points from 2 classes, shown as rectangles and dots in Figure S12.2. For each of the following sets of points, decide whether the set satisfies or fails to satisfy all the Na¨ıve Bayes modelling assumptions.Figure S12.2
Let A and B be Boolean random variables. You are given the following quantities:P(A = J true) = 1/2P(B = true | A = true) = 1P(B = true) = 3/4What is P(B = true | A = false)?
Write out a general algorithm for answering queries of the form P(Cause|e), using a naive Bayes distribution. Assume that the evidence e may assign values to any subset of the effect variables.
a. Consider the following two assertions, where U, V, W, X, Y, and Z are sets of random variables:(i) U is independent of V given W. (ii) X is independent of Y given Z. Under what conditions, in terms of subset/superset relationships among U, V, W, X, Y, and Z, can one say that (i)
a. Suppose A ⊥⊥ B. Determine the missing entries x and y of the joint distribution P(A, B), where A and B take values in {0, 1}. P(A = 0, B = 0) = 0.1 P(A = 0, B = 1) = 0.3 P(A = 1, B = 0) = x P(A = 1, B = 1) = y b. Suppose B ⊥⊥ C | A. Determine the missing entries
Simplify each of the following expressions down a single probability term, without making any independence assumptions: a.b.c. Σa P(a' | D)P(bla', D).
You have three coins in your pocket: • Coin 1 is a fair coin that comes up heads with probability 1/2. • Coin 2 is a biased coin that comes up heads with probability 1/4. • Coin 3 is a biased coin that comes up heads with probability 3/4.Suppose you pick one of the coins
For each of the following assertions, say whether it is true or false and support your answer with arguments or counterexamples where appropriate.a. P(A, B) = P(A)P(B).b. P(A | B) = P(A)P(B).c. P(A, B) = P(A)P(B) − P(A | B).d. P(A, B, C) = P(A | B, C)P(B | C)P(C).e. P(A, B, C) = P(C | A,
a. Assuming that A is independent of B given C and that A and C are absolutely independent, what is the most factored representation of P(A, B, C)? b. Assuming that A is independent of B given C, what is the most factored representation of P(A, B | C)? c. Given no independence
In this question we consider conditional distributions for binary random variables, expressed as tables. a. A, B, C, and D are binary random variables. How many entries are in the following conditional probability tables and what is the sum of the values in each table?(i) P(A | C) (ii)
For each of the following expression, derive an equivalent expression in terms of only the given conditional distributions, using the given conditional independence assumptions. If it is not possible, say so. a. Express P(A, B | C) in terms of P(A), P(A | C), P(B | C), P(C | A, B) given no
Many researchers have pointed to the possibility that machine learning algorithms will produce classifiers that display racial, gender, or other forms of bias. How does this bias arise? Is it possible to constrain machine learning algorithms to produce rigorously fair predictions?
Describe three different task environments in which the performance measure is easy to specify completely and correctly, and three in which it is not.
Define in your own words: (a) Intelligence, (b) Artificial intelligence, (c) Agent, (d) Rationality, (e) Logical reasoning.
Implement a performance-measuring environment simulator for the vacuum-cleaner world depicted in Figure 2.2 and specified on page 40. Your implementation should be modular so that the sensors, actuators, and environment characteristics (size, shape, dirt placement, etc.) can be changed
Find and analyze at least three sets of proposed principles for the governance of AI. What do the sets of principles have in common? How do they differ? How implementable are these principles?
Study the 2021 EU “Proposal for a Regulation of the European Parliament and of the Council Laying Down Harmonised Rules on Artificial Intelligence (Artificial Intelligence Act)” (or its final version, if available). Which provisions appear to have the most direct and tangible impact on what
Several “AI winters,” or rapid collapses in levels of economic and academic activity (and media interest) associated with AI, have occurred. Describe the causes of each collapse and of the boom in interest that preceded it.
Investigate the state of the art for domestic robots: what can be done (with what assumptions and restrictions on the environment) and what problems remain unsolved? Where is research most needed?
Summarize the pros and cons of allowing the development, deployment, and use of lethal autonomous weapons.
Here is pseudocode for three agent programs A, B, C:In each of these agents, the function f is some arbitrary, possibly randomized, function of its inputs with no internal state of its own; the agent program runs on a computer with unbounded memory but finite clock speed. We’ll assume also that
The resurgence of interest in AI in the 2010s is often attributed to deep learning. Explain what deep learning is, how it relates to AI as a whole, and where the core technical ideas actually originated.
The vast majority of academic publications and media articles report on successes of AI. Examine recent articles describing failures of AI. (? (?) and ? (?) are good examples, but feel free to find your own.) How serious are the problems identified? Are they examples of overclaiming of or
Examine at least three science-fiction movies in which AI systems threaten to (or actually do) “take control.” In the movie, does the takeover stem from “spooky emergent consciousness” or from a poorly defined objective? If the latter, what was it?
For each of the following agents, specify the sensors, actuators, and environment: microwave oven, chess program, autonomous supply delivery plane.
For each of the following task environment properties, rank the example task environments from most to least according to how well the environment satisfies the property. Lay out any assumptions you make to reach your conclusions.a. Fully Observable: driving; document classification; tutoring a
Write an essay on the relationship between evolution and one or more of autonomy, intelligence, rationality, and learning.
Consider a simple thermostat that turns on a furnace when the temperature is at least 3 degrees below the setting, and turns off a furnace when the temperature is at least 3 degrees above the setting. Is a thermostat an instance of a simple reflex agent, a model-based reflex agent, or a goal-based
Give a complete problem formulation for each of the following problems. Choose a formulation that is precise enough to be implemented. a. There are six glass boxes in a row, each with a lock. Each of the first five boxes holds a key unlocking the next box in line; the last box holds a banana.
You have a 9 × 9 grid of squares, each of which can be colored red or blue. The grid is initially colored all blue, but you can change the color of any square any number of times. Imagining the grid divided into nine 3 × 3 sub-squares, you want each sub-square to be all one color but neighboring
Implement two versions of the RESULT(s, a) function for the 8-puzzle: one that copies and edits the data structure for the parent node s and one that modifies the parent state directly (undoing the modifications as needed). Write versions of iterative deepening depth-first search that use these
Accurate heuristics don’t necessarily reduce search time in the worst case. Given any depth d, define a search problem with a goal node at depth d, and write a heuristic function such that |h(n) − h∗ (n)| ≤ O(log h∗ (n)) but A∗ expands all nodes of depth less than d.
Imagine that the problem in Exercise 3.ROMF, in which two friends try to meet up on the map of Romania, is modified so that one of the friends wants to avoid the other. The problem then becomes a two-player pursuit–evasion game. We assume now that the players take turns moving. The game ends only
We gave two simple heuristics for the 8-puzzle: Manhattan distance and misplaced tiles. Several heuristics in the literature purport to improve on this—see, for example, Nilsson (1971), Mostow and Prieditis (1989), and Hansson et al.(1992). Test these claims by implementing the heuristics and
Take one of the games (tic-tac-toe, Connect Four, Kalah, Othello, checkers, etc.) for which you implemented a move generator, and apply Monte Carlo tree search to the move generator. Compare the performance of an MCTS player to an alpha-beta player.
a. Implement a version of search (either alpha-beta or Monte Carlo) that cuts off the search early if it finds a move that is “obviously” best (using Sunfish or some other game engine, or code of your own). Compare the performance of this version to the standard version. b. Do the same for
Suppose you have an oracle, OM(s), that correctly predicts the opponent’s move in any state. Using this, formulate the definition of a game as a (single-agent) search problem. Describe an algorithm for finding the optimal move.
Read the paper “Monte Carlo Tree Search Techniques in the Game of Kriegspiel” by Paolo Ciancarini and Gian Piero Favini, and report on how well Monte Carlo tree search works in a game of imperfect information. Can you replicate the experiment, either for Kriegspiel or for another partially
True or False: In expectiminimax search with two players, one max and the other chance, one can use pruning to reduce the search cost.
Re-implement one of the first machine learning game playing system, a version of MENACE, the Machine Educable Noughts and Crosses (Tic-Tac-Toe) Engine (Michie, 1963). The original version was implemented with 304 matchboxes filled with colored beads. You might find it easier to use a
Consider the problem of solving two 8-puzzles: there are two 8-puzzle boards, you can make a move on either one, and the goal is to solve both. a. Give a complete problem formulation. b. How large is the reachable state space? Give an exact numerical expression. c. Suppose we make
Consider the simplified game of poker where there are exactly two players and three cards, ranked in the following order: Ace beats King and King beats Queen. Each player is dealt one of the three cards, which they view independently. Then the players simultaneously declare whether they are going
Read Monte Carlo Tree Search: A Review of Recent Modifications and Applications, by Maciej Swiechowski, Konrad Godlewski, Bartosz Sawicki, and Jacek Ma ´ ndziuk, ´ arXiv:2103.04931. Report on one or more of the following ideas for MCTS. Is the idea more help for minimax search or for MCTS? For
In each of the cases below, state whether a node can be pruned always, sometimes, or never. Assume that in the expectiminimax game that outcome values are bounded between +1 and −1. a. In a minimax game, a leaf node that is the first child of its parent. b. In a expectiminimax game, a
In a full-depth minimax search of a tree with depth D and branching factor B, with α−β pruning, what is the minimum number of leaves that must be explored to compute the best move?
In a minimax tree with a branching factor of 3 and depth 2 (one max layer, one min layer with 3 nodes, and a leaf layer with 9 total nodes) what is the maximum number of nodes that can be pruned by alpha-beta pruning?
Describe and implement a real-time, multiplayer game-playing environment, where time is part of the environment state and players are given fixed time allocations.
Which of the following statements about alpha-beta pruning are true or false? a. Alpha-beta pruning may find an approximately optimal strategy, rather than the minimax optimal strategy. b. Alpha-beta prunes the same number of subtrees regardless of the order of child nodes. c.
Consider a game in which three players, A, B, and C, are trying to solve an 8-puzzle. A player receives +1 for making the final move that solves the puzzle, –1 if another player does so. If the same state is repeated 3 times, the game ends with everyone receiving 0. But the players do not just

Showing 200 - 300 of 303

Artificial Intelligence A Modern Approach 4th Edition Stuart Russell, Peter Norvig - Solutions

Step by Step Answers