Pattern recognition. Potential function method
Hello, I have been reading Habrahabr for a long time and I often come across articles about neural networks, in particular, about a single-layer perceptron. But for the present I have not met an article about other types of recognition functions of the perceptron type. As the name of the article suggests, this type of recognition function is called the potential function method .
At once I will make a reservation, the purpose of this article is not to provide a working program based on this method, but to tell about the algorithm itself, what it is based on and what are its advantages.
To begin with, I will describe the basic concepts of the pattern recognition theory used in this article, then I will give a brief explanation of the method and then write it out in detail.
')
Basic concepts
Image - display of an object on the sensory organs. That is, the description of the object, as a set of signs. Often an object is represented as a vector. If the set of features is constant, then the object is identified with its image.
Image (class) - a subset of the set of objects or images.
A decisive function is a function, to the input of which an image is fed, which determines whether an object belongs to a certain class.
Short description
The essence of this method, and indeed, of any algorithm used for pattern recognition, is to make up a decisive function that will determine for each object its belonging to the desired class.
In this case, the decisive function is compiled iteratively, using a labeled training sample (for each object from an agent, its class is known).
Physical interpretation
Imagine an n-dimensional metric space, where n is the number of attributes required to describe an object.
Let all the objects of the training sample (hereinafter denoted as OB) belonging to the class W1 create a positive potential, which takes the maximum value at the point corresponding to the object and decreases rapidly with distance, and the objects belonging to the class W2 negative.
Then in areas where objects of class W1 prevail there will be a positive potential, and vice versa.
In fact, each object from the training sample is assigned a charge, which “attracts” the classified object to the corresponding class.
Potential function
Let's move on to the method itself. To begin with, we will describe the actual potential function. As it is clear from the section on physical interpretation, here we draw analogies with charges and potential. Therefore, as a necessary function, we need to take one that will give the maximum value at a given point and will decrease rapidly with increasing distance.
The potential function will be denoted as K (x, xk), where xk, k = 1..m is one of the objects (vectors) from the training set.
Usually, a symmetric function is used as a potential function, two variables are X and Xk.
For example, K (x, xk) = exp {-a || x-xk || ^ 2}
Decisive function. Cumulative potential.
As a decisive function, we use the cumulative potential — a positive set of values ​​of individual potential functions if the object belongs to the class w1 and negative if the object belongs to the class w2.
The cumulative potential is as follows:
where rk + 1 =
The conditions for the termination of the algorithm will be an unmistakable definition of L0 objects, in a row. Where L0 is a user-defined number. It is set depending on the quality of the algorithm’s work, based on the following facts:
p is the probability of making an error after the presentation of Lk sample objects.
Then for any e> 0 and a> 0, the probability that p <e will be greater than 1-a if
L0> log (ea) / log (1-e)
Conclusion. Advantages and disadvantages.
Ultimately, we get a certain function K (x), which determines the belonging of this object to one of two classes with a given probability of error.
The advantages of the potential function method are in the nonlinear partitioning of the set of objects. That allows you to solve problems that are difficult to solve by other methods.
And the disadvantages are in the difficult choice of a suitable potential function and the complexity of calculations, with a large amount of training sample.
The article was somewhat brief, but I hope you learned something new for yourself. I told the main idea, there was a mathematical justification for the convergence of the algorithm for finding the decisive function and the rate of convergence, as well as a more rigorous mathematical definition of the potential function.
The purpose of this article was to tell about other, less common methods used for pattern recognition. If there is interest, you can tell about the stochastic and logical approaches to this problem.
At once I will make a reservation, the purpose of this article is not to provide a working program based on this method, but to tell about the algorithm itself, what it is based on and what are its advantages.
To begin with, I will describe the basic concepts of the pattern recognition theory used in this article, then I will give a brief explanation of the method and then write it out in detail.
')
Basic concepts
Image - display of an object on the sensory organs. That is, the description of the object, as a set of signs. Often an object is represented as a vector. If the set of features is constant, then the object is identified with its image.
Image (class) - a subset of the set of objects or images.
A decisive function is a function, to the input of which an image is fed, which determines whether an object belongs to a certain class.
Short description
The essence of this method, and indeed, of any algorithm used for pattern recognition, is to make up a decisive function that will determine for each object its belonging to the desired class.
In this case, the decisive function is compiled iteratively, using a labeled training sample (for each object from an agent, its class is known).
Physical interpretation
Imagine an n-dimensional metric space, where n is the number of attributes required to describe an object.
Let all the objects of the training sample (hereinafter denoted as OB) belonging to the class W1 create a positive potential, which takes the maximum value at the point corresponding to the object and decreases rapidly with distance, and the objects belonging to the class W2 negative.
Then in areas where objects of class W1 prevail there will be a positive potential, and vice versa.
In fact, each object from the training sample is assigned a charge, which “attracts” the classified object to the corresponding class.
Potential function
Let's move on to the method itself. To begin with, we will describe the actual potential function. As it is clear from the section on physical interpretation, here we draw analogies with charges and potential. Therefore, as a necessary function, we need to take one that will give the maximum value at a given point and will decrease rapidly with increasing distance.
The potential function will be denoted as K (x, xk), where xk, k = 1..m is one of the objects (vectors) from the training set.
Usually, a symmetric function is used as a potential function, two variables are X and Xk.
For example, K (x, xk) = exp {-a || x-xk || ^ 2}
Decisive function. Cumulative potential.
As a decisive function, we use the cumulative potential — a positive set of values ​​of individual potential functions if the object belongs to the class w1 and negative if the object belongs to the class w2.
The cumulative potential is as follows:
where rk + 1 =
The conditions for the termination of the algorithm will be an unmistakable definition of L0 objects, in a row. Where L0 is a user-defined number. It is set depending on the quality of the algorithm’s work, based on the following facts:
p is the probability of making an error after the presentation of Lk sample objects.
Then for any e> 0 and a> 0, the probability that p <e will be greater than 1-a if
L0> log (ea) / log (1-e)
Conclusion. Advantages and disadvantages.
Ultimately, we get a certain function K (x), which determines the belonging of this object to one of two classes with a given probability of error.
The advantages of the potential function method are in the nonlinear partitioning of the set of objects. That allows you to solve problems that are difficult to solve by other methods.
And the disadvantages are in the difficult choice of a suitable potential function and the complexity of calculations, with a large amount of training sample.
The article was somewhat brief, but I hope you learned something new for yourself. I told the main idea, there was a mathematical justification for the convergence of the algorithm for finding the decisive function and the rate of convergence, as well as a more rigorous mathematical definition of the potential function.
The purpose of this article was to tell about other, less common methods used for pattern recognition. If there is interest, you can tell about the stochastic and logical approaches to this problem.
Source: https://habr.com/ru/post/208174/
All Articles