Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Complexity index
open-in-new
<h2 id="technical-definition">Technical definition</h2> <p>To identify this index we must first define a <i>sentry function</i> of C {\displaystyle {\mathsf {C}}} . Let us focus for a moment on a single function <i>c</i>, call it a <i>concept</i> defined on a set X {\displaystyle {\mathcal {X}}} of elements that we may figure as points in a <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a>. In this framework, the above function associates to <i>c</i> a set of points that, since are defined to be external to the concept, prevent it from expanding into another function of C {\displaystyle {\mathsf {C}}} . We may dually define these points in terms of sentinelling a given concept <i>c</i> from being fully enclosed (invaded) by another concept within the class. Therefore, we call these points either <i>sentinels</i> or <i>sentry points</i>; they are assigned by the sentry function S {\displaystyle {\boldsymbol {S}}} to each concept of C {\displaystyle {\mathsf {C}}} in such a way that: </p> <ol><li>the sentry points are external to the concept <i>c</i> to be sentineled and internal to at least one other including it,</li> <li>each concept c ′ {\displaystyle c'} including <i>c</i> has at least one of the sentry points of <i>c</i> either in the gap between <i>c</i> and c ′ {\displaystyle c'} , or outside c ′ {\displaystyle c'} and distinct from the sentry points of c ′ {\displaystyle c'} , and</li> <li>they constitute a minimal set with these properties.</li></ol> <p>The technical definition coming from (Apolloni 2006) is rooted in the inclusion of an augmented concept c + {\displaystyle c^{+}} made up of <i>c</i> plus its sentry points by another ( c ′ ) + {\displaystyle \left(c'\right)^{+}} in the same class. </p> <h2 id="definition-of-sentry-function">Definition of sentry function</h2> <p>For a concept class C {\displaystyle {\mathsf {C}}} on a space X {\displaystyle {\mathfrak {X}}} , a <i>sentry function</i> is a <a href="/facts/Total_function/0vJMw0Nm">total function</a> S : C ∪ { ∅ , X } ↦ 2 X {\displaystyle {\boldsymbol {S}}:{\mathsf {C}}\cup \{\emptyset ,{\mathfrak {X}}\}\mapsto 2^{\mathfrak {X}}} satisfying the following conditions: </p> <ol><li>Sentinels are outside the sentineled concept ( c ∩ S ( c ) = ∅ {\displaystyle c\cap {\boldsymbol {S}}(c)=\emptyset } for all c ∈ C {\displaystyle c\in {\mathsf {C}}} ).</li> <li>Sentinels are inside the invading concept (Having introduced the sets c + = c ∪ S ( c ) {\displaystyle c^{+}=c\cup {\boldsymbol {S}}(c)} , an invading concept c ′ ∈ C {\displaystyle c'\in {\mathsf {C}}} is such that c ′ ⊈ c {\displaystyle c'\not \subseteq c} and c + ⊆ ( c ′ ) + {\displaystyle c^{+}\subseteq \left(c'\right)^{+}} . Denoting u p ( c ) {\displaystyle \mathrm {up} (c)} the set of concepts invading <i>c</i>, we must have that if c 2 ∈ u p ( c 1 ) {\displaystyle c_{2}\in \mathrm {up} (c_{1})} , then c 2 ∩ S ( c 1 ) ≠ ∅ {\displaystyle c_{2}\cap {\boldsymbol {S}}(c_{1})\neq \emptyset } ).</li> <li> S ( c ) {\displaystyle {\boldsymbol {S}}(c)} is a minimal set with the above properties (No S ′ ≠ S {\displaystyle {\boldsymbol {S}}'\neq {\boldsymbol {S}}} exists satisfying (1) and (2) and having the property that S ′ ( c ) ⊆ S ( c ) {\displaystyle {\boldsymbol {S}}'(c)\subseteq {\boldsymbol {S}}(c)} for every c ∈ C {\displaystyle c\in {\mathsf {C}}} ).</li> <li>Sentinels are honest guardians. It may be that c ⊆ ( c ′ ) + {\displaystyle c\subseteq \left(c'\right)^{+}} but S ( c ) ∩ c ′ = ∅ {\displaystyle {\boldsymbol {S}}(c)\cap c'=\emptyset } so that c ′ ∉ u p ( c ) {\displaystyle c'\not \in \mathrm {up} (c)} . This however must be a consequence of the fact that all points of S ( c ) {\displaystyle {\boldsymbol {S}}(c)} are involved in really sentineling <i>c</i> against other concepts in u p ( c ) {\displaystyle \mathrm {up} (c)} and not just in avoiding inclusion of c + {\displaystyle c^{+}} by ( c ′ ) + {\displaystyle (c')^{+}} . Thus if we remove c ′ , S ( c ) {\displaystyle c',{\boldsymbol {S}}(c)} remains unchanged (Whenever c 1 {\displaystyle c_{1}} and c 2 {\displaystyle c_{2}} are such that c 1 ⊂ c 2 ∪ S ( c 2 ) {\displaystyle c_{1}\subset c_{2}\cup {\boldsymbol {S}}(c_{2})} and c 2 ∩ S ( c 1 ) = ∅ {\displaystyle c_{2}\cap {\boldsymbol {S}}(c_{1})=\emptyset } , then the restriction of S {\displaystyle {\boldsymbol {S}}} to { c 1 } ∪ u p ( c 1 ) − { c 2 } {\displaystyle \{c_{1}\}\cup \mathrm {up} (c_{1})-\{c_{2}\}} is a sentry function on this set).</li></ol> <p> S ( c ) {\displaystyle {\boldsymbol {S}}(c)} is the <i>frontier</i> of <i>c</i> upon S {\displaystyle {\boldsymbol {S}}} . </p> <p>With reference to the picture on the right, { x 1 , x 2 , x 3 } {\displaystyle \{x_{1},x_{2},x_{3}\}} is a candidate frontier of c 0 {\displaystyle c_{0}} against c 1 , c 2 , c 3 , c 4 {\displaystyle c_{1},c_{2},c_{3},c_{4}} . All points are in the gap between a c i {\displaystyle c_{i}} and c 0 {\displaystyle c_{0}} . They avoid inclusion of c 0 ∪ { x 1 , x 2 , x 3 } {\displaystyle c_{0}\cup \{x_{1},x_{2},x_{3}\}} in c 3 {\displaystyle c_{3}} , provided that these points are not used by the latter for sentineling itself against other concepts. <i>Vice versa</i> we expect that c 1 {\displaystyle c_{1}} uses x 1 {\displaystyle x_{1}} and x 3 {\displaystyle x_{3}} as its own sentinels, c 2 {\displaystyle c_{2}} uses x 2 {\displaystyle x_{2}} and x 3 {\displaystyle x_{3}} and c 4 {\displaystyle c_{4}} uses x 1 {\displaystyle x_{1}} and x 2 {\displaystyle x_{2}} analogously. Point x 4 {\displaystyle x_{4}} is not allowed as a c 0 {\displaystyle c_{0}} sentry point since, like any diplomatic seat, it should be located outside all other concepts just to ensure that it is not occupied in case of invasion by c 0 {\displaystyle c_{0}} . </p> <h3>Definition of detail</h3> <p>The frontier size of the most expensive concept to be sentineled with the least efficient sentineling function, i.e. the quantity </p> D C = sup S , c # S ( c ) {\displaystyle \mathrm {D} _{\mathsf {C}}=\sup _{{\boldsymbol {S}},c}\#{\boldsymbol {S}}(c)} , <p>is called <i>detail</i> of C {\displaystyle {\mathsf {C}}} . S {\displaystyle {\boldsymbol {S}}} spans also over sentry functions on subsets of X {\displaystyle {\mathfrak {X}}} sentineling in this case the intersections of the concepts with these subsets. Actually, proper subsets of X {\displaystyle {\mathfrak {X}}} may host sentineling tasks that prove harder than those emerging with X {\displaystyle {\mathfrak {X}}} itself. </p><p>The detail D C {\displaystyle \mathrm {D} _{\mathsf {C}}} is a complexity measure of concept classes dual to the <a href="/facts/VC_dimension/ThkxKE12">VC dimension</a> D V C {\displaystyle \mathrm {D} _{{\mathsf {V}}C}} . The former uses points to separate sets of concepts, the latter concepts for partitioning sets of points. In particular the following inequality holds (Apolloni 1997) </p> D C ≤ D V C + 1 {\displaystyle \mathrm {D} _{\mathsf {C}}\leq \mathrm {D} _{{\mathsf {V}}C}+1} <p>See also <a href="/facts/Rademacher_complexity/YTmfuHw5">Rademacher complexity</a> for a recently introduced class complexity index. </p> <h3>Example: continuous spaces</h3> <p>Class <i>C</i> of circles in R 2 {\displaystyle \mathbb {R} ^{2}} has detail D C = 2 {\displaystyle \mathrm {D} _{\mathsf {C}}=2} , as shown in the picture on left below. Similarly, for the class of segments on R {\displaystyle \mathbb {R} } , as shown in the picture on right. </p> <table><tbody><tr><td></td><td></td></tr></tbody></table> <h3>Example: discrete spaces</h3> <p>The class C = { c 1 , c 2 , c 3 , c 4 } {\displaystyle {\mathsf {C}}=\{c_{1},c_{2},c_{3},c_{4}\}} on X = { x 1 , x 2 , x 3 } {\displaystyle {\mathfrak {X}}=\{x_{1},x_{2},x_{3}\}} whose concepts are illustrated in the following scheme, where "+" denotes an element x j {\displaystyle x_{j}} belonging to c i {\displaystyle c_{i}} , "-" an element outside c i {\displaystyle c_{i}} , and ⃝ a sentry point: </p> <table><tbody><tr><td></td><td> x 1 {\displaystyle x_{1}} </td><td> x 2 {\displaystyle x_{2}} </td><td> x 3 {\displaystyle x_{3}} </td></tr><tr><td> c 1 = {\displaystyle c_{1}=} </td><td>-⃝</td><td>-⃝</td><td>-</td></tr><tr><td> c 2 = {\displaystyle c_{2}=} </td><td>-⃝</td><td>+</td><td>+</td></tr><tr><td> c 3 = {\displaystyle c_{3}=} </td><td>+</td><td>-⃝</td><td>+</td></tr><tr><td> c 4 = {\displaystyle c_{4}=} </td><td>+</td><td>+</td><td>+</td></tr></tbody></table> <p>This class has D C = 2 {\displaystyle \mathrm {D} _{\mathsf {C}}=2} . As usual we may have different sentineling functions. A worst case S, as illustrated, is: S ( c 1 ) = { x 1 , x 2 } , S ( c 2 ) = { x 1 } , S ( c 3 ) = { x 2 } , S ( c 4 ) = ∅ {\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 S ( c 1 ) = { x 3 } , S ( c 2 ) = { x 1 } , S ( c 3 ) = { x 2 } , S ( c 4 ) = ∅ {\displaystyle \mathbf {S} (c_{1})=\{x_{3}\},\mathbf {S} (c_{2})=\{x_{1}\},\mathbf {S} (c_{3})=\{x_{2}\},\mathbf {S} (c_{4})=\emptyset } : </p> <table><tbody><tr><td></td><td> x 1 {\displaystyle x_{1}} </td><td> x 2 {\displaystyle x_{2}} </td><td> x 3 {\displaystyle x_{3}} </td></tr><tr><td> c 1 = {\displaystyle c_{1}=} </td><td>-</td><td>-</td><td>-⃝</td></tr><tr><td> c 2 = {\displaystyle c_{2}=} </td><td>-⃝</td><td>+</td><td>+</td></tr><tr><td> c 3 = {\displaystyle c_{3}=} </td><td>+</td><td>-⃝</td><td>+</td></tr><tr><td> c 4 = {\displaystyle c_{4}=} </td><td>+</td><td>+</td><td>+</td></tr></tbody></table> <ul><li>Apolloni, B.; Malchiodi, D.; Gaito, S. (2006). <i>Algorithmic Inference in Machine Learning</i>. International Series on Advanced Intelligence. Vol. 5 (2nd ed.). Adelaide: Magill. Advanced Knowledge International</li> <li>Apolloni, B.; Chiaravalli, S. (1997). <a href="https://doi.org/10.1016%2FS0304-3975%2895%2900240-5">"PAC learning of concept classes through the boundaries of their items"</a>. <i>Theoretical Computer Science</i>. 172 (1–2): 91–120. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0304-3975%2895%2900240-5">10.1016/S0304-3975(95)00240-5</a>.</li></ul>