Pasar al contenido principal

SOLUCIONES EFECTIVAS BASADAS EN LA LOGICA

TIN2015-69175-C4-1-R

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos I+D+i Retos de Investigación
Año convocatoria 2015
Plan Estatal 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Unidad de gestión Dirección General de Investigación Científica y Técnica
Centro beneficiario UNIVERSITAT POLITÈCNICA DE VALÈNCIA
Identificador persistente http://dx.doi.org/10.13039/501100003329

Resultados relacionados

Resultados totales (Incluyendo duplicados): 30
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Debugging Maude programs via runtime assertion checking and trace slicing

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Ballis, Demis
  • Frechina, F.
In this paper we propose a dynamic analysis methodology for improving the diagnosis of erroneous Maude programs. The key idea is to combine runtime checking and dynamic trace slicing for automatically catching errors at runtime while reducing the size and complexity of the erroneous traces to be analyzed (i.e., those leading to states failing to satisfy some of the assertions). First, we formalize a technique that is aimed at automatically detecting deviations of the program behavior (symptoms) with respect to two types of user-defined assertions: functional assertions and system assertions. The proposed dynamic checking is provably sound in the sense that all errors flagged are definitely violations of the specifications. Then, upon eventual assertion violations we generate accurate trace slices that help identify the cause of the error. Our methodology is based on (i) a logical notation for specifying assertions that are imposed on execution runs; (ii) a runtime checking technique that dynamically tests the assertions; and (iii) a mechanism based on (equational) least general generalization that automatically derives accurate criteria for slicing from falsified assertions. Finally, we report on an implementation of the proposed technique in the assertion-based, dynamic analyzer ABETS and show how the forward and backward tracking of asserted program properties leads to a thorough trace analysis algorithm that can be used for program diagnosis and debugging. © 2016 Elsevier Inc. All rights reserved., This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN2015-69175-C4-1-R and TIN2013-45732-C4-1-P, and by Generalitat Valenciana Ref. PROMETEOII/2015/013. F. Frechina was supported by FPU-ME grant AP2010-5681, and J. Sapiña was supported by FPI-UPV grant SP2013-0083 and mobility grant VIIT-3946.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A computational analysis of general intelligence tests for evaluating cognitive development

  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • Ferri Ramírez, César|||0000-0002-8975-1120
  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Ramírez Quintana, María José|||0000-0002-0559-3568
[EN] The progression in several cognitive tests for the same subjects at different ages provides valuable information about their cognitive development. One question that has caught recent interest is whether the same approach can be used to assess the cognitive development of artificial systems. In particular, can we assess whether the fluid or crystallised intelligence of an artificial cognitive system is changing during its cognitive development as a result of acquiring more concepts? In this paper, we address several IQ tests problems (odd-one-out problems, Raven s Progressive Matrices and Thurstone s letter series) with a general learning system that is not particularly designed on purpose to solve intelligence tests. The goal is to better understand the role of the basic cognitive perational constructs (such as identity, difference, order, counting, logic, etc.) that are needed to solve these intelligence test problems and serve as a proof-of-concept for evaluation in other developmental problems. From here, we gain some insights into the characteristics and usefulness of these tests and how careful we need to be when applying human test problems to assess the abilities and cognitive development of robots and other artificial cognitive systems., This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN 2015-69175-C4-1-R and TIN 2013-45732-C4-1-P, and by Generalitat Valenciana under grant PROMETEOII/2015/013.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Evaluation in artificial intelligence: From task-oriented to ability-oriented measurement

  • Hernández-Orallo, José|||0000-0001-9746-7632
The evaluation of artificial intelligence systems and components is crucial for the progress of the discipline. In this paper we describe and critically assess the different ways AI systems are evaluated, and the role of components and techniques in these systems. We first focus on the traditional task-oriented evaluation approach. We identify three kinds of evaluation: human discrimination, problem benchmarks and peer confrontation. We describe some of the limitations of the many evaluation schemes and competitions in these three categories, and follow the progression of some of these tests. We then focus on a less customary (and challenging) ability-oriented evaluation approach, where a system is characterised by its (cognitive) abilities, rather than by the tasks it is designed to solve. We discuss several possibilities: the adaptation of cognitive tests used for humans and animals, the development of tests derived from algorithmic information theory or more integrated approaches under the perspective of universal psychometrics. We analyse some evaluation tests from AI that are better positioned for an ability-oriented evaluation and discuss how their problems and limitations can possibly be addressed with some of the tools and ideas that appear within the paper. Finally, we enumerate a series of lessons learnt and generic guidelines to be used when an AI evaluation scheme is under consideration., I thank the organisers of the AEPIA Summer School On Artificial Intelligence, held in September 2014, for giving me the opportunity to give a lecture on 'AI Evaluation'. This paper was born out of and evolved through that lecture. The information about many benchmarks and competitions discussed in this paper have been contrasted with information from and discussions with many people: M. Bedia, A. Cangelosi, C. Dimitrakakis, I. GarcIa-Varea, Katja Hofmann, W. Langdon, E. Messina, S. Mueller, M. Siebers and C. Soares. Figure 4 is courtesy of F. Martinez-Plumed. Finally, I thank the anonymous reviewers, whose comments have helped to significantly improve the balance and coverage of the paper. This work has been partially supported by the EU (FEDER) and the Spanish MINECO under Grants TIN 2013-45732-C4-1-P, TIN 2015-69175-C4-1-R and by Generalitat Valenciana PROMETEOII2015/013.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Static correction of Maude programs with assertions

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Ballis, D.
[Otros] In this paper, we present a novel transformation method for Maude programs featuring both automatic program diagnosis and correction. The input of our method is a reference specification of the program behavior that is given in the form of assertions together with an overly general program whose execution might violate the assertions. Our correction technique translates into a refined program in which every computation is also a computation in that satisfies the assertions of . The technique is first formalized for topmost rewrite theories, and then we generalize it to larger classes of rewrite theories that support nested structured configurations. Our technique copes with infinite space states and does not require the knowledge of any failing run. We report experiments that assess the effectiveness of assertion-driven correction., This work has been partially supported by the EU (FEDER) and the Spanish Ministerio de Economia y Competitividad under grant TIN2015-69175-C4-1-R, and by Generalitat Valenciana PROMETEOII/2015/013 and PROMETEO/2019/098
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Identifying the Machine Learning Family from Black-Box Models

  • Fabra-Boluda, Raúl
  • Ferri Ramírez, César|||0000-0002-8975-1120
  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • Ramírez Quintana, María José|||0000-0002-0559-3568
