PaperlayerView exact revision on arXiv

Source-linked AI summary

AIBL: Augmented Instance-Based Learning with Structured Memory and Neural Embeddings

Radha Poovendran, Andrea Stocco, Linda Bushnell

arXiv:2610.03413v1cs.LG

TL;DR

Sequential learners face high-dimensional inputs and changing distributions, while symbolic IBLT depends on manually specified situation matching. AIBL moves case-based retrieval into learned embedding space and adds memory tiers for weak matches; across tested dataset streams, vector retrieval improves over symbolic IBLT, with reported accuracy gains of 6 to 17 percentage points where symbolic baselines are available.

  • Problem

    Symbolic IBLT relies on hand-specified situation attributes and matching, limiting its fit for high-dimensional inputs whose relevant similarity is learned from data.

    Source: §1 · pp. 2–3

  • Method

    AIBL retains instance storage, activation-weighted retrieval, and utility blending while using learned embeddings and active, forgotten, and surprise memory with recurrence-based promotion.

    Source: §1 · p. 3

  • Results

    Across tested dataset streams, vector-indexed retrieval improves over symbolic IBLT; on machine-learning tasks with reported symbolic baselines, accuracy improves by 6 to 17 percentage points.

    Source: §1 · p. 3, §7 · p. 30

  • Takeaways & Limitations

    The controlled simulations indicate that surprise memory separates weakly supported cases from ordinary retrieval, while graduation lets recurring new cases influence later decisions; tiered memory alone does not infer hidden task rules.

    Source: §6 · p. 29, §7 · p. 30

    Exact retrieval scales linearly with memory size, and AIBL inherits errors when the encoder misplaces cases that should be compared.

    Source: §6.1 · p. 30

Abstract

from arXiv · show

Sequential learning systems often make decisions from accumulated experience while receiving high-dimensional inputs whose distribution may change over time. Instance-Based Learning Theory (IBLT) provides a principled case-based framework for such settings through stored situation-decision-utility instances, partial matching, activation, and blending. IBLT relies on symbolic knowledge representation in dictionary-like formats, but text, images, transaction vectors, and user-item histories often require learned similarity rather than hand-specified matching rules. In this paper, we introduce AIBL (Augmented Instance-Based Learning), an instance-learning model formulated in a learned vector space for high- dimensional sequential data. AIBL generalizes symbolic situation matching to neural embedding similarity while retaining instance storage, activation- weighted retrieval, and utility blending. The AIBL model organizes memory into active, forgotten, and surprise stores. Surprise memory separates weakly matched, possible out-of-distribution, or corner-case observations from active memory, reducing forced fitting to the nearest available cases. An observation-driven graduation algorithm promotes recurring surprise instances to active memory, allowing the memory to incorporate repeated novel patterns that may arise under concept drift. We evaluate the same implementation on five machine learning tasks and three controlled simulation tasks, comparing AIBL with classical IBLT variants and task-specific baselines where appropriate. AIBL improves accuracy by 6 to 17 percentage points. The results show where vector-space retrieval improves over symbolic matching and how the added memory mechanisms govern novelty detection, cold-start handling, drift adaptation, and reward learning under the tested protocols.

1 Introduction

AIBL extends case-based sequential learning to high-dimensional observations by using embedding similarity while preserving instance storage, retrieval, and utility blending. It separates weakly matched observations into surprise memory for recurrence-based promotion; on machine-learning tasks with symbolic baselines, it improves accuracy by 6 to 17 percentage points.

