Web Crawling in Detail and Recommender Systems

This lecture closes the crawling loop and opens recommendation. The first half follows one link from a fetched page through anchor handling, duplicate and politeness filters, normalization, distributed fetching, DNS, and the two-tier frontier, ending with how the index is split across machines. The second half asks how a store guesses what a person will like, building from the utility matrix through five recommendation paradigms into user-based and item-based neighborhood methods, content-based matching, and the hybrid stack that won the Netflix Prize.

13.1 Anchor Text and the Crawler Indexer Link

13.1.1 Where crawling meets web search

Crawling looks like a standalone job until its output flows back into the index. The fetched page text, together with its HTML tags, passes from the URL frontier path back to the indexer. Link information, including anchor text — the clickable words inside a link, written as the visible text between the opening and closing anchor tags — travels the same path. That handoff is the exact point where crawling connects to web search.

Think of the crawler as a delivery fleet and the indexer as the warehouse that shelves every delivery. Without parsing and without forwarding tokens and anchor text, crawling stays an isolated fetch loop, trucks driving with no warehouse to unload into. With the handoff, it feeds ranking, because the indexer stores both what a page says about itself and what other pages say about it. The analogy breaks at one point: delivery trucks carry boxes unchanged, while the parser transforms pages into tokens, tags, and link records before anything is stored.

The indexer keeps tag information on purpose. A term in a title or heading carries more weight than the same term buried in a footer, so the tags travel with the text. Link information travels alongside for the same reason. Anchor words are outside votes: when many independent authors point at one page with the same words, those words describe the target even when the target never uses them.

13.1.2 Four parts carried by each anchor element

For each anchor tag the crawler can pull at least four things. First, the anchor URL, which is the destination the link points to, meaning the address stored in the link target. Second, the anchor text itself, which holds the words the user sees and clicks, for example the string "learn data science". Third, the source page, which records where the link leaves from, meaning the address of the page hosting the link. Fourth, optional context, which notes where the link sits in the page, such as body or footer, plus nearby details like the words just before and after the link and whether the link sits in a navigation block or main content.

Extracting all four and passing them to the indexer sharpens later ranking, because the words other authors use to describe a page act as outside votes about that page. A page about data science may never contain the phrase "learn data science" itself, yet still earn that phrase as an index term through the anchor words of pages that point at it. Search engines give such anchor terms higher weight than ordinary body terms and can even fight spam with them, since outside descriptions are harder for one site owner to fake than on-page text.

Picture the link as a labeled arrow between two houses. The label is the anchor text, the arrowhead lands on the anchor URL, the tail sits at the source page, and the street the arrow is painted on is the context. A chart of this idea would put source on the left, target on the right, and the label on the arrow shaft. The takeaway stays fixed: the label describes the target, not the source.

13.1.3 Worked extraction of one anchor element

Concretely, suppose the tutorials page at address $p_{src}$ holds a link element pointing at address $p_{dst}$ with visible words "learn data science". The crawler emits one record with four fields: destination $p_{dst}$, text "learn data science", source $p_{src}$, and context "main body, surrounded by tutorial listing text". The indexer then does two things. It indexes the source page normally, and it adds the tokens learn, data, and science to the posting entries for the destination page $p_{dst}$ with an anchor weight. A later query for data science can therefore match $p_{dst}$ through outside words. Sense-check: the same four-part split applies to every outbound link on sites such as W3Schools, and indexers reuse the anchor words as ranking signals across tutorial and reference sites.

This outside-vote idea returns later in link analysis, where the count and wording of inbound anchors help order results. For now the working rule is plain: never drop the link record at parse time.

13.2 Three Filters Before the Frontier

13.2.1 Content seen test with shingles and fingerprints

The web holds copies of copies, so each freshly fetched page must pass a content-seen test. The rule is direct: if the page content already sits in the index, stop and process it no further. Comparison runs through document fingerprinting with shingles, which are short overlapping word chunks hashed into a compact fingerprint. A shingle (a run of several adjacent words, for example five words sliding one word at a time across the text) gives a local snapshot, and a fingerprint (a short hash built from those shingles) gives the whole page one compact signature. Two pages with matching fingerprints count as the same content.

A small picture helps. Imagine tearing a long receipt into overlapping strips five lines long, stamping a number on each strip, then keeping only a handful of stamp numbers as the receipt's signature. Two receipts with the same handful of stamps are treated as the same receipt. Where the picture breaks: tiny edits change a few strips but may leave the kept stamps untouched, so near-copies can still match, which is exactly what a crawler wants for mirror detection.

The motive is practical. Dropping known content saves indexing work and saves storage, and both savings lift overall performance. Because the test keys on content rather than address, it still catches copies that arrive under a fully different URL or with hidden changes such as tracking parameters, session identifiers, or mirrored hosts. A checksum of raw bytes would miss pages that differ by one footer line, while shingles tolerate small local changes and still flag the pair as copies.

Visualize a funnel. Fetched pages pour in at the top, the fingerprint check is the first gate, and copies fall out sideways while fresh content flows down. The horizontal axis is arrival order and the vertical drop is pages kept. The takeaway: most of the web's apparent size is repetition, so this first gate does heavy lifting.

13.2.2 URL filters and robots rules