[EN] We address the novel question of determining which kind of machine learning model is behind the predictions when we interact with a black-box model. This may allow us to identify families of techniques whose models exhibit similar vulnerabilities and strengths. In our method, we first consider how an adversary can systematically query a given black-box model (oracle) to label an artificially-generated dataset. This labelled dataset is then used for training different surrogate models (each one trying to imitate the oracle¿s behaviour). The method has two different approaches. First, we assume that the family of the surrogate model that achieves the maximum Kappa metric against the oracle labels corresponds to the family of the oracle model. The other approach, based on machine learning, consists in learning a meta-model that is able to predict the model family of a new black-box model. We compare these two approaches experimentally, giving us insight about how explanatory and predictable our concept of family is., This material is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-17-1-0287, the EU (FEDER), and the Spanish MINECO under grant TIN 2015-69175-C4-1-R, the Generalitat Valenciana PROMETEOII/2015/013. F. Martinez-Plumed was also supported by INCIBE under grant INCIBEI-2015-27345 (Ayudas para la excelencia de los equipos de investigacion avanzada en ciberseguridad). J. H-Orallo also received a Salvador de Madariaga grant (PRX17/00467) from the Spanish MECD for a research stay at the CFI, Cambridge, and a BEST grant (BEST/2017/045) from the GVA for another research stay at the CFI.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Variant-Based Decidable Satisfiability in Initial Algebras with Predicates

  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Meseguer, José
[EN] Decision procedures can be either theory-specific, e.g., Presburger arithmetic, or theory-generic, applying to an infinite number of user-definable theories. Variant satisfiability is a theory-generic procedure for quantifier-free satisfiability in the initial algebra of an order-sorted equational theory (¿,E¿B) under two conditions: (i) E¿B has the finite variant property and B has a finitary unification algorithm; and (ii) (¿,E¿B) protects a constructor subtheory (¿,E¿¿B¿) that is OS-compact. These conditions apply to many user-definable theories, but have a main limitation: they apply well to data structures, but often do not hold for user-definable predicates on such data structures. We present a theory-generic satisfiability decision procedure, and a prototype implementation, extending variant-based satisfiability to initial algebras with user-definable predicates under fairly general conditions., Partially supported by NSF Grant CNS 14-09416, NRL under contract number N00173-17-1-G002, the EU (FEDER), Spanish MINECO project TIN2015-69175- C4-1-R and GV project PROMETEOII/2015/013. Ra´ul Guti´errez was also supported by INCIBE program “Ayudas para la excelencia de los equipos de investigaci´on avanzada en ciberseguridad”.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Reframing in context: A systematic approach for model reuse in machine learning

  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Martínez Usó, Adolfo
  • Prudencio, Ricardo B. C.
  • Kull, Meelis
  • Flach, Peter
  • Ahmed, Chowdhury Farhan
  • Lachiche, Nicolas
We describe a systematic approach called reframing, defined as the process of preparing a machine learning model (e.g., a classifier) to perform well over a range of operating contexts. One way to achieve this is by constructing a versatile model, which is not fitted to a particular context, and thus enables model reuse. We formally characterise reframing in terms of a taxonomy of context changes that may be encountered and distinguish it from model retraining and revision. We then identify three main kinds of reframing: input reframing, output reframing and structural reframing. We proceed by reviewing areas and problems where some notion of reframing has already been developed and shown useful, if under different names: re-optimising, adapting, tuning, thresholding, etc. This exploration of the landscape of reframing allows us to identify opportunities where reframing might be possible and useful. Finally, we describe related approaches in terms of the problems they address or the kind of solutions they obtain. The paper closes with a re-interpretation of the model development and deployment process with the use of reframing., We thank the anonymous reviewers for their comments, which have helped to improve this paper significantly. This work was supported by the REFRAME project, granted by the European Coordinated Research on Long-term Challenges in Information and Communication Sciences Technologies ERA-Net (CHIST-ERA), funded by their respective national funding agencies in the UK (EPSRC, EP/K018728), France and Spain (MINECO, PCIN-2013-037). It has also been partially supported by the EU (FEDER) and Spanish MINECO grant TIN2015-69175-C4-1-R and by Generalitat Valenciana PROMETEOII/2015/013.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

AI Generality and Spearman&apos, s Law of Diminishing Returns

  • Hernández-Orallo, José|||0000-0001-9746-7632
[EN] Many areas of AI today use benchmarks and competitions with larger and wider sets of tasks. This tries to deter AI systems (and research effort) from specialising to a single task, and encourage them to be prepared to solve previously unseen tasks. It is unclear, however, whether the methods with best performance are actually those that are most general and, in perspective, whether the trend moves towards more general AI systems. This question has a striking similarity with the analysis of the so-called positive manifold and general factors in the area of human intelligence. In this paper, we first show how the existence of a manifold (positive average pairwise task correlation) can also be analysed in AI, and how this relates to the notion of agent generality, from the individual and the populational points of view. From the populational perspective, we analyse the following question: is this manifold correlation higher for the most or for the least able group of agents? We contrast this analysis with one of the most controversial issues in human intelligence research, the so-called Spearman's Law of Diminishing Returns (SLODR), which basically states that the relevance of a general factor diminishes for most able human groups. We perform two empirical studies on these issues in AI. We analyse the results of the 2015 general video game AI (GVGAI) competition, with games as tasks and "controllers" as agents, and the results of a synthetic setting, with modified elementary cellular automata (ECA) rules as tasks and simple interactive programs as agents. In both cases, we see that SLODR does not appear. The data, and the use of just two scenarios, does not clearly support the reverse either, a Universal Law of Augmenting Returns (ULOAR), but calls for more experiments on this question., I thank the anonymous reviewers of ECAI'2016 for their comments on an early version of the experiments shown in Section 4. I'm really grateful to Philip J. Bontrager, Ahmed Khalifa, Diego Perez-Liebana and Julian Togelius for providing me with the GVGAI competition data that made Section 3 possible. David Stillwell and Aiden Loe suggested the use of person-fit as a measure of generality. The JAIR reviewers have provided very insightful and constructive comments, which have greatly helped to improve the final version of this paper. This work has been partially supported by the EU (FEDER) and Spanish MINECO grant TIN2015-69175-C4-1-R, and by Generalitat Valenciana PROMETEOII/2015/013 and PROMETEO/2019/098. I also thank the support from the Future of Life Institute through FLI grant RFP2-152. Part of this work has been done while visiting the Leverhulme Centre for the Future of Intelligence, generously funded by the Leverhulme Trust. I also thank the UPV for granting me a sabbatical leave and the funding from the Spanish MECD programme "Salvador de Madariaga" (PRX17/00467) and a BEST grant (BEST/2017/045) from the Generalitat Valenciana for another research stay also at the CFI.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

