The issues related to the use of multithreshold neural units in multiclass classification are treated in the paper. Two models of multi-valued k-threshold neurons are considered. Online and offline modifications of the learning algorithm are designed to train multithreshold neuron to solve multiclass classification tasks using simple and fast learning techniques. The conditions are found ensuring the finiteness of the training. The experiment results demonstrate the performance of multithreshold multiclass classifier on real-world datasets compared to some popular classifiers.
Neural-like networks and systems have numerous applications in artificial intelligence [
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 [
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 w = (w1, , wn )Rn and threshold vector t = (t1, ,tk )Rk is the computation unit with n inputs x1, , xn whose single binary output y is calculated by the following rule: (1) where x = ( x1, , xn )Rn is an input vector, w x = w1x1 + ... + wn xn is the dot product of vectors w and x (weighted sum of inputs), k / 2 denotes the integer part of number k / 2 , t1 t2 ... tk , t0 = − and tk+1 = + are additional thresholds used for convenience only. Multithreshold elements outperform single-threshold ones [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 [
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 [
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 [
But recent advances in multithreshold logic changed the situation [
The advance in the application of so-called bithreshold networks was stated in [
It should be noted that the above-mentioned advance in the application of multithreshold
systems is actually related to only bithreshold models [
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 [
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: 0, if w x t1, 1, if t1 w x t2 , y = ................................................
(1 + (−1)k ) / 2, if tk−1 w x tk , (1 + (−1)k ) / 2, if tk w x. (2)
Model (2) has a simple geometrical interpretation [22, 26]. The family of parallel hyperplanes H j : w x = t j , j 1, ..., k divides the space Rn by k +1 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 n = 2, k = 3 is considered.
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 Zk+1 = 0,1,,..., k , and the neuron output y satisfies the following condition: where y = ft (w x) , 0, if x t1, 1, ft ( x) = ........................
if t1 x t2 , k −1, if tk−1 x tk , k, if tk x. (3) (4)
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 H j : w x = t j , j 1, ..., k , which make partition of the space Rn by k +1 parts.
Let A0, A1,..., Ak be strongly k-separable finite sets. Consider the task of the search of a multivalued k-threshold neuron with structure pair (w,t) that performs the desired partition ( A0 , A1,..., Ak ) of the set A that is the union of (disjoint) sets A0, A1,..., Ak , which satisfies (5).
Consider how one can reduce the above task to the solution of the homogenous system of linear inequalities in n + k variables w1,...wm,t1,...,tk . It is possible to rewrite (3)-(5) as follows:
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 k +1—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 Rn . Then every multi-valued k-threshold neuron with structure pair (w,t) performs the (ordered) partition ( A0 , A1,..., Ak ) of the set А, where:
Ai = x A | ft (w x) = i, i = 0,1,..., k
This partition is called an ordered k-threshold partition of the set A, whereas sets A0, A1,..., Ak are called strongly k-separable (compare with [22]). Note that the order matters for the strongly separated sets. Sets A0, A1,..., Ak are called k-separable, if there exists a permutation : Zk+1 → Zk+1 such that sets A (0) , A (1) ,..., A (k) are strongly k-separable [22].
a j ( x1,..., xn ) = (x1,..., xn ,0,...,0,1,0,...,0).
j−1 k− j The chained inequality t j w x t j+1 is equal to the system The last system can be rewritten in the following way: Thus, we can reduce system (6) to the following system: w x − t j 0, −w x + t j+1 0. a j (x) v 0, −a j+1 (x) v 0. w x t1, if x A0 , t j w x t j+1, if x Aj (1 j k ), w x tk , if x Ak .
Since sets A0, A1,..., Ak are finite and strongly k-separable, system (6) has solutions, which
compose n-dimensional convex set. If all non-strict inequalities in (6) were replaced by strict
ones, then resulting system would also have solutions. Let v = (w1,..., wn ,−t1,...,−tk ) ,
(5)
(6)
(7)
(8)
4
5
6
7
8
9
1
using (7) and (8). Note that there are algorithms solving (9) in polynomial time [
The reduction process can be described using the following pseudocode:
Notice that the transformation (7) is used in steps 3, 6, 7, 9 ensuring the filling of the output set B.
Consider the training of the multi-valued k-threshold neural unit to separate finite strongly kseparable sets A0, A1,..., Ak .
Let us describe the online learning algorithm for a k-threshold multi-valued neural unit that uses ReduceSet ( A0, A1, , Ak ) from the previous subsection and an adopted version of the relaxation algorithm from [31, 32]. The pseudocode of the algorithm is shown in the function OnlineMultithreshold:
ReduceSet ( A0, A1, , Ak ) 1 B 2 for x in A0 : 3 add −a1 (x) into B for i in 1,...,k −1 : for x in Ai : for x in A :
k add ak (x) into B 10 return B add ai (x) into B add −ai+1 (x) into B
B ReduceSet ( A0, A1, , Ak ) v v0 (i, j,err ) (0,0,1) while i r and err 0 : err 0 shuffle B for b in B: s b v if s 0 :
continue j j +1 err err +1 17 return w,t
Previous algorithm has four main parameters: (A0, A1,..., Ak ) — an ordered partition corresponding to strongly k-separable sets, r—the number of learning epochs, v0 — initial approximation, —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 v Rn+k such that for all b B the inequality v b 0 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 s 0 . Thus, a random initial approximation should be used for v0 to avoid the situation s = 0 during the learning. The following proposition states conditions ensuring the successful completion of the online learning using above algorithm.
Proposition 1. If A = A0 A1 ... Ak , sets A0, A1,..., Ak are finite and strongly k-separable, 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 (w,t) of multi-valued k-threshold neuron, which satisfies (6) and performs desired partition of the set A. 0 ( j ) 2 , 0 min ( j) max , (10)
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 B = b1,...,bm be a finite subset of Rn+k , and v Rn+k . We will need the following notations:
m m s( B) = bi , gv (b) = sgn ( v b), gv ( B) = ( gv (b1 ),..., gv (bm )), sv ( B) = gv (bi )bi , 1 = (1,...,1) .
i=1 i=1 n+k Note that both s( B) and sv ( B) belong to Rn+k and vector sv ( B) can be considered as an analogs of Fourier coefficients of the function gv : B → −1,0,1 . Consider the following algorithm:
1
B ReduceSet ( A0, A1, , Ak )
while j r and gv ( B) 1 : compute sv ( B)
Note that OfflineMultithreshold (A0 , A1, , Ak , r, v0 , ) 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.
Proposition 2. If A = A0 A1 ... Ak , sets A0 , A1,..., Ak are finite and strongly k-separable, v ( j −1) (sv( j) ( B) − s ( B)) where j is a correction step, ( j ) and ( j ) satisfy (10), v(j) is a value of vector v after jth correction, then there exists r such that OfflineMultithreshold (A0 , A1, , Ak , r, v0 , ) produces the structure pair ( w, t ) of a multi-valued k-threshold neuron, which performs desired k-threshold partition of the set A.
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 [
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 w0 ,t0 . 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 [
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. [16] S. Rajput, K. Sreenivasan, D. Papailiopoulos, A. Karbasi, An exponential improvement on the memorization capacity of deep threshold networks, in: Advances in Neural Information Processing Systems, volume 16, 2021, pp. 12674–12685. [17] Z.-G. Zhang, Y.-L. Xiao, J. Zhong, Unitary learning in conditional models for deep optics neural networks, in: Proceedings of SPIE – The International Society for Optical Engineering, volume 12565, 2023, no. 1256543. [18] N. Jiang, Z. Zhang, X. Ma, J. Wang, Y. Yang, Analysis of nonseparable property of multi-valued multi-threshold neuron, in: Proceedings of 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence), Hong Kong, China, 2008, pp. 413-419, doi: 10.1109/IJCNN.2008.4633825 [19] D. R. Haring, Multi-threshold threshold elements, IEEE Transactions on Electronic Computers EC-15.1 (1966): 45–65. [20] I. Prokíc, Characterization of multiple-valued threshold functions in the Vilenkin-Chrestenson basis, Journal of Multiple-Valued Logic and Soft Computing 34.3-4 (2020): 223–238. [21] R. Takiyama, The separating capacity of a multithreshold threshold element, IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-7.1 (1985): 112–116. [22] V. Kotsovsky, A. Batyuk, Multithreshold neural units and networks, in: Proceedings of IEEE 18th International Conference on Computer Sciences and Information Technologies, CSIT 2023, Lviv, Ukraine, 2023, pp. 1-5, doi: 10.1109/CSIT61576.2023.10324129. [23] N. Jiang, Y. X. Yang, X. M. Ma, and Z. Z. Zhang, Using three layer neural network to compute multi-valued functions, in 2007 Fourth International Symposium on Neural Networks, June 3-7, 2007, Nanjing, P.R. China, Part III, LNCS 4493, 2007, pp. 1-8. [24] M. Anthony, Learning multivalued multithreshold functions, CDMA Research Report No. LSE
CDMA-2003-03, London School of Economics, 2003. [25] V.K. Venkatesan, I. Izonin, J. Periyasamy, A. Indirajithu, A. Batyuk, M.T. Ramakrishna, Incorporation of energy efficient computational strategies for clustering and routing in heterogeneous networks of smart city, Energies 15.20 (2022): 7524. [26] S. Olafsson, Y. S. Abu-Mostafa, The capacity of multilevel threshold function, IEEE Transactions on Pattern Analysis and Machine Intelligence 10.2 (1988): 277–281. [27] I. Izonin, B. Ilchyshyn, R. Tkachenko, M. Gregus, N. Shakhovska, C. Strauss, Towards data normalization task for the efficient mining of medical data, in: Proceedings of 12th International Conference on Advanced Computer Information Technologies, ACIT 2022, Ruzomberok, Slovakia, 2022, pp. 480–484. [28] V. Kotsovsky, “Hybrid 4-layer bithreshold neural network for multiclass classification,” in
CEUR Workshop Proceedings, volume 3387, 2023, pp. 212–223. [29] E. B. Baum, On the capabilities of multilayer perceptrons, Journal of Complexity 4.3 (1988): 193–215. [30] V. Kotsovsky, A. Batyuk, V. Voityshyn, On the size of weights for bithreshold neurons and networks, in: Proceedings of IEEE 16th International Conference on Computer Sciences and Information Technologies, CSIT 2021, Lviv, Ukrain, 2021, volume 1, pp. 13–16. [31] S. Dasgupta, S. Sabato, Robust learning from discriminative feature feedback, in: Proceedings of Machine Learning Research, volume 108, 2020, pp. 973–982. [32] V. Kotsovsky, A. Batyuk, On-line relaxation versus off-line spectral algorithm in the learning of polynomial neural units, in: S. Babichev et al., (Eds.), Communications in Computer and Information Science, volume 1158, Springer, Cham, 2020, pp. 3–21. [33] OpenML: A worldwide machine learning lab, 2024. URL: https://openml.org. [34] M. Lupei, M. Shlahta, O. Mitsa, Y. Horoshko, H. Tsybko, V. Gorbachuk, Development of an interactive map within the implementation of actual state and public directions, in: Proceedings of the 12th International Conference on Advanced Computer Information Technologies, ACIT 2022, Ruzomberok, Slovakia, 2022, pp. 384–387. [35] M. Kelly, R. Longjohn, K. Nottingham, The UCI machine learning repository, 2023. URL: http://archive.ics.uci.edu. [36] S. Pölsterl, Scikit-survival: A library for time-to-event analysis built on top of Scikit-learn, Journal of Machine Learning Research 21 (2020): 1–6.