Graphs for Pattern Recognition

Damir Gainanov

• Éditeur: De Gruyter
• Année: 2016
• ISBN:
  9783110480306
• Édition: 1
• Sujet: Mathematics
• Sous-sujet: Counting & Numeration

This monograph deals with mathematical constructions that are foundational in such an important area of data mining as pattern recognition. By using combinatorial and graph theoretic techniques, a closer look is taken at infeasible systems of linear inequalities, whose generalized solutions act as building blocks of geometric decision rules for pattern recognition.
Infeasible systems of linear inequalities prove to be a key object in pattern recognition problems described in geometric terms thanks to the committee method. Such infeasible systems of inequalities represent an important special subclass of infeasible systems of constraints with a monotonicity property – systems whose multi-indices of feasible subsystems form abstract simplicial complexes (independence systems), which are fundamental objects of combinatorial topology.
The methods of data mining and machine learning discussed in this monograph form the foundation of technologies like big data and deep learning, which play a growing role in many areas of human-technology interaction and help to find solutions, better solutions and excellent solutions.

Contents:
Preface
Pattern recognition, infeasible systems of linear inequalities, and graphs
Infeasible monotone systems of constraints
Complexes, (hyper)graphs, and inequality systems
Polytopes, positive bases, and inequality systems
Monotone Boolean functions, complexes, graphs, and inequality systems
Inequality systems, committees, (hyper)graphs, and alternative covers
Bibliography
List of notation
Index

1Infeasible monotone systems of constraints

In discrete mathematics, the following research subjects are of prime importance: Let

:= {s1, s2, . . . , sm} be a finite nonempty system of constraints and [m] := {1,2, . . . , m} the set of the indices of constraints with which the elements of the set S are marked. Assigning to the set [m] the Boolean lattice B(m) of all its subsets partially ordered by set-theoretical inclusion, we call an arbitrary element B ∈ B(m) the multiindex of the subsystem {si : i ∈ B} of the system

; in many studies the shorter term index of a subsystem is used. To the relation A ⊆ B of inclusion for the multi-indices A, B ⊆ [m] corresponds the comparison relation A ⪯ B for the elements A and B in the lattice B(m). The set of atoms B(m)(1) := {{1}, {2}, . . . , {m}} of the lattice B(m) is in one-to-one correspondence with the set of constraints

. The least element ô̂ of the lattice B(m) is the multi-index of the empty subsystem 0 of the system

, and the greatest element î̂ of the lattice B(m) is the multi-index [m] of the entire system

.

Let a map π : B(m) → 2Γ into the family of subsets of some nonempty set Γ be given, with the following properties:

–The empty subsystem of the system S is feasible, that is,

one usually supposes π(ô̂) := Γ.

–Each constraint taken independently is realizable or, in other words, each subsystem consisting of one constraint is feasible:

–Further,

and thus

A, B ∈ 𝔹(m) ⇒π(A) ∩ π(B) ⊇ π(A ∨ B) ,

where A∨B denotes the least upper bound (i.e., the set-union A∪B) of the elements A and B in the lattice 𝔹(m).

–One often considers infeasible systems S such that

We will call any system of constraints

, for which the map π and the range family of this map associated with S satisfy conditions (1.1)–(1.4), a finite infeasible monotone system of constraints.

1.1Structural and combinatorial properties of infeasible monotone systems of constraints

In this chapter, we particularly describe some properties of constraint systems, which are essentially associated with the representativity of sets.

Speaking briefly, the mutual representativity of sets A and B of any kind is related to the answer to the question on the nonemptiness of their intersection A ∩ B.

The subject of this chapter goes back to the standard problem of combinatorial optimization: for a nonempty family A := {A1, . . . , Aα} of nonempty and pairwise distinct subsets of a finite ground set

to describe, from the structural and combinatorial point...