Cycling network projects: a decision-making aid approach

  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • Ferri Ramírez, César|||0000-0002-8975-1120
  • Contreras Ochando, Lidia
Effcient and clean urban mobility is a key factor in quality of life and sustainability of towns and cities. Traditionally, cities have focused on cars and other fuel-based vehicles as transport means. However, several problems are directly linked to massive car use, particularly in terms of air pollution and traffc congestion. Several works reckon that vehicle emissions produce over 90% of air pollution. One way to reduce the use of fuel-based vehicles (and thus the emission of pollutants) is to create effcient, easily accessible and secure bike lane networks which, as many studies show, promote cycling as a major mean of conveyance. In this regard, this paper presents an approach to design and calculate bike lane networks based on the use of open data about the historical use of a urban bike rental services. Concretely, we model this task as a network design problem (NDP) and we study four di erent optimisation strategies to solve it. We test these methods using data of the city of Valencia (Spain). Our experiments conclude that an optimisation approach based on genetic programming obtains the best performance. The proposed method can be easily used to improve or extend bike lane networks based on historic bike use data in other cities., This work has been partially supported by the EU (FEDER) and Spanish MINECO grant TIN2015-69175-C4-1-R, and the REFRAME project, granted by the European Coordinated Research on Long-term Challenges in Information and Communication Sciences Technologies ERA-Net (CHIST-ERA), and funded by MINECO in Spain (PCIN-2013-037), by Generalitat Valenciana PROMETEOII/2015/013, and by the French National Research agency (ANR).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A dataset of attributes from papers of a machine learning conference

  • Vallejo-Huanga, Diego
  • Morillo, Paulina
  • Ferri Ramírez, César|||0000-0002-8975-1120
[EN] In this work, we present a dataset which provides information on the scientific program of a set conferences of Machine Learning. Data were extracted from the IEEE Xplore Digital Library and the official web site of the International Conference on Machine Learning Applications (ICMLA). We include data of four different editions (from 2014 to 2017). Web scrapping techniques were used to mine the data contained in these web sites. The dataset covers 448 papers presented in the conference and every paper contains 6 attributes including information about the thematic session in which they were presented in the conference. The dataset is hosted in the Mendeley Dataset Repository., This work was partially supported by IDEIAGEOCA Research Group of the Universidad Politecnica Salesiana. This work also has been supported by the EU (FEDER) and the Spanish MINECO under grant TIN2015-69175-C4-1-R, and by Generalitat Valenciana PROMETE0112019/018.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Use of logical models for proving infeasibility in term rewriting

  • Lucas Alba, Salvador|||0000-0001-9923-2108
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
[EN] Given a (Conditional) Rewrite System R and terms s and t, we consider the following problem: is there a substitution a instantiating the variables in s and t such that the reachability test sigma(s) -> *(R) sigma(t) succeeds? If such a substitution does not exist, we say that the problem is infeasible; otherwise, we call it feasible. Similarly, we can consider reducibility, involving a single rewriting step. In term rewriting, a number of important problems involve such infeasibility tests (e.g., confluence and termination analysis). We show how to recast infeasibility tests into the problem of finding a model of a set of (first-order) sentences representing the operational semantics of R together with some additional sentences representing the considered property which is formulated as an infeasibility test. (C) 2018 Elsevier B.V. All rights reserved., Partially supported by the EU (FEDER) which is co-funding the project TIN2015-69175-C4-1-R, Spanish MINECO project TIN2015-69175-C4-1-R and Generalitat Valenciana (GV) project PROMETEOII/2015/013.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Estudio, informe, memoria (Report)

Static Correction of Maude Programs with Assertions

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Ballis, D.
In this paper, we present a novel transformation method for Maude programs featuring both automatic program diagnosis and correction. The input of our method is a reference specification A of the program behavior that is given in the form of assertions together with an overly general program R whose execution might violate the assertions. Our technique translates R into a refined program R' in which every computation is a computation in R that satisfies the assertions of A. Our correction technique is first formalized for topmost rewrite theories, and then we generalize it to larger rewrite theories that support nested structured configurations. Our technique copes with infinite space states and does not require the knowledge of any failing run. We report experiments that assess the effectiveness of assertion-driven correction., This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN2015-69175-C4-1-R, and by Generalitat Valenciana ref. PROMETEOII/2015/013
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

Surveying Safety-relevant AI Characteristics

  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • Avin, Shahar
  • Heigeartaigh, Sean O.
[EN] The current analysis in the AI safety literature usually combines a risk or safety issue (e.g., interruptibility) with a particular paradigm for an AI agent (e.g., reinforcement learning). However, there is currently no survey of safety-relevant characteristics of AI systems that may reveal neglected areas of research or suggest to developers what design choices they could make to avoid or minimise certain safety concerns. In this paper, we take a first step towards delivering such a survey, from two angles. The first features AI system characteristics that are already known to be relevant to safety concerns, including internal system characteristics, characteristics relating to the effect of the external environment on the system, and characteristics relating to the effect of the system on the target environment. The second presents a brief survey of a broad range of AI system characteristics that could prove relevant to safety research, including types of interaction, computation, integration, anticipation, supervision, modification, motivation and achievement. This survey enables further work in exploring system characteristics and design choices that affect safety concerns, FMP and JHO were supported by the EU (FEDER) and the Spanish MINECO under grant TIN 2015-69175-C4-1-R, by Generalitat Valenciana (GVA) under grant PROME-TEOII/2015/013 and by the U.S. Air Force Office of Scientific Research under award number FA9550-17-1-0287. FMP was also supported by INCIBE (Ayudas para la excelencia de los equipos de investigacion avanzada en ciberseguridad), the European Commission, JRC¿s Centre for Advanced Studies, HUMAINT project (Expert Contract CT-EX2018D335821-101), and UPV PAID-06-18 Ref. SP20180210. JHO was supported by a Salvador de Madariaga grant (PRX17/00467) from the Spanish MECD for a research stay at the Leverhulme Centre for the Future of Intelligence (CFI), Cambridge, and a BEST grant (BEST/2017/045) from GVA for another research stay also at the CFI. JHO and SOH were supported by the Future of Life Institute (FLI) grant RFP2-152. SOH was also supported by the Leverhulme Trust Research Centre Grant RC2015-067 awarded to the Leverhulme Centre for the Future of Intelligence, and a a grant from Templeton World Charity Foundation
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Dual Indicators to Analyse AI Benchmarks: Difficulty, Discrimination, Ability and Generality

  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • Hernández-Orallo, José|||0000-0001-9746-7632
