\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Needed by:
Input Designs
Sheet PDF
Graph PDF

Consistent Inductors


We discuss inductors that produce relations consistent with their given datasets.


Let $(x_1, y_1), \dots , (x_n, y_n)$ be a dataset in $X \times Y$. Let $\mathcal{R} $ be the set of all relations on $X \times Y$.

A consistent inductor $\set{G_n: (X \times Y)^n \to \mathcal{R} }_{n}$ is one for which, for all $n \in \N $, for all $D_n \in (X \times Y)^n$, $D$ is consistent with $G_n(D_n)$. In other words, a consistent inductor always produces a relation with which the dataset is consistent.

The interpretation follows. Fix a relation $R^\star$. And let every dataset “shown” to the algorithm $G_n$ be constructed by selecting elements from $R^{\star}$. In other words, every dataset is a sequence in $R^\star$. In this case, a dataset $D_n \in (X \times Y)^n$ is always consistent with $R^\star$ and so a consistent inductor will never “eliminate” $R^{\star}$. In other words, the inductor, in order to be consistent “must eliminate” every inconsistent relation.

We may “hope” to give the algorithm a “large and diverse” datset, so that several of the elements of $R^\star$ are included. In this case, the algorithm can “eliminate” many smaller relations in $\mathcal{R} $ which did not include records in the dataset.

Functionally consistent

The rub is that any dataset is consistent with the complete relation $X \times Y$. So we can often consider a set $\mathcal{H} \subset \mathcal{R} $ of relations. It is common to call this a hypothesis class, especially for the case in which it consists of functional relations.

Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view