Text Classification with Naive Bayes and Vector Space Models

10.1 Prospective Search and Standing Queries

10.1.1 Retrospective use and prospective need

Everything learned so far about document form, term weights, and similarity can be reused for a new task. Instead of ranking documents against a query, we use the same document forms to assign a class label to each document. This contrast between retrospective versus prospective search with standing queries sets the frame for the full lecture.

Retrospective search means a query is run once against an existing collection. A user types words, the system ranks stored documents, and the job ends. Ad hoc search works this way. The collection is fixed at query time, and the answer is a ranked list.

Prospective search means the query stays active while new documents keep arriving. An analyst who must watch news about an attack by America, or an attack on America, or conflict involving Iran and America, cannot search only once. The story is still going on. The need is for a standing query that runs without end and flags each fresh article on the topic as soon as it arrives.

A standing query is much like a handwritten classifier. For each incoming document it decides relevant versus non-relevant. Google Alerts and live notification filters are common cases of this idea. The rule can start as simple Boolean logic, for example multicore AND computer AND chip, and it grows over time as new phrasing appears, for example multicore processors instead of multicore chips.

A useful picture is a mail sorting desk. Retrospective search is reaching into a full mailbag for one request. Prospective search is sitting beside the slot where new letters drop and pushing each letter into the right tray the moment it lands. The desk, the trays, and the sorting habit stay the same. Only the direction of time changes.

10.1.2 Annotated text and class labels

Prospective filtering needs annotated text. Annotated text means text where some person has already marked which documents are relevant and which are not. Each mark is a plain tag on the full document, not a score inside the text. Other names for the same idea are gold standard labels and class labels. Gold here means trusted by agreement, not made of metal.

When class labels are given in advance and the system learns from them, the study is supervised. Supervised learning means learning from items that already carry the right answer, so the system can check its guesses during training. This point was confirmed by class discussion. Spam versus no-spam mail filtering is the classic case. The system sees many mails already marked as spam or no-spam, learns red-flag signs, and then marks new mail.

The supervision habit matters because it decides what the system can learn. With labels, the system can count which words lean toward which side. Without labels, it can only group by surface likeness and hope the groups match the real need. Labels turn a vague wish into a measurable task.

Real-world use: Google Alerts is a standing query. A user defines a topic once, and the service flags each new matching page or news item over time. Personal mail sorting into folders such as bills, announcements, and family mail uses the same idea with more than two trays.

10.1.3 Spam signs as a first example

Spam detection shows what the model must notice. Red flags include words tied to money, words that press for quick action such as urgent and today, often written in capital letters, and lures tied to real estate. Suspicious links are another flag. A mail from an address never seen before in the inbox is also suspect.

An everyday comparison helps. Think of a security guard at a building door. The guard learns faces, badges, tone of voice, and the look of delivery boxes. One strange badge alone proves little. Three odd signs at once raise the alarm. Spam scoring works the same way. No single word decides. The joint weight of money words, urgent style, strange links, and unknown senders decides.

The model must learn these signs from labeled mail and then decide for each new mail whether it is spam. Training counts how often each sign appears in spam versus no-spam. Scoring adds those weights for a new mail and picks the side with more proof.

Visual habit: picture two piles of mail dots on a table. The left pile is spam, the right pile is no-spam. Each dot is one mail. Mails with money words and urgent caps drift left. Mails from known friends with plain text drift right. The middle zone holds mixed mails where one more sign tips the choice. The takeaway is that class groups form loose clouds with a gray border, not two neat boxes.

Real-world: spam versus no-spam mail filtering is the standard first use of text classification. Safe search filtering of explicit pages, language tagging of documents, and sentiment grouping of reviews into positive, negative, or neutral all reuse the same label-then-learn pattern.

10.1.4 Student Questions and Answers

10.2 Formal Task and Document Features

10.2.1 Instance, classes, and bag of words

How do we turn filing mail into math that a machine can run. The formal instance classes bag of words features view gives that math in three short lines.

A document is one item to label, written $D$. An instance space is the set of all items we may need to label, written $X$. We say $D$ belongs to $X$. The phrase in plain words was a description of an instance D that belongs to X. For text, the central choice is how to show a document, and the answer used here is to treat each document as a high-dimensional bag of words. High-dimensional means many thousands of distinct words, each one a separate axis. Bag means order is dropped and only counts are kept.

An instance space is the set of all items we may need to label. We write it as $X$. A class variable is the label we want to predict. We write it as $Y$. A bag of words is a vector that records how many times each word type appears and forgets order. A token is one running word place in a document, while a type is one distinct word in the vocabulary.

Think of a fruit stall. One fruit is the instance $D$. The stall with all fruit is the space $X$. The trays marked apple, orange, and neither are the classes $C_1,C_2,C_3$. The label stuck on the fruit is $Y$. The sorter is allowed to look at color, weight, and smell. Those looks are the features. Where the fruit analogy breaks: fruit signs are few and stable, while word signs are many thousands and shift with topic and time.

