Training in structural pattern recognition. (Russian) Zbl 0635.68098

Dzyuba, A. S.; Shishkin, V. A.

Zh. Vychisl. Mat. Mat. Fiz. 26, No. 11, 1695-1703 (1986).

The training problem on structural objects is investigated. An structural object is a complete oriented graph with labels on every node and arc. These labels are elements of some vector space of features. The case when the number of nodes n is fixed and the labels of arcs have only two values (0 or 1) is considered. Such structures may be defined by a matrix \(\tilde g=\| g_{ij}\|_{n\times n}\), where \(g_{ij}\in \{0,1\}\). The pattern is the set of objects generating a matrix grammar \(GR=(V_ N,V_ T,P,S)\), \(V_ N=\{S,B_{11},...,B_{nn}\}\), \(V_ T=\{0,1\}\), S the initial symbol, P the set of inference rules, including \[ S\to \left( \begin{matrix} B_{11},...,B_{1n}\\ B_{n1},...,B_{nn}\end{matrix} \right)\quad and\quad B_{ij}\to g_{ij}. \] This grammar is defined by some matrix \(\tilde w=\| w_{ij}\|_{n\times n}\), where \(w_{ij}=\{g_{ij}\in \{0,1\}:\) \(B_{ij}\to g_{ij}\}.\)
The training problem on objects and on objects with inserted and/or deleted arcs is formulated as the problem of inference of matrix grammar. The conditions of inferrability of such grammars are given. The complexity of training procedures is discussed.

Reviewer: N.Huhro

MSC:

68T10	Pattern recognition, speech recognition
68Q45	Formal languages and automata

Keywords:

inference problem; training problem; structural objects; matrix grammar