AI Flashcards

Question

Rationality & Omniscience

Answer 1

Book: Walk across a clear street to friend, door falls on you from plane - you didn’t made a bad decision here, but it was unfortunate - actual performance: look Inverse - GTA: take a taxi off of a tower - the taxi AI just has no clue driving off a tower is dangerous - actual performance: NPC should check to see if high up Process is called information gathering Modifies percepts Gather information and learn when possible

Answer 2

Performance measure?? safety, destination, profits, legality, comfort, ... Environment?? US streets/freeways, traffic, pedestrians, weather, ... Actuators?? steering, accelerator, brake, horn, speaker/display, ... Sensors?? video, accelerometers, gauges, engine sensors, keyboard, GPS, ...

Answer 3

Fully-observable – sensors give it access to complete state of environment Partially-observable – sensors give it access to some of the environment state Agent has no sensors, the environment is unobservable (not hopeless though)

Answer 4

If the next state of the environment is completely determined by the current state and the action executed by agents, it is deterministic Otherwise, non-deterministic Most real situations so complex not possible to keep track of unobserved aspects, so treat as nondeterministic

Answer 5

In an episodic task environment, the agent’s experience is divided into atomic episodes. In each episode the agent receives a percept and then performs a single action -> Robots! - next episode does not depend on the actions taken in previous episodes Sequential: current decision could affect all future decisions

Answer 6

If environment can change while agent deliberates, environment is dynamic, otherwise, it is static

Answer 7

Chess has finite number of states/percepts/actions It is discrete Taxi driving is continuous -> continuous values

Answer 8

solving a crossword puzzle by itself is clearly in a single-agent environment whereas an agent playing chess is in a two-agent environment have described how an entity may be viewed as an agent, but we have not explained which entities must be viewed as agents

Answer 9

– simple reflex agents – reflex agents with state – goal-based agents – utility-based agents

Answer 10

Can implement with a Finite State Machine Algorithm: Set an initial state (Idle is common) If percept1 then: SetState(Reaction1) Else if percept2 then: SetState(Reaction2) Else if percept3 then: SetState(Reaction3) Easy to implement and generally gets pretty good results Can still make fairly realistic agents as long as perception is reasonable

Answer 11

Can again implement with a Finite State Machine One (possible) Algorithm: Set an initial state (Idle is common) worldState = PerceiveWorldState() If percept1 && worldState.reaction1Benefit then: SetState(Reaction1) Else if percept2 && worldState.reaction2Benefit then: SetState(Reaction2) Else if percept3 && worldState.reaction3Benefit then: SetState(Reaction3) Could loop over world state action benefits and take the maximum

Answer 12

Command Prompt Agent (basically the same as a grid) Environment: - real-time - turn-based? - steps? Sensors: - limited view of the characters - object representation - can you hear other agents? Actuators: very basic

Answer 13

2D Agent (pixels now instead of cells) Environment: - turn-based? - steps? Sensors: - limited view of the characters - can you hear other agents? Actuators: pretty basic

Answer 14

3D Agent (free-form movement) Environment: - turn-based? - steps? Sensors: - limited view of the characters - can you hear other agents? - More options given world Actuators: more complex

Answer 15

Large Language Model

Answer 16

An agent doesn’t have access to its entire history. It only has access to what it has remembered. The memory or belief state of an agent at time t encodes all of the agent’s history that it has access to. The belief state of an agent encapsulates the information about its past that it can use for current and future actions. At every time a controller has to decide on: What should it do? What should it remember? (How should it update its memory?) — as a function of its percepts and its memory

Answer 17

A purely reactive agent doesn’t have a belief state.

Answer 18

doesn’t perceive the world. — neither work very well in complicated domains.

Answer 19

A better architecture is a hierarchy of controllers. Each controller sees the controllers below it as a virtual body from which it gets percepts and sends commands. The lower-level controllers can run much faster, and react to the world more quickly deliver a simpler view of the world to the higherlevel controllers.

Answer 20

States Actions Goal Test Path cost

Answer 21

A search problem can be defined as follows: The initial state that the agent starts in. A set of one or more goal states. The actions available to the agent. Given a state s ACTIONS(s) returns a finite set of actions that can be executed in s. A transition model, which describes what each action does. A sequence of actions forms a path, and a solution is a path from the initial state to a goal state.

Answer 22

A search algorithm takes a search problem as input and returns a solution, or an indication of failure. The state space describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another. The search tree describes paths between these states, reaching towards the goal. We can expand the node, by considering the available Actions for that state, using the Result function to see where those actions lead to, and generating a new node.

Answer 23

Three kinds of queues are used in search algorithms: A priority queue first pops the node with the minimum cost according to some evaluation function, It is used in best-first search. A FIFO queue or first-in-first-out queue first pops the node that was added to the queue first; we shall see it is used in breadth-first search. A LIFO queue or last-in-first-out queue (also known as a stack) pops first the most recently added node; we shall see it is used in depthfirst search.

Answer 24

Uninformed strategies use only the information available in the problem definition Breadth-first search Depth-first search Uniform-cost search Depth-limited search Iterative deepening search

Answer 25

Standard search problem: state is a “black box”—any old data structure that supports goal test, eval, successor CSP: state is defined by variables Xi with values from domain Di goal test is a set of constraints specifying allowable combinations of values for subsets of variables Simple example of a formal representation language Allows useful general-purpose algorithms with more power than standard search algorithms

Answer 26

* determine whether or not a solution exists * find a solution * find all solutions * count the number of solutions * find the best solution given some solution quality * soft constraints specify preferences * determine whether some property holds in all of the solutions

