Hands-on lab — Day 158: Naive Bayes and Text Classification

"""
Naive Bayes reference library.
"""
import numpy as np
import re


def tokenize(text: str) -> list[str]:
    """
    Tokenize raw text into lowercase alphanumeric words: [a-z0-9_]+
    """
    return re.findall(r"\b\w+\b", text.lower())


def build_vocabulary(corpus: list[str]) -> dict[str, int]:
    """
    Build word-to-index mapping sorted alphabetically from a list of documents.
    """
    vocab = set()
    for doc in corpus:
        tokens = tokenize(doc)
        vocab.update(tokens)
    sorted_words = sorted(list(vocab))
    return {w: i for i, w in enumerate(sorted_words)}


def text_to_bow(corpus: list[str], vocab: dict[str, int]) -> np.ndarray:
    """
    Convert text corpus into a Bag-of-Words count matrix (N, V).
    """
    matrix = np.zeros((len(corpus), len(vocab)), dtype=float)
    for doc_idx, doc in enumerate(corpus):
        tokens = tokenize(doc)
        for token in tokens:
            if token in vocab:
                matrix[doc_idx, vocab[token]] += 1.0
    return matrix


class ScratchMultinomialNB:
    """
    Multinomial Naive Bayes with Laplace smoothing:
    theta_{c, j} = (N_{c, j} + alpha) / (N_c + alpha * V)
    log P(y=c | x) = log P(y=c) + sum_j x_j * log theta_{c, j}
    """
    def __init__(self, alpha: float = 1.0):
        self.alpha = float(alpha)
        self.class_log_prior_ = None
        self.feature_log_prob_ = None
        self.classes_ = None

    def fit(self, X: np.ndarray, y: np.ndarray):
        X = np.asarray(X, dtype=float)
        y = np.asarray(y)
        self.classes_ = np.unique(y)
        num_classes = len(self.classes_)
        num_features = X.shape[1]
        
        self.class_log_prior_ = np.zeros(num_classes)
        self.feature_log_prob_ = np.zeros((num_classes, num_features))
        
        total_samples = len(y)
        
        for c_idx, c in enumerate(self.classes_):
            X_c = X[y == c]
            # Prior: P(y=c) = N_c / N
            self.class_log_prior_[c_idx] = np.log(len(X_c) / total_samples)
            
            # Word counts for class c
            word_counts_c = np.sum(X_c, axis=0) # (V,)
            total_words_c = np.sum(word_counts_c)
            
            # Laplace smoothed conditional probability:
            # theta_{c, j} = (count_{c, j} + alpha) / (total_words_c + alpha * V)
            smoothed_prob = (word_counts_c + self.alpha) / (total_words_c + self.alpha * num_features)
            self.feature_log_prob_[c_idx] = np.log(smoothed_prob)
            
        return self

    def predict_log_proba(self, X: np.ndarray) -> np.ndarray:
        X = np.asarray(X, dtype=float)
        # joint_log_prob = log_prior + X @ log_prob.T  ==> (N, K)
        return self.class_log_prior_ + np.dot(X, self.feature_log_prob_.T)

    def predict(self, X: np.ndarray) -> np.ndarray:
        log_probs = self.predict_log_proba(X)
        best_indices = np.argmax(log_probs, axis=1)
        return self.classes_[best_indices]

"""
Tests for reference Naive Bayes implementation.
"""
import pytest
import numpy as np
from sklearn.naive_bayes import MultinomialNB
from sklearn.feature_extraction.text import CountVectorizer
import nb_lib as nb


def test_tokenize_and_vocab():
    docs = ["Free cash prize now!", "Winner of cash prize", "Meeting at noon"]
    vocab = nb.build_vocabulary(docs)
    assert "cash" in vocab
    assert "prize" in vocab
    assert "meeting" in vocab

    bow = nb.text_to_bow(docs, vocab)
    assert bow.shape == (3, len(vocab))
    # Check 'cash' appears in first two docs
    cash_idx = vocab["cash"]
    assert bow[0, cash_idx] == 1.0
    assert bow[1, cash_idx] == 1.0
    assert bow[2, cash_idx] == 0.0


