Rule Extraction in Machine Learning: Chat Incremental Pattern Constructor

arXiv:2208.00335 · cs.LG · Submitted 2026-08-11 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Rule Extraction in Machine Learning: Chat Incremental Pattern Constructor".

Jane: The paper was written by Caleb Princewill Nwokocha from.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Title and Authors: Tom: Welcome back to the show, everyone. Today we're looking at a paper that's been making the rounds on arXiv, and it's called "Rule Extraction in Machine Learning: Chat Incremental Pattern Constructor." Jane, I gotta say, the title alone had me curious.

Jane: It's a mouthful, but the idea behind it is actually pretty straightforward. This paper is about a system called ChatIPC, and it's trying to solve a really old problem in AI: how do you make a machine that learns, but does it in a way that humans can actually understand?

Tom: Right, and that's the "rule extraction" part. Usually, when we train a neural network, it figures out patterns on its own, but it's basically a black box. We get an answer, but we don't know why. This paper wants to pull the curtain back.

Jane: Exactly. Instead of a neural network, ChatIPC builds something like a giant map of words. When it reads a sentence, it draws a line from one word to the next. "The" points to "cat," "cat" points to "sat." That's the rule. It's a transition.

Tom: And the author here is Caleb Princewill Nwokocha. He's framing this as a rule extractor, but it's not extracting rules from a trained network like the old papers did. It's building the rules directly from the text it sees.

Jane: That's the key difference. Older methods, like the ones from the 90s, would train a neural network first and then try to explain it afterward. This system never goes through that opaque stage. The symbolic rules are the model. There's no hidden layer.

Tom: So if I ask it a question, it's not doing some massive probability calculation in the dark. It's literally looking at its map of word connections and picking the next word based on which path makes the most sense.

Jane: And that makes it auditable. If it gives a weird answer, you can look at the map and see exactly which connection it chose and why. You can't do that with a deep learning model.

Tom: I love that. It's like the difference between a chef who follows a written recipe and a chef who just throws ingredients in a pot and hopes for the best. One you can critique, the other you just have to taste.

Jane: That's the appeal. The paper is essentially arguing that we don't always need massive, complex models. For some tasks, a clear, inspectable map of rules is not only enough, it's better because we can trust it.

Tom: And that's a big deal for things like healthcare or finance, where you need to explain why a decision was made. We'll get into how it actually builds that map and scores its answers next.

Jane: Stay with us.

Summary and Core Method: Tom: We're back with "Rule Extraction in Machine Learning: Chat Incremental Pattern Constructor." Jane, last segment we talked about the big idea. Now let's get into the nitty-gritty of how this thing actually works.

Jane: Okay, so the core mechanism is really elegant. It's all about learning transitions between words. When the system reads a sentence, it breaks it down into tokens, which are basically words. Then it records every time one word follows another.

Tom: So it's building a graph, a network of words where the connections show what tends to come next.

Jane: Precisely. And this is where it gets clever. It doesn't just look at single words. It can look at longer patterns, up to a certain length, like "the cat" pointing to "sat." That gives it context.

Tom: But just having a map isn't enough. How does it decide which word to actually say next when there are multiple options?

Jane: That's the scoring part. It uses something called a Jaccard similarity score. Think of it like this: it builds a little basket of words related to the prompt, and then a basket of words related to each possible next word. The more those baskets overlap, the higher the score.

Tom: And it doesn't stop there. The paper mentions it also uses dictionary definitions to expand those baskets. So if the prompt has "cat," it might also look up "cat" and add "feline" and "animal" to the basket.

Jane: Right, that's the definition expansion. It gives the system a bit of semantic understanding without using any neural networks. It's using the dictionary as a kind of knowledge base.

Tom: And there's a heuristic layer on top of that. The paper talks about English-rule bonuses. For example, if you just used the word "an," it might give a bonus to candidates that start with a vowel sound.

Jane: It's like teaching it a few basic grammar rules to nudge it in the right direction. And then there's a repetition penalty. If a word has already been used a lot in the response, it gets a lower score to prevent it from getting stuck in a loop.

Tom: So it's a combination of raw data from the map, semantic knowledge from the dictionary, and a few hand-coded rules to keep it on track. It's a very layered approach.

