• Performance guarantees for rule-based classification models. • Novel score function accounting for rule overlaps via geometrical rule similarity. • Conformal prediction-guided tuning of rules via conformal critical set. Computer scientists consider an artificial intelligence system safe and trustworthy if it fulfills four pillars: robustness, transparency, fairness, and privacy. We propose a fifth fundamental aspect: conformal guarantee, that is, the probabilistic assurance that the system will behave as expected. We introduce CONFIDERAI (Conformal Interpretable by Design Explainable and Reliable Artificial Intelligence), a new score function for binary rule-based classifiers depending on both rules’ performance and geometry; the latter includes both the position of points within rule boundaries and rule overlaps, these being quantified via geometrical rule similarity. Furthermore, we address the problem of individuating regions in the feature space in which conformal guarantees are satisfied, by defining the concept of conformal critical set (CCS). The overall method is tested with promising results, comparable in efficiency to traditional scores, on ten datasets of real-world interest, such as domain name server tunneling detection and cardiovascular disease prediction. Moreover, newly generated rules from CCS resulted into an improved precision and reduced error on a target class, thus avoiding prediction failures in safety-critical contexts.

BACKGROUND: Logic Learning Machine (LLM) is an innovative method of supervised analysis capable of constructing models based on simple and intelligible rules. In this investigation the performance of LLM in classifying patients with cancer was evaluated using a set of eight publicly available gene expression databases for cancer diagnosis. LLM accuracy was assessed by summary ROC curve (sROC) analysis and estimated by the area under an sROC curve (sAUC). Its performance was compared in cross validation with that of standard supervised methods, namely: decision tree, artificial neural network, support vector machine (SVM) and k-nearest neighbor classifier. RESULTS: LLM showed an excellent accuracy (sAUC = 0.99, 95%CI: 0.98-1.0) and outperformed any other method except SVM. CONCLUSIONS: LLM is a new powerful tool for the analysis of gene expression data for cancer diagnosis. Simple rules generated by LLM could contribute to a better understanding of cancer biology, potentially addressing therapeutic approaches.

BACKGROUND: Tumour markers are standard tools for the differential diagnosis of cancer. However, the occurrence of nonspecific symptoms and different malignancies involving the same cancer site may lead to a high proportion of misclassifications. Classification accuracy can be improved by combining information from different markers using standard data mining techniques, like Decision Tree (DT), Artificial Neural Network (ANN), and k-Nearest Neighbour (KNN) classifier. Unfortunately, each method suffers from some unavoidable limitations. DT, in general, tends to show a low classification performance, whereas ANN and KNN produce a "black-box" classification that does not provide biological information useful for clinical purposes. METHODS: Logic Learning Machine (LLM) is an innovative method of supervised data analysis capable of building classifiers described by a set of intelligible rules including simple conditions in their antecedent part. It is essentially an efficient implementation of the Switching Neural Network model and reaches excellent classification accuracy while keeping low the computational demand. LLM was applied to data from a consecutive cohort of 169 patients admitted for diagnosis to two pulmonary departments in Northern Italy from 2009 to 2011. Patients included 52 malignant pleural mesotheliomas (MPM), 62 pleural metastases (MTX) from other tumours and 55 benign diseases (BD) associated with pleurisies. Concentration of three tumour markers (CEA, CYFRA 21-1 and SMRP) was measured in the pleural fluid of each patient and a cytological examination was also carried out. The performance of LLM and that of three competing methods (DT, KNN and ANN) was assessed by leave-one-out cross-validation. RESULTS: LLM outperformed all other considered methods. Global accuracy was 77.5% for LLM, 72.8% for DT, 54.4% for KNN, and 63.9% for ANN, respectively. In more details, LLM correctly classified 79% of MPM, 66% of MTX and 89% of BD. The corresponding figures for DT were: MPM = 83%, MTX = 55% and BD = 84%; for KNN: MPM = 58%, MTX = 45%, BD = 62%; for ANN: MPM = 71%, MTX = 47%, BD = 76%. Finally, LLM provided classification rules in a very good agreement with a priori knowledge about the biological role of the considered tumour markers. CONCLUSIONS: LLM is a new flexible tool potentially useful for the differential diagnosis of pleural mesothelioma.

