--- title: "Experiments with a Search Algorithm for the Data Base of a Human Belief System" authors: - "Kenneth Mark Colby" - "Lawrence G. Tesler" - "Horace J. Enea" doi: "" url: "https://ijcai.org/proceedings/1969/57" pdf: "https://ijcai.org/proceedings/1969/0057.pdf" venue: "Proceedings of the First International Joint Conference on Artificial Intelligence" year: 1969 pages: "649-654" track: "Psychological Modeling" keywords: --- # Experiments with a Search Algorithm for the Data Base of a Human Belief System Kenneth Mark Colby, Lawrence G. Tesler, Horace J. Enea *Proceedings of the First International Joint Conference on Artificial Intelligence*, pages 649-654. ## Abstract A large data base was collected from a human informant . The data consisted of beliefs regarding parent - child r e la t ion s . A variety of factors in searching the data base were manipulated in an attempt to discover which were the more important in contributing to estimates of credibility . Problems of data collection, data representation and a searching algorithm are discussed in detail. ## Full text ## Introduction It is clear that people hold beliefs . What is not so cl ear is how these beliefs are processed to judge the credibility of an input proposition. As an aid in understanding credibility processes, we constructed a computer model which was intended to simulate the belief processes of a particular human informant . We shall begin with a cl arifica­ tion of terminology used in describing the model. ## Terminology A model consists of a set of interacting com­ ponents . The major components of the mode l to be described are state- descriptions (data base), pro­ cess- descriptions (procedures) and an interpreter whose logic governs the applications of process­ descriptions to state- descriptions in accordance with the aim or task of judging credibility. Thus the model is two levelled vlith the interpreter at the top supervising interactions between procedures and data base . The data base is made up of a conceptual graph whose basic structures consists of conceptualiza­ tions in turn composed of elementary conceptions. Conceptual izations in the model are held proposi­ tions which symbolically represent states of aff­ airs or situations . Conceptualizations can be represented in both natural and computer l anguages by an ordered set of name- tokens . Thus a given con­ ceptualization might be described in English as 'Bill likes Mary ' and in a programming l anguage as the list ((agent Bill ) (action like) (object Mary)) . The particul ar conceptualizations we focussed on were those which semantically involved certain relations between humans . Since peopl e conceptual­ ize their experience with persons in terms of human action, the elementary conceptions of the data base invol ve agents , act ions, objects and (optionally) settings , modalit ies and rational es . The term 'belief' in human belief structures refers to (a) an affective attitude of acceptance , rejection or neutral judgment towards, (b) a hel d example, the name- token 'love' is defined as sim­ ilar - to and stronger- then 'like'. 'Dislike' is definabl e as negation- of 'like ' . These defiru.tions are used in finding similarities and contrasts be­ tween conceptualizations . Classifications consist of set memberships and set inclusions . In summary, the data base represents informa­ tion in the form of various kinds of state descrip­ tions . When the model runs, this information is subjected to procedures governed by a top- level interpreter . The procedures are called into operation by the interpreter in accordance with the task involved. The main task we were interested in invol ves estimating the credibil­ ity of a given proposition describing some actual or hypothetical situations . Given such a proposition, how might a person judge its credibility using the information-processing capacities he has avai l abl e? We approached this problem by selecting an informant , col lecting certain bel iefs , and represent ­ ing them in a data base . We pl anned first to con­ duct certain information- processing experiments on the data base and second to attempt a val idation of the simul ation. This report will be concerned wi t h the first phase of experimentation. ## Data Collection To find an informant for this research, we advertised in a college newspaper for persons who might be interested. Out of 65 appl icants , we interviewed 26 and then sel ected a 30 year old married woman on grounds that she was intelligent , articulate , interested in the research and serious of purpose . * Several times a week she woul d write down in natural language beliefs which occurred to her about events in her life . Each week we woul d try to reduce these natural language statements to a simpler form suitable for the model's data base and processing. At interval s we would show the data base to the i nformant for her corroboration or correction of our paraphrasings . Initially we planned to obtain her beliefs regarding al l the important people in her life space . Preliminary experience showed that while collection of such data is possibl e , the labor required to organize and represent this amount of data in a computer model makes the task extremely difficult with currently available methods . We found two main disadvantages to this method of data- collection. First , it is cumbersome and time- consuming , requiring hundreds of man- hours to obtain a data base of 700 facts, rules, definitions and classifications . A better method should be developed whereby an informant could type informa­ tion dir ectly into a data-base by means of a man­ machine dialogue . This input might be in an artifi­ cial and simplified l anguage which an informant could learn. However an artificial l anguage is distracting and constrains expressiveness . It would be better to all ow the rich freedom of natural l ang­ uage but there are great problems involved in the machine handling of this sort of input . We have had some experience along these lines3 and we are con­ tinuing an attempt to make a conceptual parsing of natural l anguage sentences in order to translate them i nto conceptualizations suitabl e for the data base of a bel ief structure4. *For obvious reasons we cannot give her name , but we woul d like to use this footnote to express our gratitude for her help. A second drawback to our initial data collection method invol ved the probl em of extensiveness ver sus intensi veness . An extensive data base is one in which there ar e a gr eat variety of conceptualizations but not a great number around any one theme . While containing a l arge amount of information, this type of data is too sparse to permit the model to come to very many conclusions regarding credibility. Few bel iefs of r el evance can be found for a given propo­ siti on unl ess it is of a very general and hence trivial nature . We then attempted to concentr ate on a particular theme in order to make the data base dense around selected conceptions . Since our informant was the mother of a three year old chil d and interested in the probl em of child raising, we concentrated on her bel iefs in this ar ea. For each of her beliefs in this domain, we obtained a weighting of a degree of credibi lity. We used crude categories of strong, medium and weak for these weightings . To obtain data rules we would ask the informant for reasons for each bel ief. For example, if a belief were 'a chil d ought not hit another child' and the reason given by the informant was 'because if a child hits another child then the second child gets hurt ' , a general if- then expectation rul e can be constructed about the rel ation between hitting and hurting. One difficulty to be anticipated in simulating a human belief structure invol ves keeping the model updated along with the informant . I f a person 's beliefs are continually changing, one cannot keep a model in close enough correspondence to test out comparisons between the person 's and the mode l 's performances in estimating credibility. However, we found that with our informant , these particular beliefs about parent- child behavior changed very little over a period of several months . In the case of onl y two beliefs did she change a credibility weight from strong to medium. Hence the str ucture appeared quite stabl e over this period of time . I t should al so be remarked that there occurred no major environmental event in this domain of interest which might be expected to have great impact on a bel ief structure. We attempted to model the credibility processes of a single individual . This approach is in the research tradition of an intensive design in contrast to an extensive design. An extensive design mi ght make one observation on 1000 persons while an inten­ sive design would make 1000 observations on one person. Both designs attempt to account f or varia­ tion in the -phenomena obser ved. In an extensive design, the unit of variability is an individual and variation between individual s is studied whereas in an intensive design we are studying the variability within an individual . In modelling a single case we are trying to understand the mechanisms involved in intra- individual processes . An intensive design attempts to show what can and does happen. The frequency of this sort of happening in a population and which population is another matter . After learn­ ing how to model one person we can model another and so build up a series of cases . The inductive problem of generalizing then becomes one of sampling and of statistical measures to discover how general the informant 's beliefs might be in a population. This was not our problem at this state of the inquiry. Our problem was how to construct a good model of the informant's belief processes . The criteria for 'good ' can be varied. And are we getting at what the informant 'real ly' bel ieves? What 'really' means here is obscure but it is common knowledge that people have limited accessibility to their beliefs at a given moment . Even worse , they have (F(agent Barb) (action like) (object chi l dren) (credibility 0. 9)) with the symbol F indicating this is a fact . More complicated is the representa­ tion of a rule because of the probl em of binding variables unambiguously. For example , the natural language statement 'parents spank children ' has a number of possible semantic interpretations . It was necessary to check carefully with the informant in order to be clear about which interpretation she intended. In this case she did not mean that the set 'parents ' spank the set 'children ' nor did she mean each member of the set 'parents ' spank each member of the set 'children'. By the expression 'parents spank children' she meant that a given parent spanks his children. More formally, if x is a parent and y is a child and x is a parent of y, then x spanks y. The relation 'is a parent of ' must first be defined in terms of certain constrained variables . For instance, the variable P 4 is defined as a parent who is a parent of cx4 and cx 4 is defined as the capacity to deceive themselves to rationalize, and to distort their own bel iefs . Over time we hoped to increase accessibil ity, real izing there are a child who is a child of px4' When assignments are always limits . In worrying about what is 'really ' made to such variabl es onl y those name tokens which believed we found it useful to keep in mind that we qual ify can be substituted. Thus the rule 'if a were constructing a model of a model . · A belief struc- parent likes his chil d, then his chil d is happy ' ture is a representation and in giving information would be represented as the list : about himself, an informant tells us what he bel ieves he believes . He simulates himsel f and it is his accessible model of himsel f that becomes the data base of a computer model . Humans ' ability to simulate themselves and to make models of other model s is of course a most interesting property for a symbolic system to have . ((agent cx4) (action has) (object happiness)))) ## Data Representation In building a data base for the model we thought of the coll ected facts , rules, defi nitions and classifications as a graph. Physically in the model tgey were lists in the programming language MLISP5 , · MLISP is a high level list processing language which translate ALGOL- like meta- statements (M- expressions ) into the symbolic statements (S­ expressions) of LISP 1. 5. The program runs on the PDP- 6/10 time- sharing system of the Stanford Arti ­ ficial Intelligence Project . Each conceptualization was represented as a list of elements consisting of English-like name tokens or atoms , of lists of atoms, and of l ists of lists which contained semantic and numerical infor­ mation . As mention in the section 'Terminology', the conceptualizations refl ect a human action model of situations in the interpersonal worl d. From this perspective, agents carry out actions towards objects which in turn can be agents or other situations . In the data base each agent, action, object, etc., is identifi ed by an atom. On the property list of each atom is a l ist of p0inters to all conceptions in the data base in which that par­ ticular atom occurs . A hash coding scheme is used for rapid look- ups and r etrieval of r el evant con­ ceptions . The representation of a fact such as 'Barb l ikes children ' appears on the l ist : with the symbol R indicating that it is an impli­ cational rule. When facts are search to match the components of a rule , the fact 'John likes Mary ' would fit this rule onl y if John is held to be a parent of Mary so that 'John ' can be substituted for Px 4 and 'Mary ' for cx 4 ' These constrained variables are global in the program. They permit the binding of variables to be unambi guous and allow rules to be arbitrarily complex since the qualifica­ tions required for the variable may involve multi­ ple conditions . Representation of definitions is in the form of a simple list . To indicate conceptual relations between 'l ove ' and 'like ' , the list appears as (love similar like s) where the symbol S indicates 'love' intensity than 'like '. The following tions represented in definitions, S stronger , W weaker , and E equal . is stronger in are some rela­ meaning similar different negative opposite kindof (love simil ar like s) (men different women) (not l ike negative like E) (love opposite hate E) (spank kindof aggression) Classifications take the simple form, (F(agent matches) (action is a) (object things)) Ini tial experience with a data base of 700 facts , rules , definitions and cl assifications not onl y taught us about the density requirements of data but also brought to light an implementation problem. When output from a running model is not satisfactory, it may be due to errors in the data as well as to inadequacies of the procedures . ' A small data error, (such as the term 'notlike' in a conceptualization instead of 'like'), originating from human mistakes in inputting data into the data base, can give rise to an incorrect credibility estimate. When a data base is l arge, it becomes extremely difficult to trace entirely by hand what happened in a given run of the model. We tried frequently to check the data for errors and the informant repeatedly studied a listing of the data- base searching for mistakes . In spite of this labor of scrutiny, disconcerting data errors would still crop up. To make sure the pro­ cedures were operating as postulated, we first selected a very restricted subset of the data base and then gradually added to it. as the program be­ came debugged. ## Procedures The modelling program scal es variables such as credibility, foundation, and consistency into the range 0 to 100. The interpretation of these number& is as follows: | 90-100 | Strongly positive | |----------|--------------------------------| | 60- S9 | Weakly to moderately positive | | 41-59 | Undecided | | 11-40 | Moderatel y to weakly negative | | 0-10 | Strongly negative. | Credibility is a function of two components: dation and consistency. ![Image](https://ijcai.org/proceedings/1969/fulltext/57/image_000000_b331a90baf2922edd20862e54246bd8c3fc3ad21d71a51e71a382c1c54dc9e3f.png) The foundation of a proposition is a measure of the model 's evidence for and against the proposition. If the positive evidence outweighs the negative, then the foundation is high; if the negative evi­ dence is stronger, the foundation is low. Credibili ty is a function mainly of foundation. When foundation is moderate , consistency has more influence on credibility than when foundation is extr eme . Thus , if the evidence concerning a propo­ sition is not dominantly pro or con, then the model gives extra weight to its consistency in determining its credibility. A formula for credibility which incorporates this factor is given below. The "weight" is a number between 0 and 0. 02 which indicates the relative importance of consistency in this computation. If consistency is irrelevant , the weight is zero. If it is dominant , the weight is 0. 02 . ## EXAMPLES CREDIBILITY as a function of Foundation and Consis­ tency The consistency of a proposition P is com­ puted by finding a few highly relevant beliefs and measuring the consonance of P with these beliefs . Relevance is defined objectively. If P is a pro­ position of the predicate form f(p) and if there i s a rule in the model that says : | | 100 | Consistenc;t - So | Consistenc;t - 50 | 20 | 0 | |------------|------------|---------------------|---------------------|------------|------------| | Foundation | Foundation | Foundation | Foundation | Foundation | Foundation | | So | 90 | S6 | So | 74 | 70 | | 50 | 75 | 65 | 50 | 35 | 25 | | 20 | 30 | 26 | 20 | 14 | 10 | and if g(p) Qi, then Qi is the predicate form of a belief is highly relevant to P. If the model already disbelieves Qi or believes , ~ -- then P is dissonant with it . I f the model neither believes or disbelieves consistency of P is not affected. Q. then the l. The computation of consistancy consists of determining the percentage of ~'s with which P is consonant . More weight is given to consonance with more credible Q. 's than to consonance with less credible ~·s . 1 A set of formulas that incor­ porate this weighting is given below. The foundation of a proposition P is computed by finding relevant beliefs and seeing whether they imply that P is or is not the case . I n the search for relevant beliefs, graph paths through beliefs consonant with P are searched harder than paths through beliefs dissonant with P if P seems to be highly consistent . The reverse strategy is used if P seems to be inconsistent . This is done so that model can attempt to l imit its search for evi ­ dence in such a way as to maintain the consistency of its entire belief structure . Formulas for foundation in terms of evidence for and against P are: - sc z credibility (~), where Qi ~ P and credibility (Q.) > 50 cc en l count of Q. 1 s contributing to sc l count of Qi's where Qi ~, P and credibility (Q.) > 50 l foundation= ![Image](https://ijcai.org/proceedings/1969/fulltext/57/image_000001_0d468decc6e710e54dbdbb47ecc2c7707e432625a8bdc79d9e88968a1d39a4b0.png) The search for relevant bel iefs is control led by a "work" factor . A consistency search will do, say, 200 units of work while a foundation search wi ll do, say, 1000 units of work. This wor k allot­ ment is apportioned among the possible graph paths that lead from the proposi tion in question to relevant areas of the graph. The algorithm for searching is as follows . The directly relevant beliefs in the graph are found. A directly relevant belief is one which can be derived from P in one step by any one of these methods : - 1) Replace the verb by a similar (or opposite) verb . 2. 2 ) Repl ace the subject or object by an analogous (or compl ementary) noun. - 3) Replace the predicate adjective by a simi l ar (or opposite ) adjective . - 4) Generate a belief which implies P (or P implies) according to any one rule . These beli efs are the heads of paths to be searched. A certain amount of work i s used up just in finding them; say, 2 units for each relevant r ule used, 2 for each step of an anal ogy that is drawn, and 3 for each simil ar verb that is found, plus 6 units overhead even if nothing rel evant is found. If there is any work that remains unused after f i nding the heads of these paths , it is divided up among the paths for further sear ching. In the consistency search, all paths receive equal treatment . However, in the foundation search, the division among paths is affected by consistency. To compute the consistency of P with these paths , a recursive short- depth search is performed along each path; these searches are al otted, say, 1/3 of the remaining work. From the resulting consistencies, proportions are computed according to the following formulas : cg consistency of p with whole system cp consistency of p with this path relative proportion 110 - ~ c~ - c~ ~ 110 - cg - 50 ![Image](https://ijcai.org/proceedings/1969/fulltext/57/image_000002_23bd7bab58b7ed0a1e61a426f3acda8c760ca8487630d12821d54c20783509e1.png) The paths with highest proportions are searched first and receive a proport ionately greater wor k allotment . If not all the work along a path is exhausted, the remainder i s divided among t ne r emaining paths . If, after searching any path, enough rel evant b~liefs have been found to compute a credibilityexceedl ng 60 or below 40 , then the search of the rest of the paths is cancelled. ## Experiments The progr am performs t wo major experiment s . The first experiment assumes that t he bel i ef struc­ ture is unchanging . One proposition at a t ime i s presented to the structure and its credi bility is judged. I n the second experiment, the belief struc­ ture does change . After each proposition 's credi­ bility has been evaluated, it becomes i ncorporatod into the structure as a belief. The first experiment is run by presenting each belief in the structure to all the other beliefs and judging its credibility. The result can be compared with the prestipulated credibility of the beli ef. Then a list of new propositions is presented to the ' . t structure for eval uation. In both experlmen s, many factors of the eval uation ar e var ied. One factor to vary is the means of finding rele­ vant bel iefs . There are four variations : - 1) Use onl y rules - no definitions . 2. 2 ) Use (1) plus rules to find supersets . - 3) Use (l) and (2 ) plus "similar" and "opposite" rules . - 4) Use (1), (2), and (3) plus rules to find instances . Another factor to vary is the use of consistency. There are two variations : - 1) Use foundation and not consistency. - 2) Use also consistency. ## Other factors varied are : - 1) Weight of consistency rel ative to founda­ tion in computing credibility. 2. 2 ) Amount of work expended in search. - 3) The initial credibilities assigned each belief. All values of these factors are combined with every meaningful combination of other factors . ## Experimental Results For the data base URP.c1 in the experiments so far, a few interesting results were obtained. The search for relevant beliefs was effective when both r ules and supersets were utilized in the search. Without supersets, many relevant beliefs were missed. The addition of similar and opposite rules expanded the search enough to discover nearly all beliefs considered relevant by the experimenters . In only a handful of cases did the application of instance r ules improve the relevance search. The use or disuse of consistency made no notice­ able difference in the credibility computation. It is planned to see whether consistency will make a difference with different data or with work allotments that have not yet been tried. The amount of work alloted made a difference in the success of finding relevant beliefs. It is intended to measure this difference quantitatively, but techniques for t his have not yet been developed. Scal ing the credibilities of all the beliefs in the system by a factor x seemed to affect the credibility computed for an input proposition by that same multiple, x. This showed that the complex search combined with the quotient formulas for credibility still preserved linearity. search algorithm. Instead we explored a vari ety of procedures in an effort to learn more about their r espective merits in processing the same data base . We intend to discuss the validation problem in a future report.