question

Artificial Intelligence

answer

The study and design of intelligent agents, where an intelligent agent is a system that perceives its environment and takes actions that maximize its chances of success

question

Fours Schools of Thought

answer

Thinking Humanly v. Thinking Rationally v. Acting Humanly v. Acting Rationally ACTING RATIONALLY is the one we study

question

Rational Agent

answer

An agent that acts so as to achieve the best outcome, or when there is uncertainty, the best expected outcome

question

Agent Equation

answer

Agent = Architecture + Program

question

Agent

answer

Perceives its environment through SENSORS and acts upon that environment through ACTUATORS Perceive --> Think --> Act

question

PEAS

answer

Performance, Environment, Actuators, Sensors

question

Fully v. Partially Observable

answer

an agent's sensors give it access to complete state

question

Deterministic v. Stochastic

answer

Next state is completely determined by current state, instead of random chance

question

Episodic vs. Sequential

answer

Agent's experience is divided into atomic "episodes," choice depends only on the episode itself

question

Discrete v. Continuous

answer

A limited number of distinct, clearly defined percepts and actions i.e. checkers

question

Simple Reflex Agents

answer

select BASED ON CURRENT STATE ONLY - fully observable, simple but limited i.e. vacuum

question

Model-Based Reflex Agents

answer

Agent needs some GOAL INFORMATION - combines goal information with environment model to choose actions that achieve the goal

question

Utility-Based Agents

answer

Agent happiness is taken into consideration - UTILITY is the agent's performance measure

question

Learning Agents

answer

4 components: learning element, performance element, critic, problem generator

question

Goal-Based Agents

answer

Agents that work toward a goal, consider the impact of actions on future states, job is to identify the action or series of actions that lead to the goal - formalized as a SEARCH through possible solutions

question

Search Problem Formulation

answer

Initial State, States, Actions, Transition Model, Goal Test, Path Cost

question

State Space

answer

A physical configuration

question

Search Space

answer

An abstract configuration represented by a search tree or graph of possible solutions

question

Search Tree

answer

Models the sequence of actions - root is the initial state, branches are the actions, nodes are results from actions

question

Search Space Regions

answer

Explored, Frontier, Unexplored

question

Completeness

answer

Does it always find a solution if one exists?

question

Time Complexity

answer

Number of nodes generated/expanded

question

Space Complexity

answer

Maximum number of nodes in memory

question

Optimality

answer

Does it always find a least-cost solution?

question

b

answer

maximum branching factor of the search tree

question

d

answer

depth of the solution

question

m

answer

maximum depth of the state space

question

BFS

answer

Expand the shallowest node Complete, O(b^d) time, O(b^d) space, optimal

question

DFS

answer

Expand deepest first Not complete! O(b^m) time, O(bm) space, not optimal

question

Depth-Limited Search

answer

DFS with depth limit l, select some limit L in depth to explore with DFS, iterative deepening increases the limit l

question

Uniform Cost Search

answer

We want the cheapest path, not the shallowest solution --> prioritize by cost, not depth, expand node n with the lowest path cost g(n)

question

Informed Search

answer

Use a heuristic function that estimates how close a state is to the goal, allows us to know whether we're actually getting closer to the goal

question

Greedy Search

answer

h(n) is our heuristic function, estimates the cost from n to the closest goal

question

Common Heuristic Functions

answer

straight-line distance, Manhattan distance

question

A* Search

answer

minimize the total estimated solution cost - g(n) cost to reach node n, h(n) cost to get from n to goal, f(n) = g(n) + h(n) Complete, exponential time, every node in memory, but optimal!

question

Admissible Heuristic

answer

never overestimates the cost to reach the goal i.e. it is optimistic, for all node n, h(n) <= h*(n) or the real cost

question

Benefits of IDFS over BFS

answer

Memory! For BFS, we have to store all the nodes of the depth in memory! For IDFS, we can look at only the number in our current subtree

question

Local Search

answer

Iterative improvement algorithms, also pure optimization problems - the path doesn't matter! No need to maintain a search tree, use very little memory, often find good solutions Hill climbing, simulated annealing, local beam, genetic algorithms

question

Hill Climbing

answer

Greedy local search - looks only to immediate good neighbors and not beyond - search move uphill, terminates when it reaches a pick, can terminate with any maxima

question

Local Beam Search

answer

maintains k states instead of just one, selects the k best successor, useful information is passed amont the states

question

Stochastic Beam Search

answer

chooses k successors at random, helps alleviate the problem of states agglomerating around same part of state space

question

Generic Algorithms

answer

variant of stochastic beam search, successor states generated by combining two parents than modifying a single state, process inspired by natural selection, have a fitness function

question

Association Rules Two Steps

answer

Mining frequent patterns in D Generating strong association rules {Bread, Butter} frequent pattern Bread --> Butter strong rule

