A scheme for stimulating message relaying cooperation

It is expected that all the nodes try their best to store and forward the messages in the intermittent connection network. However, due to the limited resources, such as memory, power, and transient communication chance, selfish nodes may relay the messages without responsibility. Stimulating selfish to behave normally could improve network performance. However, usually, it is difficult to distinguish the selfish behavior from the inability to relaying the message. By monitoring the behavior of relay nodes that messages are forwarding through, this article proposes a scheme that relays messages according to the reputation of intermediate nodes. The proposed reputation estimation scheme combines selfish behavior and inability behavior, and reveals very little private information for the protocol practice. There is a trade-off between the threshold and the performance. Too low value may not distinguish the selfish nodes. On the contrary, some normal nodes may excluded and cannot join the relaying and processing. Simulation effectively demonstrates that the reputation affects the node’s performance, and an appropriate reputation threshold value is useful for improving the network performance.

Introduction
The nodes store, carry, and forward a message in an intermediate tolerant network, by assuming that every node would like to cooperate, wait for opportunities, and try their best to deliver each message. However, selfish nodes existing in the networks or nodes that are constrained with memory, bandwidth, and calculation ability are likely to easily violate this hypothesis.
The selfish behavior of node, such as keeping itself the message when the memory becomes full 1 or first relaying itself the message when a connection ''opportunity'' arises, 2 will result in a lower delivery probability, 3 a higher overhead, and the overall performance decrease. 4,5 This would be more serious when the majority of nodes are selfish.
The barter-based schemes 5 aim at stimulating nodes to cooperate by exchanging messages. 6 Virtual currency is introduced in the credit-based system 7,8 and pricing game. 9 Cooperating nodes will be paid according to their service 10 of processing and relaying the messages of other nodes. 11 Selfish nodes that easily deny relaying messages would gradually cooperate. 12,13 Blackhole will decrease the network performance, which can be viewed as a kind of network attack and may be caused by the nodes that drop the message with the intention. 14 The node load was considered in selecting the communication mode of nodes; however, the residual energy of the node was not considered. Thus, it may not reflect the real load that the node can be processed. 15 Interactions among nodes communication 14,16 are used to evaluate and select the one that passes the threshold. Moreover, the more the personal information obtained, such as the mobile model, encounter frequency, and connection time, the more accurate the evaluations would be. 17,18 Furthermore, machine learning has been widely used in parameter decision; [19][20][21] in such methods, generally, a few key factors are chosen to design the message relaying and processing. 22 By analyzing the relation between the throughput and the packet dropping probability of the wireless channel, a jointing adaptive modulation was designed to improve the throughput with guaranteed low and tolerable packet dropped probability. 23 By observing and evaluating the interaction pattern of nodes in network, reputation-based strategies identify which node is the selfish one. A node can adopt a different strategy by checking others reputation values when they meet each other.
Moreover, usually it is difficult to distinguish the behavior of node. For example, some nodes are honest but not competent to the task of relaying message due to lack of memory, unable to move, due to short communication range, and so on. Some nodes are selfish that pay no heed to carry on relaying nodes.
Furthermore, the relay node should reveal private information as little as possible, such as the history and location information, and require low computation ability and a small amount of memory space in order to be widely used. Therefore, how to make correct calculation of node reputation has become a challenging issue in delay tolerant networks (DTN).
Conceptually, the selfish and uncompetitive behavior should be considered in node reputation for candidate selection. However, there are a lot of issues involved in reputation calculation, often the calculation of most appropriate value has to reveal various types of personal information, such as data delivery rates, memory, delay, and bandwidth consumption, and they influence each other and require high computation ability.
In order to evaluate the reputation without revealing the node's private information as little as possible, this article proposed a novel scheme. It treated the evaluation of selfish behaviors same as the uncompetitive activities. Dropping messages will eventually result in performance deterioration, even if the behavior that dropping messages are caused by insufficient.
In other words, selfish or uncompetitive behavior will result in failure of relaying message. That is, such nodes are low in reputation to task the forwarding message. Thus, fixed criteria can be used, and thus the calculation is simplified. For the protocol practice, we calculate the reputation using the successful relayed message information, which indicates all the factors affecting successful relaying message. Thus, by monitoring the results of relaying message, we can reflect their behavior in a simple way.

The reputation estimation
In the network routing, some nodes will refuse to take the duty of relaying messages due to its inadequate resources-such nodes are called selfish nodes. Usually, a reputation value is used to evaluate and mark the selfishness of the nodes. Node's reputation represents how selfish a node is. The routing algorithm should not select the node with a low reputation as a relay node. That is, the selfishness should reflect the node with a low reputation and should be avoided to be selected as relay node or may have little impact on the routing performance.
However, for practice, it is difficult to identify the primary reason that the node did not relay the node. For example, a node that did not relay a message may not only due to selfishness but also due to low power, insufficient power, short communication range, and so on. Therefore, the reputation calculation should reflect these factors to some extent.
In this way, a reputation value is used to represent the ability and the reliability that a message would be successfully processed in an intermediate node. Thus, by selecting the node with a higher reputation value, the relaying behavior and processing ability of a node are reflected and integrated into the proposed scheme.
First, a candidate node is selected as a relay node when its reputation is beyond the threshold. Second, to achieve fairness, the reputation value of a candidate node is evaluated not only by the sending node but also by the other nodes with their records of the candidate's historic behavior.
The above steps include both the quantity that a node cooperates and the ratio of successful forwarding on reputation values. In order to obtain a good reputation value, nodes need to continuously relay the reliable forward message.
Furthermore, every node would like to require service from node with higher reputation, and to process messages for nodes with high reputation, consequently, reputation values of selfish node will gradually decrease. Eventually, a selfish node will be isolated when its reputation is below a predefined threshold. This stimulates all individuals to cooperate in forwarding in order to earn a higher reputation.
In order to deal with a selfish node, an effective node cooperation mechanism that promotes the cooperation of nodes is necessary. The classical protocols, such as epidemic algorithm, are kind of flooding-based protocols in DTN. It is assumed that nodes are fully cooperative. But, in fact, due to the restrictions of various network conditions, there are always some nodes that become selfish or unable to serve continuously. The performance of network will be seriously affected due to such selfish nodes.
On the purpose of effectively estimating the selfishness degree and possibility of cooperation of nodes in DTN, each candidate node is evaluated by recording its transmission and forwarding behavior.
As we mentioned in the previous section, a node j calculates reputation of a node i, R d ij , in equation (1). It consists of two parts: One part is directly calculated based on node j's record data, another is indirectly from other node's remark value. We use R d ij and R in ij to present the direct and indirect values, respectively. The parameter a is the weight 24 The directed reputation value is calculated in equation (2). N s is the number of messages that node j sends to node i, and requires node i to relay. N f is the number of messages that node i relayed for node j Equation (3) calculates the indirect reputation. It is the average value of the direct values scored by all the other nodes The reputation-based forwarding scheme All non-duplicated messages are forwarded to each other when they are in the communication range in epidemic-based protocol. This processing will not stop until the message eventually delivered to the destination nodes. Ideal, if the message has a long time-to-live value, and the memory of the node is sufficient, a flood-based protocol could obtain a shorter delay and a higher delivery ratio. However, usually, the memory and the time slot of encountering are very limited, and the flooding process wasted the bandwidth and deteriorated the performance of protocol. 25 Nowadays, everyone pays attention to secure their private information, revealing very little private information (such as the history and location information), and requires low computation ability, and a small amount of memory space is one of the most important factors for a protocol to be widely deployed. 26 In this article, we propose a reputation-based epidemic algorithm. Conceptually, the reputation should be considered to reflect the behavior of nodes and to effectively satisfy requirement on performance metric. However, there are a lot of issues involved in reputation calculation; often the calculation of most appropriate value has to reveal various types of personal information, such as data delivery rates, memory, delay, and bandwidth consumption, and they influence each other and require high computation ability. For the protocol practice, we calculate the reputation using the successful relayed message, which indicates all the factors that affect successful relaying message. The factors, such as low memory and short communication range, result in failure of relaying message to some extent. That is, candidate node is assessed by monitoring the relaying behavior and developing a reputation-based message forwarding mechanism.
When a node j meets node i without the message, node j calculates the reputation value R ij of node i. If R ij is beyond the threshold, the message will be sent to node i for relay. The nodes with good reputation are selected as candidate nodes for relay and priority service. In order to obtain routing service, the selfish nodes will have to be honest and good to relay messages so that they get a good reputation. This mechanism stimulates all individuals to cooperate in relay message.
At the beginning, since the contact between nodes is not frequent, the direct reputation may not effectively represent the overall reputation. When more and more nodes encounter others, the reputation value may indicate reality to some extent.

Performance metrics
Following metrics, the Opportunistic Network Environment (ONE) simulator 27 was widely used in the delay tolerate network simulation to evaluate the performance of protocols: 1. Delivery probability is defined as the ratio between the number of received messages at the destination and the total number of generated messages from the source nodes. 2. Latency is used to evaluate the average time of message from generation to reception. 3. Overhead ratio is the number of delivered messages divided by the number of messages to be delivered. 4. Created represents the number of messages created excluding the duplicated message. 5. Dropped represents the number of messages dropped from nodes' buffers. 6. Hopcount is the hops through source to destination node.

Parameters used in simulation
The proposed scheme used some default parameters 27 in ONE simulator for simulation, as shown in Table 1.
The event interval and increment in the number of nodes will increase the number of messages that needed to be delivered. A node with an appropriate buffer size would be helpful to buffer the messages and kept them in the process of the relay. If the buffer size is too small, it may result in the message dropping, especially when large size messages and more messages are generated in the dynamic networks. Hence, the value of the parameters considers and meets all the above-mentioned requirements. 25

