Laplace Smoothing Practice Problem

This data science coding problem helps you practice Naive Bayes, laplace smoothing, and implementation skills. Read the problem statement, write your solution, and strengthen your understanding of Naive Bayes.

• Problem ID: 194
• Problem key: 194-laplace-smoothing
• URL: https://datacrack.app/solve/194-laplace-smoothing
• Difficulty: hard
• Topic: Naive Bayes
• Module: Supervised Learning

Problem Statement

# 🧩 Laplace Smoothing

---

### 🎯 Goal

Use Laplace smoothing to prevent zero likelihoods inside a full Naive Bayes train-and-predict workflow.

---

### 📖 Introduction

The previous train/predict problem separated Naive Bayes into two phases.

**Training phase** receives training features `X` and labels `y`. It learns and stores:

$$
P(class)
$$

and one likelihood table for each feature column:

$$
P(feature=value\mid class)
$$

**Prediction phase** receives the trained model and one query. It uses only the stored probabilities:

$$
Score(class)=P(class)\times\prod_i P(feature_i=value_i\mid class)
$$

Here, \(i\) refers to the position of a feature in the query. For each position \(i\), \(feature_i\) is the feature column, and \(value_i\) is the query value in that column. For example, if the columns are `color` and `size`, and the query is `["red", "small"]`, then the product means multiplying \(P(color=red\mid class)\) and \(P(size=small\mid class)\).

The only new idea in this problem is **Laplace smoothing** during training.

Without smoothing:

$$
P(value\mid class)=\frac{count(value,class)}{count(class)}
$$

With Laplace smoothing:

$$
P(value\mid class)=\frac{count(value,class)+1}{count(class)+K}
$$

where:

- `count(value,class)` is the number of times this value appears inside this class.
- `count(class)` is the number of training samples in this class.
- $K$ is the number of possible values for this feature column in the training data. For example, if the `color` column contains `red` and `blue`, then \(K=2\) for the `color` feature. This helps when a value exists in the training data but does not appear inside one specific class. For example, if `blue` never appears in class `A`, smoothing prevents \(P(blue \mid A)\) from becoming `0.0`.

> Laplace smoothing prevents a known training value from getting probability `0.0` for a class where it did not appear.

---

### 📖 Example Training Data

| color | size | class |
|---|---|---|
| red | small | A |
| red | large | A |
| blue | small | B |
| blue | large | B |

For query `["red", "small"]`, the value `red` exists in the training data, but it appears zero times inside class `B`. Laplace smoothing gives class `B` a small nonzero likelihood for `red` instead of killing the full score.

Important assumption: the query contains only values that appeared in the training data. 

---

### 💻 Task

Implement `smoothed_naive_bayes_predict(X, y, query)`.

Your nested training helper should create a model with this structure:

```python
{
    "classes": [...],
    "priors": {class_label: ...},
    "likelihoods": {
        class_label: [
            {value_1: probability, value_2: probability, ...},  # one dictionary for feature column 0
            {value_1: probability, value_2: probability, ...},  # one dictionary for feature column 1
            ...
        ]
    }
}
```

Your function should:

- Store one prior for every class.
- Store a smoothed likelihood table for every class and feature column.
- Use $\frac{count(value,class)+1}{count(class)+K}$ when creating likelihood tables during training.
- Use only the trained model during prediction.
- Return all class scores rounded to 6 decimals.
- Return the class with the highest score.
- Break ties alphabetically.
- Return `{"scores": {}, "prediction": None}` when there are no classes.

---

### 📥 Input / 📤 Output

**Input:** categorical feature matrix `X`, labels `y`, and one categorical `query`.

**Output:**

```python
{
    "scores": {"A": ..., "B": ...},
    "prediction": ...
}
```

---

### 🧩 Starter Code

```python
def smoothed_naive_bayes_predict(X, y, query):
    def train_model():
        # Learn priors and smoothed likelihood tables.
        pass

    def predict_with_model(model):
        # Use only the learned model to calculate class scores.
        pass

    # Train once, then predict with that model.
    pass
```

---

### 💡 Example

```python
X = [
    ["red", "small"],
    ["red", "large"],
    ["blue", "small"],
    ["blue", "large"],
]
y = ["A", "A", "B", "B"]

smoothed_naive_bayes_predict(X, y, ["red", "small"])
```

Expected output:

```python
{"scores": {"A": 0.1875, "B": 0.0625}, "prediction": "A"}
```

---

### ⚠️ Common Mistakes

- Adding unseen query values to the model during prediction.
- Applying smoothing during prediction instead of while building likelihood tables.
- Forgetting to add $K$ to the denominator.
- Using one shared $K$ for all feature columns.
- Recalculating probabilities from `X` and `y` inside the prediction helper.