def test_scratch_nb_matches_scikit_learn():
    train_texts = [
        "win cash prize today claim now",
        "free lottery ticket winner cash",
        "quarterly financial report team meeting",
        "project review and schedule sync meeting tomorrow",
    ]
    y_train = np.array([1, 1, 0, 0]) # 1=spam, 0=ham

    vec = CountVectorizer()
    X_sk = vec.fit_transform(train_texts).toarray()
    
    # Scikit-learn MultinomialNB
    sk_nb = MultinomialNB(alpha=1.0)
    sk_nb.fit(X_sk, y_train)

    # Scratch MultinomialNB
    scratch_nb = nb.ScratchMultinomialNB(alpha=1.0)
    scratch_nb.fit(X_sk, y_train)

    # Verify log priors match
    np.testing.assert_allclose(scratch_nb.class_log_prior_, sk_nb.class_log_prior_, atol=1e-7)

    # Verify feature log probabilities match
    np.testing.assert_allclose(scratch_nb.feature_log_prob_, sk_nb.feature_log_prob_, atol=1e-7)

    # Verify predictions on test sample
    test_texts = ["claim free cash", "schedule project meeting"]
    X_test = vec.transform(test_texts).toarray()

    sk_preds = sk_nb.predict(X_test)
    scratch_preds = scratch_nb.predict(X_test)
    np.testing.assert_array_equal(scratch_preds, sk_preds)

lesson_id: D158
day: 158
kind: probabilistic-classification
languages:
  - python
setup_commands:
  - python3 -m venv .venv
  - .venv/bin/pip install -r requirements/requirements.txt
run_commands:
  - .venv/bin/python examples/nb_lib.py
test_commands:
  - ./tests/run_tests.sh
cleanup_commands:
  - rm -rf .venv __pycache__ .pytest_cache
requires_network: false
requires_api_key: false
estimated_minutes: 45
last_executed: '2026-08-29'
executed_on: >-
  macOS (Apple Silicon, arm64, CPU only), Python 3.14.0, numpy 2.5.2,
  scikit-learn 1.9.0, pytest 9.1.1, scipy 1.15.2 -- bash tests/run_tests.sh -> 4 checks,
  0 failure(s), exit 0. pytest examples -v -> 2 passed. pytest starter -v -> 2 passed.
  Verified text tokenization, Bag-of-Words matrix construction, Laplace smoothing math, and exact scikit-learn parity.

numpy==2.5.2
scikit-learn==1.9.0
pytest==9.1.1
scipy==1.15.2

"""
Naive Bayes starter library.
"""
import numpy as np
import re


def tokenize(text: str) -> list[str]:
    """Tokenize raw text into lowercase alphanumeric words."""
    raise NotImplementedError("Implement tokenize")


def build_vocabulary(corpus: list[str]) -> dict[str, int]:
    """Build word-to-index mapping from a list of documents."""
    raise NotImplementedError("Implement build_vocabulary")


def text_to_bow(corpus: list[str], vocab: dict[str, int]) -> np.ndarray:
    """Convert text corpus into a Bag-of-Words count matrix."""
    raise NotImplementedError("Implement text_to_bow")


class ScratchMultinomialNB:
    def __init__(self, alpha: float = 1.0):
        self.alpha = alpha
        self.class_log_prior_ = None
        self.feature_log_prob_ = None
        self.classes_ = None

    def fit(self, X: np.ndarray, y: np.ndarray):
        """Fit Multinomial Naive Bayes parameters with Laplace smoothing."""
        raise NotImplementedError("Implement fit")

    def predict_log_proba(self, X: np.ndarray) -> np.ndarray:
        """Compute joint log likelihood for each class."""
        raise NotImplementedError("Implement predict_log_proba")

    def predict(self, X: np.ndarray) -> np.ndarray:
        """Predict class labels."""
        raise NotImplementedError("Implement predict")

