복잡도 지수

이 글에는 여러 가지 문제가 있다.이 문제를 개선하거나 대화 페이지에서 토의하십시오.(이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글은 독자들에게 혼란스럽거나 불명확할 수 있다. 기사에 대해 명확하게 설명할 수 있도록 도와주십시오. 토크 페이지에서 이에 대한 논의가 있을 수 있다.(2022년 1월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) 이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 삭제하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2022년 1월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

현대 컴퓨터 과학과 통계에서 기능의 복잡성 지수는 정보 콘텐츠의 수준을 나타내며, 이는 다시 예로부터 기능을 배우는 어려움에 영향을 미친다.이것은 함수를 계산하기 어려운 계산 복잡성과는 다르다.복잡도 지수는 우리가 관심 있는 것이 속하는 전체 종류의 함수를 특징으로 한다.부울 함수에 초점을 맞추어, 부울$함수$의 $클래스$ C {\displaystyle {\$mathsf{C}}$의 세부사항은 클래스가 얼마나 깊게 표현되는지를 본질적으로 나타낸다.

기술 정의

이 지수를 식별하려면 먼저 $C{\displaystyle \mathsf{}}$ ${\$의 Sentry 함수를 정의해야 한다$.$ 단일한 함수 c에 잠시 초점을 맞추자, 유클리드 공간에서 점으로 파악할 수 있는 원소의$$ $집합{\displaystyle \mathcal{}}$ X ${\${\$mathcal{X}$에 정의된 개념이라고 한다.이 프레임워크에서, 위의 함수는 개념의 외부에 있는 것으로 정의되었기 때문에 $C$의 다른 함수로 확장되는 것을 방지하는 c 지점 집합과 연관된다$.$ 우리는 주어진 개념 c가 다른 콘에 의해 완전히 밀폐되지 않도록($내장됨)$를 전송하는 관점에서 이러한 점을 한 번에 정의할 수 있다.반에서 합석하다따라서 우리는 이러한 점을 보초 또는 보초지점이라고 부른다. 이러한 $점들$은 다음과 같은 방식으로$$ C ${\$$boldsymbol {S}$의 각 개념에$$ 보초함수 $S{\displaystyle \mathit{}}$ {\$displaystyle$ {\mathsf ${C}$에 의해 할당된다.

1. 보초 지점은 c라는 개념의 외부에 있고, 그것을 포함한 적어도 하나의 다른 개념의 내부에 있다.
2. c를 포함한$$ 각 개념 $c{\displaystyle {}^{}}$′ ${\$ c$'}$은$($는) c와 $c{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ 사이의 간격 또는 $c{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ $c$$'}$ 밖에$$ c ${\displaystyle {\prime }^{}}$ ${\$ c$'}$의 sent points와 구별되는 c의 sent point 중 적어도 하나를 가지고 있다$.$
3. 그것들은 이 특성들로 최소 세트를 구성한다.

(Apoloni 2006) harv 오류에서 오는 기술적 정의: 대상 없음: CITREFAolloni2006(도움말)은 다른${\displaystyle {}^{}}$(${\displaystyle {{}^{}}^{}}$ ${\displaystyle {{\prime }^{}}^{}}$)${\displaystyle {}^{}}$+ ${\$$displaystyle c^{+})$에 의해 c와 그 보초지점으로 이루어진$$ 증강 개념 $c{\displaystyle {}^{}}$+ ${\$$displaystyle \left(c\right)$를 포함하는데 뿌리를 두고 있다.$^{+}}$ 같은 반에$$.

Sentry 기능의 정의

For a concept class ${\displaystyle {\mathsf {C}}}$ on a space ${\displaystyle {\mathfrak {X}}}$, a sentry function is a total function ${\displaystyle {\boldsymbol {S}}:{\mathsf {C}}\cup \{\emptyset ,{\mathfrak {X}}\}\mapsto 2^{\mathfrak {X}}}$ satisfying the following conditions:

1. Sentinels는 ${\displaystyle 모든\mathit{}}$ ${\displaystyle C\mathsf{}}$ ${\displaystyle \in }$C ${\displaystyle \mathrm{\{\backslash }}$$displaystyle$ c$\cap${\$boldsymbol$${S}($$c)=\$$emptyset$ $}$에 대한$$ Sentinels 개념 밖에 있다$.$
2. Sentinels are inside the invading concept (Having introduced the sets ${\displaystyle c^{+}=c\cup {\boldsymbol {S}}(c)}$, an invading concept ${\displaystyle c'\in {\mathsf {C}}}$ is such that ${\displaystyle c'\not \subseteq c}$ and ${\displaystyle c$$^{+}\vmeq \left(c'\오른쪽)$$^{+}}$.Denoting ${\displaystyle \mathrm {up} (c)}$ the set of concepts invading c, we must have that if ${\displaystyle c_{2}\in \mathrm {up} (c_{1})}$, then ${\displaystyle c_{2}\cap {\boldsymbol {S}}(c_{1})\neq \emptyset }$).
3. ${\displaystyle {\boldsymbol {S}}(c)}$ is a minimal set with the above properties (No ${\displaystyle {\boldsymbol {S}}'\neq {\boldsymbol {S}}}$ exists satisfying (1) and (2) and having the property that ${\displaystyle {\boldsymbol {S}}'(c)\subseteq {\boldsymbol {S}}(c)}$ for every $c{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle C\mathsf{}}$ ${\$
4. 보초병은 정직한 수호신이다.$c{\displaystyle }$ ${\displaystyle \subseteq {}^{}}$(${\displaystyle {{}^{}}^{}}$ ${\displaystyle {{\prime }^{}}^{}}$ ${\displaystyle {)}^{}}$+ ${\$일 수 있다.$^{+}}$ ${\displaystyle {}^{}}$ ${\displaystyle S}$( c${\displaystyle }$) ${\displaystyle {\cap }^{}}$ =$∅{\displaystyle{\boldsymbol{S}\c$)\$cap$c'=\$emptyeset }}$ $c$ u ${\displaystyle u\mathrm{}}$ ${\displaystyle \mathrm{p}}$ ${\displaystyle (c}$) ${\displaystystyle$ c$'\in \mathrmet$그러나 이는 $S{\displaystyle \mathit{}}$ ${\displaystyle (c}$ ${\displaystyle )}$ ${\displaystyle {\boldsymbol{S}(c)}$의 모든 지점이 ${\displaystyle \mathrm{u}}$ p${\displaystyle }$( ${\displaystyle c}$) ${\displaystyle \mathrm {up}($${\displaystyle {}^{}}$$)}$의 다른 개념에 대한 정말로 센티넬링 $c$에 관여하고 있다는$$$$ 사실의 결과일 뿐 아니라$,{\displaystyle }$ 단순히$$ $c{\displaystyle {}^{}}$+ ${\displaystyle {\{\backslash }^{}}$$display$${\displaystyle {}^{}}$c$^{{$$st$$.$$yle (c')^{+}}$.Thus if we remove ${\displaystyle c',{\boldsymbol {S}}(c)}$ remains unchanged (Whenever ${\displaystyle c_{1}}$ and ${\displaystyle c_{2}}$ are such that ${\displaystyle c_{1}\subset c_{2}\cup {\boldsymbol {S}}(c_{2})}$ and ${\displaystyle c_2\cap \mathit{S}(c_1)=}$${\displaystyle c_{2}\cap {\boldsymbol {S}}(c_{1})=\emptyset }$, then the restriction of ${\displaystyle {\boldsymbol {S}}}$ to ${\displaystyle \{c_{1}\}\cup \mathrm {up} (c_{1})-\{c_{2}\}}$ is a sentry function on this set).

${\displaystyle \mathit{S}}$(${\displaystyle c}$) ${\displaystyle {\boldsymbol {S}(c)}$은(는) $S{\displaystyle \mathit{}}$ ${\$에 대한 C의 프런티어 입니다$.$

With reference to the picture on the right, ${\displaystyle \{x_{1},x_{2},x_{3}\}}$ is a candidate frontier of ${\displaystyle c_{0}}$ against ${\displaystyle c_{1},c_{2},c_{3},c_{4}}$. All points are in the gap between a ${\displaystyle c_{$$i$$}$ 및 ${\displaystyle {c\mathrm{}}_{}}$ $0{\displaystyle {}_{}}$ ${\$그들은 이러한 $포인트$가 후자가 다른 개념에 대한 송신 자체에 사용되지 않는다면, c ${\displaystyle 3_{}}$에 c$$ $0{\displaystyle {}_{}{}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ 2,${\displaystyle {}_{}{x\mathrm{}}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\$$displaystyle c_$${0}\cup \{x_{1$},$x_$${2$},x_${$3$}\}}}}}$을(를$)$ 포함시키지 않는다$.$반대로 ${\displaystyle {우리}_{}}$는 c 1 ${\$$displaystyle$ $c_{1$}가$$ ${\displaystyle {x\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$ ${\$ ${\displaystyle {x\mathrm{}}_{}}$ $3{\displaystyle {}_{}}$ ${\$$displaystyle c_{3$$}$을 자체 센티넬로 사용하고$$$$, $c{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}, $x$ ${\$x_${$$3},$c_${4$}을$$${\displaystyle {}_{}}$ 사용한다고$$ 예상한다.${\displaystyle 1_{}}$ ${\$및$$ $x{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ 이와 유사하게$$.$point{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ 4$${\$displaystyle x_{4}$는 ${\displaystyle {c\mathrm{}}_{}}$ 0 ${\$ 보초지점으로$$ 허용되지$$ 않는다. 왜냐하면 다른 어떤 외교석과 마찬가지로 ${\displaystyle {c\mathrm{}}_{}}$ 0 ${\$의 침입 시 점유되지 않도록 다른 모든 개념 밖에 위치해야 하기 때문이다$.$

상세 정의

가장 효율이 낮은 송신 함수와 함께 가장 비싼 개념의 프런티어 크기(예: 수량

${\displaystyle {\mathrm{D}}_{}}$ ${\displaystyle {\mathsf{}}_{}}$= ${\displaystyle \underset{}{Supp\mathit{}}}$ ,${\displaystyle \underset{}{c}\mathrm{}}$# ${\displaystyle S}$ (${\displaystyle }$) ${\displaystyle \mathrm {D} _{\mathsf{C}=\supp_{\boldsymbol{S},c}\#{\boldsymbol {S}(c$

$또한{\displaystyle \mathfrak{}}$ 이 경우 X ${\$$mathsf{$$C$$\}\}.$ S ${\$$boldsymbol{S}}$의 하위 집합에 대한 보초 함수에 대한 세부사항으로 불리며, 이 하위 집합과 개념의 교차점을 전송한다$$.$실제로{\displaystyle \mathfrak{}}$ $X{\displaystyle \mathfrak{}}$ ${\$의 적절한 하위 집합은 X ${\$ 그 자체로$$ 나타나는 하위 집합보다 더 어려운 송신 작업을 호스팅할 수 있다$$.

상세 $D{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathsf{}}_{}}$ ${\$는 VC 차원 D ${\displaystyle V_{}}$ ${\displaystyle {\mathsf{}}_{}}$ ${\$ {D}$_{\mathsf {V}C}$에 해당하는 개념 클래스의 복잡도 측도로$,$ 전자는 포인트 세트를 구분하여 사용한다.특히 다음과 같은 불평등은 (아폴로니 1997) harv 에러를 억제한다: 목표가 없다: CITREFAolloni1997 (도움말)

${\displaystyle \mathrm {D} _{\mathsf {C}\leq \mathrm {D} _{\mathsf {V}C}+1}$

최근에 도입된 클래스 복잡성 지수는 Rademacher 복잡성을 참조하십시오.

예제: 연속 공백

$R{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {\mathrm{}}^{}}$ ${\$}:{2$}}:$ 원의 C급은 $아래{\displaystyle {\mathrm{}}_{}}$ 그림에서와 같이 D${\displaystyle {}_{\mathsf{}}}$ = ${\displaystyle 2}$ ${\displaystyle \mathrm {D} _{\mathsf{C}=2$ 상세도를 가지고$$ 있다.마찬가지로 $오른쪽{\displaystyle \mathbb{}}$ 그림에서와 같이 R ${\$ {$R}}$의 세그먼트 클래스에 대해서도 입니다$.$

두 점 $x{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\$${2$}} 외부 c(두꺼운 원)는 더 큰 원이 포함하지 않는 것을 방지하기에 충분하다.

$R{\displaystyle \mathbb{}}$ ${\$의 세그먼트 클래스 및$$ 개념을 전송하는 데 필요한 두 지점

예제: 이산형 공간

The class ${\displaystyle {\mathsf {C}}=\{c_{1},c_{2},c_{3},c_{4}\}}$ on ${\displaystyle {\mathfrak {X}}=\{x_{1},x_{2},x_{3}\}}$ whose concepts are illustrated in the following scheme, where "+" denotes an element ${\displaystyle x_{j}$$}}$ $c$ ${\displaystyle i_{}}$ ${\$ "- c i ${\$ 및 $and{\displaystyle {}_{}}$ sentry point:

	${\displaystyle x_{1}.$	${\displaystyle x_{2}}:$	${\displaystyle x_{3}}$
${\displaystyle c_{1}=}$	-⃝	-⃝	-
${\displaystyle c_{2}=}$	-⃝	+	+
${\displaystyle c_{3}=}$	+	-⃝	+
${\displaystyle c_{4}=}$	+	+	+

이 클래스는 $D{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathsf{}}_{}}$= ${\displaystyle 2}$ ${\displaystyle \mathrm {D} _{\mathsf{C}=2$ 평소와 같이 서로 다른 송신 기능을 가질 수 있다.A worst case S, as illustrated, is: ${\displaystyle \mathbf {S} (c_{1})=\{x_{1},x_{2}\},\mathbf {S} (c_{2})=\{x_{1}\},\mathbf {S} (c_{3})=\{x_{2}\},\mathbf {S} (c_{4})=\emptyset }$. However a cheaper one is ${\displaystyle \mathbf{S}(}$${\displaystyle \mathbf {S} (c_{1})=\{x_{3}\},\mathbf {S} (c_{2})=\{x_{1}\},\mathbf {S} (c_{3})=\{x_{2}\},\mathbf {S} (c_{4})=\emptyset }$:

	${\displaystyle x_{1}.$	${\displaystyle x_{2}}:$	${\displaystyle x_{3}}$
${\displaystyle c_{1}=}$	-	-	-⃝
${\displaystyle c_{2}=}$	-⃝	+	+
${\displaystyle c_{3}=}$	+	-⃝	+
${\displaystyle c_{4}=}$	+	+	+

참조

• Apolloni, B.; Malchiodi, D.; Gaito, S. (2006). Algorithmic Inference in Machine Learning. International Series on Advanced Intelligence. Vol. 5 (2nd ed.). Adelaide: Magill. Advanced Knowledge International
• Apolloni, B.; Chiaravalli, S. (1997). "PAC learning of concept classes through the boundaries of their items". Theoretical Computer Science. 172 (1–2): 91–120. doi:10.1016/S0304-3975(95)00240-5.