1,720,975 research outputs found
Sparse ι1 and ι2 center classifiers
No full textThe nearest-centroid classifier is a simple linear-time classifier based on computing the centroids of the data classes in the training phase, and then assigning a new datum to the class corresponding to its nearest centroid. Thanks to its very low computational cost, the nearest-centroid classifier is still widely used in machine learning, despite the development of many other more sophisticated classification methods. In this paper, we propose two sparse variants of the nearest-centroid classifier, based respectively on ι1 and ι2 distance criteria. The proposed sparse classifiers perform simultaneous classification and feature selection, by detecting the features that are most relevant for the classification purpose. We show that training of the proposed sparse models, with both distance criteria, can be performed exactly (i.e., the globally optimal set of features is selected) and at a quasi-linear computational cost. The experimental results show that the proposed methods are competitive in accuracy with state-of-the-art feature selection techniques, while having a significantly lower computational cost
Age class structure in SIRD models for the COVID-19 - An analysis of Tennessee data
Full text linkThe COVID-19 pandemic is bringing disruptive effects on the healthcare system, economy and social life of countries all over the world. Even though the elder portion of the population is the most severely affected by the coronavirus disease, the counter-measures introduced so far by the governments do not take into account age structure, and the restrictions act uniformly on the population irrespectively of age. In this paper, we introduce a SIRD model with age classes for studying the impact on the epidemic evolution of lockdown policies applied heterogeneously on the different age groups of the population. The proposed model is then applied to COVID-19 data from the state of Tennessee. The simulation results suggest that a selective lockdown, while having a lighter socioeconomic impact, may bring benefits in terms of reduction of the mortality rate that are comparable to the ones obtained by a uniform lockdown
Sparse l1- and l2-Center Classifiers
No full textIn this article, we discuss two novel sparse versions of the classical nearest-centroid classifier. The proposed sparse classifiers are based on l1 and l2 distance criteria, respectively, and perform simultaneous feature selection and classification, by detecting the features that are most relevant for the classification purpose. We formally prove that the training of the proposed sparse models, with both distance criteria, can be performed exactly (i.e., the globally optimal set of features is selected) at a linear computational cost. Especially, the proposed sparse classifiers are trained in O(mn)+O(młog k) operations, where n is the number of samples, m is the total number of features, and k łeq m is the number of features to be retained in the classifier. Furthermore, the complexity of testing and classifying a new sample is simply O(k) for both methods. The proposed models can be employed either as stand-alone sparse classifiers or fast feature-selection techniques for prefiltering the features to be later fed to other types of classifiers (e.g., SVMs). The experimental results show that the proposed methods are competitive in accuracy with state-of-the-art feature selection and classification techniques while having a substantially lower computational cost
Multiclass Sparse Centroids With Application to Fast Time Series Classification
Full text linkIn this article, we propose an efficient multiclass classification scheme based on sparse centroids classifiers. The proposed strategy exhibits linear complexity with respect to both the number of classes and the cardinality of the feature space. The classifier we introduce is based on binary space partitioning, performed by a decision tree where the assignation law at each node is defined via a sparse centroid classifier. We apply the presented strategy to the time series classification problem, showing by experimental evidence that it achieves performance comparable to that of state-of-the-art methods, but with a significantly lower classification time. The proposed technique can be an effective option in resource-constrained environments where the classification time and the computational cost are critical or, in scenarios, where real-time classification is necessary
Random convex programs for distributed multi-agent consensus
Full text linkWe consider convex optimization problems with N randomly drawn convex constraints. Previous work has shown that the tails of the distribution of the probability that the optimal solution subject to these constraints will violate the next random constraint, can be bounded by a binomial distribution. In this paper we extend these results to the violation probability of convex combinations of optimal solutions of optimization problems with random constraints and different cost objectives. This extension has interesting applications to distributed multi-agent consensus algorithms in which the decision vectors of the agents are subject to random constraints and the agents' goal is to achieve consensus on a common value of the decision vector that satisfies the constraints. We give explicit bounds on the tails of the probability that the agents' decision vectors at an arbitrary iteration of the consensus protocol violate further constraint realizations. In a numerical experiment we apply these results to a model predictive control problem in which the agents aim to achieve consensus on a control sequence subject to random terminal constraints
Control analysis and design via randomised coordinate polynomial minimisation
Full text linkA relevant family of control analysis and design problems can be reduced to the minimisation of a multivariate polynomial objective over a semialgebraic set. Such control problem formulations, however, are nonconvex in general and hard to solve in practice. In this paper, we propose a novel approach to polynomial control design based on iterations that involve either a fast coordinate-wise minimisation or a univariate minimisation along a randomly chosen direction. We provide a detailed iteration complexity analysis of the method, and we prove its convergence in probability to the global optimum. The practical effectiveness of the proposed method is also illustrated via a comparison with state-of-the-art tools available in the literature. An example of application to an automated space rendezvous manoeuvre is finally presented, showing how the method can be particularly relevant in the context of nonlinear model predictive control
Data-driven extraction of uniformly stable and passive parameterized macromodels
Full text linkA Robust algorithm for the extraction of reduced-order behavioral models from sampled frequency responses is proposed. The system under investigation can be any Linear and Time Invariant structure, although the main emphasis is on devices that are relevant for Signal and Power Integrity and RF design, such as electrical interconnects and integrated passive components. We assume that the device under modeling is parameterized by one or more design variables, which can be related to geometry or materials. Therefore, we seek for multivariate macromodels that reproduce the dynamic behavior over a predefined frequency band, with an explicit embedded dependence of the model equations on these external parameters. Such parameterized macromodels may be used to construct component libraries and prove very useful in fast system-level numerical simulations in time or frequency domain, including optimization, what-if, and sensitivity analysis. The main novel contribution is the formulation of a finite set of convex constraints that are applied during model identification, which provide sufficient conditions for uniform model stability and passivity throughout the parameter space. Such constraints are characterized by an explicit control allowing for a trade-off between model accuracy and runtime, thanks to some special properties of Bernstein polynomials. In summary, we solve the longstanding problem of multivariate stability and passivity enforcement in data-driven model order reduction, which insofar has been tackled only via either overconservative or heuristic and possibly unreliable methods
A time-varying SIRD model for the COVID-19 contagion in Italy
Full text linkThe purpose of this work is to give a contribution to the understanding of the COVID-19 contagion in Italy. To this end, we developed a modified Susceptible-Infected-Recovered-Deceased (SIRD) model for the contagion, and we used official data of the pandemic for identifying the parameters of this model. Our approach features two main non-standard aspects. The first one is that model parameters can be time-varying, allowing us to capture possible changes of the epidemic behavior, due for example to containment measures enforced by authorities or modifications of the epidemic characteristics and to the effect of advanced antiviral treatments. The time-varying parameters are written as linear combinations of basis functions and are then inferred from data using sparse identification techniques. The second non-standard aspect resides in the fact that we consider as model parameters also the initial number of susceptible individuals, as well as the proportionality factor relating the detected number of positives with the actual (and unknown) number of infected individuals. Identifying the model parameters amounts to a non-convex identification problem that we solve by means of a nested approach, consisting in a one-dimensional grid search in the outer loop, with a Lasso optimization problem in the inner step
A Modified SIR Model for the COVID-19 Contagion in Italy
Full text linkThe purpose of this work is to give a contribution to the understanding of the COVID-19 contagion in Italy. To this end, we developed a modified Susceptible-Infected-Recovered (SIR) model for the contagion, and we used official data of the pandemic up to March 30th, 2020 for identifying the parameters of this model. The non standard part of our approach resides in the fact that we considered as model parameters also the initial number of susceptible individuals, as well as the proportionality factor relating the detected number of positives with the actual (and unknown) number of infected individuals. Identifying the contagion, recovery and death rates as well as the mentioned parameters amounts to a non-convex identification problem that we solved by means of a two-dimensional grid search in the outer loop, with a standard weighted least-squares optimization problem as the inner step
Recurrent averaging inequalities in multi-agent control and social dynamics modeling
Full text linkMany multi-agent control algorithms and dynamic agent-based models arising in natural and social sciences are based on the principle of iterative averaging. Each agent is associated to a value of interest, which may represent, for instance, the opinion of an individual in a social group, the velocity vector of a mobile robot in a flock, or the measurement of a sensor within a sensor network. This value is updated, at each iteration, to a weighted average of itself and of the values of the adjacent agents. It is well known that, under natural assumptions on the network's graph connectivity, this local averaging procedure eventually leads to global consensus, or synchronization of the values at all nodes. Applications of iterative averaging include, but are not limited to, algorithms for distributed optimization, for solution of linear and nonlinear equations, for multi-robot coordination and for opinion formation in social groups. Although these algorithms have similar structures, the mathematical techniques used for their analysis are diverse, and conditions for their convergence and differ from case to case. In this paper, we review many of these algorithms and we show that their properties can be analyzed in a unified way by using a novel tool based on recurrent averaging inequalities (RAIs). We develop a theory of RAIs and apply it to the analysis of several important multi-agent algorithms recently proposed in the literature
- …
