OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Behavior of analogical inference w.r.t. Boolean functions

Couceiro, Miguel and Hug, Nicolas and Prade, Henri and Richard, Gilles Behavior of analogical inference w.r.t. Boolean functions. (2018) In: 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), 13 July 2018 - 19 July 2018 (Stockholm, Sweden).

[img] (Document in English)

PDF (Author's version) - Depositor and staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
337kB

Official URL: https://doi.org/10.24963/ijcai.2018/284

Abstract

It has been observed that a particular form of analogical inference, based on analogical proportions, yields competitive results in classification tasks. Using the algebraic normal form of Boolean functions, it has been shown that analogical prediction is always exact iff the labeling function is affine. We point out that affine functions are also meaningful when using another view of analogy. We address the accuracy of analogical inference for arbitrary Boolean functions and show that if a function is epsilon-close to an affine function, then the probability of making a wrong prediction is upper bounded by 4 epsilon. This result is confirmed by an empirical study showing that the upper bound is tight. It highlights the specificity of analogical inference, also characterized in terms of the Hamming distance.

Item Type:Conference or Workshop Item (Paper)
Additional Information:https://www.ijcai.org/proceedings/2018/284
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
French research institutions > Institut National de la Recherche en Informatique et en Automatique - INRIA (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > University of Technology, Sydney - UTS (AUSTRALIA)
Other partners > Université de Lorraine (FRANCE)
Laboratory name:
Funders:
ANR : Agence nationale de la recherche (France) - CIMI : Centre International de Mathématiques et d’Informatique (France)
Statistics:download
Deposited On:22 Nov 2019 10:19

Repository Staff Only: item control page