Surviving pages face URL filters, which are simple regular expressions tuned to the task at hand. A focused crawl might accept only academic sites or only one domain, and each candidate URL must match the allowed pattern before it returns to the frontier. An inclusive rule keeps only addresses matching the wanted pattern, while an exclusive rule drops addresses matching an unwanted pattern such as a file type or a spam domain. For example, a pattern that keeps only addresses ending in an academic suffix admits lecture pages and drops store pages.

Alongside these sits the robots check: only pages the site's robots file permits are considered, and only after the duplicate checks pass. The robots exclusion file (a small text file named robots.txt placed at the root of a site that names which crawler agents may fetch which path prefixes) must be fetched and honored before the crawler touches the target page. A cached copy of that file is reused across many addresses from the same host so the crawler does not re-fetch it per URL. Honoring those permissions is an act of politeness, and it also trims wasted fetches, which adds efficiency. Compliance here is voluntary but enforced in practice: servers that see rude behavior block the crawler by address.

The order matters. Filtering by pattern is cheap and local, while robots handling needs host-level care, so both sit after the content test and before re-queuing. A URL that fails either test never re-enters the frontier.

13.2.3 Duplicate URL elimination and priority

Duplicate URL elimination removes addresses already waiting in the frontier or already crawled and parsed. Nothing already seen goes back into the queue. The check runs on normalized addresses with a fast lookup table, so an address already queued or already fetched is dropped in constant time. This is an address test, unlike the earlier content test: the same words under a new address pass this gate but were already stopped by fingerprints, while the same address seen twice is stopped here even when the words changed.

Each admitted URL draws a priority. The frontier still drains first-in first-out within its lanes, but politeness, quality, freshness, and related factors shape which URL leaves next. Quality (an estimate of how useful a page is likely to be, often from link evidence) pushes the most useful and most key pages forward. Freshness (an estimate of how fast a page changes, often from past fetch history) pushes fast-changing pages such as news items forward. Only a fresh URL, never indexed or crawled before, earns a slot, and among fresh URLs the high-quality and fast-changing ones leave first.

Picture two lanes at a toll gate. One lane holds careful, rarely changing reference pages and the other holds fast news pages. The gate lets the urgent lane through more often while still serving both. The one-sentence read is that priority decides order while elimination decides membership.

13.2.4 Student questions and answers

Several students asked the same doubt in different words, so one canonical answer covers the group.

13.3 Normalization Distributed Crawling and DNS

13.3.1 Relative URLs become absolute URLs

A page may carry a relative URL, which points sideways from the current location, such as a short path that only makes sense next to its parent page, while the frontier wants the absolute URL, which names the full parent address including host and path. A relative URL (an incomplete address resolved against the page that holds it) is cheap for authors but ambiguous for a queue. An absolute URL (the complete address that names the true target page on its own) is unambiguous and safe to share across workers.

During parsing the crawler must normalize each relative link into its absolute form and queue only the absolute form. URL normalization (the step that turns each extracted relative link into its full absolute address and tidies equivalent spellings into one canonical form) runs right after filtering and before duplicate elimination, because only canonical absolute forms can be compared for duplicates. Relative forms can sprout confusing side paths, where the same target looks like many different queue entries, while the absolute form names the true target page.

13.3.2 Host splitter and its duplicate side effect

One thread cannot crawl the web fast enough, so parallel crawling spreads fetch threads across many nodes. A host splitter routes URLs to nodes and assigns which crawler handles which host. In practice the splitter hashes or maps each host name to one worker node, so all addresses from one host go to the same worker. This new stage sits between URL filtering and duplicate deletion: each node filters locally, the splitter forwards each surviving URL to its owner node, and only then does the owner run duplicate elimination against its local frontier.

This carries one cost: duplicate deletion can no longer rest on a local fingerprint cache. Copies need not share a domain, and pages change over time, so some potential duplicates slip through and return to the frontier. The reason is structural. Fingerprints cannot be split by host the way addresses can, because the same article can live on two unrelated hosts. A lookup for a fingerprint then needs a call to another node or a partitioned store keyed by fingerprint value rather than host, and there is little repeat traffic to cache since popular fingerprints do not exist the way popular hosts do. Add change over time, which forces old fingerprints to be deleted and re-stored with the address, and the content-seen check in a distributed fleet stays weaker than in a single-process crawler.

Picture one post office sorting letters by city before delivery. Sorting by city is fast and each carrier learns local streets, but two identical letters mailed in different cities are never compared side by side. The takeaway matches the lecture warning: distribution buys speed and weakens duplicate removal, and that trade-off is worth naming outright.

13.3.3 DNS resolution bottleneck and the five attempt rule

Names that humans read must turn into IP addresses that machines fetch, and that turn is DNS resolution. The lookup is recursive and synchronous: a thread sends a request to the DNS server and waits for the reply, blocked until the right address arrives. In practice the first server contacted may call further servers, so one lookup can mean several round trips across the network lasting seconds. That wait can jam the whole head of the pipeline and add latency plus sync strain, because standard library lookups block every thread at that node until the first request completes, which threatens a fetch rate of hundreds of pages per second.

The working fix has two parts. First, cache recent host-to-address answers so repeat hosts skip the network. Politeness limits how well this works, since the crawler deliberately spaces visits to one host. Second, replace blocking waits with a custom resolver: a worker sends its request, performs a timed wait, and lets other threads run, while one dedicated listener thread watches the DNS port and wakes the right worker when its answer arrives. Give each lookup a waiting threshold, and if the server stays slow while other threads wait, stop that attempt and hand resources to another thread, then resume later.

