This thesis addresses the question: "How can knowledge learnt through inductive inference be communicated in a multi-agent system?". Existing agent communication languages, such as KQML, assume logically sound inference methods. Unfortunately, induction is logically unsound. In general, machine learning techniques infer knowledge (or hypotheses) consistent with the locally available facts. However, in a multi-agent system, hypotheses learnt by one agent can directly contradict knowledge held by another. If an agent communicates induced knowledge as though it were logically sound, then the knowledge held by other agents in the community may become inconsistent. The answer we present in this thesis is that agents must, in general, communicate the bounds to such induced knowledge. The Version Space framework characterises inductive inference as a process which identifies the set of hypotheses that are consistent with both the observable facts and the constraints of the hypothesis description language. A Version Space can be expressed by two boundary sets, which represent the most general and most specific hypotheses. We thus propose that when communicating an induced hypothesis, that the hypothesis be bounded by descriptions of the most general and most specific hypotheses. In order to allow agents to integrate induced hypotheses with their own facts or their own induced hypotheses, the technique of Version Space Intersection can be used. We have investigated how boundary set descriptions can be generated for the common case of machine learning algorithms which learn hypotheses from unrestricted Version Spaces. This is a hard computational problem, as it is the equivalent of finding the minimal DNF description of a set of logical sentences. We consider four alternate approaches: exact minimization using the Quine-McCluskey algorithm; a naive, information-theoretic hill-climbing search; Espresso II, a sophisticated, heuristic logic minimization algorithm; and unsound approximation techniques. We demonstrate that none of these techniques are scalable to realistic machine learning problems.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:400670 |
| Date | January 2001 |
| Creators | Davies, Winton H. E. |
| Publisher | University of Aberdeen |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
Page generated in 0.0021 seconds