AbstractMitchell's original work on version spaces [Mitchell, 1982] presented an analysis of the computational complexity of version spaces. However, this analysis proved somewhat coarse, as it was parameterized by s and g, the maximum sizes that the S and G sets reach during learning. As has been pointed out by Haussler , g can be exponential in the number of examples processed. This paper presents a more fine-grained analysis of the computational complexity of version spaces, demonstrates its equivalence to Mitchell's analysis, and instantiates it for two commonly used conjunctive concept description languages.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).