Docs / Studies / Studies.HeinzKasprzikKotzing2012

Learning in the limit with lattice-structured hypothesis spaces

Heinz, J., Kasprzik, A. & Kötzing, T. (2012). Theoretical Computer Science, 457, 111–127

hypothesis spaces

A lattice space maps each word to a node of an upper semilattice, every node being the join of the nodes of finitely many words, and the language of a node is the words mapped at or below it. The lattice learner keeps the join of the nodes it has seen, and so identifies every language of the class in the limit. A class is a lattice class exactly when each finite set of words has a least language containing it and each language is the least containing some finite set. The paper's subregular classes are instances, on finite grammars: strictly local languages with arbitrary grammars are identifiable exactly when the alphabet is finite, and the width has to be given in advance, since those strictly local at some width are not identifiable. Contrary to the paper, the elementwise intersections of two lattice classes need not be identifiable; they form a lattice class when no node has an infinite ascending chain below it.

Implementation notes

The paper requires f and ⊔ to be computable and learners to be computable functions; here they are arbitrary, so the results are those of ineffective identification. A learner conjectures a language rather than an index, so the paper's condition that the indexing be one-to-one disappears. A lattice space has a least element: the paper's learner needs one on the empty sample, and its Theorem 4.7(iii) asks for a least language containing the empty set. The words form an arbitrary type W, of which the paper's Σ* is an instance.

TODO

The pattern languages, monomials and function-distinguishable classes of §5, the query complexity of §6 and the VC-dimension characterization of §7 are not formalized.

References

Lattice spaces and the lattice learner

L75–76
L87
L90
L106–107

Examples 2.4 and 2.8, and Table 1

L133–136
L138–141
L153–159

Properties of learners (Definition 2.7)

L209–217
L223

Lattice classes

L235–238

A class of languages is a lattice class exactly when each finite set of words has a least language containing it and each language is the least language containing some finite set (Theorem 4.7(iii), corrected).

theorem isLatticeClass_iffL244–290
{W : Type u} {𝓛 : Set (Set W)} :
IsLatticeClass 𝓛 ↔ (∀ (D : Finset W), ∃ (M : Set W), IsLeast {L : Set W | L ∈ 𝓛 ∧ ↑D ⊆ L} M) ∧ ∀ L ∈ 𝓛, ∃ (D : Finset W), IsLeast {L' : Set W | L' ∈ 𝓛 ∧ ↑D ⊆ L'} L

Built from

The conditions of Theorem 4.7

L360–364
L379–383

Finite joins and the chain condition

L395–411
L414–424

Products of lattice spaces (§3)

L435–436

Under the chain condition the elementwise intersections of two classes form a lattice class.

theorem isLatticeClass_interL438–460
{W : Type u} {V₁ : Type u_1} {V₂ : Type u_2} [SemilatticeSup V₁] [OrderBot V₁] [SemilatticeSup V₂] [OrderBot V₂] [∀ (v : V₁), WellFoundedGT ↑(Set.Iic v)] [∀ (v : V₂), WellFoundedGT ↑(Set.Iic v)] (f₁ : W → V₁) (f₂ : W → V₂) :
IsLatticeClass {L : Set W | ∃ (a : V₁) (b : V₂), L = language f₁ a ∩ language f₂ b}

Built from ,

L462–467

Lattice classes are not closed under elementwise intersection: both classes here are lattice classes, yet their intersections contain the numbers and all their finite subsets. The word none is what made the finite sets and all words learnable, and intersection discards it.

theorem not_identifiable_interL503–518
:
¬InductiveInference.Identifiable {L : Set (Option ℕ) | ∃ (a : WithTop (Finset ℕ)) (b : Bool), L = language counterexample₁ a ∩ language counterexample₂ b}

Built from , ,

V_kSP is not a lattice

Grammars as sets of features

A word is mapped to a finite set of features and a grammar permits a set of them, the shape of all the paper's subregular examples. With finite grammars this is a lattice class, and with arbitrary grammars it is learnable exactly when finitely many features occur at all.

L571–579
L581–595
L598–614

Subregular languages (§3)