The widely followed rule grants five attempts with a growing wait each round. Past the fifth miss, terminate that lookup and take up a new request. Concretely, the wait starts near one second and grows exponentially toward tens of seconds across the five tries, in respect of host names that genuinely take that long. Real-world: every large crawler fleet hits this same DNS wait, so the retry budget is standard operating practice rather than a corner case. It keeps one slow host from freezing a whole node while still giving slow but valid hosts a fair chance.

Visualize a phone book desk with one clerk. Callers who insist on waiting at the desk block the line. The fix is numbered tokens: take a token, step aside, and return when called, with only five calls per name before the desk moves on. The one-sentence lesson is that the crawler treats DNS as a scarce shared service with timeouts and retries, not as an instant local call.

13.4 Frontier Design and Index Partitioning

13.4.1 Polite against fresh

The frontier must serve two masters that pull in opposite directions. Politeness says do not hit one server again and again, meaning at most one open connection per host and a gap of seconds between successive visits. Freshness says revisit fast-changing pages again and again, meaning news and rapidly edited pages should be re-fetched often or their index entries go stale. A naive priority queue breaks here: it can point back at the same worn site repeatedly and burst against it, because many links on one page point to siblings on the same host, so the highest-scoring addresses cluster on one server.

The fix must hold both goals at once instead of picking one. Priority alone starves politeness, and politeness alone starves freshness. The lecture frames this as opposite masters on purpose: any design that optimizes only one side fails the other in production.

13.4.2 Mercator two tier frontier

The Mercator design splits the frontier into a front queue and a back queue. URLs flow in from the top. The front queue manages prioritization through a prioritizer and a biased selector. The back queue manages politeness, and a back queue selector hands the chosen URL to the crawler. In short, the front queue guards priority and freshness while the back queue guards politeness, and their pairing resolves the clash from the prior section.

Concretely, a prioritizer assigns each incoming URL an integer priority $i$ between $1$ and $F$ from its fetch history and change rate, with news-style fast changers scoring high, and appends it to the $i$-th of $F$ first-in first-out front queues. Each of $B$ back queues holds only addresses from a single host and stays non-empty during the crawl, with a table mapping hosts to queues. A heap entry per back queue stores the earliest time its host may be contacted again, often set to the current time plus a multiple of the last fetch time. A worker takes the heap root, waits until its time entry if needed, fetches the head URL of that back queue, then refills the drained queue from a front queue picked by a biased random choice favoring high priority. The bias is what lets urgent pages flow faster without ever bursting one host, since each back queue still releases only when its host is due.

Picture arrivals falling into stacked priority trays at the top and draining through single-host checkout lanes at the bottom, with a dispatcher that favors urgent trays but never opens two registers for the same shop at once. The axes of that sketch are priority level versus host readiness, and the takeaway is that ordering and timing live in different tiers.

13.4.3 Term partitioning and document partitioning

Crawlers and indexers work as close partners, and the index spreads over a large cluster so lookups stay fast. Two split plans dominate. Term partitioning splits by vocabulary terms and suits multi-word queries in principle, because each vocabulary slice with its postings lives on one node and a query goes only to nodes holding its terms. Document partitioning splits by documents and leans on inverse document frequency choices, because each node holds a full local index for its own document slice and every query visits all nodes with results merged at the end.

Trade-offs decide the pick. Term splits promise concurrency across different query terms but force long postings lists to travel between nodes for multi-word merging, suffer when query bursts skew load, and complicate growing indexes. Document splits trade more local disk reads for far less traffic between nodes and now dominate in practice. Their one extra chore is global statistics: a score that needs collection-wide counts such as inverse document frequency must be refreshed across nodes by background processes, since no single node sees the full collection.

A useful placement rule from the lecture pairs the two halves of the system: pages from one host may be crawled together for politeness, yet a uniform hash of addresses across index nodes spreads query work more evenly than keeping one host on one index node. High-scoring and low-scoring document slices can even be searched in tiers, consulting the weaker tier only when the strong tier returns too few matches.

13.4.4 End to end life of one page

The full path now reads as one story. A seed URL leaves the frontier and its host name resolves to an IP address, with slow lookups cut off by the retry rule. Fetch returns text plus tags plus links. Fingerprinting drops already-seen content, regular expressions plus robots rules admit only wanted URLs, and duplicate deletion drops already-queued addresses. Survivors normalize to absolute form and re-enter the frontier while page text and anchor data move to the indexer, which spreads across its cluster by term or document splits. That loop answers the opening question of how a search engine finds pages: never by blind fetching, always by polite, fresh, filtered, prioritized fetching.

Sense-check the loop against the two masters: a fast-changing news address earns high front priority yet still waits for its host's back-queue timer, so freshness advances without rudeness.

13.5 Recommender Systems and the Utility Matrix

13.5.1 Utility function definition