Jane: And it's all deterministic. Given the same state and the same prompt, it will always produce the same output. That's a huge advantage for debugging and for reproducibility.

Tom: It's like a recipe with exact measurements. You can follow the steps and know exactly what you're going to get. That's something you can't say for most modern AI systems.

Jane: Exactly. And this design choice makes it a perfect platform for studying how symbolic learning works, because you can see every single decision it makes.

Tom: So we have the map, the scoring, and the heuristics. But how does it actually learn over time? That's what I want to know next.

Improvements and Implementation: Tom: Welcome back. We're deep into "Rule Extraction in Machine Learning: Chat Incremental Pattern Constructor." Jane, we've covered the basics and the scoring. Now, what makes this implementation special? What are the improvements over just a simple idea?

Jane: The paper goes into a lot of detail on the engineering, and that's where it gets really interesting. The author, Nwokocha, has implemented this in C++, and it's not just a toy. It has a real, embedded dictionary that it parses at startup.

Tom: So it's not just looking at word adjacency. It has a whole lexical database built in.

Jane: Exactly. And it caches the definitions and part-of-speech tags for every word. So when it's scoring a candidate, it doesn't have to re-parse the dictionary every time. It's all pre-computed and ready to go.

Tom: That's a smart optimization. It makes the scoring much faster. The paper also mentions it uses bitsets for the similarity calculation. Can you explain that?

Jane: Sure. Instead of comparing lists of words, it represents the context and the candidate as a bitset, which is like a long row of ones and zeros. Each position in that row represents a word in its vocabulary. If the word is present, it's a one; if not, it's a zero.

Tom: And comparing those rows is incredibly fast for a computer. It's just a bitwise operation.

Jane: Right. It turns a complex set comparison into a simple, hardware-accelerated calculation. That's a big deal for performance.

Tom: And there's more. The paper talks about persistence. You can save the entire knowledge base to a file and load it back later. That means it can learn from one session and use that knowledge in the next.

Jane: It's like giving the system a memory that survives a reboot. It saves the graph, the interned strings, everything. And it does it atomically, so you don't corrupt the file if something goes wrong.

Tom: That's crucial for a real-world system. You can't have it forgetting everything it learned every time you turn it off.

Jane: And the paper also mentions concurrency. It can learn from multiple files at the same time using parallel processing. That makes it scalable to larger datasets.

Tom: So it's not just a clever algorithm. It's a properly engineered piece of software. That's what separates a paper that's just an idea from a paper that's a working system.

Jane: And that's what makes it so exciting. It's a fully functional platform that you can actually experiment with, not just read about.

Tom: So we have a fast, persistent, concurrent, symbolic learner. What does that mean for the future? Let's bring in the rest of the team to weigh in.

Conclusion: Tom: We're wrapping up our discussion on "Rule Extraction in Machine Learning: Chat Incremental Pattern Constructor." Jane, before we let you go, what's the big takeaway for our listeners?

Jane: The big takeaway is that this paper shows a viable path toward AI that we can actually understand. It's not trying to compete with massive language models on raw power. Instead, it's offering a different value proposition: transparency.

Tom: And that's a huge deal. Lu, from a research perspective, what excites you most about this?

Lu: The potential for it to be a testbed for symbolic learning. Because every decision is explicit, you can use this to study how knowledge accumulates and how different heuristics affect the learning process. It's a perfect laboratory.

Meng: From an engineering standpoint, I love that it's not just a paper. It's a working C++ program with a real dictionary, a binary persistence format, and concurrency. That means I could actually deploy this in a system today if I needed explainable text generation.

Tom: And Lalam, you're the model here. What's the most impactful vision you see coming out of this?

Lalam: I see this as a step toward a future where AI systems can explain their own reasoning in a way that's grounded in human-readable rules. This could change how we build trust in automated systems, especially in fields like education or legal tech, where the reasoning is as important as the answer.

Jane: That's a beautiful way to put it. It's not about making AI smarter in a way we can't follow. It's about making AI smarter in a way we can check.

