Inspired by the profound effortlessness (but also the substantial carelessness) with which humans seem to draw inferences when given even only partial information, we consider a unified formal framework for computational cognition, placing our emphasis on the existence of naturalistic mechanisms for representing, manipulating, and acquiring knowledge. Through formal results and discussion, we suggest that such fast and loose mechanisms could provide a concrete basis for the design of cognitive systems.
The founding statement of Artificial Intelligence [McCarthy et al., 1955] proceeds on the basis that “every [...] feature of intelligence can in principle be so precisely described that a machine can be made to simulate it” and proposes to “find how to make machines [...] solve kinds of problems now reserved for humans”. Philosophical considerations aside, the exceptionally powerful machine learning algorithms and the ingeniously crafted reasoning algorithms readily testify that contemporary Artificial Intelligence research has placed more emphasis on the latter front — the effectiveness of algorithms in terms of their behavior — and less emphasis on the former front — their design to simulate features of the human intellect. With Artificial Intelligence research turning sixty years old, this choice on its emphasis has ultimately led to the recently popularized concerns on its future [Open Letter, 2015].
Refocusing on the former front would seem to necessitate the abandonment of rigid and convoluted algorithms, and a shift towards more robust and naturalistic solutions, guided by psychological evidence on human cognition. Further, and contra to the specialization of contemporary Artificial Intelligence research, a holistic view of cognition seems warranted, with perception, reasoning, and learning all being considered in a unified framework that facilitates their close interaction.
We undertake such an investigation herein, with emphasis on the fast nature of drawing inferences [Kahneman, 2011], and the interplay of cognition and perception [Clark, 2013]. We assume that the environment is at each moment in a state. An agent cannot directly access such a state. Rather, it uses a pre-specified language to assign finite names to atoms, which are used to represent concepts related to the environment. The set of all such atoms is not explicitly provided upfront. Atoms are encountered while the agent perceives its environment, or introduced through the agent’s cognitive processing mechanism. At the neural level, each atom might be thought of as a set of neurons assigned to represent a concept [Valiant, 2006].
A scene s is a mapping from atoms to f0; 1; g. We write s[ ] to mean the value associated with atom , and call atom specified in scene s if s[ ] 2 f0; 1g. Scenes s1; s2 agree on atom if s1[ ] = s2[ ]. Scene s1 is an expansion of scene s2 if s1; s2 agree on every atom specified in s2. Scene s1 is a reduction of scene s2 if s2 is an expansion of s1. A scene s is the greatest common reduct of a set S of scenes if s is the only scene among its expansions that is a reduction of each scene in S. A set S of scenes is compatible if there exists a particular scene that is an expansion of each scene in S.
In simple psychological terms, a scene can be thought of as the contents of an agent’s working memory, where the agent’s perception of the environment state, and any relevant thereto drawn inferences, are made concrete for further processing. Following psychological evidence, the maximum number, denoted by w, of specified atoms in any scene used by the agent can be assumed to be a small constant [Miller, 1956].
A propositional formula is true (resp., false) and specified in s if (resp., : ) is classically entailed by the conjunction of: atoms such that s[ ] = 1, and the negation of atoms such that s[ ] = 0; otherwise, is unspecified in s.
When convenient, we represent fully and unambiguously a scene as the set of its true literals (atoms or their negations).
To formalize the agent’s interaction with its environment, let E denote the set of environments of interest, and let a particular environment hdist; perci 2 E determine: a probability distribution dist over states, capturing the possibly complex and unknown dynamics with which states are produced; a stochastic perception process perc determining for each state a probability distribution over a compatible subset of scenes. The agent has only oracle access to hdist; perci such that: in unit time the agent senses its environment and obtains a percept s, resulting by an unknown state t being first drawn from dist, and scene s then drawn from perc(t). A percept s represents, thus, what the agent senses from state t. Example 1. At a pedestrian crossing, the “Don’t Walk” state (t1) is signaled by a light being red and no audible cue, while the “Walk” state (t2) is signaled by the same light being green along with an audible cue. A person (perc1) hears the audible cue or not irrespectively of whether the signal post happens to be obscured. A color-blind person (perc2) sees both red and green lights as yellow, but still perceives the audible cue, unless the person (perc3) also suffers from hearing loss. Let s1 = f:Cueg, s2 = f:Cue; Redg, s3 = f:Cue; Yellowg, s4 = fCueg, s5 = fCue; Greeng, s6 = fCue; Yellowg, s7 = fYellowg. Consider a probability distribution dist assigning probabilities 0:9; 0:1 to states t1; t2, and three perception processes: perc1(t1) assigns probabilities 0:3; 0:7 to scenes fs1; s2g perc1(t2) assigns probabilities 0:6, 0:4 to scenes fs4; s5g perc2(t1) assigns probabilities 0:3; 0:7 to scenes fs1; s3g perc2(t2) assigns probabilities 0:6, 0:4 to scenes fs4; s6g perc3(t1) assigns probabilities 0:3; 0:7 to scenes f ; ; s7g perc3(t2) assigns probabilities 0:6, 0:4 to scenes f ; ; s7g
Scenes in each set form a compatible subset, capturing the possible ways in which the underlying state can be perceived. Not assigning an a priori meaning to states obviates the need to commit to an objective representation of the environment, and accommodates cases where an agent’s perception process determines not only what the agent does (or can possibly) perceive, but also its interpretation. For instance, no perception process above specifies the atom Safe of whether the agent itself believes it is safe to cross. The value of this atom could be inferred internally by the agent’s reasoning process after perceiving the other signals, but cannot be meaningfully determined by the environment state. Furthermore, how an agent perceives the two states, or even whether it perceives them as being distinct, depends on the agent’s perception abilities.
An agent’s key task is to decide how to act optimally (given its perception process) in the current state of the environment. Decision making is often facilitated by having access to more information, and reasoning serves this role (amongst others): it completes information not explicitly available in a percept.1 To do so, it utilizes knowledge that the agent has been given, or has acquired, on certain regularities in the environment. 3
Since reasoning serves to complete information, one naturally seeks representations and processes that determine efficiently what inferences follow, and allow inferences to follow often.
A rule is an expression of the form ' , where formula ' is the body of the rule, and literal is the head of the rule, with ' and not sharing any atoms, and with ' being readonce (no atom appears more than once). The intuitive reading of a rule is that when the rule’s body holds in a scene, an agent has certain evidence that the rule’s head should also hold.
A collection of rules could happen to simultaneously provide evidence for conflicting conclusions. To resolve such conflicts, we let rules be qualified based on their priorities.
A knowledge base = h%; i over a set R of rules comprises a finite collection % R of rules, and an irreflexive antisymmetric priority relation that is a subset of % %.
1Mercier and Sperber [
Based on qualification, we define the reasoning semantics. Definition 2 (Step Operator). The step operator for a knowledge base and a percept s is a mapping si99;sKsi+1 from a scene si to the scene si+1 that is an expansion of s and differs from s only in making true the head of each rule r in that: (i) is applicable on si, (ii) is not exogenously qualified on si by s, and (iii) is not endogenously qualified on si by a rule in ; such a rule r is called dominant in the step.
Intuitively: The truth-values of atoms specified in percept s remain as perceived, since they are not under dispute.2 The truth-values of other atoms in si are updated to incorporate in si+1 the inferences drawn by dominant rules, and also updated to drop any inferences that are no longer supported.3
The inferences of a knowledge base on a percept are determined by the set of scenes that one reaches, and from which one cannot escape, by repeatedly applying the step operator. Definition 3 (Inference Trace and Inference Frontier). The inference trace of a knowledge base on a percept s is the infinite sequence trace( ; s) = s0; s1; s2; : : : of scenes, with s0 = s and si99;sKsi+1 for each integer i 0. The inference frontier of a knowledge base on a percept s is the subset-minimal set front( ; s) of the scenes that appear in trace( ; s) after removing some finite prefix of trace( ; s). Theorem 1 (Properties of the Inference Frontier). Consider a knowledge base , and a percept s. Then, front( ; s) exists, is unique, is non-empty, and includes finitely-many scenes.
Example 2. Consider a knowledge base with the rules r1 : Penguin :Flying, r2 : Bird Flying, r3 : Penguin Bird, r4 : Feathers Bird, r5 : Antarctica ^ Bird ^ Funny Penguin, r6 : Flying Wings, and the priority r1 r2. For percept s = fAntarctica; Funny; Feathersg, trace( ; s) = fAntarctica; Funny; Feathersg, fAntarctica; Funny; Feathers; Birdg, fAntarctica; Funny; Feathers; Bird; Flying; Penguing, fAntarctica; Funny; Feathers; Bird; :Flying; Penguin; Wingsg, fAntarctica; Funny; Feathers; Bird; :Flying; Penguing, fAntarctica; Funny; Feathers; Bird; :Flying; Penguing, : : : 2Overriding percepts can be accounted for by introducing rules that map each perceived atom to a duplicate version thereof, which is thereafter amenable to endogenous qualification by other rules.
3Such updates are accommodated by having scene si+1 be an expansion of the percept s, but not necessarily of the current scene si. and front( ; s) is the singleton set whose only member is the scene fAntarctica; Funny; Feathers; Bird; :Flying; Penguing.
Observe the back and forth while computing trace( ; s). Initially Bird is inferred, giving rise to Flying, and then to Wings. When Penguin is later inferred, it leads rule r1 to oppose the inference Flying from rule r2, and in fact to override and negate it. As a result of this overriding of Flying, inference Wings is no longer supported through rule r6, and is also dropped, even though no other rule directly opposes it.
Thus, the inference trace captures the evolving contents of
an agent’s working memory, while the inference frontier
captures the memory’s final (possibly fluctuating) contents.
Related is a point by Harman [
Intuitively, each rule (i.e., its associated neuron) checks, in parallel, to see if it is applicable on the current scene si, and if its head is not specified in the input percept s. The bound w on the size of scenes ensures the high efficiency of this check. All rules that pass the check proceed to attempt to write, in parallel, their head in a shared memory location (one for each atom), and the rule with the highest priority succeeds, giving rise to a scene si+1 such that si99;sKsi+1. Going from here to computing the inference frontier requires checking for repeated scenes in the inference trace. If only singleton inference frontiers are of interest (as discussed next), such checking reduces to whether si = si+1, which, again, can be done efficiently. The nature of this computation is supported within the Priority CRCW PRAM model [Cormen et al., 2009]. 3.1
In general, the inference frontier may include multiple scenes, and one can define multiple natural notions for entailment. Definition 4 (Entailment Notions). A knowledge base plied on a percept s entails a formula if is: (N1) true in a scene in front( ; s); (N2) true in a scene in front( ; s) and not false in others; (N3) true in every scene in front( ; s); (N4) true in the greatest common reduct of front( ; s). ap
Going from the first to the last notion, entailment becomes more skeptical. Only the first notion of entailment captures what one would typically call credulous entailment, in that is possible, but : might also be possible. The following result clarifies the relationships between these notions. Theorem 2 (Relationships Between Entailment Notions). A knowledge base applied on a percept s entails under Ni if it entails under Nj , for every pair of entailment notions Ni; Nj with i < j. Furthermore, there exists a particular knowledge base applied on a particular percept s that entails a formula i under Ni but it does not entail i under Nj , for every pair of entailment notions Ni; Nj with i < j. Proof. The first claim follows easily. For the second claim, consider a knowledge base with the rules r1 : > a, r2 : a b, r3 : a ^ b c, r4 : c :a, r5 : c b, and the priority r4 r1, and consider a percept s = ;. trace( ; s) comprises the repetition of the five scenes f g a , fa; bg, fa; b; cg, f:a; b; cg, f:a; bg, which constitute front( ; s). The claim follows by letting 1 = a, 2 = b, 3 = a _ b, and observing that the greatest common reduct of front( ; s) is ;.
Note the subtle difference between the entailment notions N3 and N4: under N4 an entailed formula needs to be not only true in every scene in front( ; s), but true for the same reason. This excludes reasoning by case analysis, where an inference can follow if it does in each of a set of collectively exhaustive cases. When front( ; s) = ff g ; f gg, for instance, the formula _ is true in every scene in front( ; s) by case analysis, and is entailed under N3, but not under N4.
When the inference frontier comprises only a single scene (which is, therefore, a fixed-point of the step operator), all entailment notions coincide. In the sequel we restrict our focus, and define our entailment notion only under this special case, remaining oblivious as to what entailment means in general. Definition 5 (Resolute Entailment). A knowledge base is resolute on a percept s if front( ; s) is a singleton set; then, the unique scene in front( ; s) is the resolute conclusion of on s. A knowledge base applied on a percept s on which is resolute entails a formula , denoted ( ; s) jj= , if is true in the resolute conclusion of on s.
Although the entailment semantics itself is skeptical in nature, the mechanism that computes entailment is distinctively credulous. It jumps to inferences as long as there is sufficient evidence to do so, and no immediate / local reason to qualify them. If reasons emerge later that oppose an inference drawn earlier, those are considered as they become available.
This fast and loose mechanism follows Bach [
Are prioritized implications no more than syntactic sugar to conceal the fact that one is simply expressing a single equivalence / definition for each atom? We dismiss this possibility.
Consider a knowledge base . Let body(r0) and head(r0) mean, respectively, the body and head of rule r0 in . Let str(r0) mean the set of rules ri in such that r0; ri are conflicting, and r0 6 ri; i.e., the rules that are stronger (or, more precisely, not less preferred) than r0. Let exc(r0) , Wri2str(r0) body(ri); i.e., the condition for exceptions to r0.
Let cond( ) , Wri:head(ri)= (body(ri) ^ :exc(ri)); i.e., the conditions under which literal is inferred. For each atom , let def( ) , (U _ cond( )) ^ :cond(: ), where U is an atom that does not appear in and is unspecified in every percept of interest. Let T [ ] be the theory comprising an equivalence def( ) for each atom appearing in .
We show, next, a precise sense in which this set of equivalences captures the reasoning via the prioritized rules in . Theorem 3 (Prioritized Rules as Equivalences). Consider a knowledge base , a percept s = ;, and a scene si specifying every atom in rule bodies in . Then: si99;sKsi+1 if and only if si+1 = f j def( ) 2 T [ ]; def( ) is true in sig [ f: j def( ) 2 T [ ]; def( ) is false in sig. Proof. Each dominant rule in si99;sKsi+1 leads the associated equivalence to infer the rule’s head. Atoms with no dominant rules are left unspecified by the associated equivalences.
In Theorem 3 we have used the step operator with the percept s = ; simply as a convenient way to exclude the process of exogenous qualification, and show that endogenous qualification among prioritized rules is properly captured by the translation to equivalences. It follows, then, that if one were to define a step operator for equivalences and apply the exogenous qualification coming from an arbitrary percept s on top of the drawn inferences, one would have an equivalent step operator to the one using prioritized rules with the percept s.
What is critical, however, and is not used simply for convenience in Theorem 3, is the insistence on having a scene si in which every atom in rule bodies in is specified. Indeed, the translation works as long as full information is available, which is, of course, contrary to the perception semantics we have argued for. For general scenes the translation is problematic, as illustrated by the following two natural examples. Example 3. Consider a knowledge base with the rules r1 : Bird Flying, r2 : Penguin :Flying, and the priority r2 r1. The resulting equivalence is of the form: (U_Bird)^ :Penguin Flying. By applying Theorem 3, when si is the scene fBird; Penguing, fBird; :Penguing, f:Bird; Penguing, or f:Bird; :Penguing, both the considered knowledge base and the resulting equivalence give, respectively, rise to the same inference :Flying, Flying, :Flying, or ‘unspecified’. However, when si = fBirdg, the considered knowledge base gives rise to the inference Flying, whereas the resulting equivalence gives rise to the inference ‘unspecified’ for Flying.
Since the two formalisms agree on what to infer on a fullyspecified scene, they disagree on a general scene only when one infers ‘unspecified’ and the other does not; i.e., they never give rise to contradictory inferences in any single step. However, because of the multiple steps in the reasoning process, contradictory inferences may arise at the end. Further, it is not always the case that the knowledge base gives more specified inferences when the formalisms disagree in a single step. Example 4. Consider a knowledge base with the rules r1 : , r2 : : . The resulting equivalence is of the form: > . On a scene si that specifies , the formalisms coincide, but on the scene si = ;, the considered knowledge base gives rise to the inference ‘unspecified’ for , whereas the resulting equivalence gives rise to the inference .
Thinking that formalisms are more appropriate (in terms of completeness) if they give more specified inferences, comes from viewing them as computational processes meant to implement an underlying mathematical logic. As we have seen, however, case analysis might not be natural, and excluding it could be psychologically-warranted. In this frame of mind, it is the knowledge base that is more appropriate in both our examples, jumping to the conclusion that birds fly when no information is available on their penguin-hood, but avoiding to draw a conclusion that would follow by a case analysis.
Beyond the conceptual reasons to choose prioritized rules over equivalences, there are also certain formal reasons. First, reasoning with equivalences is an NP-hard problem: evaluating a 3-CNF formula (as the body of an equivalence) on a scene that does not specify any formula atoms amounts to deciding the formula’s satisfiability [Michael, 2010; 2011]. Second, the knowledge representable in an equivalence is subject to certain inherent limitations, which are overcome only when multiple equivalences are used instead [Michael, 2014].
Of course, one could counter-argue that the case analysis, and the intractability of reasoning that we claim is avoided by using prioritized rules can easily creep in if, for instance, a knowledge base includes the rule ' for ' = _: , or ' equal to a 3-CNF formula. Our insistence on using read-once formulas for the body of rules avoids such concerns.
Our analysis above reveals that the choice of representation follows inexorably from the partial nature of perception. Prioritized rules are easy to check, while allowing expressivity through their collectiveness, and easy to draw inferences with, while avoiding non-naturalistic reasoning patterns.
Abstract argumentation [Dung, 1995] has revealed itself as a powerful formalism, within which several forms of defeasible reasoning can be understood. We examine the relation of our proposed semantics to abstract argumentation, by considering a natural way to instantiate the arguments and their attacks. Definition 6 (Arguments). An argument A for the literal given a knowledge base and a percept s is a subset-minimal set of explanation-conclusion pairs of the form he; ci ordered such that: if e equals s, then c is a literal that is true in s; if e equals a rule r in , then c is the head of the rule, and the rule’s body is classically entailed by the set of conclusions in the preceding pairs in A; c equals for the last pair in A.
Definition 7 (Attack Notions). An argument A1 for literal 1 attacks an argument A2 for literal 2 given a knowledge base and a percept s if there exist he1; c1i 2 A1 and he2; c2i 2 A2 such that c1 = 1, c2 = : 1, e2 is a rule in , and either e1 = s or: (N1) e1 is a rule in and e2 6 e1; (N2) for every he; ci 2 A1 such that e is a rule in , it holds that e2 6 e. Definition 8 (Argumentation Framework). The argumentation framework hA; Ri associated with a knowledge base and a percept s comprises the set A of all arguments for any literal given and s, and the attacking relation R A A such that hA1; A2i 2 R if A1 attacks A2 given and s.
Most typical semantics for abstract and logic-based argumentation frameworks give rise to multiple extensions, and differ from our formalism either because they produce credulous inferences, or because determining their skeptical inferences requires checking all such extensions. We show below that the grounded semantics can also be differentiated from our proposed formalism, even if not on these same grounds. Definition 9 (Argumentation Framework Entailment). A set of arguments entails a formula if is classically entailed by the set f j A 2 is an argument for g of literals. An argumentation framework hA; Ri entails a formula if is entailed by the grounded extension of hA; Ri.
Theorem 4 (Incomparability with Argumentation). There exists a knowledge base , a percept s, and a formula such that: (i) is resolute on s, and ( ; s) jj= : , (ii) for either attack notion N1; N2, the argumentation framework hA; Ri associated with and s is well-founded, and hA; Ri entails . Proof. Let =a. Consider a knowledge base with the rules r1 : > r5 : b a :a r2 : > r6 : b b r3 : > d r7 : d c :a r4 : c r8 : :a :b d and the priorities r4 r2, r5 r1, r7 r1. Consider the percept s = ;, on which is resolute. Indeed, trace( ; s) equals ;; fa; b; cg ; f:a; :b; c; dg ; f:a; :b; c; dg ; : : :, and front( ; s) = ff:a; :b; c; dgg. Clearly, ( ; s) jj= :a.
Consider, now, the set = fA1; A2g with the arguments A1 = fhr3; ci ; hr4; :big, A2 = fhr1; aig. Observe that no argument A3 is such that hA3; A1i 2 R. Furthermore, any argument A4 such that hA4; A2i 2 R includes either hr5; :ai or hr7; :ai, and necessarily hr2; bi. Thus, hA1; A4i 2 R, and therefore is a subset of the grounded extension of hA; Ri. Clearly, hA; Ri entails a. Also, hA; Ri is well-founded.
The incomparability — even for resolute knowledge bases and well-founded argumentation frameworks — is traceable to the skeptical and rigid semantics of argumentation, which meticulously chooses an argument (and thus a new inference) to include in the grounded extension, after ensuring that the choice is globally appropriate and will not be later retracted.
Such a treatment that reasons ideally and explicitly from
premises to conclusions is dismissed by Bach [
Bach [
Given a set P of atoms, the P -projection of a scene s is the scene sP , f j 2 s and the atom of is in P g; the P projection of a set S of scenes is the set SP , fsP j s 2 Sg. Definition 10 (Projected Resoluteness). Given a knowledge base , a percept s, and a set P of atoms, is P -resolute on s if the P -projection of front( ; s) is a singleton set; then, the unique scene in the P -projection of front( ; s) is the P -resolute conclusion of on s.
Definition 11 (Projected Completeness). Given a knowledge base , a percept s, and a set P of atoms such that is P resolute on s, and si is the P -resolute conclusion of on s, is P -complete on s if si specifies every atom in P . Definition 12 (Projected Soundness). Given a knowledge base , a compatible subset S of scenes, a percept s, and a set P of atoms, such that is P -resolute on s, and si is the P -resolute conclusion of on s, is P -sound on s against S if fsig [ S is compatible; i.e., there is no atom that is true (resp., false) in si and false (resp., true) in some scene in S.
The notions above can, then, be used to evaluate the performance of a given knowledge base on a given environment. Definition 13 (Knowledge Base Evaluation Metrics). Given an environment hdist; perci 2 E, a set P of atoms, and a real number " 2 [0; 1], a knowledge base is "-resolute, "complete, or "-sound on hdist; perci with focus P if with probability at least " an oracle call to hdist; perci gives rise to a state t being drawn from dist and a scene s being drawn from perc(t) such that, respectively, is P -resolute on s, is P -complete on s, or is P -sound on s against S, where S is the compatible subset of scenes determined by perc(t).
It would seem unrealistic that a single globally-appropriate tradeoff between these evaluation metrics should exist, and that a learner should strive for a particular type of knowledge base independently of context. Nonetheless, some guidance is available. Prior work [Michael, 2014] shows that one cannot be expected to provide explicit completeness guarantees when learning from partial percepts, and that one should focus on soundness, letting reasoning over the multiple rules being considered to improve completeness to the extent allowed by the perception process perc that happens to be available.
The seemingly ill-defined requirement to ensure soundness against the unknown compatible subset S — effectively, the state t that underlies percept s — can be achieved optimally in some defined sense by (and only by) ensuring that the drawn inferences are consistent with the percept s itself [Michael, 2010]; or, in the language of this work, that the rules used are not exogenously qualified during the reasoning process.
Note that although the reasoning process can cope with exogenous qualification, this ability should be used in response to unexpected / exceptional circumstances, and only as a last resort. It is the role of the learning process to minimize the occurrences of exogenous qualifications, and to turn them into endogenous qualifications, through which the agent internally can explain why a certain rule failed to draw an inference.
Interestingly, the position above echoes evidence from the behavioral and brain sciences, asserting that the human brain is ultimately a predictive machine that learns (and even acts) in a manner that will minimize surprisal in its percepts [Clark, 2013]. Our analysis reveals that surprisal minimization is not necessarily an end in itself and a goal of the learning process, but rather a means to the reliability of the reasoning process.
Examining learnability turns out to offer arguments for and against our proposed formalism. On the positive side, learning when the atoms are not determined upfront remains possible and enjoys naturalistic algorithms for several problems [Blum, 1992]. Priorities between implications can be identified by learning default concepts [Schuurmans and Greiner, 1994] or learning exceptions [Dimopoulos and Kakas, 1995]. On the negative side, partial percepts hinder learnability, with even decision lists (hierarchical exceptions, bundled into single equivalences) being unlearnable under typical worst-case complexity assumptions [Michael, 2010; 2011]. Noisy percepts also critically hinder learnability [Kearns and Li, 1993].
Back on the positive side, environments without adversarially chosen partial and noisy percepts undermine the nonlearnability results. The demonstrable difference of a collection of prioritized implications from a single equivalence further suggests that the non-learnability of the latter need not carry over to the former. Back on the negative side again, learning from partial percepts cannot be decoupled from reasoning, and one must simultaneously learn and predict to get highly-complete inferences [Michael, 2014]. Efficiency concerns, then, impose restrictions on the length of the inference trace, which, fortuitously, can be viewed in a rather positive light as being in line with psychological evidence on the restricted depth of human reasoning [Balota and Lorch, 1986].
Overall, our framework would seem to lie at the edge between what is or is not (known to be) learnable. This realization can be viewed as favorable evidence, since, one could argue, evolutionary pressure would have pushed for such an optimal choice for the cognitive processing in humans as well. 4.1
Unsurprisingly, then, establishing the formal learnability of a knowledge base should be viewed as a major open challenge, and one that might need to be guided by a deeper understanding of how humans come to acquire their world knowledge. Nonetheless, we are able to provide some initial directions.
We consider certain complexity metrics for any knowledge base = h%; i. The breadth of is the maximum number b of body atoms in a rule r 2 %. The depth of is the maximum number d such that r0 r1 : : : rd for rules ri 2 %. A Boolean (logic) circuit implements over a set P of atoms if for every percept sP on which is P -resolute, the circuit on sP outputs the P -resolute conclusion of on sP . The circuit complexity of over P is the minimum size of such a circuit. Theorem 5 (Unlearnability of Unbounded-Breadth Knowledge Bases). For any positive integer b, and any set Pb of atoms, there exists a set Eb of environments on each of which there exists a target knowledge base with breath b and depth 1 that is 1-resolute, 1-complete, and 1-sound with focus Pb. Under cryptographic assumptions, and for any " > 0, there is no algorithm that, given b and oracle access to an environment hdist; perci 2 Eb, runs in time polynomial in the circuit complexity of the target knowledge base over Pb, and returns with probability at least " a knowledge base that is "complete and (1=2+")-sound on hdist; perci with focus Pb. Proof. A circuit C over b input variables can be implemented within a knowledge base with breadth b and depth 1: includes the rule r0 : > : ; for each disjunct ' in the DNF representation of C, includes the rule r : ' and the priority r r0. The proof rests on the unlearnability of circuits under standard cryptographic assumptions [Kearns and Vazirani, 1994] and proceeds roughly analogously to existing unlearnability results; e.g., [Michael, 2014, Theorem 8].
Does a result analogous to Theorem 5 hold for knowledge bases with unbounded depth? The question is inapplicable if one disallows duplicate rules with different names (and priorities), since breadth bounds imply depth bounds. With duplication things are less clear, and the question remains open.
Our discussion points to the main research problem: establishing the existence of naturalistic learning algorithms for bounded-breadth and bounded-depth knowledge bases. 4.2
One may wonder whether updating a knowledge base through a process of learning suffices, or whether extra revision processes are needed (e.g., removing parts of the knowledge base through belief revision [Peppas, 2008]). We show that learning new rules suffices to nullify the effect of existing parts of the knowledge base, if this happens to be desirable, without a “surgery” to the existing knowledge [McCarthy, 1998]. Definition 14 (Knowledge Base Equivalence). Knowledge bases 1; 2 are equivalent if for every percept s (on which both 1 and 2 are resolute), front( 1; s) = front( 2; s).
Below we write 1 2 for two knowledge bases 1 = h%1; 1i ; 2 = h%2; 2i to mean %1 %2 and 1 2. Theorem 6 (Additive Elaboration Tolerance). Consider two knowledge bases 0; 1. Then, there exists a knowledge base 2 such that 1 2 and 0; 2 are equivalent.
Proof. Set 2 := 1. For each rule r : ' in 1, add to 2 the rule f1(r) : ' : with a fresh name f1(r). For each rule r : ' in 0, add to 2 the rule f0(r) : ' with a fresh name f0(r). Give priority to rule f0(r) over every other rule that appears in 2 because of 1. For every priority ri 0 rj in 0, add to 2 the priority f0(ri) 2 f0(rj ). 5
For everyday cognitive tasks (as opposed to problem solving tasks), humans resort to fast thinking [Kahneman, 2011], a form of which we have formalized. The formalism has been implemented in Mathematica, and is being used for an empirical exploration of possible learning strategies and other extensions. A Prolog meta-interpreter (supporting two natural representations of prioritized implications) for the reasoning semantics has also been implemented to evaluate reasoning.
Related to our work is a neuroidal architecture that exploits relational implications and learned priorities [Valiant, 2000a], but does not examine the intricacies of reasoning with learned rules on partial percepts. Extending this work to use relational rules can proceed via known reductions [Valiant, 2000b].
In addition to other possible extensions (e.g., asynchronous and / or probabilistic application of rules, decreasing gradient in rule activations, time-stamped atoms for temporal reasoning, coherence mechanism to ensure cognitive economy), and further formal analysis (e.g., establishing learnability and complexity results), we believe that, ultimately, the challenge is the design and development of a cognitive system with the following properties — towards which our formalism makes a concrete step, and following which it can be further extended: (1) perpetual and sustainable operation, without suppositions on pre-specified and bounded collections of atoms or rules; (2) continual improvement and evaluation, without designated training and testing phases for its learning process; (3) autodidactic learnability, avoiding any dependence on some form of external human supervision [Michael, 2010]; (4) a holistic architecture, integrating seamlessly perception, reasoning, and learning in a coherent whole [Michael, 2014]; (5) non-rigidness and robustness, accommodating a graceful recovery from externally and / or internally-induced errors, a point raised by von Neumann [1961] when envisioning the differences of a future logical theory of computation from formal logic: “1. The actual length of ‘chains of reasoning’ [...] will have to be considered.” and “2. The operations of logic [...] will all have to be treated by procedures which allow exceptions (malfunctions) with low but non-zero probabilities.”.
In mechanizing human cognition, it might be that getting the behavior right offers too little feedback [Levesque, 2014], and that looking into the human psyche is the way to go.