A recommender system estimates a utility function that predicts how much a given user will like a given item. A utility function (a scoring rule written $f(u,i)$ for user $u$ and item $i$ that returns the expected liking) is the single idea behind the whole loop: find the right scoring function, rank items by score, and show the top ranks. Daily questions such as which camera to buy, which movie to watch, which book to read, or which university to consider all resolve through this machinery. Real-world: shopping sites, ticket booking apps, travel planners, and streaming services such as MakeMyTrip, BookMyShow, Amazon, and Prime Video run recommenders on each user every day.

Think of the utility function as a personal shopper who has watched every past purchase and now scores every shelf item for one client. The mapping breaks where taste needs stated constraints rather than past behavior, which is why later paradigms add peer, content, and need signals. For now the contract is fixed: learn $f$, sort by $f$, recommend the argmax items the user has not yet seen.

13.5.2 Utility matrix and its sparsity

The utility matrix lays users on rows and items on columns, with each cell holding the rating that user gave that item. Movie columns might read Harry Potter 1, 2, 3, Twilight, and Star Wars 1, 2, 3. The striking trait is sparsity: almost every cell sits empty. Sparsity (the condition where the fraction of filled cells is near zero because no person touches more than a tiny slice of the catalog) is not a bug in collection but the nature of choice at scale.

Scale makes the point concrete.

No team can force users to rate everything they touch, so the matrix stays sparse by nature. Sparsity is also skewed: a few heavy raters fill hundreds of cells while most users fill a handful, and a few blockbusters collect thousands of ratings while most items collect almost none. Any method that needs dense rows fails here, which motivates neighborhood and factor methods that borrow strength across rows and columns.

Picture the matrix as a vast dark cinema with a few lit seats per row. The lit seats are known ratings and the dark seats are predictions to make. The takeaway: the dark seats dominate, so every method in this lecture is a strategy for guessing them.

13.5.3 Explicit ratings against implicit signals

Ratings arrive two ways. Explicit ratings ask people outright for stars, meaning recorded scores on a stated scale such as 1 to 5. Implicit ratings learn from actions instead, such as purchases, watches, or clicks, without asking for stars, meaning behavior mapped into a liking score. Behavior skews explicit scores: users rate mostly when they love or hate an item, and the quiet middle never gets scored, so the observed stars overstate extremes. The catch with implicit signals is that they capture likes far better than dislikes. Buying similar goods shows taste directly, while walking away leaves no clean low score, since a non-purchase may mean unawareness, price resistance, or dislike with no way to tell.

Both paths land in the same trap: the low end of taste stays hard to observe. Ratings are also not missing at random. People choose what to rate and what to touch, so the filled cells over-represent strong feelings and familiar items. Methods that ignore this choice process treat blanks as neutral and drift toward popular items.

13.5.4 Cold start and extrapolating the unknowns

The core hardship is filling blanks in a nearly empty matrix. The cold start problem names its sharpest form: a brand-new item has no ratings column at all, and a brand-new user, such as a first-time grocery app subscriber, brings no history at all. A cold start (the state where a new row or column has too few entries for peer or content matching to work) forces generic behavior at first. Until patterns build up, sparsity bites hardest. Real-world: a new subscriber with zero orders gets generic lists first, and only later earns tuned picks as actions accrue.

Extrapolation then means borrowing from elsewhere: popular lists and item knowledge for new users, content traits for new items, and peer neighborhoods once a few ratings land. Pure peer methods suffer most here, content methods suffer less for new items with rich descriptions, and need-based methods sidestep history entirely. That ordering previews why hybrids win.

13.6 Five Paradigms of Recommendation

13.6.1 Personalized recommendation

Personalized recommendation draws only on one person's profile and context: age, gender, zip code, country, past buys, and past ratings. The model scores all available items against that single profile and recommends the best fits to that same person. No peer data enters the picture. This is the narrowest family: one row of the matrix plus side information about that user, scored against the catalog, with no community input.

Use it when privacy or data limits rule out peer data, or when the profile alone is strongly predictive. Its limit is isolation: it can never surface a title that everyone like the user loves but the user has never touched in any form.

13.6.2 Collaborative recommendation

Collaborative recommendation asks what is most popular among peers. Peers here are not real-life friends but like-minded buyers found through network methods over community data. Picture a viewer who always watches crime thrillers while a new thriller takes off among three or four close-taste neighbors. The component then suggests that new title to the viewer even though the genre history alone would not surface it. The data fuses the person's history with the peer group's history inside the recommendation component.

The mapping is social without being friendship-based: similarity over rating rows defines the neighborhood, and the neighborhood's taste completes the target row. The analogy breaks where taste is rare: with too few like-minded raters, the peer signal thins out.

13.6.3 Content based recommendation

Content-based recommendation shows more of the same kind the user already liked. It studies item features rather than peer opinion: title, genre, cast, crew, year, and similar content traits. The model then scores fresh items by resemblance to past likes and their scores. In vector terms, liked items define a taste direction and new items are ranked by closeness to that direction, with no peer rows consulted.

This family shines for rare taste and new items with rich descriptions, and it explains itself through the winning traits. Its limit is sameness: it rarely surprises, since it stays inside the content neighborhood of past likes.

Comparison across the first three families keeps them straight. Personalized uses one profile only. Collaborative uses peer rows plus the target row. Content-based uses item traits plus the target row. When the lecture asks which family can surface an unseen genre through peer buzz, the answer is collaborative; when it asks which family needs no peer data at all, the answer is content-based.

13.6.4 Knowledge based recommendation