[EN] With the purpose of better analyzing the result of artificial intelligence (AI) benchmarks, we present two indicators on the side of the AI problems, difficulty and discrimination, and two indicators on the side of the AI systems, ability and generality. The first three are adapted from psychometric models in item response theory (IRT), whereas generality is defined as a new metric that evaluates whether an agent is consistently good at easy problems and bad at difficult ones. We illustrate how these key indicators give us more insight on the results of two popular benchmarks in AI, the Arcade Learning Environment (Atari 2600 games) and the General Video Game AI competition, and we include some guidelines to estimate and interpret these indicators for other AI benchmarks and competitions., This work was supported by the U.S. Air Force Office of Scientific Research under Award FA9550-17-1-0287; in part by the EU (FEDER) and the Spanish MINECO under Grant TIN 2015-69175-C4-1-R; and in part by the Generalitat Valenciana PROMETEOII/2015/013. The work of F. Mart ' inez-Plumed was supported by INCIBE (Ayudas para la excelencia de los equipos de investigaci ' on avanzada en ciberseguridad), the European Commission, JRC's Centre for Advanced Studies, HUMAINT project (Expert Contract CT-EX2018D335821-101), and UPV PAID-06-18 Ref. SP20180210. The work of J. Hern ' andez-Orallo was supported in part by Salvador de Madariaga grant (PRX17/00467) from the Spanish MECD, in part by the BEST Grant (BEST/2017/045) from the GVA for research stays at the CFI, and in part by the FLI grant RFP2-152.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Item response theory in AI: Analysing machine learning classifiers at the instance level

  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Prudencio, Ricardo
  • Martínez-Usó, Adolfo
[EN] AI systems are usually evaluated on a range of problem instances and compared to other AI systems that use different strategies. These instances are rarely independent. Machine learning, and supervised learning in particular, is a very good example of this. Given a machine learning model, its behaviour for a single instance cannot be understood in isolation but rather in relation to the rest of the data distribution or dataset. In a dual way, the results of one machine learning model for an instance can be analysed in comparison to other models. While this analysis is relative to a population or distribution of models, it can give much more insight than an isolated analysis. Item response theory (IRT) combines this duality between items and respondents to extract latent variables of the items (such as discrimination or difficulty) and the respondents (such as ability). IRT can be adapted to the analysis of machine learning experiments (and by extension to any other artificial intelligence experiments). In this paper, we see that IRT suits classification tasks perfectly, where instances correspond to items and classifiers correspond to respondents. We perform a series of experiments with a range of datasets and classification methods to fully understand what the IRT parameters such as discrimination, difficulty and guessing mean for classification instances (and their relation to instance hardness measures) and how the estimated classifier ability can be used to compare classifier performance in a different way through classifier characteristic curves., This work has been partially supported by the EU (FEDER) and the Ministerio de Economia y Competitividad (MINECO) in Spain grant TIN2015-69175-C4-1-R, the Air Force Office of Scientific Research under award number FA9550-17-1-0287, and the REFRAME project, granted by the European Coordinated Research on Long-term Challenges in Information and Communication Sciences Technologies ERA-Net (CHIST-ERA) and funded by Ministerio de Economia y Competitividad (MINECO) in Spain (PCIN-2013-037), and by Generalitat Valenciana PROMETEOII/2015/013. Fernando Martinez-Plumed was also supported by INCIBE (INCIBEI-2015-27345) "Ayudas para la excelencia de los equipos de investigacion avanzada en ciberseguridad", the European Commission (Joint Research Centre) HUMAINT project (Expert Contract CT-EX2018D335821-101), and Universitat Politecnica de Valencia (PAID-06-18 Ref. SP20180210). Ricardo Prudencio was financially supported by CNPq (Brazilian Agency). Jose Hernandez-Orallo was supported by a Salvador de Madariaga grant (PRX17/00467) from the Spanish MECD for a research stay at the Leverhulme Centre for the Future of Intelligence (CFI), Cambridge, a BEST grant (BEST/2017/045) from the Valencia GVA for another research stay also at the CFI, and an FLI grant RFP2.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A program analysis framework for tccp based on abstract interpretation

  • Comini, Marco
  • Gallardo, Maria-del-Mar
  • Titolo, Laura
  • Villanueva, Alicia|||0000-0003-1090-5009
[EN] The timed concurrent constraint language (tccp) is a timed extension of the concurrent constraint paradigm. tccp was defined to model reactive systems, where infinite behaviors arise naturally. In previous works, a semantic framework and abstract diagnosis method for the language have been defined. On the basis of that semantic framework, this paper proposes an abstract semantics that, together with a widening operator, is suitable for the definition of different analyses for tccp programs. The abstract semantics is correct and can be represented as a finite graph where each node represents a hypothetical (abstract) computational step of the program. The widening operator allows us to guarantee the convergence of the abstract fixpoint computation., This author has been supported by the Andalusian Excellence Project P11-TIC-7659. This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grants TIN 2015-69175-C4-1-R and TIN 2013-45732-C4-1-P and by Generalitat Valenciana PROMETEOII/2015/013
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Tesis doctoral (DoctoralThesis)

Modeling and Analysis of Advanced Cryptographic Primitives and Security Protocols in Maude-NPA

  • Aparicio Sánchez, Damián
