Naive Bayes Classification

Let $s_c(d_1) = p \cdot Q_c$ with the common prior $p$ and $Q_c = \prod_{w \in d_1} p_{wc}$. Then $s_c(d_2) = p \cdot Q_c^2$. For $Q_c \ge 0$, $Q_c \mapsto Q_c^2$ is strictly increasing, so $Q_c \le Q_{c'} \iff Q_c^2 \le Q_{c'}^2$, and the ordering of the classes (also the tie-breaking) is the same.

No. Two classes, $p_A = 0.9$, $p_B = 0.1$, one word $w$ with $p_{wA} = 0.2$, $p_{wB} = 0.5$. For $d_1 = (w)$: $0.9 \cdot 0.2 = 0.18 > 0.1 \cdot 0.5 = 0.05$, predicts $A$. For $d_2 = (w, w)$: $0.9 \cdot 0.04 = 0.036 < 0.1 \cdot 0.25 = 0.025$? No, $0.036 > 0.025$, so adjust: take $p_{wA} = 0.1$, $p_{wB} = 0.5$ and $p_A = 0.6$, $p_B = 0.4$. $d_1$: $0.06 < 0.2$ predicts $B$ … use instead $p_{wA} = 0.5$, $p_{wB} = 0.4$, $p_A = 0.4$, $p_B = 0.6$: $d_1$: $0.2$ vs $0.24$ gives $B$; $d_2$: $0.1$ vs $0.096$ gives $A$. The prediction changes, because the prior is not squared.

4.3: see the second example in Naive Bayes Classifier > Example: $p_X = 1/3$, $p_Y = 2/3$, $p_{1X} = 3/4$, $p_{2X} = 1/4$, $p_{1Y} = 1/4$, $p_{2Y} = 3/4$, so $w = (\ln 3, -\ln 3)$, $b = \ln 2$. 4.4: need $b = 0$ and $w_1 = -w_2 > 0$. Take equal class sizes ($p_X = p_Y$) and a point $(1, 0)$ labeled $X$ and a point $(0, 1)$ labeled $Y$: $p_{1X} = 1$, $p_{2X} = 0$, $p_{1Y} = 0$, $p_{2Y} = 1$ (smooth with the same $\varepsilon$ if zero probabilities are a concern, giving $w = (\ln r, -\ln r)$ with $r > 1$ and $b = 0$).

def smoothing(pwc, eps):
    for pw in pwc:
        for i in range(len(pw)):
            pw[i] += eps
        sum_pw = sum(pw)
        for i in range(len(pw)):
            pw[i] /= sum_pw

1. Non-zero: adding eps > 0 makes every entry strictly positive; dividing by a positive sum keeps it so.
2. Order: $p_a < p_b \Rightarrow p_a + \varepsilon < p_b + \varepsilon$, and dividing by the same positive constant preserves the strict inequality.
3. Distribution: after dividing by $\text{sum\_pw} = \sum_i (p_i + \varepsilon)$ the entries of each class sum to 1.

def predict(doc, pwc, pc):
    doc.append(1)
    for i in range(len(pwc)):
        pwc[i].append(pc[i])
        for j in range(len(pwc[i])):
            pwc[i][j] = math.log(pwc[i][j])
    predictions = pwc * doc
    return argmax(predictions)

Appending $1$ to the document and $p_c[i]$ to row $i$ puts the prior into the dot product. The logarithm turns $\prod_j p(w_j \mid c)^{n_j} \cdot p(c)$ into $\sum_j n_j \log p(w_j \mid c) + \log p(c)$, which is the dot product of the log row with the document vector. argmax returns the class with the highest log-probability.

1. 8 numbers are even, 8 odd: $p_A = p_B = 1/2$.
2. All documents have 4 words, so $n_A = n_B = 8 \cdot 4 = 32$.
3. Class $A$ (even): the last bit is always $0$; each of the other three positions has four $0$s and four $1$s. Count of word $0$: $8 + 4 + 4 + 4 = 20$; of word $1$: $0 + 4 + 4 + 4 = 12$.
4. Class $B$ (odd): the last bit is always $1$. Count of word $0$: $12$; of word $1$: $20$.
5. $p_{0|A} = 20/32 = 5/8$, $p_{1|A} = 3/8$, $p_{0|B} = 3/8$, $p_{1|B} = 5/8$.
6. For “0 0 0 1”: $\dfrac{\Pr(A \mid 0001)}{\Pr(B \mid 0001)} = \dfrac{p_A\, p_{0|A}^3\, p_{1|A}}{p_B\, p_{0|B}^3\, p_{1|B}} = \dfrac{(5/8)^3 (3/8)}{(3/8)^3 (5/8)} = \dfrac{5^2}{3^2} = \dfrac{25}{9} > 1$, so class $A$ is predicted. $\blacksquare$

def predict(doc, wordIds, pwc, pc):
    c_best, p_best = -1, -1
    for c in range(0, len(pc)):
        p = pc[c]
        for w in doc:
            wid = wordIds[w]
            p = p * pwc[c][wid]
        if p > p_best:
            c_best, p_best = c, p
    return c_best, p_best

For each class, $P(c) \cdot \prod_{w \in \text{doc}} P(w \mid c)$ is computed using the conditional-independence assumption; the best class is tracked and returned with its score. (Tasks 4.2 and 4.3 of this exam are about a web page that calls this function, see Web Applications.)