Speed factor
As shown in Figure 1, mobility is one of the critical factors for increasing the network capacity and improving the coverage and connectivity. 26 When all the nodes move slowly at the beginning, the overall performance is almost the same. Because the nodes' mobility is low, consequently the searched areas are small and the probability of meeting the destination is low. Moreover, a  high threshold means that more nodes will be excluded from relaying messages. When all the nodes move at a higher speed, the performance degradation caused by the inadequate number of nodes could make up to some extent. This is because denser nodes provide more redundancy for the message flooding. In a sparse node, the loss of a few partial qualified nodes can result in loss of coverage to significant portions of the network. At the same number of created, a higher reputation value results in a short hopcount to forward the message. This is because the candidate nodes selected with a higher reputation will try to forward the message. Numerical results indicated that when the reputation is low, the decrease in delay due to the increased number of nodes for relaying a message is modest. This is because the delay is dominated by the validity of potential paths formed by the nodes.
Traffic load factor  for all reputation values. However, a high reputation value has a relatively good performance when a short interval is used to inject messages into the network. This showed that a higher reputation threshold is appropriate for handling the message forwarding if there is not a very high stress of message delivery.
When more and more messages are generated in the network, the intermediate nodes will drop some messages when their buffer is full. The result is that such invalid copies dropped at higher traffic load, which results in a decrease in overhead. However, the vibration of overhead is not obvious for different thresholds.
A higher reputation threshold is good for the performance of overhead, as shown in Figure 2. A higher reputation threshold results in short hops between the source and the destination since there is not an irresponsible attitude toward the message forwarding.
Node density factor Figure 3 shows the performance with varying number of nodes from 24 to 72. For the given network setting with reference to 72 nodes, performance fluctuations are high. In a network with sufficient nodes, it is quite likely that one of the relay nodes to which the message has been relayed will find a node that has a valid short hop to the eventual destination, thereby increasing the possibility that the message will be successfully delivered and decreasing the latency, as shown in Figure 3.

Conclusion
Due to the limited resources, such as memory, power, and transient communication chance, selfish nodes may relay the messages without responsibility. This article proposed a reputation-based scheme, which evaluates the node's reputation in its behavior of relaying message and node's ability to deliver message. By combining selfish behavior and inability behavior, the proposed reputation estimation method reveals very little private information. It is useful for the protocol to be widely accepted and applied in practice. Results showed that the proposed scheme is effective. The higher moving speed of nodes improves the encountering frequency so that the possibility of encountering the destination nodes is also improved. An appropriate reputation threshold value is useful to improve the network performance in different node load, speed, and density of nodes.
Conceptually, the reputation should be considered to entirely reflect the behavior of nodes. If all the information on the network can be collected, the information would be useful to exactly judge the behavior of the nodes. For example, if messages are dropped by a relay node and when the available space of the buffer of the node is enough, the dropping behavior may be unreasonable. If a node always delivers its message with high priority, then the nodes may be selfish. In other words, the more the delivery-related information obtained, the more the flexible strategy could be designed. In this article, we aim to design a protocol that collects little private information. Thus, in the future, the evaluation accurate of the results can be further improved by collecting more information.
In the future, a strategy may be applied that tries to utilize more public information, such as the mobile model, the average connection time, and the average speed, as well as to select the appropriate rule to punish and stimulate the nodes to satisfy the requirement on the performance metric. Collecting and calculating all the factors, such as data delivery rates, memory, delay, and bandwidth consumption, require high computation ability of the nodes. For the protocol practice, such protocols would be available with the developing of the hardware technique.

Declaration of conflicting interests
The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.


extfieldsofstudy:
Computer Science
Mathematics

text:
Fast Fr\'echet Inception Distance

The Fr\'echet Inception Distance (FID) has been used to evaluate thousands of generative models. We present a novel algorithm, FastFID, which allows fast computation and backpropagation for FID. FastFID can efficiently (1) evaluate generative model *during* training and (2) construct adversarial examples for FID.

Introduction
Generative modeling is a popular approach to unsupervised learning, with applications in, e.g., computer vision [21] and drug discovery [19]. A key difficulty for generative models is to evaluate their performance, i.e., how good is the generative model approximating the data distribution? For image data, it is most common to use the Frechet Inception Distance (FID) [14]. FID is computed using m "fake" samples from the model distribution and n "real" samples from the data distribution.
FID is used in two ways [14]. Most commonly, FID is used to compare generative models after training. However, FID can also be used to monitor improvements of a single generative model during training. Monitoring improvements during training is particularly useful when training Generative Adversarial Networks [12], which normally lack a numeric indicator for whether the generators performance improves. For model comparison after training one typically use 50000 samples, which takes a long time. For monitoring improvement during training, we find that it is sufficient to use surprisingly few fake samples m if the number of real samples n remains large.
Decreasing m appropriately reduces computation time from approximately 60s to 10s. We further reduce computation time to approximately 0.2s by introducing a novel algorithm FastFID. FastFID supports gradient computations which allow efficient construction of adversarial examples for FID, see Figure 1. FastFID generalizes to similar distances like Fréchet ChemNet Distance (FCD) [20].

Original
Bad FID

Modified
Good FID  Preprint.