[ES] La herramienta criptográfica Maude-NPA es un verificador de modelos especializado para protocolos de seguridad criptográficos que tienen en cuenta las propiedades algebraicas de un sistema criptográfico. En la literatura, las propiedades criptográficas adicionales han descubierto debilidades de los protocolos de seguridad y, en otros casos, son parte de los supuestos de seguridad del protocolo para funcionar correctamente. Maude-NPA tiene una base teórica en la rewriting logic, la unificación ecuacional y el narrowing para realizar una búsqueda hacia atrás desde un patrón de estado inseguro para determinar si es alcanzable o no. Maude-NPA se puede utilizar para razonar sobre una amplia gama de propiedades criptográficas, incluida la cancelación del cifrado y descifrado, la exponenciación de Diffie-Hellman, el exclusive-or y algunas aproximaciones del cifrado homomórfico. En esta tesis consideramos nuevas propiedades criptográficas, ya sea como parte de protocolos de seguridad o para descubrir nuevos ataques. También hemos modelado diferentes familias de protocolos de seguridad, incluidos los Distance Bounding Protocols or Multi-party key agreement protocolos. Y hemos desarrollado nuevas técnicas de modelado para reducir el coste del análisis en protocolos con tiempo y espacio. Esta tesis contribuye de varias maneras al área de análisis de protocolos criptográficos y muchas de las contribuciones de esta tesis pueden ser útiles para otras herramientas de análisis criptográfico., [CA] L'eina criptografica Maude-NPA es un verificador de models especialitzats per a protocols de seguretat criptogràfics que tenen en compte les propietats algebraiques d'un sistema criptogràfic. A la literatura, les propietats criptogràfiques addicionals han descobert debilitats dels protocols de seguretat i, en altres casos, formen part dels supòsits de seguretat del protocol per funcionar correctament. Maude-NPA te' una base teòrica a la rewriting lògic, la unificació' equacional i narrowing per realitzar una cerca cap enrere des d'un patró' d'estat insegur per determinar si es accessible o no. Maude-NPA es pot utilitzar per raonar sobre una amplia gamma de propietats criptogràfiques, inclosa la cancel·lació' del xifratge i desxifrat, l'exponenciacio' de Diffie-Hellman, el exclusive-or i algunes aproximacions del xifratge homomòrfic. En aquesta tesi, considerem noves propietats criptogràfiques, ja sigui com a part de protocols de seguretat o per descobrir nous atacs. Tambe' hem modelat diferents famílies de protocols de seguretat, inclosos els Distance Bounding Protocols o Multi-party key agreement protocols. I hem desenvolupat noves tècniques de modelització' de protocols per reduir el cost de l'analisi en protocols amb temps i espai. Aquesta tesi contribueix de diverses maneres a l’àrea de l’anàlisi de protocols criptogràfics i moltes de les contribucions d’aquesta tesi poden ser útils per a altres eines d’anàlisi criptogràfic., [EN] The Maude-NPA crypto tool is a specialized model checker for cryptographic security protocols that take into account the algebraic properties of the cryptosystem. In the literature, additional crypto properties have uncovered weaknesses of security protocols and, in other cases, they are part of the protocol security assumptions in order to function properly. Maude-NPA has a theoretical basis on rewriting logic, equational unification, and narrowing to perform a backwards search from an insecure state pattern to determine whether or not it is reachable. Maude-NPA can be used to reason about a wide range of cryptographic properties, including cancellation of encryption and decryption, Diffie-Hellman exponentiation, exclusive-or, and some approximations of homomorphic encryption. In this thesis, we consider new cryptographic properties, either as part of security protocols or to discover new attacks. We have also modeled different families of security protocols, including Distance Bounding Protocols or Multi-party key agreement protocols. And we have developed new protocol modeling techniques to reduce the time and space analysis effort. This thesis contributes in several ways to the area of cryptographic protocol analysis and many of the contributions of this thesis can be useful for other crypto analysis tools., This thesis would not have been possible without the funding of a set of research projects. The main contributions and derivative works of this thesis have been made in the context of the following projects: - Ministry of Economy and Business of Spain : Project LoBaSS Effective Solutions Based on Logic, Scientific Research under award number TIN2015-69175-C4-1-R, this project was focused on using powerful logic-based technologies to analyze safety-critical systems. - Air Force Office of Scientific Research of United States of America : Project Advanced symbolic methods for the cryptographic protocol analyzer Maude-NPA Scientific Research under award number FA9550-17-1-0286 - State Investigation Agency of Spain : Project FREETech: Formal Reasoning for Enabling and Emerging Technologies Scientific I+D-i Research under award number RTI2018-094403-B-C32
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Automatic Synthesis of Logical Models for Order-Sorted First-Order Theories

  • Lucas Alba, Salvador|||0000-0001-9923-2108
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
[EN] In program analysis, the synthesis of models of logical theories representing the program semantics is often useful to prove program properties. We use order-sorted first- order logic as an appropriate framework to describe the semantics and properties of programs as given theories. Then we investigate the automatic synthesis of models for such theories. We use convex polytopic domains as a flexible approach to associate different domains to different sorts. We introduce a framework for the piecewise definition of functions and predicates. We develop its use with linear expressions (in a wide sense, including linear transformations represented as matrices) and inequalities to specify functions and predicates. In this way, algorithms and tools from linear algebra and arithmetic constraint solving (e.g., SMT) can be used as a backend for an efficient implementation., Partially supported by the EU (FEDER), projects TIN2015-69175-C4-1-R, and GV PROMETEOII/2015/ 013. R. Gutiérrez also supported by Juan de la Cierva Fellowship JCI-2012-13528.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Tesis doctoral (DoctoralThesis)

Towards Data Wrangling Automation through Dynamically-Selected Background Knowledge

  • Contreras Ochando, Lidia
