Questions and Answers of Artificial Intelligence A Modern approach

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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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)
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
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
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
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
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,
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
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)
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
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
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
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
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
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
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)
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
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
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 =
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
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,
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
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
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
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
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,
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
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
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
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
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
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
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
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
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.
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
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
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)
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
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
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
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
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
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
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
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.
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
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
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
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
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.
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

Showing 200 - 300 of 303