In modern computer science and statistics, the complexity index of a function denotes the level of informational content, which in turn affects the difficulty of learning the function from examples. This is different from computational complexity, which is the difficulty to compute a function. Complexity indices characterize the entire class of functions to which the one we are interested in belongs. Focusing on Boolean functions, the detail of a class of Boolean functions c essentially denotes how deeply the class is articulated.

Technical definition

edit

To identify this index we must first define a sentry function of  . Let us focus for a moment on a single function c, call it a concept defined on a set   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  . 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   to each concept of   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   including c has at least one of the sentry points of c either in the gap between c and  , or outside   and distinct from the sentry points of  , 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   made up of c plus its sentry points by another   in the same class.

Definition of sentry function

edit

For a concept class   on a space  , a sentry function is a total function   satisfying the following conditions:

  1. Sentinels are outside the sentineled concept (  for all  ).
  2. Sentinels are inside the invading concept (Having introduced the sets  , an invading concept   is such that   and  . Denoting   the set of concepts invading c, we must have that if  , then  ).
  3.   is a minimal set with the above properties (No   exists satisfying (1) and (2) and having the property that   for every  ).
  4. Sentinels are honest guardians. It may be that   but   so that  . This however must be a consequence of the fact that all points of   are involved in really sentineling c against other concepts in   and not just in avoiding inclusion of   by  . Thus if we remove   remains unchanged (Whenever   and   are such that   and  , then the restriction of   to   is a sentry function on this set).

  is the frontier of c upon  .

 
A schematic outlook of outer sentineling functionality

With reference to the picture on the right,   is a candidate frontier of   against  . All points are in the gap between a   and  . They avoid inclusion of   in  , provided that these points are not used by the latter for sentineling itself against other concepts. Vice versa we expect that   uses   and   as its own sentinels,   uses   and   and   uses   and   analogously. Point   is not allowed as a   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  .

Definition of detail

edit

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

 ,

is called detail of  .   spans also over sentry functions on subsets of   sentineling in this case the intersections of the concepts with these subsets. Actually, proper subsets of   may host sentineling tasks that prove harder than those emerging with   itself.

The detail   is a complexity measure of concept classes dual to the VC dimension  . 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)

 

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

Example: continuous spaces

edit

Class C of circles in   has detail  , as shown in the picture on left below. Similarly, for the class of segments on  , as shown in the picture on right.

 
Two points   outside c (thick circle) are sufficient to prevent a larger circle not containing them from including it
 
The class of segments in   and two points needed to sentinel its concepts

Example: discrete spaces

edit

The class   on   whose concepts are illustrated in the following scheme, where "+" denotes an element   belonging to  , "-" an element outside  , and ⃝ a sentry point:

     
  -⃝ -⃝ -
  -⃝ + +
  + -⃝ +
  + + +

This class has  . As usual we may have different sentineling functions. A worst case S, as illustrated, is:  . However a cheaper one is  :

     
  - - -⃝
  -⃝ + +
  + -⃝ +
  + + +

References

edit
  • 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.