Knowledge-based recommendation fits items to stated needs. It draws on direct knowledge of both the requirement and the item, which suits big rare buys where past behavior says little. The egg pan story makes it concrete: a shopper hunting an omelette pan gets shown an egg boiler that cooks six or seven eggs in about fifteen minutes with one switch. The match rests on need plus item knowledge, not on peer history.

Think of a hardware clerk who asks what meal is planned and then picks the tool that fits the job, rather than asking what neighbors bought. The clerk needs a catalog of item capabilities plus a short interview about the job. Where the picture breaks: without a good needs interview or a rich item knowledge base, the clerk guesses, and so does the model.

13.6.5 Hybrid recommendation

Hybrid recommendation blends paradigms, most often collaborative plus content-based signals. Blends can score each side apart and merge the scores, or unify both signals inside one model with shared training. That blend explains the familiar shopping shock: an added pan surfaces an egg boiler that feels so fitting that the buyer wonders how life worked without it. Real-world: large stores run blended ensembles whose combined output drives those uncanny bundles, and the same blending pulls extra Lego sets into carts at prices around 3000 to 4000.

The lecture's running shock stories carry one lesson: no single signal explains the bundle. Peer history says cooks like this also bought that, content traits say the two tools share a breakfast task, and the blend outscores either side alone. Hybrids also soften cold start, since content or need signals cover rows and columns where peer data is missing.

13.6.6 Course scope and student questions and answers

This course covers the collaborative and content-based paradigms in depth. The remaining paradigms stay in view as context for hybrid designs. Personalized, knowledge-based, and hybrid ideas return as motivating cases and evaluation context, but the derivations and graded practice center on neighborhood and content methods.

The two answers above address distinct confusions, so both are kept: the first about where peer data comes from, the second about why one model cannot serve all inputs.

13.7 User Based Collaborative Filtering

13.7.1 Hypothesis and four step procedure

User-based filtering starts from one hypothesis: people who agreed in the past are likely to agree again. Tastes can shift overnight for some, but agreement on kinds of movies, books, or buys mostly holds. The assumption is stationarity of taste over the prediction window: near-term likes follow past agreement closely enough to rank unseen items.

The working loop has four steps. First, filter down to a neighborhood by listing items the target user rated, then marking other users who rated at least one of those items. Second, rank those candidates by a similarity score and keep the top K neighbors. Third, predict ratings for the target user's unrated items from neighbor ratings. Fourth, recommend the top scoring items. In the toy walkthrough the target user rated only two movies, three fellow users share at least one of them, and the weakest overlap gets dropped so two close neighbors remain.

Think of it as asking a small jury of taste twins to score what you have not seen, then weighting each juror by how often they agreed with you before. The picture breaks when the jury is thin: with one shared movie the agreement evidence is weak, and the method must say so by picking a larger overlap or more neighbors.

13.7.2 Jaccard similarity and why it fails here

Jaccard similarity counts shared occurrences while ignoring the values. Heard in class as intersection over union, it reconciles to the standard set form:

$$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$$

where $A$ and $B$ are the item sets two users rated, $|\cdot |$ counts set size, $\cap$ marks shared items, and $\cup$ marks items rated by either user. Every symbol is a count: the numerator counts movies both users rated, the denominator counts movies at least one of them rated, and the ratio lies in $[0,1]$ with $1$ for identical sets.

In the toy matrix, pair A and B share one movie and pair A and C share one movie, so both pairs score the heard value of one by seven:

$$\frac{1}{7}$$

Yet the values disagree sharply: A and B both rate Harry Potter highly with 4 and 5, which signals agreement, while Twilight draws 5 from one side and 2 from the other, which signals disagreement. Equal Jaccard scores for an agreeing pair and a disagreeing pair prove the measure blind to values, so it cannot serve here. The failure is structural, not numerical: a pure overlap count can never separate like-like from like-dislike.

13.7.3 Cosine similarity and its narrow gap

Cosine similarity uses the values through a dot product over lengths. Heard in class as dot product divided by the lengths, it reconciles to the standard vector form:

$$\cos (A,B)=\frac{A\cdot B}{\Vert A\Vert \Vert B\Vert }$$

where $A\cdot B$ sums pairwise products over co-rated items only and $\Vert A\Vert$ is the L2 length of that user's co-rated ratings. Each symbol is concrete: $A\cdot B={\sum }_{i\in I_{AB}}{a}_i{b}_i$ over the shared item set $I_{AB}$, and $\Vert A\Vert =\sqrt{{\sum }_{i\in I_{AB}}{a}_i^2}$. Scoring only co-rated entries matters because unrated cells must never turn into zeros. A zero would pose as a scored dislike and shrink both the dot product and the lengths.

The toy result gives similarity 0.38 for A and B against 0.32 for A and C. The direction is right, since 0.38 tops 0.32, but the gap stays tiny while intuition demands a wide split between agreement and direct opposition. Raw cosine sees values yet misses the baseline of agreement versus disagreement, so it also falls short as is. The reason is scale: all stars are positive numbers between 1 and 5, so any two users point into the same positive corner and their angle stays small. Two users who disagree on every shared title still get a positive cosine near the agreeing pair.

