Inference of Abstraction for Grounded Predicate Logic

Twelfth Annual Conference on Advances in Cognitive Systems Poster Collection (2025) 1-20 Inference of Abstraction for Grounded Predicate Logic Hiroyuki Kido [email protected] Cardiff University, Park Place, CF10 3AT, Cardiff, UK Abstract An important open question in AI is what simple and natural principle enables a machine to ground logical reasoning in data for meaningful abstraction. This paper explores a conceptually new approach to combining probabilistic reasoning and predicative symbolic reasoning over data. We return to the era of reasoning with a full joint distribution before the advent of Bayesian networks. We then discuss that a full joint distribution over models of exponential size in propositional logic and of infinite size in predicate logic should be simply derived from a full joint distribution over data of linear size. We show that the same process is not only enough to generalise the logical consequence relation of predicate logic but also to provide a new perspective to rethink well-known limitations such as the undecidability of predicate logic, the symbol grounding problem and the principle of explosion. The reproducibility of this theoretical work is fully demonstrated by the included proofs. 1. Introduction The current artificial intelligence (AI) systems such as large language models (LLMs) (OpenAI, 2025; DeepSeek-AI, 2025) demonstrate a surprising linguistic ability in both what they know and how they articulate it. However, the common view is that they are still not as capable as ordinary people in several areas such as logical reasoning and abstract reasoning. For logical reasoning, it is unclear how the statistical patterns an AI algorithm extracts from finite training data can capture the infinite set of rules of valid inference studied in formal logic. Moreover, it is unlikely that statistical AI modelling how people tend to think can replace formal logic modelling how people ought to think. For abstract reasoning, it is still unclear how a machine should explore and discover abstract concepts and principles from the real world in its own way. Consider the following problems requiring both abstract reasoning and logical reasoning skills. Example 1. Carol remembers the following three scenes. •Alice and Bob did not blame each other. •One day Alice blamed Bob, and she blamed herself afterwards. •Alice and Bob blamed each other on another day. One day Carol wanted to blame Bob. She hesitated because she learnt that someone will blame those who blame anyone, which can be expressed in a predicate language as follows. ∀x(∃y(Blames(x, y)) → ∃z(Blames(z, x))) © 2025 Cognitive Systems Foundation. All rights reserved. Twelfth Annual Advances in Cognitive Systems Poster Collection (2025) 213-232 This work is licensed under a Creative Commons Attribution International 4.0 License. H. KIDO Example 2. Consider the following three data. What number fits in the blank? The correct number could be 18 as the following predicate knowledge can be extracted. top ×left +right =bottom Interestingly, the current AI systems such as ChatGPT (OpenAI, 2025) and DeepSeek (DeepSeekAI, 2025) often answer them incorrectly due to a lack of abstract or logical reasoning skills. Abstraction and Reasoning Corpus (ARC) (Chollet, 2019) is a benchmark test designed to evaluate a machine’s ability to extract visual patterns from images. However, the more analytical patterns shown above are beyond its scope. In this paper, we ask how reasoning in predicate logic should be grounded in data. The underlying idea discussed in this paper is abstraction. Roughly speaking, it is about an inferential process of deriving intrinsically abstract symbols from intrinsically concrete data through selective ignorance. It is not about generalisation where typical inferential procedures, e.g., deductive reasoning, are used backward for general rules from specific examples or facts. This type of reasoning is intensively studied as inverse resolution (Muggleton & Buntine, 1988; Nienhuys-Cheng & Wolf, 1997), inverse deduction (Russell & Norvig, 2020) and inverse entailment (Muggleton, 1995) mainly in inductive logic programming (ILP) (Nienhuys-Cheng & Wolf, 1997). It is also not about parametric learning where intrinsically concrete data are assumed to be generated from probability distributions characterised by their parameters. This idea is prevalent in various applications of machine learning and statistics, e.g., (Bishop, 2006; Tenenbaum et al., 2006; Dasgupta et al., 2020; Lake et al., 2015, 2017). Abstraction is rather relevant to top-down (memory/experience-driven) and bottom-up (sensory-driven) information processing used by neuroscientists and AI researchers as a metaphor for the cognitive process of biological brains, e.g., (Pearl & Russell, 2003; Harnad, 1990; Lee & Mumford, 2003; Hawkins, 2021; Gregory, 1997; Rao & Ballard, 1999; Friston, 2010). In this paper, we extend the inference of propositional abstraction (Kido, 2025a,b) to the inference of predicative abstraction towards enhanced human-like machine intelligence. The key idea is to use the property of predicate logic and expand the joint probability distribution over data, models of predicate logic and predicate formula, denoted by D,Mand α, respectively, as follows. p(D, M, α) = p(α|M, D)p(M|D)p(D) = p(α|M)p(M|D)p(D). Here, the second expression can be derived by applying a valid rule of probability theory. The third expression is an application of the property of formal logic that the truth values of formulas are determined given a model. Probabilistically speaking, the truth values of formulas are conditionally independent of data given a model. The third expression realises the idea that intrinsically abstract knowledge is derived from intrinsically concrete data through abstraction, i.e., selective ignorance. We show that the inference of predicative abstraction serves as a solution to simple yet important problems such as Examples 1 and 2. The research is not as straightforward as we think because the semantics of predicate logic needs a reformulation in accordance with abstraction. Our theory 2 214 INFERENCE OF ABSTRACTION Figure 1. The hierarchy shown on the left is our illustration of the existing work on the inference of propositional abstraction (Kido, 2025a,b). The one shown on the right is an illustration of our work on the inference of predicative abstraction. The top layers are both distributions of data. The middle layer on the left is a distribution of models in propositional logic, i.e., valuations. The one on the right is a distribution of models in predicate logic, i.e., pairs of domains of discourse and valuation functions. The bottom layer on the left is a distribution of the truth values of the propositional formula, whereas the one on the right is the same type of distribution for the predicate formula. assumes only closed formulas, i.e., predicate formulas without free variables, to balance the expressiveness and simplicity of the theory. The contributions of this paper are summarised as follows. • We introduce a simple theory of inference that opens up the possibility of combining probability theory and predicate logic in a data-driven manner. Predicate reasoning in our theory always proceeds between data and predicate formulas. This suggests a shift in the traditional view that predicate reasoning proceeds between predicate formulas via rules of inference (see Section 2). • The theory allows us to see the traditional model-based predicate reasoning as a special case of data-based predicate reasoning studied in this paper. The data-based perspective provides a new opportunity to rethink some existing limitations such as the undecidability of predicate logic, the symbol grounding problem (Harnad, 1990; Russell & Norvig, 2020) and commonsense reasoning (Brewka, 1991; Davis & Marcus, 2015) (see Sections 3.1, 3.2 and 3.3). • We demonstrate a solution to simple yet essential problems that are often difficult to solve by existing established approaches (see Section 3.4). 2. Proposals 2.1 Data support models The inference of abstraction for propositional logic (Kido, 2025a,b) is insufficient to handle problems like Examples 1 and 2. We thus propose the inference of abstraction for predicate logic in this section. Let {d1, d2, ..., dK}be a multiset of Kdata and Dbe a random variable for data taking values from {d1, d2, ..., dK}. 3 215 H. KIDO Definition 1. Let dk∈ {d1, d2, ..., dK}. The probability of dk, denoted by p(D=dk), is defined as follows. p(D=dk) = 1 K(1) Namely, p(D)is a uniform distribution. Let C,V,Fand Pbe the sets of constants, variables, function symbols and predicate symbols, respectively, and Lbe the predicate language built with these vocabularies. Example 3. Consider the following vocabularies of a predicate language. •Constants: C={alice, bob} •Variables: V={x, y} •Function symbols: F={mentor} •Predicate symbols: P={Blames} The following is a predicate formula meaning that Alice’s mentor blames everyone who blames someone. ∀x(∃y(Blames(x, y)) →Blames(mentor(alice), x)) In this paper, we assume that the predicate language includes only formulas without free variables, i.e., closed formulas.1We exclude open formulas for the following reasons. First, it is inappropriate to view an assignment in predicate logic as an abstraction, or selective ignorance, of data or observations. Its inclusion thus does not fit the underlying idea of the inference of abstraction. Second, a lot of cases such as Examples 1 and 2 do not need open formulas. Its inclusion thus makes our formalism unnecessarily complicated. As usual, a model in predicate logic is a pair of a domain of discourse and valuation function. The domain of discourse, denoted by u, is a non-empty set of a finite or countably infinite number of entities. The valuation function, denoted by v, is a function that associates constants, function symbols and predicate symbols with u. We use the symbol ar(x)to denote the arity of the function or predicate symbol x. Specifically, •vmaps each constant c∈ C to an entity of u, i.e., v(c)∈u.2 •vmaps each function symbol f∈ F to an ar(f)-ary function from uto uar(f), i.e., v(f) : uar(f)→u. •vmaps each predicate symbol P∈ P to a subset of uar(P), i.e., v(P)⊆uar(P). 1. The truth values of closed formulas depend only on a model, whereas the truth values of open formulas, i.e., formulas with free variables, depend additionally on an assignment, a function mapping each variable to an entity in the domain of discourse. 2. We assume that vis surjective with respect to C, meaning that there is constant c∈ C such that v(c) = e, for all entities e∈u. This assumption allows us to apply simple semantics of predicate logic. 4 216 INFERENCE OF ABSTRACTION From the viewpoint of the inference of abstraction, it is important to adopt the perspective that each model represents a different state of the world. For any function symbol f∈ F, we write v(f)(v(t1), ..., v(tar(f))) as v(f(t1, ..., tar(f))), where t1, t2, ...tar(f)are the arguments of fcalled terms referring to constants, variables or functions. Let {m1, m2, ..., mN}be the set of models of the predicate language L. This set is finite or countably infinite. Let Mbe a random variable for the models taking values from {m1, m2, ..., mN}. We assume that each data point supports a single model. We thus assume a function m:{d1, d2, ..., dK} → {m1, m2, ..., mN}such that m(dk)denotes the model supported by data dk. Definition 2. Let dk∈ {d1, d2, ..., dK}and mn∈ {m1, m2, ..., mN}. The probability of mngiven dk, denoted by p(M=mn|D=dk), is defined as follows. p(M=mn|D=dk) = (1if mn=m(dk) 0otherwise (2) We use the symbols u(mn)and v(mn)to denote the domain of discourse and the valuation function of the model mn, i.e., mn=⟨u(mn), v(mn)⟩. Thus, the model supported by data dkcan be written as m(dk) = ⟨u(m(dk)), v(m(dk))⟩. Example 4. Consider the predicate language Lbuilt with the following vocabularies. •Constants: C={alice, bob} •Variables: V={x, y} •Function symbols: F=∅ •Predicate symbols: P={Blames} The top layer of the hierarchy shown on the right in Figure 1 shows twenty data. Given u={⊙,⊕}, the middle layer shows all the thirty two models ⟨u, v⟩of the language L. The depth of the middle layer shows how the valuation function vassociates the constants alice and bob with u. Its width shows how vassociates the predicate symbol Blames to u, where an arrow from xto yrepresents that xblames y. Each blank cell in the middle layer is not a model due to the assumption we made in Footnote 2. The arrow from the top to middle layers represent a function m. The twenty data dkcommonly say that there are two people ⊙and ⊕named Alice and Bob, respectively , i.e., u(m(dk)) = {⊙,⊕},v(m(dk))(alice) = ⊙and v(m(dk))(bob) = ⊕. Each data point, however, supports a different situation. Specifically, the functions mand vare given as follows, for all data dk. m(dk) =                m1if k∈ {1-7} m4if k∈ {8-11} m7if k∈ {12-17} m11 if k∈ {18} m13 if k∈ {19,20} v(m(dk))(Blames) =                ∅if k∈ {1-7} {(⊙,⊕),(⊕,⊙)}if k∈ {8-11} {(⊙,⊙),(⊙,⊕)}if k∈ {12-17} {(⊙,⊕),(⊕,⊕)}if k∈ {18} {(⊙,⊙),(⊕,⊕)}if k∈ {19,20} 5 217 H. KIDO 2.2 Models support formulas We are interested in the probability of predicate formula α∈Lbeing true or false. We thus assume that each formula is a random variable taking values from {0,1}. For any truth values v∈ {0,1}, we use the symbol [[α=v]] to denote the set of models where αhas the truth value v. We often write [[α=v]]mn= 1 if mn∈[[α=v]] and [[α=v]]mn= 0 otherwise for the membership of the model. We call formulas with neither logical connectives, such as ¬,∨,∧and →, nor quantifiers, such as ∀and ∃, atomic formulas. Let mn=⟨u, v⟩be a model. As usual, the truth value of an atomic formula without variables is defined as follows. [[P(t1, ..., tar(P))]]mn=(1if (v(t1), ..., v(tar(P))) ∈v(P) 0otherwise Let α, β ∈Lbe formulas and mn=⟨u, v⟩be a model. As usual, the truth values of compound formulas with logical connectives are defined as follows. [[¬α]]mn= 1 ⇔[[α]]mn= 0 [[α∧β]]mn= 1 ⇔[[α]]mn= 1 and [[β]]mn= 1 ⇔min{[[α]]mn,[[β]]mn} [[α∨β]]mn= 1 ⇔[[α]]mn= 1 or [[β]]mn= 1 ⇔max{[[α]]mn,[[β]]mn} [[α→β]]mn= 1 ⇔[[α]]mn= 0 or [[β]]mn= 1 ⇔max{1−[[α]]mn,[[β]]mn} Let us use the symbol α[c/x]to denote the formula replacing all the free variables x∈ V in the formula αby the constant c∈ C. Here, a variable xis free if there is no quantifier bounding xor xis outside the scope of such quantifiers. As usual, the truth values of compound formulas with quantifiers are defined as follows.3 [[∀x α]]mn= 1 ⇔[[α[c/x]]]mn= 1, for all c∈ C ⇔ min c∈C {[[α[c/x]]]mn} [[∃x α]]mn= 1 ⇔[[α[c/x]]]mn= 1, for some c∈ C ⇔ max c∈C {[[α[c/x]]]mn} We say that a formula α∈Lis true in a model mnor mnsatisfies, or supports, αif [[α]]mn= 1. We also write [[α]]mn= 1 as mn∈[[α]]. Example 5 (Continued).Let us find the models where everyone blames someone, i.e., ∀x∃y Blames(x, y), is true. Each atomic formula has the following truth value (see Figure 1). [[Blames(alice, alice)]] = {mn|n∈ {5-8,13-16,25-32}} [[Blames(alice, bob)]] = {mn|n∈ {3,4,7,8,11,12,15,16,18,20,22,24,26,28,30,32}} [[Blames(bob, alice)]] = {mn|n∈ {2,4,6,8,10,12,14,16,19,20,23,24,27,28,31,32}} [[Blames(bob, bob)]] = {mn|n∈ {9-16,21-24,29-32}} 3. This definition is based on the assumption we made in Footnote 2. With this assumption, we can define the truth solely in terms of constants, without referring to the domain of discourse. 6 218 INFERENCE OF ABSTRACTION The compound formula, ∀x∃y Blames(x, y), thus has the following truth value. [[∀x∃y Blames(x, y)]]mn= min c1∈C [[∃y Blames(c1, y)]]mn = min c1∈C max c2∈C [[Blames(c1, c2)]]mn = min max [[Blames(alice, alice)]]mn,[[Blames(alice, bob)]]mn, max [[Blames(bob, alice)]]mn,[[Blames(bob, bob)]]mn =     1if n∈ {3-8,11-16,18,20,22,24-32}∩{2,4,6,8-16,19-24,27-32}, i.e., if n∈ {4,6,8,11-16,20,22,24,27-32} 0otherwise The probability of the truth of a formula is defined using the semantics of predicate logic. Definition 3. Let µ∈[0.5,1],dk∈ {d1, d2, ..., dK},mn∈ {m1, m2, ..., mN},α1, α2, ..., αI∈L and v1, v2, ..., vI∈ {0,1}. The probability of α1=v1given α2=v2, ..., αI=vI,M=mnand D=dk, denoted by p(α1=v1|α2=v2, ..., αI=vI, M =mn, D =dk), is defined as follows. p(α1=v1|α2=v2, ..., αI=vI, M =mn, D =dk) = (µif mn∈[[α1=v1]] 1−µotherwise If we adopt the convention that 00= 1 then Definition 3 can be expressed as a Bernoulli distribution with parameter µ. p(α1=v1|α2=v2, ..., αI=vI, M =mn, D =dk) = µ[[α1=v1]]mn(1 −µ)1−[[α1=v1]]mn In Figure 1, the arrows from the middle to the bottom layer of the hierarchy shown on the right indicate that the predicate formula is true in these models. The following probabilistic property of conditional independence comes directly from the property of predicate logic. Proposition 1. Let α1, α2∈L.α1is conditionally independent of α2and Dgiven M, i.e., p(α1|α2, M, D) = p(α1|M). Proof. See Appendix. From the equation in Proposition 1, we can simplify Definition 3 as follows. p(α1=v1|M=mn) = µ[[α1=v1]](1 −µ)1−[[α1=v1]] (3) The following example shows why we need to assume µ∈[0.5,1], rather than simply µ= 1. Example 6 (Continued.).Let µ= 1 and α=Blames(alice, bob)∧ ¬Blames(alice, bob). Using the definition of conditional probability, the sum rule, the product rule and Proposition 1, we have p(M=m4|α) = p(M=m4, α) p(α)=p(M=m4, α) P32 n=1 p(M=mn, α) =p(α|M=m4)p(M=m4) P32 n=1 p(α|M=mn)p(M=mn)=(1 −µ)p(M=m4) P32 n=1(1 −µ)p(M=mn)=0 0. 7 219 H. KIDO Namely, the value is undefined due to division by zero. However, given µ= 1 such as µapproaches one, denoted by µ→1, the undefined value can be replaced by a reasonable one. p(M=m4|α) = lim µ→1 (1 −µ)p(M=m4) P32 n=1(1 −µ)p(M=mn)=p(M=m4) P32 n=1 p(M=mn)=p(M=m4) Here, P32 n=1 p(M=mn)=1as p(M)is the probability distribution over all the models. In Section 3, we will discuss that µ= 1 corresponds to the logical consequence relation and µ→1corresponds to its natural generalisations. In Figure 1, each arrow between the middle and bottom layers of the hierarchy shown on the right shows that the model satisfies or supports the formula, ∀x(∃y(Blames(x, y)) →Blames(alice, x)). 2.3 Predicate reasoning We can now discuss probabilistic reasoning with predicate language. The following property is useful to simply our notation. Proposition 2. Let α∈L.p(α= 1) = p(¬α= 0). Proof. See Appendix. Therefore, we can write ¬α= 0 as α= 1 and abbreviate α= 1 as α, for all α∈L. We also abbreviate M=mnand D=dkas mnand dk, respectively. Now, using the sum rule, the product rule and the conditional independence, i.e., Proposition 1, the probability of α, β ∈Lcan be expressed as follows. p(α, β) = K X k N X n p(α, β, mn, dk) = K X k N X n p(α|β, mn, dk)p(β|mn, dk)p(mn|dk)p(dk) = K X k N X n p(α|mn)p(β|mn)p(mn|dk)p(dk) Since p(dk)=1/K, i.e., Definition 1, and our assumption that each data point supports a single model, we finally have p(α, β) = 1 K K X k N X n p(α|mn)p(β|mn)p(mn|dk) = 1 K K X k p(α|m(dk))p(β|m(dk)).(4) We here used PN np(α|mn)p(β|mn)p(mn|dk) = p(α|m(dk))p(β|m(dk)). This fact is crucially important in terms of decidability and computational complexity since Ncan be countably infinite. 8 220 INFERENCE OF ABSTRACTION Example 7. Let αbe ∀x(∃y(Blames(x, y)) →Blames(alice, x)) shown in Figure 1. The probability of the formula being true can be evaluated using Equation (4). p(α) = 1 20 20 X k=1 p(α|m(dk)) = 1 20 20 X k=1 µ[[α]]m(dk)(1 −µ)1−[[α]]m(dk) =1 20X k∈{1-17} µ1(1 −µ)0+X k∈{18-20} µ0(1 −µ)1 =1 20X k∈{1-17} µ+X k∈{18-20} (1 −µ)=17µ+ 3(1 −µ) 20 Therefore, p(α) = 17/20 when µ= 1. This result is intuitive as it is the number of data supporting models where αis true, out of all the twenty data. 3. Evaluations 3.1 Reasoning as learning The common view in statistics is that observed data are generated from probability distributions characterised by their parameters. Maximum likelihood estimation (MLE) is the most commonly used statistical method to estimate the values of unobserved parameters only from observed data. MLE is defined as ˆ Θ = arg maxΘp(d1, d2, ..., dK|Θ), where each dkis an observed data point and Θis the set of parameters of a probability distribution. Proposition 3. Let {d1, d2, ..., dK}be a multiset of Kdata and Θbe the parameters of a categorical distribution. p(M) = ˆ Θif and only if ˆ Θmaximises the likelihood of data, i.e., ˆ Θ = arg maxΘp(d1, d2, ..., dK|Θ). Proof. See Appendix. Example 8. Consider the twenty data and thirty two models shown on the top layers of the both hierarchies in Figure 1. Let Kbe the total number of data, and Knbe the number of data in the nth model. We then have p(m1) = 7 20,p(m4) = 4 20,p(m7) = 6 20,p(m11) = 1 20,p(m13) = 2 20 and p(mn) = 0, for all the remaining models mn. 3.2 Reasoning from possible information This section aims to logically characterise the inference of predicative abstraction with µ= 1. We focus on the relation between models and formulas by marginalising out data, i.e., p(α, M) = Pkp(α, M, D =dk). As usual, we use the symbol [[∆]] to denote the set of models where all the formulas in ∆⊆Lare true, i.e., [[∆]] = Tα∈∆[[α]]. A model with a non-zero probability is called possible. We use the symbol [[[∆]]] to denote the set of possible models where all the formulas in ∆⊆Lare true, i.e., [[[∆]]] = {mn∈[[∆]]|p(mn)= 0}. We write mn∈[[∆]] and mn∈[[[∆]]] as [[∆]]mn= 1 and [[[∆]]]mn= 1, respectively. Note that [[∅]] and [[[∅]]] are the sets of all models and 9 221 H. KIDO Davis, E., & Marcus, G. (2015). Commonsense reasoning and commonsense knowledge in artificial intelligence. Communications of the ACM,58(9), 92–103. DeepSeek-AI (2025). DeepSeek-R1: Incentivizing reasoning capability in llms via reinforcement learning. https://arxiv.org/pdf/2501.12948, Retrieved Feb 2025. Friston, K. (2010). The free-energy principle: a unified brain theory? Nature Reviews Neuroscience, 11, 127–138. Gregory, R. L. (1997). Knowledge in perception and illusion. Philos Trans R Soc Lond B Biol Sci, 352, 1121–1127. Harnad, S. (1990). The symbol grounding problem. Physica D: Nonlinear Phenomena,42(1-3), 335–346. Hawkins, J. (2021). A thousand brains: A new theory of intelligence. New York City: Basic Books. Kido, H. (2025a). Inference of abstraction for human-like logical reasoning. Machine Learning, Optimization, and Data Science (pp. 191–206). Cham: Springer Nature Switzerland. Kido, H. (2025b). Inference of abstraction for human-like probabilistic reasoning. Machine Learning, Optimization, and Data Science (pp. 116–131). Cham: Springer Nature Switzerland. Lake, B. M., Salakhutdinov, R., & Tenenbaum, J. B. (2015). Human-level concept learning through probabilistic program induction. Science,350(6266), 1332–1338. Lake, B. M., Ullman, T. D., Tenenbaum, J. B., & Gershman, S. J. (2017). Building machines that learn and think like people. Behavioral and Brain Sciences,40(e253), 1–72. Lee, T. S., & Mumford, D. (2003). Hierarchical Bayesian inference in the visual cortex. Journal of Optical Society of America,20, 1434–1448. Muggleton, S. (1995). Inverse entailment and progol. New Generation Computing,13, 245–286. Muggleton, S., & Buntine, W. (1988). Machine invention of first-order predicates by inverting resolution. Proc. 5th International Conference on Machine Learning (pp. 339–352). Nienhuys-Cheng, S. H., & Wolf, R. D. (1997). Foundation of inductive logic programming. Heidelberg: Springer Berlin, Heidelberg. OpenAI (2025). ChatGPT. https://chat.openai.com/chat, Retrieved Feb 2025. Pearl, J., & Russell, S. (2003). Handbook of brain theory and neural networks, chapter Bayesian Networks, (pp. 157–160). Cambridge, Massachusetts: MIT Press. Rao, R. P. N., & Ballard, D. H. (1999). Predictive coding in the visual cortex: a functional interpretation of some extra-classical receptive-field effects. Nature Neuroscience,2, 79–87. Russell, S., & Norvig, P. (2020). Artificial intelligence : A modern approach, fourth edition. London, England: Pearson Education, Inc. Tenenbaum, J. B., Griffiths, T. L., & Kemp, C. (2006). Theory-based Bayesian models of inductive learning and reasoning. Trends in Cognitive Sciences,10(7), 309–318. 16 228 INFERENCE OF ABSTRACTION Appendix A. Proofs Proposition 1. Using the definition of conditional probability, the right-hand side can be written as p(α1|M) = p(α1, M) p(M). Using the sum rule (Bishop, 2006) and the product rule (Bishop, 2006) of probability theory, its numerator can be expanded as p(α1, M) = X v2X dk p(α1, α2=v2, M, D =dk) =X v2X dk p(α1|α2=v2, M, D =dk)p(α2=v2, M, D =dk). Now, it is obvious from Definition 3 that neither α2nor Daffects the value of p(α1|α2=v2, M, D = dk). We can thus move it outward. Using the sum rule, we have p(α1, M) = p(α1|α2, M, D)X v2X dk p(α2=v2, M, D =dk) = p(α1|α2, M, D)p(M). Taking into accout the denominator, the original expression can be written as p(α1|M) = p(α1|α2, M, D)p(M) p(M)=p(α1|α2, M, D). Proposition 2. αis true in a model iff ¬αis false in the model. Thus, [[α= 1]] = [[¬α= 0]]. Using the sum rule, the product rule and Proposition 1, we have p(α= 1) = X mn p(α= 1|M=mn)p(M=mn) = X mn µ[[α=1]]mn(1 −µ)1−[[α=1]]mnp(M=mn) =X mn µ[[¬α=0]]mn(1 −µ)1−[[¬α=0]]mnp(M=mn) =X mn p(¬α= 0|M=mn)p(M=mn) = p(¬α= 0). This holds regardless of the value of µ. Proposition 3. Let Kbe the total number of data, and Knbe the number of data in the nth category or model. The maximum likelihood estimate of the parameter θnfor a categorical distribution is simply known as the relative frequency of data, i.e., θn=The number of data in the nth category The total number of data =Kn K. 17 229 H. KIDO Therefore, the maximum likelihood estimate is given by ˆ Θ = (K1 K,K2 K, ...., KN K). Let mnbe a model of predicate logic. Using the sum and product rules, we have p(mn) = X k p(mn, dk) = X k p(mn|dk)p(dk) = 1 KX k p(mn|dk) = Kn K. Therefore, we have p(M) = ˆ Θ. Theorem 1. Using the definition of conditional probability and the conditional independence we showed in the previous section, we have p(α|∆) = p(α, ∆) p(∆) =Pnp(α, ∆, mn) Pnp(∆, mn)=Pnp(α|mn)p(∆|mn)p(mn) Pnp(∆|mn)p(mn). Dividing models into possible ones, i.e., [[[∆]]], and the others, we have p(α|∆) = Pmn∈[[[∆]]] p(α|mn)p(∆|mn)p(mn) + Pmn/∈[[[∆]]] p(α|mn)p(∆|mn)p(mn) Pmn∈[[[∆]]] p(∆|mn)p(mn) + Pmn/∈[[[∆]]] p(∆|mn)p(mn). Since µ= 1,p(∆|mn)can be expanded as follows. p(∆|mn) = Y β∈∆ p(β|mn) = Y β∈∆ 1[[β]]mn01−[[β]]mn=(1if mn∈[[∆]] 0otherwise Thus, p(∆|mn)=0, for all mn/∈[[∆]]. Moreover, p(mn)=0, for all mn∈[[∆]] \[[[∆]]]. These two facts imply that Pmn/∈[[[∆]]] p(∆|mn)p(mn)=0. Since p(∆|mn) = 1, for all mn∈[[[∆]]], we have p(α|∆) = Pmn∈[[[∆]]] p(α|mn)p(mn) Pmn∈[[[∆]]] p(mn)=Pn[[[∆]]]mnp(α|mn)p(mn) Pn[[[∆]]]mnp(mn). Since µ= 1,p(α|mn)can be developed as follows. p(α|mn)=1[[α]]mn01−[[α]]mn=(1if mn∈[[α]] 0otherwise Therefore, p(α|∆) = Pn[[α]]mn[[[∆]]]mnp(mn) Pn[[[∆]]]mnp(mn). 18 230 INFERENCE OF ABSTRACTION Corollary 1. p(mn)=0, for all mn∈[[α]] \[[[α]]]. From Theorem 1, we thus have pµ=1(α|∆) = Pn[[α]]mn[[[∆]]]mnp(mn) Pn[[[∆]]]mnp(mn)=Pn[[[α]]]mn[[[∆]]]mnp(mn) Pn[[[∆]]]mnp(mn). The above equation turns out to be one if and only if [[[∆]]] ⊆[[[α]]], i.e., ∆ p ≡α. Theorem 2. Let the symbols |∆|and |∆|mndenote the number of formulas in ∆and the number of formulas in ∆that are true in the model mn, i.e., |∆|mn=Pβ∈∆[[β]]mn, respectively. Using the definition of conditional probability and the conditional independence we showed in the previous section, we have p(α|∆) = p(α, ∆) p(∆) =Pnp(α, ∆, mn) Pnp(∆, mn)=Pnp(α|mn)p(∆|mn)p(mn) Pnp(∆|mn)p(mn). Dividing models into ones in (((∆))) and the others, we have p(α|∆) = Pˆmn∈(((∆))) p(α|ˆmn)p(∆|ˆmn)p( ˆmn) + Pmn/∈(((∆))) p(α|mn)p(∆|mn)p(mn) Pˆmn∈(((∆))) p(∆|ˆmn)p( ˆmn) + Pmn/∈(((∆))) p(∆|mn)p(mn). p(∆|mn)can be developed as follows, for all models mn. p(∆|mn) = Y β∈∆ p(β|mn) = Y β∈∆ µ[[β]]mn(1 −µ)1−[[β]]mn =µPβ∈∆[[β]]mn(1 −µ)Pβ∈∆(1−[[β]]mn)=µ|∆|mn(1 −µ)|∆|−|∆|mn Therefore, p(α|∆) = limµ→1W+X Y+Zwhere W=Pˆmn∈(((∆))) p(α|ˆmn)µ|∆|ˆmn(1 −µ)|∆|−|∆|ˆmnp( ˆmn) X=Pmn/∈(((∆))) p(α|mn)µ|∆|mn(1 −µ)|∆|−|∆|mnp(mn) Y=Pˆmn∈(((∆))) µ|∆|ˆmn(1 −µ)|∆|−|∆|ˆmnp( ˆmn) Z=Pm/∈(((∆))) µ|∆|mn(1 −µ)|∆|−|∆|mnp(mn). If mn/∈(((∆))) then mnis impossible or mnis a possible model of a subset of ∆that is not a cardinality-maximal possible subset of ∆. Therefore, p(mn) = 0 or there is ˆmn∈(((∆))) such that |∆|mn<|∆|ˆmn.|∆|ˆm1=|∆|ˆm2by definition, for all ˆm1,ˆm2∈(((∆))). The fraction thus can be simplified by dividing the denominator and numerator by (1 −µ)|∆|−|∆|ˆmn. We thus have p(α|∆) = limµ→1W′+X′ Y′+Z′where W′=Pˆmn∈(((∆))) p(α|ˆmn)µ|∆|ˆmnp( ˆmn) X′=Pmn/∈(((∆))) p(α|mn)µ|∆|mn(1 −µ)|∆|ˆmn−|∆|mnp(mn) Y′=Pˆmn∈(((∆))) µ|∆|ˆmnp( ˆmn) Z′=Pmn/∈(((∆))) µ|∆|mn(1 −µ)|∆|ˆmn−|∆|mnp(mn). 19 231 H. KIDO Applying the limit, we can cancel out X′and Z′. p(α|∆) = lim µ→1Pˆmn∈(((∆))) p(α|ˆmn)p( ˆmn) Pˆmn∈(((∆))) p( ˆmn)=Pˆmn∈(((∆))) 1[[α]] ˆm01−[[α]] ˆmnp( ˆmn) Pˆmn∈(((∆))) p( ˆmn). By convention, 1[[α]] ˆmn01−[[α]] ˆmn= 1100= 1 if ˆmn∈[[α]] and 1[[α]] ˆmn01−[[α]] ˆmn= 1001= 0 otherwise. Therefore, p(α|∆) = Pˆmn∈(((∆)))[[α]] ˆmnp( ˆmn) Pˆmn∈(((∆))) p( ˆmn)=Pn[[α]]mn(((∆)))mnp(mn) Pn(((∆)))mnp(mn).(7) Corollary 2. Recall that S p ≡αis defined as [[[S]]] ⊆[[[α]]].[[[S]]] ⊆[[[α]]], for all S∈MPS(∆) iff SS∈MP S(∆)[[[S]]] ⊆[[[α]]], i.e., (((∆))) ⊆[[[α]]]. Since Pmn∈(((∆)))[[α]]mnp(mn) = Pmn∈(((∆)))[[[α]]]mnp(mn), Equation (7) can be further expanded as follows, where the resulting value is set to one. p(α|∆) = Pn[[[α]]]mn(((∆)))mnp(mn) Pn(((∆)))mnp(mn)= 1 (8) There is thus no model mnsuch that mn∈[[[α]]] \(((∆))). Therefore, (((∆))) ⊆[[[α]]]. Corollary 3. Since (((∆))) = ((∆)), Equation (7) can be expanded as follows, where the resulting value is set to one. p(α|∆) = Pn[[α]]mn((∆))mnp(mn) Pn((∆))mnp(mn)= 1 (9) Since (((∆))) = ((∆)),p(mn)= 0, for all mn∈((∆)). Thus, Equation (9) holds iff ((∆)) ⊆[[α]], i.e., SS∈MCS(∆)[[S]] ⊆[[α]]. This holds iff [[S]] ⊆[[α]], for all S∈MCS(∆). Corollary 4. Since [[[∆]]] =∅,MPS(∆) = ∆. Thus, (((∆))) = SS∈MPS(∆)[[[S]]] = [[[∆]]]. Therefore, Equation (8) can be written as follows. p(α|∆) = Pn[[[α]]]mn[[[∆]]]mnp(mn) Pn[[[∆]]]mnp(mn)= 1 (10) The denominator cannot be zero because of the assumption of [[[∆]]] =∅. From Equation (10), p(α|∆) = 1 iff [[[∆]]] ⊆[[[α]]]. Corollary 5. Since [[[∆]]] =∅,MPS(∆) = ∆. Thus, (((∆))) = SS∈MPS(∆)[[[S]]] = [[[∆]]]. Namely, there is a possible model where all the elements of ∆are true. Therefore, there is a model where all the elements of ∆are true, i.e., ((∆)) = [[∆]]. Since (((∆))) = ((∆)), we therefore have (((∆))) = [[[∆]]] = ((∆)) = [[∆]]. From Equation (7), we have p(α|∆) = Pn[[α]]mn[[∆]]mnp(mn) Pn[[∆]]mnp(mn)= 1.(11) The denominator cannot be zero as [[∆]] = [[[∆]]] =∅. We thus have p(α|∆) = 1 iff [[∆]] ⊆[[α]]. Corollary 6. This is obvious from Corollary 1 and Corollary 4. 20 232