1 Introduction

  • Case-based learning ties predictions to stored experience, but ordinary retrieval can treat poor nearest matches as sufficient evidence.This makes weak-match handling important when distributions change or corner cases appear.Source: §1 · pp. 2–3
  • AIBL represents situations in learned vector spaces, replacing manually specified matching rules with similarity learned for high-dimensional inputs.The model retains IBLT's instance structure and uses embedding similarity for retrieval.Source: §1 · pp. 2–3
  • Surprise memory keeps weakly matched, possible out-of-distribution, or corner-case observations apart from active retrieval, reducing forced fitting to the nearest cases.Repeated similar observations can provide sufficient evidence for promotion into active memory.Source: §1 · p. 3
  • 6 to 17 percentage points: AIBL improves accuracy over symbolic IBLT on machine-learning tasks where a symbolic baseline is reported.The evaluation spans five machine-learning tasks and three controlled novelty simulations, with task-specific baselines where appropriate.Source: §1 · p. 3

2 Related Work

Related work situates AIBL between symbolic instance-based learning and embedding-indexed memory: it retains case-based decisions while using learned similarity and an explicit policy for managing weakly supported cases. Its novelty signal is retrieval support, which also governs whether an observation is withheld from blending or later promoted.

2 Related Work

  • Symbolic IBLT uses structured, modeler-specified attributes and partial matching, while AIBL represents encoded observations in embedding space for learned similarity.The distinction matters for documents, images, transaction vectors, and user-item histories, where relevant similarity is task-dependent.Source: §2 · pp. 3–4

2.1 Instance-Based Learning and Symbolic Retrieval

  • IBLT stores situation-decision-utility instances, retrieves similar cases using activation, blends their utilities, and updates memory after feedback.Activation reflects frequency and recency, while partial matching lets similar but nonidentical situations contribute [Anderson 2007].Source: §2.1 · p. 4

2.2 Relationship to Memory Models in Cognition and Machine Learning

  • AIBL combines embedding-based retrieval with explicit case management, including withholding weak matches, recurrence-based promotion, forgetting, and reactivation.Unlike embedding-indexed methods focused on retrieval or replacement rules, AIBL specifies how cases move through memory tiers.Source: §2.1 · p. 4, §2.2 · pp. 5–6

2.3 Novelty and Anomaly Detection

  • AIBL defines novelty by low similarity to stored experience and uses that same retrieval signal to route observations to surprise memory or ordinary blending.Recurring similar observations can later be promoted to active memory.Source: §2.3 · p. 6

3 AIBL Model Specification

AIBL represents each experience as an embedding-indexed instance and computes decisions from similarity, activation, and observed outcomes. Its three memory tiers and threshold-governed transitions determine which cases participate in retrieval, remain dormant, or await recurrence.

3 AIBL Model Specification

  • AIBL instances are embedding-indexed experiences, and decisions use similarity, activation, and observed outcomes.The model specification defines the instance, memory system, similarity rule, retrieval weight, and tier transitions.Source: §3 · p. 6

3.1 Formal Definitions

  • The instance tuple records the encoded observation, action or label, outcome, memory tier, access times, outcome statistics, and promotion counter.Cosine similarity compares embeddings; eligible instances contribute to blended value through weights based on activation and similarity.Source: §3.1 · pp. 7–8, Table 1 · p. 7

3.2 AIBL Memory Tiers

  • Active instances participate in ordinary retrieval, forgotten instances can reactivate when relevant, and surprise instances with low similarity are withheld from immediate blending.A surprise instance is promoted to active memory after enough later matches meet the recurrence threshold.Source: §3.2 · pp. 8–9

3.3 AIBL Configuration Parameters

  • Configuration thresholds govern retrieval eligibility, novelty routing, duplicate handling, and forgetting, while count parameters govern cold start and surprise-memory graduation.The embedding dimension comes from the encoder, and the default settings apply unless an experiment reports task-specific values.Source: §3.3 · pp. 9–10, Table 2 · p. 9

3.4 AIBL Memory Flow

  • Memory flow admits the first Nc observations directly to active memory, then handles same-action duplicates before routing unsupported cases to surprise memory.Nearby instances with substantially different outcomes can remain separate; later matching observations increment surprise counters until promotion, while forgotten cases can reactivate.Source: §3.4 · p. 10

4 AIBL Algorithms

