Documentation

Linglib.Core.Computability.InductiveInference

Language identification in the limit #

A learner sees the strings of an unknown language one at a time, in any order, with repetitions and pauses, and after each presentation conjectures a language. It identifies the language in the limit if on every such presentation its conjectures are eventually the language itself. A class of languages over a countable set of strings is identifiable exactly when it is countable and its languages have telltales, a telltale of a language being a finite subset that no member of the class properly inside the language contains. Hence no class containing an infinite language and all its finite subsets is identifiable, nor any class containing a strictly increasing chain of languages and its union.

Implementation notes #

The characterization is the ineffective one: a learner is any function on finite sequences, computable or not, and conjectures a language rather than a name for one, the two coming to the same when effectiveness is not required. Effective inference of an indexed family of recursive languages further needs the telltales to be uniformly enumerable, which is not formalized. A pause lets the empty language have a text; on nonempty languages pauses change nothing, since a learner can treat a pause as a repetition of the previous string. The strings form an arbitrary countable type, the words over an alphabet being one instance.

References #

@[reducible, inline]
abbrev InductiveInference.Text (α : Type u_2) :
Type u_2

A text presents strings one at a time, none being a pause in which nothing is presented.

Equations
Instances For
    def InductiveInference.content {α : Type u_1} (σ : List (Option α)) :
    Set α

    The strings occurring in a finite sequence of presentations.

    Equations
    Instances For
      def InductiveInference.Text.content {α : Type u_1} (t : Text α) :
      Set α

      The strings occurring in a text. A text for L is one whose content is L.

      Equations
      • t.content = {x : α | some x ∈ t}
      Instances For
        @[reducible, inline]
        abbrev InductiveInference.Learner (α : Type u_2) :
        Type u_2

        A learner conjectures a language from each finite sequence of presentations.

        Equations
        Instances For
          def InductiveInference.Identifies {α : Type u_1} (φ : Learner α) (L : Set α) :

          φ identifies L in the limit when on every text for L its conjectures are eventually L.

          Equations
          Instances For
            def InductiveInference.Identifiable {α : Type u_1} (𝓛 : Set (Set α)) :

            A class of languages is identifiable in the limit when one learner identifies each of its languages.

            Equations
            Instances For
              def InductiveInference.IsTelltale {α : Type u_1} (𝓛 : Set (Set α)) (L T : Set α) :

              T is a telltale of L in 𝓛: a finite subset of L that no language of 𝓛 properly inside L contains. Once T has been presented, conjecturing L cannot overgeneralize.

              Equations
              Instances For

                Content #

                theorem InductiveInference.content_finite {α : Type u_1} (σ : List (Option α)) :
                (content σ).Finite
                @[simp]
                theorem InductiveInference.mem_content {α : Type u_1} {σ : List (Option α)} {x : α} :
                x ∈ content σ ↔ some x ∈ σ
                @[simp]
                theorem InductiveInference.content_nil {α : Type u_1} :
                content [] = ∅
                @[simp]
                theorem InductiveInference.content_append {α : Type u_1} (σ τ : List (Option α)) :
                content (σ ++ τ) = content σ ∪ content τ
                @[simp]
                theorem InductiveInference.content_singleton_some {α : Type u_1} (x : α) :
                content [some x] = {x}
                @[simp]
                theorem InductiveInference.content_singleton_none {α : Type u_1} :
                content [none] = ∅
                theorem InductiveInference.exists_content_eq {α : Type u_1} {T : Set α} (hT : T.Finite) :
                ∃ (σ : List (Option α)), content σ = T

                Every finite set is the content of a finite sequence.

                theorem InductiveInference.Text.content_take_subset {α : Type u_1} (t : Text α) (n : ℕ) :
                InductiveInference.content (Stream'.take n t) ⊆ t.content
                theorem InductiveInference.Text.eventually_subset_content_take {α : Type u_1} {t : Text α} {T : Set α} (hT : T.Finite) (hsub : T ⊆ t.content) :
                ∀ᶠ (n : ℕ) in Filter.atTop, T ⊆ InductiveInference.content (Stream'.take n t)

                Every finite part of a text has been presented after finitely many steps.

                theorem InductiveInference.Text.content_appendStream {α : Type u_1} (σ : List (Option α)) (t : Text α) :
                theorem InductiveInference.Text.take_appendStream {α : Type u_1} (σ : List (Option α)) (t : Text α) (m : ℕ) :
                Stream'.take (σ.length + m) (σ ++ₛ t) = σ ++ Stream'.take m t
                theorem InductiveInference.Text.exists_content_eq {α : Type u_1} [Countable α] (L : Set α) :
                ∃ (t : Text α), t.content = L

                Every language over a countable set of strings has a text.

                theorem InductiveInference.Text.exists_frequently {α : Type u_1} {L : Set α} {P : List (Option α) → Prop} {e : Text α} (he : e.content = L) (hP : ∀ (σ : List (Option α)), InductiveInference.content σ ⊆ L → ∃ (τ : List (Option α)), InductiveInference.content τ ⊆ L ∧ P (σ ++ τ)) :
                ∃ (t : Text α), t.content = L ∧ ∃ᶠ (n : ℕ) in Filter.atTop, P (Stream'.take n t)

                If a property of finite sequences can always be reached by extending within L, some text for L meets it infinitely often: the text the proofs of Gold and of Angluin build.

                The characterization #

                theorem InductiveInference.Identifiable.mono {α : Type u_1} {𝓛 𝓜 : Set (Set α)} (h : 𝓛 ⊆ 𝓜) (hm : Identifiable 𝓜) :
                theorem InductiveInference.exists_isTelltale {α : Type u_1} [Countable α] {𝓛 : Set (Set α)} {φ : Learner α} (hφ : ∀ L ∈ 𝓛, Identifies φ L) {L : Set α} (hL : L ∈ 𝓛) :
                ∃ (T : Set α), IsTelltale 𝓛 L T

                A learner identifying each language of 𝓛 gives each of them a telltale, the content of a finite sequence after which it can no longer be moved off L.

                theorem InductiveInference.identifiable_of_isTelltale {α : Type u_1} {𝓛 : Set (Set α)} (hc : 𝓛.Countable) (hT : ∀ L ∈ 𝓛, ∃ (T : Set α), IsTelltale 𝓛 L T) :

                A countable class whose languages have telltales is identifiable, by conjecturing the first language in an enumeration whose telltale has appeared and which contains the data.

                theorem InductiveInference.identifiable_iff {α : Type u_1} [Countable α] {𝓛 : Set (Set α)} :
                Identifiable 𝓛 ↔ 𝓛.Countable ∧ ∀ L ∈ 𝓛, ∃ (T : Set α), IsTelltale 𝓛 L T

                A class of languages over a countable set of strings is identifiable in the limit exactly when it is countable and each of its languages has a telltale. Angluin's condition without its effectiveness requirement, and Gold's observation that only countably many conjectures exist.

                theorem InductiveInference.identifiable_of_finite {α : Type u_1} {𝓛 : Set (Set α)} (h : 𝓛.Finite) :

                Every finite class is identifiable.

                theorem InductiveInference.not_identifiable_of_finite_subsets {α : Type u_1} [Countable α] {𝓛 : Set (Set α)} {L : Set α} (hL : L ∈ 𝓛) (hinf : L.Infinite) (hfin : ∀ T ⊆ L, T.Finite → T ∈ 𝓛) :

                Gold's theorem: a class containing an infinite language and all its finite subsets is not identifiable from text. In particular no class containing every finite language and an infinite one is.

                theorem InductiveInference.not_identifiable_of_strictMono_iUnion {α : Type u_1} [Countable α] {𝓛 : Set (Set α)} {A : ℕ → Set α} (hA : StrictMono A) (hmem : ∀ (n : ℕ), A n ∈ 𝓛) (hU : ⋃ (n : ℕ), A n ∈ 𝓛) :

                A class containing a strictly increasing chain of languages and its union is not identifiable from text, since the finite telltale of the union would already lie in a member of the chain.