Английская Википедия:Growth function

The growth function, also called the shatter coefficient or the shattering number, measures the richness of a set family or class of function. It is especially used in the context of statistical learning theory, where it is used to study properties of statistical learning methods. The term 'growth function' was coined by Vapnik and Chervonenkis in their 1968 paper, where they also proved many of its properties.^[1] It is a basic concept in machine learning.^[2] ^[3]

Definitions

Set-family definition

Let <math>H</math> be a set family (a set of sets) and <math>C</math> a set. Their intersection is defined as the following set-family:

H\cap C := \{h\cap C\mid h\in H\} </math>

The intersection-size (also called the index) of <math>H</math> with respect to <math>C</math> is <math>|H\cap C|</math>. If a set <math>C_m</math> has <math>m</math> elements then the index is at most <math>2^m</math>. If the index is exactly 2^m then the set <math>C</math> is said to be shattered by <math>H</math>, because <math mode=display> H\cap C</math> contains all the subsets of <math mode>C</math>, i.e.:

|H\cap C|=2^{|C|}, </math>

The growth function measures the size of <math>H\cap C</math> as a function of <math>|C|</math>. Formally:

\operatorname{Growth}(H,m) := \max_{C: |C|=m} |H\cap C| </math>

Hypothesis-class definition

Equivalently, let <math>H</math> be a hypothesis-class (a set of binary functions) and <math>C</math> a set with <math>m</math> elements. The restriction of <math>H</math> to <math>C</math> is the set of binary functions on <math>C</math> that can be derived from <math>H</math>:^[3]Шаблон:Rp

H_{C} := \{(h(x_1),\ldots,h(x_m))\mid h\in H, x_i\in C\} </math> The growth function measures the size of <math>H_C</math> as a function of <math>|C|</math>:^[3]Шаблон:Rp

\operatorname{Growth}(H,m) := \max_{C: |C|=m} |H_C| </math>

Examples

1. The domain is the real line <math>\mathbb{R}</math>. The set-family <math>H</math> contains all the half-lines (rays) from a given number to positive infinity, i.e., all sets of the form <math>\{x > x_0 \mid x\in \mathbb{R}\}</math> for some <math>x_0\in \mathbb{R}</math>. For any set <math>C</math> of <math>m</math> real numbers, the intersection <math>H\cap C</math> contains <math>m+1</math> sets: the empty set, the set containing the largest element of <math>C</math>, the set containing the two largest elements of <math>C</math>, and so on. Therefore: <math>\operatorname{Growth}(H,m)=m+1</math>.^[1]Шаблон:Rp The same is true whether <math>H</math> contains open half-lines, closed half-lines, or both.

2. The domain is the segment <math>[0,1]</math>. The set-family <math>H</math> contains all the open sets. For any finite set <math>C</math> of <math>m</math> real numbers, the intersection <math>H\cap C</math> contains all possible subsets of <math>C</math>. There are <math>2^m</math> such subsets, so <math>\operatorname{Growth}(H,m)=2^m</math>. ^[1]Шаблон:Rp

3. The domain is the Euclidean space <math>\mathbb{R}^n</math>. The set-family <math>H</math> contains all the half-spaces of the form: <math>x\cdot \phi \geq 1</math>, where <math>\phi</math> is a fixed vector. Then <math>\operatorname{Growth}(H,m)=\operatorname{Comp}(n,m)</math>, where Comp is the number of components in a partitioning of an n-dimensional space by m hyperplanes.^[1]Шаблон:Rp

4. The domain is the real line <math>\mathbb{R}</math>. The set-family <math>H</math> contains all the real intervals, i.e., all sets of the form <math>\{x \in [x_0,x_1] | x\in \mathbb{R}\}</math> for some <math>x_0,x_1\in \mathbb{R}</math>. For any set <math>C</math> of <math>m</math> real numbers, the intersection <math>H\cap C</math> contains all runs of between 0 and <math>m</math> consecutive elements of <math>C</math>. The number of such runs is <math>{m+1 \choose 2}+1</math>, so <math>\operatorname{Growth}(H,m)={m+1 \choose 2}+1</math>.