Picture two arrows from the origin into the positive quadrant. One pair points nearly together and the other pair points only slightly apart, because with no negative coordinates no pair can open a wide angle. The geometric takeaway: without centering, opposition cannot show as a negative number.

13.7.4 Pearson correlation as centered cosine

Pearson correlation centers each rating around its mean before taking the cosine-style ratio. Heard in class as centering the data and then taking the dot product over the lengths, it reconciles to the standard centered form:

$$r(A,B)=\frac{{\sum }_i(a_i-\bar{a})(b_i-\bar{b})}{\Vert a-\bar{a}\Vert \Vert b-\bar{b}\Vert }$$

where $a_i$ is user A's rating of co-rated item $i$, $\bar{a}$ is A's mean rating over the co-rated or profile set used in the lecture, and the denominator holds the L2 lengths of the centered vectors. Centering means subtracting the mean from each point, so a rating above the user's usual level becomes positive and one below it becomes negative. The ratio then lies in $[-1,1]$, with $1$ for perfect agreement, $-1$ for perfect opposition, and $0$ for no linear relation.

For the toy user with ratings 4, 5, and 1, the mean is:

$$\bar{a}=\frac{4+5+1}{3}=\frac{10}{3}$$

and the centered points follow by subtraction:

$$4-\frac{10}{3}=\frac{2}{3}$$

$$5-\frac{10}{3}=\frac{5}{3}$$

$$1-\frac{10}{3}=-\frac{7}{3}$$

Numerically, $\bar{a}=3.33$, so the centered values are about $0.67$, $1.67$, and $-2.33$. The first two sit above the user's average and read as likes, the last sits far below and reads as a dislike. Spot-check the arithmetic: $2/3+5/3-7/3=0$, as any centered set must sum to zero.

Now both sign and size speak. Pair A and B score strongly positive because likes line up with likes, while pair A and C turn negative because one side's likes are the other side's dislikes. That negative sign is the missing dissimilarity signal, and it makes the score trustworthy. Boundary check: the output always stays inside $[-1,1]$, and flipping all signs of one user flips the sign of the score, exactly as opposition should.

13.7.5 Rating prediction formula

Prediction blends neighbor ratings by similarity weight. Heard in class as similarity times neighbor rating, summed and scaled by similarity, it reconciles to the standard neighborhood predictor:

$${\hat{r}}_{a,i}=\frac{{\sum }_{b}s(a,b)r_{b,i}}{{\sum }_b|s(a,b)|}$$

where ${\hat{r}}_{a,i}$ is the predicted stars user $a$ gives item $i$, $s(a,b)$ is the similarity between user $a$ and neighbor $b$, and $r_{b,i}$ is neighbor $b$'s actual rating of item $i$. The numerator sums one product per neighbor, the denominator sums absolute similarities so opposing neighbors still count toward scale without canceling it, and the result stays on the star scale. Division only rescales the blend.

With one neighbor of similarity 1 who rated Harry Potter 2 with 5 stars, the math collapses to:

$$\hat{r}=\frac{1\times 5}{1}=5$$

so the prediction is 5. With many neighbors nothing cancels, and the weighted sum earns its keep. For example, with similarities $0.8$ and $0.4$ and neighbor stars $5$ and $3$, the prediction is $(0.8\times 5+0.4\times 3)/(0.8+0.4)=5.2/1.2\approx 4.33$, which rounds to a whole-star 4.

13.7.6 Norms zeros distance and exam tactics

Three small facts prevent most errors. First, the denominator uses the L2 norm, the square root of squared sums, computed on centered values for Pearson scores. An L2 norm (the length of a vector, written $\Vert v{\Vert }_2$ for vector $v$) and an L1 norm (the sum of absolute entries, written $\Vert v{\Vert }_1$) differ as:

$$\Vert v{\Vert }_2=\sqrt{\sum _i{v}_i^2}$$

$$\Vert v{\Vert }_1=\sum _i|v_i|$$

where $v$ is the rating vector at hand. For the centered triple $(2/3,5/3,-7/3)$, the squared sum is $4/9+25/9+49/9=78/9$, so the L2 length is $\sqrt{78/9}\approx 2.94$, while the L1 sum is $2/3+5/3+7/3=14/3\approx 4.67$. Squaring then rooting gives the L2 norm. Summing moduli instead gives the L1 norm. Keep the two apart, since Pearson needs L2 lengths.

Second, never fill blanks with zero, because zero reads as a scored rating and pollutes the math. Score only co-rated entries, which is why vector lengths differ per pair. A pair sharing three titles has three-dimensional vectors, while another pair sharing two titles has two-dimensional vectors, and that is intended.

Third, a distance measure reports dissimilarity, so flip it with similarity equals one minus dissimilarity:

$$s=1-d$$

where $s$ is similarity and $d$ is the distance on the same pair, both on a zero-to-one scale. A Manhattan distance over co-rated stars is the fast exam substitute: sum absolute star gaps, scale into $[0,1]$, then flip with $1-d$.

13.7.7 Student questions and answers

The first two doubts share the sparsity theme but ask different things, so each keeps its canonical answer: the first about zero-filling and dimensions, the second about the Jaccard tie.

13.8 Item Based Collaborative Filtering

13.8.1 Transposed matrix and shared philosophy