BACKGROUND: Cancer patient's outcome is written, in part, in the gene expression profile of the tumor. We previously identified a 62-probe sets signature (NB-hypo) to identify tissue hypoxia in neuroblastoma tumors and showed that NB-hypo stratified neuroblastoma patients in good and poor outcome 1. It was important to develop a prognostic classifier to cluster patients into risk groups benefiting of defined therapeutic approaches. Novel classification and data discretization approaches can be instrumental for the generation of accurate predictors and robust tools for clinical decision support. We explored the application to gene expression data of Rulex, a novel software suite including the Attribute Driven Incremental Discretization technique for transforming continuous variables into simplified discrete ones and the Logic Learning Machine model for intelligible rule generation. RESULTS: We applied Rulex components to the problem of predicting the outcome of neuroblastoma patients on the bases of 62 probe sets NB-hypo gene expression signature. The resulting classifier consisted in 9 rules utilizing mainly two conditions of the relative expression of 11 probe sets. These rules were very effective predictors, as shown in an independent validation set, demonstrating the validity of the LLM algorithm applied to microarray data and patients' classification. The LLM performed as efficiently as Prediction Analysis of Microarray and Support Vector Machine, and outperformed other learning algorithms such as C4.5. Rulex carried out a feature selection by selecting a new signature (NB-hypo-II) of 11 probe sets that turned out to be the most relevant in predicting outcome among the 62 of the NB-hypo signature. Rules are easily interpretable as they involve only few conditions. CONCLUSIONS: Our findings provided evidence that the application of Rulex to the expression values of NB-hypo signature created a set of accurate, high quality, consistent and interpretable rules for the prediction of neuroblastoma patients' outcome. We identified the Rulex weighted classification as a flexible tool that can support clinical decisions. For these reasons, we consider Rulex to be a useful tool for cancer classification from microarray gene expression data.

BACKGROUND: Neuroblastoma is the most common pediatric solid tumor. About fifty percent of high risk patients die despite treatment making the exploration of new and more effective strategies for improving stratification mandatory. Hypoxia is a condition of low oxygen tension occurring in poorly vascularized areas of the tumor associated with poor prognosis. We had previously defined a robust gene expression signature measuring the hypoxic component of neuroblastoma tumors (NB-hypo) which is a molecular risk factor. We wanted to develop a prognostic classifier of neuroblastoma patients' outcome blending existing knowledge on clinical and molecular risk factors with the prognostic NB-hypo signature. Furthermore, we were interested in classifiers outputting explicit rules that could be easily translated into the clinical setting. RESULTS: Shadow Clustering (SC) technique, which leads to final models called Logic Learning Machine (LLM), exhibits a good accuracy and promises to fulfill the aims of the work. We utilized this algorithm to classify NB-patients on the bases of the following risk factors: Age at diagnosis, INSS stage, MYCN amplification and NB-hypo. The algorithm generated explicit classification rules in good agreement with existing clinical knowledge. Through an iterative procedure we identified and removed from the dataset those examples which caused instability in the rules. This workflow generated a stable classifier very accurate in predicting good and poor outcome patients. The good performance of the classifier was validated in an independent dataset. NB-hypo was an important component of the rules with a strength similar to that of tumor staging. CONCLUSIONS: The novelty of our work is to identify stability, explicit rules and blending of molecular and clinical risk factors as the key features to generate classification rules for NB patients to be conveyed to the clinic and to be used to design new therapies. We derived, through LLM, a set of four stable rules identifying a new class of poor outcome patients that could benefit from new therapies potentially targeting tumor hypoxia or its consequences.

Gene selection methods aim at determining biologically relevant subsets of genes in DNA microarray experiments. However, their assessment and validation represent a major difficulty since the subset of biologically relevant genes is usually unknown. To solve this problem a novel procedure for generating biologically plausible synthetic gene expression data is proposed. It is based on a proper mathematical model representing gene expression signatures and expression profiles through Boolean threshold functions. The results show that the proposed procedure can be successfully adopted to analyze the quality of statistical and machine learning-based gene selection algorithms.