A tiny number case helps. Say the vocabulary has only three types: bank, river, money. Then $X$ is all count triples, and one document with bank twice and money once is $D=[2,0,1]$. With classes $C_1=$ finance and $C_2=$ nature, the job is to pick $Y$ in $\{C_1,C_2\}$ for that triple. Real tasks use tens of thousands of axes instead of three, but the picking habit is the same.

10.2.2 Which features can a classifier look at

Bag of words is only one source of signs. For scientific articles, useful signs include title words, author names, affiliation strings, and keyword lists. For mail, useful signs include links inside the mail, sender address, punctuation use, capitalization, and matches against known word lists.

For the classroom examples in this topic, only bag of words is used. That means the only features are the words themselves. In real tasks, all other document traits should also be used. The simplification keeps the first math and examples easy to follow. It is not advice to drop other signs in real work.

Picture a doctor folder. Body words are the nurse notes. Title, authors, affiliation, and keywords are the cover sheet with name, lab, and prior tags. A sorter who reads only the nurse notes can still do a lot. A sorter who also reads the cover sheet does better, since the cover often names the disease area in a few words.

Real-world: scientific article grouping can use title, authors, affiliation, and keywords alongside body words. Mail filtering can use links, sender address, punctuation, capitals, and word lists. Language tagging of French versus English can use short character chunks alongside word signs.

10.2.3 Student Questions and Answers

10.3 Feature Selection

10.3.1 Why keep only some words

Why carry a full sack when a small pouch holds the tools. Feature selection with chi-square and mutual information keeps the words that carry class signal and drops the rest, which cuts redundancy and noise.

Not every word matters. Using all words makes the feature set huge. A huge set raises time cost, space cost, and training time. It also keeps noise and raises the risk of overfitting.

Overfitting means the model fits training quirks that do not hold for new data. We write no symbol for it because it names a behavior. A model that memorizes a training typo as a spam sign overfits. Noise means useless or misleading variation, such as random IDs in a footer. Feature selection saves time and space, cuts training time, removes noise, and helps avoid overfitting.

The same need arose with structured tables, where rows are cases and columns are features with a class label, and where methods such as principal component analysis cut size. Text data start without a table, so features must first be named to give the data shape, and then the feature count must be cut to keep the model fast and clean.

A food analogy helps. A cook keeps salt, oil, and rice within reach and stores rare spices away. The meal still tastes right, and the counter stays clear. Feature selection does the same for words. It keeps strong topic signs on the counter and stores weak or duplicate signs away. Where the analogy breaks: a cook knows the menu in advance, while a classifier must learn from counts which words are salt and which are dust.

10.3.2 Chi-square and mutual information

Two selection methods are named for this setting. One is the chi-square measure. The other is the mutual information score. Both test strength of link under known true chances, but they score it in different ways.

In full form, with $e_t$ marking presence or absence of the word and $e_c$ marking membership or not in the class:

$$I(t,c)=\sum _{e_t}\sum _{e_c}P(e_t,e_c)\log \frac{P(e_t,e_c)}{P(e_t)P(e_c)}$$

Here $P(e_t,e_c)$ is the joint chance of the word state and the class state, $P(e_t)$ is the chance of the word state alone, $P(e_c)$ is the chance of the class state alone, and $\log$ is the natural log. When word and class meet more often than chance, the ratio inside the log is above one and adds positive weight. When they meet only at chance level, the ratio is near one and adds near zero.

Chi-square tests strength of link under known true chances. It asks whether two features share more information than chance would allow, or in plain terms whether two columns carry the same news and one is redundant. Fisher's exact test is named as another test used the same way for structured data.

These two, chi-square and mutual information, are the top two named here for measuring strength of link when true chances are taken as known. Full detail on selection is not covered further. The point to keep is that selection exists and these are two common routes. In real work, the top few hundred or few thousand words by either score often keep most of the signal while cutting most of the cost.

10.3.3 Experts, redundancy, and a body-mass example

A domain expert can name useful features, but an expert can miss links. The body-mass case makes the point. Weight and height alone look separate. A person can have many pairings of the two. Yet weight and height together form body mass index:

$$BMI=\frac{w}{h^2}$$

Here $w$ is weight as a number in mass units, $h$ is height as a number in length units, and $BMI$ is the index value. In plain words the quote was weight and height together is used to make the body mass index. If the index is kept, weight and height alone may add the same news twice. That is redundancy. The trio of weight, height, and body mass index shows redundant features in one small table: two raw columns plus one joint index where the third repeats news already held by the first two.

Take numbers. A patient with $w=70$ and $h=1.75$ gives:

$$BMI=\frac{70}{1.75^2}=\frac{70}{3.0625}=22.86$$

Here $22.86$ is the index value in mass per squared length. Once $22.86$ is stored, keeping both $70$ and $1.75$ as separate strong signs for the same health label can double-count the same body-size news. A selection test spots that overlap and drops one side.

In the same way for papers, title, authors, and keywords may overlap. With $N$ articles labeled article 1, article 2, and so on, a test can ask whether two columns move together or add fresh news. Chi-square is one test that answers that question. A word that rides along with another word adds cost without adding proof and should go.