Item-based filtering does the same job from the other side. Transpose the utility matrix so rows become items and columns become users, then score similarity across items instead of users. The hypothesis flips with it: items that the same users scored alike in the past will be scored alike next. Centered scores stay the better input, exactly as in the user-based case, since baselines differ per item as well as per user. Sparsity hurts less here because item columns accumulate ratings across many users, so an item row in the transposed view is denser than a user row in the original view.

When asked for the difference between the two flavors, answer with the transpose plus the similarity axis, then note the shared prediction shape. User-based weights neighbor users for one target user, item-based weights neighbor items for one target item, and both divide a similarity-weighted star sum by total absolute similarity.

13.8.2 Worked prediction for user 5 and movie 1

Centering comes first. Each movie's mean is subtracted from its ratings on the shared users, so above-average entries turn positive and below-average entries turn negative. Movie totals reach 18 over 5 ratings, so the first centered entry is:

$$1-\frac{18}{5}=-\frac{13}{5}$$

Here $18/5=3.6$ is the movie mean and $1-3.6=-2.6=-13/5$ is the centered value for a 1-star rating against that mean. Matching centered values are built for the neighbor rows on the same shared users. Similarity between movie 1 and movie 3 then takes the dot product over the three shared users divided by the two L2 lengths, and the same ratio gives similarity between movie 1 and movie 6. In symbols, with shared user set $U_{1,3}$ and centered ratings $c$:

$$s_{1,3}=\frac{{\sum }_{u\in U_{1,3}}{c}_{1,u}{c}_{3,u}}{\Vert c_1\Vert \Vert c_3\Vert }$$

with the same shape for $s_{1,6}$. The denominator uses L2 lengths over the shared users only, never over blanks.

Prediction reuses the weighted blend, now over items:

$${\hat{r}}_{u,1}=\frac{s_{1,3}{r}_{u,3}+s_{1,6}{r}_{u,6}}{|s_{1,3}|+|s_{1,6}|}$$

where $s_{1,3}$ is the similarity between movie 1 and movie 3, $r_{u,3}$ is user 5's actual rating of movie 3, and the second pair mirrors this for movie 6. The numerator must use actual stars, not centered values, because the target is an actual star count. Since stored ratings are whole stars, round the result with a ceiling or floor to land on a whole-star prediction. The worked numbers confirm the earlier lesson: with two live terms nothing cancels, since the numerator holds two similarity-star products and the denominator holds two absolute weights.

Sense-check the scale: similarities stay inside $[-1,1]$, stars stay in $[1,5]$, and the weighted mean of two stars stays inside $[1,5]$, so a result like 4.2 rounding to 4 is valid while a result outside the scale would flag an error.

13.8.3 Neighbor picking rules that survive scrutiny

Neighbor quality decides the result. A neighbor with 1 star here and 5 stars there on the same user signals opposite taste and must not count as close. State the picking rule before computing: for example, demand at least three co-rated users, or score every movie pair and keep the top two. Either path is accepted when written down. The first rule guards evidence per pair, the second guards rank among pairs, and writing either one makes the grading of the steps checkable.

Compute distances only over co-rated entries, flip distance to similarity with one minus distance, and never impute zero. In symbols, $s=1-d$ on a shared zero-to-one scale. A pair sharing users 1, 9, and 11 is scored in three dimensions, while a pair sharing only two users is scored in two, and the two scores are still comparable as similarities even though their dimensions differ.

13.8.4 Student questions and answers

The first two doubts form a natural pair about finding and scoring neighbors, so they sit together with one story: rank all pairs, score each pair only on its overlap.

13.9 Content Based Recommendation

13.9.1 Item features from explicit traits and text

Content-based methods set peer data aside and model taste from item content. Features split two ways. Explicit attributes name structured traits such as genre, year, cast, and crew for a movie. A textual attribute (a word or phrase mined from titles, abstracts, or tables of contents for text goods such as books and research papers) supplies the second stream. An item feature (one measurable trait of an item, for example one genre flag or one keyword weight) is defined on first use with its symbol and a number, such as a genre flag $g=1$ for action or a keyword weight $w=0.42$ for data.

The user profile becomes the footprint of liked-item content, meaning the weighted mix of traits from items the user liked. A classifier such as naive Bayes, a support vector machine, or a neural net can learn the mapping from that footprint to future likes. A clustering option also came up for modeling taste groups: Gaussian mixture models score each point by its probability of belonging to class one, class two, or class three, and the highest probability wins the assignment, unlike hard clustering that fixes each point to one cluster by distance. In soft assignment a book can be 70 percent class one and 30 percent class two, while hard assignment would force it fully into one class.

Think of the profile as a scent trail left by past picks: new items that smell strongly of the same traits score high. The trail metaphor breaks for feel-based goods where no trait list captures the scent, which previews the limits below.

13.9.2 Worked TF-IDF book title match

A shopper opens the title "building data mining applications for CRM" and the model must rank seven candidate titles. Each title turns into a TF-IDF keyword vector, placing bought and candidate books in one shared vector space. Term frequency lifts words frequent in one title, inverse document frequency lifts words rare across titles, and their product gives the entry weight. The tokens data and mining visibly dominate the bought title's vector, so books about data mining your website and mastering data mining rise to the top, joined by the CRM technology title through the shared CRM token. Titles about marketing and customer behavior sink away. The match runs purely on content words with zero peer input, which is the whole point of the demo.