Tom: So, to our listeners, if you're tired of black boxes and you want to see how a machine can learn with a clear, inspectable logic, give this paper a read. It's a breath of fresh air in a field that often feels like it's all about bigger and more opaque models.

Jane: We're saying goodbye to "Rule Extraction in Machine Learning: Chat Incremental Pattern Constructor." It's been a great conversation, and we're ready to see what else is on arXiv.

Tom: Thanks for listening, everyone. We'll catch you on the next one.

Caleb Princewill Nwokocha

cs.LG

Submitted: 2026-08-11

License: http://creativecommons.org/licenses/by-sa/4.0/

Importance score: 42/100

The gist: The paper presents Chat Incremental Pattern Constructor (ChatIPC), a lightweight incremental symbolic learning system that extracts ordered token-transition rules from text, enriches them with

Key concepts

ChatIPC
This is a system designed to build symbolic rules directly from text, rather than training a black-box neural network. It creates an inspectable model by mapping word transitions, allowing users to see exactly why the AI made a decision.
Word Transition Mapping
The system breaks sentences into words (tokens) and records every time one word follows another. This forms a graph or map of connections, showing how patterns evolve from input to become the basis for generating output.
Scoring Mechanism
To decide which word comes next, ChatIPC uses a Jaccard similarity score based on overlapping sets of related words. It also applies heuristics like English-rule bonuses and repetition penalties to guide the selection.
Deterministic Learning
The system is deterministic, meaning it always produces the same output for a given input. It is implemented in C++ with persistence, allowing it to save its learned knowledge and use it across multiple sessions.

Terminology

Summary

The paper presents Chat Incremental Pattern Constructor (ChatIPC), a lightweight incremental symbolic learning system that extracts ordered token-transition rules from text, enriches them with definition-based expansion, and constructs responses by similarity-guided candidate selection. The system may be viewed as a rule extractor operating over a token graph rather than a conventional classifier.

ChatIPC extracts transition rules from sequences of tokens. Given an n-gram text fragment w1, w2,..., wi−1, wi, wi+1, the system induces an ordered pair w1, w2,..., wi−1, wi → wi+1. Repeated observations strengthen the symbolic structure of the knowledge base, producing a graph-like memory of token flow. The system accumulates symbolic edges in a knowledge base rather than learning continuous parameters.

Let Σ denote the token vocabulary. ChatIPC maintains a directed N-gram transition relation E ⊆ Σ≤N × Σ. The knowledge base at time t is written as Gt = (Vt, Et), where Vt ⊆ Σ is the set of known tokens and Et is the set of learned N-gram transitions. The token vocabulary is interned so that repeated strings map to stable identifiers.

The updated C++ code introduces the tokenize others function for processing arbitrary text input. If the entire string possesses a valid dictionary definition, it converts to lowercase and returns it directly as a single token. Otherwise, it splits into distinct subtokens at spaces, underscores, hyphens, slashes, camelCase transitions, or boundaries between alphabetic characters and numeric digits. Each subtoken is passed to a morphological lemmatizer. The tokenization algorithm incorporates a numeric-to-word converter that expands numbers like 1,234.56 into English word equivalents.

Three caches are central: a list of dictionary entries, a cache from lexical keys to definition-token expansions, and a cache from lexical keys to normalized part-of-speech tags.

Definition expansion is a breadth-first semantic closure over the dictionary graph. If a token has a definition, the system tokenizes the definition and collects the resulting words, iterating up to a chosen depth. The expansion operator D(d) is iterative: D(1)(w) = D(w), and for depth d > 1, D(d)(w) = ∪ D(u) for u ∈ D(d−1)(w). Deduplication is essential, since definition graphs may contain repeated words or cycles.

Candidate scoring has two layers. First, the system computes a set similarity score between the aggregated prompt-response context, each candidate token, and their dictionary neighborhood. Second, the score is adjusted by linguistic heuristics and a repetition penalty.

The adjusted score is S(c) = S0(c) + H(c x) − λn(c), where S0(c) is the Jaccard similarity, H(c x) encodes English usage, and n(c) counts recent occurrences of c. This formulation separates three concerns. The similarity term measures semantic overlap. The heuristic term injects shallow grammatical structure. The penalty term suppresses pathological repetition.

