Abstract
Analogical proportions are statements of the form “\(\mathbf {a}\) is to \(\mathbf {b}\) as \(\mathbf {c}\) is to \(\mathbf {d}\)”, where \(\mathbf {a}\), \(\mathbf {b}\), \(\mathbf {c}\), \(\mathbf {d}\) are tuples of attribute values describing items. The mechanism of analogical inference, empirically proved to be efficient in classification and reasoning tasks, started to be better understood when the characterization of the class of classification functions with which the analogical inference always agrees was established for Boolean attributes. The purpose of this paper is to study the case of finite attribute domains that are not necessarily two-valued, i.e., when attributes are nominal. In particular, we describe the more stringent class of “hard” analogy preserving (HAP) functions \(f :X_1\,\times \,\dots \,\times \,X_m \rightarrow X\) over finite domains \(X_1, \dots , X_m, X\) for binary classification purposes. This description is obtained in two steps. First we observe that such AP functions are almost affine, that is, their restriction to any \(S_1 \times \dots \times S_m\), where \(S_i \subseteq X_i\) and \(|{S_i}| \le 2\) (\(1 \le i \le m\)), can be turned into an affine function by renaming variable and function values. We then use this result together with some universal algebraic tools to show that they are essentially unary or quasi-linear, which provides a general representation of HAP functions. As a by-product, in the case when \(X_1 = \dots = X_m = X\), it follows that this class of HAP functions constitutes a clone on X, thus generalizing several results by some of the authors in the Boolean case .
The authors acknowledge a partial support of ANR-11-LABX-0040-CIMI (Cent. Int. de Math. et d’Informat.) within program ANR-11-IDEX-0002-02, project ISIPA, and a partial support of Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) through project UID/MAT/00297/2019 (Centro de Matemática e Aplicações) and project PTDC/MAT-PUR/31174/2017.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
An argument \(x_i\) is said to be inessential in \(f :\mathbf {X} \rightarrow X\) if for all \((a_1, \dots , a_m) \in \mathbf {X}\), \(a'_i \in X_i\), we have \(f(a_1, \dots , a_m) = f(a_1, \dots , a_{i-1}, a'_i, a_{i+1}, \dots , a_m)\). Otherwise, \(x_i\) is said to be essential in f. The number of essential arguments of f is called the essential arity of f.
- 2.
Recall that the kernel of f is \(\mathop {\mathrm {ker}} f := \{(\mathbf {a},\mathbf {b}) \in \{0,1\}^m \times \{0,1\}^m \mid f(\mathbf {a}) = f(\mathbf {b})\}\).
References
Barbot, N., Miclet, L., Prade, H., Richard, G.: A new perspective on analogical proportions. In: Kern-Isberner, G., Ognjanović, Z. (eds.) ECSQARU 2019. LNCS (LNAI), vol. 11726, pp. 163–174. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-29765-7_14
Bounhas, M., Prade, H., Richard, G.: Analogy-based classifiers for nominal or numerical data. Int. J. Approx. Reason. 91, 36–55 (2017)
Burle, G.A.: Classes of \(k\)-valued logic which contain all functions of a single variable. Diskret. Analiz 10, 3–7 (1967). (Russian)
Couceiro, M., Hug, N., Prade, H., Richard, G.: Analogy-preserving functions: a way to extend Boolean samples. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, August 19–25, pp. 1575–1581 (2017)
Couceiro, M., Hug, N., Prade, H., Richard, G.: Behavior of analogical inference w.r.t. Boolean functions. In: Lang, J. (ed.) Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018, Stockholm, July 13–19, pp. 2057–2063. ijcai.org (2018)
Crama, Y., Hammer, P.: Boolean Functions - Theory, Algorithms, and Applications. Encyclopedia of Mathematics and its Applications, vol. 142. Cambridge University Press (2011)
Hesse, M.: On defining analogy. Proc. Aristotelian Soc. 60, 79–100 (1959)
Klein, S.: Analogy and mysticism and the structure of culture (and Comments and Reply). Curr. Anthropol. 24(2), 151–180 (1983)
Langlais, P., Patry, A.: Translating unknown words by analogical learning. In: Joint Conference on Empirical Methods in Natural Language Processing (EMNLP) and Conference on Computational Natural Language Learning (CONLL), Prague, pp. 877–886 (2007)
Lepage, Y.: Analogy and formal languages. In: Proceedings of the FG/MOL, pp. 373–378 (2001)
Miclet, L., Bayoudh, S., Delhay, A.: Analogical dissimilarity: definition, algorithms and two experiments in machine learning. JAIR 32, 793–824 (2008)
Miclet, L., Prade, H.: Handling analogical proportions in classical logic and fuzzy logics settings. In: Sossai, C., Chemello, G. (eds.) ECSQARU 2009. LNCS (LNAI), vol. 5590, pp. 638–650. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02906-6_55
Prade, H., Richard, G.: Analogical proportions: from equality to inequality. Int. J. Approx. Reason. 101, 234–254 (2018)
Salomaa, A.: On essential variables of functions, especially in the algebra of logic. Ann. Acad. Sci. Fenn. Ser. A I(339), 1–11 (1963)
Stone, M.H.: The theory of representation for Boolean algebras. Trans. Am. Math. Soc. 40(1), 37–111 (1936)
Stroppa, N., Yvon, F.: Du quatrième de proportion comme principe inductif : une proposition et son application à l’apprentissage de la morphologie. Trait. Autom. Lang. 47(2), 1–27 (2006)
Zhegalkin, I.I.: On the technique of calculating propositions in symbolic logic. Mat. Sb. 43, 9–28 (1927)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Couceiro, M., Lehtonen, E., Miclet, L., Prade, H., Richard, G. (2020). When Nominal Analogical Proportions Do Not Fail. In: Davis, J., Tabia, K. (eds) Scalable Uncertainty Management. SUM 2020. Lecture Notes in Computer Science(), vol 12322. Springer, Cham. https://doi.org/10.1007/978-3-030-58449-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-58449-8_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58448-1
Online ISBN: 978-3-030-58449-8
eBook Packages: Computer ScienceComputer Science (R0)