Inductive vs Deductive Reasoning

• Deductive Reasoning: Starts with a knowledge base of facts and use logic or other systematic methods in order to make inferences. There are several approaches to deductive reasoning, including search and logic-based methods.

• Inductive Reasoning: Starts with specific observations or examples and generalizes them to form broader rules or patterns. Inductive reasoning is often used in machine learning, where algorithms learn from data to make predictions or decisions.

1 Deductive Reasoning in Artificial Intelligence¶

Deductive reasoning in AI involves using domain knowledge to make systematic inferences. Key methods include:

Constraint Satisfaction Problems (CSPs)

• A set of variables, each with a domain of possible values.

• A set of constraints that specify allowable combinations of values for subsets of variables.

Search Algorithms

Finding solutions in state spaces:

• Uninformed search: BFS, DFS, UCS (Chapter 2)

• Informed search: A*, Greedy best-first (Chapter 2)

• Local search: Hill climbing, simulated annealing (Chapter 2)

Logic-Based Systems

Formal reasoning using logical inference:

• Propositional logic: Boolean reasoning (Chapter 4)

• First-order logic: Predicates and quantifiers (Chapter 5)

• Resolution: Proof technique

• Theorem proving: Automated deduction

Expert Systems

Knowledge bases with inference rules:

• Forward chaining: Data-driven reasoning

• Backward chaining: Goal-driven reasoning

• Example: MYCIN for medical diagnosis

1.1 Constraint Satisfaction Problems (CSPs)¶

Constraint Satisfaction Problems involve finding values for a set of variables that satisfy all given constraints in a problem domain. CSPs are widely used in AI for tasks such as scheduling, resource allocation, and puzzle solving.

1.1.1 Modeling Sudoku as a CSP¶

• Variables: Each cell in the Sudoku grid.

• Domain: Numbers 1-9 for each cell.

• Constraints: No repeated numbers in any row, column, or 3x3 subgrid.

Given the following Sudoku puzzle, fill in the missing numbers to satisfy the constraints.

How to represent the Sudoku problem as a CSP:

• Variables: Each cell in the 9x9 grid (e.g., $(X_{1,1}, X_{1,2}, \ldots, X_{9,9})$ ).

• Domains: The possible values for each variable (1-9).

• Constraints:

  • Row constraints: All numbers in a row must be different.

    $$\forall i \in \{1, \ldots, 9\}, \forall j, k \in \{1, \ldots, 9\}, j \neq k: X_{i,j} \neq X_{i,k}$$

    (1)

• Column constraints: All numbers in a column must be different.

  $$\forall j \in \{1, \ldots, 9\}, \forall i, k \in \{1, \ldots, 9\}, i \neq k: X_{i,j} \neq X_{k,j}$$

  (2)

• Subgrid constraints: All numbers in each 3x3 subgrid must be different.

  $$\forall m, n \in \{0, 1, 2\}, \forall i, j, k, l \in \{1, 2, 3\}, (i,j) \neq (k,l): X_{3m+i, 3n+j} \neq X_{3m+k, 3n+l}$$

  (3)

1.1.2 implementing SUDOKU using python-constraint library¶

1.1.3 Modeling the 8-Queens Problem as a CSP¶

Given an 8x8 chessboard, place 8 queens such that no two queens threaten each other (i.e., no two queens share the same row, column, or diagonal).

• Variables: $Q_1, Q_2, \ldots, Q_8$ (each representing the column position of a queen in each row).

• Domains: $\{1, 2, \ldots, 8\}$ for each variable.

• Constraints:

  • Row constraints: Each queen must be in a different row (inherent in the variable definition).

  • Column constraints: No two queens can be in the same column.

    $$\forall i, j \in \{1, \ldots, 8\}, i \neq j: Q_i \neq Q_j$$

    (5)

  • Diagonal constraints: No two queens can be on the same diagonal.

    $$|Q_i - Q_j| \neq |i - j|, \forall i, j \in \{1, \ldots, 8\}, i \neq j$$

    (6)

The absolute difference between the column positions of two queens must not equal the absolute difference between their row positions. This ensures that they are not on the same diagonal. for example, if queen $Q_1$ is in row 1 and column 3 ($Q_1 = 3$) and queen $Q_2$ is in row 2 and column 5 ($Q_2 = 5$), then:

Since 2 is not equal to 1, the queens are not on the same diagonal.

