1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

import math
from collections import Counter
 
def demonstrate_zero_frequency_problem():
    """
    Show how a single unseen word breaks classification.
    """
    # Training data
    training_spam = ["free money", "free prize", "win cash", "claim prize"]
    training_ham = ["meeting today", "report ready", "project update"]
    
    # Count words per class (Maximum Likelihood Estimation)
    spam_word_counts = Counter()
    for doc in training_spam:
        spam_word_counts.update(doc.lower().split())
    
    ham_word_counts = Counter()
    for doc in training_ham:
        ham_word_counts.update(doc.lower().split())
    
    total_spam_words = sum(spam_word_counts.values())
    total_ham_words = sum(ham_word_counts.values())
    
    # MLE probability function (no smoothing)
    def mle_prob(word, class_counts, total):
        return class_counts[word] / total if class_counts[word] > 0 else 0.0
    
    print("VOCABULARY COVERAGE ANALYSIS")
    print("=" * 60)
    
    spam_vocab = set(spam_word_counts.keys())
    ham_vocab = set(ham_word_counts.keys())
    
    print(f"Spam vocabulary: {spam_vocab}")
    print(f"Ham vocabulary:  {ham_vocab}")
    print(f"Overlap:         {spam_vocab & ham_vocab}")
    print()
    
    # Test document with unseen word
    test_doc = "free cryptocurrency offer"
    test_words = test_doc.lower().split()
    
    print(f"Test document: '{test_doc}'")
    print("-" * 60)
    
    # Calculate log probabilities (without smoothing)
    log_prob_spam = 0
    log_prob_ham = 0
    
    print(f"{'Word':20s} {'P(w|spam)':>12s} {'P(w|ham)':>12s} {'log(spam)':>12s} {'log(ham)':>12s}")
    print("-" * 70)
    
    for word in test_words:
        p_spam = mle_prob(word, spam_word_counts, total_spam_words)
        p_ham = mle_prob(word, ham_word_counts, total_ham_words)
        
        # Handle log(0) case for display
        log_spam_str = f"{math.log(p_spam):.4f}" if p_spam > 0 else "-∞"
        log_ham_str = f"{math.log(p_ham):.4f}" if p_ham > 0 else "-∞"
        
        print(f"{word:20s} {p_spam:>12.4f} {p_ham:>12.4f} {log_spam_str:>12s} {log_ham_str:>12s}")
        
        if p_spam > 0:
            log_prob_spam += math.log(p_spam)
        else:
            log_prob_spam = float('-inf')
            
        if p_ham > 0:
            log_prob_ham += math.log(p_ham)
        else:
            log_prob_ham = float('-inf')
    
    print("-" * 70)
    print(f"{'TOTAL':20s} {'':>12s} {'':>12s} {log_prob_spam:>12s} {log_prob_ham:>12s}")
    
    print()
    if log_prob_spam == float('-inf') and log_prob_ham == float('-inf'):
        print("RESULT: Both classes have -∞ probability!")
        print("        Classification is UNDEFINED.")
    elif log_prob_spam == float('-inf'):
        print("RESULT: P(spam|doc) = 0, even though 'free' strongly suggests spam!")
    elif log_prob_ham == float('-inf'):
        print("RESULT: P(ham|doc) = 0")
        
    print("\n⚠️  A single unseen word ('cryptocurrency') broke the classifier!")
 
 
demonstrate_zero_frequency_problem()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

import math
from collections import Counter
from typing import Dict, List
 