question

Item

answer

an object belong to L = {x1, x2,...,xm}

question

Itemset

answer

any subset of L

question

k-itemset

answer

itemset of cardinality k

question

P(L)

answer

lattice

question

Transaction

answer

itemset identified by a unique identifier tid

question

T

answer

set of all transaction ids

question

Tidset

answer

a subset of T

question

Transaction Dataset

answer

D = {(tid, Xtid) / tid in T, Xtid subset L}

question

Frequency

answer

|t(X)| = |{(tid, Xtid) in D / X subset Xtid}|

question

Support

answer

|t(X)| / |D|

question

Frequency itemset

answer

X is frequent iff supp(x) >= MinSupp

question

Support Downward Closure

answer

if an itemset is frequent, then all its subsets also are frequent

question

A-Priori Bottlenock

answer

billions of transactions, tens of thousands of items, terabytes of data --> multiple scans of dataset, HUGE number of candidate sets

question

Probabilistic Interpretation

answer

supp(A->C) = P(A ^ C) conf(A->C) = P(A ^ C) / P(A)

question

Cons of Support/Confidence

answer

Biased rules! Confidence cannot detect bias because it ignores support! tea -> coffee - everyone buys coffee, not just because it has tea

question

Interest

answer

P(A ^ C) / P(A) x P(C) = supp(A U C) / supp(A) x supp(C)

question

Multidimensional Rules

answer

Rather than just single rules, construct k-predicatesets instead of k-itemsets

question

AR Post-Processing

answer

Use evaluation measures, increase minimum support, increase minimum confidence, use rule templates

question

Quantitative AR

answer

Infinite Search space, support-confidence tradeoff, unsupervised discretization

question

Adversarial Search

answer

Games - multi-agent competitive environments, opponent we can't control planning against us, optimal solution is a strategy - modeled as search problems, use heuristics

question

Deterministic, Perfect Info

answer

chess, checkers, go, othello Deterministic, fully observable environments, zero-sum, two agents act alternately

question

Zero-Sum Games

answer

pure competition, agents have different values on the outcomes, one agent maximizes on single value, while the other minimizes it

question

Embedded Thinking

answer

one agent is trying to figure out what to do, thinks about the consequences of the possible actions, needs to think about his opponent as well, each will imagine what would be the response from the opponent to their actions

question

Formal Game

answer

Initial state, Player(s) defines which player has the move in state s, Actions(s) returns set of legal moves in s, transitin function S x A -> S, Terminal Test true when game is over, Utility(s,p) gives us utility for a game ending in terminal state s for player p

question

Minimax

answer

Compute each node's minimax value - the best achievable utility against an optimal adversary - minimax value is the best achievable payoff against best play - DFS of game tree, compute utility of being in a state assuming both players play optimally, propagate minimax values up the tree

question

Solutions to Minimax Search

answer

Replace terminal utilities with an evaluation function for non-terminal positions, use IDS, use pruning

question

alpha-beta pruning

answer

Sometimes, minimax decisions are independent of values of certain subtrees, send alpha, beta values down during search, update by propagating upwards values of terminal nodes

question

Move Ordering

answer

Can affect the effectiveness of alpha-beta pruning - examine first successors that are likely to be best - O(b^m/2) if we get an ideal orderinge

question

Real-Time Decisions

answer

alpha-beta still has to go all the way to the leaves, which is tough - bound the depth of search (cut off search), replace utility(s) with eval(s), evaluation function to estimate value of current board configurations

question

Expectiminimax

answer

Add a third level - Chance - if the player is chance, the value should be the expected value of the results of each of the options

question

K-Nearest Neighbors

answer

Given an example xq to be classified, we take the sign of the average K-nearest neighbors

question

Common Forms of Loss

answer

Classification Error, Least Square Loss, etc.

question

Avoid Overfitting

answer

Reduce number of features, do a model selection, use regularization, do cross-validation

question

K-Fold Cross Validation

answer

Method for estimating test error using training data, randomly partition data into k equal-sized subsets, use each subset as a test set once, using the other k-1 subsets as training

question

Accuracy

answer

percentage of predictions that are correct

question

Precision

answer

percentage of positive predictions that are correct

question

Recall

answer

percentage of positive cases that were predicted as positive

question

Specificity

answer

percentage of negative cases that were predicted as negative

question

Tree Classifier

answer

popular classification method, easy to understand, simple algorithmic approach, no assumption about linearity no need for numerical features, model is a tree

question

Entropy

answer

p+ log p+ - p- log p-

question

Information Gain

answer

measures the expected reduction in entropy caused by partitioning the examples according to the attributes

Artificial Intelligence Midterm

Unlock all answers in this set

Haven't found what you were looking for?

Search for samples, answers to your questions and flashcards