New models and methods for classification and feature selection. a mathematical optimization perspective

Programa de doctorado “Matemáticas” PhD Dissertation NEW MODELS AND METHODS FOR CLASSIFICATION AND FEATURE SELECTION. A MATHEMATICAL OPTIMIZATION PERSPECTIVE. Author Sandra Benítez Peña Supervisors Prof. Dr. Rafael Blanquero Bravo Prof. Dr. Emilio Carrizosa Priego Prof. Dr. Pepa Ramírez Cobo Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 A mis padres y mi hermana, por todo su apoyo incondicional. A todos aquellos que desde mi niñez me inspiraron para llegar hasta aquí. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Agradecimientos Y aquí llegué, por fin. Y vuelvo a mi yo de 10 años, que mira aquel tablón del cole en el que se anuncian unas olimpiadas de matemáticas, en las que sueña participar en unos años, así como crecer para poder conocer cada vez más y más de aquella que es su pasión, quien cierra los ojos y dice para sí: “Lo logré. Sabía que podía.”. Pero esto no es algo que haya hecho sola, no, ni mucho menos. Por eso, quiero expresar mi gratitud a todos los que habéis formado parte de esto. Quizás no vaya uno por uno, y quizás se me escape alguien por medio, pero intentaré expresarlo de la mejor manera que pueda. En primer lugar a mis directores: Emilio, Rafa, Pepa. Así, en ese orden, os fui conociendo uno a uno. Y qué alegría hacerlo. Emilio: Gracias por ver en mí el potencial y las ganas, las suficientes como para acogerme en tu grupo de investigación, e intentar sacarle el máximo partido a lo que veías en mí. Gracias por todo el aprendizaje, desde aquellos días en que era estudiante de grado hasta ahora mismo, y todo lo que me queda por aprender de ti. Gracias por brindarme esta maravillosa oportunidad. Rafa: Gracias por, a pesar de no conocerme de nada, aceptar dirigirme aquel TFG junto con Emilio. Por, también desde ese entonces, aguantarme todos esos ratos echados en tu despacho (o por skype) intentando descifrar mis interminables scripts, y por lo muchísimo que me has enseñado de todo. Pepa: A ti te conocí la última, pero qué bien nos sentó conocerte a Reme y a mi, en todos los sentidos. Nos llenas de tranquilidad en aquellos momentos de nerviosismo, siempre con tu profesionalidad por delante, sentándote y trabajando mano a mano con nosotras, y echándonos horas y horas con tal de ayudarnos en todo lo posible y más. Gracias. Although you are not my supervisors, I carry you both as if you were. Thank you so much Dolores and Peter. I met you practically at the beginning of my PhD studies, so I have grown professionally (and personally) also with you both. Thank you for giving me the opportunity of learning from you both, and I hope I can continue doing it for a long time. Also, thanks for made from Copenhagen my second home, and from the CBS like my home institution. Gracias, Loli, no solo desde el lado profesional, sino también por hacerme un hueco en tu vida y de la de tu familia, por permitirme disfrutar de Copenhague cual ciudadana nativa con bicicleta incluída. Por esas cenas, IV Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 V cervezas, vinos y cafés, y por enseñarme tu maravilloso país de residencia, Dinamarca. Por otro lado, estas estancias en Copenhague, el poder asistir a congresos conociendo además las ciudades en las que se celebraban (ay, bendita época sin COVID) así como esta misma tesis en sí, no sería posible sin los diferentes proyectos y sus IP: MTM2015-65915-R (Ministerio de Economía y Competitividad), PID2019-110886RB- I00 (Ministerio de Ciencia, Innovación y Universidades), FQM-329 y P18-FR-2369 (Junta de Andalucía), PR2019-029 (Universidad de Cádiz), Fundación BBVA y EC H2020 MSCA RISE NeEDS Project (Grant agreement ID: 822214). Y gracias, por supuesto a quienes en menor o mayor medida han gestionado todo esto desde su lado administrativo y me han ayudado en miles de cosas más: El IMUS y sus equipos de Administración, así como al Departamento de Estadística e Investigación Operativa de la Universidad de Sevilla. Y como no podía faltar, ya que hablo del IMUS, una mención y agradecimiento a mis compañeros (ya, más que compañeros o amigos, mi familia IMUS). Algunos me habéis aguantado los 4 añitos al completo. Con otros he pasado menos tiempo, bien porque os fuísteis antes o bien porque hayáis llegado después, pero si algo es cierto, es que aún nos queda mucho por vivir juntos. Muchas gracias a todos, por vuestro lado profesional (sois unos máquinas), así como por vuestro lado personal. Es maravilloso teneros en mi vida, y saber que siempre os tendré. No quería hacer aquí menciones en concreto, pero creo que hay dos personas en particular que se lo merecen. Cristina: Sin ti y tu alegría, cantando y riendo a todas horas, estar trabajando en un despacho no será lo mismo. Reme, hemos sido prácticamente gemelas de tesis, juntas en todo momento, avanzando a la vez, y “sufriendo” y disfrutando casi al unísono cada uno de los momentos que hemos vivido. ¡Gracias, chicas! Siguiendo con menciones particulares, de sobra sabíais que estaríais aquí: Caro, Cris, Andrés, Sara, Vero, Ro, Javi, Pablo. Gracias a todos, una necesita tener a amigos al lado en todos los momentos, buenos y malos, y vosotros habéis demostrado ser los mejores estando ahí siempre que lo he necesitado. Gracias por apoyarme, creer en mi, y querer sacarme una sonrisa. Kevin, gracias por todo. Por escucharme hablar durante horas de mis cosas, a pesar de decir que no tienes idea de ellas (¡la tienes!) y por ayudarme siempre que has podido, de todas las formas habidas y por haber. Por aguantar interminables ensayos pre-charla y darme ánimos y consejos cuando yo ya no sabía de dónde sacarlos. Me ayudas a ser imparable. Mamá, papá, gracias por hacer todo lo posible y más por hacerme llegar hasta aquí. Por todos los sacrificios que hicísteis para que, desde que era una cría, pudiese disfrutar de mis queridas matemáticas. Sin duda sois, junto con mis directores, los mayores responsables de esto. Raquel, tener a una casi ingeniera en casa ayuda. Gracias por entenderme y ayudarme en mis cosas, y no hacerme sentir la rarita de la casa, con tanta Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 VI ciencia, razonamientos y fórmulas siempre rodeándome. A todos, muchísimas gracias. De una forma u otra me habéis ayudado a alcanzar esto, y sin vosotros no hubiera sido posible. Gracias por acompañarme en este viaje que solo acaba de comenzar. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Resumen Esta tesis tiene como objetivo el desarrollo de nuevos modelos para Clasificación Supervisada y Benchmarking, haciendo uso de herramientas de Optimización Matemática y Estadística. Más concretamente, abordamos la fusión de técnicas de estas dos disciplinas, con el objetivo de extraer conocimiento de los datos. De esta forma, obtenemos métodos innovadores que mejoran a los ya existentes, unificando además las Matemáticas teóricas con problemas de la vida real. El trabajo desarrollado en esta tesis se ha centrado en dos metodologias fundamentales en la Ciencia de los Datos: las máquinas de vectores soporte (SVM) y el Benchmarking. Con respecto a la primera, el classificador SVM se fundamenta en encontrar el hiperplano de máximo margen y se escribe como un problema cuadrático convexo. En el contexto de Benchmarking, el objetivo es calcular las diferentes eficiencias a través de un enfoque no paramétrico determinista. En esta tesis nos centraremos en el análisis envolvente de datos (DEA), consistente en un problema lineal. Esta tesis está estructurada de la siguiente manera. En el Capítulo 1 se presentan de forma breve los retos considerados en esta tesis, junto con su estado del arte. De la misma forma, se exponen los diferentes modelos que se utilizarán como base, así como la notación usada en los siguientes capítulos. En el Capítulo 2, se aborda el problema de la construcción de una versión del SVM que tiene en cuenta costes de error en la clasificación. Para ello, incorporamos nuevas restricciones de rendimiento de la classificación en el problema de optimización que define al SVM. En dichas restricciones imponemos cotas superiores sobre los errores de classificación. La formulación resultante consiste en un problema cuadrático convexo mixto con restricciones lineales. El Capítulo 3 continúa con base en el SVM, planteando el problema de dar no solo un etiquetado fijo (clasificación binaria) a cada uno de los individuos que conforman la muestra, sino una probabilidad de pertenencia a la misma. Más aún, proporcionamos intervalos de confianza para los valores de score así como para las probabilidades de pertenencia a las diferentes clases. Además, al igual que en el capítulo anterior, llevaremos los resultados obtenidos al terreno en el que se tienen en cuenta los costes de error en la clasificación. Para este propósito, resolveremos bien un problema cuadrático VIII Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Contents XV 3.3.3 Results when the posterior class probabilities are controlled . . . 49 3.4 ChapterSummary .............................. 51 4 Cost-sensitive feature selection in support vector machines 53 4.1 Introduction.................................. 55 4.2 Cost-sensitive Feature Selection . . . . . . . . . . . . . . . . . . . . . . . 56 4.2.1 The cost-sensitive FS procedure . . . . . . . . . . . . . . . . . . . 57 4.2.2 Cost-sensitive sparse SVMs: linear vs arbitrary kernels . . . . . . 59 4.3 Experiment Description . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.4 NumericalResults .............................. 62 4.4.1 Datadescription ........................... 62 4.4.2 Results under the cost-sensitive sparse SVM with linear kernel . 63 4.4.3 Results under the cost-sensitive sparse SVM with radial kernel . 67 4.4.4 Comparison with other methodologies . . . . . . . . . . . . . . . 68 4.5 ChapterSummary .............................. 72 5 Feature selection for benchmarking via DEA formulation 73 5.1 Introduction.................................. 75 5.2 The individual selection model . . . . . . . . . . . . . . . . . . . . . . . 77 5.2.1 The selection model for a DMU . . . . . . . . . . . . . . . . . . . 78 5.2.2 Extensions .............................. 79 5.3 The joint selection model . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.3.1 The selection model for all DMUs . . . . . . . . . . . . . . . . . 82 5.3.2 Alternative objective functions . . . . . . . . . . . . . . . . . . . 85 5.4 Numericalsection............................... 87 5.5 ChapterSummary .............................. 90 6 General Conclusions and Further Work 97 References 107 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Chapter 1 Introduction 1 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 1.1. Supervised Classification. Support Vector Machines 3 We are living in the era of Big Data, Data Science and Advanced Analytics. In Data Science, whose main purpose is to extract knowledge from datasets, some of the most important considered problems are Supervised Classification (Carrizosa and Romero Morales [2013]; Bertsimas and Shioda [2007]; Friedman et al. [2001]), including Class Probability Estimation (Kruppa et al. [2014]; Margineantu [2002]; Walker and Olshen [1992]), as well as Dimensionality Reduction (Huang et al. [2019]; Xu et al. [2019]; Sarveniazi [2014]) or Benchmarking (Bogetoft [2013], Moffett et al. [2008], Bogetoft and Otto [2010], Cook and Zhu [2006], Parsons [2002]). All previous topics are full of challenges, in particular from a Mathematical Optimization perspective, such as the construction of a mathematical model describing the different properties of the data, the study of relationships between different loss functions and the statistical performance of the model, the development of robust models, data scalability, among others as can be seen in Gambella et al. [2021]; Bartlett et al. [2006]; Ben-Tal et al. [2011]; Boţ and Lorenz [2011]; Bradley et al. [1999]; Carrizosa et al. [2016, 2017a]; Carrizosa and Romero Morales [2013]; Corne et al. [2012]; Marron et al. [2007]; Meisel and Mattfeld [2010]; Panagopoulos et al. [2016]; Bogetoft and Otto [2010]; Plastria and Carrizosa [2012]; Richtárik and Takáč [2016]; Sánchez et al. [2016]; Shen et al. [2003]. In general, in Data Science, we are given a set Ω0of individuals coming from a population Ω, each individual represented by a vector (xi, yi), where xi∈RNand yj∈RM. Depending on the nature of the data set, some techniques of Data Science may be useful or not. Furthermore, the substantial meaning of xiand yimay vary. For instance, in Supervised (binary) Classification, xi∈RNis the attribute vector and yi∈ C ={−1,+1} ⊂ Rmay be the membership of individual i. On the other hand, in Benchmarking, xi∈RN +are the values of the input attribute vector and yi∈RM +is the sampled output attribute vector. The aim of this thesis is to design or improve existing state-of-the-art approaches in the commented fields. Therefore, in the following sections we present a detailed review of both SVM and Benchmarking, with special interest in feature selection problems. 1.1 Supervised Classification. Support Vector Machines The usefulness of Classification lies in its wide variety of applicability, such as biology and medicine (Deo [2015]; Swan et al. [2013]; Tarca et al. [2007]; Kononenko [2001]), or even economics (Chaudhuri [2014]; Agarwal [2011]) and digital communication (Wei et al. [2019]; Chavda et al. [2018]). Some key examples of the use of classification in those and other fields are credit scoring (Baesens et al. [2003b,a]), in which the algorithm is used to detect good and bad customers; spam filtering (Zhang et al. [2004]), whose purpose is to distinguish between spam and desirable mails; or cancer screening (Kudva and Prasad [2018]; Guyon et al. [2002]; Mangasarian et al. [1995]), where we want to Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 4 Chapter 1. Introduction differentiate between cancer and control patients. For the task of classification, we need to build a classifier. Formally speaking, a classifier Ψ,i.e., a function Ψ : RN−→ C, is sought to assign labels c∈ C to incoming individuals for which the feature vector xis known but the label yis unknown and estimated through Ψ(x).The different classification procedures differ in the way the classifier Ψis obtained from the data set Ω0. Nearest-neighbor methods represent one of the most well-known family of classifiers (Zhang [2020]; Biau and Devroye [2015]; Guo et al. [2003]). In its basic version, the k-nearest neighbors searches for the kobjects in the so-called training sample I⊆Ω0closest to each of the incoming instances, where closeness is measured via a similarity measure. Then, those new individuals will be labeled with the most frequent class in those kinstances. Another well-known method to mention is the classification tree (Bertsimas and Dunn [2017]; Steinberg and Colla [2009]; Timofeev [2004]). This classifier is defined as a sequence of if-then statements, resulting in a hierarchy, encoded as a tree. Each element is sorted into a class by following the path of the tree, starting from the upmost statement. Another frequent approach consists of reducing the search of the classifier to the resolution of an optimization problem, namely, based on score functions. This is the case, among many others, of the state-of-the-art classifier for binary classification, known as Support Vector Machines (SVM), Carrizosa and Romero Morales [2013]; Cristianini and Shawe-Taylor [2000]; Vapnik [1995]; Vapnik and Vapnik [1998], on which we will focus throughout this thesis. In its simplest version, SVM addresses two-class problems, i.e., Chas two elements, say, C={−1,+1}. The SVM aims at separating both classes by means of a linear classifier, ω>x+β= 0, where ωis the so called score vector. We will assume throughout this thesis that C={−1,+1}and refer the reader to e.g. Allwein et al. [2001] for the reduction of multiclass problems to this case. The linear SVM classifier is obtained by solving the following convex quadratic programming (QP) formulation with linear constraints: min ω,β,ξ ω>ω+C+P i∈I:yi=+1 ξi+C−P i∈I:yi=−1 ξi s.t. yi(ω>xi+β)≥1−ξi, i ∈I(SVM(C+, C−)) ξi≥0i∈I, where Irepresents the set of training data, ξi≥0are artificial variables which allow data points to be misclassified, and C+, C−>0are regularization parameters to be tuned that control the trade-off between margin minimization and misclassification Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 1.1. Supervised Classification. Support Vector Machines 5 errors. The case C+=C−is frequently considered in the literature, but the use of different regularization parameters for the different classes may allow for a better control of misclassification costs or imbalancedness. See e.g. Lin et al. [2002]. Given an object i, it is classified in the positive or the negative class according to the sign of the so-called score function, f(x) = sign(ω>xi+β), while for the case ω>xi+β= 0, the object is classified randomly. A mapping into a high-dimensional feature space may be considered (Cortes and Vapnik [1995]), which allows us to transform this linear classification technique in a non-linear one using Mercer Theorem, Mercer [1909] and the so-called kernel trick, see e.g. Cristianini and Shawe-Taylor [2000]. In this way we can address problems with a very large number of features, such as those encountered in personalized medicine (Sánchez et al. 2016). Hence, the general formulation of SVM is max λ−1 2P j∈IP k∈I λjλkyjykK(xj, xk) + P l∈I λl s.t. P i∈I λiyi= 0 (GSVM(C+, C−)) 0≤λi≤C+, i ∈I:yi= +1 0≤λi≤C−, i ∈I:yi=−1, where K:Rm×Rm→Ris a kernel function and λare the usual variables of the dual formulation of the SVM. As already mentioned, the goal in supervised classification is to classify objects in the correct class. However, ignoring imbalancedness (either in the classes size, either in the misclassification cost structure) may have dramatic consequences in the classification task, see Carrizosa et al. [2008]; He and Ma [2013]; Prati et al. [2015]; Maldonado et al. [2017]. For instance, for clinical databases, there are usually more observations of healthy populations than of the disease cases, and therefore smaller classification errors may be obtained for the first case. To illustrate this phenomenon, consider the well-known Breast Cancer Wisconsin (Diagnostic) Data Set from the UCI repository (Lichman 2013), for which the number of sick cases (212) is smaller than the size of control cases (357). Table 1.1 depicts the estimated rates (through a 10-fold cross validation approach) using a standard SVM. Even though both rates are high, it might be of interest to increase the accuracy of predicting cancer, perhaps at the expense of deteriorating the classification rates in the other class. In addition to imbalancedness, another interesting problem arising in the context of the SVM is the extraction of probabilistic outputs. Given an object iwith attribute vector xi, then, as previously commented, the SVM produces a hard labeling in such a Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 6 Chapter 1. Introduction Mean Std % benign instances well classified 99% 1.7 % malign instances well classified 94.8% 4.9 Table 1.1: Performance of standard SVM with Radial Function Basis kernel for wisconsin dataset. Average values and standard deviations computed from 10 realizations. way that iis classified in the positive or the negative class according to sign(ω>xi+β). When an attribute vector x0is given, the value f(x0) = ω>x0+βis called the score value of x0, where f(x)is the score function. However, the SVM method does not result in probabilistic outputs as posterior probabilities P(y= +1 |x), which are of interest if a measure of confidence in the predictions is sought, see Murphy [2012]. This is of particular importance in several real-world applications such as the previously mentioned cancer screening or credit scoring, where the risk of a false-negative and a false-positive is significantly different. 1.2 Benchmarking and Performance Measurement As already said, another challenging problem in Data Science is Benchmarking. Organisations need to know whether they are using the best practices to produce their products and services, and to do so they benchmark their performance with that of others. There are many documented examples of the use of benchmarking in the literature from both the private and the public sector such as airlines, banks, hospitals, universities, manufacturers, schools, and municipalities, see Bogetoft [2013] and references therein. Benchmarking can be used both to make intra and inter organizational comparisons. The first one gains importance, for instance, when headquarters wants to promote cost efficiency in its different subunits. For the second one, a main example could be the one that involves a regulator seeking to induce cost-efficiency. Its use is also extended to make longitudinal, panel or dynamic comparisons. We can define Benchmarking as the relative performance evaluation of entities (or firms) that converts the same types of inputs (resources) xinto the same type of outputs (services) y. To calculate the relative efficiency of the firms, one can find in the literature numerous methods. Particularly, one can differentiate between parametric and non-parametric methods, as well as stochastic and non-stochastic methods. Two main approaches are Stochastic Frontier Analysis (SFA) (Coelli et al. [2005]), which is a parametric, stochastic approach, and the non-parametric, deterministic approach Data Envelopment Analysis (DEA) (Coelli et al. [2005]; Cooper et al. [2001]). Other methods that can be found in the literature are, for instance, Corrected Ordinary Least Squares (COLS) (Lovell et al. [1993]; Greene [2003, 1990]; Aigner and Chu [1968]) or Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 1.2. Benchmarking and Performance Measurement 7 Stochastic Data Envelopment Analysis (SDEA) (Olesen and Petersen [1995]; Land et al. [1993]; Fethi et al. [2001]). In both SFA and DEA approaches, we can assume a firm (a given instance i) uses Ninputs xi= (x(1) i, . . . , x(N) i)∈RN +to produce M outputs yi= (y(1) i, . . . , y(M) i)∈RM +. The set of feasible input-output combinations for such firm is T=n(x, y)∈RN +×RM +:xcan produce yo, which is denoted as the technology. SFA and DEA involve the different ways of building technologies Tbased on observations. Nevertheless, given any T,(x, y)∈Tis said to be efficient if and only if it cannot be dominated by some (x, y)∈Tand hence the efficient subset of T,TEis TE={(x, y)∈T: (x, y)is efficient in T}. In order to construct Tvia SFA, we make some a priori assumptions about the structure, providing a parametric functional based on the idea of estimating a stochastic cost or production frontier. On the other hand, DEA is based on Mathematical Programming. In what follows, we will focus on this particular approach for Benchmarking. In DEA, the general setting involves a set Fof firms that use Ninputs to produce Moutputs as specified before. In DEA, the estimate of T,T∗, is built following the so-called minimal extrapolation principle (Bogetoft [1996]; Bogetoft and Otto [2010]). Basic DEA models may differ in the assumptions they make about T, like free disposability or convexity. In what follows, we will assume a DEA model with constant returns to scale (CRS), so that the input-oriented efficiency of firm i,E(i)is equal to the optimal solution value of the following Linear Programming formulation, E(i)=maximize(αi,βi) M X m=1 β(m) iy(m) i(1.1) s.t. (DEA(i)) M X m=1 β(m) iy(m) j− N X n=1 α(n) ix(n) j≤0∀j∈I(1.2) N X n=1 α(n) ix(n) i= 1 (1.3) αi∈RN +(1.4) βi∈RM +,(1.5) where α(n) iis the weight for input nand β(m) ithe weight for output m. Problem (DEA(i)) has N+ 1 linear constraints and N+Mcontinuous variables, and thus can be solved efficiently even for large problem instances. In DEA literature, the evaluated entities are typically called Decision-Making Units (DMUs), so we will use equally the word DMU or firm. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 8 Chapter 1. Introduction 1.3 Dimensionality reduction The size of databases has suffered from a significant increase recently. This has resulted in huge databases with a high proportion of features that may turn out to be redundant, irrelevant or noisy. Dimensionality reduction has hence become a crucial procedure in Data Science tasks, since it identifies the relevant features, making thus the different procedures more interpretable, cheaper in terms of measurements and computational effort, and more effective since the noise is reduced. To perform dimensionality reduction, the original feature space is mapped onto a new space, with lower dimensionality. Such a mapping, can be implemented either by selecting a subset of the original feature space or building new features from the existing ones. There exist an assortment of techniques encompassed in what is known as Feature Selection, under the first choice. Inside this method, rather than using existing approaches like Genetic algorithms (Babatunde et al. [2014]; Tan et al. [2008]), Greedy selection/elimination (Caruana and Freitag [1994]), Lasso (Tibshirani [1996]), as well as filter or wrapper (Blum and Langley [1997]) methods, we will focus on embedded methods (Chandrashekar and Sahin [2014]; Saeys et al. [2007]), in which the Feature Selection procedure is integrated as part of the classifier. On the other hand, if we do not mind to reduce the size of the feature space at the expense of loose the original attributes, different methods can be applied such as Principal Component Analysis (Wold et al. [1987]; Abdi and Williams [2010]), Factor Analysis (Harman [1976]; Fodor [2002]) or Linear Discriminant Analysis (Balakrishnama and Ganapathiraju [1998]). 1.3.1 Feature selection for support vector machines The SVM classifier uses all the features in the data, which may be rather problematic if measuring the features involve some non-negligible costs. This is particularly relevant when the dimension of the data set is large. It is then advisable to perform any type of dimensionality reduction, as it has been undertaken by Aytug [2015]; Bertolazzi et al. [2016]; Bradley et al. [1998]; Carrizosa et al. [2011]; Fung and Mangasarian [2004]; Guyon and Elisseeff [2003]; Le Thi et al. [2015]; Maldonado and Weber [2009]; Maldonado et al. [2011]; Weston et al. [2001]. In the previous works, the set of features is reduced so that an appropriate trade-off between classification accuracy and sparsity is obtained. An amount of different FS procedures are found in the literature, some independent of the classification procedure (FS is performed in advance, based e.g. on the correlation between each feature and the label) and others embedded in the classification procedure, like the Holdout SVM (HOSVM), Maldonado and Weber [2009], Kernel- Penalized SVM (KP-SVM), Maldonado et al. [2011], or the methods presented in Chan et al. [2007], Maldonado et al. [2017] or Ghaddar and Naoum-Sawaya [2018]. Embedded Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 1.3. Dimensionality reduction 9 methods (Chandrashekar and Sahin [2014],Lal et al. [2006]) and other feature selection techniques main difference is the way feature selection and learning interact. In embedded methods, the learning and the feature selection parts cannot be separated, opposite to what happens for non-embedded procedures, which do not incorporate learning or use a learning machine to rank the quality of the different subsets of features without adding knowledge about the specific structure of the classifier. 1.3.2 Feature selection in Benchmarking Another Data Science research field where Fature Selection becomes relevant is DEA, Cook et al. [2019]; Emrouznejad and Yang [2018]; Jiang and Lin [2015]; Landete et al. [2017]; Li et al. [2017b]; Petersen [2018]; Ruiz and Sirvent [2016, 2019]. DEA model specification, in the form of feature (where the term feature is used to refer to either outputs, inputs or environmental variables) selection, has a significant impact on the shape of the so-called efficient frontier as well as the insights given to the inefficient DMUs Golany and Roll [1989]. Moreover, feature selection is known to improve the discriminatory power of DEA models Bogetoft and Otto [2010]. In benchmarking projects, a good model should make conceptual sense not only from the theoretical but also from a practical point of view. The interpretation must be easy to understand and the properties of the model must be natural. We typically seek models that have significant features with the right signs and that do not leave a large unexplained variation. The complexity of this model specification phase partially explains the lack of enough guidance in the literature at this respect, Cook et al. [2014]; Luo et al. [2012]; Soleimani-Damaneh and Zarepisheh [2009], and most of the effort goes into the analysis and interpretation of a given DEA model. With the strand of literature on feature selection, the most common approach is to use a priori rules based on Statistical Analysis (such as correlations, dimensionality reduction techniques, and regression), and Information Theory (such as AIC or Shannon entropy). Alternatively, an ex-post analysis of the sensitivity of the efficient frontier to additional features can be run to detect whether relevant features have been left out. See Adler and Yazhemsky [2010]; Fernandez-Palacin et al. [2018]; Li et al. [2017a]; Nataraja and Johnson [2011]; Pastor et al. [2002]; Sirvent et al. [2005]; Soleimani-Damaneh and Zarepisheh [2009]; Wagner and Shimshak [2007], and references therein. Recently, there have been attempts to use LASSO techniques from Statistical Learning to build sparse benchmarking models, i.e., models using just a few features, J.-Y. Cai [2016]; Lee and Cai [2020]; Qin and Song [2014]. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 16 Chapter 2. On support vector machines under a multiple-cost scenario 2.2 Constrained Support Vector Machines In this section the Constrained Support Vector Machine (CSVM) model is formulated as a Mixed Integer Nonlinear Programming (MINLP) problem (Bonami et al. 2008; Burer and Letchford 2012), specifically in terms of a Mixed Integer Quadratic Programming (MIQP) problem. This section is structured as follows. In Section 2.2.1 some theoretical foundations that motivate the novel constraints are given. Then, in Section 2.2.2 the formulation of the CSVM is presented. We will depart from the linear kernel case to later extend it to the general kernel case via the kernel trick. Finally, in Section 2.2.3, some issues about the CSVM formulation, as its feasibility, shall be discussed. 2.2.1 Theoretical Motivation As commented before, the aim of the work in this chapter is to build a classifier so that the user may have control over the performance over the two classes. Specifically, given a set Ω0={(xi, yi)}iof data (a random sample of a vector (X, Y )with unknown distribution), the target is to obtain a classifier such that p≥p0, where pis the value of a performance measurement and p0is a threshold chosen by the user. The performance measure pis chosen by the user at her convenience and may be selected among the following rates: true positive rate (TPR) or sensitivity, true negative rate (TNR) or specificity and accuracy (ACC), which are defined as follows: TPR :p=P(ω>X+β > 0|Y= +1) TNR :p=P(ω>X+β < 0|Y=−1) (2.1) ACC :p=P(Y(ω>X+β)>0), see for example, Bewick et al. [2004]. In this work, for the sake of clarity, the positive class shall be identified with the class of interest to be controlled. For instance, in cancer screening studies, cancer is labelled as positive class whereas absence of cancer is labelled as negative. Also, in credit-scoring applications the positive class will be the defaulting clients. More examples will be discussed in Section 2.3. If the random variable Z, defined as Z=(1, if an observation is well classified, 0, otherwise, is considered, then, the values of pas in (2.1) corresponding to the probability of correct Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 2.2. Constrained Support Vector Machines 17 classification can be rewritten as TPR :p=E[Z|Y= +1] TNR :p=E[Z|Y=−1] ACC :p=E[Z] and estimated from an independent and identically distributed (i.i.d.) sample {Zi}i∈S, by TPR : ˆp=¯ Z+=P i∈S+ Zi |S+| TNR : ˆp=¯ Z−=P i∈S− Zi |S−| ACC : ˆp=¯ Z=P i∈S Zi |S|, where S+and S−denote, respectively, the subsets {i∈S:yi= +1}and {i∈S:yi= −1},S⊆Ω0. From a hypothesis testing viewpoint, our aim is to build a classifier such that, for a given sample, one can reject the null hypothesis in (H0:p≤p0 H1:p>p0. Under the classic decision rule, H0is rejected if ˆp≥p∗ 0assuming that α=P(type I error). From Hoeffding Inequality (Hoeffding 1963), P(ˆp≥p+c)≤exp(−2nc2).(2.2) As α=P(type I error) = P(ˆp≥p∗ 0|p=p0), substituting pby p0in (2.2) yields P(ˆp<p0+c)≥1−exp(−2nc2)=1−α, (2.3) where p0+c=p∗ 0. Therefore, we can take p∗ 0=p0+slog α −2n.(2.4) Note that nequals |S+|,|S−|or |S|, respectively, when considering the TPR, the TNR or the accuracy. Here, the selection of the Hoeffding Inequality is motivated by its distribution-free character, but other options as the Binomial-Normal approximation could have been Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 18 Chapter 2. On support vector machines under a multiple-cost scenario chosen instead. 2.2.2 CSVM formulation In this section, the CSVM formulation is presented. As it will be seen, the formulation includes novel performance constraints, which make the optimization problem a MIQP problem in terms of some integer variables. We assume to be given a dataset Ω0with known labels. From such set we identify the training set I⊆Ω0, used to build the classifier, and the anchor set J⊆Ω0, used to impose a lower bound on the classifier performance. These sets will be considered disjoint. With the purpose of building the CSVM, the performance constraints will be formulated in terms of binary variables {zj}j∈J, which are realizations of the variable Z in Section 2.2.1 and defined as: zj=(1, if instance jis counted as well classified 0, otherwise. In order to formulate the CSVM, novel constraints are added to the standard softmargin SVM formulation as follows: min ω,β,ξ,z ω>ω+C+P i∈I:yi=+1 ξi+C−P i∈I:yi=−1 ξi s.t. yi(ω>xi+β)≥1−ξi, i ∈I(2.5) ξi≥0i∈I(2.6) yj(ω>xj+β)≥1−M1(1 −zj), j ∈J(CSVM0)(2.7) zj∈ {0,1}j∈J(2.8) ˆp`≥p∗ 0``∈L. (2.9) In the previous optimization problem, (2.5) and (2.6) are the usual constraints in the SVM formulation. Constraints (2.7) ensure that observations j∈Jwith zj= 1 will be correctly classified, without imposing any restriction when zj= 0, provided that M1 is big enough. A collection of requirements on the performance of the classifier over J can be specified by means of (2.9). Also, Lis the set of indexes of the constraints that has the form of (2.9). These constraints can be modeled via the binary variables zj, Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 2.2. Constrained Support Vector Machines 19 for instance: TPR :P j∈J+ zj≥p∗ 0|J+| TNR :P j∈J− zj≥p∗ 0|J−| ACC :P j∈J zj≥p∗ 0|J|, where J+and J−denote, respectively, the subsets {i∈J:yi= +1}and {i∈J:yi= −1}. As before, by considering the (partial) dual problem of (CSVM0) and the kernel trick, the general formulation of the CSVM is obtained as follows (the intermediate steps can be found in Appendix A): min λ,µ,β,ξ,z P s∈IP s0∈I λsysλs0ys0K(xs, xs0) + P t∈JP t0∈J µtytµt0yt0K(xt, xt0) +2 P s∈IP t∈J λsysµtytK(xs, xt)+C+P i∈I:yi=+1 ξi+C−P i∈I:yi=−1 ξi s.t. zj∈ {0,1}j∈J ˆp`≥p∗ 0``∈L yi P s∈I λsysK(xs, xi) + P t∈J µtytK(xt, xi) + β!≥1−ξii∈I yj P s∈I λsysK(xs, xj) + P t∈J µtytK(xt, xj) + β!≥1−M1(1 −zj)j∈J(CSVM) ξi≥0i∈I P i∈I λiyi+P j∈J µjyj= 0 0≤λi≤C+/2i∈I:yi= +1 0≤λi≤C−/2i∈I:yi=−1 0≤µj≤M2zjj∈J. Here K:RN×RN→Ris again a kernel function, M1and M2are big enough numbers, and (λ, µ)are the usual variables in the dual formulation of the SVM. 2.2.3 Solving the CSVM In this section we give details about the complexity of our problem as formulated in (CSVM). The problem belongs to the class of MIQP problems, and thus it can be addressed by standard mixed integer quadratic optimization solvers. In particular, the solver Gurobi (Gurobi Optimization 2016) and its Python language interface (Van Rossum and Drake 2011) have been used in our numerical experiments. In contrast to the standard SVM formulation, which is a continuous quadratic problem, the Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 20 Chapter 2. On support vector machines under a multiple-cost scenario CSVM is harder to solve due to the presence of binary variables. Hence, the optimal solution may not be found in a short period of time; however, as discussed in our numerical experience, good results are obtained when the problems are solved heuristically by imposing a short time limit to the solver. Performance constraints (2.9) may define an infeasible problem since the values of the p∗ 0`may be unattainable in practice. Hence, the study of the feasibility of Problem (CSVM) is an important issue. As an example, consider data composed by two different classes, each one represented respectively by black and white dots in the top picture in Figure 2.1. If the optimization problem for the linear kernel SVM is solved, the resulting classifier is a hyperplane that aims at separating both classes and maximizes the margin. An approximate representation of the data and the classifier is shown in the middle panel in Figure 2.1. If the aim is to correctly classify all the data corresponding to a given class, it is intuitively easy to see that this objective can be reached by moving the SVM hyperplane. In fact, it can be seen in the bottom picture in Figure 2.1 how hyperplanes 1 and 2 classify correctly all white points, and hyperplane 3 classifies all the black dots in the correct class. Among all those hyperplanes, the SVM selects the one which maximizes the margin. So, intuitively, it is evident that if just one constraint of performance is imposed in only one of the classes, the problem is always feasible. However, and using the data in Figure 2.1 again, as well as the linear kernel SVM, it is clear that it is impossible to classify correctly all the instances at the same time; thus, the problem is then infeasible. However, there exist results, as Theorem 5 in Burges [1998], that show that the class of Mercer kernels for which K(x, x0)→0as kx−x0k→∞, and for which K(x, x)is O(1), builds classifiers that get a total correct classification in all the classes in the training sample, without regard how arbitrarily the data have been chosen. Thus, if a kernel satisfies the previous conditions, then feasibility is guaranteed. In particular, Radial Function Basis (RBF) kernel meets these conditions. Therefore, to be on the safe side, if the performance thresholds imposed are not too low, they should refer only to one class misclassification rates (so that we can shift the variable βto make the problem feasible) or to use a kernel, such as the RBF, known to have large VC dimension (Burges 1998; Cristianini and Shawe-Taylor 2000), defined as the maximal training sample size for which perfect separation can always be enforced. 2.3 Computational results This section illustrates the performance of the novel method, the CSVM, in comparison with benchmark approaches. To do that, an assortment of datasets with different properties concerning size and imbalanceness shall be analyzed. Section 2.3.1 describes the experiments to be carried out, while Section 2.3.2 details the choice of parameters. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 2.3. Computational results 21 V1 V2 V1 V2 Linear SVM hyperplane V1 V2 Hyperplane 1 Hyperplane 2 Hyperplane 3 1 Figure 2.1: Study of feasiblity and unfeasibility of the CSVM. Section 2.3.3 is devoted to clarify different aspects of the cross-validation procedure for estimating the performance of the approach, and Section 2.3.4 presents the datasets to be analyzed. Finally, Section 2.3.5 contains the obtained results and a deep discussion about them. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 22 Chapter 2. On support vector machines under a multiple-cost scenario 2.3.1 Description of the experiments The objective of this chapter, as has been stated before, is to build a classifier whose performance can be controlled by means of some constraints, as in Problem (CSVM). As explained in Section 2.2.1, if we want a performance measurement pto be greater than a value p0with a specified confidence 100(1 −α)%, we should use an estimator of p,ˆp, and impose it to be greater than p∗ 0=p0+slog α −2n, according to (2.4). Experiments whose aim will be to increase the performance rate of interest in one class will be performed. However, as it will be shown, a damage may be produced in the other class. In particular, since the interest is to improve the classification in the positive class, the TPR will be the rate to be included in the novel constraints. Assume that an estimator of the TPR, TPR0is given. The aim will be to impose TPR ≥TPR0+δ, were δ= 0.025, although other values can also be tested. Therefore, our experiments will consist of: Impose TPR ≥min {1,TPR0+ 0.025}=p0, which implies that, for α= 0.05, the performance constraints in the optimization problem defining the novel CSVM are: [ TPR ≥min (1,TPR0+slog 0.05 −2n+ 0.025)=p∗ 0. The novel CSVM will be compared with benchmark approaches. The first method to be compared with is the classic SVM where two different values of C(C+and C−) are used for each class. This approach shall be noted as SVM(C+, C−)(see Section 1.1). The second benchmark method consists of moving the original hyperplane resulting from performing the standard SVM until the value p∗ 0obtained by Hoeffding Inequality is achieved. This approach will be called from now on Sliding βstrategy. 2.3.2 Parameters Setting One of the most popular kernels K(x, x0)in literature is the well-known RBF kernel (Cristianini and Shawe-Taylor 2000; Hastie et al. 2001; Hsu et al. 2003; Smola and Schölkopf 2004; Horn et al. 2016), given by K(x, x0) = exp −γkx−x0k2, where γ > 0is a parameter to be tuned. This will be the kernel chosen for implementing the CSVM, although the method is valid for an arbitrary kernel. The time limit for the solver was set equal to 300 seconds. In addition, the M1and M2values in Problem (CSVM) were set both equal to 100. The choice of these values is motivated as follows. First, for the sake of computational tractability, the time limit Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 2.3. Computational results 23 should not be too high, but high enough so that the optimizer is able to solve the problem or at least to provide good feasible solutions. In our experiments, the choice of a time limit equal to 300s gave a good balance between the computational cost and the quality of the solutions. In the case of the values of M1and M2, if small values are chosen, there may be many discarded hyperplanes, including the optimal one. However, if M1and M2are too big, it might cause computational difficulties (Camm et al. 1990) because of numerical instabilities and large gaps in the continuous relaxation, making the branch and bound too slow. A compromise solution is obtained by considering M1=M2= 100 in our problems. Setting M1and M2equal to 100, not a huge number, may indeed exclude the optimal solution of the original problem. This is not a big issue, since the original problem is nothing but a surrogate of our real aim, namely, classifying correctly forthcoming individuals. On the other hand, this constraint may also be seen as a regularization constraint, since it forces the variables involved to take relatively small values, as already happens with the variables λi, already force to be below C/2. In other words, though at the expense of excluding the optimal solution of the proxy optimization problem, setting a not too large value for M1and M2can be seen as an extra regularization, thus preventing overfit. Note that an alternative formulation, avoiding big Mconstraints is obtained by using the Specially Ordered Sets of Type 1 (SOS1) (Bertsimas and Weismantel [2005], see also Silva [2017] and Bertsimas et al. [2016] for some examples of SOS1). However, we prefer to maintain the big M1and M2for two reasons. On the one hand, the use of SOS1 would involve quadratic constraints, which would make the problem even more difficult to solve. For example, constraint 0≤µt≤M2ztwould become (µt,1−zt):SOS1 and 0≤µt. This is equivalent to µt(1 −zt)=0and 0≤µt, which includes, as we can see, a non-convex quadratic constraint. On the other hand, not every solver has implemented the SOS1 method or is capable to solve quadratic mixed integer problems with non-convex quadratic constraints. In addition, even if it can manage SOS1-type constraints, it might perform the conversion to the problem with a big Mautomatically, and thus we would be again with big Mconstraints, now controlled by the solver and not by ourselves. 2.3.3 Performance estimation The estimation of the performance of the novel CSVM is based on a K-fold cross validation (CV) as follows, see Kohavi et al. [1995]. Generally, K=10, but for those datasets with more than 1000 samples, K= 5 so that the running times are lower. Note that, apart from tuning γ, the regularization parameters C+and C−introduced in Section 2.1 also need to be tuned. In order to make the CSVM procedure quicker, our experiments are based on choosing C+=C/|I+|and C−=C/|I−|, so only one parameter Cshall be tuned for the CSVM, but not for the SVM(C+, C−), in which Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 24 Chapter 2. On support vector machines under a multiple-cost scenario both C+and C−are tuned independently. As it will be seen later, this is not a crucial issue. Hence, for a given pair of parameters (C, γ), the process consists mainly on solving a standard SVM using all the instances (I∪J), and collect the values of λ (from the dual formulation of the SVM) as well as the value of β. Once the SVM is solved, and with the purpose of providing an initial solution for the CSVM, the value of βis slightly changed (maintaining the values of λ’s fixed) until the desired number of instances well classified is reached. Then, the values of βand λ’s obtained are set as initial solutions for CSVM. In addition, depending on whether each instance in Jis well classified or not, we set their values of zas 0or 1as initial values for the CSVM. We should make the selection of the best pair (C, γ)in each of the previous folds. In order to do that, a 10-fold CV (5-fold CV for datasets with more of 1000 samples, in order to reduce the running times) as before is made for each pair in a grid given by the 121 different combinations of C= 2(−5:5) and γ= 2(−5:5) (C+= 2(−5:5),C−= 2(−5:5) and γ= 2(−5:5) for GSVM(C+, C−)). The general criterion used to select the best pair of parameters is the accuracy. However, in cases where the datasets are severely imbalanced in the classes size (when one of the classes has a weight less than a 30% of the total size), the G-mean (Tang et al. 2009), which is defined as √TPR×TNR, is used to perform the parameter tuning instead. Finally, the average values of TPR and TNR obtained in the first CV, in addition to their standard deviations, are calculated. For a better understanding, the previous algorithm is summarized in Algorithm 3. Finally, we want to clarify that for our experiments we have selected Ias the first half of I∪Jand Jas the second one. 2.3.4 Data description The performance, in terms of correct classification probabilities and accuracy, is illustrated using 6 real-life datasets from the UCI and Keel repositories (Lichman 2013 and Alcalá-Fdez et al. 2009). In particular, the datasets are australian (Statlog (Australian Credit Approval) Data Set), votes (Congressional Voting Records Data Set), wisconsin (Breast Cancer Wisconsin (Diagnostic) Data Set), german (Statlog (German Credit Data) Data Set), pageBlocks (Page Blocks Classification (Imbalanced: 0) data set) and biodeg (QSAR biodegradation Data Set). Details concerning the distribution of the classes in the considered datasets are provided by Table 4.1. The first two columns give the name and number of attributes for each set. The values |Ω0|,|Ω0V|and |Ω0+|represent, respectively, the size for each dataset, the size of the validation sample in each step of the 10(or 5)-fold CV, and the number of positive instances in Ω0. Finally, the percentage of positive instances is compiled in the last column. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 2.3. Computational results 25 Algorithm 1: Pseudocode for CSVM 1Split data (D) into “folds” subsets, D={D1, . . . , Dfolds}. 2for kf = 1,. . .,folds do 3Set V alidation =Dkf and I∪J=D−{Dkf }. 4for each pair (C, γ)in grid ({2(−5:5)},{2(−5:5)})do 5Split D−{Dkf }=D∗into “folds2” subsets, D∗={D∗ 1, . . . , D∗ folds2}. 6for kf2 = 1,. . ., folds2 do 7Set V alidation∗=D∗ kf2and I∗∪J∗=D∗−{Dkf2}. 8Run standard SVM over I∗∪J∗. 9Move βof SVM until the instances are correctly classified. 10 Run problem CSVM over I∗,J∗with initial solutions from before. 11 Validate over V alidation∗, getting the accuracy (ACC[kf2]). 12 end 13 Calculate the average accuracy (Pkf2ACC[kf2])/folds2 = ACC. 14 if ACC ≥bestACC then 15 Set bestACC =ACC,bestγ =γand bestC =C. 16 end 17 end 18 Run standard SVM over I∪Jwith the parameters bestγ and bestC. 19 Move βof SVM until the instances are correctly classified. 20 Run problem CSVM over I,Jwith initial solutions from the previous step. 21 Validate over V alidation, getting the correct classification probabilities (TPR[kf],TNR[kf]). 22 end 23 Calculate the average values for TPR and TNR. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 3.1. Introduction 33 As formerly expounded, classification in SVM is based on a score procedure, yielding a deterministic classification rule, which can be transformed into a probabilistic one (as implemented in off-the-shelf SVM libraries), but is not probabilistic in nature. On the other hand, the tuning of the regularization parameters in SVM is known to imply a high computational effort and generates pieces of information that are not fully exploited, not being used to build a probabilistic classification rule. In this chapter we propose a novel approach to generate probabilistic outputs for the SVM. The new method has the following three properties. First, it is designed to be cost-sensitive, and thus the different importance of sensitivity (or true positive rate, TPR) and specificity (true negative rate, TNR) is readily accommodated in the model. As a result, the model can deal with imbalanced data which are common in operational business problems as churn prediction or credit scoring. Second, the SVM is embedded in an ensemble method to improve its performance, making use of the valuable information generated in the parameters tuning process. Finally, the probabilities estimation is done via bootstrap estimates, avoiding the use of parametric models as competing approaches. This allows us to compute confidence intervals for the score and class probabilities for a given individual. Numerical tests on a wide range of datasets show the advantages of our approach over benchmark procedures. 3.1 Introduction There exist many real-world contexts where it is relevant to get probabilistic outputs as posterior probabilities P(y= +1 |x), which are of special interest if a measure of confidence in the predictions is sought, see Murphy [2012]. This is of particular importance in several business problems such as churn prediction, e.g., Huang et al. [2012], to calibrate the probability of churning of a customer, or credit scoring, e.g., Thomas et al. [2017], where the probability of defaulting is to be estimated. In these situations, it is important not only to get a hard label for the individual but also, an estimation of the degree of confidence in the assignation. Several attempts to obtain the posterior probabilities P(y= +1 |x)for SVM have been already carried out previously. One of them is based on assigning posterior class probabilities assuming a specific parametric family for the posterior probability. For example, Wahba [1992], Wahba et al. [1999] proposed a logistic link function, P(y= +1 |x) = 1 1 + exp(−f(x)).(3.1) Also, Vapnik and Vapnik [1998] suggested to estimate P(y= +1 |x)in terms of a series of the trigonometric functions, where the coefficients of the trigonometric expansion minimizes a regularized function. Another considered option has been to fit Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 34 Chapter 3. Cost-sensitive class probability estimation in support vector machines Gaussians to the class-conditional densities P(f(x)|y= +1) and P(f(x)|y=−1), as proposed in Hastie and Tibshirani [1998]. From such a choice, the posterior probability P(y= +1 |f(x)) is assumed to be a sigmoid, whose slope is determined by the tied variance. One of the best-known heuristics to obtain probabilities is due to Platt [2000], which considers f(x)as the log-odds ratio log P(y= +1 |x) P(y=−1|x). This implies that P(y= +1 |x) = 1 1 + exp(Af(x) + B),(3.2) and Aand Bcan be estimated by maximum likelihood on a validation set. This technique is implemented by well-known statistical packages such as the ksvm() function in R, see Karatzoglou et al. [2006], predict_proba in scikit-learn in Python (Pedregosa et al. [2011]) or in the software LIBSVM (see Chang and Lin [2011]), which uses a better implementation of the method, as presented in Lin et al. [2007]. Although SVM is designed for binary classification, there are several extensions for multiclass problems, e.g. Carrizosa et al. [2008]; Lorena and de Carvalho [2008]; Wang and Shen [2007], and also some attempts to construct class probabilities are found in the literature. In particular, multiclass versions of Platt’s approach can be found in Milgram et al. [2005] and have been implemented in software packages like LIBSVM (Chang and Lin [2011]). Platt’s approach has been criticized for failing to provide insight and for interpreting f(x)as a log-odds ratio, which may be not accurate for some datasets, see Murphy [2012]; Tipping [2001]; Franc et al. [2011]. To illustrate such a phenomenon, consider Figure 3.1, which shows the fit of the sigmoid function (3.2) to the empirical class probabilities of two different, well-referenced datasets: adult and wisconsin, respectively (see Section 3.3.1). It can be seen that, while for adult dataset the fit provided by the method given in (3.2) performs reasonably well, the performance is poor for wisconsin. Sollich [2002] considers a different probabilistic framework for SVM classification, based on Bayesian theory. In particular, it relates the SVM kernel to the covariance function for a Gaussian process prior and as a result, optimal values of the tuning parameter Cand class probabilities are obtained in a natural way. Again, this method as the previously commented approaches make modeling assumptions that might not be satisfied by the data. Finally, other procedures seeking probabilistic outputs are found in the literature, as Seeger [2000], Kwok [1999, 1998], Herbrich et al. [1999]. None of the previously mentioned works produce cost-sensitive models, which are of crucial importance in many managerial decision-making problems. For instance, in a churn prediction context, classifying a churner customer as non-churner may have important negative consequences. In a similar way and in order to avoid high costs, it is more important for a financial institution to correctly classify a defaulting customer than a non-defaulting one. Comparable situations arise in other settings different from business and management domains as medical diagnosis, in which failing to detect a Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 3.1. Introduction 35 −4 −2 0 2 4 0.0 0.2 0.4 0.6 0.8 1.0 Adult dataset scores (f(x)) P(y=1|f(x)) f(x) −4 −2 0 2 4 0.0 0.2 0.4 0.6 0.8 1.0 Wisconsin dataset scores (f(x)) P(y=1|f(x)) f(x) Figure 3.1: Fit (in solid line) of the sigmoid function to the empirical class probabilities (dots) of adult and wisconsin datasets. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 36 Chapter 3. Cost-sensitive class probability estimation in support vector machines disease may have fatal aftermaths. Because of that, cost-sensitive classification has become a trending issue lately and a number of references can be found regarding this, see Maldonado et al. [2021]; Coussement [2014]; Bradford et al. [1998]; Freitas et al. [2007]; Carrizosa et al. [2008]; Datta and Das [2015]; Benítez-Peña et al. [2019a,b]. Cost-sensitivity is closely related to the problem of imbalancedness in datasets. Imbalancedness may produce unnacurate classification rates for the minority class that is often the most critical one, Ghatasheh et al. [2020]. Several attempts in the literature have considered probabilistic outputs for the SVM in a context of imbalancedness. For example, Tao et al. [2005] propose robust SVM that turn out insensitive to the class imbalancedness. Their approach, the posterior probability support vector machine (PPSVM), is distribution-free and weighs imbalanced training samples. A multiclass approach based on the method in Tao et al. [2005] is proposed by Gonen et al. [2008]. Also, a more sophisticated and computationally expensive alternative is proposed by Kim et al. [2015], which combines layers of SVM with class probability output networks (CPONs), in which strong statistical assumptions are imposed. In this work not only we provide a method for obtaining point estimates for the class probabilities for the SVM (as other works have done before), but also we construct confidence intervals for the scores and the posterior class probabilities. In addition, our methodology addresses properly cost sensitivity, since the rates of main interest (either TPR or TNR, which are the probabilities of an individual with label y= +1 and y=−1respectively, being classified in class +1 and −1, respectively) are explicitly controlled. As an example, and continuing with the credit scoring problem we consider the dataset german, available at the UCI Repository [Dheeru and Karra Taniskidou, 2017] and described in detail in Section 3.3. This dataset is slightly imbalanced (the class of defaulting customers represents the 30% of the total). The mean squared error (MSE) of the probability prediction for the defaulting class under the non cost-sensitive version of the novel method is equal to 0.51 (average value over a testing sample). If we use instead the cost-sensitive version, this error decreases down to 0.134. In the setting of churn prediction we obtain similar results. Again, the considered database churn is imbalanced, being the percentage of churners equal to 15.71% (see Section 3.3). From an initial mean squared error equal to 0.8the new model is able to decrease it down to 0.149. As it will be commented, such reductions may be at the expense of damaging the prediction of the posterior negative class probabilities, which are assumed to be less relevant. Another distinctive feature of our approach is that the SVM is embedded in an ensemble method which, as will be shown, means an improvement in performance. It is known that, in order to solve the SVM problem (SVM(C+, C−)), a tuning process concerning the regularization parameter Cin the grid Cneeds to be performed. Traditionally, all the information resulting from this tuning procedure is discarded and only Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 3.2. Cost-sensitive predictive probabilities for SVM 37 the best Cvalue is used to build the classifier. Instead, in this work, the final posterior class probability estimate is a weighted mean of different posterior probabilities, each one related to specific values of C. In addition, here we propose a novel methodology that does not make use of parametric models based on the score function f(x)obtained after tuning the SVM parameters. Instead, we consider a bootstrap framework (Efron and Tibshirani [1986]; Efron [2000]), which, to the best of our knowledge, has not been addressed before for this type of problems. The use of a bootstrap sampling allows us to obtain accurate values for the density of the score values, which translates into a better prediction of the posterior class probability P(y= +1 |x), and, on top of the point estimates, confidence intervals for the score values and estimated class probabilities for a given individual. This is another novelty of our approach with respect to off-the-shelf procedures in the literature. The chapter is structured as follows. First, in Section 3.2, our methodology is introduced. Section 3.2.1 describes how to integrate a bootstrap sampling into an SVM to enhance accuracy and to produce posterior class probabilities estimates as well as their corresponding confidence intervals of the score values. Section 3.2.2 explains two different ways to obtain cost-sensitive probabilistic predictions. In Section 3.3 some experimental results are presented. In particular, several well-referenced datasets from business, social sciences and other contexts are analyzed. Estimates of the posterior class probabilities under our methodology are compared to those obtained under benchmark approaches. Finally, the posterior probabilities of the classes of interest are controlled via the two different approaches described in Section 3.2.2. Conclusions can be found in Section 3.4. 3.2 Cost-sensitive predictive probabilities for SVM In this section we present our methodology to obtain point estimates for the posterior class probabilities as well as confidence intervals for them, using the SVM classifier. First, in Section 3.2.1 we explain how to integrate a bootstrap sampling into the SVM to produce posterior class probabilities estimates P(y= +1 |x). Second, in Section 3.2.2 we describe two different approaches that allow us to control the posterior probability estimates in case we have a binary classification problem with one of the classes of most interest. 3.2.1 SVM posterior class probabilities based on Bootstrap Assume that we want to solve SVM (SVM(C+, C−)) to classify the observations in a dataset, such as e.g. churn dataset (see Section 3.3.1 for details concerning the database). In order to estimate the classification error of the SVM classifier, it is standard to consider a k-fold cross-validation (CV), see Kohavi et al. [1995]. Figure 3.2 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 38 Chapter 3. Cost-sensitive class probability estimation in support vector machines (a) (b) (c) Figure 3.2: Histogram of scores for a single instance when a k-fold CV is used. Here, we set k= 20,100 and 500, obtaining as many score values as the value of k. shows the histogram (in absolute frequencies) of the score values under three different choices of k(k= 20,100,500) for a given individual (randomly chosen). It can be observed that as kincreases, the score values are less disperse, a consequence of the fact that the different samples share more elements, and thus they yield more similar scores. Our procedure to calculate P(y= +1 |x)for a given instance, as it will be explained later, will be based on considering the proportion of positive scores using different classifiers, taking advantage of the fact that different classifiers have to be build in order to measure the performance. However, in the k-fold CV situation, it might not be possible to obtain accurate posterior class probabilities P(y= +1 |x), especially when the observations of the two groups strongly overlap. What it is proposed in this paper is to replace the k-fold CV approach by a bootstrap sampling that allows us to avoid the degenerate behaviour observed in Figure 3.2. The results are those illustrated in Figure 3.3, where the analogous histograms to Figure 3.2 are shown, but where a bootstrap sampling with Breplications (B= 20,100,500) has been considered instead. The idea of using those values is just to illustrate the behavior of this method when increasing the sample size in contrast with the one shown in Figure 3.2. Finally, as already exposed, the estimates for the posterior class probabilities P(y= +1 |x)will be Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 3.2. Cost-sensitive predictive probabilities for SVM 39 (a) (b) (c) Figure 3.3: Histogram of scores for a single instance when the Bootstrap with Breplications is used. As in the k-fold CV, B= 20,100 and 500. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 40 Chapter 3. Cost-sensitive class probability estimation in support vector machines obtained as the relative frequency of the positive (negative in the case of P(y=−1|x)) score values. Now we explain how our procedure works. The pseudocode can be found as Algorithm 2 below, and a flowchart is given in Figure 3.4. The goal here will be to estimate, for a generic individual with predictor variables x, the probability P(y= +1 |x). For that, roughly speaking, we will make use of the bootstrap resampling, obtaining for each sample and each choice of the parameter Ca different classifier that will be used in order to obtain different scores for a given individual. The probability P(y= +1 |x)will be calculated as (a correction of) the proportion of positive scores obtained. The procedure is carried out as follows. First, to carry out our procedure of obtaining probabilities, consider a complete dataset Ω0 composed of minstances, nvariables, and 2 classes (+1 or −1). The dataset is divided in two samples: the training sample T(of sample size mtr) in which we have the class label information, in order to train and estimate the accuracy of the classifier (with the aim of obtaining the weights wjin (3.3) and therefore being able to calculate the probabilities as in (3.4)) and an outer sample V(of size m−mtr) which consist of the instances for which the probabilities P(y= +1 |x)have to be calculated, see Step 1 of Algorithm 2. As it is usual in the SVM implementation, a grid Cfor the regularization parameter needs to be set. Then, a matrix PX with as many rows as the number of instances in the outer sample (m−mtr) and as many columns as the number of values Cto be used is built. This matrix contains the proportions of negative scores and is generated through the algorithm as follows. Given a fixed value C∈ C, and Bbootstrap samples from the training sample T(that will be denoted as T∗ b, b = 1, . . . , B), SVM is run over each bootstrap sample and validated over the out of bag sample, i.e., the set of instances that are in Tbut not in the considered bootstrap sample (we will denote them as V∗ b, b = 1, . . . , B). In case we have class information in V, we can validate twice: the first time (over the validation in the bootstrap procedure V∗ b), to measure the performance led by the chosen value Cand then over a outer set V, to estimate the posterior negative class probabilities conditioned to C,P(yVi=−1|x, C), where Videnotes the i-th instance in V. In this way, we shall obtain Bscore values for each instance in V, which will allow us to calculate P(y= +1 |x)in a frequentist way. Such score values shall be recorded in a matrix with as many rows as number of instances in the validation sample (m−mtr) and Bcolumns, PredictionV (f(xi)∗ j). Finally, we propose to estimate its posterior negative class probability P(yVi=−1|x) as a weighted average (using the weights in (3.3) and calculated as in (3.4)) of the estimates for P(yVi=−1|x, C)when using different values of C, but taking only into account those values of Cthat lead to accuracies close to the best one, since we want to give more weight to those most promising values of C. Let accr,b denote the standard accuracy in V∗ b(fraction of instances in V∗ bcorrectly classified), given the SVM built Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 3.2. Cost-sensitive predictive probabilities for SVM 41 from using the r-th value of C, and the b-th bootstrap sample; let accrdenote the average value of the coefficients accr,b, namely accr=PB b=1 accr,b B. Only values yielding high estimates of accrare taken into consideration, the remaining ones being discarded. Those considered are stored in the set J, defined as J={j: accj≥maxlaccl−ε}, where ε > 0is a fixed parameter. Finally, if weights wj, j ∈J, are defined according to wj=acc2 j Pl∈Jacc2 l ,(3.3) then, the estimation P(yVi=−1|x)is: P(yVi=−1|x) = X j∈J wjP(yVi=−1|x, Cj).(3.4) As commented before, the bootstrap sample allows us to obtain point estimates for the posterior class probabilities P(y= +1 |x). From the classic confidence interval for a proportion, it is straightforward to construct a (1 −α)% confidence interval for ˆp=P(y= +1 |x)as  ˆp−z1−α/2s1/4 B,ˆp+z1−α/2s1/4 B ,(3.5) where z1−α/2denotes the 1−α/2-th percentile of a standard normal distribution. Note that (3.5) is not a bootstrap confidence interval per se but a confidence interval constructed from a bootstrap estimate ˆp. However, it is easy to obtain a bootstrap confidence interval for the score value [ f(xi)of a given individual i. Specifically, given a confidence level 1−α, the basic bootstrap (Wehrens et al. [2000]) procedure leads to 2[ f(xi)−f(xi)∗ (1−α/2),2[ f(xi)−f(xi)∗ (α/2),(3.6) where [ f(xi) = f(xi)∗=X j f(xi)∗ j B denotes a point estimate of the score value for individual iand f(xi)∗ (1−α/2) is the (1 −α/2)-th percentile of the bootstrapped coefficients f(xi)∗for the same individual. Note that from the confidence interval as in (3.6) it is straightforward to decide if there is evidence to reject the null hypothesis of a positive score (which would imply that the Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 48 Chapter 3. Cost-sensitive class probability estimation in support vector machines Dataset Bootstrap-based approach Sollich Platt Tao et al. (r= 0,√10,√20,√30) absenteeism 0.133 0.16 0.133 0.176, 0.176, 0.176, 0.176 adult 0.158 0.232 0.105 0.151, 0.146, 0.128, 0.13 australian 0.173 0.223 0.121 0.151, 0.149, 0.135, 0.133 banknote 0.011 0.008 0.09 0.008, 0.145, 0.221, 0.238 careval 0.052 0.074 0.04 0.047, 0.047, 0.043, 0.093 cervical-cancer-1 0.013 0.234 0.04 0.045, 0.045, 0.045, 0.045 cervical-cancer-2 0.075 0.199 0.08 0.103, 0.103, 0.103, 0.103 churn 0.108 0.227 0.093 0.104, 0.104, 0.101, 0.128 german 0.203 0.203 0.163 0.235, 0.224, 0.187, 0.182 heart 0.171 0.217 0.124 0.157, 0.119, 0.113, 0.168 housing 0.078 0.142 0.097 0.152, 0.118, 0.141, 0.163 leukemia 00.238 0.019 0.014, 0.014, 0.014, 0.014 productivity 0.212 0.238 0.190 0.242, 0.239, 0.262, 0.259 SRBCT 0.039 0.237 0.006 0,0,0,0 wisconsin 0.018 0.094 0.034 0.028, 0.019, 0.037, 0.055 Table 3.2: Mean squared errors (MSE) obtained when predicting the posterior class probabilities in a linear SVM. Dataset Best C Bootstrap-based approach absenteeism 0.176 0.133 australian 0.217 0.173 banknote 0.007 0.011 careval 0.055 0.052 cervical-cancer-1 0.012 0.013 cervical-cancer-2 0.105 0.075 churn 0.108 0.108 divorce 0.059 0.059 german 0.24 0.203 heart 0.194 0.171 housing 0.118 0.078 leukemia 0 0 productivity 0.286 0.212 SRBCT 0.125 0.039 wisconsin 0.035 0.018 Table 3.3: Mean squared errors (MSE) using only the best Cand under the bootstrapbased approach. As already mentioned, not only point estimates for the class probabilities can be calculated, but also confidence intervals for both the scores and the probabilities. In Figure 3.6 we depict the confidence intervals for the scores and the probabilities P(Y= −1|x)of 20 different instances in the validation sample, for german dataset. In Figure 3.6(a) we present 95% confidence interval for the scores according to (3.6). For those intervals that do not contain the score 0, we can guarantee (with a confidence of a 95%) that the instance belongs to the positive class if the interval is above 0or to the negative class, otherwise. Together with the intervals, we have represented with Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 3.3. Experimental results 49 −2 0 2 4 0 5 10 15 20 Instances Score values f(x) Confidence Interval for scores (german data) (a) 0.00 0.25 0.50 0.75 1.00 0 5 10 15 20 Instances P(y=−1|x) Confidence Interval for probabilities (german data) (b) Figure 3.6: Confidence intervals for the scores values (Top panel) and the probabilities P(y=−1|x)(Bottom panel), as well as actual values P(y=−1) (light colour) for some instances of german dataset. the clearer point the true class of the instance. Finally, Figure 3.6(b) represents the confidence intervals for the estimated probabilities P(y=−1|x), calculated from (3.5). Also, the true probabilities (known since we know the true classes) are represented using the clearer points. 3.3.3 Results when the posterior class probabilities are controlled In this section we apply the methodologies described in Section 3.2.2 in order to control P(y= +1 |x)or P(y=−1|x). In particular, Tables 3.4 and 3.6 are obtained under Ctrl1 and Tables 3.5 and 3.7 show the results when the method based on the CSVM (Ctrl2) is implemented. For all the tables, the class of interest to be controlled is assumed to be the positive one, that is, we aim to control the true positive rate (TPR). Tables 3.4 and 3.5 show the MSE when considering only the positive instances, while Tables 3.6 and 3.7 depict the MSE for the negative instances. The values on the Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 50 Chapter 3. Cost-sensitive class probability estimation in support vector machines “imposed TPR” depends on the original value obtained in the TPR when no control on the misclassification rates is imposed. Therefore, for values of “imposed TPR” lower than the one obtained, a “−” is placed instead of the resulting MSE. Also, depending on the obtained TPR, and in order to obtain more representation than a single value, a imposed TPR of 0.95 is imposed for some datasets. Finally, if the MSE was originally 0(TPR = 1), no TPR has been imposed, as occurs for banknote and leukemia. From Tables 3.4 and 3.5, we can see how as the threshold for obtaining a given proportion of the instances in the correct class is increased, the MSE becomes lower, as expected. In fact, there are some datasets (banknote,careval,heart,housing,SRBCT and wisconsin), for which the obtained MSEs are very close to 0, for both Tables 3.4 and 3.5. However, Tables 3.6 and 3.7 present different patterns. While Table 3.7 behaves as expected (as the MSEs for the sensitivity become smaller, the MSEs for the specificity become constant or higher), the specificity depicted by Table 3.6 remains almost unaltered or have even descending MSEs. Here again, some datasets result in almost null MSEs (cervical-cancer,divorce,leukemia,SRBCT and wisconsin). Dataset \TPR imposed 0 0.5 0.6 0.7 0.8 0.9 0.95 1 absentism 0.266 - - - 0.266 0.266 - 0.266 adult 0.476 - 0.476 0.476 0.476 0.476 - 0.476 australian 0.071 - - - - 0.071 - 0.070 banknote 0 - - - - - - - careval 0.044 - - - - - 0.040 0.038 cervical-cancer-1 1 1 1 1 1 1 - 1 cervical-cancer-2 1 0.964 0.963 0.963 0.963 0.963 - 0.963 churn 0.8 0.8 0.8 0.8 0.8 0.8 - 0.8 german 0.510 0.258 0.255 0.255 0.255 0.255 - 0.255 heart 0.141 - - - - - 0.071 0.071 housing 0.114 - - - - 0.057 - 0.057 leukemia 0 - - - - - - - productivity 0.354 - 0.352 0.180 0.180 0.180 - 0.180 SRBCT 0.063 - - - - 0.063 - 0.063 wisconsin 0.036 - - - - - 0.018 0.018 Table 3.4: MSE for the positive class probability predictions of each dataset. Ctrl1 An important remark to be made concerning the performance of Ctrl1 and Ctrl2 is as follows. The first one seems to be able to improve the sensitivity without damaging too much the specificity or even improving it at the same time, while the second method damages in a more significant way the specificity, but at the same time it leads to better sensitivity values. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 3.4. Chapter Summary 51 Dataset \TPR imposed 0 0.5 0.6 0.7 0.8 0.9 0.95 1 absenteeism 0.266 - - - 0.254 0.237 - 0.221 adult 0.476 - 0.112 0.003 0.000 0.000 - 0.219 australian 0.071 - - - - 0.056 - 0.091 banknote 0 - - - - - - - careval 0.044 - - - - - 0.019 0.014 cervical-cancer-1 1 1 1 1 1 0.999 - 0.999 cervical-cancer-2 1 0.765 0.598 0.539 0.486 0.494 - 0.493 churn 0.8 0.437 0.416 0.271 0.228 0.175 - 0.149 german 0.510 0.427 0.192 0.175 0.157 0.155 - 0.134 heart 0.141 - - - - - 0.023 0.028 housing 0.114 - - - - - 0.066 0.035 leukemia 0.000 - - - - - - - productivity 0.354 - 0.156 0.137 0.123 0.103 - 0.081 SRBCT 0.063 - - - - 0 - 0 wisconsin 0.036 - - - - - 0.014 0.003 Table 3.5: MSE for the positive class probability predictions of each dataset. Ctrl2 3.4 Chapter Summary In this chapter we have proposed a procedure to obtain probabilistic outputs for the Support Vector Machines, through both point estimates and confidence interval estimates. Contrary to existing proposals, we present a method that is distribution-free and cost-sensitive. Also, it makes use of not only a single classifier but a weighted average of them, obtaining more accurate results. The method turns out advantageous for operational business processes as credit scoring or churn prediction, where the class of interest may suffer from imbalancedness. Our proposal is compared to some benchmark methodologies. The results show that our approach is comparable or better than such approaches if the focus is on point estimates. Up to our knowledge, no prior work has undertaken posterior class probabilities estimation by confidence intervals. We have shown how the bootstrap approach naturally leads to confidence intervals for the scores values. Two cost-sensitive alternatives are proposed here. The first one is based on changing the way the probabilities are estimated and the second one proposes to modify the original classifier by a costsensitive version. Results for real datasets have been shown, proving the usefulness of the novel approach. For simplicity, the baseline SVM classifiers are taken with a linear kernel; more powerful classifiers will be obtained if nonlinear kernels (as RBF) are used, though at the expense of making the computational effort higher. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 52 Chapter 3. Cost-sensitive class probability estimation in support vector machines Dataset \TPR imposed 0 0.5 0.6 0.7 0.8 0.9 0.95 1 absentism 0.088 - - - 0.088 0.044 - 0.044 adult 0.044 - 0.022 0.022 0.022 0.022 - 0.022 australian 0.271 - - - - 0.135 - 0.135 banknote 0.019 - - - - - - - careval 0.061 - - - - - 0.030 0.030 cervical-cancer-1 0.001 0.001 0.001 0.001 0.001 0.001 - 0.001 cervical-cancer-2 0.008 0.008 0.008 0.008 0.008 0.008 - churn 0.008 0.008 0.004 0.004 0.004 0.004 - 0.004 german 0.051 0.051 0.051 0.051 0.051 0.051 - 0.051 heart 0.207 - - - - - 0.207 0.071 housing 0.046 - - - - - 0.046 0.046 leukemia 0 - - - - - - - productivity 0.119 - 0.136 0.140 0.140 0.140 - 0.140 SRBCT 0 - - - - - 0 0 wisconsin 0.006 - - - - - 0.006 0.006 Table 3.6: MSE for the negative class probability predictions of each dataset. Ctrl1 Dataset \TPR imposed 0 0.5 0.6 0.7 0.8 0.9 0.95 1 absenteeism 0.088 - - - 0.043 0.045 - 0.051 adult 0.044 - 0.202 0.825 0.969 0.976 - 0.095 australian 0.271 - - - - 0.304 - 0.171 banknote 0.019 - - - - - - - careval 0.061 - - - - - 0.066 0.119 cervical-cancer-1 0.001 0.024 0.024 0.074 0.074 0.113 - 0.113 cervical-cancer-2 0.008 0.065 0.044 0.073 0.107 0.126 - 0.171 churn 0.008 0.049 0.060 0.076 0.044 0.065 - 0.097 german 0.051 0.093 0.125 0.145 0.207 0.252 - 0.421 heart 0.207 - - - - - 0.244 0.44 housing 0.046 - - - - - 0.236 0.296 leukemia 0 - - - - - - - productivity 0.119 - 0.142 0.159 0.201 0.234 - 0.294 SRBCT 0 - - - - 0.137 - 0.090 wisconsin 0.006 - - - - - 0.007 0.017 Table 3.7: MSE for the negative class probability predictions of each dataset. Ctrl2 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Chapter 4 Cost-sensitive feature selection in support vector machines 53 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 4.1. Introduction 55 The relevance of features in a classification procedure is linked to the fact that misclassifications costs are frequently asymmetric, since false positive and false negative cases may have very different consequences. However, off-the-shelf Feature Selection procedures seldom take into account such cost-sensitivity of errors. In this chapter we propose a mathematical-optimization-based Feature Selection procedure embedded in one of the most popular classification procedures, namely, Support Vector Machines, accommodating asymmetric misclassification costs. The key idea is to replace the traditional margin maximization by minimizing the number of features selected, but imposing upper bounds on the false positive and negative rates. The problem is written as an integer linear problem plus a quadratic convex problem for Support Vector Machines with both linear and radial kernels. The reported numerical experience demonstrates the usefulness of the proposed Feature Selection procedure. Indeed, our results on benchmark data sets show that a substantial decrease of the number of features is obtained, whilst the desired trade-off between false positive and false negative rates is achieved. 4.1 Introduction An amount of different FS procedures are found in the literature, some independent of the classification procedure and others embedded in the classification procedure, like the Holdout SVM (HOSVM), Maldonado and Weber [2009], Kernel-Penalized SVM (KP-SVM), Maldonado et al. [2011], or the methods presented in Chan et al. [2007] or Ghaddar and Naoum-Sawaya [2018]. Also, one can minimize the number of relevant features or even their cost, as in Maldonado et al. [2017]. The embedded method together with whichever of the previous optimization schemes is the approach considered in this chapter, since we aim to obtain a SVM-based classifier, and, at the same time, perform the selection of the features. The core idea is the optimization problem to be solved: instead of maximizing the margin, as in the traditional SVM, we seek the classifier with lowest number of features (or cost of the features), but without damaging too much the original performance. In order to be able to control the classifier’s performance, we will make use of the model presented in Chapter 2, but choosing the anchor sample Jto be the same as the training sample I. Specifically, the formulation results minω,β,ξ,z ω>ω+CPi∈Iξi s.t. yi(ω>xi+β)≥1−ξi, i ∈I 0≤ξi≤M1(1 −zi)i∈I ˆp`≥ˆp∗ 0``∈L zi∈ {0,1}i∈I, (4.1) where M1is a large number. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 56 Chapter 4. Cost-sensitive feature selection in support vector machines In essence, this is simply the formulation for the SVM with linear kernel, to which performance constraints have been added: ˆp`≥ˆp∗ 0`, where ˆp`are different performance measures, forced to take values above thresholds ˆp∗ 0`, and ziare new binary variables that check whether sample iis counted as correctly classified. Its (partial) dual formulation is minλ,β,ξ,z P i,j∈I λiyiλjyjK(xi, xj) + CPi∈Iξi s.t. yi(P j∈I λjyjK(xj, xi) + β)≥1−ξi, i ∈I P i∈I λiyi= 0 0≤λi≤C/2i∈I 0≤ξi≤M1(1 −zi)i∈I ˆp`≥ˆp∗ 0``∈L zi∈ {0,1}i∈I. (4.2) As before, this is similar to the standard partial dual formulation of the SVM with general kernel and constraints in the performance measures, as in (4.1). For more information about how formulation (4.2) is obtained, the reader is referred to Chapter 2 and the Appendix. Note that, while mathematical optimization problems addressed in the statistical literature are, traditionally, as (SVM(C+, C−)) or (GSVM(C+, C−)), nonlinear programs in continuous variables, our approach involves integer variables, which define harder optimization problems. However, Integer Programming has shown to be rather competitive thanks to the impressive advances in (nonlinear) integer programming solvers, as demonstrated in recent papers addressing different topics in data analysis, Bertsimas et al. [2016, 2014]; Carrizosa et al. [2011, 2016, 2017a,b]. The remainder of the chapter is structured as follows. In Section 4.2 we present the new FS methodology for SVM. For either linear or nonlinear kernels, we reduce the optimization problem to solving a standard linear integer program plus, eventually, a quadratic convex problem. The performance of our FS approach is empirically tested under different experiments described in Section 4.3. The results of those experiments are shown in Section 4.4. Comparisons between the use of linear and radial kernels, and between the standard linear SVM with and without embedded FS are also provided. The chapter ends with conclusions in Section 4.5. 4.2 Cost-sensitive Feature Selection In this section we present a novel linear formulation for SVM where classification costs are modeled via certain constraints, and where, in addition, a FS approach is embedded in such a way that only the relevant features are considered. In order to cope with classification costs, first we recall some performance measures, namely, TPR, TNR and ACC as in (2.1). Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 4.2. Cost-sensitive Feature Selection 57 The objective is to perform classification using a reduced set of features, in such a way that certain constraints over the performance, such as TPR ≥p0(+1) or TNR ≥p0(−1) (for threshold values p0(+1),p0(−1) ∈[0,1]), are fulfilled. Note that the pair (X, Y )is a random vector with unknown distribution from which a sample {(xi, yi)}i∈Iis generated. This implies that TPR and TNR should be estimated from sample data. This leads to the empirical constraints [ TPR ≥p∗ 0(+1) and [ TNR ≥p∗ 0(−1), for p∗ 0(+1) ≥p0(+1) and p∗ 0(−1) ≥p0(−1), where the performance measures are replaced by their sample estimates. Two possible choices, which shall be explored in this work, are p∗ 0(+1) =p0(+1) and p∗ 0(−1) =p0(−1), (4.3) or the more conservative approach based on Hoeffding inequality, p∗ 0(+1) =p0(+1) +s−log α 2|I+| and p∗ 0(−1) =p0(−1) +s−log α 2|I−|, (4.4) where αis the significance level for the hypothesis test whose null hypothesis is either TPR ≤p0(+1) or TNR ≤p0(−1). See Chapter 2 for more details. Note that it is straightforward to extend our results to the case in which measurement costs are associated with the features, as in e.g. Carrizosa et al. [2008], and then the minimum-cost feature set is sought instead. 4.2.1 The cost-sensitive FS procedure Assume that we have a linear kernel, i.e., the kernel Kin (GSVM(C+, C−)) is given by K(x, x0) = x>x0,and thus the SVM with all features is obtained by solving (SVM(C+, C−)). We state the feature selection problem as a Mixed Integer Linear Program. Consider an auxiliary variable zithat in case of being equal to 1, the instance iis counted as correctly classified. Hence, estimates of TPR and TNR from sample Ihave lower bounds [ TPR≥Pi∈Izi(1 + yi)/Pi∈I(1 + yi)and [ TNR≥Pi∈Izi(1 −yi)/Pi∈I(1 −yi), respectively. Associated with each feature k,1≤k≤N, we define the variable δk taking the value 1 if feature kis selected for classifying, and 0 otherwise. Hence, the optimization problem that defines a linear classifier (hyperplane) taking into account the classification rates and in which a cost-based FS procedure is integrated is given by Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 64 Chapter 4. Cost-sensitive feature selection in support vector machines Name SVM FS Feature reduction Mean Std Mean Std wisconsin Acc 0.975 0.021 0.947 0.025 30 →2 (0 Std) TPR 0.992 0.013 0.973 0.031 TNR 0.943 0.051 0.905 0.063 votes Acc 0.954 0.033 0.949 0.036 32 →2 (0 Std) TPR 0.955 0.038 0.928 0.059 TNR 0.947 0.059 0.979 0.036 nursery Acc 1 0 1 0 19 →1 (0 Std) TPR 1 0 1 0 TNR 1 0 1 0 Australian Acc 0.848 0.051 0.855 0.057 34 →1 (0 Std) TPR 0.798 0.083 0.801 0.087 TNR 0.912 0.05 0.926 0.041 careval Acc 0.956 0.017 0.946 0.019 15 →9 (0 Std) TPR 0.96 0.022 0.963 0.017 TNR 0.948 0.024 0.907 0.04 leukemia Acc 0.972 0.164 0.875 0.331 7128 →3.139 (1.205 Std) TPR 0.979 0.196 0.896 0.305 TNR 0.96 0.144 0.833 0.373 gastrointestinal Acc 0.895 0.307 0.829 0.379 698 →1 (0 Std) TPR 0.929 0.258 0.839 0.367 TNR 0.8 0.4 0.8 0.4 Table 4.2: Performance measures under the cost-sensitive sparse SVM with linear kernel and p∗ 0(+1) =p0(+1),p∗ 0(−1) =p0(−1). Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 4.4. Numerical Results 65 Name SVM FS Feature reduction Mean Std Mean Std wisconsin Acc 0.975 0.021 0.965 0.023 30 →6.2 (0.919 Std) TPR 0.992 0.013 0.975 0.023 TNR 0.943 0.051 0.947 0.048 votes Acc 0.954 0.033 0.954 0.033 32 →9.3 (1.16 Std) TPR 0.955 0.038 0.96 0.034 TNR 0.947 0.059 0.945 0.052 nursery Acc 1 0 1 0 19 →1 (0 Std) TPR 1 0 1 0 TNR 1 0 1 0 Australian Acc 0.848 0.051 0.837 0.057 34 →5.5 (1.78 Std) TPR 0.769 0.083 0.772 0.074 TNR 0.912 0.05 0.924 0.053 careval Acc 0.956 0.017 0.954 0.018 15 →11 (0 Std) TPR 0.96 0.022 0.962 0.018 TNR 0.948 0.024 0.935 0.039 leukemia Acc 0.972 0.164 0.944 0.229 7128 →2 (0 Std) TPR 0.979 0.196 0.957 0.202 TNR 0.96 0.144 0.92 0.272 gastrointestinal Acc 0.895 0.307 0.842 0.365 698 →3.105 (0.552 Std) TPR 0.929 0.258 0.927 0.26 TNR 0.8 0.4 0.619 0.486 Table 4.3: Performance measures under the cost-sensitive sparse SVM with linear kernel and p∗ 0(+1) =p0(+1) +p−log α/(2|I1|),p∗ 0(−1) =p0(−1) +p−log α/(2|I−1|). Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 66 Chapter 4. Cost-sensitive feature selection in support vector machines accuracy smaller. However, the value on the TNR is increased. As happened with wisconsin, the loss is due mainly to the two facts previously mentioned. For nursery, an amazing reduction to only one feature is achieved, in addition getting a perfect classification. This is explained as follows. As commented in Section 4.4.1, multiclass datasets are transformed into 2-class ones, and this is the case, obtaining the classes “not_recom” and “others”, which are the positive and negative classes, respectively. In addition, one of the (categorical) features in the data (which is the one selected by our procedure) completely determines the class. In Australian, the total number of variables is also reduced to only one, having similar performance measures values as in the standard SVM. In fact, we obtain here even better results than under the original linear SVM. If the variable selected with the algorithm is studied, one can observe that it is a binary variable X, where the contingency table together with the class variable is given in Table 4.4. Hence this variable is by itself a good predictor, as the FS procedure pointed out. In the case of careval, we got the smallest reduction in the number of variables selected, maintaining the performance measures values above the imposed thresholds. On the other hand, in the case of leukemia, the number of variables is significantly reduced. However, since the number of instances is small, the performance measurements are affected by this reduction of features. Also, for gastrointestinal, the results are similar to what happened for leukemia, but the TNR has not been affected at all. X = 0 X = 1 Class +306 77 Class −23 284 Table 4.4: Contingency table of the feature selected in Australian. Consider next the results shown by Table 4.3, for the case where we are restrictive regarding the performance values, that is, when p∗ 0(+1) =p0(+1) +p−log α/(2|I1|) and p∗ 0(−1) =p0(−1) +p−log α/(2|I−1|). From the table, it can be seen how this approach tends to work better concerning the performance measures, but achieves less sparse solutions. For example, if we focus on wisconsin, the TNR, the TPR and the accuracy as well, obtain the desired performance requirements. However, only a reduction of variables of one fifth is obtained. In the case of votes, an analogous result is obtained for the performance measures and only a reduction in one third of the variables is achieved. The same pattern as before is observed for nursery. For Australian, we obtain even an improvement in all the three performance measures considered, reducing the number of features to one fifth. In addition, we get again in careval the smallest reduction in the number of variables selected, maintaining the performance measures values above the thresholds imposed as before, but using a larger number of features. On the contrary, and surprisingly, we have obtained for leukemia Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 4.4. Numerical Results 67 even a bigger reduction in the number of features and better results using Hoeffding inequality. However, gastrointestinal dataset goes with the flow and the number of features is increased when using the mentioned inequality. Nevertheless, the TPR has not been affected now whereas the TNR has significantly decreased. 4.4.3 Results under the cost-sensitive sparse SVM with radial kernel The analogous results to those in Section 4.4.2 are presented here, for the case of the radial kernel. However, only wisconsin,votes and Australian datasets are used here. As shown by Tables 4.5 and 4.6 and similarly as occurred in Section 4.4.2, the use of the threshold values obtained by the Hoeffding inequality (as in (4.4)) tends to yield a lower level of sparsity, but also, a higher predictive power in general (particularly, when achieving the desired bounds). Concerning the performance measures, it can be deduced from Tables 4.5 and 4.6 that this approach works well in general, especially when using Hoeffding. Finally, it should be noted how the reduction in the number of features is quite notable for some datasets, as before. Name SVM FS Feature reduction Mean Std Mean Std wisconsin Acc 0.975 0.021 0.956 0.012 30 →2 (0 Std) TPR 0.992 0.013 0.988 0.016 TNR 0.943 0.051 0.893 0.051 votes Acc 0.954 0.033 0.947 0.034 32 →2 (0 Std) TPR 0.955 0.038 0.928 0.059 TNR 0.947 0.059 0.974 0.036 nursery Acc 1 0 1 0 19 →1 (0 Std) TPR 1 0 1 0 TNR 1 0 1 0 Table 4.5: Performance measures under the cost-sensitive sparse SVM with radial kernel and p∗ 0(+1) =p0(+1),p∗ 0(−1) =p0(−1). Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 68 Chapter 4. Cost-sensitive feature selection in support vector machines Name SVM FS Feature reduction Mean Std Mean Std wisconsin Acc 0.975 0.021 0.947 0.03 30 →6.2 (0.919 Std) TPR 0.992 0.013 0.967 0.039 TNR 0.943 0.051 0.907 0.02 votes Acc 0.954 0.033 0.949 0.03 32 →9.3 (1.16 Std) TPR 0.955 0.038 0.959 0.034 TNR 0.947 0.059 0.939 0.043 nursery Acc 1 0 1 0 19 →1 (0 Std) TPR 1 0 1 0 TNR 1 0 1 0 Table 4.6: Performance measures under the cost-sensitive sparse SVM with radial kernel and p∗ 0(+1) =p0(+1) +p−log α/(2|I1|),p∗ 0(−1) =p0(−1) +p−log α/(2|I−1|). 4.4.4 Comparison with other methodologies The cost-sensitive FS procedure presented here can be compared in a certain way with some other benchmark methodologies. However, the authors are not aware of FS methods for SVM controlling, as we do, TPR or TNR. Among the different FS techniques that can be applied to SVM we can find, for example, the following ones: Filter methods (they are based on measures like Pearson’s Correlation, Linear Discriminant Analysis or Chi-Square), Wrapper methods (Forward Selection, Backward Elimination, Recursive Feature elimination, . . . ) and Embedded methods (such as the presented in the Introduction Section). In order to make a comparison with another state-of-the-art method, we have selected the method in Chan et al. [2007],Ghaddar and Naoum-Sawaya [2018]. The results can be seen in Tables 4.7 and 4.8. In Table 4.7 we can see the results for the standard SVM, the results of our FS approach when p∗ 0(+1) =p0(+1) and p∗ 0(−1) =p0(−1), and the results of the state-of-the-art method when the maximum number of features selected is the same as the obtained for our methodology. In Table 4.8, the results for the standard SVM are reported together with the results of our FS approach when p∗ 0(+1) =p0(+1) +p−log α/(2|I1|)and p∗ 0(−1) =p0(−1) +p−log α/(2|I−1|), as well as the results of the state-of-the-art method when the maximum number of features selected is the same as the obtained with our methodology. We can observe that, except for gastrointestinal dataset (when using Hoeffding inequality), where we obtain better results than the comparative, similar results are Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 4.4. Numerical Results 69 Name SVM FS Compar. Mean Std Mean Std Mean Std wisconsin Acc 0.975 0.021 0.947 0.025 0.954 0.021 TPR 0.992 0.013 0.973 0.031 0.977 0.025 TNR 0.943 0.051 0.905 0.063 0.911 0.056 votes Acc 0.954 0.033 0.949 0.036 0.956 0.026 TPR 0.955 0.038 0.928 0.059 0.949 0.039 TNR 0.947 0.059 0.979 0.036 0.969 0.034 nursery Acc 1 0 1 0 1 0 TPR 1 0 1 0 1 0 TNR 1 0 1 0 1 0 Australian Acc 0.848 0.051 0.855 0.057 0.855 0.054 TPR 0.798 0.083 0.801 0.087 0.801 0.082 TNR 0.912 0.05 0.926 0.041 0.925 0.039 careval Acc 0.956 0.017 0.946 0.019 0.949 0.016 TPR 0.96 0.022 0.963 0.017 0.967 0.012 TNR 0.948 0.024 0.907 0.04 0.91 0.043 leukemia Acc 0.972 0.164 0.875 0.331 0.653 0.471 TPR 0.979 0.196 0.896 0.305 0.66 0.474 TNR 0.96 0.144 0.833 0.373 0.68 0.466 gastrointestinal Acc 0.895 0.307 0.829 0.379 0.857 0.35 TPR 0.929 0.258 0.839 0.367 0.9 0.3 TNR 0.8 0.4 0.8 0.4 0.75 0.433 Table 4.7: Performance measures under the cost-sensitive sparse SVM with linear kernel and p∗ 0(+1) =p0(+1),p∗ 0(−1) =p0(−1) and comparative with the method in Chan et al. [2007],Ghaddar and Naoum-Sawaya [2018]. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 70 Chapter 4. Cost-sensitive feature selection in support vector machines Name SVM FS Compar. Mean Std Mean Std Mean Std wisconsin Acc 0.975 0.021 0.965 0.023 0.967 0.018 TPR 0.992 0.013 0.975 0.023 0.989 0.017 TNR 0.943 0.051 0.947 0.048 0.926 0.033 votes Acc 0.954 0.033 0.954 0.033 0.954 0.033 TPR 0.955 0.038 0.96 0.034 0.948 0.036 TNR 0.947 0.059 0.945 0.052 0.961 0.035 nursery Acc 1 0 1 0 1 0 TPR 1 0 1 0 1 0 TNR 1 0 1 0 1 0 Australian Acc 0.848 0.051 0.837 0.057 0.851 0.053 TPR 0.798 0.083 0.772 0.074 0.798 0.081 TNR 0.912 0.05 0.924 0.053 0.919 0.046 careval Acc 0.956 0.017 0.954 0.018 0.954 0.017 TPR 0.96 0.022 0.962 0.018 0.97 0.016 TNR 0.948 0.024 0.935 0.039 0.917 0.027 leukemia Acc 0.972 0.164 0.944 0.229 0.932 0.252 TPR 0.979 0.196 0.957 0.202 0.938 0.242 TNR 0.96 0.144 0.92 0.272 0.917 0.276 gastrointestinal Acc 0.895 0.307 0.842 0.365 0.714 0.452 TPR 0.929 0.258 0.927 0.26 0.75 0.433 TNR 0.8 0.4 0.619 0.486 0.625 0.484 Table 4.8: Performance measures under the cost-sensitive sparse SVM with linear kernel and p∗ 0(+1) =p0(+1) +p−log α/(2|I1|),p∗ 0(−1) =p0(−1) +p−log α/(2|I−1|)and comparative with the method in Chan et al. [2007],Ghaddar and Naoum-Sawaya [2018]. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 4.4. Numerical Results 71 obtained for our method and the method in Chan et al. [2007],Ghaddar and Naoum- Sawaya [2018] in terms of accuracy, while our methodology is cost-sensitive and we can control the performance measurements. As an illustration, in Table 4.9 we have collected all the results for dataset australian when applying the method in Chan et al. [2007], Ghaddar and Naoum-Sawaya [2018] and varying the number of features from 1(minimum) to 34 (maximum). There, we can see how the maximum TPR obtained is 0.8007, so with our methodology, and maybe at the expense of increasing misclassification rates in the another class, we can improve the accuracy rates in the target class. The results obtained when either TPR or TNR are varied are summarized in Table 4.10. Australian # Feat. Acc TPR TNR # Feat. Acc TPR TNR 1 0.8551 0.8007 0.9248 18 0.8464 0.7954 0.9121 2 0.8551 0.8007 0.9248 19 0.8464 0.7954 0.9121 3 0.8551 0.8007 0.9248 20 0.8464 0.7954 0.9121 4 0.8551 0.8007 0.9248 21 0.8464 0.7954 0.9121 5 0.8507 0.798 0.9186 22 0.8578 0.7953 0.9154 6 0.8507 0.798 0.9186 23 0.8464 0.7954 0.9121 7 0.8507 0.798 0.9186 24 0.8464 0.7954 0.9121 8 0.8507 0.798 0.9186 25 0.8464 0.7954 0.9121 9 0.8507 0.798 0.9186 26 0.8449 0.7929 0.9121 10 0.8507 0.798 0.9186 27 0.8478 0.7981 0.9121 11 0.8507 0.798 0.9186 28 0.8478 0.7954 0.9153 12 0.8478 0.798 0.9121 29 0.8464 0.7927 0.9153 13 0.8478 0.798 0.9121 30 0.8493 0.798 0.9153 14 0.8478 0.798 0.9121 31 0.8478 0.7954 0.9153 15 0.8478 0.798 0.9121 32 0.8478 0.7981 0.9121 16 0.8464 0.7954 0.9121 33 0.8478 0.7981 0.9121 17 0.8478 0.798 0.9121 34 0.8478 0.7981 0.9121 Table 4.9: Performance measures using the method in Chan et al. [2007],Ghaddar and Naoum-Sawaya [2018], varying the maximum number of features from 1 (minimum) to 34 (maximum) in Australian dataset. From these experimental results we can conclude that, indeed, our method is able not only to reduce the number of features but it also controls the performance measures. If we observe the cases where (p∗ 0(+1),p∗ 0(−1)) is (0.85,0.5) or (0.85,0.55), we see how we have strongly increased the value in the TPR, although the TNR has decreased a lot. A similar behavior is observed for the pair (0.9,0.5). However, when using (0.85,0.575) Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 72 Chapter 4. Cost-sensitive feature selection in support vector machines Australian p∗ 0(+1) p∗ 0(−1) Acc TPR TNR Aver. # Feat. Selected 0.85 0.5 0.738 0.94 0.484 1 0.85 0.55 0.738 0.94 0.484 1 0.85 0.575 0.812 0.854 0.754 1.7 0.85 0.6 0.855 0.801 0.92 2 0.9 0.5 0.757 0.896 0.582 1.333 Table 4.10: Performance measures using the method in Chan et al. [2007],Ghaddar and Naoum-Sawaya [2018], varying the maximum number of features from 1 (minimum) to 34 (maximum) in Australian dataset. a different trade-off is found, whereas for (0.85,0.6) we recover the original results. 4.5 Chapter Summary In this chapter we have proposed a Feature Selection procedure for Support Vector Machines that yields a novel, sparse, SVM. Contrary to existing Feature Selection approaches, we take explicitly into account that misclassification costs may be rather different in the two groups, and thus, instead of seeking the classifier maximizing the margin, we seek the most sparse classifier that attains certain true positive and true negative rates on the dataset. For both SVM with linear and radial kernel, the problem is written in a straightforward manner, solving first a mixed integer linear problem and then their standard SVM formulations, considering only the features obtained in the first problem as well as the performance constraints. The reported numerical results show that the novel approaches lead to comparable or better performance rates, in addition to an important reduction in the number of variables. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Chapter 5 Feature selection for benchmarking via DEA formulation 73 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 80 Chapter 5. Feature selection for benchmarking via DEA formulation s.t. (FSDEA(k)(p)) (1.2) −(1.5),(5.2) −(5.4) α(k) i≤˜ M1˜z(k) i∀i= 1, . . . , N (5.6) N X i=1 ˜z(k) i= ˜p(5.7) ˜z(k) i∈ {0,1} ∀i= 1, . . . , N, (5.8) where ˜ M1is another big constant. Constraints (5.6)–(5.8) are the counterparts of (5.2)–(5.4) but modelling the selection of inputs instead of outputs. (FSDEA(k)(p)) has K+M+N+ 3 linear constraints and 2N+ 2 Mvariables, where half of them are continuous and the other half binary. Although running times are not an issue for this model, one can lower them even further by finding tighter values of M1and ˜ M1. As above, this can be done using bounds on the inputs and the outputs. Modeling constraints on weights Our (OSDEA(k)(p)) improves the discriminatory power of the DEA model by focusing on a few outputs, and eliminating the rest from the calculation of the efficiency of DMU k. There is a strand of literature that, using also as a basis the discriminatory power, argue the necessity of controlling the values of the weights [Allen et al., 1997; Green et al., 1996; Joro and Korhonen, 2015; Podinovski, 2016; Ramón et al., 2010; Sexton et al., 1986]. In these works, it is assumed that we have upper and lower bounds on the weight β(k) o, say, L(k) oand U(k) o, for o= 1, . . . , M, i.e., L(k) o≤β(k) o≤U(k) o∀o= 1, . . . , M. (5.9) Gathering non trivial values for these bounds is not a straightforward task for the user in the presence of many outputs, as in dataset on benchmarking of electricity DSOs in our numerical section. In any case, we can enrich our (OSDEA(k)(p)), to not only control whether an output can be used, but also the range of values for the corresponding weight. These bounds can be incorporated in constraints (5.2) in (OSDEA(k)(p)) yielding L(k) oz(k) o≤β(k) o≤U(k) oz(k) o∀o= 1, . . . , M. (5.70) There are a few observations to be made. First, the knowledge of upper bounds on the weights naturally tightens the value of M1. Second, if there are meaningful lower bounds on the weights, i.e., if L(k) o>0, then z(k) omust be equal to 1. Third, these positive lower bounds make the selection problem (OSDEA(k)(p)) infeasible for small Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 5.2. The individual selection model 81 values of p. Indeed, this is the case when there are more than poutputs with a positive lower bound. Modeling attributes of the outputs Outputs may have attributes attached to them, which may affect the selection. We will model two of those. First, we will consider that outputs are different in nature and therefore we will attach a different cost to them. Let codenote the cost associated with output yo, o = 1, . . . , M, which can measure the collection and the verification of this output in a repeated setting. To select poutputs so that their total cost does not exceed a given amount C, we need to add to (OSDEA(k)(p)) the following constraint M X o=1 coz(k) o≤C. (5.10) Second, we can consider the outputs being partitioned into Sclusters, with outputs within a cluster being similar in terms of what they measure. In the context of benchmarking electricity Distribution System Operators (network companies), clusters may related to the many different measurements of connections, transformers, lines, cables, etc. Let H={H1, . . . , HS}denote the partitioning of the outputs, namely H`∩Hs=∅ and ∪S `=1H`={1, . . . , M}. Given the similarity of outputs within a cluster, we will impose that at most (respectively, at least) p(max) `(respectively, p(min) `) outputs can be selected from H`. In order to do so, we need to add to (OSDEA(k)(p)) the following constraint X o∈H` z(k) o≤p(max) `∀`= 1, . . . , S. (5.11) X o∈H` z(k) o≥p(min) `∀`= 1, . . . , S. (5.12) Finally, we have correlation ρoo0between outputs oand o0as another attribute. If two outputs are highly correlated, we may be interested in using only one of them, since the information they provide is almost the same and can derive in the problem of multicollinearity Bertsimas and King [2016]. Hence, we want to impose that if ρoo0is greater than a preselected threshold, then outputs oand o0cannot be chosen simultaneously. We can model this by first defining a 0–1 matrix R, in which Roo0= 0 if ρoo0is lower than the threshold, and 1otherwise. Then, we have simply to add to (OSDEA(k)(p)) the constraints z(k) o+z(k) o0≤2−Roo0,∀o<o0.(5.13) Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 82 Chapter 5. Feature selection for benchmarking via DEA formulation The choice of the threshold have to be done with care, since some works like Nunamaker [1985] suggest that the addition of a highly correlated variable may increase the efficiency. Throughout this section, we have made the selection of outputs individually for DMU kwith the goal to maximize the efficiency of DMU k. Therefore, for two different DMUs, kand k0, the selected outputs, z(k)(p)and z(k0)(p), may differ. In model specification one is interested in finding the most discriminatory features in order to build a valid model for all DMUs. With this in mind, we propose in the next section a mathematical optimization model that selects the outputs jointly for all DMUs, ensuring they will be the same ones for all DMUs. 5.3 The joint selection model In this section, we address the problem in which the selected outputs have to be the same for all DMUs. First, this joint selection is made maximizing the average efficiency of all DMUs, yielding an MILP formulation. The model can be enriched as in previous section with input selection decision variables, as well as constraints modeling desirable properties about the selected features. Second, we propose alternatives to the maximization of the average efficiency when making the joint selection of outputs, such as the maximization of the weighted average efficiency, the minimum efficiency, or a percentile of the efficiencies. The joint selection model can again be formulated as an MILP problem. We also consider the minimization of the square of the Euclidean distance from each DMU efficiency to the ideal value of 1, where the joint selection model can be rewritten as a Mixed Integer Quadratic Programming problem. 5.3.1 The selection model for all DMUs To obtain all efficiencies E(k)simultaneously, one can solve the following single-objective Linear Programming formulation 1 K K X k=1 E(k)=maximize(α,β) 1 K K X k=1 M X o=1 β(k) oy(k) o(5.14) Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 5.3. The joint selection model 83 s.t. M X o=1 β(k) oy(j) o− N X i=1 α(k) ix(j) i≤0∀j= 1, . . . , K;∀k= 1, . . . , K (5.15) N X i=1 α(k) ix(k) i= 1 ∀k= 1, . . . , K (5.16) α∈RN·K +(5.17) β∈RM·K +.(5.18) It is easy to see that this problem decomposes by DMU, and that each of the subproblems are equivalent to (DEA(k)), which optimal solution value is E(k). We continue with the model in which poutputs are to be selected from the M available ones, the same ones for all DMUs. The goal in this section is to maximize the average efficiency across all DMUs. Let zobe equal to 1 if output ocan be used in the calculation of the efficiencies, and 0 otherwise. The decision variables β(k) oand α(k) i are defined as above. The Output Selection for DEA problem, (OSDEA(p)), where p outputs must be selected such that the average efficiency across all DMUs is maximized, can be written as the following MILP: v(p) := maximize(α,β,z) 1 K K X k=1 M X o=1 β(k) oy(k) o(5.19) s.t. (OSDEA(p)) (5.15) −(5.18) β(k) o≤M1zo∀o= 1, . . . , M;∀k= 1, . . . , K (5.20) M X o=1 zo=p(5.21) zo∈ {0,1} ∀o= 1, . . . , M, (5.22) where M1is a big constant. Constraints (5.15)-(5.18) are necessary to find the weights of the inputs and the outputs that the efficiency for each DMU. Constraints (5.20) make sure that the selection variables zoare well defined with respect to β(k) o. Constraint (5.21) models the number of features to be selected. Finally, constraints (5.22) relate to the range of decision variables zo. (OSDEA(p)) has K(K+M+1)+1 linear constraints and K(M+N) + Mvariables, where K(M+N)are continuous and Mare binary ones. We have multiplied the size of the problem by K, except for the number of binary variables, which are still one per output. Our numerical experiments show that this problem can still be solved efficiently. Moreover, and as in previous section, the computational burden of the problem depends on the value M1and we can tighten it Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 84 Chapter 5. Feature selection for benchmarking via DEA formulation using similar bounds. As before, we might extend the model as in Section 5.2.2, with input selection decision variables, as well as constraints to model desirable properties of the outputs. Let z(p)denote the optimal selection variables to (OSDEA(p)), i.e., the poutputs that yield the maximum average efficiency. Thus, the optimal solution value to (OSDEA(p)), denoted above by v(p), is equal to 1 KPK k=1 E(k)(z(p)). In general, we have that E(k)(z(p)) ≤E(k)(z(k)(p)), since z(k)(p)is the best strategy for DMU k. As in previous section, the maximum average efficiency v(p)is non decreasing in p, i.e., the more outputs we select the better the average efficiency can be. In the limit case, we have that v(M) = 1 KPK k=1 E(k). The number of selected outputs pis a parameter of our model. The user should make the choice of pafter inspecting the curve v(p). As before, a plausible strategy to choose the value of pis to look at the marginal contribution of an additional feature, i.e., v(p+ 1) −v(p), and stop when this is below a threshold. The question is whether this marginal contribution is nonincreasing, i.e., v(p+ 2) −v(p+ 1) ≤v(p+ 1) −v(p), for all p= 1, . . . , M −2. Below, we show a toy example where this inequality is not satisfied, and thus v(p)is not a concave function of p. In the numerical section, devoted to the benchmarking of electricity DSOs, the function v(·)that we obtain empirically is concave, and thus, not convex. Counterexample 1. Consider 5DMUs, each one described by a single input and four different outputs, as can be seen in Table 1. When performing the feature selection procedure, the results that we obtain are the following. In the case of selecting just one output, say p= 1, the procedure chooses “Output 1” and the obtained efficiencies are then just the same as the values of “Output 1" for each DMU. Hence, the average efficiency is 0.8. When two outputs are selected, the procedure chooses “Output 1” and “Output 2”. These outputs make the average efficiency to be 0.867. Furthermore, if three outputs are selected, the procedure chooses “Output 2”, “Output 3” and “Output 4”. These outputs make all the DMUs efficient (i.e., efficiency equal to 1) and thus the average efficiency is 1. Clearly, v(3) −v(2) > v(2) −v(1), and therefore v(·)is not concave. A greedy approach is provided in Pastor et al. [2002] to address the feature selection problem in a nested fashion. In short, this greedy nested procedure works as follows. For p= 1, (OSDEA(p)) is solved to optimality. Let o(1) be its best output. For p= 2, (OSDEA(p)) is solved to optimality, with the additional constraint that zo(1) = 1. Let o(2) be its best output. In general, for p, (OSDEA(p)) is solved to optimality, with the additional constraints that zo(1) =zo(2) =. . . =zo(p−1) = 1. Let o(p)be its best output. Clearly, this greedy approach returns a sequence of outputs that is nested, i.e., Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 5.3. The joint selection model 85 DMU Input 1 Output 1 Output 2 Output 3 Output 4 1 1 0.6 1 3 1 3 1 3 2 1 0.7 1 3 1 3 1 3 3 1 0.8 1 0 0 4 1 0.9 0 1 0 5 1 1 0 0 1 Table 5.1: Toy example for which v(·)is not concave DMU Input 1 Output 1 Output 2 Output 3 1 1 0.85 0.2 0.8 2 1 0.95 0.4 0.6 3 1 0.9 0.6 0.4 4 1 1 0.8 0.2 Table 5.2: Toy example for which the approach in Pastor et al. [2002] does not provide the optimal solution to (OSDEA(p)) the outputs selected in iteration p−1will also be selected in iteration p, for all p. The following is a toy example that illustrates that the approach in Pastor et al. [2002] does not provide, in general, the optimal solution to (OSDEA(p)). Counterexample 2. Consider 4DMUs, each one described by a single input and three different outputs, as can be seen in Table 2. When performing the feature selection procedure, the results that we obtain are the following. In the case of selecting just one output, say p= 1, the procedure chooses “Output 1” and the obtained efficiencies are then just the same as the values of “Output 1" for each DMU. When two outputs are selected, the procedure chooses “Output 2” and “Output 3”. These outputs make all the DMUs efficient. However, if either “Output 1” and “Output 2” or “Output 1” and “Output 3” were used instead, the efficiencies would be {0.85,0.9,0.95,1} and {1,1,0.927,1}, respectively. 5.3.2 Alternative objective functions In (OSDEA(p)), we maximize the average efficiency across all DMUs. In this section, we propose other objective functions φ() to select the outputs. A straightforward generalization would be to consider the weighted average efficiency. φ(w)(α,β,z) = 1 K K X k=1 M X o=1 ω(k)β(k) oy(k) o.(5.23) This is relevant if the DMUs are not equally important. If there is only one input, say cost in $, we could for example use w(k)=x(k), and (5.23) would correspond to Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 86 Chapter 5. Feature selection for benchmarking via DEA formulation minimizing the total sector loss from inefficiency. Instead of the weighted average efficiency, one could be interested in measuring how far each DMU is from efficiency. This can be measured with the following quadratic function φ(q)(α,β,z) = 1 K K X k=1 (1 − M X o=1 β(k) oy(k) o)2.(5.24) Alternatively, our goal could have been maximizing the worst efficiency, i.e., the minimum one φ(m)(α,β,z) = min k=1,...,K M X o=1 β(k) oy(k) o.(5.25) This is relevant, for example, if outputs are selected with the aim of being Rawlsian fair towards all DMUs. Instead of the minimum, we could have optimized another πpercentile, π= 1,...,100, of the efficiency distribution. Assuming that the efficiencies are given in non-decreasing order, PM o=1 β(k) oy(k) o≤PM o=1 β(k+1) oy(k+1) o, for all k, we would have φ(π)(α,β,z) = M X o=1 β(k(π)) oy(k(π)) o,(5.26) with k(π) = bKπ 100c. The Output Selection for DEA problem where the goal is to maximize φ(w) in (5.23), (OSDEA(p))(w), can be formulated in the same fashion as (OSDEA(p)). The Output Selection for DEA problem where the goal is to maximize φ(q) in (5.24), (OSDEA(p))(q), can be formulated similarly to (OSDEA(p)). While the feasible region remains the same, the objective function becomes quadratic and the goal is to minimize it, yielding a Mixed Integer Quadratic Programming formulation. The Output Selection for DEA problem where the goal is to maximize the minimum efficiency φ(m) in (5.25), (OSDEA(p))(m) can be written as an MILP. Here, we need to define a new variable λto rewrite the minimum in the objective function, and include the corresponding constraints to ensure that the new variable is well defined. λ≤ M X o=1 β(k) oy(k) ok= 1, . . . , K, (5.27) and thus maximize(α,β,z,λ)λ(5.28) s.t. (OSDEA(p))(m) (5.15) −(5.18);(5.2) −(5.4);(5.27). Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 5.4. Numerical section 87 The Output Selection for DEA problem where the goal is to maximize the πpercentile φ(π)in (5.26), (OSDEA(p))(π), can also be written as an MILP, similarly as in Benati [2015]. We need to define a new variable λthat is equal to the percentile, as well as include the corresponding constraints to ensure that the new variable is well defined. We also need a new binary variable, δ(k), that is equal to 1if the efficiency of DMU k,PM o=1 β(k) oy(k) o, is at least λand 0otherwise. maximize(α,β,z,λ,δ)λ(5.29) s.t. (OSDEA(p))(π) (5.15) −(5.18);(5.2) −(5.4) M X o=1 β(k) oy(k) o≥λ−M0 1(1 −δ(k))∀k= 1, . . . , K (5.30) K X k=1 δ(k)=bKπ 100c(5.31) δ(k)∈ {0,1} ∀k= 1, . . . , K, (5.32) with M0 1a big constant. 5.4 Numerical section In this section, we illustrate the models in previous sections using a real-world dataset in benchmarking of electricity DSOs Agrell and Bogetoft [2017, 2018]. Here, we have K= 182 DMUs, M= 100 outputs, and N= 1 input. As customary, each output has been normalized dividing it by the difference between the maximum and the minimum values of the output. Figure 5.1 displays the correlations between the outputs, with darker colours pointing at higher correlations. This matrix reveals subsets of outputs highly correlated with each other, such as outputs 23 to 31, where correlations are above 0.5, except for corr(23,27) = 0.37 and corr(27,29) = 0.35. The experiments were run on a computer with an IntelrCoreTM i7-6700 processor at 3.4GHz using 16 GB of RAM, running Windows 10 Home. All the optimization problems have been solved using Python 3.5 interface Python Core Team [2015] with Gurobi 7.0.1 solver, Gurobi Optimization [2016]. We have solved (OSDEA(p)) for p= 1,...,10, with M1equal to 1000. We have run the approach in Pastor et al. [2002] to provide (OSDEA(p)) with an initial solution. A time limit of 300 seconds has been imposed, although this is not binding for small values of p. Once (OSDEA(p)) has selected the poutputs, p= 1,...,10, we calculate the efficiencies of the DSOs obtained with the chosen outputs. The results are summa- Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 88 Chapter 5. Feature selection for benchmarking via DEA formulation pmin max mean st. dev. q1q2q3q3-q1selected features 1 0.0000 1.0000 0.5555 0.1695 0.4743 0.5637 0.6300 0.1557 59 2 0.0006 1.0000 0.6553 0.1708 0.5772 0.6682 0.7482 0.1710 11 31 3 0.0009 1.0000 0.7118 0.1643 0.6391 0.7222 0.7839 0.1448 21 31 54 4 0.1161 1.0000 0.7487 0.1511 0.6645 0.7479 0.8404 0.1759 16 21 31 59 5 0.1161 1.0000 0.7812 0.1494 0.6962 0.7738 0.8911 0.1949 16 21 31 59 94 6 0.3105 1.0000 0.8082 0.1402 0.7222 0.8068 0.9305 0.2083 16 19 21 31 59 94 7 0.3105 1.0000 0.8290 0.1404 0.7474 0.8355 0.9545 0.2071 16 19 21 31 59 91 94 8 0.3105 1.0000 0.8462 0.1402 0.7658 0.8689 0.9802 0.2144 16 19 21 31 59 91 94 97 9 0.3105 1.0000 0.8610 0.1370 0.7789 0.8841 0.9972 0.2183 16 19 21 31 59 74 91 94 97 10 0.4576 1.0000 0.8732 0.1304 0.7902 0.9090 1.0000 0.2098 16 19 21 29 31 59 74 91 94 97 Table 5.3: Summary statistics for the distribution of efficiencies, for p= 1,...,10 rized in Table 5.4, and Figures 5.3 and 5.2, while the correlation matrix in Figure 5.4 highlights the correlations between the selected outputs. Table 5.4 presents summary statistics of the distribution of the efficiencies, namely the minimum, the maximum, the average (i.e., v(p)), the standard deviation, the quartiles qi, and the interquartile range (i.e., q3-q1). The last column of this table reports the selected outputs. Figure 5.2 displays the box-and-whiskers plots as well as the average efficiency v(p), and Figure 5.3 the histograms of the distribution of the efficiencies. The average efficiency improves with the number of selected outputs, p, increasing from 0.5555 to 0.8732. Figure 5.2 shows that the marginal effect of increasing pto p+ 1 is decreasing for this dataset. When looking at the quartiles, we can see that there is a substantial improvement too by increasing p. When the number of selected features, p, is small the chosen features give poor efficiencies to some of the DMUs. Indeed, for p≤5, the minimum efficiency is below 0.1200. As pincreases, we can see that this minimum increases rapidly with p. The first quartile increases from 0.4743 to 0.7902. Similarly, for the median, we have 0.5637 to 0.9090, while for the third quartile 0.6300 to 1.0000. The maximum efficiency is already maximal, i.e., equal to 1.0000, for the smallest value of p, and remains like that for all values of ptested. In general, the standard deviation of the efficiencies decreases with p, while the interquartile range increases. In terms of the correlations, for small values of p, the selected outputs are highly correlated with each other. For instance, for p= 2, we choose outputs 11 and 31, for which corr(11,31) = 0.91; while for p= 3, we choose outputs 21, 31, 54, with corr(21,31) = 0.89, corr(21,54) = 0.88 and corr(31,54) = 0.91.Actually, for p= 2,...,5, the smallest correlation between the selected outputs is equal to 0.61. For p= 10, there are only two outputs, for which we can find correlations below 0.5, namely outputs 19 and 74. In real-life applications, the DMUs may be consulted on the chosen outputs. This may be useful to ensure that the resulting choices make conceptual sense. However, such involvement is likely to lead strategic behavior. The evaluated DMUs may try to influence the choice of outputs in their own advantage. This may lead to a game Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 5.4. Numerical section 89 between the DMUs (the players), each of which has preferred selections of outputs (strategies), and the modeler, who is trying to make a reasonable selection based on the resulting efficiencies of all DMUs (the outcome). To start investigating the challenges of such strategic behavior, we will consider a simple game or social choice problem. Without loss of generality, we assume that pis fixed. We assume that there are Kplayers, the DMUs, and K+ 1 strategies or choices, namely the selection of outputs zk(p)according to the individual preferences as determined by (OSDEA(k)(p)), k= 1, . . . , K, and to the joint selection z(p)as determined by (OSDEA(p)). We will think of the joint selection z(p)as the default or status quo selection and the question is now if one of the individual selections zk(p) would be preferred by a large group of DMUs. If so, the modeler is likely to face strong opposition to his proposed selection of outputs. For DMU k0, the selection of outputs made with (OSDEA(k0)(p)), z(k0)(p), is at least as attractive as the one made with (OSDEA(p)), z(p), or in other words, the reported efficiency with z(k0)(p)is at least as high as the one with z(p). However, for any other DMU k6=k0, it is not clear whether the selection z(k0)(p)reports a higher efficiency for DMU kor not. One would like to know how many DMUs prefer the joint strategy z(p) over the Kindividual strategies z(k0)(p). The so-called cross-efficiency measures this preference. Let ∆(k)(k0) = E(k)(z(k0)(p)) −E(k)(z(p)), with k, k0= 1, . . . , K, be equal to the difference in reported efficiency for DMU kby the joint selection model and the individual selection model for DMU k0. We can define Π(k0) = 100 Kcardinality({k: ∆(k)(k0)>0}), i.e., the percentage of DMUs that prefer the individual strategy of DMU k0over the joint one. In Figure 5.5, we illustrate the share of DMUs that prefer individual selections to the joint selection. As for the joint strategy, a time limit of 300 seconds has been imposed to (OSDEA(k0)(p)), although this is not binding for any value of p. We have binned the support to the individual selections in intervals of width 5%. The height of the first bar indicates how many individual strategies are preferred by [0%,5%) of the DMUs, the height of the second bar corresponds to [5%,10%) DMUs supporting it, etc. When pincreases, we see that less individual strategies are preferred by many DMUs over the joint strategy. Indeed, for values of pabove 5, the joint strategy is supported by at least 50% of the DMUs over any of the individual strategies, while for values of pabove 7, this becomes at least 60%. We can therefore conclude that, in this simple game, as the model gets larger, it becomes less likely that a large group of DMUs will agree on alternative to the modeler’s selection. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Chapter 6 General Conclusions and Further Work 97 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 99 In this PhD dissertation, Mathematical Optimization and Statistics have been used together as tools for the development of new models in Data Science. In particular, we focus on Support Vector Machines (SVM) (Chapters 2 to 4) and Benchmarking (Chapter 5). The works that has been presented here are motivated by the fact that in these recent years, the extraction of knowledge for both learning and interpreting information from datasets has became one of the most relevant tasks in Science and other fields of knowledge. Regarding SVM, we have first proposed, in Chapter 2, a novel SVM model in which performance constraints are included in order to control the different misclassification costs. This is of particular importance in presence of imbalancedness in the dataset. In order to do that, threshold values for the misclassification rates are given to the model. Later, in Chapter 3, we have addressed the problem of obtaining class probabilities estimates for SVM. The method proposed is, contrary to existing proposals, distribution-free and cost-sensitive. Furthermore, it provides confidence intervals for both the score values and the posterior class probabilities. We close the SVM part by proposing a mathematical-optimization-based Feature Selection procedure for SVM in Chapter 4. Such a proposal consist on an embedded method, which also includes the idea of controlling the misclassification rates. Concerning Benchmarking, we propose in Chapter 5 a single-model approach for feature (inputs and outputs) selection in Data Envelopment Analysis (DEA). In this work, opposed to previous literature on feature selection in DEA, our method is purely based on mathematical programming instead of on a mixture of statistical and mathematical programming methods. The research addressed in this dissertation poses new problems and challenges to be considered as future work. A possible extension concerning the results of Chapter 2 would be expand the presented approach to the case when using more complex data as multi-class or multiway arrays (Lyu et al. 2017) instead of two-ways data matrices and two-class problems as currently done. On the other hand, an alternative perspective for addressing the SVM regularization is to consider different norms (Yao and Lee 2014). Finally, another possible extension is to perform a feature selection which uses the proposed constraints in order to control the misclassification costs, as done in Benítez-Peña et al. [2019a] and also presented in Chapter 4. Such a process is an essential step in tasks such as high-dimensional microarray classification problems (Guo 2010). A number of new problems deriving from Chapter 3 are stated next. First, as previously commented, the basis classifier used in this chapter is the SVM with linear kernel. However, more complex kernels (such as the RBF) can be used in order to obtain more powerful classifiers. On the other hand, traditional SVM can be used as a basis for addressing multiclass problems. How to extend properly our approach to such multiclass problems is an interesting research avenue which is now under investigation. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 100 Chapter 6. General Conclusions and Further Work Several extensions of the approach presented in Chapter 4 are possible. In our opinion, they deserve further study. First, several classification and regression procedures based on optimization problems, such as Support Vector Regression, logistic regression or distance-weighted discrimination, are amenable to address, as done here, an integrated FS and classification or regression. The optimization problems obtained in this way have a structure which should be exploited to make the approach competitive and including cost-sensitivity in the FS procedure. Second, even within SVM, it should be observed that SVM is a tool for binary classification. For multiclass datasets, SVM classification is performed by solving a series of SVM problems, see Cristianini and Shawe-Taylor [2000]; Wang and Shen [2007]. When some classes are hard to identify, the basic multiclass strategies may yield discouraging results. Performing simultaneously feature selection and class fusion, as in Guo [2010], is an interesting nontrivial extension of our approach. To do this, problems (P1),(P2) and (P3) need to be conveniently modified. Finally, the results of Chapter 5 can be extended as follows. We have talked about the introduction of a game theory element and how to analyze different conflicts regarding the feature selection. Nevertheless, in the future, it would however be relevant to further explore better these issues. One limitation of our analysis above is that we only consider Kspecific alternatives to the modeler’s joint selection. In theory, there are, of course, many more alternatives. Indeed, any subset of size pfrom the set of potential outputs Mcould potentially muster the support of many DMUs against the modeler’s proposal. The strategic analysis of all possible alternatives is likely to become overwhelming. It may therefore be relevant to introduce some restrictions. One idea is to detect relevant clusters of DMUs and make the selection of features tailored to them. By looking at likely interest groups, the game theoretical analysis may be less complex. Groupings could, for example, refer to small versus large, start-up versus well-established, urban versus rural, and investor-owned versus cooperatively owned DMUs. Also, it would be interesting to add constraints to the feature selection model in order to guarantee the support of a number of DMUs, e.g., a majority of DMUs, hereby modeling more general game theoretical aspects, such as the scope for forming coalitions. In general, there exist many challengers extensions of the works presented in this PhD dissertation as well as the study of alternative applications of Mathematical Optimization and Statistics to both the fields of Supervised Classification and Benchmarking. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 List of Figures 2.1 Study of feasiblity and unfeasibility of the CSVM. . . . . . . . . . . . . 21 3.1 Fit (in solid line) of the sigmoid function to the empirical class probabilities (dots) of adult and wisconsin datasets. . . . . . . . . . . . . . 35 3.2 Histogram of scores for a single instance when a k-fold CV is used. Here, we set k= 20,100 and 500, obtaining as many score values as the value of k. ...................................... 38 3.3 Histogram of scores for a single instance when the Bootstrap with B replications is used. As in the k-fold CV, B= 20,100 and 500. . . . . . 39 3.4 Flowchart of the Bootstrap-based methodology for obtaining P(y= +1 | x). ....................................... 43 3.5 Control over the probabilities estimation. In Subfigures 3.6(a) we can observe the original estimated probabilities, whereas in Subfigures 3.5(b) the new cost-sensitive probabilities for 3.6(a), obtained by moving the threshold, are depicted. . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.6 Confidence intervals for the scores values (Top panel) and the probabilities P(y=−1|x)(Bottom panel), as well as actual values P(y=−1) (light colour) for some instances of german dataset. . . . . . . . . . . . . 49 5.1 Correlation matrix for the outputs, highlighting the correlation between with the selected outputs for p= 10 .................... 91 5.2 Box-and-whiskers plots of efficiencies, including average efficiency, for p= 1,...,10 ................................. 92 5.3 Histograms of the distribution of the efficiencies, p= 1,...,10 ..... 93 5.4 Correlation matrix for the selected outputs for p= 10 .......... 94 5.5 Histograms of the distribution of preferences of individual strategies over the joint strategy, p= 1,...,10 ....................... 95 101 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 List of Tables 1.1 Performance of standard SVM with Radial Function Basis kernel for wisconsin dataset. Average values and standard deviations computed from10realizations. ............................. 6 2.1 Details concerning the implementation of the CSVM for the considered datasets..................................... 26 2.2 Results under the SVM, SVM(C+, C−), the Sliding βstrategy and the novel CSVM. Target rate: TPR . . . . . . . . . . . . . . . . . . . . . . . 27 3.1 Datasets.................................... 46 3.2 Mean squared errors (MSE) obtained when predicting the posterior class probabilities in a linear SVM. . . . . . . . . . . . . . . . . . . . . . . . . 48 3.3 Mean squared errors (MSE) using only the best Cand under the bootstrapbasedapproach................................. 48 3.4 MSE for the positive class probability predictions of each dataset. Ctrl1 50 3.5 MSE for the positive class probability predictions of each dataset. Ctrl2 51 3.6 MSE for the negative class probability predictions of each dataset. Ctrl1 52 3.7 MSE for the negative class probability predictions of each dataset. Ctrl2 52 4.1 Details concerning the implementation of the CSVM for the considered datasets..................................... 63 4.2 Performance measures under the cost-sensitive sparse SVM with linear kernel and p∗ 0(+1) =p0(+1),p∗ 0(−1) =p0(−1).................. 64 4.3 Performance measures under the cost-sensitive sparse SVM with linear kernel and p∗ 0(+1) =p0(+1) +p−log α/(2|I1|),p∗ 0(−1) =p0(−1) + p−log α/(2|I−1|). .............................. 65 4.4 Contingency table of the feature selected in Australian.......... 66 4.5 Performance measures under the cost-sensitive sparse SVM with radial kernel and p∗ 0(+1) =p0(+1),p∗ 0(−1) =p0(−1).................. 67 103 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 104 List of Tables 4.6 Performance measures under the cost-sensitive sparse SVM with radial kernel and p∗ 0(+1) =p0(+1) +p−log α/(2|I1|),p∗ 0(−1) =p0(−1) + p−log α/(2|I−1|). .............................. 68 4.7 Performance measures under the cost-sensitive sparse SVM with linear kernel and p∗ 0(+1) =p0(+1),p∗ 0(−1) =p0(−1) and comparative with the method in Chan et al. [2007],Ghaddar and Naoum-Sawaya [2018]. . . . . 69 4.8 Performance measures under the cost-sensitive sparse SVM with linear kernel and p∗ 0(+1) =p0(+1) +p−log α/(2|I1|),p∗ 0(−1) =p0(−1) + p−log α/(2|I−1|)and comparative with the method in Chan et al. [2007],Ghaddar and Naoum-Sawaya [2018]. . . . . . . . . . . . . . . . . . . . . . . . 70 4.9 Performance measures using the method in Chan et al. [2007],Ghaddar and Naoum-Sawaya [2018], varying the maximum number of features from 1 (minimum) to 34 (maximum) in Australian dataset. . . . . . . 71 4.10 Performance measures using the method in Chan et al. [2007],Ghaddar and Naoum-Sawaya [2018], varying the maximum number of features from 1 (minimum) to 34 (maximum) in Australian dataset. . . . . . . 72 5.1 Toy example for which v(·)is not concave . . . . . . . . . . . . . . . . . 85 5.2 Toy example for which the approach in Pastor et al. [2002] does not provide the optimal solution to (OSDEA(p)) ............... 85 5.3 Summary statistics for the distribution of efficiencies, for p= 1,...,10 . 88 Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 List of Tables 105 Appendix In this section we describe step by step how formulation (4.2) is built from equation (4.1). Hence, let us suppose first that we have the model minω,β,ξ,z ω>ω+CPi∈Iξi s.t. yi(ω>xi+β)≥1−ξi, i ∈I 0≤ξi≤M1(1 −zi)i∈I ˆp`≥ˆp∗ 0``∈L zi∈ {0,1}i∈I. This one can be rewritten as minzminω,β,ξ ω>ω+CP i∈I ξi s.t. zi∈ {0,1}i∈Is.t. yiω>xi+β≥1−ξi, i ∈I ˆp`≥ˆp∗ 0``∈L0≤ξi≤M1(1 −zi)i∈I If we assume that the binary variables zfixed, the Karush–Kuhn–Tucker (KKT) conditions for the inner problem are ω=P i∈I λiyixi 0 = P i∈I λiyi 0≤λi≤C/2i∈I. Substituting these expressions into the last optimization problem, the partial dual of such problem can be calculated, obtaining min zmin λ,β,ξ P i∈I λiyixi!> P i∈I λiyixi!+CP i∈I ξi s.t. zi∈ {0,1}i∈Is.t. yi  P i∈I λiyixi!> xi+β ≥1−ξii∈I ˆp`≥ˆp∗ 0``∈L0≤ξi≤M1(1 −zi)i∈I P i∈I λiyi= 0 0≤λi≤C/2i∈I As a last step, the kernel trick is used and the final formulation (4.2) is obtained. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 112 References Corne, D., Dhaenens, C., and Jourdan, L. (2012). Synergies between operations research and data mining: The emerging use of multi-objective approaches. European Journal of Operational Research, 221(3):469–479. Cortes, C. and Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3):273–297. Coussement, K. (2014). Improving customer retention management through costsensitive learning. European Journal of Marketing. Cristianini, N. and Shawe-Taylor, J. (2000). An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press. Datta, S. and Das, S. (2015). Near-Bayesian Support Vector Machines for imbalanced data classification with equal or unequal misclassification costs. Neural Networks, 70:39–52. Deo, R. C. (2015). Machine learning in medicine. Circulation, 132(20):1920–1930. Dheeru, D. and Karra Taniskidou, E. (2017). UCI machine learning repository. http: //archive.ics.uci.edu/ml, University of California, Irvine, School of Information and Computer Sciences. Efron, B. (2000). The bootstrap and modern statistics. Journal of the American Statistical Association, 95(452):1293–1296. Efron, B. and Tibshirani, R. (1986). Bootstrap methods for standard errors, confidence intervals, and other measures of statistical accuracy. Statistical science, pages 54–75. Emrouznejad, A. and Yang, G.-L. (2018). A survey and analysis of the first 40 years of scholarly literature in DEA: 1978–2016. Socio-Economic Planning Sciences, 61:4–8. Fernandez-Palacin, F., Lopez-Sanchez, M., and Munõz-Márquez, M. (2018). Stepwise selection of variables in DEA using contribution loads. Pesquisa Operacional, 38(1):31–52. Fethi, M. D., Jackson, P. M., and Weyman-Jones, T. G. (2001). European airlines: a stochastic dea study of efficiency with market liberalisation. Fodor, I. K. (2002). A survey of dimension reduction techniques. Technical report, Lawrence Livermore National Lab., CA (US). Franc, V., Zien, A., and Schölkopf, B. (2011). Support vector machines as probabilistic models. In Proceedings of the 28th International Conference on Machine Learning, pages 665–672, Madison, WI, USA. International Machine Learning Society. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 References 113 Freitas, A., Costa-Pereira, A., and Brazdil, P. (2007). Cost-Sensitive Decision Trees Applied to Medical Data. In Data Warehousing and Knowledge Discovery: 9th International Conference, DaWaK 2007, Regensburg Germany, September 3-7, 2007. Proceedings, pages 303–312, Berlin, Heidelberg. Springer Berlin Heidelberg. Friedman, J., Hastie, T., and Tibshirani, R. (2001). The elements of statistical learning, volume 1. Springer series in statistics New York. Fung, G. M. and Mangasarian, O. L. (2004). A Feature Selection Newton Method for Support Vector Machine Classification. Computational Optimization and Applications, 28(2):185–202, http://dx.doi.org/10.1023/B:COAP.0000026884.66338. df, doi:10.1023/B:COAP.0000026884.66338.df. Gambella, C., Ghaddar, B., and Naoum-Sawaya, J. (2021). Optimization problems for machine learning: A survey. European Journal of Operational Research, 290(3):807 – 828, http://www.sciencedirect.com/science/article/pii/ S037722172030758X, doi:https://doi.org/10.1016/j.ejor.2020.08.045. Ghaddar, B. and Naoum-Sawaya, J. (2018). High dimensional data classification and feature selection using support vector machines. European Journal of Operational Research, 265(3):993 – 1004, http://www.sciencedirect.com/science/article/ pii/S0377221717307713, doi:https://doi.org/10.1016/j.ejor.2017.08.040. Ghatasheh, N., Faris, H., AlTaharwa, I., Harb, Y., and Harb, A. (2020). Business analytics in telemarketing: cost-sensitive analysis of bank campaigns using artificial neural networks. Applied Sciences, 10(7):2581. Golany, B. and Roll, Y. (1989). An application procedure for DEA. Omega, 17(3):237– 250. Golub, T. R., Slonim, D. K., Tamayo, P., Huard, C., Gaasenbeek, M., Mesirov, J. P., Coller, H., Loh, M. L., Downing, J. R., Caligiuri, M. A., Bloomfield, C. D., and Lander, E. S. (1999a). Molecular classification of cancer: Class discovery and class prediction by gene expression monitoring. Science, 286(5439):531–537, http://science. sciencemag.org/content/286/5439/531, doi:10.1126/science.286.5439.531. Golub, T. R., Slonim, D. K., Tamayo, P., Huard, C., Gaasenbeek, M., Mesirov, J. P., Coller, H., Loh, M. L., Downing, J. R., Caligiuri, M. A., et al. (1999b). Molecular classification of cancer: class discovery and class prediction by gene expression monitoring. science, 286(5439):531–537. Gonen, M., Tanugur, A. G., and Alpaydin, E. (2008). Multiclass posterior probability support vector machines. IEEE Transactions on Neural Networks, 19(1):130–139, doi:10.1109/TNN.2007.903157. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 114 References Green, R., Doyle, J., and Cook, W. (1996). Preference voting and project ranking using dea and cross-evaluation. European Journal of Operational Research, 90(3):461–472. Greene, W. H. (1990). A gamma-distributed stochastic frontier model. Journal of Econometrics, 46(1):141 – 163, http://www.sciencedirect.com/science/ article/pii/030440769090052U, doi:https://doi.org/10.1016/0304-4076(90)90052- U. Greene, W. H. (2003). Econometric analysis. Pearson Education India. Guo, G., Wang, H., Bell, D., Bi, Y., and Greer, K. (2003). Knn model-based approach in classification. In OTM Confederated International Conferences" On the Move to Meaningful Internet Systems", pages 986–996. Springer. Guo, J. (2010). Simultaneous variable selection and class fusion for high-dimensional linear discriminant analysis. Biostatistics, 11(4):599, doi:10.1093/biostatistics/kxq023. Gurobi Optimization, I. (2016). Gurobi Optimizer Reference Manual. http://www. gurobi.com. Guyon, I. and Elisseeff, A. (2003). An Introduction to Variable and Feature Selection. Journal of Machine Learning Research, 3(Mar):1157–1182. Guyon, I., Weston, J., Barnhill, S., and Vapnik, V. (2002). Gene selection for cancer classification using support vector machines. Machine learning, 46(1-3):389–422. Harman, H. (1976). Modern Factor Analysis. University of Chicago Press, 3rd edition. Harrison, D. and Rubinfeld, D. L. (1978). Hedonic housing prices and the demand for clean air. Journal of Environmental Economics and Management, 5(1):81–102, https://www.sciencedirect.com/science/article/pii/ 0095069678900062, doi:https://doi.org/10.1016/0095-0696(78)90006-2. Hastie, T. and Tibshirani, R. (1998). Classification by pairwise coupling. In Advances in neural information processing systems, pages 507–513. Hastie, T., Tibshirani, R., and Friedman, J. (2001). The Elements of Statistical Learning. Springer Series in Statistics. Springer New York Inc., New York, NY, USA. He, H. and Ma, Y. (2013). Imbalanced learning: foundations, algorithms, and applications. John Wiley & Sons, Inc. Herbrich, R., Graepel, T., and Campbell, C. (1999). Bayesian learning in reproducing kernel Hilbert spaces. Leiter der Fachbibliothek Informatik, Sekretariat FR 5-4. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 References 115 Hoeffding, W. (1963). Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301):13–30. Horn, D., Demircioğlu, A., Bischl, B., Glasmachers, T., and Weihs, C. (2016). A comparative study on large scale kernelized support vector machines. Advances in Data Analysis and Classification. Hsu, C.-W., Chang, C.-C., Lin, C.-J., et al. (2003). A practical guide to support vector classification. Technical report, Department of Computer Science, National Taiwan University. Huang, B., Kechadi, M. T., and Buckley, B. (2012). Customer churn prediction in telecommunications. Expert Systems with Applications, 39(1):1414–1425. Huang, X., Wu, L., and Ye, Y. (2019). A review on dimensionality reduction techniques. International Journal of Pattern Recognition and Artificial Intelligence, 33(10):1950017. J.-Y. Cai, C.-Y. L. (2016). LASSO variable selection techniques in data envelopment analysis. In The 17th Asia Pacific Industrial Engineering and Management Systems Conference (APIEMS 2016), Taipei, Taiwan. Jiang, C. and Lin, W. (2015). DEARank: a data-envelopment-analysis-based ranking method. Machine Learning, 101(1–3):415–435. Joro, T. and Korhonen, P. (2015). Data envelopment analysis. In Extension of Data Envelopment Analysis with Preference Information, pages 15–26. Springer. Karatzoglou, A., Meyer, D., and Hornik, K. (2006). Support vector machines in r. Journal of Statistical software, 15(9):1–28. Keramati, A. and Ardabili, S. M. (2011). Churn analysis for an iranian mobile operator. Telecommunications Policy, 35(4):344–356. Kim, S., Yu, Z., Kil, R. M., and Lee, M. (2015). Deep learning of support vector machines with class probability output networks. Neural Networks, 64:19 – 28, http://www.sciencedirect.com/science/article/pii/S0893608014002172, doi:https://doi.org/10.1016/j.neunet.2014.09.007. Special Issue on “Deep Learning of Representations”. Kohavi, R. et al. (1995). A study of cross-validation and bootstrap for accuracy estimation and model selection. In Ijcai, volume 14, pages 1137–1145. Stanford, CA. Kononenko, I. (2001). Machine learning for medical diagnosis: history, state of the art and perspective. Artificial Intelligence in medicine, 23(1):89–109. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 116 References Kruppa, J., Liu, Y., Biau, G., Kohler, M., König, I. R., Malley, J. D., and Ziegler, A. (2014). Probability estimation with machine learning methods for dichotomous and multicategory outcome: Theory. Biometrical Journal, 56(4):534–563, https://onlinelibrary.wiley.com/doi/abs/10.1002/bimj. 201300068, doi:https://doi.org/10.1002/bimj.201300068. Kudva, V. and Prasad, K. (2018). Pattern classification of images from acetic acid– based cervical cancer screening: A review. Critical Reviews™in Biomedical Engineering, 46(2). Kwok, J. T.-Y. (1998). Integrating the evidence framework and the support vector machine. In ESANN, volume 99, pages 177–182. Kwok, J. T.-Y. (1999). Moderating the outputs of support vector machine classifiers. IEEE Transactions on Neural Networks, 10(5):1018–1031. Lal, T. N., Chapelle, O., Weston, J., and Elisseeff, A. (2006). Embedded methods. In Feature extraction, pages 137–165. Springer. Land, K. C., Lovell, C. K., and Thore, S. (1993). Chance-constrained data envelopment analysis. Managerial and decision economics, 14(6):541–554. Landete, M., Monge, J., and Ruiz, J. (2017). Robust DEA efficiency scores: A probabilistic/combinatorial approach. Expert Systems with Applications, 86:145–154. Le Thi, H. A., Le, H. M., and Dinh, T. P. (2015). Feature selection in machine learning: an exact penalty approach using a Difference of Convex function Algorithm. Machine Learning, 101(1):163–186. Lee, C.-Y. and Cai, J.-Y. (2020). LASSO variable selection in data envelopment analysis with small datasets. Omega, 91:102019. Li, Y., Shi, X., Yang, M., and Liang, L. (2017a). Variable selection in data envelopment analysis via akaike’s information criteria. Annals of Operations Research, 253(1):453– 476. Li, Z., Crook, J., and Andreeva, G. (2017b). Dynamic prediction of financial distress using Malmquist DEA. Expert Systems with Applications, 80:94–106. Lichman, M. (2013). UCI Machine Learning Repository. http://archive.ics.uci. edu/ml, University of California, Irvine, School of Information and Computer Sciences. Lin, H.-T., Lin, C.-J., and Weng, R. C. (2007). A note on platt’s probabilistic outputs for support vector machines. Machine learning, 68(3):267–276. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 References 117 Lin, Y., Lee, Y., and Wahba, G. (2002). Support vector machines for classification in nonstandard situations. Machine Learning, 46(1-3):191–202. Lorena, A. and de Carvalho, A. (2008). Evolutionary tuning of SVM parameter values in multiclass problems. Neurocomputing, 71:3326–3334. Lovell, C. K. et al. (1993). Production frontiers and productive efficiency. The measurement of productive efficiency: Techniques and applications, 3:67. Luo, Y., Bi, G., and Liang, L. (2012). Input/output indicator selection for DEA efficiency evaluation: An empirical study of Chinese commercial banks. Expert Systems with Applications, 39(1):1118–1123. Lyu, T., Lock, E. F., and Eberly, L. E. (2017). Discriminating sample groups with multi-way data. Biostatistics. Maldonado, S., Domínguez, G., Olaya, D., and Verbeke, W. (2021). Profitdriven churn prediction for the mutual fund industry: A multisegment approach. Omega, 100:102380, https://www.sciencedirect.com/science/article/ pii/S0305048320307349, doi:https://doi.org/10.1016/j.omega.2020.102380. Maldonado, S., Pérez, J., and Bravo, C. (2017). Cost-based feature selection for support vector machines: An application in credit scoring. European Journal of Operational Research, 261(2):656 – 665, http://www.sciencedirect.com/science/ article/pii/S0377221717301595, doi:https://doi.org/10.1016/j.ejor.2017.02.037. Maldonado, S. and Weber, R. (2009). A wrapper method for feature selection using support vector machines. Information Sciences, 179(13):2208 – 2217, http://www.sciencedirect.com/science/article/pii/S0020025509000917, doi:https://doi.org/10.1016/j.ins.2009.02.014. Special Section on High Order Fuzzy Sets. Maldonado, S., Weber, R., and Basak, J. (2011). Simultaneous feature selection and classification using kernel-penalized support vector machines. Information Sciences, 181(1):115 – 128, http://www.sciencedirect.com/science/article/pii/ S0020025510004287, doi:https://doi.org/10.1016/j.ins.2010.08.047. Mangasarian, O. L., Street, W. N., and Wolberg, W. H. (1995). Breast cancer diagnosis and prognosis via linear programming. Operations Research, 43(4):570–577. Mansouri, K., Ringsted, T., Ballabio, D., Todeschini, R., and Consonni, V. (2013). Quantitative structure–activity relationship models for ready biodegradability of chemicals. Journal of Chemical Information and Modeling, 53(4):867–878. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 118 References Margineantu, D. D. (2002). Class probability estimation and cost-sensitive classification decisions. In Elomaa, T., Mannila, H., and Toivonen, H., eds., Machine Learning: ECML 2002, pages 270–281, Berlin, Heidelberg. Springer Berlin Heidelberg. Marron, J. S., Todd, M. J., and Ahn, J. (2007). Distance-weighted discrimination. Journal of the American Statistical Association, 102(480):1267–1271. Meisel, S. and Mattfeld, D. (2010). Synergies of Operations Research and Data Mining. European Journal of Operational Research, 206(1):1–10. Mercer, J. (1909). Functions of positive and negative type, and their connection with the theory of integral equations. Philosophical transactions of the royal society of London. Series A, 209:415–446. Milgram, J., Mohamed Cheriet, and Sabourin, R. (2005). Estimating accurate multiclass probabilities with support vector machines. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 3, pages 1906–1911 vol. 3. Moffett, S., Anderson-Gillespie, K., and McAdam, R. (2008). Benchmarking and performance measurement: a statistical analysis. Benchmarking: An International Journal. Murphy, K. P. (2012). Machine learning, a probabilistic perspective. The MIT Press. Nataraja, N. and Johnson, A. (2011). Guidelines for using variable selection techniques in Data Envelopment Analysis. European Journal of Operational Research, 215(3):662–669. Nunamaker, T. (1985). Using data envelopment analysis to measure the efficiency of non-profit organizations: A critical evaluation. Managerial and Decision Economics, 6(1):50–58. Olesen, O. B. and Petersen, N. (1995). Chance constrained efficiency evaluation. Management science, 41(3):442–457. Panagopoulos, O. P., Pappu, V., Xanthopoulos, P., and Pardalos, P. M. (2016). Constrained subspace classifier for high dimensional datasets. Omega, 59:40–46. Parsons, L. J. (2002). Using stochastic frontier analysis for performance measurement and benchmarking. Advances in Econometrics, 16:317–350. Pastor, J., Ruiz, J., and Sirvent, I. (2002). A statistical test for nested radial DEA models. Operations Research, 50(4):728–735. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 References 119 Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al. (2011). Scikit-learn: Machine learning in python. Journal of Machine Learning Research, 12:2825–2830. Petersen, N. (2018). Directional Distance Functions in DEA with Optimal Endogenous Directions. Operations Research, 66(4):1068–1085. Plastria, F. and Carrizosa, E. (2012). Minmax-distance approximation and separation problems: geometrical properties. Mathematical Programming, 132(1):153–177. Platt, J. C. (2000). Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In Advances in large margin classifiers, pages 61–74. MIT Press. Podinovski, V. (2016). Optimal weights in DEA models with weight restrictions. European Journal of Operational Research, 254(3):916–924. Prati, R. C., Batista, G. E., and Silva, D. F. (2015). Class imbalance revisited: a new experimental setup to assess the performance of treatment methods. Knowledge and Information Systems, 45(1):247–270. Python Core Team (2015). Python: A dynamic, open source programming language. Python Software Foundation. {https://www.python.org}. Qin, Z. and Song, I. (2014). Joint Variable Selection for Data Envelopment Analysis via Group Sparsity. ArXiv e-prints arXiv:1402.3740. Ramón, N., Ruiz, J., and Sirvent, I. (2010). On the choice of weights profiles in crossefficiency evaluations. European Journal of Operational Research, 207(3):1564–1572. Richtárik, P. and Takáč, M. (2016). Parallel coordinate descent methods for big data optimization. Mathematical Programming, 156(1):433–484. Ruiz, J. and Sirvent, I. (2016). Common benchmarking and ranking of units with DEA. Omega, 65:1 – 9, http://www.sciencedirect.com/science/article/pii/ S0305048315002510, doi:https://doi.org/10.1016/j.omega.2015.11.007. Ruiz, J. L. and Sirvent, I. (2019). Performance evaluation through DEA benchmarking adjusted to goals. Omega, 87:150–157. Saeys, Y., Inza, I., and Larrañaga, P. (2007). A review of feature selection techniques in bioinformatics. bioinformatics, 23(19):2507–2517. Sánchez, B. N., Wu, M., Song, P. X. K., and Wang, W. (2016). Study design in high-dimensional classification analysis. Biostatistics, 17(4):722, doi:10.1093/biostatistics/kxw018. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 120 References Sarveniazi, A. (2014). An actual survey of dimensionality reduction. American Journal of Computational Mathematics, 4(2):55–72. Seeger, M. (2000). Bayesian model selection for support vector machines, gaussian processes and other kernel classifiers. In Advances in neural information processing systems, pages 603–609. Sexton, T., Silkman, R., and Hogan, A. (1986). Data envelopment analysis: Critique and extensions. New Directions for Program Evaluation, 1986(32):73–105. Shen, X., Tseng, G. C., Zhang, X., and Wong, W. H. (2003). On ψ-learning. Journal of the American Statistical Association, 98(463):724–734. Silva, A. P. D. (2017). Optimization approaches to Supervised Classification. European Journal of Operational Research, 261(2):772–788. Sirvent, I., Ruiz, J., Borrás, F., and Pastor, J. (2005). A Monte Carlo evaluation of several tests for the selection of variables in DEA models. International Journal of Information Technology & Decision Making, 4(03):325–343. Smola, A. J. and Schölkopf, B. (2004). A tutorial on support vector regression. Statistics and Computing, 14(3):199–222. Soleimani-Damaneh, M. and Zarepisheh, M. (2009). Shannon’s entropy for combining the efficiency results of different DEA models: Method and application. Expert Systems with Applications, 36(3, Part 1):5146–5150. Sollich, P. (2002). Bayesian methods for support vector machines: Evidence and predictive class probabilities. Machine learning, 46(1):21–52. Steinberg, D. and Colla, P. (2009). Cart: classification and regression trees. The top ten algorithms in data mining, 9:179. Swan, A. L., Mobasheri, A., Allaway, D., Liddell, S., and Bacardit, J. (2013). Application of machine learning to proteomics data: Classification and biomarker identification in postgenomics biology. OMICS: A Journal of Integrative Biology, 17(12):595–610, https://doi.org/10.1089/omi.2013.0017, doi:10.1089/omi.2013.0017. PMID: 24116388. Tan, F., Fu, X., Zhang, Y., and Bourgeois, A. G. (2008). A genetic algorithm-based method for feature subset selection. Soft Computing, 12(2):111–120. Tang, Y., Zhang, Y. Q., Chawla, N. V., and Krasser, S. (2009). SVMs Modeling for Highly Imbalanced Classification. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 39(1):281–288. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 References 121 Tao, Q., Wu, G.-W., Wang, F.-Y., and Wang, J. (2005). Posterior probability support vector machines for unbalanced data. IEEE Transactions on Neural Networks, 16(6):1561–1573. Tarca, A. L., Carey, V. J., Chen, X.-w., Romero, R., and Drăghici, S. (2007). Machine learning and its applications to biology. PLoS Comput Biol, 3(6):e116. Thomas, L., Crook, J., and Edelman, D. (2017). Credit scoring and its applications. SIAM. Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288. Timofeev, R. (2004). Classification and regression trees (cart) theory and applications. Humboldt University, Berlin, pages 1–40. Tipping, M. (2001). Sparse bayesian learning and the relevance vector machine. Journal of machine learning research, 1(Jun):211–244. Van Rossum, G. and Drake, F. L. (2011). An Introduction to Python. Network Theory Ltd. Vapnik, V. (1995). The Nature of Statistical Learning Theory. Springer-Verlag New York, Inc., New York, NY, USA. Vapnik, V. N. and Vapnik, V. (1998). Statistical learning theory, volume 1. Wiley New York. Wagner, J. and Shimshak, D. (2007). Stepwise selection of variables in Data Envelopment Analysis: Procedures and managerial perspectives. European Journal of Operational Research, 180(1):57–67. Wahba, G. (1992). Multivariate function and operator estimation, based on smoothing splines and reproducing kernels. In Santa Fe Institute Studies in the Sciences of Complexity-Proceedings Volume-, volume 12, pages 95–95. Addison-Wesley Publishing Co. Wahba, G. et al. (1999). Support vector machines, reproducing kernel hilbert spaces and the randomized gacv. Advances in Kernel Methods-Support Vector Learning, 6:69–87. Walker, M. G. and Olshen, R. (1992). Probability estimation for biomedical classification problems. In Proceedings of the Annual Symposium on Computer Application in Medical Care, page 451. American Medical Informatics Association. Código seguro de Verificación : GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 | Puede verificar la integridad de este documento en la siguiente dirección : https://sede.administracionespublicas.gob.es/valida ÁMBITOPREFIJO CSV FECHA Y HORA DEL DOCUMENTO GEISER GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061 14/06/2021 10:40:38 Horario peninsular Nº registro DIRECCIÓN DE VALIDACIÓN Validez del documento T00000494s21N0000080 https://sede.administracionespublicas.gob.es/valida Copia GEISER-a2bf-0c48-eaa0-43fa-a8d6-b1b0-dfb8-d061