class SmoothingDemo:
    """
    Demonstrates different smoothing strategies and their effects.
    """
    
    def __init__(self, vocabulary_size: int):
        self.vocab_size = vocabulary_size
        
    def mle_probability(self, count: int, total: int) -> float:
        """Maximum Likelihood Estimate (no smoothing)."""
        return count / total if total > 0 else 0.0
    
    def laplace_probability(self, count: int, total: int, alpha: float = 1.0) -> float:
        """Laplace/Lidstone smoothed probability."""
        return (count + alpha) / (total + alpha * self.vocab_size)
    
    def jeffreys_probability(self, count: int, total: int) -> float:
        """Jeffreys smoothing (alpha = 0.5)."""
        return self.laplace_probability(count, total, alpha=0.5)
    
    def compare_smoothing(self, word_counts: Dict[str, int], total: int):
        """Compare different smoothing methods."""
        print("SMOOTHING METHOD COMPARISON")
        print("=" * 80)
        print(f"Total word count: {total}")
        print(f"Vocabulary size: {self.vocab_size}")
        print()
        
        headers = ["Word", "Count", "MLE", "Laplace(α=1)", "Lidstone(α=0.5)", "Lidstone(α=0.1)"]
        print(f"{headers[0]:15s} {headers[1]:>8s} {headers[2]:>10s} {headers[3]:>14s} {headers[4]:>16s} {headers[5]:>16s}")
        print("-" * 85)
        
        for word, count in sorted(word_counts.items(), key=lambda x: -x[1]):
            mle = self.mle_probability(count, total)
            lap1 = self.laplace_probability(count, total, alpha=1.0)
            lid05 = self.laplace_probability(count, total, alpha=0.5)
            lid01 = self.laplace_probability(count, total, alpha=0.1)
            
            print(f"{word:15s} {count:>8d} {mle:>10.6f} {lap1:>14.6f} {lid05:>16.6f} {lid01:>16.6f}")
        
        # Add unseen word
        word = "(unseen)"
        count = 0
        mle = self.mle_probability(count, total)
        lap1 = self.laplace_probability(count, total, alpha=1.0)
        lid05 = self.laplace_probability(count, total, alpha=0.5)
        lid01 = self.laplace_probability(count, total, alpha=0.1)
        
        print("-" * 85)
        print(f"{word:15s} {count:>8d} {mle:>10.6f} {lap1:>14.6f} {lid05:>16.6f} {lid01:>16.6f}")
        
        # Verify normalization
        print()
        print("Normalization check (should be 1.0):")
        for alpha, name in [(1.0, "Laplace"), (0.5, "Lidstone(0.5)"), (0.1, "Lidstone(0.1)")]:
            total_prob = sum(
                self.laplace_probability(c, total, alpha)
                for c in word_counts.values()
            )
            # Add probability mass for unseen words
            n_unseen = self.vocab_size - len(word_counts)
            total_prob += n_unseen * self.laplace_probability(0, total, alpha)
            print(f"  {name}: {total_prob:.6f}")
 
 
def demonstrate_smoothing_effect():
    """Show how smoothing fixes the zero-frequency problem."""
    
    # Simulated word counts for spam class
    spam_counts = {
        'free': 50,
        'money': 30,
        'prize': 25,
        'winner': 20,
        'click': 15,
        'urgent': 10,
    }
    total_spam = sum(spam_counts.values())
    
    demo = SmoothingDemo(vocabulary_size=1000)  # Assume 1000-word vocabulary
    demo.compare_smoothing(spam_counts, total_spam)
    
    # Show classification with and without smoothing
    print()
    print("=" * 80)
    print("CLASSIFICATION WITH NEW WORD")
    print("=" * 80)
    
    test_words = ['free', 'cryptocurrency', 'money']
    
    print(f"\nTest document: {test_words}")
    print()
    
    # Without smoothing
    log_prob_mle = 0
    print("Without smoothing (MLE):")
    for word in test_words:
        count = spam_counts.get(word, 0)
        prob = demo.mle_probability(count, total_spam)
        if prob > 0:
            log_prob_mle += math.log(prob)
            print(f"  P({word}|spam) = {prob:.6f} -> log = {math.log(prob):.4f}")
        else:
            log_prob_mle = float('-inf')
            print(f"  P({word}|spam) = 0.000000 -> log = -∞ ❌")
            break
    print(f"  Total: {log_prob_mle}")
    
    # With Laplace smoothing
    print("\nWith Laplace smoothing (α=1):")
    log_prob_laplace = 0
    for word in test_words:
        count = spam_counts.get(word, 0)
        prob = demo.laplace_probability(count, total_spam, alpha=1.0)
        log_prob_laplace += math.log(prob)
        print(f"  P({word}|spam) = {prob:.6f} -> log = {math.log(prob):.4f}")
    print(f"  Total: {log_prob_laplace:.4f} ✓")
 
 
demonstrate_smoothing_effect()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

import numpy as np
from collections import Counter
from typing import List, Tuple
import math
 
def cross_validate_alpha(documents: List[str], 
                         labels: List[str],
                         alpha_values: List[float],
                         n_folds: int = 5) -> List[Tuple[float, float]]:
    """
    Cross-validation to select optimal smoothing parameter.
    
    Returns list of (alpha, accuracy) tuples.
    """
    from random import shuffle
    
    # Create folds
    indices = list(range(len(documents)))
    shuffle(indices)
    fold_size = len(indices) // n_folds
    folds = [indices[i * fold_size:(i + 1) * fold_size] for i in range(n_folds)]
    
    results = []
    
    for alpha in alpha_values:
        fold_accuracies = []
        
        for fold_idx in range(n_folds):
            # Split into train/test
            test_indices = set(folds[fold_idx])
            train_docs = [documents[i] for i in range(len(documents)) if i not in test_indices]
            train_labels = [labels[i] for i in range(len(labels)) if i not in test_indices]
            test_docs = [documents[i] for i in test_indices]
            test_labels = [labels[i] for i in test_indices]
            
            # Train with this alpha
            model = SimpleNBWithAlpha(alpha=alpha)
            model.fit(train_docs, train_labels)
            
            # Evaluate
            correct = sum(
                model.predict(doc) == label 
                for doc, label in zip(test_docs, test_labels)
            )
            accuracy = correct / len(test_docs)
            fold_accuracies.append(accuracy)
        
        mean_accuracy = np.mean(fold_accuracies)
        std_accuracy = np.std(fold_accuracies)
        results.append((alpha, mean_accuracy, std_accuracy))
        
    return results
 
 
