Version space learning with DNA molecules

Abstract

Version space is used in inductive concept learning to represent the hypothesis space where the goal concept is expressed as a conjunction of attribute values. The size of the version space increases exponentially with the number of attributes. We present an efficient method for representing the version space with DNA molecules and demonstrate its effectiveness by experimental results. Primitive operations to maintain a version space are derived and their DNA implementations are described. We also propose a novel method for robust decision-making that exploits the huge number of DNA molecules representing the version space.