The problem of reconstructing the and-or expression of a partially defined positive Boolean function (pdpBf) is solved by adopting a novel algorithm, denoted by LSC, which combines the advantages of two efficient techniques, Logical Analysis of Data (LAD) and Shadow Clustering (SC). The kernel of the approach followed by LAD consists in a breadth-first enumeration of all the prime implicants whose degree is not greater than a fixed maximum d. In contrast, SC adopts an effective heuristic procedure for retrieving the most promising logical products to be included in the resulting and-or expression. Since the computational cost required by LAD prevents its application even for relatively small dimensions of the input domain, LSC employs a depth-first approach, with asymptotically linear memory occupation, to analyze the prime implicants having degree not greater than d. In addition, the theoretical analysis proves that LSC presents almost the same asymptotic time complexity as LAD. Extensive simulations on artificial benchmarks validate the good behavior of the computational cost exhibited by LSC, in agreement with the theoretical analysis. Furthermore, the pdpBf retrieved by LSC always shows a better performance, in terms of complexity and accuracy, with respect to those obtained by LAD.

Discretization is a fundamental phase for many classification algorithms: it aims at finding a proper set of cutoffs that subdivide a continuous domain into homogeneous intervals; the points in each interval should have a high probability of belonging to the same class. This paper proposes two different approaches for discretization: the first one consists in retrieving the optimal set of separation points through the solution of a proper linear programming problem. Since the optimal solution may require an excessive computational burden, an alternative technique, based on the iterative addition of separation points, is described. The greedy algorithm is evaluated on some artificial datasets and compared with other well-known discretization techniques such as EntMDL. The results of the simulations show the good performances of the novel algorithm in terms both of accuracy of the solution and of computational effort required for its generation.

UNLABELLED: Most microarray experiments are carried out with the purpose of identifying genes whose expression varies in relation with specific conditions or in response to environmental stimuli. In such studies, genes showing similar mean expression values between two or more groups are considered as not differentially expressed, even if hidden subclasses with different expression values may exist. In this paper we propose a new method for identifying differentially expressed genes, based on the area between the ROC curve and the rising diagonal (ABCR). ABCR represents a more general approach than the standard area under the ROC curve (AUC), because it can identify both proper (i.e., concave) and not proper ROC curves (NPRC). In particular, NPRC may correspond to those genes that tend to escape standard selection methods. RESULTS: We assessed the performance of our method using data from a publicly available database of 4026 genes, including 14 normal B cell samples (NBC) and 20 heterogeneous lymphomas (namely: 9 follicular lymphomas and 11 chronic lymphocytic leukemias). Moreover, NBC also included two sub-classes, i.e., 6 heavily stimulated and 8 slightly or not stimulated samples. We identified 1607 differentially expressed genes with an estimated False Discovery Rate of 15%. Among them, 16 corresponded to NPRC and all escaped standard selection procedures based on AUC and t statistics. Moreover, a simple inspection to the shape of such plots allowed to identify the two subclasses in either one class in 13 cases (81%). CONCLUSION: NPRC represent a new useful tool for the analysis of microarray data.

In this paper, a general method for the numerical solution of maximum-likelihood estimation (MLE) problems is presented; it adopts the deterministic learning (DL) approach to find close approximations to ML estimator functions for the unknown parameters of any given density. The method relies on the choice of a proper neural network and on the deterministic generation of samples of observations of the likelihood function, thus avoiding the problem of generating samples with the unknown density. Under mild assumptions, consistency and convergence with favorable rates to the true ML estimator function can be proved. Simulation results are provided to show the good behavior of the algorithm compared to the corresponding exact solutions.

The general problem of reconstructing an unknown function from a finite collection of samples is considered, in case the position of each input vector in the training set is not fixed beforehand but is part of the learning process. In particular, the consistency of the empirical risk minimization (ERM) principle is analyzed, when the points in the input space are generated by employing a purely deterministic algorithm (deterministic learning). When the output generation is not subject to noise, classical number-theoretic results, involving discrepancy and variation, enable the establishment of a sufficient condition for the consistency of the ERM principle. In addition, the adoption of low-discrepancy sequences enables the achievement of a learning rate of O(1/L), with L being the size of the training set. An extension to the noisy case is provided, which shows that the good properties of deterministic learning are preserved, if the level of noise at the output is not high. Simulation results confirm the validity of the proposed approach.

