Rank products by relevance

"""
Rank products with a weighted score: text match, availability, margin, popularity.

Rung N0. Deterministic, standard library only, and above all arguable: the
four weights are arguments, not constants buried in the code. That is the
point of the whole approach. When sales say the top result is wrong, the
conversation is about a number a merchandiser can read, and the answer arrives
in an afternoon rather than in a retraining cycle.

Two decisions make it usable.

Every signal is reduced to the same nought-to-one scale before the weights
touch it, so a weight of two really does mean twice as much, and the score
itself stays inside the same scale whatever the weights.

The sort is stable, so two products the score cannot separate stay in the
order the catalogue gave them. An unstable sort would reshuffle equal results
between two page loads, and nobody would be able to reproduce a complaint.
"""

import unicodedata

# The order the weights are applied in. Fixing it keeps the arithmetic
# identical everywhere, which is what makes a ranking reproducible.
SIGNALS = ("text", "availability", "margin", "popularity")

# A starting point, not a truth. These are the numbers to argue about.
DEFAULT_WEIGHTS = {"text": 6.0, "availability": 2.0, "margin": 1.0, "popularity": 3.0}


def fold(text: str) -> str:
    """Lowercase and drop accents, so that « crème » finds « creme »."""
    decomposed = unicodedata.normalize("NFD", text.lower())
    return "".join(c for c in decomposed if not unicodedata.combining(c))


def terms(text: str) -> list[str]:
    """Split on anything that is not a letter or a digit."""
    letters = "".join(c if c.isalnum() else " " for c in fold(text))
    return letters.split()


def text_match(query: str, product: dict) -> float:
    """
    Share of the query terms found at the start of a word of the product.

    Prefix matching, not equality: a shopper who types « chauss » is looking
    for « chaussures », and a shopper who types the plural is looking for the
    singular too.
    """
    wanted = terms(query)
    if not wanted:
        return 0.0
    haystack = terms(product["title"] + " " + " ".join(product.get("tags", ())))
    found = sum(1 for term in wanted if any(word.startswith(term) for word in haystack))
    return found / len(wanted)


def signals(product: dict, query: str) -> dict[str, float]:
    """The four signals, each on the same nought-to-one scale."""
    return {
        "text": text_match(query, product),
        "availability": 1.0 if product["in_stock"] else 0.0,
        "margin": product["margin"],
        "popularity": product["popularity"],
    }


def score(measured: dict[str, float], weights: dict[str, float]) -> float:
    """Weighted mean of the signals, so the score stays on the same scale."""
    total = 0.0
    weighted = 0.0
    for name in SIGNALS:
        total += weights[name]
        weighted += weights[name] * measured[name]
    return weighted / total if total else 0.0


def rank(products: list[dict], query: str, weights: dict = DEFAULT_WEIGHTS) -> list[dict]:
    """
    Sort the catalogue, best first, and hand back the reason for each place.

    Returning the signals alongside the score costs nothing and settles most
    arguments before they start: whoever asks why a product came third can see
    which signal held it back.
    """
    scored = []
    for product in products:
        measured = signals(product, query)
        scored.append({"product": product, "score": score(measured, weights), "signals": measured})
    # Stable: products the score cannot separate keep their catalogue order.
    scored.sort(key=lambda row: -row["score"])
    return scored

/**
 * Rank products with a weighted score: text match, availability, margin, popularity.
 *
 * Rung N0. Deterministic, no dependency, and above all arguable: the four
 * weights are arguments, not constants buried in the code. That is the point
 * of the whole approach. When sales say the top result is wrong, the
 * conversation is about a number a merchandiser can read, and the answer
 * arrives in an afternoon rather than in a retraining cycle.
 *
 * Two decisions make it usable.
 *
 * Every signal is reduced to the same nought-to-one scale before the weights
 * touch it, so a weight of two really does mean twice as much, and the score
 * itself stays inside the same scale whatever the weights.
 *
 * The sort is stable, so two products the score cannot separate stay in the
 * order the catalogue gave them. An unstable sort would reshuffle equal
 * results between two page loads, and nobody would be able to reproduce a
 * complaint.
 */

// The order the weights are applied in. Fixing it keeps the arithmetic
// identical everywhere, which is what makes a ranking reproducible.
export const SIGNALS = ['text', 'availability', 'margin', 'popularity'];

// A starting point, not a truth. These are the numbers to argue about.
export const DEFAULT_WEIGHTS = { text: 6, availability: 2, margin: 1, popularity: 3 };

