Draft:Algebraic Machine Learning

• Comment: Possibly AI generated. Not super notable yet. Please write a review/summary paper, not a Wikipedia page :) Caleb Stanford (talk) 14:44, 20 August 2025 (UTC)

---

In Symbolic Artificial Intelligence, Algebraic Machine Learning (AML) is a machine learning method that uses universal algebra and model theory as its foundational framework, without relying on optimization or statistics. In AML, learning tasks, from data, constraints, and goals, are encoded as algebraic identities within an algebraic structure, typically a semilattice. The method involves computing a model of these identities, which is decomposed as a subdirect product. Among all possible models, the freest model corresponds to the formal logical deductive closure of the identities. Generalization occurs by discarding factors in the subdirect decomposition of the freest model. AML has been applied on data-driven pattern recognition image classification on benchmark datasets such as CIFAR-10, or MNIST. It has also been used in formal problems, such as finding Hamiltonian cycles in graphs, sudokus, maze solving, and the n-queens completion problem. In this cases, AML learns directly from the problems' specifications without relying on explicit search algorithms.

Overview

AML relies on semantic embeddings., as defined in classical universal algebra and model theory, to represent problems as algebraic structures Data, constraints, and rules are encoded using first-order logic, resulting in a set of algebraic sentences. The sparse crossing algorithm, used for the training stage, iteratively modifies and evolves these algebraic structures to model the target problem. Generalization can be achieved by finding a small subset of the subdirect decomposition components that model the positive and negative algebraic sentences.

Semantic embedding

Semantic embedding is the process of encoding the data, constraints and rules of a problem as a set of atomic sentences, $R^{+}$, and a set of negated atomic sentences, $R^{-}$, that collectively play the role of axioms or identities for the algebraic models.

The embedding constants describe the smallest concepts used to describe a problem. E.g. embedding constants could express: "pixel at position (3,4) is red", "label: it is a boat", or "graph edge: node 3 $\rightarrow$ 12". Those constants are combined to describe more complex ideas. The embedding constants can be seen as the alphabet used for the semantic embedding.

Terms describe complex ideas and are built as the idempotent union of embedding constants. E.g. an image is a collection of pixels covering the whole space, and a graph is a collection of constants representing nodes and vertices joining them.

An algebraic sentence establishes an order relation between two terms. E.g. the atomic sentence $\{label:boat\}<\{p_{1},p_{2},...,p_{n}\}$ can be used to encode that the image described by that collections of pixels corresponds to a boat.

The freest model and the full crossing algorithm

The freest model for a given set of axioms is the one in which all the atomic sentences, and their logical consequences, are the only true statements satisfied by the model. Any other model satisfies additional atomic sentences and is therefore considered less free than the freest model.

Given a model $M$ and and a set of atomic sentence $r$ of the form $a\leq b$, the full crossing of in $M$ can be used to construct the freest semilattice model that satisfies $r$ and all the atomic sentences satisfied by $M$, specifically represented as a subdirect decomposition. This process is iterative, where one by one, each algebraic sentence in $R^{+}$ is introduced into the model:

1. The process generally begins with the term algebra, which is the model that only satisfies the positive sentences that are true in every model.
2. Applying the full crossing operator for a given atomic sentence $r$ to a model $M$ produces the freest model that satisfies all atomic sentences of $M$, the atomic sentence $r$, and their logical consequences.
3. The process is repeated for all atomic sentences in $R^{+}$.

As long as the set of axioms is consistent, meaning that it contains no logical contradictions, this procedure is guaranteed to result in the freest model that satisfies $R$.

The freest model does not generalize. In essence, it acts as a memory, strictly satisfying only the positive axioms and their logical consequences.

Sparse crossing