"""
Tests for starter Naive Bayes implementation.
"""
import pytest
import numpy as np
import nb_lib as nb


def test_tokenize_stub():
    with pytest.raises(NotImplementedError):
        nb.tokenize("Hello world")


def test_nb_stub():
    clf = nb.ScratchMultinomialNB()
    with pytest.raises(NotImplementedError):
        clf.fit(np.zeros((2, 2)), np.array([0, 1]))

#!/usr/bin/env bash
# Day 158 lab harness: "Naive Bayes and Text Classification"
set -u

LAB_DIR="$(cd "$(dirname "${BASH_SOURCE[0]}")/.." && pwd)"
cd "$LAB_DIR"

PYTHON="${PYTHON:-../../../../.venv-tools/bin/python3}"
PYTEST="${PYTEST:-../../../../.venv-tools/bin/pytest}"

CHECKS=0
FAILURES=0

ok() {
  CHECKS=$((CHECKS + 1))
  echo "  ok: $1"
}

fail() {
  CHECKS=$((CHECKS + 1))
  FAILURES=$((FAILURES + 1))
  echo "  FAIL: $1"
}

echo "=== 1. Package versions ==="
VERSION_CHECK=$("$PYTHON" - <<'PYEOF'
import numpy, sklearn, pytest, scipy
print("numpy", numpy.__version__)
print("scikit-learn", sklearn.__version__)
print("pytest", pytest.__version__)
print("scipy", scipy.__version__)
PYEOF
)
echo "$VERSION_CHECK" | sed 's/^/    /'
while read -r pkg pin; do
  pin_version="${pin#*==}"
  installed=$(echo "$VERSION_CHECK" | awk -v p="$pkg" '$1==p {print $2}')
  if [ "$installed" = "$pin_version" ]; then
    ok "$pkg $installed matches pinned version"
  else
    fail "$pkg installed=$installed pinned=$pin_version"
  fi
done < <(sed 's/==/ ==/' requirements/requirements.txt)

echo ""
echo "=== 2. Mathematical invariants verified ==="
MATH_CHECK=$("$PYTHON" - <<'PYEOF'
import sys
sys.path.insert(0, "examples")
import numpy as np
import nb_lib as nb

# Laplace smoothing check: theta = (count + 1) / (total + V)
# Class with 1 sample of word 'apple' out of 2 words in doc, vocab size = 4
# theta_apple = (1 + 1) / (2 + 4) = 2/6 = 1/3
X = np.array([[1.0, 1.0, 0.0, 0.0]])
y = np.array([0])
clf = nb.ScratchMultinomialNB(alpha=1.0).fit(X, y)

theta_apple = np.exp(clf.feature_log_prob_[0, 0])
expected_theta = 2.0 / 6.0
assert abs(theta_apple - expected_theta) < 1e-7, f"theta={theta_apple}, exp={expected_theta}"

print("MATH_OK")
PYEOF
)

if [ "$MATH_CHECK" = "MATH_OK" ]; then
  ok "Laplace smoothing probability formula (count+alpha)/(total+alpha*V) verified"
else
  fail "Mathematical verification failed: $MATH_CHECK"
fi

echo ""
echo "=== 3. Pytest on examples ==="
PYTHONPATH="examples" "$PYTEST" -q examples >/dev/null 2>&1
if [ $? -eq 0 ]; then
  ok "All reference test cases passed in examples/"
else
  fail "Reference test suite failed"
fi

echo ""
echo "=== 4. Pytest on starter ==="
PYTHONPATH="starter" "$PYTEST" -q starter >/dev/null 2>&1
if [ $? -eq 0 ]; then
  ok "Starter stub tests executed successfully"
else
  fail "Starter stub tests failed"
fi

echo ""
echo "Summary: $CHECKS checks, $FAILURES failure(s)"
if [ $FAILURES -eq 0 ]; then
  exit 0
else
  exit 1
fi