Picture a scatter plot with weight on the x-axis and height on the y-axis. Dots form a loose upward cloud. Color the dots by high versus normal index value. The colors split along a curve, not along a straight vertical or horizontal line. The takeaway is that the joint index draws the boundary that neither single axis draws alone, so keeping all three axes double-counts one shape.

Real-world: patient table with weight, height, body mass index, and lab values shows how two raw columns can be redundant once their joint index is kept. Mail filters that keep both urgent and URGENT as separate strong signs meet the same double-count trap after lowercasing.

10.4 Three Ways to Assign Labels

10.4.1 Manual labeling by people

Who puts the first labels on the pile. Manual annotation with rule-based and learned models compared through training cost and scale gives three answers, and hand work by people is the first.

The most plain route is human labeling. With 10 news documents to place into sports, study or education, and politics, a person reads each document and drops it into the right bin. Labeling documents this way is called annotating. Annotation means a person reads an item and attaches the trusted class tag.

This route is very exact when experts do it. Yahoo early web tags were hand assigned. Radiology shows the cost. One patient magnetic-resonance scan can hold 400 to 500 slice images across side, top, and front views. An expert must view the slices and mark tumor versus no tumor. A cited charge is 20 dollars per patient for this marking work. The radiology 400 slices at 20 dollars case shows hand labels cost a lot: expert eyes give trusted tags, but each patient stack bills expert minutes.

Manual work is flawless in small doses but it cannot be scaled or generalized with ease, and it costs a lot because expert time costs a lot. Marking 10 documents looks cheap. Marking scans for a whole hospital does not. Hand labels also drift when two experts read border cases in different ways, so guides and double reads are needed for trust.

Real-world: early Yahoo topic tags were hand assigned. Radiology tumor marking on magnetic-resonance slices is still hand assigned for first training sets that later train learned models.

10.4.2 Rule-based classifiers

The second route is rules. An expert writes if-then rules over a fixed word set, and new documents follow those rules. This works like a charm while incoming data keep the same shape.

A concrete rule helps. If title holds pound or pence and body holds transfer plus fee, then mark finance scam. If sender is in the contact book and no link is present, then mark no-spam. Each rule is easy to read and easy to fix in isolation.

The weak point is change. When an unseen or rare condition arrives, the rules fail. Then all rules need rework. Rule upkeep never ends because real data always bring fresh phrasing nobody fixed in advance. Since experts charge high fees, repeated rebuilds cost a lot. Rules also clash. Two rules can fire at once with different labels, so a priority order must be added and maintained.

Rules fit small and stable sets where the word scope stays fixed and no learning model is worth training. When data are large or rules need frequent change, rules are not the best choice. A law office that routes a fixed set of form types can live on rules. A news stream with daily new names cannot.

10.4.3 Learned models and training data

The third route is learned classification models. This section links manual annotation, rule-based models, learned models, and training data in one flow. The scope here follows textbook chapter 13. The methods named for this course are Naive Bayes, Rocchio, and K nearest neighbors. Support vector machines are named but marked as not covered. Rocchio and K nearest neighbors use vector-space form. Naive Bayes uses chance.

All these methods need training data with gold-standard labels. Training uses labeled items to set model values. Testing uses unseen items to check labels. Under supervised learning, grouping with labels is called classification, not clustering. K-means is clustering, not classification, because it groups without labels. Logistic regression is noted in discussion but it fits continuous-variable form and is not the focus when labels are plain categories.

A picture used in class shows the flow. A large corpus feeds bag-of-words form plus class labels. Top-level bins include regions, industries, and subject areas. Regions split into UK and China. Industries split into poultry and coffee, among others. The model trains on the corpus and labels, then a new document is funneled into one topic bin such as a region bin, an industry bin, or a subject-area bin, including sub-region bins.

Think of school. Hand labels are a tutor marking ten essays by hand. Rules are a wall chart that says if essay holds these three phrases then grade B. Learned models are a student who reads a hundred marked essays, learns the marking habit, and then marks the next essay alone. The student still needs the tutor's first marks to learn, just as learned models still need manual annotation for training data.

Search uses show the same idea. Language tagging of French versus English, spam versus no-spam, and sentiment grouping all run text through a classifier first.

Real-world: Google News first groups articles by topic such as sports, cinema, and politics through classification, then ranks documents inside each group through search. PubMed topic routing, product review sentiment, and language routing before deeper analysis follow the same train-then-file pattern.

10.5 Naive Bayes Core

10.5.1 Bayes rule for a document

How do we turn word counts into a class bet that can be ranked. Bayes posterior with token product and MAP log priors plus smoothing gives that bet in four linked steps.

Bayesian methods learn and classify with the rules of chance. The model tells a generative story, which means a story of how the data were made. Each class has a prior chance believed before seeing proof. After seeing an item, the model gives a posterior chance.

The missing bottom term $P(D)$ is the proof or chance of the document. In plain words the quote was probability of document is removed because it is the same for all classes. The full Bayes form is:

$$P(C|D)=\frac{P(D|C)P(C)}{P(D)}$$

Here $P(D)$ is the chance of the document under all classes. Since $P(D)$ does not change when $C$ changes, it only scales values to a common base, so for ranking classes it can be left out. That is why the sign is proportional-to rather than equal. Dropping a shared scale keeps the winner the same while saving work.