[ES] El proceso de ciencia de datos es esencial para extraer valor de los datos. Sin embargo, la parte más tediosa del proceso, la preparación de los datos, implica una serie de formateos, limpieza e identificación de problemas que principalmente son tareas manuales. La preparación de datos todavía se resiste a la automatización en parte porque el problema depende en gran medida de la información del dominio, que se convierte en un cuello de botella para los sistemas de última generación a medida que aumenta la diversidad de dominios, formatos y estructuras de los datos. En esta tesis nos enfocamos en generar algoritmos que aprovechen el conocimiento del dominio para la automatización de partes del proceso de preparación de datos. Mostramos la forma en que las técnicas generales de inducción de programas, en lugar de los lenguajes específicos del dominio, se pueden aplicar de manera flexible a problemas donde el conocimiento es importante, mediante el uso dinámico de conocimiento específico del dominio. De manera más general, sostenemos que una combinación de enfoques de aprendizaje dinámicos y basados en conocimiento puede conducir a buenas soluciones. Proponemos varias estrategias para seleccionar o construir automáticamente el conocimiento previo apropiado en varios escenarios de preparación de datos. La idea principal se basa en elegir las mejores primitivas especializadas de acuerdo con el contexto del problema particular a resolver. Abordamos dos escenarios. En el primero, manejamos datos personales (nombres, fechas, teléfonos, etc.) que se presentan en formatos de cadena de texto muy diferentes y deben ser transformados a un formato unificado. El problema es cómo construir una transformación compositiva a partir de un gran conjunto de primitivas en el dominio (por ejemplo, manejar meses, años, días de la semana, etc.). Desarrollamos un sistema (BK-ADAPT) que guía la búsqueda a través del conocimiento previo extrayendo varias meta-características de los ejemplos que caracterizan el dominio de la columna. En el segundo escenario, nos enfrentamos a la transformación de matrices de datos en lenguajes de programación genéricos como R, utilizando como ejemplos una matriz de entrada y algunas celdas de la matriz de salida. También desarrollamos un sistema guiado por una búsqueda basada en árboles (AUTOMAT[R]IX) que usa varias restricciones, probabilidades previas para las primitivas y sugerencias textuales, para aprender eficientemente las transformaciones. Con estos sistemas, mostramos que la combinación de programación inductiva, con la selección dinámica de las primitivas apropiadas a partir del conocimiento previo, es capaz de mejorar los resultados de otras herramientas actuales específicas para la preparación de datos., [CA] El procés de ciència de dades és essencial per extraure valor de les dades. No obstant això, la part més tediosa del procés, la preparació de les dades, implica una sèrie de transformacions, neteja i identificació de problemes que principalment són tasques manuals. La preparació de dades encara es resisteix a l'automatització en part perquè el problema depén en gran manera de la informació del domini, que es converteix en un coll de botella per als sistemes d'última generació a mesura que augmenta la diversitat de dominis, formats i estructures de les dades. En aquesta tesi ens enfoquem a generar algorismes que aprofiten el coneixement del domini per a l'automatització de parts del procés de preparació de dades. Mostrem la forma en què les tècniques generals d'inducció de programes, en lloc dels llenguatges específics del domini, es poden aplicar de manera flexible a problemes on el coneixement és important, mitjançant l'ús dinàmic de coneixement específic del domini. De manera més general, sostenim que una combinació d'enfocaments d'aprenentatge dinàmics i basats en coneixement pot conduir a les bones solucions. Proposem diverses estratègies per seleccionar o construir automàticament el coneixement previ apropiat en diversos escenaris de preparació de dades. La idea principal es basa a triar les millors primitives especialitzades d'acord amb el context del problema particular a resoldre. Abordem dos escenaris. En el primer, manegem dades personals (noms, dates, telèfons, etc.) que es presenten en formats de cadena de text molt diferents i han de ser transformats a un format unificat. El problema és com construir una transformació compositiva a partir d'un gran conjunt de primitives en el domini (per exemple, manejar mesos, anys, dies de la setmana, etc.). Desenvolupem un sistema (BK-ADAPT) que guia la cerca a través del coneixement previ extraient diverses meta-característiques dels exemples que caracteritzen el domini de la columna. En el segon escenari, ens enfrontem a la transformació de matrius de dades en llenguatges de programació genèrics com a R, utilitzant com a exemples una matriu d'entrada i algunes dades de la matriu d'eixida. També desenvolupem un sistema guiat per una cerca basada en arbres (AUTOMAT[R]IX) que usa diverses restriccions, probabilitats prèvies per a les primitives i suggeriments textuals, per aprendre eficientment les transformacions. Amb aquests sistemes, mostrem que la combinació de programació inductiva amb la selecció dinàmica de les primitives apropiades a partir del coneixement previ, és capaç de millorar els resultats d'altres enfocaments de preparació de dades d'última generació i més específics., [EN] Data science is essential for the extraction of value from data. However, the most tedious part of the process, data wrangling, implies a range of mostly manual formatting, identification and cleansing manipulations. Data wrangling still resists automation partly because the problem strongly depends on domain information, which becomes a bottleneck for state-of-the-art systems as the diversity of domains, formats and structures of the data increases. In this thesis we focus on generating algorithms that take advantage of the domain knowledge for the automation of parts of the data wrangling process. We illustrate the way in which general program induction techniques, instead of domain-specific languages, can be applied flexibly to problems where knowledge is important, through the dynamic use of domain-specific knowledge. More generally, we argue that a combination of knowledge-based and dynamic learning approaches leads to successful solutions. We propose several strategies to automatically select or construct the appropriate background knowledge for several data wrangling scenarios. The key idea is based on choosing the best specialised background primitives according to the context of the particular problem to solve. We address two scenarios. In the first one, we handle personal data (names, dates, telephone numbers, etc.) that are presented in very different string formats and have to be transformed into a unified format. The problem is how to build a compositional transformation from a large set of primitives in the domain (e.g., handling months, years, days of the week, etc.). We develop a system (BK-ADAPT) that guides the search through the background knowledge by extracting several meta-features from the examples characterising the column domain. In the second scenario, we face the transformation of data matrices in generic programming languages such as R, using an input matrix and some cells of the output matrix as examples. We also develop a system guided by a tree-based search (AUTOMAT[R]IX) that uses several constraints, prior primitive probabilities and textual hints to efficiently learn the transformations. With these systems, we show that the combination of inductive programming with the dynamic selection of the appropriate primitives from the background knowledge is able to improve the results of other state-of-the-art and more specific data wrangling approaches., This research was supported by the Spanish MECD Grant FPU15/03219;and partially by the Spanish MINECO TIN2015-69175-C4-1-R (Lobass) and RTI2018-094403-B-C32-AR (FreeTech) in Spain; and by the ERC Advanced Grant Synthesising Inductive Data Models (Synth) in Belgium.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Estudio, informe, memoria (Report)

Abstract Contract Synthesis and Verification in the Symbolic K Framework

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Villanueva, Alicia|||0000-0003-1090-5009
  • Pardo Pont, Daniel