Polynomial or exponential

The main property that makes the growth function interesting is that it can be either polynomial or exponential - nothing in-between.

The following is a property of the intersection-size:^[1]Шаблон:Rp

If, for some set <math>C_m</math> of size <math>m</math>, and for some number <math>n\leq m</math>, <math>|H\cap C_m| \geq \operatorname{Comp}(n,m)</math> -
then, there exists a subset <math>C_n\subseteq C_m</math> of size <math>n</math> such that <math>|H\cap C_n| = 2^n</math>.

This implies the following property of the Growth function.^[1]Шаблон:Rp For every family <math>H</math> there are two cases:

The exponential case: <math>\operatorname{Growth}(H,m) = 2^m</math> identically.
The polynomial case: <math>\operatorname{Growth}(H,m)</math> is majorized by <math>\operatorname{Comp}(n,m) \leq m^n+1</math>, where <math>n</math> is the smallest integer for which <math>\operatorname{Growth}(H,n) < 2^n</math>.

Other properties

Trivial upper bound

For any finite <math>H</math>:

<math>\operatorname{Growth}(H,m) \leq |H|</math>

since for every <math>C</math>, the number of elements in <math>H\cap C</math> is at most <math>|H|</math>. Therefore, the growth function is mainly interesting when <math>H</math> is infinite.

Exponential upper bound

For any nonempty <math>H</math>:

<math>\operatorname{Growth}(H,m) \leq 2^m</math>

I.e, the growth function has an exponential upper-bound.

We say that a set-family <math>H</math> shatters a set <math>C</math> if their intersection contains all possible subsets of <math>C</math>, i.e. <math>H\cap C = 2^C</math>. If <math>H</math> shatters <math>C</math> of size <math>m</math>, then <math>\operatorname{Growth}(H,C)=2^{m}</math>, which is the upper bound.

Cartesian intersection

Define the Cartesian intersection of two set-families as:

<math>H_1\bigotimes H_2 := \{h_1\cap h_2 \mid h_1\in H_1, h_2\in H_2\}</math>.

Then:^[2]Шаблон:Rp

<math>\operatorname{Growth}(H_1\bigotimes H_2, m) \leq \operatorname{Growth}(H_1, m)\cdot \operatorname{Growth}(H_2, m)</math>

Union

For every two set-families:^[2]Шаблон:Rp

<math>\operatorname{Growth}(H_1\cup H_2, m) \leq \operatorname{Growth}(H_1, m) + \operatorname{Growth}(H_2, m)</math>

VC dimension

The VC dimension of <math>H</math> is defined according to these two cases:

In the polynomial case, <math>\operatorname{VCDim}(H) = n-1</math> = the largest integer <math>d</math> for which <math>\operatorname{Growth}(H,d) = 2^d</math>.
In the exponential case <math>\operatorname{VCDim}(H) = \infty</math>.

So <math>\operatorname{VCDim}(H)\geq d</math> if-and-only-if <math>\operatorname{Growth}(H,d)=2^d</math>.

The growth function can be regarded as a refinement of the concept of VC dimension. The VC dimension only tells us whether <math>\operatorname{Growth}(H,d)</math> is equal to or smaller than <math>2^d</math>, while the growth function tells us exactly how <math>\operatorname{Growth}(H,m)</math> changes as a function of <math>m</math>.

Another connection between the growth function and the VC dimension is given by the Sauer–Shelah lemma:^[3]Шаблон:Rp

If <math>\operatorname{VCDim}(H)=d</math>, then:

for all <math>m</math>: <math>\operatorname{Growth}(H,m)\leq \sum_{i=0}^{d} {m\choose i}</math>

In particular,

for all <math>m>d+1</math>: <math>\operatorname{Growth}(H,m)\leq (em/d)^d = O(m^d)</math>

so when the VC dimension is finite, the growth function grows polynomially with <math>m</math>.

This upper bound is tight, i.e., for all <math>m>d</math> there exists <math>H</math> with VC dimension <math>d</math> such that:^[2]Шаблон:Rp

