O GoConqr está de visual novo! Conte para nós o que você achou.

Registre-se grátis

Flashcards

Artificial Intelligence

Brenna Cantwell Inglês 34 flashcards

Flashcards do conjunto (34)

  1. 1What is a policy? How is an optimal policy determined?A mapping of what action an agent should take given any possible state. The optimal policy is determined by the expected utility of its resulting state; optimal policies result in states yielding the highest expected utility.
  2. 2What is the relationship between a rational agent and an agent function, and a rational agent and a performance measure?An agent is something that perceives and acts in an environment. An agent function specifies the action taken by an agent in response to any percept sequence. A performance measure evaluates an agent's behavior. A rational agent acts as to maximize the expected value of the performance measure.
  3. 3Compare a fully observable environment with a partially observable one. Provide an example of each.A fully-observable environment provides all the information required for an agent to make a rational decision (Ex: tic-tac-toe board, chess board). A partially observable environment only provides some information about what action to take (Ex: minesweeper, card games.)
  4. 4What are some factors that prevent a partially-observable environment from being fully-observable?1. Inadequate sensing ("fog of war")
    2. Inaccurate or noisy sensing
    3. Sensing too slow (environment changes too quickly)
    4. Environment is too complex, information too much to store
  5. 5Compare a deterministic environment with a stochastic environment, and provide an example of each.In a deterministic environment, every state is completely determined by the current state and the action executed by the agent. (Ex: solitaire) In a stochastic environment, there is a degree of randomness involved (Ex: any gambling game.)
  6. 6Compare a discrete environment with a continuous environment, and provide an example of each.A discrete environment has a finite number of possible states, (Ex: tic-tac-toe, chess). If there are an infinite number of possible states, the environment is continuous (Ex: robotics, trading, medical diagnoses.)
  7. 7Define the following search algorithm criteria: Completeness Optimality Optimal Solution Time Complexity Space ComplexityCompleteness: the algorithm is guaranteed to find a solution
    Optimality: the algorithm is guaranteed to find the best solution
    Optimal Solution: the action sequence from initial state to goal state with the lowest possible cost
    Time complexity: how long it takes to find a solution in the worst case
    Space Complexity: how much memory is required to find a solution, in the worst case
  8. 8What is the correct data structure to implement the breadth-first search? What are the operations available to this data structure?A FIFO queue, with the following operations:
    enqueue(Queue, new element)
    dequeue(Queue)
    peek(Queue)
    isEmpty(Queue)
    size(Queue)
  9. 9Evaluate the Breadth-First Search according to Completeness, Optimality, TIme Complexity, and Space ComplexityCompleteness: Yes
    Optimality: No--BFS will find the path with the least number of steps (the shallowest)
    BFS is only optimal if we are in a grid-world with uniform cost
    Time Complexity: O(b^d)--in the worst case, BFS will traverse every edge of the graph
    Space Complexity: O(b^d)--in the worst case, BFS stores every vertex node it visits
  10. 10What is the correct data structure to implement the depth-first search? What are the operations available to this data structure?A LIFO stack, with the following operations:
    push(Stack, new element)
    pop(Stack)
    peek(Stack)
    isEmpty(Stack)
    size(Stack)
  11. 11Evaluate the Depth-First Search according to Completeness, Optimality, TIme Complexity, and Space ComplexityCompleteness: No
    Optimality: No, it chooses path with most steps
    Time Complexity: In the worst case, DFS traverses every edge O(b^m)
    Space complexity: In the worst case, DFS stores every vertex in graph O(b*m)
  12. 12What is "big O" notation and what do the variables b, d, m, C*, and e represent?Big O analysis measures the efficiency of an algorithm based on the time it takes for the algorithm to run as a function of the input size. The variables used represent parts of a search tree:
    b=branching factor (number of branches)
    d=depth of the shallowest solution
    m=maximum depth of tree
    C*=optimal cost
    e=least cost action
  13. 13What is the correct data structure to implement the uniform cost search? What are the operations available to this data structure?A priority queue, with the following operations:
    push(Queue, new element, value)
    pop(Queue)
    peek(Queue)
    isEmpty(Queue)
    size(Queue)
  14. 14Evaluate the Uniform Cost Search according to Completeness, Optimality, TIme Complexity, and Space ComplexityCompleteness: Yes
    Optimality: Yes, when a node is expanded, the lowest cost path has been found
    Time Complexity: O (b^(1+C*/e))--UCS must wait to find optimal path, even if it has discovered the goal node
    Space Complexity: O (b^(1+C*/e))
  15. 15Name the uninformed search that is an extension of DFS, and explain how it works.Iterative deepening--a version of DFS that sets the maximum depth to 1, and loops through each branch, incrementing the depth by 1 until the goal node is reached.
  16. 16A* is an extension of which uninformed search? What makes A* informed?A* is an extension of the Uniform Cost Search, and is considered informed because it employs a heuristic function h(n), to apply prior knowledge of the problem to pruning down solution possibilities. A* is a type of Best-First Search
  17. 17Evaluate the A* Search according to Completeness, Optimality, Time Complexity, and Space Complexity—What is special about A*’s efficiency? What condition must be true for it to be both complete and optimal?Complete: Yes, with a finite number of nodes
    Optimal: Yes
    Time Complexity: O (b^(1+C*/e))
    Space Complexity: O (b^(1+C*/e))
    A* is optimally efficient—it is guaranteed to expand the fewest number of nodes to reach the goal.
    A* is Complete and Optimal as long as its heuristic function (h(n)) is both admissible and consistent.
  18. 18What is a technique for quickly generating an admissible heuristic?Generate a relaxed problem—remove any restrictions on actions or obstacles from the original. The relaxed problem can generate better solutions by adding available edges to the graph. The cost of an optimal solution to the relaxed problem is automatically an admissible heuristic for the original problem.
  19. 19What is a zero-sum game?A mathematical representation of a game in which each player's gain/loss of utility is exactly balanced by the gains/loss of their opponent's.
  20. 20Explain how the Minimax algorithm affects zero-sum games.Minimax solutions guarantee a maximum payoff, V, for player 1, and -V for player 2. Minimax is used to determine a mixed strategy such that player 1 minimizes the maximum payoff for player 1, and player 2 minimizes the maximum payoff for player 1.
  21. 21MDP's are defined by a _______ model specifying the probabilistic outcomes of actions and a _______ function for each state.transition model, reward
  22. 22MDP's are used for ________ decision problems in ______environmentssequential, stochastic
  23. 23The solution of an MDP is a ______ that associates a decision with every state the agent might reach.policy
  24. 24The value iteration algorithm for solving MDP's works by solving the equations through successive ________, relating the utility of each state to those of its ______.iterations, neighbors
  25. 25The value iteration algorithm is used for calculating an optimal policy by calculating state_________ and using them to determine an optimal action in each state.utilities
  26. 26A discount factor is a number between ___ and ____ that describes the preference of an agent for ______ rewards over ______ rewards.0 and 1
    current
    future
  27. 27An optimal policy is represented by _____ and its actions by _______π *, π * (s)
  28. 28A _______ expresses the desirability of a state, while the _______ of an actions represents the average utility value of the outcomes, weighted by their probabilities.utility function U(s)
    expected utility EU
  29. 29The _______ specifies the probability of each complete assignment of values to random variables.full joint probability distribution
  30. 30________ rule allows unknown probabilities to be computed from known conditional probabilities.Bayes' Rule
  31. 31Given a game tree, the optimal strategy can be determined by the ________value of each node.minimax
  32. 32What's the evaluation function for the A* search algorithm?f(n) = g(n) + h(n)
  33. 33The ______ search algorithm uses simulated playouts on each expanded node, using backpropogation to update the current move sequence with simulation results.MonteCarlo Searchtree
  34. 34The Monte Carlo Tree Search is beneficial in being suitable for _______ combinatorial spaces, but is not a _______search and can fail to find reasonable moves.large, complete

Informações

Descrição
FlashCards sobre Artificial Intelligence, criado por Brenna Cantwell em 20-07-2016.
Criado por
Brenna Cantwell · jul 2016
Atualizado
23 ago 2016
Visualizações
2
Avaliação

Fale Conosco

Sobre o que é sua mensagem?

O que você acha do novo visual?

Você gostou?