In this paper we are devoted to the development of a new hybrid graph-based method of semi-supervised neural network learning for solving the classification problem. We analyze existing GSSL methods based on Laplace and Poisson Learning, identifies their advantages and disadvantages. We are proposed new generalizing error function for Poisson learning and some modifications. A new semi-supervised learning method is based on the generalized error function with an additional Tikhonov regularizer and ADAM optimizer. The proposed method allows obtaining better results compared to other existing GSSL methods on samples where there is an intersection of classes. Experimental verification of the proposed approach has shown an improvement in accuracy.
Modern methods of Semi-Supervised Learning (SSL) have been successfully used to solve data
classification problem problems in the presence of large amounts of unlabeled data and a small
amount of labeled data. In existing state-of-the-art theoretical and applied problems, the process of
data separation (the task of dividing data into classes) encourages the use of unlabeled data. There
are many SSL methods that are used to solve such problems, for example: generative models, contrast
models, cluster learning models, etc. [
The general method of Graph Based Semi-Supervised Learning (GSSL) can be represented as an algorithm and has the following steps [33].
1. Building a graph and initializing initial labels. 2. Building a penalty function. Adding regularization elements. 3. Finding the minimum of the penalty function. Label propagation algorithm.
Note that in this algorithm, the label values are calculated only for the vertices of the constructed graph, not for all the data, which significantly reduces the number of algorithm operations.
Currently, semi-supervised learning based on graphs underlies the construction of various Hybrid Neural Networks that are used in medical diagnostics [28, 29, 30].
The method of label propagation based on the Laplace equations was proposed [
A modern and more efficient method of semi-supervised learning is Poisson Learning [9]. This method is also found in other works [11], [12]. From the GSSL point of view, Poisson learning is similar to Laplace learning, but the label propagation is performed using the Poisson equation rather than the Laplace equation. In the following, we will use MODIFIED Poisson learning. Let’s consider the existing methods in the GSSL field.
2.1.
Currently, there are many different approaches for implementing semi-learning, which can be
viewed in the reviews [
Current research in GSSL is focused on the following methods: Label Propagation, Gaussian
Random Fields, Harmonic Functions and etc. Among the works that study these methods are the
following: [
One of the first studies in the eld of GSSL is the dissertation of [
Despite its effectiveness, there is no single universal method to determine a priori which learning method is best suited for any particular problem. Moreover, it is impossible to guarantee that the input of unlabeled data will not lead to performance degradation. Such degradation has been observed in practice, and its prevalence is likely underestimated due to publication bias [2]. The problem of performance degradation has been identified in other studies, [2], [38], [39].
This issue is especially relevant in examples where high performance can be achieved with purely supervised classifiers. In such cases, a significant decrease in performance is possible, outweighing the potential gain.
Several work [11], [16] have independently evaluated the performance of different semisupervised learning methods on different datasets. [38] empirically com-pared eleven different semisupervised learning algorithms using semi-supervised support vector and nearest neighbor methods, label propagation, and diversity regularization methods, applying hyperparameter optimization to each algorithm. By comparing the performance of the algorithms on eight different datasets, the authors show that no single algorithm uniformly outperforms the others. Some datasets showed significant performance improvements over the baseline, while others showed a decrease in performance. The relative performance also varied with the amount of unlabeled data. [39] compared several semi-supervised neural networks, including the average teacher model, virtual adversarial learning, and a wrapper method called the pseudo-label method, on two image classification problems. They reported significant performance improvements.
In recent years, the variational approach, which uses partial differential equations, in particular
the Laplace equation, has become a popular semi-supervised learning method [
For example, in [8], the adaptation of two partial differential equations, the p-Laplacian equation and the Eikonal equation, was considered. These equations are discrete analogs of the well-known partial differential equations widely used in image processing. The methods were illustrated for a semi-supervised classification task. The results showed that these methods work well with modern technologies and are applicable to semi-supervised classification.
In [9], a new framework called Poisson Learning is proposed and used for semi-supervised learning based on graphs with a very fast method speed. Pois-son learning solves the degeneracy problem of Laplacian semi-supervised learning. This method introduces a non-homogeneous function (the so-called "sources" and "receivers" based on the initial values of the labeled vertices), and solves the resulting Poisson equation on the graph. The results obtained are more stable and informative compared to Laplace learning. Poisson learning is efficient and easy to apply, and numerous experiments demonstrate its superiority over other state-of-the-art semi-supervised learning approaches on datasets such as MNIST, FashionMNIST, and Cifar-10. In addition, an advanced modification of Poisson learning, called Poisson MBO, is proposed, which provides higher accuracy and allows for prior knowledge of class sizes. Thus, differential equations, including the Laplace equation, the p-Laplace equation, the Eikonal equation, and the Poisson equation, play a crucial role in the variational approach to semi-supervised learning based on graphs. Poisson’s equations are especially useful when the amount of labeled data is very small.
Regularization and multiple regularization. Semi-supervised methods based onlabel propagation
using discrete partial differential equations are a powerful mathematical tool for solving
classification problems. However, even when using these approaches, there are problems when they
do not provide the required training results. Such cases include data noise, data sparsity, class
overlap, etc. The use of regularization approaches is considered in [
The issue of regularization is discussed in detail in [
One of the little-studied semi-supervised learning methods is the multiple regularization method, which is successfully used to solve practical problems in which parameter tuning is a rather complex and non-trivial task [19-23].
For example, in [19] , the authors consider a problem in which signal and noise are additively combined. To solve it, they use the method of adaptive parameter selection for multiple regularization. With the proposed algorithm, the regularization parameters are selected based on the degree of sparsity of the data area. In [20], the multiple regularization method is used to nd the optimal neural network training rate. In [21], a new regularization scheme is considered to recover the solution of a linear uncorrected operator equation given noisy data in Hilbert space. Paper [22] discusses multiple penalty regularization, which has been successfully used to solve uncertain sparse regression problems of the non-mixing type. The advantage of methods with multiple penalties is that any prior information can be incorporated into additional penalties. For example, in [23], to solve the extrapolation problem, forecasting points are included as a priori information when constructing an extrapolation estimate. Other works in this area, such as [24 -26], should also be noted. However, more complex regularization methods with multiple penalties require a more thorough study. 2.2.
Semi-supervised graph-based learning (GSSL) faces several key challenges at different stages. We list below some of the drawbacks and methods to compensate or eliminate them.
Graph construction stage. Building a suitable graph that represents the main relationships between data points is crucial. Various methods have been proposed, such as k-K-nearest neighbors, ϵ-nearest neighbors, Laplacian on a graph, and other approaches. These methods aim to identify local or global data structures and relationships. Some of them are listed in [5].
Label propagation stage. The main goal of GSSL is to propagate label values in the face of class
overlap (in a dataset with a very small number of labeled nodes) [
Scaling phase. Scaling GSSL methods for data sets whose size is constantly changing may require more time, financial and human resources. Approximation methods and parallel computing are used to optimize these costs while scaling. Some approaches, such as graph clustering and graph shredding, aim to reduce the size and complexity of a graph without additional information.
The stage of processing a limited amount of labeled data: GSSL seeks to utilize both labeled and unlabeled data. However, when labeled data is not enough, methods such as self-learning, collaborative learning, and active learning can be used [5]. These methods iteratively select informative samples for labeling or use multiple representations of the data to improve the learning process.
Resistance to noise. Noise and outliers in the data can significantly affect the performance of GSSL methods. Robust convergence measures and outlier detection algorithms are used to mitigate the impact of noisy data points on classification results [11].
In general, the following conclusions can be drawn: first, semi-supervised learning methods are powerful enough to solve many classification problems with different initial conditions; second, the most productive semi-supervised learning methods are label propagation methods based on iterative solution of partial differential equations (Laplace and Poisson); third, regularization and multiple regularization methods are used for complex data cases.
In this paper, we will study neural network training for solving a classification problem based on the Poisson equation algorithm with L2 regularization. Next, we will formulate the problem statement taking into account the solution of the existing shortcomings of other methods.
We consider the problem of classifying dataset presented by a graph with a small number of labeled and big amount vertices are given at the beginning. The dataset can have difficult cases: torch or intersection classes data.
Let there be given an undirected weighted graph ( , , ) with vertices. Х = { , , . . . , } - the set of vertices of the graph, - the set of edges, = , graph . Let us assume = 1 if the vertices , are similar, and = 0 if the vertices , are different. The degree of the node is determined by the formula = ∑ . According to Poisson learning [10], label propagation occurs by solving the Poisson equation, which has the form: - is the weight matrix of the which are considered labeled. = ∑
Nowadays, in the field of semi-supervised learning, the number of examples of label propagation models based on the variational principle and using second-order partial differential equations, such as, for example, Laplace's equation, Poisson's equation, etc., is increasing. This fact demonstrates the relevance and prospects of this approach. One of the well-known approaches in this direction is to use the Laplace equation, which is a homogeneous second-order partial differential equation. It is also known as Laplace learning. The use of the Poisson equation in semi-supervised learning is relatively recent and limited to a few studies [10]. However, the use of the Poisson equation in semisupervised learning has broader prospects for the future. Laplace learning and Poisson learning have a lot in common, but there is also a significant difference. Let's take a closer look at them.
It is known that the Laplace equation applies to various physical processes, such as heat distribution (heat conduction equation), electrostatic potential distribution, and others. However, Laplace's equation can be applied only in certain cases where there are homogeneous physical fields, such as a homogeneous electrostatic field or a homogeneous thermal field. If we need to consider a non-homogeneous problem and a non-homogeneous field, then a generalization of the Laplace equation to a non-homogeneous field, known as the Poisson equation, is used. From a mathematical point of view, the Poisson equation is a second-order inhomogeneous partial differential equation. Its left-hand side is the Laplace operator, and the right-hand side is the output function. The solution of a second-order nonhomogeneous partial differential equation can be found as the sum of the general solution of a homogeneous equation and the partial solution of a nonhomogeneous equation. The general solution is a solution to the Laplace equation. The particular solution of a nonhomogeneous equation depends on the initial term and must reflect the structure of the nonhomogeneity in at least one particular case. Thus, the Poisson's equation generalizes the solution of the Laplace equation to inhomogeneous physical fields or, in our case, to inhomogeneous information fields.
In information and data theory, the existence of relationships between data means that the data is represented in a heterogeneous space when examining the data field and its distribution in the data space. It is also necessary to assume that the structure of the heterogeneity is correct and can be described by a similar iterative algorithm. Thus, using the Poisson equation to identify data classes and dependencies within a class in a heterogeneous data space may be more promising than using Laplace equations because the heterogeneity function is used in the solution construction. This is significant when we have a small number of initial data points (labeled data). With a small number of labeled data and a large number of total data, Poisson learning has a significant advantage over Laplace learning in terms of computation time.
Thus, the study and use of Poisson learning, in particular semi-supervised graph-based learning using the Poisson method, is a more promising area that requires further research for various application tasks. 4.2.
Let's consider the problem of semi-supervised learning using Poisson equations more thoroughly. Poisson learning was proposed in [10] and has the form (2) ( ) = 0, + 1 ≤ ≤ where - is the non-normalized Laplace operator, - are the vertices of the undirected weighted graph, = ( ) - are the initial labels of the graph vertices, ( ) - is a function of graph vertex
Where Х = { , , . . . , } - is the set of vertices in the graph, - some function, neighborhood, σ is a parameter that controls the variance of neighbors.
Poisson learning also has a variational interpretation, which reduces semi-supervised learning to minimizing the Dirichlet energy. Dirichlet energy is often used as a penalty function. The Dirichlet energy formula can be represented as
- edge weight , , - is the total number of vertices in the graph, the first of which are considered labeled. = ∑
The weight of the graph edges can be calculated using the following formulas [9]: The label selection rule can be written as: do not significantly change the function u. points.
where. =
, - is the share of data belonging to the class ∈ 1,2.
These formulas can be called Poisson label propagation.
In the semi-supervised learning algorithm, to determine the value of the function that has labels for the unlabeled data, while maintaining the correspondence to the labels of the labeled data, an iterative solution is required. In general, the following four steps can be distinguished.
1. Initialization. The algorithm starts with an initial assumption that can be random or based on observed data.
2. Optimization. The function is iteratively updated to minimize the function ( )which includes both smoothing u by similar data points and fitting the labeled data.
3. Convergence. The process continues until converges, which means that further iterations 4. Prediction. After learning its functions, you can use it to predict methods for unlabeled data
use the ADAM algorithm as one of the most efficient among analogs for this problem [29].
In the next subsection, we will consider the application of a regularization application to the L2 penalty function for the proposed neural network training method. 4.3.
Application of regularization elements (3) (4) (5) (6) (7) (8) L2 regularization will help prevent overlearning by adding a penalty term to the loss function that is proportional to the square of the weights. The regulatory term has the following form: ( ) = ‖ ‖ = The objective function using Tikhonov regularization will have a modified entry: ( ) =
‖ ( )‖ = = + (1 − ) ,
= + (1 − ) ,
̅ = ( ) = ( ) −
( ̅ + ) 1 − 1 − 2 2
(9) (10) (11) (12) (13)
A qualitative difference in the behavior of 2 regularization behavior is the sparsity of the solution obtained by Lasso regression, i.e., the optimal value of some parameters is zero.
Above, we have outlined ways to improve the proposed approach for solving the classification problem when the amount of labeled data is too small and the classes overlap.
Further, within the framework of the chosen GSSL approach, a new method will be proposed with its further improvement in the form of regularization terms and an optimizer. 4.4.
Let's consider the optimization stage and apply the ADAM algorithm. The ADAM algorithm is often used to optimize the search for the minimum of error functions because of its stable performance. The structure of the algorithm is shown below.
ADAM (an extension of Adaptive Moment Estimation) is one of the best optimization algorithms commonly used in deep learning to tune model parameters during training. In practice, it has been found to perform well and often outperforms other optimization algorithms in many tasks. ADAM tracks the exponentially increasing average of previous gradients. This helps speed up convergence by taking previous gradients into account during the calculation.
For the hybrid ADAM algorithm, the optimization step looks like this , 1 Where
- this is the moment of impulse (within the middle gradient). - is the gradient at any time step k. - is the rate of exponential tightening of the momentum of the member
ADAM rescales the gradient using an exponential damped average of the previous gradient squares.
- is the velocity term (ковзне the mean square of the gradient). - is the rate of exponential decrease of the term velocity.
Because of the initialization and
at the beginning (initialized with zeros), they can be shifted towards zero. To counteract this, ADAM includes a change correction step. Using the corrected momentum and velocity terms, the parameters are updated: α is the learning rate. It determines the step size in the space parameters. - is a small constant that prevents division by zero.
This method will be presented in the form of the following algorithm. steps. weights. 4.5.
Let's consider a modified graph-based semi-supervised learning method based on Poisson learning with an additional regularizer and ADAM optimizer. So, this method will consist of the following
To build a weighted graph, we usually use the formulas of geometric distance (weight), Gaussian distance (weight), KNN distance (weight) according to formulas (3)-(5). The use of the weight function depends on the data layout. For classes that have intersections, it is better to use KNN
Initialization of the initial labels is done by selecting some labeled data from each class. It is preferable to use samples with the same number of labeled data in each class.
When constructing the penalty function, the Dirichlet energy function on the graph is used with additional terms that characterize the regularization of the data or the boundary conditions of the Dirichlet function. L2, L1, etc. regularization can be used as regularization additives.
If the full energy function is used as the energy function on the graph, then finding the minimum of the function is reduced to solving the Poisson equations on the graph. If the incomplete energy function is used, the algorithm is reduced to solving the Laplace equations. The numerical solution of these equations is the basis of the label propagation algorithm. In the proposed algorithm, we will use the ADAM method.
Thus, the algorithm can be rearranged as follows.
Step 1. Initially, we assume that an array of data and its labels is given.
1.1 Set m - the number of labels that will be selected from each class The balanced approach assumes that the number of labels from each class will be selected the same, the unbalanced approach assumes that the total number of labels for both classes will be selected randomly. But there will be at least one label in each class.
1.2 We take points from the given data set , , … , and their labels , , … , ∈ {0,1} The selection can be done randomly or by some other method.
Step 2. 2.1 Set (or calculate) = ,
an input symmetric weight matrix of dimension n. (The matrix of weights of edges (vertex degrees) is calculated using the KNN method, assuming that the vertex degree should not be higher than a given number, for example, 10) 2.2 We form. × = ( )
, - a matrix of classes of dimension 2 assuming that we have 2 classes. - j-points from the initial labeled sample m.
2.3 We define ∈ a vector on the set of classes, in which, whose element is the fraction of data points belonging to the class . If this information is not available, we assume == 1.
Step 3. In the third step, the degree matrix of the graph by the following formula: = ∗ = , ∗ Here, using the unit matrix 1, the matrix is transformed to a diagonal form.
Step 4. The fourth step calculates the non-normalized Laplace matrix of the graph by the formula = – = − Step 5. In the fifth step, the average label vector is calculated : (14) (15) On the labeled set , ...,
the computation of the solution ( ) will be shifted by an approximately constant value for each labeled node:
Since the function ( ) corresponds to some label yi , while the neighboring points will be constant and have the value equation (18) can be written as: ( ) =
( − ) = ( − ) of the degree
of the node by the centered label vector. of zeros Z of dimension 2( − ):
From equation (28), we can conclude that the Laplacian of a labeled vertex is equal to the product Step 6. In the sixth step, the solution of equation (19) is given in the form and write an array An array of zeros Z is created in dimension 2( − ): − = ( ) , −
= ,(
) ,
Step 7. The seventh step is to create an array of functions ( ) which we define as an array of zeros of dimension 2 (the starting point):
= ( , 2) = (
Step 8. In the eighth step, the main cycle of the calculation of the function ( ) for the number of steps T (11)-(13). Using these equations, we fill in the matrix of solutions ∈
Step 9. In the eleventh step, the labels are weighted. Feature weighting ( ) takes into account the label selection rule and is calculated using the following formula: =
∗ ∗ 1 ) , , (16) (17) (18) (19) (20) (21) (22) (23) (24) = [ − , (2, − )] або =
Thus, the matrix will be equal to the matrix for j from n-m to n. For j from 1 to m, calculate by the formula
( ) = ( ) ∗ - vector, the share of data belonging to class j.
Step 10. In the twelfth step, the label selection rule being tested can be written as: If formula (24) is true, the algorithm stops, otherwise the previous steps are repeated. We will consider the settings of the hyperparameters and . When considering the regularization problem, the hyperparameter plays an important role. In general, there are several algorithms for its adjustment [5]:
Grid search: in this method, a set of possible values for and then iteratively selects the optimal values. Although this can be computationally intensive, especially when multiple hyperparameters are being tuned simultaneously, it ensures a thorough search of the parameter space.
Random search: This approach first sets possible bounds for the value of and then selects a hyperparameter randomly from these bounds. Compared to grid search, random search is less thorough, but can be more efficient in cases of high-dimensional data.
Cross-Validation: Usually used in combination with grid or random search. The idea is to split the data into training and validation samples. The model is trained on the training set with a certain choice of λ and then evaluated on the validation set. The value of λ is chosen that gives the best results on the training set.
Bayesian optimization: This is a more sophisticated method that models the objective function (e.g., validation error as a function of λ) using a Gaussian process and then selects hyperparameters for a principled attempt based on this model. This is especially useful when grid search and random search are time-consuming.
Next, we will use grid search and random search. To do this, for the hyperparameters and a range of values was selected for the hyperparameters and values were selected in increments.
5.1.
Examples for synthetic data. There is the task classification of two moons without intersection and with intersection data. We consider four cases of two months (with, without class intersection, torch and embedded). A total vertex of graph - 2000 points and labeled vertex - 20 by 10 in each class (less than 1%). Here are the results of calculating the following metrics for the proposed method: accuracy, precision, recall, f1, f2, fbeta, which are summarized in the table. Figure 1,2,3 shows the given classes, initial labels, graph construction using the KNN-10 method, classification results, and the confusion matrix.
This result is shown that we can are achieved accuracy more 80%, so cases – two moons with intersection and more 75% for difficult cases two moons embedded. We have that accuracy for modified Poisson with ADAM more than accuracy Poisson with Gradient Descent.
We are considering case number two (two moons tight (torch)) and comparing with next methods: KNN, Laplace Propagation, Laplace Propagation WNLL, WNLL Poisson, Spectral Method, Conjugate gradient, Poisson Descent, Poisson Nesterov, Poisson Nesterov L1, Poisson Nesterov L2, Poison ADAM, Poisson ADAM L2, Poisson ADAGRAD, Poisson heavyball. All number of data 10000, label data {1,2,3,4}.
Modified method Poisson Label Propagation with regularize is shown the best accuracy for compare other methods so for number label data very small amount {1,2,3,4}. It is proposed a new approach for solving the classification task by using Poisson equations for SSL, which makes it possible to use a small labeled sample and a large amount of unlabeled data. The accuracy is improved by solving the Poisson equation using modern optimization methods such as ADAM. The validity of the obtained results is verified on different variants of the “two moons” sample. As a result, high classification accuracy was achieved (75-85%) - for the case of overlapping classes, (99%) - for the case of 1% of labeled data.
References