Two of the main challenges in multi-label classification are the need to collect labeled data, which can be costly or impractical, and the need to satisfy hard logical constraints between labels, which is often computationally expensive.In some applications, complementary labelsthat is, labels specifying a class to which a sample does not belong -are available and much less costly to obtain.Researchers have therefore developed methods to learn from such labels efficiently and effectively.Similar efforts have been made to address the problem of learning with hard logical constraints.Nevertheless, to the best of our knowledge, no prior work has investigated the problem of learning from complementary labels with hard logical constraints.In this work, we propose and compare methods to address this problem, showing that hard logical constraints, besides representing restrictions to be satisfied, can also serve as an additional source of weak supervision.The relationships between labels can help bridge the information gap between relevant and complementary labels.Experimental results on different datasets and scenarios support our claims.

Post-hoc explanation methods of image recognition models often exhibit high variance or disagreement across explanations when the input data are perturbed, the underlying models are modified, or different explainability techniques are employed.To mitigate this issue, several approaches have been proposed, among which ensemble strategies that aggregate multiple explanations have attracted particular attention.Although some of these methods demonstrate good empirical performance, most existing works remain largely empirical, with limited theoretical justification or understanding of why ensemble strategies work and when they fail.In this paper, we analyze the factors that influence the success and failure of ensemble strategies that combines multiple explanations, using different datasets, convolutional neural network architectures, posthoc explanation techniques, and ensembling strategies to identify the most influential image patches.In particular, we compare various ensembling strategies based on distinct voting principles -namely, Borda Count, Kemeny-Young, Reciprocal Rank Fusion, and the Schulze method -and show that the performance of such ensemble methods depends on the degree of satisfaction of their underlying theoretical assumptions.

The Optimal In-Station Train Dispatching (InSTraDi) problem consists in commanding the movements of trains inside a railway station while both (i) respecting safety, time, and travel constraints and (ii) minimizing delays. In Symbolic Pattern Planning (SPP), a pattern, suggesting the sequence of happenings to reach the goal, is encoded in a logic formula whose models correspond to valid plans. If no valid plan is found, the pattern is extended until it covers a valid plan. However, plans of better quality could exist if we had continued extending the pattern. In this paper, we formalize the InSTraDi problem as a Temporal Planning Task with Intermediate Conditions and Effects, and we show an InSTraDi-dependent way to construct, in polynomial time, a pattern ensuring the optimal plan can be found by the SPP approach without never extending the pattern. Analysis on realistic railway data validate our approach.

Machine Learning (ML) has become a central force in Artificial Intelligence, driving major breakthroughs in applications that handle increasingly complex data, from images and text sequences to graph structures. While new architectures such as Transformers and Graph Neural Networks continue to redefine performance benchmarks in various domains, these predominantly data-driven methods often neglect critical domain knowledge, practical constraints, and broader contextual factors. This oversight diminishes their trustworthiness and restricts their impact in real-world settings. In this paper, we discuss the need for a more informed approach to ML for complex data. Specifically, we advocate for solutions that explicitly integrate structural awareness to capture underlying relationships in the data, incorporate key technical requirements to ensure safety and compliance with industry standards, embed environmental considerations to promote sustainability and resource efficiency, adhere to established physical principles, and uphold ethical and societal values. By weaving these dimensions together, informed ML can bridge the gap between purely data-centric methods and the nuanced demands of practical applications. We show how this integrated framework not only strengthens model performance but also ensures that ML solutions remain trustworthy, efficient, and sensitive to human ecological, ethical, and regulatory imperatives. Our discussion underscores the transformative potential of Informed ML to drive innovation across diverse domains, setting a new benchmark for responsible and high-impact ML system design.

In recent years, Artificial Intelligence, particularly Machine Learning, has achieved remarkable success in solving complex problems. However, this progress has also revealed the emergence of unexpected, poorly understood, and elusive phenomena that characterize the behavior of machine intelligence and learning processes. These phenomena often challenge researchers to interpret them within the boundaries of existing Machine Learning theoretical frameworks, thereby motivating the development of new and more comprehensive theoretical foundations. One such phenomenon, known as grokking , refers to the sudden and substantial improvement in a model’s performance following a prolonged period of stagnant or even regressive learning. In this paper, we argue that it is possible to provide insights into grokking by leveraging the existing theoretical foundations of Machine Learning, in particular concepts from Statistical Learning Theory, such as norm-based and stability-based generalization bounds. We further show how these theories can help reconcile the phenomenon of grokking with established principles of learning and generalization. Furthermore, we demonstrate the practical applicability of these insights through concrete examples.

Fixed-budget attacks aim to generate adversarial examples—carefully crafted inputs designed to induce misclassifications during inference—while adhering to a predefined perturbation budget. These attacks maximize misclassification confidence and benefit from the transferability property, enabling the generated adversarial examples to remain effective even against multiple unknown models. However, to preserve their transferability, such attacks often yield perceptible perturbations, compromising the visual integrity of the adversarial examples. In this paper, we introduce HORNET, an extension of gradient-based fixed-budget attacks designed to minimize the perturbation magnitude of adversarial examples while maintaining their transferability against the target model. HORNET utilizes a distinct source model to craft the adversarial examples and employs a limited number of queries to the unknown target model to further minimize perturbation magnitude. We evaluate HORNET empirically by integrating it with 41 existing attack implementations and testing it against 9 different models, resulting in a total of 1700 unique configurations. Our results demonstrate that HORNET outperforms the state of the art in generating minimally perturbed yet highly transferable adversarial examples across all tested models. Code available at: https://github.com/louiswup/HORNET .