The heuristic function checks several conditions: at sentence boundaries, candidates beginning with uppercase receive a bonus; after articles a and an, vowel-sound heuristics apply including exceptional words like hour, honest, and user; certain candidate classes are favored after determiners, prepositions, or auxiliary verbs; part-of-speech classes reward plausible candidates. The point is not that these heuristics fully model grammar. Rather, they act as low-cost structural bias terms.

The scoring subsystem converts context and candidates into bitsets over the interned vocabulary. The score is the Jaccard index J(A, B) = A ∩ B / A ∪ B, with zero when the union is empty. Using bitsets is an important design choice. It reduces similarity computation to bitwise operations and population counts. When the candidate set is sufficiently large (Cl ≥ 256) and OpenMP target devices exist, the implementation offloads similarity calculation to a GPU; otherwise it uses threaded parallelism on the host.

The response constructor selects the candidate set from the prompt token for the first output step, then from the generated token for each subsequent step. If the current generated token is unavailable, the code falls back to scanning prompt tokens in smaller n-gram sizes. The selected candidate is the token with the highest adjusted score, with ties broken lexicographically.

Two learning pathways exist: learning from external files (adjacent pairs inserted into the knowledge base) and learning from interactive sessions (prompt tokens and generated tokens inserted as transitions). Persistence uses a binary save file with atomic-commit pattern: write to temporary file, flush, remove previous file, rename into place. The file includes a magic value, version number, definition depth, and serialized string pool. The serialization uses Little-Endian Base 128 (LEB128) variable-length encoding for integers, array counts, and string lengths.

Given a text stream x(t) = (x1(t), x2(t),..., xnt(t)), ChatIPC induces N-gram transition rules for each target token xi from preceding contexts of length k ∈ 1,..., min(i−1, N). The cumulative rule set after T observations is R1:T = ∪ R(t). The transition map is BT = C ↦ v: (C, v) ∈ R1:T.

For a prompt P = (p1,..., pm) and current response prefix R = (r1,..., rk), the context sets are SP = ∪ pi ∪ D(d)(pi) and SR = ∪ rⱼ ∪ D(d)(rⱼ), with A(P, R) = SP ∪ SR. For a candidate token c, B(c) = c ∪ D(d)(c).

At each step l, ChatIPC chooses yl = arg max J(A(·), B(c)) + H(·) − λnRl−1(c) over c ∈ Cl.

Time complexity: Tlearn(n) = O(n · N) for learning; Tdef(d) = O(bd) for definition expansion; Tscore(m) = O(m · q) for candidate scoring, where q reduces to O(V/64) with bitsets. Space complexity: Spool = O(V · Lavg) for the string pool; Sgraph = O(E · N) for the transition graph; Sdef = O(Vdef · bd) for definition caches.

Generation terminates for one of four reasons: length bound reached, candidate set empty, fallback search fails, or candidate would induce a trivial two-cycle. This is a conservative design.

The paper situates ChatIPC within rule extraction literature, contrasting it with post-hoc extraction methods including Fu's 1991 rule learning, Towell and Shavlik's refined-rule extraction, TREPAN, X-TREPAN, TREPAN Reloaded, MAIRE, ECLAIRE, PBRE, FIRE, REFUEL, and ANDRE. The key distinction: ChatIPC does not search inside a trained neural network... Instead, it induces explicit token-transition rules directly from observed text. The system builds its symbolic graph as the primary model state rather than extracting a surrogate explanation.

The paper discusses sensitivity to definition depth d, repetition penalty λ, and prelearning. The definition depth controls how far the definition expansion reaches. The maximum response length bounds how long the greedy path may continue. The repetition penalty controls local oscillation. Suggested metrics include transition coverage, response length utilization, repetition rate, candidate diversity, and runtime per token. An ablation study is especially natural for ChatIPC because each component is modular and explicit.

"The main claim is not that ChatIPC is equivalent to a neural language model, but that it exemplifies a transparent and mathematically tractable alternative: a text constructor whose behavior can be explained in terms of explicit symbolic rules."

Improvements for AI systems