AIBL’s algorithms process observations through intake, promotion, retrieval and blending, then memory maintenance. They combine embedding similarity with activation and outcome history to govern which cases are stored, retrieved, or kept distinct.

4.1 Embedding Intake and Instance Storage

  • Intake first fills active memory during cold start, then checks same-action duplicates against outcome history before routing weakly supported observations to surprise memory.A nearby embedding is kept separate when its outcome deviates sufficiently; low-support routing has an exception when a supervised task’s action is already active.Source: §4.1 · pp. 11–12

4.2 Surprise Memory Promotion

  • Surprise instances graduate to active memory only after later embeddings match them at least θn until their recurrence counter reaches Ng.Cumulative counts allow promotion even when matching observations are not consecutive.Source: §4.2 · pp. 12–13

4.3 Retrieval, Blending, and Memory Maintenance

  • Retrieval searches active and forgotten instances, reactivates qualifying forgotten cases, and blends up to k retrieved outcomes by activation and similarity before maintenance applies forgetting and capacity limits.Surprise memory is excluded from ordinary prediction until promotion.Source: §4.3 · pp. 13–15

4.4 Outcome Statistics for Nearby Duplicate Handling

  • For nearby same-action embeddings, AIBL uses outcome deviation—not similarity alone—to decide whether to update a stored instance or preserve a separate case.When outcome history is too limited to estimate variance, the deviation test returns false; per-instance running statistics avoid retaining the full outcome sequence.Source: §4.4 · pp. 15–17

4.5 Computational and Storage Cost

  • Brute-force retrieval costs O((nA + nF)d) per query, while surprise promotion costs O(nSd) per incoming embedding; capped access histories give O(d) storage per instance.Approximate nearest-neighbor indices can reduce retrieval time without changing tier transitions.Source: §4.5 · pp. 17–18

4.6 Equation and Algorithm Correspondence

  • Table 4 maps AIBL’s mathematical quantities to the algorithms that use them, linking embedding comparison and activation weighting to tier changes and outcome-statistic updates.The mapping makes the implementation path explicit.Source: Table 4 · p. 18, §4.6 · p. 18

5 Experiments

The experiments test AIBL as a streaming learner across task-specific datasets and controlled simulations, with encoders held fixed during evaluation. On 20 Newsgroups, embedding-indexed AIBL outperformed symbolic IBLT, while a held-out-category test assessed novelty routing.

5 Experiments

  • The experiments combine real-task datasets spanning lexical, categorical, transactional, temporal, or user-item similarity with controlled simulations of new options and rule changes.The simulations isolate surprise memory, graduation, decay, and cold-start storage.Source: §5 · p. 19

5.1 Experimental Setup

  • Encoders were trained before streaming and held fixed, so reported differences reflect storage, retrieval, thresholding, and promotion rather than online encoder-weight changes.Baselines were task-matched; published reference ranges were distinguished from directly evaluated results when protocols differed.Source: §5.1 · pp. 19–20, §5 · p. 19

5.2 Text Classification on 20 Newsgroups

  • 60.3% accuracy and 0.573 macro F1 for AIBL, versus 53.5% accuracy and 0.513 macro F1 for symbolic IBLT; Sentence-BERT k-NN reached 61.7% accuracy.AIBL’s novelty routing and activation-weighted updates did not improve top-line classification accuracy over k-NN in this experiment.Source: Table 5 · p. 20, §5.2 · p. 20
  • 88.5% of 200 held-out documents were correctly flagged as novel after AIBL stored documents from the other 16 categories, using max sim < θn with θn = 0.5.Four categories were held out from the 20 Newsgroups stream.Source: §5.2 · pp. 20–21

5.3 Reward Learning on the UCI Mushroom Dataset

In a chosen-action-feedback Mushroom reward-learning task, AIBL used autoencoder embeddings to select actions. Its optimal-action rate exceeded symbolic IBLT’s, but specialized linear bandit baselines were at least as strong.