10.5.2 From one document chance to a token product

A document is not one token. It is a bag with $N_D$ tokens, written $t_1,t_2,\dots ,t_{N_D}$. Here each $t_k$ is one token place in the document, $k$ is the place index from $1$ to $N_D$, and $N_D$ is the count of token places in $D$. A token place is one slot in the running text. A token type is one distinct word in the vocabulary.

The plain-words quote for the extension was considering all tokens in that document starting from first token to length number of tokens. The joint chance of all tokens needs a usable form. The step taken is a product over places:

$$P(D|C)=\prod _{k=1}^{N_D}P(t_k|C)$$

Here $P(t_k|C)$ is the chance of the token in place $k$ when the class is $C$, and the large $\prod$ sign means multiply from $k=1$ through $k=N_D$. In plain words, it is simply product of token one, token two, token three and so on. Then the posterior form becomes:

$$P(C|D)\propto P(C)\prod _{k=1}^{N_D}P(t_k|C)$$

Here the product gives how much proof the tokens add for class $C$. For sentiment work with positive, negative, and neutral classes, the same product is scored for each class, and the class with the largest value is picked. That Bayes posterior token product MAP log priors smoothing chain starts here and ends in log sums.

An N-gram view helps place this choice. A unigram uses one token at a time, written as one slot $t_k$. A bigram uses pairs such as information retrieval. A trigram uses triples such as new york city. Here only unigrams are used. Bigrams and trigrams are left out because data size would limit them. Pairs need far more counts to fill, and training text is never large enough to fill them well.

10.5.3 Highest-score rule and prior weight

The decision rule is called maximum a posteriori, shortened to MAP. Among candidate classes, pick the one most likely after weighing prior odds and token proof. The form is:

$$C_{map}=\arg \underset{C}{\max }P(C|D)$$

Here $C_{map}$ is the picked class, and $\arg \max$ means the class $C$ that gives the largest posterior value. In plain words, we pick the single most likely one after weighing both prior and token probability. Maximum likelihood by contrast picks the class with the largest token product alone and ignores the prior. MAP keeps both.

A common doubt is what happens when words give no clear sign. Take the sentence We are in Bangalore. None of its four words leans to positive, negative, or neutral. The product term is then tiny or flat, and the whole choice falls back on the prior $P(C)$. If the positive class is common in training, the sentence will be marked positive for that reason alone, not because its words earned it. The Bangalore sentence where prior decides when token proof is weak is the key warning for this rule.

The coin story makes MAP plain. A fair coin gives heads or tails with equal chance:

$$P(heads)=0.5,P(tails)=0.5$$

Five heads in a row can still be chance, so equal chance stays a fair call. After 100,000 flips all heads, the coin looks biased. Equal chance no longer fits. Maximum likelihood fits the equal-chance case where all guesses start even. MAP fits the uneven case where each guess carries its own prior weight. The fair coin versus biased coin contrast explains MAP for uneven classes: text classes are uneven, so MAP is the right rule. A news stream with 90 sports items and 10 politics items should not treat both trays as even before reading words.

10.5.4 Conditional independence between words

Scoring whole word chains straight would need one value for every combo: first token alone, first plus second, first plus second plus third, then the same starting from the second token, and so on. With papers of a few thousand words, or IEEE papers of 5000 to 10000 words, Springer papers of 2000 to 3000 words, and open archives with very long items, token counts cannot be capped. Combo counts blow up, training data fall short, and the gap is called data sparseness. Data sparseness means too many possible combos and too few training hits to fill them.

The likelihood then stays a product of single-word terms, as shown above. Training burden drops from combo counts to one count per type per class. Pair and triple links are left out for now. Later models such as bigrams add some links back at higher cost, but the unigram baseline stays because it trains fast and scores well on topics.

Picture word dots on a class tray. Without independence, the model must learn the shape of every word cluster. With independence, the model learns each word axis alone and multiplies the axes. The picture is less rich but far cheaper, and on topic tasks the cheap picture still sorts well.

10.5.5 Log sums and floating-point underflow

Multiplying many small token chances gives a still smaller number, at times near zero on a computer. That trap is called floating-point underflow. Floating-point underflow means the product is so small that the machine rounds it to zero and wipes out all word proof. If it hits, all token work is wasted because the final MAP value collapses to the prior alone.

The standard fix is the log trick. Since $\log (a\times b)=\log (a)+\log (b)$, products turn into sums. Log is monotonic, so the class with the top score stays the top class. The plain-words quote was log a times b is equal to log a plus log b. The scored form is:

$$C_{map}=\arg \underset{C}{\max }[\log P(C)+\sum _{k=1}^{N_D}\log P(t_k|C)]$$

Here $\log P(C)$ is the prior weight for the class, each $\log P(t_k|C)$ is the weight saying how good a sign that word is for that class, and the sum is the total proof score. The class with the most proof wins. In plain words, each log conditional is a weight and the prior is a weight for the class. Sums are also faster than long products. The log sum MAP score with prior plus token log weights keeps the same winner as the product form while staying in a safe number range.