[EN] In this article, we propose a symbolic technique that can be used for automatically inferring software contracts from programs that are written in a non-trivial fragment of C, called KernelC, that supports pointer-based structures and heap manipulation. Starting from the semantic definition of KernelC in the K semantic framework, we enrich the symbolic execution facilities recently provided by K with novel capabilities for contract synthesis that are based on abstract subsumption. Roughly speaking, we define an abstract symbolic technique that axiomatically explains the execution of any (modifier) C function by using other (observer) routines in the same program. We implemented our technique in the automated tool KindSpec 2.1, which generates logical axioms that express pre- and postcondition assertions which define the precise input/output behavior of the C routines. Thanks to the integrated support for symbolic execution and deductive verification provided by K, some synthesized axioms that cannot be guaranteed to be correct by construction due to abstraction can finally be verified in our framework with little effort., This work has been partially supported by the EU (FEDER) and Spanish MINECO under grant TIN2015-69175-C4-1-R, and and TIN2013-45732-C4-1-P, and by Generalitat Valenciana PROMETEOII/2015/013. Daniel Pardo was supported by FPU-ME grant FPU14/01830.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Inspecting Maude Variants with GLINTS

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Escobar Román, Santiago|||0000-0002-3550-4781
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Cuenca-Ortega, Angel
[EN] This paper introduces GLINTS, a graphical tool for exploring variant narrowing computations in Maude. The most recent version of Maude, version 2.7.1, provides quite sophisticated unification features, including order-sorted equational unification for convergent theories modulo axioms such as associativity, commutativity, and identity. This novel equational unification relies on built-in generation of the set of variants of a term t, i.e., the canonical form of t sigma for a computed substitution sigma. Variant generation relies on a novel narrowing strategy called folding variant narrowing that opens up new applications in formal reasoning, theorem proving, testing, protocol analysis, and model checking, especially when the theory satisfies the finite variant property, i.e., there is a finite number of most general variants for every term in the theory. However, variant narrowing computations can be extremely involved and are simply presented in text format by Maude, often being too heavy to be debugged or even understood. The GLINTS system provides support for (i) determining whether a given theory satisfies the finite variant property, (ii) thoroughly exploring variant narrowing computations, (iii) automatic checking of node embedding and closedness modulo axioms, and (iv) querying and inspecting selected parts of the variant trees., This work has been partially supported by EU (FEDER) and Spanish MINECO grant TIN 2015-69175-C4-1-R and by Generalitat Valenciana PROMETEO-II/2015/013. Angel Cuenca-Ortega is supported by SENESCYT, Ecuador (scholarship program 2013), and Julia Sapina by FPI-UPV grant SP2013-0083. Santiago Escobar is supported by the Air Force Office of Scientific Research under award number FA9550-17-1-0286.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Automatic Inference of Specifications in the K Framework

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Villanueva, Alicia|||0000-0003-1090-5009
  • Pardo Pont, Daniel
[EN] Despite its many unquestionable benefits, formal specifications are not widely used in industrial software development. In order to reduce the time and effort required to write formal specifications, in this paper we propose a technique for automatically discovering specifications from real code. The proposed methodology relies on the symbolic execution capabilities recently provided by the K framework that we exploit to automatically infer formal specifications from programs that are written in a non–trivial fragment of C, called KERNELC. Roughly speaking, our symbolic analysis of KERNELC programs explains the execution of a (modifier) function by using other (observer) routines in the program. We implemented our technique in the automated tool KINDSPEC 2.0, which generates axioms that describe the precise input/output behavior of C routines that handle pointerbased structures (i.e., result values and state change). We describe the implementation of our system and discuss the differences w.r.t. our previous work on inferring specifications from C code., This work has been partially supported by the EU (FEDER) and Spanish MINECO under grants TIN2015-69175-C4-1-R and TIN2013-45732-C4-1-P, and by Generalitat Valenciana ref. PROMETEOII/2015/013.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The 2D Dependency Pair Framework for conditional rewrite systems. Part I: Definition and basic processors

  • Lucas Alba, Salvador|||0000-0001-9923-2108
  • Gutiérrez Gil, Raúl|||0000-0002-3984-2868
  • Meseguer, José
[EN] Different termination properties of conditional term rewriting systems have been recently described emphasizing the bidimensional nature of the termination behavior of conditional rewriting. The absence of infinite sequences of rewriting steps (termination in the usual sense), provides the horizontal dimension. The absence of infinitely many attempts to launch the subsidiary processes that are required to check the rule's condition and perform a single rewriting step has been called V-termination and provides the vertical dimension. We have characterized these properties by means of appropriate notions of dependency pairs and dependency chains. In this paper we introduce a 2D Dependency Pair Framework for automatically proving and disproving all these termination properties. Our implementation of the framework as part of the termination tool MU-TERM and the benchmarks obtained so far suggest that the 2D Dependency Pair Framework is currently the most powerful technique for proving operational termination of conditional term rewriting systems. (C) 2018 Elsevier Inc. All rights reserved., Partially supported by the EU (FEDER), Spanish MINECO project TIN2015-69175-C4-1-R, GV project PROMETEOII/2015/013, and NSF grant CNS 13-19109. Raul Gutierrez is also supported by Juan de la Cierva Fellowship JCI-2012-13528.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Dependency pairs for proving termination properties of conditional term rewriting systems

  • Lucas Alba, Salvador|||0000-0001-9923-2108
  • Meseguer, José
[EN] The notion of operational termination provides a logic-based definition of termination of computational systems as the absence of infinite inferences in the computational logic describing the operational semantics of the system. For Conditional Term Rewriting Systems we show that operational termination is characterized as the conjunction of two termination properties. One of them is traditionally called termination and corresponds to the absence of infinite sequences of rewriting steps (a horizontal dimension). The other property, that we call V-termination, concerns the absence of infinitely many attempts to launch the subsidiary processes that are required to perform a single rewriting step (a vertical dimension). We introduce appropriate notions of dependency pairs to characterize termination, V-termination, and operational termination of Conditional Term Rewriting Systems. This can be used to obtain a powerful and more expressive framework for proving termination properties of Conditional Term Rewriting Systems., Partially supported by the EU (FEDER), Spanish MINECO projects TIN 2013-45732-C4-1-P and TIN2015-69175-C4-1-R, GV project PROMETEOII/2015/013, and NSF grant CNS 13-19109. Salvador Lucas' research was partly developed during a sabbatical year at UIUC
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Incremental and developmental perspectives for general-purpose learning systems

  • Martínez-Plumed, Fernando|||0000-0003-2902-6477
[EN] The stupefying success of Articial Intelligence (AI) for specic problems, from recommender systems to self-driving cars, has not yet been matched with a similar progress in general AI systems, coping with a variety of (dierent) problems. This dissertation deals with the long-standing problem of creating more general AI systems, through the analysis of their development and the evaluation of their cognitive abilities. It presents a declarative general-purpose learning system and a developmental and lifelong approach for knowledge acquisition, consolidation and forgetting. It also analyses the use of the use of more ability-oriented evaluation techniques for AI evaluation and provides further insight for the understanding of the concepts of development and incremental learning in AI systems., I would like to thank my Ph.D. advisors, José Hernández-Orallo, María José Ramírez-Quintana and César Ferri, for all his help and guidance. This work has been partially supported by the EU (FEDER) and Spanish MINECO grant TIN2015-69175-C4-1-R, and the REFRAME project, granted by the European Coordinated Research on Long-term Challenges in Information and Communication Sciences Technologies ERA-Net (CHIST-ERA), and funded by MINECO in Spain (PCIN-2013-037) and by Generalitat Valenciana PROMETEOII/2015/013.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Probabilistic class hierarchies for multiclass classification

  • Silva-Palacios, Daniel Andres
  • Ferri Ramírez, César|||0000-0002-8975-1120
  • Ramírez Quintana, María José|||0000-0002-0559-3568