5.3 Reward Learning on the UCI Mushroom Dataset

  • Each trial revealed only the reward for the selected “eat” or “avoid” action, making the evaluation a contextual bandit task rather than supervised classification with full labels.Eating a poisonous mushroom incurred −1.0 reward; the optimal action received 1.0.Source: §5.3 · p. 21
  • AIBL indexed the categorical mushroom contexts with 64-dimensional, L2-normalized embeddings from an autoencoder trained without labels.The encoder was trained on the complete one-hot feature vectors.Source: §5.3 · p. 21
  • The tested Mushroom task had only two actions and deterministic labels; larger action spaces and delayed reward remain open evaluation settings.Source: §5.3 · p. 21
  • 96.6% optimal action rate for AIBL versus 87.9% for symbolic IBLT (+8.7 percentage points); LinUCB reached 97.8%, while linear Thompson sampling matched AIBL’s rate.Linear Thompson sampling obtained a slightly higher mean reward.Source: §5.3 · p. 21, Table 6 · p. 22

5.4 Anomaly Detection on Credit Card Fraud Data

This experiment evaluates AIBL as a semi-supervised anomaly detector on credit-card transactions, using similarity to stored normal cases as a support signal. AIBL achieves higher F1 than the symbolic IBLT baseline in the held-out evaluation, but the result is limited to this setup rather than general fraud detection.

5.4 Anomaly Detection on Credit Card Fraud Data

  • The dataset contains 284,807 transactions, including 492 frauds, and the IBLT baseline represented continuous inputs by quantile-binning 29 attributes.The IBLT baseline used the same normal-memory size as AIBL.Source: §5.4 · p. 22
  • Training used normal transactions only; fraud labels were reserved for selecting the detection threshold on validation data and computing final metrics.AIBL flagged transactions when maximum cosine similarity to normal memory fell below the novelty threshold, selected as 0.87 on validation.Source: §5.4 · p. 22
  • 34.3 percentage points higher F1 than IBLT; AIBL detected 78 of 100 frauds and flagged 2 of 4,900 normal transactions, with 0.975 precision and a 0.04% false positive rate.One Class SVM matched AIBL’s recall but produced 29 false positives and a lower F1 score.Source: Table 7 · p. 23, §5.4 · p. 23
  • The findings support a claim about AIBL’s anomaly scoring, not general fraud detection; temporal sequences, merchant graphs, and supervised fraud classifiers were not evaluated.AIBL retains the nearest normal cases for each flagged transaction as a case-based audit trail.Source: §5.4 · p. 23

5.5 Concept Drift Adaptation on Electricity Market Data

The paper tests AIBL on an ordered electricity-market stream and a sequential MovieLens recommendation stream. It reports stronger results than symbolic IBLT on both, while the MovieLens split does not test cold-start detection.

5.5 Concept Drift Adaptation on Electricity Market Data; 5.6 Sequential Recommendation on MovieLens

  • Electricity predictions were evaluated online on the held-out stream, while MovieLens ratings were timestamp-ordered and evaluated on the final 20,000 ratings.AIBL used standardized state vectors for electricity and learned user–movie vectors as retrieval keys for MovieLens.Source: §5.5 · pp. 23–24, §5.6 · pp. 24–25

5.5 Concept Drift Adaptation on Electricity Market Data

  • AIBL achieved the highest overall accuracy, macro F1, and final-quarter accuracy on the Electricity Market stream; versus IBLT with quantile bins, accuracy improved by 7.1 percentage points and macro F1 by 8.2 points.The comparison used the same ordered observations and memory size; AIBL also outperformed a sliding-window kNN baseline.Source: Table 8 · p. 24, §5.5 · p. 24

5.6 Sequential Recommendation on MovieLens

  • AIBL obtained the highest F1 score and nearly matched the highest accuracy on MovieLens; versus symbolic IBLT, accuracy improved by 5.2 percentage points and F1 by 2.6 points.Versus direct matrix factorization, accuracy improved by 4.2 points and F1 by 2.4 points.Source: Table 9 · p. 25, §5.6 · p. 25
  • The MovieLens support threshold provided no useful cold-start signal in this split: an 80,000-rating temporal warmup left most evaluation pairs with substantial historical support.The result is evidence for sequential recommendation indexed by vectors, not cold-start detection on MovieLens.Source: §5.6 · p. 25

