Patterns
Market-basket rules, Apriori pruning, PageRank and recommendation, computed as contractions over matrices of ones and zeros or ratings.
Prelude.Patterns finds what goes with what, and who matters. It covers association-rule mining
(support, confidence, lift, leverage and conviction, with Apriori’s pruning up to sets of three),
PageRank over a link matrix, item-item collaborative filtering, and matrix factorisation of a
partly-observed rating matrix by gradient descent.
Conventions: a basket matrix a is n×m with one row per basket (transaction) and one column per
item, holding 1 when the basket contains the item and 0 otherwise. Supports are fractions of
baskets. Every rule table is m×m and entry \([t, u]\) is always the rule “\(t\) implies \(u\)”
(antecedent in the row, consequent in the column). A rating matrix r is users×items with 0 for
“not rated”. A link matrix g is n×n with \(g_{ij} = 1\) when page \(i\) links to page \(j\).
Limitations: frequent sets stop at three items, because an m×m×m table over ten thousand items already has \(10^{12}\) cells; beyond that a different algorithm (such as FP-growth) is needed, not a bigger tensor. Matrix factorisation uses gradient descent rather than alternating least squares.
open Prelude.Patterns
Support
The support of an item set is the fraction of baskets containing all of it. Pairwise co-occurrence is a single contraction,
\[\mathrm{supp}(t, u) = \frac{1}{n} \sum_i a_{it} \, a_{iu}\]with no counting loop and no candidate list.
Throughout the rest of this page, for a basket matrix \(A \in \{0, 1\}^{n \times m}\) we write \(s = \operatorname{support1}(A) \in [0, 1]^m\) and \(S = \operatorname{support2}(A) \in [0, 1]^{m \times m}\).
support1
support1(a) · a basket matrix n×m → vector m
Let \(A \in \{0, 1\}^{n \times m}\) (the argument a) be a basket matrix. Then
The support of each single item: the fraction of baskets that contain it.
Intuition The column mean of a 0/1 matrix, which is the chance that a randomly picked basket holds the item. It is the popularity baseline that every rule measure on this page is compared against.
Use it when you want the best sellers, a first filter that drops rare items before any pair table is built, or the per-item rates that lift and leverage divide out. For a yes/no cut at a minimum support, use frequent1. It costs one pass over the matrix.
market-basket-analysisitem-popularity
def support1(a) ≔ einsum("it->t", a) / baskets(a)
support2
support2(a) · a basket matrix n×m → matrix m×m
Let \(A \in \{0, 1\}^{n \times m}\) be a basket matrix. Then
\[\operatorname{support2}(A)_{tu} = S_{tu} = \frac{1}{n} \sum_{i=1}^{n} A_{it} A_{iu}, \qquad \text{that is} \qquad S = \tfrac{1}{n} A^{\top} A .\]The support of every pair of items. The diagonal repeats support1.
Intuition \(A^{\top} A\) counts, for every pair of columns, the baskets where both are 1. Divided by \(n\), each cell is the joint probability that a basket holds both items. The table is symmetric because co-occurrence has no direction. Direction appears only when you divide by an antecedent, as confidence does.
Use it when you need a co-occurrence heat map, “bought together” counts, or the raw table behind every rule measure. It is a dense m×m table, which is fine for thousands of items but not millions. Narrow the columns first (for example to the items frequent1 keeps).
co-occurrencemarket-basket-analysis
def support2(a) ≔ einsum("it,iu->tu", a, a) / baskets(a)
support3
support3(a) · a basket matrix n×m → tensor m×m×m
Let \(A \in \{0, 1\}^{n \times m}\) be a basket matrix. Then
\[\operatorname{support3}(A)_{tuv} = \frac{1}{n} \sum_{i=1}^{n} A_{it} A_{iu} A_{iv} .\]The support of every triple of items. Entries with a repeated index are the supports of the corresponding smaller sets.
Intuition The same count as support2 with one more factor: a basket counts for \((t, u, v)\) only when all three columns are 1. It finds groups whose pairs look ordinary but which really travel together as a trio.
Use it when you are looking for three-item bundles or checking whether a pair rule depends on a third item. The table has \(m^3\) cells, so 1,000 items already means \(10^9\) cells. Restrict the item columns to a short list before calling it. To keep only triples that pass a threshold, use frequent3.
frequent-itemsetsproduct-bundlingco-occurrence
def support3(a) ≔ einsum("it,iu,iv->tuv", a, a, a) / baskets(a)
Building blocks
baskets(a)— Let \(A \in \mathbb{R}^{n \times m}\). Then \(\operatorname{baskets}(A) = n\). The number of baskets, the row count ofa.itemOnes(a)— Let \(A \in \mathbb{R}^{n \times m}\). Then \(\operatorname{itemOnes}(A) = \mathbf{1}_m\). A vector of ones, one per item.
Rule measures
For the rule \(t \Rightarrow u\):
\[\mathrm{conf} = \frac{\mathrm{supp}(t,u)}{\mathrm{supp}(t)}, \quad \mathrm{lift} = \frac{\mathrm{supp}(t,u)}{\mathrm{supp}(t)\,\mathrm{supp}(u)}, \quad \mathrm{lev} = \mathrm{supp}(t,u) - \mathrm{supp}(t)\,\mathrm{supp}(u), \quad \mathrm{conv} = \frac{1 - \mathrm{supp}(u)}{1 - \mathrm{conf}}\]Confidence alone misleads: a consequent that everybody buys has high confidence from any antecedent. Lift divides that out, so it is 1 when the items are independent, above 1 when they go together and below 1 when they avoid each other. Leverage says the same as a difference rather than a ratio, and conviction measures how often the rule would be wrong if the items were independent. Zero divisors are replaced by one, so an item with zero support gives zeros rather than NaN.
confidence
confidence(a) · a basket matrix n×m → matrix m×m
Let \(A \in \{0, 1\}^{n \times m}\) be a basket matrix, with \(s\) and \(S\) as above. Then
\[\operatorname{confidence}(A)_{tu} = \frac{S_{tu}}{s_t + [\, s_t = 0 \,]} .\]Entry \([t, u]\) is the confidence of \(t \Rightarrow u\): of the baskets containing \(t\), the fraction that also contain \(u\).
Intuition A conditional probability, \(P(u \mid t)\): restrict attention to the baskets holding \(t\) and ask how often \(u\) is there too. It has a direction, so row \(t\) reads “given \(t\)” and the table is not symmetric.
Use it when you want “customers who bought \(t\) also bought \(u\)” suggestions, or a minimum-confidence cut for rules. It flatters popular consequents: an item almost everyone buys gets high confidence from any antecedent. Check lift or conviction before you trust a rule. Items with zero support give a row of zeros, not NaN.
association-rulesrule-rankingnext-item-suggestion
def confidence(a) ≔ support2(a) / safe(heldSupport(a))
lift
lift(a) · a basket matrix n×m → matrix m×m
Let \(A \in \{0, 1\}^{n \times m}\) be a basket matrix, with \(s\) and \(S\) as above. Then
\[\operatorname{lift}(A)_{tu} = \frac{S_{tu}}{s_t s_u + [\, s_t s_u = 0 \,]} .\]Entry \([t, u]\) is the lift of \(t \Rightarrow u\). The table is symmetric.
Intuition Observed co-occurrence divided by what independence would predict. A lift of 2 means the pair turns up together twice as often as chance allows. Dividing by both supports removes the popularity bias that confidence has, and it also removes direction.
Use it when you need to separate real associations from “everyone buys milk”. Filter on lift above 1 for complements and below 1 for substitutes. On rare items the ratio is noisy, because a handful of baskets can give a huge lift. Pair it with a support threshold (frequent2), or rank by leverage, which weights by how many baskets are involved.
association-rulesspurious-associationrule-ranking
def lift(a) ≔ support2(a) / safe(heldSupport(a) · laidSupport(a))
leverage
leverage(a) · a basket matrix n×m → matrix m×m
Let \(A \in \{0, 1\}^{n \times m}\) be a basket matrix, with \(s\) and \(S\) as above. Then
\[\operatorname{leverage}(A)_{tu} = S_{tu} - s_t s_u .\]Entry \([t, u]\) is the observed pair support minus the support expected under independence.
Intuition The same comparison as lift, taken as a difference instead of a ratio. It measures the share of all baskets that the association adds or removes, and \(n\) times the leverage is the number of extra baskets. It always lies between \(-0.25\) and \(0.25\).
Use it when you want to rank rules by practical impact. A pair of rare items that always appear together has a large lift but a tiny leverage, and leverage correctly says it touches few baskets. Like lift, the table is symmetric. For a directional measure, use confidence or conviction.
association-rulesspurious-associationrule-ranking
def leverage(a) ≔ support2(a) − heldSupport(a) · laidSupport(a)
conviction
conviction(a) · a basket matrix n×m → matrix m×m
Let \(A \in \{0, 1\}^{n \times m}\) be a basket matrix, with \(s\) as above, and let \(C = \operatorname{confidence}(A)\). Then
\[\operatorname{conviction}(A)_{tu} = \frac{1 - s_u}{(1 - C_{tu}) + [\, C_{tu} = 1 \,]} .\]Entry \([t, u]\) is the conviction of \(t \Rightarrow u\). Conviction is infinite for a rule with
confidence exactly 1; here the zero divisor is replaced by one, so such a rule (and every diagonal
entry) reports \(1 - \mathrm{supp}(u)\) instead. Check confidence before reading a small conviction
as a weak rule.
Intuition The ratio is \(P(\neg u) / P(\neg u \mid t)\): how many more times the rule “\(t\) implies \(u\)” would fail if the two items were independent than it actually fails. A value of 1 means independence, and larger values mean the rule rarely fails. Unlike lift, it has a direction.
Use it when you need to rank directional rules and want implication strength rather than symmetric association. Read it together with confidence. A rule that never fails (confidence 1) shows \(1 - \mathrm{supp}(u)\) here instead of infinity, and so does the diagonal, so a small value next to confidence 1 means the strongest rule, not a weak one.
association-rulesrule-ranking
def conviction(a) ≔ (1 − laidSupport(a)) / safe(1 − confidence(a))
Building blocks
heldSupport(a)— Let \(A \in \{0, 1\}^{n \times m}\) and \(s = \operatorname{support1}(A)\). Then \(\operatorname{heldSupport}(A)_{tu} = s_t\), that is \(s \, \mathbf{1}_m^{\top}\). m×m table whose entry[t, u]is the antecedent’s support.laidSupport(a)— Let \(A \in \{0, 1\}^{n \times m}\) and \(s = \operatorname{support1}(A)\). Then \(\operatorname{laidSupport}(A)_{tu} = s_u\), that is \(\mathbf{1}_m s^{\top}\). m×m table whose entry[t, u]is the consequent’s support.
Apriori pruning
Apriori’s principle is that a set can only be frequent if all of its subsets are. Over tensors that
is a mask: a pair is allowed only when both items are frequent, and a triple only when all three of
its pairs are. Each frequent table is a 0/1 mask, the product of its own support threshold and the
allowed mask from the level below. The threshold s is a support fraction between 0 and 1.
In this section the threshold argument s is written \(\sigma\), with \(0 \le \sigma \le 1\), so that
it is not confused with the supports \(s_t\).
frequent1
frequent1(a, s) · a basket matrix n×m · s minimum support scalar → mask m
Let \(A \in \{0, 1\}^{n \times m}\) be a basket matrix and \(0 \le \sigma \le 1\). Then
\[\operatorname{frequent1}(A, \sigma)_t = [\, s_t \ge \sigma \,] .\]1 for every item whose support is at least s.
Intuition The first level of Apriori: an item that is rare on its own can never be part of a common pair or triple, so everything built on it can be dropped. The mask is that “worth considering” decision for each item.
Use it when you want to choose the vocabulary for rule mining or cut item columns down before building m×m and m×m×m tables. Raise s until the tables fit and the surviving rules cover enough baskets to act on. Too low a threshold floods you with rules about a handful of baskets.
frequent-itemsetscandidate-pruning
def frequent1(a, s) ≔ support1(a) ≥ s
frequent2
frequent2(a, s) · a basket matrix n×m · s minimum support scalar → mask m×m
Let \(A \in \{0, 1\}^{n \times m}\) be a basket matrix and \(0 \le \sigma \le 1\). Then
\[\operatorname{frequent2}(A, \sigma)_{tu} = [\, S_{tu} \ge \sigma \,] \, [\, s_t \ge \sigma \,] \, [\, s_u \ge \sigma \,] .\]1 for every pair with support at least s whose two items are both frequent.
Intuition A pair is never more common than either of its items, so a frequent pair always has frequent items. The item mask states Apriori’s downward closure explicitly. It never removes a pair the threshold keeps, and it saves no work here, because the full support2 table is still computed.
Use it when you want the set of pairs that occur often enough to matter, for example as the support half of rules or as the input to frequent3. To also require a strong association, multiply the mask by a condition on confidence or lift.
frequent-itemsetscandidate-pruningco-occurrence
def frequent2(a, s) ≔ (support2(a) ≥ s) · allowed2(a, s)
frequent3
frequent3(a, s) · a basket matrix n×m · s minimum support scalar → mask m×m×m
Let \(A \in \{0, 1\}^{n \times m}\) be a basket matrix, \(0 \le \sigma \le 1\), and \(F = \operatorname{frequent2}(A, \sigma)\). Then
\[\operatorname{frequent3}(A, \sigma)_{tuv} = \big[\, \operatorname{support3}(A)_{tuv} \ge \sigma \,\big] \, F_{tu} \, F_{tv} \, F_{uv} .\]1 for every triple with support at least s all of whose pairs are frequent.
Intuition The next level of the same principle: a triple can be frequent only if all three of its pairs are, so the three copies of frequent2 multiplied together mark the candidates, and the triple’s own support decides.
Use it when you are looking for three-item bundles such as meal deals, kits or co-prescribed drugs. It still computes the whole support3 table, so memory grows as \(m^3\). Keep the item list short. Sets of four or more are not supported: that needs a different algorithm such as FP-growth, not a bigger tensor.
frequent-itemsetsproduct-bundlingcandidate-pruning
def frequent3(a, s) ≔ (support3(a) ≥ s) · allowed3(a, s)
rules
rules(a, s, c) · a basket matrix n×m · s minimum support scalar · c minimum confidence scalar → mask m×m
Let \(A \in \{0, 1\}^{n \times m}\) be a basket matrix, \(0 \le \sigma \le 1\) the minimum support and \(0 \le c \le 1\) the minimum confidence, and let \(F = \operatorname{frequent2}(A, \sigma)\) and \(C = \operatorname{confidence}(A)\). Then
\[\operatorname{rules}(A, \sigma, c)_{tu} = F_{tu} \, [\, C_{tu} \ge c \,] \, \big(1 - [\, t = u \,]\big) .\]The rules worth reporting: entry \([t, u]\) is 1 when the pair is frequent at support s and the
confidence of \(t \Rightarrow u\) is at least c. The diagonal is always 0, since “\(t\) implies
\(t\)” says nothing.
Intuition A rule is worth reporting when it is about enough baskets (support) and usually holds (confidence). The two tests are multiplied as masks, and the diagonal is removed because “\(t\) implies \(t\)” is trivially true.
Use it when you want a short list of single-item rules for a report, a shelf layout or cross-sell prompts. It answers a 0/1 mask, so read each kept rule’s strength from confidence, lift or conviction. Confidence alone lets popular consequents through, so multiply by a mask such as lift(a) > 1 to keep only real associations. Rules with two antecedents are not produced.
association-rulesmarket-basket-analysiscross-selling
def rules(a, s, c) ≔ frequent2(a, s) · (confidence(a) ≥ c) · (1 − identity(support2(a)))
Building blocks
allowed2(a, s)— Let \(A \in \{0, 1\}^{n \times m}\), \(0 \le \sigma \le 1\) and \(f = \operatorname{frequent1}(A, \sigma)\). Then \(\operatorname{allowed2}(A, \sigma)_{tu} = f_t f_u\). Mask of pairs whose two items are both frequent.allowed3(a, s)— Let \(A \in \{0, 1\}^{n \times m}\), \(0 \le \sigma \le 1\) and \(F = \operatorname{frequent2}(A, \sigma)\). Then \(\operatorname{allowed3}(A, \sigma)_{tuv} = F_{tu} F_{tv} F_{uv}\). Mask of triples whose three pairs are all frequent.
PageRank
PageRank is the stationary distribution of a random surfer who follows a random outgoing link with probability \(d\) and jumps to a uniformly chosen page otherwise:
\[r_j \leftarrow \frac{1 - d}{n} + d \sum_i r_i \, \frac{g_{ij}}{\mathrm{out}(i)}\]Power iteration from the uniform vector converges because of the damping. A page with no outgoing links passes nothing on (its row of the walk matrix is zero rather than spread evenly), so on a graph with such pages the ranks sum to less than one.
pagerank
pagerank(t, g, d) · t iterations scalar · g link matrix n×n · d damping factor scalar, typically 0.85 → vector n
Let \(t \in \mathbb{N}\), let \(G \in \{0, 1\}^{n \times n}\) (the argument g) be a link matrix and
\(0 < d < 1\) the damping factor, and let \(W = \operatorname{walkFrom}(G)\). Let
\(r^{(0)} = \tfrac{1}{n} \mathbf{1}_n\) and, for \(k = 0, 1, \dots\),
Then \(\operatorname{pagerank}(t, G, d) = r^{(t)}\).
The PageRank of every page after t power-iteration steps from the uniform distribution.
Intuition A page matters when pages that matter link to it. The random surfer makes that circular definition computable: rank is the long-run share of time spent on each page. Damping is the chance of following a link rather than jumping anywhere, and it stops the walk from getting trapped in a closed loop.
Use it when you need to rank nodes of any directed graph: web pages, citations, who-follows-whom, or dependency graphs. Use \(d = 0.85\) unless you have a reason not to. The error shrinks by about a factor \(d\) per step, so 50 steps cut it more than 3,000-fold. Each step works on the dense n×n matrix. With dangling pages the ranks sum to less than 1, so divide by the total if you need a distribution.
graph-rankingranking
def pagerank(t, g, d) ≔ rankLoop(t, g, d, rowOnes(g) / rows(g))
Building blocks
outDegree(g)— Let \(G \in \mathbb{R}^{n \times n}\). Then \(\operatorname{outDegree}(G)_i = o_i = \sum_{j=1}^{n} G_{ij}\). The number of links leaving each page.walkFrom(g)— Let \(G \in \mathbb{R}^{n \times n}\) and \(o = \operatorname{outDegree}(G)\). Then \(\operatorname{walkFrom}(G)_{ij} = \dfrac{G_{ij}}{o_i + [\, o_i = 0 \,]}\). The row-normalised walk matrix (rows of dangling pages stay zero).rankStep(g, d, r)— Let \(G \in \mathbb{R}^{n \times n}\), \(0 < d < 1\), \(r \in \mathbb{R}^n\) and \(W = \operatorname{walkFrom}(G)\). Then \(\operatorname{rankStep}(G, d, r)_j = \frac{1 - d}{n} + d \sum_i r_i W_{ij}\), that is \(\frac{1-d}{n} \mathbf{1}_n + d\, W^{\top} r\). One damped power-iteration step.rankLoop(t, g, d, r)— Let \(t \in \mathbb{N}\), \(G \in \mathbb{R}^{n \times n}\), \(0 < d < 1\) and \(r \in \mathbb{R}^n\). Then \(\operatorname{rankLoop}(0, G, d, r) = r\) and \(\operatorname{rankLoop}(t, G, d, r) = \operatorname{rankLoop}(t - 1, G, d, \operatorname{rankStep}(G, d, r))\). RepeatsrankStepttimes fromr.
Recommendation
Item-item collaborative filtering needs no fitting. Two items are alike when the same users rated them alike, measured by the cosine between their rating columns, and a user’s predicted score for an item is the similarity-weighted average of what that user already rated:
\[\hat r_{uj} = \frac{\sum_i r_{ui} \, s_{ij}}{\sum_i [\, r_{ui} > 0 \,] \, \lvert s_{ij} \rvert}\]In this section let \(R \in [0, \infty)^{U \times I}\) (the argument r) be a rating matrix over
\(U\) users and \(I\) items, with \(R_{ui} = 0\) meaning “not rated”.
itemSimilar
itemSimilar(r) · r ratings users×items → matrix items×items
Let \(R \in [0, \infty)^{U \times I}\) be a rating matrix and \(\nu = \operatorname{itemNorms}(R)\). Then
\[\operatorname{itemSimilar}(R)_{ij} = \frac{\sum_{u=1}^{U} R_{ui} R_{uj}}{\nu_i \, \nu_j}, \qquad \nu_i = \sqrt{\max\Big(\sum_{u=1}^{U} R_{ui}^2,\; 10^{-12}\Big)} .\]The cosine similarity between every pair of item columns. An item nobody rated has its norm guarded away from zero (floored at \(10^{-6}\)).
Intuition Each item is a vector of the ratings users gave it, and two items are alike when those vectors point the same way. The same people rated them, and rated them similarly high. Because the vectors are normalised, a blockbuster and a niche item can still be similar.
Use it when you want a “similar items” or “people who liked this also liked” list, or the similarity table behind recommend. Ratings are not mean-centred, so with non-negative ratings every similarity is at least 0. Two items look alike mainly because they share raters, not because tastes agree. The result is a dense items×items table.
item-similarityrecommendationcollaborative-filtering
def itemSimilar(r) ≔ einsum("ui,uj->ij", r, r) / einsum("i,j->ij", itemNorms(r), itemNorms(r))
recommend
recommend(r) · r ratings users×items, 0 for unrated → matrix users×items
Let \(R \in [0, \infty)^{U \times I}\) be a rating matrix and \(S = \operatorname{itemSimilar}(R)\), and let \(z_{uj} = \sum_{i=1}^{I} [\, R_{ui} > 0 \,] \, \lvert S_{ij} \rvert\). Then
\[\operatorname{recommend}(R)_{uj} = \frac{\sum_{i=1}^{I} R_{ui} S_{ij}}{z_{uj} + [\, z_{uj} = 0 \,]} .\]A predicted score for every user and item, rated or not. Read the cells where r is 0 to rank new
items for a user. A user with no ratings at all gets 0 everywhere rather than NaN.
Intuition To guess how you would rate an item, look at the items you have already rated and average your ratings, weighting each by how similar it is to the target. Nothing is fitted: the prediction is your own history seen through itemSimilar. With non-negative ratings, a prediction stays within the range of the ratings that user gave, or is 0 when none of those items is similar to the target.
Use it when you want a quick, explainable recommender (“because you liked X”) without any training. Rank each user’s unrated cells. It degrades when ratings are sparse and items share few raters, and a user with no ratings gets nothing. In that case filled generalises through latent factors. Memory grows with users×items×items.
recommendationcollaborative-filteringrating-prediction
def recommend(r) ≔ einsum("ui,ij->uj", r, itemSimilar(r)) / safe(einsum("ui,ij->uj", rated(r), abs(itemSimilar(r))))
Building blocks
itemNorms(r)— Let \(R \in \mathbb{R}^{U \times I}\). Then \(\operatorname{itemNorms}(R)_i = \sqrt{\max\big(\sum_{u} R_{ui}^2,\, 10^{-12}\big)}\). The Euclidean norm of each item’s rating column, guarded away from zero.rated(r)— Let \(R \in \mathbb{R}^{U \times I}\). Then \(\operatorname{rated}(R)_{ui} = [\, R_{ui} > 0 \,]\). Mask of the cells that hold a rating.
Matrix factorisation
Approximates a rating matrix by a product of low-rank factors, \(R \approx P Q^\top\), fitting only the cells that were rated. With mask \(M\) and ridge penalty \(\lambda\), gradient descent lowers
\[\tfrac{1}{2} \sum_{u,i} M_{ui} \big( (P Q^\top)_{ui} - R_{ui} \big)^2 + \tfrac{\lambda}{2} \big( \lVert P \rVert^2 + \lVert Q \rVert^2 \big)\]updating both factors together at each step. The mask makes the gradient blind to the blanks instead of treating them as zeros, so the product fills them in.
Parameters shared by this section: t number of steps, e2 learning rate (named e2 because
e is Euler’s number), l ridge penalty \(\lambda\), r ratings users×items, m mask of
rated cells users×items, pf starting user factors users×k, qf starting item factors
items×k. Start the factors from small non-zero values of your own (for example scaled random
draws); starting both at zero never moves. userFactors and itemFactors each run the same descent,
so they answer the two halves of one fit.
In mathematical form: let \(t \in \mathbb{N}\), let \(\eta > 0\) (the argument e2) be the learning
rate and \(\lambda \ge 0\) (the argument l) the ridge penalty, let \(R \in \mathbb{R}^{U \times I}\) be
the ratings, \(M \in \{0, 1\}^{U \times I}\) (the argument m) the mask of rated cells, and
\(P_0 \in \mathbb{R}^{U \times k}\), \(Q_0 \in \mathbb{R}^{I \times k}\) (the arguments pf, qf) the
starting factors. Both factors step from the same pair: for \(s = 0, 1, \dots\),
userFactors
userFactors(t, e2, l, r, m, pf, qf) · parameters as above → matrix users×k
Let \(t\), \(\eta\), \(\lambda\), \(R\), \(M\), \(P_0\), \(Q_0\) and \(P_s, Q_s\) be as above. Then
\[\operatorname{userFactors}(t, \eta, \lambda, R, M, P_0, Q_0) = P_t .\]The user factors \(P\) after t steps.
Intuition Each user becomes a short vector of k hidden tastes, a row of \(P\), fitted so that its dot product with an item’s vector reproduces the ratings that user gave. Users with similar vectors like similar things, even if they rated no items in common.
Use it when you want user embeddings for clustering, finding similar users, or as features for another model. Start pf and qf from small random values you draw, because zero never moves. It runs the whole descent and returns only \(P\), so calling it and itemFactors together runs the descent twice.
matrix-completionembedding-learningrecommendation
def userFactors(t, e2, l, r, m, pf, qf) ≔ userLoop(t, e2, l, r, m, pf, qf)
itemFactors
itemFactors(t, e2, l, r, m, pf, qf) · parameters as above → matrix items×k
Let \(t\), \(\eta\), \(\lambda\), \(R\), \(M\), \(P_0\), \(Q_0\) and \(P_s, Q_s\) be as above. Then
\[\operatorname{itemFactors}(t, \eta, \lambda, R, M, P_0, Q_0) = Q_t .\]The item factors \(Q\) after the same t steps.
Intuition Each item gets coordinates in the same k-dimensional taste space as the users. An item’s vector says how much of each hidden trait it has, and nearby items appeal to the same users.
Use it when you want item embeddings: similar-item search that still works when two items share few raters (where itemSimilar fails), catalogue clustering, or input features for another model. Pass exactly the same arguments as userFactors so the two halves come from the same fit. It runs its own full descent.
matrix-completionembedding-learningitem-similarity
def itemFactors(t, e2, l, r, m, pf, qf) ≔ itemLoop(t, e2, l, r, m, pf, qf)
filled
filled(t, e2, l, r, m, pf, qf) · parameters as above → matrix users×items
Let \(t\), \(\eta\), \(\lambda\), \(R\), \(M\), \(P_0\), \(Q_0\) and \(P_s, Q_s\) be as above. Then
\[\operatorname{filled}(t, \eta, \lambda, R, M, P_0, Q_0) = P_t \, Q_t^{\top} .\]The completed rating matrix \(P Q^\top\) after t steps: close to r on the rated cells, and a
prediction on the rest.
Intuition A ratings table explained by a few hidden tastes has low rank. Fit a rank-k product on the cells you saw, with the mask keeping the blanks out of the loss, and the product fills the blanks with what those tastes imply. The ridge penalty \(\lambda\) keeps the factors from inventing detail to hit every observed cell.
Use it when you need predicted ratings for sparse data, to fill gaps in a survey or sensor table, or for low-rank imputation in general. Keep k small. Raise l if blanks come out extreme. The loss is a sum over rated cells, so larger matrices need a smaller e2. It runs the descent twice, once for each factor, so cost is \(2t\) steps.
matrix-completionrating-predictionmissing-dataoverfitting-control
def filled(t, e2, l, r, m, pf, qf) ≔ guessed(userFactors(t, e2, l, r, m, pf, qf), itemFactors(t, e2, l, r, m, pf, qf))
Building blocks
guessed(pf, qf)— Let \(P \in \mathbb{R}^{U \times k}\) and \(Q \in \mathbb{R}^{I \times k}\) (the argumentspf,qf). Then \(\operatorname{guessed}(P, Q) = P Q^{\top}\), with entries \(\sum_{c=1}^{k} P_{uc} Q_{ic}\). The product of user and item factors, every cell predicted.shortfall(r, m, pf, qf)— Let \(R, M \in \mathbb{R}^{U \times I}\), \(P \in \mathbb{R}^{U \times k}\) and \(Q \in \mathbb{R}^{I \times k}\). Then \(\operatorname{shortfall}(R, M, P, Q) = E = M \odot (P Q^{\top} - R)\). The prediction error on rated cells, zero elsewhere.gradUsers(r, m, pf, qf, l)— Let \(R\), \(M\), \(P\), \(Q\) be as forshortfall, \(\lambda \ge 0\) and \(E = \operatorname{shortfall}(R, M, P, Q)\). Then \(\operatorname{gradUsers}(R, M, P, Q, \lambda) = E Q + \lambda P\). Gradient of the penalised loss with respect to the user factors.gradItems(r, m, pf, qf, l)— Let \(R\), \(M\), \(P\), \(Q\), \(\lambda\) and \(E\) be as forgradUsers. Then \(\operatorname{gradItems}(R, M, P, Q, \lambda) = E^{\top} P + \lambda Q\). Gradient of the penalised loss with respect to the item factors.userLoop(t, e2, l, r, m, pf, qf)— Let \(t \in \mathbb{N}\), \(\eta > 0\), \(\lambda \ge 0\) and \(R\), \(M\), \(P\), \(Q\) be as forshortfall. Then \(\operatorname{userLoop}(0, \eta, \lambda, R, M, P, Q) = P\) and \(\operatorname{userLoop}(t, \eta, \lambda, R, M, P, Q) = \operatorname{userLoop}\big(t - 1, \eta, \lambda, R, M, P - \eta \operatorname{gradUsers}(R, M, P, Q, \lambda), Q - \eta \operatorname{gradItems}(R, M, P, Q, \lambda)\big)\). Runstdescent steps and answers the user factors.itemLoop(t, e2, l, r, m, pf, qf)— Let \(t\), \(\eta\), \(\lambda\), \(R\), \(M\), \(P\), \(Q\) be as foruserLoop. Then \(\operatorname{itemLoop}(0, \eta, \lambda, R, M, P, Q) = Q\) and \(\operatorname{itemLoop}(t, \eta, \lambda, R, M, P, Q) = \operatorname{itemLoop}\big(t - 1, \eta, \lambda, R, M, P - \eta \operatorname{gradUsers}(R, M, P, Q, \lambda), Q - \eta \operatorname{gradItems}(R, M, P, Q, \lambda)\big)\). Runstdescent steps and answers the item factors.
Examples
All examples use one file, Baskets.hb, so the C# class is Baskets. These doorways change the
rank of their input (a matrix in, a vector or a larger tensor out), so pass the inputs as Tensor
to call the general overload.
The basket data for the first three examples: four baskets over bread (item 0), butter (item 1) and jam (item 2).
var a = new double[,] {
{ 1, 1, 0 }, // bread, butter
{ 1, 1, 1 }, // bread, butter, jam
{ 1, 0, 0 }, // bread
{ 0, 1, 1 } }; // butter, jam
Count how often items and pairs are bought
open Prelude.Patterns
fn itemShare(a) ↦ support1(a)
fn pairShare(a) ↦ support2(a)
using MLambda.Hilbert.Runtime;
using Examples;
var single = Baskets.ItemShare((Tensor)a);
var pairs = Baskets.PairShare((Tensor)a);
Output (verified):
support1 = [0.75, 0.75, 0.5]
support2 = [[0.75, 0.5, 0.25], [0.5, 0.75, 0.5], [0.25, 0.5, 0.5]]
Measure the strength of every rule
open Prelude.Patterns
fn ruleConfidence(a) ↦ confidence(a)
fn ruleLift(a) ↦ lift(a)
fn ruleLeverage(a) ↦ leverage(a)
fn ruleConviction(a) ↦ conviction(a)
using MLambda.Hilbert.Runtime;
using Examples;
var conf = Baskets.RuleConfidence((Tensor)a);
var lift = Baskets.RuleLift((Tensor)a);
var lev = Baskets.RuleLeverage((Tensor)a);
var conv = Baskets.RuleConviction((Tensor)a);
Output (verified, rounded to 6 significant digits):
confidence = [[1, 0.666667, 0.333333], [0.666667, 1, 0.666667], [0.5, 1, 1]]
lift = [[1.33333, 0.888889, 0.666667], [0.888889, 1.33333, 1.33333], [0.666667, 1.33333, 2]]
leverage = [[0.1875, -0.0625, -0.125], [-0.0625, 0.1875, 0.125], [-0.125, 0.125, 0.25]]
conviction = [[0.25, 0.75, 0.75], [0.75, 0.25, 1.5], [0.5, 0.25, 0.5]]
Jam implies butter (row 2, column 1) with confidence 1 and lift 4/3. Its true conviction is infinite;
the table shows \(1 - \mathrm{supp}(\text{butter}) = 0.25\), as described under conviction.
Keep only frequent, confident rules
Minimum support 0.5 and minimum confidence 0.6.
open Prelude.Patterns
fn worthReporting(a, s, c) ↦ rules(a, s, c)
using MLambda.Hilbert.Runtime;
using Examples;
var keep = Baskets.WorthReporting((Tensor)a, 0.5, 0.6);
Output (verified):
rules = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]
Four rules survive: bread ⇒ butter, butter ⇒ bread, butter ⇒ jam and jam ⇒ butter. Bread and jam appear together in only a quarter of the baskets, so neither rule between them is frequent.
Rank pages by PageRank
A hub (page 0) that links to pages 1 and 2, both of which link back only to the hub. With damping \(d = 0.85\) the hub’s rank solves \(r_0 = 0.05 + 0.85\,(1 - r_0)\), so \(r_0 = 0.9/1.85\).
open Prelude.Patterns
fn importance(t, g, d) ↦ pagerank(t, g, d)
using MLambda.Hilbert.Runtime;
using Examples;
var g = new double[,] { { 0, 1, 1 }, { 1, 0, 0 }, { 1, 0, 0 } };
var rank = Baskets.Importance(100.0, (Tensor)g, 0.85);
Output (verified, rounded to 6 significant digits):
pagerank = [0.486486, 0.256757, 0.256757]
Predict ratings from similar items
Three users and three items; each user left one item unrated (0).
open Prelude.Patterns
fn similarItems(r) ↦ itemSimilar(r)
fn predictedRatings(r) ↦ recommend(r)
using MLambda.Hilbert.Runtime;
using Examples;
var r = new double[,] { { 5, 4, 0 }, { 4, 0, 4 }, { 0, 5, 4 } };
var sim = Baskets.SimilarItems((Tensor)r);
var pred = Baskets.PredictedRatings((Tensor)r);
Output (verified, rounded to 6 significant digits):
itemSimilar = [[1, 0.487805, 0.441726], [0.487805, 1, 0.552158], [0.441726, 0.552158, 1]]
recommend = [[4.67213, 4.32787, 4.44444], [4, 4, 4], [4.52479, 4.64426, 4.35574]]
The unrated cells are the predictions: user 0 would give item 2 about 4.44, user 1 item 1 exactly 4 (both of that user’s ratings are 4), and user 2 item 0 about 4.52.
Fill in a rating matrix by factorisation
Three users and three items with two unrated cells, rank 2, 2000 steps with learning rate 0.02 and penalty 0.01, from a fixed starting point.
open Prelude.Patterns
fn completed(t, e2, l, r, m, pf, qf) ↦ filled(t, e2, l, r, m, pf, qf)
using MLambda.Hilbert.Runtime;
using Examples;
var r = new double[,] { { 5, 3, 0 }, { 4, 0, 1 }, { 1, 1, 5 } };
var m = new double[,] { { 1, 1, 0 }, { 1, 0, 1 }, { 1, 1, 1 } };
var pf = new double[,] { { 1, 0.5 }, { 0.9, 0.4 }, { 0.3, 1 } };
var qf = new double[,] { { 1, 0.2 }, { 0.8, 0.3 }, { 0.2, 1 } };
var full = Baskets.Completed(2000.0, 0.02, 0.01, (Tensor)r, (Tensor)m, (Tensor)pf, (Tensor)qf);
Output (verified, rounded to 4 significant digits):
filled = [[4.995, 2.993, 2.011], [3.993, 2.340, 0.9997], [1.001, 1.000, 4.990]]
The rated cells are reproduced to within the penalty’s pull; the blanks become predictions of about 2.01 (user 0, item 2) and 2.34 (user 1, item 1).