A Binary GA on De Jong's Test Functions
evolutionary computation · genetic algorithms · benchmark functions · experiments · project
My CSC 742 assignment on a binary genetic algorithm for four De Jong test functions, with 8-bit and 16-bit encodings. De Jong's original functions and how the assignment's versions differ, what the submitted GA did, its single-run results, and a rerun over thirty seeds that extends the study and shows which conclusions hold across repeated runs, with convergence curves, plots of all five functions, and the same GA on Shekel's foxholes (F5).
A Genetic Algorithm for Bin Packing
evolutionary computation · genetic algorithms · bin packing · combinatorial optimization · project
My CSC 742 assignment on a genetic algorithm that assigns items to bins, rerun and extended. What the submitted GA found and why it stopped at about four times the optimum, the lower bound and First Fit Decreasing that put those numbers in context, and a permutation encoding with a first-fit decoder that reaches the optimum on the same instances, with first fit traced on a small example and a crossover that breaks two optimal parents.
A History of Information Retrieval
information retrieval · foundations · history
The field as a sequence of problems and the ideas that answered them, from microfilm selectors to Cranfield, SMART, TREC, link analysis, learned ranking, and neural retrieval.
AlphaEvolve and LLM-Guided Evolution
evolutionary computation · genetic programming · large language models · program synthesis · AlphaEvolve · FunSearch
Evolutionary search over programs in which a large language model writes the mutations. Evolution through large models, FunSearch and its cap sets and bin-packing heuristics, and AlphaEvolve's program database, prompts, diff edits and evaluators, with its reported results stated exactly. What remains evolutionary about these systems, what the language model contributes, and their limits.
Analysis of Variance
statistics · biostatistics · hypothesis testing · analysis of variance · ANOVA · F test · multiple comparisons · Bonferroni · Tukey HSD · inference
Comparing the means of more than two groups. One-way analysis of variance derived from the partition of the sum of squares, with the F test, its relation to the pooled t-test, its assumptions and Welch's version for unequal variances; and multiple comparison procedures that find which groups differ while controlling the family-wise error rate: Bonferroni, Holm and Tukey. Worked on NHANES blood pressures in four age groups.
Arithmetic in the Integers
abstract algebra · number theory · integers · proofs
The first unit of a rings-first abstract algebra course. Division with remainder, the greatest common divisor and the Euclidean algorithm, Bezout's identity, primes and unique factorization, proved in full from the well-ordering principle, with the numbers 1729 and 1001 followed from the Euclidean algorithm to their prime factorizations.
Artificial Life Platforms
evolutionary computation · artificial life · digital evolution · open-endedness · Tierra · Avida
Systems in which evolution runs without a fitness function written by the experimenter. Tierra's self-replicating machine code and its parasites, hyper-parasites and cheaters; Avida and the evolution of the EQU logic function; Lenia's continuous cellular automata; and open-endedness, the research problem these platforms are built to study.
Asymptotic Relative Efficiency of Rank Tests
statistics · biostatistics · nonparametric methods · asymptotic relative efficiency · Pitman efficiency · sign test · Wilcoxon signed-rank test · Wilcoxon rank-sum test · Kruskal-Wallis test
How much power a rank test gives up or gains against the t and F tests, measured by the limiting ratio of the sample sizes the two tests need. The definition, the cited theorem that reduces it to a ratio of slopes, the slopes of the t, sign, signed-rank and rank-sum tests derived, the efficiencies 3/pi and 2/pi under normality, tables for other shapes, the lower bound 0.864, and the cited result for the Kruskal-Wallis test; with two worked problems that compute efficiencies in closed form.
Basic Properties of Groups
abstract algebra · groups · cancellation · inverses · laws of exponents · order of an element · direct products · proofs
The first theorems that follow from the group axioms, proved in full. Inverses are unique, cancellation holds on each side, equations ax = b and ya = b have exactly one solution, so every Cayley table is a Latin square, the inverse of a product reverses the factors, products need no parentheses, and the laws of exponents hold for all integer exponents. The order of an element controls its powers: a^k = e exactly when the order divides k, every element of a finite group has finite order, the order of a^k is n/gcd(n, k), and the order of a pair in a direct product is a least common multiple. Examples from U(9), the octagon's group D_8, Z_36 and the Rubik's cube move RU of order 105.
Basic Properties of Rings
abstract algebra · rings · units · zero divisors · Gaussian integers · proofs
The first theorems about an arbitrary ring, each proved from the axioms alone. The zero, negatives and the identity are unique; a times 0 is 0; the rules of signs, including why (-1)(-1) = 1; multiples and powers, and why (a + b)^2 has four terms for matrices; units and the uniqueness of inverses, with the units of the Gaussian integers found from the norm; the group of units and the order of inverses in a product; and zero divisors among matrices and functions. Worked problems from the course's assignment close the article.
Bayesian Inference Networks
information retrieval · probabilistic models · Bayesian networks · INQUERY
Retrieval as probabilistic inference in a network of documents, terms, query concepts, and the information need. The structure of the Turtle-Croft network, how the operators follow from link matrices, INQUERY's term belief formula, a Cranfield query propagated through the network by hand, and the model's descendants in Indri.
Binary Encoding and Gray Codes
evolutionary computation · genetic algorithms · representation · Gray code · binary encoding
How a genetic algorithm maps real-valued variables to bit strings and back. Precision and string length, decoding with worked examples, concatenating several variables, Hamming cliffs, the reflected Gray code and its conversion formulas, what Caruana and Schaffer and Whitley found about Gray coding, a 30-seed comparison on De Jong's sphere and Rosenbrock functions, and real-valued representation as the alternative.
Binary Independence Model
information retrieval · probabilistic models · ranking
The classic probabilistic retrieval model. It represents documents as sets of terms, assumes terms are independent given relevance, and turns the Probability Ranking Principle into a sum of per-term weights. The derivation step by step, the Robertson–Spärck Jones weight computed for a real Cranfield query with and without relevance judgments, and how IDF emerges.
Bloat in Genetic Programming
evolutionary computation · genetic programming · bloat · introns · parsimony
Why the programs in a genetic programming population grow without getting better. Introns, the replication-accuracy, removal-bias and search-space explanations, the size evolution equation and the crossover bias theory, and the controls used in practice (depth limits, parsimony pressure, lexicographic parsimony, the Tarpeian method, operator equalization), measured over 30 seeded runs of Koza's quartic.
BM25F
information retrieval · probabilistic models · BM25 · fields · ranking
Extending BM25 to documents with fields such as title, body, and anchor text. Why adding separate per-field BM25 scores breaks term frequency saturation, how BM25F combines weighted, length-normalized field frequencies before saturating, a worked comparison, a proof that, with one shared saturation, no weighting of summed field scores ranks like BM25F, BM25F traced on this site's own search index, and how the field weights are chosen. Worked problems on pseudo frequencies, the copied-document reading of the simple version and the rescaling of k1.
Boolean Retrieval
information retrieval · Boolean retrieval · query processing
Exact-match retrieval with AND, OR, and NOT. The Boolean model, intersecting postings lists, skip pointers, query optimization, phrase and proximity queries with positional indexes, parsing query expressions, and where Boolean search is still used.
Boolean Search in Practice
information retrieval · Boolean retrieval · legal search · web search
Where Boolean retrieval is used today and how it has been extended. Professional query languages with truncation and proximity operators, the evidence comparing Boolean and ranked search, extended Boolean and fuzzy models that grade matches, with the p-norm's limit derived and five documents ranked at several values of p, required, filter, prohibited and optional clauses in modern engines, and the implicit AND of web search. Worked problems on a Westlaw query, p-norm rankings with and without query weights, and clause-based queries.
Building an Indexing Pipeline
information retrieval · indexing · implementation · Python
The decisions inside a working indexer, stage by stage, illustrated with my first course assignment. Reading and decoding files, assigning document identifiers, tokenizing, stemming, choosing a postings representation, measuring memory, and persisting the index.
Building Fields from Irreducible Polynomials
abstract algebra · fields · finite fields · extension fields · irreducible polynomials · Kronecker's theorem · Galois fields · proofs
F[x]/(p(x)) is a field exactly when p(x) is irreducible, proved through Bezout's identity. Extension fields and Kronecker's theorem, that the class of x is a root of p(x), so every polynomial has a root in some larger field. A square root of 2 adjoined to Z_3, two constructions of the field with nine elements and an explicit isomorphism between them, its multiplication table and a generator of its nonzero elements, x^9 - x as the product of all its linear factors, the prime-power sizes of finite fields, and the 256-element field inside AES.
Cayley's Theorem
abstract algebra · groups · Cayley's theorem · permutation groups · symmetric groups · regular representation · homomorphisms · proofs
Every group is isomorphic to a group of permutations. Each row of a Cayley table is a permutation of the group's elements; the proof turns this observation into a one-to-one homomorphism g -> (x -> gx) from any group G into the symmetric group on G, so a group of order n is a subgroup of S_n. U(9) sits in S_6 as the powers of one 6-cycle; left multiplication by g splits the group into cycles all of length |g|, so it fixes nothing, its sign can be read off, and the cycle types of the octagon's group D_8 inside S_16 follow from the orders of its elements; translations for infinite groups; and smaller permutation representations, such as D_8 on 8 vertices and U(9) in S_5 but not S_4.
Clustering and the Cluster Hypothesis
information retrieval · clustering · cluster hypothesis
What document clustering is and what it is for in retrieval. Clustering as unsupervised learning, hard and soft, flat and hierarchical clustering, uses from search result clustering to cluster-based smoothing and cluster pruning, a test of the cluster hypothesis on the Cranfield collection, and worked problems.
Clustering Goodreads Reviewers
information retrieval · clustering · k-means · project
The reviewer clustering from my CSC 790 term project with James R. Brown. Four features describing each reviewer, K-means with five clusters, the clusters found, why review length shaped them, and how average rating varies with it.
Clustering Measures Corrected for Chance
information retrieval · clustering · evaluation · adjusted Rand index
The adjusted Rand index and adjusted mutual information subtract from a clustering's score what a random clustering of the same sizes would earn. The chance model and the expectation derived, both measures computed on the textbook's seventeen documents, what every external measure makes of degenerate and random clusterings, and how the measures behave on k-means clusterings of Reuters as the number of clusters grows.
CMA-ES
evolutionary computation · evolution strategies · CMA-ES · continuous optimization · covariance matrix adaptation
The covariance matrix adaptation evolution strategy as specified in Hansen's tutorial. Sampling from a multivariate normal distribution, weighted recombination, cumulative step-size adaptation, the rank-one and rank-μ covariance updates, default parameters, invariance and the link to the inverse Hessian, restarts with increasing population, and a seeded implementation measured on standard test functions and against a binary genetic algorithm.
Coevolving Soft Robots with NEAT
evolutionary computation · neuroevolution · NEAT · soft robotics · evolutionary robotics · project
My CSC 742 final project, a from-scratch NEAT that evolved the bodies and neural controllers of 5×5 voxel robots on the EvoGym Walker task. The setup, the fitness after each stage of the implementation, what the speciation and scheduler runs showed, how far single runs can support the conclusions, and what a controlled follow-up would look like. Presented as a single-run case study.
Comparing Ranking Models
information retrieval · evaluation · BM25 · TF-IDF · experiment
An experiment running Boolean retrieval, TF-IDF with cosine normalization, the Binary Independence Model, and BM25 on the Cranfield collection. Query 185 under each model, setup, results by MAP, P@10, and nDCG@10, significance tests, per-query wins and losses, tuning BM25 on separate queries, and what the comparison does and does not show.
Comparing Systems with Significance Tests
information retrieval · evaluation · statistics · significance testing
Deciding whether a difference in effectiveness is real. Why per-query variation dominates, paired tests over topics, the t-test, sign test, Wilcoxon, randomization test, and bootstrap worked step by step on one example they disagree about, a real comparison on Cranfield, how many topics are needed, multiple comparisons, and practical significance.
Comparing Two Proportions
statistics · biostatistics · hypothesis testing · proportions · two-sample test · chi-square test · contingency table · Fisher exact test · sample size · NHANES · hypertension
Whether two groups differ in the share with an outcome. The pooled two-proportion z test and the interval for the difference with the unpooled standard error, each derived; the chi-square test of a 2 x 2 table proved identical to the z test; Yates' correction and Fisher's exact test; the exact Type I error and coverage of each; and the sample size per group, from the pooled formula and checked by exact power. Worked on hypertension in young men and women from NHANES. Worked problems on tuberculin skin tests among intravenous drug users, Fisher's exact test on a table with small counts, and the sample size for comparing two age groups.
Comparison of Two Means
statistics · biostatistics · hypothesis testing · paired t test · two-sample t test · Welch test · sample size · inference
Comparing the means of two groups, the most common question in medical research. Paired and independent designs and why the design decides the analysis; the paired t-test on Student's sleep data and repeated NHANES blood pressure readings; the pooled two-sample t-test and Welch's unequal-variance test with Satterthwaite's degrees of freedom, with simulations of when pooling fails and why a preliminary F test is discouraged; and the sample size for comparing two means, including the factor of 2 and the savings from pairing.
Competitive Coevolution
evolutionary computation · coevolution · games · fitness evaluation · host-parasite
Evolution in which an individual's fitness comes from contests with other evolving individuals. Relative and absolute fitness, Hillis's sorting networks and their parasites, Axelrod's prisoner's dilemma, Rosin and Belew's competitive fitness sharing, shared sampling and hall of fame, how to schedule contests, Sims's virtual creatures, self-play in backgammon, and an experiment in which relative and absolute progress come apart.
Computing Vector Scores
information retrieval · vector space model · query processing · algorithms
Ranking a collection by cosine similarity without comparing the query with every document. Term-at-a-time scoring with accumulators, precomputed document lengths, selecting the top K with a heap, a tested implementation, both evaluation orders traced on the running example, and the shortcuts used when exact scores are too expensive, with index elimination, champion lists and cluster pruning measured on Cranfield.
Conditional Probability and the Law of Total Probability
statistics · biostatistics · probability · conditional probability · multiplication rule · chain rule · law of total probability · Bayes theorem · independence · confounding · Simpson's paradox · NHANES
How the probability of an event changes when another event is known to have occurred. The definition and its reading as a restricted population; why a conditional probability obeys the axioms; P(A | B) against P(B | A); the multiplication and chain rules, with draws without replacement; independence restated; the law of total probability as a tree and Bayes' theorem for reversing a condition; crude rates and standardization as total probability; and confounding and Simpson's paradox. Worked on obesity, diabetes, age and smoking among NHANES adults, with worked problems on conditioning on two events, reversing a condition, draws without replacement and age adjustment in both directions.
Confidence Intervals
statistics · biostatistics · confidence intervals · inference
Estimating a population mean with a stated margin of error. The confidence interval built from the sampling distribution of the mean and what its confidence level promises, checked by simulation on NHANES blood pressures; Student's t interval for the usual case where the standard deviation is estimated; one-sided bounds; and the sample size needed for a given precision.
Confidence Intervals and Coverage
statistics · biostatistics · confidence intervals · coverage · sampling distribution · NHANES
What a confidence interval for a mean is and what its confidence level promises. The interval derived from the sampling distribution of the mean, a population of 5,247 adults' blood pressures from NHANES used to draw 100 intervals and then 300,000, coverage at three confidence levels, why the 95% describes the method rather than any one interval, the price of higher confidence, and what happens to coverage when the sample is not random. Worked problems on the blood pressures of women with diabetes, the level of a given width, misses among 100 intervals and coverage from the wrong population.
Confidence Intervals for a Mean: z and t
statistics · biostatistics · confidence intervals · t distribution · Student · degrees of freedom
The interval for a population mean when the standard deviation is known (z) and when it must be estimated from the sample (t). Why substituting s for sigma breaks the z interval for small samples, Student's 1908 solution, the three facts about normal samples and the theorem on Student's ratio that give the t interval (stated here, proved in a companion article), critical values, why the divisor is n - 1, Student's own sleep-drug data worked by hand, and how well the t interval holds up for skewed populations. Worked problems on gestational ages and on a sample of two.
Confidence Intervals for a Proportion
statistics · biostatistics · confidence intervals · proportions · Wald interval · Wilson interval · Clopper-Pearson · Agresti-Coull · coverage · NHANES · hypertension
Why the textbook interval for a proportion, p-hat plus or minus z standard errors, covers the truth less often than it claims, shown by computing its coverage exactly rather than by simulation; Wilson's 1927 score interval derived by inverting the test, the Agresti-Coull interval built on its center, and the Clopper-Pearson exact interval from the binomial tails; their coverage and length compared on NHANES hypertension data and over every value of p, and what to report when no events are seen. Worked problems on post-traumatic stress disorder among 746 clinic patients, exact coverage for samples of 5, and bounds in closed form when no events are seen.
Congruence and Modular Arithmetic
abstract algebra · number theory · congruence · modular arithmetic · equivalence relations · proofs
The second unit of a rings-first abstract algebra course. Equivalence relations and the partitions they make, congruence modulo n and its classes, the integers modulo n as a number system with well-defined addition and multiplication, and which of its elements can be inverted, proved in full, with the calendar, clock arithmetic and the numbers 1729 and 1001 as running examples.
Congruence in Polynomial Rings and Field Extensions
abstract algebra · polynomials · congruence · quotient rings · fields · finite fields · extension fields · proofs
The sixth unit of a rings-first abstract algebra course. Congruence modulo a polynomial, its classes and their arithmetic, proved in parallel with congruence modulo n; the ring F[x]/(p(x)), with the complex numbers and Q(sqrt 2) as examples; the theorem that it is a field exactly when p(x) is irreducible; Kronecker's theorem that every polynomial has a root in some extension field; and finite fields, with the nine-element field built twice and the 256-element field used in AES.
Congruence Modulo a Polynomial
abstract algebra · polynomials · congruence · polynomial rings · equivalence relations · proofs
Two polynomials over a field are congruent modulo p(x) when their difference is a multiple of p(x). The definition and its three equivalent forms, the proof that congruence is an equivalence relation whose classes correspond exactly to the remainders of degree less than deg p, the rules for adding, multiplying and substituting congruences, reduction of high powers, and when a common factor can be canceled, each proved in parallel with congruence of integers.
Congruence Modulo an Ideal and Quotient Rings
abstract algebra · rings · ideals · quotient rings · cosets · prime ideals · maximal ideals · proofs
Working modulo any ideal of any ring. Congruence modulo an ideal as an equivalence relation that respects sums and products, its classes as cosets a + I, and the quotient ring R/I with its natural homomorphism, which include Z_n and F[x]/(p(x)) as special cases. A quotient of Z[x] computed by hand, a field with 25 elements beside a ring of the same size with zero divisors; prime ideals, whose quotients are integral domains, and maximal ideals, whose quotients are fields, with the prime and maximal ideals of Z, F[x], Z_n and any principal ideal domain.
Congruence Modulo n
abstract algebra · number theory · congruence · modular arithmetic · equivalence relations · proofs
Two integers are congruent modulo n when their difference is a multiple of n. The definition and its three equivalent forms, the proof that congruence is an equivalence relation with exactly n classes, the rules for adding, multiplying and raising congruences to powers, when a common factor can be canceled, and applications to the calendar, to checking multiplication by digit sums, and to polynomials with no integer roots.
Congruence-Class Arithmetic in Polynomial Rings
abstract algebra · polynomials · quotient rings · congruence classes · complex numbers · units · zero divisors · proofs
The congruence classes modulo a polynomial p(x) as a ring F[x]/(p(x)). The proof that adding and multiplying classes through representatives is well defined, rules that look reasonable and are not, the ring laws, the copy of F inside, and the class of x as a new element that satisfies p. The complex numbers as R[x]/(x^2 + 1) and Q(sqrt 2) as Q[x]/(x^2 - 2), units found by Bezout's identity, zero divisors from a reducible modulus, and two rings with sixteen elements side by side.
Constraint Handling in Evolutionary Algorithms
evolutionary computation · genetic algorithms · constrained optimization · penalty functions
How an evolutionary algorithm copes with candidates that violate constraints. Static, dynamic and adaptive penalties and the death penalty, Deb's feasibility rules for tournament selection, stochastic ranking, repair, decoders and feasibility-preserving operators, with a one-variable example of penalty exactness, Deb's rules and stochastic ranking worked through on six points, and a seeded comparison of penalty weights and Deb's rules on the benchmark problem g06.
Constraints on Term Weighting
information retrieval · vector space model · term weighting · axiomatic analysis · ranking
The axiomatic analysis of term weighting. The six formal constraints of Fang, Tao, and Zhai (2004) that a reasonable retrieval function should satisfy (TFC1, TFC2, TDC, LNC1, LNC2 and TF-LNC), stated precisely with their later revisions, what the published analyses found for pivoted normalization, Okapi and the Dirichlet prior, and an analysis of this topic's own schemes: raw and sublinear TF-IDF sums, cosine normalization, and pivoted cosine normalization, each proved or refuted and tested by a seeded script.
Cooperative Coevolution
evolutionary computation · coevolution · decomposition · large-scale optimization · multiagent learning
Solving a problem by evolving its parts in separate populations that are scored together. Potter and De Jong's architecture and their CCGA, choosing collaborators and assigning credit, relative overgeneralization in the climbing game, random and differential grouping for large-scale optimization, and the link to neuroevolution through SANE and ESP, with experiments on separable and rotated functions.
Cosets and Lagrange's Theorem
abstract algebra · groups · cosets · Lagrange's theorem · index · Euler's theorem · Fermat's little theorem · orbit-stabilizer · proofs
The translates gH of a subgroup H split a group into pieces of equal size. Left and right cosets in the octagon's group D_8, where they differ, and in Z_36, where they are congruence classes; congruence modulo a subgroup and the index. Lagrange's theorem that the order of a subgroup divides the order of a finite group, and its corollaries: element orders divide the group order, groups of prime order are cyclic, and Euler's and Fermat's theorems. The converse fails in A_4; orbit-stabilizer and the Rubik's cube group. Worked problems on cosets in U(16), S_5, a cyclic group of order 15 and Z_6 x D_3, and on the subgroups of Z_12.
Cosets, Normal Subgroups and Quotient Groups
abstract algebra · groups · cosets · Lagrange's theorem · normal subgroups · quotient groups · first isomorphism theorem · proofs
The tenth and last unit of a rings-first abstract algebra course. The cosets of a subgroup split a group into pieces of equal size, which proves Lagrange's theorem that the order of a subgroup divides the order of a finite group, with Euler's and Fermat's theorems and the orbit-stabilizer relation as corollaries. Cosets can be multiplied exactly when the subgroup is normal, closed under conjugation, and then they form the quotient group G/N; the first isomorphism theorem identifies the quotient by a kernel with the image, and splits the order of the Rubik's cube group into cubie arrangements and orientations. The unit closes the course by comparing quotient rings and quotient groups.
Cosine Similarity
information retrieval · vector space model · cosine similarity · ranking
Measuring how alike two term vectors are by the angle between them. Documents and queries as vectors, why angle works better than distance, the dot product and length normalization with a proof that the ratio is a cosine in any number of dimensions, the running example scored step by step, cosine against dot product and distance for vectors that are not normalized, an interactive weighting demo, worked comparisons of three novels, scoring queries, and the cosine of random directions in many dimensions.
CPPNs and HyperNEAT
evolutionary computation · neuroevolution · indirect encoding · CPPN · HyperNEAT · generative encoding
Indirect encodings for neuroevolution. Compositional pattern-producing networks build images and other patterns by composing simple functions of coordinates, and HyperNEAT reads such a network as the connection pattern of a much larger neural network laid out in space. Activation functions and the regularities they produce, Picbreeder, substrates, scaling to higher resolution without further evolution, ES-HyperNEAT, and the cost of a bias toward regularity.
Crawler Architecture
information retrieval · web crawling · architecture
The modules of a web crawler and how URLs flow between them. Fetching and DNS resolution, parsing, URL normalization, filtering and duplicate URL elimination, the content-seen test, and the URL frontier with its priority and politeness queues, illustrated by a crawl of this site. How priorities are chosen: crawl ordering by links seen so far, and focused crawling. Worked problems on normalization, fingerprint collisions and the frontier trace.
Crossover and Mutation Operators
evolutionary computation · genetic algorithms · crossover · mutation · representation
The standard variation operators for bit strings, real-valued vectors and permutations. One-point, two-point and uniform crossover and how often each breaks up groups of genes; bit-flip mutation at rate 1/L; arithmetic, linear and blend crossover, simulated binary crossover and polynomial mutation; PMX, order crossover, cycle crossover and permutation mutations, each with a worked example; and a seeded experiment on how the mutation rate shapes a run.
Crude Rates and Their Precision
statistics · biostatistics · epidemiology · rates · mortality · crude rate · age-specific rate · Poisson distribution · confidence intervals · exact Poisson limits · rate ratio · vital statistics
What a crude death rate is made of and how far it can be trusted. Crude, age-specific and cause-specific rates, and the crude rate proved to be a population-weighted average of age-specific rates; the Poisson model for a count of deaths, the standard error of a rate, and exact gamma limits for small counts, with the Poisson-gamma identity and their coverage proved; the NCHS rule of 20 deaths; and the comparison of two rates by their difference and their ratio. Worked on 2021 deaths in Maine and Alaska and U.S. deaths by age from CDC WONDER.
Descriptive Statistics
statistics · biostatistics · descriptive statistics · levels of measurement · histogram · box plot · mean · median · standard deviation · NHANES
Describing data before drawing inferences from it. What kind of measurement each variable is (nominal, ordinal, discrete or continuous) and which summaries respect it; frequency tables, bar charts, histograms, frequency polygons, the empirical distribution function, box plots and scatter plots, and the ways graphs mislead; and the mean, median, mode, range, interquartile range, variance and standard deviation, with their properties proved and their behavior under skewness and errors shown on NHANES 2017-2018 blood pressures, heights and self-rated health.
Designing a Modular Search Engine
information retrieval · software design · search engines · implementation
How to structure a search engine so that its components can be replaced, compared, and tested independently. Interfaces for analysis, indexing, and ranking, a working Python sketch, lessons from my course project code, and the course project worked in full (layout, command-line shell, a BM25 ranker checked against this site's engine, and a test scaffold).
Dictionary Compression
information retrieval · indexing · compression · dictionary · front coding
Storing the dictionary of an inverted index compactly enough to keep it in memory. Fixed-width entries, the dictionary as a string, blocked storage and front coding, with the sizes of each layout for RCV1 and for the Reuters-21578 vocabulary, a front-coded block decoded, and a worked exercise on block size.
Dihedral Groups
abstract algebra · groups · dihedral groups · symmetry · rotations · reflections · generators and relations · Cayley tables · proofs
The symmetries of a regular polygon with n sides form the dihedral group D_n of order 2n, n rotations and n reflections. Labeling the vertices by the integers modulo n turns every symmetry into a map x -> x + k or x -> k - x, which proves the count, gives the relations r^n = s^2 = 1 and sr = r^(-1) s, and reduces every calculation to arithmetic modulo n; how a reflection reverses rotations and a rotation turns mirror lines, the Cayley table of D_8, the octagon's group, orders of rotations and reflections and how many elements have order 2, which mirror lines pass through vertices, products of reflections, matrices, and the cycle types of D_n as permutations of the vertices.
Direct Standardization
statistics · biostatistics · epidemiology · age adjustment · direct standardization · directly standardized rate · standard population · confounding · Simpson's paradox · confidence intervals · gamma distribution · mortality · vital statistics
Removing the effect of age structure from comparisons of death rates. The directly standardized rate as a weighted average of age-specific rates, worked on U.S. deaths in 2007 and 2013, when every age-specific rate fell and the crude rate rose; a proof that lower rates at every age give a lower adjusted rate under any standard; the 2000 U.S. standard and other standards, and how the choice changes a trend; the variance of an adjusted rate and the Fay-Feuer gamma interval, with coverage checked on small simulated populations. Opens with the crude and age-adjusted death rates of Maine, Alaska, Florida and Utah in 2021.
Discounted Cumulative Gain and nDCG
information retrieval · evaluation · nDCG · graded relevance
A ranked measure for graded relevance. Gains for each relevance grade, logarithmic discounts by rank, normalization by the ideal ranking, traced rank by rank on a worked example with both gain formulas, why the logarithm's base cancels, how the gain formula and graded judgments can reverse a comparison, results on Cranfield, and the measure's pitfalls.
Distributed Crawling and Connectivity Servers
information retrieval · web crawling · distributed systems · link analysis
Crawling the web with many machines. Dividing hosts among crawler nodes, exchanging URLs, keeping duplicate detection consistent, and handing the crawl to distributed indexing, followed by connectivity servers, which store the web's link graph compactly enough to answer link queries quickly. Worked problems, including the course text's exercises on host partitioning and reference encoding.
Divisibility and the Euclidean Algorithm
abstract algebra · number theory · greatest common divisor · Euclidean algorithm · Bezout's identity · proofs
Divisibility and its basic laws, the greatest common divisor, and Euclid's method of finding it by repeated division, with proofs that it stops and that it is correct. Bezout's identity, that the gcd is a combination of the two numbers, proved through the extended Euclidean algorithm; the integer combinations of two numbers as the multiples of their gcd; relatively prime integers and cancellation; solving linear equations in integers; and Lamé's bound on the number of steps, with Fibonacci numbers as the worst case.
Enterprise, Personal, and Product Search
information retrieval · enterprise search · personal search · e-commerce search
Three settings where web search methods transfer poorly. Enterprise search with access control and few links, personal search for items people already know exist, and product search over structured catalogs ranked toward a purchase.
Equivalence Relations and Partitions
abstract algebra · equivalence relations · partitions · sets · rational numbers · proofs
How mathematics makes "treat these as the same" precise. Relations and the reflexive, symmetric and transitive properties, relations that have only two of them, equivalence classes and the proof that they split a set into disjoint pieces, the matching between equivalence relations and partitions, functions that sort a set, the rational numbers built as classes of pairs of integers, and what it means for a definition on classes to be well defined.
Escaping Local Optima
evolutionary computation · local search · optimization · simulated annealing · tabu search
How local search gets past the first local optimum it reaches. Sideways moves, random restarts and their expected cost, simulated annealing and the logarithmic cooling result of Geman and Geman and of Hajek, tabu search, iterated local search, and populations, compared at equal evaluation budgets on a 100-city TSPLIB instance.
Evaluating Classifiers
information retrieval · text classification · evaluation
How to measure a text classifier. Per-class precision, recall, and F1 and why accuracy misleads, micro- versus macro-averaging computed step by step on Reuters, the precision-recall trade-off as the decision threshold moves, confusion matrices for multiclass problems with a Reuters example, the baselines a result must beat, cross-validation, and why classifiers must be tested on documents they were not trained on, with the size of the difference measured on Reuters.
Evaluating Clusterings
information retrieval · clustering · evaluation
How to tell whether a clustering is good. Internal criteria and their limits, with the silhouette worked on six points, and the external criteria purity, normalized mutual information (with its bounds proved), homogeneity, completeness and the V-measure, the Rand index and the F measure, each computed step by step on the textbook's worked example, with worked problems on doubling the collection, subdividing clusters, and exchanging clusters with classes. The measures corrected for chance are in a companion article.
Evaluating Ranked Results
information retrieval · evaluation · precision · recall · ranking
Measures for rankings rather than sets. Precision and recall at each rank, the sawtooth precision-recall curve, interpolated precision traced step by step and the 11-point average, averaged curves on Cranfield, precision at k and its ceiling, R-precision and the break-even point, reciprocal rank, and why ROC curves are rarely used in retrieval, all on one worked ranking, with an interactive demo.
Evaluating Topic Models
information retrieval · topic modeling · evaluation · coherence
How to tell whether a topic model is good, and how many topics to use. Held-out likelihood and perplexity, human judgments of interpretability, automatic coherence measures such as NPMI, and how perplexity and coherence disagreed about the number of topics in Reuters.
Evolution Strategies
evolutionary computation · evolution strategies · continuous optimization · CMA-ES
Evolutionary optimization of real-valued parameters by adapting the mutation distribution itself, from the (1+1)-ES and the 1/5 success rule to self-adaptation, CMA-ES, and natural evolution strategies.
Evolutionary Neural Architecture Search
evolutionary computation · neuroevolution · neural architecture search · hyperparameter optimization · experiments
Using evolution to design deep networks. The architecture search problem, large-scale and regularized (aging) evolution and their comparison with reinforcement-learning search, weight sharing, what random-search baselines did and did not show, population-based training, and an experiment comparing aging evolution, non-aging evolution and random search on the NAS-Bench-101 table.
Evolutionary Robotics
evolutionary computation · evolutionary robotics · soft robotics · reality gap · neuroevolution · morphology
Evolving robot controllers and bodies. Controllers evolved on real robots, Sims's virtual creatures, the reality gap and Jakobi's minimal simulations, robots fabricated from simulation (GOLEM and multi-material soft robots), voxel-based soft robots and EvoGym, the 2020 reconfigurable organisms built from frog cells, the difficulty of co-optimizing morphology and control, and embodied evolution. With a small seeded experiment on transferring an evolved gait.
Evolved Designs in Engineering
evolutionary computation · engineering design · evolvable hardware · scheduling · surrogate models · Bayesian optimization
Engineering artifacts designed by evolutionary search and what made each possible. The NASA ST5 antenna, Keane's vibration-isolating satellite booms, Thompson's FPGA tone discriminator, university timetabling at Napier, wing and compressor-blade optimization, and an honest account of where evolutionary methods are and are not the right tool, with surrogate-assisted evolution, Bayesian optimization, and a small budget experiment.
Evolving Neural Network Weights
evolutionary computation · neuroevolution · neural networks · competing conventions · genetic algorithms
Neuroevolution with the network's structure fixed and only its weights evolved. Encoding a network as a vector of weights, a seeded genetic algorithm on a 2-2-1 XOR network compared with mutation alone and with random search, the competing conventions problem shown by crossing a network with a permuted copy of itself, the cooperative neuron-level methods SANE and ESP, and the recent evidence on when weight evolution competes with gradient-based training.
Feature Selection
information retrieval · text classification · feature selection · mutual information
Choosing which terms a classifier should use. Why to select features, mutual information and the χ² statistic derived from their definitions to formulas in four counts, with the bounds on mutual information proved, both computed cell by cell for Reuters terms and on the textbook's example, frequency-based selection, the terms each method picks for a Reuters category and why χ² prefers rarer ones, how selection affects accuracy on Reuters, an experiment showing why mutual information does badly with a multinomial classifier, and the pitfalls of selecting features on test data.
Fermat's Little Theorem
abstract algebra · number theory · modular arithmetic · Fermat's little theorem · Euler's theorem · primality testing · Carmichael numbers · proofs
Powers modulo a prime. Fermat's little theorem with the proof that multiplying by a unit rearranges the units, the form a^p = a for every integer, reducing exponents modulo p - 1, inverses as powers, the order of an element, square roots of -1, Euler's theorem for any modulus, combining congruences for relatively prime moduli, phi(pq), and the theorem as a primality test, with pseudoprimes, Carmichael numbers such as 1729, Korselt's criterion, and the strong test that repairs it, with worked problems from the course's assignment.
Finding Similar Documents
information retrieval · vector space model · cosine similarity · implementation · performance
Comparing every pair of documents in a collection with cosine similarity. Why the problem is quadratic, three implementations and their benchmarks from my course assignment, sparse matrices, inverted-index methods that skip pairs sharing no terms, how many pairs share a term in the 10,788 stories of the Reuters-21578 subset distributed with NLTK, what the weighting changes on a four-document example, the assignment solved on that example, and approximate methods for very large collections.
Fitness Landscapes
evolutionary computation · optimization · search · theory
Wright's adaptive landscape and how evolutionary computation reuses it. Neighborhoods defined by the variation operator, local optima and basins, neutrality, ruggedness and epistasis in Kauffman's NK model, deceptive trap functions, and fitness-distance correlation, measured with a (1+1)-EA on OneMax, a trap, a block function, and NK problems, with the NK autocorrelation derived and an interactive NK explorer.
Foundations of Evolutionary Computing
evolutionary computation · optimization · search
What evolutionary algorithms are, where they came from, which parts of biology they borrow, how the structure of a problem shapes their search, and what they cannot promise.
Foundations of Information Retrieval
information retrieval · search engines
What retrieval systems are for, why the problem is hard, where the field came from, and how a search engine is put together.
Freshness and Recrawling
information retrieval · web crawling · freshness
Keeping a crawled collection current as pages change. Modeling page changes as a Poisson process, deriving expected freshness and age step by step, why revisiting pages in proportion to how often they change is worse than revisiting them uniformly, the optimal revisit rates found with a Lagrange multiplier, and how conditional requests, sitemaps, and notifications make recrawling cheaper. The estimate of a page's change rate from detected changes, and worked problems.
From Bytes to Documents
information retrieval · text processing · character encoding · document units
The first stage of text processing. Decoding bytes into characters, identifying file formats and extracting their text, identifying languages, and deciding what counts as a single document.
Genetic Algorithms
evolutionary computation · optimization · genetic algorithms
Populations of encoded candidate solutions improved by selection, crossover, and mutation, from Holland's simple genetic algorithm to the encodings, operators, selection schemes, and constraint handling that make it work in practice.
Genetic Programming
evolutionary computation · genetic programming · program synthesis
Evolving computer programs instead of parameter vectors, from Koza's program trees to symbolic regression, the problem of bloat, and linear, graph, and grammar-based representations.
Genetic Programming Beyond Trees
evolutionary computation · genetic programming · representation · neutrality · program synthesis
Four ways to represent evolved programs other than as trees, each decoded by hand on the same expression. Linear GP on register machines and its effective and non-effective code; Cartesian GP's graph genome, active nodes and neutrality; grammatical evolution's codon mapping, wrapping and the locality criticism; stack-based Push programs; what Koza's list of human-competitive results and the Humies do and do not show; and how LLM-guided program search relates to all of this.
Group Homomorphisms and Isomorphisms
abstract algebra · groups · homomorphisms · isomorphisms · kernels · cyclic groups · automorphisms · conjugation · proofs
Maps between groups that respect the operation. Examples from the sign of a permutation, the rotation-or-reflection sign of a dihedral symmetry, reduction modulo n, powers of a fixed element and the vertex permutations of the octagon, and maps that fail; first properties, proved in full; the kernel, a subgroup that decides when a homomorphism is one-to-one; homomorphisms out of a cyclic group and how to count them; isomorphisms and the properties they preserve, used to sort five groups of order 16 and to identify U(32) with Z_2 x Z_8; the classification of cyclic groups as Z and Z_n; and conjugation as an automorphism.
Groups
abstract algebra · groups · dihedral groups · Rubik's cube · symmetric groups · permutations · symmetry · proofs
The ninth unit of a rings-first abstract algebra course. A group is a set with one associative operation, an identity and inverses; examples from rings (Z_n under addition, groups of units such as U(9) and GL_2(R)) and from symmetry, with the dihedral groups of the regular polygons, the Rubik's cube group of order 43,252,003,274,489,856,000, and the symmetric groups of permutations, with cycle notation and parity. The general theory follows: cancellation and the order of an element, subgroups and cyclic groups with the subgroup lattices of Z_36 and D_8, homomorphisms and isomorphisms with the classification of cyclic groups, and Cayley's theorem that every group is a group of permutations.
Groups: Definition and First Examples
abstract algebra · groups · group axioms · abelian groups · groups of units · permutations · symmetry · Cayley tables · direct products · proofs
The definition of a group, a set with one associative operation, an identity and inverses, and the first catalog of examples. Every ring is a group under addition, and the units of a ring with identity form a group under multiplication, which gives the integers modulo n, the units U(n), the Gaussian units and the invertible matrices; the bijections of a set form a group under composition, which gives permutations and symmetries; roots of unity, a group built from a new operation on the reals, Cayley tables, direct products, the order of an element, and systems that fail to be groups.
Hierarchical Clustering
information retrieval · clustering · hierarchical clustering · algorithms
Building a tree of clusters by repeatedly merging the two most similar. The agglomerative algorithm traced by hand under single, complete, average, and centroid linkage, dendrograms and where to cut them, chaining and outliers, what the method costs, and a comparison with k-means on 30 samples of Reuters news stories. With a bisecting k-means trace and a worked exercise on the optimality of the tree. The proofs of the linkages' properties are in a companion article.
Hill Climbing
evolutionary computation · local search · optimization · algorithms
Local search on a neighborhood, specified completely in its four standard forms (first-improvement, steepest-ascent, stochastic, and first-choice), with the cost of a step weighed against the number of steps on a 100-city tour, the ways hill climbing gets stuck, and the (1+1) EA read as a hill climber with a global mutation operator.
Hill Climbing on 8-Queens and the 8-Puzzle
evolutionary computation · hill climbing · local search · 8-queens · 8-puzzle · course work
The first CSC 742 assignment rebuilt as a reproducible experiment. Steepest-descent hill climbing solves 14% of random 8-queens boards and 94% with sideways moves, matching Russell and Norvig, while on the 8-puzzle it almost always stalls, and an exhaustive count of all 181,440 puzzle states shows why.
History of Evolutionary Computation
evolutionary computation · foundations · history · genetic algorithms · evolution strategies
How evolutionary computation grew from separate answers to separate problems. Turing's genetical search, Box's evolutionary operation, Fraser's genetic simulations, Friedberg's program-writing machine and Bremermann's optimization; evolution strategies in Berlin, evolutionary programming in San Diego, genetic algorithms in Ann Arbor and genetic programming; the merger of these schools in the 1990s; and the field today.
HITS: Hubs and Authorities
information retrieval · link analysis · HITS · hubs and authorities · web search
Kleinberg's hyperlink-induced topic search. The root set and base set built for one query, the mutually reinforcing hub and authority updates, the proof that the rescaled iteration converges to principal eigenvectors of MᵀM and MMᵀ and what happens when the largest eigenvalue is repeated, the link to the singular value decomposition, the five-page web computed to convergence, and the comparison with PageRank: query dependence, topic drift, the tightly knit community effect, and SALSA.
Holland's Schema Theorem
evolutionary computation · genetic algorithms · theory · schemata
Holland's account of why a genetic algorithm works. Schemata, their order and defining length, the schema theorem for the simple genetic algorithm stated as a lower bound on the expected number of instances, a seeded experiment showing where the bound is loose and why single runs fall below it, implicit parallelism and the n³ claim, the building block hypothesis, and the critiques and exact schema theorems that followed.
Homomorphisms and the Chinese Remainder Theorem
abstract algebra · rings · homomorphisms · isomorphisms · Chinese remainder theorem · congruences · proofs
The seventh unit of a rings-first abstract algebra course. Ring homomorphisms, maps that respect addition and multiplication, with reduction modulo n, evaluation, a map from the Eisenstein integers onto Z_7 and the Frobenius map as examples; isomorphisms and the properties they preserve, which tell apart three rings with nine elements; the characteristic of a ring; and the Chinese remainder theorem, that Z_mn is isomorphic to Z_m x Z_n exactly when gcd(m, n) = 1, with simultaneous congruences, idempotents, square roots of 1, RSA decryption, Euler's phi and the version for polynomials.
How a Web Search Engine Answers a Query
information retrieval · web search · query processing · ranking
What happens between typing a query and seeing results. Short queries and the intents behind them, query rewriting, candidate retrieval, the signals used to rank, duplicate removal, snippets, and the results page.
Hypothesis Testing
statistics · biostatistics · hypothesis testing · p-value · power · sample size · inference
Deciding whether data are consistent with a stated value of a population mean. The logic of a test and the correct reading of its p-value, following the American Statistical Association's 2016 statement; one- and two-sided z and t tests and their equivalence to confidence intervals; Type I and Type II errors measured by simulation on NHANES blood pressures; and power curves and the sample size a test needs.
Hypothesis Tests for a Mean
statistics · biostatistics · hypothesis testing · p-value · t test · z test · NHANES
How a test of a population mean works and what its p-value says. The logic of a test, the z test with known standard deviation and the t test with estimated standard deviation, worked on NHANES blood pressures and Student's sleep data, one- and two-sided alternatives, why a test and a confidence interval always agree, the American Statistical Association's six principles for reading a p-value, and the common misreadings they warn against. Worked problems from the course text on blood pressure, white blood cell counts, body mass index and percentage of ideal body weight.
Ideals and Principal Ideal Domains
abstract algebra · rings · ideals · principal ideals · principal ideal domains · prime elements · irreducible elements · proofs
The subsets of a ring that one can work modulo. Why a subring is not enough (working modulo Z inside Q breaks multiplication), the definition of an ideal and the ideal test, ideals generated by one or several elements, generators that differ by a unit, every ideal of Z and of F[x] generated by one element, the six ideals of Z_45, an ideal of Z[x] that needs two generators, and irreducible versus prime elements, with Z[sqrt(-5)] as the ring where they part ways.
Ideals and Quotient Rings
abstract algebra · rings · ideals · quotient rings · principal ideal domains · prime ideals · maximal ideals · kernels · first isomorphism theorem · proofs
The eighth unit of a rings-first abstract algebra course. Ideals, the subsets of a ring one can work modulo, with the ideals generated by given elements and the principal ideal domains Z and F[x] in which one generator always suffices; Z[x] and Z[sqrt(-5)] as rings in which it does not; congruence modulo an ideal and the quotient ring R/I, which contains Z_n and F[x]/(p(x)) as special cases; prime ideals, with integral domains as quotients, and maximal ideals, with fields; kernels and the first isomorphism theorem, with the field of four elements and the Gaussian integers as quotients of Z[x], the Gaussian integers modulo n, and the Chinese remainder theorem for rings.
Implementing BM25
information retrieval · BM25 · implementation · Python
A tested implementation of BM25 over an inverted index. What to precompute at indexing time, scoring with accumulators traced step by step, document-at-a-time scoring with upper bounds, a hand-checked example on the four Arctic sentences, the effect of k1 and b on Cranfield, the variants that different systems compute under the same name, an experiment showing how much the variants matter, and the same design in this site's own search. Worked problems on scoring, bounds, saturation and updating an index.
Implementing Evaluation Measures
information retrieval · evaluation · implementation · Python
Computing retrieval measures in practice. The TREC formats for relevance judgments and system runs, a tested Python implementation of precision, recall, average precision, reciprocal rank, and nDCG, the details implementations get wrong, worked cases where trec_eval and textbook definitions disagree (ties, interpolation, unjudged documents, missing topics), and the standard tools trec_eval, pytrec_eval, and ir_measures.
Index Compression
information retrieval · indexing · compression · algorithms
Making the postings of an inverted index small and fast. Why compression speeds up search, storing postings as gaps, variable byte and Elias gamma codes worked bit by bit, how far a gamma code is from optimal, the index size predicted from Zipf's law, delta, Golomb and Rice codes, every code measured on Reuters-21578, and modern word-aligned and SIMD codecs.
Index Construction
information retrieval · indexing · inverted index · algorithms · distributed systems
Building an inverted index for a collection too large for memory. Why disk access patterns dominate, blocked sort-based indexing, single-pass in-memory indexing, distributed indexing with MapReduce, and keeping an index current as documents are added and deleted.
Indirect Standardization and the Standardized Mortality Ratio
statistics · biostatistics · epidemiology · age adjustment · indirect standardization · standardized mortality ratio · expected deaths · comparative mortality figure · confidence intervals · Poisson distribution · mortality · vital statistics
Comparing a population's deaths with the deaths a standard set of age-specific rates would produce. Expected deaths, the standardized mortality ratio as a weighted average of age-specific ratios, the indirectly standardized rate and the comparative mortality figure, worked for Maine, Alaska, Florida and Utah against the 2021 U.S. rates; the exact Poisson interval and the log-scale interval for the ratio; why two ratios cannot safely be compared with each other, while ratios of directly standardized rates can; and when the direct and the indirect method each apply.
Inference on Proportions
statistics · biostatistics · proportions · binomial distribution · confidence intervals · hypothesis testing · chi-square test · sample size · inference · NHANES
Estimating and testing the share of a population with a yes-or-no outcome. The sampling distribution of a sample proportion and its normal approximation; why the textbook interval for a proportion covers the truth less often than it claims, computed exactly, and the Wilson, Agresti-Coull and Clopper-Pearson intervals that replace it; the one-sample z test and exact binomial test, power and sample size; and the comparison of two proportions, including the chi-square test of a 2 x 2 table. Worked on hypertension in NHANES adults.
Initialization and Variation in Genetic Programming
evolutionary computation · genetic programming · initialization · crossover · mutation
How genetic programming creates its first trees and changes them. The full, grow and ramped half-and-half methods and the tree shapes they actually produce, probabilistic tree creation, subtree crossover and Koza's 90/10 node-selection rule, subtree, point, hoist and shrink mutation, and the evidence on crossover versus mutation in GP.
Integral Domains and Fields
abstract algebra · rings · integral domains · fields · cancellation · zero divisors · finite fields · proofs
The commutative rings in which products of nonzero elements are nonzero (integral domains) and in which every nonzero element can be inverted (fields). Proofs that every field is an integral domain, that a ring is an integral domain exactly when nonzero factors can be canceled, and that every finite integral domain is a field; the rings Z_n[i] of Gaussian integers modulo n as a running example, with a field of nine elements and the theorem that Z_p[i] is a field exactly when -1 has no square root modulo p, which for an odd prime p happens exactly when p leaves remainder 3 on division by 4. Worked problems from the course's assignment close the article.
Intersecting Postings Lists
information retrieval · Boolean retrieval · algorithms · query processing
The core algorithms of query processing. The linear merge for AND traced pointer by pointer, with an interactive stepper, the corresponding merges for OR and AND NOT, why OR NOT is expensive, exact comparison counts, several lists intersected shortest first or all at once, and intersection by binary and galloping search when one list is much shorter, with a measured comparison of the three and a lower bound on the comparisons any method needs. Worked problems on AND NOT, OR NOT and arbitrary Boolean formulas.
Intervals and Adjustment for Relative Risks and Odds Ratios
statistics · biostatistics · epidemiology · relative risk · odds ratio · confidence intervals · Katz interval · Woolf interval · Mantel-Haenszel · stratified analysis · confounding · NHANES
Confidence intervals for an estimated relative risk or odds ratio, and adjustment of either for a confounder. The limit theorem for a function of an estimate, applied to the logarithm of a proportion and of an odds; the Katz interval for the relative risk and Woolf's interval for the odds ratio, with a worked example and their exact coverage; the Mantel-Haenszel summary odds ratio and relative risk, with the Robins-Breslow-Greenland and Greenland-Robins variances and the Mantel-Haenszel test. Worked on obesity, smoking and diabetes among NHANES adults, with worked problems on a case-control sample, a crude table and a stratified analysis by age.
Irreducible Polynomials and Roots
abstract algebra · polynomials · irreducible polynomials · unique factorization · roots · Eisenstein's criterion · Gauss's lemma · fundamental theorem of algebra · proofs
The primes of a polynomial ring. Irreducible polynomials over a field, Euclid's lemma and unique factorization for polynomials, the remainder and factor theorems, why a polynomial of degree n has at most n roots and how that fails modulo 15, x^p - x as the product of all linear factors over Z_p with Wilson's theorem as a corollary, the root test for degrees 2 and 3, and over the rationals the rational root test, Gauss's lemma, Eisenstein's criterion and reduction modulo a prime, ending with the irreducible polynomials over the reals and the complex numbers.
Island Model Genetic Algorithms
evolutionary computation · parallel computing · genetic algorithms · diversity · population structure
Dividing a population into partly isolated subpopulations that exchange migrants. Demes, migration rate, interval, policy and topology; how migration controls diversity and takeover; the early studies by Tanese and by Cohoon and colleagues; when islands help and when they do not; cellular evolutionary algorithms and their selection pressure; and a measured comparison with a single population on Rastrigin's function and a deceptive function.
K-means in Practice
information retrieval · clustering · k-means · experiments
The decisions k-means leaves to its user. Choosing starting centroids, restarts, and k-means++, naming the clusters with centroid and differential labels, choosing the number of clusters, scaling features, and spherical k-means for text, with experiments on Reuters news stories that show what each choice changes.
Kernels and the First Isomorphism Theorem for Rings
abstract algebra · rings · homomorphisms · kernels · first isomorphism theorem · quotient rings · Chinese remainder theorem · Gaussian integers · proofs
The kernel of a ring homomorphism, the set of elements sent to 0, is an ideal, and it decides when two elements have the same image and when the map is one-to-one. The first isomorphism theorem, proved in full, identifies the image of any homomorphism with the quotient by its kernel. Applications: Z[x] modulo (2, x^2 + x + 1) as the field with four elements, the complex numbers and Q(sqrt 2) as quotients of polynomial rings at one stroke, Z_n/(d) as Z_d, the Gaussian integers modulo n and which of those quotients are fields, a prime ideal of Z[x] that is not maximal, homomorphisms out of a field and the Frobenius automorphism, and the Chinese remainder theorem for any commutative ring.
Language Models for Retrieval
information retrieval · probabilistic models · language models · ranking
Ranking documents by the probability that a language model estimated from each document would generate the query. The query likelihood model, why an unsmoothed model behaves like Boolean AND, Jelinek-Mercer and Dirichlet smoothing, the derivation showing that smoothing supplies IDF-like weighting and length normalization, Cranfield query 185 scored by hand, and an experiment on all of Cranfield in which query likelihood trails BM25.
Latent Dirichlet Allocation
information retrieval · topic modeling · LDA · Bayesian inference
The standard probabilistic topic model. The generative story of documents as mixtures of topics, the Dirichlet distribution and what its parameters do, why the posterior must be approximated, collapsed Gibbs sampling derived, proved to converge and checked against the exact posterior of a toy corpus, and twenty topics found in Reuters news stories, with what they get right and wrong.
Latent Semantic Indexing
information retrieval · topic modeling · LSI · linear algebra
Retrieval in a space of latent dimensions found by the singular value decomposition. Low-rank approximation and the Eckart–Young theorem, proved for the spectral and Frobenius norms, the textbook's five-term example, folding queries and new documents into the reduced space, an experiment on Cranfield in which LSI beat BM25 though not for the usual reason, and LSI's costs and limits.
Learning to Rank
information retrieval · learning to rank · machine learning · ranking
Learning a ranking function from relevance judgments instead of designing it by hand. The textbook's two-feature example as a classifier, why ranking is better posed as ordering than as classification, the pointwise, pairwise and listwise approaches with the RankNet, LambdaRank and ListNet losses derived, gradient-boosted LambdaMART, and an experiment on Cranfield in which four learned combinations of eight retrieval features barely improve on BM25.
Likelihood Ratios for Diagnostic Tests
statistics · biostatistics · diagnostic tests · likelihood ratio · Bayes theorem · odds · pre-test probability · post-test probability · Fagan nomogram · diagnostic odds ratio · conditional independence · diabetes · HbA1c · NHANES
Summarizing what a test result says about disease by one number per result. Positive and negative likelihood ratios; Bayes' theorem in odds form, post-test odds = likelihood ratio x pre-test odds, proved and checked on three age groups; the log-odds scale and the geometry of Fagan's nomogram; confidence intervals on the log scale, which are those of a risk ratio; the diagnostic odds ratio; likelihood ratios for bands of a continuous result instead of a single cut-off; predictive values in terms of likelihood ratios; and combining two tests, which requires conditional independence that two real measurements do not have. Worked on HbA1c, BMI and fasting glucose in NHANES adults, with worked problems on a second cut-off, one patient's post-test probabilities, the ratio needed to reach a target probability and two positive results.
Limits of the Evolutionary Metaphor
evolutionary computation · metaheuristics · research methodology · criticism
Why natural selection is not an optimizer, why a fitness function is a statement of intent, and the critique of metaphor-based metaheuristics by Sörensen, Weyland, Camacho-Villalón and colleagues. Balanced against the problems where evolutionary methods have earned their place, from CMA-ES to the evolved ST5 antenna and AlphaEvolve.
Linkage Properties of Agglomerative Clustering
information retrieval · clustering · hierarchical clustering · proofs · algorithms
Why the linkage criteria of hierarchical agglomerative clustering behave as they do, with proofs. The distance-update rules, monotonic merge heights for single, complete and average linkage, the group-average vector-sum formula, centroid inversions, single linkage as a minimum spanning tree, the priority-queue algorithm and best-merge persistence, and three exercises of the course text solved in full.
Local Search
evolutionary computation · optimization · search · hill climbing
Improving a single candidate solution by small changes, why it stalls at local optima, and the methods that let it escape, from random restarts to simulated annealing and tabu search.
Master-Slave Parallel Evaluation
evolutionary computation · parallel computing · genetic algorithms · speedup
Speeding up an evolutionary algorithm by farming out fitness evaluations to worker processors while one master runs selection and variation. Parallel implementation versus parallel model, synchronous and asynchronous schemes, Cantú-Paz's model of the optimal number of slaves, Amdahl's law, uneven evaluation times, and a measured speedup on a desktop machine set against the model's prediction.
Mean Average Precision
information retrieval · evaluation · MAP · average precision
The most widely reported single-number measure for ranked retrieval. Average precision for one query, worked step by step and drawn as the area under the precision-recall curve, its mean across queries with per-query values on Cranfield, why it is top-heavy derived from the formula, the geometric mean variant for hard queries, and its interpretation as a user model.
Measures of Center and Spread
statistics · biostatistics · descriptive statistics · mean · median · mode · variance · standard deviation · interquartile range · quartiles · skewness · changes of units · NHANES
The numbers that summarize a distribution. The mean, median and mode, with proofs that the mean minimizes squared deviations and the median absolute ones; their behavior under skewness and a single recording error; the range, interquartile range, variance and standard deviation, worked by hand on eleven NHANES blood pressures; why software disagrees about quartiles; changes of units, with the quartile methods they hold for; and which summaries to report.
Model-Based Clustering and the EM Algorithm
information retrieval · clustering · expectation-maximization · mixture models
Clustering as fitting a mixture model by maximum likelihood. The mixture likelihood, the EM algorithm derived from a lower bound with the proof that the likelihood never decreases, Gaussian and Bernoulli mixtures, k-means as the limit of a spherical Gaussian mixture whose variance goes to zero, and what EM does not guarantee, computed on six points, eleven documents and Reuters.
Moment Generating Functions and Slutsky's Theorem
statistics · biostatistics · moment generating function · Slutsky's theorem · law of large numbers · Chebyshev's inequality · convergence in probability · convergence in distribution · sampling distribution · NHANES
The proofs behind the normal limit of a sample mean. The weak law of large numbers, proved from Chebyshev's inequality; the limit theorem for the standardized mean, proved with moment generating functions for every population that has one, with an exact list of what is assumed, proved and cited; and Slutsky's theorem, with the case proved that lets the sample standard deviation s replace sigma. Checked on the exponential distribution and on NHANES blood pressures. Worked problems on the moment generating function of a binomial count and its normal limit, a sample size from Chebyshev's inequality against the normal approximation, and the coverage of the interval with s for an exponential population.
Monitoring Websites
information retrieval · web crawling · Python · monitoring
The crawler most people actually write. Watching a few specific pages for changes, checking first for feeds and interfaces, fetching politely with conditional requests, fingerprinting only the part of the page that matters, handling layout changes and scripted pages, and a tested Python monitor built on requests and BeautifulSoup.
Multi-Objective Evolutionary Algorithms
evolutionary computation · multi-objective optimization · Pareto dominance · survey
How evolutionary algorithms came to optimize several objectives at once, from VEGA to NSGA-III. Pareto ranking and fitness sharing, elitist archives (SPEA, SPEA2, PAES), decomposition (MOEA/D), indicator-based selection (IBEA, SMS-EMOA), and why many objectives need reference points, with a computed demonstration of how dominance loses its grip as objectives are added.
Multi-Objective Optimization
evolutionary computation · optimization · multi-objective optimization · Pareto optimality
Optimizing several conflicting objectives at once, from Pareto dominance and scalarization to NSGA-II and its successors, and the indicators used to judge the fronts they find.
Multiple Comparisons and the Bonferroni Correction
statistics · biostatistics · hypothesis testing · multiple comparisons · Bonferroni · Holm · Tukey HSD · studentized range · family-wise error rate · analysis of variance · NHANES
Finding which group means differ after an analysis of variance without letting false alarms multiply. The family-wise error rate of all pairwise t-tests measured by simulation, the Bonferroni correction proved from the union bound and worked on NHANES blood pressures in four age groups, Holm's step-down improvement with its proof, Tukey's honestly significant difference from the studentized range, simultaneous confidence intervals, Scheffe's method, why a significant F test does not protect later comparisons, and what the corrections cost in power. Worked problems on four tobacco-use groups, a prespecified family of three and a contrast.
Naive Bayes Classification
information retrieval · text classification · Naive Bayes · probabilistic models
The standard probabilistic text classifier. Bayes' rule applied to documents, the generative story behind the multinomial model, its estimates derived as maximum likelihood with a Lagrange multiplier, add-one smoothing derived as the posterior mean under a uniform Dirichlet prior, what the smoothing constant does, computing in log space, Naive Bayes as a linear classifier, the training and classification procedure with its rule for unseen words, the textbook's worked example carried through every step, cost, results on Reuters-21578, and worked problems from the course text.
Natural Evolution Strategies and Evolution Strategies for Reinforcement Learning
evolutionary computation · evolution strategies · natural gradient · reinforcement learning · neuroevolution
Evolution strategies as gradient ascent on the parameters of a search distribution. Search gradients and the log-likelihood trick, the natural gradient through the Fisher matrix, fitness shaping, xNES and SNES, the link to CMA-ES, and the simplified evolution strategy that OpenAI scaled to train neural network policies, with the follow-up studies that clarified what it does.
Natural Selection for Computer Scientists
evolutionary computation · natural selection · population genetics · biology
The biology that evolutionary algorithms borrow, stated as biologists state it: the three conditions for selection, fitness as reproductive success, genes, alleles, genotype and phenotype, mutation, recombination, genetic drift, and the modern synthesis. For each, what an evolutionary algorithm keeps, simplifies, or discards. Worked through in numbers: the haploid selection recursion, the breeder's equation on a noisy fitness function, Wright-Fisher fixation probabilities against the diffusion formula, and a seeded experiment on drift in a small population.
Near-Duplicate Detection
information retrieval · web crawling · duplicate detection · hashing
Finding pages whose content repeats other pages. Exact fingerprints, shingling and the Jaccard coefficient, estimating resemblance cheaply with MinHash sketches, banding sketches to avoid comparing every pair, simhash, and what the measures show on this site's own pages, with a two-sentence example worked through by hand. The MinHash theorem proved, the banding S-curve 1 − (1 − s^r)^b derived with its thresholds, the random-hyperplane argument in full, and worked problems.
NEAT: NeuroEvolution of Augmenting Topologies
evolutionary computation · neuroevolution · NEAT · neural networks · speciation
Stanley and Miikkulainen's method for evolving the structure and the weights of neural networks together. Node and connection genes, historical markings and crossover by innovation number with the paper's own example worked through, speciation in brief, growth from minimal networks, the paper's XOR, pole-balancing and ablation results checked against the paper, and a from-scratch reimplementation run on XOR over 100 seeds and compared honestly with the published figures.
Neuroevolution
evolutionary computation · neuroevolution · neural networks · NEAT
Evolving neural networks, from fixed-topology weight evolution to NEAT's growing topologies, speciation, CPPNs and HyperNEAT, and evolutionary architecture search, with a soft-robot project from the course.
No Free Lunch Theorems
evolutionary computation · optimization · search · theory
What Wolpert and Macready proved about search algorithms averaged over all problems, the sharpened theorem for sets closed under permutation, why such sets are rare, what the theorems do and do not imply for evolutionary algorithms, and why they fail in continuous domains. Proved by a counting argument shown in full on three points, and checked by exhaustive enumeration of all 6,561 functions on a three-bit search space.
Nonparametric Methods
statistics · biostatistics · nonparametric methods · rank tests · sign test · Wilcoxon signed-rank test · Wilcoxon rank-sum test · Mann-Whitney U test · Kruskal-Wallis test · inference
Tests built on signs and ranks instead of a normal model. The sign test and the Wilcoxon signed-rank test for paired data, the Wilcoxon rank-sum (Mann-Whitney) test for two independent groups and the Kruskal-Wallis test for several, each with its exact null distribution by counting, its normal or chi-squared approximation and corrections for ties; what each test actually tests, and its efficiency and robustness against the t and F tests. Worked on Student's sleep data and NHANES blood pressures.
Normal Subgroups and Quotient Groups
abstract algebra · groups · normal subgroups · quotient groups · factor groups · conjugation · cosets · Rubik's cube · proofs
The subgroups a group can be worked modulo. Multiplying cosets by representatives fails for some subgroups of the octagon's group D_8 and works exactly when the subgroup is normal, closed under conjugation. Three equivalent forms of normality, with examples and non-examples in D_8, S_8 and the Rubik's cube group. The quotient group G/N, its order and the natural homomorphism, which makes normal subgroups exactly the kernels; Z/nZ, S_n/A_n and the parity of the Rubik's cube; normal subgroups beside ideals, and simple groups. Worked problems on the subgroups of S_3 and on the quotient of D_6 by its half turn, a copy of D_3.
NSGA-II
evolutionary computation · multi-objective optimization · NSGA-II · genetic algorithms · Pareto dominance
The elitist non-dominated sorting genetic algorithm of Deb, Pratap, Agarwal and Meyarivan (2002), specified completely. Fast non-dominated sorting, crowding distance, the crowded-comparison operator, survivor selection from parents and offspring, and constrained domination, with a worked example and a 30-run experiment on ZDT1, ZDT2 and ZDT3 compared with the paper's results.
Okapi BM25
information retrieval · probabilistic models · ranking
The ranking function that extended the Binary Independence Model with term frequency saturation and document length normalization, and has remained the standard lexical baseline for three decades. Built up step by step from the RSJ weight, with the saturation and length curves plotted, a fully worked score for a Cranfield query, and an interactive demo of k1 and b.
One-Sided Confidence Bounds and Sample Size
statistics · biostatistics · confidence intervals · one-sided bounds · sample size · study design
Confidence bounds that limit a mean from one side only, derived from the same pivot as two-sided intervals and worked on Student's sleep data; their link to one-sided tests, why the side must be chosen before the data are seen (choosing afterwards doubles the miss rate), and how to choose a sample size for a target margin of error, with the t iteration and the chance that the finished interval is as narrow as planned. Worked problems on gestational ages and on sizing a one-sided sleep trial.
One-Way Analysis of Variance
statistics · biostatistics · hypothesis testing · analysis of variance · ANOVA · F test · F distribution · Welch ANOVA · sums of squares · NHANES
Comparing the means of several independent groups with one test. The partition of the total sum of squares into between-groups and within-groups parts, the expected mean squares, the F distribution of s_B^2 / s_W^2 under the null hypothesis derived, a worked example on NHANES blood pressures in four age groups, why F equals t squared for two groups, the assumptions and what unequal variances do, and Welch's analysis of variance. Worked problems on blood pressure in four groups defined by tobacco use.
Online Evaluation
information retrieval · evaluation · A/B testing · interleaving · clicks
Evaluating retrieval systems with real users instead of fixed judgments. A/B tests and how many users they need, what clicks and abandonment do and do not mean, position bias measured and simulated, team-draft interleaving traced through every coin flip with an interactive demo, where its sensitivity comes from, evaluating from logged data, and how online and offline evaluation complement each other.
Optimizing Boolean Queries
information retrieval · Boolean retrieval · query processing · optimization
Choosing the order in which to evaluate a Boolean query. Processing terms by increasing document frequency, estimating the size of OR clauses, where to apply NOT, rewriting queries with Boolean identities, why ordering matters most when combined with search-based intersection, general cost bounds, and the plans measured on random postings with every intermediate result size. Worked problems on ordering OR clauses, on a query where shortest-first is not the cheapest plan, and on where to apply NOT.
Overdispersion in Count Data
statistics · biostatistics · probability · overdispersion · Poisson distribution · index of dispersion · negative binomial · gamma distribution · law of total variance · mortality · vital statistics
Why real counts vary more than the Poisson model allows, and what to do about it. Weekly deaths from NCHS for 2014 to 2019, where cancer deaths fit the Poisson and deaths from all causes, with their winter peaks, vary nearly four times as much in Iowa; the proof that a varying rate adds its own variance to the mean; the growth of the excess with the size of the state; and the remedies, with the negative binomial derived as a gamma mixture of Poisson counts. A worked problem on California's weekly deaths.
PageRank
information retrieval · link analysis · PageRank · web search
Ranking pages by the links that point to them. The random surfer model, the link matrix made stochastic and then given teleportation, why the result has exactly one answer, the eigenvalues that set the speed of power iteration, PageRank as a Markov chain and as a linear system, personalized PageRank and its linearity, a summary of HITS, and the limits of link analysis, all worked through on a five-page example. The damping factor d and the course text's teleport probability α = 1 − d. Worked problems from the course text.
Parallel and Coevolutionary Algorithms
evolutionary computation · parallel computing · coevolution
Spreading an evolutionary algorithm across processors and subpopulations, and evolving populations whose fitness depends on one another, in competition or cooperation.
Pareto Dominance and Pareto Optimality
evolutionary computation · multi-objective optimization · Pareto optimality · decision making
How to compare solutions when there is more than one objective. Decision and objective space, weak, ordinary and strict dominance, the Pareto-optimal set and front, ideal and nadir points, local and global Pareto optimality, and the trade-off view of decision making, worked through on Deb's cantilever beam design.
Parsing and Evaluating Boolean Queries
information retrieval · Boolean retrieval · parsing · implementation
Turning a query string into a tree and evaluating it against an index. Operator precedence and associativity, a grammar and a tested recursive-descent parser traced call by call, error handling, stop words and analysis inside queries, the parser behind this site's search box and the fixes that testing it led to, and lessons from my course assignment. Worked problems: every AND and OR combination of a query read left to right and by precedence, a traced parse, and a removed stop word under each operator.
Phrase and Proximity Queries
information retrieval · Boolean retrieval · phrase queries · positional index
Matching words in sequence or near each other. Why document-level postings cannot answer phrase queries, biword indexes and their false positives measured on Cranfield, positional indexes, the positional merge and the linear-time window algorithm traced position by position, a six-word phrase, distance, sentence and paragraph operators each worked to the end, the smallest window as a proximity measure, and combined indexes. Worked problems on biword false positives and on phrase and proximity queries over positional postings.
Plus and Comma Selection and Self-Adaptation
evolution strategies · evolutionary computation · self-adaptation · step-size adaptation · continuous optimization
How evolution strategies with populations select, recombine and adapt their own mutation parameters. Plus and comma selection, intermediate and discrete recombination, log-normal self-adaptation of one step size, n step sizes and rotation angles, why comma selection helps the step sizes adapt, and cumulative step-size adaptation as the derandomized alternative, with σ trajectories measured on a sphere and an ill-conditioned ellipsoid.
Politeness and robots.txt
information retrieval · web crawling · robots.txt
How a crawler avoids burdening the sites it visits. Rate limits and one connection per host, identifying the crawler, and the Robots Exclusion Protocol, with its rules for matching, error handling, and caching as standardized in RFC 9309, and where Python's parser departs from the standard. Worked problems on rates, wildcard rules, and the hosts a thread needs to stay busy.
Polynomial Arithmetic
abstract algebra · polynomials · polynomial rings · division algorithm · irreducible polynomials · unique factorization · proofs
The fifth unit of a rings-first abstract algebra course. Polynomials with coefficients in a ring form a ring; over a field they have a division algorithm, greatest common divisors computed by the Euclidean algorithm, Bezout's identity and unique factorization into irreducible polynomials, each proved in parallel with the integers. Roots and linear factors, and tests for irreducibility over finite fields, the rationals, the reals and the complex numbers, with one quartic followed through every field.
Polynomial Division over a Field
abstract algebra · polynomials · division algorithm · greatest common divisor · Euclidean algorithm · Bezout's identity · proofs
The division algorithm for polynomials, proved for any divisor whose leading coefficient is invertible and so for every nonzero divisor over a field, with degree in place of size. Long division as the proof run as a procedure, divisibility and associates, the greatest common divisor of two polynomials computed by the Euclidean algorithm, Bezout's identity through the extended algorithm, relatively prime polynomials and cancellation, and why the gcd does not change when the field is enlarged, all paralleling the integers.
Polynomial Rings
abstract algebra · rings · polynomials · polynomial rings · integral domains · units · proofs
Polynomials with coefficients in a ring, defined as sequences with finitely many nonzero terms, and the proof that they form a ring of their own. Degree and leading coefficients, why the degree of a product is the sum of the degrees exactly when the coefficients come from an integral domain, the units of a polynomial ring and why a polynomial ring is never a field, evaluation and when it respects multiplication, and why a polynomial is not the same thing as the function it defines.
Power and Sample Size for a Test of a Mean
statistics · biostatistics · hypothesis testing · power · sample size · noncentral t · study design · NHANES
How likely a test is to detect a difference that is really there, and how many observations it needs to do so reliably. The power function of the z test derived and drawn as power curves, the noncentral t distribution for the t test, the sample size formula derived from the power function and checked against the exact t calculation and simulation on NHANES blood pressures and Student's sleep data, what moves the answer, and why power computed from the observed data adds nothing to the p-value. Worked problems on a study of bone mineral content, a one-sided sleep trial and the observed power of a nonsignificant sample.
Precision, Recall, and the F Measure
information retrieval · evaluation · precision · recall
The basic measures for a retrieved set. The contingency table, precision and recall as conditional probabilities, why accuracy fails for retrieval, the trade-off between the two traced on a real Cranfield query, the F measure as a weighted harmonic mean and the meaning of its weight, its geometry over the precision-recall square, and averaging over queries.
Predicting Star Ratings from Review Text
information retrieval · text classification · Naive Bayes · sentiment analysis · project
My CSC 790 term project with James R. Brown, which classified Goodreads reviews into one to five stars with multinomial Naive Bayes. The data and pipeline, the results read class by class from the confusion matrix, the baseline they should be compared with, and natural next steps.
Predictive Values and Bayes' Theorem
statistics · biostatistics · diagnostic tests · screening · positive predictive value · negative predictive value · Bayes theorem · prevalence · base rate · natural frequencies · apparent prevalence · Rogan-Gladen · diabetes · HbA1c · NHANES
What a test result means for the person tested. Positive and negative predictive values read from a 2 x 2 table and derived from sensitivity, specificity and prevalence by Bayes' theorem; natural frequencies; why a positive result for a rare condition is often a false alarm, shown at prevalences from 0.5% to 50%; how far the theorem's predictions hold across age groups when sensitivity and specificity themselves vary; why a case-control study cannot give predictive values; and estimating true prevalence from an imperfect test with the Rogan-Gladen correction. Worked on HbA1c and fasting glucose in NHANES adults, with worked problems on a second cut-off, a population with a different prevalence, the prevalence needed for a given predictive value and the correction in two groups.
Primes and the Fundamental Theorem of Arithmetic
abstract algebra · number theory · prime numbers · unique factorization · Euclid's lemma · proofs
Prime numbers defined by their divisors and characterized by Euclid's lemma, with full proofs that every integer other than 0 and plus or minus 1 factors into primes and that the factorization is unique. Why uniqueness needs proof (the even integers, where it fails), divisibility, gcd, lcm and divisor counts read from prime exponents, the irrationality of log base 2 of 3, Euclid's proof that the primes never run out, trial division and the sieve of Eratosthenes, and how the primes thin out.
Probabilistic Latent Semantic Analysis
information retrieval · topic modeling · pLSA · expectation-maximization
Hofmann's probabilistic reformulation of latent semantic indexing. The aspect model of documents as mixtures of topics, fitting it by expectation-maximization with a worked example, its relation to LSI and nonnegative matrix factorization, and the overfitting and lack of a model for new documents that led to LDA.
Probabilistic Retrieval
information retrieval · probabilistic models
Ranking documents by an estimate of how likely they are to be relevant, from the Probability Ranking Principle through the Binary Independence Model and BM25 to inference networks and relevance feedback, with an experiment comparing the models on the Cranfield collection.
Probability
statistics · biostatistics · probability · axioms of probability · independence · conditional probability · total probability · Bayes theorem · relative risk · odds ratio · case-control study · confounding · NHANES
The rules for reasoning about uncertain events, and the two measures epidemiology uses to compare the risk of disease between groups. The axioms and the rules proved from them, including inclusion-exclusion; independence and why it differs from mutual exclusivity; conditional probability, the multiplication rule, the law of total probability and Bayes' theorem; confounding and Simpson's paradox; and the relative risk and odds ratio with their log-scale confidence intervals, the rare-disease approximation and the case-control study. Worked on hypertension, obesity, diabetes and smoking in NHANES adults.
Probability for Information Retrieval
information retrieval · probability · probabilistic models
The probability needed for probabilistic retrieval models. Events and random variables, joint and conditional probability, the chain rule, Bayes' rule with a relevance example worked as counts, odds and log odds, conditional independence tested on real term counts, and estimating probabilities from counts with smoothing derived from a Beta prior.
Program Trees in Genetic Programming
evolutionary computation · genetic programming · representation · program trees
What genetic programming evolves and how it represents it. Program trees and Lisp-style prefix notation, function and terminal sets, closure and protected operators, sufficiency, fitness cases and Koza's preparatory steps, the size bounds for trees of a given depth, strongly typed GP, and how all of this differs from a genetic algorithm.
Pseudo-Relevance Feedback
information retrieval · relevance feedback · query expansion · probabilistic models
Relevance feedback without a searcher. Assuming the top-ranked documents are relevant and expanding the query from them, the main methods from Croft and Harper to relevance models, an expansion traced term by term on three queries, experiments on Cranfield showing average gains and per-query losses, tuning on held-out queries, the round-by-round estimate of the Binary Independence Model's probabilities worked on query 185, query drift in detail, and when to apply it. Worked problems on expansion scores, average precision and reweighting.
Public-Key Cryptography
abstract algebra · number theory · cryptography · RSA · Fermat's little theorem · Euler's theorem · proofs
The fourth unit of a rings-first abstract algebra course, an application of modular arithmetic. Fermat's little theorem and Euler's theorem with full proofs, primality testing and the Carmichael numbers that defeat the Fermat test, and the RSA cryptosystem, with a worked key of our own, a proof that decryption recovers every message, and an account of why it is believed secure.
Quality Diversity: MAP-Elites and Novelty Search
evolutionary computation · quality diversity · novelty search · MAP-Elites · illumination algorithms · evolutionary robotics
Searching for what is new instead of what is best. Novelty search and the deceptive maze, behavior characterizations and archives, the MAP-Elites algorithm stated step by step, the quality-diversity framing and QD-score, CVT-MAP-Elites for many descriptor dimensions, the damaged robots of Cully and colleagues, and a 30-seed comparison with a genetic algorithm on a planar robotic arm.
Quality Indicators for Pareto Fronts
evolutionary computation · multi-objective optimization · performance indicators · hypervolume · benchmarking
How the output of a multi-objective optimizer is reduced to a number. Hypervolume, generational distance, IGD and IGD+, spacing, the spread Δ, and the ε-indicator, computed on constructed fronts; where they disagree, how the hypervolume ranking flips with the reference point, what exact hypervolume computation costs, and what Zitzler and colleagues proved unary indicators can and cannot say.
Query Expansion
information retrieval · query expansion · relevance feedback · language models
Adding terms to a query that the searcher did not type. Interactive and automatic expansion, controlled vocabularies, thesauri and query logs, an association thesaurus built from Cranfield and used to expand every query, why global expansion barely helps there while local expansion with relevance models (RM3) helps substantially, and later methods based on embeddings and document expansion. Worked problems on co-occurrence matrices and on a relevance model computed in exact fractions.
Random Variables, Expectation and Variance
statistics · biostatistics · probability · random variables · probability mass function · cumulative distribution function · expectation · variance · covariance · independence · conditional expectation · law of total variance · NHANES
The language the theoretical distributions are written in. Random variables, probability mass functions and distribution functions, on the number of an adult's three blood pressure readings that are high; the expected value and the variance, with linearity of expectation, the variance of a sum with its covariances and the additivity of variances for independent variables proved; and conditional expectation, with the laws of total expectation and total variance proved. Worked problems on an adult's first two readings (a covariance of 0.1928), two patients drawn without replacement, the variance of the count split by age group, and zero covariance without independence.
Rank Fusion
information retrieval · ranking · rank fusion · metasearch · evaluation
Combining the ranked lists of several retrieval functions into one. Why raw scores cannot be added, score-based fusion with CombSUM and CombMNZ and the normalization they need, rank-based fusion with the Borda count, reciprocal rank fusion and Condorcet fusion, the chorus, skimming and dark-horse effects, what can be proved about the methods, and an experiment fusing BM25, query likelihood and TF-IDF on Cranfield, where no fusion beats BM25 alone.
Ranking Multi-Objective Optimizers with Pareto Optimality
evolutionary computation · multi-objective optimization · performance indicators · benchmarking · project
The paper I presented in CSC 742, Ibrahim, Bidgoli, Rahnamayan and Deb (2024), which ranks multi-objective optimizers by treating their quality-indicator scores as objectives and sorting runs into Pareto levels. The method, its Olympic, linear, exponential and adaptive ranking rules, its results on the CEC 2018 competition, a recomputation of its overall ranking, and a small worked example showing how one indicator can decide the outcome.
Rates and Standardization
statistics · biostatistics · epidemiology · rates · mortality · incidence · prevalence · person-time · age adjustment · standardization · standardized mortality ratio · Poisson distribution · vital statistics
Comparing how often deaths and diseases occur in populations of different sizes and ages. Counts, proportions, ratios and rates; person-time; incidence and prevalence; crude and age-specific rates and the Poisson model for their precision; then direct standardization with a standard population, its choice and its gamma confidence interval, and indirect standardization with the standardized mortality ratio. Worked on U.S. deaths from CDC WONDER and on Maine and Alaska, where the crude death rates and the age-adjusted rates rank the two states in opposite orders.
Rates in Public Health
statistics · biostatistics · epidemiology · rates · mortality · incidence · prevalence · person-time · risk · length-biased sampling · vital statistics
How public health puts counts of deaths and disease on a common scale. Proportions, ratios and rates, and the units that tell them apart; person-time for people followed for different lengths of time, and the risk a rate implies; incidence and prevalence, with the steady-state relation P/(1 - P) = I x D derived and checked by simulation; and why a survey at one moment finds the long cases. Opens with the 2021 death rates of Maine and Alaska, which the next article takes apart.
Recent Trends and Applications of Evolutionary Computing
evolutionary computation · quality diversity · evolutionary robotics · artificial life
Where evolutionary computation stands now, from quality diversity and language-model-guided program evolution to evolutionary robotics, engineered designs, the unexpected solutions digital evolution finds, and artificial life.
Red Queen Dynamics in Coevolution
evolutionary computation · coevolution · Red Queen · game theory · measuring progress
Van Valen's Red Queen hypothesis and what it means for coevolutionary algorithms. Lotka-Volterra cycles as an analogy, why fitness measured against coevolving opponents hides progress, cycling in intransitive games, disengagement, forgetting, mediocre stable states and solution concepts, and the CIAO, master and dominance tournaments for measuring progress, with a seeded rock-paper-scissors experiment.
Relative Risk and the Odds Ratio
statistics · biostatistics · epidemiology · relative risk · risk ratio · odds ratio · case-control study · cohort study · rare disease assumption · prevalence ratio · NHANES
The two measures epidemiology uses to compare the risk of disease between exposed and unexposed groups. Risk, risk difference, relative risk, odds and the odds ratio from a 2 x 2 table; the identity OR = RR (1 - p2)/(1 - p1) and why the odds ratio approximates the relative risk only for rare outcomes; cohort, cross-sectional and case-control designs, with proofs that a case-control study estimates the odds ratio and cannot estimate the relative risk, and a simulated case-control study; and which measure to report. Worked on obesity and diabetes among NHANES adults, with worked problems on a second 2 x 2 table and on converting an odds ratio to a relative risk.
Relevance
information retrieval · foundations · relevance · evaluation
The concept every retrieval model approximates and every evaluation measures. Its kinds, why people disagree about it, how information needs change during a search, and what systems can actually observe.
Relevance Feedback
information retrieval · relevance feedback · query expansion · probabilistic models
Improving a query from the searcher's judgments of initial results. Rocchio's vector-space method drawn in two dimensions, Ide's variants, probabilistic reweighting with the Robertson–Spärck Jones weight worked on a real query, choosing expansion terms by offer weight, evaluating on the residual collection, experiments on the Cranfield collection, and why explicit feedback is rarely used. The Rocchio formula derived as the practical form of the optimal query, the difference of centroids. Worked problems from the course text's chapter 9 and on query 180.
Relevance Judgments, Pooling, and Agreement
information retrieval · evaluation · relevance judgments · pooling · kappa
Where the judgments in a test collection come from. Assessors and their instructions, pooling simulated on Cranfield and the biases it introduces, measures for incomplete judgments, the kappa statistic derived and worked, what happens to system rankings when the assessor changes, and crowdsourced and model-generated judgments.
Retrieval Evaluation
information retrieval · evaluation · test collections
How to tell whether one retrieval system is better than another. Test collections and relevance judgments, precision and recall, ranked measures such as MAP and nDCG, assessor agreement, statistical significance, online experiments with users, and code to compute it all.
Ring Homomorphisms and Isomorphisms
abstract algebra · rings · homomorphisms · isomorphisms · characteristic · Frobenius map · Eisenstein integers · Gaussian integers · proofs
Maps between rings that respect addition and multiplication. The definitions, with examples from reduction modulo n, evaluation of polynomials, a map from the Eisenstein integers onto Z_7 and the Frobenius map, and non-examples from determinants and transposes; the first properties of a homomorphism, proved in full, including what happens to the identity and to units; the homomorphisms out of Z and the characteristic of a ring; composites and inverses; the properties an isomorphism preserves, used to tell apart three rings with nine elements; and two rings with four elements and two with dual numbers shown to be the same ring under different names. A worked assignment problem shows the complex numbers to be a ring of real matrices.
Rings
abstract algebra · rings · integral domains · fields · subrings · direct products · proofs
The third unit of a rings-first abstract algebra course. The definition of a ring, abstracted from the integers and the integers modulo n; the rules that hold in every ring; units and zero divisors in general; integral domains and fields, with the theorem that every finite integral domain is a field; and subrings and direct products, with matrices, functions, the Gaussian and Eisenstein integers and the Gaussian integers modulo n as examples, all proved in full.
Rings: Definition and Examples
abstract algebra · rings · ring axioms · Gaussian integers · matrices · rings of functions · proofs
The definition of a ring, abstracted from the arithmetic of the integers and the integers modulo n. The eight ring axioms and what they leave out, commutative rings and rings with identity, and a catalog of examples (number systems, multiples of n, the Gaussian integers, polynomials, 2 x 2 matrices with a rotation and a reflection that do not commute, and functions under pointwise operations), with systems that fail to be rings and the axiom each one breaks. Worked problems from the course's assignment close the article.
ROC Curves for Diagnostic Tests
statistics · biostatistics · diagnostic tests · ROC curve · AUC · Mann-Whitney · Wilcoxon rank-sum · Youden index · DeLong test · Hanley-McNeil · cut-off · expected cost · diabetes · HbA1c · NHANES
The trade-off between sensitivity and specificity as the cut-off of a continuous test moves. The empirical ROC curve; the area under it as the probability that a person with the condition scores higher than one without, computed as the Mann-Whitney statistic; its standard error by Hanley and McNeil, by DeLong's method and by the bootstrap; comparing two tests on the same patients; and choosing the cut-off by Youden's index or by expected cost. Worked on HbA1c, BMI and age as screens for a diabetic fasting glucose in NHANES adults.
Sample Size for Comparing Two Means
statistics · biostatistics · sample size · power · two-sample t test · study design · crossover trial · NHANES
How many subjects a study comparing two means needs. The per-group sample size formula derived from the power of the two-sample test, the factor of 2 that makes a two-arm trial four times the size of a one-sample study, the exact noncentral t answer and a simulation check on NHANES blood pressures, unequal standard deviations and the optimal allocation, the cost of unequal group sizes, how much a paired or crossover design saves, and what moves the answer. Worked problems on men and women, a 3:1 trial and repeated blood pressure readings.
Sampling Distributions
statistics · biostatistics · sampling distribution · sample mean · standard error · central limit theorem · finite population correction · NHANES
The bridge from probability to inference, the course unit on the sampling distribution of the mean. A sample mean is a random quantity with a distribution of its own, centered on the population mean, narrower than the population by a factor of root n (with a finite population correction when sampling without replacement), and close to normal for large samples whatever the shape of the population, by the central limit theorem; how large is large enough, the Berry–Esseen bound, and where the theorem fails. Worked on NHANES blood pressure and C-reactive protein.
Screening and Diagnostic Tests
statistics · biostatistics · diagnostic tests · screening · sensitivity · specificity · predictive values · Bayes theorem · likelihood ratio · ROC curve · AUC · diabetes · HbA1c · NHANES
How the accuracy of a medical test is measured and what a result means for the person tested. Sensitivity and specificity against a reference standard, with their intervals and the spectrum and verification biases that distort them; predictive values from Bayes' theorem and their dependence on prevalence; likelihood ratios, pre-test and post-test odds and Fagan's nomogram; and ROC curves, the area under them as a Mann-Whitney probability, and the choice of a cut-off by Youden's index or by expected cost. Worked on HbA1c as a screen for undiagnosed diabetes, defined by fasting glucose, in NHANES adults.
Search Applications
information retrieval · search applications · filtering · question answering
A survey of the tasks built on retrieval methods. Desktop and web search, routing and filtering, classification and clustering, summarization, information extraction, topic detection and tracking, expert finding, question answering, and multimedia retrieval.
Search at Scale
information retrieval · web search · distributed systems · efficiency
How a search engine answers queries over an index too large for one machine. Partitioning by document or by term, replication, caching, tiered indexes, multi-stage ranking, tail latency, and keeping the index fresh.
Search in Professional Domains
information retrieval · domain-specific search · legal search · medical search · patent search
How legal, medical, patent, and scholarly search differ from web search. Recall-oriented tasks, authority and citation, controlled vocabularies, the persistence of Boolean queries, and the cost of a missed document.
Selection Pressure and Premature Convergence
evolutionary computation · genetic algorithms · selection · diversity · niching
How strongly a selection scheme favors the best individuals, and what happens when it favors them too much. Fitness-proportional selection and its scaling problems, stochastic universal sampling, ranking, tournament and truncation selection, takeover time and selection intensity measured against theory, elitism, and the niching methods that keep a population diverse.
Sensitivity and Specificity
statistics · biostatistics · diagnostic tests · screening · sensitivity · specificity · reference standard · spectrum bias · verification bias · confidence intervals · diabetes · HbA1c · fasting plasma glucose · NHANES
How the accuracy of a diagnostic or screening test is measured against a reference standard. The 2 x 2 table, sensitivity and specificity as conditional probabilities and why accuracy is a poor summary; what changes when the reference standard is itself a definition, shown by reading the same table with each test as the reference; Wilson intervals and the number of cases a study needs; how sensitivity depends on the severity and make-up of the cases, spectrum bias in studies of severe cases and healthy controls, and verification bias with the Begg-Greenes correction. Worked on HbA1c as a screen for undiagnosed diabetes, defined by fasting glucose, in NHANES adults, with worked problems on a second cut-off, the size of an accuracy study, the correction on one verified sample and a different case mix.
Skip Pointers
information retrieval · Boolean retrieval · algorithms · indexing
Shortcuts stored within postings lists that let an intersection jump over entries that cannot match. How the skip algorithm works, a traced example with a diagram and an interactive stepper, the square-root placement heuristic derived as a cost trade-off and tested by experiment, and how skipping works in compressed, block-based indexes. Worked problems on unions, on a traced intersection with and without skips, and on the cost model.
Speciation in NEAT
evolutionary computation · neuroevolution · NEAT · speciation · fitness sharing · niching
How NEAT protects new network structure by dividing its population into species. The compatibility distance and the coefficients the original experiments used, assignment of genomes to species by representatives, explicit fitness sharing and offspring allocation, stagnation and elitism, dynamic thresholds that target a species count, and an experiment on XOR with speciation switched on and off and with different thresholds.
Spelling Correction and Phonetic Matching
information retrieval · text processing · spelling correction · edit distance
Matching query terms that are misspelled or spelled differently from the documents. Edit distance and its dynamic-programming computation, k-gram indexes for finding candidates, context-sensitive correction, the noisy channel model, and Soundex.
Standard Scores, Chebyshev's Inequality and Grouped Data
statistics · biostatistics · descriptive statistics · z-score · standard score · empirical rule · Chebyshev's inequality · grouped data · Sheppard's correction · standard deviation · NHANES
The standard deviation used as a ruler. z-scores, which have mean 0 and standard deviation 1; the empirical rule checked against NHANES 2017-2018 heights, blood pressures, body mass index and household size; Chebyshev's inequality proved, for population and sample standard deviations; and the mean, standard deviation, median and quartiles recovered from a frequency table, with Sheppard's correction and the effect of a recording lattice.
Stemming and Lemmatization
information retrieval · text processing · stemming · lemmatization · morphology
Reducing related word forms to a common index term. Inflection and derivation, stemming compared with lemmatization, the Lovins, Porter, Paice/Husk, Krovetz, and Snowball stemmers, typical errors, and what experiments show about the effect on retrieval.
Stop Words
information retrieval · text processing · stop words
Very common words that carry little information about a document's subject. How stop lists are built, what removing them saves and costs, alternatives to removal, and why web search engines largely stopped using them.
Strengths and Limits of the Vector Space Model
information retrieval · vector space model · relevance feedback · Rocchio
What the vector space model does well, the assumptions behind it, and where they fail. Term independence and vocabulary mismatch, the lack of a theory of relevance, Rocchio relevance feedback with two worked examples, and the model's descendants in latent semantic indexing, BM25, and dense retrieval.
Subgroups and Cyclic Groups
abstract algebra · groups · subgroups · subgroup test · center · cyclic groups · generators · subgroup lattice · dihedral groups · proofs
Groups inside groups. The definition of a subgroup and the tests that make checking one quick, including the one-step test and the test for finite subsets; the center, with the scalar matrices as the center of GL_2(R); the cyclic subgroup generated by one element, whose size is that element's order; cyclic groups, which are abelian, and the theorem that every subgroup of a cyclic group is cyclic, with exactly one subgroup of each order dividing n in a cyclic group of order n and phi(n) generators; the nine subgroups of Z_36 and the 19 subgroups of the octagon's group D_8; subgroups generated by several elements; and when Z_m x Z_n is cyclic.
Subrings and Direct Products of Rings
abstract algebra · rings · subrings · subring test · direct products · Eisenstein integers · proofs
Two ways to get new rings from old. Subrings are subsets that are rings under the same operations, recognized by a three-condition subring test proved in full and applied to the Eisenstein integers, a commutative ring of upper triangular matrices, and rings of functions; subrings can have a different identity from the whole ring. Direct products combine two rings coordinatewise; their identity, units and zero divisors are found, and Z_3 x Z_7 is compared with Z_21 and Z_4 x Z_6 with Z_24. Worked problems from the course's assignment on subrings close the article.
Symbolic Regression
evolutionary computation · genetic programming · symbolic regression · model discovery · overfitting
Searching for the formula that fits a set of data, not only its coefficients. Koza's quartic and the course's quadratic, fitness on sample points and the hits criterion, ephemeral random constants, a seeded series of 30 runs with the evolved formulas simplified, what the sample points cannot see, overfitting on noisy data, and what modern systems and benchmarks show.
Symmetric Groups and Permutations
abstract algebra · groups · symmetric groups · permutations · cycle notation · transpositions · parity · alternating groups · conjugation · proofs
The symmetric group S_n of all permutations of n objects, with n! elements and composition as its operation. Two-line and cycle notation, the theorem that every permutation is a product of disjoint cycles in essentially one way (proved by sorting the objects into orbits), orders as least common multiples of cycle lengths, cycle types and how many permutations have each, conjugation as relabeling, products of transpositions, the proof that parity is well defined by counting cycles, the alternating group of order n!/2, and parity arguments for the 15 puzzle and the Rubik's cube.
Tables and Graphs for Data
statistics · biostatistics · descriptive statistics · frequency table · histogram · bar chart · box plot · frequency polygon · empirical distribution function · scatter plot · NHANES
How to show a distribution. Frequency, relative frequency and cumulative tables; bar charts for categories; histograms for measurements, with the bin rules of Sturges, Scott and Freedman and Diaconis and the density scale that unequal classes require; frequency polygons for comparing groups of different sizes; the empirical distribution function; box plots with Tukey's fences; scatter plots and line graphs; and a truncated axis that turns a 15% difference into an eightfold one. All drawn from the blood pressures of 5,247 NHANES 2017-2018 adults.
Term Dependence Models
information retrieval · probabilistic models · term dependence · proximity · Markov random fields · ranking
Ranking beyond the bag of words. Why every model in the unit assumes that query terms occur independently and what that discards, shown on two documents with the same term counts; the Markov random field model of Metzler and Croft with its graph, its full independence, sequential dependence and full dependence variants, its potentials over single terms, ordered windows and unordered windows, and the ranking function derived from the joint distribution; the sequential dependence model computed by hand and run on all 225 Cranfield queries against query likelihood; proximity terms added to BM25; and the positional index that makes these features computable. Worked problems on cliques, window counts and feature values.
Term Statistics: Zipf's Law and Heaps' Law
information retrieval · text processing · statistics · Zipf's law
How term frequencies are distributed in a collection and how vocabulary grows with collection size. Zipf's law, Heaps' law, collection and document frequency, and what the two laws imply for stop words, indexing, and compression.
Test Collections and the Cranfield Paradigm
information retrieval · evaluation · test collections · TREC
The standard apparatus for evaluating retrieval systems. Documents, information needs expressed as topics, and relevance judgments; the major collections from Cranfield to TREC, CLEF, NTCIR, and MS MARCO; and the rules for using a collection without fooling oneself.
Tests and Sample Size for a Proportion
statistics · biostatistics · hypothesis testing · proportions · z test · exact binomial test · power · sample size · NHANES · hypertension
Testing whether a population proportion equals a stated value. The one-sample z test and why its standard error uses the null value, its exact equivalence to Wilson's interval, the exact binomial test, and the actual Type I error of each computed exactly; power and the sample size formula derived from it, with the sawtooth that discreteness puts in exact power; and the sample size needed to estimate a proportion to a given margin. Worked on hypertension among young men in NHANES against the national prevalence. Worked problems on post-traumatic stress disorder among 746 clinic patients, the power of a study of young women, and the sample size for a margin of four points.
Text Classification
information retrieval · text classification · machine learning
Assigning documents to predefined categories by learning from labeled examples. The classification problem, Naive Bayes and its two event models, feature selection, evaluation with micro- and macro-averaging, vector space classifiers, and experiments on Reuters-21578 and Goodreads reviews.
Text Clustering
information retrieval · clustering · unsupervised learning · k-means
Grouping documents by similarity without predefined categories. The cluster hypothesis tested on Cranfield, the k-means algorithm and why it converges, initialization, cluster labels and choosing K, model-based clustering with the EM algorithm, measuring cluster quality with purity, NMI, and the Rand index, hierarchical clustering, and clustering Goodreads reviewers.
Text Processing and Indexing
information retrieval · text processing · indexing
Turning raw files into index terms and organizing those terms into an inverted index. Decoding, tokenization, stop words, normalization, stemming, spelling correction, and how indexes are built and compressed.
TF-IDF Weighting
information retrieval · vector space model · TF-IDF · term weighting
The standard way to weight terms in the vector space model. Term frequency and the bag-of-words view, document frequency and inverse document frequency, their product as a term weight, a four-document running example worked by hand, a worked example on Reuters statistics, and the theoretical arguments for IDF.
The (1+1) ES and the 1/5 Success Rule
evolution strategies · evolutionary computation · step-size adaptation · continuous optimization
The simplest evolution strategy, one parent and one Gaussian mutant per generation, and the rule that keeps its step size in proportion. Rechenberg's progress-rate analysis on the sphere and corridor models, the optimal success probabilities 0.27 and 0.184 behind the 1/5 rule, its implementations, linear convergence measured on the sphere, and why the rule cannot help on an ill-conditioned ellipsoid.
The 2-Poisson Model and Eliteness
information retrieval · probabilistic models · term frequency · BM25
A model of how often a term occurs in a document, based on whether the document is about the term's concept. Why a single Poisson distribution fails, the 2-Poisson mixture fitted by EM to real Cranfield term counts, the posterior probability of eliteness, the eliteness term weight computed from relevance judgments, and how its shape became BM25's term frequency saturation.
The Architecture of a Search Engine
information retrieval · foundations · search engines · indexing
The indexing process and the query process, a four-document collection carried through every stage, and why the contents of the index decide which ranking models are possible.
The Bernoulli Model and Why Naive Bayes Works
information retrieval · text classification · Naive Bayes · probabilistic models
The second event model for Naive Bayes, which records only which terms are present and absent. Its generative story and estimates, derived as maximum likelihood, the worked example where it disagrees with the multinomial model term by term, its log odds as a linear classifier whose weights are the Binary Independence Model's, how the two models compare on Reuters as the vocabulary grows, and why a classifier built on a false independence assumption classifies well while its probabilities, measured on Reuters, are badly calibrated.
The Binomial Distribution
statistics · biostatistics · probability · Bernoulli trials · binomial distribution · clustering · design effect · NHANES
The first of the three theoretical distributions of the course. Bernoulli trials and the binomial probability derived by counting; the mean np and variance np(1 - p) proved two ways; the shape of the distribution and its mode; and what happens when the conditions fail, with unequal probabilities, and with dependence between trials shown on repeated blood pressure readings and on clustering by survey location in NHANES. Worked problems on diabetes among seven older adults, television hours among twenty students, days of high carbon monoxide and a clustered sample of 25.
The Boolean Retrieval Model
information retrieval · Boolean retrieval · retrieval models
Retrieval as exact logical matching. Documents as sets of terms, queries as expressions in AND, OR, and NOT, evaluation with the incidence matrix worked row by row, queries as regions of a Venn diagram, bit vectors as filters, normal forms and their blow-up, and why the model's precision and predictability come with the problem of too many or too few results. Worked problems on an incidence matrix, on the result sets a query can return, and on a conversion to disjunctive normal form.
The Central Limit Theorem
statistics · biostatistics · central limit theorem · sampling distribution · normal approximation · Berry–Esseen theorem · Cauchy distribution · heavy tails · C-reactive protein · NHANES
Why sample means are approximately normal whatever the shape of the population, and how far to trust it. The Lindeberg–Lévy theorem stated and read carefully; exact distributions of exponential means; how fast the approximation works, with the skewness of a mean proved to fall as one over root n, and NHANES blood pressure against the far more skewed C-reactive protein; the Berry–Esseen bound; and failures under infinite variance (Cauchy, Pareto) and dependence. The proofs are in a companion article. Worked problems on albumin means, exponential means, C-reactive protein and correlated observations.
The Chi-Squared and t Distributions
statistics · biostatistics · chi-squared distribution · t distribution · Student · degrees of freedom · Helmert's matrix · normal samples · proofs
The two distributions behind Student's t interval, with full proofs. The chi-squared distribution defined as a sum of squared standard normal variables, with its mean, variance and density; a proof by an orthogonal rotation (Helmert's matrix) that for a normal sample the mean is normal, the scaled variance is chi-squared with n - 1 degrees of freedom, and the two are independent; the t distribution defined, the theorem that Student's ratio has it, and its density and variance. Worked problems on the rotation by hand and on an interval for the standard deviation.
The Chinese Remainder Theorem
abstract algebra · number theory · Chinese remainder theorem · congruences · ring isomorphisms · Euler's phi function · idempotents · proofs
Simultaneous congruences to relatively prime moduli have a solution, unique modulo the product, found from Bezout's identity; with a common factor, a solution exists exactly when the remainders agree modulo the gcd. In the language of rings, Z_mn is isomorphic to Z_m x Z_n exactly when gcd(m, n) = 1, proved in full with Z_45 and Z_5 x Z_9 as the running example. Idempotents, computing powers and products through the isomorphism, square roots of 1, RSA decryption in the form of RFC 8017, Euler's phi as a product, any number of moduli with Sunzi's puzzle, and the same theorem for polynomials. A worked assignment problem shows that (x, y) -> 4x + 9y is an isomorphism from Z_3 x Z_4 onto Z_12.
The Deep Web
information retrieval · web crawling · deep web
The part of the web a link-following crawler cannot reach. Private sites, content behind search forms, and pages built by scripts, how large the deep web was estimated to be, and how crawlers reach some of it through form surfacing, script rendering, and sitemaps. Estimating index and web sizes by capture and recapture, and worked problems, including the informativeness test run on a synthetic form.
The Division Algorithm
abstract algebra · number theory · integers · division algorithm · well-ordering · proofs
Why every integer divided by a positive integer leaves exactly one quotient and one remainder. The well-ordering principle, a full proof of existence and uniqueness, the floor formula, why programming languages disagree about negative remainders, sorting the integers by remainder, and the result that two integers leave the same remainder exactly when their difference is a multiple of the divisor, with applications to last digits.
The Evolutionary Algorithm Loop
evolutionary computation · foundations · evolutionary algorithms · optimization · search
What an evolutionary algorithm is. The three kinds of problem it can be applied to, the general scheme of representation, population, parent selection, recombination, mutation, survivor selection and termination, a complete run traced by hand on OneMax, what the loop costs compared with simpler methods, and where it is and is not the right tool.
The First Isomorphism Theorem for Groups
abstract algebra · groups · homomorphisms · kernels · first isomorphism theorem · quotient groups · normal subgroups · Rubik's cube · circle group · proofs
The quotient of a group by the kernel of a homomorphism is isomorphic to the image, proved in full, with the counting rule |G| = |kernel| x |image| and a recipe for recognizing quotient groups. Worked cases: Z_36 modulo the multiples of 9 as Z_9, S_n/A_n, cyclic groups as quotients of Z, the reals modulo the integers as the circle group, and Cayley's theorem in one line. The Rubik's cube group mapped to the positions of its cubies, with its order as kernel times image. The ring theorem as a consequence.
The Integers Modulo n
abstract algebra · number theory · modular arithmetic · integers modulo n · well-defined · proofs
The congruence classes modulo n as a number system. The set Z_n, the proof that adding and multiplying classes through their representatives is well defined, operations that look reasonable and are not, the laws of arithmetic in Z_n and how they are inherited from the integers, the addition and multiplication tables of Z_13, a quadratic equation with eight solutions in Z_24, powers by repeated squaring, and unsigned integers in computers as arithmetic modulo 2^32.
The Inverted Index
information retrieval · indexing · inverted index · data structures
The data structure behind nearly every search engine. Why scanning text and the term-document incidence matrix do not scale, the dictionary and postings lists, building an index by sorting term-document pairs, dictionary data structures, and what postings can store.
The k-means Algorithm
information retrieval · clustering · k-means · algorithms
The standard flat clustering algorithm. The residual sum of squares objective, the assignment and update steps, a worked example traced by hand, the proof that the algorithm converges, why it finds only a local minimum, and what it costs on text.
The Kruskal-Wallis Test
statistics · biostatistics · nonparametric methods · Kruskal-Wallis test · ranks · analysis of variance · multiple comparisons · Dunn's test · NHANES
Comparing several independent groups by ranks. The Kruskal-Wallis statistic H derived as the analysis of variance of the ranks, its two computing formulas and the correction for ties, its chi-squared approximation checked against exact enumeration and simulation, its reduction to the rank-sum test for two groups, worked on the NHANES blood pressures of four age groups used for one-way ANOVA; what it tests, how it behaves when spreads differ, its power against the F test, and Dunn's follow-up comparisons of mean ranks. Worked problems on Kruskal and Wallis's bottle-cap data, an exact distribution listed by hand, two groups, and three of the four age groups.
The Normal Approximation to the Binomial
statistics · biostatistics · binomial distribution · normal approximation · sample proportion · continuity correction · sampling distribution · NHANES · hypertension
How a sample proportion behaves from sample to sample. The binomial count and the sample proportion as sums of yes-or-no observations, their mean and standard error derived, the normal approximation and the continuity correction, checked against exact binomial and hypergeometric probabilities for samples of young adults from NHANES with hypertension as the outcome; why skewness, and so the product np, decides when the approximation can be trusted. Worked problems on coronary heart disease among 40 women, a sample of 200 without replacement, and the sample size at which the skewness falls to 0.1.
The Normal Distribution
statistics · biostatistics · probability · normal distribution · Gaussian distribution · probability density function · standard normal · z-scores · empirical rule · normal probability plot · Q-Q plot · Shapiro-Wilk test · Box-Cox transformation · NHANES
Continuous random variables and the normal distribution. Densities and distribution functions; the normal density, with proofs that it integrates to 1 and has mean mu and variance sigma squared; standardization and the standard normal table; the 68-95-99.7 rule; checking normality with histograms, normal probability plots and the Shapiro-Wilk test; the log, reciprocal and Box-Cox transformations; and why the normal curve arises. Worked on the heights and systolic blood pressures of NHANES adults, with worked problems on the weights of adult males, a change of units, the quartiles of the height model and blood pressure on three scales.
The Paired Samples t-Test
statistics · biostatistics · hypothesis testing · paired t test · crossover trial · matched pairs · NHANES
Comparing two means when each subject is measured twice or subjects come in matched pairs. Paired and independent designs, why pairing removes the variation between subjects (the variance of a difference derived), the paired t-test as a one-sample test on the differences, worked on Student's sleep data with its interval and one-sided bound, what ignoring the pairing does to the same data, a large-scale check on repeated NHANES blood pressure readings, and when pairing costs more than it gains. Worked problems on saliva cotinine after a cigarette, with and without the pairing, and on a test against a nonzero threshold.
The Poisson Distribution
statistics · biostatistics · probability · Poisson distribution · rare events · Poisson process · exponential distribution · index of dispersion · horse kicks · normal approximation
The distribution of counts of rare events. The Poisson probability derived as the limit of the binomial, with its mean and variance both equal to lambda; sums of independent Poisson counts; the Poisson process, its time scaling and exponential waiting times; Bortkiewicz's horse-kick deaths in the Prussian army, tested with Fisher's index of dispersion; and the normal approximation with its unequal tails. Worked problems on the Poisson approximation, the horse-kick table and a process at 2 events per hour.
The Porter Stemmer
information retrieval · text processing · stemming · algorithms
The most widely used English stemmer, rule by rule. The measure of a stem, the conditions on rules, the five steps of suffix removal with the examples from Porter's paper, worked traces, and the algorithm's known faults and variants.
The Probability Ranking Principle
information retrieval · probabilistic models · ranking
Why a search engine should sort documents by their probability of relevance, a step-by-step proof that this ordering is optimal, the version with retrieval costs and the stopping threshold it implies, a worked ambiguous query on which the principle fails, and the assumptions behind it.
The RSA Cryptosystem
abstract algebra · number theory · cryptography · RSA · public-key cryptography · modular arithmetic · proofs
Public-key encryption from modular arithmetic. The key-distribution problem and Diffie and Hellman's proposal, the construction of an RSA key with a worked example of our own (n = 3053, e = 13, d = 1357), encryption and decryption by repeated squaring, a full proof that decryption recovers every message, including messages that share a factor with n, signatures, how keys are made in practice, and why RSA is believed secure, with what is and is not known about its relation to factoring, and a worked problem from the course's assignment.
The Rubik's Cube Group
abstract algebra · groups · Rubik's cube · permutation groups · generators · orders of elements · parity · commutators · conjugation · Schreier-Sims algorithm
The moves of a Rubik's cube form a nonabelian group generated by six quarter turns, modeled here as permutations of the 48 movable stickers. Why move sequences are read left to right, which face turns commute, the orders of moves such as RU (105) and R U R' U' (6) read from how they cycle and twist the pieces, the largest order 1260, the three invariants (equal corner and edge parity, total twist, total flip) and the count of 43,252,003,274,489,856,000 positions, confirmed by the Schreier-Sims algorithm; subgroups, commutators and conjugates as solving tools, the superflip, and the proof that every position can be solved in 20 face turns.
The Rules of Probability
statistics · biostatistics · probability · axioms of probability · sample space · events · addition rule · inclusion-exclusion · independence · mutually exclusive events · Boole's inequality · NHANES
The axioms of probability and the rules that follow from them. Sample spaces, events, unions, intersections and complements; equally likely outcomes and long-run relative frequency; the three axioms; the complement rule, monotonicity, the addition rule and inclusion-exclusion, each proved; Boole's inequality behind the Bonferroni correction; and independence, for two events and for several, with a proof that mutually exclusive events cannot be independent. Worked on dice and on hypertension, obesity and diabetes among NHANES adults, with worked problems on counting the adults with exactly one, two or three conditions, bounds on a union, independence of dice events, repeated draws and inclusion-exclusion for four events.
The Sampling Distribution of the Mean
statistics · biostatistics · sampling distribution · sample mean · standard error · finite population correction · unbiased estimator · NHANES
How a sample mean varies from sample to sample. The population, the sample and the sampling distribution distinguished on NHANES blood pressures; every sample of a five-person population enumerated; proofs that the sample mean is centered on the population mean and has standard error sigma over root n; the finite population correction for sampling without replacement, derived and checked; the standard error versus the standard deviation; how the shape of the sampling distribution changes with n; and the sampling distribution of the median for comparison. Worked problems on the mean weight of 25 men, every sample of three from five adults, and the sample size for a given standard error.
The Sign Test and the Wilcoxon Signed-Rank Test
statistics · biostatistics · nonparametric methods · sign test · Wilcoxon signed-rank test · ranks · paired data · asymptotic relative efficiency · NHANES
Testing paired differences, or one sample against a hypothesized center, by signs and ranks instead of a normal model. The sign test as an exact binomial test, Wilcoxon's signed-rank statistic with its exact null distribution computed by enumerating the sign patterns, its mean and variance derived, the normal approximation with corrections for ties and zero differences, worked on Student's sleep data, Wilcoxon's own 1945 example and repeated NHANES blood pressure readings; what each test actually tests, and their efficiency and robustness against the paired t-test by simulation. Worked problems on the second sleeping drug, the smallest sample that can reject and the tie correction.
The Simple Genetic Algorithm
evolutionary computation · genetic algorithms · selection · crossover · algorithms
Holland's and Goldberg's canonical genetic algorithm, specified completely. Bit strings, fitness-proportional selection, one-point crossover, bit-flip mutation and generational replacement; Goldberg's x-squared example recomputed by hand; a seeded run that converges prematurely; the classic parameter settings of De Jong, Grefenstette and Schaffer; and measured weaknesses that later variants were designed to fix.
The Surprising Creativity of Digital Evolution
evolutionary computation · fitness functions · specification gaming · reward hacking · AI safety
Evolutionary algorithms routinely satisfy the letter of a fitness function rather than its intent. The anecdotes collected by Lehman and colleagues (2020), the same phenomenon in reinforcement learning as specification gaming and reward hacking, why it happens, a small GA that games a sorting test and the fix, and practical lessons for writing fitness functions.
The Text Classification Problem
information retrieval · text classification · machine learning
What text classification is and how it is set up. Standing queries as classifiers, hand-written rules versus supervised learning, binary, multiclass, and multilabel tasks, training and test data, and the applications that make classification one of the most widely deployed uses of retrieval methods.
The Two-Sample t-Test
statistics · biostatistics · hypothesis testing · two-sample t test · pooled variance · independent samples · NHANES
Comparing the means of two independent groups. The sampling distribution of a difference in means, the pooled two-sample t-test derived from a common variance with a full proof that its statistic has the t distribution on n1 + n2 - 2 degrees of freedom, the interval for the difference, worked on NHANES blood pressures of 20 men and 20 women, and the bias of the pooled standard error when the variances differ. A worked problem on the bone mineral content of newborns. Welch's test for unequal variances has its own article.
The Vector Space Model
information retrieval · vector space model · ranking · TF-IDF
Ranked retrieval by representing documents and queries as weighted term vectors and scoring documents by their similarity to the query. Zones and weighted zone scoring, TF-IDF, cosine similarity, efficient scoring with an inverted index, weighting variants, the formal constraints a term weighting should satisfy, and document-to-document similarity.
The Wilcoxon Rank-Sum Test
statistics · biostatistics · nonparametric methods · Wilcoxon rank-sum test · Mann-Whitney U test · ranks · two-sample test · asymptotic relative efficiency · NHANES
Comparing two independent groups by ranks. Wilcoxon's rank sum W and Mann and Whitney's U shown to be the same test, the exact null distribution from Mann and Whitney's recurrence and by counting arrangements, the mean and variance derived with the correction for ties, the normal approximation, worked on NHANES blood pressures; what a rejection shows (that one group's values tend to exceed the other's, not that the medians differ in general), stated here and established in a companion article, and its efficiency (3/pi under normality) and robustness against the two-sample t-test. Worked problems on the exact distribution for two samples of four and on two age groups.
Theoretical Probability Distributions
statistics · biostatistics · probability · random variables · expectation · variance · binomial distribution · Poisson distribution · normal distribution · overdispersion · normal probability plot · NHANES · mortality
Random variables and the three distributions that describe much of the data in medicine. Probability mass and density functions, distribution functions, expectation and variance; the binomial for successes in a fixed number of independent trials, the Poisson for counts of rare events and events in time, and the normal for measurements; each derived and proved, and each tested on real data, including what happens when trials are clustered, when a rate varies, and when measurements are skewed. Worked on NHANES adults, Bortkiewicz's horse-kick deaths and NCHS weekly death counts.
Token Normalization
information retrieval · text processing · normalization · Unicode
Mapping tokens that differ superficially to the same index term. Equivalence classes, case folding, punctuation, accents and diacritics, Unicode normalization, and the choice between normalizing the index and expanding the query.
Tokenization
information retrieval · text processing · tokenization
Splitting a character sequence into tokens. Words, tokens, types, and terms; apostrophes, hyphens, numbers, and names; languages without spaces and with long compounds; and subword tokenization.
Topic Modeling
information retrieval · topic modeling · LSI · LDA · unsupervised learning
Representing documents by latent themes instead of words. Latent semantic indexing with the singular value decomposition, probabilistic latent semantic analysis, latent Dirichlet allocation and its inference, evaluating topic models by perplexity and coherence, and extensions from dynamic topic models to neural and embedding-based methods, with experiments on Cranfield and Reuters.
Topic Models Beyond LDA
information retrieval · topic modeling · NMF · neural topic models
Where topic modeling went after LDA. Topic models as smoothing for retrieval, models with correlated, evolving, supervised, and author-specific topics, nonparametric models that infer the number of topics, nonnegative matrix factorization compared with LDA on Reuters, and neural, embedding-based, and language-model-based approaches.
Two-Way Analysis of Variance
statistics · biostatistics · hypothesis testing · analysis of variance · two-way ANOVA · interaction · indicator variables · regression · sums of squares · NHANES
The analysis of variance as a regression on indicator variables, and its extension to two factors and their interaction. The regression identities for the one-way analysis, the partition of the total sum of squares of a two-way layout with equal cell sizes proved, the three F tests stated, and an example on NHANES blood pressures by age group and sex.
Type I and Type II Errors
statistics · biostatistics · hypothesis testing · Type I error · Type II error · power · Neyman-Pearson · NHANES
The two ways a hypothesis test can reach the wrong decision, measured by simulation on NHANES blood pressures. Neyman and Pearson's framing of tests as rules with controlled error rates, why p-values are uniform when the null hypothesis is true, how the Type II error rate depends on the true mean and the sample size, the trade-off between the two errors, practices that inflate the Type I rate (optional stopping, choosing the side, many tests), and what an error rate does not say about a single study. Worked problems on the Type II error rate of a z test, on many tests and on false discoveries.
Types of Numerical Data
statistics · biostatistics · descriptive statistics · levels of measurement · nominal · ordinal · discrete · continuous · ranks · NHANES
What kind of measurement a variable is, and why it matters for every summary computed from it. Nominal, ordinal, discrete and continuous data illustrated on one NHANES 2017-2018 participant's record and the 5,247 adults it comes from; Stevens's 1946 scales of measurement and the statistics each permits; a proof that group means of an ordinal rating can be reordered by recoding unless one group's cumulative distribution lies above the other's; ranks; how recording rules (even-numbered blood pressures, top-coded age and household size) shape continuous and discrete data; and the criticism that scale type depends on the question asked.
Units and Zero Divisors in the Integers Modulo n
abstract algebra · number theory · modular arithmetic · units · zero divisors · Bezout's identity · proofs
Which classes in Z_n can be inverted. Units and their inverses, the theorem that [a] is a unit exactly when gcd(a, n) = 1, proved with Bezout's identity, inverses computed by the extended Euclidean algorithm, zero divisors and the proof that every nonzero class is a unit or a zero divisor and never both, the characterization of prime moduli, cancellation, the linear equation ax = b and its number of solutions, the group of units and Euler's phi function, and Wilson's theorem.
User Models Behind Retrieval Metrics: RBP and ERR
information retrieval · evaluation · user models · rank-biased precision · expected reciprocal rank · cascade model
Retrieval measures as expected utility under a model of how a user reads a ranking. The position-based reading of precision at k and of the DCG discount; rank-biased precision derived from the persistence model, with its residual, the bound on what unjudged documents could add; the cascade model and expected reciprocal rank derived from it; average precision under Robertson's stopping model. Each measure computed on the unit's worked ranking and on Cranfield, with the derived identities checked by simulation.
Variants of TF-IDF Weighting
information retrieval · vector space model · TF-IDF · term weighting
Refinements to the basic TF-IDF weight. Sublinear (logarithmic) term frequency, maximum term frequency normalization, the SMART notation for weighting schemes with worked lnc.ltc examples and eight schemes compared on one collection, and pivoted document length normalization, derived geometrically and repeated on Cranfield.
Variational Inference for LDA
information retrieval · topic modeling · LDA · variational inference · Bayesian inference
Fitting latent Dirichlet allocation by optimization instead of sampling. The expected logarithm of a Dirichlet, the factorized family and the evidence lower bound, the two coordinate updates each proved to be a maximum, the M-step for the topics, and the bound traced on the six documents, where it rises at every step and stays below the exact evidence.
Vector Space Classification
information retrieval · text classification · vector space model · nearest neighbors
Classifying documents by their position in the vector space of terms. The contiguity hypothesis, Rocchio classification with class centroids and its linear boundary derived, k nearest neighbors and its Voronoi regions, both worked on a two-dimensional example with an interactive demo, why Rocchio fails for diffuse classes, kNN's accuracy as k varies on Reuters, a comparison with Naive Bayes, linear classifiers, the support vector machine and its margin 2/‖w‖, and the bias-variance trade-off measured on simulated data.
Web Crawling
information retrieval · web crawling · web search
How search engines and other programs gather pages from the web. What a crawler must and should do, politeness and robots.txt, crawler architecture and the URL frontier, duplicate detection, freshness, the deep web, distributed crawling and connectivity servers, PageRank, and monitoring individual sites.
Weighted Sums and the ε-Constraint Method
evolutionary computation · multi-objective optimization · scalarization · optimization
Classical scalarization of multi-objective problems. Why a weighted sum of objectives reaches only the points of the front on the lower boundary of its convex hull, and spreads them unevenly even then; the ε-constraint method; Tchebycheff and achievement scalarizing functions; and when solving scalarized problems beats an evolutionary multi-objective algorithm, with a sweep of all three methods on ZDT1 and ZDT2.
Welch's t-Test and Unequal Variances
statistics · biostatistics · hypothesis testing · Welch test · unequal variances · Satterthwaite · Behrens-Fisher problem · F test · NHANES
Comparing the means of two independent groups without assuming equal variances. Welch's statistic and the Satterthwaite degrees of freedom derived by matching moments, a statement of exactly which steps are approximations, proved bounds on the degrees of freedom and a proof that the approximation is exact only for equal weights, worked on NHANES blood pressures of younger and older adults, simulations of when the pooled test fails, why a preliminary F test of the variances is discouraged, and intervals for the difference. Worked problems on the bone mineral content of newborns.
What a Web Crawler Does
information retrieval · web crawling
The crawl loop from seed URLs to fetched, parsed, and indexed pages, the parts of a URL a crawler works with, and the features a crawler must provide (robustness and politeness) and should provide (quality, scalability, efficiency, distribution, freshness, and extensibility). The bow-tie shape and power-law degrees of the web graph, and what they mean for a crawl from given seeds. Worked problems on the toy crawl and on in-degree distributions.
What Information Retrieval Is
information retrieval · foundations
The problem retrieval systems solve, the vocabulary used to describe it, why ambiguity and vocabulary mismatch make it hard, and how retrieval differs from databases, NLP, and recommendation.
What Is Topic Modeling
information retrieval · topic modeling · unsupervised learning
The idea behind topic models. The vocabulary mismatch problem, topics as distributions over words and documents as mixtures of topics, how topic models differ from clustering and classification, preparing text for them, and what they are used for in retrieval and beyond.
What the Rank-Sum Test Tests
statistics · biostatistics · nonparametric methods · Wilcoxon rank-sum test · Mann-Whitney U test · shift model · probability of superiority · Behrens-Fisher problem · Hodges-Lehmann estimator · NHANES
What a rejection by the Wilcoxon rank-sum (Mann-Whitney) test shows. The test responds to theta, the probability that a value from one population exceeds a value from the other; it compares medians or means only under a shift model, which is proved; simulations of equal medians with different shapes and of equal centers with unequal spreads, where the test does not hold its level; the variance of U when the two distributions differ, with the rejection rates it predicts; and the Hodges-Lehmann estimate and interval for a shift.
Wildcard Queries
information retrieval · text processing · wildcard queries · permuterm index · k-gram index · B-tree · data structures
How a dictionary answers patterns such as mon*, *mon, m*n and m*n*r. Hash tables against search trees and B-trees for prefix lookup, a tree and a reverse tree for trailing and leading wildcards, the permuterm index with its rotation rule for each query form, and the k-gram index with its Boolean query and post-filtering step. Every technique worked on twenty Reuters terms, both indexes built and measured on the whole Reuters-21578 vocabulary, and what a wildcard costs in terms and postings.
Zones and Weighted Zone Scoring
information retrieval · vector space model · ranking · zones · machine learning
Using document structure in retrieval. Metadata fields and parametric search, zone indexes, scoring documents by which zones match the query, and learning the zone weights from relevance judgments, with a derivation, a traced ZoneScore merge, the learned weight read as a regression, and a three-zone example.