Machine Discovery in the Presence of Incomplete or Ambiguous Data

Abstract

We define a logic for machine discovery, which we call learning with justified refutation, in the style of Mukouchi and Arikawa's learning with refutation. By comparison, our model is more tolerant of the learning agent's behaviour in two particular cases, which we call the cases of incomplete and ambiguous data, respectively. Consequently our formalism correctly learns or refutes a wider spectrum of language classes than its forerunner. We compare the class of language classes learnable with justified refutation with those learnable under other identification criteria. Comparison of learning with justified refutation from text and from informant shows that these two identification types are mutually incomparable in strength. Finally we consider whether either of the two formalisms for machine discovery are truly in the tradition of Popper's logic of scientific discovery, the original inspiration for Mukouchi and Arikawa's work.