[EN] The improvement in the performance of classifiers has been the focus of attention of many researchers over the last few decades. Obtaining accurate predictions becomes more complicated as the number of classes increases. Most families of classification techniques generate models that define decision boundaries trying to separate the classes as well as possible. As an alternative, in this paper, we propose to hierarchically decompose the original multiclass problem by reducing the number of classes involved in each local subproblem. This is done by deriving a similarity matrix from the misclassification errors given by a first classifier that is learned for this, and then, using the similarity matrix to build a tree-like hierarchy of specialized classifiers. Then, we present two approaches to solve the multiclass problem: the first one traverses the tree of classifiers in a top-down manner similar to the way some hierarchical classification methods do for dealing with hierarchical domains; the second one is inspired in the way probabilistic decision trees compute class membership probabilities. To improve the efficiency of our methods, we propose a criterion to reduce the size of the hierarchy. We experimentally evaluate all of the proposals on a collection of multiclass datasets showing that, in general, the generated classifier hierarchies outperform the original (flat) multiclass classification., This work was partially supported by the the EU (FEDER) and the Spanish MINECO under grant TIN 2015-69175-C4-1-R, and by Generalitat Valenciana PROMETEOII2015/013. This work has been supported by the Secretary of Higher Education, Science and Technology (SENESCYT: Secretaria Nacional de Educacion Superior, Ciencia y Tecnologia), of the Republic of Ecuador.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Setting decision thresholds when operating conditions are uncertain

  • Ferri Ramírez, César|||0000-0002-8975-1120
  • Hernández-Orallo, José|||0000-0001-9746-7632
  • Flach, Peter
[EN] The quality of the decisions made by a machine learning model depends on the data and the operating conditions during deployment. Often, operating conditions such as class distribution and misclassification costs have changed during the time since the model was trained and evaluated. When deploying a binary classifier that outputs scores, once we know the new class distribution and the new cost ratio between false positives and false negatives, there are several methods in the literature to help us choose an appropriate threshold for the classifier's scores. However, on many occasions, the information that we have about this operating condition is uncertain. Previous work has considered ranges or distributions of operating conditions during deployment, with expected costs being calculated for ranges or intervals, but still the decision for each point is made as if the operating condition were certain. The implications of this assumption have received limited attention: a threshold choice that is best suited without uncertainty may be suboptimal under uncertainty. In this paper we analyse the effect of operating condition uncertainty on the expected loss for different threshold choice methods, both theoretically and experimentally. We model uncertainty as a second conditional distribution over the actual operation condition and study it theoretically in such a way that minimum and maximum uncertainty are both seen as special cases of this general formulation. This is complemented by a thorough experimental analysis investigating how different learning algorithms behave for a range of datasets according to the threshold choice method and the uncertainty level., We thank the anonymous reviewers for their comments, which have helped to improve this paper significantly. This work has been partially supported by the EU (FEDER) and the Spanish MINECO under Grant TIN 2015-69175-C4-1-R and by Generalitat Valenciana under Grant PROMETEOII/2015/013. Jose Hernandez-Orallo was supported by a Salvador de Madariaga Grant (PRX17/00467) from the Spanish MECD for a research stay at the Leverhulme Centre for the Future of Intelligence (CFI), Cambridge, a BEST Grant (BEST/2017/045) from Generalitat Valenciana for another research stay also at the CFI and an FLI Grant RFP2-152.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Using Well-Founded Relations for Proving Operational Termination

  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] In this paper, we study operational termination, a proof theoretical notion for capturing the termination behavior of computational systems. We prove that operational termination can be characterized at different levels by means of well- founded relations on specific formulas which can be obtained from the considered system. We show how to obtain such well-founded relations from logical models which can be automatically generated using existing tools., Partially supported by the EU (FEDER), Projects TIN2015-69175-C4-1-R, and GV PROMETEOII/2015/013.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Assertion-based Analysis via Slicing with ABETS

  • Alpuente Frasnedo, María|||0000-0002-9268-1178
  • Sapiña-Sanchis, Julia|||0000-0003-2994-6986
  • Frechina, F.
  • Ballis, Demis
[EN] We present ABETS, an assertion-based, dynamic analyzer that helps diagnose errors in Maude programs. ABETS uses slicing to automatically create reduced versions of both a run's execution trace and executed program, reduced versions in which any information that is not relevant to the bug currently being diagnosed is removed. In addition, ABETS employs runtime assertion checking to automate the identification of bugs so that whenever an assertion is violated, the system automatically infers accurate slicing criteria from the failure. We summarize the main services provided by ABETS, which also include a novel assertionbased facility for program repair that generates suitable program fixes when a state invariant is violated. Finally, we provide an experimental evaluation that shows the performance and effectiveness of the system., This work has been partially supported by the EU (FEDER) and Spanish MINECO grant TIN2015-69175-C4-1-R, and by Generalitat Valenciana PROMETEOII/2015/013. J. Sapina was supported by FPI-UPV grant SP2013-0083.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Use of Logical Models for Proving Operational Termination in General Logics

  • Lucas Alba, Salvador|||0000-0001-9923-2108
[EN] A declarative programming language is based on some logic L and its operational semantics is given by a proof calculus which is often presented in a natural deduction style by means of inference rules. Declarative programs are theories S of L and executing a program is proving goals ϕ in the inference system I(S) associated to S as a particulariza-tion of the inference system of the logic. The usual soundness assumption for L implies that every model A of S also satisfies ϕ. In this setting, the operational termination of a declarative program is quite naturally defined as the absence of infinite proof trees in the inference system I(S). Proving operational termination of declarative programs often involves two main ingredients: (i) the generation of logical models A to abstract the program execution (i.e., the provability of specific goals in I(S)), and (ii) the use of well-founded relations to guarantee the absence of infinite branches in proof trees and hence of infinite proof trees, possibly taking into account the information about provability encoded by A. In this paper we show how to deal with (i) and (ii) in a uniform way. The main point is the synthesis of logical models where well-foundedness is a side requirement for some specific predicate symbols., Partially supported by the EU (FEDER), Spanish MINECO TIN 2013-45732-C4-1-P and TIN2015-69175-C4-1-R, and GV PROMETEOII/2015/013.