Complexity index

Complexity index

Besides complexity intended as a difficulty to compute a function (see computational complexity), in modern computer science and in statistics another complexity index of a function stands for denoting its information content, in turn affecting the difficulty of learning the function from examples. Complexity indices in this sense characterize the entire class of functions to which the one we are interested in belongs. Focusing on Boolean functions, the detail of a class \mathsf C of Boolean functions c essentially denotes how deeply the class is articulated.

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

Contents

Definition of sentry function

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

  1. Sentinels are outside the sentineled concept (c\cap{\boldsymbol S}(c)=\emptyset for all c\in \mathsf C).
  2. Sentinels are inside the invading concept (Having introduced the sets c^+=c\cup\boldsymbol S(c), an invading concept c'\in \mathsf C is such that c'\not\subseteq c and c^+\subseteq \left(c'\right)^+. Denoting up(c) the set of concepts invading c, we must have that if c_2\in\mathrm{up}(c_1), then c_2\cap{\boldsymbol S}(c_1)\neq\emptyset).
  3. {\boldsymbol S}(c) is a minimal set with the above properties (No {\boldsymbol S}'\neq{\boldsymbol S} exists satisfying (1) and (2) and having the property that \boldsymbol S'(c)\subseteq \boldsymbol S(c) for every c\in \mathsf C).
  4. Sentinels are honest guardians. It may be that c\subseteq \left(c'\right)^+ but {\boldsymbol S} (c)\cap c'=\emptyset so that c'\not\in\mathrm{up}(c). This however must be a consequence of the fact that all points of {\boldsymbol S}(c) are involved in really sentineling c against other concepts in up(c) and not just in avoiding inclusion of c + by (c') + . Thus if we remove c', {\boldsymbol S}(c) remains unchanged (Whenever c1 and c2 are such that c_1\subset c_2\cup{\boldsymbol S}(c_2) and c_2\cap{\boldsymbol S}(c_1)=\emptyset, then the restriction of {\boldsymbol S} to \{c_1\}\cup\mathrm{up}(c_1)-\{c_2\} is a sentry function on this set).

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

A schematic outlook of outer sentineling functionality

With reference to the picture on the right, {x1,x2,x3} is a candidate frontier of c0 against c1,c2,c3,c4. All points are in the gap between a ci and c0. They avoid inclusion of c_0\cup\{x_1,x_2,x_3\} in c3, provided that these points are not used by the latter for sentineling itself against other concepts. Vice versa we expect that c1 uses x1 and x3 as its own sentinels, c2 uses x2 and x3 and c4 uses x1 and x2 analogously. Point x4 is not allowed as a c0 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 c0.

Definition of detail

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

\mathrm D_{\mathsf C}=\sup_{{\boldsymbol S},c}\#{\boldsymbol S}(c),

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

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

\mathrm D_{\mathsf C}\leq \mathrm D_{\mathsf VC}+1

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

Example: continuous spaces

Class C of circles in \mathbb R^2 has detail \mathrm D_{\mathsf C}=2, as shown in the picture on left below. Similarly, for the class of segments on \mathbb R, as shown in the picture on right.

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

Example: discrete spaces

The class \mathsf C=\{c_1,c_2,c_3,c_4\} on \mathfrak X=\{x_1,x_2,x_3\} whose concepts are illustrated in the following scheme, where “ + ” denotes an element xj belonging to ci, “ ” an element outside ci and \bigcirc a sentry point:

x1 x2 x3
c1 = \bigcirc\!\!\!\!\!- \bigcirc\!\!\!\!\!-
c2 = \bigcirc\!\!\!\!\!- + +
c3 = + \bigcirc\!\!\!\!\!- +
c4 = + + +

This class has \mathrm D_{\mathsf C}=2. As usual we may have different sentineling functions. A worst case \mathbf S, as illustrated, is: \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 \mathbf S(c_1)=\{x_3\}, \mathbf S(c_2)=\{x_1\}, \mathbf S(c_3)=\{x_2\}, \mathbf S(c_4)=\emptyset:

x1 x2 x3
c1 = \bigcirc\!\!\!\!\!-
c2 = \bigcirc\!\!\!\!\!- + +
c3 = + \bigcirc\!\!\!\!\!- +
c4 = + + +

References

  • Apolloni, B; Malchiodi, D., Gaito, S. (2006). Algorithmic Inference in Machine Learning. International Series on Advanced Intelligence. 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. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • complexity index — sudėtingumo rodiklis statusas T sritis radioelektronika atitikmenys: angl. complexity index vok. Komplexitätsindex, m rus. параметр сложности, m; показатель сложности, m pranc. index de complexité, m; indice de complexité, m …   Radioelektronikos terminų žodynas

  • Nelson complexity index — The Nelson complexity index was developed by Wilbur L. Nelson in a series of articles in Oil Gas Journal in 1960 61 (Mar. 14, p. 189; Sept. 26, p. 216; and June 19, p. 109). In 1976, he elaborated on the concept in another series… …   Wikipedia

  • complexity — index complication, confusion (turmoil), enigma, entanglement (confusion), imbroglio, impasse …   Law dictionary

  • index de complexité — sudėtingumo rodiklis statusas T sritis radioelektronika atitikmenys: angl. complexity index vok. Komplexitätsindex, m rus. параметр сложности, m; показатель сложности, m pranc. index de complexité, m; indice de complexité, m …   Radioelektronikos terminų žodynas

  • Complexity management — is a business methodology that deals with the analysis and optimization of complexity in enterprises. Effects of complexity pertain to all business processes along the value chain and hence complexity management requires a holistic approach.… …   Wikipedia

  • compLexity — coL Логотип организации Страна …   Википедия

  • Complexity (journal) —   Discipline Complex Systems …   Wikipedia

  • Complexity of constraint satisfaction — The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction… …   Wikipedia

  • Index (publishing) — For other uses of Index , see Index (disambiguation). An index (plural: indexes) is a list of words or phrases ( headings ) and associated pointers ( locators ) to where useful material relating to that heading can be found in a document. In a… …   Wikipedia

  • Index set — In mathematics, the elements of a set A may be indexed or labeled by means of a set J that is on that account called an index set. The indexing consists of a surjective function from J onto A and the indexed collection is typically called an… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”