class SimpleNBWithAlpha:
    """Minimal NB implementation for alpha testing."""
    
    def __init__(self, alpha: float = 1.0):
        self.alpha = alpha
        self.log_priors = {}
        self.log_probs = {}
        self.vocab = set()
        
    def fit(self, docs: List[str], labels: List[str]):
        tokenized = [doc.lower().split() for doc in docs]
        for tokens in tokenized:
            self.vocab.update(tokens)
        
        classes = set(labels)
        class_counts = Counter(labels)
        n_docs = len(docs)
        
        self.log_priors = {c: math.log(class_counts[c] / n_docs) for c in classes}
        
        word_counts = {c: Counter() for c in classes}
        for tokens, label in zip(tokenized, labels):
            word_counts[label].update(tokens)
        
        self.log_probs = {}
        for c in classes:
            total = sum(word_counts[c].values())
            self.log_probs[c] = {
                w: math.log((word_counts[c][w] + self.alpha) / 
                           (total + self.alpha * len(self.vocab)))
                for w in self.vocab
            }
            # Default for unseen
            self.log_probs[c]['__unseen__'] = math.log(
                self.alpha / (total + self.alpha * len(self.vocab))
            )
    
    def predict(self, doc: str) -> str:
        tokens = doc.lower().split()
        scores = {}
        for c in self.log_priors:
            score = self.log_priors[c]
            for token in tokens:
                if token in self.log_probs[c]:
                    score += self.log_probs[c][token]
                else:
                    score += self.log_probs[c]['__unseen__']
            scores[c] = score
        return max(scores, key=scores.get)
 
 
def demonstrate_alpha_effect():
    """Show how different alpha values affect classification."""
    
    # Synthetic data
    training_data = [
        ("great product love it amazing quality", "positive"),
        ("excellent service wonderful experience", "positive"),
        ("fantastic value highly recommend", "positive"),
        ("terrible product waste of money", "negative"),
        ("horrible service very disappointed", "negative"),
        ("awful quality never buying again", "negative"),
    ] * 5  # Repeat for more data
    
    # Add some noise
    training_data.extend([
        ("decent product okay value", "positive"),
        ("not great not terrible", "negative"),
    ])
    
    docs = [d for d, _ in training_data]
    labels = [l for _, l in training_data]
    
    # Test documents (including novel words)
    test_docs = [
        "great product recommend",              # Clear positive
        "terrible waste disappointed",          # Clear negative
        "good product blockchain technology",   # Positive with unseen word
        "bad service cryptocurrency scam",      # Negative with unseen words
    ]
    test_labels = ["positive", "negative", "positive", "negative"]
    
    print("ALPHA SELECTION EXPERIMENT")
    print("=" * 70)
    
    alpha_values = [0.01, 0.1, 0.5, 1.0, 2.0, 5.0]
    
    print(f"\n{'α':>8s}", end="")
    for doc in test_docs:
        print(f" | {doc[:20]+'..':22s}", end="")
    print(" | Accuracy")
    print("-" * 120)
    
    for alpha in alpha_values:
        model = SimpleNBWithAlpha(alpha=alpha)
        model.fit(docs, labels)
        
        predictions = [model.predict(doc) for doc in test_docs]
        accuracy = sum(p == t for p, t in zip(predictions, test_labels)) / len(test_labels)
        
        print(f"{alpha:>8.2f}", end="")
        for pred, true in zip(predictions, test_labels):
            mark = "✓" if pred == true else "✗"
            print(f" | {pred[:6]:6s} {mark:15s}", end="")
        print(f" | {accuracy:.2%}")
    
    print()
    print("Observations:")
    print("- Very small α (0.01) may undersmooth: unseen words get too little probability")
    print("- Very large α (5.0) may oversmooth: reduces discrimination between classes")
    print("- Optimal α often in range [0.1, 1.0] for typical datasets")
 
 
demonstrate_alpha_effect()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

import math
from collections import Counter
from typing import Dict, List
 
