Declarative Feature Synthesis from Logical Specifications

17 concepts13 papers3 proposals

Machine learning models fundamentally operate on propositional feature vectors—fixed-length arrays of numbers or booleans. However, real-world data is rarely flat; it is inherently relational, hierarchical, and structural. Whether dealing with dependency trees in natural language processing or state graphs in automated planning, bridging the gap between raw relational structures and propositional learning algorithms presents a major challenge.

Traditionally, engineers have bridged this gap through manual feature engineering, writing imperative code to traverse structures and extract specific attributes. This approach is fragile, tightly couples the feature representation to the codebase, and struggles to scale when structural relationships grow combinatorially.

To solve this, a powerful paradigm emerged: declarative feature synthesis. Instead of writing how to extract a feature using imperative code, researchers write a declarative specification of what structural properties the feature should capture using formal logic or domain-specific grammars. An underlying engine then automatically compiles, grounds, or searches these specifications to generate the required feature vectors.


Decoupling Representation from Execution

The first step toward declarative feature engineering involves abstracting feature definitions out of the core source code and into external, formal configurations. This separation of concerns ensures that changing the model's representation does not require rewriting its execution logic.

In natural language processing, this architectural shift was prominently demonstrated in data-driven dependency parsing. Hall et al., in developing MaltParser for A generic architecture for data-driven dependency parsing, showed that complex, state-dependent linguistic features could be defined via an external formal specification language. This allowed the system to perform multi-step lookups based on structural relationships within a parser's current configuration (such as the attributes of a token's head) without modifying the underlying system implementation.

A similar evolution occurred in coreference resolution—the task of determining which noun phrases refer to the same real-world entity. Early toolkits like BART, introduced by Ponzetto et al. in BART: A modular toolkit for coreference resolution, utilized external XML-based configurations to decouple feature engineering from learning algorithms.

This concept was pushed to its logical conclusion by the SUCRE system, developed by Kobdani et al. in SUCRE: A Modular System for Coreference Resolution and Supervised Coreference Resolution with SUCRE. The authors introduced a specialized regular language to define linguistic features. Instead of hard-coding extraction routines, users declaratively specified access to complex attributes—such as semantic classes, grammatical roles, and structural positions—allowing the underlying engine to handle the data-structure traversals automatically.


Logic Programming and Relational Templates

While external configurations decouple code, logic programming provides the mathematical machinery to synthesize entirely new features from basic data signatures. By treating data as a collection of logical facts, features can be expressed as intensional relations (rules) rather than extensional lists.

Consider Markov Logic Networks (MLNs), which combine first-order logic with probabilistic graphical models. As outlined by Poon in Markov Logic in Natural Language Processing: Theory, Algorithms, and Applications, first-order logic rules serve as abstract templates for constructing propositional features. Instead of manually coding features for every specific task interaction, a practitioner writes high-level logical rules. The system then automatically expands these templates into specific grounded features based on the input data. This strategy allowed Meza-Ruíz et al. in Multilingual Semantic Role Labelling with Markov Logic to efficiently generate complex feature sets from basic linguistic attributes like lemmas and dependency relations across multiple languages.

+-------------------------------------------------------------------+
| Abstract Logical Template (First-Order Logic Rule)                |
| e.g., HasRole(x, Verb) ∧ DependencyLink(x, y) ⇒ SemanticArg(y)    |
+-------------------------------------------------------------------+
                                 │
                                 ▼  [Grounding Engine]
+-------------------------------------------------------------------+
| Grounded Propositional Features (Evaluated against raw data)      |
| - Feature 1: HasRole(word_3, Verb) ∧ DependencyLink(word_3, word_5)|
| - Feature 2: HasRole(word_7, Verb) ∧ DependencyLink(word_7, word_2)|
+-------------------------------------------------------------------+

This declarative approach is equally powerful when paired with kernel-based learning. The kLog framework, introduced by Frasconi et al. in kLog: A Language for Logical and Relational Learning with Kernels (Extended Abstract), uses declarative logic programming to derive complex relational features from basic data signatures. kLog transforms these logical representations into graphs (a process called "graphicalization"), allowing efficient graph kernels to compute similarities over the resulting structures.

