The method of fragmented standards. Linear decision rules

The method of fragmented standards

The learning process is as follows. At the first stage, in the training sample "cover" all objects of each class with a hypersphere of the smallest possible radius. You can do this, for example, so. The standard of each class is under construction. Calculates the distance from the standard to all objects of this class included in the training sample. The maximum of these distances is chosen. . A hypersphere is built with the center in the standard and the radius = + . It covers all objects of this class. This procedure is carried out for all classes (images). In fig. 3 shows an example of two images in a two-dimensional attribute space.

Fig. 3. Decisive rule of the type “The method of fragmented standards”

If the hyperspheres of different images intersect and in the overlap area there are objects of more than one image, then hyperspheres of the second level are built for them, then the third, etc. until the areas are non-intersecting, or objects of only one image are present in the intersection area.

Recognition is as follows. The location of the object relative to the first level hyperspheres is determined. When an object hits the hypersphere corresponding to one and only one image, the recognition procedure is terminated. If the object is in the overlap area of ​​the hyperspheres, which, when trained, contained objects of more than one image, then proceed to the second level hyperspheres and perform the same actions as for the first level hyperspheres. This process continues until the identity of an unknown object to a particular image is determined unequivocally. True, this event may not occur. In particular, an unknown object may not fall into any of the hypersphere of any level. In these cases, the “teacher” should include appropriate actions in the decision rules. For example, the system can either refuse to decide on an unambiguous assignment of an object to any image, or use the criterion of the minimum distance to the standards of a given or previous level, etc. Which of these techniques is more effective is difficult to say, because The method of fragmented standards is mainly empirical.

Linear decision rules

The name itself suggests that the border separating the region of different images in the attribute space is described by a linear function (Fig. 4)

= .

Fig. 4. Linear decision rule for recognition
two images

At the same time, one border divides the areas of two images. If a > 2, then several linear functions are required and the boundary is, generally speaking, piecewise linear. For clarity, we will assume = 2. If the set of objects satisfies the condition

,

if a - implementation of the first image ,

if a - implementation of the second image ,

then images and called linearly separable.

There are various methods for constructing linear decision rules. Consider one of them, implemented in the 50s by Rosenblat, in image recognition devices called perceptrons (Fig. 5).

Let be

Where - some object of one of the images, .

Fig. 5. Simplified scheme of a single-layer perceptron

Selection carried out step by step. present value replaced by new after the presentation of the next object of the training sample to the perceptron. This adjustment is made according to the following rule:

one. , if a and or if and .

2 , if a and , .

3 , if a and .

This rule is quite logical. If the next object is classified correctly by the system, then there is no reason to change . In case of (2) should be changed to increase . The proposed rule satisfies this requirement. Really,

.

Accordingly, in the case of (3) .

The choice is important . You can, in particular, choose . It is shown that if the training samples of two patterns are linearly separable, then the described step-by-step procedure converges, that is, the values ​​will be found at which

, if a ,

, if a .

If the samples are linearly inseparable (Fig. 6), then there is no convergence and the estimate , minimizing the number of incorrect recognitions, find the method of stochastic approximation.