Visualize one bar chart per title with one bar per keyword. The bought chart shows tall bars for data and mining, a medium bar for CRM, and flat bars elsewhere. Winners are charts with the same tall bars, losers are charts tall where the bought chart is flat. The one-sentence takeaway is that rare shared words decide, not raw word counts.

13.9.3 Strengths and limits

Freedom from peer data is the headline strength. The method handles users with rare taste, surfaces unpopular or brand-new items, and explains itself, since the winning tokens show why a title won. A user who loves only narrow CRM titles still gets CRM titles, and a book published yesterday with a rich blurb can be recommended today with no ratings at all.

Limits bite elsewhere. Only content that encodes into sound features works well, so text goods shine while music or movie feel resist encoding. Pure content matching also sidelines the user's own past ratings signal in the sense that it never borrows peer rows, which a hybrid blend later restores by adding collaborative scores. Overspecialization is the third limit: the method stays inside the content neighborhood and rarely surprises.

13.9.4 Student questions and answers

13.10 Hybrid Models and the Netflix Prize

13.10.1 Three layer winning design

Hybrids fuse content signals with collaborative signals, either by scoring each side apart and merging or by unifying both in one model. Scoring apart means training a content scorer and a collaborative scorer separately and blending their outputs, while unifying means training one model that reads both trait and peer inputs together. The Netflix Prize story shows the payoff.

Netflix opened about six years of data with 100 million ratings from 480,000 people across nearly 18,000 movies, posting its in-house root mean square error near 0.95 and offering 1 million dollars for roughly a ten percent improvement. In standard reference form the contest released 100,480,507 ratings on a 1 to 5 star scale from 480,189 users on 17,770 movies covering late 1999 through 2005, with the in-house Cinematch baseline at RMSE 0.9514 on the quiz set and the grand-prize bar set below 0.8563, meaning a ten percent cut. The lecture's rounded figures match this standard form: near 0.95 is 0.9514, and ten percent is the drop to 0.8563, finally beaten at 0.8567 by the winners.

The lecture heard about 207,000 teams entering. Standard reports count the scale differently: roughly 51,000 contestants forming about 41,000 teams from 186 countries, with about 5,000 teams submitting valid entries. The two counts differ because registrations, contestants, teams, and submitting teams are counted separately across sources. The working picture stays fixed either way: tens of thousands of entrants chased one ten-percent gap.

The winning team heard in class under a Bellcore-like name reconciles to BellKor's Pragmatic Chaos, the merged team of BellKor with BigChaos and Pragmatic Theory, seven members in total. The contest ran from October 2006 to September 2009, almost three years rather than the heard five, with progress prizes along the way before the merged team crossed the bar in the final month.

Their design stacked three scales: a global layer for baseline effects, a latent-factor layer with matrix factorization such as SVD for regional hidden factors, and a neighborhood collaborative layer for local patterns. The global layer (standing biases for each user and each item plus the overall mean) captures who rates high and what is liked on average. The latent-factor layer (hidden taste dimensions learned by factorizing the rating matrix, often with SVD-style methods) captures regional structure such as genre or style affinities. The neighborhood layer (peer or item-neighbor corrections around the baseline) captures local exceptions such as loving one thriller but hating a close sibling. No single model won; the stack won, with blending of hundreds of predictors doing the final lift.

Picture the prediction as a three-step correction. Start from the world average, adjust for the movie and the rater, add hidden-factor affinities, then nudge for near-title exceptions. Each layer fixes what the coarser layer above it cannot see.

13.10.2 Global and local effects worked numbers

The global layer adjusts for standing biases. All movies average 3.7 stars while Sixth Sense sits 0.5 above that line, and a test user rates 0.2 below average, so the global estimate is:

$$3.7+0.5-0.2=4.0$$

where 3.7 is the overall movie mean, 0.5 is the Sixth Sense lift, and 0.2 is the user's drag. In words, start from the world mean $\mu =3.7$, add the item bias $b_{item}=+0.5$ so the title mean is $4.2$, add the user bias $b_{user}=-0.2$, and land at $4.0$. Domain check: every input and the output sit inside the 1 to 5 star range, so no clipping is needed.

The local penalty has no fixed formula in the lecture; it is a neighborhood nudge learned from similar-title ratings. Its sign is what matters: similarity to a disliked neighbor lowers the estimate, similarity to a liked neighbor raises it.

13.10.3 Student questions and answers

Exam Guidance Summary

Key Industry Applications

Anchor text from every outbound link feeds indexer ranking signals across tutorial and reference sites, where outside words describe targets better than on-page text alone and help fight spam. DNS retry budgets with about five growing waits plus host-splitter routing keep large crawler fleets moving without freezing on slow hosts or bursting polite servers.

Shopping, travel, ticket booking, grocery, and streaming platforms, including Amazon, MakeMyTrip, BookMyShow, Big Basket, Hotstar, and Prime Video, run ensemble recommenders that blend profile, peer, content, and need signals. Need-aware suggestions such as the egg boiler bundle and peer-driven picks such as newly popular thriller titles show hybrid models shaping carts and watch lists daily. The Netflix Prize setup with 100 million ratings turned global baselines, latent factors, and neighborhood signals into the standard hybrid playbook, with per-user and per-item biases plus hidden dimensions plus near-title corrections behind most modern stacks.