Based on the paper, here are specific improvements I can make to an AI system, and what the improved system can do:

  • Implement a directed n-gram transition graph (context → next token) as a persistent, inspectable knowledge base alongside any neural model.

  • Use interning (canonical string IDs) to reduce memory and enable fast set operations.

  • Build a dictionary cache that maps each token to its definition tokens and part-of-speech tags.

  • Use iterative breadth-first expansion (up to depth d) to create a symbolic semantic neighborhood for each token.

  • Cache expansions to avoid recomputation.

  • Represent context and candidate semantic sets as bitsets over the interned vocabulary.

  • Compute Jaccard similarity via bitwise AND/OR and population counts (fast, deterministic).

  • Combine with:

  • English-rule heuristic bonus (sentence boundary, article-vowel compatibility, part-of-speech plausibility)

  • Repetition penalty (λ · recent count)

  • Lexicographic tie-breaking for determinism

  • If the current context has no outgoing transitions, fall back to shorter context suffixes.

  • If still no candidates, fall back to the latest prompt token with outgoing edges.

  • Detect and break two-cycles (e.g., A→B→A→B) during generation.

  • Apply a recent-count penalty to discourage local oscillation.

  • Save/load the knowledge base with:

  • Magic value + version check

  • LEB128 variable-length integer encoding for compactness

  • Atomic rename (write to temp, then rename)

  • This enables reproducible state snapshots and separation of learning from generation.

  • Use OpenMP for:

  • Parallel file learning (dynamic schedule)

  • Candidate scoring (host threads or GPU offload via OpenMP target teams when candidate set ≥ 256)

  • Ensure determinism via explicit tie-breaking.

  • Normalize tokens (lowercase, split on spaces/underscores/hyphens/slashes/camelCase/digit boundaries).

  • Convert numeric tokens (e.g., 1,234.56) to English word sequences (one, thousand, two, hundred, thirty, four, point, five, six) so they integrate with dictionary-based heuristics.

  • Every generated token can be traced to:

  • A specific learned transition rule

  • Its definition-expanded semantic neighborhood

  • Its Jaccard score, heuristic bonus, and repetition penalty

  • No hidden latent state; failures are local and diagnosable.

  • Learns from:

  • External text files (token streams)

  • Interactive prompts and its own generated responses

  • The knowledge base grows with use, and saved states can be resumed or shared.

  • Handles unseen or sparse contexts via:

  • N-gram backoff

  • Fallback to prompt tokens

  • Definition-based semantic generalization

  • Avoids degenerate loops via cycle suppression and repetition penalties.

  • Bitset Jaccard computation is hardware-friendly and deterministic.

  • Parallelizable across candidates and files without changing output.

  • Save/load with versioned binary format enables:

  • Ablation studies (remove definition expansion, heuristics, penalties)

  • Parameter sensitivity analysis (depth d, penalty λ, max length L)

  • Exact replication of generation given the same state and prompt

  • The symbolic graph can serve as:

  • A prior or constraint for neural generation

  • A post-hoc explanation layer for neural outputs

  • A fallback when neural confidence is low

If you want, I can also provide a concrete pseudocode or C++-style implementation sketch for any of these improvements.

Abstract

Rule extraction is a central problem in interpretable machine learning because it seeks to convert opaque predictive behavior into human-readable symbolic structure. This paper presents Chat Incremental Pattern Constructor (ChatIPC), a lightweight incremental symbolic learning system that extracts ordered token-transition rules from text, enriches them with definition-based expansion, and constructs responses by similarity-guided candidate selection. The system may be viewed as a rule extractor operating over a token graph rather than a conventional classifier. I formalize the knowledge base, definition expansion, candidate scoring, repetition control, English-rule heuristics, and response construction mechanisms used by ChatIPC. I further situate the method within the literature on rule extraction, decision tree induction, association rules, interpretable machine learning, and sequence construction. The updated C++ code implementation of ChatIPC is also reviewed in detail: it parses an embedded dictionary, normalizes lexical keys, caches definition tokens and part-of-speech tags, computes Jaccard scores on bitsets, applies heuristic linguistic bonuses, and persists the knowledge base with a versioned binary format. The paper emphasizes mathematical formulation and algorithmic clarity, and it provides pseudocode for the learning, scoring, and construction algorithms.

Sources

Related papers