You get a bonus - 1 coin for daily activity. Now you have 1 coin

The method of fragmented standards. Linear decision rules

Lecture



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.   The method of fragmented standards.  Linear decision rules . A hypersphere is built with the center in the standard and the radius   The method of fragmented standards.  Linear decision rules =   The method of fragmented standards.  Linear decision rules +   The method of fragmented standards.  Linear decision rules . 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.

  The method of fragmented standards.  Linear decision rules

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)

  The method of fragmented standards.  Linear decision rules =   The method of fragmented standards.  Linear decision rules .

  The method of fragmented standards.  Linear decision rules

Fig. 4. Linear decision rule for recognition
two images

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

  The method of fragmented standards.  Linear decision rules   The method of fragmented standards.  Linear decision rules   The method of fragmented standards.  Linear decision rules ,

if a   The method of fragmented standards.  Linear decision rules - implementation of the first image   The method of fragmented standards.  Linear decision rules ,

  The method of fragmented standards.  Linear decision rules   The method of fragmented standards.  Linear decision rules   The method of fragmented standards.  Linear decision rules

if a   The method of fragmented standards.  Linear decision rules - implementation of the second image   The method of fragmented standards.  Linear decision rules ,

then images   The method of fragmented standards.  Linear decision rules and   The method of fragmented standards.  Linear decision rules 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

  The method of fragmented standards.  Linear decision rules   The method of fragmented standards.  Linear decision rules   The method of fragmented standards.  Linear decision rules

  The method of fragmented standards.  Linear decision rules if a   The method of fragmented standards.  Linear decision rules   The method of fragmented standards.  Linear decision rules ,

  The method of fragmented standards.  Linear decision rules   The method of fragmented standards.  Linear decision rules , if a   The method of fragmented standards.  Linear decision rules   The method of fragmented standards.  Linear decision rules ,

Where   The method of fragmented standards.  Linear decision rules - some object of one of the images,   The method of fragmented standards.  Linear decision rules .

  The method of fragmented standards.  Linear decision rules

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

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

one.   The method of fragmented standards.  Linear decision rules , if a   The method of fragmented standards.  Linear decision rules and   The method of fragmented standards.  Linear decision rules or if   The method of fragmented standards.  Linear decision rules and   The method of fragmented standards.  Linear decision rules .

2   The method of fragmented standards.  Linear decision rules , if a   The method of fragmented standards.  Linear decision rules and   The method of fragmented standards.  Linear decision rules ,   The method of fragmented standards.  Linear decision rules .

3   The method of fragmented standards.  Linear decision rules , if a   The method of fragmented standards.  Linear decision rules and   The method of fragmented standards.  Linear decision rules .

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

  The method of fragmented standards.  Linear decision rules .

Accordingly, in the case of (3)   The method of fragmented standards.  Linear decision rules .

The choice is important   The method of fragmented standards.  Linear decision rules . You can, in particular, choose   The method of fragmented standards.  Linear decision rules . 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   The method of fragmented standards.  Linear decision rules at which

  The method of fragmented standards.  Linear decision rules   The method of fragmented standards.  Linear decision rules , if a   The method of fragmented standards.  Linear decision rules ,

  The method of fragmented standards.  Linear decision rules   The method of fragmented standards.  Linear decision rules , if a   The method of fragmented standards.  Linear decision rules .

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


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Pattern recognition

Terms: Pattern recognition