Training in structural pattern recognition. (Russian) Zbl 0635.68098

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


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