5.7 Controlled Novelty Simulations

The controlled simulations test how AIBL’s memory mechanisms handle recurring novel options, changing outcomes, and latent rule changes. Graduation supports later use of recurring low-support options, but its initial withholding can cost performance, and tiered memory alone does not solve hidden-rule inference.

Novelty Phases; Dynamic Bandits

  • Novelty Phases introduced option C, shifted option A’s outcome distribution, then restored it; Dynamic Bandits added and removed arms with higher-reward new options.The simulations test algorithm performance in simulated sequential decisions, not fits to human data; experiments used 100 agents and five random seeds.Source: §5.7 · pp. 25–26

Novelty Phases

  • 75.3% accuracy in the Novelty phase for full AIBL versus 7.2% without graduation, showing graduation’s importance when surprise memory withholds new options from ordinary retrieval.Removing surprise memory makes the model behave like standard IBLT in this task, but removes the separate low-support memory state.Source: Table 10 · p. 26, §5.7 · p. 26

Dynamic Bandits

  • When arm D appeared in Dynamic Bandits, removing graduation reduced accuracy from 48.5% to 22.7%; full AIBL initially lagged standard IBLT while withholding low-support observations.Removing cold-start storage had smaller, localized effects: initial-phase bandit accuracy fell from 46.7% to 44.4%, and Novelty Phases standard-phase accuracy from 63.0% to 60.9%.Source: §5.7 · p. 26, Table 11 · p. 27

Wisconsin Card Sorting Task

  • On the Wisconsin Card Sorting Task, all variants remained close to chance because AIBL stores action outcomes but does not infer the task’s hidden sorting rule.The task has four response options, so chance accuracy is 0.25.Source: §5.7 · p. 27, Table 12 · p. 27

5.8 Parameter and Mechanism Sensitivity

AIBL outperforms symbolic IBLT on the primary metric in each dataset comparison, while sensitivity analyses show that useful parameter settings vary by task. Controlled simulations also show that graduation matters when recurring novel cases must influence later choices.

5.8 Parameter and Mechanism Sensitivity

  • The sensitivity analysis summarizes validation sweeps used to choose task configurations and mechanism ablations in controlled simulations, rather than adding a separate benchmark.The analyses identify parameters that control task-specific behavior.Source: §5.8 · p. 27
  • Table 13 summarizes task-specific parameter sensitivity from validation sweeps and controlled simulations; regions are near-best settings, except text uses one reproduced setting.Regions are within 0.5 percentage points of the best validation score, except fraud, which uses validation F1 within 0.02; text evaluates one fixed parameter choice.Source: Table 13 · p. 28, §5.8 · p. 28
  • No single threshold regime is uniformly best: Mushroom favors a high retrieval threshold, Electricity a small neighborhood with moderate decay, and MovieLens larger neighborhoods.For fraud detection, the novelty threshold is the controlling parameter because the prediction concerns weak transaction support.Source: §5.8 · p. 28
  • Without graduation, Novelty Phases accuracy falls from 75.3% to 7.2%, and Dynamic Bandits accuracy from 48.5% to 22.7%; WCST remains near chance.In WCST, the model stores action outcomes but does not infer the hidden sorting rule.Source: §5.8 · p. 28
  • AIBL exceeds symbolic IBLT by 6.8 points in text accuracy, 8.7 in Mushroom optimal action rate, 34.3 in fraud F1, 7.1 in Electricity accuracy, and 2.6 in MovieLens F1.These comparisons use the same task streams as the corresponding IBLT baselines.Source: §5.8 · p. 28
  • AIBL does not lead every task-specific comparison: Sentence-BERT k-NN is slightly more accurate on 20 Newsgroups, LinUCB is best on Mushroom, and item kNN has the highest MovieLens accuracy.The narrower contribution is an instance-memory rule that uses learned vector representations while retaining case storage, activation weighting, novelty routing, and online updates.Source: §5.8 · p. 29

