Neural-like networks and systems have numerous applications in artificial intelligence [1] and intelligent data analysis [2]. They are used in modern hardware [3] and software [4] tools and products [5,6]. The amazing capacities of artificial neural networks (ANN) are provided by the appropriate use of the network architecture [7] and related learning techniques [8,9].
The synergy between the network architecture, the kind of network nodes and the network learning (or synthesis) procedures is very important in the practice of neural computations [10]. Linear neural units with threshold activation functions [11], binary inputs and output were used in early models [12]. This kind of computation units was inspired by the models of biological neurons from the brain study [11]. But both the theoretical studies and practical applications showed the strong limitations of the basic neuron model of McCulloch and Pitts [12,13] as well as difficulties related to the learning of threshold ANN [14,15]. In order to overcome abovementioned limitations and difficulties, many more complicated models of neural devices were proposed [11,12]. The overall majority of these models employed two ways to increase the network capacities by enhancing the power of network neurons [10]. The first is based on the use of more sophisticated models of the aggregation of the input signals of the neural unit instead of the classical weighted sum of inputs [12], e.g., polynomial threshold units [12,13]. The second approach consists in the use of more complicated activation functions instead of the step function [12] from the Rosenblatt model [16,17]. Both approaches have their pros and cons discussed in [10][11][12][13][14] The multithreshold models were developed under the second approach [18]. One of the earliest among them was the multithreshold threshold element [19]. Binary multithreshold neuron with weight vector
where ( ) [18,20], because they are activated when the sum of weighted inputs is within the one if given disjoint half-open intervals, which are specified by the ordered sequence of their thresholds [21].
But the increase in the recognition capability of multithreshold is not gratuitous. One must pay a high price for this, which consists in the difficulty of the learning of such units [7,22], because the respective learning task is NP-hard even in the case of a unit with two thresholds. The research has two main goals:
•
The study of the model of multi-valued multithreshold neuron that should effectively use the advantages of multiple thresholds, be suitable for the multiclass classification and admits fairly simple training techniques.
The development of the learning algorithm for such units and the study of its fitness for intended applications in classification. The paper has the following structure. First, the works related to the topic of the study will be reviewed. Then, two models of multithreshold neural units will be considered: binary-valued and multi-valued, respectively. We will discuss its advantages and consider some downsides related to the complexity of their learning. In the next section two learning algorithms will be described, which are designed for the learning of a single k-threshold neuron. For both algorithms the conditions on the learning rate will be stated, which satisfy the finiteness of the learning in the case of their application to the learning of strongly k-separable sets. Next, the simulation results will be treated of the performance of trained multiclass k-threshold neural classifiers in the comparison with some other popular classifiers provided by Sklearn library [11]. Finally, two last sections contain the discussion of obtained results and conclusions.
The study of multithreshold neural units has a long history [19,23,24]. Multithreshold neural elements were introduced in the early studies in threshold logic [19,25]. As mentioned above, the additional thresholds were proposed with intention to increase the capacities of basic singlethreshold element [19,26]. Some properties of multithreshold neurons were stated in [22,25,26]. These works mostly dealt with the recognition capacity of multithreshold elements [2]. Issues related to the synthesis of multithreshold devices remained almost untouched, because few algorithms for training such multithreshold units and networks had been developed [18,24]. Therefore, the applications of devices using multithreshold approach were almost unknown [27] despite the better capabilities of multithreshold units compared to the classical linear threshold units [20,26]. The hardness results from [15,22] can explain these difficulties for the practical application of bithreshold systems to some extent. Nevertheless, as stated in [8,10,28], the lack of learning techniques for multithreshold systems caused the decline of interest in their study.
But recent advances in multithreshold logic changed the situation [7,14]. One of the reasons were new approaches in the synthesis ANN with hidden layers consisting of neurons with bithreshold activation functions [14,20]. They were developed on the base of the generalization of the Baum's synthesis algorithm [29] for threshold networks in the case of bithreshold nodes [14,28].
The advance in the application of so-called bithreshold networks was stated in [1,10], where such networks were considered as the effective tools, which are capable to solve typical problems of intellectual data processing and computational intelligence. The limitations and downsides of the basic bithreshold ANN from [7,14] were stated in [28]. Hybrid models of the multiclass classifier with heterogenous hidden layers were proposed in [28], where other kinds of neural units (e.g., WTA and single-threshold) units were used in order to enhance network performance and reduce its drawbacks. It should be noted that bithreshold ANN can be useful not only in classifiers. Their potential applications are considerably wider [2,6,8,9]. E.g., they were mentioned
in design of powerful deep ANN providing the exponential improvement of the memorization capacity [16]. The bithreshold approach primary was employed for the solution of real-valued problems [10]. But it admits the generalization to the complex domain [14]. The complex analogs of bithreshold activation could be proposed [30] that extend the capacity of complex-valued threshold neural units. This allows the multithreshold approach in the proceeding of data in the complex domain [17,28].
It should be noted that the above-mentioned advance in the application of multithreshold systems is actually related to only bithreshold models [7]. The examples of successful application of general multithreshold models with an arbitrary number of thresholds are unknown [14,30]. It became evident that the additional study is necessary before such models can be employed in machine learning systems [10]. One of them was the paper [22], where general k-threshold neural units were treated in the case 2 k . As was observed in [22], the parity of k has the great influence to the properties of multithreshold neurons. Moreover, every multithreshold unit can be realized using a small threshold circuit, and, consequently, every multithreshold network can be replaced by the equivalent networks consisting solely of bithreshold and threshold nodes [30]. Notice also that unlike the learning of a single threshold linear unit, the learning of a multithreshold unit proved to be NP-hard [22] confirming the similar result of the intractability of the learning of a single bithreshold unit [14].
Notice that all mentioned applications of bithreshold and k-threshold neurons have the binary outputs [28]. Thus, their employment in the classifiers requires the special shape of the network output layer with a separate neuron for every class and the using of "one versus all" approach in the learning or synthesis [11]. In some cases, a single output multi-valued neuron is preferable [12], because its application results in the network having fewer nodes and weight coefficients.
Let us consider again a model of k-threshold binary-valued neuron with the weight vector w and (ordered) threshold vector t, which output is given by (1). Note that its performance can be described as follows:
Model (2) has a simple geometrical interpretation [22,26]. The family of parallel hyperplanes
divides the space n R by 1 k + parts, which can be successively labeled by numbers 0, 1, …, k. All points belonging to "even" parts are attributed as "negative" ones. Remaining parts are considered as "positive" [22]. The illustration is shown in Figure 1, where the case 2, 3 nk == is considered. Figure 1 can also illustrate the nature of difficulties related to the application of binary-valued multithreshold neuron. Its value can alternate many times. It ensures the great capability of the multithreshold unit on the one hand, but results in the hardness of its training on the other hand. Note that the strict proof of the NP-hardness of the learning of a single binary-valued multithreshold neuron can be found in [22].
The multi-valued modification of the model ( 2) can be considered [18,23] that keeps the capacity of the base model and is easier in the training [24]. This multithreshold model uses the same weight vector w and threshold vector t, but differs in the output range of the neuron. To be more precise, the range set of k-threshold multi-valued neuron is
, and the neuron output y satisfies the following condition:
( )
where ( )
Consider again the geometrical illustration, now, for the k-threshold multi-valued neuron (3), (4). As it is shown in Figure 2, the performance of the neuron is also defined by parallel hyperplanes :
, which make partition of the space n R by 1 k + parts. These parts also are labeled by indices 0, 1, …, k corresponding to the output value of the (multi-valued) neuron whose activation is given by (4). Notice that same points are used in both Figure 1 and Figure 2, but their partition by classes differs, because there are only two classes for binary-valued k-threshold neuron and 1 k + -for its many-valued counterpart [22].
The pair (w, t) completely defines the multi-valued multithreshold neuron and is called its structure pair. Let A be an arbitrary set in n R . Then every multi-valued k-threshold neuron with structure pair ( )
This partition is called an ordered k-threshold partition of the set A, whereas sets 01 , ,..., k A A A are called strongly k-separable (compare with [22]). Note that the order matters for the strongly separated sets. Sets 01 , ,...,
are strongly k-separable [22].
,..., ( ,..., ,0,...,0,1,0,...,0).
The chained inequality
The last system can be rewritten in the following way:
Thus, we can reduce system (6) to the following system: A A A = − − ( X denotes the cardinality of the set X) and vectors bi are obtained using (7) and (8). Note that there are algorithms solving (9) in polynomial time [13]. Thus, the task of the learning of k-threshold multi-valued neuron (3)-( 4) is not NP-complete.
The reduction process can be described using the following pseudocode: A from the previous subsection and an adopted version of the relaxa- tion algorithm from [31,32]. The pseudocode of the algorithm is shown in the function Online-Multithreshold: A -an ordered partition corresponding to strongly k-separable sets, r-the number of learning epochs, 0 v -initial approxima- tion, -the schedule function that defines the behavior of the learning rate. The above algorithm uses three internal counters: i that is responsible for learning epochs, j-responsible for learning corrections, and err-responsible for the unit errors during the current epoch of learning. The goal of algorithm is the search of a vector
the inequality 0 vb holds. If such vector is already found, then the learning process terminates. Otherwise, the weight correction occurs in step 13 at least once per epoch. Note that this correction is successful only in the case 0 s . Thus, a random initial approximation should be used for 0 v to avoid the situation 0 s = during the learning. The following proposition states conditions ensuring the successful completion of the online learning using above algorithm.
where j is a correction step, s(j) is the dot product obtained in step 8 before jth correction, ( )
then there exists r such that OnlineMultithreshold produces a structure pair ( ) , wt of multi-valued k-threshold neuron, which satisfies (6) and performs desired partition of the set A.
Let us describe the offline approach to the learning of k-threshold multi-valued neural unit. It is designed using the modification of offline spectral algorithm from [32] adopted to solving the system (9). Let 1 ,..., m B = bb be a finite subset of nk + R , and nk + vR . We will need the following notations:
, sgn , ,..., ,
Note that both ( ) B s and ( )
. Consider the following algorithm:
has identical input parameters as its online counterpart from the previous subsection.
The following proposition states conditions ensuring the successful completion of the offline learning using above algorithm. Proofs of both propositions are omitted. They can be obtained using reasons similar to [32].
Consider the capability of our learning algorithms from the previous section to train a multivalued multithreshold-based classifier to solve the classification problems on some benchmarks. Let us compare their performance with well-known classification methods, such as classical perceptron, nearest neighbor classifier, random forest and feed-forward ANN (multilayer perceptron). Classifiers were compared on the following two real-world datasets: "balance-scale" (Balance Scale Weight & Distance Database) and "dry-bean" (Dry Bean Dataset) [33,34] provided by UC Irvine Machine Learning Repository [35]. The datasets contain 625 and 13611 learning instances from 3 and 7 classes, respectively [33,35]. The first dataset has 5 features, the second one-16 [33]. 25% instances of every dataset were used as the test set, and the rest 75%-as the training set. In order to obtain consistent results [12], the repeated random subsampling validation [11,36] was used. The learning experiments were repeated 500 times for every dataset and then obtained results were averaged concerning the accuracy on the training and test sets.
Default values of parameters recommended by Scikit-Learn library were used during training experiments for first four classical classifiers: 5 neighbors for nearest neighbor classifier, 1000 iterations for linear perceptron classifier, unbounded depth for random forest, one hidden layer with 100 nodes and 200 iterations for multilayer perceptron [36]. The constant learning rate 2 = was used for both MultiThreshold algorithm as well as random initial approximations 00 , wt. Datasets are not provided with an ordered partition into classes [35]. So, the classes were ordered using the alphabetical order induced by their labels. The following table contains results of experiments. By analyzing data from Table 1, we can conclude that:
• Both multithreshold algorithms performed well on the relatively easy small 3-class classification task on balance-scale dataset and the online modification had the second-best accuracy on the test set. • Classification on the dry-bean dataset was more difficult task for almost all classifiers considered during simulation. Learning for both linear perceptron and multilayer perceptron failed completely. Multi-valued multithreshold neuron yielded by OfflineMultithreshold performed better than neuron produced by online algorithm and had the best accuracy among all neural-like models, which were considered. But its accuracy was considerably worse than in the case of the use of random forest classifier.
Two versions of the learning algorithm for multi-valued multithreshold neurons have been proposed. The simulation results prove that both algorithms are capable to yield networks, which are suitable for the solution of classification problems in the case when the number of classes is relatively small. But the performance of both algorithms decreases in the case when the number of classes increases. It seems that it is due to at least two reasons.
The first one is the small number of parameters of the multithreshold model compared to other classifiers, which often use "one versus all" scheme [11,36]. It seems that above drawback can be overcome by using multithreshold networks [29] or more powerful neuron models with multithreshold activation, e.g., polynomial neurons [23,30,32].
The second reason is caused by the nature of the datasets related to majority of classification problems. They contain training pairs, each of which consists of a pattern and its class label. In terms of the partition, we deal with an unordered partition while proposed learning algorithms are designed to process with strongly k-separable sets corresponding to an ordered partition. The question arises how to convert an unordered partition to an ordered one. The brute force is not effective due to fast growth of factorial. Numerous heuristics can be used in order to increase the performance of the multithreshold neurons. This is a problem that deserves a separate consideration.
The problem of the application of multithreshold multi-valued neural units has been considered. These units separate the sets of patterns in n-dimensional vector space using parallel hyperplanes. This ability allows them to become candidates for computational nodes of multiclass ANN classifiers. Thus, the development of learning methods for such networks is important.
The simplest case of this learning problem has been treated, namely, issues concerning the learning of a single multi-valued multithreshold neuron. Two approaches to the training of multithreshold neuron have been developed. Both of them require the simple preliminary patterns transformation in order to reduce a given multiclass task to corresponding binary classification task. The online version of the learning algorithm is simpler and often faster. The offline modification performs single correction during each learning epoch, usually is more expensive but often yield the neuron having a somewhat better accuracy of classification. The conditions have been stated ensuring the finiteness of the learning process in the case of application of both algorithms to the training of k-separable sets.