A tiny number check helps. Three token chances $0.01$, $0.02$, and $0.03$ multiply to $0.000006$. Their logs add to about $-4.61+-3.91+-3.51=-12.03$. Both forms rank the same, but the sum never nears zero. With fifty such tokens, the product would vanish while the sum would sit near $-200$, still easy to compare across classes.

10.5.6 Priors, likelihoods, and Laplace smoothing

The prior in text work is a doc ratio:

$$P(C)=\frac{N_C}{N}$$

Here $N_C$ is the count of training documents in class $C$, and $N$ is the count of all training documents. In plain words, number of documents belonging to that class and total number of documents. For sentiment work with three classes, the positive prior is positive docs over all docs, and so on. A class with $30$ of $100$ docs has prior $0.3$.

The likelihood for each token uses term counts with repeat hits counted. A word seen 10 times counts as 10, not 1. The plain-words quote was total number of occurrences of terms, including multiple occurrence. The raw form is:

$$P(t|C)=\frac{T_{Ct}}{{\sum }_{t^{\prime }}{T}_{C{t}^{\prime }}}$$

Here $T_{Ct}$ is the count of term $t$ in class $C$, $t^{\prime }$ ranges over word types, and the bottom sum is all term hits in class $C$ with repeats kept. Words are also treated as positionally independent. A word counts the same in a title, abstract, or closing part. No spot gets extra weight.

Raw ratios break on unseen words. The China demo shows why. Training has a China class with words Beijing and Taipei and join and WTO. If WTO never occurs in that class, its top count is zero. Zero over anything is zero. Zero times anything is zero. One missing word then zeroes the whole document score, no matter how strong the other words are. The plain-words quote was zero multiplied by anything is going to be zero.

10.5.7 Training, testing, and cost

Naive Bayes runs in three steps. First, estimate all values from labeled text with add-one smoothing. Next, for a new document and each class, add the log prior and the log token chances. Then assign the class with the largest sum.

Purpose first: the procedure turns labeled counts into fast class scores. Inputs are labeled training documents plus the vocabulary. Outputs are priors plus likelihoods, then one label per test document. Steps in order: extract vocabulary, count documents per class for priors, convert documents to token counts, count tokens per class for likelihoods with smoothing. The rationale for each count is direct: priors need doc shares, likelihoods need word shares. Testing extracts tokens from the new document with the same token routine, scores each class by sums, and returns the max.

Training code is mostly counting. Named steps are extract vocabulary, count documents, convert documents, and count tokens. These are data-shaping and sum steps that build priors and likelihoods. Testing extracts tokens from the new document with the same token routine, scores each class by sums, and returns the max.

Time cost is linear. Training time grows with total training size because it only counts and then sets values from counts. Testing time grows with test length plus class count and relevant terms because it only sums. No quadratic term appears. That is why turnaround is fast and storage stays low. In standard notation, training is linear in collection size and testing is linear in test length times class count, which matches the vector method training cost shown later.

Real-world: fast linear training fits live filters where many mails or news items must be scored quickly. Spam folders, news topic routers, and sentiment dashboards all score streams of short items under tight time limits.

10.5.8 Student Questions and Answers

10.6 Worked China Example: Multinomial and Bernoulli

10.6.1 Multinomial setup and priors

Training has four documents. Three belong to China class, one belongs to non-China class. The test document, called document 5, holds Chinese, Chinese, Chinese, Tokyo, Japan. So Chinese occurs three times, Tokyo once, Japan once. This China multinomial Bernoulli presence absent scores case is the running number task for the lecture.

Priors use doc counts:

$$P(c)=\frac{3}{4},P(\bar{c})=\frac{1}{4}$$

Here $c$ means China class, $\bar{c}$ means non-China class, 3 is China docs, 1 is non-China docs, and 4 is all docs. In plain words the exchange was three by four and one by four. The China multinomial priors three over four with 6 over 14 likelihoods start from this split.

Vocabulary size $B$ is 6 distinct words across training: Chinese, Beijing, Shanghai, Macao, Tokyo, Japan. Total hits in China class are 8 with repeats. Total hits in non-China class are 3 with repeats. Repeats matter here because multinomial counts hits, not docs.

10.6.2 Multinomial likelihoods and posterior

For China class, Chinese hits are 5 with repeats. With add-one smoothing:

$$P(Chinese|c)=\frac{5+1}{8+6}=\frac{6}{14}$$

Tokyo is unseen in China class, Japan is unseen in China class:

$$P(Tokyo|c)=\frac{0+1}{8+6}=\frac{1}{14}$$

$$P(Japan|c)=\frac{0+1}{8+6}=\frac{1}{14}$$

For non-China class, Chinese hits are 1, Tokyo hits are 1, Japan hits are 1, with class total 3:

$$P(Chinese|\bar{c})=\frac{1+1}{3+6}=\frac{2}{9}$$

$$P(Tokyo|\bar{c})=\frac{1+1}{3+6}=\frac{2}{9}$$

$$P(Japan|\bar{c})=\frac{1+1}{3+6}=\frac{2}{9}$$

Posterior scores use prior times likelihoods, with Chinese cubed because it occurs three times in the test:

$$Score(c)=\frac{3}{4}\times (\frac{6}{14}{)}^3\times \frac{1}{14}\times \frac{1}{14}$$

$$Score(\bar{c})=\frac{1}{4}\times (\frac{2}{9}{)}^3\times \frac{2}{9}\times \frac{2}{9}$$

Step the first score down. Write $\frac{6}{14}$ as $\frac{3}{7}$ which is about $0.4286$. Cube it to about $0.0787$. Multiply by $\frac{1}{14}$ to get about $0.00562$. Multiply by the second $\frac{1}{14}$ to get about $0.000402$. Multiply by $\frac{3}{4}$ to get about 0.0003. Step the second score down. Write $\frac{2}{9}$ as about $0.2222$. Raise to the fifth power for three Chinese plus Tokyo plus Japan to get about $0.000542$. Multiply by $\frac{1}{4}$ to get about 0.0001. The first score is about 0.0003. The second is about 0.0001. The max wins, so document 5 is marked China class. Log form would give the same winner through sums, with the China sum near $-8.11$ and the non-China sum near $-8.91$ on natural logs.

10.6.3 Why China wins despite Tokyo and Japan

All three test words occur in non-China training, while only Chinese strongly marks China training. It feels natural to guess non-China. Yet the test is marked China.

The reason is weight. Chinese at 6 over 14, cubed for three hits, outweighs Tokyo and Japan at 1 over 14 each. In plain words, Chinese has been overweighing the rest of the two. The Chinese overweighing Tokyo Japan pattern explains the China win: one strong word seen three times beats two weak words seen once each. Frequency matters in the multinomial view. Repeats count, so three copies of a strong sign beat one copy each of two weak signs.

A marble bag picture helps. The China bag holds many Chinese marbles and almost no Tokyo or Japan marbles. Drawing Chinese three times in a row points to the China bag even when Tokyo and Japan each appear once. The non-China bag holds all three words in equal small shares, so its three Chinese draws look less likely. Where the picture breaks: bags assume each draw is fresh, while real words travel in fixed phrases.

10.6.4 Bernoulli view with presence only

The multinomial result can feel wrong when presence feels more key than count. The Bernoulli view answers that need. It asks whether a term occurs at least once in a document, not how many times it occurs. The plain-words quote was fraction of documents in class which contains the term at least once.

This matches the old Boolean search idea of present versus absent. Use 1 for present, 0 for absent, or true for present and false for absent. If counts matter, stay with multinomial. If presence matters, use Bernoulli. Neither is always better. The task decides.

Real-world: law search for whether a given section is present in a document fits presence-only scoring. Mail spam work and product-defect flags can also fit presence. Gene-tag search such as BRCA1 in written reports can fit presence, though presence alone does not prove disease. Review sentiment, buyer guidance, quantum-paper search where many hits of quantum or complexity raise value, and PubMed topic search fit count-based scoring.

A key behavior gap is that Bernoulli also scores absent terms. Multinomial scored only Chinese, Tokyo, and Japan because only those occur in the test. Bernoulli also scores Beijing, Shanghai, and Macao as absent from the test. In plain words, absent terms also matter to scores. The Bernoulli presence scores 4 over 5 and 2 over 3 with absent terms show this gap in numbers next.

10.6.5 Bernoulli numbers and flipped label

Priors stay the same:

$$P(c)=\frac{3}{4},P(\bar{c})=\frac{1}{4}$$

Bernoulli smoothing uses doc counts. For China class with 3 docs, the form for a word $t$ is counts of China docs holding $t$ plus one over China docs plus two:

$$P(t|c)=\frac{N_{ct}+1}{N_c+2}$$

Here $N_{ct}$ is the count of class $c$ docs holding $t$ at least once, $N_c$ is the count of docs in class $c$, the plus one is add-one smoothing, and the plus two stands for the two outcomes present or absent. In plain words, we have only two outcomes, so B is 2 for the binary case. This matches the standard form where add-one smoothing with $B=2$ covers occurrence and nonoccurrence, in direct analogy to the multinomial form with $B$ as vocabulary size. The bottom term is class docs plus two outcomes, not vocabulary size.

Chinese occurs in all 3 China docs:

$$P(Chinese|c)=\frac{3+1}{3+2}=\frac{4}{5}$$

Tokyo and Japan are absent from all 3 China docs, so each gets:

$$P(Tokyo|c)=\frac{0+1}{3+2}=\frac{1}{5}$$

$$P(Japan|c)=\frac{0+1}{3+2}=\frac{1}{5}$$

To state it cleanly, both Tokyo and Japan in China class are $\frac{1}{5}$, since neither appears in China training. Beijing, Shanghai, and Macao each occur in 1 of 3 China docs, so each gets:

$$P(Beijing|c)=\frac{1+1}{3+2}=\frac{2}{5}$$

The same 2 over 5 holds for Shanghai and Macao in China class.

For non-China class with 1 doc, Chinese, Tokyo, and Japan each occur in that 1 doc:

$$P(Chinese|\bar{c})=\frac{1+1}{1+2}=\frac{2}{3}$$