Fast Fréchet Inception Distance
The FID between the model distribution P model and the real data distribution P data is computed as follows. Draw "fake" model samples f 1 , ..., f m ∼ P model and "real" data samples r 1 , ..., r n ∼ P data .
Encode all samples f i and r i by computing activations A(f i ) and A(r i ) of the final layer of the pretrained Inception network [23]. Compute the sample means µ 1 , µ 2 and the sample covariance matrices Σ 1 , Σ 2 of the activations A(f i ), A(r i ). The FID is then the Wasserstein distance [11] between the two multivariate normal distributions N (µ 1 , Σ 1 ) and N (µ 2 , Σ 2 ).
For evaluation during training, the original implementation use 10000 samples by default [14]. On our workstation, 2 this cause the FID evaluation to take approximately 20s. Of the 20s, it takes approximately 10s to compute Inception encodings and approximately 10s to compute tr(

Previous algorithm
The original FID implementation [14] computes tr( The matrix square root is computed using SCIPY.LINALG.SQRTM [24] which implements an extension of the algorithm from [3] which is rich in matrix-matrix operations [10]. The algorithm starts by computing the following Schur decomposition. The algorithm then computes a triangular matrix U such that U 2 = V by exploiting the triangular structure of both U and V . In particular, the triangular structure implies the following triangular [10]. The equations can be solved wrt. U one superdiagonal at a time. The resulting U yields a matrix square root of the initial matrix. Uniqueness. The matrix square root √ M is defined to be any matrix that satisfies √ M √ M = M . The square root of a matrix is in general not unique, i.e., some matrices have many square roots. The above algorithm does not necessarily find the same square root matrix if it is run several times, because the Schur decomposition is not unique. Furthermore, when computing U ii = √ T ii one has the freedom to choose both ±| √ T ii |. The SCIPY.LINALG.SQRTM implementation choose U ii = | √ T ii |. Our implementation of the algorithm we present in Section 2.2 computes the trace tr( √ Σ 1 Σ 2 ) such that it agrees with SCIPY.LINALG.SQRTM up to numerical errors.

Our algorithm
This subsection presents an algorithm that computes tr( Σ 1 Σ 2 ) fast. The high-level idea: construct a "small" matrix M such that the eigenvalues Since M is small, we can compute its eigenvalues faster than we can compute the matrix square root √ Σ 1 Σ 2 .
Let X 1 ∈ R d×m be a matrix with columns A(f 1 ), ..., A(f m ), let X 2 ∈ R d×n be a matrix with columns A(r 1 ), ..., A(r n ) and let 1 k be the 1 × k all ones vector. The sample covariance matrices Σ 1 and Σ 2 can then be computed as follows: This allows us to write Recall that the eigenvalues of AB are equal to the eigenvalues of BA if both AB and BA are square matrices [17]. The eigenvalues of the d × d matrix The matrix M is small in the sense that we will use m d, for example, for FID we often use m = 128 fake samples while d = 2048.
Since both U and V are triangular they have their eigenvalues on the diagonal, which means that Note that even though the Schur decomposition Σ 1 Σ 2 = QU Q T is not unique, U will always have the eigenvalues of Σ 1 Σ 2 on its diagonal and thus preserve the trace. Putting everything together, we realize that tr( For completeness, we provide pseudo-code in Algorithm 1. The algorithm can be modified to compute FCD by simply changing the Inception network to the ChemNet network. .., f m ∼ P model , the Inception network Net(x) and precomputed µ 2 , C 2 .
9: // Compute trace of square root matrix. 10: 14: // Compute trace of both covariance matrices. 15: tr Computing Gradients. If the network Net(x) used in Algorithm 1 supports gradients with respect to its input, as the Inception network does, it is possible to compute gradients with respect to the input samples f i . If f i were constructed by a generative model, one can even compute gradients wrt. the parameters of the generative model. If Algorithm 1 is implemented with autograd support, e.g., through PyTorch [18] or TensorFlow [1], these gradients are computed automatically. For example, we implemented Algorithm 1 in PyTorch and used autograd to compute gradients when constructing adversarial examples in Section 5.
Potential Further Speed-ups.
In this section, we have focused on decreasing the time consumption of tr( √ Σ 1 Σ 2 ). As a result, the majority of the time consumption of Algorithm 1 is spent computing Inception encodings. The Inception encodings could be further speed up by, e.g., compressing [6] the used network at the cost of introducing some small error.

Speed-Up
In Section 2, we presented a fast algorithm to compute tr( √ Σ 1 Σ 2 ), which can be used to speed up the computation of both FID and FCD. In this subsection, we compare the running time of our PyTorch [18] implementation of Algorithm 1 against open-source implementations. 3 The algorithms are compared as the number of different fake samples varies m = 256, 128, ..., 8.
We used images from the CelebA dataset [15] when timing FID. We used SMILES molecules from the MOSES dataset [19] when timing FCD. For both FID and FCD, we precomputed Σ 2 with 10000 real samples. We also timed tr( C T 1 Σ 2 C 1 ) in isolation, by using Σ 2 ∈ R d×d with N (0, 1) entries and computed C 1 from Equation (4) where X 1 ∈ R d×n has N (0, 1) entries. To make timings of tr( C T 1 Σ 2 C 1 ) comparable with FID, we chose d = 2048 so it matches the Inception network. For each m, we ran one warmup round and then repeated the experiment 100 times. For all m, our algorithm is at least 25 times faster than the previous algorithms, and in some cases up to hundreds or even thousands of times faster. We emphasize that both algorithms were given the same task and computed the same thing, our algorithm was just faster.

Numerical Error
To investigate the numerical error of Algorithm 1 and SCIPY.LINALG.SQRTM, we ran an experiment where the square root can easily be computed. If we choose C 1 = C 2 then C 1 C T 1 C 2 C T 2 = (C 1 C T 1 ) 2 is positive semi-definite and has an unique positive semi-definite square root (C 1 C T 1 ) 2 = C 1 C T 1 . Furthermore, it is exactly this positive semi-definite square root SCIPY.LINALG.SQRTM computes, since the implementation chooses the positive eigenvalues U ii = | √ V ii | (see Section 2.1 for details). We can then investigate the numerical errors by comparing the ground truth tr(C 1 C T 1 ) with the result from both Algorithm 1 and SCIPY.LINALG.SQRTM. To amplify the numerical errors we used 32-bit floating points instead of 64-bit floating points.
The experiment was repeated for m = 32, 64, 128, 256 number of fake samples, were C 1 was computed as done in Section 3.1. We report the ground truth tr(C 1 C T 1 ) and the absolute numerical error caused by Algorithm 1 and SCIPY.LINALG.SQRTM, e.g., we report |tr( Table 1. The numerical error of Algorithm 1 is at least 1000 times smaller than that of SCIPY.LINALG.SQRTM. We suspect Algorithm 1 is more numerically stable because it computes eigenvalues of a "small" m × m matrix instead of computing a Schur decomposition of the "full" d × d matrix.  Figure 3, which displays the error of discriminator/generator during training of a DCGAN [21] on CelebA [16] at 64 × 64 resolution. This looks quite different to supervised error functions like mean squared error, which typically drops steadily during training. Both the discriminator error and the generator error has no clear interpretation. This makes it difficult to determine whether training improves the performance of the generator.
To mitigate this issue, [14] used FID to evaluate a DCGAN [21] during training. We similarly computed FID every 10 mini-batch updates using m = 10000, see the right plot in Figure 3. 5 The FID drops steadily during training, which indicates that training does indeed improve the performance of the generator, at least as measured by FID. However, computing FID with m = 10000 is computationally expensive. Each FID computation took at least 20s, while a single mini-batch update of the DCGAN took 0.09s. This means the FID computations took at least 20 times the training time, even though we only computed FID once every 10 iterations. To speed up the evaluation, we computed FID with Algorithm 1 using just m = 128 fake samples, while still using the n = 10000 precomputed activations on the validation set. The resulting FID computation took 0.2s, at least 100 times faster. As a result, the FID computations took no more than 0.25 times the training time.
Let F ID m denote FID evaluated with m fake samples. We plot both F ID 128 and F ID 10 4 during training of the DCGAN in Figure 4. The left plot shows both FIDs during the first epoch (1500 mini-batch updates). Both FIDs drop during training, and they qualitatively appear to be very similar.
The middle plot shows that both FID losses behave similarly throughout training. To quantify the error we get by using F ID 128 instead of F ID 10 4 , we attempt to measure how good F ID 128 is at predicting F ID 10 4 . For simplicity, we fitted a linear regression model f (F ID 128 ) = a·F ID 128 +b to approximate F ID 10 4 . The linear regression model solves to f (x) = 1.086x−54.165 which attains correlation coefficient r = 0.995 and a mean squared error of 0.0032. The right plot in Figure 4 shows F ID 128 on x-axis and F ID 10 4 on y-axis and the linear regression model.
The linear model suggests that the computed F ID 10 4 and F ID 128 are roughly related by an offset. It thus seems reasonable to use F ID 128 as a measure of relative generative improvement during training. We emphasize that the 100× speed-up typically makes the difference as to whether such quantitative evaluation is practically feasible or not. One of the main difficulties when debugging and experimenting with GANs, is the lack of a single numeric measure of generative performance that can be frequently evaluated at a low cost, this is now possible with F ID 128 using Algorithm 1.

Frechet ChémNet Distance
On image data it is often possible for humans to qualitatively evaluate whether model samples improve during the early stages of training. However, it seems harder for humans to carry out such qualitative assessment when the generated samples are, e.g., molecules. This motivates the need for quantitative evaluation of molecules during training of generative models. In this section, we demonstrate that Algorithm 1 also allows efficient computation of FCD. For simplicity, we retrained the Variational AutoEncoder from [19] on the MOSES dataset and compared F CD 128 against F CD 10 4 . The results are visualized in Figure 5 following the same structure as Figure 4. It took around 1.87s to compute F CD 10 4 and only 0.055s to compute F CD 128 , at least 30 times faster.

Adversarial Examples
Previous work showed that it is possible to make images that fool neural network classifiers [13]. One well know example makes an imperceptible modification to a correctly classified input image of a panda by adding a small vector of "noise," which fools the classifier to predict the new input as a gibbon with high confidence [13].
What would adversarial examples be for FID? Here, we present two types. First, images that perceptibly look like random noise but attain good FID, denoted "adversarial noise for FID." For an example, see the second row of Figure 1a. Second, images that perceptibly look real but attain a bad FID, denoted "adversarial examples for FID." For an example, see the second row of Figure 1b. Together, these two types of adversarial attacks show that it is possible to fool the FID.
A simple way to make an adversarial input, being noise or a natural looking image, is to optimize F ID(z) by gradient updates from some starting point z. We take z to be samples from either random noise vectors z ∼ N (0, 1) or random samples from the CelebA dataset [16]. To ensure that generated samples remain valid, i.e., in the range [0; 1], under gradient updates, we apply the sigmoid function to the adversarial noise and clip values of adversarial examples. To compute FID during training, we have pre-computed that statistics for a training set of 190 thousand samples and a validation set of ten thousand samples. We optimize the same batch of 64 samples to either maximize or minimize FID. Note that the reported F ID 64 is biased in the sense that it is an upper bound of F ID 10 4 . This bias means that the adversarial noise may have a better (lower) F ID 10 4 since it is no more than F ID 64 . On the other hand, it means that the adversarial examples may be worse (lower).
Adversarial Noise for FID. Figure 6a depicts the training and validation loss during 500 gradient steps on a batch of noise. The validation loss reaches an FID of 42.6 after 500 steps, as indicated by the gray dashed line. In Figure 1a, one can compare random samples from the initial random batch of noise, which has a validation FID of 463.9, and the same samples but after the 500 gradient steps. The produced adversarial noise still visually looks like random noise but attains a low FID.
Adversarial examples for FID. Figure 6b shows the training and validation loss during 200 gradient steps on a random sample of 64 real images from the CelebA data set. After 200 steps, the validation FID is 9901.1, as indicated by the dashed grey line. Again, for a comparison between original samples and optimized samples, see Figure 1b.

Related Work
The literature contains several methods for evaluating generative models. An overview can be found in [4] which reviews a total of 29 different methods. This article concerns the FID, which is arguably the most popular method, often used to benchmark state of the art generative models like, e.g., [5].

Computational Resources
To the best of our knowledge, there exists no published article which reduces the computational resources associated with the FID. However, some open-source implementations of FID contain modifications which remove parts of the resource heavy computations. Such "modified FIDs" are faster but resolves to approximations. Below, we compare two modifications with our algorithm.
[9] reduces time consumption from O(d 3 + d 2 m) to O(dm) by computing only ||µ 1 − µ 2 || 2 2 , omitting the trace term tr(Σ 1 + Σ 2 − 2 √ Σ 1 Σ 2 ). [7] incorporates the covariance matrices while retaining the O(dm) time complexity, by only using the diagonal entries of the covariance matrices. We emphasize that leaving out parts of the FID formula can introduce arbitrarily high levels of error. In comparison, our algorithm computes the exact FID in O(d 2 m) time. Even though our algorithm has a higher asymptotic time complexity, for m ≤ 128 it consumes no more than double the time of [7,9]. This is true because both algorithms compute Inception encodings which take more than half of the computation time.
Finally, [8] computes tr( √ Σ 1 Σ 2 ) by computing the eigenvalues of √ Σ 1 Σ 2 √ Σ 1 . This has the advantage that Σ 1 is symmetric so one can compute √ Σ 1 through its eigendecomposition. Such approach is not possible for Σ 1 Σ 2 which, in general, is not symmetric. The derivations of [8] have some similarities to our derivations, but they do not exploit small m and thus take O(d 3 + d 2 m) time.

Adversarial Examples
The Inception Distance (ID) [22] was widely used before the introduction of the FID. Previous work has successfully constructed adversarial examples against ID [2]. To the best of our knowledge, such adversarial examples have not been constructed for the FID. FastFID allows constructing such adversarial examples efficiently by simple gradient descent as presented in Section 5.

Conclusion
We introduced FastFID which computes FID fast when the number of "real" samples is large and the number of "fake" samples is small. Depending on the number of "fake" samples, FastFID is between 25 to 500 times faster than a previous implementations. FastFID can be extended to the Frechet ChemNet Distance, FastFCD, which is between 30 to 150 times faster than a previous implementation. The attained speed-up is useful when evaluating FID/FCD frequently during training. Finally, FastFID allow the construction of adversarial examples for FID by simple gradient descent.

Broader Impact
Potential Positive Impact. FastFID allow researchers to quantitavely test the training of generative models faster than previously possible. This is particularly useful for researchers with a constraint on their computational budget, e.g., a PhD student with a single GPU will benefit more than a industry lab with several GPUs. We hope this decreases the computational budget needed to perform experimental research for generative models.
Potential Negative Impact. FastFID allows one to efficiently cheat FID. This could make FID less reliable, since bad actors can use FastFID to train their generative model to make adversarial examples for FID. For example, a bad actor might first train a competitive generative model, then fine-tune the model to attain state of the art performance by directly minimizing FID.


Empirical Evaluation on the Impact of Class Overlap for EEG-Based Early Epileptic Seizure Detection

Important physiological information is hidden in electroencephalography (EEG), which can reflect the human brain’s activity. EEG, which is a kind of complicated signal, can be used for epileptic seizure detection and epilepsy diagnosis via machine learning. A large amount of effort, including raw signal preprocessing and data preprocessing for machine learning, is required for constructing high-quality training datasets because the classification performance highly depends on high-quality data. Feature extraction has been widely used in EEG-based early epileptic seizure detection. Due to the complexity of data collection and labeling, some of the training instances are inevitably mislabeled. That means some similar instances have different labels. This is called the issue of class overlap, which leads to a poor class boundary for classification models and makes constructing a high-quality classification model more difficult. However, the previous studies investigating the impact of the class overlap for EEG data is quite limited. Our goal is to investigate the impact of the class overlap on EEG-based early epileptic seizure detection. We propose a special neighborhood cleaning rule (SNCR) to solve the class overlap issue. To alleviate the class overlap issue, we conduct large-scale experiments on two widely-used EEG datasets and compare our proposed SNCR strategy with a state-of-the-art data clean strategy, i.e., the improved $k$ -means clustering cleaning approach (IKMCCA). The experimental results show that the classification model can achieve significantly better performance in terms of AUC, recall, and F1 metrics when using our proposed SNCR strategy. Therefore, for EEG-based early epileptic seizure detection, we recommend researchers to apply the SNCR strategy to mitigate the class overlap issue and use the SNCR strategy to perform data preprocessing in a future related study.

I. INTRODUCTION
Small metal discs (electrodes) are attached to the scalp to detect the brain's activity, which is called electroencephalography (EEG). This method has been widely used in clinical domain [1]. It can promote brain science research from the The associate editor coordinating the review of this manuscript and approving it for publication was Zhaojun Li . medical perspective by acquiring the mapping relationship between brain information and behavioral information. Due to the rapid development of the Internet of things (IoT) technology, EEG information can reflect the relationship between brain activity information and behavior information. Human brain cells communicate via electrical impulses and are active all the time, even during sleep. This activity shows up as wavy lines on an EEG recording, which can be collected using IoT. There are many related studies based on the EGG, including sleep pattern recognition and epilepsy [2]. An EEG is one of the main diagnostic tests for epilepsy. 1% of the world's population is affected by epilepsy, which can have multiple effects on the human body, such as memory loss, depression, and other psychological symptoms [3]. Epilepsy is associated with brain disorders and involves recurrent, unprovoked epileptic seizures resulting from the abnormal firing of cortical neurons, recruiting neighboring cells into a critical mass [4]. Therefore, it is necessary to detect epilepsy as early as possible and respond to changes in brain waves in advance to be able to provide medical care and assistance to patients on time to prevent malignant results.
The detection of epilepsy can start with brain waves, which are different from regular brain activity. A large number of methods based on pattern recognition can analyze and model the brain waves of patients from a statistical point of view to predicting possible epileptic seizures in advance. Many machine learning methods have been used to characterize the dynamic behavior of EEG signals, like the linear model [5], logistic model [6], Gaussian model [7], and deep learning [8]. Feature extraction has been widely studied in EEG-based early epileptic seizure detection. Some of the training instances are inevitably mislabeled due to the automatic data collecting method and a small sampling interval. There may be some similar instances with different labels, which is called the class overlap issue. High-quality data is required for constructing a high-quality classification model. However, the Class overlap issue has not been investigated in previous studies for EEG-based early epileptic seizure detection.
Similar instances may overlap densely in the space based on different features. The class overlap issue has been investigated in other application domains, such as software defect prediction [9]. That is to say, for EEG-based early epileptic seizure detection, different epilepsy seizures may have the same feature. The instances at the intersection of vector space cause the class overlap issue. These instances resent a serious challenge to the classification model of machine learning.
The class overlap issue can be solved by data preprocessing technology, and after cleaning the data, high-quality training data can be provided for the classification model. In the previous related studies, the class overlap has been investigated in many application areas, including credit card fraud [10], text classification [11], and software defect prediction [12]. Moreover, the class imbalance problem often accompanies the class overlap issue. The current commonly used strategies include the neighborhood cleaning rule learning (NCR), and the improved k-means clustering cleaning approach (IKM-CCA) [9]. The NCR method removes the conflicting majority instances to solve the class overlap issue, while the minority instances are not processed to achieve the balance between the majority class and the minority class [12]. The IKMCCA method is based on the standard k-means algorithm. For each cluster, the majority instances and the minority instances are eliminated according to the ratio between the minority instances and the majority instances [9].
In this paper, we propose a novel neighborhood cleaning rule (SNCR) strategy. This strategy is divided into three stages, considering data oversampling and NCR. The motivation for this strategy is that, intuitively, the EEG dataset has a large amount of data, and the problem of the class overlap is inevitable. Therefore, the class overlap is likely to exist for each seizure type.
In our empirical studies, we design the following two research questions (RQs): RQ1: How is the prediction performance affected by the class overlap problem of epilepsy seizures?
RQ2: Which classification model performs best on epilepsy seizures in terms of different performance measures?
To achieve an objective estimation of the class overlap issue, we conduct the experiments on two widely used EEG datasets and compare our proposed SNCR strategy with a state-of-the-art data clean strategy [9]. Performance evaluation measures (i.e., AUC, recall, and F1) are used to compare the performance of different strategies.
In this study, we aim to identify and remove overlapping instances and find a crosponding effective method for epilepsy seizures. In summary, the contributions of this paper can be summarized as follows: • To the best of our knowledge, we are the first to investigate the impact of the class overlap problem on epilepsy seizures.
• We are the first to investigate how the class overlap problem influences the prediction performance on epilepsy seizures.
• We are the first to propose our SNCR strategy for the class overlap problem on epilepsy seizures.
• Empirical results on two real-world datasets show the effectiveness of our proposed SNCR strategy.
The rest of this paper is organized as follows. Section II introduces the background of EEG and previous studies on the class overlap problem in machine learning. Section III describes the method in detail, including EEG data preprocessing and data cleaning strategies. Section IV reports our experimental setup, including experimental subjects, performance evaluation measures, strategies for experimental comparison, and experimental design. Section V discusses the results of our experiments. Section VI analyzes the potential threats to validity for our empirical results. Section VII concludes the paper with some future work.

II. BACKGROUND AND RELATED WORK
In this section, we mainly discuss the related studies on EEG-based early epileptic seizure detection and the class overlap issue.

A. ELECTROENCEPHALOGRAPHY
The brain-computer interface is a technology used to obtain information from the user's brain, control external designs, VOLUME 8, 2020 or communicate. The data can reflect the information or command that the user wants to send. The signal processing tool uses electrodes and other methods to identify the information or command and send it to the corresponding output device. The current four common brain-computer interfaces include EEG, electrocorticography, deep electrodes, and functional magnetic resonance imaging. EEG is a micro-current detection technology that detects the activity in the brain through the measurement of micro-currents. This technology is a non-invasive detection technology. Its implementation is equipped with contact electrodes on the scalp of the brain. Multiple electrodes record the patient's brain wave activity overtime on the scalp in many medical fields.
Currently, research on user intentions using EEG technology is still evolving and continuing. The creation of the user intention model contains three challenging issues. The first problem is how to effectively and reasonably map the user's emotional expression to the labeled state; the second problem is to perform signal denoising, transformation, and other preprocessing on the input data; finally, the third is manual data annotation of the EEG state [13]. The effect of preprocessing methods on downstream EEG has been researched. Although the general structure of the results is similar across these preprocessing methods, there are significant differences, particularly in the low-frequency spectral features and in the residuals left by blinks [14].
EEG-based early epileptic seizure always includes three key steps, as shown in Figure 1. Raw EEG data are first collected using IoT technology. In the first step, these instances are preprocessed, like data normalization. The second step is feature engineering so that the distinguishing features are selected. The third step is constructing the classification model using the preprocessed data. In the original EEG data, due to factors such as errors collected by the device, there may exist data noise and artifacts in the original dataset [15]. Although EEG data is used to record the brain's wave activity, it also records some other weak currents. These noise instances are called artifacts and must be preprocessed using two common techniques, including physiologic and extra physiologic artifacts cleaning technology.
For EEG-based early epileptic seizure classification, two popular methods have been used to preprocess EEG data from TUH EEG Seizure Corpus [16]. The fast Fourier transform (FFT) method has been used in the TUH dataset [17]. The FFT preprocessing technology for the TUH dataset is shown in Figure 2. For non-periodic signals, discrete Fourier transform based on discrete signals can meet the requirements of signal processing. However, only handle discrete and finite-length data can be handled, so here we use FFT in our study.
On all electrode channels, we trim the EEG data and sample every s seconds. Then, we use a log function with a base of 10 to process the data at different frequencies. The minimum processing frequency is 1HZ, and the highest is f (max)HZ (max means the max sample frequency). Finally, the data is entered into the model as raw data.

B. MACHINE LEARNING-BASED EEG ANALYSIS
With the rapid development of mobile devices, patient information can be collected efficiently and quickly. The status information of these patients can be sensed in real-time through the Internet of things technology and transmitted back to the Internet of things cloud platform. High-quality user data has laid a good foundation for the creation of a patient information management system. Machine learning technology has been successfully applied in many fields, including medical image recognition, cancer diagnosis, and so on. In recent years, there have been reports that the use of optimized machine learning techniques can divide EEG data into normal or abnormal data [17]. Using supervised learning to construct classification models for EEG data has recently played an increasingly important role in EEG diagnosis [18].
The diagnosis and treatment system based on humanmachine communication interface technology has been widely used at present. The treatment prediction technology for epilepsy has also been applied [19], and the EEG analysis technology for epilepsy has also been proposed. This new technology is highly innovative and applicable, and it is being accepted by more and more nerve brain scientists [20], [21].
For EEG-based early epileptic seizure detection, the development of miniaturized and standardized equipment has made the monitoring of patients' pre-seizure status more accurate. The automated epilepsy prediction system uses machine learning models to classify EEG data [22]. The classification model uses typical features to distinguish whether there is epilepsy or to predict epilepsy. The feature used in the machine learning model must have a very high degree of discrimination. This feature should be used not only for the status analysis of the same patient in a period but also for different patients' status analysis at different times. Therefore, effective feature engineering technology is essential for EEG-based early epileptic seizure detection.
So far, there has been a series of studies to detect seizures from EEG data. Zandi et al. [23] proposed wavelet-transform technology to distinguish seizure or non-seizure states using feature extraction preprocessing technology. Deep learning has been used in many fields because of its high performance. Vidyaratne et al. [24] used bidirectional recurrent neural networks to extract features for seizure analysis. Unsupervised learning in deep learning, such as autoencoders, has also been introduced to learn features from EEG data for seizure detection [25] automatically.

C. CLASS OVERLAP
The class overlap issue can be described as instances with the same characteristics but with different class labels. The existence of the class overlap issue makes it difficult for the classifier to effectively establish classification boundaries, which significantly affects classification performance, including accuracy, recall rate, and so on. In other fields of machine learning, such as software defect prediction, the class overlap issue is mainly related to the quality of the data or the noise in the samples [12]. Tang and Khoshgoftaar [26] used outlier removal technology to detect potential noise modules and improve data quality, and the experiment revealed that the total error rates decreased with decreasing noise examples. Chen et al. [12] proposed a new classification model for software defect prediction that combines class overlap reduction and ensemble imbalance learning. The neighbor cleaning method was first applied to remove the overlapping non-defective samples. The whole dataset was then randomly sampled several times to create an ensemble classification model. Gong et al. [9] proposed an improved k-means clustering cleaning approach (IKMCCA) to solve the class overlap issue and the class imbalance problem. The experiment revealed that it is better to consider both the class overlap problem and the class imbalance problem.
To our best knowledge, there is no consideration of class overlap for EEG data. Many instances from the TUH EEG Seizure Dataset are overlapping, as shown in Figure 3, which impact the prediction performance of the constructed models. EEG data comes from an automated data collection system. However, EEG data is subject to current interference from various sources, such as current interference from the collection system itself, abnormal current interference from the body itself, and errors that may occur during data transmission. Therefore, it is essential to perform an overlap analysis of EEG data. At the same time, there is an obvious kind of imbalance in the type of epilepsy. By using noise-cleaning techniques, it is also possible to achieve a balanced sampling of the dataset.

III. OUR PROPOSED METHOD
In this section, we briefly describe the EEG data preprocessing technology and then the whole experimental process, especially data cleaning strategies. Figure 4 provides an overview of the steps in our study. Based on an automated brain wave acquisition system, raw egg data is gathered, and FFT preprocessing is performed on the original dataset to obtain the training dataset. The popular classification models, including random forest (RF), naive Bayesian model (NB), logistic regression (LR), and k-nearest neighbor (KNN), are trained on the training set. Experimental results are gathered based on the test set in terms of AUC, recall, and F1 performance measures.

A. EEG DATA PREPROCESSING
The Fourier transform was firstly used for brain wave analysis in 1932. The successive development of classic analysis VOLUME 8, 2020 methods, such as time-domain analysis, frequency-domain analysis, and time-frequency analysis, has effectively promoted the study of brain wave signals [27]. Fast Fourier transform (FFT) can be used to analyze the frequency domain characteristics of the signal, and it is now one of the most popular methods to preprocess EEG data [17], [28].
Fourier transform is derived from the Fourier series by introducing a spectral density function. The calculation process can be defined as follows: where t is the time domain, and ω represents the frequency. However, FFT can only be used for the analysis of stationary signals. For non-stationary signals, a short-time Fourier transform (STFT) must be used to perform analysis. For non-stationary signals, the short-time Fourier transform strategy is to add a window to the signal, which is generally a hamming window. Of course, it can also be other types of window functions. The signal after windowing is divided into a set of short-length sequences, and subsequences can be viewed as stationary sequences, which can be analyzed by Fourier transform. The common method of EEG signal analysis using STFT is to use STFT to separate the bands of EEG signals, to obtain the energy of each band as a feature (such as alpha, beta, theta, gamma, and delta).

B. DATA CLEANING STRATEGIES
Since the class overlap issue exists in the EEG dataset, it is essential to preprocess the EEG data. In other fields, like software defect prediction, class overlap issue is often considered as the data quality or noise detection. In our experiment, the special neighborhood cleaning rule (SNCR) and improved kmeans clustering cleaning approach (IKMCCA) [9] methods have been used to remove the class overlap instances. Gong et al. [9] improved the k-means clustering cleaning approach for the class overlap issue. This innovative method uses the standard k-means algorithm on the training dataset to cluster the dataset, which is divided into k clusters.
For each cluster, they calculate the ratio of the number of defective modules to the number of non-defective modules. If the ratio is higher than the distribution value of the defective modules on the training dataset, they delete all non-defective modules; if the ratio is less than the distribution value of the defective modules on the training dataset, they remove all defective modules on the cluster. Finally, the processed dataset is merged into the final training dataset.
Considering the vast amount of EEG data and the high degree of the class overlap issue found from data visualization analysis, we conjecture that the class overlap problem exists in the current clusters. Therefore, we design a special neighborhood cleaning rule (SNCR). The pseudo-codes for the simulation experiments are provided in Algorithm 1 to evaluate the impact of the class overlap and then answer RQ1 and RQ2. The SNCR algorithm is shown in Algorithm 1.
The motivation for this strategy is that, intuitively, the EEG dataset has a large amount of data, and the problem of the class overlap is inevitable. The class overlap is likely to exist in each seizure type. Therefore, it is unreasonable to solve the problem of class imbalance by undersampling only for most classes. In this study, we think that oversampling should be used to make different types in the datasets to reach the class balance. Moreover, using oversampling can also likely to worsen the class overlap problem. SMOTE (Synthetic Minority Oversampling technique) [29] algorithm is used to create artificial instances of the minority class. An artificial instance of the minority class x i1 is based on the randomly selected x i , then another neighbor x i(nn) is chosen to calculate the distance between x i and x i(nn) . A randomly selected parameter δ is used to guarantee the randomness.
At this time, the nearest neighbor learning is performed on the current majority class and minority class at the same time, and potential class overlap instances are eliminated. Since the amount of EEG data is relatively large and uses the above nearest neighbor method to find possible class

Algorithm 1 Special Neighborhood Cleaning Rule (SNCR)
Input: training set T = C max , C min , where C max is the majority class, C min is the minority class, and d is the ratio r of defective instances to all instances. Output: a new cleaned training set T = {C max , C min } 1 for data in C min do 2 Choose k neighbors using Euclidean distance; overlap instances, we can also analyze the current dataset by introducing standard k-means algorithms, then we perform cluster analysis on the dataset and remove the abnormal instances in each cluster. In the k-means algorithm, the distance between each object and the cluster center is calculated using Euclidean distance.
For a fair comparison, we set the No Clean strategy as the default data cleaning strategy in our study.

IV. EXPERIMENTAL SETUP
In this section, we first provide the motivation for our research questions. Then, before answering this question, we introduce the experiment setup, including experimental subjects, performance evaluation measures, strategies for experimental comparison, comparative classifications based on machine learning, and experimental design.

A. RESEARCH QUESTIONS
Our study is to evaluate the effect of the overlapping instances on EEG epilepsy seizures. To achieve this research goal, we seek to answer the following two questions: RQ1: How is the prediction performance affected by the class overlap problem of epilepsy seizures?
RQ2: Which classification model performs best on epilepsy seizures in terms of different performance measures? RQ1 and RQ2 aim to compare the performance of the existing state-of-the-art learning models by removing overlapping instances in the epilepsy seizure datasets. We studied popular classification models for epilepsy seizures datasets. If the class overlap instance is removed and the classifier's performance is improved, then practitioners can perform corresponding preprocessing on the original EGG data to improve the classifier's performance in future studies on the epilepsy seizures. Besides, by comparing the classifier's performance, it also helps to guide subsequent researchers to choose a classification model suitable for their use.

B. EXPERIMENTAL SUBJECTS
To compare these data clean strategies, we used two publicly available datasets.
The first dataset is the world's largest publicly available dataset of epilepsy seizures, which is published and maintained by Temple University Hospital. We chose the sub-dataset of the TUH EEG Seizure Corpus as our research object. These EEG records are sampled at a frequency of 250 Hz and contain up to 20 electrode channels. The TUH EEG Seizure Corpus contains 2,012 seizure cases, which contain eight different types of epilepsy. Seizure of different patients may be classified into the unified command seizure type. For seizure type classification experiments, we exclude only myoclonic seizures because of the small number of seizures recorded (three seizure events). The seven types of seizure selected for analysis are focal non-specific seizures (FNSZ), generalized non-specific seizures (GNSZ), simple partial seizures (SPSZ), complex partial seizures (CPSZ), absence seizures (ABSZ), tonic seizures (TNSZ), and tonic clonic seizures (TCSZ) [30]. Clinically SPSZ and CPSZ are more specific subclasses of FNSZ, while ABSZ, TNSZ, and TCSZ are more specific subclasses of GNSZ. ABSZ and SPSZ seizure samples are selected respectively to represent one seizure type to test the three strategies.
After preprocessing the EEG dataset for the TUH EEG Seizure Corpus, there are almost 60,000 instances. There are 3,087 instances for the ABSZ seizure type, labeled as ''1''; meanwhile, there are 6,028 instances for the SPSZ seizure type, labeled as ''0''. The ratio of the majority instances to the minority instances is about 1.95. There are 3,087 samples in the original absence seizure (ABSZ) group, and there are 6,028 samples in the original simple partial seizure (SPSZ) group. Thus, there is a clear class imbalance problem. To better test the impact of the class overlap issue on the dataset and cleaning strategy, some noise data was artificially added to the selected data.
The IBM TUSZ preprocessed dataset is inputted into the classification model as the original EEG. For this dataset, the temporal central parasagittal montage preprocessing was performed on 20 electrode channels, and fixed-length windows were used for FFT on all channels. The format of the input dataset is [#data sample, #channels, #frequency bands]. The second dataset is another publicly available dataset of epilepsy seizures. The dataset is available on UCI's machine learning repository [31]. The dataset includes 4,097 EEG readings per patient over 23.5 seconds, with 500 patients in total [32].
In the epilepsy seizures dataset on UCI's machine learning repository, there is a total of 11,500 instances, in which there are 2,300 epilepsy seizure instances labeled as ''1''. The remaining instances are labeled as ''0''. Therefore, this dataset also contains a class imbalance problem.

C. PERFORMANCE EVALUATION MEASURES
To investigate the impact of the class overlap on the performance of the constructed models, we consider three performance measures: the area under the receiver operating characteristic curve (AUC), recall, and F1-measure (F1). In Table 1, we can find that there is a significant class imbalance in TUSZ datasets. Due to the imbalance distribution, multiple performance measures are usually adopted to evaluate different aspects of constructed prediction models. We measure the performance with F1-measure and AUC, which have been widely used for the class imbalanced datasets. For a binary classification problem, an unambiguous way to present the prediction results of a constructed classifier is to use a confusion matrix.
AUC is defined as the area enclosed by the ROC curve and the coordinate axis. The maximum value cannot exceed 1. The closer the AUC value is to 1, the higher the authenticity of the classifier detection. Conversely, when it is close to the minimum value of 0.5, it represents that there is no application value. F1 is the harmonic mean of precision and recall, and this performance measure can solve the trade-off between precision and recall.
To statistically evaluate the detailed prediction results, we first employ the Friedman test to determine whether there are statistically significant differences among compared methods. If there is a statistically significant difference, the post-hoc Nemenyi test is applied to compare the difference.
When the null hypothesis is rejected, the average rank should be calculated and is compared with the critical distance (CD).
In our experiment, k represents 12 different algorithms, and N represents all 20 training datasets. q a is defined as 3.2. Therefore, the result of CD is 2.5799.
In addition, to evaluate the degree of difference among the compared methods in terms of AUC, recall, and F1-measure, we apply Cohen's d to measure the effect size.

D. STRATEGIES FOR EXPERIMENTAL COMPARISON
To compare the classification performance of the impact of class overlaps on EEG-based early epileptic seizure detection, the special neighborhood cleaning rule (SNCR) strategy is compared with the improved k-means clustering cleaning approach (IKMCCA) strategy. For the sake of fairness, the two strategies for data preprocessing are compared using the case without data preprocessing. This strategy is named the No Clean Strategy.

E. MODELING METHODS
In our experiments, three preprocessing strategies were evaluated and compared with four state-of-art classification algorithms. The details of the models are introduced as follows: RF. Random forest (RF) is a common classification model that has been widely used in many machine learning fields. This is an integrated learning classification model, which creates a series of decision trees by randomly dividing data and uses the voting results of the decision tree for classification. This model has a strong processing capacity for imbalanced datasets. NB. The naive Bayesian model (NB) is a simple but robust classification model. This model is based on the Bayesian principle and has been proven to have better classification results than complex models in multiple application areas, such as support vector machine models.
LR. Logistic regression (LR) is a variant of the regression method that is essentially a linear classifier. This model has strong interpretability, and the fitted parameters can represent the impact of each feature on the result.
KNN. The k-nearest neighbor (KNN) algorithm is relatively mature in theory. It considers the k nearest samples to a certain example, and the voting result of most examples determines the example category.

F. EXPERIMENTAL DESIGN
To evaluate the model performance of different query strategies, we first divide the preprocessed dataset into m groups and then use random stratified sampling to generate the instances training set and test set.
The experiment is performed m times (m = 10). In our experiments, we use the implementation of these classifiers provided by scikit-learn to avoid internal threats to validity and use the default value for the classifier's hyperparameters. The pseudo-code for the experimental setup is shown in Algorithm 2. In this section, we report experimental results for the comparison with and without removing the overlapping instances to answer RQ1 and RQ2.

RQ1: How is the prediction performance affected by the class overlap problem of epilepsy seizures?
To answer this RQ, we conduct the experiments on the two EEG seizure datasets via RF, NB, LR, and KNN classifiers by using the SNCR, IKMCCA, and No Clean strategies. In the IKMCCA method, the ratio p% is set to the ratio of the VOLUME 8, 2020  number of instances in the minority class to the number of instances in the majority class.
The comparison results via violin plot are shown for each learning model in Figure 5 to Figure 7. From these figures, we can observe that using the SNCR strategy can achieve the best performance (i.e., median value) in terms of AUC, recall, and F1-measure on the RF, NB, LR, and KNN classifiers. In particular, (1) compared with the No Clean strategy, it is better to solve the class overlap problem by using the cleaning strategies, and (2) compared with IKMCCA, the SNCR method performs better in the two epilepsy seizures datasets.
The graphic display of comparison results in terms of different performance measures does not clearly show the differences between different strategies. Then, to compare the performance of different strategies on the difference training datasets from a statistical point of view, the non-parametric Friedman test at a confidence level of 95% is used to conduct a statistical analysis of the results. Firstly, we define the null hypotheses (H0) and alternative hypotheses (H1) as follows: H0: There is no difference between the strategies on the different datasets.
H1: There is a difference between the strategies on the different datasets.
Secondly, we set the significance level α to 0.05. Then, we find that the calculated value is smaller than the critical value for a 0.05 significance level. Hence, the null hypothesis is rejected and we can conclude that there is a difference between these three strategies.
To reveal the differences between different strategies, we further adopt a post hoc statistical analysis method. The mean ranks results of 12 approaches in terms of AUC, recall, and F1 are shown in Table 3.
In the end, to further compare these strategies, we compared the effect size of the No Clean strategy with those of the other two strategies. Cohen's d effect size is used, and the final results are shown in Table 4.
Summary for RQ1: We can find a statistically significant performance improvement after removing the overlapping instances. Therefore, removing the overlapping instances before building the EEG-based early epileptic seizure detection prediction models is needed. Moreover, SNCR can achieve better results than IKMCCA for all the classifiers. Therefore, we recommend SNCR to consider the class overlap problem when dealing with EEG-based early epileptic seizures.

RQ2: Which classification model performs best on epilepsy seizures in terms of different performance measures?
According to the violin plots of Figure 5 to Figure 7 and Cohn's d effect size in Table 4, the SNCR strategy can better deal with the class overlap issue. Then, to answer which classifier has the best classification performance when using the SNCR strategy, we select some of the previous experiments by only focusing on the SNCR strategy in terms of AUC, recall, and F1 for different classifiers (i.e., RF, NB, LG, and KNN). We want to further reveal which of the four classifiers has strong generalization ability and robustness when dealing with the class overlap issue, which is a valuable and meaningful exploration, which can guide other researchers to use a more robust classifier in future studies.
Firstly, we use the violin plots of different classifiers according to the experimental results in terms of different evaluation measures. The violin plots on the SNCR strategy in terms of AUC, recall, and F1 measures are shown in Figure 8.   According to Figure 8, the NB classifier performs better than other classifiers based on the median value.
Secondly, the non-parametric Friedman test with post-hoc Nemenyi test at a confidence level of 95% is used to conduct a statistical analysis of the results. We can find that there is a difference between different classifiers.
In this scenario, the count of all the training datasets is 20, and the count of compared algorithms is 4. The q a is queried, and q a = 2.569. The CD is defined as 0.7416 according to Equation (5). The mean ranks results of the four classifiers in terms of AUC, recall, and F1 are shown in Table 5.
In addition, to perform a thorough comparison of the four algorithms, we compare the effect size on the 20 training sets, and the results are shown in Table 6. Summary for RQ2: After investigating which classifier performs best on EEG-based early epileptic seizure detection datasets for SNCR, we can find a statistically significant improvement in favor of the NB classifier. Therefore, we recommend the NB classifier to build the EEG-based early epileptic seizure detection prediction models in the future.

VI. THREATS TO VALIDITY
In this section, we mainly discuss potential threats to the validity of our empirical study.

A. THREATS TO CONSTRUCT VALIDITY
Only two open datasets are evaluated in our empirical studies. However, the first dataset is the world's largest publicly-available dataset of epilepsy seizures, and the representativeness of our findings can be guaranteed. The second dataset is downloaded from UCI's machine learning repository. This dataset is preprocessed, and its instances have not been transformed by using FFT.

B. THREATS TO INTERNAL VALIDITY
We do not choose all the classification models, which have been considered in the previous studies for EEG-based early epileptic seizure detection. To alleviate this threat, we only choose some representative classification models in our empirical study.

C. THREATS TO EXTERNAL VALIDITY
The two datasets used in our study are free and open datasets. Other commercial and private datasets have not been considered because of intellectual property issues. This may threaten the generalization of our empirical studies.

VII. CONCLUSION AND FUTURE WORK
EEG-based early epileptic seizure detection prediction relies on a large amount of labeled data; classifiers are used to construct models to achieve early detection of an epileptic seizure. However, in actual work, due to the many interference factors encountered in the EEG data collection process, data label errors are inevitable. Some instances have the same measured value but have different seizure types. This kind of error is called the class overlap issue. From the perspective of resolving the class imbalance problem and the class overlap problem, we propose a novel SNCR strategy. Then, we designed experiments to investigate whether using this strategy to solve class overlap can improve the classifier's performance. We conduct the empirical studies to compare the performance using different models on two open datasets. The results show that the SNCR strategy can achieve significantly better performance in terms of AUC, recall, and F1. In other words, the class overlap issue has a performance impact on prediction; it also shows that when removing the class overlap instance, strategies such as oversampling should be considered to solve the class imbalance problem.
This strategy can be used in other application domains, such as software defect predictions, to solve the class imbalance problem [33]. Also, for cross-project software defect prediction, the class imbalance problem can be solved using this SNCR strategy [34], [35]. Finally, the features of EEG data in our study are constructed based on feature engineering in a manual way. In contrast, deep learning can automatically learn semantic features. Then analyzing the impact of the class overlap problem on the leaned semantic features is another interesting problem and can be investigated in our future work.


The Big-M method with the numerical inﬁnite M

Linear programming is a very well known and deeply applied ﬁeld of optimization theory. One of its most famous and used algorithms is the so called Simplex algorithm, independently proposed by Kantoroviˇc and Dantzig, between the end of the 30s and the end of the 40s. Even if extremely powerful, the Simplex algorithm suffers of one initialization issue: its starting point must be a feasible basic solution of the problem to solve. To overcome it, two approaches may be used: the two-phases method and the Big-M method, both presenting positive and negative aspects. In this work we aim to propose a non-Archimedean and non-parametric variant of the Big-M method, able to overcome the drawbacks of its classical counterpart (mainly, the difﬁculty in setting the right value for the constant M ). We realized such extension by means of the novel computational methodology proposed by Sergeyev, known as Grossone Methodology . We have validated the new algorithm by testing it on three linear programming problems.

Introduction
Linear Programming (LP) is a branch of optimization theory which studies the minimization (or maximization) of a linear objective function, subject to linear equality and/or linear inequality constraints. LP has found a lot of successful applications both in theoretical and real world contexts, especially in countless engineering applications. Most of the algorithms developed so far to solve LP problems fall in one of the two following categories: basis exchange methods [19] and interior point methods [27].
Researchers argued a lot about the pros and the cons of these approaches, ending up asserting the equal dignity of both. The best choice depends on the characteristics of the problem at hand [16].
Concerning this work, we decided to focus on the class of basis exchange methods and, in particular, on its probably most famous member: the Simplex algorithm, firstly proposed in 1939 by Kantorovič [17] and independently rediscovered by Dantzig during the forties [8][9][10].
This algorithm needs a feasible basic solution to start from, an input which is not trivial to generate for complex real-world problems. The main ways to overcome this difficulty are: the two-phases approach [10] and the Big-M method [2,8,26].
The former splits the optimization in two-phases, and in each it runs the Simplex algorithm on a phase-specific problem. In the first one, the problem is a simple task for which a feasible starting point is known, and whose optimum is a valid basic solution for the original problem. The second one is the original problem itself. In spite of the guarantee of convergence to the optimum (if it exists), such approach wastes a lot of time, having to run the Simplex algorithm twice rather than once.
The other possibility is diametrically opposed to the previous one, indeed, it requires just one run of the Simplex algorithm, though on a problem different from the original one. The latter approach is known as Big-M method, since it requires a big parameter M: it consists of applying the Simplex algorithm to a modified and parametrized version of the original problem for which a feasible initial basic solution is known. In particular, the big constant M (along with some auxiliary variables) is added to the original problem; a good tuning of such constant also guarantees that the original problem and the modified one share the same optimum. Thus, the drawback of the Big-M method is that it adds a new parameter, which also needs to be properly set: a too small value does not guarantee the convergence to the same optimum of the original problem, while a too big value may generate loss of precision and numerical instabilities.
The actual goal of this work is to overcome the Big-M method issues by means of a non-Archimedean modification of the original method, that is converting the LP problem at hand into a new one where the cost function involves infinite and infinitesimal quantities too. In order to realize such non-Archimedean extension, we exploited the Grossone Methodology proposed by Y.D. Sergeyev (see [22] and references therein), a powerful framework which lets one numerically manipulate infinite and infinitesimal quantities. Even more interestingly, algorithms involving the Grossone Methodology can run on a hardware computing engine, called Infinity Computer (see patent [20]), which is a completely new kind of supercomputer. Once opportunely modified, the new problem can be solved by a recent extension of the Simplex algorithm due to Cococcioni et al. [4], namely the gross-Simplex algorithm (in brief, G-Simplex). The latter is an improved Simplex algorithm able to solve non-Archimedean LP problems too. Together, the G-Simplex algorithm and the non-Archimedean modified problem give birth to the parameter-less procedure presented in this work, called by us the Infinitely-Big-M method (abbreviated I-Big-M), since it relies on the use of an infinitely big constant, which is the same for all the problems and thus does not have to be specified by the user.
The remaining of the letter is structured as follows: Sect. 2 provides an introduction to LP and Big-M method, Sect. 3 contains an overview of the Grossone Methodology and a description of the Gross-Simplex algorithm, Sect. 4 presents our non-Archimedean extension of the Big-M method, i.e., the Infinitely-Big-M method. In Sect. 5 we present three experiments we conducted exploiting the I-Big-M method to solve LP problems, while Sect. 6 is devoted to the conclusions.

The linear programming problems and the Big-M method
A possible representation of an LP problem, which may be a little complex at first sight, is shown in Eq. (1): where z ∈ R n z + is the unknowns vector, d ∈ R n z is the cost vector, i ∈ R m i ×n and b i ∈ R m i + are the feasibility constraints, i = le, eq, ge. Here and throughout the whole work, bold symbols represent vectors and matrices, while non-bold ones refer to scalars.
As said, the Simplex algorithm requires a feasible basic solution to start from which may not be easy to find by hand. The Big-M method [2,8,26] tackles the problem transforming the original problem by adding some auxiliary variables which guarantee the existence of an initial feasible basic solution. However, not being part of the original problem, all of them must be equal to zero in the optimal solution of the modified problem. In order to guide the optimizer towards this annihilation, the Big-M method adds the auxiliary variables to the cost function and weights them with a big penalty M. The form of the modified problem is shown in Eq. (2): where a ∈ R n a is the vector of auxiliary variables to be penalized (n a = m eq + m ge ), M is the penalty weight, 1 is a vector of n a ones, s and p are m le and m ge slack variables, respectively. Such new form can be easily turned into the standard one (3), by applying the equalities shown in Eq. (4): The always feasible initial basic solution for the modified problem is {s, e, r}.
However, the Big-M method has a couple of relevant drawbacks. Actually, it turns a parameter-less problem into a parametric one, adding the scalar factor M. In addition, such parameter needs to be a-priory carefully set, in order to guarantee the correctness of the optimization process. Indeed, a too low value could lead to a non-zeroing of the auxiliary variables (and, thus, to no feasible solutions, even if they exist), a too high value could lead to a loss of precision and to numerical instabilities. Such setting issues, along with the need of re-tuning M for each different problem to solve, are crucial and struggling aspects from a practical point of view, sometimes limiting the applicability of the method in real contexts at all. In Sect. 4, we will present our parameter-free extension of the Big-M method which also preserves all its positive properties. With this goal in mind, let us move to the next section which introduces the methodological platform upon which to build such extension.

The Grossone methodology and the G-simplex algorithm
The Grossone Methodology (GM), which has been proved to stay apart from non-Standard Analysis [23], is a novel way for dealing with infinite, finite and infinitesimal numbers at once and in a numerical way [22]. Originally proposed in 2003, such framework already counts a lot of practical applications, for example it has been applied to non-linear optimization [11,18], global optimization [25], ordinary differential equations [1,15,21,24], control theory [3,12], and game theory [13,14], to cite a few. Also linear optimization positively enjoyed the advent of GM, as shown in [4][5][6][7]. In particular, in [4,6] the authors proposed an extension of the Simplex algorithm able to address Lexicographic Multi-Objective LP problems, both in absence and in presence of integer constraints, using a simplex-like approach. Such extension has been called gross-Simplex algorithm (briefly, G-Simplex), since it adopts GM to make the optimizer aware of the lexicographic priority between the objectives.
Actually, GM relates to the infinite unit Grossone, which is represented by the numeral ①. By means of it, a new numeral system with infinite base can be carried out, and each numberc within such numeral system can be represented as follows: In Eq. (5) the numberc is called gross-scalar (in short, G-scalar), m, k ∈ N, each p i is called gross-power (G-power) and can be of the same form ofc, while c p i is called gross-digit (G-digit) and is a finite (positive or negative) real number, i = m, . . . , −k.
As mentioned, the G-Simplex is an algorithm which extends the Simplex procedure, being also able to solve the new class of LP problems known as non-Archimedean LP (NA-LP) problems. The latter have the canonical form described by Eq. (6): where this time the cost vectorc is a vector of non-Archimedean quantities, that is infinite and infinitesimal values, rather than just real numbers as in Eq. (3). In this work, we modeledc by means of a gross-vector (G-vector), i.e., an n-dimensional vector whose entries are G-scalars. In [4], it has been proved that a NA-LP problem is equivalent to the optimization of multiple linear functions among which a lexicographic priority relation exists, i.e., the problem expressed in Eq. (7) (l is the number of functions to optimize at the same time).

The Infinitely-Big-M method
The main issues related to the Big-M method concern the weight M. As said, it needs an a-priori careful settings because a too low value may not force the Simplex algorithm to nil the auxiliary variables, and a too big value may bring to loss of precision and numerical instabilities. Moreover, the weight needs to be opportunely tuned for each different LP problem, which means the task to solve is no more a parameter-less but a parametric one. Notwithstanding, the role of the weight M is just to prioritize the zeroing of the auxiliary variables over the optimization of d T z, regardless its actual value. Indeed, it has just to put as much emphasis as possible on their minimization (reads to prioritize them), since a solution with at least one nonzero auxiliary variable is actually a non-feasible output for the original problem. Such priority lets us reformulate the modified problem into a non-Archimedean version.
The idea is to set the weight M equal to ①, in line with what De Cosmis and De Leone did in Nonlinear Programming [7]. Indeed, M represents a very big number which aims to increase the importance of the auxiliary variables zeroing over the minimization of d T z. The canonical form of such modified problem is shown in Eq. (8).
s.t. le z + Is = b le eq z + Ie = b eq ge z + Ir − Ip = b ge z, s, e, p, r ≥ 0 (8) Imposing the equalities in Eq. (4) (except for the vector c) and the ones in Eq. (9), the problem gets a form close to Eq. (7). Scaling down its cost function by a factor ①, it ens up fitting it perfectly. This means that such a problem can be solved by means of the G-Simplex algorithm. Indeed, as stated in Sect. 3, there always exists a bijection between a problem in the form of Eq. (7) and one in the form of Eq. (6). With regard to the Big-M method we aim to present in this letter, such bijection corresponds to Eq. (10).
Together, the rewriting of the modified problem into its non-Archimedean form and the use of the G-Simplex algorithm to solve it, implement the extended version of the Big-M method we sought to propose in this work. The latter is a procedure which leverages on an infinitely big constant to properly guide the optimization, which is the reason why we called it Infinitely-Big-M (in brief, I-Big-M). Notice that the I-Big-M method is a parameter-less approach, indeed, it does not require anymore the tuning of M, which is now always set to ①, regardless the problem to solve. Moreover, the issue of finding a feasible initial basic solution for the G-Simplex algorithm does not exist, since the modified problem and its non-Archimedean version are two different ways for representing the very same problem. What changes is only how to guide the optimization process, that is the loss function, while the polytope describing the feasible region stays the same. This means that a feasible initial basic solution for the Simplex algorithm in the modified problem is also a polytope vertex for the G-Simplex. Thus, Big-M and a I-Big-M methods share both their starting and optimal points (to be precise, the latter is true only if the weight M is correctly set in the Big-M method). Finally, it is worth to highlight how the I-Big-M method is able to tackle lexicographic multi-objective LP problems straightforwardly and without any modification to the method itself. Indeed, on the one hand the problem modification remains the same, this time with more than just one secondary vector. On the other hand, the G-Simplex algorithm is able to solve NA-LP problems regardless the number of objectives to deal with. Thus, the I-Big-M method, which is the combination of the problem modification and the G-Simplex algorithm, does not care whether the original problem to solve is lexicographic multi-objective or just single-objective. Numerical evidences of such property will be shown in Sect. 5.2.

A numerical illustration
In this section we show three practical cases of study where we can appreciate the effectiveness of the I-Big-M algorithm.

First case of study
The first analysed problem is a slight variant of Example 1 provided in [4]. Our variant takes into account only the first objective of that benchmark, which is actually a lexicographic multi-objective problem.
In order to involve an equality constraint, we have also introduced the additional variable z 3 , which plays a very marginal role in the economy of the problem. The analytical form of the current case of study is shown below, while its graphical description is reported in Fig. 1 (after being projected onto the plane z 3 = 10).
For completeness, below we also report the matrices i and the vectors b i by means of which we can represent the current LP problem in the form of Eq. (1), i = le, eq, ge : The problem's optimum is degenerate: any point within the red segment of Fig. 1 is optimal. We have indicated as α = [0, 70, 10] and β = [30, 50, 10] the two vertices of the optimal segment. In Table 1, we reported the iterations that the G-Simplex algorithm performed once run on our Infinity Computer simulator implemented in Matlab. As it can be seen from the table, the G-Simplex algorithm immediately gets rid of the auxiliary variables. Indeed, in the very first iteration the auxiliary variable r exits from the base, followed by variable e during the second iteration (in this case vectors r and e are actually scalars). This is confirmed by the cost function, which assumes a finite value in exactly two steps. Thus, the infinite weight ① does its own duty, that is prioritize the zeroing of the auxiliary variables during the solution of  the problem, which manifests in the auxiliary variables exiting from the optimal base before all the other unknowns. Finally, the optimum output by the routine was z * = α.

Second case of study
The aim of this second case of study is to numerically verify that the I-Big-M method is able to tackle the lexicographic multi-objective optimization transparently with respect to the user and the problem modification procedure. To do it, we run the I-Big-M routine on the problem presented in Eq. (12) and graphically described in Fig. 2. The new problem is the same as before with the addition of two new linear cost functions. The three overall cost vectors are reported in Eq. (13), and they can be lexicographically ordered by priority as follows: d d 2 d 3 . We avoided to report the problem splittings in matrices i and vectors b i (i = le, eq, ge), since the splitting is exactly the same already reported in Eq. (11): Some aspects of the problem are worth to be pointed out. Actually, the optimum of the new problem is now the point β, as higlighted by Fig. 2. Indeed, while for the first objective (d) the problem solution is degenerate (both α and β are acceptable), the function d 2 lets us discriminate between them. Thus, while before the choice between them was delegated to the G-Simplex algorithm actual implementation, now it is guided by the second objective function and it falls upon β. The third and least optimality direction, i.e., d 3 plays no role, since the optimum is just a singleton this time.
Finally, in Table 2 we reported the iterations performed by the G-Simplex algorithm when solving the lexicographic multi-objective LP problem in Eq. (12). Notice that the first four iterations of the algorithm are exactly the same reported in Table 1. The reason behind this phenomenon is twofold. Firstly, the G-Simplex solves both the problems (this and the previous one) from the very same initial basic solution {s, e, a}, chosen by the I-Big-M method. Secondly, the optimization is guided by the objective d until the degenerate solution is found. Together, this two aspects make reasonable to expect that the G-Simplex algorithm will follow the same steps in both the problems until it finds the degenerate solution. At that point, the first objective is not able anymore to discriminate among the solutions, and therefore the second objective turns to be effective, leading the algorithm towards the unique lexicographic solution of the problem β.
Before concluding, in Eq. (14) we report the non-Archimedean objective function of the modified NA-LP problem generated by the I-Big-M method. Such function lets us write such problem in the form of Eq. (6):

Third case of study
We now illustrate a third case of study where the traditional Big-M method struggles, because setting the right value for M is not trivial. We have considered the problem neos-1425699, which can be downloaded from: https://miplib.zib.de/instance_ details_neos-1425699.html The problem is included within the MIPLIB2017 collection of Mixed Integer LP benchmarks, and it contains 63 inequality constraints and 26 equality constraints. Of course, we have removed the integrality constraint from all the 105 variables, and we have also removed their upper bounds. As it can be seen from Table 3, the known optimal value of the cost function is 3.14867 · 10 9 (found using Matlab linprog function). Using values for M below 10 8 the standard Big-M algorithm is not able to find the right optimum, as proved by a different value of the cost function. Also the number of iterations performed by the Big-M method is interesting: it passes from 26 to 89 (see the third column of Table 3). Needless to say, on the same problem the I-Big-M method is able to find the optimum at the first attempt, i.e., without any trialand-error approach. Thus, we think that the I-Big-M method can be a powerful method in those setting which require the solution of LP problems as a sub-problem, like in the case of Mixed Integer Linear Programming when approached using a Branch-and-Bound/Branch-and-Cut strategy, both for the single objective and the lexicographic multiple-objective cases [6].

Conclusions
In this letter we have introduced a new algorithm, called I-Big-M method, which is a re-visitation of the Big-M method for the Infinity Computer. The I-Big-M method is able to solve a LP problem using only one run of the G-Simplex algorithm, in the very same manner of the classical Big-M method, which uses a single run of the classical Simplex algorithm. Even more interesting, the I-Big-M method does not require the constant M, a parameter difficult to set, typically chosen by an errorprone trial-and-error approach. Hence, the I-Big-M offers a parameter-less algorithm to solve LP problems, generating a single sequence of visited vertices. Moreover, its formulation also allows one to solve lexicographic multi-objective LP problems in a natural way, again without any assistance by the user and solving the problem using just a single run of the G-Simplex algorithm (i.e., by generating overall a single sequence of visited vertices: a pretty remarkable result). All these properties have been numerically validated by means of three experiments, one of which involving a realworld challenging benchmark. Finally, the I-Big-M method is expected to be more numerically stable than the original Big-M method, since it does not mix numbers with very different order of magnitudes. The verification of the latter conjecture deserves a deeper investigation and it is left to a future study.