class GoodTuringSmoothing:
    """
    Good-Turing smoothing for probability estimation.
    
    Adjusts counts based on the frequency of frequencies.
    """
    
    def __init__(self, word_counts: Dict[str, int], vocab_size: int):
        """
        Args:
            word_counts: Dictionary mapping words to their counts
            vocab_size: Total vocabulary size (including unseen)
        """
        self.word_counts = word_counts
        self.vocab_size = vocab_size
        self.total_count = sum(word_counts.values())
        
        # Compute frequency of frequencies (N_r = count of words with count r)
        count_of_counts = Counter(word_counts.values())
        self.N_r = dict(count_of_counts)
        
        # Number of unseen words (words with count 0)
        n_seen = len(word_counts)
        self.N_r[0] = vocab_size - n_seen
        
    def adjusted_count(self, c: int) -> float:
        """
        Compute Good-Turing adjusted count for a word with count c.
        
        c* = (c + 1) * N_{c+1} / N_c
        """
        if c == 0:
            # Probability mass for unseen words
            if 1 in self.N_r and self.N_r[0] > 0:
                return self.N_r[1] / self.N_r[0]
            return 1 / (self.vocab_size + 1)  # Fallback
        
        if c + 1 not in self.N_r:
            # No words with count c+1; use simple smoothing
            return c  # Or use linear interpolation
            
        return (c + 1) * self.N_r[c + 1] / self.N_r.get(c, 1)
    
    def probability(self, word: str) -> float:
        """Compute Good-Turing smoothed probability."""
        c = self.word_counts.get(word, 0)
        c_star = self.adjusted_count(c)
        
        # Normalize
        return c_star / self.total_count
 
 
class AbsoluteDiscounting:
    """
    Absolute discounting smoothing.
    
    Subtracts a fixed discount from all positive counts and
    redistributes to unseen words.
    """
    
    def __init__(self, word_counts: Dict[str, int], 
                 vocab_size: int,
                 discount: float = 0.75):
        self.word_counts = word_counts
        self.vocab_size = vocab_size
        self.discount = discount
        self.total_count = sum(word_counts.values())
        
        # Compute backoff probability mass
        n_positive = len([c for c in word_counts.values() if c > 0])
        self.backoff_mass = self.discount * n_positive / self.total_count
        
        # Number of unseen words
        self.n_unseen = vocab_size - len(word_counts)
        
    def probability(self, word: str) -> float:
        """Compute absolute discounting probability."""
        c = self.word_counts.get(word, 0)
        
        if c > 0:
            # Discount positive counts
            return max(c - self.discount, 0) / self.total_count
        else:
            # Distribute backoff mass uniformly to unseen
            if self.n_unseen > 0:
                return self.backoff_mass / self.n_unseen
            return 0
 
 
def compare_smoothing_methods():
    """Compare different smoothing approaches."""
    
    # Sample word counts (simulated from a class)
    word_counts = {
        'the': 100,
        'is': 50,
        'great': 30,
        'product': 25,
        'excellent': 10,
        'fantastic': 5,
        'wonderful': 3,
        'superb': 2,
        'magnificent': 1,
        'outstanding': 1,
    }
    
    vocab_size = 1000  # Assume 1000-word vocabulary
    total = sum(word_counts.values())
    
    # Initialize smoothers
    gt = GoodTuringSmoothing(word_counts, vocab_size)
    ad = AbsoluteDiscounting(word_counts, vocab_size, discount=0.75)
    
    print("SMOOTHING METHOD COMPARISON")
    print("=" * 80)
    print(f"Total observed words: {total}")
    print(f"Vocabulary size: {vocab_size}")
    print(f"Seen words: {len(word_counts)}, Unseen: {vocab_size - len(word_counts)}")
    print()
    
    # Compare for specific words
    test_words = ['the', 'product', 'superb', 'magnificent', '(unseen)']
    
    print(f"{'Word':15s} {'Count':>8s} {'MLE':>10s} {'Laplace':>10s} {'G-T':>10s} {'Abs Disc':>10s}")
    print("-" * 70)
    
    for word in test_words:
        c = word_counts.get(word, 0)
        mle = c / total if c > 0 else 0
        laplace = (c + 1) / (total + vocab_size)
        gt_prob = gt.probability(word if word != '(unseen)' else 'xyz_unseen')
        ad_prob = ad.probability(word if word != '(unseen)' else 'xyz_unseen')
        
        print(f"{word:15s} {c:>8d} {mle:>10.6f} {laplace:>10.6f} {gt_prob:>10.6f} {ad_prob:>10.6f}")
    
    print()
    print("Key observations:")
    print("- MLE gives 0 to unseen words (problematic)")
    print("- Laplace gives uniform mass to all unseen words")
    print("- Good-Turing bases unseen estimate on words seen once")
    print("- Absolute discounting is less aggressive than Laplace")
 
 
compare_smoothing_methods()