1.1.4 Solving the 8-Queens Problem using python-constraint library¶

1.1.5 Modeling the traveling Salesman Problem (TSP) as a CSP¶

The Traveling Salesman Problem (TSP) involves finding the shortest possible route that visits a set of cities and returns to the origin city.

• Given a set of cities denoted by ${1,\ldots,n}$ and the distances between each pair of cities denoted by $d(i,j)$, the goal is to find tour of the cities of cost at most $C$.

• There are $(n(n-1))$ variables $X_{i,j}$, where $X_{i,j} = 1$ if the tour goes directly from city $i$ to city $j$, and $X_{i,j} = 0$ otherwise.

• The constraints are:
  -Each city must be entered and exited exactly once:

  $$\forall i \in \{1, \ldots, n\}: \sum_{j=1, j \neq i}^{n} X_{i,j} = 1$$

  (9)
  $$\forall j \in \{1, \ldots, n\}: \sum_{i=1, i \neq j}^{n} X_{i,j} = 1$$

  (10)

  -The total cost of the tour must not exceed $C$:

  $$\sum_{i=1}^{n} \sum_{j=1, j \neq i}^{n} d(i,j) \cdot X_{i,j} \leq C$$

  (11)

1.1.6 Modeling the graph coloring problem as a CSP¶

The graph coloring problem involves assigning colors to the vertices of a graph such that no two adjacent vertices share the same color.

Given an undirected graph $G = (V, E)$ and a set of colors ${1, \ldots, k}$, the goal is to assign a color to each vertex such that no two adjacent vertices share the same color.

• This problem is closely related to the map coloring problem,wherein we wish to color the regions (e.g., provinces or states) in a map, so that each pair of adjacent regions has different colors.

• The map coloring problem has practical applications in cartography, because it helps visually distinguish the different regions in the map.

Modeling the graph coloring problem as a CSP:

• Variables: $n\times k$ binary variables $X_{i,c}$, where $X_{i,c} = 1$ if vertex $i$ is assigned color $c$, and $X_{i,c} = 0$ otherwise.

• Domains: $\{0, 1\}$ for each variable.

• Constraints:

  • Color each node exactly once:

    $$\sum_{c=1}^{k} X_{i,c} = 1, \forall i \in \{1, \ldots, n\}$$

    (12)

  • Adjacent nodes must have different colors:

    $$X_{i,c} + X_{j,c} \leq 1, \forall (i,j) \in E, \forall c \in \{1, \ldots, k\}$$

    (13)

1.2 Solving NP-Hard Problems¶

• Many problems in artificial intelligence suffer from the combinatorial explosion in the number of possible solutions as the problem size increases. For example, in the case of the eight queens problem, one has to choose eight positions out of 64 positions. The number of possible solutions is given by

• Generalizing the eight queens problem to the n-queens problem leads to an NP-hard setting.

• The Traveling Salesman Problem (TSP) is another classic NP-hard problem where the goal is to find the shortest possible route that visits a set of cities and returns to the origin city. An instance of TSP with n cities has $(n-1)!$ possible routes, which grows factorially with n.

• Many other problems in AI, such as scheduling, vehicle routing, and resource allocation, are also NP-hard.

1.3 Expert Systems¶

• Expert systems are AI programs that mimic the decision-making abilities of a human expert. They use a knowledge base of human expertise and an inference engine to solve specific problems within a certain domain.

• Components of expert systems:

  • Knowledge Base: Contains domain-specific knowledge, including facts and rules.

  • Inference Engine: Applies logical rules to the knowledge base to deduce new information or make decisions.

  • User Interface: Allows users to interact with the expert system, input data, and receive advice or solutions.

• Applications of expert systems:

  • Medical diagnosis (e.g., MYCIN)

  • Financial forecasting

  • Troubleshooting and repair (e.g., XCON)

For example, consider a patient, John, who comes to a doctor, while presenting the following facts about their situation:

• John is running a temperature

• John is coughing

• John has colored phlegm

Now imagine a case where the expert system contains the following subset of rules:

• IF coughing AND temperature THEN infection

• IF colored phlegm AND infection THEN bacterial infection

• IF bacterial infection THEN administer antibiotic

A doctor can then enter John’s symptoms in the expert system and then use a chain of inferences in order to conclude that an antibiotic needs to be administered to John.

2 Inductive Learning in Artificial Intelligence¶