/** Lowercase and drop accents, so that "crème" finds "creme". */
export function fold(text) {
  return text.toLowerCase().normalize('NFD').replace(/\p{M}/gu, '');
}

/** Split on anything that is not a letter or a digit. */
export function terms(text) {
  return fold(text).match(/[\p{L}\p{N}]+/gu) ?? [];
}

/**
 * Share of the query terms found at the start of a word of the product.
 *
 * Prefix matching, not equality: a shopper who types "chauss" is looking for
 * "chaussures", and a shopper who types the plural is looking for the
 * singular too.
 */
export function textMatch(query, product) {
  const wanted = terms(query);
  if (wanted.length === 0) return 0;
  const haystack = terms(`${product.title} ${(product.tags ?? []).join(' ')}`);
  const found = wanted.filter((term) => haystack.some((word) => word.startsWith(term)));
  return found.length / wanted.length;
}

/** The four signals, each on the same nought-to-one scale. */
export function signals(product, query) {
  return {
    text: textMatch(query, product),
    availability: product.inStock ? 1 : 0,
    margin: product.margin,
    popularity: product.popularity,
  };
}

/** Weighted mean of the signals, so the score stays on the same scale. */
export function score(measured, weights) {
  let total = 0;
  let weighted = 0;
  for (const name of SIGNALS) {
    total += weights[name];
    weighted += weights[name] * measured[name];
  }
  return total ? weighted / total : 0;
}

/**
 * Sort the catalogue, best first, and hand back the reason for each place.
 *
 * Returning the signals alongside the score costs nothing and settles most
 * arguments before they start: whoever asks why a product came third can see
 * which signal held it back.
 */
export function rank(products, query, weights = DEFAULT_WEIGHTS) {
  const scored = products.map((product) => {
    const measured = signals(product, query);
    return { product, score: score(measured, weights), signals: measured };
  });
  // Array.prototype.sort is stable: products the score cannot separate keep
  // their catalogue order.
  scored.sort((a, b) => b.score - a.score);
  return scored;
}

"""
Learn the ranking weights from past interactions instead of setting them by hand.

Rung N1. The score is the one of N0, a weighted sum of the same four signals.
What changes is where the four numbers come from: a merchandiser's judgement
on N0, the click log here.

The method is pairwise. What a log really says is never « this product
deserves 0.8 », it is « shown these two side by side, a shopper took that
one ». Each such pair becomes one training row, the difference between the two
signal vectors, and a logistic regression on those differences gives back the
weights of the original score. Nothing else changes: the serving code, the
explanation shown to the shop, the scale of the score, all stay as they were.

Every pair is added in both directions, one labelled a win and one a loss.
That keeps the two classes balanced, and it is why the model carries no
intercept: a constant would shift both directions of the same pair the same
way, which is meaningless when comparing two products of one result page.
"""

import numpy as np
from sklearn.linear_model import LogisticRegression

SIGNALS = ("text", "availability", "margin", "popularity")


def pairs(impressions: list[list[dict]]) -> tuple[np.ndarray, np.ndarray]:
    """
    Turn result pages into training rows.

    `impressions` is one entry per result page shown to a shopper, each item
    holding the signals logged at serving time and whether it was clicked.
    Logging the signals rather than recomputing them later matters: a product
    that has since gone out of stock must be trained on the availability it
    had on the day, not on today's.
    """
    rows, labels = [], []
    for page in impressions:
        clicked = [item["signals"] for item in page if item["clicked"]]
        ignored = [item["signals"] for item in page if not item["clicked"]]
        for winner in clicked:
            for loser in ignored:
                difference = [winner[name] - loser[name] for name in SIGNALS]
                rows.append(difference)
                labels.append(1)
                rows.append([-value for value in difference])
                labels.append(0)
    return np.array(rows, dtype=float), np.array(labels)


def learn_weights(impressions: list[list[dict]], regularisation: float = 1.0) -> dict:
    """
    Fit the weights, and hand them back on the scale of the hand-set ones.

    Dividing by the total absolute weight makes the result readable next to
    the numbers of N0, and comparable between two months of log. It changes no
    ranking: scaling every weight scales every score the same way.
    """
    rows, labels = pairs(impressions)
    if len(rows) == 0:
        raise ValueError("no clicked and ignored pair in the log: nothing to learn from")
    model = LogisticRegression(C=regularisation, fit_intercept=False, max_iter=1000)
    model.fit(rows, labels)
    learnt = model.coef_[0]
    scale = float(np.abs(learnt).sum())
    return {name: float(value) / scale for name, value in zip(SIGNALS, learnt)}


def rank(candidates: list[dict], weights: dict) -> list[dict]:
    """
    Score candidates whose signals were computed by the serving pipeline.

    Same weighted sum as N0, same stable sort, same explanation returned: only
    the provenance of the weights differs.
    """
    scored = []
    for candidate in candidates:
        total = 0.0
        for name in SIGNALS:
            total += weights[name] * candidate["signals"][name]
        scored.append({"candidate": candidate, "score": total})
    scored.sort(key=lambda row: -row["score"])
    return scored

/**
 * Learn the ranking weights from past interactions instead of setting them by hand.
 *
 * Rung N1. The score is the one of N0, a weighted sum of the same four
 * signals. What changes is where the four numbers come from: a merchandiser's
 * judgement on N0, the click log here.
 *
 * The method is pairwise. What a log really says is never "this product
 * deserves 0.8", it is "shown these two side by side, a shopper took that
 * one". Each such pair becomes one training row, the difference between the
 * two signal vectors, and a logistic regression on those differences gives
 * back the weights of the original score. Nothing else changes: the serving
 * code, the explanation shown to the shop, the scale of the score, all stay
 * as they were.
 *
 * Every pair is added in both directions, one labelled a win and one a loss.
 * That keeps the two classes balanced, and it is why the model carries no
 * intercept: a constant would shift both directions of the same pair the same
 * way, which is meaningless when comparing two products of one result page.
 *
 * The fit is thirty lines of gradient descent rather than a dependency, which
 * is the argument of this whole rung.
 */

export const SIGNALS = ['text', 'availability', 'margin', 'popularity'];

/**
 * Turn result pages into training rows.
 *
 * `impressions` is one entry per result page shown to a shopper, each item
 * holding the signals logged at serving time and whether it was clicked.
 * Logging the signals rather than recomputing them later matters: a product
 * that has since gone out of stock must be trained on the availability it had
 * on the day, not on today's.
 */
export function pairs(impressions) {
  const rows = [];
  const labels = [];
  for (const page of impressions) {
    const clicked = page.filter((item) => item.clicked).map((item) => item.signals);
    const ignored = page.filter((item) => !item.clicked).map((item) => item.signals);
    for (const winner of clicked) {
      for (const loser of ignored) {
        const difference = SIGNALS.map((name) => winner[name] - loser[name]);
        rows.push(difference);
        labels.push(1);
        rows.push(difference.map((value) => -value));
        labels.push(0);
      }
    }
  }
  return { rows, labels };
}

/**
 * Fit the weights, and hand them back on the scale of the hand-set ones.
 *
 * Dividing by the total absolute weight makes the result readable next to the
 * numbers of N0, and comparable between two months of log. It changes no
 * ranking: scaling every weight scales every score the same way.
 */
export function learnWeights(impressions, { regularisation = 1, epochs = 600, rate = 0.5 } = {}) {
  const { rows, labels } = pairs(impressions);
  if (rows.length === 0) {
    throw new Error('no clicked and ignored pair in the log: nothing to learn from');
  }
  const learnt = new Array(SIGNALS.length).fill(0);
  for (let epoch = 0; epoch < epochs; epoch += 1) {
    const gradient = new Array(SIGNALS.length).fill(0);
    for (let i = 0; i < rows.length; i += 1) {
      const z = rows[i].reduce((sum, value, j) => sum + learnt[j] * value, 0);
      const error = 1 / (1 + Math.exp(-z)) - labels[i];
      rows[i].forEach((value, j) => { gradient[j] += (error * value) / rows.length; });
    }
    // The penalty keeps a signal the log never varied at exactly nought,
    // rather than letting it drift on noise.
    const penalty = regularisation * rows.length;
    learnt.forEach((w, j) => { learnt[j] = w - rate * (gradient[j] + w / penalty); });
  }
  const scale = learnt.reduce((sum, value) => sum + Math.abs(value), 0);
  return Object.fromEntries(SIGNALS.map((name, j) => [name, learnt[j] / scale]));
}

/**
 * Score candidates whose signals were computed by the serving pipeline.
 *
 * Same weighted sum as N0, same stable sort, same explanation returned: only
 * the provenance of the weights differs.
 */
export function rank(candidates, weights) {
  const scored = candidates.map((candidate) => ({
    candidate,
    score: SIGNALS.reduce((sum, name) => sum + weights[name] * candidate.signals[name], 0),
  }));
  scored.sort((a, b) => b.score - a.score);
  return scored;
}