COMP7404 Topic 2 Beyond Classical Search

Author: Arthur | 478 words, 3 minutes | 2020-10-04 | Category: Notes

comp7404, hku, machine learning

Translations: ZH

COMP7404 Computational Intelligence and Machine Learning

Planning vs Identification

  • Planing: sequence of actions
    • The path to the goal is the important thing
    • Paths have various costs, depths
    • Heuristics to guide, frontier to keep backups
  • Identification: assignments to variables
    • The goal itself is important, not the path

Local Search can find solutions faster for specific types of identification problems

Local Search

  • Evaluate and modify one current state rather than systematically explore paths from an initial state
  • Suitable for problems were all that matters in the solution state and not the path cost to reach it
  • Although local search algorithms are not systematic they have two advantages
    • Require very little memory
    • Often find reasonable solutions in large spaces

Local Search Algorithm

	Randomly initialize currentState
	If cost of currentState == 0 return currentState
	If min(cost(getNeighbors(currentState))) > cost(currentState)
		goto step 1 (we have reached a local minimum)
	Select cheapest neighbor as currentState and goto step2

Example: 8-Queens

  • States
    • Each state has 8 queens on board, one per column
  • Successors
    • All possible states generated by moving single queen to another square in the same column
  • Cost function
    • Number of pairs of queens that are attacking each other, either directly and indirectly

Constraint Satisfaction Problems

CSPs use a factored representation for states

  • A set of variables, each of which has a value

Defining CSPs

  • A CSP consists of three components
    • A set of variables, X = {X1,…,Xn}
    • A set of domains, D = {D1,…,Dn}, where Di = {V1,…,Vk} for each variable Xi
    • A set of constraints C which specify allowable combinations of values
  • To solve a CSP we need to define a state space
    • Each state is defined by an assignment of values to some or all variables {Xi = Vi, Xj = Vj,…}

Solving CSPs

  • States are defined by the values assigned so far
  • Initial state
    • Empty assignment {}
  • Successor function
    • Assign a value to an unassigned variable
  • Goal test
    • Current assignment is complete and consistent

Solutiona to CSPs

  • Consistent - No constraints are violated
  • Complete - Every variable is assigned

Backtracking Search (The basic algorithm for solving CSPs)

Idea

  • Only consider assignments to a single variable at each point
  • Only allow legal assignemnts to each point

DFS with these two ideas is called backtracking search

Improving Backchecking

Idea

  • Forward checking (FC)
  • Constraint propagation (AC-3)

Filtering: Forward Checking

  • Filtering
    • Keep track of domains for unassigned variables and cross off bad options
  • Forward checking
    • Cross off values that violate a constraint when added to the existing assignment

Improving Backtracking Further

  • Variable Ordering
    • Minimum remaining values (MRV)
      • Choose the variable with the fewest legal left values in its domain
        • Most constraint variable
        • Fail-first heuristic
      • Tie-breaker among MRV variables
        • Degree Heuristic (Deg)
          • Choose the variable with the most constraints on remaining variables
  • Value Ordering
    • Least constraining value (LCV)
      • Choose the value that rules out the fewest values in the remaining variables

Related Posts

2020-11-11
xDeepFM for Recommender Systems - 推荐系统
2020-10-05
COMP7404 Topic 3 Adversarial Search
2020-09-16
COMP7404 Topic 1 Solving Problems by Searching
Arthur

Author

Arthur

Blockchain (Golang) Developer, MSc Student in Department of Computer Science @ The University of Hong Kong (HKU). Love to learn and build things. Follow me on GitHub