Inductive learning involves discovering patterns from data. There are three main types:

2.1 Supervised Learning¶

Supervised learning learns from labeled examples to predict outputs for new inputs.

Key Idea: Given training data with known answers (labels), learn a function that maps inputs to outputs.

Mathematical Formulation:

• Training data: $((X_1, y_1), (X_2, y_2), \ldots, (X_n, y_n))$

• Goal: Learn function $(f)$ such that $y_i \approx f(X_i)$

• Minimize loss: $L = \sum_{i=1}^{n} (y_i - f(X_i))^2$

Types of Supervised Learning:

1. Classification: Predict categorical labels

   • Binary: spam/not spam, disease/healthy

   • Multi-class: digit recognition (0-9), animal species

   • Algorithms: Logistic regression, decision trees, SVM, neural networks

2. Regression: Predict numerical values

   • Linear regression: house prices, temperature

   • Polynomial regression: non-linear relationships

   • Algorithms: Linear regression, polynomial regression, neural networks

Linear Regression Example (Conceptual):

Goal: Find line $y = mx + b$ that best fits training data

Training data: (1, 3), (2, 5), (3, 7), (4, 9)

Method: Minimize sum of squared errors
  Error = Σ(actual_y - predicted_y)²

Result: y = 2x + 1

Prediction: For x=5, predict y = 2(5) + 1 = 11

Analogy: Learning with a teacher who provides correct answers

2.2 Unsupervised Learning¶

Unsupervised learning discovers patterns in data without labeled examples.

Key Idea: Find hidden structure in unlabeled data.

Common Tasks:

1. Clustering: Group similar data points

   • K-means: Partition into k clusters

   • Hierarchical: Build tree of clusters

   • DBSCAN: Density-based clustering

   • Applications: Customer segmentation, document organization

2. Dimensionality Reduction: Compress data to fewer dimensions

   • PCA: Principal Component Analysis

   • t-SNE: Visualizing high-dimensional data

   • Applications: Feature extraction, data visualization

3. Anomaly Detection: Find unusual patterns

   • Isolation Forest

   • One-class SVM

   • Applications: Fraud detection, network intrusion

K-Means Clustering (Conceptual):

Algorithm: K-Means(data, k)
  1. Initialize k random centroids
  2. Repeat until convergence:
     a. Assign each point to nearest centroid
     b. Update centroids to mean of assigned points
  3. Return cluster assignments

Example:

Data: Customer purchase patterns
  - Age, annual spending
  
Result: 3 clusters discovered
  - Cluster 1: Young, low spending
  - Cluster 2: Middle-aged, high spending
  - Cluster 3: Senior, medium spending

Analogy: Learning without a teacher - discovering patterns on your own

2.3 Reinforcement Learning¶

Reinforcement learning learns by trial and error through interaction with an environment, receiving rewards or penalties.

Key Idea: An agent learns which actions to take by trying them and observing the results.

Core Components:

• Agent: The learner/decision maker

• Environment: What the agent interacts with

• State (s): Current situation

• Action (a): What the agent can do

• Reward (r): Feedback (positive or negative)

• Policy (\pi(s)): Strategy for selecting actions

Goal: Maximize cumulative reward over time

where (\gamma \in [0,1]) is the discount factor.

Key Algorithms:

1. Value-Based: Learn value function

   • Q-Learning

   • Deep Q-Networks (DQN)

2. Policy-Based: Learn policy directly

   • Policy Gradient

   • Actor-Critic

3. Model-Based: Learn environment model

   • AlphaZero (combines with tree search)

Multi-Armed Bandit (Simple RL Example):

Problem: Choose between k slot machines
  - Each machine has unknown reward distribution
  - Goal: Maximize total reward

Epsilon-Greedy Strategy:
  - With probability ε: explore (random action)
  - With probability 1-ε: exploit (best known action)
  
Example: 3 machines with true values [1.0, 2.0, 1.5]
  After 1000 trials:
    Learned estimates: [0.98, 2.02, 1.47]
    Machine 2 selected 70% of the time

Applications:

• Game playing: AlphaGo, AlphaZero, OpenAI Five

• Robotics: Walking, manipulation, navigation

• Autonomous vehicles: Decision making

• Resource management: Data center cooling, traffic lights

Analogy: Like training a dog - reward good behavior, penalize bad behavior

Comparing Learning Types¶