The same 2 over 3 holds for Tokyo and Japan. Beijing, Shanghai, and Macao are absent from the non-China doc:

$$P(Beijing|\bar{c})=\frac{0+1}{1+2}=\frac{1}{3}$$

The same 1 over 3 holds for Shanghai and Macao.

Final Bernoulli scores multiply prior by present-word chances and by one-minus-chance for absent words. For present words use $P(t|C)$. For absent words use $1-P(t|C)$. With this full product over both present and absent vocabulary, the same test document now scores higher for non-China class. The earlier hunch that Tokyo plus Japan should pull toward non-China comes true under presence-only scoring.

10.6.6 Student Questions and Answers

10.7 Vector Space Classification with Rocchio and Nearest Neighbors

10.7.1 Vectors and the contiguity idea

How do we sort by place instead of by chance. Vectors with contiguity plus Rocchio centroids and nearest neighbors give the place-based answer.

Documents can be drawn as vectors. Take two terms, AI and ML, as the x and y axes. Three documents hold (2, 1), (1, 3), and (3, 0). The first holds 2 AI hits and 1 ML hit. The second holds 1 AI hit and 3 ML hits. The third holds 3 AI hits and 0 ML hits. So each document is a point with one number per term. The AI ML vectors 2 1 and 1 3 with centroid gaps case starts from these three points. Cosine scores can then say which documents sit close.

Vector classification puts each labeled document as a point in that space. The contiguity idea says documents in one class occupy a connected patch of space. In plain words, documents in the same class occupy contiguous regions. If similar items form round groups and unlike groups stand apart with no overlap, lines can split the space and each patch can take one class name. A figure with China, Kenya, and UK shows three well-split patches. A new point takes the label of the patch it lands in.

Good form is required. If stop words stay, or weights are poor, like items scatter instead of grouping. Scattered points with no contiguity cannot be split cleanly, since scattered points show no round shape, lines cannot split them cleanly, and labels fail. In plain words, when the data is poorly represented, the same documents might scatter, and then there is no contiguity. Length normalization plus TF-IDF weights fix much of this scatter by putting long and short docs on one sphere before gaps are measured.

10.7.2 Rocchio centroids and boundaries

Rocchio splits space with one center per class. The center is called the centroid. Other names used are center of gravity and barycenter. It is the mean spot of that class.

A board figure shows why vector lengths vary. Documents 1 through 5 are drawn with varied arrow lengths because length normalization was not applied. Normalized vectors would all have unit length. Red marks the centroid of documents 1 to 3. Blue marks the centroid of documents 4 and 5. Purple marks new document 6. The angle from document 6 to the second centroid is smaller than to the first, so document 6 takes the second class. Angle is the natural sign, so cosine is the common pick for that angle check.

Decision lines sit halfway between centers. If A1 is a boundary point between centroid 2 and centroid 3, the gap from centroid 2 to A1 must match the gap from centroid 3 to A1. The same match holds for B1 and B2 points. In plain words, points on the line are equidistantly placed. After lines are set, each query point takes the side it falls on. For length-normalized vectors, cosine closeness and Euclidean gap rank the same way, so the text moves between gap words and cosine words without changing the pick.

Real-world: length normalization plus TF-IDF weights keeps long and short documents on fair footing before centroid gaps are measured. Without it, a long doc with many repeats would sit far from the origin and pull its centroid outward for no topic reason.

10.7.3 Rocchio steps and cost

Training loops over classes and stores only centroids. Testing scores a new vector against each centroid and returns the nearest. In plain words, compute the centroid for each and then see which is closest by taking the minimum. Purpose: replace many training points with one center per class. Inputs: labeled TF-IDF vectors. Outputs: one centroid per class plus a label rule. Steps: normalize vectors, sum by class, divide by class size, store centers. Trace on the AI ML trio: class A holds (2, 1) and (1, 3) with mean (1.5, 2.0). Class B holds (3, 0) alone with mean (3.0, 0.0). A new point (2, 2) sits nearer to (1.5, 2.0) than to (3.0, 0.0) and takes class A.

Closeness can use cosine scores or gaps. For vectors, angle is the natural sign, so cosine is the common pick. On a flat drawing the same choice looks like a gap measure. Length normalization plus cosine is the stressed pairing. Normalize lengths and assign nearest centroid label is the test habit: score cosine closeness to each centroid and take the nearest.

Time cost is linear in training and testing, like Naive Bayes. Training adds vectors per class in time linear in collection size. Testing compares the test vector to each centroid in time linear in class count times test terms. In standard form, training is linear in collection size and testing is order of class count times test types. Only lengths, sums, and means are used. No complex math appears. Accuracy gaps appear when class shapes turn complex, such as two far clusters sharing one label.

A TF-IDF plus normalized Rocchio case with yes and no classes was handed out for self work, with centroid math and a practice task. The habit is the same: normalize, average by class, score cosine to each center, pick the nearest.

10.7.4 Rocchio versus nearest-neighbor trade

Rocchio is plain and fast but weak when classes spread thinly or miss round shapes. K nearest neighbors assigns the majority label among the K closest training points. It costs more at scoring time but handles odd and non-round shapes. In plain words, it assigns the majority class of the K nearest neighbors and handles the non-spherical data. The Rocchio centroid mean and nearest centroid with TF-IDF cosine versus neighbor vote contrast is the exam one-liner for this trade.

