Experiments with a Search Algorithm for the Data Base of a Human Belief System

Sure, here's a blog-style summary of the paper "Experiments with a Search Algorithm for the Data Base of a Human Belief Structure":

TL;DR

This paper introduces a computational model designed to simulate how humans judge the credibility of propositions based on their existing beliefs. The authors developed a novel search algorithm for navigating a belief structure, finding that the way relevant beliefs are identified significantly impacts credibility estimation, with rule-based and superset searches proving most effective.

What Problem Does This Paper Address?

Understanding how humans evaluate the credibility of new information is a fundamental question in cognitive science and artificial intelligence. People don't just accept or reject statements blindly; they weigh them against their existing knowledge, experiences, and internal logic. This paper tackles the challenge of computationally modeling this complex process, specifically focusing on how a belief structure, represented as a graph of conceptualizations, can be searched to estimate the credibility of an input proposition. The authors aim to uncover which factors within this search process are most crucial for accurate credibility judgments.

Methods

The core of the paper is a computer model that simulates a human informant's belief processes. The model's "data base" is structured as a conceptual graph, comprising:

  • Conceptualizations (Facts): Propositions representing states of affairs, stored as ordered lists of name-tokens (e.g., (agent Bill) (action like) (object Mary)).
  • Beliefs: Conceptualizations paired with an affective attitude (acceptance, rejection, or neutral judgment).
  • Rules: Connectivity relations between conceptualizations, often in an "if-then" format, representing psychological implication (e.g., "if x likes y then x helps y").
  • Definitions and Classifications: Used to establish similarities, contrasts, and set memberships between concepts.

The model employs a two-levelled interpreter: a top-level supervisor and lower-level procedures. The key innovation is a search algorithm designed to estimate credibility. This algorithm navigates the conceptual graph, prioritizing paths based on factors like consistency, work allotment (computational effort), and "firmness" (pre-established credibility). The algorithm explores relevant beliefs using various methods, including:

  • Replacing verbs with similar/opposite ones.
  • Replacing subjects/objects with analogous nouns.
  • Replacing predicate adjectives with similar/opposite ones.
  • Generating beliefs that imply or are implied by the proposition.

Credibility itself is modeled as a function of foundation (evidence for/against a proposition) and consistency (consonance with relevant beliefs). The authors explore how different search strategies and the weighting of consistency influence the final credibility score.

Datasets

The paper describes data collection from a single human informant, a 30-year-old married woman interested in child-raising. Her beliefs about parent-child relations were collected over several weeks. This data was then structured into a data base containing approximately 700 facts, rules, definitions, and classifications. This dataset was specifically curated to be dense around the theme of child-raising.

Key Insights and Ideas

  • The importance of search strategy: The way the model identifies relevant beliefs is crucial. Simply using rules wasn't enough; incorporating "supersets" (broader categories) significantly improved the search. "Similar" and "opposite" rules also expanded the search effectively.
  • Consistency's nuanced role: The use or disuse of consistency in the credibility computation didn't make a noticeable difference in the initial experiments. This suggests that for this specific dataset and experimental setup, foundation might have been a stronger driver of credibility.
  • Data density matters: The authors found that an "intensive" design (many observations on one person) focused on a specific theme (child-raising) was more effective for building a useful belief structure than a broad, "extensive" approach.
  • The "model of a model" concept: The authors acknowledge that the informant's input represents her accessible model of herself, not necessarily her absolute, underlying beliefs, highlighting the inherent subjectivity in studying human cognition.

Key Results

The experiments varied several factors to understand their impact on credibility estimation:

  • Relevant Belief Search:
    • Using rules and supersets together was effective.
  • Adding "similar" and "opposite" rules helped discover nearly all relevant beliefs.
  • "Instance" rules (specific examples) rarely improved the search.
  • Consistency: Its inclusion or exclusion had no noticeable effect on credibility computation in the initial experiments.
  • Work Allotment: The amount of computational work allocated to the search made a difference, though this difference was not yet quantitatively measured.
  • Linearity: Scaling the credibilities of all beliefs by a factor x resulted in the computed credibility of input propositions also scaling by x, indicating a preserved linearity in the model's quotient formulas.

Limitations and Future Work

  • Data Collection Cumbersomeness: The manual data collection process was found to be cumbersome and time-consuming, suggesting a need for more automated, man-machine dialogue interfaces.
  • Natural Language Processing Challenges: While natural language input is desirable for expressiveness, the authors note the significant challenges in machine parsing of natural language into structured conceptualizations.
  • Validation: The paper focuses on the first phase of experimentation (building and testing the model) and explicitly states that validation of the simulation will be discussed in a future report.
  • Consistency's Role: The lack of impact from consistency in initial tests warrants further investigation with different data or work allotments.
  • Quantitative Measurement of Work: Techniques for quantitatively measuring the impact of work allotment on search success need to be developed.
  • Dynamic Belief Structures: The current experiments assume an unchanging belief structure. Future work will explore how the model handles changes in beliefs over time.

Summary updated

BibTeX
@inproceedings{1969experiments,
  title = {{Experiments with a Search Algorithm for the Data Base of a Human Belief System}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1969},
}
Figure