Extracting information from gene expression data is a difficult task, as these data are characterized by very high dimensional, small sized, samples and large degree of biological variability. However, a possible way of dealing with the curse of dimensionality is offered by feature selection algorithms, while variance problems arising from small samples and biological variability can be addressed through ensemble methods based on resampling techniques. These two approaches have been combined to improve the accuracy of Support Vector Machines (SVM) in the classification of malignant tissues from DNA microarray data. To assess the accuracy and the confidence of the predictions performed proper measures have been introduced. Presented results show that bagged ensembles of SVM are more reliable and achieve equal or better classification accuracy with respect to single SVM, whereas feature selection methods can further enhance classification accuracy.

The generation of a set of rules underlying a classification problem is performed by applying a new algorithm called Hamming Clustering (HC). It reconstructs the AND-OR expression associated with any Boolean function from a training set of samples. The basic kernel of the method is the generation of clusters of input patterns that belong to the same class and are close to each other according to the Hamming distance. Inputs which do not influence the final output are identified, thus automatically reducing the complexity of the final set of rules. The performance of HC has been evaluated through a variety of artificial and real-world benchmarks. In particular, its application in the diagnosis of breast cancer has led to the derivation of a reduced set of rules solving the associated classification problem.

The definition of nearest-neighbor probability p(C) is introduced to characterize classification problems with binary inputs. It measures the likelihood that two patterns, which are close according to the Hamming distance, are assigned to the same class. It is shown that the generalization ability gNN(C) of neural networks that resemble the nearest-neighbor algorithm can be expressed as a function of p(C) and is upper bounded by p(C) when p(C)>0.5. In the opposite case a proper operator, called complementation, is proposed to improve the classification process in the test phase.

The problem of finding optimal weights for a single threshold neuron starting from a general training set is considered. Among the variety of possible learning techniques, the pocket algorithm has a proper convergence theorem which asserts its optimality. However, the original proof ensures the asymptotic achievement of an optimal weight vector only if the inputs in the training set are integer or rational. This limitation is overcome in this paper by introducing a different approach that leads to the general result. Furthermore, a modified version of the learning method considered, called pocket algorithm with ratchet, is shown to obtain an optimal configuration within a finite number of iterations independently of the given training set.

Gene expression is regulated by different kinds of short nucleotide domains. These features can either activate or terminate the transcription process. To predict the signal sites in the 5′ and 3′ gene regions we applied the Hamming-Clustering network (HC) to the TATA box, to the transcription initiation site and to the poly(A) signal determination in DNA sequences. This approach employs a technique deriving from the synthesis of digital networks in order to generate prototypes, or rules, which can be directly analysed or used for the construction of a final neural network. More than 1000 poly-A signals have been extracted from EMBL database rel. 42 and used to build the training and the test set. A full set of the eukaryotic genes (1252 entry) from the Eukaryotic Promoter Database (EPD rel. 42) have been used for the TATA-box signal and transcription initiation site training. A set of eukaryotic plant genes have been used to test the validity of the Hamming-Clustering network approach. The results show the applicability of the Hamming-Clustering method to functional signal prediction. The program implementing the algorithm has been written in C language and it is available on the Web server (http://www.itba.mi.cnr.it/webgene). E-mail address: [email protected]

A new technique called sequential window learning (SWL), for the construction of two-layer perceptrons with binary inputs is presented. It generates the number of hidden neurons together with the correct values for the weights, starting from any binary training set. The introduction of a new type of neuron, having a window-shaped activation function, considerably increases the convergence speed and the compactness of resulting networks. Furthermore, a preprocessing technique, called hamming clustering (HC), is proposed for improving the generalization ability of constructive algorithms for binary feedforward neural networks. Its insertion in the sequential window learning is straightforward. Tests on classical benchmarks show the good performances of the proposed techniques, both in terms of network complexity and recognition accuracy.