As demonstrated by Verbeke et al. in A Statistical Relational Learning Approach to Identifying Evidence Based Medicine Categories and extended to NLP via kLogNLP by Verbeke et al. in kLogNLP: Graph Kernel-based Relational Learning of Natural Language, this mechanism allows researchers to incorporate domain-specific background knowledge—such as dependency tree roots or section contexts—as intensional logic rules. New structural patterns can be defined as logical signatures and compiled on the fly, entirely bypassing the need to re-process or flatten the underlying raw dataset.


Automated Feature Synthesis via Description Logics

The ultimate realization of this paradigm moves from manually writing logical rules to automatically searching a space of logical expressions to discover relevant features. This is achieved by defining a formal grammar over Description Logics (DL).

Description Logics are structured fragments of first-order logic designed to reason about concepts (unary predicates) and roles (binary predicates). By defining a generative grammar over DL operators—such as intersection ($\sqcap$), composition ($\circ$), and transitive closure ($^+$)—a system can automatically construct an infinite pool of candidate features from a few base predicates.

Early foundations were laid by Cumby et al. in Learning with Feature Description Logics, who introduced a Feature Generating Function (FGF). The FGF leverages descriptions from a Feature Description Logic to automatically re-represent relational domain elements as propositional features. By utilizing efficient subsumption checking—determining mathematically whether one logical concept is a subset of another—the system automates feature creation and avoids complex combinatorial searches during learning.

This automated synthesis has proven uniquely transformative for generalized planning, where the goal is to learn a single policy or "sketch" that solves every instance of a problem domain (like stacking blocks) regardless of its size.

  Base Predicates (e.g., Clear(x), On(x, y))
                     │
                     ▼ [Description Logic Grammar]
  Infinite Pool of Candidate Features 
  (e.g., ∃On⁺.Clear, ObjectCount(∃On.Clear))
                     │
                     ▼ [Max-SAT Solver / Pruning]
  Minimal, Expressive Feature Set for General Policy

As shown by Bonet et al. in Learning Features and Abstract Actions for Computing Generalized Plans. and Learning General Planning Policies from Small Examples Without Supervision, a formal grammar based on description logic can automatically generate a vast pool of candidate boolean and numerical features from basic domain predicates. By framing the selection of these features as a Weighted Max-SAT problem, the system discovers complex relational concepts (such as transitive closures) required to solve general tasks without human-provided plans.

This approach was further extended by Drexler et al. in Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width, where a description logic grammar was used to automatically generate state features (such as object counts or relational properties) that define the exact conditions for transitioning between subgoals.


Why It Works: The Intuition

To understand why declarative feature synthesis works so well, consider the alternative: searching a raw graph or relational database for patterns. If you want to find a feature that captures "a node connected to another node that satisfies property $X$ via a path of arbitrary length," writing imperative code requires nested loops, recursion, edge-case handling, and custom data structures.

By using a formal logic or grammar, this complex structural query is compressed into a single, compact expression (e.g., a description logic concept like $\exists \text{link}^+ . X$). The underlying engine leverages two core mechanisms to make this highly efficient:

  1. Grounding and Expansion: Abstract rules act as templates. The engine only evaluates them against actual data instances, expanding them into concrete propositional features only where the data supports it. This prevents the combinatorial explosion that occurs when trying to generate all possible feature combinations upfront.
  2. Logical Subsumption and Solvers: When automatically synthesizing features, description logic allows the system to determine if one feature is a logical subset of another (subsumption) purely by analyzing the syntax of the rule, without looking at the data. Combined with combinatorial optimization tools like Max-SAT solvers, the system can mathematically prune redundant features and select the minimal, most expressive set of abstractions necessary for the learning task.

Ultimately, declarative feature synthesis works because it shifts the burden of structural traversal from the human programmer (or an unconstrained search algorithm) to a highly optimized logical reasoning engine.

Key Foundational Work

Learning with Feature Description Logics (2002) — contributed 2 concept elements to this direction.
A generic architecture for data-driven dependency parsing (2005) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_declarative_feature_engineering_accadeff,
  title = {declarative feature engineering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/declarative-feature-engineering/rdr_accadeffb6fc4819b51233cd8300aa5a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_declarative_feature_engineering_accadeff_v1,
  title = {declarative feature engineering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/declarative-feature-engineering/rdr_accadeffb6fc4819b51233cd8300aa5a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake