Concept · intermediate
Naive Bayes
Classify by multiplying per-feature probabilities learned from counts.
Naive Bayes classifies by asking which label makes the observed features most probable. It is “naive” because it assumes the features are independent once you know the label. That’s rarely true, but it lets each feature be counted on its own, so training is just counting. Early spam filters worked this way, and it’s still a fast, sturdy baseline for categorical data.
The dataset
data.csv holds 200 synthetic emails labelled spam or ham, with three
yes/no features: has_link, mentions_money, and known_sender. The split
column marks 150 rows as train and 50 as test. We generated it once with
make_data.py (fixed seed 20261102) and committed the result. Each email is
spam with probability 0.4. Spam then has a link 80% of the time, mentions
money 70%, and comes from a known sender 10%; for ham, those are 30%, 10%,
and 70%. The training rows hold 55 spam and 95 ham.
The math
For a test email with feature values , the score of label is
is the number of training emails with label , the number of those whose feature is , and the number of distinct values feature takes (here 2). In words: start with how common the label is, then for each feature, ask how often that label had this value. The higher score wins; an exact tie would go to the alphabetically first label.
A worked example
The first test email has a link, doesn’t mention money, and comes from an unknown sender. It is spam. From the training counts:
| spam (55) | ham (95) | |
|---|---|---|
| 55/150 = 0.3667 | 95/150 = 0.6333 | |
| has a link | (43+1)/57 = 0.7719 | (18+1)/97 = 0.1959 |
| no money | (16+1)/57 = 0.2982 | (82+1)/97 = 0.8557 |
| unknown sender | (52+1)/57 = 0.9298 | (29+1)/97 = 0.3093 |
| score (sum of logs) | −2.5448 | −3.4164 |
Spam wins, correctly. Ham starts ahead because it’s more common, but a link is 3.9 times likelier under spam and an unknown sender 3.0 times, and that outweighs it.
Why logs? Products of probabilities shrink fast. In Python, multiplying 400
probabilities of 0.1 underflows to exactly 0.0, while the sum of their logs,
about −921, is fine. Log keeps order, so the higher score still wins.
Why add one? A zero count would make a probability zero, and one zero wipes out the whole product. No count here is zero, but one is close: only 3 of 55 training spam came from a known sender. Smoothing raises that probability from 0.0545 to 0.0702. That flips emails with all three features set from ham (−4.4734 against −4.5019 for spam) to spam (−4.2731 against −4.3927). Two of the three such test emails are spam, so smoothing gains one correct answer.
Reading the results
The model gets 42 of 50 test emails right, an accuracy of 0.84; calling everything ham would score 0.68. Three yes/no features allow only eight kinds of email, and the model calls one spam if the sender is unknown and it has a link or mentions money, or if all three features are set.
Six of the eight mistakes are ham called spam: five from unknown senders with a link or money, one with all three features set. The other two are spam that looked like ham. Training isn’t to blame: the generator’s true probabilities make the same call for all eight kinds. These features just can’t tell those emails apart.
What to watch for across languages
None of these implementations uses a naive Bayes library, and none of the
twenty-nine languages ships one. They use only general tools: counting (such as Python’s
Counter or SQL’s count(*)), logarithms, and comparing label names.
Watch how each keys its counts by feature, value, and label. Python, Ruby,
Julia, Rust, C++, Haskell, OCaml, Elixir, Common Lisp, and Tcl use a tuple, array, or list as the key (Haskell, with no
map type in base, keeps its counts in association lists), Perl and PHP nest
hashes or arrays three deep, as in $count{$label}{$f}{$value}, Go and Swift use a
small struct and Java a record, awk, JavaScript, Lua, and Ada join the three into one string, and COBOL
indexes a three-dimensional table by position. R, APL, Fortran,
C, Octave, Prolog, BASIC, and Pascal store no value counts; they recount matching training rows each time
they score. PostgreSQL turns the
three feature columns into rows first, so one GROUP BY counts them all the
same way. And watch the tie rule: each language reaches “alphabetically
first” in its own way.
Data preview
| has_link | mentions_money | known_sender | label | split |
|---|---|---|---|---|
| no | yes | no | spam | train |
| no | no | yes | ham | train |
| no | no | yes | ham | train |
| no | no | yes | ham | train |
| no | yes | no | spam | train |
| yes | no | no | spam | train |
| no | no | no | ham | train |
| yes | no | no | ham | train |
First 8 of 200 rows · Download data.csv
Expected results
Every implementation must print these, to within a relative tolerance of 10⁻⁴.
train_count | 150 |
test_count | 50 |
correct | 42 |
accuracy | 0.840000 |
Implementations
"""Categorical naive Bayes with add-one (Laplace) smoothing, standard library only.
Learns P(label) and P(feature value | label) by counting training rows, then
labels each test row with the label that has the highest log-probability.
"""
import csv
import math
import sys
from collections import Counter
FEATURES = ("has_link", "mentions_money", "known_sender")
LABEL = "label"
def main():
with open(sys.argv[1], newline="") as f:
rows = list(csv.DictReader(f))
train = [row for row in rows if row["split"] == "train"]
test = [row for row in rows if row["split"] == "test"]
label_counts = Counter(row[LABEL] for row in train)
# value_counts[(feature, value, label)] = number of training rows
value_counts = Counter((f, row[f], row[LABEL]) for row in train for f in FEATURES)
distinct_values = {f: len({row[f] for row in train}) for f in FEATURES}
def log_score(row, label):
# Logs turn the product of probabilities into a sum, avoiding underflow.
score = math.log(label_counts[label] / len(train))
for f in FEATURES:
# Add-one smoothing: an unseen value never gets probability zero.
count = value_counts[(f, row[f], label)] + 1
score += math.log(count / (label_counts[label] + distinct_values[f]))
return score
def classify(row):
# Labels are tried in alphabetical order, so an exact tie goes to the first.
return max(sorted(label_counts), key=lambda label: log_score(row, label))
correct = sum(classify(row) == row[LABEL] for row in test)
print(f"train_count {len(train)}")
print(f"test_count {len(test)}")
print(f"correct {correct}")
print(f"accuracy {correct / len(test):.6f}")
if __name__ == "__main__":
main()Python makes the counting almost invisible. csv.DictReader gives each row
as a dictionary keyed by column name, and one Counter keyed by
(feature, value, label) tuples holds every count the model needs. Looking
up a key that was never counted returns 0, so the add-one smoothing works
for unseen combinations without any special case.
The tie rule comes nearly free. max returns the first maximum it meets, so
feeding it sorted(label_counts) sends an exact tie to the alphabetically
first label.
The standard library has no naive Bayes classifier, so here, unlike on some pages, there was no built-in to skip.
-- Categorical naive Bayes with add-one (Laplace) smoothing, using only
-- Ada's standard library.
--
-- Learns P(label) and P(feature value | label) by counting training rows,
-- then labels each test row with the label that has the highest
-- log-probability. Ada has no naive Bayes routine, so there is no built-in
-- to avoid.
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Long_Float_Text_IO; use Ada.Long_Float_Text_IO;
with Ada.Command_Line;
with Ada.Characters.Handling; use Ada.Characters.Handling;
with Ada.Strings.Fixed; use Ada.Strings.Fixed;
with Ada.Numerics.Long_Elementary_Functions;
use Ada.Numerics.Long_Elementary_Functions;
with Ada.Containers.Indefinite_Vectors;
with Ada.Containers.Indefinite_Ordered_Maps;
with Ada.Containers.Indefinite_Ordered_Sets;
procedure Main is
-- "Indefinite" containers hold Strings of any length.
package Line_Vectors is new Ada.Containers.Indefinite_Vectors
(Positive, String);
package Count_Maps is new Ada.Containers.Indefinite_Ordered_Maps
(String, Natural);
package String_Sets is new Ada.Containers.Indefinite_Ordered_Sets (String);
-- The feature columns, as an enumeration. Feature'Image (Has_Link) is
-- "HAS_LINK", so the header is matched in lower case.
type Feature is (Has_Link, Mentions_Money, Known_Sender);
function Name (F : Feature) return String is (To_Lower (Feature'Image (F)));
-- The text of field number Col (counting from 1) in a CSV line.
function Field (Line : String; Col : Positive) return String is
Start : Positive := Line'First;
begin
for I in 1 .. Col - 1 loop
Start := Index (Line (Start .. Line'Last), ",") + 1;
end loop;
declare
Stop : constant Natural := Index (Line (Start .. Line'Last), ",");
begin
return (if Stop = 0 then Line (Start .. Line'Last)
else Line (Start .. Stop - 1));
end;
end Field;
File : File_Type;
Rows : Line_Vectors.Vector;
Feature_Col : array (Feature) of Natural := [others => 0];
Label_Col, Split_Col : Natural := 0;
-- Counts keyed by one string: "label" or "feature=value|label".
Counts : Count_Maps.Map;
Labels : String_Sets.Set; -- an ordered set iterates alphabetically
Values : array (Feature) of String_Sets.Set;
Train_Count, Test_Count, Correct : Natural := 0;
function Key (F : Feature; Row, Label : String) return String is
(Name (F) & "=" & Field (Row, Feature_Col (F)) & "|" & Label);
-- A missing key counts as zero.
function Count_Of (K : String) return Natural is
(if Counts.Contains (K) then Counts (K) else 0);
procedure Add_One (K : String) is
begin
Counts.Include (K, Count_Of (K) + 1); -- Include inserts or replaces
end Add_One;
function Log_Score (Row, Label : String) return Long_Float is
Label_Count : constant Natural := Count_Of (Label);
-- Logs turn the product of probabilities into a sum, avoiding
-- underflow.
Score : Long_Float :=
Log (Long_Float (Label_Count) / Long_Float (Train_Count));
begin
for F in Feature loop
-- Add-one smoothing: an unseen value never gets probability zero.
Score := Score + Log
(Long_Float (Count_Of (Key (F, Row, Label)) + 1)
/ Long_Float (Label_Count + Natural (Values (F).Length)));
end loop;
return Score;
end Log_Score;
-- Labels come out of the set in order, and only a strictly higher score
-- replaces the best, so an exact tie goes to the first.
function Classify (Row : String) return String is
Best : String_Sets.Cursor := Labels.First; -- a cursor marks a label
begin
for Position in Labels.Iterate loop
if Log_Score (Row, String_Sets.Element (Position))
> Log_Score (Row, String_Sets.Element (Best))
then
Best := Position;
end if;
end loop;
return String_Sets.Element (Best);
end Classify;
begin
Open (File, In_File, Ada.Command_Line.Argument (1));
declare
Header : constant String := Get_Line (File);
begin
for C in 1 .. Ada.Strings.Fixed.Count (Header, ",") + 1 loop
for F in Feature loop
if Field (Header, C) = Name (F) then
Feature_Col (F) := C;
end if;
end loop;
if Field (Header, C) = "label" then
Label_Col := C;
elsif Field (Header, C) = "split" then
Split_Col := C;
end if;
end loop;
end;
if Label_Col = 0 or else Split_Col = 0
or else (for some C of Feature_Col => C = 0)
then
raise Constraint_Error with "missing column";
end if;
while not End_Of_File (File) loop
declare
Line : constant String := Get_Line (File);
begin
if Line /= "" then
Rows.Append (Line);
end if;
end;
end loop;
Close (File);
-- Training: count each label, and each feature value within a label.
for Row of Rows loop
if Field (Row, Split_Col) = "train" then
Train_Count := Train_Count + 1;
Add_One (Field (Row, Label_Col));
Labels.Include (Field (Row, Label_Col)); -- ignored if present
for F in Feature loop
Add_One (Key (F, Row, Field (Row, Label_Col)));
Values (F).Include (Field (Row, Feature_Col (F)));
end loop;
end if;
end loop;
if Train_Count = 0 then
raise Constraint_Error with "no training rows";
end if;
for Row of Rows loop
if Field (Row, Split_Col) = "test" then
Test_Count := Test_Count + 1;
if Classify (Row) = Field (Row, Label_Col) then
Correct := Correct + 1;
end if;
end if;
end loop;
Put_Line ("train_count" & Natural'Image (Train_Count));
Put_Line ("test_count" & Natural'Image (Test_Count));
Put_Line ("correct" & Natural'Image (Correct));
Put ("accuracy ");
Put (Long_Float (Correct) / Long_Float (Test_Count),
Fore => 1, Aft => 6, Exp => 0); -- six decimals, no E
New_Line;
end Main;We count training rows into an Indefinite_Ordered_Maps keyed by one
string, such as has_link=yes|spam, and a missing key counts as zero. The
features are an enumeration type, but Feature'Image (Has_Link) gives
"HAS_LINK", so To_Lower turns it back into the column name. Labels and
each feature’s distinct values go into Indefinite_Ordered_Sets, which
ignore repeats with Include and iterate in sorted order.
Ada’s standard library has no naive Bayes, so scoring is written out: add logs of the smoothed probabilities, and keep a label only when it scores strictly higher. Because the set iterates alphabetically, an exact tie goes to the first label.
⍝ Categorical naive Bayes with add-one (Laplace) smoothing, from scratch in
⍝ GNU APL. Each test email gets the label with the highest log-probability.
⍝ APL reads right to left, with no operator precedence: 2×3+4 is 2×(3+4).
⍝ ⍝ starts a comment; ← assigns; ⍵ is a function's right argument.
∇NAME SAY N
⍝ Print "name value" for a whole number. ⍕ formats a number as text.
⎕←NAME,' ',⍕N
∇
∇NAME SAY6 X;T
⍝ Print "name value" with six decimal places.
T←0 6⍕|X ⍝ |X is the size of X; 0 6⍕ gives 6 decimals
T←(∨\T≠' ')/T ⍝ drop the leading blank ⍕ adds
T←((T[1]='.')/'0'),T ⍝ ⍕ writes .94 for 0.94, so put the 0 back
⎕←NAME,' ',((X<0)/'-'),T ⍝ sign as -, since APL's own minus is ¯
∇
⍝ Read the file. ⎕ARG is the command line; ↑¯1↑ takes its last item, the
⍝ data path. ⎕FIO[26] reads the whole file as one string.
TEXT←⎕FIO[26]↑¯1↑⎕ARG
LINES←(TEXT≠⎕UCS 10)⊂TEXT ⍝ ⊂ splits at the 0s of the mask: one item per line
⍝ Split each (¨) line at commas; ⊃ stacks them into a table.
ROWS←⊃{(⍵≠',')⊂⍵}¨LINES
⍝ A column by header name (⍳), minus the header (1↓).
COLUMN←{1↓ROWS[;ROWS[1;]⍳⊂⍵]}
F←⍉⊃COLUMN¨'has_link' 'mentions_money' 'known_sender' ⍝ one row per email
L←COLUMN 'label'
⍝ 1 for each training row (≡ matches whole strings).
TRAIN←(COLUMN 'split')≡¨⊂'train'
TF←TRAIN⌿F ⋄ TL←TRAIN/L ⍝ ⌿ keeps the training rows of a table
QF←(~TRAIN)⌿F ⋄ QL←(~TRAIN)/L ⍝ ~ is not: the test rows
LABELS←∪TL
⍝ Alphabetical: ⊃ pads the names into a table, ⍋ sorts its rows.
LABELS←LABELS[⍋⊃LABELS]
⍝ m, per feature: ⊂[1] takes the columns; ≢∪ counts the unique values.
DISTINCT←{≢∪⍵}¨⊂[1]TF
∇S←ROW SCORE C;M;NC;COUNTS
M←TL≡¨⊂C ⍝ 1 for the training rows labelled C
NC←+/M ⍝ how many there are
⍝ Per feature: rows with label C and the same value.
COUNTS←+⌿(M⌿TF)≡¨(NC,≢ROW)⍴ROW
⍝ ⍟ is the natural log. Summing logs multiplies the probabilities without
⍝ underflow, and the +1 keeps an unseen value from scoring zero.
S←(⍟NC÷≢TL)++/⍟(COUNTS+1)÷NC+DISTINCT
∇
⍝ ⌈/ is the max; ⍳ finds its first position, so a tie goes to the first label.
CLASSIFY←{S←(⊂⍵)SCORE¨LABELS ⋄ ⊃LABELS[S⍳⌈/S]}
PRED←CLASSIFY¨⊂[2]QF ⍝ ⊂[2] makes one item per test row
CORRECT←+/PRED≡¨QL
'train_count' SAY ≢TL
'test_count' SAY ≢QL
'correct' SAY CORRECT
'accuracy' SAY6 CORRECT÷≢QL
)OFFThe table of text values is nested: each cell holds a string like yes, so
≡¨ compares whole strings item by item. Scoring one label is three steps:
keep the training rows with that label (⌿), count the rows that match the
test email in each feature, and sum the logs (⍟) of the smoothed
fractions. ≢∪ counts each feature’s distinct values for the smoothing.
For the tie rule, ⊃ pads the label names into a character table and ⍋
sorts its rows alphabetically, so ⍳ finding the first maximum score picks
the alphabetically first label. APL has no probability built-ins, so nothing
is avoided.
# Categorical naive Bayes with add-one (Laplace) smoothing, in POSIX awk.
#
# Learns P(label) and P(feature value | label) by counting training rows, then
# labels each test row with the label that has the highest log-probability.
# awk's associative arrays do the counting; keys like "has_link,yes,spam" are
# built by joining strings, since POSIX awk has no nested arrays.
BEGIN {
FS = ","
nf = split("has_link,mentions_money,known_sender", feature, ",")
label_name = "label"
}
# The header line: find each column by name.
NR == 1 {
for (i = 1; i <= NF; i++) {
for (f = 1; f <= nf; f++)
if ($i == feature[f]) fcol[f] = i
if ($i == label_name) c_lab = i
if ($i == "split") c_split = i
}
for (f = 1; f <= nf; f++)
if (!fcol[f]) missing = missing " " feature[f]
if (!c_lab) missing = missing " " label_name
if (!c_split) missing = missing " split"
if (missing != "") {
print "missing column(s):" missing > "/dev/stderr"
failed = 1
exit 1
}
next
}
# A training row: count its label and each (feature, value, label) triple.
$c_split == "train" {
n_train++
label = $c_lab
if (!(label in label_count)) add_label(label)
label_count[label]++
for (f = 1; f <= nf; f++) {
value = $fcol[f]
value_count[f "," value "," label]++
# Count the distinct values of each feature (m_j in the formula).
if (!((f "," value) in seen)) { seen[f "," value] = 1; distinct[f]++ }
}
next
}
# A test row: keep it for END, after training has seen every row.
$c_split == "test" {
n_test++
test_label[n_test] = $c_lab
for (f = 1; f <= nf; f++)
test_value[n_test "," f] = $fcol[f]
}
# Insert a new label into labels[1..n_labels], kept in alphabetical order
# (POSIX awk has no sort, and the order decides ties).
function add_label(name, i) {
for (i = n_labels; i > 0 && labels[i] > name; i--)
labels[i + 1] = labels[i]
labels[i + 1] = name
n_labels++
}
# log P(label) + sum over features of log P(value | label), add-one smoothed.
# Logs turn the product of probabilities into a sum, avoiding underflow.
function log_score(t, label, f, score) {
score = log(label_count[label] / n_train)
for (f = 1; f <= nf; f++)
score += log((value_count[f "," test_value[t "," f] "," label] + 1) / \
(label_count[label] + distinct[f]))
return score
}
END {
if (failed) exit 1
for (t = 1; t <= n_test; t++) {
# Labels are tried alphabetically and only a strictly higher score
# replaces the best, so an exact tie goes to the first label.
best = labels[1]
best_score = log_score(t, best)
for (i = 2; i <= n_labels; i++) {
s = log_score(t, labels[i])
if (s > best_score) { best = labels[i]; best_score = s }
}
if (best == test_label[t]) correct++
}
printf "train_count %d\n", n_train
printf "test_count %d\n", n_test
printf "correct %d\n", correct
printf "accuracy %.6f\n", correct / n_test
}awk is a natural fit for counting categories. Associative arrays start every
entry at zero, so value_count[f "," value "," label]++ counts a feature,
value, and label as the rows stream past. POSIX awk has no nested arrays, so
the three parts are joined into one string key. log is built in.
The tie rule takes more work. POSIX awk has no sort, and for (k in array)
visits keys in an unspecified order: the same four keys came back in
different orders from mawk and the macOS awk. So add_label inserts each new
label into a sorted array as it’s first seen. Local variables are faked as
extra function parameters, like i in add_label(name, i). The program
runs unchanged on mawk, which the tests use, and on macOS awk.
10 REM Categorical naive Bayes with add-one (Laplace) smoothing, in
20 REM classic BASIC.
30 REM
40 REM Learns P(label) and P(feature value | label) by counting training
50 REM rows, then labels each test row with the label that has the highest
60 REM log-probability. There are no dictionaries, so nothing is stored:
70 REM each count is found again by scanning the training rows.
80 REM
90 REM run.sh passes the data path in the DATA environment variable.
100 NFE = 3
110 DIM FE$(3), FC(3), DV(3), FL$(20)
120 DIM V$(1000, 3), LB$(1000), SP$(1000), T(1000), LS$(20)
130 FE$(1) = "has_link" : FE$(2) = "mentions_money" : FE$(3) = "known_sender"
140 GOSUB 1000 : REM read rows; T(1) to T(NT) are the training row numbers
150 GOSUB 2000 : REM list the labels LS$(1) to LS$(NL) and count values DV(f)
160 NTE = 0 : CO = 0
170 FOR R = 1 TO N
180 IF SP$(R) <> "test" THEN 220
190 NTE = NTE + 1
200 GOSUB 3000 : REM classify row R into BL$
210 IF BL$ = LB$(R) THEN CO = CO + 1
220 NEXT R
230 PRINT "train_count"; NT
240 PRINT "test_count"; NTE
250 PRINT "correct"; CO
260 PRINT "accuracy ";
270 PRINT USING "#.######"; CO / NTE
280 SYSTEM : REM without SYSTEM, bwbasic waits at its prompt
1000 REM Read every row: V$(r, f) for each feature, LB$(r), and SP$(r).
1010 F$ = ENVIRON$("DATA")
1020 OPEN "I", #1, F$
1030 LINE INPUT #1, L$
1040 GOSUB 4000 : REM find which field of the header holds each column
1050 FOR C = 1 TO NF
1060 FOR G = 1 TO NFE
1070 IF FL$(C) = FE$(G) THEN FC(G) = C
1080 NEXT G
1090 IF FL$(C) = "label" THEN LCOL = C
1100 IF FL$(C) = "split" THEN SCOL = C
1110 NEXT C
1120 N = 0 : NT = 0
1130 IF EOF(1) THEN 1220
1140 LINE INPUT #1, L$
1150 GOSUB 4000
1160 N = N + 1 : LB$(N) = FL$(LCOL) : SP$(N) = FL$(SCOL)
1170 FOR G = 1 TO NFE
1180 V$(N, G) = FL$(FC(G))
1190 NEXT G
1200 IF SP$(N) = "train" THEN NT = NT + 1 : T(NT) = N
1210 GOTO 1130
1220 CLOSE #1
1230 RETURN
2000 REM A label or value is new if no earlier training row has it.
2010 REM This FOR runs its body once even when the range is empty (FOR E = 1
2020 REM TO 0), so the searches over earlier rows use WHILE, which doesn't.
2030 NL = 0
2040 FOR I = 1 TO NT
2050 S = 0 : E = 1
2060 WHILE E < I
2070 IF LB$(T(E)) = LB$(T(I)) THEN S = 1
2080 E = E + 1
2090 WEND
2100 IF S = 0 THEN NL = NL + 1 : LS$(NL) = LB$(T(I))
2110 FOR G = 1 TO NFE
2120 S = 0 : E = 1
2130 WHILE E < I
2140 IF V$(T(E), G) = V$(T(I), G) THEN S = 1
2150 E = E + 1
2160 WEND
2170 IF S = 0 THEN DV(G) = DV(G) + 1
2180 NEXT G
2190 NEXT I
2200 REM Insertion sort puts the labels in alphabetical order; <= compares
2210 REM text by character code.
2220 I = 2
2230 WHILE I <= NL
2240 Y$ = LS$(I) : J = I - 1
2250 IF J < 1 THEN 2280
2260 IF LS$(J) <= Y$ THEN 2280
2270 LS$(J + 1) = LS$(J) : J = J - 1 : GOTO 2250
2280 LS$(J + 1) = Y$
2290 I = I + 1
2300 WEND
2310 RETURN
3000 REM Classify row R. Labels are tried in alphabetical order, and only
3010 REM a strictly higher score replaces the best, so a tie goes to the first.
3020 FOR K = 1 TO NL
3030 GOSUB 5000 : REM score label LS$(K) for row R into SC
3040 IF K = 1 THEN BL$ = LS$(K) : BS = SC
3050 IF SC > BS THEN BL$ = LS$(K) : BS = SC
3060 NEXT K
3070 RETURN
4000 REM Split L$ at its commas into FL$(1) to FL$(NF).
4010 NF = 0 : P = 1
4020 Q = INSTR(P, L$, ",")
4030 NF = NF + 1
4040 IF Q = 0 THEN FL$(NF) = MID$(L$, P) : RETURN
4050 FL$(NF) = MID$(L$, P, Q - P) : P = Q + 1
4060 GOTO 4020
5000 REM Log-score of label LS$(K) for row R. Logs turn the product of
5010 REM probabilities into a sum, avoiding underflow.
5020 LCN = 0
5030 FOR I = 1 TO NT
5040 IF LB$(T(I)) = LS$(K) THEN LCN = LCN + 1
5050 NEXT I
5060 SC = LOG(LCN / NT)
5070 FOR G = 1 TO NFE
5080 CN = 0
5090 FOR I = 1 TO NT
5100 IF LB$(T(I)) = LS$(K) AND V$(T(I), G) = V$(R, G) THEN CN = CN + 1
5110 NEXT I
5120 REM Add-one smoothing: an unseen value never gets probability zero.
5130 SC = SC + LOG((CN + 1) / (LCN + DV(G)))
5140 NEXT G
5150 RETURNEach email’s three feature values go in a two-dimensional text array,
V$(row, feature), and the training rows are listed by number in T. We
store no counts: subroutine 5000 rescans the training rows, comparing text
with =, each time a score needs one, then adds the logs with LOG.
One surprise shaped the code: in this interpreter, FOR E = 1 TO 0 still
runs its body once, so the searches over earlier rows and the insertion sort
of labels use WHILE, which skips an empty range. <= compares text by
character code, so "Spam" would sort before "ham"; our labels are
lowercase, and an exact tie goes to the first in that order. BASIC has no naive Bayes function.
/* Categorical naive Bayes with add-one (Laplace) smoothing, using only the C
* standard library.
*
* Learns P(label) and P(feature value | label) by counting training rows, then
* labels each test row with the label that has the highest log-probability. */
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N_FEATURES 3
#define MAX_LINE 1024
#define MAX_TEXT 32
#define MAX_LABELS 16
static const char *FEATURES[N_FEATURES] = {"has_link", "mentions_money", "known_sender"};
/* One email. C strings are fixed-size character arrays here, copied in. */
typedef struct {
char values[N_FEATURES][MAX_TEXT];
char label[MAX_TEXT];
char split[MAX_TEXT];
} Row;
/* Return the 0-based position of name in a header line, or -1. strtok
* replaces each comma with '\0' as it goes, so it works on a copy. */
static int column_index(const char *header, const char *name) {
char copy[MAX_LINE];
strcpy(copy, header);
int index = 0;
for (char *field = strtok(copy, ",\r\n"); field; field = strtok(NULL, ",\r\n")) {
if (strcmp(field, name) == 0) return index;
index++;
}
return -1;
}
/* Copy text into a fixed-size field, cutting it short rather than overflowing. */
static void copy_text(char dest[MAX_TEXT], const char *text) {
snprintf(dest, MAX_TEXT, "%s", text);
}
/* Read every row. The array doubles in size whenever it fills, and the count
* comes back through *count. */
static Row *read_rows(const char *path, size_t *count) {
FILE *file = fopen(path, "r");
if (!file) { perror(path); exit(1); }
char line[MAX_LINE];
if (!fgets(line, sizeof line, file)) { fprintf(stderr, "empty file\n"); exit(1); }
int feature_col[N_FEATURES];
for (int f = 0; f < N_FEATURES; f++) feature_col[f] = column_index(line, FEATURES[f]);
int label_col = column_index(line, "label"), split_col = column_index(line, "split");
for (int f = 0; f < N_FEATURES; f++)
if (feature_col[f] < 0) { fprintf(stderr, "no column %s\n", FEATURES[f]); exit(1); }
if (label_col < 0 || split_col < 0) { fprintf(stderr, "no label or split\n"); exit(1); }
size_t n = 0, capacity = 64;
Row *rows = malloc(capacity * sizeof *rows);
while (fgets(line, sizeof line, file)) {
Row row = {0};
int index = 0;
for (char *field = strtok(line, ",\r\n"); field; field = strtok(NULL, ",\r\n")) {
for (int f = 0; f < N_FEATURES; f++)
if (index == feature_col[f]) copy_text(row.values[f], field);
if (index == label_col) copy_text(row.label, field);
if (index == split_col) copy_text(row.split, field);
index++;
}
if (index == 0) continue; /* a blank line */
if (n == capacity) {
capacity *= 2;
rows = realloc(rows, capacity * sizeof *rows);
}
rows[n++] = row;
}
fclose(file);
*count = n;
return rows;
}
/* Training rows and the model's counts. The labels are kept sorted. */
static const Row **train;
static size_t n_train;
static const char *labels[MAX_LABELS];
static int n_labels;
static int distinct_values[N_FEATURES];
/* Training rows with this label and, if feature >= 0, this value of it. */
static int count_rows(const char *label, int feature, const char *value) {
int count = 0;
for (size_t i = 0; i < n_train; i++)
if (strcmp(train[i]->label, label) == 0 &&
(feature < 0 || strcmp(train[i]->values[feature], value) == 0))
count++;
return count;
}
/* qsort calls this with pointers to two array elements, each a char pointer. */
static int compare_strings(const void *a, const void *b) {
return strcmp(*(const char *const *)a, *(const char *const *)b);
}
static double log_score(const Row *row, const char *label) {
int label_count = count_rows(label, -1, NULL);
/* Logs turn the product of probabilities into a sum, avoiding underflow. */
double score = log((double)label_count / n_train);
for (int f = 0; f < N_FEATURES; f++) {
/* Add-one smoothing: an unseen value never gets probability zero. */
int count = count_rows(label, f, row->values[f]) + 1;
score += log((double)count / (label_count + distinct_values[f]));
}
return score;
}
/* Labels are tried in alphabetical order, and only a strictly higher score
* replaces the best, so an exact tie goes to the first. */
static const char *classify(const Row *row) {
const char *best = labels[0];
double best_score = log_score(row, best);
for (int l = 1; l < n_labels; l++) {
double score = log_score(row, labels[l]);
if (score > best_score) { best = labels[l]; best_score = score; }
}
return best;
}
int main(int argc, char **argv) {
if (argc < 2) { fprintf(stderr, "usage: %s data.csv\n", argv[0]); return 1; }
size_t n;
Row *rows = read_rows(argv[1], &n);
/* train points into rows, so the training set copies no data. */
train = malloc(n * sizeof *train);
for (size_t i = 0; i < n; i++)
if (strcmp(rows[i].split, "train") == 0) train[n_train++] = &rows[i];
if (n_train == 0) { fprintf(stderr, "no training rows\n"); return 1; }
/* A label or value is new if no earlier training row has it. */
for (size_t i = 0; i < n_train; i++) {
int seen = 0;
for (size_t e = 0; e < i && !seen; e++) seen = strcmp(train[e]->label, train[i]->label) == 0;
if (!seen && n_labels < MAX_LABELS) labels[n_labels++] = train[i]->label;
for (int f = 0; f < N_FEATURES; f++) {
seen = 0;
for (size_t e = 0; e < i && !seen; e++)
seen = strcmp(train[e]->values[f], train[i]->values[f]) == 0;
if (!seen) distinct_values[f]++;
}
}
qsort(labels, n_labels, sizeof *labels, compare_strings);
int test_count = 0, correct = 0;
for (size_t i = 0; i < n; i++) {
if (strcmp(rows[i].split, "test") != 0) continue;
test_count++;
if (strcmp(classify(&rows[i]), rows[i].label) == 0) correct++;
}
printf("train_count %zu\n", n_train);
printf("test_count %d\n", test_count);
printf("correct %d\n", correct);
printf("accuracy %.6f\n", (double)correct / test_count);
free(train);
free(rows);
return 0;
}Each email is a struct holding its three feature values, label, and split
as fixed-size character arrays, and the training set is an array of pointers
into the rows, so it copies no data. C has no dictionary, so we store no
counts at all: count_rows recounts matching training rows, comparing text
with strcmp, each time a score needs one.
The distinct labels go through qsort with strcmp, which orders by
character code, so "Spam" would sort before "ham"; all our labels are
lowercase. Only a strictly higher score replaces the best, so an exact tie
goes to the alphabetically first label. C has no naive Bayes function to
avoid.
// Categorical naive Bayes with add-one (Laplace) smoothing, using only the C++
// standard library.
//
// Learns P(label) and P(feature value | label) by counting training rows, then
// labels each test row with the label that has the highest log-probability.
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <fstream>
#include <map>
#include <print>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <tuple>
#include <vector>
const std::vector<std::string> FEATURES = {"has_link", "mentions_money", "known_sender"};
// One email: its feature values in FEATURES order, its label, and its split.
struct Row {
std::vector<std::string> values;
std::string label;
std::string split;
};
// Split one line at every comma.
std::vector<std::string> split(const std::string& line) {
std::vector<std::string> fields;
std::stringstream stream(line);
std::string field;
while (std::getline(stream, field, ',')) {
fields.push_back(field);
}
return fields;
}
// Every row of the CSV file, with columns found by name and kept as text.
std::vector<Row> read_rows(const std::string& path) {
std::ifstream file(path);
std::string line;
std::getline(file, line);
std::vector<std::string> header = split(line);
auto column = [&header](const std::string& name) {
auto found = std::find(header.begin(), header.end(), name);
if (found == header.end()) {
throw std::runtime_error("no column " + name);
}
return static_cast<std::size_t>(found - header.begin());
};
std::vector<std::size_t> feature_cols;
for (const std::string& feature : FEATURES) {
feature_cols.push_back(column(feature));
}
std::size_t label_col = column("label");
std::size_t split_col = column("split");
std::vector<Row> rows;
while (std::getline(file, line)) {
if (line.empty()) {
continue;
}
std::vector<std::string> fields = split(line);
Row row;
for (std::size_t col : feature_cols) {
row.values.push_back(fields.at(col));
}
row.label = fields.at(label_col);
row.split = fields.at(split_col);
rows.push_back(row);
}
return rows;
}
int main(int argc, char* argv[]) {
if (argc != 2) {
std::println(stderr, "usage: program data.csv");
return 1;
}
std::vector<Row> rows = read_rows(argv[1]);
std::vector<Row> train;
std::vector<Row> test;
for (const Row& row : rows) {
if (row.split == "train") train.push_back(row);
if (row.split == "test") test.push_back(row);
}
if (train.empty() || test.empty()) {
std::println(stderr, "need training and test rows");
return 1;
}
// A std::map keeps its keys sorted, and a std::tuple compares field by
// field, so a (feature, value, label) tuple works as a key.
using Key = std::tuple<std::string, std::string, std::string>;
std::map<std::string, int> label_counts;
std::map<Key, int> value_counts;
std::vector<std::set<std::string>> distinct_values(FEATURES.size());
for (const Row& row : train) {
// operator[] inserts a zero for a missing key, so ++ starts counting at 1.
label_counts[row.label]++;
for (std::size_t f = 0; f < FEATURES.size(); f++) {
value_counts[{FEATURES[f], row.values[f], row.label}]++;
distinct_values[f].insert(row.values[f]);
}
}
auto log_score = [&](const Row& row, const std::string& label) {
int label_count = label_counts.at(label);
// Logs turn the product of probabilities into a sum, avoiding underflow.
double score = std::log(static_cast<double>(label_count) / train.size());
for (std::size_t f = 0; f < FEATURES.size(); f++) {
// find, unlike operator[], leaves the map alone when the key is missing.
auto found = value_counts.find({FEATURES[f], row.values[f], label});
int seen = found == value_counts.end() ? 0 : found->second;
// Add-one smoothing: an unseen value never gets probability zero.
score += std::log(static_cast<double>(seen + 1) /
(label_count + static_cast<int>(distinct_values[f].size())));
}
return score;
};
// A std::map visits its keys in sorted order, and only a strictly higher
// score replaces the best, so an exact tie goes to the first label.
auto classify = [&](const Row& row) {
std::string best;
double best_score = 0.0;
for (const auto& [label, count] : label_counts) {
double score = log_score(row, label);
if (best.empty() || score > best_score) {
best = label;
best_score = score;
}
}
return best;
};
int correct = 0;
for (const Row& row : test) {
if (classify(row) == row.label) correct++;
}
std::println("train_count {}", train.size());
std::println("test_count {}", test.size());
std::println("correct {}", correct);
std::println("accuracy {:.6f}", static_cast<double>(correct) / test.size());
}Where C recounts training rows for every score, we count once. A std::map
keyed by a std::tuple of feature, value, and label holds the value counts,
since tuples compare field by field, and a second map counts labels.
operator[] inserts a zero for a missing key, so ++ starts counting at 1;
scoring uses find instead, which leaves the map alone.
A std::map keeps its keys sorted, so looping over the label counts tries
labels alphabetically, and only a strictly higher score replaces the best,
so an exact tie goes to the first. The order is by character code, so
"Spam" would sort before "ham". C++ has no naive Bayes function to avoid.
*> Categorical naive Bayes with add-one (Laplace) smoothing, in
*> COBOL.
*>
*> Learns P(label) and P(feature value | label) by counting
*> training rows, then labels each test row with the label that
*> has the highest log-probability.
IDENTIFICATION DIVISION.
PROGRAM-ID. NAIVE-BAYES.
ENVIRONMENT DIVISION.
INPUT-OUTPUT SECTION.
FILE-CONTROL.
SELECT DATA-FILE ASSIGN TO DYNAMIC WS-FILE-NAME
ORGANIZATION IS LINE SEQUENTIAL.
DATA DIVISION.
FILE SECTION.
FD DATA-FILE.
01 DATA-LINE PIC X(200).
WORKING-STORAGE SECTION.
01 WS-FILE-NAME PIC X(256).
01 WS-EOF PIC X VALUE "N".
88 END-OF-FILE VALUE "Y".
*> One CSV line split into fields, and where the columns are.
01 WS-FIELDS.
05 WS-FIELD PIC X(40) OCCURS 20 TIMES.
01 WS-FIELD-COUNT PIC 99.
01 WS-POINTER PIC 999.
01 WS-LINE-LENGTH PIC 999.
01 WS-FEATURE-COUNT PIC 9 VALUE 3.
01 WS-FEATURE-NAMES.
05 FILLER PIC X(40) VALUE "has_link".
05 FILLER PIC X(40) VALUE "mentions_money".
05 FILLER PIC X(40) VALUE "known_sender".
01 FILLER REDEFINES WS-FEATURE-NAMES.
05 WS-FEATURE-NAME PIC X(40) OCCURS 3 TIMES.
01 WS-FEATURE-COLUMNS.
05 WS-FEATURE-COLUMN PIC 99 OCCURS 3 TIMES VALUE 0.
01 WS-LABEL-COLUMN PIC 99 VALUE 0.
01 WS-SPLIT-COLUMN PIC 99 VALUE 0.
*> The distinct labels seen in training, with their row counts.
01 WS-LABEL-COUNT PIC 99 VALUE 0.
01 WS-LABELS.
05 WS-LABEL OCCURS 20 TIMES.
10 WS-LABEL-NAME PIC X(40).
10 WS-LABEL-ROWS PIC 9(4) VALUE 0.
*> For each feature: its distinct training values (m_j of them),
*> and how many training rows of each label have each value.
01 WS-FEATURES.
05 WS-FEATURE OCCURS 3 TIMES.
10 WS-VALUE-COUNT PIC 99 VALUE 0.
10 WS-VALUE OCCURS 20 TIMES.
15 WS-VALUE-NAME PIC X(40).
15 WS-VALUE-ROWS PIC 9(4) OCCURS 20 TIMES
VALUE 0.
*> Test rows: the field values, kept as text.
01 WS-TEST-COUNT PIC 9(4) VALUE 0.
01 WS-TESTS.
05 WS-TEST OCCURS 5000 TIMES.
10 WS-TEST-VALUE PIC X(40) OCCURS 3 TIMES.
10 WS-TEST-LABEL PIC X(40).
01 I PIC 9(4).
01 F PIC 9.
01 V PIC 99.
01 L PIC 99.
01 WS-FOUND PIC 99.
01 WS-TRAIN-COUNT PIC 9(4) VALUE 0.
01 WS-MATCHES PIC 9(4).
01 WS-SCORE PIC S9(6)V9(12).
01 WS-BEST-SCORE PIC S9(6)V9(12).
01 WS-BEST PIC 99.
01 WS-CORRECT PIC 9(4) VALUE 0.
01 WS-ACCURACY PIC S9(3)V9(12).
01 WS-ACCURACY-OUT PIC -(3)9.9(6).
01 WS-COUNT-OUT PIC Z(8)9.
PROCEDURE DIVISION.
MAIN.
ACCEPT WS-FILE-NAME FROM ARGUMENT-VALUE
OPEN INPUT DATA-FILE
READ DATA-FILE
AT END SET END-OF-FILE TO TRUE
END-READ
PERFORM SPLIT-LINE
PERFORM VARYING I FROM 1 BY 1 UNTIL I > WS-FIELD-COUNT
PERFORM VARYING F FROM 1 BY 1
UNTIL F > WS-FEATURE-COUNT
IF WS-FIELD(I) = WS-FEATURE-NAME(F)
MOVE I TO WS-FEATURE-COLUMN(F)
END-IF
END-PERFORM
IF WS-FIELD(I) = "label"
MOVE I TO WS-LABEL-COLUMN
END-IF
IF WS-FIELD(I) = "split"
MOVE I TO WS-SPLIT-COLUMN
END-IF
END-PERFORM
IF WS-FEATURE-COLUMN(1) = 0 OR WS-FEATURE-COLUMN(2) = 0
OR WS-FEATURE-COLUMN(3) = 0
OR WS-LABEL-COLUMN = 0 OR WS-SPLIT-COLUMN = 0
DISPLAY "missing column" UPON SYSERR
MOVE 1 TO RETURN-CODE
STOP RUN
END-IF
PERFORM UNTIL END-OF-FILE
READ DATA-FILE
AT END SET END-OF-FILE TO TRUE
NOT AT END PERFORM ADD-ROW
END-READ
END-PERFORM
CLOSE DATA-FILE
PERFORM VARYING I FROM 1 BY 1 UNTIL I > WS-TEST-COUNT
PERFORM CLASSIFY
IF WS-LABEL-NAME(WS-BEST) = WS-TEST-LABEL(I)
ADD 1 TO WS-CORRECT
END-IF
END-PERFORM
MOVE WS-TRAIN-COUNT TO WS-COUNT-OUT
DISPLAY "train_count " FUNCTION TRIM(WS-COUNT-OUT)
MOVE WS-TEST-COUNT TO WS-COUNT-OUT
DISPLAY "test_count " FUNCTION TRIM(WS-COUNT-OUT)
MOVE WS-CORRECT TO WS-COUNT-OUT
DISPLAY "correct " FUNCTION TRIM(WS-COUNT-OUT)
COMPUTE WS-ACCURACY ROUNDED = WS-CORRECT / WS-TEST-COUNT
COMPUTE WS-ACCURACY-OUT ROUNDED = WS-ACCURACY
DISPLAY "accuracy " FUNCTION TRIM(WS-ACCURACY-OUT)
STOP RUN.
*> Split DATA-LINE on commas into WS-FIELD(1), WS-FIELD(2), ...
SPLIT-LINE.
MOVE SPACES TO WS-FIELDS
MOVE 0 TO WS-FIELD-COUNT
MOVE 1 TO WS-POINTER
MOVE FUNCTION LENGTH(FUNCTION TRIM(DATA-LINE TRAILING))
TO WS-LINE-LENGTH
PERFORM UNTIL WS-POINTER > WS-LINE-LENGTH
ADD 1 TO WS-FIELD-COUNT
UNSTRING DATA-LINE DELIMITED BY ","
INTO WS-FIELD(WS-FIELD-COUNT)
WITH POINTER WS-POINTER
END-UNSTRING
END-PERFORM.
*> Count a training row, or keep a test row for later.
ADD-ROW.
PERFORM SPLIT-LINE
IF WS-FIELD(WS-SPLIT-COLUMN) = "train"
PERFORM COUNT-TRAINING-ROW
ELSE
ADD 1 TO WS-TEST-COUNT
PERFORM VARYING F FROM 1 BY 1
UNTIL F > WS-FEATURE-COUNT
MOVE WS-FIELD(WS-FEATURE-COLUMN(F))
TO WS-TEST-VALUE(WS-TEST-COUNT, F)
END-PERFORM
MOVE WS-FIELD(WS-LABEL-COLUMN)
TO WS-TEST-LABEL(WS-TEST-COUNT)
END-IF.
*> Add one training row to the label and value counts, adding
*> any label or value not seen before.
COUNT-TRAINING-ROW.
ADD 1 TO WS-TRAIN-COUNT
MOVE 0 TO L
PERFORM VARYING WS-FOUND FROM 1 BY 1
UNTIL WS-FOUND > WS-LABEL-COUNT
IF WS-LABEL-NAME(WS-FOUND) = WS-FIELD(WS-LABEL-COLUMN)
MOVE WS-FOUND TO L
END-IF
END-PERFORM
IF L = 0
ADD 1 TO WS-LABEL-COUNT
MOVE WS-LABEL-COUNT TO L
MOVE WS-FIELD(WS-LABEL-COLUMN) TO WS-LABEL-NAME(L)
END-IF
ADD 1 TO WS-LABEL-ROWS(L)
PERFORM VARYING F FROM 1 BY 1 UNTIL F > WS-FEATURE-COUNT
MOVE 0 TO V
PERFORM VARYING WS-FOUND FROM 1 BY 1
UNTIL WS-FOUND > WS-VALUE-COUNT(F)
IF WS-VALUE-NAME(F, WS-FOUND)
= WS-FIELD(WS-FEATURE-COLUMN(F))
MOVE WS-FOUND TO V
END-IF
END-PERFORM
IF V = 0
ADD 1 TO WS-VALUE-COUNT(F)
MOVE WS-VALUE-COUNT(F) TO V
MOVE WS-FIELD(WS-FEATURE-COLUMN(F))
TO WS-VALUE-NAME(F, V)
END-IF
ADD 1 TO WS-VALUE-ROWS(F, V, L)
END-PERFORM.
*> Pick the label with the highest log score for test row I,
*> into WS-BEST.
CLASSIFY.
MOVE 0 TO WS-BEST
PERFORM VARYING L FROM 1 BY 1 UNTIL L > WS-LABEL-COUNT
PERFORM LOG-SCORE
*> An exact tie goes to the alphabetically first label.
IF WS-BEST = 0
OR WS-SCORE > WS-BEST-SCORE
OR (WS-SCORE = WS-BEST-SCORE
AND WS-LABEL-NAME(L) < WS-LABEL-NAME(WS-BEST))
MOVE L TO WS-BEST
MOVE WS-SCORE TO WS-BEST-SCORE
END-IF
END-PERFORM.
*> log P(label L) + sum of log P(value | label L), into WS-SCORE.
*> Logs turn the product of probabilities into a sum, avoiding
*> underflow. Each log of a ratio is taken as a difference of
*> logs of whole numbers, so no quotient is truncated first.
LOG-SCORE.
COMPUTE WS-SCORE ROUNDED =
FUNCTION LOG(WS-LABEL-ROWS(L))
- FUNCTION LOG(WS-TRAIN-COUNT)
PERFORM VARYING F FROM 1 BY 1 UNTIL F > WS-FEATURE-COUNT
*> A value never seen in training counts as zero rows.
MOVE 0 TO WS-MATCHES
PERFORM VARYING V FROM 1 BY 1
UNTIL V > WS-VALUE-COUNT(F)
IF WS-VALUE-NAME(F, V) = WS-TEST-VALUE(I, F)
MOVE WS-VALUE-ROWS(F, V, L) TO WS-MATCHES
END-IF
END-PERFORM
*> Add-one smoothing: an unseen value never gets
*> probability zero.
COMPUTE WS-SCORE ROUNDED = WS-SCORE
+ FUNCTION LOG(WS-MATCHES + 1)
- FUNCTION LOG(WS-LABEL-ROWS(L) + WS-VALUE-COUNT(F))
END-PERFORM.COBOL has no dictionaries, only fixed tables indexed by position. Nested
OCCURS clauses give a feature-by-value-by-label grid of counts,
WS-VALUE-ROWS(F, V, L), but finding the right V or L means a linear
scan of the names seen so far, adding a new entry the first time one
appears. Since the data is all text, there is no number parsing at all.
Each log score is built from logs of whole counts, `FUNCTION LOG(WS-MATCHES
-
-
- FUNCTION LOG(…)
, rather than the log of a quotient. Storing 17/57 in a four-decimal field first would shift its log by about 0.00015. GnuCOBOL's inlineFUNCTION LOG(A / B)` gave the precise value when we tried it, but whole counts avoid the question. The program runs to 246 lines, about five times the Python.
- FUNCTION LOG(…)
-
;;;; Categorical naive Bayes with add-one (Laplace) smoothing, using only
;;;; standard Common Lisp.
;;;;
;;;; Learns P(label) and P(feature value | label) by counting training rows,
;;;; then labels each test row with the label that has the highest
;;;; log-probability. Counts live in hash tables.
;; Not *features*: Common Lisp already uses that name, and SBCL locks it.
(defparameter *feature-columns* '("has_link" "mentions_money" "known_sender"))
;; No numbers are read from this file, but every program here reads doubles.
;; eval-when makes the setting apply while the compiler reads this file, too,
;; not only once the program runs.
(eval-when (:compile-toplevel :load-toplevel :execute)
(setf *read-default-float-format* 'double-float))
(defun split-on-comma (line)
"The fields of LINE, split at every comma."
(loop for start = 0 then (1+ end)
for end = (position #\, line :start start)
collect (subseq line start end)
while end))
(defun read-rows (path)
"Every data row of the CSV file at PATH, as a hash table from column name
to value. Hash tables compare keys with eql by default, which treats two
equal strings as different keys; :test 'equal compares their characters."
(with-open-file (in path)
(let ((header (split-on-comma (read-line in))))
(loop for line = (read-line in nil)
while line
unless (string= line "")
collect (let ((row (make-hash-table :test 'equal)))
(loop for name in header
for value in (split-on-comma line)
do (setf (gethash name row) value))
row)))))
(defun column (name row)
(or (gethash name row) (error "no column ~a" name)))
(defun divide (a b)
"A divided by B as a double. (/ 55 150) is the exact fraction 11/30, and
the log of a fraction is a single float, accurate to about 7 digits."
(/ (float a 1d0) b))
(defun rows-where (name value rows)
(remove-if-not (lambda (row) (string= (column name row) value)) rows))
(let* ((rows (read-rows (second sb-ext:*posix-argv*)))
(train (rows-where "split" "train" rows))
(test (rows-where "split" "test" rows))
(label-counts (make-hash-table :test 'equal))
;; Keyed by a list (feature value label), such as
;; ("has_link" "yes" "spam"); equal compares lists element by element.
(value-counts (make-hash-table :test 'equal))
(distinct-values (make-hash-table :test 'equal)))
;; gethash returns nil for a missing key; the 0 makes it start from zero.
(dolist (row train)
(let ((label (column "label" row)))
(incf (gethash label label-counts 0))
(dolist (f *feature-columns*)
(incf (gethash (list f (column f row) label) value-counts 0)))))
(dolist (f *feature-columns*)
(setf (gethash f distinct-values)
(length (remove-duplicates (mapcar (lambda (row) (column f row)) train)
:test #'string=))))
(labels ((log-score (row label)
;; Logs turn the product of probabilities into a sum, avoiding
;; underflow. Add-one smoothing means an unseen value never gets
;; probability zero.
(let ((n-label (gethash label label-counts)))
(+ (log (divide n-label (length train)))
(loop for f in *feature-columns*
for n-value = (gethash (list f (column f row) label) value-counts 0)
sum (log (divide (1+ n-value)
(+ n-label (gethash f distinct-values))))))))
(classify (row)
;; Labels are tried in alphabetical order, and only a strictly
;; higher score replaces the best, so a tie goes to the first.
(let ((names (sort (loop for label being the hash-keys of label-counts
collect label)
#'string<)))
(loop with best = (first names)
with best-score = (log-score row best)
for label in (rest names)
for score = (log-score row label)
when (> score best-score)
do (setf best label best-score score)
finally (return best)))))
(let ((correct (count-if (lambda (row) (string= (classify row) (column "label" row)))
test)))
(format t "train_count ~d~%" (length train))
(format t "test_count ~d~%" (length test))
(format t "correct ~d~%" correct)
(format t "accuracy ~,6f~%" (divide correct (length test))))))Training is counting into hash tables. The value counts are keyed by a list
such as ("has_link" "yes" "spam"), which needs :test 'equal: the default
test, eql, treats two equal lists or strings as different keys, so every
lookup would miss. (gethash key table 0) gives 0 for a key never seen.
Watch the division. (/ 55 150) is the exact fraction 11/30, and its log
comes out a single float, so divide converts the counts to doubles first.
For the tie rule, we sort the labels with string< and keep the first
unless a later label scores strictly higher. Common Lisp has no naive Bayes
or probability functions to skip.
# Categorical naive Bayes with add-one (Laplace) smoothing, using only
# Elixir's standard library.
#
# Learns P(label) and P(feature value | label) by counting training rows,
# then labels each test row with the label that has the highest
# log-probability. Enum.frequencies does the counting: it turns a list into
# a map from each distinct item to how often it appears.
defmodule NaiveBayes do
@features ["has_link", "mentions_money", "known_sender"]
# Every data line as a map from column name to value, such as
# %{"label" => "spam", ...}.
def read_rows(path) do
[header | rows] = path |> File.read!() |> String.split("\n", trim: true)
names = String.split(header, ",")
Enum.map(rows, fn row -> Map.new(Enum.zip(names, String.split(row, ","))) end)
end
def train(rows) do
# label -> rows
label_counts = Enum.frequencies_by(rows, & &1["label"])
# {feature, value, label} -> rows. Tuples compare by value, so they work
# as map keys.
value_counts =
Enum.frequencies(for row <- rows, f <- @features, do: {f, row[f], row["label"]})
# feature -> how many distinct values it takes in training
distinct =
Map.new(@features, fn f -> {f, rows |> Enum.uniq_by(& &1[f]) |> length()} end)
%{n: length(rows), labels: label_counts, values: value_counts, distinct: distinct}
end
# Logs turn the product of probabilities into a sum, avoiding underflow.
# Add-one smoothing means an unseen value never gets probability zero.
def log_score(model, row, label) do
n_label = model.labels[label]
Enum.reduce(@features, :math.log(n_label / model.n), fn f, score ->
# Map.get with a default of 0 covers a combination never seen.
count = Map.get(model.values, {f, row[f], label}, 0) + 1
score + :math.log(count / (n_label + model.distinct[f]))
end)
end
# Labels are tried in alphabetical order, and Enum.max_by keeps the first
# of equal scores, so an exact tie goes to the first.
def classify(model, row) do
model.labels
|> Map.keys()
|> Enum.sort()
|> Enum.max_by(&log_score(model, row, &1))
end
end
[path] = System.argv()
rows = NaiveBayes.read_rows(path)
train = Enum.filter(rows, &(&1["split"] == "train"))
test = Enum.filter(rows, &(&1["split"] == "test"))
model = NaiveBayes.train(train)
correct = Enum.count(test, &(NaiveBayes.classify(model, &1) == &1["label"]))
IO.puts("train_count #{length(train)}")
IO.puts("test_count #{length(test)}")
IO.puts("correct #{correct}")
IO.puts("accuracy #{:erlang.float_to_binary(correct / length(test), decimals: 6)}")We read each row into a map from column name to value, then count the
training rows with Enum.frequencies, which turns a list into a map from
each distinct item to how often it appears. The value counts use a
{feature, value, label} tuple as the key, and Map.get with a default of
0 covers a combination never seen.
Neither Elixir nor Erlang ships a naive Bayes classifier, and Hex packages
aren’t installed. Scoring adds logarithms from Erlang’s :math.log, with
add-one smoothing. We sort the labels and pick with Enum.max_by, which
keeps the first of equal scores, so an exact tie goes to the alphabetically
first label.
! Categorical naive Bayes with add-one (Laplace) smoothing, standard Fortran.
!
! Learns P(label) and P(feature value | label) by counting training rows, then
! labels each test row with the label that has the highest log-probability.
program naive_bayes
implicit none
integer, parameter :: dp = kind(1.0d0) ! double precision
integer, parameter :: n_features = 3
character(len=*), parameter :: features(n_features) = &
[character(len=16) :: "has_link", "mentions_money", "known_sender"]
! One email: a value for each feature, and its label.
type :: email
character(len=16) :: values(n_features)
character(len=16) :: label
end type email
type(email), allocatable :: train(:), test(:)
character(len=16), allocatable :: labels(:)
integer :: distinct_values(n_features), f, i, correct
call read_emails(train, test)
labels = sorted_labels()
! The number of distinct values of each feature: count each value the
! first time it appears. train%values(f) is that feature in every row.
do f = 1, n_features
distinct_values(f) = 0
do i = 1, size(train)
if (.not. any(train(:i - 1)%values(f) == train(i)%values(f))) &
distinct_values(f) = distinct_values(f) + 1
end do
end do
correct = 0
do i = 1, size(test)
if (classify(test(i)) == test(i)%label) correct = correct + 1
end do
print "(a, 1x, i0)", "train_count", size(train)
print "(a, 1x, i0)", "test_count", size(test)
print "(a, 1x, i0)", "correct", correct
call say("accuracy", real(correct, dp) / size(test))
contains
real(dp) function log_score(row, label)
type(email), intent(in) :: row
character(len=*), intent(in) :: label
integer :: label_count, value_count, f
! Logs turn the product of probabilities into a sum, avoiding underflow.
label_count = count(train%label == label)
log_score = log(real(label_count, dp) / size(train))
do f = 1, n_features
! Add-one smoothing: an unseen value never gets probability zero.
value_count = count(train%label == label .and. &
train%values(f) == row%values(f)) + 1
log_score = log_score + &
log(real(value_count, dp) / (label_count + distinct_values(f)))
end do
end function log_score
function classify(row) result(label)
type(email), intent(in) :: row
character(len=16) :: label
real(dp) :: scores(size(labels))
integer :: j
do j = 1, size(labels)
scores(j) = log_score(row, labels(j))
end do
! maxloc returns the first of equal maximums, and the labels are sorted,
! so an exact tie goes to the alphabetically first label.
label = labels(maxloc(scores, dim=1))
end function classify
! The distinct training labels in alphabetical order (an insertion sort;
! < compares strings alphabetically).
function sorted_labels() result(labels)
character(len=16), allocatable :: labels(:)
character(len=16) :: key
integer :: i, j
allocate(labels(0))
do i = 1, size(train)
if (.not. any(labels == train(i)%label)) labels = [labels, train(i)%label]
end do
do i = 2, size(labels)
key = labels(i)
j = i - 1
do while (j >= 1)
if (labels(j) <= key) exit
labels(j + 1) = labels(j)
j = j - 1
end do
labels(j + 1) = key
end do
end function sorted_labels
subroutine read_emails(train, test)
type(email), allocatable, intent(out) :: train(:), test(:)
character(len=256) :: path, line
integer :: unit, status, cols(n_features), label_col, split_col, f
type(email) :: e
call get_command_argument(1, path)
open(newunit=unit, file=path, status="old", action="read")
read(unit, "(a)") line
do f = 1, n_features
cols(f) = field_index(line, trim(features(f)))
end do
label_col = field_index(line, "label")
split_col = field_index(line, "split")
allocate(train(0), test(0))
do
read(unit, "(a)", iostat=status) line
if (status /= 0) exit
do f = 1, n_features
e%values(f) = field(line, cols(f))
end do
e%label = field(line, label_col)
if (field(line, split_col) == "train") then
train = [train, e] ! grows the array by one
else
test = [test, e]
end if
end do
close(unit)
end subroutine read_emails
! The position of a name in a comma-separated header line.
integer function field_index(header, name)
character(len=*), intent(in) :: header, name
integer :: i, fields
fields = 1
do i = 1, len_trim(header)
if (header(i:i) == ",") fields = fields + 1
end do
do field_index = 1, fields
if (field(header, field_index) == name) return
end do
error stop "column not found: " // name
end function field_index
! The k-th comma-separated field of a line.
function field(line, k) result(text)
character(len=*), intent(in) :: line
integer, intent(in) :: k
character(len=:), allocatable :: text
integer :: start, i, comma
start = 1
do i = 1, k - 1
start = start + index(line(start:), ",")
end do
comma = index(line(start:), ",")
if (comma == 0) then
text = trim(line(start:))
else
text = line(start:start + comma - 2)
end if
end function field
! Print "name value" with six decimals. The f0.6 format drops the zero
! before the point (0.5 prints as .500000), so we put it back.
subroutine say(name, x)
character(len=*), intent(in) :: name
real(dp), intent(in) :: x
character(len=40) :: text
write(text, "(f0.6)") x
if (text(1:1) == ".") text = "0" // text
if (text(1:2) == "-.") text = "-0" // text(2:)
print "(a, 1x, a)", name, trim(text)
end subroutine say
end program naive_bayesEach email is a derived type with an array of three feature values and a
label. Fortran lets you take one component across a whole array: train%label
is every training label, so
count(train%label == label .and. train%values(f) == row%values(f)) counts
one value within one label, and we add one for smoothing. Masks do the work a
dictionary does in other languages.
The labels are collected and insertion-sorted. In gfortran, < compares
character codes, so "ham" < "Spam" is false; all our labels are lowercase.
maxloc returns the first of equal scores, so an exact tie goes to the
alphabetically first label. gfortran has no naive Bayes intrinsic to avoid.
// Categorical naive Bayes with add-one (Laplace) smoothing, standard library only.
//
// Learns P(label) and P(feature value | label) by counting training rows, then
// labels each test row with the label that has the highest log-probability.
package main
import (
"encoding/csv"
"fmt"
"math"
"os"
"slices"
)
var features = []string{"has_link", "mentions_money", "known_sender"}
const label = "label"
// key identifies one count: how many training rows of a label have a value.
type key struct{ feature, value, label string }
// readRows returns each CSV row as a map from header name to value.
func readRows(path string) ([]map[string]string, error) {
f, err := os.Open(path)
if err != nil {
return nil, err
}
defer f.Close()
records, err := csv.NewReader(f).ReadAll()
if err != nil {
return nil, err
}
rows := make([]map[string]string, 0, len(records)-1)
for _, record := range records[1:] {
row := map[string]string{}
for i, name := range records[0] {
row[name] = record[i]
}
rows = append(rows, row)
}
return rows, nil
}
func main() {
rows, err := readRows(os.Args[1])
if err != nil {
fmt.Fprintln(os.Stderr, err)
os.Exit(1)
}
var train, test []map[string]string
for _, row := range rows {
if row["split"] == "train" {
train = append(train, row)
} else {
test = append(test, row)
}
}
// A missing map key reads as zero, so these work as counters.
labelCounts := map[string]int{}
valueCounts := map[key]int{}
seen := map[string]map[string]bool{} // distinct values of each feature
for _, f := range features {
seen[f] = map[string]bool{}
}
for _, row := range train {
labelCounts[row[label]]++
for _, f := range features {
valueCounts[key{f, row[f], row[label]}]++
seen[f][row[f]] = true
}
}
// Map iteration order is random in Go, so sort the labels to get a fixed
// order: an exact tie goes to the alphabetically first label.
labels := make([]string, 0, len(labelCounts))
for l := range labelCounts {
labels = append(labels, l)
}
slices.Sort(labels)
logScore := func(row map[string]string, l string) float64 {
// Logs turn the product of probabilities into a sum, avoiding underflow.
score := math.Log(float64(labelCounts[l]) / float64(len(train)))
for _, f := range features {
// Add-one smoothing: an unseen value never gets probability zero.
count := float64(valueCounts[key{f, row[f], l}] + 1)
score += math.Log(count / float64(labelCounts[l]+len(seen[f])))
}
return score
}
classify := func(row map[string]string) string {
best := labels[0]
for _, l := range labels[1:] {
if logScore(row, l) > logScore(row, best) {
best = l
}
}
return best
}
correct := 0
for _, row := range test {
if classify(row) == row[label] {
correct++
}
}
fmt.Printf("train_count %d\n", len(train))
fmt.Printf("test_count %d\n", len(test))
fmt.Printf("correct %d\n", correct)
fmt.Printf("accuracy %.6f\n", float64(correct)/float64(len(test)))
}Maps do all the counting. A struct with feature, value, and label
fields works as a map key, so valueCounts[key{f, row[f], row[label]}]++
counts all three together, and a missing key reads as zero. A map of bool
values serves as a set for the distinct values of each feature.
The trap is order. Go randomizes map iteration, so ranging over the label
counts would try the labels in a different order on different runs, and an
exact tie could go either way. We copy the labels into a slice and sort it,
so a tie always goes to the alphabetically first. Every count is an int,
so each probability converts with float64() before dividing.
-- Categorical naive Bayes with add-one (Laplace) smoothing, using only
-- Haskell's base library.
--
-- Learns P(label) and P(feature value | label) by counting training rows, then
-- labels each test row with the label that has the highest log-probability.
-- base has no map type, so counts live in association lists: lists of
-- (key, count) pairs, searched with lookup.
import Data.List (group, minimumBy, nub, sort)
import Data.Maybe (fromMaybe)
import Data.Ord (Down (..), comparing)
import System.Environment (getArgs)
import Text.Printf (printf)
-- A row pairs each column name with its value, such as ("label", "spam").
type Row = [(String, String)]
features :: [String]
features = ["has_link", "mentions_money", "known_sender"]
-- Split a line at every comma. break returns the text before the first comma
-- and the rest, which still starts with the comma.
splitOnComma :: String -> [String]
splitOnComma line = case break (== ',') line of
(field, ',' : rest) -> field : splitOnComma rest
(field, _) -> [field]
-- Every data line, with its fields paired to the header's column names.
readRows :: String -> [Row]
readRows text = case lines text of
header : rows -> [zip (splitOnComma header) (splitOnComma row) | row <- rows, not (null row)]
[] -> error "empty file"
-- The value in a named column. lookup returns Maybe: Nothing if it is missing.
column :: String -> Row -> String
column name row = fromMaybe (error ("no column " ++ name)) (lookup name row)
-- How many times each key appears: sort brings equal keys together, group
-- gathers each run of them, and every group becomes (key, its length).
countAll :: Ord a => [a] -> [(a, Int)]
countAll keys = [(head run, length run) | run <- group (sort keys)]
-- A count from an association list, or 0 for a key never seen.
countOf :: Eq a => a -> [(a, Int)] -> Int
countOf key counts = fromMaybe 0 (lookup key counts)
-- The model is three sets of counts, all from the training rows.
data Model = Model
{ trainSize :: Int
, labelCounts :: [(String, Int)] -- label -> rows
, valueCounts :: [((String, String, String), Int)] -- (feature, value, label) -> rows
, distinctValues :: [(String, Int)] -- feature -> distinct values
}
train :: [Row] -> Model
train rows = Model
{ trainSize = length rows
, labelCounts = countAll [column "label" row | row <- rows]
, valueCounts = countAll [(f, column f row, column "label" row) | row <- rows, f <- features]
, distinctValues = [(f, length (nub [column f row | row <- rows])) | f <- features]
}
-- Logs turn the product of probabilities into a sum, avoiding underflow.
-- Add-one smoothing means an unseen value never gets probability zero.
logScore :: Model -> Row -> String -> Double
logScore model row label =
log (ratio labelCount (trainSize model))
+ sum [ log (ratio (countOf (f, column f row, label) (valueCounts model) + 1)
(labelCount + countOf f (distinctValues model)))
| f <- features ]
where
labelCount = countOf label (labelCounts model)
-- Counts are Ints; fromIntegral converts them so they can divide as Doubles.
ratio a b = fromIntegral a / fromIntegral b
-- countAll sorted the labels, so they are in alphabetical order here.
-- minimumBy keeps the first of equal values, and Down flips the order so the
-- smallest is the highest score: an exact tie goes to the first label.
-- (maximumBy would keep the last, sending a tie to the wrong label.)
classify :: Model -> Row -> String
classify model row =
minimumBy (comparing (\label -> Down (logScore model row label))) (map fst (labelCounts model))
main :: IO ()
main = do
[path] <- getArgs
text <- readFile path
let rows = readRows text
trainRows = [row | row <- rows, column "split" row == "train"]
testRows = [row | row <- rows, column "split" row == "test"]
model = train trainRows
correct = length [row | row <- testRows, classify model row == column "label" row]
printf "train_count %d\n" (length trainRows)
printf "test_count %d\n" (length testRows)
printf "correct %d\n" correct
printf "accuracy %.6f\n" (fromIntegral correct / fromIntegral (length testRows) :: Double)We count by turning each training row into keys and tallying them with
countAll: sort brings equal keys together, group gathers each run,
and the run’s length is the count. Value counts are keyed by a
(feature, value, label) triple, and each row is itself a list of
(column, value) pairs. base has no map type, so all of these are
association lists searched with lookup, which returns a Maybe.
The tie rule needs care. maximumBy returns the last of equal scores, so
classify uses minimumBy with Down, which flips the order and keeps
the first. The labels come out of sort, so a tie goes to the
alphabetically first one.
// Categorical naive Bayes with add-one (Laplace) smoothing, using only the
// Java standard library.
//
// Learns P(label) and P(feature value | label) by counting training rows,
// then labels each test row with the label that has the highest
// log-probability.
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
class Main {
static final String[] FEATURES = {"has_link", "mentions_money", "known_sender"};
// One count: how many training rows of a label have a feature value. A
// record gets equals and hashCode from its fields, so two Keys with the
// same three strings find the same map entry.
record Key(String feature, String value, String label) {}
// The named column of the CSV lines, as an array of strings.
static String[] readColumn(List<String> lines, String name) {
int index = Arrays.asList(lines.get(0).split(",")).indexOf(name);
if (index < 0) {
throw new IllegalArgumentException("no column " + name);
}
String[] values = new String[lines.size() - 1];
for (int row = 1; row < lines.size(); row++) {
values[row - 1] = lines.get(row).split(",")[index];
}
return values;
}
public static void main(String[] args) throws IOException {
// Reading a file can fail with an IOException, and Java makes us say
// so with "throws".
List<String> lines = Files.readAllLines(Path.of(args[0]));
String[] labels = readColumn(lines, "label");
String[] split = readColumn(lines, "split");
// features[f][row] is feature f's value in that row.
String[][] features = new String[FEATURES.length][];
for (int f = 0; f < FEATURES.length; f++) {
features[f] = readColumn(lines, FEATURES[f]);
}
// A TreeMap keeps its keys sorted, so the labels come out in
// alphabetical order. merge(key, 1, Integer::sum) adds one, starting
// from 1 when the key is new.
Map<String, Integer> labelCounts = new TreeMap<>();
Map<Key, Integer> valueCounts = new HashMap<>();
List<Set<String>> seen = new ArrayList<>(); // distinct values
for (int f = 0; f < FEATURES.length; f++) {
seen.add(new HashSet<>());
}
int trainCount = 0;
for (int row = 0; row < labels.length; row++) {
if (!split[row].equals("train")) {
continue;
}
trainCount++;
labelCounts.merge(labels[row], 1, Integer::sum);
for (int f = 0; f < FEATURES.length; f++) {
valueCounts.merge(new Key(FEATURES[f], features[f][row], labels[row]), 1, Integer::sum);
seen.get(f).add(features[f][row]);
}
}
int testCount = 0;
int correct = 0;
for (int row = 0; row < labels.length; row++) {
if (!split[row].equals("test")) {
continue;
}
testCount++;
// Labels are tried in alphabetical order and only a strictly
// higher score replaces the best, so an exact tie goes to the
// first.
String best = null;
double bestScore = Double.NEGATIVE_INFINITY;
for (var entry : labelCounts.entrySet()) {
String label = entry.getKey();
int n = entry.getValue();
// Logs turn the product of probabilities into a sum, avoiding
// underflow. (double) keeps int / int from rounding down to 0.
double score = Math.log((double) n / trainCount);
for (int f = 0; f < FEATURES.length; f++) {
// Add-one smoothing: an unseen value never gets
// probability zero; getOrDefault reads it as 0.
int count = valueCounts.getOrDefault(new Key(FEATURES[f], features[f][row], label), 0) + 1;
score += Math.log((double) count / (n + seen.get(f).size()));
}
if (best == null || score > bestScore) {
best = label;
bestScore = score;
}
}
// equals compares the text; == would compare the objects.
if (best.equals(labels[row])) {
correct++;
}
}
Locale root = Locale.ROOT;
System.out.printf(root, "train_count %d%n", trainCount);
System.out.printf(root, "test_count %d%n", testCount);
System.out.printf(root, "correct %d%n", correct);
System.out.printf(root, "accuracy %.6f%n", (double) correct / testCount);
}
}A Key record with feature, value, and label fields keys the counts.
Records get equals and hashCode from their fields, so two Keys built
from the same three strings find the same HashMap entry; a plain class
would count them apart. merge(key, 1, Integer::sum) adds one, and
getOrDefault reads a missing count as 0, where get would return null.
The label counts live in a TreeMap, which keeps its keys sorted, so the
labels are tried alphabetically and only a strictly higher score wins a tie.
Every count is an int, and 55 / 150 is 0, so each division casts to
double first. No naive Bayes library is involved, and Java ships none.
// Categorical naive Bayes with add-one (Laplace) smoothing, Node built-ins only.
// Learns P(label) and P(feature value | label) by counting training rows, then
// labels each test row with the label that has the highest log-probability.
import { readFileSync } from "node:fs";
const FEATURES = ["has_link", "mentions_money", "known_sender"];
const LABEL = "label";
// Node has no CSV parser. No field here is quoted, so we split on commas and
// turn each line into an object keyed by the header names.
function readRows(path) {
const [header, ...lines] = readFileSync(path, "utf8").trim().split("\n");
const names = header.split(",");
return lines.map((line) => {
const fields = line.split(",");
return Object.fromEntries(names.map((name, i) => [name, fields[i]]));
});
}
// A Map counter. Arrays compare by identity, so a key made of several parts
// is joined into one string: "has_link|yes|spam".
function countBy(items, keyOf) {
const counts = new Map();
for (const item of items) {
const key = keyOf(item);
counts.set(key, (counts.get(key) ?? 0) + 1);
}
return counts;
}
const rows = readRows(process.argv[2]);
const train = rows.filter((row) => row.split === "train");
const test = rows.filter((row) => row.split === "test");
const labelCounts = countBy(train, (row) => row[LABEL]);
// valueCounts.get("feature|value|label") = number of training rows
const valueCounts = countBy(
train.flatMap((row) => FEATURES.map((f) => [f, row[f], row[LABEL]])),
(parts) => parts.join("|"),
);
const distinctValues = Object.fromEntries(
FEATURES.map((f) => [f, new Set(train.map((row) => row[f])).size]),
);
function logScore(row, label) {
// Logs turn the product of probabilities into a sum, avoiding underflow.
let score = Math.log(labelCounts.get(label) / train.length);
for (const f of FEATURES) {
// Add-one smoothing: an unseen value never gets probability zero.
const count = (valueCounts.get([f, row[f], label].join("|")) ?? 0) + 1;
score += Math.log(count / (labelCounts.get(label) + distinctValues[f]));
}
return score;
}
// Labels are tried in alphabetical order and only a strictly higher score
// replaces the best, so an exact tie goes to the alphabetically first label.
const labels = [...labelCounts.keys()].sort();
function classify(row) {
let best = labels[0];
for (const label of labels.slice(1)) {
if (logScore(row, label) > logScore(row, best)) best = label;
}
return best;
}
const correct = test.filter((row) => classify(row) === row[LABEL]).length;
console.log(`train_count ${train.length}`);
console.log(`test_count ${test.length}`);
console.log(`correct ${correct}`);
console.log(`accuracy ${(correct / test.length).toFixed(6)}`);The counting needs one workaround. A Map accepts any value as a key, but
it compares arrays by identity, so after counting the triple
["has_link", "yes", "spam"], looking up a new array with the same three
strings returns undefined. We join the parts into one string,
"has_link|yes|spam", instead. A missing key still returns undefined, and
?? 0 turns that into zero, so add-one smoothing works for unseen values.
Division is always floating point: 3 / 55 is 0.0545..., not the 0
Ruby’s integer division gives. Labels are sorted alphabetically, and only a
strictly higher score replaces the best, so a tie goes to the first label.
There was no built-in classifier to skip.
# Categorical naive Bayes with add-one (Laplace) smoothing, using only Base Julia.
#
# Learns P(label) and P(feature value | label) by counting training rows, then
# labels each test row with the label that has the highest log-probability.
using Printf
const FEATURES = ["has_link", "mentions_money", "known_sender"]
function read_rows(path)
lines = readlines(path)
header = split(lines[1], ",")
# Each row becomes a Dict from column name to value.
return [Dict(zip(header, split(line, ","))) for line in lines[2:end]]
end
function main(path)
rows = read_rows(path)
train = filter(row -> row["split"] == "train", rows)
test = filter(row -> row["split"] == "test", rows)
label_counts = Dict{String,Int}()
value_counts = Dict{Tuple{String,String,String},Int}() # (feature, value, label)
for row in train
label = row["label"]
label_counts[label] = get(label_counts, label, 0) + 1
for f in FEATURES
key = (f, row[f], label)
value_counts[key] = get(value_counts, key, 0) + 1
end
end
distinct_values = Dict(f => length(unique(row[f] for row in train))
for f in FEATURES)
function log_score(row, label)
# Logs turn the product of probabilities into a sum, avoiding underflow.
score = log(label_counts[label] / length(train))
for f in FEATURES
# Add-one smoothing: an unseen value never gets probability zero.
count = get(value_counts, (f, row[f], label), 0) + 1
score += log(count / (label_counts[label] + distinct_values[f]))
end
return score
end
# Labels are tried in alphabetical order, and argmax returns the first
# maximum, so an exact tie goes to the first label.
labels = sort(collect(keys(label_counts)))
classify(row) = labels[argmax([log_score(row, label) for label in labels])]
correct = count(row -> classify(row) == row["label"], test)
println("train_count $(length(train))")
println("test_count $(length(test))")
println("correct $correct")
@printf("accuracy %.6f\n", correct / length(test))
end
main(ARGS[1])Each row is read into a Dict from column name to value, and the counts go
into two more: one keyed by label, and one keyed by a
(feature, value, label) tuple. get(counts, key, 0) reads a missing
count as zero, so unseen combinations need no special case before add-one
smoothing.
A Dict doesn’t keep insertion order, so the labels are sorted before
scoring. argmax then returns the first of equal scores, which sends an
exact tie to the alphabetically first label, matching Python’s tie rule.
Julia’s standard library has no naive Bayes, so there was nothing to skip.
-- Categorical naive Bayes with add-one (Laplace) smoothing, using only Lua's
-- standard library.
--
-- Lua has no classifier and no counting helper, so we count training rows
-- into tables, then label each test row with the label that has the highest
-- log-probability.
local FEATURES = { "has_link", "mentions_money", "known_sender" }
-- Returns the rows as a list of tables, keyed by column name.
local function read_rows(path)
local f = assert(io.open(path, "r"))
local header = {}
for name in f:read("l"):gmatch("[^,]+") do header[#header + 1] = name end
local rows = {}
for line in f:lines() do
local row, i = {}, 0
for value in line:gmatch("[^,]+") do
i = i + 1
row[header[i]] = value
end
rows[#rows + 1] = row
end
f:close()
return rows
end
local train, test = {}, {}
for _, row in ipairs(read_rows(arg[1])) do
if row.split == "train" then
train[#train + 1] = row
else
test[#test + 1] = row
end
end
-- A table key matches by identity, so two tables {f, v, label} with the
-- same contents would be two different keys. We join the three into one
-- string instead, which matches by value.
local function key(f, v, label)
return f .. "|" .. v .. "|" .. label
end
-- label_counts: label -> rows. value_counts: "feature|value|label" -> rows.
-- values_seen: feature -> set of the distinct values it takes.
local label_counts, value_counts, values_seen = {}, {}, {}
for _, f in ipairs(FEATURES) do values_seen[f] = {} end
for _, row in ipairs(train) do
local label = row.label
-- A missing key reads as nil, so "or 0" starts each count at zero.
label_counts[label] = (label_counts[label] or 0) + 1
for _, f in ipairs(FEATURES) do
local k = key(f, row[f], label)
value_counts[k] = (value_counts[k] or 0) + 1
values_seen[f][row[f]] = true
end
end
-- # counts only the 1, 2, 3, ... part of a table, so a set is counted by
-- walking it with pairs.
local distinct = {}
for _, f in ipairs(FEATURES) do
local n = 0
for _ in pairs(values_seen[f]) do n = n + 1 end
distinct[f] = n
end
local function log_score(row, label)
local n_label = label_counts[label]
-- Logs turn the product of probabilities into a sum, avoiding underflow.
local score = math.log(n_label / #train)
for _, f in ipairs(FEATURES) do
-- Add-one smoothing: an unseen value never gets probability zero.
local count = (value_counts[key(f, row[f], label)] or 0) + 1
score = score + math.log(count / (n_label + distinct[f]))
end
return score
end
-- pairs visits keys in no fixed order, so we sort the labels first.
local labels = {}
for label in pairs(label_counts) do labels[#labels + 1] = label end
table.sort(labels)
-- Labels are tried in alphabetical order, and only a strictly higher score
-- replaces the best, so an exact tie goes to the first.
local function classify(row)
local best, best_score = nil, nil
for _, label in ipairs(labels) do
local score = log_score(row, label)
if best == nil or score > best_score then
best, best_score = label, score
end
end
return best
end
local correct = 0
for _, row in ipairs(test) do
if classify(row) == row.label then correct = correct + 1 end
end
print("train_count " .. #train)
print("test_count " .. #test)
print("correct " .. correct)
print(string.format("accuracy %.6f", correct / #test))We count with tables. A key that was never set reads as nil, so
(counts[k] or 0) + 1 starts each count at zero. A table can be a key,
but it matches by identity: t[{1}] = 5 followed by t[{1}] gives nil,
because the two {1}s are different tables. So we join the feature,
value, and label into one string, such as "has_link|yes|spam", which
matches by value.
# counts only a table’s 1, 2, 3, … part, so the set of distinct values
is counted with pairs. pairs has no fixed order, so the labels are
sorted first, and only a strictly higher score wins, so a tie goes to the
first. Lua has no classifier to skip.
(* Categorical naive Bayes with add-one (Laplace) smoothing, using only
OCaml's standard library.
Learns P(label) and P(feature value | label) by counting training rows,
then labels each test row with the label that has the highest
log-probability. Counts live in Hashtbl, the standard library's hash
table. *)
let features = [ "has_link"; "mentions_money"; "known_sender" ]
(* Every data line, with its fields paired to the header's column names, such
as ("label", "spam"). A list of pairs like this is an association list. *)
let read_rows path =
In_channel.with_open_text path (fun ic ->
match In_channel.input_lines ic with
| [] -> failwith "empty file"
| header :: rows ->
let names = String.split_on_char ',' header in
rows
|> List.filter (fun row -> row <> "")
|> List.map (fun row ->
List.combine names (String.split_on_char ',' row)))
(* The value in a named column. List.assoc raises Not_found if it's missing. *)
let column name row = List.assoc name row
(* Add one to a key's count. find_opt returns None for a key never seen. *)
let bump table key =
let n = Option.value (Hashtbl.find_opt table key) ~default:0 in
Hashtbl.replace table key (n + 1)
let count_of table key = Option.value (Hashtbl.find_opt table key) ~default:0
let () =
let rows = read_rows Sys.argv.(1) in
let train = List.filter (fun row -> column "split" row = "train") rows in
let test = List.filter (fun row -> column "split" row = "test") rows in
(* label_counts: label -> rows. value_counts: (feature, value, label) ->
rows. Hashtbl hashes and compares keys by value, so a tuple works as a
key. seen: (feature, value) -> rows, used only for its distinct keys. *)
let label_counts = Hashtbl.create 2 in
let value_counts = Hashtbl.create 16 in
let seen = Hashtbl.create 8 in
List.iter
(fun row ->
bump label_counts (column "label" row);
List.iter
(fun f ->
bump value_counts (f, column f row, column "label" row);
bump seen (f, column f row))
features)
train;
let distinct f =
Hashtbl.fold (fun (g, _) _ n -> if g = f then n + 1 else n) seen 0
in
let n_train = float_of_int (List.length train) in
(* Logs turn the product of probabilities into a sum, avoiding underflow.
Add-one smoothing means an unseen value never gets probability zero. *)
let log_score row label =
let n_label = count_of label_counts label in
List.fold_left
(fun score f ->
let count = count_of value_counts (f, column f row, label) + 1 in
score +. log (float_of_int count /. float_of_int (n_label + distinct f)))
(log (float_of_int n_label /. n_train))
features
in
(* Hashtbl visits keys in no fixed order, so we sort the labels first. *)
let labels =
List.sort compare (Hashtbl.fold (fun label _ acc -> label :: acc) label_counts [])
in
(* Labels are tried in alphabetical order, and only a strictly higher score
replaces the best, so an exact tie goes to the first. *)
let classify row =
let best, _ =
List.fold_left
(fun (best, best_score) label ->
let score = log_score row label in
if score > best_score then (label, score) else (best, best_score))
("", neg_infinity) labels
in
best
in
let correct = List.length (List.filter (fun row -> classify row = column "label" row) test) in
Printf.printf "train_count %d\n" (List.length train);
Printf.printf "test_count %d\n" (List.length test);
Printf.printf "correct %d\n" correct;
Printf.printf "accuracy %.6f\n"
(float_of_int correct /. float_of_int (List.length test))We count training rows into Hashtbl, the standard library’s hash table.
Value counts are keyed by a (feature, value, label) tuple, which works
because Hashtbl hashes and compares keys by value, not by identity.
Hashtbl.find_opt returns None for a key never seen, so bump and
count_of start each count at zero. Each row is an association list of
(column, value) pairs, searched with List.assoc.
OCaml has no classifier or counting helper, so the smoothing and log
scores are written out. Hashtbl keeps its keys in no useful order, so
the labels are sorted first, and only a strictly higher score replaces
the best: an exact tie goes to the alphabetically first label.
% Categorical naive Bayes with add-one (Laplace) smoothing, using only core
% GNU Octave.
%
% Learns P(label) and P(feature value | label) by counting training rows, then
% labels each test row with the label that has the highest log-probability.
% Counting is done with logical masks: strcmp compares a whole column of
% strings at once, and sum counts the matches.
% The named column of a CSV file, as a column cell array of strings.
function values = read_column(path, name)
lines = strsplit(strtrim(fileread(path)), "\n");
header = strsplit(strtrim(lines{1}), ",");
index = find(strcmp(header, name));
if isempty(index)
error("no column %s", name);
end
values = cell(numel(lines) - 1, 1);
for row = 2:numel(lines)
fields = strsplit(strtrim(lines{row}), ",");
values{row - 1} = fields{index};
end
end
FEATURES = {"has_link", "mentions_money", "known_sender"};
args = argv();
split = read_column(args{1}, "split");
is_train = strcmp(split, "train"); % a logical vector, one entry per row
is_test = strcmp(split, "test");
label = read_column(args{1}, "label");
train_label = label(is_train);
test_label = label(is_test);
n_train = numel(train_label);
n_test = numel(test_label);
% unique returns the distinct labels sorted, so they are tried in
% alphabetical order.
labels = unique(train_label);
% Each feature column, split into its training and test rows.
train_values = cell(1, numel(FEATURES));
test_values = cell(1, numel(FEATURES));
for f = 1:numel(FEATURES)
column = read_column(args{1}, FEATURES{f});
train_values{f} = column(is_train);
test_values{f} = column(is_test);
end
% scores(i, c) is the log-probability score of test row i under label c.
scores = zeros(n_test, numel(labels));
for c = 1:numel(labels)
in_label = strcmp(train_label, labels{c});
n_c = sum(in_label);
% Logs turn the product of probabilities into a sum, avoiding underflow.
scores(:, c) = log(n_c / n_train);
for f = 1:numel(FEATURES)
m = numel(unique(train_values{f})); % distinct values the feature takes
% For each test row, count the training rows with this label and the
% same value. cellfun calls the function on every cell and collects
% the numbers into a vector.
matches = cellfun(@(v) sum(in_label & strcmp(train_values{f}, v)), ...
test_values{f});
% Add-one smoothing: an unseen value never gets probability zero.
scores(:, c) += log((matches + 1) / (n_c + m));
end
end
% max along each row returns the column of the first maximum, so an exact
% tie goes to the alphabetically first label.
[~, best] = max(scores, [], 2);
correct = sum(strcmp(labels(best), test_label));
printf("train_count %d\n", n_train);
printf("test_count %d\n", n_test);
printf("correct %d\n", correct);
printf("accuracy %.6f\n", correct / n_test);We keep no table of counts. strcmp compares a whole column of strings with
one value and returns a logical vector, so
sum(in_label & strcmp(train_values{f}, v)) counts the training rows with
this label and this value. cellfun repeats that for every test row and
collects the counts in a vector, and the scores fill a test-by-label matrix.
unique lists the labels sorted by character code, so "Spam" would sort
before "ham"; ours are all lowercase. max(scores, [], 2) returns the
first of equal scores, so an exact tie goes to the alphabetically first
label. Core Octave has no naive Bayes to avoid, and the statistics package
isn’t installed.
{ Categorical naive Bayes with add-one (Laplace) smoothing, using only Free
Pascal's run-time library.
Learns P(label) and P(feature value | label) by counting training rows,
then labels each test row with the label that has the highest
log-probability. Sorting the labels uses TArrayHelper from
Generics.Collections. }
program NaiveBayes;
{$mode objfpc}{$H+} // 32-bit Integer, and strings longer than 255 characters
uses
SysUtils, Generics.Collections;
const
NFeatures = 3;
Features: array[0..NFeatures - 1] of String =
('has_link', 'mentions_money', 'known_sender');
type
// One email: its three feature values, its label, and its split.
TRow = record
Values: array[0..NFeatures - 1] of String;
Label_, Split: String; // "label" is a reserved word, hence the underscore
end;
TRowArray = array of TRow;
TLabelArray = array of String;
function ReadRows(const Path: String): TRowArray;
var
F: TextFile;
Line: String;
Fields: TStringArray;
Cols: array[0..NFeatures - 1] of Integer;
LabelCol, SplitCol, I, C: Integer;
begin
Result := nil;
AssignFile(F, Path);
Reset(F);
ReadLn(F, Line);
Fields := Line.Split(',');
for C := 0 to NFeatures - 1 do
Cols[C] := -1;
LabelCol := -1;
SplitCol := -1;
for I := 0 to High(Fields) do
begin
for C := 0 to NFeatures - 1 do
if Fields[I] = Features[C] then Cols[C] := I;
if Fields[I] = 'label' then LabelCol := I;
if Fields[I] = 'split' then SplitCol := I;
end;
for C := 0 to NFeatures - 1 do
if Cols[C] < 0 then
raise Exception.Create('column not found: ' + Features[C]);
if (LabelCol < 0) or (SplitCol < 0) then
raise Exception.Create('no label or split column');
while not Eof(F) do
begin
ReadLn(F, Line);
if Line = '' then
Continue;
Fields := Line.Split(',');
SetLength(Result, Length(Result) + 1); // grow by one
for C := 0 to NFeatures - 1 do
Result[High(Result)].Values[C] := Fields[Cols[C]];
Result[High(Result)].Label_ := Fields[LabelCol];
Result[High(Result)].Split := Fields[SplitCol];
end;
CloseFile(F);
end;
var
Train: TRowArray;
Labels: TLabelArray;
DistinctValues: array[0..NFeatures - 1] of Integer;
{ Training rows with this label and, if Feature >= 0, this value of it.
There is no dictionary of counts: each call recounts. }
function CountRows(const Lbl: String; Feature: Integer; const Value: String): Integer;
var
I: Integer;
begin
Result := 0;
for I := 0 to High(Train) do
if (Train[I].Label_ = Lbl) and
((Feature < 0) or (Train[I].Values[Feature] = Value)) then
Inc(Result);
end;
function LogScore(const Row: TRow; const Lbl: String): Double;
var
LabelCount, Count, C: Integer;
begin
LabelCount := CountRows(Lbl, -1, '');
// Logs turn the product of probabilities into a sum, avoiding underflow.
Result := Ln(LabelCount / Length(Train));
for C := 0 to NFeatures - 1 do
begin
// Add-one smoothing: an unseen value never gets probability zero.
Count := CountRows(Lbl, C, Row.Values[C]) + 1;
Result := Result + Ln(Count / (LabelCount + DistinctValues[C]));
end;
end;
{ Labels are tried in sorted (character-code) order, and only a strictly higher score
replaces the best, so an exact tie goes to the first. }
function Classify(const Row: TRow): String;
var
Best, Score: Double;
L: Integer;
begin
Result := Labels[0];
Best := LogScore(Row, Result);
for L := 1 to High(Labels) do
begin
Score := LogScore(Row, Labels[L]);
if Score > Best then
begin
Result := Labels[L];
Best := Score;
end;
end;
end;
{ True if any of the first Before training rows has this label (Feature < 0)
or this value of Feature. }
function SeenEarlier(Before, Feature: Integer; const Text: String): Boolean;
var
E: Integer;
begin
Result := False;
for E := 0 to Before - 1 do
if ((Feature < 0) and (Train[E].Label_ = Text)) or
((Feature >= 0) and (Train[E].Values[Feature] = Text)) then
Exit(True);
end;
var
Rows: TRowArray;
I, C, TestCount, Correct: Integer;
begin
Rows := ReadRows(ParamStr(1));
// Records are values, so Train holds copies of the training rows.
Train := nil;
for I := 0 to High(Rows) do
if Rows[I].Split = 'train' then
begin
SetLength(Train, Length(Train) + 1);
Train[High(Train)] := Rows[I];
end;
if Length(Train) = 0 then
raise Exception.Create('no training rows');
// A label or value is new if no earlier training row has it.
Labels := nil;
for C := 0 to NFeatures - 1 do
DistinctValues[C] := 0;
for I := 0 to High(Train) do
begin
if not SeenEarlier(I, -1, Train[I].Label_) then
begin
SetLength(Labels, Length(Labels) + 1);
Labels[High(Labels)] := Train[I].Label_;
end;
for C := 0 to NFeatures - 1 do
if not SeenEarlier(I, C, Train[I].Values[C]) then
Inc(DistinctValues[C]);
end;
specialize TArrayHelper<String>.Sort(Labels);
TestCount := 0;
Correct := 0;
for I := 0 to High(Rows) do
if Rows[I].Split = 'test' then
begin
Inc(TestCount);
if Classify(Rows[I]) = Rows[I].Label_ then
Inc(Correct);
end;
WriteLn('train_count ', Length(Train));
WriteLn('test_count ', TestCount);
WriteLn('correct ', Correct);
WriteLn('accuracy ', Correct / TestCount:0:6); // width 0, six decimals
end.Each email is a TRow record holding its three feature values, label,
and split. label is a reserved word in Pascal, so the field is Label_.
We keep no table of counts, since TDictionary won’t compile here with
warnings as errors: CountRows recounts matching training rows each time
a score needs one.
The distinct labels go through TArrayHelper<String>.Sort, which orders
by character code, so 'Spam' would sort before 'ham'; all our labels
are lowercase. Only a strictly higher score replaces the best, so an exact
tie goes to the alphabetically first label. Ln takes the logs, and none
of the installed units has a naive Bayes routine to avoid.
# Categorical naive Bayes with add-one (Laplace) smoothing, using only Perl
# and its core modules.
#
# Learns P(label) and P(feature value | label) by counting training rows,
# then labels each test row with the label that has the highest
# log-probability.
use strict;
use warnings;
my @FEATURES = qw(has_link mentions_money known_sender);
my $LABEL = 'label';
# Each row becomes a hash reference keyed by column name.
sub read_rows {
my ($path) = @_;
open my $fh, '<', $path or die "can't open $path: $!";
chomp(my $header = <$fh>);
my @names = split /,/, $header;
my @rows;
while (my $line = <$fh>) {
chomp $line;
my %row;
@row{@names} = split /,/, $line; # a hash slice sets every column
push @rows, \%row;
}
close $fh;
return @rows;
}
my @rows = read_rows($ARGV[0]);
my @train = grep { $_->{split} eq 'train' } @rows;
my @test = grep { $_->{split} eq 'test' } @rows;
# Nested hashes spring into existence on first use (autovivification), so
# $count{$label}{$feature}{$value}++ needs no setup.
my (%label_count, %count, %seen);
for my $row (@train) {
my $label = $row->{$LABEL};
$label_count{$label}++;
for my $f (@FEATURES) {
$count{$label}{$f}{$row->{$f}}++;
$seen{$f}{$row->{$f}} = 1;
}
}
# keys of a hash used as a number is how many keys it has.
my %distinct = map { $_ => scalar keys %{ $seen{$_} } } @FEATURES;
sub log_score {
my ($row, $label) = @_;
# Logs turn the product of probabilities into a sum, avoiding underflow.
my $score = log($label_count{$label} / @train);
for my $f (@FEATURES) {
# Add-one smoothing: an unseen value never gets probability zero.
# // gives 0 when the count is undef, a value never seen with $label.
my $n = ($count{$label}{$f}{$row->{$f}} // 0) + 1;
$score += log($n / ($label_count{$label} + $distinct{$f}));
}
return $score;
}
# Hash order changes from run to run, so sort the labels, and only a
# strictly higher score wins: an exact tie goes to the alphabetically first.
sub classify {
my ($row) = @_;
my ($best, @rest) = sort keys %label_count;
for my $label (@rest) {
$best = $label if log_score($row, $label) > log_score($row, $best);
}
return $best;
}
my $correct = grep { classify($_) eq $_->{$LABEL} } @test;
printf "train_count %d\n", scalar @train;
printf "test_count %d\n", scalar @test;
print "correct $correct\n";
printf "accuracy %.6f\n", $correct / @test;We count with nested hashes: $count{$label}{$f}{$value}++ creates each
missing level on first use, which Perl calls autovivification. A count
never seen reads as undef, and // 0 turns that into zero before the
add-one smoothing.
Each row is a hash filled by a slice, @row{@names} = split, so the
columns are found by name. Hash order changes from run to run, so the
labels are sorted before scoring, and only a strictly higher score wins,
so a tie goes to the alphabetically first label. Perl has no classifier,
so there’s nothing to skip.
<?php
// Categorical naive Bayes with add-one (Laplace) smoothing, using only PHP
// and the extensions built into it.
//
// Learns P(label) and P(feature value | label) by counting training rows,
// then labels each test row with the label that has the highest
// log-probability.
declare(strict_types=1);
const FEATURES = ['has_link', 'mentions_money', 'known_sender'];
const LABEL = 'label';
// Each row becomes an array keyed by column name.
function read_rows(string $path): array
{
$lines = file($path, FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES);
$names = explode(',', array_shift($lines));
return array_map(fn($line) => array_combine($names, explode(',', $line)), $lines);
}
$rows = read_rows($argv[1]);
// array_filter keeps the original keys; array_values numbers them from 0.
$train = array_values(array_filter($rows, fn($r) => $r['split'] === 'train'));
$test = array_values(array_filter($rows, fn($r) => $r['split'] === 'test'));
// Reading a missing key warns, so each count starts from ?? 0.
$label_count = [];
$count = []; // $count[$label][$feature][$value]
$seen = []; // $seen[$feature][$value] = true
foreach ($train as $row) {
$label = $row[LABEL];
$label_count[$label] = ($label_count[$label] ?? 0) + 1;
foreach (FEATURES as $f) {
$value = $row[$f];
$count[$label][$f][$value] = ($count[$label][$f][$value] ?? 0) + 1;
$seen[$f][$value] = true;
}
}
function log_score(array $row, string $label): float
{
global $train, $label_count, $count, $seen;
// Logs turn the product of probabilities into a sum, avoiding underflow.
$score = log($label_count[$label] / count($train));
foreach (FEATURES as $f) {
// Add-one smoothing: an unseen value never gets probability zero.
$n = ($count[$label][$f][$row[$f]] ?? 0) + 1;
$score += log($n / ($label_count[$label] + count($seen[$f])));
}
return $score;
}
// Labels are tried in alphabetical order, and only a strictly higher score
// wins, so an exact tie goes to the alphabetically first label.
function classify(array $row): string
{
global $label_count;
$labels = array_keys($label_count);
sort($labels);
$best = $labels[0];
foreach ($labels as $label) {
if (log_score($row, $label) > log_score($row, $best)) {
$best = $label;
}
}
return $best;
}
$correct = count(array_filter($test, fn($r) => classify($r) === $r[LABEL]));
printf("train_count %d\n", count($train));
printf("test_count %d\n", count($test));
printf("correct %d\n", $correct);
printf("accuracy %.6f\n", $correct / count($test));array_combine pairs the header names with each line’s fields, so every row
is an array keyed by column name. The counts live in nested arrays, as in
$count[$label][$f][$value]; writing to a nested key creates the levels
above it. Reading a key that was never set, though, raises a warning, which
fails the run here, so each lookup adds ?? 0 to fall back to zero.
We sort the labels and let only a strictly higher score replace the best, so an exact tie goes to the alphabetically first label. PHP has no naive Bayes classifier, so there was no built-in to skip.
-- Categorical naive Bayes with add-one (Laplace) smoothing, in PostgreSQL.
--
-- Learns P(label) and P(feature value | label) by counting training rows, then
-- labels each test row with the label that has the highest log-probability.
WITH emails AS (
SELECT row_id AS id, has_link, mentions_money, known_sender, label, split FROM data
),
features AS (
-- One row per (email, feature), so every feature is counted the same way.
SELECT id, label, split, feature, value
FROM emails,
LATERAL (VALUES
('has_link', has_link),
('mentions_money', mentions_money),
('known_sender', known_sender)
) AS f (feature, value)
),
label_counts AS (
-- n_c, and the training total n.
SELECT label, count(*) AS n_c, (sum(count(*)) OVER ())::bigint AS n
FROM emails
WHERE split = 'train'
GROUP BY label
),
value_counts AS (
-- n_{c,v}: training emails with label c whose feature has value v.
SELECT feature, value, label, count(*) AS n_cv
FROM features
WHERE split = 'train'
GROUP BY feature, value, label
),
distinct_values AS (
-- m_j: how many distinct values each feature takes in the training data.
SELECT feature, count(DISTINCT value) AS m
FROM features
WHERE split = 'train'
GROUP BY feature
),
scores AS (
-- log P(c) + sum over features of log P(v_j | c), for each test email and label.
SELECT t.id, t.label AS actual, c.label,
ln(c.n_c::double precision / c.n)
+ sum(ln((coalesce(vc.n_cv, 0) + 1)::double precision / (c.n_c + d.m))) AS score
FROM features t
CROSS JOIN label_counts c
JOIN distinct_values d USING (feature)
LEFT JOIN value_counts vc
ON vc.feature = t.feature AND vc.value = t.value AND vc.label = c.label
WHERE t.split = 'test'
GROUP BY t.id, t.label, c.label, c.n_c, c.n
),
predictions AS (
-- Highest score wins; an exact tie goes to the alphabetically first label.
SELECT DISTINCT ON (id) id, actual, label AS predicted
FROM scores
ORDER BY id, score DESC, label
),
totals AS (
SELECT (SELECT sum(n_c) FROM label_counts) AS train_count,
count(*) AS test_count,
count(*) FILTER (WHERE predicted = actual) AS correct
FROM predictions
)
SELECT name, value
FROM totals,
LATERAL (VALUES
(1, 'train_count', train_count::text),
(2, 'test_count', test_count::text),
(3, 'correct', correct::text),
(4, 'accuracy', round(correct::numeric / test_count, 6)::text)
) AS results (position, name, value)
ORDER BY position;Naive Bayes is counting, and counting is what GROUP BY does. The label
counts, the (feature, value, label) counts, and the number of distinct
values per feature are each a short common table expression. The winner
comes from DISTINCT ON (id) ... ORDER BY id, score DESC, label, which keeps
the first row for each email, with the alphabetical tie-break built into the
ordering.
The features are three separate columns, so LATERAL (VALUES ...) first
turns each email into three (feature, value) rows that can all be counted
the same way. A combination that never occurs in training has no count row
at all, so the join to the counts is a LEFT JOIN with
coalesce(vc.n_cv, 0) before adding one. PostgreSQL has no naive Bayes
built in.
% Categorical naive Bayes with add-one (Laplace) smoothing, using
% SWI-Prolog and the libraries that come with it.
%
% Learns P(label) and P(feature value | label) by counting training rows,
% then labels each test row with the label that has the highest
% log-probability. Every cell of the CSV becomes a fact, and each count is
% a question asked of those facts, so there are no tables of counts.
:- initialization(main, main).
% cell(Row, Column, Value) facts are added while the program runs.
% Declaring cell/3 dynamic tells Prolog they can change, and makes a
% question about cells fail quietly, not raise an error, before any exist.
:- dynamic cell/3.
features(["has_link", "mentions_money", "known_sender"]).
% load_cells(+Path): add one cell fact for every value in the file, such as
% cell(1, "label", "spam") for row 1. Rows are numbered from 1.
load_cells(Path) :-
read_file_to_string(Path, Text, []),
split_string(Text, "\n", "", [HeaderLine|Lines]),
split_string(HeaderLine, ",", "", Header),
exclude(==(""), Lines, Rows),
forall(nth1(Row, Rows, Line),
( split_string(Line, ",", "", Fields),
forall(nth1(I, Header, Column),
( nth1(I, Fields, Value),
assertz(cell(Row, Column, Value)) )) )).
% A row is in the training or the test set by its split column.
train(Row) :- cell(Row, "split", "train").
test(Row) :- cell(Row, "split", "test").
% label_count(+Label, -N): training rows with this label. aggregate_all
% counts how many ways the goal in the middle can succeed.
label_count(Label, N) :-
aggregate_all(count, (train(Row), cell(Row, "label", Label)), N).
% value_count(+Feature, +Value, +Label, -N): training rows with this label
% whose Feature is Value. The key is just the three arguments.
value_count(Feature, Value, Label, N) :-
aggregate_all(count,
( train(Row),
cell(Row, "label", Label),
cell(Row, Feature, Value) ),
N).
% distinct_values(+Feature, -M): how many different values Feature takes
% in training. Here we want sort to drop repeats.
distinct_values(Feature, M) :-
findall(Value, (train(Row), cell(Row, Feature, Value)), Values),
sort(Values, Distinct),
length(Distinct, M).
% log_score(+Row, +Label, -Score): log P(Label) plus the log of each
% feature's smoothed P(value | Label). Logs turn the product into a sum,
% avoiding underflow; adding one means no probability is ever zero.
log_score(Row, Label, Score) :-
aggregate_all(count, train(_), N),
label_count(Label, NC),
features(Features),
findall(Term,
( member(F, Features),
cell(Row, F, Value),
value_count(F, Value, Label, NV),
distinct_values(F, M),
Term is log((NV + 1) / (NC + M)) ),
Terms),
sum_list(Terms, Sum),
Score is log(NC / N) + Sum.
% classify(+Row, -Best): the label with the highest score.
% aggregate_all(max(Score, Label), Goal, max(_, Best)) finds the highest
% Score over every solution of Goal and the Label that went with it. sort
% puts the labels in alphabetical order, and when several share the
% highest score, aggregate_all keeps the first: a tie goes to the
% alphabetically first label.
classify(Row, Best) :-
findall(Label, (train(R), cell(R, "label", Label)), AllLabels),
sort(AllLabels, Labels),
aggregate_all(max(Score, Label),
( member(Label, Labels),
log_score(Row, Label, Score) ),
max(_, Best)).
main :-
current_prolog_flag(argv, [Path|_]),
load_cells(Path),
aggregate_all(count, train(_), TrainCount),
aggregate_all(count, test(_), TestCount),
% A test row counts as correct when its predicted label is its label.
aggregate_all(count,
( test(Row),
classify(Row, Predicted),
cell(Row, "label", Predicted) ),
Correct),
Accuracy is Correct / TestCount,
format("train_count ~d~n", [TrainCount]),
format("test_count ~d~n", [TestCount]),
format("correct ~d~n", [Correct]),
format("accuracy ~6f~n", [Accuracy]).We turn every CSV value into a fact, such as cell(1, "label", "spam"),
and keep no tables of counts. Each count is a question asked of the facts:
aggregate_all(count, Goal, N) counts how many ways Goal can succeed,
so the feature, value, and label are just its arguments. We recount every
time we score.
sort drops repeats, which is what counting a feature’s distinct values
needs. For the tie rule, aggregate_all(max(Score, Label), ...) keeps the
first of equal scores, and the labels arrive in alphabetical order.
Taking max_member of Score-Label pairs would break a tie by comparing
the labels, so "spam" would win it. There’s no
naive Bayes built in to skip.
# Categorical naive Bayes with add-one (Laplace) smoothing, using only base R.
#
# Learns P(label) and P(feature value | label) by counting training rows, then
# labels each test row with the label that has the highest log-probability.
features <- c("has_link", "mentions_money", "known_sender")
args <- commandArgs(trailingOnly = TRUE)
# colClasses keeps "yes"/"no" as plain strings.
data <- read.csv(args[1], colClasses = "character")
train <- data[data$split == "train", ]
test <- data[data$split == "test", ]
# table() sorts its names, so labels come out in alphabetical order.
label_counts <- table(train$label)
labels <- names(label_counts)
log_score <- function(row, label) {
in_label <- train[train$label == label, ]
# Logs turn the product of probabilities into a sum, avoiding underflow.
score <- log(label_counts[[label]] / nrow(train))
for (f in features) {
# Add-one smoothing: an unseen value never gets probability zero.
# m is the number of distinct values the feature takes in training.
count <- sum(in_label[[f]] == row[[f]]) + 1
m <- length(unique(train[[f]]))
score <- score + log(count / (label_counts[[label]] + m))
}
score
}
classify <- function(row) {
scores <- sapply(labels, function(label) log_score(row, label))
labels[which.max(scores)] # first maximum, so a tie goes to the first label
}
predicted <- sapply(seq_len(nrow(test)), function(i) classify(test[i, ]))
correct <- sum(predicted == test$label)
cat(sprintf("train_count %d\n", nrow(train)))
cat(sprintf("test_count %d\n", nrow(test)))
cat(sprintf("correct %d\n", correct))
cat(sprintf("accuracy %.6f\n", correct / nrow(test)))R reads like a description of the method. table(train$label) counts the
labels and returns them with sorted names, and which.max picks the first
maximum, so the tie rule comes for free. Comparing a column to a value gives
a logical vector, and sum() counts the TRUEs, so
sum(in_label[[f]] == row[[f]]) is a whole count in one expression. That’s
why this version keeps no count table: it recounts the matching training
rows each time it scores.
Watch the indexing. With f holding a feature name, row$f looks for a column literally
named f and returns NULL; row[[f]] uses the variable. And
colClasses = "character" stops read.csv from guessing types: a column of
T and F would come back logical. Base R has no naive Bayes classifier;
naiveBayes() lives in the e1071 package, which isn’t installed here.
# Categorical naive Bayes with add-one (Laplace) smoothing, standard library only.
# Learns P(label) and P(feature value | label) by counting training rows, then
# labels each test row with the label that has the highest log-probability.
FEATURES = %w[has_link mentions_money known_sender].freeze
LABEL = "label"
# The csv library is a bundled gem since Ruby 3.4, so split lines by hand
# (no quoted fields here) and turn each row into a hash keyed by header name.
def read_rows(path)
header, *lines = File.readlines(path, chomp: true)
names = header.split(",")
lines.map { |line| names.zip(line.split(",")).to_h }
end
rows = read_rows(ARGV[0])
train = rows.select { |row| row["split"] == "train" }
test = rows.select { |row| row["split"] == "test" }
label_counts = train.map { |row| row[LABEL] }.tally
# value_counts[[feature, value, label]] = number of training rows.
# Hash.new(0) makes missing keys count as zero.
value_counts = Hash.new(0)
train.each { |row| FEATURES.each { |f| value_counts[[f, row[f], row[LABEL]]] += 1 } }
distinct_values = FEATURES.to_h { |f| [f, train.map { |row| row[f] }.uniq.length] }
log_score = lambda do |row, label|
# Logs turn the product of probabilities into a sum, avoiding underflow.
score = Math.log(label_counts[label].fdiv(train.length))
FEATURES.each do |f|
# Add-one smoothing: an unseen value never gets probability zero.
count = value_counts[[f, row[f], label]] + 1
score += Math.log(count.fdiv(label_counts[label] + distinct_values[f]))
end
score
end
# Labels are tried in alphabetical order and max_by keeps the first maximum,
# so an exact tie goes to the alphabetically first label.
classify = ->(row) { label_counts.keys.sort.max_by { |label| log_score.(row, label) } }
correct = test.count { |row| classify.(row) == row[LABEL] }
puts "train_count #{train.length}"
puts "test_count #{test.length}"
puts "correct #{correct}"
puts format("accuracy %.6f", correct.fdiv(test.length))Ruby’s hashes do the work. tally counts the labels in one call, and
Hash.new(0) makes a counter whose missing keys read as zero. Arrays work as
hash keys, so value_counts[[f, row[f], row[LABEL]]] += 1 counts a feature,
value, and label together. max_by keeps the first maximum, so sorting the
labels first gives the tie rule.
Two things push back. Integer division truncates: 3 / 55 is 0, and
Math.log(0) is -Infinity, with no error. Every probability uses fdiv to
avoid that. And a method defined with def can’t see the script’s local
variables, so the scorer is a lambda that closes over the counts. As on
other pages, we split lines on commas by hand, because csv has been a
bundled gem rather than part of the default standard library since Ruby 3.4.
//! Categorical naive Bayes with add-one (Laplace) smoothing, standard library only.
//!
//! Learns P(label) and P(feature value | label) by counting training rows, then
//! labels each test row with the label that has the highest log-probability.
use std::collections::{BTreeMap, HashMap, HashSet};
use std::env;
use std::fs;
const FEATURES: [&str; 3] = ["has_link", "mentions_money", "known_sender"];
const LABEL: &str = "label";
/// Each row as a map from column name to value. There is no CSV parser in the
/// standard library; the file has no quoted fields, so commas suffice.
fn read_rows(text: &str) -> Vec<HashMap<&str, &str>> {
let mut lines = text.lines();
let header: Vec<&str> = lines.next().expect("empty file").split(',').collect();
lines
.map(|line| header.iter().copied().zip(line.split(',')).collect())
.collect()
}
fn main() {
let path = env::args().nth(1).expect("usage: main <data.csv>");
let text = fs::read_to_string(path).expect("cannot read data file");
let rows = read_rows(&text);
let (train, test): (Vec<_>, Vec<_>) = rows.iter().partition(|row| row["split"] == "train");
// A BTreeMap keeps its keys sorted, so the labels come out alphabetically.
let mut label_counts: BTreeMap<&str, usize> = BTreeMap::new();
// value_counts[(feature, value, label)] = number of training rows
let mut value_counts: HashMap<(&str, &str, &str), usize> = HashMap::new();
for row in &train {
*label_counts.entry(row[LABEL]).or_default() += 1;
for f in FEATURES {
*value_counts.entry((f, row[f], row[LABEL])).or_default() += 1;
}
}
let distinct_values: HashMap<&str, usize> = FEATURES
.iter()
.map(|&f| {
(
f,
train.iter().map(|row| row[f]).collect::<HashSet<_>>().len(),
)
})
.collect();
let log_score = |row: &HashMap<&str, &str>, label: &str| {
// Logs turn the product of probabilities into a sum, avoiding underflow.
let n_label = label_counts[label] as f64;
let mut score = (n_label / train.len() as f64).ln();
for f in FEATURES {
// Add-one smoothing: an unseen value never gets probability zero.
let count = value_counts.get(&(f, row[f], label)).copied().unwrap_or(0) + 1;
score += (count as f64 / (n_label + distinct_values[f] as f64)).ln();
}
score
};
let classify = |row: &HashMap<&str, &str>| {
// Labels are tried in alphabetical order, and only a strictly higher
// score replaces the best, so an exact tie goes to the first.
let mut best: Option<(&str, f64)> = None;
for &label in label_counts.keys() {
let score = log_score(row, label);
if best.is_none_or(|(_, best_score)| score > best_score) {
best = Some((label, score));
}
}
best.expect("no labels").0
};
let correct = test
.iter()
.filter(|row| classify(row) == row[LABEL])
.count();
println!("train_count {}", train.len());
println!("test_count {}", test.len());
println!("correct {correct}");
println!("accuracy {:.6}", correct as f64 / test.len() as f64);
}Rust’s two map types each do a job here. A HashMap keyed by
(feature, value, label) tuples holds every count, and
entry(key).or_default() starts a missing count at zero. Reading is
stricter: indexing a HashMap with a key that isn’t there panics, so we use
get(...).unwrap_or(0) for value-label pairs the training data never saw.
The label counts live in a BTreeMap, which keeps its keys sorted, so the
labels come out alphabetically. Only a strictly higher score replaces the
best, so an exact tie goes to the first label. The standard library has no
naive Bayes classifier, so there was no built-in to skip.
// Categorical naive Bayes with add-one (Laplace) smoothing, using only Swift's
// standard library and Foundation, which ships with it.
//
// Learns P(label) and P(feature value | label) by counting training rows, then
// labels each test row with the label that has the highest log-probability.
import Foundation
let features = ["has_link", "mentions_money", "known_sender"]
// The named column of a CSV file, as text. A function that can fail is
// marked throws, and every call to it is marked try.
func readColumn(_ path: String, _ name: String) throws -> [String] {
let text = try String(contentsOfFile: path, encoding: .utf8)
// split skips empty pieces, so a blank last line doesn't become a row.
var lines = text.split(separator: "\n")
let header = lines.removeFirst().split(separator: ",").map(String.init)
guard let index = header.firstIndex(of: name) else {
fatalError("no column \(name)")
}
return lines.map { line in
String(line.split(separator: ",", omittingEmptySubsequences: false)[index])
}
}
// A dictionary key must be Hashable. Declaring it is enough: Swift writes the
// hashing and == for a struct whose fields are all Hashable.
struct CountKey: Hashable {
let feature: String
let value: String
let label: String
}
let path = CommandLine.arguments[1]
let split = try readColumn(path, "split")
let labels = try readColumn(path, "label")
// columns["has_link"] is that whole column, one entry per row.
var columns: [String: [String]] = [:]
for f in features {
columns[f] = try readColumn(path, f)
}
let trainRows = split.indices.filter { split[$0] == "train" }
let testRows = split.indices.filter { split[$0] == "test" }
// Looking up a missing key gives nil; [key, default: 0] gives 0 instead,
// so += 1 starts a new count at zero.
var labelCounts: [String: Int] = [:]
var valueCounts: [CountKey: Int] = [:]
for i in trainRows {
labelCounts[labels[i], default: 0] += 1
for f in features {
valueCounts[CountKey(feature: f, value: columns[f]![i], label: labels[i]), default: 0] += 1
}
}
// A Set keeps one copy of each value, so its count is the number of distinct values.
var distinctValues: [String: Int] = [:]
for f in features {
distinctValues[f] = Set(trainRows.map { columns[f]![$0] }).count
}
func logScore(_ row: Int, _ label: String) -> Double {
// Logs turn the product of probabilities into a sum, avoiding underflow.
let nLabel = Double(labelCounts[label]!)
var score = log(nLabel / Double(trainRows.count))
for f in features {
// Add-one smoothing: an unseen value never gets probability zero.
let key = CountKey(feature: f, value: columns[f]![row], label: label)
let count = Double(valueCounts[key, default: 0] + 1)
score += log(count / (nLabel + Double(distinctValues[f]!)))
}
return score
}
// A dictionary's order isn't sorted and can change from run to run, so we
// sort the labels. Only a strictly higher score replaces the best, so an
// exact tie goes to the alphabetically first label.
let sortedLabels = labelCounts.keys.sorted()
func classify(_ row: Int) -> String {
var best = sortedLabels[0]
for label in sortedLabels.dropFirst() where logScore(row, label) > logScore(row, best) {
best = label
}
return best
}
let correct = testRows.filter { classify($0) == labels[$0] }.count
print("train_count", trainRows.count)
print("test_count", testRows.count)
print("correct", correct)
print("accuracy", String(format: "%.6f", Double(correct) / Double(testRows.count)))Each count is keyed by a CountKey struct holding the feature, value, and
label. A dictionary key must be Hashable, and declaring it is enough:
Swift writes the hashing and == for us. counts[key, default: 0] += 1
starts a missing count at zero, and reading with default: 0 covers pairs
the training data never saw.
A Swift dictionary has no sorted order, and its keys came out in a different order on each run, so we sort the labels before scoring. Only a strictly higher score replaces the best, so an exact tie goes to the alphabetically first label. Swift has no naive Bayes classifier, so there was no built-in to skip.
# Categorical naive Bayes with add-one (Laplace) smoothing, using only Tcl's
# built-in commands.
#
# Tcl has no classifier and no counting helper (Tcllib isn't installed), so
# we count training rows into dictionaries, then label each test row with the
# label that has the highest log-probability.
set FEATURES {has_link mentions_money known_sender}
# Returns the rows as a list of dicts, keyed by column name.
proc read_rows {path} {
set f [open $path r]
set header [split [gets $f] ,]
set rows {}
while {[gets $f line] >= 0} {
set row {}
foreach name $header value [split $line ,] {
dict set row $name $value
}
lappend rows $row
}
close $f
return $rows
}
# Reads a count, treating a key that was never seen as zero.
proc count_of {counts key} {
if {[dict exists $counts $key]} {
return [dict get $counts $key]
}
return 0
}
set train {}
set test {}
foreach row [read_rows [lindex $argv 0]] {
if {[dict get $row split] eq "train"} {
lappend train $row
} else {
lappend test $row
}
}
# label_counts: label -> rows. value_counts: {feature value label} -> rows.
# A list is a string, so a three-element list works as one dict key.
# values_seen: feature -> dict of the distinct values it takes.
set label_counts {}
set value_counts {}
set values_seen {}
foreach row $train {
set label [dict get $row label]
dict incr label_counts $label
foreach f $FEATURES {
set v [dict get $row $f]
dict incr value_counts [list $f $v $label]
dict set values_seen $f $v 1
}
}
proc log_score {row label} {
global FEATURES train label_counts value_counts values_seen
set n_label [dict get $label_counts $label]
# Logs turn the product of probabilities into a sum, avoiding underflow.
# The 1.0 matters: with two integers, / would round down to 0.
set score [expr {log(1.0 * $n_label / [llength $train])}]
foreach f $FEATURES {
set key [list $f [dict get $row $f] $label]
# Add-one smoothing: an unseen value never gets probability zero.
set count [expr {[count_of $value_counts $key] + 1}]
set distinct [dict size [dict get $values_seen $f]]
set score [expr {$score + log(1.0 * $count / ($n_label + $distinct))}]
}
return $score
}
# Labels are tried in alphabetical order, and only a strictly higher score
# replaces the best, so an exact tie goes to the first.
proc classify {row} {
global label_counts
set best {}
foreach label [lsort [dict keys $label_counts]] {
set score [log_score $row $label]
if {$best eq {} || $score > $best_score} {
set best $label
set best_score $score
}
}
return $best
}
set correct 0
foreach row $test {
if {[classify $row] eq [dict get $row label]} {
incr correct
}
}
puts "train_count [llength $train]"
puts "test_count [llength $test]"
puts "correct $correct"
puts "accuracy [format %.6f [expr {double($correct) / [llength $test]}]]"We count with dictionaries. dict incr adds one to a key and starts a new
key at 1, so label_counts needs no setup. A list is also a string, so
[list $f $v $label] works as a single dict key for each feature, value,
and label. dict get on a missing key is an error, so a small count_of
reads unseen keys as zero.
Integer division is the trap: 3 / 55 is 0, and log(0) is -Inf with
no error, so every probability multiplies by 1.0 first. Labels are tried
in lsort order, and only a strictly higher score wins, so a tie goes to
the first. Tcl has no classifier to skip; Tcllib isn’t installed.