In recent years, Artificial Intelligence, particularly Machine Learning (ML), has demonstrated remarkable success in addressing complex problems.However, this progress has been accompanied by the emergence of unexpected, poorly understood, and elusive phenomena that characterize the behavior of machine intelligence and learning processes.Researchers are often challenged to interpret these phenomena within the existing theoretical frameworks of ML, fostering a search for more complex or technical explanations.One such phenomenon, known as "grokking", occurs when an ML model, after a long period of stagnant or even regressive learning, suddenly exhibits rapid and substantial improvement.In this paper, we argue that grokking can be explained with the theoretical foundations of ML by leveraging Statistical Learning Theory, i.e., Algorithmic Stability theory.We provide insights into how this theory can reconcile grokking with established principles of learning and generalization. * This work is partially supported by (i

Stable diffusion models represent the state-of-the-art in data synthesis across diverse domains and hold transformative potential for applications in science and engineering, e.g., by facilitating the discovery of novel solutions and simulating systems that are computationally intractable to model explicitly. While there is increasing effort to incorporate physics-based constraints into generative models, existing techniques are either limited in their applicability to latent diffusion frameworks or lack the capability to strictly enforce domain-specific constraints. To address this limitation this paper proposes a novel integration of stable diffusion models with constrained optimization frameworks, enabling the generation of outputs satisfying stringent physical and functional requirements. The effectiveness of this approach is demonstrated through material design experiments requiring adherence to precise morphometric properties, challenging inverse design tasks involving the generation of materials inducing specific stress-strain responses, and copyright-constrained content generation tasks. All code has been released at https://github.com/RAISELab-atUVA/Constrained-Stable-Diffusion.

Machine Learning (ML) has transformed both research and industry by offering powerful models capable of capturing complex phenomena. However, these models often require large, high-quality datasets and may struggle to generalize beyond the distributions on which they are trained. Informed Machine Learning (IML) tackles these challenges by incorporating domain knowledge at various stages of the ML pipeline, thereby reducing data requirements and enhancing generalization. Building on statistical learning theory, we present some theoretical comparison and insights about ML and IML excess risk and generalization performance. We then illustrate how these theoretical insights can be leveraged in practice through some practical examples. Our findings shed some light on the mechanisms and conditions under which IML can outperform traditional ML, offering valuable guidance for effective implementation in real-world settings. • ML-based predictive models have greatly reshaped research, industry and society. • Informed ML leverages prior knowledge to reduce data demands and boost extrapolation. • We compare ML and Informed ML in terms of excess risk and generalization. • Informed ML can surpass ML under conditions favoring domain-specific insights.

Machine-learning models demand periodic updates to improve their average accuracy, exploiting novel architectures and additional data. However, a newly updated model may commit mistakes the previous model did not make. Such misclassifications are referred to as negative flips, experienced by users as a regression of performance. In this work, we show that this problem also affects robustness to adversarial examples, hindering the development of secure model update practices. In particular, when updating a model to improve its adversarial robustness, previously ineffective adversarial attacks on some inputs may become successful, causing a regression in the perceived security of the system. We propose a novel technique, named robustness-congruent adversarial training, to address this issue. It amounts to fine-tuning a model with adversarial training, while constraining it to retain higher robustness on the samples for which no adversarial example was found before the update. We show that our algorithm and, more generally, learning with non-regression constraints, provides a theoretically-grounded framework to train consistent estimators. Our experiments on robust models for computer vision confirm that both accuracy and robustness, even if improved after model update, can be affected by negative flips, and our robustness-congruent adversarial training can mitigate the problem, outperforming competing baseline methods.

Machine Learning (ML) based predictive models are impacting research, industry, and society at large thanks to their ability to model or surrogate real systems.Two of the main current limitations of ML are the need for large amounts of high quality data and low performance far away from the observed data.For this reason, in certain applications where prior knowledge is available, researchers have developed Informed ML (IML) to decrease ML high quality data voracity and increase ML extrapolation abilities.In this work we study the differences between ML and IML excess risk and generalization using also some examples to elucidate the theoretical discussions.Our findings shed some light on the mechanisms and the conditions under which IML outperforms ML.

In the contemporary era of data-driven decision-making, the application of Machine Learning (ML) on complex data (e.g., images, text, sequences, trees, and graphs) has become increasingly pivotal (e.g., Large Language Models and Graph Neural Networks).In this context, there is a gap between purely data-driven models and domain-specific knowledge, requirements, and expertise.In particular, this domain specificity needs to be integrated into the ML models to improve learning generalization, sustainability, trustworthiness, reliability, security, and safety.This additional knowledge can assume different forms, e.g.: software developers require ML to comply with many technical requirements, companies require ML to comply with economic and environmental sustainability, domain experts require ML to be aligned with physical and logical laws, and society requires ML to be aligned with ethical principles.This special session gathers valuable contributions and early findings in the field of Informed ML for Complex Data.Our main objective is to showcase the potential and limitations of new ideas, improvements, or the blending of ML and other research areas in solving real-world problems.

Machine learning systems often require updates for various reasons, such as the availability of new data or models and the need to optimize different technical or ethical metrics. Typically, these metrics reflect an average performance rather than sample-wise behavior. Indeed, improvements in metrics like accuracy can introduce negative flips, where the updated model makes errors that the previous model did not make. In certain applications, these negative flips can be perceived by developers or users as a regression in performance, contributing to the hidden technical debt of machine learning systems. Moreover, if the distribution of negative flips is biased with respect to some sensitive attribute (e.g., gender or race), it may be perceived as discrimination, termed unfair regression. In this paper we show, for the first time, the existence of the phenomenon of unfair regression and propose different ethical metrics to measure it. Additionally, we offer two mitigation strategies - one focused on modifying the learning algorithm and one focused on modifying the tuning phase - to address this issue. Our results on real-world datasets confirm the existence of the unfair regression phenomenon and demonstrate the effectiveness of the proposed mitigation strategies.

Over the past decade, advances in Machine Learning have significantly expanded both the number and complexity of algorithms. Consequently, solving specific tasks now requires making numerous choices, such as selecting the appropriate algorithm, architecture, and corresponding hyper-parameters. Although various methods have been proposed to expedite this search process, the final selection is typically made using a holdout set. While this practical approach is widely accepted, it can lead to the issue of overvalidation when the number of choices is large. Overvalidation refers to the bias in holdout performance, which can result in the incorrect selection of the optimal choice so to be not aligned with the technical needs. This issue can be mitigated by improving the quantity and quality of data in the validation set or through resampling, but it reappears as the number of choices increases. Thus, the challenge of better understanding and detecting overvalidation to avoid or further mitigate it remains unresolved. In this paper, we address this problem by measuring and understanding the overvalidation phenomenon using statistical learning theory and testing it with real-world examples.

In this paper, we investigate neural models based on graph random features for classification tasks. First, we aim to understand when over parameterization, namely generating more features than the ones necessary to interpolate, may be beneficial for the generalization abilities of the resulting models. We employ two measures: one from the algorithmic stability framework and another one based on information theory. We provide empirical evidence from several commonly adopted graph datasets showing that the considered measures, even without considering task labels, can be effective for this purpose. Additionally, we investigate whether these measures can aid in the process of hyperparameters selection. The results of our empirical analysis show that the considered measures have good correlations with the estimated generalization performance of the models with different hyperparameter configurations. Moreover, they can be used to identify good hyperparameters, achieving results comparable to the ones obtained with a classic grid search.

In the last decade it became increasingly apparent the inability of technical metrics such as accuracy, sustainability, and non-regressiveness to well characterize the behavior of intelligent systems. In fact, they are nowadays requested to meet also ethical requirements such as explainability, fairness, robustness, and privacy increasing our trust in their use in the wild. Of course often technical and ethical metrics are in tension between each other but the final goal is to be able to develop a new generation of more responsible and trustworthy machine learning. In this paper, we focus our attention on machine learning algorithms and associated predictive models, questioning for the first time, from a theoretical perspective, if it is possible to simultaneously guarantee their performance in terms of both technical and ethical metrics towards machine learning algorithms that we can trust. In particular, we will investigate for the first time both theory and practice of deterministic and randomized algorithms and associated predictive models showing the advantages and disadvantages of the different approaches. For this purpose we will leverage the most recent advances coming from the statistical learning theory: Complexity-Based Methods, Distribution Stability, PAC-Bayes, and Differential Privacy. Results will show that it is possible to develop consistent algorithms which generate predictive models with guarantees on multiple trustworthiness metrics.

Recent research has shown that some learned classifiers can be more easily fooled by an adversary who carefully crafts imperceptible or physically plausible modifications of the input data regarding particular subgroups of the population (e.g., people with particular gender, ethnicity, or skin color).This form of unfairness has been just recently studied, noting the fact that classical fairness metrics, which only observe the model outputs, are not enough but robustness biases need to be measured and mitigated as well.For this reason, in this paper, we will first develop a new metric of fairness which generalizes the current ones and degenerates in the classical ones and then we will develop a theoretical mitigation framework with consistency results able to generate a new empirical mitigation strategy and explain why the current ones actually work. * This work is supported in part

In the last decade it became increasingly apparent the inability of technical metrics to well characterize the behavior of intelligent systems.In fact, they are nowadays requested to meet also ethical requirements such as explainability, fairness, robustness, and privacy increasing our trust in their use in the wild.The final goal is to be able to develop a new generation of more responsible and trustworthy machine learning.In this paper, we focus our attention on randomized machine learning algorithms and models questioning, from a theoretical perspective, if it is possible to simultaneously optimize multiple metrics that are in tension between each other towards randomized machine learning algorithms that we can trust.For this purpose we will leverage the most recent advances coming from the statistical learning theory: distribution stability and differential privacy.* This work is supported in

This century saw an unprecedented increase of public and private investments in Artificial Intelligence (AI) and especially in (Deep) Machine Learning (ML). This led to breakthroughs in their practical ability to solve complex real-world problems impacting research and society at large. Instead, our ability to understand the fundamental mechanism behind these breakthroughs has slowed down because of their increased complexity, while in the past breakthroughs often emerged from foundational research. This questioned researchers about the necessity for a new theoretical framework able to help researchers catch up on this lag. One of the still not well understood mechanisms is the so-called over-parametrization, namely the ability of certain models to increase their generalization performance (reduce test error) when the number of parameters is above the interpolating threshold (zero training error). In this paper we will show that this phenomenon can be better understood using both known theories (surveying them in the process) and empirical evidences for both shallow and deep learning algorithms.

Signals, track circuits, switches, and relay rooms are simultaneously the most critical and most maintained railway assets.A fault of one of these assets may strongly reduce the railway network capacity or even disrupt the circulation.Effectively predicting what assets may need maintenance allows to anticipate the intervention thus avoiding a failure.Currently, this problem is tackled by infrastructure managers mostly relying on operators' experience and with limited support of decision supporting tools.In this paper, we propose a Simple Informed Machine Learning (ML) based model able to automatically predict what asset need to be maintained fully leveraging on the operator experience.However, ML models in modern industrial MLOps pipelines demand continuous data collection, model re-training, testing, and monitoring, creating a large technical debt.In fact, one of the main requirements of these pipelines is to not be regressive, i.e., not simply improve average performances but also not incorrectly predicting an output that was correctly classified by the reference model (negative flips).In this work we face this problem by empowering the proposed ML with Non Regressive properties.Results on real data coming from a portion of an Italian Railway Network managed by Rete Ferroviaria Italiana, the Italian Infrastructure Manager, will support our proposal. * This research

This century saw an unprecedented increase of public and private investments in Artificial Intelligence (AI) and especially in Machine Learning (ML).This led to breakthroughs in their practical ability to solve complex real world problems impacting research and society at large.Instead, our ability to understand the fundamental mechanism behind these breakthroughs has slowed down because of their increased complexity.This questioned researchers about the necessity for a new theoretical framework able to help researchers catch up on this lag.One of the still not well understood mechanisms is the so called over-parametrization, namely the ability of certain models to increasing their generalization performance (reduce test error) when the number of parameters is above the interpolating threshold (zero training error), and the associated doubledescent curve.In this paper we will show that this phenomena can be better understood using both known theories, i.e., the algorithmic stability theory, and empirical evidence.

The execution of a human movement involves different muscles that are activated and coordinated by the brain at different temporal scales in a complex cognitive process. For this reason, studying human motion requires to properly model multiple temporal scales that fully describe its complexity. Current approaches are not able to address this requirement properly or are based on oversimplified models with obvious limitations. Data-driven models represent research frontiers able to provide new insights. In this work we will investigate different data-driven approaches. The first one is based on shallow models that, while achieving reasonably good recognition performance, require to handcraft features according to the domain knowledge The second one is based on deep models that can be extended to manage multiple temporal scales but they are hard to exploit as too many architecture configurations exist. For this reason, we will propose a new deep multiple temporal scale data-driven model, based on Temporal Convolutional Network, capable of learning features from the data at different temporal scales, of outperforming state of the art deep and shallow models, and of exploiting shallow models to tune the architecture configuration. We designed, collected data and tested our proposal in a specially devised experiment, to prove the validity of our approach. In particular, we collected motion capture data about dyad actions where two people exchange a ball. As the weight of the ball and the throwing intentions change, we will show how it is possible to automatically detect either the weight of the ball or the intention behind the throw just based on motion data. Data regarding our experiment and code of the methods proposed in this work are also made freely available to the research community. Results support both the proposal and the need for the use of deep multi scale models as a tool to better understand human movement and its multiple time scale nature.

Studying human motion requires modelling its multiple temporal scale nature to fully describe its complexity since different muscles are activated and coordinated by the brain at different temporal scales in a complex cognitive process. Nevertheless, current approaches are not able to address this requirement properly, and are based on oversimplified models with obvious limitations. Data-driven methods represent a viable tool to address these limitations. Nevertheless, shallow data-driven models, while achieving reasonably good recognition performance, require to handcraft features based on domain-specific knowledge which, in this cases, is limited and does no allow to properly model motion- and subject-specific temporal scales. In this work, we propose a new deep multiple temporal scale data-driven model, based on Temporal Convolutional Networks, able to automatically learn features from the data at different temporal scales. Our proposal focuses first on over-performing state-of-the-art shallows and deep models in terms of recognition performance. Then, thanks to the use of feature ranking for shallow models and an attention map for deep models, we will give insights on what the different architectures actually learned from the data. We designed, collected data, and tested our proposal in custom experiment of motion recognition: detecting the person who draw a particular shape (i.e., an ellipse) on a graphics tablet, collecting data about his/her movement (e.g., pressure and speed) in different extrapolating scenarios (e.g., training with data collected from one hand and testing the model on the other one). Collected data regarding our experiment and code of the methods are also made freely available to the research community. Results, both in terms of accuracy and insight on the cognitive problem, support the proposal and support the use of the proposed technique as a support tool for better understanding the human movements and its multiple temporal scale nature.

In offshore maritime operations, automated systems capable of maintaining the vessel’s position and heading using its own propellers and thrusters to compensate exogenous disturbances, like wind, waves, and currents, are referred to as marine dynamic positioning (DP) systems. DP systems play a central role in several marine operations, such as drilling, pipe-laying, coring, and ocean observation. These operations are the primary cause of fuel consumption, having a strong impact on the overall footprint of the vessel. For this reason, we will face the problem of optimal thrust allocation of an over-actuated vessel to maintain position and heading with minimal fuel consumption. State-of-the-art approaches simplify this problem by roughly approximating it and obtain a simple, mostly convex, optimization problem that can be solved in near-real time by the automation system. In this article, we improve current approaches with the following contributions. We will exploit a higher fidelity representation of the physical system, and we will manipulate the resulting optimization problem accordingly, to allow for near-real-time solutions on conventional computing platforms on-board. We evaluate the quality of the proposal with a case study on a drilling unit equipped with six thrusters. The results will show that it is possible to achieve up to 5% of fuel savings with respect to conventional approaches.Note to Practitioners—This article was motivated by the problem of minimizing fuel consumption in thrust allocation of DP systems. The current approaches simplify this issue by adopting simpler, yet related, optimization problems as surrogates, keeping the problem tractable for near-real-time control. We propose, instead, to solve the original problem with state-of-the-art modelization of the physical system and exploit reasonable and theoretical proprietaries to achieve optimal solutions in near-real-time. The results on a drilling unit will show additional fuel savings of up to 5% with respect to alternative state-of-the-art approaches.

Public railway transport systems play a crucial role in servicing the global society and are the transport backbone of a sustainable economy.While a significant effort has been devoted to predict inter-station trains movements to support stakeholders (i.e., infrastructure managers, train operators, and travellers) decisions, the problem of predicting instation movements, while being crucial to improve train dispatching (i.e., empowering human or automatic dispatchers), has been far more less investigated.In fact, stations are the most critical points in a railway network: even small improvements in the estimation of the duration of trains movements can remarkably enhance the dispatching efficiency in coping with the increase in capacity demand and with delays.In this work we will first leverage on state of the art shallow models, fed by domain experts with domain specific features, to improve the current predictive systems.Then, we will leverage on a customised deep multi scale model able to automatically learn the representation and improve the accuracy of the shallow models.Results on real-world data coming from the Italian railway network will support our proposal.* This work has been partially

Recent researches have been shown that models induced by machine learning, in particular by deep learning, can be easily fooled by an adversary who carefully crafts imperceptible, at least from the human perspective, or physically plausible modifications of the input data.This discovery gave birth to a new field of research, the adversarial machine learning, where new methods of attacks and defence are developed continuously, mimicking what is happening from a long time in cybersecurity.In this paper we will show that the drawbacks of inducing models from data less prone to be misled actually provides some benefits when it comes to assess their generalisation abilities.

Trustworthiness, and in particular Algorithmic Fairness, is emerging as one of the most trending topics in Machine Learning (ML). In fact, ML is now ubiquitous in decision making scenarios, highlighting the necessity of discovering and correcting unfair treatments of (historically discriminated) subgroups in the population (e.g., based on gender, ethnicity, political and sexual orientation). This necessity is even more compelling and challenging when unexplainable black-box Deep Neural Networks (DNN) are exploited. An emblematic example of this necessity is provided by the detected unfair behavior of the ML-based face recognition systems exploited by law enforcement agencies in the United States. To tackle these issues, we first propose different (un)fairness mitigation regularizers in the training process of DNNs. We then study where these regularizers should be applied to make them as effective as possible. We finally measure, by means of different accuracy and fairness metrics and different visual explanation strategies, the ability of the resulting DNNs in learning the desired task while, simultaneously, behaving fairly. Results on the recent FairFace dataset prove the validity of our approach.

We investigate the problem of analyzing the train movements in Large-Scale Railway Networks for the purpose of understanding and predicting their behaviour. We focus on different important aspects: the Running Time of a train between two stations, the Dwell Time of a train in a station, the Train Delay, and the Penalty Costs associated to a delay. Two main approaches exist in literature to study these aspects. One is based on the knowledge of the network and the experience of the operators. The other one is based on the analysis of the historical data about the network with advanced data analytics methods. In this paper, we will propose an hybrid approach in order to address the limitations of the current solutions. In fact, experience-based models are interpretable and robust but not really able to take into account all the factors which influence train movements resulting in low accuracy. From the other side, Data-Driven models are usually not easy to interpret, nor robust to infrequent events, and require a representative amount of data which is not always available if the phenomenon under examination changes too fast. Results on real world data coming from the Italian railway network will show that the proposed solution outperforms both state-of-the-art experience and Data-Driven based systems in terms of interpretability, robustness, ability to handle non recurrent events and changes in the behaviour of the network, and ability to consider complex and exogenous information.

When dealing with kernel methods, one has to decide which kernel and which values for the hyperparameters to use. Resampling techniques can address this issue but these procedures are time-consuming. This problem is particularly challenging when dealing with structured data, in particular with graphs, since several kernels for graph data have been proposed in literature, but no clear relationship among them in terms of learning properties is defined. In these cases, exhaustive search seems to be the only reasonable approach. Recently, the global Rademacher complexity (RC) and local Rademacher complexity (LRC), two powerful measures of the complexity of a hypothesis space, have shown to be suited for studying kernels properties. In particular, the LRC is able to bound the generalization error of an hypothesis chosen in a space by disregarding those ones which will not be taken into account by any learning procedure because of their high error. In this paper, we show a new approach to efficiently bound the RC of the space induced by a kernel, since its exact computation is an NP-Hard problem. Then we show for the first time that RC can be used to estimate the accuracy and expressivity of different graph kernels under different parameter configurations. The authors' claims are supported by experimental results on several real-world graph data sets.

Random Forests (RF) of tree classifiers are a state-of-the-art method for classification purposes. RF show limited hyperparameter sensitivity, have high numerical robustness, possess native capacity of dealing with numerical and categorical features, and are quite effective in many real world problems with respect to other state-of-the-art techniques. In this work we show how to crack RF in order to be able to train them on arbitrary large datasets. In particular, we extend ReForeSt, an Apache Spark-based RF implementation. The new version of ReForeSt computation automatically adapts to two methodologies to distribute the data and the computation on the available machines and automatically chooses the one able to provide the result in less time. The new ReForeSt also supports Random Rotations, a quite recent randomization technique which can bust the accuracy of the original RF. We perform an extensive experimental evaluation between ReForeSt and MLlib by taking advantage of the Google Cloud Platform1. We test the performances and the scalability of ReForeSt and MLlib on several real world datasets. Results confirm that ReForeSt outperforms MLlib both in terms of memory and computational efficiency, and classification performances. ReForeSt is publicly available via GitHub2.

Nowadays, developing effective techniques able to deal with data coming from structured domains is becoming crucial. In this context kernel methods are the state-of-the-art tool widely adopted in real-world applications that involve learning on structured data. Contrarily, when one has to deal with unstructured domains, deep learning methods represent a competitive, or even better, choice. In this paper we propose a new family of kernels for graphs which exploits a deep representation of the information. Our proposal exploits the advantages of the two worlds. From one side we exploit the potentiality of the state-of-the-art graph kernels. From the other side we develop a deep architecture through a series of stacked kernel pre-image estimators trained in an unsupervised fashion via convex optimization. The hidden layers of the proposed framework are trained in a forward manner and this allows us to avoid the greedy layerwise training of classical deep learning. Results on real world graph datasets confirm the quality of the proposal.

We present a closed-loop unsupervised clustering method for motion vectors extracted from highly dynamic video scenes. Motion vectors are assigned to nonconvex homogeneous clusters characterizing direction, size and shape of regions with multiple independent activities. The proposed method is based on support vector clustering. Cluster labels are propagated over time via incremental learning. The proposed method uses a kernel function that maps the input motion vectors into a high-dimensional space to produce nonconvex clusters. We improve the mapping effectiveness by quantifying feature similarities via a blend of position and orientation affinities. We use the Quasiconformal Kernel Transformation to boost the discrimination of outliers. The temporal propagation of the clusters’ identities is achieved via incremental learning based on the concept of feature obsolescence to deal with appearing and disappearing features. Moreover, we design an online clustering performance prediction algorithm used as a feedback that refines the cluster model at each frame in an unsupervised manner. We evaluate the proposed method on synthetic data sets and real-world crowded videos and show that our solution outperforms state-of-the-art approaches.

Current train delay (TD) prediction systems do not take advantage of state-of-the-art tools and techniques for handling and extracting useful and actionable information from the large amount of endogenous (i.e., generated by the railway system itself) and exogenous (i.e., related to railway operation but generated by external phenomena) data available. Additionally, they are not designed in order to deal with the intrinsic time varying nature of the problem (e.g., regular changes in the nominal timetable, etc.). The purpose of this paper is to build a dynamic data-driven TD prediction system that exploits the most recent tools and techniques in the field of time varying big data analysis. In particular, we map the TD prediction problem into a time varying multivariate regression problem that allows exploiting both historical data about the train movements and exogenous data about the weather provided by the national weather services. The performance of these methods have been tuned through the state-of-the-art thresholdout technique, a very powerful procedure which relies on the differential privacy theory. Finally, the performance of two efficient implementations of shallow and deep extreme learning machines that fully exploit the recent in-memory large-scale data processing technologies have been compared with the current state-of-the-art TD prediction systems. Results on real-world data coming from the Italian railway network show that the proposal of this paper is able to remarkably improve the state-of-the-art systems.

State-of-the-art train delay prediction systems neither exploit historical data about train movements, nor exogenous data about phenomena that can affect railway operations. They rely, instead, on static rules built by experts of the railway infrastructure based on classical univariate statistics. The purpose of this paper is to build a data-driven train delay prediction system that exploits the most recent analytics tools. The train delay prediction problem has been mapped into a multivariate regression problem and the performance of kernel methods, ensemble methods and feed-forward neural networks have been compared. Firstly, it is shown that it is possible to build a reliable and robust data-driven model based only on the historical data about the train movements. Additionally, the model can be further improved by including data coming from exogenous sources, in particular the weather information provided by national weather services. Results on real world data coming from the Italian railway network show that the proposal of this paper is able to remarkably improve the current state-of-the-art train delay prediction systems. Moreover, the performed simulations show that the inclusion of weather data into the model has a significant positive impact on its performance.

Most state-of-the-art machine-learning (ML) algorithms do not consider the computational constraints of implementing the learned model on embedded devices. These constraints are, for example, the limited depth of the arithmetic unit, the memory availability, or the battery capacity. We propose a new learning framework, the Algorithmic Risk Minimization (ARM), which relies on Algorithmic-Stability, and includes these constraints inside the learning process itself. ARM allows one to train advanced resource-sparing ML models and to efficiently deploy them on smart embedded systems. Finally, we show the advantages of our proposal on a smartphone-based Human Activity Recognition application by comparing it to a conventional ML approach.

We review in this paper several methods from Statistical Learning Theory (SLT) for the performance assessment and uncertainty quantification of predictive models. Computational issues are addressed so to allow the scaling to large datasets and the application of SLT to Big Data analytics. The effectiveness of the application of SLT to manufacturing systems is exemplified by targeting the derivation of a predictive model for quality forecasting of products on an assembly line.

This paper presents a Learning Analytics approach for understanding the learning behavior of students while interacting with Technology Enhanced Learning tools. In this work we show that it is possible to gain insight into the learning processes of students from their interaction data. We base our study on data collected through six laboratory sessions where first-year students of Computer Engineering at the University of Genoa were using a digital electronics simulator. We exploit Process Mining methods to investigate and compare the learning processes of students. For this purpose, we measure the understandability of their process models through a complexity metric. Then we compare the various clusters of students based on their academic achievements. The results show that the measured complexity has positive correlation with the final grades of students and negative correlation with the difficulty of the laboratory sessions. Consequently, complexity of process models can be used as an indicator of variations of student learning paths.

The Support Vector Machine (SVM) is one of the most effective and used algorithms, when targeting classification. Despite its large success, SVM is mainly afflicted by two issues: (i) some hyperparameters must be tuned in advance and are, in practice, identified through computationally intensive procedures; (ii) possible a-priori knowledge about the problem (e.g. doctor expertise in medical applications) cannot be straightforwardly exploited. In this paper, we introduce a new approach, able to cope with the two previous problems: several experiments, performed on real-world benchmarking datasets, show that our method outperforms, on average, other techniques proposed in the literature.

When dealing with a Support Vector Machine (SVM) with a strictly positive definite kernel, a common misconception is that the main handle for controlling the nonlinearity of the classification surface is the set of kernel hyperparameters. We show here that this is not the case: in particular, we prove that, regardless of the value of the kernel hyperparameter, it is always possible to tune the nonlinearity of the classifier by acting only on the regularization hyperparameter C, even achieving perfect learning of any non-degenerate training set.

In this work we propose some new generalization bounds for binary classifiers, based on global Rademacher Complexity (RC), which exhibit fast convergence rates by combining state-of-the-art results by Talagrand on empirical processes and the exploitation of unlabeled patterns. In this framework, we are able to improve both the constants and the convergence rates of existing RC-based bounds. All the proposed bounds are based on empirical quantities, so that they can be easily computed in practice, and are provided both in implicit and explicit forms: the formers are the tightest ones, while the latter ones allow to get more insights about the impact of Talagrand's results and the exploitation of unlabeled patterns in the learning process. Finally, we verify the quality of the bounds, with respect to the theoretical limit, showing the room for further improvements in the common scenario of binary classification.

The purpose of this paper is to obtain a fully empirical stability-based bound on the generalization ability of a learning procedure, thus, circumventing some limitations of the structural risk minimization framework. We show that assuming a desirable property of a learning algorithm is sufficient to make data-dependency explicit for stability, which, instead, is usually bounded only in an algorithmic-dependent way. In addition, we prove that a well-known and widespread classifier, like the support vector machine (SVM), satisfies this condition. The obtained bound is then exploited for model selection purposes in SVM classification and tested on a series of real-world benchmarking datasets demonstrating, in practice, the effectiveness of our approach.

Smartphones emerge from the incorporation of new services and features into mobile phones, allowing to implement advanced functionalities for the final users. The implementation of Machine Learning (ML) algorithms on the smartphone itself, without resorting to remote computing systems, allow to achieve such goals without expensive data transmission. However, smartphones are resource-limited devices and, as such, suffer from many issues, which are typical of stand-alone devices, such as limited battery capacity and processing power. We show in this paper how to build a thrifty classifier by exploiting bit-based hypothesis spaces and local Rademacher Complexities. The resulting classifier is tested on a real-world Human Activity Recognition application, implemented on a Samsung Galaxy S II smartphone.

In this paper, we derive a deep connection between the Vapnik-Chervonenkis (VC) entropy and the Rademacher complexity. For this purpose, we first refine some previously known relationships between the two notions of complexity and then derive new results, which allow computing an admissible range for the Rademacher complexity, given a value of the VC-entropy, and vice versa. The approach adopted in this paper is new and relies on the careful analysis of the combinatorial nature of the problem. The obtained results improve the state of the art on this research topic.

This paper deals with the problem of identifying a connection between the Vapnik-Chervonenkis (VC) Entropy, a notion of complexity introduced by Vapnik in his seminal work, and the Rademacher Complexity, a more powerful notion of complexity, which has been in the limelight of several works in the recent Machine Learning literature. In order to establish this connection, we refine some previously known relationships and derive a new result. Our proposal allows computing an admissible range for the Rademacher Complexity, given a value of the VC-Entropy, and vice versa, therefore opening new appealing research perspectives in the field of assessing the complexity of an hypothesis space.

Choosing an appropriate hypothesis space in classification applications, according to the Structural Risk Minimization (SRM) principle, is of paramount importance to train effective models: in fact, properly selecting the the space complexity allows to optimize the learned functions performance. This selection is not straightforward, especially (though not solely) when few samples are available for deriving an effective model (e.g. in bioinformatics applications). In this paper, by exploiting a bit-based definition for Support Vector Machine (SVM) classifiers, selected from an hypothesis space described according to sparsity and locality principles, we show how the complexity of the corresponding space of functions can be effectively tuned through the number of bits used for the function representation. Real world datasets are exploited to show how the number of bits and the degree of sparsity/locality imposed to define the hypothesis space affect the complexity of the space of classifiers and, consequently, the performance of the model, picked up from this set.

In-sample approaches to model selection and error estimation of support vector machines (SVMs) are not as widespread as out-of-sample methods, where part of the data is removed from the training set for validation and testing purposes, mainly because their practical application is not straightforward and the latter provide, in many cases, satisfactory results. In this paper, we survey some recent and not-so-recent results of the data-dependent structural risk minimization framework and propose a proper reformulation of the SVM learning algorithm, so that the in-sample approach can be effectively applied. The experiments, performed both on simulated and real-world datasets, show that our in-sample approach can be favorably compared to out-of-sample methods, especially in cases where the latter ones provide questionable results. In particular, when the number of samples is small compared to their dimensionality, like in classification of microarray data, our proposal can outperform conventional out-of-sample approaches such as the cross validation, the leave-one-out, or the Bootstrap methods.

In-sample model selection for Support Vector Machines is a promising approach that allows using the training set both for learning the classifier and tuning its hyperparameters. This is a welcome improvement respect to out-of-sample methods, like cross-validation, which require to remove some samples from the training set and use them only for model selection purposes. Unfortunately, in-sample methods require a precise control of the classifier function space, which can be achieved only through an unconventional SVM formulation, based on Ivanov regularization. We prove in this work that, even in this case, it is possible to exploit well-known Quadratic Programming solvers like, for example, Sequential Minimal Optimization, so improving the applicability of the in-sample approach.

The Structural Risk Minimization framework has been recently proposed as a practical method for model selection in Support Vector Machines (SVMs). The main idea is to effectively measure the complexity of the hypothesis space, as defined by the set of possible classifiers, and to use this quantity as a penalty term for guiding the model selection process. Unfortunately, the conventional SVM formulation defines a hypothesis space centered at the origin, which can cause undesired effects on the selection of the optimal classifier. We propose here a more flexible SVM formulation, which addresses this drawback, and describe a practical method for selecting more effective hypothesis spaces, leading to the improvement of the generalization ability of the final classifier.

We derive here new generalization bounds, based on Rademacher Complexity theory, for model selection and error estimation of linear (kernel) classifiers, which exploit the availability of unlabeled samples. In particular, two results are obtained: the first one shows that, using the unlabeled samples, the confidence term of the conventional bound can be reduced by a factor of three; the second one shows that the unlabeled samples can be used to obtain much tighter bounds, by building localized versions of the hypothesis class containing the optimal classifier.

A common belief is that Machine Learning Theory (MLT) is not very useful, in pratice, for performing effective SVM model selection. This fact is supported by experience, because well-known hold-out methods like cross-validation, leave-one-out, and the bootstrap usually achieve better results than the ones derived from MLT. We show in this paper that, in a small sample setting, i.e. when the dimensionality of the data is larger than the number of samples, a careful application of the MLT can outperform other methods in selecting the optimal hyperparameters of a SVM.

A crucial issue in designing learning machines is to select the correct model parameters. When the number of available samples is small, theoretical sample-based generalization bounds can prove effective, provided that they are tight and track the validation error correctly. The maximal discrepancy (MD) approach is a very promising technique for model selection for support vector machines (SVM), and estimates a classifier's generalization performance by multiple training cycles on random labeled data. This paper presents a general method to compute the generalization bounds for SVMs, which is based on referring the SVM parameters to an unsupervised solution, and shows that such an approach yields tight bounds and attains effective model selection. When one estimates the generalization error, one uses an unsupervised reference to constrain the complexity of the learning machine, thereby possibly decreasing sharply the number of admissible hypothesis. Although the methodology has a general value, the method described in the paper adopts vector quantization (VQ) as a representation paradigm, and introduces a biased regularization approach in bound computation and learning. Experimental results validate the proposed method on complex real-world data sets.

In this work we show that a metaheuristic, the variable neighborhood search (VNS), can be effectively used in order to improve the performance of the hardware-friendly version of the support vector machine (SVM). Our target is the implementation of the feed-forward phase of SVM on resource-limited hardware devices, such as field programmable gate arrays (FPGAs) and digital signal processors (DSPs). The proposal has been tested on a machine-vision benchmark dataset for embedded automotive applications, showing considerable performance improvements respect to previously used techniques.

We present here a hardware-friendly version of the support vector machine (SVM), which is useful to implement its feed-forward phase on limited-resources devices such as field programmable gate arrays (FPGAs) or microcontrollers, where a floating-point unit is seldom available. Our proposal is tested on a machine-vision benchmark dataset for automotive applications.

In this paper we test a new multicategory SVM method, called augmented binary (AB), on microarray gene expression data. The AB SVM is one of the methods generating a multicategory classifier in one step, without dividing the multiclass problem into binary subproblems. This approach can be useful when the number of samples is very low, like in this kind of application. Furthermore, the use of a single SVM, instead of several binary ones, simplifies the search for optimal hyperparameters and allows a consistent output for all the classes.

In this letter, we propose a coordinate rotation digital computer (CORDIC)-like algorithm for computing the feed-forward phase of a support vector machine (SVM) in fixed-point arithmetic, using only shift and add operations and avoiding resource-consuming multiplications. This result is obtained thanks to a hardware-friendly kernel, which greatly simplifies the SVM feed-forward phase computation and, at the same time, maintains good classification performance respect to the conventional Gaussian kernel.

We apply here a probabilistic method to predict the effect of quantizing the parameters of a support vector machine with Gaussian kernel. Thanks to the particular structure of the SVM, the dependency of the output from the quantization noise can be predicted with good accuracy, and a simple closed-form formula can be derived, without imposing any hard-to-verify assumption.

The problem of how to effectively implement k-fold cross-validation for support vector machines is considered. Indeed, despite the fact that this selection criterion is widely used due to its reasonable requirements in terms of computational resources and its good ability in identifying a well performing model, it is not clear how one should employ the committee of classifiers coming from the k folds for the task of on-line classification. Three methods are here described and tested, based respectively on: averaging, random choice and majority voting. Each of these methods is tested on a wide range of data-sets for different fold settings.

In this paper we show how to map a LSSVM on digital hardware. In particular, we provide a theoretical analysis of quantization effects, due to finite register lengths, that leads to some useful bounds for computing the necessary number of bits for a correct hardware implementation. Then, we describe a new FPGA-based architecture, the KTRON, which implements the feed-forward phase of a LSSVM.

In the framework of support vector machine (SVM) classifiers, an unsupervised analysis of empirical data supports an ordering criterion for the families of possible functions. The approach enhances the structural risk minimization paradigm by sharply reducing the number of admissible classifiers, thus tightening the associate generalization bound. The paper shows that kernel-based algorithms, allowing efficient optimization, can support both the unsupervised clustering process and the generalization-error estimation. The main result of this sample-based method may be a dramatic reduction in the predicted generalization error, as demonstrated by experiments on synthetic testbeds as well as real-world problems.

In this paper we present a new method for solving multiclass problems with a support vector machine. Our method compares favorably with other proposals, appeared so far in the literature, both in terms of computational needs for the feedforward phase and of classification accuracy. The main result, however, is the mapping of the multiclass problem to a biclass one, which allows us to suggest a method for estimating the generalization error by using data-dependent error bounds.

The problem of tagging a top quark generation event in data coming from the collider detector at Fermilab is considered and tackled through the use of a support vector machine classifier. In order to select a fitting model, a twofold procedure has been adopted. The SVC hyperparameters have been selected through the bootstrap technique and then an additional tuning of the bias value and the error relevance has been performed by means both of a purity vs. efficiency curve and of the AUC value. The generalization capability of the model has been evaluated using the maximal discrepancy criterion.

We present in this paper an algorithm for Support Vector Machine (SVM) learning, which can be implemented using fixed-point math. The advantages of the fixed-point representation, respect to the more common floating-point one, allows us to address digital VLSI implementations of SVM. In particular, simple algorithms and simple architectures can be exploited for targeting programmable devices like Field Programmable Gate Arrays (FPGAs), which are the basis of many embedded systems. This paper focuses on the SVM learning algorithm: for the complete version of this work, including an actual FPGA realization.

Recent advances in characterizing the generalization ability of support vector machines (SVMs) exploit refined concepts, such as Rademacher estimates of model complexity and nonlinear criteria for weighting empirical errors. Those methods improve the SVM representation ability and tighten generalization bounds. On the other hand, quadratic-programming algorithms are no longer applicable, hence the SVM-training process cannot benefit from the notable efficiency featured by those specialized techniques. The paper considers the possibility of using quantum computing to solve the resulting problem of effective optimization, especially in the case of digital SV implementations. The behavioral aspects of conventional and enhanced SVMs are compared, supported by experiments in both a synthetic and a real-world problem. Likewise, the related differences between quadratic-programming and quantum-based optimization techniques are analyzed.

In this paper, we propose a digital architecture for support vector machine (SVM) learning and discuss its implementation on a field programmable gate array (FPGA). We analyze briefly the quantization effects on the performance of the SVM in classification problems to show its robustness, in the feedforward phase, respect to fixed-point math implementations; then, we address the problem of SVM learning. The architecture described here makes use of a new algorithm for SVM learning which is less sensitive to quantization errors respect to the solution appeared so far in the literature. The algorithm is composed of two parts: the first one exploits a recurrent network for finding the parameters of the SVM; the second one uses a bisection process for computing the threshold. The architecture implementing the algorithm is described in detail and mapped on a real current-generation FPGA (Xilinx Virtex II). Its effectiveness is then tested on a channel equalization problem, where real-time performances are of paramount importance.

The recurrent network of Xia et al. (1996) was proposed for solving quadratic programming problems and was recently adapted to support vector machine (SVM) learning by Tan et al. (2000). We show that this formulation contains some unnecessary circuits which, furthermore, can fail to provide the correct value of one of the SVM parameters and suggest how to avoid these drawbacks.

We propose a fast way to perform the gradient computation in Support Vector Machine (SVM) learning, when samples are positioned on an m-dimensional grid. Our method takes advantage of the particular structure of the constrained quadratic programming problem arising in this case. We show how such structure is connected to the properties of block Toeplitz matrices and how they can be used to speed-up the computation of matrix-vector products.

In this paper, we propose some very simple algorithms and architectures for a digital VLSI implementation of Support Vector Machines. We discuss the main aspects concerning the realization of the learning phase of SVMs, with special attention on the effects of fixed-point math for computing and storing the parameters of the network. Some experiments on two classification problems are described that show the efficiency of the proposed methods in reaching optimal solutions with reasonable hardware requirements.

We propose a VLSI friendly algorithm for the implementation of the learning phase of support vector machines (SVM). Differently from previous methods, that rely on sophisticated constrained nonlinear programming algorithms, our approach finds a simple updating rule that can be easily implemented in digital VLSI.

We derive here a new method for the analysis of weight quantization effects in multilayer perceptrons based on the application of interval arithmetic. Differently from previous results, we find worst case bounds on the errors due to weight quantization, that are valid for every distribution of the input or weight values. Given a trained network, our method allows to easily compute the minimum number of bits needed to encode its weights.