Documentation

Acmoi.dimVC

VC-dimensions of nondeterministic finite automata for words of equal length #

Part 1: Define VC dimension and VC index and prove
`dimVC = indexVC - 1` (even in the case of the empty family)
def shatters_some {V : Type u_1} [DecidableEq V] (𝓕 : Finset (Finset V)) (d : ℕ) :

To make this computable, restrict A ⊆ ⋃ 𝓕

Equations
Instances For
    def shatters_all {V : Type u_1} [DecidableEq V] (𝓕 : Finset (Finset V)) (d : ℕ) :

    Perhaps more natural to say: there is such a set, and 𝓕 shatters them all.

    Equations
    Instances For
      @[implicit_reducible]
      instance instDecidableEqFinsetInter_acmoi {V : Type u_1} [DecidableEq V] (A B C : Finset V) :
      Decidable (A ∩ C = B)
      Equations
      @[implicit_reducible]
      instance instDecidableEqFinset_acmoi {V : Type u_1} [DecidableEq V] (𝓕 𝓖 : Finset (Finset V)) :
      Decidable (𝓕 = 𝓖)
      Equations
      @[implicit_reducible]
      instance instDecidableExistsFinsetAndMemEqInter_acmoi {V : Type u_1} [DecidableEq V] (A B : Finset V) (𝓕 : Finset (Finset V)) :
      Decidable (∃ C ∈ 𝓕, A ∩ C = B)
      Equations
      @[implicit_reducible]
      instance instDecidableAndEqNatCardForallForallSubsetFinsetExistsMemInter_acmoi {V : Type u_1} [DecidableEq V] [Fintype V] (A : Finset V) (𝓕 : Finset (Finset V)) (d : ℕ) :
      Decidable (A.card = d ∧ ∀ B ⊆ A, ∃ C ∈ 𝓕, A ∩ C = B)
      Equations
      @[implicit_reducible]
      instance instDecidableShatters_some {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) (d : ℕ) :
      Equations
      @[implicit_reducible]
      instance instDecidableShatters_all {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) (d : ℕ) :
      Equations
      theorem nonempty_shatters {V : Type u_1} [DecidableEq V] (𝓕 : Finset (Finset V)) {A : Finset V} (hA : A ∈ 𝓕) :
      theorem shatters_some₀ {V : Type u_1} [DecidableEq V] [Fintype V] (F : Finset (Finset V)) :

      Shattering some set of size 0 or 1 is equivalent to having cardinality at least 2^0 or 2^1, respectively.

      theorem shatters_some₁ {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) :
      (∃ A ∈ 𝓕, ∃ B ∈ 𝓕, A ≠ B) ↔ shatters_some 𝓕 1

      Shattering some set of size 0 or 1 is equivalent to having cardinality at least 2^0 or 2^1, respectively.

      def dimVC {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) :

      The VC dimension of a finite set family.

      Equations
      Instances For
        theorem subset_of_size {α : Type u_1} {s : Finset α} (a b : ℕ) (h_card : s.card = b) (h_le : a ≤ b) :
        ∃ t ⊆ s, t.card = a

        Obtain a smaller subset of a given set.

        theorem shatters_all₀ {V : Type u_1} [DecidableEq V] [Fintype V] (F : Finset (Finset V)) :
        theorem shatters_monotone {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) (k l : ℕ) (h : k ≤ l) (h₀ : shatters_some 𝓕 l) :

        A family can also shatter a smaller set.

        theorem le_max'_iff (S : Finset ℕ) (h : S.Nonempty) (k : ℕ) :
        k ≤ S.max' h ↔ ∃ y ∈ S, k ≤ y
        theorem shattering_skolem {V : Type u_1} [DecidableEq V] [Fintype V] (F : Finset (Finset V)) (k : ℕ) (h : shatters_some F k) :
        ∃ (A : Finset V), A.card = k ∧ ∃ (φ : { B : Finset V // B ⊆ A } → ↥F), ∀ (B : { B : Finset V // B ⊆ A }), A ∩ ↑(φ B) = ↑B
        theorem VC_injective_function {V : Type u_1} [DecidableEq V] [Fintype V] (F : Finset (Finset V)) (A : Finset V) (φ : { B : Finset V // B ⊆ A } → ↥F) (h : ∀ (B : { B : Finset V // B ⊆ A }), A ∩ ↑(φ B) = ↑B) :
        theorem card_of_injective {V : Type u_1} [DecidableEq V] [Fintype V] (F : Finset (Finset V)) (A : Finset V) (φ : { B : Finset V // B ⊆ A } → ↥F) (h : Function.Injective φ) :

        Lean 3 version thanks to Adam Topaz.

        theorem pow_le_of_shatters {V : Type u_1} [DecidableEq V] [Fintype V] (F : Finset (Finset V)) (k : ℕ) (h : shatters_some F k) :
        2 ^ k ≤ F.card
        theorem pow_le_of_shatters₂ {V : Type u_1} [DecidableEq V] [Fintype V] (F : Finset (Finset V)) (k : ℕ) (h : shatters_some F k) :
        theorem pow_le (m : ℕ) :
        m < 2 ^ m
        theorem dimVC_def {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) (h𝓕 : ∃ (f : Finset V), f ∈ 𝓕) (k : ℕ) :
        k ≤ dimVC 𝓕 ↔ shatters_some 𝓕 k
        theorem pow_le_of_shatters₃! {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) (h𝓕 : ∃ (f : Finset V), f ∈ 𝓕) :
        dimVC 𝓕 ≤ Nat.log 2 𝓕.card

        The VC dimension is bounded by the logarithm of the cardinality. This is one of the bounds listed in Wikipedia.

        theorem not_shatter_ {V : Type u_1} [DecidableEq V] [Fintype V] {𝓕 : Finset (Finset V)} :
        {k ∈ Finset.range (𝓕.card + 1) | ¬shatters_some 𝓕 k}.Nonempty
        def indexVC {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) :

        The VC index is the VC dimension +1 for nonempty finite families, but can be defined for families of all cardinalities.

        Equations
        Instances For
          def indexVC_as_min' {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) :
          Equations
          Instances For
            theorem too_big_to_shatter {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) :
            theorem shatters_some_mono {k l : ℕ} (h₀ : k ≤ l) {V : Type u_1} [DecidableEq V] [Fintype V] {𝓕 : Finset (Finset V)} (h : shatters_some 𝓕 l) :
            theorem dimVC_emp {V : Type u_1} [DecidableEq V] [Fintype V] :
            theorem dim_index_VC {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) :
            dimVC 𝓕 = indexVC 𝓕 - 1

            Obtain dimVC from indexVC. Since dimVC ∅ = 0 and indexVC ∅ x= 0, this relies on 0 - 1 = 0.

            theorem VC_mono {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 𝓖 : Finset (Finset V)) (h : 𝓕 ⊆ 𝓖) :
            dimVC 𝓕 ≤ dimVC 𝓖
            theorem VC_trivBound {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) (h𝓕 : ∃ (f : Finset V), f ∈ 𝓕) :
            def indexTest {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) :

            Kathleen Romanik's testing dimension, index version.

            Equations
            Instances For
              def dimTest {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) :

              Kathleen Romanik's testing dimension, Source: Definition 2 of "VC-dimensions of nondeterministic finite automata for words of equal length".

              Equations
              Instances For
                theorem dimTest_le_dimVC {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) :
                dimTest 𝓕 ≤ dimVC 𝓕
                theorem shatters_all_mono {V : Type u_1} [DecidableEq V] [Fintype V] {𝓕 : Finset (Finset V)} {k l : ℕ} (h : shatters_all 𝓕 l) (h₀ : k ≤ l) (h₁ : l ≤ Finset.univ.card) :
                theorem please_nemp {V : Type u_1} [DecidableEq V] [Fintype V] {𝓕 : Finset (Finset V)} (G : ∃ (B : Finset V), B ∉ 𝓕) :
                theorem indexTest_le_indexVC {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) :
                theorem dim_index_test {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) :
                dimTest 𝓕 = indexTest 𝓕 - 1

                The VC dimension of the powerset is the cardinality of the underlying set. Note that this does not require [Nonempty V].

                theorem dimVC_eq {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) (h𝓕 : ∃ (f : Finset V), f ∈ 𝓕) (k : ℕ) :
                shatters_some 𝓕 k ∧ ¬shatters_some 𝓕 (k + 1) → dimVC 𝓕 = k
                theorem summarize {V : Type u_1} [DecidableEq V] [Fintype V] (𝓕 : Finset (Finset V)) :
                dimTest 𝓕 ≤ dimVC 𝓕 ∧ dimVC 𝓕 ≤ indexVC 𝓕 ∧ dimTest 𝓕 ≤ indexTest 𝓕 ∧ indexTest 𝓕 ≤ indexVC 𝓕

                A diamond:

                indexVC
                

                dimVC indexTest dimTest

                theorem counter₁ :
                ∃ (V : Type) (x : DecidableEq V) (x_1 : Fintype V) (𝓕 : Finset (Finset V)), dimVC 𝓕 < indexTest 𝓕
                theorem counter₂ :
                ∃ (V : Type) (x : DecidableEq V) (x_1 : Fintype V) (𝓕 : Finset (Finset V)), dimVC 𝓕 > indexTest 𝓕