Summary
[ Intelligent Systems ] Summary | Lecture Notes
- Course
- Institution
Summary of 17 pages for the course Intelligent Systems at VU
[Show more]
2 reviews
By: berendwiewel • 2 year ago
By: nmokadem • 4 year ago
Seller
Follow
gg2000
Reviews received
Content preview
INTELLIGENT SYSTEMSLECTURE 1 – INTRODUCTION
MACHINE AS AN INTELLIGENT AGENT
Main methods to optimize for the best expected outcome: Text/image processing, data integration,
knowledge representation, automatic reasoning, machine learning and genetic programming (writing code to
improve its own behavior).
Philosophical questions: What is consciousness/free will? Can a machine be creative/have rights?
Ethical questions: surveillance/privacy, responsibility, accountability, using/misusing IS.
CORE TOPICS
• Topic 1: Search and heuristics (principal of rationality)
• Topic 2: Knowledge
• Topic 3: Adaptivity (machine learning)
STATE SPACE REPRESENTATION
Representing problems as state spaces problems (because the world is absurdly complex) à state spaces must
be abstracted/simplified for problem solving à (Abstract) solution = set of real paths that are solutions of the
real world.
1. What actions and states to consider, given a goal:
o What are appropriate states and initial states? (atomic)
o What are the possible actions to move between states? (atomic)
o What is the cost of an action?
2. Goal formulation: what are the successful world states?
3. Search: determine possible sequences of actions that lead to goal states and choose the “best”
sequence.
4. Execute: Give the solution and perform the actions.
Example - Romania:
⁃ Concrete problem: In Arad, flight from Bucharest.
o States: various (representation of) cities
o Actions: drive between cities
⁃ Concrete goal: Be in Bucharest
⁃ Find solution: sequence of best states (Arad à Sibiu à
Fagaras à Bucharest)
⁃ Execute plan: buy tickets + travel
SEARCH
Search through explicit tree generation:
1. ROOT = initial state
2. Nodes and leafs generated through successor function (related to action)
State = a (representation of) a physical configuration
Node = a data structure belonging to a search tree
1
,SEARCH STRATEGIES
Strategy = picking order of node expansion. Performance is measured in 4 ways:
1. Completeness: does it always find a solution if one exists?
2. Optimality: does it always find the least-cost solution?
3. Time Complexity: number of nodes generated/expanded?
4. Space Complexity: number of nodes stored in memory during search?
a. Time & Space complexity are measured in terms of problem difficulty:
i. b – maximum branching factor of the search tree (amount of possible choices)
ii. d – depth of the least-cost solution (best solution: best distance between root)
iii. m – maximum depth of the state space (may be infinite)
UNINFORMED SEARCH STRATEGIES
Uninformed search strategies (a.k.a. blind search) = use only information available in problem definition:
• Breadth-first search = expand SHALLOWEST unexpanded node
o Implementation: fringe is a FirstInFirstOut (FIFO) queue (A à B à C à D à E à F…)
§ Completion: Yes, if b is finite
§ Time complexity: Yes
§ Space complexity: Yes, if each node is retained in memory
§ Optimality: Yes, unless actions have different costs
• Disadvantage: longest path
• Depth-first search = expand DEEPEST unexpanded node
o Implementation: fringe is a LIFO queue (= stack) (A à B à D à H & I à E à J & K à C…)
§ Completion: No, unless search space is finite and no loops are possible
§ Time complexity: Yes, if many solutions, a bit faster than BF
§ Space complexity: Yes, backtracking search uses even less memory
§ Optimality: No, unless search space is finite and no loops are possible
• Depth-limited search = DF-search with depth limit l
§ Completion: Yes (if I >= d)
§ Optimality: No
• Depth-first Iterative Deepening search = Breadth-F + Depth search
§ Completion: Yes (no infinite paths)
§ Space Complexity: Yes
§ Optimality: Yes
• Bidirectional search
• Uniform-cost search
2
, LECTURE 2 – INFORMED & ADVERSARIAL SEARCH
INFORMED SEARCH (HEURISTICS)
General approach of informed search: best-first search (node is selected for expansion based on an evaluation
function f(n). Fringe = queue sorted in decreasing order of desirability.
Heuristic function = educated guess that reduces or limits the search for solutions in domains that are difficult
and poorly understood. Describes the expected quality of a node.
• h(n) = estimated cost of the cheapest path from node n to goal node.
• If n is goal, then h(n) = 0.
• Complete knowledge: often not available & too expensive to calculate
• Use partial knowledge/human expertise = educated guess (can be completely wrong)
Two elements, h1(n) and h2(n), with 0 < h1(n) < h2(n) < h *(n), then h2(n) is more informed than h1(n).
• Perfect heuristics: h(n) = h*(n)
• Trivial heuristics: h(n) = 0
o Advantage: With h1 fewer nodes have to be searched with h2
o Disadvantage: h2 is often more expensive to calculate.
ADVERSARIAL SEARCH
Games are a form of multi-agent environment. Competitive multi-agent environments give rise to adversarial
problems a.k.a. games. Easy to represent and agents restricted to small number of actions.
SEARCH – NO ADVERSARY
• Solution is (heuristic) method for finding goal
• Heuristics and CSP techniques can find optimal solution
• Evaluation function: estimate cost from start to goal
• Examples: path planning, scheduling activities
GAMES – ADVERSARY
• Solution is strategy (strategy specifies moves for every possible opponent reply)
• Time limits force an approximate solution
• Evaluation function: evaluate “goodness” of game position
• Examples: chess, checkers, Othello, backgammon, GO
Deterministic: you know where the figures are.
Chance: you know where the figures are, but there is always an element of chance.
MINMAX
• Two players: MAX and MIN
• MAX moves first (uses search tree to determine next move), and they take turns
until the game is over. Winner à reward & loser à penalty.
• Games as search
o Initial state: e.g. board configuration of chess
o Successor function: list of (move, state) pairs specifying legal moves
o Terminal test: is the game finished?
o Utility function: gives numerical value of terminal states
§ win (+1), lose (-1), draw (0) in tic-tac-toe
3
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller gg2000. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $9.62. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
53068 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now