Answer 27

Binary CSP: each constraint relates at most two variables Constraint graph: nodes are variables, arcs show constraint

Answer 28

finite domains; complete assignments ♦ e.g., Boolean CSPs, incl. Boolean satisfiability (NP-complete) infinite domains (integers, strings, etc.) ♦ e.g., job scheduling, variables are start/end days for each job ♦ need a constraint language, e.g., StartJob1+ 5 ≤ StartJob3 ♦ linear constraints solvable, nonlinear undecidable Continuous variables ♦ e.g., start/end times for Hubble Telescope observations ♦ linear constraints solvable in poly time by LP methods

Answer 29

* agent observes input-output pairs * learns a function that maps from input to output

Answer 30

agent learns patterns in the input without any explicit feedback * clustering

Answer 31

agent learns from a series of reinforcements: rewards & punishments

Answer 32

* Use bias to analyze hypothesis space * the tendency of a predictive hypothesis to deviate from the expected value when averaged over different training set * Underfitting: fails to find a pattern in the data * Variance: the amount of change in the hypothesis due to fluctuation in the training data. * Overfitting: when it pays too much attention to the particular data set it is trained on, causing it to perform poorly on unseen data. * Bias–variance tradeoff: a choice between more complex, low-bias hypotheses that fit the training data well and simpler, low-variance hypotheses that may generalize better.

Answer 33

Example problem: Restaurant waiting * the problem of deciding whether to wait for a table at a restaurant. * For this problem the output, y, is a Boolean variable that we will call WillWait. * The input, x, is a vector of ten attribute values, each of which has discrete values: 1. Alternate: whether there is a suitable alternative restaurant nearby. 2. Bar: whether the restaurant has a comfortable bar area to wait in. 3. Fri/Sat: true on Fridays and Saturdays. 4. Hungry: whether we are hungry right now. 5. Patrons: how many people are in the restaurant (values are None, Some, and Full). 6. Price: the restaurant’s price range ($, $$, $$$). 7. Raining: whether it is raining outside. 8. Reservation: whether we made a reservation. 9. Type: the kind of restaurant (French, Italian, Thai, or burger). 10. WaitEstimate: host’s wait estimate: 0–10, 10–30, 30–60, or >60minutes

Answer 34

* Task of finding a good hypothesis as two subtasks: * Model selection: model selection chooses a good hypothesis space * Optimization (training) finds the best hypothesis within that space. A training set to create the hypothesis, and a test set to evaluate it. Error rate: the proportion of times that h(x) /= y for an (x, y) Three data sets are needed: 1. A training set to train candidate models. 2. A validation set, also known as a development set or dev set, to evaluate the candidate models and choose the best one. 3. A test set to do a final unbiased evaluation of the best model. When insufficient amount of data to create three sets: k-fold cross-validation * split the data into k equal subsets * perform k rounds of learning * on each round 1/k of the data are held out as a validation set and the remaining examples are used as the training set. * Popular values for k are 5 & 10 * leave-one-out cross-validation or LOOCV, k=

Answer 35

Parametric model: learning model that summarizes data with a set of parameters of fixed size (independent of the number of training examples) Nonparametric model: model that cannot be characterized by a bounded set of parameters One example piecewise linear function that retains all the data points as part of the model. (instance-based learning or memory-based learning) Simplest instance-based learning method: table lookup * take all the training examples, put them in a lookup table, and then when asked for h(x), see if x is in the table; if it is, return the corresponding y.

Answer 36

The idea of ensemble learning is to select a collection, or ensemble, of hypotheses, h1 , h2 , . . . , hn , and combine their predictions by averaging, voting, or by another level of machine learning * individual hypotheses: base models * Combination of base models: Ensemble models * Reasons to do ensemble learning * Reduce bias, ensemble can be more expressive thus less bias than base models * Reduce variance, it is hoped it is less likely multiple classifiers will misclassify

Answer 37

* generate K distinct training sets by sampling with replacement from the original training set. * randomly pick N examples from the training set, but each of those picks might be an example picked before. * run our machine learning algorithm on the N examples to get a hypothesis * repeat this process K times, getting K different hypotheses * aggregate the predictions from all K hypotheses. * for classification problems, that means taking the plurality vote (the majority vote for binary classification). * for regression problems, the final output is the average of hypotheses:

Answer 38

Random forests * a form of decision tree bagging * randomly vary the attribute choices * At each split point in constructing the tree, we select a random sampling of attributes, and then compute which of those gives the highest information gain * Given n attributes, 𝑛 common number of attributes randomly picked at each split for classification n/3 for regression problems. * Extremely randomized trees (ExtraTrees): * for each selected attribute, randomly sample several candidate values from a uniform distribution over the attribute’s range. * select the value that has the highest information gain. * Pruning prevents overfitting

Answer 39

Stacking * combines multiple base models from different model classes trained on the same data * approach: * use the same training data to train each of the base models, * use the held-out validation data (plus predictions) to train the ensemble model. * Also possible to use cross-validation if desired. * can be thought of as a layer of base models with an ensemble model stacked above it, operating on the output of the base models

Answer 40

Boosting * weighted training set: each example has an associated weight wj ≥ 0 that describes how much the example should count during training. * Start with first hypothesis h1 . * increase their weights while decreasing the weights of the correctly classified examples. * process continues in this way until we have generated K hypotheses, where K is an input to the boosting algorithm. * Similar to a Greedy algorithm in the sense that it does not backtrack; once it has chosen a hypothesis hi it will never undo that choice; rather it will add new hypotheses

AI Flashcards

(74 cards)