The full crossing operation produces the freest model, which does not generalize and typically presents a large number of subdirect components so its computation usually becomes intractable. The sparse crossing addresses both this issues. Given a set of axioms, the sparse crossing algorithm constructs a model that satisfies both the atomic and negated atomic sentences and is represented as a subdirect product, with only a subset of the components of the freest model. While the freest model only satisfies the atomic sentences that are logical consequences $R$, sparse crossing produces models that satisfy additional atomic sentences, thereby generalizing beyond the input set of axioms. Sparse crossing produces smaller models, which are computationally more tractable, and enables the model to generalize.

Given a set of axioms, the sparse crossing algorithm builds an algebraic model that:

• satisfies the positive and negative algebraic sentences;
• supports generalization;
• and remains computationally manageable.

Algorithm overview

The algorithm follows these steps:

1. Algebra construction: Express the axioms as a semilattice M.
2. Dual algebra construction: Build an auxiliary model, M*, that is a simplified version of the dual algebra of M.
3. Build trace constraints: Define the trace operator as a transformation from elements in M to elements in M*. For any algebraic sentence, we can define a transform sentence, which we refer to as trace constraint:$$\underbrace {a<b} _{M}\Rightarrow \underbrace {Tr(b)\in Tr(a)} _{M*}$$
4. Enforce trace constraints:
   1. Enforce the negative trace constraints from sentences in the $R^{-}$. This is done by creating new elements in M*.
   2. Enforce the positive trace constraints from sentences in the $R^{+}$. This is done by creating new elements in M.
5. After enforcing all trace constraints, all negated atomic sentences, $R^{-}$, are satisfied in M.
6. Crossing: Add and remove elements from M while keeping the trace constraints of all terms and constants unchanged. This allows the model to satisfy the atomic sentences without altering the already satisfied negative sentences.
7. Model reduction: It is possible to reduce the size of the model by removing elements in M while ensuring the trace constrains remain unaltered.

Applying sparse crossing once produces a model that satisfies $R$ but it does not necessarily have the most generalizing components of the subdirect decomposition of the freest model. In order to find the most generalizing models, sparse crossing is applied iteratively over $R$ or over subsets of $R$. The algorithm can leverage the components discovered in previous steps of this iteration to produce better components, leading to better generalizing models in a process that does not display overfitting.

See also

• Symbolic artificial intelligence
• Universal algebra
• Model theory
• Semilattice

References

• Martin-Maroto, Fernando; Abderrahaman, Nabil; Méndez, David; G. de Polavieja, Gonzalo (2025). "Algebraic Machine Learning: Learning as computing an algebraic decomposition of a task". arXiv:2502.19944 [cs.LG].
• "Algebraic AI (slides)" (PDF). AITP 2024. Retrieved 22 July 2025.
• Haidar, Imane M.; Sliman, Layth; Damaj, Issam W.; Haidar, Ali Massoud (2024). "High Performance and Lightweight Single Semi-Lattice Algebraic Machine Learning". IEEE Access. 12: 50517–50536. Bibcode:2024IEEEA..1250517H. doi:10.1109/ACCESS.2024.3376525.
• Haidar, Imane M.; Sliman, Layth; Damaj, Issam W.; Haidar, Ali M. (2024). "Legacy Versus Algebraic Machine Learning: A Comparative Study". 2nd International Congress of Electrical and Computer Engineering. EAI/Springer Innovations in Communication and Computing. pp. 175–188. doi:10.1007/978-3-031-52760-9_13. ISBN 978-3-031-52759-3.
• Martin-Maroto, Fernando; G. de Polavieja, Gonzalo (2022). "Semantic Embeddings in Semilattices". arXiv:2205.12618 [cs.DM].
• Malov, Dmitrii (August 2020). "Quantum Algebraic Machine Learning". 2020 IEEE 10th International Conference on Intelligent Systems (IS). pp. 426–430. doi:10.1109/IS48319.2020.9199982. ISBN 978-1-7281-5456-5.

This page will be placed in the following categories if it is moved to the article namespace.

Categories:

• Machine learning algorithms