#: How long one answer keeps half its weight as evidence about the learner. #: #: The curve is exponential, `0.5 ** (age / half_life)`. A fixed window was the #: obvious first thing and is wrong in a way that shows: it makes an answer #: twenty-nine days old count in full and one thirty-one days old count for #: nothing, so a topic crosses a cliff overnight and the ranking lurches #: without the learner having done anything. Exponential also has the property #: that matters for an order recomputed on every visit — it is memoryless, so #: an answer's weight depends only on its own age and not on what has been #: answered since, which is what keeps two consecutive sessions consistent with #: each other. A power law fits very long retention slightly better, but it #: needs an arbitrary offset to avoid a singularity at age zero and a second #: parameter nothing here could justify; one named half-life describes the #: whole of this curve. #: #: Thirty days because that is about the turn of a revision cycle. It puts a #: ninety-day-old answer at an eighth of the weight of a fresh one — so what #: was missed last week clearly outranks what was missed in spring — while not #: writing off a topic revised last month as forgotten. EVIDENCE_HALF_LIFE_DAYS = 30.0 #: What the last outcome says about whether a question is still known, at the #: moment it was answered. Not 1 and 0: one answer is one observation, and a #: right answer can be a guess as easily as a wrong one can be a slip. These #: are the numbers the recycling order always used, named here because time #: now moves them. RECALL_AFTER_CORRECT = 0.85 RECALL_AFTER_WRONG = 0.25 #: Recall of a question there is no useful evidence about either way — and the #: accuracy assumed for a topic never answered in, so it sorts between the #: learner's strong and weak areas rather than jumping the queue. NEUTRAL_RECALL = 0.5 #: Recall below which a question is due to come round again. A correct answer #: decays past this at about three and a half weeks, which is the review #: interval this is meant to express; anything ever answered wrongly is below #: it from the moment it was answered. DUE_RECALL = 0.7 #: The most of one session that may be spent on questions already seen. Review #: is not what you do once the new material runs out — that rule meant a #: learner with three thousand unseen questions never saw a repeat, which is #: no spaced repetition at all. But somebody who opens the app and is handed #: twenty questions they have already answered does not open it again, so the #: majority of any session is still new. MAX_REVIEW_SHARE = 0.4 #: Answers' worth of "no idea" mixed into every topic's accuracy. Without it a #: single correct answer made a topic 100% known and it never came back, which #: is the one thing a ranking that claims to decay must not do. PRIOR_ANSWERS = 2.0 #: How fast a topic's priority falls as the session keeps drawing from it. CATEGORY_DAMPING = 0.5 def recency_weight(age_days: float) -> float: """How much evidence that old still counts for.""" return 0.5 ** (max(0.0, age_days) / EVIDENCE_HALF_LIFE_DAYS) def recall_probability(was_correct: bool, age_days: float) -> float: """Chance a question is still known, given how it last went and how long ago. Decays towards a coin flip rather than towards zero. Forgetting a right answer does not turn it into a wrong one, and time does not turn a wrong answer into a right one either; both outcomes end up saying nothing, which is exactly the state in which the question is worth asking again. """ settled = RECALL_AFTER_CORRECT if was_correct else RECALL_AFTER_WRONG return NEUTRAL_RECALL + (settled - NEUTRAL_RECALL) * recency_weight(age_days) class CandidateRanking: """One learner, one filtered bank, and everything needed to order it. Built once and read many times. Selection and the plan that describes it are two readings of this one object rather than two calculations that would have to be kept in step — a plan that does not describe the session it starts is worse than no plan. The rules, in the order they apply: **Unseen material is most of the session.** A question never met teaches more than one already answered, so it takes every slot review is not holding. **Review takes the rest, up to `MAX_REVIEW_SHARE`, and only what is due.** Due means recall has decayed below `DUE_RECALL` — everything answered wrongly, and everything answered correctly long enough ago to be worth checking. **Within either, highest value first, damped per topic.** Value for unseen material is the topic's impact, `(1 − accuracy) × blueprint weight`; for review it is `(1 − recall) × blueprint weight`. Each pick halves its topic's priority, which stops a session of twenty becoming twenty questions from one subject — and gives a learner with no history at all a spread across the paper instead of the heaviest domain entire. Accuracy and recall both fade with time; see `EVIDENCE_HALF_LIFE_DAYS`. """ def __init__(self, db, user, category_ids=(), state="all", difficulty=None, now=None): self.now = now or datetime.utcnow() query = filtered_bank_query(db, user, category_ids, state, difficulty) # No cap. This used to take the first 2,000 rows, which on a # 2,948-question bank meant adaptive selection could not see about a # third of it, and which third depended on database order. Two integer # columns per question is not a size worth protecting against. # # Sorted by id so that every scan below, and so every tie, resolves the # same way twice running: the plan and the session it commits are # separate calls, and a ranking that reshuffles between them would make # the plan a guess. self.rows = sorted(((row[0], row[1]) for row in query.with_entities( Question.id, Question.question_category_id).all()), key=lambda row: row[0]) self.category_of = dict(self.rows) answered = db.query(AttemptAnswer.question_id, AttemptAnswer.is_correct, QuizAttempt.completed_at).join( QuizAttempt, QuizAttempt.id == AttemptAnswer.attempt_id).join(Quiz, Quiz.id == QuizAttempt.quiz_id).filter( QuizAttempt.user_id == user.id, QuizAttempt.completed_at.isnot(None), or_(QuizAttempt.expired == 0, QuizAttempt.expired.is_(None)), Quiz.course_id.is_(None), AttemptAnswer.question_id.in_([row[0] for row in self.rows]), ).order_by(QuizAttempt.completed_at.desc(), QuizAttempt.id.desc()).all() #: question id → (was correct, when, age in days) of the latest answer. self.latest: dict[int, tuple[bool, object, float]] = {} evidence: dict = defaultdict(lambda: [0.0, 0.0]) for question_id, was_correct, when in answered: age = max(0.0, (self.now - when).total_seconds() / 86400.0) self.latest.setdefault(question_id, (bool(was_correct), when, age)) # Looked up, not scanned. This was a linear search through every # candidate for every answer — the slowest part of building a # session. category = self.category_of.get(question_id) if category is None: continue counts = evidence[category] counts[0] += recency_weight(age) if was_correct: counts[1] += recency_weight(age) self._evidence = evidence self.recall = {question_id: recall_probability(was_correct, age) for question_id, (was_correct, _, age) in self.latest.items()} self.weights = blueprint_weights(db, user) # The middle of what the board publishes, for a topic it does not # mention. A zero would make unmapped material unreachable; the highest # would make it the priority. Neither is a claim the blueprint supports. self._neutral_weight = statistics.median(self.weights.values()) if self.weights else 1.0 self.unseen = [row for row in self.rows if row[0] not in self.latest] self.seen = [row for row in self.rows if row[0] in self.latest] self.due = [row for row in self.seen if self.recall[row[0]] < DUE_RECALL] def evidence_weight(self, category) -> float: """Answers' worth of evidence about a topic, after decay.""" return self._evidence.get(category, (0.0, 0.0))[0] def accuracy(self, category) -> float: """Share of this topic answered correctly, recent answers counting most. Pulled towards `NEUTRAL_RECALL` by `PRIOR_ANSWERS`, so one lucky answer does not settle a topic and a topic left alone drifts back to unknown. """ total, correct = self._evidence.get(category, (0.0, 0.0)) return (correct + PRIOR_ANSWERS * NEUTRAL_RECALL) / (total + PRIOR_ANSWERS) def weight(self, category) -> float: """The topic's share of the real paper, or a neutral stand-in.""" return self.weights.get(category, self._neutral_weight) if self.weights else 1.0 def impact(self, category) -> float: """How much a question here could move the score.""" return (1 - self.accuracy(category)) * self.weight(category) def _unseen_value(self, row) -> float: return self.impact(row[1]) def _review_value(self, row) -> float: return (1 - self.recall[row[0]]) * self.weight(row[1]) def value(self, row) -> float: """What one candidate is worth, whichever pool it came from.""" return self._review_value(row) if row[0] in self.recall else self._unseen_value(row) def review_budget(self, count: int) -> int: """Slots this session gives to questions already seen.""" return min(len(self.due), round(MAX_REVIEW_SHARE * count)) if count > 0 else 0 def select(self, count: int) -> list[int]: """The questions, in the order they will be asked.""" if count <= 0: return [] damping: dict = defaultdict(lambda: 1.0) taken: list[int] = [] spent: set[int] = set() def draw(pool, budget): candidates = [row for row in pool if row[0] not in spent] picked = 0 while candidates and picked < budget: best, best_score = None, None for row in candidates: score = self.value(row) * damping[row[1]] if best_score is None or score > best_score: best, best_score = row, score candidates.remove(best) taken.append(best[0]) spent.add(best[0]) picked += 1 damping[best[1]] *= CATEGORY_DAMPING review = self.review_budget(count) draw(self.unseen, count - review) draw(self.due, review) # Whatever the two budgets could not fill. A bank with nothing unseen # left, or nothing due, still owes the learner the length they asked # for. draw(self.rows, count - len(taken)) return taken def adaptive_select(db, user, count, category_ids, state, difficulty, now=None): """Adaptive selection: the questions most likely to raise the learner's score. The rules live on `CandidateRanking`, which the prepared session reads to explain itself. This is the same selection reached from the Adaptive toggle on the manual builder. """ return CandidateRanking(db, user, category_ids, state, difficulty, now).select(count)