The pick is a trade between speed and shape freedom. To keep scoring light and data shape clean, use Rocchio. To allow messy shapes and weaker pre-processing, use nearest neighbors. Rocchio needs round groups with like radii. Nearest neighbors follows local streets and bends with the data, at the price of keeping all training points and scoring each new item against them.

Choosing K adds its own cost. The elbow route plots error on the y-axis against K on the x-axis and reruns the method for many K values, at times 10 or 12 runs, before settling near a bend such as K equal to 3. If K is already given, scoring is just gap checks plus a vote. Rocchio is linear and light. Nearest-neighbor cost hinges on gap type and on K search. Plain gaps such as Manhattan stay cheap, while wider gaps raise cost. Full K search with an elbow plot over many K values adds runs. In standard form, kNN test time is linear in training size times average lengths, while Rocchio test time is linear in class count times test terms, so kNN trails badly on large training sets.

Visual: picture Voronoi cells around each training point for 1-nearest neighbor. Each cell holds points nearer to its owner than to any other. Borders are straight cuts halfway between neighbors. With K above 1, those cells merge into larger majority zones with wavy edges that follow local density. The takeaway is that kNN draws bendy local borders while Rocchio draws straight global cuts between centers.

Exam note: be ready to state the trade in one line. Rocchio is fast with centroids but needs round groups. Nearest neighbors is more flexible but slower at scoring and needs K to be set. The elbow plot of error versus K to pick K plus TF-IDF cosine with normalization are the must-show steps.

10.7.5 Student Questions and Answers

Exam Guidance Summary

No fixed mark split was given in this topic. The stress was on method know-how plus number work. Use this list as a final check before practice tasks.

• Expect prior math as $N_C$ over $N$ and smoothed likelihoods with plus one over plus $B$. Prior math $N_C$ over $N$ and smoothed likelihoods decide the label when token proof is weak, so write both steps with repeats counted.
• Expect a short number task on multinomial Naive Bayes like the China case with priors 3 over 4 and 1 over 4, likelihoods 6 over 14 with 1 over 14, and 2 over 9, ending near 0.0003 versus 0.0001. Show Chinese cubed for three hits and state that China wins in the multinomial view.
• Expect a Bernoulli contrast that counts documents not hits, uses plus 2 below for present or absent, and scores absent words through one-minus-chance terms. The Bernoulli contrast ends near 0.005 versus 0.022 with a flip to non-China. Remember $P(Chinese|c)=\frac{4}{5}$ and $P(Japan|c)=\frac{1}{5}$ as the presence-only pattern.
• Expect a one-line MAP versus maximum-likelihood contrast with the fair-coin versus biased-coin story. MAP carries prior weight for uneven classes. Maximum likelihood starts even and fits fair coins.
• Expect a Rocchio centroid definition as class mean $\mu (c)$ and a nearest-centroid choice with TF-IDF plus normalization and cosine scores. State the Rocchio centroid mean and nearest centroid with TF-IDF cosine versus neighbor vote trade in one line.
• Expect the Rocchio versus nearest-neighbor trade as speed versus shape freedom, plus elbow plotting of error versus K to pick K. Name K equal to 3 as a typical bend after runs at many K values.
• Two practice items to close on your own: rerun the Bernoulli bottom-term case with 3 docs plus 2 and 1 doc plus 2, and state the kNN test cost as linear in training size versus Rocchio test cost as linear in class count.

Key Industry Applications

• Google Alerts and live filters act as standing queries over fresh news. A topic defined once flags each new matching page without rerunning a one-off search.
• Spam versus no-spam mail filtering uses red-flag words, links, sender signs, caps, and punctuation. Money words, urgent style, strange link targets, and unseen addresses add joint weight.
• Google News groups articles into sports, cinema, politics, finance, and business before ranking inside each group. Classification first narrows the set, then ranking orders within the topic.
• Sentiment grouping of reviews into positive, negative, or neutral guides buyer advice and recommendation. Prior shares matter when review words carry weak signal, as in short neutral lines.
• Language tagging of French versus English routes documents before deeper steps. Short character and word signs give fast early splits.
• Law-section presence checks and defect flags fit presence-only Bernoulli scoring. One hit is enough to matter, so binary occurrence beats hit counts.
• Gene-tag search such as BRCA1 in written reports and anomaly flags fit presence signs, with care because presence alone does not prove disease. A tag hit routes the report for expert review rather than deciding the case.
• Quantum, complexity, and PubMed topic search where repeat hits add weight fit count-based multinomial scoring. More hits mean more proof, so frequencies stay in the score.
• Radiology tumor marking on 400 to 500 magnetic-resonance slices per patient supplies gold labels at about 20 dollars per patient, showing why hand labels cost a lot. Those hand-marked stacks seed training sets for learned models that later score new scans.
• IEEE papers of 5000 to 10000 words and Springer papers of 2000 to 3000 words show why linear training and testing matter. Counting plus sums scale to long papers where combo models would stall.