<math>\operatorname{Growth}(H,m)= \sum_{i=0}^{d} {m\choose i}</math>

Entropy

While the growth-function is related to the maximum intersection-size, the entropy is related to the average intersection size:^[1]Шаблон:Rp

<math>\operatorname{Entropy}(H, m) = E_{|C_m|=m}\big[\log_2(|H\cap C_m|)\big]</math>

The intersection-size has the following property. For every set-family <math>H</math>:

<math>

<math>

\operatorname{Entropy}(H, m_1+m_2) \leq \operatorname{Entropy}(H, m_1) + \operatorname{Entropy}(H, m_2) </math> Moreover, the sequence <math>\operatorname{Entropy}(H, m)/m</math> converges to a constant <math>c\in [0,1]</math> when <math>m\to\infty</math>.

Moreover, the random-variable <math>\log_2{|H\cap C_m|/m}</math> is concentrated near <math>c</math>.

Applications in probability theory

Let <math>\Omega</math> be a set on which a probability measure <math>\Pr</math> is defined. Let <math>H</math> be family of subsets of <math>\Omega</math> (= a family of events).

Suppose we choose a set <math>C_m</math> that contains <math>m</math> elements of <math>\Omega</math>, where each element is chosen at random according to the probability measure <math>P</math>, independently of the others (i.e., with replacements). For each event <math>h\in H</math>, we compare the following two quantities:

Its relative frequency in <math>C_m</math>, i.e., <math>|h\cap C_m|/m</math>;
Its probability <math>\Pr[h]</math>.

We are interested in the difference, <math>D(h,C_m) := \big||h\cap C_m|/m - \Pr[h]\big|</math>. This difference satisfies the following upper bound:

\Pr\left[\forall h\in H: D(h,C_m) \leq \sqrt{8(\ln\operatorname{Growth}(H, 2m) + \ln(4/\delta)) \over m} \right] EducationBot (обсуждение) 06:43, 17 марта 2024 (+04) > EducationBot (обсуждение) 06:43, 17 марта 2024 (+04) 1 - \delta </math> which is equivalent to:^[1]Шаблон:Rp

\Pr\big[\forall h\in H: D(h,C_m) \leq \varepsilon\big] EducationBot (обсуждение) 06:43, 17 марта 2024 (+04) > EducationBot (обсуждение) 06:43, 17 марта 2024 (+04) 1 - 4\cdot \operatorname{Growth}(H, 2m)\cdot \exp(-\varepsilon^2\cdot m/8) </math> In words: the probability that for all events in <math>H</math>, the relative-frequency is near the probability, is lower-bounded by an expression that depends on the growth-function of <math>H</math>.

A corollary of this is that, if the growth function is polynomial in <math>m</math> (i.e., there exists some <math>n</math> such that <math>\operatorname{Growth}(H,m)\leq m^n+1</math>), then the above probability approaches 1 as <math>m\to\infty</math>. I.e, the family <math>H</math> enjoys uniform convergence in probability.

References

Шаблон:Reflist

↑ ^1,0 ^1,1 ^1,2 ^1,3 ^1,4 ^1,5 ^1,6 ^1,7 Шаблон:Cite Vapnik Chervonenkis
↑ ^2,0 ^2,1 ^2,2 ^2,3 Шаблон:Cite Mehryar Afshin Ameet 2012, especially Section 3.2
↑ ^3,0 ^3,1 ^3,2 ^3,3 Шаблон:Cite Shai Shai 2014

[vc-1] 1,0 ^1,1 ^1,2 ^1,3 ^1,4 ^1,5 ^1,6 ^1,7 Шаблон:Cite Vapnik Chervonenkis

[book12-2] 2,0 ^2,1 ^2,2 ^2,3 Шаблон:Cite Mehryar Afshin Ameet 2012, especially Section 3.2

[book14-3] 3,0 ^3,1 ^3,2 ^3,3 Шаблон:Cite Shai Shai 2014

[1]

[2]

[3]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.