• Images
• Videos
• Documents
• Books
• Articles

Technical definition

To identify this index we must first define a sentry function of C {\displaystyle {\mathsf {C}}} . Let us focus for a moment on a single function c, call it a concept defined on a set X {\displaystyle {\mathcal {X}}} of elements that we may figure as points in a Euclidean space. In this framework, the above function associates to c 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 c from being fully enclosed (invaded) by another concept within the class. Therefore, we call these points either sentinels or sentry points; they are assigned by the sentry function S {\displaystyle {\boldsymbol {S}}} to each concept of C {\displaystyle {\mathsf {C}}} in such a way that:

1. the sentry points are external to the concept c to be sentineled and internal to at least one other including it,
2. each concept c ′ {\displaystyle c'} including c has at least one of the sentry points of c either in the gap between c and c ′ {\displaystyle c'} , or outside c ′ {\displaystyle c'} and distinct from the sentry points of c ′ {\displaystyle c'} , and
3. they constitute a minimal set with these properties.

The technical definition coming from (Apolloni 2006) is rooted in the inclusion of an augmented concept c + {\displaystyle c^{+}} made up of c plus its sentry points by another ( c ′ ) + {\displaystyle \left(c'\right)^{+}} in the same class.

Definition of sentry function

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

1. 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}}} ).
2. 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 c, 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 } ).
3. 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}}} ).
4. 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 c 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).

S ( c ) {\displaystyle {\boldsymbol {S}}(c)} is the frontier of c upon S {\displaystyle {\boldsymbol {S}}} .

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. Vice versa 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}} .

Definition of detail

The frontier size of the most expensive concept to be sentineled with the least efficient sentineling function, i.e. the quantity

D C = sup S , c # S ( c ) {\displaystyle \mathrm {D} _{\mathsf {C}}=\sup _{{\boldsymbol {S}},c}\#{\boldsymbol {S}}(c)} ,

is called detail 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.

The detail D C {\displaystyle \mathrm {D} _{\mathsf {C}}} is a complexity measure of concept classes dual to the VC dimension 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)

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

See also Rademacher complexity for a recently introduced class complexity index.

Example: continuous spaces

Class C 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.

Example: discrete spaces

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:

	x 1 {\displaystyle x_{1}}	x 2 {\displaystyle x_{2}}	x 3 {\displaystyle x_{3}}
c 1 = {\displaystyle c_{1}=}	-⃝	-⃝	-
c 2 = {\displaystyle c_{2}=}	-⃝	+	+
c 3 = {\displaystyle c_{3}=}	+	-⃝	+
c 4 = {\displaystyle c_{4}=}	+	+	+

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 } :

	x 1 {\displaystyle x_{1}}	x 2 {\displaystyle x_{2}}	x 3 {\displaystyle x_{3}}
c 1 = {\displaystyle c_{1}=}	-	-	-⃝
c 2 = {\displaystyle c_{2}=}	-⃝	+	+
c 3 = {\displaystyle c_{3}=}	+	-⃝	+
c 4 = {\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.