ย
ย
DiscussionLJ
Types of AI Models
Reflex
- Regression
- Classification
ย
Map Coloring (Example)
- That can be solved using the state tree
- It can be treated as a searching problem:
- State: partial assignment of colors to provinces
- Action: assign next uncolored province a compatible color
ย
- This approach is not efficient and takes a long time, so we use the factor graph method.
Variables-Based Models: Factor Graphs
- Functions specifies the relationship between variables (or how they should be related)
- Variables: , where
- Factors: with each
- Each assignment has a weight:
- An assignment is consistent if
Objective of CSP:
- Find the maximum weight assignment:
- A CSP is satisfiable if
- This requires global reasoning over all the factors
ย
Note: weights cannot be negative like in ML
ย
Constraints Satisfaction Problems (CSP)
Boolean satisfiability (SAT)
- Variables are Booleans
- Factors are logical formulas (AND, OR, NOT)
It is NP-complete, so in the worst case it is really hard, and there is no efficient problem that can solve it.
Types of CSPs
Linear programming (LP)
- Variables are reals
- Factors are linear inequalities:
Integer linear programming (ILP)
- Same as LP but variables are integers
- This makes it hard to solve like SAT
Mixed integer programming (MIP)
- Same as LP but variables are reals and integers
- This makes it hard to solve like SAT
Model Real-World Problems as CSPs
- This lecture presents very useful demos on CSP
ย
ย
ย
ย