6 Discussion

AIBL replaces hand-specified symbolic matching with vector-based retrieval while retaining case storage and activation. Its discussion links weak-support routing and memory updates to tested behaviors, and bounds the approach by its retrieval, learning, and evaluation limits.

6 Discussion

  • AIBL represents situations with encoder-produced vectors, so similarity depends on the encoder, metric, and retrieval threshold rather than hand-specified partial matching.It retains case storage, similarity- and activation-based retrieval, and updates from observed outcomes.Source: §6 · p. 29
  • Observations below the novelty threshold enter surprise memory, and graduation lets recurring low-support cases become active; decay instead reduces older cases' influence when recent outcomes are more reliable.These mechanisms explain why recurring new options remain unable to guide choices without graduation in the controlled simulations.Source: §6 · p. 29
  • AIBL does not infer hidden task rules, and task-specific methods can lead on some datasets; the supported claim is improvement over symbolic IBLT on tested streams.The WCST result remains near chance because the implementation stores action outcomes without learning an explicit latent sorting rule.Source: §6 · p. 29
  • Retrieved cases, similarities, activations, and outcomes support tracing decisions and audit logs, but do not by themselves establish causal explanations.The discussion gives inspection of a flagged transaction's nearest stored normal transactions and maximum similarity as an example.Source: §6 · p. 29

6.1 Limitations

  • Exact retrieval costs O(n) per query; above 105 instances the paper says approximate-nearest-neighbor indices would be needed, and retrieval inherits encoder errors.The limitation applies when the encoder places dissimilar cases together or separates cases that should be compared.Source: §6.1 · p. 30
  • The implementation learns values for individual actions, not action sequences or temporal credit assignment; tuning needs validation data, and sensitivity analysis is not a full factorial ablation.The analysis summarizes reproduced-experiment validation sweeps and controlled-simulation mechanism ablations.Source: §6.1 · p. 30

7 Conclusion and Open Problems

AIBL applies IBLT's case-based operations to learned vector representations and adds memory rules for weakly supported observations. Experiments support gains over symbolic IBLT on tested streams, while identifying limits and open problems for the approach.

7 Conclusion and Open Problems

  • AIBL moves IBLT's situation representation into a learned vector space while retaining instances containing a situation, decision, and utility, retrieved by similarity and activation and updated after feedback.The representation supports operation on text, tabular records, transaction vectors, and user-item representations.Source: §7 · p. 30
  • AIBL routes weakly supported observations to surprise memory, keeps inactive cases in forgotten memory, and promotes recurring surprise cases into active memory when a recurrence threshold is met.Novelty handling becomes part of the storage and retrieval process used for prediction.Source: §7 · p. 30
  • On tested dataset streams, vector-indexed retrieval improves over symbolic IBLT; simulations show graduation is needed for recurring new cases to influence decisions, while tiered memory does not infer hidden task rules.WCST identifies this boundary of the approach.Source: §7 · p. 30
  • Open problems include sublinear retrieval preserving activation and blending semantics, less validation-dependent threshold selection, regret analysis for bandits, and direct evaluation of novelty, drift, and cold-start signals.The proposed direct evaluations include detection metrics and abstention or exploration policies.Source: §7 · p. 30

Code and Data Availability

The paper states that its implementation, experimental code, and ablation scripts will be released upon publication, and names the public datasets used in its experiments.

Code and Data Availability

  • The experiments use public datasets including 20 Newsgroups, UCI Mushroom, Credit Card Fraud, Electricity Market, and MovieLens 100K; code, implementation, and ablation scripts are slated for release upon publication.Source: Code and Data Availability · p. 31
Loading 2610.03413v1…